Tidying up techical notes
[barrelfish] / doc / 013-capability-mgmt / CapMgmt.tex
1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2 % Copyright (c) 2011, ETH Zurich.
3 % All rights reserved.
4 %
5 % This file is distributed under the terms in the attached LICENSE file.
6 % If you do not find this file, copies can be found by writing to:
7 % ETH Zurich D-INFK, Universitaetstr. 6, CH-8092 Zurich. Attn: Systems Group.
8 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
9
10 \documentclass[a4paper,twoside]{report} % for a report (default)
11
12 \usepackage{bftn} % You need this
13 \usepackage[pdftex]{graphicx}
14 \usepackage{color,listings,ctable}
15
16 \title{Capability Management in Barrelfish}   % title of report
17 \author{Akhilesh Singhania, Ihor Kuz, Mark Nevill}      % author
18 \tnnumber{013}  % give the number of the tech report
19 \tnkey{Capability Management} % Short title, will appear in footer
20
21 % \date{Month Year} % Not needed - will be taken from version history
22
23 \newcommand{\note}[1]{[\textcolor{red}{\textit{#1}}]}
24
25 \lstdefinelanguage{Mackerel}{
26   morekeywords={datatype,device,register,regtype,constants,type,at,
27               many,edit,io,also},
28   sensitive=false,
29   morecomment=[l]{//},
30   morecomment=[s]{/*}{*/},
31   morestring=[b]",
32   showspaces=false,
33   showstringspaces=false,
34   showtabs=false,
35 }
36
37 \newcommand{\noarginvocation}[1]{\paragraph{#1 invocation}}
38 \newcounter{invocArgCnt}
39 \newenvironment{invocation}[1]{%
40   \noarginvocation{#1}
41   
42   \begin{list}{\emph{Argument~\arabic{invocArgCnt}:}}{%
43     \usecounter{invocArgCnt}%
44     \setlength{\rightmargin}{\leftmargin}%
45     \setlength{\itemsep}{0ex}%
46   }
47   \renewcommand{\arg}{\item}
48 }{%
49   \end{list}
50 }
51
52 \begin{document}
53 \maketitle
54
55 %
56 % Include version history first
57 %
58 \begin{versionhistory}
59 \vhEntry{1.0}{08.03.2011}{AS}{Initial version}
60 \vhEntry{2.0}{27.1.2012}{MN}{New capability system design}
61 \vhEntry{2.1}{8.7.2013}{SK}{Updates}
62 \vhEntry{2.2}{1.12.2013}{TR}{Fixed missing references/citations}
63 \end{versionhistory}
64
65 % \intro{Abstract}              % Insert abstract here
66 % \intro{Acknowledgements}      % Uncomment (if needed) for acknowledgements
67 % \tableofcontents              % Uncomment (if needed) for final draft
68 % \listoffigures                % Uncomment (if needed) for final draft
69 % \listoftables                 % Uncomment (if needed) for final draft
70
71 \chapter{Introduction}
72
73 This document discusses the state of capabilities in the Barrelfish
74 operating system.
75
76 Chapter \ref{chap:known_issues} lists the currently known issues with
77 capability management and \ref{chap:type_system} discusses the type
78 system.
79
80 Chapter \ref{chap:current_state} discusses the current state of the
81 implementation in Barrelfish, chapter \ref{chap:db} discusses
82 different approaches for maintaining a multicore mapping database of
83 capabilities, chapter \ref{chap:solutions} discusses the requirements
84 from a correct solution and discusses four different solutions,
85 chapter \ref{chap:implementation} discusses some Barrelfish specific
86 challenges in implementing the solutions, and chapter \ref{chap:nyd}
87 highlights issues not yet covered in this document.
88
89 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
90 \chapter{Known Issues}\label{chap:known_issues}
91 \begin{itemize}
92
93 \item Kernel operations should not take longer than $O(1)$.  Some
94   capability operations are not constant time but can take $O(n)$
95   where $n$ is the size of the mapping database. Spending so much time
96   in the kernel is detrimental for good scheduling as when in the
97   kernel, interrupts are disabled. All non constant time operations
98   should be punted to the monitor.
99
100 \item When the last copy of a lmp capability or frame capability
101   backing ump channels is deleted, should it initiate a connection
102   tear down?
103
104 \item We have no mechanics for tracking frames mapped into VNodes. So
105   that if either is deleted, the entries are properly cleaned up.
106
107 \item Multicore capability management. We have an implementation on
108   the tip. It is not enabled and has some shortcomings. Not all
109   shortcomings are not known however some missing details are
110   known. As discussed in chapter~\ref{chap:solutions}, all remote
111   relations including descendants, copies, and ancestors must be
112   tracked. The implementation only tracks ancestors.
113
114 \item Fragmentation of memory. Example: a ram capability of 4GB is
115   retyped into two capabilities of 2GB each. One of the 2GB capability
116   is deleted. The only way to get a capability to that 2GB back is to
117   also delete the other 2GB capability and then retype the 4GB
118   capability again.
119
120 \item The mapping database is maintained as a doubly linked
121   list. Implementing Boolean operations like ``has\_descendants'' and
122   ``has\_copies'' require walking the database and testing type
123   specific data structures. We feel that these are not efficient or
124   robust. If we move the mapping database into the monitor, we think
125   that this should at worse become a performance issue and not a
126   correctness one.
127
128 \item IO space can be treated in a same way as physical memory. So
129   instead of using mint operations to update ranges, we use retype
130   operations. This is useful as different IO capabilities will have
131   the ancestor, descendant, and copy relationships rather than just a
132   copy relationship. The former is richer and can offer improved
133   maintenance.
134
135 \item When a new capability is introduced in a core via cross-core
136   send, the kernel must walk the entire mapping database to find the
137   appropriate place to insert the capability. The operation is linear
138   time. This operation must either happen in the monitor or must be
139   made more efficient. If we move the mapping database into the
140   monitor, we think that this should at worse become a performance
141   issue and not a correctness one.
142
143 \item Simon and I had envisioned a memory server mechanism where it
144   would delete all ram capabilities after handing them out. This
145   allows Simon to implement his version of domain shutdown (discussed
146   in a supporting document). In a nutshell, in his system, the spawn
147   daemon saves all user dispatcher capabilities and revokes them to
148   kill a user dispatcher and repossess its memory. However, there is a
149   subtle problem with this mechanism. A malicious dispatcher can
150   create loops in its CSpace. E.g. root cnode contains a capability to
151   cnode1, cnode1 contains a capability to cnode2, and cnode2 contains
152   another capability to cnode1. When a dispatcher does this and the OS
153   tries to kill it, root cnode will be deleted and all capabilities
154   within it as well. When the OS deletes cnode1, it will check if it
155   has copies, which it does so cnode1 will not be deleted. This will
156   leak memory in the system.
157
158   To avoid this problem, the OS must maintain ancestors of all
159   capabilities that are handed out to user applications and to kill
160   the user application, it must revoke the ancestor capabilities.
161 \end{itemize}
162
163 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
164 \input{type_system.tex}
165
166 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
167
168 \chapter{Current State}\label{chap:current_state}
169
170 This chapter will cover how capabilities are stored and what happens
171 on capability invocation.
172
173 \section{Storage}\label{sec:cspace}
174 For security reasons, capabilities are stored in kernel-space and
175 users are given pointers to them. Each capability is stored in two
176 separate databases:
177
178 \begin{itemize}
179 \item Each dispatcher has an associated capability space that holds
180   all the capabilities it has.  The capability space of a dispatcher
181   is implemented using the CNode type capability. Each dispatcher is
182   associated with a ``root CNode'' that contains all capabilities the
183   dispatcher has.
184 \item Each core has a mapping database that holds all the capabilities on the
185         core. The mapping database is implemented using a tree of the capabilities.
186         As discussed later in the chapter, the mapping database stores the
187         capabilities in a particular order to facilitate different capability
188         operations.
189 \end{itemize}
190
191 \section{Capability invocation}\label{sec:sys_invoke}
192 When a dispatcher invokes a capability, it passes the kernel an
193 address of the capability in the CSpace it wishes to invoke. The
194 kernel locates the capability starting from the dispatcher's root
195 CNode (walks the capability space), verifies that the requested
196 operation can indeed be performed on the specified capability and then
197 performs the operation.
198
199 \section{Data structures}
200 Capabilities in Barrelfish are represented by the following data
201 structures:
202
203 {\scriptsize
204 \begin{verbatim}
205     struct mdbnode {
206       struct cte *left, *right;  // Links to the mapping database
207           ...
208     };
209
210     struct CNode {
211       paddr_t cnode;      // Base address of CNode
212       uint8_t bits;       // Size in number of bits
213       ...
214     };
215
216     union capability_u {  // Union of all types of capabilities
217       ...
218       struct CNode cnode;
219       ...
220     };
221
222     struct capability {
223       enum objtype type;     // Type of capability
224       union capability_u u; // Union of the capability
225     };
226
227     struct cte {
228       struct capability   cap;     ///< The actual capability
229       struct mdbnode      mdbnode; ///< MDB node for the cap
230     };
231 \end{verbatim}
232 }
233
234 A capability, \verb|cte|, consists of the actual capability represented by the
235 ``capability'' structure and an entry in the mapping database represented by
236 the ``mdbnode'' structure. The capability structure contains the type specific
237 information and the mdbnode contains pointers for the tree representing the
238 mapping database.
239
240 Capabilities can be looked-up in two ways.
241 \begin{itemize}
242 \item All capabilities on a core are stored in a mapping database. It
243   is possible to reach any capability on the core by traversing from
244   any other capability on the core.
245
246 \item Capabilities are also stored in the CNode type capability. The
247   area of memory identified by the CNode structure is actually an
248   array of capabilities. Starting from the ``root CNode'' of a
249   dispatcher, it is only possible to reach any capability the
250   dispatcher holds.
251 \end{itemize}
252
253 \section{Terminology}
254
255 This section discusses some terminology to facilitate the discussion
256 of capability management.
257
258 \subsection{Copy}
259
260 A capability X is a copy of a capability Y if:
261
262 \begin{itemize}
263 \item X was copied from Y
264 \item or Y was copied from X
265 \item or X was copied from Z and Z was copied from Y
266 \end{itemize}
267
268 \subsection{Descendants}
269
270 A capability X is a descendant of a capability Y if:
271
272 \begin{itemize}
273 \item X was retyped from Y
274
275 \item or X is a descendant of Y1 and Y1 is a copy of Y
276
277 \item or X is a descendant of Z and Z is a descendant of Y
278
279 \item or X is a copy of X1 and X1 is a descendant of Y
280 \end{itemize}
281
282 \subsection{Ancestor}
283
284 A is a ancestor of B if B is a descendant of A.
285
286 \section{CNode invocations}
287
288 Most Capabilities have type specific invocations.  Operations on the
289 CNode capability modifies the capability space of the system. We
290 discuss how these operations are implemented for a single core system
291 here.
292
293 \note{Invocations on other capability types will probably also modify
294   the capability space but alas we don't know how those will work yet.}
295
296 \subsection{Retype}
297
298 Retyping a capability creates one or more descendants of the
299 capability. This operation will fail if the capability already has
300 descendants. The descendants are inserted into a CNode specified by
301 the operation and into the mapping database right after the retyped
302 capability.
303
304 When a dispatcher issues the retype invocation, the kernel must traverse the
305 mapping database to ensure that the capability has no descendants, create the
306 descendants capabilities, insert them in the specified CNode and in the mapping
307 database.
308
309 \subsection{Copy}
310
311 Copying a capability creates a new copy of it. The kernel walks the capability
312 space to find the capability to be copied, creates the copy, and inserts it
313 into the specified CNode and mapping database.
314
315 \subsection{Delete}
316
317 Delete removes the specified capability from the CNode in which it
318 resides and from the mapping database. This operation cannot fail.
319
320 The kernel first walks the capability space to locate the capability
321 to delete. It then walks the mapping database to check if there still
322 exist copies of the deleted capability. If no copies are found, then
323 it performs certain operations based on the capability type.
324
325 \subsection{Revoke}
326
327 Revoking a capability calls delete on all copies and descendants of
328 it. When the operation returns, the capability will not have any
329 copies or descendants.
330
331 The kernel walks the capability space to find the specified
332 capability, uses the mapping database to find all copies and
333 descendants of the specified capability and deletes them.
334
335 \subsection{Looking up local copies and descendants}
336
337 Due to the capability ordering used by the mapping database, copies are located
338 adjacant to a capabality and descendants immediately thereafter. Therefore, it
339 is easy to look up all related copies of a capability on the same core. This
340 facilitates revocation by looking up all copies and descendants, retypes by
341 checking for existing descendants, and deltes by checking for copies.
342
343 The following pseudo-code looks up all descendants and copies of a
344 capability given the existence of type specific is\_copy and
345 is\_descendant functions.
346
347 {\scriptsize
348 \begin{verbatim}
349   // Traverse forward
350   mdbnode *walk = successor(cap);
351   while (walk) {
352     // Check if descendant
353     if (is_descendant(cap, walk)) {
354       // Found a descendant
355       goto increment;
356     }
357
358     // Check if copy
359     if (is_copy(cap, walk)) {
360       // Found a copy
361       goto increment;
362     }
363
364     // Cap is not a descendant or copy
365     break;
366
367   increment:
368     walk = successor(walk);
369   }
370
371   // Traverse backwards
372   mdbnode *walk = predecessor(cap);
373   while (walk) {
374     // Predecessors cannot be descendants
375
376     // Check if copy
377     if (is_copy(cap, walk)) {
378       // Found a copy
379       goto increment;
380     }
381
382     // Cap is not a copy
383     break;
384
385   increment:
386     walk = predecessor(walk);
387   }
388 }
389 \end{verbatim}
390 }
391
392 \section{Multicore extensions}
393
394 The model above only works for a single core system. We have already
395 extended it to work on multiple cores. Here we discuss these
396 extensions.
397
398 \subsection{Cross-core transfer}
399
400 This is a special operation available only to the monitors. This sends
401 a capability from one core to another.
402
403 \subsection{Missing operations}
404
405 When a capability is sent to another core, no state is maintained
406 about it. When checking for capability relations in capability
407 operations, only the current core is checked. Therefore these
408 operations are not implemented correctly right now.
409
410 \section{Summary}
411
412 In this chapter, we presented a background and the current state of
413 capabilities management in Barrelfish. We can now discuss different
414 designs for multicore capability management.
415
416
417 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
418
419 \chapter{Maintaining the database}\label{chap:db}
420 We consider the following approaches for managing the mapping
421 database.
422
423 \note{Use diagrams to better illustrate the discussion below.}
424
425 \begin{itemize}
426 \item \textbf{No partition:} The mapping database and capability space
427   for all cores is maintained on a single centralized
428   coordinator. Accessing either the capability space or the mapping
429   database on any core requires communication with the coordinator.
430
431 \item \textbf{Partitioned data structure:} The mapping database for
432   all cores is maintained on a single centralized coordinator and the
433   capability space is maintained on the local cores. This implies that
434   the cte structure is split between the coordinator and the local
435   cores. Cores can access the capability space locally and have to
436   message the coordinator to access the mapping database. Note that
437   split ``capability'' and ``mdbnode'' structures need to maintain
438   references to each other.
439
440 \item \textbf{Centrally replicated space:} The mapping database and
441   the capability space is replicated between a single coordinator and
442   the local cores. This implies that two copies of each ``cte''
443   structure exist in the system, one on the local core and one on the
444   coordinator. Both local core and the coordinator can access the
445   mapping database and the capability space.
446
447 \item \textbf{Partitioned space:} The mapping database and the
448   capability space are maintained on the local cores. The entire
449   ``cte'' structure can be accessed locally but capability operations
450   will require coordination and communication with remote cores.
451
452 \item \textbf{Minimal replication:} The database is partitioned
453   between local cores as in the above approach and additionally for
454   each capability the cores maintain a cache of its remote relations.
455   This is discussed in more detail in section \ref{sec:cache}.
456 \end{itemize}
457
458 We qualitatively compare the above approaches and why the partitioned
459 space and minimal replication is the best.
460
461 \section{Comparison}\label{sec:comparison}
462 We compare the above approaches in this section.
463
464 \subsection{Efficiency of capability invocations}
465 When a dispatcher invokes a capability, the kernel has to look it up
466 in the capability space starting from the dispatcher's ``root'' CNode.
467 If the capability space is not local, then the core has to message the
468 coordinator to perform the look up. A round trip with the coordinator
469 is more expensive than a local look up and can become a scalability
470 bottleneck if we use a single coordinator.
471
472 The no partition approach does not maintain a local capability space
473 and therefore may suffer from poor performance. All other approaches
474 maintain the capability space locally.
475
476 \subsection{Local operations}
477 Approaches that enable more pure local operations will perform better
478 as they will reduce the amount of cross-core communication. In the no
479 partition, partitioned data structure, and replicated space
480 approaches, no operation can be performed locally. In the partitioned
481 and minimal replication approaches, certain operations such as copying
482 capabilities is purely local.
483
484 \begin{table*}
485 \begin{center}
486 \begin{tabular}{|c|c|c|c|c|c|}
487   \hline
488
489   & Cap invocation & Local operations \\
490   \hline
491
492   No partition                & - & -   \\ \hline
493   Partitioned data structure  & + & -   \\ \hline
494   Centrally replicated space  & + & -   \\ \hline
495   Partitioned space           & + & +   \\ \hline
496   Minimal replication         & + & +   \\ \hline
497
498 \end{tabular}
499 \end{center}
500 \caption{\label{t:summary}Summary of the different approaches.}
501 \end{table*}
502
503 \subsection{Discussion}
504 Table \ref{t:summary} summarizes our comparison of the five
505 approaches. A (+) indicates that the approach performs relatively well
506 on the given metric and a (-) indicates that the approach performs
507 relatively poorly. Based on the results, we choose to implement the
508 partitioned space and minimal replication approaches.
509
510 \section{Caching}\label{sec:cache}
511 The minimal replication approach is characterized as the partitioned
512 approach with caching the state of remote relations. Capabilities
513 without remote relations are marked as such and when performing
514 operations on these no remote communication is required.
515
516 When tracking remote relations, three types of relations must be
517 tracked: copies, descendants, and ancestors. Tracking of remote copies
518 and descendants is required so that revoke, retype, and delete
519 operations can be correctly implemented. And capabilities must track
520 their remote ancestors so if they are deleted, the remote ancestors
521 can be informed to update the state about their remote descendants.
522
523 \subsection{How to maintain the cache?}
524
525 \note{Once I discuss total order broadcast with caching, this
526   discussion will be revamped.}
527
528 There are two ways of maintaining the cache:
529 \begin{itemize}
530 \item \textbf{Single bit:} A bit each for the three types of remote
531   relations is used. The bits merely indicate the presence of remote
532   relations but provide no further information such as which cores
533   have the remote relations.
534
535 \item \textbf{List:} A list each for the three types of remote
536   relations is used. The list contains exact information about which
537   cores the remote relations exist on. Uhlig et al [?]'s core mask
538   technique can be used to maintain the lists with fixed space
539   requirement.
540 \end{itemize}
541
542 \subsubsection{Comparison}
543 \textbf{Informing existing relations:} When a capability that already
544 has remote relations is sent to another core, with the single-bit
545 approach, none of the existing cores with relations have to be
546 informed, but with the list approach, cores with existing relations
547 must be informed so they can update their lists.
548
549 With both approaches when the last local copy of a capability is
550 deleted, its remote relations should be informed. This is required in
551 the list approach so that the cores can update their list and is
552 required in the single-bit approach so that the cores can determine if
553 the last remote relation has been deleted and it can mark the
554 capability as not having the remote relation anymore.
555
556 \textbf{Number of cores communicated:} With the single bit approach,
557 all cores in the system must be contacted, while with the list
558 approach, just the cores of interest must be contacted.
559
560 \textbf{Discussion:} The single-bit approach will probably be more
561 efficient if the system has few cores and the capabilities that have
562 remote relations, tend to have them on many cores. The list approach
563 will have better performance if there are lots of cores in the system
564 and typically a capability only has relations on a few cores.
565
566 \subsection{Where to maintain the cache?}\label{subsec:where}
567 Imagine that there exists a capability with only local relations. Then
568 cross-core transfer it applied to it. Should we only mark that
569 capability as having a remote copy or should we mark all impacted
570 capabilities accordingly? This section will discuss and compare these
571 two approaches.
572
573 \subsubsection{Mark all}
574 When cross-core transfer is applied to a capability, it is marked has
575 having remote copies and all its local relations are also marked as
576 having the appropriate remote relations. Its local copies will be
577 marked as having remote copies, its local descendants will be marked
578 as having remote ancestors, and its local ancestors will be marked as
579 having remote descendants.
580
581 All capabilities maintain complete state of their remote relations at
582 all times.
583
584 \subsubsection{Mark just individual capability}
585 When cross-core transfer is applied to a capability, it is marked has
586 having remote copies and none of its local relations are updated.
587
588 Capabilities do not maintain the complete state of their remote
589 relations. Their local relations must be looked up to build the
590 complete state of their remote relations.
591
592 \subsubsection{Comparison}
593 Both approaches have their specific strengths and weaknesses discussed
594 here.
595
596 \textbf{Cost of cross-core transferring:} When applying cross-core
597 transfer to a capability, in the mark all approach, all local
598 relations must be updated whereas in the mark just individual
599 capability approach, the local relations do not have to be updated.
600 However, the cross-core transfer operation needs to send full
601 information about the state of local relations so that the newly
602 created remote capability can setup its cache properly. Gathering this
603 information will require accessing all local relations so the mark all
604 approach represents a small in the operation that must be performed
605 anyways.
606
607 \textbf{Cost of building state of remote relations:} Any capability
608 operation that requires information on the current state of remote
609 relations will have to build the full state of remote relations for
610 the capability. This is done trivially in the mark all approach as
611 each capability maintains the full state. In the mark just individual
612 capability approach, all local relations must be accessed to build the
613 state.
614
615 \textbf{Discussion:} Given that the state of remote relations is
616 trivially constructed in the mark all approach and the cost of
617 cross-core transfer is only marginally higher than the bare minimum
618 cost already required, we conclude that the mark all approach is
619 superior to the mark just individual capability approach.
620
621 \subsection{Summary}\label{subsec:cache:summary}
622 In summary, we have come up with two approaches for the type of cache:
623 single-bit and list, and we have concluded that the mark all approach
624 is superior for maintaining the cache.
625
626 Maintaining a cache will require the following adjustment to the
627 capability operations presented above.
628
629 \begin{itemize}
630 \item When cross-core transfer is applied to a capability, it is
631   marked as having remote copies. The operation sends information on
632   the state of the capability's local and remote relations.
633
634 \item When a capability is created due to the cross-core receive
635   operation, it incorporates the information about relations sent with
636   the cross-core transfer operation.
637
638 \item When a copy of a capability is marked as having remote
639   relations, the capability is marked as having the same remote
640   relations.
641
642 \item When a descendant of a capability is marked as having remote
643   relations, the capability is marked also marked as having remote
644   relations based on the following rules:
645   \begin{itemize}
646   \item If the descendant has a remote copy, then capability has a
647     remote descendant.
648   \item If the descendant has a remote descendant, then capability has
649     a remote descendant.
650   \item If the descendant has a remote ancestor, then capability
651     either has a remote copy or an ancestor depending on the outcome
652     from the type-specific is\_descendant function.
653   \end{itemize}
654
655 \item When an ancestor of a capability is marked as having remote
656   relations, the capability is marked also marked as having remote
657   relations based on the following rules:
658   \begin{itemize}
659   \item If the ancestor has a remote copy, then capability has a
660     remote ancestors.
661   \item If the ancestor has a remote descendant, then capability
662     either has a remote copy or a remote descendant depending on the
663     outcome from the type-specific is\_descendant function.
664   \item If the ancestor has a remote ancestor, then capability
665     has remote ancestors.
666   \end{itemize}
667
668 \item When a capability is retyped:
669   \begin{itemize}
670   \item Its remote copies are marked as having remote descendants
671   \item The descendants are marked as having remote ancestors if the
672     capability has remote copies.
673   \end{itemize}
674
675 \item When a capability is copied, the copy is marked as having the
676   same remote relations that the capability has.
677
678 \item When the last copy of a capability on the core is deleted, its
679   remote copies, descendants, ancestors are informed.
680 \end{itemize}
681
682 We now discuss some implications of maintaining a cache.
683
684 \textbf{Drawbacks:} Caching introduces the following drawbacks that
685 the non-caching approach does not suffer from.
686
687 \begin{itemize}
688 \item The application dispatchers must first try to perform the
689   capability operations locally and if that fails, then communicate
690   with the monitors. If no caching were used, the application
691   dispatchers can always directly communicate with the monitor saving
692   one superfluous trip into the kernel.
693
694 \item As discussed above, caching requires additional overhead in
695   keeping the cache consistent.
696
697 \item Caching increases the space requirement for maintaining the
698   mapping database.
699 \end{itemize}
700
701 Caching can work if typically few capabilities are shared between
702 cores and can hurt if many capabilities are shared.
703
704 \textbf{Decide dynamically:} It is clear that application scenarios
705 will actually dictate if caching can help and if it does, which type
706 of caching helps. To support this, Barrelfish can allow applications
707 to specify which type of caching is well suited for it or the OS can
708 gather appropriate metrics on application execution and based on that
709 dynamically update the type of caching used.  For this, we need to
710 identify the cross-over point where one approach is preferred over the
711 other.
712
713 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
714
715 \chapter{Solutions}\label{chap:solutions}
716 In this chapter, we discuss mechanisms for implementing the capability
717 operations. In section \ref{sec:challenges}, we will first discuss the
718 challenges in correctly implementing the operations by discussing how
719 executing multiple related operations in parallel can lead to
720 conflicts and by discussing how an intuitive solution of using
721 acknowledgments fails to resolve the conflicts. We then present the
722 requirements from a correct solution in section \ref{sec:requirements}
723 and compare four different correct solution in section
724 \ref{sec:solutions}.
725
726 \section{Challenges}\label{sec:challenges}
727 We first discuss the conflicts that can arise if two or more related
728 operations execute in parallel and then discuss an intuitive but
729 incorrect solution of using acknowledgments to resolve the conflicts.
730
731 \subsection{Conflicts}\label{subsec:conflicts}
732 Performing overlapping operations on related capability can lead to
733 conflicts. This section discusses the different types of conflicts
734 that can arise.
735
736 \textbf{Conflicts between two retypes, deletes, or revokes:} If two
737 different cores are trying to retype, delete, or revoke related
738 capabilities, then they can conflict. If two different cores try to
739 retype two copies of a capability, the correct behavior is for one to
740 succeed and for one to fail. If two cores try to delete the last two
741 copies of a capability, the correct behavior is for one to just delete
742 locally and for the other to perform type-specific operations required
743 when deleting the last copy of a capability. If two cores try to
744 revoke the same capability, one should succeed, the other should fail
745 and the capability it was trying to revoke should also be deleted.
746
747 \textbf{Conflict between revoke and cross-core transfer:} If a core is
748 trying to revoke a capability, a copy or descendant of which another
749 core is trying to transfer, the revoke operation should only finish
750 when the in-flight capability is also deleted.
751
752 \textbf{Conflict between revoke and retype:} If a core is trying to
753 revoke a capability, a copy or descendant of which another core is
754 trying to retype, then the retype should either succeed and the new
755 capabilities be deleted before revoke finishes or the retype should
756 fail.
757
758 \subsection{Non-conflicts}
759 This section discusses why it is safe to perform other operations in
760 parallel.
761
762 \textbf{Delete and revoke:} Delete at least deletes one capability and
763 potentially more. If a revoke for a related capability is issued at
764 the same time, they will overlap and potentially try to perform
765 redundant operations but these are safe.
766
767 \textbf{Delete and transfer:} Delete will delete one capability and
768 perform a check for copies. The in-flight capability already has a
769 copy that can satisfy the requirements of delete. If the capability is
770 also being deleted, it is the same two deletes overlapping which
771 indeed is a conflict.
772
773 \textbf{Retype and delete:} A delete will not conflict with retypes
774 because it checks for the existence of copies which a successful
775 retype cannot possibly create. A retype will not conflict with deletes
776 because no matter when it performs the check for descendants, it will
777 either see descendants that are about to be deleted or not see them at
778 all, either of the outcomes is correct.
779
780 \textbf{Retype and transfer:} Retype cannot conflict with transfers
781 because in order to transfer a capability because the capability being
782 transferred is a copy of an existing capability which does not change
783 the existing descendants relationships.
784
785 \subsection{Incorrect solution}
786 Since the essential issue with the relation with cross-core transfer
787 operation is that in-flight capabilities do not exist anywhere, the
788 sending core can maintain a list of in-flight capabilities which are
789 garbage collected when the receiver acknowledges the reception of the
790 capability. This allows the sending core to include the in-flight
791 capabilities in the search for copies and descendants. As shown below,
792 this intuitive solution is actually incorrect.
793
794 \begin{figure}[t]
795  \includegraphics[width=0.75\textwidth]{acks-problem.pdf}
796  \caption{Problem with using acknowledments}\label{fig:acks-problem}
797 \end{figure}
798
799 Consider the scenario shown in figure \ref{fig:acks-problem}. The
800 system consists of three cores \{A, B, C\}, A is trying to revoke a
801 capability and B is trying to send a copy of the capability to C. A
802 sends a revoke request to B, C and waits for their acknowledgments. B
803 sends the capability to C and adds it to its list of in-flight
804 capabilities. C sees the revoke request first, performs the operation
805 locally and replies to A. Then it sees the capability sent from B,
806 inserts it locally and send an acknowledgment to B. B sees the
807 acknowledgment from C first garbage collecting its list of in-flight
808 capabilities and then sees the revoke request from A, performs the
809 revoke locally, and replies to A. A receives replies from both B and C
810 concluding the revoke operation. The revoke operation has finished and
811 C still has a copy of the revoked capability.
812
813 \section{Requirements from a correct solution}\label{sec:requirements}
814 A correct solution will enforce the following transactional like and
815 ordering properties.
816
817 \subsection{Transactional properties}
818 \textbf{Atomic:} If one part of a capability operation fails, then the
819 entire operation must fail. For example, in a retype operation, the
820 descendant capabilities can be created in parallel with the check for
821 existing descendants. If existing descendants are found, then the
822 newly created descendants must be removed.
823
824 \textbf{Consistent:} Every capability operation must leave the system
825 in a consistent state. For example, if caching is used an operation
826 deletes the last copy of a capability on a core, then all its remote
827 relations should be informed and updated before the operation
828 finishes.
829
830 \textbf{Isolation:} The data that has been modified during a
831 capability operation must not be accessible by other operations till
832 the operation finishes. For example, if a retype operation has eagerly
833 created descendants while checking for existing descendants in
834 parallel, no other capability operation should be able to access the
835 descendants created eagerly till the retype operation finishes.
836
837 \subsection{Ordering}
838 Section \ref{subsec:conflicts} discusses the two types of conflicts
839 that can arise when multiple cores try to perform operations on
840 related capabilities at the time. Correctness can be ensured if the
841 individual steps (messages) in operations must be executed in some
842 order.  We provide some background on ordering messages before
843 discussing the actual ordering requirements.
844
845 \textbf{Background on ordering:} Four types of ordering are
846 possible. We discuss them from the cheapest to the most expensive.
847
848 \begin{itemize}
849 \item No order: Messages can be delivered in any order. This cannot
850   happen on Barrelfish.
851 \item Single Source FIFO (SSF): Messages from the same sender are
852   delivered in the order they were sent. This is what currently is
853   available on Barrelfish by default.
854 \item Causal: Messages are delivered based on their partial order
855   given by the happens-before relationship. Vector clocks [?] can be
856   used to provide causal delivery of messages.
857 \item Total order: All receivers receive messages in the same
858   order. Note that any ordering function can be used to order the
859   messages. Further, total order does not imply causal order but if
860   the ordering function respects SSF, then total order does imply
861   causal order.
862 \end{itemize}
863
864 \subsection{Conflicts with each-other}
865
866 \begin{figure}[t]
867  \includegraphics[width=0.75\textwidth]{causal-problem.pdf}
868  \caption{Problem with using causal order
869    delivery}\label{fig:causal-problem}
870 \end{figure}
871
872 The minimum ordering required for resolving conflicts between retype,
873 delete, and revoke operations is total order. Figure
874 \ref{fig:causal-problem} illustrates the reason causal ordering does
875 not work. Nodes \{A,B,C,D\} each contain copies of the same capability
876 that \{A,D\} wish to retype at the same time. B receives the message
877 from A before the message from D, and C receives the D's message
878 before A's. The messages were delivered in causal order, C will refuse
879 to A, B will refuse to D not allowing either retype operation to
880 succeed. Similar examples can be constructed for the delete and revoke
881 operations as well.
882
883 Total order delivery will deliver the messages to B and C in the same
884 order allowing just one and only one retype to succeed.
885
886 \subsection{Conflict between revoke and transfer}
887 Figure \ref{fig:acks-problem} illustrates the conflict between revoke
888 and cross-core transfer operation. C sees the message from A before
889 the message from B. Hence any message it sends to B causally depend
890 upon the message from A. If this was reflected in the message C sent
891 to B, then B could delay handling the message till it sees the revoke
892 request from A. When B receives the revoke request from A, it will
893 realize that A is trying to revoke an in-flight capability and take
894 appropriate actions to resolve the issue. The delaying of the message
895 can be guaranteed by enforcing causal delivery of messages.
896
897 \subsection{Conflict between revoke and retype}
898 The minimum ordering requirement is total. With less stricter
899 ordering, different cores might see the revoke request and retype
900 requests in different orders. The retyping core might delete the
901 source capability but end up creating descendants later.
902
903 \section{Solutions}\label{sec:solutions}
904
905 We will discuss and compare the following four solutions.
906
907 \begin{itemize}
908 \item Locks
909 \item Total order broadcast
910 \item Two phase commit
911 \item Sequencer
912 \end{itemize}
913
914 \subsection{Locks}\label{subsec:locks}
915 Locks can be used to enforce the above transactional and ordering
916 policies. Critical sections can be used to resolve the conflicts
917 ensuring that \emph{Time-of-check-to-time-of-use} is not violated.
918
919 Below, we provide pseudo-code for how capability operations will be
920 implemented when using a centralized lock and not caching information
921 about remote relations.
922
923 \textbf{Copying a capability:} This operation is safe to be performed
924 without holding a lock.
925
926 \begin{verbatim}
927 cap_copy(struct cte *cte) {
928   create_copies();
929 }
930 \end{verbatim}
931
932 \textbf{Retyping a capability:} Holding the lock is required to
933 prevent multiple cores from trying to retype copies of the same
934 capability. Acquiring the lock is a blocking call during which the
935 capability might have been deleted so it is important to check that
936 the capability still exists after the lock is acquired.
937
938 \begin{verbatim}
939 cap_retype(struct cte *cte) {
940   errval_t err = success;
941   acquire_lock();
942   if (cap_exists(cte) == false) {
943     err = fail;
944     goto done;
945   }
946   if (has_descendants(cte) == true) {
947     err = fail;
948     goto done;
949   }
950   create_descendants(cte);
951 done:
952   release_lock();
953   return err;
954 }
955 \end{verbatim}
956
957 \textbf{Deleting a capability:} If the capability has local copies,
958 the operation is purely local. Otherwise, holding the lock is required
959 to ensure that if the last copy of the capability in the system is
960 being deleted, then the type-specific cleanup operations are executed.
961
962 \begin{verbatim}
963 cap_delete(struct cte *cte) {
964   remove_cap(cte);
965
966   if (!requires_typed_ops(cte)) {
967     return success;
968   }
969   if (has_local_copies(cte)) {
970     return success;
971   }
972
973   errval_t err = success;
974   acquire_lock();
975   if (!cap_exists(cte) {
976     goto done;
977   }
978
979   if (!has_copies(cte) {
980     type_specific_ops(cte);
981   }
982
983 done:
984   release_lock();
985   return err;
986 }
987 \end{verbatim}
988
989 \textbf{Revoking a capability:} Holding the lock is required to ensure
990 that if multiple cores are trying to revoke related capabilities, only
991 one succeeds. This is why the code below ensures that the capability
992 still exists after acquiring the lock.
993
994 \begin{verbatim}
995 cap_revoke(struct cte *cte) {
996   errval_t err = success;
997   acquire_lock();
998   if (!cap_exists(cte) {
999     err = fail;
1000     goto done;
1001   }
1002
1003   while(has_descendants(cte) {
1004     struct cte *dest = get_next_descendant(cte);
1005     remove_cap(dest);
1006   }
1007   while(has_copies(cte) {
1008     struct cte *dest = get_next_copy(cte);
1009     remove_cap(dest);
1010   }
1011
1012 done:
1013   release_lock();
1014   return err;
1015 }
1016 \end{verbatim}
1017
1018 \textbf{Cross-core transferring a capability:} Holding the lock is
1019 required to conflicts between the above capability operations and
1020 cross-core transfer operation. The sender acquires the lock and sends
1021 the capability. The receiver creates the capability and releases the
1022 lock.
1023
1024 \begin{verbatim}
1025 cap_send(struct cte *cte, coreid_t dest) {
1026   acquire_lock();
1027   if (cap_exists(cte) == false) {
1028     return fail;
1029   }
1030   send_cap(cte, dest);
1031 }
1032
1033 cap_receive(struct cte *cte) {
1034   create_cap(cte);
1035   release_lock();
1036   return_success_to_app();
1037 }
1038 \end{verbatim}
1039
1040 \subsubsection{Caching remote relations}
1041 If remote relations are cached, then the cache has to be kept
1042 consistent when capability operations change the state of
1043 relations. Below we describe the modifications that will be required
1044 in the above pseudo-code to keep the cache consistent. Note that our
1045 cache can be seen as eager replication. As discussed in section
1046 \ref{subsec:where}, we will be using the mark all approach to maintain
1047 the cache.
1048
1049 \textbf{Copying a capability:} When the new copy is created, its cache
1050 of remote relations is set equal to the cache from the capability it
1051 was copied from.
1052
1053 \textbf{Retyping a capability:} If the capability does not have remote
1054 copies and descendants, the operation is purely local and the lock is
1055 not required. If the operation is not local, then the lock is
1056 acquired, checks for existence of capability and for descendants and
1057 is made, the capability is retyped, and remote relations are updated
1058 based on the rules presented in section \ref{subsec:cache:summary}.
1059
1060 \begin{verbatim}
1061 cap_retype(struct cte *cte) {
1062   if (has_local_descendants(cte) == true) {
1063     return fail;
1064   }
1065
1066   if (!has_remote_copies(cte) && !has_remote_descendants(cte)) {
1067     create_descendants(cte);
1068     return success;
1069   }
1070
1071   if (has_remote_descendants(cte)) {
1072     return fail;
1073   }
1074
1075   errval_t err = success;
1076   acquire_lock();
1077   if (!cap_exists(cte)) {
1078     err = fail;
1079     goto done;
1080   }
1081
1082   if (has_remote_descendants(cte)) {
1083     err = fail;
1084     goto done;
1085   }
1086   if (has_local_descendants(cte)) {
1087     err = fail;
1088     goto done;
1089   }
1090
1091   create_descendants(cte);
1092   update_relations(cte);
1093
1094 done:
1095   release_lock();
1096   return err;
1097 }
1098 \end{verbatim}
1099
1100 \textbf{Deleting a capability:} If the capability has local copies or
1101 no remote relations, the operation is purely local. Otherwise, the
1102 lock is required and the remote relations must be updated.
1103
1104 \begin{verbatim}
1105 cap_delete(struct cte *cte) {
1106   remove_cap(cte);
1107
1108   if (!requires_typed_ops(cte)) {
1109     return success;
1110   }
1111   if (has_local_copies(cte)) {
1112     return success;
1113   }
1114
1115   if (!has_remote_relations(cte)) {
1116     type_specific_ops(cte);
1117     return success;
1118   }
1119
1120   acquire_lock();
1121   if (!cap_exists(cte)) {
1122     goto done;
1123   }
1124   if (!has_copies(cte) {
1125     type_specific_ops(cte);
1126   }
1127   update_remote_relations(cte);
1128   remove_cap(cte);
1129   release_lock();
1130 done:
1131   return success;
1132 }
1133 \end{verbatim}
1134
1135 \textbf{Revoking a capability:} If the capability has no remote
1136 relations, the operation is purely local. Otherwise, the lock is
1137 required.
1138
1139 \begin{verbatim}
1140 cap_revoke(struct cte *cte) {
1141   if (!has_remote_relations(cte)) {
1142     while(has_descendants(cte) == true) {
1143       struct cte *dest = get_next_descendant(cte);
1144       remove_cap(dest);
1145     }
1146     while(has_copies(cte) == true) {
1147       struct cte *dest = get_next_copy(cte);
1148       remove_cap(dest);
1149     }
1150     return success;
1151   }
1152
1153   errval_t err = success;
1154   acquire_lock();
1155   if (!cap_exists(cte)) {
1156     err = fail;
1157     goto done;
1158   }
1159
1160   while(has_descendants(cte) == true) {
1161     struct cte *dest = get_next_descendant(cte);
1162     remote_cap(dest);
1163   }
1164   while(has_copies(cte) == true) {
1165     struct cte *dest = get_next_copy(cte);
1166     remote_cap(dest);
1167   }
1168   release_lock();
1169 done:
1170   return err;
1171 }
1172 \end{verbatim}
1173
1174 \textbf{Cross-core transferring a capability:} The remote relations
1175 cache on local and remote capabilities is updated as presented in
1176 section \ref{subsec:cache:summary}.
1177
1178 \subsubsection{Multiple locks}
1179 \note{NYI}
1180 If a single lock for the entire system is used, only one capability
1181 operation can be performed at any given moment limiting the available
1182 potential for parallelism. By using different locks for unrelated
1183 capabilities, multiple capability operations can proceed in
1184 parallel. Using multiple locks will increase the space requirement but
1185 will also improve parallelism.
1186
1187 \note{Multiple locks are not straight-forward. Ancestors reference
1188   more memory than descendants do.}
1189
1190 \note{Can a copy lock for delete, a descendant lock for retype, and
1191   both for revoke work?}
1192
1193 \subsection{Total order broadcast}
1194 \note{Use a single data structure for all pending cap operations.}
1195
1196 The required transactional and ordering guarantees can be provided by
1197 ensuring that messages for related capabilities are delivered in the
1198 same order on all cores. Note that causal order delivery resolves the
1199 conflict between retype, delete, revoke and cross-core transfer
1200 operation but not within the retype, delete, revoke operations.
1201
1202 Below we present pseudo-code for how the capability operations will be
1203 implemented when not caching information about remote relations.
1204
1205 \textbf{Copying a capability:} This operation is safe to be performed
1206 without any ordering requirements.
1207
1208 \textbf{Deleting a capability:} If the capability does not require
1209 type-specific operations or has local copies, the operation succeeds.
1210 Or else, local state is created and a message is broadcast to all
1211 cores.
1212
1213 \begin{verbatim}
1214 cap_delete(struct cte *cte) {
1215   if (!requires_typed_ops(cte) || has_local_copies(cte)) {
1216     remove_cap(data->cte);
1217     return success;
1218   }
1219
1220   struct delete_data *data = malloc(sizeof(struct delete_data));
1221   delete_data_initialize(data, cte);
1222   outstanding_delete_list->add(data);
1223   send_delete_request_bcast(TOTAL_ORDER, data);
1224 }
1225 \end{verbatim}
1226
1227 If a core receives a delete request broadcast and it was the sender of
1228 the message, it removes the capability and returns. If the core was
1229 not the sender of the message, then it replies with the state of local
1230 copies of the specified capability.
1231
1232 \begin{verbatim}
1233 delete_request_bcast(coreid_t from, struct delete_request *data) {
1234   if (from == my_core_id) {
1235     remove_cap(data->cte);
1236     return;
1237   }
1238
1239   send_delete_reply(from, data, has_local_copies(data->cte));
1240 }
1241 \end{verbatim}
1242
1243 Finally, when a core receives a reply from a delete request, if a
1244 remote copy is found, no type-specific cleanup is required and the
1245 operation finishes. If all replies have been aggregated and no copies
1246 were found, then the type-specific cleanups are performed and then the
1247 operation finishes.
1248
1249 \begin{verbatim}
1250 delete_reply(coreid_t from, bool has_copies) {
1251   struct cte *my_data = outstanding_deletes_list->get(data);
1252   if (!my_data) {
1253     return;
1254   }
1255
1256   if (has_copies) {
1257     outstanding_deletes_list->remove(my_data);
1258     return;
1259   }
1260
1261   increment_replies(my_data);
1262   if (seen_all_replies(my_data)) {
1263     type_specific_ops(cte);
1264     outstanding_deletes_list->remove(my_data);
1265   }
1266 }
1267 \end{verbatim}
1268
1269 Since the deleting cores remove the capability when they receive the
1270 broadcast, when multiple cores are trying to delete copies, the last
1271 core's broadcast will see no copies while other cores will see copies.
1272
1273 \note{Malloc probably means unbounded memory requirement.}
1274
1275 \textbf{Retyping a capability:} If the capability has local
1276 descendants, then the operation fails. Else, a retype request
1277 broadcast is sent.
1278
1279 \begin{verbatim}
1280 cap_retype(struct cte *cte) {
1281   if (has_local_descendants(cte)) {
1282     return fail;
1283   }
1284
1285   struct retype_data *data = malloc(sizeof(struct retype_data));
1286   retype_data_initialize(data, cte);
1287   outstanding_retypes_list->add(data);
1288   send_retype_request_bcast(data);
1289 }
1290 \end{verbatim}
1291
1292 When a core receives a retype request broadcast and it was the sender
1293 of the message, one of two things may have happened. Either the core
1294 had already received a broadcast from another core trying to retype
1295 the same capability in which case the receiver's operation has failed
1296 and the state for the request has been removed or the core can succeed
1297 in retyping the capability and updates its state accordingly. If the
1298 core was not the sender of the broadcast, it sends a reply to the
1299 sender with the state of its local descendants. Then the core checks
1300 if it has an outstanding retype request for the capability. If it does
1301 and its request has not been delivered yet, its retype fails. An error
1302 is sent to the application and the state is garbage collected.
1303
1304 \begin{verbatim}
1305 retype_request_bcast(coreid_t from, struct retype_request *data) {
1306   if (from == my_core_id) {
1307     struct cte *my_data = outstanding_retypes_list->get(data);
1308     if (!my_data) {
1309       return;
1310     }
1311     my_data->can_succeed_flag = true;
1312     return;
1313   }
1314
1315   send_retype_reply(from, data, has_local_descendants(data->cte));
1316   struct cte *my_data = outstanding_retypes_list->get(data);
1317   if (!my_data) {
1318     return;
1319   }
1320
1321   if (!my_data->success_flag) {
1322     outstanding_retypes_list->remove(my_data);
1323     return_failure_to_app();
1324   }
1325 }
1326 \end{verbatim}
1327
1328 When a core receives a reply to the retype request broadcast, the
1329 operation may already have been failed, in which case the reply is
1330 ignored. If the operation has not been canceled yet, then if the reply
1331 indicates no descendants, the operation can still succeed. If all
1332 replies are seen then the retype operation succeeds.
1333
1334 \begin{verbatim}
1335 retype_reply(struct retype_request *data, bool has_descendants) {
1336   struct cte *my_data = outstanding_retypes_list->get(data);
1337   if (!my_data) {
1338     return;
1339   }
1340
1341   if (has_descendants) {
1342     outstanding_retypes_list->remove(my_data);
1343     return_failure_to_app();
1344     return;
1345   }
1346
1347   increment_replies(my_data);
1348   if (seen_all_replies(my_data)) {
1349     create_descendants();
1350     outstanding_retypes_list->remove(my_data);
1351     return_success_to_app();
1352   }
1353 }
1354 \end{verbatim}
1355
1356 This resolves the conflicts between two retypes. The conflict between
1357 retype and revoke are discussed below.
1358
1359 \note{Malloc probably means unbounded memory requirement.}
1360
1361 \textbf{Revoking a capability:} The core initializes some local state
1362 and then broadcasts a revoke request to all cores in the system.
1363
1364 \begin{verbatim}
1365 cap_revoke(struct cte *cte) {
1366   struct revoke_data *data = malloc(sizeof(struct revoke_data));
1367   revoke_data_initialize(data, cte);
1368   outstanding_revokes_list->add(data);
1369   send_revoke_request_bcast(TOTAL_ORDER, data);
1370 }
1371 \end{verbatim}
1372
1373 When a core receives a revoke request broadcast, if the core was
1374 trying to retype a related capability, then it fails the retype
1375 operation. If it is not trying to revoke the capability itself, it
1376 simply revokes the capability locally and sends a reply. If the core
1377 is trying to revoke the same capability but it was not the sender of
1378 the broadcast, then this core's revoke operation fails.
1379
1380 \begin{verbatim}
1381 revoke_request_bcast(coreid_t from, struct revoke_request *data) {
1382
1383   if (related_retype_in_progress(data->cte)) {
1384     outstanding_retypes_list->remove(data);
1385     return_fail_to_app();
1386   }
1387
1388   struct cte *my_data = outstanding_revokes_list->get(data);
1389   if (!my_data) {
1390     revoke_locally(data->cte);
1391     send_revoke_reply(from, data);
1392     return;
1393   }
1394
1395   if (from != my_core_id && !my_data->success_flag) {
1396     outstanding_revokes_list->remove(my_data);
1397     send_revoke_reply(from, data);
1398     return_failure_to_app();
1399     return;
1400   }
1401
1402   my_data->success_flag = true;
1403 }
1404 \end{verbatim}
1405
1406 When a core receives a reply from the broadcast, it aggregates them
1407 till it has heard back from all cores in the system and then sends a
1408 success to the application.
1409
1410 \begin{verbatim}
1411 revoke_reply(struct revoke_request *data) {
1412   struct cte *my_data = outstanding_revokes_list->get(data);
1413   if (!my_data) {
1414     return;
1415   }
1416
1417   increment_replies(my_data);
1418   if (seen_all_replies(my_data) && !my_data->sent_transfer_cap_delete_flag) {
1419     outstanding_revokes_list->remove(my_data);
1420     return_success_to_app();
1421   }
1422 }
1423 \end{verbatim}
1424
1425 \textbf{cross core transfer:} When sending a capability to another
1426 core, the sending core creates local states and broadcasts the send
1427 message to all cores in the system.
1428
1429 \begin{verbatim}
1430 cap_transfer(struct cte *cte, coreid_t to) {
1431   struct transfer_data *data = malloc(sizeof(struct transfer_data));
1432   transfer_data_initialize(data, cte);
1433   outstanding_transfers_list->add(data);
1434   send_transfer_request_bcast(TOTAL_ORDER, data, to);
1435 }
1436 \end{verbatim}
1437
1438 When a core receives the capability transfer broadcast, it checks
1439 against the state of current capability operations in progress and
1440 takes appropriate actions if they are related.
1441
1442 If a revoke operation is in progress that is trying to revoke a copy
1443 or an ancestor of the capability being transferred, the broadcast will
1444 indicate that the system indeed has more copies and descendant of the
1445 capability being revoked which must be deleted. If the receiver was
1446 also the recipient of the capability, it does not create it and
1447 returns an error to the sender of the capability or else the receiver
1448 sends a message to the core to which the capability is being
1449 transferred to requesting it to delete the capability.
1450
1451 \begin{verbatim}
1452 transfer_request_bcast(coreid_t from, struct transfer_data *data, coreid_t to) {
1453   struct cte *my_data;
1454   my_data = outstanding_revokes_list->get(data);
1455   if (my_data) {
1456     if (to == my_core_id) {
1457       send_transfer_reply(from, FAILURE_REVOKED, data);
1458       return;
1459     }
1460
1461     my_data->sent_transfer_cap_delete_flag = true;
1462     send_delete_transferred_cap_request(to, data);
1463   }
1464
1465   if (to != my_core_id) {
1466     return;
1467   }
1468
1469   my_data = pending_delete_for_transferred_cap_list->get(data);
1470   if (my_data) {
1471     pending_delete_for_transferred_cap_list->remove(my_data);
1472     send_delete_transferred_cap_reply(my_data->from);
1473     send_transfer_reply(from, FAILURE_REVOKED, data);
1474   }
1475
1476   cap_create(data->cte);
1477   send_transfer_reply(from, SUCCESS);
1478 }
1479 \end{verbatim}
1480
1481 When the sender of the capability gets a reply from the receiver, it
1482 forwards the error code to the application and garbage collects its
1483 state.
1484
1485 \begin{verbatim}
1486 transfer_reply(errval_t err, struct transfer_request *data) {
1487   my_data = outstanding_transfers_list->get(data);
1488   outstanding_transfers_list->remove(data);
1489   return_err_to_app(my_data->app, err);
1490 }
1491 \end{verbatim}
1492
1493 If a revoke was in progress during the transfer of the capability, the
1494 core revoking the capability sends a message to the receiver of the
1495 transferred capability to delete it. When the receiver receives this
1496 message, it may or may not have received the capability yet. If it has
1497 already received the capability, it deletes or else it establishes
1498 some state to delete when it is later received.
1499
1500 \begin{verbatim}
1501 delete_transferred_cap_request(coreid_t from, struct data *data) {
1502   if (cap_exists(data->cte)) {
1503     remove_cap(cte);
1504     send_delete_transferred_cap_reply(from);
1505     return;
1506   }
1507
1508   struct pending_delete_for_transferred_cap *my_data =
1509     malloc(sizeof(struct pending_delete_for_transferred_cap));
1510   pending_delete_for_transferred_cap_initialize(my_data);
1511   pending_delete_for_transferred_cap_list->add(my_data);
1512 }
1513 \end{verbatim}
1514
1515 \begin{verbatim}
1516 delete_transferred_cap_reply(struct data *data) {
1517   my_data = outstanding_revokes_list->get(data);
1518   if (my_data) {
1519     return;
1520   }
1521
1522   my_data->sent_transfer_cap_delete_flag = false;
1523   if (seen_all_replies(my_data)) {
1524     outstanding_revokes_list->remove(my_data);
1525     return_success_to_app();
1526   }
1527 }
1528 \end{verbatim}
1529
1530 \note{Caching NYI}
1531
1532 \subsection{Two phase commit}
1533 \note{NYI}
1534 Use 2pc.
1535
1536 \subsection{Sequencer}
1537 \note{NYI}
1538 Use a sequencer. This will order whole operations.
1539
1540 \subsection{Comparison}
1541 Compare the approaches
1542
1543 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1544
1545 \chapter{Implementation details}\label{chap:implementation}
1546
1547 \begin{itemize}
1548 \item Using THC
1549 \item Using RPC between app and monitor
1550 \item Using RPC between monitors
1551 \item Everything having ancestors on memserv
1552 \item Optimization: monitor caches root cnodes
1553 \item Bootstrap
1554 \item How to put enum objtype in interface file?
1555 \item Two types of ifdefs: type of caching (none, list, or bits) and
1556   type of mgmt
1557 \end{itemize}
1558
1559 \section{Performing capability operations}
1560 If caching is not used, then the application knows for which
1561 operations it must contact the monitor and does so directly without
1562 requesting the kernel to try to perform the operation first.
1563
1564 If caching is used, then the application should try to perform the
1565 operation via the kernel first. If the capability does have remote
1566 relations, the kernel returns an appropriate error to the application
1567 in which case it contacts the monitor.
1568
1569 \section{Sharing mdb between kernel and monitor}
1570 When the application wants the monitor to perform an operation for it,
1571 it passes the monitor its root CNode and all the required parameters.
1572
1573 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1574
1575 \chapter{Not Yet Discussed}\label{chap:nyd}
1576
1577 Things that I know that I need to discuss.
1578
1579 \begin{itemize}
1580
1581 \item The OS does not guarantee which order the operations will be
1582   performed in. The user must enforce the ordering herself.
1583
1584 \item Partitioned approach with caching is eager replication. Consider
1585   lazy replication.
1586 \end{itemize}
1587
1588 \bibliographystyle{plain}
1589 \bibliography{defs,barrelfish}
1590
1591 \end{document}