mm_tests.h

Go to the documentation of this file.

/* -*- C -*-
 * Serene programming language
 * Copyright (C) 2019-2026 Sameer Rahmani <lxsameer@lxsameer.com>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */
#pragma once
 
#include <signal.h>
#include <stddef.h>
#include <sys/wait.h>
#include <unistd.h>
 
#include <serene/rt/mm/interface.h>
 
#include "base.h"
#include "serene/utils.h"
 
#define MM_TESTS(X)                                                                                \
  X("mm::allocation", test_mm_allocation), X("mm::block_allocation", test_mm_allocation_in_block), \
    X("mm::multiblock_allocation", test_mm_allocation_multiblock),                                 \
    X("mm::block_bitmap", test_mm_block_bitmap),                                                   \
    X("mm::block_size_properties", test_mm_block_size_properties),                                 \
    X("mm::aligned_block_allocation", test_mm_aligned_block_allocation),                           \
    X("mm::immortal_multiblock", test_mm_immortal_multiblock),                                     \
    X("mm::get_block_out_of_range", test_mm_get_block_out_of_range),                               \
    X("mm::block_release_reuse", test_mm_block_release_reuse),                                     \
    X("mm::get_block_after_release", test_mm_get_block_after_release),                             \
    X("mm::over_aligned_allocation", test_mm_over_aligned_allocation),                             \
    X("mm::over_aligned_request_near_capacity", test_mm_over_aligned_request_near_capacity)
 
#if defined(MM_DEBUG)
#  define MM_TEST_LOG(...) DBG("MM_TEST", __VA_ARGS__)
#else
#  define MM_TEST_LOG(...)
#endif
 
typedef struct mm_dummy {
  char foo[200];
  char bar[200];
} mm_dummy;
 
typedef struct mm_64k {
  char foo[0xffff];
} mm_64k;
 
static inline size_t padding(size_t size, size_t align) {
  return (align - (size & (align - 1U))) & (align - 1);
}
 
static void test_mm_allocation() {
  srn_mm_t *mm = srn_mm_init(nullptr);
  ASSERT_NOT_NULL(mm);
 
  mm_dummy *d = srn_mm_immortal_allocate(mm, mm_dummy);
 
  for (int i = 0; i < 200; i++) {
    d->foo[i] = 'A';
    d->bar[i] = 'B';
  }
 
  // DBG_HEX(mm->immortal_block, 600);
 
  srn_mm_shutdown(mm);
}
 
static void test_mm_allocation_in_block() {
  srn_mm_t *mm = srn_mm_init(nullptr);
  ASSERT_NOT_NULL(mm);
 
  srn_block_id_t b = srn_mm_allocate_block(mm);
  mm_dummy *d      = srn_mm_allocate_in_block(mm, b, mm_dummy);
 
  for (int i = 0; i < 200; i++) {
    d->foo[i] = 'A';
    d->bar[i] = 'B';
  }
 
  srn_block_t *block = srn_mm_get_block(mm, b);
 
  TEST_CHECK(block != nullptr);
  // DBG_HEX(block, 600);
 
  srn_mm_shutdown(mm);
}
 
static void test_mm_allocation_multiblock() {
  srn_mm_t *mm = srn_mm_init(nullptr);
  ASSERT_NOT_NULL(mm);
 
  srn_block_id_t b = srn_mm_allocate_block(mm);
  MM_TEST_LOG("Allocated block 'b' with id %zu", b);
  MM_TEST_LOG("Allocating 'd1'");
  mm_64k *d1 = srn_mm_allocate_in_block(mm, b, mm_64k);
 
  for (int i = 0; i < 0xffff; i++) {
    d1->foo[i] = 'A';
  }
  MM_TEST_LOG("Allocating 'd2'");
  mm_64k *d2 = srn_mm_allocate_in_block(mm, b, mm_64k);
  for (int i = 0; i < 0xffff; i++) {
    d2->foo[i] = 'B';
  }
 
  MM_TEST_LOG("Allocating 'd3'");
  // this should end up on the root block
  mm_dummy *d3 = srn_mm_allocate_in_block(mm, b, mm_dummy);
  for (int i = 0; i < 200; i++) {
    d3->foo[i] = 'C';
    d3->bar[i] = 'D';
  }
 
  srn_block_t *block = srn_mm_get_block(mm, b);
 
  TEST_CHECK(block != nullptr);
  TEST_CHECK(block->next != nullptr);
  TEST_CHECK(block->next->next == nullptr);
  TEST_CHECK((uintptr_t)&block->next->base == (uintptr_t)d2);
 
  TEST_CHECK(
    (uintptr_t)&block->base + 0xffff + padding(sizeof(mm_64k), alignof(mm_64k)) == (uintptr_t)d3
  );
 
  /* DBG_HEX(block, 600); */
  /* DBG_HEX(((char *)(uintptr_t)&block->base + (uintptr_t)0xfff0), 600); */
 
  /* DBG_HEX(block->next, 600); */
 
  srn_mm_shutdown(mm);
}
 
