## 4 Implementation
### Example of API Use of RCU-Style Synchronizations  
Figure 4 demonstrates API examples of RW-lock and RCU-style synchronizations applied to a singly linked list node deletion. RW-lock and RCU update employ the coarse-grained locking approach, while RLU and MV-RLU use hand-over-hand locking, one of the fine-grained locking policies, according to the synchronization method's design approach [9]. Hand-over-hand locking is a mechanism that allows several threads to access data structures in a secure manner [9]. It is a procedure for acquiring locks on a target node and the prior node together, conducting operations, and then releasing the locks. write threads, prevents interruptions in critical sections, hence avoiding overhead caused by context switching. Additionally, the non-blocking rcu_call() is used to wait for the read completion (grace period) before releasing the memory associated with the logically deleted object. By employing the non-blocking method rcu_call(), performance improvements in node deletion can be expected when compared to the blocking method rcu_synchronize(). The EBR method is used to determine whether the read of logically deleted nodes has been completed in order to free up memory. EBR is an epoch-based memory reclamation policy that divides an entire thread execution into epochs and collects nodes that should release memory during each epoch [19; 56]. After a certain number of epochs (the number is usually 2 in the optimized implementation), nodes collected by each epoch are assured to have no more reading threads. Nodes that no longer have any reading threads are safely released. The user-level RCU implementation makes use of the recently introduced Citrus RCU implementation, which improves performance by avoiding overhead such as memory barriers [26]. This implementation identifies nodes that needs to be freed in a manner similar to EBR by synchronizing between threads. Each read thread notifies the entering and exiting of the critical section through manipulating variables and flags. rcu_synchronize() can be implemented without coordination between threads by using thread internal variables and flags [26]. The major difference from the kernel-level implementation is the use of the blocking method rcu_synchronize(). This results in a significant degradation in workloads with writes. **RLU implementation:** We use the open-source library of RLU [57] for user and kernel-level benchmarks. When porting RLU to sv6 variant, the primary consideration is memory allocation for logs per thread and nodes for the linked lists and the chained hash tables. At the user level, the logs and the nodes are allocated using the POSIX-compliant malloc() and free() functions of sv6 variant. In the case of kernel level, kmalloc() and kfree() are used to allocate the logs for each thread and the nodes for the shared data structures. However, because kfree() requires the size of the memory to be released due to the interface of sv6 variant, it is necessary to fix the metadata for each log to keep the size of the allocated memory. **MV-RLU implementation:** We use MV-RLU's open-source library [58] for user and kernel-level benchmarks. Some insufficient libraries and system call implementations are required to port the MV-RLU library to the user level of sv6 variant, as follows. MV-RLU runs the garbage collector periodically to help recycle each thread's log. The garbage collector waits in a sleep state for a certain period, using condition variables to operate periodically. However, because the condition variable is not supported in the sv6 variant pthread library, we implemented it using the futex (fast user level mutex) system call and open-source code [59]. The log allocation of MV-RLU uses the same interface as RLU, and the following implementation is additionally required. Additionally, as a performance issue, we implemented a simple memory allocator for assigning the log for each thread while porting the MV-RLU library to the kernel level of sv6 variant.