See also: https://fedorahosted.org/389/ticket/48411

attachment
0001-Ticket-45-Upgrade-liblfds-to-710.patch

This is a very large patch: But it's what we've been waiting for. LFDS710 is much faster than the previous version.

We are now using the unbounded queues, so there is no possibility of silent job loss. This is a huge win in reliability.

LFDS710 also has some cleanup callbacks, what makes shut down far cleaner and more reliable.

The upgrade now is much faster, which exposed issues with CPU cache sync on my machine, so the get/set and checks for the FSM are now CPU barricaded correctly.

Because we don't have the silent job drop issue, we can now push the stress test past 1000 events, with no drop. At high loads (4:1 ration of client to server threads), and large job counts, we can cause accept() timeouts on the server. This can be improved, but we are now working in the order of 200 connections accepted, read, written to, and closed per second.

I have tested this extensively with the test suites, and stress test, and there are no crashes, leaks, use after frees or races.

It's still a pain that every file and symbol of liblfds is versioned e.g. liblfds710.h, lfds710_stack_state, etc.
It means once liblfds 7.1.1 is released, it is a heaping pile of search/replace, enormous git diffs, etc. etc. to review for subtle mistakes. It is almost acceptable that nunc-stans hides all of this from other applicatios.

{{{
if test "$enable_debug" = "yes" ; then
- lfds_make_target=ardbg
+ lfds_make_target=so_dbg
else
- lfds_make_target=arrel
+ lfds_make_target=so_rel
fi
}}}
Does this mean that 389 will need to link against liblfds .so files? Or is liblfds still a "hidden implementation detail" of nunc-stans?

{{{
+ LFDS710_MISC_BARRIER_LOAD;
}}}
This seems . . . inelegant.

Replying to [comment:5 rmeggins]:

It's still a pain that every file and symbol of liblfds is versioned e.g. liblfds710.h, lfds710_stack_state, etc.
It means once liblfds 7.1.1 is released, it is a heaping pile of search/replace, enormous git diffs, etc. etc. to review for subtle mistakes. It is almost acceptable that nunc-stans hides all of this from other applicatios.

I'm talking to the author of lfds about how we can handle this. Right now, I have added the queue / stack function abstractions which helps to limit this. I'm not worried TBH.

{{{
if test "$enable_debug" = "yes" ; then
- lfds_make_target=ardbg
+ lfds_make_target=so_dbg
else
- lfds_make_target=arrel
+ lfds_make_target=so_rel
fi
}}}
Does this mean that 389 will need to link against liblfds .so files? Or is liblfds still a "hidden implementation detail" of nunc-stans?

389ds will link to nunc-stans, and nunc-stans links to the lfds library. Ns does install it correctly. So 389 doesn't need to be aware of this at all.

{{{
+ LFDS710_MISC_BARRIER_LOAD;
}}}
This seems . . . inelegant.

Without it, we cannot guarantee that we are reading the content of the atomic set integer. The load barrier is far cheaper in CPU time than the ATOMIC_IS_ZERO macro you have in the file. So this is staying because without it, we have all kinds of issues with cpu sync. LFDS710 is now fast enough to expose cache coherency issues on my laptop, so we need this if we want sane operation. This is the reality of the lock free library world :)

As a follow up, with the LOAD / STORE barriers, I think there are a few places in the code still not done correctly, so I need to actually update some more code to finish making this properly thread / numa / cache safe.

Looking at the patch 0001-Ticket-45-Upgrade-liblfds-to-710.patch, it is not "diff", but the file replacements... Not sure what we are supposed to do as a reviewer... If liblfds is a given library and we are a user, I could just ack this ticket like this is for upgrading liblfds... In that case, I guess we need a place to report a bug/rfe?

A lot of it is file replacement, but there are changes in ns_thrpool.c to enable the change. Do you want me to split the patch into two, one for the file replacement, and one for the code changes to use it? This might make the review easier.

From the DS perspective, we don't really care until we go to release a new version of NS which is still some time weeks away with the other tickets I want to complete....

Replying to [comment:9 firstyear]:

A lot of it is file replacement, but there are changes in ns_thrpool.c to enable the change. Do you want me to split the patch into two, one for the file replacement, and one for the code changes to use it? This might make the review easier.

Or just tell us which files we are supposed to review... So, ns_thrpool.c is one of them. Yes, I see the real diffs.

From the DS perspective, we don't really care until we go to release a new version of NS which is still some time weeks away with the other tickets I want to complete....

Ok!

Or just tell us which files we are supposed to review... So, ns_thrpool.c is one of them. Yes, I see the real diffs.

{{{
Makefile.am | 2 +-
configure.ac | 2 +-
m4/lfds.m4 | 32 +-
ns_thrpool.c | 283 ++++++--
tests/cmocka/stress_test.c | 19 +-
tests/cmocka/test.c | 47 +-
}}}

These are the nunc-stans parts that were changed to accommodate this.

Replying to [comment:7 firstyear]:

As a follow up, with the LOAD / STORE barriers, I think there are a few places in the code still not done correctly, so I need to actually update some more code to finish making this properly thread / numa / cache safe.

If this really is necessary, then we need to be very careful about this, and document it i.e. how do I, as a user of liblfds, know where/when to use LFDS710_MISC_BARRIER_LOAD/STORE? Do they need to be the very first/very last statements in the function? Do we have to be careful about using return/goto non-local function exit? If the user of liblfds has to be a CSE/EE, that's a high barrier to entry, and a recipe for hard-to-debug problems.

