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
|
/*
* Copyright (c) Jon Santmyer.
* This source file is released under the LGPL Version 3 as detailed in
* the LICENSE file provided in the following repository:
* https://git.jonsantmyer.com/heap/
* */
#include "malloc.h"
#include <assert.h>
bucket_t*
__bucket_from_obj(heap_cache_t *cache, bucket_obj_t *obj)
{
assert(cache != NULL);
assert(cache->head != NULL);
/* Buckets are always aligned to the nearest page boundary, and that the
* metadata is always below the object. We use this fact to quickly find
* owning buckets.*/
uintptr_t objptr = (uintptr_t)obj;
uintptr_t bktptr = objptr & ~0xFFF;
while(1) {
/* If the page boundary is below the head, we are below the heap memory
* region and can stop.*/
if(bktptr < (uintptr_t)cache->head) return NULL;
/* At each page boundary below the object, check for the heap checksum.
* If it is found, we can assume that we found a bucket.*/
bucket_t *bucket = (bucket_t*)bktptr;
if(OBJ_VALID(bucket)) {
if(bucket->limit > objptr) return NULL;
return bucket;
}
bktptr -= BUCKET_ALIGN;
}
}
void
__free_impl(heap_cache_t *cache, void *ptr)
{
DBGPRINT("free: asking to free ptr %p\n", ptr);
assert(cache != NULL);
/* free(NULL) does nothing.*/
if(ptr == NULL) return;
/* Make sure the pointer actually comes from the heap.*/
assert((uintptr_t)ptr < (uintptr_t)cache->tail);
assert((uintptr_t)ptr > (uintptr_t)cache->head);
bucket_obj_t *obj = OBJ_FROM_PTR(ptr);
assert(OBJ_VALID(obj));
/* Mask the taken bit in the object to mark it free.*/
DBGPRINT("free: masking taken bit in object %p (was %i, now ",
obj, obj->size_taken);
obj->size_taken &= ~1;
DBGPRINT("%i)\n", obj->size_taken);
/* If the buckets' lastfree is greater than this new free object, this
* object will be the lastfree.*/
bucket_t *bucket = __bucket_from_obj(cache, obj);
if(bucket != NULL && bucket->firstfree > obj)
bucket->firstfree = obj;
/* Start trying to merge this free object with the next object.
* If the object after is taken, do nothing.*/
bucket_obj_t *after = OBJ_AFTER(obj);
if((uintptr_t)after > bucket->limit) return;
assert(OBJ_VALID(after));
if(OBJ_TAKEN(after)) return;
/* Merge with the next object.
* from:
* [meta| -objw-][meta| -afterw-]
* to:
* [meta| ---------objw---------]*/
DBGPRINT("free: obj %p merging with adjacent free object %p (was %i, now \n",
obj, after, obj->size_taken);
obj->size_taken += sizeof(bucket_obj_t) + after->size_taken;
DBGPRINT("%i)\n", obj->size_taken);
}
|
