Import of CMU's RAIDframe via NetBSD.

1 files changed, 371 insertions, 0 deletions

diff --git a/sys/dev/raidframe/rf_fifo.c b/sys/dev/raidframe/rf_fifo.c
new file mode 100644
index 00000000000..63367aeb4ab
--- /dev/null
+++ b/sys/dev/raidframe/rf_fifo.c
@@ -0,0 +1,371 @@
+/*	$OpenBSD: rf_fifo.c,v 1.1 1999/01/11 14:29:22 niklas Exp $	*/
+/*	$NetBSD: rf_fifo.c,v 1.1 1998/11/13 04:20:29 oster Exp $	*/
+/*
+ * Copyright (c) 1995 Carnegie-Mellon University.
+ * All rights reserved.
+ *
+ * Author: Mark Holland
+ *
+ * Permission to use, copy, modify and distribute this software and
+ * its documentation is hereby granted, provided that both the copyright
+ * notice and this permission notice appear in all copies of the
+ * software, derivative works or modified versions, and any portions
+ * thereof, and that both notices appear in supporting documentation.
+ *
+ * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
+ * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
+ * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
+ *
+ * Carnegie Mellon requests users of this software to return to
+ *
+ *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
+ *  School of Computer Science
+ *  Carnegie Mellon University
+ *  Pittsburgh PA 15213-3890
+ *
+ * any improvements or extensions that they make and grant Carnegie the
+ * rights to redistribute these changes.
+ */
+
+/***************************************************
+ *
+ * rf_fifo.c --  prioritized fifo queue code.  
+ * There are only two priority levels: hi and lo.
+ *
+ * Aug 4, 1994, adapted from raidSim version (MCH)
+ *
+ ***************************************************/
+
+/*
+ * :  
+ * Log: rf_fifo.c,v 
+ * Revision 1.20  1996/06/18 20:53:11  jimz
+ * fix up disk queueing (remove configure routine,
+ * add shutdown list arg to create routines)
+ *
+ * Revision 1.19  1996/06/14  00:08:21  jimz
+ * make happier in all environments
+ *
+ * Revision 1.18  1996/06/13  20:41:24  jimz
+ * add random queueing
+ *
+ * Revision 1.17  1996/06/09  02:36:46  jimz
+ * lots of little crufty cleanup- fixup whitespace
+ * issues, comment #ifdefs, improve typing in some
+ * places (esp size-related)
+ *
+ * Revision 1.16  1996/06/07  22:26:27  jimz
+ * type-ify which_ru (RF_ReconUnitNum_t)
+ *
+ * Revision 1.15  1996/06/07  21:33:04  jimz
+ * begin using consistent types for sector numbers,
+ * stripe numbers, row+col numbers, recon unit numbers
+ *
+ * Revision 1.14  1996/06/06  01:15:02  jimz
+ * added debugging
+ *
+ * Revision 1.13  1996/05/30  23:22:16  jimz
+ * bugfixes of serialization, timing problems
+ * more cleanup
+ *
+ * Revision 1.12  1996/05/30  11:29:41  jimz
+ * Numerous bug fixes. Stripe lock release code disagreed with the taking code
+ * about when stripes should be locked (I made it consistent: no parity, no lock)
+ * There was a lot of extra serialization of I/Os which I've removed- a lot of
+ * it was to calculate values for the cache code, which is no longer with us.
+ * More types, function, macro cleanup. Added code to properly quiesce the array
+ * on shutdown. Made a lot of stuff array-specific which was (bogusly) general
+ * before. Fixed memory allocation, freeing bugs.
+ *
+ * Revision 1.11  1996/05/27  18:56:37  jimz
+ * more code cleanup
+ * better typing
+ * compiles in all 3 environments
+ *
+ * Revision 1.10  1996/05/23  21:46:35  jimz
+ * checkpoint in code cleanup (release prep)
+ * lots of types, function names have been fixed
+ *
+ * Revision 1.9  1995/12/12  18:10:06  jimz
+ * MIN -> RF_MIN, MAX -> RF_MAX, ASSERT -> RF_ASSERT
+ * fix 80-column brain damage in comments
+ *
+ * Revision 1.8  1995/12/01  18:22:15  root
+ * added copyright info
+ *
+ * Revision 1.7  1995/11/07  15:32:16  wvcii
+ * added function FifoPeek()
+ *
+ */
+
+#include "rf_types.h"
+#include "rf_alloclist.h"
+#include "rf_stripelocks.h"
+#include "rf_layout.h"
+#include "rf_diskqueue.h"
+#include "rf_fifo.h"
+#include "rf_debugMem.h"
+#include "rf_general.h"
+#include "rf_threadid.h"
+#include "rf_options.h"
+
+#if !defined(KERNEL) && RF_INCLUDE_QUEUE_RANDOM > 0
+#include "rf_randmacros.h"
+RF_DECLARE_STATIC_RANDOM
+#endif /* !KERNEL && RF_INCLUDE_QUEUE_RANDOM > 0 */
+
+/* just malloc a header, zero it (via calloc), and return it */
+/*ARGSUSED*/
+void *rf_FifoCreate(sectPerDisk, clList, listp)
+  RF_SectorCount_t      sectPerDisk;
+  RF_AllocListElem_t   *clList;
+  RF_ShutdownList_t   **listp;
+{
+  RF_FifoHeader_t *q;
+
+#if !defined(KERNEL) && RF_INCLUDE_QUEUE_RANDOM > 0
+  RF_INIT_STATIC_RANDOM(1);
+#endif /* !KERNEL && RF_INCLUDE_QUEUE_RANDOM > 0 */
+  RF_CallocAndAdd(q, 1, sizeof(RF_FifoHeader_t), (RF_FifoHeader_t *), clList);
+  q->hq_count = q->lq_count = 0;
+#if !defined(KERNEL) && RF_INCLUDE_QUEUE_RANDOM > 0
+  q->rval = (long)RF_STATIC_RANDOM();
+#endif /* !KERNEL && RF_INCLUDE_QUEUE_RANDOM > 0 */
+  return((void *)q);
+}
+
+void rf_FifoEnqueue(q_in, elem, priority)
+  void                *q_in;
+  RF_DiskQueueData_t  *elem;
+  int                  priority;
+{
+  RF_FifoHeader_t *q = (RF_FifoHeader_t *)q_in;
+
+  RF_ASSERT(priority == RF_IO_NORMAL_PRIORITY || priority == RF_IO_LOW_PRIORITY);
+
+  elem->next = NULL;
+  if (priority == RF_IO_NORMAL_PRIORITY) {
+    if (!q->hq_tail) {
+      RF_ASSERT(q->hq_count == 0 && q->hq_head == NULL);
+      q->hq_head = q->hq_tail = elem;
+    } else {
+      RF_ASSERT(q->hq_count != 0 && q->hq_head != NULL);
+      q->hq_tail->next = elem;
+      q->hq_tail = elem;
+    }
+    q->hq_count++;
+  }
+  else {
+    RF_ASSERT(elem->next == NULL);
+    if (rf_fifoDebug) {
+      int tid;
+      rf_get_threadid(tid);
+      printf("[%d] fifo: ENQ lopri\n", tid);
+    }
+    if (!q->lq_tail) {
+      RF_ASSERT(q->lq_count == 0 && q->lq_head == NULL);
+      q->lq_head = q->lq_tail = elem;
+    } else {
+      RF_ASSERT(q->lq_count != 0 && q->lq_head != NULL);
+      q->lq_tail->next = elem;
+      q->lq_tail = elem;
+    }
+    q->lq_count++;
+  }
+  if ((q->hq_count + q->lq_count)!= elem->queue->queueLength) {
+	  printf("Queue lengths differ!: %d %d %d\n",
+		 q->hq_count, q->lq_count, (int)elem->queue->queueLength);
+	  printf("%d %d %d %d\n",
+		 (int)elem->queue->numOutstanding,
+		 (int)elem->queue->maxOutstanding,
+		 (int)elem->queue->row,
+		 (int)elem->queue->col);
+  }
+  RF_ASSERT((q->hq_count + q->lq_count) == elem->queue->queueLength);
+}
+
+RF_DiskQueueData_t *rf_FifoDequeue(q_in)
+  void  *q_in;
+{
+  RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in;
+  RF_DiskQueueData_t *nd;
+
+  RF_ASSERT(q);
+  if (q->hq_head) {
+    RF_ASSERT(q->hq_count != 0 && q->hq_tail != NULL);
+    nd = q->hq_head; q->hq_head = q->hq_head->next;
+    if (!q->hq_head) q->hq_tail = NULL;
+    nd->next = NULL;
+    q->hq_count--;
+  } else if (q->lq_head) {
+    RF_ASSERT(q->lq_count != 0 && q->lq_tail != NULL);
+    nd = q->lq_head; q->lq_head = q->lq_head->next;
+    if (!q->lq_head) q->lq_tail = NULL;
+    nd->next = NULL;
+    q->lq_count--;
+    if (rf_fifoDebug) {
+      int tid;
+      rf_get_threadid(tid);
+      printf("[%d] fifo: DEQ lopri %lx\n", tid, (long)nd);
+    }
+  } else {
+    RF_ASSERT(q->hq_count == 0 && q->lq_count == 0 && q->hq_tail == NULL && q->lq_tail == NULL);
+    nd = NULL;
+  }
+  return(nd);
+}
+
+/* This never gets used!! No loss (I hope) if we don't include it... GO */
+#if !defined(__NetBSD__) && !defined(__OpenBSD__) && !defined(_KERNEL)
+
+static RF_DiskQueueData_t *n_in_q(headp, tailp, countp, n, deq)
+  RF_DiskQueueData_t  **headp;
+  RF_DiskQueueData_t  **tailp;
+  int                  *countp;
+  int                   n;
+  int                   deq;
+{
+  RF_DiskQueueData_t *r, *s;
+  int i;
+
+  for(s=NULL,i=n,r=*headp;r;s=r,r=r->next) {
+    if (i == 0)
+      break;
+    i--;
+  }
+  RF_ASSERT(r != NULL);
+  if (deq == 0)
+    return(r);
+  if (s) {
+    s->next = r->next;
+  }
+  else {
+    *headp = r->next;
+  }
+  if (*tailp == r)
+    *tailp = s;
+  (*countp)--;
+  return(r);
+}
+#endif
+
+#if !defined(KERNEL) && RF_INCLUDE_QUEUE_RANDOM > 0
+RF_DiskQueueData_t *rf_RandomPeek(q_in)
+  void  *q_in;
+{
+  RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in;
+  RF_DiskQueueData_t *req;
+  int n;
+
+  if (q->hq_head) {
+    n = q->rval % q->hq_count;
+    req = n_in_q(&q->hq_head, &q->hq_tail, &q->hq_count, n, 0);
+  }
+  else {
+    RF_ASSERT(q->hq_count == 0);
+    if (q->lq_head == NULL) {
+      RF_ASSERT(q->lq_count == 0);
+      return(NULL);
+    }
+    n = q->rval % q->lq_count;
+    req = n_in_q(&q->lq_head, &q->lq_tail, &q->lq_count, n, 0);
+  }
+  RF_ASSERT((q->hq_count + q->lq_count) == req->queue->queueLength);
+  RF_ASSERT(req != NULL);
+  return(req);
+}
+
+RF_DiskQueueData_t *rf_RandomDequeue(q_in)
+  void  *q_in;
+{
+  RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in;
+  RF_DiskQueueData_t *req;
+  int n;
+
+  if (q->hq_head) {
+    n = q->rval % q->hq_count;
+    q->rval = (long)RF_STATIC_RANDOM();
+    req = n_in_q(&q->hq_head, &q->hq_tail, &q->hq_count, n, 1);
+  }
+  else {
+    RF_ASSERT(q->hq_count == 0);
+    if (q->lq_head == NULL) {
+      RF_ASSERT(q->lq_count == 0);
+      return(NULL);
+    }
+    n = q->rval % q->lq_count;
+    q->rval = (long)RF_STATIC_RANDOM();
+    req = n_in_q(&q->lq_head, &q->lq_tail, &q->lq_count, n, 1);
+  }
+  RF_ASSERT((q->hq_count + q->lq_count) == (req->queue->queueLength-1));
+  return(req);
+}
+#endif /* !KERNEL && RF_INCLUDE_QUEUE_RANDOM > 0 */
+
+/* Return ptr to item at head of queue.  Used to examine request
+ * info without actually dequeueing the request.
+ */
+RF_DiskQueueData_t *rf_FifoPeek(void *q_in)
+{
+  RF_DiskQueueData_t *headElement = NULL;
+  RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in;
+
+  RF_ASSERT(q);
+  if (q->hq_head)
+    headElement = q->hq_head;
+  else if (q->lq_head)
+    headElement = q->lq_head;
+  return(headElement);
+}
+
+/* We sometimes need to promote a low priority access to a regular priority access.
+ * Currently, this is only used when the user wants to write a stripe which is currently
+ * under reconstruction.
+ * This routine will promote all accesses tagged with the indicated parityStripeID from
+ * the low priority queue to the end of the normal priority queue.
+ * We assume the queue is locked upon entry.
+ */
+int rf_FifoPromote(q_in, parityStripeID, which_ru)
+  void               *q_in;
+  RF_StripeNum_t      parityStripeID;
+  RF_ReconUnitNum_t   which_ru;
+{
+  RF_FifoHeader_t *q = (RF_FifoHeader_t *) q_in;
+  RF_DiskQueueData_t *lp = q->lq_head, *pt = NULL;  /* lp = lo-pri queue pointer, pt = trailer */
+  int retval = 0;
+
+  while (lp) {
+
+    /* search for the indicated parity stripe in the low-pri queue */
+    if (lp->parityStripeID == parityStripeID && lp->which_ru == which_ru) {
+      /*printf("FifoPromote:  promoting access for psid %ld\n",parityStripeID);*/
+      if (pt) pt->next = lp->next;                              /* delete an entry other than the first */
+      else q->lq_head = lp->next;                               /* delete the head entry */
+      
+      if (!q->lq_head) q->lq_tail = NULL;                       /* we deleted the only entry */
+      else if (lp == q->lq_tail) q->lq_tail = pt;               /* we deleted the tail entry */
+      
+      lp->next = NULL;
+      q->lq_count--;
+      
+      if (q->hq_tail) {q->hq_tail->next = lp; q->hq_tail = lp;} /* append to hi-priority queue */
+      else {q->hq_head = q->hq_tail = lp;}
+      q->hq_count++;
+
+      /*UpdateShortestSeekFinishTimeForced(lp->requestPtr, lp->diskState);*/     /* deal with this later, if ever */
+
+      lp = (pt) ? pt->next : q->lq_head;		       /* reset low-pri pointer and continue */
+      retval++;
+      
+    } else {pt = lp; lp = lp->next;}
+  }
+  
+  /* sanity check.  delete this if you ever put more than one entry in the low-pri queue */
+  RF_ASSERT(retval == 0 || retval == 1);
+  if (rf_fifoDebug) {
+    int tid;
+    rf_get_threadid(tid);
+    printf("[%d] fifo: promote %d\n", tid, retval);
+  }
+  return(retval);
+}