sys/dev/raidframe/rf_fifo.c

   1 /*      $NetBSD: rf_fifo.c,v 1.14 2006/10/12 01:31:51 christos Exp $    */
   2 /*
   3  * Copyright (c) 1995 Carnegie-Mellon University.
   4  * All rights reserved.
   5  *
   6  * Author: Mark Holland
   7  *
   8  * Permission to use, copy, modify and distribute this software and
   9  * its documentation is hereby granted, provided that both the copyright
  10  * notice and this permission notice appear in all copies of the
  11  * software, derivative works or modified versions, and any portions
  12  * thereof, and that both notices appear in supporting documentation.
  13  *
  14  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
  15  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
  16  * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  17  *
  18  * Carnegie Mellon requests users of this software to return to
  19  *
  20  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
  21  *  School of Computer Science
  22  *  Carnegie Mellon University
  23  *  Pittsburgh PA 15213-3890
  24  *
  25  * any improvements or extensions that they make and grant Carnegie the
  26  * rights to redistribute these changes.
  27  */
  28
  29 /***************************************************
  30  *
  31  * rf_fifo.c --  prioritized fifo queue code.
  32  * There are only two priority levels: hi and lo.
  33  *
  34  * Aug 4, 1994, adapted from raidSim version (MCH)
  35  *
  36  ***************************************************/
  37
  38 #include <sys/cdefs.h>
  39 __KERNEL_RCSID(0, "$NetBSD: rf_fifo.c,v 1.14 2006/10/12 01:31:51 christos Exp $");
  40
  41 #include <dev/raidframe/raidframevar.h>
  42
  43 #include "rf_alloclist.h"
  44 #include "rf_stripelocks.h"
  45 #include "rf_layout.h"
  46 #include "rf_diskqueue.h"
  47 #include "rf_fifo.h"
  48 #include "rf_debugMem.h"
  49 #include "rf_general.h"
  50 #include "rf_options.h"
  51 #include "rf_raid.h"
  52
  53 /* just malloc a header, zero it (via calloc), and return it */
  54 /*ARGSUSED*/
  55 void   *
  56 rf_FifoCreate(RF_SectorCount_t sectPerDisk, RF_AllocListElem_t *clList,
  57               RF_ShutdownList_t **listp)
  58 {
  59         RF_FifoHeader_t *q;
  60
  61         RF_MallocAndAdd(q, sizeof(RF_FifoHeader_t),
  62                                 (RF_FifoHeader_t *), clList);
  63         q->hq_count = q->lq_count = 0;
  64         return ((void *) q);
  65 }
  66
  67 void
  68 rf_FifoEnqueue(void *q_in, RF_DiskQueueData_t *elem, int priority)
  69 {
  70         RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in;
  71
  72         RF_ASSERT(priority == RF_IO_NORMAL_PRIORITY || priority == RF_IO_LOW_PRIORITY);
  73
  74         elem->next = NULL;
  75         if (priority == RF_IO_NORMAL_PRIORITY) {
  76                 if (!q->hq_tail) {
  77                         RF_ASSERT(q->hq_count == 0 && q->hq_head == NULL);
  78                         q->hq_head = q->hq_tail = elem;
  79                 } else {
  80                         RF_ASSERT(q->hq_count != 0 && q->hq_head != NULL);
  81                         q->hq_tail->next = elem;
  82                         q->hq_tail = elem;
  83                 }
  84                 q->hq_count++;
  85         } else {
  86                 RF_ASSERT(elem->next == NULL);
  87 #if RF_DEBUG_QUEUE
  88                 if (rf_fifoDebug) {
  89                         printf("raid%d: fifo: ENQ lopri\n",
  90                                elem->raidPtr->raidid);
  91                 }
  92 #endif
  93                 if (!q->lq_tail) {
  94                         RF_ASSERT(q->lq_count == 0 && q->lq_head == NULL);
  95                         q->lq_head = q->lq_tail = elem;
  96                 } else {
  97                         RF_ASSERT(q->lq_count != 0 && q->lq_head != NULL);
  98                         q->lq_tail->next = elem;
  99                         q->lq_tail = elem;
 100                 }
 101                 q->lq_count++;
 102         }
 103         if ((q->hq_count + q->lq_count) != elem->queue->queueLength) {
 104                 printf("Queue lengths differ!: %d %d %d\n",
 105                     q->hq_count, q->lq_count, (int) elem->queue->queueLength);
 106                 printf("%d %d %d\n",
 107                     (int) elem->queue->numOutstanding,
 108                     (int) elem->queue->maxOutstanding,
 109                     (int) elem->queue->col);
 110         }
 111         RF_ASSERT((q->hq_count + q->lq_count) == elem->queue->queueLength);
 112 }
 113
 114 RF_DiskQueueData_t *
 115 rf_FifoDequeue(void *q_in)
 116 {
 117         RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in;
 118         RF_DiskQueueData_t *nd;
 119
 120         RF_ASSERT(q);
 121         if (q->hq_head) {
 122                 RF_ASSERT(q->hq_count != 0 && q->hq_tail != NULL);
 123                 nd = q->hq_head;
 124                 q->hq_head = q->hq_head->next;
 125                 if (!q->hq_head)
 126                         q->hq_tail = NULL;
 127                 nd->next = NULL;
 128                 q->hq_count--;
 129         } else
 130                 if (q->lq_head) {
 131                         RF_ASSERT(q->lq_count != 0 && q->lq_tail != NULL);
 132                         nd = q->lq_head;
 133                         q->lq_head = q->lq_head->next;
 134                         if (!q->lq_head)
 135                                 q->lq_tail = NULL;
 136                         nd->next = NULL;
 137                         q->lq_count--;
 138 #if RF_DEBUG_QUEUE
 139                         if (rf_fifoDebug) {
 140                                 printf("raid%d: fifo: DEQ lopri %lx\n",
 141                                        nd->raidPtr->raidid, (long) nd);
 142                         }
 143 #endif
 144                 } else {
 145                         RF_ASSERT(q->hq_count == 0 && q->lq_count == 0 && q->hq_tail == NULL && q->lq_tail == NULL);
 146                         nd = NULL;
 147                 }
 148         return (nd);
 149 }
 150
 151 /* Return ptr to item at head of queue.  Used to examine request
 152  * info without actually dequeueing the request.
 153  */
 154 RF_DiskQueueData_t *
 155 rf_FifoPeek(void *q_in)
 156 {
 157         RF_DiskQueueData_t *headElement = NULL;
 158         RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in;
 159
 160         RF_ASSERT(q);
 161         if (q->hq_head)
 162                 headElement = q->hq_head;
 163         else
 164                 if (q->lq_head)
 165                         headElement = q->lq_head;
 166         return (headElement);
 167 }
 168 /* We sometimes need to promote a low priority access to a regular priority access.
 169  * Currently, this is only used when the user wants to write a stripe which is currently
 170  * under reconstruction.
 171  * This routine will promote all accesses tagged with the indicated parityStripeID from
 172  * the low priority queue to the end of the normal priority queue.
 173  * We assume the queue is locked upon entry.
 174  */
 175 int
 176 rf_FifoPromote(void *q_in, RF_StripeNum_t parityStripeID,
 177                RF_ReconUnitNum_t which_ru)
 178 {
 179         RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in;
 180         RF_DiskQueueData_t *lp = q->lq_head, *pt = NULL;        /* lp = lo-pri queue
 181                                                                  * pointer, pt = trailer */
 182         int     retval = 0;
 183
 184         while (lp) {
 185
 186                 /* search for the indicated parity stripe in the low-pri queue */
 187                 if (lp->parityStripeID == parityStripeID && lp->which_ru == which_ru) {
 188                         /* printf("FifoPromote:  promoting access for psid
 189                          * %ld\n",parityStripeID); */
 190                         if (pt)
 191                                 pt->next = lp->next;    /* delete an entry other
 192                                                          * than the first */
 193                         else
 194                                 q->lq_head = lp->next;  /* delete the head entry */
 195
 196                         if (!q->lq_head)
 197                                 q->lq_tail = NULL;      /* we deleted the only
 198                                                          * entry */
 199                         else
 200                                 if (lp == q->lq_tail)
 201                                         q->lq_tail = pt;        /* we deleted the tail
 202                                                                  * entry */
 203
 204                         lp->next = NULL;
 205                         q->lq_count--;
 206
 207                         if (q->hq_tail) {
 208                                 q->hq_tail->next = lp;
 209                                 q->hq_tail = lp;
 210                         }
 211                          /* append to hi-priority queue */
 212                         else {
 213                                 q->hq_head = q->hq_tail = lp;
 214                         }
 215                         q->hq_count++;
 216
 217                         /* UpdateShortestSeekFinishTimeForced(lp->requestPtr,
 218                          * lp->diskState); *//* deal with this later, if ever */
 219
 220                         lp = (pt) ? pt->next : q->lq_head;      /* reset low-pri pointer
 221                                                                  * and continue */
 222                         retval++;
 223
 224                 } else {
 225                         pt = lp;
 226                         lp = lp->next;
 227                 }
 228         }
 229
 230         /* sanity check.  delete this if you ever put more than one entry in
 231          * the low-pri queue */
 232         RF_ASSERT(retval == 0 || retval == 1);
 233         return (retval);
 234 }