Skip to contentSkip to conversation

xmalloc patches

PATCH Superseded Paul Durrant 2 participants 10 messages Jul 2, 2019 – Jul 3, 2019

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

cover xmalloc patches

These are patches that stem from debugging the problem that led to commit 56ad6265 "x86/msi: fix loop termination condition in pci_msi_conf_write_intercept()".

Paul Durrant (3):
xmalloc: stop using a magic '1' in alignment padding
xmalloc: don't evaluate ADD_REGION without holding the pool lock
xmalloc: add a Kconfig option to poison free pool memory

 xen/Kconfig.debug         |  7 +++++++
 xen/common/xmalloc_tlsf.c | 29 +++++++++++++++++++++++------
 2 files changed, 30 insertions(+), 6 deletions(-)

---
Cc: Andrew Cooper <[email protected]>
Cc: George Dunlap <[email protected]>
Cc: Ian Jackson <[email protected]>
Cc: Jan Beulich <[email protected]>
Cc: Julien Grall <[email protected]>
Cc: Konrad Rzeszutek Wilk <[email protected]>
Cc: Stefano Stabellini <[email protected]>
Cc: Tim Deegan <[email protected]>
Cc: Wei Liu <[email protected]>

Signature · 7 lines
2.20.1.2.gb21ebb671


_______________________________________________
Xen-devel mailing list
[email protected]
https://lists.xenproject.org/mailman/listinfo/xen-devel
#1 lore raw

PATCH 1/3 xmalloc: stop using a magic '1' in alignment padding

Alignment padding inserts a pseudo block header in front of the allocation, sets its size field to the pad size and then ORs in 1, which is equivalent to marking it as a free block, so that xfree() can distinguish it from a real block header.

This patch simply replaces the magic '1' with the defined 'FREE_BLOCK' to make it more obvious what's going on. Also, whilst in the neighbourhood, it removes a stray space after a cast.

---
Cc: Andrew Cooper <[email protected]>
Cc: George Dunlap <[email protected]>
Cc: Ian Jackson <[email protected]>
Cc: Jan Beulich <[email protected]>
Cc: Julien Grall <[email protected]>
Cc: Konrad Rzeszutek Wilk <[email protected]>
Cc: Stefano Stabellini <[email protected]>
Cc: Tim Deegan <[email protected]>
Cc: Wei Liu <[email protected]>

---
 xen/common/xmalloc_tlsf.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
xen/common/xmalloc_tlsf.c +4 -4
index 2076953ac4..6d889b7bdc 100644
@@ -595,7 +595,7 @@ void *_xmalloc(unsigned long size, unsigned long align)
         char *q = (char *)p + pad;
         struct bhdr *b = (struct bhdr *)(q - BHDR_OVERHEAD);
         ASSERT(q > (char *)p);
-        b->size = pad | 1;
+        b->size = pad | FREE_BLOCK;
         p = q;
     }
 
@@ -638,12 +638,12 @@ void xfree(void *p)
     }
 
     /* Strip alignment padding. */
-    b = (struct bhdr *)((char *) p - BHDR_OVERHEAD);
-    if ( b->size & 1 )
+    b = (struct bhdr *)((char *)p - BHDR_OVERHEAD);
+    if ( b->size & FREE_BLOCK )
     {
         p = (char *)p - (b->size & ~1u);
         b = (struct bhdr *)((char *)p - BHDR_OVERHEAD);
-        ASSERT(!(b->size & 1));
+        ASSERT(!(b->size & FREE_BLOCK));
     }
 
     xmem_pool_free(p, xenpool);
Signature · 7 lines
2.20.1.2.gb21ebb671


_______________________________________________
Xen-devel mailing list
[email protected]
https://lists.xenproject.org/mailman/listinfo/xen-devel
Reviewed-by on v1 1/3
#2 lore raw

Re: [Xen-devel] [PATCH 1/3] xmalloc: stop using a magic '1' in alignment padding

Quoted 7 lines · Paul Durrant

Alignment padding inserts a pseudo block header in front of the allocation, sets its size field to the pad size and then ORs in 1, which is equivalent to marking it as a free block, so that xfree() can distinguish it from a real block header.

This patch simply replaces the magic '1' with the defined 'FREE_BLOCK' to make it more obvious what's going on.

Hmm, that's still an abuse of some sort, I think. FREE_BLOCK (together with USED_BLOCK, PREV_FREE, and PREV_USED) serve block splitting and re-combination, which isn't strictly the case here. But yes, I guess (ab)using the manifest constants is still better than (ab)using the literal numbers.

Quoted 1 line

Also, whilst in the neighbourhood, it removes a stray space after a cast.

