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