Tbman - Fast and Easy Memory Manager

Table of Content

• What it is
• Benefits
• How to use it
• Detailed Description
  • Basics
  • Faster collection
  • One function for everything
  • Advanced Alignment
  • Granted Memory
  • Diagnostic Features
  • Thread safety
  • Multiple managers
  • Mixing different memory managers
• Side effects
  • Prefetching
  • Unused Memory
  • Memory Model
  • Debugging Tools
• How it works internally
• Motivation/Origin

<a name="anchor_what_it_is"></a>

What it is

Tbman is a general-purpose memory manager offering (among others) these functions

tbman_malloc, tbman_free, tbman_realloc,

which can replace corresponding stdlib functions

malloc, free, realloc,

in C and C++ code.

<a name="anchor_benefits"></a>

Benefits

• Very fast. (You can easily verify this yourself.)
• Low fragmentation of system memory.
• Few system calls.
• Advanced Alignment.
• Integrated Leak Detection
• Diagnostic Features
• Granted Memory
• Platform Independence

<a name="anchor_how_to_use_it"></a>

How to use it

• $ git clone https://github.com/johsteffens/tbman.git

<a name="anchor_build_requirements"></a>

In your workspace

• Compile tbman.c and btree.c (either among your source files or into a static library)
• In your code:
  • #include "tbman.h"
  • Call once tbman_open(); at the beginning or your program. (E.g. first in main())
  • Use tbman_* - functions anywhere.
  • Call once tbman_close(); at the end or your program. (E.g. last in main())

C++

In object oriented C++ programming, the direct use of malloc, realloc or free is discouraged in favor of using operators new and delete, which take care of object construction/destruction. However, you can overload these operators. This gives you control over the part concerned with memory allocation.

Example:

If you add the code below to your program, operators new and delete will work as intended but use tbman for allocating and freeing memory.

void* operator new( size_t size )
{
    return tbman_malloc( size ); 
}

void operator delete( void* p )
{
    tbman_free( p ); 
}

<a name="anchor_quick_evaluation"></a>

Quick Evaluation

eval.c is an evaluation program simulating realistic runtime conditions for a memory manager. It verifies correct functionality and assesses the processing speed. It compares the performance of stdlib functions with tbman functions. You can quickly run it yourself.

Enter the folder with source files:

$ gcc -std=c11 -O3 btree.c tbman.c eval.c -lm -lpthread
$ ./a.out

Requirements/Dependencies

• Compiler supporting the C11 standard (e.g. gcc, clang).

• Compiler options: -std=c11, -O3 for max speed; (or compatible settings)

• Linker options: -lm -lpthread (or compatible settings)

• POSIX: Out of the box, tbman relies on two features, which are normally available on POSIX compliant systems

  • Flat Memory Model.
  • Library pthread: Tbman uses pthread_mutex_t (locking) for thread safety in tbman.c.
  • The following platforms have sufficient POSIX compliance: Linux, Android, Darwin (and related OS)

• If pthread is not available, try one of the folowing options ...:

  • Check if the 🔗Tread Support Library is available for your traget platform. In tbman.c: Use mtx_t instead of pthread_mutex_t; replace functions pthread_mutex_... with corresponding functions mtx_...; use call_once instead of pthread_once.

  • If you have other native locks available: In tbman.c: Replace pthread-locks by native locks.

  • Windows: You can setup a posix subsystem

    • Set up a POSIX-environment via cygwin.
    • Windows 10: Provides an optional Linux-Subsystem.

<a name="anchor_features"></a>

Detailed Description

<a name="anchor_basic"></a>

Basics

Tbman offers the three basic functions of a memory manager:

void* tbman_malloc(             size_t size ); // pure allocation
void* tbman_realloc( void* ptr, size_t size ); // reallocation
void  tbman_free(    void* ptr              ); // freeing

Usage and behavior is compatible to corresponding stdlib functions malloc, free, realloc. <br>_{Exception: Should the entire system run out of available memory, tbman aborts with an error message to stderr.}

