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