Fri Nov 25 14:14:34 EST 2011

Writing stateful code

I've recently had the pleasure (!) to write some file system code.
The main problems I run into are 1. robustness (error detection and
recovery) and 2. simply getting it to work correctly in the first
place.  I talk about robustness somewhere else[1].  This post is about
how to handle stateful code.

File systems generally have a lot of state and a lot of invariants
covering relationships between state elements.

Often a lot of this state is cache or index data: some *duplication*
of state that is available from other state, but is too expensive to

A practical way to solve this is to use an approximation of [2].  In
logic, structure is expressed as predicates.  To use this in
programming, make sure these predicates can be evaluated by reusing
some of the code that computes the caches:

1. Make sure the code that computes the cached/index data is readily
available as subroutines.

2. Add assert checks that verify stored caches against computed data
after major state updates occur.  Make these optional, so they can be
run only during testing/debugging or under specially constructed

[1] entry://20111125-141642
[2] http://en.wikipedia.org/wiki/Hoare_logic