Software blog

Efficient Software-Based Fault Isolation

Myoungsoo Jung

Problems, Solutions and Summaries:

The key idea to isolate fault by software is very simple, and allows us to archive the efficient way to make fault isolation cheap enough. Begin with this paper, Robert Wahbe at al. figure out the problem of the traditional fault isolation method. When we use such scheme (i.e., hardware-based fault isolation), high performance cost is necessary because preventing the code in one address space from corrupting the contents of another induces prohibitive context switch overhead and needs some additional operation such as trapping, copying arguments, saving and loading relative register, and flush look-aside buffer. To overcome this challenge, the authors provide a software approach, which implemented within a single address space. It grants a separated fault domain to load code and data for a distrusted module and modify object code to prevent faults from writing and jumping to address outside such fault domain.

To archive mentioned goal of this paper, the authors propose the software encapsulation transforming distrusted module not to escape its fault domain – fault domain consists of two segments, one for distrusted module's code, and another for its static data, heap and stack. The software encapsulation contains of two kinds of key mechanism to pinpoint the actual location of fault within a module and isolate distrust module. One is called, segment matching preventing the use of illegal addresses. In segment matching, insert checking code before every unsafe instruction that jumps to or store to statically unverified address within the correct segment. If the check fails, such code traps to a system error routine outside the distributed modules' fault domain.

Another key mechanism of software encapsulation is address sandboxing. Sanding boxing indicate inserted code that sets the upper bits of the target address to the correct segment identifier before distrusted instructions. As with segment matching, earlier mentioned, unsafe store or jump instruction can be modified to use dedicate register, and it guarantee that distrusted module code cannot produce an illegal address. There are two instruction for providing sandboxing, one to clear segment-id and store the result in a dedicate register, the other to set segment id for the correct value.

Remaining issues for supporting efficient software encapsulation are optimization, how to prevent corrupting process resources and to access among domains when they need data sharing. In the view of optimization, the authors provide the way to reduce overhead, which is induced from computing target address. Basically, instruction of RISC has register address and offset. However, sandboxing mechanism just use only register addresses or numbers and handles offset by creating guard zone, which indicate unmapped area. In process resources problem, the authors require distrusted modules for accessing resource through cross-fault-domain RPC. For instance, if a distrusted module's object code performs a direct system call, the authors transform this call into the appropriate RPC call. In last, I talk about data sharing. Because segment encapsulation doesn't alter load instruction, fault domains can read any memory mapped in the application's address space. However, each domain cannot share data among them. So the authors provide lazy pointer swizzling that alias the shared regions into multiple locations in the virtual address space by modifying the hardware page table.

Critiques:

Although this paper strives for reducing the cost of fault isolation by using not hardware but software, I afraid some kinds of possibility that its mechanism can break pipeline. Traditionally, many scientists who involved in computer architecture realm take effort to reduce the number of broken pipeline because it induces the terrible performance degradation. As software encapsulation, we should insert code for support segment matching and sandboxing, which incur to break pipeline. So the authors should provide clearer evidence that proposed approach cannot hurt breaking pipeline. Secondly, I don't find realistic solution for adding "correct" value which used for implementing segment matching. If the actual location where occupied with loadable distrusted modules is fixed then we can easily find segment-id during a compile time, but if not, segment-id is unable to be recognized when compile time. For this reason, the authors also should refine the correct value and provide the way to find segment-id without any operating system's load modules mechanism during a compile time.

Unmodified Device Driver Reuse and Improved System Dependability via Virtual Machines

Myoungsoo Jung

Problems, Solutions and Summaries:

This paper proposes the way to reuse unmodified device driver. At the same time, Joshua Le Vasseur et al. point out how to improve system dependability by using virtual machine. Actually full reuse for a driver base has been considered unachievable. It's because if we want to introduce device driver into new Operating System, then elusive problems occur such as unavailable code, undocumented feature, and extent of programming errors. The authors suggest pragmatic approach for it and strong isolation of legacy device drivers by guaranteeing that semantics a preserved and incompatibilities are limited using virtual machine multiplexing. Also this scheme allows system suffer from minimal resource overhead by collaborating VMs.

Traditionally, for experience driver reuse, the author divides approaches into two parts. First one is a co-hosting method that indicates binary driver reuse. Another one is transplanting driver that enables to enjoy independence. However the previous approach can interfere between VM and driver OS because they run with all privileges. Also, the last method has problem to successfully reuse device driver because they has to use glue code, and it raise conflicts. When system tries to reuse device driver, the authors propose three considerations such as semantic resource conflicts that represent accidental denial of service, sharing conflicts that are induced since fair address space sharing may be unachievable. Finally, in the view of an engineering effort, donor OS knowledge significantly required writing glue and it is even difficult.

