Annotation of sys/dev/raidframe/rf_fifo.c, Revision 1.1.1.1
1.1 nbrk 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: }
CVSweb