Programming the Garcia Robot
People: Richard West, Aaron Hughes, Gerald FryFor more info see: http://cs-people.bu.edu/gfry/garcia
(
http://www.acroname.com/garcia/garcia.html
)
Effort is now underway on a project to enhance extensibility and protection in embedded real-time system software using COTS components. This project involves porting the User-level Sandboxing mechanism mentioned below to the Stargate XScale platform running Linux 2.6.11. Goals of this project include predictable and safe execution of real-time tasks associated with robotic sensors and actuators found on the Garcia robot manufactured by Acroname, Inc. Additionally, we seek to prove that widely available general purpose systems such as Linux can be extended to support real-time service in embedded platforms and that the programming interface for real-time task developers can be cleanly integrated with existing system services and API's.
Effort is now underway on a project to enhance extensibility and protection in embedded real-time system software using COTS components. This project involves porting the User-level Sandboxing mechanism mentioned below to the Stargate XScale platform running Linux 2.6.11. Goals of this project include predictable and safe execution of real-time tasks associated with robotic sensors and actuators found on the Garcia robot manufactured by Acroname, Inc. Additionally, we seek to prove that widely available general purpose systems such as Linux can be extended to support real-time service in embedded platforms and that the programming interface for real-time task developers can be cleanly integrated with existing system services and API's.
Real-time Asynchronous I/O Mechanism for Linux
People: Richard West, Gerald Fry
Most modern operating systems support at least one form of asynchronous
I/O. Examples of such interfaces include the POSIX AIO standard, the select
and poll system calls, and response to events on file descriptors by
registered signal handlers (ie, SIGIO). However, in order to provide
predictable event handling capabilities for real-time applications, the
implementation of such interfaces must ensure that I/O event dispatch
latency is as low as possible.
Most implementations of the above mentioned I/O interfaces delegate event dispatching to the kernel thread dispatcher. That is, a process event handling function may not execute immediately upon occurrence of an event, but the event processing is delayed until the associated process thread is next scheduled. This is the case in many signal implementations, such as in Linux.
This project focuses on dispatching of I/O event handlers from within softirq context in Linux. A User-level Sandboxing technique (see below) is leveraged to perform dispatching of real-time event processing functions in a safe and predictable fashion. This contrasts with other approaches to extending the Linux kernel to support real-time tasks such as RTAI and RTLinux, which require real-time tasks to be executed within top-half interrupt context and do not provide the same level of isolation between real-time code and best-effort processes.
Most implementations of the above mentioned I/O interfaces delegate event dispatching to the kernel thread dispatcher. That is, a process event handling function may not execute immediately upon occurrence of an event, but the event processing is delayed until the associated process thread is next scheduled. This is the case in many signal implementations, such as in Linux.
This project focuses on dispatching of I/O event handlers from within softirq context in Linux. A User-level Sandboxing technique (see below) is leveraged to perform dispatching of real-time event processing functions in a safe and predictable fashion. This contrasts with other approaches to extending the Linux kernel to support real-time tasks such as RTAI and RTLinux, which require real-time tasks to be executed within top-half interrupt context and do not provide the same level of isolation between real-time code and best-effort processes.
User-level Sandboxing
People: Richard West, Jason Gloudon, Xin Qi, Gabriel Parmer, Luis Hernandez, Gerald FryFor more info see: http://www.cs.bu.edu/fac/richwest/sandboxing.html .
Extensibility and protection are important characteristics of modern operating systems. For example, microkernel structured systems theoretically provide the maximal degree of extensibility while supporting memory isolation between extension modules in separate protection domains. However, the performance of such systems is dependent upon the hardware protection mechanisms available to kernel developers, and thus each microkernel must be designed around the particular protection features available in the target hardware platform.
Such inherent non-portability of microkernel structured operating systems has contributed to the architecture's limited success in practical situations. Notwithstanding, there are advantages in supporting dynamic extension of system services while ensuring overall OS integrity, but it is crucial that these mechanisms assume only the most widely available hardware protection features, such as page-based virtual memory and simple address translation caching using a non-tagged TLB.
The User-level Sandboxing architecture maps a 4MB physical superpage into the virtual address space of every process in the system. The permissions bits of this page are initially set such that access to the associated memory range is permitted only when the processor executes in kernel mode. An additional 4MB page frame is similarly maintained for storing data associated with extension modules (ie, an execution stack). During the initialization of a sandbox thread (system or application-level extension module), memory is allocated for executable code and an execution stack from these two superpages, collectively referred to as the "sandbox memory region."
The extension thread is dispatched by the kernel via an upcall into user-space to an entry point specified by an upcall_client descriptor, which associates the extension with a process domain and points to executable code within the sandbox memory region. A major advantage to the dispatching approach, when compared with other mechanisms such as POSIX-style signals, is the direct transfer of control to user-level extension code without incurring non-deterministic scheduling latency (partly due to multiple flushes of the enitre TLB contents). Before a sandbox thread may begin execution, the superpage permissions must be reset to allow read/write access to user-level code.
Once a sandbox thread completes execution, the superpage permissions are reset to only allow kernel-mode access and only the sandbox superpage TLB entries are flushed (if necessary) to protect extension code and data from subsequently scheduled processes. Requiring sandbox threads to be implemented in a type-safe language provides additional protection of process address spaces and extension memory from code executing in the sandbox region.
In response to the need for efficient and safe extensions in commercial off-the-shelf (COTS) systems, the User-level Sandboxing project seeks to provide mechanisms for dispatch/execution of system or application-level extension modules in user-space. The current implementation includes a patch for the Linux 2.6.15 kernel as well as a loadable kernel module. Developers may program extensions in C and link extension code with a lightweight libc library such as dietlibc if use of standard C library functions is required. Invocation of system calls is also supported from within extension code.
The User-level Sandboxing architecture maps a 4MB physical superpage into the virtual address space of every process in the system. The permissions bits of this page are initially set such that access to the associated memory range is permitted only when the processor executes in kernel mode. An additional 4MB page frame is similarly maintained for storing data associated with extension modules (ie, an execution stack). During the initialization of a sandbox thread (system or application-level extension module), memory is allocated for executable code and an execution stack from these two superpages, collectively referred to as the "sandbox memory region."
The extension thread is dispatched by the kernel via an upcall into user-space to an entry point specified by an upcall_client descriptor, which associates the extension with a process domain and points to executable code within the sandbox memory region. A major advantage to the dispatching approach, when compared with other mechanisms such as POSIX-style signals, is the direct transfer of control to user-level extension code without incurring non-deterministic scheduling latency (partly due to multiple flushes of the enitre TLB contents). Before a sandbox thread may begin execution, the superpage permissions must be reset to allow read/write access to user-level code.
Once a sandbox thread completes execution, the superpage permissions are reset to only allow kernel-mode access and only the sandbox superpage TLB entries are flushed (if necessary) to protect extension code and data from subsequently scheduled processes. Requiring sandbox threads to be implemented in a type-safe language provides additional protection of process address spaces and extension memory from code executing in the sandbox region.
In response to the need for efficient and safe extensions in commercial off-the-shelf (COTS) systems, the User-level Sandboxing project seeks to provide mechanisms for dispatch/execution of system or application-level extension modules in user-space. The current implementation includes a patch for the Linux 2.6.15 kernel as well as a loadable kernel module. Developers may program extensions in C and link extension code with a lightweight libc library such as dietlibc if use of standard C library functions is required. Invocation of system calls is also supported from within extension code.
knSPACE: Scalable Distributed System
People: Richard West, Gerald Fry
A distributed system designed to scale to many millions of hosts communicating over a geographically dispersed inter-network (ie, the Internet), the knSPACE system enables application-level message routing across a logical overlay network in O(lg n) hops, while only requiring each participating node to store O(lg n) routing table entries (where n is the number of nodes in the system). The overlay topology is modeled on a k-ary n-cube graph, that is, a graph theoretic structure that is proven to have desirable properties such as logarithmic (wrt. number of nodes) diameter and highly redundant connectivity. The knSPACE system is capable of completely decentralized self-organization using periodic stabilization and node discovery protocols.