The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/cam/cam_queue.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /*-
    2  * CAM request queue management functions.
    3  *
    4  * Copyright (c) 1997 Justin T. Gibbs.
    5  * All rights reserved.
    6  *
    7  * Redistribution and use in source and binary forms, with or without
    8  * modification, are permitted provided that the following conditions
    9  * are met:
   10  * 1. Redistributions of source code must retain the above copyright
   11  *    notice, this list of conditions, and the following disclaimer,
   12  *    without modification, immediately at the beginning of the file.
   13  * 2. The name of the author may not be used to endorse or promote products
   14  *    derived from this software without specific prior written permission.
   15  *
   16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
   17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   19  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR
   20  * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   26  * SUCH DAMAGE.
   27  */
   28 
   29 #include <sys/cdefs.h>
   30 __FBSDID("$FreeBSD: releng/11.2/sys/cam/cam_queue.c 308352 2016-11-05 20:23:18Z markj $");
   31 
   32 #include <sys/param.h>
   33 #include <sys/systm.h>
   34 #include <sys/types.h>
   35 #include <sys/malloc.h>
   36 #include <sys/kernel.h>
   37 
   38 #include <cam/cam.h>
   39 #include <cam/cam_ccb.h>
   40 #include <cam/cam_queue.h>
   41 #include <cam/cam_debug.h>
   42 
   43 static MALLOC_DEFINE(M_CAMQ, "CAM queue", "CAM queue buffers");
   44 static MALLOC_DEFINE(M_CAMDEVQ, "CAM dev queue", "CAM dev queue buffers");
   45 static MALLOC_DEFINE(M_CAMCCBQ, "CAM ccb queue", "CAM ccb queue buffers");
   46 
   47 static __inline int
   48                 queue_cmp(cam_pinfo **queue_array, int i, int j);
   49 static __inline void
   50                 swap(cam_pinfo **queue_array, int i, int j);
   51 static void     heap_up(cam_pinfo **queue_array, int new_index);
   52 static void     heap_down(cam_pinfo **queue_array, int index,
   53                           int last_index);
   54 
   55 struct camq *
   56 camq_alloc(int size)
   57 {
   58         struct camq *camq;
   59 
   60         camq = (struct camq *)malloc(sizeof(*camq), M_CAMQ, M_NOWAIT);
   61         if (camq != NULL) {
   62                 if (camq_init(camq, size) != 0) {
   63                         free(camq, M_CAMQ);
   64                         camq = NULL;
   65                 }
   66         }
   67         return (camq);
   68 }
   69         
   70 int
   71 camq_init(struct camq *camq, int size)
   72 {
   73         bzero(camq, sizeof(*camq));
   74         camq->array_size = size;
   75         if (camq->array_size != 0) {
   76                 camq->queue_array = (cam_pinfo**)malloc(size*sizeof(cam_pinfo*),
   77                                                         M_CAMQ, M_NOWAIT);
   78                 if (camq->queue_array == NULL) {
   79                         printf("camq_init: - cannot malloc array!\n");
   80                         return (1);
   81                 }
   82                 /*
   83                  * Heap algorithms like everything numbered from 1, so
   84                  * offset our pointer into the heap array by one element.
   85                  */
   86                 camq->queue_array--;
   87         }
   88         return (0);
   89 }
   90 
   91 /*
   92  * Free a camq structure.  This should only be called if a controller
   93  * driver failes somehow during its attach routine or is unloaded and has
   94  * obtained a camq structure.  The XPT should ensure that the queue
   95  * is empty before calling this routine.
   96  */
   97 void
   98 camq_free(struct camq *queue)
   99 {
  100         if (queue != NULL) {
  101                 camq_fini(queue);
  102                 free(queue, M_CAMQ);
  103         }
  104 }
  105 
  106 void
  107 camq_fini(struct camq *queue)
  108 {
  109         if (queue->queue_array != NULL) {
  110                 /*
  111                  * Heap algorithms like everything numbered from 1, so
  112                  * our pointer into the heap array is offset by one element.
  113                  */
  114                 queue->queue_array++;
  115                 free(queue->queue_array, M_CAMQ);
  116         }
  117 }
  118 
  119 u_int32_t
  120 camq_resize(struct camq *queue, int new_size)
  121 {
  122         cam_pinfo **new_array;
  123 
  124         KASSERT(new_size >= queue->entries, ("camq_resize: "
  125             "New queue size can't accommodate queued entries (%d < %d).",
  126             new_size, queue->entries));
  127         new_array = (cam_pinfo **)malloc(new_size * sizeof(cam_pinfo *),
  128                                          M_CAMQ, M_NOWAIT);
  129         if (new_array == NULL) {
  130                 /* Couldn't satisfy request */
  131                 return (CAM_RESRC_UNAVAIL);
  132         }
  133         /*
  134          * Heap algorithms like everything numbered from 1, so
  135          * remember that our pointer into the heap array is offset
  136          * by one element.
  137          */
  138         if (queue->queue_array != NULL) {
  139                 queue->queue_array++;
  140                 bcopy(queue->queue_array, new_array,
  141                       queue->entries * sizeof(cam_pinfo *));
  142                 free(queue->queue_array, M_CAMQ);
  143         }
  144         queue->queue_array = new_array-1;
  145         queue->array_size = new_size;
  146         return (CAM_REQ_CMP);
  147 }
  148 
  149 /*
  150  * camq_insert: Given an array of cam_pinfo* elememnts with
  151  * the Heap(1, num_elements) property and array_size - num_elements >= 1,
  152  * output Heap(1, num_elements+1) including new_entry in the array.
  153  */
  154 void
  155 camq_insert(struct camq *queue, cam_pinfo *new_entry)
  156 {
  157 
  158         KASSERT(queue->entries < queue->array_size,
  159             ("camq_insert: Attempt to insert into a full queue (%d >= %d)",
  160             queue->entries, queue->array_size));
  161         queue->entries++;
  162         queue->queue_array[queue->entries] = new_entry;
  163         new_entry->index = queue->entries;
  164         if (queue->entries != 0)
  165                 heap_up(queue->queue_array, queue->entries);
  166 }
  167 
  168 /*
  169  * camq_remove:  Given an array of cam_pinfo* elevements with the
  170  * Heap(1, num_elements) property and an index such that 1 <= index <=
  171  * num_elements, remove that entry and restore the Heap(1, num_elements-1)
  172  * property.
  173  */
  174 cam_pinfo *
  175 camq_remove(struct camq *queue, int index)
  176 {
  177         cam_pinfo *removed_entry;
  178 
  179         if (index <= 0 || index > queue->entries)
  180                 panic("%s: Attempt to remove out-of-bounds index %d "
  181                     "from queue %p of size %d", __func__, index, queue,
  182                     queue->entries);
  183 
  184         removed_entry = queue->queue_array[index];
  185         if (queue->entries != index) {
  186                 queue->queue_array[index] = queue->queue_array[queue->entries];
  187                 queue->queue_array[index]->index = index;
  188                 heap_down(queue->queue_array, index, queue->entries - 1);
  189         }
  190         removed_entry->index = CAM_UNQUEUED_INDEX;
  191         queue->entries--;
  192         return (removed_entry);
  193 }
  194 
  195 /*
  196  * camq_change_priority:  Given an array of cam_pinfo* elements with the
  197  * Heap(1, num_entries) property, an index such that 1 <= index <= num_elements,
  198  * and a new priority for the element at index, change the priority of
  199  * element index and restore the Heap(0, num_elements) property.
  200  */
  201 void
  202 camq_change_priority(struct camq *queue, int index, u_int32_t new_priority)
  203 {
  204         if (new_priority > queue->queue_array[index]->priority) {
  205                 queue->queue_array[index]->priority = new_priority;
  206                 heap_down(queue->queue_array, index, queue->entries);
  207         } else {
  208                 /* new_priority <= old_priority */
  209                 queue->queue_array[index]->priority = new_priority;
  210                 heap_up(queue->queue_array, index);
  211         }
  212 }
  213 
  214 struct cam_devq *
  215 cam_devq_alloc(int devices, int openings)
  216 {
  217         struct cam_devq *devq;
  218 
  219         devq = (struct cam_devq *)malloc(sizeof(*devq), M_CAMDEVQ, M_NOWAIT);
  220         if (devq == NULL) {
  221                 printf("cam_devq_alloc: - cannot malloc!\n");
  222                 return (NULL);
  223         }
  224         if (cam_devq_init(devq, devices, openings) != 0) {
  225                 free(devq, M_CAMDEVQ);
  226                 return (NULL);
  227         }
  228         return (devq);
  229 }
  230 
  231 int
  232 cam_devq_init(struct cam_devq *devq, int devices, int openings)
  233 {
  234 
  235         bzero(devq, sizeof(*devq));
  236         mtx_init(&devq->send_mtx, "CAM queue lock", NULL, MTX_DEF);
  237         if (camq_init(&devq->send_queue, devices) != 0)
  238                 return (1);
  239         devq->send_openings = openings;
  240         devq->send_active = 0;
  241         return (0);
  242 }
  243 
  244 void
  245 cam_devq_free(struct cam_devq *devq)
  246 {
  247 
  248         camq_fini(&devq->send_queue);
  249         mtx_destroy(&devq->send_mtx);
  250         free(devq, M_CAMDEVQ);
  251 }
  252 
  253 u_int32_t
  254 cam_devq_resize(struct cam_devq *camq, int devices)
  255 {
  256         u_int32_t retval;
  257 
  258         retval = camq_resize(&camq->send_queue, devices);
  259         return (retval);
  260 }
  261 
  262 struct cam_ccbq *
  263 cam_ccbq_alloc(int openings)
  264 {
  265         struct cam_ccbq *ccbq;
  266 
  267         ccbq = (struct cam_ccbq *)malloc(sizeof(*ccbq), M_CAMCCBQ, M_NOWAIT);
  268         if (ccbq == NULL) {
  269                 printf("cam_ccbq_alloc: - cannot malloc!\n");
  270                 return (NULL);
  271         }
  272         if (cam_ccbq_init(ccbq, openings) != 0) {
  273                 free(ccbq, M_CAMCCBQ);
  274                 return (NULL);          
  275         }
  276         
  277         return (ccbq);
  278 }
  279 
  280 void
  281 cam_ccbq_free(struct cam_ccbq *ccbq)
  282 {
  283         if (ccbq) {
  284                 cam_ccbq_fini(ccbq);
  285                 free(ccbq, M_CAMCCBQ);
  286         }
  287 }
  288 
  289 u_int32_t
  290 cam_ccbq_resize(struct cam_ccbq *ccbq, int new_size)
  291 {
  292         int delta;
  293 
  294         delta = new_size - (ccbq->dev_active + ccbq->dev_openings);
  295         ccbq->total_openings += delta;
  296         ccbq->dev_openings += delta;
  297 
  298         new_size = imax(64, 1 << fls(new_size + new_size / 2));
  299         if (new_size > ccbq->queue.array_size)
  300                 return (camq_resize(&ccbq->queue, new_size));
  301         else
  302                 return (CAM_REQ_CMP);
  303 }
  304 
  305 int
  306 cam_ccbq_init(struct cam_ccbq *ccbq, int openings)
  307 {
  308         bzero(ccbq, sizeof(*ccbq));
  309         if (camq_init(&ccbq->queue,
  310             imax(64, 1 << fls(openings + openings / 2))) != 0)
  311                 return (1);
  312         ccbq->total_openings = openings;
  313         ccbq->dev_openings = openings;
  314         return (0);
  315 }
  316 
  317 void
  318 cam_ccbq_fini(struct cam_ccbq *ccbq)
  319 {
  320 
  321         camq_fini(&ccbq->queue);
  322 }
  323 
  324 /*
  325  * Heap routines for manipulating CAM queues.
  326  */
  327 /*
  328  * queue_cmp: Given an array of cam_pinfo* elements and indexes i
  329  * and j, return less than 0, 0, or greater than 0 if i is less than,
  330  * equal too, or greater than j respectively.
  331  */
  332 static __inline int
  333 queue_cmp(cam_pinfo **queue_array, int i, int j)
  334 {
  335         if (queue_array[i]->priority == queue_array[j]->priority)
  336                 return (  queue_array[i]->generation
  337                         - queue_array[j]->generation );
  338         else
  339                 return (  queue_array[i]->priority
  340                         - queue_array[j]->priority );
  341 }
  342 
  343 /*
  344  * swap: Given an array of cam_pinfo* elements and indexes i and j,
  345  * exchange elements i and j.
  346  */
  347 static __inline void
  348 swap(cam_pinfo **queue_array, int i, int j)
  349 {
  350         cam_pinfo *temp_qentry;
  351 
  352         temp_qentry = queue_array[j];
  353         queue_array[j] = queue_array[i];
  354         queue_array[i] = temp_qentry;
  355         queue_array[j]->index = j;
  356         queue_array[i]->index = i;
  357 }
  358 
  359 /*
  360  * heap_up:  Given an array of cam_pinfo* elements with the
  361  * Heap(1, new_index-1) property and a new element in location
  362  * new_index, output Heap(1, new_index).
  363  */
  364 static void
  365 heap_up(cam_pinfo **queue_array, int new_index)
  366 {
  367         int child;
  368         int parent;
  369 
  370         child = new_index;
  371 
  372         while (child != 1) {
  373 
  374                 parent = child >> 1;
  375                 if (queue_cmp(queue_array, parent, child) <= 0)
  376                         break;
  377                 swap(queue_array, parent, child);
  378                 child = parent;
  379         }
  380 }
  381 
  382 /*
  383  * heap_down:  Given an array of cam_pinfo* elements with the
  384  * Heap(index + 1, num_entries) property with index containing
  385  * an unsorted entry, output Heap(index, num_entries).
  386  */
  387 static void
  388 heap_down(cam_pinfo **queue_array, int index, int num_entries)
  389 {
  390         int child;
  391         int parent;
  392         
  393         parent = index;
  394         child = parent << 1;
  395         for (; child <= num_entries; child = parent << 1) {
  396 
  397                 if (child < num_entries) {
  398                         /* child+1 is the right child of parent */
  399                         if (queue_cmp(queue_array, child + 1, child) < 0)
  400                                 child++;
  401                 }
  402                 /* child is now the least child of parent */
  403                 if (queue_cmp(queue_array, parent, child) <= 0)
  404                         break;
  405                 swap(queue_array, child, parent);
  406                 parent = child;
  407         }
  408 }

Cache object: 1dae3e5c31f55d4c077a49324308799f


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.