1/* Malloc implementation for multiple threads without lock contention.
2 Copyright (C) 2001-2016 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Wolfram Gloger <wg@malloc.de>, 2001.
5
6 The GNU C Library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public License as
8 published by the Free Software Foundation; either version 2.1 of the
9 License, or (at your option) any later version.
10
11 The GNU C Library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
15
16 You should have received a copy of the GNU Lesser General Public
17 License along with the GNU C Library; see the file COPYING.LIB. If
18 not, see <http://www.gnu.org/licenses/>. */
19
20/* What to do if the standard debugging hooks are in place and a
21 corrupt pointer is detected: do nothing (0), print an error message
22 (1), or call abort() (2). */
23
24/* Hooks for debugging versions. The initial hooks just call the
25 initialization routine, then do the normal work. */
26
27static void *
28malloc_hook_ini (size_t sz, const void *caller)
29{
30 __malloc_hook = NULL;
31 ptmalloc_init ();
32 return __libc_malloc (sz);
33}
34
35static void *
36realloc_hook_ini (void *ptr, size_t sz, const void *caller)
37{
38 __malloc_hook = NULL;
39 __realloc_hook = NULL;
40 ptmalloc_init ();
41 return __libc_realloc (ptr, sz);
42}
43
44static void *
45memalign_hook_ini (size_t alignment, size_t sz, const void *caller)
46{
47 __memalign_hook = NULL;
48 ptmalloc_init ();
49 return __libc_memalign (alignment, sz);
50}
51
52/* Whether we are using malloc checking. */
53static int using_malloc_checking;
54
55/* A flag that is set by malloc_set_state, to signal that malloc checking
56 must not be enabled on the request from the user (via the MALLOC_CHECK_
57 environment variable). It is reset by __malloc_check_init to tell
58 malloc_set_state that the user has requested malloc checking.
59
60 The purpose of this flag is to make sure that malloc checking is not
61 enabled when the heap to be restored was constructed without malloc
62 checking, and thus does not contain the required magic bytes.
63 Otherwise the heap would be corrupted by calls to free and realloc. If
64 it turns out that the heap was created with malloc checking and the
65 user has requested it malloc_set_state just calls __malloc_check_init
66 again to enable it. On the other hand, reusing such a heap without
67 further malloc checking is safe. */
68static int disallow_malloc_check;
69
70/* Activate a standard set of debugging hooks. */
71void
72__malloc_check_init (void)
73{
74 if (disallow_malloc_check)
75 {
76 disallow_malloc_check = 0;
77 return;
78 }
79 using_malloc_checking = 1;
80 __malloc_hook = malloc_check;
81 __free_hook = free_check;
82 __realloc_hook = realloc_check;
83 __memalign_hook = memalign_check;
84}
85
86/* A simple, standard set of debugging hooks. Overhead is `only' one
87 byte per chunk; still this will catch most cases of double frees or
88 overruns. The goal here is to avoid obscure crashes due to invalid
89 usage, unlike in the MALLOC_DEBUG code. */
90
91static unsigned char
92magicbyte (const void *p)
93{
94 unsigned char magic;
95
96 magic = (((uintptr_t) p >> 3) ^ ((uintptr_t) p >> 11)) & 0xFF;
97 /* Do not return 1. See the comment in mem2mem_check(). */
98 if (magic == 1)
99 ++magic;
100 return magic;
101}
102
103
104/* Visualize the chunk as being partitioned into blocks of 255 bytes from the
105 highest address of the chunk, downwards. The end of each block tells
106 us the size of that block, up to the actual size of the requested
107 memory. Our magic byte is right at the end of the requested size, so we
108 must reach it with this iteration, otherwise we have witnessed a memory
109 corruption. */
110static size_t
111malloc_check_get_size (mchunkptr p)
112{
113 size_t size;
114 unsigned char c;
115 unsigned char magic = magicbyte (p);
116
117 assert (using_malloc_checking == 1);
118
119 for (size = chunksize (p) - 1 + (chunk_is_mmapped (p) ? 0 : SIZE_SZ);
120 (c = ((unsigned char *) p)[size]) != magic;
121 size -= c)
122 {
123 if (c <= 0 || size < (c + 2 * SIZE_SZ))
124 {
125 malloc_printerr (check_action, "malloc_check_get_size: memory corruption",
126 chunk2mem (p),
127 chunk_is_mmapped (p) ? NULL : arena_for_chunk (p));
128 return 0;
129 }
130 }
131
132 /* chunk2mem size. */
133 return size - 2 * SIZE_SZ;
134}
135
136/* Instrument a chunk with overrun detector byte(s) and convert it
137 into a user pointer with requested size req_sz. */
138
139static void *
140internal_function
141mem2mem_check (void *ptr, size_t req_sz)
142{
143 mchunkptr p;
144 unsigned char *m_ptr = ptr;
145 size_t max_sz, block_sz, i;
146 unsigned char magic;
147
148 if (!ptr)
149 return ptr;
150
151 p = mem2chunk (ptr);
152 magic = magicbyte (p);
153 max_sz = chunksize (p) - 2 * SIZE_SZ;
154 if (!chunk_is_mmapped (p))
155 max_sz += SIZE_SZ;
156 for (i = max_sz - 1; i > req_sz; i -= block_sz)
157 {
158 block_sz = MIN (i - req_sz, 0xff);
159 /* Don't allow the magic byte to appear in the chain of length bytes.
160 For the following to work, magicbyte cannot return 0x01. */
161 if (block_sz == magic)
162 --block_sz;
163
164 m_ptr[i] = block_sz;
165 }
166 m_ptr[req_sz] = magic;
167 return (void *) m_ptr;
168}
169
170/* Convert a pointer to be free()d or realloc()ed to a valid chunk
171 pointer. If the provided pointer is not valid, return NULL. */
172
173static mchunkptr
174internal_function
175mem2chunk_check (void *mem, unsigned char **magic_p)
176{
177 mchunkptr p;
178 INTERNAL_SIZE_T sz, c;
179 unsigned char magic;
180
181 if (!aligned_OK (mem))
182 return NULL;
183
184 p = mem2chunk (mem);
185 sz = chunksize (p);
186 magic = magicbyte (p);
187 if (!chunk_is_mmapped (p))
188 {
189 /* Must be a chunk in conventional heap memory. */
190 int contig = contiguous (&main_arena);
191 if ((contig &&
192 ((char *) p < mp_.sbrk_base ||
193 ((char *) p + sz) >= (mp_.sbrk_base + main_arena.system_mem))) ||
194 sz < MINSIZE || sz & MALLOC_ALIGN_MASK || !inuse (p) ||
195 (!prev_inuse (p) && (p->prev_size & MALLOC_ALIGN_MASK ||
196 (contig && (char *) prev_chunk (p) < mp_.sbrk_base) ||
197 next_chunk (prev_chunk (p)) != p)))
198 return NULL;
199
200 for (sz += SIZE_SZ - 1; (c = ((unsigned char *) p)[sz]) != magic; sz -= c)
201 {
202 if (c == 0 || sz < (c + 2 * SIZE_SZ))
203 return NULL;
204 }
205 }
206 else
207 {
208 unsigned long offset, page_mask = GLRO (dl_pagesize) - 1;
209
210 /* mmap()ed chunks have MALLOC_ALIGNMENT or higher power-of-two
211 alignment relative to the beginning of a page. Check this
212 first. */
213 offset = (unsigned long) mem & page_mask;
214 if ((offset != MALLOC_ALIGNMENT && offset != 0 && offset != 0x10 &&
215 offset != 0x20 && offset != 0x40 && offset != 0x80 && offset != 0x100 &&
216 offset != 0x200 && offset != 0x400 && offset != 0x800 && offset != 0x1000 &&
217 offset < 0x2000) ||
218 !chunk_is_mmapped (p) || (p->size & PREV_INUSE) ||
219 ((((unsigned long) p - p->prev_size) & page_mask) != 0) ||
220 ((p->prev_size + sz) & page_mask) != 0)
221 return NULL;
222
223 for (sz -= 1; (c = ((unsigned char *) p)[sz]) != magic; sz -= c)
224 {
225 if (c == 0 || sz < (c + 2 * SIZE_SZ))
226 return NULL;
227 }
228 }
229 ((unsigned char *) p)[sz] ^= 0xFF;
230 if (magic_p)
231 *magic_p = (unsigned char *) p + sz;
232 return p;
233}
234
235/* Check for corruption of the top chunk, and try to recover if
236 necessary. */
237
238static int
239internal_function
240top_check (void)
241{
242 mchunkptr t = top (&main_arena);
243 char *brk, *new_brk;
244 INTERNAL_SIZE_T front_misalign, sbrk_size;
245 unsigned long pagesz = GLRO (dl_pagesize);
246
247 if (t == initial_top (&main_arena) ||
248 (!chunk_is_mmapped (t) &&
249 chunksize (t) >= MINSIZE &&
250 prev_inuse (t) &&
251 (!contiguous (&main_arena) ||
252 (char *) t + chunksize (t) == mp_.sbrk_base + main_arena.system_mem)))
253 return 0;
254
255 malloc_printerr (check_action, "malloc: top chunk is corrupt", t,
256 &main_arena);
257
258 /* Try to set up a new top chunk. */
259 brk = MORECORE (0);
260 front_misalign = (unsigned long) chunk2mem (brk) & MALLOC_ALIGN_MASK;
261 if (front_misalign > 0)
262 front_misalign = MALLOC_ALIGNMENT - front_misalign;
263 sbrk_size = front_misalign + mp_.top_pad + MINSIZE;
264 sbrk_size += pagesz - ((unsigned long) (brk + sbrk_size) & (pagesz - 1));
265 new_brk = (char *) (MORECORE (sbrk_size));
266 if (new_brk == (char *) (MORECORE_FAILURE))
267 {
268 __set_errno (ENOMEM);
269 return -1;
270 }
271 /* Call the `morecore' hook if necessary. */
272 void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
273 if (hook)
274 (*hook)();
275 main_arena.system_mem = (new_brk - mp_.sbrk_base) + sbrk_size;
276
277 top (&main_arena) = (mchunkptr) (brk + front_misalign);
278 set_head (top (&main_arena), (sbrk_size - front_misalign) | PREV_INUSE);
279
280 return 0;
281}
282
283static void *
284malloc_check (size_t sz, const void *caller)
285{
286 void *victim;
287
288 if (sz + 1 == 0)
289 {
290 __set_errno (ENOMEM);
291 return NULL;
292 }
293
294 (void) mutex_lock (&main_arena.mutex);
295 victim = (top_check () >= 0) ? _int_malloc (&main_arena, sz + 1) : NULL;
296 (void) mutex_unlock (&main_arena.mutex);
297 return mem2mem_check (victim, sz);
298}
299
300static void
301free_check (void *mem, const void *caller)
302{
303 mchunkptr p;
304
305 if (!mem)
306 return;
307
308 (void) mutex_lock (&main_arena.mutex);
309 p = mem2chunk_check (mem, NULL);
310 if (!p)
311 {
312 (void) mutex_unlock (&main_arena.mutex);
313
314 malloc_printerr (check_action, "free(): invalid pointer", mem,
315 &main_arena);
316 return;
317 }
318 if (chunk_is_mmapped (p))
319 {
320 (void) mutex_unlock (&main_arena.mutex);
321 munmap_chunk (p);
322 return;
323 }
324 _int_free (&main_arena, p, 1);
325 (void) mutex_unlock (&main_arena.mutex);
326}
327
328static void *
329realloc_check (void *oldmem, size_t bytes, const void *caller)
330{
331 INTERNAL_SIZE_T nb;
332 void *newmem = 0;
333 unsigned char *magic_p;
334
335 if (bytes + 1 == 0)
336 {
337 __set_errno (ENOMEM);
338 return NULL;
339 }
340 if (oldmem == 0)
341 return malloc_check (bytes, NULL);
342
343 if (bytes == 0)
344 {
345 free_check (oldmem, NULL);
346 return NULL;
347 }
348 (void) mutex_lock (&main_arena.mutex);
349 const mchunkptr oldp = mem2chunk_check (oldmem, &magic_p);
350 (void) mutex_unlock (&main_arena.mutex);
351 if (!oldp)
352 {
353 malloc_printerr (check_action, "realloc(): invalid pointer", oldmem,
354 &main_arena);
355 return malloc_check (bytes, NULL);
356 }
357 const INTERNAL_SIZE_T oldsize = chunksize (oldp);
358
359 checked_request2size (bytes + 1, nb);
360 (void) mutex_lock (&main_arena.mutex);
361
362 if (chunk_is_mmapped (oldp))
363 {
364#if HAVE_MREMAP
365 mchunkptr newp = mremap_chunk (oldp, nb);
366 if (newp)
367 newmem = chunk2mem (newp);
368 else
369#endif
370 {
371 /* Note the extra SIZE_SZ overhead. */
372 if (oldsize - SIZE_SZ >= nb)
373 newmem = oldmem; /* do nothing */
374 else
375 {
376 /* Must alloc, copy, free. */
377 if (top_check () >= 0)
378 newmem = _int_malloc (&main_arena, bytes + 1);
379 if (newmem)
380 {
381 memcpy (newmem, oldmem, oldsize - 2 * SIZE_SZ);
382 munmap_chunk (oldp);
383 }
384 }
385 }
386 }
387 else
388 {
389 if (top_check () >= 0)
390 {
391 INTERNAL_SIZE_T nb;
392 checked_request2size (bytes + 1, nb);
393 newmem = _int_realloc (&main_arena, oldp, oldsize, nb);
394 }
395 }
396
397 /* mem2chunk_check changed the magic byte in the old chunk.
398 If newmem is NULL, then the old chunk will still be used though,
399 so we need to invert that change here. */
400 if (newmem == NULL)
401 *magic_p ^= 0xFF;
402
403 (void) mutex_unlock (&main_arena.mutex);
404
405 return mem2mem_check (newmem, bytes);
406}
407
408static void *
409memalign_check (size_t alignment, size_t bytes, const void *caller)
410{
411 void *mem;
412
413 if (alignment <= MALLOC_ALIGNMENT)
414 return malloc_check (bytes, NULL);
415
416 if (alignment < MINSIZE)
417 alignment = MINSIZE;
418
419 /* If the alignment is greater than SIZE_MAX / 2 + 1 it cannot be a
420 power of 2 and will cause overflow in the check below. */
421 if (alignment > SIZE_MAX / 2 + 1)
422 {
423 __set_errno (EINVAL);
424 return 0;
425 }
426
427 /* Check for overflow. */
428 if (bytes > SIZE_MAX - alignment - MINSIZE)
429 {
430 __set_errno (ENOMEM);
431 return 0;
432 }
433
434 /* Make sure alignment is power of 2. */
435 if (!powerof2 (alignment))
436 {
437 size_t a = MALLOC_ALIGNMENT * 2;
438 while (a < alignment)
439 a <<= 1;
440 alignment = a;
441 }
442
443 (void) mutex_lock (&main_arena.mutex);
444 mem = (top_check () >= 0) ? _int_memalign (&main_arena, alignment, bytes + 1) :
445 NULL;
446 (void) mutex_unlock (&main_arena.mutex);
447 return mem2mem_check (mem, bytes);
448}
449
450
451/* Get/set state: malloc_get_state() records the current state of all
452 malloc variables (_except_ for the actual heap contents and `hook'
453 function pointers) in a system dependent, opaque data structure.
454 This data structure is dynamically allocated and can be free()d
455 after use. malloc_set_state() restores the state of all malloc
456 variables to the previously obtained state. This is especially
457 useful when using this malloc as part of a shared library, and when
458 the heap contents are saved/restored via some other method. The
459 primary example for this is GNU Emacs with its `dumping' procedure.
460 `Hook' function pointers are never saved or restored by these
461 functions, with two exceptions: If malloc checking was in use when
462 malloc_get_state() was called, then malloc_set_state() calls
463 __malloc_check_init() if possible; if malloc checking was not in
464 use in the recorded state but the user requested malloc checking,
465 then the hooks are reset to 0. */
466
467#define MALLOC_STATE_MAGIC 0x444c4541l
468#define MALLOC_STATE_VERSION (0 * 0x100l + 5l) /* major*0x100 + minor */
469
470struct malloc_save_state
471{
472 long magic;
473 long version;
474 mbinptr av[NBINS * 2 + 2];
475 char *sbrk_base;
476 int sbrked_mem_bytes;
477 unsigned long trim_threshold;
478 unsigned long top_pad;
479 unsigned int n_mmaps_max;
480 unsigned long mmap_threshold;
481 int check_action;
482 unsigned long max_sbrked_mem;
483 unsigned long max_total_mem; /* Always 0, for backwards compatibility. */
484 unsigned int n_mmaps;
485 unsigned int max_n_mmaps;
486 unsigned long mmapped_mem;
487 unsigned long max_mmapped_mem;
488 int using_malloc_checking;
489 unsigned long max_fast;
490 unsigned long arena_test;
491 unsigned long arena_max;
492 unsigned long narenas;
493};
494
495void *
496__malloc_get_state (void)
497{
498 struct malloc_save_state *ms;
499 int i;
500 mbinptr b;
501
502 ms = (struct malloc_save_state *) __libc_malloc (sizeof (*ms));
503 if (!ms)
504 return 0;
505
506 (void) mutex_lock (&main_arena.mutex);
507 malloc_consolidate (&main_arena);
508 ms->magic = MALLOC_STATE_MAGIC;
509 ms->version = MALLOC_STATE_VERSION;
510 ms->av[0] = 0;
511 ms->av[1] = 0; /* used to be binblocks, now no longer used */
512 ms->av[2] = top (&main_arena);
513 ms->av[3] = 0; /* used to be undefined */
514 for (i = 1; i < NBINS; i++)
515 {
516 b = bin_at (&main_arena, i);
517 if (first (b) == b)
518 ms->av[2 * i + 2] = ms->av[2 * i + 3] = 0; /* empty bin */
519 else
520 {
521 ms->av[2 * i + 2] = first (b);
522 ms->av[2 * i + 3] = last (b);
523 }
524 }
525 ms->sbrk_base = mp_.sbrk_base;
526 ms->sbrked_mem_bytes = main_arena.system_mem;
527 ms->trim_threshold = mp_.trim_threshold;
528 ms->top_pad = mp_.top_pad;
529 ms->n_mmaps_max = mp_.n_mmaps_max;
530 ms->mmap_threshold = mp_.mmap_threshold;
531 ms->check_action = check_action;
532 ms->max_sbrked_mem = main_arena.max_system_mem;
533 ms->max_total_mem = 0;
534 ms->n_mmaps = mp_.n_mmaps;
535 ms->max_n_mmaps = mp_.max_n_mmaps;
536 ms->mmapped_mem = mp_.mmapped_mem;
537 ms->max_mmapped_mem = mp_.max_mmapped_mem;
538 ms->using_malloc_checking = using_malloc_checking;
539 ms->max_fast = get_max_fast ();
540 ms->arena_test = mp_.arena_test;
541 ms->arena_max = mp_.arena_max;
542 ms->narenas = narenas;
543 (void) mutex_unlock (&main_arena.mutex);
544 return (void *) ms;
545}
546
547int
548__malloc_set_state (void *msptr)
549{
550 struct malloc_save_state *ms = (struct malloc_save_state *) msptr;
551
552 if (ms->magic != MALLOC_STATE_MAGIC)
553 return -1;
554
555 /* Must fail if the major version is too high. */
556 if ((ms->version & ~0xffl) > (MALLOC_STATE_VERSION & ~0xffl))
557 return -2;
558
559 /* We do not need to perform locking here because __malloc_set_state
560 must be called before the first call into the malloc subsytem
561 (usually via __malloc_initialize_hook). pthread_create always
562 calls calloc and thus must be called only afterwards, so there
563 cannot be more than one thread when we reach this point. */
564
565 /* Disable the malloc hooks (and malloc checking). */
566 __malloc_hook = NULL;
567 __realloc_hook = NULL;
568 __free_hook = NULL;
569 __memalign_hook = NULL;
570 using_malloc_checking = 0;
571
572 /* Patch the dumped heap. We no longer try to integrate into the
573 existing heap. Instead, we mark the existing chunks as mmapped.
574 Together with the update to dumped_main_arena_start and
575 dumped_main_arena_end, realloc and free will recognize these
576 chunks as dumped fake mmapped chunks and never free them. */
577
578 /* Find the chunk with the lowest address with the heap. */
579 mchunkptr chunk = NULL;
580 {
581 size_t *candidate = (size_t *) ms->sbrk_base;
582 size_t *end = (size_t *) (ms->sbrk_base + ms->sbrked_mem_bytes);
583 while (candidate < end)
584 if (*candidate != 0)
585 {
586 chunk = mem2chunk ((void *) (candidate + 1));
587 break;
588 }
589 else
590 ++candidate;
591 }
592 if (chunk == NULL)
593 return 0;
594
595 /* Iterate over the dumped heap and patch the chunks so that they
596 are treated as fake mmapped chunks. */
597 mchunkptr top = ms->av[2];
598 while (chunk < top)
599 {
600 if (inuse (chunk))
601 {
602 /* Mark chunk as mmapped, to trigger the fallback path. */
603 size_t size = chunksize (chunk);
604 set_head (chunk, size | IS_MMAPPED);
605 }
606 chunk = next_chunk (chunk);
607 }
608
609 /* The dumped fake mmapped chunks all lie in this address range. */
610 dumped_main_arena_start = (mchunkptr) ms->sbrk_base;
611 dumped_main_arena_end = top;
612
613 return 0;
614}
615
616/*
617 * Local variables:
618 * c-basic-offset: 2
619 * End:
620 */
621