Using Meta-level Compilation to Check FLASH Protocol Code
Andy Chou, Benjamin Chelf, Dawson Engler et al. · 2000
Building systems such a s O S k ernels and embedded software is di cult.An important source of this di culty i s the numerous rules they must obey: interrupts cannot be disabled for \too long," global variables must be protected by l o c ks, user pointers passed to OS code must bechecked for safety before use, etc.A single violation can crash the system, yet typically these invariants are unchecked, existing only on paper or in the implementor's mind.This paper is a case study in how system implementors can use a new programming methodology, metalevel compilation (MC), to easily check s u c h i n variants.It focuses on using MC to check for errors in the code used to manage cache coherence on the FLASH shared memory multiprocessor.The only real practical method known for verifying such code is testing and simulation.We s h o w that simple, system-speci c checkers can dramatically improve this situation by statically pinpointing errors in the program source.These checkers can be written by implementors themselves and, by exploiting the system-speci c information this allows, can detect errors unreachable with other methods.The checkers in this paper found 34 bugs in FLASH code despite the care used in building it and the years of testing it has undergone.Many of these errors fall in the worst category of systems bugs: those that show up sporadically only after days of continuous use.The case study is interesting because it shows that the MC approach n d s serious errors in well-tested, non-toy systems code.Further, the code to nd such bugs is usually 10-100 lines long, written in a few hours, and exactly locates errors that, if discovered during testing, would require several days of investigation by an experienced implementor.The paper present s 8 c heckers we wrote, their applic a t i o n t o v e di erent protocol implementations, and a discussion of the errors that we found.
Cited by 1 works. doi:10.21236/ada419588
Authors
References
- Assigning meanings to programs
- Extended static checking
- A retargetable C compiler : design and implementation
- Automated proofs of object code for a widely used microprocessor
- The Stanford FLASH multiprocessor
- ASTLOG: A Language for Examining Abstract Syntax Trees
- Incorporating application semantics and control into compilation
- Flexible use of memory for replication/migration in cache-coherent DSM multiprocessors
- Experience with a language for writing coherence protocols
- Interface compilation: steps toward compiling program interfaces as languages