aboutsummaryrefslogtreecommitdiffstats
path: root/src/malloc.c
blob: 61ef24416f8fbd739cab9967e2161d87c8103cbe (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
/**
 * slibc — Yet another C library
 * Copyright © 2015  Mattias Andrée (maandree@member.fsf.org)
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
#include <stdlib.h>
#include <slibc/internals.h>
#include <stddef.h>
#include <slibc-alloc.h>
#include <strings.h>
/* TODO #include <sys/mman.h> */
#include <unistd.h>
#include <errno.h>
/* TODO temporary constants from other headers { */
#define PROT_READ 0
#define PROT_WRITE 0
#define MAP_PRIVATE 0
#define MAP_ANONYMOUS 0
#define _SC_PAGESIZE 0
/* } */


/**
 * Implementation of `malloc`.
 */
#define MALLOC(size)  memalign(sizeof(max_align_t), size)



/**
 * Create a new memory allocation on the heap.
 * The allocation will not be initialised.
 * The returned pointer is unaligned.
 * 
 * @param   size  The size of the allocation.
 * @return        Pointer to the beginning of the new allocation.
 *                If `size` is zero, this function will either return
 *                `NULL` (that is what this implement does) or return
 *                a unique pointer that can later be freed with `free`.
 *                `NULL` is returned on error, and `errno` is set to
 *                indicate the error.
 * 
 * @throws  ENOMEM  The process cannot allocate more memory.
 */
static void* unaligned_malloc(size_t size)
{
  char* ptr;
  size_t full_size;
  
  if (size == 0)
    return NULL;
  MEM_OVERFLOW(uaddl, 2 * sizeof(size_t), size, &full_size);
  
  ptr = mmap(NULL, full_size, (PROT_READ | PROT_WRITE),
	     (MAP_PRIVATE | MAP_ANONYMOUS), -1, 0);
  if (ptr == MAP_FAILED)
    return NULL;
  
  ((size_t*)ptr)[0] = size;
  ((size_t*)ptr)[1] = 0;
  return ptr + 2 * sizeof(size_t);
}


/**
 * Create a new memory allocation on the heap.
 * The allocation will not be initialised.
 * The returned pointer has an alignment usable
 * for any compiler-independent intrinsic data type.
 * 
 * @param   size  The size of the allocation.
 * @return        Pointer to the beginning of the new allocation.
 *                If `size` is zero, this function will either return
 *                `NULL` (that is what this implement does) or return
 *                a unique pointer that can later be freed with `free`.
 *                `NULL` is returned on error, and `errno` is set to
 *                indicate the error.
 * 
 * @throws  ENOMEM  The process cannot allocate more memory.
 */
void* malloc(size_t size)
{
  return MALLOC(size);
}


/**
 * Variant of `malloc` that clears the allocation with zeroes.
 * 
 * `p = calloc(n, m)` is equivalent to
 * `(p = malloc(n * m), p ? (explicit_bzero(p, n * m), p) : NULL)`
 * 
 * @param   elem_count  The number of elements to allocate.
 * @param   elem_size   The size of each element.
 * @return              Pointer to the beginning of the new allocation.
 *                      If `elem_count` or `elem_size` is zero, this function
 *                      will either return `NULL` (that is what this implement
 *                      does) or return a unique pointer that can later be
 *                      freed with `free`. `NULL` is returned on error, and
 *                      `errno` is set to indicate the error.
 * 
 * @throws  ENOMEM  The process cannot allocate more memory.
 */
void* calloc(size_t elem_count, size_t elem_size)
{
  void* ptr;
  size_t size;
  
  MEM_OVERFLOW(umull, elem_count, elem_size, &size);
  ptr = MALLOC(size);
  if (ptr != NULL)
    explicit_bzero(ptr, size);
  
  return ptr;
}


/**
 * Variant of `malloc` that conditionally clears the allocation with zeroes.
 * 
 * `mallocz(size, clear)` is equivalent to
 *  both `(clear ? zalloc : malloc)(size)`
 *  and `(clear ? calloc(1, size) : malloc(size))`.
 * 
 * This is a Plan 9 from Bell Labs extension.
 * 
 * @param   size   The size of the allocation.
 * @param   clear  Clear the allocation unless this value is zero.
 * @return         Pointer to the beginning of the new allocation.
 *                 If `size` is zero, this function will either return
 *                 `NULL` (that is what this implement does) or return
 *                 a unique pointer that can later be freed with `free`.
 *                 `NULL` is returned on error, and `errno` is set to
 *                 indicate the error.
 * 
 * @throws  ENOMEM  The process cannot allocate more memory.
 */
void* mallocz(size_t size, int clear)
{
  void* ptr = MALLOC(size);
  if ((ptr != NULL) && clear)
    explicit_bzero(ptr, size);
  return ptr;
}


/**
 * Variant of `malloc` that clears the allocation with zeroes.
 * 
 * `zalloc(n)` is equivalent to `calloc(1, n)`, or equivalently,
 * `calloc(n, m)` is equivalent to `zalloc(n * m)` assuming `n * m`
 * does not overflow (in which case `calloc(n, m)` returns `ENOMEM`.)
 * 
 * This is a klibc extension.
 * 
 * @param   size  The size of the allocation.
 * @return        Pointer to the beginning of the new allocation.
 *                If `size` is zero, this function will either return
 *                `NULL` (that is what this implement does) or return
 *                a unique pointer that can later be freed with `free`.
 *                `NULL` is returned on error, and `errno` is set to
 *                indicate the error.
 * 
 * @throws  ENOMEM  The process cannot allocate more memory.
 */
void* zalloc(size_t size)
{
  void* ptr = MALLOC(size);
  if (ptr != NULL)
    explicit_bzero(ptr, size);
  return ptr;
}


/**
 * Variant of `malloc` that extends, or shrinks, an existing allocation,
 * if beneficial and possible, or creates a new allocation with the new
 * size, copies the data, and frees the old allocation. The returned
 * pointer has an alignment usable for any compiler-independent intrinsic
 * data type, if a new pointer is returned.
 * 
 * On error, `ptr` is not freed.
 * 
 * @param   ptr   Pointer to the beginning of the old memory allocation.
 *                The process may crash if it does not point to the
 *                beginning of a memory allocation on the heap.
 *                However, if it is `NULL`, this function will behave
 *                like `malloc`.
 * @param   size  The new allocation size. If zero, this function will
 *                behave like `free`, and will return `NULL`.
 * @return        Pointer to the beginning of the new allocation.
 *                If `size` is zero, `NULL` is returned. On error `NULL`
 *                is returned and `errno` is set to indicate the error.
 * 
 * @throws  ENOMEM  The process cannot allocate more memory.
 */
void* realloc(void* ptr, size_t size)
{
  return fast_realloc(ptr, size);
}


/**
 * Free a memory allocation.
 * 
 * @param  ptr  Pointer to the beginning of the memory allocation.
 *              The process may crash if it does not point to the
 *              beginning of a memory allocation on the heap.
 *              However, if it is `NULL`, nothing will happen.
 */
void free(void* ptr)
{
  fast_free(ptr);
}


/**
 * This function is identical to `free`.
 * Any argument beyond the first argument, is ignored.
 * 
 * This function uses variadic arguments because there
 * there are multiple conflicting specifications for `cfree`.
 * 
 * @param  ptr  Pointer to the beginning of the memory allocation.
 *              The process may crash if it does not point to the
 *              beginning of a memory allocation on the heap.
 *              However, if it is `NULL`, nothing will happen.
 */
void cfree(void* ptr, ...)
{
  fast_free(ptr);
}


/**
 * Variant of `malloc` that returns an address with a
 * specified alignment.
 * 
 * It is unspecified how the function works. This implemention
 * will allocate a bit of extra memory and shift the returned
 * pointer so that it is aligned.
 * 
 * As a GNU-compliant slibc extension, memory allocated
 * with this function can be freed with `free`.
 * 
 * @param   boundary  The alignment.
 * @param   size      The number of bytes to allocated.
 * @return            Pointer to the beginning of the new allocation.
 *                    If `size` is zero, this function will either return
 *                    `NULL` (that is what this implement does) or return
 *                    a unique pointer that can later be freed with `free`.
 *                    `NULL` is returned on error, and `errno` is set to
 *                    indicate the error.
 * 
 * @throws  ENOMEM  The process cannot allocate more memory.
 * @throws  EINVAL  If `boundary` is not a power of two.
 */
void* memalign(size_t boundary, size_t size)
{
  char* ptr;
  size_t full_size;
  size_t address;
  size_t shift = 0;
  
  if (!boundary || (__builtin_ffsl((long int)boundary) != boundary))
    /* `size_t` mat not be wider than `long int`. */
    return errno = EINVAL, NULL;
  MEM_OVERFLOW(uaddl, boundary - 1, size, &full_size);
  
  ptr = unaligned_malloc(full_size);
  if (ptr == NULL)
    return NULL;
  
  address = (size_t)ptr;
  if (address % boundary != 0)
    {
      shift = boundary - (address % boundary);
      ptr += shift;
      *(size_t*)(ptr - sizeof(size_t)) = shift;
    }
  
  return ptr;
}


/**
 * `posix_memalign(p, b, n)` is equivalent to
 * `(*p = memalign(b, n), *p ? 0 : errno)`, except
 * `boundary` must also be a multiple of `sizeof(void*)`,
 * and `errno` is unspecified.
 * 
 * As a GNU-compliant slibc extension, memory allocated
 * with this function can be freed with `free`.
 * 
 * @param   ptrptr    Output parameter for the allocated memory.
 * @param   boundary  The alignment.
 * @param   size      The number of bytes to allocated.
 * @return            Zero on success, a value for `errno` on error.
 * 
 * @throws  ENOMEM  The process cannot allocate more memory.
 * @throws  EINVAL  If `boundary` is not a power-of-two multiple of `sizeof(void*)`.
 */
int posix_memalign(void** ptrptr, size_t boundary, size_t size)
{
  if (boundary < sizeof(void*))
    return EINVAL;
  *ptrptr = memalign(boundary, size);
  return *ptrptr ? 0 : errno;
}


/**
 * `valloc(n)` is equivalent to `memalign(sysconf(_SC_PAGESIZE), n)`.
 * 
 * As a GNU-compliant slibc extension, memory allocated
 * with this function can be freed with `free`.
 * 
 * @param   size  The number of bytes to allocated.
 * @return        Pointer to the beginning of the new allocation.
 *                If `size` is zero, this function will either return
 *                `NULL` (that is what this implement does) or return
 *                a unique pointer that can later be freed with `free`.
 *                `NULL` is returned on error, and `errno` is set to
 *                indicate the error.
 * 
 * @throws  ENOMEM  The process cannot allocate more memory.
 */
void* valloc(size_t size)
{
  return memalign((size_t)sysconf(_SC_PAGESIZE), size);
}


/**
 * This function works like `valloc`, except the allocation size,
 * including auxiliary space, is rounded up to the next multiple
 * of the page size.
 * 
 * @param   size    The number of bytes to allocated.
 * @return          Pointer to the beginning of the new allocation.
 *                  If `size` is zero, this function will either return
 *                  `NULL` (that is what this implement does) or return
 *                  a unique pointer that can later be freed with `free`.
 *                  `NULL` is returned on error, and `errno` is set to
 *                  indicate the error.
 * 
 * @throws  ENOMEM  The process cannot allocate more memory.
 */
void* pvalloc(size_t size)
{
  size_t boundary = (size_t)sysconf(_SC_PAGESIZE);
  size_t full_size = 2 * sizeof(size_t) + boundary - 1 + size;
  size_t rounding = 0;
  
  if (full_size % boundary != 0)
      rounding = boundary - (full_size % boundary);
  
  MEM_OVERFLOW(uaddl, size, rounding, &full_size);
  return memalign(boundary, full_size);
}


/**
 * This function is identical to `memalign`,
 * except it can be freed with `free`.
 * 
 * Variant of `malloc` that returns an address with a
 * specified alignment.
 * 
 * It is unspecified how the function works. This implemention
 * will allocate a bit of extra memory and shift the returned
 * pointer so that it is aligned.
 * 
 * @param   boundary  The alignment.
 * @param   size      The number of bytes to allocated.
 * @return            Pointer to the beginning of the new allocation.
 *                    If `size` is zero, this function will either return
 *                    `NULL` (that is what this implement does) or return
 *                    a unique pointer that can later be freed with `free`.
 *                    `NULL` is returned on error, and `errno` is set to
 *                    indicate the error.
 * 
 * @throws  ENOMEM  The process cannot allocate more memory.
 * @throws  EINVAL  If `boundary` is not a power of two.
 */
void* aligned_alloc(size_t boundary, size_t size)
{
  return memalign(boundary, size);
}


/**
 * This function returns the allocation size of
 * a memory segment.
 * 
 * `p = malloc(n), malloc_usable_size(p)` will return `n`.
 * 
 * @param   segment  The memory segment.
 * @return           The size of the memory segment, 0 if `segment` is `NULL`.
 */
size_t malloc_usable_size(void* segment)
{
  return allocsize(segment);  
}