AGENT SKILL

memory-allocator-from-scratch

Use when implementing a custom malloc/free-style memory allocator from first principles — not when just using a language's built-in allocator. Triggers on: 'write a malloc implementation', 'build a memory allocator', 'free list allocator', 'buddy allocator', 'slab allocator', 'implement my own malloc/free'. Covers free-list design, block metadata, coalescing, alignment, and allocator strategy tradeoffs.

License 许可
Apache-2.0
最近更新
2026-11-14
Stars
★ 13
Forks
2

01 前言 Front Matter

name
memory-allocator-from-scratch
origin
yana-ai — synthesized from classic allocator literature (K&R malloc, dlmalloc design notes, jemalloc/tcmalloc public design docs) and community from-scratch tutorials indexed in codecrafters-io/build-your-own-x
license
Apache-2.0
version
1.0.0
description
Use when implementing a custom malloc/free-style memory allocator from first principles — not when just using a language's built-in allocator. Triggers on: 'write a malloc implementation', 'build a memory allocator', 'free list allocator', 'buddy allocator', 'slab allocator', 'implement my own malloc/free'. Covers free-list design, block metadata, coalescing, alignment, and allocator strategy tradeoffs.
compatibility
yana-ai >= 0.43.2

03 SKILL.md 正文

/memory-allocator-from-scratch

When to Use

  • Implementing malloc/free/realloc semantics from raw memory (e.g. over mmap/sbrk, or a fixed byte array) for teaching, an embedded target, or a custom-runtime project.
  • Choosing between allocator strategies (bump, free-list, buddy, slab) for a specific workload and needing the actual tradeoffs, not just the names.
  • Debugging fragmentation, use-after-free, or double-free in a hand-rolled allocator.

Do NOT use for

  • Application-level memory management in a language with a GC or a mature allocator (JS, Python, Go, Java) — there is nothing to build here, use the runtime's allocator.
  • General performance profiling of memory usage — see memory-leak-detection and profiling-benchmarking instead.
  • Production allocator replacement — use jemalloc/mimalloc/tcmalloc; this skill is for understanding the mechanism, not shipping a faster malloc than decades of tuned production allocators.

Strategy Decision

Need the simplest possible allocator, never freeing individual objects?
  → Bump allocator (Step 1) — O(1) alloc, no free, reset all at once

Need general alloc/free of variable sizes, simplicity over raw speed?
  → Free-list allocator (Step 2) — the "classic malloc" approach

Need to minimize external fragmentation with fast coalescing?
  → Buddy allocator (Step 3) — power-of-2 sizes, easy merge, some internal waste

Need fast alloc/free of many same-sized objects (e.g. a fixed struct)?
  → Slab allocator (Step 4) — pre-carved fixed-size slots, near-zero overhead per alloc

Step 1: Bump Allocator (baseline)

