perl 5.0 alpha 3
[perl.git] / malloc.c
1 /* $RCSfile: malloc.c,v $$Revision: 4.1 $$Date: 92/08/07 18:24:25 $
2  *
3  * $Log:        malloc.c,v $
4  * Revision 4.1  92/08/07  18:24:25  lwall
5  * 
6  * Revision 4.0.1.4  92/06/08  14:28:38  lwall
7  * patch20: removed implicit int declarations on functions
8  * patch20: hash tables now split only if the memory is available to do so
9  * patch20: realloc(0, size) now does malloc in case library routines call it
10  * 
11  * Revision 4.0.1.3  91/11/05  17:57:40  lwall
12  * patch11: safe malloc code now integrated into Perl's malloc when possible
13  * 
14  * Revision 4.0.1.2  91/06/07  11:20:45  lwall
15  * patch4: many, many itty-bitty portability fixes
16  * 
17  * Revision 4.0.1.1  91/04/11  17:48:31  lwall
18  * patch1: Configure now figures out malloc ptr type
19  * 
20  * Revision 4.0  91/03/20  01:28:52  lwall
21  * 4.0 baseline.
22  * 
23  */
24
25 #ifndef lint
26 /*SUPPRESS 592*/
27 static char sccsid[] = "@(#)malloc.c    4.3 (Berkeley) 9/16/83";
28
29 #ifdef DEBUGGING
30 #define RCHECK
31 #endif
32 /*
33  * malloc.c (Caltech) 2/21/82
34  * Chris Kingsley, kingsley@cit-20.
35  *
36  * This is a very fast storage allocator.  It allocates blocks of a small 
37  * number of different sizes, and keeps free lists of each size.  Blocks that
38  * don't exactly fit are passed up to the next larger size.  In this 
39  * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
40  * This is designed for use in a program that uses vast quantities of memory,
41  * but bombs when it runs out. 
42  */
43
44 #include "EXTERN.h"
45 #include "perl.h"
46
47 static int findbucket();
48 static int morecore();
49
50 /* I don't much care whether these are defined in sys/types.h--LAW */
51
52 #define u_char unsigned char
53 #define u_int unsigned int
54 #define u_short unsigned short
55
56 /*
57  * The overhead on a block is at least 4 bytes.  When free, this space
58  * contains a pointer to the next free block, and the bottom two bits must
59  * be zero.  When in use, the first byte is set to MAGIC, and the second
60  * byte is the size index.  The remaining bytes are for alignment.
61  * If range checking is enabled and the size of the block fits
62  * in two bytes, then the top two bytes hold the size of the requested block
63  * plus the range checking words, and the header word MINUS ONE.
64  */
65 union   overhead {
66         union   overhead *ov_next;      /* when free */
67 #if ALIGNBYTES > 4
68         double  strut;                  /* alignment problems */
69 #endif
70         struct {
71                 u_char  ovu_magic;      /* magic number */
72                 u_char  ovu_index;      /* bucket # */
73 #ifdef RCHECK
74                 u_short ovu_size;       /* actual block size */
75                 u_int   ovu_rmagic;     /* range magic number */
76 #endif
77         } ovu;
78 #define ov_magic        ovu.ovu_magic
79 #define ov_index        ovu.ovu_index
80 #define ov_size         ovu.ovu_size
81 #define ov_rmagic       ovu.ovu_rmagic
82 };
83
84 #define MAGIC           0xff            /* magic # on accounting info */
85 #define OLDMAGIC        0x7f            /* same after a free() */
86 #define RMAGIC          0x55555555      /* magic # on range info */
87 #ifdef RCHECK
88 #define RSLOP           sizeof (u_int)
89 #else
90 #define RSLOP           0
91 #endif
92
93 /*
94  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
95  * smallest allocatable block is 8 bytes.  The overhead information
96  * precedes the data area returned to the user.
97  */
98 #define NBUCKETS 30
99 static  union overhead *nextf[NBUCKETS];
100 extern  char *sbrk();
101
102 #ifdef MSTATS
103 /*
104  * nmalloc[i] is the difference between the number of mallocs and frees
105  * for a given block size.
106  */
107 static  u_int nmalloc[NBUCKETS];
108 #include <stdio.h>
109 #endif
110
111 #ifdef debug
112 #define ASSERT(p)   if (!(p)) botch("p"); else
113 static void
114 botch(s)
115         char *s;
116 {
117
118         printf("assertion botched: %s\n", s);
119         abort();
120 }
121 #else
122 #define ASSERT(p)
123 #endif
124
125 MALLOCPTRTYPE *
126 malloc(nbytes)
127         register MEM_SIZE nbytes;
128 {
129         register union overhead *p;
130         register int bucket = 0;
131         register MEM_SIZE shiftr;
132
133 #ifdef safemalloc
134 #ifdef DEBUGGING
135         MEM_SIZE size = nbytes;
136 #endif
137
138 #ifdef MSDOS
139         if (nbytes > 0xffff) {
140                 fprintf(stderr, "Allocation too large: %lx\n", (long)nbytes);
141                 my_exit(1);
142         }
143 #endif /* MSDOS */
144 #ifdef DEBUGGING
145         if ((long)nbytes < 0)
146             fatal("panic: malloc");
147 #endif
148 #endif /* safemalloc */
149
150         /*
151          * Convert amount of memory requested into
152          * closest block size stored in hash buckets
153          * which satisfies request.  Account for
154          * space used per block for accounting.
155          */
156         nbytes += sizeof (union overhead) + RSLOP;
157         nbytes = (nbytes + 3) &~ 3; 
158         shiftr = (nbytes - 1) >> 2;
159         /* apart from this loop, this is O(1) */
160         while (shiftr >>= 1)
161                 bucket++;
162         /*
163          * If nothing in hash bucket right now,
164          * request more memory from the system.
165          */
166         if (nextf[bucket] == NULL)    
167                 morecore(bucket);
168         if ((p = (union overhead *)nextf[bucket]) == NULL) {
169 #ifdef safemalloc
170                 if (!nomemok) {
171                     fputs("Out of memory!\n", stderr);
172                     my_exit(1);
173                 }
174 #else
175                 return (NULL);
176 #endif
177         }
178
179 #ifdef safemalloc
180 #if !(defined(I286) || defined(atarist))
181     DEBUG_m(fprintf(stderr,"0x%x: (%05d) malloc %ld bytes\n",p+1,an++,(long)size));
182 #else
183     DEBUG_m(fprintf(stderr,"0x%lx: (%05d) malloc %ld bytes\n",p+1,an++,(long)size));
184 #endif
185 #endif /* safemalloc */
186
187         /* remove from linked list */
188 #ifdef RCHECK
189         if (*((int*)p) & (sizeof(union overhead) - 1))
190 #if !(defined(I286) || defined(atarist))
191             fprintf(stderr,"Corrupt malloc ptr 0x%x at 0x%x\n",*((int*)p),p);
192 #else
193             fprintf(stderr,"Corrupt malloc ptr 0x%lx at 0x%lx\n",*((int*)p),p);
194 #endif
195 #endif
196         nextf[bucket] = p->ov_next;
197         p->ov_magic = MAGIC;
198         p->ov_index= bucket;
199 #ifdef MSTATS
200         nmalloc[bucket]++;
201 #endif
202 #ifdef RCHECK
203         /*
204          * Record allocated size of block and
205          * bound space with magic numbers.
206          */
207         if (nbytes <= 0x10000)
208                 p->ov_size = nbytes - 1;
209         p->ov_rmagic = RMAGIC;
210         *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
211 #endif
212         return ((MALLOCPTRTYPE *)(p + 1));
213 }
214
215 /*
216  * Allocate more memory to the indicated bucket.
217  */
218 static
219 morecore(bucket)
220         register int bucket;
221 {
222         register union overhead *op;
223         register int rnu;       /* 2^rnu bytes will be requested */
224         register int nblks;     /* become nblks blocks of the desired size */
225         register MEM_SIZE siz;
226
227         if (nextf[bucket])
228                 return;
229         /*
230          * Insure memory is allocated
231          * on a page boundary.  Should
232          * make getpageize call?
233          */
234 #ifndef atarist /* on the atari we dont have to worry about this */
235         op = (union overhead *)sbrk(0);
236 #ifndef I286
237         if ((int)op & 0x3ff)
238                 (void)sbrk(1024 - ((int)op & 0x3ff));
239 #else
240         /* The sbrk(0) call on the I286 always returns the next segment */
241 #endif
242 #endif /* atarist */
243
244 #if !(defined(I286) || defined(atarist))
245         /* take 2k unless the block is bigger than that */
246         rnu = (bucket <= 8) ? 11 : bucket + 3;
247 #else
248         /* take 16k unless the block is bigger than that 
249            (80286s like large segments!), probably good on the atari too */
250         rnu = (bucket <= 11) ? 14 : bucket + 3;
251 #endif
252         nblks = 1 << (rnu - (bucket + 3));  /* how many blocks to get */
253         if (rnu < bucket)
254                 rnu = bucket;
255         op = (union overhead *)sbrk(1L << rnu);
256         /* no more room! */
257         if ((int)op == -1)
258                 return;
259         /*
260          * Round up to minimum allocation size boundary
261          * and deduct from block count to reflect.
262          */
263 #ifndef I286
264         if ((int)op & 7) {
265                 op = (union overhead *)(((MEM_SIZE)op + 8) &~ 7);
266                 nblks--;
267         }
268 #else
269         /* Again, this should always be ok on an 80286 */
270 #endif
271         /*
272          * Add new memory allocated to that on
273          * free list for this hash bucket.
274          */
275         nextf[bucket] = op;
276         siz = 1 << (bucket + 3);
277         while (--nblks > 0) {
278                 op->ov_next = (union overhead *)((caddr_t)op + siz);
279                 op = (union overhead *)((caddr_t)op + siz);
280         }
281 }
282
283 void
284 free(mp)
285         MALLOCPTRTYPE *mp;
286 {   
287         register MEM_SIZE size;
288         register union overhead *op;
289         char *cp = (char*)mp;
290
291 #ifdef safemalloc
292 #if !(defined(I286) || defined(atarist))
293         DEBUG_m(fprintf(stderr,"0x%x: (%05d) free\n",cp,an++));
294 #else
295         DEBUG_m(fprintf(stderr,"0x%lx: (%05d) free\n",cp,an++));
296 #endif
297 #endif /* safemalloc */
298
299         if (cp == NULL)
300                 return;
301         op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
302 #ifdef debug
303         ASSERT(op->ov_magic == MAGIC);          /* make sure it was in use */
304 #else
305         if (op->ov_magic != MAGIC) {
306                 warn("%s free() ignored",
307                     op->ov_magic == OLDMAGIC ? "Duplicate" : "Bad");
308                 return;                         /* sanity */
309         }
310         op->ov_magic = OLDMAGIC;
311 #endif
312 #ifdef RCHECK
313         ASSERT(op->ov_rmagic == RMAGIC);
314         if (op->ov_index <= 13)
315                 ASSERT(*(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC);
316 #endif
317         ASSERT(op->ov_index < NBUCKETS);
318         size = op->ov_index;
319         op->ov_next = nextf[size];
320         nextf[size] = op;
321 #ifdef MSTATS
322         nmalloc[size]--;
323 #endif
324 }
325
326 /*
327  * When a program attempts "storage compaction" as mentioned in the
328  * old malloc man page, it realloc's an already freed block.  Usually
329  * this is the last block it freed; occasionally it might be farther
330  * back.  We have to search all the free lists for the block in order
331  * to determine its bucket: 1st we make one pass thru the lists
332  * checking only the first block in each; if that fails we search
333  * ``reall_srchlen'' blocks in each list for a match (the variable
334  * is extern so the caller can modify it).  If that fails we just copy
335  * however many bytes was given to realloc() and hope it's not huge.
336  */
337 int reall_srchlen = 4;  /* 4 should be plenty, -1 =>'s whole list */
338
339 MALLOCPTRTYPE *
340 realloc(mp, nbytes)
341         MALLOCPTRTYPE *mp; 
342         MEM_SIZE nbytes;
343 {   
344         register MEM_SIZE onb;
345         union overhead *op;
346         char *res;
347         register int i;
348         int was_alloced = 0;
349         char *cp = (char*)mp;
350
351 #ifdef safemalloc
352 #ifdef DEBUGGING
353         MEM_SIZE size = nbytes;
354 #endif
355
356 #ifdef MSDOS
357         if (nbytes > 0xffff) {
358                 fprintf(stderr, "Reallocation too large: %lx\n", size);
359                 my_exit(1);
360         }
361 #endif /* MSDOS */
362         if (!cp)
363                 return malloc(nbytes);
364 #ifdef DEBUGGING
365         if ((long)nbytes < 0)
366                 fatal("panic: realloc");
367 #endif
368 #endif /* safemalloc */
369
370         op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
371         if (op->ov_magic == MAGIC) {
372                 was_alloced++;
373                 i = op->ov_index;
374         } else {
375                 /*
376                  * Already free, doing "compaction".
377                  *
378                  * Search for the old block of memory on the
379                  * free list.  First, check the most common
380                  * case (last element free'd), then (this failing)
381                  * the last ``reall_srchlen'' items free'd.
382                  * If all lookups fail, then assume the size of
383                  * the memory block being realloc'd is the
384                  * smallest possible.
385                  */
386                 if ((i = findbucket(op, 1)) < 0 &&
387                     (i = findbucket(op, reall_srchlen)) < 0)
388                         i = 0;
389         }
390         onb = (1L << (i + 3)) - sizeof (*op) - RSLOP;
391         /* avoid the copy if same size block */
392         if (was_alloced &&
393             nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP) {
394 #ifdef RCHECK
395                 /*
396                  * Record new allocated size of block and
397                  * bound space with magic numbers.
398                  */
399                 if (op->ov_index <= 13) {
400                         /*
401                          * Convert amount of memory requested into
402                          * closest block size stored in hash buckets
403                          * which satisfies request.  Account for
404                          * space used per block for accounting.
405                          */
406                         nbytes += sizeof (union overhead) + RSLOP;
407                         nbytes = (nbytes + 3) &~ 3; 
408                         op->ov_size = nbytes - 1;
409                         *((u_int *)((caddr_t)op + nbytes - RSLOP)) = RMAGIC;
410                 }
411 #endif
412                 res = cp;
413         }
414         else {
415                 if ((res = (char*)malloc(nbytes)) == NULL)
416                         return (NULL);
417                 if (cp != res)                  /* common optimization */
418                         Copy(cp, res, (MEM_SIZE)(nbytes<onb?nbytes:onb), char);
419                 if (was_alloced)
420                         free(cp);
421         }
422
423 #ifdef safemalloc
424 #ifdef DEBUGGING
425 #  if !(defined(I286) || defined(atarist))
426         if (debug & 128) {
427             fprintf(stderr,"0x%x: (%05d) rfree\n",res,an++);
428             fprintf(stderr,"0x%x: (%05d) realloc %ld bytes\n",res,an++,(long)size);
429         }
430 #  else
431         if (debug & 128) {
432             fprintf(stderr,"0x%lx: (%05d) rfree\n",res,an++);
433             fprintf(stderr,"0x%lx: (%05d) realloc %ld bytes\n",res,an++,(long)size);
434         }
435 #  endif
436 #endif
437 #endif /* safemalloc */
438         return ((MALLOCPTRTYPE*)res);
439 }
440
441 /*
442  * Search ``srchlen'' elements of each free list for a block whose
443  * header starts at ``freep''.  If srchlen is -1 search the whole list.
444  * Return bucket number, or -1 if not found.
445  */
446 static int
447 findbucket(freep, srchlen)
448         union overhead *freep;
449         int srchlen;
450 {
451         register union overhead *p;
452         register int i, j;
453
454         for (i = 0; i < NBUCKETS; i++) {
455                 j = 0;
456                 for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
457                         if (p == freep)
458                                 return (i);
459                         j++;
460                 }
461         }
462         return (-1);
463 }
464
465 #ifdef MSTATS
466 /*
467  * mstats - print out statistics about malloc
468  * 
469  * Prints two lines of numbers, one showing the length of the free list
470  * for each size category, the second showing the number of mallocs -
471  * frees for each size category.
472  */
473 void
474 mstats(s)
475         char *s;
476 {
477         register int i, j;
478         register union overhead *p;
479         int totfree = 0,
480         totused = 0;
481
482         fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
483         for (i = 0; i < NBUCKETS; i++) {
484                 for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
485                         ;
486                 fprintf(stderr, " %d", j);
487                 totfree += j * (1 << (i + 3));
488         }
489         fprintf(stderr, "\nused:\t");
490         for (i = 0; i < NBUCKETS; i++) {
491                 fprintf(stderr, " %d", nmalloc[i]);
492                 totused += nmalloc[i] * (1 << (i + 3));
493         }
494         fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
495             totused, totfree);
496 }
497 #endif
498 #endif /* lint */