[PATCH] MCE: Fix race condition in mctelem_reserve

[PATCH] MCE: Fix race condition in mctelem_reserve

[Frediano Ziglio]

These lines (in mctelem_reserve)


        newhead = oldhead->mcte_next;
        if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {

are racy. After you read the newhead pointer it can happen that another
flow (thread or recursive invocation) change all the list but set head
with same value. So oldhead is the same as *freelp but you are setting
a new head that could point to whatever element (even already used).

This patch use instead a bit array and atomic bit operations.

Actually it use unsigned long instead of bitmap type as testing for
all zeroes is easier.

Signed-off-by: Frediano Ziglio <frediano.ziglio@citrix.com>
---
 xen/arch/x86/cpu/mcheck/mctelem.c |   52 ++++++++++++++++++++++---------------
 1 file changed, 31 insertions(+), 21 deletions(-)

diff --git a/xen/arch/x86/cpu/mcheck/mctelem.c b/xen/arch/x86/cpu/mcheck/mctelem.c
index 895ce1a..e56b6fb 100644
--- a/xen/arch/x86/cpu/mcheck/mctelem.c
+++ b/xen/arch/x86/cpu/mcheck/mctelem.c
@@ -69,6 +69,11 @@ struct mctelem_ent {
 #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 @@ struct mctelem_ent {
 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 @@ static struct mc_telem_ctl {
 	 * 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 @@ static void mctelem_free(struct mctelem_ent *tep)
 	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 @@ void mctelem_init(int reqdatasz)
 	}
 
 	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 @@ void mctelem_init(int reqdatasz)
 		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 @@ static int mctelem_drop_count;
 
 /* 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 @@ mctelem_cookie_t mctelem_reserve(mctelem_class_t which)
 			}
 		}
 
-		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);
-- 
1.7.10.4

Re: [PATCH] MCE: Fix race condition in mctelem_reserve

[David Vrabel]

On 22/01/14 10:50, Frediano Ziglio wrote:
> These lines (in mctelem_reserve)
> 
> 
>         newhead = oldhead->mcte_next;
>         if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
> 
> are racy. After you read the newhead pointer it can happen that another
> flow (thread or recursive invocation) change all the list but set head
> with same value. So oldhead is the same as *freelp but you are setting
> a new head that could point to whatever element (even already used).
> 
> This patch use instead a bit array and atomic bit operations.
> 
> Actually it use unsigned long instead of bitmap type as testing for
> all zeroes is easier.

bitmap_zero() does what you want.

David

Re: [PATCH] MCE: Fix race condition in mctelem_reserve

[Frediano Ziglio]

On Wed, 2014-01-22 at 10:56 +0000, David Vrabel wrote:
> On 22/01/14 10:50, Frediano Ziglio wrote:
> > These lines (in mctelem_reserve)
> > 
> > 
> >         newhead = oldhead->mcte_next;
> >         if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
> > 
> > are racy. After you read the newhead pointer it can happen that another
> > flow (thread or recursive invocation) change all the list but set head
> > with same value. So oldhead is the same as *freelp but you are setting
> > a new head that could point to whatever element (even already used).
> > 
> > This patch use instead a bit array and atomic bit operations.
> > 
> > Actually it use unsigned long instead of bitmap type as testing for
> > all zeroes is easier.
> 
> bitmap_zero() does what you want.
> 
> David

No, bitmap_zero fills with zero, do not check for zeroes.

Actually I read the bitmap, check for all zeroes (some item free) and
then use find_first_set_bit to find the bit number set to 1.

Frediano

Re: [PATCH] MCE: Fix race condition in mctelem_reserve

[Jan Beulich]

>>> On 22.01.14 at 11:50, Frediano Ziglio <frediano.ziglio@citrix.com> wrote:
> These lines (in mctelem_reserve)
> 
> 
>         newhead = oldhead->mcte_next;
>         if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
> 
> are racy. After you read the newhead pointer it can happen that another
> flow (thread or recursive invocation) change all the list but set head
> with same value. So oldhead is the same as *freelp but you are setting
> a new head that could point to whatever element (even already used).
> 
> This patch use instead a bit array and atomic bit operations.
> 
> Actually it use unsigned long instead of bitmap type as testing for
> all zeroes is easier.

Except you never test for all zeroes. All of the operations you use
(with the exception of find_first_set_bit(), which would need
replacing by find_first_bit()) are suitable to be used on bitmaps, so
I really don't see why this can't be a proper bitmap.

Jan

Re: [PATCH] MCE: Fix race condition in mctelem_reserve

[David Vrabel]

On 22/01/14 11:00, Frediano Ziglio wrote:
> On Wed, 2014-01-22 at 10:56 +0000, David Vrabel wrote:
>> On 22/01/14 10:50, Frediano Ziglio wrote:
>>> These lines (in mctelem_reserve)
>>>
>>>
>>>         newhead = oldhead->mcte_next;
>>>         if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
>>>
>>> are racy. After you read the newhead pointer it can happen that another
>>> flow (thread or recursive invocation) change all the list but set head
>>> with same value. So oldhead is the same as *freelp but you are setting
>>> a new head that could point to whatever element (even already used).
>>>
>>> This patch use instead a bit array and atomic bit operations.
>>>
>>> Actually it use unsigned long instead of bitmap type as testing for
>>> all zeroes is easier.
>>
>> bitmap_zero() does what you want.
>>
>> David
> 
> No, bitmap_zero fills with zero, do not check for zeroes.

bitmap_empty() sorry.

David

[PATCH v2] MCE: Fix race condition in mctelem_reserve

[Frediano Ziglio]

>From 49b37906afef0981f318064f4cb53a3602bca50a Mon Sep 17 00:00:00 2001
From: Frediano Ziglio <frediano.ziglio@citrix.com>
Date: Wed, 22 Jan 2014 10:48:50 +0000
Subject: [PATCH] MCE: Fix race condition in mctelem_reserve
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

These lines (in mctelem_reserve)

        newhead = oldhead->mcte_next;
        if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {

are racy. After you read the newhead pointer it can happen that another
flow (thread or recursive invocation) change all the list but set head
with same value. So oldhead is the same as *freelp but you are setting
a new head that could point to whatever element (even already used).

This patch use instead a bit array and atomic bit operations.

Signed-off-by: Frediano Ziglio <frediano.ziglio@citrix.com>
---
 xen/arch/x86/cpu/mcheck/mctelem.c |   81 ++++++++++++++-----------------------
 1 file changed, 30 insertions(+), 51 deletions(-)

Changes from v1:
- Use bitmap to allow any number of items to be used;
- Use a single bitmap to simplify reserve loop;
- Remove HOME flags as was not used anymore.

diff --git a/xen/arch/x86/cpu/mcheck/mctelem.c b/xen/arch/x86/cpu/mcheck/mctelem.c
index 895ce1a..ed8e8d2 100644
--- a/xen/arch/x86/cpu/mcheck/mctelem.c
+++ b/xen/arch/x86/cpu/mcheck/mctelem.c
@@ -37,24 +37,19 @@ struct mctelem_ent {
 	void *mcte_data;		/* corresponding data payload */
 };
 
-#define	MCTE_F_HOME_URGENT		0x0001U	/* free to urgent freelist */
-#define	MCTE_F_HOME_NONURGENT		0x0002U /* free to nonurgent freelist */
-#define	MCTE_F_CLASS_URGENT		0x0004U /* in use - urgent errors */
-#define	MCTE_F_CLASS_NONURGENT		0x0008U /* in use - nonurgent errors */
+#define	MCTE_F_CLASS_URGENT		0x0001U /* in use - urgent errors */
+#define	MCTE_F_CLASS_NONURGENT		0x0002U /* in use - nonurgent errors */
 #define	MCTE_F_STATE_FREE		0x0010U	/* on a freelist */
 #define	MCTE_F_STATE_UNCOMMITTED	0x0020U	/* reserved; on no list */
 #define	MCTE_F_STATE_COMMITTED		0x0040U	/* on a committed list */
 #define	MCTE_F_STATE_PROCESSING		0x0080U	/* on a processing list */
 
-#define	MCTE_F_MASK_HOME	(MCTE_F_HOME_URGENT | MCTE_F_HOME_NONURGENT)
 #define	MCTE_F_MASK_CLASS	(MCTE_F_CLASS_URGENT | MCTE_F_CLASS_NONURGENT)
 #define	MCTE_F_MASK_STATE	(MCTE_F_STATE_FREE | \
 				MCTE_F_STATE_UNCOMMITTED | \
 				MCTE_F_STATE_COMMITTED | \
 				MCTE_F_STATE_PROCESSING)
 
-#define	MCTE_HOME(tep) ((tep)->mcte_flags & MCTE_F_MASK_HOME)
-
 #define	MCTE_CLASS(tep) ((tep)->mcte_flags & MCTE_F_MASK_CLASS)
 #define	MCTE_SET_CLASS(tep, new) do { \
     (tep)->mcte_flags &= ~MCTE_F_MASK_CLASS; \
