From: Junio C Hamano <gitster@pobox.com>
Date: Tue, 29 Jan 2019 20:47:55 +0000 (-0800)
Subject: Merge branch 'bc/sha-256'
X-Git-Tag: v2.21.0-rc0~65
X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/33e4ae9c509e0ecdc6508475f2974d275539616e?ds=inline;hp=-c

Merge branch 'bc/sha-256'

Add sha-256 hash and plug it through the code to allow building Git
with the "NewHash".

* bc/sha-256:
hash: add an SHA-256 implementation using OpenSSL
sha256: add an SHA-256 implementation using libgcrypt
Add a base implementation of SHA-256 support
commit-graph: convert to using the_hash_algo
t/helper: add a test helper to compute hash speed
sha1-file: add a constant for hash block size
t: make the sha1 test-tool helper generic
t: add basic tests for our SHA-1 implementation
cache: make hashcmp and hasheq work with larger hashes
hex: introduce functions to print arbitrary hashes
sha1-file: provide functions to look up hash algorithms
sha1-file: rename algorithm to "sha1"
---

33e4ae9c509e0ecdc6508475f2974d275539616e
diff --combined Makefile
index 1a44c811aa,3164e2aeee..6e8d017e8e
--- a/Makefile
+++ b/Makefile
@@@ -59,13 -59,6 +59,13 @@@ all:
  # Define CURL_CONFIG to curl's configuration program that prints information
  # about the library (e.g., its version number).  The default is 'curl-config'.
  #
 +# Define CURL_LDFLAGS to specify flags that you need to link when using libcurl,
 +# if you do not want to rely on the libraries provided by CURL_CONFIG.  The
 +# default value is a result of `curl-config --libs`.  An example value for
 +# CURL_LDFLAGS is as follows:
 +#
 +#     CURL_LDFLAGS=-lcurl
 +#
  # Define NO_EXPAT if you do not have expat installed.  git-http-push is
  # not built, and you cannot push using http:// and https:// transports (dumb).
  #
@@@ -186,10 -179,20 +186,16 @@@
  # in one call to the platform's SHA1_Update(). e.g. APPLE_COMMON_CRYPTO
  # wants 'SHA1_MAX_BLOCK_SIZE=1024L*1024L*1024L' defined.
  #
+ # Define BLK_SHA256 to use the built-in SHA-256 routines.
+ #
+ # Define GCRYPT_SHA256 to use the SHA-256 routines in libgcrypt.
+ #
+ # Define OPENSSL_SHA256 to use the SHA-256 routines in OpenSSL.
+ #
  # Define NEEDS_CRYPTO_WITH_SSL if you need -lcrypto when using -lssl (Darwin).
  #
  # Define NEEDS_SSL_WITH_CRYPTO if you need -lssl when using -lcrypto (Darwin).
  #
 -# Define NEEDS_SSL_WITH_CURL if you need -lssl with -lcurl (Minix).
 -#
 -# Define NEEDS_IDN_WITH_CURL if you need -lidn when using -lcurl (Minix).
 -#
  # Define NEEDS_LIBICONV if linking with libc is not enough (Darwin).
  #
  # Define NEEDS_LIBINTL_BEFORE_LIBICONV if you need libintl before libiconv.
@@@ -210,12 -213,10 +216,12 @@@
  # Define MMAP_PREVENTS_DELETE if a file that is currently mmapped cannot be
  # deleted or cannot be replaced using rename().
  #
 +# Define NO_POLL_H if you don't have poll.h.
 +#
  # Define NO_SYS_POLL_H if you don't have sys/poll.h.
  #
  # Define NO_POLL if you do not have or don't want to use poll().
 -# This also implies NO_SYS_POLL_H.
 +# This also implies NO_POLL_H and NO_SYS_POLL_H.
  #
  # Define NEEDS_SYS_PARAM_H if you need to include sys/param.h to compile,
  # *PLEASE* REPORT to git@vger.kernel.org if your platform needs this;
@@@ -367,6 -368,11 +373,6 @@@
  # Define HAVE_DEV_TTY if your system can open /dev/tty to interact with the
  # user.
  #
 -# Define GETTEXT_POISON if you are debugging the choice of strings marked
 -# for translation.  In a GETTEXT_POISON build, you can turn all strings marked
 -# for translation into gibberish by setting the GIT_GETTEXT_POISON variable
 -# (to any value) in your environment.
 -#
  # Define JSMIN to point to JavaScript minifier that functions as
  # a filter to have gitweb.js minified.
  #
@@@ -400,7 -406,7 +406,7 @@@
  # (defaults to "man") if you want to have a different default when
  # "git help" is called without a parameter specifying the format.
  #
 -# Define TEST_GIT_INDEX_VERSION to 2, 3 or 4 to run the test suite
 +# Define GIT_TEST_INDEX_VERSION to 2, 3 or 4 to run the test suite
  # with a different indexfile format version.  If it isn't set the index
  # file format used is index-v[23].
  #
@@@ -590,8 -596,6 +596,8 @@@ XDIFF_OBJS 
  VCSSVN_OBJS =
  GENERATED_H =
  EXTRA_CPPFLAGS =
 +FUZZ_OBJS =
 +FUZZ_PROGRAMS =
  LIB_OBJS =
  PROGRAM_OBJS =
  PROGRAMS =
@@@ -616,7 -620,7 +622,7 @@@ SCRIPT_SH += git-merge-one-file.s
  SCRIPT_SH += git-merge-resolve.sh
  SCRIPT_SH += git-mergetool.sh
  SCRIPT_SH += git-quiltimport.sh
 -SCRIPT_SH += git-rebase.sh
 +SCRIPT_SH += git-legacy-rebase.sh
  SCRIPT_SH += git-remote-testgit.sh
  SCRIPT_SH += git-request-pull.sh
  SCRIPT_SH += git-stash.sh
@@@ -626,7 -630,7 +632,7 @@@ SCRIPT_SH += git-web--browse.s
  SCRIPT_LIB += git-mergetool--lib
  SCRIPT_LIB += git-parse-remote
  SCRIPT_LIB += git-rebase--am
 -SCRIPT_LIB += git-rebase--interactive
 +SCRIPT_LIB += git-rebase--common
  SCRIPT_LIB += git-rebase--preserve-merges
  SCRIPT_LIB += git-rebase--merge
  SCRIPT_LIB += git-sh-setup
@@@ -684,14 -688,6 +690,14 @@@ SCRIPTS = $(SCRIPT_SH_INS) 
  
  ETAGS_TARGET = TAGS
  
 +FUZZ_OBJS += fuzz-pack-headers.o
 +FUZZ_OBJS += fuzz-pack-idx.o
 +
 +# Always build fuzz objects even if not testing, to prevent bit-rot.
 +all:: $(FUZZ_OBJS)
 +
 +FUZZ_PROGRAMS += $(patsubst %.o,%,$(FUZZ_OBJS))
 +
  # Empty...
  EXTRA_PROGRAMS =
  
@@@ -724,7 -720,9 +730,9 @@@ TEST_BUILTINS_OBJS += test-dump-split-i
  TEST_BUILTINS_OBJS += test-dump-untracked-cache.o
  TEST_BUILTINS_OBJS += test-example-decorate.o
  TEST_BUILTINS_OBJS += test-genrandom.o
+ TEST_BUILTINS_OBJS += test-hash.o
  TEST_BUILTINS_OBJS += test-hashmap.o
+ TEST_BUILTINS_OBJS += test-hash-speed.o
  TEST_BUILTINS_OBJS += test-index-version.o
  TEST_BUILTINS_OBJS += test-json-writer.o
  TEST_BUILTINS_OBJS += test-lazy-init-name-hash.o
@@@ -747,11 -745,11 +755,12 @@@ TEST_BUILTINS_OBJS += test-run-command.
  TEST_BUILTINS_OBJS += test-scrap-cache-tree.o
  TEST_BUILTINS_OBJS += test-sha1.o
  TEST_BUILTINS_OBJS += test-sha1-array.o
+ TEST_BUILTINS_OBJS += test-sha256.o
  TEST_BUILTINS_OBJS += test-sigchain.o
  TEST_BUILTINS_OBJS += test-strcmp-offset.o
  TEST_BUILTINS_OBJS += test-string-list.o
  TEST_BUILTINS_OBJS += test-submodule-config.o
 +TEST_BUILTINS_OBJS += test-submodule-nested-repo-config.o
  TEST_BUILTINS_OBJS += test-subprocess.o
  TEST_BUILTINS_OBJS += test-urlmatch-normalization.o
  TEST_BUILTINS_OBJS += test-wildmatch.o
@@@ -955,7 -953,6 +964,7 @@@ LIB_OBJS += quote.
  LIB_OBJS += range-diff.o
  LIB_OBJS += reachable.o
  LIB_OBJS += read-cache.o
 +LIB_OBJS += rebase-interactive.o
  LIB_OBJS += reflog-walk.o
  LIB_OBJS += refs.o
  LIB_OBJS += refs/files-backend.o
@@@ -993,7 -990,6 +1002,7 @@@ LIB_OBJS += sub-process.
  LIB_OBJS += symlinks.o
  LIB_OBJS += tag.o
  LIB_OBJS += tempfile.o
 +LIB_OBJS += thread-utils.o
  LIB_OBJS += tmp-objdir.o
  LIB_OBJS += trace.o
  LIB_OBJS += trailer.o
@@@ -1096,8 -1092,7 +1105,8 @@@ BUILTIN_OBJS += builtin/pull.
  BUILTIN_OBJS += builtin/push.o
  BUILTIN_OBJS += builtin/range-diff.o
  BUILTIN_OBJS += builtin/read-tree.o
 -BUILTIN_OBJS += builtin/rebase--helper.o
 +BUILTIN_OBJS += builtin/rebase.o
 +BUILTIN_OBJS += builtin/rebase--interactive.o
  BUILTIN_OBJS += builtin/receive-pack.o
  BUILTIN_OBJS += builtin/reflog.o
  BUILTIN_OBJS += builtin/remote.o
@@@ -1309,17 -1304,20 +1318,17 @@@ els
  	ifdef CURLDIR
  		# Try "-Wl,-rpath=$(CURLDIR)/$(lib)" in such a case.
  		BASIC_CFLAGS += -I$(CURLDIR)/include
 -		CURL_LIBCURL = -L$(CURLDIR)/$(lib) $(CC_LD_DYNPATH)$(CURLDIR)/$(lib) -lcurl
 +		CURL_LIBCURL = -L$(CURLDIR)/$(lib) $(CC_LD_DYNPATH)$(CURLDIR)/$(lib)
  	else
 -		CURL_LIBCURL = -lcurl
 -	endif
 -	ifdef NEEDS_SSL_WITH_CURL
 -		CURL_LIBCURL += -lssl
 -		ifdef NEEDS_CRYPTO_WITH_SSL
 -			CURL_LIBCURL += -lcrypto
 -		endif
 -	endif
 -	ifdef NEEDS_IDN_WITH_CURL
 -		CURL_LIBCURL += -lidn
 +		CURL_LIBCURL =
  	endif
  
 +ifdef CURL_LDFLAGS
 +	CURL_LIBCURL += $(CURL_LDFLAGS)
 +else
 +	CURL_LIBCURL += $(shell $(CURL_CONFIG) --libs)
 +endif
 +
  	REMOTE_CURL_PRIMARY = git-remote-http$X
  	REMOTE_CURL_ALIASES = git-remote-https$X git-remote-ftp$X git-remote-ftps$X
  	REMOTE_CURL_NAMES = $(REMOTE_CURL_PRIMARY) $(REMOTE_CURL_ALIASES)
