Bitcoind aborts on startup: ./db/skiplist.h:152 Assertion `n >= 0' failed. #2416

Hi,

I just tried to upgrade from 0.7.x to 0.8.1 compiling bitcoin-0.8.1-linux.tar.gz from source, but the resulting bitcoind executable fails with an assertion in ./db/skiplist.h. This is on debian-mipsel squeeze, compiled via

make -C src/src -f makefile.unix CXXFLAGS="-O2 -march=loongson2f"
DEBUGFLAGS=

using gcc (Debian 4.4.5-8) 4.4.5

(Note the unusual architecture: 32-bit MIPSEL!)

A backtrace recorded from GDB: (gdb) run Starting program: /usr/local/bin/bitcoind [Thread debugging using libthread_db enabled] bitcoind: ./db/skiplist.h:152: leveldb::SkipList<Key, Comparator>::Node* leveldb::SkipList<Key, Comparator>::Node::Next(int) [with Key = const char*, Comparator = leveldb::MemTable::KeyComparator]: Assertion `n >= 0' failed.

Program received signal SIGABRT, Aborted. 0x2b221048 in raise () from /lib/libc.so.6 (gdb) bt #0 0x2b221048 in raise () from /lib/libc.so.6 #1 0x2b2261f8 in abort () from /lib/libc.so.6 #2 0x2b218238 in __assert_fail () from /lib/libc.so.6 #3 0x0063884c in leveldb::SkipList<char const, leveldb::MemTable::KeyComparator>::FindGreaterOrEqual(char const\ const&, leveldb::SkipList<char const, leveldb::MemTable::KeyComparator>::Node**) const () #4 0x00638944 in leveldb::SkipList<char const, leveldb::MemTable::KeyComparator>::Insert(char const* const&) () #5 0x00638294 in leveldb::MemTable::Add(unsigned long long, leveldb::ValueType, leveldb::Slice const&, leveldb::Slice const&) () #6 0x00646fdc in leveldb::(anonymous namespace)::MemTableInserter::Put(leveldb::Slice const&, leveldb::Slice const&) () #7 0x00647464 in leveldb::WriteBatch::Iterate(leveldb::WriteBatch::Handler) const () #8 0x006475c4 in leveldb::WriteBatchInternal::InsertInto(leveldb::WriteBatch const_, leveldb::MemTable_) () #9 0x0062c550 in leveldb::DBImpl::RecoverLogFile(unsigned long long, leveldb::VersionEdit_, unsigned long long_) () #10 0x0062d734 in leveldb::DBImpl::Recover(leveldb::VersionEdit) () #11 0x0062e6b8 in leveldb::DB::Open(leveldb::Options const&, std::string const&, leveldb::DB**) () #12 0x0061c38c in CLevelDB::CLevelDB(boost::filesystem::basic_path<std::string, boost::filesystem::path_traits> const&, unsigned int, bool, bool) ()

---Type <return> to continue, or q <return> to quit--- #13 0x0061ca70 in CBlockTreeDB::CBlockTreeDB(unsigned int, bool, bool) () #14 0x00496dac in AppInit2() () #15 0x0049a290 in AppInit(int, char**) () #16 0x0049aeb0 in main ()

This happened on first invokation, I do not yet have any leveldb files present. The only files touched by 0.8.1 in my ~/.bitcoin directory are debug.log and peers.dat.

cheers,

David

Did you use a clean datadir or an old 0.7 datadir with the old block-storage? Perhaps there is problem with upgrading to 0.8 format?

As bitcoin doesn't upgrade database by default (without -loadblock= arguments), this shouldn't be an issue IMO.

I just tried with ~/.bitcoin moved out of the way, but I'm still hitting the same assertion. Are there any other leftovers from 0.7 other than ~/.bitcoin that need to be taken care of?

@sipa Can you have a look at that seems LevelDB related.

Same problem with bitcoin 0.8.3

