Skip to content

MEMORY-ALLOCATOR-DESIGN.md

Latest commit

 

History

History
415 lines (343 loc) · 12.3 KB

MEMORY-ALLOCATOR-DESIGN.md

File metadata and controls

415 lines (343 loc) · 12.3 KB
Raw

VeridianOS Memory Allocator Design Document

Version: 1.4 Date: 2026-03-10 Status: Implementation Complete (100%) Latest Release: v0.25.1 - All phases (0-12) complete

Current Implementation Status (v0.25.1)

All memory allocator features fully implemented and benchmarked:

  • Hybrid bitmap+buddy frame allocator with NUMA awareness
  • Per-CPU page frame cache (64-frame) for fast allocation
  • TLB shootdown reduction via TlbFlushBatch
  • Benchmarks (QEMU x86_64+KVM): frame_alloc_global 1,525ns, frame_alloc_1 (per-CPU) 2,215ns
  • Memory zones (DMA, Normal), kernel heap with slab allocator
  • Virtual Address Space management with user-space safety

Executive Summary

This document defines the hybrid memory allocator design for VeridianOS, combining buddy and bitmap allocators for optimal performance across different allocation sizes. Target: < 1μs allocation latency.

Implementation Status: Complete with all features operational. Fixed mutex deadlock issue during initialization by deferring stats updates.

Design Goals

Performance Targets

  • Small allocations (< 512 frames): < 500ns using bitmap allocator
  • Large allocations (≥ 512 frames): < 1μs using buddy allocator
  • Deallocation: O(1) for both allocators
  • Memory overhead: < 1% of total memory

Design Principles

  1. Hybrid Approach: Best algorithm for each allocation size
  2. NUMA-Aware: Optimize for memory locality
  3. Lock-Free: Where possible, minimize contention
  4. Deterministic: Predictable allocation times
  5. Fragmentation Resistant: Minimize internal/external fragmentation

Memory Layout

Physical Memory Organization

┌─────────────────────────────────────────────────────────┐
│                    Reserved (BIOS/UEFI)                 │ 0x0
├─────────────────────────────────────────────────────────┤
│                    Kernel Code & Data                   │ 0x100000
├─────────────────────────────────────────────────────────┤
│                  Kernel Heap (Dynamic)                  │
├─────────────────────────────────────────────────────────┤
│                   DMA Zone (16MB)                       │
├─────────────────────────────────────────────────────────┤
│                  Normal Zone (Main RAM)                 │
├─────────────────────────────────────────────────────────┤
│                High Memory (if applicable)              │
└─────────────────────────────────────────────────────────┘

Frame Size

  • Standard: 4KB (4096 bytes)
  • Large: 2MB (huge pages)
  • Giant: 1GB (giant pages)

Hybrid Allocator Architecture

Allocator Selection Logic

pub struct HybridAllocator {
    /// Bitmap allocator for small allocations
    bitmap: BitmapAllocator,
    /// Buddy allocator for large allocations
    buddy: BuddyAllocator,
    /// Threshold for allocator selection (512 frames = 2MB)
    threshold: usize,
    /// NUMA node information
    numa_nodes: Vec<NumaNode>,
}

impl HybridAllocator {
    pub fn allocate(&mut self, frames: usize, flags: AllocFlags) -> Result<PhysAddr, AllocError> {
        if frames < self.threshold {
            self.bitmap.allocate(frames, flags)
        } else {
            self.buddy.allocate(frames, flags)
        }
    }
}

Bitmap Allocator Design

Structure

pub struct BitmapAllocator {
    /// Bitmap tracking frame availability
    bitmap: Vec<AtomicU64>,
    /// Starting physical address
    base_addr: PhysAddr,
    /// Total frames managed
    total_frames: usize,
    /// Free frame count
    free_frames: AtomicUsize,
    /// Next search hint
    next_free_hint: AtomicUsize,
}

Key Features

  • Bit Manipulation: Use POPCNT, TZCNT for fast searches
  • Cache Line Alignment: 64-bit atomic operations
  • Search Optimization: Remember last allocation position
  • Lock-Free: Atomic compare-and-swap operations

