[PATCH/RFC v2 0/3] git checkout optimisation - part 3

[PATCH/RFC v2 0/3] git checkout optimisation - part 3

[Kjetil Barvik]

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(-)

[PATCH/RFC v2 1/3] fix compile error when USE_NSEC is defined

[Kjetil Barvik]

'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'.

Signed-off-by: Kjetil Barvik <barvik@broadpark.no>
---
 builtin-fetch-pack.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/builtin-fetch-pack.c b/builtin-fetch-pack.c
index 67fb80e..3b210c7 100644
--- a/builtin-fetch-pack.c
+++ b/builtin-fetch-pack.c
@@ -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

[PATCH/RFC v2 2/3] make USE_NSEC work as expected

[Kjetil Barvik]

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

Signed-off-by: Kjetil Barvik <barvik@broadpark.no>
---
 cache.h        |    6 ++--
 read-cache.c   |   70 ++++++++++++++++++++++++++++++++++++++++++++-----------
 unpack-trees.c |    8 ++++-
 3 files changed, 65 insertions(+), 19 deletions(-)

diff --git a/cache.h b/cache.h
index 37dfb1c..309053d 100644
--- a/cache.h
+++ b/cache.h
@@ -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;
diff --git a/read-cache.c b/read-cache.c
index 940ec76..ca4bec2 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -67,8 +67,15 @@ void rename_index_entry_at(struct index_state *istate, int nr, const char *new_n
  */
 void fill_stat_cache_info(struct cache_entry *ce, struct stat *st)
 {
-	ce->ce_ctime = st->st_ctime;
-	ce->ce_mtime = st->st_mtime;
+	ce->ce_ctime.sec = (unsigned int)st->st_ctime;
+	ce->ce_mtime.sec = (unsigned int)st->st_mtime;
+#ifdef USE_NSEC
+	ce->ce_ctime.nsec = (unsigned int)st->st_ctim.tv_nsec;
+	ce->ce_mtime.nsec = (unsigned int)st->st_mtim.tv_nsec;
+#else
+	ce->ce_ctime.nsec = 0;
+	ce->ce_mtime.nsec = 0;
+#endif
 	ce->ce_dev = st->st_dev;
 	ce->ce_ino = st->st_ino;
 	ce->ce_uid = st->st_uid;
@@ -196,11 +203,18 @@ static int ce_match_stat_basic(struct cache_entry *ce, struct stat *st)
 	default:
 		die("internal error: ce_mode is %o", ce->ce_mode);
 	}
-	if (ce->ce_mtime != (unsigned int) st->st_mtime)
+	if (ce->ce_mtime.sec != (unsigned int)st->st_mtime)
 		changed |= MTIME_CHANGED;
-	if (trust_ctime && ce->ce_ctime != (unsigned int) st->st_ctime)
+	if (trust_ctime && ce->ce_ctime.sec != (unsigned int)st->st_ctime)
 		changed |= CTIME_CHANGED;
 
+#ifdef USE_NSEC
+	if (ce->ce_mtime.nsec != (unsigned int)st->st_mtim.tv_nsec)
+		changed |= MTIME_CHANGED;
+	if (trust_ctime && ce->ce_ctime.nsec != (unsigned int)st->st_ctim.tv_nsec)
+		changed |= CTIME_CHANGED;
+#endif
+
 	if (ce->ce_uid != (unsigned int) st->st_uid ||
 	    ce->ce_gid != (unsigned int) st->st_gid)
 		changed |= OWNER_CHANGED;
@@ -232,8 +246,16 @@ static int ce_match_stat_basic(struct cache_entry *ce, struct stat *st)
 static int is_racy_timestamp(const struct index_state *istate, struct cache_entry *ce)
 {
 	return (!S_ISGITLINK(ce->ce_mode) &&
-		istate->timestamp &&
-		((unsigned int)istate->timestamp) <= ce->ce_mtime);
+		istate->timestamp.sec &&
+#ifdef USE_NSEC
+		 /* nanosecond timestamped files can also be racy! */
+		(istate->timestamp.sec < ce->ce_mtime.sec ||
+		 (istate->timestamp.sec == ce->ce_mtime.sec &&
+		  istate->timestamp.nsec <= ce->ce_mtime.nsec))
+#else
+		istate->timestamp.sec <= ce->ce_mtime.sec
+#endif
+		 );
 }
 
 int ie_match_stat(const struct index_state *istate,
@@ -1139,8 +1161,15 @@ static void convert_from_disk(struct ondisk_cache_entry *ondisk, struct cache_en
 	size_t len;
 	const char *name;
 
-	ce->ce_ctime = ntohl(ondisk->ctime.sec);
-	ce->ce_mtime = ntohl(ondisk->mtime.sec);
+	ce->ce_ctime.sec = ntohl(ondisk->ctime.sec);
+	ce->ce_mtime.sec = ntohl(ondisk->mtime.sec);
+#ifdef USE_NSEC
+	ce->ce_ctime.nsec = ntohl(ondisk->ctime.nsec);
+	ce->ce_mtime.nsec = ntohl(ondisk->mtime.nsec);
+#else
+	ce->ce_ctime.nsec = 0;
+	ce->ce_mtime.nsec = 0;
+#endif
 	ce->ce_dev   = ntohl(ondisk->dev);
 	ce->ce_ino   = ntohl(ondisk->ino);
 	ce->ce_mode  = ntohl(ondisk->mode);
@@ -1206,7 +1235,8 @@ int read_index_from(struct index_state *istate, const char *path)
 		return istate->cache_nr;
 
 	errno = ENOENT;
-	istate->timestamp = 0;
+	istate->timestamp.sec = 0;
+	istate->timestamp.nsec = 0;
 	fd = open(path, O_RDONLY);
 	if (fd < 0) {
 		if (errno == ENOENT)
@@ -1258,7 +1288,13 @@ int read_index_from(struct index_state *istate, const char *path)
 		src_offset += ondisk_ce_size(ce);
 		dst_offset += ce_size(ce);
 	}
-	istate->timestamp = st.st_mtime;
+	istate->timestamp.sec = st.st_mtime;
+#ifdef USE_NSEC
+	istate->timestamp.nsec = (unsigned int)st.st_mtim.tv_nsec;
+#else
+	istate->timestamp.nsec = 0;
+#endif
+
 	while (src_offset <= mmap_size - 20 - 8) {
 		/* After an array of active_nr index entries,
 		 * there can be arbitrary number of extended
@@ -1288,14 +1324,15 @@ unmap:
 
 int is_index_unborn(struct index_state *istate)
 {
-	return (!istate->cache_nr && !istate->alloc && !istate->timestamp);
+	return (!istate->cache_nr && !istate->alloc && !istate->timestamp.sec);
 }
 
 int discard_index(struct index_state *istate)
 {
 	istate->cache_nr = 0;
 	istate->cache_changed = 0;
-	istate->timestamp = 0;
+	istate->timestamp.sec = 0;
+	istate->timestamp.nsec = 0;
 	istate->name_hash_initialized = 0;
 	free_hash(&istate->name_hash);
 	cache_tree_free(&(istate->cache_tree));
@@ -1441,10 +1478,15 @@ static int ce_write_entry(git_SHA_CTX *c, int fd, struct cache_entry *ce)
 	struct ondisk_cache_entry *ondisk = xcalloc(1, size);
 	char *name;
 
-	ondisk->ctime.sec = htonl(ce->ce_ctime);
+	ondisk->ctime.sec = htonl(ce->ce_ctime.sec);
+	ondisk->mtime.sec = htonl(ce->ce_mtime.sec);
+#ifdef USE_NSEC
+	ondisk->ctime.nsec = htonl(ce->ce_ctime.nsec);
+	ondisk->mtime.nsec = htonl(ce->ce_mtime.nsec);
+#else
 	ondisk->ctime.nsec = 0;
-	ondisk->mtime.sec = htonl(ce->ce_mtime);
 	ondisk->mtime.nsec = 0;
+#endif
 	ondisk->dev  = htonl(ce->ce_dev);
 	ondisk->ino  = htonl(ce->ce_ino);
 	ondisk->mode = htonl(ce->ce_mode);
diff --git a/unpack-trees.c b/unpack-trees.c
index e547282..44714cc 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -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

[PATCH/RFC v2 3/3] verify_uptodate(): add ce_uptodate(ce) test

[Kjetil Barvik]

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 <gitster@pobox.com>
    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.

Signed-off-by: Kjetil Barvik <barvik@broadpark.no>
---
 unpack-trees.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/unpack-trees.c b/unpack-trees.c
index 44714cc..1687aee 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -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

Re: [PATCH/RFC v2 0/3] git checkout optimisation - part 3

[Junio C Hamano]

Kjetil Barvik <barvik@broadpark.no> writes:

> 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)

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

Re: [PATCH/RFC v2 2/3] make USE_NSEC work as expected

[Junio C Hamano]

Kjetil Barvik <barvik@broadpark.no> writes:

> diff --git a/read-cache.c b/read-cache.c
> index 940ec76..ca4bec2 100644
> --- a/read-cache.c
> +++ b/read-cache.c
> @@ -67,8 +67,15 @@ void rename_index_entry_at(struct index_state *istate, int nr, const char *new_n
>   */
>  void fill_stat_cache_info(struct cache_entry *ce, struct stat *st)
>  {
> -	ce->ce_ctime = st->st_ctime;
> -	ce->ce_mtime = st->st_mtime;
> +	ce->ce_ctime.sec = (unsigned int)st->st_ctime;
> +	ce->ce_mtime.sec = (unsigned int)st->st_mtime;
> +#ifdef USE_NSEC
> +	ce->ce_ctime.nsec = (unsigned int)st->st_ctim.tv_nsec;
> +	ce->ce_mtime.nsec = (unsigned int)st->st_mtim.tv_nsec;
> +#else
> +	ce->ce_ctime.nsec = 0;
> +	ce->ce_mtime.nsec = 0;
> +#endif

How does this affect a use case where the same index file used with two 
instances of git (one compiled with and another without USE_NSEC)?

> @@ -232,8 +246,16 @@ static int ce_match_stat_basic(struct cache_entry *ce, struct stat *st)
>  static int is_racy_timestamp(const struct index_state *istate, struct cache_entry *ce)
>  {
>  	return (!S_ISGITLINK(ce->ce_mode) &&
> -		istate->timestamp &&
> -		((unsigned int)istate->timestamp) <= ce->ce_mtime);
> +		istate->timestamp.sec &&
> +#ifdef USE_NSEC
> +		 /* nanosecond timestamped files can also be racy! */

Amusing ;-)

> diff --git a/unpack-trees.c b/unpack-trees.c
> index e547282..44714cc 100644
> --- a/unpack-trees.c
> +++ b/unpack-trees.c
> @@ -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
> +	}

Do we need this hunk?

Re: [PATCH/RFC v2 0/3] git checkout optimisation - part 3

[Kjetil Barvik]

Junio C Hamano <gitster@pobox.com> writes:
> Hmm, have you noticed that the rest of the stuff are queued on 'next'?

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

Re: [PATCH/RFC v2 0/3] git checkout optimisation - part 3

[Sverre Rabbelier]

Heya,

On Fri, Feb 20, 2009 at 10:03, Kjetil Barvik <barvik@broadpark.no> wrote:
> Junio C Hamano <gitster@pobox.com> writes:
>> Hmm, have you noticed that the rest of the stuff are queued on 'next'?
>
>  Yes, I have!  I was also glad to receive my first acked-by git-tag!!

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

-- 
Cheers,

Sverre Rabbelier

Re: [PATCH/RFC v2 2/3] make USE_NSEC work as expected

[Kjetil Barvik]

Junio C Hamano <gitster@pobox.com> writes:

> Kjetil Barvik <barvik@broadpark.no> writes:
>
>> diff --git a/read-cache.c b/read-cache.c
>> index 940ec76..ca4bec2 100644
>> --- a/read-cache.c
>> +++ b/read-cache.c
>> @@ -67,8 +67,15 @@ void rename_index_entry_at(struct index_state *istate, int nr, const char *new_n
>>   */
>>  void fill_stat_cache_info(struct cache_entry *ce, struct stat *st)
>>  {
>> -	ce->ce_ctime = st->st_ctime;
>> -	ce->ce_mtime = st->st_mtime;
>> +	ce->ce_ctime.sec = (unsigned int)st->st_ctime;
>> +	ce->ce_mtime.sec = (unsigned int)st->st_mtime;
>> +#ifdef USE_NSEC
>> +	ce->ce_ctime.nsec = (unsigned int)st->st_ctim.tv_nsec;
>> +	ce->ce_mtime.nsec = (unsigned int)st->st_mtim.tv_nsec;
>> +#else
>> +	ce->ce_ctime.nsec = 0;
>> +	ce->ce_mtime.nsec = 0;
>> +#endif
>
> How does this affect a use case where the same index file used with two 
> instances of git (one compiled with and another without USE_NSEC)?

  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.


>> diff --git a/unpack-trees.c b/unpack-trees.c
>> index e547282..44714cc 100644
>> --- a/unpack-trees.c
>> +++ b/unpack-trees.c
>> @@ -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
>> +	}
>
> Do we need this hunk?

  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

Re: [PATCH/RFC v2 2/3] make USE_NSEC work as expected

[Junio C Hamano]

Kjetil Barvik <barvik@broadpark.no> writes:

> Junio C Hamano <gitster@pobox.com> writes:
>
>>> +	ce->ce_ctime.sec = (unsigned int)st->st_ctime;
>>> +	ce->ce_mtime.sec = (unsigned int)st->st_mtime;
>>> +#ifdef USE_NSEC
>>> +	ce->ce_ctime.nsec = (unsigned int)st->st_ctim.tv_nsec;
>>> +	ce->ce_mtime.nsec = (unsigned int)st->st_mtim.tv_nsec;
>>> +#else
>>> +	ce->ce_ctime.nsec = 0;
>>> +	ce->ce_mtime.nsec = 0;
>>> +#endif
>>
>> How does this affect a use case where the same index file used with two 
>> instances of git (one compiled with and another without USE_NSEC)?
>
>   OK, I admit that I was thinking safe here,...

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.

>>> diff --git a/unpack-trees.c b/unpack-trees.c
>>> index e547282..44714cc 100644
>>> --- a/unpack-trees.c
>>> +++ b/unpack-trees.c
>>> @@ -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
>>> +	}
>>
>> Do we need this hunk?
>
>   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.

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...