patch, 3 partsstring-list: make string_list_sort() reentrant

Use qsort_s() from C11 Annex K to make string_list_sort() safer, in particular when called from parallel threads.

  compat: add qsort_s()
  add QSORT_S
  string-list: use QSORT_S in string_list_sort()

 Makefile          | 10 ++++++++
 compat/qsort_s.c  | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 git-compat-util.h | 11 +++++++++
 string-list.c     | 13 ++++-------
 4 files changed, 95 insertions(+), 8 deletions(-)
 create mode 100644 compat/qsort_s.c

The function qsort_s() was introduced with C11 Annex K; it provides the ability to pass a context pointer to the comparison function, supports the convention of using a NULL pointer for an empty array and performs a few safety checks.

Add an implementation based on compat/qsort.c for platforms that lack a native standards-compliant qsort_s() (i.e. basically everyone). It doesn't perform the full range of possible checks: It uses size_t instead of rsize_t and doesn't check nmemb and size against RSIZE_MAX because we probably don't have the restricted size type defined. For the same reason it returns int instead of errno_t.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 Makefile          | 10 ++++++++
 compat/qsort_s.c  | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 git-compat-util.h |  6 +++++
 3 files changed, 85 insertions(+)
 create mode 100644 compat/qsort_s.c

Am 01.12.2016 um 17:26 schrieb René Scharfe:

And here's the diff for compat/qsort_s.c with copy detection (-C -C):
---
 compat/{qsort.c => qsort_s.c} | 25 ++++++++++++++++---------
 1 file changed, 16 insertions(+), 9 deletions(-)

On Thu, Dec 01, 2016 at 05:26:43PM +0100, René Scharfe wrote:

Hmm. So it sounds like qsort_r(), but with the NULL-is-empty magic. But we already are OK without the latter (and can emulate it easily). Would it make sense to do:

  #if defined(HAVE_QSORT_S)
  /* huzzah, use the system-native qsort_s */

  #elif defined(HAVE_QSORT_R)
  int git_qsort_s(void *b, size_t n, size_t s,
		   int (*cmp)(const void *, const void *, void *), void *ctx)
  {
	if (!n)
		return 0;
	if (!b || !cmp)
		return -1;
	qsort_r(b, n, s, cmp, ctx);
	return 0;
  }

  #else
  /* fallback implementation as your patch does */
  #endif

To make matters more fun, apparently[1] there are multiple variants of qsort_r with different argument orders. _And_ apparently Microsoft defines qsort_s, but it's not quite the same thing. But all of that can be dealt with by having more specific flags (HAVE_GNU_QSORT_R, etc).

It just seems like we should be able to do a better job of using the system qsort in many cases.

-Peff

[1] https://stackoverflow.com/questions/39560773/different-declarations-of-qsort-r-on-mac-and-linux/39561369

Jeff King <peff@peff.net> writes:

If we were to go that route, perhaps we shouldn't have HAVE_QSORT_S so that Microsoft folks won't define it by mistake (instead perhaps call it HAVE_ISO_QSORT_S or something).

I like your suggestion in general. The body of git_qsort_s() on systems without ISO_QSORT_S can do

 - GNU qsort_r() without any change in the parameters, 

 - Microsoft qsort_s() with parameter reordered, or 

 - Apple/BSD qsort_r() with parameter reordered.

and that would cover the major platforms.

Eh, wait. BSD and Microsoft have paramters reordered in the callback comparison function. I suspect that would not fly very well.

On Thu, Dec 01, 2016 at 12:14:42PM -0800, Junio C Hamano wrote:

You can hack around it by passing a wrapper callback that flips the arguments. Since we have a "void *" data pointer, that would point to a struct holding the "real" callback and chaining to the original data pointer.

It does incur the cost of an extra level of indirection for each comparison, though (not just for each qsort call).

You could do it as zero-cost if you were willing to turn the comparison function definition into a macro.

-Peff

Jeff King <peff@peff.net> writes:

Apparently our mails crossed.

Am 01.12.2016 um 21:19 schrieb Jeff King:

AFAIU it went like this:

// FreeBSD 5.0 (2003)
void qsort_r(void *base, size_t nmemb, size_t size,
	void *context,
	int (*compar)(void *context, const void *x, const void *y));

// Microsoft Visual Studio 2005
void qsort_s(void *base, size_t nmemb, size_t size,
	int (*compar)(void *context, const void *x, const void *y),
	void *context);

// glibc 2.8 (2008)
void qsort_r(void *base, size_t nmemb, size_t size,
	int (*compar)(const void *x, const void *y, void *context),
	void *context);

