From 4cd598105d4f196946bb15068ec4be2dc6c691bc Mon Sep 17 00:00:00 2001
From: Brian Norris <banorris@uci.edu>
Date: Fri, 8 Mar 2013 15:36:20 -0800
Subject: [PATCH 1/1] ms-queue: fixup initialization and free lists

There are a few things we fix:

1) We shouldn't initialize node[0].next, since node[0] is the 'NULL'
pointer and should never be accessed.

2) The per-thread free list is too restrictive. Now, we generate a list
of free nodes for each thread that can contain up to 4 node indexes.
We only initialize this list with 2 nodes each (so each thread can
expand its free list, if needed). There is some minimal assertion
framework and race detection performed on these lists, just in case.

3) We only initialize those nodes that are placed in the free list.
Accesses to other nodes' 'next' pointer should trigger an uninitialized
loads assertion.
---
 ms-queue/my_queue.c | 77 +++++++++++++++++++++++++++++----------------
 1 file changed, 50 insertions(+), 27 deletions(-)

diff --git a/ms-queue/my_queue.c b/ms-queue/my_queue.c
index 8a74060..492c862 100644
--- a/ms-queue/my_queue.c
+++ b/ms-queue/my_queue.c
@@ -1,6 +1,7 @@
 #include <threads.h>
 #include <stdlib.h>
 #include "librace.h"
+#include "model-assert.h"
 
 #include "my_queue.h"
 
@@ -8,46 +9,68 @@
 #define release memory_order_release
 #define acquire memory_order_acquire
 
-static unsigned int *node_nums;
+#define MAX_FREELIST 4 /* Each thread can own up to MAX_FREELIST free nodes */
+#define INITIAL_FREE 2 /* Each thread starts with INITIAL_FREE free nodes */
 
+static unsigned int (*free_lists)[MAX_FREELIST];
+
+/* Search this thread's free list for a "new" node */
 static unsigned int new_node()
 {
-	return node_nums[get_thread_num()];
+	int i;
+	int t = get_thread_num();
+	for (i = 0; i < MAX_FREELIST; i++) {
+		unsigned int node = load_32(&free_lists[t][i]);
+		if (node) {
+			store_32(&free_lists[t][i], 0);
+			return node;
+		}
+	}
+	/* free_list is empty? */
+	MODEL_ASSERT(0);
+	return 0;
 }
 
+/* Place this node index back on this thread's free list */
 static void reclaim(unsigned int node)
 {
-	node_nums[get_thread_num()] = node;
+	int i;
+	int t = get_thread_num();
+
+	/* Don't reclaim NULL node */
+	MODEL_ASSERT(node);
+
+	for (i = 0; i < MAX_FREELIST; i++) {
+		/* Should never race with our own thread here */
+		unsigned int idx = load_32(&free_lists[t][i]);
+
+		/* Found empty spot in free list */
+		if (idx == 0) {
+			store_32(&free_lists[t][i], node);
+			return;
+		}
+	}
+	/* free list is full? */
+	MODEL_ASSERT(0);
 }
 
 void init_queue(queue_t *q, int num_threads)
 {
-	unsigned int i;
-	pointer head;
-	pointer tail;
-	pointer next;
-
-	node_nums = malloc(num_threads * sizeof(*node_nums));
-	for (i = 0; i < num_threads; i++)
-		node_nums[i] = 2 + i;
-
-	/* initialize queue */
-	head = MAKE_POINTER(1, 0);
-	tail = MAKE_POINTER(1, 0);
-	next = MAKE_POINTER(0, 0); // (NULL, 0)
-
-	atomic_init(&q->head, head);
-	atomic_init(&q->tail, tail);
-	atomic_init(&q->nodes[1].next, next);
-
-	/* initialize avail list */
-	for (i = 2; i < MAX_NODES; i++) {
-		next = MAKE_POINTER(i + 1, 0);
-		atomic_init(&q->nodes[i].next, next);
+	int i, j;
+
+	/* Initialize each thread's free list with INITIAL_FREE NULL "pointers" */
+	free_lists = malloc(num_threads * sizeof(*free_lists));
+	for (i = 0; i < num_threads; i++) {
+		for (j = 0; j < INITIAL_FREE; j++) {
+			free_lists[i][j] = 2 + i * MAX_FREELIST + j;
+			atomic_init(&q->nodes[free_lists[i][j]].next, MAKE_POINTER(0, 0));
+		}
 	}
 
-	next = MAKE_POINTER(0, 0); // (NULL, 0)
-	atomic_init(&q->nodes[MAX_NODES].next, next);
+	/* initialize queue */
+	atomic_init(&q->head, MAKE_POINTER(1, 0));
+	atomic_init(&q->tail, MAKE_POINTER(1, 0));
+	atomic_init(&q->nodes[1].next, MAKE_POINTER(0, 0));
 }
 
 void enqueue(queue_t *q, unsigned int val)
-- 
2.34.1