path: root/tests/liballoc_tests.c

/*
 * tests/liballoc_tests.c
 *
 * Unit tests for liballoc
 * CISC 301 -- Operating Systems, Project 3
 *
 * Copyright (C) 2025  Douglas B. Rumbaugh <dbrumbaugh@harrisburgu.edu>
 *
 * Distributed under the Modified BSD License
 *
 */
#include "alloc.h"
#include "constants.h"

#include <check.h>
#include <stdio.h>
#include <stdlib.h>

START_TEST(basic_allocate) {
  void *memory = allocate(ALIGNMENT * 3);
  ck_assert_ptr_nonnull(memory);

  /* verify we can write to the memory w/o segfaulting */
  memset(memory, 0, ALIGNMENT * 3);

  size_t alignment = (size_t)memory % ALIGNMENT;
  ck_assert_int_eq(alignment, 0);

  /* leak the memory--we aren't testing release */
}
END_TEST

START_TEST(multiple_allocations) {
  size_t size = ALIGNMENT * 5;

  void *allocations[100];
  for (size_t i = 0; i < 100; i++) {
    allocations[i] = allocate(size);
    ck_assert_ptr_nonnull(allocations[i]);

    memset(allocations[i], 0, size);

    size_t alignment = (size_t)allocations[i] % ALIGNMENT;
    ck_assert_int_eq(alignment, 0);
  }

  /* verify the headers */
  for (size_t i = 0; i < 100; i++) {
    header *hdr = allocations[i] - sizeof(header);
    ck_assert_int_eq(hdr->size, size);
    ck_assert_int_eq(hdr->magic_number, MAGIC_NUMBER);
  }

  /* leak the memory--we aren't testing release */
}

START_TEST(basic_release) {
  void *memory = allocate(ALIGNMENT * 3);
  ck_assert_ptr_nonnull(memory);

  release(memory);

  free_nd *list_head = free_list_head();
  ck_assert_ptr_nonnull(list_head);
  ck_assert_ptr_eq(list_head, memory);
  ck_assert_int_eq(list_head->size, ALIGNMENT * 3);
  ck_assert_ptr_null(list_head->next);
}
END_TEST

START_TEST(free_list_emptying) {
  void *memory = allocate(ALIGNMENT * 3);
  ck_assert_ptr_nonnull(memory);

  release(memory);

  free_nd *list_head = free_list_head();
  ck_assert_ptr_nonnull(list_head);
  ck_assert_ptr_eq(list_head, memory);
  ck_assert_int_eq(list_head->size, ALIGNMENT * 3);
  ck_assert_ptr_null(list_head->next);

  void *memory2 = allocate(ALIGNMENT * 3);
  ck_assert_ptr_eq(memory, memory2);
  ck_assert_ptr_null(free_list_head());
}

START_TEST(release_null) {
  /* releasing NULL should take no action */
  release(NULL);

  ck_assert_ptr_null(free_list_head());
}
END_TEST

START_TEST(unaligned_allocation) {
  size_t unaligned_size = ALIGNMENT + 3;

  void *allocations[100];
  /* ensure first allocation is aligned */
  allocations[0] = allocate(unaligned_size);
  size_t first_alignment = (size_t)allocations[0] % ALIGNMENT;
  ck_assert_int_eq(first_alignment, 0);

  memset(allocations[0], 0, unaligned_size);

  /* now allocate several more times--each allocation should be aligned */
  for (size_t i = 1; i < 100; i++) {
    allocations[i] = allocate(unaligned_size);
    size_t alignment = (size_t)allocations[i] % ALIGNMENT;
    ck_assert_int_eq(alignment, 0);

    /* verify we can write the the memory */
    memset(allocations[i], 0, unaligned_size);

    /* just leak the memory--we aren't testing release here */
  }

  /* verify the headers */
  for (size_t i = 0; i < 100; i++) {
    header *hdr = allocations[i] - sizeof(header);
    ck_assert_int_eq(hdr->magic_number, MAGIC_NUMBER);
  }
}

START_TEST(free_list_reuse) {
  size_t size = ALIGNMENT * 3;

  void *memory = allocate(size);
  release(memory);

  for (size_t i = 0; i < 10; i++) {
    void *new_memory = allocate(size);
    ck_assert_ptr_eq(memory, new_memory);
    ck_assert_ptr_null(free_list_head());
    release(new_memory);
  }
}
END_TEST

START_TEST(free_list_coalesce_forward) {
  size_t size = ALIGNMENT * 3;
  const size_t n = 100;
  void *ptrs[n];

  for (size_t i = 0; i < n; i++) {
    ptrs[i] = allocate(size);
  }

  /*
   * release memory in forward order. Each release should be
   * coalesced, so there's only ever one free block
   */
  size_t cnt = 0;
  for (size_t i = 0; i < n; i++) {
    release(ptrs[i]);
    cnt++;
    free_nd *fl_head = free_list_head();
    ck_assert_ptr_null(fl_head->next);
    ck_assert_int_eq(fl_head->size, (cnt)*size + (cnt - 1) * sizeof(header));
  }
}
END_TEST

START_TEST(free_list_coalesce_backward) {
  size_t size = ALIGNMENT * 3;
  const size_t n = 100;
  void *ptrs[n];

  for (size_t i = 0; i < n; i++) {
    ptrs[i] = allocate(size);
  }

  /*
   * release memory in reverse order. Each release should be
   * coalesced, so there's only ever one free block
   */
  size_t cnt = 0;
  for (ssize_t i = n - 1; i >= 0; i--) {
    release(ptrs[i]);
    cnt++;
    free_nd *fl_head = free_list_head();
    ck_assert_ptr_null(fl_head->next);
    ck_assert_int_eq(fl_head->size, (cnt)*size + (cnt - 1) * sizeof(header));
  }
}
END_TEST

START_TEST(free_list_split_basic) {
  size_t initial_size = ALIGNMENT * 10;
  size_t second_size = ALIGNMENT * 5;

  void *memory = allocate(initial_size);
  release(memory);

  void *memory2 = allocate(second_size);
  ck_assert_ptr_eq(memory, memory2);

  ck_assert_ptr_nonnull(free_list_head());
}
END_TEST

START_TEST(free_list_split_below_threshold) {
  size_t initial_size = 5 * ALIGNMENT;
  size_t second_size = 2 * ALIGNMENT;

  void *memory = allocate(initial_size);
  release(memory);

  void *memory2 = allocate(second_size);
  ck_assert_ptr_eq(memory, memory2);

  ck_assert_ptr_null(free_list_head());
}

Suite *liballoc_suite(void) {
  Suite *s;
  TCase *unit;

  s = suite_create("liballoc");

  unit = tcase_create("unit");
  tcase_add_test(unit, basic_allocate);
  tcase_add_test(unit, multiple_allocations);
  tcase_add_test(unit, unaligned_allocation);
  tcase_add_test(unit, basic_release);
  tcase_add_test(unit, release_null);
  tcase_add_test(unit, free_list_emptying);
  tcase_add_test(unit, free_list_reuse);
  tcase_add_test(unit, free_list_coalesce_forward);
  tcase_add_test(unit, free_list_coalesce_backward);
  tcase_add_test(unit, free_list_split_basic);
  tcase_add_test(unit, free_list_split_below_threshold);

  suite_add_tcase(s, unit);
  return s;
}

int main(void) {
  int number_failed;
  Suite *s;
  SRunner *sr;

  s = liballoc_suite();
  sr = srunner_create(s);

  srunner_run_all(sr, CK_NORMAL);
  number_failed = srunner_ntests_failed(sr);
  srunner_free(sr);

  exit((number_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE);
}