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 2007 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"	/* SVr4.0 1.2	*/
31
32#include <stdlib.h>
33#include <unistd.h>
34#include <fcntl.h>
35#include <string.h>
36#include <errno.h>
37#include <memory.h>
38#include <thread.h>
39#include <pthread.h>
40#include <synch.h>
41#include <procfs.h>
42#include <limits.h>
43#include <sys/types.h>
44#include <sys/stat.h>
45
46/* debugging macros */
47#ifdef	DEBUG
48#define	ASSERT(p)	((void) ((p) || (abort(), 0)))
49#define	COUNT(n)	((void) n++)
50static int		nmalloc, nrealloc, nfree;
51#else
52#define	ASSERT(p)	((void)0)
53#define	COUNT(n)	((void)0)
54#endif /* DEBUG */
55
56/* for conveniences */
57#ifndef NULL
58#define	NULL		(0)
59#endif
60
61#define	WORDSIZE	(sizeof (WORD))
62#define	MINSIZE		(sizeof (TREE) - sizeof (WORD))
63#define	ROUND(s)	if ((s)%WORDSIZE) (s) += (WORDSIZE - ((s)%WORDSIZE))
64
65/*
66 * All of our allocations will be aligned on the least multiple of 4,
67 * at least, so the two low order bits are guaranteed to be available.
68 */
69#ifdef _LP64
70#define	ALIGN		16
71#else
72#define	ALIGN		8
73#endif
74
75/* the proto-word; size must be ALIGN bytes */
76typedef union _w_ {
77	size_t		w_i;		/* an unsigned int */
78	struct _t_	*w_p[2];	/* two pointers */
79} WORD;
80
81/* structure of a node in the free tree */
82typedef struct _t_ {
83	WORD	t_s;	/* size of this element */
84	WORD	t_p;	/* parent node */
85	WORD	t_l;	/* left child */
86	WORD	t_r;	/* right child */
87	WORD	t_n;	/* next in link list */
88	WORD	t_d;	/* dummy to reserve space for self-pointer */
89} TREE;
90
91/* usable # of bytes in the block */
92#define	SIZE(b)		(((b)->t_s).w_i)
93#define	RSIZE(b)	(((b)->t_s).w_i & ~BITS01)
94
95/* free tree pointers */
96#define	PARENT(b)	(((b)->t_p).w_p[0])
97#define	LEFT(b)		(((b)->t_l).w_p[0])
98#define	RIGHT(b)	(((b)->t_r).w_p[0])
99
100/* forward link in lists of small blocks */
101#define	AFTER(b)	(((b)->t_p).w_p[0])
102
103/* forward and backward links for lists in the tree */
104#define	LINKFOR(b)	(((b)->t_n).w_p[0])
105#define	LINKBAK(b)	(((b)->t_p).w_p[0])
106
107/* set/test indicator if a block is in the tree or in a list */
108#define	SETNOTREE(b)	(LEFT(b) = (TREE *)(-1))
109#define	ISNOTREE(b)	(LEFT(b) == (TREE *)(-1))
110
111/* functions to get information on a block */
112#define	DATA(b)		(((char *)(b)) + WORDSIZE)
113#define	BLOCK(d)	((TREE *)(((char *)(d)) - WORDSIZE))
114#define	SELFP(b)	(&(NEXT(b)->t_s.w_p[1]))
115#define	LAST(b)		((b)->t_s.w_p[1])
116#define	NEXT(b)		((TREE *)(((char *)(b)) + RSIZE(b) + WORDSIZE))
117#define	BOTTOM(b)	((DATA(b) + RSIZE(b) + WORDSIZE) == Baddr)
118
119/* functions to set and test the lowest two bits of a word */
120#define	BIT0		(01)		/* ...001 */
121#define	BIT1		(02)		/* ...010 */
122#define	BITS01		(03)		/* ...011 */
123#define	ISBIT0(w)	((w) & BIT0)	/* Is busy? */
124#define	ISBIT1(w)	((w) & BIT1)	/* Is the preceding free? */
125#define	SETBIT0(w)	((w) |= BIT0)	/* Block is busy */
126#define	SETBIT1(w)	((w) |= BIT1)	/* The preceding is free */
127#define	CLRBIT0(w)	((w) &= ~BIT0)	/* Clean bit0 */
128#define	CLRBIT1(w)	((w) &= ~BIT1)	/* Clean bit1 */
129#define	SETBITS01(w)	((w) |= BITS01)	/* Set bits 0 & 1 */
130#define	CLRBITS01(w)	((w) &= ~BITS01) /* Clean bits 0 & 1 */
131#define	SETOLD01(n, o)	((n) |= (BITS01 & (o)))
132
133/* system call to get more memory */
134#define	GETCORE		sbrk
135#define	ERRCORE		((char *)(-1))
136#define	CORESIZE	(1024*ALIGN)
137#define	MAX_GETCORE (size_t)(SSIZE_MAX & ~(ALIGN - 1)) /* round down ALIGN */
138#define	MAX_MALLOC (size_t)(SIZE_MAX - CORESIZE - 3 * ALIGN) /* overflow chk */
139#define	MAX_ALIGN	(1 + (size_t)SSIZE_MAX)
140