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_disksubr.c 7.1 (Berkeley) 06/05/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 } 109