Merge pull request #2802 from BrzVlad/feature-evacuation-opt2

[mono.git] / mono / utils / lock-free-queue.c

diff --git a/mono/utils/lock-free-queue.c b/mono/utils/lock-free-queue.c
index 0053304e930a6210bd7eeef284fd35ebf635dde0..2e06b63f526258de4e6f2004e3fd397d8f523611 100644 (file)
--- a/mono/utils/lock-free-queue.c
+++ b/mono/utils/lock-free-queue.c
@@ -53,14 +53,17 @@
 
 #include <mono/utils/mono-membar.h>
 #include <mono/utils/hazard-pointer.h>
-#include <mono/io-layer/io-layer.h>
+#include <mono/utils/atomic.h>
 
 #include <mono/utils/lock-free-queue.h>
 
-#define INVALID_NEXT   ((void*)-1)
-#define END_MARKER     ((void*)-2)
-#define FREE_NEXT      ((void*)-3)
+#define INVALID_NEXT   ((MonoLockFreeQueueNode *volatile)-1)
+#define END_MARKER     ((MonoLockFreeQueueNode *volatile)-2)
+#define FREE_NEXT      ((MonoLockFreeQueueNode *volatile)-3)
 
+/*
+ * Initialize a lock-free queue in-place at @q.
+ */
 void
 mono_lock_free_queue_init (MonoLockFreeQueue *q)
 {
@@ -77,17 +80,30 @@ mono_lock_free_queue_init (MonoLockFreeQueue *q)
        q->has_dummy = 1;
 }
 
+/*
+ * Initialize @node's state. If @poison is TRUE, @node may not be enqueued to a
+ * queue - @mono_lock_free_queue_node_unpoison must be called first; otherwise,
+ * the node can be enqueued right away.
+ *
+ * The poisoning feature is mainly intended for ensuring correctness in complex
+ * lock-free code that uses the queue. For example, in some code that reuses
+ * nodes, nodes can be poisoned when they're dequeued, and then unpoisoned and
+ * enqueued in their hazard free callback.
+ */
 void
-mono_lock_free_queue_node_init (MonoLockFreeQueueNode *node, gboolean to_be_freed)
+mono_lock_free_queue_node_init (MonoLockFreeQueueNode *node, gboolean poison)
 {
-       node->next = to_be_freed ? INVALID_NEXT : FREE_NEXT;
+       node->next = poison ? INVALID_NEXT : FREE_NEXT;
 #ifdef QUEUE_DEBUG
        node->in_queue = FALSE;
 #endif
 }
 
+/*
+ * Unpoisons @node so that it may be enqueued.
+ */
 void
-mono_lock_free_queue_node_free (MonoLockFreeQueueNode *node)
+mono_lock_free_queue_node_unpoison (MonoLockFreeQueueNode *node)
 {
        g_assert (node->next == INVALID_NEXT);
 #ifdef QUEUE_DEBUG
@@ -96,6 +112,10 @@ mono_lock_free_queue_node_free (MonoLockFreeQueueNode *node)
        node->next = FREE_NEXT;
 }
 
+/*
+ * Enqueue @node to @q. @node must have been initialized by a prior call to
+ * @mono_lock_free_queue_node_init, and must not be in a poisoned state.
+ */
 void
 mono_lock_free_queue_enqueue (MonoLockFreeQueue *q, MonoLockFreeQueueNode *node)
 {
@@ -113,7 +133,7 @@ mono_lock_free_queue_enqueue (MonoLockFreeQueue *q, MonoLockFreeQueueNode *node)
        for (;;) {
                MonoLockFreeQueueNode *next;
 
-               tail = get_hazardous_pointer ((gpointer volatile*)&q->tail, hp, 0);
+               tail = (MonoLockFreeQueueNode *) get_hazardous_pointer ((gpointer volatile*)&q->tail, hp, 0);
                mono_memory_read_barrier ();
                /*
                 * We never dereference next so we don't need a
@@ -157,8 +177,8 @@ mono_lock_free_queue_enqueue (MonoLockFreeQueue *q, MonoLockFreeQueueNode *node)
 static void
 free_dummy (gpointer _dummy)
 {
-       MonoLockFreeQueueDummy *dummy = _dummy;
-       mono_lock_free_queue_node_free (&dummy->node);
+       MonoLockFreeQueueDummy *dummy = (MonoLockFreeQueueDummy *) _dummy;
+       mono_lock_free_queue_node_unpoison (&dummy->node);
        g_assert (dummy->in_use);
        mono_memory_write_barrier ();
        dummy->in_use = 0;
@@ -183,7 +203,7 @@ get_dummy (MonoLockFreeQueue *q)
 static gboolean
 is_dummy (MonoLockFreeQueue *q, MonoLockFreeQueueNode *n)
 {
-       return n >= &q->dummies [0].node && n < &q->dummies [MONO_LOCK_FREE_QUEUE_NUM_DUMMIES].node;
+       return n >= &q->dummies [0].node && n <= &q->dummies [MONO_LOCK_FREE_QUEUE_NUM_DUMMIES-1].node;
 }
 
 static gboolean
@@ -208,6 +228,11 @@ try_reenqueue_dummy (MonoLockFreeQueue *q)
        return TRUE;
 }
 
+/*
+ * Dequeues a node from @q. Returns NULL if no nodes are available. The returned
+ * node is hazardous and must be freed with @mono_thread_hazardous_try_free or
+ * @mono_thread_hazardous_queue_free - it must not be freed directly.
+ */
 MonoLockFreeQueueNode*
 mono_lock_free_queue_dequeue (MonoLockFreeQueue *q)
 {
@@ -218,7 +243,7 @@ mono_lock_free_queue_dequeue (MonoLockFreeQueue *q)
        for (;;) {
                MonoLockFreeQueueNode *tail, *next;
 
-               head = get_hazardous_pointer ((gpointer volatile*)&q->head, hp, 0);
+               head = (MonoLockFreeQueueNode *) get_hazardous_pointer ((gpointer volatile*)&q->head, hp, 0);
                tail = (MonoLockFreeQueueNode*)q->tail;
                mono_memory_read_barrier ();
                next = head->next;
@@ -286,7 +311,7 @@ mono_lock_free_queue_dequeue (MonoLockFreeQueue *q)
                g_assert (q->has_dummy);
                q->has_dummy = 0;
                mono_memory_write_barrier ();
-               mono_thread_hazardous_free_or_queue (head, free_dummy, FALSE, TRUE);
+               mono_thread_hazardous_try_free (head, free_dummy);
                if (try_reenqueue_dummy (q))
                        goto retry;
                return NULL;