?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
8815 mega_sas: variable set but not used
[unleashed.git] / usr / src / uts / common / io / 1394 / s1394_addr.c
blob4ff928bb14eb9a60a90571adfb022893d3369ec8
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 }
Unleashed OS