/* [<][>][^][v][top][bottom][index][help] */
DEFINITIONS
This source file includes following definitions.
- __malloc_init
- __malloc_dump
- __malloc_sbrk
- __malloc_split
- malloc
- __malloc_deadbeef
- __malloc_trymerge
- free
1 /*
2 * Copyright (c) 2000, 2001, 2002, 2003, 2004, 2005, 2008, 2009
3 * The President and Fellows of Harvard College.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE UNIVERSITY AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE UNIVERSITY OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 */
29
30 /*
31 * User-level malloc and free implementation.
32 *
33 * This is a basic first-fit allocator. It's intended to be simple and
34 * easy to follow. It performs abysmally if the heap becomes larger than
35 * physical memory. To get (much) better out-of-core performance, port
36 * the kernel's malloc. :-)
37 */
38
39 #include <stdlib.h>
40 #include <unistd.h>
41 #include <err.h>
42 #include <stdint.h> // for uintptr_t on non-OS/161 platforms
43
44 #undef MALLOCDEBUG
45
46 #if defined(__mips__) || defined(__i386__)
47 #define MALLOC32
48 #elif defined(__alpha__)
49 #define MALLOC64
50 #else
51 #error "please fix me"
52 #endif
53
54 /*
55 * malloc block header.
56 *
57 * mh_prevblock is the downwards offset to the previous header, 0 if this
58 * is the bottom of the heap.
59 *
60 * mh_nextblock is the upwards offset to the next header.
61 *
62 * mh_pad is unused.
63 * mh_inuse is 1 if the block is in use, 0 if it is free.
64 * mh_magic* should always be a fixed value.
65 *
66 * MBLOCKSIZE should equal sizeof(struct mheader) and be a power of 2.
67 * MBLOCKSHIFT is the log base 2 of MBLOCKSIZE.
68 * MMAGIC is the value for mh_magic*.
69 */
70 struct mheader {
71
72 #if defined(MALLOC32)
73 #define MBLOCKSIZE 8
74 #define MBLOCKSHIFT 3
75 #define MMAGIC 2
76 /*
77 * 32-bit platform. size_t is 32 bits (4 bytes).
78 * Block size is 8 bytes.
79 */
80 unsigned mh_prevblock:29;
81 unsigned mh_pad:1;
82 unsigned mh_magic1:2;
83
84 unsigned mh_nextblock:29;
85 unsigned mh_inuse:1;
86 unsigned mh_magic2:2;
87
88 #elif defined(MALLOC64)
89 #define MBLOCKSIZE 16
90 #define MBLOCKSHIFT 4
91 #define MMAGIC 6
92 /*
93 * 64-bit platform. size_t is 64 bits (8 bytes)
94 * Block size is 16 bytes.
95 */
96 unsigned mh_prevblock:62;
97 unsigned mh_pad:1;
98 unsigned mh_magic1:3;
99
100 unsigned mh_nextblock:62;
101 unsigned mh_inuse:1;
102 unsigned mh_magic2:3;
103
104 #else
105 #error "please fix me"
106 #endif
107 };
108
109 /*
110 * Operator macros on struct mheader.
111 *
112 * M_NEXT/PREVOFF: return offset to next/previous header
113 * M_NEXT/PREV: return next/previous header
114 *
115 * M_DATA: return data pointer of a header
116 * M_SIZE: return data size of a header
117 *
118 * M_OK: true if the magic values are correct
119 *
120 * M_MKFIELD: prepare a value for mh_next/prevblock.
121 * (value should include the header size)
122 */
123
124 #define M_NEXTOFF(mh) ((size_t)(((size_t)((mh)->mh_nextblock))<<MBLOCKSHIFT))
125 #define M_PREVOFF(mh) ((size_t)(((size_t)((mh)->mh_prevblock))<<MBLOCKSHIFT))
126 #define M_NEXT(mh) ((struct mheader *)(((char*)(mh))+M_NEXTOFF(mh)))
127 #define M_PREV(mh) ((struct mheader *)(((char*)(mh))-M_PREVOFF(mh)))
128
129 #define M_DATA(mh) ((void *)((mh)+1))
130 #define M_SIZE(mh) (M_NEXTOFF(mh)-MBLOCKSIZE)
131
132 #define M_OK(mh) ((mh)->mh_magic1==MMAGIC && (mh)->mh_magic2==MMAGIC)
133
134 #define M_MKFIELD(off) ((off)>>MBLOCKSHIFT)
135
136 ////////////////////////////////////////////////////////////
137
138 /*
139 * Static variables - the bottom and top addresses of the heap.
140 */
141 static uintptr_t __heapbase, __heaptop;
142
143 /*
144 * Setup function.
145 */
146 static
147 void
148 __malloc_init(void)
149 {
150 void *x;
151
152 /*
153 * Check various assumed properties of the sizes.
154 */
155 if (sizeof(struct mheader) != MBLOCKSIZE) {
156 errx(1, "malloc: Internal error - MBLOCKSIZE wrong");
157 }
158 if ((MBLOCKSIZE & (MBLOCKSIZE-1))!=0) {
159 errx(1, "malloc: Internal error - MBLOCKSIZE not power of 2");
160 }
161 if (1<<MBLOCKSHIFT != MBLOCKSIZE) {
162 errx(1, "malloc: Internal error - MBLOCKSHIFT wrong");
163 }
164
165 /* init should only be called once. */
166 if (__heapbase!=0 || __heaptop!=0) {
167 errx(1, "malloc: Internal error - bad init call");
168 }
169
170 /* Use sbrk to find the base of the heap. */
171 x = sbrk(0);
172 if (x==(void *)-1) {
173 err(1, "malloc: initial sbrk failed");
174 }
175 if (x==(void *) 0) {
176 errx(1, "malloc: Internal error - heap began at 0");
177 }
178 __heapbase = __heaptop = (uintptr_t)x;
179
180 /*
181 * Make sure the heap base is aligned the way we want it.
182 * (On OS/161, it will begin on a page boundary. But on
183 * an arbitrary Unix, it may not be, as traditionally it
184 * begins at _end.)
185 */
186
187 if (__heapbase % MBLOCKSIZE != 0) {
188 size_t adjust = MBLOCKSIZE - (__heapbase % MBLOCKSIZE);
189 x = sbrk(adjust);
190 if (x==(void *)-1) {
191 err(1, "malloc: sbrk failed aligning heap base");
192 }
193 if ((uintptr_t)x != __heapbase) {
194 err(1, "malloc: heap base moved during init");
195 }
196 #ifdef MALLOCDEBUG
197 warnx("malloc: adjusted heap base upwards by %lu bytes",
198 (unsigned long) adjust);
199 #endif
200 __heapbase += adjust;
201 __heaptop = __heapbase;
202 }
203 }
204
205 ////////////////////////////////////////////////////////////
206
207 #ifdef MALLOCDEBUG
208
209 /*
210 * Debugging print function to iterate and dump the entire heap.
211 */
212 static
213 void
214 __malloc_dump(void)
215 {
216 struct mheader *mh;
217 uintptr_t i;
218 size_t rightprevblock;
219
220 warnx("heap: ************************************************");
221
222 rightprevblock = 0;
223 for (i=__heapbase; i<__heaptop; i += M_NEXTOFF(mh)) {
224 mh = (struct mheader *) i;
225 if (!M_OK(mh)) {
226 errx(1, "malloc: Heap corrupt; header at 0x%lx"
227 " has bad magic bits",
228 (unsigned long) i);
229 }
230 if (mh->mh_prevblock != rightprevblock) {
231 errx(1, "malloc: Heap corrupt; header at 0x%lx"
232 " has bad previous-block size %lu "
233 "(should be %lu)",
234 (unsigned long) i,
235 (unsigned long) mh->mh_prevblock << MBLOCKSHIFT,
236 (unsigned long) rightprevblock << MBLOCKSHIFT);
237 }
238 rightprevblock = mh->mh_nextblock;
239
240 warnx("heap: 0x%lx 0x%-6lx (next: 0x%lx) %s",
241 (unsigned long) i + MBLOCKSIZE,
242 (unsigned long) M_SIZE(mh),
243 (unsigned long) (i+M_NEXTOFF(mh)),
244 mh->mh_inuse ? "INUSE" : "FREE");
245 }
246 if (i!=__heaptop) {
247 errx(1, "malloc: Heap corrupt; ran off end");
248 }
249
250 warnx("heap: ************************************************");
251 }
252
253 #endif /* MALLOCDEBUG */
254
255 ////////////////////////////////////////////////////////////
256
257 /*
258 * Get more memory (at the top of the heap) using sbrk, and
259 * return a pointer to it.
260 */
261 static
262 void *
263 __malloc_sbrk(size_t size)
264 {
265 void *x;
266
267 x = sbrk(size);
268 if (x == (void *)-1) {
269 return NULL;
270 }
271
272 if ((uintptr_t)x != __heaptop) {
273 errx(1, "malloc: Internal error - "
274 "heap top moved itself from 0x%lx to 0x%lx",
275 (unsigned long) __heaptop,
276 (unsigned long) (uintptr_t) x);
277 }
278 __heaptop += size;
279 return x;
280 }
281
282 /*
283 * Make a new (free) block from the block passed in, leaving size
284 * bytes for data in the current block. size must be a multiple of
285 * MBLOCKSIZE.
286 *
287 * Only split if the excess space is at least twice the blocksize -
288 * one blocksize to hold a header and one for data.
289 */
290 static
291 void
292 __malloc_split(struct mheader *mh, size_t size)
293 {
294 struct mheader *mhnext, *mhnew;
295 size_t oldsize;
296
297 if (size % MBLOCKSIZE != 0) {
298 errx(1, "malloc: Internal error (size %lu passed to split)",
299 (unsigned long) size);
300 }
301
302 if (M_SIZE(mh) - size < 2*MBLOCKSIZE) {
303 /* no room */
304 return;
305 }
306
307 mhnext = M_NEXT(mh);
308
309 oldsize = M_SIZE(mh);
310 mh->mh_nextblock = M_MKFIELD(size + MBLOCKSIZE);
311
312 mhnew = M_NEXT(mh);
313 if (mhnew==mhnext) {
314 errx(1, "malloc: Internal error (split screwed up?)");
315 }
316
317 mhnew->mh_prevblock = M_MKFIELD(size + MBLOCKSIZE);
318 mhnew->mh_pad = 0;
319 mhnew->mh_magic1 = MMAGIC;
320 mhnew->mh_nextblock = M_MKFIELD(oldsize - size);
321 mhnew->mh_inuse = 0;
322 mhnew->mh_magic2 = MMAGIC;
323
324 if (mhnext != (struct mheader *) __heaptop) {
325 mhnext->mh_prevblock = mhnew->mh_nextblock;
326 }
327 }
328
329 /*
330 * malloc itself.
331 */
332 void *
333 malloc(size_t size)
334 {
335 struct mheader *mh;
336 uintptr_t i;
337 size_t rightprevblock;
338
339 if (__heapbase==0) {
340 __malloc_init();
341 }
342 if (__heapbase==0 || __heaptop==0 || __heapbase > __heaptop) {
343 warnx("malloc: Internal error - local data corrupt");
344 errx(1, "malloc: heapbase 0x%lx; heaptop 0x%lx",
345 (unsigned long) __heapbase, (unsigned long) __heaptop);
346 }
347
348 #ifdef MALLOCDEBUG
349 warnx("malloc: about to allocate %lu (0x%lx) bytes",
350 (unsigned long) size, (unsigned long) size);
351 __malloc_dump();
352 #endif
353
354 /* Round size up to an integral number of blocks. */
355 size = ((size + MBLOCKSIZE - 1) & ~(size_t)(MBLOCKSIZE-1));
356
357 /*
358 * First-fit search algorithm for available blocks.
359 * Check to make sure the next/previous sizes all agree.
360 */
361 rightprevblock = 0;
362 for (i=__heapbase; i<__heaptop; i += M_NEXTOFF(mh)) {
363 mh = (struct mheader *) i;
364 if (!M_OK(mh)) {
365 errx(1, "malloc: Heap corrupt; header at 0x%lx"
366 " has bad magic bits",
367 (unsigned long) i);
368 }
369 if (mh->mh_prevblock != rightprevblock) {
370 errx(1, "malloc: Heap corrupt; header at 0x%lx"
371 " has bad previous-block size %lu "
372 "(should be %lu)",
373 (unsigned long) i,
374 (unsigned long) mh->mh_prevblock << MBLOCKSHIFT,
375 (unsigned long) rightprevblock << MBLOCKSHIFT);
376 }
377 rightprevblock = mh->mh_nextblock;
378
379 /* Can't allocate a block that's in use. */
380 if (mh->mh_inuse) {
381 continue;
382 }
383
384 /* Can't allocate a block that isn't big enough. */
385 if (M_SIZE(mh) < size) {
386 continue;
387 }
388
389 /* Try splitting block. */
390 __malloc_split(mh, size);
391
392 /*
393 * Now, allocate.
394 */
395 mh->mh_inuse = 1;
396
397 #ifdef MALLOCDEBUG
398 warnx("malloc: allocating at %p", M_DATA(mh));
399 __malloc_dump();
400 #endif
401 return M_DATA(mh);
402 }
403 if (i!=__heaptop) {
404 errx(1, "malloc: Heap corrupt; ran off end");
405 }
406
407 /*
408 * Didn't find anything. Expand the heap.
409 */
410
411 mh = __malloc_sbrk(size + MBLOCKSIZE);
412 if (mh == NULL) {
413 return NULL;
414 }
415
416 mh->mh_prevblock = rightprevblock;
417 mh->mh_magic1 = MMAGIC;
418 mh->mh_magic2 = MMAGIC;
419 mh->mh_pad = 0;
420 mh->mh_inuse = 1;
421 mh->mh_nextblock = M_MKFIELD(size + MBLOCKSIZE);
422
423 #ifdef MALLOCDEBUG
424 warnx("malloc: allocating at %p", M_DATA(mh));
425 __malloc_dump();
426 #endif
427 return M_DATA(mh);
428 }
429
430 ////////////////////////////////////////////////////////////
431
432 /*
433 * Clear a range of memory with 0xdeadbeef.
434 * ptr must be suitably aligned.
435 */
436 static
437 void
438 __malloc_deadbeef(void *ptr, size_t size)
439 {
440 uint32_t *x = ptr;
441 size_t i, n = size/sizeof(uint32_t);
442 for (i=0; i<n; i++) {
443 x[i] = 0xdeadbeef;
444 }
445 }
446
447 /*
448 * Attempt to merge two adjacent blocks (mh below mhnext).
449 */
450 static
451 void
452 __malloc_trymerge(struct mheader *mh, struct mheader *mhnext)
453 {
454 struct mheader *mhnextnext;
455
456 if (mh->mh_nextblock != mhnext->mh_prevblock) {
457 errx(1, "free: Heap corrupt (%p and %p inconsistent)",
458 mh, mhnext);
459 }
460 if (mh->mh_inuse || mhnext->mh_inuse) {
461 /* can't merge */
462 return;
463 }
464
465 mhnextnext = M_NEXT(mhnext);
466
467 mh->mh_nextblock = M_MKFIELD(MBLOCKSIZE + M_SIZE(mh) +
468 MBLOCKSIZE + M_SIZE(mhnext));
469
470 if (mhnextnext != (struct mheader *)__heaptop) {
471 mhnextnext->mh_prevblock = mh->mh_nextblock;
472 }
473
474 /* Deadbeef out the memory used by the now-obsolete header */
475 __malloc_deadbeef(mhnext, sizeof(struct mheader));
476 }
477
478 /*
479 * The actual free() implementation.
480 */
481 void
482 free(void *x)
483 {
484 struct mheader *mh, *mhnext, *mhprev;
485
486 if (x==NULL) {
487 /* safest practice */
488 return;
489 }
490
491 /* Consistency check. */
492 if (__heapbase==0 || __heaptop==0 || __heapbase > __heaptop) {
493 warnx("free: Internal error - local data corrupt");
494 errx(1, "free: heapbase 0x%lx; heaptop 0x%lx",
495 (unsigned long) __heapbase, (unsigned long) __heaptop);
496 }
497
498 /* Don't allow freeing pointers that aren't on the heap. */
499 if ((uintptr_t)x < __heapbase || (uintptr_t)x >= __heaptop) {
500 errx(1, "free: Invalid pointer %p freed (out of range)", x);
501 }
502
503 #ifdef MALLOCDEBUG
504 warnx("free: about to free %p", x);
505 __malloc_dump();
506 #endif
507
508 mh = ((struct mheader *)x)-1;
509 if (!M_OK(mh)) {
510 errx(1, "free: Invalid pointer %p freed (corrupt header)", x);
511 }
512
513 if (!mh->mh_inuse) {
514 errx(1, "free: Invalid pointer %p freed (already free)", x);
515 }
516
517 /* mark it free */
518 mh->mh_inuse = 0;
519
520 /* wipe it */
521 __malloc_deadbeef(M_DATA(mh), M_SIZE(mh));
522
523 /* Try merging with the block above (but not if we're at the top) */
524 mhnext = M_NEXT(mh);
525 if (mhnext != (struct mheader *)__heaptop) {
526 __malloc_trymerge(mh, mhnext);
527 }
528
529 /* Try merging with the block below (but not if we're at the bottom) */
530 if (mh != (struct mheader *)__heapbase) {
531 mhprev = M_PREV(mh);
532 __malloc_trymerge(mhprev, mh);
533 }
534
535 #ifdef MALLOCDEBUG
536 warnx("free: freed %p", x);
537 __malloc_dump();
538 #endif
539 }