Thread safe cache

6 files changed, 304 insertions, 59 deletions

diff --git a/src/cache.c b/src/cache.c
new file mode 100644
index 000000000..5a9b8415c
--- /dev/null
+++ b/src/cache.c
@@ -0,0 +1,175 @@
+/*
+ * This file is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License, version 2,
+ * as published by the Free Software Foundation.
+ *
+ * In addition to the permissions in the GNU General Public License,
+ * the authors give you unlimited permission to link the compiled
+ * version of this file into combinations with other programs,
+ * and to distribute those combinations without any restriction
+ * coming from the use of this file.  (The General Public License
+ * restrictions do apply in other respects; for example, they cover
+ * modification of the file, and distribution when not linked into
+ * a combined executable.)
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; see the file COPYING.  If not, write to
+ * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#include "common.h"
+#include "repository.h"
+#include "commit.h"
+#include "thread-utils.h"
+#include "cache.h"
+
+#define GIT_CACHE_OPENADR 3
+
+
+GIT_INLINE(int) cached_obj_compare(git_cached_obj *obj, const git_oid *oid)
+{
+	return git_oid_cmp(&obj->oid, oid);
+}
+
+GIT_INLINE(void) cached_obj_incref(git_cached_obj *obj)
+{
+	git_atomic_inc(&obj->refcount);
+}
+
+GIT_INLINE(void) cached_obj_decref(git_cached_obj *obj, git_cached_obj_freeptr free_obj)
+{
+	if (git_atomic_dec(&obj->refcount) == 0)
+		free_obj(obj);
+}
+
+
+void git_cache_init(git_cache *cache, size_t size, git_cached_obj_freeptr free_ptr)
+{
+	size_t i;
+
+	if (size < 8)
+		size = 8;
+
+	/* round up size to closest power of 2 */
+	size--;
+	size |= size >> 1;
+	size |= size >> 2;
+	size |= size >> 4;
+	size |= size >> 8;
+	size |= size >> 16;
+
+	cache->size_mask = size;
+	cache->lru_count = 0;
+	cache->free_obj = free_ptr;
+
+	cache->nodes = git__malloc((size + 1) * sizeof(cache_node));
+
+	for (i = 0; i < (size + 1); ++i) {
+		git_mutex_init(&cache->nodes[i].lock);
+		cache->nodes[i].ptr = NULL;
+		cache->nodes[i].lru = 0;
+	}
+}
+
+void git_cache_free(git_cache *cache)
+{
+	size_t i;
+
+	for (i = 0; i < (cache->size_mask + 1); ++i) {
+		cached_obj_decref(cache->nodes[i].ptr, cache->free_obj);
+		git_mutex_free(&cache->nodes[i].lock);
+	}
+
+	free(cache->nodes);
+}
+
+void *git_cache_get(git_cache *cache, const git_oid *oid)
+{
+	const uint32_t *hash;
+	size_t i, pos, found = 0;
+	cache_node *node;
+
+	hash = (const uint32_t *)oid->id;
+
+	for (i = 0; !found && i < GIT_CACHE_OPENADR; ++i) {
+		pos = hash[i] & cache->size_mask;
+		node = &cache->nodes[pos];
+
+		git_mutex_lock(&node->lock);
+		{
+			if (cached_obj_compare(node->ptr, oid) == 0) {
+				cached_obj_incref(node->ptr);
+				node->lru = ++cache->lru_count;
+				found = 1;
+			}
+		}
+		git_mutex_unlock(&node->lock);
+	}
+
+
+	return found ? node->ptr : NULL;
+}
+
+void *git_cache_try_store(git_cache *cache, void *entry)
+{
+	cache_node *nodes[GIT_CACHE_OPENADR], *lru_node;
+	const uint32_t *hash;
+	const git_oid *oid;
+	size_t i, stored = 0;
+
+	oid = &((git_cached_obj*)entry)->oid;
+	hash = (const uint32_t *)oid->id;
+
+	/* increase the refcount on this object, because
+	 * the cache now owns it */
+	cached_obj_incref(entry);
+
+	for (i = 0; i < GIT_CACHE_OPENADR; ++i) {
+		size_t pos = hash[i] & cache->size_mask;
+
+		nodes[i] = &cache->nodes[pos];
+		git_mutex_lock(&nodes[i]->lock);
+	}
+
+	lru_node = nodes[0];
+
+	for (i = 0; !stored && entry && i < GIT_CACHE_OPENADR; ++i) {
+
+		if (nodes[i]->ptr == NULL) {
+			nodes[i]->ptr = entry;
+			nodes[i]->lru = ++cache->lru_count;
+			stored = 1;
+		} else if (cached_obj_compare(nodes[i]->ptr, oid) == 0) {
+			cached_obj_decref(entry, cache->free_obj);
+			entry = nodes[i]->ptr;
+			stored = 1;
+		}
+
+		if (nodes[i]->lru < lru_node->lru)
+			lru_node = nodes[i];
+	}
+
+	if (!stored) {
+		void *old_entry = lru_node->ptr;
+		assert(old_entry);
+
+		cached_obj_decref(old_entry, cache->free_obj);
+		lru_node->ptr = entry;
+		lru_node->lru = ++cache->lru_count;
+	}
+
+	/* increase the refcount again, because we are
+	 * returning it to the user */
+	cached_obj_incref(entry);
+
+	for (i = 0; i < GIT_CACHE_OPENADR; ++i)
+		git_mutex_unlock(&nodes[i]->lock);
+
+	return entry;
+}
diff --git a/src/cache.h b/src/cache.h
new file mode 100644
index 000000000..9f525e68c
--- /dev/null
+++ b/src/cache.h
@@ -0,0 +1,38 @@
+#ifndef INCLUDE_cache_h__
+#define INCLUDE_cache_h__
+
+#include "git2/common.h"
+#include "git2/oid.h"
+#include "git2/odb.h"
+
+#include "thread-utils.h"
+
+typedef void (*git_cached_obj_freeptr)(void *);
+
+typedef struct {
+	git_oid oid;
+	git_atomic refcount;
+} git_cached_obj;
+
+typedef struct {
+	git_cached_obj *ptr;
+	git_mutex lock;
+	unsigned int lru;
+} cache_node;
+
+typedef struct {
+	cache_node *nodes;
+
+	unsigned int lru_count;
+	size_t size_mask;
+	git_cached_obj_freeptr free_obj;
+} git_cache;
+
+
+void git_cache_init(git_cache *cache, size_t size, git_cached_obj_freeptr free_ptr);
+void git_cache_free(git_cache *cache);
+
+void *git_cache_try_store(git_cache *cache, void *entry);
+void *git_cache_get(git_cache *cache, const git_oid *oid);
+
+#endif
diff --git a/src/common.h b/src/common.h
index 723085a2b..5ad878e26 100644
--- a/src/common.h
+++ b/src/common.h
@@ -31,18 +31,21 @@
 # include <windows.h>
 # include "msvc-compat.h"
 # include "mingw-compat.h"
