Stewart's Honors Project - The Walnut Kernel

To Design and Implement an Object Store for the Walnut Kernel with support for advanced features such as transactions and versioning.

Abstract

The Walnut Kernel is a persistent, capability based operating system kernel developed at and extending the previous work in the School of Computer Science and Software Engineering at Monash University. Building on work in the Password-Capability System, Walnut has some very unique features such as its capability architecture, charging scheme and persistence. Walnut requires a slightly specialised set of features from its equivalent of a file system, the Walnut object store. Various deficiencies with the original design were found, and it was decided that alternative systems should be explored.

This thesis extends initial work on the Walnut kernel by examining the issues related to its object store. Other operating systems use a file system as their method of on disk storage and various file systems are closely examined for their efficiency, reliability and possible applicability to a Walnut system.

As processes are persistent in Walnut, care must be taken to ensure these can be restored from disk in a consistent state. That is, the image on disk should match the appearance of these objects at a specific time, in essence a ``snapshot'' of the process and all objects it is using. We call this the problem of inter-object dependencies as the process object depends on a specific version of the objects it has loaded.

The addition of the revision tracking of objects is examined with the aim towards helping solve the problem of inter-object dependencies and remove the consequences of user error. A discussion on the possible Walnut interface and possible security implications is included and it is found that there needs to be further exploration of "Temporal Windowing" before access to previous revisions of objects can be done in both a flexible and secure manner.

The near complete design of a new object store for the Walnut is presented providing a flexible volume format that can be extended to encompass future ideas and features. Knowledge gained from other systems helps us in determining that this system has the capacity to fulfil the listed requirements. A proof of concept implementation in a simulation environment is presented with support for most of the features discussed and reasonable performance considering its stage in development. The implementation has been written so that it can be extended and eventually incorporated into Walnut.

Progress

I recorded progress, thoughts and comments in my Weblog, inside the hons-project category.

Interesting Things

If you are interested in some Walnut related things, sometimes not too academic :)

• Some photos of Walnut related things are here.
• My bibtex bibliography as html or annotated bibtex. Many of these references will be very useful if you want an understanding of Walnut, persistence or file systems.

Available Documents

• Project Overview (PDF) - a rough, draft like, sketchy overview of thoughts on the project. NOTE: this document won't be maintained or revised and is out of date.
• Research Proposal (PDF) - I handed this in as the first assessable piece of work.
• Interim Presentation (PDF) - Slides from my Interim Presentation.
• Final Presentation (HTML) - Slides from my final presentation, given on Thursday 30th October at Monash University.
• Testkit Documentation (PDF) - Preliminary Documentation on my Testkit package. NOTE: This is not the final document.
• On Disk Format Documentation and Justification (PDF) - Preliminary documentation and justification for the on disk format. NOTE: This document is out of date, look at the thesis for up to date documentation.
• Literature Review - Reviews existing and related literature.
• Thesis (759K PDF) or (393K PS.gz) - The finished product, my honors thesis.
• cxref output for the FCFS and testkit source (HTML) - cxref is a C cross-referencing and documentation tool. This is the output produced by it, which can give a better indication of the relationships between parts of the code.
• References - HTML version of my bibtex file used in the thesis

Other Documents Relating to Walnut

There are documents by several other poeple detailing parts of the theory behind Walnut, here are some of them (look at my bibliography for more references):

• The original thesis on Walnut (PhD thesis of Maurice Castro) can be found at: http://www.csse.monash.edu.au/~rdp/fetch/castro-thesis.ps
• Implementation of stdio and IPC on Walnut: http://www.csse.monash.edu.au/~carlo/archive/PAPERS/msc.thesis.ck.pdf
• Charging in a secure environment (garbage collection of objects in Walnut): http://www.csse.monash.edu.au/~rdp/hp/Bremen-paper.pdf
• The original Password-Capability System:http://www.csse.monash.edu.au/~rdp/hp/apwcs.pdf

Available Code

The following code should be considered pre-alpha, pre-working, pre-everything really... It's a tarball of my working directory - literally. It will be mostly broken - get used to it.

