-
Notifications
You must be signed in to change notification settings - Fork 0
/
implicit.c
177 lines (151 loc) · 5.49 KB
/
implicit.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
/* This file contains the implementation of the implicit free
list allocator. Includes functions that initialize the heap,
deal with malloc, realloc, and freeing memory.
*/
/* Features of implicit:
- Headers that track block information (8byte)
- Free blocks that are recycled and reused for subsequent malloc requests if possible
- malloc implementation searches heap for free blocks with implicit list
*/
#include "allocator.h"
#include "debug_break.h"
#include <string.h>
#include <stdio.h>
#define HEADER_SIZE 8
#define GET(p) (*(Header *)p).sa_bit //extracts header bits
#define GET_HEADER(blk) (Header *)blk - 1
#define GET_MEMORY(p) p + 1
#define GET_USED(p) (GET(p) & 0x1) //gets least significant bit
#define GET_SIZE(p) (GET(p) & ~0x7) // 3 LSB hold allocated status
#define SET_HEADER(p, val) (GET(p) = val)
#define SET_USED(p) (GET(p) |= 0x1)
#define SET_UNUSED(p) (GET(p) &= ~0x1)
#define GET_NEXT_HEADER(p) (Header*)((char*)p + GET_SIZE(p));
// node for linked list comprises of a ptr to the header and
// pointer to next node
typedef struct header {
size_t sa_bit; // stores size and allocation status
} Header;
// global variable for start of linked list
static void *segment_start;
static size_t nused;
static size_t segment_size;
static Header *base; //start node
//helper function header
Header *find_best_header(Header** cur_head, size_t size);
// rounds up sz to closest multiple of mult
size_t roundup(size_t sz, size_t mult) {
return (sz + mult - 1) & ~(mult - 1);
}
// initialize the heap and return the status of this
// initialization
bool myinit(void *heap_start, size_t heap_size) {
if (heap_size < HEADER_SIZE) {
return false;
}
segment_start = heap_start;
segment_size = heap_size;
nused = 0;
base = segment_start;
(*base).sa_bit = 0; //clear heap by allowing overwrite
return true;
}
// Malloc function that uses best fit to determine utilization of blocks. Implemented using a linked
// list of structs containing a pointer to the header and apointer to the next node
void *mymalloc(size_t requested_size) {
size_t req_size = roundup(requested_size, ALIGNMENT);
size_t total_size = req_size + HEADER_SIZE; // header is a multiple of alignment
Header *next_head_loc;
void *block;
Header *cur_head = base;
if (requested_size == 0 || requested_size > MAX_REQUEST_SIZE ||
(req_size + nused > segment_size)) {
return NULL;
}
Header *best_blk_head = find_best_header(&cur_head, total_size);
if (best_blk_head != NULL) { // usable block found
size_t best_blk_size = GET_SIZE(best_blk_head);
SET_USED(best_blk_head);
block = GET_MEMORY(best_blk_head); //best_blk_head + 1;
nused += (best_blk_size - HEADER_SIZE);
return block;
} else { // new allocation
size_t header = total_size + 1;
next_head_loc = GET_NEXT_HEADER(cur_head);
SET_HEADER(next_head_loc, header);
nused += total_size;
block = GET_MEMORY(next_head_loc);
return block;
}
return NULL;
}
// function that searches for a free, usable block of at least
// total_size using best-fit algorithm (block with lowest amt of enough free space)
Header *find_best_header(Header** cur_head_ad, size_t total_size) {
size_t best_blk_size = segment_size; //set to some max value
Header *best_blk_head = NULL;
Header *cur_head = *cur_head_ad;
size_t cur_blk_size = GET_SIZE(*cur_head_ad);
while(cur_blk_size != 0) { // search all blocks
if(cur_blk_size >= total_size && !GET_USED(cur_head)) {
if((cur_blk_size < best_blk_size) || (best_blk_head == NULL)) {
best_blk_head = cur_head;
best_blk_size = cur_blk_size;
}
}
cur_head = GET_NEXT_HEADER(cur_head);
cur_blk_size = GET_SIZE(cur_head);
}
*cur_head_ad = cur_head; // make sure current node in mymalloc is updated
return best_blk_head;
}
// this function "frees" memory by clearing the lowest bit in the header (where use of
// block is stored) for future resuse
void myfree(void *ptr) {
if (ptr == NULL) {
return;
}
Header* head = GET_HEADER(ptr);
SET_UNUSED(head);
nused -= (GET_SIZE(head) - HEADER_SIZE);
}
// myrealloc moves memory to new location with the new size and copies
// over data from old pointer and frees the old_ptr
void *myrealloc(void *old_ptr, size_t new_size) {
if (old_ptr == NULL) {
return mymalloc(new_size); //nothing to copy over
} else if (old_ptr != NULL && new_size == 0) {
myfree(old_ptr);
} else {
Header *old_head = GET_HEADER(old_ptr);
size_t old_size = GET_SIZE(old_head);
void *new_ptr = mymalloc(new_size); // updating of new header done in malloc
if (new_ptr == NULL) { //realloc failed
return NULL;
}
if (new_size < old_size) {
old_size = new_size;
}
memcpy(new_ptr, old_ptr, old_size);
myfree(old_ptr);
return new_ptr;
}
return NULL;
}
bool validate_heap() {
if(!base) {
return false;
}
// print_heap();
return true;
}
// prints entire heap from segment_start address
// prints address and header information
void print_heap() {
Header *cur = segment_start;
printf("Print entire heap: \n");
while(GET_SIZE(cur)) {
printf("Header Address: %p ; Header: %lu\n", cur, GET(cur));
cur = GET_NEXT_HEADER(cur);
}
}