diff options
-rw-r--r-- | README.md | 15 | ||||
-rwxr-xr-x | myalloc.c | 571 | ||||
-rw-r--r-- | report.pdf | bin | 0 -> 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 Binary files differnew file mode 100644 index 0000000..5651580 --- /dev/null +++ b/report.pdf |