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 /*
33 * Memory management: malloc(), realloc(), free().
34 *
35 * The following #-parameters may be redefined:
36 * SEGMENTED: if defined, memory requests are assumed to be
37 * non-contiguous across calls of GETCORE's.
38 * GETCORE: a function to get more core memory. If not SEGMENTED,
39 * GETCORE(0) is assumed to return the next available
40 * address. Default is 'sbrk'.
41 * ERRCORE: the error code as returned by GETCORE.
42 * Default is (char *)(-1).
43 * CORESIZE: a desired unit (measured in bytes) to be used
44 * with GETCORE. Default is (1024*ALIGN).
45 *
46 * This algorithm is based on a best fit strategy with lists of
47 * free elts maintained in a self-adjusting binary tree. Each list
48 * contains all elts of the same size. The tree is ordered by size.
49 * For results on self-adjusting trees, see the paper:
50 * Self-Adjusting Binary Trees,
51 * DD Sleator & RE Tarjan, JACM 1985.
52 *
53 * The header of a block contains the size of the data part in bytes.
54 * Since the size of a block is 0%4, the low two bits of the header
55 * are free and used as follows:
56 *
57 * BIT0: 1 for busy (block is in use), 0 for free.
58 * BIT1: if the block is busy, this bit is 1 if the
59 * preceding block in contiguous memory is free.
60 * Otherwise, it is always 0.
61 */
62
63 #include "lint.h"
64 #include "mallint.h"
65 #include "mtlib.h"
66
67 /*
68 * Some abusers of the system (notably java1.2) acquire __malloc_lock
69 * in order to prevent threads from holding it while they are being
70 * suspended via thr_suspend() or thr_suspend_allmutators().
71 * This never worked when alternate malloc() libraries were used
72 * because they don't use __malloc_lock for their locking strategy.
73 * We leave __malloc_lock as an external variable to satisfy these
74 * old programs, but we define a new lock, private to libc, to do the
75 * real locking: libc_malloc_lock. This puts libc's malloc() package
76 * on the same footing as all other malloc packages.
77 */
78 mutex_t __malloc_lock = DEFAULTMUTEX;
79 mutex_t libc_malloc_lock = DEFAULTMUTEX;
80
81 static TREE *Root, /* root of the free tree */
82 *Bottom, /* the last free chunk in the arena */
83 *_morecore(size_t); /* function to get more core */
84
85 static char *Baddr; /* current high address of the arena */
86 static char *Lfree; /* last freed block with data intact */
87
88 static void t_delete(TREE *);
89 static void t_splay(TREE *);
90 static void realfree(void *);
91 static void cleanfree(void *);
92 static void *_malloc_unlocked(size_t);
93
94 #define FREESIZE (1<<5) /* size for preserving free blocks until next malloc */
95 #define FREEMASK FREESIZE-1
96
97 static void *flist[FREESIZE]; /* list of blocks to be freed on next malloc */
98 static int freeidx; /* index of free blocks in flist % FREESIZE */
99
100 /*
101 * Interfaces used only by atfork_init() functions.
102 */
103 void
malloc_locks(void)104 malloc_locks(void)
105 {
106 (void) mutex_lock(&libc_malloc_lock);
107 }
108
109 void
malloc_unlocks(void)110 malloc_unlocks(void)
111 {
112 (void) mutex_unlock(&libc_malloc_lock);
113 }
114
115 /*
116 * Allocation of small blocks
117 */
118 static TREE *List[MINSIZE/WORDSIZE-1]; /* lists of small blocks */
119
120 static void *
_smalloc(size_t size)121 _smalloc(size_t size)
122 {
123 TREE *tp;
124 size_t i;
125
126 ASSERT(size % WORDSIZE == 0);
127 /* want to return a unique pointer on malloc(0) */
128 if (size == 0)
129 size = WORDSIZE;
130
131 /* list to use */
132 i = size / WORDSIZE - 1;
133
134 if (List[i] == NULL) {
135 TREE *np;
136 int n;
137 /* number of blocks to get at one time */
138 #define NPS (WORDSIZE*8)
139 ASSERT((size + WORDSIZE) * NPS >= MINSIZE);
140
141 /* get NPS of these block types */
142 if ((List[i] = _malloc_unlocked((size + WORDSIZE) * NPS)) == 0)
143 return (0);
144
145 /* make them into a link list */
146 for (n = 0, np = List[i]; n < NPS; ++n) {
147 tp = np;
148 SIZE(tp) = size;
149 np = NEXT(tp);
150 AFTER(tp) = np;
151 }
152 AFTER(tp) = NULL;
153 }
154
155 /* allocate from the head of the queue */
156 tp = List[i];
157 List[i] = AFTER(tp);
158 SETBIT0(SIZE(tp));
159 return (DATA(tp));
160 }
161
162 void *
malloc(size_t size)163 malloc(size_t size)
164 {
165 void *ret;
166
167 if (!primary_link_map) {
168 errno = ENOTSUP;
169 return (NULL);
170 }
171 assert_no_libc_locks_held();
172 (void) mutex_lock(&libc_malloc_lock);
173 ret = _malloc_unlocked(size);
174 (void) mutex_unlock(&libc_malloc_lock);
175 return (ret);
176 }
177
178 static void *
_malloc_unlocked(size_t size)179 _malloc_unlocked(size_t size)
180 {
181 size_t n;
182 TREE *tp, *sp;
183 size_t o_bit1;
184
185 COUNT(nmalloc);
186 ASSERT(WORDSIZE == ALIGN);
187
188 /* check for size that could overflow calculations */
189 if (size > MAX_MALLOC) {
190 errno = ENOMEM;
191 return (NULL);
192 }
193
194 /* make sure that size is 0 mod ALIGN */
195 ROUND(size);
196
197 /* see if the last free block can be used */
198 if (Lfree) {
199 sp = BLOCK(Lfree);
200 n = SIZE(sp);
201 CLRBITS01(n);
202 if (n == size) {
203 /*
204 * exact match, use it as is
205 */
206 freeidx = (freeidx + FREESIZE - 1) &
207 FREEMASK; /* 1 back */
208 flist[freeidx] = Lfree = NULL;
209 return (DATA(sp));
210 } else if (size >= MINSIZE && n > size) {
211 /*
212 * got a big enough piece
213 */
214 freeidx = (freeidx + FREESIZE - 1) &
215 FREEMASK; /* 1 back */
216 flist[freeidx] = Lfree = NULL;
217 o_bit1 = SIZE(sp) & BIT1;
218 SIZE(sp) = n;
219 goto leftover;
220 }
221 }
222 o_bit1 = 0;
223
224 /* perform free's of space since last malloc */
225 cleanfree(NULL);
226
227 /* small blocks */
228 if (size < MINSIZE)
229 return (_smalloc(size));
230
231 /* search for an elt of the right size */
232 sp = NULL;
233 n = 0;
234 if (Root) {
235 tp = Root;
236 for (;;) {
237 /* branch left */
238 if (SIZE(tp) >= size) {
239 if (n == 0 || n >= SIZE(tp)) {
240 sp = tp;
241 n = SIZE(tp);
242 }
243 if (LEFT(tp))
244 tp = LEFT(tp);
245 else
246 break;
247 } else { /* branch right */
248 if (RIGHT(tp))
249 tp = RIGHT(tp);
250 else
251 break;
252 }
253 }
254
255 if (sp) {
256 t_delete(sp);
257 } else if (tp != Root) {
258 /* make the searched-to element the root */
259 t_splay(tp);
260 Root = tp;
261 }
262 }
263
264 /* if found none fitted in the tree */
265 if (!sp) {
266 if (Bottom && size <= SIZE(Bottom)) {
267 sp = Bottom;
268 CLRBITS01(SIZE(sp));
269 } else if ((sp = _morecore(size)) == NULL) /* no more memory */
270 return (NULL);
271 }
272
273 /* tell the forward neighbor that we're busy */
274 CLRBIT1(SIZE(NEXT(sp)));
275
276 ASSERT(ISBIT0(SIZE(NEXT(sp))));
277
278 leftover:
279 /* if the leftover is enough for a new free piece */
280 if ((n = (SIZE(sp) - size)) >= MINSIZE + WORDSIZE) {
281 n -= WORDSIZE;
282 SIZE(sp) = size;
283 tp = NEXT(sp);
284 SIZE(tp) = n|BIT0;
285 realfree(DATA(tp));
286 } else if (BOTTOM(sp))
287 Bottom = NULL;
288
289 /* return the allocated space */
290 SIZE(sp) |= BIT0 | o_bit1;
291 return (DATA(sp));
292 }
293
294
295 /*
296 * realloc().
297 *
298 * If the block size is increasing, we try forward merging first.
299 * This is not best-fit but it avoids some data recopying.
300 */
301 void *
realloc(void * old,size_t size)302 realloc(void *old, size_t size)
303 {
304 TREE *tp, *np;
305 size_t ts;
306 char *new;
307
308 if (!primary_link_map) {
309 errno = ENOTSUP;
310 return (NULL);
311 }
312
313 assert_no_libc_locks_held();
314 COUNT(nrealloc);
315
316 /* check for size that could overflow calculations */
317 if (size > MAX_MALLOC) {
318 errno = ENOMEM;
319 return (NULL);
320 }
321
322 /* pointer to the block */
323 (void) mutex_lock(&libc_malloc_lock);
324 if (old == NULL) {
325 new = _malloc_unlocked(size);
326 (void) mutex_unlock(&libc_malloc_lock);
327 return (new);
328 }
329
330 /* perform free's of space since last malloc */
331 cleanfree(old);
332
333 /* make sure that size is 0 mod ALIGN */
334 ROUND(size);
335
336 tp = BLOCK(old);
337 ts = SIZE(tp);
338
339 /* if the block was freed, data has been destroyed. */
340 if (!ISBIT0(ts)) {
341 (void) mutex_unlock(&libc_malloc_lock);
342 return (NULL);
343 }
344
345 /* nothing to do */
346 CLRBITS01(SIZE(tp));
347 if (size == SIZE(tp)) {
348 SIZE(tp) = ts;
349 (void) mutex_unlock(&libc_malloc_lock);
350 return (old);
351 }
352
353 /* special cases involving small blocks */
354 if (size < MINSIZE || SIZE(tp) < MINSIZE) {
355 /* free is size is zero */
356 if (size == 0) {
357 SETOLD01(SIZE(tp), ts);
358 _free_unlocked(old);
359 (void) mutex_unlock(&libc_malloc_lock);
360 return (NULL);
361 } else {
362 goto call_malloc;
363 }
364 }
365
366 /* block is increasing in size, try merging the next block */
367 if (size > SIZE(tp)) {
368 np = NEXT(tp);
369 if (!ISBIT0(SIZE(np))) {
370 ASSERT(SIZE(np) >= MINSIZE);
371 ASSERT(!ISBIT1(SIZE(np)));
372 SIZE(tp) += SIZE(np) + WORDSIZE;
373 if (np != Bottom)
374 t_delete(np);
375 else
376 Bottom = NULL;
377 CLRBIT1(SIZE(NEXT(np)));
378 }
379
380 #ifndef SEGMENTED
381 /* not enough & at TRUE end of memory, try extending core */
382 if (size > SIZE(tp) && BOTTOM(tp) && GETCORE(0) == Baddr) {
383 Bottom = tp;
384 if ((tp = _morecore(size)) == NULL) {
385 tp = Bottom;
386 Bottom = NULL;
387 }
388 }
389 #endif
390 }
391
392 /* got enough space to use */
393 if (size <= SIZE(tp)) {
394 size_t n;
395
396 chop_big:
397 if ((n = (SIZE(tp) - size)) >= MINSIZE + WORDSIZE) {
398 n -= WORDSIZE;
399 SIZE(tp) = size;
400 np = NEXT(tp);
401 SIZE(np) = n|BIT0;
402 realfree(DATA(np));
403 } else if (BOTTOM(tp))
404 Bottom = NULL;
405
406 /* the previous block may be free */
407 SETOLD01(SIZE(tp), ts);
408 (void) mutex_unlock(&libc_malloc_lock);
409 return (old);
410 }
411
412 /* call malloc to get a new block */
413 call_malloc:
414 SETOLD01(SIZE(tp), ts);
415 if ((new = _malloc_unlocked(size)) != NULL) {
416 CLRBITS01(ts);
417 if (ts > size)
418 ts = size;
419 MEMCOPY(new, old, ts);
420 _free_unlocked(old);
421 (void) mutex_unlock(&libc_malloc_lock);
422 return (new);
423 }
424
425 /*
426 * Attempt special case recovery allocations since malloc() failed:
427 *
428 * 1. size <= SIZE(tp) < MINSIZE
429 * Simply return the existing block
430 * 2. SIZE(tp) < size < MINSIZE
431 * malloc() may have failed to allocate the chunk of
432 * small blocks. Try asking for MINSIZE bytes.
433 * 3. size < MINSIZE <= SIZE(tp)
434 * malloc() may have failed as with 2. Change to
435 * MINSIZE allocation which is taken from the beginning
436 * of the current block.
437 * 4. MINSIZE <= SIZE(tp) < size
438 * If the previous block is free and the combination of
439 * these two blocks has at least size bytes, then merge
440 * the two blocks copying the existing contents backwards.
441 */
442 CLRBITS01(SIZE(tp));
443 if (SIZE(tp) < MINSIZE) {
444 if (size < SIZE(tp)) { /* case 1. */
445 SETOLD01(SIZE(tp), ts);
446 (void) mutex_unlock(&libc_malloc_lock);
447 return (old);
448 } else if (size < MINSIZE) { /* case 2. */
449 size = MINSIZE;
450 goto call_malloc;
451 }
452 } else if (size < MINSIZE) { /* case 3. */
453 size = MINSIZE;
454 goto chop_big;
455 } else if (ISBIT1(ts) &&
456 (SIZE(np = LAST(tp)) + SIZE(tp) + WORDSIZE) >= size) {
457 ASSERT(!ISBIT0(SIZE(np)));
458 t_delete(np);
459 SIZE(np) += SIZE(tp) + WORDSIZE;
460 /*
461 * Since the copy may overlap, use memmove() if available.
462 * Otherwise, copy by hand.
463 */
464 (void) memmove(DATA(np), old, SIZE(tp));
465 old = DATA(np);
466 tp = np;
467 CLRBIT1(ts);
468 goto chop_big;
469 }
470 SETOLD01(SIZE(tp), ts);
471 (void) mutex_unlock(&libc_malloc_lock);
472 return (NULL);
473 }
474
475
476 /*
477 * realfree().
478 *
479 * Coalescing of adjacent free blocks is done first.
480 * Then, the new free block is leaf-inserted into the free tree
481 * without splaying. This strategy does not guarantee the amortized
482 * O(nlogn) behaviour for the insert/delete/find set of operations
483 * on the tree. In practice, however, free is much more infrequent
484 * than malloc/realloc and the tree searches performed by these
485 * functions adequately keep the tree in balance.
486 */
487 static void
realfree(void * old)488 realfree(void *old)
489 {
490 TREE *tp, *sp, *np;
491 size_t ts, size;
492
493 COUNT(nfree);
494
495 /* pointer to the block */
496 tp = BLOCK(old);
497 ts = SIZE(tp);
498 if (!ISBIT0(ts))
499 return;
500 CLRBITS01(SIZE(tp));
501
502 /* small block, put it in the right linked list */
503 if (SIZE(tp) < MINSIZE) {
504 ASSERT(SIZE(tp) / WORDSIZE >= 1);
505 ts = SIZE(tp) / WORDSIZE - 1;
506 AFTER(tp) = List[ts];
507 List[ts] = tp;
508 return;
509 }
510
511 /* see if coalescing with next block is warranted */
512 np = NEXT(tp);
513 if (!ISBIT0(SIZE(np))) {
514 if (np != Bottom)
515 t_delete(np);
516 SIZE(tp) += SIZE(np) + WORDSIZE;
517 }
518
519 /* the same with the preceding block */
520 if (ISBIT1(ts)) {
521 np = LAST(tp);
522 ASSERT(!ISBIT0(SIZE(np)));
523 ASSERT(np != Bottom);
524 t_delete(np);
525 SIZE(np) += SIZE(tp) + WORDSIZE;
526 tp = np;
527 }
528
529 /* initialize tree info */
530 PARENT(tp) = LEFT(tp) = RIGHT(tp) = LINKFOR(tp) = NULL;
531
532 /* the last word of the block contains self's address */
533 *(SELFP(tp)) = tp;
534
535 /* set bottom block, or insert in the free tree */
536 if (BOTTOM(tp))
537 Bottom = tp;
538 else {
539 /* search for the place to insert */
540 if (Root) {
541 size = SIZE(tp);
542 np = Root;
543 for (;;) {
544 if (SIZE(np) > size) {
545 if (LEFT(np))
546 np = LEFT(np);
547 else {
548 LEFT(np) = tp;
549 PARENT(tp) = np;
550 break;
551 }
552 } else if (SIZE(np) < size) {
553 if (RIGHT(np))
554 np = RIGHT(np);
555 else {
556 RIGHT(np) = tp;
557 PARENT(tp) = np;
558 break;
559 }
560 } else {
561 if ((sp = PARENT(np)) != NULL) {
562 if (np == LEFT(sp))
563 LEFT(sp) = tp;
564 else
565 RIGHT(sp) = tp;
566 PARENT(tp) = sp;
567 } else
568 Root = tp;
569
570 /* insert to head of list */
571 if ((sp = LEFT(np)) != NULL)
572 PARENT(sp) = tp;
573 LEFT(tp) = sp;
574
575 if ((sp = RIGHT(np)) != NULL)
576 PARENT(sp) = tp;
577 RIGHT(tp) = sp;
578
579 /* doubly link list */
580 LINKFOR(tp) = np;
581 LINKBAK(np) = tp;
582 SETNOTREE(np);
583
584 break;
585 }
586 }
587 } else
588 Root = tp;
589 }
590
591 /* tell next block that this one is free */
592 SETBIT1(SIZE(NEXT(tp)));
593
594 ASSERT(ISBIT0(SIZE(NEXT(tp))));
595 }
596
597 /*
598 * Get more core. Gaps in memory are noted as busy blocks.
599 */
600 static TREE *
_morecore(size_t size)601 _morecore(size_t size)
602 {
603 TREE *tp;
604 ssize_t n, offset;
605 char *addr;
606 ssize_t nsize;
607
608 /* compute new amount of memory to get */
609 tp = Bottom;
610 n = (ssize_t)size + 2 * WORDSIZE;
611 addr = GETCORE(0);
612
613 if (addr == ERRCORE)
614 return (NULL);
615
616 /* need to pad size out so that addr is aligned */
617 if ((((uintptr_t)addr) % ALIGN) != 0)
618 offset = ALIGN - (uintptr_t)addr % ALIGN;
619 else
620 offset = 0;
621
622 #ifndef SEGMENTED
623 /* if not segmented memory, what we need may be smaller */
624 if (addr == Baddr) {
625 n -= WORDSIZE;
626 if (tp != NULL)
627 n -= SIZE(tp);
628 }
629 #endif
630
631 /* get a multiple of CORESIZE */
632 n = ((n - 1) / CORESIZE + 1) * CORESIZE;
633 nsize = n + offset;
634
635 /* check if nsize request could overflow in GETCORE */
636 if ((size_t)nsize > MAX_MALLOC - (uintptr_t)addr) {
637 errno = ENOMEM;
638 return (NULL);
639 }
640
641 if ((size_t)nsize <= MAX_GETCORE) {
642 if (GETCORE(nsize) == ERRCORE)
643 return (NULL);
644 } else {
645 intptr_t delta;
646 /*
647 * the value required is too big for GETCORE() to deal with
648 * in one go, so use GETCORE() at most 2 times instead.
649 * Argument to GETCORE() must be multiple of ALIGN.
650 * If not, GETCORE(-MAX_GETCORE) will not return brk point
651 * to previous value, but will be ALIGN more.
652 * This would leave a small hole.
653 */
654 delta = MAX_GETCORE;
655 while (delta > 0) {
656 if (GETCORE(delta) == ERRCORE) {
657 if (addr != GETCORE(0))
658 (void) GETCORE(-MAX_GETCORE);
659 return (NULL);
660 }
661 nsize -= MAX_GETCORE;
662 delta = nsize;
663 }
664 }
665
666 /* contiguous memory */
667 if (addr == Baddr) {
668 ASSERT(offset == 0);
669 if (tp) {
670 addr = (char *)tp;
671 n += SIZE(tp) + 2 * WORDSIZE;
672 } else {
673 addr = Baddr - WORDSIZE;
674 n += WORDSIZE;
675 }
676 } else
677 addr += offset;
678
679 /* new bottom address */
680 Baddr = addr + n;
681
682 /* new bottom block */
683 tp = (TREE *)(uintptr_t)addr;
684 SIZE(tp) = n - 2 * WORDSIZE;
685 ASSERT((SIZE(tp) % ALIGN) == 0);
686
687 /* reserved the last word to head any noncontiguous memory */
688 SETBIT0(SIZE(NEXT(tp)));
689
690 /* non-contiguous memory, free old bottom block */
691 if (Bottom && Bottom != tp) {
692 SETBIT0(SIZE(Bottom));
693 realfree(DATA(Bottom));
694 }
695
696 return (tp);
697 }
698
699
700 /*
701 * Tree rotation functions (BU: bottom-up, TD: top-down)
702 */
703
704 #define LEFT1(x, y) \
705 if ((RIGHT(x) = LEFT(y)) != NULL) PARENT(RIGHT(x)) = x;\
706 if ((PARENT(y) = PARENT(x)) != NULL)\
707 if (LEFT(PARENT(x)) == x) LEFT(PARENT(y)) = y;\
708 else RIGHT(PARENT(y)) = y;\
709 LEFT(y) = x; PARENT(x) = y
710
711 #define RIGHT1(x, y) \
712 if ((LEFT(x) = RIGHT(y)) != NULL) PARENT(LEFT(x)) = x;\
713 if ((PARENT(y) = PARENT(x)) != NULL)\
714 if (LEFT(PARENT(x)) == x) LEFT(PARENT(y)) = y;\
715 else RIGHT(PARENT(y)) = y;\
716 RIGHT(y) = x; PARENT(x) = y
717
718 #define BULEFT2(x, y, z) \
719 if ((RIGHT(x) = LEFT(y)) != NULL) PARENT(RIGHT(x)) = x;\
720 if ((RIGHT(y) = LEFT(z)) != NULL) PARENT(RIGHT(y)) = y;\
721 if ((PARENT(z) = PARENT(x)) != NULL)\
722 if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\
723 else RIGHT(PARENT(z)) = z;\
724 LEFT(z) = y; PARENT(y) = z; LEFT(y) = x; PARENT(x) = y
725
726 #define BURIGHT2(x, y, z) \
727 if ((LEFT(x) = RIGHT(y)) != NULL) PARENT(LEFT(x)) = x;\
728 if ((LEFT(y) = RIGHT(z)) != NULL) PARENT(LEFT(y)) = y;\
729 if ((PARENT(z) = PARENT(x)) != NULL)\
730 if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\
731 else RIGHT(PARENT(z)) = z;\
732 RIGHT(z) = y; PARENT(y) = z; RIGHT(y) = x; PARENT(x) = y
733
734 #define TDLEFT2(x, y, z) \
735 if ((RIGHT(y) = LEFT(z)) != NULL) PARENT(RIGHT(y)) = y;\
736 if ((PARENT(z) = PARENT(x)) != NULL)\
737 if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\
738 else RIGHT(PARENT(z)) = z;\
739 PARENT(x) = z; LEFT(z) = x;
740
741 #define TDRIGHT2(x, y, z) \
742 if ((LEFT(y) = RIGHT(z)) != NULL) PARENT(LEFT(y)) = y;\
743 if ((PARENT(z) = PARENT(x)) != NULL)\
744 if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\
745 else RIGHT(PARENT(z)) = z;\
746 PARENT(x) = z; RIGHT(z) = x;
747
748 /*
749 * Delete a tree element
750 */
751 static void
t_delete(TREE * op)752 t_delete(TREE *op)
753 {
754 TREE *tp, *sp, *gp;
755
756 /* if this is a non-tree node */
757 if (ISNOTREE(op)) {
758 tp = LINKBAK(op);
759 if ((sp = LINKFOR(op)) != NULL)
760 LINKBAK(sp) = tp;
761 LINKFOR(tp) = sp;
762 return;
763 }
764
765 /* make op the root of the tree */
766 if (PARENT(op))
767 t_splay(op);
768
769 /* if this is the start of a list */
770 if ((tp = LINKFOR(op)) != NULL) {
771 PARENT(tp) = NULL;
772 if ((sp = LEFT(op)) != NULL)
773 PARENT(sp) = tp;
774 LEFT(tp) = sp;
775
776 if ((sp = RIGHT(op)) != NULL)
777 PARENT(sp) = tp;
778 RIGHT(tp) = sp;
779
780 Root = tp;
781 return;
782 }
783
784 /* if op has a non-null left subtree */
785 if ((tp = LEFT(op)) != NULL) {
786 PARENT(tp) = NULL;
787
788 if (RIGHT(op)) {
789 /* make the right-end of the left subtree its root */
790 while ((sp = RIGHT(tp)) != NULL) {
791 if ((gp = RIGHT(sp)) != NULL) {
792 TDLEFT2(tp, sp, gp);
793 tp = gp;
794 } else {
795 LEFT1(tp, sp);
796 tp = sp;
797 }
798 }
799
800 /* hook the right subtree of op to the above elt */
801 RIGHT(tp) = RIGHT(op);
802 PARENT(RIGHT(tp)) = tp;
803 }
804 } else if ((tp = RIGHT(op)) != NULL) /* no left subtree */
805 PARENT(tp) = NULL;
806
807 Root = tp;
808 }
809
810 /*
811 * Bottom up splaying (simple version).
812 * The basic idea is to roughly cut in half the
813 * path from Root to tp and make tp the new root.
814 */
815 static void
t_splay(TREE * tp)816 t_splay(TREE *tp)
817 {
818 TREE *pp, *gp;
819
820 /* iterate until tp is the root */
821 while ((pp = PARENT(tp)) != NULL) {
822 /* grandparent of tp */
823 gp = PARENT(pp);
824
825 /* x is a left child */
826 if (LEFT(pp) == tp) {
827 if (gp && LEFT(gp) == pp) {
828 BURIGHT2(gp, pp, tp);
829 } else {
830 RIGHT1(pp, tp);
831 }
832 } else {
833 ASSERT(RIGHT(pp) == tp);
834 if (gp && RIGHT(gp) == pp) {
835 BULEFT2(gp, pp, tp);
836 } else {
837 LEFT1(pp, tp);
838 }
839 }
840 }
841 }
842
843
844 /*
845 * free().
846 * Performs a delayed free of the block pointed to
847 * by old. The pointer to old is saved on a list, flist,
848 * until the next malloc or realloc. At that time, all the
849 * blocks pointed to in flist are actually freed via
850 * realfree(). This allows the contents of free blocks to
851 * remain undisturbed until the next malloc or realloc.
852 */
853 void
free(void * old)854 free(void *old)
855 {
856 if (!primary_link_map) {
857 errno = ENOTSUP;
858 return;
859 }
860 assert_no_libc_locks_held();
861 (void) mutex_lock(&libc_malloc_lock);
862 _free_unlocked(old);
863 (void) mutex_unlock(&libc_malloc_lock);
864 }
865
866
867 void
_free_unlocked(void * old)868 _free_unlocked(void *old)
869 {
870 int i;
871
872 if (old == NULL)
873 return;
874
875 /*
876 * Make sure the same data block is not freed twice.
877 * 3 cases are checked. It returns immediately if either
878 * one of the conditions is true.
879 * 1. Last freed.
880 * 2. Not in use or freed already.
881 * 3. In the free list.
882 */
883 if (old == Lfree)
884 return;
885 if (!ISBIT0(SIZE(BLOCK(old))))
886 return;
887 for (i = 0; i < freeidx; i++)
888 if (old == flist[i])
889 return;
890
891 if (flist[freeidx] != NULL)
892 realfree(flist[freeidx]);
893 flist[freeidx] = Lfree = old;
894 freeidx = (freeidx + 1) & FREEMASK; /* one forward */
895 }
896
897 /*
898 * cleanfree() frees all the blocks pointed to be flist.
899 *
900 * realloc() should work if it is called with a pointer
901 * to a block that was freed since the last call to malloc() or
902 * realloc(). If cleanfree() is called from realloc(), ptr
903 * is set to the old block and that block should not be
904 * freed since it is actually being reallocated.
905 */
906 static void
cleanfree(void * ptr)907 cleanfree(void *ptr)
908 {
909 char **flp;
910
911 flp = (char **)&(flist[freeidx]);
912 for (;;) {
913 if (flp == (char **)&(flist[0]))
914 flp = (char **)&(flist[FREESIZE]);
915 if (*--flp == NULL)
916 break;
917 if (*flp != ptr)
918 realfree(*flp);
919 *flp = NULL;
920 }
921 freeidx = 0;
922 Lfree = NULL;
923 }
924