Advertisement
CSenshi

Malloc

Jul 14th, 2020
1,353
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 4.38 KB | None | 0 0
  1. /*
  2.  * mm_alloc.c
  3.  *
  4.  * Stub implementations of the mm_* routines.
  5.  */
  6.  
  7. #include "mm_alloc.h"
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <string.h>
  11. #include <unistd.h>
  12.  
  13. #define METADATA_SIZE (sizeof(struct block))
  14. #define _GET_METADATA(ptr) ((struct block *)(ptr - METADATA_SIZE))
  15.  
  16. void *_get_memory(size_t size, struct block *prev);
  17. void *_find_free_block(size_t size, struct block **prev);
  18.  
  19. void _split_block(struct block *block, size_t size);
  20. void _merge_free_blocks(struct block *block);
  21.  
  22. int DBG = 0;
  23.  
  24. void *mm_malloc(size_t size)
  25. {
  26.     if (size <= 0)
  27.         return NULL;
  28.  
  29.     // first allocation
  30.     if (!head)
  31.     {
  32.         head = _get_memory(size, NULL);
  33.         _mm_print("HEAD");
  34.         return head->data;
  35.     }
  36.  
  37.     struct block *prev;
  38.     struct block *allocated = _find_free_block(size, &prev);
  39.     if (!allocated) // if need to allocate new data
  40.     {
  41.         allocated = _get_memory(size, prev);
  42.         _mm_print("MALLOC | ALLOCATED");
  43.     }
  44.     else // if found enough free space within free data
  45.     {
  46.         allocated->free = 0;
  47.         memset(allocated->data, 0, size);
  48.  
  49.         _split_block(allocated, size);
  50.         _mm_print("MALLOC | FOUND");
  51.     }
  52.  
  53.     return allocated->data;
  54. }
  55.  
  56. void *mm_realloc(void *ptr, size_t size)
  57. {
  58.     if (!ptr)
  59.         return mm_malloc(size);
  60.     if (!size)
  61.     {
  62.         mm_free(ptr);
  63.         return NULL;
  64.     }
  65.  
  66.     struct block *to_realloc = _GET_METADATA(ptr);
  67.  
  68.     if (to_realloc->size >= size)
  69.     {
  70.         to_realloc->size = size;
  71.         _split_block(to_realloc, size);
  72.         _mm_print("REALLOC | STAY IN SAME");
  73.         return to_realloc->data;
  74.     }
  75.     else
  76.     {
  77.         void *new_mem = mm_malloc(size);
  78.         if (!new_mem)
  79.             return NULL;
  80.         memmove(new_mem, ptr, to_realloc->size);
  81.         mm_free(ptr);
  82.         _mm_print("REALLOC | NEED MALLOC");
  83.         return new_mem;
  84.     }
  85. }
  86.  
  87. void mm_free(void *ptr)
  88. {
  89.     if (!ptr)
  90.         return;
  91.  
  92.     struct block *to_free = _GET_METADATA(ptr);
  93.     if (to_free->free)
  94.         return;
  95.  
  96.     to_free->free = 1;
  97.     _merge_free_blocks(to_free);
  98.  
  99.     _mm_print("FREE");
  100. }
  101.  
  102. void *_get_memory(size_t size, struct block *prev)
  103. {
  104.     struct block *allocated = sbrk(size + METADATA_SIZE);
  105.     if (!allocated)
  106.     {
  107.         perror("malloc");
  108.         return NULL;
  109.     }
  110.  
  111.     memset(allocated, 0, size + METADATA_SIZE);
  112.     allocated->next = NULL;
  113.     allocated->prev = prev;
  114.     if (prev)
  115.         prev->next = allocated;
  116.     allocated->size = size;
  117.     allocated->free = 0;
  118.  
  119.     return allocated;
  120. }
  121.  
  122. void *_find_free_block(size_t size, struct block **prev)
  123. {
  124.     struct block *ptr = head;
  125.     *prev = NULL;
  126.     while (ptr && (!ptr->free || ptr->size < size))
  127.     {
  128.         *prev = ptr;
  129.         ptr = ptr->next;
  130.     }
  131.     if ((*prev) && (*prev)->free)
  132.     {
  133.         sbrk(size - (*prev)->size);
  134.         (*prev)->size = size;
  135.         return (*prev);
  136.     }
  137.     return ptr;
  138. }
  139.  
  140. void _split_block(struct block *block, size_t size)
  141. {
  142.     if (block->size - size > METADATA_SIZE) // NEED TO SPLIT
  143.     {
  144.         struct block *new_block = ((void *)block->data + size);
  145.         int old_size = block->size;
  146.  
  147.         if (block->next)
  148.             block->next->prev = new_block;
  149.         new_block->next = block->next;
  150.  
  151.         block->next = new_block;
  152.         new_block->prev = block;
  153.  
  154.         block->size = size;
  155.         new_block->free = 1;
  156.         new_block->size = old_size - METADATA_SIZE - block->size;
  157.     }
  158. }
  159.  
  160. void _merge_free_blocks(struct block *block)
  161. {
  162.     if (block->next && block->next->free)
  163.     {
  164.         block->size += block->next->size + METADATA_SIZE;
  165.         block->next = block->next->next;
  166.         if (block->next)
  167.             block->next->prev = block;
  168.     }
  169.     if (block->prev && block->prev->free)
  170.     {
  171.         _merge_free_blocks(block->prev);
  172.     }
  173. }
  174.  
  175. void _mm_print(char *s)
  176. {
  177.     if (!DBG)
  178.         return;
  179.     struct block *ptr = head;
  180.     int counter = 0;
  181.  
  182.     printf("\n$$$$$ %s $$$$$\n", s);
  183.     printf("!!! MEMORY !!!\n");
  184.     while (ptr)
  185.     {
  186.         printf("###  %d\n", ++counter);
  187.         printf("Cur        : %p\n", ptr);
  188.         printf("Alloc Size : %ld\n", ptr->size);
  189.         printf("Free       : %d\n", ptr->free);
  190.         printf("Prev       : %p\n", ptr->prev);
  191.         printf("Next       : %p\n", ptr->next);
  192.         ptr = ptr->next;
  193.     }
  194. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement