[PATCH v2 3/7] tlsf: fix sizeof(size_t) == sizeof(void *) assumption

Ahmad Fatoum a.fatoum at pengutronix.de
Mon Sep 11 08:24:29 PDT 2023


TLSF struct block_header_t doesn't describe a single block, but
instead its first member covers the previous block:

                              .~~~~~~~~~~~~~~~~~~~.
                              |  prev_phys_block  |
    End of previous block --> |———————————————————| <-- Start of a free block
                              |       size        |
                              |— — — — — — — — — —|
                              | < Start of Data > |
                              '———————————————————'

This works because if the previous block is free, there is no harm in
using its last word to store the prev_phys_block.

We thus need pointer arithmetic to:

  - arrive from start of data to size, i.e. decrement offset
    by sizeof(size_t)

  - arrive from size to prev_phys_block, i.e. decrement offset
    by sizeof(struct block_header_t *)

Across the TLSF implementation, we conflate the two though and use
block_header_shift to mean both.  This works as long as
sizeof(size_t) == sizeof(struct block_header_t *), which is true
for both 32-bit and 64-bit configuration currently.

To facilitate having an 8-byte minimum allocation alignment for 32-bit
systems as well, we will increase sizeof(struct block_header_t::size)
to 8 bytes, which will break the implicit assumption. Fix it by adding
an additional const block_header_shift and use it where appropriate.

No functional change just yet.

Signed-off-by: Ahmad Fatoum <a.fatoum at pengutronix.de>
---
 common/tlsf.c | 15 ++++++++-------
 1 file changed, 8 insertions(+), 7 deletions(-)

diff --git a/common/tlsf.c b/common/tlsf.c
index 784012a1f7ab..0986c7c457e3 100644
--- a/common/tlsf.c
+++ b/common/tlsf.c
@@ -141,10 +141,11 @@ typedef struct block_header_t
 ** The size of the block header exposed to used blocks is the size field.
 ** The prev_phys_block field is stored *inside* the previous free block.
 */
+#define block_header_shift		offsetof(block_header_t, size)
 #define block_header_overhead		sizeof(size_t)
 
 /* User data starts directly after the size field in a used block. */
-#define block_start_offset		(offsetof(block_header_t, size) + sizeof(size_t))
+#define block_start_offset		(block_header_shift + block_header_overhead)
 
 /*
 ** A free block must be large enough to store its header minus the size of
@@ -251,7 +252,7 @@ static block_header_t* block_prev(const block_header_t* block)
 static block_header_t* block_next(const block_header_t* block)
 {
 	block_header_t* next = offset_to_block(block_to_ptr(block),
-		block_size(block) - block_header_overhead);
+		block_size(block) - block_header_shift);
 	tlsf_assert(!block_is_last(block));
 	return next;
 }
@@ -462,7 +463,7 @@ static block_header_t* block_split(block_header_t* block, size_t size)
 {
 	/* Calculate the amount of space left in the remaining block. */
 	block_header_t* remaining =
-		offset_to_block(block_to_ptr(block), size - block_header_overhead);
+		offset_to_block(block_to_ptr(block), size - block_header_shift);
 
 	const size_t remain_size = block_size(block) - (size + block_header_overhead);
 
@@ -728,7 +729,7 @@ void tlsf_walk_pool(pool_t pool, tlsf_walker walker, void* user)
 {
 	tlsf_walker pool_walker = walker ? walker : default_walker;
 	block_header_t* block =
-		offset_to_block(pool, -(int)block_header_overhead);
+		offset_to_block(pool, -(int)block_header_shift);
 
 	while (block && !block_is_last(block))
 	{
@@ -834,7 +835,7 @@ pool_t tlsf_add_pool(tlsf_t tlsf, void* mem, size_t bytes)
 	** so that the prev_phys_block field falls outside of the pool -
 	** it will never be used.
 	*/
-	block = offset_to_block(mem, -(tlsfptr_t)block_header_overhead);
+	block = offset_to_block(mem, -(tlsfptr_t)block_header_shift);
 	block_set_size(block, pool_bytes);
 	block_set_free(block);
 	block_set_prev_used(block);
@@ -852,7 +853,7 @@ pool_t tlsf_add_pool(tlsf_t tlsf, void* mem, size_t bytes)
 void tlsf_remove_pool(tlsf_t tlsf, pool_t pool)
 {
 	control_t* control = tlsf_cast(control_t*, tlsf);
-	block_header_t* block = offset_to_block(pool, -(int)block_header_overhead);
+	block_header_t* block = offset_to_block(pool, -(int)block_header_shift);
 
 	int fl = 0, sl = 0;
 
@@ -980,7 +981,7 @@ void* tlsf_memalign(tlsf_t tlsf, size_t align, size_t size)
 	block = block_locate_free(control, aligned_size);
 
 	/* This can't be a static assert. */
-	tlsf_assert(sizeof(block_header_t) == block_size_min + block_header_overhead);
+	tlsf_assert(sizeof(block_header_t) == block_size_min + block_header_shift);
 
 	if (block)
 	{
-- 
2.39.2




More information about the barebox mailing list