From 782117ab58b38643f0061e6d4cfad2a023512aa2 Mon Sep 17 00:00:00 2001 From: Simon Gerber Date: Fri, 2 Jun 2017 10:51:22 +0200 Subject: [PATCH] doc: tn13: update capability type section Signed-off-by: Simon Gerber --- doc/013-capability-mgmt/type_system.tex | 361 ++++++++++++++++++----------- usr/monitor/include/monitor_invocations.h | 2 - 2 files changed, 227 insertions(+), 136 deletions(-) diff --git a/doc/013-capability-mgmt/type_system.tex b/doc/013-capability-mgmt/type_system.tex index 147a0a5..c926801 100644 --- a/doc/013-capability-mgmt/type_system.tex +++ b/doc/013-capability-mgmt/type_system.tex @@ -64,36 +64,37 @@ CNodes are used to hierarchically construct the CSpace of a domain, as 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. @@ -102,33 +103,46 @@ address lookup terminates early. \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 @@ -138,47 +152,53 @@ of the existing capability, except for changes to the 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, @@ -203,15 +223,17 @@ capability divided by the size of the newly-created objects. \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. @@ -254,6 +276,8 @@ resides. \note{Full implementation and discussion pending} 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} @@ -285,12 +309,12 @@ the trusted computing base. \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} @@ -314,12 +338,12 @@ region of kernel-accessible memory. \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} @@ -354,13 +378,12 @@ user-level dispatcher. \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. @@ -387,6 +410,7 @@ is specified changed by minting an endpoint to another endpoint. 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 @@ -407,6 +431,7 @@ is specified changed by minting an endpoint to another endpoint. receiver's dispatcher control block"; epoffset 64 "Offset of endpoint buffer within dispatcher structure"; + buflen 32 "Length of endpoint buffer in words"; }; \end{lstlisting} @@ -423,6 +448,9 @@ invoking a CNode. The architecture may impose limitations on the 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. @@ -448,10 +476,13 @@ attributes to be set when minting. \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} @@ -466,32 +497,36 @@ created (ie.~retyped from RAM), the kernel zero-fills the frame. \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. @@ -504,30 +539,35 @@ typically used for access to memory-mapped devices. \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 @@ -591,6 +631,8 @@ The IRQ table capability allows the holder to configure the user-level 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. @@ -625,9 +667,13 @@ interrupts will be delivered as IDC messages. 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. @@ -642,13 +688,15 @@ kernel. \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} @@ -671,36 +719,81 @@ The invocation returns the APIC ID of the 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} diff --git a/usr/monitor/include/monitor_invocations.h b/usr/monitor/include/monitor_invocations.h index b2b968f..96affd6 100644 --- a/usr/monitor/include/monitor_invocations.h +++ b/usr/monitor/include/monitor_invocations.h @@ -217,8 +217,6 @@ errval_t monitor_cap_has_relations(struct capref cap, uint8_t mask, uint8_t *res); errval_t monitor_cap_create(struct capref dest, struct capability *cap, coreid_t owner); -errval_t monitor_identify_cnode_get_cap(struct capability *cnode_raw, - capaddr_t slot, struct capability *ret); errval_t monitor_nullify_cap(struct capref cap); errval_t monitor_retype_remote_cap(struct capref croot, capaddr_t src, gensize_t offset, enum objtype newtype, gensize_t objsize, -- 1.7.2.5