X-Git-Url: http://wien.tomnetworks.com/gitweb/?a=blobdiff_plain;f=mono%2Futils%2Fmono-linked-list-set.h;h=bb25cb1c18e83055981fb35d944af508d2705e91;hb=HEAD;hp=0abcee98f15730a8d73b7a2f4dec99dc81409b06;hpb=66e33aa2ee25b9de6ff80e41aa7036b9a8352479;p=mono.git

diff --git a/mono/utils/mono-linked-list-set.h b/mono/utils/mono-linked-list-set.h
index 0abcee98f15..bb25cb1c18e 100644
--- a/mono/utils/mono-linked-list-set.h
+++ b/mono/utils/mono-linked-list-set.h
@@ -1,5 +1,6 @@
-/*
- * mono-linked-list-set.h: A lock-free split ordered list.
+/**
+ * \file
+ * A lock-free split ordered list.
  *
  * Author:
  *	Rodrigo Kumpera (kumpera@gmail.com)
@@ -44,78 +45,130 @@ Those are low level operations. prev, cur, next are returned in the hazard point
 You must manually clean the hazard pointer table after using them.
 */
 
-void
+MONO_API void
 mono_lls_init (MonoLinkedListSet *list, void (*free_node_func)(void *));
 
-gboolean
+MONO_API gboolean
 mono_lls_find (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, uintptr_t key);
 
-gboolean
+MONO_API gboolean
 mono_lls_insert (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value);
 
-gboolean
+MONO_API gboolean
 mono_lls_remove (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLinkedListSetNode *value);
 
