s1394_addr.c revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (the "License"). You may not use this file except in compliance
* with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 1999-2002 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* 1394 Address Space Routines
* of the 1394 address space
*/
#include <sys/tnf_probe.h>
s1394_addr_space_blk_t *w, int side_of_x);
/*
* s1394_request_addr_blk()
* is called when a target driver is requesting a block of 1394 Address
* Space of a particular type without regard for its exact location. It
* searches the free list for a block that's big enough and of the specified
* type, and it inserts it into the used tree.
*/
int
{
S1394_TNF_SL_ARREQ_STACK, "");
/* Lock the address space "free" list */
/* Unlock the address space "free" list */
"1394 address space - no more memory");
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
/* Does it fit exact? */
/* Take it out of the "free" list */
/* Unlock the address space "free" list */
/* Put it into the "used" tree */
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_SUCCESS);
} else {
/* Needs to be broken up */
/* Unlock the address space "free" list */
S1394_TNF_SL_ARREQ_ERROR, "");
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
/* Unlock the address space "free" list */
/* Put it into the "used" tree */
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_SUCCESS);
}
}
/*
* s1394_claim_addr_blk()
* is called when a target driver is requesting a block of 1394 Address
* Space with a specific address. If the block containing that address
* is not in the free list, or if the block is too small, then
* s1394_claim_addr_blk() returns failure. If the block is found,
* however, it is inserted into the used tree.
*/
int
{
S1394_TNF_SL_ARREQ_STACK, "");
/* Lock the address space "free" list */
/* Find the block in the "free" list */
/* If it wasn't found, it isn't free... */
/* Unlock the address space free list */
"1394 address space - address unavailable");
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
/* Does the request fit in the block? */
/* How does the requested range fit in the current range? */
/* Exact fit */
/* Take it out of the "free" list */
curr_blk);
/* Unlock the address space "free" list */
/* Put it into the "used" tree */
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_SUCCESS);
} else {
/* If space is reserved, must claim it all */
goto claim_error;
}
/* Front part of range */
kmem_zalloc(sizeof (s1394_addr_space_blk_t),
/* Unlock the addr space "free" list */
S1394_TNF_SL_ARREQ_ERROR, "");
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
/* Unlock the address space free list */
/* Put it into the "used" tree */
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_SUCCESS);
}
} else {
/* If space is reserved, must claim it all */
goto claim_error;
}
/* End part of range */
kmem_zalloc(sizeof (s1394_addr_space_blk_t),
/* Unlock the addr space "free" list */
S1394_TNF_SL_ARREQ_ERROR, "");
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
/* Unlock the address space free list */
/* Put it into the "used" tree */
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_SUCCESS);
} else {
/* If space is reserved, must claim it all */
goto claim_error;
}
/* Middle part of range */
kmem_zalloc(sizeof (s1394_addr_space_blk_t),
/* Unlock the addr space "free" list */
S1394_TNF_SL_ARREQ_ERROR, "");
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
kmem_zalloc(sizeof (s1394_addr_space_blk_t),
if (middle_blk == NULL) {
/* Unlock the addr space "free" list */
sizeof (s1394_addr_space_blk_t));
S1394_TNF_SL_ARREQ_ERROR, "");
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
/* Put part back into the "free" tree */
/* Unlock the address space free list */
/* Put it into the "used" tree */
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_SUCCESS);
}
}
}
/* Unlock the address space free list */
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
/*
* s1394_free_addr_blk()
* An opposite of s1394_claim_addr_blk(): takes the address block
* out of the "used" tree and puts it into the "free" tree.
*/
int
{
"");
/* Lock the address space "free" list */
/* Take it out of the "used" tree */
/* Unlock the address space "free" list */
"Can't free block not found in used list");
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
/* Put it into the "free" tree */
/* Unlock the address space "free" list */
"");
return (DDI_SUCCESS);
}
/*
* s1394_reserve_addr_blk()
* is similar to s1394_claim_addr_blk(), with the difference being that
* after the address block is found, it is marked as "reserved" rather
* than inserted into the used tree. Blocks of data that are marked
* "reserved" cannot be unintentionally allocated by a target, they must
* be specifically requested by specifying the exact address and size of
* the "reserved" block.
*/
int
{
S1394_TNF_SL_ARREQ_STACK, "");
/* Lock the address space "free" list */
/* Find the block in the "free" list */
/* If it wasn't found, it isn't free... */
/* Unlock the address space free list */
"1394 address space - address unavailable");
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
/* Is this block already reserved? */
/* Unlock the address space free list */
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
/* Does the request fit in the block? */
/* How does the requested range fit in the current range? */
/* Exact fit */
/* Unlock the address space "free" list */
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_SUCCESS);
} else {
/* Front part of range */
kmem_zalloc(sizeof (s1394_addr_space_blk_t),
/* Unlock the addr space "free" list */
S1394_TNF_SL_ARREQ_ERROR, "");
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
/* Put it back into the "free" list */
/* Unlock the address space free list */
"stacktrace 1394 s1394 arreq", "");
return (DDI_SUCCESS);
}
} else {
/* End part of range */
kmem_zalloc(sizeof (s1394_addr_space_blk_t),
/* Unlock the addr space "free" list */
S1394_TNF_SL_ARREQ_ERROR, "");
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
/* Put it back into the "free" list */
/* Unlock the address space free list */
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_SUCCESS);
} else {
/* Middle part of range */
kmem_zalloc(sizeof (s1394_addr_space_blk_t),
/* Unlock the addr space "free" list */
S1394_TNF_SL_ARREQ_ERROR, "");
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
kmem_zalloc(sizeof (s1394_addr_space_blk_t),
if (middle_blk == NULL) {
/* Unlock the addr space "free" list */
sizeof (s1394_addr_space_blk_t));
S1394_TNF_SL_ARREQ_ERROR, "");
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
/* Put pieces back into the "free" list */
/* Unlock the address space free list */
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_SUCCESS);
}
}
}
/* Unlock the address space free list */
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
/*
* s1394_init_addr_space()
* is called in the HAL attach routine - h1394_attach() - to setup the
* initial address space with the appropriate ranges, etc. At attach,
* the HAL specifies not only the type and bounds for each kind of 1394
* address space, but also a list of the blocks that are to be marked
* �reserved". Prior to marking the "reserved" ranges the local hosts
*/
int
{
int i;
int ret;
S1394_TNF_SL_ARREQ_STACK, "");
/* Setup Address Space */
/* Set address space to NULL (empty) */
/* Initialize the 1394 Address Space from HAL's description */
/* Lock the address space free list */
/* Default to NO posted write space */
/* Default to NO physical space */
/* Default to NO CSR space */
/* Default to NO normal space */
for (i = 0; i < num_blks; i++) {
continue;
KM_SLEEP);
case H1394_ADDR_POSTED_WRITE:
break;
case H1394_ADDR_NORMAL:
break;
case H1394_ADDR_CSR:
break;
case H1394_ADDR_PHYSICAL:
break;
default:
/* Unlock the address space free list */
"Invalid addr_type specified");
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
}
/* Unlock the address space free list */
/* Setup the necessary CSR space */
"Failed in s1394_setup_CSR_space()");
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
/* Handle all the HAL's reserved spaces */
for (i = 0; i < num_blks; i++) {
/* Can't reserve physical addresses */
"Attempted to reserve physical memory");
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
if (ret != DDI_SUCCESS) {
"Unable to reserve 1394 address");
S1394_TNF_SL_ARREQ_STACK, "");
return (DDI_FAILURE);
}
}
"");
return (DDI_SUCCESS);
}
/*
* s1394_destroy_addr_space()
* is necessary for h1394_detach(). It undoes all the work that
* s1394_init_addr_space() had setup and more. By pulling everything out
* of the used tree and free list and then freeing the structures,
* mutexes, and (if necessary) any backing store memory, the 1394 address
* space is completely dismantled.
*/
void
{
S1394_TNF_SL_ARREQ_STACK, "");
/* Lock the address space "used" tree */
} else {
/* Free any of our own backing store (if necessary) */
}
/* Free the s1394_addr_space_blk_t structure */
sizeof (s1394_addr_space_blk_t));
else
}
}
}
/* Unlock and destroy the address space "used" tree */
/* Lock the address space "free" list */
/* Free the s1394_addr_space_blk_t structure */
}
/* Unlock & destroy the address space "free" list */
S1394_TNF_SL_ARREQ_STACK, "");
}
/*
* s1394_free_list_insert()
* takes an s1394_addr_space_blk_t and inserts it into the free list in the
* appropriate place. It will concatenate into a single structure on the
* list any two neighboring blocks that can be joined (same type,
* consecutive addresses, neither is "reserved", etc.)
*/
void
{
S1394_TNF_SL_ARREQ_STACK, "");
/* Start at the head of the "free" list */
else
break;
/* Go to the next element in the list */
}
else
/* Can we merge with block to the left? */
}
/* Can we merge with block to the right? */
}
new_blk->addr_enable = 0;
S1394_TNF_SL_ARREQ_STACK, "");
}
/*
* s1394_free_list_search()
* attempts to find a block in the free list that contains the address
* specified. If none is found, it returns NULL.
*/
static s1394_addr_space_blk_t *
{
S1394_TNF_SL_ARREQ_STACK, "");
/* Start at the head of the list */
break;
else
}
S1394_TNF_SL_ARREQ_STACK, "");
return (curr_blk);
}
/*
* s1394_free_list_find()
* attempts to find a block in the free list that is of the specified
* type and size. It will ignore any blocks marked "reserved".
*/
static s1394_addr_space_blk_t *
{
"");
/* Start at the head of the list */
/* Find block of right "type" - that isn't "reserved" */
/* CSR allocs above IEEE1394_UCSR_RESERVED_BOUNDARY */
if ((type == T1394_ADDR_CSR) &&
continue;
}
break;
}
}
"");
return (curr_blk);
}
/*
* s1394_free_list_delete()
* will remove the block pointed to by del_blk from the free list.
* Typically, this is done so that it may be inserted into the used tree.
*/
static s1394_addr_space_blk_t *
{
S1394_TNF_SL_ARREQ_STACK, "");
else
S1394_TNF_SL_ARREQ_STACK, "");
return (del_blk);
}
/*
* s1394_used_tree_insert()
* is used to insert a 1394 address block that has been removed from the
* free list into the used tree. In the used tree it will be possible
* to search for a given address when an AR request arrives. Since the
* used tree is implemented as a red-black tree, the insertion is done
* with s1394_tree_insert() which does a simple binary tree insertion.
* It is then followed by cleanup of links and red-black coloring. This
* particulat implementation of the red-black tree is modified from code
* included in "Introduction to Algorithms" - Cormen, Leiserson, and Rivest,
* pp. 263 - 277.
*/
static void
{
S1394_TNF_SL_ARREQ_STACK, "");
/* Lock the "used" tree */
/* Get the head of the "used" tree */
s1394_tree_insert(root, x);
/* Is x's parent the "left-child" or the "right-child"? */
/* Left-child, set y to the sibling */
x = x->asb_parent->asb_parent;
} else {
if (x == x->asb_parent->asb_right) {
x = x->asb_parent;
s1394_left_rotate(root, x);
}
x->asb_parent->asb_parent);
}
} else {
/* Right-child, set y to the sibling */
x = x->asb_parent->asb_parent;
} else {
if (x == x->asb_parent->asb_left) {
x = x->asb_parent;
s1394_right_rotate(root, x);
}
x->asb_parent->asb_parent);
}
}
}
/* Unlock the "used" tree */
S1394_TNF_SL_ARREQ_STACK, "");
}
/*
* s1394_tree_insert()
* is a "helper" function for s1394_used_tree_insert(). It inserts an
* address block into a binary tree (red-black tree), and
* s1394_used_tree_insert() then cleans up the links and colorings, etc.
*/
static void
{
s1394_addr_space_blk_t *y = NULL;
s1394_addr_space_blk_t *x = *root;
"");
while (x != NULL) {
y = x;
x = x->asb_left;
else
x = x->asb_right;
}
z->asb_parent = y;
if (y == NULL)
*root = z;
y->asb_left = z;
else
y->asb_right = z;
"");
}
/*
* s1394_used_tree_search()
* is called when an AR request arrives. By calling s1394_tree_search()
* with the destination address, it can quickly find a block for that
* address (if one exists in the used tree) and return a pointer to it.
*/
{
S1394_TNF_SL_ARREQ_STACK, "");
/* Search the HAL's "used" tree for this address */
S1394_TNF_SL_ARREQ_STACK, "");
return (curr_blk);
}
/*
* s1394_tree_search()
* is a "helper" function for s1394_used_tree_search(). It implements a
* typical binary tree search with the address as the search key.
*/
static s1394_addr_space_blk_t *
{
"");
while (x != NULL) {
x = x->asb_left;
x = x->asb_right;
else
break;
}
"");
return (x);
}
/*
* s1394_used_tree_delete()
* is used to remove an address block from the used tree. This is
* necessary when address spaces are freed. The removal is accomplished
* in two steps, the removal done by this function and the cleanup done
* by s1394_used_tree_delete_fixup().
*/
{
int old_color;
int side_of_x;
S1394_TNF_SL_ARREQ_STACK, "");
/* Lock the "used" tree */
/* Get the head of the "used" tree */
y = z;
else
y = s1394_tree_successor(z);
if (y->asb_parent == z)
p = y;
else
p = y->asb_parent;
x = y->asb_left;
w = y->asb_parent->asb_right;
}
w = y->asb_parent->asb_left;
}
} else {
x = y->asb_right;
w = y->asb_parent->asb_right;
}
w = y->asb_parent->asb_left;
}
}
if (x != NULL)
x->asb_parent = y->asb_parent;
if (y->asb_parent == NULL)
*root = x;
else if (y == y->asb_parent->asb_left)
y->asb_parent->asb_left = x;
else
y->asb_parent->asb_right = x;
/* Substitute the y-node for the z-node (deleted) */
if (y != z) {
y->asb_parent = z->asb_parent;
if (z->asb_parent != NULL) {
if (z->asb_parent->asb_left == z)
z->asb_parent->asb_left = y;
if (z->asb_parent->asb_right == z)
z->asb_parent->asb_right = y;
}
z->asb_left->asb_parent = y;
z->asb_right->asb_parent = y;
if (z == *root)
*root = y;
}
z->asb_parent = NULL;
/* Unlock the "used" tree */
S1394_TNF_SL_ARREQ_STACK, "");
return (z);
}
/*
* s1394_used_tree_delete_fixup()
* is the "helper" function for s1394_used_tree_delete(). It is used to
*/
static void
s1394_addr_space_blk_t *w, int side_of_x)
{
S1394_TNF_SL_ARREQ_STACK, "");
first_time = B_TRUE;
if (first_time != B_TRUE)
w = p->asb_right;
s1394_left_rotate(root, p);
w = p->asb_right;
}
if (w == NULL) {
x = p;
p = p->asb_parent;
x = p;
p = p->asb_parent;
} else {
s1394_right_rotate(root, w);
w = p->asb_right;
}
s1394_left_rotate(root, p);
x = *root;
}
} else {
if (first_time == B_FALSE)
w = p->asb_left;
s1394_right_rotate(root, p);
w = p->asb_left;
}
if (w == NULL) {
x = p;
p = p->asb_parent;
x = p;
p = p->asb_parent;
} else {
s1394_left_rotate(root, w);
w = p->asb_left;
}
s1394_right_rotate(root, p);
x = *root;
}
}
}
if (x != NULL)
S1394_TNF_SL_ARREQ_STACK, "");
}
/*
* s1394_left_rotate()
* is necessary with a red-black tree to help maintain the coloring in the
* tree as items are inserted and removed. Its operation, the opposite of
* s1394_right_rotate(), is a fundamental operation on the red-black tree.
*/
static void
{
"");
y = x->asb_right;
y->asb_left->asb_parent = x;
y->asb_parent = x->asb_parent;
if (x->asb_parent == NULL)
*root = y;
else if (x == x->asb_parent->asb_left)
x->asb_parent->asb_left = y;
else
x->asb_parent->asb_right = y;
y->asb_left = x;
x->asb_parent = y;
"");
}
/*
* s1394_right_rotate()
* is necessary with a red-black tree to help maintain the coloring in the
* tree as items are inserted and removed. Its operation, the opposite of
* s1394_left_rotate(), is a fundamental operation on the red-black tree.
*/
static void
{
"");
y = x->asb_left;
y->asb_right->asb_parent = x;
y->asb_parent = x->asb_parent;
if (x->asb_parent == NULL)
*root = y;
else if (x == x->asb_parent->asb_right)
x->asb_parent->asb_right = y;
else
x->asb_parent->asb_left = y;
y->asb_right = x;
x->asb_parent = y;
"");
}
/*
* s1394_tree_minimum()
* is used to find the smallest key in a binary tree.
*/
static s1394_addr_space_blk_t *
{
"");
x = x->asb_left;
"");
return (x);
}
/*
* s1394_tree_successor()
* is used to find the next largest key is a binary tree, given a starting
* point.
*/
static s1394_addr_space_blk_t *
{
"");
y = s1394_tree_minimum(x->asb_right);
S1394_TNF_SL_ARREQ_STACK, "");
return (y);
}
y = x->asb_parent;
x = y;
y = y->asb_parent;
}
"");
return (y);
}
/*
* s1394_is_posted_write()
* returns a B_TRUE if the given address is in the "posted write" range
* of the given HAL's 1394 address space and B_FALSE if it isn't.
*/
{
return (B_TRUE);
else
return (B_FALSE);
}
/*
* s1394_is_physical_addr()
* returns a B_TRUE if the given address is in the "physical" range of
* the given HAL's 1394 address space and B_FALSE if it isn't.
*/
{
return (B_TRUE);
else
return (B_FALSE);
}
/*
* s1394_is_csr_addr()
* returns a B_TRUE if the given address is in the "CSR" range of the
* given HAL's 1394 address space and B_FALSE if it isn't.
*/
{
return (B_TRUE);
else
return (B_FALSE);
}
/*
* s1394_is_normal_addr()
* returns a B_TRUE if the given address is in the "normal" range of
* the given HAL's 1394 address space and B_FALSE if it isn't.
*/
{
return (B_TRUE);
else
return (B_FALSE);
}