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