described in \ref{sec:cspace}. All capability management is
performed through invocations on CNodes.
-A CNode capability stores a \emph{guard} and \emph{guard size}, which
-is expressed as a number of bits. As in guarded page
-tables\cite{Liedtke_GPT}, the guard allows the depth of the CSpace
-tree to be reduced by skipping levels that would only contain a single
-mapping. When resolving a CSpace address that has led to a CNode
-capability, the guard is compared with the corresponding number of
-bits from the remaining part of the address, and if it does not match,
-the lookup fails.
+CNodes are organized as a two-level table with distinct capability types for
+the root or L1 CNode (which can be dynamically enlarged), and L2 or leaf
+CNodes which have a fixed size of 256 capability slots.
+The two-level CNode table forms a 32-bit capability address space for each
+dispatcher.
+User space refers to entries in that address space with a 32-bit
+\emph{capability address}.
+The high 24 bits of the capability address are used as an index into the L1
+CNode.
+The L1 CNode index can be too large for a given L1 CNode that has not been
+enlarged to it's maximum size of $2^24$ slots.
+A user space operation referring to an L1 slot that is not allocated will fail
+with \verb|SYS_ERR_L1_CNODE_INDEX|.
+The CPU driver then uses the L1 index to perform a lookup for the L2 CNode.
+If an L2 CNode exists for the given L1 index, the low 8 bits of the supplied
+capability address are used as an index into the L2 CNode.
+The CPU driver then uses the L2 index to perform a lookup for the requested
+capability.
Many CNode invocations require that the caller provide both a CSpace
-address and the number of \emph{valid bits} in the address. This
-allows the invocations to refer to another CNode capability that is
-located at an intermediate level in the tree, and thus would usually
-be recursed through by the address resolution algorithm. If the number
-of valid bits associated with a CSpace is less than the size of a full
-CSpace address, only the least significant bits that are valid, but
-starting with the most significant bit thereof, are used, and the
-address lookup terminates early.
+address and the number of \emph{levels} to resolve. This allows the
+invocations to refer to a L2 CNode capability that is located in a L1 slot,
+and thus would usually be recursed through by the address resolution
+algorithm.
\begin{description}
\item[Origin] Retyping from RAM type capabilities
\item[Retypability] No
-\item[Mint parameters] The mint parameters can be used to set a guard
- on a CNode.
- \begin{itemize}
- \item Parameter 1: The guard to set.
- \item Parameter 2: The size of the guard in bits.
- \end{itemize}
+\item[Mint parameters] No
\item[Interpretation of rights] \note{Explain rights and rights mask.
Capability rights and rights masks are currently not implemented.
\item[Transferability to another core] Yes. When transfered to
another core, capability is implicitly retyped to a Foreign CNode
- type. \note{We do not allow CNode type caps to be transferred yet.}
+ type.
+ \note{We currently allow CNode type caps to be transferred without doing
+ the type conversion, which is extremely risky, but does not break the
+ system if the receiver only ever tries to copy capabilities out of the
+ received CNode.}
\item[Last copy deleted] When the last copy is deleted, all
capabilities stored within it are also deleted.
-\item[Concrete representations] The in-memory representation of on
- x86-64 is as follows:
+\item[Concrete representations] The in-memory representation is as follows:
\begin{lstlisting}[language=Mackerel]
- datatype cnode_cap "CNode capability" {
+ datatype L1CNode "L1 CNode capability" {
cnode 64 "Physical base address of CNode";
- bits 8 "Number of bits this CNode resolves";
+ size 64 "Allocated size of CNode in bytes";
rightsmask 8 "Capability rights mask";
- guard_size 8 "Number of bits in guard word";
- guard 32 "Bitmask already resolved when reaching this CNode";
};
\end{lstlisting}
+
+ \begin{lstlisting}[language=Mackerel]
+ datatype L2CNode "L2 CNode capability" {
+ cnode 64 "Physical base address of CNode";
+ rightsmask 8 "Capability rights mask";
+ };
+ \end{lstlisting}
+
+ Note that L2 CNodes have a fixed size of 16384 bytes, which is
+ \textbf{not} stored in their in-memory representation.
\end{description}
\begin{invocation}{Mint}\label{sec:mint}
- \arg CSpace address of destination CNode
- \arg Slot number in destination CNode
- \arg CSpace address of source capability
- \arg Number of valid bits in destination CNode address
- \arg Number of valid bits in source capability address
- \arg Type-specific parameter 1
- \arg Type-specific parameter 2
+ \arg Capability of the source cspace root CNode to invoke
+ \arg Destination cspace cap address relative to source cspace
+ \arg Destination CNode address relative to destination cspace
+ \arg Slot in destination CNode cap to place copy into
+ \arg Address of cap to copy.
+ \arg Level/depth of 'to'.
+ \arg Level/depth of 'from'.
+ \arg 1st cap-dependent parameter.
+ \arg 2nd cap-dependent parameter.
\end{invocation}
The Mint invocation creates a new capability in an existing CNode
slot, given an existing capability. The new capability will be a copy
The use of the two type-specific parameters is described along with
the description of the relevant type.
-If the destination capability is of type VNode, then instead of a
-mint, a page table entry is made into the page table pointed to by the
-VNode. In this case, the source capabilities must be of type VNode,
-Frame, or Device Frame. The first parameter specifies architecture
-specific page (table) attributes and the second parameter specifies an
-offset from the source frame/device frame to map.
-
\begin{invocation}{Copy}
- \arg CSpace address of destination CNode
- \arg Slot number in destination CNode
- \arg CSpace address of source capability
- \arg Number of valid bits in destination CNode address
- \arg Number of valid bits in source capability address
+ \arg Capability of the source cspace root CNode to invoke
+ \arg Capability address of destination root cnode relative to our cspace
+ \arg CNode address to place copy into relative to destination cspace.
+ \arg Slot in CNode cap to place copy into.
+ \arg Capability address of source root cnode relative to our cspace
+ \arg Address of cap to copy.
+ \arg Level/depth of 'to'.
+ \arg Level/depth of 'from'.
\end{invocation}
This invocation is similar to Mint, but does not change any
-type-specific data.
-
-If the destination capability is of type VNode, then instead of a
-copy, a page table entry is made into the page table pointed to by the
-VNode. In this case, the source capabilities must be of type VNode,
-Frame, or Device Frame.
+type-specific data. In fact, the CPU driver currently uses the same code path
+for copy and mint, and a mint with both cap-dependent parameters set to zero
+will behave exactly like a Copy invocation.
\begin{invocation}{Retype}
- \arg CSpace address of source capability to retype
- \arg Type of new objects to create
- \arg Size in bits of each object, for variable-sized objects
- \arg CSpace address of destination CNode
- \arg Slot number in desination CNode of the first created capability
- \arg Number of valid bits in destination CNode address
+ \arg Capability of the source cspace root CNode to invoke
+ \arg Source cspace cap address in our cspace.
+ \arg Address of cap to retype in source cspace.
+ \arg Offset into cap to retype
+ \arg Kernel object type to retype to.
+ \arg Size of created objects, for variable-sized types
+ \arg Number of objects to create
+ \arg Destination cspace cap address in our cspace
+ \arg Address of CNode cap in destination cspcae to place retyped caps into.
+ \arg Level/depth of CNode cap in destination cspace
+ \arg Slot in CNode cap to start placement.
\end{invocation}
This invocation creates one or more new descendant capabilities of the
specified type in the specified slots, given a source capability and a
-destination type. It will fail if the source or destination are
-invalid, or if the capability already has descendants. (some
-capability types, currently only the dispatcher type can be retyped
-even if it already has descendants). The destination slots must all
-occupy the same CNode. The permissible source/destination pairs are
-shown in \ref{fig:cap_types} and \ref{tab:retype_types}. The number
-of new capabilities created is determined by the size of the source
-capability divided by the size of the newly-created objects.
+destination type.
+It will fail if the source or destination are invalid, or if the capability
+already has descendants which overlap the requested region (some capability
+types, currently only the dispatcher type can be retyped even if it already
+has descendants).
+The destination slots must all occupy the same CNode. The permissible
+source/destination pairs are shown in \ref{fig:cap_types} and
+\ref{tab:retype_types}.
+The number of new capabilities created is given as an argument.
+The invocation can fail if the retype region, which is defined as a pair of
+base address and size does not fit into the source capability.
+The retype region's base address is given as an offset into the source
+capability, and it's size is given as the number of capabilities to create
+multiplied by the requested size for the new capabilities.
+
+\note{check tables and figure for validity in 2017}
\ctable[
caption=Permissible types for the Retype invocation,
\end{figure}
\begin{invocation}{Delete}
- \arg CSpace address of capability to delete
- \arg Number of valid bits in capability address
+ \arg Capability of the CNode to invoke
+ \arg Address of cap to delete.
+ \arg Level/depth of 'cap'.
\end{invocation}
This invocation deletes the capability at the given address, freeing
the associated CNode slot.
\begin{invocation}{Revoke}
- \arg CSpace address of capability to Revoke
- \arg Number of valid bits in capability address
+ \arg Capability of the CNode to invoke
+ \arg Address of cap to delete.
+ \arg Level/depth of 'cap'.
\end{invocation}
This invocation revokes the capability at the given address.
guard 32 "Bitmask already resolved when reaching this CNode";
};
\end{lstlisting}
+ \note{This should not be used as-is, as we have changed the CNodes
+ themselves significantly in 2016.}
\end{description}
\note{Discussion pending on invocations}
\item[Last copy deleted] \note{NYI, maybe inform some special
dispatcher like memory server}
-\item[Concrete representations] The in-memory representation on x86-64 is as follows:
+\item[Concrete representations] The in-memory representation is as follows:
\begin{lstlisting}[language=Mackerel]
datatype physaddr_cap "Physical address range capability" {
base 64 "Physical base address of region";
- bits 8 "Size of region";
+ bytes 64 "Size of region";
};
\end{lstlisting}
\end{description}
\item[Last copy deleted] \note{NYI, maybe inform some special
dispatcher like memory server}
-\item[Concrete representations] The in-memory representation on x86-64 is as follows:
+\item[Concrete representations] The in-memory representation is as follows:
\begin{lstlisting}[language=Mackerel]
datatype ram_cap "RAM capability" {
base 64 "Physical base address of region";
- bits 8 "Size fo region";
+ bytes 64 "Size of region";
};
\end{lstlisting}
\end{description}
\end{description}
\begin{invocation}{Setup}
- \arg CSpace address of domain's root CNode (root of CSpace)
- \arg Number of valid bits in root CNode address
- \arg CSpace address of domain's root VNode (root page table)
- \arg Number of valid bits in root VNode address
- \arg CSpace address of dispatcher frame (user-level dispatcher
- data) capability
- \arg Whether to make dispatcher runnable
+ \arg Address of dispatcher capability relative to dispatchers caller's cspace
+ \arg Address of existing dispatcher for domain ID relative to caller's cspace
+ \arg Root of CSpace for new dispatcher relative to caller's cspace
+ \arg Root of VSpace for new dispatcher relative to cspace for new dispatcher.
+ \arg Frame capability for dispatcher structure relative to cspace for new dispatcher.
+ \arg Make runnable if true
\end{invocation}
This invocation sets any of the above parameters on a dispatcher
object. If any of the CSpace addresses are null, they are ignored.
badge on the capability
\begin{itemize}
\item Parameter 1: The endpoint offset to set on the capability.
+ \item Parameter 2: The endpoint buffer size to set on the capability.
\end{itemize}
\item[Retyability] No
receiver's dispatcher control block";
epoffset 64 "Offset of endpoint buffer within dispatcher
structure";
+ buflen 32 "Length of endpoint buffer in words";
};
\end{lstlisting}
capabilities that may be copied into a VNode, or may allow extra
attributes to be set when minting.
+We define one VNode capability type per hardware page table type per
+architecture.
+
\begin{description}
\item[Origin] Retyping from RAM type capabilities.
\end{description}
\subsection{Frame}
-A frame capability refers to a naturally-aligned power-of-two-sized
-region of physical memory that may be mapped into a domain's virtual
-address space (by copying it to a VNode). When a frame capability is
-created (ie.~retyped from RAM), the kernel zero-fills the frame.
+A frame capability refers to a page-aligned\footnote{We coloquially refer to
+4kB pages as pages} region of physical memory with a size that is a multiple
+of 4096 bytes.
+A frame capability may be mapped into a domain's virtual address space (by
+copying it to a VNode).
+When a frame capability is created (ie.~retyped from RAM), the kernel
+zero-fills the frame.
\note{Is this a good idea? Shouldn't we be able to pre-zero frames?
-AB}
\item[Transferability to another core] Yes
-\item[Last copy deleted] \note{NYI, initiate unmapping from page
- tables. We may choose for this to happen when the last copy of a
- frame within a dispatcher is deleted rather than the last copy in
- the entire system.}
+\item[Any copy deleted] Look up associated \emph{Mapping} capability and use
+ information stored in that mapping to remove any page table entries that
+ exist for this copy of the frame capability.
+
+\item[Last copy deleted] Check whether there are any other capabilities that
+ refer to the region, or a superset of the region, referred to by this
+ capability. If not, return create a new RAM capability and return it to a
+ specially identified ``memory server'' dispatcher.
-\item[Concrete representations] The in-memory representation on x86-64
- is as follows:
+\item[Concrete representations] The in-memory representation is as follows:
\begin{lstlisting}[language=Mackerel]
datatype frame_cap "Frame capability" {
- base 64 "Physical base address of untyped region";
- bits 8 "Size of the region";
+ base 64 "Physical base address of mappable region";
+ bytes 64 "Size of the region";
};
\end{lstlisting}
\end{description}
\noarginvocation{Identify}
-This invocation returns the physical address and size (in bits) of the frame.
+This invocation returns the physical address and size (in bytes) of the frame.
\subsection{Device frame}
-A device frame capability refers to a naturally-aligned
-power-of-two-sized region of physical address space that may be mapped
-into a domain's virtual address space (by copying it to a VNode).
-Unlike frame capabilties, the kernel does not zero-fill device frame
-capabilities upon mapping. As the name implies, device frames are
-typically used for access to memory-mapped devices.
+A device frame capability refers to a page-aligned region of physical address
+space, with a size that is a multiple of 4096, that may be mapped into a
+domain's virtual address space (by copying it to a VNode).
+Unlike frame capabilities, the kernel does not zero-fill device frame
+capabilities upon mapping.
+As the name implies, device frames are typically used for access to
+memory-mapped devices.
\begin{description}
\item[Origin] Retyping Physical address range type capabilities.
\item[Transferability to another core] Yes
-\item[Last copy deleted] \note{NYI, initiate unmapping from page
- tables. We may choose for this to happen when the last copy of a
- frame within a dispatcher is deleted rather than the last copy in
- the entire system.}
+\item[Any copy deleted] Look up associated \emph{Mapping} capability and use
+ information stored in that mapping to remove any page table entries that
+ exist for this copy of the frame capability.
+
+\item[Last copy deleted] Check whether there are any other capabilities that
+ refer to the region, or a superset of the region, referred to by this
+ capability. If not, return create a new RAM capability and return it to a
+ specially identified ``memory server'' dispatcher.
-\item[Concrete representations] The in-memory representation on x86-64 is as follows:
+\item[Concrete representations] The in-memory representation is as follows:
\begin{lstlisting}[language=Mackerel]
datatype device_cap "Device Frame capability" {
base 64 "Physical base address of region";
- bits 8 "Size of the region";
+ bytes 64 "Size of the region";
};
\end{lstlisting}
\end{description}
\noarginvocation{Identify} This invocation returns the physical
-address and size (in bits) of the frame.
+address and size (in bytes) of the frame.
\subsection{IO}
-IO capability gives the holder the ability to read and write to IO
-ports.
+An IO capability gives the holder the ability to read and write to IO ports.
+IO capabilities are currently only supported on x86-64.
\begin{description}
-\item[Origin] A single capability created at boot time in the bsp core.
+\item[Origin] A single IO capability covering the whole IO region created at
+ boot time in the BSP core.
\item[Retyability] No
handler dispatcher that will be invoked when the kernel receives
device interrupts.
+\note{Discuss new IRQSrc and IRQDest capabilities}
+
\begin{description}
\item[Origin] Given to the first domain spawned on a core.
This invocation clears the handler for the given IRQ.
\subsection{Kernel Capability}
-So far, this capability is treated as the magic capability that gives
-the holder a backdoor into performing special operations in the
-kernel.
+This capability is used to confer authority to the user-space part of the
+Barrelfish kernel, the ``monitor''.
+Some other privileged domains also receive a copy of the kernel capability,
+but we should factor those operations out and create different capability
+types that give those dispatchers only the right to invoke the operations they
+actually need.
+One example of such a dispatcher is the dispatcher that brings up new cores.
\begin{description}
\item[Origin] Given to the first domain spawned on a core.
\item[Last copy deleted] \note{NYI}
-\item[Concrete representations] The in-memory representation on x86-64 is as follows:
+\item[Concrete representations] The in-memory representation is as follows:
\begin{lstlisting}[language=Mackerel]
datatype kernel_cap "Kernel capability" {
- kernel_id 8 "Id of the Kernel";
};
\end{lstlisting}
+
+ The kernel capability does not convey any information, it is simply a
+ token of authority.
\end{description}
\begin{invocation}{Spawn core}
\begin{invocation}{Identify capability}
\arg CSpace address of the capability to identify
- \arg Number of valid bits in the capability
+ \arg Level of the capability to identify
\arg Location of buffer to hold capability representation
\end{invocation}
The invocation stores the kernel's in-memory representation of the
capability into the given buffer.
-
-\begin{invocation}{Identify CNode, get capability}
- \arg In memory representation of a CNode capability
- \arg Slot number of a capability within the CNode capability
+j
+\begin{invocation}{Identify another dispatcher's capability}
+ \arg CSpace address of the dispatcher's L1 cnode capability
+ \arg Level in our CSpace of the L1 cnode capability
+ \arg CSpace address relative to the dispatcher's CSpace of the capability to
+ identify
+ \arg Level in the dispatcher's CSpace of the capability to identify
\arg Location of buffer to hold capability representation
\end{invocation}
-The invocation stores the kernel's in-memory representation of the
-capability located at the given slot in the given CNode into the given
-buffer.
+The invocation stores the kernel's in-memory representation of another
+dispatcher's capability into the given buffer.
\begin{invocation}{Create capability}
\arg In memory representation of a capability
\arg CSpace address of the CNode the place the created capability in
- \arg Number of valid bits in the CSpace address of the CNode
+ \arg Level of the CNode in the CSpace
\arg Slot number to place the capability in
+ \arg Owning core of the new capability
\end{invocation}
-Creates the given capability in the given slot in the given CNode.
-
-\begin{invocation}{Create capability}
- \arg In memory representation of a capability
- \arg CSpace address of the CNode the place the created capability in
- \arg Number of valid bits in the CSpace address of the CNode
- \arg Slot number to place the capability in
+Creates the given capability in the given slot in the given CNode with the
+given Owner.
+
+\note{TODO: KernelCmd_Copy_existing}
+
+\begin{invocation}{Set capability's remote relations}
+ \arg CSpace address of CSpace (L1 CNode) in which to look for capability
+ \arg Level of root capability.
+ \arg CSpace address of capability
+ \arg Level of capability
+ \arg Remote relations to set.
+ \arg Mask: bitmask to show which remote relations to set.
+\end{invocation}
+If mask is not zero, set remote relations according to the bits set in the
+expression \verb|remote_relations & mask|.
+Always returns the remote relations bitmask after potentially setting new
+remote relations.
+
+\begin{invocation}{Read capability's remote relations}
+ \arg CSpace address of capability
+ \arg Level of capability
\end{invocation}
-Creates the given capability in the given slot in the given CNode.
+Returns bitmask of currently set remote relations on capability.
+
+\begin{itemize}
+ \item \verb|KernelCmd_Get_arch_id|: Returns arch id of caller's core
+ \item \verb|KernelCmd_Nullify_cap|: Set the capability to NULL allowed it to be reused
+ \item \verb|KernelCmd_Setup_trace|: Set up trace buffer
+ \item \verb|KernelCmd_Register|: Register monitor notify endpoint
+ \item \verb|KernelCmd_Domain_Id|: Set domain ID of dispatcher
+ \item \verb|KernelCmd_Get_cap_owner|:
+ \item \verb|KernelCmd_Set_cap_owner|:
+ \item \verb|KernelCmd_Lock_cap|:
+ \item \verb|KernelCmd_Unlock_cap|:
+ \item \verb|KernelCmd_Delete_last|:
+ \item \verb|KernelCmd_Delete_foreigns|:
+ \item \verb|KernelCmd_Revoke_mark_target|:
+ \item \verb|KernelCmd_Revoke_mark_relations|:
+ \item \verb|KernelCmd_Delete_step|:
+ \item \verb|KernelCmd_Clear_step|:
+ \item \verb|KernelCmd_Retype|:
+ \item \verb|KernelCmd_Has_descendants|:
+ \item \verb|KernelCmd_Is_retypeable|:
+ \item \verb|KernelCmd_Sync_timer|:
+ \item \verb|KernelCmd_IPI_Register|:
+ \item \verb|KernelCmd_IPI_Delete|:
+ \item \verb|KernelCmd_GetGlobalPhys|:
+ \item \verb|KernelCmd_Add_kcb|: add extra kcb to be scheduled
+ \item \verb|KernelCmd_Remove_kcb|: remove kcb from scheduling ring
+ \item \verb|KernelCmd_Suspend_kcb_sched|: suspend/resume kcb scheduler
+ \item \verb|KernelCmd_Get_platform|: Get architecture platform
\note{The other invocations are outdated and will probably change
when the monitors are discussed}
projects / barrelfish / commitdiff