API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Dec 13th, 2018
69
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.87 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. * mm-implicit.c - Simple allocator based on implicit free lists,
  3. * first fit placement, and boundary tag coalescing.
  4. * (64-bit version)
  5. */
  6. #include <stdio.h>
  7. #include <string.h>
  8. #include <stdlib.h>
  9. #include <unistd.h>
  10.  
  11. #include "mm.h"
  12. #include "memlib.h"
  13.  
  14. /*
  15. * If NEXT_FIT defined use next fit search, else use first fit search
  16. */
  17. #define NEXT_FIT
  18.  
  19. /* $begin mallocmacros */
  20. /* Basic constants and macros */
  21. #define WSIZE 8 /* word size (bytes) */
  22. #define DSIZE 16 /* doubleword size (bytes) */
  23. #define CHUNKSIZE (1<<12) /* initial heap size (bytes) */
  24. #define OVERHEAD 16 /* overhead of header and footer (bytes) */
  25.  
  26. #define MAX(x, y) ((x) > (y)? (x) : (y))
  27.  
  28. /* Pack a size and allocated bit into a word */
  29. #define PACK(size, alloc) ((size) | (alloc))
  30.  
  31. /* Read and write a word at address p */
  32. /* NB: this code calls a 32-bit quantity a word */
  33. #define GET(p) (*(unsigned int *)(p))
  34. #define PUT(p, val) (*(unsigned int *)(p) = (val))
  35.  
  36. /* Read the size and allocated fields from address p */
  37. #define GET_SIZE(p) (GET(p) & ~0x7)
  38. #define GET_ALLOC(p) (GET(p) & 0x1)
  39.  
  40. /* Given block ptr bp, compute address of its header and footer */
  41. #define HDRP(bp) ((char *)(bp) - WSIZE)
  42. #define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
  43.  
  44. /* Given block ptr bp, compute address of next and previous blocks */
  45. #define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
  46. #define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
  47.  
  48. #define NEXT_BP(bp) (*(char**)(bp + WSIZE))
  49. #define PREV_BP(bp) (*(char**)bp)
  50. /* $end mallocmacros */
  51.  
  52. /* Global variables */
  53. static char *heap_listp = 0; /* pointer to first block */
  54. static char *free_listp = NULL;
  55. static int WSHIFT = 3;
  56. static int DSHIFT = 4;
  57.  
  58. /* function prototypes for internal helper routines */
  59. static void *extend_heap(size_t words);
  60. static void place(void *bp, size_t asize);
  61. static void *find_fit(size_t asize);
  62. static void *coalesce(void *bp);
  63. static void printblock(void *bp);
  64. static void checkblock(void *bp);
  65. static void addit(void *bp);
  66. static void removeit(void *bp);
  67.  
  68. /*
  69. * mm_init - Initialize the memory manager
  70. */
  71. /* $begin mminit */
  72. int mm_init(void)
  73. {
  74. heap_listp = 0;
  75. free_listp = 0;
  76. /* create the initial empty heap */
  77. if ((heap_listp = mem_sbrk(WSIZE<<WSHIFT)) == NULL)
  78. return -1;
  79. PUT(heap_listp, 0); /* alignment padding */
  80. PUT(heap_listp+WSIZE, PACK(OVERHEAD, 1)); /* prologue header */
  81. PUT(heap_listp+DSIZE, PACK(OVERHEAD, 1)); /* prologue footer */
  82. PUT(heap_listp+WSIZE+DSIZE, PACK(0, 1)); /* epilogue header */
  83. //heap_listp += DSIZE;
  84. free_listp = heap_listp + DSIZE;
  85.  
  86. /* Extend the empty heap with a free block of CHUNKSIZE bytes */
  87. if (extend_heap(CHUNKSIZE>>WSHIFT) == NULL)
  88. return -1;
  89. return 0;
  90. }
  91. /* $end mminit */
  92.  
  93. /*
  94. * malloc - Allocate a block with at least size bytes of payload
  95. */
  96. /* $begin mmmalloc */
  97. void *mm_malloc(size_t size)
  98. {
  99. size_t asize; /* adjusted block size */
  100. size_t extendsize; /* amount to extend heap if no fit */
  101. char *bp;
  102. if (heap_listp == 0){
  103. mm_init();
  104. }
  105.  
  106. /* Ignore spurious requests */
  107. if (size <= 0)
  108. return NULL;
  109.  
  110. /* Adjust block size to include overhead and alignment reqs. */
  111. if (size <= DSIZE)
  112. asize = DSIZE + OVERHEAD;
  113. else
  114. asize = (((size+(OVERHEAD)+(DSIZE-1))>>DSHIFT)<<DSHIFT);
  115.  
  116. /* Search the free list for a fit */
  117. if ((bp = find_fit(asize)) != NULL) {
  118. place(bp, asize);
  119. return bp;
  120. }
  121.  
  122. /* No fit found. Get more memory and place the block */
  123. extendsize = MAX(asize,CHUNKSIZE);
  124. if ((bp = extend_heap(extendsize>>WSHIFT)) == NULL)
  125. return NULL;
  126. place(bp, asize);
  127. return bp;
  128. }
  129. /* $end mmmalloc */
  130.  
  131. /*
  132. * free - Free a block
  133. */
  134. /* $begin mmfree */
  135. void mm_free(void *bp)
  136. {
  137. if(bp == 0) return;
  138.  
  139. size_t size = GET_SIZE(HDRP(bp));
  140. if (heap_listp == 0){
  141. mm_init();
  142. }
  143.  
  144. PUT(HDRP(bp), PACK(size, 0));
  145. PUT(FTRP(bp), PACK(size, 0));
  146. coalesce(bp); // do we need this ???
  147. //mm_checkheap(0);
  148. }
  149.  
  150. /* $end mmfree */
  151.  
  152. static void addit(void *bp){
  153. NEXT_BP(bp) = free_listp;
  154. PREV_BP(free_listp) = bp;
  155. PREV_BP(bp) = NULL;
  156. free_listp = bp;
  157. }
  158.  
  159. static void removeit(void *bp){
  160. int not_prev_bool =! (PREV_BP(bp));
  161. char *next_bp = NEXT_BP(bp);
  162. char *prev_bp = PREV_BP(bp);
  163. if (not_prev_bool) {
  164. free_listp = next_bp;
  165. } else {
  166. NEXT_BP(PREV_BP(bp)) = next_bp;
  167. }
  168. PREV_BP(NEXT_BP(bp)) = prev_bp;
  169. }
  170.  
  171. /*
  172. * realloc - naive implementation of realloc
  173. */
  174. void *mm_realloc(void *ptr, size_t size)
  175. {
  176. size_t oldsize;
  177. void *newptr;
  178.  
  179. /* If size == 0 then this is just free, and we return NULL. */
  180. if(size == 0) {
  181. mm_free(ptr);
  182. return 0;
  183. }
  184.  
  185. /* If oldptr is NULL, then this is just malloc. */
  186. if(ptr == NULL) {
  187. return mm_malloc(size);
  188. }
  189.  
  190. newptr = mm_malloc(size);
  191.  
  192. /* If realloc() fails the original block is left untouched */
  193. if(!newptr) {
  194. return 0;
  195. }
  196.  
  197. /* Copy the old data. */
  198. oldsize = GET_SIZE(HDRP(ptr));
  199. if(size < oldsize) oldsize = size;
  200. memcpy(newptr, ptr, oldsize);
  201.  
  202. /* Free the old block. */
  203. mm_free(ptr);
  204.  
  205. return newptr;
  206. }
  207.  
  208. /*
  209. * checkheap - Minimal check of the heap for consistency
  210. */
  211. void mm_checkheap(int verbose)
  212. {
  213. char *bp = heap_listp;
  214.  
  215. if (verbose)
  216. printf("Heap (%p):\n", heap_listp);
  217.  
  218. if ((GET_SIZE(HDRP(heap_listp)) != DSIZE) || !GET_ALLOC(HDRP(heap_listp)))
  219. printf("Bad prologue header\n");
  220. checkblock(heap_listp);
  221.  
  222. for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
  223. if (verbose)
  224. printblock(bp);
  225. checkblock(bp);
  226. }
  227.  
  228. if (verbose)
  229. printblock(bp);
  230. if ((GET_SIZE(HDRP(bp)) != 0) || !(GET_ALLOC(HDRP(bp))))
  231. printf("Bad epilogue header\n");
  232. }
  233.  
  234. /* The remaining routines are internal helper routines */
  235.  
  236. /*
  237. * extend_heap - Extend heap with free block and return its block pointer
  238. */
  239. /* $begin mmextendheap */
  240. static void *extend_heap(size_t words)
  241. {
  242. char *bp;
  243. size_t size;
  244. void *return_ptr;
  245.  
  246. /* Allocate an even number of words to maintain alignment */
  247. size = (words % 2) ? ((words+1)<<WSHIFT) : (words<<WSHIFT);
  248. if ((long)(bp = mem_sbrk(size)) < 0)
  249. return NULL;
  250.  
  251. /* Initialize free block header/footer and the epilogue header */
  252. PUT(HDRP(bp), PACK(size, 0)); /* free block header */
  253. PUT(FTRP(bp), PACK(size, 0)); /* free block footer */
  254. PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* new epilogue header */
  255.  
  256. /* Coalesce if the previous block was free */
  257. return_ptr = coalesce(bp);
  258. //mm_checkheap(0);
  259. return return_ptr;
  260. }
  261. /* $end mmextendheap */
  262.  
  263. /*
  264. * place - Place block of asize bytes at start of free block bp
  265. * and split if remainder would be at least minimum block size
  266. */
  267. /* $begin mmplace */
  268. /* $begin mmplace-proto */
  269. static void place(void *bp, size_t asize)
  270. /* $end mmplace-proto */
  271. {
  272. size_t csize = GET_SIZE(HDRP(bp));
  273.  
  274. if ((csize - asize) >= (DSIZE + OVERHEAD)) {
  275. PUT(HDRP(bp), PACK(asize, 1));
  276. PUT(FTRP(bp), PACK(asize, 1));
  277. removeit(bp);
  278. bp = NEXT_BLKP(bp);
  279. PUT(HDRP(bp), PACK(csize-asize, 0));
  280. PUT(FTRP(bp), PACK(csize-asize, 0));
  281. addit(bp);
  282. //coalesce(bp);
  283. }
  284. else {
  285. PUT(HDRP(bp), PACK(csize, 1));
  286. PUT(FTRP(bp), PACK(csize, 1));
  287. removeit(bp);
  288. }
  289. }
  290. /* $end mmplace */
  291.  
  292. /*
  293. * find_fit - Find a fit for a block with asize bytes
  294. */
  295. static void *find_fit(size_t asize)
  296. {
  297. /* first fit search */
  298. void *bp;
  299. for (bp = free_listp; GET_ALLOC(HDRP(bp)) == 0 && GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BP(bp)) {
  300. if (asize <= (size_t) GET_SIZE(HDRP(bp))) {
  301. return bp;
  302. }
  303. }
  304. return NULL; /* no fit */
  305. }
  306.  
  307. /*
  308. * coalesce - boundary tag coalescing. Return ptr to coalesced block
  309. */
  310. static void *coalesce(void *bp)
  311. {
  312. size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
  313. size_t prev_none = PREV_BLKP(bp) == bp;
  314. prev_alloc = prev_alloc | prev_none;
  315. size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
  316. size_t size = GET_SIZE(HDRP(bp));
  317.  
  318. if (prev_alloc && next_alloc) { /* Case 1 */
  319. addit(bp);
  320. return bp;
  321. }
  322.  
  323. else if (prev_alloc && !next_alloc) { /* Case 2 */
  324. size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
  325. removeit(NEXT_BLKP(bp));
  326. PUT(HDRP(bp), PACK(size, 0));
  327. PUT(FTRP(bp), PACK(size,0));
  328. addit(bp);
  329. }
  330.  
  331. else if (!prev_alloc && next_alloc) { /* Case 3 */
  332. size += GET_SIZE(HDRP(PREV_BLKP(bp)));
  333. removeit(PREV_BLKP(bp));
  334. PUT(FTRP(bp), PACK(size, 0));
  335. PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
  336. addit(PREV_BLKP(bp));
  337. bp = PREV_BLKP(bp);
  338. }
  339.  
  340. else { /* Case 4 */
  341. size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
  342. GET_SIZE(FTRP(NEXT_BLKP(bp)));
  343. removeit(PREV_BLKP(bp));
  344. removeit(NEXT_BLKP(bp));
  345. PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
  346. PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
  347. addit(PREV_BLKP(bp));
  348. bp = PREV_BLKP(bp);
  349. }
  350.  
  351. return bp;
  352. }
  353.  
  354.  
  355. static void printblock(void *bp)
  356. {
  357. size_t hsize;//, halloc, fsize, falloc;
  358.  
  359. hsize = GET_SIZE(HDRP(bp));
  360. //halloc = GET_ALLOC(HDRP(bp));
  361. //fsize = GET_SIZE(FTRP(bp));
  362. //falloc = GET_ALLOC(FTRP(bp));
  363.  
  364. if (hsize == 0) {
  365. printf("%p: EOL\n", bp);
  366. return;
  367. }
  368.  
  369. /* printf("%p: header: [%p:%c] footer: [%p:%c]\n", bp,
  370. hsize, (halloc ? 'a' : 'f'),
  371. fsize, (falloc ? 'a' : 'f')); */
  372. }
  373.  
  374. static void checkblock(void *bp)
  375. {
  376. if ((size_t)bp % 8)
  377. printf("Error: %p is not doubleword aligned\n", bp);
  378. if (GET(HDRP(bp)) != GET(FTRP(bp)))
  379. printf("Error: header does not match footer\n");
  380. }
  381.  
  382. // from mm-naive.c
  383. void *mm_calloc (size_t nmemb, size_t size)
  384. {
  385. size_t bytes = nmemb * size;
  386. void *newptr;
  387.  
  388. newptr = mm_malloc(bytes);
  389. memset(newptr, 0, bytes);
  390.  
  391. return newptr;
  392. }
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!