1
2 #include <assert.h>
3 #include <stdint.h>
4 #include <stdlib.h>
5 #include <sys/types.h>
6 #include <sys/mman.h>
7
8 typedef struct Header {
9 uint16_t magic;
10 uint16_t status;
11 uint32_t size;
12 struct Header *next;
13 } Header;
14
15 #define HEAP_MAGIC 0x8051
16
17 #define HEAP_MIN_POOLSIZE (64 - sizeof(Header))
18 #define HEAP_MAX_POOLSIZE (128*1024 - sizeof(Header))
19 #define HEAP_POOLS (12)
20
21 #define PGSIZE 4096
22 #define HEAP_INCREMENT (PGSIZE / 64)
23
24 typedef struct HeapPool {
25 uint32_t blocksInuse;
26 uint32_t blocksFree;
27 Header *free;
28 uint64_t base;
29 uint64_t top;
30 } HeapPool;
31
32 #define ROUNDUP(_x, _n) (((_x) + (_n) - 1) & ~((_n) - 1))
33
34 static HeapPool pool[HEAP_POOLS] = {
35 { 0, 0, (Header *)0, 0x400000000, 0x400000000 }, // 64B
36 { 0, 0, (Header *)0, 0x410000000, 0x410000000 }, // 128B
37 { 0, 0, (Header *)0, 0x420000000, 0x420000000 }, // 256B
38 { 0, 0, (Header *)0, 0x430000000, 0x430000000 }, // 512B
39 { 0, 0, (Header *)0, 0x440000000, 0x440000000 }, // 1KB
40 { 0, 0, (Header *)0, 0x450000000, 0x450000000 }, // 2KB
41 { 0, 0, (Header *)0, 0x460000000, 0x460000000 }, // 4KB
42 { 0, 0, (Header *)0, 0x470000000, 0x470000000 }, // 8KB
43 { 0, 0, (Header *)0, 0x480000000, 0x480000000 }, // 16KB
44 { 0, 0, (Header *)0, 0x490000000, 0x490000000 }, // 32KB
45 { 0, 0, (Header *)0, 0x4A0000000, 0x4A0000000 }, // 64KB
46 { 0, 0, (Header *)0, 0x4B0000000, 0x4B0000000 }, // 128KB
47 };
48
49 static HeapPool largePool = { 0, 0, (Header *)0, 0x4C000000, 0x4C000000 }; // 128KB+
50
51 static int
size_to_idx(size_t sz)52 size_to_idx(size_t sz)
53 {
54 int i;
55 size_t bucketSz = 64;
56
57 for (i = 0; ; i++) {
58 if ((bucketSz - sizeof(Header)) >= sz) {
59 return i;
60 }
61
62 bucketSz *= 2;
63 }
64 }
65
66 static void
grow_small(int idx)67 grow_small(int idx)
68 {
69 int i;
70 size_t bucketSz = (1 << idx) * 64; // Compute bucket size
71 char *addr = (char *)pool[idx].top;
72
73 addr = (char *)mmap(addr, bucketSz * HEAP_INCREMENT,
74 PROT_READ|PROT_WRITE, MAP_ANON|MAP_FIXED,
75 -1, 0);
76 if (addr == NULL) {
77 return;
78 }
79
80 // Update top pointer
81 pool[idx].top += bucketSz * HEAP_INCREMENT;
82
83 for (i = 0; i < HEAP_INCREMENT; i++) {
84 Header *obj = (Header *)(addr + i * bucketSz);
85
86 obj->magic = HEAP_MAGIC;
87 obj->status = 0;
88 obj->size = bucketSz - sizeof(Header);
89 obj->next = pool[idx].free;
90 pool[idx].free = obj;
91 }
92 }
93
94 static void *
malloc_small(size_t sz)95 malloc_small(size_t sz)
96 {
97 int idx = size_to_idx(sz);
98 Header *hdr;
99
100 // Grow pool if freelist is empty
101 if (pool[idx].free == 0)
102 grow_small(idx);
103
104 // Malloc failed
105 if (pool[idx].free == 0)
106 return NULL;
107
108 hdr = pool[idx].free;
109 pool[idx].free = hdr->next;
110
111 return (void *)(hdr + 1);
112 }
113
114 static void
free_small(Header * mem)115 free_small(Header *mem)
116 {
117 int idx = size_to_idx(mem->size);
118
119 mem->next = pool[idx].free;
120 pool[idx].free = mem;
121 }
122
123 static void *
malloc_large(size_t sz)124 malloc_large(size_t sz)
125 {
126 uintptr_t ptr = largePool.top;
127 uintptr_t realSz = ROUNDUP(sz, 4096);
128 Header *addr;
129
130 addr = (Header *)mmap((void *)ptr, realSz,
131 PROT_READ|PROT_WRITE, MAP_ANON|MAP_FIXED,
132 -1, 0);
133 if (addr == NULL) {
134 return NULL;
135 }
136
137 addr->magic = HEAP_MAGIC;
138 addr->status = 0;
139 addr->size = realSz;
140 addr->next = 0;
141
142 largePool.top += realSz;
143
144 return (void *)(addr + 1);
145 }
146
147 static void
free_large(Header * mem)148 free_large(Header *mem)
149 {
150 munmap(mem, mem->size);
151 }
152
153 void *
calloc(size_t num,size_t sz)154 calloc(size_t num, size_t sz)
155 {
156 return malloc(num*sz);
157 }
158
159 void *
malloc(size_t sz)160 malloc(size_t sz)
161 {
162 if (sz > HEAP_MAX_POOLSIZE)
163 return malloc_large(sz);
164 else
165 return malloc_small(sz);
166 }
167
168 void
free(void * mem)169 free(void *mem)
170 {
171 Header *hdr = (Header *)mem;
172 hdr--;
173
174 if (mem == NULL)
175 return;
176
177 assert(hdr->magic == HEAP_MAGIC);
178
179 if (hdr->size > HEAP_MAX_POOLSIZE)
180 free_large(hdr);
181 else
182 free_small(hdr);
183 }
184
185