]>
Commit | Line | Data |
---|---|---|
cce855bc | 1 | /* malloc.c - dynamic memory allocation for bash. */ |
726f6388 | 2 | |
cce855bc | 3 | /* Copyright (C) 1985, 1987, 1997 Free Software Foundation, Inc. |
726f6388 JA |
4 | |
5 | This program is free software; you can redistribute it and/or modify | |
6 | it under the terms of the GNU General Public License as published by | |
7 | the Free Software Foundation; either version 1, or (at your option) | |
8 | any later version. | |
9 | ||
10 | This program is distributed in the hope that it will be useful, | |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
13 | GNU General Public License for more details. | |
14 | ||
15 | You should have received a copy of the GNU General Public License | |
16 | along with this program; if not, write to the Free Software | |
17 | Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. | |
18 | ||
19 | In other words, you are welcome to use, share and improve this program. | |
20 | You are forbidden to forbid anyone else to use, share and improve | |
21 | what you give them. Help stamp out software-hoarding! */ | |
22 | ||
23 | /* | |
24 | * @(#)nmalloc.c 1 (Caltech) 2/21/82 | |
25 | * | |
26 | * U of M Modified: 20 Jun 1983 ACT: strange hacks for Emacs | |
27 | * | |
28 | * Nov 1983, Mike@BRL, Added support for 4.1C/4.2 BSD. | |
29 | * | |
30 | * This is a very fast storage allocator. It allocates blocks of a small | |
31 | * number of different sizes, and keeps free lists of each size. Blocks | |
32 | * that don't exactly fit are passed up to the next larger size. In this | |
33 | * implementation, the available sizes are (2^n)-4 (or -16) bytes long. | |
34 | * This is designed for use in a program that uses vast quantities of | |
35 | * memory, but bombs when it runs out. To make it a little better, it | |
36 | * warns the user when he starts to get near the end. | |
37 | * | |
38 | * June 84, ACT: modified rcheck code to check the range given to malloc, | |
39 | * rather than the range determined by the 2-power used. | |
40 | * | |
41 | * Jan 85, RMS: calls malloc_warning to issue warning on nearly full. | |
42 | * No longer Emacs-specific; can serve as all-purpose malloc for GNU. | |
43 | * You should call malloc_init to reinitialize after loading dumped Emacs. | |
cce855bc | 44 | * Call malloc_stats to get info on memory stats if MALLOC_STATS turned on. |
726f6388 JA |
45 | * realloc knows how to return same block given, just changing its size, |
46 | * if the power of 2 is correct. | |
47 | */ | |
cce855bc | 48 | #define MALLOC_STATS /* for the time being */ |
726f6388 JA |
49 | |
50 | /* | |
51 | * nextf[i] is the pointer to the next free block of size 2^(i+3). The | |
52 | * smallest allocatable block is 8 bytes. The overhead information will | |
53 | * go in the first int of the block, and the returned pointer will point | |
54 | * to the second. | |
726f6388 JA |
55 | */ |
56 | ||
ccc6cda3 JA |
57 | /* Define this to have free() write 0xcf into memory as it's freed, to |
58 | uncover callers that refer to freed memory. */ | |
59 | /* SCO 3.2v4 getcwd and possibly other libc routines fail with MEMSCRAMBLE */ | |
60 | #if !defined (NO_MEMSCRAMBLE) | |
61 | # define MEMSCRAMBLE | |
62 | #endif | |
63 | ||
cce855bc | 64 | #if defined (HAVE_CONFIG_H) |
ccc6cda3 | 65 | # include <config.h> |
cce855bc JA |
66 | #endif /* HAVE_CONFIG_H */ |
67 | ||
68 | #if defined (SHELL) | |
69 | # include "bashtypes.h" | |
70 | #else | |
71 | # include <sys/types.h> | |
72 | #endif | |
726f6388 | 73 | |
ccc6cda3 JA |
74 | #if defined (HAVE_UNISTD_H) |
75 | # include <unistd.h> | |
76 | #endif | |
726f6388 JA |
77 | |
78 | /* Determine which kind of system this is. */ | |
cce855bc JA |
79 | #include <signal.h> |
80 | ||
81 | #if defined (HAVE_STRING_H) | |
82 | # include <string.h> | |
d166f048 | 83 | #else |
cce855bc | 84 | # include <strings.h> |
d166f048 | 85 | #endif |
cce855bc JA |
86 | |
87 | #if defined (MALLOC_STATS) || !defined (botch) | |
88 | # include <stdio.h> | |
89 | #endif /* MALLOC_STATS || !botch */ | |
726f6388 | 90 | |
ccc6cda3 JA |
91 | /* Define getpagesize () if the system does not. */ |
92 | #ifndef HAVE_GETPAGESIZE | |
726f6388 JA |
93 | # include "getpagesize.h" |
94 | #endif | |
95 | ||
d166f048 JA |
96 | #if __GNUC__ > 1 |
97 | # define FASTCOPY(s, d, n) __builtin_memcpy (d, s, n) | |
98 | #else /* !__GNUC__ */ | |
99 | # if !defined (HAVE_BCOPY) | |
100 | # if !defined (HAVE_MEMMOVE) | |
101 | # define FASTCOPY(s, d, n) memcpy (d, s, n) | |
102 | # else | |
103 | # define FASTCOPY(s, d, n) memmove (d, s, n) | |
104 | # endif /* !HAVE_MEMMOVE */ | |
105 | # else /* HAVE_BCOPY */ | |
106 | # define FASTCOPY(s, d, n) bcopy (s, d, n) | |
107 | # endif /* HAVE_BCOPY */ | |
108 | #endif /* !__GNUC__ */ | |
109 | ||
ccc6cda3 JA |
110 | #if !defined (NULL) |
111 | # define NULL 0 | |
112 | #endif | |
113 | ||
cce855bc | 114 | #define NBUCKETS 30 |
726f6388 JA |
115 | |
116 | #define ISALLOC ((char) 0xf7) /* magic byte that implies allocation */ | |
117 | #define ISFREE ((char) 0x54) /* magic byte that implies free block */ | |
118 | /* this is for error checking only */ | |
119 | #define ISMEMALIGN ((char) 0xd6) /* Stored before the value returned by | |
120 | memalign, with the rest of the word | |
121 | being the distance to the true | |
122 | beginning of the block. */ | |
726f6388 | 123 | |
ccc6cda3 | 124 | #if !defined (SBRK_DECLARED) |
726f6388 | 125 | extern char *sbrk (); |
ccc6cda3 | 126 | #endif /* !SBRK_DECLARED */ |
726f6388 | 127 | |
cce855bc JA |
128 | #ifdef MALLOC_STATS |
129 | /* | |
130 | * NMALLOC[i] is the difference between the number of mallocs and frees | |
131 | * for a given block size. TMALLOC[i] is the total number of mallocs for | |
132 | * a given block size. NMORECORE[i] is the total number of calls to | |
133 | * morecore(i). NMAL and NFRE are counts of the number of calls to malloc() | |
134 | * and free(), respectively. NREALLOC is the total number of calls to | |
135 | * realloc(); NRCOPY is the number of times realloc() had to allocate new | |
136 | * memory and copy to it. NRECURSE is a count of the number of recursive | |
137 | * calls to malloc() for the same bucket size, which can be caused by calls | |
138 | * to malloc() from a signal handler. NSBRK is the number of calls to sbrk() | |
139 | * (whether by morecore() or for alignment); TSBRK is the total number of | |
140 | * bytes requested from the kernel with sbrk(). BYTESUSED is the total | |
141 | * number of bytes consumed by blocks currently in use; BYTESFREE is the | |
142 | * total number of bytes currently on all of the free lists. NBSPLIT is | |
143 | * the number of times a larger block was split to satisfy a smaller request. | |
144 | * NBCOALESCE is the number of times two adjacent smaller blocks off the free | |
145 | * list were combined to satisfy a larger request. | |
146 | */ | |
147 | struct _malstats { | |
148 | int nmalloc[NBUCKETS]; | |
149 | int tmalloc[NBUCKETS]; | |
150 | int nmorecore[NBUCKETS]; | |
151 | int nmal; | |
152 | int nfre; | |
153 | int nrealloc; | |
154 | int nrcopy; | |
155 | int nrecurse; | |
156 | int nsbrk; | |
157 | int32_t tsbrk; | |
158 | int32_t bytesused; | |
159 | int32_t bytesfree; | |
160 | int nbsplit; | |
161 | int nbcoalesce; | |
162 | }; | |
163 | ||
164 | static struct _malstats _mstats; | |
165 | ||
166 | /* Return statistics describing allocation of blocks of size BLOCKSIZE. | |
167 | NFREE is the number of free blocks for this allocation size. NUSED | |
168 | is the number of blocks in use. NMAL is the number of requests for | |
169 | blocks of size BLOCKSIZE. NMORECORE is the number of times we had | |
170 | to call MORECORE to repopulate the free list for this bucket. */ | |
171 | struct bucket_stats { | |
172 | u_int32_t blocksize; | |
173 | int nfree; | |
174 | int nused; | |
175 | int nmal; | |
176 | int nmorecore; | |
177 | }; | |
178 | #endif /* MALLOC_STATS */ | |
179 | ||
180 | /* We have a flag indicating whether memory is allocated, an index in | |
181 | nextf[], a size field, and a sentinel value to determine whether or | |
182 | not a caller wrote before the start of allocated memory; to realloc() | |
183 | memory we either copy mh_nbytes or just change mh_nbytes if there is | |
184 | enough room in the block for the new size. Range checking is always | |
185 | done. */ | |
186 | union mhead { | |
b72432fd | 187 | bits64_t mh_align; /* 8 */ |
cce855bc JA |
188 | struct { |
189 | char mi_alloc; /* ISALLOC or ISFREE */ /* 1 */ | |
190 | char mi_index; /* index in nextf[] */ /* 1 */ | |
191 | /* Remainder are valid only when block is allocated */ | |
192 | u_int32_t mi_nbytes; /* # of bytes allocated */ /* 4 */ | |
193 | unsigned short mi_magic2;/* should be == MAGIC2 */ /* 2 */ | |
194 | } minfo; | |
726f6388 | 195 | }; |
cce855bc JA |
196 | #define mh_alloc minfo.mi_alloc |
197 | #define mh_index minfo.mi_index | |
198 | #define mh_nbytes minfo.mi_nbytes | |
199 | #define mh_magic2 minfo.mi_magic2 | |
726f6388 JA |
200 | |
201 | /* Access free-list pointer of a block. | |
cce855bc | 202 | It is stored at block + sizeof (char *). |
b72432fd JA |
203 | This is not a field in the minfo structure member of union mhead |
204 | because we want sizeof (union mhead) | |
cce855bc JA |
205 | to describe the overhead for when the block is in use, |
206 | and we do not want the free-list pointer to count in that. */ | |
726f6388 JA |
207 | |
208 | #define CHAIN(a) \ | |
cce855bc | 209 | (*(union mhead **) (sizeof (char *) + (char *) (a))) |
726f6388 | 210 | |
cce855bc JA |
211 | #if defined (botch) |
212 | extern void botch (); | |
213 | #else | |
214 | static void | |
215 | botch (s) | |
216 | char *s; | |
217 | { | |
218 | fprintf (stderr, "\r\nmalloc: assertion botched: %s\r\n", s); | |
219 | (void)fflush (stderr); | |
220 | abort (); | |
221 | } | |
222 | #endif /* !botch */ | |
726f6388 | 223 | |
cce855bc JA |
224 | #if !defined (__STRING) |
225 | # if defined (__STDC__) | |
226 | # define __STRING(x) #x | |
227 | # else | |
228 | # define __STRING(x) "x" | |
726f6388 | 229 | # endif |
cce855bc | 230 | #endif /* !__STRING */ |
726f6388 | 231 | |
cce855bc JA |
232 | /* To implement range checking, we write magic values in at the beginning |
233 | and end of each allocated block, and make sure they are undisturbed | |
234 | whenever a free or a realloc occurs. */ | |
235 | ||
236 | /* Written in each of the 4 bytes following the block's real space */ | |
237 | #define MAGIC1 0x55 | |
238 | /* Written in the 2 bytes before the block's real space */ | |
239 | #define MAGIC2 0x5555 | |
240 | #define ASSERT(p) do { if (!(p)) botch(__STRING(p)); } while (0) | |
241 | #define MSLOP 4 /* 4 bytes extra for MAGIC1s */ | |
242 | ||
243 | /* Minimum and maximum bucket indices for block splitting (and to bound | |
244 | the search for a block to split). */ | |
245 | #define SPLIT_MIN 3 | |
246 | #define SPLIT_MID 9 | |
247 | #define SPLIT_MAX 12 | |
248 | ||
249 | /* Minimum and maximum bucket indices for block coalescing. */ | |
250 | #define COMBINE_MIN 6 | |
251 | #define COMBINE_MAX (pagebucket - 1) | |
252 | ||
253 | #define MIN_COMBINE_FREE 4 | |
726f6388 JA |
254 | |
255 | /* nextf[i] is free list of blocks of size 2**(i + 3) */ | |
256 | ||
cce855bc | 257 | static union mhead *nextf[NBUCKETS]; |
726f6388 JA |
258 | |
259 | /* busy[i] is nonzero while allocation of block size i is in progress. */ | |
260 | ||
cce855bc | 261 | static char busy[NBUCKETS]; |
726f6388 | 262 | |
cce855bc JA |
263 | static int pagesz; /* system page size. */ |
264 | static int pagebucket; /* bucket for requests a page in size */ | |
726f6388 | 265 | |
cce855bc JA |
266 | #if 0 |
267 | /* Coalesce two adjacent free blocks off the free list for size NU - 1, | |
268 | as long as there are at least MIN_COMBINE_FREE free blocks and we | |
269 | can find two adjacent free blocks. nextf[NU -1] is assumed to not | |
270 | be busy; the caller (morecore()) checks for this. */ | |
271 | static void | |
272 | bcoalesce (nu) | |
273 | register int nu; | |
274 | { | |
275 | register union mhead *mp, *mp1, *mp2; | |
276 | register int nfree, nbuck; | |
277 | unsigned long siz; | |
726f6388 | 278 | |
cce855bc JA |
279 | nbuck = nu - 1; |
280 | if (nextf[nbuck] == 0) | |
281 | return; | |
726f6388 | 282 | |
cce855bc JA |
283 | nfree = 1; |
284 | mp1 = nextf[nbuck]; | |
285 | mp = CHAIN (mp1); | |
286 | mp2 = (union mhead *)0; | |
287 | while (CHAIN (mp)) | |
288 | { | |
289 | mp2 = mp1; | |
290 | mp1 = mp; | |
291 | mp = CHAIN (mp); | |
292 | nfree++; | |
293 | /* We may not want to run all the way through the free list here; | |
294 | if we do not, we need to check a threshold value here and break | |
295 | if nfree exceeds it. */ | |
296 | } | |
297 | if (nfree < MIN_COMBINE_FREE) | |
298 | return; | |
299 | /* OK, now we have mp1 pointing to the block we want to add to nextf[NU]. | |
300 | CHAIN(mp2) must equal mp1. Check that mp1 and mp are adjacent. */ | |
301 | if (CHAIN(mp2) != mp1) | |
302 | botch ("bcoalesce: CHAIN(mp2) != mp1"); | |
303 | siz = 1 << (nbuck + 3); | |
304 | if (CHAIN (mp1) != (union mhead *)((char *)mp1 + siz)) | |
305 | return; /* not adjacent */ | |
306 | ||
307 | #ifdef MALLOC_STATS | |
308 | _mstats.nbcoalesce++; | |
309 | #endif | |
726f6388 | 310 | |
cce855bc JA |
311 | /* Since they are adjacent, remove them from the free list */ |
312 | CHAIN (mp2) = CHAIN (mp); | |
726f6388 | 313 | |
cce855bc JA |
314 | /* And add the combined two blocks to nextf[NU]. */ |
315 | mp1->mh_alloc = ISFREE; | |
316 | mp1->mh_index = nu; | |
317 | CHAIN (mp1) = nextf[nu]; | |
318 | nextf[nu] = mp1; | |
319 | } | |
320 | #endif | |
726f6388 | 321 | |
cce855bc JA |
322 | /* Split a block at index > NU (but less than SPLIT_MAX) into a set of |
323 | blocks of the correct size, and attach them to nextf[NU]. nextf[NU] | |
324 | is assumed to be empty. Must be called with signals blocked (e.g., | |
325 | by morecore()). */ | |
326 | static void | |
327 | bsplit (nu) | |
328 | register int nu; | |
726f6388 | 329 | { |
cce855bc JA |
330 | register union mhead *mp; |
331 | int nbuck, nblks; | |
332 | unsigned long siz; | |
726f6388 | 333 | |
cce855bc JA |
334 | if (nu >= SPLIT_MID) |
335 | { | |
336 | for (nbuck = SPLIT_MAX; nbuck > nu; nbuck--) | |
337 | { | |
338 | if (busy[nbuck] || nextf[nbuck] == 0) | |
339 | continue; | |
340 | break; | |
341 | } | |
342 | } | |
343 | else | |
344 | { | |
345 | for (nbuck = nu + 1; nbuck <= SPLIT_MAX; nbuck++) | |
346 | { | |
347 | if (busy[nbuck] || nextf[nbuck] == 0) | |
348 | continue; | |
349 | break; | |
350 | } | |
351 | } | |
726f6388 | 352 | |
cce855bc JA |
353 | if (nbuck > SPLIT_MAX || nbuck <= nu) |
354 | return; | |
355 | ||
356 | /* XXX might want to split only if nextf[nbuck] has >= 2 blocks free | |
357 | and nbuck is below some threshold. */ | |
358 | ||
359 | #ifdef MALLOC_STATS | |
360 | _mstats.nbsplit++; | |
361 | #endif | |
362 | ||
363 | /* Figure out how many blocks we'll get. */ | |
364 | siz = (1 << (nu + 3)); | |
365 | nblks = (1 << (nbuck + 3)) / siz; | |
726f6388 | 366 | |
cce855bc JA |
367 | /* Remove the block from the chain of larger blocks. */ |
368 | mp = nextf[nbuck]; | |
369 | nextf[nbuck] = CHAIN (mp); | |
370 | ||
371 | /* Split the block and put it on the requested chain. */ | |
372 | nextf[nu] = mp; | |
373 | while (1) | |
374 | { | |
375 | mp->mh_alloc = ISFREE; | |
376 | mp->mh_index = nu; | |
377 | if (--nblks <= 0) break; | |
378 | CHAIN (mp) = (union mhead *)((char *)mp + siz); | |
379 | mp = (union mhead *)((char *)mp + siz); | |
380 | } | |
381 | CHAIN (mp) = 0; | |
726f6388 | 382 | } |
ccc6cda3 | 383 | |
726f6388 JA |
384 | static void |
385 | morecore (nu) /* ask system for more memory */ | |
386 | register int nu; /* size index to get more of */ | |
387 | { | |
cce855bc | 388 | register union mhead *mp; |
726f6388 | 389 | register int nblks; |
cce855bc JA |
390 | register long siz; |
391 | long sbrk_amt; /* amount to get via sbrk() */ | |
726f6388 | 392 | |
ccc6cda3 JA |
393 | /* Block all signals in case we are executed from a signal handler. */ |
394 | #if defined (HAVE_BSD_SIGNALS) | |
395 | int oldmask; | |
726f6388 | 396 | oldmask = sigsetmask (-1); |
ccc6cda3 JA |
397 | #else |
398 | # if defined (HAVE_POSIX_SIGNALS) | |
399 | sigset_t set, oset; | |
400 | sigfillset (&set); | |
401 | sigemptyset (&oset); | |
402 | sigprocmask (SIG_BLOCK, &set, &oset); | |
403 | # endif /* HAVE_POSIX_SIGNALS */ | |
404 | #endif /* HAVE_BSD_SIGNALS */ | |
726f6388 | 405 | |
cce855bc JA |
406 | siz = 1 << (nu + 3); /* size of desired block for nextf[nu] */ |
407 | ||
408 | if (siz < 0) | |
409 | return; /* oops */ | |
410 | ||
411 | #ifdef MALLOC_STATS | |
412 | _mstats.nmorecore[nu]++; | |
413 | #endif | |
414 | ||
415 | /* Try to split a larger block here, if we're within the range of sizes | |
416 | to split. */ | |
417 | if (nu >= SPLIT_MIN && nu < SPLIT_MAX) | |
418 | { | |
419 | bsplit (nu); | |
420 | if (nextf[nu] != 0) | |
421 | goto morecore_done; | |
422 | } | |
423 | ||
424 | #if 0 | |
425 | /* Try to coalesce two adjacent blocks from the free list on nextf[nu - 1], | |
426 | if we can, and we're withing the range of the block coalescing limits. */ | |
427 | if (nu >= COMBINE_MIN && nu < COMBINE_MAX && busy[nu - 1] == 0 && nextf[nu - 1]) | |
428 | { | |
429 | bcoalesce (nu); | |
430 | if (nextf[nu] != 0) | |
431 | goto morecore_done; | |
432 | } | |
433 | #endif | |
434 | ||
435 | /* Take at least a page, and figure out how many blocks of the requested | |
436 | size we're getting. */ | |
437 | if (siz <= pagesz) | |
726f6388 | 438 | { |
cce855bc JA |
439 | sbrk_amt = pagesz; |
440 | nblks = sbrk_amt / siz; | |
726f6388 | 441 | } |
cce855bc JA |
442 | else |
443 | { | |
444 | /* We always want to request an integral multiple of the page size | |
445 | from the kernel, so let's compute whether or not `siz' is such | |
446 | an amount. If it is, we can just request it. If not, we want | |
447 | the smallest integral multiple of pagesize that is larger than | |
448 | `siz' and will satisfy the request. */ | |
449 | sbrk_amt = siz % pagesz; | |
450 | if (sbrk_amt == 0) | |
451 | sbrk_amt = siz; | |
452 | else | |
453 | sbrk_amt = siz + pagesz - sbrk_amt; | |
454 | nblks = 1; | |
455 | } | |
456 | ||
457 | #ifdef MALLOC_STATS | |
458 | _mstats.nsbrk++; | |
459 | _mstats.tsbrk += sbrk_amt; | |
460 | #endif | |
461 | ||
462 | mp = (union mhead *) sbrk (sbrk_amt); | |
726f6388 | 463 | |
cce855bc JA |
464 | /* Totally out of memory. */ |
465 | if ((long)mp == -1) | |
466 | return; | |
467 | ||
468 | /* shouldn't happen, but just in case -- require 8-byte alignment */ | |
469 | if ((long)mp & 7) | |
470 | { | |
471 | mp = (union mhead *) (((long)mp + 8) & ~7); | |
726f6388 JA |
472 | nblks--; |
473 | } | |
474 | ||
cce855bc JA |
475 | /* save new header and link the nblks blocks together */ |
476 | nextf[nu] = mp; | |
726f6388 JA |
477 | while (1) |
478 | { | |
cce855bc JA |
479 | mp->mh_alloc = ISFREE; |
480 | mp->mh_index = nu; | |
726f6388 | 481 | if (--nblks <= 0) break; |
cce855bc JA |
482 | CHAIN (mp) = (union mhead *)((char *)mp + siz); |
483 | mp = (union mhead *)((char *)mp + siz); | |
726f6388 | 484 | } |
cce855bc | 485 | CHAIN (mp) = 0; |
726f6388 | 486 | |
cce855bc | 487 | morecore_done: |
ccc6cda3 | 488 | #if defined (HAVE_BSD_SIGNALS) |
726f6388 | 489 | sigsetmask (oldmask); |
ccc6cda3 JA |
490 | #else |
491 | # if defined (HAVE_POSIX_SIGNALS) | |
492 | sigprocmask (SIG_SETMASK, &oset, (sigset_t *)NULL); | |
b72432fd JA |
493 | # else |
494 | ; /* nothing to do, but need a null statement before the brace */ | |
ccc6cda3 JA |
495 | # endif |
496 | #endif /* HAVE_BSD_SIGNALS */ | |
726f6388 JA |
497 | } |
498 | ||
ccc6cda3 JA |
499 | #if defined (MEMSCRAMBLE) || !defined (NO_CALLOC) |
500 | static char * | |
501 | zmemset (s, c, n) | |
502 | char *s; | |
503 | int c; | |
504 | register int n; | |
505 | { | |
506 | register char *sp; | |
507 | ||
508 | sp = s; | |
509 | while (--n >= 0) | |
510 | *sp++ = c; | |
511 | return (s); | |
512 | } | |
513 | #endif /* MEMSCRAMBLE || !NO_CALLOC */ | |
514 | ||
cce855bc JA |
515 | static void |
516 | malloc_debug_dummy () | |
517 | { | |
518 | ; | |
519 | } | |
520 | ||
726f6388 JA |
521 | char * |
522 | malloc (n) /* get a block */ | |
cce855bc | 523 | size_t n; |
726f6388 | 524 | { |
cce855bc JA |
525 | register union mhead *p; |
526 | register long nbytes; | |
527 | register int nunits; | |
726f6388 | 528 | |
cce855bc JA |
529 | /* Get the system page size and align break pointer so everything will |
530 | be page-aligned. The page size must be at least 1K -- anything | |
531 | smaller is increased. */ | |
532 | if (pagesz == 0) | |
533 | { | |
534 | register long sbrk_needed; | |
535 | ||
536 | pagesz = getpagesize (); | |
537 | if (pagesz < 1024) | |
538 | pagesz = 1024; | |
539 | /* OK, how much do we need to allocate to make things page-aligned? | |
540 | This partial page is wasted space. Once we figure out how much | |
541 | to advance the break pointer, go ahead and do it. */ | |
542 | sbrk_needed = pagesz - ((long)sbrk (0) & (pagesz - 1)); /* sbrk(0) % pagesz */ | |
543 | if (sbrk_needed < 0) | |
544 | sbrk_needed += pagesz; | |
545 | /* Now allocate the wasted space. */ | |
546 | if (sbrk_needed) | |
547 | { | |
548 | #ifdef MALLOC_STATS | |
549 | _mstats.nsbrk++; | |
550 | _mstats.tsbrk += sbrk_needed; | |
551 | #endif | |
552 | if ((long)sbrk (sbrk_needed) == -1) | |
553 | return (NULL); | |
554 | } | |
555 | nunits = 0; | |
556 | nbytes = 8; | |
557 | while (pagesz > nbytes) | |
558 | { | |
559 | nbytes <<= 1; | |
560 | nunits++; | |
561 | } | |
562 | pagebucket = nunits; | |
563 | } | |
564 | ||
726f6388 | 565 | /* Figure out how many bytes are required, rounding up to the nearest |
cce855bc JA |
566 | multiple of 4, then figure out which nextf[] area to use. Try to |
567 | be smart about where to start searching -- if the number of bytes | |
568 | needed is greater than the page size, we can start at pagebucket. */ | |
569 | nbytes = (n + sizeof *p + MSLOP + 3) & ~3; | |
570 | nunits = 0; | |
571 | if (nbytes <= (pagesz >> 1)) | |
572 | { | |
573 | register unsigned int shiftr; | |
726f6388 | 574 | |
cce855bc JA |
575 | shiftr = (nbytes - 1) >> 2; /* == (nbytes - 1) / 4 */ |
576 | while (shiftr >>= 1) /* == (nbytes - 1) / {8,16,32,...} */ | |
577 | nunits++; | |
578 | } | |
579 | else | |
580 | { | |
581 | register u_int32_t amt; | |
582 | ||
583 | nunits = pagebucket; | |
584 | amt = pagesz; | |
585 | while (nbytes > amt) | |
586 | { | |
587 | amt <<= 1; | |
588 | nunits++; | |
589 | } | |
590 | } | |
726f6388 JA |
591 | |
592 | /* In case this is reentrant use of malloc from signal handler, | |
593 | pick a block size that no other malloc level is currently | |
594 | trying to allocate. That's the easiest harmless way not to | |
595 | interfere with the other level of execution. */ | |
cce855bc JA |
596 | #ifdef MALLOC_STATS |
597 | if (busy[nunits]) _mstats.nrecurse++; | |
598 | #endif | |
726f6388 JA |
599 | while (busy[nunits]) nunits++; |
600 | busy[nunits] = 1; | |
601 | ||
602 | /* If there are no blocks of the appropriate size, go get some */ | |
726f6388 JA |
603 | if (nextf[nunits] == 0) |
604 | morecore (nunits); | |
605 | ||
606 | /* Get one block off the list, and set the new list head */ | |
cce855bc | 607 | if ((p = nextf[nunits]) == NULL) |
726f6388 JA |
608 | { |
609 | busy[nunits] = 0; | |
cce855bc | 610 | return NULL; |
726f6388 JA |
611 | } |
612 | nextf[nunits] = CHAIN (p); | |
613 | busy[nunits] = 0; | |
614 | ||
615 | /* Check for free block clobbered */ | |
cce855bc JA |
616 | /* If not for this check, we would gobble a clobbered free chain ptr |
617 | and bomb out on the NEXT allocate of this size block */ | |
618 | if (p->mh_alloc != ISFREE || p->mh_index != nunits) | |
619 | botch ("malloc: block on free list clobbered"); | |
726f6388 JA |
620 | |
621 | /* Fill in the info, and if range checking, set up the magic numbers */ | |
cce855bc JA |
622 | p->mh_alloc = ISALLOC; |
623 | p->mh_nbytes = n; | |
624 | p->mh_magic2 = MAGIC2; | |
726f6388 JA |
625 | { |
626 | register char *m = (char *) (p + 1) + n; | |
627 | ||
628 | *m++ = MAGIC1, *m++ = MAGIC1, *m++ = MAGIC1, *m = MAGIC1; | |
629 | } | |
cce855bc | 630 | |
ccc6cda3 JA |
631 | #ifdef MEMSCRAMBLE |
632 | zmemset ((char *)(p + 1), 0xdf, n); /* scramble previous contents */ | |
633 | #endif | |
cce855bc JA |
634 | #ifdef MALLOC_STATS |
635 | _mstats.nmalloc[nunits]++; | |
636 | _mstats.tmalloc[nunits]++; | |
637 | _mstats.nmal++; | |
638 | #endif /* MALLOC_STATS */ | |
726f6388 JA |
639 | return (char *) (p + 1); |
640 | } | |
641 | ||
642 | void | |
643 | free (mem) | |
644 | char *mem; | |
645 | { | |
cce855bc JA |
646 | register union mhead *p; |
647 | register char *ap; | |
648 | register int nunits; | |
649 | ||
650 | if ((ap = mem) == 0) | |
651 | return; | |
726f6388 | 652 | |
cce855bc | 653 | p = (union mhead *) ap - 1; |
726f6388 | 654 | |
cce855bc JA |
655 | if (p->mh_alloc == ISMEMALIGN) |
656 | { | |
657 | ap -= p->mh_nbytes; | |
658 | p = (union mhead *) ap - 1; | |
659 | } | |
660 | ||
661 | if (p->mh_alloc != ISALLOC) | |
662 | { | |
663 | if (p->mh_alloc == ISFREE) | |
664 | botch ("free: called with already freed block argument"); | |
665 | else | |
666 | botch ("free: called with unallocated block argument"); | |
667 | } | |
668 | ||
669 | ASSERT (p->mh_magic2 == MAGIC2); | |
670 | ap += p->mh_nbytes; | |
671 | ASSERT (*ap++ == MAGIC1); ASSERT (*ap++ == MAGIC1); | |
672 | ASSERT (*ap++ == MAGIC1); ASSERT (*ap == MAGIC1); | |
726f6388 | 673 | |
ccc6cda3 | 674 | #ifdef MEMSCRAMBLE |
cce855bc | 675 | zmemset (mem, 0xcf, p->mh_nbytes); |
ccc6cda3 | 676 | #endif |
cce855bc JA |
677 | |
678 | nunits = p->mh_index; | |
679 | ||
680 | ASSERT (nunits < NBUCKETS); | |
681 | p->mh_alloc = ISFREE; | |
682 | ||
683 | /* Protect against signal handlers calling malloc. */ | |
684 | busy[nunits] = 1; | |
685 | /* Put this block on the free list. */ | |
686 | CHAIN (p) = nextf[nunits]; | |
687 | nextf[nunits] = p; | |
688 | busy[nunits] = 0; | |
689 | ||
690 | #ifdef MALLOC_STATS | |
691 | _mstats.nmalloc[nunits]--; | |
692 | _mstats.nfre++; | |
693 | #endif /* MALLOC_STATS */ | |
726f6388 JA |
694 | } |
695 | ||
696 | char * | |
697 | realloc (mem, n) | |
698 | char *mem; | |
cce855bc | 699 | register size_t n; |
726f6388 | 700 | { |
cce855bc JA |
701 | register union mhead *p; |
702 | register u_int32_t tocopy; | |
726f6388 JA |
703 | register unsigned int nbytes; |
704 | register int nunits; | |
cce855bc JA |
705 | register char *m; |
706 | ||
707 | #ifdef MALLOC_STATS | |
708 | _mstats.nrealloc++; | |
709 | #endif | |
726f6388 | 710 | |
cce855bc JA |
711 | if (n == 0) |
712 | { | |
713 | free (mem); | |
714 | return (NULL); | |
715 | } | |
716 | if ((p = (union mhead *) mem) == 0) | |
726f6388 JA |
717 | return malloc (n); |
718 | p--; | |
cce855bc JA |
719 | nunits = p->mh_index; |
720 | ASSERT (p->mh_alloc == ISALLOC); | |
721 | ASSERT (p->mh_magic2 == MAGIC2); | |
722 | ||
723 | m = mem + (tocopy = p->mh_nbytes); | |
724 | ASSERT (*m++ == MAGIC1); ASSERT (*m++ == MAGIC1); | |
725 | ASSERT (*m++ == MAGIC1); ASSERT (*m == MAGIC1); | |
726f6388 JA |
726 | |
727 | /* See if desired size rounds to same power of 2 as actual size. */ | |
cce855bc | 728 | nbytes = (n + sizeof *p + MSLOP + 7) & ~7; |
726f6388 JA |
729 | |
730 | /* If ok, use the same block, just marking its size as changed. */ | |
731 | if (nbytes > (4 << nunits) && nbytes <= (8 << nunits)) | |
732 | { | |
cce855bc | 733 | m = mem + tocopy; |
726f6388 | 734 | *m++ = 0; *m++ = 0; *m++ = 0; *m++ = 0; |
cce855bc | 735 | p->mh_nbytes = n; |
726f6388 JA |
736 | m = mem + n; |
737 | *m++ = MAGIC1; *m++ = MAGIC1; *m++ = MAGIC1; *m++ = MAGIC1; | |
726f6388 JA |
738 | return mem; |
739 | } | |
740 | ||
cce855bc JA |
741 | #ifdef MALLOC_STATS |
742 | _mstats.nrcopy++; | |
743 | #endif | |
744 | ||
726f6388 JA |
745 | if (n < tocopy) |
746 | tocopy = n; | |
726f6388 | 747 | |
cce855bc JA |
748 | if ((m = malloc (n)) == 0) |
749 | return 0; | |
750 | FASTCOPY (mem, m, tocopy); | |
751 | free (mem); | |
752 | return m; | |
726f6388 JA |
753 | } |
754 | ||
755 | char * | |
756 | memalign (alignment, size) | |
cce855bc JA |
757 | unsigned int alignment; |
758 | size_t size; | |
726f6388 | 759 | { |
ccc6cda3 | 760 | register char *ptr; |
726f6388 | 761 | register char *aligned; |
cce855bc | 762 | register union mhead *p; |
726f6388 | 763 | |
ccc6cda3 JA |
764 | ptr = malloc (size + alignment); |
765 | ||
726f6388 JA |
766 | if (ptr == 0) |
767 | return 0; | |
768 | /* If entire block has the desired alignment, just accept it. */ | |
769 | if (((int) ptr & (alignment - 1)) == 0) | |
770 | return ptr; | |
771 | /* Otherwise, get address of byte in the block that has that alignment. */ | |
772 | aligned = (char *) (((int) ptr + alignment - 1) & -alignment); | |
773 | ||
774 | /* Store a suitable indication of how to free the block, | |
775 | so that free can find the true beginning of it. */ | |
cce855bc JA |
776 | p = (union mhead *) aligned - 1; |
777 | p->mh_nbytes = aligned - ptr; | |
778 | p->mh_alloc = ISMEMALIGN; | |
726f6388 JA |
779 | return aligned; |
780 | } | |
781 | ||
ccc6cda3 | 782 | #if !defined (HPUX) |
726f6388 JA |
783 | /* This runs into trouble with getpagesize on HPUX, and Multimax machines. |
784 | Patching out seems cleaner than the ugly fix needed. */ | |
ccc6cda3 JA |
785 | #if defined (__STDC__) |
786 | void * | |
787 | #else | |
726f6388 | 788 | char * |
ccc6cda3 | 789 | #endif |
726f6388 | 790 | valloc (size) |
ccc6cda3 | 791 | size_t size; |
726f6388 JA |
792 | { |
793 | return memalign (getpagesize (), size); | |
794 | } | |
ccc6cda3 JA |
795 | #endif /* !HPUX */ |
796 | ||
797 | #ifndef NO_CALLOC | |
798 | char * | |
799 | calloc (n, s) | |
800 | size_t n, s; | |
801 | { | |
802 | size_t total; | |
803 | char *result; | |
804 | ||
805 | total = n * s; | |
806 | result = malloc (total); | |
807 | if (result) | |
808 | zmemset (result, 0, total); | |
809 | return result; | |
810 | } | |
811 | ||
812 | void | |
813 | cfree (p) | |
814 | char *p; | |
815 | { | |
816 | free (p); | |
817 | } | |
818 | #endif /* !NO_CALLOC */ | |
819 | ||
cce855bc | 820 | #ifdef MALLOC_STATS |
726f6388 | 821 | |
cce855bc JA |
822 | struct bucket_stats |
823 | malloc_bucket_stats (size) | |
726f6388 JA |
824 | int size; |
825 | { | |
cce855bc JA |
826 | struct bucket_stats v; |
827 | register union mhead *p; | |
726f6388 JA |
828 | |
829 | v.nfree = 0; | |
830 | ||
cce855bc | 831 | if (size < 0 || size >= NBUCKETS) |
726f6388 JA |
832 | { |
833 | v.blocksize = 0; | |
cce855bc | 834 | v.nused = v.nmal = 0; |
726f6388 JA |
835 | return v; |
836 | } | |
837 | ||
838 | v.blocksize = 1 << (size + 3); | |
cce855bc JA |
839 | v.nused = _mstats.nmalloc[size]; |
840 | v.nmal = _mstats.tmalloc[size]; | |
841 | v.nmorecore = _mstats.nmorecore[size]; | |
726f6388 JA |
842 | |
843 | for (p = nextf[size]; p; p = CHAIN (p)) | |
844 | v.nfree++; | |
845 | ||
846 | return v; | |
847 | } | |
ccc6cda3 | 848 | |
cce855bc JA |
849 | /* Return a copy of _MSTATS, with two additional fields filled in: |
850 | BYTESFREE is the total number of bytes on free lists. BYTESUSED | |
851 | is the total number of bytes in use. These two fields are fairly | |
852 | expensive to compute, so we do it only when asked to. */ | |
853 | struct _malstats | |
854 | malloc_stats () | |
855 | { | |
856 | struct _malstats result; | |
857 | struct bucket_stats v; | |
858 | register int i; | |
726f6388 | 859 | |
cce855bc JA |
860 | result = _mstats; |
861 | result.bytesused = result.bytesfree = 0; | |
862 | for (i = 0; i < NBUCKETS; i++) | |
863 | { | |
864 | v = malloc_bucket_stats (i); | |
865 | result.bytesfree += v.nfree * v.blocksize; | |
866 | result.bytesused += v.nused * v.blocksize; | |
867 | } | |
868 | return (result); | |
726f6388 JA |
869 | } |
870 | ||
cce855bc JA |
871 | void |
872 | print_malloc_stats (s) | |
873 | char *s; | |
726f6388 | 874 | { |
cce855bc JA |
875 | register int i; |
876 | int totused, totfree; | |
877 | struct bucket_stats v; | |
726f6388 | 878 | |
cce855bc JA |
879 | fprintf (stderr, "Memory allocation statistics: %s\n\tsize\tfree\tin use\ttotal\tmorecore\n", s ? s : ""); |
880 | for (i = totused = totfree = 0; i < NBUCKETS; i++) | |
881 | { | |
882 | v = malloc_bucket_stats (i); | |
883 | fprintf (stderr, "%12lu\t%4d\t%6d\t%5d\t%8d\n", v.blocksize, v.nfree, v.nused, v.nmal, v.nmorecore); | |
884 | totfree += v.nfree * v.blocksize; | |
885 | totused += v.nused * v.blocksize; | |
886 | } | |
887 | fprintf (stderr, "\nTotal bytes in use: %d, total bytes free: %d\n", | |
888 | totused, totfree); | |
889 | fprintf (stderr, "Total mallocs: %d, total frees: %d, total reallocs: %d (%d copies)\n", | |
890 | _mstats.nmal, _mstats.nfre, _mstats.nrealloc, _mstats.nrcopy); | |
891 | fprintf (stderr, "Total sbrks: %d, total bytes via sbrk: %d\n", | |
892 | _mstats.nsbrk, _mstats.tsbrk); | |
893 | fprintf (stderr, "Total blocks split: %d, total block coalesces: %d\n", | |
894 | _mstats.nbsplit, _mstats.nbcoalesce); | |
726f6388 | 895 | } |
cce855bc | 896 | #endif /* MALLOC_STATS */ |