Intial commit: No free list management yet

10 files changed, 390 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..f9ed49a
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+bin/*
+build/*
+lib/*
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..c3e87d9
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,30 @@
+BSD 3-Clause License
+
+Copyright (c) 2025, Douglas B. Rumbaugh <dbrumbaugh@harrisburgu.edu>
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions
+are met:
+
+1. Redistributions of source code must retain the above copyright notice, 
+   this list of conditions and the following disclaimer.
+
+2. Redistributions in binary form must reproduce the above copyright 
+   notice, this list of conditions and the following disclaimer in the 
+   documentation and/or other materials provided with the distribution.
+
+3. Neither the name of the copyright holder nor the names of its
+   contributors may be used to endorse or promote products derived from
+   this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
+TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..0ba98c3
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,20 @@
+all: lib/liballoc.a bin/liballoc_tests
+
+bin/liballoc_tests: lib/liballoc.a build
+	gcc -Iinclude tests/liballoc_tests.c -lcheck -pthread -lsubunit -lm lib/liballoc.a -o bin/liballoc_tests
+
+lib/liballoc.a: build/alloc.o build/free_list.o build
+	ar rcs lib/liballoc.a build/alloc.o build/free_list.o
+
+build/alloc.o: build
+	gcc -Iinclude -c src/alloc.c -o build/alloc.o
+
+build/free_list.o: build
+	gcc -Iinclude -c src/free_list.c -o build/free_list.o
+
+.PHONY: build clean
+build:
+	-mkdir build bin lib
+
+clean:
+	-rm -r build bin lib
diff --git a/compile_flags.txt b/compile_flags.txt
new file mode 100644
index 0000000..30679be
--- /dev/null
+++ b/compile_flags.txt
@@ -0,0 +1 @@
+-Iinclude
diff --git a/include/alloc.h b/include/alloc.h
new file mode 100644
index 0000000..cdbdb37
--- /dev/null
+++ b/include/alloc.h
@@ -0,0 +1,38 @@
+/*
+ * include/alloc.h
+ *
+ * Primary header for liballoc API
+ * CISC 301 -- Operating Systems, Project 3
+ *
+ * Copyright (C) 2025  Douglas B. Rumbaugh <dbrumbaugh@harrisburgu.edu>
+ * 
+ * Distributed under the Modified BSD License
+ *
+ */
+#ifndef H_LIBALLOC
+#define H_LIBALLOC
+
+#include <assert.h>
+#include <stdio.h>
+#include <unistd.h>
+
+#include "constants.h"
+#include "free_list.h"
+
+/*
+ * Returns a pointer to a new region of memory of the specified
+ * size, or NULL if no memory is available.
+ */
+void *allocate(size_t);
+
+/*
+ * Release a block of memory previous allocated using allocate(). If the
+ * input pointer was not returned by allocate(), then the behavior of
+ * this function is undefined.
+ *
+ * Accessing a pointer that has been previous passed to this function is
+ * undefined behavior.
+ */
+void release(void *);
+
+#endif
diff --git a/include/constants.h b/include/constants.h
new file mode 100644
index 0000000..7d88060
--- /dev/null
+++ b/include/constants.h
@@ -0,0 +1,18 @@
+/*
+ * include/constants.h
+ *
+ * Configuration constant values for liballoc
+ * CISC 301 -- Operating Systems, Project 3
+ *
+ * Copyright (C) 2025  Douglas B. Rumbaugh <dbrumbaugh@harrisburgu.edu>
+ * 
+ * Distributed under the Modified BSD License
+ *
+ */
+#ifndef H_LIBALLOC_CONST
+#define H_LIBALLOC_CONST
+
+#define MAGIC_NUMBER 0x123456789
+#define ALIGNMENT 16
+
+#endif
diff --git a/include/free_list.h b/include/free_list.h
new file mode 100644
index 0000000..887167b
--- /dev/null
+++ b/include/free_list.h
@@ -0,0 +1,52 @@
+/*
+ * include/free_list.h
+ *
+ * Free list management routines for liballoc
+ * CISC 301 -- Operating Systems, Project 3
+ *
+ * Copyright (C) 2025  Douglas B. Rumbaugh <dbrumbaugh@harrisburgu.edu>
+ * 
+ * Distributed under the Modified BSD License
+ *
+ */
+#ifndef H_LIBALLOC_FREELIST
+#define H_LIBALLOC_FREELIST
+
+#include <stdlib.h>
+
+#include "constants.h"
+
+typedef struct free_nd {
+  size_t size;
+  struct free_nd *next;
+} free_nd;
+
+/*
+ * Scans the specified free list for the first node with >= the
+ * specified size and returns a pointer to it. If no such node can
+ * be found, returns NULL.
+ */
+free_nd *fl_find_first_fit(free_nd *free_list, size_t size);
+
+/*
+ * Split the specified free list node based on the required size, while
+ * maintaining alignment, and update the free list accordingly. If the
+ * specified node cannot be split (e.g., it's an exact match for size
+ * within alignment restrictions), simply remove it from the list.
+ *
+ * Returns a pointer to the region of memory removed from the list.
+ */
+void *fl_split_node(free_nd *free_list, free_nd *nd, size_t size);
+
+/*
+ * Scans the free list for adjacent nodes and merges them together
+ */
+void fl_coalesce_nodes(free_nd *free_list);
+
+/*
+ * Scans the free list for the correct location for the specified
+ * pointer, and link it into the list at that point.
+ */
+void fl_add_node(free_nd *free_list, void *ptr);
+
+#endif
diff --git a/src/alloc.c b/src/alloc.c
new file mode 100644
index 0000000..c13b1e8
--- /dev/null
+++ b/src/alloc.c
@@ -0,0 +1,87 @@
+/*
+ * src/alloc.c
+ *
+ * Primary implementation of allocator logic 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 "free_list.h"
+
+typedef struct header {
+  size_t size;
+  size_t magic_number;
+} header;
+
+static_assert(sizeof(header) % ALIGNMENT == 0, "Header improperly aligned");
+
+static void *heap_start = 0;
+static void *heap_end = 0;
+free_nd *free_list = NULL;
+
+static void initialize() {
+  heap_start = sbrk(0);
+
+  if (heap_start == (void *)-1) {
+    perror("liballoc initialization:");
+    exit(EXIT_FAILURE);
+  }
+
+  size_t padding = (size_t)heap_start % ALIGNMENT;
+  if (padding) {
+    heap_start = sbrk(padding);
+    if (heap_start == (void *)-1) {
+      perror("liballoc initialization:");
+      exit(EXIT_FAILURE);
+    }
+  }
+
+  assert((size_t)heap_start % ALIGNMENT == 0);
+  heap_end = heap_start;
+}
+
+void *allocate(size_t size) {
+  if (!heap_start) {
+    initialize();
+  }
+
+  /*
+   * pad the requested size to ensure alignment using
+   * the alignment one-liner we discussed in class
+   */
+  size = (size + ALIGNMENT - 1) & ~(ALIGNMENT - 1);
+
+  /* first check for a suitable memory block on the free list */
+  free_nd *nd = fl_find_first_fit(free_list, size);
+  if (nd) {
+    void *return_region = fl_split_node(free_list, nd, size);
+  }
+
+  /*
+   * if there aren't any blocks on the free list, we need to allocate
+   * from scratch
+   */
+  void *new_region = sbrk(size + sizeof(header));
+
+  /* out of memory */
+  if (new_region == (void *)-1) {
+    return NULL;
+  }
+
+  heap_end = new_region + size + sizeof(header);
+
+  ((header *)new_region)->size = size;
+  ((header *)new_region)->magic_number = MAGIC_NUMBER;
+
+  return new_region + sizeof(header);
+}
+
+void release(void *ptr) {
+  fl_add_node(free_list, ptr);
+  fl_coalesce_nodes(free_list);
+}
diff --git a/src/free_list.c b/src/free_list.c
new file mode 100644
index 0000000..c1dd79c
--- /dev/null
+++ b/src/free_list.c
@@ -0,0 +1,22 @@
+/*
+ * src/free_list.c
+ *
+ * Implementation of free list management for liballoc
+ * CISC 301 -- Operating Systems, Project 3
+ *
+ * Copyright (C) 2025  Douglas B. Rumbaugh <dbrumbaugh@harrisburgu.edu>
+ * 
+ * Distributed under the Modified BSD License
+ *
+ */
+#include "free_list.h"
+
+free_nd *fl_find_first_fit(free_nd *free_list, size_t size) { return NULL; }
+
+void *fl_split_node(free_nd *free_list, free_nd *nd, size_t size) {
+  return NULL;
+}
+
+void fl_coalesce_nodes(free_nd *free_list) {}
+
+void fl_add_node(free_nd *free_list, void *ptr) {}
diff --git a/tests/liballoc_tests.c b/tests/liballoc_tests.c
new file mode 100644
index 0000000..235656d
--- /dev/null
+++ b/tests/liballoc_tests.c
@@ -0,0 +1,119 @@
+/*
+ * 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 <stdlib.h>
+#include <stdio.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;
+  for (size_t i=0; i<100; i++) {
+    void *memory = allocate(size);
+    ck_assert_ptr_nonnull(memory);
+
+    memset(memory, 0, size);
+
+    size_t alignment = (size_t) memory % ALIGNMENT;
+    ck_assert_int_eq(alignment, 0);
+  }
+
+  /* leak the memory--we aren't testing release */
+}
+
+START_TEST(basic_release) {
+  void *memory = allocate(ALIGNMENT * 3);
+  ck_assert_ptr_nonnull(memory);
+
+  release(memory);
+
+  // TODO: verify entry on the free list
+}
+END_TEST
+
+START_TEST(release_null) {
+  /* releasing NULL should take no action */
+  release(NULL);
+
+  // TODO: verify no entry on free list
+}
+END_TEST
+
+START_TEST(unaligned_allocation) {
+  size_t unaligned_size = ALIGNMENT + 3;
+
+  /* ensure first allocation is aligned */
+  void *first_memory = allocate(unaligned_size);
+  size_t first_alignment = (size_t) first_memory % ALIGNMENT;
+  fprintf(stderr, "ALIGNMENT: %ld\n", first_alignment);
+  ck_assert_int_eq(first_alignment, 0);
+
+  /* now allocate several more times--each allocation should be aligned */
+  for (size_t i=0; i<10; i++) {
+    void *memory = allocate(unaligned_size);
+    size_t alignment = (size_t) memory % ALIGNMENT;
+    fprintf(stderr, "ALIGNMENT: %ld\n", alignment);
+    ck_assert_int_eq(alignment, 0);
+
+    /* just leak the memory--we aren't testing release here */
+  }
+}
+
+
+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);
+
+
+  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);
+}