bitcoind: ./db/skiplist.h:152: leveldb::SkipList<Key, Comparator>::Node* leveldb::SkipList<Key, Comparator>::Node::Next(int) [with Key = const char*, Comparator = leveldb::MemTable::KeyComparator]: Assertion `n >= 0' failed.

I'd really like to eventually upgrade to to the 0.8 branch... :/

This is almost certainly due to missing mips atomics in leveldb: https://code.google.com/p/leveldb/issues/detail?id=104&q=mips

From the looks, Debian attempted to patch some in, but didn't fare so well. Seems the gcc intrinsics should suffice for a hammer solution.

That thought already crossed my mind, but then looking at atomic_pointer.h, it seems the CPU-specific implementations only deal with memory ordering semantics. On my single-core MIPS system, there should be no problems WRT memory ordering when accessing the same 4-byte quantity from different threads. The only problem could be GCC introducing memory ordering issues due to read/write reordering on code optimization. But compiling with -Os should have removed any such issues for class AtomicPointer (by keeping all accesses cleanly in non-inlined functions).

Note that compiliation is already setting -DLEVELDB_CSTDATOMIC_PRESENT, how likely is it that <cstdatomic> is broken on MIPS?

Still, going to run some more tests...

@dvdkhlng I was under the assumption that stdatomic wasn't present in your toolchain and you took the debian patch, sounds like that's not the case. Either way, I think skiplist_test would be a good next step, if you haven't tried that already.

@theuni: looks like you are right, it's a atomic operations problem. cstdatomic is either broken with the Debian Mipsel Squeeze toolchain or the leveldb code does uses it in a broken way.

Implementing MemoryBarrier as

asm volatile ("" : : : "memory");

makes bitcoin work for me. The proper implementation for those newer multi-core MIPSes (Loongson 3A, Octeon etc.) should be :

asm volatile ("sync" : : : "memory");

This version is curently running here, though on a single-core system there shouldn't be any perceivable difference.

To make the implementation somewhat portable across Linux distributions, we might have to change that into:

asm volatile (".int 0x0f" : : : "memory");

This generates the same code, but doesn't rely on GNU As to parse the 'sync' mnemonic. GNU As will only allow sync opcode assembly when MIPS III or newer architecture was specified via GCC march= switch. However on Debian Mips, default settings compile for Mips1 only, to support all the older gear.

Now on old Mips1 CPUs, leveldb would SIGILL at runtime, but then those old CPUs may not be capable to keep up with the Bitcoin network's load anyways. All recently manufactured MIPS CPUs/SoCs I know of support at least the MIPS III instructions (most should do MIPS32r2, Loongson 2f is very backwards in only supporting MIPS III, but that's due to patents).

A proper patch would look like this:

Index: bitcoin-0.8.5-linux/src/src/leveldb/port/atomic_pointer.h
===================================================================
--- bitcoin-0.8.5-linux.orig/src/src/leveldb/port/atomic_pointer.h      2013-09-12 12:43:31.000000000 +0200
+++ bitcoin-0.8.5-linux/src/src/leveldb/port/atomic_pointer.h   2013-09-18 04:24:17.358004348 +0200
@@ -68,6 +68,18 @@
 }
 #define LEVELDB_HAVE_MEMORY_BARRIER

+// Gcc on MIPS
+#elif defined(__mips) && defined(__GNUC__)
+inline void MemoryBarrier() {
+   /* Actually a 'sync' instruction, though that can only be assembled
+      with the right -march= switch present, so compilation would fail with
+      default GCC options on Debian-Mipsel (which compiles for Mips1 per
+      default) */
+  __asm__ __volatile__(".int 0x0000000f" : : : "memory");
+}
+#warning "Mips detected"
+#define LEVELDB_HAVE_MEMORY_BARRIER
+
 // Mac OS
 #elif defined(OS_MACOSX)
 inline void MemoryBarrier() {

Note WRT my comment above: Markdown ate the underscores around th asm keywords. Should be

__asm__

(somehow Github doesn't allow me to edit my comment above, maybe Debian Mipsel's Firefox is too old ? :)

@dvdkhlng Nice sleuthing. Though now that the issue is nailed down, I'd suggest taking it upstream. I'm not sure that the bitcoin devs would be interested in carrying this.

Perhaps you could ping the leveldb devs on the bug report above?

Agree with @theuni, this issue should be taken upstream. We use libraries such as boost and leveldb to not have to bother with architecture-specific details, and going into mips assembly is just a step to far. We don't have any way to test this either.