# 2022q1 Homework5 (quiz5)
contributed by <`yaohwang99`>
> [Problem link](https://hackmd.io/@sysprog/linux2022-quiz5)

## Problem 2
A successful call to pthread_create() stores the ID of the new thread in the buffer pointed to by `readers + i`, return `0` and starts execution by invoking `reader_thread`

int main()
{
    pthread_t readers[N_READERS], writers[N_WRITERS];
    init();
    /* Start threads */
    for (size_t i = 0; i < ARRAY_SIZE(readers); ++i) {
        if (pthread_create(readers + i, NULL, reader_thread, NULL))
            warn("pthread_create");
    }
    ...

    /* Wait for threads to finish */
    for (size_t i = 0; i < ARRAY_SIZE(readers); ++i) {
        if (pthread_join(readers[i], NULL))
            warn("pthread_join");
    }
    ...
    deinit();

    return EXIT_SUCCESS;
}

Both ==EXP3 and EXP4 is `list_remove(&dom->retired, ptr)`== because the function `cleanup` iterates through the list and deallocate if `ptr` is in the `retired` list and not in `pointers` list.

void cleanup(domain_t *dom, int flags) {
  hp_t *node;

  LIST_ITER(&dom->retired, node) {
    uintptr_t ptr = node->ptr;
    if (!ptr)
      continue;

    if (!list_contains(&dom->pointers, ptr)) {
      /* We can deallocate straight away */
      if (list_remove(&dom->retired, ptr))
        dom->deallocator((void *)ptr);
    } else if (!(flags & DEFER_DEALLOC)) {
      /* Spin until all readers are done, then deallocate */
      while (list_contains(&dom->pointers, ptr))
        ;
      if (list_remove(&dom->retired, ptr))
        dom->deallocator((void *)ptr);
    }
  }
}

### Multiple writer
With the following configuration and [ThreadSanitizer](https://clang.llvm.org/docs/ThreadSanitizer.html), several error will occur.

#define N_READERS 1
#define N_WRITERS 2
#define N_ITERS 200

:::spoiler Thread Sanitizer error output

==================
SUMMARY: ThreadSanitizer: data race (/home/yao/linux2022/hazard_pointer/hazard_pointer+0x4237f8) in free
==================
==================
WARNING: ThreadSanitizer: data race (pid=24104)
...

SUMMARY: ThreadSanitizer: data race /home/yao/linux2022/hazard_pointer/hazard_pointer.c:246:59 in print_config
==================

:::

That is because we didn't mark the data as hazard when writing.
`shared_confing` may be written before or after line 10 and cause data race.

static void *writer_thread(void *arg) {
    (void)arg;
    for (int i = 0; i < N_ITERS / 2; ++i) {
        config_t *new_config = create_config();
        new_config->v1 = rand();
        new_config->v2 = rand();
        new_config->v3 = rand();
        print_config("updating config", new_config);

        swap(config_dom, (uintptr_t *) &shared_config, (uintptr_t) new_config,
             0);
        print_config("updated config ", new_config);
    }
  return NULL;
}

Improve:
Just like in `read_thread()`, use `load` to mark the data as hazard and drop when we no longer need the data.
Note that in line 22, the flag is set as `DEFER_DEALLOC` because deadlock will occur if `cleanup_ptr` spins until data is unused.

static void *writer_thread(void *arg) {
  (void)arg;

  for (int i = 0; i < N_ITERS / 2; ++i) {
    config_t *safe_config =
        (config_t *)load(config_dom, (uintptr_t *)&shared_config);
    if (!safe_config)
      err(EXIT_FAILURE, "load");
    config_t *new_config = create_config();
    new_config->v1 = rand();
    new_config->v2 = rand();
    new_config->v3 = rand();
    print_config("updating config", new_config);
    do {
      safe_config = (config_t *)load(config_dom, (uintptr_t *)&shared_config);
      config_t *old_config = safe_config;
      if (atomic_cas(&shared_config, &safe_config, &new_config))
        break;
      drop(config_dom, (uintptr_t)old_config);
    } while (1);
    print_config("updated config ", new_config);
    cleanup_ptr(config_dom, safe_config, DEFER_DEALLOC);
  }
  return NULL;
}

### Compare Hazard Pointer and RCU
Hazard Pointer:
1. Hazard pointer list: Store the pointer that the thread is referencing, meaning that the pointer is marked as "hazard".
2. Retire list: Store the pointer that has been request to free.
3. Scan through retire list and free those not in the hazard pointer list.

RCU synchronizer:
1. Single writer, multiple reader.
2. Mark the critical section by `rcu_read_lock()` and `rcu_read_unlock`.
3. Block the writer with `synchronize_rcu()` when other reader is in critical section.

I believe that Linux uses RCU because hazard pointer is implemented by different data structure for different types of data. Whereas RCU is implemented the same way, so it is easier to write the code to fit every scenario.