Geek Answers Handbook

How to write a thread safe and efficient blocking block memory allocation in C?

How to write thread safe and efficient blocking block memory allocation in C? By effective I mean:

  • Quick distribution and release

  • Optimal memory usage (minimal loss and lack of external fragmentation)

  • Minimum Metadata Overhead

+6
performance c multithreading memory allocation
source share
3 answers

http://www.research.ibm.com/people/m/michael/pldi-2004.pdf

This document presents a fully blocking memory allocator. It uses only widely available operating systems and hardware atomic instructions. It offers guaranteed availability even under an arbitrary thread of interruption and failure, and it is not protected from deadlock regardless of scheduling policies, and therefore it can be used even in interrupt handlers and real-time applications without the need for special scheduler support. In addition, through the use of some high-level structures from Hoard, our distributor is highly scalable, limits spatial inflation to a constant factor, and is able to avoid false exchanges ...

+11
source share

Depends on what you mean by efficiency. If I was worried about doing something quickly, I would probably provide each thread with its own separate memory pool for work and a custom "malloc" that took memory from this pool. Of course, if speed bothered me, I would probably avoid distribution in the first place.

No answer; You will balance a number of problems. It will be almost impossible to obtain without locking the distributor, but you can lock earlier and infrequently (by allocating large pools for each thread), or you can make the locks so small and tight that they must be correct.

+3
source share

You can use a block list and a pair of buckets of various sizes.

So:

typedef struct { union{ SLIST_ENTRY entry; void* list; }; byte mem[]; } mem_block; typedef struct { SLIST_HEADER root; } mem_block_list; #define BUCKET_COUNT 4 #define BLOCKS_TO_ALLOCATE 16 static mem_block_list Buckets[BUCKET_COUNT]; void init_buckets() { for( int i = 0; i < BUCKET_COUNT; ++i ) { InitializeSListHead( &Buckets[i].root ); for( int j = 0; j < BLOCKS_TO_ALLOCATE; ++j ) { mem_block* p = (mem_block*) malloc( sizeof( mem_block ) + (0x1 << BUCKET_COUNT) * 0x8 ); InterlockedPushEntrySList( &Buckets[i].root, &p->entry ); } } } void* balloc( size_t size ) { for( int i = 0; i < BUCKET_COUNT; ++i ) { if( size <= (0x1 << i) * 0x8 ) { mem_block* p = (mem_block*) InterlockedPopEntrySList( &Buckets[i].root ); p->list = &Buckets[i]; } } return 0; // block to large } void bfree( void* p ) { mem_block* block = (mem_block*) (((byte*)p) - sizeof( block->entry )); InterlockedPushEntrySList( ((mem_block_list*)block)->root, &block->entry ); }

SLIST_ENTRY, InterlockedPushEntrySList, InterlockedPopEntrySList, InitializeSListHead - these are functions for operations with unprotected singly linked lists under Win32. Use the appropriate operations for other operating systems.

Disadvantages:

  • sizeof( SLIST_ENTRY ) overhead sizeof( SLIST_ENTRY )
  • Buckets can only grow once at the beginning, after which you can run out of memory and ask for OS / other buckets. (Other buckets lead to fragmentation)
  • This example is too simple and needs to be expanded to handle more cases.
+2
source share

More articles:


All Articles