default.c File Reference

#include <assert.h>
#include <inttypes.h>
#include <stdlib.h>
#include <string.h>
#include "serene/rt/mm/interface.h"
#include "serene/utils.h"

Include dependency graph for default.c:

Go to the source code of this file.

Macros
#define	MM_LOG(FMT, ...)

Functions
static bool	is_block_id_free (const srn_mm_t *mm, uint16_t bit)
static void	allocated_block_id (srn_mm_t *mm, uint16_t bit)
static void	deallocated_block_id (srn_mm_t *mm, uint16_t bit)
static int	find_a_free_block_id (const srn_mm_t *mm)
static srn_block_t *	get_block (const srn_mm_t *mm, srn_block_id_t block_id)
	An abstraction over ID->Block operation.
static void *	stdlib_allocator (size_t size, size_t alignment)
	Just a proxy functions to the standard stdlib malloc/free later on if we decided to use mimalloc or something or even our own malloc, we can plug them in like this.
static void	stdlib_releaser (void *ptr)
void *	srn_mm_malloc (srn_mm_t *mm, size_t size)
	Generic allocations that do not participate in the block based pools.
void *	srn_mm_reallocate (srn_mm_t *mm, void *ptr, size_t new_size)
void	srn_mm_free (srn_mm_t *mm, void *ptr)
	Release a pointer previously returned by srn_mm_malloc or srn_mm_reallocate.
static size_t	block_capacity (const srn_block_t *block)
	Return the size of the payload section of the block.
static size_t	block_remaining (const srn_block_t *block)
	Return the number of unused payload bytes left in the block.
static void	init_block (srn_mm_t *mm, srn_block_t *block)
static void *	alloc_block_internal (srn_mm_t *mm)
	Allocate a block worth of memory using the memory provider.
static void	destroy_chain (srn_mm_t *mm, srn_block_id_t root_id)
static void *	alloc_in_block (srn_mm_t *mm, srn_block_t *root_block, size_t size, size_t alignment)
	This is the main allocation logic that allocates the space in the given block.
size_t	srn_mm_get_os_page_size (void)
	Retutrns the OS page size.
srn_block_t *	srn_mm_get_block (srn_mm_t *mm, srn_block_id_t block_id)
	Return the block object associated by the given block_id.
srn_mm_t *	srn_mm_init (const srn_configuration_t *config)
	Initialize the memory manager, this function will panic on error.
void	srn_mm_shutdown (srn_mm_t *mm)
	Shut down the memory manager and release the resources.
void *	srn_mm_allocate_in_block_aligned (srn_mm_t *mm, srn_block_id_t block_id, size_t size, size_t alignment)
	Allocate memory on a block with the given block_id.
void *	srn_mm_immortal_allocate_aligned (srn_mm_t *mm, size_t size, size_t alignment)
	Allocate memory on the importal block which will never gets freed.
void	srn_unlock_memory_manager (srn_mm_t *mm)
	Unocks the memory manager.
void	srn_lock_memory_manager (srn_mm_t *mm)
	Locks the memory manager.
srn_block_id_t	srn_mm_allocate_block (srn_mm_t *mm)
	Allocate a new block in the memory manager and return its ID.
void	srn_mm_release_block (srn_mm_t *mm, srn_block_id_t id)
	Release the given block id and free the memory for later allocations.

Variables
static srn_memory_provider_t	stdlib_provider

Macro Definition Documentation

MM_LOG

#define MM_LOG	(		FMT,
			... )

Definition at line 38 of file default.c.

Function Documentation

alloc_block_internal()

void * alloc_block_internal ( srn_mm_t * mm )

inlinestatic

Allocate a block worth of memory using the memory provider.

This is an internal function and it will NOT allocate block_id nor track the block via the memory manager by default.

Definition at line 197 of file default.c.

                                                       {
  PANIC_IF_NULL(mm);
  srn_block_t *block =
    (srn_block_t *)mm->provider->allocate(mm->block_size, DEFAULT_BLOCK_ALIGNMENT);
  PANIC_IF_NULL(block);
  init_block(mm, block);
  return block;
}

Here is the call graph for this function:

Here is the caller graph for this function:

alloc_in_block()

void * alloc_in_block ( srn_mm_t * mm, srn_block_t * root_block, size_t size, size_t alignment )

inlinestatic

This is the main allocation logic that allocates the space in the given block.

Other public functions have to use this fuction to operate. The caller must hold the chain's lock for the whole call.

