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 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 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 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 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 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 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 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 * 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 * 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 * 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 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 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 * 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 * 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 * 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 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 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 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 * 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 * 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 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 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 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 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