7 #if defined(PERL_CORE) && !defined(DEBUGGING_MSTATS)
8 # define DEBUGGING_MSTATS
12 # if defined(DEBUGGING) && !defined(NO_RCHECK)
16 * malloc.c (Caltech) 2/21/82
17 * Chris Kingsley, kingsley@cit-20.
19 * This is a very fast storage allocator. It allocates blocks of a small
20 * number of different sizes, and keeps free lists of each size. Blocks that
21 * don't exactly fit are passed up to the next larger size. In this
22 * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
23 * If PACK_MALLOC is defined, small blocks are 2^n bytes long.
24 * This is designed for use in a program that uses vast quantities of memory,
25 * but bombs when it runs out.
33 #define DEBUG_m(a) if (debug & 128) a
36 /* I don't much care whether these are defined in sys/types.h--LAW */
38 #define u_char unsigned char
39 #define u_int unsigned int
40 #define u_short unsigned short
42 /* 286 and atarist like big chunks, which gives too much overhead. */
43 #if (defined(RCHECK) || defined(I286) || defined(atarist)) && defined(PACK_MALLOC)
49 * The description below is applicable if PACK_MALLOC is not defined.
51 * The overhead on a block is at least 4 bytes. When free, this space
52 * contains a pointer to the next free block, and the bottom two bits must
53 * be zero. When in use, the first byte is set to MAGIC, and the second
54 * byte is the size index. The remaining bytes are for alignment.
55 * If range checking is enabled and the size of the block fits
56 * in two bytes, then the top two bytes hold the size of the requested block
57 * plus the range checking words, and the header word MINUS ONE.
60 union overhead *ov_next; /* when free */
61 #if MEM_ALIGNBYTES > 4
62 double strut; /* alignment problems */
65 u_char ovu_magic; /* magic number */
66 u_char ovu_index; /* bucket # */
68 u_short ovu_size; /* actual block size */
69 u_int ovu_rmagic; /* range magic number */
72 #define ov_magic ovu.ovu_magic
73 #define ov_index ovu.ovu_index
74 #define ov_size ovu.ovu_size
75 #define ov_rmagic ovu.ovu_rmagic
79 static void botch _((char *s));
81 static void morecore _((int bucket));
82 static int findbucket _((union overhead *freep, int srchlen));
84 #define MAGIC 0xff /* magic # on accounting info */
85 #define RMAGIC 0x55555555 /* magic # on range info */
87 # define RSLOP sizeof (u_int)
88 # ifdef TWO_POT_OPTIMIZE
89 # define MAX_SHORT_BUCKET 12
91 # define MAX_SHORT_BUCKET 13
99 * In this case it is assumed that if we do sbrk() in 2K units, we
100 * will get 2K aligned blocks. The bucket number of the given subblock is
101 * on the boundary of 2K block which contains the subblock.
102 * Several following bytes contain the magic numbers for the subblocks
105 * Sizes of chunks are powers of 2 for chunks in buckets <=
106 * MAX_PACKED, after this they are (2^n - sizeof(union overhead)) (to
107 * get alignment right).
109 * We suppose that starts of all the chunks in a 2K block are in
110 * different 2^n-byte-long chunks. If the top of the last chunk is
111 * aligned on a boundary of 2K block, this means that
112 * sizeof(union overhead)*"number of chunks" < 2^n, or
113 * sizeof(union overhead)*2K < 4^n, or n > 6 + log2(sizeof()/2)/2, if a
114 * chunk of size 2^n - overhead is used. Since this rules out n = 7
115 * for 8 byte alignment, we specialcase allocation of the first of 16
116 * 128-byte-long chunks.
118 * Note that with the above assumption we automatically have enough
119 * place for MAGIC at the start of 2K block. Note also that we
120 * overlay union overhead over the chunk, thus the start of the chunk
121 * is immediately overwritten after freeing.
123 # define MAX_PACKED 6
124 # define MAX_2_POT_ALGO ((1<<(MAX_PACKED + 1)) - M_OVERHEAD)
125 # define TWOK_MASK ((1<<11) - 1)
126 # define TWOK_MASKED(x) ((u_int)(x) & ~TWOK_MASK)
127 # define TWOK_SHIFT(x) ((u_int)(x) & TWOK_MASK)
128 # define OV_INDEXp(block) ((u_char*)(TWOK_MASKED(block)))
129 # define OV_INDEX(block) (*OV_INDEXp(block))
130 # define OV_MAGIC(block,bucket) (*(OV_INDEXp(block) + \
131 (TWOK_SHIFT(block)>>(bucket + 3)) + \
132 (bucket > MAX_NONSHIFT ? 1 : 0)))
133 # define CHUNK_SHIFT 0
135 static u_char n_blks[11 - 3] = {224, 120, 62, 31, 16, 8, 4, 2};
136 static u_short blk_shift[11 - 3] = {256, 128, 64, 32,
137 16*sizeof(union overhead),
138 8*sizeof(union overhead),
139 4*sizeof(union overhead),
140 2*sizeof(union overhead),
141 # define MAX_NONSHIFT 2 /* Shift 64 greater than chunk 32. */
144 #else /* !PACK_MALLOC */
146 # define OV_MAGIC(block,bucket) (block)->ov_magic
147 # define OV_INDEX(block) (block)->ov_index
148 # define CHUNK_SHIFT 1
149 #endif /* !PACK_MALLOC */
151 # define M_OVERHEAD (sizeof(union overhead) + RSLOP)
154 * Big allocations are often of the size 2^n bytes. To make them a
155 * little bit better, make blocks of size 2^n+pagesize for big n.
158 #ifdef TWO_POT_OPTIMIZE
160 # ifndef PERL_PAGESIZE
161 # define PERL_PAGESIZE 4096
163 # ifndef FIRST_BIG_TWO_POT
164 # define FIRST_BIG_TWO_POT 14 /* 16K */
166 # define FIRST_BIG_BLOCK (1<<FIRST_BIG_TWO_POT) /* 16K */
167 /* If this value or more, check against bigger blocks. */
168 # define FIRST_BIG_BOUND (FIRST_BIG_BLOCK - M_OVERHEAD)
169 /* If less than this value, goes into 2^n-overhead-block. */
170 # define LAST_SMALL_BOUND ((FIRST_BIG_BLOCK>>1) - M_OVERHEAD)
172 #endif /* TWO_POT_OPTIMIZE */
174 #if defined(PERL_EMERGENCY_SBRK) && defined(PERL_CORE)
177 # define BIG_SIZE (1<<16) /* 64K */
180 static char *emergency_buffer;
181 static MEM_SIZE emergency_buffer_size;
187 if (size >= BIG_SIZE) {
188 /* Give the possibility to recover: */
189 die("Out of memory during request for %i bytes", size);
190 /* croak may eat too much memory. */
193 if (!emergency_buffer) {
195 /* First offense, give a possibility to recover by dieing. */
196 /* No malloc involved here: */
197 GV **gvp = (GV**)hv_fetch(defstash, "^M", 2, 0);
201 if (!gvp) gvp = (GV**)hv_fetch(defstash, "\015", 1, 0);
202 if (!gvp || !(sv = GvSV(*gvp)) || !SvPOK(sv)
203 || (SvLEN(sv) < (1<<11) - M_OVERHEAD))
204 return (char *)-1; /* Now die die die... */
206 /* Got it, now detach SvPV: */
208 /* Check alignment: */
209 if (((u_int)(pv - M_OVERHEAD)) & ((1<<11) - 1)) {
210 PerlIO_puts(PerlIO_stderr(),"Bad alignment of $^M!\n");
211 return (char *)-1; /* die die die */
214 emergency_buffer = pv - M_OVERHEAD;
215 emergency_buffer_size = SvLEN(sv) + M_OVERHEAD;
218 die("Out of memory!"); /* croak may eat too much memory. */
220 else if (emergency_buffer_size >= size) {
221 emergency_buffer_size -= size;
222 return emergency_buffer + emergency_buffer_size;
225 return (char *)-1; /* poor guy... */
228 #else /* !(defined(TWO_POT_OPTIMIZE) && defined(PERL_CORE)) */
229 # define emergency_sbrk(size) -1
230 #endif /* !(defined(TWO_POT_OPTIMIZE) && defined(PERL_CORE)) */
233 * nextf[i] is the pointer to the next free block of size 2^(i+3). The
234 * smallest allocatable block is 8 bytes. The overhead information
235 * precedes the data area returned to the user.
238 static union overhead *nextf[NBUCKETS];
241 #define sbrk(a) Perl_sbrk(a)
242 char * Perl_sbrk _((int size));
244 #ifdef DONT_DECLARE_STD
249 extern char *sbrk(int);
253 #ifdef DEBUGGING_MSTATS
255 * nmalloc[i] is the difference between the number of mallocs and frees
256 * for a given block size.
258 static u_int nmalloc[NBUCKETS];
259 static u_int goodsbrk;
260 static u_int sbrk_slack;
261 static u_int start_slack;
265 #define ASSERT(p) if (!(p)) botch(STRINGIFY(p)); else
269 PerlIO_printf(PerlIO_stderr(), "assertion botched: %s\n", s);
277 malloc(register size_t nbytes)
279 register union overhead *p;
280 register int bucket = 0;
281 register MEM_SIZE shiftr;
283 #if defined(DEBUGGING) || defined(RCHECK)
284 MEM_SIZE size = nbytes;
289 if (nbytes > 0xffff) {
290 PerlIO_printf(PerlIO_stderr(),
291 "Allocation too large: %lx\n", (long)nbytes);
294 #endif /* HAS_64K_LIMIT */
296 if ((long)nbytes < 0)
297 croak("panic: malloc");
299 #endif /* PERL_CORE */
301 MUTEX_LOCK(&malloc_mutex);
303 * Convert amount of memory requested into
304 * closest block size stored in hash buckets
305 * which satisfies request. Account for
306 * space used per block for accounting.
311 else if (nbytes > MAX_2_POT_ALGO)
314 #ifdef TWO_POT_OPTIMIZE
315 if (nbytes >= FIRST_BIG_BOUND)
316 nbytes -= PERL_PAGESIZE;
318 nbytes += M_OVERHEAD;
319 nbytes = (nbytes + 3) &~ 3;
321 shiftr = (nbytes - 1) >> 2;
322 /* apart from this loop, this is O(1) */
326 * If nothing in hash bucket right now,
327 * request more memory from the system.
329 if (nextf[bucket] == NULL)
331 if ((p = (union overhead *)nextf[bucket]) == NULL) {
332 MUTEX_UNLOCK(&malloc_mutex);
335 PerlIO_puts(PerlIO_stderr(),"Out of memory!\n");
344 DEBUG_m(PerlIO_printf(Perl_debug_log, "0x%lx: (%05lu) malloc %ld bytes\n",
345 (unsigned long)(p+1),(unsigned long)(an++),(long)size));
346 #endif /* PERL_CORE */
348 /* remove from linked list */
350 if (*((int*)p) & (sizeof(union overhead) - 1))
351 PerlIO_printf(PerlIO_stderr(), "Corrupt malloc ptr 0x%lx at 0x%lx\n",
352 (unsigned long)*((int*)p),(unsigned long)p);
354 nextf[bucket] = p->ov_next;
355 OV_MAGIC(p, bucket) = MAGIC;
357 OV_INDEX(p) = bucket;
361 * Record allocated size of block and
362 * bound space with magic numbers.
364 nbytes = (size + M_OVERHEAD + 3) &~ 3;
365 if (nbytes <= 0x10000)
366 p->ov_size = nbytes - 1;
367 p->ov_rmagic = RMAGIC;
368 *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
370 MUTEX_UNLOCK(&malloc_mutex);
371 return ((Malloc_t)(p + CHUNK_SHIFT));
375 * Allocate more memory to the indicated bucket.
378 morecore(register int bucket)
380 register union overhead *ovp;
381 register int rnu; /* 2^rnu bytes will be requested */
382 register int nblks; /* become nblks blocks of the desired size */
383 register MEM_SIZE siz, needed;
388 if (bucket == (sizeof(MEM_SIZE)*8 - 3)) {
389 croak("Allocation too large");
392 * Insure memory is allocated
393 * on a page boundary. Should
394 * make getpageize call?
396 #ifndef atarist /* on the atari we dont have to worry about this */
397 ovp = (union overhead *)sbrk(0);
399 if ((UV)ovp & (0x7FF >> CHUNK_SHIFT)) {
400 slack = (0x800 >> CHUNK_SHIFT) - ((UV)ovp & (0x7FF >> CHUNK_SHIFT));
402 # if defined(DEBUGGING_MSTATS)
407 /* The sbrk(0) call on the I286 always returns the next segment */
411 #if !(defined(I286) || defined(atarist))
412 /* take 2k unless the block is bigger than that */
413 rnu = (bucket <= 8) ? 11 : bucket + 3;
415 /* take 16k unless the block is bigger than that
416 (80286s like large segments!), probably good on the atari too */
417 rnu = (bucket <= 11) ? 14 : bucket + 3;
419 nblks = 1 << (rnu - (bucket + 3)); /* how many blocks to get */
420 needed = (MEM_SIZE)1 << rnu;
421 #ifdef TWO_POT_OPTIMIZE
422 needed += (bucket >= (FIRST_BIG_TWO_POT - 3) ? PERL_PAGESIZE : 0);
424 ovp = (union overhead *)sbrk(needed);
426 if (ovp == (union overhead *)-1) {
427 ovp = (union overhead *)emergency_sbrk(needed);
428 if (ovp == (union overhead *)-1)
431 #ifdef DEBUGGING_MSTATS
435 * Round up to minimum allocation size boundary
436 * and deduct from block count to reflect.
441 croak("panic: Off-page sbrk");
444 ovp = (union overhead *)(((UV)ovp + 8) & ~7);
448 /* Again, this should always be ok on an 80286 */
451 * Add new memory allocated to that on
452 * free list for this hash bucket.
454 siz = 1 << (bucket + 3);
456 *(u_char*)ovp = bucket; /* Fill index. */
457 if (bucket <= MAX_PACKED - 3) {
458 ovp = (union overhead *) ((char*)ovp + blk_shift[bucket]);
459 nblks = n_blks[bucket];
460 # ifdef DEBUGGING_MSTATS
461 start_slack += blk_shift[bucket];
463 } else if (bucket <= 11 - 1 - 3) {
464 ovp = (union overhead *) ((char*)ovp + blk_shift[bucket]);
465 /* nblks = n_blks[bucket]; */
466 siz -= sizeof(union overhead);
467 } else ovp++; /* One chunk per block. */
468 #endif /* !PACK_MALLOC */
470 #ifdef DEBUGGING_MSTATS
471 nmalloc[bucket] += nblks;
473 while (--nblks > 0) {
474 ovp->ov_next = (union overhead *)((caddr_t)ovp + siz);
475 ovp = (union overhead *)((caddr_t)ovp + siz);
477 /* Not all sbrks return zeroed memory.*/
478 ovp->ov_next = (union overhead *)NULL;
480 if (bucket == 7 - 3) { /* Special case, explanation is above. */
481 union overhead *n_op = nextf[7 - 3]->ov_next;
482 nextf[7 - 3] = (union overhead *)((caddr_t)nextf[7 - 3]
483 - sizeof(union overhead));
484 nextf[7 - 3]->ov_next = n_op;
486 #endif /* !PACK_MALLOC */
492 register MEM_SIZE size;
493 register union overhead *ovp;
494 char *cp = (char*)mp;
500 DEBUG_m(PerlIO_printf(Perl_debug_log, "0x%lx: (%05lu) free\n",(unsigned long)cp,(unsigned long)(an++)));
501 #endif /* PERL_CORE */
505 ovp = (union overhead *)((caddr_t)cp
506 - sizeof (union overhead) * CHUNK_SHIFT);
508 bucket = OV_INDEX(ovp);
510 if (OV_MAGIC(ovp, bucket) != MAGIC) {
511 static int bad_free_warn = -1;
512 if (bad_free_warn == -1) {
513 char *pbf = getenv("PERL_BADFREE");
514 bad_free_warn = (pbf) ? atoi(pbf) : 1;
519 warn("%s free() ignored",
520 ovp->ov_rmagic == RMAGIC - 1 ? "Duplicate" : "Bad");
522 warn("Bad free() ignored");
526 MUTEX_LOCK(&malloc_mutex);
528 ASSERT(ovp->ov_rmagic == RMAGIC);
529 if (OV_INDEX(ovp) <= MAX_SHORT_BUCKET)
530 ASSERT(*(u_int *)((caddr_t)ovp + ovp->ov_size + 1 - RSLOP) == RMAGIC);
531 ovp->ov_rmagic = RMAGIC - 1;
533 ASSERT(OV_INDEX(ovp) < NBUCKETS);
534 size = OV_INDEX(ovp);
535 ovp->ov_next = nextf[size];
537 MUTEX_UNLOCK(&malloc_mutex);
541 * When a program attempts "storage compaction" as mentioned in the
542 * old malloc man page, it realloc's an already freed block. Usually
543 * this is the last block it freed; occasionally it might be farther
544 * back. We have to search all the free lists for the block in order
545 * to determine its bucket: 1st we make one pass thru the lists
546 * checking only the first block in each; if that fails we search
547 * ``reall_srchlen'' blocks in each list for a match (the variable
548 * is extern so the caller can modify it). If that fails we just copy
549 * however many bytes was given to realloc() and hope it's not huge.
551 int reall_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */
554 realloc(void *mp, size_t nbytes)
556 register MEM_SIZE onb;
561 char *cp = (char*)mp;
564 MEM_SIZE size = nbytes;
569 if (nbytes > 0xffff) {
570 PerlIO_printf(PerlIO_stderr(),
571 "Reallocation too large: %lx\n", size);
574 #endif /* HAS_64K_LIMIT */
576 return malloc(nbytes);
578 if ((long)nbytes < 0)
579 croak("panic: realloc");
581 #endif /* PERL_CORE */
583 MUTEX_LOCK(&malloc_mutex);
584 ovp = (union overhead *)((caddr_t)cp
585 - sizeof (union overhead) * CHUNK_SHIFT);
587 if (OV_MAGIC(ovp, i) == MAGIC) {
591 * Already free, doing "compaction".
593 * Search for the old block of memory on the
594 * free list. First, check the most common
595 * case (last element free'd), then (this failing)
596 * the last ``reall_srchlen'' items free'd.
597 * If all lookups fail, then assume the size of
598 * the memory block being realloc'd is the
601 if ((i = findbucket(ovp, 1)) < 0 &&
602 (i = findbucket(ovp, reall_srchlen)) < 0)
605 onb = (1L << (i + 3)) -
607 (i <= (MAX_PACKED - 3) ? 0 : M_OVERHEAD)
611 #ifdef TWO_POT_OPTIMIZE
612 + (i >= (FIRST_BIG_TWO_POT - 3) ? PERL_PAGESIZE : 0)
616 * avoid the copy if same size block.
617 * We are not agressive with boundary cases. Note that it is
618 * possible for small number of cases give false negative if
619 * both new size and old one are in the bucket for
620 * FIRST_BIG_TWO_POT, but the new one is near the lower end.
623 nbytes <= onb && (nbytes > ( (onb >> 1) - M_OVERHEAD )
624 #ifdef TWO_POT_OPTIMIZE
625 || (i == (FIRST_BIG_TWO_POT - 3)
626 && nbytes >= LAST_SMALL_BOUND )
631 * Record new allocated size of block and
632 * bound space with magic numbers.
634 if (OV_INDEX(ovp) <= MAX_SHORT_BUCKET) {
636 * Convert amount of memory requested into
637 * closest block size stored in hash buckets
638 * which satisfies request. Account for
639 * space used per block for accounting.
641 nbytes += M_OVERHEAD;
642 nbytes = (nbytes + 3) &~ 3;
643 ovp->ov_size = nbytes - 1;
644 *((u_int *)((caddr_t)ovp + nbytes - RSLOP)) = RMAGIC;
648 MUTEX_UNLOCK(&malloc_mutex);
651 MUTEX_UNLOCK(&malloc_mutex);
652 if ((res = (char*)malloc(nbytes)) == NULL)
654 if (cp != res) /* common optimization */
655 Copy(cp, res, (MEM_SIZE)(nbytes<onb?nbytes:onb), char);
663 PerlIO_printf(Perl_debug_log, "0x%lx: (%05lu) rfree\n",(unsigned long)res,(unsigned long)(an++));
664 PerlIO_printf(Perl_debug_log, "0x%lx: (%05lu) realloc %ld bytes\n",
665 (unsigned long)res,(unsigned long)(an++),(long)size);
668 #endif /* PERL_CORE */
669 return ((Malloc_t)res);
673 * Search ``srchlen'' elements of each free list for a block whose
674 * header starts at ``freep''. If srchlen is -1 search the whole list.
675 * Return bucket number, or -1 if not found.
678 findbucket(union overhead *freep, int srchlen)
680 register union overhead *p;
683 for (i = 0; i < NBUCKETS; i++) {
685 for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
695 calloc(register size_t elements, register size_t size)
697 long sz = elements * size;
698 Malloc_t p = malloc(sz);
701 memset((void*)p, 0, sz);
706 #ifdef DEBUGGING_MSTATS
708 * mstats - print out statistics about malloc
710 * Prints two lines of numbers, one showing the length of the free list
711 * for each size category, the second showing the number of mallocs -
712 * frees for each size category.
718 register union overhead *p;
719 int topbucket=0, totfree=0, total=0;
720 u_int nfree[NBUCKETS];
722 for (i=0; i < NBUCKETS; i++) {
723 for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
726 totfree += nfree[i] * (1 << (i + 3));
727 total += nmalloc[i] * (1 << (i + 3));
732 PerlIO_printf(PerlIO_stderr(), "Memory allocation statistics %s (buckets 8..%d)\n",
733 s, (1 << (topbucket + 3)) );
734 PerlIO_printf(PerlIO_stderr(), "%8d free:", totfree);
735 for (i=0; i <= topbucket; i++) {
736 PerlIO_printf(PerlIO_stderr(), (i<5 || i==7)?" %5d": (i<9)?" %3d":" %d", nfree[i]);
738 PerlIO_printf(PerlIO_stderr(), "\n%8d used:", total - totfree);
739 for (i=0; i <= topbucket; i++) {
740 PerlIO_printf(PerlIO_stderr(), (i<5 || i==7)?" %5d": (i<9)?" %3d":" %d", nmalloc[i] - nfree[i]);
742 PerlIO_printf(PerlIO_stderr(), "\nTotal sbrk(): %8d. Odd ends: sbrk(): %7d, malloc(): %7d bytes.\n",
743 goodsbrk + sbrk_slack, sbrk_slack, start_slack);
757 # define PERL_SBRK_VIA_MALLOC
760 # ifdef PERL_SBRK_VIA_MALLOC
761 # if defined(HIDEMYMALLOC) || defined(EMBEDMYMALLOC)
764 # include "Error: -DPERL_SBRK_VIA_MALLOC needs -D(HIDE|EMBED)MYMALLOC"
767 /* it may seem schizophrenic to use perl's malloc and let it call system */
768 /* malloc, the reason for that is only the 3.2 version of the OS that had */
769 /* frequent core dumps within nxzonefreenolock. This sbrk routine put an */
770 /* end to the cores */
772 # define SYSTEM_ALLOC(a) malloc(a)
774 # endif /* PERL_SBRK_VIA_MALLOC */
776 static IV Perl_sbrk_oldchunk;
777 static long Perl_sbrk_oldsize;
779 # define PERLSBRK_32_K (1<<15)
780 # define PERLSBRK_64_K (1<<16)
791 reqsize = size; /* just for the DEBUG_m statement */
794 size = (size + 0x7ff) & ~0x7ff;
796 if (size <= Perl_sbrk_oldsize) {
797 got = Perl_sbrk_oldchunk;
798 Perl_sbrk_oldchunk += size;
799 Perl_sbrk_oldsize -= size;
801 if (size >= PERLSBRK_32_K) {
807 size = PERLSBRK_64_K;
810 got = (IV)SYSTEM_ALLOC(size);
812 got = (got + 0x7ff) & ~0x7ff;
815 /* Chunk is small, register the rest for future allocs. */
816 Perl_sbrk_oldchunk = got + reqsize;
817 Perl_sbrk_oldsize = size - reqsize;
822 DEBUG_m(PerlIO_printf(Perl_debug_log, "sbrk malloc size %ld (reqsize %ld), left size %ld, give addr 0x%lx\n",
823 size, reqsize, Perl_sbrk_oldsize, got));
829 #endif /* ! defined USE_PERL_SBRK */