Thursday, May 19, 2005

inferno wiki

i have setup a demo inferno wiki for wikifs on inferno.

lab 30 - wikifs


lab 30 - wikifs for inferno


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.


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

Sunday, May 08, 2005

lab 29 - embedded graphs


lab 29 - embedded graphs


Taking inspiration from Mathematica's notebook user interface, I tried implementing graphs embedded within the shell window, wm/sh. The idea being that a scrolling page of graphs, text and images is easier to manage than many overlapping windows. I feel this especially while I'm iteratively running commands, generating data and viewing graphs.

The shell window provides a history of activity. By including other windows in that history I can look back at the graphs I generated, what data generated them, what command was used to generate the data, and so on. With overlapping windows this context can be lost.

Wm/sh used in this way now behaves as a rudimentary window manager. It is easy to imagine ways in which it becomes inconvient to use. Such as interacting with two windows separated by a large block of text. But it still might add a useful alternative to the wm/wm and acme window manager styles.


The graphs are Tk windows embedded within the text of the shell window. The graph can respond to events, and in this case clicking inside the graph updates the displayed coordinates.

I didn't know how to do any of this, or even that Tk made it possible, until I looked at the editor wm/brutus. Brutus seems to be a forgotten application within Inferno and not very stable. It supports embedding of images, tables, and excerpts of code within the text and simple formatting. It is still useful to trawl through such programs for snippets of code. Finding the code to embed Tk windows within text was enlightening.

I used the brutus extension interface brutusext.m to implement the graph module. The graph module itself was adapted from /appl/math/gr.b.

The shell already comes with a file system inteface /chan/shctl to communicate with external programs. I added to wm/sh two commands to be recognized by this file.

          % echo graph filename > /chan/shctl

where filename contains a set of coordinates. Wm/sh displays a graph within the shell window. embedgraph

I also added a command to display images. For example,

          % echo bitmap /icons/coin.bit > /chan/shctl

To clear memory from all the Tk objects created,

          % echo clear >/chan/shctl


By adding this feature many other possibilities and questions quickly arise. How can we collapse individual embedded windows? Can we cut and paste the embeds? What about saving the whole contents of the shell window, including embeds, and restoring them later for browsing. Wm/brutus again points the way to doing some of this, by creating a simple markup using SGML or sexprs to store the contents as an expression.


graph.b sh.b

Sunday, May 01, 2005


I took a break from this blog and inferno coding for March and April.

During that time I've been reading about web services, deconstructing Google's offerings and AJAX, and most importantly reading about the REST architectural style for the web.

I like the approach taken by the Plan9 wikifs to offer web pages by first writing a filesystem, then just mount that into the httpd namespace.

I'd like to experiment with that approach further to implement RESTful services like

I've been porting wikifs to Inferno to learn more how it's done. I'll post that soon.

I'd like to update the Inferno httpd to support HTTP 1.1 and basic authentication. That shouldn't be hard considering Plan9's supports this and the code is very similar.