Re: inotify to minimize stat() calls

[Karsten Blees <karsten.blees@gmail.com>]

Am 13.02.2013 23:55, schrieb Jeff King:
> 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;
 	}