Libc: malloc

The IRIX libc malloc family (malloc, free, realloc, etc.) implements a classic System V-style dynamic memory allocator using a splay tree for managing free blocks of varying sizes, separate linked lists for small blocks, aggressive coalescing, and delayed freeing to preserve freed block contents across calls. It obtains more memory via sbrk (or equivalent GETCORE), aligns allocations to word boundaries, and handles non-contiguous arenas when necessary.

This decompiled implementation reveals MIPS-specific details (e.g., word size alignment, conditional segmented memory handling), a unique delayed free mechanism using flist and Lfree to avoid disturbing freed data until the next allocation, and optimizations like small-block lists and history-based batch allocation.

Also see: Kernel:malloc

Key Functions

The allocator centers on a splay tree of free blocks with supporting structures and routines for coalescing, tree maintenance, and arena growth.

Core Allocation (_malloc / __malloc)

Rounds size to word alignment (WORDSIZE, typically 8 on 64-bit MIPS). Checks last freed block (Lfree) for reuse. Performs pending frees via cleanfree(). Handles small requests (< MINSIZE) via _smalloc. Searches splay tree for best-fit (approximated via splaying). Falls back to Bottom chunk or _morecore() for new memory. Coalesces leftovers if large enough.

Deallocation (free / __free / realfree) free delays actual deallocation by placing pointer in circular flist buffer (size FREESIZE=32) and sets Lfree. Actual freeing occurs in next malloc/realloc via cleanfree() or when buffer fills. realfree coalesces with adjacent blocks, inserts into small lists or splay tree (leaf insertion without immediate splay), updates neighbor busy/free bits.

Reallocation (realloc / _realloc)

Attempts in-place expansion by forward merging. Extends via _morecore if at arena end. Falls back to new allocation + copy + free. Handles special recovery cases when allocation fails (shrink, small-block fallback, backward merge with copy).

Small Block Allocation (_smalloc) Maintains per-size linked lists (List[]) for sizes < MINSIZE. Batch-allocates multiples (powers of 2 based on history bits) from large blocks to reduce calls to main allocator.

Arena Extension (_morecore)

Requests memory via GETCORE (sbrk wrapper), aligns to page boundaries, doubles request size after threshold calls, handles contiguous/non-contiguous cases, creates new Bottom block.

Tree Maintenance (t_splay, t_delete)

Bottom-up splaying on access (in search/delete). Macro-based rotations for zig/zig-zig cases. Supports lists of equal-sized blocks within tree nodes (via LINKFOR/LINKBAK).

Undocumented or IRIX-Specific Interfaces and Behaviors

Critical Structures for ABI Compatibility (from mallint.h)

Exact layout must match for binary compatibility; block headers overlap user data minimally.

TREE (block header, placed before user data):

size_t SIZE field in low bits: actual size + flags (BIT0 busy, BIT1 previous free).

Tree fields: TREE *LEFT, RIGHT, PARENT. List fields: TREE *LINKFOR, LINKBAK (for equal-size doubly-linked lists).

Self-pointer at end of block for validation. Macros: DATA(tp) (user pointer), BLOCK(p) (header from user), NEXT(tp), LAST(tp), BOTTOM(tp), etc.

Global state:

TREE *Root — splay tree root.

TREE *Bottom — last chunk at arena end.

char *Baddr — current break address.

char *Lfree — last freed pointer (data intact).

VOID *flist[FREESIZE] + int freeidx — delayed free ring buffer.

TREE *List[MINSIZE/WORDSIZE-1] — small block free lists.

History vars: coresizemask, corecalls.

Constants/macros: WORDSIZE — typically 8 (64-bit) or 4.

ALIGN — same as WORDSIZE. MINSIZE — threshold for small lists (often 40-48 bytes).

BIT0 (busy), BIT1 (prev free), BITS01.

Delayed Free Mechanism

Unique to this implementation: free rarely calls realfree immediately. Instead buffers pointers in flist (preserves data in freed blocks). Next allocation frees buffered blocks (except possibly current realloc target). Enables optimizations assuming freed data undisturbed briefly.

Splay Tree with Equal-Size Lists

Free blocks ordered by size in splay tree. Equal-size blocks form doubly-linked lists within tree nodes (using extra fields). Insertion leaf-only; splaying on search/delete for amortization.

Other Behaviors

malloc(0) returns unique pointer (size WORDSIZE).

Aggressive coalescing forward/backward on free.

No mmap for large blocks (pure sbrk).

Thread-safe via optional locks (__LOCK_MALLOC).

Special sgi page-end allocation adjustment.

Similarities to illumos and BSD libc Implementations

To enable reimplementation via modified illumos/BSD sources:

illumos libc (malloc.c in libc or watchmalloc)

Extremely close — IRIX derived from same SVR4 lineage as Solaris/illumos:

Nearly identical structure: splay tree + small lists + coalescing + delayed free via flist/Lfree.

Same functions: realfree, t_splay, t_delete, _morecore.

Identical delayed free ring buffer and cleanfree.

Same small-block batching with history bits.

Minor differences: illumos evolved (better thread support, umem alternative); may use mmap for large allocs.

For reimplementation: illumos malloc.c is virtually the same base. Adjust MIPS alignment/constants, ensure exact header layout/macros, preserve delayed free and splay details.

BSD libc (jemalloc or legacy)

More divergent:

Modern FreeBSD/NetBSD use jemalloc (arena-per-thread, red-black trees, extensive caching).

Older BSD had simpler first-fit or dlmalloc-derived.

No splay trees, no delayed free ring, different coalescing.

jemalloc highly tuned for multi-thread, low fragmentation.

For reimplementation: BSD sources less suitable as base; useful for ideas on thread arenas or modern features, but require major rewrite to match IRIX splay/delayed behavior.

Overall, illumos/Solaris-derived malloc is the closest match for direct porting due to shared System V heritage and near-identical internals. Combine with IRIX specifics for exact ABI/behavior replication. Verify against mallint.h equivalents and test with IRIX binaries.