Advertisement
jkonefal

Untitled

Jan 18th, 2023
1,106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 7.33 KB | None | 0 0
  1. /*
  2.  * mm-naive.c - The fastest, least memory-efficient malloc package.
  3.  *
  4.  * In this naive approach, a block is allocated by simply incrementing
  5.  * the brk pointer.  Blocks are never coalesced or reused.  The size of
  6.  * a block is found at the first aligned word before the block (we need
  7.  * it for realloc).
  8.  *
  9.  * This code is correct and blazingly fast, but very bad usage-wise since
  10.  * it never frees anything.
  11.  */
  12. #include <assert.h>
  13. #include <stdio.h>
  14. #include <stdlib.h>
  15. #include <string.h>
  16. #include <stdbool.h>
  17. #include <stdint.h>
  18. #include <stddef.h>
  19. #include <unistd.h>
  20.  
  21. #include "mm.h"
  22. #include "memlib.h"
  23.  
  24. /* If you want debugging output, use the following macro.  When you hand
  25.  * in, remove the #define DEBUG line. */
  26. #define DEBUG
  27. #ifdef DEBUG
  28. #define debug(...) printf(__VA_ARGS__)
  29. #else
  30. #define debug(...)
  31. #endif
  32.  
  33. /* do not change the following! */
  34. #ifdef DRIVER
  35. /* create aliases for driver tests */
  36. #define malloc mm_malloc
  37. #define free mm_free
  38. #define realloc mm_realloc
  39. #define calloc mm_calloc
  40. #endif /* def DRIVER */
  41.  
  42. static uint8_t *heap_begin; // first byte of heap
  43. static uint8_t *heap_end;   // first byte after the heap
  44.  
  45. typedef struct {
  46.   int32_t header;
  47.   /*
  48.    * We don't know what the size of the payload will be, so we will
  49.    * declare it as a zero-length array.  This allow us to obtain a
  50.    * pointer to the start of the payload.
  51.    */
  52.   uint8_t payload[];
  53. } block_t;
  54.  
  55. static size_t round_up(size_t size) {
  56.   return (size + ALIGNMENT - 1) & -ALIGNMENT;
  57. }
  58.  
  59. static size_t get_size(block_t *block) {
  60.   return block->header & -2;
  61. }
  62.  
  63. static size_t get_size_of_payload(block_t *block) {
  64.   return get_size(block) - 2 * offsetof(block_t, payload);
  65. }
  66.  
  67. static block_t *move_right(block_t *ptr, size_t how_much) {
  68.   uint8_t *help_ptr = (uint8_t *)ptr;
  69.   help_ptr += how_much;
  70.   return (block_t *)help_ptr;
  71. }
  72.  
  73. static block_t *move_left(block_t *ptr, size_t how_much) {
  74.   uint8_t *help_ptr = (uint8_t *)ptr;
  75.   help_ptr -= how_much;
  76.   return (block_t *)help_ptr;
  77. }
  78.  
  79. static void set_header(block_t *block, size_t size, bool current_is_allocated) {
  80.   block->header = size | current_is_allocated;
  81. }
  82.  
  83. static void set_footer(block_t *block, size_t size, bool is_allocated) {
  84.   block = move_right(block, size - sizeof(block_t));
  85.   block->header = size | is_allocated;
  86. }
  87.  
  88. static bool expand_heap(size_t size) {
  89.   // creates a free block at the end of heap of size at least 'size'
  90.   // returns true on success
  91.   size = round_up(2 * sizeof(block_t) + size);
  92.   block_t *free_block = mem_sbrk(size);
  93.   if ((long)free_block < 0)
  94.     return false;
  95.  
  96.   heap_end += size;
  97.   set_header(free_block, size, false);
  98.   set_footer(free_block, size, false);
  99.   return true;
  100. }
  101.  
  102. static bool next_is_free(block_t *block_next) {
  103.   return block_next < (block_t *)heap_end && (!(block_next->header & 1));
  104. }
  105.  
  106. static void coalesce_with_next(block_t *left_block_ptr) {
  107.   size_t left_size = get_size(left_block_ptr);
  108.   block_t *block_next = move_right(left_block_ptr, left_size);
  109.   size_t size_sum = left_size;
  110.   if (next_is_free(block_next)) {
  111.     size_sum += get_size(block_next);
  112.   }
  113.   set_header(left_block_ptr, size_sum, false);
  114.   set_footer(left_block_ptr, size_sum, false);
  115. }
  116.  
  117. static bool prev_is_free(block_t *right_block_ptr) {
  118.   block_t *block_prev = right_block_ptr - 1;
  119.   return right_block_ptr > (block_t *)heap_begin && (!(block_prev->header & 1));
  120. }
  121.  
  122. static void coalesce_with_prev(block_t *right_block_ptr) {
  123.   block_t *block_prev = right_block_ptr - 1;
  124.   if (prev_is_free(right_block_ptr)) {
  125.     block_t *block_prev_start =
  126.       move_left(block_prev, get_size(block_prev) - sizeof(block_t));
  127.     size_t size_sum = get_size(right_block_ptr) + get_size(block_prev_start);
  128.     set_header(block_prev_start, size_sum, false);
  129.     set_footer(block_prev_start, size_sum, false);
  130.   }
  131. }
  132.  
  133. static void split_blocks(block_t *block_ptr, size_t size) {
  134.   size_t final_block_size = get_size(block_ptr);
  135.   size_t needed_size = round_up(2 * sizeof(block_t) + size);
  136.   if (get_size(block_ptr) - 2 * sizeof(block_t) > needed_size) {
  137.     block_t *new_block_ptr = move_right(block_ptr, needed_size);
  138.     size_t  new_block_size = get_size(block_ptr) - needed_size;
  139.     // if next block is free, we merge it with the current block
  140.     set_header(new_block_ptr, new_block_size, false);
  141.     set_footer(new_block_ptr, new_block_size, false);
  142.     final_block_size = needed_size;
  143.   }
  144.   set_header(block_ptr, final_block_size, true);
  145.   set_footer(block_ptr, final_block_size, true);
  146. }
  147. /*
  148.  * mm_init - Called when a new trace starts.
  149.  */
  150. int mm_init(void) {
  151.   /* Pad heap start so first payload is at ALIGNMENT. */
  152.   size_t offset = ALIGNMENT - sizeof(block_t);
  153.   uint8_t *fake_begin = mem_sbrk(offset);
  154.   if ((long)fake_begin < 0)
  155.     return -1;
  156.   heap_begin = fake_begin + offset;
  157.   heap_end = heap_begin;
  158.   return 0;
  159. }
  160.  
  161. /*
  162.  * malloc - Allocate a block by incrementing the brk pointer.
  163.  *      Always allocate a block whose size is a multiple of the alignment.
  164.  */
  165. void *malloc(size_t size) {
  166.   uint8_t *cur_ptr = heap_begin;
  167.   while (cur_ptr < heap_end) {
  168.     block_t *block_ptr = (block_t *)cur_ptr;
  169.     if (!(block_ptr->header & 1) && get_size_of_payload(block_ptr) >= size) {
  170.       break;
  171.     }
  172.     cur_ptr += get_size(block_ptr);
  173.   }
  174.   if (cur_ptr == heap_end) {
  175.     if (!expand_heap(size))
  176.       return NULL;
  177.   }
  178.  
  179.   block_t *block_ptr = (block_t *)cur_ptr;
  180.   split_blocks(block_ptr, size);
  181.   return block_ptr->payload;
  182. }
  183.  
  184. /*
  185.  * free - We don't know how to free a block.  So we ignore this call.
  186.  *      Computers have big memories; surely it won't be a problem.
  187.  */
  188. void free(void *ptr) {
  189.   if (ptr == NULL)
  190.     return;
  191.   block_t *block_ptr = (block_t *)ptr;
  192.   block_ptr -= 1;
  193.   coalesce_with_next(block_ptr);
  194.   coalesce_with_prev(block_ptr);
  195. }
  196.  
  197. /*
  198.  * realloc - Change the size of the block by mallocing a new block,
  199.  *      copying its data, and freeing the old block.
  200.  **/
  201. void *realloc(void *old_ptr, size_t size) {
  202.   /* If size == 0 then this is just free, and we return NULL. */
  203.   if (size == 0) {
  204.     free(old_ptr);
  205.     return NULL;
  206.   }
  207.  
  208.   /* If old_ptr is NULL, then this is just malloc. */
  209.   if (!old_ptr)
  210.     return malloc(size);
  211.  
  212.   block_t *old_block_ptr = (block_t *)old_ptr;
  213.   old_block_ptr -= 1;
  214.   size_t old_size = get_size(old_block_ptr);
  215.   if (size + 2 * sizeof(block_t) < old_size) {
  216.     split_blocks(old_block_ptr, size);
  217.      if (move_right(old_block_ptr, get_size(old_block_ptr)) < (block_t*)heap_end)
  218.        coalesce_with_next(move_right(old_block_ptr, get_size(old_block_ptr)));
  219.     return old_ptr;
  220.   }
  221.  
  222.   else {
  223.     void *new_ptr = malloc(size);
  224.  
  225.     /* If malloc() fails, the original block is left untouched. */
  226.     if (!new_ptr)
  227.       return NULL;
  228.  
  229.     /* Copy the old data. */
  230.     old_size -= 2 * sizeof(block_t);
  231.     // if (size < old_size)
  232.     //   old_size = size;
  233.     memcpy(new_ptr, old_ptr, old_size);
  234.     free(old_ptr);
  235.     return new_ptr;
  236.   }
  237. }
  238.  
  239. /*
  240.  * calloc - Allocate the block and set it to zero.
  241.  */
  242. void *calloc(size_t nmemb, size_t size) {
  243.   size_t bytes = nmemb * size;
  244.   void *new_ptr = malloc(bytes);
  245.  
  246.   /* If malloc() fails, skip zeroing out the memory. */
  247.   if (new_ptr)
  248.     memset(new_ptr, 0, bytes);
  249.  
  250.   return new_ptr;
  251. }
  252.  
  253. /*
  254.  * mm_checkheap - So simple, it doesn't need a checker!
  255.  */
  256. void mm_checkheap(int verbose) {
  257. }
  258.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement