/* * 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. */ /* * s1394_addr.c * 1394 Address Space Routines * Implements all the routines necessary for alloc/free and lookup * of the 1394 address space */ #include #include #include #include #include #include #include #include #include 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; 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); 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); 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); 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); 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; 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); 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); 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); 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); 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); 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); 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); 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)); 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); return (DDI_SUCCESS); } } } claim_error: /* Unlock the address space free list */ mutex_exit(&hal->addr_space_free_mutex); 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) { /* 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); 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); 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; 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); 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); 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); 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); 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); 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); 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); 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); 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)); 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); return (DDI_SUCCESS); } } } /* Unlock the address space free list */ mutex_exit(&hal->addr_space_free_mutex); 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; /* 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); 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); 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); 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); 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_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; /* 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); } /* * 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; 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; } /* * 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; 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; } 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; 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; } 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; 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; 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; /* 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); } /* * 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; 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; } /* * 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; 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); 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) { while (x != NULL) { if (x->addr_lo > address) x = x->asb_left; else if (x->addr_hi < address) 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(). */ 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; /* 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); 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; 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; } /* * 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; 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; } /* * 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; 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; } /* * 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) { while (x->asb_left != NULL) 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 * s1394_tree_successor(s1394_addr_space_blk_t *x) { s1394_addr_space_blk_t *y; if (x->asb_right != NULL) { y = s1394_tree_minimum(x->asb_right); return (y); } y = x->asb_parent; while ((y != NULL) && (x == y->asb_right)) { 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. */ 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); }