_Composite_ Data-Structures and Invocation Path
===============================================

This document briefly details the main data-structures in the
_Composite_ kernel, and the invocation path between components.

Kernel Data-Structures
----------------------

<center>
![Composite data structures](http://www.seas.gwu.edu/~gparmer/data_structures.png)
</center>

The main data-structures include:

- `spd` : Each component is described by a `struct spd`.  Not shown
  are the page tables that are referenced by the `spd`.  Also included
  in the `spd` is a list of extents of valid virtual addresses for the
  component, a list of capabilities that are associated with specific
  faults (i.e. capabilities that should be invoked if that fault
  occurs), a base and extent of the capabilities accessible by the
  `spd`, and other fields.
- `thread` : The thread structure includes a stack of
  `thd_invocation_frame`s, and the `stack_ptr` indexes the top of the
  stack.  This structure acts as a stack of invocations; the bottom of
  the stack is the component that the thread begins execution in, and
  when a component is invoked, a reference to it is pushed on the
  stack.  When an invoked function in the interface of a component
  returns, it pops an item off of the stack to expose the new head,
  and current component.  Not shown here, an invocation frame holds
  the instruction and stack pointers to return to the previous
  component.
- `invocation_cap` : When an invocation is made, the component making
  the invocation specifies a *capability* corresponding to a function
  in the interface of the invoked component.  Each `invocation_cap`
  specifies the component that _owns_ it, the _destination_ component
  of the invocation, and the instruction pointer to begin execution
  at.  Additionally, each capability has a corresponding user-level
  `usr_inv_cap` that includes not only the capability number to pass
  to the kernel, and a function pointer to call to mediate the
  invocation.
- `virtual_spd_layout` : Currently, _Composite_ is a single
  address-space OS.  Components don't overlap in virtual
  addresses. The `virtual_spd_layout` is an array with each entry
  corresponding to a 4MB region of virtual address range, and pointing
  to the `spd` that owns that region.

The Invocation Operation
------------------------

To transfer control from one component to another, an invocation on a
function exported in the target component's interface is
made. Component invocations are one of the most common operations in
_Composite_.  In initial versions of the web server, each HTTP request
make more than 70 invocations between components.

A client component executing in a function (e.g. `main`) calls a
function (e.g. `fn`).  The procedure for this operation follows:

1. The loading process makes such an invocation execute code generated
   by `src/platform/linux/link_load/gen_client_stub.c`.  This code
   parses the `usr_inv_cap` and retrieves both the capability number,
   and the function pointer to call to conduct the invocation.  This
   code is dynamically generated by the `cos_loader`.
2. If both components are in the same protection domain (via Mutable
   Protection Domains), then this function pointer points directly to
   `fn`, thus making its invocation have very little overhead.
   Otherwise, a stub function is invoked.
3. The stub's job is to marshall any arguments that cannot be passed
   in 4 registers, and invoke the kernel.  These clients stubs are
   defined in `src/components/interface/*/stubs/c_stub.c`.  If a
   function does not require more than 4 scalar arguments, then the
   default stub can be used in `src/components/lib/c_stub.S`.  This
   code uses `sysenter` to call the kernel, with the return address
   set to `SS_ipc_client_ret_unmarshal`. A fault-handling path in the
   component exists at this address minus 8, and this path jumps to
   `SS_ipc_client_ret_fatal_err`. Custom stubs, such as those for wrapping
   C invocations in `src/components/include/cstub.h`, must mimic the
   existence of a fault return path at the return address minus 8.
4. Once in the kernel, execution begins in
   `src/platform/linux/module/kern_entry.S:sysenter_interposition_entry`
   which calls `src/platform/linux/module/ipc.S:composite_call_ipc`.
   This assembly function calls the
   `src/kernel/inv.c:ipc_walk_static_cap` function.  This is the main
   logic that will 1) parse through the capability specified to find
   the destination component and entry instruction, 2) switch
   protection domains (by writing to `cr3`), and 3) pushes onto the
   thread's invocation stack the new component.
5. An upcall is triggered at that address in the invoked component and
   execution begins at another stub that demarshals the arguments,
   `src/components/interface/*/stubs/s_stub.S`.  If defined, an
   additional `c` stub is called in
   `src/components/interface/*/stubs/s_cstub.c`.  These call the
   actual function itself.
