lab 30 - wikifs

NAME

lab 30 - wikifs for inferno

DESCRIPTION

I ported plan 9's wikifs to inferno. There were various aspects of the application I wanted to learn about--such as, the cache, the transforms from wiki syntax to html, the method for using html templates, and the details of creating the namespace--that it seemed worthwhile to write it in limbo to absorb it all. I also had a hunch I'd be borrowing a lot of the code for my next file system.

The differences between the original and the port are small. The one significant difference is the approach to locking data structures.

The original uses locks for the Map and the Cache memory as well as file locks for accessing disk.

For the port I attempted to avoid the memory locks altogether. One reason being that when the Flush message is received I attempt to kill the proc processing the request, but that might leave stray locks. The file locks get freed when the file references are garbage collected.

To eliminate locks, I take advantage of limbo's garbage collection and try to use immutable types, or pass-by-value semantics.

For example, the Map is stored in a global variable. When the Map is read in from a file a new structure is created locally then assigned to that variable. The map is not changed (except for timestamps) after that and always remains self consistent.

The find routine for the map makes a local copy of the reference to the map and uses that safe knowing that the reference will stay unchanged for the duration of it's use. All memory will be collected if in the mean time a new map has been loaded.

With the cache I use a last-in-wins policy. This saves us the trouble of worrying about locks at the cost of extra reads of the disk file because of data added to the cache but lost because of overwriting the global cache references. Once data is cached is is unchanged (except for timestamps) so no locking is required once a function has a local reference to the cache data.

Here's an example of code from the cache handling. I create a new Wcache object, c, and I want to add it to the cache. The cache is an

       array of list of ref Wcache 

so when I add an item I create a new list and assign it to an array location, overwriting whatever list reference may have been there. It will be garbage collected if no other code references it. Also, the cache needs to be bounded, so I set a max length for every list. I remove items from the local copy of the list until there's room to add the new entry. Here tab is the global array.

      h := n%Nhash;
      ol := tab[h];
      c := ref Wcache(0, 0, 0, 0, nil, nil, nil, nil);
      # ... c is properly initialized before added to the list
      while(len ol >= Mcache){
          evict := -1;
          t := Sys->Maxint;
          for(l := ol; l != nil; l = tl l){
              if((hd l).use < t){
                  t = (hd l).use;
                  evict = (hd l).n;
              }
          }
          l = nil;
          for(;ol != nil; ol = tl ol)
              if((hd ol).n != evict)
                  l = hd ol :: l;
          ol = l;
      }
      # last in wins!
      tab[h] = c :: ol;

Because limbo lists are read only we don't need to worry that the references in the list change (although the referenced objects might). We must guard against changing the referenced objects, except only trivially for the timestamps, and treat them as read only.

Not having to worry about locks does simplify the code. Enough that I'd look for opportunities to eliminate locks like this style of programming in the future.

FILES

lookup.b testwrite.b wiki.b wiki.m wiki2html.b wiki2text.b wikifs.b wikipost.b