cam_queue.c revision 39212
139212Sgibbs/* 239212Sgibbs * CAM request queue management functions. 339212Sgibbs * 439212Sgibbs * Copyright (c) 1997 Justin T. Gibbs. 539212Sgibbs * All rights reserved. 639212Sgibbs * 739212Sgibbs * Redistribution and use in source and binary forms, with or without 839212Sgibbs * modification, are permitted provided that the following conditions 939212Sgibbs * are met: 1039212Sgibbs * 1. Redistributions of source code must retain the above copyright 1139212Sgibbs * notice, this list of conditions, and the following disclaimer, 1239212Sgibbs * without modification, immediately at the beginning of the file. 1339212Sgibbs * 2. The name of the author may not be used to endorse or promote products 1439212Sgibbs * derived from this software without specific prior written permission. 1539212Sgibbs * 1639212Sgibbs * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 1739212Sgibbs * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1839212Sgibbs * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1939212Sgibbs * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR 2039212Sgibbs * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2139212Sgibbs * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2239212Sgibbs * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2339212Sgibbs * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2439212Sgibbs * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2539212Sgibbs * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2639212Sgibbs * SUCH DAMAGE. 2739212Sgibbs * 2839212Sgibbs * $Id$ 2939212Sgibbs */ 3039212Sgibbs#include <sys/param.h> 3139212Sgibbs#include <sys/systm.h> 3239212Sgibbs#include <sys/types.h> 3339212Sgibbs#include <sys/malloc.h> 3439212Sgibbs 3539212Sgibbs#include <cam/cam.h> 3639212Sgibbs#include <cam/cam_ccb.h> 3739212Sgibbs#include <cam/cam_queue.h> 3839212Sgibbs#include <cam/cam_debug.h> 3939212Sgibbs 4039212Sgibbsstatic __inline int 4139212Sgibbs queue_cmp(cam_pinfo **queue_array, int i, int j); 4239212Sgibbsstatic __inline void 4339212Sgibbs swap(cam_pinfo **queue_array, int i, int j); 4439212Sgibbsstatic void heap_up(cam_pinfo **queue_array, int new_index); 4539212Sgibbsstatic void heap_down(cam_pinfo **queue_array, int index, 4639212Sgibbs int last_index); 4739212Sgibbs 4839212Sgibbsstruct camq * 4939212Sgibbscamq_alloc(int size) 5039212Sgibbs{ 5139212Sgibbs struct camq *camq; 5239212Sgibbs 5339212Sgibbs camq = (struct camq *)malloc(sizeof(*camq), M_DEVBUF, M_NOWAIT); 5439212Sgibbs if (camq != NULL) { 5539212Sgibbs if (camq_init(camq, size) != 0) { 5639212Sgibbs free(camq, M_DEVBUF); 5739212Sgibbs camq = NULL; 5839212Sgibbs } 5939212Sgibbs } 6039212Sgibbs return (camq); 6139212Sgibbs} 6239212Sgibbs 6339212Sgibbsint 6439212Sgibbscamq_init(struct camq *camq, int size) 6539212Sgibbs{ 6639212Sgibbs bzero(camq, sizeof(*camq)); 6739212Sgibbs camq->array_size = size; 6839212Sgibbs if (camq->array_size != 0) { 6939212Sgibbs camq->queue_array = (cam_pinfo**)malloc(size*sizeof(cam_pinfo*), 7039212Sgibbs M_DEVBUF, M_NOWAIT); 7139212Sgibbs if (camq->queue_array == NULL) { 7239212Sgibbs printf("camq_init: - cannot malloc array!\n"); 7339212Sgibbs return (1); 7439212Sgibbs } 7539212Sgibbs } 7639212Sgibbs return (0); 7739212Sgibbs} 7839212Sgibbs 7939212Sgibbs/* 8039212Sgibbs * Free a camq structure. This should only be called if a controller 8139212Sgibbs * driver failes somehow during its attach routine or is unloaded and has 8239212Sgibbs * obtained a camq structure. The XPT should ensure that the queue 8339212Sgibbs * is empty before calling this routine. 8439212Sgibbs */ 8539212Sgibbsvoid 8639212Sgibbscamq_free(struct camq *queue) 8739212Sgibbs{ 8839212Sgibbs if (queue != NULL) { 8939212Sgibbs camq_fini(queue); 9039212Sgibbs free(queue, M_DEVBUF); 9139212Sgibbs } 9239212Sgibbs} 9339212Sgibbs 9439212Sgibbsvoid 9539212Sgibbscamq_fini(struct camq *queue) 9639212Sgibbs{ 9739212Sgibbs if (queue->queue_array != NULL) { 9839212Sgibbs free(queue->queue_array, M_DEVBUF); 9939212Sgibbs } 10039212Sgibbs} 10139212Sgibbs 10239212Sgibbsu_int32_t 10339212Sgibbscamq_resize(struct camq *queue, int new_size) 10439212Sgibbs{ 10539212Sgibbs cam_pinfo **new_array; 10639212Sgibbs 10739212Sgibbs#ifdef DIAGNOSTIC 10839212Sgibbs if (new_size < queue->entries) 10939212Sgibbs panic("camq_resize: New queue size can't accomodate " 11039212Sgibbs "queued entries."); 11139212Sgibbs#endif 11239212Sgibbs new_array = (cam_pinfo **)malloc(new_size * sizeof(cam_pinfo *), 11339212Sgibbs M_DEVBUF, M_NOWAIT); 11439212Sgibbs if (new_array == NULL) { 11539212Sgibbs /* Couldn't satisfy request */ 11639212Sgibbs return (CAM_RESRC_UNAVAIL); 11739212Sgibbs } 11839212Sgibbs if (queue->queue_array != NULL) { 11939212Sgibbs bcopy(queue->queue_array, new_array, 12039212Sgibbs queue->entries * sizeof(cam_pinfo *)); 12139212Sgibbs free(queue->queue_array, M_DEVBUF); 12239212Sgibbs } 12339212Sgibbs queue->queue_array = new_array; 12439212Sgibbs queue->array_size = new_size; 12539212Sgibbs return (CAM_REQ_CMP); 12639212Sgibbs} 12739212Sgibbs 12839212Sgibbs/* 12939212Sgibbs * camq_regen: Given an array of cam_pinfo* elements with the 13039212Sgibbs * Heap(0, num_elements) property, perform the second half of 13139212Sgibbs * a heap sort, and assign new generation numbers to all entries. 13239212Sgibbs * It is assumed that the starting generation number plus the 13339212Sgibbs * number of entries in the queue is smaller than the wrap point 13439212Sgibbs * of the generation number. 13539212Sgibbs */ 13639212Sgibbsvoid 13739212Sgibbscamq_regen(struct camq *queue) 13839212Sgibbs{ 13939212Sgibbs int index; 14039212Sgibbs 14139212Sgibbs for (index = 0; index < queue->entries; index++) { 14239212Sgibbs 14339212Sgibbs heap_down(queue->queue_array, index, queue->entries); 14439212Sgibbs queue->queue_array[index]->generation = queue->generation++; 14539212Sgibbs } 14639212Sgibbs /* A sorted array is still a heap, so we are done */ 14739212Sgibbs} 14839212Sgibbs 14939212Sgibbs/* 15039212Sgibbs * camq_insert: Given an array of cam_pinfo* elememnts with 15139212Sgibbs * the Heap(0, num_elements) property and array_size - num_elements >= 1, 15239212Sgibbs * output Heap(0, num_elements+1) including new_entry in the array. 15339212Sgibbs */ 15439212Sgibbsvoid 15539212Sgibbscamq_insert(struct camq *queue, cam_pinfo *new_entry) 15639212Sgibbs{ 15739212Sgibbs#ifdef DIAGNOSTIC 15839212Sgibbs if (queue->entries >= queue->array_size) 15939212Sgibbs panic("camq_insert: Attempt to insert into a full queue"); 16039212Sgibbs#endif 16139212Sgibbs queue->queue_array[queue->entries] = new_entry; 16239212Sgibbs new_entry->index = queue->entries; 16339212Sgibbs if (queue->entries != 0) 16439212Sgibbs heap_up(queue->queue_array, queue->entries); 16539212Sgibbs queue->entries++; 16639212Sgibbs} 16739212Sgibbs 16839212Sgibbs/* 16939212Sgibbs * camq_remove: Given an array of cam_pinfo* elevements with the 17039212Sgibbs * Heap(0, num_elements) property and an index such that 0 <= index <= 17139212Sgibbs * num_elements, remove that entry and restore the Heap(0, num_elements-1) 17239212Sgibbs * property. 17339212Sgibbs */ 17439212Sgibbscam_pinfo * 17539212Sgibbscamq_remove(struct camq *queue, int index) 17639212Sgibbs{ 17739212Sgibbs cam_pinfo *removed_entry; 17839212Sgibbs 17939212Sgibbs if ((queue->entries - index) <= 0) 18039212Sgibbs return (NULL); 18139212Sgibbs removed_entry = queue->queue_array[index]; 18239212Sgibbs queue->entries--; 18339212Sgibbs if (queue->entries != index) { 18439212Sgibbs queue->queue_array[index] = queue->queue_array[queue->entries]; 18539212Sgibbs queue->queue_array[index]->index = index; 18639212Sgibbs heap_down(queue->queue_array, index, queue->entries); 18739212Sgibbs } 18839212Sgibbs removed_entry->index = CAM_UNQUEUED_INDEX; 18939212Sgibbs return (removed_entry); 19039212Sgibbs} 19139212Sgibbs 19239212Sgibbs/* 19339212Sgibbs * camq_change_priority: Given an array of cam_pinfo* elements with the 19439212Sgibbs * Heap(0, num_entries) property, an index such that 0 <= index <= num_elements, 19539212Sgibbs * and an new priority for the element at index, change the priority of 19639212Sgibbs * element index and restore the Heap(0, num_elements) property. 19739212Sgibbs */ 19839212Sgibbsvoid 19939212Sgibbscamq_change_priority(struct camq *queue, int index, u_int32_t new_priority) 20039212Sgibbs{ 20139212Sgibbs if (new_priority > queue->queue_array[index]->priority) { 20239212Sgibbs queue->queue_array[index]->priority = new_priority; 20339212Sgibbs heap_down(queue->queue_array, index, queue->entries); 20439212Sgibbs } else { 20539212Sgibbs /* new_priority <= old_priority */ 20639212Sgibbs queue->queue_array[index]->priority = new_priority; 20739212Sgibbs heap_up(queue->queue_array, index); 20839212Sgibbs } 20939212Sgibbs} 21039212Sgibbs 21139212Sgibbsstruct cam_devq * 21239212Sgibbscam_devq_alloc(int devices, int openings) 21339212Sgibbs{ 21439212Sgibbs struct cam_devq *devq; 21539212Sgibbs 21639212Sgibbs devq = (struct cam_devq *)malloc(sizeof(*devq), M_DEVBUF, M_NOWAIT); 21739212Sgibbs if (devq == NULL) { 21839212Sgibbs printf("cam_devq_alloc: - cannot malloc!\n"); 21939212Sgibbs return (NULL); 22039212Sgibbs } 22139212Sgibbs if (cam_devq_init(devq, devices, openings) != 0) { 22239212Sgibbs free(devq, M_DEVBUF); 22339212Sgibbs return (NULL); 22439212Sgibbs } 22539212Sgibbs 22639212Sgibbs return (devq); 22739212Sgibbs} 22839212Sgibbs 22939212Sgibbsint 23039212Sgibbscam_devq_init(struct cam_devq *devq, int devices, int openings) 23139212Sgibbs{ 23239212Sgibbs bzero(devq, sizeof(*devq)); 23339212Sgibbs if (camq_init(&devq->alloc_queue, devices) != 0) { 23439212Sgibbs return (1); 23539212Sgibbs } 23639212Sgibbs if (camq_init(&devq->send_queue, devices) != 0) { 23739212Sgibbs camq_fini(&devq->alloc_queue); 23839212Sgibbs return (1); 23939212Sgibbs } 24039212Sgibbs devq->alloc_openings = openings; 24139212Sgibbs devq->alloc_active = 0; 24239212Sgibbs devq->send_openings = openings; 24339212Sgibbs devq->send_active = 0; 24439212Sgibbs return (0); 24539212Sgibbs} 24639212Sgibbs 24739212Sgibbsvoid 24839212Sgibbscam_devq_free(struct cam_devq *devq) 24939212Sgibbs{ 25039212Sgibbs camq_free(&devq->alloc_queue); 25139212Sgibbs camq_free(&devq->send_queue); 25239212Sgibbs free(devq, M_DEVBUF); 25339212Sgibbs} 25439212Sgibbs 25539212Sgibbsu_int32_t 25639212Sgibbscam_devq_resize(struct cam_devq *camq, int devices) 25739212Sgibbs{ 25839212Sgibbs u_int32_t retval; 25939212Sgibbs 26039212Sgibbs retval = camq_resize(&camq->alloc_queue, devices); 26139212Sgibbs 26239212Sgibbs if (retval == CAM_REQ_CMP) 26339212Sgibbs retval = camq_resize(&camq->send_queue, devices); 26439212Sgibbs 26539212Sgibbs return (retval); 26639212Sgibbs} 26739212Sgibbs 26839212Sgibbsstruct cam_ccbq * 26939212Sgibbscam_ccbq_alloc(int openings) 27039212Sgibbs{ 27139212Sgibbs struct cam_ccbq *ccbq; 27239212Sgibbs 27339212Sgibbs ccbq = (struct cam_ccbq *)malloc(sizeof(*ccbq), M_DEVBUF, M_NOWAIT); 27439212Sgibbs if (ccbq == NULL) { 27539212Sgibbs printf("cam_ccbq_alloc: - cannot malloc!\n"); 27639212Sgibbs return (NULL); 27739212Sgibbs } 27839212Sgibbs if (cam_ccbq_init(ccbq, openings) != 0) { 27939212Sgibbs free(ccbq, M_DEVBUF); 28039212Sgibbs return (NULL); 28139212Sgibbs } 28239212Sgibbs 28339212Sgibbs return (ccbq); 28439212Sgibbs} 28539212Sgibbs 28639212Sgibbsvoid 28739212Sgibbscam_ccbq_free(struct cam_ccbq *ccbq) 28839212Sgibbs{ 28939212Sgibbs if (ccbq) { 29039212Sgibbs camq_fini(&ccbq->queue); 29139212Sgibbs free(ccbq, M_DEVBUF); 29239212Sgibbs } 29339212Sgibbs} 29439212Sgibbs 29539212Sgibbsu_int32_t 29639212Sgibbscam_ccbq_resize(struct cam_ccbq *ccbq, int new_size) 29739212Sgibbs{ 29839212Sgibbs int delta; 29939212Sgibbs int space_left; 30039212Sgibbs 30139212Sgibbs delta = new_size - (ccbq->dev_active + ccbq->dev_openings); 30239212Sgibbs space_left = new_size 30339212Sgibbs - ccbq->queue.entries 30439212Sgibbs - ccbq->held 30539212Sgibbs - ccbq->dev_active; 30639212Sgibbs 30739212Sgibbs /* 30839212Sgibbs * Only attempt to change the underlying queue size if we are 30939212Sgibbs * shrinking it and there is space for all outstanding entries 31039212Sgibbs * in the new array or we have been requested to grow the array. 31139212Sgibbs * We don't fail in the case where we can't reduce the array size, 31239212Sgibbs * but clients that care that the queue be "garbage collected" 31339212Sgibbs * should detect this condition and call us again with the 31439212Sgibbs * same size once the outstanding entries have been processed. 31539212Sgibbs */ 31639212Sgibbs if (space_left < 0 31739212Sgibbs || camq_resize(&ccbq->queue, new_size) == CAM_REQ_CMP) { 31839212Sgibbs ccbq->devq_openings += delta; 31939212Sgibbs ccbq->dev_openings += delta; 32039212Sgibbs return (CAM_REQ_CMP); 32139212Sgibbs } else { 32239212Sgibbs return (CAM_RESRC_UNAVAIL); 32339212Sgibbs } 32439212Sgibbs} 32539212Sgibbs 32639212Sgibbsint 32739212Sgibbscam_ccbq_init(struct cam_ccbq *ccbq, int openings) 32839212Sgibbs{ 32939212Sgibbs bzero(ccbq, sizeof(*ccbq)); 33039212Sgibbs if (camq_init(&ccbq->queue, openings) != 0) { 33139212Sgibbs return (1); 33239212Sgibbs } 33339212Sgibbs ccbq->devq_openings = openings; 33439212Sgibbs ccbq->dev_openings = openings; 33539212Sgibbs TAILQ_INIT(&ccbq->active_ccbs); 33639212Sgibbs return (0); 33739212Sgibbs} 33839212Sgibbs 33939212Sgibbsvoid 34039212Sgibbscam_ccbq_regen(struct cam_ccbq *ccbq) 34139212Sgibbs{ 34239212Sgibbs struct ccb_hdr *ccbh; 34339212Sgibbs 34439212Sgibbs /* First get all of the guys down at a device */ 34539212Sgibbs ccbh = ccbq->active_ccbs.tqh_first; 34639212Sgibbs 34739212Sgibbs while (ccbh != NULL) { 34839212Sgibbs ccbh->pinfo.generation = ccbq->queue.generation++; 34939212Sgibbs ccbh = ccbh->xpt_links.tqe.tqe_next; 35039212Sgibbs } 35139212Sgibbs 35239212Sgibbs /* Now get everyone in our CAM queue */ 35339212Sgibbs camq_regen(&ccbq->queue); 35439212Sgibbs} 35539212Sgibbs 35639212Sgibbs/* 35739212Sgibbs * Heap routines for manipulating CAM queues. 35839212Sgibbs */ 35939212Sgibbs/* 36039212Sgibbs * queue_cmp: Given an array of cam_pinfo* elements and indexes i 36139212Sgibbs * and j, return less than 0, 0, or greater than 0 if i is less than, 36239212Sgibbs * equal too, or greater than j respectively. 36339212Sgibbs */ 36439212Sgibbsstatic __inline int 36539212Sgibbsqueue_cmp(cam_pinfo **queue_array, int i, int j) 36639212Sgibbs{ 36739212Sgibbs if (queue_array[i]->priority == queue_array[j]->priority) 36839212Sgibbs return ( queue_array[i]->generation 36939212Sgibbs - queue_array[j]->generation ); 37039212Sgibbs else 37139212Sgibbs return ( queue_array[i]->priority 37239212Sgibbs - queue_array[j]->priority ); 37339212Sgibbs} 37439212Sgibbs 37539212Sgibbs/* 37639212Sgibbs * swap: Given an array of cam_pinfo* elements and indexes i and j, 37739212Sgibbs * exchange elements i and j. 37839212Sgibbs */ 37939212Sgibbsstatic __inline void 38039212Sgibbsswap(cam_pinfo **queue_array, int i, int j) 38139212Sgibbs{ 38239212Sgibbs cam_pinfo *temp_qentry; 38339212Sgibbs 38439212Sgibbs temp_qentry = queue_array[j]; 38539212Sgibbs queue_array[j] = queue_array[i]; 38639212Sgibbs queue_array[i] = temp_qentry; 38739212Sgibbs queue_array[j]->index = j; 38839212Sgibbs queue_array[i]->index = i; 38939212Sgibbs} 39039212Sgibbs 39139212Sgibbs/* 39239212Sgibbs * heap_up: Given an array of cam_pinfo* elements with the 39339212Sgibbs * Heap(0, new_index-1) property and a new element in location 39439212Sgibbs * new_index, output Heap(0, new_index). 39539212Sgibbs */ 39639212Sgibbsstatic void 39739212Sgibbsheap_up(cam_pinfo **queue_array, int new_index) 39839212Sgibbs{ 39939212Sgibbs int child; 40039212Sgibbs int parent; 40139212Sgibbs 40239212Sgibbs child = new_index; 40339212Sgibbs 40439212Sgibbs while (child != 0) { 40539212Sgibbs 40639212Sgibbs parent = child >> 1; 40739212Sgibbs if (queue_cmp(queue_array, parent, child) <= 0) 40839212Sgibbs break; 40939212Sgibbs swap(queue_array, parent, child); 41039212Sgibbs child = parent; 41139212Sgibbs } 41239212Sgibbs} 41339212Sgibbs 41439212Sgibbs/* 41539212Sgibbs * heap_down: Given an array of cam_pinfo* elements with the 41639212Sgibbs * Heap(1, num_entries - 1) property with index 0 containing an unsorted 41739212Sgibbs * entry, output Heap(0, num_entries - 1). 41839212Sgibbs */ 41939212Sgibbsstatic void 42039212Sgibbsheap_down(cam_pinfo **queue_array, int index, int num_entries) 42139212Sgibbs{ 42239212Sgibbs int child; 42339212Sgibbs int parent; 42439212Sgibbs 42539212Sgibbs parent = index; 42639212Sgibbs child = parent == 0 ? 1 : parent << 1; 42739212Sgibbs for (; child < num_entries; child = parent << 1) { 42839212Sgibbs 42939212Sgibbs if (child + 1 < num_entries) { 43039212Sgibbs /* child+1 is the right child of parent */ 43139212Sgibbs if (queue_cmp(queue_array, child + 1, child) < 0) 43239212Sgibbs child++; 43339212Sgibbs } 43439212Sgibbs /* child is now the least child of parent */ 43539212Sgibbs if (queue_cmp(queue_array, parent, child) <= 0) 43639212Sgibbs break; 43739212Sgibbs swap(queue_array, child, parent); 43839212Sgibbs parent = child; 43939212Sgibbs } 44039212Sgibbs} 44139212Sgibbs 442