1 /* $NetBSD: rf_fifo.c,v 1.3 1999/02/05 00:06:11 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 "rf_types.h" 39 #include "rf_alloclist.h" 40 #include "rf_stripelocks.h" 41 #include "rf_layout.h" 42 #include "rf_diskqueue.h" 43 #include "rf_fifo.h" 44 #include "rf_debugMem.h" 45 #include "rf_general.h" 46 #include "rf_threadid.h" 47 #include "rf_options.h" 48 49 /* just malloc a header, zero it (via calloc), and return it */ 50 /*ARGSUSED*/ 51 void * 52 rf_FifoCreate(sectPerDisk, clList, listp) 53 RF_SectorCount_t sectPerDisk; 54 RF_AllocListElem_t *clList; 55 RF_ShutdownList_t **listp; 56 { 57 RF_FifoHeader_t *q; 58 59 RF_CallocAndAdd(q, 1, sizeof(RF_FifoHeader_t), (RF_FifoHeader_t *), clList); 60 q->hq_count = q->lq_count = 0; 61 return ((void *) q); 62 } 63 64 void 65 rf_FifoEnqueue(q_in, elem, priority) 66 void *q_in; 67 RF_DiskQueueData_t *elem; 68 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_fifoDebug) { 88 int tid; 89 rf_get_threadid(tid); 90 printf("[%d] fifo: ENQ lopri\n", tid); 91 } 92 if (!q->lq_tail) { 93 RF_ASSERT(q->lq_count == 0 && q->lq_head == NULL); 94 q->lq_head = q->lq_tail = elem; 95 } else { 96 RF_ASSERT(q->lq_count != 0 && q->lq_head != NULL); 97 q->lq_tail->next = elem; 98 q->lq_tail = elem; 99 } 100 q->lq_count++; 101 } 102 if ((q->hq_count + q->lq_count) != elem->queue->queueLength) { 103 printf("Queue lengths differ!: %d %d %d\n", 104 q->hq_count, q->lq_count, (int) elem->queue->queueLength); 105 printf("%d %d %d %d\n", 106 (int) elem->queue->numOutstanding, 107 (int) elem->queue->maxOutstanding, 108 (int) elem->queue->row, 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(q_in) 116 void *q_in; 117 { 118 RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in; 119 RF_DiskQueueData_t *nd; 120 121 RF_ASSERT(q); 122 if (q->hq_head) { 123 RF_ASSERT(q->hq_count != 0 && q->hq_tail != NULL); 124 nd = q->hq_head; 125 q->hq_head = q->hq_head->next; 126 if (!q->hq_head) 127 q->hq_tail = NULL; 128 nd->next = NULL; 129 q->hq_count--; 130 } else 131 if (q->lq_head) { 132 RF_ASSERT(q->lq_count != 0 && q->lq_tail != NULL); 133 nd = q->lq_head; 134 q->lq_head = q->lq_head->next; 135 if (!q->lq_head) 136 q->lq_tail = NULL; 137 nd->next = NULL; 138 q->lq_count--; 139 if (rf_fifoDebug) { 140 int tid; 141 rf_get_threadid(tid); 142 printf("[%d] fifo: DEQ lopri %lx\n", tid, (long) nd); 143 } 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 /* This never gets used!! No loss (I hope) if we don't include it... GO */ 151 #if !defined(__NetBSD__) && !defined(_KERNEL) 152 153 static RF_DiskQueueData_t * 154 n_in_q(headp, tailp, countp, n, deq) 155 RF_DiskQueueData_t **headp; 156 RF_DiskQueueData_t **tailp; 157 int *countp; 158 int n; 159 int deq; 160 { 161 RF_DiskQueueData_t *r, *s; 162 int i; 163 164 for (s = NULL, i = n, r = *headp; r; s = r, r = r->next) { 165 if (i == 0) 166 break; 167 i--; 168 } 169 RF_ASSERT(r != NULL); 170 if (deq == 0) 171 return (r); 172 if (s) { 173 s->next = r->next; 174 } else { 175 *headp = r->next; 176 } 177 if (*tailp == r) 178 *tailp = s; 179 (*countp)--; 180 return (r); 181 } 182 #endif 183 184 #if !defined(KERNEL) && RF_INCLUDE_QUEUE_RANDOM > 0 185 RF_DiskQueueData_t * 186 rf_RandomPeek(q_in) 187 void *q_in; 188 { 189 RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in; 190 RF_DiskQueueData_t *req; 191 int n; 192 193 if (q->hq_head) { 194 n = q->rval % q->hq_count; 195 req = n_in_q(&q->hq_head, &q->hq_tail, &q->hq_count, n, 0); 196 } else { 197 RF_ASSERT(q->hq_count == 0); 198 if (q->lq_head == NULL) { 199 RF_ASSERT(q->lq_count == 0); 200 return (NULL); 201 } 202 n = q->rval % q->lq_count; 203 req = n_in_q(&q->lq_head, &q->lq_tail, &q->lq_count, n, 0); 204 } 205 RF_ASSERT((q->hq_count + q->lq_count) == req->queue->queueLength); 206 RF_ASSERT(req != NULL); 207 return (req); 208 } 209 210 RF_DiskQueueData_t * 211 rf_RandomDequeue(q_in) 212 void *q_in; 213 { 214 RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in; 215 RF_DiskQueueData_t *req; 216 int n; 217 218 if (q->hq_head) { 219 n = q->rval % q->hq_count; 220 q->rval = (long) RF_STATIC_RANDOM(); 221 req = n_in_q(&q->hq_head, &q->hq_tail, &q->hq_count, n, 1); 222 } else { 223 RF_ASSERT(q->hq_count == 0); 224 if (q->lq_head == NULL) { 225 RF_ASSERT(q->lq_count == 0); 226 return (NULL); 227 } 228 n = q->rval % q->lq_count; 229 q->rval = (long) RF_STATIC_RANDOM(); 230 req = n_in_q(&q->lq_head, &q->lq_tail, &q->lq_count, n, 1); 231 } 232 RF_ASSERT((q->hq_count + q->lq_count) == (req->queue->queueLength - 1)); 233 return (req); 234 } 235 #endif /* !KERNEL && RF_INCLUDE_QUEUE_RANDOM > 0 */ 236 237 /* Return ptr to item at head of queue. Used to examine request 238 * info without actually dequeueing the request. 239 */ 240 RF_DiskQueueData_t * 241 rf_FifoPeek(void *q_in) 242 { 243 RF_DiskQueueData_t *headElement = NULL; 244 RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in; 245 246 RF_ASSERT(q); 247 if (q->hq_head) 248 headElement = q->hq_head; 249 else 250 if (q->lq_head) 251 headElement = q->lq_head; 252 return (headElement); 253 } 254 /* We sometimes need to promote a low priority access to a regular priority access. 255 * Currently, this is only used when the user wants to write a stripe which is currently 256 * under reconstruction. 257 * This routine will promote all accesses tagged with the indicated parityStripeID from 258 * the low priority queue to the end of the normal priority queue. 259 * We assume the queue is locked upon entry. 260 */ 261 int 262 rf_FifoPromote(q_in, parityStripeID, which_ru) 263 void *q_in; 264 RF_StripeNum_t parityStripeID; 265 RF_ReconUnitNum_t which_ru; 266 { 267 RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in; 268 RF_DiskQueueData_t *lp = q->lq_head, *pt = NULL; /* lp = lo-pri queue 269 * pointer, pt = trailer */ 270 int retval = 0; 271 272 while (lp) { 273 274 /* search for the indicated parity stripe in the low-pri queue */ 275 if (lp->parityStripeID == parityStripeID && lp->which_ru == which_ru) { 276 /* printf("FifoPromote: promoting access for psid 277 * %ld\n",parityStripeID); */ 278 if (pt) 279 pt->next = lp->next; /* delete an entry other 280 * than the first */ 281 else 282 q->lq_head = lp->next; /* delete the head entry */ 283 284 if (!q->lq_head) 285 q->lq_tail = NULL; /* we deleted the only 286 * entry */ 287 else 288 if (lp == q->lq_tail) 289 q->lq_tail = pt; /* we deleted the tail 290 * entry */ 291 292 lp->next = NULL; 293 q->lq_count--; 294 295 if (q->hq_tail) { 296 q->hq_tail->next = lp; 297 q->hq_tail = lp; 298 } 299 /* append to hi-priority queue */ 300 else { 301 q->hq_head = q->hq_tail = lp; 302 } 303 q->hq_count++; 304 305 /* UpdateShortestSeekFinishTimeForced(lp->requestPtr, 306 * lp->diskState); *//* deal with this later, if ever */ 307 308 lp = (pt) ? pt->next : q->lq_head; /* reset low-pri pointer 309 * and continue */ 310 retval++; 311 312 } else { 313 pt = lp; 314 lp = lp->next; 315 } 316 } 317 318 /* sanity check. delete this if you ever put more than one entry in 319 * the low-pri queue */ 320 RF_ASSERT(retval == 0 || retval == 1); 321 if (rf_fifoDebug) { 322 int tid; 323 rf_get_threadid(tid); 324 printf("[%d] fifo: promote %d\n", tid, retval); 325 } 326 return (retval); 327 } 328