In this paper, drivers are closely knit to kernel, applications are not. In addition to that, orthogonal drivers should be based on following principles: 1. Resource delegation by receiving only bulk resources. 2. Separation of name spaces that indicate each driver has its own address space. 3. Separation of privilege by executing driver in unprivileged mode. In last the author claims secure isolation and common API as basic principle to satisfy orthogonal device driver requirements. In architectural view, to reuse and isolate each device driver, system executes it and its native OS within VM called by DD/OS. This approach is same effect that each deriver can be executed in separate VMs and it allows systems exploit simultaneous use of driver from incompatible OS-s. To communicate each deriver located in separated VMs, translation module support abstractions and control them by adding to DD/OS to interface with client.

The authors also claim that low overhead communication by using message notification and request completion. In addition to it, to bolster their reuse approach, they insist low overhead memory sharing registering memory areas of a VM into another VM's physical memory space. Besides those claims, the authors consider virtualization issues such as DMA operation, additional requirements regarding resources, and special timing. In DMA operation case, there are problem that DD/OS can perform DMA to physical memory not allowed by memory protection system. For this reason, it uses DMA to replace hypervisor code and data. I will discuss regarding these considerations in next critique section to argue for details. This research contributes unmodified reuse, a strong isolation, and fault containment to existing device driver.

Critiques:

In DMA and trust section of this paper, I wonder if where actual memory locations that cannot be reclaimed are when this approach uses DMA operation. I think that the author have to solve this ambiguity. In addition to it, the author claims that client must not use pinned memory because of DD/OS until faulted it complete rebooting process. However, I am not confident this mechanism is right. For example if DMA completes before the faulted VM restart then system fall down to ambiguous status, and I wonder if VM fail to reboot their system then what can be incur. If systems need a bunch of drivers to provide one functionality like PCI device then I have question to decide whether the proposed approach still use distributed device drivers to deal with one functionality or not. With this reason, to bolster their claims, the author should provide tradeoff between performance and isolation advantage. More crucial problem is resource consumption. The authors solve this problem by using swapping memory method. To evict it, It considers which one is cold page or not. However, most device drivers are managed as block box. So, the author should suggest the way to recognize cold and hot page even if each device driver is encapsulated, and hide their own information.

Scheduling I/O in Virtual Machine Monitors

Myoungsoo Jung

Problems, Solutions and Summaries:

Deigo Ongaro et al. evaluate that the impact of VMM scheduler on performance using multiple guest domains concurrently running different types of applications. To concrete it, the authors add numerous schedulers to Xen. Such evaluation reveals the relationship between domain scheduling and I/O performance in a Virtual Machine Monitor(VMM), and provide the major problems in VMM's I/O scheduling. In other words, this study of Deigo Ongaro et al. is contributed by identifying I/O performance degradation, overcoming unfairness in I/O sensitive domains, and removing side effects from scheduler tickling from the Xen scheduler.

The authors figure out that traditional way to fairly scheduling results in poor and unpredictable I/O performance when applications intending to latency and bandwidth sensitive are performed by VMM schedulers. Basically, the Xen exploit default scheduler as the Credit scheduler which uses a credit/debit system to fairly share process' resources. To bolster the facts those I/O degradations, the authors show experimental results that its scheduler achieve mixed performance depending on the particular configurations with bandwidth-intensive and latency sensitive applications. In addition to it, the author also evaluate impact of Simple Earliest Deadline First(SEDF) scheduler. Its scheduler's performance is similar with Credit scheduler even if it can fairly share process' resources when plays with CPU-sensitive applications.

Turn to problems of Xen's scheduling. First of all, latency is induced by scheduling other domains. It's because event is used to communicate virtual interrupt as well as inter-domain. Especially, in the network interface card(NIC) case, there are at least two chances to run other domains to deliver a network packet, and it results in latency. More serious problem is unfairness in I/O performance. In other words, the scheduler is fairly sharing the process resources only by approximations. Modern trend is exploiting completely fair scheduler. For this reason, if low response latency is desired then such scheduler policy may not be effective. Also Credit scheduler doesn't provide fair latency because it doesn't consider when each domain should receive its allocated fraction of processor resources. Finally, the scheduler's problem occurs if it tickles too frequently. It results in preempting domain in execution is too early.

