cam_queue.c revision 198377
11541Srgrimes/*- 21541Srgrimes * CAM request queue management functions. 31541Srgrimes * 41541Srgrimes * Copyright (c) 1997 Justin T. Gibbs. 51541Srgrimes * All rights reserved. 61541Srgrimes * 71541Srgrimes * Redistribution and use in source and binary forms, with or without 81541Srgrimes * modification, are permitted provided that the following conditions 91541Srgrimes * are met: 101541Srgrimes * 1. Redistributions of source code must retain the above copyright 111541Srgrimes * notice, this list of conditions, and the following disclaimer, 121541Srgrimes * without modification, immediately at the beginning of the file. 131541Srgrimes * 2. The name of the author may not be used to endorse or promote products 141541Srgrimes * derived from this software without specific prior written permission. 151541Srgrimes * 161541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 171541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 181541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 191541Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR 201541Srgrimes * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 211541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 221541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 231541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 241541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 251541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 261541Srgrimes * SUCH DAMAGE. 271541Srgrimes */ 281541Srgrimes 291541Srgrimes#include <sys/cdefs.h> 301541Srgrimes__FBSDID("$FreeBSD: head/sys/cam/cam_queue.c 198377 2009-10-22 21:07:32Z mav $"); 311541Srgrimes 321541Srgrimes#include <sys/param.h> 331541Srgrimes#include <sys/systm.h> 341541Srgrimes#include <sys/types.h> 351541Srgrimes#include <sys/malloc.h> 361541Srgrimes#include <sys/kernel.h> 371541Srgrimes 381541Srgrimes#include <cam/cam.h> 3950477Speter#include <cam/cam_ccb.h> 401541Srgrimes#include <cam/cam_queue.h> 411541Srgrimes#include <cam/cam_debug.h> 421541Srgrimes 431541SrgrimesMALLOC_DEFINE(M_CAMQ, "CAM queue", "CAM queue buffers"); 441541SrgrimesMALLOC_DEFINE(M_CAMDEVQ, "CAM dev queue", "CAM dev queue buffers"); 451541SrgrimesMALLOC_DEFINE(M_CAMCCBQ, "CAM ccb queue", "CAM ccb queue buffers"); 4631778Seivind 4775426Srwatsonstatic __inline int 4831778Seivind queue_cmp(cam_pinfo **queue_array, int i, int j); 491541Srgrimesstatic __inline void 501541Srgrimes swap(cam_pinfo **queue_array, int i, int j); 511541Srgrimesstatic void heap_up(cam_pinfo **queue_array, int new_index); 5212221Sbdestatic void heap_down(cam_pinfo **queue_array, int index, 5341059Speter int last_index); 5470317Sjake 551541Srgrimesstruct camq * 561541Srgrimescamq_alloc(int size) 5731891Ssef{ 5865495Struckman struct camq *camq; 5961287Srwatson 6072786Srwatson camq = (struct camq *)malloc(sizeof(*camq), M_CAMQ, M_NOWAIT); 611541Srgrimes if (camq != NULL) { 6230354Sphk if (camq_init(camq, size) != 0) { 6330354Sphk free(camq, M_CAMQ); 6412221Sbde camq = NULL; 6511332Sswallace } 661541Srgrimes } 671541Srgrimes return (camq); 6812221Sbde} 691541Srgrimes 7058717Sdillonint 7170317Sjakecamq_init(struct camq *camq, int size) 7258717Sdillon{ 7370317Sjake bzero(camq, sizeof(*camq)); 741541Srgrimes camq->array_size = size; 751549Srgrimes if (camq->array_size != 0) { 7630994Sphk camq->queue_array = (cam_pinfo**)malloc(size*sizeof(cam_pinfo*), 771541Srgrimes M_CAMQ, M_NOWAIT); 7811332Sswallace if (camq->queue_array == NULL) { 791541Srgrimes printf("camq_init: - cannot malloc array!\n"); 801541Srgrimes return (1); 8130994Sphk } 821541Srgrimes /* 8374728Sjhb * Heap algorithms like everything numbered from 1, so 8430994Sphk * offset our pointer into the heap array by one element. 8574728Sjhb */ 861541Srgrimes camq->queue_array--; 871541Srgrimes } 881541Srgrimes return (0); 891541Srgrimes} 9070317Sjake 9170317Sjake/* 9270317Sjake * Free a camq structure. This should only be called if a controller 9370317Sjake * driver failes somehow during its attach routine or is unloaded and has 9412221Sbde * obtained a camq structure. The XPT should ensure that the queue 9511332Sswallace * is empty before calling this routine. 9611332Sswallace */ 9711332Sswallacevoid 9812221Sbdecamq_free(struct camq *queue) 991541Srgrimes{ 1001549Srgrimes if (queue != NULL) { 10130994Sphk camq_fini(queue); 1021541Srgrimes free(queue, M_CAMQ); 10311332Sswallace } 1041541Srgrimes} 1051541Srgrimes 10674728Sjhbvoid 10730994Sphkcamq_fini(struct camq *queue) 10874728Sjhb{ 1091541Srgrimes if (queue->queue_array != NULL) { 1101541Srgrimes /* 1111541Srgrimes * Heap algorithms like everything numbered from 1, so 11258717Sdillon * our pointer into the heap array is offset by one element. 11358717Sdillon */ 11458717Sdillon queue->queue_array++; 11558717Sdillon free(queue->queue_array, M_CAMQ); 11658717Sdillon } 11712221Sbde} 11811332Sswallace 11911332Sswallaceu_int32_t 12011332Sswallacecamq_resize(struct camq *queue, int new_size) 12112221Sbde{ 12211332Sswallace cam_pinfo **new_array; 1231549Srgrimes 12430994Sphk#ifdef DIAGNOSTIC 1251541Srgrimes if (new_size < queue->entries) 12611332Sswallace panic("camq_resize: New queue size can't accomodate " 1271541Srgrimes "queued entries."); 1281541Srgrimes#endif 12930994Sphk new_array = (cam_pinfo **)malloc(new_size * sizeof(cam_pinfo *), 1301541Srgrimes M_CAMQ, M_NOWAIT); 1311541Srgrimes if (new_array == NULL) { 1321541Srgrimes /* Couldn't satisfy request */ 13328401Speter return (CAM_RESRC_UNAVAIL); 13412221Sbde } 13528401Speter /* 13628401Speter * Heap algorithms like everything numbered from 1, so 13728401Speter * remember that our pointer into the heap array is offset 13828401Speter * by one element. 13928401Speter */ 14028401Speter if (queue->queue_array != NULL) { 14130994Sphk queue->queue_array++; 14228401Speter bcopy(queue->queue_array, new_array, 14328401Speter queue->entries * sizeof(cam_pinfo *)); 14428401Speter free(queue->queue_array, M_CAMQ); 14541726Struckman } 14675448Srwatson queue->queue_array = new_array-1; 14741726Struckman queue->array_size = new_size; 14841726Struckman return (CAM_REQ_CMP); 14928401Speter} 15028401Speter 15128401Speter/* 15241726Struckman * camq_insert: Given an array of cam_pinfo* elememnts with 15328401Speter * the Heap(1, num_elements) property and array_size - num_elements >= 1, 15475448Srwatson * output Heap(1, num_elements+1) including new_entry in the array. 15575448Srwatson */ 15628401Spetervoid 15741726Struckmancamq_insert(struct camq *queue, cam_pinfo *new_entry) 15828401Speter{ 15928401Speter#ifdef DIAGNOSTIC 16028401Speter if (queue->entries >= queue->array_size) 16128401Speter panic("camq_insert: Attempt to insert into a full queue"); 16228401Speter#endif 16328401Speter queue->entries++; 16428401Speter queue->queue_array[queue->entries] = new_entry; 16528401Speter new_entry->index = queue->entries; 16628401Speter if (queue->entries != 0) 16728401Speter heap_up(queue->queue_array, queue->entries); 16828401Speter} 16928401Speter 17028401Speter/* 17130994Sphk * camq_remove: Given an array of cam_pinfo* elevements with the 17228401Speter * Heap(1, num_elements) property and an index such that 1 <= index <= 17328401Speter * num_elements, remove that entry and restore the Heap(1, num_elements-1) 17428401Speter * property. 17541726Struckman */ 17675448Srwatsoncam_pinfo * 17741726Struckmancamq_remove(struct camq *queue, int index) 17841726Struckman{ 17928401Speter cam_pinfo *removed_entry; 18028401Speter 18128401Speter if (index == 0 || index > queue->entries) 18271002Sben return (NULL); 18328401Speter removed_entry = queue->queue_array[index]; 18475448Srwatson if (queue->entries != index) { 18575448Srwatson queue->queue_array[index] = queue->queue_array[queue->entries]; 18628401Speter queue->queue_array[index]->index = index; 18741726Struckman heap_down(queue->queue_array, index, queue->entries - 1); 18828401Speter } 18928401Speter removed_entry->index = CAM_UNQUEUED_INDEX; 19028401Speter queue->entries--; 19128401Speter return (removed_entry); 19258941Sdillon} 19358941Sdillon 19458941Sdillon/* 19528401Speter * camq_change_priority: Given an array of cam_pinfo* elements with the 19611332Sswallace * Heap(1, num_entries) property, an index such that 1 <= index <= num_elements, 19711332Sswallace * and a new priority for the element at index, change the priority of 19811332Sswallace * element index and restore the Heap(0, num_elements) property. 19912221Sbde */ 20011332Sswallacevoid 2011541Srgrimescamq_change_priority(struct camq *queue, int index, u_int32_t new_priority) 2021549Srgrimes{ 20330994Sphk if (new_priority > queue->queue_array[index]->priority) { 2041541Srgrimes queue->queue_array[index]->priority = new_priority; 20511332Sswallace heap_down(queue->queue_array, index, queue->entries); 2061541Srgrimes } else { 2071541Srgrimes /* new_priority <= old_priority */ 20830994Sphk queue->queue_array[index]->priority = new_priority; 2091541Srgrimes heap_up(queue->queue_array, index); 21030994Sphk } 2111541Srgrimes} 2121541Srgrimes 2131541Srgrimesstruct cam_devq * 2141541Srgrimescam_devq_alloc(int devices, int openings) 21558941Sdillon{ 21658941Sdillon struct cam_devq *devq; 21758941Sdillon 21812221Sbde devq = (struct cam_devq *)malloc(sizeof(*devq), M_CAMDEVQ, M_NOWAIT); 21911332Sswallace if (devq == NULL) { 22011332Sswallace printf("cam_devq_alloc: - cannot malloc!\n"); 22111332Sswallace return (NULL); 22212221Sbde } 22311332Sswallace if (cam_devq_init(devq, devices, openings) != 0) { 2241541Srgrimes free(devq, M_CAMDEVQ); 2251549Srgrimes return (NULL); 22630994Sphk } 2271541Srgrimes 22811332Sswallace return (devq); 2291541Srgrimes} 2301541Srgrimes 23130994Sphkint 2321541Srgrimescam_devq_init(struct cam_devq *devq, int devices, int openings) 2331541Srgrimes{ 2341541Srgrimes bzero(devq, sizeof(*devq)); 23558941Sdillon if (camq_init(&devq->alloc_queue, devices) != 0) { 23658941Sdillon return (1); 23758941Sdillon } 23812221Sbde if (camq_init(&devq->send_queue, devices) != 0) { 23911332Sswallace camq_fini(&devq->alloc_queue); 24011332Sswallace return (1); 24111332Sswallace } 24212221Sbde devq->alloc_openings = openings; 24311332Sswallace devq->alloc_active = 0; 2441541Srgrimes devq->send_openings = openings; 2451549Srgrimes devq->send_active = 0; 24630994Sphk return (0); 2471541Srgrimes} 24811332Sswallace 2491541Srgrimesvoid 2501541Srgrimescam_devq_free(struct cam_devq *devq) 25130994Sphk{ 2521541Srgrimes camq_fini(&devq->alloc_queue); 25330994Sphk camq_fini(&devq->send_queue); 2541541Srgrimes free(devq, M_CAMDEVQ); 2551541Srgrimes} 2561541Srgrimes 2571541Srgrimesu_int32_t 2581541Srgrimescam_devq_resize(struct cam_devq *camq, int devices) 2591541Srgrimes{ 2601541Srgrimes u_int32_t retval; 2611541Srgrimes 2621541Srgrimes retval = camq_resize(&camq->alloc_queue, devices); 26312221Sbde 26411332Sswallace if (retval == CAM_REQ_CMP) 26511332Sswallace retval = camq_resize(&camq->send_queue, devices); 26611332Sswallace 26712221Sbde return (retval); 26811332Sswallace} 2691541Srgrimes 2701549Srgrimesstruct cam_ccbq * 27130994Sphkcam_ccbq_alloc(int openings) 2721541Srgrimes{ 27311332Sswallace struct cam_ccbq *ccbq; 2741541Srgrimes 2751541Srgrimes ccbq = (struct cam_ccbq *)malloc(sizeof(*ccbq), M_CAMCCBQ, M_NOWAIT); 27630994Sphk if (ccbq == NULL) { 2771541Srgrimes printf("cam_ccbq_alloc: - cannot malloc!\n"); 2781541Srgrimes return (NULL); 2791541Srgrimes } 28012221Sbde if (cam_ccbq_init(ccbq, openings) != 0) { 2811541Srgrimes free(ccbq, M_CAMCCBQ); 2821541Srgrimes return (NULL); 2831541Srgrimes } 2841541Srgrimes 28512221Sbde return (ccbq); 2861549Srgrimes} 28730994Sphk 2881541Srgrimesvoid 2891541Srgrimescam_ccbq_free(struct cam_ccbq *ccbq) 2901541Srgrimes{ 2911541Srgrimes if (ccbq) { 2921541Srgrimes cam_ccbq_fini(ccbq); 2931541Srgrimes free(ccbq, M_CAMCCBQ); 2941541Srgrimes } 2951541Srgrimes} 29630994Sphk 2971541Srgrimesu_int32_t 2981541Srgrimescam_ccbq_resize(struct cam_ccbq *ccbq, int new_size) 2991541Srgrimes{ 3001541Srgrimes int delta; 3011541Srgrimes int space_left; 3023098Sphk 3033098Sphk delta = new_size - (ccbq->dev_active + ccbq->dev_openings); 3041541Srgrimes space_left = new_size 30530994Sphk - ccbq->queue.entries 3061541Srgrimes - ccbq->held 3071541Srgrimes - ccbq->dev_active; 3081541Srgrimes 30912221Sbde /* 31012207Sbde * Only attempt to change the underlying queue size if we are 31111332Sswallace * shrinking it and there is space for all outstanding entries 31211332Sswallace * in the new array or we have been requested to grow the array. 31312221Sbde * We don't fail in the case where we can't reduce the array size, 31411332Sswallace * but clients that care that the queue be "garbage collected" 3151541Srgrimes * should detect this condition and call us again with the 3161549Srgrimes * same size once the outstanding entries have been processed. 31730994Sphk */ 3181541Srgrimes if (space_left < 0 31912207Sbde || camq_resize(&ccbq->queue, new_size) == CAM_REQ_CMP) { 3201541Srgrimes ccbq->devq_openings += delta; 3211541Srgrimes ccbq->dev_openings += delta; 3221541Srgrimes return (CAM_REQ_CMP); 3231541Srgrimes } else { 3241541Srgrimes return (CAM_RESRC_UNAVAIL); 3251541Srgrimes } 32630994Sphk} 3271541Srgrimes 3281541Srgrimesint 3291541Srgrimescam_ccbq_init(struct cam_ccbq *ccbq, int openings) 3301541Srgrimes{ 3311541Srgrimes bzero(ccbq, sizeof(*ccbq)); 3321541Srgrimes if (camq_init(&ccbq->queue, openings) != 0) { 3331541Srgrimes return (1); 3341541Srgrimes } 3351541Srgrimes ccbq->devq_openings = openings; 3361541Srgrimes ccbq->dev_openings = openings; 3371541Srgrimes TAILQ_INIT(&ccbq->active_ccbs); 3381541Srgrimes return (0); 3391541Srgrimes} 3401541Srgrimes 3411541Srgrimesvoid 3421541Srgrimescam_ccbq_fini(struct cam_ccbq *ccbq) 3431541Srgrimes{ 34412221Sbde 3451541Srgrimes camq_fini(&ccbq->queue); 3461541Srgrimes} 3471541Srgrimes 3481541Srgrimes/* 34912221Sbde * Heap routines for manipulating CAM queues. 3501541Srgrimes */ 3511549Srgrimes/* 35230994Sphk * queue_cmp: Given an array of cam_pinfo* elements and indexes i 3531541Srgrimes * and j, return less than 0, 0, or greater than 0 if i is less than, 3541541Srgrimes * equal too, or greater than j respectively. 3551541Srgrimes */ 3561541Srgrimesstatic __inline int 3571541Srgrimesqueue_cmp(cam_pinfo **queue_array, int i, int j) 35875448Srwatson{ 3591541Srgrimes if (queue_array[i]->priority == queue_array[j]->priority) 36020677Sbde return ( queue_array[i]->generation 36120677Sbde - queue_array[j]->generation ); 3621541Srgrimes else 3631541Srgrimes return ( queue_array[i]->priority 3641541Srgrimes - queue_array[j]->priority ); 36575448Srwatson} 36675448Srwatson 36715985Sdg/* 3681541Srgrimes * swap: Given an array of cam_pinfo* elements and indexes i and j, 3691541Srgrimes * exchange elements i and j. 3701541Srgrimes */ 3711541Srgrimesstatic __inline void 3721541Srgrimesswap(cam_pinfo **queue_array, int i, int j) 3731541Srgrimes{ 3741541Srgrimes cam_pinfo *temp_qentry; 3751541Srgrimes 3761541Srgrimes temp_qentry = queue_array[j]; 3771541Srgrimes queue_array[j] = queue_array[i]; 3781541Srgrimes queue_array[i] = temp_qentry; 3791541Srgrimes queue_array[j]->index = j; 3801541Srgrimes queue_array[i]->index = i; 3811541Srgrimes} 3821541Srgrimes 3831541Srgrimes/* 38424448Speter * heap_up: Given an array of cam_pinfo* elements with the 38524448Speter * Heap(1, new_index-1) property and a new element in location 38672093Sasmodai * new_index, output Heap(1, new_index). 38724448Speter */ 38824448Speterstatic void 38924448Speterheap_up(cam_pinfo **queue_array, int new_index) 39024448Speter{ 39124448Speter int child; 39224448Speter int parent; 39324448Speter 39424448Speter child = new_index; 39524448Speter 39612221Sbde while (child != 1) { 3971541Srgrimes 3981541Srgrimes parent = child >> 1; 3991541Srgrimes if (queue_cmp(queue_array, parent, child) <= 0) 40012221Sbde break; 4011541Srgrimes swap(queue_array, parent, child); 4021549Srgrimes child = parent; 40330994Sphk } 4041541Srgrimes} 4051541Srgrimes 4061541Srgrimes/* 4071541Srgrimes * heap_down: Given an array of cam_pinfo* elements with the 4081541Srgrimes * Heap(index + 1, num_entries) property with index containing 4091541Srgrimes * an unsorted entry, output Heap(index, num_entries). 4101541Srgrimes */ 41124448Speterstatic void 41224448Speterheap_down(cam_pinfo **queue_array, int index, int num_entries) 41324448Speter{ 41424448Speter int child; 41524448Speter int parent; 41672093Sasmodai 41724448Speter parent = index; 41824448Speter child = parent << 1; 41924448Speter for (; child <= num_entries; child = parent << 1) { 42024448Speter 42124448Speter if (child < num_entries) { 42224448Speter /* child+1 is the right child of parent */ 42324448Speter if (queue_cmp(queue_array, child + 1, child) < 0) 42424448Speter child++; 42524448Speter } 42624448Speter /* child is now the least child of parent */ 42724448Speter if (queue_cmp(queue_array, parent, child) <= 0) 4281541Srgrimes break; 42924448Speter swap(queue_array, child, parent); 43017994Sache parent = child; 43124448Speter } 43217994Sache} 43324448Speter