{"thread":{"id":"48714","subject":"security: potential out-of-bound read at ewah_io.c |ewah_read_mmap|","startedAt":"2018-06-15T00:16:32Z","lastAt":"2018-06-19T19:56:55Z","messageCount":58,"participants":["Luat Nguyen","Jeff King","SZEDER Gábor","Derrick Stolee","Ramsay Jones","Junio C Hamano","Dyer, Edwin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"350221","messageId":"2067D731-C415-4D19-8CDA-90D7DC638397@l4w.io","threadId":"48714","inReplyTo":null,"subject":"security: potential out-of-bound read at ewah_io.c |ewah_read_mmap|","fromName":"Luat Nguyen","fromEmail":"root@l4w.io","sentAt":"2018-06-14T22:59:43Z","receivedAt":"2018-06-15T00:16:32Z","isPatch":false,"sender":{"key":"root@l4w.io","avatar":null},"body":"Hi folks,\n\nRecently, I’ve found a security issue related to out-of-bound read at function named `ewah_read_mmap`\n\nAssume that, an attacker can put malicious `./git/index` into a repo by somehow.\n\nSince there is lack of check whether the remaining size of `ptr`is equal to `buffer_size` or not.\n\nSo the code reads exceed the buffer of `ptr` and reach to higher page. In this case, it is `/lib/x86_64-linux-gnu/ld-2.23.so`.\n\nLeads to infoleak. You can find more details and asan crash below.\n\n\n\n# xxd .git/index\n00000000: 4449 5243 0000 0002 0000 0000 4653 4d4e DIRC........FSMN\n00000010: 0000 0024 0000 0001 1538 2489 c8fc 3616 ...$.....8$...6.\n00000020: 0000 0014 0000 0000 0000 2000 4141 .......... .AA\n ^ evil size here = 0x2000\n\n\n***** SNIP CODE *****\n\nint ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len)\n{\n… \n\tself->buffer_size = self->alloc_size = get_be32(ptr);\n\tptr += sizeof(uint32_t);\n… \n\tmemcpy(self->buffer, ptr, self->buffer_size * sizeof(eword_t));\n\n\n[memory map]\n\n 0x7f990eca3000 0x7f990eca4000 r--p 1000 0 /media/sf_Fuzz/vuln_repo/.git/index <— where `ptr` is placed\n 0x7f990eca4000 0x7f990eca5000 r--p 1000 25000 /lib/x86_64-linux-gnu/ld-2.23.so <— memcpy will reach here\n 0x7f990eca5000 0x7f990eca6000 rw-p 1000 26000 /lib/x86_64-linux-gnu/ld-2.23.so <— and here \n\n\n[ ASAN log ]\n\nroot@guest:/media/sf_SHARE/vuln_repo# /media/sf_SHARE/git-master-asan/git status\n=================================================================\n==4324==ERROR: AddressSanitizer: unknown-crash on address 0x7f6f235b0000 at pc 0x0000004bba79 bp 0x7ffc75e68850 sp 0x7ffc75e68000\nREAD of size 65536 at 0x7f6f235b0000 thread T0\n #0 0x4bba78 in __asan_memcpy /tmp/final/llvm.src/projects/compiler-rt/lib/asan/asan_interceptors_memintrinsics.cc:23:3\n #1 0x8c910e in ewah_read_mmap /media/sf_SHARE/git-master-asan/ewah/ewah_io.c:144:2\n #2 0x8e2534 in read_fsmonitor_extension /media/sf_SHARE/git-master-asan/fsmonitor.c:46:8\n #3 0xa05862 in read_index_extension /media/sf_SHARE/git-master-asan/read-cache.c:1615:3\n #4 0xa046f3 in do_read_index /media/sf_SHARE/git-master-asan/read-cache.c:1872:7\n #5 0xa03325 in read_index_from /media/sf_SHARE/git-master-asan/read-cache.c:1913:8\n #6 0xa03231 in read_index /media/sf_SHARE/git-master-asan/read-cache.c:1634:9\n #7 0x9de5e8 in read_index_preload /media/sf_SHARE/git-master-asan/preload-index.c:119:15\n #8 0x566cc6 in cmd_status /media/sf_SHARE/git-master-asan/builtin/commit.c:1358:2\n #9 0x4ede8c in run_builtin /media/sf_SHARE/git-master-asan/git.c:417:11\n #10 0x4ea939 in handle_builtin /media/sf_SHARE/git-master-asan/git.c:632:8\n #11 0x4ed655 in run_argv /media/sf_SHARE/git-master-asan/git.c:684:4\n #12 0x4ea037 in cmd_main /media/sf_SHARE/git-master-asan/git.c:761:19\n #13 0x759c8b in main /media/sf_SHARE/git-master-asan/common-main.c:45:9\n #14 0x7f6f2243382f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)\n #15 0x41c268 in _start (/media/sf_SHARE/git-master-asan/git+0x41c268)\n\nAddress 0x7f6f235b0000 is a wild pointer.\nSUMMARY: AddressSanitizer: unknown-crash /tmp/final/llvm.src/projects/compiler-rt/lib/asan/asan_interceptors_memintrinsics.cc:23:3 in __asan_memcpy\nShadow bytes around the buggy address:\n 0x0fee646adfb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n 0x0fee646adfc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n 0x0fee646adfd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n 0x0fee646adfe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n 0x0fee646adff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n=>0x0fee646ae000:[fe]fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe\n 0x0fee646ae010: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe\n 0x0fee646ae020: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe\n 0x0fee646ae030: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe\n 0x0fee646ae040: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe\n 0x0fee646ae050: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe\nShadow byte legend (one shadow byte represents 8 application bytes):\n Addressable: 00\n Partially addressable: 01 02 03 04 05 06 07\n Heap left redzone: fa\n Freed heap region: fd\n Stack left redzone: f1\n Stack mid redzone: f2\n Stack right redzone: f3\n Stack after return: f5\n Stack use after scope: f8\n Global redzone: f9\n Global init order: f6\n Poisoned by user: f7\n Container overflow: fc\n Array cookie: ac\n Intra object redzone: bb\n ASan internal: fe\n Left alloca redzone: ca\n Right alloca redzone: cb\n==4324==ABORTING\nroot@guest:/media/sf_SHARE/vuln_repo#\n\n\nRegards,\nLuat Nguyen."},{"id":"350223","messageId":"20180615032850.GA23241@sigill.intra.peff.net","threadId":"48714","inReplyTo":"2067D731-C415-4D19-8CDA-90D7DC638397@l4w.io","subject":"Re: security: potential out-of-bound read at ewah_io.c |ewah_read_mmap|","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-06-15T03:28:51Z","receivedAt":"2018-06-15T03:28:55Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jun 15, 2018 at 06:59:43AM +0800, Luat Nguyen wrote:\n\n> Recently, I’ve found a security issue related to out-of-bound read at function named `ewah_read_mmap`\n\nThanks, this is definitely a bug worth addressing. But note...\n\n> Assume that, an attacker can put malicious `./git/index` into a repo by somehow.\n\nWe generally don't consider .git/index (or pack .bitmap files, which\nalso use this implementation) to be a major part of Git's attack\nsurface, since they are generated locally. And if you can write to\nsomebody's .git directory, there are already much easier ways to execute\narbitrary code.\n\n> Since there is lack of check whether the remaining size of `ptr`is\n> equal to `buffer_size` or not.\n\nYep. We also fail to check if we even have enough bytes to read the\nbuffer_size in the first place.\n\nHere are some patches. The first one fixes the problem you found. The\nsecond one drops some dead code that has a related problem. And the\nthird just drops some dead code that I noticed in the same file. :)\n\n [1/3]: ewah_read_mmap: bounds-check mmap reads\n [2/3]: ewah: drop ewah_deserialize function\n [3/3]: ewah: drop ewah_serialize_native function\n\n ewah/ewah_io.c | 106 ++++++++--------------------------------\n ewah/ewok.h | 4 +-\n t/t5310-pack-bitmaps.sh | 13 +++++\n 3 files changed, 35 insertions(+), 88 deletions(-)\n\n-Peff\n"},{"id":"350224","messageId":"20180615033112.GA20390@sigill.intra.peff.net","threadId":"48714","inReplyTo":"20180615032850.GA23241@sigill.intra.peff.net","subject":"[PATCH 1/3] ewah_read_mmap: bounds-check mmap reads","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-06-15T03:31:13Z","receivedAt":"2018-06-15T03:31:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The on-disk ewah format tells us how big the ewah data is,\nand we blindly read that much from the buffer without\nconsidering whether the mmap'd data is long enough, which\ncan lead to out-of-bound reads.\n\nLet's make sure we have data available before reading it,\nboth for the ewah header/footer as well as for the bit data\nitself. In particular:\n\n - keep our ptr/len pair in sync as we move through the\n buffer, and check it before each read\n\n - check the size for integer overflow (this should be\n impossible on 64-bit, as the size is given as a 32-bit\n count of 8-byte words, but is possible on a 32-bit\n system)\n\n - return the number of bytes read as an ssize_t instead of\n an int, again to prevent integer overflow\n\n - compute the return value using a pointer difference;\n this should yield the same result as the existing code,\n but makes it more obvious that we got our computations\n right\n\nThe included test is far from comprehensive, as it just\npicks a static point at which to truncate the generated\nbitmap. But in practice this will hit in the middle of an\newah and make sure we're at least exercising this code.\n\nReported-by: Luat Nguyen \nSigned-off-by: Jeff King \n---\n ewah/ewah_io.c | 25 +++++++++++++++++++++----\n ewah/ewok.h | 2 +-\n t/t5310-pack-bitmaps.sh | 13 +++++++++++++\n 3 files changed, 35 insertions(+), 5 deletions(-)\n\ndiff --git a/ewah/ewah_io.c b/ewah/ewah_io.c\nindex bed1994551..33c08c40f8 100644\n--- a/ewah/ewah_io.c\n+++ b/ewah/ewah_io.c\n@@ -122,16 +122,23 @@ int ewah_serialize_strbuf(struct ewah_bitmap *self, struct strbuf *sb)\n \treturn ewah_serialize_to(self, write_strbuf, sb);\n }\n \n-int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len)\n+ssize_t ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len)\n {\n \tconst uint8_t *ptr = map;\n+\tsize_t data_len;\n \tsize_t i;\n \n+\tif (len < sizeof(uint32_t))\n+\t\treturn error(\"corrupt ewah bitmap: eof before bit size\");\n \tself->bit_size = get_be32(ptr);\n \tptr += sizeof(uint32_t);\n+\tlen -= sizeof(uint32_t);\n \n+\tif (len < sizeof(uint32_t))\n+\t\treturn error(\"corrupt ewah bitmap: eof before length\");\n \tself->buffer_size = self->alloc_size = get_be32(ptr);\n \tptr += sizeof(uint32_t);\n+\tlen -= sizeof(uint32_t);\n \n \tREALLOC_ARRAY(self->buffer, self->alloc_size);\n \n@@ -141,15 +148,25 @@ int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len)\n \t * the endianness conversion in a separate pass to ensure\n \t * we're loading 8-byte aligned words.\n \t */\n-\tmemcpy(self->buffer, ptr, self->buffer_size * sizeof(eword_t));\n-\tptr += self->buffer_size * sizeof(eword_t);\n+\tdata_len = st_mult(self->buffer_size, sizeof(eword_t));\n+\tif (len < data_len)\n+\t\treturn error(\"corrupt ewah bitmap: eof in data \"\n+\t\t\t \"(%\"PRIuMAX\" bytes short)\",\n+\t\t\t (uintmax_t)(data_len - len));\n+\tmemcpy(self->buffer, ptr, data_len);\n+\tptr += data_len;\n+\tlen -= data_len;\n \n \tfor (i = 0; i < self->buffer_size; ++i)\n \t\tself->buffer[i] = ntohll(self->buffer[i]);\n \n+\tif (len < sizeof(uint32_t))\n+\t\treturn error(\"corrupt ewah bitmap: eof before rlw\");\n \tself->rlw = self->buffer + get_be32(ptr);\n+\tptr += sizeof(uint32_t);\n+\tlen -= sizeof(uint32_t);\n \n-\treturn (3 * 4) + (self->buffer_size * 8);\n+\treturn ptr - (const uint8_t *)map;\n }\n \n int ewah_deserialize(struct ewah_bitmap *self, int fd)\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex dc43d05b64..357fd93c84 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -91,7 +91,7 @@ int ewah_serialize_native(struct ewah_bitmap *self, int fd);\n int ewah_serialize_strbuf(struct ewah_bitmap *self, struct strbuf *);\n \n int ewah_deserialize(struct ewah_bitmap *self, int fd);\n-int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len);\n+ssize_t ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len);\n \n uint32_t ewah_checksum(struct ewah_bitmap *self);\n \ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex 423c0a475f..237ee6e5fc 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -331,4 +331,17 @@ test_expect_success 'pack reuse respects --incremental' '\n \tgit show-index actual &&\n \ttest_cmp expect actual\n '\n+\n+test_expect_success 'truncated bitmap fails gracefully' '\n+\tgit repack -ad &&\n+\tgit rev-list --use-bitmap-index --count --all >expect &&\n+\tbitmap=$(ls .git/objects/pack/*.bitmap) &&\n+\ttest_when_finished \"rm -f $bitmap\" &&\n+\thead -c 512 <$bitmap >$bitmap.tmp &&\n+\tmv $bitmap.tmp $bitmap &&\n+\tgit rev-list --use-bitmap-index --count --all >actual 2>stderr &&\n+\ttest_cmp expect actual &&\n+\ttest_i18ngrep corrupt stderr\n+'\n+\n test_done\n-- \n2.18.0.rc2.534.g53d976aeb8\n\n"},{"id":"350225","messageId":"20180615033157.GB20390@sigill.intra.peff.net","threadId":"48714","inReplyTo":"20180615032850.GA23241@sigill.intra.peff.net","subject":"[PATCH 2/3] ewah: drop ewah_deserialize function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-06-15T03:31:58Z","receivedAt":"2018-06-15T03:32:02Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We don't call this function, and in fact never have since it\nwas added (at least not in iterations of the ewah patches\nthat got merged). Instead we use ewah_read_mmap().\n\nLet's drop the unused code.\n\nNote to anybody who later wants to resurrect this: it does\nnot check for integer overflow in the ewah data size,\nmeaning it may be possible to convince the code to allocate\na too-small buffer and read() into it.\n\nSigned-off-by: Jeff King \n---\n ewah/ewah_io.c | 55 --------------------------------------------------\n ewah/ewok.h | 1 -\n 2 files changed, 56 deletions(-)\n\ndiff --git a/ewah/ewah_io.c b/ewah/ewah_io.c\nindex 33c08c40f8..97c74266da 100644\n--- a/ewah/ewah_io.c\n+++ b/ewah/ewah_io.c\n@@ -168,58 +168,3 @@ ssize_t ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len)\n \n \treturn ptr - (const uint8_t *)map;\n }\n-\n-int ewah_deserialize(struct ewah_bitmap *self, int fd)\n-{\n-\tsize_t i;\n-\teword_t dump[2048];\n-\tconst size_t words_per_dump = sizeof(dump) / sizeof(eword_t);\n-\tuint32_t bitsize, word_count, rlw_pos;\n-\n-\teword_t *buffer = NULL;\n-\tsize_t words_left;\n-\n-\tewah_clear(self);\n-\n-\t/* 32 bit -- bit size for the map */\n-\tif (read(fd, &bitsize, 4) != 4)\n-\t\treturn -1;\n-\n-\tself->bit_size = (size_t)ntohl(bitsize);\n-\n-\t/** 32 bit -- number of compressed 64-bit words */\n-\tif (read(fd, &word_count, 4) != 4)\n-\t\treturn -1;\n-\n-\tself->buffer_size = self->alloc_size = (size_t)ntohl(word_count);\n-\tREALLOC_ARRAY(self->buffer, self->alloc_size);\n-\n-\t/** 64 bit x N -- compressed words */\n-\tbuffer = self->buffer;\n-\twords_left = self->buffer_size;\n-\n-\twhile (words_left >= words_per_dump) {\n-\t\tif (read(fd, dump, sizeof(dump)) != sizeof(dump))\n-\t\t\treturn -1;\n-\n-\t\tfor (i = 0; i < words_per_dump; ++i, ++buffer)\n-\t\t\t*buffer = ntohll(dump[i]);\n-\n-\t\twords_left -= words_per_dump;\n-\t}\n-\n-\tif (words_left) {\n-\t\tif (read(fd, dump, words_left * 8) != words_left * 8)\n-\t\t\treturn -1;\n-\n-\t\tfor (i = 0; i < words_left; ++i, ++buffer)\n-\t\t\t*buffer = ntohll(dump[i]);\n-\t}\n-\n-\t/** 32 bit -- position for the RLW */\n-\tif (read(fd, &rlw_pos, 4) != 4)\n-\t\treturn -1;\n-\n-\tself->rlw = self->buffer + ntohl(rlw_pos);\n-\treturn 0;\n-}\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex 357fd93c84..7e25ca2e61 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -90,7 +90,6 @@ int ewah_serialize(struct ewah_bitmap *self, int fd);\n int ewah_serialize_native(struct ewah_bitmap *self, int fd);\n int ewah_serialize_strbuf(struct ewah_bitmap *self, struct strbuf *);\n \n-int ewah_deserialize(struct ewah_bitmap *self, int fd);\n ssize_t ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len);\n \n uint32_t ewah_checksum(struct ewah_bitmap *self);\n-- \n2.18.0.rc2.534.g53d976aeb8\n\n"},{"id":"350226","messageId":"20180615033228.GC20390@sigill.intra.peff.net","threadId":"48714","inReplyTo":"20180615032850.GA23241@sigill.intra.peff.net","subject":"[PATCH 3/3] ewah: drop ewah_serialize_native function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-06-15T03:32:28Z","receivedAt":"2018-06-15T03:32:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We don't call this function, and never have. The on-disk\nbitmap format uses network-byte-order integers, meaning that\nwe cannot use the native-byte-order format written here.\n\nLet's drop it in the name of simplicity.\n\nSigned-off-by: Jeff King \n---\n ewah/ewah_io.c | 26 --------------------------\n ewah/ewok.h | 1 -\n 2 files changed, 27 deletions(-)\n\ndiff --git a/ewah/ewah_io.c b/ewah/ewah_io.c\nindex 97c74266da..586396122f 100644\n--- a/ewah/ewah_io.c\n+++ b/ewah/ewah_io.c\n@@ -20,32 +20,6 @@\n #include \"ewok.h\"\n #include \"strbuf.h\"\n \n-int ewah_serialize_native(struct ewah_bitmap *self, int fd)\n-{\n-\tuint32_t write32;\n-\tsize_t to_write = self->buffer_size * 8;\n-\n-\t/* 32 bit -- bit size for the map */\n-\twrite32 = (uint32_t)self->bit_size;\n-\tif (write(fd, &write32, 4) != 4)\n-\t\treturn -1;\n-\n-\t/** 32 bit -- number of compressed 64-bit words */\n-\twrite32 = (uint32_t)self->buffer_size;\n-\tif (write(fd, &write32, 4) != 4)\n-\t\treturn -1;\n-\n-\tif (write(fd, self->buffer, to_write) != to_write)\n-\t\treturn -1;\n-\n-\t/** 32 bit -- position for the RLW */\n-\twrite32 = self->rlw - self->buffer;\n-\tif (write(fd, &write32, 4) != 4)\n-\t\treturn -1;\n-\n-\treturn (3 * 4) + to_write;\n-}\n-\n int ewah_serialize_to(struct ewah_bitmap *self,\n \t\t int (*write_fun)(void *, const void *, size_t),\n \t\t void *data)\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex 7e25ca2e61..e6102e6c75 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -87,7 +87,6 @@ int ewah_serialize_to(struct ewah_bitmap *self,\n \t\t int (*write_fun)(void *out, const void *buf, size_t len),\n \t\t void *out);\n int ewah_serialize(struct ewah_bitmap *self, int fd);\n-int ewah_serialize_native(struct ewah_bitmap *self, int fd);\n int ewah_serialize_strbuf(struct ewah_bitmap *self, struct strbuf *);\n \n ssize_t ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len);\n-- \n2.18.0.rc2.534.g53d976aeb8\n"},{"id":"350227","messageId":"20180615034442.GA14422@sigill.intra.peff.net","threadId":"48714","inReplyTo":"20180615032850.GA23241@sigill.intra.peff.net","subject":"[PATCH 4/3] ewah: adjust callers of ewah_read_mmap()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-06-15T03:44:43Z","receivedAt":"2018-06-15T03:44:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 14, 2018 at 11:28:50PM -0400, Jeff King wrote:\n\n> Yep. We also fail to check if we even have enough bytes to read the\n> buffer_size in the first place.\n> \n> Here are some patches. The first one fixes the problem you found. The\n> second one drops some dead code that has a related problem. And the\n> third just drops some dead code that I noticed in the same file. :)\n> \n> [1/3]: ewah_read_mmap: bounds-check mmap reads\n> [2/3]: ewah: drop ewah_deserialize function\n> [3/3]: ewah: drop ewah_serialize_native function\n\nActually, we'd want this one on top. Arguably it could be squashed into\npatch 1.\n\n-- >8 --\nSubject: ewah: adjust callers of ewah_read_mmap()\n\nThe return value of ewah_read_mmap() is now an ssize_t,\nsince we could (in theory) process up to 32GB of data. This\nwould never happen in practice, but a corrupt or malicious\n.bitmap or index file could convince us to do so.\n\nLet's make sure that we don't stuff the value into an int,\nwhich would cause us to incorrectly move our pointer\nforward. We'd always move too little, since negative values\nare used for reporting errors. So the worst case is just\nthat we end up reporting a corrupt file, not an\nout-of-bounds read.\n\nSigned-off-by: Jeff King \n---\n dir.c | 3 ++-\n pack-bitmap.c | 2 +-\n 2 files changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 61b513a078..d5185660f1 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -2725,7 +2725,8 @@ struct untracked_cache *read_untracked_extension(const void *data, unsigned long\n \tstruct read_data rd;\n \tconst unsigned char *next = data, *end = (const unsigned char *)data + sz;\n \tconst char *ident;\n-\tint ident_len, len;\n+\tint ident_len;\n+\tssize_t len;\n \tconst char *exclude_per_dir;\n \n \tif (sz <= 1 || end[-1] != '\\0')\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 369bf69d75..2f27b10e35 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -125,7 +125,7 @@ static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index)\n {\n \tstruct ewah_bitmap *b = ewah_pool_new();\n \n-\tint bitmap_size = ewah_read_mmap(b,\n+\tssize_t bitmap_size = ewah_read_mmap(b,\n \t\tindex->map + index->map_pos,\n \t\tindex->map_size - index->map_pos);\n \n-- \n2.18.0.rc2.534.g53d976aeb8\n\n"},{"id":"350243","messageId":"20180615091432.7155-1-szeder.dev@gmail.com","threadId":"48714","inReplyTo":"20180615033112.GA20390@sigill.intra.peff.net","subject":"Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2018-06-15T09:14:32Z","receivedAt":"2018-06-15T09:14:43Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"> diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\n> index 423c0a475f..237ee6e5fc 100755\n> --- a/t/t5310-pack-bitmaps.sh\n> +++ b/t/t5310-pack-bitmaps.sh\n> @@ -331,4 +331,17 @@ test_expect_success 'pack reuse respects --incremental' '\n> \tgit show-index actual &&\n> \ttest_cmp expect actual\n> '\n> +\n> +test_expect_success 'truncated bitmap fails gracefully' '\n> +\tgit repack -ad &&\n> +\tgit rev-list --use-bitmap-index --count --all >expect &&\n> +\tbitmap=$(ls .git/objects/pack/*.bitmap) &&\n\nI think the 'ls' is unnecessary and this would do:\n\n bitmap=.git/objects/pack/*.bitmap\n\n> +\ttest_when_finished \"rm -f $bitmap\" &&\n> +\thead -c 512 <$bitmap >$bitmap.tmp &&\n> +\tmv $bitmap.tmp $bitmap &&\n> +\tgit rev-list --use-bitmap-index --count --all >actual 2>stderr &&\n> +\ttest_cmp expect actual &&\n> +\ttest_i18ngrep corrupt stderr\n> +'\n> +\n> test_done\n> -- \n> 2.18.0.rc2.534.g53d976aeb8\n> \n> \n"},{"id":"350245","messageId":"f6931351-df79-cb76-ee29-c57472a6a201@gmail.com","threadId":"48714","inReplyTo":"20180615034442.GA14422@sigill.intra.peff.net","subject":"Re: [PATCH 4/3] ewah: adjust callers of ewah_read_mmap()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-06-15T11:23:15Z","receivedAt":"2018-06-15T11:23:21Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/14/2018 11:44 PM, Jeff King wrote:\n> The return value of ewah_read_mmap() is now an ssize_t,\n> since we could (in theory) process up to 32GB of data. This\n> would never happen in practice, but a corrupt or malicious\n> .bitmap or index file could convince us to do so.\n\nAside: Why a 32GB limit? Usually I see 32-bit issues limiting by 2 \n(signed) or 4 GB (unsigned). Is there something specifically in the \nbitmap format that stops at this size?\n\nThanks,\n-Stolee\n\n"},{"id":"350246","messageId":"afbd5335-ef0d-5ca5-84ab-bdfa8bdc50bb@ramsayjones.plus.com","threadId":"48714","inReplyTo":"20180615033228.GC20390@sigill.intra.peff.net","subject":"Re: [PATCH 3/3] ewah: drop ewah_serialize_native function","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsayjones.plus.com","sentAt":"2018-06-15T13:56:41Z","receivedAt":"2018-06-15T13:56:48Z","isPatch":true,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"\n\nOn 15/06/18 04:32, Jeff King wrote:\n> We don't call this function, and never have. The on-disk\n> bitmap format uses network-byte-order integers, meaning that\n> we cannot use the native-byte-order format written here.\n> \n> Let's drop it in the name of simplicity.\n\nHmm, if you are in the mood to drop ewah dead code, how about:\n\n ewah/bitmap.o - bitmap_clear\n ewah/bitmap.o - bitmap_each_bit\n ewah/ewah_bitmap.o - ewah_and\n ewah/ewah_bitmap.o - ewah_and_not\n ewah/ewah_bitmap.o - ewah_not\n ewah/ewah_bitmap.o - ewah_or\n\n... in addition to these *(de)serialize* functions. ;-)\n\nATB,\nRamsay Jones\n\n"},{"id":"350247","messageId":"f25c0798-7778-7146-5349-ae2c2fb560dd@ramsayjones.plus.com","threadId":"48714","inReplyTo":"afbd5335-ef0d-5ca5-84ab-bdfa8bdc50bb@ramsayjones.plus.com","subject":"Re: [PATCH 3/3] ewah: drop ewah_serialize_native function","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsayjones.plus.com","sentAt":"2018-06-15T14:07:16Z","receivedAt":"2018-06-15T14:07:21Z","isPatch":true,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"\n\nOn 15/06/18 14:56, Ramsay Jones wrote:\n> \n> \n> On 15/06/18 04:32, Jeff King wrote:\n>> We don't call this function, and never have. The on-disk\n>> bitmap format uses network-byte-order integers, meaning that\n>> we cannot use the native-byte-order format written here.\n>>\n>> Let's drop it in the name of simplicity.\n> \n> Hmm, if you are in the mood to drop ewah dead code, how about:\n> \n> ewah/bitmap.o - bitmap_clear\n> ewah/bitmap.o - bitmap_each_bit\n> ewah/ewah_bitmap.o - ewah_and\n> ewah/ewah_bitmap.o - ewah_and_not\n> ewah/ewah_bitmap.o - ewah_not\n> ewah/ewah_bitmap.o - ewah_or\n> \n> ... in addition to these *(de)serialize* functions. ;-)\n\nHmm, I didn't spot it at first, but ewah_serialize() also\nseems to be unused!\n\nATB,\nRamsay Jones\n\n"},{"id":"350248","messageId":"ab6378a8-3728-7fa8-da08-b58ec768dbfe@gmail.com","threadId":"48714","inReplyTo":"afbd5335-ef0d-5ca5-84ab-bdfa8bdc50bb@ramsayjones.plus.com","subject":"Re: [PATCH 3/3] ewah: drop ewah_serialize_native function","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-06-15T14:15:50Z","receivedAt":"2018-06-15T14:15:56Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/15/2018 9:56 AM, Ramsay Jones wrote:\n>\n> On 15/06/18 04:32, Jeff King wrote:\n>> We don't call this function, and never have. The on-disk\n>> bitmap format uses network-byte-order integers, meaning that\n>> we cannot use the native-byte-order format written here.\n>>\n>> Let's drop it in the name of simplicity.\n> Hmm, if you are in the mood to drop ewah dead code, how about:\n>\n> ewah/bitmap.o - bitmap_clear\n> ewah/bitmap.o - bitmap_each_bit\n> ewah/ewah_bitmap.o - ewah_and\n> ewah/ewah_bitmap.o - ewah_and_not\n> ewah/ewah_bitmap.o - ewah_not\n> ewah/ewah_bitmap.o - ewah_or\n>\n> ... in addition to these *(de)serialize* functions. ;-)\n>\n\nNormally, I would say we should keep this folder as close to the \n\"original\" [1] as possible, so we could more easily take improvements to \nthat library. However, it appears that code is not being updated. \nPerhaps this is in favor of other EWAH libraries [2] or other compressed \nbitmap formats [3].\n\nFor that reason, I agree we should clean this up. We shouldn't block \nPeff's patch for that reason. I'll send a patch that deletes these methods.\n\nThanks,\n-Stolee:\n\n[1] https://github.com/vmg/libewok\n\n[2] https://github.com/lemire/EWAHBoolArray\n\n[3] https://github.com/RoaringBitmap/CRoaring\n"},{"id":"350249","messageId":"20180615143018.170686-1-dstolee@microsoft.com","threadId":"48714","inReplyTo":"f25c0798-7778-7146-5349-ae2c2fb560dd@ramsayjones.plus.com","subject":"[PATCH 0/8] Delete unused methods in EWAH bitmap","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-15T14:30:29Z","receivedAt":"2018-06-15T14:30:35Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"The EWAH bitmap code includes several logical operations that are\nimportant for a general-purpose bitmap library. However, Git only\nuses the XOR operation for storing deltas between reachability\nbitmaps. This means that we can delete the following unused methods:\n\n* ewah_and()\n* ewah_and_not()\n* ewah_not()\n* ewah_or()\n* ewah_serialize()\n* ewah_serialize_native()\n\nWe can also delete the unused methods bitmap_clear() and\nbitmap_each_bit().\n\nDerrick Stolee (8):\n ewah/bitmap.c: delete unused 'bitmap_clear()'\n ewah/bitmap.c: delete unused 'bitmap_each_bit()'\n ewah_bitmap: delete unused 'ewah_and()'\n ewah_bitmap: delete unused 'ewah_and_not()'\n ewah_bitmap: delete unused 'ewah_not()'\n ewah_bitmap: delete unused 'ewah_or()'\n ewah_io: delete unused 'ewah_serialize()'\n ewah_io: delete unused 'ewah_serialize_native()'\n\n ewah/bitmap.c | 32 -------\n ewah/ewah_bitmap.c | 229 ---------------------------------------------\n ewah/ewah_io.c | 36 -------\n ewah/ewok.h | 24 -----\n 4 files changed, 321 deletions(-)\n\n\nbase-commit: fc54c1af3ec09bab8b8ea09768c2da4069b7f53e\n-- \n2.18.0.rc1\n\n"},{"id":"350250","messageId":"20180615143018.170686-3-dstolee@microsoft.com","threadId":"48714","inReplyTo":"20180615143018.170686-1-dstolee@microsoft.com","subject":"[PATCH 2/8] ewah/bitmap.c: delete unused 'bitmap_each_bit()'","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-15T14:30:32Z","receivedAt":"2018-06-15T14:30:38Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Reported-by: Ramsay Jones \nSigned-off-by: Derrick Stolee \n---\n ewah/bitmap.c | 24 ------------------------\n 1 file changed, 24 deletions(-)\n\ndiff --git a/ewah/bitmap.c b/ewah/bitmap.c\nindex d61dc6114a..52f1178db4 100644\n--- a/ewah/bitmap.c\n+++ b/ewah/bitmap.c\n@@ -129,30 +129,6 @@ void bitmap_or_ewah(struct bitmap *self, struct ewah_bitmap *other)\n \t\tself->words[i++] |= word;\n }\n \n-void bitmap_each_bit(struct bitmap *self, ewah_callback callback, void *data)\n-{\n-\tsize_t pos = 0, i;\n-\n-\tfor (i = 0; i < self->word_alloc; ++i) {\n-\t\teword_t word = self->words[i];\n-\t\tuint32_t offset;\n-\n-\t\tif (word == (eword_t)~0) {\n-\t\t\tfor (offset = 0; offset < BITS_IN_EWORD; ++offset)\n-\t\t\t\tcallback(pos++, data);\n-\t\t} else {\n-\t\t\tfor (offset = 0; offset < BITS_IN_EWORD; ++offset) {\n-\t\t\t\tif ((word >> offset) == 0)\n-\t\t\t\t\tbreak;\n-\n-\t\t\t\toffset += ewah_bit_ctz64(word >> offset);\n-\t\t\t\tcallback(pos + offset, data);\n-\t\t\t}\n-\t\t\tpos += BITS_IN_EWORD;\n-\t\t}\n-\t}\n-}\n-\n size_t bitmap_popcount(struct bitmap *self)\n {\n \tsize_t i, count = 0;\n-- \n2.18.0.rc1\n\n"},{"id":"350251","messageId":"20180615143018.170686-5-dstolee@microsoft.com","threadId":"48714","inReplyTo":"20180615143018.170686-1-dstolee@microsoft.com","subject":"[PATCH 4/8] ewah_bitmap: delete unused 'ewah_and_not()'","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-15T14:30:35Z","receivedAt":"2018-06-15T14:30:41Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Reported-by: Ramsay Jones \nSigned-off-by: Derrick Stolee \n---\n ewah/ewah_bitmap.c | 73 ----------------------------------------------\n ewah/ewok.h | 5 ----\n 2 files changed, 78 deletions(-)\n\ndiff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\nindex 5a4d3a6eb6..559adde37c 100644\n--- a/ewah/ewah_bitmap.c\n+++ b/ewah/ewah_bitmap.c\n@@ -459,79 +459,6 @@ void ewah_xor(\n \tout->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);\n }\n \n-void ewah_and_not(\n-\tstruct ewah_bitmap *ewah_i,\n-\tstruct ewah_bitmap *ewah_j,\n-\tstruct ewah_bitmap *out)\n-{\n-\tstruct rlw_iterator rlw_i;\n-\tstruct rlw_iterator rlw_j;\n-\tsize_t literals;\n-\n-\trlwit_init(&rlw_i, ewah_i);\n-\trlwit_init(&rlw_j, ewah_j);\n-\n-\twhile (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {\n-\t\twhile (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {\n-\t\t\tstruct rlw_iterator *prey, *predator;\n-\n-\t\t\tif (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {\n-\t\t\t\tprey = &rlw_i;\n-\t\t\t\tpredator = &rlw_j;\n-\t\t\t} else {\n-\t\t\t\tprey = &rlw_j;\n-\t\t\t\tpredator = &rlw_i;\n-\t\t\t}\n-\n-\t\t\tif ((predator->rlw.running_bit && prey == &rlw_i) ||\n-\t\t\t\t(!predator->rlw.running_bit && prey != &rlw_i)) {\n-\t\t\t\tewah_add_empty_words(out, 0,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t\trlwit_discard_first_words(prey,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t\trlwit_discard_first_words(predator,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t} else {\n-\t\t\t\tsize_t index;\n-\t\t\t\tint negate_words;\n-\n-\t\t\t\tnegate_words = (&rlw_i != prey);\n-\t\t\t\tindex = rlwit_discharge(prey, out,\n-\t\t\t\t\tpredator->rlw.running_len, negate_words);\n-\t\t\t\tewah_add_empty_words(out, negate_words,\n-\t\t\t\t\tpredator->rlw.running_len - index);\n-\t\t\t\trlwit_discard_first_words(predator,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t}\n-\t\t}\n-\n-\t\tliterals = min_size(\n-\t\t\trlw_i.rlw.literal_words,\n-\t\t\trlw_j.rlw.literal_words);\n-\n-\t\tif (literals) {\n-\t\t\tsize_t k;\n-\n-\t\t\tfor (k = 0; k < literals; ++k) {\n-\t\t\t\tewah_add(out,\n-\t\t\t\t\trlw_i.buffer[rlw_i.literal_word_start + k] &\n-\t\t\t\t\t~(rlw_j.buffer[rlw_j.literal_word_start + k])\n-\t\t\t\t);\n-\t\t\t}\n-\n-\t\t\trlwit_discard_first_words(&rlw_i, literals);\n-\t\t\trlwit_discard_first_words(&rlw_j, literals);\n-\t\t}\n-\t}\n-\n-\tif (rlwit_word_size(&rlw_i) > 0)\n-\t\trlwit_discharge(&rlw_i, out, ~0, 0);\n-\telse\n-\t\trlwit_discharge_empty(&rlw_j, out);\n-\n-\tout->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);\n-}\n-\n void ewah_or(\n \tstruct ewah_bitmap *ewah_i,\n \tstruct ewah_bitmap *ewah_j,\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex 5841c83507..21c420770e 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -169,11 +169,6 @@ void ewah_or(\n \tstruct ewah_bitmap *ewah_j,\n \tstruct ewah_bitmap *out);\n \n-void ewah_and_not(\n-\tstruct ewah_bitmap *ewah_i,\n-\tstruct ewah_bitmap *ewah_j,\n-\tstruct ewah_bitmap *out);\n-\n void ewah_xor(\n \tstruct ewah_bitmap *ewah_i,\n \tstruct ewah_bitmap *ewah_j,\n-- \n2.18.0.rc1\n\n"},{"id":"350252","messageId":"20180615143018.170686-7-dstolee@microsoft.com","threadId":"48714","inReplyTo":"20180615143018.170686-1-dstolee@microsoft.com","subject":"[PATCH 6/8] ewah_bitmap: delete unused 'ewah_or()'","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-15T14:30:38Z","receivedAt":"2018-06-15T14:30:45Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Reported-by: Ramsay Jones \nSigned-off-by: Derrick Stolee \n---\n ewah/ewah_bitmap.c | 69 ----------------------------------------------\n ewah/ewok.h | 5 ----\n 2 files changed, 74 deletions(-)\n\ndiff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\nindex 3fa3edf2a3..017c677f98 100644\n--- a/ewah/ewah_bitmap.c\n+++ b/ewah/ewah_bitmap.c\n@@ -440,75 +440,6 @@ void ewah_xor(\n \tout->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);\n }\n \n-void ewah_or(\n-\tstruct ewah_bitmap *ewah_i,\n-\tstruct ewah_bitmap *ewah_j,\n-\tstruct ewah_bitmap *out)\n-{\n-\tstruct rlw_iterator rlw_i;\n-\tstruct rlw_iterator rlw_j;\n-\tsize_t literals;\n-\n-\trlwit_init(&rlw_i, ewah_i);\n-\trlwit_init(&rlw_j, ewah_j);\n-\n-\twhile (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {\n-\t\twhile (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {\n-\t\t\tstruct rlw_iterator *prey, *predator;\n-\n-\t\t\tif (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {\n-\t\t\t\tprey = &rlw_i;\n-\t\t\t\tpredator = &rlw_j;\n-\t\t\t} else {\n-\t\t\t\tprey = &rlw_j;\n-\t\t\t\tpredator = &rlw_i;\n-\t\t\t}\n-\n-\t\t\tif (predator->rlw.running_bit) {\n-\t\t\t\tewah_add_empty_words(out, 0,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t\trlwit_discard_first_words(prey,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t\trlwit_discard_first_words(predator,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t} else {\n-\t\t\t\tsize_t index = rlwit_discharge(prey, out,\n-\t\t\t\t\tpredator->rlw.running_len, 0);\n-\t\t\t\tewah_add_empty_words(out, 0,\n-\t\t\t\t\tpredator->rlw.running_len - index);\n-\t\t\t\trlwit_discard_first_words(predator,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t}\n-\t\t}\n-\n-\t\tliterals = min_size(\n-\t\t\trlw_i.rlw.literal_words,\n-\t\t\trlw_j.rlw.literal_words);\n-\n-\t\tif (literals) {\n-\t\t\tsize_t k;\n-\n-\t\t\tfor (k = 0; k < literals; ++k) {\n-\t\t\t\tewah_add(out,\n-\t\t\t\t\trlw_i.buffer[rlw_i.literal_word_start + k] |\n-\t\t\t\t\trlw_j.buffer[rlw_j.literal_word_start + k]\n-\t\t\t\t);\n-\t\t\t}\n-\n-\t\t\trlwit_discard_first_words(&rlw_i, literals);\n-\t\t\trlwit_discard_first_words(&rlw_j, literals);\n-\t\t}\n-\t}\n-\n-\tif (rlwit_word_size(&rlw_i) > 0)\n-\t\trlwit_discharge(&rlw_i, out, ~0, 0);\n-\telse\n-\t\trlwit_discharge(&rlw_j, out, ~0, 0);\n-\n-\tout->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);\n-}\n-\n-\n #define BITMAP_POOL_MAX 16\n static struct ewah_bitmap *bitmap_pool[BITMAP_POOL_MAX];\n static size_t bitmap_pool_size;\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex 4b665d09d9..cd826a0136 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -157,11 +157,6 @@ void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent);\n */\n int ewah_iterator_next(eword_t *next, struct ewah_iterator *it);\n \n-void ewah_or(\n-\tstruct ewah_bitmap *ewah_i,\n-\tstruct ewah_bitmap *ewah_j,\n-\tstruct ewah_bitmap *out);\n-\n void ewah_xor(\n \tstruct ewah_bitmap *ewah_i,\n \tstruct ewah_bitmap *ewah_j,\n-- \n2.18.0.rc1\n\n"},{"id":"350253","messageId":"20180615143018.170686-9-dstolee@microsoft.com","threadId":"48714","inReplyTo":"20180615143018.170686-1-dstolee@microsoft.com","subject":"[PATCH 8/8] ewah_io: delete unused 'ewah_serialize_native()'","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-15T14:30:41Z","receivedAt":"2018-06-15T14:30:48Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Signed-off-by: Derrick Stolee \n---\n ewah/ewah_io.c | 26 --------------------------\n ewah/ewok.h | 1 -\n 2 files changed, 27 deletions(-)\n\ndiff --git a/ewah/ewah_io.c b/ewah/ewah_io.c\nindex 86d3f1d02e..dde736bcd9 100644\n--- a/ewah/ewah_io.c\n+++ b/ewah/ewah_io.c\n@@ -20,32 +20,6 @@\n #include \"ewok.h\"\n #include \"strbuf.h\"\n \n-int ewah_serialize_native(struct ewah_bitmap *self, int fd)\n-{\n-\tuint32_t write32;\n-\tsize_t to_write = self->buffer_size * 8;\n-\n-\t/* 32 bit -- bit size for the map */\n-\twrite32 = (uint32_t)self->bit_size;\n-\tif (write(fd, &write32, 4) != 4)\n-\t\treturn -1;\n-\n-\t/** 32 bit -- number of compressed 64-bit words */\n-\twrite32 = (uint32_t)self->buffer_size;\n-\tif (write(fd, &write32, 4) != 4)\n-\t\treturn -1;\n-\n-\tif (write(fd, self->buffer, to_write) != to_write)\n-\t\treturn -1;\n-\n-\t/** 32 bit -- position for the RLW */\n-\twrite32 = self->rlw - self->buffer;\n-\tif (write(fd, &write32, 4) != 4)\n-\t\treturn -1;\n-\n-\treturn (3 * 4) + to_write;\n-}\n-\n int ewah_serialize_to(struct ewah_bitmap *self,\n \t\t int (*write_fun)(void *, const void *, size_t),\n \t\t void *data)\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex 1055706e44..8a2b334278 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -86,7 +86,6 @@ void ewah_free(struct ewah_bitmap *self);\n int ewah_serialize_to(struct ewah_bitmap *self,\n \t\t int (*write_fun)(void *out, const void *buf, size_t len),\n \t\t void *out);\n-int ewah_serialize_native(struct ewah_bitmap *self, int fd);\n int ewah_serialize_strbuf(struct ewah_bitmap *self, struct strbuf *);\n \n int ewah_deserialize(struct ewah_bitmap *self, int fd);\n-- \n2.18.0.rc1\n\n"},{"id":"350254","messageId":"20180615143018.170686-2-dstolee@microsoft.com","threadId":"48714","inReplyTo":"20180615143018.170686-1-dstolee@microsoft.com","subject":"[PATCH 1/8] ewah/bitmap.c: delete unused 'bitmap_clear()'","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-15T14:30:31Z","receivedAt":"2018-06-15T14:30:50Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Reported-by: Ramsay Jones \nSigned-off-by: Derrick Stolee \n---\n ewah/bitmap.c | 8 --------\n 1 file changed, 8 deletions(-)\n\ndiff --git a/ewah/bitmap.c b/ewah/bitmap.c\nindex 756bdd050e..d61dc6114a 100644\n--- a/ewah/bitmap.c\n+++ b/ewah/bitmap.c\n@@ -45,14 +45,6 @@ void bitmap_set(struct bitmap *self, size_t pos)\n \tself->words[block] |= EWAH_MASK(pos);\n }\n \n-void bitmap_clear(struct bitmap *self, size_t pos)\n-{\n-\tsize_t block = EWAH_BLOCK(pos);\n-\n-\tif (block < self->word_alloc)\n-\t\tself->words[block] &= ~EWAH_MASK(pos);\n-}\n-\n int bitmap_get(struct bitmap *self, size_t pos)\n {\n \tsize_t block = EWAH_BLOCK(pos);\n-- \n2.18.0.rc1\n\n"},{"id":"350255","messageId":"20180615143018.170686-8-dstolee@microsoft.com","threadId":"48714","inReplyTo":"20180615143018.170686-1-dstolee@microsoft.com","subject":"[PATCH 7/8] ewah_io: delete unused 'ewah_serialize()'","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-15T14:30:40Z","receivedAt":"2018-06-15T14:30:53Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Reported-by: Ramsay Jones \nSigned-off-by: Derrick Stolee \n---\n ewah/ewah_io.c | 10 ----------\n ewah/ewok.h | 1 -\n 2 files changed, 11 deletions(-)\n\ndiff --git a/ewah/ewah_io.c b/ewah/ewah_io.c\nindex bed1994551..86d3f1d02e 100644\n--- a/ewah/ewah_io.c\n+++ b/ewah/ewah_io.c\n@@ -100,16 +100,6 @@ int ewah_serialize_to(struct ewah_bitmap *self,\n \treturn (3 * 4) + (self->buffer_size * 8);\n }\n \n-static int write_helper(void *fd, const void *buf, size_t len)\n-{\n-\treturn write((intptr_t)fd, buf, len);\n-}\n-\n-int ewah_serialize(struct ewah_bitmap *self, int fd)\n-{\n-\treturn ewah_serialize_to(self, write_helper, (void *)(intptr_t)fd);\n-}\n-\n static int write_strbuf(void *user_data, const void *data, size_t len)\n {\n \tstruct strbuf *sb = user_data;\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex cd826a0136..1055706e44 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -86,7 +86,6 @@ void ewah_free(struct ewah_bitmap *self);\n int ewah_serialize_to(struct ewah_bitmap *self,\n \t\t int (*write_fun)(void *out, const void *buf, size_t len),\n \t\t void *out);\n-int ewah_serialize(struct ewah_bitmap *self, int fd);\n int ewah_serialize_native(struct ewah_bitmap *self, int fd);\n int ewah_serialize_strbuf(struct ewah_bitmap *self, struct strbuf *);\n \n-- \n2.18.0.rc1\n\n"},{"id":"350256","messageId":"20180615143018.170686-4-dstolee@microsoft.com","threadId":"48714","inReplyTo":"20180615143018.170686-1-dstolee@microsoft.com","subject":"[PATCH 3/8] ewah_bitmap: delete unused 'ewah_and()'","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-15T14:30:34Z","receivedAt":"2018-06-15T14:30:55Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Reported-by: Ramsay Jones \nSigned-off-by: Derrick Stolee \n---\n ewah/ewah_bitmap.c | 68 ----------------------------------------------\n ewah/ewok.h | 5 ----\n 2 files changed, 73 deletions(-)\n\ndiff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\nindex b9fdda1d3d..5a4d3a6eb6 100644\n--- a/ewah/ewah_bitmap.c\n+++ b/ewah/ewah_bitmap.c\n@@ -459,74 +459,6 @@ void ewah_xor(\n \tout->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);\n }\n \n-void ewah_and(\n-\tstruct ewah_bitmap *ewah_i,\n-\tstruct ewah_bitmap *ewah_j,\n-\tstruct ewah_bitmap *out)\n-{\n-\tstruct rlw_iterator rlw_i;\n-\tstruct rlw_iterator rlw_j;\n-\tsize_t literals;\n-\n-\trlwit_init(&rlw_i, ewah_i);\n-\trlwit_init(&rlw_j, ewah_j);\n-\n-\twhile (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {\n-\t\twhile (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {\n-\t\t\tstruct rlw_iterator *prey, *predator;\n-\n-\t\t\tif (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {\n-\t\t\t\tprey = &rlw_i;\n-\t\t\t\tpredator = &rlw_j;\n-\t\t\t} else {\n-\t\t\t\tprey = &rlw_j;\n-\t\t\t\tpredator = &rlw_i;\n-\t\t\t}\n-\n-\t\t\tif (predator->rlw.running_bit == 0) {\n-\t\t\t\tewah_add_empty_words(out, 0,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t\trlwit_discard_first_words(prey,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t\trlwit_discard_first_words(predator,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t} else {\n-\t\t\t\tsize_t index = rlwit_discharge(prey, out,\n-\t\t\t\t\tpredator->rlw.running_len, 0);\n-\t\t\t\tewah_add_empty_words(out, 0,\n-\t\t\t\t\tpredator->rlw.running_len - index);\n-\t\t\t\trlwit_discard_first_words(predator,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t}\n-\t\t}\n-\n-\t\tliterals = min_size(\n-\t\t\trlw_i.rlw.literal_words,\n-\t\t\trlw_j.rlw.literal_words);\n-\n-\t\tif (literals) {\n-\t\t\tsize_t k;\n-\n-\t\t\tfor (k = 0; k < literals; ++k) {\n-\t\t\t\tewah_add(out,\n-\t\t\t\t\trlw_i.buffer[rlw_i.literal_word_start + k] &\n-\t\t\t\t\trlw_j.buffer[rlw_j.literal_word_start + k]\n-\t\t\t\t);\n-\t\t\t}\n-\n-\t\t\trlwit_discard_first_words(&rlw_i, literals);\n-\t\t\trlwit_discard_first_words(&rlw_j, literals);\n-\t\t}\n-\t}\n-\n-\tif (rlwit_word_size(&rlw_i) > 0)\n-\t\trlwit_discharge_empty(&rlw_i, out);\n-\telse\n-\t\trlwit_discharge_empty(&rlw_j, out);\n-\n-\tout->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);\n-}\n-\n void ewah_and_not(\n \tstruct ewah_bitmap *ewah_i,\n \tstruct ewah_bitmap *ewah_j,\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex dc43d05b64..5841c83507 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -179,11 +179,6 @@ void ewah_xor(\n \tstruct ewah_bitmap *ewah_j,\n \tstruct ewah_bitmap *out);\n \n-void ewah_and(\n-\tstruct ewah_bitmap *ewah_i,\n-\tstruct ewah_bitmap *ewah_j,\n-\tstruct ewah_bitmap *out);\n-\n /**\n * Direct word access\n */\n-- \n2.18.0.rc1\n\n"},{"id":"350257","messageId":"20180615143018.170686-6-dstolee@microsoft.com","threadId":"48714","inReplyTo":"20180615143018.170686-1-dstolee@microsoft.com","subject":"[PATCH 5/8] ewah_bitmap: delete unused 'ewah_not()'","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-15T14:30:37Z","receivedAt":"2018-06-15T14:30:56Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Reported-by: Ramsay Jones \nSigned-off-by: Derrick Stolee \n---\n ewah/ewah_bitmap.c | 19 -------------------\n ewah/ewok.h | 7 -------\n 2 files changed, 26 deletions(-)\n\ndiff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\nindex 559adde37c..3fa3edf2a3 100644\n--- a/ewah/ewah_bitmap.c\n+++ b/ewah/ewah_bitmap.c\n@@ -376,25 +376,6 @@ void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent)\n \t\tread_new_rlw(it);\n }\n \n-void ewah_not(struct ewah_bitmap *self)\n-{\n-\tsize_t pointer = 0;\n-\n-\twhile (pointer < self->buffer_size) {\n-\t\teword_t *word = &self->buffer[pointer];\n-\t\tsize_t literals, k;\n-\n-\t\trlw_xor_run_bit(word);\n-\t\t++pointer;\n-\n-\t\tliterals = rlw_get_literal_words(word);\n-\t\tfor (k = 0; k < literals; ++k) {\n-\t\t\tself->buffer[pointer] = ~self->buffer[pointer];\n-\t\t\t++pointer;\n-\t\t}\n-\t}\n-}\n-\n void ewah_xor(\n \tstruct ewah_bitmap *ewah_i,\n \tstruct ewah_bitmap *ewah_j,\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex 21c420770e..4b665d09d9 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -95,13 +95,6 @@ int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len);\n \n uint32_t ewah_checksum(struct ewah_bitmap *self);\n \n-/**\n- * Logical not (bitwise negation) in-place on the bitmap\n- *\n- * This operation is linear time based on the size of the bitmap.\n- */\n-void ewah_not(struct ewah_bitmap *self);\n-\n /**\n * Call the given callback with the position of every single bit\n * that has been set on the bitmap.\n-- \n2.18.0.rc1\n\n"},{"id":"350259","messageId":"117a06ba-9ea1-ca7e-7967-e92db0e27c38@gmail.com","threadId":"48714","inReplyTo":"20180615143018.170686-1-dstolee@microsoft.com","subject":"Re: [PATCH 0/8] Delete unused methods in EWAH bitmap","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-06-15T14:35:00Z","receivedAt":"2018-06-15T14:35:05Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/15/2018 10:30 AM, Derrick Stolee wrote:\n> The EWAH bitmap code includes several logical operations that are\n> important for a general-purpose bitmap library. However, Git only\n> uses the XOR operation for storing deltas between reachability\n> bitmaps. This means that we can delete the following unused methods:\n>\n> * ewah_and()\n> * ewah_and_not()\n> * ewah_not()\n> * ewah_or()\n> * ewah_serialize()\n> * ewah_serialize_native()\n>\n> We can also delete the unused methods bitmap_clear() and\n> bitmap_each_bit().\n>\n> Derrick Stolee (8):\n> ewah/bitmap.c: delete unused 'bitmap_clear()'\n> ewah/bitmap.c: delete unused 'bitmap_each_bit()'\n> ewah_bitmap: delete unused 'ewah_and()'\n> ewah_bitmap: delete unused 'ewah_and_not()'\n> ewah_bitmap: delete unused 'ewah_not()'\n> ewah_bitmap: delete unused 'ewah_or()'\n> ewah_io: delete unused 'ewah_serialize()'\n> ewah_io: delete unused 'ewah_serialize_native()'\n>\n> ewah/bitmap.c | 32 -------\n> ewah/ewah_bitmap.c | 229 ---------------------------------------------\n> ewah/ewah_io.c | 36 -------\n> ewah/ewok.h | 24 -----\n> 4 files changed, 321 deletions(-)\n>\n>\n> base-commit: fc54c1af3ec09bab8b8ea09768c2da4069b7f53e\n\nResponders to this thread beware: I accidentally added an extra letter \nin Peff's email address, so be careful with reply-all.\n\nSorry!\n-Stolee\n"},{"id":"350260","messageId":"f95526b3-0f4f-ccf7-1c31-e7f48a00d1e2@ramsayjones.plus.com","threadId":"48714","inReplyTo":"20180615143018.170686-2-dstolee@microsoft.com","subject":"Re: [PATCH 1/8] ewah/bitmap.c: delete unused 'bitmap_clear()'","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsayjones.plus.com","sentAt":"2018-06-15T14:46:19Z","receivedAt":"2018-06-15T14:46:25Z","isPatch":true,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"\n\nOn 15/06/18 15:30, Derrick Stolee wrote:\n> Reported-by: Ramsay Jones \n> Signed-off-by: Derrick Stolee \n> ---\n> ewah/bitmap.c | 8 --------\n> 1 file changed, 8 deletions(-)\n> \n> diff --git a/ewah/bitmap.c b/ewah/bitmap.c\n> index 756bdd050e..d61dc6114a 100644\n> --- a/ewah/bitmap.c\n> +++ b/ewah/bitmap.c\n> @@ -45,14 +45,6 @@ void bitmap_set(struct bitmap *self, size_t pos)\n> \tself->words[block] |= EWAH_MASK(pos);\n> }\n> \n> -void bitmap_clear(struct bitmap *self, size_t pos)\n> -{\n> -\tsize_t block = EWAH_BLOCK(pos);\n> -\n> -\tif (block < self->word_alloc)\n> -\t\tself->words[block] &= ~EWAH_MASK(pos);\n> -}\n> -\n> int bitmap_get(struct bitmap *self, size_t pos)\n> {\n> \tsize_t block = EWAH_BLOCK(pos);\n> \n\nI haven't read all the patches yet, but what about the extern\ndeclaration in ewah/ewok.h?\n\nATB,\nRamsay Jones\n\n\n"},{"id":"350261","messageId":"57747146-2aea-39f4-0ef7-aca3a2ce0a66@ramsayjones.plus.com","threadId":"48714","inReplyTo":"20180615143018.170686-9-dstolee@microsoft.com","subject":"Re: [PATCH 8/8] ewah_io: delete unused 'ewah_serialize_native()'","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsayjones.plus.com","sentAt":"2018-06-15T15:01:21Z","receivedAt":"2018-06-15T15:01:26Z","isPatch":true,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"\n\nOn 15/06/18 15:30, Derrick Stolee wrote:\n> Signed-off-by: Derrick Stolee \n> ---\n> ewah/ewah_io.c | 26 --------------------------\n> ewah/ewok.h | 1 -\n> 2 files changed, 27 deletions(-)\n\nThis duplicates Jeff's patch #3.\n\nATB,\nRamsay Jones\n"},{"id":"350262","messageId":"aa2e0c9e-752c-e8ec-ce1f-ccbc6af6ce27@ramsayjones.plus.com","threadId":"48714","inReplyTo":"20180615143018.170686-3-dstolee@microsoft.com","subject":"Re: [PATCH 2/8] ewah/bitmap.c: delete unused 'bitmap_each_bit()'","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsayjones.plus.com","sentAt":"2018-06-15T15:03:13Z","receivedAt":"2018-06-15T15:03:19Z","isPatch":true,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"\n\nOn 15/06/18 15:30, Derrick Stolee wrote:\n> Reported-by: Ramsay Jones \n> Signed-off-by: Derrick Stolee \n> ---\n> ewah/bitmap.c | 24 ------------------------\n> 1 file changed, 24 deletions(-)\n> \n> diff --git a/ewah/bitmap.c b/ewah/bitmap.c\n> index d61dc6114a..52f1178db4 100644\n> --- a/ewah/bitmap.c\n> +++ b/ewah/bitmap.c\n> @@ -129,30 +129,6 @@ void bitmap_or_ewah(struct bitmap *self, struct ewah_bitmap *other)\n> \t\tself->words[i++] |= word;\n> }\n> \n> -void bitmap_each_bit(struct bitmap *self, ewah_callback callback, void *data)\n> -{\n> -\tsize_t pos = 0, i;\n> -\n> -\tfor (i = 0; i < self->word_alloc; ++i) {\n> -\t\teword_t word = self->words[i];\n> -\t\tuint32_t offset;\n> -\n> -\t\tif (word == (eword_t)~0) {\n> -\t\t\tfor (offset = 0; offset < BITS_IN_EWORD; ++offset)\n> -\t\t\t\tcallback(pos++, data);\n> -\t\t} else {\n> -\t\t\tfor (offset = 0; offset < BITS_IN_EWORD; ++offset) {\n> -\t\t\t\tif ((word >> offset) == 0)\n> -\t\t\t\t\tbreak;\n> -\n> -\t\t\t\toffset += ewah_bit_ctz64(word >> offset);\n> -\t\t\t\tcallback(pos + offset, data);\n> -\t\t\t}\n> -\t\t\tpos += BITS_IN_EWORD;\n> -\t\t}\n> -\t}\n> -}\n> -\n> size_t bitmap_popcount(struct bitmap *self)\n> {\n> \tsize_t i, count = 0;\n> \n\nAgain, remove extern declaration from header file.\n\nATB,\nRamsay Jones\n\n\n"},{"id":"350263","messageId":"2148a0f8-fbe1-4486-b27c-a8d8194b6e7f@gmail.com","threadId":"48714","inReplyTo":"57747146-2aea-39f4-0ef7-aca3a2ce0a66@ramsayjones.plus.com","subject":"Re: [PATCH 8/8] ewah_io: delete unused 'ewah_serialize_native()'","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-06-15T15:10:34Z","receivedAt":"2018-06-15T15:10:39Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/15/2018 11:01 AM, Ramsay Jones wrote:\n>\n> On 15/06/18 15:30, Derrick Stolee wrote:\n>> Signed-off-by: Derrick Stolee \n>> ---\n>> ewah/ewah_io.c | 26 --------------------------\n>> ewah/ewok.h | 1 -\n>> 2 files changed, 27 deletions(-)\n> This duplicates Jeff's patch #3.\nThanks. I got a bit hasty as I was working from 'maint' and didn't \ndouble-check.\n\n-Stolee\n"},{"id":"350264","messageId":"93cbfe90-701c-b2c0-b4fc-c3c5036f90f2@gmail.com","threadId":"48714","inReplyTo":"f95526b3-0f4f-ccf7-1c31-e7f48a00d1e2@ramsayjones.plus.com","subject":"Re: [PATCH 1/8] ewah/bitmap.c: delete unused 'bitmap_clear()'","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-06-15T15:11:08Z","receivedAt":"2018-06-15T15:11:13Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/15/2018 10:46 AM, Ramsay Jones wrote:\n>\n> On 15/06/18 15:30, Derrick Stolee wrote:\n>> Reported-by: Ramsay Jones \n>> Signed-off-by: Derrick Stolee \n>> ---\n>> ewah/bitmap.c | 8 --------\n>> 1 file changed, 8 deletions(-)\n>>\n>> diff --git a/ewah/bitmap.c b/ewah/bitmap.c\n>> index 756bdd050e..d61dc6114a 100644\n>> --- a/ewah/bitmap.c\n>> +++ b/ewah/bitmap.c\n>> @@ -45,14 +45,6 @@ void bitmap_set(struct bitmap *self, size_t pos)\n>> \tself->words[block] |= EWAH_MASK(pos);\n>> }\n>> \n>> -void bitmap_clear(struct bitmap *self, size_t pos)\n>> -{\n>> -\tsize_t block = EWAH_BLOCK(pos);\n>> -\n>> -\tif (block < self->word_alloc)\n>> -\t\tself->words[block] &= ~EWAH_MASK(pos);\n>> -}\n>> -\n>> int bitmap_get(struct bitmap *self, size_t pos)\n>> {\n>> \tsize_t block = EWAH_BLOCK(pos);\n>>\n> I haven't read all the patches yet, but what about the extern\n> declaration in ewah/ewok.h?\n\nThanks! I'll get that, too.\n"},{"id":"350266","messageId":"xmqqa7rw2fo6.fsf@gitster-ct.c.googlers.com","threadId":"48714","inReplyTo":"20180615032850.GA23241@sigill.intra.peff.net","subject":"Re: security: potential out-of-bound read at ewah_io.c |ewah_read_mmap|","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-06-15T16:11:21Z","receivedAt":"2018-06-15T16:11:27Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Fri, Jun 15, 2018 at 06:59:43AM +0800, Luat Nguyen wrote:\n>\n>> Recently, I’ve found a security issue related to out-of-bound read at function named `ewah_read_mmap`\n>\n> Thanks, this is definitely a bug worth addressing. But note...\n>\n>> Assume that, an attacker can put malicious `./git/index` into a repo by somehow.\n>\n> We generally don't consider .git/index (or pack .bitmap files, which\n> also use this implementation) to be a major part of Git's attack\n> surface, since they are generated locally. And if you can write to\n> somebody's .git directory, there are already much easier ways to execute\n> arbitrary code.\n\nThanks for giving a fair assessment on the gravity of the issue, to\nwhich I agree fully, and also fixes and clean-ups.\n\n\n\n>\n>> Since there is lack of check whether the remaining size of `ptr`is\n>> equal to `buffer_size` or not.\n>\n> Yep. We also fail to check if we even have enough bytes to read the\n> buffer_size in the first place.\n>\n> Here are some patches. The first one fixes the problem you found. The\n> second one drops some dead code that has a related problem. And the\n> third just drops some dead code that I noticed in the same file. :)\n>\n> [1/3]: ewah_read_mmap: bounds-check mmap reads\n> [2/3]: ewah: drop ewah_deserialize function\n> [3/3]: ewah: drop ewah_serialize_native function\n>\n> ewah/ewah_io.c | 106 ++++++++--------------------------------\n> ewah/ewok.h | 4 +-\n> t/t5310-pack-bitmaps.sh | 13 +++++\n> 3 files changed, 35 insertions(+), 88 deletions(-)\n>\n> -Peff\n"},{"id":"350267","messageId":"xmqq602k2f9o.fsf@gitster-ct.c.googlers.com","threadId":"48714","inReplyTo":"20180615091432.7155-1-szeder.dev@gmail.com","subject":"Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-06-15T16:20:03Z","receivedAt":"2018-06-15T16:20:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"SZEDER Gábor writes:\n\n>> +\tbitmap=$(ls .git/objects/pack/*.bitmap) &&\n>\n> I think the 'ls' is unnecessary and this would do:\n>\n> bitmap=.git/objects/pack/*.bitmap\n\nYuck.\n\n>> +\ttest_when_finished \"rm -f $bitmap\" &&\n\nOK, this will become \"rm -f .git/objects/pack/*.bitmap\" and then\neval that implements when-finished would make it work OK.\n\n>> +\thead -c 512 <$bitmap >$bitmap.tmp &&\n\nThe reading side would be OK but would the writing side also be\nalright?\n\n\tmakefile=Mak?file\n\thead -n 4 <$makefile >$makefile.tmp\n\t/bin/ls -t -1 | head -n 1\n Mak?file.tmp\n\nHmm...\n\n>> +\tmv $bitmap.tmp $bitmap &&\n\nLikewise...\n\nI said \"yuck\" because the original does not work if there happen to\nbe more than (or for that matter, less than) one '.bitmap' file\nthere. But at least as long as there is one, it should work ;-)\n"},{"id":"350268","messageId":"xmqq1sd82e9h.fsf@gitster-ct.c.googlers.com","threadId":"48714","inReplyTo":"f6931351-df79-cb76-ee29-c57472a6a201@gmail.com","subject":"Re: [PATCH 4/3] ewah: adjust callers of ewah_read_mmap()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-06-15T16:41:46Z","receivedAt":"2018-06-15T16:42:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> On 6/14/2018 11:44 PM, Jeff King wrote:\n>> The return value of ewah_read_mmap() is now an ssize_t,\n>> since we could (in theory) process up to 32GB of data. This\n>> would never happen in practice, but a corrupt or malicious\n>> .bitmap or index file could convince us to do so.\n>\n> Aside: Why a 32GB limit? Usually I see 32-bit issues limiting by 2\n> (signed) or 4 GB (unsigned). Is there something specifically in the\n> bitmap format that stops at this size?\n\nThe proposed log message for 1/3 has this bit\n\n - check the size for integer overflow (this should be\n impossible on 64-bit, as the size is given as a 32-bit\n count of 8-byte words, but is possible on a 32-bit\n system)\n\n4 Giga 8-byte words makes 32 Giga bytes, I'd guess.\n"},{"id":"350269","messageId":"xmqqsh5o0yl5.fsf@gitster-ct.c.googlers.com","threadId":"48714","inReplyTo":"20180615033112.GA20390@sigill.intra.peff.net","subject":"Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-06-15T17:05:42Z","receivedAt":"2018-06-15T17:05:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> diff --git a/ewah/ewah_io.c b/ewah/ewah_io.c\n> index bed1994551..33c08c40f8 100644\n> --- a/ewah/ewah_io.c\n> +++ b/ewah/ewah_io.c\n> @@ -122,16 +122,23 @@ int ewah_serialize_strbuf(struct ewah_bitmap *self, struct strbuf *sb)\n> \treturn ewah_serialize_to(self, write_strbuf, sb);\n> }\n> \n> -int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len)\n> +ssize_t ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len)\n> {\n> \tconst uint8_t *ptr = map;\n> +\tsize_t data_len;\n> \tsize_t i;\n> \n> +\tif (len < sizeof(uint32_t))\n> +\t\treturn error(\"corrupt ewah bitmap: eof before bit size\");\n> \tself->bit_size = get_be32(ptr);\n> \tptr += sizeof(uint32_t);\n> +\tlen -= sizeof(uint32_t);\n> \n> +\tif (len < sizeof(uint32_t))\n> +\t\treturn error(\"corrupt ewah bitmap: eof before length\");\n> \tself->buffer_size = self->alloc_size = get_be32(ptr);\n> \tptr += sizeof(uint32_t);\n> +\tlen -= sizeof(uint32_t);\n> \n> \tREALLOC_ARRAY(self->buffer, self->alloc_size);\n> \n> @@ -141,15 +148,25 @@ int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len)\n> \t * the endianness conversion in a separate pass to ensure\n> \t * we're loading 8-byte aligned words.\n> \t */\n> -\tmemcpy(self->buffer, ptr, self->buffer_size * sizeof(eword_t));\n> -\tptr += self->buffer_size * sizeof(eword_t);\n\n\n> +\tdata_len = st_mult(self->buffer_size, sizeof(eword_t));\n\nThis is a faithful conversion from the original, but I somehow would\nhave appreciated if the latter were not sizeof(eword_t) but rather\nsizeof(self->buffer_size[0]), especially as I wondered ...\n\n> +\tif (len < data_len)\n> +\t\treturn error(\"corrupt ewah bitmap: eof in data \"\n> +\t\t\t \"(%\"PRIuMAX\" bytes short)\",\n> +\t\t\t (uintmax_t)(data_len - len));\n> +\tmemcpy(self->buffer, ptr, data_len);\n> +\tptr += data_len;\n> +\tlen -= data_len;\n> \n> \tfor (i = 0; i < self->buffer_size; ++i)\n> \t\tself->buffer[i] = ntohll(self->buffer[i]);\n\n... what individual datum one iteration of this loop is copying, and\nthen realized \"buffer_size\" is a misleading field name (anything that \nclaims to be size and not measuring in bytes is misleading to me ;-).\n\n> +\tif (len < sizeof(uint32_t))\n> +\t\treturn error(\"corrupt ewah bitmap: eof before rlw\");\n> \tself->rlw = self->buffer + get_be32(ptr);\n> +\tptr += sizeof(uint32_t);\n> +\tlen -= sizeof(uint32_t);\n> \n> -\treturn (3 * 4) + (self->buffer_size * 8);\n> +\treturn ptr - (const uint8_t *)map;\n\nMuch nicer; I needed to wonder what these 12 and 8 in the original are.\n\n> \n> int ewah_deserialize(struct ewah_bitmap *self, int fd);\n> -int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len);\n> +ssize_t ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len);\n\nI double checked all the callers and made sure that they are already\nprepared to react sensibly to error returns, which is good.\n\n> \n> uint32_t ewah_checksum(struct ewah_bitmap *self);\n> \n> diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\n> index 423c0a475f..237ee6e5fc 100755\n> --- a/t/t5310-pack-bitmaps.sh\n> +++ b/t/t5310-pack-bitmaps.sh\n> @@ -331,4 +331,17 @@ test_expect_success 'pack reuse respects --incremental' '\n> \tgit show-index actual &&\n> \ttest_cmp expect actual\n> '\n> +\n> +test_expect_success 'truncated bitmap fails gracefully' '\n> +\tgit repack -ad &&\n> +\tgit rev-list --use-bitmap-index --count --all >expect &&\n> +\tbitmap=$(ls .git/objects/pack/*.bitmap) &&\n> +\ttest_when_finished \"rm -f $bitmap\" &&\n> +\thead -c 512 <$bitmap >$bitmap.tmp &&\n> +\tmv $bitmap.tmp $bitmap &&\n> +\tgit rev-list --use-bitmap-index --count --all >actual 2>stderr &&\n> +\ttest_cmp expect actual &&\n> +\ttest_i18ngrep corrupt stderr\n> +'\n> +\n> test_done\n"},{"id":"350270","messageId":"CAM0VKjnZXfaNskiba9VsFWwwOx_kvGxZDY_AiyQv8L6gCPX4Fw@mail.gmail.com","threadId":"48714","inReplyTo":"xmqq602k2f9o.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2018-06-15T17:10:28Z","receivedAt":"2018-06-15T17:10:32Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Fri, Jun 15, 2018 at 6:20 PM, Junio C Hamano wrote:\n> SZEDER Gábor writes:\n>\n>>> + bitmap=$(ls .git/objects/pack/*.bitmap) &&\n>>\n>> I think the 'ls' is unnecessary and this would do:\n>>\n>> bitmap=.git/objects/pack/*.bitmap\n>\n> Yuck.\n\nOh, wow, now this is embarrassing...\n\n\n> I said \"yuck\" because the original does not work if there happen to\n> be more than (or for that matter, less than) one '.bitmap' file\n> there. But at least as long as there is one, it should work ;-)\n\nWell, the test starts with 'git repack -ad', so there can be only one\nbitmap file. (Unless something is broken, of course, but the second\ntest would catch that much earlier.)\n"},{"id":"350271","messageId":"xmqqo9gc0yan.fsf@gitster-ct.c.googlers.com","threadId":"48714","inReplyTo":"20180615034442.GA14422@sigill.intra.peff.net","subject":"Re: [PATCH 4/3] ewah: adjust callers of ewah_read_mmap()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-06-15T17:12:00Z","receivedAt":"2018-06-15T17:12:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Thu, Jun 14, 2018 at 11:28:50PM -0400, Jeff King wrote:\n>\n>> Yep. We also fail to check if we even have enough bytes to read the\n>> buffer_size in the first place.\n>> \n>> Here are some patches. The first one fixes the problem you found. The\n>> second one drops some dead code that has a related problem. And the\n>> third just drops some dead code that I noticed in the same file. :)\n>> \n>> [1/3]: ewah_read_mmap: bounds-check mmap reads\n>> [2/3]: ewah: drop ewah_deserialize function\n>> [3/3]: ewah: drop ewah_serialize_native function\n>\n> Actually, we'd want this one on top. Arguably it could be squashed into\n> patch 1.\n>\n> -- >8 --\n> Subject: ewah: adjust callers of ewah_read_mmap()\n>\n> The return value of ewah_read_mmap() is now an ssize_t,\n> since we could (in theory) process up to 32GB of data. This\n> would never happen in practice, but a corrupt or malicious\n> .bitmap or index file could convince us to do so.\n>\n> Let's make sure that we don't stuff the value into an int,\n> which would cause us to incorrectly move our pointer\n> forward. We'd always move too little, since negative values\n> are used for reporting errors. So the worst case is just\n> that we end up reporting a corrupt file, not an\n> out-of-bounds read.\n>\n> Signed-off-by: Jeff King \n> ---\n\nMakes sense.\n\n> dir.c | 3 ++-\n> pack-bitmap.c | 2 +-\n> 2 files changed, 3 insertions(+), 2 deletions(-)\n>\n> diff --git a/dir.c b/dir.c\n> index 61b513a078..d5185660f1 100644\n> --- a/dir.c\n> +++ b/dir.c\n> @@ -2725,7 +2725,8 @@ struct untracked_cache *read_untracked_extension(const void *data, unsigned long\n> \tstruct read_data rd;\n> \tconst unsigned char *next = data, *end = (const unsigned char *)data + sz;\n> \tconst char *ident;\n> -\tint ident_len, len;\n> +\tint ident_len;\n> +\tssize_t len;\n> \tconst char *exclude_per_dir;\n> \n> \tif (sz <= 1 || end[-1] != '\\0')\n> diff --git a/pack-bitmap.c b/pack-bitmap.c\n> index 369bf69d75..2f27b10e35 100644\n> --- a/pack-bitmap.c\n> +++ b/pack-bitmap.c\n> @@ -125,7 +125,7 @@ static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index)\n> {\n> \tstruct ewah_bitmap *b = ewah_pool_new();\n> \n> -\tint bitmap_size = ewah_read_mmap(b,\n> +\tssize_t bitmap_size = ewah_read_mmap(b,\n> \t\tindex->map + index->map_pos,\n> \t\tindex->map_size - index->map_pos);\n"},{"id":"350272","messageId":"20180615172121.GA3067@sigill.intra.peff.net","threadId":"48714","inReplyTo":"CAM0VKjnZXfaNskiba9VsFWwwOx_kvGxZDY_AiyQv8L6gCPX4Fw@mail.gmail.com","subject":"Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-06-15T17:21:22Z","receivedAt":"2018-06-15T17:21:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jun 15, 2018 at 07:10:28PM +0200, SZEDER Gábor wrote:\n\n> > I said \"yuck\" because the original does not work if there happen to\n> > be more than (or for that matter, less than) one '.bitmap' file\n> > there. But at least as long as there is one, it should work ;-)\n> \n> Well, the test starts with 'git repack -ad', so there can be only one\n> bitmap file. (Unless something is broken, of course, but the second\n> test would catch that much earlier.)\n\nRight. I almost put \"head -1\" in there, but we know that we just created\na single bitmap. And my thought was that if we don't, the test would\nblow up horribly, which is exactly what you want.\n\n-Peff\n"},{"id":"350273","messageId":"20180615172656.GB3067@sigill.intra.peff.net","threadId":"48714","inReplyTo":"xmqqsh5o0yl5.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-06-15T17:26:56Z","receivedAt":"2018-06-15T17:27:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jun 15, 2018 at 10:05:42AM -0700, Junio C Hamano wrote:\n\n> > -\tmemcpy(self->buffer, ptr, self->buffer_size * sizeof(eword_t));\n> > -\tptr += self->buffer_size * sizeof(eword_t);\n> \n> \n> > +\tdata_len = st_mult(self->buffer_size, sizeof(eword_t));\n> \n> This is a faithful conversion from the original, but I somehow would\n> have appreciated if the latter were not sizeof(eword_t) but rather\n> sizeof(self->buffer_size[0]), especially as I wondered ...\n\nI actually thought about going the _other_ way. The sizeof(eword_t) is\nnot something we can change, but is actually decided by the on-disk\nformat. So I wondered if this should be much more clearly \"hey, this is\n8 bytes\". Possibly with an assert(sizeof(*self->buffer_size) == 8).\n\nAnd yes, I think having the on-disk format specify the size in 8-byte\ndouble words is vaguely crazy. Blame JGit. ;) Or maybe even blame the\noriginal EWAH authors, this may have originated even earlier (I didn't\ndig).\n\n> > +\tif (len < data_len)\n> > +\t\treturn error(\"corrupt ewah bitmap: eof in data \"\n> > +\t\t\t \"(%\"PRIuMAX\" bytes short)\",\n> > +\t\t\t (uintmax_t)(data_len - len));\n> > +\tmemcpy(self->buffer, ptr, data_len);\n> > +\tptr += data_len;\n> > +\tlen -= data_len;\n> > \n> > \tfor (i = 0; i < self->buffer_size; ++i)\n> > \t\tself->buffer[i] = ntohll(self->buffer[i]);\n> \n> ... what individual datum one iteration of this loop is copying, and\n> then realized \"buffer_size\" is a misleading field name (anything that \n> claims to be size and not measuring in bytes is misleading to me ;-).\n\nYeah, it confused me at first, too. I don't mind changing these kinds of\ncosmetics, but I'd like to do it in a separate patch from this fix.\n\n> > -\treturn (3 * 4) + (self->buffer_size * 8);\n> > +\treturn ptr - (const uint8_t *)map;\n> \n> Much nicer; I needed to wonder what these 12 and 8 in the original are.\n\nMe too. ;)\n\n> > int ewah_deserialize(struct ewah_bitmap *self, int fd);\n> > -int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len);\n> > +ssize_t ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len);\n> \n> I double checked all the callers and made sure that they are already\n> prepared to react sensibly to error returns, which is good.\n\nYep, modulo the int/ssize_t thing from the fourth patch.\n\n-Peff\n"},{"id":"350274","messageId":"20180615173155.GC3067@sigill.intra.peff.net","threadId":"48714","inReplyTo":"xmqq1sd82e9h.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 4/3] ewah: adjust callers of ewah_read_mmap()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-06-15T17:31:55Z","receivedAt":"2018-06-15T17:31:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jun 15, 2018 at 09:41:46AM -0700, Junio C Hamano wrote:\n\n> Derrick Stolee writes:\n> \n> > On 6/14/2018 11:44 PM, Jeff King wrote:\n> >> The return value of ewah_read_mmap() is now an ssize_t,\n> >> since we could (in theory) process up to 32GB of data. This\n> >> would never happen in practice, but a corrupt or malicious\n> >> .bitmap or index file could convince us to do so.\n> >\n> > Aside: Why a 32GB limit? Usually I see 32-bit issues limiting by 2\n> > (signed) or 4 GB (unsigned). Is there something specifically in the\n> > bitmap format that stops at this size?\n> \n> The proposed log message for 1/3 has this bit\n> \n> - check the size for integer overflow (this should be\n> impossible on 64-bit, as the size is given as a 32-bit\n> count of 8-byte words, but is possible on a 32-bit\n> system)\n> \n> 4 Giga 8-byte words makes 32 Giga bytes, I'd guess.\n\nYes, exactly. It's definitely an odd size. I think using the same\nvarints we use in the packfile would be more efficient (and they're\nalready variable-length records), though we tend to have few enough of\nthese that it probably doesn't matter.\n\nI think a more useful change for the bitmap format would be some kind of\nindex. IIRC, right now readers have to linearly scan the whole file in\norder to use a single bitmap.\n\nWith Stolee's commit-metadata files, we could potentially move to\nstoring reachability bitmaps as a data element there. But there are two\ncomplications:\n\n - the bitmaps themselves are dependent on having an ordered list of\n objects (one per bit) to talk about. And that's why they're\n integrated with packfiles, since that provides a constrained universe\n with a set ordering.\n\n - the existing storage isn't entirely independent between bitmaps. Some\n of them are basically \"deltas\" off of nearby bitmaps.\n\n-Peff\n"},{"id":"350275","messageId":"20180615175111.GD3067@sigill.intra.peff.net","threadId":"48714","inReplyTo":"ab6378a8-3728-7fa8-da08-b58ec768dbfe@gmail.com","subject":"Re: [PATCH 3/3] ewah: drop ewah_serialize_native function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-06-15T17:51:12Z","receivedAt":"2018-06-15T17:51:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jun 15, 2018 at 10:15:50AM -0400, Derrick Stolee wrote:\n\n> > Hmm, if you are in the mood to drop ewah dead code, how about:\n> > \n> > ewah/bitmap.o - bitmap_clear\n> > ewah/bitmap.o - bitmap_each_bit\n> > ewah/ewah_bitmap.o - ewah_and\n> > ewah/ewah_bitmap.o - ewah_and_not\n> > ewah/ewah_bitmap.o - ewah_not\n> > ewah/ewah_bitmap.o - ewah_or\n> > \n> > ... in addition to these *(de)serialize* functions. ;-)\n> > \n> \n> Normally, I would say we should keep this folder as close to the \"original\"\n> [1] as possible, so we could more easily take improvements to that library.\n> However, it appears that code is not being updated. Perhaps this is in favor\n> of other EWAH libraries [2] or other compressed bitmap formats [3].\n\nThe ewok library was written specifically for Git, as a port of Daniel\nLemire's original EWAH work, since at the time there was no pure-C\nimplementation of EWAH (that might even still be the case -- I don't\nknow).\n\nWe pulled it out into a separate library with the thought that maybe\nother people would find it useful. But I don't specifically know of any\nother users of the library, nor do I think Vicent has spent any time on\nit since writing it for Git (I know I haven't).\n\nSo yeah, I think it is fine to just consider this \"our\" code and chop it\nup as we see fit (and you can see we've already tweaked it for things\nlike allocating consistently with our other code).\n\nOne thing that gave me pause on ripping out more code is that I have\nsome bitmap-related patches on my send-to-upstream list, and I wasn't\nsure if they used any of this code. But I checked against your patches,\nand no, this can all go (which makes sense -- my patches are about using\n.bitmap files in more places, so they build at a higher level).\n\nSo your patches look good to me, modulo the declarations that Ramsay\nnoticed should be removed, too.\n\n-Peff\n"},{"id":"350276","messageId":"1685a358-f033-64e0-2e12-df3a1c10af19@gmail.com","threadId":"48714","inReplyTo":"20180615173155.GC3067@sigill.intra.peff.net","subject":"Re: [PATCH 4/3] ewah: adjust callers of ewah_read_mmap()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-06-15T18:23:44Z","receivedAt":"2018-06-15T18:23:49Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/15/2018 1:31 PM, Jeff King wrote:\n> On Fri, Jun 15, 2018 at 09:41:46AM -0700, Junio C Hamano wrote:\n>\n>> Derrick Stolee writes:\n>>\n>>> On 6/14/2018 11:44 PM, Jeff King wrote:\n>>>> The return value of ewah_read_mmap() is now an ssize_t,\n>>>> since we could (in theory) process up to 32GB of data. This\n>>>> would never happen in practice, but a corrupt or malicious\n>>>> .bitmap or index file could convince us to do so.\n>>> Aside: Why a 32GB limit? Usually I see 32-bit issues limiting by 2\n>>> (signed) or 4 GB (unsigned). Is there something specifically in the\n>>> bitmap format that stops at this size?\n>> The proposed log message for 1/3 has this bit\n>>\n>> - check the size for integer overflow (this should be\n>> impossible on 64-bit, as the size is given as a 32-bit\n>> count of 8-byte words, but is possible on a 32-bit\n>> system)\n>>\n>> 4 Giga 8-byte words makes 32 Giga bytes, I'd guess.\n> Yes, exactly. It's definitely an odd size. I think using the same\n> varints we use in the packfile would be more efficient (and they're\n> already variable-length records), though we tend to have few enough of\n> these that it probably doesn't matter.\n>\n> I think a more useful change for the bitmap format would be some kind of\n> index. IIRC, right now readers have to linearly scan the whole file in\n> order to use a single bitmap.\n>\n> With Stolee's commit-metadata files, we could potentially move to\n> storing reachability bitmaps as a data element there. But there are two\n> complications:\n>\n> - the bitmaps themselves are dependent on having an ordered list of\n> objects (one per bit) to talk about. And that's why they're\n> integrated with packfiles, since that provides a constrained universe\n> with a set ordering.\n>\n> - the existing storage isn't entirely independent between bitmaps. Some\n> of them are basically \"deltas\" off of nearby bitmaps.\n\nThe VSTS reachability bitmap is different from the Git bitmap in a few ways.\n\n1. It uses Roaring+Run bitmaps [1] instead of EWAH bitmap. This format \nis simpler (in my opinion) in several ways, especially in how it splits \nthe bitmap into 16-bit address ranges and compresses each on its own. \nThis makes set containment queries much faster, as we can navigate \ndirectly to the region that is important (and then binary search if that \nchunk is an \"array\" or \"run\" chunk). I say this is simpler because I can \nexplain the entire compression format to you in five minutes and a \nwhiteboard. The paper [2] is a simple enough read (start at the \"Roaring \nBitmap\" section at the end of page 4).\n\n2. Our file uses a chunk-based approach similar to the commit-graph \nfile: one chunk is simply a list of the commits that have bitmaps. \nAnother chunk is the raw binary data of all bitmaps concatenated \ntogether. The last chunk connects the other two chunks by a) providing \nan offset into the binary data for the bitmap at that commit, and b) the \ncommit that provides a delta base for the bitmap.\n\nIf we are considering changing the reachability bitmap, then I'm very \nintrigued. I think the number one thing to consider is to use the \nmulti-pack-index as a reference point (with a stable object order) so \nthe objects can be repacked independently from the reachability bitmap \ncomputation. If we are changing the model at that level, then it is \nworth thinking about other questions, like how we index the file or how \nwe compress the bitmaps.\n\nThanks,\n-Stolee\n\n[1] https://roaringbitmap.org/about/\n\n[2] https://arxiv.org/abs/1603.06549\n     Consistently faster and smaller compressed bitmaps with Roaring\n"},{"id":"350277","messageId":"20180615182727.172075-1-dstolee@microsoft.com","threadId":"48714","inReplyTo":"20180615143018.170686-1-dstolee@microsoft.com","subject":"[PATCH v2 0/7] Delete unused methods in EWAH bitmap","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-15T18:27:36Z","receivedAt":"2018-06-15T18:27:42Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"The EWAH bitmap code includes several logical operations that are\nimportant for a general-purpose bitmap library. However, Git only\nuses the XOR operation for storing deltas between reachability\nbitmaps. This means that we can delete the following unused methods:\n\n* ewah_and()\n* ewah_and_not()\n* ewah_not()\n* ewah_or()\n* ewah_serialize()\n\nWe can also delete the unused methods bitmap_clear() and\nbitmap_each_bit().\n\nDerrick Stolee (7):\n ewah/bitmap.c: delete unused 'bitmap_clear()'\n ewah/bitmap.c: delete unused 'bitmap_each_bit()'\n ewah_bitmap: delete unused 'ewah_and()'\n ewah_bitmap: delete unused 'ewah_and_not()'\n ewah_bitmap: delete unused 'ewah_not()'\n ewah_bitmap: delete unused 'ewah_or()'\n ewah_io: delete unused 'ewah_serialize()'\n\n ewah/bitmap.c | 32 -------\n ewah/ewah_bitmap.c | 229 ---------------------------------------------\n ewah/ewah_io.c | 10 --\n ewah/ewok.h | 25 -----\n 4 files changed, 296 deletions(-)\n\n\nbase-commit: fc54c1af3ec09bab8b8ea09768c2da4069b7f53e\n-- \n2.18.0.rc1\n\n"},{"id":"350278","messageId":"20180615182727.172075-2-dstolee@microsoft.com","threadId":"48714","inReplyTo":"20180615182727.172075-1-dstolee@microsoft.com","subject":"[PATCH v2 1/7] ewah/bitmap.c: delete unused 'bitmap_clear()'","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-15T18:27:38Z","receivedAt":"2018-06-15T18:27:46Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Reported-by: Ramsay Jones \nSigned-off-by: Derrick Stolee \n---\n ewah/bitmap.c | 8 --------\n ewah/ewok.h | 1 -\n 2 files changed, 9 deletions(-)\n\ndiff --git a/ewah/bitmap.c b/ewah/bitmap.c\nindex 756bdd050e..d61dc6114a 100644\n--- a/ewah/bitmap.c\n+++ b/ewah/bitmap.c\n@@ -45,14 +45,6 @@ void bitmap_set(struct bitmap *self, size_t pos)\n \tself->words[block] |= EWAH_MASK(pos);\n }\n \n-void bitmap_clear(struct bitmap *self, size_t pos)\n-{\n-\tsize_t block = EWAH_BLOCK(pos);\n-\n-\tif (block < self->word_alloc)\n-\t\tself->words[block] &= ~EWAH_MASK(pos);\n-}\n-\n int bitmap_get(struct bitmap *self, size_t pos)\n {\n \tsize_t block = EWAH_BLOCK(pos);\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex dc43d05b64..2d25e93b9e 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -204,7 +204,6 @@ struct bitmap {\n \n struct bitmap *bitmap_new(void);\n void bitmap_set(struct bitmap *self, size_t pos);\n-void bitmap_clear(struct bitmap *self, size_t pos);\n int bitmap_get(struct bitmap *self, size_t pos);\n void bitmap_reset(struct bitmap *self);\n void bitmap_free(struct bitmap *self);\n-- \n2.18.0.rc1\n\n"},{"id":"350279","messageId":"20180615182727.172075-3-dstolee@microsoft.com","threadId":"48714","inReplyTo":"20180615182727.172075-1-dstolee@microsoft.com","subject":"[PATCH v2 2/7] ewah/bitmap.c: delete unused 'bitmap_each_bit()'","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-15T18:27:41Z","receivedAt":"2018-06-15T18:27:47Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Reported-by: Ramsay Jones \nSigned-off-by: Derrick Stolee \n---\n ewah/bitmap.c | 24 ------------------------\n ewah/ewok.h | 1 -\n 2 files changed, 25 deletions(-)\n\ndiff --git a/ewah/bitmap.c b/ewah/bitmap.c\nindex d61dc6114a..52f1178db4 100644\n--- a/ewah/bitmap.c\n+++ b/ewah/bitmap.c\n@@ -129,30 +129,6 @@ void bitmap_or_ewah(struct bitmap *self, struct ewah_bitmap *other)\n \t\tself->words[i++] |= word;\n }\n \n-void bitmap_each_bit(struct bitmap *self, ewah_callback callback, void *data)\n-{\n-\tsize_t pos = 0, i;\n-\n-\tfor (i = 0; i < self->word_alloc; ++i) {\n-\t\teword_t word = self->words[i];\n-\t\tuint32_t offset;\n-\n-\t\tif (word == (eword_t)~0) {\n-\t\t\tfor (offset = 0; offset < BITS_IN_EWORD; ++offset)\n-\t\t\t\tcallback(pos++, data);\n-\t\t} else {\n-\t\t\tfor (offset = 0; offset < BITS_IN_EWORD; ++offset) {\n-\t\t\t\tif ((word >> offset) == 0)\n-\t\t\t\t\tbreak;\n-\n-\t\t\t\toffset += ewah_bit_ctz64(word >> offset);\n-\t\t\t\tcallback(pos + offset, data);\n-\t\t\t}\n-\t\t\tpos += BITS_IN_EWORD;\n-\t\t}\n-\t}\n-}\n-\n size_t bitmap_popcount(struct bitmap *self)\n {\n \tsize_t i, count = 0;\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex 2d25e93b9e..71704ed37f 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -217,7 +217,6 @@ void bitmap_and_not(struct bitmap *self, struct bitmap *other);\n void bitmap_or_ewah(struct bitmap *self, struct ewah_bitmap *other);\n void bitmap_or(struct bitmap *self, const struct bitmap *other);\n \n-void bitmap_each_bit(struct bitmap *self, ewah_callback callback, void *data);\n size_t bitmap_popcount(struct bitmap *self);\n \n #endif\n-- \n2.18.0.rc1\n\n"},{"id":"350280","messageId":"20180615182727.172075-4-dstolee@microsoft.com","threadId":"48714","inReplyTo":"20180615182727.172075-1-dstolee@microsoft.com","subject":"[PATCH v2 3/7] ewah_bitmap: delete unused 'ewah_and()'","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-15T18:27:44Z","receivedAt":"2018-06-15T18:27:51Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Reported-by: Ramsay Jones \nSigned-off-by: Derrick Stolee \n---\n ewah/ewah_bitmap.c | 68 ----------------------------------------------\n ewah/ewok.h | 5 ----\n 2 files changed, 73 deletions(-)\n\ndiff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\nindex b9fdda1d3d..5a4d3a6eb6 100644\n--- a/ewah/ewah_bitmap.c\n+++ b/ewah/ewah_bitmap.c\n@@ -459,74 +459,6 @@ void ewah_xor(\n \tout->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);\n }\n \n-void ewah_and(\n-\tstruct ewah_bitmap *ewah_i,\n-\tstruct ewah_bitmap *ewah_j,\n-\tstruct ewah_bitmap *out)\n-{\n-\tstruct rlw_iterator rlw_i;\n-\tstruct rlw_iterator rlw_j;\n-\tsize_t literals;\n-\n-\trlwit_init(&rlw_i, ewah_i);\n-\trlwit_init(&rlw_j, ewah_j);\n-\n-\twhile (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {\n-\t\twhile (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {\n-\t\t\tstruct rlw_iterator *prey, *predator;\n-\n-\t\t\tif (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {\n-\t\t\t\tprey = &rlw_i;\n-\t\t\t\tpredator = &rlw_j;\n-\t\t\t} else {\n-\t\t\t\tprey = &rlw_j;\n-\t\t\t\tpredator = &rlw_i;\n-\t\t\t}\n-\n-\t\t\tif (predator->rlw.running_bit == 0) {\n-\t\t\t\tewah_add_empty_words(out, 0,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t\trlwit_discard_first_words(prey,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t\trlwit_discard_first_words(predator,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t} else {\n-\t\t\t\tsize_t index = rlwit_discharge(prey, out,\n-\t\t\t\t\tpredator->rlw.running_len, 0);\n-\t\t\t\tewah_add_empty_words(out, 0,\n-\t\t\t\t\tpredator->rlw.running_len - index);\n-\t\t\t\trlwit_discard_first_words(predator,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t}\n-\t\t}\n-\n-\t\tliterals = min_size(\n-\t\t\trlw_i.rlw.literal_words,\n-\t\t\trlw_j.rlw.literal_words);\n-\n-\t\tif (literals) {\n-\t\t\tsize_t k;\n-\n-\t\t\tfor (k = 0; k < literals; ++k) {\n-\t\t\t\tewah_add(out,\n-\t\t\t\t\trlw_i.buffer[rlw_i.literal_word_start + k] &\n-\t\t\t\t\trlw_j.buffer[rlw_j.literal_word_start + k]\n-\t\t\t\t);\n-\t\t\t}\n-\n-\t\t\trlwit_discard_first_words(&rlw_i, literals);\n-\t\t\trlwit_discard_first_words(&rlw_j, literals);\n-\t\t}\n-\t}\n-\n-\tif (rlwit_word_size(&rlw_i) > 0)\n-\t\trlwit_discharge_empty(&rlw_i, out);\n-\telse\n-\t\trlwit_discharge_empty(&rlw_j, out);\n-\n-\tout->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);\n-}\n-\n void ewah_and_not(\n \tstruct ewah_bitmap *ewah_i,\n \tstruct ewah_bitmap *ewah_j,\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex 71704ed37f..f4ada6979e 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -179,11 +179,6 @@ void ewah_xor(\n \tstruct ewah_bitmap *ewah_j,\n \tstruct ewah_bitmap *out);\n \n-void ewah_and(\n-\tstruct ewah_bitmap *ewah_i,\n-\tstruct ewah_bitmap *ewah_j,\n-\tstruct ewah_bitmap *out);\n-\n /**\n * Direct word access\n */\n-- \n2.18.0.rc1\n\n"},{"id":"350281","messageId":"20180615182727.172075-5-dstolee@microsoft.com","threadId":"48714","inReplyTo":"20180615182727.172075-1-dstolee@microsoft.com","subject":"[PATCH v2 4/7] ewah_bitmap: delete unused 'ewah_and_not()'","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-15T18:27:46Z","receivedAt":"2018-06-15T18:27:53Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Reported-by: Ramsay Jones \nSigned-off-by: Derrick Stolee \n---\n ewah/ewah_bitmap.c | 73 ----------------------------------------------\n ewah/ewok.h | 5 ----\n 2 files changed, 78 deletions(-)\n\ndiff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\nindex 5a4d3a6eb6..559adde37c 100644\n--- a/ewah/ewah_bitmap.c\n+++ b/ewah/ewah_bitmap.c\n@@ -459,79 +459,6 @@ void ewah_xor(\n \tout->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);\n }\n \n-void ewah_and_not(\n-\tstruct ewah_bitmap *ewah_i,\n-\tstruct ewah_bitmap *ewah_j,\n-\tstruct ewah_bitmap *out)\n-{\n-\tstruct rlw_iterator rlw_i;\n-\tstruct rlw_iterator rlw_j;\n-\tsize_t literals;\n-\n-\trlwit_init(&rlw_i, ewah_i);\n-\trlwit_init(&rlw_j, ewah_j);\n-\n-\twhile (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {\n-\t\twhile (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {\n-\t\t\tstruct rlw_iterator *prey, *predator;\n-\n-\t\t\tif (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {\n-\t\t\t\tprey = &rlw_i;\n-\t\t\t\tpredator = &rlw_j;\n-\t\t\t} else {\n-\t\t\t\tprey = &rlw_j;\n-\t\t\t\tpredator = &rlw_i;\n-\t\t\t}\n-\n-\t\t\tif ((predator->rlw.running_bit && prey == &rlw_i) ||\n-\t\t\t\t(!predator->rlw.running_bit && prey != &rlw_i)) {\n-\t\t\t\tewah_add_empty_words(out, 0,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t\trlwit_discard_first_words(prey,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t\trlwit_discard_first_words(predator,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t} else {\n-\t\t\t\tsize_t index;\n-\t\t\t\tint negate_words;\n-\n-\t\t\t\tnegate_words = (&rlw_i != prey);\n-\t\t\t\tindex = rlwit_discharge(prey, out,\n-\t\t\t\t\tpredator->rlw.running_len, negate_words);\n-\t\t\t\tewah_add_empty_words(out, negate_words,\n-\t\t\t\t\tpredator->rlw.running_len - index);\n-\t\t\t\trlwit_discard_first_words(predator,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t}\n-\t\t}\n-\n-\t\tliterals = min_size(\n-\t\t\trlw_i.rlw.literal_words,\n-\t\t\trlw_j.rlw.literal_words);\n-\n-\t\tif (literals) {\n-\t\t\tsize_t k;\n-\n-\t\t\tfor (k = 0; k < literals; ++k) {\n-\t\t\t\tewah_add(out,\n-\t\t\t\t\trlw_i.buffer[rlw_i.literal_word_start + k] &\n-\t\t\t\t\t~(rlw_j.buffer[rlw_j.literal_word_start + k])\n-\t\t\t\t);\n-\t\t\t}\n-\n-\t\t\trlwit_discard_first_words(&rlw_i, literals);\n-\t\t\trlwit_discard_first_words(&rlw_j, literals);\n-\t\t}\n-\t}\n-\n-\tif (rlwit_word_size(&rlw_i) > 0)\n-\t\trlwit_discharge(&rlw_i, out, ~0, 0);\n-\telse\n-\t\trlwit_discharge_empty(&rlw_j, out);\n-\n-\tout->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);\n-}\n-\n void ewah_or(\n \tstruct ewah_bitmap *ewah_i,\n \tstruct ewah_bitmap *ewah_j,\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex f4ada6979e..8dae8a608c 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -169,11 +169,6 @@ void ewah_or(\n \tstruct ewah_bitmap *ewah_j,\n \tstruct ewah_bitmap *out);\n \n-void ewah_and_not(\n-\tstruct ewah_bitmap *ewah_i,\n-\tstruct ewah_bitmap *ewah_j,\n-\tstruct ewah_bitmap *out);\n-\n void ewah_xor(\n \tstruct ewah_bitmap *ewah_i,\n \tstruct ewah_bitmap *ewah_j,\n-- \n2.18.0.rc1\n\n"},{"id":"350282","messageId":"20180615182727.172075-8-dstolee@microsoft.com","threadId":"48714","inReplyTo":"20180615182727.172075-1-dstolee@microsoft.com","subject":"[PATCH v2 7/7] ewah_io: delete unused 'ewah_serialize()'","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-15T18:27:52Z","receivedAt":"2018-06-15T18:27:58Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Reported-by: Ramsay Jones \nSigned-off-by: Derrick Stolee \n---\n ewah/ewah_io.c | 10 ----------\n ewah/ewok.h | 1 -\n 2 files changed, 11 deletions(-)\n\ndiff --git a/ewah/ewah_io.c b/ewah/ewah_io.c\nindex bed1994551..86d3f1d02e 100644\n--- a/ewah/ewah_io.c\n+++ b/ewah/ewah_io.c\n@@ -100,16 +100,6 @@ int ewah_serialize_to(struct ewah_bitmap *self,\n \treturn (3 * 4) + (self->buffer_size * 8);\n }\n \n-static int write_helper(void *fd, const void *buf, size_t len)\n-{\n-\treturn write((intptr_t)fd, buf, len);\n-}\n-\n-int ewah_serialize(struct ewah_bitmap *self, int fd)\n-{\n-\treturn ewah_serialize_to(self, write_helper, (void *)(intptr_t)fd);\n-}\n-\n static int write_strbuf(void *user_data, const void *data, size_t len)\n {\n \tstruct strbuf *sb = user_data;\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex a540df2aa9..f3ac78ef1a 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -86,7 +86,6 @@ void ewah_free(struct ewah_bitmap *self);\n int ewah_serialize_to(struct ewah_bitmap *self,\n \t\t int (*write_fun)(void *out, const void *buf, size_t len),\n \t\t void *out);\n-int ewah_serialize(struct ewah_bitmap *self, int fd);\n int ewah_serialize_native(struct ewah_bitmap *self, int fd);\n int ewah_serialize_strbuf(struct ewah_bitmap *self, struct strbuf *);\n \n-- \n2.18.0.rc1\n\n"},{"id":"350283","messageId":"20180615182727.172075-6-dstolee@microsoft.com","threadId":"48714","inReplyTo":"20180615182727.172075-1-dstolee@microsoft.com","subject":"[PATCH v2 5/7] ewah_bitmap: delete unused 'ewah_not()'","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-15T18:27:48Z","receivedAt":"2018-06-15T18:28:00Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Reported-by: Ramsay Jones \nSigned-off-by: Derrick Stolee \n---\n ewah/ewah_bitmap.c | 19 -------------------\n ewah/ewok.h | 7 -------\n 2 files changed, 26 deletions(-)\n\ndiff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\nindex 559adde37c..3fa3edf2a3 100644\n--- a/ewah/ewah_bitmap.c\n+++ b/ewah/ewah_bitmap.c\n@@ -376,25 +376,6 @@ void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent)\n \t\tread_new_rlw(it);\n }\n \n-void ewah_not(struct ewah_bitmap *self)\n-{\n-\tsize_t pointer = 0;\n-\n-\twhile (pointer < self->buffer_size) {\n-\t\teword_t *word = &self->buffer[pointer];\n-\t\tsize_t literals, k;\n-\n-\t\trlw_xor_run_bit(word);\n-\t\t++pointer;\n-\n-\t\tliterals = rlw_get_literal_words(word);\n-\t\tfor (k = 0; k < literals; ++k) {\n-\t\t\tself->buffer[pointer] = ~self->buffer[pointer];\n-\t\t\t++pointer;\n-\t\t}\n-\t}\n-}\n-\n void ewah_xor(\n \tstruct ewah_bitmap *ewah_i,\n \tstruct ewah_bitmap *ewah_j,\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex 8dae8a608c..a467645eec 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -95,13 +95,6 @@ int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len);\n \n uint32_t ewah_checksum(struct ewah_bitmap *self);\n \n-/**\n- * Logical not (bitwise negation) in-place on the bitmap\n- *\n- * This operation is linear time based on the size of the bitmap.\n- */\n-void ewah_not(struct ewah_bitmap *self);\n-\n /**\n * Call the given callback with the position of every single bit\n * that has been set on the bitmap.\n-- \n2.18.0.rc1\n\n"},{"id":"350284","messageId":"20180615182727.172075-7-dstolee@microsoft.com","threadId":"48714","inReplyTo":"20180615182727.172075-1-dstolee@microsoft.com","subject":"[PATCH v2 6/7] ewah_bitmap: delete unused 'ewah_or()'","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-15T18:27:50Z","receivedAt":"2018-06-15T18:28:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Reported-by: Ramsay Jones \nSigned-off-by: Derrick Stolee \n---\n ewah/ewah_bitmap.c | 69 ----------------------------------------------\n ewah/ewok.h | 5 ----\n 2 files changed, 74 deletions(-)\n\ndiff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\nindex 3fa3edf2a3..017c677f98 100644\n--- a/ewah/ewah_bitmap.c\n+++ b/ewah/ewah_bitmap.c\n@@ -440,75 +440,6 @@ void ewah_xor(\n \tout->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);\n }\n \n-void ewah_or(\n-\tstruct ewah_bitmap *ewah_i,\n-\tstruct ewah_bitmap *ewah_j,\n-\tstruct ewah_bitmap *out)\n-{\n-\tstruct rlw_iterator rlw_i;\n-\tstruct rlw_iterator rlw_j;\n-\tsize_t literals;\n-\n-\trlwit_init(&rlw_i, ewah_i);\n-\trlwit_init(&rlw_j, ewah_j);\n-\n-\twhile (rlwit_word_size(&rlw_i) > 0 && rlwit_word_size(&rlw_j) > 0) {\n-\t\twhile (rlw_i.rlw.running_len > 0 || rlw_j.rlw.running_len > 0) {\n-\t\t\tstruct rlw_iterator *prey, *predator;\n-\n-\t\t\tif (rlw_i.rlw.running_len < rlw_j.rlw.running_len) {\n-\t\t\t\tprey = &rlw_i;\n-\t\t\t\tpredator = &rlw_j;\n-\t\t\t} else {\n-\t\t\t\tprey = &rlw_j;\n-\t\t\t\tpredator = &rlw_i;\n-\t\t\t}\n-\n-\t\t\tif (predator->rlw.running_bit) {\n-\t\t\t\tewah_add_empty_words(out, 0,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t\trlwit_discard_first_words(prey,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t\trlwit_discard_first_words(predator,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t} else {\n-\t\t\t\tsize_t index = rlwit_discharge(prey, out,\n-\t\t\t\t\tpredator->rlw.running_len, 0);\n-\t\t\t\tewah_add_empty_words(out, 0,\n-\t\t\t\t\tpredator->rlw.running_len - index);\n-\t\t\t\trlwit_discard_first_words(predator,\n-\t\t\t\t\tpredator->rlw.running_len);\n-\t\t\t}\n-\t\t}\n-\n-\t\tliterals = min_size(\n-\t\t\trlw_i.rlw.literal_words,\n-\t\t\trlw_j.rlw.literal_words);\n-\n-\t\tif (literals) {\n-\t\t\tsize_t k;\n-\n-\t\t\tfor (k = 0; k < literals; ++k) {\n-\t\t\t\tewah_add(out,\n-\t\t\t\t\trlw_i.buffer[rlw_i.literal_word_start + k] |\n-\t\t\t\t\trlw_j.buffer[rlw_j.literal_word_start + k]\n-\t\t\t\t);\n-\t\t\t}\n-\n-\t\t\trlwit_discard_first_words(&rlw_i, literals);\n-\t\t\trlwit_discard_first_words(&rlw_j, literals);\n-\t\t}\n-\t}\n-\n-\tif (rlwit_word_size(&rlw_i) > 0)\n-\t\trlwit_discharge(&rlw_i, out, ~0, 0);\n-\telse\n-\t\trlwit_discharge(&rlw_j, out, ~0, 0);\n-\n-\tout->bit_size = max_size(ewah_i->bit_size, ewah_j->bit_size);\n-}\n-\n-\n #define BITMAP_POOL_MAX 16\n static struct ewah_bitmap *bitmap_pool[BITMAP_POOL_MAX];\n static size_t bitmap_pool_size;\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex a467645eec..a540df2aa9 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -157,11 +157,6 @@ void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent);\n */\n int ewah_iterator_next(eword_t *next, struct ewah_iterator *it);\n \n-void ewah_or(\n-\tstruct ewah_bitmap *ewah_i,\n-\tstruct ewah_bitmap *ewah_j,\n-\tstruct ewah_bitmap *out);\n-\n void ewah_xor(\n \tstruct ewah_bitmap *ewah_i,\n \tstruct ewah_bitmap *ewah_j,\n-- \n2.18.0.rc1\n\n"},{"id":"350287","messageId":"xmqq602j293p.fsf@gitster-ct.c.googlers.com","threadId":"48714","inReplyTo":"20180615175111.GD3067@sigill.intra.peff.net","subject":"Re: [PATCH 3/3] ewah: drop ewah_serialize_native function","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-06-15T18:33:14Z","receivedAt":"2018-06-15T18:33:19Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> One thing that gave me pause on ripping out more code is that I have\n> some bitmap-related patches on my send-to-upstream list, and I wasn't\n> sure if they used any of this code. But I checked against your patches,\n> and no, this can all go (which makes sense -- my patches are about using\n> .bitmap files in more places, so they build at a higher level).\n>\n> So your patches look good to me, modulo the declarations that Ramsay\n> noticed should be removed, too.\n\nI'll queue your 1/3 and 4/3 (without 2&3/3) for now and let Derrick\nand you handle the removal of unused stuff separately on top, so\nthat the fix-proper can graduate earlier than the rest.\n\nThanks.\n"},{"id":"350288","messageId":"20180615184634.GA18633@sigill.intra.peff.net","threadId":"48714","inReplyTo":"xmqq602j293p.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 3/3] ewah: drop ewah_serialize_native function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-06-15T18:46:35Z","receivedAt":"2018-06-15T18:46:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jun 15, 2018 at 11:33:14AM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > One thing that gave me pause on ripping out more code is that I have\n> > some bitmap-related patches on my send-to-upstream list, and I wasn't\n> > sure if they used any of this code. But I checked against your patches,\n> > and no, this can all go (which makes sense -- my patches are about using\n> > .bitmap files in more places, so they build at a higher level).\n> >\n> > So your patches look good to me, modulo the declarations that Ramsay\n> > noticed should be removed, too.\n> \n> I'll queue your 1/3 and 4/3 (without 2&3/3) for now and let Derrick\n> and you handle the removal of unused stuff separately on top, so\n> that the fix-proper can graduate earlier than the rest.\n\nThanks, that sounds good. 2/3 is sort-of-related in that it has an\ninteger overflow bug like the one in 1/3. But the fact that it is not\nused at all makes it very low priority. ;)\n\n-Peff\n"},{"id":"350289","messageId":"xmqq1sd7288z.fsf@gitster-ct.c.googlers.com","threadId":"48714","inReplyTo":"20180615182727.172075-1-dstolee@microsoft.com","subject":"Re: [PATCH v2 0/7] Delete unused methods in EWAH bitmap","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-06-15T18:51:40Z","receivedAt":"2018-06-15T18:51:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> The EWAH bitmap code includes several logical operations that are\n> important for a general-purpose bitmap library. However, Git only\n> uses the XOR operation for storing deltas between reachability\n> bitmaps. This means that we can delete the following unused methods:\n>\n> * ewah_and()\n> * ewah_and_not()\n> * ewah_not()\n> * ewah_or()\n> * ewah_serialize()\n>\n> We can also delete the unused methods bitmap_clear() and\n> bitmap_each_bit().\n>\n> Derrick Stolee (7):\n> ewah/bitmap.c: delete unused 'bitmap_clear()'\n> ewah/bitmap.c: delete unused 'bitmap_each_bit()'\n> ewah_bitmap: delete unused 'ewah_and()'\n> ewah_bitmap: delete unused 'ewah_and_not()'\n> ewah_bitmap: delete unused 'ewah_not()'\n> ewah_bitmap: delete unused 'ewah_or()'\n> ewah_io: delete unused 'ewah_serialize()'\n>\n> ewah/bitmap.c | 32 -------\n> ewah/ewah_bitmap.c | 229 ---------------------------------------------\n> ewah/ewah_io.c | 10 --\n> ewah/ewok.h | 25 -----\n> 4 files changed, 296 deletions(-)\n>\n>\n> base-commit: fc54c1af3ec09bab8b8ea09768c2da4069b7f53e\n\nThanks. \n\newah_clear() can become file-scope static, and\nrlwit_discharge_empty() can be eliminated. I do not know if either\nis worth doing, though.\n\n ewah/ewah_bitmap.c | 20 ++++++++++++--------\n ewah/ewah_rlw.c | 8 --------\n ewah/ewok.h | 6 ------\n ewah/ewok_rlw.h | 1 -\n 4 files changed, 12 insertions(+), 23 deletions(-)\n\ndiff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\nindex 017c677f98..d59b1afe3d 100644\n--- a/ewah/ewah_bitmap.c\n+++ b/ewah/ewah_bitmap.c\n@@ -276,6 +276,18 @@ void ewah_each_bit(struct ewah_bitmap *self, void (*callback)(size_t, void*), vo\n \t}\n }\n \n+/**\n+ * Clear all the bits in the bitmap. Does not free or resize\n+ * memory.\n+ */\n+static void ewah_clear(struct ewah_bitmap *self)\n+{\n+\tself->buffer_size = 1;\n+\tself->buffer[0] = 0;\n+\tself->bit_size = 0;\n+\tself->rlw = self->buffer;\n+}\n+\n struct ewah_bitmap *ewah_new(void)\n {\n \tstruct ewah_bitmap *self;\n@@ -288,14 +300,6 @@ struct ewah_bitmap *ewah_new(void)\n \treturn self;\n }\n \n-void ewah_clear(struct ewah_bitmap *self)\n-{\n-\tself->buffer_size = 1;\n-\tself->buffer[0] = 0;\n-\tself->bit_size = 0;\n-\tself->rlw = self->buffer;\n-}\n-\n void ewah_free(struct ewah_bitmap *self)\n {\n \tif (!self)\ndiff --git a/ewah/ewah_rlw.c b/ewah/ewah_rlw.c\nindex b9643b7d0f..5093d43e2f 100644\n--- a/ewah/ewah_rlw.c\n+++ b/ewah/ewah_rlw.c\n@@ -104,11 +104,3 @@ size_t rlwit_discharge(\n \n \treturn index;\n }\n-\n-void rlwit_discharge_empty(struct rlw_iterator *it, struct ewah_bitmap *out)\n-{\n-\twhile (rlwit_word_size(it) > 0) {\n-\t\tewah_add_empty_words(out, 0, rlwit_word_size(it));\n-\t\trlwit_discard_first_words(it, rlwit_word_size(it));\n-\t}\n-}\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex 0c504f28e2..84b2a29faa 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -72,12 +72,6 @@ void ewah_pool_free(struct ewah_bitmap *self);\n */\n struct ewah_bitmap *ewah_new(void);\n \n-/**\n- * Clear all the bits in the bitmap. Does not free or resize\n- * memory.\n- */\n-void ewah_clear(struct ewah_bitmap *self);\n-\n /**\n * Free all the memory of the bitmap\n */\ndiff --git a/ewah/ewok_rlw.h b/ewah/ewok_rlw.h\nindex bb3c6ff7e0..7cdfdd0c02 100644\n--- a/ewah/ewok_rlw.h\n+++ b/ewah/ewok_rlw.h\n@@ -98,7 +98,6 @@ void rlwit_init(struct rlw_iterator *it, struct ewah_bitmap *bitmap);\n void rlwit_discard_first_words(struct rlw_iterator *it, size_t x);\n size_t rlwit_discharge(\n \tstruct rlw_iterator *it, struct ewah_bitmap *out, size_t max, int negate);\n-void rlwit_discharge_empty(struct rlw_iterator *it, struct ewah_bitmap *out);\n \n static inline size_t rlwit_word_size(struct rlw_iterator *it)\n {\n\n\n"},{"id":"350290","messageId":"ee8a1b8f-d14e-218c-3bdf-82908fefbec0@gmail.com","threadId":"48714","inReplyTo":"xmqq1sd7288z.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v2 0/7] Delete unused methods in EWAH bitmap","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-06-15T18:56:43Z","receivedAt":"2018-06-15T18:56:48Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/15/2018 2:51 PM, Junio C Hamano wrote:\n> Derrick Stolee writes:\n>\n>> The EWAH bitmap code includes several logical operations that are\n>> important for a general-purpose bitmap library. However, Git only\n>> uses the XOR operation for storing deltas between reachability\n>> bitmaps. This means that we can delete the following unused methods:\n>>\n>> * ewah_and()\n>> * ewah_and_not()\n>> * ewah_not()\n>> * ewah_or()\n>> * ewah_serialize()\n>>\n>> We can also delete the unused methods bitmap_clear() and\n>> bitmap_each_bit().\n>>\n>> Derrick Stolee (7):\n>> ewah/bitmap.c: delete unused 'bitmap_clear()'\n>> ewah/bitmap.c: delete unused 'bitmap_each_bit()'\n>> ewah_bitmap: delete unused 'ewah_and()'\n>> ewah_bitmap: delete unused 'ewah_and_not()'\n>> ewah_bitmap: delete unused 'ewah_not()'\n>> ewah_bitmap: delete unused 'ewah_or()'\n>> ewah_io: delete unused 'ewah_serialize()'\n>>\n>> ewah/bitmap.c | 32 -------\n>> ewah/ewah_bitmap.c | 229 ---------------------------------------------\n>> ewah/ewah_io.c | 10 --\n>> ewah/ewok.h | 25 -----\n>> 4 files changed, 296 deletions(-)\n>>\n>>\n>> base-commit: fc54c1af3ec09bab8b8ea09768c2da4069b7f53e\n> Thanks.\n>\n> ewah_clear() can become file-scope static, and\n> rlwit_discharge_empty() can be eliminated. I do not know if either\n> is worth doing, though.\n\nWith Peff's patches, this is true. When I applied your diff to my patch \nalone we could not do that.\n\nIf you want to create a commit with the below, I'm happy to add my \n\"Reviewed-by: Derrick Stolee \"\n\nGood team effort today!\n\n>\n> ewah/ewah_bitmap.c | 20 ++++++++++++--------\n> ewah/ewah_rlw.c | 8 --------\n> ewah/ewok.h | 6 ------\n> ewah/ewok_rlw.h | 1 -\n> 4 files changed, 12 insertions(+), 23 deletions(-)\n>\n> diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\n> index 017c677f98..d59b1afe3d 100644\n> --- a/ewah/ewah_bitmap.c\n> +++ b/ewah/ewah_bitmap.c\n> @@ -276,6 +276,18 @@ void ewah_each_bit(struct ewah_bitmap *self, void (*callback)(size_t, void*), vo\n> \t}\n> }\n> \n> +/**\n> + * Clear all the bits in the bitmap. Does not free or resize\n> + * memory.\n> + */\n> +static void ewah_clear(struct ewah_bitmap *self)\n> +{\n> +\tself->buffer_size = 1;\n> +\tself->buffer[0] = 0;\n> +\tself->bit_size = 0;\n> +\tself->rlw = self->buffer;\n> +}\n> +\n> struct ewah_bitmap *ewah_new(void)\n> {\n> \tstruct ewah_bitmap *self;\n> @@ -288,14 +300,6 @@ struct ewah_bitmap *ewah_new(void)\n> \treturn self;\n> }\n> \n> -void ewah_clear(struct ewah_bitmap *self)\n> -{\n> -\tself->buffer_size = 1;\n> -\tself->buffer[0] = 0;\n> -\tself->bit_size = 0;\n> -\tself->rlw = self->buffer;\n> -}\n> -\n> void ewah_free(struct ewah_bitmap *self)\n> {\n> \tif (!self)\n> diff --git a/ewah/ewah_rlw.c b/ewah/ewah_rlw.c\n> index b9643b7d0f..5093d43e2f 100644\n> --- a/ewah/ewah_rlw.c\n> +++ b/ewah/ewah_rlw.c\n> @@ -104,11 +104,3 @@ size_t rlwit_discharge(\n> \n> \treturn index;\n> }\n> -\n> -void rlwit_discharge_empty(struct rlw_iterator *it, struct ewah_bitmap *out)\n> -{\n> -\twhile (rlwit_word_size(it) > 0) {\n> -\t\tewah_add_empty_words(out, 0, rlwit_word_size(it));\n> -\t\trlwit_discard_first_words(it, rlwit_word_size(it));\n> -\t}\n> -}\n> diff --git a/ewah/ewok.h b/ewah/ewok.h\n> index 0c504f28e2..84b2a29faa 100644\n> --- a/ewah/ewok.h\n> +++ b/ewah/ewok.h\n> @@ -72,12 +72,6 @@ void ewah_pool_free(struct ewah_bitmap *self);\n> */\n> struct ewah_bitmap *ewah_new(void);\n> \n> -/**\n> - * Clear all the bits in the bitmap. Does not free or resize\n> - * memory.\n> - */\n> -void ewah_clear(struct ewah_bitmap *self);\n> -\n> /**\n> * Free all the memory of the bitmap\n> */\n> diff --git a/ewah/ewok_rlw.h b/ewah/ewok_rlw.h\n> index bb3c6ff7e0..7cdfdd0c02 100644\n> --- a/ewah/ewok_rlw.h\n> +++ b/ewah/ewok_rlw.h\n> @@ -98,7 +98,6 @@ void rlwit_init(struct rlw_iterator *it, struct ewah_bitmap *bitmap);\n> void rlwit_discard_first_words(struct rlw_iterator *it, size_t x);\n> size_t rlwit_discharge(\n> \tstruct rlw_iterator *it, struct ewah_bitmap *out, size_t max, int negate);\n> -void rlwit_discharge_empty(struct rlw_iterator *it, struct ewah_bitmap *out);\n> \n> static inline size_t rlwit_word_size(struct rlw_iterator *it)\n> {\n>\n>\n\n"},{"id":"350292","messageId":"xmqqwouzzvjh.fsf@gitster-ct.c.googlers.com","threadId":"48714","inReplyTo":"20180615172121.GA3067@sigill.intra.peff.net","subject":"Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-06-15T19:42:10Z","receivedAt":"2018-06-15T19:42:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Fri, Jun 15, 2018 at 07:10:28PM +0200, SZEDER Gábor wrote:\n>\n>> > I said \"yuck\" because the original does not work if there happen to\n>> > be more than (or for that matter, less than) one '.bitmap' file\n>> > there. But at least as long as there is one, it should work ;-)\n>> \n>> Well, the test starts with 'git repack -ad', so there can be only one\n>> bitmap file. (Unless something is broken, of course, but the second\n>> test would catch that much earlier.)\n>\n> Right. I almost put \"head -1\" in there, but we know that we just created\n> a single bitmap. And my thought was that if we don't, the test would\n> blow up horribly, which is exactly what you want.\n\nYes, and \"file=$(ls gl*b) &&\" breaks if there is no matching file\n(iow, I said 'for that matter, less than' which was incorrect), so\nthe original is OK in practice.\n\nThanks.\n"},{"id":"350293","messageId":"xmqqsh5nzvfs.fsf@gitster-ct.c.googlers.com","threadId":"48714","inReplyTo":"20180615172656.GB3067@sigill.intra.peff.net","subject":"Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-06-15T19:44:23Z","receivedAt":"2018-06-15T19:44:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Fri, Jun 15, 2018 at 10:05:42AM -0700, Junio C Hamano wrote:\n>\n>> > -\tmemcpy(self->buffer, ptr, self->buffer_size * sizeof(eword_t));\n>> > -\tptr += self->buffer_size * sizeof(eword_t);\n>> \n>> \n>> > +\tdata_len = st_mult(self->buffer_size, sizeof(eword_t));\n>> \n>> This is a faithful conversion from the original, but I somehow would\n>> have appreciated if the latter were not sizeof(eword_t) but rather\n>> sizeof(self->buffer_size[0]), especially as I wondered ...\n>\n> I actually thought about going the _other_ way. The sizeof(eword_t) is\n> not something we can change, but is actually decided by the on-disk\n> format. So I wondered if this should be much more clearly \"hey, this is\n> 8 bytes\". Possibly with an assert(sizeof(*self->buffer_size) == 8).\n\nHmph, that's a thought.\n"},{"id":"350295","messageId":"xmqqo9gbzv8b.fsf@gitster-ct.c.googlers.com","threadId":"48714","inReplyTo":"ee8a1b8f-d14e-218c-3bdf-82908fefbec0@gmail.com","subject":"Re: [PATCH v2 0/7] Delete unused methods in EWAH bitmap","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-06-15T19:48:52Z","receivedAt":"2018-06-15T19:48:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n>> ewah_clear() can become file-scope static, and\n>> rlwit_discharge_empty() can be eliminated. I do not know if either\n>> is worth doing, though.\n>\n> With Peff's patches, this is true. When I applied your diff to my\n> patch alone we could not do that.\n\nYeah, as I organized the patches on two topics in this order:\n\n jk/ewah-bounds-check (build on 'maint')\n Peff's 1/3\n Peff's 4/3\n\n ds/ewah-cleanup (build on top of the above)\n 7 patches in this series\n Peff's 2/3\n Peff's 3/3\n\nat the end, these two changes become possible. Again, I am not sure\nif these are worth doing, so I'll leave it out of these two series,\nat least for now.\n\nThis is a tangent, but I too felt that roaring paper quite a\npleasant read ;-)\n"},{"id":"350299","messageId":"20180615203559.GA26653@sigill.intra.peff.net","threadId":"48714","inReplyTo":"xmqqo9gbzv8b.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v2 0/7] Delete unused methods in EWAH bitmap","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-06-15T20:35:59Z","receivedAt":"2018-06-15T20:36:04Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jun 15, 2018 at 12:48:52PM -0700, Junio C Hamano wrote:\n\n> Derrick Stolee writes:\n> \n> >> ewah_clear() can become file-scope static, and\n> >> rlwit_discharge_empty() can be eliminated. I do not know if either\n> >> is worth doing, though.\n> >\n> > With Peff's patches, this is true. When I applied your diff to my\n> > patch alone we could not do that.\n> \n> Yeah, as I organized the patches on two topics in this order:\n> \n> jk/ewah-bounds-check (build on 'maint')\n> Peff's 1/3\n> Peff's 4/3\n> \n> ds/ewah-cleanup (build on top of the above)\n> 7 patches in this series\n> Peff's 2/3\n> Peff's 3/3\n\nThanks, I wasn't sure if I should resend mine on top, but it looks like\nyou've got it all organized already.\n\n> at the end, these two changes become possible. Again, I am not sure\n> if these are worth doing, so I'll leave it out of these two series,\n> at least for now.\n\nIMHO the extra cleanups you showed are worth doing.\n\n-Peff\n"},{"id":"350300","messageId":"20180615203813.GA27008@sigill.intra.peff.net","threadId":"48714","inReplyTo":"1685a358-f033-64e0-2e12-df3a1c10af19@gmail.com","subject":"Re: [PATCH 4/3] ewah: adjust callers of ewah_read_mmap()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-06-15T20:38:13Z","receivedAt":"2018-06-15T20:38:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jun 15, 2018 at 02:23:44PM -0400, Derrick Stolee wrote:\n\n> If we are considering changing the reachability bitmap, then I'm very\n> intrigued. I think the number one thing to consider is to use the\n> multi-pack-index as a reference point (with a stable object order) so the\n> objects can be repacked independently from the reachability bitmap\n> computation. If we are changing the model at that level, then it is worth\n> thinking about other questions, like how we index the file or how we\n> compress the bitmaps.\n\nI'm open to a new format if it provides significant improvements over\nthe existing one. I think the existing bitmaps have served us well for\nseveral years, but they do have a few weaknesses. Some of which I\nmentioned before, but the most obvious one is that being very\npack-oriented they require repacking to update (and don't handle\ncross-pack reachability at all). I know that doesn't fly for\nWindows-sized repos at all, but it would also be nice if we could do\nincremental updates more cheaply (e.g., after every push instead of just\nonce a day).\n\nThe Roaring stuff looks really interesting. I'm curious about the stable\nobject order you guys use. Because EWAH is basically run-length-encoding,\nit benefits hugely from having the bitmaps in pack order (where there's\na enormous locality with respect to reachability) as opposed to sha1\norder (where it's essentially random).\n\nIs your stable object order based on traversing the commit graph? Or\ndoes Roaring do a sufficiently better job of compressing the jumbled\nsha1 order?\n\n-Peff\n"},{"id":"350324","messageId":"20180616143513.10086-1-szeder.dev@gmail.com","threadId":"48714","inReplyTo":"20180615033112.GA20390@sigill.intra.peff.net","subject":"Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2018-06-16T14:35:13Z","receivedAt":"2018-06-16T14:35:25Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"> diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\n> index 423c0a475f..237ee6e5fc 100755\n> --- a/t/t5310-pack-bitmaps.sh\n> +++ b/t/t5310-pack-bitmaps.sh\n> @@ -331,4 +331,17 @@ test_expect_success 'pack reuse respects --incremental' '\n> \tgit show-index actual &&\n> \ttest_cmp expect actual\n> '\n> +\n> +test_expect_success 'truncated bitmap fails gracefully' '\n> +\tgit repack -ad &&\n> +\tgit rev-list --use-bitmap-index --count --all >expect &&\n> +\tbitmap=$(ls .git/objects/pack/*.bitmap) &&\n> +\ttest_when_finished \"rm -f $bitmap\" &&\n> +\thead -c 512 <$bitmap >$bitmap.tmp &&\n> +\tmv $bitmap.tmp $bitmap &&\n\nThis line turns out to be problematic on OSX and ultimately causes the\ntest to fail.\n\nWhen OSX's 'mv's destination is read-only, it asks whether to replace\nthe destination even though in the test its stdin is not a terminal\n(and thus doesn't conform to POSIX[1]). Since the '.bitmap' file is\nread-only, and since 'mv' obviously doesn't get an affirmative\nresponse from /dev/null, the original '.bitmap' file is not\noverwritten, the subsequent 'git rev-list' doesn't print any error\nmessage, and finally 'test_i18ngrep' causes the test to fail.\n\nThe relevant part of the '-x' test output on Travis CI:\n\n ++mv .git/objects/pack/pack-8886db3fce4f9657c1a43fee7d3ea4f2a4b5be2d.bitmap.tmp .git/objects/pack/pack-8886db3fce4f9657c1a43fee7d3ea4f2a4b5be2d.bitmap\n override r--r--r-- travis/staff for .git/objects/pack/pack-8886db3fce4f9657c1a43fee7d3ea4f2a4b5be2d.bitmap? (y/n [n]) not overwritten\n ++git rev-list --use-bitmap-index --count --all\n ++test_cmp expect actual\n ++diff -u expect actual\n ++test_i18ngrep corrupt stderr\n ++eval 'last_arg=${2}'\n +++last_arg=stderr\n ++test -f stderr\n ++test 2 -lt 2\n ++test 'x!' = xcorrupt\n ++test -n ''\n ++test 'x!' = xcorrupt\n ++grep corrupt stderr\n ++echo 'error: '\\''grep corrupt' 'stderr'\\'' didn'\\''t find a match in:'\n error: 'grep corrupt stderr' didn't find a match in:\n ++test -s stderr\n ++echo ''\n \n ++return 1\n error: last command exited with $?=1\n not ok 43 - truncated bitmap fails gracefully\n\nAs far as I can tell, 'mv -f' appears to make the test work on OSX as\nwell.\n\nI've run a build job with an additional 'grep ^override\nt/test-results/*.out' command following the tests to see whether there\nare any other cases where OSX 'mv' doesn't overwrite a read-only file\nwithout causing the tests to fail, but found nothing. (But note that\nthe OSX build jobs don't run all tests.)\n\n[1] http://pubs.opengroup.org/onlinepubs/9699919799/utilities/mv.html\n\n> +\tgit rev-list --use-bitmap-index --count --all >actual 2>stderr &&\n> +\ttest_cmp expect actual &&\n> +\ttest_i18ngrep corrupt stderr\n> +'\n> +\n"},{"id":"350328","messageId":"20180616191400.GB8914@sigill.intra.peff.net","threadId":"48714","inReplyTo":"20180616143513.10086-1-szeder.dev@gmail.com","subject":"Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-06-16T19:14:00Z","receivedAt":"2018-06-16T19:14:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Jun 16, 2018 at 04:35:13PM +0200, SZEDER Gábor wrote:\n\n> > +\thead -c 512 <$bitmap >$bitmap.tmp &&\n> > +\tmv $bitmap.tmp $bitmap &&\n> \n> This line turns out to be problematic on OSX and ultimately causes the\n> test to fail.\n> \n> When OSX's 'mv's destination is read-only, it asks whether to replace\n> the destination even though in the test its stdin is not a terminal\n> (and thus doesn't conform to POSIX[1]). Since the '.bitmap' file is\n> read-only, and since 'mv' obviously doesn't get an affirmative\n> response from /dev/null, the original '.bitmap' file is not\n> overwritten, the subsequent 'git rev-list' doesn't print any error\n> message, and finally 'test_i18ngrep' causes the test to fail.\n\nRight, sorry, I should have remembered that we've run into this before.\nUsing \"mv -f\" is the standard solution. E.g., c20d4d702f (t1450: use \"mv\n-f\" within loose object directory, 2017-01-24).\n\nJunio, can you squash this in to jk/ewah-bounds-check~1?\n\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex c4ed88030c..b11bc392a8 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -338,7 +338,7 @@ test_expect_success 'truncated bitmap fails gracefully' '\n \tbitmap=$(ls .git/objects/pack/*.bitmap) &&\n \ttest_when_finished \"rm -f $bitmap\" &&\n \thead -c 512 <$bitmap >$bitmap.tmp &&\n-\tmv $bitmap.tmp $bitmap &&\n+\tmv -f $bitmap.tmp $bitmap &&\n \tgit rev-list --use-bitmap-index --count --all >actual 2>stderr &&\n \ttest_cmp expect actual &&\n \ttest_i18ngrep corrupt stderr\n\n-Peff\n"},{"id":"350525","messageId":"CO2PR01MB20383AC645BE4FD6BF47C697F1700@CO2PR01MB2038.prod.exchangelabs.com","threadId":"48714","inReplyTo":"2067D731-C415-4D19-8CDA-90D7DC638397@l4w.io","subject":"RE: security: potential out-of-bound read at ewah_io.c |ewah_read_mmap|","fromName":"Dyer, Edwin","fromEmail":"edwin.dyer@alliancedata.com","sentAt":"2018-06-19T19:00:48Z","receivedAt":"2018-06-19T19:00:55Z","isPatch":false,"sender":{"key":"edwin.dyer@alliancedata.com","avatar":null},"body":"Greetings, all:\n\nJust curious if there was any additional comment on this potential OOB? I may have missed it and if so, apologies for the ask.\n\nCheers,\n\nEd\n\n\n-----Original Message-----\nFrom: git-owner@vger.kernel.org [mailto:git-owner@vger.kernel.org] On Behalf Of Luat Nguyen\nSent: Thursday, June 14, 2018 7:00 PM\nTo: git@vger.kernel.org\nSubject: security: potential out-of-bound read at ewah_io.c |ewah_read_mmap|\n\nHi folks,\n\nRecently, I’ve found a security issue related to out-of-bound read at function named `ewah_read_mmap`\n\nAssume that, an attacker can put malicious `./git/index` into a repo by somehow.\n\nSince there is lack of check whether the remaining size of `ptr`is equal to `buffer_size` or not.\n\nSo the code reads exceed the buffer of `ptr` and reach to higher page. In this case, it is `/lib/x86_64-linux-gnu/ld-2.23.so`.\n\nLeads to infoleak. You can find more details and asan crash below.\n\n\n\n# xxd .git/index\n00000000: 4449 5243 0000 0002 0000 0000 4653 4d4e DIRC........FSMN\n00000010: 0000 0024 0000 0001 1538 2489 c8fc 3616 ...$.....8$...6.\n00000020: 0000 0014 0000 0000 0000 2000 4141 .......... .AA\n ^ evil size here = 0x2000\n\n\n***** SNIP CODE *****\n\nint ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len) { … \n\tself->buffer_size = self->alloc_size = get_be32(ptr);\n\tptr += sizeof(uint32_t);\n… \n\tmemcpy(self->buffer, ptr, self->buffer_size * sizeof(eword_t));\n\n\n[memory map]\n\n 0x7f990eca3000 0x7f990eca4000 r--p 1000 0 /media/sf_Fuzz/vuln_repo/.git/index <— where `ptr` is placed\n 0x7f990eca4000 0x7f990eca5000 r--p 1000 25000 /lib/x86_64-linux-gnu/ld-2.23.so <— memcpy will reach here\n 0x7f990eca5000 0x7f990eca6000 rw-p 1000 26000 /lib/x86_64-linux-gnu/ld-2.23.so <— and here \n\n\n[ ASAN log ]\n\nroot@guest:/media/sf_SHARE/vuln_repo# /media/sf_SHARE/git-master-asan/git status =================================================================\n==4324==ERROR: AddressSanitizer: unknown-crash on address 0x7f6f235b0000 at pc 0x0000004bba79 bp 0x7ffc75e68850 sp 0x7ffc75e68000 READ of size 65536 at 0x7f6f235b0000 thread T0\n #0 0x4bba78 in __asan_memcpy /tmp/final/llvm.src/projects/compiler-rt/lib/asan/asan_interceptors_memintrinsics.cc:23:3\n #1 0x8c910e in ewah_read_mmap /media/sf_SHARE/git-master-asan/ewah/ewah_io.c:144:2\n #2 0x8e2534 in read_fsmonitor_extension /media/sf_SHARE/git-master-asan/fsmonitor.c:46:8\n #3 0xa05862 in read_index_extension /media/sf_SHARE/git-master-asan/read-cache.c:1615:3\n #4 0xa046f3 in do_read_index /media/sf_SHARE/git-master-asan/read-cache.c:1872:7\n #5 0xa03325 in read_index_from /media/sf_SHARE/git-master-asan/read-cache.c:1913:8\n #6 0xa03231 in read_index /media/sf_SHARE/git-master-asan/read-cache.c:1634:9\n #7 0x9de5e8 in read_index_preload /media/sf_SHARE/git-master-asan/preload-index.c:119:15\n #8 0x566cc6 in cmd_status /media/sf_SHARE/git-master-asan/builtin/commit.c:1358:2\n #9 0x4ede8c in run_builtin /media/sf_SHARE/git-master-asan/git.c:417:11\n #10 0x4ea939 in handle_builtin /media/sf_SHARE/git-master-asan/git.c:632:8\n #11 0x4ed655 in run_argv /media/sf_SHARE/git-master-asan/git.c:684:4\n #12 0x4ea037 in cmd_main /media/sf_SHARE/git-master-asan/git.c:761:19\n #13 0x759c8b in main /media/sf_SHARE/git-master-asan/common-main.c:45:9\n #14 0x7f6f2243382f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)\n #15 0x41c268 in _start (/media/sf_SHARE/git-master-asan/git+0x41c268)\n\nAddress 0x7f6f235b0000 is a wild pointer.\nSUMMARY: AddressSanitizer: unknown-crash /tmp/final/llvm.src/projects/compiler-rt/lib/asan/asan_interceptors_memintrinsics.cc:23:3 in __asan_memcpy Shadow bytes around the buggy address:\n 0x0fee646adfb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n 0x0fee646adfc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n 0x0fee646adfd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n 0x0fee646adfe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n 0x0fee646adff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 =>0x0fee646ae000:[fe]fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe\n 0x0fee646ae010: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe\n 0x0fee646ae020: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe\n 0x0fee646ae030: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe\n 0x0fee646ae040: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe\n 0x0fee646ae050: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe Shadow byte legend (one shadow byte represents 8 application bytes):\n Addressable: 00\n Partially addressable: 01 02 03 04 05 06 07\n Heap left redzone: fa\n Freed heap region: fd\n Stack left redzone: f1\n Stack mid redzone: f2\n Stack right redzone: f3\n Stack after return: f5\n Stack use after scope: f8\n Global redzone: f9\n Global init order: f6\n Poisoned by user: f7\n Container overflow: fc\n Array cookie: ac\n Intra object redzone: bb\n ASan internal: fe\n Left alloca redzone: ca\n Right alloca redzone: cb\n==4324==ABORTING\nroot@guest:/media/sf_SHARE/vuln_repo#\n\n\nRegards,\nLuat Nguyen.\n\n______________________________________________________________________\nThe information contained in this e-mail message and any attachments may be privileged and confidential. If the reader of this message is not the intended recipient or an agent responsible for delivering it to the intended recipient, you are hereby notified that any review, dissemination, distribution or copying of this communication is strictly prohibited. If you have received this communication in error, please notify the sender immediately by replying to this e-mail and delete the message and any attachments from your computer.\n______________________________________________________________________\n"},{"id":"350529","messageId":"20180619195649.GA1499@sigill.intra.peff.net","threadId":"48714","inReplyTo":"CO2PR01MB20383AC645BE4FD6BF47C697F1700@CO2PR01MB2038.prod.exchangelabs.com","subject":"Re: security: potential out-of-bound read at ewah_io.c |ewah_read_mmap|","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-06-19T19:56:50Z","receivedAt":"2018-06-19T19:56:55Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jun 19, 2018 at 07:00:48PM +0000, Dyer, Edwin wrote:\n\n> Just curious if there was any additional comment on this potential\n> OOB? I may have missed it and if so, apologies for the ask.\n\nThe fix is in master, and should be part of the upcoming v2.18. See\ncommit 9d2e330b17 (ewah_read_mmap: bounds-check mmap reads, 2018-06-14).\n\n-Peff\n"}]}