An option would have been to drop the cast altogether. The code here appears to assume that void pointer arithmetic is not allowed (as is indeed the case in plain C).

Quoted 1 line

with one further adjustment:

xen/common/xmalloc_tlsf.c void xfree(void *p) · line 644

Quoted 10 lines
xen/common/xmalloc_tlsf.c +2 -2
@@ -638,12 +638,12 @@ void xfree(void *p)
      }
 
      /* Strip alignment padding. */
-    b = (struct bhdr *)((char *) p - BHDR_OVERHEAD);
-    if ( b->size & 1 )
+    b = (struct bhdr *)((char *)p - BHDR_OVERHEAD);
+    if ( b->size & FREE_BLOCK )
      {
          p = (char *)p - (b->size & ~1u);

This ~1u also wants to become ~FREE_BLOCK then. I guess the change is easy enough to make while committing; I don't expect the loss of the u suffix to actually cause any problems. In fact its presence was not a problem only because ->size can't get very large and is of u32 type.

Jan
_______________________________________________
Xen-devel mailing list
[email protected]
https://lists.xenproject.org/mailman/listinfo/xen-devel

#3 lore raw

Re: [Xen-devel] [PATCH 1/3] xmalloc: stop using a magic '1' in alignment padding

Quoted 25 lines

-----Original Message-----
From: Jan Beulich <[email protected]>
Sent: 03 July 2019 10:39
To: Paul Durrant <[email protected]>; [email protected]
Cc: Julien Grall <[email protected]>; Andrew Cooper <[email protected]>; George Dunlap <[email protected]>; Ian Jackson <[email protected]>; Stefano Stabellini <[email protected]>; Konrad Rzeszutek Wilk <[email protected]>; Tim (Xen.org) <[email protected]>; Wei Liu <[email protected]>
Subject: Re: [PATCH 1/3] xmalloc: stop using a magic '1' in alignment padding

Quoted 7 lines · Paul Durrant

Alignment padding inserts a pseudo block header in front of the allocation, sets its size field to the pad size and then ORs in 1, which is equivalent to marking it as a free block, so that xfree() can distinguish it from a real block header.

This patch simply replaces the magic '1' with the defined 'FREE_BLOCK' to make it more obvious what's going on.

Hmm, that's still an abuse of some sort, I think. FREE_BLOCK (together with USED_BLOCK, PREV_FREE, and PREV_USED) serve block splitting and re-combination, which isn't strictly the case here. But yes, I guess (ab)using the manifest constants is still better than (ab)using the literal numbers.

Quoted 6 lines
Quoted 1 line

Also, whilst in the neighbourhood, it removes a stray space after a cast.

An option would have been to drop the cast altogether. The code here appears to assume that void pointer arithmetic is not allowed (as is indeed the case in plain C).

Yes, the code is pretty ancient. There's a whole bunch of cleanup/style adjustments (e.g. u32 -> uint32_t) too. I left this one for consistency.

Quoted 3 lines
Quoted 1 line

Thanks.

Quoted 5 lines

with one further adjustment:

Quoted 3 lines
(quoted diff) +0 -0
@@ -638,12 +638,12 @@ void xfree(void *p)
      }
 
Quoted 9 lines

xen/common/xmalloc_tlsf.c void xfree(void *p) · line 644

Quoted 7 lines
xen/common/xmalloc_tlsf.c +2 -2
      /* Strip alignment padding. */
-    b = (struct bhdr *)((char *) p - BHDR_OVERHEAD);
-    if ( b->size & 1 )
+    b = (struct bhdr *)((char *)p - BHDR_OVERHEAD);
+    if ( b->size & FREE_BLOCK )
      {
          p = (char *)p - (b->size & ~1u);

This ~1u also wants to become ~FREE_BLOCK then.

Oh yes, sorry I missed that.

Quoted 6 lines

I guess the
change is easy enough to make while committing; I don't expect the loss of the u suffix to actually cause any problems. In fact its presence was not a problem only because ->size can't get very large and is of u32 type.

Yes, please go ahead and fix on commit.

Paul

Quoted 1 line

Jan

_______________________________________________
Xen-devel mailing list
[email protected]
https://lists.xenproject.org/mailman/listinfo/xen-devel

#4 lore raw

PATCH 2/3 xmalloc: don't evaluate ADD_REGION without holding the pool lock

In reply to Paul Durrant

It's not safe to add a region without holding the lock, but this is exactly what may happen if two threads race entering xmem_pool_alloc() before the init_region is set.

This patch instead checks for init_region under lock, drops the lock if it needs to allocate a page, takes the lock, adds the region and then confirms init_region is still unset before pointing it at the newly added region. Thus, it is possible that a race may cause an extra region to be added, but there will be no pool metadata corruption.

---
Cc: Andrew Cooper <[email protected]>
Cc: George Dunlap <[email protected]>
Cc: Ian Jackson <[email protected]>
Cc: Jan Beulich <[email protected]>
Cc: Julien Grall <[email protected]>
Cc: Konrad Rzeszutek Wilk <[email protected]>
Cc: Stefano Stabellini <[email protected]>
Cc: Tim Deegan <[email protected]>
Cc: Wei Liu <[email protected]>

---
 xen/common/xmalloc_tlsf.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)
