doc: tn13: Add section on implementation of cap database
authorSimon Gerber <simon.gerber@inf.ethz.ch>
Fri, 2 Jun 2017 10:11:55 +0000 (12:11 +0200)
committerSimon Gerber <simon.gerber@inf.ethz.ch>
Fri, 2 Jun 2017 11:57:47 +0000 (13:57 +0200)
Signed-off-by: Simon Gerber <simon.gerber@inf.ethz.ch>

doc/013-capability-mgmt/CapMgmt.tex
doc/style/barrelfish.bib

index 7d5786a..7744e77 100644 (file)
@@ -673,6 +673,33 @@ dynamically update the type of caching used.  For this, we need to
 identify the cross-over point where one approach is preferred over the
 other.
 
+\section{Implementation}
+
+As summarized, the current implementation uses a partitioned database which
+caches remote relations of capabilities with three bits, one each for remote
+copies, ancestors, and descendants.
+
+Each database partition is associated with a kernel control block, and keeps
+track of all the capabilities in the CSpaces of all the dispatchers associated
+with that kernel control block.
+The database is implemented as a binary search tree.
+We chose the AA tree~\cite{Andersson1993}, which is a variation of the
+red-black tree where red nodes can only be added as right subchildren.
+This results in a greatly simplified implementation of the maintenance
+operations while conserving the red-black tree's invariants.
+
+The particular variation we implement for the capability database is an
+interval tree as described by
+Cormen et al.~\cite[section~14.3, pp~348-354]{Cormen2001} which uses the AA
+tree as its basis.
+
+It is noteworthy that we embed the tree nodes into each kernel capability
+object to avoid any dynamic allocations in the CPU driver.
+
+The choice of tree, the database implementation and its performance are more
+extensively discussed in chapter 4 of Mark Nevill's master's
+thesis~\cite{Nevill2012}.
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 \chapter{Solutions}\label{chap:solutions}
index e13316a..24dade9 100644 (file)
@@ -1389,3 +1389,27 @@ D. E. Long and Carlos Maltzahn},
  publisher = {USENIX Association},
  address = {Berkeley, CA, USA},
 }
+
+@inproceedings{Andersson1993,
+ author = {Andersson, Arne},
+ title = {Balanced Search Trees Made Simple},
+ booktitle = {Proceedings of the Third Workshop on Algorithms and Data Structures},
+ series = {WADS '93},
+ year = {1993},
+ isbn = {3-540-57155-8},
+ pages = {60--71},
+ numpages = {12},
+ url = {http://dl.acm.org/citation.cfm?id=645929.672716},
+ acmid = {672716},
+ publisher = {Springer-Verlag},
+ address = {London, UK, UK},
+}
+
+@book{Cormen2001,
+  author = "Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford",
+  title = "Introduction to Algorithms",
+  edition = 3,
+  publisher = "{MIT} Press and McGraw-Hill",
+  year = 2009,
+  isbn = "987-0-262-03384-4"
+}