Copyright Cretu Mihnea Tudor 315CAa 2022 - 2023

1st Homework for Data Structures and Algorithms Class, Year I - Faculty of Automation Control and Computer Science, Polytechnic University of Bucharest

Virtual Memory Allocator

1) Introduction:

This program uses doubly linked lists to mimic a real memory allocator. The program uses a virtual arena with a given size in which the memory blocks and their respective miniblock lists will be allocated in. The arena itself and all of its components have been allocated dinamically in memory, thus the arena has to be deallocated from the memory before exiting the program. The information stored in the memory can be of any data type.

2) Installation:

Download or clone the repository to your local machine.

Navigate to the root directory of the project in your terminal.

Run the command make build to build the program

Once the build is successful, you can run the program by using the command ./vma

To clean the generated files from the build process, use the command make clean

3) Usage

ALLOC_ARENA {size}

-> needs to be the first command written in the terminal; this command initialises the virtual arena and implies that all the memory blocks written afterwards need to be allocated inside it

DEALLOC_ARENA

-> frees all the memory used by the arena and all of the blocks inside of it, including the data stored in them

ALLOC_BLOCK {start_address} {size}

-> allocates size bytes of memory in the arena, starting from the start_address. Each block has a miniblock list implemented in which the block is divided in more miniblocks that start at the start_addressand all of their sizes added up are equal to the block's size.

NOTE: There are 3 cases of using this command that modifies the structure of the blocks:

-> block connects to the right side of another: miniblock is added to the end of left-side block's miniblock list and its size is now equal to the sum of both block's sizes;

-> block connects to the left side of another: miniblock is added to the start (head) of right-side block's miniblock list, its size is now equal to the sum of both block's sizes and the start address is now equal to the left-side block's start address;

-> block connects between 2 other blocks: miniblock is added in the middle of the left-side block's miniblock list, the miniblocks from the right side block's miniblock list get transferred at the end of left-side block's miniblock list and the right-side block is removed; at the end of this process there remains one single block with the size of all the previous blocks and 3 miniblocks in its list;

FREE_BLOCK {start_address}

-> frees the miniblock and all its data allocated at the start_address:

-> if the miniblock is the only one in the list, it removes its corresponding block with it;

-> if the miniblock is nor at the start, nor at the end of the list, the miniblock will be deleted and all the miniblocks after the deleted one will make up a new block with a new list;

WRITE {address} {size} {data}

-> writes size bytes of data starting at the address;

-> the data will be automatically continued to another miniblock of the list if the miniblock's memory will be occupied;

NOTE: if the writing size is bigger than the remaining size of the block corresponding with the address, only the available writing size will be used and the remaining data will not be written;

READ {address} {size} {data}

-> reads size bytes of data starting at the address;

NOTE: if the reading size is bigger than the remaining size of the block corresponding with the address, only the available reading size will be read

PMAP

-> shows all the useful information regarding the memory, displays all the blocks, their lists of miniblocks and the miniblocks' permissions (READ, WRITE, EXECUTE)

MPROTECT {change_permission}

-> the default permissions for the miniblocks are RW- (READ and WRITE)

The permissions can be changed by using these commands:

-> PROT_NONE, PROT_READ, PROT_WRITE, PROT_EXECUTE

NOTE: The READ and WRITE permissions have direct connection with the READ and WRITE commands. Without these permissions the commands.

4) Examples

ALLOC_ARENA 50

ALLOC_BLOCK 20 5

ALLOC_BLOCK 10 3

ALLOC_BLOCK 17 2

ALLOC_BLOCK 13 4

ALLOC_BLOCK 25 2

ALLOC_BLOCK 35 4

PMAP

PMAP OUTPUT:

Total memory: 0x32 bytes

Free memory: 0x1E bytes

Number of allocated blocks: 3

Number of allocated miniblocks: 6

Block 1 begin

Zone: 0xA - 0x13

Miniblock 1: 0xA - 0xD | RW-

Miniblock 2: 0xD - 0x11 | RW-

Miniblock 3: 0x11 - 0x13 | RW-

Block 1 end

Block 2 begin

Zone: 0x14 - 0x1B

Miniblock 1: 0x14 - 0x19 | RW-

Miniblock 2: 0x19 - 0x1B | RW-

Block 2 end

Block 3 begin

Zone: 0x23 - 0x27

Miniblock 1: 0x23 - 0x27 | RW-

Block 3 end

FREE_BLOCK 25

WRITE 13 10 helloworld

WRITE OUTPUT:

Warning: size was bigger than the block size. Writing 6 characters.

READ 13 6

READ OUTPUT:

hell

DEALLOC_ARENA

5) Troubleshooting

-> ALLOC_ARENA needs to be the first used command

-> Can't free a block which wasn't allocated previously

-> Can't read a block which wasn't written in previously

-> Can't allocate memory in a zone already allocated

-> Can't allocate memory in a zone bigger than the arena

-> In case of MPROTECT applied, can't do an operation without the necessary permission (e.g. READ on a block with -WX permissions)

6) Technical Details

All the functions and methods used for making or using this program are detailed in the source code, the functions are explained in vma.c and the data structures used are explained in vma.h.