static void test_mm_block_bitmap(void) {
  srn_mm_t *mm = srn_mm_init(nullptr);
  ASSERT_NOT_NULL(mm);
 
  // Initially all bits must be 0 (no user blocks allocated)
  for (int i = 0; i < 4; i++) {
    TEST_CHECK(mm->block_bitmap[i] == 0);
  }
 
  srn_block_id_t b0 = srn_mm_allocate_block(mm);
  srn_block_id_t b1 = srn_mm_allocate_block(mm);
  srn_block_id_t b2 = srn_mm_allocate_block(mm);
 
  MM_TEST_LOG("Allocated block ids: %zu, %zu, %zu", (size_t)b0, (size_t)b1, (size_t)b2);
 
  TEST_CHECK(b0 == 0);
  TEST_CHECK(b1 == 1);
  TEST_CHECK(b2 == 2);
 
  uint64_t word0 = mm->block_bitmap[0];
 
  // Bits 0,1,2 must be set
  TEST_CHECK((word0 & 0x7ULL) == 0x7ULL);
  // Other bits in the first word are untouched
  // and other words should still be zero
  TEST_CHECK(mm->block_bitmap[1] == 0);
  TEST_CHECK(mm->block_bitmap[2] == 0);
  TEST_CHECK(mm->block_bitmap[3] == 0);
 
  srn_mm_shutdown(mm);
}
 
static void test_mm_block_size_properties(void) {
  size_t page_size = srn_mm_get_os_page_size();
 
  TEST_CHECK(page_size > 0);
  // The block size is a power of two derived from the magnitude, so it is a
  // whole number of pages on this platform by construction.
  TEST_CHECK(
    SRN_CONFIG_DEFAULT_BLOCK_SIZE == ((size_t)1 << SRN_CONFIG_DEFAULT_BLOCK_SIZE_MAGNITUDE)
  );
  TEST_CHECK(SRN_CONFIG_DEFAULT_BLOCK_SIZE % page_size == 0);
}
 
static void test_mm_aligned_block_allocation(void) {
  srn_mm_t *mm = srn_mm_init(nullptr);
  ASSERT_NOT_NULL(mm);
 
  srn_block_id_t b = srn_mm_allocate_block(mm);
  MM_TEST_LOG("Allocated block id for aligned test: %zu", (size_t)b);
 
  size_t alignment = 32;
  size_t size      = 13;
 
  void *p1 = srn_mm_allocate_in_block_aligned(mm, b, size, alignment);
  void *p2 = srn_mm_allocate_in_block_aligned(mm, b, size, alignment);
 
  MM_TEST_LOG("Aligned allocations: p1=%p, p2=%p", p1, p2);
 
  TEST_CHECK(p1 != NULL);
  TEST_CHECK(p2 != NULL);
  // The requested alignment is honored, which implies the default block
  // alignment as well.
  TEST_CHECK(((uintptr_t)p1 % alignment) == 0);
  TEST_CHECK(((uintptr_t)p2 % alignment) == 0);
 
  // Quick sanity, both allocations must belong to the same root block
  srn_block_t *block = srn_mm_get_block(mm, b);
  TEST_CHECK(block != nullptr);
 
  uintptr_t base = (uintptr_t)&block->base;
  uintptr_t end  = base + (block->size - offsetof(srn_block_t, base));
 
  TEST_CHECK((uintptr_t)p1 >= base && (uintptr_t)p1 + size <= end);
  TEST_CHECK((uintptr_t)p2 >= base && (uintptr_t)p2 + size <= end);
 
  srn_mm_shutdown(mm);
}
 
static void test_mm_immortal_multiblock(void) {
  srn_mm_t *mm = srn_mm_init(nullptr);
  ASSERT_NOT_NULL(mm);
 
  // Same trick as test_mm_allocation_multiblock but on immortal_block
  MM_TEST_LOG("Allocating mm_64k instances in immortal block");
 
  mm_64k *i1 = srn_mm_immortal_allocate(mm, mm_64k);
  mm_64k *i2 = srn_mm_immortal_allocate(mm, mm_64k);
  mm_64k *i3 = srn_mm_immortal_allocate(mm, mm_64k);
 
  ASSERT_NOT_NULL(i1);
  ASSERT_NOT_NULL(i2);
  ASSERT_NOT_NULL(i3);
 
  for (int i = 0; i < 0xffff; i++) {
    i1->foo[i] = 'X';
    i2->foo[i] = 'Y';
    i3->foo[i] = 'Z';
  }
 
  srn_block_t *root = mm->immortal_block;
  TEST_CHECK(root != nullptr);
  TEST_CHECK(root->next != nullptr);
 
  MM_TEST_LOG("immortal root = %p, next = %p", (void *)root, (void *)root->next);
 
  srn_mm_shutdown(mm);
}
 
