# HG changeset patch
# User Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
# Date 1542320652 18000
# Node ID 0e7e00acfe88aca9603ea4d50686dca3ff73a6d4
# Parent  a480f75291cd5dbae08377eac9f1648c0d63ee90
objstore: maintain a tree of head object versions

We must keep track of which versions are heads in order to properly
determine which version to use when handling unqualified opens.

Signed-off-by: Josef 'Jeff' Sipek <jeffpc@josefsipek.net>

diff -r a480f75291cd -r 0e7e00acfe88 src/objstore/include/nomad/objstore_backend.h
--- a/src/objstore/include/nomad/objstore_backend.h	Mon Nov 12 21:31:25 2018 -0500
+++ b/src/objstore/include/nomad/objstore_backend.h	Thu Nov 15 17:24:12 2018 -0500
@@ -39,6 +39,7 @@
 
 	/* value */
 	struct rb_tree versions;/* cached versions */
+	struct rb_tree heads;	/* head versions */
 	uint64_t nversions;	/* number of versions */
 	uint32_t nlink;		/* file link count */
 	void *private;
@@ -76,7 +77,8 @@
 
 	/* misc */
 	struct obj *obj;
-	struct rb_node node;
+	struct rb_node all_node;	/* all versions */
+	struct rb_node head_node;	/* head versions */
 };
 
 struct objstore_open_obj_info {
diff -r a480f75291cd -r 0e7e00acfe88 src/objstore/obj.c
--- a/src/objstore/obj.c	Mon Nov 12 21:31:25 2018 -0500
+++ b/src/objstore/obj.c	Thu Nov 15 17:24:12 2018 -0500
@@ -54,7 +54,9 @@
 	memset(&obj->oid, 0, sizeof(obj->oid));
 
 	rb_create(&obj->versions, ver_cmp, sizeof(struct objver),
-		  offsetof(struct objver, node));
+		  offsetof(struct objver, all_node));
+	rb_create(&obj->heads, ver_cmp, sizeof(struct objver),
+		  offsetof(struct objver, head_node));
 
 	obj->nversions = 0;
 	obj->nlink = 0;
@@ -357,6 +359,67 @@
 	return ver;
 }
 
+/* check new version against currently known heads & update as necessary */
+static void __add_head(struct obj *obj, struct objver *new)
+{
+	struct objver *head;
+	bool found_descendant;
+	bool removed_head;
+
+	found_descendant = false;
+	removed_head = false;
+
+	/*
+	 * The set of heads is a set of versions that are all pair-wise
+	 * divergent.
+	 *
+	 * When adding a head, we want to accomplish three things which can
+	 * be reasoned about independently:
+	 *
+	 * (1) We want remove all heads that are less than the version being
+	 *     added.
+	 *
+	 * (2) We want to keep all heads that are greater than the version
+	 *     being added.
+	 *
+	 * (3) We want to keep all heads that are divergent from the version
+	 *     being added.
+	 *
+	 * (4) We want to add the new version as a head iff all the
+	 *     remaining heads are divergent with it.
+	 */
+
+restart:
+	rb_for_each(&obj->heads, head) {
+		ASSERT3P(head, !=, new);
+
+		switch (nvclock_cmp(head->clock, new->clock)) {
+			case NVC_EQ:
+				panic("found duplicate head version");
+			case NVC_LT:
+				/* head is less than new - remove it */
+				rb_remove(&obj->heads, head);
+				removed_head = true;
+				goto restart;
+			case NVC_GT:
+				/* head is greater than new - not a new head */
+				found_descendant = true;
+				break;
+			case NVC_DIV:
+				/* head is unrelated to new - nothing to do */
+				break;
+		}
+	}
+
+	/*
+	 * Add the new version as a head if...
+	 *  (1) we found at least one old head that is the new's ancestor
+	 *  (2) none of the old heads are the new's descendants
+	 */
+	if (removed_head && !found_descendant)
+		rb_add(&obj->heads, new);
+}
+
 struct objver *obj_add_version(struct obj *obj, const struct nvclock *clock)
 {
 	struct objver *ver;
@@ -381,6 +444,8 @@
 		goto err;
 	}
 
+	__add_head(obj, ver);
+
 	return ver;
 
 err: