{"thread":{"id":"57186","subject":"[PATCH] apply: Avoid ambiguous pointer provenance for CHERI/Arm's Morello","startedAt":"2022-01-05T13:23:24Z","lastAt":"2022-01-08T00:52:07Z","messageCount":14,"participants":["Jessica Clarke","Konstantin Khomoutov","Taylor Blau","Junio C Hamano","René Scharfe"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"445519","messageId":"20220105132310.6600-1-jrtc27@jrtc27.com","threadId":"57186","inReplyTo":null,"subject":"[PATCH] apply: Avoid ambiguous pointer provenance for CHERI/Arm's Morello","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-05T13:23:10Z","receivedAt":"2022-01-05T13:23:24Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"On CHERI, and thus Arm's Morello prototype, pointers are implemented as\nhardware capabilities which, as well as having a normal integer address,\nhave additional bounds, permissions and other metadata in a second word.\nIn order to preserve this metadata, uintptr_t is also implemented as a\ncapability, not a plain integer, which causes problems for binary\noperators, as the metadata preserved in the output can only come from\none of the inputs. In most cases this is clear, as normally at least one\noperand is provably a plain integer, but if both operands are uintptr_t\nand have no indication they're just plain integers then it is ambiguous,\nand the current implementation will arbitrarily, but deterministically,\npick the left-hand side, due to empirical evidence that it is more\nlikely to be correct.\n\nIn this instance, both operands are of type uintptr_t, with one being a\nfunction argument and one being cast from a pointer, so both could be\nvalid pointers. Moreover, the left-hand side is not the actual pointer.\nThis means that, currently, the code when run on a CHERI architecture\nwill preserve the metadata from the integer, i.e. an invalid capability\nthat will trap on deference, and not the pointer.\n\nThis can be addressed by changing the type of the function argument in\norder to more clearly convey intent, both to the compiler so it knows to\ngenerate the right code but also to the developer so it's clear that the\nargument is not in fact a pointer but just a plain integer (in this case\nbeing either APPLY_SYMLINK_GOES_AWAY or APPLY_SYMLINK_IN_RESULT).\n\nSigned-off-by: Jessica Clarke \n---\n apply.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/apply.c b/apply.c\nindex fed195250b..7c7d56cacb 100644\n--- a/apply.c\n+++ b/apply.c\n@@ -3814,7 +3814,7 @@ static int check_to_create(struct apply_state *state,\n \n static uintptr_t register_symlink_changes(struct apply_state *state,\n \t\t\t\t\t const char *path,\n-\t\t\t\t\t uintptr_t what)\n+\t\t\t\t\t size_t what)\n {\n \tstruct string_list_item *ent;\n \n@@ -3823,7 +3823,7 @@ static uintptr_t register_symlink_changes(struct apply_state *state,\n \t\tent = string_list_insert(&state->symlink_changes, path);\n \t\tent->util = (void *)0;\n \t}\n-\tent->util = (void *)(what | ((uintptr_t)ent->util));\n+\tent->util = (void *)((uintptr_t)what | ((uintptr_t)ent->util));\n \treturn (uintptr_t)ent->util;\n }\n \n-- \n2.33.1\n\n"},{"id":"445534","messageId":"20220105163935.eqfdqbeifcgj2wna@carbon","threadId":"57186","inReplyTo":"20220105132310.6600-1-jrtc27@jrtc27.com","subject":"Re: [PATCH] apply: Avoid ambiguous pointer provenance for CHERI/Arm's Morello","fromName":"Konstantin Khomoutov","fromEmail":"kostix@bswap.ru","sentAt":"2022-01-05T16:39:35Z","receivedAt":"2022-01-05T16:39:47Z","isPatch":true,"sender":{"key":"kostix@bswap.ru","avatar":null},"body":"On Wed, Jan 05, 2022 at 01:23:10PM +0000, Jessica Clarke wrote:\n\n[...]\n> This means that, currently, the code when run on a CHERI architecture\n> will preserve the metadata from the integer, i.e. an invalid capability\n> that will trap on deference, and not the pointer.\n\n^ You have probably meant to use \"dereference\" here.\n\n"},{"id":"445535","messageId":"85A71121-BD74-416B-BDC5-3818C6892F7C@jrtc27.com","threadId":"57186","inReplyTo":"20220105163935.eqfdqbeifcgj2wna@carbon","subject":"Re: [PATCH] apply: Avoid ambiguous pointer provenance for CHERI/Arm's Morello","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-05T16:40:59Z","receivedAt":"2022-01-05T16:41:02Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"On 5 Jan 2022, at 16:39, Konstantin Khomoutov wrote:\n> \n> On Wed, Jan 05, 2022 at 01:23:10PM +0000, Jessica Clarke wrote:\n> \n> [...]\n>> This means that, currently, the code when run on a CHERI architecture\n>> will preserve the metadata from the integer, i.e. an invalid capability\n>> that will trap on deference, and not the pointer.\n> \n> ^ You have probably meant to use \"dereference\" here.\n\nIndeed I did; spellcheck doesn’t help for wrong words...\n\nShould I send a v2, or can that be fixed on git-am?\n\nJess\n\n"},{"id":"445673","messageId":"YddySiBCOOYYKDmC@nand.local","threadId":"57186","inReplyTo":"20220105132310.6600-1-jrtc27@jrtc27.com","subject":"Re: [PATCH] apply: Avoid ambiguous pointer provenance for CHERI/Arm's Morello","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2022-01-06T22:50:50Z","receivedAt":"2022-01-06T22:50:54Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Wed, Jan 05, 2022 at 01:23:10PM +0000, Jessica Clarke wrote:\n> [...] In most cases this is clear, as normally at least one operand is\n> provably a plain integer, but if both operands are uintptr_t and have\n> no indication they're just plain integers then it is ambiguous, and\n> the current implementation will arbitrarily, but deterministically,\n> pick the left-hand side, due to empirical evidence that it is more\n> likely to be correct.\n\nWouldn't a simpler, less invasive fix be to instead write the expression\nso that the left-hand operand is a pointer? IOW, shouldn't the following\nwork (with no other changes):\n\n ent->util = (void *)((uintptr_t)what | ent->util);\n\n?\n\n(I dropped the explicit cast on the right-hand side, since ent->util is\nalready a uintptr_t, and the left-hand side has an explicit cast, so\nthere isn't any type promotion going on here).\n\nThanks,\nTaylor\n"},{"id":"445674","messageId":"xmqqczl4bhmo.fsf@gitster.g","threadId":"57186","inReplyTo":"20220105132310.6600-1-jrtc27@jrtc27.com","subject":"Re: [PATCH] apply: Avoid ambiguous pointer provenance for CHERI/Arm's Morello","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-06T22:53:51Z","receivedAt":"2022-01-06T22:53:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jessica Clarke writes:\n\n> On CHERI, and thus Arm's Morello prototype, pointers are implemented as\n> hardware capabilities which, as well as having a normal integer address,\n> have additional bounds, permissions and other metadata in a second word.\n> In order to preserve this metadata, uintptr_t is also implemented as a\n> capability, not a plain integer, which causes problems for binary\n> operators, as the metadata preserved in the output can only come from\n> one of the inputs. In most cases this is clear, as normally at least one\n> operand is provably a plain integer, but if both operands are uintptr_t\n> and have no indication they're just plain integers then it is ambiguous,\n> and the current implementation will arbitrarily, but deterministically,\n> pick the left-hand side, due to empirical evidence that it is more\n> likely to be correct.\n\nWhat's left-hand side in the context of the code you changed?\nBetween \"what\" vs \"ent->util\" you take \"what\"? That cannot be\ntrue. Are you referring to the (usually hidden and useless when we\nuse it as an integer) \"hardware capabilities\" word as \"left\" vs the\nvalue of the pointer as \"right\"?\n\n> static uintptr_t register_symlink_changes(struct apply_state *state,\n> \t\t\t\t\t const char *path,\n> -\t\t\t\t\t uintptr_t what)\n> +\t\t\t\t\t size_t what)\n> {\n> \tstruct string_list_item *ent;\n> \n> @@ -3823,7 +3823,7 @@ static uintptr_t register_symlink_changes(struct apply_state *state,\n> \t\tent = string_list_insert(&state->symlink_changes, path);\n> \t\tent->util = (void *)0;\n> \t}\n> -\tent->util = (void *)(what | ((uintptr_t)ent->util));\n> +\tent->util = (void *)((uintptr_t)what | ((uintptr_t)ent->util));\n> \treturn (uintptr_t)ent->util;\n> }\n\nI actually wonder if it results in code that is much easier to\nfollow if we did:\n\n * Introduce an \"enum apply_symlink_treatment\" that has\n APPLY_SYMLINK_GOES_AWAY and APPLY_SYMLINK_IN_RESULT as its\n possible values;\n\n * Make register_symlink_changes() and check_symlink_changes()\n work with \"enum apply_symlink_treatment\";\n\n * (optional) stop using string_list() to store the symlink_changes;\n use strintmap and use strintmap_set() and strintmap_get() to\n access its entries, so that the ugly implementation detail\n (i.e. \"the container type we use only has a (void *) field to\n store caller-supplied data, so we cast an integer and a pointer\n back and forth\") can be safely hidden.\n\n"},{"id":"445676","messageId":"C2DD77CA-D1F1-45ED-912F-C4532EB2720C@jrtc27.com","threadId":"57186","inReplyTo":"YddySiBCOOYYKDmC@nand.local","subject":"Re: [PATCH] apply: Avoid ambiguous pointer provenance for CHERI/Arm's Morello","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-06T22:57:42Z","receivedAt":"2022-01-06T22:57:45Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"]On 6 Jan 2022, at 22:50, Taylor Blau wrote:\n> \n> On Wed, Jan 05, 2022 at 01:23:10PM +0000, Jessica Clarke wrote:\n>> [...] In most cases this is clear, as normally at least one operand is\n>> provably a plain integer, but if both operands are uintptr_t and have\n>> no indication they're just plain integers then it is ambiguous, and\n>> the current implementation will arbitrarily, but deterministically,\n>> pick the left-hand side, due to empirical evidence that it is more\n>> likely to be correct.\n> \n> Wouldn't a simpler, less invasive fix be to instead write the expression\n> so that the left-hand operand is a pointer? IOW, shouldn't the following\n> work (with no other changes):\n> \n> ent->util = (void *)((uintptr_t)what | ent->util);\n> \n> ?\n> \n> (I dropped the explicit cast on the right-hand side, since ent->util is\n> already a uintptr_t, and the left-hand side has an explicit cast, so\n> there isn't any type promotion going on here).\n\nThat would still warn as it’s still ambiguous. It just happens that the\narbitrary choice picks the right side. Better to clean up the code to\nremove the ambiguity and clarify it to the programmer.\n\nJess\n\n"},{"id":"445677","messageId":"BE9D3BD5-EC19-4881-872D-CEB4039A382D@jrtc27.com","threadId":"57186","inReplyTo":"xmqqczl4bhmo.fsf@gitster.g","subject":"Re: [PATCH] apply: Avoid ambiguous pointer provenance for CHERI/Arm's Morello","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-06T23:02:23Z","receivedAt":"2022-01-06T23:02:26Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"On 6 Jan 2022, at 22:53, Junio C Hamano wrote:\n> \n> Jessica Clarke writes:\n> \n>> On CHERI, and thus Arm's Morello prototype, pointers are implemented as\n>> hardware capabilities which, as well as having a normal integer address,\n>> have additional bounds, permissions and other metadata in a second word.\n>> In order to preserve this metadata, uintptr_t is also implemented as a\n>> capability, not a plain integer, which causes problems for binary\n>> operators, as the metadata preserved in the output can only come from\n>> one of the inputs. In most cases this is clear, as normally at least one\n>> operand is provably a plain integer, but if both operands are uintptr_t\n>> and have no indication they're just plain integers then it is ambiguous,\n>> and the current implementation will arbitrarily, but deterministically,\n>> pick the left-hand side, due to empirical evidence that it is more\n>> likely to be correct.\n> \n> What's left-hand side in the context of the code you changed?\n> Between \"what\" vs \"ent->util\" you take \"what\"? That cannot be\n> true. Are you referring to the (usually hidden and useless when we\n> use it as an integer) \"hardware capabilities\" word as \"left\" vs the\n> value of the pointer as \"right\"?\n\nLeft-hand side is what, right-hand side is ((uintptr_t)ent->util). The\nbounds/permissions/tag/etc need to be inherited from somewhere, and as\nan arbitrary empirically-best choice when otherwise ambiguous we choose\nthe left, i.e. what. The alternative would just be to error, which will\nresult in strictly more code failing to build for CHERI despite such a\nguess being correct most of the time.\n\n>> static uintptr_t register_symlink_changes(struct apply_state *state,\n>> \t\t\t\t\t const char *path,\n>> -\t\t\t\t\t uintptr_t what)\n>> +\t\t\t\t\t size_t what)\n>> {\n>> \tstruct string_list_item *ent;\n>> \n>> @@ -3823,7 +3823,7 @@ static uintptr_t register_symlink_changes(struct apply_state *state,\n>> \t\tent = string_list_insert(&state->symlink_changes, path);\n>> \t\tent->util = (void *)0;\n>> \t}\n>> -\tent->util = (void *)(what | ((uintptr_t)ent->util));\n>> +\tent->util = (void *)((uintptr_t)what | ((uintptr_t)ent->util));\n>> \treturn (uintptr_t)ent->util;\n>> }\n> \n> I actually wonder if it results in code that is much easier to\n> follow if we did:\n> \n> * Introduce an \"enum apply_symlink_treatment\" that has\n> APPLY_SYMLINK_GOES_AWAY and APPLY_SYMLINK_IN_RESULT as its\n> possible values;\n> \n> * Make register_symlink_changes() and check_symlink_changes()\n> work with \"enum apply_symlink_treatment\";\n> \n> * (optional) stop using string_list() to store the symlink_changes;\n> use strintmap and use strintmap_set() and strintmap_get() to\n> access its entries, so that the ugly implementation detail\n> (i.e. \"the container type we use only has a (void *) field to\n> store caller-supplied data, so we cast an integer and a pointer\n> back and forth\") can be safely hidden.\n\nThose would be better if you want a less-minimal change. I can easily\ndo the first two, but the last one may or may not take me a while to\nfigure out given I’m not familiar with git’s C internals.\n\nJess\n\n"},{"id":"445680","messageId":"xmqqwnjca0vn.fsf@gitster.g","threadId":"57186","inReplyTo":"BE9D3BD5-EC19-4881-872D-CEB4039A382D@jrtc27.com","subject":"Re: [PATCH] apply: Avoid ambiguous pointer provenance for CHERI/Arm's Morello","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-06T23:41:00Z","receivedAt":"2022-01-06T23:41:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jessica Clarke writes:\n\n>> I actually wonder if it results in code that is much easier to\n>> follow if we did:\n>> \n>> * Introduce an \"enum apply_symlink_treatment\" that has\n>> APPLY_SYMLINK_GOES_AWAY and APPLY_SYMLINK_IN_RESULT as its\n>> possible values;\n>> \n>> * Make register_symlink_changes() and check_symlink_changes()\n>> work with \"enum apply_symlink_treatment\";\n>> \n>> * (optional) stop using string_list() to store the symlink_changes;\n>> use strintmap and use strintmap_set() and strintmap_get() to\n>> access its entries, so that the ugly implementation detail\n>> (i.e. \"the container type we use only has a (void *) field to\n>> store caller-supplied data, so we cast an integer and a pointer\n>> back and forth\") can be safely hidden.\n>\n> Those would be better if you want a less-minimal change.\n\nThe first two at least would make an understandable change, as\nopposed to the code as posted, which is totally opaque why we need\nto take size_t and cast it to uintptr_t in the first place.\n\nI have no confidence in myself that I would not accept a future\npatch that reverts the change made by this patch happily. I usually\ntry to be careful to go back to the originating commit by running\n\"blame\" on the preimage and may find your commit, but that's only\n\"usually\". If I were to work only with the file contents after\napplying this patch, because no clue ...\n\n\tent->util = (void *)((uintptr_t)what | ((uintptr_t)ent->util));\n\n... on this line of code hints why we must be called with size_t and\nhave to cast it here, instead of working with uintptr_t throughout,\nI am reasonably sure I'd happily take such a patch and break your\n\"fix\" here.\n\nIf we make the code pass around the enum, have a temporary variable\nof the same enum type to compute the next value we stuff in\nent->util, and make an assignment of that enum value to ent->util,\nit is much less likely that I'd blindly accept a patch to take us\nback to deal with uintptr_t directly.\n"},{"id":"445711","messageId":"8739caad-aa3d-1f0f-b5dd-6174a8e059f6@web.de","threadId":"57186","inReplyTo":"xmqqczl4bhmo.fsf@gitster.g","subject":"Re: [PATCH] apply: Avoid ambiguous pointer provenance for CHERI/Arm's Morello","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-01-07T12:16:53Z","receivedAt":"2022-01-07T12:17:03Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 06.01.22 um 23:53 schrieb Junio C Hamano:\n> Jessica Clarke writes:\n>\n>> On CHERI, and thus Arm's Morello prototype, pointers are implemented as\n>> hardware capabilities which, as well as having a normal integer address,\n>> have additional bounds, permissions and other metadata in a second word.\n>> In order to preserve this metadata, uintptr_t is also implemented as a\n>> capability, not a plain integer, which causes problems for binary\n>> operators, as the metadata preserved in the output can only come from\n>> one of the inputs. In most cases this is clear, as normally at least one\n>> operand is provably a plain integer, but if both operands are uintptr_t\n>> and have no indication they're just plain integers then it is ambiguous,\n>> and the current implementation will arbitrarily, but deterministically,\n>> pick the left-hand side, due to empirical evidence that it is more\n>> likely to be correct.\n>\n> What's left-hand side in the context of the code you changed?\n> Between \"what\" vs \"ent->util\" you take \"what\"? That cannot be\n> true. Are you referring to the (usually hidden and useless when we\n> use it as an integer) \"hardware capabilities\" word as \"left\" vs the\n> value of the pointer as \"right\"?\n>\n>> static uintptr_t register_symlink_changes(struct apply_state *state,\n>> \t\t\t\t\t const char *path,\n>> -\t\t\t\t\t uintptr_t what)\n>> +\t\t\t\t\t size_t what)\n>> {\n>> \tstruct string_list_item *ent;\n>>\n>> @@ -3823,7 +3823,7 @@ static uintptr_t register_symlink_changes(struct apply_state *state,\n>> \t\tent = string_list_insert(&state->symlink_changes, path);\n>> \t\tent->util = (void *)0;\n>> \t}\n>> -\tent->util = (void *)(what | ((uintptr_t)ent->util));\n>> +\tent->util = (void *)((uintptr_t)what | ((uintptr_t)ent->util));\n>> \treturn (uintptr_t)ent->util;\n>> }\n>\n> I actually wonder if it results in code that is much easier to\n> follow if we did:\n>\n> * Introduce an \"enum apply_symlink_treatment\" that has\n> APPLY_SYMLINK_GOES_AWAY and APPLY_SYMLINK_IN_RESULT as its\n> possible values;\n>\n> * Make register_symlink_changes() and check_symlink_changes()\n> work with \"enum apply_symlink_treatment\";\n>\n> * (optional) stop using string_list() to store the symlink_changes;\n> use strintmap and use strintmap_set() and strintmap_get() to\n> access its entries, so that the ugly implementation detail\n> (i.e. \"the container type we use only has a (void *) field to\n> store caller-supplied data, so we cast an integer and a pointer\n> back and forth\") can be safely hidden.\n>\nOr strsets -- we only need two.\n\n--- >8 ---\nSubject: [PATCH] apply: use strsets to track symlinks\n\nSymlink changes are tracked in a string_list, with the util pointer\nvalue indicating whether a symlink is kept or removed. Using fake\npointer values requires awkward casts. Use one strset for each type of\nchange instead to simplify and shorten the code.\n\nOriginal-patch-by: Jessica Clarke \nSigned-off-by: René Scharfe \n---\n apply.c | 42 ++++++++----------------------------------\n apply.h | 26 +++++++++++---------------\n 2 files changed, 19 insertions(+), 49 deletions(-)\n\ndiff --git a/apply.c b/apply.c\nindex fed195250b..7deb4f79fd 100644\n--- a/apply.c\n+++ b/apply.c\n@@ -103,7 +103,8 @@ int init_apply_state(struct apply_state *state,\n \tstate->linenr = 1;\n \tstring_list_init_nodup(&state->fn_table);\n \tstring_list_init_nodup(&state->limit_by_name);\n-\tstring_list_init_nodup(&state->symlink_changes);\n+\tstrset_init(&state->removed_symlinks);\n+\tstrset_init(&state->kept_symlinks);\n \tstrbuf_init(&state->root, 0);\n\n \tgit_apply_config();\n@@ -117,7 +118,8 @@ int init_apply_state(struct apply_state *state,\n void clear_apply_state(struct apply_state *state)\n {\n \tstring_list_clear(&state->limit_by_name, 0);\n-\tstring_list_clear(&state->symlink_changes, 0);\n+\tstrset_clear(&state->removed_symlinks);\n+\tstrset_clear(&state->kept_symlinks);\n \tstrbuf_release(&state->root);\n\n \t/* &state->fn_table is cleared at the end of apply_patch() */\n@@ -3812,59 +3814,31 @@ static int check_to_create(struct apply_state *state,\n \treturn 0;\n }\n\n-static uintptr_t register_symlink_changes(struct apply_state *state,\n-\t\t\t\t\t const char *path,\n-\t\t\t\t\t uintptr_t what)\n-{\n-\tstruct string_list_item *ent;\n-\n-\tent = string_list_lookup(&state->symlink_changes, path);\n-\tif (!ent) {\n-\t\tent = string_list_insert(&state->symlink_changes, path);\n-\t\tent->util = (void *)0;\n-\t}\n-\tent->util = (void *)(what | ((uintptr_t)ent->util));\n-\treturn (uintptr_t)ent->util;\n-}\n-\n-static uintptr_t check_symlink_changes(struct apply_state *state, const char *path)\n-{\n-\tstruct string_list_item *ent;\n-\n-\tent = string_list_lookup(&state->symlink_changes, path);\n-\tif (!ent)\n-\t\treturn 0;\n-\treturn (uintptr_t)ent->util;\n-}\n-\n static void prepare_symlink_changes(struct apply_state *state, struct patch *patch)\n {\n \tfor ( ; patch; patch = patch->next) {\n \t\tif ((patch->old_name && S_ISLNK(patch->old_mode)) &&\n \t\t (patch->is_rename || patch->is_delete))\n \t\t\t/* the symlink at patch->old_name is removed */\n-\t\t\tregister_symlink_changes(state, patch->old_name, APPLY_SYMLINK_GOES_AWAY);\n+\t\t\tstrset_add(&state->removed_symlinks, patch->old_name);\n\n \t\tif (patch->new_name && S_ISLNK(patch->new_mode))\n \t\t\t/* the symlink at patch->new_name is created or remains */\n-\t\t\tregister_symlink_changes(state, patch->new_name, APPLY_SYMLINK_IN_RESULT);\n+\t\t\tstrset_add(&state->kept_symlinks, patch->new_name);\n \t}\n }\n\n static int path_is_beyond_symlink_1(struct apply_state *state, struct strbuf *name)\n {\n \tdo {\n-\t\tunsigned int change;\n-\n \t\twhile (--name->len && name->buf[name->len] != '/')\n \t\t\t; /* scan backwards */\n \t\tif (!name->len)\n \t\t\tbreak;\n \t\tname->buf[name->len] = '\\0';\n-\t\tchange = check_symlink_changes(state, name->buf);\n-\t\tif (change & APPLY_SYMLINK_IN_RESULT)\n+\t\tif (strset_contains(&state->kept_symlinks, name->buf))\n \t\t\treturn 1;\n-\t\tif (change & APPLY_SYMLINK_GOES_AWAY)\n+\t\tif (strset_contains(&state->removed_symlinks, name->buf))\n \t\t\t/*\n \t\t\t * This cannot be \"return 0\", because we may\n \t\t\t * see a new one created at a higher level.\ndiff --git a/apply.h b/apply.h\nindex 16202da160..4052da50c0 100644\n--- a/apply.h\n+++ b/apply.h\n@@ -4,6 +4,7 @@\n #include \"hash.h\"\n #include \"lockfile.h\"\n #include \"string-list.h\"\n+#include \"strmap.h\"\n\n struct repository;\n\n@@ -25,20 +26,6 @@ enum apply_verbosity {\n \tverbosity_verbose = 1\n };\n\n-/*\n- * We need to keep track of how symlinks in the preimage are\n- * manipulated by the patches. A patch to add a/b/c where a/b\n- * is a symlink should not be allowed to affect the directory\n- * the symlink points at, but if the same patch removes a/b,\n- * it is perfectly fine, as the patch removes a/b to make room\n- * to create a directory a/b so that a/b/c can be created.\n- *\n- * See also \"struct string_list symlink_changes\" in \"struct\n- * apply_state\".\n- */\n-#define APPLY_SYMLINK_GOES_AWAY 01\n-#define APPLY_SYMLINK_IN_RESULT 02\n-\n struct apply_state {\n \tconst char *prefix;\n\n@@ -86,7 +73,16 @@ struct apply_state {\n\n \t/* Various \"current state\" */\n \tint linenr; /* current line number */\n-\tstruct string_list symlink_changes; /* we have to track symlinks */\n+\t/*\n+\t * We need to keep track of how symlinks in the preimage are\n+\t * manipulated by the patches. A patch to add a/b/c where a/b\n+\t * is a symlink should not be allowed to affect the directory\n+\t * the symlink points at, but if the same patch removes a/b,\n+\t * it is perfectly fine, as the patch removes a/b to make room\n+\t * to create a directory a/b so that a/b/c can be created.\n+\t */\n+\tstruct strset removed_symlinks;\n+\tstruct strset kept_symlinks;\n\n \t/*\n \t * For \"diff-stat\" like behaviour, we keep track of the biggest change\n--\n2.34.1\n"},{"id":"445716","messageId":"3AB57D1A-E4B5-47B6-AD43-97299C9DE92D@jrtc27.com","threadId":"57186","inReplyTo":"8739caad-aa3d-1f0f-b5dd-6174a8e059f6@web.de","subject":"Re: [PATCH] apply: Avoid ambiguous pointer provenance for CHERI/Arm's Morello","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-07T13:00:41Z","receivedAt":"2022-01-07T13:00:45Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"On 7 Jan 2022, at 12:16, René Scharfe wrote:\n> \n> Am 06.01.22 um 23:53 schrieb Junio C Hamano:\n>> Jessica Clarke writes:\n>> \n>>> On CHERI, and thus Arm's Morello prototype, pointers are implemented as\n>>> hardware capabilities which, as well as having a normal integer address,\n>>> have additional bounds, permissions and other metadata in a second word.\n>>> In order to preserve this metadata, uintptr_t is also implemented as a\n>>> capability, not a plain integer, which causes problems for binary\n>>> operators, as the metadata preserved in the output can only come from\n>>> one of the inputs. In most cases this is clear, as normally at least one\n>>> operand is provably a plain integer, but if both operands are uintptr_t\n>>> and have no indication they're just plain integers then it is ambiguous,\n>>> and the current implementation will arbitrarily, but deterministically,\n>>> pick the left-hand side, due to empirical evidence that it is more\n>>> likely to be correct.\n>> \n>> What's left-hand side in the context of the code you changed?\n>> Between \"what\" vs \"ent->util\" you take \"what\"? That cannot be\n>> true. Are you referring to the (usually hidden and useless when we\n>> use it as an integer) \"hardware capabilities\" word as \"left\" vs the\n>> value of the pointer as \"right\"?\n>> \n>>> static uintptr_t register_symlink_changes(struct apply_state *state,\n>>> \t\t\t\t\t const char *path,\n>>> -\t\t\t\t\t uintptr_t what)\n>>> +\t\t\t\t\t size_t what)\n>>> {\n>>> \tstruct string_list_item *ent;\n>>> \n>>> @@ -3823,7 +3823,7 @@ static uintptr_t register_symlink_changes(struct apply_state *state,\n>>> \t\tent = string_list_insert(&state->symlink_changes, path);\n>>> \t\tent->util = (void *)0;\n>>> \t}\n>>> -\tent->util = (void *)(what | ((uintptr_t)ent->util));\n>>> +\tent->util = (void *)((uintptr_t)what | ((uintptr_t)ent->util));\n>>> \treturn (uintptr_t)ent->util;\n>>> }\n>> \n>> I actually wonder if it results in code that is much easier to\n>> follow if we did:\n>> \n>> * Introduce an \"enum apply_symlink_treatment\" that has\n>> APPLY_SYMLINK_GOES_AWAY and APPLY_SYMLINK_IN_RESULT as its\n>> possible values;\n>> \n>> * Make register_symlink_changes() and check_symlink_changes()\n>> work with \"enum apply_symlink_treatment\";\n>> \n>> * (optional) stop using string_list() to store the symlink_changes;\n>> use strintmap and use strintmap_set() and strintmap_get() to\n>> access its entries, so that the ugly implementation detail\n>> (i.e. \"the container type we use only has a (void *) field to\n>> store caller-supplied data, so we cast an integer and a pointer\n>> back and forth\") can be safely hidden.\n>> \n> Or strsets -- we only need two.\n> \n> --- >8 ---\n> Subject: [PATCH] apply: use strsets to track symlinks\n> \n> Symlink changes are tracked in a string_list, with the util pointer\n> value indicating whether a symlink is kept or removed. Using fake\n> pointer values requires awkward casts. Use one strset for each type of\n> change instead to simplify and shorten the code.\n> \n> Original-patch-by: Jessica Clarke \n> Signed-off-by: René Scharfe \n\nThanks, this patch makes sense to me. Incidentally, seeing the bigger\npicture as a result of this patch touching everywhere that used that\nlist, I can see that in fact the existing code would have worked, just\nwith the compiler warning that something potentially iffy was going on.\nI had assumed ent->util was still sometimes storing an actual pointer,\nwith the low bits being used as flags, as many things tend to do, but\nin fact it was always NULL plus a couple of flag bits, so both sides of\nthe | always had the same bounds/permissions/tag, that of NULL (i.e.\ntag cleared as invalid, full bounds). This still looks like a nice\ncleanup though.\n\nJess\n\n> ---\n> apply.c | 42 ++++++++----------------------------------\n> apply.h | 26 +++++++++++---------------\n> 2 files changed, 19 insertions(+), 49 deletions(-)\n> \n> diff --git a/apply.c b/apply.c\n> index fed195250b..7deb4f79fd 100644\n> --- a/apply.c\n> +++ b/apply.c\n> @@ -103,7 +103,8 @@ int init_apply_state(struct apply_state *state,\n> \tstate->linenr = 1;\n> \tstring_list_init_nodup(&state->fn_table);\n> \tstring_list_init_nodup(&state->limit_by_name);\n> -\tstring_list_init_nodup(&state->symlink_changes);\n> +\tstrset_init(&state->removed_symlinks);\n> +\tstrset_init(&state->kept_symlinks);\n> \tstrbuf_init(&state->root, 0);\n> \n> \tgit_apply_config();\n> @@ -117,7 +118,8 @@ int init_apply_state(struct apply_state *state,\n> void clear_apply_state(struct apply_state *state)\n> {\n> \tstring_list_clear(&state->limit_by_name, 0);\n> -\tstring_list_clear(&state->symlink_changes, 0);\n> +\tstrset_clear(&state->removed_symlinks);\n> +\tstrset_clear(&state->kept_symlinks);\n> \tstrbuf_release(&state->root);\n> \n> \t/* &state->fn_table is cleared at the end of apply_patch() */\n> @@ -3812,59 +3814,31 @@ static int check_to_create(struct apply_state *state,\n> \treturn 0;\n> }\n> \n> -static uintptr_t register_symlink_changes(struct apply_state *state,\n> -\t\t\t\t\t const char *path,\n> -\t\t\t\t\t uintptr_t what)\n> -{\n> -\tstruct string_list_item *ent;\n> -\n> -\tent = string_list_lookup(&state->symlink_changes, path);\n> -\tif (!ent) {\n> -\t\tent = string_list_insert(&state->symlink_changes, path);\n> -\t\tent->util = (void *)0;\n> -\t}\n> -\tent->util = (void *)(what | ((uintptr_t)ent->util));\n> -\treturn (uintptr_t)ent->util;\n> -}\n> -\n> -static uintptr_t check_symlink_changes(struct apply_state *state, const char *path)\n> -{\n> -\tstruct string_list_item *ent;\n> -\n> -\tent = string_list_lookup(&state->symlink_changes, path);\n> -\tif (!ent)\n> -\t\treturn 0;\n> -\treturn (uintptr_t)ent->util;\n> -}\n> -\n> static void prepare_symlink_changes(struct apply_state *state, struct patch *patch)\n> {\n> \tfor ( ; patch; patch = patch->next) {\n> \t\tif ((patch->old_name && S_ISLNK(patch->old_mode)) &&\n> \t\t (patch->is_rename || patch->is_delete))\n> \t\t\t/* the symlink at patch->old_name is removed */\n> -\t\t\tregister_symlink_changes(state, patch->old_name, APPLY_SYMLINK_GOES_AWAY);\n> +\t\t\tstrset_add(&state->removed_symlinks, patch->old_name);\n> \n> \t\tif (patch->new_name && S_ISLNK(patch->new_mode))\n> \t\t\t/* the symlink at patch->new_name is created or remains */\n> -\t\t\tregister_symlink_changes(state, patch->new_name, APPLY_SYMLINK_IN_RESULT);\n> +\t\t\tstrset_add(&state->kept_symlinks, patch->new_name);\n> \t}\n> }\n> \n> static int path_is_beyond_symlink_1(struct apply_state *state, struct strbuf *name)\n> {\n> \tdo {\n> -\t\tunsigned int change;\n> -\n> \t\twhile (--name->len && name->buf[name->len] != '/')\n> \t\t\t; /* scan backwards */\n> \t\tif (!name->len)\n> \t\t\tbreak;\n> \t\tname->buf[name->len] = '\\0';\n> -\t\tchange = check_symlink_changes(state, name->buf);\n> -\t\tif (change & APPLY_SYMLINK_IN_RESULT)\n> +\t\tif (strset_contains(&state->kept_symlinks, name->buf))\n> \t\t\treturn 1;\n> -\t\tif (change & APPLY_SYMLINK_GOES_AWAY)\n> +\t\tif (strset_contains(&state->removed_symlinks, name->buf))\n> \t\t\t/*\n> \t\t\t * This cannot be \"return 0\", because we may\n> \t\t\t * see a new one created at a higher level.\n> diff --git a/apply.h b/apply.h\n> index 16202da160..4052da50c0 100644\n> --- a/apply.h\n> +++ b/apply.h\n> @@ -4,6 +4,7 @@\n> #include \"hash.h\"\n> #include \"lockfile.h\"\n> #include \"string-list.h\"\n> +#include \"strmap.h\"\n> \n> struct repository;\n> \n> @@ -25,20 +26,6 @@ enum apply_verbosity {\n> \tverbosity_verbose = 1\n> };\n> \n> -/*\n> - * We need to keep track of how symlinks in the preimage are\n> - * manipulated by the patches. A patch to add a/b/c where a/b\n> - * is a symlink should not be allowed to affect the directory\n> - * the symlink points at, but if the same patch removes a/b,\n> - * it is perfectly fine, as the patch removes a/b to make room\n> - * to create a directory a/b so that a/b/c can be created.\n> - *\n> - * See also \"struct string_list symlink_changes\" in \"struct\n> - * apply_state\".\n> - */\n> -#define APPLY_SYMLINK_GOES_AWAY 01\n> -#define APPLY_SYMLINK_IN_RESULT 02\n> -\n> struct apply_state {\n> \tconst char *prefix;\n> \n> @@ -86,7 +73,16 @@ struct apply_state {\n> \n> \t/* Various \"current state\" */\n> \tint linenr; /* current line number */\n> -\tstruct string_list symlink_changes; /* we have to track symlinks */\n> +\t/*\n> +\t * We need to keep track of how symlinks in the preimage are\n> +\t * manipulated by the patches. A patch to add a/b/c where a/b\n> +\t * is a symlink should not be allowed to affect the directory\n> +\t * the symlink points at, but if the same patch removes a/b,\n> +\t * it is perfectly fine, as the patch removes a/b to make room\n> +\t * to create a directory a/b so that a/b/c can be created.\n> +\t */\n> +\tstruct strset removed_symlinks;\n> +\tstruct strset kept_symlinks;\n> \n> \t/*\n> \t * For \"diff-stat\" like behaviour, we keep track of the biggest change\n> --\n> 2.34.1\n\n"},{"id":"445740","messageId":"xmqq35lz9vxl.fsf@gitster.g","threadId":"57186","inReplyTo":"8739caad-aa3d-1f0f-b5dd-6174a8e059f6@web.de","subject":"Re: [PATCH] apply: Avoid ambiguous pointer provenance for CHERI/Arm's Morello","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-07T19:40:06Z","receivedAt":"2022-01-07T19:40:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n>> I actually wonder if it results in code that is much easier to\n>> follow if we did:\n>>\n>> * Introduce an \"enum apply_symlink_treatment\" that has\n>> APPLY_SYMLINK_GOES_AWAY and APPLY_SYMLINK_IN_RESULT as its\n>> possible values;\n>>\n>> * Make register_symlink_changes() and check_symlink_changes()\n>> work with \"enum apply_symlink_treatment\";\n>>\n>> * (optional) stop using string_list() to store the symlink_changes;\n>> use strintmap and use strintmap_set() and strintmap_get() to\n>> access its entries, so that the ugly implementation detail\n>> (i.e. \"the container type we use only has a (void *) field to\n>> store caller-supplied data, so we cast an integer and a pointer\n>> back and forth\") can be safely hidden.\n>>\n> Or strsets -- we only need two.\n\nTrue.\n\nWhen we check a path, we make a single look-up of two bit in a\nsingle hashtable but now we need two look-ups, but addition, removal\nand renaming of a symlink would be rare enough to matter either way.\n\nWill queue; thanks.\n\n> --- >8 ---\n> Subject: [PATCH] apply: use strsets to track symlinks\n>\n> Symlink changes are tracked in a string_list, with the util pointer\n> value indicating whether a symlink is kept or removed. Using fake\n> pointer values requires awkward casts. Use one strset for each type of\n> change instead to simplify and shorten the code.\n>\n> Original-patch-by: Jessica Clarke \n> Signed-off-by: René Scharfe \n> ---\n> apply.c | 42 ++++++++----------------------------------\n> apply.h | 26 +++++++++++---------------\n> 2 files changed, 19 insertions(+), 49 deletions(-)\n>\n> diff --git a/apply.c b/apply.c\n> index fed195250b..7deb4f79fd 100644\n> --- a/apply.c\n> +++ b/apply.c\n> @@ -103,7 +103,8 @@ int init_apply_state(struct apply_state *state,\n> \tstate->linenr = 1;\n> \tstring_list_init_nodup(&state->fn_table);\n> \tstring_list_init_nodup(&state->limit_by_name);\n> -\tstring_list_init_nodup(&state->symlink_changes);\n> +\tstrset_init(&state->removed_symlinks);\n> +\tstrset_init(&state->kept_symlinks);\n> \tstrbuf_init(&state->root, 0);\n>\n> \tgit_apply_config();\n> @@ -117,7 +118,8 @@ int init_apply_state(struct apply_state *state,\n> void clear_apply_state(struct apply_state *state)\n> {\n> \tstring_list_clear(&state->limit_by_name, 0);\n> -\tstring_list_clear(&state->symlink_changes, 0);\n> +\tstrset_clear(&state->removed_symlinks);\n> +\tstrset_clear(&state->kept_symlinks);\n> \tstrbuf_release(&state->root);\n>\n> \t/* &state->fn_table is cleared at the end of apply_patch() */\n> @@ -3812,59 +3814,31 @@ static int check_to_create(struct apply_state *state,\n> \treturn 0;\n> }\n>\n> -static uintptr_t register_symlink_changes(struct apply_state *state,\n> -\t\t\t\t\t const char *path,\n> -\t\t\t\t\t uintptr_t what)\n> -{\n> -\tstruct string_list_item *ent;\n> -\n> -\tent = string_list_lookup(&state->symlink_changes, path);\n> -\tif (!ent) {\n> -\t\tent = string_list_insert(&state->symlink_changes, path);\n> -\t\tent->util = (void *)0;\n> -\t}\n> -\tent->util = (void *)(what | ((uintptr_t)ent->util));\n> -\treturn (uintptr_t)ent->util;\n> -}\n> -\n> -static uintptr_t check_symlink_changes(struct apply_state *state, const char *path)\n> -{\n> -\tstruct string_list_item *ent;\n> -\n> -\tent = string_list_lookup(&state->symlink_changes, path);\n> -\tif (!ent)\n> -\t\treturn 0;\n> -\treturn (uintptr_t)ent->util;\n> -}\n> -\n> static void prepare_symlink_changes(struct apply_state *state, struct patch *patch)\n> {\n> \tfor ( ; patch; patch = patch->next) {\n> \t\tif ((patch->old_name && S_ISLNK(patch->old_mode)) &&\n> \t\t (patch->is_rename || patch->is_delete))\n> \t\t\t/* the symlink at patch->old_name is removed */\n> -\t\t\tregister_symlink_changes(state, patch->old_name, APPLY_SYMLINK_GOES_AWAY);\n> +\t\t\tstrset_add(&state->removed_symlinks, patch->old_name);\n>\n> \t\tif (patch->new_name && S_ISLNK(patch->new_mode))\n> \t\t\t/* the symlink at patch->new_name is created or remains */\n> -\t\t\tregister_symlink_changes(state, patch->new_name, APPLY_SYMLINK_IN_RESULT);\n> +\t\t\tstrset_add(&state->kept_symlinks, patch->new_name);\n> \t}\n> }\n>\n> static int path_is_beyond_symlink_1(struct apply_state *state, struct strbuf *name)\n> {\n> \tdo {\n> -\t\tunsigned int change;\n> -\n> \t\twhile (--name->len && name->buf[name->len] != '/')\n> \t\t\t; /* scan backwards */\n> \t\tif (!name->len)\n> \t\t\tbreak;\n> \t\tname->buf[name->len] = '\\0';\n> -\t\tchange = check_symlink_changes(state, name->buf);\n> -\t\tif (change & APPLY_SYMLINK_IN_RESULT)\n> +\t\tif (strset_contains(&state->kept_symlinks, name->buf))\n> \t\t\treturn 1;\n> -\t\tif (change & APPLY_SYMLINK_GOES_AWAY)\n> +\t\tif (strset_contains(&state->removed_symlinks, name->buf))\n> \t\t\t/*\n> \t\t\t * This cannot be \"return 0\", because we may\n> \t\t\t * see a new one created at a higher level.\n> diff --git a/apply.h b/apply.h\n> index 16202da160..4052da50c0 100644\n> --- a/apply.h\n> +++ b/apply.h\n> @@ -4,6 +4,7 @@\n> #include \"hash.h\"\n> #include \"lockfile.h\"\n> #include \"string-list.h\"\n> +#include \"strmap.h\"\n>\n> struct repository;\n>\n> @@ -25,20 +26,6 @@ enum apply_verbosity {\n> \tverbosity_verbose = 1\n> };\n>\n> -/*\n> - * We need to keep track of how symlinks in the preimage are\n> - * manipulated by the patches. A patch to add a/b/c where a/b\n> - * is a symlink should not be allowed to affect the directory\n> - * the symlink points at, but if the same patch removes a/b,\n> - * it is perfectly fine, as the patch removes a/b to make room\n> - * to create a directory a/b so that a/b/c can be created.\n> - *\n> - * See also \"struct string_list symlink_changes\" in \"struct\n> - * apply_state\".\n> - */\n> -#define APPLY_SYMLINK_GOES_AWAY 01\n> -#define APPLY_SYMLINK_IN_RESULT 02\n> -\n> struct apply_state {\n> \tconst char *prefix;\n>\n> @@ -86,7 +73,16 @@ struct apply_state {\n>\n> \t/* Various \"current state\" */\n> \tint linenr; /* current line number */\n> -\tstruct string_list symlink_changes; /* we have to track symlinks */\n> +\t/*\n> +\t * We need to keep track of how symlinks in the preimage are\n> +\t * manipulated by the patches. A patch to add a/b/c where a/b\n> +\t * is a symlink should not be allowed to affect the directory\n> +\t * the symlink points at, but if the same patch removes a/b,\n> +\t * it is perfectly fine, as the patch removes a/b to make room\n> +\t * to create a directory a/b so that a/b/c can be created.\n> +\t */\n> +\tstruct strset removed_symlinks;\n> +\tstruct strset kept_symlinks;\n>\n> \t/*\n> \t * For \"diff-stat\" like behaviour, we keep track of the biggest change\n> --\n> 2.34.1\n"},{"id":"445761","messageId":"xmqq1r1j5dsy.fsf@gitster.g","threadId":"57186","inReplyTo":"8739caad-aa3d-1f0f-b5dd-6174a8e059f6@web.de","subject":"Re: [PATCH] apply: Avoid ambiguous pointer provenance for CHERI/Arm's Morello","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-07T23:25:17Z","receivedAt":"2022-01-07T23:25:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Subject: [PATCH] apply: use strsets to track symlinks\n>\n> Symlink changes are tracked in a string_list, with the util pointer\n> value indicating whether a symlink is kept or removed. Using fake\n> pointer values requires awkward casts. Use one strset for each type of\n> change instead to simplify and shorten the code.\n>\n> Original-patch-by: Jessica Clarke \n\nThis may be recording a misleading credit. The original patch\ncertainly was a good input to make us realize that we have a\nproblem, but has no contribution to the final code.\n\n> Signed-off-by: René Scharfe \n"},{"id":"445763","messageId":"4f05f434-7bd1-d563-94bd-607858deb1f8@web.de","threadId":"57186","inReplyTo":"xmqq35lz9vxl.fsf@gitster.g","subject":"Re: [PATCH] apply: Avoid ambiguous pointer provenance for CHERI/Arm's Morello","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-01-08T00:04:23Z","receivedAt":"2022-01-08T00:04:31Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 07.01.22 um 20:40 schrieb Junio C Hamano:\n> René Scharfe writes:\n>\n>>> I actually wonder if it results in code that is much easier to\n>>> follow if we did:\n>>>\n>>> * Introduce an \"enum apply_symlink_treatment\" that has\n>>> APPLY_SYMLINK_GOES_AWAY and APPLY_SYMLINK_IN_RESULT as its\n>>> possible values;\n>>>\n>>> * Make register_symlink_changes() and check_symlink_changes()\n>>> work with \"enum apply_symlink_treatment\";\n>>>\n>>> * (optional) stop using string_list() to store the symlink_changes;\n>>> use strintmap and use strintmap_set() and strintmap_get() to\n>>> access its entries, so that the ugly implementation detail\n>>> (i.e. \"the container type we use only has a (void *) field to\n>>> store caller-supplied data, so we cast an integer and a pointer\n>>> back and forth\") can be safely hidden.\n>>>\n>> Or strsets -- we only need two.\n>\n> True.\n>\n> When we check a path, we make a single look-up of two bit in a\n> single hashtable but now we need two look-ups, but addition, removal\n> and renaming of a symlink would be rare enough to matter either way.\n\nHmm, symlinks changes are rare, but this only affects the register phase\n(which should be noticeably slow for the string_list based code with its\nO(n*log(n)) lookup per registered symlink if there were a lot of them).\nBut the final lookups are done for each path _component_, of any file\ntype.\n\nI suspect that two lookups in (sparsely populated) hash tables are still\nfast enough. (At least I couldn't measure any difference with git apply\nand a patch between v2.33.0 and v2.34.0.)\n\nRené\n"},{"id":"445767","messageId":"xmqqsftz3v82.fsf@gitster.g","threadId":"57186","inReplyTo":"4f05f434-7bd1-d563-94bd-607858deb1f8@web.de","subject":"Re: [PATCH] apply: Avoid ambiguous pointer provenance for CHERI/Arm's Morello","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-08T00:51:57Z","receivedAt":"2022-01-08T00:52:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n>>> Or strsets -- we only need two.\n>>\n>> True.\n>>\n>> When we check a path, we make a single look-up of two bit in a\n>> single hashtable but now we need two look-ups, but addition, removal\n>> and renaming of a symlink would be rare enough to matter either way.\n>\n> Hmm, symlinks changes are rare, but this only affects the register phase\n> (which should be noticeably slow for the string_list based code with its\n> O(n*log(n)) lookup per registered symlink if there were a lot of them).\n> But the final lookups are done for each path _component_, of any file\n> type.\n>\n> I suspect that two lookups in (sparsely populated) hash tables are still\n> fast enough. (At least I couldn't measure any difference with git apply\n> and a patch between v2.33.0 and v2.34.0.)\n\nYup. I do not think it matters, and the resulting code is certainly\na lot simpler and easier to read ;-)\n\nThanks.\n"}]}