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>>
30 *
31 * Interface documentation refer to malloc.c.
32 */
33
34 #define _DEFAULT_SOURCE
35 #include <stdio.h>
36 #include <string.h>
37 #include <stdbool.h>
38 #include <errno.h>
39 #include <malloc.h>
40 #include <stdlib.h>
41 #include <unistd.h>
42 #include <sys/lock.h>
43 #include <sys/param.h>
44 #include <stdint.h>
45
46 #if MALLOC_DEBUG
47 void __malloc_validate(void);
48 void __malloc_validate_block(chunk_t *r);
49 #define MALLOC_LOCK do { __LIBC_LOCK(); __malloc_validate(); } while(0)
50 #define MALLOC_UNLOCK do { __malloc_validate(); __LIBC_UNLOCK(); } while(0)
51 #else
52 #define __malloc_validate()
53 #define __malloc_validate_block(r)
54 #define MALLOC_LOCK __LIBC_LOCK()
55 #define MALLOC_UNLOCK __LIBC_UNLOCK()
56 #endif
57
58 typedef union {
59 void *p;
60 double d;
61 long long ll;
62 size_t s;
63 } align_chunk_t;
64
65 /* --------------------------------------
66 * | size |
67 * chunk->| When allocated: data |
68 * | When freed: pointer to next free |
69 * | chunk |
70 * --------------------------------------
71 *
72 * mem_ptr is aligned to MALLOC_CHUNK_ALIGN. That means that the
73 * address of 'size' may not be aligned to MALLOC_CHUNK_ALIGN. But it
74 * will be aligned to MALLOC_HEAD_ALIGN.
75 *
76 * size is set so that a chunk starting at chunk+size will be
77 * aligned correctly
78 *
79 * We can't use a single struct containing both size and next as that
80 * may insert padding between the size and pointer fields when
81 * pointers are larger than size_t.
82 */
83
84 typedef struct malloc_head {
85 size_t size;
86 } head_t;
87
88 typedef struct malloc_chunk {
89 struct malloc_chunk *next;
90 } chunk_t;
91
92 /* Alignment of allocated chunk. Compute the alignment required from a
93 * range of types */
94 #define MALLOC_CHUNK_ALIGN _Alignof(align_chunk_t)
95
96 /* Alignment of the header. Never larger than MALLOC_CHUNK_ALIGN, but
97 * may be smaller on some targets when size_t is smaller than
98 * align_chunk_t.
99 */
100 #define MALLOC_HEAD_ALIGN _Alignof(head_t)
101
102 #define MALLOC_HEAD sizeof(head_t)
103
104 /* nominal "page size" */
105 #define MALLOC_PAGE_ALIGN (0x1000)
106
107 /* Minimum allocation size */
108 #define MALLOC_MINSIZE __align_up(MALLOC_HEAD + sizeof(chunk_t), MALLOC_HEAD_ALIGN)
109
110 /* Maximum allocation size */
111 #define MALLOC_MAXSIZE (SIZE_MAX - (MALLOC_HEAD + 2*MALLOC_CHUNK_ALIGN))
112
_size_ref(chunk_t * chunk)113 static inline size_t *_size_ref(chunk_t *chunk)
114 {
115 return (size_t *) ((char *) chunk - MALLOC_HEAD);
116 }
117
_size(chunk_t * chunk)118 static inline size_t _size(chunk_t *chunk)
119 {
120 return *_size_ref(chunk);
121 }
122
_set_size(chunk_t * chunk,size_t size)123 static inline void _set_size(chunk_t *chunk, size_t size)
124 {
125 *_size_ref(chunk) = size;
126 }
127
128 /* Forward data declarations */
129 extern chunk_t *__malloc_free_list;
130 extern char * __malloc_sbrk_start;
131 extern char * __malloc_sbrk_top;
132
133 #if MALLOC_DEBUG
134 #else
135 #endif
136
137 bool __malloc_grow_chunk(chunk_t *c, size_t new_size);
138
139 /* Work around compiler optimizing away stores to 'size' field before
140 * call to free.
141 */
142 #ifdef _HAVE_ALIAS_ATTRIBUTE
143 void __malloc_free(void *);
144 void *__malloc_malloc(size_t);
145 #else
146 #define __malloc_free(x) free(x)
147 #define __malloc_malloc(x) malloc(x)
148 #endif
149
150 /* convert storage pointer to chunk */
151 static inline chunk_t *
ptr_to_chunk(void * ptr)152 ptr_to_chunk(void * ptr)
153 {
154 return (chunk_t *) ptr;
155 }
156
157 /* convert chunk to storage pointer */
158 static inline void *
chunk_to_ptr(chunk_t * c)159 chunk_to_ptr(chunk_t *c)
160 {
161 return c;
162 }
163
164 /* Convert address of chunk region to chunk pointer */
165 static inline chunk_t *
blob_to_chunk(void * blob)166 blob_to_chunk(void *blob)
167 {
168 return (chunk_t *) ((char *) blob + MALLOC_HEAD);
169 }
170
171 /* Convert chunk pointer to address of chunk region */
172 static inline void *
chunk_to_blob(chunk_t * c)173 chunk_to_blob(chunk_t *c)
174 {
175 return (void *) ((char *) c - MALLOC_HEAD);
176 }
177
178 /* end of chunk -- address of first byte past chunk storage */
179 static inline void *
chunk_end(chunk_t * c)180 chunk_end(chunk_t *c)
181 {
182 size_t *s = _size_ref(c);
183 return (char *) s + *s;
184 }
185
186 /* next chunk in memory -- address of chunk header past this chunk */
187 static inline chunk_t *
chunk_after(chunk_t * c)188 chunk_after(chunk_t *c)
189 {
190 return (chunk_t *) ((char *) c + _size(c));
191 }
192
193 /* chunk size needed to hold 'malloc_size' bytes */
194 static inline size_t
chunk_size(size_t malloc_size)195 chunk_size(size_t malloc_size)
196 {
197 /* Keep all blocks aligned */
198 malloc_size = __align_up(malloc_size, MALLOC_CHUNK_ALIGN);
199
200 /* Add space for header */
201 malloc_size += MALLOC_HEAD;
202
203 /* fill the gap between chunks */
204 malloc_size += (MALLOC_CHUNK_ALIGN - MALLOC_HEAD_ALIGN);
205
206 /* Make sure the requested size is big enough to hold a free chunk */
207 malloc_size = MAX(MALLOC_MINSIZE, malloc_size);
208 return malloc_size;
209 }
210
211 /* available storage in chunk */
212 static inline size_t
chunk_usable(chunk_t * c)213 chunk_usable(chunk_t *c)
214 {
215 return _size(c) - MALLOC_HEAD;
216 }
217
218 /* assign 'size' to the specified chunk and return it to the free
219 * pool */
220 static inline void
make_free_chunk(chunk_t * c,size_t size)221 make_free_chunk(chunk_t *c, size_t size)
222 {
223 _set_size(c, size);
224 __malloc_free(chunk_to_ptr(c));
225 }
226
