{"thread":{"id":"45513","subject":"[PATCH] notes: Fix note_tree_consolidate not to break the note_tree structure","startedAt":"2017-03-26T02:26:27Z","lastAt":"2017-04-07T14:53:41Z","messageCount":2,"participants":["Mike Hommey","Johan Herland"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"315418","messageId":"20170326015212.11578-1-mh@glandium.org","threadId":"45513","inReplyTo":null,"subject":"[PATCH] notes: Fix note_tree_consolidate not to break the note_tree structure","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2017-03-26T01:52:12Z","receivedAt":"2017-03-26T02:26:27Z","isPatch":true,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"After a note is removed, note_tree_consolidate is called to eliminate\nsome useless nodes. The typical case is that if you had an int_node\nwith 2 PTR_TYPE_NOTEs in it, and remove one of them, then the\nPTR_TYPE_INTERNAL pointer in the parent tree can be replaced with the\nremaining PTR_TYPE_NOTE.\n\nThis works fine when PTR_TYPE_NOTEs are involved, but falls flat when\nother types are involved.\n\nTo put things in more practical terms, let's say we start from an empty\nnotes tree, and add 3 notes:\n- one for a sha1 that starts with 424\n- one for a sha1 that starts with 428\n- one for a sha1 that starts with 4c\n\nTo keep track of this, note_tree.root will have a PTR_TYPE_INTERNAL at\na[4], pointing to an int_node*.\nIn turn, that int_node* will have a PTR_TYPE_NOTE at a[0xc], pointing to\nthe leaf_node* with the key and value, and a PTR_TYPE_INTERNAL at a[2],\npointing to another int_node*.\nThat other int_node* will have 2 PTR_TYPE_NOTE, one at a[4] and the\nother at a[8].\n\nWhen looking for the note for the sha1 starting with 428, get_note() will\nrecurse through (simplified) root.a[4].a[2].a[8].\n\nNow, if we remove the note for the sha1 that starts with 4c, we're left\nwith a int_node* with only one PTR_TYPE_INTERNAL entry in it. After\nnote_tree_consolidate runs, root.a[4] now points to what used to be\npointed at by root.a[4].a[2].\n\nWhich means looking up for the note for the sha1 starting with 428 now\nfails because there is nothing at root.a[4].a[2] anymore: there is only\nroot.a[4].a[4] and root.a[4].a[8], which don't match the expected\nstructure for the lookup.\n\nSo if all there is left in an int_node* is a PTR_TYPE_INTERNAL pointer,\nwe can't safely remove it. I think the same applies for PTR_TYPE_SUBTREE\npointers. IOW, only PTR_TYPE_NOTEs are safe to be moved to the parent\nint_node*.\n\nThis doesn't have a practical effect on git because all that happens\nafter a remove_note is a write_notes_tree, which just iterates the entire\nnote tree, but this affects anything using libgit.a that would try to do\nlookups after removing notes.\n\nSigned-off-by: Mike Hommey \n---\n notes.c | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex 2bab961ac..542563b28 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -153,8 +153,8 @@ static struct leaf_node *note_tree_find(struct notes_tree *t,\n * How to consolidate an int_node:\n * If there are > 1 non-NULL entries, give up and return non-zero.\n * Otherwise replace the int_node at the given index in the given parent node\n- * with the only entry (or a NULL entry if no entries) from the given tree,\n- * and return 0.\n+ * with the only NOTE entry (or a NULL entry if no entries) from the given\n+ * tree, and return 0.\n */\n static int note_tree_consolidate(struct int_node *tree,\n \tstruct int_node *parent, unsigned char index)\n@@ -173,6 +173,8 @@ static int note_tree_consolidate(struct int_node *tree,\n \t\t}\n \t}\n \n+\tif (p && (GET_PTR_TYPE(p) != PTR_TYPE_NOTE))\n+\t\treturn -2;\n \t/* replace tree with p in parent[index] */\n \tparent->a[index] = p;\n \tfree(tree);\n-- \n2.12.1.dirty\n\n"},{"id":"316355","messageId":"CALKQrgfH-hHFrMz=t=-XKkZFvhGDRquw8Pnbgz0kJtnb-tB+Ag@mail.gmail.com","threadId":"45513","inReplyTo":"20170326015212.11578-1-mh@glandium.org","subject":"Re: [PATCH] notes: Fix note_tree_consolidate not to break the note_tree structure","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2017-04-07T14:21:55Z","receivedAt":"2017-04-07T14:53:41Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Sun, Mar 26, 2017 at 3:52 AM, Mike Hommey wrote:\n> After a note is removed, note_tree_consolidate is called to eliminate\n> some useless nodes. The typical case is that if you had an int_node\n> with 2 PTR_TYPE_NOTEs in it, and remove one of them, then the\n> PTR_TYPE_INTERNAL pointer in the parent tree can be replaced with the\n> remaining PTR_TYPE_NOTE.\n>\n> This works fine when PTR_TYPE_NOTEs are involved, but falls flat when\n> other types are involved.\n>\n> To put things in more practical terms, let's say we start from an empty\n> notes tree, and add 3 notes:\n> - one for a sha1 that starts with 424\n> - one for a sha1 that starts with 428\n> - one for a sha1 that starts with 4c\n>\n> To keep track of this, note_tree.root will have a PTR_TYPE_INTERNAL at\n> a[4], pointing to an int_node*.\n> In turn, that int_node* will have a PTR_TYPE_NOTE at a[0xc], pointing to\n> the leaf_node* with the key and value, and a PTR_TYPE_INTERNAL at a[2],\n> pointing to another int_node*.\n> That other int_node* will have 2 PTR_TYPE_NOTE, one at a[4] and the\n> other at a[8].\n>\n> When looking for the note for the sha1 starting with 428, get_note() will\n> recurse through (simplified) root.a[4].a[2].a[8].\n>\n> Now, if we remove the note for the sha1 that starts with 4c, we're left\n> with a int_node* with only one PTR_TYPE_INTERNAL entry in it. After\n> note_tree_consolidate runs, root.a[4] now points to what used to be\n> pointed at by root.a[4].a[2].\n>\n> Which means looking up for the note for the sha1 starting with 428 now\n> fails because there is nothing at root.a[4].a[2] anymore: there is only\n> root.a[4].a[4] and root.a[4].a[8], which don't match the expected\n> structure for the lookup.\n>\n> So if all there is left in an int_node* is a PTR_TYPE_INTERNAL pointer,\n> we can't safely remove it.\n\nCorrect.\n\n> I think the same applies for PTR_TYPE_SUBTREE pointers.\n\nI disagree. The subtree nodes contain the entire key prefix for that subtree\nin their .key_sha1, and before descending into a subtree (causing it to be\nunpacked), we always prefix-compare the key we're looking for against the\nsubtree's .key_sha1. This behavior, as well as the subtree's .key_sha1 is\nunaffected by which level of the notes tree hold the subtree node (provided\n- obviously - that the location is along the prefix path).\n\nAdding a variation to your example: Assume that the 424 and 428 nodes are\npacked inside a subtree node. We then have: root.a[4] points to an int_node\nwhose .a[2] points to a subtree node, and .a[0xc] points to a note node. The\nsubtree node at root.a[4].a[2] represents a key-prefix of \"42\" (i.e.\nits .key_sha1\nequals [0x42, 0x0, ..., 0x0, 0x2]).\n\nNow, after removing the 4c note, we consider consolidating the int_node at\nroot.a[4]. At this point, its only member is the single subtree entry at a[2].\nBy removing the int_node and moving the subtree node to root.a[4], we\nhave simply reorganized from\n\n root.a[4].a[2] -> subtree(\"42\")\n\nto\n\n root.a[4] -> subtree(\"42\")\n\nAFAICS, this layout is equally valid (and more optimal) than before we\nconsolidated. We will still always perform the complete prefix-compare\nagainst \"42\" before descending into the subtree.\n\nIn summary, the bug that really needs fixing is the relocation of existing\nint_nodes. Otherwise, leaf_nodes (whether they be PTR_TYPE_NOTE or\nPTR_TYPE_SUBTREE) can be freely relocated within the tree as long as the\npath leading to them (root.a[x].a[y].a[z]) prefix-matches their .key_sha1.\n\n> IOW, only PTR_TYPE_NOTEs are safe to be moved to the parent\n> int_node*.\n\nThis holds for both PTR_TYPE_NOTEs and PTR_TYPE_SUBTREEs, IMHO.\n\n>\n> This doesn't have a practical effect on git because all that happens\n> after a remove_note is a write_notes_tree, which just iterates the entire\n> note tree, but this affects anything using libgit.a that would try to do\n> lookups after removing notes.\n>\n> Signed-off-by: Mike Hommey \n\nRegardless of the PTR_TYPE_SUBTREE optimization discussed above,\nI believe your patch is safe, and can be used as-is.\n\n> ---\n> notes.c | 6 ++++--\n> 1 file changed, 4 insertions(+), 2 deletions(-)\n>\n> diff --git a/notes.c b/notes.c\n> index 2bab961ac..542563b28 100644\n> --- a/notes.c\n> +++ b/notes.c\n> @@ -153,8 +153,8 @@ static struct leaf_node *note_tree_find(struct notes_tree *t,\n> * How to consolidate an int_node:\n> * If there are > 1 non-NULL entries, give up and return non-zero.\n> * Otherwise replace the int_node at the given index in the given parent node\n> - * with the only entry (or a NULL entry if no entries) from the given tree,\n> - * and return 0.\n> + * with the only NOTE entry (or a NULL entry if no entries) from the given\n> + * tree, and return 0.\n> */\n> static int note_tree_consolidate(struct int_node *tree,\n> struct int_node *parent, unsigned char index)\n> @@ -173,6 +173,8 @@ static int note_tree_consolidate(struct int_node *tree,\n> }\n> }\n>\n> + if (p && (GET_PTR_TYPE(p) != PTR_TYPE_NOTE))\n> + return -2;\n\nBased on the above discussion, I believe this can be rewritten to:\n\n+ if (p && (GET_PTR_TYPE(p) == PTR_TYPE_INTERNAL))\n+ return -2; /* Cannot move int_nodes within the tree. */\n\nfor a more optimal handling of subtree nodes in this scenario.\n\n\nHave fun! :)\n\n...Johan\n\n\n> /* replace tree with p in parent[index] */\n> parent->a[index] = p;\n> free(tree);\n> --\n> 2.12.1.dirty\n>\n\n\n\n-- \nJohan Herland, \nwww.herland.net\n"}]}