You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
533 lines
14 KiB
533 lines
14 KiB
/*
|
|
* mm-naive.c - The clear list(LIFO), best fit, coalesce immediately malloc package.
|
|
*/
|
|
#include <string.h>
|
|
|
|
#include "mm.h"
|
|
#include "memlib.h"
|
|
|
|
team_t team = {
|
|
/* Team name */
|
|
"team",
|
|
/* First member's full name */
|
|
"GentleCold",
|
|
/* First member's email address */
|
|
"1952173800@qq.com",
|
|
/* Second member's full name (leave blank if none) */
|
|
"",
|
|
/* Second member's email address (leave blank if none) */
|
|
""
|
|
};
|
|
|
|
/* single size_t (4) or double size_t (8) alignment */
|
|
#define ALIGNMENT 8
|
|
/* rounds up to the nearest multiple of ALIGNMENT */
|
|
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)
|
|
|
|
// My define
|
|
#define WSIZE 4
|
|
#define DSIZE 8
|
|
#define FSIZE 16
|
|
#define ADDRESS (sizeof(size_t))
|
|
#define CHUNK 1 << 12
|
|
#define MIN_BLOCK (2 * ADDRESS + DSIZE)
|
|
|
|
#define MAX(a, b) ((a) > (b) ? (a) : (b))
|
|
|
|
#define PARSE(v) ((v) & ~0x7)
|
|
#define PACK(v, a) ((v) | (a))
|
|
|
|
#define HEAD(bp) ((byte *)(bp) - WSIZE)
|
|
#define FOOT(bp) ((byte *)(bp) + SIZE(bp))
|
|
#define SIZE(bp) (PARSE(GET(HEAD(bp))))
|
|
#define ALLOC(bp) (GET(HEAD(bp)) & 0x1)
|
|
|
|
#define GET(p) (*(word *)(p))
|
|
#define SET(p, v) (*(word *)(p) = (v))
|
|
|
|
#define NEXT(bp) (FOOT(bp) + DSIZE)
|
|
#define PREV(bp) ((byte *)(bp) - PARSE(GET((bp) - DSIZE)) - DSIZE)
|
|
|
|
#define POS_PRED(bp) ((byte *)(bp))
|
|
#define POS_SUCC(bp) (((byte *)(bp) + ADDRESS))
|
|
#define GET_PRED(bp) (*(size_t *)POS_PRED(bp))
|
|
#define GET_SUCC(bp) (*(size_t *)POS_SUCC(bp))
|
|
|
|
typedef unsigned int word;
|
|
typedef char byte;
|
|
|
|
// mark the front and tail pos
|
|
void *front_p = NULL;
|
|
void *tail_p = NULL;
|
|
|
|
/**
|
|
* used for next fit, updated by mm_init, mm_malloc, _coalesce
|
|
* @deprecated useless for clear list
|
|
*/
|
|
void *fitted_p = NULL;
|
|
void *list_p = NULL;
|
|
|
|
// My func
|
|
/**
|
|
* add a blank chunk and coalesce
|
|
* will update tail_p
|
|
* @param size align by 8, excluding head and foot
|
|
* @return new bp
|
|
*/
|
|
static void *_extend(size_t size);
|
|
|
|
/**
|
|
* coalesce blank chunk before and after bp
|
|
* @param bp loaded point
|
|
* @return bp after coalesce
|
|
*/
|
|
static void *_coalesce(void *bp);
|
|
static void *__coalesce_prev(void *bp);
|
|
static void *__coalesce_next(void *bp);
|
|
static void *__coalesce_all(void *bp);
|
|
static void *__coalesce_none(void *bp);
|
|
|
|
/**
|
|
* traverse and find first fit, then place in
|
|
* @deprecated too slow
|
|
* @param size align by 8, excluding head and foot
|
|
* @return
|
|
*/
|
|
static void *_first_fit(size_t size);
|
|
|
|
/**
|
|
* find next fit, then place in
|
|
* @deprecated I'll use clear list
|
|
* @param size align by 8, excluding head and foot
|
|
* @return
|
|
*/
|
|
static void *_next_fit(size_t size);
|
|
|
|
/**
|
|
* find next fit, then place in, if from beginning, use best fit
|
|
* @deprecated thru loss
|
|
* @param size align by 8, excluding head and foot
|
|
* @return
|
|
*/
|
|
static void *_next_best_fit(size_t size);
|
|
|
|
/**
|
|
* traverse blank block only and find first fit, then place in
|
|
* @deprecated for the memory loss
|
|
* @param size align by 8, excluding head and foot
|
|
* @return
|
|
*/
|
|
static void *_first_fit_of_clear(size_t size);
|
|
|
|
/**
|
|
* best fit for clear list
|
|
* @param size align by 8, excluding head and foot
|
|
* @return
|
|
*/
|
|
static void *_best_fit_of_clear(size_t size);
|
|
|
|
/**
|
|
* allocate the block and cut sometimes
|
|
* @param size align by 8, excluding head and foot
|
|
*/
|
|
static void _place(void *ptr, size_t size);
|
|
|
|
/**
|
|
* just replace in of out in list
|
|
* @param in the block that in the list
|
|
* @param out the block that out the list
|
|
*/
|
|
static void _fix_list(void *in, void *out);
|
|
|
|
/**
|
|
* check the number of blank list nums and real blank nums and print
|
|
* @deprecated
|
|
*/
|
|
static void _check();
|
|
// end
|
|
|
|
/**
|
|
* initialize the malloc package.
|
|
* get a new chunk, set front_p and tail_p
|
|
*/
|
|
int mm_init(void) {
|
|
if ((front_p = mem_sbrk(WSIZE)) == (void *) - 1) return -1; // blank
|
|
front_p += DSIZE; // first chunk
|
|
// fitted_p = front_p; // init fitted_p
|
|
if (!_extend(CHUNK)) return -1;
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* find first fit or extend
|
|
*/
|
|
void *mm_malloc(size_t size) {
|
|
size_t adjust_size = ALIGN(size);
|
|
size_t extend_size;
|
|
void *bp;
|
|
if ((bp = _best_fit_of_clear(adjust_size)) != NULL) {
|
|
// fitted_p = bp;
|
|
return bp;
|
|
} else {
|
|
extend_size = adjust_size;
|
|
if (!ALLOC(tail_p)) {
|
|
extend_size -= (SIZE(tail_p) + DSIZE);
|
|
}
|
|
bp = _extend(MAX(extend_size, CHUNK));
|
|
if (bp == NULL) return bp;
|
|
_place(bp, adjust_size);
|
|
// fitted_p = bp;
|
|
return bp;
|
|
}
|
|
}
|
|
|
|
/**
|
|
* free a block and coalesce immediately
|
|
*/
|
|
void mm_free(void *ptr) {
|
|
#ifdef DEBUG
|
|
printf("---free---\n");
|
|
_check();
|
|
printf("----------\n");
|
|
#endif
|
|
size_t size = SIZE(ptr);
|
|
SET(HEAD(ptr), PACK(size, 0));
|
|
SET(FOOT(ptr), PACK(size, 0));
|
|
_coalesce(ptr);
|
|
}
|
|
|
|
/**
|
|
* implemented simply in terms of mm_malloc and mm_free
|
|
* compare adjust_size and total_size step by step
|
|
*/
|
|
void *mm_realloc(void *ptr, size_t size) {
|
|
if (ptr == NULL) return mm_malloc(size);
|
|
if (size == 0) return NULL;
|
|
|
|
void *new_ptr;
|
|
size_t adjust_size = ALIGN(size);
|
|
size_t old_size = SIZE(ptr);
|
|
if (adjust_size <= old_size) {
|
|
// just return, for the memory lost is little
|
|
return ptr;
|
|
}
|
|
size_t next_size = (ptr != tail_p && !ALLOC(NEXT(ptr))) ? SIZE(NEXT(ptr)) + DSIZE : 0;
|
|
size_t total_size = old_size + next_size;
|
|
if (adjust_size <= total_size) {
|
|
void *next = NEXT(ptr);
|
|
// remove
|
|
if (total_size - adjust_size >= MIN_BLOCK) {
|
|
SET(POS_SUCC(GET_PRED(next)), GET_SUCC(next));
|
|
SET(POS_PRED(GET_SUCC(next)), GET_PRED(next));
|
|
SET(HEAD(ptr), PACK(total_size, 1));
|
|
SET(FOOT(ptr), PACK(total_size, 1));
|
|
if (next == list_p) {
|
|
if (GET_SUCC(next) == (size_t) next) list_p = NULL;
|
|
else list_p = (void *) GET_SUCC(next);
|
|
}
|
|
if (next == tail_p) tail_p = ptr;
|
|
} else { // replace
|
|
void *pred = (void *)GET_PRED(next);
|
|
void *succ = (void *) GET_SUCC(next);
|
|
SET(HEAD(ptr), PACK(adjust_size, 1));
|
|
SET(FOOT(ptr), PACK(adjust_size, 1));
|
|
size_t new_size = total_size - adjust_size - DSIZE;
|
|
void *new = NEXT(ptr);
|
|
SET(HEAD(new), PACK(new_size, 0));
|
|
SET(FOOT(new), PACK(new_size, 0));
|
|
if (pred == next) {
|
|
SET(POS_PRED(new), (size_t)new);
|
|
SET(POS_SUCC(new), (size_t)new);
|
|
} else {
|
|
SET(POS_PRED(succ), (size_t)new);
|
|
SET(POS_SUCC(pred), (size_t)new);
|
|
}
|
|
if (list_p == next) list_p = new;
|
|
if (next == tail_p) tail_p = new;
|
|
}
|
|
return ptr;
|
|
} else {
|
|
if ((new_ptr = mm_malloc(size)) == NULL) return NULL;
|
|
memmove(new_ptr, ptr, old_size);
|
|
mm_free(ptr);
|
|
return new_ptr;
|
|
}
|
|
}
|
|
|
|
// my func
|
|
static void *_extend(size_t size) {
|
|
void *bp;
|
|
if ((bp = mem_sbrk(size + DSIZE)) == (void *) - 1) return NULL;
|
|
// init chunk
|
|
SET(bp, PACK(size, 0));
|
|
bp += WSIZE;
|
|
SET(FOOT(bp), PACK(size, 0));
|
|
#ifdef DEBUG
|
|
if (tail_p) {
|
|
printf("----extend----\n");
|
|
_check();
|
|
printf("--------------\n");
|
|
}
|
|
#endif
|
|
// init mark point
|
|
tail_p = bp;
|
|
return _coalesce(bp);
|
|
}
|
|
|
|
static void *_coalesce(void *bp) {
|
|
// one chunk
|
|
if (bp == front_p && bp == tail_p) return __coalesce_none(bp);
|
|
if (bp == front_p || ALLOC(PREV(bp))) {
|
|
if (bp == tail_p || ALLOC(NEXT(bp))) return __coalesce_none(bp);
|
|
return __coalesce_next(bp);
|
|
} else if (bp == tail_p || ALLOC(NEXT(bp))) {
|
|
return __coalesce_prev(bp);
|
|
} else {
|
|
return __coalesce_all(bp);
|
|
}
|
|
}
|
|
|
|
static void *__coalesce_prev(void *bp) {
|
|
void *prev = PREV(bp);
|
|
size_t new_size = SIZE(prev) + SIZE(bp) + DSIZE;
|
|
SET(HEAD(prev), PACK(new_size, 0));
|
|
SET(FOOT(bp), PACK(new_size, 0));
|
|
if (bp == tail_p) tail_p = prev;
|
|
// if (bp == fitted_p) fitted_p = prev;
|
|
list_p = prev;
|
|
return prev;
|
|
}
|
|
|
|
static void *__coalesce_next(void *bp) {
|
|
void *next = NEXT(bp);
|
|
// tweak list
|
|
_fix_list(next, bp);
|
|
// coalesce
|
|
size_t new_size = SIZE(next) + SIZE(bp) + DSIZE;
|
|
SET(HEAD(bp), PACK(new_size, 0));
|
|
SET(FOOT(next), PACK(new_size, 0));
|
|
if (next == tail_p) tail_p = bp; // should also change
|
|
// if (next == fitted_p) fitted_p = bp;
|
|
list_p = bp;
|
|
|
|
#ifdef DEBUG
|
|
printf("----coalesce next----\n");
|
|
_check();
|
|
printf("---------------------\n");
|
|
#endif
|
|
return bp;
|
|
}
|
|
|
|
static void *__coalesce_all(void *bp) {
|
|
void *prev = PREV(bp);
|
|
void *next = NEXT(bp);
|
|
// tweak list
|
|
SET(POS_SUCC(GET_PRED(next)), GET_SUCC(next));
|
|
SET(POS_PRED(GET_SUCC(next)), GET_PRED(next));
|
|
// coalesce
|
|
size_t new_size = SIZE(prev) + SIZE(bp) + SIZE(next) + FSIZE;
|
|
SET(HEAD(prev), PACK(new_size, 0));
|
|
SET(FOOT(next), PACK(new_size, 0));
|
|
if (next == tail_p) tail_p = prev;
|
|
// if (next == fitted_p || bp == fitted_p) fitted_p = prev;
|
|
list_p = prev;
|
|
#ifdef DEBUG
|
|
printf("---coalesce all---\n");
|
|
_check();
|
|
printf("-------------------\n");
|
|
#endif
|
|
return prev;
|
|
}
|
|
|
|
static void *__coalesce_none(void *bp) {
|
|
// tweak list
|
|
if (list_p == NULL) {
|
|
list_p = bp;
|
|
SET(POS_SUCC(list_p), (size_t)list_p);
|
|
SET(POS_PRED(list_p), (size_t)list_p);
|
|
} else {
|
|
// add to list
|
|
SET(POS_SUCC(bp), GET_SUCC(list_p));
|
|
SET(POS_PRED(bp), (size_t)list_p);
|
|
SET(POS_PRED(GET_SUCC(list_p)), (size_t)bp);
|
|
SET(POS_SUCC(list_p), (size_t)bp);
|
|
list_p = bp;
|
|
}
|
|
#ifdef DEBUG
|
|
printf("---coalesce none---\n");
|
|
_check();
|
|
printf("-------------------\n");
|
|
#endif
|
|
return bp;
|
|
}
|
|
|
|
static void *_first_fit(size_t size) {
|
|
void *bp = front_p;
|
|
void *after_p = NEXT(tail_p);
|
|
while (bp != after_p) {
|
|
if (!ALLOC(bp) && SIZE(bp) >= size) {
|
|
_place(bp, size);
|
|
return bp;
|
|
}
|
|
bp = NEXT(bp);
|
|
}
|
|
return NULL;
|
|
}
|
|
|
|
static void *_next_fit(size_t size) {
|
|
void *bp = fitted_p;
|
|
void *after_p = NEXT(tail_p);
|
|
while (bp != after_p) {
|
|
if (!ALLOC(bp) && SIZE(bp) >= size) {
|
|
_place(bp, size);
|
|
return bp;
|
|
}
|
|
bp = NEXT(bp);
|
|
}
|
|
bp = front_p;
|
|
while (bp != fitted_p) {
|
|
if (!ALLOC(bp) && SIZE(bp) >= size) {
|
|
_place(bp, size);
|
|
return bp;
|
|
}
|
|
bp = NEXT(bp);
|
|
}
|
|
return NULL;
|
|
}
|
|
|
|
static void *_next_best_fit(size_t size) {
|
|
void *bp = fitted_p;
|
|
void *after_p = NEXT(tail_p);
|
|
while (bp != after_p) {
|
|
if (!ALLOC(bp) && SIZE(bp) >= size) {
|
|
_place(bp, size);
|
|
return bp;
|
|
}
|
|
bp = NEXT(bp);
|
|
}
|
|
bp = front_p;
|
|
size_t min = 0;
|
|
void *min_p = NULL;
|
|
while (bp != fitted_p) {
|
|
if (!ALLOC(bp) && SIZE(bp) >= size) {
|
|
if (min_p == NULL || SIZE(bp) < min) {
|
|
min = SIZE(bp);
|
|
min_p = bp;
|
|
}
|
|
}
|
|
bp = NEXT(bp);
|
|
}
|
|
if (min_p == NULL) return NULL;
|
|
_place(min_p, size);
|
|
return min_p;
|
|
}
|
|
|
|
static void *_first_fit_of_clear(size_t size) {
|
|
void *bp = list_p;
|
|
if (bp == NULL) return NULL;
|
|
do {
|
|
if (SIZE(bp) >= size) {
|
|
_place(bp, size);
|
|
return bp;
|
|
}
|
|
bp = (void *)GET_SUCC(bp);
|
|
} while (bp != list_p);
|
|
return NULL;
|
|
}
|
|
|
|
static void *_best_fit_of_clear(size_t size) {
|
|
void *bp = list_p;
|
|
if (bp == NULL) return NULL;
|
|
size_t min = 0;
|
|
void *min_p = NULL;
|
|
do {
|
|
if (SIZE(bp) >= size) {
|
|
if (min_p == NULL || SIZE(bp) < min) {
|
|
min = SIZE(bp);
|
|
min_p = bp;
|
|
}
|
|
}
|
|
bp = (void *)GET_SUCC(bp);
|
|
} while (bp != list_p);
|
|
if (min_p == NULL) return NULL;
|
|
_place(min_p, size);
|
|
return min_p;
|
|
}
|
|
|
|
static void _place(void *ptr, size_t size) {
|
|
size_t p_size = SIZE(ptr);
|
|
if (p_size - size >= MIN_BLOCK) {
|
|
SET(HEAD(ptr), PACK(size, 1));
|
|
SET(FOOT(ptr), PACK(size, 1));
|
|
// DSIZE adjust
|
|
size_t adjust_size = p_size - size - DSIZE;
|
|
void *new_ptr = NEXT(ptr);
|
|
SET(HEAD(new_ptr), PACK(adjust_size, 0));
|
|
SET(FOOT(new_ptr), PACK(adjust_size, 0));
|
|
if (ptr == tail_p) tail_p = new_ptr;
|
|
// tweak list
|
|
_fix_list(ptr, new_ptr);
|
|
if (ptr == list_p) list_p = new_ptr;
|
|
} else {
|
|
SET(HEAD(ptr), PACK(p_size, 1));
|
|
SET(FOOT(ptr), PACK(p_size, 1));
|
|
// tweak list
|
|
// remove
|
|
SET(POS_SUCC(GET_PRED(ptr)), GET_SUCC(ptr));
|
|
SET(POS_PRED(GET_SUCC(ptr)), GET_PRED(ptr));
|
|
if (ptr == list_p) {
|
|
if (GET_SUCC(ptr) == (size_t)ptr) list_p = NULL;
|
|
else list_p = (void *)GET_SUCC(ptr);
|
|
}
|
|
}
|
|
//#ifdef DEBUG
|
|
// printf("----place----\n");
|
|
// _check();
|
|
// printf("-------------\n");
|
|
//#endif
|
|
}
|
|
|
|
static void _fix_list(void *in, void *out) {
|
|
if (GET_SUCC(in) == (size_t)in) {
|
|
SET(POS_SUCC(out), (size_t)out);
|
|
SET(POS_PRED(out), (size_t)out);
|
|
} else {
|
|
SET(POS_SUCC(out), GET_SUCC(in));
|
|
SET(POS_PRED(out), GET_PRED(in));
|
|
SET(POS_SUCC(GET_PRED(in)), (size_t)out);
|
|
SET(POS_PRED(GET_SUCC(in)), (size_t)out);
|
|
}
|
|
}
|
|
|
|
static void _check() {
|
|
int num1 = 0;
|
|
int num2 = 0;
|
|
int num3 = 0;
|
|
void *bp = front_p;
|
|
void *after_p = NEXT(tail_p);
|
|
void *blank_p = NULL;
|
|
while (bp != after_p) {
|
|
if (!ALLOC(bp)) {
|
|
if (blank_p == NULL) blank_p = bp;
|
|
num1++;
|
|
}
|
|
bp = NEXT(bp);
|
|
}
|
|
bp = blank_p;
|
|
do {
|
|
if (bp != NULL) {
|
|
bp = (void *)GET_SUCC(bp);
|
|
num2++;
|
|
}
|
|
} while (bp != blank_p);
|
|
|
|
bp = list_p;
|
|
do {
|
|
if (bp != NULL) {
|
|
bp = (void *)GET_SUCC(bp);
|
|
num3++;
|
|
}
|
|
} while (bp != list_p);
|
|
|
|
printf("expect: %d, actual: %d, list_p: %d\n", num1, num2, num3);
|
|
}
|