@@ -69,6 +64,8 @@ struct mctelem_ent {
 #define	MC_URGENT_NENT		10
 #define	MC_NONURGENT_NENT	20
 
+#define MC_NENT (MC_URGENT_NENT + MC_NONURGENT_NENT)
+
 #define	MC_NCLASSES		(MC_NONURGENT + 1)
 
 #define	COOKIE2MCTE(c)		((struct mctelem_ent *)(c))
@@ -77,11 +74,9 @@ struct mctelem_ent {
 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 +96,7 @@ static struct mc_telem_ctl {
 	 * 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];
+	DECLARE_BITMAP(mctc_free, MC_NENT);
 	struct mctelem_ent *mctc_committed[MC_NCLASSES];
 	struct mctelem_ent *mctc_processing_head[MC_NCLASSES];
 	struct mctelem_ent *mctc_processing_tail[MC_NCLASSES];
@@ -207,14 +202,14 @@ int mctelem_has_deferred(unsigned int cpu)
  */
 static void mctelem_free(struct mctelem_ent *tep)
 {
-	mctelem_class_t target = MCTE_HOME(tep) == MCTE_F_HOME_URGENT ?
-	    MC_URGENT : MC_NONURGENT;
-
 	BUG_ON(tep->mcte_refcnt != 0);
 	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);
 }
 
 /* Increment the reference count of an entry that is not linked on to
@@ -274,34 +269,25 @@ void mctelem_init(int reqdatasz)
 	}
 
 	if ((mctctl.mctc_elems = xmalloc_array(struct mctelem_ent,
-	    MC_URGENT_NENT + MC_NONURGENT_NENT)) == NULL ||
-	    (datarr = xmalloc_bytes((MC_URGENT_NENT + MC_NONURGENT_NENT) *
-	    datasz)) == NULL) {
+	    MC_NENT)) == NULL ||
+	    (datarr = xmalloc_bytes(MC_NENT * datasz)) == NULL) {
 		if (mctctl.mctc_elems)
 			xfree(mctctl.mctc_elems);
 		printk("Allocations for MCA telemetry failed\n");
 		return;
 	}
 
-	for (i = 0; i < MC_URGENT_NENT + MC_NONURGENT_NENT; i++) {
-		struct mctelem_ent *tep, **tepp;
+	for (i = 0; i < MC_NENT; i++) {
+		struct mctelem_ent *tep;
 
 		tep = mctctl.mctc_elems + i;
 		tep->mcte_flags = MCTE_F_STATE_FREE;
 		tep->mcte_refcnt = 0;
 		tep->mcte_data = datarr + i * datasz;
 
-		if (i < MC_URGENT_NENT) {
-			tepp = &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;
-		}
-
-		tep->mcte_next = *tepp;
+		__set_bit(i, mctctl.mctc_free);
+		tep->mcte_next = NULL;
 		tep->mcte_prev = NULL;
-		*tepp = tep;
 	}
 }
 
@@ -310,32 +296,25 @@ static int mctelem_drop_count;
 
 /* 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;
-	mctelem_class_t target = (which == MC_URGENT) ?
-	    MC_URGENT : MC_NONURGENT;
+	unsigned bit;
+	unsigned start_bit = (which == MC_URGENT) ? 0 : MC_URGENT_NENT;
 
-	freelp = &mctctl.mctc_free[target];
 	for (;;) {
-		if ((oldhead = *freelp) == NULL) {
-			if (which == MC_URGENT && target == MC_URGENT) {
-				/* raid the non-urgent freelist */
-				target = MC_NONURGENT;
-				freelp = &mctctl.mctc_free[target];
-				continue;
-			} else {
-				mctelem_drop_count++;
-				return (NULL);
-			}
+		bit = find_next_bit(mctctl.mctc_free, MC_NENT, start_bit);
+
+		if (bit >= MC_NENT) {
+			mctelem_drop_count++;
+			return (NULL);
 		}
 
