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

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

Imagine that you are developing a multi-threaded application which proceeds concurrently many read and some write requests on a shared data structure. Your goal is to speed up the application so that there is as much read operations as possible while keeping the same amount of write operations.

Steps
  - Download a naive implementation with mutexes from git repository: <code>git clone https://gitlab.fel.cvut.cz/matejjoe/rcu.git</code>
  - Compile the program (simply run ''make'' in rcu directory)
  - Run the program (''./list_mutex <number of reader threads>'') and measure read operations and their scalability
  - Replace the mutexes with rwlocks and measure improvement
  - Replace list with liburcu (userspace RCU library) list and measure improvement
  - You can use provided template with "ifdefs" or write separate solutions with the same functionality as well.
  - 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 our server called Ritchie ''ssh username@ritchie.ciirc.cvut.cz'' (KOS password)
  - Commit the graph and your code into the upload system and notify your tutor (Joel). We will make a short call and evaluate the solution. The graph should look roughly like this:
  {{:courses:b4m36esw:labs:rcu.svg.png?nolink&300|}}
==== 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)

Replacement of mutexes to rwlock should be quite easy. The only "tricky" part is to correctly initialize rwlock. You can find an example at the end of the first article in Supplementary materials section.

==== 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. If you want to use your own machine, I would recommend you to use library from distribution repository (''sudo apt install liburcu-dev'').

First, please read [[http://liburcu.org/#quick-start-guide|quick start guide]]. Examples how to use liburcu are available in doc/examples folder in the source code of the library and also on [[https://github.com/urcu/userspace-rcu/tree/master/doc/examples/list|github]]. Please take a look into for each example and replace example, and try to apply similar changes in the given code. The template assumes that you will use "qsbr flavour", but you can choose another flavour or compare different flavours. To change the flavour, you have to update Makefile (change ''-lurcu-qsbr'' to something else), list.hpp (change ''#include <urcu-qsbr.h>'' to something else), and change required library calls (see quick start guide and examples [[https://github.com/urcu/userspace-rcu/tree/master/doc/examples/urcu-flavors|here]]).

The tricky part of RCU is probably esw_list_update function. In short, you update function should work like that:
  * Find node to be replaced
  * Create new node (independent copy with new values)
  * Link new node into old list
  * Make sure that old node is deleted **when it is safe**
     * You can either wait for it or schedule deletion by using callback function

☺
== Compiling RCU library (only if not available in your repository) ==
In order to compile and use the library do the following:
  * Download and compile the library: <code sh>
wget https://lttng.org/files/urcu/userspace-rcu-latest-0.11.tar.bz2
tar -xjf userspace-rcu-latest-0.11.tar.bz2
cd userspace-rcu-0.11.1/
./configure --prefix=/home/me/somefolder/mybuild/output/target
make -j8
make install</code>
  * In ./doc/examples/list/ are useful examples
  * Add library into Makefile
    * 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 ''$LDFLAGS''

==== Ritchie ====
Since the assignment requires high-performance system with many cores, you can use our server called [[https://en.wikipedia.org/wiki/Dennis_Ritchie|Ritchie]]. The server is accessible over ssh ''ssh username@ritchie.ciirc.cvut.cz'' with KOS password. I can recommend to use ssh keys while connecting, you can generate them by using ''ssh-keygen'' and copy them to server using ''ssh-copy-id''. Then, you should be able to login without typing your password.

☺
== CLion and remote work on ritchie ==
If you like CLion IDE for developing C/C++ programs, you can use our server for so called full remote mode. Follow the instructions [[https://www.jetbrains.com/help/clion/remote-projects-support.html|here]].

==== Remote corona-support ====
If you have general questions, please ask in Microsoft teams in [[https://teams.microsoft.com/l/channel/19%3a808f1178557d4adb828576318ae2700b%40thread.tacv2/Assignment%25204%2520%25E2%2580%2593%2520RCU?groupId=5df990ab-0cb2-4268-acf9-53d5d14b4a78&tenantId=f345c406-5268-43b0-b19f-5862fa6833f8|dedicated channel]]. If you have a specific question related only to your solution, please write me a private message via teams. If you work on ritchie with command line, you can share your session with me by typing ''tmux-share joel''.

==== 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]]