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