@@@ -1451,14 -1449,13 +1460,14 @@@ ifdef NO_SYMLINK_HEA
  	BASIC_CFLAGS += -DNO_SYMLINK_HEAD
  endif
  ifdef GETTEXT_POISON
 -	BASIC_CFLAGS += -DGETTEXT_POISON
 +$(warning The GETTEXT_POISON option has been removed in favor of runtime GIT_TEST_GETTEXT_POISON. See t/README!)
  endif
  ifdef NO_GETTEXT
  	BASIC_CFLAGS += -DNO_GETTEXT
  	USE_GETTEXT_SCHEME ?= fallthrough
  endif
  ifdef NO_POLL
 +	NO_POLL_H = YesPlease
  	NO_SYS_POLL_H = YesPlease
  	COMPAT_CFLAGS += -DNO_POLL -Icompat/poll
  	COMPAT_OBJS += compat/poll/poll.o
@@@ -1497,9 -1494,6 +1506,9 @@@ endi
  ifdef NO_SYS_SELECT_H
  	BASIC_CFLAGS += -DNO_SYS_SELECT_H
  endif
 +ifdef NO_POLL_H
 +	BASIC_CFLAGS += -DNO_POLL_H
 +endif
  ifdef NO_SYS_POLL_H
  	BASIC_CFLAGS += -DNO_SYS_POLL_H
  endif
@@@ -1646,6 -1640,19 +1655,19 @@@ endi
  endif
  endif
  
+ ifdef OPENSSL_SHA256
+ 	EXTLIBS += $(LIB_4_CRYPTO)
+ 	BASIC_CFLAGS += -DSHA256_OPENSSL
+ else
+ ifdef GCRYPT_SHA256
+ 	BASIC_CFLAGS += -DSHA256_GCRYPT
+ 	EXTLIBS += -lgcrypt
+ else
+ 	LIB_OBJS += sha256/block/sha256.o
+ 	BASIC_CFLAGS += -DSHA256_BLK
+ endif
+ endif
+ 
  ifdef SHA1_MAX_BLOCK_SIZE
  	LIB_OBJS += compat/sha1-chunked.o
  	BASIC_CFLAGS += -DSHA1_MAX_BLOCK_SIZE="$(SHA1_MAX_BLOCK_SIZE)"
@@@ -1679,6 -1686,7 +1701,6 @@@ ifdef NO_PTHREAD
  else
  	BASIC_CFLAGS += $(PTHREAD_CFLAGS)
  	EXTLIBS += $(PTHREAD_LIBS)
 -	LIB_OBJS += thread-utils.o
  endif
  
  ifdef HAVE_PATHS_H
@@@ -1810,7 -1818,6 +1832,7 @@@ ifndef 
  	QUIET_MSGFMT   = @echo '   ' MSGFMT $@;
  	QUIET_GCOV     = @echo '   ' GCOV $@;
  	QUIET_SP       = @echo '   ' SP $<;
 +	QUIET_HDR      = @echo '   ' HDR $<;
  	QUIET_RC       = @echo '   ' RC $@;
  	QUIET_SUBDIR0  = +@subdir=
  	QUIET_SUBDIR1  = ;$(NO_SUBDIR) echo '   ' SUBDIR $$subdir; \
@@@ -2072,7 -2079,7 +2094,7 @@@ $(BUILT_INS): git$
  
  command-list.h: generate-cmdlist.sh command-list.txt
  
 -command-list.h: $(wildcard Documentation/git*.txt) Documentation/*config.txt
 +command-list.h: $(wildcard Documentation/git*.txt) Documentation/*config.txt Documentation/config/*.txt
  	$(QUIET_GEN)$(SHELL_PATH) ./generate-cmdlist.sh command-list.txt >$@+ && mv $@+ $@
  
  SCRIPT_DEFINES = $(SHELL_PATH_SQ):$(DIFF_SQ):$(GIT_VERSION):\
@@@ -2112,7 -2119,7 +2134,7 @@@ $(SCRIPT_LIB) : % : %.sh GIT-SCRIPT-DEF
  	$(QUIET_GEN)$(cmd_munge_script) && \
  	mv $@+ $@
  
 -git.res: git.rc GIT-VERSION-FILE
 +git.res: git.rc GIT-VERSION-FILE GIT-PREFIX
  	$(QUIET_RC)$(RC) \
  	  $(join -DMAJOR= -DMINOR= -DMICRO= -DPATCHLEVEL=, $(wordlist 1, 4, \
  	    $(shell echo $(GIT_VERSION) 0 0 0 0 | tr '.a-zA-Z-' ' '))) \
@@@ -2267,7 -2274,6 +2289,7 @@@ TEST_OBJS := $(patsubst %$X,%.o,$(TEST_
  OBJECTS := $(LIB_OBJS) $(BUILTIN_OBJS) $(PROGRAM_OBJS) $(TEST_OBJS) \
  	$(XDIFF_OBJS) \
  	$(VCSSVN_OBJS) \
 +	$(FUZZ_OBJS) \
  	common-main.o \
  	git.o
  ifndef NO_CURL
@@@ -2438,6 -2444,7 +2460,6 @@@ XGETTEXT_FLAGS_PERL = $(XGETTEXT_FLAGS
  LOCALIZED_C = $(C_OBJ:o=c) $(LIB_H) $(GENERATED_H)
  LOCALIZED_SH = $(SCRIPT_SH)
  LOCALIZED_SH += git-parse-remote.sh
 -LOCALIZED_SH += git-rebase--interactive.sh
  LOCALIZED_SH += git-rebase--preserve-merges.sh
  LOCALIZED_SH += git-sh-setup.sh
  LOCALIZED_PERL = $(SCRIPT_PERL)
@@@ -2592,7 -2599,6 +2614,7 @@@ GIT-BUILD-OPTIONS: FORC
  	@echo NO_UNIX_SOCKETS=\''$(subst ','\'',$(subst ','\'',$(NO_UNIX_SOCKETS)))'\' >>$@+
  	@echo PAGER_ENV=\''$(subst ','\'',$(subst ','\'',$(PAGER_ENV)))'\' >>$@+
  	@echo DC_SHA1=\''$(subst ','\'',$(subst ','\'',$(DC_SHA1)))'\' >>$@+
 +	@echo X=\'$(X)\' >>$@+
  ifdef TEST_OUTPUT_DIRECTORY
  	@echo TEST_OUTPUT_DIRECTORY=\''$(subst ','\'',$(subst ','\'',$(TEST_OUTPUT_DIRECTORY)))'\' >>$@+
  endif
@@@ -2606,6 -2612,7 +2628,6 @@@ ifdef GIT_TEST_CMP_USE_COPIED_CONTEX
  	@echo GIT_TEST_CMP_USE_COPIED_CONTEXT=YesPlease >>$@+
  endif
  	@echo NO_GETTEXT=\''$(subst ','\'',$(subst ','\'',$(NO_GETTEXT)))'\' >>$@+
 -	@echo GETTEXT_POISON=\''$(subst ','\'',$(subst ','\'',$(GETTEXT_POISON)))'\' >>$@+
  ifdef GIT_PERF_REPEAT_COUNT
  	@echo GIT_PERF_REPEAT_COUNT=\''$(subst ','\'',$(subst ','\'',$(GIT_PERF_REPEAT_COUNT)))'\' >>$@+
  endif
@@@ -2624,8 -2631,8 +2646,8 @@@ endi
  ifdef GIT_INTEROP_MAKE_OPTS
  	@echo GIT_INTEROP_MAKE_OPTS=\''$(subst ','\'',$(subst ','\'',$(GIT_INTEROP_MAKE_OPTS)))'\' >>$@+
  endif
 -ifdef TEST_GIT_INDEX_VERSION
 -	@echo TEST_GIT_INDEX_VERSION=\''$(subst ','\'',$(subst ','\'',$(TEST_GIT_INDEX_VERSION)))'\' >>$@+
 +ifdef GIT_TEST_INDEX_VERSION
 +	@echo GIT_TEST_INDEX_VERSION=\''$(subst ','\'',$(subst ','\'',$(GIT_TEST_INDEX_VERSION)))'\' >>$@+
  endif
  	@if cmp $@+ $@ >/dev/null 2>&1; then $(RM) $@+; else mv $@+ $@; fi
  
@@@ -2693,17 -2700,6 +2715,17 @@@ $(SP_OBJ): %.sp: %.c GIT-CFLAGS FORC
  .PHONY: sparse $(SP_OBJ)
  sparse: $(SP_OBJ)
  
 +GEN_HDRS := command-list.h unicode-width.h
 +EXCEPT_HDRS := $(GEN_HDRS) compat% xdiff%
 +CHK_HDRS = $(filter-out $(EXCEPT_HDRS),$(patsubst ./%,%,$(LIB_H)))
 +HCO = $(patsubst %.h,%.hco,$(CHK_HDRS))
 +
 +$(HCO): %.hco: %.h FORCE
 +	$(QUIET_HDR)$(CC) -include git-compat-util.h -I. -o /dev/null -c -xc $<
 +
 +.PHONY: hdr-check $(HCO)
 +hdr-check: $(HCO)
 +
  .PHONY: style
  style:
  	git clang-format --style file --diff --extensions c,h
@@@ -2742,12 -2738,9 +2764,12 @@@ endi
  	then \
  		echo '    ' SPATCH result: $@; \
  	fi
 -coccicheck: $(addsuffix .patch,$(wildcard contrib/coccinelle/*.cocci))
 +coccicheck: $(addsuffix .patch,$(filter-out %.pending.cocci,$(wildcard contrib/coccinelle/*.cocci)))
 +
 +# See contrib/coccinelle/README
 +coccicheck-pending: $(addsuffix .patch,$(wildcard contrib/coccinelle/*.pending.cocci))
  
 -.PHONY: coccicheck
 +.PHONY: coccicheck coccicheck-pending
  
  ### Installation rules
  
@@@ -2968,7 -2961,6 +2990,7 @@@ clean: profile-clean coverage-clean coc
  	$(RM) $(LIB_FILE) $(XDIFF_LIB) $(VCSSVN_LIB)
  	$(RM) $(ALL_PROGRAMS) $(SCRIPT_LIB) $(BUILT_INS) git$X
  	$(RM) $(TEST_PROGRAMS) $(NO_INSTALL)
 +	$(RM) $(FUZZ_PROGRAMS)
  	$(RM) -r bin-wrappers $(dep_dirs)
  	$(RM) -r po/build/
  	$(RM) *.pyc *.pyo */*.pyc */*.pyo command-list.h $(ETAGS_TARGET) tags cscope*
@@@ -3093,26 -3085,3 +3115,26 @@@ cover_db: coverage-repor
  cover_db_html: cover_db
  	cover -report html -outputdir cover_db_html cover_db
  
 +
 +### Fuzz testing
 +#
 +# Building fuzz targets generally requires a special set of compiler flags that
 +# are not necessarily appropriate for general builds, and that vary greatly
 +# depending on the compiler version used.
 +#
 +# An example command to build against libFuzzer from LLVM 4.0.0:
 +#
 +# make CC=clang CXX=clang++ \
 +#      FUZZ_CXXFLAGS="-fsanitize-coverage=trace-pc-guard -fsanitize=address" \
 +#      LIB_FUZZING_ENGINE=/usr/lib/llvm-4.0/lib/libFuzzer.a \
 +#      fuzz-all
 +#
 +FUZZ_CXXFLAGS ?= $(CFLAGS)
 +
 +.PHONY: fuzz-all
 +
 +$(FUZZ_PROGRAMS): all
 +	$(QUIET_LINK)$(CXX) $(FUZZ_CXXFLAGS) $(LIB_OBJS) $(BUILTIN_OBJS) \
 +		$(XDIFF_OBJS) $(EXTLIBS) git.o $@.o $(LIB_FUZZING_ENGINE) -o $@
 +
 +fuzz-all: $(FUZZ_PROGRAMS)
diff --combined cache.h
index 49713cc5a5,a082164df8..d94eff88a9
--- a/cache.h
+++ b/cache.h
@@@ -45,10 -45,20 +45,20 @@@ unsigned long git_deflate_bound(git_zst
  /* The length in bytes and in hex digits of an object name (SHA-1 value). */
  #define GIT_SHA1_RAWSZ 20
  #define GIT_SHA1_HEXSZ (2 * GIT_SHA1_RAWSZ)
