*** empty log message ***
[emacs.git] / src / gmalloc.c
blob751e90baf133aa65a670c1df2871ad3805882b8c
1 /* This file is no longer automatically generated from libc. */
3 #define _MALLOC_INTERNAL
5 /* The malloc headers and source files from the C library follow here. */
7 /* Declarations for `malloc' and friends.
8 Copyright 1990, 91, 92, 93, 95, 96, 99 Free Software Foundation, Inc.
9 Written May 1989 by Mike Haertel.
11 This library is free software; you can redistribute it and/or
12 modify it under the terms of the GNU Library General Public License as
13 published by the Free Software Foundation; either version 2 of the
14 License, or (at your option) any later version.
16 This library is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 Library General Public License for more details.
21 You should have received a copy of the GNU Library General Public
22 License along with this library; see the file COPYING.LIB. If
23 not, write to the Free Software Foundation, Inc., 675 Mass Ave,
24 Cambridge, MA 02139, USA.
26 The author may be reached (Email) at the address mike@ai.mit.edu,
27 or (US mail) as Mike Haertel c/o Free Software Foundation. */
29 #ifndef _MALLOC_H
31 #define _MALLOC_H 1
33 #ifdef _MALLOC_INTERNAL
35 #ifdef HAVE_CONFIG_H
36 #include <config.h>
37 #endif
39 #if defined __cplusplus || (defined (__STDC__) && __STDC__) || \
40 defined STDC_HEADERS || defined PROTOTYPES
41 #undef PP
42 #define PP(args) args
43 #undef __ptr_t
44 #define __ptr_t void *
45 #else /* Not C++ or ANSI C. */
46 #undef PP
47 #define PP(args) ()
48 #undef __ptr_t
49 #define __ptr_t char *
50 #endif /* C++ or ANSI C. */
52 #if defined(_LIBC) || defined(STDC_HEADERS) || defined(USG)
53 #include <string.h>
54 #else
55 #ifndef memset
56 #define memset(s, zero, n) bzero ((s), (n))
57 #endif
58 #ifndef memcpy
59 #define memcpy(d, s, n) bcopy ((s), (d), (n))
60 #endif
61 #endif
63 #ifdef HAVE_LIMITS_H
64 #include <limits.h>
65 #endif
66 #ifndef CHAR_BIT
67 #define CHAR_BIT 8
68 #endif
70 #ifdef HAVE_UNISTD_H
71 #include <unistd.h>
72 #endif
74 #endif /* _MALLOC_INTERNAL. */
77 #ifdef __cplusplus
78 extern "C"
80 #endif
82 #ifdef STDC_HEADERS
83 #include <stddef.h>
84 #define __malloc_size_t size_t
85 #define __malloc_ptrdiff_t ptrdiff_t
86 #else
87 #define __malloc_size_t unsigned int
88 #define __malloc_ptrdiff_t int
89 #endif
91 #ifndef NULL
92 #define NULL 0
93 #endif
95 #ifndef FREE_RETURN_TYPE
96 #define FREE_RETURN_TYPE void
97 #endif
100 /* Allocate SIZE bytes of memory. */
101 extern __ptr_t malloc PP ((__malloc_size_t __size));
102 /* Re-allocate the previously allocated block
103 in __ptr_t, making the new block SIZE bytes long. */
104 extern __ptr_t realloc PP ((__ptr_t __ptr, __malloc_size_t __size));
105 /* Allocate NMEMB elements of SIZE bytes each, all initialized to 0. */
106 extern __ptr_t calloc PP ((__malloc_size_t __nmemb, __malloc_size_t __size));
107 /* Free a block allocated by `malloc', `realloc' or `calloc'. */
108 extern FREE_RETURN_TYPE free PP ((__ptr_t __ptr));
110 /* Allocate SIZE bytes allocated to ALIGNMENT bytes. */
111 #if ! (defined (_MALLOC_INTERNAL) && __DJGPP__ - 0 == 1) /* Avoid conflict. */
112 extern __ptr_t memalign PP ((__malloc_size_t __alignment,
113 __malloc_size_t __size));
114 #endif
116 /* Allocate SIZE bytes on a page boundary. */
117 #if ! (defined (_MALLOC_INTERNAL) && defined (GMALLOC_INHIBIT_VALLOC))
118 extern __ptr_t valloc PP ((__malloc_size_t __size));
119 #endif
122 #ifdef _MALLOC_INTERNAL
124 /* The allocator divides the heap into blocks of fixed size; large
125 requests receive one or more whole blocks, and small requests
126 receive a fragment of a block. Fragment sizes are powers of two,
127 and all fragments of a block are the same size. When all the
128 fragments in a block have been freed, the block itself is freed. */
129 #define INT_BIT (CHAR_BIT * sizeof(int))
130 #define BLOCKLOG (INT_BIT > 16 ? 12 : 9)
131 #define BLOCKSIZE (1 << BLOCKLOG)
132 #define BLOCKIFY(SIZE) (((SIZE) + BLOCKSIZE - 1) / BLOCKSIZE)
134 /* Determine the amount of memory spanned by the initial heap table
135 (not an absolute limit). */
136 #define HEAP (INT_BIT > 16 ? 4194304 : 65536)
138 /* Number of contiguous free blocks allowed to build up at the end of
139 memory before they will be returned to the system. */
140 #define FINAL_FREE_BLOCKS 8
142 /* Data structure giving per-block information. */
143 typedef union
145 /* Heap information for a busy block. */
146 struct
148 /* Zero for a large (multiblock) object, or positive giving the
149 logarithm to the base two of the fragment size. */
150 int type;
151 union
153 struct
155 __malloc_size_t nfree; /* Free frags in a fragmented block. */
156 __malloc_size_t first; /* First free fragment of the block. */
157 } frag;
158 /* For a large object, in its first block, this has the number
159 of blocks in the object. In the other blocks, this has a
160 negative number which says how far back the first block is. */
161 __malloc_ptrdiff_t size;
162 } info;
163 } busy;
164 /* Heap information for a free block
165 (that may be the first of a free cluster). */
166 struct
168 __malloc_size_t size; /* Size (in blocks) of a free cluster. */
169 __malloc_size_t next; /* Index of next free cluster. */
170 __malloc_size_t prev; /* Index of previous free cluster. */
171 } free;
172 } malloc_info;
174 /* Pointer to first block of the heap. */
175 extern char *_heapbase;
177 /* Table indexed by block number giving per-block information. */
178 extern malloc_info *_heapinfo;
180 /* Address to block number and vice versa. */
181 #define BLOCK(A) (((char *) (A) - _heapbase) / BLOCKSIZE + 1)
182 #define ADDRESS(B) ((__ptr_t) (((B) - 1) * BLOCKSIZE + _heapbase))
184 /* Current search index for the heap table. */
185 extern __malloc_size_t _heapindex;
187 /* Limit of valid info table indices. */
188 extern __malloc_size_t _heaplimit;
190 /* Doubly linked lists of free fragments. */
191 struct list
193 struct list *next;
194 struct list *prev;
197 /* Free list headers for each fragment size. */
198 extern struct list _fraghead[];
200 /* List of blocks allocated with `memalign' (or `valloc'). */
201 struct alignlist
203 struct alignlist *next;
204 __ptr_t aligned; /* The address that memaligned returned. */
205 __ptr_t exact; /* The address that malloc returned. */
207 extern struct alignlist *_aligned_blocks;
209 /* Instrumentation. */
210 extern __malloc_size_t _chunks_used;
211 extern __malloc_size_t _bytes_used;
212 extern __malloc_size_t _chunks_free;
213 extern __malloc_size_t _bytes_free;
215 /* Internal versions of `malloc', `realloc', and `free'
216 used when these functions need to call each other.
217 They are the same but don't call the hooks. */
218 extern __ptr_t _malloc_internal PP ((__malloc_size_t __size));
219 extern __ptr_t _realloc_internal PP ((__ptr_t __ptr, __malloc_size_t __size));
220 extern void _free_internal PP ((__ptr_t __ptr));
222 #endif /* _MALLOC_INTERNAL. */
224 /* Given an address in the middle of a malloc'd object,
225 return the address of the beginning of the object. */
226 extern __ptr_t malloc_find_object_address PP ((__ptr_t __ptr));
228 /* Underlying allocation function; successive calls should
229 return contiguous pieces of memory. */
230 extern __ptr_t (*__morecore) PP ((__malloc_ptrdiff_t __size));
232 /* Default value of `__morecore'. */
233 extern __ptr_t __default_morecore PP ((__malloc_ptrdiff_t __size));
235 /* If not NULL, this function is called after each time
236 `__morecore' is called to increase the data size. */
237 extern void (*__after_morecore_hook) PP ((void));
239 /* Number of extra blocks to get each time we ask for more core.
240 This reduces the frequency of calling `(*__morecore)'. */
241 extern __malloc_size_t __malloc_extra_blocks;
243 /* Nonzero if `malloc' has been called and done its initialization. */
244 extern int __malloc_initialized;
245 /* Function called to initialize malloc data structures. */
246 extern int __malloc_initialize PP ((void));
248 /* Hooks for debugging versions. */
249 extern void (*__malloc_initialize_hook) PP ((void));
250 extern void (*__free_hook) PP ((__ptr_t __ptr));
251 extern __ptr_t (*__malloc_hook) PP ((__malloc_size_t __size));
252 extern __ptr_t (*__realloc_hook) PP ((__ptr_t __ptr, __malloc_size_t __size));
253 extern __ptr_t (*__memalign_hook) PP ((__malloc_size_t __size,
254 __malloc_size_t __alignment));
256 /* Return values for `mprobe': these are the kinds of inconsistencies that
257 `mcheck' enables detection of. */
258 enum mcheck_status
260 MCHECK_DISABLED = -1, /* Consistency checking is not turned on. */
261 MCHECK_OK, /* Block is fine. */
262 MCHECK_FREE, /* Block freed twice. */
263 MCHECK_HEAD, /* Memory before the block was clobbered. */
264 MCHECK_TAIL /* Memory after the block was clobbered. */
267 /* Activate a standard collection of debugging hooks. This must be called
268 before `malloc' is ever called. ABORTFUNC is called with an error code
269 (see enum above) when an inconsistency is detected. If ABORTFUNC is
270 null, the standard function prints on stderr and then calls `abort'. */
271 extern int mcheck PP ((void (*__abortfunc) PP ((enum mcheck_status))));
273 /* Check for aberrations in a particular malloc'd block. You must have
274 called `mcheck' already. These are the same checks that `mcheck' does
275 when you free or reallocate a block. */
276 extern enum mcheck_status mprobe PP ((__ptr_t __ptr));
278 /* Activate a standard collection of tracing hooks. */
279 extern void mtrace PP ((void));
280 extern void muntrace PP ((void));
282 /* Statistics available to the user. */
283 struct mstats
285 __malloc_size_t bytes_total; /* Total size of the heap. */
286 __malloc_size_t chunks_used; /* Chunks allocated by the user. */
287 __malloc_size_t bytes_used; /* Byte total of user-allocated chunks. */
288 __malloc_size_t chunks_free; /* Chunks in the free list. */
289 __malloc_size_t bytes_free; /* Byte total of chunks in the free list. */
292 /* Pick up the current statistics. */
293 extern struct mstats mstats PP ((void));
295 /* Call WARNFUN with a warning message when memory usage is high. */
296 extern void memory_warnings PP ((__ptr_t __start,
297 void (*__warnfun) PP ((const char *))));
300 /* Relocating allocator. */
302 /* Allocate SIZE bytes, and store the address in *HANDLEPTR. */
303 extern __ptr_t r_alloc PP ((__ptr_t *__handleptr, __malloc_size_t __size));
305 /* Free the storage allocated in HANDLEPTR. */
306 extern void r_alloc_free PP ((__ptr_t *__handleptr));
308 /* Adjust the block at HANDLEPTR to be SIZE bytes long. */
309 extern __ptr_t r_re_alloc PP ((__ptr_t *__handleptr, __malloc_size_t __size));
312 #ifdef __cplusplus
314 #endif
316 #endif /* malloc.h */
317 /* Memory allocator `malloc'.
318 Copyright 1990, 1991, 1992, 1993, 1994, 1995 Free Software Foundation, Inc.
319 Written May 1989 by Mike Haertel.
321 This library is free software; you can redistribute it and/or
322 modify it under the terms of the GNU Library General Public License as
323 published by the Free Software Foundation; either version 2 of the
324 License, or (at your option) any later version.
326 This library is distributed in the hope that it will be useful,
327 but WITHOUT ANY WARRANTY; without even the implied warranty of
328 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
329 Library General Public License for more details.
331 You should have received a copy of the GNU Library General Public
332 License along with this library; see the file COPYING.LIB. If
333 not, write to the Free Software Foundation, Inc., 675 Mass Ave,
334 Cambridge, MA 02139, USA.
336 The author may be reached (Email) at the address mike@ai.mit.edu,
337 or (US mail) as Mike Haertel c/o Free Software Foundation. */
339 #ifndef _MALLOC_INTERNAL
340 #define _MALLOC_INTERNAL
341 #include <malloc.h>
342 #endif
343 #include <errno.h>
345 /* How to really get more memory. */
346 __ptr_t (*__morecore) PP ((ptrdiff_t __size)) = __default_morecore;
348 /* Debugging hook for `malloc'. */
349 __ptr_t (*__malloc_hook) PP ((__malloc_size_t __size));
351 /* Pointer to the base of the first block. */
352 char *_heapbase;
354 /* Block information table. Allocated with align/__free (not malloc/free). */
355 malloc_info *_heapinfo;
357 /* Number of info entries. */
358 static __malloc_size_t heapsize;
360 /* Search index in the info table. */
361 __malloc_size_t _heapindex;
363 /* Limit of valid info table indices. */
364 __malloc_size_t _heaplimit;
366 /* Free lists for each fragment size. */
367 struct list _fraghead[BLOCKLOG];
369 /* Instrumentation. */
370 __malloc_size_t _chunks_used;
371 __malloc_size_t _bytes_used;
372 __malloc_size_t _chunks_free;
373 __malloc_size_t _bytes_free;
375 /* Are you experienced? */
376 int __malloc_initialized;
378 __malloc_size_t __malloc_extra_blocks;
380 void (*__malloc_initialize_hook) PP ((void));
381 void (*__after_morecore_hook) PP ((void));
383 #if defined GC_MALLOC_CHECK && defined GC_PROTECT_MALLOC_STATE
385 /* Some code for hunting a bug writing into _heapinfo.
387 Call this macro with argument PROT non-zero to protect internal
388 malloc state against writing to it, call it with a zero argument to
389 make it readable and writable.
391 Note that this only works if BLOCKSIZE == page size, which is
392 the case on the i386. */
394 #include <sys/types.h>
395 #include <sys/mman.h>
397 static int state_protected_p;
398 static __malloc_size_t last_state_size;
399 static malloc_info *last_heapinfo;
401 void
402 protect_malloc_state (protect_p)
403 int protect_p;
405 /* If _heapinfo has been relocated, make sure its old location
406 isn't left read-only; it will be reused by malloc. */
407 if (_heapinfo != last_heapinfo
408 && last_heapinfo
409 && state_protected_p)
410 mprotect (last_heapinfo, last_state_size, PROT_READ | PROT_WRITE);
412 last_state_size = _heaplimit * sizeof *_heapinfo;
413 last_heapinfo = _heapinfo;
415 if (protect_p != state_protected_p)
417 state_protected_p = protect_p;
418 if (mprotect (_heapinfo, last_state_size,
419 protect_p ? PROT_READ : PROT_READ | PROT_WRITE) != 0)
420 abort ();
424 #define PROTECT_MALLOC_STATE(PROT) protect_malloc_state(PROT)
426 #else
427 #define PROTECT_MALLOC_STATE(PROT) /* empty */
428 #endif
431 /* Aligned allocation. */
432 static __ptr_t align PP ((__malloc_size_t));
433 static __ptr_t
434 align (size)
435 __malloc_size_t size;
437 __ptr_t result;
438 unsigned long int adj;
440 result = (*__morecore) (size);
441 adj = (unsigned long int) ((unsigned long int) ((char *) result -
442 (char *) NULL)) % BLOCKSIZE;
443 if (adj != 0)
445 __ptr_t new;
446 adj = BLOCKSIZE - adj;
447 new = (*__morecore) (adj);
448 result = (char *) result + adj;
451 if (__after_morecore_hook)
452 (*__after_morecore_hook) ();
454 return result;
457 /* Get SIZE bytes, if we can get them starting at END.
458 Return the address of the space we got.
459 If we cannot get space at END, fail and return 0. */
460 static __ptr_t get_contiguous_space PP ((__malloc_ptrdiff_t, __ptr_t));
461 static __ptr_t
462 get_contiguous_space (size, position)
463 __malloc_ptrdiff_t size;
464 __ptr_t position;
466 __ptr_t before;
467 __ptr_t after;
469 before = (*__morecore) (0);
470 /* If we can tell in advance that the break is at the wrong place,
471 fail now. */
472 if (before != position)
473 return 0;
475 /* Allocate SIZE bytes and get the address of them. */
476 after = (*__morecore) (size);
477 if (!after)
478 return 0;
480 /* It was not contiguous--reject it. */
481 if (after != position)
483 (*__morecore) (- size);
484 return 0;
487 return after;
491 /* This is called when `_heapinfo' and `heapsize' have just
492 been set to describe a new info table. Set up the table
493 to describe itself and account for it in the statistics. */
494 static void register_heapinfo PP ((void));
495 #ifdef __GNUC__
496 __inline__
497 #endif
498 static void
499 register_heapinfo ()
501 __malloc_size_t block, blocks;
503 block = BLOCK (_heapinfo);
504 blocks = BLOCKIFY (heapsize * sizeof (malloc_info));
506 /* Account for the _heapinfo block itself in the statistics. */
507 _bytes_used += blocks * BLOCKSIZE;
508 ++_chunks_used;
510 /* Describe the heapinfo block itself in the heapinfo. */
511 _heapinfo[block].busy.type = 0;
512 _heapinfo[block].busy.info.size = blocks;
513 /* Leave back-pointers for malloc_find_address. */
514 while (--blocks > 0)
515 _heapinfo[block + blocks].busy.info.size = -blocks;
518 /* Set everything up and remember that we have. */
520 __malloc_initialize ()
522 if (__malloc_initialized)
523 return 0;
525 #ifdef GC_MCHECK
526 mcheck (NULL);
527 #endif
529 if (__malloc_initialize_hook)
530 (*__malloc_initialize_hook) ();
532 heapsize = HEAP / BLOCKSIZE;
533 _heapinfo = (malloc_info *) align (heapsize * sizeof (malloc_info));
534 if (_heapinfo == NULL)
535 return 0;
536 memset (_heapinfo, 0, heapsize * sizeof (malloc_info));
537 _heapinfo[0].free.size = 0;
538 _heapinfo[0].free.next = _heapinfo[0].free.prev = 0;
539 _heapindex = 0;
540 _heapbase = (char *) _heapinfo;
541 _heaplimit = BLOCK (_heapbase + heapsize * sizeof (malloc_info));
543 register_heapinfo ();
545 __malloc_initialized = 1;
546 PROTECT_MALLOC_STATE (1);
547 return 1;
550 static int morecore_recursing;
552 /* Get neatly aligned memory, initializing or
553 growing the heap info table as necessary. */
554 static __ptr_t morecore PP ((__malloc_size_t));
555 static __ptr_t
556 morecore (size)
557 __malloc_size_t size;
559 __ptr_t result;
560 malloc_info *newinfo, *oldinfo;
561 __malloc_size_t newsize;
563 if (morecore_recursing)
564 /* Avoid recursion. The caller will know how to handle a null return. */
565 return NULL;
567 result = align (size);
568 if (result == NULL)
569 return NULL;
571 PROTECT_MALLOC_STATE (0);
573 /* Check if we need to grow the info table. */
574 if ((__malloc_size_t) BLOCK ((char *) result + size) > heapsize)
576 /* Calculate the new _heapinfo table size. We do not account for the
577 added blocks in the table itself, as we hope to place them in
578 existing free space, which is already covered by part of the
579 existing table. */
580 newsize = heapsize;
582 newsize *= 2;
583 while ((__malloc_size_t) BLOCK ((char *) result + size) > newsize);
585 /* We must not reuse existing core for the new info table when called
586 from realloc in the case of growing a large block, because the
587 block being grown is momentarily marked as free. In this case
588 _heaplimit is zero so we know not to reuse space for internal
589 allocation. */
590 if (_heaplimit != 0)
592 /* First try to allocate the new info table in core we already
593 have, in the usual way using realloc. If realloc cannot
594 extend it in place or relocate it to existing sufficient core,
595 we will get called again, and the code above will notice the
596 `morecore_recursing' flag and return null. */
597 int save = errno; /* Don't want to clobber errno with ENOMEM. */
598 morecore_recursing = 1;
599 newinfo = (malloc_info *) _realloc_internal
600 (_heapinfo, newsize * sizeof (malloc_info));
601 morecore_recursing = 0;
602 if (newinfo == NULL)
603 errno = save;
604 else
606 /* We found some space in core, and realloc has put the old
607 table's blocks on the free list. Now zero the new part
608 of the table and install the new table location. */
609 memset (&newinfo[heapsize], 0,
610 (newsize - heapsize) * sizeof (malloc_info));
611 _heapinfo = newinfo;
612 heapsize = newsize;
613 goto got_heap;
617 /* Allocate new space for the malloc info table. */
618 while (1)
620 newinfo = (malloc_info *) align (newsize * sizeof (malloc_info));
622 /* Did it fail? */
623 if (newinfo == NULL)
625 (*__morecore) (-size);
626 return NULL;
629 /* Is it big enough to record status for its own space?
630 If so, we win. */
631 if ((__malloc_size_t) BLOCK ((char *) newinfo
632 + newsize * sizeof (malloc_info))
633 < newsize)
634 break;
636 /* Must try again. First give back most of what we just got. */
637 (*__morecore) (- newsize * sizeof (malloc_info));
638 newsize *= 2;
641 /* Copy the old table to the beginning of the new,
642 and zero the rest of the new table. */
643 memcpy (newinfo, _heapinfo, heapsize * sizeof (malloc_info));
644 memset (&newinfo[heapsize], 0,
645 (newsize - heapsize) * sizeof (malloc_info));
646 oldinfo = _heapinfo;
647 _heapinfo = newinfo;
648 heapsize = newsize;
650 register_heapinfo ();
652 /* Reset _heaplimit so _free_internal never decides
653 it can relocate or resize the info table. */
654 _heaplimit = 0;
655 _free_internal (oldinfo);
656 PROTECT_MALLOC_STATE (0);
658 /* The new heap limit includes the new table just allocated. */
659 _heaplimit = BLOCK ((char *) newinfo + heapsize * sizeof (malloc_info));
660 return result;
663 got_heap:
664 _heaplimit = BLOCK ((char *) result + size);
665 return result;
668 /* Allocate memory from the heap. */
669 __ptr_t
670 _malloc_internal (size)
671 __malloc_size_t size;
673 __ptr_t result;
674 __malloc_size_t block, blocks, lastblocks, start;
675 register __malloc_size_t i;
676 struct list *next;
678 /* ANSI C allows `malloc (0)' to either return NULL, or to return a
679 valid address you can realloc and free (though not dereference).
681 It turns out that some extant code (sunrpc, at least Ultrix's version)
682 expects `malloc (0)' to return non-NULL and breaks otherwise.
683 Be compatible. */
685 #if 0
686 if (size == 0)
687 return NULL;
688 #endif
690 PROTECT_MALLOC_STATE (0);
692 if (size < sizeof (struct list))
693 size = sizeof (struct list);
695 #ifdef SUNOS_LOCALTIME_BUG
696 if (size < 16)
697 size = 16;
698 #endif
700 /* Determine the allocation policy based on the request size. */
701 if (size <= BLOCKSIZE / 2)
703 /* Small allocation to receive a fragment of a block.
704 Determine the logarithm to base two of the fragment size. */
705 register __malloc_size_t log = 1;
706 --size;
707 while ((size /= 2) != 0)
708 ++log;
710 /* Look in the fragment lists for a
711 free fragment of the desired size. */
712 next = _fraghead[log].next;
713 if (next != NULL)
715 /* There are free fragments of this size.
716 Pop a fragment out of the fragment list and return it.
717 Update the block's nfree and first counters. */
718 result = (__ptr_t) next;
719 next->prev->next = next->next;
720 if (next->next != NULL)
721 next->next->prev = next->prev;
722 block = BLOCK (result);
723 if (--_heapinfo[block].busy.info.frag.nfree != 0)
724 _heapinfo[block].busy.info.frag.first = (unsigned long int)
725 ((unsigned long int) ((char *) next->next - (char *) NULL)
726 % BLOCKSIZE) >> log;
728 /* Update the statistics. */
729 ++_chunks_used;
730 _bytes_used += 1 << log;
731 --_chunks_free;
732 _bytes_free -= 1 << log;
734 else
736 /* No free fragments of the desired size, so get a new block
737 and break it into fragments, returning the first. */
738 #ifdef GC_MALLOC_CHECK
739 result = _malloc_internal (BLOCKSIZE);
740 PROTECT_MALLOC_STATE (0);
741 #else
742 result = malloc (BLOCKSIZE);
743 #endif
744 if (result == NULL)
746 PROTECT_MALLOC_STATE (1);
747 return NULL;
750 /* Link all fragments but the first into the free list. */
751 next = (struct list *) ((char *) result + (1 << log));
752 next->next = NULL;
753 next->prev = &_fraghead[log];
754 _fraghead[log].next = next;
756 for (i = 2; i < (__malloc_size_t) (BLOCKSIZE >> log); ++i)
758 next = (struct list *) ((char *) result + (i << log));
759 next->next = _fraghead[log].next;
760 next->prev = &_fraghead[log];
761 next->prev->next = next;
762 next->next->prev = next;
765 /* Initialize the nfree and first counters for this block. */
766 block = BLOCK (result);
767 _heapinfo[block].busy.type = log;
768 _heapinfo[block].busy.info.frag.nfree = i - 1;
769 _heapinfo[block].busy.info.frag.first = i - 1;
771 _chunks_free += (BLOCKSIZE >> log) - 1;
772 _bytes_free += BLOCKSIZE - (1 << log);
773 _bytes_used -= BLOCKSIZE - (1 << log);
776 else
778 /* Large allocation to receive one or more blocks.
779 Search the free list in a circle starting at the last place visited.
780 If we loop completely around without finding a large enough
781 space we will have to get more memory from the system. */
782 blocks = BLOCKIFY (size);
783 start = block = _heapindex;
784 while (_heapinfo[block].free.size < blocks)
786 block = _heapinfo[block].free.next;
787 if (block == start)
789 /* Need to get more from the system. Get a little extra. */
790 __malloc_size_t wantblocks = blocks + __malloc_extra_blocks;
791 block = _heapinfo[0].free.prev;
792 lastblocks = _heapinfo[block].free.size;
793 /* Check to see if the new core will be contiguous with the
794 final free block; if so we don't need to get as much. */
795 if (_heaplimit != 0 && block + lastblocks == _heaplimit &&
796 /* We can't do this if we will have to make the heap info
797 table bigger to accomodate the new space. */
798 block + wantblocks <= heapsize &&
799 get_contiguous_space ((wantblocks - lastblocks) * BLOCKSIZE,
800 ADDRESS (block + lastblocks)))
802 /* We got it contiguously. Which block we are extending
803 (the `final free block' referred to above) might have
804 changed, if it got combined with a freed info table. */
805 block = _heapinfo[0].free.prev;
806 _heapinfo[block].free.size += (wantblocks - lastblocks);
807 _bytes_free += (wantblocks - lastblocks) * BLOCKSIZE;
808 _heaplimit += wantblocks - lastblocks;
809 continue;
811 result = morecore (wantblocks * BLOCKSIZE);
812 if (result == NULL)
813 return NULL;
814 block = BLOCK (result);
815 /* Put the new block at the end of the free list. */
816 _heapinfo[block].free.size = wantblocks;
817 _heapinfo[block].free.prev = _heapinfo[0].free.prev;
818 _heapinfo[block].free.next = 0;
819 _heapinfo[0].free.prev = block;
820 _heapinfo[_heapinfo[block].free.prev].free.next = block;
821 ++_chunks_free;
822 /* Now loop to use some of that block for this allocation. */
826 /* At this point we have found a suitable free list entry.
827 Figure out how to remove what we need from the list. */
828 result = ADDRESS (block);
829 if (_heapinfo[block].free.size > blocks)
831 /* The block we found has a bit left over,
832 so relink the tail end back into the free list. */
833 _heapinfo[block + blocks].free.size
834 = _heapinfo[block].free.size - blocks;
835 _heapinfo[block + blocks].free.next
836 = _heapinfo[block].free.next;
837 _heapinfo[block + blocks].free.prev
838 = _heapinfo[block].free.prev;
839 _heapinfo[_heapinfo[block].free.prev].free.next
840 = _heapinfo[_heapinfo[block].free.next].free.prev
841 = _heapindex = block + blocks;
843 else
845 /* The block exactly matches our requirements,
846 so just remove it from the list. */
847 _heapinfo[_heapinfo[block].free.next].free.prev
848 = _heapinfo[block].free.prev;
849 _heapinfo[_heapinfo[block].free.prev].free.next
850 = _heapindex = _heapinfo[block].free.next;
851 --_chunks_free;
854 _heapinfo[block].busy.type = 0;
855 _heapinfo[block].busy.info.size = blocks;
856 ++_chunks_used;
857 _bytes_used += blocks * BLOCKSIZE;
858 _bytes_free -= blocks * BLOCKSIZE;
860 /* Mark all the blocks of the object just allocated except for the
861 first with a negative number so you can find the first block by
862 adding that adjustment. */
863 while (--blocks > 0)
864 _heapinfo[block + blocks].busy.info.size = -blocks;
867 PROTECT_MALLOC_STATE (1);
868 return result;
871 __ptr_t
872 malloc (size)
873 __malloc_size_t size;
875 if (!__malloc_initialized && !__malloc_initialize ())
876 return NULL;
878 return (__malloc_hook != NULL ? *__malloc_hook : _malloc_internal) (size);
881 #ifndef _LIBC
883 /* On some ANSI C systems, some libc functions call _malloc, _free
884 and _realloc. Make them use the GNU functions. */
886 __ptr_t
887 _malloc (size)
888 __malloc_size_t size;
890 return malloc (size);
893 void
894 _free (ptr)
895 __ptr_t ptr;
897 free (ptr);
900 __ptr_t
901 _realloc (ptr, size)
902 __ptr_t ptr;
903 __malloc_size_t size;
905 return realloc (ptr, size);
908 #endif
909 /* Free a block of memory allocated by `malloc'.
910 Copyright 1990, 1991, 1992, 1994, 1995 Free Software Foundation, Inc.
911 Written May 1989 by Mike Haertel.
913 This library is free software; you can redistribute it and/or
914 modify it under the terms of the GNU Library General Public License as
915 published by the Free Software Foundation; either version 2 of the
916 License, or (at your option) any later version.
918 This library is distributed in the hope that it will be useful,
919 but WITHOUT ANY WARRANTY; without even the implied warranty of
920 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
921 Library General Public License for more details.
923 You should have received a copy of the GNU Library General Public
924 License along with this library; see the file COPYING.LIB. If
925 not, write to the Free Software Foundation, Inc., 675 Mass Ave,
926 Cambridge, MA 02139, USA.
928 The author may be reached (Email) at the address mike@ai.mit.edu,
929 or (US mail) as Mike Haertel c/o Free Software Foundation. */
931 #ifndef _MALLOC_INTERNAL
932 #define _MALLOC_INTERNAL
933 #include <malloc.h>
934 #endif
937 /* Cope with systems lacking `memmove'. */
938 #ifndef memmove
939 #if (defined (MEMMOVE_MISSING) || \
940 !defined(_LIBC) && !defined(STDC_HEADERS) && !defined(USG))
941 #ifdef emacs
942 #undef __malloc_safe_bcopy
943 #define __malloc_safe_bcopy safe_bcopy
944 #endif
945 /* This function is defined in realloc.c. */
946 extern void __malloc_safe_bcopy PP ((__ptr_t, __ptr_t, __malloc_size_t));
947 #define memmove(to, from, size) __malloc_safe_bcopy ((from), (to), (size))
948 #endif
949 #endif
952 /* Debugging hook for free. */
953 void (*__free_hook) PP ((__ptr_t __ptr));
955 /* List of blocks allocated by memalign. */
956 struct alignlist *_aligned_blocks = NULL;
958 /* Return memory to the heap.
959 Like `free' but don't call a __free_hook if there is one. */
960 void
961 _free_internal (ptr)
962 __ptr_t ptr;
964 int type;
965 __malloc_size_t block, blocks;
966 register __malloc_size_t i;
967 struct list *prev, *next;
968 __ptr_t curbrk;
969 const __malloc_size_t lesscore_threshold
970 /* Threshold of free space at which we will return some to the system. */
971 = FINAL_FREE_BLOCKS + 2 * __malloc_extra_blocks;
973 register struct alignlist *l;
975 if (ptr == NULL)
976 return;
978 PROTECT_MALLOC_STATE (0);
980 for (l = _aligned_blocks; l != NULL; l = l->next)
981 if (l->aligned == ptr)
983 l->aligned = NULL; /* Mark the slot in the list as free. */
984 ptr = l->exact;
985 break;
988 block = BLOCK (ptr);
990 type = _heapinfo[block].busy.type;
991 switch (type)
993 case 0:
994 /* Get as many statistics as early as we can. */
995 --_chunks_used;
996 _bytes_used -= _heapinfo[block].busy.info.size * BLOCKSIZE;
997 _bytes_free += _heapinfo[block].busy.info.size * BLOCKSIZE;
999 /* Find the free cluster previous to this one in the free list.
1000 Start searching at the last block referenced; this may benefit
1001 programs with locality of allocation. */
1002 i = _heapindex;
1003 if (i > block)
1004 while (i > block)
1005 i = _heapinfo[i].free.prev;
1006 else
1009 i = _heapinfo[i].free.next;
1010 while (i > 0 && i < block);
1011 i = _heapinfo[i].free.prev;
1014 /* Determine how to link this block into the free list. */
1015 if (block == i + _heapinfo[i].free.size)
1017 /* Coalesce this block with its predecessor. */
1018 _heapinfo[i].free.size += _heapinfo[block].busy.info.size;
1019 block = i;
1021 else
1023 /* Really link this block back into the free list. */
1024 _heapinfo[block].free.size = _heapinfo[block].busy.info.size;
1025 _heapinfo[block].free.next = _heapinfo[i].free.next;
1026 _heapinfo[block].free.prev = i;
1027 _heapinfo[i].free.next = block;
1028 _heapinfo[_heapinfo[block].free.next].free.prev = block;
1029 ++_chunks_free;
1032 /* Now that the block is linked in, see if we can coalesce it
1033 with its successor (by deleting its successor from the list
1034 and adding in its size). */
1035 if (block + _heapinfo[block].free.size == _heapinfo[block].free.next)
1037 _heapinfo[block].free.size
1038 += _heapinfo[_heapinfo[block].free.next].free.size;
1039 _heapinfo[block].free.next
1040 = _heapinfo[_heapinfo[block].free.next].free.next;
1041 _heapinfo[_heapinfo[block].free.next].free.prev = block;
1042 --_chunks_free;
1045 /* How many trailing free blocks are there now? */
1046 blocks = _heapinfo[block].free.size;
1048 /* Where is the current end of accessible core? */
1049 curbrk = (*__morecore) (0);
1051 if (_heaplimit != 0 && curbrk == ADDRESS (_heaplimit))
1053 /* The end of the malloc heap is at the end of accessible core.
1054 It's possible that moving _heapinfo will allow us to
1055 return some space to the system. */
1057 __malloc_size_t info_block = BLOCK (_heapinfo);
1058 __malloc_size_t info_blocks = _heapinfo[info_block].busy.info.size;
1059 __malloc_size_t prev_block = _heapinfo[block].free.prev;
1060 __malloc_size_t prev_blocks = _heapinfo[prev_block].free.size;
1061 __malloc_size_t next_block = _heapinfo[block].free.next;
1062 __malloc_size_t next_blocks = _heapinfo[next_block].free.size;
1064 if (/* Win if this block being freed is last in core, the info table
1065 is just before it, the previous free block is just before the
1066 info table, and the two free blocks together form a useful
1067 amount to return to the system. */
1068 (block + blocks == _heaplimit &&
1069 info_block + info_blocks == block &&
1070 prev_block != 0 && prev_block + prev_blocks == info_block &&
1071 blocks + prev_blocks >= lesscore_threshold) ||
1072 /* Nope, not the case. We can also win if this block being
1073 freed is just before the info table, and the table extends
1074 to the end of core or is followed only by a free block,
1075 and the total free space is worth returning to the system. */
1076 (block + blocks == info_block &&
1077 ((info_block + info_blocks == _heaplimit &&
1078 blocks >= lesscore_threshold) ||
1079 (info_block + info_blocks == next_block &&
1080 next_block + next_blocks == _heaplimit &&
1081 blocks + next_blocks >= lesscore_threshold)))
1084 malloc_info *newinfo;
1085 __malloc_size_t oldlimit = _heaplimit;
1087 /* Free the old info table, clearing _heaplimit to avoid
1088 recursion into this code. We don't want to return the
1089 table's blocks to the system before we have copied them to
1090 the new location. */
1091 _heaplimit = 0;
1092 _free_internal (_heapinfo);
1093 _heaplimit = oldlimit;
1095 /* Tell malloc to search from the beginning of the heap for
1096 free blocks, so it doesn't reuse the ones just freed. */
1097 _heapindex = 0;
1099 /* Allocate new space for the info table and move its data. */
1100 newinfo = (malloc_info *) _malloc_internal (info_blocks
1101 * BLOCKSIZE);
1102 PROTECT_MALLOC_STATE (0);
1103 memmove (newinfo, _heapinfo, info_blocks * BLOCKSIZE);
1104 _heapinfo = newinfo;
1106 /* We should now have coalesced the free block with the
1107 blocks freed from the old info table. Examine the entire
1108 trailing free block to decide below whether to return some
1109 to the system. */
1110 block = _heapinfo[0].free.prev;
1111 blocks = _heapinfo[block].free.size;
1114 /* Now see if we can return stuff to the system. */
1115 if (block + blocks == _heaplimit && blocks >= lesscore_threshold)
1117 register __malloc_size_t bytes = blocks * BLOCKSIZE;
1118 _heaplimit -= blocks;
1119 (*__morecore) (-bytes);
1120 _heapinfo[_heapinfo[block].free.prev].free.next
1121 = _heapinfo[block].free.next;
1122 _heapinfo[_heapinfo[block].free.next].free.prev
1123 = _heapinfo[block].free.prev;
1124 block = _heapinfo[block].free.prev;
1125 --_chunks_free;
1126 _bytes_free -= bytes;
1130 /* Set the next search to begin at this block. */
1131 _heapindex = block;
1132 break;
1134 default:
1135 /* Do some of the statistics. */
1136 --_chunks_used;
1137 _bytes_used -= 1 << type;
1138 ++_chunks_free;
1139 _bytes_free += 1 << type;
1141 /* Get the address of the first free fragment in this block. */
1142 prev = (struct list *) ((char *) ADDRESS (block) +
1143 (_heapinfo[block].busy.info.frag.first << type));
1145 if (_heapinfo[block].busy.info.frag.nfree == (BLOCKSIZE >> type) - 1)
1147 /* If all fragments of this block are free, remove them
1148 from the fragment list and free the whole block. */
1149 next = prev;
1150 for (i = 1; i < (__malloc_size_t) (BLOCKSIZE >> type); ++i)
1151 next = next->next;
1152 prev->prev->next = next;
1153 if (next != NULL)
1154 next->prev = prev->prev;
1155 _heapinfo[block].busy.type = 0;
1156 _heapinfo[block].busy.info.size = 1;
1158 /* Keep the statistics accurate. */
1159 ++_chunks_used;
1160 _bytes_used += BLOCKSIZE;
1161 _chunks_free -= BLOCKSIZE >> type;
1162 _bytes_free -= BLOCKSIZE;
1164 #ifdef GC_MALLOC_CHECK
1165 _free_internal (ADDRESS (block));
1166 #else
1167 free (ADDRESS (block));
1168 #endif
1170 else if (_heapinfo[block].busy.info.frag.nfree != 0)
1172 /* If some fragments of this block are free, link this
1173 fragment into the fragment list after the first free
1174 fragment of this block. */
1175 next = (struct list *) ptr;
1176 next->next = prev->next;
1177 next->prev = prev;
1178 prev->next = next;
1179 if (next->next != NULL)
1180 next->next->prev = next;
1181 ++_heapinfo[block].busy.info.frag.nfree;
1183 else
1185 /* No fragments of this block are free, so link this
1186 fragment into the fragment list and announce that
1187 it is the first free fragment of this block. */
1188 prev = (struct list *) ptr;
1189 _heapinfo[block].busy.info.frag.nfree = 1;
1190 _heapinfo[block].busy.info.frag.first = (unsigned long int)
1191 ((unsigned long int) ((char *) ptr - (char *) NULL)
1192 % BLOCKSIZE >> type);
1193 prev->next = _fraghead[type].next;
1194 prev->prev = &_fraghead[type];
1195 prev->prev->next = prev;
1196 if (prev->next != NULL)
1197 prev->next->prev = prev;
1199 break;
1202 PROTECT_MALLOC_STATE (1);
1205 /* Return memory to the heap. */
1207 FREE_RETURN_TYPE
1208 free (ptr)
1209 __ptr_t ptr;
1211 if (__free_hook != NULL)
1212 (*__free_hook) (ptr);
1213 else
1214 _free_internal (ptr);
1217 /* Define the `cfree' alias for `free'. */
1218 #ifdef weak_alias
1219 weak_alias (free, cfree)
1220 #else
1221 void
1222 cfree (ptr)
1223 __ptr_t ptr;
1225 free (ptr);
1227 #endif
1228 /* Change the size of a block allocated by `malloc'.
1229 Copyright 1990, 1991, 1992, 1993, 1994, 1995 Free Software Foundation, Inc.
1230 Written May 1989 by Mike Haertel.
1232 This library is free software; you can redistribute it and/or
1233 modify it under the terms of the GNU Library General Public License as
1234 published by the Free Software Foundation; either version 2 of the
1235 License, or (at your option) any later version.
1237 This library is distributed in the hope that it will be useful,
1238 but WITHOUT ANY WARRANTY; without even the implied warranty of
1239 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1240 Library General Public License for more details.
1242 You should have received a copy of the GNU Library General Public
1243 License along with this library; see the file COPYING.LIB. If
1244 not, write to the Free Software Foundation, Inc., 675 Mass Ave,
1245 Cambridge, MA 02139, USA.
1247 The author may be reached (Email) at the address mike@ai.mit.edu,
1248 or (US mail) as Mike Haertel c/o Free Software Foundation. */
1250 #ifndef _MALLOC_INTERNAL
1251 #define _MALLOC_INTERNAL
1252 #include <malloc.h>
1253 #endif
1257 /* Cope with systems lacking `memmove'. */
1258 #if (defined (MEMMOVE_MISSING) || \
1259 !defined(_LIBC) && !defined(STDC_HEADERS) && !defined(USG))
1261 #ifdef emacs
1262 #undef __malloc_safe_bcopy
1263 #define __malloc_safe_bcopy safe_bcopy
1264 #else
1266 /* Snarfed directly from Emacs src/dispnew.c:
1267 XXX Should use system bcopy if it handles overlap. */
1269 /* Like bcopy except never gets confused by overlap. */
1271 void
1272 __malloc_safe_bcopy (afrom, ato, size)
1273 __ptr_t afrom;
1274 __ptr_t ato;
1275 __malloc_size_t size;
1277 char *from = afrom, *to = ato;
1279 if (size <= 0 || from == to)
1280 return;
1282 /* If the source and destination don't overlap, then bcopy can
1283 handle it. If they do overlap, but the destination is lower in
1284 memory than the source, we'll assume bcopy can handle that. */
1285 if (to < from || from + size <= to)
1286 bcopy (from, to, size);
1288 /* Otherwise, we'll copy from the end. */
1289 else
1291 register char *endf = from + size;
1292 register char *endt = to + size;
1294 /* If TO - FROM is large, then we should break the copy into
1295 nonoverlapping chunks of TO - FROM bytes each. However, if
1296 TO - FROM is small, then the bcopy function call overhead
1297 makes this not worth it. The crossover point could be about
1298 anywhere. Since I don't think the obvious copy loop is too
1299 bad, I'm trying to err in its favor. */
1300 if (to - from < 64)
1303 *--endt = *--endf;
1304 while (endf != from);
1306 else
1308 for (;;)
1310 endt -= (to - from);
1311 endf -= (to - from);
1313 if (endt < to)
1314 break;
1316 bcopy (endf, endt, to - from);
1319 /* If SIZE wasn't a multiple of TO - FROM, there will be a
1320 little left over. The amount left over is
1321 (endt + (to - from)) - to, which is endt - from. */
1322 bcopy (from, to, endt - from);
1326 #endif /* emacs */
1328 #ifndef memmove
1329 extern void __malloc_safe_bcopy PP ((__ptr_t, __ptr_t, __malloc_size_t));
1330 #define memmove(to, from, size) __malloc_safe_bcopy ((from), (to), (size))
1331 #endif
1333 #endif
1336 #define min(A, B) ((A) < (B) ? (A) : (B))
1338 /* Debugging hook for realloc. */
1339 __ptr_t (*__realloc_hook) PP ((__ptr_t __ptr, __malloc_size_t __size));
1341 /* Resize the given region to the new size, returning a pointer
1342 to the (possibly moved) region. This is optimized for speed;
1343 some benchmarks seem to indicate that greater compactness is
1344 achieved by unconditionally allocating and copying to a
1345 new region. This module has incestuous knowledge of the
1346 internals of both free and malloc. */
1347 __ptr_t
1348 _realloc_internal (ptr, size)
1349 __ptr_t ptr;
1350 __malloc_size_t size;
1352 __ptr_t result;
1353 int type;
1354 __malloc_size_t block, blocks, oldlimit;
1356 if (size == 0)
1358 _free_internal (ptr);
1359 return _malloc_internal (0);
1361 else if (ptr == NULL)
1362 return _malloc_internal (size);
1364 block = BLOCK (ptr);
1366 PROTECT_MALLOC_STATE (0);
1368 type = _heapinfo[block].busy.type;
1369 switch (type)
1371 case 0:
1372 /* Maybe reallocate a large block to a small fragment. */
1373 if (size <= BLOCKSIZE / 2)
1375 result = _malloc_internal (size);
1376 if (result != NULL)
1378 memcpy (result, ptr, size);
1379 _free_internal (ptr);
1380 return result;
1384 /* The new size is a large allocation as well;
1385 see if we can hold it in place. */
1386 blocks = BLOCKIFY (size);
1387 if (blocks < _heapinfo[block].busy.info.size)
1389 /* The new size is smaller; return
1390 excess memory to the free list. */
1391 _heapinfo[block + blocks].busy.type = 0;
1392 _heapinfo[block + blocks].busy.info.size
1393 = _heapinfo[block].busy.info.size - blocks;
1394 _heapinfo[block].busy.info.size = blocks;
1395 /* We have just created a new chunk by splitting a chunk in two.
1396 Now we will free this chunk; increment the statistics counter
1397 so it doesn't become wrong when _free_internal decrements it. */
1398 ++_chunks_used;
1399 _free_internal (ADDRESS (block + blocks));
1400 result = ptr;
1402 else if (blocks == _heapinfo[block].busy.info.size)
1403 /* No size change necessary. */
1404 result = ptr;
1405 else
1407 /* Won't fit, so allocate a new region that will.
1408 Free the old region first in case there is sufficient
1409 adjacent free space to grow without moving. */
1410 blocks = _heapinfo[block].busy.info.size;
1411 /* Prevent free from actually returning memory to the system. */
1412 oldlimit = _heaplimit;
1413 _heaplimit = 0;
1414 _free_internal (ptr);
1415 result = _malloc_internal (size);
1416 PROTECT_MALLOC_STATE (0);
1417 if (_heaplimit == 0)
1418 _heaplimit = oldlimit;
1419 if (result == NULL)
1421 /* Now we're really in trouble. We have to unfree
1422 the thing we just freed. Unfortunately it might
1423 have been coalesced with its neighbors. */
1424 if (_heapindex == block)
1425 (void) _malloc_internal (blocks * BLOCKSIZE);
1426 else
1428 __ptr_t previous
1429 = _malloc_internal ((block - _heapindex) * BLOCKSIZE);
1430 (void) _malloc_internal (blocks * BLOCKSIZE);
1431 _free_internal (previous);
1433 return NULL;
1435 if (ptr != result)
1436 memmove (result, ptr, blocks * BLOCKSIZE);
1438 break;
1440 default:
1441 /* Old size is a fragment; type is logarithm
1442 to base two of the fragment size. */
1443 if (size > (__malloc_size_t) (1 << (type - 1)) &&
1444 size <= (__malloc_size_t) (1 << type))
1445 /* The new size is the same kind of fragment. */
1446 result = ptr;
1447 else
1449 /* The new size is different; allocate a new space,
1450 and copy the lesser of the new size and the old. */
1451 result = _malloc_internal (size);
1452 if (result == NULL)
1453 return NULL;
1454 memcpy (result, ptr, min (size, (__malloc_size_t) 1 << type));
1455 _free_internal (ptr);
1457 break;
1460 PROTECT_MALLOC_STATE (1);
1461 return result;
1464 __ptr_t
1465 realloc (ptr, size)
1466 __ptr_t ptr;
1467 __malloc_size_t size;
1469 if (!__malloc_initialized && !__malloc_initialize ())
1470 return NULL;
1472 return (__realloc_hook != NULL ? *__realloc_hook : _realloc_internal)
1473 (ptr, size);
1475 /* Copyright (C) 1991, 1992, 1994 Free Software Foundation, Inc.
1477 This library is free software; you can redistribute it and/or
1478 modify it under the terms of the GNU Library General Public License as
1479 published by the Free Software Foundation; either version 2 of the
1480 License, or (at your option) any later version.
1482 This library is distributed in the hope that it will be useful,
1483 but WITHOUT ANY WARRANTY; without even the implied warranty of
1484 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1485 Library General Public License for more details.
1487 You should have received a copy of the GNU Library General Public
1488 License along with this library; see the file COPYING.LIB. If
1489 not, write to the Free Software Foundation, Inc., 675 Mass Ave,
1490 Cambridge, MA 02139, USA.
1492 The author may be reached (Email) at the address mike@ai.mit.edu,
1493 or (US mail) as Mike Haertel c/o Free Software Foundation. */
1495 #ifndef _MALLOC_INTERNAL
1496 #define _MALLOC_INTERNAL
1497 #include <malloc.h>
1498 #endif
1500 /* Allocate an array of NMEMB elements each SIZE bytes long.
1501 The entire array is initialized to zeros. */
1502 __ptr_t
1503 calloc (nmemb, size)
1504 register __malloc_size_t nmemb;
1505 register __malloc_size_t size;
1507 register __ptr_t result = malloc (nmemb * size);
1509 if (result != NULL)
1510 (void) memset (result, 0, nmemb * size);
1512 return result;
1514 /* Copyright (C) 1991, 1992, 1993, 1994, 1995 Free Software Foundation, Inc.
1515 This file is part of the GNU C Library.
1517 The GNU C Library is free software; you can redistribute it and/or modify
1518 it under the terms of the GNU General Public License as published by
1519 the Free Software Foundation; either version 2, or (at your option)
1520 any later version.
1522 The GNU C Library is distributed in the hope that it will be useful,
1523 but WITHOUT ANY WARRANTY; without even the implied warranty of
1524 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1525 GNU General Public License for more details.
1527 You should have received a copy of the GNU General Public License
1528 along with the GNU C Library; see the file COPYING. If not, write to
1529 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
1531 #ifndef _MALLOC_INTERNAL
1532 #define _MALLOC_INTERNAL
1533 #include <malloc.h>
1534 #endif
1536 #ifndef __GNU_LIBRARY__
1537 #define __sbrk sbrk
1538 #endif
1540 #ifdef __GNU_LIBRARY__
1541 /* It is best not to declare this and cast its result on foreign operating
1542 systems with potentially hostile include files. */
1544 #include <stddef.h>
1545 extern __ptr_t __sbrk PP ((ptrdiff_t increment));
1546 #endif
1548 #ifndef NULL
1549 #define NULL 0
1550 #endif
1552 /* Allocate INCREMENT more bytes of data space,
1553 and return the start of data space, or NULL on errors.
1554 If INCREMENT is negative, shrink data space. */
1555 __ptr_t
1556 __default_morecore (increment)
1557 __malloc_ptrdiff_t increment;
1559 __ptr_t result = (__ptr_t) __sbrk (increment);
1560 if (result == (__ptr_t) -1)
1561 return NULL;
1562 return result;
1564 /* Copyright (C) 1991, 92, 93, 94, 95, 96 Free Software Foundation, Inc.
1566 This library is free software; you can redistribute it and/or
1567 modify it under the terms of the GNU Library General Public License as
1568 published by the Free Software Foundation; either version 2 of the
1569 License, or (at your option) any later version.
1571 This library is distributed in the hope that it will be useful,
1572 but WITHOUT ANY WARRANTY; without even the implied warranty of
1573 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1574 Library General Public License for more details.
1576 You should have received a copy of the GNU Library General Public
1577 License along with this library; see the file COPYING.LIB. If
1578 not, write to the Free Software Foundation, Inc., 675 Mass Ave,
1579 Cambridge, MA 02139, USA. */
1581 #ifndef _MALLOC_INTERNAL
1582 #define _MALLOC_INTERNAL
1583 #include <malloc.h>
1584 #endif
1586 #if __DJGPP__ - 0 == 1
1588 /* There is some problem with memalign in DJGPP v1 and we are supposed
1589 to omit it. Noone told me why, they just told me to do it. */
1591 #else
1593 __ptr_t (*__memalign_hook) PP ((size_t __size, size_t __alignment));
1595 __ptr_t
1596 memalign (alignment, size)
1597 __malloc_size_t alignment;
1598 __malloc_size_t size;
1600 __ptr_t result;
1601 unsigned long int adj, lastadj;
1603 if (__memalign_hook)
1604 return (*__memalign_hook) (alignment, size);
1606 /* Allocate a block with enough extra space to pad the block with up to
1607 (ALIGNMENT - 1) bytes if necessary. */
1608 result = malloc (size + alignment - 1);
1609 if (result == NULL)
1610 return NULL;
1612 /* Figure out how much we will need to pad this particular block
1613 to achieve the required alignment. */
1614 adj = (unsigned long int) ((char *) result - (char *) NULL) % alignment;
1618 /* Reallocate the block with only as much excess as it needs. */
1619 free (result);
1620 result = malloc (adj + size);
1621 if (result == NULL) /* Impossible unless interrupted. */
1622 return NULL;
1624 lastadj = adj;
1625 adj = (unsigned long int) ((char *) result - (char *) NULL) % alignment;
1626 /* It's conceivable we might have been so unlucky as to get a
1627 different block with weaker alignment. If so, this block is too
1628 short to contain SIZE after alignment correction. So we must
1629 try again and get another block, slightly larger. */
1630 } while (adj > lastadj);
1632 if (adj != 0)
1634 /* Record this block in the list of aligned blocks, so that `free'
1635 can identify the pointer it is passed, which will be in the middle
1636 of an allocated block. */
1638 struct alignlist *l;
1639 for (l = _aligned_blocks; l != NULL; l = l->next)
1640 if (l->aligned == NULL)
1641 /* This slot is free. Use it. */
1642 break;
1643 if (l == NULL)
1645 l = (struct alignlist *) malloc (sizeof (struct alignlist));
1646 if (l == NULL)
1648 free (result);
1649 return NULL;
1651 l->next = _aligned_blocks;
1652 _aligned_blocks = l;
1654 l->exact = result;
1655 result = l->aligned = (char *) result + alignment - adj;
1658 return result;
1661 #endif /* Not DJGPP v1 */
1662 /* Allocate memory on a page boundary.
1663 Copyright (C) 1991, 92, 93, 94, 96 Free Software Foundation, Inc.
1665 This library is free software; you can redistribute it and/or
1666 modify it under the terms of the GNU Library General Public License as
1667 published by the Free Software Foundation; either version 2 of the
1668 License, or (at your option) any later version.
1670 This library is distributed in the hope that it will be useful,
1671 but WITHOUT ANY WARRANTY; without even the implied warranty of
1672 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1673 Library General Public License for more details.
1675 You should have received a copy of the GNU Library General Public
1676 License along with this library; see the file COPYING.LIB. If
1677 not, write to the Free Software Foundation, Inc., 675 Mass Ave,
1678 Cambridge, MA 02139, USA.
1680 The author may be reached (Email) at the address mike@ai.mit.edu,
1681 or (US mail) as Mike Haertel c/o Free Software Foundation. */
1683 #if defined (_MALLOC_INTERNAL) && defined (GMALLOC_INHIBIT_VALLOC)
1685 /* Emacs defines GMALLOC_INHIBIT_VALLOC to avoid this definition
1686 on MSDOS, where it conflicts with a system header file. */
1688 #define ELIDE_VALLOC
1690 #endif
1692 #ifndef ELIDE_VALLOC
1694 #if defined (__GNU_LIBRARY__) || defined (_LIBC)
1695 #include <stddef.h>
1696 #include <sys/cdefs.h>
1697 #if defined (__GLIBC__) && __GLIBC__ >= 2
1698 /* __getpagesize is already declared in <unistd.h> with return type int */
1699 #else
1700 extern size_t __getpagesize PP ((void));
1701 #endif
1702 #else
1703 #include "getpagesize.h"
1704 #define __getpagesize() getpagesize()
1705 #endif
1707 #ifndef _MALLOC_INTERNAL
1708 #define _MALLOC_INTERNAL
1709 #include <malloc.h>
1710 #endif
1712 static __malloc_size_t pagesize;
1714 __ptr_t
1715 valloc (size)
1716 __malloc_size_t size;
1718 if (pagesize == 0)
1719 pagesize = __getpagesize ();
1721 return memalign (pagesize, size);
1724 #endif /* Not ELIDE_VALLOC. */
1726 #ifdef GC_MCHECK
1728 /* Standard debugging hooks for `malloc'.
1729 Copyright 1990, 1991, 1992, 1993, 1994 Free Software Foundation, Inc.
1730 Written May 1989 by Mike Haertel.
1732 This library is free software; you can redistribute it and/or
1733 modify it under the terms of the GNU Library General Public License as
1734 published by the Free Software Foundation; either version 2 of the
1735 License, or (at your option) any later version.
1737 This library is distributed in the hope that it will be useful,
1738 but WITHOUT ANY WARRANTY; without even the implied warranty of
1739 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1740 Library General Public License for more details.
1742 You should have received a copy of the GNU Library General Public
1743 License along with this library; see the file COPYING.LIB. If
1744 not, write to the Free Software Foundation, Inc., 675 Mass Ave,
1745 Cambridge, MA 02139, USA.
1747 The author may be reached (Email) at the address mike@ai.mit.edu,
1748 or (US mail) as Mike Haertel c/o Free Software Foundation. */
1750 #ifdef emacs
1751 #include <stdio.h>
1752 #else
1753 #ifndef _MALLOC_INTERNAL
1754 #define _MALLOC_INTERNAL
1755 #include <malloc.h>
1756 #include <stdio.h>
1757 #endif
1758 #endif
1760 /* Old hook values. */
1761 static void (*old_free_hook) __P ((__ptr_t ptr));
1762 static __ptr_t (*old_malloc_hook) __P ((__malloc_size_t size));
1763 static __ptr_t (*old_realloc_hook) __P ((__ptr_t ptr, __malloc_size_t size));
1765 /* Function to call when something awful happens. */
1766 static void (*abortfunc) __P ((enum mcheck_status));
1768 /* Arbitrary magical numbers. */
1769 #define MAGICWORD 0xfedabeeb
1770 #define MAGICFREE 0xd8675309
1771 #define MAGICBYTE ((char) 0xd7)
1772 #define MALLOCFLOOD ((char) 0x93)
1773 #define FREEFLOOD ((char) 0x95)
1775 struct hdr
1777 __malloc_size_t size; /* Exact size requested by user. */
1778 unsigned long int magic; /* Magic number to check header integrity. */
1781 #if defined(_LIBC) || defined(STDC_HEADERS) || defined(USG)
1782 #define flood memset
1783 #else
1784 static void flood __P ((__ptr_t, int, __malloc_size_t));
1785 static void
1786 flood (ptr, val, size)
1787 __ptr_t ptr;
1788 int val;
1789 __malloc_size_t size;
1791 char *cp = ptr;
1792 while (size--)
1793 *cp++ = val;
1795 #endif
1797 static enum mcheck_status checkhdr __P ((const struct hdr *));
1798 static enum mcheck_status
1799 checkhdr (hdr)
1800 const struct hdr *hdr;
1802 enum mcheck_status status;
1803 switch (hdr->magic)
1805 default:
1806 status = MCHECK_HEAD;
1807 break;
1808 case MAGICFREE:
1809 status = MCHECK_FREE;
1810 break;
1811 case MAGICWORD:
1812 if (((char *) &hdr[1])[hdr->size] != MAGICBYTE)
1813 status = MCHECK_TAIL;
1814 else
1815 status = MCHECK_OK;
1816 break;
1818 if (status != MCHECK_OK)
1819 (*abortfunc) (status);
1820 return status;
1823 static void freehook __P ((__ptr_t));
1824 static void
1825 freehook (ptr)
1826 __ptr_t ptr;
1828 struct hdr *hdr;
1830 if (ptr)
1832 hdr = ((struct hdr *) ptr) - 1;
1833 checkhdr (hdr);
1834 hdr->magic = MAGICFREE;
1835 flood (ptr, FREEFLOOD, hdr->size);
1837 else
1838 hdr = NULL;
1840 __free_hook = old_free_hook;
1841 free (hdr);
1842 __free_hook = freehook;
1845 static __ptr_t mallochook __P ((__malloc_size_t));
1846 static __ptr_t
1847 mallochook (size)
1848 __malloc_size_t size;
1850 struct hdr *hdr;
1852 __malloc_hook = old_malloc_hook;
1853 hdr = (struct hdr *) malloc (sizeof (struct hdr) + size + 1);
1854 __malloc_hook = mallochook;
1855 if (hdr == NULL)
1856 return NULL;
1858 hdr->size = size;
1859 hdr->magic = MAGICWORD;
1860 ((char *) &hdr[1])[size] = MAGICBYTE;
1861 flood ((__ptr_t) (hdr + 1), MALLOCFLOOD, size);
1862 return (__ptr_t) (hdr + 1);
1865 static __ptr_t reallochook __P ((__ptr_t, __malloc_size_t));
1866 static __ptr_t
1867 reallochook (ptr, size)
1868 __ptr_t ptr;
1869 __malloc_size_t size;
1871 struct hdr *hdr = NULL;
1872 __malloc_size_t osize = 0;
1874 if (ptr)
1876 hdr = ((struct hdr *) ptr) - 1;
1877 osize = hdr->size;
1879 checkhdr (hdr);
1880 if (size < osize)
1881 flood ((char *) ptr + size, FREEFLOOD, osize - size);
1884 __free_hook = old_free_hook;
1885 __malloc_hook = old_malloc_hook;
1886 __realloc_hook = old_realloc_hook;
1887 hdr = (struct hdr *) realloc ((__ptr_t) hdr, sizeof (struct hdr) + size + 1);
1888 __free_hook = freehook;
1889 __malloc_hook = mallochook;
1890 __realloc_hook = reallochook;
1891 if (hdr == NULL)
1892 return NULL;
1894 hdr->size = size;
1895 hdr->magic = MAGICWORD;
1896 ((char *) &hdr[1])[size] = MAGICBYTE;
1897 if (size > osize)
1898 flood ((char *) (hdr + 1) + osize, MALLOCFLOOD, size - osize);
1899 return (__ptr_t) (hdr + 1);
1902 static void
1903 mabort (status)
1904 enum mcheck_status status;
1906 const char *msg;
1907 switch (status)
1909 case MCHECK_OK:
1910 msg = "memory is consistent, library is buggy";
1911 break;
1912 case MCHECK_HEAD:
1913 msg = "memory clobbered before allocated block";
1914 break;
1915 case MCHECK_TAIL:
1916 msg = "memory clobbered past end of allocated block";
1917 break;
1918 case MCHECK_FREE:
1919 msg = "block freed twice";
1920 break;
1921 default:
1922 msg = "bogus mcheck_status, library is buggy";
1923 break;
1925 #ifdef __GNU_LIBRARY__
1926 __libc_fatal (msg);
1927 #else
1928 fprintf (stderr, "mcheck: %s\n", msg);
1929 fflush (stderr);
1930 abort ();
1931 #endif
1934 static int mcheck_used = 0;
1937 mcheck (func)
1938 void (*func) __P ((enum mcheck_status));
1940 abortfunc = (func != NULL) ? func : &mabort;
1942 /* These hooks may not be safely inserted if malloc is already in use. */
1943 if (!__malloc_initialized && !mcheck_used)
1945 old_free_hook = __free_hook;
1946 __free_hook = freehook;
1947 old_malloc_hook = __malloc_hook;
1948 __malloc_hook = mallochook;
1949 old_realloc_hook = __realloc_hook;
1950 __realloc_hook = reallochook;
1951 mcheck_used = 1;
1954 return mcheck_used ? 0 : -1;
1957 enum mcheck_status
1958 mprobe (__ptr_t ptr)
1960 return mcheck_used ? checkhdr (ptr) : MCHECK_DISABLED;
1963 #endif /* GC_MCHECK */