88217db8b10db5ad9bd23aaf84901c1f530c3fb6
[platform/upstream/bash.git] / lib / malloc / malloc.c
1 /* dynamic memory allocation for GNU. */
2
3 /*  Copyright (C) 1985, 1987 Free Software Foundation, Inc.
4
5     This program is free software; you can redistribute it and/or modify
6     it under the terms of the GNU General Public License as published by
7     the Free Software Foundation; either version 1, or (at your option)
8     any later version.
9
10     This program is distributed in the hope that it will be useful,
11     but WITHOUT ANY WARRANTY; without even the implied warranty of
12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13     GNU General Public License for more details.
14
15     You should have received a copy of the GNU General Public License
16     along with this program; if not, write to the Free Software
17     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18
19 In other words, you are welcome to use, share and improve this program.
20 You are forbidden to forbid anyone else to use, share and improve
21 what you give them.   Help stamp out software-hoarding!  */
22
23 /*
24  * @(#)nmalloc.c 1 (Caltech) 2/21/82
25  *
26  *      U of M Modified: 20 Jun 1983 ACT: strange hacks for Emacs
27  *
28  *      Nov 1983, Mike@BRL, Added support for 4.1C/4.2 BSD.
29  *
30  * This is a very fast storage allocator.  It allocates blocks of a small 
31  * number of different sizes, and keeps free lists of each size.  Blocks
32  * that don't exactly fit are passed up to the next larger size.  In this 
33  * implementation, the available sizes are (2^n)-4 (or -16) bytes long.
34  * This is designed for use in a program that uses vast quantities of
35  * memory, but bombs when it runs out.  To make it a little better, it
36  * warns the user when he starts to get near the end.
37  *
38  * June 84, ACT: modified rcheck code to check the range given to malloc,
39  * rather than the range determined by the 2-power used.
40  *
41  * Jan 85, RMS: calls malloc_warning to issue warning on nearly full.
42  * No longer Emacs-specific; can serve as all-purpose malloc for GNU.
43  * You should call malloc_init to reinitialize after loading dumped Emacs.
44  * Call malloc_stats to get info on memory stats if MSTATS turned on.
45  * realloc knows how to return same block given, just changing its size,
46  * if the power of 2 is correct.
47  */
48
49 /*
50  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
51  * smallest allocatable block is 8 bytes.  The overhead information will
52  * go in the first int of the block, and the returned pointer will point
53  * to the second.
54  *
55 #ifdef MSTATS
56  * nmalloc[i] is the difference between the number of mallocs and frees
57  * for a given block size.
58 #endif
59  */
60
61 /* Define this to have free() write 0xcf into memory as it's freed, to
62    uncover callers that refer to freed memory. */
63 /* SCO 3.2v4 getcwd and possibly other libc routines fail with MEMSCRAMBLE */
64 #if !defined (NO_MEMSCRAMBLE)
65 #  define MEMSCRAMBLE
66 #endif
67
68 #if defined (emacs) || defined (HAVE_CONFIG_H)
69 #  include <config.h>
70 #endif /* emacs */
71
72 #if defined (HAVE_UNISTD_H)
73 #  include <unistd.h>
74 #endif
75
76 /* Determine which kind of system this is.  */
77 #include <sys/types.h>
78 #include <signal.h>
79
80 /* Define getpagesize () if the system does not.  */
81 #ifndef HAVE_GETPAGESIZE
82 #  include "getpagesize.h"
83 #endif
84
85 #if defined (HAVE_RESOURCE)
86 #  include <sys/time.h>
87 #  include <sys/resource.h>
88 #endif /* HAVE_RESOURCE */
89
90 /* Check for the needed symbols.  If they aren't present, this
91    system's <sys/resource.h> isn't very useful to us. */
92 #if !defined (RLIMIT_DATA)
93 #  undef HAVE_RESOURCE
94 #endif
95
96 #if !defined (NULL)
97 #  define NULL 0
98 #endif
99
100 #define start_of_data() &etext
101
102 #define ISALLOC ((char) 0xf7)   /* magic byte that implies allocation */
103 #define ISFREE ((char) 0x54)    /* magic byte that implies free block */
104                                 /* this is for error checking only */
105 #define ISMEMALIGN ((char) 0xd6)  /* Stored before the value returned by
106                                      memalign, with the rest of the word
107                                      being the distance to the true
108                                      beginning of the block.  */
109 extern char etext;
110
111 #if !defined (SBRK_DECLARED)
112 extern char *sbrk ();
113 #endif /* !SBRK_DECLARED */
114
115 /* These two are for user programs to look at, when they are interested.  */
116 unsigned int malloc_sbrk_used;       /* amount of data space used now */
117 unsigned int malloc_sbrk_unused;     /* amount more we can have */
118
119 /* start of data space; can be changed by calling init_malloc */
120 static char *data_space_start;
121
122 static void get_lim_data ();
123
124 #ifdef MSTATS
125 static int nmalloc[30];
126 static int nmal, nfre;
127 #endif /* MSTATS */
128
129 /* If range checking is not turned on, all we have is a flag indicating
130    whether memory is allocated, an index in nextf[], and a size field; to
131    realloc() memory we copy either size bytes or 1<<(index+3) bytes depending
132    on whether the former can hold the exact size (given the value of
133    'index').  If range checking is on, we always need to know how much space
134    is allocated, so the 'size' field is never used. */
135
136 struct mhead {
137         char     mh_alloc;      /* ISALLOC or ISFREE */
138         char     mh_index;      /* index in nextf[] */
139 /* Remainder are valid only when block is allocated */
140         unsigned short mh_size; /* size, if < 0x10000 */
141 #ifdef rcheck
142         unsigned int mh_nbytes; /* number of bytes allocated */
143         int      mh_magic4;     /* should be == MAGIC4 */
144 #endif /* rcheck */
145 };
146
147 /* Access free-list pointer of a block.
148   It is stored at block + 4.
149   This is not a field in the mhead structure
150   because we want sizeof (struct mhead)
151   to describe the overhead for when the block is in use,
152   and we do not want the free-list pointer to count in that.  */
153
154 #define CHAIN(a) \
155   (*(struct mhead **) (sizeof (char *) + (char *) (a)))
156
157 #ifdef rcheck
158 #  include <stdio.h>
159 #  if !defined (botch)
160 #    define botch(x) abort ()
161 #  endif /* botch */
162
163 #  if !defined (__STRING)
164 #    if defined (__STDC__)
165 #      define __STRING(x) #x
166 #    else
167 #      define __STRING(x) "x"
168 #    endif
169 #  endif
170
171   /* To implement range checking, we write magic values in at the beginning
172      and end of each allocated block, and make sure they are undisturbed
173      whenever a free or a realloc occurs. */
174
175   /* Written in each of the 4 bytes following the block's real space */
176 #  define MAGIC1 0x55
177   /* Written in the 4 bytes before the block's real space */
178 #  define MAGIC4 0x55555555
179 #  define ASSERT(p) if (!(p)) botch(__STRING(p)); else
180 #  define EXTRA  4              /* 4 bytes extra for MAGIC1s */
181 #else /* !rcheck */
182 #  define ASSERT(p)
183 #  define EXTRA  0
184 #endif /* rcheck */
185
186 /* nextf[i] is free list of blocks of size 2**(i + 3)  */
187
188 static struct mhead *nextf[30];
189
190 /* busy[i] is nonzero while allocation of block size i is in progress.  */
191
192 static char busy[30];
193
194 /* Number of bytes of writable memory we can expect to be able to get */
195 static unsigned int lim_data;
196
197 /* Level number of warnings already issued.
198   0 -- no warnings issued.
199   1 -- 75% warning already issued.
200   2 -- 85% warning already issued.
201 */
202 static int warnlevel;
203
204 /* Function to call to issue a warning;
205    0 means don't issue them.  */
206 static void (*warnfunction) ();
207
208 /* nonzero once initial bunch of free blocks made */
209 static int gotpool;
210
211 char *_malloc_base;
212
213 static void getpool ();
214
215 /* Cause reinitialization based on job parameters;
216   also declare where the end of pure storage is. */
217 void
218 malloc_init (start, warnfun)
219      char *start;
220      void (*warnfun) ();
221 {
222   if (start)
223     data_space_start = start;
224   lim_data = 0;
225   warnlevel = 0;
226   warnfunction = warnfun;
227 }
228
229 /* Return the maximum size to which MEM can be realloc'd
230    without actually requiring copying.  */
231
232 int
233 malloc_usable_size (mem)
234      char *mem;
235 {
236   int blocksize = 8 << (((struct mhead *) mem) - 1) -> mh_index;
237
238   return blocksize - sizeof (struct mhead) - EXTRA;
239 }
240
241 static void
242 morecore (nu)                   /* ask system for more memory */
243      register int nu;           /* size index to get more of  */
244 {
245   register char *cp;
246   register int nblks;
247   register unsigned int siz;
248
249   /* Block all signals in case we are executed from a signal handler. */
250 #if defined (HAVE_BSD_SIGNALS)
251   int oldmask;
252   oldmask = sigsetmask (-1);
253 #else
254 #  if defined (HAVE_POSIX_SIGNALS)
255   sigset_t set, oset;
256   sigfillset (&set);
257   sigemptyset (&oset);
258   sigprocmask (SIG_BLOCK, &set, &oset);
259 #  endif /* HAVE_POSIX_SIGNALS */
260 #endif /* HAVE_BSD_SIGNALS */
261
262   if (!data_space_start)
263     {
264       data_space_start = start_of_data ();
265     }
266
267   if (lim_data == 0)
268     get_lim_data ();
269
270  /* On initial startup, get two blocks of each size up to 1k bytes */
271   if (!gotpool)
272     { getpool (); getpool (); gotpool = 1; }
273
274   /* Find current end of memory and issue warning if getting near max */
275
276   cp = sbrk (0);
277   siz = cp - data_space_start;
278   malloc_sbrk_used = siz;
279   malloc_sbrk_unused = lim_data - siz;
280
281   if (warnfunction)
282     switch (warnlevel)
283       {
284       case 0: 
285         if (siz > (lim_data / 4) * 3)
286           {
287             warnlevel++;
288             (*warnfunction) ("Warning: past 75% of memory limit");
289           }
290         break;
291       case 1: 
292         if (siz > (lim_data / 20) * 17)
293           {
294             warnlevel++;
295             (*warnfunction) ("Warning: past 85% of memory limit");
296           }
297         break;
298       case 2: 
299         if (siz > (lim_data / 20) * 19)
300           {
301             warnlevel++;
302             (*warnfunction) ("Warning: past 95% of memory limit");
303           }
304         break;
305       }
306
307   if ((int) cp & 0x3ff) /* land on 1K boundaries */
308     sbrk (1024 - ((int) cp & 0x3ff));
309
310  /* Take at least 2k, and figure out how many blocks of the desired size
311     we're about to get */
312   nblks = 1;
313   if ((siz = nu) < 8)
314     nblks = 1 << ((siz = 8) - nu);
315
316   if ((cp = sbrk (1 << (siz + 3))) == (char *) -1)
317     return;                     /* no more room! */
318
319   if ((int) cp & 7)
320     {           /* shouldn't happen, but just in case */
321       cp = (char *) (((int) cp + 8) & ~7);
322       nblks--;
323     }
324
325  /* save new header and link the nblks blocks together */
326   nextf[nu] = (struct mhead *) cp;
327   siz = 1 << (nu + 3);
328   while (1)
329     {
330       ((struct mhead *) cp) -> mh_alloc = ISFREE;
331       ((struct mhead *) cp) -> mh_index = nu;
332       if (--nblks <= 0) break;
333       CHAIN ((struct mhead *) cp) = (struct mhead *) (cp + siz);
334       cp += siz;
335     }
336   CHAIN ((struct mhead *) cp) = 0;
337
338 #if defined (HAVE_BSD_SIGNALS)
339   sigsetmask (oldmask);
340 #else
341 #  if defined (HAVE_POSIX_SIGNALS)
342   sigprocmask (SIG_SETMASK, &oset, (sigset_t *)NULL);
343 #  endif
344 #endif /* HAVE_BSD_SIGNALS */
345 }
346
347 static void
348 getpool ()
349 {
350   register int nu;
351   register char *cp = sbrk (0);
352
353   if ((int) cp & 0x3ff) /* land on 1K boundaries */
354     sbrk (1024 - ((int) cp & 0x3ff));
355
356   /* Record address of start of space allocated by malloc.  */
357   if (_malloc_base == 0)
358     _malloc_base = cp;
359
360   /* Get 2k of storage */
361
362   cp = sbrk (04000);
363   if (cp == (char *) -1)
364     return;
365
366   /* Divide it into an initial 8-word block
367      plus one block of size 2**nu for nu = 3 ... 10.  */
368
369   CHAIN (cp) = nextf[0];
370   nextf[0] = (struct mhead *) cp;
371   ((struct mhead *) cp) -> mh_alloc = ISFREE;
372   ((struct mhead *) cp) -> mh_index = 0;
373   cp += 8;
374
375   for (nu = 0; nu < 7; nu++)
376     {
377       CHAIN (cp) = nextf[nu];
378       nextf[nu] = (struct mhead *) cp;
379       ((struct mhead *) cp) -> mh_alloc = ISFREE;
380       ((struct mhead *) cp) -> mh_index = nu;
381       cp += 8 << nu;
382     }
383 }
384
385 #if defined (MEMSCRAMBLE) || !defined (NO_CALLOC)
386 static char *
387 zmemset (s, c, n)
388      char *s;
389      int c;
390      register int n;
391 {
392   register char *sp;
393
394   sp = s;
395   while (--n >= 0)
396     *sp++ = c;
397   return (s);
398 }
399 #endif /* MEMSCRAMBLE || !NO_CALLOC */
400
401 char *
402 malloc (n)              /* get a block */
403      unsigned int n;
404 {
405   register struct mhead *p;
406   register unsigned int nbytes;
407   register int nunits = 0;
408
409   /* Figure out how many bytes are required, rounding up to the nearest
410      multiple of 4, then figure out which nextf[] area to use */
411   nbytes = (n + sizeof *p + EXTRA + 3) & ~3;
412   {
413     register unsigned int   shiftr = (nbytes - 1) >> 2;
414
415     while (shiftr >>= 1)
416       nunits++;
417   }
418
419   /* In case this is reentrant use of malloc from signal handler,
420      pick a block size that no other malloc level is currently
421      trying to allocate.  That's the easiest harmless way not to
422      interfere with the other level of execution.  */
423   while (busy[nunits]) nunits++;
424   busy[nunits] = 1;
425
426   /* If there are no blocks of the appropriate size, go get some */
427   /* COULD SPLIT UP A LARGER BLOCK HERE ... ACT */
428   if (nextf[nunits] == 0)
429     morecore (nunits);
430
431   /* Get one block off the list, and set the new list head */
432   if ((p = nextf[nunits]) == 0)
433     {
434       busy[nunits] = 0;
435       return 0;
436     }
437   nextf[nunits] = CHAIN (p);
438   busy[nunits] = 0;
439
440   /* Check for free block clobbered */
441   /* If not for this check, we would gobble a clobbered free chain ptr */
442   /* and bomb out on the NEXT allocate of this size block */
443   if (p -> mh_alloc != ISFREE || p -> mh_index != nunits)
444 #ifdef rcheck
445     botch ("block on free list clobbered");
446 #else /* not rcheck */
447     abort ();
448 #endif /* not rcheck */
449
450   /* Fill in the info, and if range checking, set up the magic numbers */
451   p -> mh_alloc = ISALLOC;
452 #ifdef rcheck
453   p -> mh_nbytes = n;
454   p -> mh_magic4 = MAGIC4;
455   {
456     register char  *m = (char *) (p + 1) + n;
457
458     *m++ = MAGIC1, *m++ = MAGIC1, *m++ = MAGIC1, *m = MAGIC1;
459   }
460 #else /* not rcheck */
461   p -> mh_size = n;
462 #endif /* not rcheck */
463 #ifdef MEMSCRAMBLE
464   zmemset ((char *)(p + 1), 0xdf, n);   /* scramble previous contents */
465 #endif
466 #ifdef MSTATS
467   nmalloc[nunits]++;
468   nmal++;
469 #endif /* MSTATS */
470   return (char *) (p + 1);
471 }
472
473 void
474 free (mem)
475      char *mem;
476 {
477   register struct mhead *p;
478   {
479     register char *ap = mem;
480
481     if (ap == 0)
482       return;
483
484     p = (struct mhead *) ap - 1;
485
486     if (p -> mh_alloc == ISMEMALIGN)
487       {
488 #ifdef rcheck
489         ap -= p->mh_nbytes;
490 #endif
491         p = (struct mhead *) ap - 1;
492       }
493
494 #ifndef rcheck
495     if (p -> mh_alloc != ISALLOC)
496       abort ();
497
498 #else /* rcheck */
499     if (p -> mh_alloc != ISALLOC)
500       {
501         if (p -> mh_alloc == ISFREE)
502           botch ("free: Called with already freed block argument\n");
503         else
504           botch ("free: Called with unallocated block argument\n");
505       }
506
507     ASSERT (p -> mh_magic4 == MAGIC4);
508     ap += p -> mh_nbytes;
509     ASSERT (*ap++ == MAGIC1); ASSERT (*ap++ == MAGIC1);
510     ASSERT (*ap++ == MAGIC1); ASSERT (*ap   == MAGIC1);
511 #endif /* rcheck */
512   }
513 #ifdef MEMSCRAMBLE
514   {
515     register int n;
516     
517 #ifdef rcheck
518     n = p->mh_nbytes;
519 #else /* not rcheck */
520     n = p->mh_size;
521 #endif /* not rcheck */
522     zmemset (mem, 0xcf, n);
523   }
524 #endif
525   {
526     register int nunits = p -> mh_index;
527
528     ASSERT (nunits <= 29);
529     p -> mh_alloc = ISFREE;
530
531     /* Protect against signal handlers calling malloc.  */
532     busy[nunits] = 1;
533     /* Put this block on the free list.  */
534     CHAIN (p) = nextf[nunits];
535     nextf[nunits] = p;
536     busy[nunits] = 0;
537
538 #ifdef MSTATS
539     nmalloc[nunits]--;
540     nfre++;
541 #endif /* MSTATS */
542   }
543 }
544
545 char *
546 realloc (mem, n)
547      char *mem;
548      register unsigned int n;
549 {
550   register struct mhead *p;
551   register unsigned int tocopy;
552   register unsigned int nbytes;
553   register int nunits;
554
555   if ((p = (struct mhead *) mem) == 0)
556     return malloc (n);
557   p--;
558   nunits = p -> mh_index;
559   ASSERT (p -> mh_alloc == ISALLOC);
560 #ifdef rcheck
561   ASSERT (p -> mh_magic4 == MAGIC4);
562   {
563     register char *m = mem + (tocopy = p -> mh_nbytes);
564     ASSERT (*m++ == MAGIC1); ASSERT (*m++ == MAGIC1);
565     ASSERT (*m++ == MAGIC1); ASSERT (*m   == MAGIC1);
566   }
567 #else /* not rcheck */
568   if (p -> mh_index >= 13)
569     tocopy = (1 << (p -> mh_index + 3)) - sizeof *p;
570   else
571     tocopy = p -> mh_size;
572 #endif /* not rcheck */
573
574   /* See if desired size rounds to same power of 2 as actual size. */
575   nbytes = (n + sizeof *p + EXTRA + 7) & ~7;
576
577   /* If ok, use the same block, just marking its size as changed.  */
578   if (nbytes > (4 << nunits) && nbytes <= (8 << nunits))
579     {
580 #ifdef rcheck
581       register char *m = mem + tocopy;
582       *m++ = 0;  *m++ = 0;  *m++ = 0;  *m++ = 0;
583       p-> mh_nbytes = n;
584       m = mem + n;
585       *m++ = MAGIC1;  *m++ = MAGIC1;  *m++ = MAGIC1;  *m++ = MAGIC1;
586 #else /* not rcheck */
587       p -> mh_size = n;
588 #endif /* not rcheck */
589       return mem;
590     }
591
592   if (n < tocopy)
593     tocopy = n;
594   {
595     register char *new;
596
597     if ((new = malloc (n)) == 0)
598       return 0;
599     bcopy (mem, new, tocopy);
600     free (mem);
601     return new;
602   }
603 }
604
605 char *
606 memalign (alignment, size)
607      unsigned int alignment, size;
608 {
609   register char *ptr;
610   register char *aligned;
611   register struct mhead *p;
612
613   ptr = malloc (size + alignment);
614
615   if (ptr == 0)
616     return 0;
617   /* If entire block has the desired alignment, just accept it.  */
618   if (((int) ptr & (alignment - 1)) == 0)
619     return ptr;
620   /* Otherwise, get address of byte in the block that has that alignment.  */
621   aligned = (char *) (((int) ptr + alignment - 1) & -alignment);
622
623   /* Store a suitable indication of how to free the block,
624      so that free can find the true beginning of it.  */
625   p = (struct mhead *) aligned - 1;
626   p -> mh_size = aligned - ptr;
627   p -> mh_alloc = ISMEMALIGN;
628   return aligned;
629 }
630
631 #if !defined (HPUX)
632 /* This runs into trouble with getpagesize on HPUX, and Multimax machines.
633    Patching out seems cleaner than the ugly fix needed.  */
634 #if defined (__STDC__)
635 void *
636 #else
637 char *
638 #endif
639 valloc (size)
640      size_t size;
641 {
642   return memalign (getpagesize (), size);
643 }
644 #endif /* !HPUX */
645
646 #ifndef NO_CALLOC
647 char *
648 calloc (n, s)
649      size_t n, s;
650 {
651   size_t total;
652   char *result;
653
654   total = n * s;
655   result = malloc (total);
656   if (result)
657     zmemset (result, 0, total);
658   return result;  
659 }
660
661 void
662 cfree (p)
663      char *p;
664 {
665   free (p);
666 }
667 #endif /* !NO_CALLOC */
668
669 #ifdef MSTATS
670 /* Return statistics describing allocation of blocks of size 2**n. */
671
672 struct mstats_value
673   {
674     int blocksize;
675     int nfree;
676     int nused;
677   };
678
679 struct mstats_value
680 malloc_stats (size)
681      int size;
682 {
683   struct mstats_value v;
684   register int i;
685   register struct mhead *p;
686
687   v.nfree = 0;
688
689   if (size < 0 || size >= 30)
690     {
691       v.blocksize = 0;
692       v.nused = 0;
693       return v;
694     }
695
696   v.blocksize = 1 << (size + 3);
697   v.nused = nmalloc[size];
698
699   for (p = nextf[size]; p; p = CHAIN (p))
700     v.nfree++;
701
702   return v;
703 }
704 #endif /* MSTATS */
705
706 /*
707  *      This function returns the total number of bytes that the process
708  *      will be allowed to allocate via the sbrk(2) system call.  On
709  *      BSD systems this is the total space allocatable to stack and
710  *      data.  On USG systems this is the data space only.
711  */
712
713 #if !defined (HAVE_RESOURCE)
714 extern long ulimit ();
715
716 static void
717 get_lim_data ()
718 {    
719   lim_data = ulimit (3, 0);
720   lim_data -= (long) data_space_start;
721 }
722
723 #else /* HAVE_RESOURCE */
724 static void
725 get_lim_data ()
726 {
727   struct rlimit XXrlimit;
728
729   getrlimit (RLIMIT_DATA, &XXrlimit);
730 #ifdef RLIM_INFINITY
731   lim_data = XXrlimit.rlim_cur & RLIM_INFINITY; /* soft limit */
732 #else
733   lim_data = XXrlimit.rlim_cur; /* soft limit */
734 #endif
735 }
736
737 #endif /* HAVE_RESOURCE */