-# include "win32/pthread.h"
+# ifdef GIT_THREADS
+#  include "win32/pthread.h"
+#endif
 
 # define snprintf _snprintf
 
 typedef SSIZE_T ssize_t;
 
 #else
-
 # include <unistd.h>
 # include <arpa/inet.h>
-# include <pthread.h>
 
+# ifdef GIT_THREADS
+#  include <pthread.h>
+# endif
 #endif
 
 #include "git2/common.h"
diff --git a/src/thread-utils.h b/src/thread-utils.h
index e8372e731..1cf0e3407 100644
--- a/src/thread-utils.h
+++ b/src/thread-utils.h
@@ -2,6 +2,19 @@
 #define INCLUDE_thread_utils_h__
 
 
+
+/* Common operations even if threading has been disabled */
+typedef struct {
+	volatile int val;
+} git_atomic;
+
+static inline void git_atomic_set(git_atomic *a, int val)
+{
+	a->val = val;
+}
+
+#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_kill(thread) pthread_cancel(thread)
@@ -15,13 +28,70 @@
 #define git_mutex_unlock(a) pthread_mutex_unlock(a)
 #define git_mutex_free(a)   pthread_mutex_destroy(a)
 
+/* Pthreads condition vars -- disabled by now */
+#define git_cond unsigned int //pthread_cond_t
+#define git_cond_init(c, a)	(void)0		//pthread_cond_init(c, a)
+#define git_cond_free(c) (void)0		//pthread_cond_destroy(c)
+#define git_cond_wait(c, l)	(void)0		//pthread_cond_wait(c, l)
+#define git_cond_signal(c)	(void)0		//pthread_cond_signal(c)
+#define git_cond_broadcast(c) (void)0	//pthread_cond_broadcast(c)
+
+static inline int git_atomic_inc(git_atomic *a)
+{
+#ifdef __GNUC__
+	return __sync_add_and_fetch(&a->val, 1);
+#elif defined(_MSC_VER)
+	return InterlockedIncrement(&a->val);
+#else
+#	error "Unsupported architecture for atomic operations"
+#endif
+}
+
+static inline int git_atomic_dec(git_atomic *a)
+{
+#ifdef __GNUC__
+	return __sync_sub_and_fetch(&a->val, 1);
+#elif defined(_MSC_VER)
+	return InterlockedDecrement(&a->val);
+#else
+#	error "Unsupported architecture for atomic operations"
+#endif
+}
+
+#else
+
+#define git_thread unsigned int
+#define git_thread_create(thread, attr, start_routine, arg) (void)0
+#define git_thread_kill(thread) (void)0
+#define git_thread_exit(status) (void)0
+#define git_thread_join(id, status) (void)0
+
+/* Pthreads Mutex */
+#define git_mutex unsigned int
+#define git_mutex_init(a) (void)0
+#define git_mutex_lock(a) (void)0
+#define git_mutex_unlock(a) (void)0
+#define git_mutex_free(a) (void)0
+
 /* Pthreads condition vars */
