From eb47984a47e0baa5a95cd25cf6b4d745429d42e6 Mon Sep 17 00:00:00 2001 From: _ov4 Date: Sat, 31 Oct 2026 07:08:25 +0000 Subject: fix malloc implicit --- malloclab-handout/Makefile | 14 +- malloclab-handout/mm-implicit.cc | 231 +++++++++++++++++++++++++++++++++ malloclab-handout/mm-naive-free.cc | 195 ---------------------------- malloclab-handout/util/mm-implicit.h | 101 ++++++++++++++ malloclab-handout/util/mm-naive-free.h | 95 -------------- 5 files changed, 342 insertions(+), 294 deletions(-) create mode 100644 malloclab-handout/mm-implicit.cc delete mode 100644 malloclab-handout/mm-naive-free.cc create mode 100644 malloclab-handout/util/mm-implicit.h delete mode 100644 malloclab-handout/util/mm-naive-free.h (limited to 'malloclab-handout') diff --git a/malloclab-handout/Makefile b/malloclab-handout/Makefile index ba906f6..288a361 100644 --- a/malloclab-handout/Makefile +++ b/malloclab-handout/Makefile @@ -7,8 +7,8 @@ HANDINDIR = /afs/cs.cmu.edu/academic/class/15213-f01/malloclab/handin CC = gcc CXX = g++ -CFLAGS = -Wall -Og -m32 -CXXFLAGS = -Wall -Og -m32 -std=c++23 +CFLAGS = -Wall -Og -g -m32 +CXXFLAGS = -Wall -Og -g -m32 -std=c++23 OBJS = mdriver.o memlib.o fsecs.o fcyc.o clock.o ftimer.o MM_TARGETS = $(basename $(wildcard mm*.cc)) @@ -16,6 +16,12 @@ MM_TARGETS = $(basename $(wildcard mm*.cc)) MAKEFLAGS += --no-builtin-rules .SUFFIXES: +VERBOSE ?= 0 + +ifeq ($(VERBOSE),1) +VERBOSE_FLAG += -DOV4_VERBOSE +endif + .PHONY: $(MM_TARGETS) $(MM_TARGETS): %: %.out @@ -23,10 +29,10 @@ $(MM_TARGETS): %: %.out $(CXX) $(CXXFLAGS) -o $@ $^ %.o: %.cc mm.h memlib.h - $(CXX) $(CXXFLAGS) -c -o $@ $< + $(CXX) $(VERBOSE_FLAG) $(CXXFLAGS) -c -o $@ $< %.o: %.c - $(CC) $(CFLAGS) -c -o $@ $< + $(CC) $(VERBOSE_FLAG) $(CFLAGS) -c -o $@ $< mdriver.o: mdriver.c fsecs.h fcyc.h clock.h memlib.h config.h mm.h memlib.o: memlib.c memlib.h diff --git a/malloclab-handout/mm-implicit.cc b/malloclab-handout/mm-implicit.cc new file mode 100644 index 0000000..f38032d --- /dev/null +++ b/malloclab-handout/mm-implicit.cc @@ -0,0 +1,231 @@ +/* + * mm-naive.c - The fastest, least memory-efficient malloc package. + * + * In this naive approach, a block is allocated by simply incrementing + * the brk pointer. A block is pure payload. There are no headers or + * footers. Blocks are never coalesced or reused. Realloc is + * implemented directly using mm_malloc and mm_free. + * + * NOTE TO STUDENTS: Replace this header comment with your own header + * comment that gives a high level description of your solution. + */ +#include +#include +#include +#include +#include +#include +#include + +#include "util/mm-implicit.h" + +#include "mm.h" +#include "memlib.h" + +using namespace std; + +void print_list(); + +/********************************************************* + * NOTE TO STUDENTS: Before you do anything else, please + * provide your team information in the following struct. + ********************************************************/ +team_t team = { + /* Team name */ + "ov4.org", + /* First member's full name */ + "_ov4", + /* First member's email address */ + "ov4@ov4.org", + /* Second member's full name (leave blank if none) */ + "", + /* Second member's email address (leave blank if none) */ + "" +}; + + +/* + * mm_init - initialize the malloc package. + */ +int mm_init(void) +{ + return 0; +} + +void mm_quit(int code, int line) +{ + loggerln("exit, line: {}", line); + exit(code); +} + +/* + * mm_malloc - Allocate a block by incrementing the brk pointer. + * Always allocate a block whose size is a multiple of the alignment. + */ +void *mm_malloc(size_t size) +{ + loggerln("---------- malloc ----------"); + loggerln("argument: {}", size); + print_list(); + size_t newsize = align(size + SIZE_T_SIZE); + loggerln("newsize: {}", newsize); + size_t p = (size_t)mem_heap_lo(); + bool prev_alloc = true; + + while (true) + { + //if (newsize == 4080) sleep(1); + size_t status = 0; + loggerln("offset: {}", (size_t)p-(size_t)mem_heap_lo()); + + // out of heap + if (p >= (size_t)mem_heap_hi()) + { + // then increase heap + // and set current pos to be free + // so it can be alloc'd soon + loggerln("before: max addr {}", offset((size_t)mem_heap_hi())); + mem_sbrk(newsize); + loggerln("sbrk {}", newsize); + loggerln("max addr {}", offset((size_t)mem_heap_hi())); + + set_size(status, newsize); + set_alloc(status, false); + set_prev_alloc(status, true); // TODO + *(size_t*)p = status; + } + status = *(size_t*)p; + if (is_alloc(status)) + { + p += get_size(status); + prev_alloc = true; + continue; + } + prev_alloc = false; + + if (get_size(status) < newsize) + { + next(p); + continue; + } + + size_t oldsize = get_size(status); + + set_size(status, newsize); + set_alloc(status, true); + set_prev_alloc(status, true); // TODO + *(size_t*)p = status; + void *ret = (void*)((char*)p + SIZE_T_SIZE); + + + // if we don't use all of free space + // split free block into 2 parts + if (oldsize > newsize) + { + size_t free_status = 0; + set_size(free_status, oldsize - newsize); + set_alloc(free_status, false); + set_prev_alloc(free_status, true); + size_t free_header_p = p+newsize; + *(size_t*)(free_header_p) = free_status; + sync_footer(free_header_p); + loggerln("split free: free begins {}", offset(free_header_p)); + } + + loggerln("return: {}" , (size_t)ret-(size_t)mem_heap_lo()); + return ret; + + } + +} + +/* + * mm_free - Freeing a block does nothing. + */ +void mm_free(void *ptr) +{ + if (ptr == nullptr) return; + + loggerln("---------- free ----------"); + + loggerln("argument: {}", (size_t)ptr-(size_t)mem_heap_lo()); + + print_list(); + + size_t header = (size_t)ptr-SIZE_T_SIZE; + size_t next_header = header + get_size(*(size_t*)header); + + if (next_header > (size_t)mem_heap_hi()) next_header = 0; + + loggerln("header: {}", offset(header)); + loggerln("header size: {}", get_size(*(size_t*)header)); + loggerln("next: {}", next_header != 0 ? offset(next_header) : 0); + + // free current block + set_alloc(*(size_t*)header, false); + sync_footer(header); + + // if next_header is free + if ((next_header != 0) + && (!is_alloc(*(size_t*)next_header))) + { + size_t newsize = get_size(*(size_t*)header) + get_size(*(size_t*)next_header); + loggerln("next free: newsize {}", newsize); + set_size(*(size_t*)header, newsize); + sync_footer(header); + } + + // if prev exists + // and is free + if (!is_prev_alloc(*(size_t*)header) + && header != (size_t)mem_heap_lo()) + { + + loggerln("handling prev free"); + + size_t prev_footer = header - SIZE_T_SIZE; + size_t prev_header = header - get_size(*(size_t*)prev_footer); + + loggerln("prev_footer: {}", offset(prev_footer)); + loggerln("prev footer size: {}", get_size(*(size_t*)prev_footer)); + + loggerln("ok 0"); + size_t newsize = get_size(*(size_t*)prev_header) + get_size(*(size_t*)header); + loggerln("ok1"); + set_size(*(size_t*)prev_header, newsize); + loggerln("ok2"); + sync_footer(prev_header); + } +} + +/* + * mm_realloc - Implemented simply in terms of mm_malloc and mm_free + */ +void *mm_realloc(void *ptr, size_t size) +{ + void *oldptr = ptr; + void *newptr; + size_t copySize; + + newptr = mm_malloc(size); + if (newptr == NULL) + return NULL; + copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE); + if (size < copySize) + copySize = size; + memcpy(newptr, oldptr, copySize); + mm_free(oldptr); + return newptr; +} + + + + + + + + + + + + diff --git a/malloclab-handout/mm-naive-free.cc b/malloclab-handout/mm-naive-free.cc deleted file mode 100644 index f39361a..0000000 --- a/malloclab-handout/mm-naive-free.cc +++ /dev/null @@ -1,195 +0,0 @@ -/* - * mm-naive.c - The fastest, least memory-efficient malloc package. - * - * In this naive approach, a block is allocated by simply incrementing - * the brk pointer. A block is pure payload. There are no headers or - * footers. Blocks are never coalesced or reused. Realloc is - * implemented directly using mm_malloc and mm_free. - * - * NOTE TO STUDENTS: Replace this header comment with your own header - * comment that gives a high level description of your solution. - */ -#include -#include -#include -#include -#include -#include -#include - -#include "util/mm-naive-free.h" - -#include "mm.h" -#include "memlib.h" - -using namespace std; - -void print_list(); - -/********************************************************* - * NOTE TO STUDENTS: Before you do anything else, please - * provide your team information in the following struct. - ********************************************************/ -team_t team = { - /* Team name */ - "ov4.org", - /* First member's full name */ - "_ov4", - /* First member's email address */ - "ov4@ov4.org", - /* Second member's full name (leave blank if none) */ - "", - /* Second member's email address (leave blank if none) */ - "" -}; - - -/* - * mm_init - initialize the malloc package. - */ -int mm_init(void) -{ - return 0; -} - -void mm_quit(int code, int line) -{ - loggerln("exit, line: {}", line); - exit(code); -} - -/* - * mm_malloc - Allocate a block by incrementing the brk pointer. - * Always allocate a block whose size is a multiple of the alignment. - */ -void *mm_malloc(size_t size) -{ - loggerln("---------- malloc ----------"); - print_list(); - size_t newsize = align(size + SIZE_T_SIZE); - loggerln("newsize: {}", newsize); - size_t p = (size_t)mem_heap_lo(); - bool prev_alloc = true; - - while (true) - { - //if (newsize == 4080) sleep(1); - size_t status = 0; - loggerln("offset: {}", (size_t)p-(size_t)mem_heap_lo()); - - // out of heap - if (p >= (size_t)mem_heap_hi()) - { - // then increase heap - // and set current pos to be free - // so it can be alloc'd soon - loggerln("sbrk"); - mem_sbrk(newsize); - set_size(status, newsize); - set_alloc(status, false); - *(size_t*)p = status; - } - status = *(size_t*)p; - if (is_alloc(status)) - { - p += get_size(status); - prev_alloc = true; - continue; - } - prev_alloc = false; - - if (get_size(status) < newsize) - { - next(p); - continue; - } - - size_t oldsize = get_size(status); - - set_size(status, newsize); - set_alloc(status, true); - set_prev_alloc(status, prev_alloc); - *(size_t*)p = status; - void *ret = (void*)((char*)p + SIZE_T_SIZE); - - if (oldsize > newsize) - { - size_t free_status = 0; - set_size(free_status, oldsize-newsize); - set_alloc(free_status, false); - set_prev_alloc(free_status, false); - *(size_t*)(p+newsize) = free_status; - loggerln("split free: free begins {}", offset(p+newsize)); - } - - loggerln("return: {}" , (size_t)ret-(size_t)mem_heap_lo()); - return ret; - - } - -} - -/* - * mm_free - Freeing a block does nothing. - */ -void mm_free(void *ptr) -{ - if (ptr == nullptr) return; - - loggerln("---------- free ----------"); - - loggerln("argument: {}", (size_t)ptr-(size_t)mem_heap_lo()); - - print_list(); - - size_t header = (size_t)ptr-SIZE_T_SIZE; - size_t next = header + get_size(*(size_t*)header); - - if (next > (size_t)mem_heap_hi()) next = 0; - - loggerln("header: {}", offset(header)); - loggerln("header size: {}", get_size(*(size_t*)header)); - loggerln("next: {}", next != 0 ? offset(next) : 0); - - set_alloc(*(size_t*)header, false); - - // if next is free - if ((next != 0) - && (!is_alloc(*(size_t*)next))) - { - size_t newsize = get_size(*(size_t*)header) + get_size(*(size_t*)next); - set_size(*(size_t*)header, newsize); - } -} - -/* - * mm_realloc - Implemented simply in terms of mm_malloc and mm_free - */ -void *mm_realloc(void *ptr, size_t size) -{ - void *oldptr = ptr; - void *newptr; - size_t copySize; - - newptr = mm_malloc(size); - if (newptr == NULL) - return NULL; - copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE); - if (size < copySize) - copySize = size; - memcpy(newptr, oldptr, copySize); - mm_free(oldptr); - return newptr; -} - - - - - - - - - - - - diff --git a/malloclab-handout/util/mm-implicit.h b/malloclab-handout/util/mm-implicit.h new file mode 100644 index 0000000..74e0f86 --- /dev/null +++ b/malloclab-handout/util/mm-implicit.h @@ -0,0 +1,101 @@ +#pragma once + +#include + +#include "../mm.h" +#include "../memlib.h" + + +using namespace std; + +/* single word (4) or double word (8) alignment */ +#define ALIGNMENT 8 + +/* rounds up to the nearest multiple of ALIGNMENT */ +inline size_t align(size_t size) +{ + return (((size) + (ALIGNMENT-1)) & ~0x7); +} + +inline constexpr size_t SIZE_T_SIZE = 8; + +inline bool is_alloc(size_t status) +{ + return (status&0x1); +} +inline bool is_prev_alloc(size_t status) +{ + return (status&0x2) >> 1; +} +inline void set_alloc(size_t &status, bool is_alloc) +{ + if (is_alloc) + status |= 0x1; + else + status &= 0xfffffffe; +} +inline void set_prev_alloc(size_t &status, bool is_prev_alloc) +{ + if (is_prev_alloc) + status |= 0x2; + else + status &= 0xfffffffd; +} +inline size_t get_size(size_t status) +{ + // ignore lowest 2 bits + return status&0xfffffffc; +} +inline void set_size(size_t &status, size_t size) +{ + status &= 0x3; + status |= (size & 0xfffffffc); +} +inline size_t offset(size_t p) +{ + return (size_t)((size_t)p-(size_t)mem_heap_lo()); +} +inline void next(size_t &p) +{ + p += get_size(*(size_t*)p); +} + +template< class... Args > +void loggerln( std::format_string fmt, Args&&... args ) +{ +#ifdef OV4_VERBOSE + println(fmt, forward(args)...); +#endif +} + +template< class... Args > +void logger( std::format_string fmt, Args&&... args ) +{ +#ifdef OV4_VERBOSE + print(fmt, forward(args)...); +#endif +} + + +void print_list() +{ +#ifdef OV4_VERBOSE + logger("print_list: "); + size_t p = (size_t)mem_heap_lo(); + while (true) + { + if (p >= (size_t)mem_heap_hi()) + break; + + logger("{}({},{}) ", offset(p), is_alloc(*(size_t*)p) ? "alloc" : "free", get_size(*(size_t*)p)); + p += get_size(*(size_t*)p); + } + loggerln(""); +#endif +} + +void sync_footer(size_t header) +{ + size_t footer = header + get_size(*(size_t*)header) - SIZE_T_SIZE; + *(size_t*)footer = *(size_t*)header; +} \ No newline at end of file diff --git a/malloclab-handout/util/mm-naive-free.h b/malloclab-handout/util/mm-naive-free.h deleted file mode 100644 index 3aa06bd..0000000 --- a/malloclab-handout/util/mm-naive-free.h +++ /dev/null @@ -1,95 +0,0 @@ -#pragma once - -#include - -#include "../mm.h" -#include "../memlib.h" - - -using namespace std; - -/* single word (4) or double word (8) alignment */ -#define ALIGNMENT 8 - -/* rounds up to the nearest multiple of ALIGNMENT */ -inline size_t align(size_t size) -{ - return (((size) + (ALIGNMENT-1)) & ~0x7); -} - -inline constexpr size_t SIZE_T_SIZE = 8; - -inline bool is_alloc(size_t status) -{ - return (status&0x1); -} -inline bool is_prev_alloc(size_t status) -{ - return (status&0x2) >> 1; -} -inline void set_alloc(size_t &status, bool is_alloc) -{ - if (is_alloc) - status |= 0x1; - else - status &= 0xfffffffe; -} -inline void set_prev_alloc(size_t &status, bool is_prev_alloc) -{ - if (is_prev_alloc) - status |= 0x2; - else - status &= 0xfffffffd; -} -inline size_t get_size(size_t status) -{ - // ignore lowest 2 bits - return status&0xfffffffc; -} -inline void set_size(size_t &status, size_t size) -{ - status &= 0x3; - status |= (size & 0xfffffffc); -} -inline size_t offset(size_t p) -{ - return (size_t)((size_t)p-(size_t)mem_heap_lo()); -} -inline void next(size_t &p) -{ - p += get_size(*(size_t*)p); -} - -template< class... Args > -void loggerln( std::format_string fmt, Args&&... args ) -{ -#ifdef OV4_VERBOSE - println(fmt, forward(args)...); -#endif -} - -template< class... Args > -void logger( std::format_string fmt, Args&&... args ) -{ -#ifdef OV4_VERBOSE - print(fmt, forward(args)...); -#endif -} - - -void print_list() -{ -#ifdef OV4_VERBOSE - logger("print_list: "); - size_t p = (size_t)mem_heap_lo(); - while (true) - { - if (p >= (size_t)mem_heap_hi()) - break; - - logger("{} ", offset(p)); - p += get_size(*(size_t*)p); - } - loggerln(""); -#endif -} \ No newline at end of file -- cgit v1.3.1-4-g156e