casaroli opened a new pull request, #21156:
URL: https://github.com/apache/nuttx/pull/21156
## Summary
The granule allocator (`mm/mm_gran`) found a free range in a time that grows
with the number of used granules below it. The page allocator of the kernel
build (`mm_pgalloc()`) is a granule allocator and gets one page at a time, so
`fork()`, `exec()` and `posix_spawn()` became slow, and slower when other
processes held much memory.
- **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. Now the search reads the table one 32-bit word at a
time: it finds the first free granule, then the first used granule after it,
with a count of trailing zeros (`__builtin_ctzl()`, or the de Bruijn table that
the file already has when the compiler has no builtin). A word with no free
granule costs one read. The result does not change: it is the free range with
the lowest address.
- **mm/mm_gran: Start the search at the lowest free granule.** `struct
gran_s` keeps `lowfree`, the position below which no granule is free.
`gran_set()` moves it up when an allocation takes that granule, and
`gran_clear()` moves it down when a lower granule becomes free. `gran_search()`
starts there. The result does not change.
- **Documentation/mm: Describe the search of the granule allocator.** One
paragraph in `Documentation/os/memory/index.rst`.
History: 1abcb6a0905 ("Speed optimize gran_match") skipped from the highest
used bit of the whole word, which also skipped free granules below a used bit
outside the range. fb5d0f61f3e corrected that with the masked value, and with
it a one-granule search went back to one step per used granule. This PR keeps
that correction and makes the search fast again.
## Impact
- The same code in flat, protected and kernel builds and on every
architecture: generic C in `mm/mm_gran`. Every user of the granule allocator
(the page allocator of kernel builds, DMA heaps) gets the same allocations as
before, faster.
- `struct gran_s` (private to `mm/mm_gran`) is 4 bytes larger.
- No change of an interface, an ABI or a configuration. Not a breaking
change.
- Compilers: the builtin is used only where `include/nuttx/compiler.h`
defines `CONFIG_HAVE_BUILTIN_CTZ` (GCC and clang). It is the `long` form
because `int` has 16 bits on some GCC targets (AVR). Other compilers (SDCC,
IAR, TASKING, ZDS, MSVC, ...) use the de Bruijn table.
## Testing
Test program `forkspeed.c` (POSIX: `fork()` copies the memory, then the mean
time of 50 `fork()` + `_exit()` + `waitpid()`, alone and while another process
holds memory; "held" passes when its time is below 2 x "time" + 2 ms) on
qemu-armv8a:knsh (QEMU, HVF, 1 CPU) with `CONFIG_PIPES`,
`CONFIG_SCHED_WAITPID`, `CONFIG_SCHED_CHILD_STATUS`:
| Case | master | this PR |
|---|---|---|
| default page pool (4 MiB): time per `fork()` | 161 us | 38 us |
| default page pool: the same while another process holds 256 KiB | 184 us |
39 us |
| `CONFIG_ARCH_PGPOOL_SIZE` 96 MiB: time per `fork()` | 194 us | 54 us |
| 96 MiB page pool: the same while another process holds 32 MiB | 11446 us
(FAIL) | 95 us (PASS) |
Test program `granflat.c` (a flat build calls the allocator directly) on
qemu-armv8a:nsh with `CONFIG_GRAN=y`: 10056 random
`gran_alloc()`/`gran_alloc_align()` of 1-100 granules with random frees in a
table of 2000 granules, each address compared with a model of first fit: 0
differences on master and with this PR. One allocation and free of one granule
when 15000 of 16384 granules are used: 2230741 ns on master, 124 ns with this
PR.
Host test (the old and the new `mm_grantable.c` built for the host): random
tables of 1-2000 granules, random allocations of 1-40 granules (some aligned)
and frees through the new `gran_set()`/`gran_clear()`: 8010954 searches, each
gives the position of the old code, with `__builtin_ctzl()` and with the de
Bruijn table. One search for one granule in a table of 229376 granules:
| Used granules | master | this PR |
|---|---|---|
| 3500 | 12.6 us | 4 ns |
| 20000 | 89.8 us | 4 ns |
| 82000 | 331 us | 4 ns |
| 200000 | 776 us | 3 ns |
The new `mm_grantable.c` also compiles with SDCC 4.6.0 for z80 and mcs51
(the de Bruijn path, 16-bit `int`).
ostest exits with status 0 on qemu-armv8a:knsh and qemu-armv8a:nsh (also
with `CONFIG_GRAN=y`), on master and with this PR.
Build check, each OK and with `mm_grantable.c` compiled: qemu-armv8a:knsh
(kernel, arm64), rv-virt:knsh64 and rv-virt:ksmp64 (kernel, rv64, also SMP),
qemu-intel64:knsh_romfs (kernel, x86_64), qemu-armv7a:knsh (kernel, armv7-a),
and with `CONFIG_GRAN=y`: qemu-armv8a:nsh and qemu-armv8a:nsh_smp (flat),
sim:nsh (flat, sim), rv-virt:pnsh64 (protected, rv64), mps2-an500:knsh
(protected, Cortex-M7); imx93-evk:nsh and stm32f746-ws:nsh (flat,
`CONFIG_GRAN=y` in the defconfig).
`tools/checkpatch.sh -c -u -m -g` passes.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
