summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTom Harley2018-07-05 16:29:19 +0100
committerTom Harley2018-07-05 16:29:19 +0100
commitc957a725a9436b34f4db708557312d5ecd25b37b (patch)
tree65313ffb0198efa42011bcd0752c133b06391673
downloadalloc-c957a725a9436b34f4db708557312d5ecd25b37b.tar.gz
alloc-c957a725a9436b34f4db708557312d5ecd25b37b.zip

Initial commit

-rw-r--r--README.md15
-rwxr-xr-xmyalloc.c571
-rw-r--r--report.pdfbin0 -> 304525 bytes
3 files changed, 586 insertions, 0 deletions
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..5eff626
--- /dev/null
+++ b/README.md
@@ -0,0 +1,15 @@
+A _C_ implementation of `malloc` and `free` functions.
+
+## Debugging Mode
+
+Compiling with `MYALLOC_DEBUG` defined will cause debugging messages to be
+output to `stderr` when running.
+
+## _Doxygen_ Documentation Generation
+
+`myalloc.c` is a shell script, and can be run as
+```shell
+sh myalloc.c
+```
+
+The "homepage" file generated is `docs/myalloc_8c.html`.
diff --git a/myalloc.c b/myalloc.c
new file mode 100755
index 0000000..3030051
--- /dev/null
+++ b/myalloc.c
@@ -0,0 +1,571 @@
+#if 0
+ (
+ echo "PROJECT_NAME=CS3104P1"
+ echo "INPUT=myalloc.c"
+ echo "OPTIMIZE_OUTPUT_FOR_C=YES"
+ echo "EXTRACT_STATIC=YES"
+ echo "GENERATE_LATEX=NO"
+ echo "GENERATE_HTML=YES"
+ echo "HTML_OUTPUT=docs"
+ ) | doxygen -
+ exit
+#endif
+
+/**
+ * @file myalloc.c
+ * @author Stuart Norcross
+ * @author 150001937
+ * $Date: 4 Oct 2017 $
+ * @brief Submission for CS3104 Practical 1 ("myalloc")
+ *
+ * Single submission file for CS3104's first 2017 practical,
+ * to implement `malloc` and `free` under the names `myalloc` and
+ * `myfree` respectively.
+ *
+ * This file was originally created by Stuart Norcross on 12/03/2010
+ * and has been edited and completed by the submitter for this
+ * practical submission.
+ */
+
+// for sysconf():
+#include <unistd.h>
+// for bool:
+#include <stdbool.h>
+// for size_t:
+#include <stddef.h>
+// for mmap(), munmap() and associated constants:
+#include <sys/mman.h>
+// for uintptr_t:
+#include <stdint.h>
+// for assert():
+#include <assert.h>
+
+#include "myalloc.h"
+
+/**
+ * @brief Returns `n` rounded up the nearest multiple of `t`.
+ *
+ * If `n` is already a multiple of `t`, `n` is returned.
+ *
+ * @param n The value to round up.
+ * @param t The modulus to use when rounding.
+ */
+#define round_up(n, t) (((n) % (t)) ? (((n) / (t)) + 1) * (t) : (n))
+
+/**
+ * @brief A data type exactly one byte wide.
+ *
+ * A simple zero-cost abstraction since logically chars are not being used.
+ */
+typedef char byte;
+
+/**
+ * @brief Header containing persistent information about the
+ * directly-following memory.
+ *
+ * Although this `struct` only contains one value, it is left as
+ * a `struct`:
+ * - to promote alignment of the following memory by the compiler,
+ * - to allow the addition of other values at a later date.
+ */
+typedef struct header {
+ /** The size of the headed memory space, in bytes. */
+ size_t size;
+} header;
+
+/**
+ * @brief Non-persistent information related to a memory space.
+ *
+ * Any information related to a memory space that is unreliable after
+ * being given to a user and later returned should go here.
+ *
+ * This `struct` is placed straight after the memory space's `header`,
+ * inside the memory that would be given to the user, and is
+ * theoretically overwritten by the user. This is done to reduce the
+ * space taken up by `header`s.
+ */
+typedef struct flnode {
+ /** The next `flnode` in the free-list. */
+ struct flnode* next;
+ /** The previous `flnode` in the free-list. */
+ struct flnode* prev;
+} flnode;
+
+/**
+ * @brief Total size required to store information about a chunk of memory.
+ */
+static const size_t META_SIZE = sizeof(header) + sizeof(flnode);
+
+/**
+ * @brief Global marker representing start of free-list.
+ */
+static header* start = NULL;
+
+/**
+ * @brief Global marker representing end of free-list.
+ */
+static header* end = NULL;
+
+/**
+ * @brief Global "constant" representing the size of a page in bytes.
+ *
+ * Calculated at runtime.
+ */
+static long PAGE_SIZE = 0;
+
+/**
+ * @brief Returns the `header` associated with the given `node`.
+ *
+ * @param n The `node` to find the `header` for.
+ * @returns The `header` associated with the given `node`.
+ */
+static header* get_header(flnode* n);
+
+/**
+ * @brief Returns the `node` associated with the given `header`.
+ *
+ * @param h The `header` to find the `node` for.
+ * @returns The `node` associated with the given `header`.
+ */
+static flnode* get_node(header* h);
+
+/**
+ * @brief Returns a pointer pointing at the "end" of the given `header`.
+ *
+ * @param h The `header` to find the "end" of.
+ * @returns A pointer pointing to the "end" of the given `header`.
+ */
+static byte* end_of_header(header* h);
+
+/**
+ * @brief Returns the last `flnode` in a free-list.
+ *
+ * @param start_of_list The start of the list to find the end of.
+ * @returns The `flnode` of the last item in the list.
+ */
+static flnode* last_node(header* start_of_list);
+
+/**
+ * @brief Finds the first item in a free-list with enough space to store
+ * data of size `s`.
+ *
+ * @param minimum_size The minimum size of the `flnode`-to-be-returned, in
+ * bytes.
+ * @param start_of_list The free-list to search through.
+ * @returns The first item in the free-list with enough space to store data
+ * of `s` bytes; `NULL` otherwise.
+ */
+static header* first_enough_space(
+ size_t minimum_size, flnode* start_of_list);
+
+/**
+ * @brief Finds the first item in a free-list with enough space to store
+ * data of size `s`.
+ *
+ * @param minimum_size The minimum size of the `flnode`-to-be-returned, in
+ * bytes.
+ * @param start_of_list The free-list to search through.
+ * @returns The smallest item in the free-list with enough space to store
+ * data of `s` bytes; `NULL` otherwise.
+ */
+static header* smallest_enough_space(
+ size_t minimum_size, flnode* start_of_list);
+
+/**
+ * @brief Finds the last item in a free-list that precedes a given `flnode`.
+ *
+ * If `m` is `NULL`, uses the global variable `start` in its place.
+ *
+ * @param n The `flnode` to check against.
+ * @param start_of_list The start of the free-list to traverse.
+ * @returns The `flnode` that would be before `n` in the free-list,
+ * were `n` in the free-list.
+ */
+static flnode* node_before(flnode* n, flnode* start_of_list);
+
+/**
+ * @brief Checks if two `flnode`s represent spaces directly adjacent in
+ * memory.
+ *
+ * @param left_node The "left" (smaller-address) `flnode`.
+ * @param right_node The "right" (larger-address) `flnode`.
+ * @returns `TRUE` if `n` directly precedes `m` in memory, `FALSE`
+ * otherwise.
+ */
+static bool is_contiguous(flnode* left_node, flnode* right_node);
+
+/**
+ * @brief Stitches two contiguous `flnode`s together.
+ *
+ * The size of the new `flnode` is calculated as the sum of the sizes of the
+ * two given `flnode`s, plus the size of a `header`.
+ *
+ * @param left_node The "left" (smaller-address) `flnode`.
+ * @param right_node The "right" (larger-address) `flnode`.
+ * @returns The `flnode` produced from the stitch (usually `n`).
+ */
+static flnode* stitch(flnode* left_node, flnode* right_node);
+
+/**
+ * @brief Splits a memory space into two.
+ *
+ * The `header` given as `l` will always be preserved, and will never be
+ * the `header` returned by `split`.
+ *
+ * @param to_split The `header` of the memory to split.
+ * @param minimum_split_size The minimum size of the resulting memory space.
+ * @param size_includes_header Whether or not `size` includes the size of a
+ * `header`.
+ * @returns The `header` of the new space produced by the split.
+ */
+static header* split(header* to_split, size_t minimum_split_size,
+ bool size_includes_header);
+
+/**
+ * @brief Removes a `flnode` from a free-list.
+ *
+ * @param to_remove The `flnode` to remove.
+ */
+static void remove_node(flnode* to_remove);
+
+/**
+ * @brief Adds a `flnode` to a free-list.
+ *
+ * The `flnode`-to-be-added may be stitched together with an adjacent
+ * `flnode`(s). For this reason, it's important to use the value returned
+ * by `add_node`.
+ *
+ * @param to_add The `flnode` to add to the free-list.
+ * @returns The `flnode` added to the free-list.
+ */
+static flnode* add_node(flnode* to_add);
+
+/**
+ * @brief `munmap`s all pages contained _entirely_ by the given memory
+ * space.
+ *
+ * @param h The `header` to `munmap` from.
+ * @returns The `header` heading the remainder space on the other side
+ * of the unmapped memory from `h` (or `NULL` if there is no remainder
+ * there).
+ */
+static header* unmap_excess_pages(header* h);
+
+/**
+ * @brief `mmap`s for extra pages.
+ *
+ * @param minimum_size The minimum number of bytes of memory required.
+ * @returns The `header` of some newly-allocated space capable of storing
+ * at least `min` bytes.
+ */
+static header* more_memory(size_t minimum_size);
+
+/**
+ * @brief Allocates memory for the user to use for data storage.
+ *
+ * @param size The size of the memory space requested, in bytes.
+ * @returns A pointer to memory, at least the size of that requested,
+ * that the user can write to, or `NULL` if such memory cannot be
+ * allocated.
+ */
+void* myalloc(int size);
+
+/**
+ * @brief Frees a chunk of memory, allowing other processes to use it.
+ *
+ * @param ptr A pointer to the start of the memory that should be freed.
+ */
+void myfree(void* ptr);
+
+#ifdef MYALLOC_DEBUG
+ #include <stdio.h>
+
+ #define debug(...) fprintf(stderr, __VA_ARGS__)
+
+ void debug_print_list(header* s) {
+ long unsigned i = 0;
+ while (s && get_node(s)) {
+ debug("|%p -> %p|\n", s, end_of_header(s) + s->size);
+ s = get_header(get_node(s)->next);
+ ++i;
+ }
+ debug("free-list is %lu items long\n", i);
+ }
+#else
+ #define debug(...)
+ #define debug_print_list(s)
+#endif
+
+static header* get_header(flnode* n) {
+ return ((header*) n) - 1;
+}
+
+static flnode* get_node(header* h) {
+ return (flnode*) (h + 1);
+}
+
+static byte* end_of_header(header* h) {
+ return (byte*) (h + 1);
+}
+
+static flnode* last_node(header* h) {
+ flnode* n = get_node(h);
+ for (; n->next; n = n->next);
+ return n;
+}
+
+static header* first_enough_space(size_t s, flnode* n) {
+ for (; n; n = n->next) {
+ header* h = get_header(n);
+ if (h->size >= s) {
+ return h;
+ }
+ }
+ return NULL;
+}
+
+static header* smallest_enough_space(size_t s, flnode* n) {
+ struct { header* adr; size_t size; } t;
+ t.adr = NULL;
+ for (; n; n = n->next) {
+ header* h = get_header(n);
+ size_t x = h->size;
+ if (x == s) {
+ return h;
+ }
+ if (x > s) {
+ if ((!t.adr) || (x < t.size)) {
+ t.adr = h;
+ t.size = x;
+ }
+ }
+ }
+ return t.adr;
+}
+
+static flnode* node_before(flnode* n, flnode* m) {
+ debug("finding node before %p...", n);
+ m = m ? m : get_node(start);
+ flnode* p = NULL;
+ while (m) {
+ if (m >= n) {
+ break;
+ }
+ p = m;
+ m = m->next;
+ }
+ debug("got %p\n", p);
+ return p;
+}
+
+static bool is_contiguous(flnode* n, flnode* m) {
+ header* nh = get_header(n);
+ header* mh = get_header(m);
+ bool ret = (header*) (end_of_header(nh) + (nh->size)) == mh;
+ debug("is %p + %zu + %i == %p? %s\n", nh, nh->size, sizeof(header), mh,
+ ret ? "yes" : "no");
+ return ret;
+}
+
+static flnode* stitch(flnode* n, flnode* m) {
+ debug("stitching %p to %p...", n, m);
+ get_header(n)->size += get_header(m)->size + sizeof(header);
+ debug("done\n");
+ return n;
+}
+
+static header* split(header* l, size_t size, bool size_includes_header) {
+ size_t rs = size - (size_includes_header ? sizeof(header) : 0);
+ if (rs < sizeof(flnode)) {
+ rs = sizeof(flnode);
+ }
+ rs = round_up(rs, sizeof(header));
+
+ if (l->size < (rs + (size_includes_header ? 0 : sizeof(header)))) {
+ return NULL;
+ }
+ size_t ls = l->size - rs - (size_includes_header ? 0 : sizeof(header));
+ if (ls < sizeof(flnode)) {
+ return NULL;
+ }
+
+ debug("splitting node at %p (%zu", l, l->size);
+ l->size = ls;
+ header* r = (header*) (end_of_header(l) + ls);
+ r->size = rs;
+ debug("->>%zu) new node at %p\n", l->size, r);
+
+ return r;
+}
+
+static void remove_node(flnode* n) {
+ debug("removing %p from free-list (%p and %p)\n", n, n->next, n->prev);
+ if (n == get_node(start)) start = n->next ? get_header(n->next) : NULL;
+ if (n->next) n->next->prev = n->prev;
+ if (n->prev) n->prev->next = n->next;
+ if (n == get_node(end)) end = n->prev ? get_header(n->prev) : NULL;
+}
+
+static flnode* add_node(flnode* n) {
+ flnode* m;
+
+ debug("adding %p to freelist...\n", n);
+ m = node_before(n, NULL);
+ if (m) {
+ // if there is a node before n in the freelist
+ if (is_contiguous(m, n)) {
+ // if n is directly after the node before it
+ stitch(m, n);
+ n = m;
+ } else {
+ if (m->next) {
+ // if n isn't the new last node in the list
+ m->next->prev = n;
+ } else {
+ // if n is the new last node in the list
+ end = get_header(n);
+ }
+ n->next = m->next;
+ n->prev = m;
+ m->next = n;
+ }
+ } else {
+ // if there is not a node preceding n in the list
+ get_node(start)->prev = n;
+ n->next = get_node(start);
+ start = get_header(n);
+ }
+
+ m = n->next;
+ if (m && is_contiguous(n, m)) {
+ stitch(n, m);
+ remove_node(m);
+ }
+
+ return n;
+}
+
+static header* unmap_excess_pages(header* h) {
+ debug("investigating %p for free pages...", h);
+ if ((h->size + sizeof(header)) < PAGE_SIZE) {
+ return h;
+ }
+
+ // find the first page boundary after the start of the node
+ byte* p = (byte*) h;
+
+ // some casting for pointer arithmetic
+ uintptr_t pi = (uintptr_t) p;
+ uintptr_t qi = pi;
+ if (qi % PAGE_SIZE) {
+ qi = round_up(qi + META_SIZE, PAGE_SIZE);
+ }
+
+ byte* q = (byte*) qi;
+ byte* e = p + h->size + sizeof(header);
+
+ // find number of free pages
+ int pages = (e - q) / PAGE_SIZE;
+ debug("found %i pages to unmap\n", pages);
+
+ // I can't find anywhere what munmap-ing with a range of 0 does,
+ // so this is just in case it would do something bad:
+ if (!pages) {
+ return h;
+ }
+
+ size_t r = e - (q + (pages * PAGE_SIZE));
+
+ header* rh = NULL;
+ if (r) {
+ rh = split(h, r, true);
+ if (!rh) {
+ --pages;
+ if (!pages) {
+ return h;
+ }
+ rh = split(h, r + PAGE_SIZE, true);
+ }
+ }
+
+ if (q == (byte*) h) {
+ remove_node(get_node(h));
+ } else {
+ h->size = q - end_of_header(h);
+ }
+
+ munmap(q, pages * PAGE_SIZE);
+
+ return rh;
+}
+
+static header* more_memory(size_t min) {
+ static const int PFLAGS = PROT_EXEC | PROT_READ | PROT_WRITE;
+ static const int FLAGS = MAP_ANONYMOUS | MAP_PRIVATE;
+
+ if (!PAGE_SIZE) {
+ PAGE_SIZE = sysconf(_SC_PAGESIZE);
+ assert((META_SIZE / PAGE_SIZE) == 0);
+ }
+
+ size_t claimed_size = round_up(min + sizeof(header), PAGE_SIZE);
+
+ debug("asking for %luB (<=%lu page(s))...", min, claimed_size / PAGE_SIZE);
+ header* out = (header*) mmap(NULL, claimed_size, PFLAGS, FLAGS, -1, 0);
+ debug("got %p -> %p\n", out, ((byte*) out) + claimed_size);
+
+ out->size = claimed_size - sizeof(header);
+
+ flnode* outn = get_node(out);
+ outn->next = NULL;
+ outn->prev = NULL;
+
+ return out;
+}
+
+void* myalloc(int size) {
+ if (size < 1) {
+ return NULL;
+ }
+
+ size_t min = (size_t) size;
+
+ if (!start) {
+ // we should get some memory
+ start = more_memory(min);
+ end = start;
+ }
+
+ header* h = smallest_enough_space(min, get_node(start));
+ if (!h) {
+ // we need a bigger contiguous space
+ h = get_header(add_node(get_node(more_memory(min))));
+ }
+
+ header* g = split(h, min, false);
+ if (!g) {
+ remove_node(get_node(h));
+ g = h;
+ if (g == start) {
+ start = NULL;
+ }
+ }
+
+ debug_print_list(start);
+
+ return end_of_header(g);
+}
+
+void myfree(void* ptr){
+ flnode* n = (flnode*) ptr;
+ n->next = NULL;
+ n->prev = NULL;
+ debug("%p has been freed!\n", ptr);
+ if (!start) {
+ start = get_header(n);
+ } else {
+ n = add_node(n);
+ unmap_excess_pages(get_header(n));
+ }
+ debug_print_list(start);
+}
diff --git a/report.pdf b/report.pdf
new file mode 100644
index 0000000..5651580
--- /dev/null
+++ b/report.pdf
Binary files differ