xref: /titanic_51/usr/src/uts/common/io/1394/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
 * or http://www.opensolaris.org/os/licensing.
 * 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"

/*
 * s1394_addr.c
 *    1394 Address Space Routines
 *    Implements all the routines necessary for alloc/free and lookup
 *    of the 1394 address space
 */

#include <sys/conf.h>
#include <sys/ddi.h>
#include <sys/sunddi.h>
#include <sys/types.h>
#include <sys/kmem.h>
#include <sys/tnf_probe.h>

#include <sys/1394/t1394.h>
#include <sys/1394/s1394.h>
#include <sys/1394/h1394.h>
#include <sys/1394/ieee1394.h>

static s1394_addr_space_blk_t *s1394_free_list_search(s1394_hal_t *hal,
    uint64_t addr);

static s1394_addr_space_blk_t *s1394_free_list_find(s1394_hal_t *hal,
    uint32_t type, uint32_t length);

static s1394_addr_space_blk_t *s1394_free_list_delete(s1394_hal_t *hal,
    s1394_addr_space_blk_t *del_blk);

static void s1394_used_tree_insert(s1394_hal_t *hal, s1394_addr_space_blk_t *x);

static void s1394_tree_insert(s1394_addr_space_blk_t **root,
    s1394_addr_space_blk_t *z);

static s1394_addr_space_blk_t *s1394_tree_search(s1394_addr_space_blk_t *x,
    uint64_t address);

static void s1394_used_tree_delete_fixup(s1394_addr_space_blk_t **root,
    s1394_addr_space_blk_t *p, s1394_addr_space_blk_t *x,
    s1394_addr_space_blk_t *w, int side_of_x);

static void s1394_left_rotate(s1394_addr_space_blk_t **root,
    s1394_addr_space_blk_t *x);

static void s1394_right_rotate(s1394_addr_space_blk_t **root,
    s1394_addr_space_blk_t *x);

static s1394_addr_space_blk_t *s1394_tree_minimum(s1394_addr_space_blk_t *x);

