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