Mercurial > nomad
changeset 555:0e7e00acfe88
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>
| author | Josef 'Jeff' Sipek <jeffpc@josefsipek.net> |
|---|---|
| date | Thu, 15 Nov 2018 17:24:12 -0500 |
| parents | a480f75291cd |
| children | be5d61e30d01 |
| files | src/objstore/include/nomad/objstore_backend.h src/objstore/obj.c |
| diffstat | 2 files changed, 69 insertions(+), 2 deletions(-) [+] |
line wrap: on
line diff
--- 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 {
--- 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: