17c478bdstevel@tonic-gate/*
27c478bdstevel@tonic-gate * CDDL HEADER START
37c478bdstevel@tonic-gate *
47c478bdstevel@tonic-gate * The contents of this file are subject to the terms of the
57c478bdstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only
67c478bdstevel@tonic-gate * (the "License").  You may not use this file except in compliance
77c478bdstevel@tonic-gate * with the License.
87c478bdstevel@tonic-gate *
97c478bdstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
107c478bdstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
117c478bdstevel@tonic-gate * See the License for the specific language governing permissions
127c478bdstevel@tonic-gate * and limitations under the License.
137c478bdstevel@tonic-gate *
147c478bdstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
157c478bdstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
167c478bdstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
177c478bdstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
187c478bdstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
197c478bdstevel@tonic-gate *
207c478bdstevel@tonic-gate * CDDL HEADER END
217c478bdstevel@tonic-gate */
227c478bdstevel@tonic-gate/*
237c478bdstevel@tonic-gate * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
247c478bdstevel@tonic-gate * Use is subject to license terms.
257c478bdstevel@tonic-gate */
267c478bdstevel@tonic-gate
277c478bdstevel@tonic-gate#if 1
287c478bdstevel@tonic-gate#undef DEBUG
297c478bdstevel@tonic-gate#endif
307c478bdstevel@tonic-gate
317c478bdstevel@tonic-gate/*  #define	DEBUG ON */
327c478bdstevel@tonic-gate
337c478bdstevel@tonic-gate/*
347c478bdstevel@tonic-gate * Conditions on use:
357c478bdstevel@tonic-gate * kmem_alloc and kmem_free must not be called from interrupt level,
367c478bdstevel@tonic-gate * except from software interrupt level.  This is because they are
377c478bdstevel@tonic-gate * not reentrant, and only block out software interrupts.  They take
387c478bdstevel@tonic-gate * too long to block any real devices.  There is a routine
397c478bdstevel@tonic-gate * kmem_free_intr that can be used to free blocks at interrupt level,
407c478bdstevel@tonic-gate * but only up to splimp, not higher.  This is because kmem_free_intr
417c478bdstevel@tonic-gate * only spl's to splimp.
427c478bdstevel@tonic-gate *
437c478bdstevel@tonic-gate * Also, these routines are not that fast, so they should not be used
447c478bdstevel@tonic-gate * in very frequent operations (e.g. operations that happen more often
457c478bdstevel@tonic-gate * than, say, once every few seconds).
467c478bdstevel@tonic-gate */
477c478bdstevel@tonic-gate
487c478bdstevel@tonic-gate/*
497c478bdstevel@tonic-gate * description:
507c478bdstevel@tonic-gate *	Yet another memory allocator, this one based on a method
517c478bdstevel@tonic-gate *	described in C.J. Stephenson, "Fast Fits", IBM Sys. Journal
527c478bdstevel@tonic-gate *
537c478bdstevel@tonic-gate *	The basic data structure is a "Cartesian" binary tree, in which
547c478bdstevel@tonic-gate *	nodes are ordered by ascending addresses (thus minimizing free
557c478bdstevel@tonic-gate *	list insertion time) and block sizes decrease with depth in the
567c478bdstevel@tonic-gate *	tree (thus minimizing search time for a block of a given size).
577c478bdstevel@tonic-gate *
587c478bdstevel@tonic-gate *	In other words, for any node s, letting D(s) denote
597c478bdstevel@tonic-gate *	the set of descendents of s, we have:
607c478bdstevel@tonic-gate *
617c478bdstevel@tonic-gate *	a. addr(D(left(s))) <  addr(s) <  addr(D(right(s)))
627c478bdstevel@tonic-gate *	b. len(D(left(s)))  <= len(s)  >= len(D(right(s)))
637c478bdstevel@tonic-gate */
647c478bdstevel@tonic-gate
657c478bdstevel@tonic-gate#include <sys/param.h>
667c478bdstevel@tonic-gate#include <sys/sysmacros.h>
677c478bdstevel@tonic-gate#include <sys/salib.h>
687c478bdstevel@tonic-gate#include <sys/saio.h>
697c478bdstevel@tonic-gate#include <sys/promif.h>
707c478bdstevel@tonic-gate
717c478bdstevel@tonic-gate/*
727c478bdstevel@tonic-gate * The node header structure.
737c478bdstevel@tonic-gate *
747c478bdstevel@tonic-gate * To reduce storage consumption, a header block is associated with
757c478bdstevel@tonic-gate * free blocks only, not allocated blocks.
767c478bdstevel@tonic-gate * When a free block is allocated, its header block is put on
777c478bdstevel@tonic-gate * a free header block list.
787c478bdstevel@tonic-gate *
797c478bdstevel@tonic-gate * This creates a header space and a free block space.
807c478bdstevel@tonic-gate * The left pointer of a header blocks is used to chain free header
817c478bdstevel@tonic-gate * blocks together.
827c478bdstevel@tonic-gate */
837c478bdstevel@tonic-gate
847c478bdstevel@tonic-gatetypedef enum {false, true} bool;
857c478bdstevel@tonic-gatetypedef struct	freehdr	*Freehdr;
867c478bdstevel@tonic-gatetypedef struct	dblk	*Dblk;
877c478bdstevel@tonic-gate
887c478bdstevel@tonic-gate/*
897c478bdstevel@tonic-gate * Description of a header for a free block
907c478bdstevel@tonic-gate * Only free blocks have such headers.
917c478bdstevel@tonic-gate */
927c478bdstevel@tonic-gatestruct 	freehdr	{
937c478bdstevel@tonic-gate	Freehdr	left;			/* Left tree pointer */
947c478bdstevel@tonic-gate	Freehdr	right;			/* Right tree pointer */
957c478bdstevel@tonic-gate	Dblk	block;			/* Ptr to the data block */
967c478bdstevel@tonic-gate	size_t	size;			/* Size of the data block */
977c478bdstevel@tonic-gate};
987c478bdstevel@tonic-gate
997c478bdstevel@tonic-gate#define	NIL		((Freehdr) 0)
1007c478bdstevel@tonic-gate#define	WORDSIZE	sizeof (int)
1017c478bdstevel@tonic-gate#define	SMALLEST_BLK	1		/* Size of smallest block */
1027c478bdstevel@tonic-gate
1037c478bdstevel@tonic-gate/*
1047c478bdstevel@tonic-gate * Description of a data block.
1057c478bdstevel@tonic-gate */
1067c478bdstevel@tonic-gatestruct	dblk	{
1077c478bdstevel@tonic-gate	char	data[1];		/* Addr returned to the caller */
1087c478bdstevel@tonic-gate};
1097c478bdstevel@tonic-gate
1107c478bdstevel@tonic-gate/*
1117c478bdstevel@tonic-gate * weight(x) is the size of a block, in bytes; or 0 if and only if x
1127c478bdstevel@tonic-gate *	is a null pointer. It is the responsibility of kmem_alloc() and
1137c478bdstevel@tonic-gate *	kmem_free() to keep zero-length blocks out of the arena.
1147c478bdstevel@tonic-gate */
1157c478bdstevel@tonic-gate
1167c478bdstevel@tonic-gate#define	weight(x)	((x) == NIL? 0: (x->size))
1177c478bdstevel@tonic-gate#define	nextblk(p, size) ((Dblk) ((char *)(p) + (size)))
1187c478bdstevel@tonic-gate#define	max(a, b)	((a) < (b)? (b): (a))
1197c478bdstevel@tonic-gate
1207c478bdstevel@tonic-gatevoid		*kmem_alloc(size_t, int);
1217c478bdstevel@tonic-gatevoid		kmem_free(void *ptr, size_t nbytes);
1227c478bdstevel@tonic-gateFreehdr		getfreehdr(void);
1237c478bdstevel@tonic-gatestatic bool	morecore(size_t);
1247c478bdstevel@tonic-gatevoid		insert(Dblk p, size_t len, Freehdr *tree);
1257c478bdstevel@tonic-gatevoid		freehdr(Freehdr p);
1267c478bdstevel@tonic-gatevoid		delete(Freehdr *p);
1277c478bdstevel@tonic-gatestatic void	check_need_to_free(void);
1287c478bdstevel@tonic-gateextern caddr_t	resalloc(enum RESOURCES, size_t, caddr_t, int);
1297c478bdstevel@tonic-gate#ifdef	__sparc
1307c478bdstevel@tonic-gateextern void	resalloc_init(void);
1317c478bdstevel@tonic-gate#endif
1327c478bdstevel@tonic-gateextern int	splnet(void);
1337c478bdstevel@tonic-gateextern int	splimp(void);
1347c478bdstevel@tonic-gateextern void	splx(int);
1357c478bdstevel@tonic-gate
1367c478bdstevel@tonic-gate/*
1377c478bdstevel@tonic-gate * Structure containing various info about allocated memory.
1387c478bdstevel@tonic-gate */
1397c478bdstevel@tonic-gate#define	NEED_TO_FREE_SIZE	5
1407c478bdstevel@tonic-gatestruct kmem_info {
1417c478bdstevel@tonic-gate	Freehdr	free_root;
1427c478bdstevel@tonic-gate	Freehdr	free_hdr_list;
1437c478bdstevel@tonic-gate	struct map *map;
1447c478bdstevel@tonic-gate	struct pte *pte;
1457c478bdstevel@tonic-gate	caddr_t	vaddr;
1467c478bdstevel@tonic-gate	struct need_to_free {
1477c478bdstevel@tonic-gate		caddr_t addr;
1487c478bdstevel@tonic-gate		size_t	nbytes;
1497c478bdstevel@tonic-gate	} need_to_free_list, need_to_free[NEED_TO_FREE_SIZE];
1507c478bdstevel@tonic-gate} kmem_info;
1517c478bdstevel@tonic-gate
1527c478bdstevel@tonic-gate
1537c478bdstevel@tonic-gatestruct map *kernelmap;
1547c478bdstevel@tonic-gate
1557c478bdstevel@tonic-gate#ifdef DEBUG
1567c478bdstevel@tonic-gatestatic void prtree(Freehdr, char *);
1577c478bdstevel@tonic-gate#endif
1587c478bdstevel@tonic-gate
1597c478bdstevel@tonic-gate/*
1607c478bdstevel@tonic-gate * Initialize kernel memory allocator
1617c478bdstevel@tonic-gate */
1627c478bdstevel@tonic-gate
1637c478bdstevel@tonic-gatevoid
1647c478bdstevel@tonic-gatekmem_init(void)
1657c478bdstevel@tonic-gate{
1667c478bdstevel@tonic-gate	int i;
1677c478bdstevel@tonic-gate	struct need_to_free *ntf;
1687c478bdstevel@tonic-gate
1697c478bdstevel@tonic-gate#ifdef DEBUG
1707c478bdstevel@tonic-gateprintf("kmem_init entered\n");
1717c478bdstevel@tonic-gate#endif
1727c478bdstevel@tonic-gate
1737c478bdstevel@tonic-gate#ifdef __sparc
1747c478bdstevel@tonic-gate	resalloc_init();
1757c478bdstevel@tonic-gate#endif
1767c478bdstevel@tonic-gate
1777c478bdstevel@tonic-gate	kmem_info.free_root = NIL;
1787c478bdstevel@tonic-gate	kmem_info.free_hdr_list = NULL;
1797c478bdstevel@tonic-gate	kmem_info.map = kernelmap;
1807c478bdstevel@tonic-gate	kmem_info.need_to_free_list.addr = 0;
1817c478bdstevel@tonic-gate	ntf = kmem_info.need_to_free;
1827c478bdstevel@tonic-gate	for (i = 0; i < NEED_TO_FREE_SIZE; i++) {
1837c478bdstevel@tonic-gate		ntf[i].addr = 0;
1847c478bdstevel@tonic-gate	}
1857c478bdstevel@tonic-gate#ifdef DEBUG
1867c478bdstevel@tonic-gateprintf("kmem_init returning\n");
1877c478bdstevel@tonic-gateprtree(kmem_info.free_root, "kmem_init");
1887c478bdstevel@tonic-gate#endif
1897c478bdstevel@tonic-gate}
1907c478bdstevel@tonic-gate
1917c478bdstevel@tonic-gate/*
1927c478bdstevel@tonic-gate * Insert a new node in a cartesian tree or subtree, placing it
1937c478bdstevel@tonic-gate *	in the correct position with respect to the existing nodes.
1947c478bdstevel@tonic-gate *
1957c478bdstevel@tonic-gate * algorithm:
1967c478bdstevel@tonic-gate *	Starting from the root, a binary search is made for the new
1977c478bdstevel@tonic-gate *	node. If this search were allowed to continue, it would
1987c478bdstevel@tonic-gate *	eventually fail (since there cannot already be a node at the
1997c478bdstevel@tonic-gate *	given address); but in fact it stops when it reaches a node in
2007c478bdstevel@tonic-gate *	the tree which has a length less than that of the new node (or
2017c478bdstevel@tonic-gate *	when it reaches a null tree pointer).  The new node is then
2027c478bdstevel@tonic-gate *	inserted at the root of the subtree for which the shorter node
2037c478bdstevel@tonic-gate *	forms the old root (or in place of the null pointer).
2047c478bdstevel@tonic-gate */
2057c478bdstevel@tonic-gate
2067c478bdstevel@tonic-gate
2077c478bdstevel@tonic-gatevoid
2087c478bdstevel@tonic-gateinsert(Dblk p,		/* Ptr to the block to insert */
2097c478bdstevel@tonic-gate    size_t len,		/* Length of new node */
2107c478bdstevel@tonic-gate    Freehdr *tree)	/* Address of ptr to root */
2117c478bdstevel@tonic-gate{
2127c478bdstevel@tonic-gate	Freehdr x;
2137c478bdstevel@tonic-gate	Freehdr *left_hook;	/* Temp for insertion */
2147c478bdstevel@tonic-gate	Freehdr *right_hook;	/* Temp for insertion */
2157c478bdstevel@tonic-gate	Freehdr newhdr;
2167c478bdstevel@tonic-gate
2177c478bdstevel@tonic-gate	x = *tree;
2187c478bdstevel@tonic-gate	/*
2197c478bdstevel@tonic-gate	 * Search for the first node which has a weight less
2207c478bdstevel@tonic-gate	 *	than that of the new node; this will be the
2217c478bdstevel@tonic-gate	 *	point at which we insert the new node.
2227c478bdstevel@tonic-gate	 */
2237c478bdstevel@tonic-gate
2247c478bdstevel@tonic-gate	while (weight(x) >= len) {
2257c478bdstevel@tonic-gate		if (p < x->block)
2267c478bdstevel@tonic-gate			tree = &x->left;
2277c478bdstevel@tonic-gate		else
2287c478bdstevel@tonic-gate			tree = &x->right;
2297c478bdstevel@tonic-gate		x = *tree;
2307c478bdstevel@tonic-gate	}
2317c478bdstevel@tonic-gate
2327c478bdstevel@tonic-gate	/*
2337c478bdstevel@tonic-gate	 * Perform root insertion. The variable x traces a path through
2347c478bdstevel@tonic-gate	 *	the tree, and with the help of left_hook and right_hook,
2357c478bdstevel@tonic-gate	 *	rewrites all links that cross the territory occupied
2367c478bdstevel@tonic-gate	 *	by p.  Note that this improves performance under
2377c478bdstevel@tonic-gate	 *	paging.
2387c478bdstevel@tonic-gate	 */
2397c478bdstevel@tonic-gate
2407c478bdstevel@tonic-gate	newhdr = getfreehdr();
2417c478bdstevel@tonic-gate	*tree = newhdr;
2427c478bdstevel@tonic-gate	left_hook = &newhdr->left;
2437c478bdstevel@tonic-gate	right_hook = &newhdr->right;
2447c478bdstevel@tonic-gate
2457c478bdstevel@tonic-gate	newhdr->left = NIL;
2467c478bdstevel@tonic-gate	newhdr->right = NIL;
2477c478bdstevel@tonic-gate	newhdr->block = p;
2487c478bdstevel@tonic-gate	newhdr->size = len;
2497c478bdstevel@tonic-gate
2507c478bdstevel@tonic-gate	while (x != NIL) {
2517c478bdstevel@tonic-gate		/*
2527c478bdstevel@tonic-gate		 * Remark:
2537c478bdstevel@tonic-gate		 *	The name 'left_hook' is somewhat confusing, since
2547c478bdstevel@tonic-gate		 *	it is always set to the address of a .right link
2557c478bdstevel@tonic-gate		 *	field.  However, its value is always an address
2567c478bdstevel@tonic-gate		 *	below (i.e., to the left of) p. Similarly
2577c478bdstevel@tonic-gate		 *	for right_hook. The values of left_hook and
2587c478bdstevel@tonic-gate		 *	right_hook converge toward the value of p,
2597c478bdstevel@tonic-gate		 *	as in a classical binary search.
2607c478bdstevel@tonic-gate		 */
2617c478bdstevel@tonic-gate		if (x->block < p) {
2627c478bdstevel@tonic-gate			/*
2637c478bdstevel@tonic-gate			 * rewrite link crossing from the left
2647c478bdstevel@tonic-gate			 */
2657c478bdstevel@tonic-gate			*left_hook = x;
2667c478bdstevel@tonic-gate			left_hook = &x->right;
2677c478bdstevel@tonic-gate			x = x->right;
2687c478bdstevel@tonic-gate		} else {
2697c478bdstevel@tonic-gate			/*
2707c478bdstevel@tonic-gate			 * rewrite link crossing from the right
2717c478bdstevel@tonic-gate			 */
2727c478bdstevel@tonic-gate			*right_hook = x;
2737c478bdstevel@tonic-gate			right_hook = &x->left;
2747c478bdstevel@tonic-gate			x = x->left;
2757c478bdstevel@tonic-gate		} /* else */
2767c478bdstevel@tonic-gate	} /* while */
2777c478bdstevel@tonic-gate
2787c478bdstevel@tonic-gate	*left_hook = *right_hook = NIL;		/* clear remaining hooks */
2797c478bdstevel@tonic-gate
2807c478bdstevel@tonic-gate} /* insert */
2817c478bdstevel@tonic-gate
2827c478bdstevel@tonic-gate
2837c478bdstevel@tonic-gate/*
2847c478bdstevel@tonic-gate * Delete a node from a cartesian tree. p is the address of
2857c478bdstevel@tonic-gate *	a pointer to the node which is to be deleted.
2867c478bdstevel@tonic-gate *
2877c478bdstevel@tonic-gate * algorithm:
2887c478bdstevel@tonic-gate *	The left and right sons of the node to be deleted define two
2897c478bdstevel@tonic-gate *	subtrees which are to be merged and attached in place of the
2907c478bdstevel@tonic-gate *	deleted node.  Each node on the inside edges of these two
2917c478bdstevel@tonic-gate *	subtrees is examined and longer nodes are placed above the
2927c478bdstevel@tonic-gate *	shorter ones.
2937c478bdstevel@tonic-gate *
2947c478bdstevel@tonic-gate * On entry:
2957c478bdstevel@tonic-gate *	*p is assumed to be non-null.
2967c478bdstevel@tonic-gate */
2977c478bdstevel@tonic-gate
2987c478bdstevel@tonic-gatevoid
2997c478bdstevel@tonic-gatedelete(Freehdr *p)
3007c478bdstevel@tonic-gate{
3017c478bdstevel@tonic-gate	Freehdr x;
3027c478bdstevel@tonic-gate	Freehdr left_branch;	/* left subtree of deleted node */
3037c478bdstevel@tonic-gate	Freehdr right_branch;	/* right subtree of deleted node */
3047c478bdstevel@tonic-gate
3057c478bdstevel@tonic-gate	x = *p;
3067c478bdstevel@tonic-gate	left_branch = x->left;
3077c478bdstevel@tonic-gate	right_branch = x->right;
3087c478bdstevel@tonic-gate
3097c478bdstevel@tonic-gate	while (left_branch != right_branch) {
3107c478bdstevel@tonic-gate		/*
3117c478bdstevel@tonic-gate		 * iterate until left branch and right branch are
3127c478bdstevel@tonic-gate		 * both NIL.
3137c478bdstevel@tonic-gate		 */
3147c478bdstevel@tonic-gate		if (weight(left_branch) >= weight(right_branch)) {
3157c478bdstevel@tonic-gate			/*
3167c478bdstevel@tonic-gate			 * promote the left branch
3177c478bdstevel@tonic-gate			 */
3187c478bdstevel@tonic-gate			*p = left_branch;
3197c478bdstevel@tonic-gate			p = &left_branch->right;
3207c478bdstevel@tonic-gate			left_branch = left_branch->right;
3217c478bdstevel@tonic-gate		} else {
3227c478bdstevel@tonic-gate			/*
3237c478bdstevel@tonic-gate			 * promote the right branch
3247c478bdstevel@tonic-gate			 */
3257c478bdstevel@tonic-gate			*p = right_branch;
3267c478bdstevel@tonic-gate			p = &right_branch->left;
3277c478bdstevel@tonic-gate			right_branch = right_branch->left;
3287c478bdstevel@tonic-gate		} /* else */
3297c478bdstevel@tonic-gate	} /* while */
3307c478bdstevel@tonic-gate	*p = NIL;
3317c478bdstevel@tonic-gate	freehdr(x);
3327c478bdstevel@tonic-gate} /* delete */
3337c478bdstevel@tonic-gate
3347c478bdstevel@tonic-gate
3357c478bdstevel@tonic-gate/*
3367c478bdstevel@tonic-gate * Demote a node in a cartesian tree, if necessary, to establish
3377c478bdstevel@tonic-gate *	the required vertical ordering.
3387c478bdstevel@tonic-gate *
3397c478bdstevel@tonic-gate * algorithm:
3407c478bdstevel@tonic-gate *	The left and right subtrees of the node to be demoted are to
3417c478bdstevel@tonic-gate *	be partially merged and attached in place of the demoted node.
3427c478bdstevel@tonic-gate *	The nodes on the inside edges of these two subtrees are
3437c478bdstevel@tonic-gate *	examined and the longer nodes are placed above the shorter
3447c478bdstevel@tonic-gate *	ones, until a node is reached which has a length no greater
3457c478bdstevel@tonic-gate *	than that of the node being demoted (or until a null pointer
3467c478bdstevel@tonic-gate *	is reached).  The node is then attached at this point, and
3477c478bdstevel@tonic-gate *	the remaining subtrees (if any) become its descendants.
3487c478bdstevel@tonic-gate *
3497c478bdstevel@tonic-gate * on entry:
3507c478bdstevel@tonic-gate *   a. All the nodes in the tree, including the one to be demoted,
3517c478bdstevel@tonic-gate *	must be correctly ordered horizontally;
3527c478bdstevel@tonic-gate *   b. All the nodes except the one to be demoted must also be
3537c478bdstevel@tonic-gate *	correctly positioned vertically.  The node to be demoted
3547c478bdstevel@tonic-gate *	may be already correctly positioned vertically, or it may
3557c478bdstevel@tonic-gate *	have a length which is less than that of one or both of
3567c478bdstevel@tonic-gate *	its progeny.
3577c478bdstevel@tonic-gate *   c. *p is non-null
3587c478bdstevel@tonic-gate */
3597c478bdstevel@tonic-gate
3607c478bdstevel@tonic-gate
3617c478bdstevel@tonic-gatestatic void
3627c478bdstevel@tonic-gatedemote(Freehdr *p)
3637c478bdstevel@tonic-gate{
3647c478bdstevel@tonic-gate	Freehdr x;		/* addr of node to be demoted */
3657c478bdstevel@tonic-gate	Freehdr left_branch;
3667c478bdstevel@tonic-gate	Freehdr right_branch;
3677c478bdstevel@tonic-gate	size_t    wx;
3687c478bdstevel@tonic-gate
3697c478bdstevel@tonic-gate	x = *p;
3707c478bdstevel@tonic-gate	left_branch = x->left;
3717c478bdstevel@tonic-gate	right_branch = x->right;
3727c478bdstevel@tonic-gate	wx = weight(x);
3737c478bdstevel@tonic-gate
3747c478bdstevel@tonic-gate	while (weight(left_branch) > wx || weight(right_branch) > wx) {
3757c478bdstevel@tonic-gate		/*
3767c478bdstevel@tonic-gate		 * select a descendant branch for promotion
3777c478bdstevel@tonic-gate		 */
3787c478bdstevel@tonic-gate		if (weight(left_branch) >= weight(right_branch)) {
3797c478bdstevel@tonic-gate			/*
3807c478bdstevel@tonic-gate			 * promote the left branch
3817c478bdstevel@tonic-gate			 */
3827c478bdstevel@tonic-gate			*p = left_branch;
3837c478bdstevel@tonic-gate			p = &left_branch->right;
3847c478bdstevel@tonic-gate			left_branch = *p;
3857c478bdstevel@tonic-gate		} else {
3867c478bdstevel@tonic-gate			/*
3877c478bdstevel@tonic-gate			 * promote the right branch
3887c478bdstevel@tonic-gate			 */
3897c478bdstevel@tonic-gate			*p = right_branch;
3907c478bdstevel@tonic-gate			p = &right_branch->left;
3917c478bdstevel@tonic-gate			right_branch = *p;
3927c478bdstevel@tonic-gate		} /* else */
3937c478bdstevel@tonic-gate	} /* while */
3947c478bdstevel@tonic-gate
3957c478bdstevel@tonic-gate	*p = x;				/* attach demoted node here */
3967c478bdstevel@tonic-gate	x->left = left_branch;
3977c478bdstevel@tonic-gate	x->right = right_branch;
3987c478bdstevel@tonic-gate} /* demote */
3997c478bdstevel@tonic-gate
4007c478bdstevel@tonic-gate/*
4017c478bdstevel@tonic-gate * Allocate a block of storage
4027c478bdstevel@tonic-gate *
4037c478bdstevel@tonic-gate * algorithm:
4047c478bdstevel@tonic-gate *	The freelist is searched by descending the tree from the root
4057c478bdstevel@tonic-gate *	so that at each decision point the "better fitting" child node
4067c478bdstevel@tonic-gate *	is chosen (i.e., the shorter one, if it is long enough, or
4077c478bdstevel@tonic-gate *	the longer one, otherwise).  The descent stops when both
4087c478bdstevel@tonic-gate *	child nodes are too short.
4097c478bdstevel@tonic-gate *
4107c478bdstevel@tonic-gate * function result:
4117c478bdstevel@tonic-gate *	kmem_alloc returns a pointer to the allocated block; a null
4127c478bdstevel@tonic-gate *	pointer indicates storage could not be allocated.
4137c478bdstevel@tonic-gate */
4147c478bdstevel@tonic-gate/*
4157c478bdstevel@tonic-gate * We need to return blocks that are on word boundaries so that callers
4167c478bdstevel@tonic-gate * that are putting int's into the area will work.  Since we allow
4177c478bdstevel@tonic-gate * arbitrary free'ing, we need a weight function that considers
4187c478bdstevel@tonic-gate * free blocks starting on an odd boundary special.  Allocation is
4197c478bdstevel@tonic-gate * aligned to 8 byte boundaries (ALIGN).
4207c478bdstevel@tonic-gate */
4217c478bdstevel@tonic-gate#define	ALIGN		8		/* doubleword aligned .. */
4227c478bdstevel@tonic-gate#define	ALIGNMASK	(ALIGN-1)
4237c478bdstevel@tonic-gate#define	ALIGNMORE(addr)	(ALIGN - ((uintptr_t)(addr) & ALIGNMASK))
4247c478bdstevel@tonic-gate
4257c478bdstevel@tonic-gate/*
4267c478bdstevel@tonic-gate * If it is empty then weight == 0
4277c478bdstevel@tonic-gate * If it is aligned then weight == size
4287c478bdstevel@tonic-gate * If it is unaligned
4297c478bdstevel@tonic-gate *	if not enough room to align then weight == 0
4307c478bdstevel@tonic-gate *	else weight == aligned size
4317c478bdstevel@tonic-gate */
4327c478bdstevel@tonic-gate#define	mweight(x) ((x) == NIL ? 0 : \
4337c478bdstevel@tonic-gate	((((uintptr_t)(x)->block) & ALIGNMASK) == 0 ? (x)->size : \
4347c478bdstevel@tonic-gate		(((x)->size <= ALIGNMORE((x)->block)) ? 0 : \
4357c478bdstevel@tonic-gate			(x)->size - ALIGNMORE((x)->block))))
4367c478bdstevel@tonic-gate
4377c478bdstevel@tonic-gate/*ARGSUSED1*/
4387c478bdstevel@tonic-gatevoid *
4397c478bdstevel@tonic-gatekmem_alloc(size_t nbytes, int kmflag)
4407c478bdstevel@tonic-gate{
4417c478bdstevel@tonic-gate	Freehdr a;		/* ptr to node to be allocated */
4427c478bdstevel@tonic-gate	Freehdr *p;		/* address of ptr to node */
4437c478bdstevel@tonic-gate	size_t	 left_weight;
4447c478bdstevel@tonic-gate	size_t	 right_weight;
4457c478bdstevel@tonic-gate	Freehdr left_son;
4467c478bdstevel@tonic-gate	Freehdr right_son;
4477c478bdstevel@tonic-gate	char	 *retblock;	/* Address returned to the user */
4487c478bdstevel@tonic-gate	int s;
4497c478bdstevel@tonic-gate#ifdef	DEBUG
4507c478bdstevel@tonic-gate	printf("kmem_alloc(nbytes 0x%lx)\n", nbytes);
4517c478bdstevel@tonic-gate#endif	/* DEBUG */
4527c478bdstevel@tonic-gate
4537c478bdstevel@tonic-gate	if (nbytes == 0) {
4547c478bdstevel@tonic-gate		return (NULL);
4557c478bdstevel@tonic-gate	}
4567c478bdstevel@tonic-gate	s = splnet();
4577c478bdstevel@tonic-gate
4587c478bdstevel@tonic-gate	if (nbytes < SMALLEST_BLK) {
4597c478bdstevel@tonic-gate		printf("illegal kmem_alloc call for %lx bytes\n", nbytes);
4607c478bdstevel@tonic-gate		prom_panic("kmem_alloc");
4617c478bdstevel@tonic-gate	}
4627c478bdstevel@tonic-gate	check_need_to_free();
4637c478bdstevel@tonic-gate
4647c478bdstevel@tonic-gate	/*
4657c478bdstevel@tonic-gate	 * ensure that at least one block is big enough to satisfy
4667c478bdstevel@tonic-gate	 *	the request.
4677c478bdstevel@tonic-gate	 */
4687c478bdstevel@tonic-gate
4697c478bdstevel@tonic-gate	if (mweight(kmem_info.free_root) <= nbytes) {
4707c478bdstevel@tonic-gate		/*
4717c478bdstevel@tonic-gate		 * the largest block is not enough.
4727c478bdstevel@tonic-gate		 */
4737c478bdstevel@tonic-gate		if (!morecore(nbytes)) {
4747c478bdstevel@tonic-gate			printf("kmem_alloc failed, nbytes %lx\n", nbytes);
4757c478bdstevel@tonic-gate			prom_panic("kmem_alloc");
4767c478bdstevel@tonic-gate		}
4777c478bdstevel@tonic-gate	}
4787c478bdstevel@tonic-gate
4797c478bdstevel@tonic-gate	/*
4807c478bdstevel@tonic-gate	 * search down through the tree until a suitable block is
4817c478bdstevel@tonic-gate	 *	found.  At each decision point, select the better
4827c478bdstevel@tonic-gate	 *	fitting node.
4837c478bdstevel@tonic-gate	 */
4847c478bdstevel@tonic-gate
4857c478bdstevel@tonic-gate	p = (Freehdr *) &kmem_info.free_root;
4867c478bdstevel@tonic-gate	a = *p;
4877c478bdstevel@tonic-gate	left_son = a->left;
4887c478bdstevel@tonic-gate	right_son = a->right;
4897c478bdstevel@tonic-gate	left_weight = mweight(left_son);
4907c478bdstevel@tonic-gate	right_weight = mweight(right_son);
4917c478bdstevel@tonic-gate
4927c478bdstevel@tonic-gate	while (left_weight >= nbytes || right_weight >= nbytes) {
4937c478bdstevel@tonic-gate		if (left_weight <= right_weight) {
4947c478bdstevel@tonic-gate			if (left_weight >= nbytes) {
4957c478bdstevel@tonic-gate				p = &a->left;
4967c478bdstevel@tonic-gate				a = left_son;
4977c478bdstevel@tonic-gate			} else {
4987c478bdstevel@tonic-gate				p = &a->right;
4997c478bdstevel@tonic-gate				a = right_son;
5007c478bdstevel@tonic-gate			}
5017c478bdstevel@tonic-gate		} else {
5027c478bdstevel@tonic-gate			if (right_weight >= nbytes) {
5037c478bdstevel@tonic-gate				p = &a->right;
5047c478bdstevel@tonic-gate				a = right_son;
5057c478bdstevel@tonic-gate			} else {
5067c478bdstevel@tonic-gate				p = &a->left;
5077c478bdstevel@tonic-gate				a = left_son;
5087c478bdstevel@tonic-gate			}
5097c478bdstevel@tonic-gate		}
5107c478bdstevel@tonic-gate		left_son = a->left;
5117c478bdstevel@tonic-gate		right_son = a->right;
5127c478bdstevel@tonic-gate		left_weight = mweight(left_son);
5137c478bdstevel@tonic-gate		right_weight = mweight(right_son);
5147c478bdstevel@tonic-gate	} /* while */
5157c478bdstevel@tonic-gate
5167c478bdstevel@tonic-gate	/*
5177c478bdstevel@tonic-gate	 * allocate storage from the selected node.
5187c478bdstevel@tonic-gate	 */
5197c478bdstevel@tonic-gate
5207c478bdstevel@tonic-gate	if (a->size - nbytes < SMALLEST_BLK) {
5217c478bdstevel@tonic-gate		/*
5227c478bdstevel@tonic-gate		 * not big enough to split; must leave at least
5237c478bdstevel@tonic-gate		 * a dblk's worth of space.
5247c478bdstevel@tonic-gate		 */
5257c478bdstevel@tonic-gate		retblock = a->block->data;
5267c478bdstevel@tonic-gate		delete(p);
5277c478bdstevel@tonic-gate	} else {
5287c478bdstevel@tonic-gate
5297c478bdstevel@tonic-gate		/*
5307c478bdstevel@tonic-gate		 * split the node, allocating nbytes from the top.
5317c478bdstevel@tonic-gate		 *	Remember we've already accounted for the
5327c478bdstevel@tonic-gate		 *	allocated node's header space.
5337c478bdstevel@tonic-gate		 */
5347c478bdstevel@tonic-gate		Freehdr x;
5357c478bdstevel@tonic-gate		x = getfreehdr();
5367c478bdstevel@tonic-gate		if ((uintptr_t)a->block->data & ALIGNMASK) {
5377c478bdstevel@tonic-gate			size_t size;
5387c478bdstevel@tonic-gate			if (a->size <= ALIGNMORE(a->block->data))
5397c478bdstevel@tonic-gate				prom_panic("kmem_alloc: short block allocated");
5407c478bdstevel@tonic-gate			size = nbytes + ALIGNMORE(a->block->data);
5417c478bdstevel@tonic-gate			x->block = a->block;
5427c478bdstevel@tonic-gate			x->size = ALIGNMORE(a->block->data);
5437c478bdstevel@tonic-gate			x->left = a->left;
5447c478bdstevel@tonic-gate			x->right = a->right;
5457c478bdstevel@tonic-gate			/*
5467c478bdstevel@tonic-gate			 * the node pointed to by *p has become smaller;
5477c478bdstevel@tonic-gate			 *	move it down to its appropriate place in
5487c478bdstevel@tonic-gate			 *	the tree.
5497c478bdstevel@tonic-gate			 */
5507c478bdstevel@tonic-gate			*p = x;
5517c478bdstevel@tonic-gate			demote(p);
5527c478bdstevel@tonic-gate			retblock = a->block->data + ALIGNMORE(a->block->data);
5537c478bdstevel@tonic-gate			if (a->size > size) {
5547c478bdstevel@tonic-gate				kmem_free((caddr_t)nextblk(a->block, size),
5557c478bdstevel@tonic-gate				    (size_t)(a->size - size));
5567c478bdstevel@tonic-gate			}
5577c478bdstevel@tonic-gate			freehdr(a);
5587c478bdstevel@tonic-gate		} else {
5597c478bdstevel@tonic-gate			x->block = nextblk(a->block, nbytes);
5607c478bdstevel@tonic-gate			x->size = a->size - nbytes;
5617c478bdstevel@tonic-gate			x->left = a->left;
5627c478bdstevel@tonic-gate			x->right = a->right;
5637c478bdstevel@tonic-gate			/*
5647c478bdstevel@tonic-gate			 * the node pointed to by *p has become smaller;
5657c478bdstevel@tonic-gate			 *	move it down to its appropriate place in
5667c478bdstevel@tonic-gate			 *	the tree.
5677c478bdstevel@tonic-gate			 */
5687c478bdstevel@tonic-gate			*p = x;
5697c478bdstevel@tonic-gate			demote(p);
5707c478bdstevel@tonic-gate			retblock = a->block->data;
5717c478bdstevel@tonic-gate			freehdr(a);
5727c478bdstevel@tonic-gate		}
5737c478bdstevel@tonic-gate	}
5747c478bdstevel@tonic-gate#ifdef DEBUG
5757c478bdstevel@tonic-gate	prtree(kmem_info.free_root, "kmem_alloc");
5767c478bdstevel@tonic-gate#endif
5777c478bdstevel@tonic-gate
5787c478bdstevel@tonic-gate	splx(s);
5797c478bdstevel@tonic-gate	bzero(retblock, nbytes);
5807c478bdstevel@tonic-gate#ifdef DEBUG
5817c478bdstevel@tonic-gate	printf("kmem_alloc  bzero complete - returning %p\n", retblock);
5827c478bdstevel@tonic-gate#endif
5837c478bdstevel@tonic-gate	return (retblock);
5847c478bdstevel@tonic-gate
5857c478bdstevel@tonic-gate} /* kmem_alloc */
5867c478bdstevel@tonic-gate
5877c478bdstevel@tonic-gate/*
5887c478bdstevel@tonic-gate * Return a block to the free space tree.
5897c478bdstevel@tonic-gate *
5907c478bdstevel@tonic-gate * algorithm:
5917c478bdstevel@tonic-gate *	Starting at the root, search for and coalesce free blocks
5927c478bdstevel@tonic-gate *	adjacent to one given.  When the appropriate place in the
5937c478bdstevel@tonic-gate *	tree is found, insert the given block.
5947c478bdstevel@tonic-gate *
5957c478bdstevel@tonic-gate * Do some sanity checks to avoid total confusion in the tree.
5967c478bdstevel@tonic-gate * If the block has already been freed, prom_panic.
5977c478bdstevel@tonic-gate * If the ptr is not from the arena, prom_panic.
5987c478bdstevel@tonic-gate */
5997c478bdstevel@tonic-gatevoid
6007c478bdstevel@tonic-gatekmem_free(void *ptr, size_t nbytes)
6017c478bdstevel@tonic-gate{
6027c478bdstevel@tonic-gate	Freehdr *np;		/* For deletion from free list */
6037c478bdstevel@tonic-gate	Freehdr neighbor;	/* Node to be coalesced */
6047c478bdstevel@tonic-gate	char	 *neigh_block;	/* Ptr to potential neighbor */
6057c478bdstevel@tonic-gate	size_t	 neigh_size;	/* Size of potential neighbor */
6067c478bdstevel@tonic-gate	int s;
6077c478bdstevel@tonic-gate
6087c478bdstevel@tonic-gate#ifdef DEBUG
6097c478bdstevel@tonic-gateprintf("kmem_free (ptr %p nbytes %lx)\n", ptr, nbytes);
6107c478bdstevel@tonic-gateprtree(kmem_info.free_root, "kmem_free");
6117c478bdstevel@tonic-gate#endif
6127c478bdstevel@tonic-gate
6137c478bdstevel@tonic-gate#ifdef	lint
6147c478bdstevel@tonic-gate	neigh_block = bkmem_zalloc(nbytes);
6157c478bdstevel@tonic-gate	neigh_block = neigh_block;
6167c478bdstevel@tonic-gate#endif
6177c478bdstevel@tonic-gate	if (nbytes == 0) {
6187c478bdstevel@tonic-gate		return;
6197c478bdstevel@tonic-gate	}
6207c478bdstevel@tonic-gate
6217c478bdstevel@tonic-gate	if (ptr == 0) {
6227c478bdstevel@tonic-gate		prom_panic("kmem_free of 0");
6237c478bdstevel@tonic-gate	}
6247c478bdstevel@tonic-gate	s = splnet();
6257c478bdstevel@tonic-gate
6267c478bdstevel@tonic-gate	/*
6277c478bdstevel@tonic-gate	 * Search the tree for the correct insertion point for this
6287c478bdstevel@tonic-gate	 *	node, coalescing adjacent free blocks along the way.
6297c478bdstevel@tonic-gate	 */
6307c478bdstevel@tonic-gate	np = &kmem_info.free_root;
6317c478bdstevel@tonic-gate	neighbor = *np;
6327c478bdstevel@tonic-gate	while (neighbor != NIL) {
6337c478bdstevel@tonic-gate		neigh_block = (char *)neighbor->block;
6347c478bdstevel@tonic-gate		neigh_size = neighbor->size;
6357c478bdstevel@tonic-gate		if ((char *)ptr < neigh_block) {
6367c478bdstevel@tonic-gate			if ((char *)ptr + nbytes == neigh_block) {
6377c478bdstevel@tonic-gate				/*
6387c478bdstevel@tonic-gate				 * Absorb and delete right neighbor
6397c478bdstevel@tonic-gate				 */
6407c478bdstevel@tonic-gate				nbytes += neigh_size;
6417c478bdstevel@tonic-gate				delete(np);
6427c478bdstevel@tonic-gate			} else if ((char *)ptr + nbytes > neigh_block) {
6437c478bdstevel@tonic-gate				/*
6447c478bdstevel@tonic-gate				 * The block being freed overlaps
6457c478bdstevel@tonic-gate				 * another block in the tree.  This
6467c478bdstevel@tonic-gate				 * is bad news.
6477c478bdstevel@tonic-gate				 */
6487c478bdstevel@tonic-gate				printf("kmem_free: free block overlap %p+%lx"
6497c478bdstevel@tonic-gate				    " over %p\n", (void *)ptr, nbytes,
6507c478bdstevel@tonic-gate				    (void *)neigh_block);
6517c478bdstevel@tonic-gate				prom_panic("kmem_free: free block overlap");
6527c478bdstevel@tonic-gate			} else {
6537c478bdstevel@tonic-gate				/*
6547c478bdstevel@tonic-gate				 * Search to the left
6557c478bdstevel@tonic-gate				 */
6567c478bdstevel@tonic-gate				np = &neighbor->left;
6577c478bdstevel@tonic-gate			}
6587c478bdstevel@tonic-gate		} else if ((char *)ptr > neigh_block) {
6597c478bdstevel@tonic-gate			if (neigh_block + neigh_size == ptr) {
6607c478bdstevel@tonic-gate				/*
6617c478bdstevel@tonic-gate				 * Absorb and delete left neighbor
6627c478bdstevel@tonic-gate				 */
6637c478bdstevel@tonic-gate				ptr = neigh_block;
6647c478bdstevel@tonic-gate				nbytes += neigh_size;
6657c478bdstevel@tonic-gate				delete(np);
6667c478bdstevel@tonic-gate			} else if (neigh_block + neigh_size > (char *)ptr) {
6677c478bdstevel@tonic-gate				/*
6687c478bdstevel@tonic-gate				 * This block has already been freed
6697c478bdstevel@tonic-gate				 */
6707c478bdstevel@tonic-gate				prom_panic("kmem_free block already free");
6717c478bdstevel@tonic-gate			} else {
6727c478bdstevel@tonic-gate				/*
6737c478bdstevel@tonic-gate				 * search to the right
6747c478bdstevel@tonic-gate				 */
6757c478bdstevel@tonic-gate				np = &neighbor->right;
6767c478bdstevel@tonic-gate			}
6777c478bdstevel@tonic-gate		} else {
6787c478bdstevel@tonic-gate			/*
6797c478bdstevel@tonic-gate			 * This block has already been freed
6807c478bdstevel@tonic-gate			 * as "ptr == neigh_block"
6817c478bdstevel@tonic-gate			 */
6827c478bdstevel@tonic-gate			prom_panic("kmem_free: block already free as neighbor");
6837c478bdstevel@tonic-gate		} /* else */
6847c478bdstevel@tonic-gate		neighbor = *np;
6857c478bdstevel@tonic-gate	} /* while */
6867c478bdstevel@tonic-gate
6877c478bdstevel@tonic-gate	/*
6887c478bdstevel@tonic-gate	 * Insert the new node into the free space tree
6897c478bdstevel@tonic-gate	 */
6907c478bdstevel@tonic-gate	insert((Dblk) ptr, nbytes, &kmem_info.free_root);
6917c478bdstevel@tonic-gate#ifdef DEBUG
6927c478bdstevel@tonic-gateprintf("exiting kmem_free\n");
6937c478bdstevel@tonic-gateprtree(kmem_info.free_root, "kmem_free");
6947c478bdstevel@tonic-gate#endif
6957c478bdstevel@tonic-gate	splx(s);
6967c478bdstevel@tonic-gate} /* kmem_free */
6977c478bdstevel@tonic-gate
6987c478bdstevel@tonic-gate/*
6997c478bdstevel@tonic-gate *  Sigh.  We include a header file which the kernel
7007c478bdstevel@tonic-gate *  uses to declare (one of its many) kmem_free prototypes.
7017c478bdstevel@tonic-gate *  In order not to use the kernel's namespace, then, we must
7027c478bdstevel@tonic-gate *  define another name here for use by boot.
7037c478bdstevel@tonic-gate */
7047c478bdstevel@tonic-gatevoid *
7057c478bdstevel@tonic-gatebkmem_alloc(size_t size)
7067c478bdstevel@tonic-gate{
7077c478bdstevel@tonic-gate	return (kmem_alloc(size, 0));
7087c478bdstevel@tonic-gate}
7097c478bdstevel@tonic-gate
7107c478bdstevel@tonic-gate/*
7117c478bdstevel@tonic-gate * Boot's kmem_alloc is really kmem_zalloc().
7127c478bdstevel@tonic-gate */
7137c478bdstevel@tonic-gatevoid *
7147c478bdstevel@tonic-gatebkmem_zalloc(size_t size)
7157c478bdstevel@tonic-gate{
7167c478bdstevel@tonic-gate	return (kmem_alloc(size, 0));
7177c478bdstevel@tonic-gate}
7187c478bdstevel@tonic-gate
7197c478bdstevel@tonic-gatevoid
7207c478bdstevel@tonic-gatebkmem_free(void *p, size_t bytes)
7217c478bdstevel@tonic-gate{
7227c478bdstevel@tonic-gate	kmem_free(p, bytes);
7237c478bdstevel@tonic-gate}
7247c478bdstevel@tonic-gate
7257c478bdstevel@tonic-gatestatic void
7267c478bdstevel@tonic-gatecheck_need_to_free(void)
7277c478bdstevel@tonic-gate{
7287c478bdstevel@tonic-gate	int i;
7297c478bdstevel@tonic-gate	struct need_to_free *ntf;
7307c478bdstevel@tonic-gate	caddr_t addr;
7317c478bdstevel@tonic-gate	size_t nbytes;
7327c478bdstevel@tonic-gate	int s;
7337c478bdstevel@tonic-gate
7347c478bdstevel@tonic-gateagain:
7357c478bdstevel@tonic-gate	s = splimp();
7367c478bdstevel@tonic-gate	ntf = &kmem_info.need_to_free_list;
7377c478bdstevel@tonic-gate	if (ntf->addr) {
7387c478bdstevel@tonic-gate		addr = ntf->addr;
7397c478bdstevel@tonic-gate		nbytes = ntf->nbytes;
7407c478bdstevel@tonic-gate		*ntf = *(struct need_to_free *)ntf->addr;
7417c478bdstevel@tonic-gate		splx(s);
7427c478bdstevel@tonic-gate		kmem_free(addr, nbytes);
7437c478bdstevel@tonic-gate		goto again;
7447c478bdstevel@tonic-gate	}
7457c478bdstevel@tonic-gate	ntf = kmem_info.need_to_free;
7467c478bdstevel@tonic-gate	for (i = 0; i < NEED_TO_FREE_SIZE; i++) {
7477c478bdstevel@tonic-gate		if (ntf[i].addr) {
7487c478bdstevel@tonic-gate			addr = ntf[i].addr;
7497c478bdstevel@tonic-gate			nbytes = ntf[i].nbytes;
7507c478bdstevel@tonic-gate			ntf[i].addr = 0;
7517c478bdstevel@tonic-gate			splx(s);
7527c478bdstevel@tonic-gate			kmem_free(addr, nbytes);
7537c478bdstevel@tonic-gate			goto again;
7547c478bdstevel@tonic-gate		}
7557c478bdstevel@tonic-gate	}
7567c478bdstevel@tonic-gate	splx(s);
7577c478bdstevel@tonic-gate}
7587c478bdstevel@tonic-gate
7597c478bdstevel@tonic-gate/*
7607c478bdstevel@tonic-gate * Add a block of at least nbytes to the free space tree.
7617c478bdstevel@tonic-gate *
7627c478bdstevel@tonic-gate * return value:
7637c478bdstevel@tonic-gate *	true	if at least nbytes can be allocated
7647c478bdstevel@tonic-gate *	false	otherwise
7657c478bdstevel@tonic-gate *
7667c478bdstevel@tonic-gate * remark:
7677c478bdstevel@tonic-gate *	free space (delimited by the static variable ubound) is
7687c478bdstevel@tonic-gate *	extended by an amount determined by rounding nbytes up to
7697c478bdstevel@tonic-gate *	a multiple of the system page size.
7707c478bdstevel@tonic-gate */
7717c478bdstevel@tonic-gate
7727c478bdstevel@tonic-gatestatic bool
7737c478bdstevel@tonic-gatemorecore(size_t nbytes)
7747c478bdstevel@tonic-gate{
7757c478bdstevel@tonic-gate#ifdef	__sparc
7767c478bdstevel@tonic-gate	enum RESOURCES type = RES_BOOTSCRATCH_NOFAIL;
7777c478bdstevel@tonic-gate#else
7787c478bdstevel@tonic-gate	enum RESOURCES type = RES_BOOTSCRATCH;
7797c478bdstevel@tonic-gate#endif
7807c478bdstevel@tonic-gate	Dblk p;
7817c478bdstevel@tonic-gate#ifdef	DEBUG
7827c478bdstevel@tonic-gate	printf("morecore(nbytes 0x%lx)\n", nbytes);
7837c478bdstevel@tonic-gate#endif	/* DEBUG */
7847c478bdstevel@tonic-gate
7857c478bdstevel@tonic-gate
7867c478bdstevel@tonic-gate	nbytes = roundup(nbytes, PAGESIZE);
7877c478bdstevel@tonic-gate	p = (Dblk) resalloc(type, nbytes, (caddr_t)0, 0);
7887c478bdstevel@tonic-gate	if (p == 0) {
7897c478bdstevel@tonic-gate		return (false);
7907c478bdstevel@tonic-gate	}
7917c478bdstevel@tonic-gate	kmem_free((caddr_t)p, nbytes);
7927c478bdstevel@tonic-gate#ifdef DEBUG
7937c478bdstevel@tonic-gate	printf("morecore() returing, p = %p\n", p);
7947c478bdstevel@tonic-gate#endif
7957c478bdstevel@tonic-gate	return (true);
7967c478bdstevel@tonic-gate
7977c478bdstevel@tonic-gate} /* morecore */
7987c478bdstevel@tonic-gate
7997c478bdstevel@tonic-gate/*
8007c478bdstevel@tonic-gate * Get a free block header
8017c478bdstevel@tonic-gate * There is a list of available free block headers.
8027c478bdstevel@tonic-gate * When the list is empty, allocate another pagefull.
8037c478bdstevel@tonic-gate */
8047c478bdstevel@tonic-gateFreehdr
8057c478bdstevel@tonic-gategetfreehdr(void)
8067c478bdstevel@tonic-gate{
8077c478bdstevel@tonic-gate	Freehdr	r;
8087c478bdstevel@tonic-gate	int	n = 0;
8097c478bdstevel@tonic-gate#ifdef	DEBUG
8107c478bdstevel@tonic-gate	printf("getfreehdr()\n");
8117c478bdstevel@tonic-gate#endif	/* DEBUG */
8127c478bdstevel@tonic-gate
8137c478bdstevel@tonic-gate	if (kmem_info.free_hdr_list != NIL) {
8147c478bdstevel@tonic-gate		r = kmem_info.free_hdr_list;
8157c478bdstevel@tonic-gate		kmem_info.free_hdr_list = kmem_info.free_hdr_list->left;
8167c478bdstevel@tonic-gate	} else {
8177c478bdstevel@tonic-gate		r = (Freehdr)resalloc(RES_BOOTSCRATCH, PAGESIZE, (caddr_t)0, 0);
8187c478bdstevel@tonic-gate		if (r == 0) {
8197c478bdstevel@tonic-gate			prom_panic("getfreehdr");
8207c478bdstevel@tonic-gate		}
8217c478bdstevel@tonic-gate		for (n = 1; n < PAGESIZE / sizeof (*r); n++) {
8227c478bdstevel@tonic-gate			freehdr(&r[n]);
8237c478bdstevel@tonic-gate		}
8247c478bdstevel@tonic-gate	}
8257c478bdstevel@tonic-gate#ifdef	DEBUG
8267c478bdstevel@tonic-gate	printf("getfreehdr: freed %x headers\n", n);
8277c478bdstevel@tonic-gate	printf("getfreehdr: returning %p\n", r);
8287c478bdstevel@tonic-gate#endif	/* DEBUG */
8297c478bdstevel@tonic-gate	return (r);
8307c478bdstevel@tonic-gate}
8317c478bdstevel@tonic-gate
8327c478bdstevel@tonic-gate/*
8337c478bdstevel@tonic-gate * Free a free block header
8347c478bdstevel@tonic-gate * Add it to the list of available headers.
8357c478bdstevel@tonic-gate */
8367c478bdstevel@tonic-gate
8377c478bdstevel@tonic-gatevoid
8387c478bdstevel@tonic-gatefreehdr(Freehdr p)
8397c478bdstevel@tonic-gate{
8407c478bdstevel@tonic-gate#ifdef	DEBUG
8417c478bdstevel@tonic-gate	printf("freehdr(%p)\n", p);
8427c478bdstevel@tonic-gate#endif	/* DEBUG */
8437c478bdstevel@tonic-gate	p->left = kmem_info.free_hdr_list;
8447c478bdstevel@tonic-gate	p->right = NIL;
8457c478bdstevel@tonic-gate	p->block = NULL;
8467c478bdstevel@tonic-gate	kmem_info.free_hdr_list = p;
8477c478bdstevel@tonic-gate}
8487c478bdstevel@tonic-gate
8497c478bdstevel@tonic-gate#ifdef DEBUG
8507c478bdstevel@tonic-gate/*
8517c478bdstevel@tonic-gate * Diagnostic routines
8527c478bdstevel@tonic-gate */
8537c478bdstevel@tonic-gatestatic int depth = 0;
8547c478bdstevel@tonic-gate
8557c478bdstevel@tonic-gatestatic void
8567c478bdstevel@tonic-gateprtree(Freehdr p, char *cp)
8577c478bdstevel@tonic-gate{
8587c478bdstevel@tonic-gate	int n;
8597c478bdstevel@tonic-gate	if (depth == 0) {
8607c478bdstevel@tonic-gate		printf("prtree(p %p cp %s)\n", p, cp);
8617c478bdstevel@tonic-gate	}
8627c478bdstevel@tonic-gate	if (p != NIL) {
8637c478bdstevel@tonic-gate		depth++;
8647c478bdstevel@tonic-gate		prtree(p->left, (char *)NULL);
8657c478bdstevel@tonic-gate		depth--;
8667c478bdstevel@tonic-gate
8677c478bdstevel@tonic-gate		for (n = 0; n < depth; n++) {
8687c478bdstevel@tonic-gate			printf("   ");
8697c478bdstevel@tonic-gate		}
8707c478bdstevel@tonic-gate		printf(
8717c478bdstevel@tonic-gate		    "(%p): (left = %p, right = %p, block = %p, size = %lx)\n",
8727c478bdstevel@tonic-gate			p, p->left, p->right, p->block, p->size);
8737c478bdstevel@tonic-gate
8747c478bdstevel@tonic-gate		depth++;
8757c478bdstevel@tonic-gate		prtree(p->right, (char *)NULL);
8767c478bdstevel@tonic-gate		depth--;
8777c478bdstevel@tonic-gate	}
8787c478bdstevel@tonic-gate}
8797c478bdstevel@tonic-gate#endif /* DEBUG */
880