{"thread":{"id":"35769","subject":"[PATCH] Ensure __BYTE_ORDER is always set","startedAt":"2014-01-30T19:55:41Z","lastAt":"2014-01-31T02:35:14Z","messageCount":9,"participants":["Brian Gernhardt","Jeff King","Jonathan Nieder","Eric Sunshine"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"233955","messageId":"1391111741-28994-1-git-send-email-brian@gernhardtsoftware.com","threadId":"35769","inReplyTo":null,"subject":"[PATCH] Ensure __BYTE_ORDER is always set","fromName":"Brian Gernhardt","fromEmail":"brian@gernhardtsoftware.com","sentAt":"2014-01-30T19:55:41Z","receivedAt":"2014-01-30T19:55:41Z","isPatch":true,"sender":{"key":"brian@gernhardtsoftware.com","avatar":"https://avatars.githubusercontent.com/u/133455?v=4"},"body":"a201c20 (ewah: support platforms that require aligned reads) added a\nreliance on the existence of __BYTE_ORDER and __BIG_ENDIAN. However,\nthese macros are spelled without the leading __ on some platforms (OS\nX at least). In this case, the endian-swapping code was added even\nwhen unnecessary, which caused assertion failures in\nt5310-pack-bitmaps.sh as the code that used the bitmap would read past\nthe end.\n\nWe already had code to handle this case in compat/bswap.h, but it was\nonly used if we couldn't already find a reasonable version of bswap64.\nMove the macro-defining and checking code out of a conditional so that\neither __BYTE_ORDER is defined or we get a compilation error instead\nof a runtime error in the bitmap code.\n\nSigned-off-by: Brian Gernhardt \n---\n compat/bswap.h | 24 ++++++++++++------------\n 1 file changed, 12 insertions(+), 12 deletions(-)\n\ndiff --git a/compat/bswap.h b/compat/bswap.h\nindex 120c6c1..7db09d6 100644\n--- a/compat/bswap.h\n+++ b/compat/bswap.h\n@@ -80,6 +80,18 @@ static inline uint64_t git_bswap64(uint64_t x)\n \n #endif\n \n+#if !defined(__BYTE_ORDER)\n+# if defined(BYTE_ORDER) && defined(LITTLE_ENDIAN) && defined(BIG_ENDIAN)\n+# define __BYTE_ORDER BYTE_ORDER\n+# define __LITTLE_ENDIAN LITTLE_ENDIAN\n+# define __BIG_ENDIAN BIG_ENDIAN\n+# endif\n+#endif\n+\n+#if !defined(__BYTE_ORDER)\n+# error \"Cannot determine endianness\"\n+#endif\n+\n #if defined(bswap32)\n \n #undef ntohl\n@@ -101,18 +113,6 @@ static inline uint64_t git_bswap64(uint64_t x)\n #undef ntohll\n #undef htonll\n \n-#if !defined(__BYTE_ORDER)\n-# if defined(BYTE_ORDER) && defined(LITTLE_ENDIAN) && defined(BIG_ENDIAN)\n-# define __BYTE_ORDER BYTE_ORDER\n-# define __LITTLE_ENDIAN LITTLE_ENDIAN\n-# define __BIG_ENDIAN BIG_ENDIAN\n-# endif\n-#endif\n-\n-#if !defined(__BYTE_ORDER)\n-# error \"Cannot determine endianness\"\n-#endif\n-\n #if __BYTE_ORDER == __BIG_ENDIAN\n # define ntohll(n) (n)\n # define htonll(n) (n)\n-- \n1.9.rc0.256.gbc3fa69\n"},{"id":"233957","messageId":"20140130204538.GA1130@sigill.intra.peff.net","threadId":"35769","inReplyTo":"1391111741-28994-1-git-send-email-brian@gernhardtsoftware.com","subject":"Re: [PATCH] Ensure __BYTE_ORDER is always set","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-30T20:45:38Z","receivedAt":"2014-01-30T20:45:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 30, 2014 at 02:55:41PM -0500, Brian Gernhardt wrote:\n\n> a201c20 (ewah: support platforms that require aligned reads) added a\n> reliance on the existence of __BYTE_ORDER and __BIG_ENDIAN. However,\n> these macros are spelled without the leading __ on some platforms (OS\n> X at least). In this case, the endian-swapping code was added even\n> when unnecessary, which caused assertion failures in\n> t5310-pack-bitmaps.sh as the code that used the bitmap would read past\n> the end.\n> \n> We already had code to handle this case in compat/bswap.h, but it was\n> only used if we couldn't already find a reasonable version of bswap64.\n> Move the macro-defining and checking code out of a conditional so that\n> either __BYTE_ORDER is defined or we get a compilation error instead\n> of a runtime error in the bitmap code.\n\nThanks, this makes sense, and matches the assumption that a201c20 made.\n\nI do find the failure mode interesting. The endian-swapping code kicked\nin when it did not, meaning your are on a big-endian system. Is this on\nan ancient PPC Mac? Or is the problem that the code did not kick in when\nit should?\n\nEither way, we should perhaps be more careful in the bitmap code, too,\nthat the values we get are sensible. It's better to die(\"your bitmap is\nbroken\") than to read off the end of the array. I can't seem to trigger\nthe same failure mode, though. On my x86 system, turning off the\nendian-swap (i.e., the opposite of what should happen) makes t5310 fail,\nbut it is because we end up trying to set the bit very far into a\ndynamic bitfield, and die allocating memory.\n\n-Peff\n"},{"id":"233958","messageId":"20140130215002.GB1130@sigill.intra.peff.net","threadId":"35769","inReplyTo":"20140130204538.GA1130@sigill.intra.peff.net","subject":"Re: [PATCH] Ensure __BYTE_ORDER is always set","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-30T21:50:03Z","receivedAt":"2014-01-30T21:50:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 30, 2014 at 03:45:38PM -0500, Jeff King wrote:\n\n> Either way, we should perhaps be more careful in the bitmap code, too,\n> that the values we get are sensible. It's better to die(\"your bitmap is\n> broken\") than to read off the end of the array. I can't seem to trigger\n> the same failure mode, though. On my x86 system, turning off the\n> endian-swap (i.e., the opposite of what should happen) makes t5310 fail,\n> but it is because we end up trying to set the bit very far into a\n> dynamic bitfield, and die allocating memory.\n\nI think we could do this with something like the patch below, which\nchecks two things:\n\n 1. When we expand the ewah, it has the same number of bits we claimed\n in the on-disk header.\n\n 2. The ewah header matches the number of objects in the packfile.\n\nThe first catches a corruption in the ewah data itself, and the latter\nwhen the header is corrupted. You can test either by breaking the\nendian-swapping. :)\n\nVicent, can you confirm my assumptions about the round-to-nearest-64 in\nthe patch below? I assume that the bit_size on-disk may be rounded in\nsome cases (and it is -- if you take out the rounding, this breaks\nthings). Is that sane? Or should the on-disk ewah bit_size header always\nmatch the number of objects in the pack, and our writer is just being\nsloppy?\n\ndiff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\nindex 9ced2da..a8f77cf 100644\n--- a/ewah/ewah_bitmap.c\n+++ b/ewah/ewah_bitmap.c\n@@ -343,6 +343,18 @@ int ewah_iterator_next(eword_t *next, struct ewah_iterator *it)\n \tif (it->pointer >= it->buffer_size)\n \t\treturn 0;\n \n+\t/*\n+\t * If we return more bits than the ewah advertised, then either\n+\t * our data bits or the bit_size field was corrupted, and we\n+\t * risk a caller overwriting their own buffer (if they used\n+\t * bit_size to size their buffer in the first place).\n+\t *\n+\t * We don't have a good way of returning an error here, so let's\n+\t * just die.\n+\t */\n+\tif (!it->words_remaining--)\n+\t\tdie(\"ewah bitmap contains more bits than it claims\");\n+\n \tif (it->compressed < it->rl) {\n \t\tit->compressed++;\n \t\t*next = it->b ? (eword_t)(~0) : 0;\n@@ -371,6 +383,8 @@ void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent)\n \tit->buffer_size = parent->buffer_size;\n \tit->pointer = 0;\n \n+\tit->words_remaining = (parent->bit_size + 63) / 64;\n+\n \tit->lw = 0;\n \tit->rl = 0;\n \tit->compressed = 0;\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex 43adeb5..a3f49de 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -144,6 +144,7 @@ struct ewah_iterator {\n \tsize_t buffer_size;\n \n \tsize_t pointer;\n+\tsize_t words_remaining;\n \teword_t compressed, literals;\n \teword_t rl, lw;\n \tint b;\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex ae0b57b..a31e529 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -118,6 +118,7 @@ static struct ewah_bitmap *lookup_stored_bitmap(struct stored_bitmap *st)\n */\n static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index)\n {\n+\tsize_t expected_bits;\n \tstruct ewah_bitmap *b = ewah_pool_new();\n \n \tint bitmap_size = ewah_read_mmap(b,\n@@ -130,6 +131,31 @@ static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index)\n \t\treturn NULL;\n \t}\n \n+\t/*\n+\t * It's OK for us to have too fewer bits than objects, as the EWAH\n+\t * writer may have simply left off an ending that is all-zeroes.\n+\t *\n+\t * However it's not OK for us to have too many bits, as that would\n+\t * entail touching objects that we don't have. We are careful\n+\t * enough to avoid doing so in later code, but in the case of\n+\t * nonsensical values, we would want to avoid even allocating\n+\t * memory to hold the expanded bitmap.\n+\t *\n+\t * There is one exception: we may \"go over\" to round up to the next\n+\t * 64-bit ewah word, since the storage comes in chunks of that size.\n+\t */\n+\texpected_bits = index->pack->num_objects;\n+\tif (expected_bits & 63) {\n+\t\texpected_bits &= ~63;\n+\t\texpected_bits += 64;\n+\t}\n+\tif (b->bit_size > expected_bits) {\n+\t\terror(\"unexpected number of bits in bitmap: %\"PRIuMAX\" > %\"PRIuMAX,\n+\t\t (uintmax_t)b->bit_size, (uintmax_t)expected_bits);\n+\t\tewah_pool_free(b);\n+\t\treturn NULL;\n+\t}\n+\n \tindex->map_pos += bitmap_size;\n \treturn b;\n }\n"},{"id":"233959","messageId":"20140130220233.GH27577@google.com","threadId":"35769","inReplyTo":"1391111741-28994-1-git-send-email-brian@gernhardtsoftware.com","subject":"Re: [PATCH] Ensure __BYTE_ORDER is always set","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2014-01-30T22:02:33Z","receivedAt":"2014-01-30T22:02:33Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nBrian Gernhardt wrote:\n\n> a201c20 (ewah: support platforms that require aligned reads) added a\n> reliance on the existence of __BYTE_ORDER and __BIG_ENDIAN. However,\n> these macros are spelled without the leading __ on some platforms (OS\n> X at least). In this case, the endian-swapping code was added even\n> when unnecessary, which caused assertion failures in\n> t5310-pack-bitmaps.sh as the code that used the bitmap would read past\n> the end.\n>\n> We already had code to handle this case in compat/bswap.h, but it was\n> only used if we couldn't already find a reasonable version of bswap64.\n\nMakes sense. Sorry I missed this.\n\nIn an ideal world I would prefer to just rely on ntohll when it's\ndecent (meaning that the '#if __BYTE_ORDER != __BIG_ENDIAN' block\ncould be written as\n\n\tif (ntohll(1) != 1) {\n\t\t...\n\t}\n\nor\n\n\tif (ntohll(1) == 1)\n\t\t; /* Big endian. Nothing to do.\n\telse {\n\t\t...\n\t}\n\n). But compat/bswap.h already relies on knowing the endianness at\npreprocessing time so that wouldn't buy anything.\n\nAnother \"in an ideal world\" option: make the loop unconditional after\nchecking that optimizers on big-endian systems realize it's a noop.\nIn any event, in the real world your patch looks like the right thing\nto do.\n\nReviewed-by: Jonathan Nieder \n"},{"id":"233960","messageId":"20140130221205.GI27577@google.com","threadId":"35769","inReplyTo":"20140130204538.GA1130@sigill.intra.peff.net","subject":"Re: [PATCH] Ensure __BYTE_ORDER is always set","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2014-01-30T22:12:05Z","receivedAt":"2014-01-30T22:12:05Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nJeff King wrote:\n\n> I do find the failure mode interesting. The endian-swapping code kicked\n> in when it did not\n\nOdd --- wouldn't the #if condition expand to '0 != 0'?\n"},{"id":"233962","messageId":"20140130224657.GA30478@sigill.intra.peff.net","threadId":"35769","inReplyTo":"20140130220233.GH27577@google.com","subject":"Re: [PATCH] Ensure __BYTE_ORDER is always set","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-30T22:46:57Z","receivedAt":"2014-01-30T22:46:57Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 30, 2014 at 02:02:33PM -0800, Jonathan Nieder wrote:\n\n> In an ideal world I would prefer to just rely on ntohll when it's\n> decent (meaning that the '#if __BYTE_ORDER != __BIG_ENDIAN' block\n> could be written as\n> \n> \tif (ntohll(1) != 1) {\n> \t\t...\n> \t}\n> \n> or\n> \n> \tif (ntohll(1) == 1)\n> \t\t; /* Big endian. Nothing to do.\n> \telse {\n> \t\t...\n> \t}\n> \n> ). But compat/bswap.h already relies on knowing the endianness at\n> preprocessing time so that wouldn't buy anything.\n\nYes, though it would simplify things because we are depending on ntohll\nbeing defined, rather than some obscure macros.\n\n> Another \"in an ideal world\" option: make the loop unconditional after\n> checking that optimizers on big-endian systems realize it's a noop.\n> In any event, in the real world your patch looks like the right thing\n> to do.\n\nI had the same thought when reading the original patch. The loop after\npre-processing on a big-endian system should look like:\n\n {\n size_t i;\n for (i = 0; i < self->buffer_size; ++i)\n self->buffer[i] = self->buffer[i];\n }\n\nIt really seems like the sort of thing that any halfway decent compiler\nshould be able to turn into a noop. I'm OK to go that route, and if you\ndon't have a halfway decent compiler, tough cookies; git will waste your\nprecious nanoseconds doing a relatively small loop. If this loop\nactually mattered, we would probably do better still to leave it in disk\norder, and fix it up as-needed only when we look at a particular bitmap\n(we do not typically need to look at all of them on disk).\n\n-Peff\n"},{"id":"233963","messageId":"20140130224817.GB30478@sigill.intra.peff.net","threadId":"35769","inReplyTo":"20140130221205.GI27577@google.com","subject":"Re: [PATCH] Ensure __BYTE_ORDER is always set","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-30T22:48:17Z","receivedAt":"2014-01-30T22:48:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 30, 2014 at 02:12:05PM -0800, Jonathan Nieder wrote:\n\n> Jeff King wrote:\n> \n> > I do find the failure mode interesting. The endian-swapping code kicked\n> > in when it did not\n> \n> Odd --- wouldn't the #if condition expand to '0 != 0'?\n\nI had the same thought. The \"kicked in when it did not\" is Brian's claim\nfrom the original, which is why I was confused. He replied to me\noff-list, and I think he may simply have had it backwards. :)\n\n-Peff\n"},{"id":"233964","messageId":"1E24F82E-3543-459E-9C55-350AE8C4E455@gernhardtsoftware.com","threadId":"35769","inReplyTo":"20140130204538.GA1130@sigill.intra.peff.net","subject":"Re: [PATCH] Ensure __BYTE_ORDER is always set","fromName":"Brian Gernhardt","fromEmail":"brian@gernhardtsoftware.com","sentAt":"2014-01-30T23:24:01Z","receivedAt":"2014-01-30T23:24:01Z","isPatch":true,"sender":{"key":"brian@gernhardtsoftware.com","avatar":"https://avatars.githubusercontent.com/u/133455?v=4"},"body":"[Re-send to include the list. Meant to hit reply all, not just reply.]\n\n> On Jan 30, 2014, at 3:45 PM, Jeff King wrote:\n> \n> I do find the failure mode interesting. The endian-swapping code kicked\n> in when it did not, meaning your are on a big-endian system. Is this on\n> an ancient PPC Mac? Or is the problem that the code did not kick in when\n> it should?\n\nErm. I was perhaps writing my analysis too quickly. I was running on a x86_64 Mac, so it wasn't included when it was supposed to be. Or whichever you said that I didn't. ;-)\n\n> Either way, we should perhaps be more careful in the bitmap code, too,\n> that the values we get are sensible. It's better to die(\"your bitmap is\n> broken\") than to read off the end of the array. I can't seem to trigger\n> the same failure mode, though. On my x86 system, turning off the\n> endian-swap (i.e., the opposite of what should happen) makes t5310 fail,\n> but it is because we end up trying to set the bit very far into a\n> dynamic bitfield, and die allocating memory.\n\nTo be more specific, I hit an assertion failure at in ewah_iterator_next() (ewah/ewah_bitmap.c:355) when running `git rev-list --test-bitmap HEAD` (and others if I don't have it die immediately). That seems to me that there is a check to ensure it doesn't run off the end. Perhaps you have assertions disabled so hit an error somewhere else?\n\n~~ Brian Gernhardt\n"},{"id":"233965","messageId":"CAPig+cS-ae3PGPGAAam6oKnFS4SxUOg2RE_7aUJrMyqE+sZvvw@mail.gmail.com","threadId":"35769","inReplyTo":"20140130215002.GB1130@sigill.intra.peff.net","subject":"Re: [PATCH] Ensure __BYTE_ORDER is always set","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2014-01-31T02:35:14Z","receivedAt":"2014-01-31T02:35:14Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Thu, Jan 30, 2014 at 4:50 PM, Jeff King wrote:\n> I think we could do this with something like the patch below, which\n> checks two things:\n>\n> 1. When we expand the ewah, it has the same number of bits we claimed\n> in the on-disk header.\n>\n> 2. The ewah header matches the number of objects in the packfile.\n>\n> The first catches a corruption in the ewah data itself, and the latter\n> when the header is corrupted. You can test either by breaking the\n> endian-swapping. :)\n>\n> diff --git a/pack-bitmap.c b/pack-bitmap.c\n> index ae0b57b..a31e529 100644\n> --- a/pack-bitmap.c\n> +++ b/pack-bitmap.c\n> @@ -130,6 +131,31 @@ static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index)\n> return NULL;\n> }\n>\n> + /*\n> + * It's OK for us to have too fewer bits than objects, as the EWAH\n\ns/fewer/few/\n\n> + * writer may have simply left off an ending that is all-zeroes.\n> + *\n> + * However it's not OK for us to have too many bits, as that would\n> + * entail touching objects that we don't have. We are careful\n> + * enough to avoid doing so in later code, but in the case of\n> + * nonsensical values, we would want to avoid even allocating\n> + * memory to hold the expanded bitmap.\n> + *\n> + * There is one exception: we may \"go over\" to round up to the next\n> + * 64-bit ewah word, since the storage comes in chunks of that size.\n> + */\n> + expected_bits = index->pack->num_objects;\n> + if (expected_bits & 63) {\n> + expected_bits &= ~63;\n> + expected_bits += 64;\n> + }\n> + if (b->bit_size > expected_bits) {\n> + error(\"unexpected number of bits in bitmap: %\"PRIuMAX\" > %\"PRIuMAX,\n> + (uintmax_t)b->bit_size, (uintmax_t)expected_bits);\n> + ewah_pool_free(b);\n> + return NULL;\n> + }\n> +\n> index->map_pos += bitmap_size;\n> return b;\n> }\n> --\n"}]}