{"thread":{"id":"42483","subject":"[PATCH 0/2] strbuf: improve API","startedAt":"2016-05-30T10:36:40Z","lastAt":"2016-06-24T17:20:44Z","messageCount":38,"participants":["William Duclot","Remi Galan Alfonso","Johannes Schindelin","Matthieu Moy","Simon Rabourg","Mike Hommey","Michael Haggerty","Junio C Hamano","William","Jeff King","David Turner"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"287796","messageId":"20160530103642.7213-1-william.duclot@ensimag.grenoble-inp.fr","threadId":"42483","inReplyTo":null,"subject":"[PATCH 0/2] strbuf: improve API","fromName":"William Duclot","fromEmail":"william.duclot@ensimag.grenoble-inp.fr","sentAt":"2016-05-30T10:36:40Z","receivedAt":"2016-05-30T10:36:40Z","isPatch":true,"sender":{"key":"william.duclot@ensimag.grenoble-inp.fr","avatar":null},"body":"This patch series implements an improvment of the strbuf API, allowing\nstrbuf to use preallocated memory. This makes strbuf fit to be used\nin performance-critical operations.\n\nThe first patch is simply a preparatory work, adding tests for\nexisting strbuf implementation.\nMost of the work is made in the second patch: handle pre-allocated\nmemory, extend the API, document it and test it.\n\nAs said in the second commit, the idea comes from Michael Haggerty.\n\nWilliam Duclot (2):\n strbuf: add tests\n strbuf: allow to use preallocated memory\n\nMakefile | 1 +\nstrbuf.c | 68 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----\nstrbuf.h | 31 +++++++++++++++++++++++++++++--\nt/helper/test-strbuf.c | 111 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\nt/t0082-strbuf.sh | 47 +++++++++++++++++++++++++++++++++++++++++++++++\n5 files changed, 251 insertions(+), 7 deletions(-)\n"},{"id":"287797","messageId":"20160530103642.7213-2-william.duclot@ensimag.grenoble-inp.fr","threadId":"42483","inReplyTo":"20160530103642.7213-1-william.duclot@ensimag.grenoble-inp.fr","subject":"[PATCH 1/2] strbuf: add tests","fromName":"William Duclot","fromEmail":"william.duclot@ensimag.grenoble-inp.fr","sentAt":"2016-05-30T10:36:41Z","receivedAt":"2016-05-30T10:36:41Z","isPatch":true,"sender":{"key":"william.duclot@ensimag.grenoble-inp.fr","avatar":null},"body":"Test the strbuf API. Being used throughout all Git the API could be\nconsidered tested, but adding specific tests makes it easier to improve\nand extend the API.\n---\n Makefile | 1 +\n t/helper/test-strbuf.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++\n t/t0082-strbuf.sh | 19 ++++++++++++++\n 3 files changed, 89 insertions(+)\n create mode 100644 t/helper/test-strbuf.c\n create mode 100755 t/t0082-strbuf.sh\n\ndiff --git a/Makefile b/Makefile\nindex 3f03366..dc84f43 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -613,6 +613,7 @@ TEST_PROGRAMS_NEED_X += test-scrap-cache-tree\n TEST_PROGRAMS_NEED_X += test-sha1\n TEST_PROGRAMS_NEED_X += test-sha1-array\n TEST_PROGRAMS_NEED_X += test-sigchain\n+TEST_PROGRAMS_NEED_X += test-strbuf\n TEST_PROGRAMS_NEED_X += test-string-list\n TEST_PROGRAMS_NEED_X += test-submodule-config\n TEST_PROGRAMS_NEED_X += test-subprocess\ndiff --git a/t/helper/test-strbuf.c b/t/helper/test-strbuf.c\nnew file mode 100644\nindex 0000000..622f627\n--- /dev/null\n+++ b/t/helper/test-strbuf.c\n@@ -0,0 +1,69 @@\n+#include \"git-compat-util.h\"\n+#include \"strbuf.h\"\n+\n+/*\n+ * Check behavior on usual use cases\n+ */\n+int test_usual(struct strbuf *sb)\n+{\n+\tsize_t size, old_alloc;\n+\tchar *res, *old_buf, *str_test = malloc(5*sizeof(char));\n+\tstrbuf_grow(sb, 1);\n+\tstrcpy(str_test, \"test\");\n+\told_alloc = sb->alloc;\n+\tstrbuf_grow(sb, 1000);\n+\tif (old_alloc == sb->alloc)\n+\t\tdie(\"strbuf_grow does not realloc the buffer as expected\");\n+\told_buf = sb->buf;\n+\tres = strbuf_detach(sb, &size);\n+\tif (res != old_buf)\n+\t\tdie(\"strbuf_detach does not return the expected buffer\");\n+\tfree(res);\n+\n+\tstrcpy(str_test, \"test\");\n+\tstrbuf_attach(sb, (void *)str_test, strlen(str_test), sizeof(str_test));\n+\tres = strbuf_detach(sb, &size);\n+\tif (res != str_test)\n+\t\tdie(\"strbuf_detach does not return the expected buffer\");\n+\tfree(res);\n+\tstrbuf_release(sb);\n+\n+\treturn 0;\n+}\n+\n+int main(int argc, char *argv[])\n+{\n+\tsize_t size = 1;\n+\tstruct strbuf sb;\n+\tchar str_test[5] = \"test\";\n+\tchar str_foo[7] = \"foo\";\n+\n+\tif (argc != 2)\n+\t\tusage(\"test-strbuf mode\");\n+\n+\tif (!strcmp(argv[1], \"basic_grow\")) {\n+\t\t/*\n+\t\t * Check if strbuf_grow(0) allocate a new NUL-terminated buffer\n+\t\t */\n+\t\tstrbuf_init(&sb, 0);\n+\t\tstrbuf_grow(&sb, 0);\n+\t\tif (sb.buf == strbuf_slopbuf)\n+\t\t\tdie(\"strbuf_grow failed to alloc memory\");\n+\t\tstrbuf_release(&sb);\n+\t\tif (sb.buf != strbuf_slopbuf)\n+\t\t\tdie(\"strbuf_release does not reinitialize the strbuf\");\n+\t} else if (!strcmp(argv[1], \"strbuf_check_behavior\")) {\n+\t\tstrbuf_init(&sb, 0);\n+\t\treturn test_usual(&sb);\n+\t} else if (!strcmp(argv[1], \"grow_overflow\")) {\n+\t\t/*\n+\t\t * size_t overflow: should die()\n+\t\t */\n+\t\tstrbuf_init(&sb, 1000);\n+\t\tstrbuf_grow(&sb, maximum_unsigned_value_of_type((size_t)1));\n+\t} else {\n+\t\tusage(\"test-strbuf mode\");\n+\t}\n+\n+\treturn 0;\n+}\ndiff --git a/t/t0082-strbuf.sh b/t/t0082-strbuf.sh\nnew file mode 100755\nindex 0000000..0800d26\n--- /dev/null\n+++ b/t/t0082-strbuf.sh\n@@ -0,0 +1,19 @@\n+#!/bin/sh\n+\n+test_description=\"Test the strbuf API.\n+\"\n+. ./test-lib.sh\n+\n+test_expect_success 'basic test on strbuf_grow()' '\n+\ttest-strbuf basic_grow\n+'\n+\n+test_expect_success 'check strbuf behavior in usual use cases ' '\n+\ttest-strbuf strbuf_check_behavior\n+'\n+\n+test_expect_success 'overflow while calling strbuf_grow' '\n+\ttest_must_fail test-strbuf grow_overflow\n+'\n+\n+test_done\n-- \n2.8.2.403.ge2646ba.dirty\n"},{"id":"287798","messageId":"20160530103642.7213-3-william.duclot@ensimag.grenoble-inp.fr","threadId":"42483","inReplyTo":"20160530103642.7213-1-william.duclot@ensimag.grenoble-inp.fr","subject":"[PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"William Duclot","fromEmail":"william.duclot@ensimag.grenoble-inp.fr","sentAt":"2016-05-30T10:36:42Z","receivedAt":"2016-05-30T10:36:42Z","isPatch":true,"sender":{"key":"william.duclot@ensimag.grenoble-inp.fr","avatar":null},"body":"It is unfortunate that it is currently impossible to use a strbuf\nwithout doing a memory allocation. So code like\n\nvoid f()\n{\n char path[PATH_MAX];\n ...\n}\n\ntypically gets turned into either\n\nvoid f()\n{\n struct strbuf path;\n strbuf_add(&path, ...); <-- does a malloc\n ...\n strbuf_release(&path); <-- does a free\n}\n\nwhich costs extra memory allocations, or\n\nvoid f()\n{\n static struct strbuf path;\n strbuf_add(&path, ...);\n ...\n strbuf_setlen(&path, 0);\n}\n\nwhich, by using a static variable, avoids most of the malloc/free\noverhead, but makes the function unsafe to use recursively or from\nmultiple threads. Those limitations prevent strbuf to be used in\nperformance-critical operations.\n\nTHE IDEA\n--------\n\nThe idea here is to enhance strbuf to allow it to use memory that it\ndoesn't own (for example, stack-allocated memory), while (optionally)\nallowing it to switch over to using allocated memory if the string grows\npast the size of the pre-allocated buffer.\n\nAPI ENHANCEMENT\n---------------\n\nAll functions of the API can still be reliably called without\nknowledge of the initialization (normal/preallocated/fixed) with the\nexception that strbuf_grow() may die() if the string try to overflow a\nfixed buffer.\n\nThe API contract is still respected:\n\n- The API users may peek strbuf.buf in-place until they perform an\n operation that makes it longer (at which point the .buf pointer\n may point at a new piece of memory).\n\n- The API users may strbuf_detach() to obtain a piece of memory that\n belongs to them (at which point the strbuf becomes empty), hence\n needs to be freed by the callers.\n\nFull credit to Michael Haggerty for the idea and most of the wording of\nthis commit (http://mid.gmane.org/53512DB6.1070600@alum.mit.edu). The\nimplementation and bugs are all mine.\n\nSigned-off by: William Duclot \nSigned-off by: Simon Rabourg \nSigned-off by: Matthieu Moy \n---\n strbuf.c | 68 ++++++++++++++++++++++++++++++++++++++++++++++----\n strbuf.h | 31 +++++++++++++++++++++--\n t/helper/test-strbuf.c | 42 +++++++++++++++++++++++++++++++\n t/t0082-strbuf.sh | 28 +++++++++++++++++++++\n 4 files changed, 162 insertions(+), 7 deletions(-)\n\ndiff --git a/strbuf.c b/strbuf.c\nindex 1ba600b..527b986 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -1,6 +1,14 @@\n #include \"cache.h\"\n #include \"refs.h\"\n #include \"utf8.h\"\n+#include \n+\n+/**\n+ * Flags\n+ * --------------\n+ */\n+#define STRBUF_OWNS_MEMORY 1\n+#define STRBUF_FIXED_MEMORY (1 << 1)\n \n int starts_with(const char *str, const char *prefix)\n {\n@@ -20,16 +28,37 @@ char strbuf_slopbuf[1];\n \n void strbuf_init(struct strbuf *sb, size_t hint)\n {\n+\tsb->flags = 0;\n \tsb->alloc = sb->len = 0;\n \tsb->buf = strbuf_slopbuf;\n \tif (hint)\n \t\tstrbuf_grow(sb, hint);\n }\n \n+void strbuf_wrap_preallocated(struct strbuf *sb, char *path_buf,\n+\t\t\t size_t path_buf_len, size_t alloc_len)\n+{\n+\tif (!path_buf)\n+\t\tdie(\"you try to use a NULL buffer to initialize a strbuf\");\n+\n+\tstrbuf_init(sb, 0);\n+\tstrbuf_attach(sb, path_buf, path_buf_len, alloc_len);\n+\tsb->flags &= ~STRBUF_OWNS_MEMORY;\n+\tsb->flags &= ~STRBUF_FIXED_MEMORY;\n+}\n+\n+void strbuf_wrap_fixed(struct strbuf *sb, char *path_buf,\n+\t\t size_t path_buf_len, size_t alloc_len)\n+{\n+\tstrbuf_wrap_preallocated(sb, path_buf, path_buf_len, alloc_len);\n+\tsb->flags |= STRBUF_FIXED_MEMORY;\n+}\n+\n void strbuf_release(struct strbuf *sb)\n {\n \tif (sb->alloc) {\n-\t\tfree(sb->buf);\n+\t\tif (sb->flags & STRBUF_OWNS_MEMORY)\n+\t\t\tfree(sb->buf);\n \t\tstrbuf_init(sb, 0);\n \t}\n }\n@@ -38,7 +67,11 @@ char *strbuf_detach(struct strbuf *sb, size_t *sz)\n {\n \tchar *res;\n \tstrbuf_grow(sb, 0);\n-\tres = sb->buf;\n+\tif (sb->flags & STRBUF_OWNS_MEMORY)\n+\t\tres = sb->buf;\n+\telse\n+\t\tres = xmemdupz(sb->buf, sb->alloc - 1);\n+\n \tif (sz)\n \t\t*sz = sb->len;\n \tstrbuf_init(sb, 0);\n@@ -51,6 +84,8 @@ void strbuf_attach(struct strbuf *sb, void *buf, size_t len, size_t alloc)\n \tsb->buf = buf;\n \tsb->len = len;\n \tsb->alloc = alloc;\n+\tsb->flags |= STRBUF_OWNS_MEMORY;\n+\tsb->flags &= ~STRBUF_FIXED_MEMORY;\n \tstrbuf_grow(sb, 0);\n \tsb->buf[sb->len] = '\\0';\n }\n@@ -61,9 +96,32 @@ void strbuf_grow(struct strbuf *sb, size_t extra)\n \tif (unsigned_add_overflows(extra, 1) ||\n \t unsigned_add_overflows(sb->len, extra + 1))\n \t\tdie(\"you want to use way too much memory\");\n-\tif (new_buf)\n-\t\tsb->buf = NULL;\n-\tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n+\tif ((sb->flags & STRBUF_FIXED_MEMORY) && sb->len + extra + 1 > sb->alloc)\n+\t\tdie(\"you try to make a string overflow the buffer of a fixed strbuf\");\n+\n+\t/*\n+\t * ALLOC_GROW may do a realloc() if needed, so we must not use it on\n+\t * a buffer the strbuf doesn't own\n+\t */\n+\tif (sb->flags & STRBUF_OWNS_MEMORY) {\n+\t\tif (new_buf)\n+\t\t\tsb->buf = NULL;\n+\t\tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n+\t} else {\n+\t\t/*\n+\t\t * The strbuf doesn't own the buffer: to avoid to realloc it,\n+\t\t * the strbuf needs to use a new buffer without freeing the old\n+\t\t */\n+\t\tif (sb->len + extra + 1 > sb->alloc) {\n+\t\t\tsize_t new_alloc = MAX(sb->len + extra + 1, alloc_nr(sb->alloc));\n+\t\t\tchar *buf = xmalloc(new_alloc);\n+\t\t\tmemcpy(buf, sb->buf, sb->alloc);\n+\t\t\tsb->buf = buf;\n+\t\t\tsb->alloc = new_alloc;\n+\t\t\tsb->flags |= STRBUF_OWNS_MEMORY;\n+\t\t}\n+\t}\n+\n \tif (new_buf)\n \t\tsb->buf[0] = '\\0';\n }\ndiff --git a/strbuf.h b/strbuf.h\nindex 7987405..634759c 100644\n--- a/strbuf.h\n+++ b/strbuf.h\n@@ -11,11 +11,16 @@\n * A strbuf is NUL terminated for convenience, but no function in the\n * strbuf API actually relies on the string being free of NULs.\n *\n+ * You can avoid the malloc/free overhead of `strbuf_init()`, `strbuf_add()` and\n+ * `strbuf_release()` by wrapping pre-allocated memory (stack-allocated for\n+ * example) using `strbuf_wrap_preallocated()` or `strbuf_wrap_fixed()`.\n+ *\n * strbufs have some invariants that are very important to keep in mind:\n *\n * - The `buf` member is never NULL, so it can be used in any usual C\n * string operations safely. strbuf's _have_ to be initialized either by\n- * `strbuf_init()` or by `= STRBUF_INIT` before the invariants, though.\n+ * `strbuf_init()`, `= STRBUF_INIT`, `strbuf_wrap_preallocated()` or\n+ * `strbuf_wrap_fixed()` before the invariants, though.\n *\n * Do *not* assume anything on what `buf` really is (e.g. if it is\n * allocated memory or not), use `strbuf_detach()` to unwrap a memory\n@@ -62,13 +67,14 @@\n * access to the string itself.\n */\n struct strbuf {\n+\tunsigned int flags;\n \tsize_t alloc;\n \tsize_t len;\n \tchar *buf;\n };\n \n extern char strbuf_slopbuf[];\n-#define STRBUF_INIT { 0, 0, strbuf_slopbuf }\n+#define STRBUF_INIT { 0, 0, 0, strbuf_slopbuf }\n \n /**\n * Life Cycle Functions\n@@ -81,6 +87,25 @@ extern char strbuf_slopbuf[];\n */\n extern void strbuf_init(struct strbuf *, size_t);\n \n+/**\n+ * Allow the caller to give a pre-allocated piece of memory for the strbuf\n+ * to use. It is possible then to strbuf_grow() the string past the size of the\n+ * pre-allocated buffer: a new buffer will be allocated. The pre-allocated\n+ * buffer will never be freed.\n+ */\n+void strbuf_wrap_preallocated(struct strbuf *sb, char *path_buf,\n+\t\t\t size_t path_buf_len, size_t alloc_len);\n+\n+/**\n+ * Allow the caller to give a pre-allocated piece of memory for the strbuf\n+ * to use and indicate that the strbuf must use exclusively this buffer,\n+ * never realloc() it or allocate a new one. It means that the string can\n+ * be manipulated but cannot overflow the pre-allocated buffer. The\n+ * pre-allocated buffer will never be freed.\n+ */\n+void strbuf_wrap_fixed(struct strbuf *sb, char *path_buf,\n+\t\t size_t path_buf_len, size_t alloc_len);\n+\n /**\n * Release a string buffer and the memory it used. You should not use the\n * string buffer after using this function, unless you initialize it again.\n@@ -91,6 +116,8 @@ extern void strbuf_release(struct strbuf *);\n * Detach the string from the strbuf and returns it; you now own the\n * storage the string occupies and it is your responsibility from then on\n * to release it with `free(3)` when you are done with it.\n+ * Must allocate a copy of the buffer in case of a preallocated/fixed buffer.\n+ * Performance-critical operations have to be aware of this.\n */\n extern char *strbuf_detach(struct strbuf *, size_t *);\n \ndiff --git a/t/helper/test-strbuf.c b/t/helper/test-strbuf.c\nindex 622f627..1aaacb5 100644\n--- a/t/helper/test-strbuf.c\n+++ b/t/helper/test-strbuf.c\n@@ -61,6 +61,48 @@ int main(int argc, char *argv[])\n \t\t */\n \t\tstrbuf_init(&sb, 1000);\n \t\tstrbuf_grow(&sb, maximum_unsigned_value_of_type((size_t)1));\n+\t} else if (!strcmp(argv[1], \"preallocated_check_behavior\")) {\n+\t\tstrbuf_wrap_preallocated(&sb, (void *)str_test,\n+\t\t\t\t\t strlen(str_test), sizeof(str_test));\n+\t\treturn test_usual(&sb);\n+\t} else if (!strcmp(argv[1], \"preallocated_NULL\")) {\n+\t\t/*\n+\t\t * Violation of invariant \"strbuf must not be NULL\": should die()\n+\t\t */\n+\t\tstrbuf_wrap_preallocated(&sb, NULL, 0, sizeof(str_test));\n+\t} else if (!strcmp(argv[1], \"grow_fixed_overflow\")) {\n+\t\t/*\n+\t\t * Overflowing the buffer of a fixed strbuf: should die()\n+\t\t */\n+\t\tstrbuf_wrap_fixed(&sb, (void *)str_foo,\n+\t\t\t\t strlen(str_foo), sizeof(str_foo));\n+\t\tstrbuf_grow(&sb, 3);\n+\t\tstrbuf_grow(&sb, 1000);\n+\t} else if (!strcmp(argv[1], \"grow_fixed_overflow_min\")) {\n+\t\t/*\n+\t\t * Minimum strbuf_grow() for overflowing a fixed strbuf: should die()\n+\t\t */\n+\t\tstrbuf_wrap_fixed(&sb, (void *)str_foo,\n+\t\t\t\t strlen(str_foo), sizeof(str_foo));\n+\t\tstrbuf_grow(&sb, 4);\n+\t} else if (!strcmp(argv[1], \"grow_fixed_success\")) {\n+\t\tstrbuf_wrap_fixed(&sb, (void *)str_foo,\n+\t\t\t\t strlen(str_foo), sizeof(str_foo));\n+\t\tstrbuf_grow(&sb, 3);\n+\t} else if (!strcmp(argv[1], \"detach_fixed\")) {\n+\t\tchar *buf;\n+\t\tstrbuf_wrap_fixed(&sb, (void *)str_test,\n+\t\t\t\t strlen(str_test), sizeof(str_test));\n+\t\tbuf = strbuf_detach(&sb, &size);\n+\t\tif (str_test == buf)\n+\t\t\tdie(\"strbuf_detach does not copy the buffer\");\n+\t\tfree(buf);\n+\t} else if (!strcmp(argv[1], \"release_fixed\")) {\n+\t\tstrbuf_wrap_fixed(&sb, (void *)str_test, strlen(str_test),\n+\t\t\t\t sizeof(sb) + 1);\n+\t\tstrbuf_release(&sb);\n+\t\tif (sb.buf != strbuf_slopbuf)\n+\t\t\tdie(\"strbuf_release does not reinitialize the strbuf\");\n \t} else {\n \t\tusage(\"test-strbuf mode\");\n \t}\ndiff --git a/t/t0082-strbuf.sh b/t/t0082-strbuf.sh\nindex 0800d26..5de909d 100755\n--- a/t/t0082-strbuf.sh\n+++ b/t/t0082-strbuf.sh\n@@ -16,4 +16,32 @@ test_expect_success 'overflow while calling strbuf_grow' '\n \ttest_must_fail test-strbuf grow_overflow\n '\n \n+test_expect_success 'check preallocated strbuf behavior in usual use cases' '\n+\ttest-strbuf preallocated_check_behavior\n+'\n+\n+test_expect_success 'strbuf_wrap_preallocated NULL initialization' '\n+\ttest_must_fail test-strbuf preallocated_NULL\n+'\n+\n+test_expect_success 'strbuf_grow with wrap_fixed overflow' '\n+\ttest_must_fail test-strbuf grow_fixed_overflow\n+'\n+\n+test_expect_success 'strbuf_grow with wrap_fixed minimum overflow' '\n+\ttest_must_fail test-strbuf grow_fixed_overflow_min\n+'\n+\n+test_expect_success 'strbuf_grow with wrap_fixed in a successful case' '\n+\ttest-strbuf grow_fixed_success\n+'\n+\n+test_expect_success 'stbuf_detach with wrap_fixed memory' '\n+\ttest-strbuf detach_fixed\n+'\n+\n+test_expect_success 'stbuf_release with wrap_fixed memory' '\n+\ttest-strbuf release_fixed\n+'\n+\n test_done\n-- \n2.8.2.403.ge2646ba.dirty\n"},{"id":"287809","messageId":"alpine.DEB.2.20.1605301323310.4449@virtualbox","threadId":"42483","inReplyTo":"20160530103642.7213-2-william.duclot@ensimag.grenoble-inp.fr","subject":"Re: [PATCH 1/2] strbuf: add tests","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2016-05-30T11:26:48Z","receivedAt":"2016-05-30T11:26:48Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi William,\n\nOn Mon, 30 May 2016, William Duclot wrote:\n\n> Test the strbuf API. Being used throughout all Git the API could be\n> considered tested, but adding specific tests makes it easier to improve\n> and extend the API.\n> ---\n\nThe commit message makes sense. Please add your sign-off.\n\n> Makefile | 1 +\n> t/helper/test-strbuf.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++\n> t/t0082-strbuf.sh | 19 ++++++++++++++\n> 3 files changed, 89 insertions(+)\n> create mode 100644 t/helper/test-strbuf.c\n> create mode 100755 t/t0082-strbuf.sh\n> \n> diff --git a/Makefile b/Makefile\n> index 3f03366..dc84f43 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -613,6 +613,7 @@ TEST_PROGRAMS_NEED_X += test-scrap-cache-tree\n> TEST_PROGRAMS_NEED_X += test-sha1\n> TEST_PROGRAMS_NEED_X += test-sha1-array\n> TEST_PROGRAMS_NEED_X += test-sigchain\n> +TEST_PROGRAMS_NEED_X += test-strbuf\n> TEST_PROGRAMS_NEED_X += test-string-list\n> TEST_PROGRAMS_NEED_X += test-submodule-config\n> TEST_PROGRAMS_NEED_X += test-subprocess\n> diff --git a/t/helper/test-strbuf.c b/t/helper/test-strbuf.c\n> new file mode 100644\n> index 0000000..622f627\n> --- /dev/null\n> +++ b/t/helper/test-strbuf.c\n> @@ -0,0 +1,69 @@\n> +#include \"git-compat-util.h\"\n> +#include \"strbuf.h\"\n> +\n> +/*\n> + * Check behavior on usual use cases\n> + */\n> +int test_usual(struct strbuf *sb)\n\nI have to admit that I would prefer a more concrete name. And since your\nother tests are more fine-grained, maybe this one could be split into\nmultiple separate ones, too?\n\n> +{\n> +\tsize_t size, old_alloc;\n> +\tchar *res, *old_buf, *str_test = malloc(5*sizeof(char));\n\nOur convention is to list the initialized variables first, the\nuninitialized ones after that, and for readability an empty line is\nrecommended after the variable declaration block.\n\n> +\tstrbuf_grow(sb, 1);\n> +\tstrcpy(str_test, \"test\");\n> +\told_alloc = sb->alloc;\n> +\tstrbuf_grow(sb, 1000);\n> +\tif (old_alloc == sb->alloc)\n> +\t\tdie(\"strbuf_grow does not realloc the buffer as expected\");\n> +\told_buf = sb->buf;\n> +\tres = strbuf_detach(sb, &size);\n> +\tif (res != old_buf)\n> +\t\tdie(\"strbuf_detach does not return the expected buffer\");\n> +\tfree(res);\n> +\n> +\tstrcpy(str_test, \"test\");\n> +\tstrbuf_attach(sb, (void *)str_test, strlen(str_test), sizeof(str_test));\n> +\tres = strbuf_detach(sb, &size);\n> +\tif (res != str_test)\n> +\t\tdie(\"strbuf_detach does not return the expected buffer\");\n> +\tfree(res);\n> +\tstrbuf_release(sb);\n> +\n> +\treturn 0;\n> +}\n> +\n> +int main(int argc, char *argv[])\n> +{\n> +\tsize_t size = 1;\n> +\tstruct strbuf sb;\n\nThe common theme in our source code seems to initialize using\nSTRBUF_INIT... Let's use that paradigm here, too?\n\n> +\tchar str_test[5] = \"test\";\n> +\tchar str_foo[7] = \"foo\";\n> +\n> +\tif (argc != 2)\n> +\t\tusage(\"test-strbuf mode\");\n\nA nice and convenient way to do command-line parsing is to use the\nparse-options API, in this case with OPT_CMDMODE. This would also give us\na chance to document the command modes in a nice and succinct way: as help\nstrings.\n\n> +\n> +\tif (!strcmp(argv[1], \"basic_grow\")) {\n> +\t\t/*\n> +\t\t * Check if strbuf_grow(0) allocate a new NUL-terminated buffer\n\ns/allocate/&s/\n\n> +\t\t */\n> +\t\tstrbuf_init(&sb, 0);\n> +\t\tstrbuf_grow(&sb, 0);\n> +\t\tif (sb.buf == strbuf_slopbuf)\n> +\t\t\tdie(\"strbuf_grow failed to alloc memory\");\n> +\t\tstrbuf_release(&sb);\n> +\t\tif (sb.buf != strbuf_slopbuf)\n> +\t\t\tdie(\"strbuf_release does not reinitialize the strbuf\");\n> +\t} else if (!strcmp(argv[1], \"strbuf_check_behavior\")) {\n> +\t\tstrbuf_init(&sb, 0);\n> +\t\treturn test_usual(&sb);\n> +\t} else if (!strcmp(argv[1], \"grow_overflow\")) {\n> +\t\t/*\n> +\t\t * size_t overflow: should die()\n> +\t\t */\n> +\t\tstrbuf_init(&sb, 1000);\n> +\t\tstrbuf_grow(&sb, maximum_unsigned_value_of_type((size_t)1));\n\nA comment \"If this does not die(), fall through to returning success, to\nindicate an error\" might be nice here.\n\n> +\t} else {\n> +\t\tusage(\"test-strbuf mode\");\n> +\t}\n> +\n> +\treturn 0;\n> +}\n> diff --git a/t/t0082-strbuf.sh b/t/t0082-strbuf.sh\n> new file mode 100755\n> index 0000000..0800d26\n> --- /dev/null\n> +++ b/t/t0082-strbuf.sh\n> @@ -0,0 +1,19 @@\n> +#!/bin/sh\n> +\n> +test_description=\"Test the strbuf API.\n> +\"\n\nThis description does not need a new-line, and existing one-liner test\ndescriptions seem not to be terminated by a period.\n\nThe rest of this patch looks good.\n\nCiao,\nJohannes\n"},{"id":"287808","messageId":"1069084553.156626.1464607928755.JavaMail.zimbra@ensimag.grenoble-inp.fr","threadId":"42483","inReplyTo":"20160530103642.7213-1-william.duclot@ensimag.grenoble-inp.fr","subject":"Re: [PATCH 0/2] strbuf: improve API","fromName":"Remi Galan Alfonso","fromEmail":"remi.galan-alfonso@ensimag.grenoble-inp.fr","sentAt":"2016-05-30T11:32:08Z","receivedAt":"2016-05-30T11:32:08Z","isPatch":true,"sender":{"key":"remi.galan-alfonso@ensimag.grenoble-inp.fr","avatar":"https://avatars.githubusercontent.com/u/12509162?v=4"},"body":"William Duclot writes:\n> This patch series implements an improvment of the strbuf API, allowing\n> strbuf to use preallocated memory. This makes strbuf fit to be used\n> in performance-critical operations.\n> \n> The first patch is simply a preparatory work, adding tests for\n> existing strbuf implementation.\n> Most of the work is made in the second patch: handle pre-allocated\n> memory, extend the API, document it and test it.\n\nSeems interesting, however do you have any test/example that would\nshow the difference of performance between using these optimizations\nand not using them?\n\nSuch values would make a nice addition to help convince people that\nyour series is interesting to have and use.\n\nThanks,\nRémi\n"},{"id":"287810","messageId":"vpqwpmbg3oq.fsf@anie.imag.fr","threadId":"42483","inReplyTo":"20160530103642.7213-2-william.duclot@ensimag.grenoble-inp.fr","subject":"Re: [PATCH 1/2] strbuf: add tests","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@grenoble-inp.fr","sentAt":"2016-05-30T11:56:05Z","receivedAt":"2016-05-30T11:56:05Z","isPatch":true,"sender":{"key":"matthieu.moy@grenoble-inp.fr","avatar":"https://gravatar.com/avatar/72c8a2705971a25dfaff23cece15130d405685845d911aedd5667ace277f3fc5?d=mp&s=160"},"body":"I agree with Johannes' remarks. I'd add two style nits:\n\nWilliam Duclot writes:\n\n> --- /dev/null\n> +++ b/t/helper/test-strbuf.c\n> @@ -0,0 +1,69 @@\n> +#include \"git-compat-util.h\"\n> +#include \"strbuf.h\"\n> +\n> +/*\n> + * Check behavior on usual use cases\n> + */\n> +int test_usual(struct strbuf *sb)\n> +{\n> +\tsize_t size, old_alloc;\n> +\tchar *res, *old_buf, *str_test = malloc(5*sizeof(char));\n\nSpaces around binary operator.\n\n> +int main(int argc, char *argv[])\n> +{\n> +\tsize_t size = 1;\n> +\tstruct strbuf sb;\n> +\tchar str_test[5] = \"test\";\n> +\tchar str_foo[7] = \"foo\";\n> +\n> +\tif (argc != 2)\n> +\t\tusage(\"test-strbuf mode\");\n> +\n> +\tif (!strcmp(argv[1], \"basic_grow\")) {\n> +\t\t/*\n> +\t\t * Check if strbuf_grow(0) allocate a new NUL-terminated buffer\n> +\t\t */\n> +\t\tstrbuf_init(&sb, 0);\n> +\t\tstrbuf_grow(&sb, 0);\n> +\t\tif (sb.buf == strbuf_slopbuf)\n> +\t\t\tdie(\"strbuf_grow failed to alloc memory\");\n> +\t\tstrbuf_release(&sb);\n> +\t\tif (sb.buf != strbuf_slopbuf)\n> +\t\t\tdie(\"strbuf_release does not reinitialize the strbuf\");\n> +\t} else if (!strcmp(argv[1], \"strbuf_check_behavior\")) {\n> +\t\tstrbuf_init(&sb, 0);\n> +\t\treturn test_usual(&sb);\n\nI think the command (\"strbuf_check_behavior\") should have the same name\nas the function (test_usual). This avoids one indirection for the\nreader going from t*.sh file to the actual test code.\n\n-- \nMatthieu Moy\nhttp://www-verimag.imag.fr/~moy/\n"},{"id":"287811","messageId":"alpine.DEB.2.20.1605301326530.4449@virtualbox","threadId":"42483","inReplyTo":"20160530103642.7213-3-william.duclot@ensimag.grenoble-inp.fr","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2016-05-30T12:13:52Z","receivedAt":"2016-05-30T12:13:52Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi William,\n\nOn Mon, 30 May 2016, William Duclot wrote:\n\n> It is unfortunate that it is currently impossible to use a strbuf\n> without doing a memory allocation. So code like\n> \n> void f()\n> {\n> char path[PATH_MAX];\n> ...\n> }\n> \n> typically gets turned into either\n> \n> void f()\n> {\n> struct strbuf path;\n> strbuf_add(&path, ...); <-- does a malloc\n> ...\n> strbuf_release(&path); <-- does a free\n> }\n> \n> which costs extra memory allocations, or\n> \n> void f()\n> {\n> static struct strbuf path;\n> strbuf_add(&path, ...);\n> ...\n> strbuf_setlen(&path, 0);\n> }\n> \n> which, by using a static variable, avoids most of the malloc/free\n> overhead, but makes the function unsafe to use recursively or from\n> multiple threads. Those limitations prevent strbuf to be used in\n> performance-critical operations.\n\nThis description is nice and verbose, but maybe something like this would\nintroduce the subject in a quicker manner?\n\n\tWhen working e.g. with file paths or with dates, strbuf's\n\tmalloc()/free() dance of strbufs can be easily avoided: as\n\ta sensible initial buffer size is already known, it can be\n\tallocated on the heap.\n\nThe rest of the commit message flows nicely.\n\n> diff --git a/strbuf.c b/strbuf.c\n> index 1ba600b..527b986 100644\n> --- a/strbuf.c\n> +++ b/strbuf.c\n> @@ -1,6 +1,14 @@\n> #include \"cache.h\"\n> #include \"refs.h\"\n> #include \"utf8.h\"\n> +#include \n\nWhy?\n\n> +/**\n> + * Flags\n> + * --------------\n> + */\n> +#define STRBUF_OWNS_MEMORY 1\n> +#define STRBUF_FIXED_MEMORY (1 << 1)\n\n>From reading the commit message, I expected STRBUF_OWNS_MEMORY.\nSTRBUF_FIXED_MEMORY still needs to be explained.\n\n> @@ -20,16 +28,37 @@ char strbuf_slopbuf[1];\n> \n> void strbuf_init(struct strbuf *sb, size_t hint)\n> {\n> +\tsb->flags = 0;\n> \tsb->alloc = sb->len = 0;\n> \tsb->buf = strbuf_slopbuf;\n> \tif (hint)\n> \t\tstrbuf_grow(sb, hint);\n> }\n> \n> +void strbuf_wrap_preallocated(struct strbuf *sb, char *path_buf,\n> +\t\t\t size_t path_buf_len, size_t alloc_len)\n> +{\n> +\tif (!path_buf)\n> +\t\tdie(\"you try to use a NULL buffer to initialize a strbuf\");\n> +\n> +\tstrbuf_init(sb, 0);\n> +\tstrbuf_attach(sb, path_buf, path_buf_len, alloc_len);\n> +\tsb->flags &= ~STRBUF_OWNS_MEMORY;\n> +\tsb->flags &= ~STRBUF_FIXED_MEMORY;\n\nShorter: sb->flags &= ~(STRBUF_OWNS_MEMORY | STRBUF_FIXED_MEMORY);\n\n> +}\n> +\n> +void strbuf_wrap_fixed(struct strbuf *sb, char *path_buf,\n> +\t\t size_t path_buf_len, size_t alloc_len)\n> +{\n> +\tstrbuf_wrap_preallocated(sb, path_buf, path_buf_len, alloc_len);\n> +\tsb->flags |= STRBUF_FIXED_MEMORY;\n> +}\n\nRather than letting strbuf_wrap_preallocated() set sb->flags &=\n~FIXED_MEMORY only to revert that decision right away, a static function\ncould be called by both strbuf_wrap_preallocated() and\nstrbuf_wrap_fixed().\n\n> void strbuf_release(struct strbuf *sb)\n> {\n> \tif (sb->alloc) {\n> -\t\tfree(sb->buf);\n> +\t\tif (sb->flags & STRBUF_OWNS_MEMORY)\n> +\t\t\tfree(sb->buf);\n> \t\tstrbuf_init(sb, 0);\n> \t}\n\nShould we not reset the flags here, too?\n\n> @@ -38,7 +67,11 @@ char *strbuf_detach(struct strbuf *sb, size_t *sz)\n> {\n> \tchar *res;\n> \tstrbuf_grow(sb, 0);\n> -\tres = sb->buf;\n> +\tif (sb->flags & STRBUF_OWNS_MEMORY)\n> +\t\tres = sb->buf;\n> +\telse\n> +\t\tres = xmemdupz(sb->buf, sb->alloc - 1);\n\nThis looks like a usage to be avoided: if we plan to detach the buffer,\nanyway, there is no good reason to allocate it on the heap first. I would\nat least issue a warning here.\n\n> @@ -51,6 +84,8 @@ void strbuf_attach(struct strbuf *sb, void *buf, size_t len, size_t alloc)\n> \tsb->buf = buf;\n> \tsb->len = len;\n> \tsb->alloc = alloc;\n> +\tsb->flags |= STRBUF_OWNS_MEMORY;\n> +\tsb->flags &= ~STRBUF_FIXED_MEMORY;\n> \tstrbuf_grow(sb, 0);\n> \tsb->buf[sb->len] = '\\0';\n> }\n> @@ -61,9 +96,32 @@ void strbuf_grow(struct strbuf *sb, size_t extra)\n> \tif (unsigned_add_overflows(extra, 1) ||\n> \t unsigned_add_overflows(sb->len, extra + 1))\n> \t\tdie(\"you want to use way too much memory\");\n> -\tif (new_buf)\n> -\t\tsb->buf = NULL;\n> -\tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n> +\tif ((sb->flags & STRBUF_FIXED_MEMORY) && sb->len + extra + 1 > sb->alloc)\n> +\t\tdie(\"you try to make a string overflow the buffer of a fixed strbuf\");\n\nWe try to avoid running over 80 columns/row. This message could be\nmore to the point: cannot grow fixed string\n\n> +\t/*\n> +\t * ALLOC_GROW may do a realloc() if needed, so we must not use it on\n> +\t * a buffer the strbuf doesn't own\n> +\t */\n> +\tif (sb->flags & STRBUF_OWNS_MEMORY) {\n> +\t\tif (new_buf)\n> +\t\t\tsb->buf = NULL;\n> +\t\tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n> +\t} else {\n> +\t\t/*\n> +\t\t * The strbuf doesn't own the buffer: to avoid to realloc it,\n> +\t\t * the strbuf needs to use a new buffer without freeing the old\n> +\t\t */\n> +\t\tif (sb->len + extra + 1 > sb->alloc) {\n> +\t\t\tsize_t new_alloc = MAX(sb->len + extra + 1, alloc_nr(sb->alloc));\n> +\t\t\tchar *buf = xmalloc(new_alloc);\n> +\t\t\tmemcpy(buf, sb->buf, sb->alloc);\n> +\t\t\tsb->buf = buf;\n> +\t\t\tsb->alloc = new_alloc;\n> +\t\t\tsb->flags |= STRBUF_OWNS_MEMORY;\n> +\t\t}\n> +\t}\n> +\n> \tif (new_buf)\n> \t\tsb->buf[0] = '\\0';\n> }\n> diff --git a/strbuf.h b/strbuf.h\n> index 7987405..634759c 100644\n> --- a/strbuf.h\n> +++ b/strbuf.h\n> @@ -11,11 +11,16 @@\n> * A strbuf is NUL terminated for convenience, but no function in the\n> * strbuf API actually relies on the string being free of NULs.\n> *\n> + * You can avoid the malloc/free overhead of `strbuf_init()`, `strbuf_add()` and\n> + * `strbuf_release()` by wrapping pre-allocated memory (stack-allocated for\n> + * example) using `strbuf_wrap_preallocated()` or `strbuf_wrap_fixed()`.\n> + *\n> * strbufs have some invariants that are very important to keep in mind:\n> *\n> * - The `buf` member is never NULL, so it can be used in any usual C\n> * string operations safely. strbuf's _have_ to be initialized either by\n> - * `strbuf_init()` or by `= STRBUF_INIT` before the invariants, though.\n> + * `strbuf_init()`, `= STRBUF_INIT`, `strbuf_wrap_preallocated()` or\n> + * `strbuf_wrap_fixed()` before the invariants, though.\n> *\n> * Do *not* assume anything on what `buf` really is (e.g. if it is\n> * allocated memory or not), use `strbuf_detach()` to unwrap a memory\n> @@ -62,13 +67,14 @@\n> * access to the string itself.\n> */\n> struct strbuf {\n> +\tunsigned int flags;\n> \tsize_t alloc;\n> \tsize_t len;\n> \tchar *buf;\n> };\n> \n> extern char strbuf_slopbuf[];\n> -#define STRBUF_INIT { 0, 0, strbuf_slopbuf }\n> +#define STRBUF_INIT { 0, 0, 0, strbuf_slopbuf }\n\nIf I am not mistaken, to preserve the existing behavior the initial flags\nshould be 1 (own memory).\n\nBTW this demonstrates that it may not be a good idea to declare the\n\"flags\" field globally but then make the actual flags private.\n\nAlso: similar use cases in Git used :1 flags (see e.g. the \"configured\"\nfield in credential.h).\n\nCiao,\nJohannes\n"},{"id":"287812","messageId":"vpqlh2remhy.fsf@anie.imag.fr","threadId":"42483","inReplyTo":"20160530103642.7213-3-william.duclot@ensimag.grenoble-inp.fr","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@grenoble-inp.fr","sentAt":"2016-05-30T12:52:41Z","receivedAt":"2016-05-30T12:52:41Z","isPatch":true,"sender":{"key":"matthieu.moy@grenoble-inp.fr","avatar":"https://gravatar.com/avatar/72c8a2705971a25dfaff23cece15130d405685845d911aedd5667ace277f3fc5?d=mp&s=160"},"body":"William Duclot writes:\n\n> multiple threads. Those limitations prevent strbuf to be used in\n\nprevent strbuf from being used ...\n\n> API ENHANCEMENT\n> ---------------\n>\n> All functions of the API can still be reliably called without\n> knowledge of the initialization (normal/preallocated/fixed) with the\n> exception that strbuf_grow() may die() if the string try to overflow a\n\ns/try/tries/\n\n> @@ -20,16 +28,37 @@ char strbuf_slopbuf[1];\n> \n> void strbuf_init(struct strbuf *sb, size_t hint)\n> {\n> +\tsb->flags = 0;\n> \tsb->alloc = sb->len = 0;\n> \tsb->buf = strbuf_slopbuf;\n> \tif (hint)\n> \t\tstrbuf_grow(sb, hint);\n> }\n\nIf you set flags = 0 here, existing callers will have all flags off,\nincluding OWNS_MEMORY.\n\nI *think* this is OK, as sb->buf is currently pointing to\nstrbuf_slopbuf, which the the strbuf doesn't own. But that is too subtle\nto go without an explanatory comment IMHO.\n\nAlso, doesn't this make the \"new_buf\" case useless in strbuf_grow?\n\nWith your patch, the code looks like:\n\nvoid strbuf_grow(struct strbuf *sb, size_t extra)\n{\n\tint new_buf = !sb->alloc;\n...\n\tif (sb->flags & STRBUF_OWNS_MEMORY) {\n\t\tif (new_buf) // <---------------------------------------- (1)\n\t\t\tsb->buf = NULL;\n\t\tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n\t} else {\n\t\t/*\n\t\t * The strbuf doesn't own the buffer: to avoid to realloc it,\n\t\t * the strbuf needs to use a new buffer without freeing the old\n\t\t */\n\t\tif (sb->len + extra + 1 > sb->alloc) {\n\t\t\tsize_t new_alloc = MAX(sb->len + extra + 1, alloc_nr(sb->alloc));\n\t\t\tchar *buf = xmalloc(new_alloc);\n\t\t\tmemcpy(buf, sb->buf, sb->alloc);\n\t\t\tsb->buf = buf;\n\t\t\tsb->alloc = new_alloc;\n\t\t\tsb->flags |= STRBUF_OWNS_MEMORY;\n\t\t}\n\t}\n\n\tif (new_buf) // <---------------------------------------- (2)\n\t\tsb->buf[0] = '\\0';\n}\n\nI think (1) is now dead code, since sb->alloc == 0 implies that\nSTRBUF_OWNS_MEMORY is set. (2) seems redundant since you've just\nmemcpy-ed the existing '\\0' into the buffer.\n\n> +void strbuf_wrap_preallocated(struct strbuf *sb, char *path_buf,\n> +\t\t\t size_t path_buf_len, size_t alloc_len)\n> +{\n> +\tif (!path_buf)\n> +\t\tdie(\"you try to use a NULL buffer to initialize a strbuf\");\n> +\n> +\tstrbuf_init(sb, 0);\n> +\tstrbuf_attach(sb, path_buf, path_buf_len, alloc_len);\n> +\tsb->flags &= ~STRBUF_OWNS_MEMORY;\n> +\tsb->flags &= ~STRBUF_FIXED_MEMORY;\n> +}\n\nstrbuf_wrap_preallocated seem very close to strbuf_attach. I'd rather\nsee a symmetric code sharing like\n\nvoid strbuf_attach_internal(struct strbuf *sb, ..., unsigned int flags)\n\nand then strbuf_attach() and strbuf_wrap_preallocated() become\nstraightforward wrappers around it.\n\nThis would avoid setting and then unsetting STRBUF_OWNS_MEMORY (the\nperformance impact is probably small, but it looks weird to set the flag\nand then unset it right away).\n\nAfter your patch, there are differences between\nstrbuf_wrap_preallocated() which I think are inconsistencies:\n\n* strbuf_attach() does not check for NULL buffer, but it doesn't accept\n them either if I read correctly. It would make sense to add the check\n to strbuf_attach(), but it's weird to have the performance-critical\n oriented function do the expensive stuff that the\n non-performance-critical one doesn't.\n\n* strbuf_attach() calls strbuf_release(), which allows reusing an\n existing strbuf. strbuf_wrap_preallocated() calls strbuf_init which\n would override silently any previous content. I think strbuf_attach()\n does the right thing here.\n\n (And I'm probably the one who misguided you to do this)\n\n In any case, you probably want to include calls to strbuf_attach() and\n strbuf_wrap_*() functions on existing non-empty strbufs.\n\n> +void strbuf_wrap_fixed(struct strbuf *sb, char *path_buf,\n> +\t\t size_t path_buf_len, size_t alloc_len)\n> +{\n> +\tstrbuf_wrap_preallocated(sb, path_buf, path_buf_len, alloc_len);\n> +\tsb->flags |= STRBUF_FIXED_MEMORY;\n> +}\n\nAnd this could become a 3rd caller of strbuf_attach_internal().\n\n> @@ -61,9 +96,32 @@ void strbuf_grow(struct strbuf *sb, size_t extra)\n> \tif (unsigned_add_overflows(extra, 1) ||\n> \t unsigned_add_overflows(sb->len, extra + 1))\n> \t\tdie(\"you want to use way too much memory\");\n> -\tif (new_buf)\n> -\t\tsb->buf = NULL;\n> -\tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n> +\tif ((sb->flags & STRBUF_FIXED_MEMORY) && sb->len + extra + 1 > sb->alloc)\n> +\t\tdie(\"you try to make a string overflow the buffer of a fixed strbuf\");\n> +\n> +\t/*\n> +\t * ALLOC_GROW may do a realloc() if needed, so we must not use it on\n> +\t * a buffer the strbuf doesn't own\n> +\t */\n> +\tif (sb->flags & STRBUF_OWNS_MEMORY) {\n> +\t\tif (new_buf)\n> +\t\t\tsb->buf = NULL;\n> +\t\tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n> +\t} else {\n> +\t\t/*\n> +\t\t * The strbuf doesn't own the buffer: to avoid to realloc it,\n> +\t\t * the strbuf needs to use a new buffer without freeing the old\n> +\t\t */\n> +\t\tif (sb->len + extra + 1 > sb->alloc) {\n> +\t\t\tsize_t new_alloc = MAX(sb->len + extra + 1, alloc_nr(sb->alloc));\n> +\t\t\tchar *buf = xmalloc(new_alloc);\n> +\t\t\tmemcpy(buf, sb->buf, sb->alloc);\n\nI think you want to memcpy only sb->len + 1 bytes. Here, you're\nmemcpy-ing the allocated-but-not-initialized part of the array.\n\nxmemdupz can probably simplify the code too (either you include the '\\0'\nin what memcpy copies, or you let xmemdupz add it).\n\n> +/**\n> + * Allow the caller to give a pre-allocated piece of memory for the strbuf\n> + * to use. It is possible then to strbuf_grow() the string past the size of the\n> + * pre-allocated buffer: a new buffer will be allocated. The pre-allocated\n\nTo make it clearer: \"a new buffer will then be allocated\"?\n\n> +/**\n> + * Allow the caller to give a pre-allocated piece of memory for the strbuf\n> + * to use and indicate that the strbuf must use exclusively this buffer,\n> + * never realloc() it or allocate a new one. It means that the string can\n> + * be manipulated but cannot overflow the pre-allocated buffer. The\n> + * pre-allocated buffer will never be freed.\n> + */\n\nPerhaps say explicitly that although the allocated buffer has a fixed\nsize, the string itself can grow as long as it does not overflow the\nbuffer?\n\n> @@ -91,6 +116,8 @@ extern void strbuf_release(struct strbuf *);\n> * Detach the string from the strbuf and returns it; you now own the\n> * storage the string occupies and it is your responsibility from then on\n> * to release it with `free(3)` when you are done with it.\n> + * Must allocate a copy of the buffer in case of a preallocated/fixed buffer.\n> + * Performance-critical operations have to be aware of this.\n\nBetter than just warn about performance, you can give the alternative.\n\n-- \nMatthieu Moy\nhttp://www-verimag.imag.fr/~moy/\n"},{"id":"287813","messageId":"953965621.202433.1464614453377.JavaMail.zimbra@ensimag.grenoble-inp.fr","threadId":"42483","inReplyTo":"alpine.DEB.2.20.1605301326530.4449@virtualbox","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"William Duclot","fromEmail":"william.duclot@ensimag.grenoble-inp.fr","sentAt":"2016-05-30T13:20:53Z","receivedAt":"2016-05-30T13:20:53Z","isPatch":true,"sender":{"key":"william.duclot@ensimag.grenoble-inp.fr","avatar":null},"body":"Johannes Schindelin writes:\n> On Mon, 30 May 2016, William Duclot wrote:\n> \n>> It is unfortunate that it is currently impossible to use a strbuf\n>> without doing a memory allocation. So code like\n>> \n>> void f()\n>> {\n>> char path[PATH_MAX];\n>> ...\n>> }\n>> \n>> typically gets turned into either\n>> \n>> void f()\n>> {\n>> struct strbuf path;\n>> strbuf_add(&path, ...); <-- does a malloc\n>> ...\n>> strbuf_release(&path); <-- does a free\n>> }\n>> \n>> which costs extra memory allocations, or\n>> \n>> void f()\n>> {\n>> static struct strbuf path;\n>> strbuf_add(&path, ...);\n>> ...\n>> strbuf_setlen(&path, 0);\n>> }\n>> \n>> which, by using a static variable, avoids most of the malloc/free\n>> overhead, but makes the function unsafe to use recursively or from\n>> multiple threads. Those limitations prevent strbuf to be used in\n>> performance-critical operations.\n> \n> This description is nice and verbose, but maybe something like this would\n> introduce the subject in a quicker manner?\n> \n> \tWhen working e.g. with file paths or with dates, strbuf's\n> \tmalloc()/free() dance of strbufs can be easily avoided: as\n> \ta sensible initial buffer size is already known, it can be\n> \tallocated on the heap.\n\nstrbuf already allow to indicate a sensible initial buffer size thanks\nto strbuf_init() second parameter. The main perk of pre-allocation\nis to use stack-allocated memory, and not heap-allocated :)\nUnless I misunderstood your message?\n\n>> diff --git a/strbuf.c b/strbuf.c\n>> index 1ba600b..527b986 100644\n>> --- a/strbuf.c\n>> +++ b/strbuf.c\n>> @@ -1,6 +1,14 @@\n>> #include \"cache.h\"\n>> #include \"refs.h\"\n>> #include \"utf8.h\"\n>> +#include \n> \n> Why?\n\nFor the MAX macro. It may be a teeny tiny overkill\n\n>> +/**\n>> + * Flags\n>> + * --------------\n>> + */\n>> +#define STRBUF_OWNS_MEMORY 1\n>> +#define STRBUF_FIXED_MEMORY (1 << 1)\n> \n> From reading the commit message, I expected STRBUF_OWNS_MEMORY.\n> STRBUF_FIXED_MEMORY still needs to be explained.\n\nYes, that seems right\n\n>> @@ -20,16 +28,37 @@ char strbuf_slopbuf[1];\n>> \n>> void strbuf_init(struct strbuf *sb, size_t hint)\n>> {\n>> +\tsb->flags = 0;\n>> \tsb->alloc = sb->len = 0;\n>> \tsb->buf = strbuf_slopbuf;\n>> \tif (hint)\n>> \t\tstrbuf_grow(sb, hint);\n>> }\n>> \n>> +void strbuf_wrap_preallocated(struct strbuf *sb, char *path_buf,\n>> +\t\t\t size_t path_buf_len, size_t alloc_len)\n>> +{\n>> +\tif (!path_buf)\n>> +\t\tdie(\"you try to use a NULL buffer to initialize a strbuf\");\n>> +\n>> +\tstrbuf_init(sb, 0);\n>> +\tstrbuf_attach(sb, path_buf, path_buf_len, alloc_len);\n>> +\tsb->flags &= ~STRBUF_OWNS_MEMORY;\n>> +\tsb->flags &= ~STRBUF_FIXED_MEMORY;\n> \n> Shorter: sb->flags &= ~(STRBUF_OWNS_MEMORY | STRBUF_FIXED_MEMORY);\n\nOkay with me\n\n>> +}\n>> +\n>> +void strbuf_wrap_fixed(struct strbuf *sb, char *path_buf,\n>> +\t\t size_t path_buf_len, size_t alloc_len)\n>> +{\n>> +\tstrbuf_wrap_preallocated(sb, path_buf, path_buf_len, alloc_len);\n>> +\tsb->flags |= STRBUF_FIXED_MEMORY;\n>> +}\n> \n> Rather than letting strbuf_wrap_preallocated() set sb->flags &=\n> ~FIXED_MEMORY only to revert that decision right away, a static function\n> could be called by both strbuf_wrap_preallocated() and\n> strbuf_wrap_fixed().\n\nMakes sense\n\n>> void strbuf_release(struct strbuf *sb)\n>> {\n>> \tif (sb->alloc) {\n>> -\t\tfree(sb->buf);\n>> +\t\tif (sb->flags & STRBUF_OWNS_MEMORY)\n>> +\t\t\tfree(sb->buf);\n>> \t\tstrbuf_init(sb, 0);\n>> \t}\n> \n> Should we not reset the flags here, too?\n\nWell, strbuf_init() reset the flags. The only way to have !sb->alloc\nis that strbuf has been initialized and never used (even alloc_grow(0)\nset sb->alloc=1), so sb==STRBUF_INIT, so the flags don't have to be reset \n\n>> @@ -38,7 +67,11 @@ char *strbuf_detach(struct strbuf *sb, size_t *sz)\n>> {\n>> \tchar *res;\n>> \tstrbuf_grow(sb, 0);\n>> -\tres = sb->buf;\n>> +\tif (sb->flags & STRBUF_OWNS_MEMORY)\n>> +\t\tres = sb->buf;\n>> +\telse\n>> +\t\tres = xmemdupz(sb->buf, sb->alloc - 1);\n> \n> This looks like a usage to be avoided: if we plan to detach the buffer,\n> anyway, there is no good reason to allocate it on the heap first. I would\n> at least issue a warning here.\n\nstrbuf_detach() guarantees to return heap-allocated memory, that the caller\ncan use however he want and that he'll have to free. If the strbuf doesn't\nown the memory, it cannot return the buf attribute directly because:\n- The memory belong to someone else (so the caller can't use it however\nhe want)\n- The caller can't have the responsibility to free (because the memory\nbelong to someone else)\n- The memory may not even be heap-allocated\n\n>> @@ -51,6 +84,8 @@ void strbuf_attach(struct strbuf *sb, void *buf, size_t\n>> len, size_t alloc)\n>> \tsb->buf = buf;\n>> \tsb->len = len;\n>> \tsb->alloc = alloc;\n>> +\tsb->flags |= STRBUF_OWNS_MEMORY;\n>> +\tsb->flags &= ~STRBUF_FIXED_MEMORY;\n>> \tstrbuf_grow(sb, 0);\n>> \tsb->buf[sb->len] = '\\0';\n>> }\n>> @@ -61,9 +96,32 @@ void strbuf_grow(struct strbuf *sb, size_t extra)\n>> \tif (unsigned_add_overflows(extra, 1) ||\n>> \t unsigned_add_overflows(sb->len, extra + 1))\n>> \t\tdie(\"you want to use way too much memory\");\n>> -\tif (new_buf)\n>> -\t\tsb->buf = NULL;\n>> -\tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n>> +\tif ((sb->flags & STRBUF_FIXED_MEMORY) && sb->len + extra + 1 > sb->alloc)\n>> +\t\tdie(\"you try to make a string overflow the buffer of a fixed strbuf\");\n> \n> We try to avoid running over 80 columns/row. This message could be\n> more to the point: cannot grow fixed string\n\nWhat is fixed is the buffer, not the string. I'll shrink that under 80 columns\n \n>> extern char strbuf_slopbuf[];\n>> -#define STRBUF_INIT { 0, 0, strbuf_slopbuf }\n>> +#define STRBUF_INIT { 0, 0, 0, strbuf_slopbuf }\n> \n> If I am not mistaken, to preserve the existing behavior the initial flags\n> should be 1 (own memory).\n\nstrbuf_slopbuf is a buffer that doesn't belong to any strbuf (because it's\nshared between all just-initialized strbufs). If STRBUF_OWNS_MEMORY was\nset, strbuf_slopbuf could be freed (which is impossible because it is\nshared AND even more because it is stack-allocated) \n\n> BTW this demonstrates that it may not be a good idea to declare the\n> \"flags\" field globally but then make the actual flags private.\n\nI'm not sure what you mean here?\n\n> Also: similar use cases in Git used :1 flags (see e.g. the \"configured\"\n> field in credential.h).\n\nI think that keeping an obscure `flags` attribute may be better, as they\nshould only be useful for internal operations and the user shouldn't mess\nwith it. Keeping it a `private` attribute, in a way\n"},{"id":"287816","messageId":"559442672.168369.1464615740454.JavaMail.zimbra@ensimag.grenoble-inp.fr","threadId":"42483","inReplyTo":"alpine.DEB.2.20.1605301323310.4449@virtualbox","subject":"Re: [PATCH 1/2] strbuf: add tests","fromName":"Simon Rabourg","fromEmail":"simon.rabourg@ensimag.grenoble-inp.fr","sentAt":"2016-05-30T13:42:20Z","receivedAt":"2016-05-30T13:42:20Z","isPatch":true,"sender":{"key":"simon.rabourg@ensimag.grenoble-inp.fr","avatar":null},"body":"Hi Johannes, \n\nI'm William's teammate on this feature. \n\nJohannes Schindelin writes:\n> Hi William,\n> \n> On Mon, 30 May 2016, William Duclot wrote:\n> \n> > Test the strbuf API. Being used throughout all Git the API could be\n> > considered tested, but adding specific tests makes it easier to improve\n> > and extend the API.\n> > ---\n> \n> The commit message makes sense. Please add your sign-off.\n> \n\nWe forgot to add the sign-off, we will fix that in the V2.\n\n> > Makefile | 1 +\n> > t/helper/test-strbuf.c | 69\n> > ++++++++++++++++++++++++++++++++++++++++++++++++++\n> > t/t0082-strbuf.sh | 19 ++++++++++++++\n> > 3 files changed, 89 insertions(+)\n> > create mode 100644 t/helper/test-strbuf.c\n> > create mode 100755 t/t0082-strbuf.sh\n> > \n> > diff --git a/Makefile b/Makefile\n> > index 3f03366..dc84f43 100644\n> > --- a/Makefile\n> > +++ b/Makefile\n> > @@ -613,6 +613,7 @@ TEST_PROGRAMS_NEED_X += test-scrap-cache-tree\n> > TEST_PROGRAMS_NEED_X += test-sha1\n> > TEST_PROGRAMS_NEED_X += test-sha1-array\n> > TEST_PROGRAMS_NEED_X += test-sigchain\n> > +TEST_PROGRAMS_NEED_X += test-strbuf\n> > TEST_PROGRAMS_NEED_X += test-string-list\n> > TEST_PROGRAMS_NEED_X += test-submodule-config\n> > TEST_PROGRAMS_NEED_X += test-subprocess\n> > diff --git a/t/helper/test-strbuf.c b/t/helper/test-strbuf.c\n> > new file mode 100644\n> > index 0000000..622f627\n> > --- /dev/null\n> > +++ b/t/helper/test-strbuf.c\n> > @@ -0,0 +1,69 @@\n> > +#include \"git-compat-util.h\"\n> > +#include \"strbuf.h\"\n> > +\n> > +/*\n> > + * Check behavior on usual use cases\n> > + */\n> > +int test_usual(struct strbuf *sb)\n> \n> I have to admit that I would prefer a more concrete name. And since your\n> other tests are more fine-grained, maybe this one could be split into\n> multiple separate ones, too?\n> \n\nWe will rename this function.\nWe thought that one complete function would be convenient to test \nthe usual API's behaviour. We are not sure how that change would be useful?\n\n> > +{\n> > +\tsize_t size, old_alloc;\n> > +\tchar *res, *old_buf, *str_test = malloc(5*sizeof(char));\n> \n> Our convention is to list the initialized variables first, the\n> uninitialized ones after that, and for readability an empty line is\n> recommended after the variable declaration block.\n\nOK, seems more readable.\n\n> > +\tstrbuf_grow(sb, 1);\n> > +\tstrcpy(str_test, \"test\");\n> > +\told_alloc = sb->alloc;\n> > +\tstrbuf_grow(sb, 1000);\n> > +\tif (old_alloc == sb->alloc)\n> > +\t\tdie(\"strbuf_grow does not realloc the buffer as expected\");\n> > +\told_buf = sb->buf;\n> > +\tres = strbuf_detach(sb, &size);\n> > +\tif (res != old_buf)\n> > +\t\tdie(\"strbuf_detach does not return the expected buffer\");\n> > +\tfree(res);\n> > +\n> > +\tstrcpy(str_test, \"test\");\n> > +\tstrbuf_attach(sb, (void *)str_test, strlen(str_test), sizeof(str_test));\n> > +\tres = strbuf_detach(sb, &size);\n> > +\tif (res != str_test)\n> > +\t\tdie(\"strbuf_detach does not return the expected buffer\");\n> > +\tfree(res);\n> > +\tstrbuf_release(sb);\n> > +\n> > +\treturn 0;\n> > +}\n> > +\n> > +int main(int argc, char *argv[])\n> > +{\n> > +\tsize_t size = 1;\n> > +\tstruct strbuf sb;\n> \n> The common theme in our source code seems to initialize using\n> STRBUF_INIT... Let's use that paradigm here, too?\n\nWe will add a test to check that initializing with srtbuf_init(...) is the\nsame as initializing with STRBUF_INIT. \n\n> \n> > +\tchar str_test[5] = \"test\";\n> > +\tchar str_foo[7] = \"foo\";\n> > +\n> > +\tif (argc != 2)\n> > +\t\tusage(\"test-strbuf mode\");\n> \n> A nice and convenient way to do command-line parsing is to use the\n> parse-options API, in this case with OPT_CMDMODE. This would also give us\n> a chance to document the command modes in a nice and succinct way: as help\n> strings.\n> \n\nTrue, we're going to make that change.\n\n\n> > +\n> > +\tif (!strcmp(argv[1], \"basic_grow\")) {\n> > +\t\t/*\n> > +\t\t * Check if strbuf_grow(0) allocate a new NUL-terminated buffer\n> \n> s/allocate/&s/\n> \n> > +\t\t */\n> > +\t\tstrbuf_init(&sb, 0);\n> > +\t\tstrbuf_grow(&sb, 0);\n> > +\t\tif (sb.buf == strbuf_slopbuf)\n> > +\t\t\tdie(\"strbuf_grow failed to alloc memory\");\n> > +\t\tstrbuf_release(&sb);\n> > +\t\tif (sb.buf != strbuf_slopbuf)\n> > +\t\t\tdie(\"strbuf_release does not reinitialize the strbuf\");\n> > +\t} else if (!strcmp(argv[1], \"strbuf_check_behavior\")) {\n> > +\t\tstrbuf_init(&sb, 0);\n> > +\t\treturn test_usual(&sb);\n> > +\t} else if (!strcmp(argv[1], \"grow_overflow\")) {\n> > +\t\t/*\n> > +\t\t * size_t overflow: should die()\n> > +\t\t */\n> > +\t\tstrbuf_init(&sb, 1000);\n> > +\t\tstrbuf_grow(&sb, maximum_unsigned_value_of_type((size_t)1));\n> \n> A comment \"If this does not die(), fall through to returning success, to\n> indicate an error\" might be nice here.\n\nAgreed.\n\n> > +\t} else {\n> > +\t\tusage(\"test-strbuf mode\");\n> > +\t}\n> > +\n> > +\treturn 0;\n> > +}\n> > diff --git a/t/t0082-strbuf.sh b/t/t0082-strbuf.sh\n> > new file mode 100755\n> > index 0000000..0800d26\n> > --- /dev/null\n> > +++ b/t/t0082-strbuf.sh\n> > @@ -0,0 +1,19 @@\n> > +#!/bin/sh\n> > +\n> > +test_description=\"Test the strbuf API.\n> > +\"\n> \n> This description does not need a new-line, and existing one-liner test\n> descriptions seem not to be terminated by a period.\n\nOK.\n\n> The rest of this patch looks good.\n> \n> Ciao,\n> Johannes\n> \n\nThanks for the Review,\nSimon Rabourg\n"},{"id":"287818","messageId":"1639412597.204503.1464617754937.JavaMail.zimbra@ensimag.grenoble-inp.fr","threadId":"42483","inReplyTo":"vpqlh2remhy.fsf@anie.imag.fr","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"William Duclot","fromEmail":"william.duclot@ensimag.grenoble-inp.fr","sentAt":"2016-05-30T14:15:54Z","receivedAt":"2016-05-30T14:15:54Z","isPatch":true,"sender":{"key":"william.duclot@ensimag.grenoble-inp.fr","avatar":null},"body":"Matthieu Moy writes:\n> William Duclot writes:\n> \n>> @@ -20,16 +28,37 @@ char strbuf_slopbuf[1];\n>> \n>> void strbuf_init(struct strbuf *sb, size_t hint)\n>> {\n>> +\tsb->flags = 0;\n>> \tsb->alloc = sb->len = 0;\n>> \tsb->buf = strbuf_slopbuf;\n>> \tif (hint)\n>> \t\tstrbuf_grow(sb, hint);\n>> }\n> \n> If you set flags = 0 here, existing callers will have all flags off,\n> including OWNS_MEMORY.\n> \n> I *think* this is OK, as sb->buf is currently pointing to\n> strbuf_slopbuf, which the the strbuf doesn't own. But that is too subtle\n> to go without an explanatory comment IMHO.\n\nRight\n\n> \n> Also, doesn't this make the \"new_buf\" case useless in strbuf_grow?\n> \n> With your patch, the code looks like:\n> \n> void strbuf_grow(struct strbuf *sb, size_t extra)\n> {\n> \tint new_buf = !sb->alloc;\n> ...\n> \tif (sb->flags & STRBUF_OWNS_MEMORY) {\n> \t\tif (new_buf) // <---------------------------------------- (1)\n> \t\t\tsb->buf = NULL;\n> \t\tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n> \t} else {\n> \t\t/*\n> \t\t * The strbuf doesn't own the buffer: to avoid to realloc it,\n> \t\t * the strbuf needs to use a new buffer without freeing the old\n> \t\t */\n> \t\tif (sb->len + extra + 1 > sb->alloc) {\n> \t\t\tsize_t new_alloc = MAX(sb->len + extra + 1, alloc_nr(sb->alloc));\n> \t\t\tchar *buf = xmalloc(new_alloc);\n> \t\t\tmemcpy(buf, sb->buf, sb->alloc);\n> \t\t\tsb->buf = buf;\n> \t\t\tsb->alloc = new_alloc;\n> \t\t\tsb->flags |= STRBUF_OWNS_MEMORY;\n> \t\t}\n> \t}\n> \n> \tif (new_buf) // <---------------------------------------- (2)\n> \t\tsb->buf[0] = '\\0';\n> }\n> \n> I think (1) is now dead code, since sb->alloc == 0 implies that\n> STRBUF_OWNS_MEMORY is set. (2) seems redundant since you've just\n> memcpy-ed the existing '\\0' into the buffer.\n\nYou're right for (1), I hadn't noticed that.\nFor (2), we'll still have to set sb->buf[new_alloc-1]='\\0' after the memcpy, if we\nhave sb->alloc==0 then the memcpy won't copy it.\n\n>> +void strbuf_wrap_preallocated(struct strbuf *sb, char *path_buf,\n>> +\t\t\t size_t path_buf_len, size_t alloc_len)\n>> +{\n>> +\tif (!path_buf)\n>> +\t\tdie(\"you try to use a NULL buffer to initialize a strbuf\");\n>> +\n>> +\tstrbuf_init(sb, 0);\n>> +\tstrbuf_attach(sb, path_buf, path_buf_len, alloc_len);\n>> +\tsb->flags &= ~STRBUF_OWNS_MEMORY;\n>> +\tsb->flags &= ~STRBUF_FIXED_MEMORY;\n>> +}\n> \n> strbuf_wrap_preallocated seem very close to strbuf_attach. I'd rather\n> see a symmetric code sharing like\n> \n> void strbuf_attach_internal(struct strbuf *sb, ..., unsigned int flags)\n> \n> and then strbuf_attach() and strbuf_wrap_preallocated() become\n> straightforward wrappers around it.\n> \n> This would avoid setting and then unsetting STRBUF_OWNS_MEMORY (the\n> performance impact is probably small, but it looks weird to set the flag\n> and then unset it right away).\n\nWe'll refactor the code with Johannes' remarks and yours in mind\n\n> After your patch, there are differences between\n> strbuf_wrap_preallocated() which I think are inconsistencies:\n> \n> * strbuf_attach() does not check for NULL buffer, but it doesn't accept\n> them either if I read correctly. It would make sense to add the check\n> to strbuf_attach(), but it's weird to have the performance-critical\n> oriented function do the expensive stuff that the\n> non-performance-critical one doesn't.\n\nI agree that strbuf_attach should do the check (it seems strange that it\ndoesn't already do it, as the \"buffer never NULL\" invariant is not new).\nI don't understand your \"but\" part, what \"expensive stuff\" are you talking\nabout?\n\n> * strbuf_attach() calls strbuf_release(), which allows reusing an\n> existing strbuf. strbuf_wrap_preallocated() calls strbuf_init which\n> would override silently any previous content. I think strbuf_attach()\n> does the right thing here.\n>\n> In any case, you probably want to include calls to strbuf_attach() and\n> strbuf_wrap_*() functions on existing non-empty strbufs.\n>\n>> +void strbuf_wrap_fixed(struct strbuf *sb, char *path_buf,\n>> +\t\t size_t path_buf_len, size_t alloc_len)\n>> +{\n>> +\tstrbuf_wrap_preallocated(sb, path_buf, path_buf_len, alloc_len);\n>> +\tsb->flags |= STRBUF_FIXED_MEMORY;\n>> +}\n> \n> And this could become a 3rd caller of strbuf_attach_internal().\n\nTrue. We'll take care of that when refactoring\n\n>> @@ -61,9 +96,32 @@ void strbuf_grow(struct strbuf *sb, size_t extra)\n>> \tif (unsigned_add_overflows(extra, 1) ||\n>> \t unsigned_add_overflows(sb->len, extra + 1))\n>> \t\tdie(\"you want to use way too much memory\");\n>> -\tif (new_buf)\n>> -\t\tsb->buf = NULL;\n>> -\tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n>> +\tif ((sb->flags & STRBUF_FIXED_MEMORY) && sb->len + extra + 1 > sb->alloc)\n>> +\t\tdie(\"you try to make a string overflow the buffer of a fixed strbuf\");\n>> +\n>> +\t/*\n>> +\t * ALLOC_GROW may do a realloc() if needed, so we must not use it on\n>> +\t * a buffer the strbuf doesn't own\n>> +\t */\n>> +\tif (sb->flags & STRBUF_OWNS_MEMORY) {\n>> +\t\tif (new_buf)\n>> +\t\t\tsb->buf = NULL;\n>> +\t\tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n>> +\t} else {\n>> +\t\t/*\n>> +\t\t * The strbuf doesn't own the buffer: to avoid to realloc it,\n>> +\t\t * the strbuf needs to use a new buffer without freeing the old\n>> +\t\t */\n>> +\t\tif (sb->len + extra + 1 > sb->alloc) {\n>> +\t\t\tsize_t new_alloc = MAX(sb->len + extra + 1, alloc_nr(sb->alloc));\n>> +\t\t\tchar *buf = xmalloc(new_alloc);\n>> +\t\t\tmemcpy(buf, sb->buf, sb->alloc);\n> \n> I think you want to memcpy only sb->len + 1 bytes. Here, you're\n> memcpy-ing the allocated-but-not-initialized part of the array.\n> \n> xmemdupz can probably simplify the code too (either you include the '\\0'\n> in what memcpy copies, or you let xmemdupz add it).\n\nmemcpying sb->len+1 bytes is indeed enough.\nxmemdupz can only allocate the same size it will copy. Here we want to\nallocate `new_alloc` bytes but only copy `sb->alloc` bytes (or sb->len+1\nbytes, as you noticed)\n\n>> +/**\n>> + * Allow the caller to give a pre-allocated piece of memory for the strbuf\n>> + * to use. It is possible then to strbuf_grow() the string past the size\n>> of the\n>> + * pre-allocated buffer: a new buffer will be allocated. The pre-allocated\n> \n> To make it clearer: \"a new buffer will then be allocated\"?\n\nOK\n\n>> +/**\n>> + * Allow the caller to give a pre-allocated piece of memory for the strbuf\n>> + * to use and indicate that the strbuf must use exclusively this buffer,\n>> + * never realloc() it or allocate a new one. It means that the string can\n>> + * be manipulated but cannot overflow the pre-allocated buffer. The\n>> + * pre-allocated buffer will never be freed.\n>> + */\n> \n> Perhaps say explicitly that although the allocated buffer has a fixed\n> size, the string itself can grow as long as it does not overflow the\n> buffer?\n\nThat's what I meant by \"the string can be manipulated but cannot overflow\nthe pre-allocated buffer\". I'll try to reformulate\n\n>> @@ -91,6 +116,8 @@ extern void strbuf_release(struct strbuf *);\n>> * Detach the string from the strbuf and returns it; you now own the\n>> * storage the string occupies and it is your responsibility from then on\n>> * to release it with `free(3)` when you are done with it.\n>> + * Must allocate a copy of the buffer in case of a preallocated/fixed\n>> buffer.\n>> + * Performance-critical operations have to be aware of this.\n> \n> Better than just warn about performance, you can give the alternative.\n\nI'm not sure what you mean, I don't think there really is an alternative for\ndetaching a string?\n"},{"id":"287823","messageId":"vpqpos38vi4.fsf@anie.imag.fr","threadId":"42483","inReplyTo":"1639412597.204503.1464617754937.JavaMail.zimbra@ensimag.grenoble-inp.fr","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@grenoble-inp.fr","sentAt":"2016-05-30T14:34:43Z","receivedAt":"2016-05-30T14:34:43Z","isPatch":true,"sender":{"key":"matthieu.moy@grenoble-inp.fr","avatar":"https://gravatar.com/avatar/72c8a2705971a25dfaff23cece15130d405685845d911aedd5667ace277f3fc5?d=mp&s=160"},"body":"William Duclot writes:\n\n> Matthieu Moy writes:\n>\n>> void strbuf_grow(struct strbuf *sb, size_t extra)\n>> {\n>> \tint new_buf = !sb->alloc;\n>> ...\n>> \tif (sb->flags & STRBUF_OWNS_MEMORY) {\n>> \t\tif (new_buf) // <---------------------------------------- (1)\n>> \t\t\tsb->buf = NULL;\n>> \t\tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n>> \t} else {\n>> \t\t/*\n>> \t\t * The strbuf doesn't own the buffer: to avoid to realloc it,\n>> \t\t * the strbuf needs to use a new buffer without freeing the old\n>> \t\t */\n>> \t\tif (sb->len + extra + 1 > sb->alloc) {\n>> \t\t\tsize_t new_alloc = MAX(sb->len + extra + 1, alloc_nr(sb->alloc));\n>> \t\t\tchar *buf = xmalloc(new_alloc);\n>> \t\t\tmemcpy(buf, sb->buf, sb->alloc);\n>> \t\t\tsb->buf = buf;\n>> \t\t\tsb->alloc = new_alloc;\n>> \t\t\tsb->flags |= STRBUF_OWNS_MEMORY;\n>> \t\t}\n>> \t}\n>> \n>> \tif (new_buf) // <---------------------------------------- (2)\n>> \t\tsb->buf[0] = '\\0';\n>> }\n>> \n>> I think (1) is now dead code, since sb->alloc == 0 implies that\n>> STRBUF_OWNS_MEMORY is set. (2) seems redundant since you've just\n>> memcpy-ed the existing '\\0' into the buffer.\n>\n> You're right for (1), I hadn't noticed that.\n> For (2), we'll still have to set sb->buf[new_alloc-1]='\\0' after the memcpy, if we\n> have sb->alloc==0 then the memcpy won't copy it.\n\nThat sounds like one more reason to memcpy len + 1 bytes, and you'll get\nthe '\\0' copied.\n\n>> After your patch, there are differences between\n>> strbuf_wrap_preallocated() which I think are inconsistencies:\n>> \n>> * strbuf_attach() does not check for NULL buffer, but it doesn't accept\n>> them either if I read correctly. It would make sense to add the check\n>> to strbuf_attach(), but it's weird to have the performance-critical\n>> oriented function do the expensive stuff that the\n>> non-performance-critical one doesn't.\n>\n> I agree that strbuf_attach should do the check (it seems strange that it\n> doesn't already do it, as the \"buffer never NULL\" invariant is not new).\n> I don't understand your \"but\" part, what \"expensive stuff\" are you talking\n> about?\n\n\"expensive stuff\" was an exageration for \"== NULL\" test. It's not that\nexpensive, but costs a tiny bit of CPU time.\n\n> xmemdupz can only allocate the same size it will copy.\n\nIndeed, so forget about it.\n\n>>> +/**\n>>> + * Allow the caller to give a pre-allocated piece of memory for the strbuf\n>>> + * to use and indicate that the strbuf must use exclusively this buffer,\n>>> + * never realloc() it or allocate a new one. It means that the string can\n>>> + * be manipulated but cannot overflow the pre-allocated buffer. The\n>>> + * pre-allocated buffer will never be freed.\n>>> + */\n>> \n>> Perhaps say explicitly that although the allocated buffer has a fixed\n>> size, the string itself can grow as long as it does not overflow the\n>> buffer?\n>\n> That's what I meant by \"the string can be manipulated but cannot overflow\n> the pre-allocated buffer\". I'll try to reformulate\n\nMaybe \"the string can grow, but cannot overflow\"?\n\n>>> @@ -91,6 +116,8 @@ extern void strbuf_release(struct strbuf *);\n>>> * Detach the string from the strbuf and returns it; you now own the\n>>> * storage the string occupies and it is your responsibility from then on\n>>> * to release it with `free(3)` when you are done with it.\n>>> + * Must allocate a copy of the buffer in case of a preallocated/fixed\n>>> buffer.\n>>> + * Performance-critical operations have to be aware of this.\n>> \n>> Better than just warn about performance, you can give the alternative.\n>\n> I'm not sure what you mean, I don't think there really is an alternative for\n> detaching a string?\n\nSo, is the comment above saying \"You're doomed, there's no way you can\nget good performance anyway\"?\n\nThe alternative is just that you don't have to call strbuf_release since\nthe caller can access the .buf field and is already the one responsible\nfor freeing it when needed, and it's safe to just call strbuf_init() if\none needs to re-initialize the stbuf structure.\n\n-- \nMatthieu Moy\nhttp://www-verimag.imag.fr/~moy/\n"},{"id":"287826","messageId":"131406846.207070.1464621404690.JavaMail.zimbra@ensimag.grenoble-inp.fr","threadId":"42483","inReplyTo":"vpqpos38vi4.fsf@anie.imag.fr","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"William Duclot","fromEmail":"william.duclot@ensimag.grenoble-inp.fr","sentAt":"2016-05-30T15:16:44Z","receivedAt":"2016-05-30T15:16:44Z","isPatch":true,"sender":{"key":"william.duclot@ensimag.grenoble-inp.fr","avatar":null},"body":"Matthieu Moy writes:\n> William Duclot writes:\n> \n>> Matthieu Moy writes:\n>>>> +/**\n>>>> + * Allow the caller to give a pre-allocated piece of memory for the\n>>>> strbuf\n>>>> + * to use and indicate that the strbuf must use exclusively this buffer,\n>>>> + * never realloc() it or allocate a new one. It means that the string\n>>>> can\n>>>> + * be manipulated but cannot overflow the pre-allocated buffer. The\n>>>> + * pre-allocated buffer will never be freed.\n>>>> + */\n>>> \n>>> Perhaps say explicitly that although the allocated buffer has a fixed\n>>> size, the string itself can grow as long as it does not overflow the\n>>> buffer?\n>>\n>> That's what I meant by \"the string can be manipulated but cannot overflow\n>> the pre-allocated buffer\". I'll try to reformulate\n> \n> Maybe \"the string can grow, but cannot overflow\"?\n\nSeems OK\n\n>>>> @@ -91,6 +116,8 @@ extern void strbuf_release(struct strbuf *);\n>>>> * Detach the string from the strbuf and returns it; you now own the\n>>>> * storage the string occupies and it is your responsibility from then\n>>>> on\n>>>> * to release it with `free(3)` when you are done with it.\n>>>> + * Must allocate a copy of the buffer in case of a preallocated/fixed\n>>>> buffer.\n>>>> + * Performance-critical operations have to be aware of this.\n>>> \n>>> Better than just warn about performance, you can give the alternative.\n>>\n>> I'm not sure what you mean, I don't think there really is an alternative\n>> for\n>> detaching a string?\n> \n> So, is the comment above saying \"You're doomed, there's no way you can\n> get good performance anyway\"?\n> \n> The alternative is just that you don't have to call strbuf_release since\n> the caller can access the .buf field and is already the one responsible\n> for freeing it when needed, and it's safe to just call strbuf_init() if\n> one needs to re-initialize the stbuf structure.\n\nActually, if the user _needs_ to detach(), then yes he's doomed. Or more\nrealistically, he have to refactor so he'll don't need detach() (by being\nsure the strbuf is pre-allocated by himself for example).\nThe strbuf_release() function is not the problem here, it does nothing\nproblematic for performances. The problem is strbuf_wrap_preallocated(),\nbut you're right I can add a comment so the user know when he don't have\nto call it.\n"},{"id":"287855","messageId":"20160530215652.GA6456@glandium.org","threadId":"42483","inReplyTo":"20160530103642.7213-3-william.duclot@ensimag.grenoble-inp.fr","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2016-05-30T21:56:52Z","receivedAt":"2016-05-30T21:56:52Z","isPatch":true,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"> struct strbuf {\n> +\tunsigned int flags;\n> \tsize_t alloc;\n> \tsize_t len;\n> \tchar *buf;\n> };\n\nDepending whether the size of strbuf matters, it /might/ be worth\nconsidering some packing here. malloc() usually returns buffers that can\ncontain more data than what is requested. Which means allocation sizes\ncould be rounded and that wouldn't change the amount of allocated\nmemory. On glibc malloc_usable_size(malloc(1)) apparently returns 24.\nOn jemalloc, it's 4 or 8. It's in the same ballbark with many\nallocators.\n\nSo, it would be possible to round alloc such that it's always a multiple\nof, say, 4, and stick flags in the low, unused bits.\n\nWhether it's worth doing is another question.\n\nMike\n"},{"id":"287858","messageId":"1686469496.216457.1464648383516.JavaMail.zimbra@ensimag.grenoble-inp.fr","threadId":"42483","inReplyTo":"20160530215652.GA6456@glandium.org","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"William Duclot","fromEmail":"william.duclot@ensimag.grenoble-inp.fr","sentAt":"2016-05-30T22:46:23Z","receivedAt":"2016-05-30T22:46:23Z","isPatch":true,"sender":{"key":"william.duclot@ensimag.grenoble-inp.fr","avatar":null},"body":"Mike Hommey writes:\n>> struct strbuf {\n>> +\tunsigned int flags;\n>> \tsize_t alloc;\n>> \tsize_t len;\n>> \tchar *buf;\n>> };\n> \n> Depending whether the size of strbuf matters, it /might/ be worth\n> considering some packing here. malloc() usually returns buffers that can\n> contain more data than what is requested. Which means allocation sizes\n> could be rounded and that wouldn't change the amount of allocated\n> memory. On glibc malloc_usable_size(malloc(1)) apparently returns 24.\n> On jemalloc, it's 4 or 8. It's in the same ballbark with many\n> allocators.\n> \n> So, it would be possible to round alloc such that it's always a multiple\n> of, say, 4, and stick flags in the low, unused bits.\n\nIf I'm not mistaken, the memory allocated is not necessarily linear with\nthe size asked, depending on the algorithm used by the allocator and/or\nthe kernel. The system for exemple use powers of two, if the user asks\nfor exactly 2^x bytes, adding the space for the flags would lead to an\nallocation of 2^(x+1) bytes. Way worse than storing an unsigned.\nIf the allocator use a fibonnaci system, we can't even rely on multiples\nof 4 (or 2).\nI'm not sure the fibonnaci system is actually used by any allocator, but\nmy point is that I'm not sure it is a good thing to rely on such \nlow-level implementations.\n\n> Whether it's worth doing is another question.\n\nI'd say it is not, we generally lack time more than space, storing an\nunsigned seems very reasonable compared to operations involved in using\nmalloc() leftovers :)\nNot even talking about growing buffers, so realloc(), so a whole new set\nof problems...\n"},{"id":"287859","messageId":"20160530225029.GA9624@glandium.org","threadId":"42483","inReplyTo":"1686469496.216457.1464648383516.JavaMail.zimbra@ensimag.grenoble-inp.fr","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2016-05-30T22:50:29Z","receivedAt":"2016-05-30T22:50:29Z","isPatch":true,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Tue, May 31, 2016 at 12:46:23AM +0200, William Duclot wrote:\n> Mike Hommey writes:\n> >> struct strbuf {\n> >> +\tunsigned int flags;\n> >> \tsize_t alloc;\n> >> \tsize_t len;\n> >> \tchar *buf;\n> >> };\n> > \n> > Depending whether the size of strbuf matters, it /might/ be worth\n> > considering some packing here. malloc() usually returns buffers that can\n> > contain more data than what is requested. Which means allocation sizes\n> > could be rounded and that wouldn't change the amount of allocated\n> > memory. On glibc malloc_usable_size(malloc(1)) apparently returns 24.\n> > On jemalloc, it's 4 or 8. It's in the same ballbark with many\n> > allocators.\n> > \n> > So, it would be possible to round alloc such that it's always a multiple\n> > of, say, 4, and stick flags in the low, unused bits.\n> \n> If I'm not mistaken, the memory allocated is not necessarily linear with\n> the size asked, depending on the algorithm used by the allocator and/or\n> the kernel. The system for exemple use powers of two, if the user asks\n> for exactly 2^x bytes, adding the space for the flags would lead to an\n> allocation of 2^(x+1) bytes.\n\nNo, it would not. If you requested 129 bytes, you'd request 136 instead,\nwhich the allocator would round to the same power of two. If you\nrequested 128, you'd still request 128. It's not about adding space in\nthe allocated buffer for the flags, it's about needing less bits in\n`alloc` because those bits are effectively useless because of how\nallocators work.\n\n> Way worse than storing an unsigned.\n> If the allocator use a fibonnaci system, we can't even rely on multiples\n> of 4 (or 2).\n> I'm not sure the fibonnaci system is actually used by any allocator, but\n> my point is that I'm not sure it is a good thing to rely on such \n> low-level implementations.\n\nAllocators have constraints related to word sizes and alignment, so they\nare pretty much guaranteed to align things to powers of two.\n\nMike\n"},{"id":"287866","messageId":"574CF147.8020507@alum.mit.edu","threadId":"42483","inReplyTo":"20160530103642.7213-2-william.duclot@ensimag.grenoble-inp.fr","subject":"Re: [PATCH 1/2] strbuf: add tests","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2016-05-31T02:04:55Z","receivedAt":"2016-05-31T02:04:55Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Hi,\n\nCool that you are working on this! See my comments below.\n\nOn 05/30/2016 12:36 PM, William Duclot wrote:\n> Test the strbuf API. Being used throughout all Git the API could be\n> considered tested, but adding specific tests makes it easier to improve\n> and extend the API.\n> ---\n> Makefile | 1 +\n> t/helper/test-strbuf.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++\n> t/t0082-strbuf.sh | 19 ++++++++++++++\n> 3 files changed, 89 insertions(+)\n> create mode 100644 t/helper/test-strbuf.c\n> create mode 100755 t/t0082-strbuf.sh\n> \n> diff --git a/Makefile b/Makefile\n> index 3f03366..dc84f43 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -613,6 +613,7 @@ TEST_PROGRAMS_NEED_X += test-scrap-cache-tree\n> TEST_PROGRAMS_NEED_X += test-sha1\n> TEST_PROGRAMS_NEED_X += test-sha1-array\n> TEST_PROGRAMS_NEED_X += test-sigchain\n> +TEST_PROGRAMS_NEED_X += test-strbuf\n> TEST_PROGRAMS_NEED_X += test-string-list\n> TEST_PROGRAMS_NEED_X += test-submodule-config\n> TEST_PROGRAMS_NEED_X += test-subprocess\n> diff --git a/t/helper/test-strbuf.c b/t/helper/test-strbuf.c\n> new file mode 100644\n> index 0000000..622f627\n> --- /dev/null\n> +++ b/t/helper/test-strbuf.c\n> @@ -0,0 +1,69 @@\n> +#include \"git-compat-util.h\"\n> +#include \"strbuf.h\"\n> +\n> +/*\n> + * Check behavior on usual use cases\n> + */\n> +int test_usual(struct strbuf *sb)\n\nIs there a particular reason that you pass `sb` into the function? Why\nnot use a local variable?\n\nIt wouldn't hurt to declare this function static, because it is only\nused within this one compilation unit. On the other hand, in this\nparticular case I don't think it matters much one way or the other.\n\n> +{\n> +\tsize_t size, old_alloc;\n> +\tchar *res, *old_buf, *str_test = malloc(5*sizeof(char));\n\nThere is no reason to multiply by `sizeof(char)` here, and we don't do\nit in our code. (According to the C standard, `sizeof(char)` is always 1.)\n\n> +\tstrbuf_grow(sb, 1);\n> +\tstrcpy(str_test, \"test\");\n> +\told_alloc = sb->alloc;\n> +\tstrbuf_grow(sb, 1000);\n> +\tif (old_alloc == sb->alloc)\n> +\t\tdie(\"strbuf_grow does not realloc the buffer as expected\");\n\nIt's not ideal that your test depends on the details of the allocation\npolicy of strbuf. If somebody were to decide that it makes sense for the\ninitial allocation of a strbuf to be 1024 characters, this test would\nbreak. I know it's implausible, but it's better to remove this coupling.\n\nYou could do it by ensuring that you request more space than is already\nallocated:\n\n strbuf_grow(sb, sb.alloc - sb.len + 1000);\n\nOn the other hand, if you *want* to test the details of strbuf's\nallocation policy here, you would do it explicitly rather than as the\nside effect of this test. For example, before calling `strbuf_grow(sb,\n1000)`, you could insert:\n\n if (sb.alloc > SOME_VALUE)\n die(\"strbuf_grow(sb, 1) allocated too much space\");\n\nThough my opinion is that if you want to write tests of strbuf's\nallocation policies, it should be in an entirely separate test.\n\n> +\told_buf = sb->buf;\n> +\tres = strbuf_detach(sb, &size);\n\nSince you don't use `size`, you can pass `NULL` as the second argument\nof `strbuf_detach()`. The same below.\n\nAlternatively, maybe you want to add a test that `strbuf_detach()` sets\n`size` to the expected value.\n\n> +\tif (res != old_buf)\n> +\t\tdie(\"strbuf_detach does not return the expected buffer\");\n> +\tfree(res);\n> +\n> +\tstrcpy(str_test, \"test\");\n\nNear the beginning of the function you have this exact line, but here\nyou do it again even though str_test wasn't touched between the two\nlines. One of them can be deleted...\n\n...but in fact it would be easier to initialize str_test using our\nxstrdup() function:\n\n char *str_test = xstrdup(\"test\");\n\n> +\tstrbuf_attach(sb, (void *)str_test, strlen(str_test), sizeof(str_test));\n\nSince str_test is a `char *`, `sizeof(str_test)` returns the size of the\npointer itself (e.g., 4 or 8 bytes, depending on your computer's\narchitecture). What you want here is the size of the memory that it\npoints at, which in this case is `strlen(str_test) + 1`.\n\n(You may be confusing this pattern with code that looks like this:\n\n char str_test[5];\n\nIn this case, `sizeof(str_test)` is indeed 5, because `str_test` is an\narray of characters rather than a pointer to a character. It's confusing.)\n\nAlso, you don't need to cast `str_test` to `void *`. Any pointer can be\nconverted to `void *` implicitly.\n\n> +\tres = strbuf_detach(sb, &size);\n> +\tif (res != str_test)\n> +\t\tdie(\"strbuf_detach does not return the expected buffer\");\n> +\tfree(res);\n> +\tstrbuf_release(sb);\n> +\n> +\treturn 0;\n> +}\n> +\n> +int main(int argc, char *argv[])\n> +{\n> +\tsize_t size = 1;\n> +\tstruct strbuf sb;\n> +\tchar str_test[5] = \"test\";\n> +\tchar str_foo[7] = \"foo\";\n\n`size`, `str_test`, and `str_foo` are all unused.\n\nYou should compile using `DEVELOPER=1` to enable a bunch of compiler\nwarnings that Git developers tend to use. Any code you write should\ncompile without warnings or errors when compiled with that setting. See\n`Documentation/CodingGuidelines` for more info.\n\n> +\n> +\tif (argc != 2)\n> +\t\tusage(\"test-strbuf mode\");\n> +\n> +\tif (!strcmp(argv[1], \"basic_grow\")) {\n> +\t\t/*\n> +\t\t * Check if strbuf_grow(0) allocate a new NUL-terminated buffer\n> +\t\t */\n> +\t\tstrbuf_init(&sb, 0);\n> +\t\tstrbuf_grow(&sb, 0);\n> +\t\tif (sb.buf == strbuf_slopbuf)\n> +\t\t\tdie(\"strbuf_grow failed to alloc memory\");\n> +\t\tstrbuf_release(&sb);\n> +\t\tif (sb.buf != strbuf_slopbuf)\n> +\t\t\tdie(\"strbuf_release does not reinitialize the strbuf\");\n> +\t} else if (!strcmp(argv[1], \"strbuf_check_behavior\")) {\n> +\t\tstrbuf_init(&sb, 0);\n> +\t\treturn test_usual(&sb);\n> +\t} else if (!strcmp(argv[1], \"grow_overflow\")) {\n> +\t\t/*\n> +\t\t * size_t overflow: should die()\n> +\t\t */\n> +\t\tstrbuf_init(&sb, 1000);\n> +\t\tstrbuf_grow(&sb, maximum_unsigned_value_of_type((size_t)1));\n> +\t} else {\n> +\t\tusage(\"test-strbuf mode\");\n> +\t}\n\nConsider putting each test in a separate function, rather than\nimplementing some tests inline and one as a function. Consistency makes\ncode easier to read.\n\n> [...]\n\nMichael\n"},{"id":"287867","messageId":"574CFF75.3090805@alum.mit.edu","threadId":"42483","inReplyTo":"alpine.DEB.2.20.1605301326530.4449@virtualbox","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2016-05-31T03:05:25Z","receivedAt":"2016-05-31T03:05:25Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/30/2016 02:13 PM, Johannes Schindelin wrote:\n> [...]\n>> @@ -38,7 +67,11 @@ char *strbuf_detach(struct strbuf *sb, size_t *sz)\n>> {\n>> \tchar *res;\n>> \tstrbuf_grow(sb, 0);\n>> -\tres = sb->buf;\n>> +\tif (sb->flags & STRBUF_OWNS_MEMORY)\n>> +\t\tres = sb->buf;\n>> +\telse\n>> +\t\tres = xmemdupz(sb->buf, sb->alloc - 1);\n> \n> This looks like a usage to be avoided: if we plan to detach the buffer,\n> anyway, there is no good reason to allocate it on the heap first. I would\n> at least issue a warning here.\n\nI think this last case should be changed to\n\n res = xmemdupz(sb->buf, sb->len);\n\nJohannes, if this change is made then I think that there is a reasonable\nuse case for calling `strbuf_detach()` on a strbuf that wraps a\nstack-allocated string, so I don't think that a warning is needed.\n\nI think this change makes sense. After all, once a caller detaches a\nstring, it is probably not planning on growing/shrinking it anymore, so\nany more space than that would probably be wasted. In fact, since the\ncaller has no way to ask how much extra space the detached string has\nallocated, it is almost guaranteed that the space would be wasted.\n\nActually, that is not 100% certain. Theoretically, a caller might read\n`sb->alloc` *before* calling `strbuf_detach()`, and assume that the\ndetached string has that allocated size. Or the caller might call\n`strbuf_grow()` then assume that the detached string has at least that\nmuch free space.\n\nI sure hope that no callers actually do that. The docstring for\n`strbuf_detach()` doesn't promise that it will work, and there is a\npretty stern warning [1] that should hopefully have dissuaded developers\nfrom such a usage. But how could it be checked for sure?\n\n* Audit the callers of strbuf_detach(). But given that there are nearly\n200 callers, that would be a huge amount of work.\n\n* On a test branch, change the existing implementation of\nstrbuf_detach() to return newly-allocated memory of size `sb->len + 1`\nand free `sb->buf`, then run the test suite under valgrind. This would\nflush out examples of this antipattern in the test suite.\n\nIt might seem like we don't have to worry about this, because existing\ncallers only deal with strbufs that wrap heap-allocated strings. But\nsuch a caller might get a strbuf passed to it from a caller, and that\ncaller might someday be modified to use stack-allocated strings. So I\nthink that at least the valgrind test suggested above would be prudent.\n\nMichael\n\n[1]\nhttps://github.com/git/git/blob/f3913c2d03abc660140678a9e14dac399f847647/strbuf.h#L20-L23\n"},{"id":"287869","messageId":"574D0D99.6080303@alum.mit.edu","threadId":"42483","inReplyTo":"vpqlh2remhy.fsf@anie.imag.fr","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2016-05-31T04:05:45Z","receivedAt":"2016-05-31T04:05:45Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/30/2016 02:52 PM, Matthieu Moy wrote:\n> [...]\n\nI feel bad bikeshedding about names, especially since you took some of\nthe original names from my RFC. But names are very important, so I think\nit's worth considering whether the current names could be improved upon.\n\nWhen reading this patch series, I found I had trouble remembering\nwhether \"preallocated\" meant \"preallocated and movable\" or \"preallocated\nand immovable\". So maybe we should brainstorm alternatives to\n\"preallocated\" and \"fixed\". For example,\n\n* \"growable\"/\"fixed\"? Seems OK, though all strbufs are growable at least\nto the size of their initial allocation, so maybe \"growable\" is misleading.\n\n* \"movable\"/\"fixed\"? This maybe better captures the essence of the\ndistinction. I'll use those names below for concreteness, without\nclaiming that they are the best.\n\n> * strbuf_attach() calls strbuf_release(), which allows reusing an\n> existing strbuf. strbuf_wrap_preallocated() calls strbuf_init which\n> would override silently any previous content. I think strbuf_attach()\n> does the right thing here.\n\nHmmm....\n\nI think the best way to answer these questions is to think about use\ncases and make them as easy/consistent as possible.\n\nI expect that a very common use of strbuf_wrap_fixed() will be to wrap a\nstack-allocated string, like\n\n char pathbuf[PATH_MAX];\n struct strbuf path;\n\n strbuf_wrap_fixed(&path, pathbuf, 0, sizeof(pathbuf));\n\nIn this use case, it would be a shame if `path` had to be initialized to\nSTRBUF_INIT just because `strbuf_wrap_fixed()` calls `strbuf_release()`\ninternally.\n\nBut maybe we could make this use case easier still. If there were a macro\n\n #define STRBUF_FIXED_WRAPPER(sb, buf, len) { STRBUF_FIXED_MEMORY,\nsizeof(buf), (len), (buf) }\n\nthen we could write\n\n char pathbuf[PATH_MAX];\n struct strbuf path = STRBUF_FIXED_WRAPPER(pathbuf, 0);\n\nI think that would be pretty usable. One would have to be careful only\nto wrap arrays and not `char *` pointers, because `sizeof` wouldn't work\non the latter. The BARF_UNLESS_AN_ARRAY macro could be used here to add\na little safety.\n\n(It would be even nicer if we could write\n\n struct strbuf path = STRBUF_FIXED(PATH_MAX);\n\nand it would initialize both path and a pathbuf variable for it to wrap,\nbut I don't think there is a way to implement such a macro. So I think\nthe only way to squeeze this onto one line would be to make it look like\n\n DEFINE_FIXED_STRBUF(path, PATH_MAX);\n\nBut that looks awful, so I think the two-line version above is preferable.)\n\nSimilarly, there could be a macro\n\n #define STRBUF_MOVABLE_WRAPPER(sb, buf, len) { 0, sizeof(buf),\n(len), (buf) }\n\nIf you provide macro forms like these for initializing strbufs, then I\nagree with Matthieu that the analogous functional forms should probably\ncall strbuf_release() before wrapping the array. The functions might be\nnamed more like `strbuf_attach()` to emphasize their similarity to that\nexisting function. Maybe\n\n strbuf_attach_fixed(struct strbuf *sb, void *s, size_t len, size_t\nalloc);\n strbuf_attach_movable(struct strbuf *sb, void *s, size_t len, size_t\nalloc);\n\nMichael\n"},{"id":"287876","messageId":"alpine.DEB.2.20.1605310803580.4449@virtualbox","threadId":"42483","inReplyTo":"953965621.202433.1464614453377.JavaMail.zimbra@ensimag.grenoble-inp.fr","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2016-05-31T06:21:15Z","receivedAt":"2016-05-31T06:21:15Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi William,\n\nOn Mon, 30 May 2016, William Duclot wrote:\n\n> Johannes Schindelin writes:\n> > \n> > \tWhen working e.g. with file paths or with dates, strbuf's\n> > \tmalloc()/free() dance of strbufs can be easily avoided: as\n> > \ta sensible initial buffer size is already known, it can be\n> > \tallocated on the heap.\n> \n> strbuf already allow to indicate a sensible initial buffer size thanks\n> to strbuf_init() second parameter. The main perk of pre-allocation\n> is to use stack-allocated memory, and not heap-allocated :)\n\nSorry, my brain thought about the next point while my fingers typed\n\"heap\". It is \"stack\" I meant.\n\n> >> +#include \n> > \n> > Why?\n> \n> For the MAX macro. It may be a teeny tiny overkill\n\nTeeny tiny.\n\nYou probably assumed that everybody compiles this on Linux, and since it\ncompiles on your machine, no problem, right?\n\n> >> @@ -38,7 +67,11 @@ char *strbuf_detach(struct strbuf *sb, size_t *sz)\n> >> {\n> >> \tchar *res;\n> >> \tstrbuf_grow(sb, 0);\n> >> -\tres = sb->buf;\n> >> +\tif (sb->flags & STRBUF_OWNS_MEMORY)\n> >> +\t\tres = sb->buf;\n> >> +\telse\n> >> +\t\tres = xmemdupz(sb->buf, sb->alloc - 1);\n> > \n> > This looks like a usage to be avoided: if we plan to detach the buffer,\n> > anyway, there is no good reason to allocate it on the heap first. I would\n> > at least issue a warning here.\n> \n> strbuf_detach() guarantees to return heap-allocated memory, that the caller\n> can use however he want and that he'll have to free.\n\nFirst of all, let's stop this \"caller == he\" thing right here and now. A\nbetter way is to use the \"singular they\": ... the caller can use however\nthey want...\n\n> If the strbuf doesn't own the memory, it cannot return the buf attribute\n> directly because: [...]\n\nI know that. My point was that it is more elegant to allocate the buffer on\nthe heap right away, if we already know that we want to detach it.\n\nI'll reply to Michael's comment on this.\n\n> - The memory belong to someone else (so the caller can't use it however\n> he want)\n\ns/belong/belongs/ (just because the 's' is often silent in spoken French\ndoes not mean that you can drop it from written English)\n\n> >> extern char strbuf_slopbuf[];\n> >> -#define STRBUF_INIT { 0, 0, strbuf_slopbuf }\n> >> +#define STRBUF_INIT { 0, 0, 0, strbuf_slopbuf }\n> > \n> > If I am not mistaken, to preserve the existing behavior the initial flags\n> > should be 1 (own memory).\n> \n> strbuf_slopbuf is a buffer that doesn't belong to any strbuf (because it's\n> shared between all just-initialized strbufs).\n\nYet we somehow already have handling for that, right? Makes me wonder why\nI did not see that handling converted to the STRBUF_OWNS_MEMORY way...\n\n> > BTW this demonstrates that it may not be a good idea to declare the\n> > \"flags\" field globally but then make the actual flags private.\n> \n> I'm not sure what you mean here?\n\nWhat I meant is that the global _INIT cannot set any flags, because the\nconstants are not available globally. And that seems odd. If you ever want\nto introduce something like STRBUF_INIT_WRAP(buffer), you would *require*\nthose flag constants to be public.\n\n> > Also: similar use cases in Git used :1 flags (see e.g. the \"configured\"\n> > field in credential.h).\n> \n> I think that keeping an obscure `flags` attribute may be better, as they\n> should only be useful for internal operations and the user shouldn't mess\n> with it. Keeping it a `private` attribute, in a way\n\nThis is not C++. To do what you intend to do, you would require C++ style\nvisibility scopes, where a constructor can use a private enum. If you\ntruly want to go this way, I fear you will have *a lot more* to do than\nthis 2-patch series: there are a *ton* of existing header files\ndisagreeing with this goal.\n\nCiao,\nJohannes\n"},{"id":"287878","messageId":"xmqqbn3m7n25.fsf@gitster.mtv.corp.google.com","threadId":"42483","inReplyTo":"20160530103642.7213-3-william.duclot@ensimag.grenoble-inp.fr","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-05-31T06:34:42Z","receivedAt":"2016-05-31T06:34:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"William Duclot writes:\n\n> The API contract is still respected:\n>\n> - The API users may peek strbuf.buf in-place until they perform an\n> operation that makes it longer (at which point the .buf pointer\n> may point at a new piece of memory).\n\nI think the contract is actually a bit stronger; the API reserves\nthe right to free and reallocate a smaller chunk of memory if you\nmake the string shorter, so peeked value of .buf will not be relied\nupon even if you didn't make it longer.\n\n> - The API users may strbuf_detach() to obtain a piece of memory that\n> belongs to them (at which point the strbuf becomes empty), hence\n> needs to be freed by the callers.\n\nShouldn't you be honuoring another API contract?\n\n - If you allow an instance of strbuf go out of scope without taking\n the ownership of the string by calling strbuf_detach(), you must\n release the resource by calling strbuf_release().\n\nAs long as your \"on stack strbuf\" allows lengthening the string\nbeyond the initial allocation (i.e. .alloc, not .len), the user of\nthe API (i.e. the one that placed the strbuf on its stack) would not\nknow when the implementation (i.e. the code in this patch) decides\nto switch to allocated memory, so it must call strbuf_release()\nbefore it leaves. Which in turn means that your implementation of\nstrbuf_release() must be prepared to be take a strbuf that still has\nits string on the stack.\n\nOn the other hand, if your \"on stack strbuf\" does not allow\nlengthening, I'd find such a \"feature\" pretty much useless. The\ncaller must always test the remaining capacity, and switch to a\ndynamic strbuf, which is something the caller would expect the API\nimplementation to handle silently. You obviously do not have to\nrelease the resource in such a case, but that is being convenient\nin the wrong part of the API.\n\nIt would be wonderful if I can do:\n\n\tvoid func (void)\n {\n\t\textern void use(char *[2]);\n\t\t/*\n * strbuf that uses 1024-byte on-stack buffer\n * initially, but it may be extended dynamically.\n */\n\t\tstruct strbuf buf = STRBUF_INIT_ON_STACK(1024);\n\t\tchar *x[2];\n\n\t\tstrbuf_add(&buf, ...); /* add a lot of stuff */\n x[0] = strbuf_detach(&buf, NULL);\n\t\tstrbuf_add(&buf, ...); /* do some stuff */\n x[1] = strbuf_detach(&buf, NULL);\n\t\tuse(x);\n\n strbuf_release(&buf);\n\t}\n\nand add more than 2kb with the first add (hence causing buf to\nswitch to dynamic scheme), the first _detach() gives the malloc()ed \npiece of memory to x[0] _and_ points buf.buf back to the on-stack\nbuffer (and buf.alloc back to 1024) while setting buf.len to 0,\nso that the second _add() can still work purely on stack as long as\nit does not go beyond the 1024-byte on-stack buffer.\n\n> +/**\n> + * Flags\n> + * --------------\n> + */\n> +#define STRBUF_OWNS_MEMORY 1\n> +#define STRBUF_FIXED_MEMORY (1 << 1)\n\nThis is somewhat a strange way to spell two flag bits. Either spell\nthem as 1 and 2 (perhaps in octal or hexadecimal), or spell them as\n1 shifted by 0 and 1 to the left. Don't mix the notation.\n\n> @@ -20,16 +28,37 @@ char strbuf_slopbuf[1];\n> \n> void strbuf_init(struct strbuf *sb, size_t hint)\n> {\n> +\tsb->flags = 0;\n> \tsb->alloc = sb->len = 0;\n> \tsb->buf = strbuf_slopbuf;\n> \tif (hint)\n> \t\tstrbuf_grow(sb, hint);\n> }\n> \n> +void strbuf_wrap_preallocated(struct strbuf *sb, char *path_buf,\n> +\t\t\t size_t path_buf_len, size_t alloc_len)\n> +{\n> +\tif (!path_buf)\n> +\t\tdie(\"you try to use a NULL buffer to initialize a strbuf\");\n\nWhat does \"path\" mean in the context of this function (and its\n\"fixed\" sibling)?\n"},{"id":"287881","messageId":"alpine.DEB.2.20.1605310822490.4449@virtualbox","threadId":"42483","inReplyTo":"574CFF75.3090805@alum.mit.edu","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2016-05-31T06:41:54Z","receivedAt":"2016-05-31T06:41:54Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Michael,\n\nOn Tue, 31 May 2016, Michael Haggerty wrote:\n\n> On 05/30/2016 02:13 PM, Johannes Schindelin wrote:\n> > [...]\n> >> @@ -38,7 +67,11 @@ char *strbuf_detach(struct strbuf *sb, size_t *sz)\n> >> {\n> >> \tchar *res;\n> >> \tstrbuf_grow(sb, 0);\n> >> -\tres = sb->buf;\n> >> +\tif (sb->flags & STRBUF_OWNS_MEMORY)\n> >> +\t\tres = sb->buf;\n> >> +\telse\n> >> +\t\tres = xmemdupz(sb->buf, sb->alloc - 1);\n> > \n> > This looks like a usage to be avoided: if we plan to detach the buffer,\n> > anyway, there is no good reason to allocate it on the heap first. I would\n> > at least issue a warning here.\n> \n> I think this last case should be changed to\n> \n> res = xmemdupz(sb->buf, sb->len);\n> \n> Johannes, if this change is made then I think that there is a reasonable\n> use case for calling `strbuf_detach()` on a strbuf that wraps a\n> stack-allocated string, so I don't think that a warning is needed.\n> \n> I think this change makes sense. After all, once a caller detaches a\n> string, it is probably not planning on growing/shrinking it anymore, so\n> any more space than that would probably be wasted. In fact, since the\n> caller has no way to ask how much extra space the detached string has\n> allocated, it is almost guaranteed that the space would be wasted.\n\nAh, I did not think of that. (We could of course introduce\nstrbuf_realloc_snugly() or some such, but I agree: why?) So the best\ncounter-example to my objection might be something like this:\n\n-- snip --\nSubject: git_pathdup(): avoid realloc()\n\nWhen generating Git paths, we already know the maximum length:\nMAX_PATH. Let's avoid realloc()-caused fragmentation by using a\nfixed buffer.\n\nAs a side effect, we avoid overallocating the end result, too:\npreviously, strbuf_detach() would not realloc() to avoid wasting\nthe (sb->alloc - sb->len) bytes, while it malloc()s the precisely\nneeded amount of memory when detaching fixed buffers.\n\ndiff --git a/path.c b/path.c\nindex 2511d8a..64fd3ee 100644\n--- a/path.c\n+++ b/path.c\n@@ -426,7 +426,8 @@ const char *git_path(const char *fmt, ...)\n \n char *git_pathdup(const char *fmt, ...)\n {\n-\tstruct strbuf path = STRBUF_INIT;\n+\tchar buffer[MAX_PATH];\n+\tstruct strbuf path = STRBUF_WRAP_FIXED(buffer);\n \tva_list args;\n \tva_start(args, fmt);\n \tdo_git_path(&path, fmt, args);\n-- snap --\n\nColor me convinced,\nDscho\n"},{"id":"287885","messageId":"574D4A79.1030405@alum.mit.edu","threadId":"42483","inReplyTo":"alpine.DEB.2.20.1605310822490.4449@virtualbox","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2016-05-31T08:25:29Z","receivedAt":"2016-05-31T08:25:29Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/31/2016 08:41 AM, Johannes Schindelin wrote:\n> Hi Michael,\n> \n> On Tue, 31 May 2016, Michael Haggerty wrote:\n> \n>> On 05/30/2016 02:13 PM, Johannes Schindelin wrote:\n>>> [...]\n>>>> @@ -38,7 +67,11 @@ char *strbuf_detach(struct strbuf *sb, size_t *sz)\n>>>> {\n>>>> \tchar *res;\n>>>> \tstrbuf_grow(sb, 0);\n>>>> -\tres = sb->buf;\n>>>> +\tif (sb->flags & STRBUF_OWNS_MEMORY)\n>>>> +\t\tres = sb->buf;\n>>>> +\telse\n>>>> +\t\tres = xmemdupz(sb->buf, sb->alloc - 1);\n>>>\n>>> This looks like a usage to be avoided: if we plan to detach the buffer,\n>>> anyway, there is no good reason to allocate it on the heap first. I would\n>>> at least issue a warning here.\n>>\n>> I think this last case should be changed to\n>>\n>> res = xmemdupz(sb->buf, sb->len);\n>>\n>> Johannes, if this change is made then I think that there is a reasonable\n>> use case for calling `strbuf_detach()` on a strbuf that wraps a\n>> stack-allocated string, so I don't think that a warning is needed.\n>>\n>> I think this change makes sense. After all, once a caller detaches a\n>> string, it is probably not planning on growing/shrinking it anymore, so\n>> any more space than that would probably be wasted. In fact, since the\n>> caller has no way to ask how much extra space the detached string has\n>> allocated, it is almost guaranteed that the space would be wasted.\n> \n> Ah, I did not think of that. (We could of course introduce\n> strbuf_realloc_snugly() or some such, but I agree: why?) So the best\n> counter-example to my objection might be something like this:\n> \n> -- snip --\n> Subject: git_pathdup(): avoid realloc()\n> \n> When generating Git paths, we already know the maximum length:\n> MAX_PATH. Let's avoid realloc()-caused fragmentation by using a\n> fixed buffer.\n> \n> As a side effect, we avoid overallocating the end result, too:\n> previously, strbuf_detach() would not realloc() to avoid wasting\n> the (sb->alloc - sb->len) bytes, while it malloc()s the precisely\n> needed amount of memory when detaching fixed buffers.\n> \n> diff --git a/path.c b/path.c\n> index 2511d8a..64fd3ee 100644\n> --- a/path.c\n> +++ b/path.c\n> @@ -426,7 +426,8 @@ const char *git_path(const char *fmt, ...)\n> \n> char *git_pathdup(const char *fmt, ...)\n> {\n> -\tstruct strbuf path = STRBUF_INIT;\n> +\tchar buffer[MAX_PATH];\n> +\tstruct strbuf path = STRBUF_WRAP_FIXED(buffer);\n> \tva_list args;\n> \tva_start(args, fmt);\n> \tdo_git_path(&path, fmt, args);\n> -- snap --\n\nI like the idea, but apparently MAX_PATH is not a hard limit that OSs\nmust respect (e.g., see [1]). The existing implementation can generate\npaths longer than MAX_PATH whereas your replacement cannot.\n\nThis would be easy to solve by using STRBUF_WRAP_MOVABLE() instead of\nSTRBUF_WRAP_FIXED() in your patch. We would thereby accept the\npossibility that the strbuf might need to be expanded for really long\npaths. However, if that happens, then strbuf_detach() is likely to\nreturn the string in an overallocated memory area.\n\nSo if there are callers who *really* care about not having overallocated\nmemory, we might want a strbuf_detach_snugly().\n\nYour (only half-serious) idea for strbuf_realloc_snugly() would have the\ndisadvantage that it couldn't work with a fixed strbuf, whereas\nstrbuf_detach_snugly() could. It would be sad for callers to have to\nworry about the distinction.\n\nMichael\n\n[1] http://insanecoding.blogspot.de/2007/11/pathmax-simply-isnt.html\n"},{"id":"287888","messageId":"446224387.188052.1464688101694.JavaMail.zimbra@ensimag.grenoble-inp.fr","threadId":"42483","inReplyTo":"574CF147.8020507@alum.mit.edu","subject":"Re: [PATCH 1/2] strbuf: add tests","fromName":"Simon Rabourg","fromEmail":"simon.rabourg@ensimag.grenoble-inp.fr","sentAt":"2016-05-31T09:48:21Z","receivedAt":"2016-05-31T09:48:21Z","isPatch":true,"sender":{"key":"simon.rabourg@ensimag.grenoble-inp.fr","avatar":null},"body":"Hi Michael,\n\nMichael Haggerty writes:\n> Hi,\n> \n> Cool that you are working on this! See my comments below.\n> \n> On 05/30/2016 12:36 PM, William Duclot wrote:\n> > Test the strbuf API. Being used throughout all Git the API could be\n> > considered tested, but adding specific tests makes it easier to improve\n> > and extend the API.\n> > ---\n> > Makefile | 1 +\n> > t/helper/test-strbuf.c | 69\n> > ++++++++++++++++++++++++++++++++++++++++++++++++++\n> > t/t0082-strbuf.sh | 19 ++++++++++++++\n> > 3 files changed, 89 insertions(+)\n> > create mode 100644 t/helper/test-strbuf.c\n> > create mode 100755 t/t0082-strbuf.sh\n> > \n> > diff --git a/Makefile b/Makefile\n> > index 3f03366..dc84f43 100644\n> > --- a/Makefile\n> > +++ b/Makefile\n> > @@ -613,6 +613,7 @@ TEST_PROGRAMS_NEED_X += test-scrap-cache-tree\n> > TEST_PROGRAMS_NEED_X += test-sha1\n> > TEST_PROGRAMS_NEED_X += test-sha1-array\n> > TEST_PROGRAMS_NEED_X += test-sigchain\n> > +TEST_PROGRAMS_NEED_X += test-strbuf\n> > TEST_PROGRAMS_NEED_X += test-string-list\n> > TEST_PROGRAMS_NEED_X += test-submodule-config\n> > TEST_PROGRAMS_NEED_X += test-subprocess\n> > diff --git a/t/helper/test-strbuf.c b/t/helper/test-strbuf.c\n> > new file mode 100644\n> > index 0000000..622f627\n> > --- /dev/null\n> > +++ b/t/helper/test-strbuf.c\n> > @@ -0,0 +1,69 @@\n> > +#include \"git-compat-util.h\"\n> > +#include \"strbuf.h\"\n> > +\n> > +/*\n> > + * Check behavior on usual use cases\n> > + */\n> > +int test_usual(struct strbuf *sb)\n> \n> Is there a particular reason that you pass `sb` into the function? Why\n> not use a local variable?\n> \n\nThe fact is that we currently use the same 'sb' variable for all the \ntests. We are calling the \"test_usual\" function twice:\nthe first time after calling strbuf_init on sb and the second one after\ncalling strbuf_wrap_preallocated. \n\n> It wouldn't hurt to declare this function static, because it is only\n> used within this one compilation unit. On the other hand, in this\n> particular case I don't think it matters much one way or the other.\n> \n\nAgreed.\n\n> > +{\n> > +\tsize_t size, old_alloc;\n> > +\tchar *res, *old_buf, *str_test = malloc(5*sizeof(char));\n> \n> There is no reason to multiply by `sizeof(char)` here, and we don't do\n> it in our code. (According to the C standard, `sizeof(char)` is always 1.)\n> \n\nOk.\n\n> > +\tstrbuf_grow(sb, 1);\n> > +\tstrcpy(str_test, \"test\");\n> > +\told_alloc = sb->alloc;\n> > +\tstrbuf_grow(sb, 1000);\n> > +\tif (old_alloc == sb->alloc)\n> > +\t\tdie(\"strbuf_grow does not realloc the buffer as expected\");\n> \n> It's not ideal that your test depends on the details of the allocation\n> policy of strbuf. If somebody were to decide that it makes sense for the\n> initial allocation of a strbuf to be 1024 characters, this test would\n> break. I know it's implausible, but it's better to remove this coupling.\n> \n> You could do it by ensuring that you request more space than is already\n> allocated:\n> \n> strbuf_grow(sb, sb.alloc - sb.len + 1000);\n> \n> On the other hand, if you *want* to test the details of strbuf's\n> allocation policy here, you would do it explicitly rather than as the\n> side effect of this test. For example, before calling `strbuf_grow(sb,\n> 1000)`, you could insert:\n> \n> if (sb.alloc > SOME_VALUE)\n> die(\"strbuf_grow(sb, 1) allocated too much space\");\n\nOk.\n\n> \n> Though my opinion is that if you want to write tests of strbuf's\n> allocation policies, it should be in an entirely separate test.\n> \n> > +\told_buf = sb->buf;\n> > +\tres = strbuf_detach(sb, &size);\n> \n> Since you don't use `size`, you can pass `NULL` as the second argument\n> of `strbuf_detach()`. The same below.\n> \n> Alternatively, maybe you want to add a test that `strbuf_detach()` sets\n> `size` to the expected value.\n> \n\nTrue, we will put that test in the next version.\n\n> > +\tif (res != old_buf)\n> > +\t\tdie(\"strbuf_detach does not return the expected buffer\");\n> > +\tfree(res);\n> > +\n> > +\tstrcpy(str_test, \"test\");\n> \n> Near the beginning of the function you have this exact line, but here\n> you do it again even though str_test wasn't touched between the two\n> lines. One of them can be deleted...\n> \n> ...but in fact it would be easier to initialize str_test using our\n> xstrdup() function:\n> \n> char *str_test = xstrdup(\"test\");\n\nOk.\n\n\n> \n> > +\tstrbuf_attach(sb, (void *)str_test, strlen(str_test), sizeof(str_test));\n> \n> Since str_test is a `char *`, `sizeof(str_test)` returns the size of the\n> pointer itself (e.g., 4 or 8 bytes, depending on your computer's\n> architecture). What you want here is the size of the memory that it\n> points at, which in this case is `strlen(str_test) + 1`.\n> \n> (You may be confusing this pattern with code that looks like this:\n> \n> char str_test[5];\n> \n> In this case, `sizeof(str_test)` is indeed 5, because `str_test` is an\n> array of characters rather than a pointer to a character. It's confusing.)\n> \n\nIn the first version, str_test was a static variable. We updated it \nbut forgot to make the changes on the alloc_size passed to the \nstrbuf_detach call.\nIndeed it's a big mistake.\nThanks for pointing it out.\n\n> Also, you don't need to cast `str_test` to `void *`. Any pointer can be\n> converted to `void *` implicitly.\n\nAgreed.\n\n> \n> > +\tres = strbuf_detach(sb, &size);\n> > +\tif (res != str_test)\n> > +\t\tdie(\"strbuf_detach does not return the expected buffer\");\n> > +\tfree(res);\n> > +\tstrbuf_release(sb);\n> > +\n> > +\treturn 0;\n> > +}\n> > +\n> > +int main(int argc, char *argv[])\n> > +{\n> > +\tsize_t size = 1;\n> > +\tstruct strbuf sb;\n> > +\tchar str_test[5] = \"test\";\n> > +\tchar str_foo[7] = \"foo\";\n> \n> `size`, `str_test`, and `str_foo` are all unused.\n\nTrue. The fact is that we don't use them in all cases so \nthey are not necessary for all the tests. \nWe will change that in the next version.\n\n> \n> You should compile using `DEVELOPER=1` to enable a bunch of compiler\n> warnings that Git developers tend to use. Any code you write should\n> compile without warnings or errors when compiled with that setting. See\n> `Documentation/CodingGuidelines` for more info.\n> \n\nThanks for this advice.\n\n> > +\n> > +\tif (argc != 2)\n> > +\t\tusage(\"test-strbuf mode\");\n> > +\n> > +\tif (!strcmp(argv[1], \"basic_grow\")) {\n> > +\t\t/*\n> > +\t\t * Check if strbuf_grow(0) allocate a new NUL-terminated buffer\n> > +\t\t */\n> > +\t\tstrbuf_init(&sb, 0);\n> > +\t\tstrbuf_grow(&sb, 0);\n> > +\t\tif (sb.buf == strbuf_slopbuf)\n> > +\t\t\tdie(\"strbuf_grow failed to alloc memory\");\n> > +\t\tstrbuf_release(&sb);\n> > +\t\tif (sb.buf != strbuf_slopbuf)\n> > +\t\t\tdie(\"strbuf_release does not reinitialize the strbuf\");\n> > +\t} else if (!strcmp(argv[1], \"strbuf_check_behavior\")) {\n> > +\t\tstrbuf_init(&sb, 0);\n> > +\t\treturn test_usual(&sb);\n> > +\t} else if (!strcmp(argv[1], \"grow_overflow\")) {\n> > +\t\t/*\n> > +\t\t * size_t overflow: should die()\n> > +\t\t */\n> > +\t\tstrbuf_init(&sb, 1000);\n> > +\t\tstrbuf_grow(&sb, maximum_unsigned_value_of_type((size_t)1));\n> > +\t} else {\n> > +\t\tusage(\"test-strbuf mode\");\n> > +\t}\n> \n> Consider putting each test in a separate function, rather than\n> implementing some tests inline and one as a function. Consistency makes\n> code easier to read.\n> \n\nOk.\n\n> > [...]\n> \n> Michael\n> \n> \n\nThanks,\nSimon Rabourg\n"},{"id":"287908","messageId":"20160531154503.GA24895@Messiaen","threadId":"42483","inReplyTo":"xmqqbn3m7n25.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"William","fromEmail":"william.duclot@ensimag.grenoble-inp.fr","sentAt":"2016-05-31T15:45:03Z","receivedAt":"2016-05-31T15:45:03Z","isPatch":true,"sender":{"key":"william.duclot@ensimag.grenoble-inp.fr","avatar":null},"body":"On Mon, May 30, 2016 at 11:34:42PM -0700, Junio C Hamano wrote:\n> William Duclot writes:\n> \n>> The API contract is still respected:\n>>\n>> - The API users may peek strbuf.buf in-place until they perform an\n>> operation that makes it longer (at which point the .buf pointer\n>> may point at a new piece of memory).\n> \n> I think the contract is actually a bit stronger; the API reserves\n> the right to free and reallocate a smaller chunk of memory if you\n> make the string shorter, so peeked value of .buf will not be relied\n> upon even if you didn't make it longer.\n\nRight, anytime the string size change\n \n>> - The API users may strbuf_detach() to obtain a piece of memory that\n>> belongs to them (at which point the strbuf becomes empty), hence\n>> needs to be freed by the callers.\n> \n> Shouldn't you be honuoring another API contract?\n> \n> - If you allow an instance of strbuf go out of scope without taking\n> the ownership of the string by calling strbuf_detach(), you must\n> release the resource by calling strbuf_release().\n> \n> As long as your \"on stack strbuf\" allows lengthening the string\n> beyond the initial allocation (i.e. .alloc, not .len), the user of\n> the API (i.e. the one that placed the strbuf on its stack) would not\n> know when the implementation (i.e. the code in this patch) decides\n> to switch to allocated memory, so it must call strbuf_release()\n> before it leaves. Which in turn means that your implementation of\n> strbuf_release() must be prepared to be take a strbuf that still has\n> its string on the stack.\n\nWell, my implementation does handle a strbuf that still has its\nstring on the stack: the buffer won't be freed in this case (only a\nreset to STRBUF_INIT).\nUnless I misunderstood you?\n\n> On the other hand, if your \"on stack strbuf\" does not allow\n> lengthening, I'd find such a \"feature\" pretty much useless. The\n> caller must always test the remaining capacity, and switch to a\n> dynamic strbuf, which is something the caller would expect the API\n> implementation to handle silently. You obviously do not have to\n> release the resource in such a case, but that is being convenient\n> in the wrong part of the API.\n> \n> It would be wonderful if I can do:\n> \n> \tvoid func (void)\n> {\n> \t\textern void use(char *[2]);\n> \t\t/*\n> * strbuf that uses 1024-byte on-stack buffer\n> * initially, but it may be extended dynamically.\n> */\n> \t\tstruct strbuf buf = STRBUF_INIT_ON_STACK(1024);\n> \t\tchar *x[2];\n> \n> \t\tstrbuf_add(&buf, ...); /* add a lot of stuff */\n> x[0] = strbuf_detach(&buf, NULL);\n> \t\tstrbuf_add(&buf, ...); /* do some stuff */\n> x[1] = strbuf_detach(&buf, NULL);\n> \t\tuse(x);\n> \n> strbuf_release(&buf);\n> \t}\n>\n> and add more than 2kb with the first add (hence causing buf to\n> switch to dynamic scheme), the first _detach() gives the malloc()ed \n> piece of memory to x[0] _and_ points buf.buf back to the on-stack\n> buffer (and buf.alloc back to 1024) while setting buf.len to 0,\n> so that the second _add() can still work purely on stack as long as\n> it does not go beyond the 1024-byte on-stack buffer. \n\n\nI think that it's possible, but extends the API beyond what was\noriginally intended by Michael. I don't see other use cases than treating\nseveral string sequentially, is it worth avoiding a attach_movable() \n(as suggested by Michael in place of wrap_preallocated())?\nYou could do:\n\n\tvoid func (void)\n {\n\t\textern void use(char *[2]);\n\t\t/*\n * strbuf that uses 1024-byte on-stack buffer\n * initially, but it may be extended dynamically.\n */\n char on_stack[1024];\n\t\tstruct strbuf buf;\n \t\tchar x[2];\n\n strbuf_attach_movable(&sb, on_stack, 0, sizeof(on_stack));\n \t\tstrbuf_add(&buf, ...); /* add a lot of stuff */\n x[0] = strbuf_detach(&buf, NULL);\n strbuf_attach_movable(&sb, on_stack, 0, sizeof(on_stack));\n \t\tstrbuf_add(&buf, ...); /* do some stuff */\n x[1] = strbuf_detach(&buf, NULL);\n \t\tuse(x);\n \n strbuf_release(&buf);\n \t}\n\nWhich seems pretty close without needing the strbuf API to remember the\noriginal buffer or to even care about memory being on the stack or the\nheap.\n\n>> +/**\n>> + * Flags\n>> + * --------------\n>> + */\n>> +#define STRBUF_OWNS_MEMORY 1\n>> +#define STRBUF_FIXED_MEMORY (1 << 1)\n> \n> This is somewhat a strange way to spell two flag bits. Either spell\n> them as 1 and 2 (perhaps in octal or hexadecimal), or spell them as\n> 1 shifted by 0 and 1 to the left. Don't mix the notation.\n\nNoted\n\n>> @@ -20,16 +28,37 @@ char strbuf_slopbuf[1];\n>> \n>> void strbuf_init(struct strbuf *sb, size_t hint)\n>> {\n>> +\tsb->flags = 0;\n>> \tsb->alloc = sb->len = 0;\n>> \tsb->buf = strbuf_slopbuf;\n>> \tif (hint)\n>> \t\tstrbuf_grow(sb, hint);\n>> }\n>> \n>> +void strbuf_wrap_preallocated(struct strbuf *sb, char *path_buf,\n>> +\t\t\t size_t path_buf_len, size_t alloc_len)\n>> +{\n>> +\tif (!path_buf)\n>> +\t\tdie(\"you try to use a NULL buffer to initialize a strbuf\");\n> \n> What does \"path\" mean in the context of this function (and its\n> \"fixed\" sibling)?\n\nThat should be someting like `str` and `str_len` indeed\n"},{"id":"287910","messageId":"vpq4m9eql2k.fsf@anie.imag.fr","threadId":"42483","inReplyTo":"20160531154503.GA24895@Messiaen","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@grenoble-inp.fr","sentAt":"2016-05-31T15:54:59Z","receivedAt":"2016-05-31T15:54:59Z","isPatch":true,"sender":{"key":"matthieu.moy@grenoble-inp.fr","avatar":"https://gravatar.com/avatar/72c8a2705971a25dfaff23cece15130d405685845d911aedd5667ace277f3fc5?d=mp&s=160"},"body":"William writes:\n\n> On Mon, May 30, 2016 at 11:34:42PM -0700, Junio C Hamano wrote:\n>\n>> As long as your \"on stack strbuf\" allows lengthening the string\n>> beyond the initial allocation (i.e. .alloc, not .len), the user of\n>> the API (i.e. the one that placed the strbuf on its stack) would not\n>> know when the implementation (i.e. the code in this patch) decides\n>> to switch to allocated memory, so it must call strbuf_release()\n>> before it leaves. Which in turn means that your implementation of\n>> strbuf_release() must be prepared to be take a strbuf that still has\n>> its string on the stack.\n>\n> Well, my implementation does handle a strbuf that still has its\n> string on the stack: the buffer won't be freed in this case (only a\n> reset to STRBUF_INIT).\n> Unless I misunderstood you?\n\nI think Junio meant:\n\nvoid f()\n{\n\tstruct strbuf sb;\n\tchar buf[N];\n\tstrbuf_wrap_preallocated(&sb, buf, ...);\n\tstrbuf_add(&sb, ...);\n\n\t// is it safe to just let sb reach the end of its scope?\n}\n\nTo answer the last question, the user would need to know too much about\nthe allocation policy, so in this case the user should call\nstrbuf_release(), and let it chose whether to call \"free()\"\n(OWNS_MEMORY) or not. This is OK with your implementation, but the doc\nneeds to reflect this.\n\n-- \nMatthieu Moy\nhttp://www-verimag.imag.fr/~moy/\n"},{"id":"287911","messageId":"20160531155947.GB24895@Messiaen","threadId":"42483","inReplyTo":"574D0D99.6080303@alum.mit.edu","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"William Duclot","fromEmail":"william.duclot@ensimag.grenoble-inp.fr","sentAt":"2016-05-31T15:59:47Z","receivedAt":"2016-05-31T15:59:47Z","isPatch":true,"sender":{"key":"william.duclot@ensimag.grenoble-inp.fr","avatar":null},"body":"On Tue, May 31, 2016 at 06:05:45AM +0200, Michael Haggerty wrote:\n> On 05/30/2016 02:52 PM, Matthieu Moy wrote:\n> > [...]\n> \n> I feel bad bikeshedding about names, especially since you took some of\n> the original names from my RFC. But names are very important, so I think\n> it's worth considering whether the current names could be improved upon.\n> \n> When reading this patch series, I found I had trouble remembering\n> whether \"preallocated\" meant \"preallocated and movable\" or \"preallocated\n> and immovable\". So maybe we should brainstorm alternatives to\n> \"preallocated\" and \"fixed\". For example,\n> \n> * \"growable\"/\"fixed\"? Seems OK, though all strbufs are growable at least\n> to the size of their initial allocation, so maybe \"growable\" is misleading.\n> \n> * \"movable\"/\"fixed\"? This maybe better captures the essence of the\n> distinction. I'll use those names below for concreteness, without\n> claiming that they are the best.\n\nYes, the names are debatable\n\n> > * strbuf_attach() calls strbuf_release(), which allows reusing an\n> > existing strbuf. strbuf_wrap_preallocated() calls strbuf_init which\n> > would override silently any previous content. I think strbuf_attach()\n> > does the right thing here.\n> \n> Hmmm....\n> \n> I think the best way to answer these questions is to think about use\n> cases and make them as easy/consistent as possible.\n> \n> I expect that a very common use of strbuf_wrap_fixed() will be to wrap a\n> stack-allocated string, like\n> \n> char pathbuf[PATH_MAX];\n> struct strbuf path;\n> \n> strbuf_wrap_fixed(&path, pathbuf, 0, sizeof(pathbuf));\n> \n> In this use case, it would be a shame if `path` had to be initialized to\n> STRBUF_INIT just because `strbuf_wrap_fixed()` calls `strbuf_release()`\n> internally.\n> \n> But maybe we could make this use case easier still. If there were a macro\n> \n> #define STRBUF_FIXED_WRAPPER(sb, buf, len) { STRBUF_FIXED_MEMORY,\n> sizeof(buf), (len), (buf) }\n> \n> then we could write\n> \n> char pathbuf[PATH_MAX];\n> struct strbuf path = STRBUF_FIXED_WRAPPER(pathbuf, 0);\n> \n> I think that would be pretty usable. One would have to be careful only\n> to wrap arrays and not `char *` pointers, because `sizeof` wouldn't work\n> on the latter. The BARF_UNLESS_AN_ARRAY macro could be used here to add\n> a little safety.\n\nThat sounds like a good idea to me\n\n> [...]\n> If you provide macro forms like these for initializing strbufs, then I\n> agree with Matthieu that the analogous functional forms should probably\n> call strbuf_release() before wrapping the array. The functions might be\n> named more like `strbuf_attach()` to emphasize their similarity to that\n> existing function. Maybe\n> \n> strbuf_attach_fixed(struct strbuf *sb, void *s, size_t len, size_t\n> alloc);\n> strbuf_attach_movable(struct strbuf *sb, void *s, size_t len, size_t\n> alloc);\n\nI'm not a big fan of the idea that the macro and the function don't have\nthe same behavior. Using \"attach\" instead of \"wrap\" or \"init\" may\njustify that\n"},{"id":"287913","messageId":"20160531160856.GC24895@Messiaen","threadId":"42483","inReplyTo":"vpq4m9eql2k.fsf@anie.imag.fr","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"William Duclot","fromEmail":"william.duclot@ensimag.grenoble-inp.fr","sentAt":"2016-05-31T16:08:56Z","receivedAt":"2016-05-31T16:08:56Z","isPatch":true,"sender":{"key":"william.duclot@ensimag.grenoble-inp.fr","avatar":null},"body":"On Tue, May 31, 2016 at 05:54:59PM +0200, Matthieu Moy wrote:\n> William writes:\n> \n> > On Mon, May 30, 2016 at 11:34:42PM -0700, Junio C Hamano wrote:\n> >\n> >> As long as your \"on stack strbuf\" allows lengthening the string\n> >> beyond the initial allocation (i.e. .alloc, not .len), the user of\n> >> the API (i.e. the one that placed the strbuf on its stack) would not\n> >> know when the implementation (i.e. the code in this patch) decides\n> >> to switch to allocated memory, so it must call strbuf_release()\n> >> before it leaves. Which in turn means that your implementation of\n> >> strbuf_release() must be prepared to be take a strbuf that still has\n> >> its string on the stack.\n> >\n> > Well, my implementation does handle a strbuf that still has its\n> > string on the stack: the buffer won't be freed in this case (only a\n> > reset to STRBUF_INIT).\n> > Unless I misunderstood you?\n> \n> I think Junio meant:\n> \n> void f()\n> {\n> \tstruct strbuf sb;\n> \tchar buf[N];\n> \tstrbuf_wrap_preallocated(&sb, buf, ...);\n> \tstrbuf_add(&sb, ...);\n> \n> \t// is it safe to just let sb reach the end of its scope?\n> }\n> \n> To answer the last question, the user would need to know too much about\n> the allocation policy, so in this case the user should call\n> strbuf_release(), and let it chose whether to call \"free()\"\n> (OWNS_MEMORY) or not. This is OK with your implementation, but the doc\n> needs to reflect this.\n\nOkay, I understand. The idea was that the only change in the API is the\ninitialization: the API user can then use the strbuf like they could\nbefore this patch, with the same responsabilities (having to release the\nstrbuf when they don't need it anymore).\nMaybe a clearer documentation about the life and death of a strbuf\n(initialization, use and release) would be useful, yes\n"},{"id":"287984","messageId":"20160601074218.GB14096@sigill.intra.peff.net","threadId":"42483","inReplyTo":"1069084553.156626.1464607928755.JavaMail.zimbra@ensimag.grenoble-inp.fr","subject":"Re: [PATCH 0/2] strbuf: improve API","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-06-01T07:42:18Z","receivedAt":"2016-06-01T07:42:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, May 30, 2016 at 01:32:08PM +0200, Remi Galan Alfonso wrote:\n\n> William Duclot writes:\n> > This patch series implements an improvment of the strbuf API, allowing\n> > strbuf to use preallocated memory. This makes strbuf fit to be used\n> > in performance-critical operations.\n> > \n> > The first patch is simply a preparatory work, adding tests for\n> > existing strbuf implementation.\n> > Most of the work is made in the second patch: handle pre-allocated\n> > memory, extend the API, document it and test it.\n> \n> Seems interesting, however do you have any test/example that would\n> show the difference of performance between using these optimizations\n> and not using them?\n> \n> Such values would make a nice addition to help convince people that\n> your series is interesting to have and use.\n\nI'll second the request for actual numbers. I'm a little dubious that\nmalloc overhead is actually a significant place we are spending time, or\nif there is simply a superstitious avoidance of using strbufs. A huge\nnumber of strbufs are used for filenames, where we're about to make a\nsyscall anyway. If your allocator for a 4K page is not competitive with\na context switch, I suspect the best solution is to get a new allocator.\n\nSo I wonder if we have some less-invasive alternatives:\n\n 1. Ship a faster allocator library with git, and use its malloc by\n default.\n\n 2. Do caching tricks for strbufs used in tight loops. For example,\n have strbuf_release() throw its buffer into a last-used cache, and\n let the next strbuf_grow() use that cache entry. This cuts malloc()\n out of the loop.\n\n You'd probably want to protect the cache with a mutex, though. Most\n of git isn't thread-safe, but a few parts are, and strbufs are\n low-level enough that they might get called.\n\nI have no idea if those ideas would work. But I wouldn't want to start\nlooking into either of them without some idea of how much time we're\nactually spending on strbuf mallocs (or how much time we would spend if\nstrbufs were used in some proposed sites).\n\n-Peff\n"},{"id":"288075","messageId":"1464810629.3988.11.camel@twopensource.com","threadId":"42483","inReplyTo":"20160601074218.GB14096@sigill.intra.peff.net","subject":"Re: [PATCH 0/2] strbuf: improve API","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2016-06-01T19:50:29Z","receivedAt":"2016-06-01T19:50:29Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Wed, 2016-06-01 at 03:42 -0400, Jeff King wrote:\n> 2. Do caching tricks for strbufs used in tight loops. For example,\n> have strbuf_release() throw its buffer into a last-used cache,\n> and\n> let the next strbuf_grow() use that cache entry. This cuts\n> malloc()\n> out of the loop.\n> \n> You'd probably want to protect the cache with a mutex, though.\n\n\n... or make the last-used cache be thread-local.\n"},{"id":"288076","messageId":"20160601200959.GA13061@sigill.intra.peff.net","threadId":"42483","inReplyTo":"1464810629.3988.11.camel@twopensource.com","subject":"Re: [PATCH 0/2] strbuf: improve API","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-06-01T20:09:59Z","receivedAt":"2016-06-01T20:09:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 01, 2016 at 03:50:29PM -0400, David Turner wrote:\n\n> On Wed, 2016-06-01 at 03:42 -0400, Jeff King wrote:\n> > 2. Do caching tricks for strbufs used in tight loops. For example,\n> > have strbuf_release() throw its buffer into a last-used cache,\n> > and\n> > let the next strbuf_grow() use that cache entry. This cuts\n> > malloc()\n> > out of the loop.\n> > \n> > You'd probably want to protect the cache with a mutex, though.\n> \n> \n> ... or make the last-used cache be thread-local.\n\nGood idea.\n\nI almost didn't mention threading at all, because I'd be surprised if\nmalloc lock contention is a serious bottleneck for us anywhere.\n\nIt's hard to really say much concrete because it's not clear to me where\npeople think strbuf allocation _is_ a bottleneck (or again, _would be_\nif we were to use it more).\n\nIf we imagine a loop like this:\n\n for (i = 0; i < n; i++) {\n\tstruct strbuf buf = STRBUF_INIT;\n\tdo_something_with(&buf);\n\tstrbuf_release(&buf);\n }\n\nthen yes, we'll call malloc() and free() a lot of times. But unless your\nlibc malloc is terrible, those calls are all probably just taking a\nmutex and reusing the same block from a free list. The strbuf case is\nactually really friendly to allocators because our blocks tend to be\npredictable sizes (they're sized by ALLOC_GROW, which has a\ndeterministic set of block sizes).\n\nIn practice, I'd imagine loops get more complicated than that. They call\nsub-functions which allocate a strbuf, and sometimes don't release it\nuntil other strbufs have been allocated, etc. The proposal in this\nthread is basically using the call stack to mirror the allocation\npatterns. So when the pattern of allocations matches an actual stack,\nthat's good, but I'd expect a reasonably smart allocator to perform\nsimilarly. And when it's not a true stack, the stack-based strbufs are\ngoing to end up with wasted stack space hanging around even after we've\nfree()'d the memory and could reuse it. And I'd still expect an\nallocator based off a linked list or something to handle such cases\npretty well.\n\nThere are also other non-big-O factors at play in modern systems, like\nCPU cache footprints. Is heap memory cheaper or more expensive to access\nthan stack? I can imagine stack is kept in the cache better, but if\nyou're reusing the same heap block over and over, it probably stays in\ncache, too. But if you have unused stack buffers that _could_ be reused\n(but won't be because you'd have to manually feed them to a new strbuf),\nthat hurts your footprint. And on top of that, the stack proposals I've\nseen generally involve over-sizing the stack buffers out of a fear of\nactually calling malloc.\n\nAnd then on top of that, there is the question of whether anything\ninvolving a strbuf allocation is actually a tight enough loop to even\n_care_ about cache dynamics.\n\nSo again, I'm slightly negative on anything that makes the code even\nslightly more complex, especially the call sites, if we can't show\nactual measurable improvement numbers.\n\nSorry, this turned into a mini-rant, and it's not really directed at\nyou, David. Your email was just what spurred me to put some of these\nthoughts into words. :)\n\n-Peff\n"},{"id":"288077","messageId":"1464812542.3988.12.camel@twopensource.com","threadId":"42483","inReplyTo":"20160601200959.GA13061@sigill.intra.peff.net","subject":"Re: [PATCH 0/2] strbuf: improve API","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2016-06-01T20:22:22Z","receivedAt":"2016-06-01T20:22:22Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Wed, 2016-06-01 at 16:09 -0400, Jeff King wrote:\n> On Wed, Jun 01, 2016 at 03:50:29PM -0400, David Turner wrote:\n> \n> > On Wed, 2016-06-01 at 03:42 -0400, Jeff King wrote:\n> > > 2. Do caching tricks for strbufs used in tight loops. For\n> > > example,\n> > > have strbuf_release() throw its buffer into a last-used\n> > > cache,\n> > > and\n> > > let the next strbuf_grow() use that cache entry. This cuts\n> > > malloc()\n> > > out of the loop.\n> > > \n> > > You'd probably want to protect the cache with a mutex,\n> > > though.\n> > \n> > \n> > ... or make the last-used cache be thread-local.\n> \n> Good idea.\n> \n> I almost didn't mention threading at all, because I'd be surprised if\n> malloc lock contention is a serious bottleneck for us anywhere.\n> \n> It's hard to really say much concrete because it's not clear to me\n> where\n> people think strbuf allocation _is_ a bottleneck (or again, _would\n> be_\n> if we were to use it more).\n> \n> If we imagine a loop like this:\n> \n> for (i = 0; i < n; i++) {\n> \tstruct strbuf buf = STRBUF_INIT;\n> \tdo_something_with(&buf);\n> \tstrbuf_release(&buf);\n> }\n> \n> then yes, we'll call malloc() and free() a lot of times. But unless\n> your\n> libc malloc is terrible, those calls are all probably just taking a\n> mutex and reusing the same block from a free list. The strbuf case is\n> actually really friendly to allocators because our blocks tend to be\n> predictable sizes (they're sized by ALLOC_GROW, which has a\n> deterministic set of block sizes).\n> \n> In practice, I'd imagine loops get more complicated than that. They\n> call\n> sub-functions which allocate a strbuf, and sometimes don't release it\n> until other strbufs have been allocated, etc. The proposal in this\n> thread is basically using the call stack to mirror the allocation\n> patterns. So when the pattern of allocations matches an actual stack,\n> that's good, but I'd expect a reasonably smart allocator to perform\n> similarly. And when it's not a true stack, the stack-based strbufs\n> are\n> going to end up with wasted stack space hanging around even after\n> we've\n> free()'d the memory and could reuse it. And I'd still expect an\n> allocator based off a linked list or something to handle such cases\n> pretty well.\n> \n> There are also other non-big-O factors at play in modern systems,\n> like\n> CPU cache footprints. Is heap memory cheaper or more expensive to\n> access\n> than stack? I can imagine stack is kept in the cache better, but if\n> you're reusing the same heap block over and over, it probably stays\n> in\n> cache, too. But if you have unused stack buffers that _could_ be\n> reused\n> (but won't be because you'd have to manually feed them to a new\n> strbuf),\n> that hurts your footprint. And on top of that, the stack proposals\n> I've\n> seen generally involve over-sizing the stack buffers out of a fear of\n> actually calling malloc.\n> \n> And then on top of that, there is the question of whether anything\n> involving a strbuf allocation is actually a tight enough loop to even\n> _care_ about cache dynamics.\n> \n> So again, I'm slightly negative on anything that makes the code even\n> slightly more complex, especially the call sites, if we can't show\n> actual measurable improvement numbers.\n> \n> Sorry, this turned into a mini-rant, and it's not really directed at\n> you, David. Your email was just what spurred me to put some of these\n> thoughts into words. :)\n\nI agree with all this stuff anyway.\n"},{"id":"288086","messageId":"20160601210713.GA18118@sigill.intra.peff.net","threadId":"42483","inReplyTo":"20160601074218.GB14096@sigill.intra.peff.net","subject":"Re: [PATCH 0/2] strbuf: improve API","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-06-01T21:07:13Z","receivedAt":"2016-06-01T21:07:13Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 01, 2016 at 03:42:18AM -0400, Jeff King wrote:\n\n> I have no idea if those ideas would work. But I wouldn't want to start\n> looking into either of them without some idea of how much time we're\n> actually spending on strbuf mallocs (or how much time we would spend if\n> strbufs were used in some proposed sites).\n\nSo I tried to come up with some numbers.\n\nHere's an utterly silly use of strbufs, but one that I think should\nover-emphasize the effect of any improvements we make:\n\ndiff --git a/Makefile b/Makefile\nindex 7a0551a..72b968a 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -579,6 +579,7 @@ PROGRAM_OBJS += shell.o\n PROGRAM_OBJS += show-index.o\n PROGRAM_OBJS += upload-pack.o\n PROGRAM_OBJS += remote-testsvn.o\n+PROGRAM_OBJS += foo.o\n \n # Binary suffix, set to .exe for Windows builds\n X =\ndiff --git a/foo.c b/foo.c\nindex e69de29..b62dd97 100644\n--- a/foo.c\n+++ b/foo.c\n@@ -0,0 +1,18 @@\n+#include \"git-compat-util.h\"\n+#include \"strbuf.h\"\n+\n+int main(void)\n+{\n+\tconst char *str = \"this is a string that we'll repeatedly insert\";\n+\tsize_t len = strlen(str);\n+\n+\tint i;\n+\tfor (i = 0; i < 1000000; i++) {\n+\t\tstruct strbuf buf = STRBUF_INIT;\n+\t\tint j;\n+\t\tfor (j = 0; j < 500; j++)\n+\t\t\tstrbuf_add(&buf, str, len);\n+\t\tstrbuf_release(&buf);\n+\t}\n+\treturn 0;\n+}\n\nThat takes about 3.5 seconds to run git-foo on my machine. Here's where\nperf says the time goes:\n\n# Children Self Command Shared Object Symbol \n# ........ ........ ....... ................. ..........................\n#\n 35.62% 34.58% git-foo git-foo [.] strbuf_add \n 22.70% 22.14% git-foo git-foo [.] strbuf_grow \n 19.85% 19.04% git-foo libc-2.22.so [.] __memcpy_avx_unaligned\n 9.47% 9.17% git-foo git-foo [.] main \n 4.88% 4.68% git-foo git-foo [.] memcpy@plt \n 3.21% 3.12% git-foo libc-2.22.so [.] realloc \n 1.75% 1.71% git-foo libc-2.22.so [.] _int_realloc \n 1.42% 0.00% git-foo [unknown] [.] 0x676e697274732061 \n 0.82% 0.79% git-foo git-foo [.] xrealloc \n 0.61% 0.59% git-foo git-foo [.] memory_limit_check \n 0.45% 0.00% git-foo [unknown] [.] 0000000000000000 \n 0.32% 0.00% git-foo [unknown] [.] 0x0000000000000fff \n 0.32% 0.32% git-foo [unknown] [k] 0x00007f591b44a2f0 \n 0.31% 0.31% git-foo [unknown] [k] 0x0000000000404719 \n 0.30% 0.00% git-foo [unknown] [.] 0x0000000000001ffe \n 0.30% 0.30% git-foo libc-2.22.so [.] _int_free \n 0.30% 0.28% git-foo libc-2.22.so [.] _int_malloc \n\nSo malloc and free are pretty low. It looks like realloc is more,\nprobably because of the memcpys it has to do. I don't think that would\nbe much better in a stack-based system (because we'd realloc there,\ntoo). What would help is simply using a larger initial size (for _this_\nmade-up benchmark; I'm not convinced it would be all that good in the\nreal world).\n\nBut either way, most of the time is actually spent in the strbuf\nfunctions themselves (interesting, if you replace strbuf_add with\nstrbuf_addf, we spend much more time dealing with the formatted input).\nWe can probably micro-optimize them some.\n\nHere's a short and hacky patch to inline strbuf_grow, and to use\ncompiler intrinsics to do the overflow checks (which obviously isn't\nportable, but we can easily hide it behind a macro and fall back to the\nexisting scheme):\n\ndiff --git a/strbuf.c b/strbuf.c\nindex 1ba600b..4f163cb 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -55,19 +55,25 @@ void strbuf_attach(struct strbuf *sb, void *buf, size_t len, size_t alloc)\n \tsb->buf[sb->len] = '\\0';\n }\n \n-void strbuf_grow(struct strbuf *sb, size_t extra)\n+static inline void strbuf_grow_inline(struct strbuf *sb, size_t extra)\n {\n \tint new_buf = !sb->alloc;\n-\tif (unsigned_add_overflows(extra, 1) ||\n-\t unsigned_add_overflows(sb->len, extra + 1))\n+\tif (__builtin_add_overflow(extra, sb->len, &extra) ||\n+\t __builtin_add_overflow(extra, 1, &extra))\n \t\tdie(\"you want to use way too much memory\");\n \tif (new_buf)\n \t\tsb->buf = NULL;\n-\tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n+\tALLOC_GROW(sb->buf, extra, sb->alloc);\n \tif (new_buf)\n \t\tsb->buf[0] = '\\0';\n }\n \n+void strbuf_grow(struct strbuf *sb, size_t extra)\n+{\n+\tstrbuf_grow_inline(sb, extra);\n+}\n+#define strbuf_grow strbuf_grow_inline\n+\n void strbuf_trim(struct strbuf *sb)\n {\n \tstrbuf_rtrim(sb);\n\nThat drops my best-of-five for git-foo from:\n\n real 0m3.377s\n user 0m3.376s\n sys 0m0.000s\n\nto:\n\n real 0m3.107s\n user 0m3.104s\n sys 0m0.000s\n\nSo that's at least measurable. Again, though, I'm not convinced it\nactually matters much in the real world. But from what I see here, I'd\nbe surprised if the stack-buffer thing actually generates measurable\nimprovements here _or_ in the real world.\n\n-Peff\n"},{"id":"288115","messageId":"5750147C.5060609@alum.mit.edu","threadId":"42483","inReplyTo":"20160601210713.GA18118@sigill.intra.peff.net","subject":"Re: [PATCH 0/2] strbuf: improve API","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2016-06-02T11:11:56Z","receivedAt":"2016-06-02T11:11:56Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 06/01/2016 11:07 PM, Jeff King wrote:\n> On Wed, Jun 01, 2016 at 03:42:18AM -0400, Jeff King wrote:\n> \n>> I have no idea if those ideas would work. But I wouldn't want to start\n>> looking into either of them without some idea of how much time we're\n>> actually spending on strbuf mallocs (or how much time we would spend if\n>> strbufs were used in some proposed sites).\n> \n> So I tried to come up with some numbers.\n> \n> Here's an utterly silly use of strbufs, but one that I think should\n> over-emphasize the effect of any improvements we make:\n> \n> diff --git a/Makefile b/Makefile\n> index 7a0551a..72b968a 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -579,6 +579,7 @@ PROGRAM_OBJS += shell.o\n> PROGRAM_OBJS += show-index.o\n> PROGRAM_OBJS += upload-pack.o\n> PROGRAM_OBJS += remote-testsvn.o\n> +PROGRAM_OBJS += foo.o\n> \n> # Binary suffix, set to .exe for Windows builds\n> X =\n> diff --git a/foo.c b/foo.c\n> index e69de29..b62dd97 100644\n> --- a/foo.c\n> +++ b/foo.c\n> @@ -0,0 +1,18 @@\n> +#include \"git-compat-util.h\"\n> +#include \"strbuf.h\"\n> +\n> +int main(void)\n> +{\n> +\tconst char *str = \"this is a string that we'll repeatedly insert\";\n> +\tsize_t len = strlen(str);\n> +\n> +\tint i;\n> +\tfor (i = 0; i < 1000000; i++) {\n> +\t\tstruct strbuf buf = STRBUF_INIT;\n> +\t\tint j;\n> +\t\tfor (j = 0; j < 500; j++)\n> +\t\t\tstrbuf_add(&buf, str, len);\n> +\t\tstrbuf_release(&buf);\n> +\t}\n> +\treturn 0;\n> +}\n\nThanks for generating actual data.\n\nYour benchmark could do two things to stress malloc()/free()\neven more. I'm not claiming that this makes the benchmark more typical\nof real-world use, but it maybe gets us closer to the theoretical upper\nlimit on improvement.\n\n1. Since strbuf_grow() allocates new space in geometrically increasing\nsizes, the number of mallocs needed to do N strbuf_add()s increases only\nlike log(N). So decreasing the \"500\" would increase the fraction of the\ntime spent on allocations.\n\n2. Since the size of the string being appended increases the time spent\ncopying bytes, without appreciably changing the number of allocations\n(also because of geometric growth), decreasing the length of the string\nwould also increase the fraction of the time spent on allocations.\n\nI put those together as options, programmed several variants of the\nstring-concatenating loop, and added a perf script to run them; you can\nsee the full patch here:\n\n\nhttps://github.com/mhagger/git/commit/b417935a4425e0f2bf62e59a924dc652bb2eae0c\n\nThe guts look like this:\n\n> \tint j;\n> \tif (variant == 0) {\n> \t\t/* Use buffer allocated a single time */\n> \t\tchar *buf = big_constant_lifetime_buf;\n> \n> \t\tfor (j = 0; j < reps; j++)\n> \t\t\tstrcpy(buf + j * len, str);\n> \t} else if (variant == 1) {\n> \t\t/* One correct-sized buffer malloc per iteration */\n> \t\tchar *buf = xmalloc(reps * len + 1);\n> \n> \t\tfor (j = 0; j < reps; j++)\n> \t\t\tstrcpy(buf + j * len, str);\n> \n> \t\tfree(buf);\n> \t} else if (variant == 2) {\n> \t\t/* Conventional use of strbuf */\n> \t\tstruct strbuf buf = STRBUF_INIT;\n> \n> \t\tfor (j = 0; j < reps; j++)\n> \t\t\tstrbuf_add(&buf, str, len);\n> \n> \t\tstrbuf_release(&buf);\n> \t} else if (variant == 3) {\n> \t\t/* strbuf initialized to correct size */\n> \t\tstruct strbuf buf;\n> \t\tstrbuf_init(&buf, reps * len);\n> \n> \t\tfor (j = 0; j < reps; j++)\n> \t\t\tstrbuf_add(&buf, str, len);\n> \n> \t\tstrbuf_release(&buf);\n> \t} else if (variant == 4) {\n> \t\t/*\n> \t\t * Simulated fixed strbuf with correct size.\n> \t\t * This code only works because we know how\n> \t\t * strbuf works internally, namely that it\n> \t\t * will never realloc() or free() the buffer\n> \t\t * that we attach to it.\n> \t\t */\n> \t\tstruct strbuf buf = STRBUF_INIT;\n> \t\tstrbuf_attach(&buf, big_constant_lifetime_buf, 0, reps * len + 1);\n> \n> \t\tfor (j = 0; j < reps; j++)\n> \t\t\tstrbuf_add(&buf, str, len);\n> \n> \t\t/* No strbuf_release() here! */\n> \t}\n\nI ran this for a short string (\"short\") and a long string (\"this is a\nstring that we will repeatedly insert\"), and also concatenating the\nstring 5, 20, or 500 times. The number of loops around the whole program\nis normalized to make the total number of concatenations approximately\nconstant. Here are the full results:\n\n\n time (s)\nTest 0 1 2 3 4\n----------------------------------------------------\n5 short strings 1.64 3.37 8.72 6.08 3.65\n20 short strings 1.72 2.12 5.43 4.01 3.39\n500 short strings 1.62 1.61 3.36 3.26 3.10\n5 long strings 2.08 6.64 13.09 8.50 3.79\n20 long strings 2.16 3.33 7.03 4.72 3.55\n500 long strings 2.04 2.10 3.61 3.33 3.26\n\n\nColumn 0 is approximately the \"bare metal\" approach, with a\npre-allocated buffer and no strbuf overhead.\n\nColumn 1 is like column 0, except allocating a correctly-sized buffer\neach time through the loop. This increases the runtime by as much as 219%.\n\nColumn 2 is a naive use of strbuf, where each time through the loop the\nstrbuf is reinitialized to STRBUF_INIT, and managing the space is\nentirely left to strbuf.\n\nColumn 3 is like column 2, except that it initializes the strbuf to the\ncorrect size right away using strbuf_init(). This reduces the runtime\nrelative to column 2 by as much as 35%.\n\nColumn 4 uses a simulated \"fixed strbuf\", where the fixed-size buffer is\nbig enough for the full string (thus there are no calls to\nmalloc()/realloc()/free()).\n\nThe comparison between columns 0 and 4 shows that using a strbuf costs\nas much as 123% more than using a simple char array, even if the strbuf\ndoesn't have to do any memory allocations.\n\nThe comparison between columns 3 and 4 shows savings a reduction in\nruntime of up to 55% from using a \"fixed strbuf\" rather than a pre-sized\nconventional strbuf. I think this is the comparison that is most\nrelevant to the current discussion.\n\nOf course strbuf manipulation (especially of small numbers of strings)\nis unlikely to be a big fraction of the workload of any Git command, so\nthis is far from proof that this optimization is worthwhile in terms of\ncode complexity. But I am still moderately in favor of the idea, for two\nreasons:\n\n1. The amount of added code complexity is small and quite\n encapsulated.\n\n2. The ability to use strbufs without having to allocate memory might\n make enough *psychological* difference that it encourages some\n devs to use strbufs where they would otherwise have done manual\n memory management. I think this would be a *big* win in terms of\n potential bugs and security vulnerabilities avoided.\n\nMichael\n"},{"id":"288118","messageId":"vpqwpm7n3wx.fsf@anie.imag.fr","threadId":"42483","inReplyTo":"5750147C.5060609@alum.mit.edu","subject":"Re: [PATCH 0/2] strbuf: improve API","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@grenoble-inp.fr","sentAt":"2016-06-02T12:58:22Z","receivedAt":"2016-06-02T12:58:22Z","isPatch":true,"sender":{"key":"matthieu.moy@grenoble-inp.fr","avatar":"https://gravatar.com/avatar/72c8a2705971a25dfaff23cece15130d405685845d911aedd5667ace277f3fc5?d=mp&s=160"},"body":"Michael Haggerty writes:\n\n> 1. The amount of added code complexity is small and quite\n> encapsulated.\n\nActually, STRBUF_OWNS_MEMORY can even be seen as a simplification if\ndone properly: we already have the case where the strbuf does not own\nthe memory with strbuf_slopbuf. I already pointed places in\nstrbuf_grow() which could be simplified after the patch. Re-reading the\ncode it seems at lesat the call to strbuf_grow(sb, 0); in strbuf_detach\nbecomes useless. The same in strbuf_attach() probably is, too.\n\nSo, the final strbuf.[ch] code might not be \"worse\" that the previous.\n\nI'm unsure about the complexity of the future code using the new API. I\ndon't forsee cases where using the new API would lead to a high\nmaintenance cost, but I don't claim I considered all possible uses.\n\n> 2. The ability to use strbufs without having to allocate memory might\n> make enough *psychological* difference that it encourages some\n> devs to use strbufs where they would otherwise have done manual\n> memory management. I think this would be a *big* win in terms of\n> potential bugs and security vulnerabilities avoided.\n\nNote that this can also be seen as a counter-argument, since it\nmay psychologically encourage people to micro-optimize code and use\ncontributors/reviewers neurons to spend time on \"shall this be on-stack\nor malloced?\".\n\nI think we already have a tendency to micro-optimize non-critical code\ntoo much in Git's codebase, so it's not necessarily a step in the right\ndirection.\n\nIn conclusion, I don't have a conclusion, sorry ;-).\n\n-- \nMatthieu Moy\nhttp://www-verimag.imag.fr/~moy/\n"},{"id":"288121","messageId":"20160602142205.GA5566@Messiaen","threadId":"42483","inReplyTo":"vpqwpm7n3wx.fsf@anie.imag.fr","subject":"Re: [PATCH 0/2] strbuf: improve API","fromName":"William Duclot","fromEmail":"william.duclot@ensimag.grenoble-inp.fr","sentAt":"2016-06-02T14:22:05Z","receivedAt":"2016-06-02T14:22:05Z","isPatch":true,"sender":{"key":"william.duclot@ensimag.grenoble-inp.fr","avatar":null},"body":"On Thu, Jun 02, 2016 at 02:58:22PM +0200, Matthieu Moy wrote:\n> Michael Haggerty writes:\n> \n>> 1. The amount of added code complexity is small and quite\n>> encapsulated.\n> \n> Actually, STRBUF_OWNS_MEMORY can even be seen as a simplification if\n> done properly: we already have the case where the strbuf does not own\n> the memory with strbuf_slopbuf. I already pointed places in\n> strbuf_grow() which could be simplified after the patch. Re-reading the\n> code it seems at lesat the call to strbuf_grow(sb, 0); in strbuf_detach\n> becomes useless. The same in strbuf_attach() probably is, too.\n> \n> So, the final strbuf.[ch] code might not be \"worse\" that the previous.\n> \n> I'm unsure about the complexity of the future code using the new API. I\n> don't forsee cases where using the new API would lead to a high\n> maintenance cost, but I don't claim I considered all possible uses.\n> \n>> 2. The ability to use strbufs without having to allocate memory might\n>> make enough *psychological* difference that it encourages some\n>> devs to use strbufs where they would otherwise have done manual\n>> memory management. I think this would be a *big* win in terms of\n>> potential bugs and security vulnerabilities avoided.\n> \n> Note that this can also be seen as a counter-argument, since it\n> may psychologically encourage people to micro-optimize code and use\n> contributors/reviewers neurons to spend time on \"shall this be on-stack\n> or malloced?\".\n> \n> I think we already have a tendency to micro-optimize non-critical code\n> too much in Git's codebase, so it's not necessarily a step in the right\n> direction.\n> \n> In conclusion, I don't have a conclusion, sorry ;-).\n\nThank you all for your input and your tests, those are very valuable!\nMe and Simon have to take a decision, as this contribution is part of a\nschool project that comes to an end. We won't have the time to create\ntests that are representative of the use of strbuf in the Git codebase\n(partly because we lack knowledge of the codebase) to settle on whether\nthis API improvement is useful or not.\n\nJeff made very good points, and the tests we ran ourselves seem to\nagree with yours. That being said, the tests made by Michael, more\ndetailed, suggest that there may be room for an improvement of the\nstrbuf API (even thought that's to confront to the reality of the\ncodebase).\n\nHaving little time, we will refactor the patch and send it as a V2: this\nway, if it appears one day that improving the API with stack-allocated\nmemory is indeed useful, the patch will be ready to merge :)\n"},{"id":"288251","messageId":"20160603140444.GA3903@Messiaen","threadId":"42483","inReplyTo":"574D0D99.6080303@alum.mit.edu","subject":"Re: [PATCH 2/2] strbuf: allow to use preallocated memory","fromName":"William Duclot","fromEmail":"william.duclot@ensimag.grenoble-inp.fr","sentAt":"2016-06-03T14:04:44Z","receivedAt":"2016-06-03T14:04:44Z","isPatch":true,"sender":{"key":"william.duclot@ensimag.grenoble-inp.fr","avatar":null},"body":"On Tue, May 31, 2016 at 06:05:45AM +0200, Michael Haggerty wrote:\n> When reading this patch series, I found I had trouble remembering\n> whether \"preallocated\" meant \"preallocated and movable\" or \"preallocated\n> and immovable\". So maybe we should brainstorm alternatives to\n> \"preallocated\" and \"fixed\". For example,\n> \n> * \"growable\"/\"fixed\"? Seems OK, though all strbufs are growable at least\n> to the size of their initial allocation, so maybe \"growable\" is misleading.\n> \n> * \"movable\"/\"fixed\"? This maybe better captures the essence of the\n> distinction. I'll use those names below for concreteness, without\n> claiming that they are the best.\n> \n> [...]\n> \n> The functions might be\n> named more like `strbuf_attach()` to emphasize their similarity to that\n> existing function. Maybe\n> \n> strbuf_attach_fixed(struct strbuf *sb, void *s, size_t len, size_t\n> alloc);\n> strbuf_attach_movable(struct strbuf *sb, void *s, size_t len, size_t\n> alloc);\n\nNow that I am looking in detail into it, I am not so convinced by those\nnames. Using \"attach\" suggests the same behavior as strbuf_attach(),\nwhich is _not_ the case to me:\n - The aim of the attach() function is to give ownership of a\n buffer allocated by the caller to the strbuf.\n - The aim of the wrap() functions is to give the right to use a\n buffer allocated by the caller to the strbuf, while keeping\n ownership.\n - For completion: the aim of the init() function is to let the\n strbuf manage its own buffer.\n\nI think that it is important to distinct those 3 use cases for the API user\nto be able to understand. And to describe this API extension, \"wrap\"\nseems clear to me.\nAnother point that would makes me skeptical about using\n`strbuf_attach_preallocated()` is that the real difference with\n`strbuf_attach()` isn't in the allocation of the buffer parameter, it is\nin the ownership. Both takes a buffer allocated by the user as\nparameter (so a preallocated buffer), even thought\n`strbuf_attach_preallocated()` may use a stack-allocated one.\n\nSo I come to the conclusion that even using the word \"preallocated\" may\nnot be such a good idea, as even strbuf_attach() use a preallocated\nbuffer. What I think would be the clearer would be:\n\n - strbuf_attach() (unchanged)\n - strbuf_wrap() (no need for the \"preallocated\")\n - strbuf_wrap_fixed()\n - STRBUF_WRAP \n - STRBUF_WRAP_FIXED\n\nThe two last ones would be macros, equivalent to the functions except\nthat they don't release the strbuf before initializing it.\n\nWhat do you think about this?\n"},{"id":"290032","messageId":"20160624172037.GA3273@sigill.intra.peff.net","threadId":"42483","inReplyTo":"5750147C.5060609@alum.mit.edu","subject":"Re: [PATCH 0/2] strbuf: improve API","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-06-24T17:20:37Z","receivedAt":"2016-06-24T17:20:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 02, 2016 at 01:11:56PM +0200, Michael Haggerty wrote:\n\n> On 06/01/2016 11:07 PM, Jeff King wrote:\n> > On Wed, Jun 01, 2016 at 03:42:18AM -0400, Jeff King wrote:\n> > \n> >> I have no idea if those ideas would work. But I wouldn't want to start\n> >> looking into either of them without some idea of how much time we're\n> >> actually spending on strbuf mallocs (or how much time we would spend if\n> >> strbufs were used in some proposed sites).\n> > \n> > So I tried to come up with some numbers.\n> > \n> > Here's an utterly silly use of strbufs, but one that I think should\n> > over-emphasize the effect of any improvements we make:\n> [...]\n> \n> Thanks for generating actual data.\n\nThanks for following up on this, and sorry for my slow response. It got\nput in my \"to think about and respond to later\" pile (never a good place\nto be :) ).\n\n> Your benchmark could do two things to stress malloc()/free()\n> even more. I'm not claiming that this makes the benchmark more typical\n> of real-world use, but it maybe gets us closer to the theoretical upper\n> limit on improvement.\n\nYeah, you're right. I added more writes to try to actually stimulate the\nstrbuf to grow, but if the point is to call malloc in a tight loop, it\nworks against that (I agree that malloc-in-a-tight-loop does not\nnecessarily represent a real workload, but I think the point of this\nexercise is to make sure we can get a useful speedup even under\ntheoretical conditions).\n\n> I ran this for a short string (\"short\") and a long string (\"this is a\n> string that we will repeatedly insert\"), and also concatenating the\n> string 5, 20, or 500 times. The number of loops around the whole program\n> is normalized to make the total number of concatenations approximately\n> constant. Here are the full results:\n\nI suspect \"5 short\" and \"5 long\" are the only really interesting cases.\nFor the cases we're talking about, the author clearly expects most input\nto fit into a single small-ish allocation (or else they would not bother\nwith the fixed strbuf in the first place). So \"500 long\" is really just\nexercising memcpy.\n\n> Test 0 1 2 3 4\n> ----------------------------------------------------\n> 5 short strings 1.64 3.37 8.72 6.08 3.65\n> 20 short strings 1.72 2.12 5.43 4.01 3.39\n> 500 short strings 1.62 1.61 3.36 3.26 3.10\n> 5 long strings 2.08 6.64 13.09 8.50 3.79\n> 20 long strings 2.16 3.33 7.03 4.72 3.55\n> 500 long strings 2.04 2.10 3.61 3.33 3.26\n> \n> \n> Column 0 is approximately the \"bare metal\" approach, with a\n> pre-allocated buffer and no strbuf overhead.\n> \n> Column 1 is like column 0, except allocating a correctly-sized buffer\n> each time through the loop. This increases the runtime by as much as 219%.\n\nMakes sense. malloc() isn't free (no pun intended).\n\nAnd I think this shows why the 20/500 cases aren't all that interesting,\nas we really just end up measuring memcpy.\n\n> Column 2 is a naive use of strbuf, where each time through the loop the\n> strbuf is reinitialized to STRBUF_INIT, and managing the space is\n> entirely left to strbuf.\n\nI'd think this would be about the same as column 1 for our interesting\ncases, modulo some strbuf overhead. But it's way higher. That implies\nthat either:\n\n 1. Strbuf overhead is high (and I think in a really tight loop like\n this that things like our overflow checks might start to matter; we\n could be doing those with intrinsics, for example).\n\n 2. We're doing multiple mallocs per strbuf, which implies our initial\n sizes could be a bit more aggressive (it's not like the 30-byte\n \"short\" case is that huge).\n\n> Column 3 is like column 2, except that it initializes the strbuf to the\n> correct size right away using strbuf_init(). This reduces the runtime\n> relative to column 2 by as much as 35%.\n\nThat should show us the effects of multiple-allocations (my (2) above).\nAnd indeed, it counts for some of it but not all.\n\n> Column 4 uses a simulated \"fixed strbuf\", where the fixed-size buffer is\n> big enough for the full string (thus there are no calls to\n> malloc()/realloc()/free()).\n> \n> The comparison between columns 0 and 4 shows that using a strbuf costs\n> as much as 123% more than using a simple char array, even if the strbuf\n> doesn't have to do any memory allocations.\n\nYeah, I can believe there is overhead in all of the \"are we big enough\"\nchecks (though I'd hope that for the no-allocation cases we simply rely\non snprintf to tell us \"yes, you fit\").\n\n> The comparison between columns 3 and 4 shows savings a reduction in\n> runtime of up to 55% from using a \"fixed strbuf\" rather than a pre-sized\n> conventional strbuf. I think this is the comparison that is most\n> relevant to the current discussion.\n\nI'm including a patch at the end of this mail that implements a \"variant\n5\", which essentially keeps a single-buffer cache of the last-released\nstrbuf, and reuses it. Other than that, it is identical to 2 (no tricks,\nnot even a size hint, in the caller).\n\nThat skips the malloc/free cycle entirely for loops like this (or any\nwhere your malloc/free are matched, and you're not using multiple\nstrbufs or interleaving detached ones).\n\nHere are the numbers from my machine with that variant added in:\n\nTest 0 1 2 3 4 5\n------------------------------------------------------------\n5 short strings 1.99 3.95 8.80 5.96 3.56 3.53\n20 short strings 2.00 2.49 5.44 3.83 3.29 3.22\n500 short strings 1.86 1.90 3.21 3.00 2.99 3.00\n5 long strings 2.22 5.30 12.07 7.47 3.71 3.50\n20 long strings 2.31 2.97 6.99 4.37 3.39 3.32\n500 long strings 2.14 2.16 3.50 3.14 3.14 3.46\n\nUnsurprisingly, it performs about as well as the fixed buffer on this\ntest, because this is the optimal case for it. The question remains open\nwhether it would do so in real code practice (I also ignored threading\nin my patch, which might add some overhead).\n\nBut it also shows that glibc malloc is kind of expensive. I expected it\nto be able to optimize this case pretty well. I tried running your tests\nagainst tcmalloc. It's definitely better than glibc, but still not as\nfast as either variants 4 or 5.\n\n> Of course strbuf manipulation (especially of small numbers of strings)\n> is unlikely to be a big fraction of the workload of any Git command, so\n> this is far from proof that this optimization is worthwhile in terms of\n> code complexity. But I am still moderately in favor of the idea, for two\n> reasons:\n> \n> 1. The amount of added code complexity is small and quite\n> encapsulated.\n\nActually, this is the part I am most concerned about. The code itself is\nencapsulated, but it adds a new decision to every caller: should I be\nusing a stack buffer? How big?\n\nI already hate the \"hint\" field for the same reason. It's just one more\ncomplication to think about during writing and review.\n\nThat's why I prefer something like my variant-5, even if it ends up\nbeing more code (e.g., to do thread-local storage). It means things Just\nWork, and the caller does not have to care about micro-optimizing.\n\n> 2. The ability to use strbufs without having to allocate memory might\n> make enough *psychological* difference that it encourages some\n> devs to use strbufs where they would otherwise have done manual\n> memory management. I think this would be a *big* win in terms of\n> potential bugs and security vulnerabilities avoided.\n\nYeah, I agree there is definitely a psychological difference. I was\nhoping to provide evidence that it's merely superstition to combat that.\nUnfortunately, this conversation has left me less certain than ever. :)\n\n-Peff\n\n---\ndiff --git a/strbuf.c b/strbuf.c\nindex 1ba600b..ec40c1a 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -18,6 +18,10 @@ int starts_with(const char *str, const char *prefix)\n */\n char strbuf_slopbuf[1];\n \n+int use_buf_cache;\n+static char *buf_cache;\n+static size_t alloc_cache;\n+\n void strbuf_init(struct strbuf *sb, size_t hint)\n {\n \tsb->alloc = sb->len = 0;\n@@ -29,7 +33,12 @@ void strbuf_init(struct strbuf *sb, size_t hint)\n void strbuf_release(struct strbuf *sb)\n {\n \tif (sb->alloc) {\n-\t\tfree(sb->buf);\n+\t\tif (use_buf_cache && !buf_cache && sb->len < 4096) {\n+\t\t\tbuf_cache = sb->buf;\n+\t\t\talloc_cache = sb->alloc;\n+\t\t} else {\n+\t\t\tfree(sb->buf);\n+\t\t}\n \t\tstrbuf_init(sb, 0);\n \t}\n }\n@@ -61,8 +70,16 @@ void strbuf_grow(struct strbuf *sb, size_t extra)\n \tif (unsigned_add_overflows(extra, 1) ||\n \t unsigned_add_overflows(sb->len, extra + 1))\n \t\tdie(\"you want to use way too much memory\");\n-\tif (new_buf)\n-\t\tsb->buf = NULL;\n+\tif (new_buf) {\n+\t\tif (buf_cache) {\n+\t\t\tsb->buf = buf_cache;\n+\t\t\tsb->alloc = alloc_cache;\n+\t\t\tbuf_cache = NULL;\n+\t\t\talloc_cache = 0;\n+\t\t} else {\n+\t\t\tsb->buf = NULL;\n+\t\t}\n+\t}\n \tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n \tif (new_buf)\n \t\tsb->buf[0] = '\\0';\ndiff --git a/t/helper/test-strbuf-perf.c b/t/helper/test-strbuf-perf.c\nindex 13c437c..516905a 100644\n--- a/t/helper/test-strbuf-perf.c\n+++ b/t/helper/test-strbuf-perf.c\n@@ -13,6 +13,8 @@\n #include \"git-compat-util.h\"\n #include \"strbuf.h\"\n \n+extern int use_buf_cache;\n+\n int main(int argc, char *argv[])\n {\n \tconst char *str;\n@@ -55,6 +57,9 @@ int main(int argc, char *argv[])\n \t}\n \tfprintf(stderr, \"count = '%d'\\n\", count);\n \n+\tif (variant == 5)\n+\t\tuse_buf_cache = 1;\n+\n \tbig_constant_lifetime_buf = xmalloc(total_len + 1);\n \tfor (i = 0; i < count; i++) {\n \t\tint j;\n@@ -72,7 +77,7 @@ int main(int argc, char *argv[])\n \t\t\t\tstrcpy(buf + j * len, str);\n \n \t\t\tfree(buf);\n-\t\t} else if (variant == 2) {\n+\t\t} else if (variant == 2 || variant == 5) {\n \t\t\t/* Conventional use of strbuf */\n \t\t\tstruct strbuf buf = STRBUF_INIT;\n \ndiff --git a/t/perf/p0003-strbuf.sh b/t/perf/p0003-strbuf.sh\nindex 2be1908..5530197 100755\n--- a/t/perf/p0003-strbuf.sh\n+++ b/t/perf/p0003-strbuf.sh\n@@ -5,7 +5,7 @@ test_description='Benchmark different uses of strbuf'\n \n test_perf_default_repo\n \n-for variant in $(seq 0 4)\n+for variant in $(seq 0 5)\n do\n \texport variant\n \ttest_perf \"variant $variant, 5 short strings\" '\n@@ -13,7 +13,7 @@ do\n \t'\n done\n \n-for variant in $(seq 0 4)\n+for variant in $(seq 0 5)\n do\n \texport variant\n \ttest_perf \"variant $variant, 20 short strings\" '\n@@ -21,7 +21,7 @@ do\n \t'\n done\n \n-for variant in $(seq 0 4)\n+for variant in $(seq 0 5)\n do\n \texport variant\n \ttest_perf \"variant $variant, 500 short strings\" '\n@@ -29,7 +29,7 @@ do\n \t'\n done\n \n-for variant in $(seq 0 4)\n+for variant in $(seq 0 5)\n do\n \texport variant\n \ttest_perf \"variant $variant, 5 long strings\" '\n@@ -37,7 +37,7 @@ do\n \t'\n done\n \n-for variant in $(seq 0 4)\n+for variant in $(seq 0 5)\n do\n \texport variant\n \ttest_perf \"variant $variant, 20 long strings\" '\n@@ -45,7 +45,7 @@ do\n \t'\n done\n \n-for variant in $(seq 0 4)\n+for variant in $(seq 0 5)\n do\n \texport variant\n \ttest_perf \"variant $variant, 500 long strings\" '\n"}]}