1 /* $RCSfile: malloc.c,v $$Revision: 4.0.1.3 $$Date: 91/11/05 17:57:40 $
4 * Revision 4.0.1.3 91/11/05 17:57:40 lwall
5 * patch11: safe malloc code now integrated into Perl's malloc when possible
7 * Revision 4.0.1.2 91/06/07 11:20:45 lwall
8 * patch4: many, many itty-bitty portability fixes
10 * Revision 4.0.1.1 91/04/11 17:48:31 lwall
11 * patch1: Configure now figures out malloc ptr type
13 * Revision 4.0 91/03/20 01:28:52 lwall
20 static char sccsid[] = "@(#)malloc.c 4.3 (Berkeley) 9/16/83";
26 * malloc.c (Caltech) 2/21/82
27 * Chris Kingsley, kingsley@cit-20.
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.
40 static findbucket(), morecore();
42 /* I don't much care whether these are defined in sys/types.h--LAW */
44 #define u_char unsigned char
45 #define u_int unsigned int
46 #define u_short unsigned short
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.
58 union overhead *ov_next; /* when free */
60 double strut; /* alignment problems */
63 u_char ovu_magic; /* magic number */
64 u_char ovu_index; /* bucket # */
66 u_short ovu_size; /* actual block size */
67 u_int ovu_rmagic; /* range magic number */
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
76 #define MAGIC 0xff /* magic # on accounting info */
77 #define OLDMAGIC 0x7f /* same after a free() */
78 #define RMAGIC 0x55555555 /* magic # on range info */
80 #define RSLOP sizeof (u_int)
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.
91 static union overhead *nextf[NBUCKETS];
96 * nmalloc[i] is the difference between the number of mallocs and frees
97 * for a given block size.
99 static u_int nmalloc[NBUCKETS];
104 #define ASSERT(p) if (!(p)) botch("p"); else
110 printf("assertion botched: %s\n", s);
123 register unsigned nbytes;
125 register union overhead *p;
126 register int bucket = 0;
127 register unsigned shiftr;
135 if (nbytes > 0xffff) {
136 fprintf(stderr, "Allocation too large: %lx\n", nbytes);
141 if ((long)nbytes < 0)
142 fatal("panic: malloc");
144 #endif /* safemalloc */
147 * Convert amount of memory requested into
148 * closest block size stored in hash buckets
149 * which satisfies request. Account for
150 * space used per block for accounting.
152 nbytes += sizeof (union overhead) + RSLOP;
153 nbytes = (nbytes + 3) &~ 3;
154 shiftr = (nbytes - 1) >> 2;
155 /* apart from this loop, this is O(1) */
159 * If nothing in hash bucket right now,
160 * request more memory from the system.
162 if (nextf[bucket] == NULL)
164 if ((p = (union overhead *)nextf[bucket]) == NULL) {
166 fputs("Out of memory!\n", stderr);
177 fprintf(stderr,"0x%x: (%05d) malloc %d bytes\n",p+1,an++,size);
180 fprintf(stderr,"0x%lx: (%05d) malloc %d bytes\n",p+1,an++,size);
183 #endif /* safemalloc */
185 /* remove from linked list */
187 if (*((int*)p) & (sizeof(union overhead) - 1))
189 fprintf(stderr,"Corrupt malloc ptr 0x%x at 0x%x\n",*((int*)p),p);
191 fprintf(stderr,"Corrupt malloc ptr 0x%lx at 0x%lx\n",*((int*)p),p);
194 nextf[bucket] = p->ov_next;
202 * Record allocated size of block and
203 * bound space with magic numbers.
205 if (nbytes <= 0x10000)
206 p->ov_size = nbytes - 1;
207 p->ov_rmagic = RMAGIC;
208 *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
210 return ((MALLOCPTRTYPE *)(p + 1));
214 * Allocate more memory to the indicated bucket.
220 register union overhead *op;
221 register int rnu; /* 2^rnu bytes will be requested */
222 register int nblks; /* become nblks blocks of the desired size */
228 * Insure memory is allocated
229 * on a page boundary. Should
230 * make getpageize call?
232 op = (union overhead *)sbrk(0);
235 (void)sbrk(1024 - ((int)op & 0x3ff));
237 /* The sbrk(0) call on the I286 always returns the next segment */
241 /* take 2k unless the block is bigger than that */
242 rnu = (bucket <= 8) ? 11 : bucket + 3;
244 /* take 16k unless the block is bigger than that
245 (80286s like large segments!) */
246 rnu = (bucket <= 11) ? 14 : bucket + 3;
248 nblks = 1 << (rnu - (bucket + 3)); /* how many blocks to get */
251 op = (union overhead *)sbrk(1 << rnu);
256 * Round up to minimum allocation size boundary
257 * and deduct from block count to reflect.
261 op = (union overhead *)(((int)op + 8) &~ 7);
265 /* Again, this should always be ok on an 80286 */
268 * Add new memory allocated to that on
269 * free list for this hash bucket.
272 siz = 1 << (bucket + 3);
273 while (--nblks > 0) {
274 op->ov_next = (union overhead *)((caddr_t)op + siz);
275 op = (union overhead *)((caddr_t)op + siz);
284 register union overhead *op;
285 char *cp = (char*)mp;
291 fprintf(stderr,"0x%x: (%05d) free\n",cp,an++);
294 fprintf(stderr,"0x%lx: (%05d) free\n",cp,an++);
297 #endif /* safemalloc */
301 op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
303 ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */
305 if (op->ov_magic != MAGIC) {
306 warn("%s free() ignored",
307 op->ov_magic == OLDMAGIC ? "Duplicate" : "Bad");
310 op->ov_magic = OLDMAGIC;
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);
317 ASSERT(op->ov_index < NBUCKETS);
319 op->ov_next = nextf[size];
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.
337 int reall_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */
349 char *cp = (char*)mp;
357 if (nbytes > 0xffff) {
358 fprintf(stderr, "Reallocation too large: %lx\n", size);
363 fatal("Null realloc");
365 if ((long)nbytes < 0)
366 fatal("panic: realloc");
368 #endif /* safemalloc */
371 return (malloc(nbytes));
372 op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
373 if (op->ov_magic == MAGIC) {
378 * Already free, doing "compaction".
380 * Search for the old block of memory on the
381 * free list. First, check the most common
382 * case (last element free'd), then (this failing)
383 * the last ``reall_srchlen'' items free'd.
384 * If all lookups fail, then assume the size of
385 * the memory block being realloc'd is the
388 if ((i = findbucket(op, 1)) < 0 &&
389 (i = findbucket(op, reall_srchlen)) < 0)
392 onb = (1 << (i + 3)) - sizeof (*op) - RSLOP;
393 /* avoid the copy if same size block */
395 nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP) {
398 * Record new allocated size of block and
399 * bound space with magic numbers.
401 if (op->ov_index <= 13) {
403 * Convert amount of memory requested into
404 * closest block size stored in hash buckets
405 * which satisfies request. Account for
406 * space used per block for accounting.
408 nbytes += sizeof (union overhead) + RSLOP;
409 nbytes = (nbytes + 3) &~ 3;
410 op->ov_size = nbytes - 1;
411 *((u_int *)((caddr_t)op + nbytes - RSLOP)) = RMAGIC;
417 if ((res = (char*)malloc(nbytes)) == NULL)
419 if (cp != res) /* common optimization */
420 bcopy(cp, res, (int)(nbytes < onb ? nbytes : onb));
429 fprintf(stderr,"0x%x: (%05d) rfree\n",res,an++);
430 fprintf(stderr,"0x%x: (%05d) realloc %d bytes\n",res,an++,size);
434 fprintf(stderr,"0x%lx: (%05d) rfree\n",res,an++);
435 fprintf(stderr,"0x%lx: (%05d) realloc %d bytes\n",res,an++,size);
439 #endif /* safemalloc */
440 return ((MALLOCPTRTYPE*)res);
444 * Search ``srchlen'' elements of each free list for a block whose
445 * header starts at ``freep''. If srchlen is -1 search the whole list.
446 * Return bucket number, or -1 if not found.
449 findbucket(freep, srchlen)
450 union overhead *freep;
453 register union overhead *p;
456 for (i = 0; i < NBUCKETS; i++) {
458 for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
469 * mstats - print out statistics about malloc
471 * Prints two lines of numbers, one showing the length of the free list
472 * for each size category, the second showing the number of mallocs -
473 * frees for each size category.
479 register union overhead *p;
483 fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
484 for (i = 0; i < NBUCKETS; i++) {
485 for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
487 fprintf(stderr, " %d", j);
488 totfree += j * (1 << (i + 3));
490 fprintf(stderr, "\nused:\t");
491 for (i = 0; i < NBUCKETS; i++) {
492 fprintf(stderr, " %d", nmalloc[i]);
493 totused += nmalloc[i] * (1 << (i + 3));
495 fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",