x86 Assembly Memory Allocator

memory-sim is a memory management system simulation written in x86 Assembly (AT&T syntax). The project implements a block-based memory allocator capable of handling contiguous storage operations, memory mapping, and defragmentation on a virtual heap.

It demonstrates fundamental concepts of computer architecture, direct memory addressing, stack frame management, and storage allocation algorithms.

Features

The project consists of two main components representing different memory models:

1. One-Dimensional Allocator (Linear Heap)

• Contiguous Allocation: Implements a First Fit strategy to allocate blocks in a linear vector.
• File Descriptors: Manages files using unique IDs (0-255).
• CRUD Operations: Supports adding, retrieving, and deleting files from the virtual memory.
• Defragmentation: Implements a compaction algorithm to eliminate external fragmentation by moving allocated blocks to the beginning of the memory space.

2. Two-Dimensional Allocator (Matrix Mapping)

• Matrix Mapping: Manages memory as a 1024x1024 grid of blocks.
• 2D Allocation: Maps files onto specific lines within the matrix structure.
• Coordinate System: Retrieves file locations using ((row, start_col), (row, end_col)) format.
• 2D Defragmentation: Reorganizes blocks within the matrix to ensure data compactness.

Prerequisites

To build and run this project, you need a Linux environment with support for 32-bit compilation:

• GCC (GNU Compiler Collection)
• 32-bit development libraries (e.g., gcc-multilib)

Installing Dependencies (Debian/Ubuntu)

sudo apt-get update
sudo apt-get install gcc-multilib

Build Instructions

The project is split into two independent tasks corresponding to the memory models.

Compiling the 1D Allocator

gcc -m32 task00.s -o task00

Compiling the 2D Allocator

gcc -m32 task01.s -o task01

Usage

The program interacts via STDIN and outputs to STDOUT. It is recommended to use input files for testing complex operation sequences.

Running with Input Redirection

./task1 < input.txt

Operation Codes

The system accepts a sequence of numerical commands:

Code	Operation	Description
1	ADD	Allocates memory for N files (followed by ID and Size).
2	GET	Retrieves the allocation interval for a file ID.
3	DELETE	Frees the memory blocks associated with a file ID.
4	DEFRAG	Compacts the memory to remove gaps.

Example Input

4
1
1
12 10
2
12
3
12
4          

Explanation: 4 operations total. 1 (ADD) one file with ID 12 and size 10KB. 2 (GET) location of ID 12. 3 (DELETE) ID 12. 4 (DEFRAGMENT) memory.

File Structure

• task00.s - Source code for the linear (1D) memory allocator.
• task01.s - Source code for the matrix (2D) memory allocator.

Technical Implementation Details

This project operates directly on the CPU's registers and memory without high-level abstractions. Key implementation highlights include:

1. Memory Management & Addressing

• The simulation uses a reserved .data section via the .space directive to act as the memory heap, avoiding system-level malloc overhead.
• Since x86 memory is linear, the 2D matrix (1024x1024) is flattened. Access to element matrix[row][col] is calculated manually using Row-Major Order: Address = Base + (RowIndex * 1024) + ColIndex

2. Stack Frame & ABI Compliance

• The program manually constructs stack frames to interface with the C standard library (libc).
  • Arguments for printf, scanf, and fflush are pushed onto the stack in reverse order.
  • The stack pointer %esp is manually adjusted (e.g., addl $16, %esp) after calls to clean up the stack.
• Callee-saved registers (%ebx, %esi, %edi, %ebp) are pushed/popped across function calls to maintain state integrity, adhering to the 32-bit x86 ABI.

3. Algorithms

• Implements a First Fit algorithm. The allocator scans the memory array linearly to find the first sequence of free blocks large enough to hold the requested file.
• Utilizes an in-place compaction algorithm. It iterates through the memory, shifting used blocks to the lower addresses while preserving their relative order, effectively merging all free space at the end of the heap.

License

This project is open-source and available under the MIT License.