This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
Use root EXTERN.h when compiling x2p/malloc.c.
[perl5.git] / malloc.c
CommitLineData
a0d0e21e 1/* malloc.c
8d063cd8 2 *
8d063cd8
LW
3 */
4
5#ifndef lint
a687059c 6#ifdef DEBUGGING
8d063cd8 7#define RCHECK
a687059c 8#endif
8d063cd8
LW
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.
cf5c4ad8 17 * If PACK_MALLOC is defined, small blocks are 2^n bytes long.
8d063cd8
LW
18 * This is designed for use in a program that uses vast quantities of memory,
19 * but bombs when it runs out.
20 */
21
135863df 22#include "EXTERN.h"
135863df
AB
23#include "perl.h"
24
760ac839
LW
25#ifdef DEBUGGING
26#undef DEBUG_m
27#define DEBUG_m(a) if (debug & 128) a
28#endif
29
135863df
AB
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
8d063cd8 35
cf5c4ad8
PP
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
8d063cd8 42/*
cf5c4ad8
PP
43 * The description below is applicable if PACK_MALLOC is not defined.
44 *
8d063cd8
LW
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 */
53union overhead {
54 union overhead *ov_next; /* when free */
85e6fe83 55#if MEM_ALIGNBYTES > 4
c623bd54 56 double strut; /* alignment problems */
a687059c 57#endif
8d063cd8
LW
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
760ac839 72#ifdef DEBUGGING
a0d0e21e
LW
73static void botch _((char *s));
74#endif
75static void morecore _((int bucket));
76static int findbucket _((union overhead *freep, int srchlen));
77
8d063cd8
LW
78#define MAGIC 0xff /* magic # on accounting info */
79#define RMAGIC 0x55555555 /* magic # on range info */
80#ifdef RCHECK
c2a5c2d2
IZ
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
8d063cd8 87#else
c2a5c2d2 88# define RSLOP 0
8d063cd8
LW
89#endif
90
cf5c4ad8
PP
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)
ff68c719
PP
120# define TWOK_MASKED(x) ((u_int)(x) & ~TWOK_MASK)
121# define TWOK_SHIFT(x) ((u_int)(x) & TWOK_MASK)
cf5c4ad8
PP
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
129static u_char n_blks[11 - 3] = {224, 120, 62, 31, 16, 8, 4, 2};
130static 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
cf5c4ad8
PP
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
8d063cd8 147/*
55497cff
PP
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
5f05dabc
PP
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
55497cff
PP
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
72e5b9db 168#if defined(PERL_EMERGENCY_SBRK) && defined(PERL_CORE)
55497cff
PP
169
170#ifndef BIG_SIZE
171# define BIG_SIZE (1<<16) /* 64K */
172#endif
173
174static char *emergency_buffer;
175static MEM_SIZE emergency_buffer_size;
176
177static char *
178emergency_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: */
bbce6d69 200 pv = SvPV(sv, na);
55497cff 201 /* Check alignment: */
ff68c719 202 if (((u_int)(pv - M_OVERHEAD)) & ((1<<11) - 1)) {
55497cff 203 PerlIO_puts(PerlIO_stderr(),"Bad alignment of $^M!\n");
bbce6d69 204 return (char *)-1; /* die die die */
55497cff
PP
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. */
ff68c719
PP
212 }
213 else if (emergency_buffer_size >= size) {
55497cff
PP
214 emergency_buffer_size -= size;
215 return emergency_buffer + emergency_buffer_size;
216 }
217
218 return (char *)-1; /* poor guy... */
219}
220
72e5b9db 221#else /* !(defined(TWO_POT_OPTIMIZE) && defined(PERL_CORE)) */
55497cff 222# define emergency_sbrk(size) -1
72e5b9db 223#endif /* !(defined(TWO_POT_OPTIMIZE) && defined(PERL_CORE)) */
55497cff
PP
224
225/*
8d063cd8
LW
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
231static union overhead *nextf[NBUCKETS];
cf5c4ad8
PP
232
233#ifdef USE_PERL_SBRK
234#define sbrk(a) Perl_sbrk(a)
235char * Perl_sbrk _((int size));
236#else
8d063cd8 237extern char *sbrk();
cf5c4ad8 238#endif
8d063cd8 239
c07a80fd 240#ifdef DEBUGGING_MSTATS
8d063cd8
LW
241/*
242 * nmalloc[i] is the difference between the number of mallocs and frees
243 * for a given block size.
244 */
245static u_int nmalloc[NBUCKETS];
5f05dabc
PP
246static u_int goodsbrk;
247static u_int sbrk_slack;
248static u_int start_slack;
8d063cd8
LW
249#endif
250
760ac839 251#ifdef DEBUGGING
4dfc412b 252#define ASSERT(p) if (!(p)) botch(STRINGIFY(p)); else
ee0007ab 253static void
8d063cd8
LW
254botch(s)
255 char *s;
256{
4dfc412b 257 PerlIO_printf(PerlIO_stderr(), "assertion botched: %s\n", s);
8d063cd8
LW
258 abort();
259}
260#else
261#define ASSERT(p)
262#endif
263
2304df62 264Malloc_t
8d063cd8 265malloc(nbytes)
ee0007ab 266 register MEM_SIZE nbytes;
8d063cd8
LW
267{
268 register union overhead *p;
269 register int bucket = 0;
ee0007ab 270 register MEM_SIZE shiftr;
8d063cd8 271
55497cff 272#ifdef PERL_CORE
c2a5c2d2 273#if defined(DEBUGGING) || defined(RCHECK)
ee0007ab 274 MEM_SIZE size = nbytes;
45d8adaa
LW
275#endif
276
55497cff 277#ifdef HAS_64K_LIMIT
45d8adaa 278 if (nbytes > 0xffff) {
760ac839 279 PerlIO_printf(PerlIO_stderr(), "Allocation too large: %lx\n", (long)nbytes);
79072805 280 my_exit(1);
45d8adaa 281 }
55497cff 282#endif /* HAS_64K_LIMIT */
45d8adaa
LW
283#ifdef DEBUGGING
284 if ((long)nbytes < 0)
463ee0b2 285 croak("panic: malloc");
45d8adaa 286#endif
55497cff 287#endif /* PERL_CORE */
45d8adaa 288
8d063cd8
LW
289 /*
290 * Convert amount of memory requested into
291 * closest block size stored in hash buckets
292 * which satisfies request. Account for
293 * space used per block for accounting.
294 */
cf5c4ad8
PP
295#ifdef PACK_MALLOC
296 if (nbytes > MAX_2_POT_ALGO) {
297#endif
55497cff
PP
298#ifdef TWO_POT_OPTIMIZE
299 if (nbytes >= FIRST_BIG_BOUND) {
300 nbytes -= PERL_PAGESIZE;
301 }
302#endif
cf5c4ad8
PP
303 nbytes += M_OVERHEAD;
304 nbytes = (nbytes + 3) &~ 3;
305#ifdef PACK_MALLOC
306 } else if (nbytes == 0) {
307 nbytes = 1;
308 }
309#endif
8d063cd8
LW
310 shiftr = (nbytes - 1) >> 2;
311 /* apart from this loop, this is O(1) */
312 while (shiftr >>= 1)
313 bucket++;
314 /*
315 * If nothing in hash bucket right now,
316 * request more memory from the system.
317 */
318 if (nextf[bucket] == NULL)
319 morecore(bucket);
45d8adaa 320 if ((p = (union overhead *)nextf[bucket]) == NULL) {
55497cff 321#ifdef PERL_CORE
ee0007ab 322 if (!nomemok) {
760ac839 323 PerlIO_puts(PerlIO_stderr(),"Out of memory!\n");
79072805 324 my_exit(1);
ee0007ab 325 }
45d8adaa 326#else
8d063cd8 327 return (NULL);
45d8adaa
LW
328#endif
329 }
330
55497cff 331#ifdef PERL_CORE
760ac839 332 DEBUG_m(PerlIO_printf(Perl_debug_log, "0x%lx: (%05d) malloc %ld bytes\n",
a0d0e21e 333 (unsigned long)(p+1),an++,(long)size));
55497cff 334#endif /* PERL_CORE */
45d8adaa 335
8d063cd8 336 /* remove from linked list */
bf38876a
LW
337#ifdef RCHECK
338 if (*((int*)p) & (sizeof(union overhead) - 1))
760ac839 339 PerlIO_printf(PerlIO_stderr(), "Corrupt malloc ptr 0x%lx at 0x%lx\n",
a0d0e21e 340 (unsigned long)*((int*)p),(unsigned long)p);
bf38876a
LW
341#endif
342 nextf[bucket] = p->ov_next;
cf5c4ad8
PP
343 OV_MAGIC(p, bucket) = MAGIC;
344#ifndef PACK_MALLOC
345 OV_INDEX(p) = bucket;
346#endif
8d063cd8
LW
347#ifdef RCHECK
348 /*
349 * Record allocated size of block and
350 * bound space with magic numbers.
351 */
c2a5c2d2 352 nbytes = (size + M_OVERHEAD + 3) &~ 3;
8d063cd8
LW
353 if (nbytes <= 0x10000)
354 p->ov_size = nbytes - 1;
355 p->ov_rmagic = RMAGIC;
356 *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
357#endif
cf5c4ad8 358 return ((Malloc_t)(p + CHUNK_SHIFT));
8d063cd8
LW
359}
360
361/*
362 * Allocate more memory to the indicated bucket.
363 */
a0d0e21e 364static void
8d063cd8 365morecore(bucket)
a687059c 366 register int bucket;
8d063cd8
LW
367{
368 register union overhead *op;
369 register int rnu; /* 2^rnu bytes will be requested */
370 register int nblks; /* become nblks blocks of the desired size */
bbce6d69 371 register MEM_SIZE siz, needed;
cf5c4ad8 372 int slack = 0;
8d063cd8
LW
373
374 if (nextf[bucket])
375 return;
55497cff
PP
376 if (bucket == (sizeof(MEM_SIZE)*8 - 3)) {
377 croak("Allocation too large");
378 }
8d063cd8
LW
379 /*
380 * Insure memory is allocated
381 * on a page boundary. Should
382 * make getpageize call?
383 */
ee0007ab 384#ifndef atarist /* on the atari we dont have to worry about this */
8d063cd8 385 op = (union overhead *)sbrk(0);
cf5c4ad8
PP
386# ifndef I286
387# ifdef PACK_MALLOC
ff68c719
PP
388 if ((u_int)op & 0x7ff)
389 (void)sbrk(slack = 2048 - ((u_int)op & 0x7ff));
cf5c4ad8 390# else
ff68c719
PP
391 if ((u_int)op & 0x3ff)
392 (void)sbrk(slack = 1024 - ((u_int)op & 0x3ff));
cf5c4ad8 393# endif
5f05dabc 394# if defined(DEBUGGING_MSTATS)
cf5c4ad8
PP
395 sbrk_slack += slack;
396# endif
397# else
a687059c 398 /* The sbrk(0) call on the I286 always returns the next segment */
cf5c4ad8 399# endif
ee0007ab 400#endif /* atarist */
a687059c 401
ee0007ab 402#if !(defined(I286) || defined(atarist))
8d063cd8
LW
403 /* take 2k unless the block is bigger than that */
404 rnu = (bucket <= 8) ? 11 : bucket + 3;
a687059c
LW
405#else
406 /* take 16k unless the block is bigger than that
ee0007ab 407 (80286s like large segments!), probably good on the atari too */
a687059c
LW
408 rnu = (bucket <= 11) ? 14 : bucket + 3;
409#endif
8d063cd8 410 nblks = 1 << (rnu - (bucket + 3)); /* how many blocks to get */
bbce6d69 411 needed = (MEM_SIZE)1 << rnu;
55497cff 412#ifdef TWO_POT_OPTIMIZE
bbce6d69 413 needed += (bucket >= (FIRST_BIG_TWO_POT - 3) ? PERL_PAGESIZE : 0);
55497cff 414#endif
bbce6d69 415 op = (union overhead *)sbrk(needed);
8d063cd8 416 /* no more room! */
ff68c719
PP
417 if (op == (union overhead *)-1) {
418 op = (union overhead *)emergency_sbrk(needed);
419 if (op == (union overhead *)-1)
8d063cd8 420 return;
ff68c719 421 }
5f05dabc
PP
422#ifdef DEBUGGING_MSTATS
423 goodsbrk += needed;
424#endif
8d063cd8
LW
425 /*
426 * Round up to minimum allocation size boundary
427 * and deduct from block count to reflect.
428 */
a687059c 429#ifndef I286
cf5c4ad8 430# ifdef PACK_MALLOC
ff68c719 431 if ((u_int)op & 0x7ff)
cf5c4ad8
PP
432 croak("panic: Off-page sbrk");
433# endif
ff68c719 434 if ((u_int)op & 7) {
ee0007ab 435 op = (union overhead *)(((MEM_SIZE)op + 8) &~ 7);
8d063cd8
LW
436 nblks--;
437 }
a687059c
LW
438#else
439 /* Again, this should always be ok on an 80286 */
440#endif
8d063cd8
LW
441 /*
442 * Add new memory allocated to that on
443 * free list for this hash bucket.
444 */
8d063cd8 445 siz = 1 << (bucket + 3);
cf5c4ad8
PP
446#ifdef PACK_MALLOC
447 *(u_char*)op = bucket; /* Fill index. */
448 if (bucket <= MAX_PACKED - 3) {
449 op = (union overhead *) ((char*)op + blk_shift[bucket]);
450 nblks = n_blks[bucket];
451# ifdef DEBUGGING_MSTATS
452 start_slack += blk_shift[bucket];
453# endif
454 } else if (bucket <= 11 - 1 - 3) {
455 op = (union overhead *) ((char*)op + blk_shift[bucket]);
456 /* nblks = n_blks[bucket]; */
457 siz -= sizeof(union overhead);
458 } else op++; /* One chunk per block. */
459#endif /* !PACK_MALLOC */
460 nextf[bucket] = op;
5f05dabc
PP
461#ifdef DEBUGGING_MSTATS
462 nmalloc[bucket] += nblks;
463#endif
8d063cd8
LW
464 while (--nblks > 0) {
465 op->ov_next = (union overhead *)((caddr_t)op + siz);
466 op = (union overhead *)((caddr_t)op + siz);
467 }
8595d6f1 468 /* Not all sbrks return zeroed memory.*/
cf5c4ad8 469 op->ov_next = (union overhead *)NULL;
cf5c4ad8
PP
470#ifdef PACK_MALLOC
471 if (bucket == 7 - 3) { /* Special case, explanation is above. */
472 union overhead *n_op = nextf[7 - 3]->ov_next;
473 nextf[7 - 3] = (union overhead *)((caddr_t)nextf[7 - 3]
474 - sizeof(union overhead));
475 nextf[7 - 3]->ov_next = n_op;
476 }
477#endif /* !PACK_MALLOC */
8d063cd8
LW
478}
479
94b6baf5 480Free_t
352d5a3a 481free(mp)
2304df62 482 Malloc_t mp;
8d063cd8 483{
ee0007ab 484 register MEM_SIZE size;
8d063cd8 485 register union overhead *op;
352d5a3a 486 char *cp = (char*)mp;
cf5c4ad8
PP
487#ifdef PACK_MALLOC
488 u_char bucket;
489#endif
8d063cd8 490
55497cff 491#ifdef PERL_CORE
760ac839 492 DEBUG_m(PerlIO_printf(Perl_debug_log, "0x%lx: (%05d) free\n",(unsigned long)cp,an++));
55497cff 493#endif /* PERL_CORE */
45d8adaa 494
cf5c4ad8
PP
495 if (cp == NULL)
496 return;
497 op = (union overhead *)((caddr_t)cp
498 - sizeof (union overhead) * CHUNK_SHIFT);
499#ifdef PACK_MALLOC
500 bucket = OV_INDEX(op);
501#endif
760ac839 502#ifdef DEBUGGING
cf5c4ad8 503 ASSERT(OV_MAGIC(op, bucket) == MAGIC); /* make sure it was in use */
8d063cd8 504#else
cf5c4ad8
PP
505 if (OV_MAGIC(op, bucket) != MAGIC) {
506 static bad_free_warn = -1;
507 if (bad_free_warn == -1) {
508 char *pbf = getenv("PERL_BADFREE");
509 bad_free_warn = (pbf) ? atoi(pbf) : 1;
510 }
511 if (!bad_free_warn)
512 return;
8990e307 513#ifdef RCHECK
a687059c 514 warn("%s free() ignored",
8990e307
LW
515 op->ov_rmagic == RMAGIC - 1 ? "Duplicate" : "Bad");
516#else
517 warn("Bad free() ignored");
518#endif
8d063cd8 519 return; /* sanity */
378cc40b 520 }
8d063cd8
LW
521#endif
522#ifdef RCHECK
523 ASSERT(op->ov_rmagic == RMAGIC);
c2a5c2d2 524 if (OV_INDEX(op) <= MAX_SHORT_BUCKET)
8d063cd8 525 ASSERT(*(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC);
8990e307 526 op->ov_rmagic = RMAGIC - 1;
8d063cd8 527#endif
cf5c4ad8
PP
528 ASSERT(OV_INDEX(op) < NBUCKETS);
529 size = OV_INDEX(op);
8d063cd8
LW
530 op->ov_next = nextf[size];
531 nextf[size] = op;
8d063cd8
LW
532}
533
534/*
535 * When a program attempts "storage compaction" as mentioned in the
536 * old malloc man page, it realloc's an already freed block. Usually
537 * this is the last block it freed; occasionally it might be farther
538 * back. We have to search all the free lists for the block in order
539 * to determine its bucket: 1st we make one pass thru the lists
540 * checking only the first block in each; if that fails we search
378cc40b 541 * ``reall_srchlen'' blocks in each list for a match (the variable
8d063cd8
LW
542 * is extern so the caller can modify it). If that fails we just copy
543 * however many bytes was given to realloc() and hope it's not huge.
544 */
378cc40b 545int reall_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */
8d063cd8 546
2304df62 547Malloc_t
352d5a3a 548realloc(mp, nbytes)
2304df62 549 Malloc_t mp;
ee0007ab 550 MEM_SIZE nbytes;
8d063cd8 551{
ee0007ab 552 register MEM_SIZE onb;
8d063cd8
LW
553 union overhead *op;
554 char *res;
555 register int i;
556 int was_alloced = 0;
352d5a3a 557 char *cp = (char*)mp;
8d063cd8 558
55497cff 559#ifdef PERL_CORE
45d8adaa 560#ifdef DEBUGGING
ee0007ab 561 MEM_SIZE size = nbytes;
45d8adaa
LW
562#endif
563
55497cff 564#ifdef HAS_64K_LIMIT
45d8adaa 565 if (nbytes > 0xffff) {
760ac839 566 PerlIO_printf(PerlIO_stderr(), "Reallocation too large: %lx\n", size);
79072805 567 my_exit(1);
45d8adaa 568 }
55497cff 569#endif /* HAS_64K_LIMIT */
45d8adaa 570 if (!cp)
ee0007ab 571 return malloc(nbytes);
45d8adaa
LW
572#ifdef DEBUGGING
573 if ((long)nbytes < 0)
463ee0b2 574 croak("panic: realloc");
45d8adaa 575#endif
55497cff 576#endif /* PERL_CORE */
45d8adaa 577
cf5c4ad8
PP
578 op = (union overhead *)((caddr_t)cp
579 - sizeof (union overhead) * CHUNK_SHIFT);
580 i = OV_INDEX(op);
581 if (OV_MAGIC(op, i) == MAGIC) {
55497cff 582 was_alloced = 1;
8d063cd8
LW
583 } else {
584 /*
585 * Already free, doing "compaction".
586 *
587 * Search for the old block of memory on the
588 * free list. First, check the most common
589 * case (last element free'd), then (this failing)
378cc40b 590 * the last ``reall_srchlen'' items free'd.
8d063cd8
LW
591 * If all lookups fail, then assume the size of
592 * the memory block being realloc'd is the
593 * smallest possible.
594 */
595 if ((i = findbucket(op, 1)) < 0 &&
378cc40b 596 (i = findbucket(op, reall_srchlen)) < 0)
8d063cd8
LW
597 i = 0;
598 }
cf5c4ad8
PP
599 onb = (1L << (i + 3)) -
600#ifdef PACK_MALLOC
601 (i <= (MAX_PACKED - 3) ? 0 : M_OVERHEAD)
602#else
603 M_OVERHEAD
604#endif
55497cff
PP
605#ifdef TWO_POT_OPTIMIZE
606 + (i >= (FIRST_BIG_TWO_POT - 3) ? PERL_PAGESIZE : 0)
607#endif
cf5c4ad8 608 ;
55497cff
PP
609 /*
610 * avoid the copy if same size block.
611 * We are not agressive with boundary cases. Note that it is
612 * possible for small number of cases give false negative if
613 * both new size and old one are in the bucket for
614 * FIRST_BIG_TWO_POT, but the new one is near the lower end.
615 */
8d063cd8 616 if (was_alloced &&
55497cff
PP
617 nbytes <= onb && (nbytes > ( (onb >> 1) - M_OVERHEAD )
618#ifdef TWO_POT_OPTIMIZE
619 || (i == (FIRST_BIG_TWO_POT - 3)
620 && nbytes >= LAST_SMALL_BOUND )
621#endif
622 )) {
a687059c
LW
623#ifdef RCHECK
624 /*
625 * Record new allocated size of block and
626 * bound space with magic numbers.
627 */
c2a5c2d2 628 if (OV_INDEX(op) <= MAX_SHORT_BUCKET) {
a687059c
LW
629 /*
630 * Convert amount of memory requested into
631 * closest block size stored in hash buckets
632 * which satisfies request. Account for
633 * space used per block for accounting.
634 */
cf5c4ad8 635 nbytes += M_OVERHEAD;
a687059c
LW
636 nbytes = (nbytes + 3) &~ 3;
637 op->ov_size = nbytes - 1;
638 *((u_int *)((caddr_t)op + nbytes - RSLOP)) = RMAGIC;
639 }
640#endif
45d8adaa 641 res = cp;
a687059c 642 }
45d8adaa
LW
643 else {
644 if ((res = (char*)malloc(nbytes)) == NULL)
645 return (NULL);
646 if (cp != res) /* common optimization */
ee0007ab 647 Copy(cp, res, (MEM_SIZE)(nbytes<onb?nbytes:onb), char);
45d8adaa
LW
648 if (was_alloced)
649 free(cp);
650 }
651
55497cff 652#ifdef PERL_CORE
45d8adaa 653#ifdef DEBUGGING
a0d0e21e 654 if (debug & 128) {
760ac839
LW
655 PerlIO_printf(PerlIO_stderr(), "0x%lx: (%05d) rfree\n",(unsigned long)res,an++);
656 PerlIO_printf(PerlIO_stderr(), "0x%lx: (%05d) realloc %ld bytes\n",
a0d0e21e
LW
657 (unsigned long)res,an++,(long)size);
658 }
45d8adaa 659#endif
55497cff 660#endif /* PERL_CORE */
2304df62 661 return ((Malloc_t)res);
8d063cd8
LW
662}
663
664/*
665 * Search ``srchlen'' elements of each free list for a block whose
666 * header starts at ``freep''. If srchlen is -1 search the whole list.
667 * Return bucket number, or -1 if not found.
668 */
ee0007ab 669static int
8d063cd8
LW
670findbucket(freep, srchlen)
671 union overhead *freep;
672 int srchlen;
673{
674 register union overhead *p;
675 register int i, j;
676
677 for (i = 0; i < NBUCKETS; i++) {
678 j = 0;
679 for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
680 if (p == freep)
681 return (i);
682 j++;
683 }
684 }
685 return (-1);
686}
687
cf5c4ad8
PP
688Malloc_t
689calloc(elements, size)
690 register MEM_SIZE elements;
691 register MEM_SIZE size;
692{
693 long sz = elements * size;
694 Malloc_t p = malloc(sz);
695
696 if (p) {
697 memset((void*)p, 0, sz);
698 }
699 return p;
700}
701
c07a80fd 702#ifdef DEBUGGING_MSTATS
8d063cd8
LW
703/*
704 * mstats - print out statistics about malloc
705 *
706 * Prints two lines of numbers, one showing the length of the free list
707 * for each size category, the second showing the number of mallocs -
708 * frees for each size category.
709 */
ee0007ab 710void
c07a80fd 711dump_mstats(s)
8d063cd8
LW
712 char *s;
713{
714 register int i, j;
715 register union overhead *p;
5f05dabc 716 int topbucket=0, totfree=0, total=0;
c07a80fd 717 u_int nfree[NBUCKETS];
8d063cd8 718
c07a80fd 719 for (i=0; i < NBUCKETS; i++) {
8d063cd8
LW
720 for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
721 ;
c07a80fd
PP
722 nfree[i] = j;
723 totfree += nfree[i] * (1 << (i + 3));
5f05dabc
PP
724 total += nmalloc[i] * (1 << (i + 3));
725 if (nmalloc[i])
c07a80fd
PP
726 topbucket = i;
727 }
728 if (s)
760ac839 729 PerlIO_printf(PerlIO_stderr(), "Memory allocation statistics %s (buckets 8..%d)\n",
c07a80fd 730 s, (1 << (topbucket + 3)) );
5f05dabc 731 PerlIO_printf(PerlIO_stderr(), "%8d free:", totfree);
c07a80fd 732 for (i=0; i <= topbucket; i++) {
5f05dabc 733 PerlIO_printf(PerlIO_stderr(), (i<5 || i==7)?" %5d": (i<9)?" %3d":" %d", nfree[i]);
8d063cd8 734 }
5f05dabc 735 PerlIO_printf(PerlIO_stderr(), "\n%8d used:", total - totfree);
c07a80fd 736 for (i=0; i <= topbucket; i++) {
5f05dabc 737 PerlIO_printf(PerlIO_stderr(), (i<5 || i==7)?" %5d": (i<9)?" %3d":" %d", nmalloc[i] - nfree[i]);
c07a80fd 738 }
5f05dabc
PP
739 PerlIO_printf(PerlIO_stderr(), "\nTotal sbrk(): %8d. Odd ends: sbrk(): %7d, malloc(): %7d bytes.\n",
740 goodsbrk + sbrk_slack, sbrk_slack, start_slack);
c07a80fd
PP
741}
742#else
743void
744dump_mstats(s)
745 char *s;
746{
8d063cd8
LW
747}
748#endif
a687059c 749#endif /* lint */
cf5c4ad8
PP
750
751
752#ifdef USE_PERL_SBRK
753
760ac839
LW
754# ifdef NeXT
755# define PERL_SBRK_VIA_MALLOC
756# endif
757
758# ifdef PERL_SBRK_VIA_MALLOC
72e5b9db 759# if defined(HIDEMYMALLOC) || defined(EMBEDMYMALLOC)
760ac839
LW
760# undef malloc
761# else
72e5b9db 762# include "Error: -DPERL_SBRK_VIA_MALLOC needs -D(HIDE|EMBED)MYMALLOC"
760ac839 763# endif
cf5c4ad8
PP
764
765/* it may seem schizophrenic to use perl's malloc and let it call system */
766/* malloc, the reason for that is only the 3.2 version of the OS that had */
767/* frequent core dumps within nxzonefreenolock. This sbrk routine put an */
768/* end to the cores */
769
760ac839 770# define SYSTEM_ALLOC(a) malloc(a)
cf5c4ad8 771
760ac839 772# endif /* PERL_SBRK_VIA_MALLOC */
cf5c4ad8
PP
773
774static IV Perl_sbrk_oldchunk;
775static long Perl_sbrk_oldsize;
776
760ac839
LW
777# define PERLSBRK_32_K (1<<15)
778# define PERLSBRK_64_K (1<<16)
cf5c4ad8
PP
779
780char *
781Perl_sbrk(size)
782int size;
783{
784 IV got;
785 int small, reqsize;
786
787 if (!size) return 0;
55497cff 788#ifdef PERL_CORE
cf5c4ad8
PP
789 reqsize = size; /* just for the DEBUG_m statement */
790#endif
791 if (size <= Perl_sbrk_oldsize) {
792 got = Perl_sbrk_oldchunk;
793 Perl_sbrk_oldchunk += size;
794 Perl_sbrk_oldsize -= size;
795 } else {
796 if (size >= PERLSBRK_32_K) {
797 small = 0;
798 } else {
55497cff 799#ifndef PERL_CORE
cf5c4ad8
PP
800 reqsize = size;
801#endif
802 size = PERLSBRK_64_K;
803 small = 1;
804 }
805 got = (IV)SYSTEM_ALLOC(size);
806 if (small) {
807 /* Chunk is small, register the rest for future allocs. */
808 Perl_sbrk_oldchunk = got + reqsize;
809 Perl_sbrk_oldsize = size - reqsize;
810 }
811 }
812
55497cff 813#ifdef PERL_CORE
760ac839 814 DEBUG_m(PerlIO_printf(PerlIO_stderr(), "sbrk malloc size %ld (reqsize %ld), left size %ld, give addr 0x%lx\n",
cf5c4ad8
PP
815 size, reqsize, Perl_sbrk_oldsize, got));
816#endif
817
818 return (void *)got;
819}
820
821#endif /* ! defined USE_PERL_SBRK */