Tbman must be initialized once before usage. It should also be properly closed at the end of the program. These two functions take care of it:

void tbman_open( void );  // initializes tbman
void tbman_close( void ); // closes tbman

Example:

int main( int argc, char* argv[] )
{
   tbman_open();

   ... // my program

   tbman_close();
   return my_exit_state;
}

<a name="anchor_faster_collection"></a>

Faster collection

If you free or reallocate memory and know the previously allocated amount, you can further speed up processing by telling tbman about the currently allocated size using tbman_nrealloc and tbman_nfree. This helps the manager finding the corresponding node for the memory instance faster.

// realloc with size communication
void* tbman_nrealloc( void* current_ptr, size_t current_size, size_t new_size ); 

// free with size communication
void  tbman_nfree( void* current_ptr, size_t current_size );

current_size must hold either the requested amount or the granted amount for the memory instance addressed by current_ptr.

<a name="anchor_one_function_for_everything"></a>

One function for everything

Alternatively, you can use just one of the following two functions for all memory management including some special features of tbman.

void* tbman_alloc(  void* current_ptr,                      size_t requested_size, size_t* granted_size );
void* tbman_nalloc( void* current_ptr, size_t current_size, size_t requested_size, size_t* granted_size );

tbman_nalloc works slightly faster than tbman_alloc but requires extra size input. The two functions can also be mixed; even serving the same memory instance.

Arguments

| Name | Description | | :---- | :--------------------------- | | current_ptr | Pointer to current memory instance for freeing or reallocating. <br> Set to NULL for pure allocation. | | current_size | Previously requested or granted size for freeing or reallocating a memory instance. <br> Set to 0 for pure allocation. | | requested_size | Requested new size pure allocation or reallocation.<br> Set to 0 for freeing.| | granted_size | Optional pointer to variable where the function stores the granted amount.<br> Set to NULL when not needed. |

Return value

Pointer to new memory instance for pure allocation or reallocation. Returns NULL in case of freeing.

<a name="anchor_advanced_alignment"></a>

Advanced Alignment

Tbman aligns the memory instance selectively. This covers all standard C/C++ data types char, short, int, float, double, etc and also larger types such as int32x4_t, float32x4_t, etc, which are typically used for SIMD-extensions such as SSE, AVX, NEON, etc.

Example:

int32x4_t* my_data = tbman_malloc( sizeof( int32x4_t ) * 10 ); // aligned array of 10 x int32x4_t

<a name="anchor_granted_memory"></a>

Granted Memory

For design reasons, tbman might find no proper use for some space immediately following your requested memory block. In that case, it grants you that extra space, appending it to your request. You may use the granted space as if you had requested it in the first place. <br>_{(Note: Tbman never grants less than requested.)}

This feature is a special resource for optimizing speed and memory efficiency of objects that vary allocation size during lifetime. It is extensively used in beth on dynamic arrays.

Function tbman_alloc lets you allocate with the granted amount communicated. You can retrieve the granted amount for a given instance using function tbman_granted_space:

// Allocation with granted amount communicated.
void* tbman_alloc( void* current_ptr, size_t requested_size, size_t* granted_size );

// Explicit query for the granted amount from an already existing memory instance
size_t tbman_granted_space( const void* ptr );

Example:

size_t requested_space = 5;
size_t granted_space;
char* my_string = tbman_alloc( NULL, requested_space, &granted_space );
// At this point granted_space >= requested_space. Using that extra space is allowed.

// To visualize, we fill the requested and extra space with different characters:
for( size_t i = 0; i < requested_space - 1; i++ ) my_string[ i ] = '=';
for( size_t i = requested_space - 1; i < granted_space - 1; i++ ) my_string[ i ] = '#';
my_string[ granted_space - 1 ] = 0;

// Possible output:
// ====###
printf( "%s\n", my_string );
`