cam_queue.c revision 139743
1139743Simp/*- 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 */ 28116161Sobrien 29116161Sobrien#include <sys/cdefs.h> 30116161Sobrien__FBSDID("$FreeBSD: head/sys/cam/cam_queue.c 139743 2005-01-05 22:34:37Z imp $"); 31116161Sobrien 3239212Sgibbs#include <sys/param.h> 3339212Sgibbs#include <sys/systm.h> 3439212Sgibbs#include <sys/types.h> 3539212Sgibbs#include <sys/malloc.h> 3639212Sgibbs 3739212Sgibbs#include <cam/cam.h> 3839212Sgibbs#include <cam/cam_ccb.h> 3939212Sgibbs#include <cam/cam_queue.h> 4039212Sgibbs#include <cam/cam_debug.h> 4139212Sgibbs 4239212Sgibbsstatic __inline int 4339212Sgibbs queue_cmp(cam_pinfo **queue_array, int i, int j); 4439212Sgibbsstatic __inline void 4539212Sgibbs swap(cam_pinfo **queue_array, int i, int j); 4639212Sgibbsstatic void heap_up(cam_pinfo **queue_array, int new_index); 4739212Sgibbsstatic void heap_down(cam_pinfo **queue_array, int index, 4839212Sgibbs int last_index); 4939212Sgibbs 5039212Sgibbsstruct camq * 5139212Sgibbscamq_alloc(int size) 5239212Sgibbs{ 5339212Sgibbs struct camq *camq; 5439212Sgibbs 5539212Sgibbs camq = (struct camq *)malloc(sizeof(*camq), M_DEVBUF, M_NOWAIT); 5639212Sgibbs if (camq != NULL) { 5739212Sgibbs if (camq_init(camq, size) != 0) { 5839212Sgibbs free(camq, M_DEVBUF); 5939212Sgibbs camq = NULL; 6039212Sgibbs } 6139212Sgibbs } 6239212Sgibbs return (camq); 6339212Sgibbs} 6439212Sgibbs 6539212Sgibbsint 6639212Sgibbscamq_init(struct camq *camq, int size) 6739212Sgibbs{ 6839212Sgibbs bzero(camq, sizeof(*camq)); 6939212Sgibbs camq->array_size = size; 7039212Sgibbs if (camq->array_size != 0) { 7139212Sgibbs camq->queue_array = (cam_pinfo**)malloc(size*sizeof(cam_pinfo*), 7239212Sgibbs M_DEVBUF, M_NOWAIT); 7339212Sgibbs if (camq->queue_array == NULL) { 7439212Sgibbs printf("camq_init: - cannot malloc array!\n"); 7539212Sgibbs return (1); 7639212Sgibbs } 7745844Sgibbs /* 7845844Sgibbs * Heap algorithms like everything numbered from 1, so 7945844Sgibbs * offset our pointer into the heap array by one element. 8045844Sgibbs */ 8145844Sgibbs camq->queue_array--; 8239212Sgibbs } 8339212Sgibbs return (0); 8439212Sgibbs} 8539212Sgibbs 8639212Sgibbs/* 8739212Sgibbs * Free a camq structure. This should only be called if a controller 8839212Sgibbs * driver failes somehow during its attach routine or is unloaded and has 8939212Sgibbs * obtained a camq structure. The XPT should ensure that the queue 9039212Sgibbs * is empty before calling this routine. 9139212Sgibbs */ 9239212Sgibbsvoid 9339212Sgibbscamq_free(struct camq *queue) 9439212Sgibbs{ 9539212Sgibbs if (queue != NULL) { 9639212Sgibbs camq_fini(queue); 9739212Sgibbs free(queue, M_DEVBUF); 9839212Sgibbs } 9939212Sgibbs} 10039212Sgibbs 10139212Sgibbsvoid 10239212Sgibbscamq_fini(struct camq *queue) 10339212Sgibbs{ 10439212Sgibbs if (queue->queue_array != NULL) { 10545844Sgibbs /* 10645844Sgibbs * Heap algorithms like everything numbered from 1, so 10745844Sgibbs * our pointer into the heap array is offset by one element. 10845844Sgibbs */ 10945844Sgibbs queue->queue_array++; 11039212Sgibbs free(queue->queue_array, M_DEVBUF); 11139212Sgibbs } 11239212Sgibbs} 11339212Sgibbs 11439212Sgibbsu_int32_t 11539212Sgibbscamq_resize(struct camq *queue, int new_size) 11639212Sgibbs{ 11739212Sgibbs cam_pinfo **new_array; 11839212Sgibbs 11939212Sgibbs#ifdef DIAGNOSTIC 12039212Sgibbs if (new_size < queue->entries) 12139212Sgibbs panic("camq_resize: New queue size can't accomodate " 12239212Sgibbs "queued entries."); 12339212Sgibbs#endif 12439212Sgibbs new_array = (cam_pinfo **)malloc(new_size * sizeof(cam_pinfo *), 12539212Sgibbs M_DEVBUF, M_NOWAIT); 12639212Sgibbs if (new_array == NULL) { 12739212Sgibbs /* Couldn't satisfy request */ 12839212Sgibbs return (CAM_RESRC_UNAVAIL); 12939212Sgibbs } 13045844Sgibbs /* 13145844Sgibbs * Heap algorithms like everything numbered from 1, so 13245844Sgibbs * remember that our pointer into the heap array is offset 13345844Sgibbs * by one element. 13445844Sgibbs */ 13539212Sgibbs if (queue->queue_array != NULL) { 13645844Sgibbs queue->queue_array++; 13739212Sgibbs bcopy(queue->queue_array, new_array, 13839212Sgibbs queue->entries * sizeof(cam_pinfo *)); 13939212Sgibbs free(queue->queue_array, M_DEVBUF); 14039212Sgibbs } 14145844Sgibbs queue->queue_array = new_array-1; 14239212Sgibbs queue->array_size = new_size; 14339212Sgibbs return (CAM_REQ_CMP); 14439212Sgibbs} 14539212Sgibbs 14639212Sgibbs/* 14739212Sgibbs * camq_insert: Given an array of cam_pinfo* elememnts with 14845844Sgibbs * the Heap(1, num_elements) property and array_size - num_elements >= 1, 14945844Sgibbs * output Heap(1, num_elements+1) including new_entry in the array. 15039212Sgibbs */ 15139212Sgibbsvoid 15239212Sgibbscamq_insert(struct camq *queue, cam_pinfo *new_entry) 15339212Sgibbs{ 15439212Sgibbs#ifdef DIAGNOSTIC 15539212Sgibbs if (queue->entries >= queue->array_size) 15639212Sgibbs panic("camq_insert: Attempt to insert into a full queue"); 15739212Sgibbs#endif 15845844Sgibbs queue->entries++; 15939212Sgibbs queue->queue_array[queue->entries] = new_entry; 16039212Sgibbs new_entry->index = queue->entries; 16139212Sgibbs if (queue->entries != 0) 16239212Sgibbs heap_up(queue->queue_array, queue->entries); 16339212Sgibbs} 16439212Sgibbs 16539212Sgibbs/* 16639212Sgibbs * camq_remove: Given an array of cam_pinfo* elevements with the 16745844Sgibbs * Heap(1, num_elements) property and an index such that 1 <= index <= 16845844Sgibbs * num_elements, remove that entry and restore the Heap(1, num_elements-1) 16939212Sgibbs * property. 17039212Sgibbs */ 17139212Sgibbscam_pinfo * 17239212Sgibbscamq_remove(struct camq *queue, int index) 17339212Sgibbs{ 17439212Sgibbs cam_pinfo *removed_entry; 17539212Sgibbs 17645844Sgibbs if (index == 0 || index > queue->entries) 17739212Sgibbs return (NULL); 17839212Sgibbs removed_entry = queue->queue_array[index]; 17939212Sgibbs if (queue->entries != index) { 18039212Sgibbs queue->queue_array[index] = queue->queue_array[queue->entries]; 18139212Sgibbs queue->queue_array[index]->index = index; 18245844Sgibbs heap_down(queue->queue_array, index, queue->entries - 1); 18339212Sgibbs } 18439212Sgibbs removed_entry->index = CAM_UNQUEUED_INDEX; 18545844Sgibbs queue->entries--; 18639212Sgibbs return (removed_entry); 18739212Sgibbs} 18839212Sgibbs 18939212Sgibbs/* 19039212Sgibbs * camq_change_priority: Given an array of cam_pinfo* elements with the 19145844Sgibbs * Heap(1, num_entries) property, an index such that 1 <= index <= num_elements, 192108470Sschweikh * and a new priority for the element at index, change the priority of 19339212Sgibbs * element index and restore the Heap(0, num_elements) property. 19439212Sgibbs */ 19539212Sgibbsvoid 19639212Sgibbscamq_change_priority(struct camq *queue, int index, u_int32_t new_priority) 19739212Sgibbs{ 19839212Sgibbs if (new_priority > queue->queue_array[index]->priority) { 19939212Sgibbs queue->queue_array[index]->priority = new_priority; 20039212Sgibbs heap_down(queue->queue_array, index, queue->entries); 20139212Sgibbs } else { 20239212Sgibbs /* new_priority <= old_priority */ 20339212Sgibbs queue->queue_array[index]->priority = new_priority; 20439212Sgibbs heap_up(queue->queue_array, index); 20539212Sgibbs } 20639212Sgibbs} 20739212Sgibbs 20839212Sgibbsstruct cam_devq * 20939212Sgibbscam_devq_alloc(int devices, int openings) 21039212Sgibbs{ 21139212Sgibbs struct cam_devq *devq; 21239212Sgibbs 21339212Sgibbs devq = (struct cam_devq *)malloc(sizeof(*devq), M_DEVBUF, M_NOWAIT); 21439212Sgibbs if (devq == NULL) { 21539212Sgibbs printf("cam_devq_alloc: - cannot malloc!\n"); 21639212Sgibbs return (NULL); 21739212Sgibbs } 21839212Sgibbs if (cam_devq_init(devq, devices, openings) != 0) { 21939212Sgibbs free(devq, M_DEVBUF); 22039212Sgibbs return (NULL); 22139212Sgibbs } 22239212Sgibbs 22339212Sgibbs return (devq); 22439212Sgibbs} 22539212Sgibbs 22639212Sgibbsint 22739212Sgibbscam_devq_init(struct cam_devq *devq, int devices, int openings) 22839212Sgibbs{ 22939212Sgibbs bzero(devq, sizeof(*devq)); 23039212Sgibbs if (camq_init(&devq->alloc_queue, devices) != 0) { 23139212Sgibbs return (1); 23239212Sgibbs } 23339212Sgibbs if (camq_init(&devq->send_queue, devices) != 0) { 23439212Sgibbs camq_fini(&devq->alloc_queue); 23539212Sgibbs return (1); 23639212Sgibbs } 23739212Sgibbs devq->alloc_openings = openings; 23839212Sgibbs devq->alloc_active = 0; 23939212Sgibbs devq->send_openings = openings; 24039212Sgibbs devq->send_active = 0; 24139212Sgibbs return (0); 24239212Sgibbs} 24339212Sgibbs 24439212Sgibbsvoid 24539212Sgibbscam_devq_free(struct cam_devq *devq) 24639212Sgibbs{ 24749862Sgibbs camq_fini(&devq->alloc_queue); 24849862Sgibbs camq_fini(&devq->send_queue); 24939212Sgibbs free(devq, M_DEVBUF); 25039212Sgibbs} 25139212Sgibbs 25239212Sgibbsu_int32_t 25339212Sgibbscam_devq_resize(struct cam_devq *camq, int devices) 25439212Sgibbs{ 25539212Sgibbs u_int32_t retval; 25639212Sgibbs 25739212Sgibbs retval = camq_resize(&camq->alloc_queue, devices); 25839212Sgibbs 25939212Sgibbs if (retval == CAM_REQ_CMP) 26039212Sgibbs retval = camq_resize(&camq->send_queue, devices); 26139212Sgibbs 26239212Sgibbs return (retval); 26339212Sgibbs} 26439212Sgibbs 26539212Sgibbsstruct cam_ccbq * 26639212Sgibbscam_ccbq_alloc(int openings) 26739212Sgibbs{ 26839212Sgibbs struct cam_ccbq *ccbq; 26939212Sgibbs 27039212Sgibbs ccbq = (struct cam_ccbq *)malloc(sizeof(*ccbq), M_DEVBUF, M_NOWAIT); 27139212Sgibbs if (ccbq == NULL) { 27239212Sgibbs printf("cam_ccbq_alloc: - cannot malloc!\n"); 27339212Sgibbs return (NULL); 27439212Sgibbs } 27539212Sgibbs if (cam_ccbq_init(ccbq, openings) != 0) { 27639212Sgibbs free(ccbq, M_DEVBUF); 27739212Sgibbs return (NULL); 27839212Sgibbs } 27939212Sgibbs 28039212Sgibbs return (ccbq); 28139212Sgibbs} 28239212Sgibbs 28339212Sgibbsvoid 28439212Sgibbscam_ccbq_free(struct cam_ccbq *ccbq) 28539212Sgibbs{ 28639212Sgibbs if (ccbq) { 28739212Sgibbs camq_fini(&ccbq->queue); 28839212Sgibbs free(ccbq, M_DEVBUF); 28939212Sgibbs } 29039212Sgibbs} 29139212Sgibbs 29239212Sgibbsu_int32_t 29339212Sgibbscam_ccbq_resize(struct cam_ccbq *ccbq, int new_size) 29439212Sgibbs{ 29539212Sgibbs int delta; 29639212Sgibbs int space_left; 29739212Sgibbs 29839212Sgibbs delta = new_size - (ccbq->dev_active + ccbq->dev_openings); 29939212Sgibbs space_left = new_size 30039212Sgibbs - ccbq->queue.entries 30139212Sgibbs - ccbq->held 30239212Sgibbs - ccbq->dev_active; 30339212Sgibbs 30439212Sgibbs /* 30539212Sgibbs * Only attempt to change the underlying queue size if we are 30639212Sgibbs * shrinking it and there is space for all outstanding entries 30739212Sgibbs * in the new array or we have been requested to grow the array. 30839212Sgibbs * We don't fail in the case where we can't reduce the array size, 30939212Sgibbs * but clients that care that the queue be "garbage collected" 31039212Sgibbs * should detect this condition and call us again with the 31139212Sgibbs * same size once the outstanding entries have been processed. 31239212Sgibbs */ 31339212Sgibbs if (space_left < 0 31439212Sgibbs || camq_resize(&ccbq->queue, new_size) == CAM_REQ_CMP) { 31539212Sgibbs ccbq->devq_openings += delta; 31639212Sgibbs ccbq->dev_openings += delta; 31739212Sgibbs return (CAM_REQ_CMP); 31839212Sgibbs } else { 31939212Sgibbs return (CAM_RESRC_UNAVAIL); 32039212Sgibbs } 32139212Sgibbs} 32239212Sgibbs 32339212Sgibbsint 32439212Sgibbscam_ccbq_init(struct cam_ccbq *ccbq, int openings) 32539212Sgibbs{ 32639212Sgibbs bzero(ccbq, sizeof(*ccbq)); 32739212Sgibbs if (camq_init(&ccbq->queue, openings) != 0) { 32839212Sgibbs return (1); 32939212Sgibbs } 33039212Sgibbs ccbq->devq_openings = openings; 33139212Sgibbs ccbq->dev_openings = openings; 33239212Sgibbs TAILQ_INIT(&ccbq->active_ccbs); 33339212Sgibbs return (0); 33439212Sgibbs} 33539212Sgibbs 33639212Sgibbs/* 33739212Sgibbs * Heap routines for manipulating CAM queues. 33839212Sgibbs */ 33939212Sgibbs/* 34039212Sgibbs * queue_cmp: Given an array of cam_pinfo* elements and indexes i 34139212Sgibbs * and j, return less than 0, 0, or greater than 0 if i is less than, 34239212Sgibbs * equal too, or greater than j respectively. 34339212Sgibbs */ 34439212Sgibbsstatic __inline int 34539212Sgibbsqueue_cmp(cam_pinfo **queue_array, int i, int j) 34639212Sgibbs{ 34739212Sgibbs if (queue_array[i]->priority == queue_array[j]->priority) 34839212Sgibbs return ( queue_array[i]->generation 34939212Sgibbs - queue_array[j]->generation ); 35039212Sgibbs else 35139212Sgibbs return ( queue_array[i]->priority 35239212Sgibbs - queue_array[j]->priority ); 35339212Sgibbs} 35439212Sgibbs 35539212Sgibbs/* 35639212Sgibbs * swap: Given an array of cam_pinfo* elements and indexes i and j, 35739212Sgibbs * exchange elements i and j. 35839212Sgibbs */ 35939212Sgibbsstatic __inline void 36039212Sgibbsswap(cam_pinfo **queue_array, int i, int j) 36139212Sgibbs{ 36239212Sgibbs cam_pinfo *temp_qentry; 36339212Sgibbs 36439212Sgibbs temp_qentry = queue_array[j]; 36539212Sgibbs queue_array[j] = queue_array[i]; 36639212Sgibbs queue_array[i] = temp_qentry; 36739212Sgibbs queue_array[j]->index = j; 36839212Sgibbs queue_array[i]->index = i; 36939212Sgibbs} 37039212Sgibbs 37139212Sgibbs/* 37239212Sgibbs * heap_up: Given an array of cam_pinfo* elements with the 37345844Sgibbs * Heap(1, new_index-1) property and a new element in location 37445844Sgibbs * new_index, output Heap(1, new_index). 37539212Sgibbs */ 37639212Sgibbsstatic void 37739212Sgibbsheap_up(cam_pinfo **queue_array, int new_index) 37839212Sgibbs{ 37939212Sgibbs int child; 38039212Sgibbs int parent; 38139212Sgibbs 38239212Sgibbs child = new_index; 38339212Sgibbs 38445844Sgibbs while (child != 1) { 38539212Sgibbs 38645844Sgibbs parent = child >> 1; 38739212Sgibbs if (queue_cmp(queue_array, parent, child) <= 0) 38839212Sgibbs break; 38939212Sgibbs swap(queue_array, parent, child); 39039212Sgibbs child = parent; 39139212Sgibbs } 39239212Sgibbs} 39339212Sgibbs 39439212Sgibbs/* 39539212Sgibbs * heap_down: Given an array of cam_pinfo* elements with the 39645844Sgibbs * Heap(index + 1, num_entries) property with index containing 39745844Sgibbs * an unsorted entry, output Heap(index, num_entries). 39839212Sgibbs */ 39939212Sgibbsstatic void 40039212Sgibbsheap_down(cam_pinfo **queue_array, int index, int num_entries) 40139212Sgibbs{ 40239212Sgibbs int child; 40339212Sgibbs int parent; 40439212Sgibbs 40539212Sgibbs parent = index; 40645844Sgibbs child = parent << 1; 40745844Sgibbs for (; child <= num_entries; child = parent << 1) { 40839212Sgibbs 40945844Sgibbs if (child < num_entries) { 41039212Sgibbs /* child+1 is the right child of parent */ 41139212Sgibbs if (queue_cmp(queue_array, child + 1, child) < 0) 41239212Sgibbs child++; 41339212Sgibbs } 41439212Sgibbs /* child is now the least child of parent */ 41539212Sgibbs if (queue_cmp(queue_array, parent, child) <= 0) 41639212Sgibbs break; 41739212Sgibbs swap(queue_array, child, parent); 41839212Sgibbs parent = child; 41939212Sgibbs } 42039212Sgibbs} 421