tree_barrier.c

// John M. Mellor-Crummey and Michael L. Scott. 1991. Algorithms for scalable
// synchronization on shared-memory multiprocessors. ACM Trans. Comput. Syst. 9,
// 1 (Feb. 1991), 21–65. DOI:https://doi.org/10.1145/103727.103729

#include <stdlib.h>
#include <assert.h>
#include <errno.h>

typedef int tree_barrierattr_t;

typedef struct tree_barriernode_t {
  volatile bool parent_sense;
  volatile bool *volatile parent_pointer;
  volatile bool *volatile child_pointers[2];
  volatile bool have_child[4];
  volatile bool child_not_ready[4];
  volatile bool sense;
  volatile bool dummy;
} tree_barriernode_t;

typedef struct tree_barrier_t {
  tree_barriernode_t *nodes;
} tree_barrier_t;

const int TREE_BARRIER_SERIAL_THREAD = EINTR;
const tree_barrierattr_t TREE_PROCESS_SHARED = 0;
const tree_barrierattr_t TREE_PROCESS_PRIVATE = 1;

int tree_barrier_init(tree_barrier_t *barrier, const tree_barrierattr_t *attr, unsigned count) {
  if (barrier == NULL) {
    return EINVAL;
  }
  if (count == 0u) {
    return EINVAL;
  }
  if (attr != NULL && *attr != TREE_PROCESS_PRIVATE) {
    assert(false && "Not implemented.");
  }
  barrier->nodes = (tree_barriernode_t *)malloc(count * sizeof(tree_barriernode_t));
  for (int i = 0; i < (int)count; i++) {
    barrier->nodes[i].sense = true;
    barrier->nodes[i].dummy = false;
    barrier->nodes[i].have_child[0] = (4 * i + 1 < (int)count);
    barrier->nodes[i].have_child[1] = (4 * i + 2 < (int)count);
    barrier->nodes[i].have_child[2] = (4 * i + 3 < (int)count);
    barrier->nodes[i].have_child[3] = (4 * i + 4 < (int)count);
    barrier->nodes[i].parent_pointer = (i == 0) ? &barrier->nodes[i].dummy : &barrier->nodes[(i - 1) / 4].child_not_ready[(i - 1) % 4];
    barrier->nodes[i].child_pointers[0] = (2 * i + 1 >= (int)count) ? &barrier->nodes[i].dummy : &barrier->nodes[2 * i + 1].parent_sense;
    barrier->nodes[i].child_pointers[1] = (2 * i + 2 >= (int)count) ? &barrier->nodes[i].dummy : &barrier->nodes[2 * i + 2].parent_sense;
    barrier->nodes[i].child_not_ready[0] = barrier->nodes[i].have_child[0];
    barrier->nodes[i].child_not_ready[1] = barrier->nodes[i].have_child[1];
    barrier->nodes[i].child_not_ready[2] = barrier->nodes[i].have_child[2];
    barrier->nodes[i].child_not_ready[3] = barrier->nodes[i].have_child[3];
    barrier->nodes[i].parent_sense = false;
  }
  return 0;
}

int tree_barrier_destroy(tree_barrier_t *barrier) {
  if (barrier == NULL) {
    return EINVAL;
  }
  free(barrier->nodes);
  return 0;
}

int tree_barrierattr_init(tree_barrierattr_t *attr) {
  if (attr == NULL) {
    return EINVAL;
  }
  return 0;
}

int tree_barrierattr_destroy(tree_barrierattr_t *attr) {
  if (attr == NULL) {
    return EINVAL;
  }
  return 0;
}

int tree_barrierattr_getpshared(const tree_barrierattr_t *attr, int *pshared) {
  if (attr == NULL || pshared == NULL) {
    return EINVAL;
  }
  *pshared = *attr;
  return 0;
}

int tree_barrierattr_setpshared(tree_barrierattr_t *attr, int pshared) {
  if (attr == NULL) {
    return EINVAL;
  }
  if (pshared != TREE_PROCESS_SHARED && pshared != TREE_PROCESS_PRIVATE) {
    return EINVAL;
  }
  if (pshared != TREE_PROCESS_PRIVATE) {
    assert(false && "Not implemented.");
  }
  *attr = pshared;
  return 0;
}

int tree_barrier_wait(tree_barrier_t *barrier, int pid) {
  if (barrier == NULL) {
    return EINVAL;
  }
  while (
    barrier->nodes[pid].child_not_ready[0] ||
    barrier->nodes[pid].child_not_ready[1] ||
    barrier->nodes[pid].child_not_ready[2] ||
    barrier->nodes[pid].child_not_ready[3]
  );
  barrier->nodes[pid].child_not_ready[0] = barrier->nodes[pid].have_child[0];
  barrier->nodes[pid].child_not_ready[1] = barrier->nodes[pid].have_child[1];
  barrier->nodes[pid].child_not_ready[2] = barrier->nodes[pid].have_child[2];
  barrier->nodes[pid].child_not_ready[3] = barrier->nodes[pid].have_child[3];
  *barrier->nodes[pid].parent_pointer = false;
  if (pid != 0) {
    while (barrier->nodes[pid].parent_sense != barrier->nodes[pid].sense);
  }
  *barrier->nodes[pid].child_pointers[0] = barrier->nodes[pid].sense;
  *barrier->nodes[pid].child_pointers[1] = barrier->nodes[pid].sense;
  barrier->nodes[pid].sense = !(barrier->nodes[pid].sense);
  return 0;
}