static s1394_addr_space_blk_t *s1394_tree_successor(s1394_addr_space_blk_t *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_request_addr_blk(s1394_hal_t *hal, t1394_alloc_addr_t *addr_allocp)
{
	s1394_addr_space_blk_t	*curr_blk;
	s1394_addr_space_blk_t	*new_blk;
	uint64_t		amount_free;

	TNF_PROBE_0_DEBUG(s1394_request_addr_blk_enter,
	    S1394_TNF_SL_ARREQ_STACK, "");

	ASSERT(hal != NULL);

	/* Lock the address space "free" list */
	mutex_enter(&hal->addr_space_free_mutex);

	curr_blk = s1394_free_list_find(hal, addr_allocp->aa_type,
	    addr_allocp->aa_length);
	if (curr_blk == NULL) {
		/* Unlock the address space "free" list */
		mutex_exit(&hal->addr_space_free_mutex);

		TNF_PROBE_1(s1394_request_addr_blk_error,
		    S1394_TNF_SL_ARREQ_ERROR, "", tnf_string, msg,
		    "1394 address space - no more memory");
		TNF_PROBE_0_DEBUG(s1394_request_addr_blk_exit,
		    S1394_TNF_SL_ARREQ_STACK, "");
		return (DDI_FAILURE);
	}

	amount_free = (curr_blk->addr_hi - curr_blk->addr_lo) + 1;
	/* Does it fit exact? */
	if (amount_free == addr_allocp->aa_length) {
		/* Take it out of the "free" list */
		curr_blk = s1394_free_list_delete(hal, curr_blk);

		/* Unlock the address space "free" list */
		mutex_exit(&hal->addr_space_free_mutex);

		curr_blk->addr_enable = addr_allocp->aa_enable;
		curr_blk->kmem_bufp = addr_allocp->aa_kmem_bufp;
		curr_blk->addr_arg = addr_allocp->aa_arg;
		curr_blk->addr_events = addr_allocp->aa_evts;

		addr_allocp->aa_address = curr_blk->addr_lo;
		addr_allocp->aa_hdl = (t1394_addr_handle_t)curr_blk;

		/* Put it into the "used" tree */
		s1394_used_tree_insert(hal, curr_blk);

		s1394_addr_alloc_kstat(hal, addr_allocp->aa_address);

		TNF_PROBE_0_DEBUG(s1394_request_addr_blk_exit,
		    S1394_TNF_SL_ARREQ_STACK, "");
		return (DDI_SUCCESS);

	} else {
		/* Needs to be broken up */
		new_blk = (s1394_addr_space_blk_t *)
		    kmem_zalloc(sizeof (s1394_addr_space_blk_t), KM_NOSLEEP);
		if (new_blk == NULL) {
			/* Unlock the address space "free" list */
			mutex_exit(&hal->addr_space_free_mutex);
			TNF_PROBE_0(s1394_request_addr_blk_error,
			    S1394_TNF_SL_ARREQ_ERROR, "");
			TNF_PROBE_0_DEBUG(s1394_request_addr_blk_exit,
			    S1394_TNF_SL_ARREQ_STACK, "");
			return (DDI_FAILURE);
		}

		new_blk->addr_lo = curr_blk->addr_lo;
		new_blk->addr_hi = curr_blk->addr_lo +
		    (addr_allocp->aa_length - 1);
		new_blk->addr_type = curr_blk->addr_type;
		new_blk->addr_enable = addr_allocp->aa_enable;
		new_blk->kmem_bufp = addr_allocp->aa_kmem_bufp;
		new_blk->addr_arg = addr_allocp->aa_arg;
		new_blk->addr_events = addr_allocp->aa_evts;

		curr_blk->addr_lo = new_blk->addr_hi + 1;

		addr_allocp->aa_address = new_blk->addr_lo;
		addr_allocp->aa_hdl = (t1394_addr_handle_t)new_blk;

		/* Unlock the address space "free" list */
		mutex_exit(&hal->addr_space_free_mutex);

		/* Put it into the "used" tree */
		s1394_used_tree_insert(hal, new_blk);

		s1394_addr_alloc_kstat(hal, addr_allocp->aa_address);

		TNF_PROBE_0_DEBUG(s1394_request_addr_blk_exit,
		    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_claim_addr_blk(s1394_hal_t *hal, t1394_alloc_addr_t *addr_allocp)
{
	s1394_addr_space_blk_t	*curr_blk;
	s1394_addr_space_blk_t	*new_blk;
	s1394_addr_space_blk_t	*middle_blk;
	uint64_t		upper_bound;

	TNF_PROBE_0_DEBUG(s1394_claim_addr_blk_enter,
	    S1394_TNF_SL_ARREQ_STACK, "");

	ASSERT(hal != NULL);

	/* Lock the address space "free" list */
	mutex_enter(&hal->addr_space_free_mutex);

	/* Find the block in the "free" list */
	curr_blk = s1394_free_list_search(hal, addr_allocp->aa_address);

	/* If it wasn't found, it isn't free... */
	if (curr_blk == NULL) {
		/* Unlock the address space free list */
		mutex_exit(&hal->addr_space_free_mutex);

		TNF_PROBE_1(s1394_claim_addr_blk_error,
		    S1394_TNF_SL_ARREQ_ERROR, "", tnf_string, msg,
		    "1394 address space - address unavailable");
		TNF_PROBE_0_DEBUG(s1394_claim_addr_blk_exit,
		    S1394_TNF_SL_ARREQ_STACK, "");
		return (DDI_FAILURE);
	}

	/* Does the request fit in the block? */
	upper_bound = (addr_allocp->aa_address + addr_allocp->aa_length) - 1;
	if ((upper_bound >= curr_blk->addr_lo) &&
	    (upper_bound <= curr_blk->addr_hi)) {

		/* How does the requested range fit in the current range? */
		if (addr_allocp->aa_address == curr_blk->addr_lo) {
			if (upper_bound == curr_blk->addr_hi) {
				/* Exact fit */

				/* Take it out of the "free" list */
				curr_blk = s1394_free_list_delete(hal,
				    curr_blk);

				/* Unlock the address space "free" list */
				mutex_exit(&hal->addr_space_free_mutex);

				curr_blk->addr_enable = addr_allocp->aa_enable;
				curr_blk->kmem_bufp = addr_allocp->aa_kmem_bufp;
				curr_blk->addr_arg = addr_allocp->aa_arg;
				curr_blk->addr_events = addr_allocp->aa_evts;

				addr_allocp->aa_hdl =
				    (t1394_addr_handle_t)curr_blk;

				/* Put it into the "used" tree */
				s1394_used_tree_insert(hal, curr_blk);

				s1394_addr_alloc_kstat(hal,
				    addr_allocp->aa_address);

				TNF_PROBE_0_DEBUG(s1394_claim_addr_blk_exit,
				    S1394_TNF_SL_ARREQ_STACK, "");
				return (DDI_SUCCESS);

			} else {
				/* If space is reserved, must claim it all */
				if (curr_blk->addr_reserved == ADDR_RESERVED) {
					goto claim_error;
				}

				/* Front part of range */
				new_blk = (s1394_addr_space_blk_t *)
				    kmem_zalloc(sizeof (s1394_addr_space_blk_t),
				    KM_NOSLEEP);
				if (new_blk == NULL) {
					/* Unlock the addr space "free" list */
					mutex_exit(&hal->addr_space_free_mutex);
					TNF_PROBE_0(s1394_claim_addr_blk_error,
					    S1394_TNF_SL_ARREQ_ERROR, "");
					TNF_PROBE_0_DEBUG(
					    s1394_claim_addr_blk_exit,
					    S1394_TNF_SL_ARREQ_STACK, "");
					return (DDI_FAILURE);
				}

				new_blk->addr_lo = curr_blk->addr_lo;
				new_blk->addr_hi = upper_bound;
				new_blk->addr_type = curr_blk->addr_type;
				new_blk->addr_enable = addr_allocp->aa_enable;
				new_blk->kmem_bufp = addr_allocp->aa_kmem_bufp;
				new_blk->addr_arg = addr_allocp->aa_arg;
				new_blk->addr_events = addr_allocp->aa_evts;

				curr_blk->addr_lo = new_blk->addr_hi + 1;

				addr_allocp->aa_hdl =
				    (t1394_addr_handle_t)new_blk;

				/* Unlock the address space free list */
				mutex_exit(&hal->addr_space_free_mutex);

				/* Put it into the "used" tree */
				s1394_used_tree_insert(hal, new_blk);

				s1394_addr_alloc_kstat(hal,
				    addr_allocp->aa_address);

				TNF_PROBE_0_DEBUG(s1394_claim_addr_blk_exit,
				    S1394_TNF_SL_ARREQ_STACK, "");
				return (DDI_SUCCESS);
			}

		} else {
			if (upper_bound == curr_blk->addr_hi) {
				/* If space is reserved, must claim it all */
				if (curr_blk->addr_reserved == ADDR_RESERVED) {
					goto claim_error;
				}

				/* End part of range */
				new_blk = (s1394_addr_space_blk_t *)
				    kmem_zalloc(sizeof (s1394_addr_space_blk_t),
				    KM_NOSLEEP);
				if (new_blk == NULL) {
					/* Unlock the addr space "free" list */
					mutex_exit(&hal->addr_space_free_mutex);
					TNF_PROBE_0(s1394_claim_addr_blk_error,
					    S1394_TNF_SL_ARREQ_ERROR, "");
					TNF_PROBE_0_DEBUG
					    (s1394_claim_addr_blk_exit,
					    S1394_TNF_SL_ARREQ_STACK, "");
					return (DDI_FAILURE);
				}

				new_blk->addr_lo = addr_allocp->aa_address;
				new_blk->addr_hi = upper_bound;
				new_blk->addr_type = curr_blk->addr_type;
				new_blk->addr_enable = addr_allocp->aa_enable;
				new_blk->kmem_bufp = addr_allocp->aa_kmem_bufp;
				new_blk->addr_arg = addr_allocp->aa_arg;
				new_blk->addr_events = addr_allocp->aa_evts;

				curr_blk->addr_hi = addr_allocp->aa_address - 1;

				addr_allocp->aa_hdl =
				    (t1394_addr_handle_t)new_blk;

				/* Unlock the address space free list */
				mutex_exit(&hal->addr_space_free_mutex);

				/* Put it into the "used" tree */
				s1394_used_tree_insert(hal, new_blk);

				s1394_addr_alloc_kstat(hal,
				    addr_allocp->aa_address);

				TNF_PROBE_0_DEBUG(s1394_claim_addr_blk_exit,
				    S1394_TNF_SL_ARREQ_STACK, "");
				return (DDI_SUCCESS);

			} else {
				/* If space is reserved, must claim it all */
				if (curr_blk->addr_reserved == ADDR_RESERVED) {
					goto claim_error;
				}

				/* Middle part of range */
				new_blk = (s1394_addr_space_blk_t *)
				    kmem_zalloc(sizeof (s1394_addr_space_blk_t),
				    KM_NOSLEEP);
				if (new_blk == NULL) {
					/* Unlock the addr space "free" list */
					mutex_exit(&hal->addr_space_free_mutex);
					TNF_PROBE_0(s1394_claim_addr_blk_error,
					    S1394_TNF_SL_ARREQ_ERROR, "");
					TNF_PROBE_0_DEBUG(
					    s1394_claim_addr_blk_exit,
					    S1394_TNF_SL_ARREQ_STACK, "");
					return (DDI_FAILURE);
				}

				middle_blk = (s1394_addr_space_blk_t *)
				    kmem_zalloc(sizeof (s1394_addr_space_blk_t),
				    KM_NOSLEEP);
				if (middle_blk == NULL) {
					/* Unlock the addr space "free" list */
					mutex_exit(&hal->addr_space_free_mutex);
					kmem_free(new_blk,
					    sizeof (s1394_addr_space_blk_t));
					TNF_PROBE_0(s1394_claim_addr_blk_error,
					    S1394_TNF_SL_ARREQ_ERROR, "");
					TNF_PROBE_0_DEBUG
					    (s1394_claim_addr_blk_exit,
					    S1394_TNF_SL_ARREQ_STACK, "");
					return (DDI_FAILURE);
				}

				middle_blk->addr_lo = addr_allocp->aa_address;
				middle_blk->addr_hi = upper_bound;
				new_blk->addr_lo = upper_bound + 1;
				new_blk->addr_hi = curr_blk->addr_hi;

				new_blk->addr_type = curr_blk->addr_type;

				middle_blk->addr_type = curr_blk->addr_type;
				middle_blk->addr_enable =
				    addr_allocp->aa_enable;
				middle_blk->kmem_bufp =
				    addr_allocp->aa_kmem_bufp;
				middle_blk->addr_arg = addr_allocp->aa_arg;
				middle_blk->addr_events = addr_allocp->aa_evts;

				curr_blk->addr_hi = addr_allocp->aa_address - 1;

				addr_allocp->aa_hdl =
				    (t1394_addr_handle_t)middle_blk;

				/* Put part back into the "free" tree */
				s1394_free_list_insert(hal, new_blk);

				/* Unlock the address space free list */
				mutex_exit(&hal->addr_space_free_mutex);

				/* Put it into the "used" tree */
				s1394_used_tree_insert(hal, middle_blk);

				s1394_addr_alloc_kstat(hal,
				    addr_allocp->aa_address);

				TNF_PROBE_0_DEBUG(s1394_claim_addr_blk_exit,
				    S1394_TNF_SL_ARREQ_STACK, "");
				return (DDI_SUCCESS);
			}
		}
	}

claim_error:
	/* Unlock the address space free list */
	mutex_exit(&hal->addr_space_free_mutex);

	TNF_PROBE_0_DEBUG(s1394_claim_addr_blk_exit,
	    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
s1394_free_addr_blk(s1394_hal_t *hal, s1394_addr_space_blk_t *blk)
{
	TNF_PROBE_0_DEBUG(s1394_free_addr_blk_enter, S1394_TNF_SL_ARREQ_STACK,
	    "");

	/* Lock the address space "free" list */
	mutex_enter(&hal->addr_space_free_mutex);

	/* Take it out of the "used" tree */
	blk = s1394_used_tree_delete(hal, blk);

	if (blk == NULL) {
		/* Unlock the address space "free" list */
		mutex_exit(&hal->addr_space_free_mutex);
		TNF_PROBE_1(s1394_free_addr_blk_error,
		    S1394_TNF_SL_ARREQ_ERROR, "", tnf_string, msg,
		    "Can't free block not found in used list");
		TNF_PROBE_0_DEBUG(s1394_free_addr_blk_exit,
		    S1394_TNF_SL_ARREQ_STACK, "");
		return (DDI_FAILURE);
	}

	/* Put it into the "free" tree */
	s1394_free_list_insert(hal, blk);

	/* Unlock the address space "free" list */
	mutex_exit(&hal->addr_space_free_mutex);

	TNF_PROBE_0_DEBUG(s1394_free_addr_blk_exit, S1394_TNF_SL_ARREQ_STACK,
	    "");
	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_reserve_addr_blk(s1394_hal_t *hal, t1394_alloc_addr_t *addr_allocp)
{
	s1394_addr_space_blk_t	*curr_blk;
	s1394_addr_space_blk_t	*new_blk;
	s1394_addr_space_blk_t	*middle_blk;
	uint64_t		upper_bound;

	TNF_PROBE_0_DEBUG(s1394_reserve_addr_blk_enter,
	    S1394_TNF_SL_ARREQ_STACK, "");

	ASSERT(hal != NULL);

	/* Lock the address space "free" list */
	mutex_enter(&hal->addr_space_free_mutex);

	/* Find the block in the "free" list */
	curr_blk = s1394_free_list_search(hal, addr_allocp->aa_address);
	/* If it wasn't found, it isn't free... */
	if (curr_blk == NULL) {
		/* Unlock the address space free list */
		mutex_exit(&hal->addr_space_free_mutex);

		TNF_PROBE_1(s1394_reserve_addr_blk_error,
		    S1394_TNF_SL_ARREQ_ERROR, "", tnf_string, msg,
		    "1394 address space - address unavailable");
		TNF_PROBE_0_DEBUG(s1394_reserve_addr_blk_exit,
		    S1394_TNF_SL_ARREQ_STACK, "");
		return (DDI_FAILURE);
	}

	/* Is this block already reserved? */
	if (curr_blk->addr_reserved == ADDR_RESERVED) {
		/* Unlock the address space free list */
		mutex_exit(&hal->addr_space_free_mutex);

		TNF_PROBE_0_DEBUG(s1394_reserve_addr_blk_exit,
		    S1394_TNF_SL_ARREQ_STACK, "");
		return (DDI_FAILURE);
	}

	/* Does the request fit in the block? */
	upper_bound = (addr_allocp->aa_address + addr_allocp->aa_length) - 1;
	if ((upper_bound >= curr_blk->addr_lo) &&
	    (upper_bound <= curr_blk->addr_hi)) {

		/* How does the requested range fit in the current range? */
		if (addr_allocp->aa_address == curr_blk->addr_lo) {
			if (upper_bound == curr_blk->addr_hi) {
				/* Exact fit */
				curr_blk->addr_reserved = ADDR_RESERVED;

				/* Unlock the address space "free" list */
				mutex_exit(&hal->addr_space_free_mutex);

				TNF_PROBE_0_DEBUG(s1394_reserve_addr_blk_exit,
				    S1394_TNF_SL_ARREQ_STACK, "");
				return (DDI_SUCCESS);

			} else {
				/* Front part of range */
				new_blk = (s1394_addr_space_blk_t *)
				    kmem_zalloc(sizeof (s1394_addr_space_blk_t),
				    KM_NOSLEEP);
				if (new_blk == NULL) {
					/* Unlock the addr space "free" list */
					mutex_exit(&hal->addr_space_free_mutex);
					TNF_PROBE_0(
					    s1394_reserve_addr_blk_error,
					    S1394_TNF_SL_ARREQ_ERROR, "");
					TNF_PROBE_0_DEBUG(
					    s1394_reserve_addr_blk_exit,
					    S1394_TNF_SL_ARREQ_STACK, "");
					return (DDI_FAILURE);
				}

				new_blk->addr_lo = curr_blk->addr_lo;
				new_blk->addr_hi = upper_bound;
				new_blk->addr_type = curr_blk->addr_type;
				new_blk->addr_reserved = ADDR_RESERVED;

				curr_blk->addr_lo = new_blk->addr_hi + 1;

				/* Put it back into the "free" list */
				s1394_free_list_insert(hal, new_blk);

				/* Unlock the address space free list */
				mutex_exit(&hal->addr_space_free_mutex);

				TNF_PROBE_0_DEBUG(s1394_reserve_addr_blk_exit,
				    "stacktrace 1394 s1394 arreq", "");
				return (DDI_SUCCESS);
			}

		} else {
			if (upper_bound == curr_blk->addr_hi) {
				/* End part of range */
				new_blk = (s1394_addr_space_blk_t *)
				    kmem_zalloc(sizeof (s1394_addr_space_blk_t),
				    KM_NOSLEEP);
				if (new_blk == NULL) {
					/* Unlock the addr space "free" list */
					mutex_exit(&hal->addr_space_free_mutex);
					TNF_PROBE_0(
					    s1394_reserve_addr_blk_error,
					    S1394_TNF_SL_ARREQ_ERROR, "");
					TNF_PROBE_0_DEBUG(
					    s1394_reserve_addr_blk_exit,
					    S1394_TNF_SL_ARREQ_STACK, "");
					return (DDI_FAILURE);
				}

				new_blk->addr_lo = addr_allocp->aa_address;
				new_blk->addr_hi = upper_bound;
				new_blk->addr_type = curr_blk->addr_type;
				new_blk->addr_reserved = ADDR_RESERVED;

				curr_blk->addr_hi = addr_allocp->aa_address - 1;

				/* Put it back into the "free" list */
				s1394_free_list_insert(hal, new_blk);

				/* Unlock the address space free list */
				mutex_exit(&hal->addr_space_free_mutex);

				TNF_PROBE_0_DEBUG(s1394_reserve_addr_blk_exit,
				    S1394_TNF_SL_ARREQ_STACK, "");
				return (DDI_SUCCESS);

			} else {
				/* Middle part of range */
				new_blk = (s1394_addr_space_blk_t *)
				    kmem_zalloc(sizeof (s1394_addr_space_blk_t),
				    KM_NOSLEEP);
				if (new_blk == NULL) {
					/* Unlock the addr space "free" list */
					mutex_exit(&hal->addr_space_free_mutex);
					TNF_PROBE_0(
					    s1394_reserve_addr_blk_error,
					    S1394_TNF_SL_ARREQ_ERROR, "");
					TNF_PROBE_0_DEBUG(
					    s1394_reserve_addr_blk_exit,
					    S1394_TNF_SL_ARREQ_STACK, "");
					return (DDI_FAILURE);
				}

				middle_blk = (s1394_addr_space_blk_t *)
				    kmem_zalloc(sizeof (s1394_addr_space_blk_t),
				    KM_NOSLEEP);
				if (middle_blk == NULL) {
					/* Unlock the addr space "free" list */
					mutex_exit(&hal->addr_space_free_mutex);
					kmem_free(new_blk,
					    sizeof (s1394_addr_space_blk_t));
					TNF_PROBE_0(
					    s1394_reserve_addr_blk_error,
					    S1394_TNF_SL_ARREQ_ERROR, "");
					TNF_PROBE_0_DEBUG(
					    s1394_reserve_addr_blk_exit,
					    S1394_TNF_SL_ARREQ_STACK, "");
					return (DDI_FAILURE);
				}

				middle_blk->addr_lo = addr_allocp->aa_address;
				middle_blk->addr_hi = upper_bound;
				new_blk->addr_lo = upper_bound + 1;
				new_blk->addr_hi = curr_blk->addr_hi;

				new_blk->addr_type = curr_blk->addr_type;

				middle_blk->addr_type = curr_blk->addr_type;
				middle_blk->addr_reserved = ADDR_RESERVED;

				curr_blk->addr_hi = addr_allocp->aa_address - 1;

				/* Put pieces back into the "free" list */
				s1394_free_list_insert(hal, middle_blk);
				s1394_free_list_insert(hal, new_blk);

				/* Unlock the address space free list */
				mutex_exit(&hal->addr_space_free_mutex);

				TNF_PROBE_0_DEBUG(s1394_reserve_addr_blk_exit,
				    S1394_TNF_SL_ARREQ_STACK, "");
				return (DDI_SUCCESS);
			}
		}
	}

	/* Unlock the address space free list */
	mutex_exit(&hal->addr_space_free_mutex);

	TNF_PROBE_0_DEBUG(s1394_reserve_addr_blk_exit,
	    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
 *    CSR registers are allocated/setup in s1394_setup_CSR_space().
 */
int
s1394_init_addr_space(s1394_hal_t *hal)
{
	s1394_addr_space_blk_t	*addr_blk;
	t1394_alloc_addr_t	addr_alloc;
	h1394_addr_map_t	*addr_map;
	h1394_addr_map_t	*resv_map;
	uint_t			num_blks;
	uint64_t		lo;
	uint64_t		hi;
	int			i;
	int			ret;

	TNF_PROBE_0_DEBUG(s1394_init_addr_space_enter,
	    S1394_TNF_SL_ARREQ_STACK, "");

	/* Setup Address Space */
	mutex_init(&hal->addr_space_free_mutex,
	    NULL, MUTEX_DRIVER, NULL);
	mutex_init(&hal->addr_space_used_mutex,
	    NULL, MUTEX_DRIVER, hal->halinfo.hw_interrupt);

	/* Set address space to NULL (empty) */
	hal->addr_space_free_list = NULL;
	hal->addr_space_used_tree = NULL;

	/* Initialize the 1394 Address Space from HAL's description */
	num_blks = hal->halinfo.addr_map_num_entries;
	addr_map = hal->halinfo.addr_map;

	/* Lock the address space free list */
	mutex_enter(&hal->addr_space_free_mutex);

	/* Default to NO posted write space */
	hal->posted_write_addr_lo = ADDR_LO_INVALID;
	hal->posted_write_addr_hi = ADDR_HI_INVALID;

	/* Default to NO physical space */
	hal->physical_addr_lo = ADDR_LO_INVALID;
	hal->physical_addr_hi = ADDR_HI_INVALID;

	/* Default to NO CSR space */
	hal->csr_addr_lo = ADDR_LO_INVALID;
	hal->csr_addr_hi = ADDR_HI_INVALID;

	/* Default to NO normal space */
	hal->normal_addr_lo = ADDR_LO_INVALID;
	hal->normal_addr_hi = ADDR_HI_INVALID;

	for (i = 0; i < num_blks; i++) {
		if (addr_map[i].length == 0)
			continue;
		addr_blk = kmem_zalloc(sizeof (s1394_addr_space_blk_t),
		    KM_SLEEP);
		addr_blk->addr_lo = addr_map[i].address;
		addr_blk->addr_hi =
		    (addr_blk->addr_lo + addr_map[i].length) - 1;

		switch (addr_map[i].addr_type) {
		case H1394_ADDR_POSTED_WRITE:
			addr_blk->addr_type = T1394_ADDR_POSTED_WRITE;
			hal->posted_write_addr_lo = addr_blk->addr_lo;
			hal->posted_write_addr_hi = addr_blk->addr_hi;
			break;

		case H1394_ADDR_NORMAL:
			addr_blk->addr_type = T1394_ADDR_NORMAL;
			hal->normal_addr_lo = addr_blk->addr_lo;
			hal->normal_addr_hi = addr_blk->addr_hi;
			break;

		case H1394_ADDR_CSR:
			addr_blk->addr_type = T1394_ADDR_CSR;
			hal->csr_addr_lo = addr_blk->addr_lo;
			hal->csr_addr_hi = addr_blk->addr_hi;
			break;

		case H1394_ADDR_PHYSICAL:
			addr_blk->addr_type = T1394_ADDR_FIXED;
			hal->physical_addr_lo = addr_blk->addr_lo;
			hal->physical_addr_hi = addr_blk->addr_hi;
			break;

		default:
			/* Unlock the address space free list */
			mutex_exit(&hal->addr_space_free_mutex);
			s1394_destroy_addr_space(hal);
			TNF_PROBE_1(s1394_init_addr_space_error,
			    S1394_TNF_SL_ARREQ_ERROR, "", tnf_string, msg,
			    "Invalid addr_type specified");
			TNF_PROBE_0_DEBUG(s1394_init_addr_space_exit,
			    S1394_TNF_SL_ARREQ_STACK, "");
			return (DDI_FAILURE);
		}
		s1394_free_list_insert(hal, addr_blk);
	}

	/* Unlock the address space free list */
	mutex_exit(&hal->addr_space_free_mutex);

	/* Setup the necessary CSR space */
	if (s1394_setup_CSR_space(hal) != DDI_SUCCESS) {
		s1394_destroy_addr_space(hal);
		TNF_PROBE_1(s1394_init_addr_space_error,
		    S1394_TNF_SL_ARREQ_ERROR, "", tnf_string, msg,
		    "Failed in s1394_setup_CSR_space()");
		TNF_PROBE_0_DEBUG(s1394_init_addr_space_exit,
		    S1394_TNF_SL_ARREQ_STACK, "");
		return (DDI_FAILURE);
	}


	/* Handle all the HAL's reserved spaces */
	num_blks = hal->halinfo.resv_map_num_entries;
	resv_map = hal->halinfo.resv_map;

	for (i = 0; i < num_blks; i++) {
		/* Can't reserve physical addresses */
		lo = resv_map[i].address;
		hi = (lo + resv_map[i].length) - 1;
		if ((lo >= hal->physical_addr_lo) &&
		    (hi <= hal->physical_addr_hi)) {
			s1394_destroy_addr_space(hal);
			TNF_PROBE_1(s1394_init_addr_space_error,
			    S1394_TNF_SL_ARREQ_ERROR, "", tnf_string, msg,
			    "Attempted to reserve physical memory");
			TNF_PROBE_0_DEBUG(s1394_init_addr_space_exit,
			    S1394_TNF_SL_ARREQ_STACK, "");
			return (DDI_FAILURE);
		}

		addr_alloc.aa_address = resv_map[i].address;
		addr_alloc.aa_length = resv_map[i].length;
		ret = s1394_reserve_addr_blk(hal, &addr_alloc);
		if (ret != DDI_SUCCESS) {
			s1394_destroy_addr_space(hal);
			TNF_PROBE_1(s1394_init_addr_space_error,
			    S1394_TNF_SL_ARREQ_ERROR, "", tnf_string, msg,
			    "Unable to reserve 1394 address");
			TNF_PROBE_0_DEBUG(s1394_init_addr_space_exit,
			    S1394_TNF_SL_ARREQ_STACK, "");
			return (DDI_FAILURE);
		}
	}

	TNF_PROBE_0_DEBUG(s1394_init_addr_space_exit, S1394_TNF_SL_ARREQ_STACK,
	    "");
	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_destroy_addr_space(s1394_hal_t *hal)
{
	s1394_addr_space_blk_t	*addr_blk;
	s1394_addr_space_blk_t	*next_blk;
	uint64_t		lo;
	uint64_t		hi;
	uint_t			length;

	TNF_PROBE_0_DEBUG(s1394_destroy_addr_space_enter,
	    S1394_TNF_SL_ARREQ_STACK, "");

	/* Lock the address space "used" tree */
	mutex_enter(&hal->addr_space_used_mutex);

	addr_blk = hal->addr_space_used_tree;

	while (addr_blk != NULL) {
		if (addr_blk->asb_left != NULL) {
			addr_blk = addr_blk->asb_left;
		} else if (addr_blk->asb_right != NULL) {
			addr_blk = addr_blk->asb_right;
		} else {
			/* Free any of our own backing store (if necessary) */
			if ((addr_blk->free_kmem_bufp == B_TRUE) &&
			    (addr_blk->kmem_bufp != NULL)) {
				lo = addr_blk->addr_lo;
				hi = addr_blk->addr_hi;
				length = (uint_t)((hi - lo) + 1);
				kmem_free((void *)addr_blk->kmem_bufp, length);
			}

			next_blk = addr_blk->asb_parent;

			/* Free the s1394_addr_space_blk_t structure */
			kmem_free((void *)addr_blk,
			    sizeof (s1394_addr_space_blk_t));

			if (next_blk != NULL) {
				if (next_blk->asb_left != NULL)
					next_blk->asb_left = NULL;
				else
					next_blk->asb_right = NULL;
			}

			addr_blk = next_blk;
		}
	}

	/* Unlock and destroy the address space "used" tree */
	mutex_exit(&hal->addr_space_used_mutex);
	mutex_destroy(&hal->addr_space_used_mutex);

	/* Lock the address space "free" list */
	mutex_enter(&hal->addr_space_free_mutex);

	addr_blk = hal->addr_space_free_list;

	while (addr_blk != NULL) {
		next_blk = addr_blk->asb_right;

		/* Free the s1394_addr_space_blk_t structure */
		kmem_free((void *)addr_blk, sizeof (s1394_addr_space_blk_t));
		addr_blk = next_blk;
	}

	/* Unlock & destroy the address space "free" list */
	mutex_exit(&hal->addr_space_free_mutex);
	mutex_destroy(&hal->addr_space_free_mutex);

	TNF_PROBE_0_DEBUG(s1394_destroy_addr_space_exit,
	    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_free_list_insert(s1394_hal_t *hal, s1394_addr_space_blk_t *new_blk)
{
	s1394_addr_space_blk_t	*curr_blk;
	s1394_addr_space_blk_t	*left_blk;
	s1394_addr_space_blk_t	*right_blk;

	TNF_PROBE_0_DEBUG(s1394_free_list_insert_enter,
	    S1394_TNF_SL_ARREQ_STACK, "");

	ASSERT(MUTEX_HELD(&hal->addr_space_free_mutex));

	/* Start at the head of the "free" list */
	curr_blk = hal->addr_space_free_list;

	if (curr_blk != NULL)
		left_blk = curr_blk->asb_left;
	else
		left_blk = NULL;

	while (curr_blk != NULL) {
		if (new_blk->addr_lo < curr_blk->addr_lo)
			break;
		/* Go to the next element in the list */
		left_blk = curr_blk;
		curr_blk = curr_blk->asb_right;
	}

	new_blk->asb_left = left_blk;
	new_blk->asb_right = curr_blk;

	if (left_blk != NULL)
		left_blk->asb_right = new_blk;
	else
		hal->addr_space_free_list = new_blk;

	if (curr_blk != NULL)
		curr_blk->asb_left = new_blk;

	right_blk = new_blk->asb_right;
	left_blk = new_blk->asb_left;

	/* Can we merge with block to the left? */
	if ((left_blk != NULL) &&
	    (new_blk->addr_type == left_blk->addr_type) &&
	    (new_blk->addr_reserved != ADDR_RESERVED) &&
	    (left_blk->addr_reserved != ADDR_RESERVED) &&
	    (new_blk->addr_lo == left_blk->addr_hi + 1)) {

		new_blk->addr_lo = left_blk->addr_lo;
		new_blk->asb_left = left_blk->asb_left;

		if (left_blk->asb_left != NULL)
			left_blk->asb_left->asb_right = new_blk;
		if (hal->addr_space_free_list == left_blk)
			hal->addr_space_free_list = new_blk;
		kmem_free((void *)left_blk, sizeof (s1394_addr_space_blk_t));
	}

	/* Can we merge with block to the right? */
	if ((right_blk != NULL) &&
	    (new_blk->addr_type == right_blk->addr_type) &&
	    (new_blk->addr_reserved != ADDR_RESERVED) &&
	    (right_blk->addr_reserved != ADDR_RESERVED) &&
	    (new_blk->addr_hi + 1 == right_blk->addr_lo)) {

		new_blk->addr_hi = right_blk->addr_hi;
		new_blk->asb_right = right_blk->asb_right;

		if (right_blk->asb_right != NULL)
			right_blk->asb_right->asb_left = new_blk;
		kmem_free((void *)right_blk, sizeof (s1394_addr_space_blk_t));
	}

	new_blk->addr_enable = 0;
	new_blk->kmem_bufp = NULL;
	new_blk->addr_arg = NULL;

	TNF_PROBE_0_DEBUG(s1394_free_list_insert_exit,
	    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_free_list_search(s1394_hal_t *hal, uint64_t addr)
{
	s1394_addr_space_blk_t	*curr_blk;

	TNF_PROBE_0_DEBUG(s1394_free_list_search_enter,
	    S1394_TNF_SL_ARREQ_STACK, "");

	ASSERT(MUTEX_HELD(&hal->addr_space_free_mutex));

	/* Start at the head of the list */
	curr_blk = hal->addr_space_free_list;
	while (curr_blk != NULL) {
		if ((addr >= curr_blk->addr_lo) && (addr <= curr_blk->addr_hi))
			break;
		else
			curr_blk = curr_blk->asb_right;
	}

	TNF_PROBE_0_DEBUG(s1394_free_list_search_exit,
	    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 *
s1394_free_list_find(s1394_hal_t *hal, uint32_t type, uint32_t length)
{
	s1394_addr_space_blk_t	*curr_blk;
	uint64_t		size;

	TNF_PROBE_0_DEBUG(s1394_free_list_find_enter, S1394_TNF_SL_ARREQ_STACK,
	    "");

	ASSERT(MUTEX_HELD(&hal->addr_space_free_mutex));

	/* Start at the head of the list */
	curr_blk = hal->addr_space_free_list;

	while (curr_blk != NULL) {
		/* Find block of right "type" - that isn't "reserved" */
		if ((curr_blk->addr_type == type) &&
		    (curr_blk->addr_reserved != ADDR_RESERVED)) {

			/* CSR allocs above IEEE1394_UCSR_RESERVED_BOUNDARY */
			if ((type == T1394_ADDR_CSR) &&
			    (curr_blk->addr_lo <
				IEEE1394_UCSR_RESERVED_BOUNDARY)) {
				curr_blk = curr_blk->asb_right;
				continue;
			}

			size = (curr_blk->addr_hi - curr_blk->addr_lo) + 1;
			if (size >= (uint64_t)length)
				break;
		}
		curr_blk = curr_blk->asb_right;
	}

	TNF_PROBE_0_DEBUG(s1394_free_list_find_exit, S1394_TNF_SL_ARREQ_STACK,
	    "");
	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_free_list_delete(s1394_hal_t *hal, s1394_addr_space_blk_t *del_blk)
{
	s1394_addr_space_blk_t	*left_blk;
	s1394_addr_space_blk_t	*right_blk;

	TNF_PROBE_0_DEBUG(s1394_free_list_delete_enter,
	    S1394_TNF_SL_ARREQ_STACK, "");

	ASSERT(MUTEX_HELD(&hal->addr_space_free_mutex));

	left_blk = del_blk->asb_left;
	right_blk = del_blk->asb_right;

	del_blk->asb_left = NULL;
	del_blk->asb_right = NULL;

	if (left_blk != NULL)
		left_blk->asb_right = right_blk;
	else
		hal->addr_space_free_list = right_blk;

	if (right_blk != NULL)
		right_blk->asb_left = left_blk;

	TNF_PROBE_0_DEBUG(s1394_free_list_delete_exit,
	    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_used_tree_insert(s1394_hal_t *hal, s1394_addr_space_blk_t *x)
{
	s1394_addr_space_blk_t	*y;
	s1394_addr_space_blk_t	**root;

	TNF_PROBE_0_DEBUG(s1394_used_tree_insert_enter,
	    S1394_TNF_SL_ARREQ_STACK, "");

	/* Lock the "used" tree */
	mutex_enter(&hal->addr_space_used_mutex);

	/* Get the head of the "used" tree */
	root = &hal->addr_space_used_tree;

	s1394_tree_insert(root, x);

	x->asb_color = RED;
	while ((x != *root) && (x->asb_parent->asb_color == RED)) {
		/* Is x's parent the "left-child" or the "right-child"? */
		if (x->asb_parent == x->asb_parent->asb_parent->asb_left) {
			/* Left-child, set y to the sibling */
			y = x->asb_parent->asb_parent->asb_right;
			if ((y != NULL) && (y->asb_color == RED)) {
				x->asb_parent->asb_color = BLACK;
				y->asb_color = BLACK;
				x->asb_parent->asb_parent->asb_color = RED;
				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_color = BLACK;
				x->asb_parent->asb_parent->asb_color = RED;
				s1394_right_rotate(root,
				    x->asb_parent->asb_parent);
			}

		} else {
			/* Right-child, set y to the sibling */
			y = x->asb_parent->asb_parent->asb_left;
			if ((y != NULL) && (y->asb_color == RED)) {
				x->asb_parent->asb_color = BLACK;
				y->asb_color = BLACK;
				x->asb_parent->asb_parent->asb_color = RED;
				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_color = BLACK;
				x->asb_parent->asb_parent->asb_color = RED;
				s1394_left_rotate(root,
				    x->asb_parent->asb_parent);
			}
		}
	}

	(*root)->asb_color = BLACK;

	/* Unlock the "used" tree */
	mutex_exit(&hal->addr_space_used_mutex);

	TNF_PROBE_0_DEBUG(s1394_used_tree_insert_exit,
	    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_tree_insert(s1394_addr_space_blk_t **root, s1394_addr_space_blk_t *z)
{
	s1394_addr_space_blk_t	*y = NULL;
	s1394_addr_space_blk_t	*x = *root;

	TNF_PROBE_0_DEBUG(s1394_tree_insert_enter, S1394_TNF_SL_ARREQ_STACK,
	    "");

	while (x != NULL) {
		y = x;
		if (z->addr_lo < x->addr_lo)
			x = x->asb_left;
		else
			x = x->asb_right;
	}

	z->asb_parent = y;
	z->asb_right = NULL;
	z->asb_left = NULL;

	if (y == NULL)
		*root = z;
	else if (z->addr_lo < y->addr_lo)
		y->asb_left = z;
	else
		y->asb_right = z;

	TNF_PROBE_0_DEBUG(s1394_tree_insert_exit, S1394_TNF_SL_ARREQ_STACK,
	    "");
}

/*
 * 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_addr_space_blk_t *
s1394_used_tree_search(s1394_hal_t *hal, uint64_t addr)
{
	s1394_addr_space_blk_t *curr_blk;

	TNF_PROBE_0_DEBUG(s1394_used_tree_search_enter,
	    S1394_TNF_SL_ARREQ_STACK, "");

	ASSERT(MUTEX_HELD(&hal->addr_space_used_mutex));

	/* Search the HAL's "used" tree for this address */
	curr_blk = s1394_tree_search(hal->addr_space_used_tree, addr);

	TNF_PROBE_0_DEBUG(s1394_used_tree_search_exit,
	    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 *
s1394_tree_search(s1394_addr_space_blk_t *x, uint64_t address)
{
	TNF_PROBE_0_DEBUG(s1394_tree_search_enter, S1394_TNF_SL_ARREQ_STACK,
	    "");

	while (x != NULL) {
		if (x->addr_lo > address)
			x = x->asb_left;
		else if (x->addr_hi < address)
			x = x->asb_right;
		else
			break;
	}

	TNF_PROBE_0_DEBUG(s1394_tree_search_exit, S1394_TNF_SL_ARREQ_STACK,
	    "");
	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().
 */
s1394_addr_space_blk_t *
s1394_used_tree_delete(s1394_hal_t *hal, s1394_addr_space_blk_t *z)
{
	s1394_addr_space_blk_t	*y;
	s1394_addr_space_blk_t	*x;
	s1394_addr_space_blk_t	*w;
	s1394_addr_space_blk_t	*p;
	s1394_addr_space_blk_t	**root;
	int			old_color;
	int			side_of_x;

	TNF_PROBE_0_DEBUG(s1394_used_tree_delete_enter,
	    S1394_TNF_SL_ARREQ_STACK, "");

	/* Lock the "used" tree */
	mutex_enter(&hal->addr_space_used_mutex);

	/* Get the head of the "used" tree */
	root = &hal->addr_space_used_tree;

	if ((z->asb_left == NULL) || (z->asb_right == NULL))
		y = z;
	else
		y = s1394_tree_successor(z);

	if (y->asb_parent == z)
		p = y;
	else
		p = y->asb_parent;

	if (y->asb_left != NULL) {
		x = y->asb_left;
		if ((y != *root) && (y == y->asb_parent->asb_left)) {
			w = y->asb_parent->asb_right;
			side_of_x = LEFT;
		}

		if ((y != *root) && (y == y->asb_parent->asb_right)) {
			w = y->asb_parent->asb_left;
			side_of_x = RIGHT;
		}

	} else {
		x = y->asb_right;
		if ((y != *root) && (y == y->asb_parent->asb_left)) {
			w = y->asb_parent->asb_right;
			side_of_x = LEFT;
		}

		if ((y != *root) && (y == y->asb_parent->asb_right)) {
			w = y->asb_parent->asb_left;
			side_of_x = RIGHT;
		}

	}

	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;

	old_color = y->asb_color;

	/* Substitute the y-node for the z-node (deleted) */
	if (y != z) {
		y->asb_color = z->asb_color;
		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;
		}

		y->asb_left = z->asb_left;
		if (z->asb_left != NULL)
			z->asb_left->asb_parent = y;
		y->asb_right = z->asb_right;
		if (z->asb_right != NULL)
			z->asb_right->asb_parent = y;

		if (z == *root)
			*root = y;
	}

	z->asb_parent = NULL;
	z->asb_right = NULL;
	z->asb_left = NULL;

	if (old_color == BLACK)
		s1394_used_tree_delete_fixup(root, p, x, w, side_of_x);

	/* Unlock the "used" tree */
	mutex_exit(&hal->addr_space_used_mutex);

	TNF_PROBE_0_DEBUG(s1394_used_tree_delete_exit,
	    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
 *    cleanup/enforce the red-black coloring in the tree.
 */
static void
s1394_used_tree_delete_fixup(s1394_addr_space_blk_t **root,
    s1394_addr_space_blk_t *p, s1394_addr_space_blk_t *x,
    s1394_addr_space_blk_t *w, int side_of_x)
{
	boolean_t	first_time;

	TNF_PROBE_0_DEBUG(s1394_used_tree_delete_fixup_enter,
	    S1394_TNF_SL_ARREQ_STACK, "");

	first_time = B_TRUE;
	while ((x != *root) && ((x == NULL) || (x->asb_color == BLACK))) {
		if (((first_time == B_TRUE) && (side_of_x == LEFT)) ||
		    ((first_time == B_FALSE) && (x == p->asb_left))) {

			if (first_time != B_TRUE)
				w = p->asb_right;

			if ((w != NULL) && (w->asb_color == RED)) {
				w->asb_color = BLACK;
				p->asb_color = RED;
				s1394_left_rotate(root, p);
				w = p->asb_right;
			}

			if (w == NULL) {
				x = p;
				p = p->asb_parent;
				first_time = B_FALSE;

			} else if (((w->asb_left == NULL) ||
			    (w->asb_left->asb_color == BLACK)) &&
			    ((w->asb_right == NULL) ||
			    (w->asb_right->asb_color == BLACK))) {
				w->asb_color = RED;
				x = p;
				p = p->asb_parent;
				first_time = B_FALSE;

			} else {
				if ((w->asb_right == NULL) ||
				    (w->asb_right->asb_color == BLACK)) {
					w->asb_left->asb_color = BLACK;
					w->asb_color = RED;
					s1394_right_rotate(root, w);
					w = p->asb_right;
				}

				w->asb_color = p->asb_color;
				p->asb_color = BLACK;
				if (w->asb_right != NULL)
					w->asb_right->asb_color = BLACK;
				s1394_left_rotate(root, p);
				x = *root;
				first_time = B_FALSE;
			}

		} else {
			if (first_time == B_FALSE)
				w = p->asb_left;

			if ((w != NULL) && (w->asb_color == RED)) {
				w->asb_color = BLACK;
				p->asb_color = RED;
				s1394_right_rotate(root, p);
				w = p->asb_left;
			}

			if (w == NULL) {
				x = p;
				p = p->asb_parent;
				first_time = B_FALSE;

			} else if (((w->asb_left == NULL) ||
			    (w->asb_left->asb_color == BLACK)) &&
			    ((w->asb_right == NULL) ||
			    (w->asb_right->asb_color == BLACK))) {
				w->asb_color = RED;
				x = p;
				p = p->asb_parent;
				first_time = B_FALSE;

			} else {
				if ((w->asb_left == NULL) ||
				    (w->asb_left->asb_color == BLACK)) {

					w->asb_right->asb_color = BLACK;
					w->asb_color = RED;
					s1394_left_rotate(root, w);
					w = p->asb_left;
				}

				w->asb_color = p->asb_color;
				p->asb_color = BLACK;
				if (w->asb_left != NULL)
					w->asb_left->asb_color = BLACK;
				s1394_right_rotate(root, p);
				x = *root;
				first_time = B_FALSE;
			}
		}
	}
	if (x != NULL)
		x->asb_color = BLACK;

	TNF_PROBE_0_DEBUG(s1394_used_tree_delete_fixup_exit,
	    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
s1394_left_rotate(s1394_addr_space_blk_t **root, s1394_addr_space_blk_t *x)
{
	s1394_addr_space_blk_t	*y;

	TNF_PROBE_0_DEBUG(s1394_left_rotate_enter, S1394_TNF_SL_ARREQ_STACK,
	    "");

	y = x->asb_right;
	x->asb_right = y->asb_left;

	if (y->asb_left != NULL)
		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;

	TNF_PROBE_0_DEBUG(s1394_left_rotate_exit, S1394_TNF_SL_ARREQ_STACK,
	    "");
}

/*
 * 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
s1394_right_rotate(s1394_addr_space_blk_t **root, s1394_addr_space_blk_t *x)
{
	s1394_addr_space_blk_t	*y;

	TNF_PROBE_0_DEBUG(s1394_right_rotate_enter, S1394_TNF_SL_ARREQ_STACK,
	    "");

	y = x->asb_left;
	x->asb_left = y->asb_right;

	if (y->asb_right != NULL)
		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;

	TNF_PROBE_0_DEBUG(s1394_right_rotate_exit, S1394_TNF_SL_ARREQ_STACK,
	    "");
}

/*
 * s1394_tree_minimum()
 *    is used to find the smallest key in a binary tree.
 */
static s1394_addr_space_blk_t *
s1394_tree_minimum(s1394_addr_space_blk_t *x)
{
	TNF_PROBE_0_DEBUG(s1394_tree_minimum_enter, S1394_TNF_SL_ARREQ_STACK,
	    "");

	while (x->asb_left != NULL)
		x = x->asb_left;

	TNF_PROBE_0_DEBUG(s1394_tree_minimum_exit, S1394_TNF_SL_ARREQ_STACK,
	    "");
	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 *
s1394_tree_successor(s1394_addr_space_blk_t *x)
{
	s1394_addr_space_blk_t	*y;

	TNF_PROBE_0_DEBUG(s1394_tree_successor_enter, S1394_TNF_SL_ARREQ_STACK,
	    "");

	if (x->asb_right != NULL) {
		y = s1394_tree_minimum(x->asb_right);

		TNF_PROBE_0_DEBUG(s1394_tree_successor_exit,
		    S1394_TNF_SL_ARREQ_STACK, "");
		return (y);
	}

	y = x->asb_parent;
	while ((y != NULL) && (x == y->asb_right)) {
		x = y;
		y = y->asb_parent;
	}

	TNF_PROBE_0_DEBUG(s1394_tree_successor_exit, S1394_TNF_SL_ARREQ_STACK,
	    "");
	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.
 */
boolean_t
s1394_is_posted_write(s1394_hal_t *hal, uint64_t addr)
{
	addr = addr & IEEE1394_ADDR_OFFSET_MASK;

	if ((addr >= hal->posted_write_addr_lo) &&
	    (addr <= hal->posted_write_addr_hi))
		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.
 */
boolean_t
s1394_is_physical_addr(s1394_hal_t *hal, uint64_t addr)
{
	addr = addr & IEEE1394_ADDR_OFFSET_MASK;

	if ((addr >= hal->physical_addr_lo) &&
	    (addr <= hal->physical_addr_hi))
		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.
 */
boolean_t
s1394_is_csr_addr(s1394_hal_t *hal, uint64_t addr)
{
	addr = addr & IEEE1394_ADDR_OFFSET_MASK;

	if ((addr >= hal->csr_addr_lo) &&
	    (addr <= hal->csr_addr_hi))
		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.
 */
boolean_t
s1394_is_normal_addr(s1394_hal_t *hal, uint64_t addr)
{
	addr = addr & IEEE1394_ADDR_OFFSET_MASK;

	if ((addr >= hal->normal_addr_lo) &&
	    (addr <= hal->normal_addr_hi))
		return (B_TRUE);
	else
		return (B_FALSE);
}