-#define git_cond pthread_cond_t
-#define git_cond_init(c, a)	pthread_cond_init(c, a)
-#define git_cond_free(c)		pthread_cond_destroy(c)
-#define git_cond_wait(c, l)	pthread_cond_wait(c, l)
-#define git_cond_signal(c)		pthread_cond_signal(c)
-#define git_cond_broadcast(c)	pthread_cond_broadcast(c)
+#define git_cond unsigned int
+#define git_cond_init(c, a)	(void)0
+#define git_cond_free(c) (void)0
+#define git_cond_wait(c, l)	(void)0
+#define git_cond_signal(c) (void)0
+#define git_cond_broadcast(c) (void)0
+
+static inline int git_atomic_inc(git_atomic *a)
+{
+	return ++a->val;
+}
+
+static inline int git_atomic_dec(git_atomic *a)
+{
+	return --a->val;
+}
+
+#endif
 
 extern int git_online_cpus(void);
 
diff --git a/src/win32/pthread.c b/src/win32/pthread.c
index fffff81df..f47364a76 100644
--- a/src/win32/pthread.c
+++ b/src/win32/pthread.c
@@ -36,32 +36,6 @@ int pthread_create(pthread_t *GIT_RESTRICT thread,
 	return *thread ? GIT_SUCCESS : GIT_EOSERR;
 }
 
-int pthread_cond_signal(pthread_cond_t *cond)
-{
-    WakeConditionVariable(cond);
-    return 0;
-}
-
-int pthread_cond_wait(pthread_cond_t *GIT_RESTRICT cond,
-                      pthread_mutex_t *GIT_RESTRICT mutex)
-{
-    int ret;
-    ret = SleepConditionVariableCS(cond, mutex, INFINITE);
-    return -(!ret);
-}
-
-int pthread_mutex_lock(pthread_mutex_t *mutex)
-{
-    EnterCriticalSection(mutex);
-    return 0;
-}
-
-int pthread_mutex_unlock(pthread_mutex_t *mutex)
-{
-    LeaveCriticalSection(mutex);
-    return 0;
-}
-
 int pthread_join(pthread_t thread, void **value_ptr)
 {
     int ret;
@@ -71,9 +45,11 @@ int pthread_join(pthread_t thread, void **value_ptr)
     return -(!!ret);
 }
 
-int pthread_cond_broadcast(pthread_cond_t *cond)
+int pthread_mutex_init(pthread_mutex_t *GIT_RESTRICT mutex,
+                       const pthread_mutexattr_t *GIT_RESTRICT GIT_UNUSED(mutexattr))
 {
-    WakeAllConditionVariable(cond);
+	GIT_UNUSED_ARG(mutexattr);
+    InitializeCriticalSection(mutex);
     return 0;
 }
 
@@ -84,25 +60,15 @@ int pthread_mutex_destroy(pthread_mutex_t *mutex)
     return -(!ret);
 }
 
-int pthread_cond_destroy(pthread_cond_t *GIT_UNUSED(cond))
-{
-	GIT_UNUSED_ARG(cond);
-    return 0;
-}
-
-int pthread_cond_init(pthread_cond_t *GIT_RESTRICT cond,
-                      const pthread_condattr_t *GIT_RESTRICT GIT_UNUSED(condattr))
+int pthread_mutex_lock(pthread_mutex_t *mutex)
 {
-	GIT_UNUSED_ARG(condattr);
-    InitializeConditionVariable(cond);
+    EnterCriticalSection(mutex);
     return 0;
 }
 
-int pthread_mutex_init(pthread_mutex_t *GIT_RESTRICT mutex,
-                       const pthread_mutexattr_t *GIT_RESTRICT GIT_UNUSED(mutexattr))
+int pthread_mutex_unlock(pthread_mutex_t *mutex)
 {
-	GIT_UNUSED_ARG(mutexattr);
-    InitializeCriticalSection(mutex);
+    LeaveCriticalSection(mutex);
     return 0;
 }
 
diff --git a/src/win32/pthread.h b/src/win32/pthread.h
index ff694e303..10949f1eb 100644
--- a/src/win32/pthread.h
+++ b/src/win32/pthread.h
@@ -40,7 +40,6 @@ typedef int pthread_mutexattr_t;
 typedef int pthread_condattr_t;
 typedef int pthread_attr_t;
 typedef CRITICAL_SECTION pthread_mutex_t;
-typedef CONDITION_VARIABLE pthread_cond_t;
 typedef HANDLE pthread_t;
 
 #define PTHREAD_MUTEX_INITIALIZER {(void*)-1};
@@ -56,12 +55,6 @@ int pthread_mutex_destroy(pthread_mutex_t *);
 int pthread_mutex_lock(pthread_mutex_t *);
 int pthread_mutex_unlock(pthread_mutex_t *);
 
-int pthread_cond_init(pthread_cond_t *GIT_RESTRICT, const pthread_condattr_t *GIT_RESTRICT);
-int pthread_cond_destroy(pthread_cond_t *);
-int pthread_cond_broadcast(pthread_cond_t *);
-int pthread_cond_signal(pthread_cond_t *);
-int pthread_cond_wait(pthread_cond_t *GIT_RESTRICT, pthread_mutex_t *GIT_RESTRICT);
-
 int pthread_num_processors_np(void);
 
-#endif
\ No newline at end of file
+#endif