summaryrefslogtreecommitdiff
path: root/myalloc.c
blob: 303005179468fea2ce68e88c0945f14bcc61befa (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
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);
}