To minimize above problems, this paper provides scheduling optimizations such as boosting idle domains, re-ordering the run queue according to credits, and adjusting to tickle the scheduler by understanding I/O domain requirements. Such requirements largely divide into three parts. First one is low latency, and lasts are high bandwidth and independent of other domains' workloads respectively. By introducing boosts I/O domain into VM scheduling, latency sensitive applications have chance to try to perform their I/O more. In other view, reordering the run-queue by reinserting I/O domains into near the heard of run-queue can resolve unfairness when Xen has the heavy workload scenario. In addition to that, the authors try to minimize preemption. Actual meaning of it is that tickling is disabled altogether for avoiding to preempt the driver domain, In last, fixing event channel notifications by exploiting 2-level hierarchy of bit vectors can guarantees that no port will be processed a second time before all other pending ports have been processed once.

Critiques:

As all known, Xen has suffered from low I/O performance. I believe that these approaches are very helpful to have different views when designers of the Xen's architecture see the scheduling. However, I think it is better that the authors should provide more classifications to exploiting boost status. Since the boost method also has possible that effective is negated when they have many I/O domains. What we can we expect from when run-queue same number of UNDER domain with number of boost domain. Moreover, I believe that it is insufficient for I/O domain under heavy loads. In reordering the run-queue case, how can we compensate the low utilization of CPU when exploiting combinations of boost with ordered run-queue? If the author provide these considerations, then optimization approach regarding scheduler is more useful to enhance I/O performance of the Xen.

On micro-kernel Construction

Myoungsoo "Mozer" Jung

Problem, solution and summary:

The author, Jochen Liedtke, asserts that u-kernel's insufficient and inflexibility comes from improper implementation and from overloading the kernel. To support the author's supposition, he figured the some facts effecting to insufficient and inflexibility. These facts divided into three parts such as u-kernel approach, concepts, and implantation of it. With these reason, this paper defines fundamental and essential concept of u-kernel. Consequently, the author provides several analyses to clarify that performance problem of u-kernel sole depends on implementation not on OS concepts.

  To begin with, the author showed two kinds of design concepts. First one is independency. Typically independency in OS means that an arbitrary subsystem cannot be disturbed or corrupted by any other subsystem. Second, the author point out integrity that u-kernel should provide the way securely for establishing communication channel among subsystems, which want to build it. After that, this paper defined primitives divided into three part: 1. Address space; 2. Threads and IPC; 3. Unique Identifiers. Further, he provides consideration for flexibility of u-kernel.

  As we all know, For providing address spaces to application, mapping information and data structure dealing with it should be non accessible to unauthorized subsystem or application. It is very fundamental operation of OS. To meet address space requirements, this paper propose grant, map and flush operation. Grant indicates that the owner of an address space can grant any of its pages to another space. So, the page is removed from its address space after granting. Map operation is very similar with above it, except for the fact of which the page is remained after mapping. This small operation is enough to implement existing memory and address space management issues. Further this basic operation about memory can leave memory management outside u-kernel. Moreover, some quantitative data that analyzed performance of memory manager in terms of three operations (plant, map, and flush) verified that it did quite well.

  About threads and IPC, the author figured out three operations, it should provide by kernel. So, it will be defined to primitive. First, including dynamic or static association to address space, thread concept should be decisive by kernel. Second, to prevent corruption of address space, all change to thread's address space must be controlled by kernel. RPC can be implemented based on IPC, whereas IPC should be proposed by kernel because grand and map operation need IPC. Finally, u-kernel also should provide the way to indentify each task or subsystem. It is covered by providing Unique Identifiers.

  In sum, this paper proposed that u-kernel can be flexible without degradation efficiencies by providing higher level layer with a minimal set of appropriate abstraction. Most inflexible and inefficient factor come from insufficient understanding of the combined H/W and S/W or inefficient implementation. So, this paper also showed the factor of which many application be implemented on the u-kernel concept easily.

Critique:

I am very impressive to several approaches that reconstruct microkernel requirements. It will be better to provide compensations abut some analyses like memory effect because it suggested merely IPC optimization without pondering other source of system overheads. With this reason, the author should consider more lots of thing about impact between resources than proposed on this paper. In addition to that, it is better that the author considers memory size cost when they evaluate thread switch overhead not only consider clock cycles.

  Also, the author point out that many applications is implemented on the microkernel concept such as memory manager, pager, device driver, and remote communication by using primitives of u-kernel. Although u-kernel provide several easy way to implement the microkernel concept, I think that implementing OS is quite complex to application designer and developer. Actually, in fields, application also has too many consideration and design principle to implement microkernel concept. So it is entirely possible that the performance will be degraded by poor application even if u-kernel concept provides remarkable flexibility.

Exokernel : An Operating System Architecture for Application-Level Resource Management

Myoungsoo"Mozer" Jung

In this paper, authors provided new operating system architecture that exports all hardware resource to application through low lever interface. According to authors' claim, such method that separated resource protection from management allowed application-specific customization. It as well helped to enhance performance of traditional operating system. To bolster authors' claim, this paper point out the fixing interface and implementation result in limitation of performance.

