6850437bb9
This patch addresses the following: - Adds a number of addition hypercall that are needed for MicroV - Updates the code to support the changes made to the BSL including better checking of safe integrals and narrow contracts - Adds a lib folder to contain code shared between the kernel and extensions where possible. - Minor initial additions for Rust. Still lots of work to do here
5.6 KiB
Table of Contents
1. Introduction
This document describes some of the reasoning behind certain optimization, or the lack there of.
2. VM, VP and VS Pools
The VM, VP and VS pools used to use a combination of an array and a linked list. THe ID given to each resource is the resource's position in the array. This allows any API to access the resource using it's ID, which is fast and simple. Allocations, however, used a linked list. Basically, each resource stored a "next" pointer which the pools could use to turn the array into a linked list. This provided a means to allocate using O(1). In otherwords, all operations for each resource, including accesses, allocations and deallocations were all O(1) which is fast.
This was changed to remove the linked list portion for a couple of reasons. To start, the next pointer adds memory usage. This memory usage is small, so by itself is not enough to remove the linked list. The main reason for removing the linked list is stability. Even if Bareflank is configured to have access to the max of 32767 resources for a VM, VP and VS, O(N) in this case is not unreasonable. There are other operations that must take place other than just allocations that are O(N). For example, the microkernel must ensure that when a VM is destroyed, it is not active on any PPs, and that no VPs are assigned to it. All of these operations are all O(N), or we would need additional linked lists to reduce the overall time required to perform these checks. Each linked list not only adds additional memory requirements, but most importantly, it adds additional complexity to the microkernel.
For example, suppose in the process of performing a deallocation, a null dereference occurs in the microkernel. If this happens, the microkernel needs to mark the resource as a zombie as it was not properly deallocated. Now lets say the microkernel needs to allocate a new resource. If the zombie resource is the head (which it will eventually become), the microkernel would fail as it would have allocated a zombie resource. This means that in addition to the added complexity of the linked lists, the microkernel needs added logic for handling when it attempts to allocate a resource that is a zombie. It also needs added logic for handling when the linked list is not properly linked. There are many more examples of these types of issues. Each linked list adds a lot of extra logic that must be compiled into the code (which also adds to the size of the microkernel), unit tested, etc.
For these reasons, we simply loop through the arrays when attempting to do allocations. The move from O(1) to O(N) does mean that as N increases, allocations will take longer, but in the grand scheme of things, the reduction in overall complexity is worth it, as there are far fewer edge cases that must be considered, and a lot less state that must be properly handled in the event of unexpected errors.
3. Release and MinSizeRel Modes
The difference between bsl::unlikely and bsl::unlikely_assert (and the bsl::likely and bsl::finally equivalents) is that in Release and MinSizeRel mode, calls to these functions are optimized out, meaning they will not be executed.
There are a number of debugging checks that code must have to ensure mods to the hypervisor do not break certain assumptions that during runtime will never actually occur. For example, when creating a VP, an extension must provide the VMID that the VP will be assigned to. The ABI specification states that the microkernel will ignore the upper bits of the field that do not contribute to a 16bit ID. What this means is that the ID will never overflow, in which case the error flag in the ID's safe integral will never trigger. The code for allocating a VP however cannot assume this and so it must check for an invalid VMID even through at runtime, this check will never trigger.
To overcome this, the bsl::unlikely and friends have assert versions of them that are compiled out in a Release and MinSizeRel mode. This optimization provides a massive reduction in the overall size of the microkernel and extensions that use the BSL as most of the error checks that are in the code are there for developers while they are making changes and not for runtime specific errors. Furthermore, this optimization not only removes the check (including the branch), but is also likely removes a bunch of string information that likely adds more to the overall size of the microkernel and extensions than the code itself.
These assert versions should not be used to validate correctness. Using the same example above, the microkernel needs to verify that the VMID is a valid VMID. Specifically, it needs to be allocated. If we use the assert version of bsl::unlikely, this check will not be included in a Release or MinSizeRel mode. Extensions that are well tested should never trigger this issue in a Release or MinSizeRel build, but the microkernel cannot assume this as this check is part of the ABI and must be enforced at all times. For this reason, use the assert versions of bsl::unlikely and friends only when the check cannot trigger at runtime assuming the microkernel has been properly tested, and never use the assert versions for validating correctness of the ABI, or some other configuration (including hardware) option that could change.
The assert versions should also not be used when passing an error code onto the callee of a function. Instead, the debugging statement should be programmed to use bsl::V or higher, meaning these extra debug statements will be compiled out, but the branch will remain. So in other words, bsl::unlikely_assert and friends would only ever be paired with a bsl::error() and not a bsl::print().