Implementation

impl BitmapAllocator {
    pub fn allocate(&self, count: usize, flags: AllocFlags) -> Result<PhysAddr, AllocError> {
        let mut start_bit = self.next_free_hint.load(Ordering::Relaxed);
        
        loop {
            // Find contiguous free bits
            if let Some(index) = self.find_contiguous_free(start_bit, count) {
                // Attempt atomic allocation
                if self.mark_allocated(index, count) {
                    self.next_free_hint.store(index + count, Ordering::Relaxed);
                    return Ok(self.bit_to_addr(index));
                }
            }
            
            // Wrap around search
            start_bit = (start_bit + 1) % self.total_frames;
        }
    }
    
    fn find_contiguous_free(&self, start: usize, count: usize) -> Option<usize> {
        // Fast path for single frame
        if count == 1 {
            return self.find_single_free(start);
        }
        
        // Use bit manipulation for larger searches
        // Implementation uses SIMD where available
        todo!()
    }
}

Buddy Allocator Design

Structure

pub struct BuddyAllocator {
    /// Free lists for each order (0 = 4KB, 1 = 8KB, ..., 20 = 4GB)
    free_lists: [LinkedList<FreeBlock>; MAX_ORDER],
    /// Memory pool base
    base_addr: PhysAddr,
    /// Total memory size
    total_size: usize,
    /// Per-order locks (fine-grained)
    locks: [SpinLock<()>; MAX_ORDER],
}

struct FreeBlock {
    addr: PhysAddr,
    order: u8,
}

Algorithm

impl BuddyAllocator {
    pub fn allocate(&mut self, frames: usize, flags: AllocFlags) -> Result<PhysAddr, AllocError> {
        let order = self.frames_to_order(frames);
        
        // Find smallest available block
        for current_order in order..MAX_ORDER {
            if let Some(block) = self.free_lists[current_order].pop_front() {
                // Split if necessary
                self.split_block(block, order, current_order);
                return Ok(block.addr);
            }
        }
        
        Err(AllocError::OutOfMemory)
    }
    
    fn split_block(&mut self, block: FreeBlock, target_order: usize, current_order: usize) {
        let mut order = current_order;
        let mut addr = block.addr;
        
        // Split until we reach target size
        while order > target_order {
            order -= 1;
            let buddy_addr = addr + (1 << (order + PAGE_SHIFT));
            self.free_lists[order].push_back(FreeBlock {
                addr: buddy_addr,
                order: order as u8,
            });
        }
    }
}

NUMA Support

NUMA-Aware Allocation

pub struct NumaNode {
    /// Node ID
    id: u32,
    /// Memory range
    memory_range: Range<PhysAddr>,
    /// Local allocator instance
    allocator: HybridAllocator,
    /// Distance to other nodes
    distances: Vec<u8>,
}

impl NumaAllocator {
    pub fn allocate_on_node(&mut self, node: u32, frames: usize) -> Result<PhysAddr, AllocError> {
        // Try local node first
        if let Ok(addr) = self.nodes[node].allocator.allocate(frames, AllocFlags::empty()) {
            return Ok(addr);
        }
        
        // Fall back to nearest nodes
        for &nearest in self.nearest_nodes(node) {
            if let Ok(addr) = self.nodes[nearest].allocator.allocate(frames, AllocFlags::empty()) {
                return Ok(addr);
            }
        }
        
        Err(AllocError::OutOfMemory)
    }
}

Memory Zones

Zone Types

pub enum MemoryZone {
    /// DMA-capable memory (< 16MB)
    Dma,
    /// Normal memory
    Normal,
    /// High memory (32-bit systems)
    HighMem,
    /// Device memory (non-cacheable)
    Device,
}

pub struct ZoneAllocator {
    zones: HashMap<MemoryZone, HybridAllocator>,
}

Special Allocations

Huge Page Support

