This is an automated email from the ASF dual-hosted git repository. acassis pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/nuttx.git
commit ddbb8a2dede1ec932a9286d1e5e610b0e4c3b6d7 Author: Marco Casaroli <[email protected]> AuthorDate: Thu Oct 29 18:56:37 2026 +0100 mm/mm_gran: Search the allocation table one word at a time. gran_search() called gran_match() at each granule position from the start of the table. For a range of one granule, a used granule moved the search forward by one position only, so each allocation read all of the used granules below the first free one. This cost came back with fb5d0f61f3e, which corrected the skip that 1abcb6a0905 ("Speed optimize gran_match") had added. The page allocator of the kernel build (mm_pgalloc()) gets one page at a time. A fork() of a process with 3.6 MiB of memory made 926 allocations, and each allocation read about 3500 used granules. On qemu-armv8a (HVF) fork() took 36 ms, and 31 ms of it was in mm_pgalloc(). posix_spawn() of a program took 36 ms for the same reason. Read the table one 32-bit word at a time: find the first free granule, then the first used granule after it, with a count of trailing zeros. A word with no free granule costs one read. The result does not change: it is the free range with the lowest address. On the same system fork() now takes 0.5 ms and posix_spawn() of a program 3 ms. Assisted-by: Claude Code:claude-opus-5-5 Signed-off-by: Marco Casaroli <[email protected]> --- mm/mm_gran/mm_grantable.c | 61 +++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 51 insertions(+), 10 deletions(-) diff --git a/mm/mm_gran/mm_grantable.c b/mm/mm_gran/mm_grantable.c index b82fbb2a06e..1ebb0047d43 100644 --- a/mm/mm_gran/mm_grantable.c +++ b/mm/mm_gran/mm_grantable.c @@ -124,6 +124,40 @@ static void gran_set_(gran_t *gran, gatr_t *rang, bool val) return; } +/* Return the first granule at or above posi and below limit that is in the + * given state, or limit if there is none. Look at one GAT cell at a time. + */ + +static size_t gran_next(const gran_t *gran, size_t posi, size_t limit, + bool used) +{ + size_t width = GATC_BITS(gran); + size_t c = posi / width; + uint32_t v; + + if (posi >= limit) + { + return limit; + } + + v = used ? gran->gat[c] : ~gran->gat[c]; + v &= ~(BIT(posi % width) - 1); + + while (v == 0) + { + c++; + if (c * width >= limit) + { + return limit; + } + + v = used ? gran->gat[c] : ~gran->gat[c]; + } + + posi = c * width + ffsl(v) - 1; + return posi < limit ? posi : limit; +} + /**************************************************************************** * Public Functions ****************************************************************************/ @@ -262,25 +296,32 @@ failure: int gran_search(const gran_t *gran, size_t size) { - int ret = -EINVAL; - size_t i; + size_t posi = 0; + size_t used; if (gran == NULL || gran->ngranules < size) { - return ret; + return -EINVAL; } - ret = -ENOMEM; - for (i = 0; i <= gran->ngranules - size; i++) + for (; ; ) { - if (gran_match(gran, i, size, 0, &i)) + /* The first free granule, then the first used one after it */ + + posi = gran_next(gran, posi, gran->ngranules, false); + if (gran->ngranules - posi < size) { - ret = i; - break; + return -ENOMEM; } - } - return ret; + used = gran_next(gran, posi, posi + size, true); + if (used - posi >= size) + { + return posi; + } + + posi = used; + } } /* set a range of granules */
