1 /* $NetBSD: rf_fifo.c,v 1.8 2002/09/17 03:43:34 oster 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.8 2002/09/17 03:43:34 oster 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(sectPerDisk, clList, listp) 57 RF_SectorCount_t sectPerDisk; 58 RF_AllocListElem_t *clList; 59 RF_ShutdownList_t **listp; 60 { 61 RF_FifoHeader_t *q; 62 63 RF_CallocAndAdd(q, 1, sizeof(RF_FifoHeader_t), (RF_FifoHeader_t *), clList); 64 q->hq_count = q->lq_count = 0; 65 return ((void *) q); 66 } 67 68 void 69 rf_FifoEnqueue(q_in, elem, priority) 70 void *q_in; 71 RF_DiskQueueData_t *elem; 72 int priority; 73 { 74 RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in; 75 76 RF_ASSERT(priority == RF_IO_NORMAL_PRIORITY || priority == RF_IO_LOW_PRIORITY); 77 78 elem->next = NULL; 79 if (priority == RF_IO_NORMAL_PRIORITY) { 80 if (!q->hq_tail) { 81 RF_ASSERT(q->hq_count == 0 && q->hq_head == NULL); 82 q->hq_head = q->hq_tail = elem; 83 } else { 84 RF_ASSERT(q->hq_count != 0 && q->hq_head != NULL); 85 q->hq_tail->next = elem; 86 q->hq_tail = elem; 87 } 88 q->hq_count++; 89 } else { 90 RF_ASSERT(elem->next == NULL); 91 #if RF_DEBUG_QUEUE 92 if (rf_fifoDebug) { 93 printf("raid%d: fifo: ENQ lopri\n", 94 elem->raidPtr->raidid); 95 } 96 #endif 97 if (!q->lq_tail) { 98 RF_ASSERT(q->lq_count == 0 && q->lq_head == NULL); 99 q->lq_head = q->lq_tail = elem; 100 } else { 101 RF_ASSERT(q->lq_count != 0 && q->lq_head != NULL); 102 q->lq_tail->next = elem; 103 q->lq_tail = elem; 104 } 105 q->lq_count++; 106 } 107 if ((q->hq_count + q->lq_count) != elem->queue->queueLength) { 108 printf("Queue lengths differ!: %d %d %d\n", 109 q->hq_count, q->lq_count, (int) elem->queue->queueLength); 110 printf("%d %d %d %d\n", 111 (int) elem->queue->numOutstanding, 112 (int) elem->queue->maxOutstanding, 113 (int) elem->queue->row, 114 (int) elem->queue->col); 115 } 116 RF_ASSERT((q->hq_count + q->lq_count) == elem->queue->queueLength); 117 } 118 119 RF_DiskQueueData_t * 120 rf_FifoDequeue(q_in) 121 void *q_in; 122 { 123 RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in; 124 RF_DiskQueueData_t *nd; 125 126 RF_ASSERT(q); 127 if (q->hq_head) { 128 RF_ASSERT(q->hq_count != 0 && q->hq_tail != NULL); 129 nd = q->hq_head; 130 q->hq_head = q->hq_head->next; 131 if (!q->hq_head) 132 q->hq_tail = NULL; 133 nd->next = NULL; 134 q->hq_count--; 135 } else 136 if (q->lq_head) { 137 RF_ASSERT(q->lq_count != 0 && q->lq_tail != NULL); 138 nd = q->lq_head; 139 q->lq_head = q->lq_head->next; 140 if (!q->lq_head) 141 q->lq_tail = NULL; 142 nd->next = NULL; 143 q->lq_count--; 144 #if RF_DEBUG_QUEUE 145 if (rf_fifoDebug) { 146 printf("raid%d: fifo: DEQ lopri %lx\n", 147 nd->raidPtr->raidid, (long) nd); 148 } 149 #endif 150 } else { 151 RF_ASSERT(q->hq_count == 0 && q->lq_count == 0 && q->hq_tail == NULL && q->lq_tail == NULL); 152 nd = NULL; 153 } 154 return (nd); 155 } 156 157 /* Return ptr to item at head of queue. Used to examine request 158 * info without actually dequeueing the request. 159 */ 160 RF_DiskQueueData_t * 161 rf_FifoPeek(void *q_in) 162 { 163 RF_DiskQueueData_t *headElement = NULL; 164 RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in; 165 166 RF_ASSERT(q); 167 if (q->hq_head) 168 headElement = q->hq_head; 169 else 170 if (q->lq_head) 171 headElement = q->lq_head; 172 return (headElement); 173 } 174 /* We sometimes need to promote a low priority access to a regular priority access. 175 * Currently, this is only used when the user wants to write a stripe which is currently 176 * under reconstruction. 177 * This routine will promote all accesses tagged with the indicated parityStripeID from 178 * the low priority queue to the end of the normal priority queue. 179 * We assume the queue is locked upon entry. 180 */ 181 int 182 rf_FifoPromote(q_in, parityStripeID, which_ru) 183 void *q_in; 184 RF_StripeNum_t parityStripeID; 185 RF_ReconUnitNum_t which_ru; 186 { 187 RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in; 188 RF_DiskQueueData_t *lp = q->lq_head, *pt = NULL; /* lp = lo-pri queue 189 * pointer, pt = trailer */ 190 int retval = 0; 191 192 while (lp) { 193 194 /* search for the indicated parity stripe in the low-pri queue */ 195 if (lp->parityStripeID == parityStripeID && lp->which_ru == which_ru) { 196 /* printf("FifoPromote: promoting access for psid 197 * %ld\n",parityStripeID); */ 198 if (pt) 199 pt->next = lp->next; /* delete an entry other 200 * than the first */ 201 else 202 q->lq_head = lp->next; /* delete the head entry */ 203 204 if (!q->lq_head) 205 q->lq_tail = NULL; /* we deleted the only 206 * entry */ 207 else 208 if (lp == q->lq_tail) 209 q->lq_tail = pt; /* we deleted the tail 210 * entry */ 211 212 lp->next = NULL; 213 q->lq_count--; 214 215 if (q->hq_tail) { 216 q->hq_tail->next = lp; 217 q->hq_tail = lp; 218 } 219 /* append to hi-priority queue */ 220 else { 221 q->hq_head = q->hq_tail = lp; 222 } 223 q->hq_count++; 224 225 /* UpdateShortestSeekFinishTimeForced(lp->requestPtr, 226 * lp->diskState); *//* deal with this later, if ever */ 227 228 lp = (pt) ? pt->next : q->lq_head; /* reset low-pri pointer 229 * and continue */ 230 retval++; 231 232 } else { 233 pt = lp; 234 lp = lp->next; 235 } 236 } 237 238 /* sanity check. delete this if you ever put more than one entry in 239 * the low-pri queue */ 240 RF_ASSERT(retval == 0 || retval == 1); 241 return (retval); 242 } 243