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*/
55 void   *
rf_FifoCreate(RF_SectorCount_t sectPerDisk,RF_AllocListElem_t * clList,RF_ShutdownList_t ** listp)56 rf_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 
66 void
rf_FifoEnqueue(void * q_in,RF_DiskQueueData_t * elem,int priority)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 || 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 
113 RF_DiskQueueData_t *
rf_FifoDequeue(void * q_in)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_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  */
157 int
rf_FifoPromote(void * q_in,RF_StripeNum_t parityStripeID,RF_ReconUnitNum_t which_ru)158 rf_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