{"thread":{"id":"60648","subject":"[PATCH] mem-pool: fix big allocations","startedAt":"2023-12-21T23:13:21Z","lastAt":"2024-01-02T22:29:16Z","messageCount":12,"participants":["René Scharfe","Elijah Newren","Phillip Wood","phillip.wood123@gmail.com","Taylor Blau"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"485967","messageId":"fa89d269-1a23-4ed6-bebc-30c0b629f444@web.de","threadId":"60648","inReplyTo":null,"subject":"[PATCH] mem-pool: fix big allocations","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2023-12-21T23:13:16Z","receivedAt":"2023-12-21T23:13:21Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Memory pool allocations that require a new block and would fill at\nleast half of it are handled specially. Before 158dfeff3d (mem-pool:\nadd life cycle management functions, 2018-07-02) they used to be\nallocated outside of the pool. This patch made mem_pool_alloc() create\na bespoke block instead, to allow releasing it when the pool gets\ndiscarded.\n\nUnfortunately mem_pool_alloc() returns a pointer to the start of such a\nbespoke block, i.e. to the struct mp_block at its top. When the caller\nwrites to it, the management information gets corrupted. This affects\nmem_pool_discard() and -- if there are no other blocks in the pool --\nalso mem_pool_alloc().\n\nReturn the payload pointer of bespoke blocks, just like for smaller\nallocations, to protect the management struct.\n\nAlso update next_free to mark the block as full. This is only strictly\nnecessary for the first allocated block, because subsequent ones are\ninserted after the current block and never considered for further\nallocations, but it's easier to just do it in all cases.\n\nAdd a basic unit test to demonstate the issue by using mem_pool_calloc()\nwith a tiny block size, which forces the creation of a bespoke block.\nWithout the mem_pool_alloc() fix it reports zeroed pointers:\n\n ok 1 - mem_pool_calloc returns 100 zeroed bytes with big block\n # check \"((pool->mp_block->next_free) != (((void*)0))) == 1\" failed at t/unit-tests/t-mem-pool.c:22\n # left: 0\n # right: 1\n # check \"((pool->mp_block->end) != (((void*)0))) == 1\" failed at t/unit-tests/t-mem-pool.c:23\n # left: 0\n # right: 1\n not ok 2 - mem_pool_calloc returns 100 zeroed bytes with tiny block\n 1..2\n\nSigned-off-by: René Scharfe \n---\n Makefile | 1 +\n mem-pool.c | 6 +++---\n t/unit-tests/t-mem-pool.c | 34 ++++++++++++++++++++++++++++++++++\n 3 files changed, 38 insertions(+), 3 deletions(-)\n create mode 100644 t/unit-tests/t-mem-pool.c\n\ndiff --git a/Makefile b/Makefile\nindex 88ba7a3c51..15990ff312 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1340,6 +1340,7 @@ THIRD_PARTY_SOURCES += sha1collisiondetection/%\n THIRD_PARTY_SOURCES += sha1dc/%\n\n UNIT_TEST_PROGRAMS += t-basic\n+UNIT_TEST_PROGRAMS += t-mem-pool\n UNIT_TEST_PROGRAMS += t-strbuf\n UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))\n UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))\ndiff --git a/mem-pool.c b/mem-pool.c\nindex c34846d176..e8d976c3ee 100644\n--- a/mem-pool.c\n+++ b/mem-pool.c\n@@ -99,9 +99,9 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len)\n\n \tif (!p) {\n \t\tif (len >= (pool->block_alloc / 2))\n-\t\t\treturn mem_pool_alloc_block(pool, len, pool->mp_block);\n-\n-\t\tp = mem_pool_alloc_block(pool, pool->block_alloc, NULL);\n+\t\t\tp = mem_pool_alloc_block(pool, len, pool->mp_block);\n+\t\telse\n+\t\t\tp = mem_pool_alloc_block(pool, pool->block_alloc, NULL);\n \t}\n\n \tr = p->next_free;\ndiff --git a/t/unit-tests/t-mem-pool.c b/t/unit-tests/t-mem-pool.c\nnew file mode 100644\nindex 0000000000..2295779b0b\n--- /dev/null\n+++ b/t/unit-tests/t-mem-pool.c\n@@ -0,0 +1,34 @@\n+#include \"test-lib.h\"\n+#include \"mem-pool.h\"\n+\n+#define check_ptr(a, op, b) check_int(((a) op (b)), ==, 1)\n+\n+static void setup_static(void (*f)(struct mem_pool *), size_t block_alloc)\n+{\n+\tstruct mem_pool pool = { .block_alloc = block_alloc };\n+\tf(&pool);\n+\tmem_pool_discard(&pool, 0);\n+}\n+\n+static void t_calloc_100(struct mem_pool *pool)\n+{\n+\tsize_t size = 100;\n+\tchar *buffer = mem_pool_calloc(pool, 1, size);\n+\tfor (size_t i = 0; i < size; i++)\n+\t\tcheck_int(buffer[i], ==, 0);\n+\tif (!check_ptr(pool->mp_block, !=, NULL))\n+\t\treturn;\n+\tcheck_ptr(pool->mp_block->next_free, <=, pool->mp_block->end);\n+\tcheck_ptr(pool->mp_block->next_free, !=, NULL);\n+\tcheck_ptr(pool->mp_block->end, !=, NULL);\n+}\n+\n+int cmd_main(int argc, const char **argv)\n+{\n+\tTEST(setup_static(t_calloc_100, 1024 * 1024),\n+\t \"mem_pool_calloc returns 100 zeroed bytes with big block\");\n+\tTEST(setup_static(t_calloc_100, 1),\n+\t \"mem_pool_calloc returns 100 zeroed bytes with tiny block\");\n+\n+\treturn test_done();\n+}\n--\n2.43.0\n"},{"id":"486008","messageId":"CABPp-BFiK9A6426d7CFeMZvaBcvmShaY9O0krtCe7jeV9wW7nQ@mail.gmail.com","threadId":"60648","inReplyTo":"fa89d269-1a23-4ed6-bebc-30c0b629f444@web.de","subject":"Re: [PATCH] mem-pool: fix big allocations","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2023-12-24T03:11:57Z","receivedAt":"2023-12-24T03:12:10Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Dec 21, 2023 at 3:13 PM René Scharfe wrote:\n>\n> Memory pool allocations that require a new block and would fill at\n> least half of it are handled specially. Before 158dfeff3d (mem-pool:\n> add life cycle management functions, 2018-07-02) they used to be\n> allocated outside of the pool. This patch made mem_pool_alloc() create\n> a bespoke block instead, to allow releasing it when the pool gets\n> discarded.\n>\n> Unfortunately mem_pool_alloc() returns a pointer to the start of such a\n> bespoke block, i.e. to the struct mp_block at its top. When the caller\n> writes to it, the management information gets corrupted. This affects\n> mem_pool_discard() and -- if there are no other blocks in the pool --\n> also mem_pool_alloc().\n>\n> Return the payload pointer of bespoke blocks, just like for smaller\n> allocations, to protect the management struct.\n>\n> Also update next_free to mark the block as full. This is only strictly\n> necessary for the first allocated block, because subsequent ones are\n> inserted after the current block and never considered for further\n> allocations, but it's easier to just do it in all cases.\n>\n> Add a basic unit test to demonstate the issue by using mem_pool_calloc()\n\ndemonstrate (missing 'r')?\n\n> with a tiny block size, which forces the creation of a bespoke block.\n> Without the mem_pool_alloc() fix it reports zeroed pointers:\n>\n> ok 1 - mem_pool_calloc returns 100 zeroed bytes with big block\n> # check \"((pool->mp_block->next_free) != (((void*)0))) == 1\" failed at t/unit-tests/t-mem-pool.c:22\n> # left: 0\n> # right: 1\n> # check \"((pool->mp_block->end) != (((void*)0))) == 1\" failed at t/unit-tests/t-mem-pool.c:23\n> # left: 0\n> # right: 1\n> not ok 2 - mem_pool_calloc returns 100 zeroed bytes with tiny block\n> 1..2\n>\n> Signed-off-by: René Scharfe \n> ---\n> Makefile | 1 +\n> mem-pool.c | 6 +++---\n> t/unit-tests/t-mem-pool.c | 34 ++++++++++++++++++++++++++++++++++\n> 3 files changed, 38 insertions(+), 3 deletions(-)\n> create mode 100644 t/unit-tests/t-mem-pool.c\n>\n> diff --git a/Makefile b/Makefile\n> index 88ba7a3c51..15990ff312 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -1340,6 +1340,7 @@ THIRD_PARTY_SOURCES += sha1collisiondetection/%\n> THIRD_PARTY_SOURCES += sha1dc/%\n>\n> UNIT_TEST_PROGRAMS += t-basic\n> +UNIT_TEST_PROGRAMS += t-mem-pool\n> UNIT_TEST_PROGRAMS += t-strbuf\n> UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))\n> UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))\n> diff --git a/mem-pool.c b/mem-pool.c\n> index c34846d176..e8d976c3ee 100644\n> --- a/mem-pool.c\n> +++ b/mem-pool.c\n> @@ -99,9 +99,9 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len)\n>\n> if (!p) {\n> if (len >= (pool->block_alloc / 2))\n> - return mem_pool_alloc_block(pool, len, pool->mp_block);\n> -\n> - p = mem_pool_alloc_block(pool, pool->block_alloc, NULL);\n> + p = mem_pool_alloc_block(pool, len, pool->mp_block);\n> + else\n> + p = mem_pool_alloc_block(pool, pool->block_alloc, NULL);\n> }\n>\n> r = p->next_free;\n> diff --git a/t/unit-tests/t-mem-pool.c b/t/unit-tests/t-mem-pool.c\n> new file mode 100644\n> index 0000000000..2295779b0b\n> --- /dev/null\n> +++ b/t/unit-tests/t-mem-pool.c\n> @@ -0,0 +1,34 @@\n> +#include \"test-lib.h\"\n> +#include \"mem-pool.h\"\n> +\n> +#define check_ptr(a, op, b) check_int(((a) op (b)), ==, 1)\n> +\n> +static void setup_static(void (*f)(struct mem_pool *), size_t block_alloc)\n> +{\n> + struct mem_pool pool = { .block_alloc = block_alloc };\n> + f(&pool);\n> + mem_pool_discard(&pool, 0);\n> +}\n> +\n> +static void t_calloc_100(struct mem_pool *pool)\n> +{\n> + size_t size = 100;\n> + char *buffer = mem_pool_calloc(pool, 1, size);\n> + for (size_t i = 0; i < size; i++)\n> + check_int(buffer[i], ==, 0);\n> + if (!check_ptr(pool->mp_block, !=, NULL))\n> + return;\n> + check_ptr(pool->mp_block->next_free, <=, pool->mp_block->end);\n> + check_ptr(pool->mp_block->next_free, !=, NULL);\n> + check_ptr(pool->mp_block->end, !=, NULL);\n> +}\n> +\n> +int cmd_main(int argc, const char **argv)\n> +{\n> + TEST(setup_static(t_calloc_100, 1024 * 1024),\n> + \"mem_pool_calloc returns 100 zeroed bytes with big block\");\n> + TEST(setup_static(t_calloc_100, 1),\n> + \"mem_pool_calloc returns 100 zeroed bytes with tiny block\");\n> +\n> + return test_done();\n> +}\n> --\n> 2.43.0\n\nNice catch; looks good to me. Out of curiosity, how'd you find the issue?\n"},{"id":"486013","messageId":"459f63b9-8246-4216-9163-fe69d5ceee83@web.de","threadId":"60648","inReplyTo":"CABPp-BFiK9A6426d7CFeMZvaBcvmShaY9O0krtCe7jeV9wW7nQ@mail.gmail.com","subject":"Re: [PATCH] mem-pool: fix big allocations","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2023-12-24T09:30:32Z","receivedAt":"2023-12-24T09:30:43Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 24.12.23 um 04:11 schrieb Elijah Newren:\n> On Thu, Dec 21, 2023 at 3:13 PM René Scharfe wrote:\n>>\n>> Add a basic unit test to demonstate the issue by using mem_pool_calloc()\n>\n> demonstrate (missing 'r')?\n\nYes. I didn't intend to mention any demons or states, let alone a\ndemon state. *facepalm*\n\n> Nice catch; looks good to me. Out of curiosity, how'd you find the issue?\n\nI was working on using a memory pool for name-rev. I played with\ndifferent values for block_alloc, not fully sure why anymore -- either\nfor checking the performance impact or testing robustness.\n\nRené\n"},{"id":"486121","messageId":"9aad15c8-8d3b-475b-bd44-5d24121cb793@gmail.com","threadId":"60648","inReplyTo":"fa89d269-1a23-4ed6-bebc-30c0b629f444@web.de","subject":"Re: [PATCH] mem-pool: fix big allocations","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2023-12-28T15:10:22Z","receivedAt":"2023-12-28T15:10:26Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi René\n\nOn 21/12/2023 23:13, René Scharfe wrote:\n> +#define check_ptr(a, op, b) check_int(((a) op (b)), ==, 1)\n> [...]\n> +static void t_calloc_100(struct mem_pool *pool)\n> +{\n> +\tsize_t size = 100;\n> +\tchar *buffer = mem_pool_calloc(pool, 1, size);\n> +\tfor (size_t i = 0; i < size; i++)\n> +\t\tcheck_int(buffer[i], ==, 0);\n> +\tif (!check_ptr(pool->mp_block, !=, NULL))\n> +\t\treturn;\n> +\tcheck_ptr(pool->mp_block->next_free, <=, pool->mp_block->end);\n> +\tcheck_ptr(pool->mp_block->next_free, !=, NULL);\n> +\tcheck_ptr(pool->mp_block->end, !=, NULL);\n> +}\n\nIt's great to see the unit test framework being used here. I wonder\nthough if it would be simpler just to use\n\n\tcheck(ptr != NULL)\n\nas I'm not sure what the check_ptr() macro adds. The diff at the end of\nthis email shows a possible implementation of a check_ptr() macro for\nthe unit test library. I'm wary of adding it though because I'm not sure\nprinting the pointer values is actually very useful most of the\ntime. I'm also concerned that the rules around pointer arithmetic and\ncomparisons mean that many pointer tests such as\n\n check_ptr(pool->mp_block->next_free, <=, pool->mp_block->end);\n\nwill be undefined if they fail. The documentation for check_ptr() below\ntries to illustrate that concern. If the compiler can prove that a check\nis undefined when that check fails it is at liberty to hard code the\ntest as passing. In practice I think most failing pointer comparisons\nwould fall into the category of \"this is undefined but the compiler\ncan't prove it\" but that doesn't really make me any happier.\n\nBest Wishes\n\nPhillip\n\n---- >8 ----\ndiff --git a/t/unit-tests/test-lib.h b/t/unit-tests/test-lib.h\nindex a8f07ae0b7..ecd1fce17d 100644\n--- a/t/unit-tests/test-lib.h\n+++ b/t/unit-tests/test-lib.h\n@@ -99,6 +99,39 @@ int check_int_loc(const char *loc, const char *check, int ok,\n int check_uint_loc(const char *loc, const char *check, int ok,\n \t\t uintmax_t a, uintmax_t b);\n \n+/*\n+ * Compare two pointers. Prints a message with the two values if the\n+ * comparison fails. NB this is not thread safe.\n+ *\n+ * Use this with care. The rules around pointer arithmetic and comparison\n+ * in C are quite strict and violating them results in undefined behavior\n+ * To avoid a failing comparison resulting undefined behavior we compare\n+ * the integer value of the pointers. While this avoids undefined\n+ * behavior in the comparison in many cases a failing test will be the\n+ * result of creating an invalid pointer in a way that violates the\n+ * rules on pointer arithmetic. For example if `start` and `end` are\n+ * pointers to the beginning and end of an allocation and `offset` is an\n+ * integer then\n+ *\n+ * check_ptr(start + offset, <=, end)\n+ *\n+ * is undefined when `offset` is larger than `end - start`. Rewriting the\n+ * comparison as\n+ *\n+ * check_uint(offset, <=, end - start)\n+ *\n+ * avoids undefined behavior when offset is too large, but is still\n+ * undefined if there is a bug that means `start` and `end` do not point\n+ * to the same allocation.\n+ */\n+#define check_ptr(a, op, b)\t\t\t\t\t\t\\\n+\t(test__tmp[0].p = (a), test__tmp[1].p = (b),\t\t\t\\\n+\t check_ptr_loc(TEST_LOCATION(), #a\" \"#op\" \"#b,\t\t\t\\\n+\t\t (uintptr_t)test__tmp[0].p op (uintptr_t)test__tmp[1].p,\t\\\n+\t\t\ttest__tmp[0].p, test__tmp[1].p))\n+\n+int check_ptr_loc(const char *loc, const char *check, int ok, void *a, void *b);\n+\n /*\n * Compare two chars. Prints a message with the two values if the\n * comparison fails. NB this is not thread safe.\n@@ -133,6 +166,7 @@ int check_str_loc(const char *loc, const char *check,\n #define TEST__MAKE_LOCATION(line) __FILE__ \":\" TEST__STR(line)\n \n union test__tmp {\n+\tvoid *p;\n \tintmax_t i;\n \tuintmax_t u;\n \tchar c;\ndiff --git a/t/unit-tests/test-lib.c b/t/unit-tests/test-lib.c\nindex 7bf9dfdb95..cb757edbd8 100644\n--- a/t/unit-tests/test-lib.c\n+++ b/t/unit-tests/test-lib.c\n@@ -311,6 +311,18 @@ int check_uint_loc(const char *loc, const char *check, int ok,\n \treturn ret;\n }\n \n+int check_ptr_loc(const char *loc, const char *check, int ok, void *a, void *b)\n+{\n+\tint ret = test_assert(loc, check, ok);\n+\n+\tif (!ret) {\n+\t\ttest_msg(\" left: %p\", a);\n+\t\ttest_msg(\" right: %p\", b);\n+\t}\n+\n+\treturn ret;\n+}\n+\n static void print_one_char(char ch, char quote)\n {\n \tif ((unsigned char)ch < 0x20u || ch == 0x7f) {\n"},{"id":"486124","messageId":"c5d35735-10e2-4b71-8fc7-6218e7002549@web.de","threadId":"60648","inReplyTo":"9aad15c8-8d3b-475b-bd44-5d24121cb793@gmail.com","subject":"Re: [PATCH] mem-pool: fix big allocations","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2023-12-28T16:05:48Z","receivedAt":"2023-12-28T16:05:54Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 28.12.23 um 16:10 schrieb Phillip Wood:\n> Hi René\n>\n> On 21/12/2023 23:13, René Scharfe wrote:\n>> +#define check_ptr(a, op, b) check_int(((a) op (b)), ==, 1)\n>> [...]\n>> +static void t_calloc_100(struct mem_pool *pool)\n>> +{\n>> +    size_t size = 100;\n>> +    char *buffer = mem_pool_calloc(pool, 1, size);\n>> +    for (size_t i = 0; i < size; i++)\n>> +        check_int(buffer[i], ==, 0);\n>> +    if (!check_ptr(pool->mp_block, !=, NULL))\n>> +        return;\n>> +    check_ptr(pool->mp_block->next_free, <=, pool->mp_block->end);\n>> +    check_ptr(pool->mp_block->next_free, !=, NULL);\n>> +    check_ptr(pool->mp_block->end, !=, NULL);\n>> +}\n>\n> It's great to see the unit test framework being used here. I wonder\n> though if it would be simpler just to use\n>\n>     check(ptr != NULL)\n\nYes, that's better.\n\n> as I'm not sure what the check_ptr() macro adds. The diff at the end of\n> this email shows a possible implementation of a check_ptr() macro for\n> the unit test library. I'm wary of adding it though because I'm not sure\n> printing the pointer values is actually very useful most of the\n> time. I'm also concerned that the rules around pointer arithmetic and\n> comparisons mean that many pointer tests such as\n>\n>     check_ptr(pool->mp_block->next_free, <=, pool->mp_block->end);\n>\n> will be undefined if they fail.\n\nTrue, the compiler could legally emit mush when it finds out that the\npointers are for different objects. And the error being fixed produces\nsuch unrelated pointer pairs -- oops.\n\nThis check is not important here, we can just drop it.\n\nmem_pool_contains() has the same problem, by the way.\n\nRestricting ourselves to only equality comparisons for pointers prevents\nsome interesting sanity checks, though. Casting to intptr_t or\nuintptr_t would allow arbitrary comparisons without risk of undefined\nbehavior, though. Perhaps that would make a check_ptr() macro viable\nand useful.\n\nRené\n"},{"id":"486125","messageId":"e1e43a6c-3e06-4453-88a3-f00476132bcd@gmail.com","threadId":"60648","inReplyTo":"c5d35735-10e2-4b71-8fc7-6218e7002549@web.de","subject":"Re: [PATCH] mem-pool: fix big allocations","fromName":"","fromEmail":"phillip.wood123@gmail.com","sentAt":"2023-12-28T16:48:11Z","receivedAt":"2023-12-28T16:48:13Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"On 28/12/2023 16:05, René Scharfe wrote:\n> Am 28.12.23 um 16:10 schrieb Phillip Wood:\n>> The diff at the end of\n>> this email shows a possible implementation of a check_ptr() macro for\n>> the unit test library. I'm wary of adding it though because I'm not sure\n>> printing the pointer values is actually very useful most of the\n>> time. I'm also concerned that the rules around pointer arithmetic and\n>> comparisons mean that many pointer tests such as\n>>\n>>     check_ptr(pool->mp_block->next_free, <=, pool->mp_block->end);\n>>\n>> will be undefined if they fail.\n> \n> True, the compiler could legally emit mush when it finds out that the\n> pointers are for different objects. And the error being fixed produces\n> such unrelated pointer pairs -- oops.\n> \n> This check is not important here, we can just drop it.\n> \n> mem_pool_contains() has the same problem, by the way.\n> \n> Restricting ourselves to only equality comparisons for pointers prevents\n> some interesting sanity checks, though. Casting to intptr_t or\n> uintptr_t would allow arbitrary comparisons without risk of undefined\n> behavior, though. Perhaps that would make a check_ptr() macro viable\n> and useful.\n\nThat certainly helps and the check_ptr() macro in my previous email \ncasts the pointers to uintptr_t before comparing them. Maybe I'm \nworrying too much, but my concern is that in a failing comparison it is \nlikely one of the pointers is invalid (for example it is the result of \nsome undefined pointer arithmetic) and the program is undefined from the \npoint the invalid pointer is created. The documentation for check_ptr() \nin my previous mail contains the following example\n\n For example if `start` and `end` are pointers to the beginning and\n end of an allocation and `offset` is an integer then\n\n check_ptr(start + offset, <=, end)\n\n is undefined when `offset` is larger than `end - start`. Rewriting\n the comparison as\n\n check_uint(offset, <=, end - start)\n\n avoids undefined behavior when offset is too large, but is still\n undefined if there is a bug that means `start` and `end` do not\n point to the same allocation.\n\nI agree it would be nice to allow arbitrary pointer comparisons but it \nwould be good to do it in a way that does not expose us to undefined \nbehavior. I'm not sure what the right balance is here.\n\nBest Wishes\n\nPhillip\n"},{"id":"486134","messageId":"34f5913f-b187-43c3-99b7-3d57065dba12@web.de","threadId":"60648","inReplyTo":"e1e43a6c-3e06-4453-88a3-f00476132bcd@gmail.com","subject":"Re: [PATCH] mem-pool: fix big allocations","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2023-12-28T18:56:01Z","receivedAt":"2023-12-28T18:56:11Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 28.12.23 um 17:48 schrieb phillip.wood123@gmail.com:\n> On 28/12/2023 16:05, René Scharfe wrote:\n>> Am 28.12.23 um 16:10 schrieb Phillip Wood:\n>>> The diff at the end of\n>>> this email shows a possible implementation of a check_ptr() macro for\n>>> the unit test library. I'm wary of adding it though because I'm not sure\n>>> printing the pointer values is actually very useful most of the\n>>> time. I'm also concerned that the rules around pointer arithmetic and\n>>> comparisons mean that many pointer tests such as\n>>>\n>>>      check_ptr(pool->mp_block->next_free, <=, pool->mp_block->end);\n>>>\n>>> will be undefined if they fail.\n>>\n>> True, the compiler could legally emit mush when it finds out that the\n>> pointers are for different objects.  And the error being fixed produces\n>> such unrelated pointer pairs -- oops.\n>>\n>> This check is not important here, we can just drop it.\n>>\n>> mem_pool_contains() has the same problem, by the way.\n>>\n>> Restricting ourselves to only equality comparisons for pointers prevents\n>> some interesting sanity checks, though.  Casting to intptr_t or\n>> uintptr_t would allow arbitrary comparisons without risk of undefined\n>> behavior, though.  Perhaps that would make a check_ptr() macro viable\n>> and useful.\n>\n> That certainly helps and the check_ptr() macro in my previous email\n> casts the pointers to uintptr_t before comparing them. Maybe I'm\n> worrying too much, but my concern is that in a failing comparison it\n> is likely one of the pointers is invalid (for example it is the\n> result of some undefined pointer arithmetic) and the program is\n> undefined from the point the invalid pointer is created.\n\nThere are no restrictions on integer comparisons. So comparing after\ncasting to uintptr_t should not invoke undefined behavior. If undefined\nbehavior was involved in calculating the pointers in the first place\nthen the compiler might still legally go crazy, but not due to the\ncomparison. Right?\n\nWhether the result of a uintptr_t-cast comparison of pointers to\ndifferent objects is meaningful is a different question. Hopefully\nrange checks are possible.\n\n> The\n> documentation for check_ptr() in my previous mail contains the\n> following example\n>\n>     For example if `start` and `end` are pointers to the beginning and\n>     end of an allocation and `offset` is an integer then\n>\n>         check_ptr(start + offset, <=, end)\n>\n>     is undefined when `offset` is larger than `end - start`. Rewriting\n>     the comparison as\n>\n>         check_uint(offset, <=, end - start)\n>\n>     avoids undefined behavior when offset is too large, but is still\n>     undefined if there is a bug that means `start` and `end` do not\n>     point to the same allocation.\n\nTrue, but in such a unit test we'd need additional checks verifying\nthat start and end belong to the same object. Or perhaps use a\nnumerical size instead of an end pointer.\n\nRené\n"},{"id":"486135","messageId":"1c39c0e7-05b2-4726-a90c-f78df4356a41@web.de","threadId":"60648","inReplyTo":"fa89d269-1a23-4ed6-bebc-30c0b629f444@web.de","subject":"[PATCH v2] mem-pool: fix big allocations","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2023-12-28T19:19:06Z","receivedAt":"2023-12-28T19:19:20Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Memory pool allocations that require a new block and would fill at\nleast half of it are handled specially. Before 158dfeff3d (mem-pool:\nadd life cycle management functions, 2018-07-02) they used to be\nallocated outside of the pool. This patch made mem_pool_alloc() create\na bespoke block instead, to allow releasing it when the pool gets\ndiscarded.\n\nUnfortunately mem_pool_alloc() returns a pointer to the start of such a\nbespoke block, i.e. to the struct mp_block at its top. When the caller\nwrites to it, the management information gets corrupted. This affects\nmem_pool_discard() and -- if there are no other blocks in the pool --\nalso mem_pool_alloc().\n\nReturn the payload pointer of bespoke blocks, just like for smaller\nallocations, to protect the management struct.\n\nAlso update next_free to mark the block as full. This is only strictly\nnecessary for the first allocated block, because subsequent ones are\ninserted after the current block and never considered for further\nallocations, but it's easier to just do it in all cases.\n\nAdd a basic unit test to demonstrate the issue by using\nmem_pool_calloc() with a tiny block size, which forces the creation of a\nbespoke block.\n\nHelped-by: Phillip Wood \nSigned-off-by: René Scharfe \n---\nChanges since v1:\n- simply use check() instead of a custom check_ptr() macro\n- drop unnecessary comparison of next_free and end pointers\n\nInterdiff against v1:\n diff --git a/t/unit-tests/t-mem-pool.c b/t/unit-tests/t-mem-pool.c\n index 2295779b0b..a0d57df761 100644\n --- a/t/unit-tests/t-mem-pool.c\n +++ b/t/unit-tests/t-mem-pool.c\n @@ -1,8 +1,6 @@\n #include \"test-lib.h\"\n #include \"mem-pool.h\"\n\n -#define check_ptr(a, op, b) check_int(((a) op (b)), ==, 1)\n -\n static void setup_static(void (*f)(struct mem_pool *), size_t block_alloc)\n {\n \tstruct mem_pool pool = { .block_alloc = block_alloc };\n @@ -16,11 +14,10 @@ static void t_calloc_100(struct mem_pool *pool)\n \tchar *buffer = mem_pool_calloc(pool, 1, size);\n \tfor (size_t i = 0; i < size; i++)\n \t\tcheck_int(buffer[i], ==, 0);\n -\tif (!check_ptr(pool->mp_block, !=, NULL))\n +\tif (!check(pool->mp_block != NULL))\n \t\treturn;\n -\tcheck_ptr(pool->mp_block->next_free, <=, pool->mp_block->end);\n -\tcheck_ptr(pool->mp_block->next_free, !=, NULL);\n -\tcheck_ptr(pool->mp_block->end, !=, NULL);\n +\tcheck(pool->mp_block->next_free != NULL);\n +\tcheck(pool->mp_block->end != NULL);\n }\n\n int cmd_main(int argc, const char **argv)\n\n Makefile | 1 +\n mem-pool.c | 6 +++---\n t/unit-tests/t-mem-pool.c | 31 +++++++++++++++++++++++++++++++\n 3 files changed, 35 insertions(+), 3 deletions(-)\n create mode 100644 t/unit-tests/t-mem-pool.c\n\ndiff --git a/Makefile b/Makefile\nindex 88ba7a3c51..15990ff312 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1340,6 +1340,7 @@ THIRD_PARTY_SOURCES += sha1collisiondetection/%\n THIRD_PARTY_SOURCES += sha1dc/%\n\n UNIT_TEST_PROGRAMS += t-basic\n+UNIT_TEST_PROGRAMS += t-mem-pool\n UNIT_TEST_PROGRAMS += t-strbuf\n UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))\n UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))\ndiff --git a/mem-pool.c b/mem-pool.c\nindex c34846d176..e8d976c3ee 100644\n--- a/mem-pool.c\n+++ b/mem-pool.c\n@@ -99,9 +99,9 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len)\n\n \tif (!p) {\n \t\tif (len >= (pool->block_alloc / 2))\n-\t\t\treturn mem_pool_alloc_block(pool, len, pool->mp_block);\n-\n-\t\tp = mem_pool_alloc_block(pool, pool->block_alloc, NULL);\n+\t\t\tp = mem_pool_alloc_block(pool, len, pool->mp_block);\n+\t\telse\n+\t\t\tp = mem_pool_alloc_block(pool, pool->block_alloc, NULL);\n \t}\n\n \tr = p->next_free;\ndiff --git a/t/unit-tests/t-mem-pool.c b/t/unit-tests/t-mem-pool.c\nnew file mode 100644\nindex 0000000000..a0d57df761\n--- /dev/null\n+++ b/t/unit-tests/t-mem-pool.c\n@@ -0,0 +1,31 @@\n+#include \"test-lib.h\"\n+#include \"mem-pool.h\"\n+\n+static void setup_static(void (*f)(struct mem_pool *), size_t block_alloc)\n+{\n+\tstruct mem_pool pool = { .block_alloc = block_alloc };\n+\tf(&pool);\n+\tmem_pool_discard(&pool, 0);\n+}\n+\n+static void t_calloc_100(struct mem_pool *pool)\n+{\n+\tsize_t size = 100;\n+\tchar *buffer = mem_pool_calloc(pool, 1, size);\n+\tfor (size_t i = 0; i < size; i++)\n+\t\tcheck_int(buffer[i], ==, 0);\n+\tif (!check(pool->mp_block != NULL))\n+\t\treturn;\n+\tcheck(pool->mp_block->next_free != NULL);\n+\tcheck(pool->mp_block->end != NULL);\n+}\n+\n+int cmd_main(int argc, const char **argv)\n+{\n+\tTEST(setup_static(t_calloc_100, 1024 * 1024),\n+\t \"mem_pool_calloc returns 100 zeroed bytes with big block\");\n+\tTEST(setup_static(t_calloc_100, 1),\n+\t \"mem_pool_calloc returns 100 zeroed bytes with tiny block\");\n+\n+\treturn test_done();\n+}\n--\n2.43.0\n"},{"id":"486137","messageId":"48821d3f-2e30-4bce-b9e8-e4199c24e251@gmail.com","threadId":"60648","inReplyTo":"34f5913f-b187-43c3-99b7-3d57065dba12@web.de","subject":"Re: [PATCH] mem-pool: fix big allocations","fromName":"","fromEmail":"phillip.wood123@gmail.com","sentAt":"2023-12-28T19:34:08Z","receivedAt":"2023-12-28T19:34:10Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"On 28/12/2023 18:56, René Scharfe wrote:\n> Am 28.12.23 um 17:48 schrieb phillip.wood123@gmail.com:\n>> On 28/12/2023 16:05, René Scharfe wrote:\n>>> Am 28.12.23 um 16:10 schrieb Phillip Wood:\n>>>> The diff at the end of\n>>>> this email shows a possible implementation of a check_ptr() macro for\n>>>> the unit test library. I'm wary of adding it though because I'm not sure\n>>>> printing the pointer values is actually very useful most of the\n>>>> time. I'm also concerned that the rules around pointer arithmetic and\n>>>> comparisons mean that many pointer tests such as\n>>>>\n>>>>      check_ptr(pool->mp_block->next_free, <=, pool->mp_block->end);\n>>>>\n>>>> will be undefined if they fail.\n>>>\n>>> True, the compiler could legally emit mush when it finds out that the\n>>> pointers are for different objects.  And the error being fixed produces\n>>> such unrelated pointer pairs -- oops.\n>>>\n>>> This check is not important here, we can just drop it.\n>>>\n>>> mem_pool_contains() has the same problem, by the way.\n>>>\n>>> Restricting ourselves to only equality comparisons for pointers prevents\n>>> some interesting sanity checks, though.  Casting to intptr_t or\n>>> uintptr_t would allow arbitrary comparisons without risk of undefined\n>>> behavior, though.  Perhaps that would make a check_ptr() macro viable\n>>> and useful.\n>>\n>> That certainly helps and the check_ptr() macro in my previous email\n>> casts the pointers to uintptr_t before comparing them. Maybe I'm\n>> worrying too much, but my concern is that in a failing comparison it\n>> is likely one of the pointers is invalid (for example it is the\n>> result of some undefined pointer arithmetic) and the program is\n>> undefined from the point the invalid pointer is created.\n> \n> There are no restrictions on integer comparisons. So comparing after\n> casting to uintptr_t should not invoke undefined behavior. If undefined\n> behavior was involved in calculating the pointers in the first place\n> then the compiler might still legally go crazy, but not due to the\n> comparison. Right?\n\nExactly, my worry is that if the comparison fails it is likely that \nthere will have been undefined behavior involved in calculating the \npointer before we get to the comparison in which case so casting to \nuintptr_t in the comparison does not help.\n\n> Whether the result of a uintptr_t-cast comparison of pointers to\n> different objects is meaningful is a different question. Hopefully\n> range checks are possible.\n> \n>> The\n>> documentation for check_ptr() in my previous mail contains the\n>> following example\n>>\n>>     For example if `start` and `end` are pointers to the beginning and\n>>     end of an allocation and `offset` is an integer then\n>>\n>>         check_ptr(start + offset, <=, end)\n>>\n>>     is undefined when `offset` is larger than `end - start`. Rewriting\n>>     the comparison as\n>>\n>>         check_uint(offset, <=, end - start)\n>>\n>>     avoids undefined behavior when offset is too large, but is still\n>>     undefined if there is a bug that means `start` and `end` do not\n>>     point to the same allocation.\n> \n> True, but in such a unit test we'd need additional checks verifying\n> that start and end belong to the same object. Or perhaps use a\n> numerical size instead of an end pointer.\n\nAgreed, but I think the implication is that there will be cases we \nshould be using check_uint() as in the second comparison above rather \nthan check_ptr() as in the first comparison above. I'm not opposed to \nadding check_ptr() if we think it will be useful but I am worried it is \neasy to misuse it. If we do add check_ptr() we should have some \nguidelines about when it makes sense to use it.\n\nBest Wishes\n\nPhillip\n"},{"id":"486138","messageId":"9bafdbfe-f451-43b1-806d-be3d70e21892@gmail.com","threadId":"60648","inReplyTo":"1c39c0e7-05b2-4726-a90c-f78df4356a41@web.de","subject":"Re: [PATCH v2] mem-pool: fix big allocations","fromName":"","fromEmail":"phillip.wood123@gmail.com","sentAt":"2023-12-28T19:36:31Z","receivedAt":"2023-12-28T19:36:33Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi René\n\nOn 28/12/2023 19:19, René Scharfe wrote:\n> Interdiff against v1:\n> diff --git a/t/unit-tests/t-mem-pool.c b/t/unit-tests/t-mem-pool.c\n> index 2295779b0b..a0d57df761 100644\n> --- a/t/unit-tests/t-mem-pool.c\n> +++ b/t/unit-tests/t-mem-pool.c\n> @@ -1,8 +1,6 @@\n> #include \"test-lib.h\"\n> #include \"mem-pool.h\"\n> \n> -#define check_ptr(a, op, b) check_int(((a) op (b)), ==, 1)\n> -\n> static void setup_static(void (*f)(struct mem_pool *), size_t block_alloc)\n> {\n> \tstruct mem_pool pool = { .block_alloc = block_alloc };\n> @@ -16,11 +14,10 @@ static void t_calloc_100(struct mem_pool *pool)\n> \tchar *buffer = mem_pool_calloc(pool, 1, size);\n> \tfor (size_t i = 0; i < size; i++)\n> \t\tcheck_int(buffer[i], ==, 0);\n> -\tif (!check_ptr(pool->mp_block, !=, NULL))\n> +\tif (!check(pool->mp_block != NULL))\n> \t\treturn;\n> -\tcheck_ptr(pool->mp_block->next_free, <=, pool->mp_block->end);\n> -\tcheck_ptr(pool->mp_block->next_free, !=, NULL);\n> -\tcheck_ptr(pool->mp_block->end, !=, NULL);\n> +\tcheck(pool->mp_block->next_free != NULL);\n> +\tcheck(pool->mp_block->end != NULL);\n> }\n\nThe changes to the unit tests look good to me (I haven't really looked \nat the actual bug fix in the mem_pool code).\n\nBest Wishes\n\nPhillip\n"},{"id":"486146","messageId":"0dd59d8e-0175-43ef-893d-3352a3f5f1c4@web.de","threadId":"60648","inReplyTo":"48821d3f-2e30-4bce-b9e8-e4199c24e251@gmail.com","subject":"Re: [PATCH] mem-pool: fix big allocations","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2023-12-29T06:53:13Z","receivedAt":"2023-12-29T06:53:20Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 28.12.23 um 20:34 schrieb phillip.wood123@gmail.com:\n>\n> Exactly, my worry is that if the comparison fails it is likely that\n> there will have been undefined behavior involved in calculating the\n> pointer before we get to the comparison in which case so casting to\n> uintptr_t in the comparison does not help.\nIf there's undefined behavior (UB) somewhere in the test or the tested\nunit then the compiler could skip any checks and report success anyway.\nNot adding UB in the test framework and tests is the least we can do.\n\nPerhaps disabling link-time optimization would allow us to shield the\nunit tests from UB in the tested code, in the sense that the compiler\nwould then not be able to skip checks.\n\nRené\n"},{"id":"486224","messageId":"ZZSOOg8pMb6iKzHz@nand.local","threadId":"60648","inReplyTo":"1c39c0e7-05b2-4726-a90c-f78df4356a41@web.de","subject":"Re: [PATCH v2] mem-pool: fix big allocations","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-02T22:29:14Z","receivedAt":"2024-01-02T22:29:16Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi René,\n\nOn Thu, Dec 28, 2023 at 08:19:06PM +0100, René Scharfe wrote:\n> Changes since v1:\n> - simply use check() instead of a custom check_ptr() macro\n> - drop unnecessary comparison of next_free and end pointers\n\nGreat find and fix. It's nice to see some examples of the testing\nframework being used. I'll have to play around with it sometime :-).\n\nThanks,\nTaylor\n"}]}