Distributed Life

I recently needed to develop a way to perform pseudo-random memory accesses in a C program, in order to fool the hardware prefetchers. Without going into any details, my solution was to represent some continuous memory as a linked list with random next pointers.

Naturally, the simplest list that can be developed has nodes that do not contain any other elements apart from the next pointers that link the nodes together. In C, this can be easily done with a structure similar to the following:

struct node
{
  struct node* next;
}

However, one can leverage the flexibility of C to even avoid using the node structure: you are allowed to cast some memory to any type you like. For instance, you can use 8 bytes as an integer(uint64_t) , or as a pointer to an integer (uint64_t*).

Doing so, we can develop, what I believe is, the simplest linked list possible.
The code that generates a random list is the following:

static void
create_rand_list(volatile uint64_t* list, size_t n)
{
  srand(time(NULL));
  uint8_t* used = calloc(n, sizeof(uint8_t));
  assert (used != NULL);
 
  size_t idx = 0;
  size_t used_num = 0;
  while (used_num < n - 1)
    {
      used[idx] = 1;
      used_num++;
 
      size_t nxt;
      do
        {
          nxt = rand() % n;
        }
      while (used[nxt]);
 
      list[idx] = (uint64_t) (list + nxt);
      idx = nxt;
    }
 
  list[idx] = 0; 		/* NULL pointer in the last element */
 
  free(used);
}

The “magic” happens when we set list[idx] = (uint64_t) (list + nxt), so we set the “next” pointer for the location idx.
What is even more interesting is how we can now parse and get the size of the list:

static void
list_parse(volatile uint64_t* l)
{
  while (*l != 0)
    {
      l = (uint64_t*) *l;
    }
}
 
static size_t
list_size(volatile uint64_t* l)
{
  size_t s = 1;
  while (*l != 0)
    {
      l = (uint64_t*) *l;
      s++;
    }
  return s;
}

Pretty slick, right? 🙂