Re: inotify to minimize stat() calls
Am 13.02.2013 23:55, schrieb Jeff King:
Show 18 quoted lines
> On Wed, Feb 13, 2013 at 09:25:59PM +0100, Karsten Blees wrote:
>
>> Alternatively, we could simply create normal cache_entries for the
>> directories that are linked via ce->next, but have a trailing '/' in
>> their name?
>>
>> Reference counting sounds good to me, at least better than allocating
>> directory entries per cache entry * parent dirs.
>
> I think that is more or less what my patch does, but it splits the
> ref-counted fake cache_entries out into a separate hash of "struct
> dir_hash_entry" rather than storing it in the regular hash. Which IMHO
> is a bit cleaner for two reasons:
>
> 1. You do not have to pay the memory price of storing fake
> cache_entries (the name+refcount struct for each directory is much
> smaller than a real cache_entry).
>
Yes, but considering the small number of directories compared to files, I think this is a relatively small price to pay.
> 2. It makes the code a bit simpler, as you do not have to do any
> "check for trailing /" magic on the result of index_name_exists to
> determine if it is a "real" name or just a fake dir entry.
>
True for dir.c. On the other hand, you need a lot of new find / find_or_create logic in name-hash.c.
Just to illustrate what I mean, here's a quick sketch (there's still a segfault somewhere, but I don't have time to debug right now...).
Note that hash_index_entry_directories works from right to left - if the immediate parent directory is there, there's no need to check the parent's parent.
cache_entry.dir points to the parent directory so that we don't need to lookup all path components for reference counting when adding / removing entries.
As directory entries are 'real' cache_entries, we can reuse the existing index_name_exists and hash_index_entry code.
I feel slightly guilty for abusing ce_size as reference counter...well :-)
---
cache.h | 4 +++-
name-hash.c | 80 ++++++++++++++++++++++++++++---------------------------------
2 files changed, 39 insertions(+), 45 deletions(-)
diff --git a/cache.h b/cache.h
index 665b512..2bc1372 100644
--- a/cache.h
+++ b/cache.h
@@ -131,7 +131,7 @@ struct cache_entry {
unsigned int ce_namelen;
unsigned char sha1[20];
struct cache_entry *next;
- struct cache_entry *dir_next;
+ struct cache_entry *dir;
char name[FLEX_ARRAY]; /* more */
};
@@ -285,6 +285,8 @@ extern void add_name_hash(struct index_state *istate, struct cache_entry *ce);
static inline void remove_name_hash(struct cache_entry *ce)
{
ce->ce_flags |= CE_UNHASHED;
+ if (ce->dir && !(--ce->dir->ce_size))
+ remove_name_hash(ce->dir);
}
diff --git a/name-hash.c b/name-hash.c
index d8d25c2..01e8320 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -32,6 +32,9 @@ static unsigned int hash_name(const char *name, int namelen)
return hash;
}
+static struct cache_entry *lookup_index_entry(struct index_state *istate, const char *name, int namelen, int icase);
+static void hash_index_entry(struct index_state *istate, struct cache_entry *ce);
+
static void hash_index_entry_directories(struct index_state *istate, struct cache_entry *ce)
{
/*
@@ -40,30 +43,25 @@ static void hash_index_entry_directories(struct index_state *istate, struct cach
* closing slash. Despite submodules being a directory, they never
* reach this point, because they are stored without a closing slash
* in the cache.
- *
- * Note that the cache_entry stored with the directory does not
- * represent the directory itself. It is a pointer to an existing
- * filename, and its only purpose is to represent existence of the
- * directory in the cache. It is very possible multiple directory
- * hash entries may point to the same cache_entry.
*/
- unsigned int hash;
- void **pos;
+ int len = ce_namelen(ce);
+ if (len && ce->name[len - 1] == '/')
+ len--;
+ while (len && ce->name[len - 1] != '/')
+ len--;
+ if (!len)
+ return;
- const char *ptr = ce->name;
- while (*ptr) {
- while (*ptr && *ptr != '/')
- ++ptr;
- if (*ptr == '/') {
- ++ptr;
- hash = hash_name(ce->name, ptr - ce->name);
- pos = insert_hash(hash, ce, &istate->name_hash);
- if (pos) {
- ce->dir_next = *pos;
- *pos = ce;
- }
- }
+ ce->dir = lookup_index_entry(istate, ce->name, len, ignore_case);
+ if (!ce->dir) {
+ ce->dir = xcalloc(1, cache_entry_size(len));
+ memcpy(ce->dir->name, ce->name, len);
+ ce->dir->ce_namelen = len;
+ ce->dir->name[len] = 0;
+ hash_index_entry(istate, ce->dir);
}
+ ce->dir->ce_flags &= ~CE_UNHASHED;
+ ce->dir->ce_size++;
}
static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)
@@ -74,7 +72,7 @@ static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)
if (ce->ce_flags & CE_HASHED)
return;
ce->ce_flags |= CE_HASHED;
- ce->next = ce->dir_next = NULL;
+ ce->next = ce->dir = NULL;
hash = hash_name(ce->name, ce_namelen(ce));
pos = insert_hash(hash, ce, &istate->name_hash);
if (pos) {
@@ -137,38 +135,32 @@ static int same_name(const struct cache_entry *ce, const char *name, int namelen
if (!icase)
return 0;
- /*
- * If the entry we're comparing is a filename (no trailing slash), then compare
- * the lengths exactly.
- */
- if (name[namelen - 1] != '/')
- return slow_same_name(name, namelen, ce->name, len);
-
- /*
- * For a directory, we point to an arbitrary cache_entry filename. Just
- * make sure the directory portion matches.
- */
- return slow_same_name(name, namelen, ce->name, namelen < len ? namelen : len);
+ return slow_same_name(name, namelen, ce->name, len);
}
-struct cache_entry *index_name_exists(struct index_state *istate, const char *name, int namelen, int icase)
+static struct cache_entry *lookup_index_entry(struct index_state *istate, const char *name, int namelen, int icase)
{
unsigned int hash = hash_name(name, namelen);
- struct cache_entry *ce;
-
- lazy_init_name_hash(istate);
- ce = lookup_hash(hash, &istate->name_hash);
+ struct cache_entry *ce = lookup_hash(hash, &istate->name_hash);
while (ce) {
if (!(ce->ce_flags & CE_UNHASHED)) {
if (same_name(ce, name, namelen, icase))
return ce;
}
- if (icase && name[namelen - 1] == '/')
- ce = ce->dir_next;
- else
- ce = ce->next;
+ ce = ce->next;
}
+ return NULL;
+}
+
+struct cache_entry *index_name_exists(struct index_state *istate, const char *name, int namelen, int icase)
+{
+ struct cache_entry *ce;
+
+ lazy_init_name_hash(istate);
+ ce = lookup_index_entry(istate, name, namelen, icase);
+ if (ce)
+ return ce;
/*
* Might be a submodule. Despite submodules being directories,
@@ -182,7 +174,7 @@ struct cache_entry *index_name_exists(struct index_state *istate, const char *na
* true.
*/
if (icase && name[namelen - 1] == '/') {
- ce = index_name_exists(istate, name, namelen - 1, icase);
+ ce = lookup_index_entry(istate, name, namelen - 1, icase);
if (ce && S_ISGITLINK(ce->ce_mode))
return ce;
}
Karsten Blees <karsten.blees@gmail.com>