/// Block ids are reused after release, so a release must also retire every
/// piece of allocation bookkeeping. These cycles exceed
/// MAX_NUMBER_OF_BLOCKS; only live blocks may count against the limit.
static void test_mm_block_release_reuse(void) {
  srn_mm_t *mm = srn_mm_init(nullptr);
  ASSERT_NOT_NULL(mm);
 
  for (size_t i = 0; i < MAX_NUMBER_OF_BLOCKS + 44; i++) {
    srn_block_id_t b = srn_mm_allocate_block(mm);
    void *p          = srn_mm_allocate_in_block_aligned(mm, b, 64, 16);
    TEST_CHECK(p != nullptr);
    srn_mm_release_block(mm, b);
  }
 
  srn_mm_shutdown(mm);
}
 
/// A released id must not resolve to a block anymore. Handing back the stale
/// pointer lets callers bump allocate into freed memory.
static void test_mm_get_block_after_release(void) {
  srn_mm_t *mm = srn_mm_init(nullptr);
  ASSERT_NOT_NULL(mm);
 
  srn_block_id_t b = srn_mm_allocate_block(mm);
  TEST_CHECK(srn_mm_get_block(mm, b) != nullptr);
 
  srn_mm_release_block(mm, b);
  TEST_CHECK(srn_mm_get_block(mm, b) == nullptr);
 
  srn_mm_shutdown(mm);
}
 
/// Alignments above DEFAULT_BLOCK_ALIGNMENT must be honored on the returned
/// pointer. Aligning the bump offset alone leaves the result at
/// base modulo the requested alignment, and base is only guaranteed to be
/// 16 byte aligned.
static void test_mm_over_aligned_allocation(void) {
  srn_mm_t *mm = srn_mm_init(nullptr);
  ASSERT_NOT_NULL(mm);
 
  srn_block_id_t b = srn_mm_allocate_block(mm);
 
  // Skew the bump offset first so the aligned request cannot start at zero.
  void *skew = srn_mm_allocate_in_block_aligned(mm, b, 1, 1);
  TEST_CHECK(skew != nullptr);
 
  for (size_t alignment = 32; alignment <= 256; alignment *= 2) {
    void *p = srn_mm_allocate_in_block_aligned(mm, b, 24, alignment);
    TEST_CHECK(p != nullptr);
    TEST_MSG("alignment %zu, remainder %zu", alignment, (size_t)((uintptr_t)p % alignment));
    TEST_CHECK(((uintptr_t)p % alignment) == 0);
  }
 
  srn_mm_shutdown(mm);
}
 
// A request that fits a block only if the base happens to be aligned better
// than DEFAULT_BLOCK_ALIGNMENT cannot be served by growing the chain, every
// new block has the same base guarantee. It must be refused up front rather
// than link blocks until either memory runs out or a block happens to land on
// a better aligned base. The request runs in a child with an alarm. A refusal
// ends the child with the panic's signal, a runaway chain ends it with SIGALRM
// or, when a lucky base cuts the walk short, with a normal exit.
static void test_mm_over_aligned_request_near_capacity(void) {
  pid_t pid = fork();
  TEST_ASSERT(pid >= 0);
 
  if (pid == 0) {
    alarm(2);
    srn_mm_t *mm       = srn_mm_init(nullptr);
    srn_block_id_t b   = srn_mm_allocate_block(mm);
    srn_block_t *block = srn_mm_get_block(mm, b);
    size_t capacity    = block->size - offsetof(srn_block_t, base);
 
    // The base only promises DEFAULT_BLOCK_ALIGNMENT, but the provider may
    // hand out something better aligned by chance, so pick the smallest
    // alignment this base actually misses. Every block of the chain comes
    // from the same provider with the same layout, so a fresh one misses it
    // too.
    size_t alignment = 2 * DEFAULT_BLOCK_ALIGNMENT;
    while (alignment <= 4096 && ((uintptr_t)block->base % alignment) == 0) {
      alignment *= 2;
    }
    if (alignment > 4096) {
      // Nothing to show against a page aligned base, count it as refused.
      raise(SIGABRT);
    }
 
    (void)srn_mm_allocate_in_block_aligned(mm, b, capacity - 8, alignment);
    _exit(0);
  }
 
  int status = 0;
  TEST_ASSERT(waitpid(pid, &status, 0) == pid);
  TEST_CHECK(WIFSIGNALED(status));
  TEST_CHECK_(WTERMSIG(status) != SIGALRM, "the chain grew until the alarm fired");
}
 
static void test_mm_get_block_out_of_range(void) {
  srn_mm_t *mm = srn_mm_init(nullptr);
  ASSERT_NOT_NULL(mm);
 
  srn_block_id_t b = srn_mm_allocate_block(mm);
  MM_TEST_LOG("Allocated block id: %zu", (size_t)b);
 
  srn_block_t *block = srn_mm_get_block(mm, b);
  TEST_CHECK(block != nullptr);
 
  // This ID is guaranteed to be out of range
  srn_block_id_t invalid  = b + 100;
  srn_block_t *null_block = srn_mm_get_block(mm, invalid);
  TEST_CHECK(null_block == nullptr);
 
  srn_mm_shutdown(mm);
}