Definition at line 243 of file default.c.

                                                                                     {
  PANIC_IF(
    alignment == 0 || (alignment & (alignment - 1)) != 0,
    "'alignment' must be a nonzero power of two"
  );
 
  if (size > block_capacity(root_block) || alignment > block_capacity(root_block)) {
    // Since all the blocks in a block chain have the same size,
    // if user is asking for an allocation larger than the block size,
    // there is no way we can find it in this chain, so a larger block
    // size is required
    TODO("We need to allocate a larger block");
  }
  MM_LOG("Allocating %zu with %zu alignment", size, alignment);
 
  MM_LOG("Root block: %p", (void *)root_block);
  srn_block_t *target_block = root_block;
  MM_LOG("Walking the block chain");
  for (;;) {
    MM_LOG("Next block: %p", (void *)target_block);
 
    // Align the absolute address, not the offset. The payload base is only
    // guaranteed DEFAULT_BLOCK_ALIGNMENT, so offset arithmetic alone returns
    // misaligned pointers for larger alignments.
    uintptr_t base = (uintptr_t)target_block->base;
    uintptr_t aligned =
      (base + target_block->offset + (alignment - 1)) & ~((uintptr_t)alignment - 1);
    size_t aligned_offset = (size_t)(aligned - base);
    size_t capacity       = block_capacity(target_block);
 
    MM_LOG("Calculated aligned offset 0x%zx", aligned_offset);
 
    if (aligned_offset + size > capacity) {
      MM_LOG("We can't allocate in this block");
      if (target_block->next != nullptr) {
        // let's try the next block in the chain
        target_block = target_block->next;
        continue;
      }
      // We need to create a new block for this chain.
      MM_LOG("We have to allocate a new block");
 
      srn_block_t *b     = alloc_block_internal(mm);
      target_block->next = b;
      target_block       = b;
      MM_LOG("New block: %p", (void *)target_block);
      continue;
    }
    MM_LOG("We have found enough space");
 
    void *ptr            = (void *)aligned;
    target_block->offset = aligned_offset + size;
 
    return ptr;
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

allocated_block_id()

void allocated_block_id ( srn_mm_t * mm, uint16_t bit )

inlinestatic

Definition at line 56 of file default.c.

                                                                  {
  PANIC_IF(bit >= 256, "Bit position is out of block_bitmap boundaries.");
 
  // divide by 64, which 64-bit word
  uint64_t index = bit >> 6U;
  // remainder, which bit in that word
  unsigned offset = bit & 63U;
 
  mm->block_bitmap[index] |= (1ULL << offset);
}

Here is the caller graph for this function:

block_capacity()

size_t block_capacity ( const srn_block_t * block )

inlinestatic

Return the size of the payload section of the block.

Definition at line 173 of file default.c.

                                                              {
  return block->size - offsetof(srn_block_t, base);
}

Here is the caller graph for this function:

block_remaining()

size_t block_remaining ( const srn_block_t * block )

inlinestatic

Return the number of unused payload bytes left in the block.

Definition at line 181 of file default.c.

                                                               {
  return block_capacity(block) - block->offset;
}

Here is the call graph for this function:

deallocated_block_id()

void deallocated_block_id ( srn_mm_t * mm, uint16_t bit )

inlinestatic

Definition at line 67 of file default.c.

                                                                    {
  PANIC_IF(bit >= 256, "Bit position is out of block_bitmap boundaries.");
 
  uint64_t index  = bit >> 6U;
  unsigned offset = bit & 63U;
  uint64_t mask   = ~(1ULL << offset);
  mm->block_bitmap[index] &= mask;
}

Here is the caller graph for this function:

destroy_chain()

void destroy_chain ( srn_mm_t * mm, srn_block_id_t root_id )

inlinestatic

Definition at line 206 of file default.c.

                                                                       {
  srn_lock_memory_manager(mm);
 
  // The liveness check happens under the manager lock, so two racing
  // releases of the same id cannot both pass it and double free the chain.
  if (is_block_id_free(mm, root_id)) {
    srn_unlock_memory_manager(mm);
    return;
  }
 
  // Holding the chain lock closes the race against an allocation walking
  // this chain, the walk either finishes before the free, or starts after
  // the slot is nulled and panics on the dead id.
  srn_spinlock_t *chain_lock = &mm->chain_locks[root_id];
  srn_spinlock_lock(chain_lock);
 
  srn_block_t *block = get_block(mm, root_id);
  while (block != nullptr) {
    srn_block_t *tmp = block;
    block            = tmp->next;
 
    mm->provider->release(tmp);
  }
 
  mm->blocks[root_id] = nullptr;
  mm->block_count--;
  deallocated_block_id(mm, root_id);
  srn_spinlock_unlock(chain_lock);
  srn_unlock_memory_manager(mm);
}

Here is the call graph for this function:

Here is the caller graph for this function:

find_a_free_block_id()

int find_a_free_block_id ( const srn_mm_t * mm )

inlinestatic

Definition at line 76 of file default.c.

                                                           {
#if defined(__GNUC__) || defined(__clang__)
  for (int i = 0; i < 4; i++) {
    uint64_t word = mm->block_bitmap[i];
 
    if (~word) {
      // invert, then find first 1 bit
      int bit = __builtin_ctzll(~word);
      return (i * 64) + bit;
    }
  }
  return -1;
#else
  // Fallback
  for (int i = 0; i < 4; i++) {
    uint64_t word = mm->block_bitmap[i];
    if (word != ~0ULL) {
      uint64_t mask = ~word;
      int bit       = 0;
      while ((mask & 1ULL) == 0) {
        mask >>= 1;
        bit++;
      }
      return (i * 64) + bit;
    }
  }
  return -1;
#endif
}

Here is the caller graph for this function:

get_block()

srn_block_t * get_block ( const srn_mm_t * mm, srn_block_id_t block_id )

inlinestatic

An abstraction over ID->Block operation.

Definition at line 109 of file default.c.

                                                                                  {
  // Ids are reused, so the array slot decides liveness, a released or never
  // allocated id holds a nullptr.
  if (block_id < MAX_NUMBER_OF_BLOCKS) {
    return mm->blocks[block_id];
  }
  return nullptr;
}

Here is the caller graph for this function:

init_block()

void init_block ( srn_mm_t * mm, srn_block_t * block )

inlinestatic

Definition at line 185 of file default.c.

                                                                {
  PANIC_IF_NULL(mm);
  block->next   = nullptr;
  block->size   = mm->block_size;
  block->offset = 0;
}

Here is the caller graph for this function:

is_block_id_free()

bool is_block_id_free ( const srn_mm_t * mm, uint16_t bit )

inlinestatic

Definition at line 45 of file default.c.

                                                                      {
  PANIC_IF(bit >= 256, "Bit position is out of block_bitmap boundaries.");
 
  // divide by 64, which 64-bit word
  uint64_t index = bit >> 6U;
  // remainder, which bit in that word
  unsigned offset = bit & 63U;
 
  return ((mm->block_bitmap[index] >> offset) & 1ULL) == 0;
}

Here is the caller graph for this function:

srn_lock_memory_manager()

void srn_lock_memory_manager

(

srn_mm_t *

mm

)

Locks the memory manager.

We have to lock the memory manager when allocating blocks. TODO(lxsameer): Do we need to support thread local blocks?

Definition at line 424 of file default.c.

{ srn_spinlock_lock(&mm->lock); }

Here is the call graph for this function:

Here is the caller graph for this function:

srn_mm_allocate_block()

srn_block_id_t srn_mm_allocate_block ( srn_mm_t * mm )

nodiscard

Allocate a new block in the memory manager and return its ID.

The client code can use the ID to allocate memory on the block and when it's done, just use the same ID to release the block

Definition at line 426 of file default.c.

                                                   {
  srn_lock_memory_manager(mm);
  // Ids are reused after release, so exhaustion means every id is live
  // right now, not that this many allocations ever happened.
  int index = find_a_free_block_id(mm);
  PANIC_IF(index == -1, "Out of memory: all block ids are in use");
  srn_block_t *block = alloc_block_internal(mm);
 
  mm->block_count++;
  PANIC_IF(
    !is_block_id_free(mm, (uint16_t)index),
    "Miscalculated the block id. It is not free. This is a bug!"
  );
  allocated_block_id(mm, (uint16_t)index);
  mm->blocks[(srn_block_id_t)index] = block;
 
  srn_unlock_memory_manager(mm);
 
#if SERENE_DEBUG
  mm->stats.total_blocks++;
  mm->stats.total_os_allocations++;
#endif
  return (srn_block_id_t)index;
}

Here is the call graph for this function:

Here is the caller graph for this function:

srn_mm_allocate_in_block_aligned()

void * srn_mm_allocate_in_block_aligned ( srn_mm_t * mm, srn_block_id_t block_id, size_t size, size_t alignment )

nodiscard

Allocate memory on a block with the given block_id.

Definition at line 396 of file default.c.

  {
  MM_LOG("Allocating %zu bytes with %zu bytes alignment in block: %zu", size, alignment, block_id);
  PANIC_IF(block_id >= MAX_NUMBER_OF_BLOCKS, "Block id out of range");
 
  // The id resolves to a block only under the chain lock, so a release
  // cannot free the chain out from under this walk.
  srn_spinlock_t *chain_lock = &mm->chain_locks[block_id];
  srn_spinlock_lock(chain_lock);
 
  srn_block_t *block = get_block(mm, block_id);
  PANIC_IF_NULL(block);
 
  void *ptr = alloc_in_block(mm, block, size, alignment);
  srn_spinlock_unlock(chain_lock);
  return ptr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

srn_mm_free()

void srn_mm_free	(	srn_mm_t *	mm,
		void *	ptr )

Release a pointer previously returned by srn_mm_malloc or srn_mm_reallocate.

ptr may be nullptr, in which case the call is a no-op.

Definition at line 165 of file default.c.

                                          {
  UNUSED(mm);
  free(ptr);
}

Here is the caller graph for this function:

srn_mm_get_block()

srn_block_t * srn_mm_get_block	(	srn_mm_t *	mm,
		srn_block_id_t	block_id )

Return the block object associated by the given block_id.

Definition at line 318 of file default.c.

                                                                     {
  return get_block(mm, block_id);
}

Here is the call graph for this function:

Here is the caller graph for this function:

srn_mm_get_os_page_size()

size_t srn_mm_get_os_page_size

(

void

)

Retutrns the OS page size.

Definition at line 303 of file default.c.

                                     {
#if defined(_WIN32)
  SYSTEM_INFO si;
  GetSystemInfo(&si);
  return (size_t)si.dwPageSize;
#elif defined(__unix__) || defined(__APPLE__)
  long sz = sysconf(_SC_PAGESIZE);
  return (sz > 0) ? (size_t)sz : FALLBACK_PAGE_SIZE;
#elif defined(__wasm__)
  return WASM_PAGE_SIZE;
#else
  return FALLBACK_PAGE_SIZE;
#endif
}

Here is the caller graph for this function:

srn_mm_immortal_allocate_aligned()

void * srn_mm_immortal_allocate_aligned ( srn_mm_t * mm, size_t size, size_t alignment )

nodiscard

Allocate memory on the importal block which will never gets freed.

Definition at line 415 of file default.c.

                                                                                    {
  srn_spinlock_lock(&mm->immortal_lock);
  void *ptr = alloc_in_block(mm, mm->immortal_block, size, alignment);
  srn_spinlock_unlock(&mm->immortal_lock);
  return ptr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

srn_mm_init()

srn_mm_t * srn_mm_init

(

const srn_configuration_t *

config

)

Initialize the memory manager, this function will panic on error.

config provides the knobs the manager reads at init (mm.block_size_magnitude, the block size is 1 << magnitude); a null config means "use the defaults". The config is read only during the call, so the caller may pass a stack value and reuse it for srn_engine_make.

Definition at line 322 of file default.c.

                                                         {
  if (config != nullptr) {
    srn_config_validate(config);
  }
 
  srn_mm_t *mm = malloc(sizeof(srn_mm_t));
  PANIC_IF_NULL(mm);
 
  mm->provider = &stdlib_provider;
  memset(mm->block_bitmap, 0, sizeof(mm->block_bitmap));
 
  // The block size is the one knob the manager reads at init. It comes as a
  // magnitude, so the size is a power of two and a whole number of pages by
  // construction, with nothing to round.
  const size_t magnitude =
    (config != nullptr) ? config->mm.block_size_magnitude : SRN_CONFIG_DEFAULT_BLOCK_SIZE_MAGNITUDE;
 
  mm->block_count = 0;
  mm->block_size  = (size_t)1 << magnitude;
  memset((void *)mm->blocks, 0, sizeof(mm->blocks));
 
  PANIC_IF(
    mm->block_size <= sizeof(srn_block_t),
    "Wrong block size. Configure mm.block_size_magnitude to a larger number"
  );
  // srn_config_validate only sees a caller provided config, so the default
  // path is checked here too. The page size is only known at run time.
  PANIC_IF(
    mm->block_size % srn_mm_get_os_page_size() != 0, "Block size must be a whole number of OS pages"
  );
 
  srn_spinlock_init(&mm->lock);
  for (size_t i = 0; i < MAX_NUMBER_OF_BLOCKS; i++) {
    srn_spinlock_init(&mm->chain_locks[i]);
  }
  srn_spinlock_init(&mm->immortal_lock);
 
  srn_block_t *immortal =
    (srn_block_t *)mm->provider->allocate(mm->block_size, DEFAULT_BLOCK_ALIGNMENT);
  PANIC_IF_NULL(immortal);
  init_block(mm, immortal);
  mm->immortal_block = immortal;
 
#if SERENE_DEBUG
  mm->stats.allocated_pages      = 0;
  mm->stats.total_allocations    = 0;
  mm->stats.total_os_allocations = 0;
  mm->stats.total_blocks         = 0;
#endif
  return mm;
}

Here is the call graph for this function:

Here is the caller graph for this function:

srn_mm_malloc()

void * srn_mm_malloc ( srn_mm_t * mm, size_t size )

nodiscard

Generic allocations that do not participate in the block based pools.

Equivalent to malloc/realloc/free. Routed through the memory manager so the backend can later be swapped without touching callers. mm is reserved for future per manager routing and is currently unused inside the implementation.

Definition at line 155 of file default.c.

                                               {
  UNUSED(mm);
  return malloc(size);
}

Here is the caller graph for this function:

srn_mm_reallocate()

void * srn_mm_reallocate ( srn_mm_t * mm, void * ptr, size_t new_size )

nodiscard

Definition at line 160 of file default.c.

                                                                  {
  UNUSED(mm);
  return realloc(ptr, new_size);
}

Here is the caller graph for this function:

srn_mm_release_block()

void srn_mm_release_block	(	srn_mm_t *	mm,
		srn_block_id_t	id )

Release the given block id and free the memory for later allocations.

Definition at line 451 of file default.c.

                                                           {
  PANIC_IF_NULL(mm);
  destroy_chain(mm, id);
}

Here is the call graph for this function:

Here is the caller graph for this function:

srn_mm_shutdown()

void srn_mm_shutdown

(

srn_mm_t *

mm

)

Shut down the memory manager and release the resources.

Will panic on error. Technically it should be the final piece of clean up that we call. Note: Shutdown is not thread safe at has to execute on the main thread.

Definition at line 374 of file default.c.

                                   {
  PANIC_IF_NULL(mm);
  assert(mm->provider != nullptr);
 
  for (size_t i = 0; i < MAX_NUMBER_OF_BLOCKS; i++) {
    if (mm->blocks[i] != nullptr) {
      destroy_chain(mm, i);
    }
  }
 
  srn_block_t *block = mm->immortal_block;
 
  while (block != nullptr) {
    srn_block_t *tmp = block;
    block            = tmp->next;
 
    mm->provider->release(tmp);
  }
 
  mm->provider->release(mm);
}

Here is the call graph for this function:

Here is the caller graph for this function:

srn_unlock_memory_manager()

void srn_unlock_memory_manager

(

srn_mm_t *

mm

)

Unocks the memory manager.

Definition at line 422 of file default.c.

{ srn_spinlock_unlock(&mm->lock); }

Here is the call graph for this function:

Here is the caller graph for this function:

stdlib_allocator()

void * stdlib_allocator ( size_t size, size_t alignment )

static

Just a proxy functions to the standard stdlib malloc/free later on if we decided to use mimalloc or something or even our own malloc, we can plug them in like this.

Definition at line 123 of file default.c.

                                                             {
  PANIC_IF(size % alignment != 0, "'size' should be a multiple of alignment");
 
#if defined(_WIN32)
  return _aligned_malloc(size, alignment);
#else
  // C11 standard. It stills bothers me why microsoft is not doing it.
  return aligned_alloc(alignment, size);
#endif
}

stdlib_releaser()

void stdlib_releaser ( void * ptr )

static

Definition at line 134 of file default.c.

                                       {
#if defined(_WIN32)
  // _aligned_malloc memory must go back through _aligned_free; plain free
  // corrupts the CRT heap.
  _aligned_free(ptr);
#else
  free(ptr);
#endif
}

Variable Documentation

stdlib_provider

srn_memory_provider_t stdlib_provider

static

Initial value:

                                             = {
  .allocate = &stdlib_allocator,
  .release  = &stdlib_releaser,
}

Definition at line 144 of file default.c.

                                             {
  .allocate = &stdlib_allocator,
  .release  = &stdlib_releaser,
};