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