[PATCH 5/7] revision cache: maps of 'new' objects

From

Sam Vilain <sam@vilain.net>

Date

Jun 4, 2009, 14:05 UTC

Message-ID

<a3798f6363249996f03771bd286bb2b1db10ea24.1244125128.git.sam@vilain.net>

In-Reply-To

<cover.1244125127.git.sam@vilain.net>

Signed-off-by: Sam Vilain <sam@vilain.net>
---
 Documentation/technical/revision-cache.txt |   24 +++++++++++++++++++++++-
 1 files changed, 23 insertions(+), 1 deletions(-)

diff --git a/Documentation/technical/revision-cache.txt b/Documentation/technical/revision-cache.txt
index 198c33a..e0adb26 100644
--- a/Documentation/technical/revision-cache.txt
+++ b/Documentation/technical/revision-cache.txt
@@ -28,6 +28,11 @@ A revision cache contains;
     space.  A count of how many bits are '1' is included.  A separate
     bitmap is included for the 'start' objects.
 
+  - Optionally, for any 'end' object, a 'newness' bitmap indicating
+    which of the objects in the object list are reachable from that
+    'end' object, but not reachable from the 'start' objects reachable
+    from that 'end' object.
+
 
 Start Objects and End Objects
 -----------------------------
@@ -120,6 +125,9 @@ generating a newer one which covers objects created after it.  This
 approach will be able to answer many questions, but not topological
 ordering between objects which appeared in different caches.
 
+Stacking revision caches is essential for being able to generate the
+'newness' bitmaps efficiently.
+
 
 Revision Walker
 ~~~~~~~~~~~~~~~
@@ -144,7 +152,7 @@ required.  Some API exists to do this, and the return value from
 'rev_cache_ok' is true if suitable caches were found for the
 information required, and false if it would require a graph traversal:
 
-  rev_cache_options( ordered? )
+  rev_cache_options( ordered?, new? )
   rev_cache_ok( ) : Bool
 
 The rev_cache_ok() function must open all available revision caches,
@@ -163,6 +171,11 @@ If any 'uninteresting' objects were passed, then the return value is
 true if the suitability function passes for all of the revision caches
 which are used.
 
+If the 'new' flag is set to true, then the return value is only true
+if the 'uninteresting' objects also have suitable revision caches
+leading back to the start of history (or last 'shallow' point), or the
+'newness' bitmaps are present for all of the 'start' references used.
+
 
 Returning objects
 ^^^^^^^^^^^^^^^^^
@@ -208,6 +221,10 @@ Then, it must repeat the topological walk for each of the 'start'
 objects, looking up each object in the contents hash for a sequence
 number, set a bit in the bitmap for that 'start' object, and finally
 RLE compress it.
+If there are suitable other revision caches available, then the
+'newness' bitmaps are built by checking with the stacked revision
+caches whether the object exists and is reachable from the 'start'
+objects which connect to those stacked caches.
 
 
 receive-pack/pack-objects
@@ -250,6 +267,11 @@ If multiple 'start' objects were used, then the count can be returned
 by decompressing and OR'ing the bitmaps together, counting the total
 number of '1's in the bitmap.
 
+If the 'newness' bitmaps are available, then these can be used to
+avoid sending objects which the other end will already have.
+When applicable the 'newness' bitmaps will be masked against the
+combined reachability bitmaps to derive a shorter list of objects.
+
 If multiple revision caches were used, but not in single file, then
 the number of objects can be obtained by building a hash table of all
 the objects in all of the caches, and returning the number of hash

-- 
debian.1.5.6.1