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