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