+ /* The block size of SHA-1. */
+ #define GIT_SHA1_BLKSZ 64
+ 
+ /* The length in bytes and in hex digits of an object name (SHA-256 value). */
+ #define GIT_SHA256_RAWSZ 32
+ #define GIT_SHA256_HEXSZ (2 * GIT_SHA256_RAWSZ)
+ /* The block size of SHA-256. */
+ #define GIT_SHA256_BLKSZ 64
  
  /* The length in byte and in hex digits of the largest possible hash value. */
- #define GIT_MAX_RAWSZ GIT_SHA1_RAWSZ
- #define GIT_MAX_HEXSZ GIT_SHA1_HEXSZ
+ #define GIT_MAX_RAWSZ GIT_SHA256_RAWSZ
+ #define GIT_MAX_HEXSZ GIT_SHA256_HEXSZ
+ /* The largest possible block size for any supported hash. */
+ #define GIT_MAX_BLKSZ GIT_SHA256_BLKSZ
  
  struct object_id {
  	unsigned char hash[GIT_MAX_RAWSZ];
@@@ -410,7 -420,7 +420,7 @@@ void validate_cache_entries(const struc
  
  #define read_cache() read_index(&the_index)
  #define read_cache_from(path) read_index_from(&the_index, (path), (get_git_dir()))
 -#define read_cache_preload(pathspec) read_index_preload(&the_index, (pathspec))
 +#define read_cache_preload(pathspec) read_index_preload(&the_index, (pathspec), 0)
  #define is_cache_unborn() is_index_unborn(&the_index)
  #define read_cache_unmerged() read_index_unmerged(&the_index)
  #define discard_cache() discard_index(&the_index)
@@@ -486,8 -496,6 +496,8 @@@ static inline enum object_type object_t
  #define INFOATTRIBUTES_FILE "info/attributes"
  #define ATTRIBUTE_MACRO_PREFIX "[attr]"
  #define GITMODULES_FILE ".gitmodules"
 +#define GITMODULES_INDEX ":.gitmodules"
 +#define GITMODULES_HEAD "HEAD:.gitmodules"
  #define GIT_NOTES_REF_ENVIRONMENT "GIT_NOTES_REF"
  #define GIT_NOTES_DEFAULT_REF "refs/notes/commits"
  #define GIT_NOTES_DISPLAY_REF_ENVIRONMENT "GIT_NOTES_DISPLAY_REF"
@@@ -661,12 -669,7 +671,12 @@@ extern int daemonize(void)
  /* Initialize and use the cache information */
  struct lock_file;
  extern int read_index(struct index_state *);
 -extern int read_index_preload(struct index_state *, const struct pathspec *pathspec);
 +extern void preload_index(struct index_state *index,
 +			  const struct pathspec *pathspec,
 +			  unsigned int refresh_flags);
 +extern int read_index_preload(struct index_state *,
 +			      const struct pathspec *pathspec,
 +			      unsigned int refresh_flags);
  extern int do_read_index(struct index_state *istate, const char *path,
  			 int must_exist); /* for testting only! */
  extern int read_index_from(struct index_state *, const char *path,
@@@ -710,7 -713,7 +720,7 @@@ extern int unmerged_index(const struct 
   * provided, the space-separated list of files that differ will be appended
   * to it.
   */
 -extern int index_has_changes(const struct index_state *istate,
 +extern int index_has_changes(struct index_state *istate,
  			     struct tree *tree,
  			     struct strbuf *sb);
  
@@@ -788,16 -791,14 +798,16 @@@ extern void *read_blob_data_from_index(
  #define CE_MATCH_REFRESH		0x10
  /* don't refresh_fsmonitor state or do stat comparison even if CE_FSMONITOR_VALID is true */
  #define CE_MATCH_IGNORE_FSMONITOR 0X20
 +extern int is_racy_timestamp(const struct index_state *istate,
 +			     const struct cache_entry *ce);
  extern int ie_match_stat(struct index_state *, const struct cache_entry *, struct stat *, unsigned int);
  extern int ie_modified(struct index_state *, const struct cache_entry *, struct stat *, unsigned int);
  
  #define HASH_WRITE_OBJECT 1
  #define HASH_FORMAT_CHECK 2
  #define HASH_RENORMALIZE  4
 -extern int index_fd(struct object_id *oid, int fd, struct stat *st, enum object_type type, const char *path, unsigned flags);
 -extern int index_path(struct object_id *oid, const char *path, struct stat *st, unsigned flags);
 +extern int index_fd(struct index_state *istate, struct object_id *oid, int fd, struct stat *st, enum object_type type, const char *path, unsigned flags);
 +extern int index_path(struct index_state *istate, struct object_id *oid, const char *path, struct stat *st, unsigned flags);
  
  /*
   * Record to sd the data from st that we use to check whether a file
@@@ -823,7 -824,6 +833,7 @@@ extern void fill_stat_cache_info(struc
  #define REFRESH_IGNORE_MISSING	0x0008	/* ignore non-existent */
  #define REFRESH_IGNORE_SUBMODULES	0x0010	/* ignore submodules */
  #define REFRESH_IN_PORCELAIN	0x0020	/* user friendly output, not "needs update" */
 +#define REFRESH_PROGRESS	0x0040  /* show progress bar if stderr is tty */
  extern int refresh_index(struct index_state *, unsigned int flags, const struct pathspec *pathspec, char *seen, const char *header_msg);
  extern struct cache_entry *refresh_cache_entry(struct index_state *, struct cache_entry *, unsigned int);
  
@@@ -911,6 -911,14 +921,6 @@@ int use_optional_locks(void)
  extern char comment_line_char;
  extern int auto_comment_line_char;
  
 -/* Windows only */
 -enum hide_dotfiles_type {
 -	HIDE_DOTFILES_FALSE = 0,
 -	HIDE_DOTFILES_TRUE,
 -	HIDE_DOTFILES_DOTGITONLY
 -};
 -extern enum hide_dotfiles_type hide_dotfiles;
 -
  enum log_refs_config {
  	LOG_REFS_UNSET = -1,
  	LOG_REFS_NONE = 0,
@@@ -959,13 -967,11 +969,13 @@@ extern int grafts_replace_parents
  extern int repository_format_precious_objects;
  extern char *repository_format_partial_clone;
  extern const char *core_partial_clone_filter_default;
 +extern int repository_format_worktree_config;
  
  struct repository_format {
  	int version;
  	int precious_objects;
  	char *partial_clone; /* value of extensions.partialclone */
 +	int worktree_config;
  	int is_bare;
  	int hash_algo;
  	char *work_tree;
@@@ -1028,16 -1034,12 +1038,12 @@@ extern const struct object_id null_oid
  static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)
  {
  	/*
- 	 * This is a temporary optimization hack. By asserting the size here,
- 	 * we let the compiler know that it's always going to be 20, which lets
- 	 * it turn this fixed-size memcmp into a few inline instructions.
- 	 *
- 	 * This will need to be extended or ripped out when we learn about
- 	 * hashes of different sizes.
+ 	 * Teach the compiler that there are only two possibilities of hash size
+ 	 * here, so that it can optimize for this case as much as possible.
  	 */
- 	if (the_hash_algo->rawsz != 20)
- 		BUG("hash size not yet supported by hashcmp");
- 	return memcmp(sha1, sha2, the_hash_algo->rawsz);
+ 	if (the_hash_algo->rawsz == GIT_MAX_RAWSZ)
+ 		return memcmp(sha1, sha2, GIT_MAX_RAWSZ);
+ 	return memcmp(sha1, sha2, GIT_SHA1_RAWSZ);
  }
  
  static inline int oidcmp(const struct object_id *oid1, const struct object_id *oid2)
@@@ -1047,7 -1049,13 +1053,13 @@@
  
  static inline int hasheq(const unsigned char *sha1, const unsigned char *sha2)
  {
- 	return !hashcmp(sha1, sha2);
+ 	/*
+ 	 * We write this here instead of deferring to hashcmp so that the
+ 	 * compiler can properly inline it and avoid calling memcmp.
+ 	 */
+ 	if (the_hash_algo->rawsz == GIT_MAX_RAWSZ)
+ 		return !memcmp(sha1, sha2, GIT_MAX_RAWSZ);
+ 	return !memcmp(sha1, sha2, GIT_SHA1_RAWSZ);
  }
  
  static inline int oideq(const struct object_id *oid1, const struct object_id *oid2)
@@@ -1365,9 -1373,9 +1377,9 @@@ extern int get_oid_hex(const char *hex
  extern int hex_to_bytes(unsigned char *binary, const char *hex, size_t len);
  
  /*
-  * Convert a binary sha1 to its hex equivalent. The `_r` variant is reentrant,
+  * Convert a binary hash to its hex equivalent. The `_r` variant is reentrant,
   * and writes the NUL-terminated output to the buffer `out`, which must be at
-  * least `GIT_SHA1_HEXSZ + 1` bytes, and returns a pointer to out for
+  * least `GIT_MAX_HEXSZ + 1` bytes, and returns a pointer to out for
   * convenience.
   *
   * The non-`_r` variant returns a static buffer, but uses a ring of 4
@@@ -1375,10 -1383,13 +1387,13 @@@
   *
   *   printf("%s -> %s", sha1_to_hex(one), sha1_to_hex(two));
   */
- extern char *sha1_to_hex_r(char *out, const unsigned char *sha1);
- extern char *oid_to_hex_r(char *out, const struct object_id *oid);
- extern char *sha1_to_hex(const unsigned char *sha1);	/* static buffer result! */
- extern char *oid_to_hex(const struct object_id *oid);	/* same static buffer as sha1_to_hex */
+ char *hash_to_hex_algop_r(char *buffer, const unsigned char *hash, const struct git_hash_algo *);
+ char *sha1_to_hex_r(char *out, const unsigned char *sha1);
+ char *oid_to_hex_r(char *out, const struct object_id *oid);
+ char *hash_to_hex_algop(const unsigned char *hash, const struct git_hash_algo *);	/* static buffer result! */
+ char *sha1_to_hex(const unsigned char *sha1);						/* same static buffer */
+ char *hash_to_hex(const unsigned char *hash);						/* same static buffer */
+ char *oid_to_hex(const struct object_id *oid);						/* same static buffer */
  
  /*
   * Parse a 40-character hexadecimal object ID starting from hex, updating the
@@@ -1486,7 -1497,6 +1501,7 @@@ extern const char *fmt_name(const char 
  extern const char *ident_default_name(void);
  extern const char *ident_default_email(void);
  extern const char *git_editor(void);
 +extern const char *git_sequence_editor(void);
  extern const char *git_pager(int stdout_is_tty);
  extern int is_terminal_dumb(void);
  extern int git_ident_config(const char *, const char *, void *);
@@@ -1539,9 -1549,9 +1554,9 @@@ struct checkout 
  #define CHECKOUT_INIT { NULL, "" }
  
  #define TEMPORARY_FILENAME_LENGTH 25
 -extern int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *topath);
 +extern int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *topath, int *nr_checkouts);
  extern void enable_delayed_checkout(struct checkout *state);
 -extern int finish_delayed_checkout(struct checkout *state);
 +extern int finish_delayed_checkout(struct checkout *state, int *nr_checkouts);
  
  struct cache_def {
  	struct strbuf path;
@@@ -1710,7 -1720,7 +1725,7 @@@ void shift_tree_by(const struct object_
  /* All WS_* -- when extended, adapt diff.c emit_symbol */
  #define WS_RULE_MASK           07777
  extern unsigned whitespace_rule_cfg;
 -extern unsigned whitespace_rule(const char *);
 +extern unsigned whitespace_rule(struct index_state *, const char *);
  extern unsigned parse_whitespace_rule(const char *);
  extern unsigned ws_check(const char *line, int len, unsigned ws_rule);
  extern void ws_check_emit(const char *line, int len, unsigned ws_rule, FILE *stream, const char *set, const char *reset, const char *ws);
@@@ -1732,12 -1742,10 +1747,12 @@@ extern struct startup_info *startup_inf
  
  /* merge.c */
  struct commit_list;
 -int try_merge_command(const char *strategy, size_t xopts_nr,
 +int try_merge_command(struct repository *r,
 +		const char *strategy, size_t xopts_nr,
  		const char **xopts, struct commit_list *common,
  		const char *head_arg, struct commit_list *remotes);
 -int checkout_fast_forward(const struct object_id *from,
 +int checkout_fast_forward(struct repository *r,
 +			  const struct object_id *from,
  			  const struct object_id *to,
  			  int overwrite_ignore);
  
diff --combined commit-graph.c
index 0d6ba6da2d,7a28fbb03f..3f9c03afd5
--- a/commit-graph.c
+++ b/commit-graph.c
@@@ -13,9 -13,6 +13,9 @@@
  #include "commit-graph.h"
  #include "object-store.h"
  #include "alloc.h"
 +#include "hashmap.h"
 +#include "replace-object.h"
 +#include "progress.h"
  
  #define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */
  #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
@@@ -23,17 -20,13 +23,12 @@@
  #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
  #define GRAPH_CHUNKID_LARGEEDGES 0x45444745 /* "EDGE" */
  
- #define GRAPH_DATA_WIDTH 36
+ #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
  
  #define GRAPH_VERSION_1 0x1
  #define GRAPH_VERSION GRAPH_VERSION_1
  
- #define GRAPH_OID_VERSION_SHA1 1
- #define GRAPH_OID_LEN_SHA1 GIT_SHA1_RAWSZ
- #define GRAPH_OID_VERSION GRAPH_OID_VERSION_SHA1
- #define GRAPH_OID_LEN GRAPH_OID_LEN_SHA1
- 
  #define GRAPH_OCTOPUS_EDGES_NEEDED 0x80000000
 -#define GRAPH_PARENT_MISSING 0x7fffffff
  #define GRAPH_EDGE_LAST_MASK 0x7fffffff
  #define GRAPH_PARENT_NONE 0x70000000
  
@@@ -43,13 -36,18 +38,18 @@@
  #define GRAPH_FANOUT_SIZE (4 * 256)
  #define GRAPH_CHUNKLOOKUP_WIDTH 12
  #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
- 			+ GRAPH_FANOUT_SIZE + GRAPH_OID_LEN)
+ 			+ GRAPH_FANOUT_SIZE + the_hash_algo->rawsz)
  
  char *get_commit_graph_filename(const char *obj_dir)
  {
  	return xstrfmt("%s/info/commit-graph", obj_dir);
  }
  
+ static uint8_t oid_version(void)
+ {
+ 	return 1;
+ }
+ 
  static struct commit_graph *alloc_commit_graph(void)
  {
  	struct commit_graph *g = xcalloc(1, sizeof(*g));
@@@ -58,28 -56,6 +58,28 @@@
  	return g;
  }
  
 +extern int read_replace_refs;
 +
 +static int commit_graph_compatible(struct repository *r)
 +{
 +	if (!r->gitdir)
 +		return 0;
 +
 +	if (read_replace_refs) {
 +		prepare_replace_object(r);
 +		if (hashmap_get_size(&r->objects->replace_map->map))
 +			return 0;
 +	}
 +
 +	prepare_commit_graft(r);
 +	if (r->parsed_objects && r->parsed_objects->grafts_nr)
 +		return 0;
 +	if (is_repository_shallow(r))
 +		return 0;
 +
 +	return 1;
 +}
 +
  struct commit_graph *load_commit_graph_one(const char *graph_file)
  {
  	void *graph_map;
@@@ -124,15 -100,15 +124,15 @@@
  	}
  
  	hash_version = *(unsigned char*)(data + 5);
- 	if (hash_version != GRAPH_OID_VERSION) {
+ 	if (hash_version != oid_version()) {
  		error(_("hash version %X does not match version %X"),
- 		      hash_version, GRAPH_OID_VERSION);
+ 		      hash_version, oid_version());
  		goto cleanup_fail;
  	}
  
  	graph = alloc_commit_graph();
  
- 	graph->hash_len = GRAPH_OID_LEN;
+ 	graph->hash_len = the_hash_algo->rawsz;
  	graph->num_chunks = *(unsigned char*)(data + 6);
  	graph->graph_fd = fd;
  	graph->data = graph_map;
@@@ -148,7 -124,7 +148,7 @@@
  
  		chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
  
- 		if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
+ 		if (chunk_offset > graph_size - the_hash_algo->rawsz) {
  			error(_("improper chunk offset %08x%08x"), (uint32_t)(chunk_offset >> 32),
  			      (uint32_t)chunk_offset);
  			goto cleanup_fail;
@@@ -229,7 -205,8 +229,7 @@@ static void prepare_commit_graph_one(st
   */
  static int prepare_commit_graph(struct repository *r)
  {
 -	struct alternate_object_database *alt;
 -	char *obj_dir;
 +	struct object_directory *odb;
  	int config_value;
  
  	if (r->objects->commit_graph_attempted)
@@@ -247,14 -224,13 +247,14 @@@
  		 */
  		return 0;
  
 -	obj_dir = r->objects->objectdir;
 -	prepare_commit_graph_one(r, obj_dir);
 +	if (!commit_graph_compatible(r))
 +		return 0;
 +
  	prepare_alt_odb(r);
 -	for (alt = r->objects->alt_odb_list;
 -	     !r->objects->commit_graph && alt;
 -	     alt = alt->next)
 -		prepare_commit_graph_one(r, alt->path);
 +	for (odb = r->objects->odb;
 +	     !r->objects->commit_graph && odb;
 +	     odb = odb->next)
 +		prepare_commit_graph_one(r, odb->path);
  	return !!r->objects->commit_graph;
  }
  
@@@ -276,10 -252,10 +276,10 @@@ int generation_numbers_enabled(struct r
  	return !!first_generation;
  }
  
 -static void close_commit_graph(void)
 +void close_commit_graph(struct repository *r)
  {
 -	free_commit_graph(the_repository->objects->commit_graph);
 -	the_repository->objects->commit_graph = NULL;
 +	free_commit_graph(r->objects->commit_graph);
 +	r->objects->commit_graph = NULL;
  }
  
  static int bsearch_graph(struct commit_graph *g, struct object_id *oid, uint32_t *pos)
@@@ -492,9 -468,7 +492,9 @@@ static void write_graph_chunk_data(stru
  					      commit_to_sha1);
  
  			if (edge_value < 0)
 -				edge_value = GRAPH_PARENT_MISSING;
 +				BUG("missing parent %s for commit %s",
 +				    oid_to_hex(&parent->item->object.oid),
 +				    oid_to_hex(&(*list)->object.oid));
  		}
  
  		hashwrite_be32(f, edge_value);
@@@ -512,9 -486,7 +512,9 @@@
  					      nr_commits,
  					      commit_to_sha1);
  			if (edge_value < 0)
 -				edge_value = GRAPH_PARENT_MISSING;
 +				BUG("missing parent %s for commit %s",
 +				    oid_to_hex(&parent->item->object.oid),
 +				    oid_to_hex(&(*list)->object.oid));
  		}
  
  		hashwrite_be32(f, edge_value);
@@@ -567,9 -539,7 +567,9 @@@ static void write_graph_chunk_large_edg
  						  commit_to_sha1);
  
  			if (edge_value < 0)
 -				edge_value = GRAPH_PARENT_MISSING;
 +				BUG("missing parent %s for commit %s",
 +				    oid_to_hex(&parent->item->object.oid),
 +				    oid_to_hex(&(*list)->object.oid));
  			else if (!parent->next)
  				edge_value |= GRAPH_LAST_EDGE;
  
@@@ -597,8 -567,6 +597,8 @@@ struct packed_oid_list 
  	struct object_id *list;
  	int nr;
  	int alloc;
 +	struct progress *progress;
 +	int progress_done;
  };
  
  static int add_packed_commits(const struct object_id *oid,
@@@ -611,9 -579,6 +611,9 @@@
  	off_t offset = nth_packed_object_offset(pack, pos);
  	struct object_info oi = OBJECT_INFO_INIT;
  
 +	if (list->progress)
 +		display_progress(list->progress, ++list->progress_done);
 +
  	oi.typep = &type;
  	if (packed_object_info(the_repository, pack, offset, &oi) < 0)
  		die(_("unable to get type of object %s"), oid_to_hex(oid));
@@@ -641,66 -606,43 +641,66 @@@ static void add_missing_parents(struct 
  	}
  }
  
 -static void close_reachable(struct packed_oid_list *oids)
 +static void close_reachable(struct packed_oid_list *oids, int report_progress)
  {
 -	int i;
 +	int i, j;
  	struct commit *commit;
 +	struct progress *progress = NULL;
  
 +	if (report_progress)
 +		progress = start_delayed_progress(
 +			_("Loading known commits in commit graph"), j = 0);
  	for (i = 0; i < oids->nr; i++) {
 +		display_progress(progress, ++j);
  		commit = lookup_commit(the_repository, &oids->list[i]);
  		if (commit)
  			commit->object.flags |= UNINTERESTING;
  	}
 +	stop_progress(&progress);
  
  	/*
  	 * As this loop runs, oids->nr may grow, but not more
  	 * than the number of missing commits in the reachable
  	 * closure.
  	 */
 +	if (report_progress)
 +		progress = start_delayed_progress(
 +			_("Expanding reachable commits in commit graph"), j = 0);
  	for (i = 0; i < oids->nr; i++) {
 +		display_progress(progress, ++j);
  		commit = lookup_commit(the_repository, &oids->list[i]);
  
  		if (commit && !parse_commit(commit))
  			add_missing_parents(oids, commit);
  	}
 +	stop_progress(&progress);
  
 +	if (report_progress)
 +		progress = start_delayed_progress(
 +			_("Clearing commit marks in commit graph"), j = 0);
  	for (i = 0; i < oids->nr; i++) {
 +		display_progress(progress, ++j);
  		commit = lookup_commit(the_repository, &oids->list[i]);
  
  		if (commit)
  			commit->object.flags &= ~UNINTERESTING;
  	}
 +	stop_progress(&progress);
  }
  
 -static void compute_generation_numbers(struct packed_commit_list* commits)
 +static void compute_generation_numbers(struct packed_commit_list* commits,
 +				       int report_progress)
  {
  	int i;
  	struct commit_list *list = NULL;
 +	struct progress *progress = NULL;
  
 +	if (report_progress)
 +		progress = start_progress(
 +			_("Computing commit graph generation numbers"),
 +			commits->nr);
  	for (i = 0; i < commits->nr; i++) {
 +		display_progress(progress, i + 1);
  		if (commits->list[i]->generation != GENERATION_NUMBER_INFINITY &&
  		    commits->list[i]->generation != GENERATION_NUMBER_ZERO)
  			continue;
@@@ -732,7 -674,6 +732,7 @@@
  			}
  		}
  	}
 +	stop_progress(&progress);
  }
  
  static int add_ref_to_list(const char *refname,
@@@ -745,21 -686,19 +745,21 @@@
  	return 0;
  }
  
 -void write_commit_graph_reachable(const char *obj_dir, int append)
 +void write_commit_graph_reachable(const char *obj_dir, int append,
 +				  int report_progress)
  {
 -	struct string_list list;
 +	struct string_list list = STRING_LIST_INIT_DUP;
  
 -	string_list_init(&list, 1);
  	for_each_ref(add_ref_to_list, &list);
 -	write_commit_graph(obj_dir, NULL, &list, append);
 +	write_commit_graph(obj_dir, NULL, &list, append, report_progress);
 +
 +	string_list_clear(&list, 0);
  }
  
  void write_commit_graph(const char *obj_dir,
  			struct string_list *pack_indexes,
  			struct string_list *commit_hex,
 -			int append)
 +			int append, int report_progress)
  {
  	struct packed_oid_list oids;
  	struct packed_commit_list commits;
@@@ -772,15 -711,10 +772,16 @@@
  	int num_chunks;
  	int num_extra_edges;
  	struct commit_list *parent;
 +	struct progress *progress = NULL;
+ 	const unsigned hashsz = the_hash_algo->rawsz;
  
 +	if (!commit_graph_compatible(the_repository))
 +		return;
 +
  	oids.nr = 0;
 -	oids.alloc = approximate_object_count() / 4;
 +	oids.alloc = approximate_object_count() / 32;
 +	oids.progress = NULL;
 +	oids.progress_done = 0;
  
  	if (append) {
  		prepare_commit_graph_one(the_repository, obj_dir);
@@@ -807,11 -741,6 +808,11 @@@
  		int dirlen;
  		strbuf_addf(&packname, "%s/pack/", obj_dir);
  		dirlen = packname.len;
 +		if (report_progress) {
 +			oids.progress = start_delayed_progress(
 +				_("Finding commits for commit graph"), 0);
 +			oids.progress_done = 0;
 +		}
  		for (i = 0; i < pack_indexes->nr; i++) {
  			struct packed_git *p;
  			strbuf_setlen(&packname, dirlen);
@@@ -823,23 -752,16 +824,23 @@@
  				die(_("error opening index for %s"), packname.buf);
  			for_each_object_in_pack(p, add_packed_commits, &oids, 0);
  			close_pack(p);
 +			free(p);
  		}
 +		stop_progress(&oids.progress);
  		strbuf_release(&packname);
  	}
  
  	if (commit_hex) {
 +		if (report_progress)
 +			progress = start_delayed_progress(
 +				_("Finding commits for commit graph"),
 +				commit_hex->nr);
  		for (i = 0; i < commit_hex->nr; i++) {
  			const char *end;
  			struct object_id oid;
  			struct commit *result;
  
 +			display_progress(progress, i + 1);
  			if (commit_hex->items[i].string &&
  			    parse_oid_hex(commit_hex->items[i].string, &oid, &end))
  				continue;
@@@ -852,18 -774,12 +853,18 @@@
  				oids.nr++;
  			}
  		}
 +		stop_progress(&progress);
  	}
  
 -	if (!pack_indexes && !commit_hex)
 +	if (!pack_indexes && !commit_hex) {
 +		if (report_progress)
 +			oids.progress = start_delayed_progress(
 +				_("Finding commits for commit graph"), 0);
  		for_each_packed_object(add_packed_commits, &oids, 0);
 +		stop_progress(&oids.progress);
 +	}
  
 -	close_reachable(&oids);
 +	close_reachable(&oids, report_progress);
  
  	QSORT(oids.list, oids.nr, commit_compare);
  
@@@ -873,7 -789,7 +874,7 @@@
  			count_distinct++;
  	}
  
 -	if (count_distinct >= GRAPH_PARENT_MISSING)
 +	if (count_distinct >= GRAPH_EDGE_LAST_MASK)
  		die(_("the commit graph format cannot write %d commits"), count_distinct);
  
  	commits.nr = 0;
@@@ -900,17 -816,15 +901,17 @@@
  	}
  	num_chunks = num_extra_edges ? 4 : 3;
  
 -	if (commits.nr >= GRAPH_PARENT_MISSING)
 +	if (commits.nr >= GRAPH_EDGE_LAST_MASK)
  		die(_("too many commits to write graph"));
  
 -	compute_generation_numbers(&commits);
 +	compute_generation_numbers(&commits, report_progress);
  
  	graph_name = get_commit_graph_filename(obj_dir);
 -	if (safe_create_leading_directories(graph_name))
 +	if (safe_create_leading_directories(graph_name)) {
 +		UNLEAK(graph_name);
  		die_errno(_("unable to create leading directories of %s"),
  			  graph_name);
 +	}
  
  	hold_lock_file_for_update(&lk, graph_name, LOCK_DIE_ON_ERROR);
  	f = hashfd(lk.tempfile->fd, lk.tempfile->filename.buf);
