default.c

Go to the documentation of this file.

/* -*- C -*-
 * Serene programming language
 * Copyright (C) 2019-2026 Sameer Rahmani <lxsameer@lxsameer.com>
 *
 * This library is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#include <assert.h>
#include <inttypes.h>
#include <stdlib.h>
#include <string.h>
 
#include "serene/rt/mm/interface.h"
#include "serene/utils.h"
 
#if defined(_WIN32)
#  include <windows.h>
#elif defined(__unix__) || defined(__APPLE__)
#  include <unistd.h>
#elif defined(__wasm__)
#  define WASM_PAGE_SIZE 65536U
#endif
 
#if defined(MM_DEBUG)
#  define MM_LOG(FMT, ...) DBG("MM", FMT __VA_OPT__(, ) __VA_ARGS__)
#else
#  define MM_LOG(FMT, ...)
#endif
 
// NOLINTBEGIN(readability-magic-numbers)
// -----------------------------------------------------------------------------
// Helper functions
// -----------------------------------------------------------------------------
static inline bool is_block_id_free(const srn_mm_t *mm, uint16_t bit) {
  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;
}
 
static inline void allocated_block_id(srn_mm_t *mm, uint16_t bit) {
  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);
}
 
static inline void deallocated_block_id(srn_mm_t *mm, uint16_t bit) {
  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;
}
 
static inline int find_a_free_block_id(const srn_mm_t *mm) {
#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
}
 
/**
 * An abstraction over ID->Block operation
 */
static inline srn_block_t *get_block(const srn_mm_t *mm, srn_block_id_t block_id) {
  // 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;
}
 
/**
 * 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_allocator(size_t size, size_t alignment) {
  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
}
 
static void stdlib_releaser(void *ptr) {
#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
}
 
static srn_memory_provider_t stdlib_provider = {
  .allocate = &stdlib_allocator,
  .release  = &stdlib_releaser,
};
 
// ---------------------------------------------------------------------------
// Generic allocations (currently a thin wrapper over stdlib malloc/realloc
// /free). Block based machinery above is untouched; these are for callers
// that need a plain "give me N bytes, here you go" allocator.
// ---------------------------------------------------------------------------
 
void *srn_mm_malloc(srn_mm_t *mm, size_t size) {
  UNUSED(mm);
  void *ptr = malloc(size);
  MM_TRACEPOINT(mm_malloc, (uint64_t)size, ptr);
  return ptr;
}
 
void *srn_mm_reallocate(srn_mm_t *mm, void *ptr, size_t new_size) {
  UNUSED(mm);
  void *out = realloc(ptr, new_size);
  return out;
}
 
void srn_mm_free(srn_mm_t *mm, void *ptr) {
  UNUSED(mm);
  MM_TRACEPOINT(mm_free, ptr);
  free(ptr);
}
 
/**
 * Return the size of the payload section of the block
 */
static inline size_t block_capacity(const srn_block_t *block) {
  return block->size - offsetof(srn_block_t, base);
}
 
/**
 * Return the number of unused payload bytes left in the block
 */
[[maybe_unused]]
static inline size_t block_remaining(const srn_block_t *block) {
  return block_capacity(block) - block->offset;
}
 
static inline void init_block(srn_mm_t *mm, srn_block_t *block) {
  PANIC_IF_NULL(mm);
  block->next   = nullptr;
  block->size   = mm->block_size;
  block->offset = 0;
}
 
/**
 * 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.
 */
static inline void *alloc_block_internal(srn_mm_t *mm) {
  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);
  MM_TRACEPOINT(mm_block_new, (void *)block, (uint64_t)mm->block_size);
  return block;
}
 
static inline void destroy_chain(srn_mm_t *mm, srn_block_id_t root_id) {
  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);
  size_t freed       = 0;
  while (block != nullptr) {
    srn_block_t *tmp = block;
    block            = tmp->next;
 
    mm->provider->release(tmp);
    freed++;
  }
 
  mm->blocks[root_id] = nullptr;
  mm->block_count--;
  deallocated_block_id(mm, root_id);
  MM_TRACEPOINT(mm_chain_free, (uint64_t)root_id, (uint64_t)freed);
  srn_spinlock_unlock(chain_lock);
  srn_unlock_memory_manager(mm);
}
 
