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