API tools faq
paste
Advertisement
Guest User

malloclab mm.c

a guest
Dec 4th, 2016
86
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 11.33 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <assert.h>
  5. #include <unistd.h>
  6.  
  7. #include "mm.h"
  8. #include "memlib.h"
  9.  
  10.  
  11. /* single word (4) or double word (8) alignment */
  12. #define ALIGNMENT 16
  13.  
  14. /* rounds up to the nearest multiple of ALIGNMENT */
  15. #define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
  16.  
  17. #define IS_ALIGNED(p)  ((((long)(p)) % ALIGNMENT) == 0)
  18.  
  19. #define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
  20.  
  21.  
  22. /* Basic constants and macros */
  23. #define WSIZE       8       /* Word and header/footer size (bytes) */
  24. #define DSIZE       16       /* Doubleword size (bytes) */
  25. #define CHUNKSIZE  (1<<12)  /* Extend heap by this amount (bytes) */
  26.  
  27. #define LISTLIMIT 20
  28.  
  29. #define MAX(x, y) ((x) > (y)? (x) : (y))  
  30. #define MIN(x, y) ((x) < (y) ? (x) : (y))
  31.  
  32. /* Pack a size and allocated bit into a word */
  33. #define PACK(size, alloc)  ((size) | (alloc))
  34.  
  35. /* Read and write a word at address p */
  36. #define GET(p)       (*(unsigned int *)(p))            
  37. #define PUT(p, val)  (*(unsigned int *)(p) = (val))  
  38.  
  39. /* Read the size and allocated fields from address p */
  40. #define GET_SIZE(p)  (GET(p) & ~0x7)                
  41. #define GET_ALLOC(p) (GET(p) & 0x1)          
  42.  
  43. /* Given block ptr bp, compute address of its header and footer */
  44. #define HDRP(bp)       ((char *)(bp) - WSIZE)                      
  45. #define FTRP(bp)       ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
  46.  
  47. /* Given block ptr bp, compute address of next and previous blocks */
  48. #define NEXT_BLKP(bp)  ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
  49. #define PREV_BLKP(bp)  ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
  50.  
  51. #define NEXT(bp) (*(void **)(bp))
  52. #define PREV(bp) (*(void **)(((char *)(bp) + WSIZE)))
  53.  
  54. #define GET_FREELIST(free_list, i) (*(void **)(free_list + (i*DSIZE)))
  55.  
  56.  
  57. /* Global variables */
  58. static char *free_list = 0;
  59.  
  60. /* Function prototypes for internal helper routines */
  61. static void *extend_heap(size_t size);
  62. static void *coalesce(void *bp);
  63. static void *place(void *bp, size_t asize);
  64. static void insert(void *bp, size_t size);
  65. static void detach(void *bp);
  66. void mm_checkheap(int verbose);
  67.  
  68. /*Extends the heap with a new free block*/
  69. void *extend_heap(size_t words)
  70. {
  71.         void *bp;
  72.         size_t size;
  73.  
  74.         size = ALIGN(words);
  75.         if ((bp = mem_sbrk(size)) == (void *)-1){
  76.                 return NULL;
  77.         }
  78.                                                         // Initialize free block header/footer and the epilogue footer
  79.         PUT(HDRP(bp), PACK(size, 0));
  80.         PUT(FTRP(bp), PACK(size, 0));
  81.         PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
  82.         insert(bp, size);
  83.         return coalesce(bp);
  84. }
  85.  
  86. void insert(void *bp, size_t size) {
  87.         int list = 0;
  88.         void *search_bp = bp;
  89.         void *insert_bp = NULL;
  90.  
  91.         while ((list < LISTLIMIT - 1) && (size > 1)) {
  92.                 size /= 2;
  93.                 list++;
  94.         }
  95.  
  96.         search_bp = GET_FREELIST(free_list,list);
  97.         while ((search_bp != NULL) && (size > GET_SIZE(HDRP(search_bp)))) {
  98.                 insert_bp = search_bp;
  99.                 search_bp = NEXT(search_bp);
  100.         }
  101.  
  102.         if (search_bp != NULL) {
  103.                 if (insert_bp != NULL) {
  104.                         NEXT(bp) = search_bp;
  105.                         PREV(search_bp) =  bp;
  106.                         PREV(bp) = insert_bp;
  107.                         NEXT(insert_bp) = bp;
  108.                 }
  109.  
  110.                 else {
  111.                         NEXT(bp) = search_bp;
  112.                         PREV(search_bp) = bp;
  113.                         PREV(bp) = NULL;
  114.                         GET_FREELIST(free_list,list) = bp;
  115.                 }
  116.         }
  117.         else {
  118.                 if (insert_bp != NULL) {
  119.                         NEXT(bp) = NULL;
  120.                         PREV(bp) = insert_bp;
  121.                         NEXT(insert_bp) = bp;
  122.                 }
  123.                 else {
  124.                         NEXT(bp) = NULL;
  125.                         PREV(bp) = NULL;
  126.                         GET_FREELIST(free_list,list) = bp;
  127.                 }
  128.         }
  129.         return;
  130. }
  131.  
  132. /*detach the node from the free list*/
  133. void detach(void *bp) {
  134.         int list = 0;
  135.         size_t size = GET_SIZE(HDRP(bp));
  136.         while ((list < LISTLIMIT - 1) && (size > 1)) {
  137.                 size /= 2;
  138.                 list++;
  139.         }
  140.  
  141.         if (NEXT(bp) != NULL) {
  142.                 if (PREV(bp) != NULL) {
  143.                         PREV(NEXT(bp)) = PREV(bp);
  144.                         NEXT(PREV(bp)) = NEXT(bp);
  145.                 }
  146.                 else {
  147.                         PREV(NEXT(bp)) = NULL;
  148.                         GET_FREELIST(free_list,list) = NEXT(bp);
  149.                 }
  150.         }
  151.         else {
  152.                 if (PREV(bp) != NULL) {
  153.                         NEXT(PREV(bp)) = NULL;
  154.                 }
  155.                 else {
  156.                         GET_FREELIST(free_list,list) = NULL;
  157.                 }
  158.         }
  159.         return;
  160. }
  161.  
  162. void *coalesce(void *bp)
  163. {
  164.         size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
  165.         size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
  166.         size_t size = GET_SIZE(HDRP(bp));
  167.  
  168.         if (prev_alloc && next_alloc) {
  169.                 return bp;
  170.         }
  171.  
  172.         else if (prev_alloc && !next_alloc) {
  173.                 detach(bp);
  174.                 detach(NEXT_BLKP(bp));
  175.                 size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
  176.                 PUT(HDRP(bp), PACK(size, 0));
  177.                 PUT(FTRP(bp), PACK(size, 0));
  178.         }
  179.  
  180.         else if (!prev_alloc && next_alloc) {
  181.                 detach(bp);
  182.                 detach(PREV_BLKP(bp));
  183.                 size += GET_SIZE(HDRP(PREV_BLKP(bp)));
  184.                 PUT(FTRP(bp), PACK(size, 0));
  185.                 PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
  186.                 bp = PREV_BLKP(bp);
  187.         }
  188.         else {
  189.                 detach(bp);
  190.                 detach(PREV_BLKP(bp));
  191.                 detach(NEXT_BLKP(bp));
  192.                 size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(HDRP(NEXT_BLKP(bp)));
  193.                 PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
  194.                 PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
  195.                 bp = PREV_BLKP(bp);
  196.         }
  197.         insert(bp, size);
  198.         return bp;
  199. }
  200.  
  201. /*place the block to its position*/
  202. void *place(void *bp, size_t asize)
  203. {
  204.         size_t csize = GET_SIZE(HDRP(bp));
  205.         size_t remainder = csize - asize;
  206.         detach(bp);
  207.  
  208.         if (remainder <= DSIZE * 2) {
  209.                 PUT(HDRP(bp), PACK(csize, 1));
  210.                 PUT(FTRP(bp), PACK(csize, 1));
  211.         }
  212.  
  213.         else if (asize >= 112) {
  214.                 PUT(HDRP(bp), PACK(remainder, 0));
  215.                 PUT(FTRP(bp), PACK(remainder, 0));
  216.                 PUT(HDRP(NEXT_BLKP(bp)), PACK(asize, 1));
  217.                 PUT(FTRP(NEXT_BLKP(bp)), PACK(asize, 1));
  218.                 insert(bp, remainder);
  219.                 return NEXT_BLKP(bp);
  220.         }
  221.         else {
  222.                 PUT(HDRP(bp), PACK(asize, 1));
  223.                 PUT(FTRP(bp), PACK(asize, 1));
  224.                 PUT(HDRP(NEXT_BLKP(bp)), PACK(remainder, 0));
  225.                 PUT(FTRP(NEXT_BLKP(bp)), PACK(remainder, 0));
  226.                 insert(NEXT_BLKP(bp), remainder);
  227.         }
  228.         return bp;
  229. }
  230.  
  231. /*
  232.  * mm_init - initialize the malloc package.
  233.  */
  234. int mm_init(void)
  235. {
  236.         char *heap_listp;
  237.         free_list = NULL;
  238.  
  239.         free_list = mem_sbrk(LISTLIMIT * DSIZE);
  240.         for (int i = 0; i < LISTLIMIT ; ++i){
  241.                 GET_FREELIST(free_list,i) = NULL;
  242.         }
  243.  
  244.         if ((long)(heap_listp = mem_sbrk(4 * WSIZE)) == -1){
  245.                 return -1;
  246.         }
  247.         PUT(heap_listp, 0);                                     /* Alignment padding */
  248.         PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));          /* Prologue header */
  249.         PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));          /* Prologue footer */
  250.         PUT(heap_listp + (4 * WSIZE), PACK(0, 1));              /* Epilogue header */
  251.  
  252.         if(extend_heap(CHUNKSIZE) == NULL){
  253.                 return -1;
  254.         }
  255.         return 0;
  256. }
  257. /*
  258.  * mm_malloc - Allocate a block by incrementing the brk pointer.
  259.  *     Always allocate a block whose size is a multiple of the alignment.
  260.  */
  261. void *mm_malloc(size_t size)
  262. {
  263.         size_t asize;           /* Adjusted block size */
  264.         size_t extendsize;      /* Amount to extend heap if no fit */
  265.         void *bp = NULL;
  266.  
  267.         if (size == 0)
  268.                 return NULL;
  269.  
  270.         if (size <= DSIZE)
  271.                 asize = 2 * DSIZE;
  272.         else
  273.                 asize = ALIGN(size+DSIZE);
  274.  
  275.  
  276.         int list = 0;
  277.         size_t searchsize = asize;
  278.  
  279.         while (list < LISTLIMIT) {
  280.                 if ((list == LISTLIMIT - 1) || ((searchsize <= 1) && (GET_FREELIST(free_list,list) != NULL))) {
  281.                         bp = GET_FREELIST(free_list,list);
  282.  
  283.                         while ((bp != NULL) && ((asize > GET_SIZE(HDRP(bp))))){
  284.                                 bp = NEXT(bp);
  285.                         }
  286.                         if (bp != NULL){
  287.                                 break;
  288.                         }
  289.                 }
  290.                 searchsize /= 2;
  291.                 list++;
  292.         }
  293.  
  294.         if (bp == NULL) {
  295.                 extendsize = MAX(asize, CHUNKSIZE);
  296.                 if ((bp = extend_heap(extendsize)) == NULL)
  297.                         return NULL;
  298.         }
  299.         bp = place(bp, asize);
  300.         return bp;
  301. }
  302.  
  303. /*
  304.  * mm_free - Freeing a block does nothing.
  305.  */
  306. void mm_free(void *bp)
  307. {
  308.         size_t size = GET_SIZE(HDRP(bp));
  309.         PUT(HDRP(bp), PACK(size, 0));
  310.         PUT(FTRP(bp), PACK(size, 0));
  311.         insert(bp, size);
  312.         coalesce(bp);
  313. }
  314.  
  315. /*
  316.  * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
  317.  */
  318. void *mm_realloc(void *bp, size_t size)
  319. {
  320.         void *new_bp = bp;
  321.         size_t new_size = size;
  322.         int remainder;
  323.         int extendsize;
  324.  
  325.         if (size == 0){
  326.                 return NULL;
  327.         }
  328.  
  329.         if (new_size <= DSIZE) {
  330.                 new_size = 2 * DSIZE;
  331.         }
  332.         else {
  333.                 new_size = ALIGN(size+DSIZE);
  334.         }
  335.  
  336.         if (!GET_ALLOC(HDRP(NEXT_BLKP(bp))) || !GET_SIZE(HDRP(NEXT_BLKP(bp)))) {
  337.                 remainder = GET_SIZE(HDRP(bp)) + GET_SIZE(HDRP(NEXT_BLKP(bp))) - new_size;
  338.  
  339.                 if (remainder < 0) {
  340.                         extendsize = MAX(-remainder, CHUNKSIZE);
  341.                         if (extend_heap(extendsize) == NULL){
  342.                                 return NULL;
  343.                         }
  344.                         remainder += extendsize;
  345.                 }
  346.                 detach(NEXT_BLKP(bp));
  347.                 PUT(HDRP(bp), PACK(new_size + remainder, 1));
  348.                 PUT(FTRP(bp), PACK(new_size + remainder, 1));
  349.  
  350.         }
  351.         else {
  352.                 new_bp = mm_malloc(new_size - DSIZE);
  353.                 memcpy(new_bp, bp, MIN(size, new_size));
  354.                 mm_free(bp);
  355.         }
  356.         return new_bp;
  357. }
  358.  
  359. /* check for errors */
  360. void mm_checkheap(int verbose){
  361.         for (int i = 0; i < LISTLIMIT-1; i++){
  362.                 void* bp = GET_FREELIST(free_list,i);
  363.                 while (bp != NULL){
  364.                         if(GET_ALLOC(bp) == 1){
  365.                                 printf("You have an allocated block in the free list");
  366.                         }
  367.                         bp = NEXT(bp);
  368.                 }
  369.         }
  370. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!