Merge branch 'kb/checkout-optim'

* kb/checkout-optim:
  Revert "lstat_cache(): print a warning if doing ping-pong between cache types"
  checkout bugfix: use stat.mtime instead of stat.ctime in two places
  Makefile: Set compiler switch for USE_NSEC
  Create USE_ST_TIMESPEC and turn it on for Darwin
  Not all systems use st_[cm]tim field for ns resolution file timestamp
  Record ns-timestamps if possible, but do not use it without USE_NSEC
  write_index(): update index_state->timestamp after flushing to disk
  verify_uptodate(): add ce_uptodate(ce) test
  make USE_NSEC work as expected
  fix compile error when USE_NSEC is defined
  check_updates(): effective removal of cache entries marked CE_REMOVE
  lstat_cache(): print a warning if doing ping-pong between cache types
  show_patch_diff(): remove a call to fstat()
  write_entry(): use fstat() instead of lstat() when file is open
  write_entry(): cleanup of some duplicated code
  create_directories(): remove some memcpy() and strchr() calls
  unlink_entry(): introduce schedule_dir_for_removal()
  lstat_cache(): swap func(length, string) into func(string, length)
  lstat_cache(): generalise longest_match_lstat_cache()
  lstat_cache(): small cleanup and optimisation

15 files changed, 296 insertions, 170 deletions

diff --git a/Documentation/CodingGuidelines b/Documentation/CodingGuidelines
index 0d7fa9cca9..b8bf618a30 100644
--- a/Documentation/CodingGuidelines
+++ b/Documentation/CodingGuidelines
@@ -129,3 +129,6 @@ For C programs:
    used in the git core command set (unless your command is clearly
    separate from it, such as an importer to convert random-scm-X
    repositories to git).
+
+ - When we pass <string, length> pair to functions, we should try to
+   pass them in that order.
diff --git a/Makefile b/Makefile
index 1087884be6..216adb9d05 100644
--- a/Makefile
+++ b/Makefile
@@ -126,6 +126,12 @@ all::
 # randomly break unless your underlying filesystem supports those sub-second
 # times (my ext3 doesn't).
 #
+# Define USE_ST_TIMESPEC if your "struct stat" uses "st_ctimespec" instead of
+# "st_ctim"
+#
+# Define NO_NSEC if your "struct stat" does not have "st_ctim.tv_nsec"
+# available.  This automatically turns USE_NSEC off.
+#
 # Define USE_STDEV below if you want git to care about the underlying device
 # change being considered an inode change from the update-index perspective.
 #
@@ -657,6 +663,7 @@ ifeq ($(uname_S),Darwin)
 	endif
 	NO_MEMMEM = YesPlease
 	THREADED_DELTA_SEARCH = YesPlease
+	USE_ST_TIMESPEC = YesPlease
 endif
 ifeq ($(uname_S),SunOS)
 	NEEDS_SOCKET = YesPlease
@@ -734,6 +741,7 @@ ifeq ($(uname_S),AIX)
 	NO_MEMMEM = YesPlease
 	NO_MKDTEMP = YesPlease
 	NO_STRLCPY = YesPlease
+	NO_NSEC = YesPlease
 	FREAD_READS_DIRECTORIES = UnfortunatelyYes
 	INTERNAL_QSORT = UnfortunatelyYes
 	NEEDS_LIBICONV=YesPlease
@@ -799,6 +807,7 @@ ifneq (,$(findstring MINGW,$(uname_S)))
 	RUNTIME_PREFIX = YesPlease
 	NO_POSIX_ONLY_PROGRAMS = YesPlease
 	NO_ST_BLOCKS_IN_STRUCT_STAT = YesPlease
+	NO_NSEC = YesPlease
 	COMPAT_CFLAGS += -D__USE_MINGW_ACCESS -DNOGDI -Icompat -Icompat/regex -Icompat/fnmatch
 	COMPAT_CFLAGS += -DSNPRINTF_SIZE_CORR=1
 	COMPAT_CFLAGS += -DSTRIP_EXTENSION=\".exe\"
@@ -920,6 +929,15 @@ endif
 ifdef NO_ST_BLOCKS_IN_STRUCT_STAT
 	BASIC_CFLAGS += -DNO_ST_BLOCKS_IN_STRUCT_STAT
 endif
