What are ck_queue.h guarantees?

[Lev Serebryakov]

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.

For example, there are a lot of addresses enumeration under locks in
networks drivers, like this:

if_maddr_rlock(ifp);
CK_STAILQ_FOREACH(inm, &ifp->if_multiaddrs, ifma_link) {
if (inm->ifma_addr->sa_family != AF_LINK)
continue;
crc = ether_crc32_le(LLADDR((struct sockaddr_dl *)
inm->ifma_addr), ETHER_ADDR_LEN);

/* Just want the 6 most significant bits. */
crc >>= 26;

/* Set the corresponding bit in the filter. */
hash[crc >> 4] |= 1 << (crc & 0xf);
}
if_maddr_runlock(ifp);

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?

[Kristof Provost]

Post by Lev Serebryakov
Hello Freebsd-hackers,
====
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().

Post by Lev Serebryakov
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

[Lev Serebryakov]

Hello Kristof,

Post by Lev Serebryakov
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().

Oh, I've should look inside these functions before asking. Thank you for
pointing me out.

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.

Yep, and it is very misleading :-)


--
Best regards,
Lev mailto:***@FreeBSD.org