default.c File Reference

#include <stdlib.h>
#include "serene/rt/mm/interface.h"
#include "serene/utils.h"
#include <assert.h>
#include <inttypes.h>
#include <string.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_allocate (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_allocate or srn_mm_reallocate.
static size_t	closest_multiple (size_t x, size_t m)
static size_t	block_capacity (const srn_block_t *block)
	Return the size of the payload section of 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.
size_t	srn_mm_get_block_size (void)
	Calculates and return the block size based on our desired size and 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 ()
	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 39 of file default.c.

Function Documentation

alloc_block_internal()

static 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 178 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()

static 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.

Definition at line 207 of file default.c.

                                                     {
 
  if (size > 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 %ld with %ld 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 (;;) {
    srn_spinlock_t *lock = &target_block->lock;
    srn_spinlock_lock(lock);
 
    MM_LOG("Next block: %p", (void *)target_block);
    MM_LOG("Base: %p | Offset: 0x%lx | Space: %ld | Total size: %ld", (void *)&target_block->base,
           target_block->offset, block_remaining(target_block), target_block->size);
 
    size_t base_offset = target_block->offset;
    size_t aligned_offset = (base_offset + (alignment - 1)) & ~(alignment - 1);
    size_t capacity = block_capacity(target_block);
 
    MM_LOG("Calculated aligned offset 0x%lx", aligned_offset);
 
    if (aligned_offset + size > capacity) {
      MM_LOG("We can't allocate in this block");
      if (target_block->next != nullptr) {
        srn_spinlock_unlock(lock);
        // 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);
      init_block(mm, b);
      target_block->next = b;
      target_block = b;
      srn_spinlock_unlock(lock);
      MM_LOG("New block: %p", (void *)target_block);
      continue;
    }
    MM_LOG("We have found enough space");
 
    void *ptr = target_block->base + aligned_offset;
    target_block->offset = aligned_offset + size;
    MM_LOG("Allocated 0x%lx bytes from %p to 0x%lx", target_block->offset, ptr,
           (uintptr_t)ptr + (uintptr_t)target_block->offset);
 
    srn_spinlock_unlock(lock);
    return ptr;
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

allocated_block_id()

static 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()

static size_t block_capacity ( const srn_block_t * block )

inlinestatic

Return the size of the payload section of the block.

Definition at line 162 of file default.c.

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

Here is the caller graph for this function:

closest_multiple()

static size_t closest_multiple ( size_t x, size_t m )

inlinestatic

Definition at line 156 of file default.c.

                                                          {
  size_t half = m / 2;
  return (x + half) / m * m;
}

Here is the caller graph for this function:

deallocated_block_id()

static 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()

static void destroy_chain ( srn_mm_t * mm, srn_block_id_t root_id )

inlinestatic

Definition at line 187 of file default.c.

                                                                       {
 
  if (is_block_id_free(mm, root_id)) {
    return;
  }
  srn_block_t *block = get_block(mm, root_id);
 
  srn_lock_memory_manager(mm);
  while (block != nullptr) {
    srn_block_t *tmp = block;
    block = tmp->next;
 
    mm->provider->release(tmp);
  }
  deallocated_block_id(mm, root_id);
  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()

static 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()

static 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 107 of file default.c.

                                                                                  {
  if (block_id < mm->block_count) {
    return mm->blocks[block_id];
  }
  return nullptr;
}

Here is the caller graph for this function:

init_block()

static void init_block ( srn_mm_t * mm, srn_block_t * block )

inlinestatic

Definition at line 166 of file default.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

is_block_id_free()

static 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 362 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()

void * srn_mm_allocate ( 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 141 of file default.c.

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

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 364 of file default.c.

                                                   {
  PANIC_IF(mm->block_count >= MAX_NUMBER_OF_BLOCKS - 1, "Out of memory");
 
  srn_lock_memory_manager(mm);
  srn_block_t *block = alloc_block_internal(mm);
  int index = find_a_free_block_id(mm);
  PANIC_IF(index == -1, "Couldn't allocate a block id. This is a bug!");
 
  init_block(mm, block);
  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 347 of file default.c.

                                                         {
  MM_LOG("Allocating %ld bytes with 16 bytes alignment in block: %zu", size, block_id);
  srn_block_t *block = get_block(mm, block_id);
  PANIC_IF_NULL(block);
 
  return alloc_in_block(mm, block, size, alignment);
}

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_allocate or srn_mm_reallocate.

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

Definition at line 151 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 290 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_block_size()

size_t srn_mm_get_block_size

(

void

)

Calculates and return the block size based on our desired size and the OS page size.

Basically the ruturn value will be a number multiple of the OS page size and close or equal to our desired size

Definition at line 285 of file default.c.

                                   {
  const size_t ps = srn_mm_get_os_page_size();
  return closest_multiple(DESIRED_BLOCK_SIZE, ps);
}

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 270 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 356 of file default.c.

                                                                                    {
  return alloc_in_block(mm, mm->immortal_block, size, alignment);
}

Here is the call graph for this function:

srn_mm_init()

srn_mm_t * srn_mm_init

(

void

)

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

Definition at line 294 of file default.c.

                        {
  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));
 
  mm->block_count = 0;
  mm->block_size = srn_mm_get_block_size();
  memset((void *)mm->blocks, 0, sizeof(mm->blocks));
 
  PANIC_IF(mm->block_size <= sizeof(srn_block_t),
           "Wrong block size. Modify DESIRED_BLOCK_SIZE to a larger number");
 
  srn_spinlock_init(&mm->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_reallocate()

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

nodiscard

Definition at line 146 of file default.c.

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

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 388 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 325 of file default.c.

                                   {
  PANIC_IF_NULL(mm);
  assert(mm->provider != nullptr);
 
  for (size_t i = 0; i < mm->block_count; 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 360 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()

static 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 117 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()

static void stdlib_releaser ( void * ptr )

static

Definition at line 128 of file default.c.

{ free(ptr); }

Variable Documentation

stdlib_provider

srn_memory_provider_t stdlib_provider

static

Initial value:

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

Definition at line 130 of file default.c.

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