Merge pull request #1805 from libgit2/threading-packed-load

Thread safety for the refdb_fs

13 files changed, 1102 insertions, 536 deletions

diff --git a/src/cc-compat.h b/src/cc-compat.h
index a5e4ce17e..37f1ea81e 100644
--- a/src/cc-compat.h
+++ b/src/cc-compat.h
@@ -54,8 +54,12 @@
 
 #if defined (_MSC_VER)
 	typedef unsigned char bool;
-#	define true 1
-#	define false 0
+#	ifndef true
+#		define true 1
+#	endif
+#	ifndef false
+#		define false 0
+#	endif
 #else
 #	include <stdbool.h>
 #endif
diff --git a/src/diff_tform.c b/src/diff_tform.c
index ba35d3c14..6b8cf446e 100644
--- a/src/diff_tform.c
+++ b/src/diff_tform.c
@@ -859,9 +859,9 @@ find_best_matches:
 				}
 
 				/* write new mapping */
-				tgt2src[t].idx = s;
+				tgt2src[t].idx = (uint32_t)s;
 				tgt2src[t].similarity = (uint32_t)similarity;
-				src2tgt[s].idx = t;
+				src2tgt[s].idx = (uint32_t)t;
 				src2tgt[s].similarity = (uint32_t)similarity;
 			}
 
@@ -869,7 +869,7 @@ find_best_matches:
 			if (tgt2src_copy != NULL &&
 				tgt2src_copy[t].similarity < (uint32_t)similarity)
 			{
-				tgt2src_copy[t].idx = s;
+				tgt2src_copy[t].idx = (uint32_t)s;
 				tgt2src_copy[t].similarity = (uint32_t)similarity;
 			}
 
diff --git a/src/global.c b/src/global.c
index a06d0c81f..b504e5e0a 100644
--- a/src/global.c
+++ b/src/global.c
@@ -71,18 +71,22 @@ int git_threads_init(void)
 
 	GIT_MEMORY_BARRIER;
 
+	win32_pthread_initialize();
+
 	return error;
 }
 
 void git_threads_shutdown(void)
 {
+	/* Shut down any subsystems that have global state */
+	win32_pthread_shutdown();
+	git_futils_dirs_free();
+	git_hash_global_shutdown();
+
 	TlsFree(_tls_index);
 	_tls_init = 0;
-	git_mutex_free(&git__mwindow_mutex);
 
-	/* Shut down any subsystems that have global state */
-	git_hash_global_shutdown();
-	git_futils_dirs_free();
+	git_mutex_free(&git__mwindow_mutex);
 }
 
 git_global_st *git__global_state(void)
diff --git a/src/hash/hash_win32.c b/src/hash/hash_win32.c
index 362712e9a..095ceb359 100644
--- a/src/hash/hash_win32.c
+++ b/src/hash/hash_win32.c
@@ -28,7 +28,8 @@ GIT_INLINE(int) hash_cng_prov_init(void)
 		return -1;
 
 	/* Load bcrypt.dll explicitly from the system directory */