@@@ -918,7 -832,7 +919,7 @@@
  	hashwrite_be32(f, GRAPH_SIGNATURE);
  
  	hashwrite_u8(f, GRAPH_VERSION);
- 	hashwrite_u8(f, GRAPH_OID_VERSION);
+ 	hashwrite_u8(f, oid_version());
  	hashwrite_u8(f, num_chunks);
  	hashwrite_u8(f, 0); /* unused padding byte */
  
@@@ -933,8 -847,8 +934,8 @@@
  
  	chunk_offsets[0] = 8 + (num_chunks + 1) * GRAPH_CHUNKLOOKUP_WIDTH;
  	chunk_offsets[1] = chunk_offsets[0] + GRAPH_FANOUT_SIZE;
- 	chunk_offsets[2] = chunk_offsets[1] + GRAPH_OID_LEN * commits.nr;
- 	chunk_offsets[3] = chunk_offsets[2] + (GRAPH_OID_LEN + 16) * commits.nr;
+ 	chunk_offsets[2] = chunk_offsets[1] + hashsz * commits.nr;
+ 	chunk_offsets[3] = chunk_offsets[2] + (hashsz + 16) * commits.nr;
  	chunk_offsets[4] = chunk_offsets[3] + 4 * num_extra_edges;
  
  	for (i = 0; i <= num_chunks; i++) {
@@@ -947,17 -861,17 +948,17 @@@
  	}
  
  	write_graph_chunk_fanout(f, commits.list, commits.nr);
