{"thread":{"id":"44585","subject":"[PATCH 0/3] string-list: make string_list_sort() reentrant","startedAt":"2016-12-01T16:24:39Z","lastAt":"2016-12-21T09:37:02Z","messageCount":16,"participants":["René Scharfe","Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"306691","messageId":"3083fbf7-d67e-77e4-e05f-94a7e7e15eba@web.de","threadId":"44585","inReplyTo":null,"subject":"[PATCH 0/3] string-list: make string_list_sort() reentrant","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-12-01T16:24:25Z","receivedAt":"2016-12-01T16:24:39Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Use qsort_s() from C11 Annex K to make string_list_sort() safer, in\nparticular when called from parallel threads.\n\n compat: add qsort_s()\n add QSORT_S\n string-list: use QSORT_S in string_list_sort()\n\n Makefile | 10 ++++++++\n compat/qsort_s.c | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++++++\n git-compat-util.h | 11 +++++++++\n string-list.c | 13 ++++-------\n 4 files changed, 95 insertions(+), 8 deletions(-)\n create mode 100644 compat/qsort_s.c\n\n-- \n2.11.0\n\n"},{"id":"306692","messageId":"fc602a66-a06c-203e-b50b-55fd7b258b54@web.de","threadId":"44585","inReplyTo":"3083fbf7-d67e-77e4-e05f-94a7e7e15eba@web.de","subject":"[PATCH 1/3] compat: add qsort_s()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-12-01T16:26:43Z","receivedAt":"2016-12-01T16:27:00Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"The function qsort_s() was introduced with C11 Annex K; it provides the\nability to pass a context pointer to the comparison function, supports\nthe convention of using a NULL pointer for an empty array and performs a\nfew safety checks.\n\nAdd an implementation based on compat/qsort.c for platforms that lack a\nnative standards-compliant qsort_s() (i.e. basically everyone). It\ndoesn't perform the full range of possible checks: It uses size_t\ninstead of rsize_t and doesn't check nmemb and size against RSIZE_MAX\nbecause we probably don't have the restricted size type defined. For\nthe same reason it returns int instead of errno_t.\n\nSigned-off-by: Rene Scharfe \n---\n Makefile | 10 ++++++++\n compat/qsort_s.c | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++++++\n git-compat-util.h | 6 +++++\n 3 files changed, 85 insertions(+)\n create mode 100644 compat/qsort_s.c\n\ndiff --git a/Makefile b/Makefile\nindex f53fcc90d..2245fd95d 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -279,6 +279,9 @@ all::\n # is a simplified version of the merge sort used in glibc. This is\n # recommended if Git triggers O(n^2) behavior in your platform's qsort().\n #\n+# Define HAVE_QSORT_S if your platform provides a qsort_s() that's\n+# compatible with the one described in C11 Annex K.\n+#\n # Define UNRELIABLE_FSTAT if your system's fstat does not return the same\n # information on a not yet closed file that lstat would return for the same\n # file after it was closed.\n@@ -1423,6 +1426,13 @@ ifdef INTERNAL_QSORT\n \tCOMPAT_CFLAGS += -DINTERNAL_QSORT\n \tCOMPAT_OBJS += compat/qsort.o\n endif\n+\n+ifdef HAVE_QSORT_S\n+\tCOMPAT_CFLAGS += -DHAVE_QSORT_S\n+else\n+\tCOMPAT_OBJS += compat/qsort_s.o\n+endif\n+\n ifdef RUNTIME_PREFIX\n \tCOMPAT_CFLAGS += -DRUNTIME_PREFIX\n endif\ndiff --git a/compat/qsort_s.c b/compat/qsort_s.c\nnew file mode 100644\nindex 000000000..52d1f0a73\n--- /dev/null\n+++ b/compat/qsort_s.c\n@@ -0,0 +1,69 @@\n+#include \"../git-compat-util.h\"\n+\n+/*\n+ * A merge sort implementation, simplified from the qsort implementation\n+ * by Mike Haertel, which is a part of the GNU C Library.\n+ * Added context pointer, safety checks and return value.\n+ */\n+\n+static void msort_with_tmp(void *b, size_t n, size_t s,\n+\t\t\t int (*cmp)(const void *, const void *, void *),\n+\t\t\t char *t, void *ctx)\n+{\n+\tchar *tmp;\n+\tchar *b1, *b2;\n+\tsize_t n1, n2;\n+\n+\tif (n <= 1)\n+\t\treturn;\n+\n+\tn1 = n / 2;\n+\tn2 = n - n1;\n+\tb1 = b;\n+\tb2 = (char *)b + (n1 * s);\n+\n+\tmsort_with_tmp(b1, n1, s, cmp, t, ctx);\n+\tmsort_with_tmp(b2, n2, s, cmp, t, ctx);\n+\n+\ttmp = t;\n+\n+\twhile (n1 > 0 && n2 > 0) {\n+\t\tif (cmp(b1, b2, ctx) <= 0) {\n+\t\t\tmemcpy(tmp, b1, s);\n+\t\t\ttmp += s;\n+\t\t\tb1 += s;\n+\t\t\t--n1;\n+\t\t} else {\n+\t\t\tmemcpy(tmp, b2, s);\n+\t\t\ttmp += s;\n+\t\t\tb2 += s;\n+\t\t\t--n2;\n+\t\t}\n+\t}\n+\tif (n1 > 0)\n+\t\tmemcpy(tmp, b1, n1 * s);\n+\tmemcpy(b, t, (n - n2) * s);\n+}\n+\n+int git_qsort_s(void *b, size_t n, size_t s,\n+\t\tint (*cmp)(const void *, const void *, void *), void *ctx)\n+{\n+\tconst size_t size = st_mult(n, s);\n+\tchar buf[1024];\n+\n+\tif (!n)\n+\t\treturn 0;\n+\tif (!b || !cmp)\n+\t\treturn -1;\n+\n+\tif (size < sizeof(buf)) {\n+\t\t/* The temporary array fits on the small on-stack buffer. */\n+\t\tmsort_with_tmp(b, n, s, cmp, buf, ctx);\n+\t} else {\n+\t\t/* It's somewhat large, so malloc it. */\n+\t\tchar *tmp = xmalloc(size);\n+\t\tmsort_with_tmp(b, n, s, cmp, tmp, ctx);\n+\t\tfree(tmp);\n+\t}\n+\treturn 0;\n+}\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 87237b092..d25f0bd4c 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -988,6 +988,12 @@ static inline void sane_qsort(void *base, size_t nmemb, size_t size,\n \t\tqsort(base, nmemb, size, compar);\n }\n \n+#ifndef HAVE_QSORT_S\n+int git_qsort_s(void *base, size_t nmemb, size_t size,\n+\t\tint (*compar)(const void *, const void *, void *), void *ctx);\n+#define qsort_s git_qsort_s\n+#endif\n+\n #ifndef REG_STARTEND\n #error \"Git requires REG_STARTEND support. Compile with NO_REGEX=NeedsStartEnd\"\n #endif\n-- \n2.11.0\n\n"},{"id":"306693","messageId":"d7e9bf45-98ca-4245-7740-ef71f71610aa@web.de","threadId":"44585","inReplyTo":"3083fbf7-d67e-77e4-e05f-94a7e7e15eba@web.de","subject":"[PATCH 2/3] add QSORT_S","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-12-01T16:28:09Z","receivedAt":"2016-12-01T16:28:27Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Add the macro QSORT_S, a convenient wrapper for qsort_s() that infers\nthe size of the array elements and dies on error.\n\nBasically all possible errors are programming mistakes (passing NULL as\nbase of a non-empty array, passing NULL as comparison function,\nout-of-bounds accesses), so terminating the program should be acceptable\nfor most callers.\n\nSigned-off-by: Rene Scharfe \n---\n git-compat-util.h | 5 +++++\n 1 file changed, 5 insertions(+)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex d25f0bd4c..b707dd880 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -994,6 +994,11 @@ int git_qsort_s(void *base, size_t nmemb, size_t size,\n #define qsort_s git_qsort_s\n #endif\n \n+#define QSORT_S(base, n, compar, ctx) do {\t\t\t\\\n+\tif (qsort_s((base), (n), sizeof(*(base)), compar, ctx))\t\\\n+\t\tdie(\"BUG: qsort_s() failed\");\t\t\t\\\n+} while (0)\n+\n #ifndef REG_STARTEND\n #error \"Git requires REG_STARTEND support. Compile with NO_REGEX=NeedsStartEnd\"\n #endif\n-- \n2.11.0\n\n"},{"id":"306694","messageId":"adc18b5e-21f5-2a5f-b788-1181a8d56d3c@web.de","threadId":"44585","inReplyTo":"3083fbf7-d67e-77e4-e05f-94a7e7e15eba@web.de","subject":"[PATCH 3/3] string-list: use QSORT_S in string_list_sort()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-12-01T16:29:05Z","receivedAt":"2016-12-01T16:29:53Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Pass the comparison function to cmp_items() via the context parameter of\nqsort_s() instead of using a global variable. That allows calling\nstring_list_sort() from multiple parallel threads.\n\nSigned-off-by: Rene Scharfe \n---\n string-list.c | 13 +++++--------\n 1 file changed, 5 insertions(+), 8 deletions(-)\n\ndiff --git a/string-list.c b/string-list.c\nindex 8c83cac18..45016ad86 100644\n--- a/string-list.c\n+++ b/string-list.c\n@@ -211,21 +211,18 @@ struct string_list_item *string_list_append(struct string_list *list,\n \t\t\tlist->strdup_strings ? xstrdup(string) : (char *)string);\n }\n \n-/* Yuck */\n-static compare_strings_fn compare_for_qsort;\n-\n-/* Only call this from inside string_list_sort! */\n-static int cmp_items(const void *a, const void *b)\n+static int cmp_items(const void *a, const void *b, void *ctx)\n {\n+\tcompare_strings_fn cmp = ctx;\n \tconst struct string_list_item *one = a;\n \tconst struct string_list_item *two = b;\n-\treturn compare_for_qsort(one->string, two->string);\n+\treturn cmp(one->string, two->string);\n }\n \n void string_list_sort(struct string_list *list)\n {\n-\tcompare_for_qsort = list->cmp ? list->cmp : strcmp;\n-\tQSORT(list->items, list->nr, cmp_items);\n+\tQSORT_S(list->items, list->nr, cmp_items,\n+\t\tlist->cmp ? list->cmp : strcmp);\n }\n \n struct string_list_item *unsorted_string_list_lookup(struct string_list *list,\n-- \n2.11.0\n\n"},{"id":"306695","messageId":"f35e31c6-c9c3-3514-3932-f069b34488e5@web.de","threadId":"44585","inReplyTo":"fc602a66-a06c-203e-b50b-55fd7b258b54@web.de","subject":"Re: [PATCH 1/3] compat: add qsort_s()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-12-01T16:31:45Z","receivedAt":"2016-12-01T16:31:55Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 01.12.2016 um 17:26 schrieb René Scharfe:\n> The function qsort_s() was introduced with C11 Annex K; it provides the\n> ability to pass a context pointer to the comparison function, supports\n> the convention of using a NULL pointer for an empty array and performs a\n> few safety checks.\n> \n> Add an implementation based on compat/qsort.c for platforms that lack a\n> native standards-compliant qsort_s() (i.e. basically everyone). It\n> doesn't perform the full range of possible checks: It uses size_t\n> instead of rsize_t and doesn't check nmemb and size against RSIZE_MAX\n> because we probably don't have the restricted size type defined. For\n> the same reason it returns int instead of errno_t.\n> \n> Signed-off-by: Rene Scharfe \n> ---\n> Makefile | 10 ++++++++\n> compat/qsort_s.c | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++++++\n> git-compat-util.h | 6 +++++\n> 3 files changed, 85 insertions(+)\n> create mode 100644 compat/qsort_s.c\n\nAnd here's the diff for compat/qsort_s.c with copy detection (-C -C):\n---\n compat/{qsort.c => qsort_s.c} | 25 ++++++++++++++++---------\n 1 file changed, 16 insertions(+), 9 deletions(-)\n\ndiff --git a/compat/qsort.c b/compat/qsort_s.c\nsimilarity index 62%\ncopy from compat/qsort.c\ncopy to compat/qsort_s.c\nindex 7d071afb7..52d1f0a73 100644\n--- a/compat/qsort.c\n+++ b/compat/qsort_s.c\n@@ -3,11 +3,12 @@\n /*\n * A merge sort implementation, simplified from the qsort implementation\n * by Mike Haertel, which is a part of the GNU C Library.\n+ * Added context pointer, safety checks and return value.\n */\n \n static void msort_with_tmp(void *b, size_t n, size_t s,\n-\t\t\t int (*cmp)(const void *, const void *),\n-\t\t\t char *t)\n+\t\t\t int (*cmp)(const void *, const void *, void *),\n+\t\t\t char *t, void *ctx)\n {\n \tchar *tmp;\n \tchar *b1, *b2;\n@@ -21,13 +22,13 @@ static void msort_with_tmp(void *b, size_t n, size_t s,\n \tb1 = b;\n \tb2 = (char *)b + (n1 * s);\n \n-\tmsort_with_tmp(b1, n1, s, cmp, t);\n-\tmsort_with_tmp(b2, n2, s, cmp, t);\n+\tmsort_with_tmp(b1, n1, s, cmp, t, ctx);\n+\tmsort_with_tmp(b2, n2, s, cmp, t, ctx);\n \n \ttmp = t;\n \n \twhile (n1 > 0 && n2 > 0) {\n-\t\tif (cmp(b1, b2) <= 0) {\n+\t\tif (cmp(b1, b2, ctx) <= 0) {\n \t\t\tmemcpy(tmp, b1, s);\n \t\t\ttmp += s;\n \t\t\tb1 += s;\n@@ -44,19 +45,25 @@ static void msort_with_tmp(void *b, size_t n, size_t s,\n \tmemcpy(b, t, (n - n2) * s);\n }\n \n-void git_qsort(void *b, size_t n, size_t s,\n-\t int (*cmp)(const void *, const void *))\n+int git_qsort_s(void *b, size_t n, size_t s,\n+\t\tint (*cmp)(const void *, const void *, void *), void *ctx)\n {\n \tconst size_t size = st_mult(n, s);\n \tchar buf[1024];\n \n+\tif (!n)\n+\t\treturn 0;\n+\tif (!b || !cmp)\n+\t\treturn -1;\n+\n \tif (size < sizeof(buf)) {\n \t\t/* The temporary array fits on the small on-stack buffer. */\n-\t\tmsort_with_tmp(b, n, s, cmp, buf);\n+\t\tmsort_with_tmp(b, n, s, cmp, buf, ctx);\n \t} else {\n \t\t/* It's somewhat large, so malloc it. */\n \t\tchar *tmp = xmalloc(size);\n-\t\tmsort_with_tmp(b, n, s, cmp, tmp);\n+\t\tmsort_with_tmp(b, n, s, cmp, tmp, ctx);\n \t\tfree(tmp);\n \t}\n+\treturn 0;\n }\n\n"},{"id":"306716","messageId":"20161201193556.j2odwy3sepaxxq5a@sigill.intra.peff.net","threadId":"44585","inReplyTo":"fc602a66-a06c-203e-b50b-55fd7b258b54@web.de","subject":"Re: [PATCH 1/3] compat: add qsort_s()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-12-01T19:35:56Z","receivedAt":"2016-12-01T19:36:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Dec 01, 2016 at 05:26:43PM +0100, René Scharfe wrote:\n\n> The function qsort_s() was introduced with C11 Annex K; it provides the\n> ability to pass a context pointer to the comparison function, supports\n> the convention of using a NULL pointer for an empty array and performs a\n> few safety checks.\n> \n> Add an implementation based on compat/qsort.c for platforms that lack a\n> native standards-compliant qsort_s() (i.e. basically everyone). It\n> doesn't perform the full range of possible checks: It uses size_t\n> instead of rsize_t and doesn't check nmemb and size against RSIZE_MAX\n> because we probably don't have the restricted size type defined. For\n> the same reason it returns int instead of errno_t.\n\nHmm. So it sounds like qsort_r(), but with the NULL-is-empty magic. But\nwe already are OK without the latter (and can emulate it easily). Would\nit make sense to do:\n\n #if defined(HAVE_QSORT_S)\n /* huzzah, use the system-native qsort_s */\n\n #elif defined(HAVE_QSORT_R)\n int git_qsort_s(void *b, size_t n, size_t s,\n\t\t int (*cmp)(const void *, const void *, void *), void *ctx)\n {\n\tif (!n)\n\t\treturn 0;\n\tif (!b || !cmp)\n\t\treturn -1;\n\tqsort_r(b, n, s, cmp, ctx);\n\treturn 0;\n }\n\n #else\n /* fallback implementation as your patch does */\n #endif\n\nTo make matters more fun, apparently[1] there are multiple variants of\nqsort_r with different argument orders. _And_ apparently Microsoft\ndefines qsort_s, but it's not quite the same thing. But all of that can\nbe dealt with by having more specific flags (HAVE_GNU_QSORT_R, etc).\n\nIt just seems like we should be able to do a better job of using the\nsystem qsort in many cases.\n\n-Peff\n\n[1] https://stackoverflow.com/questions/39560773/different-declarations-of-qsort-r-on-mac-and-linux/39561369\n"},{"id":"306731","messageId":"xmqq7f7j9zkd.fsf@gitster.mtv.corp.google.com","threadId":"44585","inReplyTo":"20161201193556.j2odwy3sepaxxq5a@sigill.intra.peff.net","subject":"Re: [PATCH 1/3] compat: add qsort_s()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-12-01T20:14:42Z","receivedAt":"2016-12-01T20:14:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> To make matters more fun, apparently[1] there are multiple variants of\n> qsort_r with different argument orders. _And_ apparently Microsoft\n> defines qsort_s, but it's not quite the same thing. But all of that can\n> be dealt with by having more specific flags (HAVE_GNU_QSORT_R, etc).\n>\n> It just seems like we should be able to do a better job of using the\n> system qsort in many cases.\n\nIf we were to go that route, perhaps we shouldn't have HAVE_QSORT_S\nso that Microsoft folks won't define it by mistake (instead perhaps\ncall it HAVE_ISO_QSORT_S or something).\n\nI like your suggestion in general. The body of git_qsort_s() on\nsystems without ISO_QSORT_S can do \n\n - GNU qsort_r() without any change in the parameters, \n\n - Microsoft qsort_s() with parameter reordered, or \n\n - Apple/BSD qsort_r() with parameter reordered.\n\nand that would cover the major platforms.\n\nEh, wait. BSD and Microsoft have paramters reordered in the\ncallback comparison function. I suspect that would not fly very\nwell.\n\n"},{"id":"306732","messageId":"20161201201917.nqx3v5fl2ptl3bhr@sigill.intra.peff.net","threadId":"44585","inReplyTo":"xmqq7f7j9zkd.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/3] compat: add qsort_s()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-12-01T20:19:17Z","receivedAt":"2016-12-01T20:19:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Dec 01, 2016 at 12:14:42PM -0800, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > To make matters more fun, apparently[1] there are multiple variants of\n> > qsort_r with different argument orders. _And_ apparently Microsoft\n> > defines qsort_s, but it's not quite the same thing. But all of that can\n> > be dealt with by having more specific flags (HAVE_GNU_QSORT_R, etc).\n> >\n> > It just seems like we should be able to do a better job of using the\n> > system qsort in many cases.\n> \n> If we were to go that route, perhaps we shouldn't have HAVE_QSORT_S\n> so that Microsoft folks won't define it by mistake (instead perhaps\n> call it HAVE_ISO_QSORT_S or something).\n> \n> I like your suggestion in general. The body of git_qsort_s() on\n> systems without ISO_QSORT_S can do \n> \n> - GNU qsort_r() without any change in the parameters, \n> \n> - Microsoft qsort_s() with parameter reordered, or \n> \n> - Apple/BSD qsort_r() with parameter reordered.\n> \n> and that would cover the major platforms.\n> \n> Eh, wait. BSD and Microsoft have paramters reordered in the\n> callback comparison function. I suspect that would not fly very\n> well.\n\nYou can hack around it by passing a wrapper callback that flips the\narguments. Since we have a \"void *\" data pointer, that would point to a\nstruct holding the \"real\" callback and chaining to the original data\npointer.\n\nIt does incur the cost of an extra level of indirection for each\ncomparison, though (not just for each qsort call).\n\nYou could do it as zero-cost if you were willing to turn the comparison\nfunction definition into a macro.\n\n-Peff\n"},{"id":"306733","messageId":"xmqqy3zz8kmq.fsf@gitster.mtv.corp.google.com","threadId":"44585","inReplyTo":"xmqq7f7j9zkd.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/3] compat: add qsort_s()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-12-01T20:22:37Z","receivedAt":"2016-12-01T20:22:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Eh, wait. BSD and Microsoft have paramters reordered in the\n> callback comparison function. I suspect that would not fly very\n> well.\n\nHmm. We could do it like this, which may not be too bad.\n\n#if APPLE_QSORT_R\nstruct apple_qsort_adapter {\n\tint (*user_cmp)(const void *, const void *, void *);\n\tvoid *user_ctx;\n}\n\nstatic int apple_qsort_adapter_cmp(void *ctx, const void *a, const void *b)\n{\n\tstruct apple_qsort_adapter *wrapper_ctx = ctx;\n\treturn wrapper_ctx->user_cmp(a, b, wrapper_ctx->user_ctx);\n}\n#endif\n\nint git_qsort_s(void *b, size_t n, size_t s,\n \t int (*cmp)(const void *, const void *, void *), void *ctx)\n{\n\tif (!n)\n\t\treturn 0;\n\tif (!b || !cmp)\n\t\treturn -1;\n#if GNU_QSORT_R\n\tqsort_r(b, n, s, cmp, ctx);\n#elif APPLE_QSORT_R\n\t{\n\t\tstruct appple_qsort_adapter a = { cmp, ctx };\n\t\tqsort_r(b, n, s, &a, appple_qsort_adapter_cmp);\n\t}\n#endif\n return 0;\n}\n"},{"id":"306735","messageId":"xmqqpolb8khj.fsf@gitster.mtv.corp.google.com","threadId":"44585","inReplyTo":"20161201201917.nqx3v5fl2ptl3bhr@sigill.intra.peff.net","subject":"Re: [PATCH 1/3] compat: add qsort_s()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-12-01T20:25:44Z","receivedAt":"2016-12-01T20:25:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Thu, Dec 01, 2016 at 12:14:42PM -0800, Junio C Hamano wrote:\n>\n>> Eh, wait. BSD and Microsoft have paramters reordered in the\n>> callback comparison function. I suspect that would not fly very\n>> well.\n>\n> You can hack around it by passing a wrapper callback that flips the\n> arguments.\n\nApparently our mails crossed.\n"},{"id":"306736","messageId":"20161201202602.sfs6ycmh32ib5ed7@sigill.intra.peff.net","threadId":"44585","inReplyTo":"xmqqy3zz8kmq.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/3] compat: add qsort_s()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-12-01T20:26:03Z","receivedAt":"2016-12-01T20:26:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Dec 01, 2016 at 12:22:37PM -0800, Junio C Hamano wrote:\n\n> Junio C Hamano writes:\n> \n> > Eh, wait. BSD and Microsoft have paramters reordered in the\n> > callback comparison function. I suspect that would not fly very\n> > well.\n> \n> Hmm. We could do it like this, which may not be too bad.\n\nHeh. Exactly, but I was too lazy to write it out in my other email. :)\n\nThe no-cost version would be more like:\n\n#ifdef APPLE_QSORT_R\n#define DECLARE_CMP(func) int func(void *data, const void *va, const void *vb)\n#else\n#define DECLARE_CMP(func) int func(const void *va, const void *vb, void *data)\n#endif\n\nand then:\n\n DECLARE_CMP(foocmp);\n ...\n\n DECLARE_CMP(foocmp)\n {\n\tconst struct foo *a = va, *b = vb;\n\t... etc ...\n }\n\n-Peff\n"},{"id":"306768","messageId":"955e9bf4-d1cd-f01a-13f1-7a335dea011a@web.de","threadId":"44585","inReplyTo":"20161201201917.nqx3v5fl2ptl3bhr@sigill.intra.peff.net","subject":"Re: [PATCH 1/3] compat: add qsort_s()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-12-01T22:30:49Z","receivedAt":"2016-12-01T22:38:08Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 01.12.2016 um 21:19 schrieb Jeff King:\n> On Thu, Dec 01, 2016 at 12:14:42PM -0800, Junio C Hamano wrote:\n>\n>> Jeff King writes:\n>>\n>>> To make matters more fun, apparently[1] there are multiple variants of\n>>> qsort_r with different argument orders. _And_ apparently Microsoft\n>>> defines qsort_s, but it's not quite the same thing. But all of that can\n>>> be dealt with by having more specific flags (HAVE_GNU_QSORT_R, etc).\n\nAFAIU it went like this:\n\n// FreeBSD 5.0 (2003)\nvoid qsort_r(void *base, size_t nmemb, size_t size,\n\tvoid *context,\n\tint (*compar)(void *context, const void *x, const void *y));\n\n// Microsoft Visual Studio 2005\nvoid qsort_s(void *base, size_t nmemb, size_t size,\n\tint (*compar)(void *context, const void *x, const void *y),\n\tvoid *context);\n\n// glibc 2.8 (2008)\nvoid qsort_r(void *base, size_t nmemb, size_t size,\n\tint (*compar)(const void *x, const void *y, void *context),\n\tvoid *context);\n\n// C11 Annex K (2011)\nerrno_t qsort_s(void *base, rsize_t nmemb, rsize_t size,\n\tint (*compar)(const void *x, const void *y, void *context),\n\tvoid *context);\n\n>>> It just seems like we should be able to do a better job of using the\n>>> system qsort in many cases.\n\nSure, platform-specific implementations can be shorter.\n\n>> If we were to go that route, perhaps we shouldn't have HAVE_QSORT_S\n>> so that Microsoft folks won't define it by mistake (instead perhaps\n>> call it HAVE_ISO_QSORT_S or something).\n\nOK.\n\n>> I like your suggestion in general. The body of git_qsort_s() on\n>> systems without ISO_QSORT_S can do\n>>\n>> - GNU qsort_r() without any change in the parameters,\n>>\n>> - Microsoft qsort_s() with parameter reordered, or\n>>\n>> - Apple/BSD qsort_r() with parameter reordered.\n>>\n>> and that would cover the major platforms.\n\nYes.\n\nHowever, for MSys INTERNAL_QSORT is defined for some reason, so the \nplatform's qsort(3) is not used there; I guess the same reason applies \nto qsort_s(). If it doesn't then an implementation may want to convert \na call to the invalid parameter handler (which may show a dialog \noffering to Retry, Continue or Abort) into a non-zero return value.\n\n>> Eh, wait. BSD and Microsoft have paramters reordered in the\n>> callback comparison function. I suspect that would not fly very\n>> well.\n>\n> You can hack around it by passing a wrapper callback that flips the\n> arguments. Since we have a \"void *\" data pointer, that would point to a\n> struct holding the \"real\" callback and chaining to the original data\n> pointer.\n>\n> It does incur the cost of an extra level of indirection for each\n> comparison, though (not just for each qsort call).\n\nIndeed. We'd need a perf test to measure that overhead before we could \ndetermine if that's a problem, though.\n\n> You could do it as zero-cost if you were willing to turn the comparison\n> function definition into a macro.\n\nUgh. That either requires changing the signature of qsort_s() based on \nthe underlying native function as well, or using a void pointer to pass \nthe comparison function, no? Let's not do that, at least not without a \ngood reason.\n\nRené\n"},{"id":"306777","messageId":"xmqqd1hb6x0t.fsf@gitster.mtv.corp.google.com","threadId":"44585","inReplyTo":"955e9bf4-d1cd-f01a-13f1-7a335dea011a@web.de","subject":"Re: [PATCH 1/3] compat: add qsort_s()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-12-01T23:37:54Z","receivedAt":"2016-12-01T23:39:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n>> You can hack around it by passing a wrapper callback that flips the\n>> arguments. Since we have a \"void *\" data pointer, that would point to a\n>> struct holding the \"real\" callback and chaining to the original data\n>> pointer.\n>>\n>> It does incur the cost of an extra level of indirection for each\n>> comparison, though (not just for each qsort call).\n>\n> Indeed. We'd need a perf test to measure that overhead before we\n> could determine if that's a problem, though.\n\nI agree. Hopefully it won't be too much cost.\n\n>> You could do it as zero-cost if you were willing to turn the comparison\n>> function definition into a macro.\n>\n> Ugh. That either requires changing the signature of qsort_s() based\n> on the underlying native function as well, or using a void pointer to\n> pass the comparison function, no? Let's not do that, at least not\n> without a good reason.\n\nLet's not go there. It may be zero runtime cost, but the cognitive\ncost for people who need to code the comparison callback using the\nmacro is high.\n"},{"id":"307536","messageId":"b8aa28b1-e645-4cea-cc91-96f62fee6118@web.de","threadId":"44585","inReplyTo":"xmqqy3zz8kmq.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/3] compat: add qsort_s()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-12-12T19:51:14Z","receivedAt":"2016-12-12T19:51:39Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 01.12.2016 um 21:22 schrieb Junio C Hamano:\n> Junio C Hamano writes:\n>\n>> Eh, wait. BSD and Microsoft have paramters reordered in the\n>> callback comparison function. I suspect that would not fly very\n>> well.\n>\n> Hmm. We could do it like this, which may not be too bad.\n\nIt's kinda cool to have a bespoke compatibility layer for major \nplatforms, but the more I think about it the less I can answer why we \nwould want that. Safety, reliability and performance can't be good \nreasons -- if our fallback function lacks in these regards then we have \nto improve it in any case.\n\nText size could be a valid reason, but the full function only adds a bit \nmore than 2KB to the unstripped git binary.\n\nThe flip side is we'd build an ifdef maze that's harder to read and a \nlot more difficult to test.\n\nWhat do we get in return for that additional complexity?\n\n> #if APPLE_QSORT_R\n> struct apple_qsort_adapter {\n> \tint (*user_cmp)(const void *, const void *, void *);\n> \tvoid *user_ctx;\n> }\n>\n> static int apple_qsort_adapter_cmp(void *ctx, const void *a, const void *b)\n> {\n> \tstruct apple_qsort_adapter *wrapper_ctx = ctx;\n> \treturn wrapper_ctx->user_cmp(a, b, wrapper_ctx->user_ctx);\n> }\n> #endif\n>\n> int git_qsort_s(void *b, size_t n, size_t s,\n> \t int (*cmp)(const void *, const void *, void *), void *ctx)\n> {\n> \tif (!n)\n> \t\treturn 0;\n> \tif (!b || !cmp)\n> \t\treturn -1;\n> #if GNU_QSORT_R\n> \tqsort_r(b, n, s, cmp, ctx);\n> #elif APPLE_QSORT_R\n> \t{\n> \t\tstruct appple_qsort_adapter a = { cmp, ctx };\n> \t\tqsort_r(b, n, s, &a, appple_qsort_adapter_cmp);\n> \t}\n> #endif\n\nNit: The fallback for non-GNU, non-Apple systems is missing here, but \nthe idea is illustrated clearly enough.\n\n> return 0;\n> }\n>\n\n"},{"id":"307539","messageId":"20161212195703.nmljhwwmrn56gbyd@sigill.intra.peff.net","threadId":"44585","inReplyTo":"b8aa28b1-e645-4cea-cc91-96f62fee6118@web.de","subject":"Re: [PATCH 1/3] compat: add qsort_s()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-12-12T19:57:03Z","receivedAt":"2016-12-12T19:57:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Dec 12, 2016 at 08:51:14PM +0100, René Scharfe wrote:\n\n> It's kinda cool to have a bespoke compatibility layer for major platforms,\n> but the more I think about it the less I can answer why we would want that.\n> Safety, reliability and performance can't be good reasons -- if our fallback\n> function lacks in these regards then we have to improve it in any case.\n\nThere may be cases that we don't want to support because of portability\nissues. E.g., if your libc has an assembly-optimized qsort() we wouldn't\nwant to replicate that.\n\nI dunno. I am not that opposed to just saying \"forget libc qsort, we\nalways use our internal one which is consistent, performant, and safe\".\nBut when I suggested something similar for our regex library, I seem to\nrecall there were complaints.\n\n-Peff\n"},{"id":"308195","messageId":"2203c696-3a86-626b-c516-285daef15022@web.de","threadId":"44585","inReplyTo":"20161212195703.nmljhwwmrn56gbyd@sigill.intra.peff.net","subject":"Re: [PATCH 1/3] compat: add qsort_s()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-12-21T09:36:25Z","receivedAt":"2016-12-21T09:37:02Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 12.12.2016 um 20:57 schrieb Jeff King:\n> On Mon, Dec 12, 2016 at 08:51:14PM +0100, René Scharfe wrote:\n>\n>> It's kinda cool to have a bespoke compatibility layer for major platforms,\n>> but the more I think about it the less I can answer why we would want that.\n>> Safety, reliability and performance can't be good reasons -- if our fallback\n>> function lacks in these regards then we have to improve it in any case.\n>\n> There may be cases that we don't want to support because of portability\n> issues. E.g., if your libc has an assembly-optimized qsort() we wouldn't\n> want to replicate that.\n\nOffloading to GPUs might be a better example; I don't know of a libc \nthat does any of that, though (yet).\n\n> I dunno. I am not that opposed to just saying \"forget libc qsort, we\n> always use our internal one which is consistent, performant, and safe\".\n> But when I suggested something similar for our regex library, I seem to\n> recall there were complaints.\n\nWell, I'm not sure how comparable they are, but perhaps we can avoid \ncompat code altogether in this case. Patch coming in a new thread.\n\nRené\n"}]}