X-Git-Url: http://git.shadowcat.co.uk/gitweb/gitweb.cgi?a=blobdiff_plain;f=malloc.c;h=680b73454b01cf3fb324abebe8ee3b24852cc139;hb=ff3fa5b4f584a0f54292ef4f8308411acc3b2539;hp=2a8b5516a16e66ef6d5df33b1baeb9efb324d57f;hpb=45d8adaa83210dbf286f70ae01d99f534e6c8052;p=p5sagit%2Fp5-mst-13.2.git diff --git a/malloc.c b/malloc.c index 2a8b551..680b734 100644 --- a/malloc.c +++ b/malloc.c @@ -1,24 +1,8 @@ -/* $RCSfile: malloc.c,v $$Revision: 4.0.1.3 $$Date: 91/11/05 17:57:40 $ +/* malloc.c * - * $Log: malloc.c,v $ - * Revision 4.0.1.3 91/11/05 17:57:40 lwall - * patch11: safe malloc code now integrated into Perl's malloc when possible - * - * Revision 4.0.1.2 91/06/07 11:20:45 lwall - * patch4: many, many itty-bitty portability fixes - * - * Revision 4.0.1.1 91/04/11 17:48:31 lwall - * patch1: Configure now figures out malloc ptr type - * - * Revision 4.0 91/03/20 01:28:52 lwall - * 4.0 baseline. - * */ #ifndef lint -/*SUPPRESS 592*/ -static char sccsid[] = "@(#)malloc.c 4.3 (Berkeley) 9/16/83"; - #ifdef DEBUGGING #define RCHECK #endif @@ -30,6 +14,7 @@ static char sccsid[] = "@(#)malloc.c 4.3 (Berkeley) 9/16/83"; * number of different sizes, and keeps free lists of each size. Blocks that * don't exactly fit are passed up to the next larger size. In this * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long. + * If PACK_MALLOC is defined, small blocks are 2^n bytes long. * This is designed for use in a program that uses vast quantities of memory, * but bombs when it runs out. */ @@ -37,7 +22,10 @@ static char sccsid[] = "@(#)malloc.c 4.3 (Berkeley) 9/16/83"; #include "EXTERN.h" #include "perl.h" -static findbucket(), morecore(); +#ifdef DEBUGGING +#undef DEBUG_m +#define DEBUG_m(a) if (debug & 128) a +#endif /* I don't much care whether these are defined in sys/types.h--LAW */ @@ -45,7 +33,15 @@ static findbucket(), morecore(); #define u_int unsigned int #define u_short unsigned short +/* 286 and atarist like big chunks, which gives too much overhead. */ +#if (defined(RCHECK) || defined(I286) || defined(atarist)) && defined(PACK_MALLOC) +#undef PACK_MALLOC +#endif + + /* + * The description below is applicable if PACK_MALLOC is not defined. + * * The overhead on a block is at least 4 bytes. When free, this space * contains a pointer to the next free block, and the bottom two bits must * be zero. When in use, the first byte is set to MAGIC, and the second @@ -56,7 +52,7 @@ static findbucket(), morecore(); */ union overhead { union overhead *ov_next; /* when free */ -#if ALIGNBYTES > 4 +#if MEM_ALIGNBYTES > 4 double strut; /* alignment problems */ #endif struct { @@ -73,8 +69,13 @@ union overhead { #define ov_rmagic ovu.ovu_rmagic }; +#ifdef DEBUGGING +static void botch _((char *s)); +#endif +static void morecore _((int bucket)); +static int findbucket _((union overhead *freep, int srchlen)); + #define MAGIC 0xff /* magic # on accounting info */ -#define OLDMAGIC 0x7f /* same after a free() */ #define RMAGIC 0x55555555 /* magic # on range info */ #ifdef RCHECK #define RSLOP sizeof (u_int) @@ -82,6 +83,67 @@ union overhead { #define RSLOP 0 #endif +#ifdef PACK_MALLOC +/* + * In this case it is assumed that if we do sbrk() in 2K units, we + * will get 2K aligned blocks. The bucket number of the given subblock is + * on the boundary of 2K block which contains the subblock. + * Several following bytes contain the magic numbers for the subblocks + * in the block. + * + * Sizes of chunks are powers of 2 for chunks in buckets <= + * MAX_PACKED, after this they are (2^n - sizeof(union overhead)) (to + * get alignment right). + * + * We suppose that starts of all the chunks in a 2K block are in + * different 2^n-byte-long chunks. If the top of the last chunk is + * aligned on a boundary of 2K block, this means that + * sizeof(union overhead)*"number of chunks" < 2^n, or + * sizeof(union overhead)*2K < 4^n, or n > 6 + log2(sizeof()/2)/2, if a + * chunk of size 2^n - overhead is used. Since this rules out n = 7 + * for 8 byte alignment, we specialcase allocation of the first of 16 + * 128-byte-long chunks. + * + * Note that with the above assumption we automatically have enough + * place for MAGIC at the start of 2K block. Note also that we + * overlay union overhead over the chunk, thus the start of the chunk + * is immediately overwritten after freeing. + */ +# define MAX_PACKED 6 +# define MAX_2_POT_ALGO ((1<<(MAX_PACKED + 1)) - M_OVERHEAD) +# define TWOK_MASK ((1<<11) - 1) +# define TWOK_MASKED(x) ((int)x & ~TWOK_MASK) +# define TWOK_SHIFT(x) ((int)x & TWOK_MASK) +# define OV_INDEXp(block) ((u_char*)(TWOK_MASKED(block))) +# define OV_INDEX(block) (*OV_INDEXp(block)) +# define OV_MAGIC(block,bucket) (*(OV_INDEXp(block) + \ + (TWOK_SHIFT(block)>>(bucket + 3)) + \ + (bucket > MAX_NONSHIFT ? 1 : 0))) +# define CHUNK_SHIFT 0 + +static u_char n_blks[11 - 3] = {224, 120, 62, 31, 16, 8, 4, 2}; +static u_short blk_shift[11 - 3] = {256, 128, 64, 32, + 16*sizeof(union overhead), + 8*sizeof(union overhead), + 4*sizeof(union overhead), + 2*sizeof(union overhead), +# define MAX_NONSHIFT 2 /* Shift 64 greater than chunk 32. */ +}; + +# ifdef DEBUGGING_MSTATS +static u_int sbrk_slack; +static u_int start_slack; +# endif + +#else /* !PACK_MALLOC */ + +# define OV_MAGIC(block,bucket) (block)->ov_magic +# define OV_INDEX(block) (block)->ov_index +# define CHUNK_SHIFT 1 +#endif /* !PACK_MALLOC */ + +# define M_OVERHEAD (sizeof(union overhead) + RSLOP) + /* * nextf[i] is the pointer to the next free block of size 2^(i+3). The * smallest allocatable block is 8 bytes. The overhead information @@ -89,57 +151,57 @@ union overhead { */ #define NBUCKETS 30 static union overhead *nextf[NBUCKETS]; + +#ifdef USE_PERL_SBRK +#define sbrk(a) Perl_sbrk(a) +char * Perl_sbrk _((int size)); +#else extern char *sbrk(); +#endif -#ifdef MSTATS +#ifdef DEBUGGING_MSTATS /* * nmalloc[i] is the difference between the number of mallocs and frees * for a given block size. */ static u_int nmalloc[NBUCKETS]; -#include #endif -#ifdef debug -#define ASSERT(p) if (!(p)) botch("p"); else -static +#ifdef DEBUGGING +#define ASSERT(p) if (!(p)) botch(STRINGIFY(p)); else +static void botch(s) char *s; { - - printf("assertion botched: %s\n", s); + PerlIO_printf(PerlIO_stderr(), "assertion botched: %s\n", s); abort(); } #else #define ASSERT(p) #endif -#ifdef safemalloc -static int an = 0; -#endif - -MALLOCPTRTYPE * +Malloc_t malloc(nbytes) - register unsigned nbytes; + register MEM_SIZE nbytes; { register union overhead *p; register int bucket = 0; - register unsigned shiftr; + register MEM_SIZE shiftr; #ifdef safemalloc #ifdef DEBUGGING - int size = nbytes; + MEM_SIZE size = nbytes; #endif #ifdef MSDOS if (nbytes > 0xffff) { - fprintf(stderr, "Allocation too large: %lx\n", nbytes); - exit(1); + PerlIO_printf(PerlIO_stderr(), "Allocation too large: %lx\n", (long)nbytes); + my_exit(1); } #endif /* MSDOS */ #ifdef DEBUGGING if ((long)nbytes < 0) - fatal("panic: malloc"); + croak("panic: malloc"); #endif #endif /* safemalloc */ @@ -149,8 +211,16 @@ malloc(nbytes) * which satisfies request. Account for * space used per block for accounting. */ - nbytes += sizeof (union overhead) + RSLOP; - nbytes = (nbytes + 3) &~ 3; +#ifdef PACK_MALLOC + if (nbytes > MAX_2_POT_ALGO) { +#endif + nbytes += M_OVERHEAD; + nbytes = (nbytes + 3) &~ 3; +#ifdef PACK_MALLOC + } else if (nbytes == 0) { + nbytes = 1; + } +#endif shiftr = (nbytes - 1) >> 2; /* apart from this loop, this is O(1) */ while (shiftr >>= 1) @@ -163,38 +233,32 @@ malloc(nbytes) morecore(bucket); if ((p = (union overhead *)nextf[bucket]) == NULL) { #ifdef safemalloc - fputs("Out of memory!\n", stderr); - exit(1); + if (!nomemok) { + PerlIO_puts(PerlIO_stderr(),"Out of memory!\n"); + my_exit(1); + } #else return (NULL); #endif } #ifdef safemalloc -#ifdef DEBUGGING -# ifndef I286 - if (debug & 128) - fprintf(stderr,"0x%x: (%05d) malloc %d bytes\n",p+1,an++,size); -# else - if (debug & 128) - fprintf(stderr,"0x%lx: (%05d) malloc %d bytes\n",p+1,an++,size); -# endif -#endif + DEBUG_m(PerlIO_printf(Perl_debug_log, "0x%lx: (%05d) malloc %ld bytes\n", + (unsigned long)(p+1),an++,(long)size)); #endif /* safemalloc */ /* remove from linked list */ #ifdef RCHECK if (*((int*)p) & (sizeof(union overhead) - 1)) -#ifndef I286 - fprintf(stderr,"Corrupt malloc ptr 0x%x at 0x%x\n",*((int*)p),p); -#else - fprintf(stderr,"Corrupt malloc ptr 0x%lx at 0x%lx\n",*((int*)p),p); -#endif + PerlIO_printf(PerlIO_stderr(), "Corrupt malloc ptr 0x%lx at 0x%lx\n", + (unsigned long)*((int*)p),(unsigned long)p); #endif nextf[bucket] = p->ov_next; - p->ov_magic = MAGIC; - p->ov_index= bucket; -#ifdef MSTATS + OV_MAGIC(p, bucket) = MAGIC; +#ifndef PACK_MALLOC + OV_INDEX(p) = bucket; +#endif +#ifdef DEBUGGING_MSTATS nmalloc[bucket]++; #endif #ifdef RCHECK @@ -207,20 +271,21 @@ malloc(nbytes) p->ov_rmagic = RMAGIC; *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC; #endif - return ((MALLOCPTRTYPE *)(p + 1)); + return ((Malloc_t)(p + CHUNK_SHIFT)); } /* * Allocate more memory to the indicated bucket. */ -static +static void morecore(bucket) register int bucket; { register union overhead *op; register int rnu; /* 2^rnu bytes will be requested */ register int nblks; /* become nblks blocks of the desired size */ - register int siz; + register MEM_SIZE siz; + int slack = 0; if (nextf[bucket]) return; @@ -229,26 +294,36 @@ morecore(bucket) * on a page boundary. Should * make getpageize call? */ +#ifndef atarist /* on the atari we dont have to worry about this */ op = (union overhead *)sbrk(0); -#ifndef I286 +# ifndef I286 +# ifdef PACK_MALLOC + if ((int)op & 0x7ff) + (void)sbrk(slack = 2048 - ((int)op & 0x7ff)); +# else if ((int)op & 0x3ff) - (void)sbrk(1024 - ((int)op & 0x3ff)); -#else + (void)sbrk(slack = 1024 - ((int)op & 0x3ff)); +# endif +# if defined(DEBUGGING_MSTATS) && defined(PACK_MALLOC) + sbrk_slack += slack; +# endif +# else /* The sbrk(0) call on the I286 always returns the next segment */ -#endif +# endif +#endif /* atarist */ -#ifndef I286 +#if !(defined(I286) || defined(atarist)) /* take 2k unless the block is bigger than that */ rnu = (bucket <= 8) ? 11 : bucket + 3; #else /* take 16k unless the block is bigger than that - (80286s like large segments!) */ + (80286s like large segments!), probably good on the atari too */ rnu = (bucket <= 11) ? 14 : bucket + 3; #endif nblks = 1 << (rnu - (bucket + 3)); /* how many blocks to get */ - if (rnu < bucket) - rnu = bucket; - op = (union overhead *)sbrk(1 << rnu); + /* if (rnu < bucket) + rnu = bucket; Why anyone needs this? */ + op = (union overhead *)sbrk(1L << rnu); /* no more room! */ if ((int)op == -1) return; @@ -257,8 +332,12 @@ morecore(bucket) * and deduct from block count to reflect. */ #ifndef I286 +# ifdef PACK_MALLOC + if ((int)op & 0x7ff) + croak("panic: Off-page sbrk"); +# endif if ((int)op & 7) { - op = (union overhead *)(((int)op + 8) &~ 7); + op = (union overhead *)(((MEM_SIZE)op + 8) &~ 7); nblks--; } #else @@ -268,57 +347,91 @@ morecore(bucket) * Add new memory allocated to that on * free list for this hash bucket. */ - nextf[bucket] = op; siz = 1 << (bucket + 3); +#ifdef PACK_MALLOC + *(u_char*)op = bucket; /* Fill index. */ + if (bucket <= MAX_PACKED - 3) { + op = (union overhead *) ((char*)op + blk_shift[bucket]); + nblks = n_blks[bucket]; +# ifdef DEBUGGING_MSTATS + start_slack += blk_shift[bucket]; +# endif + } else if (bucket <= 11 - 1 - 3) { + op = (union overhead *) ((char*)op + blk_shift[bucket]); + /* nblks = n_blks[bucket]; */ + siz -= sizeof(union overhead); + } else op++; /* One chunk per block. */ +#endif /* !PACK_MALLOC */ + nextf[bucket] = op; while (--nblks > 0) { op->ov_next = (union overhead *)((caddr_t)op + siz); op = (union overhead *)((caddr_t)op + siz); } + /* Not all sbrks return zeroed memory.*/ + op->ov_next = (union overhead *)NULL; +#ifdef PACK_MALLOC + if (bucket == 7 - 3) { /* Special case, explanation is above. */ + union overhead *n_op = nextf[7 - 3]->ov_next; + nextf[7 - 3] = (union overhead *)((caddr_t)nextf[7 - 3] + - sizeof(union overhead)); + nextf[7 - 3]->ov_next = n_op; + } +#endif /* !PACK_MALLOC */ } -void +Free_t free(mp) - MALLOCPTRTYPE *mp; + Malloc_t mp; { - register int size; + register MEM_SIZE size; register union overhead *op; char *cp = (char*)mp; +#ifdef PACK_MALLOC + u_char bucket; +#endif #ifdef safemalloc -#ifdef DEBUGGING -# ifndef I286 - if (debug & 128) - fprintf(stderr,"0x%x: (%05d) free\n",cp,an++); -# else - if (debug & 128) - fprintf(stderr,"0x%lx: (%05d) free\n",cp,an++); -# endif -#endif + DEBUG_m(PerlIO_printf(Perl_debug_log, "0x%lx: (%05d) free\n",(unsigned long)cp,an++)); #endif /* safemalloc */ - if (cp == NULL) - return; - op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); -#ifdef debug - ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */ + if (cp == NULL) + return; + op = (union overhead *)((caddr_t)cp + - sizeof (union overhead) * CHUNK_SHIFT); +#ifdef PACK_MALLOC + bucket = OV_INDEX(op); +#endif +#ifdef DEBUGGING + ASSERT(OV_MAGIC(op, bucket) == MAGIC); /* make sure it was in use */ #else - if (op->ov_magic != MAGIC) { + if (OV_MAGIC(op, bucket) != MAGIC) { + static bad_free_warn = -1; + if (bad_free_warn == -1) { + char *pbf = getenv("PERL_BADFREE"); + bad_free_warn = (pbf) ? atoi(pbf) : 1; + } + if (!bad_free_warn) + return; +#ifdef RCHECK warn("%s free() ignored", - op->ov_magic == OLDMAGIC ? "Duplicate" : "Bad"); + op->ov_rmagic == RMAGIC - 1 ? "Duplicate" : "Bad"); +#else + warn("Bad free() ignored"); +#endif return; /* sanity */ } - op->ov_magic = OLDMAGIC; #endif #ifdef RCHECK ASSERT(op->ov_rmagic == RMAGIC); - if (op->ov_index <= 13) + if (OV_INDEX(op) <= 13) ASSERT(*(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC); + op->ov_rmagic = RMAGIC - 1; #endif - ASSERT(op->ov_index < NBUCKETS); - size = op->ov_index; + ASSERT(OV_INDEX(op) < NBUCKETS); + size = OV_INDEX(op); op->ov_next = nextf[size]; nextf[size] = op; -#ifdef MSTATS +#ifdef DEBUGGING_MSTATS nmalloc[size]--; #endif } @@ -336,12 +449,12 @@ free(mp) */ int reall_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ -MALLOCPTRTYPE * +Malloc_t realloc(mp, nbytes) - MALLOCPTRTYPE *mp; - unsigned nbytes; + Malloc_t mp; + MEM_SIZE nbytes; { - register u_int onb; + register MEM_SIZE onb; union overhead *op; char *res; register int i; @@ -350,29 +463,28 @@ realloc(mp, nbytes) #ifdef safemalloc #ifdef DEBUGGING - int size = nbytes; + MEM_SIZE size = nbytes; #endif #ifdef MSDOS if (nbytes > 0xffff) { - fprintf(stderr, "Reallocation too large: %lx\n", size); - exit(1); + PerlIO_printf(PerlIO_stderr(), "Reallocation too large: %lx\n", size); + my_exit(1); } #endif /* MSDOS */ if (!cp) - fatal("Null realloc"); + return malloc(nbytes); #ifdef DEBUGGING if ((long)nbytes < 0) - fatal("panic: realloc"); + croak("panic: realloc"); #endif #endif /* safemalloc */ - if (cp == NULL) - return (malloc(nbytes)); - op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); - if (op->ov_magic == MAGIC) { + op = (union overhead *)((caddr_t)cp + - sizeof (union overhead) * CHUNK_SHIFT); + i = OV_INDEX(op); + if (OV_MAGIC(op, i) == MAGIC) { was_alloced++; - i = op->ov_index; } else { /* * Already free, doing "compaction". @@ -389,23 +501,29 @@ realloc(mp, nbytes) (i = findbucket(op, reall_srchlen)) < 0) i = 0; } - onb = (1 << (i + 3)) - sizeof (*op) - RSLOP; + onb = (1L << (i + 3)) - +#ifdef PACK_MALLOC + (i <= (MAX_PACKED - 3) ? 0 : M_OVERHEAD) +#else + M_OVERHEAD +#endif + ; /* avoid the copy if same size block */ if (was_alloced && - nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP) { + nbytes <= onb && nbytes > (onb >> 1) - M_OVERHEAD) { #ifdef RCHECK /* * Record new allocated size of block and * bound space with magic numbers. */ - if (op->ov_index <= 13) { + if (OV_INDEX(op) <= 13) { /* * Convert amount of memory requested into * closest block size stored in hash buckets * which satisfies request. Account for * space used per block for accounting. */ - nbytes += sizeof (union overhead) + RSLOP; + nbytes += M_OVERHEAD; nbytes = (nbytes + 3) &~ 3; op->ov_size = nbytes - 1; *((u_int *)((caddr_t)op + nbytes - RSLOP)) = RMAGIC; @@ -417,27 +535,21 @@ realloc(mp, nbytes) if ((res = (char*)malloc(nbytes)) == NULL) return (NULL); if (cp != res) /* common optimization */ - bcopy(cp, res, (int)(nbytes < onb ? nbytes : onb)); + Copy(cp, res, (MEM_SIZE)(nbytesov_next, j++) ; - fprintf(stderr, " %d", j); - totfree += j * (1 << (i + 3)); - } - fprintf(stderr, "\nused:\t"); - for (i = 0; i < NBUCKETS; i++) { - fprintf(stderr, " %d", nmalloc[i]); + nfree[i] = j; + totfree += nfree[i] * (1 << (i + 3)); totused += nmalloc[i] * (1 << (i + 3)); + if (nfree[i] || nmalloc[i]) + topbucket = i; + } + if (s) + PerlIO_printf(PerlIO_stderr(), "Memory allocation statistics %s (buckets 8..%d)\n", + s, (1 << (topbucket + 3)) ); + PerlIO_printf(PerlIO_stderr(), " %7d free: ", totfree); + for (i=0; i <= topbucket; i++) { + PerlIO_printf(PerlIO_stderr(), (i<5)?" %5d":" %3d", nfree[i]); } - fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n", - totused, totfree); + PerlIO_printf(PerlIO_stderr(), "\n %7d used: ", totused); + for (i=0; i <= topbucket; i++) { + PerlIO_printf(PerlIO_stderr(), (i<5)?" %5d":" %3d", nmalloc[i]); + } + PerlIO_printf(PerlIO_stderr(), "\n"); +#ifdef PACK_MALLOC + if (sbrk_slack || start_slack) { + PerlIO_printf(PerlIO_stderr(), "Odd ends: %7d bytes from sbrk(), %7d from malloc.\n", + sbrk_slack, start_slack); + } +#endif +} +#else +void +dump_mstats(s) + char *s; +{ } #endif #endif /* lint */ + + +#ifdef USE_PERL_SBRK + +# ifdef NeXT +# define PERL_SBRK_VIA_MALLOC +# endif + +# ifdef PERL_SBRK_VIA_MALLOC +# ifdef HIDEMYMALLOC +# undef malloc +# else +# include "Error: -DPERL_SBRK_VIA_MALLOC requires -DHIDEMYMALLOC" +# endif + +/* it may seem schizophrenic to use perl's malloc and let it call system */ +/* malloc, the reason for that is only the 3.2 version of the OS that had */ +/* frequent core dumps within nxzonefreenolock. This sbrk routine put an */ +/* end to the cores */ + +# define SYSTEM_ALLOC(a) malloc(a) + +# endif /* PERL_SBRK_VIA_MALLOC */ + +static IV Perl_sbrk_oldchunk; +static long Perl_sbrk_oldsize; + +# define PERLSBRK_32_K (1<<15) +# define PERLSBRK_64_K (1<<16) + +char * +Perl_sbrk(size) +int size; +{ + IV got; + int small, reqsize; + + if (!size) return 0; +#ifdef safemalloc + reqsize = size; /* just for the DEBUG_m statement */ +#endif + if (size <= Perl_sbrk_oldsize) { + got = Perl_sbrk_oldchunk; + Perl_sbrk_oldchunk += size; + Perl_sbrk_oldsize -= size; + } else { + if (size >= PERLSBRK_32_K) { + small = 0; + } else { +#ifndef safemalloc + reqsize = size; +#endif + size = PERLSBRK_64_K; + small = 1; + } + got = (IV)SYSTEM_ALLOC(size); + if (small) { + /* Chunk is small, register the rest for future allocs. */ + Perl_sbrk_oldchunk = got + reqsize; + Perl_sbrk_oldsize = size - reqsize; + } + } + +#ifdef safemalloc + DEBUG_m(PerlIO_printf(PerlIO_stderr(), "sbrk malloc size %ld (reqsize %ld), left size %ld, give addr 0x%lx\n", + size, reqsize, Perl_sbrk_oldsize, got)); +#endif + + return (void *)got; +} + +#endif /* ! defined USE_PERL_SBRK */