Merge from trunk; up to 2012-12-09T01:04:43Z!rgm@gnu.org.
[bpt/emacs.git] / src / gmalloc.c
1 /* Declarations for `malloc' and friends.
2 Copyright (C) 1990, 1991, 1992, 1993, 1995, 1996, 1999, 2002, 2003, 2004,
3 2005, 2006, 2007 Free Software Foundation, Inc.
4 Written May 1989 by Mike Haertel.
5
6 This library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU General Public License as
8 published by the Free Software Foundation; either version 2 of the
9 License, or (at your option) any later version.
10
11 This 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 General Public License for more details.
15
16 You should have received a copy of the GNU General Public
17 License along with this library; see the file COPYING. If
18 not, write to the Free Software Foundation, Inc., 51 Franklin Street,
19 Fifth Floor, Boston, MA 02110-1301, USA.
20
21 The author may be reached (Email) at the address mike@ai.mit.edu,
22 or (US mail) as Mike Haertel c/o Free Software Foundation. */
23
24 #include <config.h>
25
26 #ifdef HAVE_PTHREAD
27 #define USE_PTHREAD
28 #endif
29
30 #include <string.h>
31 #include <limits.h>
32 #include <stdint.h>
33 #include <unistd.h>
34
35 #ifdef USE_PTHREAD
36 #include <pthread.h>
37 #endif
38
39 #ifdef WINDOWSNT
40 #include <w32heap.h> /* for sbrk */
41 #endif
42
43 #ifdef __cplusplus
44 extern "C"
45 {
46 #endif
47
48 #include <stddef.h>
49
50
51 /* Allocate SIZE bytes of memory. */
52 extern void *malloc (size_t size);
53 /* Re-allocate the previously allocated block
54 in ptr, making the new block SIZE bytes long. */
55 extern void *realloc (void *ptr, size_t size);
56 /* Allocate NMEMB elements of SIZE bytes each, all initialized to 0. */
57 extern void *calloc (size_t nmemb, size_t size);
58 /* Free a block allocated by `malloc', `realloc' or `calloc'. */
59 extern void free (void *ptr);
60
61 /* Allocate SIZE bytes allocated to ALIGNMENT bytes. */
62 #ifdef MSDOS
63 extern void *memalign (size_t, size_t);
64 extern int posix_memalign (void **, size_t, size_t);
65 #endif
66
67 #ifdef USE_PTHREAD
68 /* Set up mutexes and make malloc etc. thread-safe. */
69 extern void malloc_enable_thread (void);
70 #endif
71
72 /* The allocator divides the heap into blocks of fixed size; large
73 requests receive one or more whole blocks, and small requests
74 receive a fragment of a block. Fragment sizes are powers of two,
75 and all fragments of a block are the same size. When all the
76 fragments in a block have been freed, the block itself is freed. */
77 #define INT_BIT (CHAR_BIT * sizeof (int))
78 #define BLOCKLOG (INT_BIT > 16 ? 12 : 9)
79 #define BLOCKSIZE (1 << BLOCKLOG)
80 #define BLOCKIFY(SIZE) (((SIZE) + BLOCKSIZE - 1) / BLOCKSIZE)
81
82 /* Determine the amount of memory spanned by the initial heap table
83 (not an absolute limit). */
84 #define HEAP (INT_BIT > 16 ? 4194304 : 65536)
85
86 /* Number of contiguous free blocks allowed to build up at the end of
87 memory before they will be returned to the system. */
88 #define FINAL_FREE_BLOCKS 8
89
90 /* Data structure giving per-block information. */
91 typedef union
92 {
93 /* Heap information for a busy block. */
94 struct
95 {
96 /* Zero for a large (multiblock) object, or positive giving the
97 logarithm to the base two of the fragment size. */
98 int type;
99 union
100 {
101 struct
102 {
103 size_t nfree; /* Free frags in a fragmented block. */
104 size_t first; /* First free fragment of the block. */
105 } frag;
106 /* For a large object, in its first block, this has the number
107 of blocks in the object. In the other blocks, this has a
108 negative number which says how far back the first block is. */
109 ptrdiff_t size;
110 } info;
111 } busy;
112 /* Heap information for a free block
113 (that may be the first of a free cluster). */
114 struct
115 {
116 size_t size; /* Size (in blocks) of a free cluster. */
117 size_t next; /* Index of next free cluster. */
118 size_t prev; /* Index of previous free cluster. */
119 } free;
120 } malloc_info;
121
122 /* Pointer to first block of the heap. */
123 extern char *_heapbase;
124
125 /* Table indexed by block number giving per-block information. */
126 extern malloc_info *_heapinfo;
127
128 /* Address to block number and vice versa. */
129 #define BLOCK(A) (((char *) (A) - _heapbase) / BLOCKSIZE + 1)
130 #define ADDRESS(B) ((void *) (((B) - 1) * BLOCKSIZE + _heapbase))
131
132 /* Current search index for the heap table. */
133 extern size_t _heapindex;
134
135 /* Limit of valid info table indices. */
136 extern size_t _heaplimit;
137
138 /* Doubly linked lists of free fragments. */
139 struct list
140 {
141 struct list *next;
142 struct list *prev;
143 };
144
145 /* Free list headers for each fragment size. */
146 extern struct list _fraghead[];
147
148 /* List of blocks allocated with `memalign' (or `valloc'). */
149 struct alignlist
150 {
151 struct alignlist *next;
152 void *aligned; /* The address that memaligned returned. */
153 void *exact; /* The address that malloc returned. */
154 };
155 extern struct alignlist *_aligned_blocks;
156
157 /* Instrumentation. */
158 extern size_t _chunks_used;
159 extern size_t _bytes_used;
160 extern size_t _chunks_free;
161 extern size_t _bytes_free;
162
163 /* Internal versions of `malloc', `realloc', and `free'
164 used when these functions need to call each other.
165 They are the same but don't call the hooks. */
166 extern void *_malloc_internal (size_t);
167 extern void *_realloc_internal (void *, size_t);
168 extern void _free_internal (void *);
169 extern void *_malloc_internal_nolock (size_t);
170 extern void *_realloc_internal_nolock (void *, size_t);
171 extern void _free_internal_nolock (void *);
172
173 #ifdef USE_PTHREAD
174 extern pthread_mutex_t _malloc_mutex, _aligned_blocks_mutex;
175 extern int _malloc_thread_enabled_p;
176 #define LOCK() \
177 do { \
178 if (_malloc_thread_enabled_p) \
179 pthread_mutex_lock (&_malloc_mutex); \
180 } while (0)
181 #define UNLOCK() \
182 do { \
183 if (_malloc_thread_enabled_p) \
184 pthread_mutex_unlock (&_malloc_mutex); \
185 } while (0)
186 #define LOCK_ALIGNED_BLOCKS() \
187 do { \
188 if (_malloc_thread_enabled_p) \
189 pthread_mutex_lock (&_aligned_blocks_mutex); \
190 } while (0)
191 #define UNLOCK_ALIGNED_BLOCKS() \
192 do { \
193 if (_malloc_thread_enabled_p) \
194 pthread_mutex_unlock (&_aligned_blocks_mutex); \
195 } while (0)
196 #else
197 #define LOCK()
198 #define UNLOCK()
199 #define LOCK_ALIGNED_BLOCKS()
200 #define UNLOCK_ALIGNED_BLOCKS()
201 #endif
202
203 /* Given an address in the middle of a malloc'd object,
204 return the address of the beginning of the object. */
205 extern void *malloc_find_object_address (void *ptr);
206
207 /* Underlying allocation function; successive calls should
208 return contiguous pieces of memory. */
209 extern void *(*__morecore) (ptrdiff_t size);
210
211 /* Default value of `__morecore'. */
212 extern void *__default_morecore (ptrdiff_t size);
213
214 /* If not NULL, this function is called after each time
215 `__morecore' is called to increase the data size. */
216 extern void (*__after_morecore_hook) (void);
217
218 /* Number of extra blocks to get each time we ask for more core.
219 This reduces the frequency of calling `(*__morecore)'. */
220 extern size_t __malloc_extra_blocks;
221
222 /* Nonzero if `malloc' has been called and done its initialization. */
223 extern int __malloc_initialized;
224 /* Function called to initialize malloc data structures. */
225 extern int __malloc_initialize (void);
226
227 /* Hooks for debugging versions. */
228 extern void (*__malloc_initialize_hook) (void);
229 extern void (*__free_hook) (void *ptr);
230 extern void *(*__malloc_hook) (size_t size);
231 extern void *(*__realloc_hook) (void *ptr, size_t size);
232 extern void *(*__memalign_hook) (size_t size, size_t alignment);
233
234 /* Return values for `mprobe': these are the kinds of inconsistencies that
235 `mcheck' enables detection of. */
236 enum mcheck_status
237 {
238 MCHECK_DISABLED = -1, /* Consistency checking is not turned on. */
239 MCHECK_OK, /* Block is fine. */
240 MCHECK_FREE, /* Block freed twice. */
241 MCHECK_HEAD, /* Memory before the block was clobbered. */
242 MCHECK_TAIL /* Memory after the block was clobbered. */
243 };
244
245 /* Activate a standard collection of debugging hooks. This must be called
246 before `malloc' is ever called. ABORTFUNC is called with an error code
247 (see enum above) when an inconsistency is detected. If ABORTFUNC is
248 null, the standard function prints on stderr and then calls `abort'. */
249 extern int mcheck (void (*abortfunc) (enum mcheck_status));
250
251 /* Check for aberrations in a particular malloc'd block. You must have
252 called `mcheck' already. These are the same checks that `mcheck' does
253 when you free or reallocate a block. */
254 extern enum mcheck_status mprobe (void *ptr);
255
256 /* Activate a standard collection of tracing hooks. */
257 extern void mtrace (void);
258 extern void muntrace (void);
259
260 /* Statistics available to the user. */
261 struct mstats
262 {
263 size_t bytes_total; /* Total size of the heap. */
264 size_t chunks_used; /* Chunks allocated by the user. */
265 size_t bytes_used; /* Byte total of user-allocated chunks. */
266 size_t chunks_free; /* Chunks in the free list. */
267 size_t bytes_free; /* Byte total of chunks in the free list. */
268 };
269
270 /* Pick up the current statistics. */
271 extern struct mstats mstats (void);
272
273 /* Call WARNFUN with a warning message when memory usage is high. */
274 extern void memory_warnings (void *start, void (*warnfun) (const char *));
275
276 #ifdef __cplusplus
277 }
278 #endif
279
280 /* Memory allocator `malloc'.
281 Copyright 1990, 1991, 1992, 1993, 1994, 1995 Free Software Foundation, Inc.
282 Written May 1989 by Mike Haertel.
283
284 This library is free software; you can redistribute it and/or
285 modify it under the terms of the GNU General Public License as
286 published by the Free Software Foundation; either version 2 of the
287 License, or (at your option) any later version.
288
289 This library is distributed in the hope that it will be useful,
290 but WITHOUT ANY WARRANTY; without even the implied warranty of
291 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
292 General Public License for more details.
293
294 You should have received a copy of the GNU General Public
295 License along with this library; see the file COPYING. If
296 not, write to the Free Software Foundation, Inc., 51 Franklin Street,
297 Fifth Floor, Boston, MA 02110-1301, USA.
298
299 The author may be reached (Email) at the address mike@ai.mit.edu,
300 or (US mail) as Mike Haertel c/o Free Software Foundation. */
301
302 #include <errno.h>
303
304 /* On Cygwin there are two heaps. temacs uses the static heap
305 (defined in sheap.c and managed with bss_sbrk), and the dumped
306 emacs uses the Cygwin heap (managed with sbrk). When emacs starts
307 on Cygwin, it reinitializes malloc, and we save the old info for
308 use by free and realloc if they're called with a pointer into the
309 static heap.
310
311 Currently (2011-08-16) the Cygwin build doesn't use ralloc.c; if
312 this is changed in the future, we'll have to similarly deal with
313 reinitializing ralloc. */
314 #ifdef CYGWIN
315 extern void *bss_sbrk (ptrdiff_t size);
316 extern int bss_sbrk_did_unexec;
317 char *bss_sbrk_heapbase; /* _heapbase for static heap */
318 malloc_info *bss_sbrk_heapinfo; /* _heapinfo for static heap */
319 #endif
320 void *(*__morecore) (ptrdiff_t size) = __default_morecore;
321
322 /* Debugging hook for `malloc'. */
323 void *(*__malloc_hook) (size_t size);
324
325 /* Pointer to the base of the first block. */
326 char *_heapbase;
327
328 /* Block information table. Allocated with align/__free (not malloc/free). */
329 malloc_info *_heapinfo;
330
331 /* Number of info entries. */
332 static size_t heapsize;
333
334 /* Search index in the info table. */
335 size_t _heapindex;
336
337 /* Limit of valid info table indices. */
338 size_t _heaplimit;
339
340 /* Free lists for each fragment size. */
341 struct list _fraghead[BLOCKLOG];
342
343 /* Instrumentation. */
344 size_t _chunks_used;
345 size_t _bytes_used;
346 size_t _chunks_free;
347 size_t _bytes_free;
348
349 /* Are you experienced? */
350 int __malloc_initialized;
351
352 size_t __malloc_extra_blocks;
353
354 void (*__malloc_initialize_hook) (void);
355 void (*__after_morecore_hook) (void);
356
357 #if defined GC_MALLOC_CHECK && defined GC_PROTECT_MALLOC_STATE
358
359 /* Some code for hunting a bug writing into _heapinfo.
360
361 Call this macro with argument PROT non-zero to protect internal
362 malloc state against writing to it, call it with a zero argument to
363 make it readable and writable.
364
365 Note that this only works if BLOCKSIZE == page size, which is
366 the case on the i386. */
367
368 #include <sys/types.h>
369 #include <sys/mman.h>
370
371 static int state_protected_p;
372 static size_t last_state_size;
373 static malloc_info *last_heapinfo;
374
375 void
376 protect_malloc_state (int protect_p)
377 {
378 /* If _heapinfo has been relocated, make sure its old location
379 isn't left read-only; it will be reused by malloc. */
380 if (_heapinfo != last_heapinfo
381 && last_heapinfo
382 && state_protected_p)
383 mprotect (last_heapinfo, last_state_size, PROT_READ | PROT_WRITE);
384
385 last_state_size = _heaplimit * sizeof *_heapinfo;
386 last_heapinfo = _heapinfo;
387
388 if (protect_p != state_protected_p)
389 {
390 state_protected_p = protect_p;
391 if (mprotect (_heapinfo, last_state_size,
392 protect_p ? PROT_READ : PROT_READ | PROT_WRITE) != 0)
393 abort ();
394 }
395 }
396
397 #define PROTECT_MALLOC_STATE(PROT) protect_malloc_state (PROT)
398
399 #else
400 #define PROTECT_MALLOC_STATE(PROT) /* empty */
401 #endif
402
403
404 /* Aligned allocation. */
405 static void *
406 align (size_t size)
407 {
408 void *result;
409 ptrdiff_t adj;
410
411 /* align accepts an unsigned argument, but __morecore accepts a
412 signed one. This could lead to trouble if SIZE overflows the
413 ptrdiff_t type accepted by __morecore. We just punt in that
414 case, since they are requesting a ludicrous amount anyway. */
415 if (PTRDIFF_MAX < size)
416 result = 0;
417 else
418 result = (*__morecore) (size);
419 adj = (uintptr_t) result % BLOCKSIZE;
420 if (adj != 0)
421 {
422 adj = BLOCKSIZE - adj;
423 (*__morecore) (adj);
424 result = (char *) result + adj;
425 }
426
427 if (__after_morecore_hook)
428 (*__after_morecore_hook) ();
429
430 return result;
431 }
432
433 /* Get SIZE bytes, if we can get them starting at END.
434 Return the address of the space we got.
435 If we cannot get space at END, fail and return 0. */
436 static void *
437 get_contiguous_space (ptrdiff_t size, void *position)
438 {
439 void *before;
440 void *after;
441
442 before = (*__morecore) (0);
443 /* If we can tell in advance that the break is at the wrong place,
444 fail now. */
445 if (before != position)
446 return 0;
447
448 /* Allocate SIZE bytes and get the address of them. */
449 after = (*__morecore) (size);
450 if (!after)
451 return 0;
452
453 /* It was not contiguous--reject it. */
454 if (after != position)
455 {
456 (*__morecore) (- size);
457 return 0;
458 }
459
460 return after;
461 }
462
463
464 /* This is called when `_heapinfo' and `heapsize' have just
465 been set to describe a new info table. Set up the table
466 to describe itself and account for it in the statistics. */
467 static void
468 register_heapinfo (void)
469 {
470 size_t block, blocks;
471
472 block = BLOCK (_heapinfo);
473 blocks = BLOCKIFY (heapsize * sizeof (malloc_info));
474
475 /* Account for the _heapinfo block itself in the statistics. */
476 _bytes_used += blocks * BLOCKSIZE;
477 ++_chunks_used;
478
479 /* Describe the heapinfo block itself in the heapinfo. */
480 _heapinfo[block].busy.type = 0;
481 _heapinfo[block].busy.info.size = blocks;
482 /* Leave back-pointers for malloc_find_address. */
483 while (--blocks > 0)
484 _heapinfo[block + blocks].busy.info.size = -blocks;
485 }
486
487 #ifdef USE_PTHREAD
488 pthread_mutex_t _malloc_mutex = PTHREAD_MUTEX_INITIALIZER;
489 pthread_mutex_t _aligned_blocks_mutex = PTHREAD_MUTEX_INITIALIZER;
490 int _malloc_thread_enabled_p;
491
492 static void
493 malloc_atfork_handler_prepare (void)
494 {
495 LOCK ();
496 LOCK_ALIGNED_BLOCKS ();
497 }
498
499 static void
500 malloc_atfork_handler_parent (void)
501 {
502 UNLOCK_ALIGNED_BLOCKS ();
503 UNLOCK ();
504 }
505
506 static void
507 malloc_atfork_handler_child (void)
508 {
509 UNLOCK_ALIGNED_BLOCKS ();
510 UNLOCK ();
511 }
512
513 /* Set up mutexes and make malloc etc. thread-safe. */
514 void
515 malloc_enable_thread (void)
516 {
517 if (_malloc_thread_enabled_p)
518 return;
519
520 /* Some pthread implementations call malloc for statically
521 initialized mutexes when they are used first. To avoid such a
522 situation, we initialize mutexes here while their use is
523 disabled in malloc etc. */
524 pthread_mutex_init (&_malloc_mutex, NULL);
525 pthread_mutex_init (&_aligned_blocks_mutex, NULL);
526 pthread_atfork (malloc_atfork_handler_prepare,
527 malloc_atfork_handler_parent,
528 malloc_atfork_handler_child);
529 _malloc_thread_enabled_p = 1;
530 }
531 #endif
532
533 static void
534 malloc_initialize_1 (void)
535 {
536 #ifdef GC_MCHECK
537 mcheck (NULL);
538 #endif
539
540 #ifdef CYGWIN
541 if (bss_sbrk_did_unexec)
542 /* we're reinitializing the dumped emacs */
543 {
544 bss_sbrk_heapbase = _heapbase;
545 bss_sbrk_heapinfo = _heapinfo;
546 memset (_fraghead, 0, BLOCKLOG * sizeof (struct list));
547 }
548 #endif
549
550 if (__malloc_initialize_hook)
551 (*__malloc_initialize_hook) ();
552
553 heapsize = HEAP / BLOCKSIZE;
554 _heapinfo = align (heapsize * sizeof (malloc_info));
555 if (_heapinfo == NULL)
556 return;
557 memset (_heapinfo, 0, heapsize * sizeof (malloc_info));
558 _heapinfo[0].free.size = 0;
559 _heapinfo[0].free.next = _heapinfo[0].free.prev = 0;
560 _heapindex = 0;
561 _heapbase = (char *) _heapinfo;
562 _heaplimit = BLOCK (_heapbase + heapsize * sizeof (malloc_info));
563
564 register_heapinfo ();
565
566 __malloc_initialized = 1;
567 PROTECT_MALLOC_STATE (1);
568 return;
569 }
570
571 /* Set everything up and remember that we have.
572 main will call malloc which calls this function. That is before any threads
573 or signal handlers has been set up, so we don't need thread protection. */
574 int
575 __malloc_initialize (void)
576 {
577 if (__malloc_initialized)
578 return 0;
579
580 malloc_initialize_1 ();
581
582 return __malloc_initialized;
583 }
584
585 static int morecore_recursing;
586
587 /* Get neatly aligned memory, initializing or
588 growing the heap info table as necessary. */
589 static void *
590 morecore_nolock (size_t size)
591 {
592 void *result;
593 malloc_info *newinfo, *oldinfo;
594 size_t newsize;
595
596 if (morecore_recursing)
597 /* Avoid recursion. The caller will know how to handle a null return. */
598 return NULL;
599
600 result = align (size);
601 if (result == NULL)
602 return NULL;
603
604 PROTECT_MALLOC_STATE (0);
605
606 /* Check if we need to grow the info table. */
607 if ((size_t) BLOCK ((char *) result + size) > heapsize)
608 {
609 /* Calculate the new _heapinfo table size. We do not account for the
610 added blocks in the table itself, as we hope to place them in
611 existing free space, which is already covered by part of the
612 existing table. */
613 newsize = heapsize;
614 do
615 newsize *= 2;
616 while ((size_t) BLOCK ((char *) result + size) > newsize);
617
618 /* We must not reuse existing core for the new info table when called
619 from realloc in the case of growing a large block, because the
620 block being grown is momentarily marked as free. In this case
621 _heaplimit is zero so we know not to reuse space for internal
622 allocation. */
623 if (_heaplimit != 0)
624 {
625 /* First try to allocate the new info table in core we already
626 have, in the usual way using realloc. If realloc cannot
627 extend it in place or relocate it to existing sufficient core,
628 we will get called again, and the code above will notice the
629 `morecore_recursing' flag and return null. */
630 int save = errno; /* Don't want to clobber errno with ENOMEM. */
631 morecore_recursing = 1;
632 newinfo = _realloc_internal_nolock (_heapinfo,
633 newsize * sizeof (malloc_info));
634 morecore_recursing = 0;
635 if (newinfo == NULL)
636 errno = save;
637 else
638 {
639 /* We found some space in core, and realloc has put the old
640 table's blocks on the free list. Now zero the new part
641 of the table and install the new table location. */
642 memset (&newinfo[heapsize], 0,
643 (newsize - heapsize) * sizeof (malloc_info));
644 _heapinfo = newinfo;
645 heapsize = newsize;
646 goto got_heap;
647 }
648 }
649
650 /* Allocate new space for the malloc info table. */
651 while (1)
652 {
653 newinfo = align (newsize * sizeof (malloc_info));
654
655 /* Did it fail? */
656 if (newinfo == NULL)
657 {
658 (*__morecore) (-size);
659 return NULL;
660 }
661
662 /* Is it big enough to record status for its own space?
663 If so, we win. */
664 if ((size_t) BLOCK ((char *) newinfo
665 + newsize * sizeof (malloc_info))
666 < newsize)
667 break;
668
669 /* Must try again. First give back most of what we just got. */
670 (*__morecore) (- newsize * sizeof (malloc_info));
671 newsize *= 2;
672 }
673
674 /* Copy the old table to the beginning of the new,
675 and zero the rest of the new table. */
676 memcpy (newinfo, _heapinfo, heapsize * sizeof (malloc_info));
677 memset (&newinfo[heapsize], 0,
678 (newsize - heapsize) * sizeof (malloc_info));
679 oldinfo = _heapinfo;
680 _heapinfo = newinfo;
681 heapsize = newsize;
682
683 register_heapinfo ();
684
685 /* Reset _heaplimit so _free_internal never decides
686 it can relocate or resize the info table. */
687 _heaplimit = 0;
688 _free_internal_nolock (oldinfo);
689 PROTECT_MALLOC_STATE (0);
690
691 /* The new heap limit includes the new table just allocated. */
692 _heaplimit = BLOCK ((char *) newinfo + heapsize * sizeof (malloc_info));
693 return result;
694 }
695
696 got_heap:
697 _heaplimit = BLOCK ((char *) result + size);
698 return result;
699 }
700
701 /* Allocate memory from the heap. */
702 void *
703 _malloc_internal_nolock (size_t size)
704 {
705 void *result;
706 size_t block, blocks, lastblocks, start;
707 register size_t i;
708 struct list *next;
709
710 /* ANSI C allows `malloc (0)' to either return NULL, or to return a
711 valid address you can realloc and free (though not dereference).
712
713 It turns out that some extant code (sunrpc, at least Ultrix's version)
714 expects `malloc (0)' to return non-NULL and breaks otherwise.
715 Be compatible. */
716
717 #if 0
718 if (size == 0)
719 return NULL;
720 #endif
721
722 PROTECT_MALLOC_STATE (0);
723
724 if (size < sizeof (struct list))
725 size = sizeof (struct list);
726
727 /* Determine the allocation policy based on the request size. */
728 if (size <= BLOCKSIZE / 2)
729 {
730 /* Small allocation to receive a fragment of a block.
731 Determine the logarithm to base two of the fragment size. */
732 register size_t log = 1;
733 --size;
734 while ((size /= 2) != 0)
735 ++log;
736
737 /* Look in the fragment lists for a
738 free fragment of the desired size. */
739 next = _fraghead[log].next;
740 if (next != NULL)
741 {
742 /* There are free fragments of this size.
743 Pop a fragment out of the fragment list and return it.
744 Update the block's nfree and first counters. */
745 result = next;
746 next->prev->next = next->next;
747 if (next->next != NULL)
748 next->next->prev = next->prev;
749 block = BLOCK (result);
750 if (--_heapinfo[block].busy.info.frag.nfree != 0)
751 _heapinfo[block].busy.info.frag.first =
752 (uintptr_t) next->next % BLOCKSIZE >> log;
753
754 /* Update the statistics. */
755 ++_chunks_used;
756 _bytes_used += 1 << log;
757 --_chunks_free;
758 _bytes_free -= 1 << log;
759 }
760 else
761 {
762 /* No free fragments of the desired size, so get a new block
763 and break it into fragments, returning the first. */
764 #ifdef GC_MALLOC_CHECK
765 result = _malloc_internal_nolock (BLOCKSIZE);
766 PROTECT_MALLOC_STATE (0);
767 #elif defined (USE_PTHREAD)
768 result = _malloc_internal_nolock (BLOCKSIZE);
769 #else
770 result = malloc (BLOCKSIZE);
771 #endif
772 if (result == NULL)
773 {
774 PROTECT_MALLOC_STATE (1);
775 goto out;
776 }
777
778 /* Link all fragments but the first into the free list. */
779 next = (struct list *) ((char *) result + (1 << log));
780 next->next = NULL;
781 next->prev = &_fraghead[log];
782 _fraghead[log].next = next;
783
784 for (i = 2; i < (size_t) (BLOCKSIZE >> log); ++i)
785 {
786 next = (struct list *) ((char *) result + (i << log));
787 next->next = _fraghead[log].next;
788 next->prev = &_fraghead[log];
789 next->prev->next = next;
790 next->next->prev = next;
791 }
792
793 /* Initialize the nfree and first counters for this block. */
794 block = BLOCK (result);
795 _heapinfo[block].busy.type = log;
796 _heapinfo[block].busy.info.frag.nfree = i - 1;
797 _heapinfo[block].busy.info.frag.first = i - 1;
798
799 _chunks_free += (BLOCKSIZE >> log) - 1;
800 _bytes_free += BLOCKSIZE - (1 << log);
801 _bytes_used -= BLOCKSIZE - (1 << log);
802 }
803 }
804 else
805 {
806 /* Large allocation to receive one or more blocks.
807 Search the free list in a circle starting at the last place visited.
808 If we loop completely around without finding a large enough
809 space we will have to get more memory from the system. */
810 blocks = BLOCKIFY (size);
811 start = block = _heapindex;
812 while (_heapinfo[block].free.size < blocks)
813 {
814 block = _heapinfo[block].free.next;
815 if (block == start)
816 {
817 /* Need to get more from the system. Get a little extra. */
818 size_t wantblocks = blocks + __malloc_extra_blocks;
819 block = _heapinfo[0].free.prev;
820 lastblocks = _heapinfo[block].free.size;
821 /* Check to see if the new core will be contiguous with the
822 final free block; if so we don't need to get as much. */
823 if (_heaplimit != 0 && block + lastblocks == _heaplimit &&
824 /* We can't do this if we will have to make the heap info
825 table bigger to accommodate the new space. */
826 block + wantblocks <= heapsize &&
827 get_contiguous_space ((wantblocks - lastblocks) * BLOCKSIZE,
828 ADDRESS (block + lastblocks)))
829 {
830 /* We got it contiguously. Which block we are extending
831 (the `final free block' referred to above) might have
832 changed, if it got combined with a freed info table. */
833 block = _heapinfo[0].free.prev;
834 _heapinfo[block].free.size += (wantblocks - lastblocks);
835 _bytes_free += (wantblocks - lastblocks) * BLOCKSIZE;
836 _heaplimit += wantblocks - lastblocks;
837 continue;
838 }
839 result = morecore_nolock (wantblocks * BLOCKSIZE);
840 if (result == NULL)
841 goto out;
842 block = BLOCK (result);
843 /* Put the new block at the end of the free list. */
844 _heapinfo[block].free.size = wantblocks;
845 _heapinfo[block].free.prev = _heapinfo[0].free.prev;
846 _heapinfo[block].free.next = 0;
847 _heapinfo[0].free.prev = block;
848 _heapinfo[_heapinfo[block].free.prev].free.next = block;
849 ++_chunks_free;
850 /* Now loop to use some of that block for this allocation. */
851 }
852 }
853
854 /* At this point we have found a suitable free list entry.
855 Figure out how to remove what we need from the list. */
856 result = ADDRESS (block);
857 if (_heapinfo[block].free.size > blocks)
858 {
859 /* The block we found has a bit left over,
860 so relink the tail end back into the free list. */
861 _heapinfo[block + blocks].free.size
862 = _heapinfo[block].free.size - blocks;
863 _heapinfo[block + blocks].free.next
864 = _heapinfo[block].free.next;
865 _heapinfo[block + blocks].free.prev
866 = _heapinfo[block].free.prev;
867 _heapinfo[_heapinfo[block].free.prev].free.next
868 = _heapinfo[_heapinfo[block].free.next].free.prev
869 = _heapindex = block + blocks;
870 }
871 else
872 {
873 /* The block exactly matches our requirements,
874 so just remove it from the list. */
875 _heapinfo[_heapinfo[block].free.next].free.prev
876 = _heapinfo[block].free.prev;
877 _heapinfo[_heapinfo[block].free.prev].free.next
878 = _heapindex = _heapinfo[block].free.next;
879 --_chunks_free;
880 }
881
882 _heapinfo[block].busy.type = 0;
883 _heapinfo[block].busy.info.size = blocks;
884 ++_chunks_used;
885 _bytes_used += blocks * BLOCKSIZE;
886 _bytes_free -= blocks * BLOCKSIZE;
887
888 /* Mark all the blocks of the object just allocated except for the
889 first with a negative number so you can find the first block by
890 adding that adjustment. */
891 while (--blocks > 0)
892 _heapinfo[block + blocks].busy.info.size = -blocks;
893 }
894
895 PROTECT_MALLOC_STATE (1);
896 out:
897 return result;
898 }
899
900 void *
901 _malloc_internal (size_t size)
902 {
903 void *result;
904
905 LOCK ();
906 result = _malloc_internal_nolock (size);
907 UNLOCK ();
908
909 return result;
910 }
911
912 void *
913 malloc (size_t size)
914 {
915 void *(*hook) (size_t);
916
917 if (!__malloc_initialized && !__malloc_initialize ())
918 return NULL;
919
920 /* Copy the value of __malloc_hook to an automatic variable in case
921 __malloc_hook is modified in another thread between its
922 NULL-check and the use.
923
924 Note: Strictly speaking, this is not a right solution. We should
925 use mutexes to access non-read-only variables that are shared
926 among multiple threads. We just leave it for compatibility with
927 glibc malloc (i.e., assignments to __malloc_hook) for now. */
928 hook = __malloc_hook;
929 return (hook != NULL ? *hook : _malloc_internal) (size);
930 }
931 \f
932 #ifndef _LIBC
933
934 /* On some ANSI C systems, some libc functions call _malloc, _free
935 and _realloc. Make them use the GNU functions. */
936
937 extern void *_malloc (size_t);
938 extern void _free (void *);
939 extern void *_realloc (void *, size_t);
940
941 void *
942 _malloc (size_t size)
943 {
944 return malloc (size);
945 }
946
947 void
948 _free (void *ptr)
949 {
950 free (ptr);
951 }
952
953 void *
954 _realloc (void *ptr, size_t size)
955 {
956 return realloc (ptr, size);
957 }
958
959 #endif
960 /* Free a block of memory allocated by `malloc'.
961 Copyright 1990, 1991, 1992, 1994, 1995 Free Software Foundation, Inc.
962 Written May 1989 by Mike Haertel.
963
964 This library is free software; you can redistribute it and/or
965 modify it under the terms of the GNU General Public License as
966 published by the Free Software Foundation; either version 2 of the
967 License, or (at your option) any later version.
968
969 This library is distributed in the hope that it will be useful,
970 but WITHOUT ANY WARRANTY; without even the implied warranty of
971 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
972 General Public License for more details.
973
974 You should have received a copy of the GNU General Public
975 License along with this library; see the file COPYING. If
976 not, write to the Free Software Foundation, Inc., 51 Franklin Street,
977 Fifth Floor, Boston, MA 02110-1301, USA.
978
979 The author may be reached (Email) at the address mike@ai.mit.edu,
980 or (US mail) as Mike Haertel c/o Free Software Foundation. */
981
982
983 /* Debugging hook for free. */
984 void (*__free_hook) (void *__ptr);
985
986 /* List of blocks allocated by memalign. */
987 struct alignlist *_aligned_blocks = NULL;
988
989 /* Return memory to the heap.
990 Like `_free_internal' but don't lock mutex. */
991 void
992 _free_internal_nolock (void *ptr)
993 {
994 int type;
995 size_t block, blocks;
996 register size_t i;
997 struct list *prev, *next;
998 void *curbrk;
999 const size_t lesscore_threshold
1000 /* Threshold of free space at which we will return some to the system. */
1001 = FINAL_FREE_BLOCKS + 2 * __malloc_extra_blocks;
1002
1003 register struct alignlist *l;
1004
1005 if (ptr == NULL)
1006 return;
1007
1008 #ifdef CYGWIN
1009 if ((char *) ptr < _heapbase)
1010 /* We're being asked to free something in the static heap. */
1011 return;
1012 #endif
1013
1014 PROTECT_MALLOC_STATE (0);
1015
1016 LOCK_ALIGNED_BLOCKS ();
1017 for (l = _aligned_blocks; l != NULL; l = l->next)
1018 if (l->aligned == ptr)
1019 {
1020 l->aligned = NULL; /* Mark the slot in the list as free. */
1021 ptr = l->exact;
1022 break;
1023 }
1024 UNLOCK_ALIGNED_BLOCKS ();
1025
1026 block = BLOCK (ptr);
1027
1028 type = _heapinfo[block].busy.type;
1029 switch (type)
1030 {
1031 case 0:
1032 /* Get as many statistics as early as we can. */
1033 --_chunks_used;
1034 _bytes_used -= _heapinfo[block].busy.info.size * BLOCKSIZE;
1035 _bytes_free += _heapinfo[block].busy.info.size * BLOCKSIZE;
1036
1037 /* Find the free cluster previous to this one in the free list.
1038 Start searching at the last block referenced; this may benefit
1039 programs with locality of allocation. */
1040 i = _heapindex;
1041 if (i > block)
1042 while (i > block)
1043 i = _heapinfo[i].free.prev;
1044 else
1045 {
1046 do
1047 i = _heapinfo[i].free.next;
1048 while (i > 0 && i < block);
1049 i = _heapinfo[i].free.prev;
1050 }
1051
1052 /* Determine how to link this block into the free list. */
1053 if (block == i + _heapinfo[i].free.size)
1054 {
1055 /* Coalesce this block with its predecessor. */
1056 _heapinfo[i].free.size += _heapinfo[block].busy.info.size;
1057 block = i;
1058 }
1059 else
1060 {
1061 /* Really link this block back into the free list. */
1062 _heapinfo[block].free.size = _heapinfo[block].busy.info.size;
1063 _heapinfo[block].free.next = _heapinfo[i].free.next;
1064 _heapinfo[block].free.prev = i;
1065 _heapinfo[i].free.next = block;
1066 _heapinfo[_heapinfo[block].free.next].free.prev = block;
1067 ++_chunks_free;
1068 }
1069
1070 /* Now that the block is linked in, see if we can coalesce it
1071 with its successor (by deleting its successor from the list
1072 and adding in its size). */
1073 if (block + _heapinfo[block].free.size == _heapinfo[block].free.next)
1074 {
1075 _heapinfo[block].free.size
1076 += _heapinfo[_heapinfo[block].free.next].free.size;
1077 _heapinfo[block].free.next
1078 = _heapinfo[_heapinfo[block].free.next].free.next;
1079 _heapinfo[_heapinfo[block].free.next].free.prev = block;
1080 --_chunks_free;
1081 }
1082
1083 /* How many trailing free blocks are there now? */
1084 blocks = _heapinfo[block].free.size;
1085
1086 /* Where is the current end of accessible core? */
1087 curbrk = (*__morecore) (0);
1088
1089 if (_heaplimit != 0 && curbrk == ADDRESS (_heaplimit))
1090 {
1091 /* The end of the malloc heap is at the end of accessible core.
1092 It's possible that moving _heapinfo will allow us to
1093 return some space to the system. */
1094
1095 size_t info_block = BLOCK (_heapinfo);
1096 size_t info_blocks = _heapinfo[info_block].busy.info.size;
1097 size_t prev_block = _heapinfo[block].free.prev;
1098 size_t prev_blocks = _heapinfo[prev_block].free.size;
1099 size_t next_block = _heapinfo[block].free.next;
1100 size_t next_blocks = _heapinfo[next_block].free.size;
1101
1102 if (/* Win if this block being freed is last in core, the info table
1103 is just before it, the previous free block is just before the
1104 info table, and the two free blocks together form a useful
1105 amount to return to the system. */
1106 (block + blocks == _heaplimit &&
1107 info_block + info_blocks == block &&
1108 prev_block != 0 && prev_block + prev_blocks == info_block &&
1109 blocks + prev_blocks >= lesscore_threshold) ||
1110 /* Nope, not the case. We can also win if this block being
1111 freed is just before the info table, and the table extends
1112 to the end of core or is followed only by a free block,
1113 and the total free space is worth returning to the system. */
1114 (block + blocks == info_block &&
1115 ((info_block + info_blocks == _heaplimit &&
1116 blocks >= lesscore_threshold) ||
1117 (info_block + info_blocks == next_block &&
1118 next_block + next_blocks == _heaplimit &&
1119 blocks + next_blocks >= lesscore_threshold)))
1120 )
1121 {
1122 malloc_info *newinfo;
1123 size_t oldlimit = _heaplimit;
1124
1125 /* Free the old info table, clearing _heaplimit to avoid
1126 recursion into this code. We don't want to return the
1127 table's blocks to the system before we have copied them to
1128 the new location. */
1129 _heaplimit = 0;
1130 _free_internal_nolock (_heapinfo);
1131 _heaplimit = oldlimit;
1132
1133 /* Tell malloc to search from the beginning of the heap for
1134 free blocks, so it doesn't reuse the ones just freed. */
1135 _heapindex = 0;
1136
1137 /* Allocate new space for the info table and move its data. */
1138 newinfo = _malloc_internal_nolock (info_blocks * BLOCKSIZE);
1139 PROTECT_MALLOC_STATE (0);
1140 memmove (newinfo, _heapinfo, info_blocks * BLOCKSIZE);
1141 _heapinfo = newinfo;
1142
1143 /* We should now have coalesced the free block with the
1144 blocks freed from the old info table. Examine the entire
1145 trailing free block to decide below whether to return some
1146 to the system. */
1147 block = _heapinfo[0].free.prev;
1148 blocks = _heapinfo[block].free.size;
1149 }
1150
1151 /* Now see if we can return stuff to the system. */
1152 if (block + blocks == _heaplimit && blocks >= lesscore_threshold)
1153 {
1154 register size_t bytes = blocks * BLOCKSIZE;
1155 _heaplimit -= blocks;
1156 (*__morecore) (-bytes);
1157 _heapinfo[_heapinfo[block].free.prev].free.next
1158 = _heapinfo[block].free.next;
1159 _heapinfo[_heapinfo[block].free.next].free.prev
1160 = _heapinfo[block].free.prev;
1161 block = _heapinfo[block].free.prev;
1162 --_chunks_free;
1163 _bytes_free -= bytes;
1164 }
1165 }
1166
1167 /* Set the next search to begin at this block. */
1168 _heapindex = block;
1169 break;
1170
1171 default:
1172 /* Do some of the statistics. */
1173 --_chunks_used;
1174 _bytes_used -= 1 << type;
1175 ++_chunks_free;
1176 _bytes_free += 1 << type;
1177
1178 /* Get the address of the first free fragment in this block. */
1179 prev = (struct list *) ((char *) ADDRESS (block) +
1180 (_heapinfo[block].busy.info.frag.first << type));
1181
1182 if (_heapinfo[block].busy.info.frag.nfree == (BLOCKSIZE >> type) - 1)
1183 {
1184 /* If all fragments of this block are free, remove them
1185 from the fragment list and free the whole block. */
1186 next = prev;
1187 for (i = 1; i < (size_t) (BLOCKSIZE >> type); ++i)
1188 next = next->next;
1189 prev->prev->next = next;
1190 if (next != NULL)
1191 next->prev = prev->prev;
1192 _heapinfo[block].busy.type = 0;
1193 _heapinfo[block].busy.info.size = 1;
1194
1195 /* Keep the statistics accurate. */
1196 ++_chunks_used;
1197 _bytes_used += BLOCKSIZE;
1198 _chunks_free -= BLOCKSIZE >> type;
1199 _bytes_free -= BLOCKSIZE;
1200
1201 #if defined (GC_MALLOC_CHECK) || defined (USE_PTHREAD)
1202 _free_internal_nolock (ADDRESS (block));
1203 #else
1204 free (ADDRESS (block));
1205 #endif
1206 }
1207 else if (_heapinfo[block].busy.info.frag.nfree != 0)
1208 {
1209 /* If some fragments of this block are free, link this
1210 fragment into the fragment list after the first free
1211 fragment of this block. */
1212 next = ptr;
1213 next->next = prev->next;
1214 next->prev = prev;
1215 prev->next = next;
1216 if (next->next != NULL)
1217 next->next->prev = next;
1218 ++_heapinfo[block].busy.info.frag.nfree;
1219 }
1220 else
1221 {
1222 /* No fragments of this block are free, so link this
1223 fragment into the fragment list and announce that
1224 it is the first free fragment of this block. */
1225 prev = ptr;
1226 _heapinfo[block].busy.info.frag.nfree = 1;
1227 _heapinfo[block].busy.info.frag.first =
1228 (uintptr_t) ptr % BLOCKSIZE >> type;
1229 prev->next = _fraghead[type].next;
1230 prev->prev = &_fraghead[type];
1231 prev->prev->next = prev;
1232 if (prev->next != NULL)
1233 prev->next->prev = prev;
1234 }
1235 break;
1236 }
1237
1238 PROTECT_MALLOC_STATE (1);
1239 }
1240
1241 /* Return memory to the heap.
1242 Like `free' but don't call a __free_hook if there is one. */
1243 void
1244 _free_internal (void *ptr)
1245 {
1246 LOCK ();
1247 _free_internal_nolock (ptr);
1248 UNLOCK ();
1249 }
1250
1251 /* Return memory to the heap. */
1252
1253 void
1254 free (void *ptr)
1255 {
1256 void (*hook) (void *) = __free_hook;
1257
1258 if (hook != NULL)
1259 (*hook) (ptr);
1260 else
1261 _free_internal (ptr);
1262 }
1263
1264 /* Define the `cfree' alias for `free'. */
1265 #ifdef weak_alias
1266 weak_alias (free, cfree)
1267 #else
1268 void
1269 cfree (void *ptr)
1270 {
1271 free (ptr);
1272 }
1273 #endif
1274 /* Change the size of a block allocated by `malloc'.
1275 Copyright 1990, 1991, 1992, 1993, 1994, 1995 Free Software Foundation, Inc.
1276 Written May 1989 by Mike Haertel.
1277
1278 This library is free software; you can redistribute it and/or
1279 modify it under the terms of the GNU General Public License as
1280 published by the Free Software Foundation; either version 2 of the
1281 License, or (at your option) any later version.
1282
1283 This library is distributed in the hope that it will be useful,
1284 but WITHOUT ANY WARRANTY; without even the implied warranty of
1285 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1286 General Public License for more details.
1287
1288 You should have received a copy of the GNU General Public
1289 License along with this library; see the file COPYING. If
1290 not, write to the Free Software Foundation, Inc., 51 Franklin Street,
1291 Fifth Floor, Boston, MA 02110-1301, USA.
1292
1293 The author may be reached (Email) at the address mike@ai.mit.edu,
1294 or (US mail) as Mike Haertel c/o Free Software Foundation. */
1295
1296 #ifndef min
1297 #define min(A, B) ((A) < (B) ? (A) : (B))
1298 #endif
1299
1300 /* On Cygwin the dumped emacs may try to realloc storage allocated in
1301 the static heap. We just malloc space in the new heap and copy the
1302 data. */
1303 #ifdef CYGWIN
1304 void *
1305 special_realloc (void *ptr, size_t size)
1306 {
1307 void *result;
1308 int type;
1309 size_t block, oldsize;
1310
1311 block = ((char *) ptr - bss_sbrk_heapbase) / BLOCKSIZE + 1;
1312 type = bss_sbrk_heapinfo[block].busy.type;
1313 oldsize =
1314 type == 0 ? bss_sbrk_heapinfo[block].busy.info.size * BLOCKSIZE
1315 : (size_t) 1 << type;
1316 result = _malloc_internal_nolock (size);
1317 if (result != NULL)
1318 memcpy (result, ptr, min (oldsize, size));
1319 return result;
1320 }
1321 #endif
1322
1323 /* Debugging hook for realloc. */
1324 void *(*__realloc_hook) (void *ptr, size_t size);
1325
1326 /* Resize the given region to the new size, returning a pointer
1327 to the (possibly moved) region. This is optimized for speed;
1328 some benchmarks seem to indicate that greater compactness is
1329 achieved by unconditionally allocating and copying to a
1330 new region. This module has incestuous knowledge of the
1331 internals of both free and malloc. */
1332 void *
1333 _realloc_internal_nolock (void *ptr, size_t size)
1334 {
1335 void *result;
1336 int type;
1337 size_t block, blocks, oldlimit;
1338
1339 if (size == 0)
1340 {
1341 _free_internal_nolock (ptr);
1342 return _malloc_internal_nolock (0);
1343 }
1344 else if (ptr == NULL)
1345 return _malloc_internal_nolock (size);
1346
1347 #ifdef CYGWIN
1348 if ((char *) ptr < _heapbase)
1349 /* ptr points into the static heap */
1350 return special_realloc (ptr, size);
1351 #endif
1352
1353 block = BLOCK (ptr);
1354
1355 PROTECT_MALLOC_STATE (0);
1356
1357 type = _heapinfo[block].busy.type;
1358 switch (type)
1359 {
1360 case 0:
1361 /* Maybe reallocate a large block to a small fragment. */
1362 if (size <= BLOCKSIZE / 2)
1363 {
1364 result = _malloc_internal_nolock (size);
1365 if (result != NULL)
1366 {
1367 memcpy (result, ptr, size);
1368 _free_internal_nolock (ptr);
1369 goto out;
1370 }
1371 }
1372
1373 /* The new size is a large allocation as well;
1374 see if we can hold it in place. */
1375 blocks = BLOCKIFY (size);
1376 if (blocks < _heapinfo[block].busy.info.size)
1377 {
1378 /* The new size is smaller; return
1379 excess memory to the free list. */
1380 _heapinfo[block + blocks].busy.type = 0;
1381 _heapinfo[block + blocks].busy.info.size
1382 = _heapinfo[block].busy.info.size - blocks;
1383 _heapinfo[block].busy.info.size = blocks;
1384 /* We have just created a new chunk by splitting a chunk in two.
1385 Now we will free this chunk; increment the statistics counter
1386 so it doesn't become wrong when _free_internal decrements it. */
1387 ++_chunks_used;
1388 _free_internal_nolock (ADDRESS (block + blocks));
1389 result = ptr;
1390 }
1391 else if (blocks == _heapinfo[block].busy.info.size)
1392 /* No size change necessary. */
1393 result = ptr;
1394 else
1395 {
1396 /* Won't fit, so allocate a new region that will.
1397 Free the old region first in case there is sufficient
1398 adjacent free space to grow without moving. */
1399 blocks = _heapinfo[block].busy.info.size;
1400 /* Prevent free from actually returning memory to the system. */
1401 oldlimit = _heaplimit;
1402 _heaplimit = 0;
1403 _free_internal_nolock (ptr);
1404 result = _malloc_internal_nolock (size);
1405 PROTECT_MALLOC_STATE (0);
1406 if (_heaplimit == 0)
1407 _heaplimit = oldlimit;
1408 if (result == NULL)
1409 {
1410 /* Now we're really in trouble. We have to unfree
1411 the thing we just freed. Unfortunately it might
1412 have been coalesced with its neighbors. */
1413 if (_heapindex == block)
1414 (void) _malloc_internal_nolock (blocks * BLOCKSIZE);
1415 else
1416 {
1417 void *previous
1418 = _malloc_internal_nolock ((block - _heapindex) * BLOCKSIZE);
1419 (void) _malloc_internal_nolock (blocks * BLOCKSIZE);
1420 _free_internal_nolock (previous);
1421 }
1422 goto out;
1423 }
1424 if (ptr != result)
1425 memmove (result, ptr, blocks * BLOCKSIZE);
1426 }
1427 break;
1428
1429 default:
1430 /* Old size is a fragment; type is logarithm
1431 to base two of the fragment size. */
1432 if (size > (size_t) (1 << (type - 1)) &&
1433 size <= (size_t) (1 << type))
1434 /* The new size is the same kind of fragment. */
1435 result = ptr;
1436 else
1437 {
1438 /* The new size is different; allocate a new space,
1439 and copy the lesser of the new size and the old. */
1440 result = _malloc_internal_nolock (size);
1441 if (result == NULL)
1442 goto out;
1443 memcpy (result, ptr, min (size, (size_t) 1 << type));
1444 _free_internal_nolock (ptr);
1445 }
1446 break;
1447 }
1448
1449 PROTECT_MALLOC_STATE (1);
1450 out:
1451 return result;
1452 }
1453
1454 void *
1455 _realloc_internal (void *ptr, size_t size)
1456 {
1457 void *result;
1458
1459 LOCK ();
1460 result = _realloc_internal_nolock (ptr, size);
1461 UNLOCK ();
1462
1463 return result;
1464 }
1465
1466 void *
1467 realloc (void *ptr, size_t size)
1468 {
1469 void *(*hook) (void *, size_t);
1470
1471 if (!__malloc_initialized && !__malloc_initialize ())
1472 return NULL;
1473
1474 hook = __realloc_hook;
1475 return (hook != NULL ? *hook : _realloc_internal) (ptr, size);
1476 }
1477 /* Copyright (C) 1991, 1992, 1994 Free Software Foundation, Inc.
1478
1479 This library is free software; you can redistribute it and/or
1480 modify it under the terms of the GNU General Public License as
1481 published by the Free Software Foundation; either version 2 of the
1482 License, or (at your option) any later version.
1483
1484 This library is distributed in the hope that it will be useful,
1485 but WITHOUT ANY WARRANTY; without even the implied warranty of
1486 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1487 General Public License for more details.
1488
1489 You should have received a copy of the GNU General Public
1490 License along with this library; see the file COPYING. If
1491 not, write to the Free Software Foundation, Inc., 51 Franklin Street,
1492 Fifth Floor, Boston, MA 02110-1301, USA.
1493
1494 The author may be reached (Email) at the address mike@ai.mit.edu,
1495 or (US mail) as Mike Haertel c/o Free Software Foundation. */
1496
1497 /* Allocate an array of NMEMB elements each SIZE bytes long.
1498 The entire array is initialized to zeros. */
1499 void *
1500 calloc (register size_t nmemb, register size_t size)
1501 {
1502 register void *result = malloc (nmemb * size);
1503
1504 if (result != NULL)
1505 (void) memset (result, 0, nmemb * size);
1506
1507 return result;
1508 }
1509 /* Copyright (C) 1991, 1992, 1993, 1994, 1995 Free Software Foundation, Inc.
1510 This file is part of the GNU C Library.
1511
1512 The GNU C Library is free software; you can redistribute it and/or modify
1513 it under the terms of the GNU General Public License as published by
1514 the Free Software Foundation; either version 2, or (at your option)
1515 any later version.
1516
1517 The GNU C Library is distributed in the hope that it will be useful,
1518 but WITHOUT ANY WARRANTY; without even the implied warranty of
1519 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1520 GNU General Public License for more details.
1521
1522 You should have received a copy of the GNU General Public License
1523 along with the GNU C Library; see the file COPYING. If not, write to
1524 the Free Software Foundation, 51 Franklin Street, Fifth Floor, Boston,
1525 MA 02110-1301, USA. */
1526
1527 /* uClibc defines __GNU_LIBRARY__, but it is not completely
1528 compatible. */
1529 #if !defined (__GNU_LIBRARY__) || defined (__UCLIBC__)
1530 #define __sbrk sbrk
1531 #else /* __GNU_LIBRARY__ && ! defined (__UCLIBC__) */
1532 /* It is best not to declare this and cast its result on foreign operating
1533 systems with potentially hostile include files. */
1534
1535 extern void *__sbrk (ptrdiff_t increment);
1536 #endif /* __GNU_LIBRARY__ && ! defined (__UCLIBC__) */
1537
1538 /* Allocate INCREMENT more bytes of data space,
1539 and return the start of data space, or NULL on errors.
1540 If INCREMENT is negative, shrink data space. */
1541 void *
1542 __default_morecore (ptrdiff_t increment)
1543 {
1544 void *result;
1545 #if defined (CYGWIN)
1546 if (!bss_sbrk_did_unexec)
1547 {
1548 return bss_sbrk (increment);
1549 }
1550 #endif
1551 result = (void *) __sbrk (increment);
1552 if (result == (void *) -1)
1553 return NULL;
1554 return result;
1555 }
1556 /* Copyright (C) 1991, 92, 93, 94, 95, 96 Free Software Foundation, Inc.
1557
1558 This library is free software; you can redistribute it and/or
1559 modify it under the terms of the GNU General Public License as
1560 published by the Free Software Foundation; either version 2 of the
1561 License, or (at your option) any later version.
1562
1563 This library is distributed in the hope that it will be useful,
1564 but WITHOUT ANY WARRANTY; without even the implied warranty of
1565 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1566 General Public License for more details.
1567
1568 You should have received a copy of the GNU General Public
1569 License along with this library; see the file COPYING. If
1570 not, write to the Free Software Foundation, Inc., 51 Franklin Street,
1571 Fifth Floor, Boston, MA 02110-1301, USA. */
1572
1573 void *(*__memalign_hook) (size_t size, size_t alignment);
1574
1575 void *
1576 memalign (size_t alignment, size_t size)
1577 {
1578 void *result;
1579 size_t adj, lastadj;
1580 void *(*hook) (size_t, size_t) = __memalign_hook;
1581
1582 if (hook)
1583 return (*hook) (alignment, size);
1584
1585 /* Allocate a block with enough extra space to pad the block with up to
1586 (ALIGNMENT - 1) bytes if necessary. */
1587 result = malloc (size + alignment - 1);
1588 if (result == NULL)
1589 return NULL;
1590
1591 /* Figure out how much we will need to pad this particular block
1592 to achieve the required alignment. */
1593 adj = (uintptr_t) result % alignment;
1594
1595 do
1596 {
1597 /* Reallocate the block with only as much excess as it needs. */
1598 free (result);
1599 result = malloc (adj + size);
1600 if (result == NULL) /* Impossible unless interrupted. */
1601 return NULL;
1602
1603 lastadj = adj;
1604 adj = (uintptr_t) result % alignment;
1605 /* It's conceivable we might have been so unlucky as to get a
1606 different block with weaker alignment. If so, this block is too
1607 short to contain SIZE after alignment correction. So we must
1608 try again and get another block, slightly larger. */
1609 } while (adj > lastadj);
1610
1611 if (adj != 0)
1612 {
1613 /* Record this block in the list of aligned blocks, so that `free'
1614 can identify the pointer it is passed, which will be in the middle
1615 of an allocated block. */
1616
1617 struct alignlist *l;
1618 LOCK_ALIGNED_BLOCKS ();
1619 for (l = _aligned_blocks; l != NULL; l = l->next)
1620 if (l->aligned == NULL)
1621 /* This slot is free. Use it. */
1622 break;
1623 if (l == NULL)
1624 {
1625 l = malloc (sizeof *l);
1626 if (l != NULL)
1627 {
1628 l->next = _aligned_blocks;
1629 _aligned_blocks = l;
1630 }
1631 }
1632 if (l != NULL)
1633 {
1634 l->exact = result;
1635 result = l->aligned = (char *) result + alignment - adj;
1636 }
1637 UNLOCK_ALIGNED_BLOCKS ();
1638 if (l == NULL)
1639 {
1640 free (result);
1641 result = NULL;
1642 }
1643 }
1644
1645 return result;
1646 }
1647
1648 int
1649 posix_memalign (void **memptr, size_t alignment, size_t size)
1650 {
1651 void *mem;
1652
1653 if (alignment == 0
1654 || alignment % sizeof (void *) != 0
1655 || (alignment & (alignment - 1)) != 0)
1656 return EINVAL;
1657
1658 mem = memalign (alignment, size);
1659 if (mem == NULL)
1660 return ENOMEM;
1661
1662 *memptr = mem;
1663
1664 return 0;
1665 }
1666
1667 /* Allocate memory on a page boundary.
1668 Copyright (C) 1991, 92, 93, 94, 96 Free Software Foundation, Inc.
1669
1670 This library is free software; you can redistribute it and/or
1671 modify it under the terms of the GNU General Public License as
1672 published by the Free Software Foundation; either version 2 of the
1673 License, or (at your option) any later version.
1674
1675 This library is distributed in the hope that it will be useful,
1676 but WITHOUT ANY WARRANTY; without even the implied warranty of
1677 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1678 General Public License for more details.
1679
1680 You should have received a copy of the GNU General Public
1681 License along with this library; see the file COPYING. If
1682 not, write to the Free Software Foundation, Inc., 51 Franklin Street,
1683 Fifth Floor, Boston, MA 02110-1301, USA.
1684
1685 The author may be reached (Email) at the address mike@ai.mit.edu,
1686 or (US mail) as Mike Haertel c/o Free Software Foundation. */
1687
1688 /* Allocate SIZE bytes on a page boundary. */
1689 extern void *valloc (size_t);
1690
1691 #if defined _SC_PAGESIZE || !defined HAVE_GETPAGESIZE
1692 # include "getpagesize.h"
1693 #elif !defined getpagesize
1694 extern int getpagesize (void);
1695 #endif
1696
1697 static size_t pagesize;
1698
1699 void *
1700 valloc (size_t size)
1701 {
1702 if (pagesize == 0)
1703 pagesize = getpagesize ();
1704
1705 return memalign (pagesize, size);
1706 }
1707
1708 #ifdef GC_MCHECK
1709
1710 /* Standard debugging hooks for `malloc'.
1711 Copyright 1990, 1991, 1992, 1993, 1994 Free Software Foundation, Inc.
1712 Written May 1989 by Mike Haertel.
1713
1714 This library is free software; you can redistribute it and/or
1715 modify it under the terms of the GNU General Public License as
1716 published by the Free Software Foundation; either version 2 of the
1717 License, or (at your option) any later version.
1718
1719 This library is distributed in the hope that it will be useful,
1720 but WITHOUT ANY WARRANTY; without even the implied warranty of
1721 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1722 General Public License for more details.
1723
1724 You should have received a copy of the GNU General Public
1725 License along with this library; see the file COPYING. If
1726 not, write to the Free Software Foundation, Inc., 51 Franklin Street,
1727 Fifth Floor, Boston, MA 02110-1301, USA.
1728
1729 The author may be reached (Email) at the address mike@ai.mit.edu,
1730 or (US mail) as Mike Haertel c/o Free Software Foundation. */
1731
1732 #include <stdio.h>
1733
1734 /* Old hook values. */
1735 static void (*old_free_hook) (void *ptr);
1736 static void *(*old_malloc_hook) (size_t size);
1737 static void *(*old_realloc_hook) (void *ptr, size_t size);
1738
1739 /* Function to call when something awful happens. */
1740 static void (*abortfunc) (enum mcheck_status);
1741
1742 /* Arbitrary magical numbers. */
1743 #define MAGICWORD (SIZE_MAX / 11 ^ SIZE_MAX / 13 << 3)
1744 #define MAGICFREE (SIZE_MAX / 17 ^ SIZE_MAX / 19 << 4)
1745 #define MAGICBYTE ((char) 0xd7)
1746 #define MALLOCFLOOD ((char) 0x93)
1747 #define FREEFLOOD ((char) 0x95)
1748
1749 struct hdr
1750 {
1751 size_t size; /* Exact size requested by user. */
1752 size_t magic; /* Magic number to check header integrity. */
1753 };
1754
1755 static enum mcheck_status
1756 checkhdr (const struct hdr *hdr)
1757 {
1758 enum mcheck_status status;
1759 switch (hdr->magic)
1760 {
1761 default:
1762 status = MCHECK_HEAD;
1763 break;
1764 case MAGICFREE:
1765 status = MCHECK_FREE;
1766 break;
1767 case MAGICWORD:
1768 if (((char *) &hdr[1])[hdr->size] != MAGICBYTE)
1769 status = MCHECK_TAIL;
1770 else
1771 status = MCHECK_OK;
1772 break;
1773 }
1774 if (status != MCHECK_OK)
1775 (*abortfunc) (status);
1776 return status;
1777 }
1778
1779 static void
1780 freehook (void *ptr)
1781 {
1782 struct hdr *hdr;
1783
1784 if (ptr)
1785 {
1786 hdr = ((struct hdr *) ptr) - 1;
1787 checkhdr (hdr);
1788 hdr->magic = MAGICFREE;
1789 memset (ptr, FREEFLOOD, hdr->size);
1790 }
1791 else
1792 hdr = NULL;
1793
1794 __free_hook = old_free_hook;
1795 free (hdr);
1796 __free_hook = freehook;
1797 }
1798
1799 static void *
1800 mallochook (size_t size)
1801 {
1802 struct hdr *hdr;
1803
1804 __malloc_hook = old_malloc_hook;
1805 hdr = malloc (sizeof *hdr + size + 1);
1806 __malloc_hook = mallochook;
1807 if (hdr == NULL)
1808 return NULL;
1809
1810 hdr->size = size;
1811 hdr->magic = MAGICWORD;
1812 ((char *) &hdr[1])[size] = MAGICBYTE;
1813 memset (hdr + 1, MALLOCFLOOD, size);
1814 return hdr + 1;
1815 }
1816
1817 static void *
1818 reallochook (void *ptr, size_t size)
1819 {
1820 struct hdr *hdr = NULL;
1821 size_t osize = 0;
1822
1823 if (ptr)
1824 {
1825 hdr = ((struct hdr *) ptr) - 1;
1826 osize = hdr->size;
1827
1828 checkhdr (hdr);
1829 if (size < osize)
1830 memset ((char *) ptr + size, FREEFLOOD, osize - size);
1831 }
1832
1833 __free_hook = old_free_hook;
1834 __malloc_hook = old_malloc_hook;
1835 __realloc_hook = old_realloc_hook;
1836 hdr = realloc (hdr, sizeof *hdr + size + 1);
1837 __free_hook = freehook;
1838 __malloc_hook = mallochook;
1839 __realloc_hook = reallochook;
1840 if (hdr == NULL)
1841 return NULL;
1842
1843 hdr->size = size;
1844 hdr->magic = MAGICWORD;
1845 ((char *) &hdr[1])[size] = MAGICBYTE;
1846 if (size > osize)
1847 memset ((char *) (hdr + 1) + osize, MALLOCFLOOD, size - osize);
1848 return hdr + 1;
1849 }
1850
1851 static void
1852 mabort (enum mcheck_status status)
1853 {
1854 const char *msg;
1855 switch (status)
1856 {
1857 case MCHECK_OK:
1858 msg = "memory is consistent, library is buggy";
1859 break;
1860 case MCHECK_HEAD:
1861 msg = "memory clobbered before allocated block";
1862 break;
1863 case MCHECK_TAIL:
1864 msg = "memory clobbered past end of allocated block";
1865 break;
1866 case MCHECK_FREE:
1867 msg = "block freed twice";
1868 break;
1869 default:
1870 msg = "bogus mcheck_status, library is buggy";
1871 break;
1872 }
1873 #ifdef __GNU_LIBRARY__
1874 __libc_fatal (msg);
1875 #else
1876 fprintf (stderr, "mcheck: %s\n", msg);
1877 fflush (stderr);
1878 abort ();
1879 #endif
1880 }
1881
1882 static int mcheck_used = 0;
1883
1884 int
1885 mcheck (void (*func) (enum mcheck_status))
1886 {
1887 abortfunc = (func != NULL) ? func : &mabort;
1888
1889 /* These hooks may not be safely inserted if malloc is already in use. */
1890 if (!__malloc_initialized && !mcheck_used)
1891 {
1892 old_free_hook = __free_hook;
1893 __free_hook = freehook;
1894 old_malloc_hook = __malloc_hook;
1895 __malloc_hook = mallochook;
1896 old_realloc_hook = __realloc_hook;
1897 __realloc_hook = reallochook;
1898 mcheck_used = 1;
1899 }
1900
1901 return mcheck_used ? 0 : -1;
1902 }
1903
1904 enum mcheck_status
1905 mprobe (void *ptr)
1906 {
1907 return mcheck_used ? checkhdr (ptr) : MCHECK_DISABLED;
1908 }
1909
1910 #endif /* GC_MCHECK */