-		newhead = oldhead->mcte_next;
-		if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
-			struct mctelem_ent *tep = oldhead;
+		/* try to allocate, atomically clear free bit */
+		if (test_and_clear_bit(bit, mctctl.mctc_free)) {
+			/* return element we got */
+			struct mctelem_ent *tep = mctctl.mctc_elems + bit;
 
 			mctelem_hold(tep);
 			MCTE_TRANSITION_STATE(tep, FREE, UNCOMMITTED);
-- 
1.7.10.4

Re: [PATCH v2] MCE: Fix race condition in mctelem_reserve

[Frediano Ziglio]

Ping 

On Wed, 2014-01-22 at 17:17 +0000, Frediano Ziglio wrote:
> These lines (in mctelem_reserve)
> 
>         newhead = oldhead->mcte_next;
>         if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
> 
> are racy. After you read the newhead pointer it can happen that another
> flow (thread or recursive invocation) change all the list but set head
> with same value. So oldhead is the same as *freelp but you are setting
> a new head that could point to whatever element (even already used).
> 
> This patch use instead a bit array and atomic bit operations.
> 
> Signed-off-by: Frediano Ziglio <frediano.ziglio@citrix.com>
> ---
>  xen/arch/x86/cpu/mcheck/mctelem.c |   81 ++++++++++++++-----------------------
>  1 file changed, 30 insertions(+), 51 deletions(-)
> 
> Changes from v1:
> - Use bitmap to allow any number of items to be used;
> - Use a single bitmap to simplify reserve loop;
> - Remove HOME flags as was not used anymore.
> 
> diff --git a/xen/arch/x86/cpu/mcheck/mctelem.c b/xen/arch/x86/cpu/mcheck/mctelem.c
> index 895ce1a..ed8e8d2 100644
> --- a/xen/arch/x86/cpu/mcheck/mctelem.c
> +++ b/xen/arch/x86/cpu/mcheck/mctelem.c
> @@ -37,24 +37,19 @@ struct mctelem_ent {
>  	void *mcte_data;		/* corresponding data payload */
>  };
>  
> -#define	MCTE_F_HOME_URGENT		0x0001U	/* free to urgent freelist */
> -#define	MCTE_F_HOME_NONURGENT		0x0002U /* free to nonurgent freelist */
> -#define	MCTE_F_CLASS_URGENT		0x0004U /* in use - urgent errors */
> -#define	MCTE_F_CLASS_NONURGENT		0x0008U /* in use - nonurgent errors */
> +#define	MCTE_F_CLASS_URGENT		0x0001U /* in use - urgent errors */
> +#define	MCTE_F_CLASS_NONURGENT		0x0002U /* in use - nonurgent errors */
>  #define	MCTE_F_STATE_FREE		0x0010U	/* on a freelist */
>  #define	MCTE_F_STATE_UNCOMMITTED	0x0020U	/* reserved; on no list */
>  #define	MCTE_F_STATE_COMMITTED		0x0040U	/* on a committed list */
>  #define	MCTE_F_STATE_PROCESSING		0x0080U	/* on a processing list */
>  
> -#define	MCTE_F_MASK_HOME	(MCTE_F_HOME_URGENT | MCTE_F_HOME_NONURGENT)
>  #define	MCTE_F_MASK_CLASS	(MCTE_F_CLASS_URGENT | MCTE_F_CLASS_NONURGENT)
>  #define	MCTE_F_MASK_STATE	(MCTE_F_STATE_FREE | \
>  				MCTE_F_STATE_UNCOMMITTED | \
>  				MCTE_F_STATE_COMMITTED | \
>  				MCTE_F_STATE_PROCESSING)
>  
> -#define	MCTE_HOME(tep) ((tep)->mcte_flags & MCTE_F_MASK_HOME)
> -
>  #define	MCTE_CLASS(tep) ((tep)->mcte_flags & MCTE_F_MASK_CLASS)
>  #define	MCTE_SET_CLASS(tep, new) do { \
>      (tep)->mcte_flags &= ~MCTE_F_MASK_CLASS; \
> @@ -69,6 +64,8 @@ struct mctelem_ent {
>  #define	MC_URGENT_NENT		10
>  #define	MC_NONURGENT_NENT	20
>  
> +#define MC_NENT (MC_URGENT_NENT + MC_NONURGENT_NENT)
> +
>  #define	MC_NCLASSES		(MC_NONURGENT + 1)
>  
>  #define	COOKIE2MCTE(c)		((struct mctelem_ent *)(c))
> @@ -77,11 +74,9 @@ struct mctelem_ent {
>  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 +96,7 @@ static struct mc_telem_ctl {
>  	 * 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];
> +	DECLARE_BITMAP(mctc_free, MC_NENT);
>  	struct mctelem_ent *mctc_committed[MC_NCLASSES];
>  	struct mctelem_ent *mctc_processing_head[MC_NCLASSES];
>  	struct mctelem_ent *mctc_processing_tail[MC_NCLASSES];
> @@ -207,14 +202,14 @@ int mctelem_has_deferred(unsigned int cpu)
>   */
>  static void mctelem_free(struct mctelem_ent *tep)
>  {
> -	mctelem_class_t target = MCTE_HOME(tep) == MCTE_F_HOME_URGENT ?
> -	    MC_URGENT : MC_NONURGENT;
> -
>  	BUG_ON(tep->mcte_refcnt != 0);
>  	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);
>  }
>  
>  /* Increment the reference count of an entry that is not linked on to
> @@ -274,34 +269,25 @@ void mctelem_init(int reqdatasz)
>  	}
>  
>  	if ((mctctl.mctc_elems = xmalloc_array(struct mctelem_ent,
> -	    MC_URGENT_NENT + MC_NONURGENT_NENT)) == NULL ||
> -	    (datarr = xmalloc_bytes((MC_URGENT_NENT + MC_NONURGENT_NENT) *
> -	    datasz)) == NULL) {
> +	    MC_NENT)) == NULL ||
> +	    (datarr = xmalloc_bytes(MC_NENT * datasz)) == NULL) {
>  		if (mctctl.mctc_elems)
>  			xfree(mctctl.mctc_elems);
>  		printk("Allocations for MCA telemetry failed\n");
>  		return;
>  	}
>  
> -	for (i = 0; i < MC_URGENT_NENT + MC_NONURGENT_NENT; i++) {
> -		struct mctelem_ent *tep, **tepp;
> +	for (i = 0; i < MC_NENT; i++) {
> +		struct mctelem_ent *tep;
>  
>  		tep = mctctl.mctc_elems + i;
>  		tep->mcte_flags = MCTE_F_STATE_FREE;
>  		tep->mcte_refcnt = 0;
>  		tep->mcte_data = datarr + i * datasz;
>  
> -		if (i < MC_URGENT_NENT) {
> -			tepp = &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;
> -		}
> -
> -		tep->mcte_next = *tepp;
> +		__set_bit(i, mctctl.mctc_free);
> +		tep->mcte_next = NULL;
>  		tep->mcte_prev = NULL;
> -		*tepp = tep;
>  	}
>  }
>  
> @@ -310,32 +296,25 @@ static int mctelem_drop_count;
>  
>  /* 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;
> -	mctelem_class_t target = (which == MC_URGENT) ?
> -	    MC_URGENT : MC_NONURGENT;
> +	unsigned bit;
> +	unsigned start_bit = (which == MC_URGENT) ? 0 : MC_URGENT_NENT;
>  
> -	freelp = &mctctl.mctc_free[target];
>  	for (;;) {
> -		if ((oldhead = *freelp) == NULL) {
> -			if (which == MC_URGENT && target == MC_URGENT) {
> -				/* raid the non-urgent freelist */
> -				target = MC_NONURGENT;
> -				freelp = &mctctl.mctc_free[target];
> -				continue;
> -			} else {
> -				mctelem_drop_count++;
> -				return (NULL);
> -			}
> +		bit = find_next_bit(mctctl.mctc_free, MC_NENT, start_bit);
> +
> +		if (bit >= MC_NENT) {
> +			mctelem_drop_count++;
> +			return (NULL);
>  		}
>  
> -		newhead = oldhead->mcte_next;
> -		if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
> -			struct mctelem_ent *tep = oldhead;
> +		/* try to allocate, atomically clear free bit */
> +		if (test_and_clear_bit(bit, mctctl.mctc_free)) {
> +			/* return element we got */
> +			struct mctelem_ent *tep = mctctl.mctc_elems + bit;
>  
>  			mctelem_hold(tep);
>  			MCTE_TRANSITION_STATE(tep, FREE, UNCOMMITTED);

Re: [PATCH v2] MCE: Fix race condition in mctelem_reserve

[Jan Beulich]

>>> On 30.01.14 at 10:20, Frediano Ziglio <frediano.ziglio@citrix.com> wrote:
> Ping 

You're ping should be to the MCE maintainers - I'm merely
waiting for their comments/ack.

Jan

> On Wed, 2014-01-22 at 17:17 +0000, Frediano Ziglio wrote:
>> These lines (in mctelem_reserve)
>> 
>>         newhead = oldhead->mcte_next;
>>         if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
>> 
>> are racy. After you read the newhead pointer it can happen that another
>> flow (thread or recursive invocation) change all the list but set head
>> with same value. So oldhead is the same as *freelp but you are setting
>> a new head that could point to whatever element (even already used).
>> 
>> This patch use instead a bit array and atomic bit operations.
>> 
>> Signed-off-by: Frediano Ziglio <frediano.ziglio@citrix.com>
>> ---
>>  xen/arch/x86/cpu/mcheck/mctelem.c |   81 
> ++++++++++++++-----------------------
>>  1 file changed, 30 insertions(+), 51 deletions(-)
>> 
>> Changes from v1:
>> - Use bitmap to allow any number of items to be used;
>> - Use a single bitmap to simplify reserve loop;
>> - Remove HOME flags as was not used anymore.
>> 
>> diff --git a/xen/arch/x86/cpu/mcheck/mctelem.c 
> b/xen/arch/x86/cpu/mcheck/mctelem.c
>> index 895ce1a..ed8e8d2 100644
>> --- a/xen/arch/x86/cpu/mcheck/mctelem.c
>> +++ b/xen/arch/x86/cpu/mcheck/mctelem.c
>> @@ -37,24 +37,19 @@ struct mctelem_ent {
>>  	void *mcte_data;		/* corresponding data payload */
>>  };
>>  
>> -#define	MCTE_F_HOME_URGENT		0x0001U	/* free to urgent freelist */
>> -#define	MCTE_F_HOME_NONURGENT		0x0002U /* free to nonurgent freelist */
>> -#define	MCTE_F_CLASS_URGENT		0x0004U /* in use - urgent errors */
>> -#define	MCTE_F_CLASS_NONURGENT		0x0008U /* in use - nonurgent errors */
>> +#define	MCTE_F_CLASS_URGENT		0x0001U /* in use - urgent errors */
>> +#define	MCTE_F_CLASS_NONURGENT		0x0002U /* in use - nonurgent errors */
>>  #define	MCTE_F_STATE_FREE		0x0010U	/* on a freelist */
>>  #define	MCTE_F_STATE_UNCOMMITTED	0x0020U	/* reserved; on no list */
>>  #define	MCTE_F_STATE_COMMITTED		0x0040U	/* on a committed list */
>>  #define	MCTE_F_STATE_PROCESSING		0x0080U	/* on a processing list */
>>  
>> -#define	MCTE_F_MASK_HOME	(MCTE_F_HOME_URGENT | MCTE_F_HOME_NONURGENT)
>>  #define	MCTE_F_MASK_CLASS	(MCTE_F_CLASS_URGENT | MCTE_F_CLASS_NONURGENT)
>>  #define	MCTE_F_MASK_STATE	(MCTE_F_STATE_FREE | \
>>  				MCTE_F_STATE_UNCOMMITTED | \
>>  				MCTE_F_STATE_COMMITTED | \
>>  				MCTE_F_STATE_PROCESSING)
>>  
>> -#define	MCTE_HOME(tep) ((tep)->mcte_flags & MCTE_F_MASK_HOME)
>> -
>>  #define	MCTE_CLASS(tep) ((tep)->mcte_flags & MCTE_F_MASK_CLASS)
>>  #define	MCTE_SET_CLASS(tep, new) do { \
>>      (tep)->mcte_flags &= ~MCTE_F_MASK_CLASS; \
>> @@ -69,6 +64,8 @@ struct mctelem_ent {
>>  #define	MC_URGENT_NENT		10
>>  #define	MC_NONURGENT_NENT	20
>>  
>> +#define MC_NENT (MC_URGENT_NENT + MC_NONURGENT_NENT)
>> +
>>  #define	MC_NCLASSES		(MC_NONURGENT + 1)
>>  
>>  #define	COOKIE2MCTE(c)		((struct mctelem_ent *)(c))
>> @@ -77,11 +74,9 @@ struct mctelem_ent {
>>  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 +96,7 @@ static struct mc_telem_ctl {
>>  	 * 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];
>> +	DECLARE_BITMAP(mctc_free, MC_NENT);
>>  	struct mctelem_ent *mctc_committed[MC_NCLASSES];
>>  	struct mctelem_ent *mctc_processing_head[MC_NCLASSES];
>>  	struct mctelem_ent *mctc_processing_tail[MC_NCLASSES];
>> @@ -207,14 +202,14 @@ int mctelem_has_deferred(unsigned int cpu)
>>   */
>>  static void mctelem_free(struct mctelem_ent *tep)
>>  {
>> -	mctelem_class_t target = MCTE_HOME(tep) == MCTE_F_HOME_URGENT ?
>> -	    MC_URGENT : MC_NONURGENT;
>> -
>>  	BUG_ON(tep->mcte_refcnt != 0);
>>  	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);
>>  }
>>  
>>  /* Increment the reference count of an entry that is not linked on to
>> @@ -274,34 +269,25 @@ void mctelem_init(int reqdatasz)
>>  	}
>>  
>>  	if ((mctctl.mctc_elems = xmalloc_array(struct mctelem_ent,
>> -	    MC_URGENT_NENT + MC_NONURGENT_NENT)) == NULL ||
>> -	    (datarr = xmalloc_bytes((MC_URGENT_NENT + MC_NONURGENT_NENT) *
>> -	    datasz)) == NULL) {
>> +	    MC_NENT)) == NULL ||
>> +	    (datarr = xmalloc_bytes(MC_NENT * datasz)) == NULL) {
>>  		if (mctctl.mctc_elems)
>>  			xfree(mctctl.mctc_elems);
>>  		printk("Allocations for MCA telemetry failed\n");
>>  		return;
>>  	}
>>  
>> -	for (i = 0; i < MC_URGENT_NENT + MC_NONURGENT_NENT; i++) {
>> -		struct mctelem_ent *tep, **tepp;
>> +	for (i = 0; i < MC_NENT; i++) {
>> +		struct mctelem_ent *tep;
>>  
>>  		tep = mctctl.mctc_elems + i;
>>  		tep->mcte_flags = MCTE_F_STATE_FREE;
>>  		tep->mcte_refcnt = 0;
>>  		tep->mcte_data = datarr + i * datasz;
>>  
>> -		if (i < MC_URGENT_NENT) {
>> -			tepp = &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;
>> -		}
>> -
>> -		tep->mcte_next = *tepp;
>> +		__set_bit(i, mctctl.mctc_free);
>> +		tep->mcte_next = NULL;
>>  		tep->mcte_prev = NULL;
>> -		*tepp = tep;
>>  	}
>>  }
>>  
>> @@ -310,32 +296,25 @@ static int mctelem_drop_count;
>>  
>>  /* 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;
>> -	mctelem_class_t target = (which == MC_URGENT) ?
>> -	    MC_URGENT : MC_NONURGENT;
>> +	unsigned bit;
>> +	unsigned start_bit = (which == MC_URGENT) ? 0 : MC_URGENT_NENT;
>>  
>> -	freelp = &mctctl.mctc_free[target];
>>  	for (;;) {
>> -		if ((oldhead = *freelp) == NULL) {
>> -			if (which == MC_URGENT && target == MC_URGENT) {
>> -				/* raid the non-urgent freelist */
>> -				target = MC_NONURGENT;
>> -				freelp = &mctctl.mctc_free[target];
>> -				continue;
>> -			} else {
>> -				mctelem_drop_count++;
>> -				return (NULL);
>> -			}
>> +		bit = find_next_bit(mctctl.mctc_free, MC_NENT, start_bit);
>> +
>> +		if (bit >= MC_NENT) {
>> +			mctelem_drop_count++;
>> +			return (NULL);
>>  		}
>>  
>> -		newhead = oldhead->mcte_next;
>> -		if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
>> -			struct mctelem_ent *tep = oldhead;
>> +		/* try to allocate, atomically clear free bit */
>> +		if (test_and_clear_bit(bit, mctctl.mctc_free)) {
>> +			/* return element we got */
>> +			struct mctelem_ent *tep = mctctl.mctc_elems + bit;
>>  
>>  			mctelem_hold(tep);
>>  			MCTE_TRANSITION_STATE(tep, FREE, UNCOMMITTED);

Re: [PATCH v2] MCE: Fix race condition in mctelem_reserve

[Frediano Ziglio]

Ping

On Wed, 2014-01-22 at 17:17 +0000, Frediano Ziglio wrote:
> From 49b37906afef0981f318064f4cb53a3602bca50a Mon Sep 17 00:00:00 2001
> From: Frediano Ziglio <frediano.ziglio@citrix.com>
> Date: Wed, 22 Jan 2014 10:48:50 +0000
> Subject: [PATCH] MCE: Fix race condition in mctelem_reserve
> MIME-Version: 1.0
> Content-Type: text/plain; charset=UTF-8
> Content-Transfer-Encoding: 8bit
> 
> These lines (in mctelem_reserve)
> 
>         newhead = oldhead->mcte_next;
>         if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
> 
> are racy. After you read the newhead pointer it can happen that another
> flow (thread or recursive invocation) change all the list but set head
> with same value. So oldhead is the same as *freelp but you are setting
> a new head that could point to whatever element (even already used).
> 
> This patch use instead a bit array and atomic bit operations.
> 
> Signed-off-by: Frediano Ziglio <frediano.ziglio@citrix.com>
> ---
>  xen/arch/x86/cpu/mcheck/mctelem.c |   81 ++++++++++++++-----------------------
>  1 file changed, 30 insertions(+), 51 deletions(-)
> 
> Changes from v1:
> - Use bitmap to allow any number of items to be used;
> - Use a single bitmap to simplify reserve loop;
> - Remove HOME flags as was not used anymore.
> 
> diff --git a/xen/arch/x86/cpu/mcheck/mctelem.c b/xen/arch/x86/cpu/mcheck/mctelem.c
> index 895ce1a..ed8e8d2 100644
> --- a/xen/arch/x86/cpu/mcheck/mctelem.c
> +++ b/xen/arch/x86/cpu/mcheck/mctelem.c
> @@ -37,24 +37,19 @@ struct mctelem_ent {
>  	void *mcte_data;		/* corresponding data payload */
>  };
>  
> -#define	MCTE_F_HOME_URGENT		0x0001U	/* free to urgent freelist */
> -#define	MCTE_F_HOME_NONURGENT		0x0002U /* free to nonurgent freelist */
> -#define	MCTE_F_CLASS_URGENT		0x0004U /* in use - urgent errors */
> -#define	MCTE_F_CLASS_NONURGENT		0x0008U /* in use - nonurgent errors */
> +#define	MCTE_F_CLASS_URGENT		0x0001U /* in use - urgent errors */
> +#define	MCTE_F_CLASS_NONURGENT		0x0002U /* in use - nonurgent errors */
>  #define	MCTE_F_STATE_FREE		0x0010U	/* on a freelist */
>  #define	MCTE_F_STATE_UNCOMMITTED	0x0020U	/* reserved; on no list */
>  #define	MCTE_F_STATE_COMMITTED		0x0040U	/* on a committed list */
>  #define	MCTE_F_STATE_PROCESSING		0x0080U	/* on a processing list */
>  
> -#define	MCTE_F_MASK_HOME	(MCTE_F_HOME_URGENT | MCTE_F_HOME_NONURGENT)
>  #define	MCTE_F_MASK_CLASS	(MCTE_F_CLASS_URGENT | MCTE_F_CLASS_NONURGENT)
>  #define	MCTE_F_MASK_STATE	(MCTE_F_STATE_FREE | \
>  				MCTE_F_STATE_UNCOMMITTED | \
>  				MCTE_F_STATE_COMMITTED | \
>  				MCTE_F_STATE_PROCESSING)
>  
> -#define	MCTE_HOME(tep) ((tep)->mcte_flags & MCTE_F_MASK_HOME)
> -
>  #define	MCTE_CLASS(tep) ((tep)->mcte_flags & MCTE_F_MASK_CLASS)
>  #define	MCTE_SET_CLASS(tep, new) do { \
>      (tep)->mcte_flags &= ~MCTE_F_MASK_CLASS; \
> @@ -69,6 +64,8 @@ struct mctelem_ent {
>  #define	MC_URGENT_NENT		10
>  #define	MC_NONURGENT_NENT	20
>  
> +#define MC_NENT (MC_URGENT_NENT + MC_NONURGENT_NENT)
> +
>  #define	MC_NCLASSES		(MC_NONURGENT + 1)
>  
>  #define	COOKIE2MCTE(c)		((struct mctelem_ent *)(c))
> @@ -77,11 +74,9 @@ struct mctelem_ent {
>  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 +96,7 @@ static struct mc_telem_ctl {
>  	 * 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];
> +	DECLARE_BITMAP(mctc_free, MC_NENT);
>  	struct mctelem_ent *mctc_committed[MC_NCLASSES];
>  	struct mctelem_ent *mctc_processing_head[MC_NCLASSES];
>  	struct mctelem_ent *mctc_processing_tail[MC_NCLASSES];
> @@ -207,14 +202,14 @@ int mctelem_has_deferred(unsigned int cpu)
>   */
>  static void mctelem_free(struct mctelem_ent *tep)
>  {
> -	mctelem_class_t target = MCTE_HOME(tep) == MCTE_F_HOME_URGENT ?
> -	    MC_URGENT : MC_NONURGENT;
> -
>  	BUG_ON(tep->mcte_refcnt != 0);
>  	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);
>  }
>  
>  /* Increment the reference count of an entry that is not linked on to
> @@ -274,34 +269,25 @@ void mctelem_init(int reqdatasz)
>  	}
>  
>  	if ((mctctl.mctc_elems = xmalloc_array(struct mctelem_ent,
> -	    MC_URGENT_NENT + MC_NONURGENT_NENT)) == NULL ||
> -	    (datarr = xmalloc_bytes((MC_URGENT_NENT + MC_NONURGENT_NENT) *
> -	    datasz)) == NULL) {
> +	    MC_NENT)) == NULL ||
> +	    (datarr = xmalloc_bytes(MC_NENT * datasz)) == NULL) {
>  		if (mctctl.mctc_elems)
>  			xfree(mctctl.mctc_elems);
>  		printk("Allocations for MCA telemetry failed\n");
>  		return;
>  	}
>  
> -	for (i = 0; i < MC_URGENT_NENT + MC_NONURGENT_NENT; i++) {
> -		struct mctelem_ent *tep, **tepp;
> +	for (i = 0; i < MC_NENT; i++) {
> +		struct mctelem_ent *tep;
>  
>  		tep = mctctl.mctc_elems + i;
>  		tep->mcte_flags = MCTE_F_STATE_FREE;
>  		tep->mcte_refcnt = 0;
>  		tep->mcte_data = datarr + i * datasz;
>  
> -		if (i < MC_URGENT_NENT) {
> -			tepp = &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;
> -		}
> -
> -		tep->mcte_next = *tepp;
> +		__set_bit(i, mctctl.mctc_free);
> +		tep->mcte_next = NULL;
>  		tep->mcte_prev = NULL;
> -		*tepp = tep;
>  	}
>  }
>  
> @@ -310,32 +296,25 @@ static int mctelem_drop_count;
>  
>  /* 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;
> -	mctelem_class_t target = (which == MC_URGENT) ?
> -	    MC_URGENT : MC_NONURGENT;
> +	unsigned bit;
> +	unsigned start_bit = (which == MC_URGENT) ? 0 : MC_URGENT_NENT;
>  
> -	freelp = &mctctl.mctc_free[target];
>  	for (;;) {
> -		if ((oldhead = *freelp) == NULL) {
> -			if (which == MC_URGENT && target == MC_URGENT) {
> -				/* raid the non-urgent freelist */
> -				target = MC_NONURGENT;
> -				freelp = &mctctl.mctc_free[target];
> -				continue;
> -			} else {
> -				mctelem_drop_count++;
> -				return (NULL);
> -			}
> +		bit = find_next_bit(mctctl.mctc_free, MC_NENT, start_bit);
> +
> +		if (bit >= MC_NENT) {
> +			mctelem_drop_count++;
> +			return (NULL);
>  		}
>  
> -		newhead = oldhead->mcte_next;
> -		if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
> -			struct mctelem_ent *tep = oldhead;
> +		/* try to allocate, atomically clear free bit */
> +		if (test_and_clear_bit(bit, mctctl.mctc_free)) {
> +			/* return element we got */
> +			struct mctelem_ent *tep = mctctl.mctc_elems + bit;
>  
>  			mctelem_hold(tep);
>  			MCTE_TRANSITION_STATE(tep, FREE, UNCOMMITTED);

Re: [PATCH v2] MCE: Fix race condition in mctelem_reserve

[Frediano Ziglio]

Ping

On Fri, 2014-01-31 at 13:37 +0000, Frediano Ziglio wrote:
> Ping
> 
> On Wed, 2014-01-22 at 17:17 +0000, Frediano Ziglio wrote:
> > From 49b37906afef0981f318064f4cb53a3602bca50a Mon Sep 17 00:00:00 2001
> > From: Frediano Ziglio <frediano.ziglio@citrix.com>
> > Date: Wed, 22 Jan 2014 10:48:50 +0000
> > Subject: [PATCH] MCE: Fix race condition in mctelem_reserve
> > MIME-Version: 1.0
> > Content-Type: text/plain; charset=UTF-8
> > Content-Transfer-Encoding: 8bit
> > 
> > These lines (in mctelem_reserve)
> > 
> >         newhead = oldhead->mcte_next;
> >         if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
> > 
> > are racy. After you read the newhead pointer it can happen that another
> > flow (thread or recursive invocation) change all the list but set head
> > with same value. So oldhead is the same as *freelp but you are setting
> > a new head that could point to whatever element (even already used).
> > 
> > This patch use instead a bit array and atomic bit operations.
> > 
> > Signed-off-by: Frediano Ziglio <frediano.ziglio@citrix.com>
> > ---
> >  xen/arch/x86/cpu/mcheck/mctelem.c |   81 ++++++++++++++-----------------------
> >  1 file changed, 30 insertions(+), 51 deletions(-)
> > 
> > Changes from v1:
> > - Use bitmap to allow any number of items to be used;
> > - Use a single bitmap to simplify reserve loop;
> > - Remove HOME flags as was not used anymore.
> > 
> > diff --git a/xen/arch/x86/cpu/mcheck/mctelem.c b/xen/arch/x86/cpu/mcheck/mctelem.c
> > index 895ce1a..ed8e8d2 100644
> > --- a/xen/arch/x86/cpu/mcheck/mctelem.c
> > +++ b/xen/arch/x86/cpu/mcheck/mctelem.c
> > @@ -37,24 +37,19 @@ struct mctelem_ent {
> >  	void *mcte_data;		/* corresponding data payload */
> >  };
> >  
> > -#define	MCTE_F_HOME_URGENT		0x0001U	/* free to urgent freelist */
> > -#define	MCTE_F_HOME_NONURGENT		0x0002U /* free to nonurgent freelist */
> > -#define	MCTE_F_CLASS_URGENT		0x0004U /* in use - urgent errors */
> > -#define	MCTE_F_CLASS_NONURGENT		0x0008U /* in use - nonurgent errors */
> > +#define	MCTE_F_CLASS_URGENT		0x0001U /* in use - urgent errors */
> > +#define	MCTE_F_CLASS_NONURGENT		0x0002U /* in use - nonurgent errors */
> >  #define	MCTE_F_STATE_FREE		0x0010U	/* on a freelist */
> >  #define	MCTE_F_STATE_UNCOMMITTED	0x0020U	/* reserved; on no list */
> >  #define	MCTE_F_STATE_COMMITTED		0x0040U	/* on a committed list */
> >  #define	MCTE_F_STATE_PROCESSING		0x0080U	/* on a processing list */
> >  
> > -#define	MCTE_F_MASK_HOME	(MCTE_F_HOME_URGENT | MCTE_F_HOME_NONURGENT)
> >  #define	MCTE_F_MASK_CLASS	(MCTE_F_CLASS_URGENT | MCTE_F_CLASS_NONURGENT)
> >  #define	MCTE_F_MASK_STATE	(MCTE_F_STATE_FREE | \
> >  				MCTE_F_STATE_UNCOMMITTED | \
> >  				MCTE_F_STATE_COMMITTED | \
> >  				MCTE_F_STATE_PROCESSING)
> >  
> > -#define	MCTE_HOME(tep) ((tep)->mcte_flags & MCTE_F_MASK_HOME)
> > -
> >  #define	MCTE_CLASS(tep) ((tep)->mcte_flags & MCTE_F_MASK_CLASS)
> >  #define	MCTE_SET_CLASS(tep, new) do { \
> >      (tep)->mcte_flags &= ~MCTE_F_MASK_CLASS; \
> > @@ -69,6 +64,8 @@ struct mctelem_ent {
> >  #define	MC_URGENT_NENT		10
> >  #define	MC_NONURGENT_NENT	20
> >  
> > +#define MC_NENT (MC_URGENT_NENT + MC_NONURGENT_NENT)
> > +
> >  #define	MC_NCLASSES		(MC_NONURGENT + 1)
> >  
> >  #define	COOKIE2MCTE(c)		((struct mctelem_ent *)(c))
> > @@ -77,11 +74,9 @@ struct mctelem_ent {
> >  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 +96,7 @@ static struct mc_telem_ctl {
> >  	 * 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];
> > +	DECLARE_BITMAP(mctc_free, MC_NENT);
> >  	struct mctelem_ent *mctc_committed[MC_NCLASSES];
> >  	struct mctelem_ent *mctc_processing_head[MC_NCLASSES];
> >  	struct mctelem_ent *mctc_processing_tail[MC_NCLASSES];
> > @@ -207,14 +202,14 @@ int mctelem_has_deferred(unsigned int cpu)
> >   */
> >  static void mctelem_free(struct mctelem_ent *tep)
> >  {
> > -	mctelem_class_t target = MCTE_HOME(tep) == MCTE_F_HOME_URGENT ?
> > -	    MC_URGENT : MC_NONURGENT;
> > -
> >  	BUG_ON(tep->mcte_refcnt != 0);
> >  	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);
> >  }
> >  
> >  /* Increment the reference count of an entry that is not linked on to
> > @@ -274,34 +269,25 @@ void mctelem_init(int reqdatasz)
> >  	}
> >  
> >  	if ((mctctl.mctc_elems = xmalloc_array(struct mctelem_ent,
> > -	    MC_URGENT_NENT + MC_NONURGENT_NENT)) == NULL ||
> > -	    (datarr = xmalloc_bytes((MC_URGENT_NENT + MC_NONURGENT_NENT) *
> > -	    datasz)) == NULL) {
> > +	    MC_NENT)) == NULL ||
> > +	    (datarr = xmalloc_bytes(MC_NENT * datasz)) == NULL) {
> >  		if (mctctl.mctc_elems)
> >  			xfree(mctctl.mctc_elems);
> >  		printk("Allocations for MCA telemetry failed\n");
> >  		return;
> >  	}
> >  
> > -	for (i = 0; i < MC_URGENT_NENT + MC_NONURGENT_NENT; i++) {
> > -		struct mctelem_ent *tep, **tepp;
> > +	for (i = 0; i < MC_NENT; i++) {
> > +		struct mctelem_ent *tep;
> >  
> >  		tep = mctctl.mctc_elems + i;
> >  		tep->mcte_flags = MCTE_F_STATE_FREE;
> >  		tep->mcte_refcnt = 0;
> >  		tep->mcte_data = datarr + i * datasz;
> >  
> > -		if (i < MC_URGENT_NENT) {
> > -			tepp = &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;
> > -		}
> > -
> > -		tep->mcte_next = *tepp;
> > +		__set_bit(i, mctctl.mctc_free);
> > +		tep->mcte_next = NULL;
> >  		tep->mcte_prev = NULL;
> > -		*tepp = tep;
> >  	}
> >  }
> >  
> > @@ -310,32 +296,25 @@ static int mctelem_drop_count;
> >  
> >  /* 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;
> > -	mctelem_class_t target = (which == MC_URGENT) ?
> > -	    MC_URGENT : MC_NONURGENT;
> > +	unsigned bit;
> > +	unsigned start_bit = (which == MC_URGENT) ? 0 : MC_URGENT_NENT;
> >  
> > -	freelp = &mctctl.mctc_free[target];
> >  	for (;;) {
> > -		if ((oldhead = *freelp) == NULL) {
> > -			if (which == MC_URGENT && target == MC_URGENT) {
> > -				/* raid the non-urgent freelist */
> > -				target = MC_NONURGENT;
> > -				freelp = &mctctl.mctc_free[target];
> > -				continue;
> > -			} else {
> > -				mctelem_drop_count++;
> > -				return (NULL);
> > -			}
> > +		bit = find_next_bit(mctctl.mctc_free, MC_NENT, start_bit);
> > +
> > +		if (bit >= MC_NENT) {
> > +			mctelem_drop_count++;
> > +			return (NULL);
> >  		}
> >  
> > -		newhead = oldhead->mcte_next;
> > -		if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
> > -			struct mctelem_ent *tep = oldhead;
> > +		/* try to allocate, atomically clear free bit */
> > +		if (test_and_clear_bit(bit, mctctl.mctc_free)) {
> > +			/* return element we got */
> > +			struct mctelem_ent *tep = mctctl.mctc_elems + bit;
> >  
> >  			mctelem_hold(tep);
> >  			MCTE_TRANSITION_STATE(tep, FREE, UNCOMMITTED);

Re: [PATCH v2] MCE: Fix race condition in mctelem_reserve

[Jan Beulich]

>>> On 14.02.14 at 17:23, Frediano Ziglio <frediano.ziglio@citrix.com> wrote:
> Ping

And this is clearly not the first ping. Guys - you had over 3 weeks time
to respond to this. Please!

Jan

> On Fri, 2014-01-31 at 13:37 +0000, Frediano Ziglio wrote:
>> Ping
>> 
>> On Wed, 2014-01-22 at 17:17 +0000, Frediano Ziglio wrote:
>> > From 49b37906afef0981f318064f4cb53a3602bca50a Mon Sep 17 00:00:00 2001
>> > From: Frediano Ziglio <frediano.ziglio@citrix.com>
>> > Date: Wed, 22 Jan 2014 10:48:50 +0000
>> > Subject: [PATCH] MCE: Fix race condition in mctelem_reserve
>> > MIME-Version: 1.0
>> > Content-Type: text/plain; charset=UTF-8
>> > Content-Transfer-Encoding: 8bit
>> > 
>> > These lines (in mctelem_reserve)
>> > 
>> >         newhead = oldhead->mcte_next;
>> >         if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
>> > 
>> > are racy. After you read the newhead pointer it can happen that another
>> > flow (thread or recursive invocation) change all the list but set head
>> > with same value. So oldhead is the same as *freelp but you are setting
>> > a new head that could point to whatever element (even already used).
>> > 
>> > This patch use instead a bit array and atomic bit operations.
>> > 
>> > Signed-off-by: Frediano Ziglio <frediano.ziglio@citrix.com>
>> > ---
>> >  xen/arch/x86/cpu/mcheck/mctelem.c |   81 
> ++++++++++++++-----------------------
>> >  1 file changed, 30 insertions(+), 51 deletions(-)
>> > 
>> > Changes from v1:
>> > - Use bitmap to allow any number of items to be used;
>> > - Use a single bitmap to simplify reserve loop;
>> > - Remove HOME flags as was not used anymore.
>> > 
>> > diff --git a/xen/arch/x86/cpu/mcheck/mctelem.c 
> b/xen/arch/x86/cpu/mcheck/mctelem.c
>> > index 895ce1a..ed8e8d2 100644
>> > --- a/xen/arch/x86/cpu/mcheck/mctelem.c
>> > +++ b/xen/arch/x86/cpu/mcheck/mctelem.c
>> > @@ -37,24 +37,19 @@ struct mctelem_ent {
>> >  	void *mcte_data;		/* corresponding data payload */
>> >  };
>> >  
>> > -#define	MCTE_F_HOME_URGENT		0x0001U	/* free to urgent freelist */
>> > -#define	MCTE_F_HOME_NONURGENT		0x0002U /* free to nonurgent freelist */
>> > -#define	MCTE_F_CLASS_URGENT		0x0004U /* in use - urgent errors */
>> > -#define	MCTE_F_CLASS_NONURGENT		0x0008U /* in use - nonurgent errors */
>> > +#define	MCTE_F_CLASS_URGENT		0x0001U /* in use - urgent errors */
>> > +#define	MCTE_F_CLASS_NONURGENT		0x0002U /* in use - nonurgent errors */
>> >  #define	MCTE_F_STATE_FREE		0x0010U	/* on a freelist */
>> >  #define	MCTE_F_STATE_UNCOMMITTED	0x0020U	/* reserved; on no list */
>> >  #define	MCTE_F_STATE_COMMITTED		0x0040U	/* on a committed list */
>> >  #define	MCTE_F_STATE_PROCESSING		0x0080U	/* on a processing list */
>> >  
>> > -#define	MCTE_F_MASK_HOME	(MCTE_F_HOME_URGENT | MCTE_F_HOME_NONURGENT)
>> >  #define	MCTE_F_MASK_CLASS	(MCTE_F_CLASS_URGENT | MCTE_F_CLASS_NONURGENT)
>> >  #define	MCTE_F_MASK_STATE	(MCTE_F_STATE_FREE | \
>> >  				MCTE_F_STATE_UNCOMMITTED | \
>> >  				MCTE_F_STATE_COMMITTED | \
>> >  				MCTE_F_STATE_PROCESSING)
>> >  
>> > -#define	MCTE_HOME(tep) ((tep)->mcte_flags & MCTE_F_MASK_HOME)
>> > -
>> >  #define	MCTE_CLASS(tep) ((tep)->mcte_flags & MCTE_F_MASK_CLASS)
>> >  #define	MCTE_SET_CLASS(tep, new) do { \
>> >      (tep)->mcte_flags &= ~MCTE_F_MASK_CLASS; \
>> > @@ -69,6 +64,8 @@ struct mctelem_ent {
>> >  #define	MC_URGENT_NENT		10
>> >  #define	MC_NONURGENT_NENT	20
>> >  
>> > +#define MC_NENT (MC_URGENT_NENT + MC_NONURGENT_NENT)
>> > +
>> >  #define	MC_NCLASSES		(MC_NONURGENT + 1)
>> >  
>> >  #define	COOKIE2MCTE(c)		((struct mctelem_ent *)(c))
>> > @@ -77,11 +74,9 @@ struct mctelem_ent {
>> >  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 +96,7 @@ static struct mc_telem_ctl {
>> >  	 * 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];
>> > +	DECLARE_BITMAP(mctc_free, MC_NENT);
>> >  	struct mctelem_ent *mctc_committed[MC_NCLASSES];
>> >  	struct mctelem_ent *mctc_processing_head[MC_NCLASSES];
>> >  	struct mctelem_ent *mctc_processing_tail[MC_NCLASSES];
>> > @@ -207,14 +202,14 @@ int mctelem_has_deferred(unsigned int cpu)
>> >   */
>> >  static void mctelem_free(struct mctelem_ent *tep)
>> >  {
>> > -	mctelem_class_t target = MCTE_HOME(tep) == MCTE_F_HOME_URGENT ?
>> > -	    MC_URGENT : MC_NONURGENT;
>> > -
>> >  	BUG_ON(tep->mcte_refcnt != 0);
>> >  	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);
>> >  }
>> >  
>> >  /* Increment the reference count of an entry that is not linked on to
>> > @@ -274,34 +269,25 @@ void mctelem_init(int reqdatasz)
>> >  	}
>> >  
>> >  	if ((mctctl.mctc_elems = xmalloc_array(struct mctelem_ent,
>> > -	    MC_URGENT_NENT + MC_NONURGENT_NENT)) == NULL ||
>> > -	    (datarr = xmalloc_bytes((MC_URGENT_NENT + MC_NONURGENT_NENT) *
>> > -	    datasz)) == NULL) {
>> > +	    MC_NENT)) == NULL ||
>> > +	    (datarr = xmalloc_bytes(MC_NENT * datasz)) == NULL) {
>> >  		if (mctctl.mctc_elems)
>> >  			xfree(mctctl.mctc_elems);
>> >  		printk("Allocations for MCA telemetry failed\n");
>> >  		return;
>> >  	}
>> >  
>> > -	for (i = 0; i < MC_URGENT_NENT + MC_NONURGENT_NENT; i++) {
>> > -		struct mctelem_ent *tep, **tepp;
>> > +	for (i = 0; i < MC_NENT; i++) {
>> > +		struct mctelem_ent *tep;
>> >  
>> >  		tep = mctctl.mctc_elems + i;
>> >  		tep->mcte_flags = MCTE_F_STATE_FREE;
>> >  		tep->mcte_refcnt = 0;
>> >  		tep->mcte_data = datarr + i * datasz;
>> >  
>> > -		if (i < MC_URGENT_NENT) {
>> > -			tepp = &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;
>> > -		}
>> > -
>> > -		tep->mcte_next = *tepp;
>> > +		__set_bit(i, mctctl.mctc_free);
>> > +		tep->mcte_next = NULL;
>> >  		tep->mcte_prev = NULL;
>> > -		*tepp = tep;
>> >  	}
>> >  }
>> >  
>> > @@ -310,32 +296,25 @@ static int mctelem_drop_count;
>> >  
>> >  /* 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;
>> > -	mctelem_class_t target = (which == MC_URGENT) ?
>> > -	    MC_URGENT : MC_NONURGENT;
>> > +	unsigned bit;
>> > +	unsigned start_bit = (which == MC_URGENT) ? 0 : MC_URGENT_NENT;
>> >  
>> > -	freelp = &mctctl.mctc_free[target];
>> >  	for (;;) {
>> > -		if ((oldhead = *freelp) == NULL) {
>> > -			if (which == MC_URGENT && target == MC_URGENT) {
>> > -				/* raid the non-urgent freelist */
>> > -				target = MC_NONURGENT;
>> > -				freelp = &mctctl.mctc_free[target];
>> > -				continue;
>> > -			} else {
>> > -				mctelem_drop_count++;
>> > -				return (NULL);
>> > -			}
>> > +		bit = find_next_bit(mctctl.mctc_free, MC_NENT, start_bit);
>> > +
>> > +		if (bit >= MC_NENT) {
>> > +			mctelem_drop_count++;
>> > +			return (NULL);
>> >  		}
>> >  
>> > -		newhead = oldhead->mcte_next;
>> > -		if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
>> > -			struct mctelem_ent *tep = oldhead;
>> > +		/* try to allocate, atomically clear free bit */
>> > +		if (test_and_clear_bit(bit, mctctl.mctc_free)) {
>> > +			/* return element we got */
>> > +			struct mctelem_ent *tep = mctctl.mctc_elems + bit;
>> >  
>> >  			mctelem_hold(tep);
>> >  			MCTE_TRANSITION_STATE(tep, FREE, UNCOMMITTED);

Re: [PATCH v2] MCE: Fix race condition in mctelem_reserve

[Liu, Jinsong]

Sorry, I just return from long Chinese Spring Festival vacation. I will review it ASAP.

Thanks,
Jinsong

Jan Beulich wrote:
>>>> On 14.02.14 at 17:23, Frediano Ziglio <frediano.ziglio@citrix.com>
>>>> wrote: Ping 
> 
> And this is clearly not the first ping. Guys - you had over 3 weeks
> time to respond to this. Please!
> 
> Jan
> 
>> On Fri, 2014-01-31 at 13:37 +0000, Frediano Ziglio wrote:
>>> Ping
>>> 
>>> On Wed, 2014-01-22 at 17:17 +0000, Frediano Ziglio wrote:
>>>> From 49b37906afef0981f318064f4cb53a3602bca50a Mon Sep 17 00:00:00
>>>> 2001 From: Frediano Ziglio <frediano.ziglio@citrix.com>
>>>> Date: Wed, 22 Jan 2014 10:48:50 +0000
>>>> Subject: [PATCH] MCE: Fix race condition in mctelem_reserve
>>>> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8
>>>> Content-Transfer-Encoding: 8bit
>>>> 
>>>> These lines (in mctelem_reserve)
>>>> 
>>>>         newhead = oldhead->mcte_next;
>>>>         if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
>>>> 
>>>> are racy. After you read the newhead pointer it can happen that
>>>> another flow (thread or recursive invocation) change all the list
>>>> but set head with same value. So oldhead is the same as *freelp
>>>> but you are setting 
>>>> a new head that could point to whatever element (even already
>>>> used). 
>>>> 
>>>> This patch use instead a bit array and atomic bit operations.
>>>> 
>>>> Signed-off-by: Frediano Ziglio <frediano.ziglio@citrix.com> ---
>>>>  xen/arch/x86/cpu/mcheck/mctelem.c |   81
>> ++++++++++++++-----------------------
>>>>  1 file changed, 30 insertions(+), 51 deletions(-)
>>>> 
>>>> Changes from v1:
>>>> - Use bitmap to allow any number of items to be used;
>>>> - Use a single bitmap to simplify reserve loop;
>>>> - Remove HOME flags as was not used anymore.
>>>> 
>>>> diff --git a/xen/arch/x86/cpu/mcheck/mctelem.c
>> b/xen/arch/x86/cpu/mcheck/mctelem.c
>>>> index 895ce1a..ed8e8d2 100644
>>>> --- a/xen/arch/x86/cpu/mcheck/mctelem.c
>>>> +++ b/xen/arch/x86/cpu/mcheck/mctelem.c
>>>> @@ -37,24 +37,19 @@ struct mctelem_ent {
>>>>  	void *mcte_data;		/* corresponding data payload */  };
>>>> 
>>>> -#define	MCTE_F_HOME_URGENT		0x0001U	/* free to urgent freelist */
>>>> -#define	MCTE_F_HOME_NONURGENT		0x0002U /* free to nonurgent
>>>> freelist */ 
>>>> -#define	MCTE_F_CLASS_URGENT		0x0004U /* in use - urgent errors */
>>>> -#define	MCTE_F_CLASS_NONURGENT		0x0008U /* in use - nonurgent
>>>> errors */ +#define	MCTE_F_CLASS_URGENT		0x0001U /* in use - urgent
>>>> errors */ +#define	MCTE_F_CLASS_NONURGENT		0x0002U /* in use -
>>>>  nonurgent errors */ #define	MCTE_F_STATE_FREE		0x0010U	/* on a
>>>>  freelist */ #define	MCTE_F_STATE_UNCOMMITTED	0x0020U	/* reserved;
>>>>  on no list */ #define	MCTE_F_STATE_COMMITTED		0x0040U	/* on a
>>>>  committed list */ #define	MCTE_F_STATE_PROCESSING		0x0080U	/* on
>>>> a processing list */ 
>>>> 
>>>> -#define	MCTE_F_MASK_HOME	(MCTE_F_HOME_URGENT |
>>>>  MCTE_F_HOME_NONURGENT)
>>>>  #define	MCTE_F_MASK_CLASS	(MCTE_F_CLASS_URGENT |
>>>>  				MCTE_F_CLASS_NONURGENT)
>>>>  				#define	MCTE_F_MASK_STATE	(MCTE_F_STATE_FREE | \
>>>>  				MCTE_F_STATE_UNCOMMITTED | \ MCTE_F_STATE_COMMITTED | \
>>>> MCTE_F_STATE_PROCESSING) 
>>>> 
>>>> -#define	MCTE_HOME(tep) ((tep)->mcte_flags & MCTE_F_MASK_HOME) -
>>>>  #define	MCTE_CLASS(tep) ((tep)->mcte_flags & MCTE_F_MASK_CLASS)
>>>>  #define	MCTE_SET_CLASS(tep, new) do { \
>>>>      (tep)->mcte_flags &= ~MCTE_F_MASK_CLASS; \
>>>> @@ -69,6 +64,8 @@ struct mctelem_ent {
>>>>  #define	MC_URGENT_NENT		10
>>>>  #define	MC_NONURGENT_NENT	20
>>>> 
>>>> +#define MC_NENT (MC_URGENT_NENT + MC_NONURGENT_NENT) +
>>>>  #define	MC_NCLASSES		(MC_NONURGENT + 1)
>>>> 
>>>>  #define	COOKIE2MCTE(c)		((struct mctelem_ent *)(c))
>>>> @@ -77,11 +74,9 @@ struct mctelem_ent {
>>>>  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 +96,7 @@ static struct mc_telem_ctl {
>>>>  	 * 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];
>>>> +	DECLARE_BITMAP(mctc_free, MC_NENT);
>>>>  	struct mctelem_ent *mctc_committed[MC_NCLASSES];
>>>>  	struct mctelem_ent *mctc_processing_head[MC_NCLASSES];
>>>>  	struct mctelem_ent *mctc_processing_tail[MC_NCLASSES];
>>>> @@ -207,14 +202,14 @@ int mctelem_has_deferred(unsigned int cpu)  
>>>>  */ static void mctelem_free(struct mctelem_ent *tep)
>>>>  {
>>>> -	mctelem_class_t target = MCTE_HOME(tep) == MCTE_F_HOME_URGENT ?
>>>> -	    MC_URGENT : MC_NONURGENT;
>>>> -
>>>>  	BUG_ON(tep->mcte_refcnt != 0);
>>>>  	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);  }
>>>> 
>>>>  /* Increment the reference count of an entry that is not linked
>>>> on to @@ -274,34 +269,25 @@ void mctelem_init(int reqdatasz)  	}
>>>> 
>>>>  	if ((mctctl.mctc_elems = xmalloc_array(struct mctelem_ent,
>>>> -	    MC_URGENT_NENT + MC_NONURGENT_NENT)) == NULL ||
>>>> -	    (datarr = xmalloc_bytes((MC_URGENT_NENT + MC_NONURGENT_NENT)
>>>> * 
>>>> -	    datasz)) == NULL) {
>>>> +	    MC_NENT)) == NULL ||
>>>> +	    (datarr = xmalloc_bytes(MC_NENT * datasz)) == NULL) {  		if
>>>>  			(mctctl.mctc_elems) xfree(mctctl.mctc_elems);
>>>>  		printk("Allocations for MCA telemetry failed\n");  		return;
>>>>  	}
>>>> 
>>>> -	for (i = 0; i < MC_URGENT_NENT + MC_NONURGENT_NENT; i++) {
>>>> -		struct mctelem_ent *tep, **tepp;
>>>> +	for (i = 0; i < MC_NENT; i++) {
>>>> +		struct mctelem_ent *tep;
>>>> 
>>>>  		tep = mctctl.mctc_elems + i;
>>>>  		tep->mcte_flags = MCTE_F_STATE_FREE;
>>>>  		tep->mcte_refcnt = 0;
>>>>  		tep->mcte_data = datarr + i * datasz;
>>>> 
>>>> -		if (i < MC_URGENT_NENT) {
>>>> -			tepp = &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;
>>>> -		}
>>>> -
>>>> -		tep->mcte_next = *tepp;
>>>> +		__set_bit(i, mctctl.mctc_free);
>>>> +		tep->mcte_next = NULL;
>>>>  		tep->mcte_prev = NULL;
>>>> -		*tepp = tep;
>>>>  	}
>>>>  }
>>>> 
>>>> @@ -310,32 +296,25 @@ static int mctelem_drop_count;
>>>> 
>>>>  /* 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;
>>>> -	mctelem_class_t target = (which == MC_URGENT) ?
>>>> -	    MC_URGENT : MC_NONURGENT;
>>>> +	unsigned bit;
>>>> +	unsigned start_bit = (which == MC_URGENT) ? 0 : MC_URGENT_NENT;
>>>> 
>>>> -	freelp = &mctctl.mctc_free[target];
>>>>  	for (;;) {
>>>> -		if ((oldhead = *freelp) == NULL) {
>>>> -			if (which == MC_URGENT && target == MC_URGENT) {
>>>> -				/* raid the non-urgent freelist */
>>>> -				target = MC_NONURGENT;
>>>> -				freelp = &mctctl.mctc_free[target];
>>>> -				continue;
>>>> -			} else {
>>>> -				mctelem_drop_count++;
>>>> -				return (NULL);
>>>> -			}
>>>> +		bit = find_next_bit(mctctl.mctc_free, MC_NENT, start_bit); +
>>>> +		if (bit >= MC_NENT) {
>>>> +			mctelem_drop_count++;
>>>> +			return (NULL);
>>>>  		}
>>>> 
>>>> -		newhead = oldhead->mcte_next;
>>>> -		if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
>>>> -			struct mctelem_ent *tep = oldhead;
>>>> +		/* try to allocate, atomically clear free bit */
>>>> +		if (test_and_clear_bit(bit, mctctl.mctc_free)) {
>>>> +			/* return element we got */
>>>> +			struct mctelem_ent *tep = mctctl.mctc_elems + bit;
>>>> 
>>>>  			mctelem_hold(tep);
>>>>  			MCTE_TRANSITION_STATE(tep, FREE, UNCOMMITTED);

Re: [PATCH] MCE: Fix race condition in mctelem_reserve

[Liu, Jinsong]

This logic (mctelem) is related to dom0 mcelog logic. Have you tested if mcelog works fine with your patch?

Thanks,
Jinsong

Frediano Ziglio wrote:
> These lines (in mctelem_reserve)
> 
> 
>         newhead = oldhead->mcte_next;
>         if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
> 
> are racy. After you read the newhead pointer it can happen that
> another 
> flow (thread or recursive invocation) change all the list but set head
> with same value. So oldhead is the same as *freelp but you are setting
> a new head that could point to whatever element (even already used).
> 
> This patch use instead a bit array and atomic bit operations.
> 
> Actually it use unsigned long instead of bitmap type as testing for
> all zeroes is easier.
> 
> Signed-off-by: Frediano Ziglio <frediano.ziglio@citrix.com>
> ---
>  xen/arch/x86/cpu/mcheck/mctelem.c |   52
>  ++++++++++++++++++++++--------------- 1 file changed, 31
> insertions(+), 21 deletions(-) 
> 
> diff --git a/xen/arch/x86/cpu/mcheck/mctelem.c
> b/xen/arch/x86/cpu/mcheck/mctelem.c index 895ce1a..e56b6fb 100644
> --- a/xen/arch/x86/cpu/mcheck/mctelem.c
> +++ b/xen/arch/x86/cpu/mcheck/mctelem.c
> @@ -69,6 +69,11 @@ struct mctelem_ent {
>  #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 @@ struct mctelem_ent {
>  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 @@ static struct mc_telem_ctl {
>  	 * 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 @@ static void mctelem_free(struct mctelem_ent *tep)
>  	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 @@ void mctelem_init(int reqdatasz)
>  	}
> 
>  	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 @@ void mctelem_init(int reqdatasz)
>  		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 @@ static int mctelem_drop_count;
> 
>  /* 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 @@ mctelem_cookie_t mctelem_reserve(mctelem_class_t
>  			which) }
>  		}
> 
> -		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);

Re: [PATCH] MCE: Fix race condition in mctelem_reserve

[Frediano Ziglio]

Yes,
  all these patches came from some customer reports. We manage with
xen-mceinj to reproduce the problem and got these types of races. These
patches (the other one is already applied) fix the race issues we found.

I tested with a CentOS 6.4 version with mcelog.

Frediano

On Tue, 2014-02-18 at 08:42 +0000, Liu, Jinsong wrote:
> This logic (mctelem) is related to dom0 mcelog logic. Have you tested if mcelog works fine with your patch?
> 
> Thanks,
> Jinsong
> 
> Frediano Ziglio wrote:
> > These lines (in mctelem_reserve)
> > 
> > 
> >         newhead = oldhead->mcte_next;
> >         if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
> > 
> > are racy. After you read the newhead pointer it can happen that
> > another 
> > flow (thread or recursive invocation) change all the list but set head
> > with same value. So oldhead is the same as *freelp but you are setting
> > a new head that could point to whatever element (even already used).
> > 
> > This patch use instead a bit array and atomic bit operations.
> > 
> > Actually it use unsigned long instead of bitmap type as testing for
> > all zeroes is easier.
> > 
> > Signed-off-by: Frediano Ziglio <frediano.ziglio@citrix.com>
> > ---
> >  xen/arch/x86/cpu/mcheck/mctelem.c |   52
> >  ++++++++++++++++++++++--------------- 1 file changed, 31
> > insertions(+), 21 deletions(-) 
> > 
> > diff --git a/xen/arch/x86/cpu/mcheck/mctelem.c
> > b/xen/arch/x86/cpu/mcheck/mctelem.c index 895ce1a..e56b6fb 100644
> > --- a/xen/arch/x86/cpu/mcheck/mctelem.c
> > +++ b/xen/arch/x86/cpu/mcheck/mctelem.c
> > @@ -69,6 +69,11 @@ struct mctelem_ent {
> >  #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 @@ struct mctelem_ent {
> >  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 @@ static struct mc_telem_ctl {
> >  	 * 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 @@ static void mctelem_free(struct mctelem_ent *tep)
> >  	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 @@ void mctelem_init(int reqdatasz)
> >  	}
> > 
> >  	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 @@ void mctelem_init(int reqdatasz)
> >  		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 @@ static int mctelem_drop_count;
> > 
> >  /* 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 @@ mctelem_cookie_t mctelem_reserve(mctelem_class_t
> >  			which) }
> >  		}
> > 
> > -		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);
> 

Re: [PATCH] MCE: Fix race condition in mctelem_reserve

[Liu, Jinsong]

Thanks!

Reviewed-by: Liu Jinsong <jinsong.liu@intel.com>


Frediano Ziglio wrote:
> Yes,
>   all these patches came from some customer reports. We manage with
> xen-mceinj to reproduce the problem and got these types of races.
> These patches (the other one is already applied) fix the race issues
> we found. 
> 
> I tested with a CentOS 6.4 version with mcelog.
> 
> Frediano
> 
> On Tue, 2014-02-18 at 08:42 +0000, Liu, Jinsong wrote:
>> This logic (mctelem) is related to dom0 mcelog logic. Have you
>> tested if mcelog works fine with your patch? 
>> 
>> Thanks,
>> Jinsong
>> 
>> Frediano Ziglio wrote:
>>> These lines (in mctelem_reserve)
>>> 
>>> 
>>>         newhead = oldhead->mcte_next;
>>>         if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
>>> 
>>> are racy. After you read the newhead pointer it can happen that
>>> another flow (thread or recursive invocation) change all the list
>>> but set head with same value. So oldhead is the same as *freelp but
>>> you are setting a new head that could point to whatever element
>>> (even already used). 
>>> 
>>> This patch use instead a bit array and atomic bit operations.
>>> 
>>> Actually it use unsigned long instead of bitmap type as testing for
>>> all zeroes is easier. 
>>> 
>>> Signed-off-by: Frediano Ziglio <frediano.ziglio@citrix.com> ---
>>>  xen/arch/x86/cpu/mcheck/mctelem.c |   52
>>>  ++++++++++++++++++++++--------------- 1 file changed, 31
>>> insertions(+), 21 deletions(-)
>>> 
>>> diff --git a/xen/arch/x86/cpu/mcheck/mctelem.c
>>> b/xen/arch/x86/cpu/mcheck/mctelem.c index 895ce1a..e56b6fb 100644
>>> --- a/xen/arch/x86/cpu/mcheck/mctelem.c
>>> +++ b/xen/arch/x86/cpu/mcheck/mctelem.c
>>> @@ -69,6 +69,11 @@ struct mctelem_ent {
>>>  #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 @@ struct mctelem_ent {
>>>  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 @@ static struct mc_telem_ctl {
>>>  	 * 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 @@ static void mctelem_free(struct mctelem_ent
>>>  	*tep) 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 @@ void mctelem_init(int reqdatasz)  	}
>>> 
>>>  	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 @@ void mctelem_init(int reqdatasz)
>>>  		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 @@ static int mctelem_drop_count;
>>> 
>>>  /* 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 @@ mctelem_cookie_t
>>>  		mctelem_reserve(mctelem_class_t  			which) } }
>>> 
>>> -		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);

Re: [PATCH v2] MCE: Fix race condition in mctelem_reserve

[George Dunlap]

On Wed, Jan 22, 2014 at 5:17 PM, Frediano Ziglio
<frediano.ziglio@citrix.com> wrote:
> From 49b37906afef0981f318064f4cb53a3602bca50a Mon Sep 17 00:00:00 2001
> From: Frediano Ziglio <frediano.ziglio@citrix.com>
> Date: Wed, 22 Jan 2014 10:48:50 +0000
> Subject: [PATCH] MCE: Fix race condition in mctelem_reserve
> MIME-Version: 1.0
> Content-Type: text/plain; charset=UTF-8
> Content-Transfer-Encoding: 8bit
>
> These lines (in mctelem_reserve)
>
>         newhead = oldhead->mcte_next;
>         if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
>
> are racy. After you read the newhead pointer it can happen that another
> flow (thread or recursive invocation) change all the list but set head
> with same value. So oldhead is the same as *freelp but you are setting
> a new head that could point to whatever element (even already used).
>
> This patch use instead a bit array and atomic bit operations.
>
> Signed-off-by: Frediano Ziglio <frediano.ziglio@citrix.com>

What is this like from a release perspective?  When is this code run,
and how often is the bug triggered?

 -George

Re: [PATCH v2] MCE: Fix race condition in mctelem_reserve

[Frediano Ziglio]

On Tue, 2014-02-18 at 12:47 +0000, George Dunlap wrote:
> On Wed, Jan 22, 2014 at 5:17 PM, Frediano Ziglio
> <frediano.ziglio@citrix.com> wrote:
> >
> > These lines (in mctelem_reserve)
> >
> >         newhead = oldhead->mcte_next;
> >         if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
> >
> > are racy. After you read the newhead pointer it can happen that another
> > flow (thread or recursive invocation) change all the list but set head
> > with same value. So oldhead is the same as *freelp but you are setting
> > a new head that could point to whatever element (even already used).
> >
> > This patch use instead a bit array and atomic bit operations.
> >
> > Signed-off-by: Frediano Ziglio <frediano.ziglio@citrix.com>
> 
> What is this like from a release perspective?  When is this code run,
> and how often is the bug triggered?
> 
>  -George

The code handle MCE situation. So if your hardware is good is not a big
deal. If your hardware start to have some problems in some situation is
possible that cpu raise a mce quite often causing the race to happen.

I think that the probability is not that high. The test was finely
tested (not that easy to do even now) and solve a real bug.

Frediano

Re: [PATCH v2] MCE: Fix race condition in mctelem_reserve

[George Dunlap]

On 02/19/2014 09:53 AM, Frediano Ziglio wrote:
> On Tue, 2014-02-18 at 12:47 +0000, George Dunlap wrote:
>> On Wed, Jan 22, 2014 at 5:17 PM, Frediano Ziglio
>> <frediano.ziglio@citrix.com> wrote:
>>> These lines (in mctelem_reserve)
>>>
>>>          newhead = oldhead->mcte_next;
>>>          if (cmpxchgptr(freelp, oldhead, newhead) == oldhead) {
>>>
>>> are racy. After you read the newhead pointer it can happen that another
>>> flow (thread or recursive invocation) change all the list but set head
>>> with same value. So oldhead is the same as *freelp but you are setting
>>> a new head that could point to whatever element (even already used).
>>>
>>> This patch use instead a bit array and atomic bit operations.
>>>
>>> Signed-off-by: Frediano Ziglio <frediano.ziglio@citrix.com>
>> What is this like from a release perspective?  When is this code run,
>> and how often is the bug triggered?
>>
>>   -George
> The code handle MCE situation. So if your hardware is good is not a big
> deal. If your hardware start to have some problems in some situation is
> possible that cpu raise a mce quite often causing the race to happen.
>
> I think that the probability is not that high. The test was finely
> tested (not that easy to do even now) and solve a real bug.

OK thanks -- at this point then, I think I'd just as soon hold this off 
until 4.4.1, unless we get some other blocking bugs, just so that we can 
minimize the changes.

  -George