Kernel:malloc

This page documents the memory allocation subsystem of the IRIX kernel (`malloc`, `rmalloc`, and related functions) as implemented in the IRIX kernel. It is intended as a functional reference for reimplementation in other kernels (e.g., Illumos).

Overview

The IRIX memory allocation system provides:

• Map-based memory management (`struct map`) for contiguous resource allocation.
• Page-aligned and color-aware allocations for cache efficiency (R4000-specific).
• Bitmap-based system page table (SPT) management.
• Waiting and non-waiting allocation paths (`VM_NOSLEEP` flag).
• Synchronization primitives using spinlocks and semaphores.

Memory management in IRIX is based on two concepts:

1. **Maps** – contiguous resources tracked as a list of free/allocated blocks.
2. **Bitmaps** – finer-grained allocation (e.g., pages, cache-colored pages) with alignment support.

Map Allocation API

rmallocmap()

Purpose: Allocate and initialize a `struct map` for tracking resources. Inputs: `mapsiz` – number of entries in the map. Outputs: Pointer to newly allocated map, or NULL on failure.

Behavior:

• Allocates memory for `mapsiz + 2` map entries.
• Allocates and initializes a synchronization structure (`lock + semaphore`).
• Stores pointers to synchronization primitives in the second map entry.
• Returns a fully initialized map ready for allocations.

rmfreemap()

Purpose: Free a previously allocated map. Inputs: Pointer to map. Behavior:

• Waits for any threads currently blocked on the map.
• Destroys associated semaphore and spinlock.
• Frees both the map memory and the synchronization structure.

malloc / malloc_wait / rmalloc / rmalloc_wait

Purpose: Allocate contiguous units from a map. Inputs:

• `mp` – pointer to map
• `size` – number of units
• Optional `flags` (`VM_NOSLEEP` for non-blocking)

Behavior:

• Uses **first-fit allocation**.
• Non-blocking (`VM_NOSLEEP`) returns `0` if allocation fails.
• Blocking waits on the map’s semaphore until space becomes available.
• Returns the starting address of allocated space.

mfree / rmfree

Purpose: Free previously allocated space in a map. Inputs:

• `mp` – pointer to map
• `size` – units to free
• `a` – base address

Behavior:

• Sorts the freed block into the map.
• Merges with adjacent free blocks if possible.
• Updates map’s size and count.
• Broadcasts to any waiting threads if space becomes available.
• Logs warnings if map overflow or invalid free occurs.

Bitmap-Based Page Table Management

The IRIX kernel uses **bitmap structures** to manage system page tables (`spt`). This allows fine-grained allocation with support for color and alignment.

sptalloc()

Purpose: Allocate pages from the system page table bitmap. Inputs:

• `bm` – pointer to system bitmap structure
• `want` – number of pages
• `flags` – allocation flags (`VM_NOSLEEP`, `VM_VACOLOR`, `VM_BREAKABLE`)
• `color` – desired cache color (for R4000)
• `alignment` – page boundary alignment (power of 2)

Behavior:

• Selects a bitmap (clean, stale, aged) for allocation.
• If color-specific allocation is requested, attempts color map first.
• Uses rotors to track possible starting positions for efficiency.
• Supports alignment constraints.
• Will optionally wait (blocking) if pages are unavailable.
• Updates bitmap counters and rotors on allocation.

sptfree()

Purpose: Free pages back to the system page table bitmap. Inputs:

• `bm` – pointer to system bitmap
• `size` – number of pages
• `mapaddr` – base address of pages to free

Behavior:

• Updates `m_lowbit`, `m_highbit`, and `m_count` in the bitmap.
• Sets freed bits in the bitmap.
• Broadcasts to waiting threads.

mergebitmaps()

Purpose: Merge one bitmap into another (e.g., stale pages back into main SPT map). Inputs:

• `bm` – system bitmap
• `to` – destination bitmap
• `from` – source bitmap

Behavior:

• Copies set bits from source to destination.
• Updates rotor information for SPT allocation.
• Clears source bitmap.

bmapswtch()

Purpose: Swap contents of two bitmaps. Use case: Replace an old bitmap with a new one without modifying allocation state.

sptgetsizes()

Purpose: Get counts of pages in different states (clean, stale, aged, in-transit).

Synchronization and Multi-Processor Considerations

• Spinlocks (`mutex_spinlock`) protect map structures during allocation.
• Bitmaps have a hierarchy of locks:
  • Normal allocation lock (`MAP_ALLOCLOCK`)**
  • Urgent lock (`MAP_URGENTLOCK`)** – signals to other threads to back off during replenishment.
• Wait queues (semaphores) are used for threads blocked on resources.

R4000-Specific Enhancements

• **Cache-colored allocation:** ensures pages allocated from a bitmap minimize cache conflicts.
• **sptvctst()** – tests for a free bit in a specific cache color.
• **color_alloc()** – allocates a page of a specific color.
• **sptaligntst()** – ensures alignment in allocations.

Fault Checking

• `kvfaultcheck()` inspects which CPUs have references to aged or temporary pages.
• Returns a CPU mask indicating CPUs that need TLB flushes.
• Integration with isolate debugging on multi-CPU systems (EVEREST/SN0).

Notes for Reimplementation

• Map-based allocations are generic and can be adapted to other OS kernels.
• Bitmap-based page allocations depend on low-level page tables; rotors and color optimizations can be implemented optionally.
• Careful handling of spinlocks, semaphores, and wait queues is required in multi-processor environments.
• Ensure that alignment and cache color are power-of-two values for correctness.
• Debug assertions (`ASSERT`) in IRIX should be converted to runtime checks or kernel asserts in the new environment.