apply: Avoid ambiguous pointer provenance for CHERI/Arm's Morello
PATCH 1/1 apply: Avoid ambiguous pointer provenance for CHERI/Arm's Morello
On CHERI, and thus Arm's Morello prototype, pointers are implemented as hardware capabilities which, as well as having a normal integer address, have additional bounds, permissions and other metadata in a second word. In order to preserve this metadata, uintptr_t is also implemented as a capability, not a plain integer, which causes problems for binary operators, as the metadata preserved in the output can only come from one of the inputs. In most cases this is clear, as normally at least one operand is provably a plain integer, but if both operands are uintptr_t and have no indication they're just plain integers then it is ambiguous, and the current implementation will arbitrarily, but deterministically, pick the left-hand side, due to empirical evidence that it is more likely to be correct.
In this instance, both operands are of type uintptr_t, with one being a function argument and one being cast from a pointer, so both could be valid pointers. Moreover, the left-hand side is not the actual pointer. This means that, currently, the code when run on a CHERI architecture will preserve the metadata from the integer, i.e. an invalid capability that will trap on deference, and not the pointer.
This can be addressed by changing the type of the function argument in order to more clearly convey intent, both to the compiler so it knows to generate the right code but also to the developer so it's clear that the argument is not in fact a pointer but just a plain integer (in this case being either APPLY_SYMLINK_GOES_AWAY or APPLY_SYMLINK_IN_RESULT).
--- apply.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
apply.c +2 -2
@@ -3814,7 +3814,7 @@ static int check_to_create(struct apply_state *state,static uintptr_t register_symlink_changes (struct apply_state *state,const char *path, -uintptr_t what) +size_t what) {struct string_list_item *ent;
@@ -3823,7 +3823,7 @@ static uintptr_t register_symlink_changes(struct apply_state *state, ent =string_list_insert (&state->symlink_changes, path); ent->util = (void *)0 ; } - ent->util = (void *)(what | ((uintptr_t )ent->util)); + ent->util = (void *)((uintptr_t )what | ((uintptr_t )ent->util));return (uintptr_t )ent->util; }
Signature · 1 line
2.33.1
On Wed, Jan 05, 2022 at 01:23:10PM +0000, Jessica Clarke wrote:
[...]
Quoted 3 lines
This means that, currently, the code when run on a CHERI architecture will preserve the metadata from the integer, i.e. an invalid capability that will trap on deference, and not the pointer.
^ You have probably meant to use "dereference" here.
Quoted 9 lines · Konstantin Khomoutov
On Wed, Jan 05, 2022 at 01:23:10PM +0000, Jessica Clarke wrote:
[...]
Quoted 3 lines
This means that, currently, the code when run on a CHERI architecture will preserve the metadata from the integer, i.e. an invalid capability that will trap on deference, and not the pointer.
^ You have probably meant to use "dereference" here.
Indeed I did; spellcheck doesn’t help for wrong words...
Should I send a v2, or can that be fixed on git-am?
Jess
Quoted 6 lines · Jessica Clarke
[...] In most cases this is clear, as normally at least one operand is provably a plain integer, but if both operands are
uintptr_tand have no indication they're just plain integers then it is ambiguous, and the current implementation will arbitrarily, but deterministically, pick the left-hand side, due to empirical evidence that it is more likely to be correct.
Wouldn't a simpler, less invasive fix be to instead write the expression so that the left-hand operand is a pointer? IOW, shouldn't the following work (with no other changes):
ent->util = (void *)((uintptr_t)what | ent->util);
?
(I dropped the explicit cast on the right-hand side, since ent->util is already a uintptr_t, and the left-hand side has an explicit cast, so there isn't any type promotion going on here).
Thanks,
Taylor
Quoted 13 lines · Taylor Blau
Quoted 6 lines · Jessica Clarke
[...] In most cases this is clear, as normally at least one operand is provably a plain integer, but if both operands are
uintptr_tand have no indication they're just plain integers then it is ambiguous, and the current implementation will arbitrarily, but deterministically, pick the left-hand side, due to empirical evidence that it is more likely to be correct.Wouldn't a simpler, less invasive fix be to instead write the expression so that the left-hand operand is a pointer? IOW, shouldn't the following work (with no other changes):
Quoted 7 lines
ent->util = (void *)((uintptr_t)what | ent->util);?
(I dropped the explicit cast on the right-hand side, since
ent->utilis already auintptr_t, and the left-hand side has an explicit cast, so there isn't any type promotion going on here).
That would still warn as it’s still ambiguous. It just happens that the arbitrary choice picks the right side. Better to clean up the code to remove the ambiguity and clarify it to the programmer.
Jess
Quoted 4 lines · Jessica Clarke
On CHERI, and thus Arm's Morello prototype, pointers are implemented as hardware capabilities which, as well as having a normal integer address, have additional bounds, permissions and other metadata in a second word. In order to preserve this metadata,
uintptr_tis also implemented as a
Quoted 8 lines
capability, not a plain integer, which causes problems for binary operators, as the metadata preserved in the output can only come from one of the inputs. In most cases this is clear, as normally at least one operand is provably a plain integer, but if both operands are
uintptr_tand have no indication they're just plain integers then it is ambiguous, and the current implementation will arbitrarily, but deterministically, pick the left-hand side, due to empirical evidence that it is more likely to be correct.
What's left-hand side in the context of the code you changed? Between "what" vs "ent->util" you take "what"? That cannot be true. Are you referring to the (usually hidden and useless when we use it as an integer) "hardware capabilities" word as "left" vs the value of the pointer as "right"?
Quoted 8 lines
static
uintptr_tregister_symlink_changes(structapply_state*state,apply.c +1
-1const char *path, - uintptr_t what) + size_t what) {struct string_list_item *ent;
apply.c static uintptr_t register_symlink_changes(struct apply_state *state, · line 3828
Quoted 7 lines
apply.c +1
-1@@ -3823,7 +3823,7 @@ static uintptr_t register_symlink_changes(struct apply_state *state, ent =string_list_insert (&state->symlink_changes, path); ent->util = (void *)0 ; } - ent->util = (void *)(what | ((uintptr_t )ent->util)); + ent->util = (void *)((uintptr_t )what | ((uintptr_t )ent->util));return (uintptr_t )ent->util; }
I actually wonder if it results in code that is much easier to follow if we did:
* Introduce an "enum apply_symlink_treatment" that has APPLY_SYMLINK_GOES_AWAY and APPLY_SYMLINK_IN_RESULT as its possible values;
* Make register_symlink_changes() and check_symlink_changes() work with "enum apply_symlink_treatment";
* (optional) stop using string_list() to store the symlink_changes; use strintmap and use strintmap_set() and strintmap_get() to access its entries, so that the ugly implementation detail (i.e. "the container type we use only has a (void *) field to store caller-supplied data, so we cast an integer and a pointer back and forth") can be safely hidden.
Quoted 16 lines · Junio C Hamano
Quoted 4 lines · Jessica Clarke
On CHERI, and thus Arm's Morello prototype, pointers are implemented as hardware capabilities which, as well as having a normal integer address, have additional bounds, permissions and other metadata in a second word. In order to preserve this metadata,
uintptr_tis also implemented as aQuoted 8 lines
capability, not a plain integer, which causes problems for binary operators, as the metadata preserved in the output can only come from one of the inputs. In most cases this is clear, as normally at least one operand is provably a plain integer, but if both operands are
uintptr_tand have no indication they're just plain integers then it is ambiguous, and the current implementation will arbitrarily, but deterministically, pick the left-hand side, due to empirical evidence that it is more likely to be correct.
Quoted 5 lines
What's left-hand side in the context of the code you changed? Between "what" vs "
ent->util" you take "what"? That cannot be true. Are you referring to the (usually hidden and useless when we use it as an integer) "hardware capabilities" word as "left" vs the value of the pointer as "right"?
Left-hand side is what, right-hand side is ((uintptr_t)ent->util). The bounds/permissions/tag/etc need to be inherited from somewhere, and as an arbitrary empirically-best choice when otherwise ambiguous we choose the left, i.e. what. The alternative would just be to error, which will result in strictly more code failing to build for CHERI despite such a guess being correct most of the time.
Quoted 26 lines
Quoted 8 lines
static
uintptr_tregister_symlink_changes(structapply_state*state,
const char *path,apply.c +1
-1- uintptr_t what) + size_t what){ struct string_list_item *ent;apply.c static uintptr_t register_symlink_changes(struct apply_state *state, · line 3828
Quoted 7 lines
apply.c +1
-1@@ -3823,7 +3823,7 @@ static uintptr_t register_symlink_changes(struct apply_state *state, ent =string_list_insert (&state->symlink_changes, path); ent->util = (void *)0 ; } - ent->util = (void *)(what | ((uintptr_t )ent->util)); + ent->util = (void *)((uintptr_t )what | ((uintptr_t )ent->util));return (uintptr_t )ent->util; }I actually wonder if it results in code that is much easier to follow if we did:
* Introduce an "enum
apply_symlink_treatment" that hasAPPLY_SYMLINK_GOES_AWAYandAPPLY_SYMLINK_IN_RESULTas its possible values;* Make
register_symlink_changes()andcheck_symlink_changes()work with "enumapply_symlink_treatment";
Quoted 6 lines
* (optional) stop using
string_list()to store thesymlink_changes; use strintmap and usestrintmap_set()andstrintmap_get()to access its entries, so that the ugly implementation detail (i.e. "the container type we use only has a (void *) field to store caller-supplied data, so we cast an integer and a pointer back and forth") can be safely hidden.
Those would be better if you want a less-minimal change. I can easily do the first two, but the last one may or may not take me a while to figure out given I’m not familiar with git’s C internals.
Jess
Quoted 10 lines · Jessica Clarke
Quoted 10 lines
I actually wonder if it results in code that is much easier to follow if we did:
* Introduce an "enum
apply_symlink_treatment" that hasAPPLY_SYMLINK_GOES_AWAYandAPPLY_SYMLINK_IN_RESULTas its possible values;* Make
register_symlink_changes()andcheck_symlink_changes()work with "enumapply_symlink_treatment";
Quoted 8 lines
Quoted 6 lines
* (optional) stop using
string_list()to store thesymlink_changes; use strintmap and usestrintmap_set()andstrintmap_get()to access its entries, so that the ugly implementation detail (i.e. "the container type we use only has a (void *) field to store caller-supplied data, so we cast an integer and a pointer back and forth") can be safely hidden.Those would be better if you want a less-minimal change.
The first two at least would make an understandable change, as opposed to the code as posted, which is totally opaque why we need to take size_t and cast it to uintptr_t in the first place.
I have no confidence in myself that I would not accept a future patch that reverts the change made by this patch happily. I usually try to be careful to go back to the originating commit by running "blame" on the preimage and may find your commit, but that's only "usually". If I were to work only with the file contents after applying this patch, because no clue ...
ent->util = (void *)((uintptr_t)what | ((uintptr_t)ent->util));
... on this line of code hints why we must be called with size_t and have to cast it here, instead of working with uintptr_t throughout, I am reasonably sure I'd happily take such a patch and break your "fix" here.
If we make the code pass around the enum, have a temporary variable of the same enum type to compute the next value we stuff in ent->util, and make an assignment of that enum value to ent->util, it is much less likely that I'd blindly accept a patch to take us back to deal with uintptr_t directly.
Am 06.01.22 um 23:53 schrieb Junio C Hamano:
Quoted 47 lines
Quoted 4 lines · Jessica Clarke
On CHERI, and thus Arm's Morello prototype, pointers are implemented as hardware capabilities which, as well as having a normal integer address, have additional bounds, permissions and other metadata in a second word. In order to preserve this metadata,
uintptr_tis also implemented as aQuoted 8 lines
capability, not a plain integer, which causes problems for binary operators, as the metadata preserved in the output can only come from one of the inputs. In most cases this is clear, as normally at least one operand is provably a plain integer, but if both operands are
uintptr_tand have no indication they're just plain integers then it is ambiguous, and the current implementation will arbitrarily, but deterministically, pick the left-hand side, due to empirical evidence that it is more likely to be correct.What's left-hand side in the context of the code you changed? Between "what" vs "
ent->util" you take "what"? That cannot be true. Are you referring to the (usually hidden and useless when we use it as an integer) "hardware capabilities" word as "left" vs the value of the pointer as "right"?Quoted 8 lines
static
uintptr_tregister_symlink_changes(structapply_state*state,(quoted diff) +1
-1const char *path, - uintptr_t what) + size_t what) { struct string_list_item *ent;Review static uintptr_t register_symlink_changes(struct apply_state *state, · line 3828
Quoted 7 lines
(quoted diff) +1
-1@@ -3823,7 +3823,7 @@ static uintptr_t register_symlink_changes(struct apply_state *state, ent = string_list_insert(&state->symlink_changes, path); ent->util = (void *)0; } - ent->util = (void *)(what | ((uintptr_t)ent->util)); + ent->util = (void *)((uintptr_t)what | ((uintptr_t)ent->util)); return (uintptr_t)ent->util; }I actually wonder if it results in code that is much easier to follow if we did:
* Introduce an "enum
apply_symlink_treatment" that hasAPPLY_SYMLINK_GOES_AWAYandAPPLY_SYMLINK_IN_RESULTas its possible values;* Make
register_symlink_changes()andcheck_symlink_changes()work with "enumapply_symlink_treatment";
Quoted 7 lines
* (optional) stop using
string_list()to store thesymlink_changes; use strintmap and usestrintmap_set()andstrintmap_get()to access its entries, so that the ugly implementation detail (i.e. "the container type we use only has a (void *) field to store caller-supplied data, so we cast an integer and a pointer back and forth") can be safely hidden.
Or strsets -- we only need two.
--- >8 ---
Subject: [PATCH] apply: use strsets to track symlinks
Symlink changes are tracked in a string_list, with the util pointer value indicating whether a symlink is kept or removed. Using fake pointer values requires awkward casts. Use one strset for each type of change instead to simplify and shorten the code.
--- apply.c | 42 ++++++++---------------------------------- apply.h | 26 +++++++++++--------------- 2 files changed, 19 insertions(+), 49 deletions(-)
apply.c +8 -34
@@ -103,7 +103,8 @@ int init_apply_state(struct apply_state *state, state->linenr =1 ;string_list_init_nodup (&state->fn_table);string_list_init_nodup (&state->limit_by_name); -string_list_init_nodup (&state->symlink_changes); +strset_init (&state->removed_symlinks); +strset_init (&state->kept_symlinks);strbuf_init (&state->root,0 );git_apply_config ();
@@ -117,7 +118,8 @@ int init_apply_state(struct apply_state *state,void clear_apply_state (struct apply_state *state) {string_list_clear (&state->limit_by_name,0 ); -string_list_clear (&state->symlink_changes,0 ); +strset_clear (&state->removed_symlinks); +strset_clear (&state->kept_symlinks);strbuf_release (&state->root);/* &state->fn_table is cleared at the end of apply_patch() */
@@ -3812,59 +3814,31 @@ static int check_to_create(struct apply_state *state,return 0 ; } -static uintptr_t register_symlink_changes (struct apply_state *state, -const char *path, -uintptr_t what) -{ -struct string_list_item *ent; - - ent =string_list_lookup (&state->symlink_changes, path); -if (!ent) { - ent =string_list_insert (&state->symlink_changes, path); - ent->util = (void *)0 ; - } - ent->util = (void *)(what | ((uintptr_t )ent->util)); -return (uintptr_t )ent->util; -} - -static uintptr_t check_symlink_changes (struct apply_state *state,const char *path) -{ -struct string_list_item *ent; - - ent =string_list_lookup (&state->symlink_changes, path); -if (!ent) -return 0 ; -return (uintptr_t )ent->util; -} -static void prepare_symlink_changes (struct apply_state *state,struct patch *patch) {for ( ; patch; patch = patch->next) {if ((patch->old_name &&S_ISLNK (patch->old_mode)) && (patch->is_rename || patch->is_delete))/* the symlink at patch->old_name is removed */ -register_symlink_changes (state, patch->old_name,APPLY_SYMLINK_GOES_AWAY ); +strset_add (&state->removed_symlinks, patch->old_name);if (patch->new_name &&S_ISLNK (patch->new_mode))/* the symlink at patch->new_name is created or remains */ -register_symlink_changes (state, patch->new_name,APPLY_SYMLINK_IN_RESULT ); +strset_add (&state->kept_symlinks, patch->new_name); } }static int path_is_beyond_symlink_1 (struct apply_state *state,struct strbuf *name) { do { - unsigned int change; - while (--name->len && name->buf[name->len] != '/') ; /* scan backwards */ if (!name->len) break; name->buf[name->len] = '\0'; - change = check_symlink_changes(state, name->buf); - if (change & APPLY_SYMLINK_IN_RESULT) + if (strset_contains(&state->kept_symlinks, name->buf)) return 1; - if (change & APPLY_SYMLINK_GOES_AWAY) + if (strset_contains(&state->removed_symlinks, name->buf)) /* * This cannot be "return 0", because we may * see a new one created at a higher level.
apply.h +11 -15
@@ -4,6 +4,7 @@#include "hash.h" #include "lockfile.h" #include "string-list.h" +#include "strmap.h" struct repository ;
@@ -25,20 +26,6 @@ enum apply_verbosity { verbosity_verbose =1 }; -/* -* We need to keep track of how symlinks in the preimage are -* manipulated by the patches. A patch to add a/b/c where a/b -* is a symlink should not be allowed to affect the directory -* the symlink points at, but if the same patch removes a/b, -* it is perfectly fine, as the patch removes a/b to make room -* to create a directory a/b so that a/b/c can be created. -* -* See also "struct string_list symlink_changes" in "struct -* apply_state". -*/ -#define APPLY_SYMLINK_GOES_AWAY 01 -#define APPLY_SYMLINK_IN_RESULT 02 -struct apply_state {const char *prefix;
@@ -86,7 +73,16 @@ struct apply_state {/* Various "current state" */ int linenr;/* current line number */ -struct string_list symlink_changes;/* we have to track symlinks */ +/* +* We need to keep track of how symlinks in the preimage are +* manipulated by the patches. A patch to add a/b/c where a/b +* is a symlink should not be allowed to affect the directory +* the symlink points at, but if the same patch removes a/b, +* it is perfectly fine, as the patch removes a/b to make room +* to create a directory a/b so that a/b/c can be created. +*/ +struct strset removed_symlinks; +struct strset kept_symlinks;/* * For "diff-stat" like behaviour, we keep track of the biggest change
--
2.34.1
Quoted 61 lines · René Scharfe
Am 06.01.22 um 23:53 schrieb Junio C Hamano:
Quoted 47 lines
Quoted 4 lines · Jessica Clarke
On CHERI, and thus Arm's Morello prototype, pointers are implemented as hardware capabilities which, as well as having a normal integer address, have additional bounds, permissions and other metadata in a second word. In order to preserve this metadata,
uintptr_tis also implemented as aQuoted 8 lines
capability, not a plain integer, which causes problems for binary operators, as the metadata preserved in the output can only come from one of the inputs. In most cases this is clear, as normally at least one operand is provably a plain integer, but if both operands are
uintptr_tand have no indication they're just plain integers then it is ambiguous, and the current implementation will arbitrarily, but deterministically, pick the left-hand side, due to empirical evidence that it is more likely to be correct.What's left-hand side in the context of the code you changed? Between "what" vs "
ent->util" you take "what"? That cannot be true. Are you referring to the (usually hidden and useless when we use it as an integer) "hardware capabilities" word as "left" vs the value of the pointer as "right"?Quoted 8 lines
static
uintptr_tregister_symlink_changes(structapply_state*state,
const char *path,(quoted diff) +1
-1- uintptr_t what) + size_t what){ struct string_list_item *ent;Review static uintptr_t register_symlink_changes(struct apply_state *state, · line 3828
Quoted 7 lines
(quoted diff) +1
-1@@ -3823,7 +3823,7 @@ static uintptr_t register_symlink_changes(struct apply_state *state, ent = string_list_insert(&state->symlink_changes, path); ent->util = (void *)0; } - ent->util = (void *)(what | ((uintptr_t)ent->util)); + ent->util = (void *)((uintptr_t)what | ((uintptr_t)ent->util)); return (uintptr_t)ent->util; }I actually wonder if it results in code that is much easier to follow if we did:
* Introduce an "enum
apply_symlink_treatment" that hasAPPLY_SYMLINK_GOES_AWAYandAPPLY_SYMLINK_IN_RESULTas its possible values;* Make
register_symlink_changes()andcheck_symlink_changes()work with "enumapply_symlink_treatment";Quoted 7 lines
* (optional) stop using
string_list()to store thesymlink_changes; use strintmap and usestrintmap_set()andstrintmap_get()to access its entries, so that the ugly implementation detail (i.e. "the container type we use only has a (void *) field to store caller-supplied data, so we cast an integer and a pointer back and forth") can be safely hidden.Or strsets -- we only need two.
--- >8 ---
Subject: [PATCH] apply: use strsets to track symlinks
Quoted 7 lines
Symlink changes are tracked in a
string_list, with the util pointer value indicating whether a symlink is kept or removed. Using fake pointer values requires awkward casts. Use one strset for each type of change instead to simplify and shorten the code.Original-patch-by Jessica Clarke <[email protected]>Signed-off-by René Scharfe <[email protected]>
Thanks, this patch makes sense to me. Incidentally, seeing the bigger picture as a result of this patch touching everywhere that used that list, I can see that in fact the existing code would have worked, just with the compiler warning that something potentially iffy was going on. I had assumed ent->util was still sometimes storing an actual pointer, with the low bits being used as flags, as many things tend to do, but in fact it was always NULL plus a couple of flag bits, so both sides of the | always had the same bounds/permissions/tag, that of NULL (i.e. tag cleared as invalid, full bounds). This still looks like a nice cleanup though.
Jess
Quoted 146 lines
---
apply.c| 42 ++++++++----------------------------------apply.h| 26 +++++++++++---------------2 files changed, 19 insertions(+), 49 deletions(-)apply.c +8
-34@@ -103,7 +103,8 @@ int init_apply_state(struct apply_state *state, state->linenr =1 ;string_list_init_nodup (&state->fn_table);string_list_init_nodup (&state->limit_by_name); -string_list_init_nodup (&state->symlink_changes); +strset_init (&state->removed_symlinks); +strset_init (&state->kept_symlinks);strbuf_init (&state->root,0 );git_apply_config ();@@ -117,7 +118,8 @@ int init_apply_state(struct apply_state *state,void clear_apply_state (struct apply_state *state) {string_list_clear (&state->limit_by_name,0 ); -string_list_clear (&state->symlink_changes,0 ); +strset_clear (&state->removed_symlinks); +strset_clear (&state->kept_symlinks);strbuf_release (&state->root);/* &state->fn_table is cleared at the end of apply_patch() */ @@ -3812,59 +3814,31 @@ static int check_to_create(struct apply_state *state,return 0 ; } -static uintptr_t register_symlink_changes (struct apply_state *state, -const char *path, -uintptr_t what) -{ -struct string_list_item *ent; - - ent =string_list_lookup (&state->symlink_changes, path); -if (!ent) { - ent =string_list_insert (&state->symlink_changes, path); - ent->util = (void *)0 ; - } - ent->util = (void *)(what | ((uintptr_t )ent->util)); -return (uintptr_t )ent->util; -} - -static uintptr_t check_symlink_changes (struct apply_state *state,const char *path) -{ -struct string_list_item *ent; - - ent =string_list_lookup (&state->symlink_changes, path); -if (!ent) -return 0 ; -return (uintptr_t )ent->util; -} -static void prepare_symlink_changes (struct apply_state *state,struct patch *patch) {for ( ; patch; patch = patch->next) {if ((patch->old_name &&S_ISLNK (patch->old_mode)) && (patch->is_rename || patch->is_delete))/* the symlink at patch->old_name is removed */ -register_symlink_changes (state, patch->old_name,APPLY_SYMLINK_GOES_AWAY ); +strset_add (&state->removed_symlinks, patch->old_name);if (patch->new_name &&S_ISLNK (patch->new_mode))/* the symlink at patch->new_name is created or remains */ -register_symlink_changes (state, patch->new_name,APPLY_SYMLINK_IN_RESULT ); +strset_add (&state->kept_symlinks, patch->new_name); } }static int path_is_beyond_symlink_1 (struct apply_state *state,struct strbuf *name) { do { - unsigned int change; - while (--name->len && name->buf[name->len] != '/') ; /* scan backwards */ if (!name->len) break; name->buf[name->len] = '\0'; - change = check_symlink_changes(state, name->buf); - if (change & APPLY_SYMLINK_IN_RESULT) + if (strset_contains(&state->kept_symlinks, name->buf)) return 1; - if (change & APPLY_SYMLINK_GOES_AWAY) + if (strset_contains(&state->removed_symlinks, name->buf)) /* * This cannot be "return 0", because we may * see a new one created at a higher level.apply.h +11
-16@@ -4,6 +4,7 @@#include "hash.h" #include "lockfile.h" #include "string-list.h" +#include "strmap.h" struct repository ;@@ -25,20 +26,6 @@ enum apply_verbosity { verbosity_verbose =1 }; -/* -* We need to keep track of how symlinks in the preimage are -* manipulated by the patches. A patch to add a/b/c where a/b -* is a symlink should not be allowed to affect the directory -* the symlink points at, but if the same patch removes a/b, -* it is perfectly fine, as the patch removes a/b to make room -* to create a directory a/b so that a/b/c can be created. -* -* See also "struct string_list symlink_changes" in "struct -* apply_state". -*/ -#define APPLY_SYMLINK_GOES_AWAY 01 -#define APPLY_SYMLINK_IN_RESULT 02 -struct apply_state {const char *prefix;@@ -86,7 +73,16 @@ struct apply_state {/* Various "current state" */ int linenr;/* current line number */ -struct string_list symlink_changes;/* we have to track symlinks */ +/* +* We need to keep track of how symlinks in the preimage are +* manipulated by the patches. A patch to add a/b/c where a/b +* is a symlink should not be allowed to affect the directory +* the symlink points at, but if the same patch removes a/b, +* it is perfectly fine, as the patch removes a/b to make room +* to create a directory a/b so that a/b/c can be created. +*/ +struct strset removed_symlinks; +struct strset kept_symlinks;/* * For "diff-stat" like behaviour, we keep track of the biggest change -- 2.34.1
Quoted 10 lines · René Scharfe
Quoted 10 lines
I actually wonder if it results in code that is much easier to follow if we did:
* Introduce an "enum
apply_symlink_treatment" that hasAPPLY_SYMLINK_GOES_AWAYandAPPLY_SYMLINK_IN_RESULTas its possible values;* Make
register_symlink_changes()andcheck_symlink_changes()work with "enumapply_symlink_treatment";
Quoted 8 lines
Quoted 7 lines
* (optional) stop using
string_list()to store thesymlink_changes; use strintmap and usestrintmap_set()andstrintmap_get()to access its entries, so that the ugly implementation detail (i.e. "the container type we use only has a (void *) field to store caller-supplied data, so we cast an integer and a pointer back and forth") can be safely hidden.Or strsets -- we only need two.
True.
When we check a path, we make a single look-up of two bit in a single hashtable but now we need two look-ups, but addition, removal and renaming of a symlink would be rare enough to matter either way.
Will queue; thanks.
Quoted 156 lines
--- >8 ---
Subject: [PATCH] apply: use strsets to track symlinksSymlink changes are tracked in a
string_list, with the util pointer value indicating whether a symlink is kept or removed. Using fake pointer values requires awkward casts. Use one strset for each type of change instead to simplify and shorten the code.Original-patch-by Jessica Clarke <[email protected]>Signed-off-by René Scharfe <[email protected]>--- apply.c | 42 ++++++++---------------------------------- apply.h | 26 +++++++++++--------------- 2 files changed, 19 insertions(+), 49 deletions(-)apply.c +8
-34@@ -103,7 +103,8 @@ int init_apply_state(struct apply_state *state, state->linenr =1 ;string_list_init_nodup (&state->fn_table);string_list_init_nodup (&state->limit_by_name); -string_list_init_nodup (&state->symlink_changes); +strset_init (&state->removed_symlinks); +strset_init (&state->kept_symlinks);strbuf_init (&state->root,0 );git_apply_config ();@@ -117,7 +118,8 @@ int init_apply_state(struct apply_state *state,void clear_apply_state (struct apply_state *state) {string_list_clear (&state->limit_by_name,0 ); -string_list_clear (&state->symlink_changes,0 ); +strset_clear (&state->removed_symlinks); +strset_clear (&state->kept_symlinks);strbuf_release (&state->root);/* &state->fn_table is cleared at the end of apply_patch() */ @@ -3812,59 +3814,31 @@ static int check_to_create(struct apply_state *state,return 0 ; } -static uintptr_t register_symlink_changes (struct apply_state *state, -const char *path, -uintptr_t what) -{ -struct string_list_item *ent; - - ent =string_list_lookup (&state->symlink_changes, path); -if (!ent) { - ent =string_list_insert (&state->symlink_changes, path); - ent->util = (void *)0 ; - } - ent->util = (void *)(what | ((uintptr_t )ent->util)); -return (uintptr_t )ent->util; -} - -static uintptr_t check_symlink_changes (struct apply_state *state,const char *path) -{ -struct string_list_item *ent; - - ent =string_list_lookup (&state->symlink_changes, path); -if (!ent) -return 0 ; -return (uintptr_t )ent->util; -} -static void prepare_symlink_changes (struct apply_state *state,struct patch *patch) {for ( ; patch; patch = patch->next) {if ((patch->old_name &&S_ISLNK (patch->old_mode)) && (patch->is_rename || patch->is_delete))/* the symlink at patch->old_name is removed */ -register_symlink_changes (state, patch->old_name,APPLY_SYMLINK_GOES_AWAY ); +strset_add (&state->removed_symlinks, patch->old_name);if (patch->new_name &&S_ISLNK (patch->new_mode))/* the symlink at patch->new_name is created or remains */ -register_symlink_changes (state, patch->new_name,APPLY_SYMLINK_IN_RESULT ); +strset_add (&state->kept_symlinks, patch->new_name); } }static int path_is_beyond_symlink_1 (struct apply_state *state,struct strbuf *name) { do { - unsigned int change; - while (--name->len && name->buf[name->len] != '/') ; /* scan backwards */ if (!name->len) break; name->buf[name->len] = '\0'; - change = check_symlink_changes(state, name->buf); - if (change & APPLY_SYMLINK_IN_RESULT) + if (strset_contains(&state->kept_symlinks, name->buf)) return 1; - if (change & APPLY_SYMLINK_GOES_AWAY) + if (strset_contains(&state->removed_symlinks, name->buf)) /* * This cannot be "return 0", because we may * see a new one created at a higher level.apply.h +11
-16@@ -4,6 +4,7 @@#include "hash.h" #include "lockfile.h" #include "string-list.h" +#include "strmap.h" struct repository ;@@ -25,20 +26,6 @@ enum apply_verbosity { verbosity_verbose =1 }; -/* -* We need to keep track of how symlinks in the preimage are -* manipulated by the patches. A patch to add a/b/c where a/b -* is a symlink should not be allowed to affect the directory -* the symlink points at, but if the same patch removes a/b, -* it is perfectly fine, as the patch removes a/b to make room -* to create a directory a/b so that a/b/c can be created. -* -* See also "struct string_list symlink_changes" in "struct -* apply_state". -*/ -#define APPLY_SYMLINK_GOES_AWAY 01 -#define APPLY_SYMLINK_IN_RESULT 02 -struct apply_state {const char *prefix;@@ -86,7 +73,16 @@ struct apply_state {/* Various "current state" */ int linenr;/* current line number */ -struct string_list symlink_changes;/* we have to track symlinks */ +/* +* We need to keep track of how symlinks in the preimage are +* manipulated by the patches. A patch to add a/b/c where a/b +* is a symlink should not be allowed to affect the directory +* the symlink points at, but if the same patch removes a/b, +* it is perfectly fine, as the patch removes a/b to make room +* to create a directory a/b so that a/b/c can be created. +*/ +struct strset removed_symlinks; +struct strset kept_symlinks;/* * For "diff-stat" like behaviour, we keep track of the biggest change -- 2.34.1
Am 07.01.22 um 20:40 schrieb Junio C Hamano:
Quoted 19 lines
Quoted 17 lines · René Scharfe
Quoted 17 lines
I actually wonder if it results in code that is much easier to follow if we did:
* Introduce an "enum
apply_symlink_treatment" that hasAPPLY_SYMLINK_GOES_AWAYandAPPLY_SYMLINK_IN_RESULTas its possible values;* Make
register_symlink_changes()andcheck_symlink_changes()work with "enumapply_symlink_treatment";* (optional) stop using
string_list()to store thesymlink_changes; use strintmap and usestrintmap_set()andstrintmap_get()to access its entries, so that the ugly implementation detail (i.e. "the container type we use only has a (void *) field to store caller-supplied data, so we cast an integer and a pointer back and forth") can be safely hidden.
Quoted 7 lines
Quoted 1 line
Or strsets -- we only need two.
True.
When we check a path, we make a single look-up of two bit in a single hashtable but now we need two look-ups, but addition, removal and renaming of a symlink would be rare enough to matter either way.
Hmm, symlinks changes are rare, but this only affects the register phase (which should be noticeably slow for the string_list based code with its O(n*log(n)) lookup per registered symlink if there were a lot of them). But the final lookups are done for each path _component_, of any file type.
I suspect that two lookups in (sparsely populated) hash tables are still fast enough. (At least I couldn't measure any difference with git apply and a patch between v2.33.0 and v2.34.0.)
René
Quoted 14 lines · René Scharfe
Quoted 7 lines
Quoted 1 line
Or strsets -- we only need two.
True.
When we check a path, we make a single look-up of two bit in a single hashtable but now we need two look-ups, but addition, removal and renaming of a symlink would be rare enough to matter either way.
Hmm, symlinks changes are rare, but this only affects the register phase (which should be noticeably slow for the
string_listbased code with its O(n*log(n)) lookup per registered symlink if there were a lot of them). But the final lookups are done for each path _component_, of any file type.
Quoted 3 lines
I suspect that two lookups in (sparsely populated) hash tables are still fast enough. (At least I couldn't measure any difference with git apply and a patch between v2.33.0 and v2.34.0.)
Yup. I do not think it matters, and the resulting code is certainly a lot simpler and easier to read ;-)
Thanks.
Quoted 8 lines · René Scharfe
Subject: [PATCH] apply: use strsets to track symlinks
Symlink changes are tracked in a
string_list, with the util pointer value indicating whether a symlink is kept or removed. Using fake pointer values requires awkward casts. Use one strset for each type of change instead to simplify and shorten the code.Original-patch-by Jessica Clarke <[email protected]>
This may be recording a misleading credit. The original patch certainly was a good input to make us realize that we have a problem, but has no contribution to the final code.
Quoted 1 line
Signed-off-by René Scharfe <[email protected]>