2022q1 Homework5 (quiz5)

contributed by <yaohwang99>

Problem link

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, several error will occur.

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

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.