# HG changeset patch
# Parent c45cce86b944403632c81b0f3b98b0db33658e28

diff -r c45cce86b944 xen/arch/x86/cpu/mcheck/mctelem.c
--- a/xen/arch/x86/cpu/mcheck/mctelem.c	Mon Jan 20 10:27:49 2014 +0000
+++ b/xen/arch/x86/cpu/mcheck/mctelem.c	Tue Jan 21 05:50:40 2014 -0500
@@ -69,6 +69,11 @@
 #define	MC_URGENT_NENT		10
 #define	MC_NONURGENT_NENT	20
 
+/* Check if we can fit enough bits in the free bit array */
+#if MC_URGENT_NENT + MC_NONURGENT_NENT > BITS_PER_LONG
+#error Too much elements
+#endif
+
 #define	MC_NCLASSES		(MC_NONURGENT + 1)
 
 #define	COOKIE2MCTE(c)		((struct mctelem_ent *)(c))
@@ -77,11 +82,9 @@
 static struct mc_telem_ctl {
 	/* Linked lists that thread the array members together.
 	 *
-	 * The free lists are singly-linked via mcte_next, and we allocate
-	 * from them by atomically unlinking an element from the head.
-	 * Consumed entries are returned to the head of the free list.
-	 * When an entry is reserved off the free list it is not linked
-	 * on any list until it is committed or dismissed.
+	 * The free lists is a bit array where bit 1 means free.
+	 * This as element number is quite small and is easy to
+	 * atomically allocate that way.
 	 *
 	 * The committed list grows at the head and we do not maintain a
 	 * tail pointer; insertions are performed atomically.  The head
@@ -101,7 +104,7 @@
 	 * we can lock it for updates.  The head of the processing list
 	 * always has the oldest telemetry, and we append (as above)
 	 * at the tail of the processing list. */
-	struct mctelem_ent *mctc_free[MC_NCLASSES];
+	unsigned long mctc_free[MC_NCLASSES];
 	struct mctelem_ent *mctc_committed[MC_NCLASSES];
 	struct mctelem_ent *mctc_processing_head[MC_NCLASSES];
 	struct mctelem_ent *mctc_processing_tail[MC_NCLASSES];
@@ -214,7 +217,10 @@
 	BUG_ON(MCTE_STATE(tep) != MCTE_F_STATE_FREE);
 
 	tep->mcte_prev = NULL;
-	mctelem_xchg_head(&mctctl.mctc_free[target], &tep->mcte_next, tep);
+	tep->mcte_next = NULL;
+
+	/* set free in array */
+	set_bit(tep - mctctl.mctc_elems, &mctctl.mctc_free[target]);
 }
 
 /* Increment the reference count of an entry that is not linked on to
@@ -284,7 +290,7 @@
 	}
 
 	for (i = 0; i < MC_URGENT_NENT + MC_NONURGENT_NENT; i++) {
-		struct mctelem_ent *tep, **tepp;
+		struct mctelem_ent *tep;
 
 		tep = mctctl.mctc_elems + i;
 		tep->mcte_flags = MCTE_F_STATE_FREE;
@@ -292,16 +298,15 @@
 		tep->mcte_data = datarr + i * datasz;
 
 		if (i < MC_URGENT_NENT) {
-			tepp = &mctctl.mctc_free[MC_URGENT];
-			tep->mcte_flags |= MCTE_F_HOME_URGENT;
+			__set_bit(i, &mctctl.mctc_free[MC_URGENT]);
+			tep->mcte_flags = MCTE_F_HOME_URGENT;
 		} else {
-			tepp = &mctctl.mctc_free[MC_NONURGENT];
-			tep->mcte_flags |= MCTE_F_HOME_NONURGENT;
+			__set_bit(i, &mctctl.mctc_free[MC_NONURGENT]);
+			tep->mcte_flags = MCTE_F_HOME_NONURGENT;
 		}
 
-		tep->mcte_next = *tepp;
+		tep->mcte_next = NULL;
 		tep->mcte_prev = NULL;
-		*tepp = tep;
 	}
 }
 
@@ -310,18 +315,21 @@
 
 /* Reserve a telemetry entry, or return NULL if none available.
  * If we return an entry then the caller must subsequently call exactly one of
- * mctelem_unreserve or mctelem_commit for that entry.
+ * mctelem_dismiss or mctelem_commit for that entry.
  */
 mctelem_cookie_t mctelem_reserve(mctelem_class_t which)
 {
-	struct mctelem_ent **freelp;
-	struct mctelem_ent *oldhead, *newhead;
+	unsigned long *freelp;
+	unsigned long oldfree;
+	unsigned bit;
 	mctelem_class_t target = (which == MC_URGENT) ?
 	    MC_URGENT : MC_NONURGENT;
 
 	freelp = &mctctl.mctc_free[target];
 	for (;;) {
-		if ((oldhead = *freelp) == NULL) {
+		oldfree = *freelp;
+
+		if (oldfree == 0) {
 			if (which == MC_URGENT && target == MC_URGENT) {
 				/* raid the non-urgent freelist */
 				target = MC_NONURGENT;
@@ -333,9 +341,11 @@
 			}
 		}
 
-		newhead = oldhead->mcte_next;
-		if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
-			struct mctelem_ent *tep = oldhead;
+		/* try to allocate, atomically clear free bit */
+		bit = find_first_set_bit(oldfree);
+		if (test_and_clear_bit(bit, freelp)) {
+			/* return element we got */
+			struct mctelem_ent *tep = mctctl.mctc_elems + bit;
 
 			mctelem_hold(tep);
 			MCTE_TRANSITION_STATE(tep, FREE, UNCOMMITTED);
@@ -345,6 +355,7 @@
 				MCTE_SET_CLASS(tep, URGENT);
 			else
 				MCTE_SET_CLASS(tep, NONURGENT);
+
 			return MCTE2COOKIE(tep);
 		}
 	}