-gpointer
-get_hazardous_pointer_with_mask (gpointer volatile *pp, MonoThreadHazardPointers *hp, int hazard_index);
-
-/*
-Requires the world to be stoped
-*/
-#define MONO_LLS_FOREACH(list, element, type) {\
-	MonoLinkedListSetNode *__cur;	\
-	for (__cur = (list)->head; __cur; __cur = mono_lls_pointer_unmask (__cur->next)) \
-		if (!mono_lls_pointer_get_mark (__cur->next)) {	\
-			(element) = (type)__cur;
-
+MONO_API gpointer
+mono_lls_get_hazardous_pointer_with_mask (gpointer volatile *pp, MonoThreadHazardPointers *hp, int hazard_index);
 
-#define MONO_LLS_FOREACH_FILTERED(list, element, filter_func, type) {\
-	MonoLinkedListSetNode *__cur;	\
-	for (__cur = (list)->head; __cur; __cur = (MonoLinkedListSetNode *)mono_lls_pointer_unmask (__cur->next)) \
-		if (!mono_lls_pointer_get_mark (__cur->next)) {	\
-			(element) = (type)__cur;			\
-			if (!filter_func (element)) continue;
-
-#define MONO_LLS_END_FOREACH }}
-
-static inline MonoLinkedListSetNode*
-mono_lls_info_step (MonoLinkedListSetNode *val, MonoThreadHazardPointers *hp)
+static inline gboolean
+mono_lls_filter_accept_all (gpointer elem)
 {
-	val = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (val);
-	mono_hazard_pointer_set (hp, 1, val);
-	return val;
+	return TRUE;
 }
 
 /*
-Provides snapshot iteration
-*/
-#define MONO_LLS_FOREACH_SAFE(list, element, type) {\
-	MonoThreadHazardPointers *__hp = mono_hazard_pointer_get ();	\
-	MonoLinkedListSetNode *__cur, *__next;	\
-	for (__cur = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (get_hazardous_pointer ((gpointer volatile*)&(list)->head, __hp, 1)); \
-		__cur;	\
-		__cur = (MonoLinkedListSetNode *) mono_lls_info_step (__next, __hp)) {	\
-		__next = (MonoLinkedListSetNode *) get_hazardous_pointer_with_mask ((gpointer volatile*)&__cur->next, __hp, 0);	\
-		if (!mono_lls_pointer_get_mark (__next)) {	\
-			(element) = (type)__cur;
-
-#define MONO_LLS_FOREACH_FILTERED_SAFE(list, element, filter_func, type) {\
-	MonoThreadHazardPointers *__hp = mono_hazard_pointer_get ();	\
-	MonoLinkedListSetNode *__cur, *__next;	\
-	for (__cur = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (get_hazardous_pointer ((gpointer volatile*)&(list)->head, __hp, 1)); \
-		__cur;	\
-		__cur = (MonoLinkedListSetNode *) mono_lls_info_step (__next, __hp)) {	\
-		__next = (MonoLinkedListSetNode *) get_hazardous_pointer_with_mask ((gpointer volatile*)&__cur->next, __hp, 0);	\
-		if (!mono_lls_pointer_get_mark (__next)) {	\
-			(element) = (type)__cur;	\
-			if (!filter_func (element)) continue;
-
-
-#define MONO_LLS_END_FOREACH_SAFE \
+ * These macros assume that no other threads are actively modifying the list.
+ */
+
+#define MONO_LLS_FOREACH_FILTERED(list, type, elem, filter) \
+	do { \
+		MonoLinkedListSet *list__ = (list); \
+		for (MonoLinkedListSetNode *cur__ = list__->head; cur__; cur__ = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (cur__->next)) { \
+			if (!mono_lls_pointer_get_mark (cur__->next)) { \
+				type *elem = (type *) cur__; \
+				if (filter (elem)) {
+
+#define MONO_LLS_FOREACH_END \
+				} \
+			} \
 		} \
-	}	\
-	mono_hazard_pointer_clear (__hp, 0); \
-	mono_hazard_pointer_clear (__hp, 1); \
-}
+	} while (0);
+
+#define MONO_LLS_FOREACH(list, type, elem) \
+	MONO_LLS_FOREACH_FILTERED ((list), type, elem, mono_lls_filter_accept_all)
+
+/*
+ * These macros can be used while other threads are potentially modifying the
+ * list, but they only provide a snapshot of the list as a result.
+ *
+ * NOTE: Do NOT break out of the loop through any other means than a break
+ * statement, as other ways of breaking the loop will skip past important
+ * cleanup work.
+ */
+
+#define MONO_LLS_FOREACH_FILTERED_SAFE(list, type, elem, filter) \
+	do { \
+		/* NOTE: Keep this macro's code in sync with the mono_lls_find () logic. */ \
+		MonoLinkedListSet *list__ = (list); \
+		MonoThreadHazardPointers *hp__ = mono_hazard_pointer_get (); \
+		gboolean progress__ = FALSE; \
+		uintptr_t hkey__; \
+		gboolean restart__; \
+		do { \
+			restart__ = FALSE; \
+			MonoLinkedListSetNode **prev__ = &list__->head; \
+			mono_hazard_pointer_set (hp__, 2, prev__); \
+			MonoLinkedListSetNode *cur__ = (MonoLinkedListSetNode *) mono_lls_get_hazardous_pointer_with_mask ((gpointer *) prev__, hp__, 1); \
+			while (1) { \
+				if (!cur__) { \
+					break; \
+				} \
+				MonoLinkedListSetNode *next__ = (MonoLinkedListSetNode *) mono_lls_get_hazardous_pointer_with_mask ((gpointer *) &cur__->next, hp__, 0); \
+				uintptr_t ckey__ = cur__->key; \
+				mono_memory_read_barrier (); \
+				if (*prev__ != cur__) { \
+					restart__ = TRUE; \
+					break; \
+				} \
+				if (!mono_lls_pointer_get_mark (next__)) { \
+					if (!progress__ || ckey__ > hkey__) { \
+						progress__ = TRUE; \
+						hkey__ = ckey__; \
+						type *elem = (type *) cur__; \
+						if (filter (elem)) { \
+							gboolean broke__ = TRUE; \
+							gboolean done__ = FALSE; \
+							do { \
+								if (done__) { \
+									broke__ = FALSE; \
+									break; \
+								} \
+								done__ = TRUE;
+
+#define MONO_LLS_FOREACH_SAFE_END \
+								broke__ = FALSE; \
+								break; \
+							} while (1); \
+							if (broke__) { \
+								break; \
+							} \
+						} \
+					} \
+					prev__ = &cur__->next; \
+					mono_hazard_pointer_set (hp__, 2, cur__); \
+				} else { \
+					next__ = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (next__); \
+					if (InterlockedCompareExchangePointer ((volatile gpointer *) prev__, next__, cur__) == cur__) { \
+						mono_memory_write_barrier (); \
+						mono_hazard_pointer_clear (hp__, 1); \
+						if (list__->free_node_func) { \
+							mono_thread_hazardous_queue_free (cur__, list__->free_node_func); \
+						} \
+					} else { \
+						restart__ = TRUE; \
+						break; \
+					} \
+				} \
+				cur__ = (MonoLinkedListSetNode *) mono_lls_pointer_unmask (next__); \
+				mono_hazard_pointer_set (hp__, 1, cur__); \
+			} \
+		} while (restart__); \
+		mono_hazard_pointer_clear (hp__, 0); \
+		mono_hazard_pointer_clear (hp__, 1); \
+		mono_hazard_pointer_clear (hp__, 2); \
+	} while (0);
+
+#define MONO_LLS_FOREACH_SAFE(list, type, elem) \
+	MONO_LLS_FOREACH_FILTERED_SAFE ((list), type, elem, mono_lls_filter_accept_all)
 
 #endif /* __MONO_SPLIT_ORDERED_LIST_H__ */