Sometimes, the only thing to say is this : gaaaaaaaaaaaaaaaaaaaaaahhhhhhhhhhh!!!
So, I had an innocent little thing on my small to-do list; “lfds700_list_asu_get_start_and_then_next() should be a macro, not a function”.
See, the lists have this convenience function, for iterating over the list. It takes the list state and a pointer to a list element, which is initialized before calling the function to NULL. If the pointer to the list element is NULL, then it is set to point to the first element in the list, otherwise, it is moved to point to the element after itself.
So you use it like this;
struct lfds700_asu_element *le = NULL;
while( lfds700_list_asu_get_start_and_then_next(ls, &le) ) { // TRD : do work }
The problem of course is you’re making a function call per iteration, which is totally not okay.
Now, there exist already a pair of macros, LFDS700_LIST_ASU_GET_START and LFDS700_LIST_ASU_GET_NEXT. That function uses them.
Now, given the expected usage, inside a while loop, we cannot in the macro version of the function use curley braces.
Problem is, those two macros, they both issue a load barrier - and that load barrier, on some platforms, is an atomic exchange - and that means we need some store, two temporary variables, and to get them… we’re using curley braces.
In fact this work touches upon this larger issue - I would like to be able to use all these macros inside while() brackets.
Exchange is not the only atomic operation which currently needs store - given the normalized form I’ve selected for CAS and DCAS, some platforms need store for those ops as well.
The only way I can see to get round this is to have these macros as inline functions.
That means changing the liblfds header files to be C files, and #including them rather than the header files.
The code below does not compile; “the left side of the assignment operator must be an l-value” (this for the right-most assignment operator).
int cr = 1; cr == 5 ? cr = 2 : cr = 3;
The code below does compile;
int cr = 1; cr == 5 ? (cr = 2) : (cr = 3);
This is true for both MSVC and GCC.
Turns out to be an apparently common compiler issue.
http://en.cppreference.com/w/c/language/operator_precedence
However, many C compilers use non-standard expression grammar where ?: is designated higher precedence than =, which parses that expression as e = ( ((a < d) ? (a++) : a) = d ), which then fails to compile due to semantic constraints: ?: is never lvalue and = requires a modifiable lvalue on the left. This is the table presented on this page.
One of the to-do’s was to reorder the hash API arguments.
This has pulled on a mental thread and led me to remove all the key and value arguments, where-ever they’re present.
So, for example, before we might have had;
enum lfds700_btree_au_link_result
lfds700_btree_au_link_element( struct lfds700_btree_au_state baus,
struct lfds700_btree_au_element baue, void key, void
value, int (key_compare_function)(void new_key, void
existing_key, void user_state), struct lfds700_btree_au_element
**existing_baue, struct lfds700_liblfds_prng_state *ps );
The key and value arguments are convenience arguments - the function sets them into *baue. However, the user can do this - and there are prototypes where the presence of those key and value arguments makes the prototypes ungainly and indeed more complicated.
So now this has been removed, and all the functions now simply deal with data structure elements, pointers to them, and the user uses macros to get/set keys and values.
Removed key/value from prototypes.
Since most of the data structures are now key/value, users must possess the capability to set value - and in fact, where key is fixed but value is not, value changes must be atomically written (i.e. atomic exchange) or they cannot be guaranteed to be visible to other threads.
This means the SET macros must call atomic exchange, and atomic exchange right now, as with all the other atomic macros, uses curley braces… i.e. there’s a compile error.
In fact, if we think about porting, and the use of asm with GCC, we see that asm is block-level entity; it cannot be used inside the conditional part of say a while.
So in fact those lovely atomic macros all have to go back to being inline functions, which means depending on the compiler to have an inline keyword.
I’m not very happy about this.
I’ve done all but one of the to-do list of code changes. There are some build config changes to do, but I can’t do them until the code changes are done.
Of the data structures which allow random access to elements (the lists, the btree) they now support the user setting value at any time. The others only support setting value at the time the data structure element enters the data structure.
As such, the former sets atomically (and issues a load barrier when getting a value) and the latter sets non-atomically (but with a store barrier), where the act of linking atomically to the data structure publishes value before the data structure element enters the data structure.
So that’s all good and well and makes sense and is done.
I’ve modified the macros so that they generally take one argument and ‘return’ a vaalue - it seems more intuitive to me, this way, for new readers.
I’ve updated the test programme, it again now compiles.
The atomic operations are all still macros, and with curley braces. What I’ve done for now (to compile) is accepted that LFDS700_PAL_ATOMIC_EXCHANGE uses curley braces and so other macros which use them (which is to say, SET_VALUE for the lists or btree) cannot be used inline.
I’m still thinking what to do about this - because there is another issue which is tied up with this, and that is the btree code for navigating a tree.
In the lists (the other random(ish) access data structure) the code for navigating the data structure (GET_NEXT, etc) exists as macros. After all, all we’re doing is accessing a pointer in a structure. The idea of making a function call to do this is nutso.
The btree code though for navigation is much more complex - it has to deal with a wide range of cases and often contains while() loops (“get smallest element”, etc). I want to be able to put this code in the conditional clause of a while() loop (i.e. get_by_position_and_then_directon()) but you can’t put a while() inside the conditional clause of a while() - which means you cannot use macros - which means you MUST write functions and you MUST use inlining.
There’s no getting away from it.
So, I’ve kept the btree navigation code as functions. They actually usually do quite a lot of work, so it’s not so bad.
What I’m thinking about now is, well, so, the lists and btree store keys and values. You can’t change the key, but you can change the value. That’s fine.
What about the non-random(ish) access data structures? the ringbuffer, the queue, the stack, etc - should they store only values, or keys as well? they won’t use the keys, but what I’m thinking is that in an application, a user may have a structure which is being passed about through many data structures and it would be very convenient to be able to preserve the key even when it passes through queues and ringbuffers and the like.
It’s fairly unobtrusive, because in almost all cases user are passing in to data structure functions only a pointer to a data structure element, which they prepped beforehand - so can set a key if they want, but they don’t have to - so not setting a key simply means… nothing at all.
This is not the case for the ringbuffer though - users do not see ringbuffer elements, they’re always internal to the data structure; they pass in arguments (value, and then would also be key, which would always be NULL when not used).
There’s also the overhead of copying the key around, but it’ll be on the same cache line as the value, so it’ll basically come from free.
Wheush!
I am just about code complete.
There’s one bit of code rearrangement I need to do, dependency stuff with structures, I’ve a hack in place right now - and that’s it. It!
Now I have to bring all the build configuration up to date and make test pass in debug and release on all platforms. After that, the docs need to be done. Then it’s release time.
Oh. I’d like also to add a mailing list to the site, but they’re impossible to set up.
pi@raspberrypi /tmp/temp/liblfds/liblfds7.0.0/test/build/linux_usermode_gcc_and_gnumake $ ../../bin/test -v test 7.0.0 (Release) (Dec 5 2015 01:33:39) liblfds 7.0.0 (Release, Linux (user-mode), ARM (32-bit), GCC >= 4.7.3) (Dec 5 2015 01:32:48) pi@raspberrypi /tmp/temp/liblfds/liblfds7.0.0/test/build/linux_usermode_gcc_and_gnumake $ ../../bin/test -r Test Iteration 01 ================= Abstraction Atomic Tests ======================== Atomic add...passed Atomic CAS...passed Atomic DCAS...passed Atomic exchange...passed Binary Tree (add-only, unbalanced) Tests ======================================== Alignment...passed Fail and overwrite on existing key...passed Random adds and walking (fail on existing key)...passed Random adds and walking (overwrite on existing key)...passed Freelist Tests ============== Alignment...passed Popping...passed Pushing...passed Pushing array...passed Popping and pushing (5 seconds)...passed Rapid popping and pushing (10 seconds)...passed Hash (add-only) Tests ===================== Fail and overwrite on existing key...passed Random adds and get (fail on existing key)...passed Random adds, get and iterate (overwrite on existing key)...passed Iterate...passed List (add-only, singly-linked) Tests ==================================== Alignment...passed New ordered...passed New ordered with cursor (5 seconds)...passed List (add-only, singly-linked) Tests ==================================== Alignment...passed New start...passed New end...passed New after...passed Queue Tests =========== Alignment...passed Enqueuing...passed Dequeuing...passed Enqueuing and dequeuing (5 seconds)...passed Rapid enqueuing and dequeuing (5 seconds)...passed Queue (bounded, single consumer, single producer) Tests ======================================================= Enqueuing...passed Dequeuing...passed Enqueuing and dequeuing (8 seconds)...passed Ringbuffer Tests ================ Reading and writing (5 seconds)...passed Stack Tests =========== Alignment...passed Popping...passed Pushing...passed Pushing array...passed Popping and pushing (5 seconds)...passed Rapid popping and pushing (5 seconds)...passed
I realised last night that the porting abstraction layer would only work on x86, x64 and ARM.
All the other processor types which in principle work (when using GCC this is) simply were not present in the porting layer code.
So I need to implement them - but this led to an issue; the porting abstraction layer code was unravalled, to make it easy to understand. With another four or five processors, though, where every processor needs two versions (GCC < 4.7.3 and GCC >= 4.7.3) and most of the processors have 32 and 64 bit versions - it wasn’t going to fly.
The unravelled layout is from 6/6.1.1, a long time ago (after they were released) I factorized, and it turned out to come down to processor, compiler and operating system.
So I’ve gone back to this.
So, that’s fine, I need to add some boilerplate code to perform automated checking of what the user has or has not implemented, but that’s routine. The porting guide needs to be rewritten.
I’m going to do a bunch of work on the data structure docs now though, they’re stable now and they need a bunch of work done to them.
Have finished the second pass of the liblfds porting guide.
Now the big work; all the API pages.
Writing quality docs takes time.
I think I can do at most two APIs per day. There’s about ten to do…
Then there’s the test porting guide.
Then I need to update all build config.
Then I can release.
Writing the btree docs.
Something I’ve had in the middle of my mind for a while - I’m going to need to write two different get-value and set-value macro pairs, one set which guarantees by the time it returns from the set all readers will be able to see the new value (i.e. set uses an atomic set, get issues a load barrier), and another which does not offer this guarantee (set issues a store barrier, get issues a load barrier).
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…
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!
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.
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.
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 <assert.h>. I thought seriously about dropping asserts, to simplify build, but they’re just too useful for debugging.
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.
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.
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.
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.
Changed from the whole position/direction nonmenclature to absolute position/relative position nonmenclature .
So, well, time to ’fess up.
Few days ago I was looking at the queue code, and the way the ABA counter were being handled looked like it needed to be looked over. Then I realised there was something very odd going on - I was seemingly setting (and by expensive atomic adds!) ABA counters which were later overwritten with new values before added to the queue.
Then after some time thinking about this (and getting a new laptop, which I’ve spent a day or so, so far, configuring) I realised how I was handling the ABA counters in the freelist and stack was completely bonkers - I was using an atomic add on a per-state variable, but in fact no atomic add is needed at all, as you can use the counter in the top pointer, and increment it in the DWCAS. In fact, I’d really got the wrong end of the stick…
So now the freelist and stack no longer use atomic add, and in fact their elements are a bunch smaller - their next pointer is just a pointer, no counter, and none of the varibles in it are cache line/ERG aligned/padded.
I’m now looking over the queue code to make it right too.
I’ve also spent some time now reviewing all the code for proper barrier use - and here again, I had blundered, and was thinking about barrier use in not quite the right way; now I think I am getting it right, really right, and that’s led to a bunch more load barriers in the add-only code, and also shifted around where the store barriers are.
Once the queue is sorted out, I’ve one or two more minor bit of code checking to do, then it’s back to docs.
I’ve passed the “mid-December” estimate, but it’ll be out before the end of the month.
Now I just need to think about this…
http://polyglotplayground.com/2015/04/30/Problem-with-Michael-Scott-Lock-Free-Queue/
Whoaz…
So, for now at any rate, I’m using the PRNG to generate an initial value for a queue element next pointer counter.
The basic problem is that in the queue, elements have a next pointer, which has a counter - because it is the subject of DWCAS - unlike the stack/freelist, where the elements only have next pointers.
Because it has a counter, when an element leaves the queue, it takes that counter with it - but it is actually only valid for the queue the element just came from - but it CAN end up being mistaken for a valid value in a new queue the element in enqueued to.
Okay, so, I’m about to make quite a claim - and I do not make it lightly, and I make it in full knowledge that I am extremely likely to be completely wrong. M&S are experts in the field, and I am not.
This is the dequeue psuedo-code from their white paper.