2 /* gmalloc.c - THIS FILE IS AUTOMAGICALLY GENERATED SO DON'T EDIT IT. */
4 /* Single-file skeleton for GNU malloc.
5 Copyright 1989 Free Software Foundation
6 Written May 1989 by Mike Haertel.
8 The author may be reached (Email) at the address mike@ai.mit.edu,
9 or (US mail) as Mike Haertel c/o Free Software Foundation.
11 This program is free software; you can redistribute it and/or modify
12 it under the terms of the GNU General Public License as published by
13 the Free Software Foundation; either version 2 of the License, or
14 (at your option) any later version.
16 This program 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
19 GNU General Public License for more details.
21 You should have received a copy of the GNU General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
27 /* DO NOT DELETE THIS LINE -- ansidecl.h INSERTED HERE. */
28 /* Copyright (C) 1989 Free Software Foundation, Inc.
29 This file is part of the GNU C Library.
31 This program is free software; you can redistribute it and/or modify
32 it under the terms of the GNU General Public License as published by
33 the Free Software Foundation; either version 2 of the License, or
34 (at your option) any later version.
36 This program is distributed in the hope that it will be useful,
37 but WITHOUT ANY WARRANTY; without even the implied warranty of
38 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
39 GNU General Public License for more details.
41 You should have received a copy of the GNU General Public License
42 along with this program; if not, write to the Free Software
43 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
45 /* ANSI and traditional C compatibility macros
47 ANSI C is assumed if __STDC__ is #defined.
50 PTR - Generic pointer type
51 LONG_DOUBLE - `long double' type
52 CONST - `const' keyword
53 VOLATILE - `volatile' keyword
54 SIGNED - `signed' keyword
55 PTRCONST - Generic const pointer (void *const)
57 EXFUN(name, prototype) - declare external function NAME
58 with prototype PROTOTYPE
59 DEFUN(name, arglist, args) - define function NAME with
60 args ARGLIST of types in ARGS
61 DEFUN_VOID(name) - define function NAME with no args
62 AND - argument separator for ARGS
67 extern int EXFUN(printf, (CONST char *format DOTS));
68 int DEFUN(fprintf, (stream, format),
69 FILE *stream AND CONST char *format DOTS) { ... }
70 void DEFUN_VOID(abort) { ... }
78 /* Every source file includes this file,
79 so they will all get the switch for lint. */
86 #define PTRCONST void *CONST
87 #define LONG_DOUBLE long double
92 #define VOLATILE volatile
96 #define EXFUN(name, proto) name proto
97 #define DEFUN(name, arglist, args) name(args)
98 #define DEFUN_VOID(name) name(NOARGS)
100 #else /* Not ANSI C. */
104 #define LONG_DOUBLE double
113 #define EXFUN(name, proto) name()
114 #define DEFUN(name, arglist, args) name arglist args;
115 #define DEFUN_VOID(name) name()
120 #endif /* ansidecl.h */
125 /* DO NOT DELETE THIS LINE -- limits.h INSERTED HERE. */
126 /* Number of bits in a `char'. */
129 /* No multibyte characters supported yet. */
132 /* Minimum and maximum values a `signed char' can hold. */
133 #define SCHAR_MIN -128
134 #define SCHAR_MAX 127
136 /* Maximum value an `unsigned char' can hold. (Minimum is 0). */
137 #define UCHAR_MAX 255U
139 /* Minimum and maximum values a `char' can hold. */
140 #ifdef __CHAR_UNSIGNED__
142 #define CHAR_MAX 255U
144 #define CHAR_MIN -128
148 /* Minimum and maximum values a `signed short int' can hold. */
149 #define SHRT_MIN -32768
150 #define SHRT_MAX 32767
152 /* Maximum value an `unsigned short int' can hold. (Minimum is 0). */
153 #define USHRT_MAX 65535U
155 /* Minimum and maximum values a `signed int' can hold. */
156 #define INT_MIN -2147483648
157 #define INT_MAX 2147483647
159 /* Maximum value an `unsigned int' can hold. (Minimum is 0). */
160 #define UINT_MAX 4294967295U
162 /* Minimum and maximum values a `signed long int' can hold.
164 #define LONG_MIN (-LONG_MAX-1)
165 #define LONG_MAX 2147483647
167 /* Maximum value an `unsigned long int' can hold. (Minimum is 0). */
168 #define ULONG_MAX 4294967295U
174 /* DO NOT DELETE THIS LINE -- stddef.h INSERTED HERE. */
178 /* Signed type of difference of two pointers. */
180 typedef long ptrdiff_t;
182 /* Unsigned type of `sizeof' something. */
184 #ifndef _SIZE_T /* in case <sys/types.h> has defined it. */
186 typedef unsigned long size_t;
189 /* A null pointer constant. */
191 #undef NULL /* in case <stdio.h> has defined it. */
194 /* Offset of member MEMBER in a struct of type TYPE. */
196 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
198 #endif /* _STDDEF_H */
201 /* DO NOT DELETE THIS LINE -- stdlib.h INSERTED HERE. */
202 /* Fake stdlib.h supplying the stuff needed by malloc. */
208 extern void EXFUN(abort
, (NOARGS
));
209 extern void EXFUN(free
, (PTR
));
210 extern PTR
EXFUN(malloc
, (size_t));
211 extern PTR
EXFUN(realloc
, (PTR
, size_t));
213 /* DO NOT DELETE THIS LINE -- string.h INSERTED HERE. */
214 /* Fake string.h supplying stuff used by malloc. */
219 extern PTR
EXFUN(memcpy
, (PTR
, CONST PTR
, size_t));
220 extern PTR
EXFUN(memset
, (PTR
, int, size_t));
221 #define memmove memcpy
223 #define _MALLOC_INTERNAL
224 /* DO NOT DELETE THIS LINE -- malloc.h INSERTED HERE. */
225 /* Declarations for `malloc' and friends.
226 Copyright 1990 Free Software Foundation
227 Written May 1989 by Mike Haertel.
229 The author may be reached (Email) at the address mike@ai.mit.edu,
230 or (US mail) as Mike Haertel c/o Free Software Foundation.
232 This program is free software; you can redistribute it and/or modify
233 it under the terms of the GNU General Public License as published by
234 the Free Software Foundation; either version 2 of the License, or
235 (at your option) any later version.
237 This program is distributed in the hope that it will be useful,
238 but WITHOUT ANY WARRANTY; without even the implied warranty of
239 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
240 GNU General Public License for more details.
242 You should have received a copy of the GNU General Public License
243 along with this program; if not, write to the Free Software
244 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
252 #define __need_size_t
253 #define __need_ptrdiff_t
257 #ifdef _MALLOC_INTERNAL
263 /* The allocator divides the heap into blocks of fixed size; large
264 requests receive one or more whole blocks, and small requests
265 receive a fragment of a block. Fragment sizes are powers of two,
266 and all fragments of a block are the same size. When all the
267 fragments in a block have been freed, the block itself is freed. */
268 #define INT_BIT (CHAR_BIT * sizeof(int))
269 #define BLOCKLOG (INT_BIT > 16 ? 12 : 9)
270 #define BLOCKSIZE ((unsigned int) 1 << BLOCKLOG)
271 #define BLOCKIFY(SIZE) (((SIZE) + BLOCKSIZE - 1) / BLOCKSIZE)
273 /* The difference between two pointers is a signed int. On machines where
274 the data addresses have the high bit set, we need to ensure that the
275 difference becomes an unsigned int when we are using the address as an
276 integral value. In addition, when using with the '%' operator, the
277 sign of the result is machine dependent for negative values, so force
278 it to be treated as an unsigned int. */
280 #define ADDR2UINT(addr) ((unsigned int) ((char *) (addr) - (char *) NULL))
281 #define RESIDUAL(addr) ((unsigned int) (ADDR2UINT (addr) % BLOCKSIZE))
283 /* Determine the amount of memory spanned by the initial heap table
284 (not an absolute limit). */
285 #define HEAP (INT_BIT > 16 ? 4194304 : 65536)
287 /* Number of contiguous free blocks allowed to build up at the end of
288 memory before they will be returned to the system. */
289 #define FINAL_FREE_BLOCKS 8
291 /* Where to start searching the free list when looking for new memory.
292 The two possible values are 0 and _heapindex. Starting at 0 seems
293 to reduce total memory usage, while starting at _heapindex seems to
295 #define MALLOC_SEARCH_START _heapindex
297 /* Data structure giving per-block information. */
300 /* Heap information for a busy block. */
303 /* Zero for a large block, or positive giving the
304 logarithm to the base two of the fragment size. */
310 size_t nfree
; /* Free fragments in a fragmented block. */
311 size_t first
; /* First free fragment of the block. */
313 /* Size (in blocks) of a large cluster. */
317 /* Heap information for a free block (that may be the first of
321 size_t size
; /* Size (in blocks) of a free cluster. */
322 size_t next
; /* Index of next free cluster. */
323 size_t prev
; /* Index of previous free cluster. */
327 /* Pointer to first block of the heap. */
328 extern char *_heapbase
;
330 /* Table indexed by block number giving per-block information. */
331 extern malloc_info
*_heapinfo
;
333 /* Address to block number and vice versa. */
334 #define BLOCK(A) (((char *) (A) - _heapbase) / BLOCKSIZE + 1)
335 #define ADDRESS(B) ((PTR) (((B) - 1) * BLOCKSIZE + _heapbase))
337 /* Current search index for the heap table. */
338 extern size_t _heapindex
;
340 /* Limit of valid info table indices. */
341 extern size_t _heaplimit
;
343 /* Doubly linked lists of free fragments. */
350 /* Free list headers for each fragment size. */
351 extern struct list _fraghead
[];
353 /* Instrumentation. */
354 extern size_t _chunks_used
;
355 extern size_t _bytes_used
;
356 extern size_t _chunks_free
;
357 extern size_t _bytes_free
;
359 /* Internal version of free() used in morecore(). */
360 extern void EXFUN(__free
, (PTR __ptr
));
362 #endif /* _MALLOC_INTERNAL. */
364 /* Underlying allocation function; successive calls should
365 return contiguous pieces of memory. */
366 extern PTR
EXFUN((*__morecore
), (ptrdiff_t __size
));
368 /* Default value of previous. */
369 extern PTR
EXFUN(__default_morecore
, (ptrdiff_t __size
));
371 /* Flag whether malloc has been called. */
372 extern int __malloc_initialized
;
374 /* Hooks for debugging versions. */
375 extern void EXFUN((*__free_hook
), (PTR __ptr
));
376 extern PTR
EXFUN((*__malloc_hook
), (size_t __size
));
377 extern PTR
EXFUN((*__realloc_hook
), (PTR __ptr
, size_t __size
));
379 /* Activate a standard collection of debugging hooks. */
380 extern void EXFUN(mcheck
, (void EXFUN((*func
), (NOARGS
))));
382 /* Statistics available to the user. */
385 size_t bytes_total
; /* Total size of the heap. */
386 size_t chunks_used
; /* Chunks allocated by the user. */
387 size_t bytes_used
; /* Byte total of user-allocated chunks. */
388 size_t chunks_free
; /* Chunks in the free list. */
389 size_t bytes_free
; /* Byte total of chunks in the free list. */
392 /* Pick up the current statistics. */
393 extern struct mstats
EXFUN(mstats
, (NOARGS
));
395 #endif /* malloc.h */
397 /* DO NOT DELETE THIS LINE -- free.c INSERTED HERE. */
398 /* Free a block of memory allocated by `malloc'.
399 Copyright 1990 Free Software Foundation
400 Written May 1989 by Mike Haertel.
402 The author may be reached (Email) at the address mike@ai.mit.edu,
403 or (US mail) as Mike Haertel c/o Free Software Foundation.
405 This program is free software; you can redistribute it and/or modify
406 it under the terms of the GNU General Public License as published by
407 the Free Software Foundation; either version 2 of the License, or
408 (at your option) any later version.
410 This program is distributed in the hope that it will be useful,
411 but WITHOUT ANY WARRANTY; without even the implied warranty of
412 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
413 GNU General Public License for more details.
415 You should have received a copy of the GNU General Public License
416 along with this program; if not, write to the Free Software
417 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
420 #include "ansidecl.h"
424 #define _MALLOC_INTERNAL
426 #endif /* __ONEFILE */
428 /* Debugging hook for free. */
429 void EXFUN((*__free_hook
), (PTR __ptr
));
431 /* Return memory to the heap. Like free() but don't call a __free_hook
434 DEFUN(__free
, (ptr
), PTR ptr
)
437 size_t block
, blocks
;
439 struct list
*prev
, *next
;
443 type
= _heapinfo
[block
].busy
.type
;
447 /* Get as many statistics as early as we can. */
449 _bytes_used
-= _heapinfo
[block
].busy
.info
.size
* BLOCKSIZE
;
450 _bytes_free
+= _heapinfo
[block
].busy
.info
.size
* BLOCKSIZE
;
452 /* Find the free cluster previous to this one in the free list.
453 Start searching at the last block referenced; this may benefit
454 programs with locality of allocation. */
458 i
= _heapinfo
[i
].free
.prev
;
462 i
= _heapinfo
[i
].free
.next
;
463 while (i
> 0 && i
< block
);
464 i
= _heapinfo
[i
].free
.prev
;
467 /* Determine how to link this block into the free list. */
468 if (block
== i
+ _heapinfo
[i
].free
.size
)
470 /* Coalesce this block with its predecessor. */
471 _heapinfo
[i
].free
.size
+= _heapinfo
[block
].busy
.info
.size
;
476 /* Really link this block back into the free list. */
477 _heapinfo
[block
].free
.size
= _heapinfo
[block
].busy
.info
.size
;
478 _heapinfo
[block
].free
.next
= _heapinfo
[i
].free
.next
;
479 _heapinfo
[block
].free
.prev
= i
;
480 _heapinfo
[i
].free
.next
= block
;
481 _heapinfo
[_heapinfo
[block
].free
.next
].free
.prev
= block
;
485 /* Now that the block is linked in, see if we can coalesce it
486 with its successor (by deleting its successor from the list
487 and adding in its size). */
488 if (block
+ _heapinfo
[block
].free
.size
== _heapinfo
[block
].free
.next
)
490 _heapinfo
[block
].free
.size
491 += _heapinfo
[_heapinfo
[block
].free
.next
].free
.size
;
492 _heapinfo
[block
].free
.next
493 = _heapinfo
[_heapinfo
[block
].free
.next
].free
.next
;
494 _heapinfo
[_heapinfo
[block
].free
.next
].free
.prev
= block
;
498 /* Now see if we can return stuff to the system. */
499 blocks
= _heapinfo
[block
].free
.size
;
500 if (blocks
>= FINAL_FREE_BLOCKS
&& block
+ blocks
== _heaplimit
501 && (*__morecore
)(0) == ADDRESS(block
+ blocks
))
503 register size_t bytes
= blocks
* BLOCKSIZE
;
504 _heaplimit
-= blocks
;
505 (*__morecore
)(- bytes
);
506 _heapinfo
[_heapinfo
[block
].free
.prev
].free
.next
507 = _heapinfo
[block
].free
.next
;
508 _heapinfo
[_heapinfo
[block
].free
.next
].free
.prev
509 = _heapinfo
[block
].free
.prev
;
510 block
= _heapinfo
[block
].free
.prev
;
512 _bytes_free
-= bytes
;
515 /* Set the next search to begin at this block. */
520 /* Do some of the statistics. */
522 _bytes_used
-= 1 << type
;
524 _bytes_free
+= 1 << type
;
526 /* Get the address of the first free fragment in this block. */
527 prev
= (struct list
*) ((char *) ADDRESS(block
) +
528 (_heapinfo
[block
].busy
.info
.frag
.first
<< type
));
530 if (_heapinfo
[block
].busy
.info
.frag
.nfree
== (BLOCKSIZE
>> type
) - 1)
532 /* If all fragments of this block are free, remove them
533 from the fragment list and free the whole block. */
535 for (i
= 1; i
< BLOCKSIZE
>> type
; ++i
)
537 prev
->prev
->next
= next
;
539 next
->prev
= prev
->prev
;
540 _heapinfo
[block
].busy
.type
= 0;
541 _heapinfo
[block
].busy
.info
.size
= 1;
543 /* Keep the statistics accurate. */
545 _bytes_used
+= BLOCKSIZE
;
546 _chunks_free
-= BLOCKSIZE
>> type
;
547 _bytes_free
-= BLOCKSIZE
;
549 free(ADDRESS(block
));
551 else if (_heapinfo
[block
].busy
.info
.frag
.nfree
!= 0)
553 /* If some fragments of this block are free, link this
554 fragment into the fragment list after the first free
555 fragment of this block. */
556 next
= (struct list
*) ptr
;
557 next
->next
= prev
->next
;
560 if (next
->next
!= NULL
)
561 next
->next
->prev
= next
;
562 ++_heapinfo
[block
].busy
.info
.frag
.nfree
;
566 /* No fragments of this block are free, so link this
567 fragment into the fragment list and announce that
568 it is the first free fragment of this block. */
569 prev
= (struct list
*) ptr
;
570 _heapinfo
[block
].busy
.info
.frag
.nfree
= 1;
571 _heapinfo
[block
].busy
.info
.frag
.first
= RESIDUAL (ptr
) >> type
;
572 prev
->next
= _fraghead
[type
].next
;
573 prev
->prev
= &_fraghead
[type
];
574 prev
->prev
->next
= prev
;
575 if (prev
->next
!= NULL
)
576 prev
->next
->prev
= prev
;
582 /* Return memory to the heap. */
584 DEFUN(free
, (ptr
), PTR ptr
)
589 if (__free_hook
!= NULL
)
595 /* DO NOT DELETE THIS LINE -- malloc.c INSERTED HERE. */
596 /* Memory allocator `malloc'.
597 Copyright 1990 Free Software Foundation
598 Written May 1989 by Mike Haertel.
600 The author may be reached (Email) at the address mike@ai.mit.edu,
601 or (US mail) as Mike Haertel c/o Free Software Foundation.
603 This program is free software; you can redistribute it and/or modify
604 it under the terms of the GNU General Public License as published by
605 the Free Software Foundation; either version 2 of the License, or
606 (at your option) any later version.
608 This program is distributed in the hope that it will be useful,
609 but WITHOUT ANY WARRANTY; without even the implied warranty of
610 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
611 GNU General Public License for more details.
613 You should have received a copy of the GNU General Public License
614 along with this program; if not, write to the Free Software
615 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
618 #include "ansidecl.h"
623 #define _MALLOC_INTERNAL
625 #endif /* __ONEFILE */
627 /* How to really get more memory. */
628 PTR
EXFUN((*__morecore
), (ptrdiff_t __size
)) = __default_morecore
;
630 /* Debugging hook for `malloc'. */
631 PTR
EXFUN((*__malloc_hook
), (size_t __size
));
633 /* Pointer to the base of the first block. */
636 /* Block information table. Allocated with align/__free (not malloc/free). */
637 malloc_info
*_heapinfo
;
639 /* Number of info entries. */
640 static size_t heapsize
;
642 /* Search index in the info table. */
645 /* Limit of valid info table indices. */
648 /* Free lists for each fragment size. */
649 struct list _fraghead
[BLOCKLOG
];
651 /* Instrumentation. */
657 /* Are you experienced? */
658 int __malloc_initialized
;
660 /* Aligned allocation. */
662 DEFUN(align
, (size
), size_t size
)
667 result
= (*__morecore
)(size
);
668 adj
= RESIDUAL (result
);
671 adj
= BLOCKSIZE
- adj
;
672 (void) (*__morecore
)(adj
);
673 result
= (char *) result
+ adj
;
678 /* Set everything up and remember that we have. */
680 DEFUN_VOID(initialize
)
682 heapsize
= HEAP
/ BLOCKSIZE
;
683 _heapinfo
= (malloc_info
*) align(heapsize
* sizeof(malloc_info
));
684 if (_heapinfo
== NULL
)
686 memset(_heapinfo
, 0, heapsize
* sizeof(malloc_info
));
687 _heapinfo
[0].free
.size
= 0;
688 _heapinfo
[0].free
.next
= _heapinfo
[0].free
.prev
= 0;
690 _heapbase
= (char *) _heapinfo
;
691 __malloc_initialized
= 1;
695 /* Get neatly aligned memory, initializing or
696 growing the heap info table as necessary. */
698 DEFUN(morecore
, (size
), size_t size
)
701 malloc_info
*newinfo
, *oldinfo
;
704 result
= align(size
);
708 /* Check if we need to grow the info table. */
709 if (BLOCK((char *) result
+ size
) > heapsize
)
712 while (BLOCK((char *) result
+ size
) > newsize
)
714 newinfo
= (malloc_info
*) align(newsize
* sizeof(malloc_info
));
717 (*__morecore
)(- size
);
720 memset(newinfo
, 0, newsize
* sizeof(malloc_info
));
721 memcpy(newinfo
, _heapinfo
, heapsize
* sizeof(malloc_info
));
723 newinfo
[BLOCK(oldinfo
)].busy
.type
= 0;
724 newinfo
[BLOCK(oldinfo
)].busy
.info
.size
725 = BLOCKIFY(heapsize
* sizeof(malloc_info
));
731 _heaplimit
= BLOCK((char *) result
+ size
);
735 /* Allocate memory from the heap. */
737 DEFUN(malloc
, (size
), size_t size
)
740 size_t block
, blocks
, lastblocks
, start
;
747 if (__malloc_hook
!= NULL
)
748 return (*__malloc_hook
)(size
);
750 if (!__malloc_initialized
)
754 if (size
< sizeof(struct list
))
755 size
= sizeof(struct list
);
757 /* Determine the allocation policy based on the request size. */
758 if (size
<= BLOCKSIZE
/ 2)
760 /* Small allocation to receive a fragment of a block.
761 Determine the logarithm to base two of the fragment size. */
762 register size_t log
= 1;
764 while ((size
/= 2) != 0)
767 /* Look in the fragment lists for a
768 free fragment of the desired size. */
769 next
= _fraghead
[log
].next
;
772 /* There are free fragments of this size.
773 Pop a fragment out of the fragment list and return it.
774 Update the block's nfree and first counters. */
776 next
->prev
->next
= next
->next
;
777 if (next
->next
!= NULL
)
778 next
->next
->prev
= next
->prev
;
779 block
= BLOCK(result
);
780 if (--_heapinfo
[block
].busy
.info
.frag
.nfree
!= 0)
781 _heapinfo
[block
].busy
.info
.frag
.first
=
782 RESIDUAL (next
->next
) >> log
;
784 /* Update the statistics. */
786 _bytes_used
+= 1 << log
;
788 _bytes_free
-= 1 << log
;
792 /* No free fragments of the desired size, so get a new block
793 and break it into fragments, returning the first. */
794 result
= malloc(BLOCKSIZE
);
798 /* Link all fragments but the first into the free list. */
799 for (i
= 1; i
< BLOCKSIZE
>> log
; ++i
)
801 next
= (struct list
*) ((char *) result
+ (i
<< log
));
802 next
->next
= _fraghead
[log
].next
;
803 next
->prev
= &_fraghead
[log
];
804 next
->prev
->next
= next
;
805 if (next
->next
!= NULL
)
806 next
->next
->prev
= next
;
809 /* Initialize the nfree and first counters for this block. */
810 block
= BLOCK(result
);
811 _heapinfo
[block
].busy
.type
= log
;
812 _heapinfo
[block
].busy
.info
.frag
.nfree
= i
- 1;
813 _heapinfo
[block
].busy
.info
.frag
.first
= i
- 1;
815 _chunks_free
+= (BLOCKSIZE
>> log
) - 1;
816 _bytes_free
+= BLOCKSIZE
- (1 << log
);
821 /* Large allocation to receive one or more blocks.
822 Search the free list in a circle starting at the last place visited.
823 If we loop completely around without finding a large enough
824 space we will have to get more memory from the system. */
825 blocks
= BLOCKIFY(size
);
826 start
= block
= MALLOC_SEARCH_START
;
827 while (_heapinfo
[block
].free
.size
< blocks
)
829 block
= _heapinfo
[block
].free
.next
;
832 /* Need to get more from the system. Check to see if
833 the new core will be contiguous with the final free
834 block; if so we don't need to get as much. */
835 block
= _heapinfo
[0].free
.prev
;
836 lastblocks
= _heapinfo
[block
].free
.size
;
837 if (_heaplimit
!= 0 && block
+ lastblocks
== _heaplimit
&&
838 (*__morecore
)(0) == ADDRESS(block
+ lastblocks
) &&
839 (morecore((blocks
- lastblocks
) * BLOCKSIZE
)) != NULL
)
841 _heapinfo
[block
].free
.size
= blocks
;
842 _bytes_free
+= (blocks
- lastblocks
) * BLOCKSIZE
;
845 result
= morecore(blocks
* BLOCKSIZE
);
848 block
= BLOCK(result
);
849 _heapinfo
[block
].busy
.type
= 0;
850 _heapinfo
[block
].busy
.info
.size
= blocks
;
852 _bytes_used
+= blocks
* BLOCKSIZE
;
857 /* At this point we have found a suitable free list entry.
858 Figure out how to remove what we need from the list. */
859 result
= ADDRESS(block
);
860 if (_heapinfo
[block
].free
.size
> blocks
)
862 /* The block we found has a bit left over,
863 so relink the tail end back into the free list. */
864 _heapinfo
[block
+ blocks
].free
.size
865 = _heapinfo
[block
].free
.size
- blocks
;
866 _heapinfo
[block
+ blocks
].free
.next
867 = _heapinfo
[block
].free
.next
;
868 _heapinfo
[block
+ blocks
].free
.prev
869 = _heapinfo
[block
].free
.prev
;
870 _heapinfo
[_heapinfo
[block
].free
.prev
].free
.next
871 = _heapinfo
[_heapinfo
[block
].free
.next
].free
.prev
872 = _heapindex
= block
+ blocks
;
876 /* The block exactly matches our requirements,
877 so just remove it from the list. */
878 _heapinfo
[_heapinfo
[block
].free
.next
].free
.prev
879 = _heapinfo
[block
].free
.prev
;
880 _heapinfo
[_heapinfo
[block
].free
.prev
].free
.next
881 = _heapindex
= _heapinfo
[block
].free
.next
;
885 _heapinfo
[block
].busy
.type
= 0;
886 _heapinfo
[block
].busy
.info
.size
= blocks
;
888 _bytes_used
+= blocks
* BLOCKSIZE
;
889 _bytes_free
-= blocks
* BLOCKSIZE
;
895 /* DO NOT DELETE THIS LINE -- realloc.c INSERTED HERE. */
896 /* Change the size of a block allocated by `malloc'.
897 Copyright 1990 Free Software Foundation
898 Written May 1989 by Mike Haertel.
900 The author may be reached (Email) at the address mike@ai.mit.edu,
901 or (US mail) as Mike Haertel c/o Free Software Foundation.
903 This program is free software; you can redistribute it and/or modify
904 it under the terms of the GNU General Public License as published by
905 the Free Software Foundation; either version 2 of the License, or
906 (at your option) any later version.
908 This program is distributed in the hope that it will be useful,
909 but WITHOUT ANY WARRANTY; without even the implied warranty of
910 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
911 GNU General Public License for more details.
913 You should have received a copy of the GNU General Public License
914 along with this program; if not, write to the Free Software
915 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
918 #include "ansidecl.h"
922 #define _MALLOC_INTERNAL
924 #endif /* __ONEFILE */
926 #define MIN(A, B) ((A) < (B) ? (A) : (B))
928 /* Debugging hook for realloc. */
929 PTR
EXFUN((*__realloc_hook
), (PTR __ptr
, size_t __size
));
931 /* Resize the given region to the new size, returning a pointer
932 to the (possibly moved) region. This is optimized for speed;
933 some benchmarks seem to indicate that greater compactness is
934 achieved by unconditionally allocating and copying to a
935 new region. This module has incestuous knowledge of the
936 internals of both free and malloc. */
938 DEFUN(realloc
, (ptr
, size
), PTR ptr AND
size_t size
)
942 size_t block
, blocks
, oldlimit
;
949 else if (ptr
== NULL
)
952 if (__realloc_hook
!= NULL
)
953 return (*__realloc_hook
)(ptr
, size
);
957 type
= _heapinfo
[block
].busy
.type
;
961 /* Maybe reallocate a large block to a small fragment. */
962 if (size
<= BLOCKSIZE
/ 2)
964 result
= malloc(size
);
967 memcpy(result
, ptr
, size
);
973 /* The new size is a large allocation as well;
974 see if we can hold it in place. */
975 blocks
= BLOCKIFY(size
);
976 if (blocks
< _heapinfo
[block
].busy
.info
.size
)
978 /* The new size is smaller; return
979 excess memory to the free list. */
980 _heapinfo
[block
+ blocks
].busy
.type
= 0;
981 _heapinfo
[block
+ blocks
].busy
.info
.size
982 = _heapinfo
[block
].busy
.info
.size
- blocks
;
983 _heapinfo
[block
].busy
.info
.size
= blocks
;
984 free(ADDRESS(block
+ blocks
));
987 else if (blocks
== _heapinfo
[block
].busy
.info
.size
)
988 /* No size change necessary. */
992 /* Won't fit, so allocate a new region that will.
993 Free the old region first in case there is sufficient
994 adjacent free space to grow without moving. */
995 blocks
= _heapinfo
[block
].busy
.info
.size
;
996 /* Prevent free from actually returning memory to the system. */
997 oldlimit
= _heaplimit
;
1000 _heaplimit
= oldlimit
;
1001 result
= malloc(size
);
1004 (void) malloc(blocks
* BLOCKSIZE
);
1008 memmove(result
, ptr
, blocks
* BLOCKSIZE
);
1013 /* Old size is a fragment; type is logarithm
1014 to base two of the fragment size. */
1015 if (size
> 1 << (type
- 1) && size
<= 1 << type
)
1016 /* The new size is the same kind of fragment. */
1020 /* The new size is different; allocate a new space,
1021 and copy the lesser of the new size and the old. */
1022 result
= malloc(size
);
1025 memcpy(result
, ptr
, MIN(size
, 1 << type
));
1034 /* DO NOT DELETE THIS LINE -- unix.c INSERTED HERE. */
1035 /* unix.c - get more memory with a UNIX system call.
1036 Copyright 1990 Free Software Foundation
1037 Written May 1989 by Mike Haertel.
1039 The author may be reached (Email) at the address mike@ai.mit.edu,
1040 or (US mail) as Mike Haertel c/o Free Software Foundation.
1042 This program is free software; you can redistribute it and/or modify
1043 it under the terms of the GNU General Public License as published by
1044 the Free Software Foundation; either version 2 of the License, or
1045 (at your option) any later version.
1047 This program is distributed in the hope that it will be useful,
1048 but WITHOUT ANY WARRANTY; without even the implied warranty of
1049 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1050 GNU General Public License for more details.
1052 You should have received a copy of the GNU General Public License
1053 along with this program; if not, write to the Free Software
1054 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
1057 #include "ansidecl.h"
1060 #define _MALLOC_INTERNAL
1062 #endif /* __ONEFILE */
1064 extern PTR
EXFUN(sbrk
, (ptrdiff_t size
));
1067 DEFUN(__default_morecore
, (size
), ptrdiff_t size
)
1071 result
= sbrk(size
);
1072 if (result
== (PTR
) -1)
1077 #define __getpagesize getpagesize
1078 /* DO NOT DELETE THIS LINE -- valloc.c INSERTED HERE. */
1079 /* Allocate memory on a page boundary.
1080 Copyright 1990 Free Software Foundation
1081 Written May 1989 by Mike Haertel.
1083 The author may be reached (Email) at the address mike@ai.mit.edu,
1084 or (US mail) as Mike Haertel c/o Free Software Foundation.
1086 This program is free software; you can redistribute it and/or modify
1087 it under the terms of the GNU General Public License as published by
1088 the Free Software Foundation; either version 2 of the License, or
1089 (at your option) any later version.
1091 This program is distributed in the hope that it will be useful,
1092 but WITHOUT ANY WARRANTY; without even the implied warranty of
1093 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1094 GNU General Public License for more details.
1096 You should have received a copy of the GNU General Public License
1097 along with this program; if not, write to the Free Software
1098 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
1101 #include "ansidecl.h"
1103 #endif /* __ONEFILE */
1107 * M_UNIX is defined by the SCO compilers, including the port of gcc.
1110 /* On SunOS 4.1.1, <sys/param.h> typedefs size_t, which is bad since
1111 we typedef it above. Maybe it's better just to have people compile
1112 -Dgetpagesize()=4096. */
1113 /* Deal with page size. */
1114 #ifndef HAVE_GETPAGESIZE
1116 #include <sys/param.h>
1118 #if !defined (PAGESIZE)
1119 #ifdef EXEC_PAGESIZE
1120 #define PAGESIZE EXEC_PAGESIZE
1123 #define PAGESIZE NBPG * CLSIZE
1126 #endif /* no CLSIZE */
1128 #define PAGESIZE NBPC
1129 #endif /* no NBPG */
1130 #endif /* no EXEC_PAGESIZE */
1131 #endif /* no PAGESIZE */
1134 DEFUN_VOID(__getpagesize
)
1138 #endif /* not HAVE_GETPAGESIZE */
1141 extern size_t EXFUN(__getpagesize
, (NOARGS
));
1143 static size_t pagesize
;
1146 DEFUN(valloc
, (size
), size_t size
)
1152 pagesize
= __getpagesize();
1154 result
= malloc(size
+ pagesize
);
1157 adj
= (unsigned int) ((unsigned int)((char *) result
- (char *) NULL
)) % pagesize
;
1159 result
= (char *) result
+ pagesize
- adj
;
This page took 0.052749 seconds and 4 git commands to generate.