home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 2: PC / frozenfish_august_1995.bin / bbs / d07xx / d0754.lha / SmartDisk / SmartDisk.c < prev   
C/C++ Source or Header  |  1992-11-05  |  16KB  |  611 lines
  1. /*
  2.  * SmartDisk 1.3.
  3.  *
  4.  * Created by David Le Blanc 29/10/91 Absolutely no copywrite. But if you improve
  5.  * it, please send me a new version (with source!) 
  6.  * 
  7.  * Current limitations.
  8.  *   No command line options, device and cache size are hard-wired into the program.
  9.  *   Only one unit is supported.
  10.  *
  11.  * Obvious enhacements.
  12.  *   Make device and unit configurable, as well as cache size and shape.
  13.  *
  14.  * Some performance quotes: (Doesn't everyone make these??)
  15.  * Background:  I have a directory called MAN: which has 355 manuals.
  16.  *
  17.  * WARNING: These are bad examples, since a 'dir' reads the disk, then sorts the
  18.  * contents, then writes the data to the screen. These times include the sorting
  19.  * and output of the directory. This sorting and output time is in the order
  20.  * of 1.5 to 2 seconds.
  21.  *
  22.  * Normal DIR MAN:        12 seconds
  23.  * Cache enabled but empty      9  seconds (prefetch does work!) 
  24.  * Cache primed                 5  seconds.
  25.  *
  26.  * With a slower drive and/or faster machine these times can only improve.
  27.  * I have a drive capable of 800k/sec on my unaccelerated A500. Those with
  28.  * a 150K/sec A590 would notice a greater performance boost. Same for those
  29.  * with 'bloody fast machines' (grumble :) If I was REALLY worried about making
  30.  * the statistic look good, then I'd test it on an A590.
  31.  *
  32.  * A590 USERS: You MUST edit the 'scsi.device' to 'xt.device' or it will NOT WORK.
  33.  * GVP  USERS: You MUST edit the 'scsi.device' to 'gvpscsi.device' or it will
  34.  *             NOT WORK.
  35.  *
  36.  * SmartDisk: A SCSI.DEVICE disk cache.
  37.  *
  38.  * 1.3.1:       Removed some 2.0ism's that crept in, and added code to
  39.  *              read the device and unit from the command line.
  40.  * 1.3:        Added Prefetch and fixed 'CMD_WRITE' to update instead of
  41.  *              flush cache entry.
  42.  * 1.2:         Added many optimisation such as moving the semaphore locks to
  43.  *              the update functions, and for a request of many blocks, the
  44.  *              blocks are read in all at once into the users buffer, THEN
  45.  *              copied to cache. (Instead of read into cache one at a time and
  46.  *              then copied to the user buffer)
  47.  * 1.1:        Found a major problem. The following union under Lattice 5.10a
  48.  *              generates unexpected (probably correct) code. The key, line and
  49.  *        offset fields are actually unioned together, whereas I though
  50.  *        the union would be between the two int declarations. 
  51.  *
  52.  *              union sector {
  53.  *                 int key:32-LINE_BITS-ITEM_BITS,
  54.  *                     line:LINE_BITS,
  55.  *                     offset:ITEM_BITS ;
  56.  *                 int sector ;
  57.  *                 } ;
  58.  *
  59.  *        I made the bit fields a separate structure, and union'ed the 
  60.  *          sector and the new structure together.
  61.  *
  62.  * 1.0:        My school assigment was to write a N-way set associative cache
  63.  *        simulator and to plot hit-rate percentages. With a bit of
  64.  *        work, it is not a Hard Disk cache! Vive la Amiga!
  65.  *
  66.  *
  67.  * History:
  68.  *    29/10/91 : Sat down an wrote a cache.
  69.  *    30/10/91 : Problem? Works Great Now.
  70.  *    31/10/91 : Fixed up the 'aging' of blocks to handle the
  71.  *             : counter wrapping after 2^32 buffer creates/updates.
  72.  *             : (How long does 2^32 DIFFERENT accesses take?? With a fast hard
  73.  *                disk going continually, I estimate about two months.)
  74.  *             : Cleaned up the code a tad.
  75.  */
  76.  
  77. struct IOStdReq *IO;        /* All IO goes through here now. */
  78. struct SignalSemaphore *ss ;    /* To force single threading     */
  79.                 /* through the code responsible     */
  80.                 /* for updating the cache     */
  81. ULONG counter ;
  82.  
  83. int allocnum = 0 ;
  84.  
  85. void printf(char *fmt, ...) ;
  86.  
  87. /*
  88.  * Constants. Adjust for adjusting cache size and shape.
  89.  */
  90.  
  91. #define ITEM_SIZE 512           /* No change - sector size */
  92.  
  93. #define LINE_SIZE   4           /* Increase for prefetch */
  94. #define SETS        8           /* N-way set associative */
  95. #define LINES      32           /* N lines of cache      */
  96.  
  97. /*
  98.  * Bit fields. Adjust to match above constants.
  99.  */
  100.  
  101. #define ITEM_BITS  2            /* 2^ITEM_BITS = LINE_SIZE */
  102. #define LINE_BITS  5            /* 2^LINE_BITS = LINES     */
  103.  
  104. struct bitaddress {
  105.    int key:32-LINE_BITS-ITEM_BITS,
  106.        line:LINE_BITS,
  107.        offset:ITEM_BITS ;
  108.    } ;
  109.  
  110. union sector {
  111.    int sector ;
  112.    struct bitaddress s ;
  113.    } ;
  114.  
  115. struct cache_line {
  116.    int key ;                     /* Item key */
  117.    int age ;                     /* AGE for LRU alg */
  118.    int valid ;
  119.    char *buffer ;                /* [LINE_SIZE][ITEM_SIZE] of DATA */
  120.    } ;
  121.  
  122. struct cache_line cache[SETS][LINES] ;
  123.  
  124. /*
  125.  * A buffer for scsidisk.device to go through.
  126.  */
  127. char __chip globbuffer[LINE_SIZE << 9] ;
  128.  
  129. #define DEV_BEGINIO (-30)
  130. #define DEV_ABORTIO (-36)
  131.  
  132. void (*__asm oldbeginio)(register __a1 struct IOStdReq *,
  133.                          register __a6 struct Device *dev) ;
  134. /*
  135.  * Scan for sector, and return the set it resides in.
  136.  */
  137. int
  138. FindEntry(union sector *s) {
  139.  
  140.    int set ;
  141.  
  142.    for (set = 0; set < SETS; set++) 
  143.       if (cache[set][s->s.line].valid) {
  144.          if (cache[set][s->s.line].key == s->s.key) {
  145.             cache[set][s->s.line].age = counter ++ ;
  146.             return set ;
  147.             }
  148.          }
  149.       else
  150.          break ;
  151.  
  152.    return -1 ;
  153.    }
  154.  
  155. /*
  156.  * Pick a set from the associated cache, and return
  157.  * the set number. The cache memory is also allocated
  158.  * before returning. The cache entry is marked VALID. so if you
  159.  * can't fill it, remember to clear it!
  160.  */
  161. int
  162. AllocCache(union sector *s) {
  163.    int set ;
  164.    int oldest ;
  165.    int oldset ;
  166.    int found ;
  167.    int age ;
  168.  
  169.    oldset = 0 ;
  170.    oldest = 0 ;
  171.    found  = 0 ;
  172.  
  173.    for (set = 0; set < SETS; set++) 
  174.       if (cache[set][s->s.line].valid) {
  175.          if (cache[set][s->s.line].key != s->s.key) {
  176.             /*
  177.              * This 'age' calculation is complicated since normally, 
  178.              * AGE = COUNTER - CACHE.AGE, however, if counter has
  179.              * wrapped to zero, such evaluation evaluates ages of < 0 and
  180.              * these entries will never be reselected for reuse.
  181.              *
  182.              * If counter wraps to zero, then CACHE.AGE is generally larger
  183.              * than COUNTER, so we evaluate age as the total of MAXINT-AGE 
  184.              * plus the current value of the counter. IE, how much it took to
  185.              * wrap and reach the current position.
  186.              *
  187.              * Hence, 
  188.              * AGE = ~0 - CACHE.AGE + COUNTER
  189.              */
  190.             age = cache[set][s->s.line].age ;
  191.             if (age > counter)
  192.                age = ((ULONG) ~0 - age) + counter ;
  193.             else
  194.                age = counter - age ;
  195.  
  196.             if (age > oldest)
  197.                oldest = age, oldset = set ;
  198.             }
  199.          else {
  200.             found = 1 ;
  201.             break ; /* key = s.key. Line already in cache */
  202.             }
  203.          }
  204.       else
  205.          break ; /* !valid. Found a free line */
  206.  
  207.    if (found) {
  208.       return -1 ;
  209.       }
  210.  
  211.    if (set == SETS)
  212.       set = oldset ;
  213.  
  214.    cache[set][s->s.line].age = counter ++ ;
  215.    cache[set][s->s.line].key = s->s.key ;
  216.  
  217.    /*
  218.     * If no buffer, allocate one.
  219.     */
  220.    if (! cache[set][s->s.line].buffer )
  221.       if (cache[set][s->s.line].buffer = AllocMem(LINE_SIZE << 9, MEMF_PUBLIC))
  222.          allocnum ++ ;
  223.  
  224.    /*
  225.     * If STILL no buffer, return failure. Otherwise set the VALID flag.
  226.     */
  227.    if (cache[set][s->s.line].buffer )
  228.       cache[set][s->s.line].valid = 1 ;
  229.    else {
  230.       cache[set][s->s.line].valid = 0 ;         /* Allocation failed */
  231.       return -1 ;
  232.       }
  233.  
  234.    return set ;
  235.    }
  236.  
  237. /*
  238.  * Allocate a line of cache and read it from disk.
  239.  */
  240. int
  241. ReadCache(union sector *s) {
  242.    struct MsgPort *port ;
  243.    char *dest ;
  244.    int  set ;
  245.  
  246.    ObtainSemaphore(ss);
  247.  
  248.    port = CreatePort(0,0) ;
  249.  
  250.    if (!port) {
  251.       ReleaseSemaphore(ss) ;
  252.       return -1 ;
  253.       }
  254.  
  255.    if (s->s.offset)
  256.       s->s.offset = 0 ;
  257.  
  258.    IO->io_Message.mn_ReplyPort = port ;
  259.  
  260.    IO->io_Command = CMD_READ;
  261.    IO->io_Offset = s->sector << 9 ;
  262.    IO->io_Length = LINE_SIZE << 9 ;
  263.    IO->io_Data = (APTR) globbuffer ;
  264.  
  265.    oldbeginio(IO,IO->io_Device) ;
  266.    WaitIO(IO) ;
  267.  
  268.    DeletePort(port) ;
  269.  
  270.    if (IO->io_Error) {
  271.       ReleaseSemaphore(ss) ;
  272.       return -1 ;
  273.       }
  274.  
  275.    set = AllocCache(s) ;
  276.  
  277.    if (set < 0) {
  278.       ReleaseSemaphore(ss) ;
  279.       return -1 ;
  280.       }
  281.  
  282.    dest = cache[set][s->s.line].buffer ;
  283.  
  284.    CopyMemQuick(globbuffer, dest, LINE_SIZE << 9) ;
  285.  
  286.    ReleaseSemaphore(ss) ;
  287.    return 0 ;
  288.    }
  289.  
  290. int
  291. ReadBufferToCache(int linestart,int unread,char *buffer) {
  292.  
  293.    union sector s ;
  294.    struct MsgPort *port ;
  295.    int set ;
  296.  
  297.    ObtainSemaphore(ss);
  298.    s.sector = linestart ;
  299.  
  300.    port = CreatePort(0,0) ;
  301.  
  302.    if (!port) {
  303.       ReleaseSemaphore(ss) ;
  304.       return -1 ;
  305.       }
  306.  
  307.    IO->io_Message.mn_ReplyPort = port ;
  308.  
  309.    /*
  310.     * Read enough to fill the buffer.
  311.     */
  312.  
  313.    IO->io_Command = CMD_READ;
  314.    IO->io_Offset = linestart << 9 ;
  315.    IO->io_Length = unread << 9 ;
  316.    IO->io_Data = (APTR) buffer ;
  317.  
  318.    oldbeginio(IO,IO->io_Device) ;
  319.    WaitIO(IO) ;
  320.  
  321.    DeletePort(port) ;
  322.  
  323.    if (IO->io_Error) {
  324.       ReleaseSemaphore(ss) ;
  325.       return -1 ;
  326.       }
  327.  
  328.    while (unread) {
  329.       set = AllocCache(&s) ;
  330.       if (set < 0) {
  331.          ReleaseSemaphore(ss) ;
  332.          return -1 ;
  333.          }
  334.       else {
  335.          CopyMemQuick(buffer,cache[set][s.s.line].buffer, LINE_SIZE << 9) ;
  336.          }
  337.  
  338.       s.sector += LINE_SIZE ;
  339.       unread -= LINE_SIZE ;
  340.       buffer += (LINE_SIZE << 9) ;
  341.       }
  342.  
  343.    ReleaseSemaphore(ss) ;
  344.    return 0 ;
  345.    }
  346.  
  347. /* 
  348.  * This functions checks the cache. If the sector is there, it returns
  349.  * the buffer, otherwise it returns NULL.
  350.  */
  351. char *
  352. FindCache(union sector *s,int set) {
  353.    return & (cache[set][s->s.line].buffer[s->s.offset << 9 ] ) ;
  354.    }
  355.  
  356. /*
  357.  * This function takes 'sector' and set, and decides if the next sector
  358.  * is in the cache.
  359.  */
  360. int
  361. NextEntry(union sector *s, int set) {
  362.    int line ;
  363.  
  364.    line = s->s.line ;
  365.    s->sector ++ ;
  366.  
  367.    if (line == s->s.line) {
  368.       return set ;
  369.       }
  370.    else
  371.       return FindEntry(s) ;
  372.    }
  373.  
  374. /*
  375.  * Search for sector, and mark it invalid.
  376.  */
  377. void
  378. ClearEntry(union sector *s,int set) {
  379.    cache[set][s->s.line].valid = 0 ;
  380.    }
  381.  
  382. CacheUpdate(union sector *s, int seccount, char *buffer) {
  383.    int set ;
  384.  
  385.    ObtainSemaphore(ss) ;
  386.  
  387.    while (seccount) {
  388.       set = FindEntry(s) ;
  389.       if (set >= 0) {
  390.          CopyMemQuick(buffer,FindCache(s,set), ITEM_SIZE) ;
  391.          cache[set][s->s.line].age = counter ++ ;
  392.          }
  393.  
  394.       buffer += ( ITEM_SIZE ) ;
  395.       seccount -- ;
  396.       s->sector ++ ;
  397.       }
  398.  
  399.    ReleaseSemaphore(ss) ;
  400.    return 0 ;
  401.    }
  402.  
  403. void __saveds __asm mybeginio(register __a1 struct IOStdReq *req,
  404.                               register __a6 struct Device *dev) {
  405.  
  406.    union sector s ;
  407.    int   set ;
  408.    int   command ;
  409.    int   secnum ;
  410.    char  *source ;
  411.    char  *buffer ;
  412.  
  413.    int   unread ;
  414.    int   linestart ;
  415.  
  416.    s.sector = req->io_Offset >> 9 ;
  417.    secnum   = req->io_Length >> 9 ;
  418.    command  = req->io_Command ;
  419.    buffer   = (char *) req->io_Data ;
  420.  
  421.    if (command == CMD_WRITE)
  422.       CacheUpdate(&s,secnum,buffer) ;
  423.  
  424.    if (command == CMD_READ) {
  425.  
  426.       while (secnum) {
  427.          set = FindEntry(&s) ;
  428.  
  429.          if (set < 0) {
  430.             source = NULL ;
  431.             }
  432.          else {
  433.             source = FindCache(&s,set) ;
  434.             }
  435.  
  436.          /*
  437.           * Scan copying buffers to the request.
  438.           */
  439.  
  440.          while (secnum && source) {
  441.             CopyMemQuick(source,buffer,ITEM_SIZE) ;
  442.             buffer += ITEM_SIZE ;
  443.  
  444.             secnum -- ;
  445.             if (secnum) {
  446.                set = NextEntry(&s, set) ;
  447.                if (set < 0) {
  448.                   source = NULL ;
  449.                   }
  450.                else {
  451.                   source = FindCache(&s,set) ;
  452.                   }
  453.                }
  454.             }
  455.  
  456.          if (!secnum) {                                 /* Done ? */
  457.             break ;
  458.             }
  459.  
  460.          /*
  461.           * If we are in the middle of a line, read it in.
  462.           */
  463.          if (s.s.offset) {
  464.             int original = s.sector ;
  465.  
  466.             s.s.offset = 0 ;
  467.             if (ReadCache(&s) < 0) {
  468.                }
  469.  
  470.             s.sector = original ;
  471.             }
  472.          else {
  473.             /*
  474.              * Start scanning at next line.
  475.              */
  476.             unread = 0 ;
  477.  
  478.             linestart = s.sector ; 
  479.  
  480.             /*
  481.              * Scan counting sectors that need reading.
  482.              */
  483.             while ((secnum>unread) && (set < 0)) {
  484.                s.sector = linestart + unread ;
  485.                set = FindEntry(&s) ;
  486.                /*
  487.                 * For efficiency, if a sector is not found, advance to
  488.                 * the next line instead of the next sector.
  489.                 */
  490.                if (set < 0) {
  491.                   unread += LINE_SIZE ;
  492.                   }
  493.                }
  494.  
  495.             if (unread > secnum) {
  496.                unread -= LINE_SIZE ;
  497.                }
  498.  
  499.             if (unread) {
  500.                /*
  501.                 * Read the cache into the supplied buffer, and copy
  502.                 * it to cache memory.
  503.                 */
  504.                ReadBufferToCache(linestart,unread,buffer) ;
  505.                buffer += ( unread << 9 ) ;
  506.                }
  507.              else {
  508.                /*
  509.                 * If there are more sectors, call 'ReadCache()' to get them.
  510.                 */
  511.                ReadCache( (union sector *)&linestart) ;
  512.                }
  513.  
  514.             /*
  515.              * Pick up where we left off.
  516.              */
  517.             s.sector = linestart + unread ;
  518.             secnum -= unread ;
  519.             if (secnum < 0)
  520.                break ;
  521.             }
  522.          }
  523.       /*
  524.        * Done!!!
  525.        */
  526.       }
  527.  
  528.    if (command != CMD_READ)
  529.       oldbeginio(req,dev) ;
  530.    else {
  531.       req->io_Actual = req->io_Length ;
  532.       ReplyMsg((struct Message *) req) ;
  533.       } ;
  534.  
  535.    }
  536.  
  537. int
  538. main(int argc, char *argv[]) {
  539.  
  540.    int error ;
  541.    int line,set ;
  542.    int devopen ;    
  543.    struct MsgPort  *port ;
  544.    char *device ;
  545.    int unit ;
  546.  
  547.    port = NULL;
  548.    devopen = 0 ;
  549.  
  550.    if (argc != 3) {
  551.       printf ("Usage: SmartDisk <yourhd.device> <unitnum>\n") ;
  552.       goto fail ;
  553.       }
  554.    else {
  555.       device = argv[1] ;
  556.       unit = atoi(argv[2]) ;
  557.       }
  558.  
  559.    port = CreatePort(0,0) ;
  560.    IO = CreateExtIO(port,sizeof(struct IOStdReq)) ;
  561.  
  562.    error = OpenDevice(device,unit,(struct IORequest *)IO, 0) ;
  563.  
  564.    if (error) {
  565.       printf ("Unable to open %s unit %d\n",device,unit) ;
  566.       goto fail ;
  567.       }
  568.    else
  569.       devopen = 1 ;
  570.  
  571.    ss = AllocMem(sizeof(struct SignalSemaphore), MEMF_PUBLIC) ;
  572.  
  573.    if (!ss)
  574.       goto fail ;
  575.  
  576.    SumLibrary( (struct Library *) IO->io_Device) ; 
  577.  
  578.    InitSemaphore(ss) ;
  579.  
  580.    oldbeginio = SetFunction((struct Library *)IO->io_Device,DEV_BEGINIO,(APTR)mybeginio) ;
  581.    Wait (SIGBREAKF_CTRL_F) ;
  582.  
  583.    ObtainSemaphore(ss) ;
  584.    SetFunction((struct Library *)IO->io_Device,DEV_BEGINIO,(APTR)oldbeginio) ;
  585.    ReleaseSemaphore(ss) ;
  586.  
  587.    for (line = 0; line < LINES; line ++)
  588.       for (set = 0; set < SETS; set ++)
  589.          if (cache[set][line].buffer) {
  590.             FreeMem( cache[set][line].buffer,LINE_SIZE << 9 ) ;
  591.             allocnum -- ;
  592.             }
  593.  
  594.    if (allocnum)
  595.       printf("Allocation mismatch. %d buffers left lying around\n",allocnum) ;
  596.  
  597. fail:
  598.    if (ss)
  599.       FreeMem(ss,sizeof(struct SignalSemaphore)) ;
  600.    if (devopen) {
  601.       IO->io_Message.mn_ReplyPort = port ;
  602.       CloseDevice((struct IORequest *)IO) ;
  603.       }
  604.    if (IO)
  605.       DeleteExtIO((struct IORequest *)IO) ;
  606.    if (port)
  607.       DeletePort(port) ;
  608.  
  609.    return 0 ;
  610.    }
  611.