xen/common/xmalloc_tlsf.c +6 -2
index 6d889b7bdc..71597c3590 100644
@@ -380,18 +380,22 @@ void *xmem_pool_alloc(unsigned long size, struct xmem_pool *pool)
     int fl, sl;
     unsigned long tmp_size;
 
+    spin_lock(&pool->lock);
     if ( pool->init_region == NULL )
     {
+        spin_unlock(&pool->lock);
         if ( (region = pool->get_mem(pool->init_size)) == NULL )
             goto out;
+        spin_lock(&pool->lock);
         ADD_REGION(region, pool->init_size, pool);
-        pool->init_region = region;
+        /* Re-check since the lock was dropped */
+        if ( pool->init_region == NULL )
+            pool->init_region = region;
     }
 
     size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size);
     /* Rounding up the requested size and calculating fl and sl */
 
-    spin_lock(&pool->lock);
  retry_find:
     MAPPING_SEARCH(&size, &fl, &sl);
 
Signature · 7 lines
2.20.1.2.gb21ebb671


_______________________________________________
Xen-devel mailing list
[email protected]
https://lists.xenproject.org/mailman/listinfo/xen-devel
#5 lore raw

Re: [Xen-devel] [PATCH 2/3] xmalloc: don't evaluate ADD_REGION without holding the pool lock

Quoted 9 lines · Paul Durrant
xen/common/xmalloc_tlsf.c +1 -0
@@ -380,18 +380,22 @@ void *xmem_pool_alloc(unsigned long size, struct xmem_pool *pool)
     int fl, sl;
     unsigned long tmp_size;
 
+    spin_lock(&pool->lock);
     if ( pool->init_region == NULL )
     {

xen/common/xmalloc_tlsf.c void *xmem_pool_alloc(unsigned long size, struct xmem_pool *pool) · line 394

Quoted 10 lines
xen/common/xmalloc_tlsf.c +5 -1
+       spin_unlock(&pool->lock);
        if ( (region = pool->get_mem(pool->init_size)) == NULL )
            goto out;
+       spin_lock(&pool->lock);
        ADD_REGION(region, pool->init_size, pool);
-       pool->init_region = region;
+       /* Re-check since the lock was dropped */
+       if ( pool->init_region == NULL )
+           pool->init_region = region;
     }

Instead of this, how about deleting the init_region field? It's not really used anywhere. I'm not going to exclude that functions like FIND_SUITABLE_BLOCK() expect _some_ region to be there in the pool, but that still wouldn't require tracking which one was the first to get allocated. A check like that in xmem_pool_destroy() would then do here to make sure at least one region is there.

Jan
_______________________________________________
Xen-devel mailing list
[email protected]
https://lists.xenproject.org/mailman/listinfo/xen-devel

#6 lore raw

Re: [Xen-devel] [PATCH 2/3] xmalloc: don't evaluate ADD_REGION without holding the pool lock

Quoted 31 lines

-----Original Message-----
From: Jan Beulich <[email protected]>
Sent: 03 July 2019 10:57
To: Paul Durrant <[email protected]>
Cc: [email protected]; Julien Grall <[email protected]>; Andrew Cooper <[email protected]>; George Dunlap <[email protected]>; Ian Jackson <[email protected]>; Stefano Stabellini <[email protected]>; Konrad Rzeszutek Wilk <[email protected]>; Tim (Xen.org) <[email protected]>; Wei Liu <[email protected]>
Subject: Re: [PATCH 2/3] xmalloc: don't evaluate ADD_REGION without holding the pool lock

Quoted 9 lines · Paul Durrant
xen/common/xmalloc_tlsf.c +1 -0
@@ -380,18 +380,22 @@ void *xmem_pool_alloc(unsigned long size, struct xmem_pool *pool)
     int fl, sl;
     unsigned long tmp_size;
 
