Fix for environment leak
[perl.git] / malloc.c
1 /*    malloc.c
2  *
3  */
4
5 #ifndef lint
6 #  if defined(DEBUGGING) && !defined(NO_RCHECK)
7 #    define RCHECK
8 #  endif
9 /*
10  * malloc.c (Caltech) 2/21/82
11  * Chris Kingsley, kingsley@cit-20.
12  *
13  * This is a very fast storage allocator.  It allocates blocks of a small 
14  * number of different sizes, and keeps free lists of each size.  Blocks that
15  * don't exactly fit are passed up to the next larger size.  In this 
16  * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
17  * If PACK_MALLOC is defined, small blocks are 2^n bytes long.
18  * This is designed for use in a program that uses vast quantities of memory,
19  * but bombs when it runs out. 
20  */
21
22 #include "EXTERN.h"
23 #include "perl.h"
24
25 #ifdef DEBUGGING
26 #undef DEBUG_m
27 #define DEBUG_m(a)  if (debug & 128)   a
28 #endif
29
30 /* I don't much care whether these are defined in sys/types.h--LAW */
31
32 #define u_char unsigned char
33 #define u_int unsigned int
34 #define u_short unsigned short
35
36 /* 286 and atarist like big chunks, which gives too much overhead. */
37 #if (defined(RCHECK) || defined(I286) || defined(atarist)) && defined(PACK_MALLOC)
38 #undef PACK_MALLOC
39 #endif 
40
41
42 /*
43  * The description below is applicable if PACK_MALLOC is not defined.
44  *
45  * The overhead on a block is at least 4 bytes.  When free, this space
46  * contains a pointer to the next free block, and the bottom two bits must
47  * be zero.  When in use, the first byte is set to MAGIC, and the second
48  * byte is the size index.  The remaining bytes are for alignment.
49  * If range checking is enabled and the size of the block fits
50  * in two bytes, then the top two bytes hold the size of the requested block
51  * plus the range checking words, and the header word MINUS ONE.
52  */
53 union   overhead {
54         union   overhead *ov_next;      /* when free */
55 #if MEM_ALIGNBYTES > 4
56         double  strut;                  /* alignment problems */
57 #endif
58         struct {
59                 u_char  ovu_magic;      /* magic number */
60                 u_char  ovu_index;      /* bucket # */
61 #ifdef RCHECK
62                 u_short ovu_size;       /* actual block size */
63                 u_int   ovu_rmagic;     /* range magic number */
64 #endif
65         } ovu;
66 #define ov_magic        ovu.ovu_magic
67 #define ov_index        ovu.ovu_index
68 #define ov_size         ovu.ovu_size
69 #define ov_rmagic       ovu.ovu_rmagic
70 };
71
72 #ifdef DEBUGGING
73 static void botch _((char *s));
74 #endif
75 static void morecore _((int bucket));
76 static int findbucket _((union overhead *freep, int srchlen));
77
78 #define MAGIC           0xff            /* magic # on accounting info */
79 #define RMAGIC          0x55555555      /* magic # on range info */
80 #ifdef RCHECK
81 #  define       RSLOP           sizeof (u_int)
82 #  ifdef TWO_POT_OPTIMIZE
83 #    define MAX_SHORT_BUCKET 12
84 #  else
85 #    define MAX_SHORT_BUCKET 13
86 #  endif 
87 #else
88 #  define       RSLOP           0
89 #endif
90
91 #ifdef PACK_MALLOC
92 /*
93  * In this case it is assumed that if we do sbrk() in 2K units, we
94  * will get 2K aligned blocks. The bucket number of the given subblock is
95  * on the boundary of 2K block which contains the subblock.
96  * Several following bytes contain the magic numbers for the subblocks
97  * in the block.
98  *
99  * Sizes of chunks are powers of 2 for chunks in buckets <=
100  * MAX_PACKED, after this they are (2^n - sizeof(union overhead)) (to
101  * get alignment right).
102  *
103  * We suppose that starts of all the chunks in a 2K block are in
104  * different 2^n-byte-long chunks.  If the top of the last chunk is
105  * aligned on a boundary of 2K block, this means that
106  * sizeof(union overhead)*"number of chunks" < 2^n, or
107  * sizeof(union overhead)*2K < 4^n, or n > 6 + log2(sizeof()/2)/2, if a
108  * chunk of size 2^n - overhead is used. Since this rules out n = 7
109  * for 8 byte alignment, we specialcase allocation of the first of 16
110  * 128-byte-long chunks.
111  *
112  * Note that with the above assumption we automatically have enough
113  * place for MAGIC at the start of 2K block.  Note also that we
114  * overlay union overhead over the chunk, thus the start of the chunk
115  * is immediately overwritten after freeing.
116  */
117 #  define MAX_PACKED 6
118 #  define MAX_2_POT_ALGO ((1<<(MAX_PACKED + 1)) - M_OVERHEAD)
119 #  define TWOK_MASK ((1<<11) - 1)
120 #  define TWOK_MASKED(x) ((u_int)(x) & ~TWOK_MASK)
121 #  define TWOK_SHIFT(x) ((u_int)(x) & TWOK_MASK)
122 #  define OV_INDEXp(block) ((u_char*)(TWOK_MASKED(block)))
123 #  define OV_INDEX(block) (*OV_INDEXp(block))
124 #  define OV_MAGIC(block,bucket) (*(OV_INDEXp(block) +                  \
125                                     (TWOK_SHIFT(block)>>(bucket + 3)) + \
126                                     (bucket > MAX_NONSHIFT ? 1 : 0)))
127 #  define CHUNK_SHIFT 0
128
129 static u_char n_blks[11 - 3]     = {224, 120, 62, 31, 16, 8, 4, 2};
130 static u_short blk_shift[11 - 3] = {256, 128, 64, 32, 
131                                     16*sizeof(union overhead), 
132                                     8*sizeof(union overhead), 
133                                     4*sizeof(union overhead), 
134                                     2*sizeof(union overhead), 
135 #  define MAX_NONSHIFT 2        /* Shift 64 greater than chunk 32. */
136 };
137
138 #else  /* !PACK_MALLOC */
139
140 #  define OV_MAGIC(block,bucket) (block)->ov_magic
141 #  define OV_INDEX(block) (block)->ov_index
142 #  define CHUNK_SHIFT 1
143 #endif /* !PACK_MALLOC */
144
145 #  define M_OVERHEAD (sizeof(union overhead) + RSLOP)
146
147 /*
148  * Big allocations are often of the size 2^n bytes. To make them a
149  * little bit better, make blocks of size 2^n+pagesize for big n.
150  */
151
152 #ifdef TWO_POT_OPTIMIZE
153
154 #  ifndef PERL_PAGESIZE
155 #    define PERL_PAGESIZE 4096
156 #  endif 
157 #  ifndef FIRST_BIG_TWO_POT
158 #    define FIRST_BIG_TWO_POT 14        /* 16K */
159 #  endif
160 #  define FIRST_BIG_BLOCK (1<<FIRST_BIG_TWO_POT) /* 16K */
161 /* If this value or more, check against bigger blocks. */
162 #  define FIRST_BIG_BOUND (FIRST_BIG_BLOCK - M_OVERHEAD)
163 /* If less than this value, goes into 2^n-overhead-block. */
164 #  define LAST_SMALL_BOUND ((FIRST_BIG_BLOCK>>1) - M_OVERHEAD)
165
166 #endif /* TWO_POT_OPTIMIZE */
167
168 #if defined(PERL_EMERGENCY_SBRK) && defined(PERL_CORE)
169
170 #ifndef BIG_SIZE
171 #  define BIG_SIZE (1<<16)              /* 64K */
172 #endif 
173
174 static char *emergency_buffer;
175 static MEM_SIZE emergency_buffer_size;
176
177 static char *
178 emergency_sbrk(size)
179     MEM_SIZE size;
180 {
181     if (size >= BIG_SIZE) {
182         /* Give the possibility to recover: */
183         die("Out of memory during request for %i bytes", size);
184         /* croak may eat too much memory. */
185     }
186
187     if (!emergency_buffer) {            
188         /* First offense, give a possibility to recover by dieing. */
189         /* No malloc involved here: */
190         GV **gvp = (GV**)hv_fetch(defstash, "^M", 2, 0);
191         SV *sv;
192         char *pv;
193
194         if (!gvp) gvp = (GV**)hv_fetch(defstash, "\015", 1, 0);
195         if (!gvp || !(sv = GvSV(*gvp)) || !SvPOK(sv) 
196             || (SvLEN(sv) < (1<<11) - M_OVERHEAD)) 
197             return (char *)-1;          /* Now die die die... */
198
199         /* Got it, now detach SvPV: */
200         pv = SvPV(sv, na);
201         /* Check alignment: */
202         if (((u_int)(pv - M_OVERHEAD)) & ((1<<11) - 1)) {
203             PerlIO_puts(PerlIO_stderr(),"Bad alignment of $^M!\n");
204             return (char *)-1;          /* die die die */
205         }
206
207         emergency_buffer = pv - M_OVERHEAD;
208         emergency_buffer_size = SvLEN(sv) + M_OVERHEAD;
209         SvPOK_off(sv);
210         SvREADONLY_on(sv);
211         die("Out of memory!");          /* croak may eat too much memory. */
212     }
213     else if (emergency_buffer_size >= size) {
214         emergency_buffer_size -= size;
215         return emergency_buffer + emergency_buffer_size;
216     }
217     
218     return (char *)-1;                  /* poor guy... */
219 }
220
221 #else /* !(defined(TWO_POT_OPTIMIZE) && defined(PERL_CORE)) */
222 #  define emergency_sbrk(size)  -1
223 #endif /* !(defined(TWO_POT_OPTIMIZE) && defined(PERL_CORE)) */
224
225 /*
226  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
227  * smallest allocatable block is 8 bytes.  The overhead information
228  * precedes the data area returned to the user.
229  */
230 #define NBUCKETS 30
231 static  union overhead *nextf[NBUCKETS];
232
233 #ifdef USE_PERL_SBRK
234 #define sbrk(a) Perl_sbrk(a)
235 char *  Perl_sbrk _((int size));
236 #else
237 extern  char *sbrk();
238 #endif
239
240 #ifdef DEBUGGING_MSTATS
241 /*
242  * nmalloc[i] is the difference between the number of mallocs and frees
243  * for a given block size.
244  */
245 static  u_int nmalloc[NBUCKETS];
246 static  u_int goodsbrk;
247 static  u_int sbrk_slack;
248 static  u_int start_slack;
249 #endif
250
251 #ifdef DEBUGGING
252 #define ASSERT(p)   if (!(p)) botch(STRINGIFY(p));  else
253 static void
254 botch(s)
255         char *s;
256 {
257         PerlIO_printf(PerlIO_stderr(), "assertion botched: %s\n", s);
258         abort();
259 }
260 #else
261 #define ASSERT(p)
262 #endif
263
264 Malloc_t
265 malloc(nbytes)
266         register MEM_SIZE nbytes;
267 {
268         register union overhead *p;
269         register int bucket = 0;
270         register MEM_SIZE shiftr;
271
272 #if defined(DEBUGGING) || defined(RCHECK)
273         MEM_SIZE size = nbytes;
274 #endif
275
276 #ifdef PERL_CORE
277 #ifdef HAS_64K_LIMIT
278         if (nbytes > 0xffff) {
279                 PerlIO_printf(PerlIO_stderr(),
280                               "Allocation too large: %lx\n", (long)nbytes);
281                 my_exit(1);
282         }
283 #endif /* HAS_64K_LIMIT */
284 #ifdef DEBUGGING
285         if ((long)nbytes < 0)
286                 croak("panic: malloc");
287 #endif
288 #endif /* PERL_CORE */
289
290         /*
291          * Convert amount of memory requested into
292          * closest block size stored in hash buckets
293          * which satisfies request.  Account for
294          * space used per block for accounting.
295          */
296 #ifdef PACK_MALLOC
297         if (nbytes == 0)
298             nbytes = 1;
299         else if (nbytes > MAX_2_POT_ALGO)
300 #endif
301         {
302 #ifdef TWO_POT_OPTIMIZE
303                 if (nbytes >= FIRST_BIG_BOUND)
304                         nbytes -= PERL_PAGESIZE;
305 #endif 
306                 nbytes += M_OVERHEAD;
307                 nbytes = (nbytes + 3) &~ 3; 
308         }
309         shiftr = (nbytes - 1) >> 2;
310         /* apart from this loop, this is O(1) */
311         while (shiftr >>= 1)
312                 bucket++;
313         /*
314          * If nothing in hash bucket right now,
315          * request more memory from the system.
316          */
317         if (nextf[bucket] == NULL)    
318                 morecore(bucket);
319         if ((p = (union overhead *)nextf[bucket]) == NULL) {
320 #ifdef PERL_CORE
321                 if (!nomemok) {
322                     PerlIO_puts(PerlIO_stderr(),"Out of memory!\n");
323                     my_exit(1);
324                 }
325 #else
326                 return (NULL);
327 #endif
328         }
329
330 #ifdef PERL_CORE
331     DEBUG_m(PerlIO_printf(Perl_debug_log, "0x%lx: (%05lu) malloc %ld bytes\n",
332         (unsigned long)(p+1),(unsigned long)(an++),(long)size));
333 #endif /* PERL_CORE */
334
335         /* remove from linked list */
336 #ifdef RCHECK
337         if (*((int*)p) & (sizeof(union overhead) - 1))
338             PerlIO_printf(PerlIO_stderr(), "Corrupt malloc ptr 0x%lx at 0x%lx\n",
339                 (unsigned long)*((int*)p),(unsigned long)p);
340 #endif
341         nextf[bucket] = p->ov_next;
342         OV_MAGIC(p, bucket) = MAGIC;
343 #ifndef PACK_MALLOC
344         OV_INDEX(p) = bucket;
345 #endif
346 #ifdef RCHECK
347         /*
348          * Record allocated size of block and
349          * bound space with magic numbers.
350          */
351         nbytes = (size + M_OVERHEAD + 3) &~ 3; 
352         if (nbytes <= 0x10000)
353                 p->ov_size = nbytes - 1;
354         p->ov_rmagic = RMAGIC;
355         *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
356 #endif
357         return ((Malloc_t)(p + CHUNK_SHIFT));
358 }
359
360 /*
361  * Allocate more memory to the indicated bucket.
362  */
363 static void
364 morecore(bucket)
365         register int bucket;
366 {
367         register union overhead *op;
368         register int rnu;       /* 2^rnu bytes will be requested */
369         register int nblks;     /* become nblks blocks of the desired size */
370         register MEM_SIZE siz, needed;
371         int slack = 0;
372
373         if (nextf[bucket])
374                 return;
375         if (bucket == (sizeof(MEM_SIZE)*8 - 3)) {
376             croak("Allocation too large");
377         }
378         /*
379          * Insure memory is allocated
380          * on a page boundary.  Should
381          * make getpageize call?
382          */
383 #ifndef atarist /* on the atari we dont have to worry about this */
384         op = (union overhead *)sbrk(0);
385 #  ifndef I286
386         if ((UV)op & (0x7FF >> CHUNK_SHIFT)) {
387             slack = (0x800 >> CHUNK_SHIFT) - ((UV)op & (0x7FF >> CHUNK_SHIFT));
388             (void)sbrk(slack);
389 #    if defined(DEBUGGING_MSTATS)
390             sbrk_slack += slack;
391 #    endif
392         }
393 #  else
394         /* The sbrk(0) call on the I286 always returns the next segment */
395 #  endif
396 #endif /* atarist */
397
398 #if !(defined(I286) || defined(atarist))
399         /* take 2k unless the block is bigger than that */
400         rnu = (bucket <= 8) ? 11 : bucket + 3;
401 #else
402         /* take 16k unless the block is bigger than that 
403            (80286s like large segments!), probably good on the atari too */
404         rnu = (bucket <= 11) ? 14 : bucket + 3;
405 #endif
406         nblks = 1 << (rnu - (bucket + 3));  /* how many blocks to get */
407         needed = (MEM_SIZE)1 << rnu;
408 #ifdef TWO_POT_OPTIMIZE
409         needed += (bucket >= (FIRST_BIG_TWO_POT - 3) ? PERL_PAGESIZE : 0);
410 #endif 
411         op = (union overhead *)sbrk(needed);
412         /* no more room! */
413         if (op == (union overhead *)-1) {
414             op = (union overhead *)emergency_sbrk(needed);
415             if (op == (union overhead *)-1)
416                 return;
417         }
418 #ifdef DEBUGGING_MSTATS
419         goodsbrk += needed;
420 #endif  
421         /*
422          * Round up to minimum allocation size boundary
423          * and deduct from block count to reflect.
424          */
425 #ifndef I286
426 #  ifdef PACK_MALLOC
427         if ((UV)op & 0x7FF)
428                 croak("panic: Off-page sbrk");
429 #  endif
430         if ((UV)op & 7) {
431                 op = (union overhead *)(((UV)op + 8) & ~7);
432                 nblks--;
433         }
434 #else
435         /* Again, this should always be ok on an 80286 */
436 #endif
437         /*
438          * Add new memory allocated to that on
439          * free list for this hash bucket.
440          */
441         siz = 1 << (bucket + 3);
442 #ifdef PACK_MALLOC
443         *(u_char*)op = bucket;  /* Fill index. */
444         if (bucket <= MAX_PACKED - 3) {
445             op = (union overhead *) ((char*)op + blk_shift[bucket]);
446             nblks = n_blks[bucket];
447 #  ifdef DEBUGGING_MSTATS
448             start_slack += blk_shift[bucket];
449 #  endif
450         } else if (bucket <= 11 - 1 - 3) {
451             op = (union overhead *) ((char*)op + blk_shift[bucket]);
452             /* nblks = n_blks[bucket]; */
453             siz -= sizeof(union overhead);
454         } else op++;            /* One chunk per block. */
455 #endif /* !PACK_MALLOC */
456         nextf[bucket] = op;
457 #ifdef DEBUGGING_MSTATS
458         nmalloc[bucket] += nblks;
459 #endif 
460         while (--nblks > 0) {
461                 op->ov_next = (union overhead *)((caddr_t)op + siz);
462                 op = (union overhead *)((caddr_t)op + siz);
463         }
464         /* Not all sbrks return zeroed memory.*/
465         op->ov_next = (union overhead *)NULL;
466 #ifdef PACK_MALLOC
467         if (bucket == 7 - 3) {  /* Special case, explanation is above. */
468             union overhead *n_op = nextf[7 - 3]->ov_next;
469             nextf[7 - 3] = (union overhead *)((caddr_t)nextf[7 - 3] 
470                                               - sizeof(union overhead));
471             nextf[7 - 3]->ov_next = n_op;
472         }
473 #endif /* !PACK_MALLOC */
474 }
475
476 Free_t
477 free(mp)
478         Malloc_t mp;
479 {   
480         register MEM_SIZE size;
481         register union overhead *op;
482         char *cp = (char*)mp;
483 #ifdef PACK_MALLOC
484         u_char bucket;
485 #endif 
486
487 #ifdef PERL_CORE
488     DEBUG_m(PerlIO_printf(Perl_debug_log, "0x%lx: (%05lu) free\n",(unsigned long)cp,(unsigned long)(an++)));
489 #endif /* PERL_CORE */
490
491         if (cp == NULL)
492                 return;
493         op = (union overhead *)((caddr_t)cp 
494                                 - sizeof (union overhead) * CHUNK_SHIFT);
495 #ifdef PACK_MALLOC
496         bucket = OV_INDEX(op);
497 #endif 
498         if (OV_MAGIC(op, bucket) != MAGIC) {
499                 static int bad_free_warn = -1;
500                 if (bad_free_warn == -1) {
501                     char *pbf = getenv("PERL_BADFREE");
502                     bad_free_warn = (pbf) ? atoi(pbf) : 1;
503                 }
504                 if (!bad_free_warn)
505                     return;
506 #ifdef RCHECK
507                 warn("%s free() ignored",
508                     op->ov_rmagic == RMAGIC - 1 ? "Duplicate" : "Bad");
509 #else
510                 warn("Bad free() ignored");
511 #endif
512                 return;                         /* sanity */
513         }
514 #ifdef RCHECK
515         ASSERT(op->ov_rmagic == RMAGIC);
516         if (OV_INDEX(op) <= MAX_SHORT_BUCKET)
517                 ASSERT(*(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC);
518         op->ov_rmagic = RMAGIC - 1;
519 #endif
520         ASSERT(OV_INDEX(op) < NBUCKETS);
521         size = OV_INDEX(op);
522         op->ov_next = nextf[size];
523         nextf[size] = op;
524 }
525
526 /*
527  * When a program attempts "storage compaction" as mentioned in the
528  * old malloc man page, it realloc's an already freed block.  Usually
529  * this is the last block it freed; occasionally it might be farther
530  * back.  We have to search all the free lists for the block in order
531  * to determine its bucket: 1st we make one pass thru the lists
532  * checking only the first block in each; if that fails we search
533  * ``reall_srchlen'' blocks in each list for a match (the variable
534  * is extern so the caller can modify it).  If that fails we just copy
535  * however many bytes was given to realloc() and hope it's not huge.
536  */
537 int reall_srchlen = 4;  /* 4 should be plenty, -1 =>'s whole list */
538
539 Malloc_t
540 realloc(mp, nbytes)
541         Malloc_t mp; 
542         MEM_SIZE nbytes;
543 {   
544         register MEM_SIZE onb;
545         union overhead *op;
546         char *res;
547         register int i;
548         int was_alloced = 0;
549         char *cp = (char*)mp;
550
551 #ifdef DEBUGGING
552         MEM_SIZE size = nbytes;
553 #endif
554
555 #ifdef PERL_CORE
556 #ifdef HAS_64K_LIMIT
557         if (nbytes > 0xffff) {
558                 PerlIO_printf(PerlIO_stderr(),
559                               "Reallocation too large: %lx\n", size);
560                 my_exit(1);
561         }
562 #endif /* HAS_64K_LIMIT */
563         if (!cp)
564                 return malloc(nbytes);
565 #ifdef DEBUGGING
566         if ((long)nbytes < 0)
567                 croak("panic: realloc");
568 #endif
569 #endif /* PERL_CORE */
570
571         op = (union overhead *)((caddr_t)cp 
572                                 - sizeof (union overhead) * CHUNK_SHIFT);
573         i = OV_INDEX(op);
574         if (OV_MAGIC(op, i) == MAGIC) {
575                 was_alloced = 1;
576         } else {
577                 /*
578                  * Already free, doing "compaction".
579                  *
580                  * Search for the old block of memory on the
581                  * free list.  First, check the most common
582                  * case (last element free'd), then (this failing)
583                  * the last ``reall_srchlen'' items free'd.
584                  * If all lookups fail, then assume the size of
585                  * the memory block being realloc'd is the
586                  * smallest possible.
587                  */
588                 if ((i = findbucket(op, 1)) < 0 &&
589                     (i = findbucket(op, reall_srchlen)) < 0)
590                         i = 0;
591         }
592         onb = (1L << (i + 3)) - 
593 #ifdef PACK_MALLOC
594             (i <= (MAX_PACKED - 3) ? 0 : M_OVERHEAD)
595 #else
596             M_OVERHEAD
597 #endif
598 #ifdef TWO_POT_OPTIMIZE
599             + (i >= (FIRST_BIG_TWO_POT - 3) ? PERL_PAGESIZE : 0)
600 #endif
601             ;
602         /* 
603          *  avoid the copy if same size block.
604          *  We are not agressive with boundary cases. Note that it is
605          *  possible for small number of cases give false negative if
606          *  both new size and old one are in the bucket for
607          *  FIRST_BIG_TWO_POT, but the new one is near the lower end.
608          */
609         if (was_alloced &&
610             nbytes <= onb && (nbytes > ( (onb >> 1) - M_OVERHEAD )
611 #ifdef TWO_POT_OPTIMIZE
612                               || (i == (FIRST_BIG_TWO_POT - 3) 
613                                   && nbytes >= LAST_SMALL_BOUND )
614 #endif  
615                 )) {
616 #ifdef RCHECK
617                 /*
618                  * Record new allocated size of block and
619                  * bound space with magic numbers.
620                  */
621                 if (OV_INDEX(op) <= MAX_SHORT_BUCKET) {
622                         /*
623                          * Convert amount of memory requested into
624                          * closest block size stored in hash buckets
625                          * which satisfies request.  Account for
626                          * space used per block for accounting.
627                          */
628                         nbytes += M_OVERHEAD;
629                         nbytes = (nbytes + 3) &~ 3; 
630                         op->ov_size = nbytes - 1;
631                         *((u_int *)((caddr_t)op + nbytes - RSLOP)) = RMAGIC;
632                 }
633 #endif
634                 res = cp;
635         }
636         else {
637                 if ((res = (char*)malloc(nbytes)) == NULL)
638                         return (NULL);
639                 if (cp != res)                  /* common optimization */
640                         Copy(cp, res, (MEM_SIZE)(nbytes<onb?nbytes:onb), char);
641                 if (was_alloced)
642                         free(cp);
643         }
644
645 #ifdef PERL_CORE
646 #ifdef DEBUGGING
647     if (debug & 128) {
648         PerlIO_printf(PerlIO_stderr(), "0x%lx: (%05lu) rfree\n",(unsigned long)res,(unsigned long)(an++));
649         PerlIO_printf(PerlIO_stderr(), "0x%lx: (%05lu) realloc %ld bytes\n",
650             (unsigned long)res,(unsigned long)(an++),(long)size);
651     }
652 #endif
653 #endif /* PERL_CORE */
654         return ((Malloc_t)res);
655 }
656
657 /*
658  * Search ``srchlen'' elements of each free list for a block whose
659  * header starts at ``freep''.  If srchlen is -1 search the whole list.
660  * Return bucket number, or -1 if not found.
661  */
662 static int
663 findbucket(freep, srchlen)
664         union overhead *freep;
665         int srchlen;
666 {
667         register union overhead *p;
668         register int i, j;
669
670         for (i = 0; i < NBUCKETS; i++) {
671                 j = 0;
672                 for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
673                         if (p == freep)
674                                 return (i);
675                         j++;
676                 }
677         }
678         return (-1);
679 }
680
681 Malloc_t
682 calloc(elements, size)
683         register MEM_SIZE elements;
684         register MEM_SIZE size;
685 {
686     long sz = elements * size;
687     Malloc_t p = malloc(sz);
688
689     if (p) {
690         memset((void*)p, 0, sz);
691     }
692     return p;
693 }
694
695 #ifdef DEBUGGING_MSTATS
696 /*
697  * mstats - print out statistics about malloc
698  * 
699  * Prints two lines of numbers, one showing the length of the free list
700  * for each size category, the second showing the number of mallocs -
701  * frees for each size category.
702  */
703 void
704 dump_mstats(s)
705         char *s;
706 {
707         register int i, j;
708         register union overhead *p;
709         int topbucket=0, totfree=0, total=0;
710         u_int nfree[NBUCKETS];
711
712         for (i=0; i < NBUCKETS; i++) {
713                 for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
714                         ;
715                 nfree[i] = j;
716                 totfree += nfree[i]   * (1 << (i + 3));
717                 total += nmalloc[i] * (1 << (i + 3));
718                 if (nmalloc[i])
719                         topbucket = i;
720         }
721         if (s)
722                 PerlIO_printf(PerlIO_stderr(), "Memory allocation statistics %s (buckets 8..%d)\n",
723                         s, (1 << (topbucket + 3)) );
724         PerlIO_printf(PerlIO_stderr(), "%8d free:", totfree);
725         for (i=0; i <= topbucket; i++) {
726                 PerlIO_printf(PerlIO_stderr(), (i<5 || i==7)?" %5d": (i<9)?" %3d":" %d", nfree[i]);
727         }
728         PerlIO_printf(PerlIO_stderr(), "\n%8d used:", total - totfree);
729         for (i=0; i <= topbucket; i++) {
730                 PerlIO_printf(PerlIO_stderr(), (i<5 || i==7)?" %5d": (i<9)?" %3d":" %d", nmalloc[i] - nfree[i]);
731         }
732         PerlIO_printf(PerlIO_stderr(), "\nTotal sbrk(): %8d. Odd ends: sbrk(): %7d, malloc(): %7d bytes.\n",
733                       goodsbrk + sbrk_slack, sbrk_slack, start_slack);
734 }
735 #else
736 void
737 dump_mstats(s)
738     char *s;
739 {
740 }
741 #endif
742 #endif /* lint */
743
744
745 #ifdef USE_PERL_SBRK
746
747 #   ifdef NeXT
748 #      define PERL_SBRK_VIA_MALLOC
749 #   endif
750
751 #   ifdef PERL_SBRK_VIA_MALLOC
752 #      if defined(HIDEMYMALLOC) || defined(EMBEDMYMALLOC)
753 #         undef malloc
754 #      else
755 #         include "Error: -DPERL_SBRK_VIA_MALLOC needs -D(HIDE|EMBED)MYMALLOC"
756 #      endif
757
758 /* it may seem schizophrenic to use perl's malloc and let it call system */
759 /* malloc, the reason for that is only the 3.2 version of the OS that had */
760 /* frequent core dumps within nxzonefreenolock. This sbrk routine put an */
761 /* end to the cores */
762
763 #      define SYSTEM_ALLOC(a) malloc(a)
764
765 #   endif  /* PERL_SBRK_VIA_MALLOC */
766
767 static IV Perl_sbrk_oldchunk;
768 static long Perl_sbrk_oldsize;
769
770 #   define PERLSBRK_32_K (1<<15)
771 #   define PERLSBRK_64_K (1<<16)
772
773 char *
774 Perl_sbrk(size)
775 int size;
776 {
777     IV got;
778     int small, reqsize;
779
780     if (!size) return 0;
781 #ifdef PERL_CORE
782     reqsize = size; /* just for the DEBUG_m statement */
783 #endif
784     if (size <= Perl_sbrk_oldsize) {
785         got = Perl_sbrk_oldchunk;
786         Perl_sbrk_oldchunk += size;
787         Perl_sbrk_oldsize -= size;
788     } else {
789       if (size >= PERLSBRK_32_K) {
790         small = 0;
791       } else {
792 #ifndef PERL_CORE
793         reqsize = size;
794 #endif
795         size = PERLSBRK_64_K;
796         small = 1;
797       }
798       got = (IV)SYSTEM_ALLOC(size);
799       if (small) {
800         /* Chunk is small, register the rest for future allocs. */
801         Perl_sbrk_oldchunk = got + reqsize;
802         Perl_sbrk_oldsize = size - reqsize;
803       }
804     }
805
806 #ifdef PERL_CORE
807     DEBUG_m(PerlIO_printf(PerlIO_stderr(), "sbrk malloc size %ld (reqsize %ld), left size %ld, give addr 0x%lx\n",
808                     size, reqsize, Perl_sbrk_oldsize, got));
809 #endif
810
811     return (void *)got;
812 }
813
814 #endif /* ! defined USE_PERL_SBRK */