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