9fans archive / 1997 / 07 / 29 /    prev next

From: G. David Butler gdb@dbS...
Subject: indexed directories and the File Server
Date: Thu, 10 Jul 1997 16:15:00 -0500

On to the next project.

One of the big things I've always hated about *NIX was the exponential
search time directories.  I am going to do something about it in Plan9.
I have some Btree routines I wrote in '89 that would work very well here.
They are very simple and allow only search, insert and delete.  No
first, last, next and previous.  An update (rename) would be a delete
followed by an insert.

I see two ways to implement this.  First, change the allocation method
for directores from an "array" to a Btree.  The first direct block
points to the root block of the tree.  The directory blocks then
could have a structure like this:

struct IndexEntry {
  struct DirEntry
  long RightNodeBlockPointer
}

struct IndexBlock {
  struct IndexEntry[number that fills page]
  long LeftNodeBlockPointer
  int number of used entries
}


The other way would be to build an index on the directory entries and
leave the current directory structure alone.  A question is where to
store the blocks for the index?  We could use the first direct block
as above as a pointer to the root of the Btree and leave the other
5 direct, 1 indirect and 1 double-indirect for the directory as usual.
The index block could look like (dir blocks would not change):

struct IndexEntry {
  long DirSlotNumber <The key is name @ dirslotnumber not dirslotnumber>
  long RightNodeBlockPointer
}

struct IndexBlock {
  long number of used entries
  long LeftNodeBlockPointer
  struct IndexEntry[number that fills page]
}


I would also like to start a concurrent discussion about the File
Server.  When I first started with Plan9, I thought having two
different kernels was weird.  Now I think the idea is sound since
they have such different roles.  So the next question, do we put the
above functionality into kfs and make the cpu kernel and kfs able
to handle file services efficiently or do we keep the current
File Server?  (If we keep the File Server, we need to add an il
version of a port 23 server to provide access to the console.  In
fact, that is a good idea for the cpu server too.  TCP is missing
in the File Server, as it should.)

Any comments?  :-)

David Butler
gdb@dbS...