+    spin_lock(&pool->lock);
     if ( pool->init_region == NULL )
     {

xen/common/xmalloc_tlsf.c void *xmem_pool_alloc(unsigned long size, struct xmem_pool *pool) · line 394

Quoted 10 lines
xen/common/xmalloc_tlsf.c +5 -1
+       spin_unlock(&pool->lock);
        if ( (region = pool->get_mem(pool->init_size)) == NULL )
            goto out;
+       spin_lock(&pool->lock);
        ADD_REGION(region, pool->init_size, pool);
-       pool->init_region = region;
+       /* Re-check since the lock was dropped */
+       if ( pool->init_region == NULL )
+           pool->init_region = region;
     }
Quoted 8 lines

Instead of this, how about deleting the init_region field? It's not really used anywhere. I'm not going to exclude that functions like FIND_SUITABLE_BLOCK() expect _some_ region to be there in the pool, but that still wouldn't require tracking which one was the first to get allocated. A check like that in xmem_pool_destroy() would then do here to make sure at least one region is there.

Ok, I can do it that way instead... not that anything calls xmem_pool_destroy at the moment anyway.

Paul

Quoted 1 line

Jan

_______________________________________________
Xen-devel mailing list
[email protected]
https://lists.xenproject.org/mailman/listinfo/xen-devel

#7 lore raw

PATCH 3/3 xmalloc: add a Kconfig option to poison free pool memory

In reply to Paul Durrant

This patch adds POOL_POISON to the Kconfig DEBUG options. If set, free blocks (greater than MIN_BLOCK_SIZE) will be poisoned with 0xAA bytes which will then be verified when memory is subsequently allocated. This can help in spotting heap corruption, particularly use-after-free.

---
Cc: Andrew Cooper <[email protected]>
Cc: George Dunlap <[email protected]>
Cc: Ian Jackson <[email protected]>
Cc: Jan Beulich <[email protected]>
Cc: Julien Grall <[email protected]>
Cc: Konrad Rzeszutek Wilk <[email protected]>
Cc: Stefano Stabellini <[email protected]>
Cc: Tim Deegan <[email protected]>
Cc: Wei Liu <[email protected]>

---
 xen/Kconfig.debug         |  7 +++++++
 xen/common/xmalloc_tlsf.c | 13 +++++++++++++
 2 files changed, 20 insertions(+)
xen/Kconfig.debug +7 -0
index daacf85141..4f18a1144e 100644
@@ -105,6 +105,13 @@ config DEBUG_TRACE
 	  either directly to the console or are printed to console in case of
 	  a system crash.
 
+config POOL_POISON
+       bool "Poison free xenpool blocks"
+       default DEBUG
+       ---help---
+         Poison free blocks with 0xAA bytes and verify them when a block is
+	 allocated in order to spot use-after-free issues.
+
 endif # DEBUG || EXPERT
 
 endmenu
