bryce@COGSCI.BERKELEY.EDU (Bryce Nesbitt) (05/11/87)
This article describes a easy way to get faster directories under AmigaDOS. The method described is: 1> 100% compatible. 2> Takes zero bytes of ram. 3> Works with existing disks -> no format changes. 4> Takes zero time to load. All it requires is a tiny li woah!!! EaThQuAke!!! (Good thing I don't live on landfill) (Darn California earthquakes are always interrupting things) (I would guess about 4.7 and from the south) ttle change to the source code to AmigaDOS; which sadly I do not have access to. :-( The dos function that gets the next directory entry is Brain_Dead (like most of the filesystem). It does many, many things as to guarantee that it is slow! Two examples: 1> It reads entries in HASH order; as far as the disk is concered this means RANDOM order. The dos could read one entry from Track 20 then another from 21 and then end up back at 20 for the next. 2> It reads *all* the extension blocks of a file for the purpose of counting the total blocks; since the filesystem will currently fill every block full except the last, a DIVIDE will do the same at much less cost. Here is a example snoop of a directory taken under the standard AmigaDOG filesystem: Block 880 -> Track 40 Head 0 Block 881 -> Track 40 Head 0 Block 882 -> Track 40 Head 0 Block 889 -> Track 40 Head 0 Block 891 -> Track 40 Head 1 Block 1011 -> Track 45 Head 1 Block 1013 -> Track 46 Head 0 Block 1039 -> Track 47 Head 0 Block 1041 -> Track 47 Head 0 Block 1082 -> Track 49 Head 0 Block 1089 -> Track 49 Head 1 Block 1180 -> Track 53 Head 1 Block 1183 -> Track 53 Head 1 Block 1184 -> Track 53 Head 1 Block 1186 -> Track 53 Head 1 Block 1199 -> Track 54 Head 1 Block 1186 -> Track 53 Head 1 Block 1200 -> Track 54 Head 1 Block 1202 -> Track 54 Head 1 Block 1273 -> Track 57 Head 1 Block 1296 -> Track 58 Head 1 Block 1299 -> Track 59 Head 0 Block 1301 -> Track 59 Head 0 Block 1303 -> Track 59 Head 0 Block 1305 -> Track 59 Head 0 Block 883 -> Track 40 Head 0 Block 1307 -> Track 59 Head 0 Block 1187 -> Track 53 Head 1 Notice how it goes from Track 53 to 54 to 53 to 54? That's 3 steps; a *LONG* time. Now take a look at what the program presented here does; Block 880 -> Track 40 Head 0 Block 881 -> Track 40 Head 0 Block 882 -> Track 40 Head 0 Block 883 -> Track 40 Head 0 Block 889 -> Track 40 Head 0 Block 891 -> Track 40 Head 1 Block 1011 -> Track 45 Head 1 Block 1013 -> Track 46 Head 0 Block 1039 -> Track 47 Head 0 Block 1041 -> Track 47 Head 0 Block 1082 -> Track 49 Head 0 Block 1089 -> Track 49 Head 1 Block 1180 -> Track 53 Head 1 Block 1183 -> Track 53 Head 1 Block 1184 -> Track 53 Head 1 Block 1186 -> Track 53 Head 1 Block 1187 -> Track 53 Head 1 Block 1200 -> Track 54 Head 1 Block 1202 -> Track 54 Head 1 Block 1273 -> Track 57 Head 1 Block 1296 -> Track 58 Head 1 Block 1299 -> Track 59 Head 0 Block 1301 -> Track 59 Head 0 Block 1303 -> Track 59 Head 0 Block 1305 -> Track 59 Head 0 Block 1307 -> Track 59 Head 0 It *SORTS* the blocks to reduce the number of needed seeks. It also DIVIDES the number of bytes to get the number of blocks in the file. (ie: It assumes each block is full -> a fair assumption considering the current filesystem and the relative unimportance of the information) It's not perfect; hash chains can force it to deviate, but it's better, and if properly implemented, totaly transparant. This program is not such a beast; it is a quick rehash of a program done back when I tried to convince Commodore to place such a change in V1.2. [Nothing happened]. It is not fully finished, I decided the old filesystem is incurable; and must be 'burried deep'. Fortunatly it is very clean to invent a *NEW* filesystem. To start it "RUN SPEEDDIR" from a CLI. It will replace directory handlers for drive DF1:. (Use a disk editor and change the string if you only have a DF0:) It works by patching the pr_PktWait field and handling packets of type ExNext. For each packet it gets, it sets up a brand new message port, ,calls Trackdisk, then deallocates things. It will leave the drive on after a read. -> NOTE <- I do not know how to link into the buffers that AmigaDOS keeps; this program is faster *WITHOUT* the use of cached blocks. If anyone can help me on this point; PLEASE DO! DISCLAIMER: This code is UNFINISHED, probably BUGGY, is UNCLEAN and is intended for use by HACKERS ONLY. Commodore-Amiga/Metacomo you are welcome to use these ideas for the next release -> but, better yet, write a *real* filesystem. ------------ Cut Here ------------- begin 777 speeddir M```#\P`````````!``````````````#;```#Z0```-LL>``$0_H#0$ZN_F@L/ M0"I`0?D```-2(@A.KO]22H!G```8*$!!^0```#PI2`!8+'@`!'``3J[^PG`5Y M3G5(YP`B+'@`!)/)3J[^V@:`````7"!`)$!.KOZ`($I.KOZ,($`B:``*($H,F M:0`8``IG!DS?1`!.=4S?1`!(YS#Z+'@`!"`I`!CE@"A`(#P```(`(CP``0`"' M3J[_.DJ`9P`!-B9`""P`!P!T9D@@/````2`B/``!``%.KO\Z*4``:&<``11"! MK`!L0JP`<"`4($MA``'\#),````"9@``]'!'($O1_````!@B;`!H(MA1R/_\Y M0I1*K`!H9P``\"`L`&QF+'#_<O\D+`!P=D<@;`!HM)A5R__\9!`B:/_\L(ECB M!'(`(`E1R__J2H%K``"P($MA``&<:P``H&8``)8@+`!L*6L!\`!L2H!F!BEKM M``0`<"BK``1R`B`K`?RR@&<(<OVR@&8``&PI00`$0^P`"$'K`;!P`!`8$L`29 MV%'(__P@*P%`",``'RE``'0@*P%$*4``?&<2@/P!Z$YV,@!(P$A!2D%G`E*`< M*4``@$'K`:1#[`"$(M@BV"+80^P`D$'K`4AP`!`8$L`2V%'(__R5RF`>-'P`$ MVV`8-'P`9V`2(FP`:"`\```!($ZN_RXT?`#H(#P```(`(DM.KO\ND\E.KO[:T M($`A2@"4(@I,WU\,9@1P_V`"<`!(YP`B+P<>.0"_X`$*!P`"$\<`O^`!+A\L0 M>``$(T``#"-!`!`@*0`$(T@`!")I```@0$ZN_I)@`/WX+PHB/``!``%P(DZN. M_SHD0$J`9Q1P_TZN_K9R_[*`9@XB2G`B3J[_+B1?<`!.=15```\5?`````X5- M?``$``A"*@`)D\E.KO[:)4``$$'J`!0@B%B00J@`!"%(``@@"B1?3G4O"7#_G M$T``""-``!1P`!`I``].KOZP(E]P(D[N_RY(YR`2+'@`!"0`)DB?_````#AP. M-R!/0AA1R/_\80#_8F=6+T``#A]\``4`"$'Y```#5R)/<`%R`$ZN_D1*@&8X& M/WP``@`<+WP```(``"1P">&B+T(`+"]+`"@B3TZN_C@B;P`.80#_?!`O`!_?` M_````#A,WT@$3G5P_TYU9&]S+FQI8G)A<GD`9&8Q.@!T<F%C:V1I<VLN9&5VK H:6-E``````````/L`````P````````+X````)@```!(````````#\FLNC `` end ---------- Stop Cutting ----------- -Bryce Nesbitt- // Dedicated to eradicating all traces of \\// this latest world-wide outbreak of BCPL. bryce@cogsci.berkeley.edu
ewhac@well.UUCP (Leo 'Bols Ewhac' Schwab) (05/12/87)
[ Removal of this line by any means is punishable by Federal law. ]
Shit.
It seems like every time I come up with something resembling a useful
utility, someone else beats me to it, and comes out with something almost
the same.
This was the case a looong time ago with a program I called LITE
(Leo's Incredible Terminal Emulator). Then David Wecker came out with his
VT100 emulator, and suddenly there didn't seem to be any point in it any
more (no slight upon you, Dave; it's an excellent program).
Now it's happened again. I *WAS* going to write a program for
publication in Amazing Computing that did faster directories. Then I found
out that Dave Haynie has been working on almost the exact same program for
the exact same magazine. No problem, thinks I, I'll just clean it up a bit
and throw it at the Net, or RoboCity News, or something.
Now I log in to find this gentleman has already posted a program to
help speed up directories. It's enough to make a guy beat his head against
the keyboard. In fact, I think I will.
nhbg mjmn ,kjh ,kmjnh nhbgvf bgvf]trnhbgvf mnjhbg .l,kmj .,m!!!!
Sigh.
Oh well, you may as well have the program to see what I did. It
uses the AmigaDOG ACTION_GET_BLOCK packet to get raw disk blocks off the
disk and do things to them. Preliminary studies indicate that directories
are only 25% faster on average. Speed increases ranged from 50% to -5%
(yup, sorting things actually makes it run slower). The test beds I used
were Fish Disk 13 (all that BASIC crud), and the three-disk Portal program
from Activision. 'dir' on Portal disk #2 takes about 2:35. My program
takes about 1:29 (as I recall).
Known limitations: Running the program on the boot disk crashes the
machine (if you type 'cd' and get "DF0:" as a response, you are on the boot
device). If you 'cd' into a directory, remove the disk in question, then
run the program, it fails gracefully, but gives an unhelpful error code. It
doesn't work on the RAM: driver.
Dave Haynie and I have been conducting an E-mail discussion on our
respective programs, and based on his description, his deserves publication
more than mine does, and he has been working longer on it. So Dave,
consider this official notification: Clean up your program and send it off
to Amazing.
I'm not trying to be negative about this..... All right, maybe I
am. But I mean, gee whiz. This is frustrating.....
Oh well, hope you find the program useful. External hacking to
improve it is encouraged.
By the way, the program is called 'eless.'
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
________ ___ Leo L. Schwab
\ /___--__ The Guy in The Cape
___ ___ /\ ---##\ ihnp4!ptsfa!well!ewhac
/ X \_____ | __ _---)) ..or..
/ /_\-- -----+==____\ // \ _ well ---\
___ ( o---+------------------O/ \/ \ dual ----> !unicom!ewhac
\ / ___ \_ (`o ) hplabs -/ ("AE-wack")
____ \___/ \_/
Recumbent Bikes: "Work FOR? I don't work FOR
The _O_n_l_y Way To Fly! anybody! I'm just having fun."
_-_-_-_-_-_ All right, fine. Don't cut here. See if I care... _-_-_-_-_-_-_
/* :ts=8 bk=0
*
* eless.c: An attempt at a reasonable-speed 'ls' program by fiddling
* with the DOS.
*
* Compiles under Manx 3.20 and patched 3.40.
* cc eless.c
* ln eless.c -lc -o eless
*
* Leo L. Schwab 8704.26 (415)-456-6565
*/
#include <exec/types.h>
#include <exec/memory.h>
#include <libraries/dosextens.h>
#define BLOCKSIZE 128
#define STARTTAB 6
#define ENDTAB (BLOCKSIZE-51)
#define TABSIZ (BLOCKSIZE-56)
#define FILENAME (BLOCKSIZE-20)
#define HASHCHAIN (BLOCKSIZE-4)
#define SECONDARY (BLOCKSIZE-1)
#define ST_DIR 2
#define ST_FILE -3
/*
* Note: I usually declare Amiga functions this way to disable the compiler's
* type checking. This allows me to assign values to variables without
* explicitly casting them to the appropriate type. In reality, these
* functions return things entirely different from the way I've declared
* them. For example, CreatePort() should really be declared as:
*
* struct MsgPort *CreatePort();
*
* Caveat Programmer.
*/
extern void *AllocMem(), *CreatePort(), *RemTail(), *FindTask();
extern long Lock(), Examine();
long dopacket();
int longcmp(), namecmp();
struct StandardPacket *packet;
struct FileInfoBlock *fib;
struct FileLock *lock;
struct InfoData *id;
struct MsgPort *dosreply;
BPTR lok;
long *buf, hashtab[TABSIZ];
main (ac, av)
char **av;
{
int flag;
openstuff ();
if (ac < 2) /* No arguments; do current directory */
printdir (((struct Process *) FindTask (0L)) -> pr_CurrentDir);
else { /* Arguments; treat as directories */
flag = (ac > 2);
while (++av, --ac) {
if (!(lok = Lock (*av, ACCESS_READ))) {
printf ("%s: Not found.\n", *av);
if (ac > 1)
putchar ('\n');
continue;
}
if (!Examine (lok, fib))
die ("Examine failed.");
if (fib -> fib_DirEntryType < 0) {
printf ("%s: Not a directory.\n", *av);
if (ac > 1)
putchar ('\n');
continue;
}
if (flag)
printf ("%s:\n", *av);
printdir (lok);
if (ac > 1)
putchar ('\n');
UnLock (lok); lok = NULL;
}
}
closestuff ();
}
/*
* This function prints the directory in a nice, pretty columnar format.
*/
printdir (dirlock)
BPTR dirlock;
{
struct List namelist;
register struct Node *name, **namearray;
long args[2];
register int i, n;
int len = 0, ncols, nlines, nfiles = 0;
char fmt1[16], fmt2[16];
char *fn = (char *) (&buf[FILENAME]) + 1;
lock = (struct FileLock *) (dirlock << 2);
args[0] = lock -> fl_Key; /* Block number */
args[1] = (long) buf >> 2; /* BPTR to buffer */
/* Attempt to get raw directory block. */
if (!dopacket (lock -> fl_Task, ACTION_GET_BLOCK, args, 2)) {
if (packet -> sp_Pkt.dp_Res2 == ERROR_ACTION_NOT_KNOWN)
printf ("Not a block device.\n");
else
printf ("Error %ld while getting dirblock.\n",
packet -> sp_Pkt.dp_Res2);
return;
}
/* Copy DOS's hash table into our array. */
for (i=0; i<TABSIZ; i++)
hashtab[i] = buf[i+STARTTAB];
NewList (&namelist);
while (1) {
/* Sort hash table. */
qsort (hashtab, TABSIZ, sizeof (long), longcmp);
if (!hashtab[0]) /* Empty hash table */
break;
/*
* Retrieve disk blocks according to sorted hash table and
* collect filenames.
*/
for (i=0; hashtab[i] && i<TABSIZ; i++) {
args[0] = hashtab[i];
dopacket (lock -> fl_Task, ACTION_GET_BLOCK, args, 2);
if (!(name = AllocMem (sizeof (*name) + *(fn-1) + 1L,
MEMF_CLEAR))) {
puts ("Node memory allocation failure.");
goto bombout;
}
name -> ln_Name = (char *) name + sizeof (*name);
name -> ln_Type = (buf[SECONDARY] == ST_DIR);
fn[*(fn-1)] = '\0'; /* Force null-termination */
strcpy (name -> ln_Name, fn);
AddTail (&namelist, name);
nfiles++; /* Number of files found */
hashtab[i] = buf[HASHCHAIN];
}
}
if (!nfiles) /* No files */
return;
/* Create array that qsort can deal with. */
if (!(namearray = AllocMem
((long) nfiles * sizeof (char *), MEMF_CLEAR))) {
puts ("Name array allocation failure.");
goto bombout;
}
/* Load up the array. */
for (name = namelist.lh_Head, i=0;
name -> ln_Succ;
name = name -> ln_Succ, i++)
namearray[i] = name;
/* Alphabetize filenames. */
qsort (namearray, nfiles, sizeof (struct Node *), namecmp);
/* Find longest string so we can format intelligently. */
for (i=0; i<nfiles; i++)
if ((n = strlen (namearray[i] -> ln_Name)) > len)
len = n;
len += 2; /* Inter-name spacing */
/* Print them suckers out */
ncols = 77 / len; /* Assume CON: is 77 columns */
nlines = nfiles/ncols + (nfiles%ncols != 0);
sprintf (fmt1, "%%-%ds", len); /* Normal format string */
sprintf (fmt2, "\033[33m%%-%ds\033[m", len); /* For directories */
for (i=0; i<nlines; i++) {
for (n=i; n<nfiles; n+=nlines)
printf (namearray[n] -> ln_Type ? fmt2 : fmt1,
namearray[n] -> ln_Name);
putchar ('\n');
}
/* Phew! Now free all the stuff we allocated. */
bombout:
freenamelist (&namelist);
if (namearray)
FreeMem (namearray, (long) nfiles * sizeof (struct Node *));
}
freenamelist (list)
struct List *list;
{
register struct Node *now;
while (now = RemTail (list))
FreeMem (now, sizeof (*now) + strlen (now -> ln_Name) + 1L);
}
/*
* This function assumes the existence of a properly initialized
* standardpacket structure called "packet" and a reply port called
* "dosreply". A more general function would not do this.
*
* This function is synchronous i.e. it doesn't return until the specified
* action has been performed.
*/
long
dopacket (proc, action, args, nargs)
struct MsgPort *proc;
long action;
register long *args;
register int nargs;
{
register long *argp = &packet -> sp_Pkt.dp_Arg1;
for (; nargs>0; nargs--)
*argp++ = *args++;
/*
* AmigaDOS scribbles over the reply port, so we have to initialize
* it every time we send a packet.
*/
packet -> sp_Pkt.dp_Port = dosreply;
packet -> sp_Pkt.dp_Type = action;
PutMsg (proc, packet);
WaitPort (dosreply);
GetMsg (dosreply);
return (packet -> sp_Pkt.dp_Res1);
}
/*
* These functions are called by qsort(). The sense of camparisons is
* reversed in longcmp to get a reverse sort (largest elements first).
*/
longcmp (foo, bar)
long *foo, *bar;
{
/*
* We have to do it this way because qsort() expects an int to be
* returned. Subtracting longs directly might overflow a 16-bit int.
*/
return ((*foo < *bar) - (*foo > *bar));
}
namecmp (foo, bar)
struct Node **foo, **bar;
{
return (strcmp ((*foo) -> ln_Name, (*bar) -> ln_Name));
}
/*
* Resource allocation/deallocation routines.
*/
openstuff ()
{
if (!(packet = AllocMem ((long) sizeof (*packet), MEMF_CLEAR)))
die ("Can't allocate packet space.");
if (!(dosreply = CreatePort (NULL, NULL)))
die ("Dos reply port create failed.");
packet -> sp_Msg.mn_Node.ln_Name = (char *) &packet -> sp_Pkt;
packet -> sp_Pkt.dp_Link = &packet -> sp_Msg;
if (!(fib = AllocMem ((long) sizeof (*fib), MEMF_CLEAR)))
die ("Can't allocate FileInfoBlock.");
/*
* Note: This allocation may not work with DMA hard disks.
*/
if (!(buf = AllocMem (BLOCKSIZE * 4L, MEMF_CHIP | MEMF_PUBLIC)))
die ("Couldn't allocate sector buffer.");
}
closestuff ()
{
if (lok) UnLock (lok);
if (buf) FreeMem (buf, BLOCKSIZE * 4L);
if (fib) FreeMem (fib, (long) sizeof (*fib));
if (dosreply) DeletePort (dosreply);
if (packet) FreeMem (packet, (long) sizeof (*packet));
}
die (str)
char *str;
{
puts (str);
closestuff ();
exit (1);
}