- 	write_graph_chunk_oids(f, GRAPH_OID_LEN, commits.list, commits.nr);
- 	write_graph_chunk_data(f, GRAPH_OID_LEN, commits.list, commits.nr);
+ 	write_graph_chunk_oids(f, hashsz, commits.list, commits.nr);
+ 	write_graph_chunk_data(f, hashsz, commits.list, commits.nr);
  	write_graph_chunk_large_edges(f, commits.list, commits.nr);
  
 -	close_commit_graph();
 +	close_commit_graph(the_repository);
  	finalize_hashfile(f, NULL, CSUM_HASH_IN_STREAM | CSUM_FSYNC);
  	commit_lock_file(&lk);
  
 +	free(graph_name);
 +	free(commits.list);
  	free(oids.list);
 -	oids.alloc = 0;
 -	oids.nr = 0;
  }
  
  #define VERIFY_COMMIT_GRAPH_ERROR_HASH 2
@@@ -984,7 -898,6 +985,7 @@@ int verify_commit_graph(struct reposito
  	int generation_zero = 0;
  	struct hashfile *f;
  	int devnull;
 +	struct progress *progress = NULL;
  
  	if (!g) {
  		graph_report("no commit-graph file loaded");
@@@ -1052,14 -965,11 +1053,14 @@@
  	if (verify_commit_graph_error & ~VERIFY_COMMIT_GRAPH_ERROR_HASH)
  		return verify_commit_graph_error;
  
 +	progress = start_progress(_("Verifying commits in commit graph"),
 +				  g->num_commits);
  	for (i = 0; i < g->num_commits; i++) {
  		struct commit *graph_commit, *odb_commit;
  		struct commit_list *graph_parents, *odb_parents;
  		uint32_t max_generation = 0;
  
 +		display_progress(progress, i + 1);
  		hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);
  
  		graph_commit = lookup_commit(r, &cur_oid);
@@@ -1136,7 -1046,6 +1137,7 @@@
  				     graph_commit->date,
  				     odb_commit->date);
  	}
 +	stop_progress(&progress);
  
  	return verify_commit_graph_error;
  }
diff --combined sha1-file.c
index 386b96e1d7,66ba3dadb9..10f9e9936a
--- a/sha1-file.c
+++ b/sha1-file.c
@@@ -40,10 -40,20 +40,20 @@@
  #define EMPTY_TREE_SHA1_BIN_LITERAL \
  	 "\x4b\x82\x5d\xc6\x42\xcb\x6e\xb9\xa0\x60" \
  	 "\xe5\x4b\xf8\xd6\x92\x88\xfb\xee\x49\x04"
