Extensibility, Safety and Performance in the SPIN Operating System

How to make OS extensible to the needs of applications

How to deal with the three-way tension between extensibility, safety, and performance

IPC

	Remember the Mach's pager: application specific page-fault manager?
	Problem IPC is expensive Coarse grained extension

Micro-kernel approach

	Not easy to protect Kernel from malicious or faulty extension
	Few abstractions exported by the kernel makes extension difficult

Dynamic binding (like DLL) or Upcall (like scheduler activation)

Not much flexible

SPIN solution - event driven

	Make the kernel work in event-driven
	Then allow applications to register event handers which could be new one or could augment or replace the existing handler
	Make the kernel and extension run in the same virtual address space by dynamic linking No context switch. Fast Extension in the granularity of function calls becomes possible
	Safety? SPIN and extension are written in Modula-3, a strong typed and OO language So no extension can touch private members of SPIN or other extensions!

Modula-3

	Descendant of Mesa
	Object oriented language Separation of interface and implementation Protections: members which are exported at the interface are only accessible
	Strong type checking at compile time and runtime - including array index boundary checking
	Automatic storage management

The ways extension can be used

	Extension monitors system activities and reports to application upon request
	Extension offers hints to system
	Extension may entirely replace or augment an existing system service

Extension Model

	System services are done by the event handling
	Extension = installation of new handler to events
	Dispatcher routes events to appropriate handlers

Event

	An event is just a signature of a procedure
	Event definition = declaration of a procedure and exporting it
	Raising an event = calling the function Dynamically link against the definition of the event, if necessary, and call the procedure Callee(s) are dynamically determined by dispatcher A raising can be resulted in invoking multiple handlers
	Handling the event = executing the procedure linked to the specific call

Handler

	Handler registration is done through: Dispatcher.InstallHandler ( event-name, guard, handler )
	Handling an event = executing the handler procedure with the argument passed by raiser

Guard to extension

	Default handler primary handler the function with the same signature
	Installation of new handler can be denied, allowed, or guarded by the default handler
	Guard can be specified also by the handler
	Guard is a predicate which is associated with the particular handler the predicate is evaluated whenever the event arrives only when the predicate is true, the handler is invoked
	Multiple handlers with their own guards can be installed for an event

Default handler's control on handlers

	Synchronous or asynchronous invoke of handlers
	Handlers may be cancelled after timeout
	Handlers can be invoked in an arbitrary order to enforce, say, their mutual dependency
	Multiple handlers may be invoked to handle, in a cooperative way, a single event For example pipeline of handlers

Example: Syscall

	Built-in interface "TrapHandler" exports "Syscall" event
	Extension "MachEmul" imports "Syscall" event with a guard register "MachEmul.privSysCall" for a handler of "Syscall"
	How is system call handled? Application calls a system call -> trap occurs TrapHander does very basic things: change to kernel mode, save exec context raises "Syscall" event MachEmul.privSysCall gets called

Capabilities

	Unforgeable reference to objects
	Compile time type checking for safe assignment and dereferencing
	OO feature of Modula-3 provides fine-grained protection
	Even though SPIN and extension run in the same address space, they cannot access private members
	Externalized reference: reference passed from the kernel to application Maintains per-application table and passes the index into the table rather than directly passing the pointer

Protection Domains

	Protection domain defines the set of accessible names available to an execution context
	In a conventional OS, a protection domain is implemented using virtual address
	In SPIN, the naming and protection interface is at the level of language
	If an extension modifies a type (= a class interface), a new protection domain should be created and somehow get resolved against modules which use this new definition
	Domain just another object contains one or more safe object files. Safe object file: Modular-3 compiled object, or other type of binaries that SPIN takes it as safe is used to control dynamic linking Operations Create: create a domain with given safe object files. Result is: set of exported events which the creator can call set of imported and yet unresolved events which the creator can resolve by writing her own handler or connecting to exported events of other domain Resolve (src, target): resolve the imported interfaces of target domain against the exported interfaces of src domain Combine (dom1, dom2): create a new domain which is the union of dom1 and dom2
	Procedure Exporting interfaces: create a domain and exports it to the in-kernel name-server Binding: RPC-like binding -- looks like to use the in-kernel name-server (DNS-like service) to coordinate importer to appropriate exporter
	Authentication of importer Exporter may register some authorization procedure to the name-server that will be called with the identity of importer whenever the interface is imported

Interaction between exporter, name-server, and importer is done using procedure calls

Questions:

	Who can raise or handle events?
	Which handler is allowed to handle a particular instance of an event?
	Who is authorized to answer those questions?

Authorizer

	The module which defines and exports the event
	This module implements default (or intrinsic) handler, which enforces the policies concerning those questions

Who can raise an event? = Who can call the procedure? = Protection domain issue

When a module requests that it be dynamically linked against some other module, the module's authorizer is consulted and the linkage is permitted or denied

Who can handle an event or an instance of it? = Who can implement the procedure and overrides or augment the original one? = Protection domain issue, and

Handler registration is consulted to the authorizer of the event and denied, accepted, or guarded

A handler which does not respond promptly can block the event raiser or other handlers

Expensive solution: asynchronous invocation of handler

Cheap solution: timeout mechanism

Three objects are provided so that extension can define its own virtual memory system using those objects

	physical address
	virtual address
	translation

Note pink procedures are events raised by these object, i.e, extensible

Physical address -- physical memory object

	allocate (size, attribute) attribute: color, continuity, etc return: the capability of the allocated physical memory
	deallocate (the capability of the physical memory)
	reclaim (candidate capability) request to reclaim a candidate page extension may handle this event to nominate an alternative candidate

Virtual address

	allocate (size, attribute) return: the capability to the allocated virtual memory I think this is semantically identical to segment creation
	deallocate (the capability of the virtual memory)

Translation

	create () return: new translation context is created and its capability is returned
	destroy (context)
	addMapping (context, capability of virtual, capability of physical, protection)
	removeMapping (context, capability of virtual)
	examineMapping (context, capability of virtual) return: protection
	pageNotPresent (capability of virtual) remember pager of Mach?
	badAddress (capability of virtual)
	protectionFault (capability of virtual)

An extension which implements Unix address semantics

	Interfaces: copy address space & allocate additional memory to an address space
	new address space creation create a context allocate initial physical memories and virtual memories bunch of addMappings
	allocate additional memory to an address space allocate a physical and virtual page addMapping

Previous approaches

	User-level thread: lack of information on kernel status and mismatch occurs
	Scheduler activation: high communication overhead

SPIN provides strand object and user scheduler or thread package can schedule these objects

Actual binding of strands to processors and synchronization of strands are done by kernel for safety reason. Reasonable! Then user scheduler or thread package gives hints to the kernel. Right?

Strand object

	Block & unblock For a moment I am running this strand Not I want to run this strand
	checkpoint & resume - upcalls in scheduler activation The processor is being taken from the strand. So please checkpoint it Now you can schedule the strand

Great idea! Safety is, however, questionalble