What are ck_queue.h guarantees?

[Kristof Provost]

On 13 Oct 2018, at 8:40, Lev Serebryakov wrote:
> Hello Freebsd-hackers,
>
>   Concurrency Kit documentation says:
>
> ====
> ck_queue is a queue.h-compatible implementation of many-reader-single-
> writer queues. It allows for safe concurrent iteration, peeking and 
> read-
> side access in the presence of a single concurrent writer without any
> usage of locks.
> ====
>
>  But in all places at kernel I peeked, CK_XXXX macros are protected by
> locks. Yes, even read ones.
>
Note that the implementation of if_maddr_rlock() doesn’t actually take 
a lock. Instead it calls epoch_enter_preempt().

>   Why is it so? Why do we bother to use CK_XXX API (which adds all 
> needed
> barriers and uses CASes) if all accesses are protected by locks, 
> anyway?
>
ck_queues are safe to use, even when elements are being added or 
removed. Missing new elements is usually fine, but what happens if an 
element we’re looking at right now is being removed by a different 
thread?
We might still be using it when the removing thread frees it. That’s 
what the epoch code protects against. It allows the removing thread to 
know when no other thread is using the removed item any more (and thus 
when it’s safe to actually delete it).
Hence the ‘lock’ and ‘unlock’ calls. They don’t actually take 
a lock, and there’s no contention. Many threads can enter the section 
between lock and unlock at the same time.

I suspect the ‘lock’/‘unlock’ naming is mostly historical here: 
i.e. it used to be a real lock, and when it was replaced by the 
epoch-based approach the functions were not renamed.

Best regards,
Kristof