{"thread":{"id":"36811","subject":"[PATCH v5 1/2] refs.c: optimize check_refname_component()","startedAt":"2014-06-02T06:20:14Z","lastAt":"2014-06-04T03:35:11Z","messageCount":5,"participants":["David Turner","Junio C Hamano"],"isPatch":true,"patchVersion":5,"patchTotal":2},"messages":[{"id":"243116","messageId":"1401690015-19191-1-git-send-email-dturner@twitter.com","threadId":"36811","inReplyTo":null,"subject":"[PATCH v5 1/2] refs.c: optimize check_refname_component()","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-06-02T06:20:14Z","receivedAt":"2014-06-02T06:20:14Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"In a repository with many refs, check_refname_component can be a major\ncontributor to the runtime of some git commands. One such command is\n\ngit rev-parse HEAD\n\nTimings for one particular repo, with about 60k refs, almost all\npacked, are:\n\nOld: 35 ms\nNew: 29 ms\n\nMany other commands which read refs are also sped up.\n\nSigned-off-by: David Turner <dturner@twitter.com>\n---\n refs.c             | 67 +++++++++++++++++++++++++++++++-----------------------\n t/t5511-refspec.sh |  6 ++++-\n 2 files changed, 44 insertions(+), 29 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 28d5eca..dd28f2a 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -6,8 +6,29 @@\n #include \"string-list.h\"\n \n /*\n- * Make sure \"ref\" is something reasonable to have under \".git/refs/\";\n- * We do not like it if:\n+ * How to handle various characters in refnames:\n+ * 0: An acceptable character for refs\n+ * 1: End-of-component\n+ * 2: ., look for a preceding . to reject .. in refs\n+ * 3: {, look for a preceding @ to reject @{ in refs\n+ * 4: A bad character: ASCII control characters, \"~\", \"^\", \":\" or SP\n+ */\n+static unsigned char refname_disposition[256] = {\n+\t1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,\n+\t4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,\n+\t4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 2, 1,\n+\t0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 4,\n+\t0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n+\t0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4, 0, 4, 0,\n+\t0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n+\t0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 4, 4\n+};\n+\n+/*\n+ * Try to read one refname component from the front of refname.\n+ * Return the length of the component found, or -1 if the component is\n+ * not legal.  It is legal if it is something reasonable to have under\n+ * \".git/refs/\"; We do not like it if:\n  *\n  * - any path component of it begins with \".\", or\n  * - it has double dots \"..\", or\n@@ -16,41 +37,31 @@\n  * - it ends with \".lock\"\n  * - it contains a \"\\\" (backslash)\n  */\n-\n-/* Return true iff ch is not allowed in reference names. */\n-static inline int bad_ref_char(int ch)\n-{\n-\tif (((unsigned) ch) <= ' ' || ch == 0x7f ||\n-\t    ch == '~' || ch == '^' || ch == ':' || ch == '\\\\')\n-\t\treturn 1;\n-\t/* 2.13 Pattern Matching Notation */\n-\tif (ch == '*' || ch == '?' || ch == '[') /* Unsupported */\n-\t\treturn 1;\n-\treturn 0;\n-}\n-\n-/*\n- * Try to read one refname component from the front of refname.  Return\n- * the length of the component found, or -1 if the component is not\n- * legal.\n- */\n static int check_refname_component(const char *refname, int flags)\n {\n \tconst char *cp;\n \tchar last = '\\0';\n \n \tfor (cp = refname; ; cp++) {\n-\t\tchar ch = *cp;\n-\t\tif (ch == '\\0' || ch == '/')\n+\t\tunsigned char ch = (unsigned char) *cp;\n+\t\tunsigned char disp = refname_disposition[ch];\n+\t\tswitch(disp) {\n+\t\tcase 1:\n+\t\t\tgoto out;\n+\t\tcase 2:\n+\t\t\tif (last == '.')\n+\t\t\t\treturn -1; /* Refname contains \"..\". */\n+\t\t\tbreak;\n+\t\tcase 3:\n+\t\t\tif (last == '@')\n+\t\t\t\treturn -1; /* Refname contains \"@{\". */\n \t\t\tbreak;\n-\t\tif (bad_ref_char(ch))\n-\t\t\treturn -1; /* Illegal character in refname. */\n-\t\tif (last == '.' && ch == '.')\n-\t\t\treturn -1; /* Refname contains \"..\". */\n-\t\tif (last == '@' && ch == '{')\n-\t\t\treturn -1; /* Refname contains \"@{\". */\n+\t\tcase 4:\n+\t\t\treturn -1;\n+\t\t}\n \t\tlast = ch;\n \t}\n+out:\n \tif (cp == refname)\n \t\treturn 0; /* Component has zero length. */\n \tif (refname[0] == '.') {\ndiff --git a/t/t5511-refspec.sh b/t/t5511-refspec.sh\nindex c289322..1571176 100755\n--- a/t/t5511-refspec.sh\n+++ b/t/t5511-refspec.sh\n@@ -5,7 +5,6 @@ test_description='refspec parsing'\n . ./test-lib.sh\n \n test_refspec () {\n-\n \tkind=$1 refspec=$2 expect=$3\n \tgit config remote.frotz.url \".\" &&\n \tgit config --remove-section remote.frotz &&\n@@ -84,4 +83,9 @@ test_refspec push 'refs/heads/*/*/for-linus:refs/remotes/mine/*' invalid\n test_refspec fetch 'refs/heads/*/for-linus:refs/remotes/mine/*'\n test_refspec push 'refs/heads/*/for-linus:refs/remotes/mine/*'\n \n+good=$(echo -n '\\0377')\n+test_refspec fetch \"refs/heads/${good}\"\n+bad=$(echo -n '\\011')\n+test_refspec fetch \"refs/heads/${bad}\"\t\t\t\tinvalid\n+\n test_done\n-- \n2.0.0.rc1.18.gf763c0f\n"},{"id":"243117","messageId":"1401690015-19191-2-git-send-email-dturner@twitter.com","threadId":"36811","inReplyTo":"1401690015-19191-1-git-send-email-dturner@twitter.com","subject":"[PATCH v5 2/2] refs.c: SSE4.2 optimizations for check_refname_component","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-06-02T06:20:15Z","receivedAt":"2014-06-02T06:20:15Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"Optimize check_refname_component using SSE4.2, where available.\n\ngit rev-parse HEAD is a good test-case for this, since it does almost\nnothing except parse refs.  For one particular repo with about 60k\nrefs, almost all packed, the timings are:\n\nLook up table: 29 ms\nSSE4.2:        25 ms\n\nThis is about a 15% improvement.\n\nThe configure.ac changes include code from the GNU C Library written\nby Joseph S. Myers <joseph at codesourcery dot com>.\n\nSigned-off-by: David Turner <dturner@twitter.com>\n---\n Makefile           |   6 +++\n aclocal.m4         |   6 +++\n configure.ac       |  17 ++++++++\n git-compat-util.h  |  20 +++++++++\n refs.c             | 116 +++++++++++++++++++++++++++++++++++++++++++++--------\n t/t5511-refspec.sh |  13 ++++++\n 6 files changed, 161 insertions(+), 17 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex a53f3a8..dd2127a 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1326,6 +1326,11 @@ else\n \t\tCOMPAT_OBJS += compat/win32mmap.o\n \tendif\n endif\n+ifdef NO_SSE42\n+\tBASIC_CFLAGS += -DNO_SSE42\n+else\n+\tBASIC_CFLAGS += -msse4.2\n+endif\n ifdef OBJECT_CREATION_USES_RENAMES\n \tCOMPAT_CFLAGS += -DOBJECT_CREATION_MODE=1\n endif\n@@ -2199,6 +2204,7 @@ GIT-BUILD-OPTIONS: FORCE\n \t@echo NO_PERL=\\''$(subst ','\\'',$(subst ','\\'',$(NO_PERL)))'\\' >>$@\n \t@echo NO_PYTHON=\\''$(subst ','\\'',$(subst ','\\'',$(NO_PYTHON)))'\\' >>$@\n \t@echo NO_UNIX_SOCKETS=\\''$(subst ','\\'',$(subst ','\\'',$(NO_UNIX_SOCKETS)))'\\' >>$@\n+\t@echo NO_SSE42=\\''$(subst ','\\'',$(subst ','\\'',$(NO_SSE42)))'\\' >>$@\n ifdef TEST_OUTPUT_DIRECTORY\n \t@echo TEST_OUTPUT_DIRECTORY=\\''$(subst ','\\'',$(subst ','\\'',$(TEST_OUTPUT_DIRECTORY)))'\\' >>$@\n endif\ndiff --git a/aclocal.m4 b/aclocal.m4\nindex f11bc7e..d9f3f19 100644\n--- a/aclocal.m4\n+++ b/aclocal.m4\n@@ -38,3 +38,9 @@ AC_DEFUN([TYPE_SOCKLEN_T],\n       [#include <sys/types.h>\n #include <sys/socket.h>])\n ])\n+\n+dnl Test a compiler option or options with an empty input file.\n+dnl LIBC_TRY_CC_OPTION([options], [action-if-true], [action-if-false])\n+AC_DEFUN([LIBC_TRY_CC_OPTION],\n+[AS_IF([AC_TRY_COMMAND([${CC-cc} $1 -xc /dev/null -S -o /dev/null])],\n+\t[$2], [$3])])\ndiff --git a/configure.ac b/configure.ac\nindex b711254..3a5bda9 100644\n--- a/configure.ac\n+++ b/configure.ac\n@@ -382,6 +382,23 @@ AS_HELP_STRING([],[Tcl/Tk interpreter will be found in a system.]),\n GIT_PARSE_WITH(tcltk))\n #\n \n+# Declare the with-sse42/without-sse42 options.\n+AC_ARG_WITH(sse42,\n+AS_HELP_STRING([--with-sse42],[use SSE4.2 instructions])\n+AS_HELP_STRING([],[(default is YES if your compiler supports -msse4.2)]),\n+GIT_PARSE_WITH(sse42))\n+\n+if test \"$NO_SSE42\" != \"YesPlease\"; then\n+   dnl Check if -msse4.2 works.\n+   AC_CACHE_CHECK(for SSE4.2 support, cc_cv_sse42, [dnl\n+   LIBC_TRY_CC_OPTION([-msse4.2], [cc_cv_sse42=yes], [cc_cv_sse42=no])\n+   ])\n+   if test $cc_cv_sse42 = no; then\n+     NO_SSE42=1\n+   fi\n+fi\n+\n+GIT_CONF_SUBST([NO_SSE42])\n \n ## Checks for programs.\n AC_MSG_NOTICE([CHECKS for programs])\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex f6d3a46..254487a 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -668,6 +668,26 @@ void git_qsort(void *base, size_t nmemb, size_t size,\n #endif\n #endif\n \n+#ifndef NO_SSE42\n+#include <nmmintrin.h>\n+/* Clang ships with a version of nmmintrin.h that's incomplete; if\n+ * necessary, we define the constants that we're going to use. */\n+#ifndef _SIDD_UBYTE_OPS\n+#define _SIDD_UBYTE_OPS                 0x00\n+#define _SIDD_CMP_EQUAL_ANY             0x00\n+#define _SIDD_CMP_RANGES                0x04\n+#define _SIDD_CMP_EQUAL_ORDERED         0x0c\n+#define _SIDD_NEGATIVE_POLARITY         0x10\n+#endif\n+\n+/* This is the system memory page size; it's used so that we can read\n+ * outside the bounds of an allocation without segfaulting. It is\n+ * assumed to be a power of 2. */\n+#ifndef PAGE_SIZE\n+#define PAGE_SIZE 4096\n+#endif\n+#endif\n+\n #ifdef UNRELIABLE_FSTAT\n #define fstat_is_reliable() 0\n #else\ndiff --git a/refs.c b/refs.c\nindex dd28f2a..22a2dae 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -24,6 +24,25 @@ static unsigned char refname_disposition[256] = {\n \t0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 4, 4\n };\n \n+static int check_refname_component_trailer(const char *cp, const char *refname, int flags)\n+{\n+\tif (cp == refname)\n+\t\treturn 0; /* Component has zero length. */\n+\tif (refname[0] == '.') {\n+\t\tif (!(flags & REFNAME_DOT_COMPONENT))\n+\t\t\treturn -1; /* Component starts with '.'. */\n+\t\t/*\n+\t\t * Even if leading dots are allowed, don't allow \".\"\n+\t\t * as a component (\"..\" is prevented by a rule above).\n+\t\t */\n+\t\tif (refname[1] == '\\0')\n+\t\t\treturn -1; /* Component equals \".\". */\n+\t}\n+\tif (cp - refname >= 5 && !memcmp(cp - 5, \".lock\", 5))\n+\t\treturn -1; /* Refname ends with \".lock\". */\n+\treturn cp - refname;\n+}\n+\n /*\n  * Try to read one refname component from the front of refname.\n  * Return the length of the component found, or -1 if the component is\n@@ -37,7 +56,7 @@ static unsigned char refname_disposition[256] = {\n  * - it ends with \".lock\"\n  * - it contains a \"\\\" (backslash)\n  */\n-static int check_refname_component(const char *refname, int flags)\n+static int check_refname_component_1(const char *refname, int flags)\n {\n \tconst char *cp;\n \tchar last = '\\0';\n@@ -47,7 +66,7 @@ static int check_refname_component(const char *refname, int flags)\n \t\tunsigned char disp = refname_disposition[ch];\n \t\tswitch(disp) {\n \t\tcase 1:\n-\t\t\tgoto out;\n+\t\t\treturn check_refname_component_trailer(cp, refname, flags);\n \t\tcase 2:\n \t\t\tif (last == '.')\n \t\t\t\treturn -1; /* Refname contains \"..\". */\n@@ -61,23 +80,86 @@ static int check_refname_component(const char *refname, int flags)\n \t\t}\n \t\tlast = ch;\n \t}\n-out:\n-\tif (cp == refname)\n-\t\treturn 0; /* Component has zero length. */\n-\tif (refname[0] == '.') {\n-\t\tif (!(flags & REFNAME_DOT_COMPONENT))\n-\t\t\treturn -1; /* Component starts with '.'. */\n-\t\t/*\n-\t\t * Even if leading dots are allowed, don't allow \".\"\n-\t\t * as a component (\"..\" is prevented by a rule above).\n-\t\t */\n-\t\tif (refname[1] == '\\0')\n-\t\t\treturn -1; /* Component equals \".\". */\n+}\n+\n+#ifdef NO_SSE42\n+#define check_refname_component check_refname_component_1\n+#else\n+#define BLOCK_SIZE 16\n+\n+/* Vectorized version of check_refname_component */\n+static int check_refname_component(const char *refname, int flags)\n+{\n+\tconst __m128i *refname_vec = (__m128i*) refname;\n+\n+\t/* Character ranges for characters forbidden in refs; see\n+\t * above */\n+\tstatic const __v16qi bad = {\n+\t\t0x01, 0x20,  0x7e, 0x7f,  0x5e, 0x5e,  0x3a, 0x3a,\n+\t\t0x5b, 0x5c,  0x2a, 0x2a,  0x3f, 0x3f,  0x3f, 0x3f};\n+\n+\tstatic const __v16qi nonslashes = {\n+\t\t'\\001', '/' -1, '/' + 1, 0xff,\n+\t};\n+\n+\tstatic const __v16qi dotdot = {'.','.',0};\n+\tstatic const __v16qi atcurly = {'@','{',0};\n+\n+\tconst __m128i *vp;\n+\tconst char *cp = (const char *)refname_vec;\n+\n+\tint dotdotpos = BLOCK_SIZE, atcurlypos = BLOCK_SIZE;\n+\tfor (vp = refname_vec; ; vp++) {\n+\t\t__m128i tmp;\n+\t\tint endpos;\n+\n+\t\t/* Handle case of forbidden substrings .. and @{ crossing\n+\t\t * sixteen-byte boundaries */\n+\t\tif (dotdotpos == 15 && *cp == '.')\n+\t\t\treturn -1;\n+\n+\t\tif (atcurlypos == 15 && *cp == '{')\n+\t\t\treturn -1;\n+\n+\t\tif (((uintptr_t) vp & (PAGE_SIZE - 1)) > PAGE_SIZE - BLOCK_SIZE)\n+\t\t\t/* End-of-page; fall back to slow method for\n+\t\t\t * this entire component. */\n+\t\t\treturn check_refname_component_1(refname, flags);\n+\n+\t\ttmp = _mm_lddqu_si128(vp);\n+\n+\t\t/* Find slashes or end-of-string. The double-negative\n+\t\t * (negative-polarity search for non-slashes) is\n+\t\t * necessary so that \\0 will also be counted.  */\n+\t\tendpos = _mm_cmpistri((__m128i) nonslashes, tmp,\n+\t\t\t\t      _SIDD_UBYTE_OPS | _SIDD_CMP_RANGES |\n+\t\t\t\t      _SIDD_NEGATIVE_POLARITY);\n+\n+\t\tif (_mm_cmpestrc((__m128i) bad, BLOCK_SIZE, tmp, endpos,\n+\t\t\t\t _SIDD_UBYTE_OPS | _SIDD_CMP_RANGES))\n+\t\t\treturn -1;\n+\n+\t\tdotdotpos = _mm_cmpestri((__m128i) dotdot, 2, tmp, endpos,\n+\t\t\t\t\t _SIDD_UBYTE_OPS |\n+\t\t\t\t\t _SIDD_CMP_EQUAL_ORDERED);\n+\t\tif (dotdotpos < 15)\n+\t\t\treturn -1;\n+\n+\t\tatcurlypos = _mm_cmpestri((__m128i) atcurly, 2, tmp, endpos,\n+\t\t\t\t\t  _SIDD_UBYTE_OPS |\n+\t\t\t\t\t  _SIDD_CMP_EQUAL_ORDERED);\n+\t\tif (atcurlypos < 15)\n+\t\t\treturn -1;\n+\n+\t\tif (endpos < BLOCK_SIZE) {\n+\t\t\tcp = ((const char*) vp) + endpos;\n+\t\t\tbreak;\n+\t\t}\n+\t\tcp = (const char*) vp + BLOCK_SIZE;\n \t}\n-\tif (cp - refname >= 5 && !memcmp(cp - 5, \".lock\", 5))\n-\t\treturn -1; /* Refname ends with \".lock\". */\n-\treturn cp - refname;\n+\treturn check_refname_component_trailer(cp, refname, flags);\n }\n+#endif\n \n int check_refname_format(const char *refname, int flags)\n {\ndiff --git a/t/t5511-refspec.sh b/t/t5511-refspec.sh\nindex 1571176..6fc00fb 100755\n--- a/t/t5511-refspec.sh\n+++ b/t/t5511-refspec.sh\n@@ -88,4 +88,17 @@ test_refspec fetch \"refs/heads/${good}\"\n bad=$(echo -n '\\011')\n test_refspec fetch \"refs/heads/${bad}\"\t\t\t\tinvalid\n \n+test_refspec fetch 'refs/heads/a-very-long-refname'\n+test_refspec fetch 'refs/heads/.a-very-long-refname'\t\tinvalid\n+test_refspec fetch 'refs/heads/abcdefgh0123..'\t\t\tinvalid\n+test_refspec fetch 'refs/heads/abcdefgh01234..'\t\t\tinvalid\n+test_refspec fetch 'refs/heads/abcdefgh012345..'\t\tinvalid\n+test_refspec fetch 'refs/heads/abcdefgh0123456..'\t\tinvalid\n+test_refspec fetch 'refs/heads/abcdefgh01234567..'\t\tinvalid\n+test_refspec fetch 'refs/heads/abcdefgh0123.a'\n+test_refspec fetch 'refs/heads/abcdefgh01234.a'\n+test_refspec fetch 'refs/heads/abcdefgh012345.a'\n+test_refspec fetch 'refs/heads/abcdefgh0123456.a'\n+test_refspec fetch 'refs/heads/abcdefgh01234567.a'\n+\n test_done\n-- \n2.0.0.rc1.18.gf763c0f\n"},{"id":"243196","messageId":"xmqqzjhtx3vr.fsf@gitster.dls.corp.google.com","threadId":"36811","inReplyTo":"1401690015-19191-1-git-send-email-dturner@twitter.com","subject":"Re: [PATCH v5 1/2] refs.c: optimize check_refname_component()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-06-03T18:08:24Z","receivedAt":"2014-06-03T18:08:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner <dturner@twopensource.com> writes:\n\n>  static int check_refname_component(const char *refname, int flags)\n>  {\n>  \tconst char *cp;\n>  \tchar last = '\\0';\n>  \n>  \tfor (cp = refname; ; cp++) {\n> -\t\tchar ch = *cp;\n> -\t\tif (ch == '\\0' || ch == '/')\n> +\t\tunsigned char ch = (unsigned char) *cp;\n\nHmph, this cast bothers me.  I am fine with either of these two, though.\n\n\tint ch = *cp & 0377;\n        unsigned char ch = *((unsigned char *)cp);\n\n> +\t\tunsigned char disp = refname_disposition[ch];\n> +\t\tswitch(disp) {\n> +\t\tcase 1:\n> +\t\t\tgoto out;\n> +\t\tcase 2:\n> +\t\t\tif (last == '.')\n> +\t\t\t\treturn -1; /* Refname contains \"..\". */\n> +\t\t\tbreak;\n> +\t\tcase 3:\n> +\t\t\tif (last == '@')\n> +\t\t\t\treturn -1; /* Refname contains \"@{\". */\n>  \t\t\tbreak;\n> -\t\tif (bad_ref_char(ch))\n> -\t\t\treturn -1; /* Illegal character in refname. */\n> -\t\tif (last == '.' && ch == '.')\n> -\t\t\treturn -1; /* Refname contains \"..\". */\n> -\t\tif (last == '@' && ch == '{')\n> -\t\t\treturn -1; /* Refname contains \"@{\". */\n> +\t\tcase 4:\n> +\t\t\treturn -1;\n> +\t\t}\n>  \t\tlast = ch;\n>  \t}\n> +out:\n>  \tif (cp == refname)\n>  \t\treturn 0; /* Component has zero length. */\n>  \tif (refname[0] == '.') {\n> diff --git a/t/t5511-refspec.sh b/t/t5511-refspec.sh\n> index c289322..1571176 100755\n> --- a/t/t5511-refspec.sh\n> +++ b/t/t5511-refspec.sh\n> @@ -5,7 +5,6 @@ test_description='refspec parsing'\n>  . ./test-lib.sh\n>  \n>  test_refspec () {\n> -\n>  \tkind=$1 refspec=$2 expect=$3\n>  \tgit config remote.frotz.url \".\" &&\n>  \tgit config --remove-section remote.frotz &&\n> @@ -84,4 +83,9 @@ test_refspec push 'refs/heads/*/*/for-linus:refs/remotes/mine/*' invalid\n>  test_refspec fetch 'refs/heads/*/for-linus:refs/remotes/mine/*'\n>  test_refspec push 'refs/heads/*/for-linus:refs/remotes/mine/*'\n>  \n> +good=$(echo -n '\\0377')\n\nI think we avoid \"echo -n\" and use \"printf\" to be portable across\ndifferent echo implementations.\n\nUse of \\0377, which most likely to be just half-a-character, does\nnot feel a particularly good example, by the way.\n\n> +test_refspec fetch \"refs/heads/${good}\"\n> +bad=$(echo -n '\\011')\n\nLikewise.\n\n> +test_refspec fetch \"refs/heads/${bad}\"\t\t\t\tinvalid\n> +\n>  test_done\n"},{"id":"243255","messageId":"xmqqd2epwsw0.fsf@gitster.dls.corp.google.com","threadId":"36811","inReplyTo":"1401690015-19191-2-git-send-email-dturner@twitter.com","subject":"Re: [PATCH v5 2/2] refs.c: SSE4.2 optimizations for check_refname_component","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-06-03T22:05:51Z","receivedAt":"2014-06-03T22:05:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner <dturner@twopensource.com> writes:\n\n> diff --git a/git-compat-util.h b/git-compat-util.h\n> index f6d3a46..254487a 100644\n> --- a/git-compat-util.h\n> +++ b/git-compat-util.h\n> @@ -668,6 +668,26 @@ void git_qsort(void *base, size_t nmemb, size_t size,\n>  #endif\n>  #endif\n>  \n> +#ifndef NO_SSE42\n> +#include <nmmintrin.h>\n> +/* Clang ships with a version of nmmintrin.h that's incomplete; if\n> + * necessary, we define the constants that we're going to use. */\n\nAs pointed out by Michael already, we format multiline comments with\nno text on the opening line:\n\n/*\n * Clang ships\n * ... to use.\n */\n\n> +#ifndef _SIDD_UBYTE_OPS\n> +#define _SIDD_UBYTE_OPS                 0x00\n> +#define _SIDD_CMP_EQUAL_ANY             0x00\n> +#define _SIDD_CMP_RANGES                0x04\n> +#define _SIDD_CMP_EQUAL_ORDERED         0x0c\n> +#define _SIDD_NEGATIVE_POLARITY         0x10\n> +#endif\n> +\n> +/* This is the system memory page size; it's used so that we can read\n> + * outside the bounds of an allocation without segfaulting. It is\n> + * assumed to be a power of 2. */\n> +#ifndef PAGE_SIZE\n> +#define PAGE_SIZE 4096\n> +#endif\n> +#endif\n> +\n>  #ifdef UNRELIABLE_FSTAT\n>  #define fstat_is_reliable() 0\n>  #else\n> diff --git a/refs.c b/refs.c\n> index dd28f2a..22a2dae 100644\n> --- a/refs.c\n> +++ b/refs.c\n> @@ -24,6 +24,25 @@ static unsigned char refname_disposition[256] = {\n>  \t0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 4, 4\n>  };\n>  \n> +static int check_refname_component_trailer(const char *cp, const char *refname, int flags)\n> +{\n> +\tif (cp == refname)\n> +\t\treturn 0; /* Component has zero length. */\n> +\tif (refname[0] == '.') {\n> +\t\tif (!(flags & REFNAME_DOT_COMPONENT))\n> +\t\t\treturn -1; /* Component starts with '.'. */\n> +\t\t/*\n> +\t\t * Even if leading dots are allowed, don't allow \".\"\n> +\t\t * as a component (\"..\" is prevented by a rule above).\n> +\t\t */\n> +\t\tif (refname[1] == '\\0')\n> +\t\t\treturn -1; /* Component equals \".\". */\n> +\t}\n> +\tif (cp - refname >= 5 && !memcmp(cp - 5, \".lock\", 5))\n> +\t\treturn -1; /* Refname ends with \".lock\". */\n> +\treturn cp - refname;\n> +}\n> +\n>  /*\n>   * Try to read one refname component from the front of refname.\n>   * Return the length of the component found, or -1 if the component is\n> @@ -37,7 +56,7 @@ static unsigned char refname_disposition[256] = {\n>   * - it ends with \".lock\"\n>   * - it contains a \"\\\" (backslash)\n>   */\n> -static int check_refname_component(const char *refname, int flags)\n> +static int check_refname_component_1(const char *refname, int flags)\n>  {\n>  \tconst char *cp;\n>  \tchar last = '\\0';\n> @@ -47,7 +66,7 @@ static int check_refname_component(const char *refname, int flags)\n>  \t\tunsigned char disp = refname_disposition[ch];\n>  \t\tswitch(disp) {\n>  \t\tcase 1:\n> -\t\t\tgoto out;\n> +\t\t\treturn check_refname_component_trailer(cp, refname, flags);\n>  \t\tcase 2:\n>  \t\t\tif (last == '.')\n>  \t\t\t\treturn -1; /* Refname contains \"..\". */\n> @@ -61,23 +80,86 @@ static int check_refname_component(const char *refname, int flags)\n>  \t\t}\n>  \t\tlast = ch;\n>  \t}\n> -out:\n> -\tif (cp == refname)\n> -\t\treturn 0; /* Component has zero length. */\n> -\tif (refname[0] == '.') {\n> -\t\tif (!(flags & REFNAME_DOT_COMPONENT))\n> -\t\t\treturn -1; /* Component starts with '.'. */\n> -\t\t/*\n> -\t\t * Even if leading dots are allowed, don't allow \".\"\n> -\t\t * as a component (\"..\" is prevented by a rule above).\n> -\t\t */\n> -\t\tif (refname[1] == '\\0')\n> -\t\t\treturn -1; /* Component equals \".\". */\n> +}\n> +\n> +#ifdef NO_SSE42\n> +#define check_refname_component check_refname_component_1\n> +#else\n> +#define BLOCK_SIZE 16\n\nIs this macro name safe?  It feels a bit too generic/broad and\nasking to collide with some system-defined block size constant\ncoming from random <*.h> header file, but maybe it's just me.\n\n> +/* Vectorized version of check_refname_component */\n> +static int check_refname_component(const char *refname, int flags)\n> +{\n> +\tconst __m128i *refname_vec = (__m128i*) refname;\n> +\n> +\t/* Character ranges for characters forbidden in refs; see\n> +\t * above */\n> +\tstatic const __v16qi bad = {\n> +\t\t0x01, 0x20,  0x7e, 0x7f,  0x5e, 0x5e,  0x3a, 0x3a,\n> +\t\t0x5b, 0x5c,  0x2a, 0x2a,  0x3f, 0x3f,  0x3f, 0x3f};\n> +\n> +\tstatic const __v16qi nonslashes = {\n> +\t\t'\\001', '/' -1, '/' + 1, 0xff,\n> +\t};\n> +\n> +\tstatic const __v16qi dotdot = {'.','.',0};\n> +\tstatic const __v16qi atcurly = {'@','{',0};\n\ns/,/, /g; please.\n\n> +\tconst __m128i *vp;\n> +\tconst char *cp = (const char *)refname_vec;\n> +\n> +\tint dotdotpos = BLOCK_SIZE, atcurlypos = BLOCK_SIZE;\n> +\tfor (vp = refname_vec; ; vp++) {\n> +\t\t__m128i tmp;\n> +\t\tint endpos;\n> +\n> +\t\t/* Handle case of forbidden substrings .. and @{ crossing\n> +\t\t * sixteen-byte boundaries */\n> +\t\tif (dotdotpos == 15 && *cp == '.')\n> +\t\t\treturn -1;\n> +\n> +\t\tif (atcurlypos == 15 && *cp == '{')\n> +\t\t\treturn -1;\n> +\n> +\t\tif (((uintptr_t) vp & (PAGE_SIZE - 1)) > PAGE_SIZE - BLOCK_SIZE)\n> +\t\t\t/* End-of-page; fall back to slow method for\n> +\t\t\t * this entire component. */\n> +\t\t\treturn check_refname_component_1(refname, flags);\n\nIt is somewhat sad that we have to redo the whole thing, but nobody\nhigher in the callchain knows how long the refname will be before\ncalling us, so this cannot be avoided.\n"},{"id":"243274","messageId":"1401852911.18134.134.camel@stross","threadId":"36811","inReplyTo":"xmqqd2epwsw0.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v5 2/2] refs.c: SSE4.2 optimizations for check_refname_component","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2014-06-04T03:35:11Z","receivedAt":"2014-06-04T03:35:11Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Tue, 2014-06-03 at 15:05 -0700, Junio C Hamano wrote:\n> > +\t\tif (((uintptr_t) vp & (PAGE_SIZE - 1)) > PAGE_SIZE - BLOCK_SIZE)\n> > +\t\t\t/* End-of-page; fall back to slow method for\n> > +\t\t\t * this entire component. */\n> > +\t\t\treturn check_refname_component_1(refname, flags);\n> \n> It is somewhat sad that we have to redo the whole thing, but nobody\n> higher in the callchain knows how long the refname will be before\n> calling us, so this cannot be avoided.\n\nIt actually could be avoided; we could pass in some extra args that let\ncheck_refname_component_1 start checking after the part that we have\nalready checked.  I decided not to do this because I believe that\nthe average refname component is short, which means that the cost is not\ntoo high and that it won't happen very often.  But I would be willing to\nchange this if you would like.\n"}]}