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