From: Junio C Hamano <hidden> Date: 2016-06-15 22:47:02
Linus Torvalds [off-list ref] writes:
We don't really verify the whole path when we mark things ce_uptodate().
Part of what read_directory() does is to find directory entries, and in
the process things like "git add" will notice if there's a conflict with
existing index entries.
So if a directory has changed into a symlink to a directory, this
particular optimization will actually hide that, I suspect. I haven't
tested, though. But it might be worth-while to see what happens when you
had a directory structure, and then do
mkdir dir
touch dir/a
touch dir/b
git add dir
mv dir new-dir
ln -s new-dir dir
git status
In existing codepaths, we have "has_symlink_leading_path()" checks to
notice that tracked dir/[ab] have disappeared. "git diff" before or after
"git status" in the above sequence does notice what you did.
Would dir/a be marked as uptodate in the index, if somebody preloads the
index, after the above sequence? I hope not.
Would dir/a be marked as uptodate in the index, if somebody preloads the
index, after the above sequence? I hope not.
Index preloading does not care about directories. It does the standard
if (ie_match_stat(index, ce, &st, CE_MATCH_RACY_IS_DIRTY))
continue;
and since it's all threaded (and the whole _point_ is that it's threaded),
it can't do anything fancier. Our lstat cache is _not_ thread-safe.
But preloading isn't even the only thing to do that. All the merge logics
also just do "ie_match_stat()", as does git checkout, although maybe the
directory gets validated separately for those cases before recursion.
Looking at "ce_mark_uptodate()", I think diff-lib.c is the only one that
actually does that whole "has_symlink_leading_path()" thing (in
"check_removed()").
I guess we could make out lstat cache thread-safe, and have the callers
pass in a per-thread "struct cache_def *". That would work well enough for
preloading (and everybody else could just use some random static one and
pass that in).
Added Kjetil to cc.
Linus
From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Thu, 9 Jul 2009 13:14:28 -0700
Subject: [PATCH 4/3] Avoid using 'lstat()' to figure out directories
If we have an up-to-date index entry for a file in that directory, we
can know that the directories leading up to that file must be
directories. No need to do an lstat() on the directory.
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
This is the patch I already sent out earlier. Now it's just numbered.
There's going to be an additional three patches to actually give the right
behavior for index preloading, so that we can really say "if CE_UPTODATE
is set, then the whole directory structure is valid".
dir.c | 47 ++++++++++++++++++++++++++++++++++++++++++-----
1 files changed, 42 insertions(+), 5 deletions(-)
@@ -566,18 +566,55 @@ static int in_pathspec(const char *path, int len, const struct path_simplify *sireturn0;}+staticintget_index_dtype(constchar*path,intlen)+{+intpos;+structcache_entry*ce;++ce=cache_name_exists(path,len,0);+if(ce){+if(!ce_uptodate(ce))+returnDT_UNKNOWN;+if(S_ISGITLINK(ce->ce_mode))+returnDT_DIR;+/*+*Nobodyactuallycaresaboutthe+*differencebetweenDT_LNKandDT_REG+*/+returnDT_REG;+}++/* Try to look it up as a directory */+pos=cache_name_pos(path,len);+if(pos>=0)+returnDT_UNKNOWN;+pos=-pos-1;+while(pos<active_nr){+ce=active_cache[pos++];+if(strncmp(ce->name,path,len))+break;+if(ce->name[len]>'/')+break;+if(ce->name[len]<'/')+continue;+if(!ce_uptodate(ce))+break;/* continue? */+returnDT_DIR;+}+returnDT_UNKNOWN;+}+staticintget_dtype(structdirent*de,constchar*path,intlen){intdtype=de?DTYPE(de):DT_UNKNOWN;-structcache_entry*ce;structstatst;if(dtype!=DT_UNKNOWN)returndtype;-ce=cache_name_exists(path,len,0);-if(ce&&ce_uptodate(ce))-st.st_mode=ce->ce_mode;-elseif(lstat(path,&st))+dtype=get_index_dtype(path,len);+if(dtype!=DT_UNKNOWN)+returndtype;+if(lstat(path,&st))returndtype;if(S_ISREG(st.st_mode))returnDT_REG;
From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Thu, 9 Jul 2009 13:23:59 -0700
Subject: [PATCH 5/3] Prepare symlink caching for thread-safety
This doesn't actually change the external interfaces, so they are still
thread-unsafe, but it makes the code internally pass a pointer to a
local 'struct cache_def' around, so that the core code can be made
thread-safe.
The threaded index preloading will want to verify that the paths leading
up to a pathname are all real directories.
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
No real changes, but I renamed the static 'cache' data structure
'default_cache', and made all the internal functions take a pointer
instead of using the static version.
The functions with external linkage are left semantically unchanged by
just making them do a simple
struct cache_def *cache = &default_cache;
and then using that.
symlinks.c | 75 ++++++++++++++++++++++++++++++++----------------------------
1 files changed, 40 insertions(+), 35 deletions(-)
From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Thu, 9 Jul 2009 13:35:31 -0700
Subject: [PATCH 6/3] Export thread-safe version of 'has_symlink_leading_path()'
The threaded index preloading will want it, so that it can avoid
locking by simply using a per-thread symlink/directory cache.
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
This just exposes a thread-safe version of the symlink checking by
allowing a caller to pass in its own local 'struct cache_def' to the
function.
No users of this yet, but the next step is trivial and obvious..
cache.h | 10 ++++++++++
symlinks.c | 21 ++++++++++-----------
2 files changed, 20 insertions(+), 11 deletions(-)
From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Thu, 9 Jul 2009 13:37:02 -0700
Subject: [PATCH 7/3] Make index preloading check the whole path to the file
This uses the new thread-safe 'threaded_has_symlink_leading_path()'
function to efficiently verify that the whole path leading up to the
filename is a proper path, and does not contain symlinks.
This makes 'ce_uptodate()' a much stronger guarantee: it no longer just
guarantees that the 'lstat()' of the path would match, it also means
that we know that people haven't played games with moving directories
around and covered it up with symlinks.
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
Totally trivial, now that we have a thread-safe symlink checker.
If we have leading symlinks in the cache-entry path, we will refuse to
mark it up-to-date. There's no need to even try to stat anything under
that directory.
preload-index.c | 3 +++
1 files changed, 3 insertions(+), 0 deletions(-)
Ok, with these patches, the strace of the index preload looks very clean,
and has the required tests for the directory components too:
...
26504 lstat("connect.c", {st_mode=S_IFREG|0664, st_size=14312, ...}) = 0
26504 lstat("contrib", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
26504 lstat("contrib/README", {st_mode=S_IFREG|0664, st_size=2113, ...}) = 0
26504 lstat("contrib/blameview", {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
26504 lstat("contrib/blameview/blameview.perl", {st_mode=S_IFREG|0775, st_size=3776, ...}) = 0
...
ie now it actualyl verifies that the directories leading up to filenames
are really directories by doing lstat() on them. And the symlink cache
means that it doesn't do it for every single pathname, only for the first
lookup per thread and directory.
Maybe Kjetil wants to check the changes, but quite frankly, it looked
pretty trivial to make that whole has_symlink_leading_path() be
thread-safe.
Linus
From: Paolo Bonzini <hidden> Date: 2016-06-15 22:47:02
+ if (ce->name[len]> '/')
+ break;
+ if (ce->name[len]< '/')
+ continue;
What about
if (ce->name[len] < '/') {
if (strchr(ce->name + len + 1, '/'))
break;
else
continue;
}
to just punt if we'd go into a directory? I'm not much worried about
accessing foo-0001, foo-0002, foo-0003 while looking for foo/a (that
would be O(number of files in a directory), which is bearable), but
risking to go down a huge subtree is not very nice.
Paolo
I'm not much worried about accessing foo-0001, foo-0002, foo-0003 while
looking for foo/a (that would be O(number of files in a directory),
which is bearable), but risking to go down a huge subtree is not very
nice.
That sounds rather unlikely, and the thing is, even if it were to happen,
it really wouldn't be that slow. Our data structures are pretty efficient,
and it wouldn't be _that_ slow to traverse them.
That said, I don't love that loop. It would be better to do that whole
cache_name_pos() call with the '/' simply appended to the path, and then
we'd do the binary search directly to the first entry.
Of course, since 'path' is a 'const char *', we'd need to either do a
silly copy, or we'd need to change a whole lot of the code to make it
clear that we can actually add a slash to the end (which we can: I think
it's already always going to be an array that we _will_ add a slash to in
case it turns out to be a directory).
So there's definitely room for improvement there. I just think that the
improvement isn't the patch you suggest.
Linus
Of course, since 'path' is a 'const char *', we'd need to either do a
silly copy, or we'd need to change a whole lot of the code to make it
clear that we can actually add a slash to the end (which we can: I think
it's already always going to be an array that we _will_ add a slash to in
case it turns out to be a directory).
No, I was wrong. We really do give it an array that we can't change
through the 'excluded()' function.
So we'd need to do the whole "copy name and add '/' at the end" thing. But
the upside would then be that after that, we'd not need any looping to
find the right ce. So it might be the right thing to do despite the
extra copy.
Linus
So we'd need to do the whole "copy name and add '/' at the end" thing. But
the upside would then be that after that, we'd not need any looping to
find the right ce. So it might be the right thing to do despite the
extra copy.
Naah. I did the numbers. For any normal repository, the 'loop' is going to
hit exactly once. Trying to be smarter about the initial binary search
isn't going to help, and copying the pathname around is only going to
hurt.
In the Linux repo, there's a small handful of cases like this, eg
- "arch/x86/vdso32"
arch/x86/vdso/vdso32-setup.c
arch/x86/vdso/vdso32.S
arch/x86/vdso/vdsp32/
- "drivers/scsi/megaraid"
drivers/scsi/megaraid.c
drivers/scsi/megaraid.h
drivers/scsi/megaraid/
- "include/linux/i2c"
include/linux/i2c-algo-bit.h
include/linux/i2c-algo-pca.h
include/linux/i2c-algo-pcf.h
include/linux/i2c-dev.h
include/linux/i2c-gpio.h
include/linux/i2c-id.h
include/linux/i2c-ocores.h
include/linux/i2c-pca-platform.h
include/linux/i2c-pnx.h
include/linux/i2c-pxa.h
include/linux/i2c.h
include/linux/i2c/
etc (for a total of 45 cases in the whole kernel, if I did my script
right), where we'd loop a few times. But we'd spend more effort trying to
avoid looping than we spend now on the loop.
Linus
From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Thu, 9 Jul 2009 13:35:31 -0700
Subject: [PATCH 6/3] Export thread-safe version of 'has_symlink_leading_path()'
The threaded index preloading will want it, so that it can avoid
locking by simply using a per-thread symlink/directory cache.
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
This just exposes a thread-safe version of the symlink checking by
allowing a caller to pass in its own local 'struct cache_def' to the
function.
No users of this yet, but the next step is trivial and obvious..
cache.h | 10 ++++++++++
symlinks.c | 21 ++++++++++-----------
2 files changed, 20 insertions(+), 11 deletions(-)
OK, to follow the style the 3 previous lstat_cache() calls was made
with (and also let the line length be less than 80), it should have
been written like this:
return lstat_cache(cache, name, len,
FL_SYMLINK|FL_DIR, USE_ONLY_LSTAT) &
FL_SYMLINK;
Notice that the parmeters which is just copied as arguments to l_c()
is in the same order and on the first line for it self. The next line
contains the rest of the arguments, and the &-part is also on it
a separate line.
Stylefix only, so not a big deal.
+}
+
+/*
+ * Return non-zero if path 'name' has a leading symlink component
+ */
int has_symlink_leading_path(const char *name, int len)
{
- struct cache_def *cache = &default_cache; /* FIXME */
This would make it inconsistent with the 2 has_*_() functions below,
which both have such a line. Only stylefix, no change in semantics.
I personally liked this line, since it will then be easier to
"threadify" the function with an extra parameter named "cache".
I have looked at and tested (the version from the origin/pu branch, so
it contains the memset() line squashed in) patch 5/3, 6/3 and 7/3, and
all 3 patches looks correct, so you can add
Reviewed-and-tested-by: Kjetil Barvik
if you want to.
But, I guess it is me which is a litle late to comment things, since I
already see that all 3 patches is in the pu, next and master branches
already, less than 3 days after beeing posted to the malinglist.
But, would'nt it be a good thing to let all patches at least be in the
pu branch for minimum x days before entering next and master? Or: let
it go minimum x days after beeing posted to the list before entering
the next and master branch? x = 4?
Since the patches is already in master and next, I guess it is not as
easy as if the patche(es) has been in pu to make a new version of a
patch, since both master and next is expected to be fast-forward
branches.
-- kjetil, which was too late this time, too :-)