1*7c478bd9Sstevel@tonic-gate /*
2*7c478bd9Sstevel@tonic-gate * CDDL HEADER START
3*7c478bd9Sstevel@tonic-gate *
4*7c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
5*7c478bd9Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only
6*7c478bd9Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance
7*7c478bd9Sstevel@tonic-gate * with the License.
8*7c478bd9Sstevel@tonic-gate *
9*7c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10*7c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
11*7c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
12*7c478bd9Sstevel@tonic-gate * and limitations under the License.
13*7c478bd9Sstevel@tonic-gate *
14*7c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
15*7c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16*7c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
17*7c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
18*7c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
19*7c478bd9Sstevel@tonic-gate *
20*7c478bd9Sstevel@tonic-gate * CDDL HEADER END
21*7c478bd9Sstevel@tonic-gate */
22*7c478bd9Sstevel@tonic-gate /*
23*7c478bd9Sstevel@tonic-gate * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
24*7c478bd9Sstevel@tonic-gate * Use is subject to license terms.
25*7c478bd9Sstevel@tonic-gate */
26*7c478bd9Sstevel@tonic-gate
27*7c478bd9Sstevel@tonic-gate #if 1
28*7c478bd9Sstevel@tonic-gate #undef DEBUG
29*7c478bd9Sstevel@tonic-gate #endif
30*7c478bd9Sstevel@tonic-gate
31*7c478bd9Sstevel@tonic-gate /* #define DEBUG ON */
32*7c478bd9Sstevel@tonic-gate
33*7c478bd9Sstevel@tonic-gate /*
34*7c478bd9Sstevel@tonic-gate * Conditions on use:
35*7c478bd9Sstevel@tonic-gate * kmem_alloc and kmem_free must not be called from interrupt level,
36*7c478bd9Sstevel@tonic-gate * except from software interrupt level. This is because they are
37*7c478bd9Sstevel@tonic-gate * not reentrant, and only block out software interrupts. They take
38*7c478bd9Sstevel@tonic-gate * too long to block any real devices. There is a routine
39*7c478bd9Sstevel@tonic-gate * kmem_free_intr that can be used to free blocks at interrupt level,
40*7c478bd9Sstevel@tonic-gate * but only up to splimp, not higher. This is because kmem_free_intr
41*7c478bd9Sstevel@tonic-gate * only spl's to splimp.
42*7c478bd9Sstevel@tonic-gate *
43*7c478bd9Sstevel@tonic-gate * Also, these routines are not that fast, so they should not be used
44*7c478bd9Sstevel@tonic-gate * in very frequent operations (e.g. operations that happen more often
45*7c478bd9Sstevel@tonic-gate * than, say, once every few seconds).
46*7c478bd9Sstevel@tonic-gate */
47*7c478bd9Sstevel@tonic-gate
48*7c478bd9Sstevel@tonic-gate /*
49*7c478bd9Sstevel@tonic-gate * description:
50*7c478bd9Sstevel@tonic-gate * Yet another memory allocator, this one based on a method
51*7c478bd9Sstevel@tonic-gate * described in C.J. Stephenson, "Fast Fits", IBM Sys. Journal
52*7c478bd9Sstevel@tonic-gate *
53*7c478bd9Sstevel@tonic-gate * The basic data structure is a "Cartesian" binary tree, in which
54*7c478bd9Sstevel@tonic-gate * nodes are ordered by ascending addresses (thus minimizing free
55*7c478bd9Sstevel@tonic-gate * list insertion time) and block sizes decrease with depth in the
56*7c478bd9Sstevel@tonic-gate * tree (thus minimizing search time for a block of a given size).
57*7c478bd9Sstevel@tonic-gate *
58*7c478bd9Sstevel@tonic-gate * In other words, for any node s, letting D(s) denote
59*7c478bd9Sstevel@tonic-gate * the set of descendents of s, we have:
60*7c478bd9Sstevel@tonic-gate *
61*7c478bd9Sstevel@tonic-gate * a. addr(D(left(s))) < addr(s) < addr(D(right(s)))
62*7c478bd9Sstevel@tonic-gate * b. len(D(left(s))) <= len(s) >= len(D(right(s)))
63*7c478bd9Sstevel@tonic-gate */
64*7c478bd9Sstevel@tonic-gate
65*7c478bd9Sstevel@tonic-gate #include <sys/param.h>
66*7c478bd9Sstevel@tonic-gate #include <sys/sysmacros.h>
67*7c478bd9Sstevel@tonic-gate #include <sys/salib.h>
68*7c478bd9Sstevel@tonic-gate #include <sys/saio.h>
69*7c478bd9Sstevel@tonic-gate #include <sys/promif.h>
70*7c478bd9Sstevel@tonic-gate
71*7c478bd9Sstevel@tonic-gate /*
72*7c478bd9Sstevel@tonic-gate * The node header structure.
73*7c478bd9Sstevel@tonic-gate *
74*7c478bd9Sstevel@tonic-gate * To reduce storage consumption, a header block is associated with
75*7c478bd9Sstevel@tonic-gate * free blocks only, not allocated blocks.
76*7c478bd9Sstevel@tonic-gate * When a free block is allocated, its header block is put on
77*7c478bd9Sstevel@tonic-gate * a free header block list.
78*7c478bd9Sstevel@tonic-gate *
79*7c478bd9Sstevel@tonic-gate * This creates a header space and a free block space.
80*7c478bd9Sstevel@tonic-gate * The left pointer of a header blocks is used to chain free header
81*7c478bd9Sstevel@tonic-gate * blocks together.
82*7c478bd9Sstevel@tonic-gate */
83*7c478bd9Sstevel@tonic-gate
84*7c478bd9Sstevel@tonic-gate typedef enum {false, true} bool;
85*7c478bd9Sstevel@tonic-gate typedef struct freehdr *Freehdr;
86*7c478bd9Sstevel@tonic-gate typedef struct dblk *Dblk;
87*7c478bd9Sstevel@tonic-gate
88*7c478bd9Sstevel@tonic-gate /*
89*7c478bd9Sstevel@tonic-gate * Description of a header for a free block
90*7c478bd9Sstevel@tonic-gate * Only free blocks have such headers.
91*7c478bd9Sstevel@tonic-gate */
92*7c478bd9Sstevel@tonic-gate struct freehdr {
93*7c478bd9Sstevel@tonic-gate Freehdr left; /* Left tree pointer */
94*7c478bd9Sstevel@tonic-gate Freehdr right; /* Right tree pointer */
95*7c478bd9Sstevel@tonic-gate Dblk block; /* Ptr to the data block */
96*7c478bd9Sstevel@tonic-gate size_t size; /* Size of the data block */
97*7c478bd9Sstevel@tonic-gate };
98*7c478bd9Sstevel@tonic-gate
99*7c478bd9Sstevel@tonic-gate #define NIL ((Freehdr) 0)
100*7c478bd9Sstevel@tonic-gate #define WORDSIZE sizeof (int)
101*7c478bd9Sstevel@tonic-gate #define SMALLEST_BLK 1 /* Size of smallest block */
102*7c478bd9Sstevel@tonic-gate
103*7c478bd9Sstevel@tonic-gate /*
104*7c478bd9Sstevel@tonic-gate * Description of a data block.
105*7c478bd9Sstevel@tonic-gate */
106*7c478bd9Sstevel@tonic-gate struct dblk {
107*7c478bd9Sstevel@tonic-gate char data[1]; /* Addr returned to the caller */
108*7c478bd9Sstevel@tonic-gate };
109*7c478bd9Sstevel@tonic-gate
110*7c478bd9Sstevel@tonic-gate /*
111*7c478bd9Sstevel@tonic-gate * weight(x) is the size of a block, in bytes; or 0 if and only if x
112*7c478bd9Sstevel@tonic-gate * is a null pointer. It is the responsibility of kmem_alloc() and
113*7c478bd9Sstevel@tonic-gate * kmem_free() to keep zero-length blocks out of the arena.
114*7c478bd9Sstevel@tonic-gate */
115*7c478bd9Sstevel@tonic-gate
116*7c478bd9Sstevel@tonic-gate #define weight(x) ((x) == NIL? 0: (x->size))
117*7c478bd9Sstevel@tonic-gate #define nextblk(p, size) ((Dblk) ((char *)(p) + (size)))
118*7c478bd9Sstevel@tonic-gate #define max(a, b) ((a) < (b)? (b): (a))
119*7c478bd9Sstevel@tonic-gate
120*7c478bd9Sstevel@tonic-gate void *kmem_alloc(size_t, int);
121*7c478bd9Sstevel@tonic-gate void kmem_free(void *ptr, size_t nbytes);
122*7c478bd9Sstevel@tonic-gate Freehdr getfreehdr(void);
123*7c478bd9Sstevel@tonic-gate static bool morecore(size_t);
124*7c478bd9Sstevel@tonic-gate void insert(Dblk p, size_t len, Freehdr *tree);
125*7c478bd9Sstevel@tonic-gate void freehdr(Freehdr p);
126*7c478bd9Sstevel@tonic-gate void delete(Freehdr *p);
127*7c478bd9Sstevel@tonic-gate static void check_need_to_free(void);
128*7c478bd9Sstevel@tonic-gate extern caddr_t resalloc(enum RESOURCES, size_t, caddr_t, int);
129*7c478bd9Sstevel@tonic-gate #ifdef __sparc
130*7c478bd9Sstevel@tonic-gate extern void resalloc_init(void);
131*7c478bd9Sstevel@tonic-gate #endif
132*7c478bd9Sstevel@tonic-gate extern int splnet(void);
133*7c478bd9Sstevel@tonic-gate extern int splimp(void);
134*7c478bd9Sstevel@tonic-gate extern void splx(int);
135*7c478bd9Sstevel@tonic-gate
136*7c478bd9Sstevel@tonic-gate /*
137*7c478bd9Sstevel@tonic-gate * Structure containing various info about allocated memory.
138*7c478bd9Sstevel@tonic-gate */
139*7c478bd9Sstevel@tonic-gate #define NEED_TO_FREE_SIZE 5
140*7c478bd9Sstevel@tonic-gate struct kmem_info {
141*7c478bd9Sstevel@tonic-gate Freehdr free_root;
142*7c478bd9Sstevel@tonic-gate Freehdr free_hdr_list;
143*7c478bd9Sstevel@tonic-gate struct map *map;
144*7c478bd9Sstevel@tonic-gate struct pte *pte;
145*7c478bd9Sstevel@tonic-gate caddr_t vaddr;
146*7c478bd9Sstevel@tonic-gate struct need_to_free {
147*7c478bd9Sstevel@tonic-gate caddr_t addr;
148*7c478bd9Sstevel@tonic-gate size_t nbytes;
149*7c478bd9Sstevel@tonic-gate } need_to_free_list, need_to_free[NEED_TO_FREE_SIZE];
150*7c478bd9Sstevel@tonic-gate } kmem_info;
151*7c478bd9Sstevel@tonic-gate
152*7c478bd9Sstevel@tonic-gate
153*7c478bd9Sstevel@tonic-gate struct map *kernelmap;
154*7c478bd9Sstevel@tonic-gate
155*7c478bd9Sstevel@tonic-gate #ifdef DEBUG
156*7c478bd9Sstevel@tonic-gate static void prtree(Freehdr, char *);
157*7c478bd9Sstevel@tonic-gate #endif
158*7c478bd9Sstevel@tonic-gate
159*7c478bd9Sstevel@tonic-gate /*
160*7c478bd9Sstevel@tonic-gate * Initialize kernel memory allocator
161*7c478bd9Sstevel@tonic-gate */
162*7c478bd9Sstevel@tonic-gate
163*7c478bd9Sstevel@tonic-gate void
kmem_init(void)164*7c478bd9Sstevel@tonic-gate kmem_init(void)
165*7c478bd9Sstevel@tonic-gate {
166*7c478bd9Sstevel@tonic-gate int i;
167*7c478bd9Sstevel@tonic-gate struct need_to_free *ntf;
168*7c478bd9Sstevel@tonic-gate
169*7c478bd9Sstevel@tonic-gate #ifdef DEBUG
170*7c478bd9Sstevel@tonic-gate printf("kmem_init entered\n");
171*7c478bd9Sstevel@tonic-gate #endif
172*7c478bd9Sstevel@tonic-gate
173*7c478bd9Sstevel@tonic-gate #ifdef __sparc
174*7c478bd9Sstevel@tonic-gate resalloc_init();
175*7c478bd9Sstevel@tonic-gate #endif
176*7c478bd9Sstevel@tonic-gate
177*7c478bd9Sstevel@tonic-gate kmem_info.free_root = NIL;
178*7c478bd9Sstevel@tonic-gate kmem_info.free_hdr_list = NULL;
179*7c478bd9Sstevel@tonic-gate kmem_info.map = kernelmap;
180*7c478bd9Sstevel@tonic-gate kmem_info.need_to_free_list.addr = 0;
181*7c478bd9Sstevel@tonic-gate ntf = kmem_info.need_to_free;
182*7c478bd9Sstevel@tonic-gate for (i = 0; i < NEED_TO_FREE_SIZE; i++) {
183*7c478bd9Sstevel@tonic-gate ntf[i].addr = 0;
184*7c478bd9Sstevel@tonic-gate }
185*7c478bd9Sstevel@tonic-gate #ifdef DEBUG
186*7c478bd9Sstevel@tonic-gate printf("kmem_init returning\n");
187*7c478bd9Sstevel@tonic-gate prtree(kmem_info.free_root, "kmem_init");
188*7c478bd9Sstevel@tonic-gate #endif
189*7c478bd9Sstevel@tonic-gate }
190*7c478bd9Sstevel@tonic-gate
191*7c478bd9Sstevel@tonic-gate /*
192*7c478bd9Sstevel@tonic-gate * Insert a new node in a cartesian tree or subtree, placing it
193*7c478bd9Sstevel@tonic-gate * in the correct position with respect to the existing nodes.
194*7c478bd9Sstevel@tonic-gate *
195*7c478bd9Sstevel@tonic-gate * algorithm:
196*7c478bd9Sstevel@tonic-gate * Starting from the root, a binary search is made for the new
197*7c478bd9Sstevel@tonic-gate * node. If this search were allowed to continue, it would
198*7c478bd9Sstevel@tonic-gate * eventually fail (since there cannot already be a node at the
199*7c478bd9Sstevel@tonic-gate * given address); but in fact it stops when it reaches a node in
200*7c478bd9Sstevel@tonic-gate * the tree which has a length less than that of the new node (or
201*7c478bd9Sstevel@tonic-gate * when it reaches a null tree pointer). The new node is then
202*7c478bd9Sstevel@tonic-gate * inserted at the root of the subtree for which the shorter node
203*7c478bd9Sstevel@tonic-gate * forms the old root (or in place of the null pointer).
204*7c478bd9Sstevel@tonic-gate */
205*7c478bd9Sstevel@tonic-gate
206*7c478bd9Sstevel@tonic-gate
207*7c478bd9Sstevel@tonic-gate void
insert(Dblk p,size_t len,Freehdr * tree)208*7c478bd9Sstevel@tonic-gate insert(Dblk p, /* Ptr to the block to insert */
209*7c478bd9Sstevel@tonic-gate size_t len, /* Length of new node */
210*7c478bd9Sstevel@tonic-gate Freehdr *tree) /* Address of ptr to root */
211*7c478bd9Sstevel@tonic-gate {
212*7c478bd9Sstevel@tonic-gate Freehdr x;
213*7c478bd9Sstevel@tonic-gate Freehdr *left_hook; /* Temp for insertion */
214*7c478bd9Sstevel@tonic-gate Freehdr *right_hook; /* Temp for insertion */
215*7c478bd9Sstevel@tonic-gate Freehdr newhdr;
216*7c478bd9Sstevel@tonic-gate
217*7c478bd9Sstevel@tonic-gate x = *tree;
218*7c478bd9Sstevel@tonic-gate /*
219*7c478bd9Sstevel@tonic-gate * Search for the first node which has a weight less
220*7c478bd9Sstevel@tonic-gate * than that of the new node; this will be the
221*7c478bd9Sstevel@tonic-gate * point at which we insert the new node.
222*7c478bd9Sstevel@tonic-gate */
223*7c478bd9Sstevel@tonic-gate
224*7c478bd9Sstevel@tonic-gate while (weight(x) >= len) {
225*7c478bd9Sstevel@tonic-gate if (p < x->block)
226*7c478bd9Sstevel@tonic-gate tree = &x->left;
227*7c478bd9Sstevel@tonic-gate else
228*7c478bd9Sstevel@tonic-gate tree = &x->right;
229*7c478bd9Sstevel@tonic-gate x = *tree;
230*7c478bd9Sstevel@tonic-gate }
231*7c478bd9Sstevel@tonic-gate
232*7c478bd9Sstevel@tonic-gate /*
233*7c478bd9Sstevel@tonic-gate * Perform root insertion. The variable x traces a path through
234*7c478bd9Sstevel@tonic-gate * the tree, and with the help of left_hook and right_hook,
235*7c478bd9Sstevel@tonic-gate * rewrites all links that cross the territory occupied
236*7c478bd9Sstevel@tonic-gate * by p. Note that this improves performance under
237*7c478bd9Sstevel@tonic-gate * paging.
238*7c478bd9Sstevel@tonic-gate */
239*7c478bd9Sstevel@tonic-gate
240*7c478bd9Sstevel@tonic-gate newhdr = getfreehdr();
241*7c478bd9Sstevel@tonic-gate *tree = newhdr;
242*7c478bd9Sstevel@tonic-gate left_hook = &newhdr->left;
243*7c478bd9Sstevel@tonic-gate right_hook = &newhdr->right;
244*7c478bd9Sstevel@tonic-gate
245*7c478bd9Sstevel@tonic-gate newhdr->left = NIL;
246*7c478bd9Sstevel@tonic-gate newhdr->right = NIL;
247*7c478bd9Sstevel@tonic-gate newhdr->block = p;
248*7c478bd9Sstevel@tonic-gate newhdr->size = len;
249*7c478bd9Sstevel@tonic-gate
250*7c478bd9Sstevel@tonic-gate while (x != NIL) {
251*7c478bd9Sstevel@tonic-gate /*
252*7c478bd9Sstevel@tonic-gate * Remark:
253*7c478bd9Sstevel@tonic-gate * The name 'left_hook' is somewhat confusing, since
254*7c478bd9Sstevel@tonic-gate * it is always set to the address of a .right link
255*7c478bd9Sstevel@tonic-gate * field. However, its value is always an address
256*7c478bd9Sstevel@tonic-gate * below (i.e., to the left of) p. Similarly
257*7c478bd9Sstevel@tonic-gate * for right_hook. The values of left_hook and
258*7c478bd9Sstevel@tonic-gate * right_hook converge toward the value of p,
259*7c478bd9Sstevel@tonic-gate * as in a classical binary search.
260*7c478bd9Sstevel@tonic-gate */
261*7c478bd9Sstevel@tonic-gate if (x->block < p) {
262*7c478bd9Sstevel@tonic-gate /*
263*7c478bd9Sstevel@tonic-gate * rewrite link crossing from the left
264*7c478bd9Sstevel@tonic-gate */
265*7c478bd9Sstevel@tonic-gate *left_hook = x;
266*7c478bd9Sstevel@tonic-gate left_hook = &x->right;
267*7c478bd9Sstevel@tonic-gate x = x->right;
268*7c478bd9Sstevel@tonic-gate } else {
269*7c478bd9Sstevel@tonic-gate /*
270*7c478bd9Sstevel@tonic-gate * rewrite link crossing from the right
271*7c478bd9Sstevel@tonic-gate */
272*7c478bd9Sstevel@tonic-gate *right_hook = x;
273*7c478bd9Sstevel@tonic-gate right_hook = &x->left;
274*7c478bd9Sstevel@tonic-gate x = x->left;
275*7c478bd9Sstevel@tonic-gate } /* else */
276*7c478bd9Sstevel@tonic-gate } /* while */
277*7c478bd9Sstevel@tonic-gate
278*7c478bd9Sstevel@tonic-gate *left_hook = *right_hook = NIL; /* clear remaining hooks */
279*7c478bd9Sstevel@tonic-gate
280*7c478bd9Sstevel@tonic-gate } /* insert */
281*7c478bd9Sstevel@tonic-gate
282*7c478bd9Sstevel@tonic-gate
283*7c478bd9Sstevel@tonic-gate /*
284*7c478bd9Sstevel@tonic-gate * Delete a node from a cartesian tree. p is the address of
285*7c478bd9Sstevel@tonic-gate * a pointer to the node which is to be deleted.
286*7c478bd9Sstevel@tonic-gate *
287*7c478bd9Sstevel@tonic-gate * algorithm:
288*7c478bd9Sstevel@tonic-gate * The left and right sons of the node to be deleted define two
289*7c478bd9Sstevel@tonic-gate * subtrees which are to be merged and attached in place of the
290*7c478bd9Sstevel@tonic-gate * deleted node. Each node on the inside edges of these two
291*7c478bd9Sstevel@tonic-gate * subtrees is examined and longer nodes are placed above the
292*7c478bd9Sstevel@tonic-gate * shorter ones.
293*7c478bd9Sstevel@tonic-gate *
294*7c478bd9Sstevel@tonic-gate * On entry:
295*7c478bd9Sstevel@tonic-gate * *p is assumed to be non-null.
296*7c478bd9Sstevel@tonic-gate */
297*7c478bd9Sstevel@tonic-gate
298*7c478bd9Sstevel@tonic-gate void
delete(Freehdr * p)299*7c478bd9Sstevel@tonic-gate delete(Freehdr *p)
300*7c478bd9Sstevel@tonic-gate {
301*7c478bd9Sstevel@tonic-gate Freehdr x;
302*7c478bd9Sstevel@tonic-gate Freehdr left_branch; /* left subtree of deleted node */
303*7c478bd9Sstevel@tonic-gate Freehdr right_branch; /* right subtree of deleted node */
304*7c478bd9Sstevel@tonic-gate
305*7c478bd9Sstevel@tonic-gate x = *p;
306*7c478bd9Sstevel@tonic-gate left_branch = x->left;
307*7c478bd9Sstevel@tonic-gate right_branch = x->right;
308*7c478bd9Sstevel@tonic-gate
309*7c478bd9Sstevel@tonic-gate while (left_branch != right_branch) {
310*7c478bd9Sstevel@tonic-gate /*
311*7c478bd9Sstevel@tonic-gate * iterate until left branch and right branch are
312*7c478bd9Sstevel@tonic-gate * both NIL.
313*7c478bd9Sstevel@tonic-gate */
314*7c478bd9Sstevel@tonic-gate if (weight(left_branch) >= weight(right_branch)) {
315*7c478bd9Sstevel@tonic-gate /*
316*7c478bd9Sstevel@tonic-gate * promote the left branch
317*7c478bd9Sstevel@tonic-gate */
318*7c478bd9Sstevel@tonic-gate *p = left_branch;
319*7c478bd9Sstevel@tonic-gate p = &left_branch->right;
320*7c478bd9Sstevel@tonic-gate left_branch = left_branch->right;
321*7c478bd9Sstevel@tonic-gate } else {
322*7c478bd9Sstevel@tonic-gate /*
323*7c478bd9Sstevel@tonic-gate * promote the right branch
324*7c478bd9Sstevel@tonic-gate */
325*7c478bd9Sstevel@tonic-gate *p = right_branch;
326*7c478bd9Sstevel@tonic-gate p = &right_branch->left;
327*7c478bd9Sstevel@tonic-gate right_branch = right_branch->left;
328*7c478bd9Sstevel@tonic-gate } /* else */
329*7c478bd9Sstevel@tonic-gate } /* while */
330*7c478bd9Sstevel@tonic-gate *p = NIL;
331*7c478bd9Sstevel@tonic-gate freehdr(x);
332*7c478bd9Sstevel@tonic-gate } /* delete */
333*7c478bd9Sstevel@tonic-gate
334*7c478bd9Sstevel@tonic-gate
335*7c478bd9Sstevel@tonic-gate /*
336*7c478bd9Sstevel@tonic-gate * Demote a node in a cartesian tree, if necessary, to establish
337*7c478bd9Sstevel@tonic-gate * the required vertical ordering.
338*7c478bd9Sstevel@tonic-gate *
339*7c478bd9Sstevel@tonic-gate * algorithm:
340*7c478bd9Sstevel@tonic-gate * The left and right subtrees of the node to be demoted are to
341*7c478bd9Sstevel@tonic-gate * be partially merged and attached in place of the demoted node.
342*7c478bd9Sstevel@tonic-gate * The nodes on the inside edges of these two subtrees are
343*7c478bd9Sstevel@tonic-gate * examined and the longer nodes are placed above the shorter
344*7c478bd9Sstevel@tonic-gate * ones, until a node is reached which has a length no greater
345*7c478bd9Sstevel@tonic-gate * than that of the node being demoted (or until a null pointer
346*7c478bd9Sstevel@tonic-gate * is reached). The node is then attached at this point, and
347*7c478bd9Sstevel@tonic-gate * the remaining subtrees (if any) become its descendants.
348*7c478bd9Sstevel@tonic-gate *
349*7c478bd9Sstevel@tonic-gate * on entry:
350*7c478bd9Sstevel@tonic-gate * a. All the nodes in the tree, including the one to be demoted,
351*7c478bd9Sstevel@tonic-gate * must be correctly ordered horizontally;
352*7c478bd9Sstevel@tonic-gate * b. All the nodes except the one to be demoted must also be
353*7c478bd9Sstevel@tonic-gate * correctly positioned vertically. The node to be demoted
354*7c478bd9Sstevel@tonic-gate * may be already correctly positioned vertically, or it may
355*7c478bd9Sstevel@tonic-gate * have a length which is less than that of one or both of
356*7c478bd9Sstevel@tonic-gate * its progeny.
357*7c478bd9Sstevel@tonic-gate * c. *p is non-null
358*7c478bd9Sstevel@tonic-gate */
359*7c478bd9Sstevel@tonic-gate
360*7c478bd9Sstevel@tonic-gate
361*7c478bd9Sstevel@tonic-gate static void
demote(Freehdr * p)362*7c478bd9Sstevel@tonic-gate demote(Freehdr *p)
363*7c478bd9Sstevel@tonic-gate {
364*7c478bd9Sstevel@tonic-gate Freehdr x; /* addr of node to be demoted */
365*7c478bd9Sstevel@tonic-gate Freehdr left_branch;
366*7c478bd9Sstevel@tonic-gate Freehdr right_branch;
367*7c478bd9Sstevel@tonic-gate size_t wx;
368*7c478bd9Sstevel@tonic-gate
369*7c478bd9Sstevel@tonic-gate x = *p;
370*7c478bd9Sstevel@tonic-gate left_branch = x->left;
371*7c478bd9Sstevel@tonic-gate right_branch = x->right;
372*7c478bd9Sstevel@tonic-gate wx = weight(x);
373*7c478bd9Sstevel@tonic-gate
374*7c478bd9Sstevel@tonic-gate while (weight(left_branch) > wx || weight(right_branch) > wx) {
375*7c478bd9Sstevel@tonic-gate /*
376*7c478bd9Sstevel@tonic-gate * select a descendant branch for promotion
377*7c478bd9Sstevel@tonic-gate */
378*7c478bd9Sstevel@tonic-gate if (weight(left_branch) >= weight(right_branch)) {
379*7c478bd9Sstevel@tonic-gate /*
380*7c478bd9Sstevel@tonic-gate * promote the left branch
381*7c478bd9Sstevel@tonic-gate */
382*7c478bd9Sstevel@tonic-gate *p = left_branch;
383*7c478bd9Sstevel@tonic-gate p = &left_branch->right;
384*7c478bd9Sstevel@tonic-gate left_branch = *p;
385*7c478bd9Sstevel@tonic-gate } else {
386*7c478bd9Sstevel@tonic-gate /*
387*7c478bd9Sstevel@tonic-gate * promote the right branch
388*7c478bd9Sstevel@tonic-gate */
389*7c478bd9Sstevel@tonic-gate *p = right_branch;
390*7c478bd9Sstevel@tonic-gate p = &right_branch->left;
391*7c478bd9Sstevel@tonic-gate right_branch = *p;
392*7c478bd9Sstevel@tonic-gate } /* else */
393*7c478bd9Sstevel@tonic-gate } /* while */
394*7c478bd9Sstevel@tonic-gate
395*7c478bd9Sstevel@tonic-gate *p = x; /* attach demoted node here */
396*7c478bd9Sstevel@tonic-gate x->left = left_branch;
397*7c478bd9Sstevel@tonic-gate x->right = right_branch;
398*7c478bd9Sstevel@tonic-gate } /* demote */
399*7c478bd9Sstevel@tonic-gate
400*7c478bd9Sstevel@tonic-gate /*
401*7c478bd9Sstevel@tonic-gate * Allocate a block of storage
402*7c478bd9Sstevel@tonic-gate *
403*7c478bd9Sstevel@tonic-gate * algorithm:
404*7c478bd9Sstevel@tonic-gate * The freelist is searched by descending the tree from the root
405*7c478bd9Sstevel@tonic-gate * so that at each decision point the "better fitting" child node
406*7c478bd9Sstevel@tonic-gate * is chosen (i.e., the shorter one, if it is long enough, or
407*7c478bd9Sstevel@tonic-gate * the longer one, otherwise). The descent stops when both
408*7c478bd9Sstevel@tonic-gate * child nodes are too short.
409*7c478bd9Sstevel@tonic-gate *
410*7c478bd9Sstevel@tonic-gate * function result:
411*7c478bd9Sstevel@tonic-gate * kmem_alloc returns a pointer to the allocated block; a null
412*7c478bd9Sstevel@tonic-gate * pointer indicates storage could not be allocated.
413*7c478bd9Sstevel@tonic-gate */
414*7c478bd9Sstevel@tonic-gate /*
415*7c478bd9Sstevel@tonic-gate * We need to return blocks that are on word boundaries so that callers
416*7c478bd9Sstevel@tonic-gate * that are putting int's into the area will work. Since we allow
417*7c478bd9Sstevel@tonic-gate * arbitrary free'ing, we need a weight function that considers
418*7c478bd9Sstevel@tonic-gate * free blocks starting on an odd boundary special. Allocation is
419*7c478bd9Sstevel@tonic-gate * aligned to 8 byte boundaries (ALIGN).
420*7c478bd9Sstevel@tonic-gate */
421*7c478bd9Sstevel@tonic-gate #define ALIGN 8 /* doubleword aligned .. */
422*7c478bd9Sstevel@tonic-gate #define ALIGNMASK (ALIGN-1)
423*7c478bd9Sstevel@tonic-gate #define ALIGNMORE(addr) (ALIGN - ((uintptr_t)(addr) & ALIGNMASK))
424*7c478bd9Sstevel@tonic-gate
425*7c478bd9Sstevel@tonic-gate /*
426*7c478bd9Sstevel@tonic-gate * If it is empty then weight == 0
427*7c478bd9Sstevel@tonic-gate * If it is aligned then weight == size
428*7c478bd9Sstevel@tonic-gate * If it is unaligned
429*7c478bd9Sstevel@tonic-gate * if not enough room to align then weight == 0
430*7c478bd9Sstevel@tonic-gate * else weight == aligned size
431*7c478bd9Sstevel@tonic-gate */
432*7c478bd9Sstevel@tonic-gate #define mweight(x) ((x) == NIL ? 0 : \
433*7c478bd9Sstevel@tonic-gate ((((uintptr_t)(x)->block) & ALIGNMASK) == 0 ? (x)->size : \
434*7c478bd9Sstevel@tonic-gate (((x)->size <= ALIGNMORE((x)->block)) ? 0 : \
435*7c478bd9Sstevel@tonic-gate (x)->size - ALIGNMORE((x)->block))))
436*7c478bd9Sstevel@tonic-gate
437*7c478bd9Sstevel@tonic-gate /*ARGSUSED1*/
438*7c478bd9Sstevel@tonic-gate void *
kmem_alloc(size_t nbytes,int kmflag)439*7c478bd9Sstevel@tonic-gate kmem_alloc(size_t nbytes, int kmflag)
440*7c478bd9Sstevel@tonic-gate {
441*7c478bd9Sstevel@tonic-gate Freehdr a; /* ptr to node to be allocated */
442*7c478bd9Sstevel@tonic-gate Freehdr *p; /* address of ptr to node */
443*7c478bd9Sstevel@tonic-gate size_t left_weight;
444*7c478bd9Sstevel@tonic-gate size_t right_weight;
445*7c478bd9Sstevel@tonic-gate Freehdr left_son;
446*7c478bd9Sstevel@tonic-gate Freehdr right_son;
447*7c478bd9Sstevel@tonic-gate char *retblock; /* Address returned to the user */
448*7c478bd9Sstevel@tonic-gate int s;
449*7c478bd9Sstevel@tonic-gate #ifdef DEBUG
450*7c478bd9Sstevel@tonic-gate printf("kmem_alloc(nbytes 0x%lx)\n", nbytes);
451*7c478bd9Sstevel@tonic-gate #endif /* DEBUG */
452*7c478bd9Sstevel@tonic-gate
453*7c478bd9Sstevel@tonic-gate if (nbytes == 0) {
454*7c478bd9Sstevel@tonic-gate return (NULL);
455*7c478bd9Sstevel@tonic-gate }
456*7c478bd9Sstevel@tonic-gate s = splnet();
457*7c478bd9Sstevel@tonic-gate
458*7c478bd9Sstevel@tonic-gate if (nbytes < SMALLEST_BLK) {
459*7c478bd9Sstevel@tonic-gate printf("illegal kmem_alloc call for %lx bytes\n", nbytes);
460*7c478bd9Sstevel@tonic-gate prom_panic("kmem_alloc");
461*7c478bd9Sstevel@tonic-gate }
462*7c478bd9Sstevel@tonic-gate check_need_to_free();
463*7c478bd9Sstevel@tonic-gate
464*7c478bd9Sstevel@tonic-gate /*
465*7c478bd9Sstevel@tonic-gate * ensure that at least one block is big enough to satisfy
466*7c478bd9Sstevel@tonic-gate * the request.
467*7c478bd9Sstevel@tonic-gate */
468*7c478bd9Sstevel@tonic-gate
469*7c478bd9Sstevel@tonic-gate if (mweight(kmem_info.free_root) <= nbytes) {
470*7c478bd9Sstevel@tonic-gate /*
471*7c478bd9Sstevel@tonic-gate * the largest block is not enough.
472*7c478bd9Sstevel@tonic-gate */
473*7c478bd9Sstevel@tonic-gate if (!morecore(nbytes)) {
474*7c478bd9Sstevel@tonic-gate printf("kmem_alloc failed, nbytes %lx\n", nbytes);
475*7c478bd9Sstevel@tonic-gate prom_panic("kmem_alloc");
476*7c478bd9Sstevel@tonic-gate }
477*7c478bd9Sstevel@tonic-gate }
478*7c478bd9Sstevel@tonic-gate
479*7c478bd9Sstevel@tonic-gate /*
480*7c478bd9Sstevel@tonic-gate * search down through the tree until a suitable block is
481*7c478bd9Sstevel@tonic-gate * found. At each decision point, select the better
482*7c478bd9Sstevel@tonic-gate * fitting node.
483*7c478bd9Sstevel@tonic-gate */
484*7c478bd9Sstevel@tonic-gate
485*7c478bd9Sstevel@tonic-gate p = (Freehdr *) &kmem_info.free_root;
486*7c478bd9Sstevel@tonic-gate a = *p;
487*7c478bd9Sstevel@tonic-gate left_son = a->left;
488*7c478bd9Sstevel@tonic-gate right_son = a->right;
489*7c478bd9Sstevel@tonic-gate left_weight = mweight(left_son);
490*7c478bd9Sstevel@tonic-gate right_weight = mweight(right_son);
491*7c478bd9Sstevel@tonic-gate
492*7c478bd9Sstevel@tonic-gate while (left_weight >= nbytes || right_weight >= nbytes) {
493*7c478bd9Sstevel@tonic-gate if (left_weight <= right_weight) {
494*7c478bd9Sstevel@tonic-gate if (left_weight >= nbytes) {
495*7c478bd9Sstevel@tonic-gate p = &a->left;
496*7c478bd9Sstevel@tonic-gate a = left_son;
497*7c478bd9Sstevel@tonic-gate } else {
498*7c478bd9Sstevel@tonic-gate p = &a->right;
499*7c478bd9Sstevel@tonic-gate a = right_son;
500*7c478bd9Sstevel@tonic-gate }
501*7c478bd9Sstevel@tonic-gate } else {
502*7c478bd9Sstevel@tonic-gate if (right_weight >= nbytes) {
503*7c478bd9Sstevel@tonic-gate p = &a->right;
504*7c478bd9Sstevel@tonic-gate a = right_son;
505*7c478bd9Sstevel@tonic-gate } else {
506*7c478bd9Sstevel@tonic-gate p = &a->left;
507*7c478bd9Sstevel@tonic-gate a = left_son;
508*7c478bd9Sstevel@tonic-gate }
509*7c478bd9Sstevel@tonic-gate }
510*7c478bd9Sstevel@tonic-gate left_son = a->left;
511*7c478bd9Sstevel@tonic-gate right_son = a->right;
512*7c478bd9Sstevel@tonic-gate left_weight = mweight(left_son);
513*7c478bd9Sstevel@tonic-gate right_weight = mweight(right_son);
514*7c478bd9Sstevel@tonic-gate } /* while */
515*7c478bd9Sstevel@tonic-gate
516*7c478bd9Sstevel@tonic-gate /*
517*7c478bd9Sstevel@tonic-gate * allocate storage from the selected node.
518*7c478bd9Sstevel@tonic-gate */
519*7c478bd9Sstevel@tonic-gate
520*7c478bd9Sstevel@tonic-gate if (a->size - nbytes < SMALLEST_BLK) {
521*7c478bd9Sstevel@tonic-gate /*
522*7c478bd9Sstevel@tonic-gate * not big enough to split; must leave at least
523*7c478bd9Sstevel@tonic-gate * a dblk's worth of space.
524*7c478bd9Sstevel@tonic-gate */
525*7c478bd9Sstevel@tonic-gate retblock = a->block->data;
526*7c478bd9Sstevel@tonic-gate delete(p);
527*7c478bd9Sstevel@tonic-gate } else {
528*7c478bd9Sstevel@tonic-gate
529*7c478bd9Sstevel@tonic-gate /*
530*7c478bd9Sstevel@tonic-gate * split the node, allocating nbytes from the top.
531*7c478bd9Sstevel@tonic-gate * Remember we've already accounted for the
532*7c478bd9Sstevel@tonic-gate * allocated node's header space.
533*7c478bd9Sstevel@tonic-gate */
534*7c478bd9Sstevel@tonic-gate Freehdr x;
535*7c478bd9Sstevel@tonic-gate x = getfreehdr();
536*7c478bd9Sstevel@tonic-gate if ((uintptr_t)a->block->data & ALIGNMASK) {
537*7c478bd9Sstevel@tonic-gate size_t size;
538*7c478bd9Sstevel@tonic-gate if (a->size <= ALIGNMORE(a->block->data))
539*7c478bd9Sstevel@tonic-gate prom_panic("kmem_alloc: short block allocated");
540*7c478bd9Sstevel@tonic-gate size = nbytes + ALIGNMORE(a->block->data);
541*7c478bd9Sstevel@tonic-gate x->block = a->block;
542*7c478bd9Sstevel@tonic-gate x->size = ALIGNMORE(a->block->data);
543*7c478bd9Sstevel@tonic-gate x->left = a->left;
544*7c478bd9Sstevel@tonic-gate x->right = a->right;
545*7c478bd9Sstevel@tonic-gate /*
546*7c478bd9Sstevel@tonic-gate * the node pointed to by *p has become smaller;
547*7c478bd9Sstevel@tonic-gate * move it down to its appropriate place in
548*7c478bd9Sstevel@tonic-gate * the tree.
549*7c478bd9Sstevel@tonic-gate */
550*7c478bd9Sstevel@tonic-gate *p = x;
551*7c478bd9Sstevel@tonic-gate demote(p);
552*7c478bd9Sstevel@tonic-gate retblock = a->block->data + ALIGNMORE(a->block->data);
553*7c478bd9Sstevel@tonic-gate if (a->size > size) {
554*7c478bd9Sstevel@tonic-gate kmem_free((caddr_t)nextblk(a->block, size),
555*7c478bd9Sstevel@tonic-gate (size_t)(a->size - size));
556*7c478bd9Sstevel@tonic-gate }
557*7c478bd9Sstevel@tonic-gate freehdr(a);
558*7c478bd9Sstevel@tonic-gate } else {
559*7c478bd9Sstevel@tonic-gate x->block = nextblk(a->block, nbytes);
560*7c478bd9Sstevel@tonic-gate x->size = a->size - nbytes;
561*7c478bd9Sstevel@tonic-gate x->left = a->left;
562*7c478bd9Sstevel@tonic-gate x->right = a->right;
563*7c478bd9Sstevel@tonic-gate /*
564*7c478bd9Sstevel@tonic-gate * the node pointed to by *p has become smaller;
565*7c478bd9Sstevel@tonic-gate * move it down to its appropriate place in
566*7c478bd9Sstevel@tonic-gate * the tree.
567*7c478bd9Sstevel@tonic-gate */
568*7c478bd9Sstevel@tonic-gate *p = x;
569*7c478bd9Sstevel@tonic-gate demote(p);
570*7c478bd9Sstevel@tonic-gate retblock = a->block->data;
571*7c478bd9Sstevel@tonic-gate freehdr(a);
572*7c478bd9Sstevel@tonic-gate }
573*7c478bd9Sstevel@tonic-gate }
574*7c478bd9Sstevel@tonic-gate #ifdef DEBUG
575*7c478bd9Sstevel@tonic-gate prtree(kmem_info.free_root, "kmem_alloc");
576*7c478bd9Sstevel@tonic-gate #endif
577*7c478bd9Sstevel@tonic-gate
578*7c478bd9Sstevel@tonic-gate splx(s);
579*7c478bd9Sstevel@tonic-gate bzero(retblock, nbytes);
580*7c478bd9Sstevel@tonic-gate #ifdef DEBUG
581*7c478bd9Sstevel@tonic-gate printf("kmem_alloc bzero complete - returning %p\n", retblock);
582*7c478bd9Sstevel@tonic-gate #endif
583*7c478bd9Sstevel@tonic-gate return (retblock);
584*7c478bd9Sstevel@tonic-gate
585*7c478bd9Sstevel@tonic-gate } /* kmem_alloc */
586*7c478bd9Sstevel@tonic-gate
587*7c478bd9Sstevel@tonic-gate /*
588*7c478bd9Sstevel@tonic-gate * Return a block to the free space tree.
589*7c478bd9Sstevel@tonic-gate *
590*7c478bd9Sstevel@tonic-gate * algorithm:
591*7c478bd9Sstevel@tonic-gate * Starting at the root, search for and coalesce free blocks
592*7c478bd9Sstevel@tonic-gate * adjacent to one given. When the appropriate place in the
593*7c478bd9Sstevel@tonic-gate * tree is found, insert the given block.
594*7c478bd9Sstevel@tonic-gate *
595*7c478bd9Sstevel@tonic-gate * Do some sanity checks to avoid total confusion in the tree.
596*7c478bd9Sstevel@tonic-gate * If the block has already been freed, prom_panic.
597*7c478bd9Sstevel@tonic-gate * If the ptr is not from the arena, prom_panic.
598*7c478bd9Sstevel@tonic-gate */
599*7c478bd9Sstevel@tonic-gate void
kmem_free(void * ptr,size_t nbytes)600*7c478bd9Sstevel@tonic-gate kmem_free(void *ptr, size_t nbytes)
601*7c478bd9Sstevel@tonic-gate {
602*7c478bd9Sstevel@tonic-gate Freehdr *np; /* For deletion from free list */
603*7c478bd9Sstevel@tonic-gate Freehdr neighbor; /* Node to be coalesced */
604*7c478bd9Sstevel@tonic-gate char *neigh_block; /* Ptr to potential neighbor */
605*7c478bd9Sstevel@tonic-gate size_t neigh_size; /* Size of potential neighbor */
606*7c478bd9Sstevel@tonic-gate int s;
607*7c478bd9Sstevel@tonic-gate
608*7c478bd9Sstevel@tonic-gate #ifdef DEBUG
609*7c478bd9Sstevel@tonic-gate printf("kmem_free (ptr %p nbytes %lx)\n", ptr, nbytes);
610*7c478bd9Sstevel@tonic-gate prtree(kmem_info.free_root, "kmem_free");
611*7c478bd9Sstevel@tonic-gate #endif
612*7c478bd9Sstevel@tonic-gate
613*7c478bd9Sstevel@tonic-gate #ifdef lint
614*7c478bd9Sstevel@tonic-gate neigh_block = bkmem_zalloc(nbytes);
615*7c478bd9Sstevel@tonic-gate neigh_block = neigh_block;
616*7c478bd9Sstevel@tonic-gate #endif
617*7c478bd9Sstevel@tonic-gate if (nbytes == 0) {
618*7c478bd9Sstevel@tonic-gate return;
619*7c478bd9Sstevel@tonic-gate }
620*7c478bd9Sstevel@tonic-gate
621*7c478bd9Sstevel@tonic-gate if (ptr == 0) {
622*7c478bd9Sstevel@tonic-gate prom_panic("kmem_free of 0");
623*7c478bd9Sstevel@tonic-gate }
624*7c478bd9Sstevel@tonic-gate s = splnet();
625*7c478bd9Sstevel@tonic-gate
626*7c478bd9Sstevel@tonic-gate /*
627*7c478bd9Sstevel@tonic-gate * Search the tree for the correct insertion point for this
628*7c478bd9Sstevel@tonic-gate * node, coalescing adjacent free blocks along the way.
629*7c478bd9Sstevel@tonic-gate */
630*7c478bd9Sstevel@tonic-gate np = &kmem_info.free_root;
631*7c478bd9Sstevel@tonic-gate neighbor = *np;
632*7c478bd9Sstevel@tonic-gate while (neighbor != NIL) {
633*7c478bd9Sstevel@tonic-gate neigh_block = (char *)neighbor->block;
634*7c478bd9Sstevel@tonic-gate neigh_size = neighbor->size;
635*7c478bd9Sstevel@tonic-gate if ((char *)ptr < neigh_block) {
636*7c478bd9Sstevel@tonic-gate if ((char *)ptr + nbytes == neigh_block) {
637*7c478bd9Sstevel@tonic-gate /*
638*7c478bd9Sstevel@tonic-gate * Absorb and delete right neighbor
639*7c478bd9Sstevel@tonic-gate */
640*7c478bd9Sstevel@tonic-gate nbytes += neigh_size;
641*7c478bd9Sstevel@tonic-gate delete(np);
642*7c478bd9Sstevel@tonic-gate } else if ((char *)ptr + nbytes > neigh_block) {
643*7c478bd9Sstevel@tonic-gate /*
644*7c478bd9Sstevel@tonic-gate * The block being freed overlaps
645*7c478bd9Sstevel@tonic-gate * another block in the tree. This
646*7c478bd9Sstevel@tonic-gate * is bad news.
647*7c478bd9Sstevel@tonic-gate */
648*7c478bd9Sstevel@tonic-gate printf("kmem_free: free block overlap %p+%lx"
649*7c478bd9Sstevel@tonic-gate " over %p\n", (void *)ptr, nbytes,
650*7c478bd9Sstevel@tonic-gate (void *)neigh_block);
651*7c478bd9Sstevel@tonic-gate prom_panic("kmem_free: free block overlap");
652*7c478bd9Sstevel@tonic-gate } else {
653*7c478bd9Sstevel@tonic-gate /*
654*7c478bd9Sstevel@tonic-gate * Search to the left
655*7c478bd9Sstevel@tonic-gate */
656*7c478bd9Sstevel@tonic-gate np = &neighbor->left;
657*7c478bd9Sstevel@tonic-gate }
658*7c478bd9Sstevel@tonic-gate } else if ((char *)ptr > neigh_block) {
659*7c478bd9Sstevel@tonic-gate if (neigh_block + neigh_size == ptr) {
660*7c478bd9Sstevel@tonic-gate /*
661*7c478bd9Sstevel@tonic-gate * Absorb and delete left neighbor
662*7c478bd9Sstevel@tonic-gate */
663*7c478bd9Sstevel@tonic-gate ptr = neigh_block;
664*7c478bd9Sstevel@tonic-gate nbytes += neigh_size;
665*7c478bd9Sstevel@tonic-gate delete(np);
666*7c478bd9Sstevel@tonic-gate } else if (neigh_block + neigh_size > (char *)ptr) {
667*7c478bd9Sstevel@tonic-gate /*
668*7c478bd9Sstevel@tonic-gate * This block has already been freed
669*7c478bd9Sstevel@tonic-gate */
670*7c478bd9Sstevel@tonic-gate prom_panic("kmem_free block already free");
671*7c478bd9Sstevel@tonic-gate } else {
672*7c478bd9Sstevel@tonic-gate /*
673*7c478bd9Sstevel@tonic-gate * search to the right
674*7c478bd9Sstevel@tonic-gate */
675*7c478bd9Sstevel@tonic-gate np = &neighbor->right;
676*7c478bd9Sstevel@tonic-gate }
677*7c478bd9Sstevel@tonic-gate } else {
678*7c478bd9Sstevel@tonic-gate /*
679*7c478bd9Sstevel@tonic-gate * This block has already been freed
680*7c478bd9Sstevel@tonic-gate * as "ptr == neigh_block"
681*7c478bd9Sstevel@tonic-gate */
682*7c478bd9Sstevel@tonic-gate prom_panic("kmem_free: block already free as neighbor");
683*7c478bd9Sstevel@tonic-gate } /* else */
684*7c478bd9Sstevel@tonic-gate neighbor = *np;
685*7c478bd9Sstevel@tonic-gate } /* while */
686*7c478bd9Sstevel@tonic-gate
687*7c478bd9Sstevel@tonic-gate /*
688*7c478bd9Sstevel@tonic-gate * Insert the new node into the free space tree
689*7c478bd9Sstevel@tonic-gate */
690*7c478bd9Sstevel@tonic-gate insert((Dblk) ptr, nbytes, &kmem_info.free_root);
691*7c478bd9Sstevel@tonic-gate #ifdef DEBUG
692*7c478bd9Sstevel@tonic-gate printf("exiting kmem_free\n");
693*7c478bd9Sstevel@tonic-gate prtree(kmem_info.free_root, "kmem_free");
694*7c478bd9Sstevel@tonic-gate #endif
695*7c478bd9Sstevel@tonic-gate splx(s);
696*7c478bd9Sstevel@tonic-gate } /* kmem_free */
697*7c478bd9Sstevel@tonic-gate
698*7c478bd9Sstevel@tonic-gate /*
699*7c478bd9Sstevel@tonic-gate * Sigh. We include a header file which the kernel
700*7c478bd9Sstevel@tonic-gate * uses to declare (one of its many) kmem_free prototypes.
701*7c478bd9Sstevel@tonic-gate * In order not to use the kernel's namespace, then, we must
702*7c478bd9Sstevel@tonic-gate * define another name here for use by boot.
703*7c478bd9Sstevel@tonic-gate */
704*7c478bd9Sstevel@tonic-gate void *
bkmem_alloc(size_t size)705*7c478bd9Sstevel@tonic-gate bkmem_alloc(size_t size)
706*7c478bd9Sstevel@tonic-gate {
707*7c478bd9Sstevel@tonic-gate return (kmem_alloc(size, 0));
708*7c478bd9Sstevel@tonic-gate }
709*7c478bd9Sstevel@tonic-gate
710*7c478bd9Sstevel@tonic-gate /*
711*7c478bd9Sstevel@tonic-gate * Boot's kmem_alloc is really kmem_zalloc().
712*7c478bd9Sstevel@tonic-gate */
713*7c478bd9Sstevel@tonic-gate void *
bkmem_zalloc(size_t size)714*7c478bd9Sstevel@tonic-gate bkmem_zalloc(size_t size)
715*7c478bd9Sstevel@tonic-gate {
716*7c478bd9Sstevel@tonic-gate return (kmem_alloc(size, 0));
717*7c478bd9Sstevel@tonic-gate }
718*7c478bd9Sstevel@tonic-gate
719*7c478bd9Sstevel@tonic-gate void
bkmem_free(void * p,size_t bytes)720*7c478bd9Sstevel@tonic-gate bkmem_free(void *p, size_t bytes)
721*7c478bd9Sstevel@tonic-gate {
722*7c478bd9Sstevel@tonic-gate kmem_free(p, bytes);
723*7c478bd9Sstevel@tonic-gate }
724*7c478bd9Sstevel@tonic-gate
725*7c478bd9Sstevel@tonic-gate static void
check_need_to_free(void)726*7c478bd9Sstevel@tonic-gate check_need_to_free(void)
727*7c478bd9Sstevel@tonic-gate {
728*7c478bd9Sstevel@tonic-gate int i;
729*7c478bd9Sstevel@tonic-gate struct need_to_free *ntf;
730*7c478bd9Sstevel@tonic-gate caddr_t addr;
731*7c478bd9Sstevel@tonic-gate size_t nbytes;
732*7c478bd9Sstevel@tonic-gate int s;
733*7c478bd9Sstevel@tonic-gate
734*7c478bd9Sstevel@tonic-gate again:
735*7c478bd9Sstevel@tonic-gate s = splimp();
736*7c478bd9Sstevel@tonic-gate ntf = &kmem_info.need_to_free_list;
737*7c478bd9Sstevel@tonic-gate if (ntf->addr) {
738*7c478bd9Sstevel@tonic-gate addr = ntf->addr;
739*7c478bd9Sstevel@tonic-gate nbytes = ntf->nbytes;
740*7c478bd9Sstevel@tonic-gate *ntf = *(struct need_to_free *)ntf->addr;
741*7c478bd9Sstevel@tonic-gate splx(s);
742*7c478bd9Sstevel@tonic-gate kmem_free(addr, nbytes);
743*7c478bd9Sstevel@tonic-gate goto again;
744*7c478bd9Sstevel@tonic-gate }
745*7c478bd9Sstevel@tonic-gate ntf = kmem_info.need_to_free;
746*7c478bd9Sstevel@tonic-gate for (i = 0; i < NEED_TO_FREE_SIZE; i++) {
747*7c478bd9Sstevel@tonic-gate if (ntf[i].addr) {
748*7c478bd9Sstevel@tonic-gate addr = ntf[i].addr;
749*7c478bd9Sstevel@tonic-gate nbytes = ntf[i].nbytes;
750*7c478bd9Sstevel@tonic-gate ntf[i].addr = 0;
751*7c478bd9Sstevel@tonic-gate splx(s);
752*7c478bd9Sstevel@tonic-gate kmem_free(addr, nbytes);
753*7c478bd9Sstevel@tonic-gate goto again;
754*7c478bd9Sstevel@tonic-gate }
755*7c478bd9Sstevel@tonic-gate }
756*7c478bd9Sstevel@tonic-gate splx(s);
757*7c478bd9Sstevel@tonic-gate }
758*7c478bd9Sstevel@tonic-gate
759*7c478bd9Sstevel@tonic-gate /*
760*7c478bd9Sstevel@tonic-gate * Add a block of at least nbytes to the free space tree.
761*7c478bd9Sstevel@tonic-gate *
762*7c478bd9Sstevel@tonic-gate * return value:
763*7c478bd9Sstevel@tonic-gate * true if at least nbytes can be allocated
764*7c478bd9Sstevel@tonic-gate * false otherwise
765*7c478bd9Sstevel@tonic-gate *
766*7c478bd9Sstevel@tonic-gate * remark:
767*7c478bd9Sstevel@tonic-gate * free space (delimited by the static variable ubound) is
768*7c478bd9Sstevel@tonic-gate * extended by an amount determined by rounding nbytes up to
769*7c478bd9Sstevel@tonic-gate * a multiple of the system page size.
770*7c478bd9Sstevel@tonic-gate */
771*7c478bd9Sstevel@tonic-gate
772*7c478bd9Sstevel@tonic-gate static bool
morecore(size_t nbytes)773*7c478bd9Sstevel@tonic-gate morecore(size_t nbytes)
774*7c478bd9Sstevel@tonic-gate {
775*7c478bd9Sstevel@tonic-gate #ifdef __sparc
776*7c478bd9Sstevel@tonic-gate enum RESOURCES type = RES_BOOTSCRATCH_NOFAIL;
777*7c478bd9Sstevel@tonic-gate #else
778*7c478bd9Sstevel@tonic-gate enum RESOURCES type = RES_BOOTSCRATCH;
779*7c478bd9Sstevel@tonic-gate #endif
780*7c478bd9Sstevel@tonic-gate Dblk p;
781*7c478bd9Sstevel@tonic-gate #ifdef DEBUG
782*7c478bd9Sstevel@tonic-gate printf("morecore(nbytes 0x%lx)\n", nbytes);
783*7c478bd9Sstevel@tonic-gate #endif /* DEBUG */
784*7c478bd9Sstevel@tonic-gate
785*7c478bd9Sstevel@tonic-gate
786*7c478bd9Sstevel@tonic-gate nbytes = roundup(nbytes, PAGESIZE);
787*7c478bd9Sstevel@tonic-gate p = (Dblk) resalloc(type, nbytes, (caddr_t)0, 0);
788*7c478bd9Sstevel@tonic-gate if (p == 0) {
789*7c478bd9Sstevel@tonic-gate return (false);
790*7c478bd9Sstevel@tonic-gate }
791*7c478bd9Sstevel@tonic-gate kmem_free((caddr_t)p, nbytes);
792*7c478bd9Sstevel@tonic-gate #ifdef DEBUG
793*7c478bd9Sstevel@tonic-gate printf("morecore() returing, p = %p\n", p);
794*7c478bd9Sstevel@tonic-gate #endif
795*7c478bd9Sstevel@tonic-gate return (true);
796*7c478bd9Sstevel@tonic-gate
797*7c478bd9Sstevel@tonic-gate } /* morecore */
798*7c478bd9Sstevel@tonic-gate
799*7c478bd9Sstevel@tonic-gate /*
800*7c478bd9Sstevel@tonic-gate * Get a free block header
801*7c478bd9Sstevel@tonic-gate * There is a list of available free block headers.
802*7c478bd9Sstevel@tonic-gate * When the list is empty, allocate another pagefull.
803*7c478bd9Sstevel@tonic-gate */
804*7c478bd9Sstevel@tonic-gate Freehdr
getfreehdr(void)805*7c478bd9Sstevel@tonic-gate getfreehdr(void)
806*7c478bd9Sstevel@tonic-gate {
807*7c478bd9Sstevel@tonic-gate Freehdr r;
808*7c478bd9Sstevel@tonic-gate int n = 0;
809*7c478bd9Sstevel@tonic-gate #ifdef DEBUG
810*7c478bd9Sstevel@tonic-gate printf("getfreehdr()\n");
811*7c478bd9Sstevel@tonic-gate #endif /* DEBUG */
812*7c478bd9Sstevel@tonic-gate
813*7c478bd9Sstevel@tonic-gate if (kmem_info.free_hdr_list != NIL) {
814*7c478bd9Sstevel@tonic-gate r = kmem_info.free_hdr_list;
815*7c478bd9Sstevel@tonic-gate kmem_info.free_hdr_list = kmem_info.free_hdr_list->left;
816*7c478bd9Sstevel@tonic-gate } else {
817*7c478bd9Sstevel@tonic-gate r = (Freehdr)resalloc(RES_BOOTSCRATCH, PAGESIZE, (caddr_t)0, 0);
818*7c478bd9Sstevel@tonic-gate if (r == 0) {
819*7c478bd9Sstevel@tonic-gate prom_panic("getfreehdr");
820*7c478bd9Sstevel@tonic-gate }
821*7c478bd9Sstevel@tonic-gate for (n = 1; n < PAGESIZE / sizeof (*r); n++) {
822*7c478bd9Sstevel@tonic-gate freehdr(&r[n]);
823*7c478bd9Sstevel@tonic-gate }
824*7c478bd9Sstevel@tonic-gate }
825*7c478bd9Sstevel@tonic-gate #ifdef DEBUG
826*7c478bd9Sstevel@tonic-gate printf("getfreehdr: freed %x headers\n", n);
827*7c478bd9Sstevel@tonic-gate printf("getfreehdr: returning %p\n", r);
828*7c478bd9Sstevel@tonic-gate #endif /* DEBUG */
829*7c478bd9Sstevel@tonic-gate return (r);
830*7c478bd9Sstevel@tonic-gate }
831*7c478bd9Sstevel@tonic-gate
832*7c478bd9Sstevel@tonic-gate /*
833*7c478bd9Sstevel@tonic-gate * Free a free block header
834*7c478bd9Sstevel@tonic-gate * Add it to the list of available headers.
835*7c478bd9Sstevel@tonic-gate */
836*7c478bd9Sstevel@tonic-gate
837*7c478bd9Sstevel@tonic-gate void
freehdr(Freehdr p)838*7c478bd9Sstevel@tonic-gate freehdr(Freehdr p)
839*7c478bd9Sstevel@tonic-gate {
840*7c478bd9Sstevel@tonic-gate #ifdef DEBUG
841*7c478bd9Sstevel@tonic-gate printf("freehdr(%p)\n", p);
842*7c478bd9Sstevel@tonic-gate #endif /* DEBUG */
843*7c478bd9Sstevel@tonic-gate p->left = kmem_info.free_hdr_list;
844*7c478bd9Sstevel@tonic-gate p->right = NIL;
845*7c478bd9Sstevel@tonic-gate p->block = NULL;
846*7c478bd9Sstevel@tonic-gate kmem_info.free_hdr_list = p;
847*7c478bd9Sstevel@tonic-gate }
848*7c478bd9Sstevel@tonic-gate
849*7c478bd9Sstevel@tonic-gate #ifdef DEBUG
850*7c478bd9Sstevel@tonic-gate /*
851*7c478bd9Sstevel@tonic-gate * Diagnostic routines
852*7c478bd9Sstevel@tonic-gate */
853*7c478bd9Sstevel@tonic-gate static int depth = 0;
854*7c478bd9Sstevel@tonic-gate
855*7c478bd9Sstevel@tonic-gate static void
prtree(Freehdr p,char * cp)856*7c478bd9Sstevel@tonic-gate prtree(Freehdr p, char *cp)
857*7c478bd9Sstevel@tonic-gate {
858*7c478bd9Sstevel@tonic-gate int n;
859*7c478bd9Sstevel@tonic-gate if (depth == 0) {
860*7c478bd9Sstevel@tonic-gate printf("prtree(p %p cp %s)\n", p, cp);
861*7c478bd9Sstevel@tonic-gate }
862*7c478bd9Sstevel@tonic-gate if (p != NIL) {
863*7c478bd9Sstevel@tonic-gate depth++;
864*7c478bd9Sstevel@tonic-gate prtree(p->left, (char *)NULL);
865*7c478bd9Sstevel@tonic-gate depth--;
866*7c478bd9Sstevel@tonic-gate
867*7c478bd9Sstevel@tonic-gate for (n = 0; n < depth; n++) {
868*7c478bd9Sstevel@tonic-gate printf(" ");
869*7c478bd9Sstevel@tonic-gate }
870*7c478bd9Sstevel@tonic-gate printf(
871*7c478bd9Sstevel@tonic-gate "(%p): (left = %p, right = %p, block = %p, size = %lx)\n",
872*7c478bd9Sstevel@tonic-gate p, p->left, p->right, p->block, p->size);
873*7c478bd9Sstevel@tonic-gate
874*7c478bd9Sstevel@tonic-gate depth++;
875*7c478bd9Sstevel@tonic-gate prtree(p->right, (char *)NULL);
876*7c478bd9Sstevel@tonic-gate depth--;
877*7c478bd9Sstevel@tonic-gate }
878*7c478bd9Sstevel@tonic-gate }
879*7c478bd9Sstevel@tonic-gate #endif /* DEBUG */
880