Annotation of sys/dev/raidframe/rf_fifo.c, Revision 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