-	if ((dll_path_len = GetSystemDirectory(dll_path, MAX_PATH)) == 0 || dll_path_len > MAX_PATH ||
+	if ((dll_path_len = GetSystemDirectory(dll_path, MAX_PATH)) == 0 ||
+		dll_path_len > MAX_PATH ||
 		StringCchCat(dll_path, MAX_PATH, "\\") < 0 ||
 		StringCchCat(dll_path, MAX_PATH, GIT_HASH_CNG_DLL_NAME) < 0 ||
 		(hash_prov.prov.cng.dll = LoadLibrary(dll_path)) == NULL)
diff --git a/src/refdb_fs.c b/src/refdb_fs.c
index acd82594b..04516a5b0 100644
--- a/src/refdb_fs.c
+++ b/src/refdb_fs.c
@@ -15,6 +15,7 @@
 #include "refdb.h"
 #include "refdb_fs.h"
 #include "iterator.h"
+#include "sortedcache.h"
 
 #include <git2/tag.h>
 #include <git2/object.h>
@@ -53,243 +54,149 @@ typedef struct refdb_fs_backend {
 	git_repository *repo;
 	char *path;
 
-	git_refcache refcache;
+	git_sortedcache *refcache;
 	int peeling_mode;
 } refdb_fs_backend;
 
-static int reference_read(
-	git_buf *file_content,
-	time_t *mtime,
-	const char *repo_path,
-	const char *ref_name,
-	int *updated)
+static int packref_cmp(const void *a_, const void *b_)
 {
-	git_buf path = GIT_BUF_INIT;
-	int result;
-
-	assert(file_content && repo_path && ref_name);
-
-	/* Determine the full path of the file */
-	if (git_buf_joinpath(&path, repo_path, ref_name) < 0)
-		return -1;
-
-	result = git_futils_readbuffer_updated(file_content, path.ptr, mtime, NULL, updated);
-	git_buf_free(&path);
-
-	return result;
-}
-
-static int packed_parse_oid(
-	struct packref **ref_out,
-	const char **buffer_out,
-	const char *buffer_end)
-{
-	struct packref *ref = NULL;
-
-	const char *buffer = *buffer_out;
-	const char *refname_begin, *refname_end;
-
-	size_t refname_len;
-	git_oid id;
-
-	refname_begin = (buffer + GIT_OID_HEXSZ + 1);
-	if (refname_begin >= buffer_end || refname_begin[-1] != ' ')
-		goto corrupt;
-
-	/* Is this a valid object id? */
-	if (git_oid_fromstr(&id, buffer) < 0)
-		goto corrupt;
-
-	refname_end = memchr(refname_begin, '\n', buffer_end - refname_begin);
-	if (refname_end == NULL)
-		refname_end = buffer_end;
-
-	if (refname_end[-1] == '\r')
-		refname_end--;
-
-	refname_len = refname_end - refname_begin;
-
-	ref = git__calloc(1, sizeof(struct packref) + refname_len + 1);
-	GITERR_CHECK_ALLOC(ref);
-
-	memcpy(ref->name, refname_begin, refname_len);
-	ref->name[refname_len] = 0;
-
-	git_oid_cpy(&ref->oid, &id);
-
-	*ref_out = ref;
-	*buffer_out = refname_end + 1;
-	return 0;
-
-corrupt:
-	git__free(ref);
-	giterr_set(GITERR_REFERENCE, "The packed references file is corrupted");
-	return -1;
+	const struct packref *a = a_, *b = b_;
+	return strcmp(a->name, b->name);
 }
 
-static int packed_parse_peel(
-	struct packref *tag_ref,
-	const char **buffer_out,
-	const char *buffer_end)
+static int packed_reload(refdb_fs_backend *backend)
 {
-	const char *buffer = *buffer_out + 1;
-
-	assert(buffer[-1] == '^');
-
-	/* Ensure it's not the first entry of the file */
-	if (tag_ref == NULL)
-		goto corrupt;
-
-	if (buffer + GIT_OID_HEXSZ > buffer_end)
-		goto corrupt;
-
-	/* Is this a valid object id? */
-	if (git_oid_fromstr(&tag_ref->peel, buffer) < 0)
-		goto corrupt;
-
-	buffer = buffer + GIT_OID_HEXSZ;
-	if (*buffer == '\r')
-		buffer++;
-
-	if (buffer != buffer_end) {
-		if (*buffer == '\n')
-			buffer++;
-		else
-			goto corrupt;
-	}
-
-	tag_ref->flags |= PACKREF_HAS_PEEL;
-	*buffer_out = buffer;
-	return 0;
-
-corrupt:
-	giterr_set(GITERR_REFERENCE, "The packed references file is corrupted");
-	return -1;
-}
-
-static int packed_load(refdb_fs_backend *backend)
-{
-	int result, updated;
-	git_buf packfile = GIT_BUF_INIT;
-	const char *buffer_start, *buffer_end;
-	git_refcache *ref_cache = &backend->refcache;
-
-	/* First we make sure we have allocated the hash table */
-	if (ref_cache->packfile == NULL) {
-		ref_cache->packfile = git_strmap_alloc();
-		GITERR_CHECK_ALLOC(ref_cache->packfile);
-	}
+	int error;
+	git_buf packedrefs = GIT_BUF_INIT;
+	char *scan, *eof, *eol;
 
-	if (backend->path == NULL)
+	if (!backend->path)
 		return 0;
 
-	result = reference_read(&packfile, &ref_cache->packfile_time,
-		backend->path, GIT_PACKEDREFS_FILE, &updated);
+	error = git_sortedcache_lockandload(backend->refcache, &packedrefs);
 
 	/*
-	 * If we couldn't find the file, we need to clear the table and
-	 * return. On any other error, we return that error. If everything
-	 * went fine and the file wasn't updated, then there's nothing new
-	 * for us here, so just return. Anything else means we need to
-	 * refresh the packed refs.
+	 * If we can't find the packed-refs, clear table and return.
+	 * Any other error just gets passed through.
+	 * If no error, and file wasn't changed, just return.
+	 * Anything else means we need to refresh the packed refs.
 	 */
-	if (result == GIT_ENOTFOUND) {
-		git_strmap_clear(ref_cache->packfile);
-		return 0;
+	if (error <= 0) {
+		if (error == GIT_ENOTFOUND) {
+			git_sortedcache_clear(backend->refcache, true);
+			giterr_clear();
+			error = 0;
+		}
+		return error;
 	}
 
-	if (result < 0)
-		return -1;
+	/* At this point, refresh the packed refs from the loaded buffer. */
 
-	if (!updated)
-		return 0;
+	git_sortedcache_clear(backend->refcache, false);
 
-	/*
-	 * At this point, we want to refresh the packed refs. We already
-	 * have the contents in our buffer.
-	 */
-	git_strmap_clear(ref_cache->packfile);
-
-	buffer_start = (const char *)packfile.ptr;
-	buffer_end = (const char *)(buffer_start) + packfile.size;
+	scan = (char *)packedrefs.ptr;
+	eof  = scan + packedrefs.size;
 
 	backend->peeling_mode = PEELING_NONE;
 
-	if (buffer_start[0] == '#') {
+	if (*scan == '#') {
 		static const char *traits_header = "# pack-refs with: ";
 
-		if (git__prefixcmp(buffer_start, traits_header) == 0) {
-			char *traits = (char *)buffer_start + strlen(traits_header);
-			char *traits_end = strchr(traits, '\n');
+		if (git__prefixcmp(scan, traits_header) == 0) {
+			scan += strlen(traits_header);
+			eol = strchr(scan, '\n');
 
-			if (traits_end == NULL)
+			if (!eol)
 				goto parse_failed;
+			*eol = '\0';
 
-			*traits_end = '\0';
-
-			if (strstr(traits, " fully-peeled ") != NULL) {
+			if (strstr(scan, " fully-peeled ") != NULL) {
 				backend->peeling_mode = PEELING_FULL;
-			} else if (strstr(traits, " peeled ") != NULL) {
+			} else if (strstr(scan, " peeled ") != NULL) {
 				backend->peeling_mode = PEELING_STANDARD;
 			}
 
-			buffer_start = traits_end + 1;
+			scan = eol + 1;
 		}
 	}
 
-	while (buffer_start < buffer_end && buffer_start[0] == '#') {
-		buffer_start = strchr(buffer_start, '\n');
-		if (buffer_start == NULL)
+	while (scan < eof && *scan == '#') {
+		if (!(eol = strchr(scan, '\n')))
 			goto parse_failed;
-
-		buffer_start++;
+		scan = eol + 1;
 	}
 
-	while (buffer_start < buffer_end) {
-		int err;
-		struct packref *ref = NULL;
+	while (scan < eof) {
+		struct packref *ref;
+		git_oid oid;
+
+		/* parse "<OID> <refname>\n" */
 
-		if (packed_parse_oid(&ref, &buffer_start, buffer_end) < 0)
+		if (git_oid_fromstr(&oid, scan) < 0)
 			goto parse_failed;
+		scan += GIT_OID_HEXSZ;
 
-		if (buffer_start[0] == '^') {
-			if (packed_parse_peel(ref, &buffer_start, buffer_end) < 0)
-				goto parse_failed;
-		} else if (backend->peeling_mode == PEELING_FULL ||
-							(backend->peeling_mode == PEELING_STANDARD &&
-							git__prefixcmp(ref->name, GIT_REFS_TAGS_DIR) == 0)) {
-			ref->flags |= PACKREF_CANNOT_PEEL;
-		}
+		if (*scan++ != ' ')
+			goto parse_failed;
+		if (!(eol = strchr(scan, '\n')))
+			goto parse_failed;
+		*eol = '\0';
+		if (eol[-1] == '\r')
+			eol[-1] = '\0';
 
-		git_strmap_insert(ref_cache->packfile, ref->name, ref, err);
-		if (err < 0)
+		if (git_sortedcache_upsert((void **)&ref, backend->refcache, scan) < 0)
 			goto parse_failed;
+		scan = eol + 1;
+
+		git_oid_cpy(&ref->oid, &oid);
+
+		/* look for optional "^<OID>\n" */
+
+		if (*scan == '^') {
+			if (git_oid_fromstr(&oid, scan + 1) < 0)
+				goto parse_failed;
+			scan += GIT_OID_HEXSZ + 1;
+
+			if (scan < eof) {
+				if (!(eol = strchr(scan, '\n')))
+					goto parse_failed;
+				scan = eol + 1;
+			}
+
+			git_oid_cpy(&ref->peel, &oid);
+			ref->flags |= PACKREF_HAS_PEEL;
+		}
+		else if (backend->peeling_mode == PEELING_FULL ||
+				(backend->peeling_mode == PEELING_STANDARD &&
+				 git__prefixcmp(ref->name, GIT_REFS_TAGS_DIR) == 0))
+			ref->flags |= PACKREF_CANNOT_PEEL;
 	}
 
-	git_buf_free(&packfile);
+	git_sortedcache_wunlock(backend->refcache);
+	git_buf_free(&packedrefs);
+
 	return 0;
 
 parse_failed:
-	git_strmap_free(ref_cache->packfile);
-	ref_cache->packfile = NULL;
-	git_buf_free(&packfile);
+	giterr_set(GITERR_REFERENCE, "Corrupted packed references file");
+
+	git_sortedcache_clear(backend->refcache, false);
+	git_sortedcache_wunlock(backend->refcache);
+	git_buf_free(&packedrefs);
+
 	return -1;
 }
 
-static int loose_parse_oid(git_oid *oid, const char *filename, git_buf *file_content)
+static int loose_parse_oid(
+	git_oid *oid, const char *filename, git_buf *file_content)
 {
-	size_t len;
-	const char *str;
+	const char *str = git_buf_cstr(file_content);
 
-	len = git_buf_len(file_content);
-	if (len < GIT_OID_HEXSZ)
+	if (git_buf_len(file_content) < GIT_OID_HEXSZ)
 		goto corrupted;
 
-	/* str is guranteed to be zero-terminated */
-	str = git_buf_cstr(file_content);
-
 	/* we need to get 40 OID characters from the file */
-	if (git_oid_fromstr(oid, git_buf_cstr(file_content)) < 0)
+	if (git_oid_fromstr(oid, str) < 0)
 		goto corrupted;
 
 	/* If the file is longer than 40 chars, the 41st must be a space */
@@ -302,68 +209,71 @@ corrupted:
 	return -1;
 }
 
-static int loose_lookup_to_packfile(
-	struct packref **ref_out,
-	refdb_fs_backend *backend,
-	const char *name)
+static int loose_readbuffer(git_buf *buf, const char *base, const char *path)
 {
+	int error;
+
+	/* build full path to file */
+	if ((error = git_buf_joinpath(buf, base, path)) < 0 ||
+		(error = git_futils_readbuffer(buf, buf->ptr)) < 0)
+		git_buf_free(buf);
+
+	return error;
+}
+
+static int loose_lookup_to_packfile(refdb_fs_backend *backend, const char *name)
+{
+	int error = 0;
 	git_buf ref_file = GIT_BUF_INIT;
 	struct packref *ref = NULL;
-	size_t name_len;
+	git_oid oid;
 
-	*ref_out = NULL;
+	/* if we fail to load the loose reference, assume someone changed
+	 * the filesystem under us and skip it...
+	 */
+	if (loose_readbuffer(&ref_file, backend->path, name) < 0) {
+		giterr_clear();
+		goto done;
+	}
 
-	if (reference_read(&ref_file, NULL, backend->path, name, NULL) < 0)
-		return -1;
+	/* skip symbolic refs */
+	if (!git__prefixcmp(git_buf_cstr(&ref_file), GIT_SYMREF))
+		goto done;
 
-	git_buf_rtrim(&ref_file);
+	/* parse OID from file */
+	if ((error = loose_parse_oid(&oid, name, &ref_file)) < 0)
+		goto done;
 
-	name_len = strlen(name);
-	ref = git__calloc(1, sizeof(struct packref) + name_len + 1);
-	GITERR_CHECK_ALLOC(ref);
+	git_sortedcache_wlock(backend->refcache);
 
-	memcpy(ref->name, name, name_len);
-	ref->name[name_len] = 0;
+	if (!(error = git_sortedcache_upsert(
+			(void **)&ref, backend->refcache, name))) {
 
-	if (loose_parse_oid(&ref->oid, name, &ref_file) < 0) {
-		git_buf_free(&ref_file);
-		git__free(ref);
-		return -1;
+		git_oid_cpy(&ref->oid, &oid);
+		ref->flags = PACKREF_WAS_LOOSE;
 	}
 
-	ref->flags = PACKREF_WAS_LOOSE;
+	git_sortedcache_wunlock(backend->refcache);
 
-	*ref_out = ref;
+done:
 	git_buf_free(&ref_file);
-	return 0;
+	return error;
 }
 
-
 static int _dirent_loose_load(void *data, git_buf *full_path)
 {
 	refdb_fs_backend *backend = (refdb_fs_backend *)data;
-	void *old_ref = NULL;
-	struct packref *ref;
 	const char *file_path;
-	int err;
 
-	if (git_path_isdir(full_path->ptr) == true)
+	if (git__suffixcmp(full_path->ptr, ".lock") == 0)
+		return 0;
+
+	if (git_path_isdir(full_path->ptr))
 		return git_path_direach(full_path, _dirent_loose_load, backend);
 
 	file_path = full_path->ptr + strlen(backend->path);
 
-	if (loose_lookup_to_packfile(&ref, backend, file_path) < 0)
-		return -1;
-
-	git_strmap_insert2(
-		backend->refcache.packfile, ref->name, ref, old_ref, err);
-	if (err < 0) {
-		git__free(ref);
-		return -1;
-	}
-
-	git__free(old_ref);
-	return 0;
+	return loose_lookup_to_packfile(backend, file_path);
 }
 
 /*
@@ -374,11 +284,8 @@ static int _dirent_loose_load(void *data, git_buf *full_path)
  */
 static int packed_loadloose(refdb_fs_backend *backend)
 {
+	int error;
 	git_buf refs_path = GIT_BUF_INIT;
-	int result;
-
-	/* the packfile must have been previously loaded! */
-	assert(backend->refcache.packfile);
 
 	if (git_buf_joinpath(&refs_path, backend->path, GIT_REFS_DIR) < 0)
 		return -1;
@@ -388,10 +295,11 @@ static int packed_loadloose(refdb_fs_backend *backend)
 	 * This will overwrite any old packed entries with their
 	 * updated loose versions
 	 */
-	result = git_path_direach(&refs_path, _dirent_loose_load, backend);
+	error = git_path_direach(&refs_path, _dirent_loose_load, backend);
+
 	git_buf_free(&refs_path);
 
-	return result;
+	return error;
 }
 
 static int refdb_fs_backend__exists(
@@ -399,23 +307,17 @@ static int refdb_fs_backend__exists(
 	git_refdb_backend *_backend,
 	const char *ref_name)
 {
-	refdb_fs_backend *backend;
+	refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
 	git_buf ref_path = GIT_BUF_INIT;
 
-	assert(_backend);
-	backend = (refdb_fs_backend *)_backend;
-
-	if (packed_load(backend) < 0)
-		return -1;
+	assert(backend);
 
-	if (git_buf_joinpath(&ref_path, backend->path, ref_name) < 0)
+	if (packed_reload(backend) < 0 ||
+		git_buf_joinpath(&ref_path, backend->path, ref_name) < 0)
 		return -1;
 
-	if (git_path_isfile(ref_path.ptr) == true ||
-		git_strmap_exists(backend->refcache.packfile, ref_path.ptr))
-		*exists = 1;
-	else
-		*exists = 0;
+	*exists = git_path_isfile(ref_path.ptr) ||
+		(git_sortedcache_lookup(backend->refcache, ref_name) != NULL);
 
 	git_buf_free(&ref_path);
 	return 0;
@@ -447,69 +349,39 @@ static int loose_lookup(
 	refdb_fs_backend *backend,
 	const char *ref_name)
 {
-	const char *target;
-	git_oid oid;
 	git_buf ref_file = GIT_BUF_INIT;
 	int error = 0;
 
 	if (out)
 		*out = NULL;
 
-	error = reference_read(&ref_file, NULL, backend->path, ref_name, NULL);
-
-	if (error < 0)
-		goto done;
+	if ((error = loose_readbuffer(&ref_file, backend->path, ref_name)) < 0)
+		/* cannot read loose ref file - gah */;
+	else if (git__prefixcmp(git_buf_cstr(&ref_file), GIT_SYMREF) == 0) {
+		const char *target;
 
-	if (git__prefixcmp((const char *)(ref_file.ptr), GIT_SYMREF) == 0) {
 		git_buf_rtrim(&ref_file);
 
-		if ((target = loose_parse_symbolic(&ref_file)) == NULL) {
+		if (!(target = loose_parse_symbolic(&ref_file)))
 			error = -1;
-			goto done;
-		}
-
-		if (out)
+		else if (out != NULL)
 			*out = git_reference__alloc_symbolic(ref_name, target);
 	} else {
-		if ((error = loose_parse_oid(&oid, ref_name, &ref_file)) < 0)
-			goto done;
+		git_oid oid;
 
-		if (out)
+		if (!(error = loose_parse_oid(&oid, ref_name, &ref_file)) &&
+			out != NULL)
 			*out = git_reference__alloc(ref_name, &oid, NULL);
 	}
 
-	if (out && *out == NULL)
-		error = -1;
-
-done:
 	git_buf_free(&ref_file);
 	return error;
 }
 
-static int packed_map_entry(
-	struct packref **entry,
-	khiter_t *pos,
-	refdb_fs_backend *backend,
-	const char *ref_name)
+static int ref_error_notfound(const char *name)
 {
-	git_strmap *packfile_refs;
-
-	if (packed_load(backend) < 0)
-		return -1;
-
-	/* Look up on the packfile */
-	packfile_refs = backend->refcache.packfile;
-
-	*pos = git_strmap_lookup_index(packfile_refs, ref_name);
-
-	if (!git_strmap_valid_index(packfile_refs, *pos)) {
-		giterr_set(GITERR_REFERENCE, "Reference '%s' not found", ref_name);
-		return GIT_ENOTFOUND;
-	}
-
-	*entry = git_strmap_value_at(packfile_refs, *pos);
-
-	return 0;
+	giterr_set(GITERR_REFERENCE, "Reference '%s' not found", name);
+	return GIT_ENOTFOUND;
 }
 
 static int packed_lookup(
@@ -517,18 +389,27 @@ static int packed_lookup(
 	refdb_fs_backend *backend,
 	const char *ref_name)
 {
-	struct packref *entry;
-	khiter_t pos;
 	int error = 0;
+	struct packref *entry;
 
-	if ((error = packed_map_entry(&entry, &pos, backend, ref_name)) < 0)
-		return error;
+	if (packed_reload(backend) < 0)
+		return -1;
 
-	if ((*out = git_reference__alloc(ref_name,
-		&entry->oid, &entry->peel)) == NULL)
+	if (git_sortedcache_rlock(backend->refcache) < 0)
 		return -1;
 
-	return 0;
+	entry = git_sortedcache_lookup(backend->refcache, ref_name);
+	if (!entry) {
+		error = ref_error_notfound(ref_name);
+	} else {
+		*out = git_reference__alloc(ref_name, &entry->oid, &entry->peel);
+		if (!*out)
+			error = -1;
+	}
+
+	git_sortedcache_runlock(backend->refcache);
+
+	return error;
 }
 
 static int refdb_fs_backend__lookup(
@@ -536,24 +417,22 @@ static int refdb_fs_backend__lookup(
 	git_refdb_backend *_backend,
 	const char *ref_name)
 {
-	refdb_fs_backend *backend;
-	int result;
-
-	assert(_backend);
+	refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
+	int error;
 
-	backend = (refdb_fs_backend *)_backend;
+	assert(backend);
 
-	if ((result = loose_lookup(out, backend, ref_name)) == 0)
+	if (!(error = loose_lookup(out, backend, ref_name)))
 		return 0;
 
 	/* only try to lookup this reference on the packfile if it
 	 * wasn't found on the loose refs; not if there was a critical error */
-	if (result == GIT_ENOTFOUND) {
+	if (error == GIT_ENOTFOUND) {
 		giterr_clear();
-		result = packed_lookup(out, backend, ref_name);
+		error = packed_lookup(out, backend, ref_name);
 	}
 
-	return result;
+	return error;
 }
 
 typedef struct {
@@ -564,8 +443,8 @@ typedef struct {
 	git_pool pool;
 	git_vector loose;
 
-	unsigned int loose_pos;
-	khiter_t packed_pos;
+	size_t loose_pos;
+	size_t packed_pos;
 } refdb_fs_iter;
 
 static void refdb_fs_backend__iterator_free(git_reference_iterator *_iter)
@@ -580,7 +459,6 @@ static void refdb_fs_backend__iterator_free(git_reference_iterator *_iter)
 static int iter_load_loose_paths(refdb_fs_backend *backend, refdb_fs_iter *iter)
 {
 	int error = 0;
-	git_strmap *packfile = backend->refcache.packfile;
 	git_buf path = GIT_BUF_INIT;
 	git_iterator *fsit = NULL;
 	const git_index_entry *entry = NULL;
@@ -588,18 +466,18 @@ static int iter_load_loose_paths(refdb_fs_backend *backend, refdb_fs_iter *iter)
 	if (!backend->path) /* do nothing if no path for loose refs */
 		return 0;
 
-	if (git_buf_printf(&path, "%s/refs", backend->path) < 0)
-		return -1;
+	if ((error = git_buf_printf(&path, "%s/refs", backend->path)) < 0 ||
+		(error = git_iterator_for_filesystem(
+			&fsit, git_buf_cstr(&path), 0, NULL, NULL)) < 0) {
+		git_buf_free(&path);
+		return error;
+	}
 
-	if ((error = git_iterator_for_filesystem(
-			&fsit, git_buf_cstr(&path), 0, NULL, NULL)) < 0 ||
-		(error = git_vector_init(&iter->loose, 8, NULL)) < 0 ||
-		(error = git_buf_sets(&path, GIT_REFS_DIR)) < 0)
-		goto cleanup;
+	error = git_buf_sets(&path, GIT_REFS_DIR);
 
-	while (!git_iterator_advance(&entry, fsit)) {
+	while (!error && !git_iterator_advance(&entry, fsit)) {
 		const char *ref_name;
-		khiter_t pos;
+		struct packref *ref;
 		char *ref_dup;
 
 		git_buf_truncate(&path, strlen(GIT_REFS_DIR));
@@ -610,34 +488,32 @@ static int iter_load_loose_paths(refdb_fs_backend *backend, refdb_fs_iter *iter)
 			(iter->glob && p_fnmatch(iter->glob, ref_name, 0) != 0))
 			continue;
 
-		pos = git_strmap_lookup_index(packfile, ref_name);
-		if (git_strmap_valid_index(packfile, pos)) {
-			struct packref *ref = git_strmap_value_at(packfile, pos);
+		git_sortedcache_rlock(backend->refcache);
+		ref = git_sortedcache_lookup(backend->refcache, ref_name);
+		if (ref)
 			ref->flags |= PACKREF_SHADOWED;
-		}
+		git_sortedcache_runlock(backend->refcache);
 
-		if (!(ref_dup = git_pool_strdup(&iter->pool, ref_name))) {
+		ref_dup = git_pool_strdup(&iter->pool, ref_name);
+		if (!ref_dup)
 			error = -1;
-			goto cleanup;
-		}
-
-		if ((error = git_vector_insert(&iter->loose, ref_dup)) < 0)
-			goto cleanup;
+		else
+			error = git_vector_insert(&iter->loose, ref_dup);
 	}
 
-cleanup:
 	git_iterator_free(fsit);
 	git_buf_free(&path);
 
-	return 0;
+	return error;
 }
 
 static int refdb_fs_backend__iterator_next(
 	git_reference **out, git_reference_iterator *_iter)
 {
+	int error = GIT_ITEROVER;
 	refdb_fs_iter *iter = (refdb_fs_iter *)_iter;
 	refdb_fs_backend *backend = (refdb_fs_backend *)iter->parent.db->backend;
-	git_strmap *packfile = backend->refcache.packfile;
+	struct packref *ref;
 
 	while (iter->loose_pos < iter->loose.length) {
 		const char *path = git_vector_get(&iter->loose, iter->loose_pos++);
@@ -648,91 +524,83 @@ static int refdb_fs_backend__iterator_next(
 		giterr_clear();
 	}
 
-	while (iter->packed_pos < kh_end(packfile)) {
-		struct packref *ref = NULL;
-
-		while (!kh_exist(packfile, iter->packed_pos)) {
-			iter->packed_pos++;
-			if (iter->packed_pos == kh_end(packfile))
-				return GIT_ITEROVER;
-		}
+	git_sortedcache_rlock(backend->refcache);
 
-		ref = kh_val(packfile, iter->packed_pos);
-		iter->packed_pos++;
+	while (iter->packed_pos < git_sortedcache_entrycount(backend->refcache)) {
+		ref = git_sortedcache_entry(backend->refcache, iter->packed_pos++);
+		if (!ref) /* stop now if another thread deleted refs and we past end */
+			break;
 
 		if (ref->flags & PACKREF_SHADOWED)
 			continue;
-
 		if (iter->glob && p_fnmatch(iter->glob, ref->name, 0) != 0)
 			continue;
 
 		*out = git_reference__alloc(ref->name, &ref->oid, &ref->peel);
-		if (*out == NULL)
-			return -1;
-
-		return 0;
+		error = (*out != NULL) ? 0 : -1;
+		break;
 	}
 
-	return GIT_ITEROVER;
+	git_sortedcache_runlock(backend->refcache);
+	return error;
 }
 
 static int refdb_fs_backend__iterator_next_name(
 	const char **out, git_reference_iterator *_iter)
 {
+	int error = GIT_ITEROVER;
 	refdb_fs_iter *iter = (refdb_fs_iter *)_iter;
 	refdb_fs_backend *backend = (refdb_fs_backend *)iter->parent.db->backend;
-	git_strmap *packfile = backend->refcache.packfile;
+	struct packref *ref;
 
 	while (iter->loose_pos < iter->loose.length) {
 		const char *path = git_vector_get(&iter->loose, iter->loose_pos++);
 
-		if (git_strmap_exists(packfile, path))
-			continue;
-
-		if (loose_lookup(NULL, backend, path) != 0) {
-			giterr_clear();
-			continue;
+		if (loose_lookup(NULL, backend, path) == 0) {
+			*out = path;
+			return 0;
 		}
 
-		*out = path;
-		return 0;
+		giterr_clear();
 	}
 
-	while (iter->packed_pos < kh_end(packfile)) {
-		while (!kh_exist(packfile, iter->packed_pos)) {
-			iter->packed_pos++;
-			if (iter->packed_pos == kh_end(packfile))
-				return GIT_ITEROVER;
-		}
+	git_sortedcache_rlock(backend->refcache);
 
-		*out = kh_key(packfile, iter->packed_pos);
-		iter->packed_pos++;
+	while (iter->packed_pos < git_sortedcache_entrycount(backend->refcache)) {
+		ref = git_sortedcache_entry(backend->refcache, iter->packed_pos++);
+		if (!ref) /* stop now if another thread deleted refs and we past end */
+			break;
 
-		if (iter->glob && p_fnmatch(iter->glob, *out, 0) != 0)
+		if (ref->flags & PACKREF_SHADOWED)
+			continue;
+		if (iter->glob && p_fnmatch(iter->glob, ref->name, 0) != 0)
 			continue;
 
-		return 0;
+		*out = ref->name;
+		error = 0;
+		break;
 	}
 
-	return GIT_ITEROVER;
+	git_sortedcache_runlock(backend->refcache);
+	return error;
 }
 
 static int refdb_fs_backend__iterator(
 	git_reference_iterator **out, git_refdb_backend *_backend, const char *glob)
 {
 	refdb_fs_iter *iter;
-	refdb_fs_backend *backend;
+	refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
 
-	assert(_backend);
-	backend = (refdb_fs_backend *)_backend;
+	assert(backend);
 
-	if (packed_load(backend) < 0)
+	if (packed_reload(backend) < 0)
 		return -1;
 
 	iter = git__calloc(1, sizeof(refdb_fs_iter));
 	GITERR_CHECK_ALLOC(iter);
 
-	if (git_pool_init(&iter->pool, 1, 0) < 0)
+	if (git_pool_init(&iter->pool, 1, 0) < 0 ||
+		git_vector_init(&iter->loose, 8, NULL) < 0)
 		goto fail;
 
 	if (glob != NULL &&
@@ -777,33 +645,40 @@ static int reference_path_available(
 	const char* old_ref,
 	int force)
 {
-	struct packref *this_ref;
+	size_t i;
 
-	if (packed_load(backend) < 0)
+	if (packed_reload(backend) < 0)
 		return -1;
 
 	if (!force) {
 		int exists;
 
-		if (refdb_fs_backend__exists(&exists, (git_refdb_backend *)backend, new_ref) < 0)
+		if (refdb_fs_backend__exists(
+				&exists, (git_refdb_backend *)backend, new_ref) < 0)
 			return -1;
 
 		if (exists) {
 			giterr_set(GITERR_REFERENCE,
 				"Failed to write reference '%s': a reference with "
-				" that name already exists.", new_ref);
+				"that name already exists.", new_ref);
 			return GIT_EEXISTS;
 		}
 	}
 
-	git_strmap_foreach_value(backend->refcache.packfile, this_ref, {
-		if (!ref_is_available(old_ref, new_ref, this_ref->name)) {
+	git_sortedcache_rlock(backend->refcache);
+
+	for (i = 0; i < git_sortedcache_entrycount(backend->refcache); ++i) {
+		struct packref *ref = git_sortedcache_entry(backend->refcache, i);
+
+		if (ref && !ref_is_available(old_ref, new_ref, ref->name)) {
+			git_sortedcache_runlock(backend->refcache);
 			giterr_set(GITERR_REFERENCE,
-				"The path to reference '%s' collides with an existing one", new_ref);
+				"Path to reference '%s' collides with existing one", new_ref);
 			return -1;
 		}
-	});
+	}
 
+	git_sortedcache_runlock(backend->refcache);
 	return 0;
 }
 
@@ -830,12 +705,9 @@ static int loose_write(refdb_fs_backend *backend, const git_reference *ref)
 
 	if (ref->type == GIT_REF_OID) {
 		char oid[GIT_OID_HEXSZ + 1];
-
-		git_oid_fmt(oid, &ref->target.oid);
-		oid[GIT_OID_HEXSZ] = '\0';
+		git_oid_nfmt(oid, sizeof(oid), &ref->target.oid);
 
 		git_filebuf_printf(&file, "%s\n", oid);
-
 	} else if (ref->type == GIT_REF_SYMBOLIC) {
 		git_filebuf_printf(&file, GIT_SYMREF "%s\n", ref->target.symbolic);
 	} else {
@@ -845,14 +717,6 @@ static int loose_write(refdb_fs_backend *backend, const git_reference *ref)
 	return git_filebuf_commit(&file, GIT_REFS_FILE_MODE);
 }
 
-static int packed_sort(const void *a, const void *b)
-{
-	const struct packref *ref_a = (const struct packref *)a;
-	const struct packref *ref_b = (const struct packref *)b;
-
-	return strcmp(ref_a->name, ref_b->name);
-}
-
 /*
  * Find out what object this reference resolves to.
  *
@@ -905,9 +769,7 @@ static int packed_find_peel(refdb_fs_backend *backend, struct packref *ref)
 static int packed_write_ref(struct packref *ref, git_filebuf *file)
 {
 	char oid[GIT_OID_HEXSZ + 1];
-
-	git_oid_fmt(oid, &ref->oid);
-	oid[GIT_OID_HEXSZ] = 0;
+	git_oid_nfmt(oid, sizeof(oid), &ref->oid);
 
 	/*
 	 * For references that peel to an object in the repo, we must
@@ -921,8 +783,7 @@ static int packed_write_ref(struct packref *ref, git_filebuf *file)
 	 */
 	if (ref->flags & PACKREF_HAS_PEEL) {
 		char peel[GIT_OID_HEXSZ + 1];
-		git_oid_fmt(peel, &ref->peel);
-		peel[GIT_OID_HEXSZ] = 0;
+		git_oid_nfmt(peel, sizeof(peel), &ref->peel);
 
 		if (git_filebuf_printf(file, "%s %s\n^%s\n", oid, ref->name, peel) < 0)
 			return -1;
@@ -945,31 +806,30 @@ static int packed_write_ref(struct packref *ref, git_filebuf *file)
  * is well-written, because we are destructing references
  * here otherwise.
  */
-static int packed_remove_loose(
-	refdb_fs_backend *backend,
-	git_vector *packing_list)
+static int packed_remove_loose(refdb_fs_backend *backend)
 {
 	size_t i;
 	git_buf full_path = GIT_BUF_INIT;
 	int failed = 0;
 
-	for (i = 0; i < packing_list->length; ++i) {
-		struct packref *ref = git_vector_get(packing_list, i);
+	/* backend->refcache is already locked when this is called */
 
-		if ((ref->flags & PACKREF_WAS_LOOSE) == 0)
+	for (i = 0; i < git_sortedcache_entrycount(backend->refcache); ++i) {
+		struct packref *ref = git_sortedcache_entry(backend->refcache, i);
+
+		if (!ref || !(ref->flags & PACKREF_WAS_LOOSE))
 			continue;
 
 		if (git_buf_joinpath(&full_path, backend->path, ref->name) < 0)
 			return -1; /* critical; do not try to recover on oom */
 
-		if (git_path_exists(full_path.ptr) == true && p_unlink(full_path.ptr) < 0) {
+		if (git_path_exists(full_path.ptr) && p_unlink(full_path.ptr) < 0) {
 			if (failed)
 				continue;
 
 			giterr_set(GITERR_REFERENCE,
 				"Failed to remove loose reference '%s' after packing: %s",
 				full_path.ptr, strerror(errno));
-
 			failed = 1;
 		}
 
@@ -990,85 +850,53 @@ static int packed_remove_loose(
  */
 static int packed_write(refdb_fs_backend *backend)
 {
+	git_sortedcache *refcache = backend->refcache;
 	git_filebuf pack_file = GIT_FILEBUF_INIT;
 	size_t i;
-	git_buf pack_file_path = GIT_BUF_INIT;
-	git_vector packing_list;
-	unsigned int total_refs;
-
-	assert(backend && backend->refcache.packfile);
-
-	total_refs =
-		(unsigned int)git_strmap_num_entries(backend->refcache.packfile);
 
-	if (git_vector_init(&packing_list, total_refs, packed_sort) < 0)
+	/* lock the cache to updates while we do this */
+	if (git_sortedcache_wlock(refcache) < 0)
 		return -1;
 
-	/* Load all the packfile into a vector */
-	{
-		struct packref *reference;
-
-		/* cannot fail: vector already has the right size */
-		git_strmap_foreach_value(backend->refcache.packfile, reference, {
-			git_vector_insert(&packing_list, reference);
-		});
-	}
-
-	/* sort the vector so the entries appear sorted on the packfile */
-	git_vector_sort(&packing_list);
-
-	/* Now we can open the file! */
-	if (git_buf_joinpath(&pack_file_path,
-		backend->path, GIT_PACKEDREFS_FILE) < 0)
-		goto cleanup_memory;
-
-	if (git_filebuf_open(&pack_file, pack_file_path.ptr, 0) < 0)
-		goto cleanup_packfile;
+	/* Open the file! */
+	if (git_filebuf_open(&pack_file, git_sortedcache_path(refcache), 0) < 0)
+		goto fail;
 
 	/* Packfiles have a header... apparently
 	 * This is in fact not required, but we might as well print it
 	 * just for kicks */
 	if (git_filebuf_printf(&pack_file, "%s\n", GIT_PACKEDREFS_HEADER) < 0)
-		goto cleanup_packfile;
+		goto fail;
 
-	for (i = 0; i < packing_list.length; ++i) {
-		struct packref *ref = (struct packref *)git_vector_get(&packing_list, i);
+	for (i = 0; i < git_sortedcache_entrycount(refcache); ++i) {
+		struct packref *ref = git_sortedcache_entry(refcache, i);
 
 		if (packed_find_peel(backend, ref) < 0)
-			goto cleanup_packfile;
+			goto fail;
 
 		if (packed_write_ref(ref, &pack_file) < 0)
-			goto cleanup_packfile;
+			goto fail;
 	}
 
 	/* if we've written all the references properly, we can commit
 	 * the packfile to make the changes effective */
 	if (git_filebuf_commit(&pack_file, GIT_PACKEDREFS_FILE_MODE) < 0)
-		goto cleanup_memory;
+		goto fail;
 
 	/* when and only when the packfile has been properly written,
 	 * we can go ahead and remove the loose refs */
-	 if (packed_remove_loose(backend, &packing_list) < 0)
-		 goto cleanup_memory;
-
-	 {
-		struct stat st;
-		if (p_stat(pack_file_path.ptr, &st) == 0)
-			backend->refcache.packfile_time = st.st_mtime;
-	 }
+	if (packed_remove_loose(backend) < 0)
+		goto fail;
 
-	git_vector_free(&packing_list);
-	git_buf_free(&pack_file_path);
+	git_sortedcache_updated(refcache);
+	git_sortedcache_wunlock(refcache);
 
 	/* we're good now */
 	return 0;
 
-cleanup_packfile:
+fail:
 	git_filebuf_cleanup(&pack_file);
-
-cleanup_memory:
-	git_vector_free(&packing_list);
-	git_buf_free(&pack_file_path);
+	git_sortedcache_wunlock(refcache);
 
 	return -1;
 }
@@ -1078,11 +906,10 @@ static int refdb_fs_backend__write(
 	const git_reference *ref,
 	int force)
 {
-	refdb_fs_backend *backend;
+	refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
 	int error;
 
-	assert(_backend);
-	backend = (refdb_fs_backend *)_backend;
+	assert(backend);
 
 	error = reference_path_available(backend, ref->name, NULL, force);
 	if (error < 0)
@@ -1095,17 +922,13 @@ static int refdb_fs_backend__delete(
 	git_refdb_backend *_backend,
 	const char *ref_name)
 {
-	refdb_fs_backend *backend;
+	refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
 	git_buf loose_path = GIT_BUF_INIT;
-	struct packref *pack_ref;
-	khiter_t pack_ref_pos;
+	size_t pack_pos;
 	int error = 0;
 	bool loose_deleted = 0;
 
-	assert(_backend);
-	assert(ref_name);
-
-	backend = (refdb_fs_backend *)_backend;
+	assert(backend && ref_name);
 
 	/* If a loose reference exists, remove it from the filesystem */
 	if (git_buf_joinpath(&loose_path, backend->path, ref_name) < 0)
@@ -1121,19 +944,23 @@ static int refdb_fs_backend__delete(
 	if (error != 0)
 		return error;
 
+	if (packed_reload(backend) < 0)
+		return -1;
+
 	/* If a packed reference exists, remove it from the packfile and repack */
-	error = packed_map_entry(&pack_ref, &pack_ref_pos, backend, ref_name);
+	if (git_sortedcache_wlock(backend->refcache) < 0)
+		return -1;
 
-	if (error == GIT_ENOTFOUND)
-		return loose_deleted ? 0 : GIT_ENOTFOUND;
+	if (!(error = git_sortedcache_lookup_index(
+			&pack_pos, backend->refcache, ref_name)))
+		error = git_sortedcache_remove(backend->refcache, pack_pos);
 
-	if (error == 0) {
-		git_strmap_delete_at(backend->refcache.packfile, pack_ref_pos);
-		git__free(pack_ref);
-		error = packed_write(backend);
-	}
+	git_sortedcache_wunlock(backend->refcache);
 
-	return error;
+	if (error == GIT_ENOTFOUND)
+		return loose_deleted ? 0 : ref_error_notfound(ref_name);
+
+	return packed_write(backend);
 }
 
 static int refdb_fs_backend__rename(
@@ -1143,53 +970,44 @@ static int refdb_fs_backend__rename(
 	const char *new_name,
 	int force)
 {
-	refdb_fs_backend *backend;
+	refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
 	git_reference *old, *new;
 	int error;
 
-	assert(_backend);
-	backend = (refdb_fs_backend *)_backend;
-
-	error = reference_path_available(backend, new_name, old_name, force);
-	if (error < 0)
-		return error;
+	assert(backend);
 
-	error = refdb_fs_backend__lookup(&old, _backend, old_name);
-	if (error < 0)
+	if ((error = reference_path_available(
+			backend, new_name, old_name, force)) < 0 ||
+		(error = refdb_fs_backend__lookup(&old, _backend, old_name)) < 0)
 		return error;
 
-	error = refdb_fs_backend__delete(_backend, old_name);
-	if (error < 0) {
+	if ((error = refdb_fs_backend__delete(_backend, old_name)) < 0) {
 		git_reference_free(old);
 		return error;
 	}
 
-	new = realloc(old, sizeof(git_reference) + strlen(new_name) + 1);
-	memcpy(new->name, new_name, strlen(new_name) + 1);
-
-	error = loose_write(backend, new);
-	if (error < 0) {
-		git_reference_free(new);
-		return error;
+	new = git_reference__set_name(old, new_name);
+	if (!new) {
+		git_reference_free(old);
+		return -1;
 	}
 
-	if (out) {
-		*out = new;
-	} else {
+	if ((error = loose_write(backend, new)) < 0 || out == NULL) {
 		git_reference_free(new);
+		return error;
 	}
 
+	*out = new;
 	return 0;
 }
 
 static int refdb_fs_backend__compress(git_refdb_backend *_backend)
 {
-	refdb_fs_backend *backend;
+	refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
 
-	assert(_backend);
-	backend = (refdb_fs_backend *)_backend;
+	assert(backend);
 
-	if (packed_load(backend) < 0 || /* load the existing packfile */
+	if (packed_reload(backend) < 0 || /* load the existing packfile */
 		packed_loadloose(backend) < 0 || /* add all the loose refs */
 		packed_write(backend) < 0) /* write back to disk */
 		return -1;
@@ -1197,29 +1015,13 @@ static int refdb_fs_backend__compress(git_refdb_backend *_backend)
 	return 0;
 }
 
-static void refcache_free(git_refcache *refs)
-{
-	assert(refs);
-
-	if (refs->packfile) {
-		struct packref *reference;
-
-		git_strmap_foreach_value(refs->packfile, reference, {
-			git__free(reference);
-		});
-
-		git_strmap_free(refs->packfile);
-	}
-}
-
 static void refdb_fs_backend__free(git_refdb_backend *_backend)
 {
-	refdb_fs_backend *backend;
+	refdb_fs_backend *backend = (refdb_fs_backend *)_backend;
 
-	assert(_backend);
-	backend = (refdb_fs_backend *)_backend;
+	assert(backend);
 
-	refcache_free(&backend->refcache);
+	git_sortedcache_free(backend->refcache);
 	git__free(backend->path);
 	git__free(backend);
 }
@@ -1243,7 +1045,7 @@ static int setup_namespace(git_buf *path, git_repository *repo)
 	if (parts == NULL)
 		return -1;
 
-	/**
+	/*
 	 * From `man gitnamespaces`:
 	 *  namespaces which include a / will expand to a hierarchy
 	 *  of namespaces; for example, GIT_NAMESPACE=foo/bar will store
@@ -1260,7 +1062,7 @@ static int setup_namespace(git_buf *path, git_repository *repo)
 	if (git_futils_mkdir_r(git_buf_cstr(path), repo->path_repository, 0777) < 0)
 		return -1;
 
-	/* Return the root of the namespaced path, i.e. without the trailing '/refs' */
+	/* Return root of the namespaced path, i.e. without the trailing '/refs' */
 	git_buf_rtruncate_at_char(path, '/');
 	return 0;
 }
@@ -1277,13 +1079,19 @@ int git_refdb_backend_fs(
 
 	backend->repo = repository;
 
-	if (setup_namespace(&path, repository) < 0) {
-		git__free(backend);
-		return -1;
-	}
+	if (setup_namespace(&path, repository) < 0)
+		goto fail;
 
 	backend->path = git_buf_detach(&path);
 
+	if (git_buf_joinpath(&path, backend->path, GIT_PACKEDREFS_FILE) < 0 ||
+		git_sortedcache_new(
+			&backend->refcache, offsetof(struct packref, name),
+			NULL, NULL, packref_cmp, git_buf_cstr(&path)) < 0)
+		goto fail;
+
+	git_buf_free(&path);
+
 	backend->parent.exists = &refdb_fs_backend__exists;
 	backend->parent.lookup = &refdb_fs_backend__lookup;
 	backend->parent.iterator = &refdb_fs_backend__iterator;
@@ -1295,4 +1103,10 @@ int git_refdb_backend_fs(
 
 	*backend_out = (git_refdb_backend *)backend;
 	return 0;
+
+fail:
+	git_buf_free(&path);
+	git__free(backend->path);
+	git__free(backend);
+	return -1;
 }
diff --git a/src/refs.c b/src/refs.c
index 6cc937fda..c045ab9dc 100644
--- a/src/refs.c
+++ b/src/refs.c
@@ -88,6 +88,17 @@ git_reference *git_reference__alloc(
 	return ref;
 }
 
+git_reference *git_reference__set_name(
+	git_reference *ref, const char *name)
+{
+	size_t namelen = strlen(name);
+	git_reference *rewrite =
+		git__realloc(ref, sizeof(git_reference) + namelen + 1);
+	if (rewrite != NULL)
+		memcpy(rewrite->name, name, namelen + 1);
+	return rewrite;
+}
+
 void git_reference_free(git_reference *reference)
 {
 	if (reference == NULL)
diff --git a/src/refs.h b/src/refs.h
index cb75abbe5..4b91c25e8 100644
--- a/src/refs.h
+++ b/src/refs.h
@@ -61,6 +61,8 @@ struct git_reference {
 	char name[0];
 };
 
+git_reference *git_reference__set_name(git_reference *ref, const char *name);
+
 int git_reference__normalize_name_lax(char *buffer_out, size_t out_size, const char *name);
 int git_reference__normalize_name(git_buf *buf, const char *name, unsigned int flags);
 int git_reference__update_terminal(git_repository *repo, const char *ref_name, const git_oid *oid);
diff --git a/src/sortedcache.c b/src/sortedcache.c
new file mode 100644
index 000000000..466e55dbe
--- /dev/null
+++ b/src/sortedcache.c
@@ -0,0 +1,380 @@
+#include "sortedcache.h"
+
+GIT__USE_STRMAP;
+
+int git_sortedcache_new(
+	git_sortedcache **out,
+	size_t item_path_offset,
+	git_sortedcache_free_item_fn free_item,
+	void *free_item_payload,
+	git_vector_cmp item_cmp,
+	const char *path)
+{
+	git_sortedcache *sc;
+	size_t pathlen;
+
+	pathlen = path ? strlen(path) : 0;
+
+	sc = git__calloc(sizeof(git_sortedcache) + pathlen + 1, 1);
+	GITERR_CHECK_ALLOC(sc);
+
+	if (git_pool_init(&sc->pool, 1, 0) < 0 ||
+		git_vector_init(&sc->items, 4, item_cmp) < 0 ||
+		(sc->map = git_strmap_alloc()) == NULL)
+		goto fail;
+
+	if (git_rwlock_init(&sc->lock)) {
+		giterr_set(GITERR_OS, "Failed to initialize lock");
+		goto fail;
+	}
+
+	sc->item_path_offset  = item_path_offset;
+	sc->free_item         = free_item;
+	sc->free_item_payload = free_item_payload;
+	GIT_REFCOUNT_INC(sc);
+	if (pathlen)
+		memcpy(sc->path, path, pathlen);
+
+	*out = sc;
+	return 0;
+
+fail:
+	if (sc->map)
+		git_strmap_free(sc->map);
+	git_vector_free(&sc->items);
+	git_pool_clear(&sc->pool);
+	git__free(sc);
+	return -1;
+}
+
+void git_sortedcache_incref(git_sortedcache *sc)
+{
+	GIT_REFCOUNT_INC(sc);
+}
+
+const char *git_sortedcache_path(git_sortedcache *sc)
+{
+	return sc->path;
+}
+
+static void sortedcache_clear(git_sortedcache *sc)
+{
+	git_strmap_clear(sc->map);
+
+	if (sc->free_item) {
+		size_t i;
+		void *item;
+
+		git_vector_foreach(&sc->items, i, item) {
+			sc->free_item(sc->free_item_payload, item);
+		}
+	}
+
+	git_vector_clear(&sc->items);
+
+	git_pool_clear(&sc->pool);
+}
+
+static void sortedcache_free(git_sortedcache *sc)
+{
+	/* acquire write lock to make sure everyone else is done */
+	if (git_sortedcache_wlock(sc) < 0)
+		return;
+
+	sortedcache_clear(sc);
+	git_vector_free(&sc->items);
+	git_strmap_free(sc->map);
+
+	git_sortedcache_wunlock(sc);
+
+	git_rwlock_free(&sc->lock);
+	git__free(sc);
+}
+
+void git_sortedcache_free(git_sortedcache *sc)
+{
+	if (!sc)
+		return;
+	GIT_REFCOUNT_DEC(sc, sortedcache_free);
+}
+
+static int sortedcache_copy_item(void *payload, void *tgt_item, void *src_item)
+{
+	git_sortedcache *sc = payload;
+	/* path will already have been copied by upsert */
+	memcpy(tgt_item, src_item, sc->item_path_offset);
+	return 0;
+}
+
+/* copy a sorted cache */
+int git_sortedcache_copy(
+	git_sortedcache **out,
+	git_sortedcache *src,
+	bool lock,
+	int (*copy_item)(void *payload, void *tgt_item, void *src_item),
+	void *payload)
+{
+	int error = 0;
+	git_sortedcache *tgt;
+	size_t i;
+	void *src_item, *tgt_item;
+
+	/* just use memcpy if no special copy fn is passed in */
+	if (!copy_item) {
+		copy_item = sortedcache_copy_item;
+		payload   = src;
+	}
+
+	if ((error = git_sortedcache_new(
+			&tgt, src->item_path_offset,
+			src->free_item, src->free_item_payload,
+			src->items._cmp, src->path)) < 0)
+		return error;
+
+	if (lock && git_sortedcache_rlock(src) < 0) {
+		git_sortedcache_free(tgt);
+		return -1;
+	}
+
+	git_vector_foreach(&src->items, i, src_item) {
+		char *path = ((char *)src_item) + src->item_path_offset;
+
+		if ((error = git_sortedcache_upsert(&tgt_item, tgt, path)) < 0 ||
+			(error = copy_item(payload, tgt_item, src_item)) < 0)
+			break;
+	}
+
+	if (lock)
+		git_sortedcache_runlock(src);
+	if (error)
+		git_sortedcache_free(tgt);
+
+	*out = !error ? tgt : NULL;
+
+	return error;
+}
+
+/* lock sortedcache while making modifications */
+int git_sortedcache_wlock(git_sortedcache *sc)
+{
+	GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
+
+	if (git_rwlock_wrlock(&sc->lock) < 0) {
+		giterr_set(GITERR_OS, "Unable to acquire write lock on cache");
+		return -1;
+	}
+	return 0;
+}
+
+/* unlock sorted cache when done with modifications */
+void git_sortedcache_wunlock(git_sortedcache *sc)
+{
+	git_vector_sort(&sc->items);
+	git_rwlock_wrunlock(&sc->lock);
+}
+
+/* lock sortedcache for read */
+int git_sortedcache_rlock(git_sortedcache *sc)
+{
+	GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
+
+	if (git_rwlock_rdlock(&sc->lock) < 0) {
+		giterr_set(GITERR_OS, "Unable to acquire read lock on cache");
+		return -1;
+	}
+	return 0;
+}
+
+/* unlock sorted cache when done reading */
+void git_sortedcache_runlock(git_sortedcache *sc)
+{
+	GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
+	git_rwlock_rdunlock(&sc->lock);
+}
+
+/* if the file has changed, lock cache and load file contents into buf;
+ * returns <0 on error, >0 if file has not changed
+ */
+int git_sortedcache_lockandload(git_sortedcache *sc, git_buf *buf)
+{
+	int error, fd;
+
+	if ((error = git_sortedcache_wlock(sc)) < 0)
+		return error;
+
+	if ((error = git_futils_filestamp_check(&sc->stamp, sc->path)) <= 0)
+		goto unlock;
+
+	if (!git__is_sizet(sc->stamp.size)) {
+		giterr_set(GITERR_INVALID, "Unable to load file larger than size_t");
+		error = -1;
+		goto unlock;
+	}
+
+	if ((fd = git_futils_open_ro(sc->path)) < 0) {
+		error = fd;
+		goto unlock;
+	}
+
+	if (buf)
+		error = git_futils_readbuffer_fd(buf, fd, (size_t)sc->stamp.size);
+
+	(void)p_close(fd);
+
+	if (error < 0)
+		goto unlock;
+
+	return 1; /* return 1 -> file needs reload and was successfully loaded */
+
+unlock:
+	git_sortedcache_wunlock(sc);
+	return error;
+}
+
+void git_sortedcache_updated(git_sortedcache *sc)
+{
+	 /* update filestamp to latest value */
+	if (git_futils_filestamp_check(&sc->stamp, sc->path) < 0)
+		giterr_clear();
+}
+
+/* release all items in sorted cache */
+int git_sortedcache_clear(git_sortedcache *sc, bool wlock)
+{
+	if (wlock && git_sortedcache_wlock(sc) < 0)
+		return -1;
+
+	sortedcache_clear(sc);
+
+	if (wlock)
+		git_sortedcache_wunlock(sc);
+
+	return 0;
+}
+
+/* find and/or insert item, returning pointer to item data */
+int git_sortedcache_upsert(void **out, git_sortedcache *sc, const char *key)
+{
+	int error = 0;
+	khiter_t pos;
+	void *item;
+	size_t keylen, itemlen;
+	char *item_key;
+
+	pos = git_strmap_lookup_index(sc->map, key);
+	if (git_strmap_valid_index(sc->map, pos)) {
+		item = git_strmap_value_at(sc->map, pos);
+		goto done;
+	}
+
+	keylen  = strlen(key);
+	itemlen = sc->item_path_offset + keylen + 1;
+	itemlen = (itemlen + 7) & ~7;
+
+	if ((item = git_pool_mallocz(&sc->pool, (uint32_t)itemlen)) == NULL) {
+		/* don't use GITERR_CHECK_ALLOC b/c of lock */
+		error = -1;
+		goto done;
+	}
+
+	/* one strange thing is that even if the vector or hash table insert
+	 * fail, there is no way to free the pool item so we just abandon it
+	 */
+
+	item_key = ((char *)item) + sc->item_path_offset;
+	memcpy(item_key, key, keylen);
+
+	pos = kh_put(str, sc->map, item_key, &error);
+	if (error < 0)
+		goto done;
+
+	if (!error)
+		kh_key(sc->map, pos) = item_key;
+	kh_val(sc->map, pos) = item;
+
+	error = git_vector_insert(&sc->items, item);
+	if (error < 0)
+		git_strmap_delete_at(sc->map, pos);
+
+done:
+	if (out)
+		*out = !error ? item : NULL;
+	return error;
+}
+
+/* lookup item by key */
+void *git_sortedcache_lookup(const git_sortedcache *sc, const char *key)
+{
+	khiter_t pos = git_strmap_lookup_index(sc->map, key);
+	if (git_strmap_valid_index(sc->map, pos))
+		return git_strmap_value_at(sc->map, pos);
+	return NULL;
+}
+
+/* find out how many items are in the cache */
+size_t git_sortedcache_entrycount(const git_sortedcache *sc)
+{
+	return git_vector_length(&sc->items);
+}
+
+/* lookup item by index */
+void *git_sortedcache_entry(git_sortedcache *sc, size_t pos)
+{
+	/* make sure the items are sorted so this gets the correct item */
+	if (!sc->items.sorted)
+		git_vector_sort(&sc->items);
+
+	return git_vector_get(&sc->items, pos);
+}
+
+/* helper struct so bsearch callback can know offset + key value for cmp */
+struct sortedcache_magic_key {
+	size_t offset;
+	const char *key;
+};
+
+static int sortedcache_magic_cmp(const void *key, const void *value)
+{
+	const struct sortedcache_magic_key *magic = key;
+	const char *value_key = ((const char *)value) + magic->offset;
+	return strcmp(magic->key, value_key);
+}
+
+/* lookup index of item by key */
+int git_sortedcache_lookup_index(
+	size_t *out, git_sortedcache *sc, const char *key)
+{
+	struct sortedcache_magic_key magic;
+
+	magic.offset = sc->item_path_offset;
+	magic.key    = key;
+
+	return git_vector_bsearch2(out, &sc->items, sortedcache_magic_cmp, &magic);
+}
+
+/* remove entry from cache */
+int git_sortedcache_remove(git_sortedcache *sc, size_t pos)
+{
+	char *item;
+	khiter_t mappos;
+
+	/* because of pool allocation, this can't actually remove the item,
+	 * but we can remove it from the items vector and the hash table.
+	 */
+
+	if ((item = git_vector_get(&sc->items, pos)) == NULL) {
+		giterr_set(GITERR_INVALID, "Removing item out of range");
+		return GIT_ENOTFOUND;
+	}
+
+	(void)git_vector_remove(&sc->items, pos);
+
+	mappos = git_strmap_lookup_index(sc->map, item + sc->item_path_offset);
+	git_strmap_delete_at(sc->map, mappos);
+
+	if (sc->free_item)
+		sc->free_item(sc->free_item_payload, item);
+
+	return 0;
+}
+
diff --git a/src/sortedcache.h b/src/sortedcache.h
new file mode 100644
index 000000000..5ebb116ed
--- /dev/null
+++ b/src/sortedcache.h
@@ -0,0 +1,176 @@
+/*
+ * Copyright (C) the libgit2 contributors. All rights reserved.
+ *
+ * This file is part of libgit2, distributed under the GNU GPL v2 with
+ * a Linking Exception. For full terms see the included COPYING file.
+ */
+#ifndef INCLUDE_sorted_cache_h__
+#define INCLUDE_sorted_cache_h__
+
+#include "util.h"
+#include "fileops.h"
+#include "vector.h"
+#include "thread-utils.h"
+#include "pool.h"
+#include "strmap.h"
+
+/*
+ * The purpose of this data structure is to cache the parsed contents of a
+ * file (a.k.a. the backing file) where each item in the file can be
+ * identified by a key string and you want to both look them up by name
+ * and traverse them in sorted order.  Each item is assumed to itself end
+ * in a GIT_FLEX_ARRAY.
+ */
+
+typedef void (*git_sortedcache_free_item_fn)(void *payload, void *item);
+
+typedef struct {
+	git_refcount rc;
+	git_rwlock   lock;
+	size_t       item_path_offset;
+	git_sortedcache_free_item_fn free_item;
+	void         *free_item_payload;
+	git_pool     pool;
+	git_vector   items;
+	git_strmap   *map;
+	git_futils_filestamp stamp;
+	char         path[GIT_FLEX_ARRAY];
+} git_sortedcache;
+
+/* Create a new sortedcache
+ *
+ * Even though every sortedcache stores items with a GIT_FLEX_ARRAY at
+ * the end containing their key string, you have to provide the item_cmp
+ * sorting function because the sorting function doesn't get a payload
+ * and therefore can't know the offset to the item key string. :-(
+ *
+ * @param out The allocated git_sortedcache
+ * @param item_path_offset Offset to the GIT_FLEX_ARRAY item key in the
+ *        struct - use offsetof(struct mine, key-field) to get this
+ * @param free_item Optional callback to free each item
+ * @param free_item_payload Optional payload passed to free_item callback
+ * @param item_cmp Compare the keys of two items
+ * @param path The path to the backing store file for this cache; this
+ *        may be NULL.  The cache makes it easy to load this and check
+ *        if it has been modified since the last load and/or write.
+ */
+int git_sortedcache_new(
+	git_sortedcache **out,
+	size_t item_path_offset, /* use offsetof(struct, path-field) macro */
+	git_sortedcache_free_item_fn free_item,
+	void *free_item_payload,
+	git_vector_cmp item_cmp,
+	const char *path);
+
+/* Copy a sorted cache
+ *
+ * - `copy_item` can be NULL to just use memcpy
+ * - if `lock`, grabs read lock on `src` during copy and releases after
+ */
+int git_sortedcache_copy(
+	git_sortedcache **out,
+	git_sortedcache *src,
+	bool lock,
+	int (*copy_item)(void *payload, void *tgt_item, void *src_item),
+	void *payload);
+
+/* Free sorted cache (first calling `free_item` callbacks)
+ *
+ * Don't call on a locked collection - it may acquire a write lock
+ */
+void git_sortedcache_free(git_sortedcache *sc);
+
+/* Increment reference count - balance with call to free */
+void git_sortedcache_incref(git_sortedcache *sc);
+
+/* Get the pathname associated with this cache at creation time */
+const char *git_sortedcache_path(git_sortedcache *sc);
+
+/*
+ * CACHE WRITE FUNCTIONS
+ *
+ * The following functions require you to have a writer lock to make the
+ * modification.  Some of the functions take a `wlock` parameter and
+ * will optionally lock and unlock for you if that is passed as true.
+ *
+ */
+
+/* Lock sortedcache for write */
+int git_sortedcache_wlock(git_sortedcache *sc);
+
+/* Unlock sorted cache when done with write */
+void git_sortedcache_wunlock(git_sortedcache *sc);
+
+/* Lock cache and load backing file into a buffer.
+ *
+ * This grabs a write lock on the cache then looks at the modification
+ * time and size of the file on disk.
+ *
+ * If the file appears to have changed, this loads the file contents into
+ * the buffer and returns a positive value leaving the cache locked - the
+ * caller should parse the file content, update the cache as needed, then
+ * release the lock.  NOTE: In this case, the caller MUST unlock the cache.
+ *
+ * If the file appears to be unchanged, then this automatically releases
+ * the lock on the cache, clears the buffer, and returns 0.
+ *
+ * @return 0 if up-to-date, 1 if out-of-date, <0 on error
+ */
+int git_sortedcache_lockandload(git_sortedcache *sc, git_buf *buf);
+
+/* Refresh file timestamp after write completes
+ * You should already be holding the write lock when you call this.
+ */
+void git_sortedcache_updated(git_sortedcache *sc);
+
+/* Release all items in sorted cache
+ *
+ * If `wlock` is true, grabs write lock and releases when done, otherwise
+ * you should already be holding a write lock when you call this.
+ */
+int git_sortedcache_clear(git_sortedcache *sc, bool wlock);
+
+/* Find and/or insert item, returning pointer to item data.
+ * You should already be holding the write lock when you call this.
+ */
+int git_sortedcache_upsert(
+	void **out, git_sortedcache *sc, const char *key);
+
+/* Removes entry at pos from cache
+ * You should already be holding the write lock when you call this.
+ */
+int git_sortedcache_remove(git_sortedcache *sc, size_t pos);
+
+/*
+ * CACHE READ FUNCTIONS
+ *
+ * The following functions access items in the cache.  To prevent the
+ * results from being invalidated before they can be used, you should be
+ * holding either a read lock or a write lock when using these functions.
+ *
+ */
+
+/* Lock sortedcache for read */
+int git_sortedcache_rlock(git_sortedcache *sc);
+
+/* Unlock sorted cache when done with read */
+void git_sortedcache_runlock(git_sortedcache *sc);
+
+/* Lookup item by key - returns NULL if not found */
+void *git_sortedcache_lookup(const git_sortedcache *sc, const char *key);
+
+/* Get how many items are in the cache
+ *
+ * You can call this function without holding a lock, but be aware
+ * that it may change before you use it.
+ */
+size_t git_sortedcache_entrycount(const git_sortedcache *sc);
+
+/* Lookup item by index - returns NULL if out of range */
+void *git_sortedcache_entry(git_sortedcache *sc, size_t pos);
+
+/* Lookup index of item by key - returns GIT_ENOTFOUND if not found */
+int git_sortedcache_lookup_index(
+	size_t *out, git_sortedcache *sc, const char *key);
+
+#endif
diff --git a/src/thread-utils.h b/src/thread-utils.h
index 04e02959f..914c1357d 100644
--- a/src/thread-utils.h
+++ b/src/thread-utils.h
@@ -41,7 +41,8 @@ typedef git_atomic git_atomic_ssize;
 #ifdef GIT_THREADS
 
 #define git_thread pthread_t
-#define git_thread_create(thread, attr, start_routine, arg) pthread_create(thread, attr, start_routine, arg)
+#define git_thread_create(thread, attr, start_routine, arg) \
+	pthread_create(thread, attr, start_routine, arg)
 #define git_thread_kill(thread) pthread_cancel(thread)
 #define git_thread_exit(status)	pthread_exit(status)
 #define git_thread_join(id, status) pthread_join(id, status)
@@ -61,6 +62,30 @@ typedef git_atomic git_atomic_ssize;
 #define git_cond_signal(c)	pthread_cond_signal(c)
 #define git_cond_broadcast(c)	pthread_cond_broadcast(c)
 
+/* Pthread (-ish) rwlock
+ *
+ * This differs from normal pthreads rwlocks in two ways:
+ * 1. Separate APIs for releasing read locks and write locks (as
+ *    opposed to the pure POSIX API which only has one unlock fn)
+ * 2. You should not use recursive read locks (i.e. grabbing a read
+ *    lock in a thread that already holds a read lock) because the
+ *    Windows implementation doesn't support it
+ */
+#define git_rwlock pthread_rwlock_t
+#define git_rwlock_init(a)		pthread_rwlock_init(a, NULL)
+#define git_rwlock_rdlock(a)	pthread_rwlock_rdlock(a)
+#define git_rwlock_rdunlock(a)	pthread_rwlock_rdunlock(a)
+#define git_rwlock_wrlock(a)	pthread_rwlock_wrlock(a)
+#define git_rwlock_wrunlock(a)	pthread_rwlock_wrunlock(a)
+#define git_rwlock_free(a)		pthread_rwlock_destroy(a)
+#define GIT_RWLOCK_STATIC_INIT	PTHREAD_RWLOCK_INITIALIZER
+
+#ifndef GIT_WIN32
+#define pthread_rwlock_rdunlock pthread_rwlock_unlock
+#define pthread_rwlock_wrunlock pthread_rwlock_unlock
+#endif
+
+
 GIT_INLINE(void) git_atomic_set(git_atomic *a, int val)
 {
 #if defined(GIT_WIN32)
@@ -147,7 +172,7 @@ GIT_INLINE(int64_t) git_atomic64_add(git_atomic64 *a, int64_t addend)
 #else
 
 #define git_thread unsigned int
-#define git_thread_create(thread, attr, start_routine, arg) (void)0
+#define git_thread_create(thread, attr, start_routine, arg) 0
 #define git_thread_kill(thread) (void)0
 #define git_thread_exit(status) (void)0
 #define git_thread_join(id, status) (void)0
@@ -167,6 +192,17 @@ GIT_INLINE(int64_t) git_atomic64_add(git_atomic64 *a, int64_t addend)
 #define git_cond_signal(c) (void)0
 #define git_cond_broadcast(c) (void)0
 
+/* Pthreads rwlock */
+#define git_rwlock unsigned int
+#define git_rwlock_init(a)		0
+#define git_rwlock_rdlock(a)	0
+#define git_rwlock_rdunlock(a)	(void)0
+#define git_rwlock_wrlock(a)	0
+#define git_rwlock_wrunlock(a)	(void)0
+#define git_rwlock_free(a)		(void)0
+#define GIT_RWLOCK_STATIC_INIT	0
+
+
 GIT_INLINE(void) git_atomic_set(git_atomic *a, int val)
 {
 	a->val = val;
diff --git a/src/vector.h b/src/vector.h
index cca846f43..279f5c6ee 100644
--- a/src/vector.h
+++ b/src/vector.h
@@ -55,6 +55,11 @@ GIT_INLINE(void *) git_vector_get(const git_vector *v, size_t position)
 
 #define GIT_VECTOR_GET(V,I) ((I) < (V)->length ? (V)->contents[(I)] : NULL)
 
+GIT_INLINE(size_t) git_vector_length(const git_vector *v)
+{
+	return v->length;
+}
+
 GIT_INLINE(void *) git_vector_last(const git_vector *v)
 {
 	return (v->length > 0) ? git_vector_get(v, v->length - 1) : NULL;
diff --git a/src/win32/pthread.c b/src/win32/pthread.c
index 2f263b3e0..d50ace695 100644
--- a/src/win32/pthread.c
+++ b/src/win32/pthread.c
@@ -127,9 +127,10 @@ int pthread_cond_signal(pthread_cond_t *cond)
 	return 0;
 }
 
-/* pthread_cond_broadcast is not implemented because doing so with just Win32 events
- * is quite complicated, and no caller in libgit2 uses it yet. */
-
+/* pthread_cond_broadcast is not implemented because doing so with just
+ * Win32 events is quite complicated, and no caller in libgit2 uses it
+ * yet.
+ */
 int pthread_num_processors_np(void)
 {
 	DWORD_PTR p, s;
@@ -142,3 +143,111 @@ int pthread_num_processors_np(void)
 	return n ? n : 1;
 }
 
+
+static HINSTANCE win32_kernel32_dll;
+
+typedef void (WINAPI *win32_srwlock_fn)(GIT_SRWLOCK *);
+
+static win32_srwlock_fn win32_srwlock_initialize;
+static win32_srwlock_fn win32_srwlock_acquire_shared;
+static win32_srwlock_fn win32_srwlock_release_shared;
+static win32_srwlock_fn win32_srwlock_acquire_exclusive;
+static win32_srwlock_fn win32_srwlock_release_exclusive;
+
+int pthread_rwlock_init(
+	pthread_rwlock_t *GIT_RESTRICT lock,
+	const pthread_rwlockattr_t *GIT_RESTRICT attr)
+{
+	(void)attr;
+
+	if (win32_srwlock_initialize)
+		win32_srwlock_initialize(&lock->native.srwl);
+	else
+		InitializeCriticalSection(&lock->native.csec);
+
+	return 0;
+}
+
+int pthread_rwlock_rdlock(pthread_rwlock_t *lock)
+{
+	if (win32_srwlock_acquire_shared)
+		win32_srwlock_acquire_shared(&lock->native.srwl);
+	else
+		EnterCriticalSection(&lock->native.csec);
+
+	return 0;
+}
+
+int pthread_rwlock_rdunlock(pthread_rwlock_t *lock)
+{
+	if (win32_srwlock_release_shared)
+		win32_srwlock_release_shared(&lock->native.srwl);
+	else
+		LeaveCriticalSection(&lock->native.csec);
+
+	return 0;
+}
+
+int pthread_rwlock_wrlock(pthread_rwlock_t *lock)
+{
+	if (win32_srwlock_acquire_exclusive)
+		win32_srwlock_acquire_exclusive(&lock->native.srwl);
+	else
+		EnterCriticalSection(&lock->native.csec);
+
+	return 0;
+}
+
+int pthread_rwlock_wrunlock(pthread_rwlock_t *lock)
+{
+	if (win32_srwlock_release_exclusive)
+		win32_srwlock_release_exclusive(&lock->native.srwl);
+	else
+		LeaveCriticalSection(&lock->native.csec);
+
+	return 0;
+}
+
+int pthread_rwlock_destroy(pthread_rwlock_t *lock)
+{
+	if (!win32_srwlock_initialize)
+		DeleteCriticalSection(&lock->native.csec);
+	git__memzero(lock, sizeof(*lock));
+	return 0;
+}
+
+
+int win32_pthread_initialize(void)
+{
+	if (win32_kernel32_dll)
+		return 0;
+
+	win32_kernel32_dll = LoadLibrary("Kernel32.dll");
+	if (!win32_kernel32_dll) {
+		giterr_set(GITERR_OS, "Could not load Kernel32.dll!");
+		return -1;
+	}
+
+	win32_srwlock_initialize = (win32_srwlock_fn)
+		GetProcAddress(win32_kernel32_dll, "InitializeSRWLock");
+	win32_srwlock_acquire_shared = (win32_srwlock_fn)
+		GetProcAddress(win32_kernel32_dll, "AcquireSRWLockShared");
+	win32_srwlock_release_shared = (win32_srwlock_fn)
+		GetProcAddress(win32_kernel32_dll, "ReleaseSRWLockShared");
+	win32_srwlock_acquire_exclusive = (win32_srwlock_fn)
+		GetProcAddress(win32_kernel32_dll, "AcquireSRWLockExclusive");
+	win32_srwlock_release_exclusive = (win32_srwlock_fn)
+		GetProcAddress(win32_kernel32_dll, "ReleaseSRWLockExclusive");
+
+	return 0;
+}
+
+int win32_pthread_shutdown(void)
+{
+	if (win32_kernel32_dll) {
+		FreeLibrary(win32_kernel32_dll);
+		win32_kernel32_dll = NULL;
+	}
+
+	return 0;
+}
diff --git a/src/win32/pthread.h b/src/win32/pthread.h
index 8277ecf6e..2ba2ca552 100644
--- a/src/win32/pthread.h
+++ b/src/win32/pthread.h
@@ -19,22 +19,34 @@
 typedef int pthread_mutexattr_t;
 typedef int pthread_condattr_t;
 typedef int pthread_attr_t;
+typedef int pthread_rwlockattr_t;
+
 typedef CRITICAL_SECTION pthread_mutex_t;
 typedef HANDLE pthread_t;
 typedef HANDLE pthread_cond_t;
 
-#define PTHREAD_MUTEX_INITIALIZER {(void*)-1};
+typedef struct { void *Ptr; } GIT_SRWLOCK;
+
+typedef struct {
+	union {
+		GIT_SRWLOCK srwl;
+		CRITICAL_SECTION csec;
+	} native;
+} pthread_rwlock_t;
+
+#define PTHREAD_MUTEX_INITIALIZER  {(void*)-1}
 
 int pthread_create(
-	pthread_t *GIT_RESTRICT,
-	const pthread_attr_t *GIT_RESTRICT,
+	pthread_t *GIT_RESTRICT thread,
+	const pthread_attr_t *GIT_RESTRICT attr,
 	void *(*start_routine)(void*),
-	void *__restrict);
+	void *GIT_RESTRICT arg);
 
 int pthread_join(pthread_t, void **);
 
 int pthread_mutex_init(
-	pthread_mutex_t *GIT_RESTRICT, const pthread_mutexattr_t *GIT_RESTRICT);
+	pthread_mutex_t *GIT_RESTRICT mutex,
+	const pthread_mutexattr_t *GIT_RESTRICT mutexattr);
 int pthread_mutex_destroy(pthread_mutex_t *);
 int pthread_mutex_lock(pthread_mutex_t *);
 int pthread_mutex_unlock(pthread_mutex_t *);
@@ -47,4 +59,16 @@ int pthread_cond_signal(pthread_cond_t *);
 
 int pthread_num_processors_np(void);
 
+int pthread_rwlock_init(
+	pthread_rwlock_t *GIT_RESTRICT lock,
+	const pthread_rwlockattr_t *GIT_RESTRICT attr);
+int pthread_rwlock_rdlock(pthread_rwlock_t *);
+int pthread_rwlock_rdunlock(pthread_rwlock_t *);
+int pthread_rwlock_wrlock(pthread_rwlock_t *);
+int pthread_rwlock_wrunlock(pthread_rwlock_t *);
+int pthread_rwlock_destroy(pthread_rwlock_t *);
+
+extern int win32_pthread_initialize(void);
+extern int win32_pthread_shutdown(void);
+
 #endif