6. When the function returns it reverses course through all of these
   actions.  In the kernel, control flows through
   `src/platform/linux/module/kern_entry.S:sysenter_interposition_entry`,
   then `src/platform/linux/module/ipc.S:composite_ret_ipc` that in
   turn calls `src/kernel/inv.c:pop`.  This function pops an item off
   of the invocation stack, switches protection domains, and restores
   the stack and instruction pointers in the calling component that
   were saved in the stack.

System Calls
------------

Invocations are made from one component to another.  System calls are
calls to the kernel to request some functionality.  Though future
versions of _Composite_ will use the same path for these invocations
(up until `ipc_walk_static_cap`) as component invocations (to harness
the same access control mechanisms), currently system calls are a
separate path from invocations:

1. System calls are made by calling one of the functions synthesized
   in `src/components/include/cos_component.h`.  This code generates
   assembly to make a kernel system call.
2. The kernel begin execution in
   `src/platform/linux/module/kern_entry.S:sysenter_interposition_entry`,
   and `composite_make_syscall` is called.
3. Here we simply invoke the appropriate system call denoted by the
   `eax` register by offsetting into an array of function pointers
   called `cos_syscall_tbl`.  The appropriate function is invoked, and
   the return value is placed in `eax`.  
4. Most system calls are defined in `src/kernel/inv.c` and they are
   all prepended by `COS_SYSCALL` that ensures that all arguments are
   passed in on the stack (as required by the assembly code).

NOTE: Certain system calls are defined by assembly that very carefully
manipulates the registers.  For our purposes, I'm ignoring these
special case system calls.

Thread Dispatching
------------------

