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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
|
#include "malloc.h"
#include <assert.h>
#include <stdbool.h>
#include <unistd.h>
#include <errno.h>
/**Allocate memory for a new bucket in the heap.
* Automatically aligns new memory to BUCKET_ALIGN.
* Instantiates a new free object spanning the entire bucket.
* Then adds the new bucket to the heap cache.
* If sbrk encounters an error, pass through errno and return NULL.
* @param cache to allocate for.
* @param objw width of the object the bucket is assumed to hold.
* @return bucket created by this function.*/
bucket_t*
s_bucket_new(heap_cache_t *cache, size_t objw)
{
DBGPRINT("malloc: ask for new bucket for cache %p with objw %i\n", cache, objw);
size_t bucketw = BUCKET_WIDTH(objw);
/* Assuming sbrk allocates memory for after the program break, make sure
* we allocate enough for the requested bucket width and any adjustments
* to ensure page alignment.*/
uintptr_t pbrk = (uintptr_t)sbrk(0);
uintptr_t brko = pbrk % BUCKET_ALIGN;
uintptr_t nbrk = (uintptr_t)sbrk(bucketw + brko);
if(errno != 0) return NULL; /* Fail on errno. */
bucket_t *bucket = (bucket_t*)(nbrk + brko);
DBGPRINT("malloc: got new bucket at %p\n", bucket);
*bucket = (bucket_t){
.next = NULL,
.limit = (uintptr_t)bucket + bucketw,
};
/* Create a new object spanning the entire bucket. This new object will
* be the first free.*/
bucket_obj_t *obj0 = (bucket_obj_t*)bucket->objs;
*obj0 = (bucket_obj_t) {
.checksum = OBJ_CHECKSUM,
.size_taken = bucketw - sizeof(bucket_t) - sizeof(bucket_obj_t)
};
bucket->firstfree = obj0;
/* If the cache is empty, this will be the first and last bucket.*/
if(cache->head == NULL) {
cache->head = cache->tail = bucket;
return bucket;
}
/* Add the bucket to the heap cache bucket list.*/
cache->tail->next = bucket;
cache->tail = bucket;
return bucket;
}
/**Given an existing object and a size, split the object so that the original
* has size w.
* If the object is smaller than or is already the correct size, do nothing.
* Space after the split is allocated to a new free object after the resized
* original.
* If the original == bucket->firstfree, the new object is assigned to
* that variable.
* If the heap is corrupted, assert fail.
* @param bucket object's parent bucket.
* @param parent object to split.
* @param w requested size for original object. */
void
s_obj_take_split(bucket_t *bucket, bucket_obj_t *parent, size_t w)
{
DBGPRINT("malloc: requesting to split object %p (last %p) for size %i (was %i)\n",
bucket, parent, w, parent->size_taken);
/* Assert fail on corrupted heap.*/
assert(OBJ_VALID(bucket));
assert(OBJ_VALID(parent));
assert(w >= OBJ_SIZE_MIN);
size_t objw = OBJ_WIDTH(parent);
if(w == objw) { /* Obj is already correct size, take and ignore.*/
if(bucket->firstfree == parent)
bucket->firstfree = OBJ_AFTER(parent);
/* Ensure that firstfree does not exceed bucket limits.*/
if((uintptr_t)bucket->firstfree > bucket->limit)
bucket->firstfree = NULL;
DBGPRINT("malloc: Object is already right size, ignoring\n");
/* Mark object as taken.*/
parent->size_taken = w | 1;
return;
}
/* New object created by split will be the original width minus the new
* width and metadata size.
*
* from:
* [meta| --------objw-------- ]
*
* to:
* [meta| -w- ][meta| -afterw- ]*/
size_t afterw = objw - sizeof(bucket_obj_t) - w;
parent->size_taken = w | 1;
bucket_obj_t *obj = OBJ_AFTER(parent);
DBGPRINT("malloc: New object created inplace at %p with size %i\n",
obj, afterw);
/* In-place allocate after obj.*/
*obj = (bucket_obj_t){
.checksum = OBJ_CHECKSUM,
.size_taken = afterw,
};
if(bucket->firstfree == parent)
bucket->firstfree = obj;
}
/* Look for a free object in the given bucket that closest matches size w.
* Uses bucket->firstfree as a starting point to save checks against taken
* objects.
* If the heap is corrupted, assert fail.
* If there are no good objects in this bucket, return NULL.
* @param bucket to search in.
* @param w to search for.
* @return best-fitting object or NULL if none are found.
* */
bucket_obj_t*
s_obj_bestfit(bucket_t *bucket, size_t w)
{
assert(bucket != NULL);
assert(OBJ_VALID(bucket));
bucket_obj_t *best = NULL;
bucket_obj_t *obj = bucket->firstfree;
if(obj == NULL) return NULL;
for(; (uintptr_t)obj < bucket->limit; obj = OBJ_AFTER(obj))
{
assert(OBJ_VALID(obj));
if(OBJ_TAKEN(obj)) continue;
size_t objw = OBJ_WIDTH(obj);
if(objw < w) continue;
if(best == NULL) best = obj;
size_t bestw = OBJ_WIDTH(best);
if(objw < bestw) best = obj;
}
DBGPRINT("malloc: Bucket %p returns best fit at %p for size %i ",
bucket, best, w);
if(best != NULL) { DBGPRINT("(size %i)\n", best->size_taken); }
else { DBGPRINT("(is NULL)\n"); }
return best;
}
/**Searching through the entire heap, or until an object is found, find a
* free object that best fits the requested width and place the resulting
* bucket in the passed pointer.
* If the heap is corrupted, assert fail.
* If no object is found in any of the buckets, return NULL.
* @param cache heap to search through.
* @param w object width to search for.
* @param bucket pointer to bucket pointer owning the returned bucket.
* If no object is found, variable is untouched.
* @return object that fits the given width.*/
bucket_obj_t*
s_bucket_bestfit(heap_cache_t *cache, size_t w, bucket_t **bucket)
{
*bucket = cache->head;
for(; *bucket != NULL; *bucket = (*bucket)->next)
{
bucket_obj_t *obj = s_obj_bestfit(*bucket, w);
/* Object is already found, don't waste cycles searching through
* the entire heap.*/
if(obj != NULL) return obj;
}
return NULL;
}
void*
__malloc_impl(heap_cache_t *cache, size_t w)
{
assert(cache != NULL);
/* w == 0 is ub, just return NULL.*/
if(w == 0) return NULL;
/* Ensure that w is valid.*/
w = REALW(w);
DBGPRINT("malloc: Asking to malloc for size %i\n", w);
bucket_t *bucket = NULL;
bucket_obj_t *obj = s_bucket_bestfit(cache, w, &bucket);
if(obj == NULL) {
/* No bucket in the heap has an appropriate space.
* Allocate a new bucket and take the first object.
* If the bucket allocation fails, return -1 and pass errno through.*/
bucket = s_bucket_new(cache, w);
if(bucket == NULL) return (void*)(-1);
obj = (bucket_obj_t*)bucket->objs;
}
/* Split the bucket to make the object bestfit.*/
s_obj_take_split(bucket, obj, w);
return obj->data;
}
|
