1 /* Copyright (c) 2002 Geoffrey Keating <geoffk@geoffk.org> */
2 /* A replacement malloc with:
3 - Much reduced code size;
4 - Smaller RAM footprint;
5 - The ability to handle downward-growing heaps;
6 but
7 - Slower;
8 - Probably higher memory fragmentation;
9 - Doesn't support threads (but, if it did support threads,
10 it wouldn't need a global lock, only a compare-and-swap instruction);
11 - Assumes the maximum alignment required is the alignment of a pointer;
12 - Assumes that memory is already there and doesn't need to be allocated.
13
14 * Synopsis of public routines
15
16 malloc(size_t n);
17 Return a pointer to a newly allocated chunk of at least n bytes, or null
18 if no space is available.
19 free(void* p);
20 Release the chunk of memory pointed to by p, or no effect if p is null.
21 realloc(void* p, size_t n);
22 Return a pointer to a chunk of size n that contains the same data
23 as does chunk p up to the minimum of (n, p's size) bytes, or null
24 if no space is available. The returned pointer may or may not be
25 the same as p. If p is null, equivalent to malloc. Unless the
26 #define REALLOC_ZERO_BYTES_FREES below is set, realloc with a
27 size argument of zero (re)allocates a minimum-sized chunk.
28 memalign(size_t alignment, size_t n);
29 Return a pointer to a newly allocated chunk of n bytes, aligned
30 in accord with the alignment argument, which must be a power of
31 two. Will fail if 'alignment' is too large.
32 calloc(size_t unit, size_t quantity);
33 Returns a pointer to quantity * unit bytes, with all locations
34 set to zero.
35 cfree(void* p);
36 Equivalent to free(p).
37 malloc_trim(size_t pad);
38 Release all but pad bytes of freed top-most memory back
39 to the system. Return 1 if successful, else 0.
40 malloc_usable_size(void* p);
41 Report the number usable allocated bytes associated with allocated
42 chunk p. This may or may not report more bytes than were requested,
43 due to alignment and minimum size constraints.
44 malloc_stats();
45 Prints brief summary statistics on stderr.
46 mallinfo()
47 Returns (by copy) a struct containing various summary statistics.
48 mallopt(int parameter_number, int parameter_value)
49 Changes one of the tunable parameters described below. Returns
50 1 if successful in changing the parameter, else 0. Actually, returns 0
51 always, as no parameter can be changed.
52 */
53
54 #ifdef __xstormy16__
55 #define MALLOC_DIRECTION -1
56 #endif
57
58 #ifndef MALLOC_DIRECTION
59 #define MALLOC_DIRECTION 1
60 #endif
61
62 #include <stddef.h>
63
64 void* malloc(size_t);
65 void free(void*);
66 void* realloc(void*, size_t);
67 void* memalign(size_t, size_t);
68 void* valloc(size_t);
69 void* pvalloc(size_t);
70 void* calloc(size_t, size_t);
71 void cfree(void*);
72 int malloc_trim(size_t);
73 size_t malloc_usable_size(void*);
74 void malloc_stats(void);
75 int mallopt(int, int);
76 struct mallinfo mallinfo(void);
77
78 typedef struct freelist_entry {
79 size_t size;
80 struct freelist_entry *next;
81 } *fle;
82
83 extern void * __malloc_end;
84 extern fle __malloc_freelist;
85
86 /* Return the number of bytes that need to be added to X to make it
87 aligned to an ALIGN boundary. ALIGN must be a power of 2. */
88 #define M_ALIGN(x, align) (-(size_t)(x) & ((align) - 1))
89
90 /* Return the number of bytes that need to be subtracted from X to make it
91 aligned to an ALIGN boundary. ALIGN must be a power of 2. */
92 #define M_ALIGN_SUB(x, align) ((size_t)(x) & ((align) - 1))
93
94 extern void __malloc_start;
95
96 /* This is the minimum gap allowed between __malloc_end and the top of
97 the stack. This is only checked for when __malloc_end is
98 decreased; if instead the stack grows into the heap, silent data
99 corruption will result. */
100 #define MALLOC_MINIMUM_GAP 32
101
102 #ifdef __xstormy16__
103 register void * stack_pointer __asm__("r15");
104 #define MALLOC_LIMIT stack_pointer
105 #else
106 #define MALLOC_LIMIT __builtin_frame_address (0)
107 #endif
108
109 #if MALLOC_DIRECTION < 0
110 #define CAN_ALLOC_P(required) \
111 (((size_t) __malloc_end - (size_t)MALLOC_LIMIT \
112 - MALLOC_MINIMUM_GAP) >= (required))
113 #else
114 #define CAN_ALLOC_P(required) \
115 (((size_t)MALLOC_LIMIT - (size_t) __malloc_end \
116 - MALLOC_MINIMUM_GAP) >= (required))
117 #endif
118
119 /* real_size is the size we actually have to allocate, allowing for
120 overhead and alignment. */
121 #define REAL_SIZE(sz) \
122 ((sz) < sizeof (struct freelist_entry) - sizeof (size_t) \
123 ? sizeof (struct freelist_entry) \
124 : sz + sizeof (size_t) + M_ALIGN(sz, sizeof (size_t)))
125
126 #ifdef DEFINE_MALLOC
127
128 void * __malloc_end = &__malloc_start;
129 fle __malloc_freelist;
130
131 void *
malloc(size_t sz)132 malloc (size_t sz)
133 {
134 fle *nextfree;
135 fle block;
136
137 /* real_size is the size we actually have to allocate, allowing for
138 overhead and alignment. */
139 size_t real_size = REAL_SIZE (sz);
140
141 /* Look for the first block on the freelist that is large enough. */
142 for (nextfree = &__malloc_freelist;
143 *nextfree;
144 nextfree = &(*nextfree)->next)
145 {
146 block = *nextfree;
147
148 if (block->size >= real_size)
149 {
150 /* If the block found is just the right size, remove it from
151 the free list. Otherwise, split it. */
152 if (block->size < real_size + sizeof (struct freelist_entry))
153 {
154 *nextfree = block->next;
155 return (void *)&block->next;
156 }
157 else
158 {
159 size_t newsize = block->size - real_size;
160 fle newnext = block->next;
161 *nextfree = (fle)((size_t)block + real_size);
162 (*nextfree)->size = newsize;
163 (*nextfree)->next = newnext;
164 goto done;
165 }
166 }
167
168 /* If this is the last block on the freelist, and it was too small,
169 enlarge it. */
170 if (! block->next
171 && __malloc_end == (void *)((size_t)block + block->size))
172 {
173 size_t moresize = real_size - block->size;
174 if (! CAN_ALLOC_P (moresize))
175 return NULL;
176
177 *nextfree = NULL;
178 if (MALLOC_DIRECTION < 0)
179 {
180 block = __malloc_end = (void *)((size_t)block - moresize);
181 }
182 else
183 {
184 __malloc_end = (void *)((size_t)block + real_size);
185 }
186
187 goto done;
188 }
189 }
190
191 /* No free space at the end of the free list. Allocate new space
192 and use that. */
193
194 if (! CAN_ALLOC_P (real_size))
195 return NULL;
196
197 if (MALLOC_DIRECTION > 0)
198 {
199 block = __malloc_end;
200 __malloc_end = (void *)((size_t)__malloc_end + real_size);
201 }
202 else
203 {
204 block = __malloc_end = (void *)((size_t)__malloc_end - real_size);
205 }
206 done:
207 block->size = real_size;
208 return (void *)&block->next;
209 }
210
211 #endif
212
213 #ifdef DEFINE_FREE
214
215 void
free(void * block_p)216 free (void *block_p)
217 {
218 fle *nextfree;
219 fle block = (fle)((size_t) block_p - offsetof (struct freelist_entry, next));
220
221 if (block_p == NULL)
222 return;
223
224 /* Look on the freelist to see if there's a free block just before
225 or just after this block. */
226 for (nextfree = &__malloc_freelist;
227 *nextfree;
228 nextfree = &(*nextfree)->next)
229 {
230 fle thisblock = *nextfree;
231 if ((size_t)thisblock + thisblock->size == (size_t) block)
232 {
233 thisblock->size += block->size;
234 if (MALLOC_DIRECTION > 0
235 && thisblock->next
236 && (size_t) block + block->size == (size_t) thisblock->next)
237 {
238 thisblock->size += thisblock->next->size;
239 thisblock->next = thisblock->next->next;
240 }
241 return;
242 }
243 else if ((size_t) thisblock == (size_t) block + block->size)
244 {
245 if (MALLOC_DIRECTION < 0
246 && thisblock->next
247 && (size_t) block == ((size_t) thisblock->next
248 + thisblock->next->size))
249 {
250 *nextfree = thisblock->next;
251 thisblock->next->size += block->size + thisblock->size;
252 }
253 else
254 {
255 block->size += thisblock->size;
256 block->next = thisblock->next;
257 *nextfree = block;
258 }
259 return;
260 }
261 else if ((MALLOC_DIRECTION > 0
262 && (size_t) thisblock > (size_t) block)
263 || (MALLOC_DIRECTION < 0
264 && (size_t) thisblock < (size_t) block))
265 break;
266 }
267
268 block->next = *nextfree;
269 *nextfree = block;
270 return;
271 }
272 #endif
273
274 #ifdef DEFINE_REALLOC
275 #include <string.h>
276
277 void *
realloc(void * block_p,size_t sz)278 realloc (void *block_p, size_t sz)
279 {
280 fle block = (fle)((size_t) block_p - offsetof (struct freelist_entry, next));
281 size_t real_size = REAL_SIZE (sz);
282 size_t old_real_size;
283
284 if (block_p == NULL)
285 return malloc (sz);
286
287 old_real_size = block->size;
288
289 /* Perhaps we need to allocate more space. */
290 if (old_real_size < real_size)
291 {
292 void *result;
293 size_t old_size = old_real_size - sizeof (size_t);
294
295 /* Need to allocate, copy, and free. */
296 result = malloc (sz);
297 if (result == NULL)
298 return NULL;
299 memcpy (result, block_p, old_size < sz ? old_size : sz);
300 free (block_p);
301 return result;
302 }
303 /* Perhaps we can free some space. */
304 if (old_real_size - real_size >= sizeof (struct freelist_entry))
305 {
306 fle newblock = (fle)((size_t)block + real_size);
307 block->size = real_size;
308 newblock->size = old_real_size - real_size;
309 free (&newblock->next);
310 }
311 return block_p;
312 }
313 #endif
314
315 #ifdef DEFINE_CALLOC
316 #include <string.h>
317
318 void *
calloc(size_t n,size_t elem_size)319 calloc (size_t n, size_t elem_size)
320 {
321 void *result;
322 size_t sz = n * elem_size;
323 result = malloc (sz);
324 if (result != NULL)
325 memset (result, 0, sz);
326 return result;
327 }
328 #endif
329
330 #ifdef DEFINE_CFREE
331 void
cfree(void * p)332 cfree (void *p)
333 {
334 free (p);
335 }
336 #endif
337
338 #ifdef DEFINE_MEMALIGN
339 void *
memalign(size_t align,size_t sz)340 memalign (size_t align, size_t sz)
341 {
342 fle *nextfree;
343 fle block;
344
345 /* real_size is the size we actually have to allocate, allowing for
346 overhead and alignment. */
347 size_t real_size = REAL_SIZE (sz);
348
349 /* Some sanity checking on 'align'. */
350 if ((align & (align - 1)) != 0
351 || align <= 0)
352 return NULL;
353
354 /* Look for the first block on the freelist that is large enough. */
355 /* One tricky part is this: We want the result to be a valid pointer
356 to free. That means that there has to be room for a size_t
357 before the block. If there's additional space before the block,
358 it should go on the freelist, or it'll be lost---we could add it
359 to the size of the block before it in memory, but finding the
360 previous block is expensive. */
361 for (nextfree = &__malloc_freelist;
362 ;
363 nextfree = &(*nextfree)->next)
364 {
365 size_t before_size;
366 size_t old_size;
367
368 /* If we've run out of free blocks, allocate more space. */
369 if (! *nextfree)
370 {
371 old_size = real_size;
372 if (MALLOC_DIRECTION < 0)
373 {
374 old_size += M_ALIGN_SUB (((size_t)__malloc_end
375 - old_size + sizeof (size_t)),
376 align);
377 if (! CAN_ALLOC_P (old_size))
378 return NULL;
379 block = __malloc_end = (void *)((size_t)__malloc_end - old_size);
380 }
381 else
382 {
383 block = __malloc_end;
384 old_size += M_ALIGN ((size_t)__malloc_end + sizeof (size_t),
385 align);
386 if (! CAN_ALLOC_P (old_size))
387 return NULL;
388 __malloc_end = (void *)((size_t)__malloc_end + old_size);
389 }
390 *nextfree = block;
391 block->size = old_size;
392 block->next = NULL;
393 }
394 else
395 {
396 block = *nextfree;
397 old_size = block->size;
398 }
399
400
401 before_size = M_ALIGN (&block->next, align);
402 if (before_size != 0)
403 before_size = sizeof (*block) + M_ALIGN (&(block+1)->next, align);
404
405 /* If this is the last block on the freelist, and it is too small,
406 enlarge it. */
407 if (! block->next
408 && old_size < real_size + before_size
409 && __malloc_end == (void *)((size_t)block + block->size))
410 {
411 if (MALLOC_DIRECTION < 0)
412 {
413 size_t moresize = real_size - block->size;
414 moresize += M_ALIGN_SUB ((size_t)&block->next - moresize, align);
415 if (! CAN_ALLOC_P (moresize))
416 return NULL;
417 block = __malloc_end = (void *)((size_t)block - moresize);
418 block->next = NULL;
419 block->size = old_size = old_size + moresize;
420 before_size = 0;
421 }
422 else
423 {
424 if (! CAN_ALLOC_P (before_size + real_size - block->size))
425 return NULL;
426 __malloc_end = (void *)((size_t)block + before_size + real_size);
427 block->size = old_size = before_size + real_size;
428 }
429
430 /* Two out of the four cases below will now be possible; which
431 two depends on MALLOC_DIRECTION. */
432 }
433
434 if (old_size >= real_size + before_size)
435 {
436 /* This block will do. If there needs to be space before it,
437 split the block. */
438 if (before_size != 0)
439 {
440 fle old_block = block;
441
442 old_block->size = before_size;
443 block = (fle)((size_t)block + before_size);
444
445 /* If there's no space after the block, we're now nearly
446 done; just make a note of the size required.
447 Otherwise, we need to create a new free space block. */
448 if (old_size - before_size
449 <= real_size + sizeof (struct freelist_entry))
450 {
451 block->size = old_size - before_size;
452 return (void *)&block->next;
453 }
454 else
455 {
456 fle new_block;
457 new_block = (fle)((size_t)block + real_size);
458 new_block->size = old_size - before_size - real_size;
459 if (MALLOC_DIRECTION > 0)
460 {
461 new_block->next = old_block->next;
462 old_block->next = new_block;
463 }
464 else
465 {
466 new_block->next = old_block;
467 *nextfree = new_block;
468 }
469 goto done;
470 }
471 }
472 else
473 {
474 /* If the block found is just the right size, remove it from
475 the free list. Otherwise, split it. */
476 if (old_size <= real_size + sizeof (struct freelist_entry))
477 {
478 *nextfree = block->next;
479 return (void *)&block->next;
480 }
481 else
482 {
483 size_t newsize = old_size - real_size;
484 fle newnext = block->next;
485 *nextfree = (fle)((size_t)block + real_size);
486 (*nextfree)->size = newsize;
487 (*nextfree)->next = newnext;
488 goto done;
489 }
490 }
491 }
492 }
493
494 done:
495 block->size = real_size;
496 return (void *)&block->next;
497 }
498 #endif
499
500 #ifdef DEFINE_VALLOC
501 void *
valloc(size_t sz)502 valloc (size_t sz)
503 {
504 return memalign (128, sz);
505 }
506 #endif
507 #ifdef DEFINE_PVALLOC
508 void *
pvalloc(size_t sz)509 pvalloc (size_t sz)
510 {
511 return memalign (128, sz + M_ALIGN (sz, 128));
512 }
513 #endif
514
515 #ifdef DEFINE_MALLINFO
516 #include "malloc.h"
517 #include <string.h>
518
519 struct mallinfo
mallinfo(void)520 mallinfo (void)
521 {
522 struct mallinfo r;
523 fle fr;
524 size_t free_size;
525 size_t total_size;
526 size_t free_blocks;
527
528 memset (&r, 0, sizeof (r));
529
530 free_size = 0;
531 free_blocks = 0;
532 for (fr = __malloc_freelist; fr; fr = fr->next)
533 {
534 free_size += fr->size;
535 free_blocks++;
536 if (! fr->next)
537 {
538 int atend;
539 if (MALLOC_DIRECTION > 0)
540 atend = (void *)((size_t)fr + fr->size) == __malloc_end;
541 else
542 atend = (void *)fr == __malloc_end;
543 if (atend)
544 r.keepcost = fr->size;
545 }
546 }
547
548 if (MALLOC_DIRECTION > 0)
549 total_size = (char *)__malloc_end - (char *)&__malloc_start;
550 else
551 total_size = (char *)&__malloc_start - (char *)__malloc_end;
552
553 #ifdef DEBUG
554 /* Fixme: should walk through all the in-use blocks and see if
555 they're valid. */
556 #endif
557
558 r.arena = total_size;
559 r.fordblks = free_size;
560 r.uordblks = total_size - free_size;
561 r.ordblks = free_blocks;
562 return r;
563 }
564 #endif
565
566 #ifdef DEFINE_MALLOC_STATS
567 #include "malloc.h"
568 #include <stdio.h>
569
570 void
malloc_stats(void)571 malloc_stats(void)
572 {
573 struct mallinfo i;
574 FILE *fp;
575
576 fp = stderr;
577 i = mallinfo();
578 fprintf (fp, "malloc has reserved %u bytes between %p and %p\n",
579 i.arena, &__malloc_start, __malloc_end);
580 fprintf (fp, "there are %u bytes free in %u chunks\n",
581 i.fordblks, i.ordblks);
582 fprintf (fp, "of which %u bytes are at the end of the reserved space\n",
583 i.keepcost);
584 fprintf (fp, "and %u bytes are in use.\n", i.uordblks);
585 }
586 #endif
587
588 #ifdef DEFINE_MALLOC_USABLE_SIZE
589 size_t
malloc_usable_size(void * block_p)590 malloc_usable_size (void *block_p)
591 {
592 fle block = (fle)((size_t) block_p - offsetof (struct freelist_entry, next));
593 return block->size - sizeof (size_t);
594 }
595 #endif
596
597 #ifdef DEFINE_MALLOPT
598 int
mallopt(int n,int v)599 mallopt (int n, int v)
600 {
601 (void)n; (void)v;
602 return 0;
603 }
604 #endif
605
