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 /*
31 * Memory management: malloc(), realloc(), free(), memalign().
32 *
33 * The following #-parameters may be redefined:
34 * GETCORE: a function to get more core memory.
35 * GETCORE(0) is assumed to return the next available
36 * address. Default is 'sbrk'.
37 * ERRCORE: the error code as returned by GETCORE.
38 * Default is ((char *)(-1)).
39 * CORESIZE: a desired unit (measured in bytes) to be used
40 * with GETCORE. Default is (1024*ALIGN).
41 *
42 * This algorithm is based on a best fit strategy with lists of
43 * free elts maintained in a self-adjusting binary tree. Each list
44 * contains all elts of the same size. The tree is ordered by size.
45 * For results on self-adjusting trees, see the paper:
46 * Self-Adjusting Binary Trees,
47 * DD Sleator & RE Tarjan, JACM 1985.
48 *
49 * The header of a block contains the size of the data part in bytes.
50 * Since the size of a block is 0%4, the low two bits of the header
51 * are free and used as follows:
52 *
53 * BIT0: 1 for busy (block is in use), 0 for free.
54 * BIT1: if the block is busy, this bit is 1 if the
55 * preceding block in contiguous memory is free.
56 * Otherwise, it is always 0.
57 */
58
59 #include "mallint.h"
60
61 static mutex_t __watch_malloc_lock = DEFAULTMUTEX;
62
63 static TREE *Root; /* root of the free tree */
64 static TREE *Bottom; /* the last free chunk in the arena */
65 static char *Baddr; /* current high address of the arena */
66
67 static void t_delete(TREE *);
68 static void t_splay(TREE *);
69 static void realfree(void *);
70 static void *malloc_unlocked(size_t);
71 static void free_unlocked(void *);
72 static TREE *morecore(size_t);
73
74 static void protect(TREE *);
75 static void unprotect(TREE *);
76
77 #define FREEPAT 0
78 #define LIVEPAT 1
79
80 /*
81 * Patterns to be copied into freed blocks and allocated blocks.
82 * 0xfeedbeef and 0xfeedface are invalid pointer values in all programs.
83 */
84 static uint64_t patterns[2] = {
85 0xdeadbeefdeadbeefULL, /* pattern in a freed block */
86 0xbaddcafebaddcafeULL /* pattern in an allocated block */
87 };
88
89 static void
copy_pattern(int pat,TREE * tp)90 copy_pattern(int pat, TREE *tp)
91 {
92 uint64_t pattern = patterns[pat];
93 size_t sz = SIZE(tp) / sizeof (uint64_t);
94 /* LINTED improper alignment */
95 uint64_t *datap = (uint64_t *)DATA(tp);
96
97 while (sz--)
98 *datap++ = pattern;
99 }
100
101 /*
102 * Keep lists of small blocks, LIFO order.
103 */
104 static TREE *List[MINSIZE/WORDSIZE-1];
105 static TREE *Last[MINSIZE/WORDSIZE-1];
106
107 /* number of blocks to get at one time */
108 #define NPS (WORDSIZE*8)
109
110 static void *
smalloc(size_t size)111 smalloc(size_t size)
112 {
113 TREE *tp;
114 size_t i;
115
116 ASSERT(size % WORDSIZE == 0);
117 /* want to return a unique pointer on malloc(0) */
118 if (size == 0)
119 size = WORDSIZE;
120
121 /* list to use */
122 i = size / WORDSIZE - 1;
123
124 if (List[i] == NULL) {
125 TREE *np;
126 int n;
127 ASSERT((size + WORDSIZE) * NPS >= MINSIZE);
128
129 /* get NPS of these block types */
130 if ((np = malloc_unlocked((size + WORDSIZE)*NPS)) == NULL)
131 return (NULL);
132
133 /* make them into a link list */
134 for (n = 0, List[i] = np; n < NPS; ++n) {
135 tp = np;
136 SIZE(tp) = size;
137 copy_pattern(FREEPAT, tp);
138 if (n == NPS - 1) {
139 Last[i] = tp;
140 np = NULL;
141 } else {
142 /* LINTED improper alignment */
143 np = NEXT(tp);
144 }
145 AFTER(tp) = np;
146 protect(tp);
147 }
148 }
149
150 /* allocate from the head of the queue */
151 tp = List[i];
152 unprotect(tp);
153 if ((List[i] = AFTER(tp)) == NULL)
154 Last[i] = NULL;
155 copy_pattern(LIVEPAT, tp);
156 SETBIT0(SIZE(tp));
157 protect(tp);
158 return (DATA(tp));
159 }
160
161 void *
malloc(size_t size)162 malloc(size_t size)
163 {
164 void *ret;
165 (void) mutex_lock(&__watch_malloc_lock);
166 ret = malloc_unlocked(size);
167 (void) mutex_unlock(&__watch_malloc_lock);
168 return (ret);
169 }
170
171 static void *
malloc_unlocked(size_t size)172 malloc_unlocked(size_t size)
173 {
174 size_t n;
175 TREE *tp, *sp, *tmp;
176
177 COUNT(nmalloc);
178 ASSERT(WORDSIZE == ALIGN);
179
180 /* check for size that could overflow calculations */
181 if (size > MAX_MALLOC) {
182 errno = ENOMEM;
183 return (NULL);
184 }
185 /* make sure that size is 0 mod ALIGN */
186 ROUND(size);
187
188 /* small blocks */
189 if (size < MINSIZE)
190 return (smalloc(size));
191
192 /* search for an elt of the right size */
193 sp = NULL;
194 n = 0;
195 if (Root) {
196 tp = Root;
197 for (;;) {
198 unprotect(tp);
199 if (SIZE(tp) >= size) { /* branch left */
200 if (n == 0 || n >= SIZE(tp)) {
201 sp = tp;
202 n = SIZE(tp);
203 }
204 if ((tmp = LEFT(tp)) != NULL) {
205 protect(tp);
206 tp = tmp;
207 } else {
208 protect(tp);
209 break;
210 }
211 } else { /* branch right */
212 if ((tmp = RIGHT(tp)) != NULL) {
213 protect(tp);
214 tp = tmp;
215 } else {
216 protect(tp);
217 break;
218 }
219 }
220 }
221
222 if (sp) {
223 unprotect(sp);
224 t_delete(sp);
225 } else if (tp != Root) {
226 /* make the searched-to element the root */
227 unprotect(tp);
228 t_splay(tp);
229 protect(tp);
230 Root = tp;
231 }
232 }
233
234 /* if found none fitted in the tree */
235 if (sp == NULL) {
236 if (Bottom) {
237 unprotect(Bottom);
238 if (size <= SIZE(Bottom)) {
239 sp = Bottom;
240 CLRBITS01(SIZE(sp));
241 } else {
242 protect(Bottom);
243 if ((sp = morecore(size)) == NULL)
244 return (NULL);
245 }
246 } else {
247 if ((sp = morecore(size)) == NULL)
248 return (NULL);
249 }
250 }
251
252 /* tell the forward neighbor that we're busy */
253 /* LINTED improper alignment */
254 tmp = NEXT(sp);
255 unprotect(tmp);
256 CLRBIT1(SIZE(tmp));
257 ASSERT(ISBIT0(SIZE(tmp)));
258 protect(tmp);
259
260 /* if the leftover is enough for a new free piece */
261 if ((n = (SIZE(sp) - size)) >= MINSIZE + WORDSIZE) {
262 n -= WORDSIZE;
263 SIZE(sp) = size;
264 /* LINTED improper alignment */
265 tp = NEXT(sp);
266 SIZE(tp) = n | BIT0;
267 realfree(DATA(tp));
268 } else if (BOTTOM(sp))
269 Bottom = NULL;
270
271 /* return the allocated space */
272 copy_pattern(LIVEPAT, sp);
273 SIZE(sp) |= BIT0;
274 protect(sp);
275 return (DATA(sp));
276 }
277
278 /*
279 * realloc().
280 * If the block size is increasing, we try forward merging first.
281 * This is not best-fit but it avoids some data recopying.
282 */
283 void *
realloc(void * old,size_t size)284 realloc(void *old, size_t size)
285 {
286 TREE *tp, *np;
287 size_t ts;
288 char *new;
289
290 COUNT(nrealloc);
291
292 /* check for size that could overflow calculations */
293 if (size > MAX_MALLOC) {
294 errno = ENOMEM;
295 return (NULL);
296 }
297
298 /* pointer to the block */
299 (void) mutex_lock(&__watch_malloc_lock);
300 if (old == NULL) {
301 new = malloc_unlocked(size);
302 (void) mutex_unlock(&__watch_malloc_lock);
303 return (new);
304 }
305
306 /* make sure that size is 0 mod ALIGN */
307 ROUND(size);
308
309 /* LINTED improper alignment */
310 tp = BLOCK(old);
311 unprotect(tp);
312 ts = SIZE(tp);
313
314 /* if the block was freed, data has been destroyed. */
315 if (!ISBIT0(ts)) {
316 /* XXX; complain here! */
317 protect(tp);
318 (void) mutex_unlock(&__watch_malloc_lock);
319 errno = EINVAL;
320 return (NULL);
321 }
322
323 CLRBITS01(SIZE(tp));
324 if (size == SIZE(tp)) { /* nothing to do */
325 SIZE(tp) = ts;
326 protect(tp);
327 (void) mutex_unlock(&__watch_malloc_lock);
328 return (old);
329 }
330
331 /* special cases involving small blocks */
332 if (size < MINSIZE || SIZE(tp) < MINSIZE) {
333 if (size == 0) {
334 SETOLD01(SIZE(tp), ts);
335 free_unlocked(old);
336 (void) mutex_unlock(&__watch_malloc_lock);
337 return (NULL);
338 }
339 goto call_malloc;
340 }
341
342 /* block is increasing in size, try merging the next block */
343 if (size > SIZE(tp)) {
344 /* LINTED improper alignment */
345 np = NEXT(tp);
346 unprotect(np);
347 if (ISBIT0(SIZE(np)))
348 protect(np);
349 else {
350 TREE *tmp;
351 ASSERT(SIZE(np) >= MINSIZE);
352 ASSERT(!ISBIT1(SIZE(np)));
353 SIZE(tp) += SIZE(np) + WORDSIZE;
354 if (np != Bottom)
355 t_delete(np);
356 else
357 Bottom = NULL;
358 /* LINTED improper alignment */
359 tmp = NEXT(np);
360 unprotect(tmp);
361 CLRBIT1(SIZE(tmp));
362 protect(tmp);
363 }
364
365 /* not enough & at TRUE end of memory, try extending core */
366 if (size > SIZE(tp) && BOTTOM(tp) && GETCORE(0) == Baddr) {
367 Bottom = tp;
368 protect(Bottom);
369 if ((tp = morecore(size)) == NULL) {
370 tp = Bottom;
371 Bottom = NULL;
372 unprotect(tp);
373 }
374 }
375 }
376
377 /* got enough space to use */
378 if (size <= SIZE(tp)) {
379 size_t n;
380 chop_big:
381 if ((n = (SIZE(tp) - size)) >= MINSIZE + WORDSIZE) {
382 n -= WORDSIZE;
383 SIZE(tp) = size;
384 /* LINTED improper alignment */
385 np = NEXT(tp);
386 SIZE(np) = n | BIT0;
387 realfree(DATA(np));
388 } else if (BOTTOM(tp))
389 Bottom = NULL;
390
391 /* the previous block may be free */
392 SETOLD01(SIZE(tp), ts);
393 protect(tp);
394 (void) mutex_unlock(&__watch_malloc_lock);
395 return (old);
396 }
397
398 call_malloc: /* call malloc to get a new block */
399 SETOLD01(SIZE(tp), ts);
400 if ((new = malloc_unlocked(size)) != NULL) {
401 CLRBITS01(ts);
402 if (ts > size)
403 ts = size;
404 (void) memcpy(new, old, ts);
405 free_unlocked(old);
406 (void) mutex_unlock(&__watch_malloc_lock);
407 return (new);
408 }
409
410 /*
411 * Attempt special case recovery allocations since malloc() failed:
412 *
413 * 1. size <= SIZE(tp) < MINSIZE
414 * Simply return the existing block
415 * 2. SIZE(tp) < size < MINSIZE
416 * malloc() may have failed to allocate the chunk of
417 * small blocks. Try asking for MINSIZE bytes.
418 * 3. size < MINSIZE <= SIZE(tp)
419 * malloc() may have failed as with 2. Change to
420 * MINSIZE allocation which is taken from the beginning
421 * of the current block.
422 * 4. MINSIZE <= SIZE(tp) < size
423 * If the previous block is free and the combination of
424 * these two blocks has at least size bytes, then merge
425 * the two blocks copying the existing contents backwards.
426 */
427 CLRBITS01(SIZE(tp));
428 if (SIZE(tp) < MINSIZE) {
429 if (size < SIZE(tp)) /* case 1. */ {
430 SETOLD01(SIZE(tp), ts);
431 protect(tp);
432 (void) mutex_unlock(&__watch_malloc_lock);
433 return (old);
434 } else if (size < MINSIZE) /* case 2. */ {
435 size = MINSIZE;
436 goto call_malloc;
437 }
438 } else if (size < MINSIZE) /* case 3. */ {
439 size = MINSIZE;
440 goto chop_big;
441 } else if (ISBIT1(ts)) {
442 np = LAST(tp);
443 unprotect(np);
444 if ((SIZE(np) + SIZE(tp) + WORDSIZE) >= size) {
445 ASSERT(!ISBIT0(SIZE(np)));
446 t_delete(np);
447 SIZE(np) += SIZE(tp) + WORDSIZE;
448 /*
449 * Since the copy may overlap, use memmove().
450 */
451 (void) memmove(DATA(np), old, SIZE(tp));
452 old = DATA(np);
453 tp = np;
454 CLRBIT1(ts);
455 goto chop_big;
456 }
457 protect(np);
458 }
459 SETOLD01(SIZE(tp), ts);
460 protect(tp);
461 (void) mutex_unlock(&__watch_malloc_lock);
462 /* malloc() sets errno */
463 return (NULL);
464 }
465
466 /*
467 * realfree().
468 * Coalescing of adjacent free blocks is done first.
469 * Then, the new free block is leaf-inserted into the free tree
470 * without splaying. This strategy does not guarantee the amortized
471 * O(nlogn) behaviour for the insert/delete/find set of operations
472 * on the tree. In practice, however, free is much more infrequent
473 * than malloc/realloc and the tree searches performed by these
474 * functions adequately keep the tree in balance.
475 */
476 static void
realfree(void * old)477 realfree(void *old)
478 {
479 TREE *tp, *sp, *np, *tmp;
480 size_t ts, size;
481
482 COUNT(nfree);
483
484 /* pointer to the block */
485 /* LINTED improper alignment */
486 tp = BLOCK(old);
487 unprotect(tp);
488 ts = SIZE(tp);
489 if (!ISBIT0(ts)) { /* block is not busy; previously freed? */
490 protect(tp); /* force a watchpoint trap */
491 CLRBIT0(SIZE(tp));
492 return;
493 }
494 CLRBITS01(SIZE(tp));
495 copy_pattern(FREEPAT, tp);
496
497 /* small block, return it to the tail of its queue */
498 if (SIZE(tp) < MINSIZE) {
499 ASSERT(SIZE(tp) / WORDSIZE >= 1);
500 ts = SIZE(tp) / WORDSIZE - 1;
501 AFTER(tp) = NULL;
502 protect(tp);
503 if (List[ts] == NULL) {
504 List[ts] = tp;
505 Last[ts] = tp;
506 } else {
507 sp = Last[ts];
508 unprotect(sp);
509 AFTER(sp) = tp;
510 protect(sp);
511 Last[ts] = tp;
512 }
513 return;
514 }
515
516 /* see if coalescing with next block is warranted */
517 /* LINTED improper alignment */
518 np = NEXT(tp);
519 unprotect(np);
520 if (ISBIT0(SIZE(np)))
521 protect(np);
522 else {
523 if (np != Bottom)
524 t_delete(np);
525 SIZE(tp) += SIZE(np) + WORDSIZE;
526 }
527
528 /* the same with the preceding block */
529 if (ISBIT1(ts)) {
530 np = LAST(tp);
531 unprotect(np);
532 ASSERT(!ISBIT0(SIZE(np)));
533 ASSERT(np != Bottom);
534 t_delete(np);
535 SIZE(np) += SIZE(tp) + WORDSIZE;
536 tp = np;
537 }
538
539 /* initialize tree info */
540 PARENT(tp) = LEFT(tp) = RIGHT(tp) = LINKFOR(tp) = NULL;
541
542 /* set bottom block, or insert in the free tree */
543 if (BOTTOM(tp))
544 Bottom = tp;
545 else {
546 /* search for the place to insert */
547 if (Root) {
548 size = SIZE(tp);
549 np = Root;
550 for (;;) {
551 unprotect(np);
552 if (SIZE(np) > size) {
553 if ((tmp = LEFT(np)) != NULL) {
554 protect(np);
555 np = tmp;
556 } else {
557 LEFT(np) = tp;
558 PARENT(tp) = np;
559 protect(np);
560 break;
561 }
562 } else if (SIZE(np) < size) {
563 if ((tmp = RIGHT(np)) != NULL) {
564 protect(np);
565 np = tmp;
566 } else {
567 RIGHT(np) = tp;
568 PARENT(tp) = np;
569 protect(np);
570 break;
571 }
572 } else {
573 if ((sp = PARENT(np)) != NULL) {
574 unprotect(sp);
575 if (np == LEFT(sp))
576 LEFT(sp) = tp;
577 else
578 RIGHT(sp) = tp;
579 PARENT(tp) = sp;
580 protect(sp);
581 } else
582 Root = tp;
583
584 /* insert to head of list */
585 if ((sp = LEFT(np)) != NULL) {
586 unprotect(sp);
587 PARENT(sp) = tp;
588 protect(sp);
589 }
590 LEFT(tp) = sp;
591
592 if ((sp = RIGHT(np)) != NULL) {
593 unprotect(sp);
594 PARENT(sp) = tp;
595 protect(sp);
596 }
597 RIGHT(tp) = sp;
598
599 /* doubly link list */
600 LINKFOR(tp) = np;
601 LINKBAK(np) = tp;
602 SETNOTREE(np);
603 protect(np);
604
605 break;
606 }
607 }
608 } else {
609 Root = tp;
610 }
611 }
612
613 /*
614 * Tell next block that this one is free.
615 * The first WORD of the next block contains self's address.
616 */
617 /* LINTED improper alignment */
618 tmp = NEXT(tp);
619 unprotect(tmp);
620 /* LINTED improper alignment */
621 *(SELFP(tp)) = tp;
622 SETBIT1(SIZE(tmp));
623 ASSERT(ISBIT0(SIZE(tmp)));
624 protect(tmp);
625 protect(tp);
626 }
627
628 /*
629 * Get more core. Gaps in memory are noted as busy blocks.
630 */
631 static TREE *
morecore(size_t size)632 morecore(size_t size)
633 {
634 TREE *tp;
635 size_t n, offset, requestsize;
636 char *addr;
637
638 /* compute new amount of memory to get */
639 tp = Bottom;
640 n = size + 2 * WORDSIZE;
641 addr = GETCORE(0);
642
643 if (addr == ERRCORE)
644 /* errno set by GETCORE sbrk */
645 return (NULL);
646
647 /* need to pad size out so that addr is aligned */
648 if ((((size_t)addr) % ALIGN) != 0)
649 offset = ALIGN - (size_t)addr % ALIGN;
650 else
651 offset = 0;
652
653 if (tp)
654 unprotect(tp);
655
656 /* if not segmented memory, what we need may be smaller */
657 if (addr == Baddr) {
658 n -= WORDSIZE;
659 if (tp != NULL)
660 n -= SIZE(tp);
661 }
662
663 /* get a multiple of CORESIZE */
664 n = ((n - 1) / CORESIZE + 1) * CORESIZE;
665 requestsize = n + offset;
666
667 /* check if nsize request could overflow in GETCORE */
668 if (requestsize > MAX_MALLOC - (size_t)addr) {
669 if (tp)
670 protect(tp);
671 errno = ENOMEM;
672 return (NULL);
673 }
674
675 if (requestsize > MAX_GETCORE) {
676 intptr_t delta;
677 /*
678 * the value required is too big for GETCORE() to deal with
679 * in one go, so use GETCORE() at most 2 times instead.
680 * Argument to GETCORE() must be multiple of ALIGN.
681 * If not, GETCORE(-MAX_GETCORE) will not return brk point
682 * to previous value, but will be ALIGN more.
683 * This would leave a small hole.
684 */
685 delta = MAX_GETCORE;
686 while (delta > 0) {
687 if (GETCORE(delta) == ERRCORE) {
688 if (tp)
689 protect(tp);
690 if (addr != GETCORE(0))
691 (void) GETCORE(-MAX_GETCORE);
692 return (NULL);
693 }
694 requestsize -= MAX_GETCORE;
695 delta = requestsize;
696 }
697 } else if (GETCORE(requestsize) == ERRCORE) {
698 if (tp)
699 protect(tp);
700 return (NULL);
701 }
702
703 /* contiguous memory */
704 if (addr == Baddr) {
705 ASSERT(offset == 0);
706 if (tp) {
707 addr = ((char *)tp);
708 n += SIZE(tp) + 2 * WORDSIZE;
709 } else {
710 addr = Baddr - WORDSIZE;
711 n += WORDSIZE;
712 }
713 } else {
714 addr += offset;
715 }
716
717 /* new bottom address */
718 Baddr = addr + n;
719
720 /* new bottom block */
721 /* LINTED improper alignment */
722 tp = ((TREE *)addr);
723 SIZE(tp) = n - 2 * WORDSIZE;
724 ASSERT((SIZE(tp) % ALIGN) == 0);
725
726 /* reserved the last word to head any noncontiguous memory */
727 /* LINTED improper alignment */
728 SETBIT0(SIZE(NEXT(tp)));
729
730 /* non-contiguous memory, free old bottom block */
731 if (Bottom && Bottom != tp) {
732 SETBIT0(SIZE(Bottom));
733 realfree(DATA(Bottom));
734 }
735
736 return (tp);
737 }
738
739 /*
740 * Utility function to avoid protecting a tree node twice.
741 * Return true if tp is in the NULL-terminated array of tree nodes.
742 */
743 static int
in_list(TREE * tp,TREE ** npp)744 in_list(TREE *tp, TREE **npp)
745 {
746 TREE *sp;
747
748 while ((sp = *npp++) != NULL)
749 if (tp == sp)
750 return (1);
751 return (0);
752 }
753
754 /*
755 * Tree rotation functions (BU: bottom-up, TD: top-down).
756 * All functions are entered with the arguments unprotected.
757 * They must return in the same condition, with all other elements
758 * that have been unprotected during the operation re-protected.
759 */
760 static void
LEFT1(TREE * x,TREE * y)761 LEFT1(TREE *x, TREE *y)
762 {
763 TREE *node[3];
764 TREE **npp = node;
765 TREE *tp;
766
767 if ((RIGHT(x) = LEFT(y)) != NULL) {
768 unprotect(*npp++ = RIGHT(x));
769 PARENT(RIGHT(x)) = x;
770 }
771 if ((PARENT(y) = PARENT(x)) != NULL) {
772 unprotect(*npp++ = PARENT(x));
773 if (LEFT(PARENT(x)) == x)
774 LEFT(PARENT(y)) = y;
775 else
776 RIGHT(PARENT(y)) = y;
777 }
778 LEFT(y) = x;
779 PARENT(x) = y;
780
781 *npp = NULL;
782 npp = node;
783 while ((tp = *npp++) != NULL)
784 if (tp != x && tp != y && !in_list(tp, npp))
785 protect(tp);
786 }
787
788 static void
RIGHT1(TREE * x,TREE * y)789 RIGHT1(TREE *x, TREE *y)
790 {
791 TREE *node[3];
792 TREE **npp = node;
793 TREE *tp;
794
795 if ((LEFT(x) = RIGHT(y)) != NULL) {
796 unprotect(*npp++ = LEFT(x));
797 PARENT(LEFT(x)) = x;
798 }
799 if ((PARENT(y) = PARENT(x)) != NULL) {
800 unprotect(*npp++ = PARENT(x));
801 if (LEFT(PARENT(x)) == x)
802 LEFT(PARENT(y)) = y;
803 else
804 RIGHT(PARENT(y)) = y;
805 }
806 RIGHT(y) = x;
807 PARENT(x) = y;
808
809 *npp = NULL;
810 npp = node;
811 while ((tp = *npp++) != NULL)
812 if (tp != x && tp != y && !in_list(tp, npp))
813 protect(tp);
814 }
815
816 static void
BULEFT2(TREE * x,TREE * y,TREE * z)817 BULEFT2(TREE *x, TREE *y, TREE *z)
818 {
819 TREE *node[4];
820 TREE **npp = node;
821 TREE *tp;
822
823 if ((RIGHT(x) = LEFT(y)) != NULL) {
824 unprotect(*npp++ = RIGHT(x));
825 PARENT(RIGHT(x)) = x;
826 }
827 if ((RIGHT(y) = LEFT(z)) != NULL) {
828 unprotect(*npp++ = RIGHT(y));
829 PARENT(RIGHT(y)) = y;
830 }
831 if ((PARENT(z) = PARENT(x)) != NULL) {
832 unprotect(*npp++ = PARENT(x));
833 if (LEFT(PARENT(x)) == x)
834 LEFT(PARENT(z)) = z;
835 else
836 RIGHT(PARENT(z)) = z;
837 }
838 LEFT(z) = y;
839 PARENT(y) = z;
840 LEFT(y) = x;
841 PARENT(x) = y;
842
843 *npp = NULL;
844 npp = node;
845 while ((tp = *npp++) != NULL)
846 if (tp != x && tp != y && tp != z && !in_list(tp, npp))
847 protect(tp);
848 }
849
850 static void
BURIGHT2(TREE * x,TREE * y,TREE * z)851 BURIGHT2(TREE *x, TREE *y, TREE *z)
852 {
853 TREE *node[4];
854 TREE **npp = node;
855 TREE *tp;
856
857 if ((LEFT(x) = RIGHT(y)) != NULL) {
858 unprotect(*npp++ = LEFT(x));
859 PARENT(LEFT(x)) = x;
860 }
861 if ((LEFT(y) = RIGHT(z)) != NULL) {
862 unprotect(*npp++ = LEFT(y));
863 PARENT(LEFT(y)) = y;
864 }
865 if ((PARENT(z) = PARENT(x)) != NULL) {
866 unprotect(*npp++ = PARENT(x));
867 if (LEFT(PARENT(x)) == x)
868 LEFT(PARENT(z)) = z;
869 else
870 RIGHT(PARENT(z)) = z;
871 }
872 RIGHT(z) = y;
873 PARENT(y) = z;
874 RIGHT(y) = x;
875 PARENT(x) = y;
876
877 *npp = NULL;
878 npp = node;
879 while ((tp = *npp++) != NULL)
880 if (tp != x && tp != y && tp != z && !in_list(tp, npp))
881 protect(tp);
882 }
883
884 static void
TDLEFT2(TREE * x,TREE * y,TREE * z)885 TDLEFT2(TREE *x, TREE *y, TREE *z)
886 {
887 TREE *node[3];
888 TREE **npp = node;
889 TREE *tp;
890
891 if ((RIGHT(y) = LEFT(z)) != NULL) {
892 unprotect(*npp++ = RIGHT(y));
893 PARENT(RIGHT(y)) = y;
894 }
895 if ((PARENT(z) = PARENT(x)) != NULL) {
896 unprotect(*npp++ = PARENT(x));
897 if (LEFT(PARENT(x)) == x)
898 LEFT(PARENT(z)) = z;
899 else
900 RIGHT(PARENT(z)) = z;
901 }
902 PARENT(x) = z;
903 LEFT(z) = x;
904
905 *npp = NULL;
906 npp = node;
907 while ((tp = *npp++) != NULL)
908 if (tp != x && tp != y && tp != z && !in_list(tp, npp))
909 protect(tp);
910 }
911
912 #if 0 /* Not used, for now */
913 static void
914 TDRIGHT2(TREE *x, TREE *y, TREE *z)
915 {
916 TREE *node[3];
917 TREE **npp = node;
918 TREE *tp;
919
920 if ((LEFT(y) = RIGHT(z)) != NULL) {
921 unprotect(*npp++ = LEFT(y));
922 PARENT(LEFT(y)) = y;
923 }
924 if ((PARENT(z) = PARENT(x)) != NULL) {
925 unprotect(*npp++ = PARENT(x));
926 if (LEFT(PARENT(x)) == x)
927 LEFT(PARENT(z)) = z;
928 else
929 RIGHT(PARENT(z)) = z;
930 }
931 PARENT(x) = z;
932 RIGHT(z) = x;
933
934 *npp = NULL;
935 npp = node;
936 while ((tp = *npp++) != NULL)
937 if (tp != x && tp != y && tp != z && !in_list(tp, npp))
938 protect(tp);
939 }
940 #endif
941
942 /*
943 * Delete a tree element
944 */
945 static void
t_delete(TREE * op)946 t_delete(TREE *op)
947 {
948 TREE *tp, *sp, *gp;
949
950 /* if this is a non-tree node */
951 if (ISNOTREE(op)) {
952 tp = LINKBAK(op);
953 unprotect(tp);
954 if ((sp = LINKFOR(op)) != NULL) {
955 unprotect(sp);
956 LINKBAK(sp) = tp;
957 protect(sp);
958 }
959 LINKFOR(tp) = sp;
960 protect(tp);
961 return;
962 }
963
964 /* make op the root of the tree */
965 if (PARENT(op))
966 t_splay(op);
967
968 /* if this is the start of a list */
969 if ((tp = LINKFOR(op)) != NULL) {
970 unprotect(tp);
971 PARENT(tp) = NULL;
972 if ((sp = LEFT(op)) != NULL) {
973 unprotect(sp);
974 PARENT(sp) = tp;
975 protect(sp);
976 }
977 LEFT(tp) = sp;
978
979 if ((sp = RIGHT(op)) != NULL) {
980 unprotect(sp);
981 PARENT(sp) = tp;
982 protect(sp);
983 }
984 RIGHT(tp) = sp;
985
986 Root = tp;
987 protect(tp);
988 return;
989 }
990
991 /* if op has a non-null left subtree */
992 if ((tp = LEFT(op)) != NULL) {
993 unprotect(tp);
994 PARENT(tp) = NULL;
995 if (RIGHT(op)) {
996 /* make the right-end of the left subtree its root */
997 while ((sp = RIGHT(tp)) != NULL) {
998 unprotect(sp);
999 if ((gp = RIGHT(sp)) != NULL) {
1000 unprotect(gp);
1001 TDLEFT2(tp, sp, gp);
1002 protect(sp);
1003 protect(tp);
1004 tp = gp;
1005 } else {
1006 LEFT1(tp, sp);
1007 protect(tp);
1008 tp = sp;
1009 }
1010 }
1011
1012 /* hook the right subtree of op to the above elt */
1013 RIGHT(tp) = sp = RIGHT(op);
1014 unprotect(sp);
1015 PARENT(sp) = tp;
1016 protect(sp);
1017 }
1018 protect(tp);
1019 } else if ((tp = RIGHT(op)) != NULL) { /* no left subtree */
1020 unprotect(tp);
1021 PARENT(tp) = NULL;
1022 protect(tp);
1023 }
1024
1025 Root = tp;
1026 }
1027
1028 /*
1029 * Bottom up splaying (simple version).
1030 * The basic idea is to roughly cut in half the
1031 * path from Root to tp and make tp the new root.
1032 */
1033 static void
t_splay(TREE * tp)1034 t_splay(TREE *tp)
1035 {
1036 TREE *pp, *gp;
1037
1038 /* iterate until tp is the root */
1039 while ((pp = PARENT(tp)) != NULL) {
1040 unprotect(pp);
1041 /* grandparent of tp */
1042 gp = PARENT(pp);
1043 if (gp)
1044 unprotect(gp);
1045
1046 /* x is a left child */
1047 if (LEFT(pp) == tp) {
1048 if (gp && LEFT(gp) == pp) {
1049 BURIGHT2(gp, pp, tp);
1050 protect(gp);
1051 } else {
1052 if (gp)
1053 protect(gp);
1054 RIGHT1(pp, tp);
1055 }
1056 } else {
1057 ASSERT(RIGHT(pp) == tp);
1058 if (gp && RIGHT(gp) == pp) {
1059 BULEFT2(gp, pp, tp);
1060 protect(gp);
1061 } else {
1062 if (gp)
1063 protect(gp);
1064 LEFT1(pp, tp);
1065 }
1066 }
1067 protect(pp);
1068 unprotect(tp); /* just in case */
1069 }
1070 }
1071
1072 void
free(void * old)1073 free(void *old)
1074 {
1075 (void) mutex_lock(&__watch_malloc_lock);
1076 free_unlocked(old);
1077 (void) mutex_unlock(&__watch_malloc_lock);
1078 }
1079
1080
1081 static void
free_unlocked(void * old)1082 free_unlocked(void *old)
1083 {
1084 if (old != NULL)
1085 realfree(old);
1086 }
1087
1088
1089 /*
1090 * memalign(align,nbytes)
1091 *
1092 * Description:
1093 * Returns a block of specified size on a specified alignment boundary.
1094 *
1095 * Algorithm:
1096 * Malloc enough to ensure that a block can be aligned correctly.
1097 * Find the alignment point and return the fragments
1098 * before and after the block.
1099 *
1100 * Errors:
1101 * Returns NULL and sets errno as follows:
1102 * [EINVAL]
1103 * if nbytes = 0,
1104 * or if alignment is misaligned,
1105 * or if the heap has been detectably corrupted.
1106 * [ENOMEM]
1107 * if the requested memory could not be allocated.
1108 */
1109
1110 #define misaligned(p) ((unsigned)(p) & 3)
1111 /* 4-byte "word" alignment is considered ok in LP64 */
1112 #define nextblk(p, size) ((TREE *)((char *)(p) + (size)))
1113
1114 void *
memalign(size_t align,size_t nbytes)1115 memalign(size_t align, size_t nbytes)
1116 {
1117 size_t reqsize; /* Num of bytes to get from malloc() */
1118 TREE *p; /* Ptr returned from malloc() */
1119 TREE *blk; /* For addressing fragment blocks */
1120 size_t blksize; /* Current (shrinking) block size */
1121 TREE *alignedp; /* Ptr to properly aligned boundary */
1122 TREE *aligned_blk; /* The block to be returned */
1123 size_t frag_size; /* size of fragments fore and aft */
1124 size_t x;
1125
1126 /*
1127 * check for valid size and alignment parameters
1128 * MAX_ALIGN check prevents overflow in later calculation.
1129 */
1130 if (nbytes == 0 || misaligned(align) || align == 0 ||
1131 align > MAX_ALIGN) {
1132 errno = EINVAL;
1133 return (NULL);
1134 }
1135
1136 /*
1137 * Malloc enough memory to guarantee that the result can be
1138 * aligned correctly. The worst case is when malloc returns
1139 * a block so close to the next alignment boundary that a
1140 * fragment of minimum size cannot be created. In order to
1141 * make sure we can handle this, we need to force the
1142 * alignment to be at least as large as the minimum frag size
1143 * (MINSIZE + WORDSIZE).
1144 */
1145
1146 /* check for size that could overflow ROUND calculation */
1147 if (nbytes > MAX_MALLOC) {
1148 errno = ENOMEM;
1149 return (NULL);
1150 }
1151 ROUND(nbytes);
1152 if (nbytes < MINSIZE)
1153 nbytes = MINSIZE;
1154 ROUND(align);
1155 while (align < MINSIZE + WORDSIZE)
1156 align <<= 1;
1157 reqsize = nbytes + align + (MINSIZE + WORDSIZE);
1158 /* check for overflow */
1159 if (reqsize < nbytes) {
1160 errno = ENOMEM;
1161 return (NULL);
1162 }
1163 p = (TREE *) malloc(reqsize);
1164 if (p == (TREE *) NULL) {
1165 /* malloc sets errno */
1166 return (NULL);
1167 }
1168 (void) mutex_lock(&__watch_malloc_lock);
1169
1170 /*
1171 * get size of the entire block (overhead and all)
1172 */
1173 /* LINTED improper alignment */
1174 blk = BLOCK(p); /* back up to get length word */
1175 unprotect(blk);
1176 blksize = SIZE(blk);
1177 CLRBITS01(blksize);
1178
1179 /*
1180 * locate the proper alignment boundary within the block.
1181 */
1182 x = (size_t)p;
1183 if (x % align != 0)
1184 x += align - (x % align);
1185 alignedp = (TREE *)x;
1186 /* LINTED improper alignment */
1187 aligned_blk = BLOCK(alignedp);
1188
1189 /*
1190 * Check out the space to the left of the alignment
1191 * boundary, and split off a fragment if necessary.
1192 */
1193 frag_size = (size_t)aligned_blk - (size_t)blk;
1194 if (frag_size != 0) {
1195 /*
1196 * Create a fragment to the left of the aligned block.
1197 */
1198 if (frag_size < MINSIZE + WORDSIZE) {
1199 /*
1200 * Not enough space. So make the split
1201 * at the other end of the alignment unit.
1202 * We know this yields enough space, because
1203 * we forced align >= MINSIZE + WORDSIZE above.
1204 */
1205 frag_size += align;
1206 /* LINTED improper alignment */
1207 aligned_blk = nextblk(aligned_blk, align);
1208 }
1209 blksize -= frag_size;
1210 SIZE(aligned_blk) = blksize | BIT0;
1211 frag_size -= WORDSIZE;
1212 SIZE(blk) = frag_size | BIT0 | ISBIT1(SIZE(blk));
1213 free_unlocked(DATA(blk));
1214 /*
1215 * free_unlocked(DATA(blk)) has the side-effect of calling
1216 * protect() on the block following blk, that is, aligned_blk.
1217 * We recover from this by unprotect()ing it here.
1218 */
1219 unprotect(aligned_blk);
1220 }
1221
1222 /*
1223 * Is there a (sufficiently large) fragment to the
1224 * right of the aligned block?
1225 */
1226 frag_size = blksize - nbytes;
1227 if (frag_size >= MINSIZE + WORDSIZE) {
1228 /*
1229 * split and free a fragment on the right
1230 */
1231 blksize = SIZE(aligned_blk);
1232 SIZE(aligned_blk) = nbytes;
1233 /* LINTED improper alignment */
1234 blk = NEXT(aligned_blk);
1235 SETOLD01(SIZE(aligned_blk), blksize);
1236 frag_size -= WORDSIZE;
1237 SIZE(blk) = frag_size | BIT0;
1238 free_unlocked(DATA(blk));
1239 }
1240 copy_pattern(LIVEPAT, aligned_blk);
1241 protect(aligned_blk);
1242 (void) mutex_unlock(&__watch_malloc_lock);
1243 return (DATA(aligned_blk));
1244 }
1245
1246 void *
valloc(size_t size)1247 valloc(size_t size)
1248 {
1249 static unsigned pagesize;
1250 if (!pagesize)
1251 pagesize = _sysconf(_SC_PAGESIZE);
1252 return (memalign(pagesize, size));
1253 }
1254
1255 void *
calloc(size_t num,size_t size)1256 calloc(size_t num, size_t size)
1257 {
1258 void *mp;
1259 size_t total;
1260
1261 total = num * size;
1262
1263 /* check for overflow */
1264 if (num != 0 && total / num != size) {
1265 errno = ENOMEM;
1266 return (NULL);
1267 }
1268 if ((mp = malloc(total)) != NULL)
1269 (void) memset(mp, 0, total);
1270 return (mp);
1271 }
1272
1273 /* ARGSUSED1 */
1274 void
cfree(void * p,size_t num,size_t size)1275 cfree(void *p, size_t num, size_t size)
1276 {
1277 free(p);
1278 }
1279
1280 typedef struct {
1281 long cmd;
1282 prwatch_t prwatch;
1283 } ctl_t;
1284
1285 static pid_t my_pid = 0; /* to check for whether we fork()d */
1286 static int dont_watch = 0;
1287 static int do_stop = 0;
1288 static int ctlfd = -1;
1289 struct stat ctlstatb;
1290 static int wflags = WA_WRITE;
1291
1292 static void
init_watch()1293 init_watch()
1294 {
1295 char str[80];
1296 char *s;
1297
1298 my_pid = getpid();
1299
1300 dont_watch = 1;
1301
1302 if ((s = getenv("MALLOC_DEBUG")) == NULL)
1303 return;
1304
1305 s = strncpy(str, s, sizeof (str));
1306 while (s != NULL) {
1307 char *e = strchr(s, ',');
1308 if (e)
1309 *e++ = '\0';
1310 if (strcmp(s, "STOP") == 0)
1311 do_stop = 1;
1312 else if (strcmp(s, "WATCH") == 0)
1313 dont_watch = 0;
1314 else if (strcmp(s, "RW") == 0) {
1315 dont_watch = 0;
1316 wflags = WA_READ|WA_WRITE;
1317 }
1318 s = e;
1319 }
1320
1321 if (dont_watch)
1322 return;
1323
1324 if ((ctlfd = open("/proc/self/ctl", O_WRONLY)) < 0 ||
1325 fstat(ctlfd, &ctlstatb) != 0) {
1326 if (ctlfd >= 0)
1327 (void) close(ctlfd);
1328 ctlfd = -1;
1329 dont_watch = 1;
1330 return;
1331 }
1332 /* close-on-exec */
1333 (void) fcntl(ctlfd, F_SETFD, 1);
1334
1335 if (do_stop) {
1336 int pfd;
1337 pstatus_t pstatus;
1338 struct {
1339 long cmd;
1340 fltset_t fltset;
1341 } ctl;
1342
1343 /*
1344 * Play together with some /proc controller
1345 * that has set other stop-on-fault flags.
1346 */
1347 premptyset(&ctl.fltset);
1348 if ((pfd = open("/proc/self/status", O_RDONLY)) >= 0) {
1349 if (read(pfd, &pstatus, sizeof (pstatus))
1350 == sizeof (pstatus))
1351 ctl.fltset = pstatus.pr_flttrace;
1352 (void) close(pfd);
1353 }
1354 praddset(&ctl.fltset, FLTWATCH);
1355 ctl.cmd = PCSFAULT;
1356 (void) write(ctlfd, &ctl, sizeof (ctl));
1357 }
1358 }
1359
1360 static int
nowatch()1361 nowatch()
1362 {
1363 struct stat statb;
1364
1365 if (dont_watch)
1366 return (1);
1367 if (ctlfd < 0) /* first time */
1368 init_watch();
1369 else if (fstat(ctlfd, &statb) != 0 ||
1370 statb.st_dev != ctlstatb.st_dev ||
1371 statb.st_ino != ctlstatb.st_ino) {
1372 /*
1373 * Someone closed our file descriptor.
1374 * Just open another one.
1375 */
1376 if ((ctlfd = open("/proc/self/ctl", O_WRONLY)) < 0 ||
1377 fstat(ctlfd, &ctlstatb) != 0) {
1378 if (ctlfd >= 0)
1379 (void) close(ctlfd);
1380 ctlfd = -1;
1381 dont_watch = 1;
1382 return (1);
1383 }
1384 /* close-on-exec */
1385 (void) fcntl(ctlfd, F_SETFD, 1);
1386 }
1387 if (my_pid != getpid()) {
1388 /*
1389 * We fork()d since the last call to the allocator.
1390 * watchpoints are not inherited across fork().
1391 * XXX: how to recover from this ???
1392 */
1393 dont_watch = 1;
1394 (void) close(ctlfd);
1395 ctlfd = -1;
1396 }
1397 return (dont_watch);
1398 }
1399
1400 static void
protect(TREE * tp)1401 protect(TREE *tp)
1402 {
1403 ctl_t ctl;
1404 size_t size, sz;
1405
1406 if (nowatch())
1407 return;
1408 if (tp == NULL || DATA(tp) == Baddr)
1409 return;
1410
1411 sz = size = SIZE(tp);
1412 CLRBITS01(size);
1413 if (size == 0)
1414 return;
1415 if (ISBIT0(sz)) /* block is busy, protect only the head */
1416 size = 0;
1417 ctl.cmd = PCWATCH;
1418 ctl.prwatch.pr_vaddr = (uintptr_t)tp;
1419 ctl.prwatch.pr_size = size + WORDSIZE;
1420 ctl.prwatch.pr_wflags = wflags;
1421 (void) write(ctlfd, &ctl, sizeof (ctl));
1422 }
1423
1424 static void
unprotect(TREE * tp)1425 unprotect(TREE *tp)
1426 {
1427 ctl_t ctl;
1428
1429 if (nowatch())
1430 return;
1431 if (tp == NULL || DATA(tp) == Baddr)
1432 return;
1433
1434 ctl.cmd = PCWATCH;
1435 ctl.prwatch.pr_vaddr = (uintptr_t)tp;
1436 ctl.prwatch.pr_size = WORDSIZE; /* size is arbitrary */
1437 ctl.prwatch.pr_wflags = 0; /* clear the watched area */
1438 (void) write(ctlfd, &ctl, sizeof (ctl));
1439 }
1440
1441 static void
malloc_prepare()1442 malloc_prepare()
1443 {
1444 (void) mutex_lock(&__watch_malloc_lock);
1445 }
1446
1447 static void
malloc_release()1448 malloc_release()
1449 {
1450 (void) mutex_unlock(&__watch_malloc_lock);
1451 }
1452
1453 #pragma init(malloc_init)
1454 static void
malloc_init(void)1455 malloc_init(void)
1456 {
1457 (void) pthread_atfork(malloc_prepare, malloc_release, malloc_release);
1458 }
1459