Commit | Line | Data |
---|---|---|
920dae64 AT |
1 | /* |
2 | * ========== Copyright Header Begin ========================================== | |
3 | * | |
4 | * Hypervisor Software File: malloc.c | |
5 | * | |
6 | * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved. | |
7 | * | |
8 | * - Do no alter or remove copyright notices | |
9 | * | |
10 | * - Redistribution and use of this software in source and binary forms, with | |
11 | * or without modification, are permitted provided that the following | |
12 | * conditions are met: | |
13 | * | |
14 | * - Redistribution of source code must retain the above copyright notice, | |
15 | * this list of conditions and the following disclaimer. | |
16 | * | |
17 | * - Redistribution in binary form must reproduce the above copyright notice, | |
18 | * this list of conditions and the following disclaimer in the | |
19 | * documentation and/or other materials provided with the distribution. | |
20 | * | |
21 | * Neither the name of Sun Microsystems, Inc. or the names of contributors | |
22 | * may be used to endorse or promote products derived from this software | |
23 | * without specific prior written permission. | |
24 | * | |
25 | * This software is provided "AS IS," without a warranty of any kind. | |
26 | * ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, | |
27 | * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A | |
28 | * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN | |
29 | * MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR | |
30 | * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR | |
31 | * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN | |
32 | * OR ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR | |
33 | * FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE | |
34 | * DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, | |
35 | * ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF | |
36 | * SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. | |
37 | * | |
38 | * You acknowledge that this software is not designed, licensed or | |
39 | * intended for use in the design, construction, operation or maintenance of | |
40 | * any nuclear facility. | |
41 | * | |
42 | * ========== Copyright Header End ============================================ | |
43 | */ | |
44 | /* Copyright (c) 1988 AT&T */ | |
45 | /* All Rights Reserved */ | |
46 | ||
47 | /* THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T */ | |
48 | /* The copyright notice above does not evidence any */ | |
49 | /* actual or intended publication of such source code. */ | |
50 | ||
51 | #pragma ident "@(#)malloc.c 1.17 98/07/23 SMI" /* SVr4.0 1.12 */ | |
52 | ||
53 | /*LINTLIBRARY*/ | |
54 | #include <sys/types.h> | |
55 | ||
56 | #ifndef debug | |
57 | #define NDEBUG | |
58 | #endif | |
59 | ||
60 | #include <stdlib.h> | |
61 | #include <string.h> | |
62 | #include <thread.h> | |
63 | #include <synch.h> | |
64 | #include <assert.h> | |
65 | #include <malloc.h> | |
66 | #include "mallint.h" | |
67 | #include <unistd.h> | |
68 | #include <limits.h> | |
69 | ||
70 | static mutex_t mlock = DEFAULTMUTEX; | |
71 | static ssize_t freespace(struct holdblk *); | |
72 | static void *malloc_unlocked(size_t); | |
73 | static void *realloc_unlocked(void *, size_t); | |
74 | static void free_unlocked(void *); | |
75 | static void *morecore(size_t); | |
76 | ||
77 | /* | |
78 | * use level memory allocater (malloc, free, realloc) | |
79 | * | |
80 | * -malloc, free, realloc and mallopt form a memory allocator | |
81 | * similar to malloc, free, and realloc. The routines | |
82 | * here are much faster than the original, with slightly worse | |
83 | * space usage (a few percent difference on most input). They | |
84 | * do not have the property that data in freed blocks is left | |
85 | * untouched until the space is reallocated. | |
86 | * | |
87 | * -Memory is kept in the "arena", a singly linked list of blocks. | |
88 | * These blocks are of 3 types. | |
89 | * 1. A free block. This is a block not in use by the | |
90 | * user. It has a 3 word header. (See description | |
91 | * of the free queue.) | |
92 | * 2. An allocated block. This is a block the user has | |
93 | * requested. It has only a 1 word header, pointing | |
94 | * to the next block of any sort. | |
95 | * 3. A permanently allocated block. This covers space | |
96 | * aquired by the user directly through sbrk(). It | |
97 | * has a 1 word header, as does 2. | |
98 | * Blocks of type 1 have the lower bit of the pointer to the | |
99 | * nextblock = 0. Blocks of type 2 and 3 have that bit set, | |
100 | * to mark them busy. | |
101 | * | |
102 | * -Unallocated blocks are kept on an unsorted doubly linked | |
103 | * free list. | |
104 | * | |
105 | * -Memory is allocated in blocks, with sizes specified by the | |
106 | * user. A circular first-fit startegy is used, with a roving | |
107 | * head of the free queue, which prevents bunching of small | |
108 | * blocks at the head of the queue. | |
109 | * | |
110 | * -Compaction is performed at free time of any blocks immediately | |
111 | * following the freed block. The freed block will be combined | |
112 | * with a preceding block during the search phase of malloc. | |
113 | * Since a freed block is added at the front of the free queue, | |
114 | * which is moved to the end of the queue if considered and | |
115 | * rejected during the search, fragmentation only occurs if | |
116 | * a block with a contiguious preceding block that is free is | |
117 | * freed and reallocated on the next call to malloc. The | |
118 | * time savings of this strategy is judged to be worth the | |
119 | * occasional waste of memory. | |
120 | * | |
121 | * -Small blocks (of size < MAXSIZE) are not allocated directly. | |
122 | * A large "holding" block is allocated via a recursive call to | |
123 | * malloc. This block contains a header and ?????? small blocks. | |
124 | * Holding blocks for a given size of small block (rounded to the | |
125 | * nearest ALIGNSZ bytes) are kept on a queue with the property that any | |
126 | * holding block with an unused small block is in front of any without. | |
127 | * A list of free blocks is kept within the holding block. | |
128 | */ | |
129 | ||
130 | /* | |
131 | * description of arena, free queue, holding blocks etc. | |
132 | * | |
133 | * New compiler and linker does not guarentee order of initialized data. | |
134 | * Define freeptr as arena[2-3] to guarentee it follows arena in memory. | |
135 | * Later code depends on this order. | |
136 | */ | |
137 | ||
138 | static struct header arena[4] = { | |
139 | {0, 0, 0}, | |
140 | {0, 0, 0}, | |
141 | {0, 0, 0}, | |
142 | {0, 0, 0} | |
143 | }; | |
144 | /* | |
145 | * the second word is a minimal block to | |
146 | * start the arena. The first is a busy | |
147 | * block to be pointed to by the last block. | |
148 | */ | |
149 | ||
150 | #define freeptr (arena + 2) | |
151 | /* first and last entry in free list */ | |
152 | static struct header *arenaend; /* ptr to block marking high end of arena */ | |
153 | static struct header *lastblk; /* the highest block in the arena */ | |
154 | static struct holdblk **holdhead; /* pointer to array of head pointers */ | |
155 | /* to holding block chains */ | |
156 | /* | |
157 | * In order to save time calculating indices, the array is 1 too | |
158 | * large, and the first element is unused | |
159 | * | |
160 | * Variables controlling algorithm, esp. how holding blocs are used | |
161 | */ | |
162 | static int numlblks = NUMLBLKS; | |
163 | static int minhead = MINHEAD; | |
164 | static int change = 0; /* != 0, once param changes are no longer allowed */ | |
165 | static int fastct = FASTCT; | |
166 | static unsigned int maxfast = MAXFAST; | |
167 | /* number of small block sizes to map to one size */ | |
168 | ||
169 | static int grain = ALIGNSZ; | |
170 | ||
171 | #ifdef debug | |
172 | static int case1count = 0; | |
173 | ||
174 | static | |
175 | checkq(void) | |
176 | { | |
177 | register struct header *p; | |
178 | ||
179 | p = &freeptr[0]; | |
180 | ||
181 | /* check forward */ | |
182 | /*CSTYLED*/ | |
183 | while (p != &freeptr[1]) { | |
184 | p = p->nextfree; | |
185 | assert(p->prevfree->nextfree == p); | |
186 | } | |
187 | ||
188 | /* check backward */ | |
189 | /*CSTYLED*/ | |
190 | while (p != &freeptr[0]) { | |
191 | p = p->prevfree; | |
192 | assert(p->nextfree->prevfree == p); | |
193 | } | |
194 | } | |
195 | #endif | |
196 | ||
197 | ||
198 | /* | |
199 | * malloc(nbytes) - give a user nbytes to use | |
200 | */ | |
201 | ||
202 | void * | |
203 | malloc(size_t nbytes) | |
204 | { | |
205 | void *ret; | |
206 | ||
207 | mutex_lock(&mlock); | |
208 | ret = malloc_unlocked(nbytes); | |
209 | mutex_unlock(&mlock); | |
210 | return (ret); | |
211 | } | |
212 | ||
213 | ||
214 | /* | |
215 | * malloc_unlocked(nbytes) - Do the real work for malloc | |
216 | */ | |
217 | ||
218 | static void * | |
219 | malloc_unlocked(size_t nbytes) | |
220 | { | |
221 | struct header *blk; | |
222 | size_t nb; /* size of entire block we need */ | |
223 | ||
224 | /* on first call, initialize */ | |
225 | if (freeptr[0].nextfree == GROUND) { | |
226 | /* initialize arena */ | |
227 | arena[1].nextblk = (struct header *)BUSY; | |
228 | arena[0].nextblk = (struct header *)BUSY; | |
229 | lastblk = arenaend = &(arena[1]); | |
230 | /* initialize free queue */ | |
231 | freeptr[0].nextfree = &(freeptr[1]); | |
232 | freeptr[1].nextblk = &(arena[0]); | |
233 | freeptr[1].prevfree = &(freeptr[0]); | |
234 | /* mark that small blocks not init yet */ | |
235 | } | |
236 | if (nbytes == 0) | |
237 | return (NULL); | |
238 | ||
239 | if (nbytes <= maxfast) { | |
240 | /* | |
241 | * We can allocate out of a holding block | |
242 | */ | |
243 | struct holdblk *holdblk; /* head of right sized queue */ | |
244 | struct lblk *lblk; /* pointer to a little block */ | |
245 | struct holdblk *newhold; | |
246 | ||
247 | if (!change) { | |
248 | int i; | |
249 | /* | |
250 | * This allocates space for hold block | |
251 | * pointers by calling malloc recursively. | |
252 | * Maxfast is temporarily set to 0, to | |
253 | * avoid infinite recursion. allocate | |
254 | * space for an extra ptr so that an index | |
255 | * is just ->blksz/grain, with the first | |
256 | * ptr unused. | |
257 | */ | |
258 | change = 1; /* change to algorithm params */ | |
259 | /* no longer allowed */ | |
260 | /* | |
261 | * temporarily alter maxfast, to avoid | |
262 | * infinite recursion | |
263 | */ | |
264 | maxfast = 0; | |
265 | holdhead = (struct holdblk **) | |
266 | malloc_unlocked(sizeof (struct holdblk *) * | |
267 | (fastct + 1)); | |
268 | if (holdhead == NULL) | |
269 | return (malloc_unlocked(nbytes)); | |
270 | for (i = 1; i <= fastct; i++) { | |
271 | holdhead[i] = HGROUND; | |
272 | } | |
273 | maxfast = fastct * grain; | |
274 | } | |
275 | /* | |
276 | * Note that this uses the absolute min header size (MINHEAD) | |
277 | * unlike the large block case which uses minhead | |
278 | * | |
279 | * round up to nearest multiple of grain | |
280 | * code assumes grain is a multiple of MINHEAD | |
281 | */ | |
282 | /* round up to grain */ | |
283 | nb = (nbytes + grain - 1) / grain * grain; | |
284 | holdblk = holdhead[nb / grain]; | |
285 | nb = nb + MINHEAD; | |
286 | /* | |
287 | * look for space in the holding block. Blocks with | |
288 | * space will be in front of those without | |
289 | */ | |
290 | if ((holdblk != HGROUND) && (holdblk->lfreeq != LGROUND)) { | |
291 | /* there is space */ | |
292 | lblk = holdblk->lfreeq; | |
293 | ||
294 | /* | |
295 | * Now make lfreeq point to a free block. | |
296 | * If lblk has been previously allocated and | |
297 | * freed, it has a valid pointer to use. | |
298 | * Otherwise, lblk is at the beginning of | |
299 | * the unallocated blocks at the end of | |
300 | * the holding block, so, if there is room, take | |
301 | * the next space. If not, mark holdblk full, | |
302 | * and move holdblk to the end of the queue | |
303 | */ | |
304 | if (lblk < holdblk->unused) { | |
305 | /* move to next holdblk, if this one full */ | |
306 | if ((holdblk->lfreeq = | |
307 | CLRSMAL(lblk->header.nextfree)) == | |
308 | LGROUND) { | |
309 | holdhead[(nb-MINHEAD) / grain] = | |
310 | holdblk->nexthblk; | |
311 | } | |
312 | } else if (((char *)holdblk->unused + nb) < | |
313 | ((char *)holdblk + HOLDSZ(nb))) { | |
314 | holdblk->unused = (struct lblk *) | |
315 | ((char *)holdblk->unused+nb); | |
316 | holdblk->lfreeq = holdblk->unused; | |
317 | } else { | |
318 | holdblk->unused = (struct lblk *) | |
319 | ((char *)holdblk->unused+nb); | |
320 | holdblk->lfreeq = LGROUND; | |
321 | holdhead[(nb-MINHEAD)/grain] = | |
322 | holdblk->nexthblk; | |
323 | } | |
324 | /* mark as busy and small */ | |
325 | lblk->header.holder = (struct holdblk *)SETALL(holdblk); | |
326 | } else { | |
327 | /* we need a new holding block */ | |
328 | newhold = (struct holdblk *) | |
329 | malloc_unlocked(HOLDSZ(nb)); | |
330 | if ((char *)newhold == NULL) { | |
331 | return (NULL); | |
332 | } | |
333 | /* add to head of free queue */ | |
334 | if (holdblk != HGROUND) { | |
335 | newhold->nexthblk = holdblk; | |
336 | newhold->prevhblk = holdblk->prevhblk; | |
337 | holdblk->prevhblk = newhold; | |
338 | newhold->prevhblk->nexthblk = newhold; | |
339 | } else { | |
340 | newhold->nexthblk = newhold->prevhblk = newhold; | |
341 | } | |
342 | holdhead[(nb-MINHEAD)/grain] = newhold; | |
343 | /* set up newhold */ | |
344 | lblk = (struct lblk *)(newhold->space); | |
345 | newhold->lfreeq = newhold->unused = | |
346 | (struct lblk *)((char *)newhold->space+nb); | |
347 | lblk->header.holder = (struct holdblk *)SETALL(newhold); | |
348 | newhold->blksz = nb-MINHEAD; | |
349 | } | |
350 | #ifdef debug | |
351 | assert(((struct holdblk *)CLRALL(lblk->header.holder))->blksz >= | |
352 | nbytes); | |
353 | #endif /* debug */ | |
354 | return ((char *)lblk + MINHEAD); | |
355 | } else { | |
356 | /* | |
357 | * We need an ordinary block | |
358 | */ | |
359 | struct header *newblk; /* used for creating a block */ | |
360 | ||
361 | /* get number of bytes we need */ | |
362 | nb = nbytes + minhead; | |
363 | nb = (nb + ALIGNSZ - 1) / ALIGNSZ * ALIGNSZ; /* align */ | |
364 | nb = (nb > MINBLKSZ) ? nb : MINBLKSZ; | |
365 | /* | |
366 | * see if there is a big enough block | |
367 | * If none exists, you will get to freeptr[1]. | |
368 | * freeptr[1].next = &arena[0], so when you do the test, | |
369 | * the result is a large positive number, since arena[0] | |
370 | * comes before all blocks. Arena[0] is marked busy so | |
371 | * that it will not be compacted. This kludge is for the | |
372 | * sake of the almighty efficiency. | |
373 | */ | |
374 | /* check that a very large request won't cause an inf. loop */ | |
375 | ||
376 | if ((freeptr[1].nextblk-&(freeptr[1])) < nb) { | |
377 | return (NULL); | |
378 | } else { | |
379 | struct header *next; /* following block */ | |
380 | struct header *nextnext; /* block after next */ | |
381 | ||
382 | blk = freeptr; | |
383 | do { | |
384 | blk = blk->nextfree; | |
385 | /* see if we can compact */ | |
386 | next = blk->nextblk; | |
387 | if (!TESTBUSY(nextnext = next->nextblk)) { | |
388 | do { | |
389 | DELFREEQ(next); | |
390 | next = nextnext; | |
391 | nextnext = next->nextblk; | |
392 | } while (!TESTBUSY(nextnext)); | |
393 | /* | |
394 | * next will be at most == to lastblk, | |
395 | * but I think the >= test is faster | |
396 | */ | |
397 | if (next >= arenaend) | |
398 | lastblk = blk; | |
399 | blk->nextblk = next; | |
400 | } | |
401 | } while (((char *)(next) - (char *)blk) < nb); | |
402 | } | |
403 | /* | |
404 | * if we didn't find a block, get more memory | |
405 | */ | |
406 | if (blk == &(freeptr[1])) { | |
407 | /* | |
408 | * careful coding could likely replace | |
409 | * newend with arenaend | |
410 | */ | |
411 | struct header *newend; /* new end of arena */ | |
412 | ssize_t nget; /* number of words to get */ | |
413 | ||
414 | /* | |
415 | * Three cases - 1. There is space between arenaend | |
416 | * and the break value that will become | |
417 | * a permanently allocated block. | |
418 | * 2. Case 1 is not true, and the last | |
419 | * block is allocated. | |
420 | * 3. Case 1 is not true, and the last | |
421 | * block is free | |
422 | */ | |
423 | if ((newblk = (struct header *)sbrk(0)) != | |
424 | (struct header *)((char *)arenaend + HEADSZ)) { | |
425 | /* case 1 */ | |
426 | #ifdef debug | |
427 | if (case1count++ > 0) | |
428 | write(2, "Case 1 hit more that once. " | |
429 | "brk or sbrk?\n", 41); | |
430 | #endif | |
431 | /* get size to fetch */ | |
432 | nget = nb + HEADSZ; | |
433 | /* round up to a block */ | |
434 | nget = (nget + BLOCKSZ - 1)/BLOCKSZ * BLOCKSZ; | |
435 | assert((int)newblk % ALIGNSZ == 0); | |
436 | /* get memory */ | |
437 | if (morecore(nget) == (void *)-1) | |
438 | return (NULL); | |
439 | /* add to arena */ | |
440 | newend = (struct header *)((char *)newblk + nget | |
441 | - HEADSZ); | |
442 | assert((int)newblk % ALIGNSZ == 0); | |
443 | newend->nextblk = SETBUSY(&(arena[1])); | |
444 | /* ??? newblk ?? */ | |
445 | newblk->nextblk = newend; | |
446 | ||
447 | /* | |
448 | * space becomes a permanently allocated block. | |
449 | * This is likely not mt-safe as lock is not | |
450 | * shared with brk or sbrk | |
451 | */ | |
452 | arenaend->nextblk = SETBUSY(newblk); | |
453 | /* adjust other pointers */ | |
454 | arenaend = newend; | |
455 | lastblk = newblk; | |
456 | blk = newblk; | |
457 | } else if (TESTBUSY(lastblk->nextblk)) { | |
458 | /* case 2 */ | |
459 | nget = (nb + BLOCKSZ - 1) / BLOCKSZ * BLOCKSZ; | |
460 | if (morecore(nget) == (void *)-1) | |
461 | return (NULL); | |
462 | /* block must be word aligned */ | |
463 | assert(((int)newblk%ALIGNSZ) == 0); | |
464 | /* | |
465 | * stub at old arenaend becomes first word | |
466 | * in blk | |
467 | */ | |
468 | /* ??? newblk = arenaend; */ | |
469 | ||
470 | newend = | |
471 | (struct header *)((char *)arenaend+nget); | |
472 | newend->nextblk = SETBUSY(&(arena[1])); | |
473 | arenaend->nextblk = newend; | |
474 | lastblk = blk = arenaend; | |
475 | arenaend = newend; | |
476 | } else { | |
477 | /* case 3 */ | |
478 | /* | |
479 | * last block in arena is at end of memory and | |
480 | * is free | |
481 | */ | |
482 | /* 1.7 had this backward without cast */ | |
483 | nget = nb - | |
484 | ((char *)arenaend - (char *)lastblk); | |
485 | nget = (nget + (BLOCKSZ - 1)) / | |
486 | BLOCKSZ * BLOCKSZ; | |
487 | assert(((int)newblk % ALIGNSZ) == 0); | |
488 | if (morecore(nget) == (void *)-1) | |
489 | return (NULL); | |
490 | /* combine with last block, put in arena */ | |
491 | newend = (struct header *) | |
492 | ((char *)arenaend + nget); | |
493 | arenaend = lastblk->nextblk = newend; | |
494 | newend->nextblk = SETBUSY(&(arena[1])); | |
495 | /* set which block to use */ | |
496 | blk = lastblk; | |
497 | DELFREEQ(blk); | |
498 | } | |
499 | } else { | |
500 | struct header *nblk; /* next block */ | |
501 | ||
502 | /* take block found of free queue */ | |
503 | DELFREEQ(blk); | |
504 | /* | |
505 | * make head of free queue immediately follow blk, | |
506 | * unless blk was at the end of the queue | |
507 | */ | |
508 | nblk = blk->nextfree; | |
509 | if (nblk != &(freeptr[1])) { | |
510 | MOVEHEAD(nblk); | |
511 | } | |
512 | } | |
513 | /* blk now points to an adequate block */ | |
514 | if (((char *)blk->nextblk - (char *)blk) - nb >= MINBLKSZ) { | |
515 | /* carve out the right size block */ | |
516 | /* newblk will be the remainder */ | |
517 | newblk = (struct header *)((char *)blk + nb); | |
518 | newblk->nextblk = blk->nextblk; | |
519 | /* mark the block busy */ | |
520 | blk->nextblk = SETBUSY(newblk); | |
521 | ADDFREEQ(newblk); | |
522 | /* if blk was lastblk, make newblk lastblk */ | |
523 | if (blk == lastblk) | |
524 | lastblk = newblk; | |
525 | } else { | |
526 | /* just mark the block busy */ | |
527 | blk->nextblk = SETBUSY(blk->nextblk); | |
528 | } | |
529 | } | |
530 | CHECKQ; | |
531 | assert((char *)CLRALL(blk->nextblk) - | |
532 | ((char *)blk + minhead) >= nbytes); | |
533 | assert((char *)CLRALL(blk->nextblk) - | |
534 | ((char *)blk + minhead) < nbytes + MINBLKSZ); | |
535 | return ((char *)blk + minhead); | |
536 | } | |
537 | ||
538 | /* | |
539 | * free(ptr) - free block that user thinks starts at ptr | |
540 | * | |
541 | * input - ptr-1 contains the block header. | |
542 | * If the header points forward, we have a normal | |
543 | * block pointing to the next block | |
544 | * if the header points backward, we have a small | |
545 | * block from a holding block. | |
546 | * In both cases, the busy bit must be set | |
547 | */ | |
548 | ||
549 | void | |
550 | free(void *ptr) | |
551 | { | |
552 | mutex_lock(&mlock); | |
553 | free_unlocked(ptr); | |
554 | mutex_unlock(&mlock); | |
555 | } | |
556 | ||
557 | /* | |
558 | * free_unlocked(ptr) - Do the real work for free() | |
559 | */ | |
560 | ||
561 | void | |
562 | free_unlocked(void *ptr) | |
563 | { | |
564 | struct holdblk *holdblk; /* block holding blk */ | |
565 | struct holdblk *oldhead; /* former head of the hold block */ | |
566 | /* queue containing blk's holder */ | |
567 | ||
568 | if (ptr == NULL) | |
569 | return; | |
570 | if (TESTSMAL(((struct header *)((char *)ptr - MINHEAD))->nextblk)) { | |
571 | struct lblk *lblk; /* pointer to freed block */ | |
572 | ssize_t offset; /* choice of header lists */ | |
573 | ||
574 | lblk = (struct lblk *)CLRBUSY((char *)ptr - MINHEAD); | |
575 | assert((struct header *)lblk < arenaend); | |
576 | assert((struct header *)lblk > arena); | |
577 | /* allow twits (e.g. awk) to free a block twice */ | |
578 | holdblk = lblk->header.holder; | |
579 | if (!TESTBUSY(holdblk)) | |
580 | return; | |
581 | holdblk = (struct holdblk *)CLRALL(holdblk); | |
582 | /* put lblk on its hold block's free list */ | |
583 | lblk->header.nextfree = SETSMAL(holdblk->lfreeq); | |
584 | holdblk->lfreeq = lblk; | |
585 | /* move holdblk to head of queue, if its not already there */ | |
586 | offset = holdblk->blksz / grain; | |
587 | oldhead = holdhead[offset]; | |
588 | if (oldhead != holdblk) { | |
589 | /* first take out of current spot */ | |
590 | holdhead[offset] = holdblk; | |
591 | holdblk->nexthblk->prevhblk = holdblk->prevhblk; | |
592 | holdblk->prevhblk->nexthblk = holdblk->nexthblk; | |
593 | /* now add at front */ | |
594 | holdblk->nexthblk = oldhead; | |
595 | holdblk->prevhblk = oldhead->prevhblk; | |
596 | oldhead->prevhblk = holdblk; | |
597 | holdblk->prevhblk->nexthblk = holdblk; | |
598 | } | |
599 | } else { | |
600 | struct header *blk; /* real start of block */ | |
601 | struct header *next; /* next = blk->nextblk */ | |
602 | struct header *nextnext; /* block after next */ | |
603 | ||
604 | blk = (struct header *)((char *)ptr - minhead); | |
605 | next = blk->nextblk; | |
606 | /* take care of twits (e.g. awk) who return blocks twice */ | |
607 | if (!TESTBUSY(next)) | |
608 | return; | |
609 | blk->nextblk = next = CLRBUSY(next); | |
610 | ADDFREEQ(blk); | |
611 | /* see if we can compact */ | |
612 | if (!TESTBUSY(nextnext = next->nextblk)) { | |
613 | do { | |
614 | DELFREEQ(next); | |
615 | next = nextnext; | |
616 | } while (!TESTBUSY(nextnext = next->nextblk)); | |
617 | if (next == arenaend) lastblk = blk; | |
618 | blk->nextblk = next; | |
619 | } | |
620 | } | |
621 | CHECKQ | |
622 | } | |
623 | ||
624 | ||
625 | /* | |
626 | * realloc(ptr, size) - give the user a block of size "size", with | |
627 | * the contents pointed to by ptr. Free ptr. | |
628 | */ | |
629 | ||
630 | void * | |
631 | realloc(void *ptr, size_t size) | |
632 | { | |
633 | void *retval; | |
634 | ||
635 | mutex_lock(&mlock); | |
636 | retval = realloc_unlocked(ptr, size); | |
637 | mutex_unlock(&mlock); | |
638 | return (retval); | |
639 | } | |
640 | ||
641 | ||
642 | /* | |
643 | * realloc_unlocked(ptr) - Do the real work for realloc() | |
644 | */ | |
645 | ||
646 | static void * | |
647 | realloc_unlocked(void *ptr, size_t size) | |
648 | { | |
649 | struct header *blk; /* block ptr is contained in */ | |
650 | size_t trusize; /* block size as allocater sees it */ | |
651 | char *newptr; /* pointer to user's new block */ | |
652 | size_t cpysize; /* amount to copy */ | |
653 | struct header *next; /* block after blk */ | |
654 | ||
655 | if (ptr == NULL) | |
656 | return (malloc_unlocked(size)); | |
657 | ||
658 | if (size == 0) { | |
659 | free_unlocked(ptr); | |
660 | return (NULL); | |
661 | } | |
662 | ||
663 | if (TESTSMAL(((struct lblk *)((char *)ptr - MINHEAD))-> | |
664 | header.holder)) { | |
665 | /* | |
666 | * we have a special small block which can't be expanded | |
667 | * | |
668 | * This makes the assumption that even if the user is | |
669 | * reallocating a free block, malloc doesn't alter the contents | |
670 | * of small blocks | |
671 | */ | |
672 | newptr = malloc_unlocked(size); | |
673 | if (newptr == NULL) | |
674 | return (NULL); | |
675 | /* this isn't to save time--its to protect the twits */ | |
676 | if ((char *)ptr != newptr) { | |
677 | struct lblk *lblk; | |
678 | lblk = (struct lblk *)((char *)ptr - MINHEAD); | |
679 | cpysize = ((struct holdblk *) | |
680 | CLRALL(lblk->header.holder))->blksz; | |
681 | cpysize = (size > cpysize) ? cpysize : size; | |
682 | (void) memcpy(newptr, ptr, cpysize); | |
683 | free_unlocked(ptr); | |
684 | } | |
685 | } else { | |
686 | blk = (struct header *)((char *)ptr - minhead); | |
687 | next = blk->nextblk; | |
688 | /* | |
689 | * deal with twits who reallocate free blocks | |
690 | * | |
691 | * if they haven't reset minblk via getopt, that's | |
692 | * their problem | |
693 | */ | |
694 | if (!TESTBUSY(next)) { | |
695 | DELFREEQ(blk); | |
696 | blk->nextblk = SETBUSY(next); | |
697 | } | |
698 | next = CLRBUSY(next); | |
699 | /* make blk as big as possible */ | |
700 | if (!TESTBUSY(next->nextblk)) { | |
701 | do { | |
702 | DELFREEQ(next); | |
703 | next = next->nextblk; | |
704 | } while (!TESTBUSY(next->nextblk)); | |
705 | blk->nextblk = SETBUSY(next); | |
706 | if (next >= arenaend) lastblk = blk; | |
707 | } | |
708 | /* get size we really need */ | |
709 | trusize = size+minhead; | |
710 | trusize = (trusize + ALIGNSZ - 1)/ALIGNSZ*ALIGNSZ; | |
711 | trusize = (trusize >= MINBLKSZ) ? trusize : MINBLKSZ; | |
712 | /* see if we have enough */ | |
713 | /* this isn't really the copy size, but I need a register */ | |
714 | cpysize = (char *)next - (char *)blk; | |
715 | if (cpysize >= trusize) { | |
716 | /* carve out the size we need */ | |
717 | struct header *newblk; /* remainder */ | |
718 | ||
719 | if (cpysize - trusize >= MINBLKSZ) { | |
720 | /* | |
721 | * carve out the right size block | |
722 | * newblk will be the remainder | |
723 | */ | |
724 | newblk = (struct header *)((char *)blk + | |
725 | trusize); | |
726 | newblk->nextblk = next; | |
727 | blk->nextblk = SETBUSY(newblk); | |
728 | /* at this point, next is invalid */ | |
729 | ADDFREEQ(newblk); | |
730 | /* if blk was lastblk, make newblk lastblk */ | |
731 | if (blk == lastblk) | |
732 | lastblk = newblk; | |
733 | } | |
734 | newptr = ptr; | |
735 | } else { | |
736 | /* bite the bullet, and call malloc */ | |
737 | cpysize = (size > cpysize) ? cpysize : size; | |
738 | newptr = malloc_unlocked(size); | |
739 | if (newptr == NULL) | |
740 | return (NULL); | |
741 | (void) memcpy(newptr, ptr, cpysize); | |
742 | free_unlocked(ptr); | |
743 | } | |
744 | } | |
745 | return (newptr); | |
746 | } | |
747 | ||
748 | ||
749 | /* LINTLIBRARY */ | |
750 | /* | |
751 | * calloc - allocate and clear memory block | |
752 | */ | |
753 | ||
754 | void * | |
755 | calloc(size_t num, size_t size) | |
756 | { | |
757 | char *mp; | |
758 | ||
759 | num *= size; | |
760 | mp = malloc(num); | |
761 | if (mp == NULL) | |
762 | return (NULL); | |
763 | (void) memset(mp, 0, num); | |
764 | return (mp); | |
765 | } | |
766 | ||
767 | ||
768 | /* | |
769 | * Mallopt - set options for allocation | |
770 | * | |
771 | * Mallopt provides for control over the allocation algorithm. | |
772 | * The cmds available are: | |
773 | * | |
774 | * M_MXFAST Set maxfast to value. Maxfast is the size of the | |
775 | * largest small, quickly allocated block. Maxfast | |
776 | * may be set to 0 to disable fast allocation entirely. | |
777 | * | |
778 | * M_NLBLKS Set numlblks to value. Numlblks is the number of | |
779 | * small blocks per holding block. Value must be | |
780 | * greater than 0. | |
781 | * | |
782 | * M_GRAIN Set grain to value. The sizes of all blocks | |
783 | * smaller than maxfast are considered to be rounded | |
784 | * up to the nearest multiple of grain. The default | |
785 | * value of grain is the smallest number of bytes | |
786 | * which will allow alignment of any data type. Grain | |
787 | * will be rounded up to a multiple of its default, | |
788 | * and maxsize will be rounded up to a multiple of | |
789 | * grain. Value must be greater than 0. | |
790 | * | |
791 | * M_KEEP Retain data in freed block until the next malloc, | |
792 | * realloc, or calloc. Value is ignored. | |
793 | * This option is provided only for compatibility with | |
794 | * the old version of malloc, and is not recommended. | |
795 | * | |
796 | * returns - 0, upon successful completion | |
797 | * 1, if malloc has previously been called or | |
798 | * if value or cmd have illegal values | |
799 | */ | |
800 | ||
801 | int | |
802 | _mallopt(int cmd, int value) | |
803 | { | |
804 | /* disallow changes once a small block is allocated */ | |
805 | mutex_lock(&mlock); | |
806 | if (change) { | |
807 | mutex_unlock(&mlock); | |
808 | return (1); | |
809 | } | |
810 | switch (cmd) { | |
811 | case M_MXFAST: | |
812 | if (value < 0) { | |
813 | mutex_unlock(&mlock); | |
814 | return (1); | |
815 | } | |
816 | fastct = (value + grain - 1) / grain; | |
817 | maxfast = grain*fastct; | |
818 | break; | |
819 | case M_NLBLKS: | |
820 | if (value <= 1) { | |
821 | mutex_unlock(&mlock); | |
822 | return (1); | |
823 | } | |
824 | numlblks = value; | |
825 | break; | |
826 | case M_GRAIN: | |
827 | if (value <= 0) { | |
828 | mutex_unlock(&mlock); | |
829 | return (1); | |
830 | } | |
831 | ||
832 | /* round grain up to a multiple of ALIGNSZ */ | |
833 | grain = (value + ALIGNSZ - 1)/ALIGNSZ*ALIGNSZ; | |
834 | ||
835 | /* reduce fastct appropriately */ | |
836 | fastct = (maxfast + grain - 1) / grain; | |
837 | maxfast = grain * fastct; | |
838 | break; | |
839 | case M_KEEP: | |
840 | if (change && holdhead != NULL) { | |
841 | mutex_unlock(&mlock); | |
842 | return (1); | |
843 | } | |
844 | minhead = HEADSZ; | |
845 | break; | |
846 | default: | |
847 | mutex_unlock(&mlock); | |
848 | return (1); | |
849 | } | |
850 | mutex_unlock(&mlock); | |
851 | return (0); | |
852 | } | |
853 | ||
854 | /* | |
855 | * mallinfo-provide information about space usage | |
856 | * | |
857 | * input - max; mallinfo will return the size of the | |
858 | * largest block < max. | |
859 | * | |
860 | * output - a structure containing a description of | |
861 | * of space usage, defined in malloc.h | |
862 | */ | |
863 | ||
864 | struct mallinfo | |
865 | _mallinfo(void) | |
866 | { | |
867 | struct header *blk, *next; /* ptr to ordinary blocks */ | |
868 | struct holdblk *hblk; /* ptr to holding blocks */ | |
869 | struct mallinfo inf; /* return value */ | |
870 | int i; /* the ubiquitous counter */ | |
871 | ssize_t size; /* size of a block */ | |
872 | ssize_t fsp; /* free space in 1 hold block */ | |
873 | ||
874 | mutex_lock(&mlock); | |
875 | (void) memset(&inf, 0, sizeof (struct mallinfo)); | |
876 | if (freeptr[0].nextfree == GROUND) { | |
877 | mutex_unlock(&mlock); | |
878 | return (inf); | |
879 | } | |
880 | blk = CLRBUSY(arena[1].nextblk); | |
881 | /* return total space used */ | |
882 | inf.arena = (char *)arenaend - (char *)blk; | |
883 | ||
884 | /* | |
885 | * loop through arena, counting # of blocks, and | |
886 | * and space used by blocks | |
887 | */ | |
888 | next = CLRBUSY(blk->nextblk); | |
889 | while (next != &(arena[1])) { | |
890 | inf.ordblks++; | |
891 | size = (char *)next - (char *)blk; | |
892 | if (TESTBUSY(blk->nextblk)) { | |
893 | inf.uordblks += size; | |
894 | inf.keepcost += HEADSZ-MINHEAD; | |
895 | } else { | |
896 | inf.fordblks += size; | |
897 | } | |
898 | blk = next; | |
899 | next = CLRBUSY(blk->nextblk); | |
900 | } | |
901 | ||
902 | /* | |
903 | * if any holding block have been allocated | |
904 | * then examine space in holding blks | |
905 | */ | |
906 | if (change && holdhead != NULL) { | |
907 | for (i = fastct; i > 0; i--) { /* loop thru ea. chain */ | |
908 | hblk = holdhead[i]; | |
909 | /* do only if chain not empty */ | |
910 | if (hblk != HGROUND) { | |
911 | size = hblk->blksz + | |
912 | sizeof (struct lblk) - sizeof (int); | |
913 | do { /* loop thru 1 hold blk chain */ | |
914 | inf.hblks++; | |
915 | fsp = freespace(hblk); | |
916 | inf.fsmblks += fsp; | |
917 | inf.usmblks += numlblks*size - fsp; | |
918 | inf.smblks += numlblks; | |
919 | hblk = hblk->nexthblk; | |
920 | } while (hblk != holdhead[i]); | |
921 | } | |
922 | } | |
923 | } | |
924 | inf.hblkhd = (inf.smblks / numlblks) * sizeof (struct holdblk); | |
925 | /* holding block were counted in ordblks, so subtract off */ | |
926 | inf.ordblks -= inf.hblks; | |
927 | inf.uordblks -= inf.hblkhd + inf.usmblks + inf.fsmblks; | |
928 | inf.keepcost -= inf.hblks*(HEADSZ - MINHEAD); | |
929 | mutex_unlock(&mlock); | |
930 | return (inf); | |
931 | } | |
932 | ||
933 | ||
934 | /* | |
935 | * freespace - calc. how much space is used in the free | |
936 | * small blocks in a given holding block | |
937 | * | |
938 | * input - hblk = given holding block | |
939 | * | |
940 | * returns space used in free small blocks of hblk | |
941 | */ | |
942 | ||
943 | static ssize_t | |
944 | freespace(struct holdblk *holdblk) | |
945 | { | |
946 | struct lblk *lblk; | |
947 | ssize_t space = 0; | |
948 | ssize_t size; | |
949 | struct lblk *unused; | |
950 | ||
951 | lblk = CLRSMAL(holdblk->lfreeq); | |
952 | size = holdblk->blksz + sizeof (struct lblk) - sizeof (int); | |
953 | unused = CLRSMAL(holdblk->unused); | |
954 | /* follow free chain */ | |
955 | while ((lblk != LGROUND) && (lblk != unused)) { | |
956 | space += size; | |
957 | lblk = CLRSMAL(lblk->header.nextfree); | |
958 | } | |
959 | space += ((char *)holdblk + HOLDSZ(size)) - (char *)unused; | |
960 | return (space); | |
961 | } | |
962 | ||
963 | static void * | |
964 | morecore(size_t bytes) | |
965 | { | |
966 | void * ret; | |
967 | ||
968 | if (bytes > LONG_MAX) { | |
969 | intptr_t wad; | |
970 | /* | |
971 | * The request size is too big. We need to do this in | |
972 | * chunks. Sbrk only takes an int for an arg. | |
973 | */ | |
974 | if (bytes == ULONG_MAX) | |
975 | return ((void *)-1); | |
976 | ||
977 | ret = sbrk(0); | |
978 | wad = LONG_MAX; | |
979 | while (wad > 0) { | |
980 | if (sbrk(wad) == (void *)-1) { | |
981 | if (ret != sbrk(0)) | |
982 | (void) sbrk(-LONG_MAX); | |
983 | return ((void *)-1); | |
984 | } | |
985 | bytes -= LONG_MAX; | |
986 | wad = bytes; | |
987 | } | |
988 | } else | |
989 | ret = sbrk(bytes); | |
990 | ||
991 | return (ret); | |
992 | } | |
993 | ||
994 | #ifdef debug | |
995 | int | |
996 | check_arena(void) | |
997 | { | |
998 | unsigned bsize; | |
999 | struct header *blk, *prev, *next; /* ptr to ordinary blocks */ | |
1000 | ||
1001 | (void) mutex_lock(&mlock); | |
1002 | if (freeptr[0].nextfree == GROUND) { | |
1003 | (void) mutex_unlock(&mlock); | |
1004 | return (-1); | |
1005 | } | |
1006 | blk = arena + 1; | |
1007 | ||
1008 | /* loop through arena, checking */ | |
1009 | blk = (struct header *)CLRALL(blk->nextblk); | |
1010 | next = (struct header *)CLRALL(blk->nextblk); | |
1011 | while (next != arena + 1) { | |
1012 | assert(blk >= arena + 1); | |
1013 | assert(blk <= lastblk); | |
1014 | assert(next >= blk + 1); | |
1015 | assert(((unsigned)((struct header *)blk->nextblk) & | |
1016 | (4 | SMAL)) == 0); | |
1017 | ||
1018 | if (TESTBUSY(blk->nextblk) == 0) { | |
1019 | assert(blk->nextfree >= freeptr); | |
1020 | assert(blk->prevfree >= freeptr); | |
1021 | assert(blk->nextfree <= lastblk); | |
1022 | assert(blk->prevfree <= lastblk); | |
1023 | assert(((unsigned)((struct header *)blk->nextfree) & | |
1024 | 7) == 0); | |
1025 | assert(((unsigned)((struct header *)blk->prevfree) & | |
1026 | 7) == 0 || blk->prevfree == freeptr); | |
1027 | } | |
1028 | blk = next; | |
1029 | next = CLRBUSY(blk->nextblk); | |
1030 | } | |
1031 | (void) mutex_unlock(&mlock); | |
1032 | return (0); | |
1033 | } | |
1034 | ||
1035 | #define RSTALLOC 1 | |
1036 | #endif | |
1037 | ||
1038 | #ifdef RSTALLOC | |
1039 | /* | |
1040 | * rstalloc - reset alloc routines | |
1041 | * | |
1042 | * description - return allocated memory and reset | |
1043 | * allocation pointers. | |
1044 | * | |
1045 | * Warning - This is for debugging purposes only. | |
1046 | * It will return all memory allocated after | |
1047 | * the first call to malloc, even if some | |
1048 | * of it was fetched by a user's sbrk(). | |
1049 | */ | |
1050 | ||
1051 | void | |
1052 | rstalloc(void) | |
1053 | { | |
1054 | (void) mutex_lock(&mlock); | |
1055 | minhead = MINHEAD; | |
1056 | grain = ALIGNSZ; | |
1057 | numlblks = NUMLBLKS; | |
1058 | fastct = FASTCT; | |
1059 | maxfast = MAXFAST; | |
1060 | change = 0; | |
1061 | if (freeptr[0].nextfree == GROUND) { | |
1062 | (void) mutex_unlock(&mlock); | |
1063 | return; | |
1064 | } | |
1065 | brk(CLRBUSY(arena[1].nextblk)); | |
1066 | freeptr[0].nextfree = GROUND; | |
1067 | #ifdef debug | |
1068 | case1count = 0; | |
1069 | #endif | |
1070 | (void) mutex_unlock(&mlock); | |
1071 | } | |
1072 | #endif /* RSTALLOC */ | |
1073 | ||
1074 | /* | |
1075 | * cfree is an undocumented, obsolete function | |
1076 | */ | |
1077 | ||
1078 | /* ARGSUSED */ | |
1079 | void | |
1080 | _cfree(char *p, unsigned num, unsigned size) | |
1081 | { | |
1082 | free(p); | |
1083 | } |