• FCFS and Testkit (fcfs.tar.gz) 70kb - A lot of stuff works in this release - which is current to what was submitted in support of my thesis. It is distributed under the GNU Public License. Expect improvements in the future. Note that the included documentation is probably very out of date.

Really Bad Docs

A quick runthrough of some of the stuff you can do with the current code. Note that I've removed some of the output from the listings here as it's just a bit verbose and lists what testkit is doing with block devices and caching. Not all that interesting unless you're a cache freak.

• Make sure you have glib installed and 'glib-config' is in your path
• Compile testkit and then fcfs:
  $ cd fcfs/testkit && make && cd .. && make
• Create a test "disk" to turn into a volume (NOTE: the mkflie utility will take advantage of sparse files if you file system supports it, and although this does save disk space, a performance hit will be felt - so don't base benchmarks on this - use dd to create an empty file, or use a real block device)
  $ ./mkfile testvolume 4096 10240
• Create a file system on the test volume:
  $ ./mkfs testvolume 4096 10240 volumename

Going to create volume 'volumename' with 0x2800 blocks at 0x1000 bytes each
                                                                                
ALLOCATION GROUPS: 0x8, each 0x500
SuperBlock at Block 0
BACKUP SuperBlock at Block 0x27ff
BACKUP SuperBlock at Block 0x50000500000 (offset 0x500)
BACKUP SuperBlock at Block 0xa0000a00000 (offset 0xa00)
BACKUP SuperBlock at Block 0xf0000f00000 (offset 0xf00)
BACKUP SuperBlock at Block 0x140001400000 (offset 0x1400)
BACKUP SuperBlock at Block 0x190001900000 (offset 0x1900)
BACKUP SuperBlock at Block 0x1e0001e00000 (offset 0x1e00)
BACKUP SuperBlock at Block 0x230002300000 (offset 0x2300)
BITMAP: Zeroing 0x2 (offset 2000) length 1
BITMAP: Zeroing 0x502 (offset 502000) length 1
BITMAP: Zeroing 0xa02 (offset a02000) length 1
BITMAP: Zeroing 0xf02 (offset f02000) length 1
BITMAP: Zeroing 0x1402 (offset 1402000) length 1
BITMAP: Zeroing 0x1902 (offset 1902000) length 1
BITMAP: Zeroing 0x1e02 (offset 1e02000) length 1
BITMAP: Zeroing 0x2302 (offset 2302000) length 1
Onode Index node created at: AG: 0, Start: 2, Len: 1
****ONODE INDEX**** 2

• Now we can get some information about the volume using the volinfo utility (NOTE: there is a small bug in the current code, that's why you get a WARNING-CORRUPT message, but it does not really matter):
  $ ./volinfo testvolume 4096 10240

Primary Superblock
------------------
Volume name is: volumename
MAGIC1:  0x46436673     MAGIC2: 0x3f8ec2a1
VERSION: 0x10001        BITS: 64         LENGTH: 320 bytes
Block Size: 4096        No. Blocks: 10240
WARNING-CORRUPT: This is the start of an Allocation Group
FLAGS: 0x3000000001
        - Volume has been used by EXPERIMENTAL code. It's probably b0rked.
        - Volume journals Meta Data
Number of Clean Mounts:   0
Number of UnClean Mounts: 0
Time Created:             1068436506
Time last cleanly mounted:1068436506
Time last dirty mounted:  0
 
Onode Index:
------------
ONode Index location: 2
Number of onodes: 0 used, 254 available, 0 total
Next ID: 1      Node Size: 254
 
 
Checking end of disk super block backup...
This is the End of a volume
FLAGS: 0x3000000002
        - Volume has been used by EXPERIMENTAL code. It's probably b0rked.
        - Volume journals Meta Data
Checking used blocks...
-----------------------
AG 0: 0,1,2,
AG 1: 0,1,
AG 2: 0,1,
AG 3: 0,1,
AG 4: 0,1,
AG 5: 0,1,
AG 6: 0,1,
AG 7: 0,1,
Onode Index Node: 0 in block 2
Used: 0/254
  key:block

• Now we can add an object to the volume:
  $ ./fcfs_newobj testvolume test_v1

test_v1 in fork 1

• We can re-run volinfo and find out the o-node id of the newly created object:
  $ ./volinfo testvolume 4096 10240

Primary Superblock
------------------
Volume name is: volumename
MAGIC1:  0x46436673     MAGIC2: 0x3f8ec2a1
VERSION: 0x10001        BITS: 64         LENGTH: 320 bytes
Block Size: 4096        No. Blocks: 10240
WARNING-CORRUPT: This is the start of an Allocation Group
FLAGS: 0x3000000001
        - Volume has been used by EXPERIMENTAL code. It's probably b0rked.
        - Volume journals Meta Data
Number of Clean Mounts:   0
Number of UnClean Mounts: 0
Time Created:             1068437228
Time last cleanly mounted:1068437228
Time last dirty mounted:  0
 
Onode Index:
------------
ONode Index location: 2
Number of onodes: 0 used, 254 available, 0 total
Next ID: 2      Node Size: 254
 
 
Checking end of disk super block backup...
This is the End of a volume
FLAGS: 0x3000000002
        - Volume has been used by EXPERIMENTAL code. It's probably b0rked.
        - Volume journals Meta Data
Checking used blocks...
-----------------------
AG 0: 0,1,2,3,11,301,302,303,
AG 1: 0,1,
AG 2: 0,1,
AG 3: 0,1,
AG 4: 0,1,
AG 5: 0,1,
AG 6: 0,1,
AG 7: 0,1,
Onode Index Node: 0 in block 2
Used: 1/254
  key:block
  1804289383:3
        Onode Index LEAF: 1 in block 3
        Used: 1/254
          key:block
          1804289383:11

• Now we can update the object (with o-node id of 1804289383) which will add a revision to it:
  $ ./fcfs_updateobj testvolume test_v2 0 10 1804289383

FOUND A LEAF!
 
READ LEAF 0x1
        block 3
        used  1
leaf i = 0, 1804289383 11
+++++++GOING TO GO AND WRITE 0++++++++
*******WRITING 10 bytes*******

• The final volinfo run will tell us that we've used a few more blocks of disk space, as volinfo does not yet list revisions stored on disk. You can see that the information has been written by using the hexdump program (not included) and examining the contents of the disk.
  $ ./volinfo testvolume 4096 10240

Primary Superblock
------------------
Volume name is: volumename
MAGIC1:  0x46436673     MAGIC2: 0x3f8ec2a1
VERSION: 0x10001        BITS: 64         LENGTH: 320 bytes
Block Size: 4096        No. Blocks: 10240
WARNING-CORRUPT: This is the start of an Allocation Group
FLAGS: 0x3000000001
        - Volume has been used by EXPERIMENTAL code. It's probably b0rked.
        - Volume journals Meta Data
Number of Clean Mounts:   0
Number of UnClean Mounts: 0
Time Created:             1068437228
Time last cleanly mounted:1068437228
Time last dirty mounted:  0
 
Onode Index:
------------
ONode Index location: 2
Number of onodes: 0 used, 254 available, 0 total
Next ID: 2      Node Size: 254
 
 
Checking end of disk super block backup...
This is the End of a volume
FLAGS: 0x3000000002
        - Volume has been used by EXPERIMENTAL code. It's probably b0rked.
        - Volume journals Meta Data
Checking used blocks...
-----------------------
AG 0: 0,1,2,3,11,301,302,303,304,305,
AG 1: 0,1,
AG 2: 0,1,
AG 3: 0,1,
AG 4: 0,1,
AG 5: 0,1,
AG 6: 0,1,
AG 7: 0,1,
Onode Index Node: 0 in block 2
Used: 1/254
  key:block
  1804289383:3
        Onode Index LEAF: 1 in block 3
        Used: 1/254
          key:block
          1804289383:11

Mirrors

• FlamingSpork my personal site.
• Monash University School of Computer Science and Software Engineering Honors Projects is keeping a mirror of the web sites relating to honors projects. NOTE: This is probably never going to be updated.