NAME
     lab xx - 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 := ~0;
     		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

                    Inferno Manual