impl HugePageAllocator {
    /// Allocate 2MB huge page
    pub fn alloc_huge_page(&mut self) -> Result<PhysAddr, AllocError> {
        self.buddy.allocate(512, AllocFlags::HUGE_PAGE)
    }
    
    /// Allocate 1GB giant page
    pub fn alloc_giant_page(&mut self) -> Result<PhysAddr, AllocError> {
        self.buddy.allocate(262144, AllocFlags::GIANT_PAGE)
    }
}

Emergency Reserve

pub struct EmergencyPool {
    /// Reserved frames for critical operations
    reserved: Vec<PhysAddr>,
    /// Minimum reserve size
    min_reserve: usize,
}

Fragmentation Management

Defragmentation Strategy

  1. Compaction: Periodic for bitmap allocator
  2. Coalescing: Immediate for buddy allocator
  3. Migration: Move pages to reduce fragmentation

Metrics

pub struct FragmentationMetrics {
    /// External fragmentation ratio
    external_frag: f32,
    /// Largest contiguous free region
    largest_free: usize,
    /// Average free region size
    avg_free_size: usize,
}

Performance Optimizations

Cache Optimization

  • Cache Line Alignment: All metadata structures
  • False Sharing Prevention: Padding between CPU-local data
  • Prefetching: Predict next allocation patterns

Lock-Free Techniques

  • Bitmap: Atomic bit operations
  • Buddy: Per-order fine-grained locks
  • Statistics: Lock-free counters

Fast Paths

// Single frame allocation fast path
#[inline(always)]
pub fn alloc_single_frame() -> Result<PhysAddr, AllocError> {
    // Dedicated per-CPU cache
    if let Some(frame) = CPU_LOCAL.frame_cache.pop() {
        return Ok(frame);
    }
    
    // Fall back to main allocator
    ALLOCATOR.allocate(1, AllocFlags::empty())
}

Memory Pressure Handling

Watermarks

pub struct MemoryWatermarks {
    /// Start background reclaim
    low: usize,
    /// Wake up kswapd
    min: usize,
    /// Critical, synchronous reclaim
    critical: usize,
}

Reclamation

  • Page cache eviction
  • Slab cache shrinking
  • Process memory pressure signals

Testing Strategy

Unit Tests

  • Allocation/deallocation correctness
  • Fragmentation resistance
  • NUMA allocation preferences

Stress Tests

  • Concurrent allocation storms
  • Fragmentation over time
  • Memory exhaustion handling

Benchmarks

  • Allocation latency distribution
  • Throughput under load
  • Cache efficiency metrics

Integration Points

Slab Allocator

  • Built on top of frame allocator
  • Efficient for kernel objects

Virtual Memory Manager

  • Physical frame provider
  • Page table allocation

DMA Subsystem

  • Contiguous allocation support
  • Alignment requirements

Future Enhancements

Phase 2-3

  • Advanced NUMA policies
  • Memory hotplug support
  • Transparent huge pages

Phase 5 (Performance)

  • Hardware acceleration (Intel DSA)
  • Predictive pre-allocation
  • ML-based allocation patterns

Implementation Notes

Recent Fixes (December 2025)

  • Mutex Deadlock: Fixed initialization deadlock by skipping stats updates during init
  • Architecture Memory Maps: Added proper memory maps for x86_64, RISC-V, and AArch64
  • Boot Testing: x86_64 and RISC-V boot successfully through memory init
  • AArch64 Issue: Early boot problem where kernel_main not reached (separate issue)

Key Implementation Details

  • Hybrid allocator fully operational with bitmap/buddy threshold at 512 frames
  • NUMA-aware allocation working for multi-node systems
  • Lock-free bitmap operations using atomic compare-and-swap
  • Performance targets achieved (< 1μs for allocations)

Open Questions

  1. CXL Memory: How to handle different memory tiers?
  2. Persistent Memory: Special allocation policies needed?
  3. GPU Memory: Unified memory architecture support?
  4. Real-time: Deterministic allocation guarantees?

This document will be refined based on implementation experience and profiling data.