default.c

Go to the documentation of this file.

/* -*- C -*-
 * Serene programming language
 * Copyright (C) 2019-2026 Sameer Rahmani <[email protected]>
 *
 * 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 <stdlib.h>
 
#include "serene/rt/mm/interface.h"
#include "serene/utils.h"
 
#include <assert.h>
#include <inttypes.h>
#include <string.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
 
// -----------------------------------------------------------------------------
// 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) {
  if (block_id < mm->block_count) {
    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) { free(ptr); }
 
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_allocate(srn_mm_t *mm, size_t size) {
  UNUSED(mm);
  return malloc(size);
}
 
void *srn_mm_reallocate(srn_mm_t *mm, void *ptr, size_t new_size) {
  UNUSED(mm);
  return realloc(ptr, new_size);
}
 
void srn_mm_free(srn_mm_t *mm, void *ptr) {
  UNUSED(mm);
  free(ptr);
}
 
static inline size_t closest_multiple(size_t x, size_t m) {
  size_t half = m / 2;
  return (x + half) / m * m;
}
 
/// 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);
}
 
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;
  srn_spinlock_init(&block->lock);
  srn_spinlock_unlock(&block->lock);
}
 
/// 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);
  return block;
}
 
static inline void destroy_chain(srn_mm_t *mm, srn_block_id_t root_id) {
 
  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);
}
 
/// This is the main allocation logic that allocates the space in the given
/// block. Other public functions have to use this fuction to operate.
static inline void *alloc_in_block(srn_mm_t *mm, srn_block_t *root_block, size_t size,
                                   size_t alignment) {
 
  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;
  }
}
 
// -----------------------------------------------------------------------------
// 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
}
 
size_t srn_mm_get_block_size(void) {
  const size_t ps = srn_mm_get_os_page_size();
  return closest_multiple(DESIRED_BLOCK_SIZE, ps);
}
 
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() {
  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;
}
 
void srn_mm_shutdown(srn_mm_t *mm) {
  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);
}
 
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 %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);
}
 
void *srn_mm_immortal_allocate_aligned(srn_mm_t *mm, size_t size, size_t alignment) {
  return alloc_in_block(mm, mm->immortal_block, size, alignment);
}
 
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) {
  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;
}
 
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@%lx" PRIXPTR "\n", id, (uintptr_t)block);
  printf("======================================================\n");
  printf("Next:\t");
  if (block->next == nullptr) {
    printf("X\n");
  } else {
    printf("%lx" PRIXPTR "\n", (uintptr_t)block->next);
  }
}
 
void srn_mm_print_blocks_summary(srn_mm_t *mm) {
  for (size_t d = 0; d <= mm->block_count; d++) {
    srn_mm_print_block_summary(mm, d);
  }
}
#endif