This is an automated email from the ASF dual-hosted git repository. xiaoxiang pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/nuttx.git
commit b1948a1631a6663f21e4d4da0c799729f24abebb Author: wangbowen6 <wangbow...@xiaomi.com> AuthorDate: Thu Dec 22 16:02:42 2022 +0800 mm: move preceding to previous free node to reduce the overhead Signed-off-by: wangbowen6 <wangbow...@xiaomi.com> --- mm/mm_heap/mm.h | 10 +++++++++- mm/mm_heap/mm_extend.c | 7 +++---- mm/mm_heap/mm_foreach.c | 5 +++-- mm/mm_heap/mm_free.c | 20 +++++++++++++++----- mm/mm_heap/mm_initialize.c | 21 ++++++++++----------- mm/mm_heap/mm_mallinfo.c | 10 +++++++++- mm/mm_heap/mm_malloc.c | 28 +++++++++++++++++++--------- mm/mm_heap/mm_malloc_size.c | 2 +- mm/mm_heap/mm_memalign.c | 26 +++++++++++++------------- mm/mm_heap/mm_realloc.c | 36 ++++++++++++++++++------------------ mm/mm_heap/mm_shrinkchunk.c | 10 +++++----- 11 files changed, 105 insertions(+), 70 deletions(-) diff --git a/mm/mm_heap/mm.h b/mm/mm_heap/mm.h index 764156d826..4892f6f686 100644 --- a/mm/mm_heap/mm.h +++ b/mm/mm_heap/mm.h @@ -119,7 +119,8 @@ */ #define MM_ALLOC_BIT 0x1 -#define MM_MASK_BIT MM_ALLOC_BIT +#define MM_PREVFREE_BIT 0x2 +#define MM_MASK_BIT (MM_ALLOC_BIT | MM_PREVFREE_BIT) #ifdef CONFIG_MM_SMALL # define MMSIZE_MAX UINT16_MAX #else @@ -130,6 +131,13 @@ #define SIZEOF_MM_ALLOCNODE sizeof(struct mm_allocnode_s) +/* What is the overhead of the allocnode + * Remove the space of preceding field since it locates at the end of the + * previous freenode + */ + +#define OVERHEAD_MM_ALLOCNODE (SIZEOF_MM_ALLOCNODE - sizeof(mmsize_t)) + /* What is the size of the freenode? */ #define SIZEOF_MM_FREENODE sizeof(struct mm_freenode_s) diff --git a/mm/mm_heap/mm_extend.c b/mm/mm_heap/mm_extend.c index 94c2392a0c..8781f4b20e 100644 --- a/mm/mm_heap/mm_extend.c +++ b/mm/mm_heap/mm_extend.c @@ -100,10 +100,9 @@ void mm_extend(FAR struct mm_heap_s *heap, FAR void *mem, size_t size, /* Get and initialize the new terminal node in the heap */ - newnode = (FAR struct mm_allocnode_s *) - (blockend - SIZEOF_MM_ALLOCNODE); - newnode->size = SIZEOF_MM_ALLOCNODE | MM_ALLOC_BIT; - newnode->preceding = size; + newnode = (FAR struct mm_allocnode_s *) + (blockend - SIZEOF_MM_ALLOCNODE); + newnode->size = SIZEOF_MM_ALLOCNODE | MM_ALLOC_BIT; heap->mm_heapend[region] = newnode; diff --git a/mm/mm_heap/mm_foreach.c b/mm/mm_heap/mm_foreach.c index 58daef0cb8..23255bf8a5 100644 --- a/mm/mm_heap/mm_foreach.c +++ b/mm/mm_heap/mm_foreach.c @@ -79,13 +79,14 @@ void mm_foreach(FAR struct mm_heap_s *heap, mm_node_handler_t handler, node = (FAR struct mm_allocnode_s *)((FAR char *)node + nodesize)) { nodesize = SIZEOF_MM_NODE(node); - minfo("region=%d node=%p size=%zu preceding=%u (%c)\n", + minfo("region=%d node=%p size=%zu preceding=%u (%c %c)\n", region, node, nodesize, (unsigned int)node->preceding, + (node->size & MM_PREVFREE_BIT) ? 'F' : 'A', (node->size & MM_ALLOC_BIT) ? 'A' : 'F'); handler(node, arg); - DEBUGASSERT(prev == NULL || + DEBUGASSERT((node->size & MM_PREVFREE_BIT) == 0 || SIZEOF_MM_NODE(prev) == node->preceding); prev = node; } diff --git a/mm/mm_heap/mm_free.c b/mm/mm_heap/mm_free.c index 6ca89dd314..00e715ab29 100644 --- a/mm/mm_heap/mm_free.c +++ b/mm/mm_heap/mm_free.c @@ -120,7 +120,7 @@ void mm_free(FAR struct mm_heap_s *heap, FAR void *mem) /* Check if the following node is free and, if so, merge it */ next = (FAR struct mm_freenode_s *)((FAR char *)node + nodesize); - DEBUGASSERT(next->preceding == nodesize); + DEBUGASSERT((next->size & MM_PREVFREE_BIT) == 0); if ((next->size & MM_ALLOC_BIT) == 0) { FAR struct mm_allocnode_s *andbeyond; @@ -132,6 +132,8 @@ void mm_free(FAR struct mm_heap_s *heap, FAR void *mem) */ andbeyond = (FAR struct mm_allocnode_s *)((FAR char *)next + nextsize); + DEBUGASSERT((andbeyond->size & MM_PREVFREE_BIT) != 0 && + andbeyond->preceding == nextsize); /* Remove the next node. There must be a predecessor, * but there may not be a successor node. @@ -151,16 +153,24 @@ void mm_free(FAR struct mm_heap_s *heap, FAR void *mem) andbeyond->preceding = nodesize; next = (FAR struct mm_freenode_s *)andbeyond; } + else + { + next->size |= MM_PREVFREE_BIT; + next->preceding = nodesize; + } /* Check if the preceding node is also free and, if so, merge * it with this node */ - prev = (FAR struct mm_freenode_s *)((FAR char *)node - node->preceding); - prevsize = SIZEOF_MM_NODE(prev); - DEBUGASSERT(node->preceding == prevsize); - if ((prev->size & MM_ALLOC_BIT) == 0) + if ((node->size & MM_PREVFREE_BIT) != 0) { + prev = (FAR struct mm_freenode_s *) + ((FAR char *)node - node->preceding); + prevsize = SIZEOF_MM_NODE(prev); + DEBUGASSERT((prev->size & MM_ALLOC_BIT) == 0 && + node->preceding == prevsize); + /* Remove the node. There must be a predecessor, but there may * not be a successor node. */ diff --git a/mm/mm_heap/mm_initialize.c b/mm/mm_heap/mm_initialize.c index ebcffa79c6..c82f905634 100644 --- a/mm/mm_heap/mm_initialize.c +++ b/mm/mm_heap/mm_initialize.c @@ -134,19 +134,18 @@ void mm_addregion(FAR struct mm_heap_s *heap, FAR void *heapstart, * all available memory. */ - heap->mm_heapstart[IDX] = (FAR struct mm_allocnode_s *) - heapbase; + heap->mm_heapstart[IDX] = (FAR struct mm_allocnode_s *)heapbase; MM_ADD_BACKTRACE(heap, heap->mm_heapstart[IDX]); - heap->mm_heapstart[IDX]->size = SIZEOF_MM_ALLOCNODE | MM_ALLOC_BIT; - node = (FAR struct mm_freenode_s *) - (heapbase + SIZEOF_MM_ALLOCNODE); + heap->mm_heapstart[IDX]->size = SIZEOF_MM_ALLOCNODE | MM_ALLOC_BIT; + node = (FAR struct mm_freenode_s *) + (heapbase + SIZEOF_MM_ALLOCNODE); DEBUGASSERT((((uintptr_t)node + SIZEOF_MM_ALLOCNODE) % MM_MIN_CHUNK) == 0); - node->size = heapsize - 2*SIZEOF_MM_ALLOCNODE; - node->preceding = SIZEOF_MM_ALLOCNODE; - heap->mm_heapend[IDX] = (FAR struct mm_allocnode_s *) - (heapend - SIZEOF_MM_ALLOCNODE); - heap->mm_heapend[IDX]->size = SIZEOF_MM_ALLOCNODE | MM_ALLOC_BIT; - heap->mm_heapend[IDX]->preceding = node->size; + node->size = heapsize - 2 * SIZEOF_MM_ALLOCNODE; + heap->mm_heapend[IDX] = (FAR struct mm_allocnode_s *) + (heapend - SIZEOF_MM_ALLOCNODE); + heap->mm_heapend[IDX]->size = SIZEOF_MM_ALLOCNODE | MM_ALLOC_BIT | + MM_PREVFREE_BIT; + heap->mm_heapend[IDX]->preceding = node->size; MM_ADD_BACKTRACE(heap, heap->mm_heapend[IDX]); #undef IDX diff --git a/mm/mm_heap/mm_mallinfo.c b/mm/mm_heap/mm_mallinfo.c index 0e6ee6eda6..34e90994bf 100644 --- a/mm/mm_heap/mm_mallinfo.c +++ b/mm/mm_heap/mm_mallinfo.c @@ -129,7 +129,15 @@ int mm_mallinfo(FAR struct mm_heap_s *heap, FAR struct mallinfo *info) mm_foreach(heap, mallinfo_handler, info); info->arena = heap->mm_heapsize; - info->uordblks += region * SIZEOF_MM_ALLOCNODE; /* account for the tail node */ + + /* Account for the heap->mm_heapend[region] node overhead and the + * heap->mm_heapstart[region]->preceding: + * heap->mm_heapend[region] overhead size = OVERHEAD_MM_ALLOCNODE + * heap->mm_heapstart[region]->preceding size = sizeof(mmsize_t) + * and SIZEOF_MM_ALLOCNODE = OVERHEAD_MM_ALLOCNODE + sizeof(mmsize_t). + */ + + info->uordblks += region * SIZEOF_MM_ALLOCNODE; DEBUGASSERT((size_t)info->uordblks + info->fordblks == heap->mm_heapsize); diff --git a/mm/mm_heap/mm_malloc.c b/mm/mm_heap/mm_malloc.c index 22919c1f43..d03abec747 100644 --- a/mm/mm_heap/mm_malloc.c +++ b/mm/mm_heap/mm_malloc.c @@ -133,7 +133,7 @@ FAR void *mm_malloc(FAR struct mm_heap_s *heap, size_t size) * (2) to make sure that it is an even multiple of our granule size. */ - alignsize = MM_ALIGN_UP(size + SIZEOF_MM_ALLOCNODE); + alignsize = MM_ALIGN_UP(size + OVERHEAD_MM_ALLOCNODE); if (alignsize < size) { /* There must have been an integer overflow */ @@ -189,6 +189,13 @@ FAR void *mm_malloc(FAR struct mm_heap_s *heap, size_t size) node->flink->blink = node->blink; } + /* Get a pointer to the next node in physical memory */ + + next = (FAR struct mm_freenode_s *)(((FAR char *)node) + nodesize); + DEBUGASSERT((next->size & MM_ALLOC_BIT) != 0 && + (next->size & MM_PREVFREE_BIT) != 0 && + next->preceding == nodesize); + /* Check if we have to split the free node into one of the allocated * size and another smaller freenode. In some cases, the remaining * bytes can be smaller (they may be SIZEOF_MM_ALLOCNODE). In that @@ -199,21 +206,16 @@ FAR void *mm_malloc(FAR struct mm_heap_s *heap, size_t size) remaining = nodesize - alignsize; if (remaining >= SIZEOF_MM_FREENODE) { - /* Get a pointer to the next node in physical memory */ - - next = (FAR struct mm_freenode_s *)(((FAR char *)node) + nodesize); - /* Create the remainder node */ remainder = (FAR struct mm_freenode_s *) (((FAR char *)node) + alignsize); - remainder->size = remaining; - remainder->preceding = alignsize; + remainder->size = remaining; /* Adjust the size of the node under consideration */ - node->size = alignsize; + node->size = alignsize | (node->size & MM_MASK_BIT); /* Adjust the 'preceding' size of the (old) next node. */ @@ -223,6 +225,14 @@ FAR void *mm_malloc(FAR struct mm_heap_s *heap, size_t size) mm_addfreechunk(heap, remainder); } + else + { + /* Previous physical memory node is alloced, so clear the previous + * free bit in next->size. + */ + + next->size &= ~MM_PREVFREE_BIT; + } /* Handle the case of an exact size match */ @@ -238,7 +248,7 @@ FAR void *mm_malloc(FAR struct mm_heap_s *heap, size_t size) MM_ADD_BACKTRACE(heap, node); kasan_unpoison(ret, mm_malloc_size(heap, ret)); #ifdef CONFIG_MM_FILL_ALLOCATIONS - memset(ret, 0xaa, alignsize - SIZEOF_MM_ALLOCNODE); + memset(ret, 0xaa, alignsize - OVERHEAD_MM_ALLOCNODE); #endif #ifdef CONFIG_DEBUG_MM minfo("Allocated %p, size %zu\n", ret, alignsize); diff --git a/mm/mm_heap/mm_malloc_size.c b/mm/mm_heap/mm_malloc_size.c index b70ec55c7b..5cc7471ace 100644 --- a/mm/mm_heap/mm_malloc_size.c +++ b/mm/mm_heap/mm_malloc_size.c @@ -62,5 +62,5 @@ size_t mm_malloc_size(FAR struct mm_heap_s *heap, FAR void *mem) DEBUGASSERT(node->size & MM_ALLOC_BIT); - return SIZEOF_MM_NODE(node) - SIZEOF_MM_ALLOCNODE; + return SIZEOF_MM_NODE(node) - OVERHEAD_MM_ALLOCNODE; } diff --git a/mm/mm_heap/mm_memalign.c b/mm/mm_heap/mm_memalign.c index db73e85144..ee98a79c67 100644 --- a/mm/mm_heap/mm_memalign.c +++ b/mm/mm_heap/mm_memalign.c @@ -146,7 +146,6 @@ FAR void *mm_memalign(FAR struct mm_heap_s *heap, size_t alignment, { FAR struct mm_allocnode_s *newnode; FAR struct mm_allocnode_s *next; - FAR struct mm_freenode_s *prev; size_t precedingsize; size_t newnodesize; @@ -154,8 +153,6 @@ FAR void *mm_memalign(FAR struct mm_heap_s *heap, size_t alignment, next = (FAR struct mm_allocnode_s *) ((FAR char *)node + SIZEOF_MM_NODE(node)); - prev = (FAR struct mm_freenode_s *) - ((FAR char *)node - node->preceding); /* Make sure that there is space to convert the preceding * mm_allocnode_s into an mm_freenode_s. I think that this should @@ -193,8 +190,11 @@ FAR void *mm_memalign(FAR struct mm_heap_s *heap, size_t alignment, * set up the node size. */ - if ((prev->size & MM_ALLOC_BIT) == 0) + if ((node->size & MM_PREVFREE_BIT) != 0) { + FAR struct mm_freenode_s *prev = + (FAR struct mm_freenode_s *)((FAR char *)node - node->preceding); + /* Remove the node. There must be a predecessor, but there may * not be a successor node. */ @@ -206,7 +206,7 @@ FAR void *mm_memalign(FAR struct mm_heap_s *heap, size_t alignment, prev->flink->blink = prev->blink; } - precedingsize += prev->size; + precedingsize += SIZEOF_MM_NODE(prev); node = (FAR struct mm_allocnode_s *)prev; } @@ -215,18 +215,18 @@ FAR void *mm_memalign(FAR struct mm_heap_s *heap, size_t alignment, /* Set up the size of the new node */ newnodesize = (uintptr_t)next - (uintptr_t)newnode; - newnode->size = newnodesize | MM_ALLOC_BIT; + newnode->size = newnodesize | MM_ALLOC_BIT | MM_PREVFREE_BIT; newnode->preceding = precedingsize; - /* Fix the preceding size of the next node */ + /* Clear the previous free bit of the next node */ - next->preceding = newnodesize; + next->size &= ~MM_PREVFREE_BIT; /* Convert the newnode chunk size back into malloc-compatible size by - * subtracting the header size SIZEOF_MM_ALLOCNODE. + * subtracting the header size OVERHEAD_MM_ALLOCNODE. */ - allocsize = newnodesize - SIZEOF_MM_ALLOCNODE; + allocsize = newnodesize - OVERHEAD_MM_ALLOCNODE; /* Add the original, newly freed node to the free nodelist */ @@ -240,16 +240,16 @@ FAR void *mm_memalign(FAR struct mm_heap_s *heap, size_t alignment, } /* Check if there is free space at the end of the aligned chunk. Convert - * malloc-compatible chunk size to include SIZEOF_MM_ALLOCNODE as needed + * malloc-compatible chunk size to include OVERHEAD_MM_ALLOCNODE as needed * for mm_shrinkchunk. */ - size = MM_ALIGN_UP(size + SIZEOF_MM_ALLOCNODE); + size = MM_ALIGN_UP(size + OVERHEAD_MM_ALLOCNODE); if (allocsize > size) { /* Shrink the chunk by that much -- remember, mm_shrinkchunk wants - * internal chunk sizes that include SIZEOF_MM_ALLOCNODE. + * internal chunk sizes that include OVERHEAD_MM_ALLOCNODE. */ mm_shrinkchunk(heap, node, size); diff --git a/mm/mm_heap/mm_realloc.c b/mm/mm_heap/mm_realloc.c index a9e3fdc150..2b0add69fd 100644 --- a/mm/mm_heap/mm_realloc.c +++ b/mm/mm_heap/mm_realloc.c @@ -71,7 +71,7 @@ FAR void *mm_realloc(FAR struct mm_heap_s *heap, FAR void *oldmem, size_t size) { FAR struct mm_allocnode_s *oldnode; - FAR struct mm_freenode_s *prev; + FAR struct mm_freenode_s *prev = NULL; FAR struct mm_freenode_s *next; size_t newsize; size_t oldsize; @@ -117,7 +117,7 @@ FAR void *mm_realloc(FAR struct mm_heap_s *heap, FAR void *oldmem, * (2) to make sure that it is an even multiple of our granule size. */ - newsize = MM_ALIGN_UP(size + SIZEOF_MM_ALLOCNODE); + newsize = MM_ALIGN_UP(size + OVERHEAD_MM_ALLOCNODE); if (newsize < size) { /* There must have been an integer overflow */ @@ -149,8 +149,8 @@ FAR void *mm_realloc(FAR struct mm_heap_s *heap, FAR void *oldmem, if (newsize < oldsize) { mm_shrinkchunk(heap, oldnode, newsize); - kasan_poison((FAR char *)oldnode + SIZEOF_MM_NODE(oldnode), - oldsize - SIZEOF_MM_NODE(oldnode)); + kasan_poison((FAR char *)oldnode + SIZEOF_MM_NODE(oldnode) + + sizeof(mmsize_t), oldsize - SIZEOF_MM_NODE(oldnode)); } /* Then return the original address */ @@ -169,13 +169,15 @@ FAR void *mm_realloc(FAR struct mm_heap_s *heap, FAR void *oldmem, next = (FAR struct mm_freenode_s *)((FAR char *)oldnode + oldsize); if ((next->size & MM_ALLOC_BIT) == 0) { + DEBUGASSERT((next->size & MM_PREVFREE_BIT) == 0); nextsize = SIZEOF_MM_NODE(next); } - prev = (FAR struct mm_freenode_s *) - ((FAR char *)oldnode - oldnode->preceding); - if ((prev->size & MM_ALLOC_BIT) == 0) + if ((oldnode->size & MM_PREVFREE_BIT) != 0) { + prev = (FAR struct mm_freenode_s *) + ((FAR char *)oldnode - oldnode->preceding); + DEBUGASSERT((prev->size & MM_ALLOC_BIT) == 0); prevsize = SIZEOF_MM_NODE(prev); } @@ -251,7 +253,7 @@ FAR void *mm_realloc(FAR struct mm_heap_s *heap, FAR void *oldmem, * there may not be a successor node. */ - DEBUGASSERT(prev->blink); + DEBUGASSERT(prev && prev->blink); prev->blink->flink = prev->flink; if (prev->flink) { @@ -273,11 +275,10 @@ FAR void *mm_realloc(FAR struct mm_heap_s *heap, FAR void *oldmem, prevsize -= takeprev; DEBUGASSERT(prevsize >= SIZEOF_MM_FREENODE); - prev->size = prevsize; + prev->size = prevsize | (prev->size & MM_MASK_BIT); nodesize += takeprev; - newnode->size = nodesize | MM_MASK_BIT; + newnode->size = nodesize | MM_ALLOC_BIT | MM_PREVFREE_BIT; newnode->preceding = prevsize; - next->preceding = nodesize; /* Return the previous free node to the nodelist * (with the new size) @@ -289,9 +290,9 @@ FAR void *mm_realloc(FAR struct mm_heap_s *heap, FAR void *oldmem, { /* Yes.. update its size (newnode->preceding is already set) */ - nodesize += prevsize; - newnode->size = nodesize | MM_ALLOC_BIT; - next->preceding = nodesize; + nodesize += prevsize; + newnode->size = nodesize | MM_ALLOC_BIT | + (newnode->size & MM_MASK_BIT); } newmem = (FAR void *)((FAR char *)newnode + SIZEOF_MM_ALLOCNODE); @@ -343,7 +344,6 @@ FAR void *mm_realloc(FAR struct mm_heap_s *heap, FAR void *oldmem, ((FAR char *)oldnode + nodesize); newnode->size = nextsize - takenext; DEBUGASSERT(newnode->size >= SIZEOF_MM_FREENODE); - newnode->preceding = nodesize; andbeyond->preceding = newnode->size; /* Add the new free node to the nodelist (with the new size) */ @@ -354,7 +354,7 @@ FAR void *mm_realloc(FAR struct mm_heap_s *heap, FAR void *oldmem, { /* Yes, just update some pointers. */ - andbeyond->preceding = nodesize; + andbeyond->size &= ~MM_PREVFREE_BIT; } } @@ -368,7 +368,7 @@ FAR void *mm_realloc(FAR struct mm_heap_s *heap, FAR void *oldmem, * should be safe for this. */ - memcpy(newmem, oldmem, oldsize - SIZEOF_MM_ALLOCNODE); + memcpy(newmem, oldmem, oldsize - OVERHEAD_MM_ALLOCNODE); } return newmem; @@ -388,7 +388,7 @@ FAR void *mm_realloc(FAR struct mm_heap_s *heap, FAR void *oldmem, newmem = mm_malloc(heap, size); if (newmem) { - memcpy(newmem, oldmem, oldsize - SIZEOF_MM_ALLOCNODE); + memcpy(newmem, oldmem, oldsize - OVERHEAD_MM_ALLOCNODE); mm_free(heap, oldmem); } diff --git a/mm/mm_heap/mm_shrinkchunk.c b/mm/mm_heap/mm_shrinkchunk.c index 7d950b8d63..9360f9ab61 100644 --- a/mm/mm_heap/mm_shrinkchunk.c +++ b/mm/mm_heap/mm_shrinkchunk.c @@ -72,6 +72,7 @@ void mm_shrinkchunk(FAR struct mm_heap_s *heap, /* Get the chunk next the next node (which could be the tail chunk) */ andbeyond = (FAR struct mm_allocnode_s *)((FAR char *)next + nextsize); + DEBUGASSERT((andbeyond->size & MM_PREVFREE_BIT) != 0); /* Remove the next node. There must be a predecessor, but there may * not be a successor node. @@ -93,7 +94,6 @@ void mm_shrinkchunk(FAR struct mm_heap_s *heap, /* Set up the size of the new node */ newnode->size = nextsize + nodesize - size; - newnode->preceding = size; node->size = size | (node->size & MM_MASK_BIT); andbeyond->preceding = newnode->size; @@ -118,10 +118,10 @@ void mm_shrinkchunk(FAR struct mm_heap_s *heap, /* Set up the size of the new node */ - newnode->size = nodesize - size; - newnode->preceding = size; - node->size = size | (node->size & MM_MASK_BIT); - next->preceding = newnode->size; + newnode->size = nodesize - size; + node->size = size | (node->size & MM_MASK_BIT); + next->size |= MM_PREVFREE_BIT; + next->preceding = newnode->size; /* Add the new node to the freenodelist */