1 /*
2 * Copyright (c) 2012, 2013 ARM Ltd
3 * All rights reserved.
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. The name of the company may not be used to endorse or promote
14 * products derived from this software without specific prior written
15 * permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY ARM LTD ``AS IS'' AND ANY EXPRESS OR IMPLIED
18 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
19 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL ARM LTD BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
22 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
23 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
24 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
25 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 /* Implementation of <<malloc>> <<free>> <<calloc>> <<realloc>>, optional
30 * as to be reenterable.
31 *
32 * Interface documentation refer to malloc.c.
33 */
34
35 #include <stdio.h>
36 #include <string.h>
37 #include <errno.h>
38
39 #if DEBUG
40 #include <assert.h>
41 #else
42 #define assert(x) ((void)0)
43 #endif
44
45 #ifndef MAX
46 #define MAX(a,b) ((a) >= (b) ? (a) : (b))
47 #endif
48
49 #define _SBRK_R(X) _sbrk_r(X)
50
51 #ifdef INTERNAL_NEWLIB
52
53 #include <sys/config.h>
54 #include <reent.h>
55
56 #define RARG struct _reent *reent_ptr,
57 #define RONEARG struct _reent *reent_ptr
58 #define RCALL reent_ptr,
59 #define RONECALL reent_ptr
60
61 /* Disable MALLOC_LOCK so far. So it won't be thread safe */
62 #define MALLOC_LOCK /*__malloc_lock(reent_ptr) */
63 #define MALLOC_UNLOCK /*__malloc_unlock(reent_ptr) */
64
65 #define RERRNO reent_ptr->_errno
66
67 #define nano_malloc _malloc_r
68 #define nano_free _free_r
69 #define nano_realloc _realloc_r
70 #define nano_memalign _memalign_r
71 #define nano_valloc _valloc_r
72 #define nano_pvalloc _pvalloc_r
73 #define nano_calloc _calloc_r
74 #define nano_cfree _cfree_r
75 #define nano_malloc_usable_size _malloc_usable_size_r
76 #define nano_malloc_stats _malloc_stats_r
77 #define nano_mallinfo _mallinfo_r
78 #define nano_mallopt _mallopt_r
79
80 #else /* ! INTERNAL_NEWLIB */
81
82 #define RARG
83 #define RONEARG
84 #define RCALL
85 #define RONECALL
86 #define MALLOC_LOCK
87 #define MALLOC_UNLOCK
88 #define RERRNO errno
89
90 #define nano_malloc malloc
91 #define nano_free free
92 #define nano_realloc realloc
93 #define nano_memalign memalign
94 #define nano_valloc valloc
95 #define nano_pvalloc pvalloc
96 #define nano_calloc calloc
97 #define nano_cfree cfree
98 #define nano_malloc_usable_size malloc_usable_size
99 #define nano_malloc_stats malloc_stats
100 #define nano_mallinfo mallinfo
101 #define nano_mallopt mallopt
102 #endif /* ! INTERNAL_NEWLIB */
103
104 /* Redefine names to avoid conflict with user names */
105 #define free_list __malloc_free_list
106 #define sbrk_start __malloc_sbrk_start
107 #define current_mallinfo __malloc_current_mallinfo
108
109 #define ALIGN_TO(size, align) \
110 (((size) + (align) -1L) & ~((align) -1L))
111
112 /* Alignment of allocated block */
113 #define MALLOC_ALIGN (8U)
114 #define CHUNK_ALIGN (sizeof(void*))
115 #define MALLOC_PADDING ((MAX(MALLOC_ALIGN, CHUNK_ALIGN)) - CHUNK_ALIGN)
116
117 /* as well as the minimal allocation size
118 * to hold a free pointer */
119 #define MALLOC_MINSIZE (sizeof(void *))
120 #define MALLOC_PAGE_ALIGN (0x1000)
121 #define MAX_ALLOC_SIZE (0x80000000U)
122
123 typedef size_t malloc_size_t;
124
125 typedef struct malloc_chunk
126 {
127 /* ------------------
128 * chunk->| size (4 bytes) |
129 * ------------------
130 * | Padding for |
131 * | alignment |
132 * | holding neg |
133 * | offset to size |
134 * ------------------
135 * mem_ptr->| point to next |
136 * | free when freed|
137 * | or data load |
138 * | when allocated |
139 * ------------------
140 */
141 /* size of the allocated payload area, including size before
142 CHUNK_OFFSET */
143 long size;
144
145 /* since here, the memory is either the next free block, or data load */
146 struct malloc_chunk * next;
147 }chunk;
148
149 /* Copied from malloc.h */
150 struct mallinfo
151 {
152 size_t arena; /* total space allocated from system */
153 size_t ordblks; /* number of non-inuse chunks */
154 size_t smblks; /* unused -- always zero */
155 size_t hblks; /* number of mmapped regions */
156 size_t hblkhd; /* total space in mmapped regions */
157 size_t usmblks; /* unused -- always zero */
158 size_t fsmblks; /* unused -- always zero */
159 size_t uordblks; /* total allocated space */
160 size_t fordblks; /* total non-inuse space */
161 size_t keepcost; /* top-most, releasable (via malloc_trim) space */
162 };
163
164 #define CHUNK_OFFSET ((malloc_size_t)(&(((struct malloc_chunk *)0)->next)))
165
166 /* size of smallest possible chunk. A memory piece smaller than this size
167 * won't be able to create a chunk */
168 #define MALLOC_MINCHUNK (CHUNK_OFFSET + MALLOC_PADDING + MALLOC_MINSIZE)
169
170 /* Forward data declarations */
171 extern chunk * free_list;
172 extern char * sbrk_start;
173 extern struct mallinfo current_mallinfo;
174
175 /* Forward function declarations */
176 extern void * nano_malloc(RARG malloc_size_t);
177 extern void nano_free (RARG void * free_p);
178 extern void nano_cfree(RARG void * ptr);
179 extern void * nano_calloc(RARG malloc_size_t n, malloc_size_t elem);
180 extern struct mallinfo nano_mallinfo(RONEARG);
181 extern void nano_malloc_stats(RONEARG);
182 extern malloc_size_t nano_malloc_usable_size(RARG void * ptr);
183 extern void * nano_realloc(RARG void * ptr, malloc_size_t size);
184 extern void * nano_memalign(RARG size_t align, size_t s);
185 extern int nano_mallopt(RARG int parameter_number, int parameter_value);
186 extern void * nano_valloc(RARG size_t s);
187 extern void * nano_pvalloc(RARG size_t s);
188
get_chunk_from_ptr(void * ptr)189 static inline chunk * get_chunk_from_ptr(void * ptr)
190 {
191 chunk * c = (chunk *)((char *)ptr - CHUNK_OFFSET);
192 /* Skip the padding area */
193 if (c->size < 0) c = (chunk *)((char *)c + c->size);
194 return c;
195 }
196
197 #ifdef DEFINE_MALLOC
198 /* List list header of free blocks */
199 chunk * free_list = NULL;
200
201 /* Starting point of memory allocated from system */
202 char * sbrk_start = NULL;
203
204 /** Function sbrk_aligned
205 * Algorithm:
206 * Use sbrk() to obtain more memory and ensure it is CHUNK_ALIGN aligned
207 * Optimise for the case that it is already aligned - only ask for extra
208 * padding after we know we need it
209 */
sbrk_aligned(RARG malloc_size_t s)210 static void* sbrk_aligned(RARG malloc_size_t s)
211 {
212 char *p, *align_p;
213
214 if (sbrk_start == NULL) sbrk_start = _SBRK_R(RCALL 0);
215
216 p = _SBRK_R(RCALL s);
217
218 /* sbrk returns -1 if fail to allocate */
219 if (p == (void *)-1)
220 return p;
221
222 align_p = (char*)ALIGN_TO((unsigned long)p, CHUNK_ALIGN);
223 if (align_p != p)
224 {
225 /* p is not aligned, ask for a few more bytes so that we have s
226 * bytes reserved from align_p. */
227 p = _SBRK_R(RCALL align_p - p);
228 if (p == (void *)-1)
229 return p;
230 }
231 return align_p;
232 }
233
234 /** Function nano_malloc
235 * Algorithm:
236 * Walk through the free list to find the first match. If fails to find
237 * one, call sbrk to allocate a new chunk.
238 */
nano_malloc(RARG malloc_size_t s)239 void * nano_malloc(RARG malloc_size_t s)
240 {
241 chunk *p, *r;
242 char * ptr, * align_ptr;
243 int offset;
244
245 malloc_size_t alloc_size;
246
247 alloc_size = ALIGN_TO(s, CHUNK_ALIGN); /* size of aligned data load */
248 alloc_size += MALLOC_PADDING; /* padding */
249 alloc_size += CHUNK_OFFSET; /* size of chunk head */
250 alloc_size = MAX(alloc_size, MALLOC_MINCHUNK);
251
252 if (alloc_size >= MAX_ALLOC_SIZE || alloc_size < s)
253 {
254 RERRNO = ENOMEM;
255 return NULL;
256 }
257
258 MALLOC_LOCK;
259
260 p = free_list;
261 r = p;
262
263 while (r)
264 {
265 int rem = r->size - alloc_size;
266 if (rem >= 0)
267 {
268 if (rem >= MALLOC_MINCHUNK)
269 {
270 /* Find a chunk that much larger than required size, break
271 * it into two chunks and return the second one */
272 r->size = rem;
273 r = (chunk *)((char *)r + rem);
274 r->size = alloc_size;
275 }
276 /* Find a chunk that is exactly the size or slightly bigger
277 * than requested size, just return this chunk */
278 else if (p == r)
279 {
280 /* Now it implies p==r==free_list. Move the free_list
281 * to next chunk */
282 free_list = r->next;
283 }
284 else
285 {
286 /* Normal case. Remove it from free_list */
287 p->next = r->next;
288 }
289 break;
290 }
291 p=r;
292 r=r->next;
293 }
294
295 /* Failed to find a appropriate chunk. Ask for more memory */
296 if (r == NULL)
297 {
298 r = sbrk_aligned(RCALL alloc_size);
299
300 /* sbrk returns -1 if fail to allocate */
301 if (r == (void *)-1)
302 {
303 RERRNO = ENOMEM;
304 MALLOC_UNLOCK;
305 return NULL;
306 }
307 r->size = alloc_size;
308 }
309 MALLOC_UNLOCK;
310
311 ptr = (char *)r + CHUNK_OFFSET;
312
313 align_ptr = (char *)ALIGN_TO((unsigned long)ptr, MALLOC_ALIGN);
314 offset = align_ptr - ptr;
315
316 if (offset)
317 {
318 *(int *)((char *)r + offset) = -offset;
319 }
320
321 assert(align_ptr + size <= (char *)r + alloc_size);
322 return align_ptr;
323 }
324 #endif /* DEFINE_MALLOC */
325
326 #ifdef DEFINE_FREE
327 #define MALLOC_CHECK_DOUBLE_FREE
328
329 /** Function nano_free
330 * Implementation of libc free.
331 * Algorithm:
332 * Maintain a global free chunk single link list, headed by global
333 * variable free_list.
334 * When free, insert the to-be-freed chunk into free list. The place to
335 * insert should make sure all chunks are sorted by address from low to
336 * high. Then merge with neighbor chunks if adjacent.
337 */
nano_free(RARG void * free_p)338 void nano_free (RARG void * free_p)
339 {
340 chunk * p_to_free;
341 chunk * p, * q;
342
343 if (free_p == NULL) return;
344
345 p_to_free = get_chunk_from_ptr(free_p);
346
347 MALLOC_LOCK;
348 if (free_list == NULL)
349 {
350 /* Set first free list element */
351 p_to_free->next = free_list;
352 free_list = p_to_free;
353 MALLOC_UNLOCK;
354 return;
355 }
356
357 if (p_to_free < free_list)
358 {
359 if ((char *)p_to_free + p_to_free->size == (char *)free_list)
360 {
361 /* Chunk to free is just before the first element of
362 * free list */
363 p_to_free->size += free_list->size;
364 p_to_free->next = free_list->next;
365 }
366 else
367 {
368 /* Insert before current free_list */
369 p_to_free->next = free_list;
370 }
371 free_list = p_to_free;
372 MALLOC_UNLOCK;
373 return;
374 }
375
376 q = free_list;
377 /* Walk through the free list to find the place for insert. */
378 do
379 {
380 p = q;
381 q = q->next;
382 } while (q && q <= p_to_free);
383
384 /* Now p <= p_to_free and either q == NULL or q > p_to_free
385 * Try to merge with chunks immediately before/after it. */
386
387 if ((char *)p + p->size == (char *)p_to_free)
388 {
389 /* Chunk to be freed is adjacent
390 * to a free chunk before it */
391 p->size += p_to_free->size;
392 /* If the merged chunk is also adjacent
393 * to the chunk after it, merge again */
394 if ((char *)p + p->size == (char *) q)
395 {
396 p->size += q->size;
397 p->next = q->next;
398 }
399 }
400 #ifdef MALLOC_CHECK_DOUBLE_FREE
401 else if ((char *)p + p->size > (char *)p_to_free)
402 {
403 /* Report double free fault */
404 RERRNO = ENOMEM;
405 MALLOC_UNLOCK;
406 return;
407 }
408 #endif
409 else if ((char *)p_to_free + p_to_free->size == (char *) q)
410 {
411 /* Chunk to be freed is adjacent
412 * to a free chunk after it */
413 p_to_free->size += q->size;
414 p_to_free->next = q->next;
415 p->next = p_to_free;
416 }
417 else
418 {
419 /* Not adjacent to any chunk. Just insert it. Resulting
420 * a fragment. */
421 p_to_free->next = q;
422 p->next = p_to_free;
423 }
424 MALLOC_UNLOCK;
425 }
426 #endif /* DEFINE_FREE */
427
428 #ifdef DEFINE_CFREE
nano_cfree(RARG void * ptr)429 void nano_cfree(RARG void * ptr)
430 {
431 nano_free(RCALL ptr);
432 }
433 #endif /* DEFINE_CFREE */
434
435 #ifdef DEFINE_CALLOC
436 /* Function nano_calloc
437 * Implement calloc simply by calling malloc and set zero */
nano_calloc(RARG malloc_size_t n,malloc_size_t elem)438 void * nano_calloc(RARG malloc_size_t n, malloc_size_t elem)
439 {
440 void * mem = nano_malloc(RCALL n * elem);
441 if (mem != NULL) memset(mem, 0, n * elem);
442 return mem;
443 }
444 #endif /* DEFINE_CALLOC */
445
446 #ifdef DEFINE_REALLOC
447 /* Function nano_realloc
448 * Implement realloc by malloc + memcpy */
nano_realloc(RARG void * ptr,malloc_size_t size)449 void * nano_realloc(RARG void * ptr, malloc_size_t size)
450 {
451 void * mem;
452 chunk * p_to_realloc;
453
454 if (ptr == NULL) return nano_malloc(RCALL size);
455
456 if (size == 0)
457 {
458 nano_free(RCALL ptr);
459 return NULL;
460 }
461
462 /* TODO: There is chance to shrink the chunk if newly requested
463 * size is much small */
464 if (nano_malloc_usable_size(RCALL ptr) >= size)
465 return ptr;
466
467 mem = nano_malloc(RCALL size);
468 if (mem != NULL)
469 {
470 memcpy(mem, ptr, size);
471 nano_free(RCALL ptr);
472 }
473 return mem;
474 }
475 #endif /* DEFINE_REALLOC */
476
477 #ifdef DEFINE_MALLINFO
478 struct mallinfo current_mallinfo={0,0,0,0,0,0,0,0,0,0};
479
nano_mallinfo(RONEARG)480 struct mallinfo nano_mallinfo(RONEARG)
481 {
482 char * sbrk_now;
483 chunk * pf;
484 size_t free_size = 0;
485 size_t total_size;
486
487 MALLOC_LOCK;
488
489 if (sbrk_start == NULL) total_size = 0;
490 else {
491 sbrk_now = _SBRK_R(RCALL 0);
492
493 if (sbrk_now == (void *)-1)
494 total_size = (size_t)-1;
495 else
496 total_size = (size_t) (sbrk_now - sbrk_start);
497 }
498
499 for (pf = free_list; pf; pf = pf->next)
500 free_size += pf->size;
501
502 current_mallinfo.arena = total_size;
503 current_mallinfo.fordblks = free_size;
504 current_mallinfo.uordblks = total_size - free_size;
505
506 MALLOC_UNLOCK;
507 return current_mallinfo;
508 }
509 #endif /* DEFINE_MALLINFO */
510
511 #ifdef DEFINE_MALLOC_STATS
nano_malloc_stats(RONEARG)512 void nano_malloc_stats(RONEARG)
513 {
514 nano_mallinfo(RONECALL);
515 fiprintf(stderr, "max system bytes = %10u\n",
516 current_mallinfo.arena);
517 fiprintf(stderr, "system bytes = %10u\n",
518 current_mallinfo.arena);
519 fiprintf(stderr, "in use bytes = %10u\n",
520 current_mallinfo.uordblks);
521 }
522 #endif /* DEFINE_MALLOC_STATS */
523
524 #ifdef DEFINE_MALLOC_USABLE_SIZE
nano_malloc_usable_size(RARG void * ptr)525 malloc_size_t nano_malloc_usable_size(RARG void * ptr)
526 {
527 chunk * c = (chunk *)((char *)ptr - CHUNK_OFFSET);
528 int size_or_offset = c->size;
529
530 if (size_or_offset < 0)
531 {
532 /* Padding is used. Excluding the padding size */
533 c = (chunk *)((char *)c + c->size);
534 return c->size - CHUNK_OFFSET + size_or_offset;
535 }
536 return c->size - CHUNK_OFFSET;
537 }
538 #endif /* DEFINE_MALLOC_USABLE_SIZE */
539
540 #ifdef DEFINE_MEMALIGN
541 /* Function nano_memalign
542 * Allocate memory block aligned at specific boundary.
543 * align: required alignment. Must be power of 2. Return NULL
544 * if not power of 2. Undefined behavior is bigger than
545 * pointer value range.
546 * s: required size.
547 * Return: allocated memory pointer aligned to align
548 * Algorithm: Malloc a big enough block, padding pointer to aligned
549 * address, then truncate and free the tail if too big.
550 * Record the offset of align pointer and original pointer
551 * in the padding area.
552 */
nano_memalign(RARG size_t align,size_t s)553 void * nano_memalign(RARG size_t align, size_t s)
554 {
555 chunk * chunk_p;
556 malloc_size_t size_allocated, offset, ma_size, size_with_padding;
557 char * allocated, * aligned_p;
558
559 /* Return NULL if align isn't power of 2 */
560 if ((align & (align-1)) != 0) return NULL;
561
562 align = MAX(align, MALLOC_ALIGN);
563 ma_size = ALIGN_TO(MAX(s, MALLOC_MINSIZE), CHUNK_ALIGN);
564 size_with_padding = ma_size + align - MALLOC_ALIGN;
565
566 allocated = nano_malloc(RCALL size_with_padding);
567 if (allocated == NULL) return NULL;
568
569 chunk_p = get_chunk_from_ptr(allocated);
570 aligned_p = (char *)ALIGN_TO(
571 (unsigned long)((char *)chunk_p + CHUNK_OFFSET),
572 (unsigned long)align);
573 offset = aligned_p - ((char *)chunk_p + CHUNK_OFFSET);
574
575 if (offset)
576 {
577 if (offset >= MALLOC_MINCHUNK)
578 {
579 /* Padding is too large, free it */
580 chunk * front_chunk = chunk_p;
581 chunk_p = (chunk *)((char *)chunk_p + offset);
582 chunk_p->size = front_chunk->size - offset;
583 front_chunk->size = offset;
584 nano_free(RCALL (char *)front_chunk + CHUNK_OFFSET);
585 }
586 else
587 {
588 /* Padding is used. Need to set a jump offset for aligned pointer
589 * to get back to chunk head */
590 assert(offset >= sizeof(int));
591 *(int *)((char *)chunk_p + offset) = -offset;
592 }
593 }
594
595 size_allocated = chunk_p->size;
596 if ((char *)chunk_p + size_allocated >
597 (aligned_p + ma_size + MALLOC_MINCHUNK))
598 {
599 /* allocated much more than what's required for padding, free
600 * tail part */
601 chunk * tail_chunk = (chunk *)(aligned_p + ma_size);
602 chunk_p->size = aligned_p + ma_size - (char *)chunk_p;
603 tail_chunk->size = size_allocated - chunk_p->size;
604 nano_free(RCALL (char *)tail_chunk + CHUNK_OFFSET);
605 }
606 return aligned_p;
607 }
608 #endif /* DEFINE_MEMALIGN */
609
610 #ifdef DEFINE_MALLOPT
nano_mallopt(RARG int parameter_number,int parameter_value)611 int nano_mallopt(RARG int parameter_number, int parameter_value)
612 {
613 return 0;
614 }
615 #endif /* DEFINE_MALLOPT */
616
617 #ifdef DEFINE_VALLOC
nano_valloc(RARG size_t s)618 void * nano_valloc(RARG size_t s)
619 {
620 return nano_memalign(RCALL MALLOC_PAGE_ALIGN, s);
621 }
622 #endif /* DEFINE_VALLOC */
623
624 #ifdef DEFINE_PVALLOC
nano_pvalloc(RARG size_t s)625 void * nano_pvalloc(RARG size_t s)
626 {
627 return nano_valloc(RCALL ALIGN_TO(s, MALLOC_PAGE_ALIGN));
628 }
629 #endif /* DEFINE_PVALLOC */
630