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 1999-2002 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 /*
28*7c478bd9Sstevel@tonic-gate * s1394_addr.c
29*7c478bd9Sstevel@tonic-gate * 1394 Address Space Routines
30*7c478bd9Sstevel@tonic-gate * Implements all the routines necessary for alloc/free and lookup
31*7c478bd9Sstevel@tonic-gate * of the 1394 address space
32*7c478bd9Sstevel@tonic-gate */
33*7c478bd9Sstevel@tonic-gate
34*7c478bd9Sstevel@tonic-gate #include <sys/conf.h>
35*7c478bd9Sstevel@tonic-gate #include <sys/ddi.h>
36*7c478bd9Sstevel@tonic-gate #include <sys/sunddi.h>
37*7c478bd9Sstevel@tonic-gate #include <sys/types.h>
38*7c478bd9Sstevel@tonic-gate #include <sys/kmem.h>
39*7c478bd9Sstevel@tonic-gate #include <sys/1394/t1394.h>
40*7c478bd9Sstevel@tonic-gate #include <sys/1394/s1394.h>
41*7c478bd9Sstevel@tonic-gate #include <sys/1394/h1394.h>
42*7c478bd9Sstevel@tonic-gate #include <sys/1394/ieee1394.h>
43*7c478bd9Sstevel@tonic-gate
44*7c478bd9Sstevel@tonic-gate static s1394_addr_space_blk_t *s1394_free_list_search(s1394_hal_t *hal,
45*7c478bd9Sstevel@tonic-gate uint64_t addr);
46*7c478bd9Sstevel@tonic-gate
47*7c478bd9Sstevel@tonic-gate static s1394_addr_space_blk_t *s1394_free_list_find(s1394_hal_t *hal,
48*7c478bd9Sstevel@tonic-gate uint32_t type, uint32_t length);
49*7c478bd9Sstevel@tonic-gate
50*7c478bd9Sstevel@tonic-gate static s1394_addr_space_blk_t *s1394_free_list_delete(s1394_hal_t *hal,
51*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *del_blk);
52*7c478bd9Sstevel@tonic-gate
53*7c478bd9Sstevel@tonic-gate static void s1394_used_tree_insert(s1394_hal_t *hal, s1394_addr_space_blk_t *x);
54*7c478bd9Sstevel@tonic-gate
55*7c478bd9Sstevel@tonic-gate static void s1394_tree_insert(s1394_addr_space_blk_t **root,
56*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *z);
57*7c478bd9Sstevel@tonic-gate
58*7c478bd9Sstevel@tonic-gate static s1394_addr_space_blk_t *s1394_tree_search(s1394_addr_space_blk_t *x,
59*7c478bd9Sstevel@tonic-gate uint64_t address);
60*7c478bd9Sstevel@tonic-gate
61*7c478bd9Sstevel@tonic-gate static void s1394_used_tree_delete_fixup(s1394_addr_space_blk_t **root,
62*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *p, s1394_addr_space_blk_t *x,
63*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *w, int side_of_x);
64*7c478bd9Sstevel@tonic-gate
65*7c478bd9Sstevel@tonic-gate static void s1394_left_rotate(s1394_addr_space_blk_t **root,
66*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *x);
67*7c478bd9Sstevel@tonic-gate
68*7c478bd9Sstevel@tonic-gate static void s1394_right_rotate(s1394_addr_space_blk_t **root,
69*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *x);
70*7c478bd9Sstevel@tonic-gate
71*7c478bd9Sstevel@tonic-gate static s1394_addr_space_blk_t *s1394_tree_minimum(s1394_addr_space_blk_t *x);
72*7c478bd9Sstevel@tonic-gate
73*7c478bd9Sstevel@tonic-gate static s1394_addr_space_blk_t *s1394_tree_successor(s1394_addr_space_blk_t *x);
74*7c478bd9Sstevel@tonic-gate
75*7c478bd9Sstevel@tonic-gate /*
76*7c478bd9Sstevel@tonic-gate * s1394_request_addr_blk()
77*7c478bd9Sstevel@tonic-gate * is called when a target driver is requesting a block of 1394 Address
78*7c478bd9Sstevel@tonic-gate * Space of a particular type without regard for its exact location. It
79*7c478bd9Sstevel@tonic-gate * searches the free list for a block that's big enough and of the specified
80*7c478bd9Sstevel@tonic-gate * type, and it inserts it into the used tree.
81*7c478bd9Sstevel@tonic-gate */
82*7c478bd9Sstevel@tonic-gate int
s1394_request_addr_blk(s1394_hal_t * hal,t1394_alloc_addr_t * addr_allocp)83*7c478bd9Sstevel@tonic-gate s1394_request_addr_blk(s1394_hal_t *hal, t1394_alloc_addr_t *addr_allocp)
84*7c478bd9Sstevel@tonic-gate {
85*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *curr_blk;
86*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *new_blk;
87*7c478bd9Sstevel@tonic-gate uint64_t amount_free;
88*7c478bd9Sstevel@tonic-gate
89*7c478bd9Sstevel@tonic-gate ASSERT(hal != NULL);
90*7c478bd9Sstevel@tonic-gate
91*7c478bd9Sstevel@tonic-gate /* Lock the address space "free" list */
92*7c478bd9Sstevel@tonic-gate mutex_enter(&hal->addr_space_free_mutex);
93*7c478bd9Sstevel@tonic-gate
94*7c478bd9Sstevel@tonic-gate curr_blk = s1394_free_list_find(hal, addr_allocp->aa_type,
95*7c478bd9Sstevel@tonic-gate addr_allocp->aa_length);
96*7c478bd9Sstevel@tonic-gate if (curr_blk == NULL) {
97*7c478bd9Sstevel@tonic-gate /* Unlock the address space "free" list */
98*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
99*7c478bd9Sstevel@tonic-gate
100*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
101*7c478bd9Sstevel@tonic-gate }
102*7c478bd9Sstevel@tonic-gate
103*7c478bd9Sstevel@tonic-gate amount_free = (curr_blk->addr_hi - curr_blk->addr_lo) + 1;
104*7c478bd9Sstevel@tonic-gate /* Does it fit exact? */
105*7c478bd9Sstevel@tonic-gate if (amount_free == addr_allocp->aa_length) {
106*7c478bd9Sstevel@tonic-gate /* Take it out of the "free" list */
107*7c478bd9Sstevel@tonic-gate curr_blk = s1394_free_list_delete(hal, curr_blk);
108*7c478bd9Sstevel@tonic-gate
109*7c478bd9Sstevel@tonic-gate /* Unlock the address space "free" list */
110*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
111*7c478bd9Sstevel@tonic-gate
112*7c478bd9Sstevel@tonic-gate curr_blk->addr_enable = addr_allocp->aa_enable;
113*7c478bd9Sstevel@tonic-gate curr_blk->kmem_bufp = addr_allocp->aa_kmem_bufp;
114*7c478bd9Sstevel@tonic-gate curr_blk->addr_arg = addr_allocp->aa_arg;
115*7c478bd9Sstevel@tonic-gate curr_blk->addr_events = addr_allocp->aa_evts;
116*7c478bd9Sstevel@tonic-gate
117*7c478bd9Sstevel@tonic-gate addr_allocp->aa_address = curr_blk->addr_lo;
118*7c478bd9Sstevel@tonic-gate addr_allocp->aa_hdl = (t1394_addr_handle_t)curr_blk;
119*7c478bd9Sstevel@tonic-gate
120*7c478bd9Sstevel@tonic-gate /* Put it into the "used" tree */
121*7c478bd9Sstevel@tonic-gate s1394_used_tree_insert(hal, curr_blk);
122*7c478bd9Sstevel@tonic-gate
123*7c478bd9Sstevel@tonic-gate s1394_addr_alloc_kstat(hal, addr_allocp->aa_address);
124*7c478bd9Sstevel@tonic-gate
125*7c478bd9Sstevel@tonic-gate return (DDI_SUCCESS);
126*7c478bd9Sstevel@tonic-gate
127*7c478bd9Sstevel@tonic-gate } else {
128*7c478bd9Sstevel@tonic-gate /* Needs to be broken up */
129*7c478bd9Sstevel@tonic-gate new_blk = (s1394_addr_space_blk_t *)
130*7c478bd9Sstevel@tonic-gate kmem_zalloc(sizeof (s1394_addr_space_blk_t), KM_NOSLEEP);
131*7c478bd9Sstevel@tonic-gate if (new_blk == NULL) {
132*7c478bd9Sstevel@tonic-gate /* Unlock the address space "free" list */
133*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
134*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
135*7c478bd9Sstevel@tonic-gate }
136*7c478bd9Sstevel@tonic-gate
137*7c478bd9Sstevel@tonic-gate new_blk->addr_lo = curr_blk->addr_lo;
138*7c478bd9Sstevel@tonic-gate new_blk->addr_hi = curr_blk->addr_lo +
139*7c478bd9Sstevel@tonic-gate (addr_allocp->aa_length - 1);
140*7c478bd9Sstevel@tonic-gate new_blk->addr_type = curr_blk->addr_type;
141*7c478bd9Sstevel@tonic-gate new_blk->addr_enable = addr_allocp->aa_enable;
142*7c478bd9Sstevel@tonic-gate new_blk->kmem_bufp = addr_allocp->aa_kmem_bufp;
143*7c478bd9Sstevel@tonic-gate new_blk->addr_arg = addr_allocp->aa_arg;
144*7c478bd9Sstevel@tonic-gate new_blk->addr_events = addr_allocp->aa_evts;
145*7c478bd9Sstevel@tonic-gate
146*7c478bd9Sstevel@tonic-gate curr_blk->addr_lo = new_blk->addr_hi + 1;
147*7c478bd9Sstevel@tonic-gate
148*7c478bd9Sstevel@tonic-gate addr_allocp->aa_address = new_blk->addr_lo;
149*7c478bd9Sstevel@tonic-gate addr_allocp->aa_hdl = (t1394_addr_handle_t)new_blk;
150*7c478bd9Sstevel@tonic-gate
151*7c478bd9Sstevel@tonic-gate /* Unlock the address space "free" list */
152*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
153*7c478bd9Sstevel@tonic-gate
154*7c478bd9Sstevel@tonic-gate /* Put it into the "used" tree */
155*7c478bd9Sstevel@tonic-gate s1394_used_tree_insert(hal, new_blk);
156*7c478bd9Sstevel@tonic-gate
157*7c478bd9Sstevel@tonic-gate s1394_addr_alloc_kstat(hal, addr_allocp->aa_address);
158*7c478bd9Sstevel@tonic-gate
159*7c478bd9Sstevel@tonic-gate return (DDI_SUCCESS);
160*7c478bd9Sstevel@tonic-gate }
161*7c478bd9Sstevel@tonic-gate }
162*7c478bd9Sstevel@tonic-gate
163*7c478bd9Sstevel@tonic-gate /*
164*7c478bd9Sstevel@tonic-gate * s1394_claim_addr_blk()
165*7c478bd9Sstevel@tonic-gate * is called when a target driver is requesting a block of 1394 Address
166*7c478bd9Sstevel@tonic-gate * Space with a specific address. If the block containing that address
167*7c478bd9Sstevel@tonic-gate * is not in the free list, or if the block is too small, then
168*7c478bd9Sstevel@tonic-gate * s1394_claim_addr_blk() returns failure. If the block is found,
169*7c478bd9Sstevel@tonic-gate * however, it is inserted into the used tree.
170*7c478bd9Sstevel@tonic-gate */
171*7c478bd9Sstevel@tonic-gate int
s1394_claim_addr_blk(s1394_hal_t * hal,t1394_alloc_addr_t * addr_allocp)172*7c478bd9Sstevel@tonic-gate s1394_claim_addr_blk(s1394_hal_t *hal, t1394_alloc_addr_t *addr_allocp)
173*7c478bd9Sstevel@tonic-gate {
174*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *curr_blk;
175*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *new_blk;
176*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *middle_blk;
177*7c478bd9Sstevel@tonic-gate uint64_t upper_bound;
178*7c478bd9Sstevel@tonic-gate
179*7c478bd9Sstevel@tonic-gate ASSERT(hal != NULL);
180*7c478bd9Sstevel@tonic-gate
181*7c478bd9Sstevel@tonic-gate /* Lock the address space "free" list */
182*7c478bd9Sstevel@tonic-gate mutex_enter(&hal->addr_space_free_mutex);
183*7c478bd9Sstevel@tonic-gate
184*7c478bd9Sstevel@tonic-gate /* Find the block in the "free" list */
185*7c478bd9Sstevel@tonic-gate curr_blk = s1394_free_list_search(hal, addr_allocp->aa_address);
186*7c478bd9Sstevel@tonic-gate
187*7c478bd9Sstevel@tonic-gate /* If it wasn't found, it isn't free... */
188*7c478bd9Sstevel@tonic-gate if (curr_blk == NULL) {
189*7c478bd9Sstevel@tonic-gate /* Unlock the address space free list */
190*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
191*7c478bd9Sstevel@tonic-gate
192*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
193*7c478bd9Sstevel@tonic-gate }
194*7c478bd9Sstevel@tonic-gate
195*7c478bd9Sstevel@tonic-gate /* Does the request fit in the block? */
196*7c478bd9Sstevel@tonic-gate upper_bound = (addr_allocp->aa_address + addr_allocp->aa_length) - 1;
197*7c478bd9Sstevel@tonic-gate if ((upper_bound >= curr_blk->addr_lo) &&
198*7c478bd9Sstevel@tonic-gate (upper_bound <= curr_blk->addr_hi)) {
199*7c478bd9Sstevel@tonic-gate
200*7c478bd9Sstevel@tonic-gate /* How does the requested range fit in the current range? */
201*7c478bd9Sstevel@tonic-gate if (addr_allocp->aa_address == curr_blk->addr_lo) {
202*7c478bd9Sstevel@tonic-gate if (upper_bound == curr_blk->addr_hi) {
203*7c478bd9Sstevel@tonic-gate /* Exact fit */
204*7c478bd9Sstevel@tonic-gate
205*7c478bd9Sstevel@tonic-gate /* Take it out of the "free" list */
206*7c478bd9Sstevel@tonic-gate curr_blk = s1394_free_list_delete(hal,
207*7c478bd9Sstevel@tonic-gate curr_blk);
208*7c478bd9Sstevel@tonic-gate
209*7c478bd9Sstevel@tonic-gate /* Unlock the address space "free" list */
210*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
211*7c478bd9Sstevel@tonic-gate
212*7c478bd9Sstevel@tonic-gate curr_blk->addr_enable = addr_allocp->aa_enable;
213*7c478bd9Sstevel@tonic-gate curr_blk->kmem_bufp = addr_allocp->aa_kmem_bufp;
214*7c478bd9Sstevel@tonic-gate curr_blk->addr_arg = addr_allocp->aa_arg;
215*7c478bd9Sstevel@tonic-gate curr_blk->addr_events = addr_allocp->aa_evts;
216*7c478bd9Sstevel@tonic-gate
217*7c478bd9Sstevel@tonic-gate addr_allocp->aa_hdl =
218*7c478bd9Sstevel@tonic-gate (t1394_addr_handle_t)curr_blk;
219*7c478bd9Sstevel@tonic-gate
220*7c478bd9Sstevel@tonic-gate /* Put it into the "used" tree */
221*7c478bd9Sstevel@tonic-gate s1394_used_tree_insert(hal, curr_blk);
222*7c478bd9Sstevel@tonic-gate
223*7c478bd9Sstevel@tonic-gate s1394_addr_alloc_kstat(hal,
224*7c478bd9Sstevel@tonic-gate addr_allocp->aa_address);
225*7c478bd9Sstevel@tonic-gate
226*7c478bd9Sstevel@tonic-gate return (DDI_SUCCESS);
227*7c478bd9Sstevel@tonic-gate
228*7c478bd9Sstevel@tonic-gate } else {
229*7c478bd9Sstevel@tonic-gate /* If space is reserved, must claim it all */
230*7c478bd9Sstevel@tonic-gate if (curr_blk->addr_reserved == ADDR_RESERVED) {
231*7c478bd9Sstevel@tonic-gate goto claim_error;
232*7c478bd9Sstevel@tonic-gate }
233*7c478bd9Sstevel@tonic-gate
234*7c478bd9Sstevel@tonic-gate /* Front part of range */
235*7c478bd9Sstevel@tonic-gate new_blk = (s1394_addr_space_blk_t *)
236*7c478bd9Sstevel@tonic-gate kmem_zalloc(sizeof (s1394_addr_space_blk_t),
237*7c478bd9Sstevel@tonic-gate KM_NOSLEEP);
238*7c478bd9Sstevel@tonic-gate if (new_blk == NULL) {
239*7c478bd9Sstevel@tonic-gate /* Unlock the addr space "free" list */
240*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
241*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
242*7c478bd9Sstevel@tonic-gate }
243*7c478bd9Sstevel@tonic-gate
244*7c478bd9Sstevel@tonic-gate new_blk->addr_lo = curr_blk->addr_lo;
245*7c478bd9Sstevel@tonic-gate new_blk->addr_hi = upper_bound;
246*7c478bd9Sstevel@tonic-gate new_blk->addr_type = curr_blk->addr_type;
247*7c478bd9Sstevel@tonic-gate new_blk->addr_enable = addr_allocp->aa_enable;
248*7c478bd9Sstevel@tonic-gate new_blk->kmem_bufp = addr_allocp->aa_kmem_bufp;
249*7c478bd9Sstevel@tonic-gate new_blk->addr_arg = addr_allocp->aa_arg;
250*7c478bd9Sstevel@tonic-gate new_blk->addr_events = addr_allocp->aa_evts;
251*7c478bd9Sstevel@tonic-gate
252*7c478bd9Sstevel@tonic-gate curr_blk->addr_lo = new_blk->addr_hi + 1;
253*7c478bd9Sstevel@tonic-gate
254*7c478bd9Sstevel@tonic-gate addr_allocp->aa_hdl =
255*7c478bd9Sstevel@tonic-gate (t1394_addr_handle_t)new_blk;
256*7c478bd9Sstevel@tonic-gate
257*7c478bd9Sstevel@tonic-gate /* Unlock the address space free list */
258*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
259*7c478bd9Sstevel@tonic-gate
260*7c478bd9Sstevel@tonic-gate /* Put it into the "used" tree */
261*7c478bd9Sstevel@tonic-gate s1394_used_tree_insert(hal, new_blk);
262*7c478bd9Sstevel@tonic-gate
263*7c478bd9Sstevel@tonic-gate s1394_addr_alloc_kstat(hal,
264*7c478bd9Sstevel@tonic-gate addr_allocp->aa_address);
265*7c478bd9Sstevel@tonic-gate
266*7c478bd9Sstevel@tonic-gate return (DDI_SUCCESS);
267*7c478bd9Sstevel@tonic-gate }
268*7c478bd9Sstevel@tonic-gate
269*7c478bd9Sstevel@tonic-gate } else {
270*7c478bd9Sstevel@tonic-gate if (upper_bound == curr_blk->addr_hi) {
271*7c478bd9Sstevel@tonic-gate /* If space is reserved, must claim it all */
272*7c478bd9Sstevel@tonic-gate if (curr_blk->addr_reserved == ADDR_RESERVED) {
273*7c478bd9Sstevel@tonic-gate goto claim_error;
274*7c478bd9Sstevel@tonic-gate }
275*7c478bd9Sstevel@tonic-gate
276*7c478bd9Sstevel@tonic-gate /* End part of range */
277*7c478bd9Sstevel@tonic-gate new_blk = (s1394_addr_space_blk_t *)
278*7c478bd9Sstevel@tonic-gate kmem_zalloc(sizeof (s1394_addr_space_blk_t),
279*7c478bd9Sstevel@tonic-gate KM_NOSLEEP);
280*7c478bd9Sstevel@tonic-gate if (new_blk == NULL) {
281*7c478bd9Sstevel@tonic-gate /* Unlock the addr space "free" list */
282*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
283*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
284*7c478bd9Sstevel@tonic-gate }
285*7c478bd9Sstevel@tonic-gate
286*7c478bd9Sstevel@tonic-gate new_blk->addr_lo = addr_allocp->aa_address;
287*7c478bd9Sstevel@tonic-gate new_blk->addr_hi = upper_bound;
288*7c478bd9Sstevel@tonic-gate new_blk->addr_type = curr_blk->addr_type;
289*7c478bd9Sstevel@tonic-gate new_blk->addr_enable = addr_allocp->aa_enable;
290*7c478bd9Sstevel@tonic-gate new_blk->kmem_bufp = addr_allocp->aa_kmem_bufp;
291*7c478bd9Sstevel@tonic-gate new_blk->addr_arg = addr_allocp->aa_arg;
292*7c478bd9Sstevel@tonic-gate new_blk->addr_events = addr_allocp->aa_evts;
293*7c478bd9Sstevel@tonic-gate
294*7c478bd9Sstevel@tonic-gate curr_blk->addr_hi = addr_allocp->aa_address - 1;
295*7c478bd9Sstevel@tonic-gate
296*7c478bd9Sstevel@tonic-gate addr_allocp->aa_hdl =
297*7c478bd9Sstevel@tonic-gate (t1394_addr_handle_t)new_blk;
298*7c478bd9Sstevel@tonic-gate
299*7c478bd9Sstevel@tonic-gate /* Unlock the address space free list */
300*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
301*7c478bd9Sstevel@tonic-gate
302*7c478bd9Sstevel@tonic-gate /* Put it into the "used" tree */
303*7c478bd9Sstevel@tonic-gate s1394_used_tree_insert(hal, new_blk);
304*7c478bd9Sstevel@tonic-gate
305*7c478bd9Sstevel@tonic-gate s1394_addr_alloc_kstat(hal,
306*7c478bd9Sstevel@tonic-gate addr_allocp->aa_address);
307*7c478bd9Sstevel@tonic-gate
308*7c478bd9Sstevel@tonic-gate return (DDI_SUCCESS);
309*7c478bd9Sstevel@tonic-gate
310*7c478bd9Sstevel@tonic-gate } else {
311*7c478bd9Sstevel@tonic-gate /* If space is reserved, must claim it all */
312*7c478bd9Sstevel@tonic-gate if (curr_blk->addr_reserved == ADDR_RESERVED) {
313*7c478bd9Sstevel@tonic-gate goto claim_error;
314*7c478bd9Sstevel@tonic-gate }
315*7c478bd9Sstevel@tonic-gate
316*7c478bd9Sstevel@tonic-gate /* Middle part of range */
317*7c478bd9Sstevel@tonic-gate new_blk = (s1394_addr_space_blk_t *)
318*7c478bd9Sstevel@tonic-gate kmem_zalloc(sizeof (s1394_addr_space_blk_t),
319*7c478bd9Sstevel@tonic-gate KM_NOSLEEP);
320*7c478bd9Sstevel@tonic-gate if (new_blk == NULL) {
321*7c478bd9Sstevel@tonic-gate /* Unlock the addr space "free" list */
322*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
323*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
324*7c478bd9Sstevel@tonic-gate }
325*7c478bd9Sstevel@tonic-gate
326*7c478bd9Sstevel@tonic-gate middle_blk = (s1394_addr_space_blk_t *)
327*7c478bd9Sstevel@tonic-gate kmem_zalloc(sizeof (s1394_addr_space_blk_t),
328*7c478bd9Sstevel@tonic-gate KM_NOSLEEP);
329*7c478bd9Sstevel@tonic-gate if (middle_blk == NULL) {
330*7c478bd9Sstevel@tonic-gate /* Unlock the addr space "free" list */
331*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
332*7c478bd9Sstevel@tonic-gate kmem_free(new_blk,
333*7c478bd9Sstevel@tonic-gate sizeof (s1394_addr_space_blk_t));
334*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
335*7c478bd9Sstevel@tonic-gate }
336*7c478bd9Sstevel@tonic-gate
337*7c478bd9Sstevel@tonic-gate middle_blk->addr_lo = addr_allocp->aa_address;
338*7c478bd9Sstevel@tonic-gate middle_blk->addr_hi = upper_bound;
339*7c478bd9Sstevel@tonic-gate new_blk->addr_lo = upper_bound + 1;
340*7c478bd9Sstevel@tonic-gate new_blk->addr_hi = curr_blk->addr_hi;
341*7c478bd9Sstevel@tonic-gate
342*7c478bd9Sstevel@tonic-gate new_blk->addr_type = curr_blk->addr_type;
343*7c478bd9Sstevel@tonic-gate
344*7c478bd9Sstevel@tonic-gate middle_blk->addr_type = curr_blk->addr_type;
345*7c478bd9Sstevel@tonic-gate middle_blk->addr_enable =
346*7c478bd9Sstevel@tonic-gate addr_allocp->aa_enable;
347*7c478bd9Sstevel@tonic-gate middle_blk->kmem_bufp =
348*7c478bd9Sstevel@tonic-gate addr_allocp->aa_kmem_bufp;
349*7c478bd9Sstevel@tonic-gate middle_blk->addr_arg = addr_allocp->aa_arg;
350*7c478bd9Sstevel@tonic-gate middle_blk->addr_events = addr_allocp->aa_evts;
351*7c478bd9Sstevel@tonic-gate
352*7c478bd9Sstevel@tonic-gate curr_blk->addr_hi = addr_allocp->aa_address - 1;
353*7c478bd9Sstevel@tonic-gate
354*7c478bd9Sstevel@tonic-gate addr_allocp->aa_hdl =
355*7c478bd9Sstevel@tonic-gate (t1394_addr_handle_t)middle_blk;
356*7c478bd9Sstevel@tonic-gate
357*7c478bd9Sstevel@tonic-gate /* Put part back into the "free" tree */
358*7c478bd9Sstevel@tonic-gate s1394_free_list_insert(hal, new_blk);
359*7c478bd9Sstevel@tonic-gate
360*7c478bd9Sstevel@tonic-gate /* Unlock the address space free list */
361*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
362*7c478bd9Sstevel@tonic-gate
363*7c478bd9Sstevel@tonic-gate /* Put it into the "used" tree */
364*7c478bd9Sstevel@tonic-gate s1394_used_tree_insert(hal, middle_blk);
365*7c478bd9Sstevel@tonic-gate
366*7c478bd9Sstevel@tonic-gate s1394_addr_alloc_kstat(hal,
367*7c478bd9Sstevel@tonic-gate addr_allocp->aa_address);
368*7c478bd9Sstevel@tonic-gate
369*7c478bd9Sstevel@tonic-gate return (DDI_SUCCESS);
370*7c478bd9Sstevel@tonic-gate }
371*7c478bd9Sstevel@tonic-gate }
372*7c478bd9Sstevel@tonic-gate }
373*7c478bd9Sstevel@tonic-gate
374*7c478bd9Sstevel@tonic-gate claim_error:
375*7c478bd9Sstevel@tonic-gate /* Unlock the address space free list */
376*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
377*7c478bd9Sstevel@tonic-gate
378*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
379*7c478bd9Sstevel@tonic-gate }
380*7c478bd9Sstevel@tonic-gate
381*7c478bd9Sstevel@tonic-gate /*
382*7c478bd9Sstevel@tonic-gate * s1394_free_addr_blk()
383*7c478bd9Sstevel@tonic-gate * An opposite of s1394_claim_addr_blk(): takes the address block
384*7c478bd9Sstevel@tonic-gate * out of the "used" tree and puts it into the "free" tree.
385*7c478bd9Sstevel@tonic-gate */
386*7c478bd9Sstevel@tonic-gate int
s1394_free_addr_blk(s1394_hal_t * hal,s1394_addr_space_blk_t * blk)387*7c478bd9Sstevel@tonic-gate s1394_free_addr_blk(s1394_hal_t *hal, s1394_addr_space_blk_t *blk)
388*7c478bd9Sstevel@tonic-gate {
389*7c478bd9Sstevel@tonic-gate /* Lock the address space "free" list */
390*7c478bd9Sstevel@tonic-gate mutex_enter(&hal->addr_space_free_mutex);
391*7c478bd9Sstevel@tonic-gate
392*7c478bd9Sstevel@tonic-gate /* Take it out of the "used" tree */
393*7c478bd9Sstevel@tonic-gate blk = s1394_used_tree_delete(hal, blk);
394*7c478bd9Sstevel@tonic-gate
395*7c478bd9Sstevel@tonic-gate if (blk == NULL) {
396*7c478bd9Sstevel@tonic-gate /* Unlock the address space "free" list */
397*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
398*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
399*7c478bd9Sstevel@tonic-gate }
400*7c478bd9Sstevel@tonic-gate
401*7c478bd9Sstevel@tonic-gate /* Put it into the "free" tree */
402*7c478bd9Sstevel@tonic-gate s1394_free_list_insert(hal, blk);
403*7c478bd9Sstevel@tonic-gate
404*7c478bd9Sstevel@tonic-gate /* Unlock the address space "free" list */
405*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
406*7c478bd9Sstevel@tonic-gate
407*7c478bd9Sstevel@tonic-gate return (DDI_SUCCESS);
408*7c478bd9Sstevel@tonic-gate }
409*7c478bd9Sstevel@tonic-gate
410*7c478bd9Sstevel@tonic-gate /*
411*7c478bd9Sstevel@tonic-gate * s1394_reserve_addr_blk()
412*7c478bd9Sstevel@tonic-gate * is similar to s1394_claim_addr_blk(), with the difference being that
413*7c478bd9Sstevel@tonic-gate * after the address block is found, it is marked as "reserved" rather
414*7c478bd9Sstevel@tonic-gate * than inserted into the used tree. Blocks of data that are marked
415*7c478bd9Sstevel@tonic-gate * "reserved" cannot be unintentionally allocated by a target, they must
416*7c478bd9Sstevel@tonic-gate * be specifically requested by specifying the exact address and size of
417*7c478bd9Sstevel@tonic-gate * the "reserved" block.
418*7c478bd9Sstevel@tonic-gate */
419*7c478bd9Sstevel@tonic-gate int
s1394_reserve_addr_blk(s1394_hal_t * hal,t1394_alloc_addr_t * addr_allocp)420*7c478bd9Sstevel@tonic-gate s1394_reserve_addr_blk(s1394_hal_t *hal, t1394_alloc_addr_t *addr_allocp)
421*7c478bd9Sstevel@tonic-gate {
422*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *curr_blk;
423*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *new_blk;
424*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *middle_blk;
425*7c478bd9Sstevel@tonic-gate uint64_t upper_bound;
426*7c478bd9Sstevel@tonic-gate
427*7c478bd9Sstevel@tonic-gate ASSERT(hal != NULL);
428*7c478bd9Sstevel@tonic-gate
429*7c478bd9Sstevel@tonic-gate /* Lock the address space "free" list */
430*7c478bd9Sstevel@tonic-gate mutex_enter(&hal->addr_space_free_mutex);
431*7c478bd9Sstevel@tonic-gate
432*7c478bd9Sstevel@tonic-gate /* Find the block in the "free" list */
433*7c478bd9Sstevel@tonic-gate curr_blk = s1394_free_list_search(hal, addr_allocp->aa_address);
434*7c478bd9Sstevel@tonic-gate /* If it wasn't found, it isn't free... */
435*7c478bd9Sstevel@tonic-gate if (curr_blk == NULL) {
436*7c478bd9Sstevel@tonic-gate /* Unlock the address space free list */
437*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
438*7c478bd9Sstevel@tonic-gate
439*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
440*7c478bd9Sstevel@tonic-gate }
441*7c478bd9Sstevel@tonic-gate
442*7c478bd9Sstevel@tonic-gate /* Is this block already reserved? */
443*7c478bd9Sstevel@tonic-gate if (curr_blk->addr_reserved == ADDR_RESERVED) {
444*7c478bd9Sstevel@tonic-gate /* Unlock the address space free list */
445*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
446*7c478bd9Sstevel@tonic-gate
447*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
448*7c478bd9Sstevel@tonic-gate }
449*7c478bd9Sstevel@tonic-gate
450*7c478bd9Sstevel@tonic-gate /* Does the request fit in the block? */
451*7c478bd9Sstevel@tonic-gate upper_bound = (addr_allocp->aa_address + addr_allocp->aa_length) - 1;
452*7c478bd9Sstevel@tonic-gate if ((upper_bound >= curr_blk->addr_lo) &&
453*7c478bd9Sstevel@tonic-gate (upper_bound <= curr_blk->addr_hi)) {
454*7c478bd9Sstevel@tonic-gate
455*7c478bd9Sstevel@tonic-gate /* How does the requested range fit in the current range? */
456*7c478bd9Sstevel@tonic-gate if (addr_allocp->aa_address == curr_blk->addr_lo) {
457*7c478bd9Sstevel@tonic-gate if (upper_bound == curr_blk->addr_hi) {
458*7c478bd9Sstevel@tonic-gate /* Exact fit */
459*7c478bd9Sstevel@tonic-gate curr_blk->addr_reserved = ADDR_RESERVED;
460*7c478bd9Sstevel@tonic-gate
461*7c478bd9Sstevel@tonic-gate /* Unlock the address space "free" list */
462*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
463*7c478bd9Sstevel@tonic-gate
464*7c478bd9Sstevel@tonic-gate return (DDI_SUCCESS);
465*7c478bd9Sstevel@tonic-gate
466*7c478bd9Sstevel@tonic-gate } else {
467*7c478bd9Sstevel@tonic-gate /* Front part of range */
468*7c478bd9Sstevel@tonic-gate new_blk = (s1394_addr_space_blk_t *)
469*7c478bd9Sstevel@tonic-gate kmem_zalloc(sizeof (s1394_addr_space_blk_t),
470*7c478bd9Sstevel@tonic-gate KM_NOSLEEP);
471*7c478bd9Sstevel@tonic-gate if (new_blk == NULL) {
472*7c478bd9Sstevel@tonic-gate /* Unlock the addr space "free" list */
473*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
474*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
475*7c478bd9Sstevel@tonic-gate }
476*7c478bd9Sstevel@tonic-gate
477*7c478bd9Sstevel@tonic-gate new_blk->addr_lo = curr_blk->addr_lo;
478*7c478bd9Sstevel@tonic-gate new_blk->addr_hi = upper_bound;
479*7c478bd9Sstevel@tonic-gate new_blk->addr_type = curr_blk->addr_type;
480*7c478bd9Sstevel@tonic-gate new_blk->addr_reserved = ADDR_RESERVED;
481*7c478bd9Sstevel@tonic-gate
482*7c478bd9Sstevel@tonic-gate curr_blk->addr_lo = new_blk->addr_hi + 1;
483*7c478bd9Sstevel@tonic-gate
484*7c478bd9Sstevel@tonic-gate /* Put it back into the "free" list */
485*7c478bd9Sstevel@tonic-gate s1394_free_list_insert(hal, new_blk);
486*7c478bd9Sstevel@tonic-gate
487*7c478bd9Sstevel@tonic-gate /* Unlock the address space free list */
488*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
489*7c478bd9Sstevel@tonic-gate
490*7c478bd9Sstevel@tonic-gate return (DDI_SUCCESS);
491*7c478bd9Sstevel@tonic-gate }
492*7c478bd9Sstevel@tonic-gate
493*7c478bd9Sstevel@tonic-gate } else {
494*7c478bd9Sstevel@tonic-gate if (upper_bound == curr_blk->addr_hi) {
495*7c478bd9Sstevel@tonic-gate /* End part of range */
496*7c478bd9Sstevel@tonic-gate new_blk = (s1394_addr_space_blk_t *)
497*7c478bd9Sstevel@tonic-gate kmem_zalloc(sizeof (s1394_addr_space_blk_t),
498*7c478bd9Sstevel@tonic-gate KM_NOSLEEP);
499*7c478bd9Sstevel@tonic-gate if (new_blk == NULL) {
500*7c478bd9Sstevel@tonic-gate /* Unlock the addr space "free" list */
501*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
502*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
503*7c478bd9Sstevel@tonic-gate }
504*7c478bd9Sstevel@tonic-gate
505*7c478bd9Sstevel@tonic-gate new_blk->addr_lo = addr_allocp->aa_address;
506*7c478bd9Sstevel@tonic-gate new_blk->addr_hi = upper_bound;
507*7c478bd9Sstevel@tonic-gate new_blk->addr_type = curr_blk->addr_type;
508*7c478bd9Sstevel@tonic-gate new_blk->addr_reserved = ADDR_RESERVED;
509*7c478bd9Sstevel@tonic-gate
510*7c478bd9Sstevel@tonic-gate curr_blk->addr_hi = addr_allocp->aa_address - 1;
511*7c478bd9Sstevel@tonic-gate
512*7c478bd9Sstevel@tonic-gate /* Put it back into the "free" list */
513*7c478bd9Sstevel@tonic-gate s1394_free_list_insert(hal, new_blk);
514*7c478bd9Sstevel@tonic-gate
515*7c478bd9Sstevel@tonic-gate /* Unlock the address space free list */
516*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
517*7c478bd9Sstevel@tonic-gate
518*7c478bd9Sstevel@tonic-gate return (DDI_SUCCESS);
519*7c478bd9Sstevel@tonic-gate
520*7c478bd9Sstevel@tonic-gate } else {
521*7c478bd9Sstevel@tonic-gate /* Middle part of range */
522*7c478bd9Sstevel@tonic-gate new_blk = (s1394_addr_space_blk_t *)
523*7c478bd9Sstevel@tonic-gate kmem_zalloc(sizeof (s1394_addr_space_blk_t),
524*7c478bd9Sstevel@tonic-gate KM_NOSLEEP);
525*7c478bd9Sstevel@tonic-gate if (new_blk == NULL) {
526*7c478bd9Sstevel@tonic-gate /* Unlock the addr space "free" list */
527*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
528*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
529*7c478bd9Sstevel@tonic-gate }
530*7c478bd9Sstevel@tonic-gate
531*7c478bd9Sstevel@tonic-gate middle_blk = (s1394_addr_space_blk_t *)
532*7c478bd9Sstevel@tonic-gate kmem_zalloc(sizeof (s1394_addr_space_blk_t),
533*7c478bd9Sstevel@tonic-gate KM_NOSLEEP);
534*7c478bd9Sstevel@tonic-gate if (middle_blk == NULL) {
535*7c478bd9Sstevel@tonic-gate /* Unlock the addr space "free" list */
536*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
537*7c478bd9Sstevel@tonic-gate kmem_free(new_blk,
538*7c478bd9Sstevel@tonic-gate sizeof (s1394_addr_space_blk_t));
539*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
540*7c478bd9Sstevel@tonic-gate }
541*7c478bd9Sstevel@tonic-gate
542*7c478bd9Sstevel@tonic-gate middle_blk->addr_lo = addr_allocp->aa_address;
543*7c478bd9Sstevel@tonic-gate middle_blk->addr_hi = upper_bound;
544*7c478bd9Sstevel@tonic-gate new_blk->addr_lo = upper_bound + 1;
545*7c478bd9Sstevel@tonic-gate new_blk->addr_hi = curr_blk->addr_hi;
546*7c478bd9Sstevel@tonic-gate
547*7c478bd9Sstevel@tonic-gate new_blk->addr_type = curr_blk->addr_type;
548*7c478bd9Sstevel@tonic-gate
549*7c478bd9Sstevel@tonic-gate middle_blk->addr_type = curr_blk->addr_type;
550*7c478bd9Sstevel@tonic-gate middle_blk->addr_reserved = ADDR_RESERVED;
551*7c478bd9Sstevel@tonic-gate
552*7c478bd9Sstevel@tonic-gate curr_blk->addr_hi = addr_allocp->aa_address - 1;
553*7c478bd9Sstevel@tonic-gate
554*7c478bd9Sstevel@tonic-gate /* Put pieces back into the "free" list */
555*7c478bd9Sstevel@tonic-gate s1394_free_list_insert(hal, middle_blk);
556*7c478bd9Sstevel@tonic-gate s1394_free_list_insert(hal, new_blk);
557*7c478bd9Sstevel@tonic-gate
558*7c478bd9Sstevel@tonic-gate /* Unlock the address space free list */
559*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
560*7c478bd9Sstevel@tonic-gate
561*7c478bd9Sstevel@tonic-gate return (DDI_SUCCESS);
562*7c478bd9Sstevel@tonic-gate }
563*7c478bd9Sstevel@tonic-gate }
564*7c478bd9Sstevel@tonic-gate }
565*7c478bd9Sstevel@tonic-gate
566*7c478bd9Sstevel@tonic-gate /* Unlock the address space free list */
567*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
568*7c478bd9Sstevel@tonic-gate
569*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
570*7c478bd9Sstevel@tonic-gate }
571*7c478bd9Sstevel@tonic-gate
572*7c478bd9Sstevel@tonic-gate /*
573*7c478bd9Sstevel@tonic-gate * s1394_init_addr_space()
574*7c478bd9Sstevel@tonic-gate * is called in the HAL attach routine - h1394_attach() - to setup the
575*7c478bd9Sstevel@tonic-gate * initial address space with the appropriate ranges, etc. At attach,
576*7c478bd9Sstevel@tonic-gate * the HAL specifies not only the type and bounds for each kind of 1394
577*7c478bd9Sstevel@tonic-gate * address space, but also a list of the blocks that are to be marked
578*7c478bd9Sstevel@tonic-gate * �reserved". Prior to marking the "reserved" ranges the local hosts
579*7c478bd9Sstevel@tonic-gate * CSR registers are allocated/setup in s1394_setup_CSR_space().
580*7c478bd9Sstevel@tonic-gate */
581*7c478bd9Sstevel@tonic-gate int
s1394_init_addr_space(s1394_hal_t * hal)582*7c478bd9Sstevel@tonic-gate s1394_init_addr_space(s1394_hal_t *hal)
583*7c478bd9Sstevel@tonic-gate {
584*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *addr_blk;
585*7c478bd9Sstevel@tonic-gate t1394_alloc_addr_t addr_alloc;
586*7c478bd9Sstevel@tonic-gate h1394_addr_map_t *addr_map;
587*7c478bd9Sstevel@tonic-gate h1394_addr_map_t *resv_map;
588*7c478bd9Sstevel@tonic-gate uint_t num_blks;
589*7c478bd9Sstevel@tonic-gate uint64_t lo;
590*7c478bd9Sstevel@tonic-gate uint64_t hi;
591*7c478bd9Sstevel@tonic-gate int i;
592*7c478bd9Sstevel@tonic-gate int ret;
593*7c478bd9Sstevel@tonic-gate
594*7c478bd9Sstevel@tonic-gate /* Setup Address Space */
595*7c478bd9Sstevel@tonic-gate mutex_init(&hal->addr_space_free_mutex,
596*7c478bd9Sstevel@tonic-gate NULL, MUTEX_DRIVER, NULL);
597*7c478bd9Sstevel@tonic-gate mutex_init(&hal->addr_space_used_mutex,
598*7c478bd9Sstevel@tonic-gate NULL, MUTEX_DRIVER, hal->halinfo.hw_interrupt);
599*7c478bd9Sstevel@tonic-gate
600*7c478bd9Sstevel@tonic-gate /* Set address space to NULL (empty) */
601*7c478bd9Sstevel@tonic-gate hal->addr_space_free_list = NULL;
602*7c478bd9Sstevel@tonic-gate hal->addr_space_used_tree = NULL;
603*7c478bd9Sstevel@tonic-gate
604*7c478bd9Sstevel@tonic-gate /* Initialize the 1394 Address Space from HAL's description */
605*7c478bd9Sstevel@tonic-gate num_blks = hal->halinfo.addr_map_num_entries;
606*7c478bd9Sstevel@tonic-gate addr_map = hal->halinfo.addr_map;
607*7c478bd9Sstevel@tonic-gate
608*7c478bd9Sstevel@tonic-gate /* Lock the address space free list */
609*7c478bd9Sstevel@tonic-gate mutex_enter(&hal->addr_space_free_mutex);
610*7c478bd9Sstevel@tonic-gate
611*7c478bd9Sstevel@tonic-gate /* Default to NO posted write space */
612*7c478bd9Sstevel@tonic-gate hal->posted_write_addr_lo = ADDR_LO_INVALID;
613*7c478bd9Sstevel@tonic-gate hal->posted_write_addr_hi = ADDR_HI_INVALID;
614*7c478bd9Sstevel@tonic-gate
615*7c478bd9Sstevel@tonic-gate /* Default to NO physical space */
616*7c478bd9Sstevel@tonic-gate hal->physical_addr_lo = ADDR_LO_INVALID;
617*7c478bd9Sstevel@tonic-gate hal->physical_addr_hi = ADDR_HI_INVALID;
618*7c478bd9Sstevel@tonic-gate
619*7c478bd9Sstevel@tonic-gate /* Default to NO CSR space */
620*7c478bd9Sstevel@tonic-gate hal->csr_addr_lo = ADDR_LO_INVALID;
621*7c478bd9Sstevel@tonic-gate hal->csr_addr_hi = ADDR_HI_INVALID;
622*7c478bd9Sstevel@tonic-gate
623*7c478bd9Sstevel@tonic-gate /* Default to NO normal space */
624*7c478bd9Sstevel@tonic-gate hal->normal_addr_lo = ADDR_LO_INVALID;
625*7c478bd9Sstevel@tonic-gate hal->normal_addr_hi = ADDR_HI_INVALID;
626*7c478bd9Sstevel@tonic-gate
627*7c478bd9Sstevel@tonic-gate for (i = 0; i < num_blks; i++) {
628*7c478bd9Sstevel@tonic-gate if (addr_map[i].length == 0)
629*7c478bd9Sstevel@tonic-gate continue;
630*7c478bd9Sstevel@tonic-gate addr_blk = kmem_zalloc(sizeof (s1394_addr_space_blk_t),
631*7c478bd9Sstevel@tonic-gate KM_SLEEP);
632*7c478bd9Sstevel@tonic-gate addr_blk->addr_lo = addr_map[i].address;
633*7c478bd9Sstevel@tonic-gate addr_blk->addr_hi =
634*7c478bd9Sstevel@tonic-gate (addr_blk->addr_lo + addr_map[i].length) - 1;
635*7c478bd9Sstevel@tonic-gate
636*7c478bd9Sstevel@tonic-gate switch (addr_map[i].addr_type) {
637*7c478bd9Sstevel@tonic-gate case H1394_ADDR_POSTED_WRITE:
638*7c478bd9Sstevel@tonic-gate addr_blk->addr_type = T1394_ADDR_POSTED_WRITE;
639*7c478bd9Sstevel@tonic-gate hal->posted_write_addr_lo = addr_blk->addr_lo;
640*7c478bd9Sstevel@tonic-gate hal->posted_write_addr_hi = addr_blk->addr_hi;
641*7c478bd9Sstevel@tonic-gate break;
642*7c478bd9Sstevel@tonic-gate
643*7c478bd9Sstevel@tonic-gate case H1394_ADDR_NORMAL:
644*7c478bd9Sstevel@tonic-gate addr_blk->addr_type = T1394_ADDR_NORMAL;
645*7c478bd9Sstevel@tonic-gate hal->normal_addr_lo = addr_blk->addr_lo;
646*7c478bd9Sstevel@tonic-gate hal->normal_addr_hi = addr_blk->addr_hi;
647*7c478bd9Sstevel@tonic-gate break;
648*7c478bd9Sstevel@tonic-gate
649*7c478bd9Sstevel@tonic-gate case H1394_ADDR_CSR:
650*7c478bd9Sstevel@tonic-gate addr_blk->addr_type = T1394_ADDR_CSR;
651*7c478bd9Sstevel@tonic-gate hal->csr_addr_lo = addr_blk->addr_lo;
652*7c478bd9Sstevel@tonic-gate hal->csr_addr_hi = addr_blk->addr_hi;
653*7c478bd9Sstevel@tonic-gate break;
654*7c478bd9Sstevel@tonic-gate
655*7c478bd9Sstevel@tonic-gate case H1394_ADDR_PHYSICAL:
656*7c478bd9Sstevel@tonic-gate addr_blk->addr_type = T1394_ADDR_FIXED;
657*7c478bd9Sstevel@tonic-gate hal->physical_addr_lo = addr_blk->addr_lo;
658*7c478bd9Sstevel@tonic-gate hal->physical_addr_hi = addr_blk->addr_hi;
659*7c478bd9Sstevel@tonic-gate break;
660*7c478bd9Sstevel@tonic-gate
661*7c478bd9Sstevel@tonic-gate default:
662*7c478bd9Sstevel@tonic-gate /* Unlock the address space free list */
663*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
664*7c478bd9Sstevel@tonic-gate s1394_destroy_addr_space(hal);
665*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
666*7c478bd9Sstevel@tonic-gate }
667*7c478bd9Sstevel@tonic-gate s1394_free_list_insert(hal, addr_blk);
668*7c478bd9Sstevel@tonic-gate }
669*7c478bd9Sstevel@tonic-gate
670*7c478bd9Sstevel@tonic-gate /* Unlock the address space free list */
671*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
672*7c478bd9Sstevel@tonic-gate
673*7c478bd9Sstevel@tonic-gate /* Setup the necessary CSR space */
674*7c478bd9Sstevel@tonic-gate if (s1394_setup_CSR_space(hal) != DDI_SUCCESS) {
675*7c478bd9Sstevel@tonic-gate s1394_destroy_addr_space(hal);
676*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
677*7c478bd9Sstevel@tonic-gate }
678*7c478bd9Sstevel@tonic-gate
679*7c478bd9Sstevel@tonic-gate
680*7c478bd9Sstevel@tonic-gate /* Handle all the HAL's reserved spaces */
681*7c478bd9Sstevel@tonic-gate num_blks = hal->halinfo.resv_map_num_entries;
682*7c478bd9Sstevel@tonic-gate resv_map = hal->halinfo.resv_map;
683*7c478bd9Sstevel@tonic-gate
684*7c478bd9Sstevel@tonic-gate for (i = 0; i < num_blks; i++) {
685*7c478bd9Sstevel@tonic-gate /* Can't reserve physical addresses */
686*7c478bd9Sstevel@tonic-gate lo = resv_map[i].address;
687*7c478bd9Sstevel@tonic-gate hi = (lo + resv_map[i].length) - 1;
688*7c478bd9Sstevel@tonic-gate if ((lo >= hal->physical_addr_lo) &&
689*7c478bd9Sstevel@tonic-gate (hi <= hal->physical_addr_hi)) {
690*7c478bd9Sstevel@tonic-gate s1394_destroy_addr_space(hal);
691*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
692*7c478bd9Sstevel@tonic-gate }
693*7c478bd9Sstevel@tonic-gate
694*7c478bd9Sstevel@tonic-gate addr_alloc.aa_address = resv_map[i].address;
695*7c478bd9Sstevel@tonic-gate addr_alloc.aa_length = resv_map[i].length;
696*7c478bd9Sstevel@tonic-gate ret = s1394_reserve_addr_blk(hal, &addr_alloc);
697*7c478bd9Sstevel@tonic-gate if (ret != DDI_SUCCESS) {
698*7c478bd9Sstevel@tonic-gate s1394_destroy_addr_space(hal);
699*7c478bd9Sstevel@tonic-gate return (DDI_FAILURE);
700*7c478bd9Sstevel@tonic-gate }
701*7c478bd9Sstevel@tonic-gate }
702*7c478bd9Sstevel@tonic-gate
703*7c478bd9Sstevel@tonic-gate return (DDI_SUCCESS);
704*7c478bd9Sstevel@tonic-gate }
705*7c478bd9Sstevel@tonic-gate
706*7c478bd9Sstevel@tonic-gate /*
707*7c478bd9Sstevel@tonic-gate * s1394_destroy_addr_space()
708*7c478bd9Sstevel@tonic-gate * is necessary for h1394_detach(). It undoes all the work that
709*7c478bd9Sstevel@tonic-gate * s1394_init_addr_space() had setup and more. By pulling everything out
710*7c478bd9Sstevel@tonic-gate * of the used tree and free list and then freeing the structures,
711*7c478bd9Sstevel@tonic-gate * mutexes, and (if necessary) any backing store memory, the 1394 address
712*7c478bd9Sstevel@tonic-gate * space is completely dismantled.
713*7c478bd9Sstevel@tonic-gate */
714*7c478bd9Sstevel@tonic-gate void
s1394_destroy_addr_space(s1394_hal_t * hal)715*7c478bd9Sstevel@tonic-gate s1394_destroy_addr_space(s1394_hal_t *hal)
716*7c478bd9Sstevel@tonic-gate {
717*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *addr_blk;
718*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *next_blk;
719*7c478bd9Sstevel@tonic-gate uint64_t lo;
720*7c478bd9Sstevel@tonic-gate uint64_t hi;
721*7c478bd9Sstevel@tonic-gate uint_t length;
722*7c478bd9Sstevel@tonic-gate
723*7c478bd9Sstevel@tonic-gate /* Lock the address space "used" tree */
724*7c478bd9Sstevel@tonic-gate mutex_enter(&hal->addr_space_used_mutex);
725*7c478bd9Sstevel@tonic-gate
726*7c478bd9Sstevel@tonic-gate addr_blk = hal->addr_space_used_tree;
727*7c478bd9Sstevel@tonic-gate
728*7c478bd9Sstevel@tonic-gate while (addr_blk != NULL) {
729*7c478bd9Sstevel@tonic-gate if (addr_blk->asb_left != NULL) {
730*7c478bd9Sstevel@tonic-gate addr_blk = addr_blk->asb_left;
731*7c478bd9Sstevel@tonic-gate } else if (addr_blk->asb_right != NULL) {
732*7c478bd9Sstevel@tonic-gate addr_blk = addr_blk->asb_right;
733*7c478bd9Sstevel@tonic-gate } else {
734*7c478bd9Sstevel@tonic-gate /* Free any of our own backing store (if necessary) */
735*7c478bd9Sstevel@tonic-gate if ((addr_blk->free_kmem_bufp == B_TRUE) &&
736*7c478bd9Sstevel@tonic-gate (addr_blk->kmem_bufp != NULL)) {
737*7c478bd9Sstevel@tonic-gate lo = addr_blk->addr_lo;
738*7c478bd9Sstevel@tonic-gate hi = addr_blk->addr_hi;
739*7c478bd9Sstevel@tonic-gate length = (uint_t)((hi - lo) + 1);
740*7c478bd9Sstevel@tonic-gate kmem_free((void *)addr_blk->kmem_bufp, length);
741*7c478bd9Sstevel@tonic-gate }
742*7c478bd9Sstevel@tonic-gate
743*7c478bd9Sstevel@tonic-gate next_blk = addr_blk->asb_parent;
744*7c478bd9Sstevel@tonic-gate
745*7c478bd9Sstevel@tonic-gate /* Free the s1394_addr_space_blk_t structure */
746*7c478bd9Sstevel@tonic-gate kmem_free((void *)addr_blk,
747*7c478bd9Sstevel@tonic-gate sizeof (s1394_addr_space_blk_t));
748*7c478bd9Sstevel@tonic-gate
749*7c478bd9Sstevel@tonic-gate if (next_blk != NULL) {
750*7c478bd9Sstevel@tonic-gate if (next_blk->asb_left != NULL)
751*7c478bd9Sstevel@tonic-gate next_blk->asb_left = NULL;
752*7c478bd9Sstevel@tonic-gate else
753*7c478bd9Sstevel@tonic-gate next_blk->asb_right = NULL;
754*7c478bd9Sstevel@tonic-gate }
755*7c478bd9Sstevel@tonic-gate
756*7c478bd9Sstevel@tonic-gate addr_blk = next_blk;
757*7c478bd9Sstevel@tonic-gate }
758*7c478bd9Sstevel@tonic-gate }
759*7c478bd9Sstevel@tonic-gate
760*7c478bd9Sstevel@tonic-gate /* Unlock and destroy the address space "used" tree */
761*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_used_mutex);
762*7c478bd9Sstevel@tonic-gate mutex_destroy(&hal->addr_space_used_mutex);
763*7c478bd9Sstevel@tonic-gate
764*7c478bd9Sstevel@tonic-gate /* Lock the address space "free" list */
765*7c478bd9Sstevel@tonic-gate mutex_enter(&hal->addr_space_free_mutex);
766*7c478bd9Sstevel@tonic-gate
767*7c478bd9Sstevel@tonic-gate addr_blk = hal->addr_space_free_list;
768*7c478bd9Sstevel@tonic-gate
769*7c478bd9Sstevel@tonic-gate while (addr_blk != NULL) {
770*7c478bd9Sstevel@tonic-gate next_blk = addr_blk->asb_right;
771*7c478bd9Sstevel@tonic-gate
772*7c478bd9Sstevel@tonic-gate /* Free the s1394_addr_space_blk_t structure */
773*7c478bd9Sstevel@tonic-gate kmem_free((void *)addr_blk, sizeof (s1394_addr_space_blk_t));
774*7c478bd9Sstevel@tonic-gate addr_blk = next_blk;
775*7c478bd9Sstevel@tonic-gate }
776*7c478bd9Sstevel@tonic-gate
777*7c478bd9Sstevel@tonic-gate /* Unlock & destroy the address space "free" list */
778*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_free_mutex);
779*7c478bd9Sstevel@tonic-gate mutex_destroy(&hal->addr_space_free_mutex);
780*7c478bd9Sstevel@tonic-gate }
781*7c478bd9Sstevel@tonic-gate
782*7c478bd9Sstevel@tonic-gate /*
783*7c478bd9Sstevel@tonic-gate * s1394_free_list_insert()
784*7c478bd9Sstevel@tonic-gate * takes an s1394_addr_space_blk_t and inserts it into the free list in the
785*7c478bd9Sstevel@tonic-gate * appropriate place. It will concatenate into a single structure on the
786*7c478bd9Sstevel@tonic-gate * list any two neighboring blocks that can be joined (same type,
787*7c478bd9Sstevel@tonic-gate * consecutive addresses, neither is "reserved", etc.)
788*7c478bd9Sstevel@tonic-gate */
789*7c478bd9Sstevel@tonic-gate void
s1394_free_list_insert(s1394_hal_t * hal,s1394_addr_space_blk_t * new_blk)790*7c478bd9Sstevel@tonic-gate s1394_free_list_insert(s1394_hal_t *hal, s1394_addr_space_blk_t *new_blk)
791*7c478bd9Sstevel@tonic-gate {
792*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *curr_blk;
793*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *left_blk;
794*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *right_blk;
795*7c478bd9Sstevel@tonic-gate
796*7c478bd9Sstevel@tonic-gate ASSERT(MUTEX_HELD(&hal->addr_space_free_mutex));
797*7c478bd9Sstevel@tonic-gate
798*7c478bd9Sstevel@tonic-gate /* Start at the head of the "free" list */
799*7c478bd9Sstevel@tonic-gate curr_blk = hal->addr_space_free_list;
800*7c478bd9Sstevel@tonic-gate
801*7c478bd9Sstevel@tonic-gate if (curr_blk != NULL)
802*7c478bd9Sstevel@tonic-gate left_blk = curr_blk->asb_left;
803*7c478bd9Sstevel@tonic-gate else
804*7c478bd9Sstevel@tonic-gate left_blk = NULL;
805*7c478bd9Sstevel@tonic-gate
806*7c478bd9Sstevel@tonic-gate while (curr_blk != NULL) {
807*7c478bd9Sstevel@tonic-gate if (new_blk->addr_lo < curr_blk->addr_lo)
808*7c478bd9Sstevel@tonic-gate break;
809*7c478bd9Sstevel@tonic-gate /* Go to the next element in the list */
810*7c478bd9Sstevel@tonic-gate left_blk = curr_blk;
811*7c478bd9Sstevel@tonic-gate curr_blk = curr_blk->asb_right;
812*7c478bd9Sstevel@tonic-gate }
813*7c478bd9Sstevel@tonic-gate
814*7c478bd9Sstevel@tonic-gate new_blk->asb_left = left_blk;
815*7c478bd9Sstevel@tonic-gate new_blk->asb_right = curr_blk;
816*7c478bd9Sstevel@tonic-gate
817*7c478bd9Sstevel@tonic-gate if (left_blk != NULL)
818*7c478bd9Sstevel@tonic-gate left_blk->asb_right = new_blk;
819*7c478bd9Sstevel@tonic-gate else
820*7c478bd9Sstevel@tonic-gate hal->addr_space_free_list = new_blk;
821*7c478bd9Sstevel@tonic-gate
822*7c478bd9Sstevel@tonic-gate if (curr_blk != NULL)
823*7c478bd9Sstevel@tonic-gate curr_blk->asb_left = new_blk;
824*7c478bd9Sstevel@tonic-gate
825*7c478bd9Sstevel@tonic-gate right_blk = new_blk->asb_right;
826*7c478bd9Sstevel@tonic-gate left_blk = new_blk->asb_left;
827*7c478bd9Sstevel@tonic-gate
828*7c478bd9Sstevel@tonic-gate /* Can we merge with block to the left? */
829*7c478bd9Sstevel@tonic-gate if ((left_blk != NULL) &&
830*7c478bd9Sstevel@tonic-gate (new_blk->addr_type == left_blk->addr_type) &&
831*7c478bd9Sstevel@tonic-gate (new_blk->addr_reserved != ADDR_RESERVED) &&
832*7c478bd9Sstevel@tonic-gate (left_blk->addr_reserved != ADDR_RESERVED) &&
833*7c478bd9Sstevel@tonic-gate (new_blk->addr_lo == left_blk->addr_hi + 1)) {
834*7c478bd9Sstevel@tonic-gate
835*7c478bd9Sstevel@tonic-gate new_blk->addr_lo = left_blk->addr_lo;
836*7c478bd9Sstevel@tonic-gate new_blk->asb_left = left_blk->asb_left;
837*7c478bd9Sstevel@tonic-gate
838*7c478bd9Sstevel@tonic-gate if (left_blk->asb_left != NULL)
839*7c478bd9Sstevel@tonic-gate left_blk->asb_left->asb_right = new_blk;
840*7c478bd9Sstevel@tonic-gate if (hal->addr_space_free_list == left_blk)
841*7c478bd9Sstevel@tonic-gate hal->addr_space_free_list = new_blk;
842*7c478bd9Sstevel@tonic-gate kmem_free((void *)left_blk, sizeof (s1394_addr_space_blk_t));
843*7c478bd9Sstevel@tonic-gate }
844*7c478bd9Sstevel@tonic-gate
845*7c478bd9Sstevel@tonic-gate /* Can we merge with block to the right? */
846*7c478bd9Sstevel@tonic-gate if ((right_blk != NULL) &&
847*7c478bd9Sstevel@tonic-gate (new_blk->addr_type == right_blk->addr_type) &&
848*7c478bd9Sstevel@tonic-gate (new_blk->addr_reserved != ADDR_RESERVED) &&
849*7c478bd9Sstevel@tonic-gate (right_blk->addr_reserved != ADDR_RESERVED) &&
850*7c478bd9Sstevel@tonic-gate (new_blk->addr_hi + 1 == right_blk->addr_lo)) {
851*7c478bd9Sstevel@tonic-gate
852*7c478bd9Sstevel@tonic-gate new_blk->addr_hi = right_blk->addr_hi;
853*7c478bd9Sstevel@tonic-gate new_blk->asb_right = right_blk->asb_right;
854*7c478bd9Sstevel@tonic-gate
855*7c478bd9Sstevel@tonic-gate if (right_blk->asb_right != NULL)
856*7c478bd9Sstevel@tonic-gate right_blk->asb_right->asb_left = new_blk;
857*7c478bd9Sstevel@tonic-gate kmem_free((void *)right_blk, sizeof (s1394_addr_space_blk_t));
858*7c478bd9Sstevel@tonic-gate }
859*7c478bd9Sstevel@tonic-gate
860*7c478bd9Sstevel@tonic-gate new_blk->addr_enable = 0;
861*7c478bd9Sstevel@tonic-gate new_blk->kmem_bufp = NULL;
862*7c478bd9Sstevel@tonic-gate new_blk->addr_arg = NULL;
863*7c478bd9Sstevel@tonic-gate }
864*7c478bd9Sstevel@tonic-gate
865*7c478bd9Sstevel@tonic-gate /*
866*7c478bd9Sstevel@tonic-gate * s1394_free_list_search()
867*7c478bd9Sstevel@tonic-gate * attempts to find a block in the free list that contains the address
868*7c478bd9Sstevel@tonic-gate * specified. If none is found, it returns NULL.
869*7c478bd9Sstevel@tonic-gate */
870*7c478bd9Sstevel@tonic-gate static s1394_addr_space_blk_t *
s1394_free_list_search(s1394_hal_t * hal,uint64_t addr)871*7c478bd9Sstevel@tonic-gate s1394_free_list_search(s1394_hal_t *hal, uint64_t addr)
872*7c478bd9Sstevel@tonic-gate {
873*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *curr_blk;
874*7c478bd9Sstevel@tonic-gate
875*7c478bd9Sstevel@tonic-gate ASSERT(MUTEX_HELD(&hal->addr_space_free_mutex));
876*7c478bd9Sstevel@tonic-gate
877*7c478bd9Sstevel@tonic-gate /* Start at the head of the list */
878*7c478bd9Sstevel@tonic-gate curr_blk = hal->addr_space_free_list;
879*7c478bd9Sstevel@tonic-gate while (curr_blk != NULL) {
880*7c478bd9Sstevel@tonic-gate if ((addr >= curr_blk->addr_lo) && (addr <= curr_blk->addr_hi))
881*7c478bd9Sstevel@tonic-gate break;
882*7c478bd9Sstevel@tonic-gate else
883*7c478bd9Sstevel@tonic-gate curr_blk = curr_blk->asb_right;
884*7c478bd9Sstevel@tonic-gate }
885*7c478bd9Sstevel@tonic-gate
886*7c478bd9Sstevel@tonic-gate return (curr_blk);
887*7c478bd9Sstevel@tonic-gate }
888*7c478bd9Sstevel@tonic-gate
889*7c478bd9Sstevel@tonic-gate /*
890*7c478bd9Sstevel@tonic-gate * s1394_free_list_find()
891*7c478bd9Sstevel@tonic-gate * attempts to find a block in the free list that is of the specified
892*7c478bd9Sstevel@tonic-gate * type and size. It will ignore any blocks marked "reserved".
893*7c478bd9Sstevel@tonic-gate */
894*7c478bd9Sstevel@tonic-gate static s1394_addr_space_blk_t *
s1394_free_list_find(s1394_hal_t * hal,uint32_t type,uint32_t length)895*7c478bd9Sstevel@tonic-gate s1394_free_list_find(s1394_hal_t *hal, uint32_t type, uint32_t length)
896*7c478bd9Sstevel@tonic-gate {
897*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *curr_blk;
898*7c478bd9Sstevel@tonic-gate uint64_t size;
899*7c478bd9Sstevel@tonic-gate
900*7c478bd9Sstevel@tonic-gate ASSERT(MUTEX_HELD(&hal->addr_space_free_mutex));
901*7c478bd9Sstevel@tonic-gate
902*7c478bd9Sstevel@tonic-gate /* Start at the head of the list */
903*7c478bd9Sstevel@tonic-gate curr_blk = hal->addr_space_free_list;
904*7c478bd9Sstevel@tonic-gate
905*7c478bd9Sstevel@tonic-gate while (curr_blk != NULL) {
906*7c478bd9Sstevel@tonic-gate /* Find block of right "type" - that isn't "reserved" */
907*7c478bd9Sstevel@tonic-gate if ((curr_blk->addr_type == type) &&
908*7c478bd9Sstevel@tonic-gate (curr_blk->addr_reserved != ADDR_RESERVED)) {
909*7c478bd9Sstevel@tonic-gate
910*7c478bd9Sstevel@tonic-gate /* CSR allocs above IEEE1394_UCSR_RESERVED_BOUNDARY */
911*7c478bd9Sstevel@tonic-gate if ((type == T1394_ADDR_CSR) &&
912*7c478bd9Sstevel@tonic-gate (curr_blk->addr_lo <
913*7c478bd9Sstevel@tonic-gate IEEE1394_UCSR_RESERVED_BOUNDARY)) {
914*7c478bd9Sstevel@tonic-gate curr_blk = curr_blk->asb_right;
915*7c478bd9Sstevel@tonic-gate continue;
916*7c478bd9Sstevel@tonic-gate }
917*7c478bd9Sstevel@tonic-gate
918*7c478bd9Sstevel@tonic-gate size = (curr_blk->addr_hi - curr_blk->addr_lo) + 1;
919*7c478bd9Sstevel@tonic-gate if (size >= (uint64_t)length)
920*7c478bd9Sstevel@tonic-gate break;
921*7c478bd9Sstevel@tonic-gate }
922*7c478bd9Sstevel@tonic-gate curr_blk = curr_blk->asb_right;
923*7c478bd9Sstevel@tonic-gate }
924*7c478bd9Sstevel@tonic-gate
925*7c478bd9Sstevel@tonic-gate return (curr_blk);
926*7c478bd9Sstevel@tonic-gate }
927*7c478bd9Sstevel@tonic-gate
928*7c478bd9Sstevel@tonic-gate /*
929*7c478bd9Sstevel@tonic-gate * s1394_free_list_delete()
930*7c478bd9Sstevel@tonic-gate * will remove the block pointed to by del_blk from the free list.
931*7c478bd9Sstevel@tonic-gate * Typically, this is done so that it may be inserted into the used tree.
932*7c478bd9Sstevel@tonic-gate */
933*7c478bd9Sstevel@tonic-gate static s1394_addr_space_blk_t *
s1394_free_list_delete(s1394_hal_t * hal,s1394_addr_space_blk_t * del_blk)934*7c478bd9Sstevel@tonic-gate s1394_free_list_delete(s1394_hal_t *hal, s1394_addr_space_blk_t *del_blk)
935*7c478bd9Sstevel@tonic-gate {
936*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *left_blk;
937*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *right_blk;
938*7c478bd9Sstevel@tonic-gate
939*7c478bd9Sstevel@tonic-gate ASSERT(MUTEX_HELD(&hal->addr_space_free_mutex));
940*7c478bd9Sstevel@tonic-gate
941*7c478bd9Sstevel@tonic-gate left_blk = del_blk->asb_left;
942*7c478bd9Sstevel@tonic-gate right_blk = del_blk->asb_right;
943*7c478bd9Sstevel@tonic-gate
944*7c478bd9Sstevel@tonic-gate del_blk->asb_left = NULL;
945*7c478bd9Sstevel@tonic-gate del_blk->asb_right = NULL;
946*7c478bd9Sstevel@tonic-gate
947*7c478bd9Sstevel@tonic-gate if (left_blk != NULL)
948*7c478bd9Sstevel@tonic-gate left_blk->asb_right = right_blk;
949*7c478bd9Sstevel@tonic-gate else
950*7c478bd9Sstevel@tonic-gate hal->addr_space_free_list = right_blk;
951*7c478bd9Sstevel@tonic-gate
952*7c478bd9Sstevel@tonic-gate if (right_blk != NULL)
953*7c478bd9Sstevel@tonic-gate right_blk->asb_left = left_blk;
954*7c478bd9Sstevel@tonic-gate
955*7c478bd9Sstevel@tonic-gate return (del_blk);
956*7c478bd9Sstevel@tonic-gate }
957*7c478bd9Sstevel@tonic-gate
958*7c478bd9Sstevel@tonic-gate /*
959*7c478bd9Sstevel@tonic-gate * s1394_used_tree_insert()
960*7c478bd9Sstevel@tonic-gate * is used to insert a 1394 address block that has been removed from the
961*7c478bd9Sstevel@tonic-gate * free list into the used tree. In the used tree it will be possible
962*7c478bd9Sstevel@tonic-gate * to search for a given address when an AR request arrives. Since the
963*7c478bd9Sstevel@tonic-gate * used tree is implemented as a red-black tree, the insertion is done
964*7c478bd9Sstevel@tonic-gate * with s1394_tree_insert() which does a simple binary tree insertion.
965*7c478bd9Sstevel@tonic-gate * It is then followed by cleanup of links and red-black coloring. This
966*7c478bd9Sstevel@tonic-gate * particulat implementation of the red-black tree is modified from code
967*7c478bd9Sstevel@tonic-gate * included in "Introduction to Algorithms" - Cormen, Leiserson, and Rivest,
968*7c478bd9Sstevel@tonic-gate * pp. 263 - 277.
969*7c478bd9Sstevel@tonic-gate */
970*7c478bd9Sstevel@tonic-gate static void
s1394_used_tree_insert(s1394_hal_t * hal,s1394_addr_space_blk_t * x)971*7c478bd9Sstevel@tonic-gate s1394_used_tree_insert(s1394_hal_t *hal, s1394_addr_space_blk_t *x)
972*7c478bd9Sstevel@tonic-gate {
973*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *y;
974*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t **root;
975*7c478bd9Sstevel@tonic-gate
976*7c478bd9Sstevel@tonic-gate /* Lock the "used" tree */
977*7c478bd9Sstevel@tonic-gate mutex_enter(&hal->addr_space_used_mutex);
978*7c478bd9Sstevel@tonic-gate
979*7c478bd9Sstevel@tonic-gate /* Get the head of the "used" tree */
980*7c478bd9Sstevel@tonic-gate root = &hal->addr_space_used_tree;
981*7c478bd9Sstevel@tonic-gate
982*7c478bd9Sstevel@tonic-gate s1394_tree_insert(root, x);
983*7c478bd9Sstevel@tonic-gate
984*7c478bd9Sstevel@tonic-gate x->asb_color = RED;
985*7c478bd9Sstevel@tonic-gate while ((x != *root) && (x->asb_parent->asb_color == RED)) {
986*7c478bd9Sstevel@tonic-gate /* Is x's parent the "left-child" or the "right-child"? */
987*7c478bd9Sstevel@tonic-gate if (x->asb_parent == x->asb_parent->asb_parent->asb_left) {
988*7c478bd9Sstevel@tonic-gate /* Left-child, set y to the sibling */
989*7c478bd9Sstevel@tonic-gate y = x->asb_parent->asb_parent->asb_right;
990*7c478bd9Sstevel@tonic-gate if ((y != NULL) && (y->asb_color == RED)) {
991*7c478bd9Sstevel@tonic-gate x->asb_parent->asb_color = BLACK;
992*7c478bd9Sstevel@tonic-gate y->asb_color = BLACK;
993*7c478bd9Sstevel@tonic-gate x->asb_parent->asb_parent->asb_color = RED;
994*7c478bd9Sstevel@tonic-gate x = x->asb_parent->asb_parent;
995*7c478bd9Sstevel@tonic-gate
996*7c478bd9Sstevel@tonic-gate } else {
997*7c478bd9Sstevel@tonic-gate if (x == x->asb_parent->asb_right) {
998*7c478bd9Sstevel@tonic-gate x = x->asb_parent;
999*7c478bd9Sstevel@tonic-gate s1394_left_rotate(root, x);
1000*7c478bd9Sstevel@tonic-gate }
1001*7c478bd9Sstevel@tonic-gate x->asb_parent->asb_color = BLACK;
1002*7c478bd9Sstevel@tonic-gate x->asb_parent->asb_parent->asb_color = RED;
1003*7c478bd9Sstevel@tonic-gate s1394_right_rotate(root,
1004*7c478bd9Sstevel@tonic-gate x->asb_parent->asb_parent);
1005*7c478bd9Sstevel@tonic-gate }
1006*7c478bd9Sstevel@tonic-gate
1007*7c478bd9Sstevel@tonic-gate } else {
1008*7c478bd9Sstevel@tonic-gate /* Right-child, set y to the sibling */
1009*7c478bd9Sstevel@tonic-gate y = x->asb_parent->asb_parent->asb_left;
1010*7c478bd9Sstevel@tonic-gate if ((y != NULL) && (y->asb_color == RED)) {
1011*7c478bd9Sstevel@tonic-gate x->asb_parent->asb_color = BLACK;
1012*7c478bd9Sstevel@tonic-gate y->asb_color = BLACK;
1013*7c478bd9Sstevel@tonic-gate x->asb_parent->asb_parent->asb_color = RED;
1014*7c478bd9Sstevel@tonic-gate x = x->asb_parent->asb_parent;
1015*7c478bd9Sstevel@tonic-gate
1016*7c478bd9Sstevel@tonic-gate } else {
1017*7c478bd9Sstevel@tonic-gate if (x == x->asb_parent->asb_left) {
1018*7c478bd9Sstevel@tonic-gate x = x->asb_parent;
1019*7c478bd9Sstevel@tonic-gate s1394_right_rotate(root, x);
1020*7c478bd9Sstevel@tonic-gate }
1021*7c478bd9Sstevel@tonic-gate x->asb_parent->asb_color = BLACK;
1022*7c478bd9Sstevel@tonic-gate x->asb_parent->asb_parent->asb_color = RED;
1023*7c478bd9Sstevel@tonic-gate s1394_left_rotate(root,
1024*7c478bd9Sstevel@tonic-gate x->asb_parent->asb_parent);
1025*7c478bd9Sstevel@tonic-gate }
1026*7c478bd9Sstevel@tonic-gate }
1027*7c478bd9Sstevel@tonic-gate }
1028*7c478bd9Sstevel@tonic-gate
1029*7c478bd9Sstevel@tonic-gate (*root)->asb_color = BLACK;
1030*7c478bd9Sstevel@tonic-gate
1031*7c478bd9Sstevel@tonic-gate /* Unlock the "used" tree */
1032*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_used_mutex);
1033*7c478bd9Sstevel@tonic-gate }
1034*7c478bd9Sstevel@tonic-gate
1035*7c478bd9Sstevel@tonic-gate /*
1036*7c478bd9Sstevel@tonic-gate * s1394_tree_insert()
1037*7c478bd9Sstevel@tonic-gate * is a "helper" function for s1394_used_tree_insert(). It inserts an
1038*7c478bd9Sstevel@tonic-gate * address block into a binary tree (red-black tree), and
1039*7c478bd9Sstevel@tonic-gate * s1394_used_tree_insert() then cleans up the links and colorings, etc.
1040*7c478bd9Sstevel@tonic-gate */
1041*7c478bd9Sstevel@tonic-gate static void
s1394_tree_insert(s1394_addr_space_blk_t ** root,s1394_addr_space_blk_t * z)1042*7c478bd9Sstevel@tonic-gate s1394_tree_insert(s1394_addr_space_blk_t **root, s1394_addr_space_blk_t *z)
1043*7c478bd9Sstevel@tonic-gate {
1044*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *y = NULL;
1045*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *x = *root;
1046*7c478bd9Sstevel@tonic-gate
1047*7c478bd9Sstevel@tonic-gate while (x != NULL) {
1048*7c478bd9Sstevel@tonic-gate y = x;
1049*7c478bd9Sstevel@tonic-gate if (z->addr_lo < x->addr_lo)
1050*7c478bd9Sstevel@tonic-gate x = x->asb_left;
1051*7c478bd9Sstevel@tonic-gate else
1052*7c478bd9Sstevel@tonic-gate x = x->asb_right;
1053*7c478bd9Sstevel@tonic-gate }
1054*7c478bd9Sstevel@tonic-gate
1055*7c478bd9Sstevel@tonic-gate z->asb_parent = y;
1056*7c478bd9Sstevel@tonic-gate z->asb_right = NULL;
1057*7c478bd9Sstevel@tonic-gate z->asb_left = NULL;
1058*7c478bd9Sstevel@tonic-gate
1059*7c478bd9Sstevel@tonic-gate if (y == NULL)
1060*7c478bd9Sstevel@tonic-gate *root = z;
1061*7c478bd9Sstevel@tonic-gate else if (z->addr_lo < y->addr_lo)
1062*7c478bd9Sstevel@tonic-gate y->asb_left = z;
1063*7c478bd9Sstevel@tonic-gate else
1064*7c478bd9Sstevel@tonic-gate y->asb_right = z;
1065*7c478bd9Sstevel@tonic-gate }
1066*7c478bd9Sstevel@tonic-gate
1067*7c478bd9Sstevel@tonic-gate /*
1068*7c478bd9Sstevel@tonic-gate * s1394_used_tree_search()
1069*7c478bd9Sstevel@tonic-gate * is called when an AR request arrives. By calling s1394_tree_search()
1070*7c478bd9Sstevel@tonic-gate * with the destination address, it can quickly find a block for that
1071*7c478bd9Sstevel@tonic-gate * address (if one exists in the used tree) and return a pointer to it.
1072*7c478bd9Sstevel@tonic-gate */
1073*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *
s1394_used_tree_search(s1394_hal_t * hal,uint64_t addr)1074*7c478bd9Sstevel@tonic-gate s1394_used_tree_search(s1394_hal_t *hal, uint64_t addr)
1075*7c478bd9Sstevel@tonic-gate {
1076*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *curr_blk;
1077*7c478bd9Sstevel@tonic-gate
1078*7c478bd9Sstevel@tonic-gate ASSERT(MUTEX_HELD(&hal->addr_space_used_mutex));
1079*7c478bd9Sstevel@tonic-gate
1080*7c478bd9Sstevel@tonic-gate /* Search the HAL's "used" tree for this address */
1081*7c478bd9Sstevel@tonic-gate curr_blk = s1394_tree_search(hal->addr_space_used_tree, addr);
1082*7c478bd9Sstevel@tonic-gate
1083*7c478bd9Sstevel@tonic-gate return (curr_blk);
1084*7c478bd9Sstevel@tonic-gate }
1085*7c478bd9Sstevel@tonic-gate
1086*7c478bd9Sstevel@tonic-gate /*
1087*7c478bd9Sstevel@tonic-gate * s1394_tree_search()
1088*7c478bd9Sstevel@tonic-gate * is a "helper" function for s1394_used_tree_search(). It implements a
1089*7c478bd9Sstevel@tonic-gate * typical binary tree search with the address as the search key.
1090*7c478bd9Sstevel@tonic-gate */
1091*7c478bd9Sstevel@tonic-gate static s1394_addr_space_blk_t *
s1394_tree_search(s1394_addr_space_blk_t * x,uint64_t address)1092*7c478bd9Sstevel@tonic-gate s1394_tree_search(s1394_addr_space_blk_t *x, uint64_t address)
1093*7c478bd9Sstevel@tonic-gate {
1094*7c478bd9Sstevel@tonic-gate while (x != NULL) {
1095*7c478bd9Sstevel@tonic-gate if (x->addr_lo > address)
1096*7c478bd9Sstevel@tonic-gate x = x->asb_left;
1097*7c478bd9Sstevel@tonic-gate else if (x->addr_hi < address)
1098*7c478bd9Sstevel@tonic-gate x = x->asb_right;
1099*7c478bd9Sstevel@tonic-gate else
1100*7c478bd9Sstevel@tonic-gate break;
1101*7c478bd9Sstevel@tonic-gate }
1102*7c478bd9Sstevel@tonic-gate
1103*7c478bd9Sstevel@tonic-gate return (x);
1104*7c478bd9Sstevel@tonic-gate }
1105*7c478bd9Sstevel@tonic-gate
1106*7c478bd9Sstevel@tonic-gate /*
1107*7c478bd9Sstevel@tonic-gate * s1394_used_tree_delete()
1108*7c478bd9Sstevel@tonic-gate * is used to remove an address block from the used tree. This is
1109*7c478bd9Sstevel@tonic-gate * necessary when address spaces are freed. The removal is accomplished
1110*7c478bd9Sstevel@tonic-gate * in two steps, the removal done by this function and the cleanup done
1111*7c478bd9Sstevel@tonic-gate * by s1394_used_tree_delete_fixup().
1112*7c478bd9Sstevel@tonic-gate */
1113*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *
s1394_used_tree_delete(s1394_hal_t * hal,s1394_addr_space_blk_t * z)1114*7c478bd9Sstevel@tonic-gate s1394_used_tree_delete(s1394_hal_t *hal, s1394_addr_space_blk_t *z)
1115*7c478bd9Sstevel@tonic-gate {
1116*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *y;
1117*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *x;
1118*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *w;
1119*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *p;
1120*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t **root;
1121*7c478bd9Sstevel@tonic-gate int old_color;
1122*7c478bd9Sstevel@tonic-gate int side_of_x;
1123*7c478bd9Sstevel@tonic-gate
1124*7c478bd9Sstevel@tonic-gate /* Lock the "used" tree */
1125*7c478bd9Sstevel@tonic-gate mutex_enter(&hal->addr_space_used_mutex);
1126*7c478bd9Sstevel@tonic-gate
1127*7c478bd9Sstevel@tonic-gate /* Get the head of the "used" tree */
1128*7c478bd9Sstevel@tonic-gate root = &hal->addr_space_used_tree;
1129*7c478bd9Sstevel@tonic-gate
1130*7c478bd9Sstevel@tonic-gate if ((z->asb_left == NULL) || (z->asb_right == NULL))
1131*7c478bd9Sstevel@tonic-gate y = z;
1132*7c478bd9Sstevel@tonic-gate else
1133*7c478bd9Sstevel@tonic-gate y = s1394_tree_successor(z);
1134*7c478bd9Sstevel@tonic-gate
1135*7c478bd9Sstevel@tonic-gate if (y->asb_parent == z)
1136*7c478bd9Sstevel@tonic-gate p = y;
1137*7c478bd9Sstevel@tonic-gate else
1138*7c478bd9Sstevel@tonic-gate p = y->asb_parent;
1139*7c478bd9Sstevel@tonic-gate
1140*7c478bd9Sstevel@tonic-gate if (y->asb_left != NULL) {
1141*7c478bd9Sstevel@tonic-gate x = y->asb_left;
1142*7c478bd9Sstevel@tonic-gate if ((y != *root) && (y == y->asb_parent->asb_left)) {
1143*7c478bd9Sstevel@tonic-gate w = y->asb_parent->asb_right;
1144*7c478bd9Sstevel@tonic-gate side_of_x = LEFT;
1145*7c478bd9Sstevel@tonic-gate }
1146*7c478bd9Sstevel@tonic-gate
1147*7c478bd9Sstevel@tonic-gate if ((y != *root) && (y == y->asb_parent->asb_right)) {
1148*7c478bd9Sstevel@tonic-gate w = y->asb_parent->asb_left;
1149*7c478bd9Sstevel@tonic-gate side_of_x = RIGHT;
1150*7c478bd9Sstevel@tonic-gate }
1151*7c478bd9Sstevel@tonic-gate
1152*7c478bd9Sstevel@tonic-gate } else {
1153*7c478bd9Sstevel@tonic-gate x = y->asb_right;
1154*7c478bd9Sstevel@tonic-gate if ((y != *root) && (y == y->asb_parent->asb_left)) {
1155*7c478bd9Sstevel@tonic-gate w = y->asb_parent->asb_right;
1156*7c478bd9Sstevel@tonic-gate side_of_x = LEFT;
1157*7c478bd9Sstevel@tonic-gate }
1158*7c478bd9Sstevel@tonic-gate
1159*7c478bd9Sstevel@tonic-gate if ((y != *root) && (y == y->asb_parent->asb_right)) {
1160*7c478bd9Sstevel@tonic-gate w = y->asb_parent->asb_left;
1161*7c478bd9Sstevel@tonic-gate side_of_x = RIGHT;
1162*7c478bd9Sstevel@tonic-gate }
1163*7c478bd9Sstevel@tonic-gate
1164*7c478bd9Sstevel@tonic-gate }
1165*7c478bd9Sstevel@tonic-gate
1166*7c478bd9Sstevel@tonic-gate if (x != NULL)
1167*7c478bd9Sstevel@tonic-gate x->asb_parent = y->asb_parent;
1168*7c478bd9Sstevel@tonic-gate
1169*7c478bd9Sstevel@tonic-gate if (y->asb_parent == NULL)
1170*7c478bd9Sstevel@tonic-gate *root = x;
1171*7c478bd9Sstevel@tonic-gate else if (y == y->asb_parent->asb_left)
1172*7c478bd9Sstevel@tonic-gate y->asb_parent->asb_left = x;
1173*7c478bd9Sstevel@tonic-gate else
1174*7c478bd9Sstevel@tonic-gate y->asb_parent->asb_right = x;
1175*7c478bd9Sstevel@tonic-gate
1176*7c478bd9Sstevel@tonic-gate old_color = y->asb_color;
1177*7c478bd9Sstevel@tonic-gate
1178*7c478bd9Sstevel@tonic-gate /* Substitute the y-node for the z-node (deleted) */
1179*7c478bd9Sstevel@tonic-gate if (y != z) {
1180*7c478bd9Sstevel@tonic-gate y->asb_color = z->asb_color;
1181*7c478bd9Sstevel@tonic-gate y->asb_parent = z->asb_parent;
1182*7c478bd9Sstevel@tonic-gate if (z->asb_parent != NULL) {
1183*7c478bd9Sstevel@tonic-gate if (z->asb_parent->asb_left == z)
1184*7c478bd9Sstevel@tonic-gate z->asb_parent->asb_left = y;
1185*7c478bd9Sstevel@tonic-gate if (z->asb_parent->asb_right == z)
1186*7c478bd9Sstevel@tonic-gate z->asb_parent->asb_right = y;
1187*7c478bd9Sstevel@tonic-gate }
1188*7c478bd9Sstevel@tonic-gate
1189*7c478bd9Sstevel@tonic-gate y->asb_left = z->asb_left;
1190*7c478bd9Sstevel@tonic-gate if (z->asb_left != NULL)
1191*7c478bd9Sstevel@tonic-gate z->asb_left->asb_parent = y;
1192*7c478bd9Sstevel@tonic-gate y->asb_right = z->asb_right;
1193*7c478bd9Sstevel@tonic-gate if (z->asb_right != NULL)
1194*7c478bd9Sstevel@tonic-gate z->asb_right->asb_parent = y;
1195*7c478bd9Sstevel@tonic-gate
1196*7c478bd9Sstevel@tonic-gate if (z == *root)
1197*7c478bd9Sstevel@tonic-gate *root = y;
1198*7c478bd9Sstevel@tonic-gate }
1199*7c478bd9Sstevel@tonic-gate
1200*7c478bd9Sstevel@tonic-gate z->asb_parent = NULL;
1201*7c478bd9Sstevel@tonic-gate z->asb_right = NULL;
1202*7c478bd9Sstevel@tonic-gate z->asb_left = NULL;
1203*7c478bd9Sstevel@tonic-gate
1204*7c478bd9Sstevel@tonic-gate if (old_color == BLACK)
1205*7c478bd9Sstevel@tonic-gate s1394_used_tree_delete_fixup(root, p, x, w, side_of_x);
1206*7c478bd9Sstevel@tonic-gate
1207*7c478bd9Sstevel@tonic-gate /* Unlock the "used" tree */
1208*7c478bd9Sstevel@tonic-gate mutex_exit(&hal->addr_space_used_mutex);
1209*7c478bd9Sstevel@tonic-gate
1210*7c478bd9Sstevel@tonic-gate return (z);
1211*7c478bd9Sstevel@tonic-gate }
1212*7c478bd9Sstevel@tonic-gate
1213*7c478bd9Sstevel@tonic-gate /*
1214*7c478bd9Sstevel@tonic-gate * s1394_used_tree_delete_fixup()
1215*7c478bd9Sstevel@tonic-gate * is the "helper" function for s1394_used_tree_delete(). It is used to
1216*7c478bd9Sstevel@tonic-gate * cleanup/enforce the red-black coloring in the tree.
1217*7c478bd9Sstevel@tonic-gate */
1218*7c478bd9Sstevel@tonic-gate static void
s1394_used_tree_delete_fixup(s1394_addr_space_blk_t ** root,s1394_addr_space_blk_t * p,s1394_addr_space_blk_t * x,s1394_addr_space_blk_t * w,int side_of_x)1219*7c478bd9Sstevel@tonic-gate s1394_used_tree_delete_fixup(s1394_addr_space_blk_t **root,
1220*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *p, s1394_addr_space_blk_t *x,
1221*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *w, int side_of_x)
1222*7c478bd9Sstevel@tonic-gate {
1223*7c478bd9Sstevel@tonic-gate boolean_t first_time;
1224*7c478bd9Sstevel@tonic-gate
1225*7c478bd9Sstevel@tonic-gate first_time = B_TRUE;
1226*7c478bd9Sstevel@tonic-gate while ((x != *root) && ((x == NULL) || (x->asb_color == BLACK))) {
1227*7c478bd9Sstevel@tonic-gate if (((first_time == B_TRUE) && (side_of_x == LEFT)) ||
1228*7c478bd9Sstevel@tonic-gate ((first_time == B_FALSE) && (x == p->asb_left))) {
1229*7c478bd9Sstevel@tonic-gate
1230*7c478bd9Sstevel@tonic-gate if (first_time != B_TRUE)
1231*7c478bd9Sstevel@tonic-gate w = p->asb_right;
1232*7c478bd9Sstevel@tonic-gate
1233*7c478bd9Sstevel@tonic-gate if ((w != NULL) && (w->asb_color == RED)) {
1234*7c478bd9Sstevel@tonic-gate w->asb_color = BLACK;
1235*7c478bd9Sstevel@tonic-gate p->asb_color = RED;
1236*7c478bd9Sstevel@tonic-gate s1394_left_rotate(root, p);
1237*7c478bd9Sstevel@tonic-gate w = p->asb_right;
1238*7c478bd9Sstevel@tonic-gate }
1239*7c478bd9Sstevel@tonic-gate
1240*7c478bd9Sstevel@tonic-gate if (w == NULL) {
1241*7c478bd9Sstevel@tonic-gate x = p;
1242*7c478bd9Sstevel@tonic-gate p = p->asb_parent;
1243*7c478bd9Sstevel@tonic-gate first_time = B_FALSE;
1244*7c478bd9Sstevel@tonic-gate
1245*7c478bd9Sstevel@tonic-gate } else if (((w->asb_left == NULL) ||
1246*7c478bd9Sstevel@tonic-gate (w->asb_left->asb_color == BLACK)) &&
1247*7c478bd9Sstevel@tonic-gate ((w->asb_right == NULL) ||
1248*7c478bd9Sstevel@tonic-gate (w->asb_right->asb_color == BLACK))) {
1249*7c478bd9Sstevel@tonic-gate w->asb_color = RED;
1250*7c478bd9Sstevel@tonic-gate x = p;
1251*7c478bd9Sstevel@tonic-gate p = p->asb_parent;
1252*7c478bd9Sstevel@tonic-gate first_time = B_FALSE;
1253*7c478bd9Sstevel@tonic-gate
1254*7c478bd9Sstevel@tonic-gate } else {
1255*7c478bd9Sstevel@tonic-gate if ((w->asb_right == NULL) ||
1256*7c478bd9Sstevel@tonic-gate (w->asb_right->asb_color == BLACK)) {
1257*7c478bd9Sstevel@tonic-gate w->asb_left->asb_color = BLACK;
1258*7c478bd9Sstevel@tonic-gate w->asb_color = RED;
1259*7c478bd9Sstevel@tonic-gate s1394_right_rotate(root, w);
1260*7c478bd9Sstevel@tonic-gate w = p->asb_right;
1261*7c478bd9Sstevel@tonic-gate }
1262*7c478bd9Sstevel@tonic-gate
1263*7c478bd9Sstevel@tonic-gate w->asb_color = p->asb_color;
1264*7c478bd9Sstevel@tonic-gate p->asb_color = BLACK;
1265*7c478bd9Sstevel@tonic-gate if (w->asb_right != NULL)
1266*7c478bd9Sstevel@tonic-gate w->asb_right->asb_color = BLACK;
1267*7c478bd9Sstevel@tonic-gate s1394_left_rotate(root, p);
1268*7c478bd9Sstevel@tonic-gate x = *root;
1269*7c478bd9Sstevel@tonic-gate first_time = B_FALSE;
1270*7c478bd9Sstevel@tonic-gate }
1271*7c478bd9Sstevel@tonic-gate
1272*7c478bd9Sstevel@tonic-gate } else {
1273*7c478bd9Sstevel@tonic-gate if (first_time == B_FALSE)
1274*7c478bd9Sstevel@tonic-gate w = p->asb_left;
1275*7c478bd9Sstevel@tonic-gate
1276*7c478bd9Sstevel@tonic-gate if ((w != NULL) && (w->asb_color == RED)) {
1277*7c478bd9Sstevel@tonic-gate w->asb_color = BLACK;
1278*7c478bd9Sstevel@tonic-gate p->asb_color = RED;
1279*7c478bd9Sstevel@tonic-gate s1394_right_rotate(root, p);
1280*7c478bd9Sstevel@tonic-gate w = p->asb_left;
1281*7c478bd9Sstevel@tonic-gate }
1282*7c478bd9Sstevel@tonic-gate
1283*7c478bd9Sstevel@tonic-gate if (w == NULL) {
1284*7c478bd9Sstevel@tonic-gate x = p;
1285*7c478bd9Sstevel@tonic-gate p = p->asb_parent;
1286*7c478bd9Sstevel@tonic-gate first_time = B_FALSE;
1287*7c478bd9Sstevel@tonic-gate
1288*7c478bd9Sstevel@tonic-gate } else if (((w->asb_left == NULL) ||
1289*7c478bd9Sstevel@tonic-gate (w->asb_left->asb_color == BLACK)) &&
1290*7c478bd9Sstevel@tonic-gate ((w->asb_right == NULL) ||
1291*7c478bd9Sstevel@tonic-gate (w->asb_right->asb_color == BLACK))) {
1292*7c478bd9Sstevel@tonic-gate w->asb_color = RED;
1293*7c478bd9Sstevel@tonic-gate x = p;
1294*7c478bd9Sstevel@tonic-gate p = p->asb_parent;
1295*7c478bd9Sstevel@tonic-gate first_time = B_FALSE;
1296*7c478bd9Sstevel@tonic-gate
1297*7c478bd9Sstevel@tonic-gate } else {
1298*7c478bd9Sstevel@tonic-gate if ((w->asb_left == NULL) ||
1299*7c478bd9Sstevel@tonic-gate (w->asb_left->asb_color == BLACK)) {
1300*7c478bd9Sstevel@tonic-gate
1301*7c478bd9Sstevel@tonic-gate w->asb_right->asb_color = BLACK;
1302*7c478bd9Sstevel@tonic-gate w->asb_color = RED;
1303*7c478bd9Sstevel@tonic-gate s1394_left_rotate(root, w);
1304*7c478bd9Sstevel@tonic-gate w = p->asb_left;
1305*7c478bd9Sstevel@tonic-gate }
1306*7c478bd9Sstevel@tonic-gate
1307*7c478bd9Sstevel@tonic-gate w->asb_color = p->asb_color;
1308*7c478bd9Sstevel@tonic-gate p->asb_color = BLACK;
1309*7c478bd9Sstevel@tonic-gate if (w->asb_left != NULL)
1310*7c478bd9Sstevel@tonic-gate w->asb_left->asb_color = BLACK;
1311*7c478bd9Sstevel@tonic-gate s1394_right_rotate(root, p);
1312*7c478bd9Sstevel@tonic-gate x = *root;
1313*7c478bd9Sstevel@tonic-gate first_time = B_FALSE;
1314*7c478bd9Sstevel@tonic-gate }
1315*7c478bd9Sstevel@tonic-gate }
1316*7c478bd9Sstevel@tonic-gate }
1317*7c478bd9Sstevel@tonic-gate if (x != NULL)
1318*7c478bd9Sstevel@tonic-gate x->asb_color = BLACK;
1319*7c478bd9Sstevel@tonic-gate }
1320*7c478bd9Sstevel@tonic-gate
1321*7c478bd9Sstevel@tonic-gate /*
1322*7c478bd9Sstevel@tonic-gate * s1394_left_rotate()
1323*7c478bd9Sstevel@tonic-gate * is necessary with a red-black tree to help maintain the coloring in the
1324*7c478bd9Sstevel@tonic-gate * tree as items are inserted and removed. Its operation, the opposite of
1325*7c478bd9Sstevel@tonic-gate * s1394_right_rotate(), is a fundamental operation on the red-black tree.
1326*7c478bd9Sstevel@tonic-gate */
1327*7c478bd9Sstevel@tonic-gate static void
s1394_left_rotate(s1394_addr_space_blk_t ** root,s1394_addr_space_blk_t * x)1328*7c478bd9Sstevel@tonic-gate s1394_left_rotate(s1394_addr_space_blk_t **root, s1394_addr_space_blk_t *x)
1329*7c478bd9Sstevel@tonic-gate {
1330*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *y;
1331*7c478bd9Sstevel@tonic-gate
1332*7c478bd9Sstevel@tonic-gate y = x->asb_right;
1333*7c478bd9Sstevel@tonic-gate x->asb_right = y->asb_left;
1334*7c478bd9Sstevel@tonic-gate
1335*7c478bd9Sstevel@tonic-gate if (y->asb_left != NULL)
1336*7c478bd9Sstevel@tonic-gate y->asb_left->asb_parent = x;
1337*7c478bd9Sstevel@tonic-gate
1338*7c478bd9Sstevel@tonic-gate y->asb_parent = x->asb_parent;
1339*7c478bd9Sstevel@tonic-gate if (x->asb_parent == NULL)
1340*7c478bd9Sstevel@tonic-gate *root = y;
1341*7c478bd9Sstevel@tonic-gate else if (x == x->asb_parent->asb_left)
1342*7c478bd9Sstevel@tonic-gate x->asb_parent->asb_left = y;
1343*7c478bd9Sstevel@tonic-gate else
1344*7c478bd9Sstevel@tonic-gate x->asb_parent->asb_right = y;
1345*7c478bd9Sstevel@tonic-gate
1346*7c478bd9Sstevel@tonic-gate y->asb_left = x;
1347*7c478bd9Sstevel@tonic-gate x->asb_parent = y;
1348*7c478bd9Sstevel@tonic-gate }
1349*7c478bd9Sstevel@tonic-gate
1350*7c478bd9Sstevel@tonic-gate /*
1351*7c478bd9Sstevel@tonic-gate * s1394_right_rotate()
1352*7c478bd9Sstevel@tonic-gate * is necessary with a red-black tree to help maintain the coloring in the
1353*7c478bd9Sstevel@tonic-gate * tree as items are inserted and removed. Its operation, the opposite of
1354*7c478bd9Sstevel@tonic-gate * s1394_left_rotate(), is a fundamental operation on the red-black tree.
1355*7c478bd9Sstevel@tonic-gate */
1356*7c478bd9Sstevel@tonic-gate static void
s1394_right_rotate(s1394_addr_space_blk_t ** root,s1394_addr_space_blk_t * x)1357*7c478bd9Sstevel@tonic-gate s1394_right_rotate(s1394_addr_space_blk_t **root, s1394_addr_space_blk_t *x)
1358*7c478bd9Sstevel@tonic-gate {
1359*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *y;
1360*7c478bd9Sstevel@tonic-gate
1361*7c478bd9Sstevel@tonic-gate y = x->asb_left;
1362*7c478bd9Sstevel@tonic-gate x->asb_left = y->asb_right;
1363*7c478bd9Sstevel@tonic-gate
1364*7c478bd9Sstevel@tonic-gate if (y->asb_right != NULL)
1365*7c478bd9Sstevel@tonic-gate y->asb_right->asb_parent = x;
1366*7c478bd9Sstevel@tonic-gate
1367*7c478bd9Sstevel@tonic-gate y->asb_parent = x->asb_parent;
1368*7c478bd9Sstevel@tonic-gate if (x->asb_parent == NULL)
1369*7c478bd9Sstevel@tonic-gate *root = y;
1370*7c478bd9Sstevel@tonic-gate else if (x == x->asb_parent->asb_right)
1371*7c478bd9Sstevel@tonic-gate x->asb_parent->asb_right = y;
1372*7c478bd9Sstevel@tonic-gate else
1373*7c478bd9Sstevel@tonic-gate x->asb_parent->asb_left = y;
1374*7c478bd9Sstevel@tonic-gate
1375*7c478bd9Sstevel@tonic-gate y->asb_right = x;
1376*7c478bd9Sstevel@tonic-gate x->asb_parent = y;
1377*7c478bd9Sstevel@tonic-gate }
1378*7c478bd9Sstevel@tonic-gate
1379*7c478bd9Sstevel@tonic-gate /*
1380*7c478bd9Sstevel@tonic-gate * s1394_tree_minimum()
1381*7c478bd9Sstevel@tonic-gate * is used to find the smallest key in a binary tree.
1382*7c478bd9Sstevel@tonic-gate */
1383*7c478bd9Sstevel@tonic-gate static s1394_addr_space_blk_t *
s1394_tree_minimum(s1394_addr_space_blk_t * x)1384*7c478bd9Sstevel@tonic-gate s1394_tree_minimum(s1394_addr_space_blk_t *x)
1385*7c478bd9Sstevel@tonic-gate {
1386*7c478bd9Sstevel@tonic-gate while (x->asb_left != NULL)
1387*7c478bd9Sstevel@tonic-gate x = x->asb_left;
1388*7c478bd9Sstevel@tonic-gate
1389*7c478bd9Sstevel@tonic-gate return (x);
1390*7c478bd9Sstevel@tonic-gate }
1391*7c478bd9Sstevel@tonic-gate
1392*7c478bd9Sstevel@tonic-gate /*
1393*7c478bd9Sstevel@tonic-gate * s1394_tree_successor()
1394*7c478bd9Sstevel@tonic-gate * is used to find the next largest key is a binary tree, given a starting
1395*7c478bd9Sstevel@tonic-gate * point.
1396*7c478bd9Sstevel@tonic-gate */
1397*7c478bd9Sstevel@tonic-gate static s1394_addr_space_blk_t *
s1394_tree_successor(s1394_addr_space_blk_t * x)1398*7c478bd9Sstevel@tonic-gate s1394_tree_successor(s1394_addr_space_blk_t *x)
1399*7c478bd9Sstevel@tonic-gate {
1400*7c478bd9Sstevel@tonic-gate s1394_addr_space_blk_t *y;
1401*7c478bd9Sstevel@tonic-gate
1402*7c478bd9Sstevel@tonic-gate if (x->asb_right != NULL) {
1403*7c478bd9Sstevel@tonic-gate y = s1394_tree_minimum(x->asb_right);
1404*7c478bd9Sstevel@tonic-gate
1405*7c478bd9Sstevel@tonic-gate return (y);
1406*7c478bd9Sstevel@tonic-gate }
1407*7c478bd9Sstevel@tonic-gate
1408*7c478bd9Sstevel@tonic-gate y = x->asb_parent;
1409*7c478bd9Sstevel@tonic-gate while ((y != NULL) && (x == y->asb_right)) {
1410*7c478bd9Sstevel@tonic-gate x = y;
1411*7c478bd9Sstevel@tonic-gate y = y->asb_parent;
1412*7c478bd9Sstevel@tonic-gate }
1413*7c478bd9Sstevel@tonic-gate
1414*7c478bd9Sstevel@tonic-gate return (y);
1415*7c478bd9Sstevel@tonic-gate }
1416*7c478bd9Sstevel@tonic-gate
1417*7c478bd9Sstevel@tonic-gate /*
1418*7c478bd9Sstevel@tonic-gate * s1394_is_posted_write()
1419*7c478bd9Sstevel@tonic-gate * returns a B_TRUE if the given address is in the "posted write" range
1420*7c478bd9Sstevel@tonic-gate * of the given HAL's 1394 address space and B_FALSE if it isn't.
1421*7c478bd9Sstevel@tonic-gate */
1422*7c478bd9Sstevel@tonic-gate boolean_t
s1394_is_posted_write(s1394_hal_t * hal,uint64_t addr)1423*7c478bd9Sstevel@tonic-gate s1394_is_posted_write(s1394_hal_t *hal, uint64_t addr)
1424*7c478bd9Sstevel@tonic-gate {
1425*7c478bd9Sstevel@tonic-gate addr = addr & IEEE1394_ADDR_OFFSET_MASK;
1426*7c478bd9Sstevel@tonic-gate
1427*7c478bd9Sstevel@tonic-gate if ((addr >= hal->posted_write_addr_lo) &&
1428*7c478bd9Sstevel@tonic-gate (addr <= hal->posted_write_addr_hi))
1429*7c478bd9Sstevel@tonic-gate return (B_TRUE);
1430*7c478bd9Sstevel@tonic-gate else
1431*7c478bd9Sstevel@tonic-gate return (B_FALSE);
1432*7c478bd9Sstevel@tonic-gate }
1433*7c478bd9Sstevel@tonic-gate
1434*7c478bd9Sstevel@tonic-gate /*
1435*7c478bd9Sstevel@tonic-gate * s1394_is_physical_addr()
1436*7c478bd9Sstevel@tonic-gate * returns a B_TRUE if the given address is in the "physical" range of
1437*7c478bd9Sstevel@tonic-gate * the given HAL's 1394 address space and B_FALSE if it isn't.
1438*7c478bd9Sstevel@tonic-gate */
1439*7c478bd9Sstevel@tonic-gate boolean_t
s1394_is_physical_addr(s1394_hal_t * hal,uint64_t addr)1440*7c478bd9Sstevel@tonic-gate s1394_is_physical_addr(s1394_hal_t *hal, uint64_t addr)
1441*7c478bd9Sstevel@tonic-gate {
1442*7c478bd9Sstevel@tonic-gate addr = addr & IEEE1394_ADDR_OFFSET_MASK;
1443*7c478bd9Sstevel@tonic-gate
1444*7c478bd9Sstevel@tonic-gate if ((addr >= hal->physical_addr_lo) &&
1445*7c478bd9Sstevel@tonic-gate (addr <= hal->physical_addr_hi))
1446*7c478bd9Sstevel@tonic-gate return (B_TRUE);
1447*7c478bd9Sstevel@tonic-gate else
1448*7c478bd9Sstevel@tonic-gate return (B_FALSE);
1449*7c478bd9Sstevel@tonic-gate }
1450*7c478bd9Sstevel@tonic-gate
1451*7c478bd9Sstevel@tonic-gate /*
1452*7c478bd9Sstevel@tonic-gate * s1394_is_csr_addr()
1453*7c478bd9Sstevel@tonic-gate * returns a B_TRUE if the given address is in the "CSR" range of the
1454*7c478bd9Sstevel@tonic-gate * given HAL's 1394 address space and B_FALSE if it isn't.
1455*7c478bd9Sstevel@tonic-gate */
1456*7c478bd9Sstevel@tonic-gate boolean_t
s1394_is_csr_addr(s1394_hal_t * hal,uint64_t addr)1457*7c478bd9Sstevel@tonic-gate s1394_is_csr_addr(s1394_hal_t *hal, uint64_t addr)
1458*7c478bd9Sstevel@tonic-gate {
1459*7c478bd9Sstevel@tonic-gate addr = addr & IEEE1394_ADDR_OFFSET_MASK;
1460*7c478bd9Sstevel@tonic-gate
1461*7c478bd9Sstevel@tonic-gate if ((addr >= hal->csr_addr_lo) &&
1462*7c478bd9Sstevel@tonic-gate (addr <= hal->csr_addr_hi))
1463*7c478bd9Sstevel@tonic-gate return (B_TRUE);
1464*7c478bd9Sstevel@tonic-gate else
1465*7c478bd9Sstevel@tonic-gate return (B_FALSE);
1466*7c478bd9Sstevel@tonic-gate }
1467*7c478bd9Sstevel@tonic-gate
1468*7c478bd9Sstevel@tonic-gate /*
1469*7c478bd9Sstevel@tonic-gate * s1394_is_normal_addr()
1470*7c478bd9Sstevel@tonic-gate * returns a B_TRUE if the given address is in the "normal" range of
1471*7c478bd9Sstevel@tonic-gate * the given HAL's 1394 address space and B_FALSE if it isn't.
1472*7c478bd9Sstevel@tonic-gate */
1473*7c478bd9Sstevel@tonic-gate boolean_t
s1394_is_normal_addr(s1394_hal_t * hal,uint64_t addr)1474*7c478bd9Sstevel@tonic-gate s1394_is_normal_addr(s1394_hal_t *hal, uint64_t addr)
1475*7c478bd9Sstevel@tonic-gate {
1476*7c478bd9Sstevel@tonic-gate addr = addr & IEEE1394_ADDR_OFFSET_MASK;
1477*7c478bd9Sstevel@tonic-gate
1478*7c478bd9Sstevel@tonic-gate if ((addr >= hal->normal_addr_lo) &&
1479*7c478bd9Sstevel@tonic-gate (addr <= hal->normal_addr_hi))
1480*7c478bd9Sstevel@tonic-gate return (B_TRUE);
1481*7c478bd9Sstevel@tonic-gate else
1482*7c478bd9Sstevel@tonic-gate return (B_FALSE);
1483*7c478bd9Sstevel@tonic-gate }
1484