+ifdef USE_NSEC
+	BASIC_CFLAGS += -DUSE_NSEC
+endif
+ifdef USE_ST_TIMESPEC
+	BASIC_CFLAGS += -DUSE_ST_TIMESPEC
+endif
+ifdef NO_NSEC
+	BASIC_CFLAGS += -DNO_NSEC
+endif
 ifdef NO_C99_FORMAT
 	BASIC_CFLAGS += -DNO_C99_FORMAT
 endif
diff --git a/builtin-add.c b/builtin-add.c
index 08443f2f1e..7ddb65932d 100644
--- a/builtin-add.c
+++ b/builtin-add.c
@@ -148,7 +148,7 @@ static const char **validate_pathspec(int argc, const char **argv, const char *p
 	if (pathspec) {
 		const char **p;
 		for (p = pathspec; *p; p++) {
-			if (has_symlink_leading_path(strlen(*p), *p)) {
+			if (has_symlink_leading_path(*p, strlen(*p))) {
 				int len = prefix ? strlen(prefix) : 0;
 				die("'%s' is beyond a symbolic link", *p + len);
 			}
diff --git a/builtin-apply.c b/builtin-apply.c
index f312798af3..106be94105 100644
--- a/builtin-apply.c
+++ b/builtin-apply.c
@@ -2360,7 +2360,7 @@ static int check_to_create_blob(const char *new_name, int ok_if_exists)
 		 * In such a case, path "new_name" does not exist as
 		 * far as git is concerned.
 		 */
-		if (has_symlink_leading_path(strlen(new_name), new_name))
+		if (has_symlink_leading_path(new_name, strlen(new_name)))
 			return 0;
 
 		return error("%s: already exists in working directory", new_name);
diff --git a/builtin-fetch-pack.c b/builtin-fetch-pack.c
index c2e5adc884..29f4315e92 100644
--- a/builtin-fetch-pack.c
+++ b/builtin-fetch-pack.c
@@ -800,15 +800,13 @@ struct ref *fetch_pack(struct fetch_pack_args *my_args,
 		int fd;
 
 		mtime.sec = st.st_mtime;
-#ifdef USE_NSEC
-		mtime.usec = st.st_mtim.usec;
-#endif
+		mtime.nsec = ST_MTIME_NSEC(st);
 		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_MTIME_NSEC(st) != mtime.nsec
 #endif
 			  )
 			die("shallow file was changed during fetch");
diff --git a/builtin-update-index.c b/builtin-update-index.c
index dd43d5bef4..1fde893cfa 100644
--- a/builtin-update-index.c
+++ b/builtin-update-index.c
@@ -195,7 +195,7 @@ static int process_path(const char *path)
 	struct stat st;
 
 	len = strlen(path);
-	if (has_symlink_leading_path(len, path))
+	if (has_symlink_leading_path(path, len))
 		return error("'%s' is beyond a symbolic link", path);
 
 	/*
diff --git a/cache.h b/cache.h
index fdc4ada43a..bd4c390d57 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;
@@ -428,7 +428,7 @@ extern int read_index_preload(struct index_state *, const char **pathspec);
 extern int read_index_from(struct index_state *, const char *path);
 extern int is_index_unborn(struct index_state *);
 extern int read_index_unmerged(struct index_state *);
-extern int write_index(const struct index_state *, int newfd);
+extern int write_index(struct index_state *, int newfd);
 extern int discard_index(struct index_state *);
 extern int unmerged_index(const struct index_state *);
 extern int verify_path(const char *path);
@@ -443,6 +443,7 @@ extern int add_index_entry(struct index_state *, struct cache_entry *ce, int opt
 extern struct cache_entry *refresh_cache_entry(struct cache_entry *ce, int really);
 extern void rename_index_entry_at(struct index_state *, int pos, const char *new_name);
 extern int remove_index_entry_at(struct index_state *, int pos);
+extern void remove_marked_cache_entries(struct index_state *istate);
 extern int remove_file_from_index(struct index_state *, const char *path);
 #define ADD_CACHE_VERBOSE 1
 #define ADD_CACHE_PRETEND 2
@@ -725,11 +726,13 @@ struct checkout {
 };
 
 extern int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *topath);
-extern int has_symlink_leading_path(int len, const char *name);
-extern int has_symlink_or_noent_leading_path(int len, const char *name);
-extern int has_dirs_only_path(int len, const char *name, int prefix_len);
-extern void invalidate_lstat_cache(int len, const char *name);
+extern int has_symlink_leading_path(const char *name, int len);
+extern int has_symlink_or_noent_leading_path(const char *name, int len);
+extern int has_dirs_only_path(const char *name, int len, int prefix_len);
+extern void invalidate_lstat_cache(const char *name, int len);
 extern void clear_lstat_cache(void);
+extern void schedule_dir_for_removal(const char *name, int len);
+extern void remove_scheduled_dirs(void);
 
 extern struct alternate_object_database {
 	struct alternate_object_database *next;
diff --git a/combine-diff.c b/combine-diff.c
index b3b86aebcb..066ce841ed 100644
--- a/combine-diff.c
+++ b/combine-diff.c
@@ -712,9 +712,7 @@ static void show_patch_diff(struct combine_diff_path *elem, int num_parent,
 			result_size = buf.len;
 			result = strbuf_detach(&buf, NULL);
 			elem->mode = canon_mode(st.st_mode);
-		}
-		else if (0 <= (fd = open(elem->path, O_RDONLY)) &&
-			 !fstat(fd, &st)) {
+		} else if (0 <= (fd = open(elem->path, O_RDONLY))) {
 			size_t len = xsize_t(st.st_size);
 			ssize_t done;
 			int is_file, i;
diff --git a/diff-lib.c b/diff-lib.c
index 79d0606834..a310fb2ad0 100644
--- a/diff-lib.c
+++ b/diff-lib.c
@@ -31,7 +31,7 @@ static int check_removed(const struct cache_entry *ce, struct stat *st)
 			return -1;
 		return 1;
 	}
-	if (has_symlink_leading_path(ce_namelen(ce), ce->name))
+	if (has_symlink_leading_path(ce->name, ce_namelen(ce)))
 		return 1;
 	if (S_ISDIR(st->st_mode)) {
 		unsigned char sub[20];
diff --git a/dir.c b/dir.c
index 2245749b3f..371bcf7cfb 100644
--- a/dir.c
+++ b/dir.c
@@ -720,7 +720,7 @@ int read_directory(struct dir_struct *dir, const char *path, const char *base, i
 {
 	struct path_simplify *simplify;
 
-	if (has_symlink_leading_path(strlen(path), path))
+	if (has_symlink_leading_path(path, strlen(path)))
 		return dir->nr;
 
 	simplify = create_simplify(pathspec);
diff --git a/entry.c b/entry.c
index 05aa58d348..5daacc2fe5 100644
--- a/entry.c
+++ b/entry.c
@@ -2,15 +2,19 @@
 #include "blob.h"
 #include "dir.h"
 
-static void create_directories(const char *path, const struct checkout *state)
+static void create_directories(const char *path, int path_len,
+			       const struct checkout *state)
 {
-	int len = strlen(path);
-	char *buf = xmalloc(len + 1);
-	const char *slash = path;
-
-	while ((slash = strchr(slash+1, '/')) != NULL) {
-		len = slash - path;
-		memcpy(buf, path, len);
+	char *buf = xmalloc(path_len + 1);
+	int len = 0;
+
+	while (len < path_len) {
+		do {
+			buf[len] = path[len];
+			len++;
+		} while (len < path_len && path[len] != '/');
+		if (len >= path_len)
+			break;
 		buf[len] = 0;
 
 		/*
@@ -20,7 +24,7 @@ static void create_directories(const char *path, const struct checkout *state)
 		 * we test the path components of the prefix with the
 		 * stat() function instead of the lstat() function.
 		 */
-		if (has_dirs_only_path(len, buf, state->base_dir_len))
+		if (has_dirs_only_path(buf, len, state->base_dir_len))
 			continue; /* ok, it is already a directory. */
 
 		/*
@@ -74,7 +78,7 @@ static int create_file(const char *path, unsigned int mode)
 	return open(path, O_WRONLY | O_CREAT | O_EXCL, mode);
 }
 
-static void *read_blob_entry(struct cache_entry *ce, const char *path, unsigned long *size)
+static void *read_blob_entry(struct cache_entry *ce, unsigned long *size)
 {
 	enum object_type type;
 	void *new = read_sha1_file(ce->sha1, &type, size);
@@ -89,36 +93,52 @@ static void *read_blob_entry(struct cache_entry *ce, const char *path, unsigned
 
 static int write_entry(struct cache_entry *ce, char *path, const struct checkout *state, int to_tempfile)
 {
-	int fd;
-	long wrote;
-
-	switch (ce->ce_mode & S_IFMT) {
-		char *new;
-		struct strbuf buf;
-		unsigned long size;
+	unsigned int ce_mode_s_ifmt = ce->ce_mode & S_IFMT;
+	int fd, ret, fstat_done = 0;
+	char *new;
+	struct strbuf buf = STRBUF_INIT;
+	unsigned long size;
+	size_t wrote, newsize = 0;
+	struct stat st;
 
+	switch (ce_mode_s_ifmt) {
 	case S_IFREG:
-		new = read_blob_entry(ce, path, &size);
+	case S_IFLNK:
+		new = read_blob_entry(ce, &size);
 		if (!new)
 			return error("git checkout-index: unable to read sha1 file of %s (%s)",
 				path, sha1_to_hex(ce->sha1));
 
+		if (ce_mode_s_ifmt == S_IFLNK && has_symlinks && !to_tempfile) {
+			ret = symlink(new, path);
+			free(new);
+			if (ret)
+				return error("git checkout-index: unable to create symlink %s (%s)",
+					     path, strerror(errno));
+			break;
+		}
+
 		/*
 		 * Convert from git internal format to working tree format
 		 */
-		strbuf_init(&buf, 0);
-		if (convert_to_working_tree(ce->name, new, size, &buf)) {
-			size_t newsize = 0;
+		if (ce_mode_s_ifmt == S_IFREG &&
+		    convert_to_working_tree(ce->name, new, size, &buf)) {
 			free(new);
 			new = strbuf_detach(&buf, &newsize);
 			size = newsize;
 		}
 
 		if (to_tempfile) {
-			strcpy(path, ".merge_file_XXXXXX");
+			if (ce_mode_s_ifmt == S_IFREG)
+				strcpy(path, ".merge_file_XXXXXX");
+			else
+				strcpy(path, ".merge_link_XXXXXX");
 			fd = mkstemp(path);
-		} else
+		} else if (ce_mode_s_ifmt == S_IFREG) {
 			fd = create_file(path, ce->ce_mode);
+		} else {
+			fd = create_file(path, 0666);
+		}
 		if (fd < 0) {
 			free(new);
 			return error("git checkout-index: unable to create file %s (%s)",
@@ -126,41 +146,16 @@ static int write_entry(struct cache_entry *ce, char *path, const struct checkout
 		}
 
 		wrote = write_in_full(fd, new, size);
+		/* use fstat() only when path == ce->name */
+		if (state->refresh_cache && !to_tempfile && !state->base_dir_len) {
+			fstat(fd, &st);
+			fstat_done = 1;
+		}
 		close(fd);
 		free(new);
 		if (wrote != size)
 			return error("git checkout-index: unable to write file %s", path);
 		break;
-	case S_IFLNK:
-		new = read_blob_entry(ce, path, &size);
-		if (!new)
-			return error("git checkout-index: unable to read sha1 file of %s (%s)",
-				path, sha1_to_hex(ce->sha1));
-		if (to_tempfile || !has_symlinks) {
-			if (to_tempfile) {
-				strcpy(path, ".merge_link_XXXXXX");
-				fd = mkstemp(path);
-			} else
-				fd = create_file(path, 0666);
-			if (fd < 0) {
-				free(new);
-				return error("git checkout-index: unable to create "
-						 "file %s (%s)", path, strerror(errno));
-			}
-			wrote = write_in_full(fd, new, size);
-			close(fd);
-			free(new);
-			if (wrote != size)
-				return error("git checkout-index: unable to write file %s",
-					path);
-		} else {
-			wrote = symlink(new, path);
-			free(new);
-			if (wrote)
-				return error("git checkout-index: unable to create "
-						 "symlink %s (%s)", path, strerror(errno));
-		}
-		break;
 	case S_IFGITLINK:
 		if (to_tempfile)
 			return error("git checkout-index: cannot create temporary subproject %s", path);
@@ -172,8 +167,8 @@ static int write_entry(struct cache_entry *ce, char *path, const struct checkout
 	}
 
 	if (state->refresh_cache) {
-		struct stat st;
-		lstat(ce->name, &st);
+		if (!fstat_done)
+			lstat(ce->name, &st);
 		fill_stat_cache_info(ce, &st);
 	}
 	return 0;
@@ -190,6 +185,7 @@ int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *t
 
 	memcpy(path, state->base_dir, len);
 	strcpy(path + len, ce->name);
+	len += ce_namelen(ce);
 
 	if (!lstat(path, &st)) {
 		unsigned changed = ce_match_stat(ce, &st, CE_MATCH_IGNORE_VALID);
@@ -218,6 +214,6 @@ int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *t
 			return error("unable to unlink old '%s' (%s)", path, strerror(errno));
 	} else if (state->not_new)
 		return 0;
-	create_directories(path, state);
+	create_directories(path, len, state);
 	return write_entry(ce, path, state, 0);
 }
diff --git a/git-compat-util.h b/git-compat-util.h
index 878d83dd08..19062534a1 100644
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -388,4 +388,18 @@ void git_qsort(void *base, size_t nmemb, size_t size,
 # define FORCE_DIR_SET_GID 0
 #endif
 
+#ifdef NO_NSEC
+#undef USE_NSEC
+#define ST_CTIME_NSEC(st) 0
+#define ST_MTIME_NSEC(st) 0
+#else
+#ifdef USE_ST_TIMESPEC
+#define ST_CTIME_NSEC(st) ((unsigned int)((st).st_ctimespec.tv_nsec))
+#define ST_MTIME_NSEC(st) ((unsigned int)((st).st_mtimespec.tv_nsec))
+#else
+#define ST_CTIME_NSEC(st) ((unsigned int)((st).st_ctim.tv_nsec))
+#define ST_MTIME_NSEC(st) ((unsigned int)((st).st_mtim.tv_nsec))
+#endif
+#endif
+
 #endif
diff --git a/read-cache.c b/read-cache.c
index 940ec76fdf..3f587110cb 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -67,8 +67,10 @@ 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;
+	ce->ce_ctime.nsec = ST_CTIME_NSEC(*st);
+	ce->ce_mtime.nsec = ST_MTIME_NSEC(*st);
 	ce->ce_dev = st->st_dev;
 	ce->ce_ino = st->st_ino;
 	ce->ce_uid = st->st_uid;
@@ -196,11 +198,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 != ST_MTIME_NSEC(*st))
+		changed |= MTIME_CHANGED;
+	if (trust_ctime && ce->ce_ctime.nsec != ST_CTIME_NSEC(*st))
+		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 +241,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,
@@ -443,6 +460,26 @@ int remove_index_entry_at(struct index_state *istate, int pos)
 	return 1;
 }
 
+/*
+ * Remove all cache ententries marked for removal, that is where
+ * CE_REMOVE is set in ce_flags.  This is much more effective than
+ * calling remove_index_entry_at() for each entry to be removed.
+ */
+void remove_marked_cache_entries(struct index_state *istate)
+{
+	struct cache_entry **ce_array = istate->cache;
+	unsigned int i, j;
+
+	for (i = j = 0; i < istate->cache_nr; i++) {
+		if (ce_array[i]->ce_flags & CE_REMOVE)
+			remove_name_hash(ce_array[i]);
+		else
+			ce_array[j++] = ce_array[i];
+	}
+	istate->cache_changed = 1;
+	istate->cache_nr = j;
+}
+
 int remove_file_from_index(struct index_state *istate, const char *path)
 {
 	int pos = index_name_pos(istate, path, strlen(path));
@@ -1139,8 +1176,10 @@ 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);
+	ce->ce_ctime.nsec = ntohl(ondisk->ctime.nsec);
+	ce->ce_mtime.nsec = ntohl(ondisk->mtime.nsec);
 	ce->ce_dev   = ntohl(ondisk->dev);
 	ce->ce_ino   = ntohl(ondisk->ino);
 	ce->ce_mode  = ntohl(ondisk->mode);
@@ -1206,7 +1245,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 +1298,9 @@ 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;
+	istate->timestamp.nsec = ST_MTIME_NSEC(st);
+
 	while (src_offset <= mmap_size - 20 - 8) {
 		/* After an array of active_nr index entries,
 		 * there can be arbitrary number of extended
@@ -1288,14 +1330,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 +1484,10 @@ 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.nsec = 0;
-	ondisk->mtime.sec = htonl(ce->ce_mtime);
-	ondisk->mtime.nsec = 0;
+	ondisk->ctime.sec = htonl(ce->ce_ctime.sec);
+	ondisk->mtime.sec = htonl(ce->ce_mtime.sec);
+	ondisk->ctime.nsec = htonl(ce->ce_ctime.nsec);
+	ondisk->mtime.nsec = htonl(ce->ce_mtime.nsec);
 	ondisk->dev  = htonl(ce->ce_dev);
 	ondisk->ino  = htonl(ce->ce_ino);
 	ondisk->mode = htonl(ce->ce_mode);
@@ -1466,13 +1509,14 @@ static int ce_write_entry(git_SHA_CTX *c, int fd, struct cache_entry *ce)
 	return ce_write(c, fd, ondisk, size);
 }
 
-int write_index(const struct index_state *istate, int newfd)
+int write_index(struct index_state *istate, int newfd)
 {
 	git_SHA_CTX c;
 	struct cache_header hdr;
 	int i, err, removed, extended;
 	struct cache_entry **cache = istate->cache;
 	int entries = istate->cache_nr;
+	struct stat st;
 
 	for (i = removed = extended = 0; i < entries; i++) {
 		if (cache[i]->ce_flags & CE_REMOVE)
@@ -1516,7 +1560,12 @@ int write_index(const struct index_state *istate, int newfd)
 		if (err)
 			return -1;
 	}
-	return ce_flush(&c, newfd);
+
+	if (ce_flush(&c, newfd) || fstat(newfd, &st))
+		return -1;
+	istate->timestamp.sec = (unsigned int)st.st_mtime;
+	istate->timestamp.nsec = ST_MTIME_NSEC(st);
+	return 0;
 }
 
 /*
diff --git a/symlinks.c b/symlinks.c
index f262b7c44b..1d6b35b858 100644
--- a/symlinks.c
+++ b/symlinks.c
@@ -1,51 +1,54 @@
 #include "cache.h"
 
-static struct cache_def {
-	char path[PATH_MAX + 1];
-	int len;
-	int flags;
-	int track_flags;
-	int prefix_len_stat_func;
-} cache;
-
 /*
  * Returns the length (on a path component basis) of the longest
- * common prefix match of 'name' and the cached path string.
+ * common prefix match of 'name_a' and 'name_b'.
  */
-static inline int longest_match_lstat_cache(int len, const char *name,
-					    int *previous_slash)
+static int longest_path_match(const char *name_a, int len_a,
+			      const char *name_b, int len_b,
+			      int *previous_slash)
 {
 	int max_len, match_len = 0, match_len_prev = 0, i = 0;
 
-	max_len = len < cache.len ? len : cache.len;
-	while (i < max_len && name[i] == cache.path[i]) {
-		if (name[i] == '/') {
+	max_len = len_a < len_b ? len_a : len_b;
+	while (i < max_len && name_a[i] == name_b[i]) {
+		if (name_a[i] == '/') {
 			match_len_prev = match_len;
 			match_len = i;
 		}
 		i++;
 	}
-	/* Is the cached path string a substring of 'name'? */
-	if (i == cache.len && cache.len < len && name[cache.len] == '/') {
-		match_len_prev = match_len;
-		match_len = cache.len;
-	/* Is 'name' a substring of the cached path string? */
-	} else if ((i == len && len < cache.len && cache.path[len] == '/') ||
-		   (i == len && len == cache.len)) {
+	/*
+	 * Is 'name_b' a substring of 'name_a', the other way around,
+	 * or is 'name_a' and 'name_b' the exact same string?
+	 */
+	if (i >= max_len && ((len_a > len_b && name_a[len_b] == '/') ||
+			     (len_a < len_b && name_b[len_a] == '/') ||
+			     (len_a == len_b))) {
 		match_len_prev = match_len;
-		match_len = len;
+		match_len = i;
 	}
 	*previous_slash = match_len_prev;
 	return match_len;
 }
 
-static inline void reset_lstat_cache(int track_flags, int prefix_len_stat_func)
+static struct cache_def {
+	char path[PATH_MAX + 1];
+	int len;
+	int flags;
+	int track_flags;
+	int prefix_len_stat_func;
+} cache;
+
+static inline void reset_lstat_cache(void)
 {
 	cache.path[0] = '\0';
 	cache.len = 0;
 	cache.flags = 0;
-	cache.track_flags = track_flags;
-	cache.prefix_len_stat_func = prefix_len_stat_func;
+	/*
+	 * The track_flags and prefix_len_stat_func members is only
+	 * set by the safeguard rule inside lstat_cache()
+	 */
 }
 
 #define FL_DIR      (1 << 0)
@@ -67,7 +70,7 @@ static inline void reset_lstat_cache(int track_flags, int prefix_len_stat_func)
  * of the prefix, where the cache should use the stat() function
  * instead of the lstat() function to test each path component.
  */
-static int lstat_cache(int len, const char *name,
+static int lstat_cache(const char *name, int len,
 		       int track_flags, int prefix_len_stat_func)
 {
 	int match_len, last_slash, last_slash_dir, previous_slash;
@@ -77,11 +80,13 @@ static int lstat_cache(int len, const char *name,
 	if (cache.track_flags != track_flags ||
 	    cache.prefix_len_stat_func != prefix_len_stat_func) {
 		/*
-		 * As a safeguard we clear the cache if the values of
-		 * track_flags and/or prefix_len_stat_func does not
-		 * match with the last supplied values.
+		 * As a safeguard rule we clear the cache if the
+		 * values of track_flags and/or prefix_len_stat_func
+		 * does not match with the last supplied values.
 		 */
-		reset_lstat_cache(track_flags, prefix_len_stat_func);
+		reset_lstat_cache();
+		cache.track_flags = track_flags;
+		cache.prefix_len_stat_func = prefix_len_stat_func;
 		match_len = last_slash = 0;
 	} else {
 		/*
@@ -89,7 +94,8 @@ static int lstat_cache(int len, const char *name,
 		 * the 2 "excluding" path types.
 		 */
 		match_len = last_slash =
-			longest_match_lstat_cache(len, name, &previous_slash);
+			longest_path_match(name, len, cache.path, cache.len,
+					   &previous_slash);
 		match_flags = cache.flags & track_flags & (FL_NOENT|FL_SYMLINK);
 		if (match_flags && match_len == cache.len)
 			return match_flags;
@@ -153,7 +159,7 @@ static int lstat_cache(int len, const char *name,
 		cache.path[last_slash] = '\0';
 		cache.len = last_slash;
 		cache.flags = save_flags;
-	} else if (track_flags & FL_DIR &&
+	} else if ((track_flags & FL_DIR) &&
 		   last_slash_dir > 0 && last_slash_dir <= PATH_MAX) {
 		/*
 		 * We have a separate test for the directory case,
@@ -170,7 +176,7 @@ static int lstat_cache(int len, const char *name,
 		cache.len = last_slash_dir;
 		cache.flags = FL_DIR;
 	} else {
-		reset_lstat_cache(track_flags, prefix_len_stat_func);
+		reset_lstat_cache();
 	}
 	return ret_flags;
 }
@@ -179,19 +185,19 @@ static int lstat_cache(int len, const char *name,
  * Invalidate the given 'name' from the cache, if 'name' matches
  * completely with the cache.
  */
-void invalidate_lstat_cache(int len, const char *name)
+void invalidate_lstat_cache(const char *name, int len)
 {
 	int match_len, previous_slash;
 
-	match_len = longest_match_lstat_cache(len, name, &previous_slash);
+	match_len = longest_path_match(name, len, cache.path, cache.len,
+				       &previous_slash);
 	if (len == match_len) {
 		if ((cache.track_flags & FL_DIR) && previous_slash > 0) {
 			cache.path[previous_slash] = '\0';
 			cache.len = previous_slash;
 			cache.flags = FL_DIR;
 		} else
-			reset_lstat_cache(cache.track_flags,
-					  cache.prefix_len_stat_func);
+			reset_lstat_cache();
 	}
 }
 
@@ -200,7 +206,7 @@ void invalidate_lstat_cache(int len, const char *name)
  */
 void clear_lstat_cache(void)
 {
-	reset_lstat_cache(0, 0);
+	reset_lstat_cache();
 }
 
 #define USE_ONLY_LSTAT  0
@@ -208,9 +214,9 @@ void clear_lstat_cache(void)
 /*
  * Return non-zero if path 'name' has a leading symlink component
  */
-int has_symlink_leading_path(int len, const char *name)
+int has_symlink_leading_path(const char *name, int len)
 {
-	return lstat_cache(len, name,
+	return lstat_cache(name, len,
 			   FL_SYMLINK|FL_DIR, USE_ONLY_LSTAT) &
 		FL_SYMLINK;
 }
@@ -219,9 +225,9 @@ int has_symlink_leading_path(int len, const char *name)
  * Return non-zero if path 'name' has a leading symlink component or
  * if some leading path component does not exists.
  */
-int has_symlink_or_noent_leading_path(int len, const char *name)
+int has_symlink_or_noent_leading_path(const char *name, int len)
 {
-	return lstat_cache(len, name,
+	return lstat_cache(name, len,
 			   FL_SYMLINK|FL_NOENT|FL_DIR, USE_ONLY_LSTAT) &
 		(FL_SYMLINK|FL_NOENT);
 }
@@ -233,9 +239,68 @@ int has_symlink_or_noent_leading_path(int len, const char *name)
  * 'prefix_len', thus we then allow for symlinks in the prefix part as
  * long as those points to real existing directories.
  */
-int has_dirs_only_path(int len, const char *name, int prefix_len)
+int has_dirs_only_path(const char *name, int len, int prefix_len)
 {
-	return lstat_cache(len, name,
+	return lstat_cache(name, len,
 			   FL_DIR|FL_FULLPATH, prefix_len) &
 		FL_DIR;
 }
+
+static struct removal_def {
+	char path[PATH_MAX];
+	int len;
+} removal;
+
+static void do_remove_scheduled_dirs(int new_len)
+{
+	while (removal.len > new_len) {
+		removal.path[removal.len] = '\0';
+		if (rmdir(removal.path))
+			break;
+		do {
+			removal.len--;
+		} while (removal.len > new_len &&
+			 removal.path[removal.len] != '/');
+	}
+	removal.len = new_len;
+	return;
+}
+
+void schedule_dir_for_removal(const char *name, int len)
+{
+	int match_len, last_slash, i, previous_slash;
+
+	match_len = last_slash = i =
+		longest_path_match(name, len, removal.path, removal.len,
+				   &previous_slash);
+	/* Find last slash inside 'name' */
+	while (i < len) {
+		if (name[i] == '/')
+			last_slash = i;
+		i++;
+	}
+
+	/*
+	 * If we are about to go down the directory tree, we check if
+	 * we must first go upwards the tree, such that we then can
+	 * remove possible empty directories as we go upwards.
+	 */
+	if (match_len < last_slash && match_len < removal.len)
+		do_remove_scheduled_dirs(match_len);
+	/*
+	 * If we go deeper down the directory tree, we only need to
+	 * save the new path components as we go down.
+	 */
+	if (match_len < last_slash) {
+		memcpy(&removal.path[match_len], &name[match_len],
+		       last_slash - match_len);
+		removal.len = last_slash;
+	}
+	return;
+}
+
+void remove_scheduled_dirs(void)
+{
+	do_remove_scheduled_dirs(0);
+	return;
+}
diff --git a/unpack-trees.c b/unpack-trees.c
index e547282ed5..da2e3c0915 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -52,36 +52,17 @@ static void add_entry(struct unpack_trees_options *o, struct cache_entry *ce,
 	add_index_entry(&o->result, new, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE|ADD_CACHE_SKIP_DFCHECK);
 }
 
-/* Unlink the last component and attempt to remove leading
- * directories, in case this unlink is the removal of the
- * last entry in the directory -- empty directories are removed.
+/*
+ * Unlink the last component and schedule the leading directories for
+ * removal, such that empty directories get removed.
  */
 static void unlink_entry(struct cache_entry *ce)
 {
-	char *cp, *prev;
-	char *name = ce->name;
-
-	if (has_symlink_or_noent_leading_path(ce_namelen(ce), ce->name))
+	if (has_symlink_or_noent_leading_path(ce->name, ce_namelen(ce)))
 		return;
-	if (unlink(name))
+	if (unlink(ce->name))
 		return;
-	prev = NULL;
-	while (1) {
-		int status;
-		cp = strrchr(name, '/');
-		if (prev)
-			*prev = '/';
-		if (!cp)
-			break;
-
-		*cp = 0;
-		status = rmdir(name);
-		if (status) {
-			*cp = '/';
-			break;
-		}
-		prev = cp;
-	}
+	schedule_dir_for_removal(ce->name, ce_namelen(ce));
 }
 
 static struct checkout state;
@@ -112,11 +93,10 @@ static int check_updates(struct unpack_trees_options *o)
 			display_progress(progress, ++cnt);
 			if (o->update)
 				unlink_entry(ce);
-			remove_index_entry_at(&o->result, i);
-			i--;
-			continue;
 		}
 	}
+	remove_marked_cache_entries(&o->result);
+	remove_scheduled_dirs();
 
 	for (i = 0; i < index->cache_nr; i++) {
 		struct cache_entry *ce = index->cache[i];
@@ -380,8 +360,10 @@ 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;
+		o->result.timestamp.nsec = o->src_index->timestamp.nsec;
+	}
 	o->merge_size = len;
 
 	if (!dfc)
@@ -446,7 +428,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)) {
@@ -583,7 +565,7 @@ static int verify_absent(struct cache_entry *ce, const char *action,
 	if (o->index_only || o->reset || !o->update)
 		return 0;
 
-	if (has_symlink_or_noent_leading_path(ce_namelen(ce), ce->name))
+	if (has_symlink_or_noent_leading_path(ce->name, ce_namelen(ce)))
 		return 0;
 
 	if (!lstat(ce->name, &st)) {