Schedulers are components in _Composite_ that have the ability to
switch between threads.  The `cos_switch_thread` function takes as an
argument, the thread id of the target thread to switch to.  If that
thread being switched to is active in another component (i.e. another
component is on the top of the that thread's invocation stack), then
this involves switching protection domains, and restoring all of that
thread's registers.

Schedulers must also publish data about thread priority for the kernel
to interpret when interrupts occur (see the discussion on the
interrupt "scheduling test" later).  Each scheduler then, has a
`struct cos_sched_data_area` that is a page that is shared between the
scheduler and kernel.  This has an array of structures that correspond
to threads (set up using `sched_cntl`).  These structures include a
`u16_t` that the scheduler uses to publish the "priority" (that might
actually mean something other than priority as is the case in EDF).
The kernel can read this asynchrously to scheduler execution (e.g. at
interrupt time).  For more details, see the scheduler papers on
_Composite_.

Bootstrapping Upcalls
---------------------

When components are created, they do not have any active entities in
them (i.e. threads).  _Composite_ has a mechanism for starting
execution in a component at a well-defined entry point (function).  If
a component requires a thread to start execution, this will always end
up calling the `cos_init` function, by default.  This is the
equivalent of `main` in the normal C API (a compatibility layer will
include a `cos_init` that calls `main`).

The `cos_upcall` _Composite_ system call function is accessible to
schedulers and can be used to make the current thread begin execution
in a target component.  This function will reset the invocation stack
of that thread. to have only one entry, that of the component.  The
`ip` is set to the address of `cos_upcall_fn` that is recorded in the
`spd`.  There are multiple types of upcalls, and the first argument to
the `cos_upcall_fn` is the type.  `cos_upcall`'s type is
`COS_UPCALL_BOOTSTRAP`.  The default implementation of `cos_upcall_fn`
calls `cos_init` for this type.  The default implementation is a
`weak` symbol, so some components (e.g. schedulers) define their own
implementation.

Other types of upcalls:

- Thread termination (see _Thread Termination_ later).
- Unhandled faults (for which an exception handler is not defined; see
  _Fault/Exception Handling_ later).
- Thread creation within the scheduler.
- Brand completion (see _Interrupt Notification and Handling_).

Interrupt Notification and Handling
-----------------------------------

Components require some mechanism for being notified of interrupts
with a low (bounded) latency.  This is currently used for 

1. timer notification,
2. IPIs,
3. network packet arrival,
4. translator events

When a component wants to receive interrupts, they create a `brand`
that is `wired` to an interrupt source.  A thread in that component
can execute `brand_wait`, specifying the brand to wait on.  This
thread will block waiting on the brand for an interrupt it is wired
to.  Technically, a brand is not necessary, and one could wait for the
event from the source directly.  However, we use the intermediate (the
brand) and enforce a two step process (first wire the brand to the
interrupt source, and second have a thread wait on interrupts wired to
the brand) to 

1. Enable access control to be done at wire time (by calling
`brand_wire`).  Specifically, at this time we can answer the question
of it the component should have access to the interrupt source.  This
is not a fast path.
2. Multiple threads can wait for interrupts from a single interrupt
source, and they are all queued on the brand.  When an interrupt
arrives, the first is re-activated.

_Data-structures_: Brands are threads.  This is unintentially very
confusing.  Do not think of brands as threads.  However, in the
kernel, brands are represented using the `thread` structure.

_Interrupt arrival_: When an interrupt arrives, if there is a thread
(called, ambiguously, and `upcall` thread) waiting on the brand, it is
activated pending a "scheduling test".  If a thread is not blocked on
the brand, then the brand incriments a `pending_interrupt` count.

_Interrupt-time "scheduling test"_: A scheduling test is done to
determine if the thread to be activated on the interrupt has a higher
priority than the currently executing thread.  As only the schedulers
can make this determination and interrupts trigger kernel execution,
this is non-trivial.  Long-story short, the `cos_sched_data_area` is
used to convey this information, and the kernel will walk through all
of the schedulers that schedule both the interrupt thread and the
current thread.  Only if the priority values in that structure are
higher (numerically lower) for the interrupt thread is it immedately
executed.  When this is done, a pointer is maintained to the
`interrupted_thread` in the interrupt `thread`'s structure.

`brand_wait` _implementation_: The kernel does the following
operations when `brand_wait` is called.  If `pending_interrupt` is
non-zero, it is decrimented, and the thread returns immediately.

Thread Termination
------------------

When a thread returns from a component, either it is returning from an
invocation in which case it has multiple entries on its invocation
stack, or it is in the component that it was originally `cos_upcall`ed
into.  In the latter case, there is no other component to return to,
and the thread is terminating (this is equivalent to returning from
`main`).

In such cases, the thread is caused to upcall into the scheduler
responsible for that thread passing `COS_UPCALL_DESTROY` as the type
of upcall.  At this point, the scheduler can destroy the thread (using
`cos_sched_cntl`).

Fault/Exception Handling
------------------------

Exceptional execution condition can occur during a specific thread's
execution.  This includes hardware-defined conditions such as page
faults, general protection faults, and divide by zero, but also
software-defined conditions such as a fault notification (see Jiguo
Song's work).  When an exception occurs, we must save all registers,
and maintain the ability to return to that execution state after the
exception has been handled.

The mechanism for doing this in _Composite_ harnesses the normal
invocation path, and simply defines the specific capability that
should be invoked for the specific exception.  Before the invocation
path is called, the registers are saved in `fault_regs` in the
`thread` structure.  The entry on the invocation stack is marked as
returning from a fault, so that when the component that handles the
fault returns, the registers will be restored.  The fault registers
can be read and written to using the `cos_thread_cntl` system call.
An example of an use for this is in a page-fault handler, one wants to
know the `ip` register to print out information about where the fault
occured.

The component that defines the exception handler simply defines a
globally visible function prepended by `fault_` from the list
`src/platform/linux/link_load/cos_loader.c:cos_flt_handlers`.

The code relevant to fault handling is in:

- In `src/kernel/include/spd.h`, the `fault_handler` array is a
  mapping of the exception enumerated in
  `src/kernel/include/shared/cos_types.h:cos_flt_off`, to the
  capability for that `spd` that should be invoked for that specific
  exception.
- To create the capabilities to the component that should handle the
  fault, there is a one-to-one correspondance between entries
  `src/kernel/include/shared/cos_types.h:cos_flt_off` and the handler
  names in
  `src/platform/linux/link_load/cos_loader.c:cos_flt_handlers`.  The
  loader observes these handler names, and creates the capabilities to
  them, while placing the capability number in the exception's entry
  in the `spd`'s `fault_handler` array.
- Fault handling is processed through `src/kernel/inv.c:fault_ipc_invoke`
  which looks up and invokes the capability for the fault handler.

A useful example of a fault handler is the page fault handler implemented in
`src/components/implementation/pgfault/recov_poc/pgfault.c`, which attempts
to recover a page fault by resetting the faulted component with its initial
boot state. The handler manipulates the invocation stack to set the return
instruction pointer so that the client component that invoked the faulted
component will retry the component invocation.

Future Changes
--------------

- In the future, we will probably make the capability table per-`spd`,
  thus index into a local table for each component.
- System calls should share a fair amount of code with the invocation
  path.  At the very least, the access control mechanisms
  (capabilities) used to protection invocation destinations should
  also be applied to system calls.
- Many different thread notifications such as thread termination and
  the like should actually use the fault notification invocation
  mechanism to consolidate much of the code.
