Mem C (mem-c)

Table of Contents

1. Overview
2. Installation
3. Getting Started
   • Basic Allocation and Freeing
   • Other Functions
4. Debugging Features
5. Performance
6. License

Overview

mem-c is a simple memory allocator that uses a heap data structure with the mmap Linux syscall to manage dynamic memory allocation, just for educational purpose. The current implementation has a worst-case time complexity of O(n * log n) for chunk searches, but in average cases, it achieves O(log n) runtimes.

The allocator is designed to support various memory management features, memory pagination, chunk merging, and future plans for more sophisticated functionalities like garbage collection and arenas (user-defined memory spaces). The project is still evolving, and further optimizations are planned.

Currently, the allocator likely only works on 64-bit CPU machines.

Installation

At the moment, this package is not yet available in the AUR but may be in the future. For now, you can install mem-c manually via the following steps:

1. Clone the project or download a relesed version of the project:

   git clone <repository-url>
   cd mem-c

2. Build and install the package using makepkg:

   makepkg -si

This will compile the project and install it on your Arch Linux system. If you are using a different distribution, you can run:

1. Run make with the compilation

   make compile
   

2. Then, install the header file and the library:

   cp include/mem.h /path/you/want/to/install
   cp build/lib/libmem.so /path/you/want/to/install
   

Getting Started

To get started using mem-c, include the mem.h header in your project and follow the examples below.

Basic Allocation and Freeing

To allocate memory for a pointer and free it after usage:

#include <mem.h>

struct Person {
    char name[100];
    int age;
};

int main(void)
{
    strcut Person *ptr;

    // Allocate memory for a new struct Person, with the macro `NEW`
    NEW(ptr);

    // Use the allocated memory
    ptr->age = 10;

    // More code here ...

    // Free the allocated memory, with the macro `FREE`
    FREE(ptr);

    return 0;
}

Compiling

To compile your code, you must link the library using the -lmem flag:

cc yourcode.c -lmem

Other Functions

mem-c provides several other functions for memory management:

• mem_alloc: Allocates a specified number of bytes.
• mem_ralloc: Reallocates memory for a given address.
• mem_calloc: Allocates memory for an array of objects, initializing them to zero.
• mem_free: Frees memory associated with a given address.

Example usage:

#include <mem.h>

int main(void)
{
    int *array;

    // Allocate memory for an array of 10 integers, initialized to zero
    array = mem_calloc(sizeof(int), 10);

    // More code here ...

    // Resize the memory block
    array = mem_ralloc(array, sizeof(int) * 20);

    // More code here ...

    // Free the allocated memory
    mem_free(array);

    return 0;
}

Debugging Features

In debug mode (enabled when NDEBUG is not defined), mem-c offers additional features to monitor memory usage and detect issues:

• mem_dbg_fetch_mem_stats: Retrieves statistics about memory usage and chunks. It also logs this information to the given file descriptor based on the specified verbosity level.

  • Level 0 will not print anything.
  • Level 1 will print only the main statistics.
  • Level 2 will print all pages and their information.
  • Level 3 will print each allocated chunk.

  The verbosity is given as the second argument, and the third argument will be the file descriptor.

• mem_dbg_verify_ds_integrity: Verifies the integrity of the heap data structure.

• mem_dbg_is_freeded: Checks if a specific address has already been freed, useful for asserting addresses.

Debugging example:

#include <mem.h>


void foo(void *ptr)
{
    assert(!mem_dbg_is_freeded(ptr), "Should be able to be used");

    // Do something with that pointer ...
}


int main(void)
{
    MemStats_T stats;

    // Several allocations here ...

    // Fetch memory stats. This will log information at verbosity level 1 and output it to file descriptor 1 (stdout).
    mem_dbg_fetch_mem_stats(&stats, 1, 1);

    // Verify data structures integrity
    mem_dbg_verify_ds_integrity();

    // Free all the allocs ...

    return 0;
}

Performance

In this section, we present the charts showing how the allocator is currently performing. Using scatter charts, I applied polynomial regressions to visualize the trends. Several important observations can be made:

• Time Complexity: We can see that time complexity is linear, likely because of the O(n * log n) operations. I plan to make optimizations to improve this. It's also worth noting that the release version is almost three times faster than the debug version.

• Memory Management: A key point is how the allocator handles memory. I need to reserve extra memory to manage dynamic allocations. This extra memory is not directly used by the user, and as shown in the chart, the allocator's memory management follows a logarithmic behavior. Both the raw and percentage representations of this memory are presented. As the user allocates more memory, the extra memory used to manage those allocations becomes negligible compared to the total allocated memory.

• Freed Chunks: For each allocation, the allocator creates chunks. Due to how memory works, I can't simply release or stop using these chunks because of pagination. Instead, I mark these chunks as freed to reuse them later. The last two charts illustrate how, with more and larger allocations, the number of freed chunks decreases, keeping more allocated chunks in memory.

Debug Version Charts

Here are the charts for the debug version of the allocator:

Released Version Charts

Here are the charts for the release version of the allocator:

License

This project is licensed under the MIT License. See the LICENSE file for more details.