The key idea for this paper is maximizing application freedom by exporting hardware. It gave several advantages to OS architecture: Firstly, tightly coupled to application – it mean application resource management -- allowed simple specialized implementation. Secondly, exporting resource would allow the fast system evolution. It's because library operating systems, which manage resource instead of kernel, can be developed in isolation. So, anyone can develop and modify some portion of OS. To support it, implemented OS (i.e,. exokernel) by M.I.T laboratory exposed many things of operating system. I divide considerations for exposing into four parts. First, to avoid resource management, exokernel exposed the hardware -- it will be discussed in next paragraph more. Second, Exposing allocations allowed applications (or library OS) request physical resources to enhance their performance. Also, exokernel exposed name and revocation for resources. A former means exposing physical name of hardware to application, so application could use it follow own private policy. It was helpful to improve their operation performance too. A latter will be mentioned in next paragraph to handle more detail information.

The exokernel employ three techniques to export resource securely -- actually securely exporting resource is important to prevent system chaos. First, application can securely bind to machine resource and handle events by using secure binding. Second, visible resource revocation allowed applications participate in a resource revocation protocol. Typically, traditional OS adopted a policy that only allowed invisibly revocation. So, the impossible management for resource of application is the cause of performance degradation. Finally, by using an abort protocol, exokernel could break secure binding of uncooperative application by force. It meant that certain application fail to take resource from library of exokernel then it can revoke resources by force. To record the forced loss of a resource when exorkernel revoke it, this paper used a repossession vector which used to update mapping information about revoked resource.

In conclusion, the author point out problems of typical operating system. It was that operating system abstraction might degrade application performance. To prevent it, this paper provided several exporting method without abstraction. Experiments show that simplicity and limited number of OS primitive allowed it to be implemented very efficiently. Also, experiments showed that exokernel's performance of exception dispatch and control transfer routine is better than typical OS. I agree with which exokernel is a viable architecture for high performance. However, this paper unfairly relied on the assumption of which developers who responsible for implementing the application (or some parts of library OS) is skilled and disciplined well to enhance their OS environments. I think that it will be entirely possible that someone who not familiar with fundaments can hurt the performance of exokernel.

System Architecture Directions for Networked Sensors

Myoungsoo "Mozer" Jung

The key idea of this paper - "System Architecture Directions for Networked Sensor" is that to develop the efficient and appropriate network system, which reside in embedded system, designer consider the new architecture. The main reason for this is that current general- purpose system couldn't handle embedded resources and fit in the small system well. Basing upon reason, this paper suggest that authors developed and designed a tiny event driven operating system by identifying key requirements of networked sensors.

To bolster authors' claim, they point out several networked sensor characteristics as follows: First, small physical size and low power consumption. Most hardware in network system' size is reduced, and its power consumption requirement is lower than past. That's why software architecture reflects the fact of which it should make efficient use of resources while enabling low power consumptions. Second, concurrency-intensive operation will be considered because major operation what networked sensor system's device should do is to follow information from place to place. Moreover, its follow has some constraint such as lower density of memory and a large number of communications between low and high level processing. Finally, this system should consider two factors of software design. One is the diversity in design and usage, another is robust operations.

The mentioned operating system, which indicates TinyOS in this paper, was designed under the two major rules – concurrency intensive, efficient modularity. It was as well designed by preceding characteristics of networked sensor. So, eventual integration of sensor, and processing and communication should be considered during design time: TinyOS implemented with an event model so that high level concurrency can be handled. Actually, they implemented TinyOS by composing a tiny scheduler and components that interrelated with command handlers, an encapsulated fixed-size frame, and set of tasks.

In the evaluation, this paper analyze TyniOS by numerous factors such as small physical size, concurrency-intensive operations (it mentioned by second paragraph), efficient modularity, limited physical parallelism and controller hierarchy, and diversity in usage and robust operations. In brevity, TyniOS fits in small size memory system well, and propagates events by using just 6 byte memory. In other words, those events can propagate through the exploited components quickly.

To support the proposed system architecture for networked sensor, authors finally provided several quantitative analyses by evaluation about the developed TinyOS. These analyses are clear evidence as follows: First, event based communication model is efficient in the networked sensors system. Turn to the next, analysis betray the impact of architectural changes in micro controllers. In this paper, the fact of which the additional register set save us about more reduced time and CPU load.

In conclusion, authors proposed issues about the appropriate software architecture for networked sensors and embedded system under higher constraints. To bolster their claim, they provide analysis about the key requirements of its system by implementing TyniOS. I believe that the analysis is very helpful groundwork for embedded system architecture even if it handled old fashion of operating system issue.