+ #define EMPTY_TREE_SHA256_BIN_LITERAL \
+ 	"\x6e\xf1\x9b\x41\x22\x5c\x53\x69\xf1\xc1" \
+ 	"\x04\xd4\x5d\x8d\x85\xef\xa9\xb0\x57\xb5" \
+ 	"\x3b\x14\xb4\xb9\xb9\x39\xdd\x74\xde\xcc" \
+ 	"\x53\x21"
  
  #define EMPTY_BLOB_SHA1_BIN_LITERAL \
  	"\xe6\x9d\xe2\x9b\xb2\xd1\xd6\x43\x4b\x8b" \
  	"\x29\xae\x77\x5a\xd8\xc2\xe4\x8c\x53\x91"
+ #define EMPTY_BLOB_SHA256_BIN_LITERAL \
+ 	"\x47\x3a\x0f\x4c\x3b\xe8\xa9\x36\x81\xa2" \
+ 	"\x67\xe3\xb1\xe9\xa7\xdc\xda\x11\x85\x43" \
+ 	"\x6f\xe1\x41\xf7\x74\x91\x20\xa3\x03\x72" \
+ 	"\x18\x13"
  
  const unsigned char null_sha1[GIT_MAX_RAWSZ];
  const struct object_id null_oid;
@@@ -53,6 -63,12 +63,12 @@@ static const struct object_id empty_tre
  static const struct object_id empty_blob_oid = {
  	EMPTY_BLOB_SHA1_BIN_LITERAL
  };
