[PATCH 1/2] Make xmalloc and xrealloc thread-safe

[PATCH 1/2] Make xmalloc and xrealloc thread-safe

[Fredrik Kuivinen]

Signed-off-by: Fredrik Kuivinen <frekui@gmail.com>
---

 builtin/grep.c         |    2 +-
 builtin/pack-objects.c |    4 ++--
 git-compat-util.h      |    8 ++++++++
 preload-index.c        |    2 +-
 run-command.c          |    3 ++-
 wrapper.c              |   22 ++++++++++++++++------
 6 files changed, 30 insertions(+), 11 deletions(-)

diff --git a/builtin/grep.c b/builtin/grep.c
index 9d30ddb..78b0bf4 100644
--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -236,7 +236,7 @@ static void start_threads(struct grep_opt *opt)
 		struct grep_opt *o = grep_opt_dup(opt);
 		o->output = strbuf_out;
 		compile_grep_patterns(o);
-		err = pthread_create(&threads[i], NULL, run, o);
+		err = xpthread_create(&threads[i], NULL, run, o);
 
 		if (err)
 			die("grep: failed to create thread: %s",
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 9780258..022b6a8 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -1651,8 +1651,8 @@ static void ll_find_deltas(struct object_entry **list, unsigned list_size,
 			continue;
 		pthread_mutex_init(&p[i].mutex, NULL);
 		pthread_cond_init(&p[i].cond, NULL);
-		ret = pthread_create(&p[i].thread, NULL,
-				     threaded_find_deltas, &p[i]);
+		ret = xpthread_create(&p[i].thread, NULL,
+				      threaded_find_deltas, &p[i]);
 		if (ret)
 			die("unable to create thread: %s", strerror(ret));
 		active_threads++;
diff --git a/git-compat-util.h b/git-compat-util.h
index aebd9cd..fe10901 100644
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -140,6 +140,10 @@ extern char *gitbasename(char *);
 #include <openssl/err.h>
 #endif
 
+#ifndef NO_PTHREADS
+#include <pthread.h>
+#endif
+
 /* On most systems <limits.h> would have given us this, but
  * not on some systems (e.g. GNU/Hurd).
  */
@@ -356,6 +360,10 @@ static inline void *gitmempcpy(void *dest, const void *src, size_t n)
 
 extern void release_pack_memory(size_t, int);
 
+#ifndef NO_PTHREADS
+extern int xpthread_create(pthread_t *thread, const pthread_attr_t *attr,
+			   void *(*start_routine)(void*), void *arg);
+#endif
 extern char *xstrdup(const char *str);
 extern void *xmalloc(size_t size);
 extern void *xmallocz(size_t size);
diff --git a/preload-index.c b/preload-index.c
index e3d0bda..250bb0b 100644
--- a/preload-index.c
+++ b/preload-index.c
@@ -86,7 +86,7 @@ static void preload_index(struct index_state *index, const char **pathspec)
 		p->offset = offset;
 		p->nr = work;
 		offset += work;
-		if (pthread_create(&p->pthread, NULL, preload_thread, p))
+		if (xpthread_create(&p->pthread, NULL, preload_thread, p))
 			die("unable to create threaded lstat");
 	}
 	for (i = 0; i < threads; i++) {
diff --git a/run-command.c b/run-command.c
index e996b21..1e4def4 100644
--- a/run-command.c
+++ b/run-command.c
@@ -568,7 +568,8 @@ int start_async(struct async *async)
 	async->proc_in = proc_in;
 	async->proc_out = proc_out;
 	{
-		int err = pthread_create(&async->tid, NULL, run_thread, async);
+		int err = xpthread_create(&async->tid, NULL, run_thread,
+					  async);
 		if (err) {
 			error("cannot create thread: %s", strerror(err));
 			goto error;
diff --git a/wrapper.c b/wrapper.c
index 9c71b21..e7140d1 100644
--- a/wrapper.c
+++ b/wrapper.c
@@ -15,19 +15,29 @@ char *xstrdup(const char *str)
 	return ret;
 }
 
+static int multiple_threads;
+#ifndef NO_PTHREADS
+int xpthread_create(pthread_t *thread, const pthread_attr_t *attr,
+		    void *(*start_routine)(void*), void *arg)
+{
+	multiple_threads = 1;
+	return pthread_create(thread, attr, start_routine, arg);
+}
+#endif
+
 void *xmalloc(size_t size)
 {
 	void *ret = malloc(size);
 	if (!ret && !size)
 		ret = malloc(1);
-	if (!ret) {
+	if (!ret && !multiple_threads) {
 		release_pack_memory(size, -1);
 		ret = malloc(size);
 		if (!ret && !size)
 			ret = malloc(1);
-		if (!ret)
-			die("Out of memory, malloc failed");
 	}
+	if (!ret)
+		die("Out of memory, malloc failed");
 #ifdef XMALLOC_POISON
 	memset(ret, 0xA5, size);
 #endif
@@ -66,14 +76,14 @@ void *xrealloc(void *ptr, size_t size)
 	void *ret = realloc(ptr, size);
 	if (!ret && !size)
 		ret = realloc(ptr, 1);
-	if (!ret) {
+	if (!ret && !multiple_threads) {
 		release_pack_memory(size, -1);
 		ret = realloc(ptr, size);
 		if (!ret && !size)
 			ret = realloc(ptr, 1);
-		if (!ret)
-			die("Out of memory, realloc failed");
 	}
+	if (!ret)
+		die("Out of memory, realloc failed");
 	return ret;
 }
 

[PATCH 2/2] Make sha1_to_hex thread-safe

[Fredrik Kuivinen]

Signed-off-by: Fredrik Kuivinen <frekui@gmail.com>
---

 hex.c |   53 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 53 insertions(+), 0 deletions(-)

diff --git a/hex.c b/hex.c
index bb402fb..fe1d302 100644
--- a/hex.c
+++ b/hex.c
@@ -1,5 +1,9 @@
 #include "cache.h"
 
+#ifndef NO_PTHREADS
+#include <pthread.h>
+#endif
+
 const signed char hexval_table[256] = {
 	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 00-07 */
 	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 08-0f */
@@ -48,6 +52,7 @@ int get_sha1_hex(const char *hex, unsigned char *sha1)
 	return 0;
 }
 
+#ifdef NO_PTHREADS
 char *sha1_to_hex(const unsigned char *sha1)
 {
 	static int bufno;
@@ -65,3 +70,51 @@ char *sha1_to_hex(const unsigned char *sha1)
 
 	return buffer;
 }
+#else
+static pthread_once_t sha1_to_hex_once = PTHREAD_ONCE_INIT;
+static pthread_key_t sha1_to_hex_key;
+
+static void sha1_to_hex_init(void)
+{
+	int err = pthread_key_create(&sha1_to_hex_key, free);
+	if (err)
+		die("pthread_key_create failed: %s", strerror(err));
+}
+
+struct sha1_to_hex_buf
+{
+	int no;
+	char hex[4][50];
+};
+
+char *sha1_to_hex(const unsigned char *sha1)
+{
+	static const char hex[] = "0123456789abcdef";
+	struct sha1_to_hex_buf *hexbuf;
+	int i;
+	char *buffer, *buf;
+
+	pthread_once(&sha1_to_hex_once, sha1_to_hex_init);
+
+	hexbuf = pthread_getspecific(sha1_to_hex_key);
+	if (!hexbuf) {
+		int err;
+		hexbuf = xmalloc(sizeof(struct sha1_to_hex_buf));
+		hexbuf->no = 0;
+		err = pthread_setspecific(sha1_to_hex_key, hexbuf);
+		if (err)
+			die("pthread_getspecific failed: %s", strerror(err));
+	}
+
+	buffer = hexbuf->hex[3 & ++hexbuf->no], buf = buffer;
+
+	for (i = 0; i < 20; i++) {
+		unsigned int val = *sha1++;
+		*buf++ = hex[val >> 4];
+		*buf++ = hex[val & 0xf];
+	}
+	*buf = '\0';
+
+	return buffer;
+}
+#endif

Re: [PATCH 1/2] Make xmalloc and xrealloc thread-safe

[Shawn O. Pearce]

Fredrik Kuivinen <frekui@gmail.com> wrote:
> +static int multiple_threads;
> +#ifndef NO_PTHREADS
> +int xpthread_create(pthread_t *thread, const pthread_attr_t *attr,
> +		    void *(*start_routine)(void*), void *arg)
> +{
> +	multiple_threads = 1;
> +	return pthread_create(thread, attr, start_routine, arg);
> +}
> +#endif
> +
>  void *xmalloc(size_t size)
>  {
>  	void *ret = malloc(size);
>  	if (!ret && !size)
>  		ret = malloc(1);
> -	if (!ret) {
> +	if (!ret && !multiple_threads) {
>  		release_pack_memory(size, -1);

So by "make thread safe" you really mean "disable release of
least-frequently used pack windows once any thread starts".

If that is what we are doing, disabling the release of pack windows
when malloc fails, why can't we do that all of the time?

-- 
Shawn.

Re: [PATCH 2/2] Make sha1_to_hex thread-safe

[Johannes Sixt]

As I said in my previous mail, this is not necessary.

In particular...

On Dienstag, 23. März 2010, Fredrik Kuivinen wrote:
> +static pthread_once_t sha1_to_hex_once = PTHREAD_ONCE_INIT;

... please give us a break: Don't force us to pile missing pthreads features 
in our Windows layer.

-- Hannes

Re: [PATCH 1/2] Make xmalloc and xrealloc thread-safe

[Fredrik Kuivinen]

On Tue, Mar 23, 2010 at 19:43, Shawn O. Pearce <spearce@spearce.org> wrote:
> Fredrik Kuivinen <frekui@gmail.com> wrote:
>> +static int multiple_threads;
>> +#ifndef NO_PTHREADS
>> +int xpthread_create(pthread_t *thread, const pthread_attr_t *attr,
>> +                 void *(*start_routine)(void*), void *arg)
>> +{
>> +     multiple_threads = 1;
>> +     return pthread_create(thread, attr, start_routine, arg);
>> +}
>> +#endif
>> +
>>  void *xmalloc(size_t size)
>>  {
>>       void *ret = malloc(size);
>>       if (!ret && !size)
>>               ret = malloc(1);
>> -     if (!ret) {
>> +     if (!ret && !multiple_threads) {
>>               release_pack_memory(size, -1);
>
> So by "make thread safe" you really mean "disable release of
> least-frequently used pack windows once any thread starts".

Yes.

> If that is what we are doing, disabling the release of pack windows
> when malloc fails, why can't we do that all of the time?

The idea was that most git programs are single threaded, so they can
still benefit from releasing the pack windows when they are low on
memory.

- Fredrik

Re: [PATCH 1/2] Make xmalloc and xrealloc thread-safe

[Nicolas Pitre]

On Tue, 23 Mar 2010, Fredrik Kuivinen wrote:

> On Tue, Mar 23, 2010 at 19:43, Shawn O. Pearce <spearce@spearce.org> wrote:
> > If that is what we are doing, disabling the release of pack windows
> > when malloc fails, why can't we do that all of the time?
> 
> The idea was that most git programs are single threaded, so they can
> still benefit from releasing the pack windows when they are low on
> memory.

This is bobus. The Git program using the most memory is probably 
pack-objects and it is threaded.  Most single-threaded programs don't 
use close to as much memory.


Nicolas

Re: [PATCH 1/2] Make xmalloc and xrealloc thread-safe

[Fredrik Kuivinen]

On Wed, Mar 24, 2010 at 00:50, Nicolas Pitre <nico@fluxnic.net> wrote:
> On Tue, 23 Mar 2010, Fredrik Kuivinen wrote:
>
>> On Tue, Mar 23, 2010 at 19:43, Shawn O. Pearce <spearce@spearce.org> wrote:
>> > If that is what we are doing, disabling the release of pack windows
>> > when malloc fails, why can't we do that all of the time?
>>
>> The idea was that most git programs are single threaded, so they can
>> still benefit from releasing the pack windows when they are low on
>> memory.
>
> This is bobus. The Git program using the most memory is probably
> pack-objects and it is threaded.  Most single-threaded programs don't
> use close to as much memory.

Ok, you are right. But xmalloc/xrealloc cannot be used in multiple
threads simultaneously without some serialization.

For example, I think there are some potential race conditions in the
pack-objects code. In the threaded code we have the following call
chains leading to xcalloc, xmalloc, and xrealloc:

find_deltas -> xcalloc
find_deltas -> do_compress -> xmalloc
find_deltas -> try_delta -> xrealloc
find_deltas -> try_delta -> read_sha1_file -> ... -> xmalloc  (called
with read_lock held, but it can still race with the other calls)

As far as I can see there is no serialization between these calls.

- Fredrik

Re: [PATCH 1/2] Make xmalloc and xrealloc thread-safe

[Nicolas Pitre]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1435 bytes --]

On Wed, 24 Mar 2010, Fredrik Kuivinen wrote:

> On Wed, Mar 24, 2010 at 00:50, Nicolas Pitre <nico@fluxnic.net> wrote:
> > On Tue, 23 Mar 2010, Fredrik Kuivinen wrote:
> >
> >> On Tue, Mar 23, 2010 at 19:43, Shawn O. Pearce <spearce@spearce.org> wrote:
> >> > If that is what we are doing, disabling the release of pack windows
> >> > when malloc fails, why can't we do that all of the time?
> >>
> >> The idea was that most git programs are single threaded, so they can
> >> still benefit from releasing the pack windows when they are low on
> >> memory.
> >
> > This is bobus. The Git program using the most memory is probably
> > pack-objects and it is threaded.  Most single-threaded programs don't
> > use close to as much memory.
> 
> Ok, you are right. But xmalloc/xrealloc cannot be used in multiple
> threads simultaneously without some serialization.
> 
> For example, I think there are some potential race conditions in the
> pack-objects code. In the threaded code we have the following call
> chains leading to xcalloc, xmalloc, and xrealloc:
> 
> find_deltas -> xcalloc
> find_deltas -> do_compress -> xmalloc
> find_deltas -> try_delta -> xrealloc
> find_deltas -> try_delta -> read_sha1_file -> ... -> xmalloc  (called
> with read_lock held, but it can still race with the other calls)
> 
> As far as I can see there is no serialization between these calls.

True.  We already have a problem.  This is nasty.


Nicolas

Re: [PATCH 1/2] Make xmalloc and xrealloc thread-safe

[Shawn Pearce]

On Wed, Mar 24, 2010 at 10:53 AM, Nicolas Pitre <nico@fluxnic.net> wrote:
> On Wed, 24 Mar 2010, Fredrik Kuivinen wrote:
>
>> On Wed, Mar 24, 2010 at 00:50, Nicolas Pitre <nico@fluxnic.net> wrote:
>> > On Tue, 23 Mar 2010, Fredrik Kuivinen wrote:
>> >
>> >> On Tue, Mar 23, 2010 at 19:43, Shawn O. Pearce <spearce@spearce.org> wrote:
>> >> > If that is what we are doing, disabling the release of pack windows
>> >> > when malloc fails, why can't we do that all of the time?
>> >>
>> >> The idea was that most git programs are single threaded, so they can
>> >> still benefit from releasing the pack windows when they are low on
>> >> memory.
>> >
>> > This is bobus. The Git program using the most memory is probably
>> > pack-objects and it is threaded.  Most single-threaded programs don't
>> > use close to as much memory.
>>
>> Ok, you are right. But xmalloc/xrealloc cannot be used in multiple
>> threads simultaneously without some serialization.
>>
>> For example, I think there are some potential race conditions in the
>> pack-objects code. In the threaded code we have the following call
>> chains leading to xcalloc, xmalloc, and xrealloc:
>>
>> find_deltas -> xcalloc
>> find_deltas -> do_compress -> xmalloc
>> find_deltas -> try_delta -> xrealloc
>> find_deltas -> try_delta -> read_sha1_file -> ... -> xmalloc  (called
>> with read_lock held, but it can still race with the other calls)
>>
>> As far as I can see there is no serialization between these calls.
>
> True.  We already have a problem.  This is nasty.

The easy solution is probably to remove the use of xmalloc from
find_deltas code path.  But then we run into hard failures when we
can't get the memory we need, there isn't a way to recover from a
malloc() failure deep within read_sha1_file for example.  The current
solution is the best we can do, try to ditch pack windows and hope
that releases sufficient virtual memory space that a second malloc()
attempt can succeed by increasing heap.

We could use a mutex during the malloc failure code-path of xmalloc,
to ensure only one thread goes through that pack window cleanup at a
time.  But that will still mess with the main thread which doesn't
really want to acquire mutexes during object access as it uses the
existing pack windows.

I thought pack-objects did all object access from the main thread and
only delta searches on the worker threads?  If that is true, maybe we
can have the worker threads signal the main thread on malloc failure
to release pack windows, and then wait for that signal to be
acknowledged before they attempt to retry the malloc.  This means the
main thread would need to periodically test that condition as its
dispatching batches of objects to the workers.

Ugly.

-- 
Shawn.

Re: [PATCH 1/2] Make xmalloc and xrealloc thread-safe

[Junio C Hamano]

Shawn Pearce <spearce@spearce.org> writes:

> I thought pack-objects did all object access from the main thread and
> only delta searches on the worker threads?

Hmm, you lost me.  try_delta() is the one that reads the data out of
either loose object or from an existing pack for comparison lazily, and
that is what each worker thread runs repeatedly in find_deltas()...

Re: [PATCH 1/2] Make xmalloc and xrealloc thread-safe

[Nicolas Pitre]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 3752 bytes --]

On Wed, 24 Mar 2010, Shawn Pearce wrote:

> On Wed, Mar 24, 2010 at 10:53 AM, Nicolas Pitre <nico@fluxnic.net> wrote:
> > On Wed, 24 Mar 2010, Fredrik Kuivinen wrote:
> >
> >> On Wed, Mar 24, 2010 at 00:50, Nicolas Pitre <nico@fluxnic.net> wrote:
> >> > On Tue, 23 Mar 2010, Fredrik Kuivinen wrote:
> >> >
> >> >> On Tue, Mar 23, 2010 at 19:43, Shawn O. Pearce <spearce@spearce.org> wrote:
> >> >> > If that is what we are doing, disabling the release of pack windows
> >> >> > when malloc fails, why can't we do that all of the time?
> >> >>
> >> >> The idea was that most git programs are single threaded, so they can
> >> >> still benefit from releasing the pack windows when they are low on
> >> >> memory.
> >> >
> >> > This is bobus. The Git program using the most memory is probably
> >> > pack-objects and it is threaded.  Most single-threaded programs don't
> >> > use close to as much memory.
> >>
> >> Ok, you are right. But xmalloc/xrealloc cannot be used in multiple
> >> threads simultaneously without some serialization.
> >>
> >> For example, I think there are some potential race conditions in the
> >> pack-objects code. In the threaded code we have the following call
> >> chains leading to xcalloc, xmalloc, and xrealloc:
> >>
> >> find_deltas -> xcalloc
> >> find_deltas -> do_compress -> xmalloc
> >> find_deltas -> try_delta -> xrealloc
> >> find_deltas -> try_delta -> read_sha1_file -> ... -> xmalloc  (called
> >> with read_lock held, but it can still race with the other calls)
> >>
> >> As far as I can see there is no serialization between these calls.
> >
> > True.  We already have a problem.  This is nasty.
> 
> The easy solution is probably to remove the use of xmalloc from
> find_deltas code path.  But then we run into hard failures when we
> can't get the memory we need, there isn't a way to recover from a
> malloc() failure deep within read_sha1_file for example.

The read_sha1_file path is not the problem -- it is always protected 
against concurrency with a mutex.

It is more about do_compress() called on line 1476 of pack-objects.c for 
example.


> The current solution is the best we can do, try to ditch pack windows 
> and hope that releases sufficient virtual memory space that a second 
> malloc() attempt can succeed by increasing heap.
> 
> We could use a mutex during the malloc failure code-path of xmalloc,
> to ensure only one thread goes through that pack window cleanup at a
> time.  But that will still mess with the main thread which doesn't
> really want to acquire mutexes during object access as it uses the
> existing pack windows.

Right.

> I thought pack-objects did all object access from the main thread and
> only delta searches on the worker threads?

No.  Each thread is responsible for grabbing its own data set.

> If that is true, maybe we
> can have the worker threads signal the main thread on malloc failure
> to release pack windows, and then wait for that signal to be
> acknowledged before they attempt to retry the malloc.  This means the
> main thread would need to periodically test that condition as its
> dispatching batches of objects to the workers.
> 
> Ugly.

Indeed.

The real solution, of course, would be to have pack window manipulations 
protected by a mutex of its own.  This, plus another mutex for the delta 
base cache, and then read_sha1_file() could almost be reentrant.

Another solution could be for xmalloc() to use a function pointer for 
the method to use on malloc error path, which would default to a 
function calling release_pack_memory(size, -1).  Then pack-objects.c 
would override the default with its own to acquire the read_mutex around 
the call to release_pack_memory().  That is probably the easiest 
solution for now.


Nicolas

Re: [PATCH 1/2] Make xmalloc and xrealloc thread-safe

[Shawn Pearce]

On Wed, Mar 24, 2010 at 11:54 AM, Nicolas Pitre <nico@fluxnic.net> wrote:
> Another solution could be for xmalloc() to use a function pointer for
> the method to use on malloc error path, which would default to a
> function calling release_pack_memory(size, -1).  Then pack-objects.c
> would override the default with its own to acquire the read_mutex around
> the call to release_pack_memory().  That is probably the easiest
> solution for now.

Yea, that sounds like the most reasonable solution right now.

-- 
Shawn.

[PATCH] Make xmalloc and xrealloc thread-safe

[Nicolas Pitre]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 4298 bytes --]

By providing a hook for the routine responsible for trying to free some 
memory on malloc failure, we can ensure that the  called routine is
protected by the appropriate locks when threads are in play.

The obvious offender here was pack-objects which was calling xmalloc()
within threads while release_pack_memory() is not thread safe.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
---

On Wed, 24 Mar 2010, Shawn Pearce wrote:

> On Wed, Mar 24, 2010 at 11:54 AM, Nicolas Pitre <nico@fluxnic.net> wrote:
> > Another solution could be for xmalloc() to use a function pointer for
> > the method to use on malloc error path, which would default to a
> > function calling release_pack_memory(size, -1).  Then pack-objects.c
> > would override the default with its own to acquire the read_mutex around
> > the call to release_pack_memory().  That is probably the easiest
> > solution for now.
> 
> Yea, that sounds like the most reasonable solution right now.

So here it is.

Note: there was a dubious usage of fd when calling release_pack_memory() 
in xmmap() which is now removed.

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 9780258..65f797f 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -1522,6 +1522,13 @@ static void find_deltas(struct object_entry **list, unsigned *list_size,
 
 #ifndef NO_PTHREADS
 
+static void try_to_free_from_threads(size_t size)
+{
+	read_lock();
+	release_pack_memory(size, -1);
+	read_unlock();
+}
+
 /*
  * The main thread waits on the condition that (at least) one of the workers
  * has stopped working (which is indicated in the .working member of
@@ -1556,10 +1563,12 @@ static void init_threaded_search(void)
 	pthread_mutex_init(&cache_mutex, NULL);
 	pthread_mutex_init(&progress_mutex, NULL);
 	pthread_cond_init(&progress_cond, NULL);
+	set_try_to_free_routine(try_to_free_from_threads);
 }
 
 static void cleanup_threaded_search(void)
 {
+	set_try_to_free_routine(NULL);
 	pthread_cond_destroy(&progress_cond);
 	pthread_mutex_destroy(&read_mutex);
 	pthread_mutex_destroy(&cache_mutex);
diff --git a/git-compat-util.h b/git-compat-util.h
index aebd9cd..53ab5aa 100644
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -356,6 +356,8 @@ static inline void *gitmempcpy(void *dest, const void *src, size_t n)
 
 extern void release_pack_memory(size_t, int);
 
+extern void set_try_to_free_routine(void (*routine)(size_t));
+
 extern char *xstrdup(const char *str);
 extern void *xmalloc(size_t size);
 extern void *xmallocz(size_t size);
diff --git a/wrapper.c b/wrapper.c
index 9c71b21..8a4f3f2 100644
--- a/wrapper.c
+++ b/wrapper.c
@@ -3,11 +3,23 @@
  */
 #include "cache.h"
 
+static void try_to_free_builtin(size_t size)
+{
+	release_pack_memory(size, -1);
+}
+
+static void (*try_to_free_routine)(size_t size) = try_to_free_builtin;
+
+void set_try_to_free_routine(void (*routine)(size_t))
+{
+	try_to_free_routine = (routine) ? routine : try_to_free_builtin;
+}
+
 char *xstrdup(const char *str)
 {
 	char *ret = strdup(str);
 	if (!ret) {
-		release_pack_memory(strlen(str) + 1, -1);
+		try_to_free_routine(strlen(str) + 1);
 		ret = strdup(str);
 		if (!ret)
 			die("Out of memory, strdup failed");
@@ -21,7 +33,7 @@ void *xmalloc(size_t size)
 	if (!ret && !size)
 		ret = malloc(1);
 	if (!ret) {
-		release_pack_memory(size, -1);
+		try_to_free_routine(size);
 		ret = malloc(size);
 		if (!ret && !size)
 			ret = malloc(1);
@@ -67,7 +79,7 @@ void *xrealloc(void *ptr, size_t size)
 	if (!ret && !size)
 		ret = realloc(ptr, 1);
 	if (!ret) {
-		release_pack_memory(size, -1);
+		try_to_free_routine(size);
 		ret = realloc(ptr, size);
 		if (!ret && !size)
 			ret = realloc(ptr, 1);
@@ -83,7 +95,7 @@ void *xcalloc(size_t nmemb, size_t size)
 	if (!ret && (!nmemb || !size))
 		ret = calloc(1, 1);
 	if (!ret) {
-		release_pack_memory(nmemb * size, -1);
+		try_to_free_routine(nmemb * size);
 		ret = calloc(nmemb, size);
 		if (!ret && (!nmemb || !size))
 			ret = calloc(1, 1);
@@ -100,7 +112,7 @@ void *xmmap(void *start, size_t length,
 	if (ret == MAP_FAILED) {
 		if (!length)
 			return NULL;
-		release_pack_memory(length, fd);
+		try_to_free_routine(length);
 		ret = mmap(start, length, prot, flags, fd, offset);
 		if (ret == MAP_FAILED)
 			die_errno("Out of memory? mmap failed");

Re: [PATCH] Make xmalloc and xrealloc thread-safe

[Shawn O. Pearce]

Nicolas Pitre <nico@fluxnic.net> wrote:
> Note: there was a dubious usage of fd when calling release_pack_memory() 
> in xmmap() which is now removed.
...
> @@ -100,7 +112,7 @@ void *xmmap(void *start, size_t length,
>  	if (ret == MAP_FAILED) {
>  		if (!length)
>  			return NULL;
> -		release_pack_memory(length, fd);
> +		try_to_free_routine(length);

This isn't dubious!  The fd passed here is to prevent the pack
release code from closing this fd right before we try to mmap it.
Its an actual bug fix that I had to write years ago, check the
history of that section of code...  :-)

-- 
Shawn.

Re: [PATCH] Make xmalloc and xrealloc thread-safe

[Nicolas Pitre]

On Wed, 24 Mar 2010, Shawn O. Pearce wrote:

> Nicolas Pitre <nico@fluxnic.net> wrote:
> > Note: there was a dubious usage of fd when calling release_pack_memory() 
> > in xmmap() which is now removed.
> ...
> > @@ -100,7 +112,7 @@ void *xmmap(void *start, size_t length,
> >  	if (ret == MAP_FAILED) {
> >  		if (!length)
> >  			return NULL;
> > -		release_pack_memory(length, fd);
> > +		try_to_free_routine(length);
> 
> This isn't dubious!  The fd passed here is to prevent the pack
> release code from closing this fd right before we try to mmap it.
> Its an actual bug fix that I had to write years ago, check the
> history of that section of code...  :-)

Argh.  My bad.  I somehow thought that fd was the actual pack to free 
when specified.  Let's drop the very last hunk of the patch then.  
xmmap() is certainly not going to be invoked concurrently to the rest of 
sha1_file.c in a separate thread.

Junio: I suppose you don't need me to resend?


Nicolas

Re: [PATCH] Make xmalloc and xrealloc thread-safe

[Junio C Hamano]

Nicolas Pitre <nico@fluxnic.net> writes:

> On Wed, 24 Mar 2010, Shawn O. Pearce wrote:
>
>> Nicolas Pitre <nico@fluxnic.net> wrote:
>> > Note: there was a dubious usage of fd when calling release_pack_memory() 
>> > in xmmap() which is now removed.
>> ...
>> > @@ -100,7 +112,7 @@ void *xmmap(void *start, size_t length,
>> >  	if (ret == MAP_FAILED) {
>> >  		if (!length)
>> >  			return NULL;
>> > -		release_pack_memory(length, fd);
>> > +		try_to_free_routine(length);
>> 
>> This isn't dubious!  The fd passed here is to prevent the pack
>> release code from closing this fd right before we try to mmap it.
>> Its an actual bug fix that I had to write years ago, check the
>> history of that section of code...  :-)
>
> Argh.  My bad.  I somehow thought that fd was the actual pack to free 
> when specified.  Let's drop the very last hunk of the patch then.  
> xmmap() is certainly not going to be invoked concurrently to the rest of 
> sha1_file.c in a separate thread.
>
> Junio: I suppose you don't need me to resend?

Will just drop the last hunk.  Thanks, both.

Re: [PATCH] Make xmalloc and xrealloc thread-safe

[Junio C Hamano]

"Shawn O. Pearce" <spearce@spearce.org> writes:

>> @@ -100,7 +112,7 @@ void *xmmap(void *start, size_t length,
>>  	if (ret == MAP_FAILED) {
>>  		if (!length)
>>  			return NULL;
>> -		release_pack_memory(length, fd);
>> +		try_to_free_routine(length);
>
> This isn't dubious!  The fd passed here is to prevent the pack release
> code from closing this fd right before we try to mmap it.  Its an actual
> bug fix that I had to write years ago, check the history of that section
> of code...  :-)

A tangent.

I thought that it incidentally might be a good example for the "line-mode"
log that has been discussed recently to follow the history of this code,
but this turns out to be too easy:

$ git blame -C -L'/^void \*xmmap/,/^}/' wrapper.c

directly gives you the answer.  d1efefa4 explains why this passes fd
rather well.

Re: [PATCH] Make xmalloc and xrealloc thread-safe

[Fredrik Kuivinen]

On Wed, Mar 24, 2010 at 21:22, Nicolas Pitre <nico@fluxnic.net> wrote:
> By providing a hook for the routine responsible for trying to free some
> memory on malloc failure, we can ensure that the  called routine is
> protected by the appropriate locks when threads are in play.
>
> The obvious offender here was pack-objects which was calling xmalloc()
> within threads while release_pack_memory() is not thread safe.
>
> Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
> ---
>
> On Wed, 24 Mar 2010, Shawn Pearce wrote:
>
>> On Wed, Mar 24, 2010 at 11:54 AM, Nicolas Pitre <nico@fluxnic.net> wrote:
>> > Another solution could be for xmalloc() to use a function pointer for
>> > the method to use on malloc error path, which would default to a
>> > function calling release_pack_memory(size, -1).  Then pack-objects.c
>> > would override the default with its own to acquire the read_mutex around
>> > the call to release_pack_memory().  That is probably the easiest
>> > solution for now.
>>
>> Yea, that sounds like the most reasonable solution right now.
>
> So here it is.
>
> Note: there was a dubious usage of fd when calling release_pack_memory()
> in xmmap() which is now removed.
>
> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
> index 9780258..65f797f 100644
> --- a/builtin/pack-objects.c
> +++ b/builtin/pack-objects.c
> @@ -1522,6 +1522,13 @@ static void find_deltas(struct object_entry **list, unsigned *list_size,
>
>  #ifndef NO_PTHREADS
>
> +static void try_to_free_from_threads(size_t size)
> +{
> +       read_lock();
> +       release_pack_memory(size, -1);
> +       read_unlock();
> +}
> +

Will this really work in all cases? In the find_deltas -> try_delta ->
read_sha1_file -> ... -> xmalloc call path, the mutex is already
locked when we get to xmalloc. As the mutex is of the default type
(NULL is passed as the mutex attribute argument to
pthread_mutex_init), it is undefined behaviour to lock the mutex again
(see http://www.opengroup.org/onlinepubs/007908799/xsh/pthread_mutexattr_gettype.html
)

I just realised that builtin/grep.c also needs a fix for its use of xmalloc.

- Fredrik

Re: [PATCH] Make xmalloc and xrealloc thread-safe

[Nicolas Pitre]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 497 bytes --]

On Sat, 27 Mar 2010, Fredrik Kuivinen wrote:

> On Wed, Mar 24, 2010 at 21:22, Nicolas Pitre <nico@fluxnic.net> wrote:
> > +static void try_to_free_from_threads(size_t size)
> > +{
> > +       read_lock();
> > +       release_pack_memory(size, -1);
> > +       read_unlock();
> > +}
> > +
> 
> Will this really work in all cases? In the find_deltas -> try_delta ->
> read_sha1_file -> ... -> xmalloc call path, the mutex is already
> locked when we get to xmalloc.

You're right.  Damn.


Nicolas

Re: [PATCH] Make xmalloc and xrealloc thread-safe

[Fredrik Kuivinen]

On Sat, Mar 27, 2010 at 19:59, Nicolas Pitre <nico@fluxnic.net> wrote:
> On Sat, 27 Mar 2010, Fredrik Kuivinen wrote:
>
>> On Wed, Mar 24, 2010 at 21:22, Nicolas Pitre <nico@fluxnic.net> wrote:
>> > +static void try_to_free_from_threads(size_t size)
>> > +{
>> > +       read_lock();
>> > +       release_pack_memory(size, -1);
>> > +       read_unlock();
>> > +}
>> > +
>>
>> Will this really work in all cases? In the find_deltas -> try_delta ->
>> read_sha1_file -> ... -> xmalloc call path, the mutex is already
>> locked when we get to xmalloc.
>
> You're right.  Damn.

A simple fix is to make it a recursive mutex instead. This will work
with a minimal change in win32 as well as the CRITICAL_SECTION type is
recursive.

I guess the downside is that the locking potentially gets slightly slower.


- Fredrik

[PATCH v2] Make xmalloc and xrealloc thread-safe

[Nicolas Pitre]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 4820 bytes --]

By providing a hook for the routine responsible for trying to free some
memory on malloc failure, we can ensure that the  called routine is
protected by the appropriate locks when threads are in play.

The obvious offender here was pack-objects which was calling xmalloc()
within threads while release_pack_memory() is not thread safe.

To avoid a deadlock if try_to_free_from_threads() is called while
read_lock is already locked within the same thread (may happen through
the read_sha1_file() path), a simple mutex ownership is added. This 
could have been handled automatically with the PTHREAD_MUTEX_RECURSIVE 
type but the Windows pthread emulation would get much more complex.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
---

On Sat, 27 Mar 2010, Fredrik Kuivinen wrote:

> > +static void try_to_free_from_threads(size_t size)
> > +{
> > +       read_lock();
> > +       release_pack_memory(size, -1);
> > +       read_unlock();
> > +}
> > +
> 
> Will this really work in all cases? In the find_deltas -> try_delta ->
> read_sha1_file -> ... -> xmalloc call path, the mutex is already
> locked when we get to xmalloc.

So here's a fixed version.

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 9780258..d3ac41f 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -1211,8 +1211,17 @@ static int delta_cacheable(unsigned long src_size, unsigned long trg_size,
 #ifndef NO_PTHREADS
 
 static pthread_mutex_t read_mutex;
-#define read_lock()		pthread_mutex_lock(&read_mutex)
-#define read_unlock()		pthread_mutex_unlock(&read_mutex)
+static pthread_t read_mutex_owner;
+#define read_lock() \
+	do { \
+		pthread_mutex_lock(&read_mutex); \
+		read_mutex_owner = pthread_self(); \
+	} while (0)
+#define read_unlock() \
+	do { \
+		memset(&read_mutex_owner, 0, sizeof(read_mutex_owner)); \
+		pthread_mutex_unlock(&read_mutex); \
+	} while (0)
 
 static pthread_mutex_t cache_mutex;
 #define cache_lock()		pthread_mutex_lock(&cache_mutex)
@@ -1522,6 +1531,16 @@ static void find_deltas(struct object_entry **list, unsigned *list_size,
 
 #ifndef NO_PTHREADS
 
+static void try_to_free_from_threads(size_t size)
+{
+	int self = pthread_equal(read_mutex_owner, pthread_self());
+	if (!self)
+		read_lock();
+	release_pack_memory(size, -1);
+	if (!self)
+		read_unlock();
+}
+
 /*
  * The main thread waits on the condition that (at least) one of the workers
  * has stopped working (which is indicated in the .working member of
@@ -1556,10 +1575,12 @@ static void init_threaded_search(void)
 	pthread_mutex_init(&cache_mutex, NULL);
 	pthread_mutex_init(&progress_mutex, NULL);
 	pthread_cond_init(&progress_cond, NULL);
+	set_try_to_free_routine(try_to_free_from_threads);
 }
 
 static void cleanup_threaded_search(void)
 {
+	set_try_to_free_routine(NULL);
 	pthread_cond_destroy(&progress_cond);
 	pthread_mutex_destroy(&read_mutex);
 	pthread_mutex_destroy(&cache_mutex);
diff --git a/git-compat-util.h b/git-compat-util.h
index b56c297..4ee8f86 100644
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -357,6 +357,8 @@ static inline void *gitmempcpy(void *dest, const void *src, size_t n)
 
 extern void release_pack_memory(size_t, int);
 
+extern void set_try_to_free_routine(void (*routine)(size_t));
+
 extern char *xstrdup(const char *str);
 extern void *xmalloc(size_t size);
 extern void *xmallocz(size_t size);
diff --git a/wrapper.c b/wrapper.c
index 10a6750..58201b6 100644
--- a/wrapper.c
+++ b/wrapper.c
@@ -3,11 +3,23 @@
  */
 #include "cache.h"
 
+static void try_to_free_builtin(size_t size)
+{
+	release_pack_memory(size, -1);
+}
+
+static void (*try_to_free_routine)(size_t size) = try_to_free_builtin;
+
+void set_try_to_free_routine(void (*routine)(size_t))
+{
+	try_to_free_routine = (routine) ? routine : try_to_free_builtin;
+}
+
 char *xstrdup(const char *str)
 {
 	char *ret = strdup(str);
 	if (!ret) {
-		release_pack_memory(strlen(str) + 1, -1);
+		try_to_free_routine(strlen(str) + 1);
 		ret = strdup(str);
 		if (!ret)
 			die("Out of memory, strdup failed");
@@ -21,7 +33,7 @@ void *xmalloc(size_t size)
 	if (!ret && !size)
 		ret = malloc(1);
 	if (!ret) {
-		release_pack_memory(size, -1);
+		try_to_free_routine(size);
 		ret = malloc(size);
 		if (!ret && !size)
 			ret = malloc(1);
@@ -67,7 +79,7 @@ void *xrealloc(void *ptr, size_t size)
 	if (!ret && !size)
 		ret = realloc(ptr, 1);
 	if (!ret) {
-		release_pack_memory(size, -1);
+		try_to_free_routine(size);
 		ret = realloc(ptr, size);
 		if (!ret && !size)
 			ret = realloc(ptr, 1);
@@ -83,7 +95,7 @@ void *xcalloc(size_t nmemb, size_t size)
 	if (!ret && (!nmemb || !size))
 		ret = calloc(1, 1);
 	if (!ret) {
-		release_pack_memory(nmemb * size, -1);
+		try_to_free_routine(nmemb * size);
 		ret = calloc(nmemb, size);
 		if (!ret && (!nmemb || !size))
 			ret = calloc(1, 1);

Re: [PATCH v2] Make xmalloc and xrealloc thread-safe

[Shawn O. Pearce]

Nicolas Pitre <nico@fluxnic.net> wrote:
> To avoid a deadlock if try_to_free_from_threads() is called while
> read_lock is already locked within the same thread (may happen through
> the read_sha1_file() path), a simple mutex ownership is added. This 
> could have been handled automatically with the PTHREAD_MUTEX_RECURSIVE 
> type but the Windows pthread emulation would get much more complex.
...
> +static void try_to_free_from_threads(size_t size)
> +{
> +	int self = pthread_equal(read_mutex_owner, pthread_self());
> +	if (!self)
> +		read_lock();
> +	release_pack_memory(size, -1);
> +	if (!self)
> +		read_unlock();
> +}

Is there any concern that a partially unset read_mutex_owner might
look like the current thread's identity?

That is, memset() can be setting the bytes one by one.  If the lock
is being released we might observe the current owner as ourselves
if we see only part of that release, and our identity is the same
as another thread, only with the lower-address bytes unset.

-- 
Shawn.

Re: [PATCH v2] Make xmalloc and xrealloc thread-safe

[Nicolas Pitre]

On Tue, 6 Apr 2010, Shawn O. Pearce wrote:

> Nicolas Pitre <nico@fluxnic.net> wrote:
> > To avoid a deadlock if try_to_free_from_threads() is called while
> > read_lock is already locked within the same thread (may happen through
> > the read_sha1_file() path), a simple mutex ownership is added. This 
> > could have been handled automatically with the PTHREAD_MUTEX_RECURSIVE 
> > type but the Windows pthread emulation would get much more complex.
> ...
> > +static void try_to_free_from_threads(size_t size)
> > +{
> > +	int self = pthread_equal(read_mutex_owner, pthread_self());
> > +	if (!self)
> > +		read_lock();
> > +	release_pack_memory(size, -1);
> > +	if (!self)
> > +		read_unlock();
> > +}
> 
> Is there any concern that a partially unset read_mutex_owner might
> look like the current thread's identity?
> 
> That is, memset() can be setting the bytes one by one.  If the lock
> is being released we might observe the current owner as ourselves
> if we see only part of that release, and our identity is the same
> as another thread, only with the lower-address bytes unset.

In practice memset() will optimize the memory access by using words and 
no bytes.  But in theory this is not guaranteed.  The solution for this 
would be to have yet another mutex just to protect the read_mutex 
hownership information modifications in order to make it atomic to 
potential readers.  That is becoming ugly for a feature (the freeing of 
pack data) that is not supposed to be the common case.


Nicolas

Re: [PATCH v2] Make xmalloc and xrealloc thread-safe

[Junio C Hamano]

"Shawn O. Pearce" <spearce@spearce.org> writes:

>> +static void try_to_free_from_threads(size_t size)
>> +{
>> +	int self = pthread_equal(read_mutex_owner, pthread_self());
>> +	if (!self)
>> +		read_lock();
>> +	release_pack_memory(size, -1);
>> +	if (!self)
>> +		read_unlock();
>> +}
>
> Is there any concern that a partially unset read_mutex_owner might
> look like the current thread's identity?
>
> That is, memset() can be setting the bytes one by one.  If the lock
> is being released we might observe the current owner as ourselves
> if we see only part of that release, and our identity is the same
> as another thread, only with the lower-address bytes unset.

Yuck.  I hope that it doesn't mean we need another mutex to protect the
owner data.

Re: [PATCH v2] Make xmalloc and xrealloc thread-safe

[Shawn Pearce]

On Tue, Apr 6, 2010 at 9:51 PM, Nicolas Pitre <nico@fluxnic.net> wrote:
> On Tue, 6 Apr 2010, Shawn O. Pearce wrote:
>> Nicolas Pitre <nico@fluxnic.net> wrote:
>> > To avoid a deadlock if try_to_free_from_threads() is called while
>> > read_lock is already locked within the same thread (may happen through
>> > the read_sha1_file() path), a simple mutex ownership is added. This
>> > could have been handled automatically with the PTHREAD_MUTEX_RECURSIVE
>> > type but the Windows pthread emulation would get much more complex.
>> ...
>> > +static void try_to_free_from_threads(size_t size)
>> > +{
>> > +   int self = pthread_equal(read_mutex_owner, pthread_self());
>> > +   if (!self)
>> > +           read_lock();
>> > +   release_pack_memory(size, -1);
>> > +   if (!self)
>> > +           read_unlock();
>> > +}
>>
>> Is there any concern that a partially unset read_mutex_owner might
>> look like the current thread's identity?
>>
>> That is, memset() can be setting the bytes one by one.  If the lock
>> is being released we might observe the current owner as ourselves
>> if we see only part of that release, and our identity is the same
>> as another thread, only with the lower-address bytes unset.
>
> In practice memset() will optimize the memory access by using words and
> no bytes.  But in theory this is not guaranteed.  The solution for this
> would be to have yet another mutex just to protect the read_mutex
> hownership information modifications in order to make it atomic to
> potential readers.  That is becoming ugly for a feature (the freeing of
> pack data) that is not supposed to be the common case.

Multi-threaded programming is hard.  Its never easy to get it right.
We had really excellent reasons for avoiding multiple threads in the
early days of Git.  We still have those excellent reasons, but we have
been pushing more and more into these async threads to support
windows, and now its making us realize we never really thought about
this stuff very much.

You mentioned avoiding a recursive mutex only because windows
emulation doesn't have support for it.  But that's exactly what we
need here.  Shouldn't windows have a recursive mutex object that can
just be used inside of the emulation layer when we really need a
recursive mutex?

-- 
Shawn.

Re: [PATCH v2] Make xmalloc and xrealloc thread-safe

[Nicolas Pitre]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2104 bytes --]

On Wed, 7 Apr 2010, Shawn Pearce wrote:

> On Tue, Apr 6, 2010 at 9:51 PM, Nicolas Pitre <nico@fluxnic.net> wrote:
> > In practice memset() will optimize the memory access by using words and
> > no bytes.  But in theory this is not guaranteed.  The solution for this
> > would be to have yet another mutex just to protect the read_mutex
> > hownership information modifications in order to make it atomic to
> > potential readers.  That is becoming ugly for a feature (the freeing of
> > pack data) that is not supposed to be the common case.
> 
> Multi-threaded programming is hard.  Its never easy to get it right.

Indeed.  But in this case what makes it harder is the willingness to 
stick to standard APIs.

> We had really excellent reasons for avoiding multiple threads in the
> early days of Git.  We still have those excellent reasons, but we have
> been pushing more and more into these async threads to support
> windows, and now its making us realize we never really thought about
> this stuff very much.

Well, pack-objects was "broken" even without Windows in the picture.  
What I'm trying to fix here is not Windows specific (although the thread 
API limitations are).

> You mentioned avoiding a recursive mutex only because windows
> emulation doesn't have support for it.  But that's exactly what we
> need here.  Shouldn't windows have a recursive mutex object that can
> just be used inside of the emulation layer when we really need a
> recursive mutex?

Maybe.  That would in fact just mean pushing the double mutex issue into 
the pthread emulation instead of having it outside it.  This would 
impact performances for all mutexes although only one instance of them 
currently require a recursive behavior.

Yet, the memset() issue comes up only because pthread_t is meant to be 
an opaque type.  The only information we would need here is the actual 
thread ID as returned by gettid() on Linux or GetCurrentThreadId() on 
Windows, and then the read_mutex_owner could be a simple atomically 
modifiable integer.  But what about other pthread-capable non Linux 
systems?


Nicolas

Re: [PATCH v2] Make xmalloc and xrealloc thread-safe

[Shawn Pearce]

On Wed, Apr 7, 2010 at 6:17 AM, Nicolas Pitre <nico@fluxnic.net> wrote:
> Maybe.  That would in fact just mean pushing the double mutex issue into
> the pthread emulation instead of having it outside it.  This would
> impact performances for all mutexes although only one instance of them
> currently require a recursive behavior.

But we know when the mutex is created whether or not it needs
recursive support.  So in the Windows emulation we may need to
allocate two mutexes for each pthread_mutex_t storage-wise, but we
don't necessarily need to use that owner thread mutex on every
lock/unlock request, do we?

> Yet, the memset() issue comes up only because pthread_t is meant to be
> an opaque type.  The only information we would need here is the actual
> thread ID as returned by gettid() on Linux or GetCurrentThreadId() on
> Windows, and then the read_mutex_owner could be a simple atomically
> modifiable integer.  But what about other pthread-capable non Linux
> systems?

Indeed.  If Windows threads are atomic words, then actually you don't
need that double mutex in the emulation layer, and can instead use the
atomic word to determine ownership.  Which makes this entire debate
somewhat moot, doesn't it?

Use a standard recursive pthread mutex, and implement recursive
support in the emulation layer using the atomic word holding a
GetCurrentThreadId() result.  We don't need to worry about how
pthread_t is stored on any particular system, the thread library will
do it for us.

-- 
Shawn.

Re: [PATCH v2] Make xmalloc and xrealloc thread-safe

[Fredrik Kuivinen]

On Wed, Apr 07, 2010 at 09:17:04AM -0400, Nicolas Pitre wrote:
> On Wed, 7 Apr 2010, Shawn Pearce wrote:
> > You mentioned avoiding a recursive mutex only because windows
> > emulation doesn't have support for it.  But that's exactly what we
> > need here.  Shouldn't windows have a recursive mutex object that can
> > just be used inside of the emulation layer when we really need a
> > recursive mutex?
> 
> Maybe.  That would in fact just mean pushing the double mutex issue into 
> the pthread emulation instead of having it outside it.  This would 
> impact performances for all mutexes although only one instance of them 
> currently require a recursive behavior.

As I mentioned in another mail in this thread, our mutex
implementation on WIN32 already is recursive. It is implemented on top
of the CRITICAL_SECTION type, which is recursive. See
http://msdn.microsoft.com/en-us/library/ms682530%28VS.85%29.aspx

We only need something like the following (on top of Nico's previous
patch). Warning: It hasn't even been compile tested on WIN32.

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 65f797f..19e42cf 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -1559,7 +1559,7 @@ static pthread_cond_t progress_cond;
  */
 static void init_threaded_search(void)
 {
-	pthread_mutex_init(&read_mutex, NULL);
+	init_recursive_mutex(&read_mutex);
 	pthread_mutex_init(&cache_mutex, NULL);
 	pthread_mutex_init(&progress_mutex, NULL);
 	pthread_cond_init(&progress_cond, NULL);
diff --git a/thread-utils.c b/thread-utils.c
index 4f9c829..3c8d817 100644
--- a/thread-utils.c
+++ b/thread-utils.c
@@ -1,4 +1,5 @@
 #include "cache.h"
+#include <pthread.h>
 
 #if defined(hpux) || defined(__hpux) || defined(_hpux)
 #  include <sys/pstat.h>
@@ -43,3 +44,24 @@ int online_cpus(void)
 
 	return 1;
 }
+
+int init_recursive_mutex(pthread_mutex_t *m)
+{
+#ifdef _WIN32
+	/* The mutexes in the WIN32 pthreads emulation layer are
+	 * recursive, so we don't have to do anything extra here. */
+	return pthread_mutex_init(m, NULL);
+#else
+	pthread_mutexattr_t a;
+	int ret;
+	if (pthread_mutexattr_init(&a))
+		die("pthread_mutexattr_init failed: %s", strerror(errno));
+
+	if (pthread_mutexattr_settype(&a, PTHREAD_MUTEX_RECURSIVE))
+		die("pthread_mutexattr_settype failed: %s", strerror(errno));
+
+	ret = pthread_mutex_init(m, &a);
+	pthread_mutexattr_destroy(&a);
+	return ret;
+#endif
+}
diff --git a/thread-utils.h b/thread-utils.h
index cce4b77..1727a03 100644
--- a/thread-utils.h
+++ b/thread-utils.h
@@ -2,5 +2,6 @@
 #define THREAD_COMPAT_H
 
 extern int online_cpus(void);
+extern int init_recursive_mutex(pthread_mutex_t*);
 
 #endif /* THREAD_COMPAT_H */

Re: [PATCH v2] Make xmalloc and xrealloc thread-safe

[Nicolas Pitre]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 768 bytes --]

On Wed, 7 Apr 2010, Shawn Pearce wrote:

> On Wed, Apr 7, 2010 at 6:17 AM, Nicolas Pitre <nico@fluxnic.net> wrote:
> > Yet, the memset() issue comes up only because pthread_t is meant to be
> > an opaque type.  The only information we would need here is the actual
> > thread ID as returned by gettid() on Linux or GetCurrentThreadId() on
> > Windows, and then the read_mutex_owner could be a simple atomically
> > modifiable integer.  But what about other pthread-capable non Linux
> > systems?
> 
> Indeed.  If Windows threads are atomic words, then actually you don't
> need that double mutex in the emulation layer, and can instead use the
> atomic word to determine ownership.  Which makes this entire debate
> somewhat moot, doesn't it?

Well, indeed.


Nicolas

Re: [PATCH v2] Make xmalloc and xrealloc thread-safe

[Nicolas Pitre]

On Wed, 7 Apr 2010, Fredrik Kuivinen wrote:

> As I mentioned in another mail in this thread, our mutex
> implementation on WIN32 already is recursive. It is implemented on top
> of the CRITICAL_SECTION type, which is recursive. See
> http://msdn.microsoft.com/en-us/library/ms682530%28VS.85%29.aspx

Ahhhh.  Goodie.

> We only need something like the following (on top of Nico's previous
> patch). Warning: It hasn't even been compile tested on WIN32.
> 
[...]
> diff --git a/thread-utils.c b/thread-utils.c
> index 4f9c829..3c8d817 100644
> --- a/thread-utils.c
> +++ b/thread-utils.c
> @@ -1,4 +1,5 @@
>  #include "cache.h"
> +#include <pthread.h>

This will fail compilation on Windows surely?

>  #if defined(hpux) || defined(__hpux) || defined(_hpux)
>  #  include <sys/pstat.h>
> @@ -43,3 +44,24 @@ int online_cpus(void)
>  
>  	return 1;
>  }
> +
> +int init_recursive_mutex(pthread_mutex_t *m)
> +{
> +#ifdef _WIN32
> +	/* The mutexes in the WIN32 pthreads emulation layer are
> +	 * recursive, so we don't have to do anything extra here. */
> +	return pthread_mutex_init(m, NULL);
> +#else
> +	pthread_mutexattr_t a;
> +	int ret;
> +	if (pthread_mutexattr_init(&a))
> +		die("pthread_mutexattr_init failed: %s", strerror(errno));
> +
> +	if (pthread_mutexattr_settype(&a, PTHREAD_MUTEX_RECURSIVE))
> +		die("pthread_mutexattr_settype failed: %s", strerror(errno));
> +
> +	ret = pthread_mutex_init(m, &a);
> +	pthread_mutexattr_destroy(&a);
> +	return ret;

Are you sure the pthread_mutexattr_t object can be destroyed even if the 
mutex is still in use?  Is the attribute object "attached" to the mutex 
or merely used as a template?


Nicolas

Re: [PATCH v2] Make xmalloc and xrealloc thread-safe

[Sverre Rabbelier]

Heya,

On Wed, Apr 7, 2010 at 09:45, Fredrik Kuivinen <frekui@gmail.com> wrote:
> +               die("pthread_mutexattr_settype failed: %s", strerror(errno));

Can't you just die_errno here?

-- 
Cheers,

Sverre Rabbelier

Re: [PATCH v2] Make xmalloc and xrealloc thread-safe

[Fredrik Kuivinen]

On Wed, Apr 7, 2010 at 17:08, Nicolas Pitre <nico@fluxnic.net> wrote:
> On Wed, 7 Apr 2010, Fredrik Kuivinen wrote:
>> diff --git a/thread-utils.c b/thread-utils.c
>> index 4f9c829..3c8d817 100644
>> --- a/thread-utils.c
>> +++ b/thread-utils.c
>> @@ -1,4 +1,5 @@
>>  #include "cache.h"
>> +#include <pthread.h>
>
> This will fail compilation on Windows surely?

I think it will work. We use "#include <pthread.h>" in builtin/grep.c,
builtin/pack-objects.c, and preload-index.c already.

>>  #if defined(hpux) || defined(__hpux) || defined(_hpux)
>>  #  include <sys/pstat.h>
>> @@ -43,3 +44,24 @@ int online_cpus(void)
>>
>>       return 1;
>>  }
>> +
>> +int init_recursive_mutex(pthread_mutex_t *m)
>> +{
>> +#ifdef _WIN32
>> +     /* The mutexes in the WIN32 pthreads emulation layer are
>> +      * recursive, so we don't have to do anything extra here. */
>> +     return pthread_mutex_init(m, NULL);
>> +#else
>> +     pthread_mutexattr_t a;
>> +     int ret;
>> +     if (pthread_mutexattr_init(&a))
>> +             die("pthread_mutexattr_init failed: %s", strerror(errno));
>> +
>> +     if (pthread_mutexattr_settype(&a, PTHREAD_MUTEX_RECURSIVE))
>> +             die("pthread_mutexattr_settype failed: %s", strerror(errno));
>> +
>> +     ret = pthread_mutex_init(m, &a);
>> +     pthread_mutexattr_destroy(&a);
>> +     return ret;
>
> Are you sure the pthread_mutexattr_t object can be destroyed even if the
> mutex is still in use?  Is the attribute object "attached" to the mutex
> or merely used as a template?

It is safe. See
http://www.opengroup.org/onlinepubs/009695399/functions/pthread_mutexattr_init.html

- Fredrik

Re: [PATCH v2] Make xmalloc and xrealloc thread-safe

[Fredrik Kuivinen]

On Wed, Apr 7, 2010 at 17:27, Sverre Rabbelier <srabbelier@gmail.com> wrote:
> Heya,
>
> On Wed, Apr 7, 2010 at 09:45, Fredrik Kuivinen <frekui@gmail.com> wrote:
>> +               die("pthread_mutexattr_settype failed: %s", strerror(errno));
>
> Can't you just die_errno here?

Ah, yes you are right. Thanks.


- Fredrik

Re: [PATCH v2] Make xmalloc and xrealloc thread-safe

[Junio C Hamano]

Fredrik Kuivinen <frekui@gmail.com> writes:

> As I mentioned in another mail in this thread, our mutex
> implementation on WIN32 already is recursive.

Good ;-)

Re: [PATCH v2] Make xmalloc and xrealloc thread-safe

[Erik Faye-Lund]

On Wed, Apr 7, 2010 at 6:13 PM, Fredrik Kuivinen <frekui@gmail.com> wrote:
> On Wed, Apr 7, 2010 at 17:08, Nicolas Pitre <nico@fluxnic.net> wrote:
>> On Wed, 7 Apr 2010, Fredrik Kuivinen wrote:
>>> diff --git a/thread-utils.c b/thread-utils.c
>>> index 4f9c829..3c8d817 100644
>>> --- a/thread-utils.c
>>> +++ b/thread-utils.c
>>> @@ -1,4 +1,5 @@
>>>  #include "cache.h"
>>> +#include <pthread.h>
>>
>> This will fail compilation on Windows surely?
>
> I think it will work. We use "#include <pthread.h>" in builtin/grep.c,
> builtin/pack-objects.c, and preload-index.c already.
>

Still, isn't this REALLY the kind of stuff that usually goes in
git-compat-util.h? I'm not asking you to change it, I'm just a bit
puzzled that the other pthread-clients did it this way...

-- 
Erik "kusma" Faye-Lund

Re: [PATCH v2] Make xmalloc and xrealloc thread-safe

[Nicolas Pitre]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1820 bytes --]

On Wed, 7 Apr 2010, Fredrik Kuivinen wrote:

> On Wed, Apr 7, 2010 at 17:08, Nicolas Pitre <nico@fluxnic.net> wrote:
> > On Wed, 7 Apr 2010, Fredrik Kuivinen wrote:
> >> diff --git a/thread-utils.c b/thread-utils.c
> >> index 4f9c829..3c8d817 100644
> >> --- a/thread-utils.c
> >> +++ b/thread-utils.c
> >> @@ -1,4 +1,5 @@
> >>  #include "cache.h"
> >> +#include <pthread.h>
> >
> > This will fail compilation on Windows surely?
> 
> I think it will work. We use "#include <pthread.h>" in builtin/grep.c,
> builtin/pack-objects.c, and preload-index.c already.

True indeed.

> >>  #if defined(hpux) || defined(__hpux) || defined(_hpux)
> >>  #  include <sys/pstat.h>
> >> @@ -43,3 +44,24 @@ int online_cpus(void)
> >>
> >>       return 1;
> >>  }
> >> +
> >> +int init_recursive_mutex(pthread_mutex_t *m)
> >> +{
> >> +#ifdef _WIN32
> >> +     /* The mutexes in the WIN32 pthreads emulation layer are
> >> +      * recursive, so we don't have to do anything extra here. */
> >> +     return pthread_mutex_init(m, NULL);
> >> +#else
> >> +     pthread_mutexattr_t a;
> >> +     int ret;
> >> +     if (pthread_mutexattr_init(&a))
> >> +             die("pthread_mutexattr_init failed: %s", strerror(errno));
> >> +
> >> +     if (pthread_mutexattr_settype(&a, PTHREAD_MUTEX_RECURSIVE))
> >> +             die("pthread_mutexattr_settype failed: %s", strerror(errno));
> >> +
> >> +     ret = pthread_mutex_init(m, &a);
> >> +     pthread_mutexattr_destroy(&a);
> >> +     return ret;
> >
> > Are you sure the pthread_mutexattr_t object can be destroyed even if the
> > mutex is still in use?  Is the attribute object "attached" to the mutex
> > or merely used as a template?
> 
> It is safe. See
> http://www.opengroup.org/onlinepubs/009695399/functions/pthread_mutexattr_init.html

OK.  ACK to your patch then.


Nicolas

Re: [PATCH v2] Make xmalloc and xrealloc thread-safe

[Johannes Sixt]

On Mittwoch, 7. April 2010, Fredrik Kuivinen wrote:
> As I mentioned in another mail in this thread, our mutex
> implementation on WIN32 already is recursive. It is implemented on top
> of the CRITICAL_SECTION type, which is recursive. See
> http://msdn.microsoft.com/en-us/library/ms682530%28VS.85%29.aspx

Very true!

> +	if (pthread_mutexattr_settype(&a, PTHREAD_MUTEX_RECURSIVE))

I wonder how many pthreads implementations there are that do not support 
recursive mutexes...

-- Hannes

[PATCH] Thread-safe xmalloc and xrealloc needs a recursive mutex

[Johannes Sixt]

From: Johannes Sixt <j6t@kdbg.org>

The mutex used to protect object access (read_mutex) may need to be
acquired recursively.  Introduce init_recursive_mutex() helper function
in thread-utils.c that constructs a mutex with the PHREAD_MUTEX_RECURSIVE
attribute.

pthread_mutex_init() emulation on Win32 is already recursive as it is
implemented on top of the CRITICAL_SECTION type, which is recursive.

    http://msdn.microsoft.com/en-us/library/ms682530%28VS.85%29.aspx

Add do-nothing compatibility wrappers for pthread_mutexattr* functions.

Initial-version-by: Fredrik Kuivinen <frekui@gmail.com>
Signed-off-by: Johannes Sixt <j6t@kdbg.org>
---
Am 4/7/2010 16:45, schrieb Fredrik Kuivinen:
> We only need something like the following (on top of Nico's previous
> patch). Warning: It hasn't even been compile tested on WIN32.

Unfortunately, it doesn't build. This patch replaces the tip of
nd/malloc-threading.

BTW, your uses of strerror(errno) in init_recursive_mutex() were wrong
(pthread functions do not set errno), but it is better in any case to
avoid die() in this function.

-- Hannes

 builtin-grep.c         |    2 +-
 builtin-pack-objects.c |    4 ++--
 compat/win32/pthread.h |    8 +++++++-
 thread-utils.c         |   16 ++++++++++++++++
 thread-utils.h         |    1 +
 5 files changed, 27 insertions(+), 4 deletions(-)

diff --git a/builtin-grep.c b/builtin-grep.c
index 371db0a..52137f4 100644
--- a/builtin-grep.c
+++ b/builtin-grep.c
@@ -16,8 +16,8 @@
 #include "quote.h"
 
 #ifndef NO_PTHREADS
-#include "thread-utils.h"
 #include <pthread.h>
+#include "thread-utils.h"
 #endif
 
 static char const * const grep_usage[] = {
diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c
index 0ecc198..26fc7cd 100644
--- a/builtin-pack-objects.c
+++ b/builtin-pack-objects.c
@@ -18,8 +18,8 @@
 #include "refs.h"
 
 #ifndef NO_PTHREADS
-#include "thread-utils.h"
 #include <pthread.h>
+#include "thread-utils.h"
 #endif
 
 static const char pack_usage[] =
@@ -1586,7 +1586,7 @@ static pthread_cond_t progress_cond;
  */
 static void init_threaded_search(void)
 {
-	pthread_mutex_init(&read_mutex, NULL);
+	init_recursive_mutex(&read_mutex);
 	pthread_mutex_init(&cache_mutex, NULL);
 	pthread_mutex_init(&progress_mutex, NULL);
 	pthread_cond_init(&progress_cond, NULL);
diff --git a/compat/win32/pthread.h b/compat/win32/pthread.h
index c72f100..a45f8d6 100644
--- a/compat/win32/pthread.h
+++ b/compat/win32/pthread.h
@@ -18,11 +18,17 @@
  */
 #define pthread_mutex_t CRITICAL_SECTION
 
-#define pthread_mutex_init(a,b) InitializeCriticalSection((a))
+#define pthread_mutex_init(a,b) (InitializeCriticalSection((a)), 0)
 #define pthread_mutex_destroy(a) DeleteCriticalSection((a))
 #define pthread_mutex_lock EnterCriticalSection
 #define pthread_mutex_unlock LeaveCriticalSection
 
+typedef int pthread_mutexattr_t;
+#define pthread_mutexattr_init(a) (*(a) = 0)
+#define pthread_mutexattr_destroy(a) do {} while (0)
+#define pthread_mutexattr_settype(a, t) 0
+#define PTHREAD_MUTEX_RECURSIVE 0
+
 /*
  * Implement simple condition variable for Windows threads, based on ACE
  * implementation.
diff --git a/thread-utils.c b/thread-utils.c
index 4f9c829..589f838 100644
--- a/thread-utils.c
+++ b/thread-utils.c
@@ -1,4 +1,5 @@
 #include "cache.h"
+#include <pthread.h>
 
 #if defined(hpux) || defined(__hpux) || defined(_hpux)
 #  include <sys/pstat.h>
@@ -43,3 +44,18 @@ int online_cpus(void)
 
 	return 1;
 }
+
+int init_recursive_mutex(pthread_mutex_t *m)
+{
+	pthread_mutexattr_t a;
+	int ret;
+
+	ret = pthread_mutexattr_init(&a);
+	if (!ret) {
+		ret = pthread_mutexattr_settype(&a, PTHREAD_MUTEX_RECURSIVE);
+		if (!ret)
+			ret = pthread_mutex_init(m, &a);
+		pthread_mutexattr_destroy(&a);
+	}
+	return ret;
+}
diff --git a/thread-utils.h b/thread-utils.h
index cce4b77..1727a03 100644
--- a/thread-utils.h
+++ b/thread-utils.h
@@ -2,5 +2,6 @@
 #define THREAD_COMPAT_H
 
 extern int online_cpus(void);
+extern int init_recursive_mutex(pthread_mutex_t*);
 
 #endif /* THREAD_COMPAT_H */
-- 
1.7.0.3.1356.g75346

Re: [PATCH] Thread-safe xmalloc and xrealloc needs a recursive mutex

[Fredrik Kuivinen]

On Thu, Apr 8, 2010 at 09:15, Johannes Sixt <j.sixt@viscovery.net> wrote:
> From: Johannes Sixt <j6t@kdbg.org>
>
> The mutex used to protect object access (read_mutex) may need to be
> acquired recursively.  Introduce init_recursive_mutex() helper function
> in thread-utils.c that constructs a mutex with the PHREAD_MUTEX_RECURSIVE
> attribute.
>
> pthread_mutex_init() emulation on Win32 is already recursive as it is
> implemented on top of the CRITICAL_SECTION type, which is recursive.
>
>    http://msdn.microsoft.com/en-us/library/ms682530%28VS.85%29.aspx
>
> Add do-nothing compatibility wrappers for pthread_mutexattr* functions.
>
> Initial-version-by: Fredrik Kuivinen <frekui@gmail.com>
> Signed-off-by: Johannes Sixt <j6t@kdbg.org>
> ---
> Am 4/7/2010 16:45, schrieb Fredrik Kuivinen:
>> We only need something like the following (on top of Nico's previous
>> patch). Warning: It hasn't even been compile tested on WIN32.
>
> Unfortunately, it doesn't build. This patch replaces the tip of
> nd/malloc-threading.
>
> BTW, your uses of strerror(errno) in init_recursive_mutex() were wrong
> (pthread functions do not set errno), but it is better in any case to
> avoid die() in this function.

Very true. Thanks.

- Fredrik