CAMLprim value hh_add()

in src/heap/hh_shared.c [1621:1707]

• 51 lines of code
• 9 McCabe index (conditional complexity)

CAMLprim value hh_add(value key, value addr) {
  CAMLparam2(key, addr);
  check_should_exit();

  helt_t elt;
  elt.hash = get_hash(key);
  elt.addr = Long_val(addr);

  size_t hashtbl_slots = info->hashtbl_slots;
  unsigned int slot = elt.hash & (hashtbl_slots - 1);
  unsigned int init_slot = slot;

  while (1) {
    uint64_t slot_hash = hashtbl[slot].hash;

    if (slot_hash == elt.hash) {
      // This value has already been been written to this slot, except that the
      // value may have been deleted. Deleting a slot leaves the hash in place
      // but replaces the addr field with NULL_ADDR. In this case, we can re-use
      // the slot by writing the new address into.
      //
      // Remember that only reads and writes can happen concurrently, so we
      // don't need to worry about concurrent deletes.

      if (hashtbl[slot].addr == NULL_ADDR) {
        // Two threads may be racing to write this value, so try to grab the
        // slot atomically.
        addr_t old_addr = __sync_val_compare_and_swap(
            &hashtbl[slot].addr, NULL_ADDR, elt.addr);

        if (old_addr == NULL_ADDR) {
          __sync_fetch_and_add(&info->hcounter_filled, 1);
        } else {
          // Another thread won the race, but since the slot hashes match, it
          // wrote the value we were trying to write, so our work is done.
          addr = Val_long(old_addr);
        }
      }

      break;
    }

    if (slot_hash == 0) {
      helt_t old;

      // This slot is free, but two threads may be racing to write to this slot,
      // so try to grab the slot atomically. Note that this is a 16-byte CAS
      // writing both the hash and the address at the same time. We expect the
      // slot to contain `0`. If that's the case, `success == true`; otherwise,
      // whatever data was in the slot at the time of the CAS will be stored in
      // `old`.
      old.value = 0;
      _Bool success = __atomic_compare_exchange(
          /* ptr */ &hashtbl[slot].value,
          /* expected */ &old.value,
          /* desired */ &elt.value,
          /* weak */ 0,
          /* success_memorder */ __ATOMIC_SEQ_CST,
          /* failure_memorder */ __ATOMIC_SEQ_CST);

      if (success) {
        // The slot was still empty when we tried to CAS, meaning we
        // successfully grabbed the slot.
        uint64_t size = __sync_fetch_and_add(&info->hcounter, 1);
        __sync_fetch_and_add(&info->hcounter_filled, 1);
        assert(size < hashtbl_slots); // sanity check
        break;
      }

      if (old.hash == elt.hash) {
        // The slot was non-zero, so we failed to grab the slot. However, the
        // thread which won the race wrote the value we were trying to write,
        // meaning out work is done.
        addr = Val_long(old.addr);
        break;
      }
    }

    slot = (slot + 1) & (hashtbl_slots - 1);
    if (slot == init_slot) {
      // We're never going to find a spot
      raise_hash_table_full();
    }
  }

  CAMLreturn(addr);
}