Replying to [comment:12 rmeggins]:

Replying to [comment:7 firstyear]:

As a follow up, with the LOAD / STORE barriers, I think there are a few places in the code still not done correctly, so I need to actually update some more code to finish making this properly thread / numa / cache safe.

If this really is necessary, then we need to be very careful about this, and document it i.e. how do I, as a user of liblfds, know where/when to use LFDS710_MISC_BARRIER_LOAD/STORE? Do they need to be the very first/very last statements in the function? Do we have to be careful about using return/goto non-local function exit? If the user of liblfds has to be a CSE/EE, that's a high barrier to entry, and a recipe for hard-to-debug problems.

Whoa no. This isn't because we are a user of LFDS queue or stacks that we need this.

Now, if the library was:

{{{
- Single thread accesses and works on job
- job goes to queue
- some thread x dequeues and works on job
- only thread x works on job
- thread x calls job_done, or re-queues.
}}}

Everything would be great. The stack and the queues are safe, and provide these guarantees for us.

But that's not the case. We have jobs that can be accessed after they are queued (which violates the statemachine, thus the ASSERTS and explosion. We also have jobs that are accessed in other ways, ie signal jobs, timers, io .... We may keep a reference to it, then attempt to call job done, or other things even after it's been queued / dequeued in a variety of ways.

The statemachine guarantees that the job isn't tampered with during function() call, or while queued, but outside of that we have no guarantee about other threads peeking or reading jobs. We need to keep the jobs that are out of the queues, synced correctly for access by multiple threads.

This is the problem.

Because we have many threads now interacting with a job, and they have data in them that is set/get, we now have to deal with all the gorey lovely horrible details of cache synchronisation and coherency. Because you want to avoid locks, now we get to use the raw CPU primitives.

I highly advise that you read http://www.liblfds.org/downloads/white%20papers/[Misc]%20-%20[Drepper]%20-%20What%20Every%20Programmer%20Should%20Know%20About%20Memory.pdf for more about this topic.

It just so happens that LFDS provides the LOAD / STORE barriers that are needed to allow lock free synchronisation of these values, and that's what the barriers are for. Forget about the other parts of LFDS, the LOAD and STORE is to make this library actually thread safe when you are accessing an ns_job_t.

Again, I really advise reading of the Drepper paper, it's excellent.

If you don't like the barriers on the ns_job_t values, then the only alternative is a mutex on the ns_job_t during these function calls (we can still use LFDS queues and stacks regardless).

There are still a few more fixes coming for this part of the code to make it safer before we want to release.

To apply the patch 0001-Ticket-45-Upgrade-liblfds-to-710.patch​ onto the master branch, do we need to have some other patches? "git-am" fails for me...
{{{
error: patch failed: liblfds/liblfds.sln:1
error: liblfds/liblfds.sln: patch does not apply
error: patch failed: liblfds/liblfds.vcproj:1
error: liblfds/liblfds.vcproj: patch does not apply
error: patch failed: liblfds/test/test.sln:1
error: liblfds/test/test.sln: patch does not apply
error: patch failed: liblfds/test/test.vcproj:1
error: liblfds/test/test.vcproj: patch does not apply
Patch failed at 0001 Ticket 45 - Upgrade liblfds to 710
.....
}}}

In addition to this comment, I should point out that the improvement in lfds710 and nunc-stans have made the library much faster, to the point I can now expose these coherency issues on my own laptop, let alone a large multicore / numa system. My goal is to make the library safe first, because in it's current release it's not thread safe.

Fix for git am
0001-Ticket-45-Upgrade-liblfds-to-710.2.patch

Was nunc-stans ever thread safe?

I heard the diff with https://github.com/liblfds/liblfds/tree/master/liblfds/liblfds7.1.0 is very small. And the feedback is sent to the "upstream".
{{{
One was for compiler error, one for allowing non-gcc to work
}}}

For the upgrade, currently in addition to replacing nunc-stans/liblfds/ with the new version from the github, I learned we need to manually modifying lfds710_ to lfds711_*. But the modify part will be automated and/or taken care in the future. If that's the case, you have my ack.

Replying to [comment:16 rmeggins]:

Was nunc-stans ever thread safe?

No, but it should be. We should always be writing safe code first, and making it fast after. Especially for something as critical as Directory Server connection and thread management.

From this website itself,

https://fedorahosted.org/nunc-stans/

"""
Nunc Stans is an event framework wrapper that provides a thread pool for event callback execution. It provides thread safety to event frameworks by isolating and protecting the thread safe parts from the non-thread safe parts, and allows multi-threaded applications to use event frameworks that are not thread safe.
"""

So I think the goal is thread safety :)

By my question, I was not implying that nunc-stans was not intended to be thread safe. Of course thread safety is necessary. I was genuinely curious, and I am quite surprised that nunc-stans has never been thread safe, and I simply do not understand why. I understand that there were and are still some bugs that caused thread-unsafe access in certain conditions, but I am quite surprised that nunc-stans, in general, was not designed and implemented to be thread safe. I guess I need to go back to first principles to understand why. Yes, the Drepper paper, among other things.

I did the cherry pick, and ran the tests again to be 100% sure.

commit 9aca82a4d7cc5ac1d15fcdd2266c65f4cc88d27d
Writing objects: 100% (124/124), 63.31 KiB | 0 bytes/s, done.
Total 124 (delta 45), reused 0 (delta 0)
To ssh://git.fedorahosted.org/git/nunc-stans.git
309649d..9aca82a master -> master