xen/common/xmalloc_tlsf.c +13 -0
index 71597c3590..a12dbc8e11 100644
@@ -223,6 +223,10 @@ static inline void EXTRACT_BLOCK_HDR(struct bhdr *b, struct xmem_pool *p, int fl
 static inline void EXTRACT_BLOCK(struct bhdr *b, struct xmem_pool *p, int fl,
                                  int sl)
 {
+#ifdef CONFIG_POOL_POISON
+    unsigned int i;
+#endif /* CONFIG_POOL_POISON */
+
     if ( b->ptr.free_ptr.next )
         b->ptr.free_ptr.next->ptr.free_ptr.prev =
             b->ptr.free_ptr.prev;
@@ -240,6 +244,10 @@ static inline void EXTRACT_BLOCK(struct bhdr *b, struct xmem_pool *p, int fl,
         }
     }
     b->ptr.free_ptr = (struct free_ptr) {NULL, NULL};
+#ifdef CONFIG_POOL_POISON
+    for ( i = MIN_BLOCK_SIZE; i < (b->size & BLOCK_SIZE_MASK); i++ )
+        ASSERT(b->ptr.buffer[i] == 0xAA);
+#endif /* CONFIG_POOL_POISON */
 }
 
 /**
@@ -247,6 +255,11 @@ static inline void EXTRACT_BLOCK(struct bhdr *b, struct xmem_pool *p, int fl,
  */
 static inline void INSERT_BLOCK(struct bhdr *b, struct xmem_pool *p, int fl, int sl)
 {
+#ifdef CONFIG_POOL_POISON
+    if ( (b->size & BLOCK_SIZE_MASK) > MIN_BLOCK_SIZE )
+        memset(b->ptr.buffer + MIN_BLOCK_SIZE, 0xAA,
+               (b->size & BLOCK_SIZE_MASK) - MIN_BLOCK_SIZE);
+#endif /* CONFIG_POOL_POISON */
     b->ptr.free_ptr = (struct free_ptr) {NULL, p->matrix[fl][sl]};
     if ( p->matrix[fl][sl] )
         p->matrix[fl][sl]->ptr.free_ptr.prev = b;
Signature · 7 lines
2.20.1.2.gb21ebb671


_______________________________________________
Xen-devel mailing list
[email protected]
https://lists.xenproject.org/mailman/listinfo/xen-devel
#8 lore raw

Re: [Xen-devel] [PATCH 3/3] xmalloc: add a Kconfig option to poison free pool memory

xen/Kconfig.debug config DEBUG_TRACE · line 108

Quoted 7 lines · Paul Durrant
xen/Kconfig.debug +1 -0
@@ -105,6 +105,13 @@ config DEBUG_TRACE
  	  either directly to the console or are printed to console in case of
  	  a system crash.
 
+config POOL_POISON

May I suggest this to become XMEM_POOL_POISON, to parallel the names of the involved functions?

xen/Kconfig.debug static inline void EXTRACT_BLOCK(struct bhdr *b, struct xmem_pool *p, int fl, · line 250

Quoted 8 lines
xen/Kconfig.debug +4 -0
@@ -240,6 +244,10 @@ static inline void EXTRACT_BLOCK(struct bhdr *b, struct xmem_pool *p, int fl,
          }
      }
      b->ptr.free_ptr = (struct free_ptr) {NULL, NULL};
+#ifdef CONFIG_POOL_POISON
+    for ( i = MIN_BLOCK_SIZE; i < (b->size & BLOCK_SIZE_MASK); i++ )
+        ASSERT(b->ptr.buffer[i] == 0xAA);
+#endif /* CONFIG_POOL_POISON */

May I further suggest that we clone Linux'es memchr_inv() for this purpose (perhaps with a more simplistic implementation along the lines of memchr())? We should then also use it in check_one_page().

Jan
_______________________________________________
Xen-devel mailing list
[email protected]
https://lists.xenproject.org/mailman/listinfo/xen-devel

#9 lore raw

Re: [Xen-devel] [PATCH 3/3] xmalloc: add a Kconfig option to poison free pool memory

Quoted 17 lines

-----Original Message-----
From: Jan Beulich <[email protected]>
Sent: 03 July 2019 11:07
To: Paul Durrant <[email protected]>
Cc: [email protected]; Julien Grall <[email protected]>; Andrew Cooper <[email protected]>; George Dunlap <[email protected]>; Ian Jackson <[email protected]>; Stefano Stabellini <[email protected]>; Konrad Rzeszutek Wilk <[email protected]>; Tim (Xen.org) <[email protected]>; Wei Liu <[email protected]>
Subject: Re: [PATCH 3/3] xmalloc: add a Kconfig option to poison free pool memory

Quoted 6 lines · Paul Durrant
xen/Kconfig.debug +0 -0
@@ -105,6 +105,13 @@ config DEBUG_TRACE
  	  either directly to the console or are printed to console in case of
  	  a system crash.
 
Quoted 5 lines

xen/Kconfig.debug config DEBUG_TRACE · line 108

Quoted 1 line
xen/Kconfig.debug +1 -0
+config POOL_POISON

May I suggest this to become XMEM_POOL_POISON, to parallel the names of the involved functions?

Sure.

Quoted 4 lines
Quoted 4 lines
xen/Kconfig.debug +0 -0
@@ -240,6 +244,10 @@ static inline void EXTRACT_BLOCK(struct bhdr *b, struct xmem_pool *p, int fl,
          }
      }
      b->ptr.free_ptr = (struct free_ptr) {NULL, NULL};
Quoted 9 lines

xen/Kconfig.debug static inline void EXTRACT_BLOCK(struct bhdr *b, struct xmem_pool *p, int fl, · line 250

Quoted 4 lines
xen/Kconfig.debug +4 -0
+#ifdef CONFIG_POOL_POISON
+    for ( i = MIN_BLOCK_SIZE; i < (b->size & BLOCK_SIZE_MASK); i++ )
+        ASSERT(b->ptr.buffer[i] == 0xAA);
+#endif /* CONFIG_POOL_POISON */

May I further suggest that we clone Linux'es memchr_inv() for this purpose (perhaps with a more simplistic implementation along the lines of memchr())? We should then also use it in check_one_page().

Yes, that sounds like a worthy thing to do.

Paul

Quoted 1 line

Jan

_______________________________________________
Xen-devel mailing list
[email protected]
https://lists.xenproject.org/mailman/listinfo/xen-devel