Implementing a Simple Memory Allocator in Rust

Memory allocation is a fundamental concept in systems programming. In this tutorial, we'll implement a simple memory allocator in Rust. This will help you understand how memory management works at a low level.

Understanding Memory Allocation

A memory allocator is responsible for managing dynamic memory allocation and deallocation. Our simple allocator will:

1. Manage a fixed-size block of memory
2. Track allocated and free blocks
3. Handle allocation and deallocation requests

Basic Structure

Let's start by defining our allocator's structure:

use std::ptr::NonNull;

pub struct SimpleAllocator {
    memory: Vec<u8>,
    free_list: Vec<Block>,
}

struct Block {
    size: usize,
    is_free: bool,
    start: usize,
}

Here's what each component does:

• memory: A vector that represents our heap memory
• free_list: Tracks free memory blocks
• Block: Represents a memory block with its size, status, and starting position

Implementation

Let's implement the core functionality:

impl SimpleAllocator {
    pub fn new(size: usize) -> Self {
        SimpleAllocator {
            memory: vec![0; size],
            free_list: vec![Block {
                size,
                is_free: true,
                start: 0,
            }],
        }
    }

    pub fn allocate(&mut self, size: usize) -> Option<NonNull<u8>> {
        // Find a suitable free block
        let block_index = self.free_list.iter().position(|block| 
            block.is_free && block.size >= size
        )?;

        let block = &mut self.free_list[block_index];
        let start = block.start;
        
        // Split the block if it's larger than needed
        if block.size > size {
            let new_block = Block {
                size: block.size - size,
                is_free: true,
                start: start + size,
            };
            block.size = size;
            self.free_list.insert(block_index + 1, new_block);
        }

        block.is_free = false;
        unsafe { Some(NonNull::new_unchecked(&mut self.memory[start] as *mut u8)) }
    }

    pub fn deallocate(&mut self, ptr: NonNull<u8>) {
        let start = unsafe { ptr.as_ptr() as usize - self.memory.as_ptr() as usize };
        
        // Find the block containing this pointer
        if let Some(block_index) = self.free_list.iter().position(|block| 
            block.start == start
        ) {
            let block = &mut self.free_list[block_index];
            block.is_free = true;
            
            // Merge with adjacent free blocks
            self.merge_adjacent_blocks();
        }
    }

    fn merge_adjacent_blocks(&mut self) {
        let mut i = 0;
        while i < self.free_list.len() - 1 {
            let current = &self.free_list[i];
            let next = &self.free_list[i + 1];
            
            if current.is_free && next.is_free && 
               current.start + current.size == next.start {
                self.free_list[i].size += next.size;
                self.free_list.remove(i + 1);
            } else {
                i += 1;
            }
        }
    }
}

Using the Allocator

Here's how to use our simple allocator:

fn main() {
    let mut allocator = SimpleAllocator::new(1024); // 1KB of memory
    
    // Allocate some memory
    if let Some(ptr) = allocator.allocate(100) {
        unsafe {
            // Use the allocated memory
            let slice = std::slice::from_raw_parts_mut(ptr.as_ptr(), 100);
            slice[0] = 42;
            
            // Deallocate when done
            allocator.deallocate(ptr);
        }
    }
}

Explanation of Key Concepts

1. Memory Block Management:

   • Each block tracks its size, status (free/allocated), and starting position
   • The free list maintains all available memory blocks

2. Allocation Strategy:

   • First-fit algorithm: finds the first block large enough for the request
   • Splits blocks if they're larger than needed
   • Returns a pointer to the allocated memory

3. Deallocation:

   • Marks blocks as free
   • Merges adjacent free blocks to prevent fragmentation
   • Uses pointer arithmetic to find the correct block

Limitations and Improvements

This is a basic implementation with several limitations:

• No alignment handling
• No thread safety
• Fixed-size memory pool
• Simple first-fit allocation strategy

To improve this allocator, you could:

1. Add alignment support
2. Implement thread safety
3. Use more sophisticated allocation strategies
4. Add memory pooling for different size classes

Conclusion

This tutorial demonstrated a basic memory allocator implementation in Rust. While simple, it illustrates the core concepts of memory management. Understanding these fundamentals is crucial for systems programming and can help you write more efficient code.

Remember that Rust's standard library provides a robust memory allocator, and you should use it in production code. This implementation is for educational purposes to understand the underlying concepts.