+ static const struct object_id empty_tree_oid_sha256 = {
+ 	EMPTY_TREE_SHA256_BIN_LITERAL
+ };
+ static const struct object_id empty_blob_oid_sha256 = {
+ 	EMPTY_BLOB_SHA256_BIN_LITERAL
+ };
  
  static void git_hash_sha1_init(git_hash_ctx *ctx)
  {
@@@ -69,6 -85,22 +85,22 @@@ static void git_hash_sha1_final(unsigne
  	git_SHA1_Final(hash, &ctx->sha1);
  }
  
+ 
+ static void git_hash_sha256_init(git_hash_ctx *ctx)
+ {
+ 	git_SHA256_Init(&ctx->sha256);
+ }
+ 
+ static void git_hash_sha256_update(git_hash_ctx *ctx, const void *data, size_t len)
+ {
+ 	git_SHA256_Update(&ctx->sha256, data, len);
+ }
+ 
+ static void git_hash_sha256_final(unsigned char *hash, git_hash_ctx *ctx)
+ {
+ 	git_SHA256_Final(hash, &ctx->sha256);
+ }
+ 
  static void git_hash_unknown_init(git_hash_ctx *ctx)
  {
  	BUG("trying to init unknown hash");
@@@ -90,6 -122,7 +122,7 @@@ const struct git_hash_algo hash_algos[G
  		0x00000000,
  		0,
  		0,
+ 		0,
  		git_hash_unknown_init,
  		git_hash_unknown_update,
  		git_hash_unknown_final,
@@@ -97,17 -130,31 +130,31 @@@
  		NULL,
  	},
  	{
- 		"sha-1",
+ 		"sha1",
  		/* "sha1", big-endian */
  		0x73686131,
  		GIT_SHA1_RAWSZ,
  		GIT_SHA1_HEXSZ,
+ 		GIT_SHA1_BLKSZ,
  		git_hash_sha1_init,
  		git_hash_sha1_update,
  		git_hash_sha1_final,
  		&empty_tree_oid,
  		&empty_blob_oid,
  	},
+ 	{
+ 		"sha256",
+ 		/* "s256", big-endian */
+ 		0x73323536,
+ 		GIT_SHA256_RAWSZ,
+ 		GIT_SHA256_HEXSZ,
+ 		GIT_SHA256_BLKSZ,
+ 		git_hash_sha256_init,
+ 		git_hash_sha256_update,
+ 		git_hash_sha256_final,
+ 		&empty_tree_oid_sha256,
+ 		&empty_blob_oid_sha256,
+ 	}
  };
  
  const char *empty_tree_oid_hex(void)
@@@ -122,6 -169,27 +169,27 @@@ const char *empty_blob_oid_hex(void
  	return oid_to_hex_r(buf, the_hash_algo->empty_blob);
  }
  
+ int hash_algo_by_name(const char *name)
+ {
+ 	int i;
+ 	if (!name)
+ 		return GIT_HASH_UNKNOWN;
+ 	for (i = 1; i < GIT_HASH_NALGOS; i++)
+ 		if (!strcmp(name, hash_algos[i].name))
+ 			return i;
+ 	return GIT_HASH_UNKNOWN;
+ }
+ 
+ int hash_algo_by_id(uint32_t format_id)
+ {
+ 	int i;
+ 	for (i = 1; i < GIT_HASH_NALGOS; i++)
+ 		if (format_id == hash_algos[i].format_id)
+ 			return i;
+ 	return GIT_HASH_UNKNOWN;
+ }
+ 
+ 
  /*
   * This is meant to hold a *small* number of objects that you would
   * want read_sha1_file() to be able to return, but yet you do not want
@@@ -346,21 -414,25 +414,21 @@@ static void fill_sha1_path(struct strbu
  	}
  }
  
 -void sha1_file_name(struct repository *r, struct strbuf *buf, const unsigned char *sha1)
 +static const char *odb_loose_path(struct object_directory *odb,
 +				  struct strbuf *buf,
 +				  const unsigned char *sha1)
  {
 -	strbuf_addstr(buf, r->objects->objectdir);
 +	strbuf_reset(buf);
 +	strbuf_addstr(buf, odb->path);
  	strbuf_addch(buf, '/');
  	fill_sha1_path(buf, sha1);
 +	return buf->buf;
  }
  
 -struct strbuf *alt_scratch_buf(struct alternate_object_database *alt)
 +const char *loose_object_path(struct repository *r, struct strbuf *buf,
 +			      const unsigned char *sha1)
  {
 -	strbuf_setlen(&alt->scratch, alt->base_len);
 -	return &alt->scratch;
 -}
 -
 -static const char *alt_sha1_path(struct alternate_object_database *alt,
 -				 const unsigned char *sha1)
 -{
 -	struct strbuf *buf = alt_scratch_buf(alt);
 -	fill_sha1_path(buf, sha1);
 -	return buf->buf;
 +	return odb_loose_path(r->objects->odb, buf, sha1);
  }
  
  /*
@@@ -370,7 -442,7 +438,7 @@@ static int alt_odb_usable(struct raw_ob
  			  struct strbuf *path,
  			  const char *normalized_objdir)
  {
 -	struct alternate_object_database *alt;
 +	struct object_directory *odb;
  
  	/* Detect cases where alternate disappeared */
  	if (!is_directory(path->buf)) {
@@@ -384,8 -456,8 +452,8 @@@
  	 * Prevent the common mistake of listing the same
  	 * thing twice, or object directory itself.
  	 */
 -	for (alt = o->alt_odb_list; alt; alt = alt->next) {
 -		if (!fspathcmp(path->buf, alt->path))
 +	for (odb = o->odb; odb; odb = odb->next) {
 +		if (!fspathcmp(path->buf, odb->path))
  			return 0;
  	}
  	if (!fspathcmp(path->buf, normalized_objdir))
@@@ -398,7 -470,7 +466,7 @@@
   * Prepare alternate object database registry.
   *
   * The variable alt_odb_list points at the list of struct
 - * alternate_object_database.  The elements on this list come from
 + * object_directory.  The elements on this list come from
   * non-empty elements from colon separated ALTERNATE_DB_ENVIRONMENT
   * environment variable, and $GIT_OBJECT_DIRECTORY/info/alternates,
   * whose contents is similar to that environment variable but can be
@@@ -415,7 -487,7 +483,7 @@@ static void read_info_alternates(struc
  static int link_alt_odb_entry(struct repository *r, const char *entry,
  	const char *relative_base, int depth, const char *normalized_objdir)
  {
 -	struct alternate_object_database *ent;
 +	struct object_directory *ent;
  	struct strbuf pathbuf = STRBUF_INIT;
  
  	if (!is_absolute_path(entry) && relative_base) {
@@@ -443,12 -515,11 +511,12 @@@
  		return -1;
  	}
  
 -	ent = alloc_alt_odb(pathbuf.buf);
 +	ent = xcalloc(1, sizeof(*ent));
 +	ent->path = xstrdup(pathbuf.buf);
  
  	/* add the alternate entry */
 -	*r->objects->alt_odb_tail = ent;
 -	r->objects->alt_odb_tail = &(ent->next);
 +	*r->objects->odb_tail = ent;
 +	r->objects->odb_tail = &(ent->next);
  	ent->next = NULL;
  
  	/* recursively add alternates */
@@@ -502,7 -573,7 +570,7 @@@ static void link_alt_odb_entries(struc
  		return;
  	}
  
 -	strbuf_add_absolute_path(&objdirbuf, r->objects->objectdir);
 +	strbuf_add_absolute_path(&objdirbuf, r->objects->odb->path);
  	if (strbuf_normalize_path(&objdirbuf) < 0)
  		die(_("unable to normalize object directory: %s"),
  		    objdirbuf.buf);
@@@ -537,6 -608,18 +605,6 @@@ static void read_info_alternates(struc
  	free(path);
  }
  
 -struct alternate_object_database *alloc_alt_odb(const char *dir)
 -{
 -	struct alternate_object_database *ent;
 -
 -	FLEX_ALLOC_STR(ent, path, dir);
 -	strbuf_init(&ent->scratch, 0);
 -	strbuf_addf(&ent->scratch, "%s/", dir);
 -	ent->base_len = ent->scratch.len;
 -
 -	return ent;
 -}
 -
  void add_to_alternates_file(const char *reference)
  {
  	struct lock_file lock = LOCK_INIT;
@@@ -573,7 -656,7 +641,7 @@@
  		fprintf_or_die(out, "%s\n", reference);
  		if (commit_lock_file(&lock))
  			die_errno(_("unable to move new alternates file into place"));
 -		if (the_repository->objects->alt_odb_tail)
 +		if (the_repository->objects->loaded_alternates)
  			link_alt_odb_entries(the_repository, reference,
  					     '\n', NULL, 0);
  	}
@@@ -669,11 -752,11 +737,11 @@@ out
  
  int foreach_alt_odb(alt_odb_fn fn, void *cb)
  {
 -	struct alternate_object_database *ent;
 +	struct object_directory *ent;
  	int r = 0;
  
  	prepare_alt_odb(the_repository);
 -	for (ent = the_repository->objects->alt_odb_list; ent; ent = ent->next) {
 +	for (ent = the_repository->objects->odb->next; ent; ent = ent->next) {
  		r = fn(ent, cb);
  		if (r)
  			break;
@@@ -683,13 -766,13 +751,13 @@@
  
  void prepare_alt_odb(struct repository *r)
  {
 -	if (r->objects->alt_odb_tail)
 +	if (r->objects->loaded_alternates)
  		return;
  
 -	r->objects->alt_odb_tail = &r->objects->alt_odb_list;
  	link_alt_odb_entries(r, r->objects->alternate_db, PATH_SEP, NULL, 0);
  
 -	read_info_alternates(r, r->objects->objectdir, 0);
 +	read_info_alternates(r, r->objects->odb->path, 0);
 +	r->objects->loaded_alternates = 1;
  }
  
  /* Returns 1 if we have successfully freshened the file, 0 otherwise. */
@@@ -716,27 -799,23 +784,27 @@@ int check_and_freshen_file(const char *
  	return 1;
  }
  
 -static int check_and_freshen_local(const struct object_id *oid, int freshen)
 +static int check_and_freshen_odb(struct object_directory *odb,
 +				 const struct object_id *oid,
 +				 int freshen)
  {
 -	static struct strbuf buf = STRBUF_INIT;
 -
 -	strbuf_reset(&buf);
 -	sha1_file_name(the_repository, &buf, oid->hash);
 +	static struct strbuf path = STRBUF_INIT;
 +	odb_loose_path(odb, &path, oid->hash);
 +	return check_and_freshen_file(path.buf, freshen);
 +}
  
 -	return check_and_freshen_file(buf.buf, freshen);
 +static int check_and_freshen_local(const struct object_id *oid, int freshen)
 +{
 +	return check_and_freshen_odb(the_repository->objects->odb, oid, freshen);
  }
  
  static int check_and_freshen_nonlocal(const struct object_id *oid, int freshen)
  {
 -	struct alternate_object_database *alt;
 +	struct object_directory *odb;
 +
  	prepare_alt_odb(the_repository);
 -	for (alt = the_repository->objects->alt_odb_list; alt; alt = alt->next) {
 -		const char *path = alt_sha1_path(alt, oid->hash);
 -		if (check_and_freshen_file(path, freshen))
 +	for (odb = the_repository->objects->odb->next; odb; odb = odb->next) {
 +		if (check_and_freshen_odb(odb, oid, freshen))
  			return 1;
  	}
  	return 0;
@@@ -822,7 -901,7 +890,7 @@@ int check_object_signature(const struc
  		return -1;
  
  	/* Generate the header */
 -	hdrlen = xsnprintf(hdr, sizeof(hdr), "%s %lu", type_name(obj_type), size) + 1;
 +	hdrlen = xsnprintf(hdr, sizeof(hdr), "%s %"PRIuMAX , type_name(obj_type), (uintmax_t)size) + 1;
  
  	/* Sha1.. */
  	the_hash_algo->init_fn(&c);
@@@ -877,17 -956,25 +945,17 @@@ int git_open_cloexec(const char *name, 
   *
   * The "path" out-parameter will give the path of the object we found (if any).
   * Note that it may point to static storage and is only valid until another
 - * call to sha1_file_name(), etc.
 + * call to stat_sha1_file().
   */
  static int stat_sha1_file(struct repository *r, const unsigned char *sha1,
  			  struct stat *st, const char **path)
  {
 -	struct alternate_object_database *alt;
 +	struct object_directory *odb;
  	static struct strbuf buf = STRBUF_INIT;
  
 -	strbuf_reset(&buf);
 -	sha1_file_name(r, &buf, sha1);
 -	*path = buf.buf;
 -
 -	if (!lstat(*path, st))
 -		return 0;
 -
  	prepare_alt_odb(r);
 -	errno = ENOENT;
 -	for (alt = r->objects->alt_odb_list; alt; alt = alt->next) {
 -		*path = alt_sha1_path(alt, sha1);
 +	for (odb = r->objects->odb; odb; odb = odb->next) {
 +		*path = odb_loose_path(odb, &buf, sha1);
  		if (!lstat(*path, st))
  			return 0;
  	}
@@@ -903,17 -990,25 +971,17 @@@ static int open_sha1_file(struct reposi
  			  const unsigned char *sha1, const char **path)
  {
  	int fd;
 -	struct alternate_object_database *alt;
 -	int most_interesting_errno;
 +	struct object_directory *odb;
 +	int most_interesting_errno = ENOENT;
  	static struct strbuf buf = STRBUF_INIT;
  
 -	strbuf_reset(&buf);
 -	sha1_file_name(r, &buf, sha1);
 -	*path = buf.buf;
 -
 -	fd = git_open(*path);
 -	if (fd >= 0)
 -		return fd;
 -	most_interesting_errno = errno;
 -
  	prepare_alt_odb(r);
 -	for (alt = r->objects->alt_odb_list; alt; alt = alt->next) {
 -		*path = alt_sha1_path(alt, sha1);
 +	for (odb = r->objects->odb; odb; odb = odb->next) {
 +		*path = odb_loose_path(odb, &buf, sha1);
  		fd = git_open(*path);
  		if (fd >= 0)
  			return fd;
 +
  		if (most_interesting_errno == ENOENT)
  			most_interesting_errno = errno;
  	}
@@@ -921,22 -1016,6 +989,22 @@@
  	return -1;
  }
  
 +static int quick_has_loose(struct repository *r,
 +			   const unsigned char *sha1)
 +{
 +	struct object_id oid;
 +	struct object_directory *odb;
 +
 +	hashcpy(oid.hash, sha1);
 +
 +	prepare_alt_odb(r);
 +	for (odb = r->objects->odb; odb; odb = odb->next) {
 +		if (oid_array_lookup(odb_loose_cache(odb, &oid), &oid) >= 0)
 +			return 1;
 +	}
 +	return 0;
 +}
 +
  /*
   * Map the loose object at "path" if it is not NULL, or the path found by
   * searching for a loose object named "sha1".
@@@ -960,7 -1039,6 +1028,7 @@@ static void *map_sha1_file_1(struct rep
  			if (!*size) {
  				/* mmap() is forbidden on empty files */
  				error(_("object file %s is empty"), path);
 +				close(fd);
  				return NULL;
  			}
  			map = xmmap(NULL, *size, PROT_READ, MAP_PRIVATE, fd, 0);
@@@ -1188,8 -1266,6 +1256,8 @@@ static int sha1_loose_object_info(struc
  	if (!oi->typep && !oi->type_name && !oi->sizep && !oi->contentp) {
  		const char *path;
  		struct stat st;
 +		if (!oi->disk_sizep && (flags & OBJECT_INFO_QUICK))
 +			return quick_has_loose(r, sha1) ? 0 : -1;
  		if (stat_sha1_file(r, sha1, &st, &path) < 0)
  			return -1;
  		if (oi->disk_sizep)
@@@ -1484,7 -1560,7 +1552,7 @@@ static void write_object_file_prepare(c
  	git_hash_ctx c;
  
  	/* Generate the header */
 -	*hdrlen = xsnprintf(hdr, *hdrlen, "%s %lu", type, len)+1;
 +	*hdrlen = xsnprintf(hdr, *hdrlen, "%s %"PRIuMAX , type, (uintmax_t)len)+1;
  
  	/* Sha1.. */
  	the_hash_algo->init_fn(&c);
@@@ -1618,7 -1694,8 +1686,7 @@@ static int write_loose_object(const str
  	static struct strbuf tmp_file = STRBUF_INIT;
  	static struct strbuf filename = STRBUF_INIT;
  
 -	strbuf_reset(&filename);
 -	sha1_file_name(the_repository, &filename, oid->hash);
 +	loose_object_path(the_repository, &filename, oid->hash);
  
  	fd = create_tmpfile(&tmp_file, filename.buf);
  	if (fd < 0) {
@@@ -1749,7 -1826,7 +1817,7 @@@ int force_object_loose(const struct obj
  	buf = read_object(oid->hash, &type, &len);
  	if (!buf)
  		return error(_("cannot read sha1_file for %s"), oid_to_hex(oid));
 -	hdrlen = xsnprintf(hdr, sizeof(hdr), "%s %lu", type_name(type), len) + 1;
 +	hdrlen = xsnprintf(hdr, sizeof(hdr), "%s %"PRIuMAX , type_name(type), (uintmax_t)len) + 1;
  	ret = write_loose_object(oid, hdr, hdrlen, buf, len, mtime);
  	free(buf);
  
@@@ -1804,8 -1881,7 +1872,8 @@@ static void check_tag(const void *buf, 
  		die(_("corrupt tag"));
  }
  
 -static int index_mem(struct object_id *oid, void *buf, size_t size,
 +static int index_mem(struct index_state *istate,
 +		     struct object_id *oid, void *buf, size_t size,
  		     enum object_type type,
  		     const char *path, unsigned flags)
  {
@@@ -1820,7 -1896,7 +1888,7 @@@
  	 */
  	if ((type == OBJ_BLOB) && path) {
  		struct strbuf nbuf = STRBUF_INIT;
 -		if (convert_to_git(&the_index, path, buf, size, &nbuf,
 +		if (convert_to_git(istate, path, buf, size, &nbuf,
  				   get_conv_flags(flags))) {
  			buf = strbuf_detach(&nbuf, &size);
  			re_allocated = 1;
@@@ -1844,20 -1920,17 +1912,20 @@@
  	return ret;
  }
  
 -static int index_stream_convert_blob(struct object_id *oid, int fd,
 -				     const char *path, unsigned flags)
 +static int index_stream_convert_blob(struct index_state *istate,
 +				     struct object_id *oid,
 +				     int fd,
 +				     const char *path,
 +				     unsigned flags)
  {
  	int ret;
  	const int write_object = flags & HASH_WRITE_OBJECT;
  	struct strbuf sbuf = STRBUF_INIT;
  
  	assert(path);
 -	assert(would_convert_to_git_filter_fd(&the_index, path));
 +	assert(would_convert_to_git_filter_fd(istate, path));
  
 -	convert_to_git_filter_fd(&the_index, path, fd, &sbuf,
 +	convert_to_git_filter_fd(istate, path, fd, &sbuf,
  				 get_conv_flags(flags));
  
  	if (write_object)
@@@ -1870,15 -1943,14 +1938,15 @@@
  	return ret;
  }
  
 -static int index_pipe(struct object_id *oid, int fd, enum object_type type,
 +static int index_pipe(struct index_state *istate, struct object_id *oid,
 +		      int fd, enum object_type type,
  		      const char *path, unsigned flags)
  {
  	struct strbuf sbuf = STRBUF_INIT;
  	int ret;
  
  	if (strbuf_read(&sbuf, fd, 4096) >= 0)
 -		ret = index_mem(oid, sbuf.buf, sbuf.len, type, path, flags);
 +		ret = index_mem(istate, oid, sbuf.buf, sbuf.len, type, path, flags);
  	else
  		ret = -1;
  	strbuf_release(&sbuf);
@@@ -1887,15 -1959,14 +1955,15 @@@
  
  #define SMALL_FILE_SIZE (32*1024)
  
 -static int index_core(struct object_id *oid, int fd, size_t size,
 +static int index_core(struct index_state *istate,
 +		      struct object_id *oid, int fd, size_t size,
  		      enum object_type type, const char *path,
  		      unsigned flags)
  {
  	int ret;
  
  	if (!size) {
 -		ret = index_mem(oid, "", size, type, path, flags);
 +		ret = index_mem(istate, oid, "", size, type, path, flags);
  	} else if (size <= SMALL_FILE_SIZE) {
  		char *buf = xmalloc(size);
  		ssize_t read_result = read_in_full(fd, buf, size);
@@@ -1906,11 -1977,11 +1974,11 @@@
  			ret = error(_("short read while indexing %s"),
  				    path ? path : "<unknown>");
  		else
 -			ret = index_mem(oid, buf, size, type, path, flags);
 +			ret = index_mem(istate, oid, buf, size, type, path, flags);
  		free(buf);
  	} else {
  		void *buf = xmmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);
 -		ret = index_mem(oid, buf, size, type, path, flags);
 +		ret = index_mem(istate, oid, buf, size, type, path, flags);
  		munmap(buf, size);
  	}
  	return ret;
@@@ -1938,8 -2009,7 +2006,8 @@@ static int index_stream(struct object_i
  	return index_bulk_checkin(oid, fd, size, type, path, flags);
  }
  
 -int index_fd(struct object_id *oid, int fd, struct stat *st,
 +int index_fd(struct index_state *istate, struct object_id *oid,
 +	     int fd, struct stat *st,
  	     enum object_type type, const char *path, unsigned flags)
  {
  	int ret;
@@@ -1948,14 -2018,14 +2016,14 @@@
  	 * Call xsize_t() only when needed to avoid potentially unnecessary
  	 * die() for large files.
  	 */
 -	if (type == OBJ_BLOB && path && would_convert_to_git_filter_fd(&the_index, path))
 -		ret = index_stream_convert_blob(oid, fd, path, flags);
 +	if (type == OBJ_BLOB && path && would_convert_to_git_filter_fd(istate, path))
 +		ret = index_stream_convert_blob(istate, oid, fd, path, flags);
  	else if (!S_ISREG(st->st_mode))
 -		ret = index_pipe(oid, fd, type, path, flags);
 +		ret = index_pipe(istate, oid, fd, type, path, flags);
  	else if (st->st_size <= big_file_threshold || type != OBJ_BLOB ||
 -		 (path && would_convert_to_git(&the_index, path)))
 -		ret = index_core(oid, fd, xsize_t(st->st_size), type, path,
 -				 flags);
 +		 (path && would_convert_to_git(istate, path)))
 +		ret = index_core(istate, oid, fd, xsize_t(st->st_size),
 +				 type, path, flags);
  	else
  		ret = index_stream(oid, fd, xsize_t(st->st_size), type, path,
  				   flags);
@@@ -1963,8 -2033,7 +2031,8 @@@
  	return ret;
  }
  
 -int index_path(struct object_id *oid, const char *path, struct stat *st, unsigned flags)
 +int index_path(struct index_state *istate, struct object_id *oid,
 +	       const char *path, struct stat *st, unsigned flags)
  {
  	int fd;
  	struct strbuf sb = STRBUF_INIT;
@@@ -1975,7 -2044,7 +2043,7 @@@
  		fd = open(path, O_RDONLY);
  		if (fd < 0)
  			return error_errno("open(\"%s\")", path);
 -		if (index_fd(oid, fd, st, OBJ_BLOB, path, flags) < 0)
 +		if (index_fd(istate, oid, fd, st, OBJ_BLOB, path, flags) < 0)
  			return error(_("%s: failed to insert into database"),
  				     path);
  		break;
@@@ -2125,63 -2194,43 +2193,63 @@@ int for_each_loose_file_in_objdir(cons
  	return r;
  }
  
 -struct loose_alt_odb_data {
 -	each_loose_object_fn *cb;
 -	void *data;
 -};
 +int for_each_loose_object(each_loose_object_fn cb, void *data,
 +			  enum for_each_object_flags flags)
 +{
 +	struct object_directory *odb;
 +
 +	prepare_alt_odb(the_repository);
 +	for (odb = the_repository->objects->odb; odb; odb = odb->next) {
 +		int r = for_each_loose_file_in_objdir(odb->path, cb, NULL,
 +						      NULL, data);
 +		if (r)
 +			return r;
 +
 +		if (flags & FOR_EACH_OBJECT_LOCAL_ONLY)
 +			break;
 +	}
 +
 +	return 0;
 +}
  
 -static int loose_from_alt_odb(struct alternate_object_database *alt,
 -			      void *vdata)
 +static int append_loose_object(const struct object_id *oid, const char *path,
 +			       void *data)
  {
 -	struct loose_alt_odb_data *data = vdata;
 +	oid_array_append(data, oid);
 +	return 0;
 +}
 +
 +struct oid_array *odb_loose_cache(struct object_directory *odb,
 +				  const struct object_id *oid)
 +{
 +	int subdir_nr = oid->hash[0];
  	struct strbuf buf = STRBUF_INIT;
 -	int r;
  
 -	strbuf_addstr(&buf, alt->path);
 -	r = for_each_loose_file_in_objdir_buf(&buf,
 -					      data->cb, NULL, NULL,
 -					      data->data);
 +	if (subdir_nr < 0 ||
 +	    subdir_nr >= ARRAY_SIZE(odb->loose_objects_subdir_seen))
 +		BUG("subdir_nr out of range");
 +
 +	if (odb->loose_objects_subdir_seen[subdir_nr])
 +		return &odb->loose_objects_cache[subdir_nr];
 +
 +	strbuf_addstr(&buf, odb->path);
 +	for_each_file_in_obj_subdir(subdir_nr, &buf,
 +				    append_loose_object,
 +				    NULL, NULL,
 +				    &odb->loose_objects_cache[subdir_nr]);
 +	odb->loose_objects_subdir_seen[subdir_nr] = 1;
  	strbuf_release(&buf);
 -	return r;
 +	return &odb->loose_objects_cache[subdir_nr];
  }
  
 -int for_each_loose_object(each_loose_object_fn cb, void *data,
 -			  enum for_each_object_flags flags)
 +void odb_clear_loose_cache(struct object_directory *odb)
  {
 -	struct loose_alt_odb_data alt;
 -	int r;
 -
 -	r = for_each_loose_file_in_objdir(get_object_directory(),
 -					  cb, NULL, NULL, data);
 -	if (r)
 -		return r;
 -
 -	if (flags & FOR_EACH_OBJECT_LOCAL_ONLY)
 -		return 0;
 +	int i;
  
 -	alt.cb = cb;
 -	alt.data = data;
 -	return foreach_alt_odb(loose_from_alt_odb, &alt);
 +	for (i = 0; i < ARRAY_SIZE(odb->loose_objects_cache); i++)
 +		oid_array_clear(&odb->loose_objects_cache[i]);
 +	memset(&odb->loose_objects_subdir_seen, 0,
 +	       sizeof(odb->loose_objects_subdir_seen));
  }
  
  static int check_stream_sha1(git_zstream *stream,
@@@ -2210,8 -2259,7 +2278,8 @@@
  	 * see the comment in unpack_sha1_rest for details.
  	 */
  	while (total_read <= size &&
 -	       (status == Z_OK || status == Z_BUF_ERROR)) {
 +	       (status == Z_OK ||
 +		(status == Z_BUF_ERROR && !stream->avail_out))) {
  		stream->next_out = buf;
  		stream->avail_out = sizeof(buf);
  		if (size - total_read < stream->avail_out)
diff --combined t/helper/test-tool.c
index bfb195b1a8,2a65193514..5b137874e1
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@@ -20,6 -20,7 +20,7 @@@ static struct test_cmd cmds[] = 
  	{ "example-decorate", cmd__example_decorate },
  	{ "genrandom", cmd__genrandom },
  	{ "hashmap", cmd__hashmap },
+ 	{ "hash-speed", cmd__hash_speed },
  	{ "index-version", cmd__index_version },
  	{ "json-writer", cmd__json_writer },
  	{ "lazy-init-name-hash", cmd__lazy_init_name_hash },
@@@ -42,11 -43,11 +43,12 @@@
  	{ "scrap-cache-tree", cmd__scrap_cache_tree },
  	{ "sha1", cmd__sha1 },
  	{ "sha1-array", cmd__sha1_array },
+ 	{ "sha256", cmd__sha256 },
  	{ "sigchain", cmd__sigchain },
  	{ "strcmp-offset", cmd__strcmp_offset },
  	{ "string-list", cmd__string_list },
  	{ "submodule-config", cmd__submodule_config },
 +	{ "submodule-nested-repo-config", cmd__submodule_nested_repo_config },
  	{ "subprocess", cmd__subprocess },
  	{ "urlmatch-normalization", cmd__urlmatch_normalization },
  	{ "wildmatch", cmd__wildmatch },
@@@ -56,23 -57,13 +58,23 @@@
  	{ "write-cache", cmd__write_cache },
  };
  
 +static NORETURN void die_usage(void)
 +{
 +	size_t i;
 +
 +	fprintf(stderr, "usage: test-tool <toolname> [args]\n");
 +	for (i = 0; i < ARRAY_SIZE(cmds); i++)
 +		fprintf(stderr, "  %s\n", cmds[i].name);
 +	exit(128);
 +}
 +
  int cmd_main(int argc, const char **argv)
  {
  	int i;
  
  	BUG_exit_code = 99;
  	if (argc < 2)
 -		die("I need a test name!");
 +		die_usage();
  
  	for (i = 0; i < ARRAY_SIZE(cmds); i++) {
  		if (!strcmp(cmds[i].name, argv[1])) {
@@@ -81,6 -72,5 +83,6 @@@
  			return cmds[i].fn(argc, argv);
  		}
  	}
 -	die("There is no test named '%s'", argv[1]);
 +	error("there is no tool named '%s'", argv[1]);
 +	die_usage();
  }
diff --combined t/helper/test-tool.h
index 042f12464b,2e66a8e47b..ca5c88edb2
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@@ -1,5 -1,5 +1,5 @@@
 -#ifndef __TEST_TOOL_H__
 -#define __TEST_TOOL_H__
 +#ifndef TEST_TOOL_H
 +#define TEST_TOOL_H
  
  #include "git-compat-util.h"
  
@@@ -16,6 -16,7 +16,7 @@@ int cmd__dump_untracked_cache(int argc
  int cmd__example_decorate(int argc, const char **argv);
  int cmd__genrandom(int argc, const char **argv);
  int cmd__hashmap(int argc, const char **argv);
+ int cmd__hash_speed(int argc, const char **argv);
  int cmd__index_version(int argc, const char **argv);
  int cmd__json_writer(int argc, const char **argv);
  int cmd__lazy_init_name_hash(int argc, const char **argv);
@@@ -38,11 -39,11 +39,12 @@@ int cmd__run_command(int argc, const ch
  int cmd__scrap_cache_tree(int argc, const char **argv);
  int cmd__sha1(int argc, const char **argv);
  int cmd__sha1_array(int argc, const char **argv);
+ int cmd__sha256(int argc, const char **argv);
  int cmd__sigchain(int argc, const char **argv);
  int cmd__strcmp_offset(int argc, const char **argv);
  int cmd__string_list(int argc, const char **argv);
  int cmd__submodule_config(int argc, const char **argv);
 +int cmd__submodule_nested_repo_config(int argc, const char **argv);
  int cmd__subprocess(int argc, const char **argv);
  int cmd__urlmatch_normalization(int argc, const char **argv);
  int cmd__wildmatch(int argc, const char **argv);
@@@ -51,4 -52,6 +53,6 @@@ int cmd__windows_named_pipe(int argc, c
  #endif
  int cmd__write_cache(int argc, const char **argv);
  
+ int cmd_hash_impl(int ac, const char **av, int algo);
+ 
  #endif