Ci20 / MIPS32

Just ordered a Ci20, a dual-core MIPS32 dev board, runs Linux.

I think I can boot it to Android too, which would give me some capability to compile and test for that platform.


Well, yesterday was a blow-out – I’ve ODed on docs.

Today was good though, haven’t touched the docs, been working on code.

It’s been a day’s worth of tidying up – getting enum value names right, checking all the structure aligns, realised I’d blundered with atomic isolation for I still need a “double” atomic isolation on CAS architectures, normalized the API names for adding data elements to a structure (it’s now “insert”, where-ever it makes sense – still push/pop enqueue/dequeue for freelist/stack and the queues), and so much other stuff I can’t even remember – oh, changed backoff config so the number of NOPS per timeslot is hardcoded in a #define for CAS and DWCAS. Having them configurable just didn’t make sense – you can hardcode it if you’re on one platform, but chances are your software will run on a variety of different versions of an architecure, and with different clock speeds. There’s no real use in run-time configurability. Also, by being varibles in memory, it’s possible that the backoff code might need to do a TLB lookup and memory access! which blows that whole thing out of the water.

I feel I’m very close now to actually really being code complete, with nothing else in my mind that needs to be done.

new intro paragraph

I’ve written a new intro paragraph, for readers who do not know what lock-free data structures are and do. Love it 🙂

Lock-free data structures are thread-safe and interrupt-safe (i.e. the same data structure instance can be safely used both inside and outside of an interrupt handler), never sleep (and so are safe for kernel use where sleeping is not permitted), operate without context switches, cannot fail (no need to handle error cases, as there are none), perform and scale literally orders of magnitude better than locking data structures, and ”liblfds” itself (as of release 7.0.0) is implemented such that it performs no allocations and compiles not just on a freestanding C implementation, but on a bare C implementation.


As ever, working on the docs.

Freelist, Misc, Ringbuffer and Stack are now good enough to release.

That leaves both lists, both queues and the hash.

The porting and usage guides are good enough to release, although the porting doc for test revealed the need for some work on the test abstraction layer.

The list, queue and hash docs will be completed tomorrow.

Once the final code work is done, I can then update the build configurations. There’s this… dual convergence, going on – the docs and the code – change one and you have to change the other, so doing work on either means you need to change the other. The goal is to get to the point where you need to change neither, then you can release.


Amazin’ really how wrong things can be and you don’t notice until almost the last moment.

The way I had the build directories named, and the detection of OS platforms, was wrong.

I realised because I came to make a freestanding build with GCC. The build directory really is about toolchains only – it’s about getting a build going, even if the build fails (because the porting layer is missing).

The porting layer is separate and different from the build tools, i.e. GCC and gnumake will give you build on any platforms, say an RTOS with no hosted implementation – but there’s no porting layer for that platform.

Of course I’ve always known this, but it turns out it’s not actually really what had been *done*.

So now the build dirs are named after the toolchain/system header requirements, and there’s a new build, “gcc_gnumake”, which uses “-ffreestanding -nodefaultlibs -nostdinc -nostdlib”, i.e. the real McCoy. The hosted implementation is almost the same, in fact – all it takes is . I thought seriously about dropping asserts, to simplify build, but they’re just too useful for debugging.


Gettin’ on.

Currently focusing on the stack docs. Making them perfect, or as perfect as they can reasonably be. They’re going to be the template for the other pages. So I’m working to get them right, really right (and so also to have made all the code base changes which come from docs) and then to iterate over all the other doc pages and produce them correctly in basically one more pass.

A lot of the time editing is actually spent waiting for the mediawiki to load and save pages – to be more efficient, you really need to cut down the number of passes.


Getting on.

The liblfds API has been renamed misc, it’s more self-explanatory.

All the init() functions are back to being init_valid_on_current_logical_core().

User callbacks no longer receive a user state argument, rather, there is a macro for getting the user state value from the data structure state.

Key compare functions and hash functions no longer receive a user state argument – what they do is too small and atomic for this.

The key compare function (and the hash function) has the const qualifier now, so it has the same prototype as the qsort() callback.

The queue cleanup function has an extra argument, a flag, which is raised when the dummy element is given (there’s no other way for the user to know the key and value in that element are invalid).

The ringbuffer cleanup function has an extra argument, which indicates if the element is unread.

Docs are coming along nicely.

I expect to release inside a week now.


Huh, the mediawiki is now at 499 articles 🙂

So, been a full complete long day of doc writing.

Second pass done for btree, freelist, liblfds, hash and stack.

Tomoz it’ll be the lists, the queues and the ringbuffer.

Then I guess the test porting guide.

Then third pass for everything… uuhhhhh!


Let’s see…

Removed the key hash/compare function over-rides from the non-init() functions. Their use is going to be so rare they don’t carry their own weight, and people can add them very easily.

The extra set macro didn’t happen. Think about it – you can atomically store (exchange), use a store barrier, or do nothing. What does a store barrier get you? it get you ordering… BUT ONLY A PER THREAD BASIS. Writes, if/when they do go out, are in order – sure – but only with respect to writes from the same thread. Fat lot of use that is! however, I now undersstand the GCC >= 4.7.3 docs on atomic instrincs – they stuff they’re alluding to is the difference between no barriers, barriers or atomic. They’re TOTALLY TOALLY UTTERLY TOTALLY UTTERLY HUMUNGOUSLY UNCLEAR – unless you already know what they’re talking about, in which case you can figure out what they’re getting at.

Spent five hours so far today on docs, feel like I’ve got bugger all done – some new pages for btree enums, the btree query page, that bit of experimentation with a new set. Ten more APIs to go…