Need more get/set macros

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).

Update

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.

Update

Have finished the second pass of the liblfds porting guide.

Now the big work; all the API pages.

Factorized the porting abstraction layer

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.

tests pass on debug and release on 32 bit ARM

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

99.9% code complete

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.

Musing

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.

Update

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.

Update

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.

API changes

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.