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