]> Projects (at) Tadryanom (dot) Me - AdrOS.git/commit
refactor: replace doubly-linked-list heap with buddy allocator
authorTulio A M Mendes <[email protected]>
Fri, 13 Feb 2026 04:07:06 +0000 (01:07 -0300)
committerTulio A M Mendes <[email protected]>
Fri, 13 Feb 2026 04:07:06 +0000 (01:07 -0300)
commit698aa0e0546190281e017ec1f3efab44dbf09a61
treee774a7e6ea9b668ac726f63da645055a3a070c02
parent083bebf0946f2601506d4efd92f19710ce8144c5
refactor: replace doubly-linked-list heap with buddy allocator

Power-of-2 block sizes from 2^5 (32B) to 2^23 (8MB) with O(log N)
alloc/free and automatic buddy coalescing on free.

Design:
- block_hdr_t (8B) at the start of every block: magic, order, is_free
- Free blocks embed circular doubly-linked list pointers in their
  data area (free_node_t) for O(1) insert/remove per order
- 19 free lists (one per order, sentinel-based)
- Buddy merge: XOR offset to find buddy, check magic + is_free + order
- Spinlock-protected for SMP safety

Allocation:
- size_to_order: find smallest 2^k >= size + 8 (header)
- Search free lists from requested order upward
- Split larger blocks down, placing upper buddies on their free lists

Deallocation:
- Verify magic and double-free
- Iteratively merge with buddy while buddy is free at same order
- Insert merged block into correct free list

Trade-offs vs previous doubly-linked-list allocator:
+ O(log N) worst case vs O(N) first-fit scan
+ No external fragmentation (buddy coalescing)
+ Deterministic allocation time
- Internal fragmentation from power-of-2 rounding (~50% worst case)
- Fixed 8MB heap (was 10MB growable to 64MB)

Updated smoke test expectation for new init message.
19/19 smoke tests pass, cppcheck clean.
src/mm/heap.c
tests/smoke_test.exp