/**
 * 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.
 */
static inline void *
alloc_in_block(srn_mm_t *mm, srn_block_t *root_block, size_t size, size_t alignment) {
  PANIC_IF(
    alignment == 0 || (alignment & (alignment - 1)) != 0,
    "'alignment' must be a nonzero power of two"
  );
 
  // A block base only guarantees DEFAULT_BLOCK_ALIGNMENT, so a request may
  // need up to `alignment - DEFAULT_BLOCK_ALIGNMENT` bytes of padding in any
  // block of the chain, a fresh one included. A request that does not fit
  // together with that padding can never be satisfied by growing the chain,
  // it has to be refused here or the walk below links new blocks forever.
  size_t capacity = block_capacity(root_block);
  size_t padding  = alignment > DEFAULT_BLOCK_ALIGNMENT ? alignment - DEFAULT_BLOCK_ALIGNMENT : 0;
  if (size > capacity || padding > capacity - size) {
    // 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);
 
    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_TRACEPOINT(mm_chain_grow, (void *)root_block, (void *)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;
  }
}
 
// -----------------------------------------------------------------------------
// Public API
// -----------------------------------------------------------------------------
size_t srn_mm_get_os_page_size(void) {
#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
}
 
srn_block_t *srn_mm_get_block(srn_mm_t *mm, srn_block_id_t block_id) {
  return get_block(mm, block_id);
}
 
srn_mm_t *srn_mm_init(const srn_configuration_t *config) {
  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;
}
 
void srn_mm_shutdown(srn_mm_t *mm) {
  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);
}
 
void *srn_mm_allocate_in_block_aligned(
  srn_mm_t *mm, srn_block_id_t block_id, size_t size, size_t alignment
) {
  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);
  MM_TRACEPOINT(mm_alloc, (uint64_t)block_id, (uint64_t)size, ptr);
  return ptr;
}
 
void *srn_mm_immortal_allocate_aligned(srn_mm_t *mm, size_t size, size_t alignment) {
  srn_spinlock_lock(&mm->immortal_lock);
  void *ptr = alloc_in_block(mm, mm->immortal_block, size, alignment);
  srn_spinlock_unlock(&mm->immortal_lock);
  MM_TRACEPOINT(mm_immortal_alloc, (uint64_t)size, ptr);
  return ptr;
}
 
void srn_unlock_memory_manager(srn_mm_t *mm) { srn_spinlock_unlock(&mm->lock); }
 
void srn_lock_memory_manager(srn_mm_t *mm) { srn_spinlock_lock(&mm->lock); }
 
srn_block_id_t srn_mm_allocate_block(srn_mm_t *mm) {
  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;
}
 
void srn_mm_release_block(srn_mm_t *mm, srn_block_id_t id) {
  PANIC_IF_NULL(mm);
  destroy_chain(mm, id);
}
 
#if SERENE_DEBUG
void srn_mm_print_block_summary(srn_mm_t *mm, srn_block_id_t id) {
  srn_block_t *block = get_block(mm, id);
  PANIC_IF_NULL(block);
 
  printf("Block: %zu@%" PRIXPTR "\n", id, (uintptr_t)block);
  printf("======================================================\n");
  printf("Next:\t");
  if (block->next == nullptr) {
    printf("X\n");
  } else {
    printf("%" PRIXPTR "\n", (uintptr_t)block->next);
  }
}
 
void srn_mm_print_blocks_summary(srn_mm_t *mm) {
  for (size_t d = 0; d < MAX_NUMBER_OF_BLOCKS; d++) {
    if (mm->blocks[d] != nullptr) {
      srn_mm_print_block_summary(mm, d);
    }
  }
}
#endif
// NOLINTEND(readability-magic-numbers)