4.3BSD - /usr/src/sys/sys/ufs_dsort.c

   1: /*
   2:  * Copyright (c) 1982, 1986 Regents of the University of California.
   3:  * All rights reserved.  The Berkeley software License Agreement
   4:  * specifies the terms and conditions for redistribution.
   5:  *
   6:  *	@(#)ufs_dsort.c	7.1 (Berkeley) 6/5/86
   7:  */
   8: 
   9: /*
  10:  * Seek sort for disks.  We depend on the driver
  11:  * which calls us using b_resid as the current cylinder number.
  12:  *
  13:  * The argument dp structure holds a b_actf activity chain pointer
  14:  * on which we keep two queues, sorted in ascending cylinder order.
  15:  * The first queue holds those requests which are positioned after
  16:  * the current cylinder (in the first request); the second holds
  17:  * requests which came in after their cylinder number was passed.
  18:  * Thus we implement a one way scan, retracting after reaching the
  19:  * end of the drive to the first request on the second queue,
  20:  * at which time it becomes the first queue.
  21:  *
  22:  * A one-way scan is natural because of the way UNIX read-ahead
  23:  * blocks are allocated.
  24:  */
  25: 
  26: #include "param.h"
  27: #include "systm.h"
  28: #include "buf.h"
  29: 
  30: #define b_cylin b_resid
  31: 
  32: disksort(dp, bp)
  33:     register struct buf *dp, *bp;
  34: {
  35:     register struct buf *ap;
  36: 
  37:     /*
  38: 	 * If nothing on the activity queue, then
  39: 	 * we become the only thing.
  40: 	 */
  41:     ap = dp->b_actf;
  42:     if(ap == NULL) {
  43:         dp->b_actf = bp;
  44:         dp->b_actl = bp;
  45:         bp->av_forw = NULL;
  46:         return;
  47:     }
  48:     /*
  49: 	 * If we lie after the first (currently active)
  50: 	 * request, then we must locate the second request list
  51: 	 * and add ourselves to it.
  52: 	 */
  53:     if (bp->b_cylin < ap->b_cylin) {
  54:         while (ap->av_forw) {
  55:             /*
  56: 			 * Check for an ``inversion'' in the
  57: 			 * normally ascending cylinder numbers,
  58: 			 * indicating the start of the second request list.
  59: 			 */
  60:             if (ap->av_forw->b_cylin < ap->b_cylin) {
  61:                 /*
  62: 				 * Search the second request list
  63: 				 * for the first request at a larger
  64: 				 * cylinder number.  We go before that;
  65: 				 * if there is no such request, we go at end.
  66: 				 */
  67:                 do {
  68:                     if (bp->b_cylin < ap->av_forw->b_cylin)
  69:                         goto insert;
  70:                     ap = ap->av_forw;
  71:                 } while (ap->av_forw);
  72:                 goto insert;        /* after last */
  73:             }
  74:             ap = ap->av_forw;
  75:         }
  76:         /*
  77: 		 * No inversions... we will go after the last, and
  78: 		 * be the first request in the second request list.
  79: 		 */
  80:         goto insert;
  81:     }
  82:     /*
  83: 	 * Request is at/after the current request...
  84: 	 * sort in the first request list.
  85: 	 */
  86:     while (ap->av_forw) {
  87:         /*
  88: 		 * We want to go after the current request
  89: 		 * if there is an inversion after it (i.e. it is
  90: 		 * the end of the first request list), or if
  91: 		 * the next request is a larger cylinder than our request.
  92: 		 */
  93:         if (ap->av_forw->b_cylin < ap->b_cylin ||
  94:             bp->b_cylin < ap->av_forw->b_cylin)
  95:             goto insert;
  96:         ap = ap->av_forw;
  97:     }
  98:     /*
  99: 	 * Neither a second list nor a larger
 100: 	 * request... we go at the end of the first list,
 101: 	 * which is the same as the end of the whole schebang.
 102: 	 */
 103: insert:
 104:     bp->av_forw = ap->av_forw;
 105:     ap->av_forw = bp;
 106:     if (ap == dp->b_actl)
 107:         dp->b_actl = bp;
 108: }

Defined functions

Defined macros