Add the Linux Kernel style thread-based simple RCU. It supports sparse checking [1].

With sparse, it will report:

main.c: note: in included file:
thrd_rcu.h:95:42: warning: Using plain integer as NULL pointer
thrd_rcu.h:95:42: warning: Using plain integer as NULL pointer

It is from the pthread_mutex_t initializer, we can ignore it.

[1] https://www.kernel.org/doc/html/latest/dev-tools/sparse.html

From the ThreadSanitizer report, ignore the volatile type data race warning [1][2], there still have the data race warning.

[reader 2835343104] 0
[reader 2826950400] 0
[reader 2818557696] 0
[reader 2810164992] 0
[reader 2801772288] 0
[updater 2793379584]
==================
WARNING: ThreadSanitizer: data race (pid=434539)
  Write of size 8 at 0x7b0400000000 by thread T6:
    #0 free ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:711 (libtsan.so.0+0x37ab8)
    #1 updater_side /home/xxxx/linux2021/concurrent-programs/thrd_rcu/main.c:41 (main+0x1a38)

  Previous read of size 4 at 0x7b0400000000 by thread T5:
    #0 reader_side /home/xxxx/linux2021/concurrent-programs/thrd_rcu/main.c:23 (main+0x1898)

  Thread T6 (tid=434546, running) created by main thread at:
    #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:969 (libtsan.so.0+0x605f8)
    #1 main /home/xxxx/linux2021/concurrent-programs/thrd_rcu/main.c:59 (main+0x1429)

  Thread T5 (tid=434545, finished) created by main thread at:
    #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:969 (libtsan.so.0+0x605f8)
    #1 main /home/xxxx/linux2021/concurrent-programs/thrd_rcu/main.c:56 (main+0x13fd)

SUMMARY: ThreadSanitizer: data race /home/xxxx/linux2021/concurrent-programs/thrd_rcu/main.c:41 in updater_side
==================
[reader 2784986880] 2793379584
[reader 2744121088] 2793379584
[reader 2735728384] 2793379584
[reader 2727335680] 2793379584
[reader 2718942976] 2793379584
ThreadSanitizer: reported 1 warnings

I try to debug it, but cannot figure out where the wrong is. Not sure if it is a false positive or not.

[1] https://gcc.gnu.org/pipermail/gcc-patches/2020-June/547633.html [2] https://gcc.gnu.org/gcc-11/changes.html

The macros of coroutine provided in the original version may cause misusing, such as declaring a set of coroutines by wrapping several pairs of cr_begin and cr_end macro in a loop, which may cause unexpected result while someone waits a condition to pass with cr_wait macro and that condition failed. To avoid such misusing, we have to abstract the usage of controlling macros that would be invoked in the coroutine function. With in this version, a set of macros are introduced, which aim to provide standard style for someone to declare or access the coroutine function and its corresponding context. One should declare a coroutine function with cr_func_def macro, and its corresponding context with cr_context macro, the argument name provides to those macros for the same coroutine should be identical. After declaration, one could run a coroutine by cr_run macro. Wrapping a set of cr_run macros in a loop makes several coroutines execute concurrently. Since the declaration of a coroutine funciton is wrapped by macro cr_func_def, there is no need to provide the context as argument of macros that contorl the coroutine, such as cr_begin, cr_end, cr_wait etc. That argument was hardcoded as __ct in the body of those macros. To pass arguments to a coroutine, one can provide a pointer to that argument as parameter of cr_context_init macro, and to extract them in the coroutine, two macros, cr_arg and cr_arg_member, were introduced. Macro cr_arg will cast __ct->arg to the pointer of corresponding type, while cr_arg_member will return a pointer to the specific member of given structure type that __ct->arg points to. Finally, to define a static variable with in the coroutine, one can define them with cr_local macro, which helps to hightlight wheather a variable is a part of that coroutine or just for temporary usage. With the changes made in this version, compiler will raise errors for one of the following situations:

• Declaring coroutines as several pairs of cr_begin and cr_end with in a loop.
• The declaration of function of a coroutine or its corresponding context was missed.

Add more operation analysis, combine with deletes and inserts variables. And Using the preprocessor to decide the analysis being set or not.

For example:

retry     : 187
contains  : 0
traversal : 21028166
fail      : 0
del       : 0
ins       : 0
load      : 63167962
store     : 4096
deletes   : 4098
inserts   : 4098
"retry"    is the number of retries in the __list_find function.
"contains" is the number of wait-free contains in the __list_find function that curr pointer pointed.
"traversal"is the number of list element traversal in the __list_find function.
"fail"     is the number of CAS() failures.
"del"      is the number of list_delete operation failed and restart again.
"ins"      is the number of list_insert operation failed and restart again.
"deletes"  is the number of linked list elements deleted.
"inserts"  is the number of linked list elements created.
"load"     is the number of atomic_load operation in list_delete, list_insert and __list_find.
"store"    is the number of atomic_store operation in list_delete, list_insert and __list_find.

The following are the new variables to record the operations: rtry is the number of retries in the __list_find function. cons is the number of wait-free contains in the __list_find function that curr pointer pointed. trav is the number of list element traversal in the __list_find function. fail is the number of CAS() failures. del is the number of list_delete operation failed and restart again. ins is the number of list_insert operation failed and restart again.

In hp_list project's function : list_hp_retire, it attempt to reorganize retire list while the object is deleting. However, as I see, the origin code doesn't adjust the index simultaneously, which will skip track of the object origin from &rl->list[iret + 1]. I'm not sure whether the behavior was originally intended or not.

The value N is power of 2 integer which is declared in :

#define N (1 << 12) /* node size */
#define NBITS (N - 1)

N will become 1 0000 0000 0000 in binary. When the divisor N is power of 2, the operator % is equal to logical AND with N - 1 which means that i mod 2^n with bitwise AND is ( i & N - 1 ) not ( i & N ).

For example: 3 % 4 == 3 == 0011 % 0100 == 0011 & ( 0100 - 1 )

The ringbuf_shm link in README.md is not working since it's linked to an inexistent ringbuf_shm folder. Renaming ringbuf-shm folder to ringbuf_shm fixes the problem.

The node on the linked list should follow the ordering by its key. However, the function list_insert doesn't actually do this because of the wrong implementation of __list_find.

There are three main fixes in this patch. First, once we should do synchronization, we have to iterate the list again but not return from the function. Second, the while loop should iterate until the last node but not the second last one. Finally, under the normal situation that the tail node with key UINTPTR_MAX should not be deleted (unless the end of the program), some codes are never executed which can be removed.

Here's a macro solution to avoid unexpected output by the buffered I/O printf. It could have some limitations and need improvement, but it achieves the purpose of output in text lines as we may want.

rcu.h:

• Fix the parameter type of smp_store_release(). The parameter that wants to store should be a pointer type.
• Fix the type of tid in rcu_node.
• Rename all the internal parameters in Linux kernel style API to make it more prettier.

main.c:

• Fix the barrier counter that doesn't initialize after exit.

No function change.

The array of the grace period will have the number update run + 1 of the index. So the bound of the grace period is the number of update runs, not update run + 1.

I'm not sure why the actual size is calculated by ALIGN_FLOOR.

Since the constraint of count is that it must be the power of 2, so it is valid to be like 2 or 4. However, in these cases, ALIGN_FLOOR won't allocate any size for *ring[] in ringbuf_t when CACHE_LINE_SIZE == 64. It makes the overflow access of memory which can be detected by valgrind or ASAN. So I think ALIGN_CEIL should be the correct one in general? Do I miss some reason for using ALIGN_FLOOR?