xmalloc patches
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
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
@@ -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
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
Signed-off-by Paul Durrant <[email protected]>
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
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 paddingQuoted 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 withUSED_BLOCK,PREV_FREE, andPREV_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
Signed-off-by Paul Durrant <[email protected]>Reviewed-by Jan Beulich <[email protected]>
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
PATCH 2/3 xmalloc: don't evaluate ADD_REGION without holding the pool lock
In reply to Paul DurrantIt'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
@@ -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
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
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 evaluateADD_REGIONwithout holding the pool lockQuoted 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_regionfield? It's not really used anywhere. I'm not going to exclude that functions likeFIND_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 inxmem_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
PATCH 3/3 xmalloc: add a Kconfig option to poison free pool memory
In reply to Paul DurrantThis 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
@@ -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
@@ -223,6 +223,10 @@ static inline void EXTRACT_BLOCK_HDR(struct bhdr *b, struct xmem_pool *p, int flstatic 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
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
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 aKconfigoption to poison free pool memoryQuoted 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_POISONMay 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 ofmemchr())? We should then also use it incheck_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