koreth@ssyx.ucsc.edu (Steven Grimm) (05/13/88)
Submitted-by: egisin@watmath.waterloo.edu (Eric Gisin)
Posting-number: Volume 1, Issue 32
Archive-name: cache
[This is a cache system, which speeds up floppy accesses. The executables
are being posted to comp.binaries.atari.st along with the same readme file
included here. -sg]
#--------------------------Cut Here--------------------------
#! /bin/sh
# This is a shell archive. Remove anything before the "#! /bin/sh" line,
# then unpack it by saving it in a file and typing "sh file."
#
# unpacks with default permissions
#
# Contents : cache.c cstat.c cache.h readme
#
if `test ! -s cache.c`
then
echo "x - cache.c"
cat > cache.c << '@\Rogue\Monster\'
/*
* Floppy Disk Cache (Atari ST)
*
* Copyright 1988, Eric Gisin <egisin@UWaterloo.CA>
* this program may be copied as long as this copyright notice is retained.
* the author will not be liable for any damages resulting from the use of this program.
*
* Usage: cache [drive][size]
* can be loaded twice to handle two drives.
*
* The cache is based on paging and page replacement techniques
* used in virtual memory systems. The replacement algorithm is
* similiar to "not frequently used" (NFU).
*
* each sector of the disk has a (struct) Cache element
* that contains a pointer to a cache buffer,
* and an "average usage" value. The average is a combination
* of long term usage and short term usage (somethink like 4bsd's load avg).
* there are also averages for total IO, read, write, hits, and reclaims.
* an average is increased for each reference (read/write),
* and all averages are decreased (by a percentage) every 100 accesses.
* the reference function is: avg += A_INC; A_INC = 16;
* the update function is: avg -= 1/8*avg;
* for these parameters, the total avg will tend between 12800 and 14400.
*/
#include <osbind.h>
#include "cache.h"
/* cache.c can compile with DLIBS or MWC */
#ifndef MWC
#define DLIBS
#endif
#ifdef MJC
#define ASM 1 /* inline assembler */
#endif
#define reg register
#ifdef OK
typedef long (*Func)(); /* function returning long */
#else
typedef char * Func; /* good enough */
#endif
/* define system variables */
#define bios_rw (*(Func*)0x000476) /* bios read/write routine */
#define bios_mc (*(Func*)0x00047E) /* bios media change routine */
#ifdef OK
Func old_rw;
Func cur_mc;
#else
long (*old_rw)(); /* previous rwabs routine */
long (*cur_mc)(); /* current mediach routine */
#endif
/* per-device data */
int c_dev = 0; /* cached device, A: */
int disable; /* flag to disable */
short stats [STATS]; /* global averages */
Cache cache [NSECT]; /* per sector averages and cbufs indices */
short csize; /* size of cache in sectors */
Sector* cbufs; /* cached sector buffers */
short cycle; /* count from 100 to 0 */
short nfree; /* next free cache sector */
#ifdef DLIBS
extern char *_base, *_break; /* program basepage, heap break */
long _STKSIZ = -2L; /* grab all free memory for heap */
#else /* MWC */
#include <basepage.h>
#define _base ((char *)BP)
#define _break _stack /* MWC combines _STKSIZ and _break as _stack */
char *_break = (char *)300*1024L; /* grab 300K for heap */
#endif
char header [] = "ST Floppy Disk Cache (by Eric Gisin)\r\n";
/*
* setup bios disk IO routines, terminate and stay resident.
*/
main(argc, argv)
int argc;
char **argv;
{
long stack;
extern long cache_rw();
extern char *sbrk(/*size_t n*/);
Cconws(header);
if (argc > 1) {
char *arg = argv[1];
if ('a' <= *arg && *arg <= 'z')
c_dev = *arg++ - 'a';
if ('A' <= *arg && *arg <= 'Z')
c_dev = *arg++ - 'A';
csize = atoi(arg) * 1024/sizeof(Sector);
}
if (csize < 100)
csize = 100; /* 50K is minimum */
#ifndef DEBUG
if (Rwabs(CSTAT, (char*)NULL, 0, 0, c_dev) != NULL) { /* already loaded */
Cconws("Cache already loaded\r\n");
return 0;
}
#endif
#if 0
cbufs = (Sector*) sbrk(csize * sizeof(Sector));
#else /* avoid loading long multiply */
cbufs = (Sector*) sbrk((size_t)&((Sector*)NULL)[csize]);
#endif
if (cbufs == NULL) {
Cconws("Not enough memory\r\n");
Pterm(-1);
}
/* set up our routines for bios rwabs */
stack = Super(NULL); /* super mode */
old_rw = bios_rw;
bios_rw = cache_rw;
cur_mc = bios_mc;
Super(stack); /* user mode */
cache_init();
Ptermres(_break - _base, 0); /* terminate, stay resident */
}
/* clear the cache */
cache_init()
{
reg int i;
cycle = CYCLE;
nfree = 0;
for (i = 0; i < STATS; i ++)
stats[i] = 0;
for (i = 0; i < NSECT; i ++) {
cache[i].avg = 0;
cache[i].buf = NOBUF;
}
return 0;
}
/* our BIOS rwabs routine */
long
cache_rw(func, addr, count, sect, dev)
int func; /* IO function */
Sector* addr; /* buffer address */
int count; /* sector count */
int sect; /* sector number */
int dev; /* disk drive */
{
reg int s;
reg int i;
int n;
long l;
if (dev != c_dev || disable)
return (*old_rw)(func, addr, count, sect, dev);
/* recognize magic function for cstat */
if (func == CSTAT)
return (sect==0) ? stats : cache;
if (func == CINIT)
return cache_init();
/* check for media change */
/* floppy rwabs will return -14 if real media change */
if ((*cur_mc)(dev) != 0) {
l = (*old_rw)(0, 0xFC0000, 0, 0, dev); /* dummy read */
if (l != 0) {
cache_init();
return l; /* always -14 (media changed)? */
}
}
if (sect < 0 || count < 0 || sect+count < 0)
return -5; /* sector out of range */
/* update cache averages */
for (i = 0; i < count; i ++) {
s = sect + i;
stats[TOTAL] += A_INC;
stats[((func&1)==0) ? READS : WRITES] += A_INC;
if (s < NSECT)
cache[s].avg += A_INC;
if (-- cycle < 0) {
cycle = CYCLE;
update_averages();
}
}
/* copy cache to read buffer */
if ((func&1)==0 && sect>0) {
for (i = 0; i < count; i ++) {
s = sect + i;
n = cache[s].buf;
if (n == NOBUF)
break;
copy_sector(&cbufs[n], addr++);
stats[HITS] += A_INC;
}
sect += i; count -= i;
}
/* do BIOS IO */
l = (*old_rw)(func, addr, count, sect, dev);
if (l != 0)
return l;
/* update cache from IO buffer */
for (i = 0; i < count; i ++) {
s = sect + i;
n = cache[s].buf;
if (n == NOBUF)
get_free(s);
n = cache[s].buf;
if (n != NOBUF)
copy_sector(addr + i, &cbufs[n]);
}
return 0;
}
/*
* update averages.
* this is called once per N accesses.
*/
update_averages()
{
reg int i;
int n;
for (i = 0; i < STATS; ++ i) {
stats[i] -= stats[i]+7 >> 3;
}
for (i = 0; i < NSECT; ++ i) {
cache[i].avg -= cache[i].avg+7 >> 3;
n = cache[i].buf;
if (!(n == NOBUF || 0<=n && n<csize)) {
disable = 1;
Cconws("<cache: internal error>");
}
}
}
/*
* get cache block with lowest avg less than requested block.
* somewhat inefficient, but should not be called often.
*/
get_free(c)
int c; /* sector */
{
reg int s;
reg Cache * p;
reg Cache * m;
if (nfree < csize) {
cache[c].buf = nfree++;
return;
}
/* find sector with a buffer and lowest avg */
p = &cache[0];
m = &cache[c];
for (s = 0; s < NSECT; s ++, p ++)
if (p->buf != NOBUF && p->avg <= m->avg)
m = p;
/* if that sector has lower avg than requested sector, reclaim */
if (m->avg < cache[c].avg) {
cache[c].buf = m->buf;
m->buf = NOBUF;
stats[RECLMS] += A_INC;
}
}
copy_sector(s, d)
Sector *s;
Sector *d;
{
int i;
reg char *dp = d->data; /* A5 in MJC */
reg char *sp = s->data; /* A4 in MJC */
if ((s&1) | (d&1)) { /* odd address! */
i = sizeof(Sector);
while (--i >= 0)
*dp++ = *sp++;
} else {
#ifndef ASM
/* usually generates loop: move.w (A0)+, (A1)+; dbra D0, loop */
*d = *s;
#else
/* this is twice as fast as above */
sizeof(Sector)/sizeof(long)/4 - 1; /* result to D0 */
/* isn't machine language fun! loop: */
asm(= 10972); /* move.l (A4)+, (A5)+ */
asm(= 10972); /* move.l (A4)+, (A5)+ */
asm(= 10972); /* move.l (A4)+, (A5)+ */
asm(= 10972); /* move.l (A4)+, (A5)+ */
asm(= 20936 = -10); /* dbra D0, loop */
#endif
}
}
/* allocate n bytes from heap (stack segment). NULL on error */
char *sbrk(n)
size_t n;
{
extern char *_break; /* current heap break */
char *p = _break;
int dummy; /* &dummy is almost SP */
_break += n;
if (_break+256 > (char*)&dummy) {
_break = p;
return NULL;
}
return p;
}
#if 0
int brk(p)
char *p; /* new break address */
{
int dummy; /* &dummy is almost SP */
extern char *_break; /* current break address */
extern char *end; /* initial _break; */
if (p < end || p+256 > (char *)&dummy)
return -1;
_break = p;
return 0;
}
#endif
@\Rogue\Monster\
else
echo "shar: Will not over write cache.c"
fi
if `test ! -s cstat.c`
then
echo "x - cstat.c"
cat > cstat.c << '@\Rogue\Monster\'
/*
* Disk Cache statistics
*/
#include <osbind.h>
#include "cache.h"
#define reg register
int verbose = 0;
extern char * c1_4f();
main(argc, argv)
char ** argv;
{
reg int i = 1, n;
reg short * stats;
reg Cache * cache;
int dev = 0
int total;
if (i < argc && argv[i][0]=='-') {
verbose = 1;
i ++;
}
if (i < argc)
if ('a' <= argv[i][0] && argv[i][0] <= 'z')
dev = argv[i][0] - 'a';
stats = Rwabs(CSTAT, 0L, 0, 0, dev);
cache = Rwabs(CSTAT, 0L, 0, 1, dev);
if (stats == NULL || cache == NULL) {
printf("Cache not installed\n");
return 1;
}
total = stats[0];
if (total==0) {
printf("No statistics yet\n");
return 1;
}
printf("Cache hits %s, ", c1_4f(stats[HITS], total));
printf("Disk reads %s, ", c1_4f(stats[READS]-stats[HITS], total));
printf("Disk writes %s; ", c1_4f(stats[WRITES], total));
printf("Buffer reclaims%s\n", c1_4f(stats[RECLMS], total));
if (!verbose)
return 0;
n = 0;
for (i = 0; i < NSECT; i ++) {
short avg, buf;
avg = cache[i].avg;
buf = cache[i].buf;
if (avg > 0 || buf != NOBUF) {
printf("%4d%c%5s ",
i, (buf == NOBUF) ? '.' : ':', c1_4f(avg, total));
if (++n % 6 == 0)
printf("\n");
}
}
printf("\n");
return 0;
}
/* convert a/b in %1.3f format */
char * c1_4f(a, b)
int a, b;
{
register int i;
register long l;
register char * p;
static char buf [12];
p = buf;
l = a;
i = a/b;
*p++ = (0<i && i<=9) ? '0'+i : ' ';
*p++ = '.';
for (i = 1; i <= 4; i++) {
l = 10*(l%b);
*p++ = '0' + (short)(l/b);
}
*p = '\0';
return buf;
}
@\Rogue\Monster\
else
echo "shar: Will not over write cstat.c"
fi
if `test ! -s cache.h`
then
echo "x - cache.h"
cat > cache.h << '@\Rogue\Monster\'
/*
* Floppy Disk Cache (Atari ST)
*/
#ifndef NULL /* belong in <stddef.h> */
#define NULL 0L
typedef long size_t;
#endif
/* magic functions to return internal tables to cstat */
#define CSTAT -1 /* return address of cache tables */
#define CINIT -2 /* clear cache */
/* cache parameters */
#define NSECT (82*2*10) /* maximum sectors cached */
#define CYCLE 100 /* update interval */
#define A_INC 16 /* increment for each reference */
/* indices for stats array */
#define TOTAL 0
#define HITS 1
#define READS 2
#define WRITES 3
#define RECLMS 4
#define STATS 5 /* elements in stats */
#define NOBUF (-1) /* no cached sector */
/* per sector cache information */
typedef struct {
short avg; /* average usage */
short buf; /* index of cached sector in cbufs [] */
} Cache;
typedef struct {
char data [512];
} Sector;
@\Rogue\Monster\
else
echo "shar: Will not over write cache.h"
fi
if `test ! -s readme`
then
echo "x - readme"
cat > readme << '@\Rogue\Monster\'
Floppy Disk Cache
What is a disk cache?
A disk cache is resident program that speeds up disk IO
by keeping a copy of recently used sectors of the disk
in RAM memory. It is similar to a RAM disk but has the
advantage that files are always up-to-date on the disk.
You can't lose files like a RAM disk does when the system crashes.
This cache will typically eliminate from 50-85% of disk IO if enough
cached sectors are installed. There is a slight CPU
overhead in copying sectors to the cache after disk IO.
Installation
The programs cache.ttp and cstat.ttp should be placed
in your directory for executable files, usually \bin.
cache.ttp should be run from a shell startup file;
for example gulam.g under Gulam or GemBoot's startup file.
The first argument to "cache" is the size of the cache in K-bytes,
which defaults to 50K. The size can be preceeded by a drive letter.
Run "cache" twice if you need to cache two drives.
If you install cache.ttp as \auto\cache.prg
there is no way to set the drive or cache size without modifing the source.
Operation
The cache clears automatically whenever you change disks.
Make sure all your disks have been formatted correctly with unique
serial numbers. An early version of twister and any bit-image
disk copy program will not generate unique serial numbers.
An easy way to check for unique serial numbers is:
list the root directory, switch disks, list the root directory.
If the directory lists are identical then the serial numbers may be the same.
You will probably trash disks even without a disk cache
when you have non-unique serial numbers.
The utility "cstat" will print some statistics averaged over
the last 1000 (approx.) sectors of IO.
Other Hints
Using a "fast" formatter like DC Format will speed up disk IO further.
You can also turn off write verify with DC Format or pokew in Gulam,
but there is some risk of losing files then.
It also helps to create all directories before anything else
is placed on a new disk, this speeds up file creation and deletion.
Compilation
This program is written completly in C for readability and portablity.
The cache program should be compiled with the dLibs library or MWC.
It requires the _base, _break, and _STKSIZ variables dLibs implements.
Non-standard compilers may require a "define short int".
Please indicate in the source and object when you make non-trivial changes.
Possible Extensions
Modify it for multiple hard disk partitions. This is non-trivial.
The current algorithm assumes sectors can be accessed through
cache[sector]. The cache array would be 160K bytes for a 20M byte drive,
and is scanned sequentially in a couple of places.
Eric Gisin, egisin@UWaterloo.CA
@\Rogue\Monster\
else
echo "shar: Will not over write readme"
fi
# to concatenate archives, remove anything after this line
exit 0