BREADSYSTEM 1.0.0 ARCHITECTURE
(Rough Draft)
BreadSystem is a general-purpose operating system designed by Jack Eisenmann. This document describes the design elements of BreadSystem.
DESIGN GOALS
Efficiency may be sacrificed within reason to reach these goals.
GENERAL FEATURES
FILE SYSTEM
Non-volatile storage is organized by volume at the highest level. A volume represents a storage device such as flash memory or a disk drive. Each volume contains a tree of files and directories. Entities stored inside a volume, such as files and directories, are called "volume items".
The system chooses one volume to be the primary volume. The primary volume holds critical information for the system, including boot applications and user directories.
The primary volume has the following directory structure:
The system directory contains standard interfaces and applications which are available to all users. Please see this page for a list of system interfaces:
The bootApps directory contains applications which will be automatically launched after the system boots.
The users directory contains one user directory for each user in the system. Each user has full permissions to their corresponding user directory.
A path is a string describing the location of a volume item. A relative path is written in relation to a working directory, while an absolute path is written in relation to the top level of a volume.
Relative path = "(relative path)/(item name)" or "(item name)"
Absolute path = "(volume name?):(relative path?)"
An absolute path with a missing volume name will use the primary volume.
A period as an item name in a relative path refers to the previous volume item in the path. For example, the path :myDir/. describes the same location as :myDir. Two periods as an item name in a relative path refer to the parent directory of the previous volume item in the path. For example, the path :myDir1/myDir2/.. describes the same location as :myDir1.
Every file has one of the following types:
A generic file does not hold special significance in the system. A generic file can store any sort of data.
A bytecode application file contains BreadBytecode instructions for user applications. Please see this page for details about BreadBytecode:
A system application file is used to access hardware features of the machine. A system application file does not contain any bytecode or machine code. Instead, the file contains an enumeration value which is consumed by the operating system. This enumeration value indicates which hardware feature to use. Enumeration values are specific to each system implementation, and are generally incompatible across machines.
An interface file describes the functions offered by applications which conform to an interface. Both bytecode applications and system applications may conform to interfaces.
Every directory has one of the following types:
A generic directory does not hold special significance in the system. A generic directory can store any sorts of files and directories.
A bundle directory organizes available versions of a single application or interface. Each version number contains major, minor, and patch integer components:
Every application bundle has the following directory structure:
A bundle contains one ver_(major)_(minor)_(patch) directory for each installed version of the application. For example, version 2.15.3 of an application file would have a corresponding directory named ver_2_15_3.
Interface bundles have a similar directory structure:
A soft link is a volume item which refers to a file or directory in another location. When an application uses a path to a soft link, the system will access the referenced file or directory instead.
APPLICATION SYSTEM
The user may launch an application file or bundle by providing a path to the application. In the case of an application bundle, the system will try to launch the latest application version possible.
An application may conform to an interface so that other applications may discover and access particular functions. If an application conforms to an interface, the application must implement all functions specified in the interface.
If an application implements an interface function, the function is considered to be "public", and may be invoked by any application. The permission system may restrict access to particular public functions. If an application implements a function which is not part of an interface, the function is considered to be "private", and cannot be invoked by any other application.
An interface file provides the following information for each function in an interface:
Each application specifies a list of required and recommended dependencies. When launching an application, the system will resolve a path for each dependency. If a required dependency is missing, the system will throw an informative error.
Each file and directory may be associated with a list of search paths. The system uses these search paths to find interfaces and applications specified by relative paths.
Suppose an application is trying to launch a dependency which has a relative path. The system will perform the following steps:
A running application is called an "agent", which is similar to a process under other operating systems. An agent may contain several threads running in parallel, each using its own memory stack.
Every application uses the same unified heap for dynamic memory allocation. The system transparently manages garbage collection in the heap.
Heap allocation read and write operations are controlled by the permission system. If an agent tries to read or write a heap allocation without appropriate permission, the system will throw an error.
Public functions may be configured to automatically grant permissions for input and output heap allocations. Automatic permission assignment is established in both bytecode application files and interface files.
Bytecode applications cannot create and manipulate memory pointers in an arbitrary fashion. Every pointer is created by allocating in the heap, and always points to the same heap allocation. The only exception is the null pointer, which represents a missing heap allocation. Pointers are stored in special "alpha" memory regions to ensure that they cannot be corrupted. These restrictions prevent agents from accessing memory in undesirable ways.
PERMISSION SYSTEM
The permission system protects the access of particular instructions and public agent functions. If an agent tries to invoke an instruction or function without holding sufficient permission, the system will throw an error.
A "vessel" is an entity which can hold permissions. All agents, files, and directories are vessels. If an agent dies, the permissions it holds will be deleted. If a volume item is deleted, the permissions it holds will also be deleted.
Each operation which requires permission to perform is represented as a "protab" (a portmanteau of "protected ability"). The data in a protab identifies certain aspects of the associated operation, such as the function, instruction, or arguments. Every permission held by a vessel is associated with exactly one protab.
Protabs for bytecode operations may be acquired from corresponding bytecode instructions. For example, the protab to perform the launch instruction may be acquired from the launchProtab instruction.
An "arbiter" application manages the protabs and permissions of a particular set of operations. An arbiter determines the structure of data in each protab, and provides public functions to generate protabs for other applications.
Protab data may contain an alpha region with one or more pointers. Pointers stored in permission protabs are considered to be "weak" references. If a heap allocation is garbage collected, any permission referencing the allocation will be deleted. Furthermore, if a permission protab contains an alpha region, the permission will not be persisted to non-volatile storage. This is because heap allocations do not remain after system shutdown.
Arbiters are also responsible for validating permission to access particular public functions. Each public function may have a designated arbiter which restricts access. The arbiter defines corresponding "guard" functions to validate permission. Before a public function runs, its guard function is automatically invoked to check permission. The guard function will throw an informative error if the caller does not have permission to invoke the public function. Otherwise, the public function will run without an error.
An agent may give permission for a protab if either of the following conditions are true:
Every permission is associated with a maximum propagation count. When an agent gives a permission, it must decrease the maximum propagation count of the received permission by at least one. An agent cannot give a permission if the maximum propagation count of the permission is zero.
An arbiter may create a permission with infinite maximum propagation count. Such a permission may be transferred between agents an unlimited number of times.
A vessel may hold a permission explicitly or implicitly. An explicit permission is a permission which has been granted through the givePerm instruction. An implicit permission is a permission which has been established using the arbiter interface of the arbiter application. The arbiter is responsible for deciding the circumstances under which a vessel holds implicit permission.
Each permission is associated with a list of preceding permissions. A preceding permission serves as justification for the existence of another permission.
In the case of explicit permission, preceding permission is determined by the identity of the vessel which gave the permission. Suppose that agent A1 gives permission A2 to agent A3, and agent A3 receives this permission as permission A4. Permission A2 is the preceding permission of permission A4.
In the case of implicit permission, preceding permission is determined by the arbiter application. The arbiter may decide to include any number of preceding permissions, including zero.
Ability to remove permission depends on preceding permissions. An agent may remove a permission if it holds preceding permission with any number of steps removed. Suppose that permission B1 is a preceding permission of permission B2, and permission B2 is a preceding permission of permission B3. An agent may remove permission B3 if the agent holds either permission B3, permission B2, or permission B1.
An implicit permission cannot be removed in any meaningful way. This is because it will always be regenerated by its arbiter application.
If a preceding permission is removed, it will be replaced by its own preceding permission. Suppose that permission C1 is a preceding permission of permission C2, and permission C2 is a preceding permission of permission C3. If permission C2 is removed from its vessel, the preceding permission of permission C3 becomes permission C1.
The "admin permission" is the highest level of permission in the system. If a vessel holds admin permission, the vessel has implicit permission to all other permissions. As a result, an agent with admin permission can give any permission in the system. An agent holding admin permission can also remove any permission from any vessel regardless of preceding permission. Admin permission should be reserved for system administrators or highly trusted applications.
In general, permission to perform an operation on a directory denotes ability to perform the same operation on the directory's contents. For example, if an agent holds vItemWrtProtab permission for a directory, the agent implicitly holds vItemWrtProtab permission for all items inside the directory.
In an analagous fashion, permission to configure an application file denotes ability to configure agents launched from the application file. For example, if a vessel holds permission for lifeControlProtab on an application file, the vessel implicitly holds permission for lifeControlProtab on any agents launched from the application file.
Permission to permControlProtab allows an agent to give and remove the permissions of another vessel. If vessel D1 holds permControlProtab permission on vessel D2, then vessel D1 implicitly holds all permissions held by vessel D2.
permControlProtab permission is transitive across vessels. If vessel E1 holds permControlProtab permission on vessel E2, and E2 holds permControlProtab permission on vessel E3, then E1 implicitly holds permControlProtab permission on vessel E3.
RESOURCE SYSTEM
The resource system distributes hardware resources to vessels. Such hardware resources include RAM (memory usage), core time (CPU usage), and non-volatile storage (volume usage).
Resource system values are quantified in the following ways:
Two vessels may be configured so that one is a "life parent" of the other. A vessel may only use as much memory and CPU load as allowed by its life parents. If vessel A1 is a life parent of vessel A2, then vessel A1 can set the maximum memory and core quotas of vessel A2.
Establishing life parent/child relationships requires permission to lifeControlProtab. If agent B1 wants to assign vessel B2 as a life child to vessel B3, agent B1 must hold permission to lifeControlProtab on vessel B3, and vessel B3 must hold permission to lifeControlProtab on vessel B2.
lifeControlProtab permission is transitive across vessels. If vessel C1 holds lifeControlProtab permission on vessel C2, and C2 holds lifeControlProtab permission on vessel C3, then C1 implicitly holds lifeControlProtab permission on vessel C3.
A heap allocation counts toward the memory usage of an agent if both of the following conditions are true:
If the memory usage of a life child exceeds the amount allowed by the parent, the system will attempt the actions listed below. The actions are listed in order from most favorable to least favorable:
If the CPU utilization of a life child exceeds the amount allowed by the parent, the system will slow down the child. In this case the system will not kill the child, but the child may be suspended temporarily.
A life parent may assign a memory priority to each of its children. The system will try to throttle and kill life children with the lowest memory priority first.
In an analagous fashion, a life parent may assign a core priority to each of its children. The system will try to slow down children with the lowest core priority first.
The resource usage of a life child also counts toward the resource usage of its parent. If a vessel has multiple life parents, the child's resource usage counts toward the combined quota of all its parents.
An application may be configured so that the launcher automatically becomes a life parent of the launched agent. This mechanism is useful when the application creator does not wish to be a life parent of its application.
To preserve system resources, an agent may mark itself as collectable. The system may kill a collectable agent to free resources. A dependent agent may mark a collectable agent as a reference. The system will not kill any direct or indirect references of a non-collectable agent.
Each volume item has a maximum volume quota. The total storage size of a file cannot exceed the volume quota of the file. In a similar fashion, the total storage size of all items in a directory cannot exceed the volume quota of the directory.
The system performs the following actions to maintain the volume quota invariant:
If an agent has write permission for a directory, the agent may set the volume quota of any item in the directory. Note that write permission for a volume item alone is insufficient to modify the volume quota of the volume item itself.
MIRROR SYSTEM
A "vessel mirror" is a mechanism which causes one vessel to adopt the permission and resource identity of another vessel. If vessel A1 is a mirror of vessel A2, then the following properties hold true:
Setting up a vessel mirror requires permission to both permControlProtab and lifeControlProtab. If agent B1 wants to configure vessel B2 as a mirror of vessel B3, agent B1 must hold permControlProtab and lifeControlProtab permissions on both vessel B2 and B3.
A vessel mirror may be used to automatically persist the permissions and life configuration of an agent during runtime. For example, if agent C1 is a vessel mirror of volume item C2, and agent C1 receives permission C3, then permission C3 will be persisted in volume item C2. Even after agent C1 dies, volume item C2 will still hold permission C3.
An agent launched from an application file is a vessel mirror of its application file. An agent launched from an application bundle is a vessel mirror of its application bundle. As a consequence, a launched agent holds the same permissions and life configuration as its application file or bundle. This relationship may be broken if the vessel mirror is removed during runtime.
Every volume item holds implicit permission for all operations on itself. Because a launched agent is a vessel mirror of its application bundle or file, an agent holds full permissions on its application bundle or file upon launch.
ABBREVIATION GLOSSARY
These abbreviations are used throughout BreadSystem documentation.
alloc = Allocation
alt = Alternative
app = Application
arg = Argument
async = Asynchronous
attr = Attribute
buff = Buffer
clr = Clear
cmp = Compare
coll = Collectable
compat = Compatibility
cond = Condition
del = Delete
delim = Delimiter
dep = Dependency
desc = Description
dest = Destination
dir = Directory
equ = Equal
err = Error
func = Function
iface = Interface
impl = Implementation
init = Initialize
instr = Instruction
jmp = Jump
len = Length
max = Maximum
mem = Memory
min = Minimum
msg = Message
num = Number
opt = Option
perm = Permission
pos = Position
prev = Previous
prio = Priority
priv = Private
prop = Propagation
pub = Public
ref = Reference
rel = Release
sLink = Soft link
src = Source
sType = Sentry type
term = Terminal
ver = Version
vItem = Volume item
vol = Volume
wrt = Write