// C11 Annex K (2011)
errno_t qsort_s(void *base, rsize_t nmemb, rsize_t size,
	int (*compar)(const void *x, const void *y, void *context),
	void *context);

Sure, platform-specific implementations can be shorter.

OK.

Yes.

However, for MSys INTERNAL_QSORT is defined for some reason, so the platform's qsort(3) is not used there; I guess the same reason applies to qsort_s(). If it doesn't then an implementation may want to convert a call to the invalid parameter handler (which may show a dialog offering to Retry, Continue or Abort) into a non-zero return value.

Indeed. We'd need a perf test to measure that overhead before we could determine if that's a problem, though.

Ugh. That either requires changing the signature of qsort_s() based on the underlying native function as well, or using a void pointer to pass the comparison function, no? Let's not do that, at least not without a good reason.

René

René Scharfe <l.s.r@web.de> writes:

I agree.  Hopefully it won't be too much cost.

Let's not go there. It may be zero runtime cost, but the cognitive cost for people who need to code the comparison callback using the macro is high.

Junio C Hamano <gitster@pobox.com> writes:

Hmm.  We could do it like this, which may not be too bad.

#if APPLE_QSORT_R
struct apple_qsort_adapter {
	int (*user_cmp)(const void *, const void *, void *);
	void *user_ctx;
}

static int apple_qsort_adapter_cmp(void *ctx, const void *a, const void *b)
{
	struct apple_qsort_adapter *wrapper_ctx = ctx;
	return wrapper_ctx->user_cmp(a, b, wrapper_ctx->user_ctx);
}
#endif

int git_qsort_s(void *b, size_t n, size_t s,
      	   int (*cmp)(const void *, const void *, void *), void *ctx)
{
	if (!n)
		return 0;
	if (!b || !cmp)
		return -1;
#if GNU_QSORT_R
	qsort_r(b, n, s, cmp, ctx);
#elif APPLE_QSORT_R
	{
		struct appple_qsort_adapter a = { cmp, ctx };
		qsort_r(b, n, s, &a, appple_qsort_adapter_cmp);
	}
#endif
      return 0;
}

On Thu, Dec 01, 2016 at 12:22:37PM -0800, Junio C Hamano wrote:

Heh. Exactly, but I was too lazy to write it out in my other email. :)

The no-cost version would be more like:

#ifdef APPLE_QSORT_R #define DECLARE_CMP(func) int func(void *data, const void *va, const void *vb) #else #define DECLARE_CMP(func) int func(const void *va, const void *vb, void *data) #endif

and then:

  DECLARE_CMP(foocmp);
  ...

  DECLARE_CMP(foocmp)
  {
	const struct foo *a = va, *b = vb;
	... etc ...
  }

-Peff

Am 01.12.2016 um 21:22 schrieb Junio C Hamano:

It's kinda cool to have a bespoke compatibility layer for major platforms, but the more I think about it the less I can answer why we would want that. Safety, reliability and performance can't be good reasons -- if our fallback function lacks in these regards then we have to improve it in any case.

Text size could be a valid reason, but the full function only adds a bit more than 2KB to the unstripped git binary.

The flip side is we'd build an ifdef maze that's harder to read and a lot more difficult to test.

What do we get in return for that additional complexity?

Nit: The fallback for non-GNU, non-Apple systems is missing here, but 
the idea is illustrated clearly enough.

On Mon, Dec 12, 2016 at 08:51:14PM +0100, René Scharfe wrote:

There may be cases that we don't want to support because of portability issues. E.g., if your libc has an assembly-optimized qsort() we wouldn't want to replicate that.

I dunno. I am not that opposed to just saying "forget libc qsort, we always use our internal one which is consistent, performant, and safe". But when I suggested something similar for our regex library, I seem to recall there were complaints.

-Peff

Am 12.12.2016 um 20:57 schrieb Jeff King:

Offloading to GPUs might be a better example; I don't know of a libc that does any of that, though (yet).

Well, I'm not sure how comparable they are, but perhaps we can avoid compat code altogether in this case. Patch coming in a new thread.

René

Add the macro QSORT_S, a convenient wrapper for qsort_s() that infers the size of the array elements and dies on error.

Basically all possible errors are programming mistakes (passing NULL as base of a non-empty array, passing NULL as comparison function, out-of-bounds accesses), so terminating the program should be acceptable for most callers.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 git-compat-util.h | 5 +++++
 1 file changed, 5 insertions(+)

Pass the comparison function to cmp_items() via the context parameter of qsort_s() instead of using a global variable. That allows calling string_list_sort() from multiple parallel threads.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 string-list.c | 13 +++++--------
 1 file changed, 5 insertions(+), 8 deletions(-)