git checkout optimisation - part 3

Changes sine v1
(v1 was posted with subject "The ext4 filesystem and racy git")

-- patch 2/3 --
Added missing timestamp => timestamp.(u)sec update for unpack-trees.c

-- patch 3/3 --
New patch which removes some 14300 lstat(2) calls, and the total is now at 41677 calls, or 1.382 calls/unique string to lstat() for the reference 'git checkout'-test to Linux tag v2.6.27.

Total reduction so far for all the lstat/git checkout optimisation patches has been 120954 - 41677 = 79277 calls. Some 14400 fstat(2) calls is added, but those should be faster than simmilar lstat() calls.

(patch-series based on master)

Kjetil Barvik (3):
fix compile error when USE_NSEC is defined
make USE_NSEC work as expected
verify_uptodate(): add ce_uptodate(ce) test

 builtin-fetch-pack.c |    4 +-
 cache.h              |    6 ++--
 read-cache.c         |   70 ++++++++++++++++++++++++++++++++++++++++----------
 unpack-trees.c       |   10 +++++--
 4 files changed, 68 insertions(+), 22 deletions(-)

'struct cache' does not have a 'usec' member, but a 'unsigned int nsec' member. Simmilar 'struct stat' does not have a 'st_mtim.usec' member, and we should instead use 'st_mtim.tv_nsec'.

---
 builtin-fetch-pack.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

index 67fb80e..3b210c7 100644
@@ -802,14 +802,14 @@ struct ref *fetch_pack(struct fetch_pack_args *my_args,
 
 		mtime.sec = st.st_mtime;
 #ifdef USE_NSEC
-		mtime.usec = st.st_mtim.usec;
+		mtime.nsec = st.st_mtim.tv_nsec;
 #endif
 		if (stat(shallow, &st)) {
 			if (mtime.sec)
 				die("shallow file was removed during fetch");
 		} else if (st.st_mtime != mtime.sec
 #ifdef USE_NSEC
-				|| st.st_mtim.usec != mtime.usec
+				|| st.st_mtim.tv_nsec != mtime.nsec
 #endif
 			  )
 			die("shallow file was changed during fetch");

1.6.1.349.g99fa5

Since the filesystem ext4 is now defined as stable in Linux v2.6.28, and ext4 supports nanonsecond resolution timestamps natively, it is time to make USE_NSEC work as expected.

This will make racy git situations less likely to happen. For 'git checkout' this means it will be less likely that we have to open, read the contents of the file into RAM, and check if file is really modified or not. The result sould be a litle less used CPU time, less pagefaults and a litle faster program, at least for 'git checkout'.

Since the number of possible racy git situations would increase when disks gets faster, this patch would be more and more helpfull as times go by. For a fast Solid State Disk, this patch should be helpfull.

Note that, when file operations starts to take less than 1 nanosecond, one would again start to get more racy git situations.

For more info on racy git, see Documentation/technical/racy-git.txt For more info on ext4, see http://kernelnewbies.org/Ext4

---
 cache.h        |    6 ++--
 read-cache.c   |   70 ++++++++++++++++++++++++++++++++++++++++++++-----------
 unpack-trees.c |    8 ++++-
 3 files changed, 65 insertions(+), 19 deletions(-)

index 37dfb1c..309053d 100644
@@ -140,8 +140,8 @@ struct ondisk_cache_entry_extended {
 };
 
 struct cache_entry {
-	unsigned int ce_ctime;
-	unsigned int ce_mtime;
+	struct cache_time ce_ctime;
+	struct cache_time ce_mtime;
 	unsigned int ce_dev;
 	unsigned int ce_ino;
 	unsigned int ce_mode;

@@ -282,7 +282,7 @@ struct index_state {
 	struct cache_entry **cache;
 	unsigned int cache_nr, cache_alloc, cache_changed;
 	struct cache_tree *cache_tree;
-	time_t timestamp;
+	struct cache_time timestamp;
 	void *alloc;
 	unsigned name_hash_initialized : 1,
 		 initialized : 1;

index e547282..44714cc 100644
@@ -380,8 +380,12 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 
 	memset(&o->result, 0, sizeof(o->result));
 	o->result.initialized = 1;
-	if (o->src_index)
-		o->result.timestamp = o->src_index->timestamp;
+	if (o->src_index) {
+		o->result.timestamp.sec = o->src_index->timestamp.sec;
+#ifdef USE_NSEC
+		o->result.timestamp.nsec = o->src_index->timestamp.nsec;
+#endif
+	}
 	o->merge_size = len;
 
 	if (!dfc)

1.6.1.349.g99fa5

OK, I admit that I was thinking safe here, so the one using the git compiled with USE_NSEC will see a slow down.

If we for the use case can assume that both is using an git program compiled from the same source, and the index file is placed on a filesystem which supports nanoseconds timestamp, I guess that the use case for the one using USE_NSEC could be better.

I will make a new patch to this one (since it is already placed in next), and then you can see if you like the updated one.

Since timestamp is now a 'struct cache_time' member, I converted the usage of this if-test to be in line with the USE_NSEC usage.

-- kjetil

It was not a veiled objection in the guise of a rhetoric question. I just wanted to know what happens, when you have "/usr/bin/git" compiled without NSEC and "/usr/local/bin/git" compiled with NSEC, and tried to use the two interchangeably. A NSEC enabled one will leave nsec in the index entry, and the normal one reads from the index file (truncating the nsec from both file timestamp and on-disk index entries), and it is unclear what it does to the racy-git algorithm. If there is no adverse effect, that is great. Otherwise, even though the on-disk format might be compatible, we need to somehow tell people not to use two gits on the same index file.

My question was if it is wrong to leave this as "a->timestamp = b->timestamp" which now becomes structure assignment. You would need to move extra 4 (or 8) bytes if you are not using NSEC, but this is not per index entry but one assignment for the whole index file, so...

If we inside verify_uptodate() can already tell from the ce entry that it is already uptodate by testing it with ce_uptodate(ce), there is no need to call lstat(2) and ie_match_stat() afterwards.

And, reading from the commit log message from:

commit eadb5831342bb2e756fa05c03642c4aa1929d4f5
Author: Junio C Hamano <[email protected]>
Date: Fri Jan 18 23:45:24 2008 -0800

Avoid running lstat(2) on the same cache entry.

this also seems to be correct usage of the ce_uptodate() macro introduced by that patch.

This will avoid lots of lstat(2) calls in some cases, for example by running the 'git checkout' command.

---
 unpack-trees.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

index 44714cc..1687aee 100644
@@ -450,7 +450,7 @@ static int verify_uptodate(struct cache_entry *ce,
 {
 	struct stat st;
 
-	if (o->index_only || o->reset)
+	if (o->index_only || o->reset || ce_uptodate(ce))
 		return 0;
 
 	if (!lstat(ce->name, &st)) {

1.6.1.349.g99fa5

Hmm, have you noticed that the rest of the stuff are queued on 'next'? Not that it matters in this case...

Yes, I have! I was also glad to receive my first acked-by git-tag!! :-)

Heya,

In that case, it wouldof been appopriate to base your further patches on next rather than master ;).

Cheers,

Sverre Rabbelier