{"thread":{"id":"57187","subject":"[PATCH] Properly align memory allocations and temporary buffers","startedAt":"2022-01-05T13:23:32Z","lastAt":"2022-01-24T17:12:05Z","messageCount":32,"participants":["Jessica Clarke","Taylor Blau","Junio C Hamano","brian m. carlson","Philip Oakley","René Scharfe","Elijah Newren"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"445520","messageId":"20220105132324.6651-1-jrtc27@jrtc27.com","threadId":"57187","inReplyTo":null,"subject":"[PATCH] Properly align memory allocations and temporary buffers","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-05T13:23:24Z","receivedAt":"2022-01-05T13:23:32Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"Currently git_qsort_s allocates a buffer on the stack that has no\nalignment, and mem_pool_alloc assumes uintmax_t's size is adequate\nalignment for any type.\n\nOn CHERI, and thus Arm's Morello prototype, pointers are implemented as\nhardware capabilities which, as well as having a normal integer address,\nhave additional bounds, permissions and other metadata in a second word,\nso on a 64-bit architecture they are 128-bit quantities, including their\nalignment requirements. Despite being 128-bit, their integer component\nis still only a 64-bit field, so uintmax_t remains 64-bit, and therefore\nuintmax_t does not sufficiently align an allocation.\n\nMoreover, these capabilities have an additional \"129th\" tag bit, which\ntracks the validity of the capability and is cleared on any invalid\noperation that doesn't trap (e.g. partially overwriting a capability\nwill invalidate it) which, combined with the architecture's strict\nchecks on capability manipulation instructions, ensures it is\narchitecturally impossible to construct a capability that gives more\nrights than those you were given in the first place. To store these tag\nbits, each capability sized and aligned word in memory gains a single\ntag bit that is stored in unaddressable (to the processor) memory. This\nmeans that it is impossible to store a capability at an unaligned\naddress: a normal load or store of a capability will always take an\nalignment fault even if the (micro)architecture supports unaligned\nloads/stores for other data types, and a memcpy will, if the destination\nis not appropriately aligned, copy the byte representation but lose the\ntag, meaning that if it is eventually copied back and loaded from an\naligned location any attempt to dereference it will trap with a tag\nfault. Thus, even char buffers that are memcpy'ed to or from must be\nproperly aligned on CHERI architectures if they are to hold pointers.\n\nAddress both of these by introducing a new git_max_align type put in a\nunion with the on-stack buffer to force its alignment, as well as a new\nGIT_MAX_ALIGNMENT macro whose value is the alignment of git_max_align\nthat gets used for mem_pool_alloc. As well as making the code work on\nCHERI, the former change likely also improves performance on some\narchitectures by making memcpy faster (either because it can use larger\nblock sizes or because the microarchitecture has inefficient unaligned\naccesses).\n\nSigned-off-by: Jessica Clarke <jrtc27@jrtc27.com>\n---\n compat/qsort_s.c  | 11 +++++++----\n git-compat-util.h | 11 +++++++++++\n mem-pool.c        |  6 +++---\n 3 files changed, 21 insertions(+), 7 deletions(-)\n\ndiff --git a/compat/qsort_s.c b/compat/qsort_s.c\nindex 52d1f0a73d..1ccdb87451 100644\n--- a/compat/qsort_s.c\n+++ b/compat/qsort_s.c\n@@ -49,16 +49,19 @@ int git_qsort_s(void *b, size_t n, size_t s,\n \t\tint (*cmp)(const void *, const void *, void *), void *ctx)\n {\n \tconst size_t size = st_mult(n, s);\n-\tchar buf[1024];\n+\tunion {\n+\t\tchar buf[1024];\n+\t\tgit_max_align align;\n+\t} u;\n \n \tif (!n)\n \t\treturn 0;\n \tif (!b || !cmp)\n \t\treturn -1;\n \n-\tif (size < sizeof(buf)) {\n-\t\t/* The temporary array fits on the small on-stack buffer. */\n-\t\tmsort_with_tmp(b, n, s, cmp, buf, ctx);\n+\tif (size < sizeof(u.buf)) {\n+\t\t/* The temporary array fits in the small on-stack buffer. */\n+\t\tmsort_with_tmp(b, n, s, cmp, u.buf, ctx);\n \t} else {\n \t\t/* It's somewhat large, so malloc it.  */\n \t\tchar *tmp = xmalloc(size);\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 5fa54a7afe..28581a45c5 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -274,6 +274,17 @@ typedef unsigned long uintptr_t;\n #define _ALL_SOURCE 1\n #endif\n \n+typedef union {\n+\tuintmax_t max_align_uintmax;\n+\tvoid *max_align_pointer;\n+} git_max_align;\n+\n+typedef struct {\n+\tchar unalign;\n+\tgit_max_align aligned;\n+} git_max_alignment;\n+#define GIT_MAX_ALIGNMENT offsetof(git_max_alignment, aligned)\n+\n /* used on Mac OS X */\n #ifdef PRECOMPOSE_UNICODE\n #include \"compat/precompose_utf8.h\"\ndiff --git a/mem-pool.c b/mem-pool.c\nindex ccdcad2e3d..748eff925a 100644\n--- a/mem-pool.c\n+++ b/mem-pool.c\n@@ -69,9 +69,9 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len)\n \tstruct mp_block *p = NULL;\n \tvoid *r;\n \n-\t/* round up to a 'uintmax_t' alignment */\n-\tif (len & (sizeof(uintmax_t) - 1))\n-\t\tlen += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));\n+\t/* round up to a 'GIT_MAX_ALIGNMENT' alignment */\n+\tif (len & (GIT_MAX_ALIGNMENT - 1))\n+\t\tlen += GIT_MAX_ALIGNMENT - (len & (GIT_MAX_ALIGNMENT - 1));\n \n \tif (pool->mp_block &&\n \t    pool->mp_block->end - pool->mp_block->next_free >= len)\n-- \n2.33.1\n\n"},{"id":"445659","messageId":"YddjJ+uIQM34Gedo@nand.local","threadId":"57187","inReplyTo":"20220105132324.6651-1-jrtc27@jrtc27.com","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2022-01-06T21:46:15Z","receivedAt":"2022-01-06T21:46:24Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"(+cc René as another possible reviewer)\n\nOn Wed, Jan 05, 2022 at 01:23:24PM +0000, Jessica Clarke wrote:\n> Currently git_qsort_s allocates a buffer on the stack that has no\n> alignment, and mem_pool_alloc assumes uintmax_t's size is adequate\n> alignment for any type.\n>\n> On CHERI, and thus Arm's Morello prototype, pointers are implemented as\n> hardware capabilities which, as well as having a normal integer address,\n> have additional bounds, permissions and other metadata in a second word,\n> so on a 64-bit architecture they are 128-bit quantities, including their\n> alignment requirements. Despite being 128-bit, their integer component\n> is still only a 64-bit field, so uintmax_t remains 64-bit, and therefore\n> uintmax_t does not sufficiently align an allocation.\n>\n> Moreover, these capabilities have an additional \"129th\" tag bit, which\n> tracks the validity of the capability and is cleared on any invalid\n> operation that doesn't trap (e.g. partially overwriting a capability\n> will invalidate it) which, combined with the architecture's strict\n> checks on capability manipulation instructions, ensures it is\n> architecturally impossible to construct a capability that gives more\n> rights than those you were given in the first place. To store these tag\n> bits, each capability sized and aligned word in memory gains a single\n> tag bit that is stored in unaddressable (to the processor) memory. This\n> means that it is impossible to store a capability at an unaligned\n> address: a normal load or store of a capability will always take an\n> alignment fault even if the (micro)architecture supports unaligned\n> loads/stores for other data types, and a memcpy will, if the destination\n> is not appropriately aligned, copy the byte representation but lose the\n> tag, meaning that if it is eventually copied back and loaded from an\n> aligned location any attempt to dereference it will trap with a tag\n> fault. Thus, even char buffers that are memcpy'ed to or from must be\n> properly aligned on CHERI architectures if they are to hold pointers.\n>\n> Address both of these by introducing a new git_max_align type put in a\n> union with the on-stack buffer to force its alignment, as well as a new\n> GIT_MAX_ALIGNMENT macro whose value is the alignment of git_max_align\n> that gets used for mem_pool_alloc. As well as making the code work on\n> CHERI, the former change likely also improves performance on some\n> architectures by making memcpy faster (either because it can use larger\n> block sizes or because the microarchitecture has inefficient unaligned\n> accesses).\n>\n> Signed-off-by: Jessica Clarke <jrtc27@jrtc27.com>\n> ---\n>  compat/qsort_s.c  | 11 +++++++----\n>  git-compat-util.h | 11 +++++++++++\n>  mem-pool.c        |  6 +++---\n>  3 files changed, 21 insertions(+), 7 deletions(-)\n>\n> diff --git a/compat/qsort_s.c b/compat/qsort_s.c\n> index 52d1f0a73d..1ccdb87451 100644\n> --- a/compat/qsort_s.c\n> +++ b/compat/qsort_s.c\n> @@ -49,16 +49,19 @@ int git_qsort_s(void *b, size_t n, size_t s,\n>  \t\tint (*cmp)(const void *, const void *, void *), void *ctx)\n>  {\n>  \tconst size_t size = st_mult(n, s);\n> -\tchar buf[1024];\n> +\tunion {\n> +\t\tchar buf[1024];\n> +\t\tgit_max_align align;\n> +\t} u;\n\nI'm not sure I understand. Clearly this union aligns buf along the width\nof git_max_align. But what about the preimage makes buf unaligned?\n\n> diff --git a/git-compat-util.h b/git-compat-util.h\n> index 5fa54a7afe..28581a45c5 100644\n> --- a/git-compat-util.h\n> +++ b/git-compat-util.h\n> @@ -274,6 +274,17 @@ typedef unsigned long uintptr_t;\n>  #define _ALL_SOURCE 1\n>  #endif\n>\n> +typedef union {\n> +\tuintmax_t max_align_uintmax;\n> +\tvoid *max_align_pointer;\n> +} git_max_align;\n\nOK, the purpose of this union is to be as wide as the least common\nalignment between uintmax_t and void *, yes?\n\n> +\n> +typedef struct {\n> +\tchar unalign;\n> +\tgit_max_align aligned;\n> +} git_max_alignment;\n> +#define GIT_MAX_ALIGNMENT offsetof(git_max_alignment, aligned)\n\n...then the offset of the aligned field within the git_max_alignment\nstruct is going to be that common alignment? Could you not `#define\nGIT_MAX_ALIGNMENT` to be `sizeof(git_max_align)` directly, or is there\nsomething I'm missing?\n\nI suppose the way you wrote it here is done in order to prevent padding\non the end of the git_max_align union from artificially increasing the\nvalue of GIT_MAX_ALIGNMENT.\n\nIn any case, I *think* what you wrote here is right. The typedef's are\nuncommon to our codebase, though. I wonder how much of this is all\nnecessary.\n\nThanks,\nTaylor\n"},{"id":"445660","messageId":"9F022B78-5EC7-41D8-8AA6-99470019BB95@jrtc27.com","threadId":"57187","inReplyTo":"YddjJ+uIQM34Gedo@nand.local","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-06T21:56:18Z","receivedAt":"2022-01-06T21:56:24Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"On 6 Jan 2022, at 21:46, Taylor Blau <me@ttaylorr.com> wrote:\n> \n> (+cc René as another possible reviewer)\n> \n> On Wed, Jan 05, 2022 at 01:23:24PM +0000, Jessica Clarke wrote:\n>> Currently git_qsort_s allocates a buffer on the stack that has no\n>> alignment, and mem_pool_alloc assumes uintmax_t's size is adequate\n>> alignment for any type.\n>> \n>> On CHERI, and thus Arm's Morello prototype, pointers are implemented as\n>> hardware capabilities which, as well as having a normal integer address,\n>> have additional bounds, permissions and other metadata in a second word,\n>> so on a 64-bit architecture they are 128-bit quantities, including their\n>> alignment requirements. Despite being 128-bit, their integer component\n>> is still only a 64-bit field, so uintmax_t remains 64-bit, and therefore\n>> uintmax_t does not sufficiently align an allocation.\n>> \n>> Moreover, these capabilities have an additional \"129th\" tag bit, which\n>> tracks the validity of the capability and is cleared on any invalid\n>> operation that doesn't trap (e.g. partially overwriting a capability\n>> will invalidate it) which, combined with the architecture's strict\n>> checks on capability manipulation instructions, ensures it is\n>> architecturally impossible to construct a capability that gives more\n>> rights than those you were given in the first place. To store these tag\n>> bits, each capability sized and aligned word in memory gains a single\n>> tag bit that is stored in unaddressable (to the processor) memory. This\n>> means that it is impossible to store a capability at an unaligned\n>> address: a normal load or store of a capability will always take an\n>> alignment fault even if the (micro)architecture supports unaligned\n>> loads/stores for other data types, and a memcpy will, if the destination\n>> is not appropriately aligned, copy the byte representation but lose the\n>> tag, meaning that if it is eventually copied back and loaded from an\n>> aligned location any attempt to dereference it will trap with a tag\n>> fault. Thus, even char buffers that are memcpy'ed to or from must be\n>> properly aligned on CHERI architectures if they are to hold pointers.\n>> \n>> Address both of these by introducing a new git_max_align type put in a\n>> union with the on-stack buffer to force its alignment, as well as a new\n>> GIT_MAX_ALIGNMENT macro whose value is the alignment of git_max_align\n>> that gets used for mem_pool_alloc. As well as making the code work on\n>> CHERI, the former change likely also improves performance on some\n>> architectures by making memcpy faster (either because it can use larger\n>> block sizes or because the microarchitecture has inefficient unaligned\n>> accesses).\n>> \n>> Signed-off-by: Jessica Clarke <jrtc27@jrtc27.com>\n>> ---\n>> compat/qsort_s.c  | 11 +++++++----\n>> git-compat-util.h | 11 +++++++++++\n>> mem-pool.c        |  6 +++---\n>> 3 files changed, 21 insertions(+), 7 deletions(-)\n>> \n>> diff --git a/compat/qsort_s.c b/compat/qsort_s.c\n>> index 52d1f0a73d..1ccdb87451 100644\n>> --- a/compat/qsort_s.c\n>> +++ b/compat/qsort_s.c\n>> @@ -49,16 +49,19 @@ int git_qsort_s(void *b, size_t n, size_t s,\n>> \t\tint (*cmp)(const void *, const void *, void *), void *ctx)\n>> {\n>> \tconst size_t size = st_mult(n, s);\n>> -\tchar buf[1024];\n>> +\tunion {\n>> +\t\tchar buf[1024];\n>> +\t\tgit_max_align align;\n>> +\t} u;\n> \n> I'm not sure I understand. Clearly this union aligns buf along the width\n> of git_max_align. But what about the preimage makes buf unaligned?\n\nIt’s a char array, so it can have any alignment. Its address could be\n0x10007. And it doesn’t align to the width of git_max_align, it aligns\nto the alignment of git_max_align. Those don’t need to be the same, the\nalignment just needs to be a factor of the size.\n\n(Technically if git_max_align has a size > 1024 then it’d also make the\nunion bigger, but that’s clearly absurd for any real C implementation)\n\n>> diff --git a/git-compat-util.h b/git-compat-util.h\n>> index 5fa54a7afe..28581a45c5 100644\n>> --- a/git-compat-util.h\n>> +++ b/git-compat-util.h\n>> @@ -274,6 +274,17 @@ typedef unsigned long uintptr_t;\n>> #define _ALL_SOURCE 1\n>> #endif\n>> \n>> +typedef union {\n>> +\tuintmax_t max_align_uintmax;\n>> +\tvoid *max_align_pointer;\n>> +} git_max_align;\n> \n> OK, the purpose of this union is to be as wide as the least common\n> alignment between uintmax_t and void *, yes?\n\nNo, the purpose is for the union’s *alignment* to be the least common\nalignment between uintmax_t and void *. The size doesn’t matter for\nanything.\n\n>> +\n>> +typedef struct {\n>> +\tchar unalign;\n>> +\tgit_max_align aligned;\n>> +} git_max_alignment;\n>> +#define GIT_MAX_ALIGNMENT offsetof(git_max_alignment, aligned)\n> \n> ...then the offset of the aligned field within the git_max_alignment\n> struct is going to be that common alignment? Could you not `#define\n> GIT_MAX_ALIGNMENT` to be `sizeof(git_max_align)` directly, or is there\n> something I'm missing?\n\nYou could, but that would over-align in cases where the alignment of\ngit_max_align is smaller than its size. For example, uint32_t and\nuint64_t only require 2-byte alignment on m68k. Using offsetof ensures\nwe actually query the thing we care about, the alignment, and not the\nsize, which is guaranteed to be a multiple of the alignment, but not\nnecessarily equal to it.\n\n> I suppose the way you wrote it here is done in order to prevent padding\n> on the end of the git_max_align union from artificially increasing the\n> value of GIT_MAX_ALIGNMENT.\n\nSo long as all those types have a size that is a power of two there\nshouldn’t actually be any padding in the union, though it might be\nlegal for a hostile compiler to introduce it anyway for fun.\n\n> In any case, I *think* what you wrote here is right. The typedef's are\n> uncommon to our codebase, though. I wonder how much of this is all\n> necessary.\n\nIf you’re willing to risk overaligning and wasting space then you can\njust use sizeof the union. If you want it to be precise then I don’t\nthink you can cut any of it out (otherwise I would have done...).\n\nJess\n\n"},{"id":"445663","messageId":"xmqqh7agbiuq.fsf@gitster.g","threadId":"57187","inReplyTo":"YddjJ+uIQM34Gedo@nand.local","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-06T22:27:25Z","receivedAt":"2022-01-06T22:27:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau <me@ttaylorr.com> writes:\n\n> (+cc René as another possible reviewer)\n>\n> On Wed, Jan 05, 2022 at 01:23:24PM +0000, Jessica Clarke wrote:\n>> Currently git_qsort_s allocates a buffer on the stack that has no\n>> alignment, and mem_pool_alloc assumes uintmax_t's size is adequate\n>> alignment for any type.\n>>\n>> On CHERI, and thus Arm's Morello prototype, pointers are implemented as\n>> hardware capabilities which, as well as having a normal integer address,\n>> have additional bounds, permissions and other metadata in a second word,\n>> so on a 64-bit architecture they are 128-bit quantities, including their\n>> alignment requirements. Despite being 128-bit, their integer component\n>> is still only a 64-bit field, so uintmax_t remains 64-bit, and therefore\n>> uintmax_t does not sufficiently align an allocation.\n\nAlignment aside, if uintmax_t is 64-bit but your pointer needs\n128-bit to store, saving a pointer value in uintmax_t variable would\nnot work correctly, I presume, as casting the 64-bit integral type\nback into pointer would not be sufficient to recover the lost\ninformation that used to be in the second word.\n\nSo, does the architecture have 128-bit uintptr_t and that is a safe\ntype both from the point of view of alignment and from the point of\nview of not losing information?  \n\nIf that type is larger than uintmax_t, something smells wrong,\nthough.  max is not max anymore at that point.\n\nIIRC, uintptr_t is optional in C99, so a simpler solution to use the\nlarger type between uintptr_t and uintmax_t as a replacement for how\nwe use uintmax_t would not quite work out of the box X-<.\n"},{"id":"445675","messageId":"97D2AB55-0F8F-4C38-A5C6-1AAA43EA064A@jrtc27.com","threadId":"57187","inReplyTo":"xmqqh7agbiuq.fsf@gitster.g","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-06T22:56:42Z","receivedAt":"2022-01-06T22:56:46Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"On 6 Jan 2022, at 22:27, Junio C Hamano <gitster@pobox.com> wrote:\n> \n> Taylor Blau <me@ttaylorr.com> writes:\n> \n>> (+cc René as another possible reviewer)\n>> \n>> On Wed, Jan 05, 2022 at 01:23:24PM +0000, Jessica Clarke wrote:\n>>> Currently git_qsort_s allocates a buffer on the stack that has no\n>>> alignment, and mem_pool_alloc assumes uintmax_t's size is adequate\n>>> alignment for any type.\n>>> \n>>> On CHERI, and thus Arm's Morello prototype, pointers are implemented as\n>>> hardware capabilities which, as well as having a normal integer address,\n>>> have additional bounds, permissions and other metadata in a second word,\n>>> so on a 64-bit architecture they are 128-bit quantities, including their\n>>> alignment requirements. Despite being 128-bit, their integer component\n>>> is still only a 64-bit field, so uintmax_t remains 64-bit, and therefore\n>>> uintmax_t does not sufficiently align an allocation.\n> \n> Alignment aside, if uintmax_t is 64-bit but your pointer needs\n> 128-bit to store, saving a pointer value in uintmax_t variable would\n> not work correctly, I presume, as casting the 64-bit integral type\n> back into pointer would not be sufficient to recover the lost\n> information that used to be in the second word.\n> \n> So, does the architecture have 128-bit uintptr_t and that is a safe\n> type both from the point of view of alignment and from the point of\n> view of not losing information?  \n\nYes. It is basically just a char * that lets you perform arbitrary\narithmetic; not an unsigned long any more for our architectures.\n\n> If that type is larger than uintmax_t, something smells wrong,\n> though.  max is not max anymore at that point.\n> \n> IIRC, uintptr_t is optional in C99, so a simpler solution to use the\n> larger type between uintptr_t and uintmax_t as a replacement for how\n> we use uintmax_t would not quite work out of the box X-<.\n\nThis is also true of uint128_t, it doesn’t fit in a uintmax_t either.\nuintmax_t was a mistake as it becomes part of the ABI and can never be\nrevised even when new integer types come along. uintmax_t can hold any\nvalid address, but will strip the metadata. It turns out almost no\nsoftware tries to put a pointer in a uintmax_t and cast it back to a\npointer.\n\nNote that, even if we wanted to, we coldn't just map uintmax_t to a\nuintptr_t, as on 32-bit architectures uintmax_t is a 64-bit integer but\nuintptr_t only has a 32-bit range (plus 32 bits of metadata), and we do\nhave a 32-bit CHERI variant for embedded use cases.\n\nThis is one of a few warts that people will just have to deal with for\nCHERI; there’s no way round it if you want anything that implements the\nideas of CHERI.\n\nJess\n\n"},{"id":"445678","messageId":"Ydd50/BLKlbK+Wj4@camp.crustytoothpaste.net","threadId":"57187","inReplyTo":"20220105132324.6651-1-jrtc27@jrtc27.com","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2022-01-06T23:22:59Z","receivedAt":"2022-01-06T23:23:04Z","isPatch":true,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On 2022-01-05 at 13:23:24, Jessica Clarke wrote:\n> Currently git_qsort_s allocates a buffer on the stack that has no\n> alignment, and mem_pool_alloc assumes uintmax_t's size is adequate\n> alignment for any type.\n> \n> On CHERI, and thus Arm's Morello prototype, pointers are implemented as\n> hardware capabilities which, as well as having a normal integer address,\n> have additional bounds, permissions and other metadata in a second word,\n> so on a 64-bit architecture they are 128-bit quantities, including their\n> alignment requirements. Despite being 128-bit, their integer component\n> is still only a 64-bit field, so uintmax_t remains 64-bit, and therefore\n> uintmax_t does not sufficiently align an allocation.\n> \n> Moreover, these capabilities have an additional \"129th\" tag bit, which\n> tracks the validity of the capability and is cleared on any invalid\n> operation that doesn't trap (e.g. partially overwriting a capability\n> will invalidate it) which, combined with the architecture's strict\n> checks on capability manipulation instructions, ensures it is\n> architecturally impossible to construct a capability that gives more\n> rights than those you were given in the first place. To store these tag\n> bits, each capability sized and aligned word in memory gains a single\n> tag bit that is stored in unaddressable (to the processor) memory. This\n> means that it is impossible to store a capability at an unaligned\n> address: a normal load or store of a capability will always take an\n> alignment fault even if the (micro)architecture supports unaligned\n> loads/stores for other data types, and a memcpy will, if the destination\n> is not appropriately aligned, copy the byte representation but lose the\n> tag, meaning that if it is eventually copied back and loaded from an\n> aligned location any attempt to dereference it will trap with a tag\n> fault. Thus, even char buffers that are memcpy'ed to or from must be\n> properly aligned on CHERI architectures if they are to hold pointers.\n\nI think this is going to be a problem in a lot of places, not just in\nGit.  I'm pretty sure that copying data this way is specifically allowed\nby C and POSIX, and thus this approach is going to break a whole lot of\nthings.\n\nFor example, casting a void * to uintptr_t and back should produce two\npointers that compare equal.  The C standard says that two pointers\ncompare equal if they're both null, both point to the same object, or\none points one past the end of an array and the other happens to point\nto the beginning of another object.  If the pointers aren't null and the\noriginal one points to valid data, then the resulting pointer (after the\ntwo casts) would point to the same object (since that's the only valid\noption that's left), and therefore could be used to access it, but that\nwouldn't necessarily work in this case.\n\nThe CHERI paper I'm reading also specifically says it is not changing\nuintmax_t, which is a direct violation of the C standard.  If uintptr_t\nmust be larger than 64 bits, then so must uintmax_t, even if that\nhappens to be inconvenient (because it changes the ABI from the normal\nsystem ABI).  It sounds like, in fact, that you can't actually provide\nuintptr_t with the current architecture, because it can't be provided in\na standard-compliant way.\n\nIs there something I'm missing here, or is it the case that CHERI's\nbehavior isn't compliant with the C standard?\n-- \nbrian m. carlson (he/him or they/them)\nToronto, Ontario, CA\n"},{"id":"445679","messageId":"F5B62547-BC22-4EF8-87FE-70E195EC88B8@jrtc27.com","threadId":"57187","inReplyTo":"Ydd50/BLKlbK+Wj4@camp.crustytoothpaste.net","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-06T23:31:56Z","receivedAt":"2022-01-06T23:32:00Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"On 6 Jan 2022, at 23:22, brian m. carlson <sandals@crustytoothpaste.net> wrote:\n> \n> On 2022-01-05 at 13:23:24, Jessica Clarke wrote:\n>> Currently git_qsort_s allocates a buffer on the stack that has no\n>> alignment, and mem_pool_alloc assumes uintmax_t's size is adequate\n>> alignment for any type.\n>> \n>> On CHERI, and thus Arm's Morello prototype, pointers are implemented as\n>> hardware capabilities which, as well as having a normal integer address,\n>> have additional bounds, permissions and other metadata in a second word,\n>> so on a 64-bit architecture they are 128-bit quantities, including their\n>> alignment requirements. Despite being 128-bit, their integer component\n>> is still only a 64-bit field, so uintmax_t remains 64-bit, and therefore\n>> uintmax_t does not sufficiently align an allocation.\n>> \n>> Moreover, these capabilities have an additional \"129th\" tag bit, which\n>> tracks the validity of the capability and is cleared on any invalid\n>> operation that doesn't trap (e.g. partially overwriting a capability\n>> will invalidate it) which, combined with the architecture's strict\n>> checks on capability manipulation instructions, ensures it is\n>> architecturally impossible to construct a capability that gives more\n>> rights than those you were given in the first place. To store these tag\n>> bits, each capability sized and aligned word in memory gains a single\n>> tag bit that is stored in unaddressable (to the processor) memory. This\n>> means that it is impossible to store a capability at an unaligned\n>> address: a normal load or store of a capability will always take an\n>> alignment fault even if the (micro)architecture supports unaligned\n>> loads/stores for other data types, and a memcpy will, if the destination\n>> is not appropriately aligned, copy the byte representation but lose the\n>> tag, meaning that if it is eventually copied back and loaded from an\n>> aligned location any attempt to dereference it will trap with a tag\n>> fault. Thus, even char buffers that are memcpy'ed to or from must be\n>> properly aligned on CHERI architectures if they are to hold pointers.\n> \n> I think this is going to be a problem in a lot of places, not just in\n> Git.  I'm pretty sure that copying data this way is specifically allowed\n> by C and POSIX, and thus this approach is going to break a whole lot of\n> things.\n\nThe standard says you can copy anything to an unsigned char array to\nget its object representation. This we support just fine. The standard\ndoes not say you can copy that object representation back to an object\nof the original type and get a valid object of the original type. We\nonly support that if the unsigned char array is aligned enough.\n\nTechnically git is already wrong here by using char not unsigned char,\nthough that doesn’t make a difference for CHERI, nor any implementation\nI know of.\n\n> For example, casting a void * to uintptr_t and back should produce two\n> pointers that compare equal.  The C standard says that two pointers\n> compare equal if they're both null, both point to the same object, or\n> one points one past the end of an array and the other happens to point\n> to the beginning of another object.  If the pointers aren't null and the\n> original one points to valid data, then the resulting pointer (after the\n> two casts) would point to the same object (since that's the only valid\n> option that's left), and therefore could be used to access it, but that\n> wouldn't necessarily work in this case.\n\nAll of this CHERI supports. Casting to uintptr_t and back works just fine.\n\n> The CHERI paper I'm reading also specifically says it is not changing\n> uintmax_t, which is a direct violation of the C standard.  If uintptr_t\n> must be larger than 64 bits, then so must uintmax_t, even if that\n> happens to be inconvenient (because it changes the ABI from the normal\n> system ABI).  It sounds like, in fact, that you can't actually provide\n> uintptr_t with the current architecture, because it can't be provided in\n> a standard-compliant way.\n\nEvery C implementation that provides 128-bit integers violates this.\nNothing cares. As explained in my reply to Junio this thread it is not\npossible to provide a uintmax_t that can hold a uintptr_t on CHERI in\ngeneral. So we don’t. And almost no software cares.\n\nNot providing a uintptr_t breaks basically all systems code ever,\nexcept the code that’s so old it assumes unsigned long is the right\ntype and is already broken for CHERI as a result.\n\n> Is there something I'm missing here, or is it the case that CHERI's\n> behavior isn't compliant with the C standard?\n\nThere are some cases where we’re slightly non-compliant. So is every\nimplementation that exists. We believe the few restrictions we add,\nwhich can all be easily worked around, are vastly outweighed by the\nbenefit of having hardware that enforces fine-grained memory safety\nefficiently, and the empirical evidence is that these restrictions are\nnot an issue for the vast majority of real-world C code.\n\nJess\n\n"},{"id":"445682","messageId":"xmqqfsq09ziq.fsf@gitster.g","threadId":"57187","inReplyTo":"97D2AB55-0F8F-4C38-A5C6-1AAA43EA064A@jrtc27.com","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-07T00:10:21Z","receivedAt":"2022-01-07T00:10:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jessica Clarke <jrtc27@jrtc27.com> writes:\n\n> This is also true of uint128_t, it doesn’t fit in a uintmax_t either.\n\nuintmax_t is supposed to be an unsigned integer type capable of\nrepresenting any value of any unsigned integer type, so if you have\n128-bit unsigned integer, your uintmax_t should be at last that\nwide, or your uintmax_t is not uintmax_t as far as C standard is\nconcerned, no?\n\nuintptr_t is an unsigned integer type that any valid pointer to void\ncan be converted to this type, then converted back to pointer to\nvoid, and the result will compare equal to the original pointer.  So\nthe value of uintptr_t cannot be represented by uintmax_t, there is\nsomething wrong.\n\n> uintmax_t was a mistake as it becomes part of the ABI and can never be\n> revised even when new integer types come along. uintmax_t can hold any\n> valid address, but will strip the metadata.\n\nIt is a flaw in the implementation of uintmax_t on the architecture\nthat needs \"the metadata\", no?  If the implementation supports a\nnotion of uintptr_t (i.e. there exists an unsigned integer type that\ncan safely go back and forth from pointer to void), an unsigned\ninteger type that is at least as wide as any unsigned integer type\nshould certainly be able to hold what would fit in uintptr_t, no?\n\nPuzzled.\n\n"},{"id":"445683","messageId":"54D928E7-7BA2-4BD7-9C08-A4650712CEBF@jrtc27.com","threadId":"57187","inReplyTo":"xmqqfsq09ziq.fsf@gitster.g","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-07T00:22:35Z","receivedAt":"2022-01-07T00:22:38Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"On 7 Jan 2022, at 00:10, Junio C Hamano <gitster@pobox.com> wrote:\n> \n> Jessica Clarke <jrtc27@jrtc27.com> writes:\n> \n>> This is also true of uint128_t, it doesn’t fit in a uintmax_t either.\n> \n> uintmax_t is supposed to be an unsigned integer type capable of\n> representing any value of any unsigned integer type, so if you have\n> 128-bit unsigned integer, your uintmax_t should be at last that\n> wide, or your uintmax_t is not uintmax_t as far as C standard is\n> concerned, no?\n\nYes. Every 64-bit architecture implemented by GCC and Clang violates\nthis. This is why uintmax_t is a terrible idea, it gets baked into your\nABI and you can’t add new integer types. People decided for 128-bit\nintegers it was better to add them than let uintmax_t constrain them.\nWe take the same approach for CHERI of not caring about uintmax_t. If\nyou want to hold this against CHERI, go file bugs against GCC and Clang\nfor violating the standard on x86_64, aarch64, mips64, powerpc64,\ns390x, sparc64, and so on.\n\n> uintptr_t is an unsigned integer type that any valid pointer to void\n> can be converted to this type, then converted back to pointer to\n> void, and the result will compare equal to the original pointer.  So\n> the value of uintptr_t cannot be represented by uintmax_t, there is\n> something wrong.\n> \n>> uintmax_t was a mistake as it becomes part of the ABI and can never be\n>> revised even when new integer types come along. uintmax_t can hold any\n>> valid address, but will strip the metadata.\n> \n> It is a flaw in the implementation of uintmax_t on the architecture\n> that needs \"the metadata\", no?  If the implementation supports a\n> notion of uintptr_t (i.e. there exists an unsigned integer type that\n> can safely go back and forth from pointer to void), an unsigned\n> integer type that is at least as wide as any unsigned integer type\n> should certainly be able to hold what would fit in uintptr_t, no?\n\nIf you want to get really language-lawyer-y about it, you can actually\nargue that this is a compliant implementation of the C standard.\nInteger types are permitted to have padding bits, and some combinations\nof padding bits are allowed to be trap representations. Technically, in\nour representation, the metadata bits are padding bits, because they do\nnot contribute to the precision like value bits. It is therefore the\ncase that the *value* of a uintptr_t still fits into a uintmax_t, but\nthe latter has no padding bits, and casting the latter to the former\nyields a trap representation when further cast back to a pointer. This\nmay not the intent of the spec, and not how anyone thinks of it because\nCHERI is the first implementation that pushes the boundary here, but\nit’s technically legal under that interpretation. You may disagree with\nthe interpretation, and I don’t like to use it most of the time because\nit’s complicated and involves yet more ill-defined parts of the spec\n(e.g. it says arithmetic operations on valid values (they mean objects,\nI assume, as the value only includes value bits, but the input could be\na trap representation on some implementations) never generate a trap\nrepresentation other than as part of an exceptional condition such as\nan overflow, but nowhere defines what counts as an arithmetic\noperation).\n\nJess\n\n> Puzzled.\n> \n\n"},{"id":"445684","messageId":"YdeJ8Ub2Q0/c9kO2@camp.crustytoothpaste.net","threadId":"57187","inReplyTo":"xmqqfsq09ziq.fsf@gitster.g","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2022-01-07T00:31:45Z","receivedAt":"2022-01-07T00:31:51Z","isPatch":true,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On 2022-01-07 at 00:10:21, Junio C Hamano wrote:\n> Jessica Clarke <jrtc27@jrtc27.com> writes:\n> \n> > This is also true of uint128_t, it doesn’t fit in a uintmax_t either.\n\nI don't have this type from either GCC or Clang on my Debian amd64/sid\nsystem.  I know those compilers support 128-bit values because Rust uses\nthem, but they are not exposed in standard C and therefore those\ncompilers appear to be compliant when run in standards mode.\n\n> uintmax_t is supposed to be an unsigned integer type capable of\n> representing any value of any unsigned integer type, so if you have\n> 128-bit unsigned integer, your uintmax_t should be at last that\n> wide, or your uintmax_t is not uintmax_t as far as C standard is\n> concerned, no?\n> \n> uintptr_t is an unsigned integer type that any valid pointer to void\n> can be converted to this type, then converted back to pointer to\n> void, and the result will compare equal to the original pointer.  So\n> the value of uintptr_t cannot be represented by uintmax_t, there is\n> something wrong.\n\nYes, this is the case.  The C standard mandates this behavior.\n\nNow, as far as I'm aware, the standard does not mandate that that\nuintmax_t have the strictest alignment requirements of any integral\ntype.  It could be that other types have stricter requirements, for\nexample, on some systems.  But it is required that conversion from void *\nto uintptr_t to uintmax_t to uintptr_t to void * preserve the\nfunctionality of the pointer.\n-- \nbrian m. carlson (he/him or they/them)\nToronto, Ontario, CA\n"},{"id":"445685","messageId":"4D8B32AE-8316-4907-98F6-097901EC3DC0@jrtc27.com","threadId":"57187","inReplyTo":"YdeJ8Ub2Q0/c9kO2@camp.crustytoothpaste.net","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-07T00:39:59Z","receivedAt":"2022-01-07T00:40:02Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"On 7 Jan 2022, at 00:31, brian m. carlson <sandals@crustytoothpaste.net> wrote:\n> \n> On 2022-01-07 at 00:10:21, Junio C Hamano wrote:\n>> Jessica Clarke <jrtc27@jrtc27.com> writes:\n>> \n>>> This is also true of uint128_t, it doesn’t fit in a uintmax_t either.\n> \n> I don't have this type from either GCC or Clang on my Debian amd64/sid\n> system.  I know those compilers support 128-bit values because Rust uses\n> them, but they are not exposed in standard C and therefore those\n> compilers appear to be compliant when run in standards mode.\n\nAh, I should have said (un)(signed) __int128, there is no typedef for them even in GNU C.\n\n__int128 exists as an integer type even with -std=c99, not just\n-std=gnu99. -pedantic will warn that __int128 does not exist in ISO C,\nbut __int128__ still exists and works with no warnings even then. So it\nvery much exists in standards mode.\n\n>> uintmax_t is supposed to be an unsigned integer type capable of\n>> representing any value of any unsigned integer type, so if you have\n>> 128-bit unsigned integer, your uintmax_t should be at last that\n>> wide, or your uintmax_t is not uintmax_t as far as C standard is\n>> concerned, no?\n>> \n>> uintptr_t is an unsigned integer type that any valid pointer to void\n>> can be converted to this type, then converted back to pointer to\n>> void, and the result will compare equal to the original pointer.  So\n>> the value of uintptr_t cannot be represented by uintmax_t, there is\n>> something wrong.\n> \n> Yes, this is the case.  The C standard mandates this behavior.\n> \n> Now, as far as I'm aware, the standard does not mandate that that\n> uintmax_t have the strictest alignment requirements of any integral\n> type.  It could be that other types have stricter requirements, for\n> example, on some systems.  But it is required that conversion from void *\n> to uintptr_t to uintmax_t to uintptr_t to void * preserve the\n> functionality of the pointer.\n\nTo quote what I said to Junio in a futher reply:\n\n> If you want to get really language-lawyer-y about it, you can actually\n> argue that this is a compliant implementation of the C standard.\n> Integer types are permitted to have padding bits, and some combinations\n> of padding bits are allowed to be trap representations. Technically, in\n> our representation, the metadata bits are padding bits, because they do\n> not contribute to the precision like value bits. It is therefore the\n> case that the *value* of a uintptr_t still fits into a uintmax_t, but\n> the latter has no padding bits, and casting the latter to the former\n> yields a trap representation when further cast back to a pointer. This\n> may not the intent of the spec, and not how anyone thinks of it because\n> CHERI is the first implementation that pushes the boundary here, but\n> it’s technically legal under that interpretation. You may disagree with\n> the interpretation, and I don’t like to use it most of the time because\n> it’s complicated and involves yet more ill-defined parts of the spec\n> (e.g. it says arithmetic operations on valid values (they mean objects,\n> I assume, as the value only includes value bits, but the input could be\n> a trap representation on some implementations) never generate a trap\n> representation other than as part of an exceptional condition such as\n> an overflow, but nowhere defines what counts as an arithmetic\n> operation).\n\n\nSo, no, C does not actually require what you say. It requires that void\n* -> uintptr_t -> void * give you a valid pointer. It requires that\nuintptr_t -> uintmax_t preserves the *value* of the uintptr_t, which we\ndo, because the value is formed from only the value bits which\ncontribute to the precision, which is 64 bits in this case, and\nuintmax_t is still 64-bit. It requires that uintmax_t -> uintptr_t,\nsince uintptr_t’s precision is the same as uintmax_t’s, be always\nvalid, which is is. But it does not require that that uintptr_t has the\nsame representation as the original uintptr_t, which it does not for\nus. And therefore it does not require that casting that uintptr_t back\nto a void * yields a valid pointer. So if you want to really dig into\nthe details of the standard, we are technically compliant, even if some\nmight argue it’s not in the spirit of the standard.\n\nJess\n\n"},{"id":"445686","messageId":"Ydea3EO7wrYc9/Ij@camp.crustytoothpaste.net","threadId":"57187","inReplyTo":"4D8B32AE-8316-4907-98F6-097901EC3DC0@jrtc27.com","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2022-01-07T01:43:56Z","receivedAt":"2022-01-07T01:44:03Z","isPatch":true,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On 2022-01-07 at 00:39:59, Jessica Clarke wrote:\n> On 7 Jan 2022, at 00:31, brian m. carlson <sandals@crustytoothpaste.net> wrote:\n> > If you want to get really language-lawyer-y about it, you can actually\n> > argue that this is a compliant implementation of the C standard.\n> > Integer types are permitted to have padding bits, and some combinations\n> > of padding bits are allowed to be trap representations. Technically, in\n> > our representation, the metadata bits are padding bits, because they do\n> > not contribute to the precision like value bits. It is therefore the\n> > case that the *value* of a uintptr_t still fits into a uintmax_t, but\n> > the latter has no padding bits, and casting the latter to the former\n> > yields a trap representation when further cast back to a pointer. This\n> > may not the intent of the spec, and not how anyone thinks of it because\n> > CHERI is the first implementation that pushes the boundary here, but\n> > it’s technically legal under that interpretation. You may disagree with\n> > the interpretation, and I don’t like to use it most of the time because\n> > it’s complicated and involves yet more ill-defined parts of the spec\n> > (e.g. it says arithmetic operations on valid values (they mean objects,\n> > I assume, as the value only includes value bits, but the input could be\n> > a trap representation on some implementations) never generate a trap\n> > representation other than as part of an exceptional condition such as\n> > an overflow, but nowhere defines what counts as an arithmetic\n> > operation).\n> \n> \n> So, no, C does not actually require what you say. It requires that void\n> * -> uintptr_t -> void * give you a valid pointer. It requires that\n> uintptr_t -> uintmax_t preserves the *value* of the uintptr_t, which we\n> do, because the value is formed from only the value bits which\n> contribute to the precision, which is 64 bits in this case, and\n> uintmax_t is still 64-bit. It requires that uintmax_t -> uintptr_t,\n> since uintptr_t’s precision is the same as uintmax_t’s, be always\n> valid, which is is. But it does not require that that uintptr_t has the\n> same representation as the original uintptr_t, which it does not for\n> us. And therefore it does not require that casting that uintptr_t back\n> to a void * yields a valid pointer. So if you want to really dig into\n> the details of the standard, we are technically compliant, even if some\n> might argue it’s not in the spirit of the standard.\n\nSure, implementations are allowed to have padding bits.  They're also\nallowed, at the moment, to use signed-magnitude or ones' complement\nintegers, have CHAR_BIT greater than 8, have sizeof(char) ==\nsizeof(short), not implement any of the customary sizes of intN_t or\nuintN_t, not provide uintptr_t, and use middle-endian numbers.\n\nHowever, if your ABI is only compliant in the face of those features\n(especially when it could have been written in a way which would have\nbeen compliant without the use of those features), it's intentionally\nhostile to real-world developers, and I don't think we should support\nit[0].  I'd be willing to revisit this if your ABI were defined in a\nreasonable, sane way, where sizeof(uintmax_t) >= sizeof(uintptr_t),\nwithout padding bits, where the alignment of pointers from malloc is\nsuitable for all types, and where the alignment of a type is no greater\nthan sizeof(type).\n\nI'm not opposed to a small amount of finagling for this case, but I am\nvery much opposed to defining your C ABI in an intentionally difficult\nway.  128-bit integers in 64-bit Linux were not originally part of the C\nABIs and if the ABI is ill defined now, that's a historical accident.\nBut this is a new ABI for a new architecture and it could have been\ndefined in a responsible way, but wasn't.\n\nAs an aside, I was actually going to point out that you could propose a\nnice Rust or Go ABI with the status quo, but if your C ABI requires\npadding bits, then you're probably going to have a hard time doing so,\nsince I don't believe those languages support padding bits and they need\nto support the C ABI.\n\n[0] For the record, I care strongly about portability, and I would not\naccept a runtime having any of the qualities I mentioned in the first\nparagraph.\n-- \nbrian m. carlson (he/him or they/them)\nToronto, Ontario, CA\n"},{"id":"445687","messageId":"B8B73861-9095-47D2-AC4F-5EC8D7589401@jrtc27.com","threadId":"57187","inReplyTo":"Ydea3EO7wrYc9/Ij@camp.crustytoothpaste.net","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-07T02:08:33Z","receivedAt":"2022-01-07T02:08:37Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"On 7 Jan 2022, at 01:43, brian m. carlson <sandals@crustytoothpaste.net> wrote:\n> \n> On 2022-01-07 at 00:39:59, Jessica Clarke wrote:\n>> On 7 Jan 2022, at 00:31, brian m. carlson <sandals@crustytoothpaste.net> wrote:\n>>> If you want to get really language-lawyer-y about it, you can actually\n>>> argue that this is a compliant implementation of the C standard.\n>>> Integer types are permitted to have padding bits, and some combinations\n>>> of padding bits are allowed to be trap representations. Technically, in\n>>> our representation, the metadata bits are padding bits, because they do\n>>> not contribute to the precision like value bits. It is therefore the\n>>> case that the *value* of a uintptr_t still fits into a uintmax_t, but\n>>> the latter has no padding bits, and casting the latter to the former\n>>> yields a trap representation when further cast back to a pointer. This\n>>> may not the intent of the spec, and not how anyone thinks of it because\n>>> CHERI is the first implementation that pushes the boundary here, but\n>>> it’s technically legal under that interpretation. You may disagree with\n>>> the interpretation, and I don’t like to use it most of the time because\n>>> it’s complicated and involves yet more ill-defined parts of the spec\n>>> (e.g. it says arithmetic operations on valid values (they mean objects,\n>>> I assume, as the value only includes value bits, but the input could be\n>>> a trap representation on some implementations) never generate a trap\n>>> representation other than as part of an exceptional condition such as\n>>> an overflow, but nowhere defines what counts as an arithmetic\n>>> operation).\n>> \n>> \n>> So, no, C does not actually require what you say. It requires that void\n>> * -> uintptr_t -> void * give you a valid pointer. It requires that\n>> uintptr_t -> uintmax_t preserves the *value* of the uintptr_t, which we\n>> do, because the value is formed from only the value bits which\n>> contribute to the precision, which is 64 bits in this case, and\n>> uintmax_t is still 64-bit. It requires that uintmax_t -> uintptr_t,\n>> since uintptr_t’s precision is the same as uintmax_t’s, be always\n>> valid, which is is. But it does not require that that uintptr_t has the\n>> same representation as the original uintptr_t, which it does not for\n>> us. And therefore it does not require that casting that uintptr_t back\n>> to a void * yields a valid pointer. So if you want to really dig into\n>> the details of the standard, we are technically compliant, even if some\n>> might argue it’s not in the spirit of the standard.\n> \n> Sure, implementations are allowed to have padding bits.  They're also\n> allowed, at the moment, to use signed-magnitude or ones' complement\n> integers, have CHAR_BIT greater than 8, have sizeof(char) ==\n> sizeof(short), not implement any of the customary sizes of intN_t or\n> uintN_t, not provide uintptr_t, and use middle-endian numbers.\n> \n> However, if your ABI is only compliant in the face of those features\n> (especially when it could have been written in a way which would have\n> been compliant without the use of those features), it's intentionally\n> hostile to real-world developers, and I don't think we should support\n> it[0].  I'd be willing to revisit this if your ABI were defined in a\n> reasonable, sane way, where sizeof(uintmax_t) >= sizeof(uintptr_t),\n> without padding bits, where the alignment of pointers from malloc is\n> suitable for all types, and where the alignment of a type is no greater\n> than sizeof(type).\n> \n> I'm not opposed to a small amount of finagling for this case, but I am\n> very much opposed to defining your C ABI in an intentionally difficult\n> way.  128-bit integers in 64-bit Linux were not originally part of the C\n> ABIs and if the ABI is ill defined now, that's a historical accident.\n> But this is a new ABI for a new architecture and it could have been\n> defined in a responsible way, but wasn't.\n\nIt’s not a choice. It is not possible to define uintmax_t as being able\nto safely round-trip any uintptr_t in a way that preserves pointer\nvalidity unless you want to outlaw 64-bit integers on 32-bit CHERI\nimplementations, and good luck with that one, for reasons I have\npreviously explained, so if you do not wish to support this C\nimplementation then upstream Git will not work on CHERI/Arm’s Morello.\nNothing in this patch causes additional burden on other architectures,\nin fact it likely improves performance on some due to increased buffer\nalignment, so this seems a rather unnecessary line to take. We have all\nof our fork of FreeBSD, kernel and userland, built and working on\nCHERI, as well as X11 and the core of a KDE desktop (KWin, Plasma,\nKate, Okular, Gwenview, Konsole; we would have more but up until\nrecently we’ve needed to cross-compile everything and that’s often a\npain to get things building), plus WebKit’s JavaScriptCore complete\nwith a working JIT, so Git would be a notable omission in the stack,\nand rather important for developers to actually get work done on their\nboards.\n\nNote that C requires us to define those bits as padding bits; the range\nof an integer type is defined to be 0 to 2^N-1, where N is the number\nof value bits, so it would be impossible to have any metadata in a\nuintptr_t.\n\nSo I take issue with “in a responsible way”. CHERI has been in\ndevelopment for over 10 years, it’s been done in collaboration with\nArm, with people intimately familiar with C semantics and with\nextensive analysis of what real-world software expects of C in order to\ncome up with the most-compatible implementation we reasonably can\nthat’s still feasible to implement in hardware and provides the desired\nprotection properties. Declaring it broken/hostile/etc feels like\nthrowing the baby out with the bath water; for industry to move away\nfrom the sorry state of affairs that we still see with C and C++ where\nmemory safety vulnerabilities are ubiquitous you cannot just restrict\nnew ABIs to the status quo, as you just won’t make any progress.\n\n> As an aside, I was actually going to point out that you could propose a\n> nice Rust or Go ABI with the status quo, but if your C ABI requires\n> padding bits, then you're probably going to have a hard time doing so,\n> since I don't believe those languages support padding bits and they need\n> to support the C ABI.\n\nThere is no such restriction in Rust that I can see. It’s true you’d\nneed to slightly tweak Go’s specification as uintptr is currently an\ninteger type and n-bit integer types are defined to be n-bit two’s\ncomplement values. I see no reason why that couldn’t be done though, I\ndoubt much cares. Rust only defines the representation of its\nfixed-width integer types. There’s no reason you couldn’t add an\nadditional integer type for a capability, like we do for C. The only\nissue with Rust is that it conflates uintptr_t with size_t, for which\nthere are various discussion threads with Rust maintainers and a path\nforward for making it work if someone has the time to invest in making\nRust work. Languages can evolve; there’s no reason they can’t for CHERI\nlike they do for anything else they want to add, change, deprecate or\nremove.\n\nBut this is all irrelevant to discussions of C.\n\nJess\n\n> [0] For the record, I care strongly about portability, and I would not\n> accept a runtime having any of the qualities I mentioned in the first\n> paragraph.\n> -- \n> brian m. carlson (he/him or they/them)\n> Toronto, Ontario, CA\n\n"},{"id":"445688","messageId":"40419F44-8D68-42EF-BA50-27AB2B167265@jrtc27.com","threadId":"57187","inReplyTo":"B8B73861-9095-47D2-AC4F-5EC8D7589401@jrtc27.com","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-07T02:11:26Z","receivedAt":"2022-01-07T02:11:30Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"On 7 Jan 2022, at 02:08, Jessica Clarke <jrtc27@jrtc27.com> wrote:\n> \n> On 7 Jan 2022, at 01:43, brian m. carlson <sandals@crustytoothpaste.net> wrote:\n>> \n>> On 2022-01-07 at 00:39:59, Jessica Clarke wrote:\n>>> On 7 Jan 2022, at 00:31, brian m. carlson <sandals@crustytoothpaste.net> wrote:\n>>>> If you want to get really language-lawyer-y about it, you can actually\n>>>> argue that this is a compliant implementation of the C standard.\n>>>> Integer types are permitted to have padding bits, and some combinations\n>>>> of padding bits are allowed to be trap representations. Technically, in\n>>>> our representation, the metadata bits are padding bits, because they do\n>>>> not contribute to the precision like value bits. It is therefore the\n>>>> case that the *value* of a uintptr_t still fits into a uintmax_t, but\n>>>> the latter has no padding bits, and casting the latter to the former\n>>>> yields a trap representation when further cast back to a pointer. This\n>>>> may not the intent of the spec, and not how anyone thinks of it because\n>>>> CHERI is the first implementation that pushes the boundary here, but\n>>>> it’s technically legal under that interpretation. You may disagree with\n>>>> the interpretation, and I don’t like to use it most of the time because\n>>>> it’s complicated and involves yet more ill-defined parts of the spec\n>>>> (e.g. it says arithmetic operations on valid values (they mean objects,\n>>>> I assume, as the value only includes value bits, but the input could be\n>>>> a trap representation on some implementations) never generate a trap\n>>>> representation other than as part of an exceptional condition such as\n>>>> an overflow, but nowhere defines what counts as an arithmetic\n>>>> operation).\n>>> \n>>> \n>>> So, no, C does not actually require what you say. It requires that void\n>>> * -> uintptr_t -> void * give you a valid pointer. It requires that\n>>> uintptr_t -> uintmax_t preserves the *value* of the uintptr_t, which we\n>>> do, because the value is formed from only the value bits which\n>>> contribute to the precision, which is 64 bits in this case, and\n>>> uintmax_t is still 64-bit. It requires that uintmax_t -> uintptr_t,\n>>> since uintptr_t’s precision is the same as uintmax_t’s, be always\n>>> valid, which is is. But it does not require that that uintptr_t has the\n>>> same representation as the original uintptr_t, which it does not for\n>>> us. And therefore it does not require that casting that uintptr_t back\n>>> to a void * yields a valid pointer. So if you want to really dig into\n>>> the details of the standard, we are technically compliant, even if some\n>>> might argue it’s not in the spirit of the standard.\n>> \n>> Sure, implementations are allowed to have padding bits.  They're also\n>> allowed, at the moment, to use signed-magnitude or ones' complement\n>> integers, have CHAR_BIT greater than 8, have sizeof(char) ==\n>> sizeof(short), not implement any of the customary sizes of intN_t or\n>> uintN_t, not provide uintptr_t, and use middle-endian numbers.\n>> \n>> However, if your ABI is only compliant in the face of those features\n>> (especially when it could have been written in a way which would have\n>> been compliant without the use of those features), it's intentionally\n>> hostile to real-world developers, and I don't think we should support\n>> it[0].  I'd be willing to revisit this if your ABI were defined in a\n>> reasonable, sane way, where sizeof(uintmax_t) >= sizeof(uintptr_t),\n>> without padding bits, where the alignment of pointers from malloc is\n>> suitable for all types, and where the alignment of a type is no greater\n>> than sizeof(type).\n>> \n>> I'm not opposed to a small amount of finagling for this case, but I am\n>> very much opposed to defining your C ABI in an intentionally difficult\n>> way.  128-bit integers in 64-bit Linux were not originally part of the C\n>> ABIs and if the ABI is ill defined now, that's a historical accident.\n>> But this is a new ABI for a new architecture and it could have been\n>> defined in a responsible way, but wasn't.\n> \n> It’s not a choice. It is not possible to define uintmax_t as being able\n> to safely round-trip any uintptr_t in a way that preserves pointer\n> validity unless you want to outlaw 64-bit integers on 32-bit CHERI\n> implementations, and good luck with that one, for reasons I have\n> previously explained, so if you do not wish to support this C\n> implementation then upstream Git will not work on CHERI/Arm’s Morello.\n> Nothing in this patch causes additional burden on other architectures,\n> in fact it likely improves performance on some due to increased buffer\n> alignment, so this seems a rather unnecessary line to take. We have all\n> of our fork of FreeBSD, kernel and userland, built and working on\n> CHERI, as well as X11 and the core of a KDE desktop (KWin, Plasma,\n> Kate, Okular, Gwenview, Konsole; we would have more but up until\n> recently we’ve needed to cross-compile everything and that’s often a\n> pain to get things building), plus WebKit’s JavaScriptCore complete\n> with a working JIT, so Git would be a notable omission in the stack,\n> and rather important for developers to actually get work done on their\n> boards.\n> \n> Note that C requires us to define those bits as padding bits; the range\n> of an integer type is defined to be 0 to 2^N-1, where N is the number\n> of value bits, so it would be impossible to have any metadata in a\n> uintptr_t.\n> \n> So I take issue with “in a responsible way”. CHERI has been in\n> development for over 10 years, it’s been done in collaboration with\n> Arm, with people intimately familiar with C semantics and with\n> extensive analysis of what real-world software expects of C in order to\n> come up with the most-compatible implementation we reasonably can\n> that’s still feasible to implement in hardware and provides the desired\n> protection properties. Declaring it broken/hostile/etc feels like\n> throwing the baby out with the bath water; for industry to move away\n> from the sorry state of affairs that we still see with C and C++ where\n> memory safety vulnerabilities are ubiquitous you cannot just restrict\n> new ABIs to the status quo, as you just won’t make any progress.\n> \n>> As an aside, I was actually going to point out that you could propose a\n>> nice Rust or Go ABI with the status quo, but if your C ABI requires\n>> padding bits, then you're probably going to have a hard time doing so,\n>> since I don't believe those languages support padding bits and they need\n>> to support the C ABI.\n> \n> There is no such restriction in Rust that I can see. It’s true you’d\n> need to slightly tweak Go’s specification as uintptr is currently an\n> integer type and n-bit integer types are defined to be n-bit two’s\n> complement values. I see no reason why that couldn’t be done though, I\n> doubt much cares. Rust only defines the representation of its\n> fixed-width integer types. There’s no reason you couldn’t add an\n> additional integer type for a capability, like we do for C. The only\n> issue with Rust is that it conflates uintptr_t with size_t, for which\n> there are various discussion threads with Rust maintainers and a path\n> forward for making it work if someone has the time to invest in making\n> Rust work. Languages can evolve; there’s no reason they can’t for CHERI\n> like they do for anything else they want to add, change, deprecate or\n> remove.\n> \n> But this is all irrelevant to discussions of C.\n\nOh and:\n\n> where the alignment of pointers from malloc is\n> suitable for all types\n\nThis is true of CHERI.\n\n> and where the alignment of a type is no greater\n> than sizeof(type).\n\nThis is true of CHERI, and it’s impossible for that not to be true.\nOtherwise arrays don’t work.\n\nJess\n\n"},{"id":"445720","messageId":"3b03382e-3fb3-54b2-0917-18ddcade566f@iee.email","threadId":"57187","inReplyTo":"20220105132324.6651-1-jrtc27@jrtc27.com","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.email","sentAt":"2022-01-07T14:57:11Z","receivedAt":"2022-01-07T14:57:15Z","isPatch":true,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"On 05/01/2022 13:23, Jessica Clarke wrote:\n> Currently git_qsort_s allocates a buffer on the stack that has no\n> alignment, and mem_pool_alloc assumes uintmax_t's size is adequate\n> alignment for any type.\n>\n> On CHERI, and thus Arm's Morello prototype, pointers are implemented as\n> hardware capabilities which, as well as having a normal integer address,\n> have additional bounds, permissions and other metadata in a second word,\n> so on a 64-bit architecture they are 128-bit quantities, including their\n> alignment requirements. Despite being 128-bit, their integer component\n> is still only a 64-bit field, so uintmax_t remains 64-bit, and therefore\n> uintmax_t does not sufficiently align an allocation.\n\nI did find that the introduction paragraphs in this and its companion\npatch needed a little more background of the uninitiated.\n\nI felt it needed a few words to highlight the innovative, potentially\n'breaking', changes that CHERI (&co) provides, such as the hidden bit,\nthe shift from classic von Neumann architecture, inclusion of typing\nfor  values, etc. and how that affects the compromises that are within\nthe C standard (and those that features misreadings and conflicts with it).\n\nSome of the follow up discussions have a great similarity with the\nWindows LLP64 (`long long`) issues that also confuse the arithmetic\noperation capabilities with the memory pointer capabilities.\n\nThe layout needed a bit of SPIN (situation, problem, implication, need\npayoff) to see how it hangs together across all the different\nimplementations. I know, from experience, it's not easy to pick out the\n'obvious', but implicit, foundational aspects. While, explaining them\nfrom an implementation perspective is easy for those who know the\nimplementation, I found it took a few reads to get my head around the\ndiscussion (e.g. I wasn't familiar with `typedef union`s).\n\nImproved memory safety does sound to be worthwhile!\n\nPhilip\n> Moreover, these capabilities have an additional \"129th\" tag bit, which\n> tracks the validity of the capability and is cleared on any invalid\n> operation that doesn't trap (e.g. partially overwriting a capability\n> will invalidate it) which, combined with the architecture's strict\n> checks on capability manipulation instructions, ensures it is\n> architecturally impossible to construct a capability that gives more\n> rights than those you were given in the first place. To store these tag\n> bits, each capability sized and aligned word in memory gains a single\n> tag bit that is stored in unaddressable (to the processor) memory. This\n> means that it is impossible to store a capability at an unaligned\n> address: a normal load or store of a capability will always take an\n> alignment fault even if the (micro)architecture supports unaligned\n> loads/stores for other data types, and a memcpy will, if the destination\n> is not appropriately aligned, copy the byte representation but lose the\n> tag, meaning that if it is eventually copied back and loaded from an\n> aligned location any attempt to dereference it will trap with a tag\n> fault. Thus, even char buffers that are memcpy'ed to or from must be\n> properly aligned on CHERI architectures if they are to hold pointers.\n>\n> Address both of these by introducing a new git_max_align type put in a\n> union with the on-stack buffer to force its alignment, as well as a new\n> GIT_MAX_ALIGNMENT macro whose value is the alignment of git_max_align\n> that gets used for mem_pool_alloc. As well as making the code work on\n> CHERI, the former change likely also improves performance on some\n> architectures by making memcpy faster (either because it can use larger\n> block sizes or because the microarchitecture has inefficient unaligned\n> accesses).\n>\n> Signed-off-by: Jessica Clarke <jrtc27@jrtc27.com>\n> ---\n>  compat/qsort_s.c  | 11 +++++++----\n>  git-compat-util.h | 11 +++++++++++\n>  mem-pool.c        |  6 +++---\n>  3 files changed, 21 insertions(+), 7 deletions(-)\n>\n> diff --git a/compat/qsort_s.c b/compat/qsort_s.c\n> index 52d1f0a73d..1ccdb87451 100644\n> --- a/compat/qsort_s.c\n> +++ b/compat/qsort_s.c\n> @@ -49,16 +49,19 @@ int git_qsort_s(void *b, size_t n, size_t s,\n>  \t\tint (*cmp)(const void *, const void *, void *), void *ctx)\n>  {\n>  \tconst size_t size = st_mult(n, s);\n> -\tchar buf[1024];\n> +\tunion {\n> +\t\tchar buf[1024];\n> +\t\tgit_max_align align;\n> +\t} u;\n>  \n>  \tif (!n)\n>  \t\treturn 0;\n>  \tif (!b || !cmp)\n>  \t\treturn -1;\n>  \n> -\tif (size < sizeof(buf)) {\n> -\t\t/* The temporary array fits on the small on-stack buffer. */\n> -\t\tmsort_with_tmp(b, n, s, cmp, buf, ctx);\n> +\tif (size < sizeof(u.buf)) {\n> +\t\t/* The temporary array fits in the small on-stack buffer. */\n> +\t\tmsort_with_tmp(b, n, s, cmp, u.buf, ctx);\n>  \t} else {\n>  \t\t/* It's somewhat large, so malloc it.  */\n>  \t\tchar *tmp = xmalloc(size);\n> diff --git a/git-compat-util.h b/git-compat-util.h\n> index 5fa54a7afe..28581a45c5 100644\n> --- a/git-compat-util.h\n> +++ b/git-compat-util.h\n> @@ -274,6 +274,17 @@ typedef unsigned long uintptr_t;\n>  #define _ALL_SOURCE 1\n>  #endif\n>  \n> +typedef union {\n> +\tuintmax_t max_align_uintmax;\n> +\tvoid *max_align_pointer;\n> +} git_max_align;\n> +\n> +typedef struct {\n> +\tchar unalign;\n> +\tgit_max_align aligned;\n> +} git_max_alignment;\n> +#define GIT_MAX_ALIGNMENT offsetof(git_max_alignment, aligned)\n> +\n>  /* used on Mac OS X */\n>  #ifdef PRECOMPOSE_UNICODE\n>  #include \"compat/precompose_utf8.h\"\n> diff --git a/mem-pool.c b/mem-pool.c\n> index ccdcad2e3d..748eff925a 100644\n> --- a/mem-pool.c\n> +++ b/mem-pool.c\n> @@ -69,9 +69,9 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len)\n>  \tstruct mp_block *p = NULL;\n>  \tvoid *r;\n>  \n> -\t/* round up to a 'uintmax_t' alignment */\n> -\tif (len & (sizeof(uintmax_t) - 1))\n> -\t\tlen += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));\n> +\t/* round up to a 'GIT_MAX_ALIGNMENT' alignment */\n> +\tif (len & (GIT_MAX_ALIGNMENT - 1))\n> +\t\tlen += GIT_MAX_ALIGNMENT - (len & (GIT_MAX_ALIGNMENT - 1));\n>  \n>  \tif (pool->mp_block &&\n>  \t    pool->mp_block->end - pool->mp_block->next_free >= len)\n\n"},{"id":"445722","messageId":"3b469866-3718-9f0e-419c-bdc793de18e9@web.de","threadId":"57187","inReplyTo":"20220105132324.6651-1-jrtc27@jrtc27.com","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-01-07T16:08:56Z","receivedAt":"2022-01-07T16:09:00Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 05.01.22 um 14:23 schrieb Jessica Clarke:\n> Currently git_qsort_s allocates a buffer on the stack that has no\n> alignment, and mem_pool_alloc assumes uintmax_t's size is adequate\n> alignment for any type.\n>\n> On CHERI, and thus Arm's Morello prototype, pointers are implemented as\n> hardware capabilities which, as well as having a normal integer address,\n> have additional bounds, permissions and other metadata in a second word,\n> so on a 64-bit architecture they are 128-bit quantities, including their\n> alignment requirements. Despite being 128-bit, their integer component\n> is still only a 64-bit field, so uintmax_t remains 64-bit, and therefore\n> uintmax_t does not sufficiently align an allocation.\n>\n> Moreover, these capabilities have an additional \"129th\" tag bit, which\n> tracks the validity of the capability and is cleared on any invalid\n> operation that doesn't trap (e.g. partially overwriting a capability\n> will invalidate it) which, combined with the architecture's strict\n> checks on capability manipulation instructions, ensures it is\n> architecturally impossible to construct a capability that gives more\n> rights than those you were given in the first place. To store these tag\n> bits, each capability sized and aligned word in memory gains a single\n> tag bit that is stored in unaddressable (to the processor) memory. This\n> means that it is impossible to store a capability at an unaligned\n> address: a normal load or store of a capability will always take an\n> alignment fault even if the (micro)architecture supports unaligned\n> loads/stores for other data types, and a memcpy will, if the destination\n> is not appropriately aligned, copy the byte representation but lose the\n> tag, meaning that if it is eventually copied back and loaded from an\n> aligned location any attempt to dereference it will trap with a tag\n> fault. Thus, even char buffers that are memcpy'ed to or from must be\n> properly aligned on CHERI architectures if they are to hold pointers.\n>\n> Address both of these by introducing a new git_max_align type put in a\n> union with the on-stack buffer to force its alignment, as well as a new\n> GIT_MAX_ALIGNMENT macro whose value is the alignment of git_max_align\n> that gets used for mem_pool_alloc. As well as making the code work on\n> CHERI, the former change likely also improves performance on some\n> architectures by making memcpy faster (either because it can use larger\n> block sizes or because the microarchitecture has inefficient unaligned\n> accesses).\n>\n> Signed-off-by: Jessica Clarke <jrtc27@jrtc27.com>\n> ---\n>  compat/qsort_s.c  | 11 +++++++----\n>  git-compat-util.h | 11 +++++++++++\n>  mem-pool.c        |  6 +++---\n>  3 files changed, 21 insertions(+), 7 deletions(-)\n>\n> diff --git a/compat/qsort_s.c b/compat/qsort_s.c\n> index 52d1f0a73d..1ccdb87451 100644\n> --- a/compat/qsort_s.c\n> +++ b/compat/qsort_s.c\n> @@ -49,16 +49,19 @@ int git_qsort_s(void *b, size_t n, size_t s,\n>  \t\tint (*cmp)(const void *, const void *, void *), void *ctx)\n>  {\n>  \tconst size_t size = st_mult(n, s);\n> -\tchar buf[1024];\n> +\tunion {\n> +\t\tchar buf[1024];\n> +\t\tgit_max_align align;\n> +\t} u;\n>\n>  \tif (!n)\n>  \t\treturn 0;\n>  \tif (!b || !cmp)\n>  \t\treturn -1;\n>\n> -\tif (size < sizeof(buf)) {\n> -\t\t/* The temporary array fits on the small on-stack buffer. */\n> -\t\tmsort_with_tmp(b, n, s, cmp, buf, ctx);\n> +\tif (size < sizeof(u.buf)) {\n> +\t\t/* The temporary array fits in the small on-stack buffer. */\n> +\t\tmsort_with_tmp(b, n, s, cmp, u.buf, ctx);\n\nSo buf gets maximum alignment instead of char alignment (i.e. none)\nbecause some callers use it to sort pointers, which need that on your\nplatform.  Makes sense.\n\n>  \t} else {\n>  \t\t/* It's somewhat large, so malloc it.  */\n>  \t\tchar *tmp = xmalloc(size);\n\ntmp is used instead of buf if the latter is not big enough, so it can\nalso contain pointers.  No problem, because malloc(3) returns memory\nthat is properly aligned for anything already.\n\n\nstable-qsort.c uses the same algorithm as compat/qsort_s.c, it just\nlacks the context pointer.  Shouldn't it get the same treatment?  It\nis used e.g. (via the macro STABLE_QSORT) in merge-ort.c to sort\npointers..\n\n> diff --git a/git-compat-util.h b/git-compat-util.h\n> index 5fa54a7afe..28581a45c5 100644\n> --- a/git-compat-util.h\n> +++ b/git-compat-util.h\n> @@ -274,6 +274,17 @@ typedef unsigned long uintptr_t;\n>  #define _ALL_SOURCE 1\n>  #endif\n>\n> +typedef union {\n> +\tuintmax_t max_align_uintmax;\n> +\tvoid *max_align_pointer;\n> +} git_max_align;\n\nFor your purposes just the void * member would suffice here, right?  And\nwith the added uintmax_t this currently gets maximum alignment, suitable\nfor any of our objects.  If we were to start using __int128 etc. then\nwe'd have to add that to this union as well to really get the maximum\npossible alignment, though.\n\n> +\n> +typedef struct {\n> +\tchar unalign;\n> +\tgit_max_align aligned;\n> +} git_max_alignment;\n> +#define GIT_MAX_ALIGNMENT offsetof(git_max_alignment, aligned)\n\nC11 has alignas, alignof and max_align_t.  We only recently started to\ndepend on some C99 features, so perhaps it's a bit early to use\nstdalign.h in Git's code base.  That's a pity, though.  The\nGIT_MAX_ALIGNMENT macro is sightly enough, but using a union to get\npointer alignment is a bit more cumbersome than something like\n\n\talignas(alignof(max_align_t)) char buf[1024];\n\n> +\n>  /* used on Mac OS X */\n>  #ifdef PRECOMPOSE_UNICODE\n>  #include \"compat/precompose_utf8.h\"\n> diff --git a/mem-pool.c b/mem-pool.c\n> index ccdcad2e3d..748eff925a 100644\n> --- a/mem-pool.c\n> +++ b/mem-pool.c\n> @@ -69,9 +69,9 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len)\n>  \tstruct mp_block *p = NULL;\n>  \tvoid *r;\n>\n> -\t/* round up to a 'uintmax_t' alignment */\n> -\tif (len & (sizeof(uintmax_t) - 1))\n> -\t\tlen += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));\n> +\t/* round up to a 'GIT_MAX_ALIGNMENT' alignment */\n> +\tif (len & (GIT_MAX_ALIGNMENT - 1))\n> +\t\tlen += GIT_MAX_ALIGNMENT - (len & (GIT_MAX_ALIGNMENT - 1));\n\nOK.\n\n>\n>  \tif (pool->mp_block &&\n>  \t    pool->mp_block->end - pool->mp_block->next_free >= len)\n\n"},{"id":"445724","messageId":"BDDA4F68-B9D4-4F8D-B7D2-C1DF3237F897@jrtc27.com","threadId":"57187","inReplyTo":"3b469866-3718-9f0e-419c-bdc793de18e9@web.de","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-07T16:21:47Z","receivedAt":"2022-01-07T16:21:51Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"On 7 Jan 2022, at 16:08, René Scharfe <l.s.r@web.de> wrote:\n> \n> Am 05.01.22 um 14:23 schrieb Jessica Clarke:\n>> Currently git_qsort_s allocates a buffer on the stack that has no\n>> alignment, and mem_pool_alloc assumes uintmax_t's size is adequate\n>> alignment for any type.\n>> \n>> On CHERI, and thus Arm's Morello prototype, pointers are implemented as\n>> hardware capabilities which, as well as having a normal integer address,\n>> have additional bounds, permissions and other metadata in a second word,\n>> so on a 64-bit architecture they are 128-bit quantities, including their\n>> alignment requirements. Despite being 128-bit, their integer component\n>> is still only a 64-bit field, so uintmax_t remains 64-bit, and therefore\n>> uintmax_t does not sufficiently align an allocation.\n>> \n>> Moreover, these capabilities have an additional \"129th\" tag bit, which\n>> tracks the validity of the capability and is cleared on any invalid\n>> operation that doesn't trap (e.g. partially overwriting a capability\n>> will invalidate it) which, combined with the architecture's strict\n>> checks on capability manipulation instructions, ensures it is\n>> architecturally impossible to construct a capability that gives more\n>> rights than those you were given in the first place. To store these tag\n>> bits, each capability sized and aligned word in memory gains a single\n>> tag bit that is stored in unaddressable (to the processor) memory. This\n>> means that it is impossible to store a capability at an unaligned\n>> address: a normal load or store of a capability will always take an\n>> alignment fault even if the (micro)architecture supports unaligned\n>> loads/stores for other data types, and a memcpy will, if the destination\n>> is not appropriately aligned, copy the byte representation but lose the\n>> tag, meaning that if it is eventually copied back and loaded from an\n>> aligned location any attempt to dereference it will trap with a tag\n>> fault. Thus, even char buffers that are memcpy'ed to or from must be\n>> properly aligned on CHERI architectures if they are to hold pointers.\n>> \n>> Address both of these by introducing a new git_max_align type put in a\n>> union with the on-stack buffer to force its alignment, as well as a new\n>> GIT_MAX_ALIGNMENT macro whose value is the alignment of git_max_align\n>> that gets used for mem_pool_alloc. As well as making the code work on\n>> CHERI, the former change likely also improves performance on some\n>> architectures by making memcpy faster (either because it can use larger\n>> block sizes or because the microarchitecture has inefficient unaligned\n>> accesses).\n>> \n>> Signed-off-by: Jessica Clarke <jrtc27@jrtc27.com>\n>> ---\n>> compat/qsort_s.c  | 11 +++++++----\n>> git-compat-util.h | 11 +++++++++++\n>> mem-pool.c        |  6 +++---\n>> 3 files changed, 21 insertions(+), 7 deletions(-)\n>> \n>> diff --git a/compat/qsort_s.c b/compat/qsort_s.c\n>> index 52d1f0a73d..1ccdb87451 100644\n>> --- a/compat/qsort_s.c\n>> +++ b/compat/qsort_s.c\n>> @@ -49,16 +49,19 @@ int git_qsort_s(void *b, size_t n, size_t s,\n>> \t\tint (*cmp)(const void *, const void *, void *), void *ctx)\n>> {\n>> \tconst size_t size = st_mult(n, s);\n>> -\tchar buf[1024];\n>> +\tunion {\n>> +\t\tchar buf[1024];\n>> +\t\tgit_max_align align;\n>> +\t} u;\n>> \n>> \tif (!n)\n>> \t\treturn 0;\n>> \tif (!b || !cmp)\n>> \t\treturn -1;\n>> \n>> -\tif (size < sizeof(buf)) {\n>> -\t\t/* The temporary array fits on the small on-stack buffer. */\n>> -\t\tmsort_with_tmp(b, n, s, cmp, buf, ctx);\n>> +\tif (size < sizeof(u.buf)) {\n>> +\t\t/* The temporary array fits in the small on-stack buffer. */\n>> +\t\tmsort_with_tmp(b, n, s, cmp, u.buf, ctx);\n> \n> So buf gets maximum alignment instead of char alignment (i.e. none)\n> because some callers use it to sort pointers, which need that on your\n> platform.  Makes sense.\n\nYes, exactly.\n\n>> \t} else {\n>> \t\t/* It's somewhat large, so malloc it.  */\n>> \t\tchar *tmp = xmalloc(size);\n> \n> tmp is used instead of buf if the latter is not big enough, so it can\n> also contain pointers.  No problem, because malloc(3) returns memory\n> that is properly aligned for anything already.\n\nYes.\n\n> stable-qsort.c uses the same algorithm as compat/qsort_s.c, it just\n> lacks the context pointer.  Shouldn't it get the same treatment?  It\n> is used e.g. (via the macro STABLE_QSORT) in merge-ort.c to sort\n> pointers..\n\nIndeed it should; I guess git_stable_qsort just isn’t used for most\ncommon commands, or at least not with structures containing pointers,\nas I haven’t seen it break yet.\n\n>> diff --git a/git-compat-util.h b/git-compat-util.h\n>> index 5fa54a7afe..28581a45c5 100644\n>> --- a/git-compat-util.h\n>> +++ b/git-compat-util.h\n>> @@ -274,6 +274,17 @@ typedef unsigned long uintptr_t;\n>> #define _ALL_SOURCE 1\n>> #endif\n>> \n>> +typedef union {\n>> +\tuintmax_t max_align_uintmax;\n>> +\tvoid *max_align_pointer;\n>> +} git_max_align;\n> \n> For your purposes just the void * member would suffice here, right?  And\n> with the added uintmax_t this currently gets maximum alignment, suitable\n> for any of our objects.  If we were to start using __int128 etc. then\n> we'd have to add that to this union as well to really get the maximum\n> possible alignment, though.\n\nFor us, yes, uintmax_t’s alignment is never greater than void *’s. On\nmost 32-bit non-CHERI architectures though that isn’t the case, so\nwhilst omitting uintmax_t would be fine for qsort, it would break\nmem_pool_alloc’s alignment, as this gets used for both. Plus aligning\nto uintmax_t may still help performance for memcpy there (e.g. maybe it\nguarantees the memcpy implementation can use a load/store pair\ninstruction that it wouldn’t otherwise necessarily be able to).\n\nRegarding __int128, yes, you would, though both GCC’s and FreeBSD’s\nstddef.h don’t admit __int128 exists. They do include long double in\ntheir max_align_t, though, which generally has the same alignment\nrequirements as __int128 on 64-bit architectures, though I have a funny\nfeeling it might not on some.\n\n>> +\n>> +typedef struct {\n>> +\tchar unalign;\n>> +\tgit_max_align aligned;\n>> +} git_max_alignment;\n>> +#define GIT_MAX_ALIGNMENT offsetof(git_max_alignment, aligned)\n> \n> C11 has alignas, alignof and max_align_t.  We only recently started to\n> depend on some C99 features, so perhaps it's a bit early to use\n> stdalign.h in Git's code base.  That's a pity, though.  The\n> GIT_MAX_ALIGNMENT macro is sightly enough, but using a union to get\n> pointer alignment is a bit more cumbersome than something like\n> \n> \talignas(alignof(max_align_t)) char buf[1024];\n\nIt is; max_align_t is our preferred solution and what our programming\nguide recommends, but not everyone is ready to jump to C11, so until\nthen various bodges like this are needed.\n\nJess\n\n>> +\n>> /* used on Mac OS X */\n>> #ifdef PRECOMPOSE_UNICODE\n>> #include \"compat/precompose_utf8.h\"\n>> diff --git a/mem-pool.c b/mem-pool.c\n>> index ccdcad2e3d..748eff925a 100644\n>> --- a/mem-pool.c\n>> +++ b/mem-pool.c\n>> @@ -69,9 +69,9 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len)\n>> \tstruct mp_block *p = NULL;\n>> \tvoid *r;\n>> \n>> -\t/* round up to a 'uintmax_t' alignment */\n>> -\tif (len & (sizeof(uintmax_t) - 1))\n>> -\t\tlen += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));\n>> +\t/* round up to a 'GIT_MAX_ALIGNMENT' alignment */\n>> +\tif (len & (GIT_MAX_ALIGNMENT - 1))\n>> +\t\tlen += GIT_MAX_ALIGNMENT - (len & (GIT_MAX_ALIGNMENT - 1));\n> \n> OK.\n> \n>> \n>> \tif (pool->mp_block &&\n>> \t    pool->mp_block->end - pool->mp_block->next_free >= len)\n\n"},{"id":"445736","messageId":"xmqq7dbb9wcz.fsf@gitster.g","threadId":"57187","inReplyTo":"Ydea3EO7wrYc9/Ij@camp.crustytoothpaste.net","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-07T19:30:52Z","receivedAt":"2022-01-07T19:30:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"brian m. carlson\" <sandals@crustytoothpaste.net> writes:\n\n> I'm not opposed to a small amount of finagling for this case, but I am\n> very much opposed to defining your C ABI in an intentionally difficult\n> way.\n\nI was looking at git_qsort_s() today and thought that its use of\n\"char buf[1k]\" on stack is something we would write for a system\nwithout alloca().\n\nWe already have xalloca() wrapper defined in the compat-util header.\nPerhaps it is a good idea to use it instead?\n\nBoth the true alloca() and xmalloc() we use as a fallback (when\n<alloca.h> is not available) are supposed to return a block of\nmemory that is suitably aligned for any use, no?  \n\n compat/qsort_s.c | 20 +++++++++++---------\n 1 file changed, 11 insertions(+), 9 deletions(-)\n\ndiff --git c/compat/qsort_s.c w/compat/qsort_s.c\nindex 52d1f0a73d..63660a4304 100644\n--- c/compat/qsort_s.c\n+++ w/compat/qsort_s.c\n@@ -49,21 +49,23 @@ int git_qsort_s(void *b, size_t n, size_t s,\n \t\tint (*cmp)(const void *, const void *, void *), void *ctx)\n {\n \tconst size_t size = st_mult(n, s);\n-\tchar buf[1024];\n+\tchar *tmp;\n+\tint use_alloca;\n \n \tif (!n)\n \t\treturn 0;\n \tif (!b || !cmp)\n \t\treturn -1;\n \n-\tif (size < sizeof(buf)) {\n-\t\t/* The temporary array fits on the small on-stack buffer. */\n-\t\tmsort_with_tmp(b, n, s, cmp, buf, ctx);\n-\t} else {\n-\t\t/* It's somewhat large, so malloc it.  */\n-\t\tchar *tmp = xmalloc(size);\n-\t\tmsort_with_tmp(b, n, s, cmp, tmp, ctx);\n+\tuse_alloca = (size < 1024);\n+\n+\ttmp = use_alloca ? xalloca(size) : xmalloc(size);\n+\n+\tmsort_with_tmp(b, n, s, cmp, tmp, ctx);\n+\n+\tif (use_alloca)\n+\t\txalloca_free(tmp);\n+\telse\n \t\tfree(tmp);\n-\t}\n \treturn 0;\n }\n"},{"id":"445738","messageId":"70126D1C-37EC-42CC-B830-9730E6D43156@jrtc27.com","threadId":"57187","inReplyTo":"xmqq7dbb9wcz.fsf@gitster.g","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-07T19:33:56Z","receivedAt":"2022-01-07T19:34:00Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"On 7 Jan 2022, at 19:30, Junio C Hamano <gitster@pobox.com> wrote:\n> \n> \"brian m. carlson\" <sandals@crustytoothpaste.net> writes:\n> \n>> I'm not opposed to a small amount of finagling for this case, but I am\n>> very much opposed to defining your C ABI in an intentionally difficult\n>> way.\n> \n> I was looking at git_qsort_s() today and thought that its use of\n> \"char buf[1k]\" on stack is something we would write for a system\n> without alloca().\n> \n> We already have xalloca() wrapper defined in the compat-util header.\n> Perhaps it is a good idea to use it instead?\n> \n> Both the true alloca() and xmalloc() we use as a fallback (when\n> <alloca.h> is not available) are supposed to return a block of\n> memory that is suitably aligned for any use, no?  \n\nYes; I initially considered using it, but didn’t in case the fact that\nxalloca falls back on malloc when alloca doesn’t exist was considered a\nregression. If that’s acceptable then xalloca avoids the issue entirely\nand it’s just the mem pool allocator that needs some notion of max\nalignment that isn’t just uintmax_t in order to support CHERI.\n\nJess\n\n> compat/qsort_s.c | 20 +++++++++++---------\n> 1 file changed, 11 insertions(+), 9 deletions(-)\n> \n> diff --git c/compat/qsort_s.c w/compat/qsort_s.c\n> index 52d1f0a73d..63660a4304 100644\n> --- c/compat/qsort_s.c\n> +++ w/compat/qsort_s.c\n> @@ -49,21 +49,23 @@ int git_qsort_s(void *b, size_t n, size_t s,\n> \t\tint (*cmp)(const void *, const void *, void *), void *ctx)\n> {\n> \tconst size_t size = st_mult(n, s);\n> -\tchar buf[1024];\n> +\tchar *tmp;\n> +\tint use_alloca;\n> \n> \tif (!n)\n> \t\treturn 0;\n> \tif (!b || !cmp)\n> \t\treturn -1;\n> \n> -\tif (size < sizeof(buf)) {\n> -\t\t/* The temporary array fits on the small on-stack buffer. */\n> -\t\tmsort_with_tmp(b, n, s, cmp, buf, ctx);\n> -\t} else {\n> -\t\t/* It's somewhat large, so malloc it.  */\n> -\t\tchar *tmp = xmalloc(size);\n> -\t\tmsort_with_tmp(b, n, s, cmp, tmp, ctx);\n> +\tuse_alloca = (size < 1024);\n> +\n> +\ttmp = use_alloca ? xalloca(size) : xmalloc(size);\n> +\n> +\tmsort_with_tmp(b, n, s, cmp, tmp, ctx);\n> +\n> +\tif (use_alloca)\n> +\t\txalloca_free(tmp);\n> +\telse\n> \t\tfree(tmp);\n> -\t}\n> \treturn 0;\n> }\n\n"},{"id":"445746","messageId":"40077881-e91a-dfba-5950-cdc03719264d@web.de","threadId":"57187","inReplyTo":"xmqq7dbb9wcz.fsf@gitster.g","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-01-07T20:56:49Z","receivedAt":"2022-01-07T20:57:02Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 07.01.22 um 20:30 schrieb Junio C Hamano:\n> \"brian m. carlson\" <sandals@crustytoothpaste.net> writes:\n>\n>> I'm not opposed to a small amount of finagling for this case, but I am\n>> very much opposed to defining your C ABI in an intentionally difficult\n>> way.\n>\n> I was looking at git_qsort_s() today and thought that its use of\n> \"char buf[1k]\" on stack is something we would write for a system\n> without alloca().\n>\n> We already have xalloca() wrapper defined in the compat-util header.\n> Perhaps it is a good idea to use it instead?\n>\n> Both the true alloca() and xmalloc() we use as a fallback (when\n> <alloca.h> is not available) are supposed to return a block of\n> memory that is suitably aligned for any use, no?\n\nIf falling back to malloc(3) is fine in general then I wonder if we can\njust it use always.  This would save two branches and make buffer\nmanagement trivial here.  How much worse is malloc(3) on platforms with\nalloca(3)?  Do we sort lots of short lists somewhere?  In other words:\nDoes this stack allocation optimization actually make a measurable\ndifference?\n\nHeap fragmention should not be a concern here, at least, because the\npattern of requesting, using and releasing a single allocation won't\nleave holes.\n\n>\n>  compat/qsort_s.c | 20 +++++++++++---------\n>  1 file changed, 11 insertions(+), 9 deletions(-)\n>\n> diff --git c/compat/qsort_s.c w/compat/qsort_s.c\n> index 52d1f0a73d..63660a4304 100644\n> --- c/compat/qsort_s.c\n> +++ w/compat/qsort_s.c\n> @@ -49,21 +49,23 @@ int git_qsort_s(void *b, size_t n, size_t s,\n>  \t\tint (*cmp)(const void *, const void *, void *), void *ctx)\n>  {\n>  \tconst size_t size = st_mult(n, s);\n> -\tchar buf[1024];\n> +\tchar *tmp;\n> +\tint use_alloca;\n>\n>  \tif (!n)\n>  \t\treturn 0;\n>  \tif (!b || !cmp)\n>  \t\treturn -1;\n>\n> -\tif (size < sizeof(buf)) {\n> -\t\t/* The temporary array fits on the small on-stack buffer. */\n> -\t\tmsort_with_tmp(b, n, s, cmp, buf, ctx);\n> -\t} else {\n> -\t\t/* It's somewhat large, so malloc it.  */\n> -\t\tchar *tmp = xmalloc(size);\n> -\t\tmsort_with_tmp(b, n, s, cmp, tmp, ctx);\n> +\tuse_alloca = (size < 1024);\n> +\n> +\ttmp = use_alloca ? xalloca(size) : xmalloc(size);\n> +\n> +\tmsort_with_tmp(b, n, s, cmp, tmp, ctx);\n> +\n> +\tif (use_alloca)\n> +\t\txalloca_free(tmp);\n> +\telse\n>  \t\tfree(tmp);\n> -\t}\n>  \treturn 0;\n>  }\n"},{"id":"445749","messageId":"xmqqzgo76xpj.fsf@gitster.g","threadId":"57187","inReplyTo":"40077881-e91a-dfba-5950-cdc03719264d@web.de","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-07T21:30:00Z","receivedAt":"2022-01-07T21:30:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <l.s.r@web.de> writes:\n\n> If falling back to malloc(3) is fine in general then I wonder if we can\n> just it use always.  This would save two branches and make buffer\n> management trivial here.  How much worse is malloc(3) on platforms with\n> alloca(3)?  Do we sort lots of short lists somewhere?  In other words:\n> Does this stack allocation optimization actually make a measurable\n> difference?\n\nWell all the preimage of this came from your 04ee8b87 (compat: add\nqsort_s(), 2017-01-22), so you tell me ;-)\n\n> Heap fragmention should not be a concern here, at least, because the\n> pattern of requesting, using and releasing a single allocation won't\n> leave holes.\n\nSure.  Even in a multi-threaded environment that should be true.\n\n----- >8 --------- >8 --------- >8 --------- >8 --------- >8 -----\nSubject: compat/qsort_s.c: avoid using potentially unaligned access\n\nThe compatibility definition for qsort_s() uses \"char buffer[1024]\"\non the stack to avoid making malloc() calls for small temporary\nspace, which essentially hand-rolls alloca().\n\nBut the elements of the array being sorted may have alignment needs\nmore strict than what an array of bytes may have. &buf[0] may be\nword aligned, but using the address as if it stores the first\nelement of an array of a struct, whose first member may need to be\naligned on double-word boundary, would be a no-no.\n\nWe could use xalloca() from git-compat-util.h, or alloca() directly\non platforms with HAVE_ALLOCA_H, but let's try using unconditionally\nxmalloc() before we know the performance characteristics of the\ncallers.\n\nIt may not make much of an argument to inspect the current callers\nand say \"it shouldn't matter to any of them\", but anyway:\n\n * The one in object-name.c is used to sort potential matches to a\n   given ambiguous object name prefix in the error path;\n\n * The one in pack-write.c is done once per a pack .idx file being\n   written to create the reverse index, so (1) the cost of malloc()\n   overhead is dwarfed by the cost of the packing operation, and (2)\n   the number of entries being sorted is the number of objects in a\n   pack;\n\n * The one in ref-filter.c is used by \"branch --list\", \"tag --list\",\n   and \"for-each-ref\", only once per operation.  We sort an array of\n   pointers with entries, each corresponding to a ref that is shown.\n\n * The one in string-list.c is used by sort_string_list(), which is\n   way too generic to assume any access patterns, so it may or may\n   not matter, but I do not care too much ;-)\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n compat/qsort_s.c | 14 ++++----------\n 1 file changed, 4 insertions(+), 10 deletions(-)\n\ndiff --git c/compat/qsort_s.c w/compat/qsort_s.c\nindex 52d1f0a73d..0f7ff30f5f 100644\n--- c/compat/qsort_s.c\n+++ w/compat/qsort_s.c\n@@ -49,21 +49,15 @@ int git_qsort_s(void *b, size_t n, size_t s,\n \t\tint (*cmp)(const void *, const void *, void *), void *ctx)\n {\n \tconst size_t size = st_mult(n, s);\n-\tchar buf[1024];\n+\tchar *tmp;\n \n \tif (!n)\n \t\treturn 0;\n \tif (!b || !cmp)\n \t\treturn -1;\n \n-\tif (size < sizeof(buf)) {\n-\t\t/* The temporary array fits on the small on-stack buffer. */\n-\t\tmsort_with_tmp(b, n, s, cmp, buf, ctx);\n-\t} else {\n-\t\t/* It's somewhat large, so malloc it.  */\n-\t\tchar *tmp = xmalloc(size);\n-\t\tmsort_with_tmp(b, n, s, cmp, tmp, ctx);\n-\t\tfree(tmp);\n-\t}\n+\ttmp = xmalloc(size);\n+\tmsort_with_tmp(b, n, s, cmp, tmp, ctx);\n+\tfree(tmp);\n \treturn 0;\n }\n"},{"id":"445762","messageId":"f40c1b47-9aad-2dcc-ceeb-5dee2b517cd8@web.de","threadId":"57187","inReplyTo":"xmqqzgo76xpj.fsf@gitster.g","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-01-07T23:30:44Z","receivedAt":"2022-01-07T23:31:02Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 07.01.22 um 22:30 schrieb Junio C Hamano:\n> René Scharfe <l.s.r@web.de> writes:\n>\n>> If falling back to malloc(3) is fine in general then I wonder if we can\n>> just it use always.  This would save two branches and make buffer\n>> management trivial here.  How much worse is malloc(3) on platforms with\n>> alloca(3)?  Do we sort lots of short lists somewhere?  In other words:\n>> Does this stack allocation optimization actually make a measurable\n>> difference?\n>\n> Well all the preimage of this came from your 04ee8b87 (compat: add\n> qsort_s(), 2017-01-22), so you tell me ;-)\n\nRight, except I stole the code almost verbatim from compat/qsort.c,\nwhich had this optimization since 43fe901b71 (compat: Add simplified\nmerge sort implementation from glibc, 2008-02-05).  :)  The\noptimization may have raised my eyebrow a bit at the time, but not\nenough to come up with a meaningful benchmark..\n\nhttps://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/msort.c (the\noriginal) still uses alloca(3) (and more tricks), by the way;\nhttps://cgit.freebsd.org/src/tree/lib/libc/stdlib/merge.c still\ndoesn't.\n\n>\n>> Heap fragmention should not be a concern here, at least, because the\n>> pattern of requesting, using and releasing a single allocation won't\n>> leave holes.\n>\n> Sure.  Even in a multi-threaded environment that should be true.\n>\n> ----- >8 --------- >8 --------- >8 --------- >8 --------- >8 -----\n> Subject: compat/qsort_s.c: avoid using potentially unaligned access\n>\n> The compatibility definition for qsort_s() uses \"char buffer[1024]\"\n> on the stack to avoid making malloc() calls for small temporary\n> space, which essentially hand-rolls alloca().\n>\n> But the elements of the array being sorted may have alignment needs\n> more strict than what an array of bytes may have. &buf[0] may be\n> word aligned, but using the address as if it stores the first\n> element of an array of a struct, whose first member may need to be\n> aligned on double-word boundary, would be a no-no.\n>\n> We could use xalloca() from git-compat-util.h, or alloca() directly\n> on platforms with HAVE_ALLOCA_H, but let's try using unconditionally\n> xmalloc() before we know the performance characteristics of the\n> callers.\n>\n> It may not make much of an argument to inspect the current callers\n> and say \"it shouldn't matter to any of them\", but anyway:\n>\n>  * The one in object-name.c is used to sort potential matches to a\n>    given ambiguous object name prefix in the error path;\n>\n>  * The one in pack-write.c is done once per a pack .idx file being\n>    written to create the reverse index, so (1) the cost of malloc()\n>    overhead is dwarfed by the cost of the packing operation, and (2)\n>    the number of entries being sorted is the number of objects in a\n>    pack;\n>\n>  * The one in ref-filter.c is used by \"branch --list\", \"tag --list\",\n>    and \"for-each-ref\", only once per operation.  We sort an array of\n>    pointers with entries, each corresponding to a ref that is shown.\n>\n>  * The one in string-list.c is used by sort_string_list(), which is\n>    way too generic to assume any access patterns, so it may or may\n>    not matter, but I do not care too much ;-)\n>\n> Signed-off-by: Junio C Hamano <gitster@pobox.com>\n> ---\n>  compat/qsort_s.c | 14 ++++----------\n>  1 file changed, 4 insertions(+), 10 deletions(-)\n>\n> diff --git c/compat/qsort_s.c w/compat/qsort_s.c\n> index 52d1f0a73d..0f7ff30f5f 100644\n> --- c/compat/qsort_s.c\n> +++ w/compat/qsort_s.c\n> @@ -49,21 +49,15 @@ int git_qsort_s(void *b, size_t n, size_t s,\n>  \t\tint (*cmp)(const void *, const void *, void *), void *ctx)\n>  {\n>  \tconst size_t size = st_mult(n, s);\n> -\tchar buf[1024];\n> +\tchar *tmp;\n>\n>  \tif (!n)\n>  \t\treturn 0;\n>  \tif (!b || !cmp)\n>  \t\treturn -1;\n>\n> -\tif (size < sizeof(buf)) {\n> -\t\t/* The temporary array fits on the small on-stack buffer. */\n> -\t\tmsort_with_tmp(b, n, s, cmp, buf, ctx);\n> -\t} else {\n> -\t\t/* It's somewhat large, so malloc it.  */\n> -\t\tchar *tmp = xmalloc(size);\n> -\t\tmsort_with_tmp(b, n, s, cmp, tmp, ctx);\n> -\t\tfree(tmp);\n> -\t}\n> +\ttmp = xmalloc(size);\n> +\tmsort_with_tmp(b, n, s, cmp, tmp, ctx);\n> +\tfree(tmp);\n>  \treturn 0;\n>  }\n\n--- >8 ---\nSubject: [PATCH] stable-qsort: avoid using potentially unaligned access\n\nLike in the previous patch for compat/qsort_s.c, remove the optimization\nof using an on-stack buffer to avoid small allocations.  This ensures\nmaximum alignment for the array elements and simplifies the code a bit.\n\nThe performance impact for the current callers is unlikely to be\nnoticeable:\n\n * compat/mingw.c::make_environment_block() uses ALLOC_ARRAY and\n   ALLOC_GROW several times already, so another allocation of up to 1KB\n   should not matter much.\n\n * diffcore-rename.c::diffcore_rename_extended() is called once per diff\n   or twice per merge, and those require allocations for each object and\n   more already.\n\n * merge-ort.c::detect_and_process_renames() is called once per merge.\n   It's responsible for the two per-merge diffcore_rename_extended()\n   calls mentioned above as well, though.  So this is possibly the most\n   impacted caller.  Per-object allocations are likely to dwarf the\n   additional small allocations in git_stable_qsort(), though.\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n stable-qsort.c | 16 +++++-----------\n 1 file changed, 5 insertions(+), 11 deletions(-)\n\ndiff --git a/stable-qsort.c b/stable-qsort.c\nindex 6cbaf39f7b..7ff12467cd 100644\n--- a/stable-qsort.c\n+++ b/stable-qsort.c\n@@ -48,15 +48,9 @@ void git_stable_qsort(void *b, size_t n, size_t s,\n \t\t      int (*cmp)(const void *, const void *))\n {\n \tconst size_t size = st_mult(n, s);\n-\tchar buf[1024];\n-\n-\tif (size < sizeof(buf)) {\n-\t\t/* The temporary array fits on the small on-stack buffer. */\n-\t\tmsort_with_tmp(b, n, s, cmp, buf);\n-\t} else {\n-\t\t/* It's somewhat large, so malloc it.  */\n-\t\tchar *tmp = xmalloc(size);\n-\t\tmsort_with_tmp(b, n, s, cmp, tmp);\n-\t\tfree(tmp);\n-\t}\n+\tchar *tmp;\n+\n+\ttmp = xmalloc(size);\n+\tmsort_with_tmp(b, n, s, cmp, tmp);\n+\tfree(tmp);\n }\n--\n2.34.1\n\n\n"},{"id":"445764","messageId":"CABPp-BG3rwC2fy-1fu0GwzofUjaF2HbJOC79BNBHxSoVS-vNAQ@mail.gmail.com","threadId":"57187","inReplyTo":"f40c1b47-9aad-2dcc-ceeb-5dee2b517cd8@web.de","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-01-08T00:18:10Z","receivedAt":"2022-01-08T00:18:25Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Jan 7, 2022 at 3:30 PM René Scharfe <l.s.r@web.de> wrote:\n>\n...\n> --- >8 ---\n> Subject: [PATCH] stable-qsort: avoid using potentially unaligned access\n>\n> Like in the previous patch for compat/qsort_s.c, remove the optimization\n> of using an on-stack buffer to avoid small allocations.  This ensures\n> maximum alignment for the array elements and simplifies the code a bit.\n>\n> The performance impact for the current callers is unlikely to be\n> noticeable:\n>\n>  * compat/mingw.c::make_environment_block() uses ALLOC_ARRAY and\n>    ALLOC_GROW several times already, so another allocation of up to 1KB\n>    should not matter much.\n\nNot familiar with this code, but that makes sense to me.\n\n>  * diffcore-rename.c::diffcore_rename_extended() is called once per diff\n>    or twice per merge, and those require allocations for each object and\n>    more already.\n\nActually, this sort could be skipped entirely if it can determine all\nrenames early (either because they are found via exact matches, or\nthey aren't relevant for the merge result, or they are found via\nbasename comparisons).  This sort is only called when we have to\nresort to the full quadratic pairwise comparisons between files, in\nwhich case we're also slurping in full files, doing the diffcore-delta\nwork to convert each file's contents into a spanhash, and then\npairwise comparing spanhashes for every pairing of source &\ndestination files that remain.  That work would absolutely dwarf the\nmalloc of a kilobyte.  So I agree, it's not worth worrying about this\none.\n\n>  * merge-ort.c::detect_and_process_renames() is called once per merge.\n>    It's responsible for the two per-merge diffcore_rename_extended()\n>    calls mentioned above as well, though.  So this is possibly the most\n>    impacted caller.  Per-object allocations are likely to dwarf the\n>    additional small allocations in git_stable_qsort(), though.\n\nThe particular sort call directly found in\ndetect_and_process_renames() was once nearly 30% of overall execution\ntime in merge-ort[1], but according to some local notes I kept, it\neventually dropped to about ~1% of overall execution time after\ntrivial directory resolution[2] (due to the fact that it could just\ninclude some higher level directories and omit all the files\nunderneath them -- i.e. it had far fewer paths to sort).\n\nSince I suspect your change here would generally just be a small\npercentage of the overall git_stable_qsort() time (if it can even be\nmeasured), and git_stable_qsort() time is a small percentage of\nmerge-ort runtime, I think any runtime differences here would be\nnegligible.\n\n[1] https://lore.kernel.org/git/140c1e89e0ec69c5c5e8a99b632c1cf25c2325d4.1623168703.git.gitgitgadget@gmail.com/\n[2] https://lore.kernel.org/git/pull.988.v4.git.1626841444.gitgitgadget@gmail.com/\n\n>\n> Signed-off-by: René Scharfe <l.s.r@web.de>\n> ---\n>  stable-qsort.c | 16 +++++-----------\n>  1 file changed, 5 insertions(+), 11 deletions(-)\n>\n> diff --git a/stable-qsort.c b/stable-qsort.c\n> index 6cbaf39f7b..7ff12467cd 100644\n> --- a/stable-qsort.c\n> +++ b/stable-qsort.c\n> @@ -48,15 +48,9 @@ void git_stable_qsort(void *b, size_t n, size_t s,\n>                       int (*cmp)(const void *, const void *))\n>  {\n>         const size_t size = st_mult(n, s);\n> -       char buf[1024];\n> -\n> -       if (size < sizeof(buf)) {\n> -               /* The temporary array fits on the small on-stack buffer. */\n> -               msort_with_tmp(b, n, s, cmp, buf);\n> -       } else {\n> -               /* It's somewhat large, so malloc it.  */\n> -               char *tmp = xmalloc(size);\n> -               msort_with_tmp(b, n, s, cmp, tmp);\n> -               free(tmp);\n> -       }\n> +       char *tmp;\n> +\n> +       tmp = xmalloc(size);\n> +       msort_with_tmp(b, n, s, cmp, tmp);\n> +       free(tmp);\n>  }\n> --\n> 2.34.1\n\nPatch looks good to me.  Reviewed-by: Elijah Newren <newren@gmail.com>\n"},{"id":"446024","messageId":"641A33F3-E98A-40B1-BB11-ADC8C1FECA75@jrtc27.com","threadId":"57187","inReplyTo":"20220105132324.6651-1-jrtc27@jrtc27.com","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-12T13:58:38Z","receivedAt":"2022-01-12T13:58:44Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"On 5 Jan 2022, at 13:23, Jessica Clarke <jrtc27@jrtc27.com> wrote:\n> \n> Currently git_qsort_s allocates a buffer on the stack that has no\n> alignment, and mem_pool_alloc assumes uintmax_t's size is adequate\n> alignment for any type.\n> \n> On CHERI, and thus Arm's Morello prototype, pointers are implemented as\n> hardware capabilities which, as well as having a normal integer address,\n> have additional bounds, permissions and other metadata in a second word,\n> so on a 64-bit architecture they are 128-bit quantities, including their\n> alignment requirements. Despite being 128-bit, their integer component\n> is still only a 64-bit field, so uintmax_t remains 64-bit, and therefore\n> uintmax_t does not sufficiently align an allocation.\n> \n> Moreover, these capabilities have an additional \"129th\" tag bit, which\n> tracks the validity of the capability and is cleared on any invalid\n> operation that doesn't trap (e.g. partially overwriting a capability\n> will invalidate it) which, combined with the architecture's strict\n> checks on capability manipulation instructions, ensures it is\n> architecturally impossible to construct a capability that gives more\n> rights than those you were given in the first place. To store these tag\n> bits, each capability sized and aligned word in memory gains a single\n> tag bit that is stored in unaddressable (to the processor) memory. This\n> means that it is impossible to store a capability at an unaligned\n> address: a normal load or store of a capability will always take an\n> alignment fault even if the (micro)architecture supports unaligned\n> loads/stores for other data types, and a memcpy will, if the destination\n> is not appropriately aligned, copy the byte representation but lose the\n> tag, meaning that if it is eventually copied back and loaded from an\n> aligned location any attempt to dereference it will trap with a tag\n> fault. Thus, even char buffers that are memcpy'ed to or from must be\n> properly aligned on CHERI architectures if they are to hold pointers.\n> \n> Address both of these by introducing a new git_max_align type put in a\n> union with the on-stack buffer to force its alignment, as well as a new\n> GIT_MAX_ALIGNMENT macro whose value is the alignment of git_max_align\n> that gets used for mem_pool_alloc. As well as making the code work on\n> CHERI, the former change likely also improves performance on some\n> architectures by making memcpy faster (either because it can use larger\n> block sizes or because the microarchitecture has inefficient unaligned\n> accesses).\n> \n> Signed-off-by: Jessica Clarke <jrtc27@jrtc27.com>\n> ---\n> compat/qsort_s.c  | 11 +++++++----\n> git-compat-util.h | 11 +++++++++++\n> mem-pool.c        |  6 +++---\n> 3 files changed, 21 insertions(+), 7 deletions(-)\n\nI can see the alternative fixes for qsort are now in next, as is the\ncleanup of register_symlink_changes to use string sets, which just\nleaves the mem-pool.c change to not assume that uintmax_t is\nsufficiently aligned for every type that git will use. If I move\nGIT_MAX_ALIGNMENT and its helper aggregates to mem-pool.c would that be\nacceptable?\n\nJess\n\n> diff --git a/compat/qsort_s.c b/compat/qsort_s.c\n> index 52d1f0a73d..1ccdb87451 100644\n> --- a/compat/qsort_s.c\n> +++ b/compat/qsort_s.c\n> @@ -49,16 +49,19 @@ int git_qsort_s(void *b, size_t n, size_t s,\n> \t\tint (*cmp)(const void *, const void *, void *), void *ctx)\n> {\n> \tconst size_t size = st_mult(n, s);\n> -\tchar buf[1024];\n> +\tunion {\n> +\t\tchar buf[1024];\n> +\t\tgit_max_align align;\n> +\t} u;\n> \n> \tif (!n)\n> \t\treturn 0;\n> \tif (!b || !cmp)\n> \t\treturn -1;\n> \n> -\tif (size < sizeof(buf)) {\n> -\t\t/* The temporary array fits on the small on-stack buffer. */\n> -\t\tmsort_with_tmp(b, n, s, cmp, buf, ctx);\n> +\tif (size < sizeof(u.buf)) {\n> +\t\t/* The temporary array fits in the small on-stack buffer. */\n> +\t\tmsort_with_tmp(b, n, s, cmp, u.buf, ctx);\n> \t} else {\n> \t\t/* It's somewhat large, so malloc it.  */\n> \t\tchar *tmp = xmalloc(size);\n> diff --git a/git-compat-util.h b/git-compat-util.h\n> index 5fa54a7afe..28581a45c5 100644\n> --- a/git-compat-util.h\n> +++ b/git-compat-util.h\n> @@ -274,6 +274,17 @@ typedef unsigned long uintptr_t;\n> #define _ALL_SOURCE 1\n> #endif\n> \n> +typedef union {\n> +\tuintmax_t max_align_uintmax;\n> +\tvoid *max_align_pointer;\n> +} git_max_align;\n> +\n> +typedef struct {\n> +\tchar unalign;\n> +\tgit_max_align aligned;\n> +} git_max_alignment;\n> +#define GIT_MAX_ALIGNMENT offsetof(git_max_alignment, aligned)\n> +\n> /* used on Mac OS X */\n> #ifdef PRECOMPOSE_UNICODE\n> #include \"compat/precompose_utf8.h\"\n> diff --git a/mem-pool.c b/mem-pool.c\n> index ccdcad2e3d..748eff925a 100644\n> --- a/mem-pool.c\n> +++ b/mem-pool.c\n> @@ -69,9 +69,9 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len)\n> \tstruct mp_block *p = NULL;\n> \tvoid *r;\n> \n> -\t/* round up to a 'uintmax_t' alignment */\n> -\tif (len & (sizeof(uintmax_t) - 1))\n> -\t\tlen += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));\n> +\t/* round up to a 'GIT_MAX_ALIGNMENT' alignment */\n> +\tif (len & (GIT_MAX_ALIGNMENT - 1))\n> +\t\tlen += GIT_MAX_ALIGNMENT - (len & (GIT_MAX_ALIGNMENT - 1));\n> \n> \tif (pool->mp_block &&\n> \t    pool->mp_block->end - pool->mp_block->next_free >= len)\n> -- \n> 2.33.1\n> \n\n"},{"id":"446029","messageId":"c4de043e-45e1-6066-37d5-6b06b7a820f7@web.de","threadId":"57187","inReplyTo":"641A33F3-E98A-40B1-BB11-ADC8C1FECA75@jrtc27.com","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2022-01-12T15:47:10Z","receivedAt":"2022-01-12T15:47:14Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 12.01.22 um 14:58 schrieb Jessica Clarke:\n>\n> I can see the alternative fixes for qsort are now in next, as is the\n> cleanup of register_symlink_changes to use string sets, which just\n> leaves the mem-pool.c change to not assume that uintmax_t is\n> sufficiently aligned for every type that git will use. If I move\n> GIT_MAX_ALIGNMENT and its helper aggregates to mem-pool.c would that be\n> acceptable?\n\nDefining it at its single site of use sounds like a good idea to me.\nWe can export it to git-compat-util.h later, iff necessary.\n\n>> diff --git a/git-compat-util.h b/git-compat-util.h\n>> index 5fa54a7afe..28581a45c5 100644\n>> --- a/git-compat-util.h\n>> +++ b/git-compat-util.h\n>> @@ -274,6 +274,17 @@ typedef unsigned long uintptr_t;\n>> #define _ALL_SOURCE 1\n>> #endif\n>>\n>> +typedef union {\n>> +\tuintmax_t max_align_uintmax;\n>> +\tvoid *max_align_pointer;\n>> +} git_max_align;\n>> +\n>> +typedef struct {\n>> +\tchar unalign;\n>> +\tgit_max_align aligned;\n>> +} git_max_alignment;\n>> +#define GIT_MAX_ALIGNMENT offsetof(git_max_alignment, aligned)\n\nStyle nit: We tend to use typedef sparingly.  And the union type doesn't\neven need a name.  E.g. this would work as well, while reducing the name\nspace footprint:\n\n   struct git_max_alignment {\n      char unalign;\n      union {\n         uintmax_t max_align_uintmax;\n         void *max_align_pointer;\n      } aligned;\n   };\n   #define GIT_MAX_ALIGNMENT offsetof(struct git_max_alignment, aligned)\n\nWhen someone uses a mempool for objects that requires 128-bit alignment\n(e.g. because it includes a long double or uint128_t member) then we'd\nneed add long double to the union as well, like e.g. compat/obstack.c\ndoes.  That would be the safe route, but currently only add 8 bytes of\nunnecessary overhead to each allocation.\n\nPerhaps mempool alignment should be configurable.  For now a comment\nmight suffice which indicates that GIT_MAX_ALIGNMENT is only the\nmaximum alignment requirement of current mempool users, not the\nhighest possible requirement for the machine.  Renaming it to something\nwith MEMPOOL in the name would help in this regard as well.\n\n>> +\n>> /* used on Mac OS X */\n>> #ifdef PRECOMPOSE_UNICODE\n>> #include \"compat/precompose_utf8.h\"\n>> diff --git a/mem-pool.c b/mem-pool.c\n>> index ccdcad2e3d..748eff925a 100644\n>> --- a/mem-pool.c\n>> +++ b/mem-pool.c\n>> @@ -69,9 +69,9 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len)\n>> \tstruct mp_block *p = NULL;\n>> \tvoid *r;\n>>\n>> -\t/* round up to a 'uintmax_t' alignment */\n>> -\tif (len & (sizeof(uintmax_t) - 1))\n>> -\t\tlen += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));\n>> +\t/* round up to a 'GIT_MAX_ALIGNMENT' alignment */\n>> +\tif (len & (GIT_MAX_ALIGNMENT - 1))\n>> +\t\tlen += GIT_MAX_ALIGNMENT - (len & (GIT_MAX_ALIGNMENT - 1));\n>>\n>> \tif (pool->mp_block &&\n>> \t    pool->mp_block->end - pool->mp_block->next_free >= len)\n>> --\n>> 2.33.1\n>>\n>\n\n"},{"id":"446030","messageId":"366952CA-95D1-4912-9E93-1178247AF173@jrtc27.com","threadId":"57187","inReplyTo":"c4de043e-45e1-6066-37d5-6b06b7a820f7@web.de","subject":"Re: [PATCH] Properly align memory allocations and temporary buffers","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-12T15:49:09Z","receivedAt":"2022-01-12T15:49:21Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"On 12 Jan 2022, at 15:47, René Scharfe <l.s.r@web.de> wrote:\n> \n> Am 12.01.22 um 14:58 schrieb Jessica Clarke:\n>> \n>> I can see the alternative fixes for qsort are now in next, as is the\n>> cleanup of register_symlink_changes to use string sets, which just\n>> leaves the mem-pool.c change to not assume that uintmax_t is\n>> sufficiently aligned for every type that git will use. If I move\n>> GIT_MAX_ALIGNMENT and its helper aggregates to mem-pool.c would that be\n>> acceptable?\n> \n> Defining it at its single site of use sounds like a good idea to me.\n> We can export it to git-compat-util.h later, iff necessary.\n> \n>>> diff --git a/git-compat-util.h b/git-compat-util.h\n>>> index 5fa54a7afe..28581a45c5 100644\n>>> --- a/git-compat-util.h\n>>> +++ b/git-compat-util.h\n>>> @@ -274,6 +274,17 @@ typedef unsigned long uintptr_t;\n>>> #define _ALL_SOURCE 1\n>>> #endif\n>>> \n>>> +typedef union {\n>>> +\tuintmax_t max_align_uintmax;\n>>> +\tvoid *max_align_pointer;\n>>> +} git_max_align;\n>>> +\n>>> +typedef struct {\n>>> +\tchar unalign;\n>>> +\tgit_max_align aligned;\n>>> +} git_max_alignment;\n>>> +#define GIT_MAX_ALIGNMENT offsetof(git_max_alignment, aligned)\n> \n> Style nit: We tend to use typedef sparingly.  And the union type doesn't\n> even need a name.  E.g. this would work as well, while reducing the name\n> space footprint:\n> \n>   struct git_max_alignment {\n>      char unalign;\n>      union {\n>         uintmax_t max_align_uintmax;\n>         void *max_align_pointer;\n>      } aligned;\n>   };\n>   #define GIT_MAX_ALIGNMENT offsetof(struct git_max_alignment, aligned)\n> \n> When someone uses a mempool for objects that requires 128-bit alignment\n> (e.g. because it includes a long double or uint128_t member) then we'd\n> need add long double to the union as well, like e.g. compat/obstack.c\n> does.  That would be the safe route, but currently only add 8 bytes of\n> unnecessary overhead to each allocation.\n> \n> Perhaps mempool alignment should be configurable.  For now a comment\n> might suffice which indicates that GIT_MAX_ALIGNMENT is only the\n> maximum alignment requirement of current mempool users, not the\n> highest possible requirement for the machine.  Renaming it to something\n> with MEMPOOL in the name would help in this regard as well.\n\nSure, that all makes sense.\n\nJess\n\n>>> +\n>>> /* used on Mac OS X */\n>>> #ifdef PRECOMPOSE_UNICODE\n>>> #include \"compat/precompose_utf8.h\"\n>>> diff --git a/mem-pool.c b/mem-pool.c\n>>> index ccdcad2e3d..748eff925a 100644\n>>> --- a/mem-pool.c\n>>> +++ b/mem-pool.c\n>>> @@ -69,9 +69,9 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len)\n>>> \tstruct mp_block *p = NULL;\n>>> \tvoid *r;\n>>> \n>>> -\t/* round up to a 'uintmax_t' alignment */\n>>> -\tif (len & (sizeof(uintmax_t) - 1))\n>>> -\t\tlen += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));\n>>> +\t/* round up to a 'GIT_MAX_ALIGNMENT' alignment */\n>>> +\tif (len & (GIT_MAX_ALIGNMENT - 1))\n>>> +\t\tlen += GIT_MAX_ALIGNMENT - (len & (GIT_MAX_ALIGNMENT - 1));\n>>> \n>>> \tif (pool->mp_block &&\n>>> \t    pool->mp_block->end - pool->mp_block->next_free >= len)\n>>> --\n>>> 2.33.1\n>>> \n>> \n> \n\n"},{"id":"446718","messageId":"20220123152458.72540-1-jrtc27@jrtc27.com","threadId":"57187","inReplyTo":"20220105132324.6651-1-jrtc27@jrtc27.com","subject":"[PATCH v2] mem-pool: Don't assume uintmax_t is aligned enough for all types","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-23T15:24:58Z","receivedAt":"2022-01-23T15:25:06Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"Currently mem_pool_alloc uses sizeof(uintmax_t) as a proxy for what\nshould be _Alignof(max_align_t) in C11. On most architectures this is\nsufficient (though on m68k it is in fact overly strict, since the\nde-facto ABI, which differs from the specified System V ABI, has the\nmaximum alignment of all types as 2 bytes), but on CHERI, and thus Arm's\nMorello prototype, it is insufficient for any type that stores a\npointer, which must be aligned to 128 bits (on 64-bit architectures\nextended with CHERI), whilst uintmax_t is a 64-bit integer.\n\nFix this by introducing our own approximation for max_align_t and a\nmeans to compute _Alignof it without relying on C11. Currently this\nunion only contains uintmax_t and void *, but more types can be added as\nneeded.\n\nSigned-off-by: Jessica Clarke <jrtc27@jrtc27.com>\n---\n mem-pool.c | 22 +++++++++++++++++++---\n 1 file changed, 19 insertions(+), 3 deletions(-)\n\ndiff --git a/mem-pool.c b/mem-pool.c\nindex ccdcad2e3d..b373cadd01 100644\n--- a/mem-pool.c\n+++ b/mem-pool.c\n@@ -7,6 +7,22 @@\n \n #define BLOCK_GROWTH_SIZE (1024 * 1024 - sizeof(struct mp_block))\n \n+/*\n+ * The inner union is an approximation for C11's max_align_t, and the\n+ * struct + offsetof computes _Alignof. This can all just be replaced\n+ * with _Alignof(max_align_t) if/when C11 is part of the baseline.\n+ *\n+ * Add more types to the union if the current set is insufficient.\n+ */\n+struct git_max_alignment {\n+\tchar unalign;\n+\tunion {\n+\t\tuintmax_t max_align_uintmax;\n+\t\tvoid *max_align_pointer;\n+\t} aligned;\n+};\n+#define GIT_MAX_ALIGNMENT offsetof(struct git_max_alignment, aligned)\n+\n /*\n  * Allocate a new mp_block and insert it after the block specified in\n  * `insert_after`. If `insert_after` is NULL, then insert block at the\n@@ -69,9 +85,9 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len)\n \tstruct mp_block *p = NULL;\n \tvoid *r;\n \n-\t/* round up to a 'uintmax_t' alignment */\n-\tif (len & (sizeof(uintmax_t) - 1))\n-\t\tlen += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));\n+\t/* round up to a 'GIT_MAX_ALIGNMENT' alignment */\n+\tif (len & (GIT_MAX_ALIGNMENT - 1))\n+\t\tlen += GIT_MAX_ALIGNMENT - (len & (GIT_MAX_ALIGNMENT - 1));\n \n \tif (pool->mp_block &&\n \t    pool->mp_block->end - pool->mp_block->next_free >= len)\n-- \n2.33.1\n\n"},{"id":"446723","messageId":"xmqqsfte8awj.fsf@gitster.g","threadId":"57187","inReplyTo":"20220123152458.72540-1-jrtc27@jrtc27.com","subject":"Re: [PATCH v2] mem-pool: Don't assume uintmax_t is aligned enough for all types","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-23T20:17:16Z","receivedAt":"2022-01-23T20:17:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jessica Clarke <jrtc27@jrtc27.com> writes:\n\n> Currently mem_pool_alloc uses sizeof(uintmax_t) as a proxy for what\n> should be _Alignof(max_align_t) in C11. On most architectures this is\n\nLose \"Currently\", as the present tense describes the status quo, the\nshape of the problematic code we have today that wants improvement\nby the proposed patch.\n\n> sufficient (though on m68k it is in fact overly strict, since the\n> de-facto ABI, which differs from the specified System V ABI, has the\n> maximum alignment of all types as 2 bytes), but on CHERI, and thus Arm's\n> Morello prototype, it is insufficient for any type that stores a\n> pointer, which must be aligned to 128 bits (on 64-bit architectures\n> extended with CHERI), whilst uintmax_t is a 64-bit integer.\n\nOK.\n\n> Fix this by introducing our own approximation for max_align_t and a\n> means to compute _Alignof it without relying on C11. Currently this\n> union only contains uintmax_t and void *, but more types can be added as\n> needed.\n\nNicely described.\n\n> +/*\n> + * The inner union is an approximation for C11's max_align_t, and the\n> + * struct + offsetof computes _Alignof. This can all just be replaced\n> + * with _Alignof(max_align_t) if/when C11 is part of the baseline.\n> + *\n> + * Add more types to the union if the current set is insufficient.\n> + */\n> +struct git_max_alignment {\n> +\tchar unalign;\n> +\tunion {\n> +\t\tuintmax_t max_align_uintmax;\n> +\t\tvoid *max_align_pointer;\n> +\t} aligned;\n> +};\n> +#define GIT_MAX_ALIGNMENT offsetof(struct git_max_alignment, aligned)\n> +\n\nThe original computed the alignment requirement for uintmax_t as\nsizeof(uintmax_t), not as\n\n\toffsetof(struct {\n\t\tchar unalign;\n\t\tunion { uintmax_t i; } aligned;\n\t}, aligned)\n\nbecause if you have an array of a type, each element of it must be\naligned appropriately already for that type, without the unalignment\nthe outer struct enforces.  I wonder if your complex offsetof is\nequivalent to sizeof(union { uintmax_t u; void *p; })?\n\nIOW, in this struct:\n\n\tstruct max_alignment_helper {\n\t\tchar unalign;\n\t\tunion {\n\t\t\tuintmax_t uintmax_t_unused;\n\t\t\tvoid *pointer_unused;\n\t\t} u[2];\n\t} s;\n\nboth s.u[0] and s.u[1] must be properly aligned, so wouldn't the\nalignment requirement for the union type, which can be used to hold\na single value of either uintmax_t or a poinhter, be the distance\nbetween these two array elements, i.e. sizeof(s.u[0])?\n\nTo put it differently in yet another way, wouldn't it simplify down\nto this?\n\n\tunion max_alignment_helper {\n\t\tuintmax_t uintmax_t_unused;\n                void *pointer_unused;\n\t};\n\t#define GIT_MAX_ALIGNMENT sizeof(union max_alignment_helper);\n\nI am not saying that the \"a forcibly unaligned union in a struct\" is\na bad/wrong way to express what you want to achieve.  I just do not\nknow if there is a reason to choose it over a seemingly simpler\nsizeof(that union) without the outer struct and unalign member.\n\nOther than that, looks OK to me.  Especially the parts that use the\nmacro look correctly converted.\n\nThanks.\n\n> @@ -69,9 +85,9 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len)\n>  \tstruct mp_block *p = NULL;\n>  \tvoid *r;\n>  \n> -\t/* round up to a 'uintmax_t' alignment */\n> -\tif (len & (sizeof(uintmax_t) - 1))\n> -\t\tlen += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));\n> +\t/* round up to a 'GIT_MAX_ALIGNMENT' alignment */\n> +\tif (len & (GIT_MAX_ALIGNMENT - 1))\n> +\t\tlen += GIT_MAX_ALIGNMENT - (len & (GIT_MAX_ALIGNMENT - 1));\n>  \n>  \tif (pool->mp_block &&\n>  \t    pool->mp_block->end - pool->mp_block->next_free >= len)\n\n\n>  /*\n>   * Allocate a new mp_block and insert it after the block specified in\n>   * `insert_after`. If `insert_after` is NULL, then insert block at the\n> @@ -69,9 +85,9 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len)\n>  \tstruct mp_block *p = NULL;\n>  \tvoid *r;\n>  \n> -\t/* round up to a 'uintmax_t' alignment */\n> -\tif (len & (sizeof(uintmax_t) - 1))\n> -\t\tlen += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));\n> +\t/* round up to a 'GIT_MAX_ALIGNMENT' alignment */\n> +\tif (len & (GIT_MAX_ALIGNMENT - 1))\n> +\t\tlen += GIT_MAX_ALIGNMENT - (len & (GIT_MAX_ALIGNMENT - 1));\n>  \n>  \tif (pool->mp_block &&\n>  \t    pool->mp_block->end - pool->mp_block->next_free >= len)\n"},{"id":"446724","messageId":"FD089F0E-C826-4A8E-BC16-F763E256B410@jrtc27.com","threadId":"57187","inReplyTo":"xmqqsfte8awj.fsf@gitster.g","subject":"Re: [PATCH v2] mem-pool: Don't assume uintmax_t is aligned enough for all types","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-23T20:23:53Z","receivedAt":"2022-01-23T20:23:59Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"On 23 Jan 2022, at 20:17, Junio C Hamano <gitster@pobox.com> wrote:\n> \n> Jessica Clarke <jrtc27@jrtc27.com> writes:\n> \n>> Currently mem_pool_alloc uses sizeof(uintmax_t) as a proxy for what\n>> should be _Alignof(max_align_t) in C11. On most architectures this is\n> \n> Lose \"Currently\", as the present tense describes the status quo, the\n> shape of the problematic code we have today that wants improvement\n> by the proposed patch.\n\nDo you want a v3 or is that something you'll amend on git-am?\n\n>> sufficient (though on m68k it is in fact overly strict, since the\n>> de-facto ABI, which differs from the specified System V ABI, has the\n>> maximum alignment of all types as 2 bytes), but on CHERI, and thus Arm's\n>> Morello prototype, it is insufficient for any type that stores a\n>> pointer, which must be aligned to 128 bits (on 64-bit architectures\n>> extended with CHERI), whilst uintmax_t is a 64-bit integer.\n> \n> OK.\n> \n>> Fix this by introducing our own approximation for max_align_t and a\n>> means to compute _Alignof it without relying on C11. Currently this\n>> union only contains uintmax_t and void *, but more types can be added as\n>> needed.\n> \n> Nicely described.\n> \n>> +/*\n>> + * The inner union is an approximation for C11's max_align_t, and the\n>> + * struct + offsetof computes _Alignof. This can all just be replaced\n>> + * with _Alignof(max_align_t) if/when C11 is part of the baseline.\n>> + *\n>> + * Add more types to the union if the current set is insufficient.\n>> + */\n>> +struct git_max_alignment {\n>> +\tchar unalign;\n>> +\tunion {\n>> +\t\tuintmax_t max_align_uintmax;\n>> +\t\tvoid *max_align_pointer;\n>> +\t} aligned;\n>> +};\n>> +#define GIT_MAX_ALIGNMENT offsetof(struct git_max_alignment, aligned)\n>> +\n> \n> The original computed the alignment requirement for uintmax_t as\n> sizeof(uintmax_t), not as\n> \n> \toffsetof(struct {\n> \t\tchar unalign;\n> \t\tunion { uintmax_t i; } aligned;\n> \t}, aligned)\n> \n> because if you have an array of a type, each element of it must be\n> aligned appropriately already for that type, without the unalignment\n> the outer struct enforces.  I wonder if your complex offsetof is\n> equivalent to sizeof(union { uintmax_t u; void *p; })?\n> \n> IOW, in this struct:\n> \n> \tstruct max_alignment_helper {\n> \t\tchar unalign;\n> \t\tunion {\n> \t\t\tuintmax_t uintmax_t_unused;\n> \t\t\tvoid *pointer_unused;\n> \t\t} u[2];\n> \t} s;\n> \n> both s.u[0] and s.u[1] must be properly aligned, so wouldn't the\n> alignment requirement for the union type, which can be used to hold\n> a single value of either uintmax_t or a poinhter, be the distance\n> between these two array elements, i.e. sizeof(s.u[0])?\n> \n> To put it differently in yet another way, wouldn't it simplify down\n> to this?\n> \n> \tunion max_alignment_helper {\n> \t\tuintmax_t uintmax_t_unused;\n>                void *pointer_unused;\n> \t};\n> \t#define GIT_MAX_ALIGNMENT sizeof(union max_alignment_helper);\n> \n> I am not saying that the \"a forcibly unaligned union in a struct\" is\n> a bad/wrong way to express what you want to achieve.  I just do not\n> know if there is a reason to choose it over a seemingly simpler\n> sizeof(that union) without the outer struct and unalign member.\n\nSo, sizeof(X) does not always equal _Alignof(X), even for primitive\ntypes, _Alignof need only be a factor of sizeof. The two are the same\non most architectures, and is a sensible ABI, but the exception is the\nm68k case I was referring to above. On m68k, sizeof(long long) == 8,\nbut _Alignof(long long) == 2 (yes this is a real pain point of its ABI;\nin particular int is only 2-byte aligned, but futex(2) explicitly\nrequires 4-byte alignment). So using sizeof definitely gets you\nsomething sufficiently aligned, but can waste space. This doesn’t\naffect CHERI/Morello, all our implementations keep sizeof == _Alignof,\nbut as I was changing this code I felt I should use the more precise\nconstruct.\n\nJess\n\n> Other than that, looks OK to me.  Especially the parts that use the\n> macro look correctly converted.\n> \n> Thanks.\n> \n>> @@ -69,9 +85,9 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len)\n>> \tstruct mp_block *p = NULL;\n>> \tvoid *r;\n>> \n>> -\t/* round up to a 'uintmax_t' alignment */\n>> -\tif (len & (sizeof(uintmax_t) - 1))\n>> -\t\tlen += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));\n>> +\t/* round up to a 'GIT_MAX_ALIGNMENT' alignment */\n>> +\tif (len & (GIT_MAX_ALIGNMENT - 1))\n>> +\t\tlen += GIT_MAX_ALIGNMENT - (len & (GIT_MAX_ALIGNMENT - 1));\n>> \n>> \tif (pool->mp_block &&\n>> \t    pool->mp_block->end - pool->mp_block->next_free >= len)\n> \n> \n>> /*\n>>  * Allocate a new mp_block and insert it after the block specified in\n>>  * `insert_after`. If `insert_after` is NULL, then insert block at the\n>> @@ -69,9 +85,9 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len)\n>> \tstruct mp_block *p = NULL;\n>> \tvoid *r;\n>> \n>> -\t/* round up to a 'uintmax_t' alignment */\n>> -\tif (len & (sizeof(uintmax_t) - 1))\n>> -\t\tlen += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));\n>> +\t/* round up to a 'GIT_MAX_ALIGNMENT' alignment */\n>> +\tif (len & (GIT_MAX_ALIGNMENT - 1))\n>> +\t\tlen += GIT_MAX_ALIGNMENT - (len & (GIT_MAX_ALIGNMENT - 1));\n>> \n>> \tif (pool->mp_block &&\n>> \t    pool->mp_block->end - pool->mp_block->next_free >= len)\n\n"},{"id":"446725","messageId":"xmqqo8428ae6.fsf@gitster.g","threadId":"57187","inReplyTo":"FD089F0E-C826-4A8E-BC16-F763E256B410@jrtc27.com","subject":"Re: [PATCH v2] mem-pool: Don't assume uintmax_t is aligned enough for all types","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-23T20:28:17Z","receivedAt":"2022-01-23T20:28:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jessica Clarke <jrtc27@jrtc27.com> writes:\n\n> So, sizeof(X) does not always equal _Alignof(X), even for primitive\n> types, _Alignof need only be a factor of sizeof. The two are the same\n> on most architectures, and is a sensible ABI, but the exception is the\n> m68k case I was referring to above. On m68k, sizeof(long long) == 8,\n> but _Alignof(long long) == 2 (yes this is a real pain point of its ABI;\n\nAh, thanks.  Having a variant of the above explanation in a comment\nnext to the \"union within a struct\" would help future readers from\nasking the same question as I asked.\n\n"},{"id":"446726","messageId":"20220123203347.74869-1-jrtc27@jrtc27.com","threadId":"57187","inReplyTo":"20220123152458.72540-1-jrtc27@jrtc27.com","subject":"[PATCH v3] mem-pool: Don't assume uintmax_t is aligned enough for all types","fromName":"Jessica Clarke","fromEmail":"jrtc27@jrtc27.com","sentAt":"2022-01-23T20:33:47Z","receivedAt":"2022-01-23T20:33:57Z","isPatch":true,"sender":{"key":"jrtc27@jrtc27.com","avatar":"https://avatars.githubusercontent.com/u/816232?v=4"},"body":"mem_pool_alloc uses sizeof(uintmax_t) as a proxy for what should be\n_Alignof(max_align_t) in C11. On most architectures this is sufficient\n(though on m68k it is in fact overly strict, since the de-facto ABI,\nwhich differs from the specified System V ABI, has the maximum alignment\nof all types as 2 bytes), but on CHERI, and thus Arm's Morello\nprototype, it is insufficient for any type that stores a pointer, which\nmust be aligned to 128 bits (on 64-bit architectures extended with\nCHERI), whilst uintmax_t is a 64-bit integer.\n\nFix this by introducing our own approximation for max_align_t and a\nmeans to compute _Alignof it without relying on C11. Currently this\nunion only contains uintmax_t and void *, but more types can be added as\nneeded.\n\nSigned-off-by: Jessica Clarke <jrtc27@jrtc27.com>\n---\n\nChanged in v3:\n* Removed first \"Currently\" from commit message body\n* Added explanation for _Alignof vs sizeof in comment\n\n mem-pool.c | 26 +++++++++++++++++++++++---\n 1 file changed, 23 insertions(+), 3 deletions(-)\n\ndiff --git a/mem-pool.c b/mem-pool.c\nindex ccdcad2e3d..599d8e895f 100644\n--- a/mem-pool.c\n+++ b/mem-pool.c\n@@ -7,6 +7,26 @@\n \n #define BLOCK_GROWTH_SIZE (1024 * 1024 - sizeof(struct mp_block))\n \n+/*\n+ * The inner union is an approximation for C11's max_align_t, and the\n+ * struct + offsetof computes _Alignof. This can all just be replaced\n+ * with _Alignof(max_align_t) if/when C11 is part of the baseline.\n+ * Note that _Alignof(X) need not be the same as sizeof(X); it's only\n+ * required to be a (possibly trivial) factor. They are the same for\n+ * most architectures, but m68k for example has only 2-byte alignment\n+ * for its 4-byte and 8-byte types, so using sizeof would waste space.\n+ *\n+ * Add more types to the union if the current set is insufficient.\n+ */\n+struct git_max_alignment {\n+\tchar unalign;\n+\tunion {\n+\t\tuintmax_t max_align_uintmax;\n+\t\tvoid *max_align_pointer;\n+\t} aligned;\n+};\n+#define GIT_MAX_ALIGNMENT offsetof(struct git_max_alignment, aligned)\n+\n /*\n  * Allocate a new mp_block and insert it after the block specified in\n  * `insert_after`. If `insert_after` is NULL, then insert block at the\n@@ -69,9 +89,9 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len)\n \tstruct mp_block *p = NULL;\n \tvoid *r;\n \n-\t/* round up to a 'uintmax_t' alignment */\n-\tif (len & (sizeof(uintmax_t) - 1))\n-\t\tlen += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));\n+\t/* round up to a 'GIT_MAX_ALIGNMENT' alignment */\n+\tif (len & (GIT_MAX_ALIGNMENT - 1))\n+\t\tlen += GIT_MAX_ALIGNMENT - (len & (GIT_MAX_ALIGNMENT - 1));\n \n \tif (pool->mp_block &&\n \t    pool->mp_block->end - pool->mp_block->next_free >= len)\n-- \n2.33.1\n\n"},{"id":"446758","messageId":"xmqq1r0x6otd.fsf@gitster.g","threadId":"57187","inReplyTo":"20220123203347.74869-1-jrtc27@jrtc27.com","subject":"Re: [PATCH v3] mem-pool: Don't assume uintmax_t is aligned enough for all types","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-24T17:11:58Z","receivedAt":"2022-01-24T17:12:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"> +/*\n> + * The inner union is an approximation for C11's max_align_t, and the\n> + * struct + offsetof computes _Alignof. This can all just be replaced\n> + * with _Alignof(max_align_t) if/when C11 is part of the baseline.\n> + * Note that _Alignof(X) need not be the same as sizeof(X); it's only\n> + * required to be a (possibly trivial) factor. They are the same for\n> + * most architectures, but m68k for example has only 2-byte alignment\n> + * for its 4-byte and 8-byte types, so using sizeof would waste space.\n> + *\n> + * Add more types to the union if the current set is insufficient.\n> + */\n\nThat reads very clear.  Thanks.\n\nWill queue.\n"}]}