====== Read Copy Update ======

===== Task assignment =====

Imagine that you are developing a multi-threaded application which proceeds concurrently many read and write requests on a shared data structure. Your goal is to speed up the application and achieve processing of 50k write operations per second and as much read operations as possible.

Steps:
  - Download a naive implementation with mutexes from git repository: <code>git clone https://gitlab.fel.cvut.cz/matejjoe/list_mutex.git</code>
  - Compile the program (simply run ''make'' in list_mutex directory)
  - Run the program (''./list_mutex <number or reader threads>'') and see how slow the program is
    * The program creates one write thread and specified number of reader threads and prints achieved read and write operations per second
    * Since a priority of the mutex cannot be set, it may happen that writes or reads are not performed at all
  - Replace the mutexes with rwlocks and measure improvement
    * Use lock priority, to guarantee that given amount of writes will be performed
  - Replace list with liburcu (userspace RCU library) list and measure improvement
    * See hints below
  - For rwlocks and librcu, measure reads with various number of reader threads and plot the results into a graph (for example from one to twenty readers) – use **sufficient hardware** (at least 8 cores -- total number of threads shouldn't be larger than physical cores) – you can use some of remote servers such as ritchie.ciirc.cvut.cz (CTU login with KOS password). It is sufficient to measure just average values from let say 10 iterations.
  - Commit the graph and code changes **to your tutor** (then into upload system). The graph should look roughly like this:
  {{ :courses:b4m36esw:labs:rcu.svg.png?400 | sample graph}}
==== pthread rwlocks ====
The rwlock is part of pthread library. You could be interested in:
  * [[https://linux.die.net/man/3/pthread_rwlock_init|pthread_rwlock_init()]]
  * [[https://linux.die.net/man/3/pthread_rwlock_wrlock|pthread_rwlock_wrlock()]]
  * [[https://linux.die.net/man/3/pthread_rwlock_rdlock|pthread_rwlock_rdlock()]]
  * [[https://linux.die.net/man/3/pthread_rwlock_unlock|pthread_rwlock_unlock()]]
  * [[https://linux.die.net/man/3/pthread_rwlockattr_init|pthread_rwlockattr_init()]]
  * [[http://man7.org/linux/man-pages/man3/pthread_rwlockattr_setkind_np.3.html|pthread_rwlockattr_setkind_np()]] – reader/writer priority – use PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP and don't forget to init atribute before (pthread_rwlockattr_init)

This part should be quite straightforward. In short, replace all pthread_mutex_lock/unlock, and update initialization. Variables (also structures) in C created on the stack (e.g. local variables) are initialized by random values, therefore, make sure that you initialize any created structure before use.
==== Userspace RCU ====
The liburcu should work on Linux, Cygwin and MacOS X. You can obtain [[http://liburcu.org|liburcu]] from distribution repository or compile yourself. I would recommend you compiling the library because libraries in repositories are usually a bit old. In order to compile and use library do following:
  * Download and compile library
    * <code>wget --no-check-certificate http://www.lttng.org/files/urcu/userspace-rcu-latest-0.10.tar.bz2</code>
    * <code>tar -xjf userspace-rcu-latest-0.10.tar.bz2</code>
    * <code>cd userspace-rcu-0.10.2/</code>
    * <code>./configure --prefix=/home/me/somefolder/mybuild/output/target</code> replace the prefix by something meaningful on your system -- this is a place where you will install the library and link with the application afterwards
    * <code>make -j8</code>
    * <code>make install</code>
  * In ./doc/examples/list/ are useful examples
  * Add library into Makefile
    * add ''-lurcu'' or other rcu flavour into ''$LIBS'' (before ''-lpthread'')
    * add path to include directory ''-I/home/me/somefolder/mybuild/output/target/include'' into ''$INCLUDES''
    * add path to library directory ''-L/home/me/somefolder/mybuild/output/target/lib'' into ''$LFLAGS''

Which steps should I do?
  - Get liburcu library
  - Read [[https://liburcu.org/#quick-start-guide|quick start guide]]
  - Look into examples folder (doc/examples/list/) to see how can you use the library
  - Chose user-space rcu flavor ([[https://lwn.net/Articles/573424/#URCU%20Flavors|check table with requirements]] and [[https://liburcu.org/#quick-start-guide|quick start guide]])
  - Integrate it into the application (you can do it directly in main or in list implementation -- I recommend you the latter)
    - Update esw_node structure -- add two elements (struct cds_list_head and struct rcu_head required by rcu implementation)
    - Replace declaration of list (use CDS_LIST_HEAD macro)
    - Implement required functions (take inspiration from examples) -- you don't have to implement not used operations
    - Don't forget to put requred library calls -- depending on selected flavour, you have to insert some of these: rcu_read_(un)lock, synchronize_rcu, rcu_(un)register_thread, rcu_quiescent_state, (sys_membarrier)
  - Measure speed-up
==== Supplementary materials ====

[[http://www.compsci.hunter.cuny.edu/~sweiss/course_materials/unix_lecture_notes/chapter_10.pdf|Article about threads and various types of locks]]

[[https://lwn.net/Articles/573424/|Article about Userspace RCU library]]

[[http://www.efficios.com/pub/rcu/urcu-main.pdf|User-Level Implementations of Read-Copy Update]]