Simplest possible allocator: keep one pointer to the next free byte, hand out size bytes and advance the pointer. No free() — the whole arena resets or is discarded at once (common in arena/region allocators for a single request's lifetime, e.g. a per-frame game allocator or a per-HTTP-request arena).

alloc(size):
  aligned = align_up(next_free, ALIGNMENT)
  if aligned + size > arena_end: return OUT_OF_MEMORY
  next_free = aligned + size
  return aligned

Step 2: Free-List Allocator

The mechanism behind classic malloc. Every allocated AND free block gets a small header before the returned pointer:

struct BlockHeader {
  size_t size;       // payload size, not including header
  bool   is_free;
  BlockHeader* next; // intrusive linked list of free blocks
}

alloc(size): walk the free list looking for a block big enough.

  • First-fit: take the first block that fits — fast, can fragment.
  • Best-fit: scan for the smallest block that fits — less waste per allocation, slower, can leave many tiny unusable fragments over time.
  • If the found block is much bigger than needed, split it: carve off the requested size, leave the remainder as a new (smaller) free block.

free(ptr): walk back from ptr to its header, mark is_free = true, then coalesce with adjacent free blocks (check the block immediately before and after in memory address order, merge if both are free) — without coalescing, freed memory fragments into unusable slivers over time even though total free bytes is fine.

Alignment: most platforms require allocations aligned to 8 or 16 bytes (SIMD types need more). Round the requested size up to the alignment boundary before computing block size — an unaligned pointer returned to the caller can crash on some architectures (e.g. ARM strict alignment) or silently corrupt SIMD loads.

Step 3: Buddy Allocator

Only allocates in power-of-2 sizes. The whole arena starts as one free block of size 2^max. To satisfy a request, repeatedly split the smallest available block in half ("buddies") until you reach the smallest power-of-2 that fits the request. To free, check if your buddy (computable directly from your address via XOR with the block size) is also free — if so, merge back into the parent block, and recurse the check upward.

Tradeoff vs free-list: coalescing is O(log n) and address-computable (no list walk needed to find the buddy), but every allocation rounds up to the next power of 2 — a 65-byte request costs 128 bytes (internal fragmentation).

Step 4: Slab Allocator

For a workload that allocates/frees many objects of the SAME fixed size (e.g. kernel task_struct, a game's particle objects): pre-allocate a "slab" (a page or arena) already carved into fixed-size slots, and track free slots with a simple bitmap or intrusive free list of slot indices. Alloc and free are both O(1) with no header-walking or fragmentation concerns, since every slot is identical size.

What NOT to Do

  • Don't skip the header — without per-block metadata, free() has no way to know a block's size or its free-list neighbors.
  • Don't forget alignment — misaligned pointers are a portability bug that won't show up on every platform/compiler, making it easy to ship broken and not notice.
  • Don't free() without coalescing adjacent blocks — a free-list allocator that never merges will eventually report "out of memory" while holding plenty of free (but fragmented) bytes.
  • Don't reach for buddy or slab allocators before a free-list works correctly — they solve fragmentation/speed problems a working free-list doesn't have yet.

04 同仓库更多 Skills

Horonomos-laps
Horonomos-laps/Yana-AI

openai--sentry--sentry

Use when the user asks to inspect Sentry issues or events, summarize recent production errors, or pull basic Sentry health data via the Sentry API; perform read-only queries with the bundled script and require `SENTRY_AUTH_TOKEN`.

★ 13
Horonomos-laps
Horonomos-laps/Yana-AI

ito-basket-compare

Compare Itô prediction-market baskets against a user's knowledge base, portfolio notes, financial context, watchlist, or research thesis. Use for read-only basket comparison and gap analysis without investment advice or live trading.

★ 13
Horonomos-laps
Horonomos-laps/Yana-AI

implementing-network-traffic-baselining

Build network traffic baselines from NetFlow/IPFIX data using Python pandas for statistical analysis, z-score anomaly detection, and hourly/daily traffic pattern profiling

★ 13
Horonomos-laps
Horonomos-laps/Yana-AI

detecting-evasion-techniques-in-endpoint-logs

Detects defense evasion techniques used by adversaries in endpoint logs including log tampering, timestomping, process injection, and security tool disabling. Use when investigating suspicious endpoint behavior, building detection rules for evasion tactics, or conducting threat hunting for stealthy adversary activity. Activates for requests involving evasion detection, defense evasion analysis, log tampering detection, or MITRE ATT&CK TA0005.

★ 13
Horonomos-laps
Horonomos-laps/Yana-AI

implementing-microsegmentation-with-guardicore

Implementing microsegmentation using Akamai Guardicore Segmentation to map application dependencies, create granular network policies, visualize east-west traffic flows, and enforce least-privilege communication between workloads across data centers and cloud.

★ 13
Horonomos-laps
Horonomos-laps/Yana-AI

ramdisk-tmpfs-patterns

暂无简介

★ 13