security: potential out-of-bound read at ewah_io.c |ewah_read_mmap|
Hi folks,
Recently, I’ve found a security issue related to out-of-bound read at function named ewah_read_mmap
Assume that, an attacker can put malicious ./git/index into a repo by somehow.
Since there is lack of check whether the remaining size of ptris equal to buffer_size or not.
So 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.
Leads to infoleak. You can find more details and asan crash below.
# xxd .git/index
00000000: 4449 5243 0000 0002 0000 0000 4653 4d4e DIRC........FSMN
00000010: 0000 0024 0000 0001 1538 2489 c8fc 3616 ...$.....8$...6.
00000020: 0000 0014 0000 0000 0000 2000 4141 .......... .AA
^ evil size here = 0x2000***** SNIP CODE *****
int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len) {
…
self->buffer_size = self->alloc_size = get_be32(ptr); ptr += sizeof(uint32_t); … memcpy(self->buffer, ptr, self->buffer_size * sizeof(eword_t));
[memory map]
0x7f990eca3000 0x7f990eca4000 r--p 1000 0 /media/sf_Fuzz/vuln_repo/.git/index <— where `ptr` is placed
0x7f990eca4000 0x7f990eca5000 r--p 1000 25000 /lib/x86_64-linux-gnu/ld-2.23.so <— memcpy will reach here
0x7f990eca5000 0x7f990eca6000 rw-p 1000 26000 /lib/x86_64-linux-gnu/ld-2.23.so <— and here [ ASAN log ]
root@guest:/media/sf_SHARE/vuln_repo# /media/sf_SHARE/git-master-asan/git status
=================================================================
==4324==ERROR: AddressSanitizer: unknown-crash on address 0x7f6f235b0000 at pc 0x0000004bba79 bp 0x7ffc75e68850 sp 0x7ffc75e68000
READ of size 65536 at 0x7f6f235b0000 thread T0
#0 0x4bba78 in __asan_memcpy /tmp/final/llvm.src/projects/compiler-rt/lib/asan/asan_interceptors_memintrinsics.cc:23:3
#1 0x8c910e in ewah_read_mmap /media/sf_SHARE/git-master-asan/ewah/ewah_io.c:144:2
#2 0x8e2534 in read_fsmonitor_extension /media/sf_SHARE/git-master-asan/fsmonitor.c:46:8
#3 0xa05862 in read_index_extension /media/sf_SHARE/git-master-asan/read-cache.c:1615:3
#4 0xa046f3 in do_read_index /media/sf_SHARE/git-master-asan/read-cache.c:1872:7
#5 0xa03325 in read_index_from /media/sf_SHARE/git-master-asan/read-cache.c:1913:8
#6 0xa03231 in read_index /media/sf_SHARE/git-master-asan/read-cache.c:1634:9
#7 0x9de5e8 in read_index_preload /media/sf_SHARE/git-master-asan/preload-index.c:119:15
#8 0x566cc6 in cmd_status /media/sf_SHARE/git-master-asan/builtin/commit.c:1358:2
#9 0x4ede8c in run_builtin /media/sf_SHARE/git-master-asan/git.c:417:11
#10 0x4ea939 in handle_builtin /media/sf_SHARE/git-master-asan/git.c:632:8
#11 0x4ed655 in run_argv /media/sf_SHARE/git-master-asan/git.c:684:4
#12 0x4ea037 in cmd_main /media/sf_SHARE/git-master-asan/git.c:761:19
#13 0x759c8b in main /media/sf_SHARE/git-master-asan/common-main.c:45:9
#14 0x7f6f2243382f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
#15 0x41c268 in _start (/media/sf_SHARE/git-master-asan/git+0x41c268)Address 0x7f6f235b0000 is a wild pointer.
SUMMARY: 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:
0x0fee646adfb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0fee646adfc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0fee646adfd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0fee646adfe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
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
0x0fee646ae010: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
0x0fee646ae020: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
0x0fee646ae030: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
0x0fee646ae040: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
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):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa Freed heap region: fd Stack left redzone: f1 Stack mid redzone: f2 Stack right redzone: f3 Stack after return: f5 Stack use after scope: f8 Global redzone: f9 Global init order: f6 Poisoned by user: f7 Container overflow: fc Array cookie: ac Intra object redzone: bb ASan internal: fe Left alloca redzone: ca Right alloca redzone: cb
==4324==ABORTING
root@guest:/media/sf_SHARE/vuln_repo#
Regards,
Luat Nguyen.
Quoted 1 line · Luat Nguyen
Recently, I’ve found a security issue related to out-of-bound read at function named
ewah_read_mmap
Thanks, this is definitely a bug worth addressing. But note...
Quoted 1 line
Assume that, an attacker can put malicious
./git/indexinto a repo by somehow.
We generally don't consider .git/index (or pack .bitmap files, which also use this implementation) to be a major part of Git's attack surface, since they are generated locally. And if you can write to somebody's .git directory, there are already much easier ways to execute arbitrary code.
Quoted 2 lines
Since there is lack of check whether the remaining size of
ptris equal tobuffer_sizeor not.
Yep. We also fail to check if we even have enough bytes to read the buffer_size in the first place.
Here are some patches. The first one fixes the problem you found. The second one drops some dead code that has a related problem. And the third just drops some dead code that I noticed in the same file. :)
[1/3]: ewah_read_mmap: bounds-check mmap reads [2/3]: ewah: drop ewah_deserialize function [3/3]: ewah: drop ewah_serialize_native function
ewah/ewah_io.c | 106 ++++++++-------------------------------- ewah/ewok.h | 4 +- t/t5310-pack-bitmaps.sh | 13 +++++ 3 files changed, 35 insertions(+), 88 deletions(-)
-Peff
PATCH 1/3 ewah_read_mmap: bounds-check mmap reads
The on-disk ewah format tells us how big the ewah data is, and we blindly read that much from the buffer without considering whether the mmap'd data is long enough, which can lead to out-of-bound reads.
Let's make sure we have data available before reading it, both for the ewah header/footer as well as for the bit data itself. In particular:
- keep our ptr/len pair in sync as we move through the buffer, and check it before each read
- check the size for integer overflow (this should be impossible on 64-bit, as the size is given as a 32-bit count of 8-byte words, but is possible on a 32-bit system)
- return the number of bytes read as an ssize_t instead of an int, again to prevent integer overflow
- compute the return value using a pointer difference; this should yield the same result as the existing code, but makes it more obvious that we got our computations right
The included test is far from comprehensive, as it just picks a static point at which to truncate the generated bitmap. But in practice this will hit in the middle of an ewah and make sure we're at least exercising this code.
--- ewah/ewah_io.c | 25 +++++++++++++++++++++---- ewah/ewok.h | 2 +- t/t5310-pack-bitmaps.sh | 13 +++++++++++++ 3 files changed, 35 insertions(+), 5 deletions(-)
ewah/ewah_io.c +21 -4
@@ -122,16 +122,23 @@ int ewah_serialize_strbuf(struct ewah_bitmap *self, struct strbuf *sb)return ewah_serialize_to (self, write_strbuf, sb); } -int ewah_read_mmap (struct ewah_bitmap *self,const void *map,size_t len) +ssize_t ewah_read_mmap (struct ewah_bitmap *self,const void *map,size_t len) {const uint8_t *ptr = map; +size_t data_len;size_t i; +if (len <sizeof (uint32_t )) +return error ("corrupt ewah bitmap: eof before bit size" ); self->bit_size =get_be32 (ptr); ptr +=sizeof (uint32_t ); + len -=sizeof (uint32_t ); +if (len <sizeof (uint32_t )) +return error ("corrupt ewah bitmap: eof before length" ); self->buffer_size = self->alloc_size =get_be32 (ptr); ptr +=sizeof (uint32_t ); + len -=sizeof (uint32_t );REALLOC_ARRAY (self->buffer, self->alloc_size);
@@ -141,15 +148,25 @@ int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len)* the endianness conversion in a separate pass to ensure * we're loading 8-byte aligned words. */ -memcpy (self->buffer, ptr, self->buffer_size *sizeof (eword_t)); - ptr += self->buffer_size *sizeof (eword_t); + data_len =st_mult (self->buffer_size,sizeof (eword_t)); +if (len < data_len) +return error ("corrupt ewah bitmap: eof in data " +"(%" PRIuMAX" bytes short)" , + (uintmax_t)(data_len - len)); +memcpy (self->buffer, ptr, data_len); + ptr += data_len; + len -= data_len;for (i =0 ; i < self->buffer_size; ++i) self->buffer[i] =ntohll (self->buffer[i]); +if (len <sizeof (uint32_t )) +return error ("corrupt ewah bitmap: eof before rlw" ); self->rlw = self->buffer +get_be32 (ptr); + ptr +=sizeof (uint32_t ); + len -=sizeof (uint32_t ); -return (3 *4 ) + (self->buffer_size *8 ); +return ptr - (const uint8_t *)map; }int ewah_deserialize (struct ewah_bitmap *self,int fd)
ewah/ewok.h +1 -1
@@ -91,7 +91,7 @@ int ewah_serialize_native(struct ewah_bitmap *self, int fd);int ewah_serialize_strbuf (struct ewah_bitmap *self,struct strbuf *);int ewah_deserialize (struct ewah_bitmap *self,int fd); -int ewah_read_mmap (struct ewah_bitmap *self,const void *map,size_t len); +ssize_t ewah_read_mmap (struct ewah_bitmap *self,const void *map,size_t len);uint32_t ewah_checksum (struct ewah_bitmap *self);
t/t5310-pack-bitmaps.sh +13 -0
@@ -331,4 +331,17 @@ test_expect_success 'pack reuse respects --incremental' ' git show-index <empty.idx >actual && test_cmp expect actual ' + +test_expect_success 'truncated bitmap fails gracefully' ' + git repack -ad && + git rev-list --use-bitmap-index --count --all >expect && + bitmap=$(ls .git/objects/pack/*.bitmap) && + test_when_finished "rm -f $bitmap" && + head -c 512 <$bitmap >$bitmap.tmp && + mv $bitmap.tmp $bitmap && + git rev-list --use-bitmap-index --count --all >actual 2>stderr && + test_cmp expect actual && + test_i18ngrep corrupt stderr +' + test_done
Signature · 1 line
2.18.0.rc2.534.g53d976aeb8
Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads
t/t5310-pack-bitmaps.sh test_expect_success 'pack reuse respects --incremental' ' · line 338
Quoted 13 lines
t/t5310-pack-bitmaps.sh +5
-0@@ -331,4 +331,17 @@ test_expect_success 'pack reuse respects --incremental' ' git show-index <empty.idx >actual && test_cmp expect actual ' + +test_expect_success 'truncated bitmap fails gracefully' ' + git repack -ad && + git rev-list --use-bitmap-index --count --all >expect && + bitmap=$(ls .git/objects/pack/*.bitmap) &&
I think the 'ls' is unnecessary and this would do:
bitmap=.git/objects/pack/*.bitmap
Quoted 13 lines
t/t5310-pack-bitmaps.sh +8
-0+ test_when_finished "rm -f $bitmap" && + head -c 512 <$bitmap >$bitmap.tmp && + mv $bitmap.tmp $bitmap && + git rev-list --use-bitmap-index --count --all >actual 2>stderr && + test_cmp expect actual && + test_i18ngrep corrupt stderr +' + test_doneSignature · 1 line
2.18.0.rc2.534.g53d976aeb8
Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads
Quoted 5 lines · SZEDER Gábor
t/t5310-pack-bitmaps.sh test_expect_success 'pack reuse respects --incremental' ' · line 338
Quoted 1 line
t/t5310-pack-bitmaps.sh +1
-0+ bitmap=$(ls .git/objects/pack/*.bitmap) &&I think the 'ls' is unnecessary and this would do:
bitmap=.git/objects/pack/*.bitmap
Yuck.
Quoted 1 line
t/t5310-pack-bitmaps.sh test_expect_success 'pack reuse respects --incremental' ' · line 339
Quoted 1 line
t/t5310-pack-bitmaps.sh +1
-0+ test_when_finished "rm -f $bitmap" &&
OK, this will become "rm -f .git/objects/pack/*.bitmap" and then eval that implements when-finished would make it work OK.
Quoted 1 line
t/t5310-pack-bitmaps.sh test_expect_success 'pack reuse respects --incremental' ' · line 340
Quoted 1 line
t/t5310-pack-bitmaps.sh +1
-0+ head -c 512 <$bitmap >$bitmap.tmp &&
The reading side would be OK but would the writing side also be alright?
makefile=Mak?file
head -n 4 <$makefile >$makefile.tmp
/bin/ls -t -1 | head -n 1
Mak?file.tmpHmm...
Quoted 1 line
t/t5310-pack-bitmaps.sh test_expect_success 'pack reuse respects --incremental' ' · line 341
Quoted 1 line
t/t5310-pack-bitmaps.sh +1
-0+ mv $bitmap.tmp $bitmap &&
Likewise...
I said "yuck" because the original does not work if there happen to be more than (or for that matter, less than) one '.bitmap' file there. But at least as long as there is one, it should work ;-)
Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads
Quoted 9 lines · Junio C Hamano
Quoted 5 lines · SZEDER Gábor
Quoted 1 line
+ bitmap=$(ls .git/objects/pack/*.bitmap) &&
I think the 'ls' is unnecessary and this would do:
bitmap=.git/objects/pack/*.bitmap
Yuck.
Oh, wow, now this is embarrassing...
Quoted 3 lines
I said "yuck" because the original does not work if there happen to be more than (or for that matter, less than) one '.bitmap' file there. But at least as long as there is one, it should work ;-)
Well, the test starts with 'git repack -ad', so there can be only one bitmap file. (Unless something is broken, of course, but the second test would catch that much earlier.)
Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads
Quoted 7 lines · SZEDER Gábor
Quoted 3 lines
I said "yuck" because the original does not work if there happen to be more than (or for that matter, less than) one '.bitmap' file there. But at least as long as there is one, it should work ;-)
Well, the test starts with 'git repack -ad', so there can be only one bitmap file. (Unless something is broken, of course, but the second test would catch that much earlier.)
Right. I almost put "head -1" in there, but we know that we just created a single bitmap. And my thought was that if we don't, the test would blow up horribly, which is exactly what you want.
-Peff
Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads
Quoted 6 lines · Jeff King
Quoted 4 lines · SZEDER Gábor
Quoted 3 lines
I said "yuck" because the original does not work if there happen to be more than (or for that matter, less than) one '.bitmap' file there. But at least as long as there is one, it should work ;-)
Quoted 7 lines
Quoted 3 lines
Well, the test starts with 'git repack -ad', so there can be only one bitmap file. (Unless something is broken, of course, but the second test would catch that much earlier.)
Right. I almost put "head -1" in there, but we know that we just created a single bitmap. And my thought was that if we don't, the test would blow up horribly, which is exactly what you want.
Yes, and "file=$(ls gl*b) &&" breaks if there is no matching file (iow, I said 'for that matter, less than' which was incorrect), so the original is OK in practice.
Thanks.
Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads
In reply to Jeff KingQuoted 30 lines · Jeff King
ewah/ewah_io.c +8
-1@@ -122,16 +122,23 @@ int ewah_serialize_strbuf(struct ewah_bitmap *self, struct strbuf *sb)return ewah_serialize_to (self, write_strbuf, sb); } -int ewah_read_mmap (struct ewah_bitmap *self,const void *map,size_t len) +ssize_t ewah_read_mmap (struct ewah_bitmap *self,const void *map,size_t len) {const uint8_t *ptr = map; +size_t data_len;size_t i; +if (len <sizeof (uint32_t )) +return error ("corrupt ewah bitmap: eof before bit size" ); self->bit_size =get_be32 (ptr); ptr +=sizeof (uint32_t ); + len -=sizeof (uint32_t ); +if (len <sizeof (uint32_t )) +return error ("corrupt ewah bitmap: eof before length" ); self->buffer_size = self->alloc_size =get_be32 (ptr); ptr +=sizeof (uint32_t ); + len -=sizeof (uint32_t );REALLOC_ARRAY (self->buffer, self->alloc_size);
ewah/ewah_io.c int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len) · line 153
Quoted 8 lines
ewah/ewah_io.c +1
-2@@ -141,15 +148,25 @@ int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len)* the endianness conversion in a separate pass to ensure * we're loading 8-byte aligned words. */ -memcpy (self->buffer, ptr, self->buffer_size *sizeof (eword_t)); - ptr += self->buffer_size *sizeof (eword_t); + data_len =st_mult (self->buffer_size,sizeof (eword_t));
This is a faithful conversion from the original, but I somehow would have appreciated if the latter were not sizeof(eword_t) but rather sizeof(self->buffer_size[0]), especially as I wondered ...
ewah/ewah_io.c int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len) · line 161
Quoted 10 lines
ewah/ewah_io.c +7
-0+if (len < data_len) +return error ("corrupt ewah bitmap: eof in data " +"(%" PRIuMAX" bytes short)" , + (uintmax_t)(data_len - len)); +memcpy (self->buffer, ptr, data_len); + ptr += data_len; + len -= data_len;for (i =0 ; i < self->buffer_size; ++i) self->buffer[i] =ntohll (self->buffer[i]);
... what individual datum one iteration of this loop is copying, and then realized "buffer_size" is a misleading field name (anything that claims to be size and not measuring in bytes is misleading to me ;-).
ewah/ewah_io.c int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len) · line 169
Quoted 8 lines
ewah/ewah_io.c +5
-1+if (len <sizeof (uint32_t )) +return error ("corrupt ewah bitmap: eof before rlw" ); self->rlw = self->buffer +get_be32 (ptr); + ptr +=sizeof (uint32_t ); + len -=sizeof (uint32_t ); -return (3 *4 ) + (self->buffer_size *8 ); +return ptr - (const uint8_t *)map;
Much nicer; I needed to wonder what these 12 and 8 in the original are.
ewah/ewah_io.c int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len) · line 172
Quoted 4 lines
ewah/ewah_io.c +1
-1int ewah_deserialize (struct ewah_bitmap *self,int fd); -int ewah_read_mmap (struct ewah_bitmap *self,const void *map,size_t len); +ssize_t ewah_read_mmap (struct ewah_bitmap *self,const void *map,size_t len);
I double checked all the callers and made sure that they are already prepared to react sensibly to error returns, which is good.
Quoted 25 lines
uint32_tewah_checksum(struct ewah_bitmap *self);t/t5310-pack-bitmaps.sh +13
-0@@ -331,4 +331,17 @@ test_expect_success 'pack reuse respects --incremental' ' git show-index <empty.idx >actual && test_cmp expect actual ' + +test_expect_success 'truncated bitmap fails gracefully' ' + git repack -ad && + git rev-list --use-bitmap-index --count --all >expect && + bitmap=$(ls .git/objects/pack/*.bitmap) && + test_when_finished "rm -f $bitmap" && + head -c 512 <$bitmap >$bitmap.tmp && + mv $bitmap.tmp $bitmap && + git rev-list --use-bitmap-index --count --all >actual 2>stderr && + test_cmp expect actual && + test_i18ngrep corrupt stderr +' + test_done
Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads
Quoted 9 lines · Junio C Hamano
ewah/ewah_io.c int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len)
Quoted 5 lines
ewah/ewah_io.c +1
-2-memcpy (self->buffer, ptr, self->buffer_size *sizeof (eword_t)); - ptr += self->buffer_size *sizeof (eword_t); + data_len =st_mult (self->buffer_size,sizeof (eword_t));This is a faithful conversion from the original, but I somehow would have appreciated if the latter were not
sizeof(eword_t)but rathersizeof(self->buffer_size[0]), especially as I wondered ...
I actually thought about going the _other_ way. The sizeof(eword_t) is not something we can change, but is actually decided by the on-disk format. So I wondered if this should be much more clearly "hey, this is 8 bytes". Possibly with an assert(sizeof(*self->buffer_size) == 8).
And yes, I think having the on-disk format specify the size in 8-byte double words is vaguely crazy. Blame JGit. ;) Or maybe even blame the original EWAH authors, this may have originated even earlier (I didn't dig).
Quoted 8 lines
Quoted 8 lines
ewah/ewah_io.c +7
-0+if (len < data_len) +return error ("corrupt ewah bitmap: eof in data " +"(%" PRIuMAX" bytes short)" , + (uintmax_t)(data_len - len)); +memcpy (self->buffer, ptr, data_len); + ptr += data_len; + len -= data_len;
Quoted 6 lines
ewah/ewah_io.c int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len) · line 161
Quoted 2 lines
ewah/ewah_io.c +0
-0for (i =0 ; i < self->buffer_size; ++i) self->buffer[i] =ntohll (self->buffer[i]);... what individual datum one iteration of this loop is copying, and then realized "
buffer_size" is a misleading field name (anything that claims to be size and not measuring in bytes is misleading to me ;-).
Yeah, it confused me at first, too. I don't mind changing these kinds of cosmetics, but I'd like to do it in a separate patch from this fix.
Quoted 4 lines
ewah/ewah_io.c int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len) · line 169
Quoted 2 lines
ewah/ewah_io.c +1
-1-return (3 *4 ) + (self->buffer_size *8 ); +return ptr - (const uint8_t *)map;Much nicer; I needed to wonder what these 12 and 8 in the original are.
Me too. ;)
Quoted 6 lines
ewah/ewok.h int ewah_serialize_native(struct ewah_bitmap *self, int fd); · line 94
Quoted 3 lines
int
ewah_deserialize(struct ewah_bitmap *self, int fd);ewah/ewok.h +1
-1-int ewah_read_mmap (struct ewah_bitmap *self,const void *map,size_t len); +ssize_t ewah_read_mmap (struct ewah_bitmap *self,const void *map,size_t len);I double checked all the callers and made sure that they are already prepared to react sensibly to error returns, which is good.
Yep, modulo the int/ssize_t thing from the fourth patch.
-Peff
Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads
Quoted 12 lines · Jeff King
Quoted 9 lines · Junio C Hamano
ewah/ewah_io.c int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len)
Quoted 5 lines
ewah/ewah_io.c +1
-2-memcpy (self->buffer, ptr, self->buffer_size *sizeof (eword_t)); - ptr += self->buffer_size *sizeof (eword_t); + data_len =st_mult (self->buffer_size,sizeof (eword_t));This is a faithful conversion from the original, but I somehow would have appreciated if the latter were not
sizeof(eword_t)but rathersizeof(self->buffer_size[0]), especially as I wondered ...
Quoted 4 lines
I actually thought about going the _other_ way. The
sizeof(eword_t)is not something we can change, but is actually decided by the on-disk format. So I wondered if this should be much more clearly "hey, this is 8 bytes". Possibly with anassert(sizeof(*self->buffer_size) == 8).
Hmph, that's a thought.
Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads
In reply to Jeff KingQuoted 6 lines
t/t5310-pack-bitmaps.sh +0
-0@@ -331,4 +331,17 @@ test_expect_success 'pack reuse respects --incremental' ' git show-index <empty.idx >actual &&
t/t5310-pack-bitmaps.sh test_expect_success 'pack reuse respects --incremental' ' · line 341
Quoted 10 lines
t/t5310-pack-bitmaps.sh +8
-0test_cmp expect actual ' + +test_expect_success 'truncated bitmap fails gracefully' ' + git repack -ad && + git rev-list --use-bitmap-index --count --all >expect && + bitmap=$(ls .git/objects/pack/*.bitmap) && + test_when_finished "rm -f $bitmap" && + head -c 512 <$bitmap >$bitmap.tmp && + mv $bitmap.tmp $bitmap &&
This line turns out to be problematic on OSX and ultimately causes the test to fail.
When OSX's 'mv's destination is read-only, it asks whether to replace the destination even though in the test its stdin is not a terminal (and thus doesn't conform to POSIX[1]). Since the '.bitmap' file is read-only, and since 'mv' obviously doesn't get an affirmative response from /dev/null, the original '.bitmap' file is not overwritten, the subsequent 'git rev-list' doesn't print any error message, and finally 'test_i18ngrep' causes the test to fail.
The relevant part of the '-x' test output on Travis CI:
++mv .git/objects/pack/pack-8886db3fce4f9657c1a43fee7d3ea4f2a4b5be2d.bitmap.tmp .git/objects/pack/pack-8886db3fce4f9657c1a43fee7d3ea4f2a4b5be2d.bitmap override r--r--r-- travis/staff for .git/objects/pack/pack-8886db3fce4f9657c1a43fee7d3ea4f2a4b5be2d.bitmap? (y/n [n]) not overwritten ++git rev-list --use-bitmap-index --count --all
++test_cmp expect actual
++diff -u expect actual
++test_i18ngrep corrupt stderr
++eval 'last_arg=${2}'
+++last_arg=stderr
++test -f stderr
++test 2 -lt 2
++test 'x!' = xcorrupt
++test -n ''
++test 'x!' = xcorrupt
++grep corrupt stderr
++echo 'error: '\''grep corrupt' 'stderr'\'' didn'\''t find a match in:'
error: 'grep corrupt stderr' didn't find a match in:
++test -s stderr
++echo '<File '\''stderr'\'' is empty>'
<File 'stderr' is empty>
++return 1
error: last command exited with $?=1
not ok 43 - truncated bitmap fails gracefully
As far as I can tell, 'mv -f' appears to make the test work on OSX as well.
I've run a build job with an additional 'grep ^override t/test-results/*.out' command following the tests to see whether there are any other cases where OSX 'mv' doesn't overwrite a read-only file without causing the tests to fail, but found nothing. (But note that the OSX build jobs don't run all tests.)
[1] http://pubs.opengroup.org/onlinepubs/9699919799/utilities/mv.html
Quoted 5 lines
t/t5310-pack-bitmaps.sh +5
-0+ git rev-list --use-bitmap-index --count --all >actual 2>stderr && + test_cmp expect actual && + test_i18ngrep corrupt stderr +' +
Re: [PATCH 1/3] ewah_read_mmap: bounds-check mmap reads
Quoted 6 lines · SZEDER Gábor
Review
Quoted 2 lines
(quoted diff) +2
-0+ head -c 512 <$bitmap >$bitmap.tmp && + mv $bitmap.tmp $bitmap &&This line turns out to be problematic on OSX and ultimately causes the test to fail.
Quoted 7 lines
When OSX's 'mv's destination is read-only, it asks whether to replace the destination even though in the test its stdin is not a terminal (and thus doesn't conform to POSIX[1]). Since the '.bitmap' file is read-only, and since 'mv' obviously doesn't get an affirmative response from
/dev/null, the original '.bitmap' file is not overwritten, the subsequent 'git rev-list' doesn't print any error message, and finally 'test_i18ngrep' causes the test to fail.
Right, sorry, I should have remembered that we've run into this before. Using "mv -f" is the standard solution. E.g., c20d4d702f (t1450: use "mv -f" within loose object directory, 2017-01-24).
Junio, can you squash this in to jk/ewah-bounds-check~1?
t/t5310-pack-bitmaps.sh +1 -1
@@ -338,7 +338,7 @@ test_expect_success 'truncated bitmap fails gracefully' ' bitmap=$(ls .git/objects/pack/*.bitmap) && test_when_finished "rm -f $bitmap" && head -c 512 <$bitmap >$bitmap.tmp && - mv $bitmap.tmp $bitmap && + mv -f $bitmap.tmp $bitmap && git rev-list --use-bitmap-index --count --all >actual 2>stderr && test_cmp expect actual && test_i18ngrep corrupt stderr
-Peff
PATCH 2/3 ewah: drop ewah_deserialize function
In reply to Jeff KingWe don't call this function, and in fact never have since it was added (at least not in iterations of the ewah patches that got merged). Instead we use ewah_read_mmap().
Let's drop the unused code.
Note to anybody who later wants to resurrect this: it does not check for integer overflow in the ewah data size, meaning it may be possible to convince the code to allocate a too-small buffer and read() into it.
--- ewah/ewah_io.c | 55 -------------------------------------------------- ewah/ewok.h | 1 - 2 files changed, 56 deletions(-)
ewah/ewah_io.c +0 -55
@@ -168,58 +168,3 @@ ssize_t ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len)return ptr - (const uint8_t *)map; } - -int ewah_deserialize (struct ewah_bitmap *self,int fd) -{ -size_t i; -eword_t dump[2048 ]; -const size_t words_per_dump =sizeof (dump) /sizeof (eword_t); -uint32_t bitsize, word_count, rlw_pos; - -eword_t *buffer =NULL ; -size_t words_left; - -ewah_clear (self); - -/* 32 bit -- bit size for the map */ -if (read (fd, &bitsize,4 ) !=4 ) -return -1 ; - - self->bit_size = (size_t )ntohl (bitsize); - -/** 32 bit -- number of compressed 64-bit words */ -if (read (fd, &word_count,4 ) !=4 ) -return -1 ; - - self->buffer_size = self->alloc_size = (size_t )ntohl (word_count); -REALLOC_ARRAY (self->buffer, self->alloc_size); - -/** 64 bit x N -- compressed words */ - buffer = self->buffer; - words_left = self->buffer_size; - -while (words_left >= words_per_dump) { -if (read (fd, dump,sizeof (dump)) !=sizeof (dump)) -return -1 ; - -for (i =0 ; i < words_per_dump; ++i, ++buffer) - *buffer =ntohll (dump[i]); - - words_left -= words_per_dump; - } - -if (words_left) { -if (read (fd, dump, words_left *8 ) != words_left *8 ) -return -1 ; - -for (i =0 ; i < words_left; ++i, ++buffer) - *buffer =ntohll (dump[i]); - } - -/** 32 bit -- position for the RLW */ -if (read (fd, &rlw_pos,4 ) !=4 ) -return -1 ; - - self->rlw = self->buffer +ntohl (rlw_pos); -return 0 ; -}
ewah/ewok.h +0 -1
@@ -90,7 +90,6 @@ int ewah_serialize(struct ewah_bitmap *self, int fd);int ewah_serialize_native (struct ewah_bitmap *self,int fd);int ewah_serialize_strbuf (struct ewah_bitmap *self,struct strbuf *); -int ewah_deserialize (struct ewah_bitmap *self,int fd);ssize_t ewah_read_mmap (struct ewah_bitmap *self,const void *map,size_t len);uint32_t ewah_checksum (struct ewah_bitmap *self);
Signature · 1 line
2.18.0.rc2.534.g53d976aeb8
PATCH 3/3 ewah: drop ewah_serialize_native function
In reply to Jeff KingWe don't call this function, and never have. The on-disk bitmap format uses network-byte-order integers, meaning that we cannot use the native-byte-order format written here.
Let's drop it in the name of simplicity.
--- ewah/ewah_io.c | 26 -------------------------- ewah/ewok.h | 1 - 2 files changed, 27 deletions(-)
ewah/ewah_io.c +0 -26
@@ -20,32 +20,6 @@#include "ewok.h" #include "strbuf.h" -int ewah_serialize_native (struct ewah_bitmap *self,int fd) -{ -uint32_t write32; -size_t to_write = self->buffer_size *8 ; - -/* 32 bit -- bit size for the map */ - write32 = (uint32_t )self->bit_size; -if (write (fd, &write32,4 ) !=4 ) -return -1 ; - -/** 32 bit -- number of compressed 64-bit words */ - write32 = (uint32_t )self->buffer_size; -if (write (fd, &write32,4 ) !=4 ) -return -1 ; - -if (write (fd, self->buffer, to_write) != to_write) -return -1 ; - -/** 32 bit -- position for the RLW */ - write32 = self->rlw - self->buffer; -if (write (fd, &write32,4 ) !=4 ) -return -1 ; - -return (3 *4 ) + to_write; -} -int ewah_serialize_to (struct ewah_bitmap *self,int (*write_fun)(void *,const void *,size_t ),void *data)
ewah/ewok.h +0 -1
@@ -87,7 +87,6 @@ int ewah_serialize_to(struct ewah_bitmap *self,int (*write_fun)(void *out,const void *buf,size_t len), void *out);int ewah_serialize (struct ewah_bitmap *self,int fd); -int ewah_serialize_native (struct ewah_bitmap *self,int fd);int ewah_serialize_strbuf (struct ewah_bitmap *self,struct strbuf *);ssize_t ewah_read_mmap (struct ewah_bitmap *self,const void *map,size_t len);
Signature · 1 line
2.18.0.rc2.534.g53d976aeb8
Re: [PATCH 3/3] ewah: drop ewah_serialize_native function
Quoted 5 lines · Jeff King
We don't call this function, and never have. The on-disk bitmap format uses network-byte-order integers, meaning that we cannot use the native-byte-order format written here.
Let's drop it in the name of simplicity.
Hmm, if you are in the mood to drop ewah dead code, how about:
ewah/bitmap.o - bitmap_clear
ewah/bitmap.o - bitmap_each_bit
ewah/ewah_bitmap.o - ewah_and ewah/ewah_bitmap.o - ewah_and_not ewah/ewah_bitmap.o - ewah_not ewah/ewah_bitmap.o - ewah_or
... in addition to these *(de)serialize* functions. ;-)
ATB,
Ramsay Jones
Re: [PATCH 3/3] ewah: drop ewah_serialize_native function
Quoted 11 lines · Ramsay Jones
Quoted 5 lines · Jeff King
We don't call this function, and never have. The on-disk bitmap format uses network-byte-order integers, meaning that we cannot use the native-byte-order format written here.
Let's drop it in the name of simplicity.
Hmm, if you are in the mood to drop ewah dead code, how about:
Quoted 8 lines
ewah/bitmap.o-bitmap_clear
ewah/bitmap.o-bitmap_each_bitewah/ewah_bitmap.o - ewah_and ewah/ewah_bitmap.o - ewah_and_not ewah/ewah_bitmap.o - ewah_not ewah/ewah_bitmap.o - ewah_or... in addition to these *(de)serialize* functions. ;-)
Hmm, I didn't spot it at first, but ewah_serialize() also seems to be unused!
ATB,
Ramsay Jones
cover Delete unused methods in EWAH bitmap
The EWAH bitmap code includes several logical operations that are important for a general-purpose bitmap library. However, Git only uses the XOR operation for storing deltas between reachability bitmaps. This means that we can delete the following unused methods:
* ewah_and()
* ewah_and_not()
* ewah_not()
* ewah_or()
* ewah_serialize()
* ewah_serialize_native()
We can also delete the unused methods bitmap_clear() and bitmap_each_bit().
Derrick Stolee (8):
ewah/bitmap.c: delete unused 'bitmap_clear()' ewah/bitmap.c: delete unused 'bitmap_each_bit()'
ewah_bitmap: delete unused 'ewah_and()'
ewah_bitmap: delete unused 'ewah_and_not()'
ewah_bitmap: delete unused 'ewah_not()'
ewah_bitmap: delete unused 'ewah_or()'
ewah_io: delete unused 'ewah_serialize()'
ewah_io: delete unused 'ewah_serialize_native()'
ewah/bitmap.c | 32 ------- ewah/ewah_bitmap.c | 229 --------------------------------------------- ewah/ewah_io.c | 36 ------- ewah/ewok.h | 24 ----- 4 files changed, 321 deletions(-)
base-commit: fc54c1af3ec09bab8b8ea09768c2da4069b7f53e
Signature · 1 line
2.18.0.rc1
PATCH 1/8 ewah/bitmap.c: delete unused 'bitmap_clear()'
--- ewah/bitmap.c | 8 -------- 1 file changed, 8 deletions(-)
ewah/bitmap.c +0 -8
@@ -45,14 +45,6 @@ void bitmap_set(struct bitmap *self, size_t pos) self->words[block] |=EWAH_MASK (pos); } -void bitmap_clear (struct bitmap *self,size_t pos) -{ -size_t block =EWAH_BLOCK (pos); - -if (block < self->word_alloc) - self->words[block] &= ~EWAH_MASK (pos); -} -int bitmap_get (struct bitmap *self,size_t pos) {size_t block =EWAH_BLOCK (pos);
Signature · 1 line
2.18.0.rc1
Re: [PATCH 1/8] ewah/bitmap.c: delete unused 'bitmap_clear()'
Quoted 16 lines · Derrick Stolee
Reported-by Ramsay Jones <[email protected]>Signed-off-by Derrick Stolee <[email protected]>--- ewah/bitmap.c | 8 -------- 1 file changed, 8 deletions(-)ewah/bitmap.c +0
-1@@ -45,14 +45,6 @@ void bitmap_set(struct bitmap *self, size_t pos) self->words[block] |=EWAH_MASK (pos); } -void bitmap_clear (struct bitmap *self,size_t pos)
ewah/bitmap.c void bitmap_set(struct bitmap *self, size_t pos) · line 50
Quoted 10 lines
ewah/bitmap.c +0
-7-{ -size_t block =EWAH_BLOCK (pos); - -if (block < self->word_alloc) - self->words[block] &= ~EWAH_MASK (pos); -} -int bitmap_get (struct bitmap *self,size_t pos) {size_t block =EWAH_BLOCK (pos);
I haven't read all the patches yet, but what about the extern declaration in ewah/ewok.h?
ATB,
Ramsay Jones
Re: [PATCH 1/8] ewah/bitmap.c: delete unused 'bitmap_clear()'
Quoted 16 lines · Ramsay Jones
Quoted 14 lines · Derrick Stolee
Reported-by Ramsay Jones <[email protected]>Signed-off-by Derrick Stolee <[email protected]>--- ewah/bitmap.c | 8 -------- 1 file changed, 8 deletions(-)ewah/bitmap.c +0
-0@@ -45,14 +45,6 @@ void bitmap_set(struct bitmap *self, size_t pos) self->words[block] |=EWAH_MASK (pos); }
Quoted 14 lines
ewah/bitmap.c void bitmap_set(struct bitmap *self, size_t pos) · line 50
Quoted 12 lines
ewah/bitmap.c +0
-8-void bitmap_clear (struct bitmap *self,size_t pos) -{ -size_t block =EWAH_BLOCK (pos); - -if (block < self->word_alloc) - self->words[block] &= ~EWAH_MASK (pos); -} -int bitmap_get (struct bitmap *self,size_t pos) {size_t block =EWAH_BLOCK (pos);I haven't read all the patches yet, but what about the extern declaration in
ewah/ewok.h?
Thanks! I'll get that, too.
PATCH 2/8 ewah/bitmap.c: delete unused 'bitmap_each_bit()'
In reply to Derrick Stolee--- ewah/bitmap.c | 24 ------------------------ 1 file changed, 24 deletions(-)
ewah/bitmap.c +0 -24
@@ -129,30 +129,6 @@ void bitmap_or_ewah(struct bitmap *self, struct ewah_bitmap *other) self->words[i++] |= word; } -void bitmap_each_bit (struct bitmap *self,ewah_callback callback,void *data) -{ -size_t pos =0 , i; - -for (i =0 ; i < self->word_alloc; ++i) { -eword_t word = self->words[i]; -uint32_t offset; - -if (word == (eword_t )~0 ) { -for (offset =0 ; offset <BITS_IN_EWORD ; ++offset) -callback (pos++, data); - }else { -for (offset =0 ; offset <BITS_IN_EWORD ; ++offset) { -if ((word >> offset) ==0 ) -break ; - - offset +=ewah_bit_ctz64 (word >> offset); -callback (pos + offset, data); - } - pos +=BITS_IN_EWORD ; - } - } -} -size_t bitmap_popcount (struct bitmap *self) {size_t i, count =0 ;
Signature · 1 line
2.18.0.rc1
Re: [PATCH 2/8] ewah/bitmap.c: delete unused 'bitmap_each_bit()'
Quoted 32 lines · Derrick Stolee
Reported-by Ramsay Jones <[email protected]>Signed-off-by Derrick Stolee <[email protected]>--- ewah/bitmap.c | 24 ------------------------ 1 file changed, 24 deletions(-)ewah/bitmap.c +0
-17@@ -129,30 +129,6 @@ void bitmap_or_ewah(struct bitmap *self, struct ewah_bitmap *other) self->words[i++] |= word; } -void bitmap_each_bit (struct bitmap *self,ewah_callback callback,void *data) -{ -size_t pos =0 , i; - -for (i =0 ; i < self->word_alloc; ++i) { -eword_t word = self->words[i]; -uint32_t offset; - -if (word == (eword_t )~0 ) { -for (offset =0 ; offset <BITS_IN_EWORD ; ++offset) -callback (pos++, data); - }else { -for (offset =0 ; offset <BITS_IN_EWORD ; ++offset) { -if ((word >> offset) ==0 ) -break ; - - offset +=ewah_bit_ctz64 (word >> offset);
ewah/bitmap.c void bitmap_or_ewah(struct bitmap *self, struct ewah_bitmap *other) · line 134
Quoted 10 lines
ewah/bitmap.c +0
-7-callback (pos + offset, data); - } - pos +=BITS_IN_EWORD ; - } - } -} -size_t bitmap_popcount (struct bitmap *self) {size_t i, count =0 ;
Again, remove extern declaration from header file.
ATB,
Ramsay Jones
PATCH 3/8 ewah_bitmap: delete unused 'ewah_and()'
In reply to Derrick Stolee--- ewah/ewah_bitmap.c | 68 ---------------------------------------------- ewah/ewok.h | 5 ---- 2 files changed, 73 deletions(-)
ewah/ewah_bitmap.c +0 -68
@@ -459,74 +459,6 @@ void ewah_xor( out->bit_size =max_size (ewah_i->bit_size, ewah_j->bit_size); } -void ewah_and ( -struct ewah_bitmap *ewah_i, -struct ewah_bitmap *ewah_j, -struct ewah_bitmap *out) -{ -struct rlw_iterator rlw_i; -struct rlw_iterator rlw_j; -size_t literals; - -rlwit_init (&rlw_i, ewah_i); -rlwit_init (&rlw_j, ewah_j); - -while (rlwit_word_size (&rlw_i) >0 &&rlwit_word_size (&rlw_j) >0 ) { -while (rlw_i.rlw.running_len >0 || rlw_j.rlw.running_len >0 ) { -struct rlw_iterator *prey, *predator; - -if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) { - prey = &rlw_i; - predator = &rlw_j; - }else { - prey = &rlw_j; - predator = &rlw_i; - } - -if (predator->rlw.running_bit ==0 ) { -ewah_add_empty_words (out,0 , - predator->rlw.running_len); -rlwit_discard_first_words (prey, - predator->rlw.running_len); -rlwit_discard_first_words (predator, - predator->rlw.running_len); - }else { -size_t index =rlwit_discharge (prey, out, - predator->rlw.running_len,0 ); -ewah_add_empty_words (out,0 , - predator->rlw.running_len - index); -rlwit_discard_first_words (predator, - predator->rlw.running_len); - } - } - - literals =min_size ( - rlw_i.rlw.literal_words, - rlw_j.rlw.literal_words); - -if (literals) { -size_t k; - -for (k =0 ; k < literals; ++k) { -ewah_add (out, - rlw_i.buffer[rlw_i.literal_word_start + k] & - rlw_j.buffer[rlw_j.literal_word_start + k] - ); - } - -rlwit_discard_first_words (&rlw_i, literals); -rlwit_discard_first_words (&rlw_j, literals); - } - } - -if (rlwit_word_size (&rlw_i) >0 ) -rlwit_discharge_empty (&rlw_i, out); -else -rlwit_discharge_empty (&rlw_j, out); - - out->bit_size =max_size (ewah_i->bit_size, ewah_j->bit_size); -} - void ewah_and_not( struct ewah_bitmap *ewah_i, struct ewah_bitmap *ewah_j,
ewah/ewok.h +0 -5
@@ -179,11 +179,6 @@ void ewah_xor(struct ewah_bitmap *ewah_j, struct ewah_bitmap *out); -void ewah_and ( -struct ewah_bitmap *ewah_i, -struct ewah_bitmap *ewah_j, -struct ewah_bitmap *out); -/** * Direct word access */
Signature · 1 line
2.18.0.rc1
PATCH 4/8 ewah_bitmap: delete unused 'ewah_and_not()'
In reply to Derrick Stolee--- ewah/ewah_bitmap.c | 73 ---------------------------------------------- ewah/ewok.h | 5 ---- 2 files changed, 78 deletions(-)
ewah/ewah_bitmap.c +0 -73
@@ -459,79 +459,6 @@ void ewah_xor( out->bit_size =max_size (ewah_i->bit_size, ewah_j->bit_size); } -void ewah_and_not ( -struct ewah_bitmap *ewah_i, -struct ewah_bitmap *ewah_j, -struct ewah_bitmap *out) -{ -struct rlw_iterator rlw_i; -struct rlw_iterator rlw_j; -size_t literals; - -rlwit_init (&rlw_i, ewah_i); -rlwit_init (&rlw_j, ewah_j); - -while (rlwit_word_size (&rlw_i) >0 &&rlwit_word_size (&rlw_j) >0 ) { -while (rlw_i.rlw.running_len >0 || rlw_j.rlw.running_len >0 ) { -struct rlw_iterator *prey, *predator; - -if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) { - prey = &rlw_i; - predator = &rlw_j; - }else { - prey = &rlw_j; - predator = &rlw_i; - } - -if ((predator->rlw.running_bit && prey == &rlw_i) || - (!predator->rlw.running_bit && prey != &rlw_i)) { -ewah_add_empty_words (out,0 , - predator->rlw.running_len); -rlwit_discard_first_words (prey, - predator->rlw.running_len); -rlwit_discard_first_words (predator, - predator->rlw.running_len); - }else { -size_t index; -int negate_words; - - negate_words = (&rlw_i != prey); - index =rlwit_discharge (prey, out, - predator->rlw.running_len, negate_words); -ewah_add_empty_words (out, negate_words, - predator->rlw.running_len - index); -rlwit_discard_first_words (predator, - predator->rlw.running_len); - } - } - - literals =min_size ( - rlw_i.rlw.literal_words, - rlw_j.rlw.literal_words); - -if (literals) { -size_t k; - -for (k =0 ; k < literals; ++k) { -ewah_add (out, - rlw_i.buffer[rlw_i.literal_word_start + k] & - ~(rlw_j.buffer[rlw_j.literal_word_start + k]) - ); - } - -rlwit_discard_first_words (&rlw_i, literals); -rlwit_discard_first_words (&rlw_j, literals); - } - } - -if (rlwit_word_size (&rlw_i) >0 ) -rlwit_discharge (&rlw_i, out, ~0 ,0 ); -else -rlwit_discharge_empty (&rlw_j, out); - - out->bit_size =max_size (ewah_i->bit_size, ewah_j->bit_size); -} - void ewah_or( struct ewah_bitmap *ewah_i, struct ewah_bitmap *ewah_j,
ewah/ewok.h +0 -5
@@ -169,11 +169,6 @@ void ewah_or(struct ewah_bitmap *ewah_j, struct ewah_bitmap *out); -void ewah_and_not ( -struct ewah_bitmap *ewah_i, -struct ewah_bitmap *ewah_j, -struct ewah_bitmap *out); - void ewah_xor( struct ewah_bitmap *ewah_i, struct ewah_bitmap *ewah_j,
Signature · 1 line
2.18.0.rc1
PATCH 5/8 ewah_bitmap: delete unused 'ewah_not()'
In reply to Derrick Stolee--- ewah/ewah_bitmap.c | 19 ------------------- ewah/ewok.h | 7 ------- 2 files changed, 26 deletions(-)
ewah/ewah_bitmap.c +0 -19
@@ -376,25 +376,6 @@ void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent)read_new_rlw (it); } -void ewah_not (struct ewah_bitmap *self) -{ -size_t pointer =0 ; - -while (pointer < self->buffer_size) { -eword_t *word = &self->buffer[pointer]; -size_t literals, k; - -rlw_xor_run_bit (word); - ++pointer; - - literals =rlw_get_literal_words (word); -for (k =0 ; k < literals; ++k) { - self->buffer[pointer] = ~self->buffer[pointer]; - ++pointer; - } - } -} - void ewah_xor( struct ewah_bitmap *ewah_i, struct ewah_bitmap *ewah_j,
ewah/ewok.h +0 -7
@@ -95,13 +95,6 @@ int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len);uint32_t ewah_checksum (struct ewah_bitmap *self); -/** -* Logical not (bitwise negation) in-place on the bitmap -* -* This operation is linear time based on the size of the bitmap. -*/ -void ewah_not (struct ewah_bitmap *self); -/** * Call the given callback with the position of every single bit * that has been set on the bitmap.
Signature · 1 line
2.18.0.rc1
PATCH 6/8 ewah_bitmap: delete unused 'ewah_or()'
In reply to Derrick Stolee--- ewah/ewah_bitmap.c | 69 ---------------------------------------------- ewah/ewok.h | 5 ---- 2 files changed, 74 deletions(-)
ewah/ewah_bitmap.c +0 -69
@@ -440,75 +440,6 @@ void ewah_xor( out->bit_size =max_size (ewah_i->bit_size, ewah_j->bit_size); } -void ewah_or ( -struct ewah_bitmap *ewah_i, -struct ewah_bitmap *ewah_j, -struct ewah_bitmap *out) -{ -struct rlw_iterator rlw_i; -struct rlw_iterator rlw_j; -size_t literals; - -rlwit_init (&rlw_i, ewah_i); -rlwit_init (&rlw_j, ewah_j); - -while (rlwit_word_size (&rlw_i) >0 &&rlwit_word_size (&rlw_j) >0 ) { -while (rlw_i.rlw.running_len >0 || rlw_j.rlw.running_len >0 ) { -struct rlw_iterator *prey, *predator; - -if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) { - prey = &rlw_i; - predator = &rlw_j; - }else { - prey = &rlw_j; - predator = &rlw_i; - } - -if (predator->rlw.running_bit) { -ewah_add_empty_words (out,0 , - predator->rlw.running_len); -rlwit_discard_first_words (prey, - predator->rlw.running_len); -rlwit_discard_first_words (predator, - predator->rlw.running_len); - }else { -size_t index =rlwit_discharge (prey, out, - predator->rlw.running_len,0 ); -ewah_add_empty_words (out,0 , - predator->rlw.running_len - index); -rlwit_discard_first_words (predator, - predator->rlw.running_len); - } - } - - literals =min_size ( - rlw_i.rlw.literal_words, - rlw_j.rlw.literal_words); - -if (literals) { -size_t k; - -for (k =0 ; k < literals; ++k) { -ewah_add (out, - rlw_i.buffer[rlw_i.literal_word_start + k] | - rlw_j.buffer[rlw_j.literal_word_start + k] - ); - } - -rlwit_discard_first_words (&rlw_i, literals); -rlwit_discard_first_words (&rlw_j, literals); - } - } - -if (rlwit_word_size (&rlw_i) >0 ) -rlwit_discharge (&rlw_i, out, ~0 ,0 ); -else -rlwit_discharge (&rlw_j, out, ~0 ,0 ); - - out->bit_size =max_size (ewah_i->bit_size, ewah_j->bit_size); -} - -#define BITMAP_POOL_MAX 16static struct ewah_bitmap *bitmap_pool[BITMAP_POOL_MAX ];static size_t bitmap_pool_size;
ewah/ewok.h +0 -5
@@ -157,11 +157,6 @@ void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent);*/ int ewah_iterator_next (eword_t *next,struct ewah_iterator *it); -void ewah_or ( -struct ewah_bitmap *ewah_i, -struct ewah_bitmap *ewah_j, -struct ewah_bitmap *out); - void ewah_xor( struct ewah_bitmap *ewah_i, struct ewah_bitmap *ewah_j,
Signature · 1 line
2.18.0.rc1
PATCH 7/8 ewah_io: delete unused 'ewah_serialize()'
In reply to Derrick Stolee--- ewah/ewah_io.c | 10 ---------- ewah/ewok.h | 1 - 2 files changed, 11 deletions(-)
ewah/ewah_io.c +0 -10
@@ -100,16 +100,6 @@ int ewah_serialize_to(struct ewah_bitmap *self,return (3 *4 ) + (self->buffer_size *8 ); } -static int write_helper (void *fd,const void *buf,size_t len) -{ -return write ((intptr_t )fd, buf, len); -} - -int ewah_serialize (struct ewah_bitmap *self,int fd) -{ -return ewah_serialize_to (self, write_helper, (void *)(intptr_t )fd); -} -static int write_strbuf (void *user_data,const void *data,size_t len) {struct strbuf *sb = user_data;
ewah/ewok.h +0 -1
@@ -86,7 +86,6 @@ void ewah_free(struct ewah_bitmap *self);int ewah_serialize_to (struct ewah_bitmap *self,int (*write_fun)(void *out,const void *buf,size_t len),void *out); -int ewah_serialize (struct ewah_bitmap *self,int fd);int ewah_serialize_native (struct ewah_bitmap *self,int fd);int ewah_serialize_strbuf (struct ewah_bitmap *self,struct strbuf *);
Signature · 1 line
2.18.0.rc1
PATCH 8/8 ewah_io: delete unused 'ewah_serialize_native()'
In reply to Derrick Stolee--- ewah/ewah_io.c | 26 -------------------------- ewah/ewok.h | 1 - 2 files changed, 27 deletions(-)
ewah/ewah_io.c +0 -26
@@ -20,32 +20,6 @@#include "ewok.h" #include "strbuf.h" -int ewah_serialize_native (struct ewah_bitmap *self,int fd) -{ -uint32_t write32; -size_t to_write = self->buffer_size *8 ; - -/* 32 bit -- bit size for the map */ - write32 = (uint32_t )self->bit_size; -if (write (fd, &write32,4 ) !=4 ) -return -1 ; - -/** 32 bit -- number of compressed 64-bit words */ - write32 = (uint32_t )self->buffer_size; -if (write (fd, &write32,4 ) !=4 ) -return -1 ; - -if (write (fd, self->buffer, to_write) != to_write) -return -1 ; - -/** 32 bit -- position for the RLW */ - write32 = self->rlw - self->buffer; -if (write (fd, &write32,4 ) !=4 ) -return -1 ; - -return (3 *4 ) + to_write; -} -int ewah_serialize_to (struct ewah_bitmap *self,int (*write_fun)(void *,const void *,size_t ),void *data)
ewah/ewok.h +0 -1
@@ -86,7 +86,6 @@ void ewah_free(struct ewah_bitmap *self);int ewah_serialize_to (struct ewah_bitmap *self,int (*write_fun)(void *out,const void *buf,size_t len),void *out); -int ewah_serialize_native (struct ewah_bitmap *self,int fd);int ewah_serialize_strbuf (struct ewah_bitmap *self,struct strbuf *);int ewah_deserialize (struct ewah_bitmap *self,int fd);
Signature · 1 line
2.18.0.rc1
Re: [PATCH 8/8] ewah_io: delete unused 'ewah_serialize_native()'
Quoted 5 lines · Derrick Stolee
Signed-off-by Derrick Stolee <[email protected]>--- ewah/ewah_io.c | 26 -------------------------- ewah/ewok.h | 1 - 2 files changed, 27 deletions(-)
This duplicates Jeff's patch #3.
ATB,
Ramsay Jones
Re: [PATCH 8/8] ewah_io: delete unused 'ewah_serialize_native()'
Quoted 8 lines · Ramsay Jones
Quoted 5 lines · Derrick Stolee
Signed-off-by Derrick Stolee <[email protected]>--- ewah/ewah_io.c | 26 -------------------------- ewah/ewok.h | 1 - 2 files changed, 27 deletions(-)This duplicates Jeff's patch #3.
Thanks. I got a bit hasty as I was working from 'maint' and didn't double-check.
-Stolee
Re: [PATCH 0/8] Delete unused methods in EWAH bitmap
In reply to Derrick StoleeQuoted 25 lines · Derrick Stolee
The EWAH bitmap code includes several logical operations that are important for a general-purpose bitmap library. However, Git only uses the XOR operation for storing deltas between reachability bitmaps. This means that we can delete the following unused methods:
*
ewah_and()
*ewah_and_not()
*ewah_not()
*ewah_or()
*ewah_serialize()
*ewah_serialize_native()We can also delete the unused methods
bitmap_clear()andbitmap_each_bit().Derrick Stolee (8):
ewah/bitmap.c: delete unused 'bitmap_clear()'ewah/bitmap.c: delete unused 'bitmap_each_bit()'
ewah_bitmap: delete unused 'ewah_and()'
ewah_bitmap: delete unused 'ewah_and_not()'
ewah_bitmap: delete unused 'ewah_not()'
ewah_bitmap: delete unused 'ewah_or()'
ewah_io: delete unused 'ewah_serialize()'
ewah_io: delete unused 'ewah_serialize_native()'
Quoted 8 lines
ewah/bitmap.c | 32 ------- ewah/ewah_bitmap.c | 229 --------------------------------------------- ewah/ewah_io.c | 36 ------- ewah/ewok.h | 24 ----- 4 files changed, 321 deletions(-)base-commit:
fc54c1af3ec09bab8b8ea09768c2da4069b7f53e
Responders to this thread beware: I accidentally added an extra letter in Peff's email address, so be careful with reply-all.
Sorry!
-Stolee
v2 cover Delete unused methods in EWAH bitmap
In reply to Derrick StoleeThe EWAH bitmap code includes several logical operations that are important for a general-purpose bitmap library. However, Git only uses the XOR operation for storing deltas between reachability bitmaps. This means that we can delete the following unused methods:
* ewah_and()
* ewah_and_not()
* ewah_not()
* ewah_or()
* ewah_serialize()
We can also delete the unused methods bitmap_clear() and bitmap_each_bit().
Derrick Stolee (7):
ewah/bitmap.c: delete unused 'bitmap_clear()' ewah/bitmap.c: delete unused 'bitmap_each_bit()'
ewah_bitmap: delete unused 'ewah_and()'
ewah_bitmap: delete unused 'ewah_and_not()'
ewah_bitmap: delete unused 'ewah_not()'
ewah_bitmap: delete unused 'ewah_or()'
ewah_io: delete unused 'ewah_serialize()'
ewah/bitmap.c | 32 ------- ewah/ewah_bitmap.c | 229 --------------------------------------------- ewah/ewah_io.c | 10 -- ewah/ewok.h | 25 ----- 4 files changed, 296 deletions(-)
base-commit: fc54c1af3ec09bab8b8ea09768c2da4069b7f53e
Signature · 1 line
2.18.0.rc1
PATCH v2 1/7 ewah/bitmap.c: delete unused 'bitmap_clear()'
--- ewah/bitmap.c | 8 -------- ewah/ewok.h | 1 - 2 files changed, 9 deletions(-)
ewah/bitmap.c +0 -8
@@ -45,14 +45,6 @@ void bitmap_set(struct bitmap *self, size_t pos) self->words[block] |=EWAH_MASK (pos); } -void bitmap_clear (struct bitmap *self,size_t pos) -{ -size_t block =EWAH_BLOCK (pos); - -if (block < self->word_alloc) - self->words[block] &= ~EWAH_MASK (pos); -} -int bitmap_get (struct bitmap *self,size_t pos) {size_t block =EWAH_BLOCK (pos);
ewah/ewok.h +0 -1
@@ -204,7 +204,6 @@ struct bitmap {struct bitmap *bitmap_new (void );void bitmap_set (struct bitmap *self,size_t pos); -void bitmap_clear (struct bitmap *self,size_t pos);int bitmap_get (struct bitmap *self,size_t pos);void bitmap_reset (struct bitmap *self);void bitmap_free (struct bitmap *self);
Signature · 1 line
2.18.0.rc1
PATCH v2 2/7 ewah/bitmap.c: delete unused 'bitmap_each_bit()'
In reply to Derrick Stolee--- ewah/bitmap.c | 24 ------------------------ ewah/ewok.h | 1 - 2 files changed, 25 deletions(-)
ewah/bitmap.c +0 -24
@@ -129,30 +129,6 @@ void bitmap_or_ewah(struct bitmap *self, struct ewah_bitmap *other) self->words[i++] |= word; } -void bitmap_each_bit (struct bitmap *self,ewah_callback callback,void *data) -{ -size_t pos =0 , i; - -for (i =0 ; i < self->word_alloc; ++i) { -eword_t word = self->words[i]; -uint32_t offset; - -if (word == (eword_t )~0 ) { -for (offset =0 ; offset <BITS_IN_EWORD ; ++offset) -callback (pos++, data); - }else { -for (offset =0 ; offset <BITS_IN_EWORD ; ++offset) { -if ((word >> offset) ==0 ) -break ; - - offset +=ewah_bit_ctz64 (word >> offset); -callback (pos + offset, data); - } - pos +=BITS_IN_EWORD ; - } - } -} -size_t bitmap_popcount (struct bitmap *self) {size_t i, count =0 ;
ewah/ewok.h +0 -1
@@ -217,7 +217,6 @@ void bitmap_and_not(struct bitmap *self, struct bitmap *other);void bitmap_or_ewah (struct bitmap *self,struct ewah_bitmap *other);void bitmap_or (struct bitmap *self,const struct bitmap *other); -void bitmap_each_bit (struct bitmap *self,ewah_callback callback,void *data);size_t bitmap_popcount (struct bitmap *self);#endif
Signature · 1 line
2.18.0.rc1
PATCH v2 3/7 ewah_bitmap: delete unused 'ewah_and()'
In reply to Derrick Stolee--- ewah/ewah_bitmap.c | 68 ---------------------------------------------- ewah/ewok.h | 5 ---- 2 files changed, 73 deletions(-)
ewah/ewah_bitmap.c +0 -68
@@ -459,74 +459,6 @@ void ewah_xor( out->bit_size =max_size (ewah_i->bit_size, ewah_j->bit_size); } -void ewah_and ( -struct ewah_bitmap *ewah_i, -struct ewah_bitmap *ewah_j, -struct ewah_bitmap *out) -{ -struct rlw_iterator rlw_i; -struct rlw_iterator rlw_j; -size_t literals; - -rlwit_init (&rlw_i, ewah_i); -rlwit_init (&rlw_j, ewah_j); - -while (rlwit_word_size (&rlw_i) >0 &&rlwit_word_size (&rlw_j) >0 ) { -while (rlw_i.rlw.running_len >0 || rlw_j.rlw.running_len >0 ) { -struct rlw_iterator *prey, *predator; - -if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) { - prey = &rlw_i; - predator = &rlw_j; - }else { - prey = &rlw_j; - predator = &rlw_i; - } - -if (predator->rlw.running_bit ==0 ) { -ewah_add_empty_words (out,0 , - predator->rlw.running_len); -rlwit_discard_first_words (prey, - predator->rlw.running_len); -rlwit_discard_first_words (predator, - predator->rlw.running_len); - }else { -size_t index =rlwit_discharge (prey, out, - predator->rlw.running_len,0 ); -ewah_add_empty_words (out,0 , - predator->rlw.running_len - index); -rlwit_discard_first_words (predator, - predator->rlw.running_len); - } - } - - literals =min_size ( - rlw_i.rlw.literal_words, - rlw_j.rlw.literal_words); - -if (literals) { -size_t k; - -for (k =0 ; k < literals; ++k) { -ewah_add (out, - rlw_i.buffer[rlw_i.literal_word_start + k] & - rlw_j.buffer[rlw_j.literal_word_start + k] - ); - } - -rlwit_discard_first_words (&rlw_i, literals); -rlwit_discard_first_words (&rlw_j, literals); - } - } - -if (rlwit_word_size (&rlw_i) >0 ) -rlwit_discharge_empty (&rlw_i, out); -else -rlwit_discharge_empty (&rlw_j, out); - - out->bit_size =max_size (ewah_i->bit_size, ewah_j->bit_size); -} - void ewah_and_not( struct ewah_bitmap *ewah_i, struct ewah_bitmap *ewah_j,
ewah/ewok.h +0 -5
@@ -179,11 +179,6 @@ void ewah_xor(struct ewah_bitmap *ewah_j, struct ewah_bitmap *out); -void ewah_and ( -struct ewah_bitmap *ewah_i, -struct ewah_bitmap *ewah_j, -struct ewah_bitmap *out); -/** * Direct word access */
Signature · 1 line
2.18.0.rc1
PATCH v2 4/7 ewah_bitmap: delete unused 'ewah_and_not()'
In reply to Derrick Stolee--- ewah/ewah_bitmap.c | 73 ---------------------------------------------- ewah/ewok.h | 5 ---- 2 files changed, 78 deletions(-)
ewah/ewah_bitmap.c +0 -73
@@ -459,79 +459,6 @@ void ewah_xor( out->bit_size =max_size (ewah_i->bit_size, ewah_j->bit_size); } -void ewah_and_not ( -struct ewah_bitmap *ewah_i, -struct ewah_bitmap *ewah_j, -struct ewah_bitmap *out) -{ -struct rlw_iterator rlw_i; -struct rlw_iterator rlw_j; -size_t literals; - -rlwit_init (&rlw_i, ewah_i); -rlwit_init (&rlw_j, ewah_j); - -while (rlwit_word_size (&rlw_i) >0 &&rlwit_word_size (&rlw_j) >0 ) { -while (rlw_i.rlw.running_len >0 || rlw_j.rlw.running_len >0 ) { -struct rlw_iterator *prey, *predator; - -if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) { - prey = &rlw_i; - predator = &rlw_j; - }else { - prey = &rlw_j; - predator = &rlw_i; - } - -if ((predator->rlw.running_bit && prey == &rlw_i) || - (!predator->rlw.running_bit && prey != &rlw_i)) { -ewah_add_empty_words (out,0 , - predator->rlw.running_len); -rlwit_discard_first_words (prey, - predator->rlw.running_len); -rlwit_discard_first_words (predator, - predator->rlw.running_len); - }else { -size_t index; -int negate_words; - - negate_words = (&rlw_i != prey); - index =rlwit_discharge (prey, out, - predator->rlw.running_len, negate_words); -ewah_add_empty_words (out, negate_words, - predator->rlw.running_len - index); -rlwit_discard_first_words (predator, - predator->rlw.running_len); - } - } - - literals =min_size ( - rlw_i.rlw.literal_words, - rlw_j.rlw.literal_words); - -if (literals) { -size_t k; - -for (k =0 ; k < literals; ++k) { -ewah_add (out, - rlw_i.buffer[rlw_i.literal_word_start + k] & - ~(rlw_j.buffer[rlw_j.literal_word_start + k]) - ); - } - -rlwit_discard_first_words (&rlw_i, literals); -rlwit_discard_first_words (&rlw_j, literals); - } - } - -if (rlwit_word_size (&rlw_i) >0 ) -rlwit_discharge (&rlw_i, out, ~0 ,0 ); -else -rlwit_discharge_empty (&rlw_j, out); - - out->bit_size =max_size (ewah_i->bit_size, ewah_j->bit_size); -} - void ewah_or( struct ewah_bitmap *ewah_i, struct ewah_bitmap *ewah_j,
ewah/ewok.h +0 -5
@@ -169,11 +169,6 @@ void ewah_or(struct ewah_bitmap *ewah_j, struct ewah_bitmap *out); -void ewah_and_not ( -struct ewah_bitmap *ewah_i, -struct ewah_bitmap *ewah_j, -struct ewah_bitmap *out); - void ewah_xor( struct ewah_bitmap *ewah_i, struct ewah_bitmap *ewah_j,
Signature · 1 line
2.18.0.rc1
PATCH v2 5/7 ewah_bitmap: delete unused 'ewah_not()'
In reply to Derrick Stolee--- ewah/ewah_bitmap.c | 19 ------------------- ewah/ewok.h | 7 ------- 2 files changed, 26 deletions(-)
ewah/ewah_bitmap.c +0 -19
@@ -376,25 +376,6 @@ void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent)read_new_rlw (it); } -void ewah_not (struct ewah_bitmap *self) -{ -size_t pointer =0 ; - -while (pointer < self->buffer_size) { -eword_t *word = &self->buffer[pointer]; -size_t literals, k; - -rlw_xor_run_bit (word); - ++pointer; - - literals =rlw_get_literal_words (word); -for (k =0 ; k < literals; ++k) { - self->buffer[pointer] = ~self->buffer[pointer]; - ++pointer; - } - } -} - void ewah_xor( struct ewah_bitmap *ewah_i, struct ewah_bitmap *ewah_j,
ewah/ewok.h +0 -7
@@ -95,13 +95,6 @@ int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len);uint32_t ewah_checksum (struct ewah_bitmap *self); -/** -* Logical not (bitwise negation) in-place on the bitmap -* -* This operation is linear time based on the size of the bitmap. -*/ -void ewah_not (struct ewah_bitmap *self); -/** * Call the given callback with the position of every single bit * that has been set on the bitmap.
Signature · 1 line
2.18.0.rc1
PATCH v2 6/7 ewah_bitmap: delete unused 'ewah_or()'
In reply to Derrick Stolee--- ewah/ewah_bitmap.c | 69 ---------------------------------------------- ewah/ewok.h | 5 ---- 2 files changed, 74 deletions(-)
ewah/ewah_bitmap.c +0 -69
@@ -440,75 +440,6 @@ void ewah_xor( out->bit_size =max_size (ewah_i->bit_size, ewah_j->bit_size); } -void ewah_or ( -struct ewah_bitmap *ewah_i, -struct ewah_bitmap *ewah_j, -struct ewah_bitmap *out) -{ -struct rlw_iterator rlw_i; -struct rlw_iterator rlw_j; -size_t literals; - -rlwit_init (&rlw_i, ewah_i); -rlwit_init (&rlw_j, ewah_j); - -while (rlwit_word_size (&rlw_i) >0 &&rlwit_word_size (&rlw_j) >0 ) { -while (rlw_i.rlw.running_len >0 || rlw_j.rlw.running_len >0 ) { -struct rlw_iterator *prey, *predator; - -if (rlw_i.rlw.running_len < rlw_j.rlw.running_len) { - prey = &rlw_i; - predator = &rlw_j; - }else { - prey = &rlw_j; - predator = &rlw_i; - } - -if (predator->rlw.running_bit) { -ewah_add_empty_words (out,0 , - predator->rlw.running_len); -rlwit_discard_first_words (prey, - predator->rlw.running_len); -rlwit_discard_first_words (predator, - predator->rlw.running_len); - }else { -size_t index =rlwit_discharge (prey, out, - predator->rlw.running_len,0 ); -ewah_add_empty_words (out,0 , - predator->rlw.running_len - index); -rlwit_discard_first_words (predator, - predator->rlw.running_len); - } - } - - literals =min_size ( - rlw_i.rlw.literal_words, - rlw_j.rlw.literal_words); - -if (literals) { -size_t k; - -for (k =0 ; k < literals; ++k) { -ewah_add (out, - rlw_i.buffer[rlw_i.literal_word_start + k] | - rlw_j.buffer[rlw_j.literal_word_start + k] - ); - } - -rlwit_discard_first_words (&rlw_i, literals); -rlwit_discard_first_words (&rlw_j, literals); - } - } - -if (rlwit_word_size (&rlw_i) >0 ) -rlwit_discharge (&rlw_i, out, ~0 ,0 ); -else -rlwit_discharge (&rlw_j, out, ~0 ,0 ); - - out->bit_size =max_size (ewah_i->bit_size, ewah_j->bit_size); -} - -#define BITMAP_POOL_MAX 16static struct ewah_bitmap *bitmap_pool[BITMAP_POOL_MAX ];static size_t bitmap_pool_size;
ewah/ewok.h +0 -5
@@ -157,11 +157,6 @@ void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent);*/ int ewah_iterator_next (eword_t *next,struct ewah_iterator *it); -void ewah_or ( -struct ewah_bitmap *ewah_i, -struct ewah_bitmap *ewah_j, -struct ewah_bitmap *out); - void ewah_xor( struct ewah_bitmap *ewah_i, struct ewah_bitmap *ewah_j,
Signature · 1 line
2.18.0.rc1
PATCH v2 7/7 ewah_io: delete unused 'ewah_serialize()'
In reply to Derrick Stolee--- ewah/ewah_io.c | 10 ---------- ewah/ewok.h | 1 - 2 files changed, 11 deletions(-)
ewah/ewah_io.c +0 -10
@@ -100,16 +100,6 @@ int ewah_serialize_to(struct ewah_bitmap *self,return (3 *4 ) + (self->buffer_size *8 ); } -static int write_helper (void *fd,const void *buf,size_t len) -{ -return write ((intptr_t )fd, buf, len); -} - -int ewah_serialize (struct ewah_bitmap *self,int fd) -{ -return ewah_serialize_to (self, write_helper, (void *)(intptr_t )fd); -} -static int write_strbuf (void *user_data,const void *data,size_t len) {struct strbuf *sb = user_data;
ewah/ewok.h +0 -1
@@ -86,7 +86,6 @@ void ewah_free(struct ewah_bitmap *self);int ewah_serialize_to (struct ewah_bitmap *self,int (*write_fun)(void *out,const void *buf,size_t len),void *out); -int ewah_serialize (struct ewah_bitmap *self,int fd);int ewah_serialize_native (struct ewah_bitmap *self,int fd);int ewah_serialize_strbuf (struct ewah_bitmap *self,struct strbuf *);
Signature · 1 line
2.18.0.rc1
Re: [PATCH v2 0/7] Delete unused methods in EWAH bitmap
In reply to Derrick StoleeQuoted 23 lines · Derrick Stolee
The EWAH bitmap code includes several logical operations that are important for a general-purpose bitmap library. However, Git only uses the XOR operation for storing deltas between reachability bitmaps. This means that we can delete the following unused methods:
*
ewah_and()
*ewah_and_not()
*ewah_not()
*ewah_or()
*ewah_serialize()We can also delete the unused methods
bitmap_clear()andbitmap_each_bit().Derrick Stolee (7):
ewah/bitmap.c: delete unused 'bitmap_clear()'ewah/bitmap.c: delete unused 'bitmap_each_bit()'
ewah_bitmap: delete unused 'ewah_and()'
ewah_bitmap: delete unused 'ewah_and_not()'
ewah_bitmap: delete unused 'ewah_not()'
ewah_bitmap: delete unused 'ewah_or()'
ewah_io: delete unused 'ewah_serialize()'
Quoted 8 lines
ewah/bitmap.c | 32 ------- ewah/ewah_bitmap.c | 229 --------------------------------------------- ewah/ewah_io.c | 10 -- ewah/ewok.h | 25 ----- 4 files changed, 296 deletions(-)base-commit:
fc54c1af3ec09bab8b8ea09768c2da4069b7f53e
Thanks.
ewah_clear() can become file-scope static, and rlwit_discharge_empty() can be eliminated. I do not know if either is worth doing, though.
ewah/ewah_bitmap.c | 20 ++++++++++++-------- ewah/ewah_rlw.c | 8 -------- ewah/ewok.h | 6 ------ ewah/ewok_rlw.h | 1 - 4 files changed, 12 insertions(+), 23 deletions(-)
ewah/ewah_bitmap.c +12 -8
@@ -276,6 +276,18 @@ void ewah_each_bit(struct ewah_bitmap *self, void (*callback)(size_t, void*), vo } } +/** +* Clear all the bits in the bitmap. Does not free or resize +* memory. +*/ +static void ewah_clear (struct ewah_bitmap *self) +{ + self->buffer_size =1 ; + self->buffer[0 ] =0 ; + self->bit_size =0 ; + self->rlw = self->buffer; +} +struct ewah_bitmap *ewah_new (void ) {struct ewah_bitmap *self;
@@ -288,14 +300,6 @@ struct ewah_bitmap *ewah_new(void)return self; } -void ewah_clear (struct ewah_bitmap *self) -{ - self->buffer_size =1 ; - self->buffer[0 ] =0 ; - self->bit_size =0 ; - self->rlw = self->buffer; -} -void ewah_free (struct ewah_bitmap *self) {if (!self)
ewah/ewah_rlw.c +0 -8
@@ -104,11 +104,3 @@ size_t rlwit_discharge(return index; } - -void rlwit_discharge_empty (struct rlw_iterator *it,struct ewah_bitmap *out) -{ -while (rlwit_word_size (it) >0 ) { -ewah_add_empty_words (out,0 ,rlwit_word_size (it)); -rlwit_discard_first_words (it,rlwit_word_size (it)); - } -}
ewah/ewok.h +0 -6
@@ -72,12 +72,6 @@ void ewah_pool_free(struct ewah_bitmap *self);*/ struct ewah_bitmap *ewah_new (void ); -/** -* Clear all the bits in the bitmap. Does not free or resize -* memory. -*/ -void ewah_clear (struct ewah_bitmap *self); -/** * Free all the memory of the bitmap */
ewah/ewok_rlw.h +0 -1
@@ -98,7 +98,6 @@ void rlwit_init(struct rlw_iterator *it, struct ewah_bitmap *bitmap);void rlwit_discard_first_words (struct rlw_iterator *it,size_t x);size_t rlwit_discharge (struct rlw_iterator *it,struct ewah_bitmap *out,size_t max,int negate); -void rlwit_discharge_empty (struct rlw_iterator *it,struct ewah_bitmap *out);static inline size_t rlwit_word_size (struct rlw_iterator *it) {
Re: [PATCH v2 0/7] Delete unused methods in EWAH bitmap
Quoted 32 lines · Junio C Hamano
Quoted 30 lines · Derrick Stolee
The EWAH bitmap code includes several logical operations that are important for a general-purpose bitmap library. However, Git only uses the XOR operation for storing deltas between reachability bitmaps. This means that we can delete the following unused methods:
*
ewah_and()
*ewah_and_not()
*ewah_not()
*ewah_or()
*ewah_serialize()We can also delete the unused methods
bitmap_clear()andbitmap_each_bit().Derrick Stolee (7):
ewah/bitmap.c: delete unused 'bitmap_clear()'ewah/bitmap.c: delete unused 'bitmap_each_bit()'
ewah_bitmap: delete unused 'ewah_and()'
ewah_bitmap: delete unused 'ewah_and_not()'
ewah_bitmap: delete unused 'ewah_not()'
ewah_bitmap: delete unused 'ewah_or()'
ewah_io: delete unused 'ewah_serialize()'ewah/bitmap.c | 32 ------- ewah/ewah_bitmap.c | 229 --------------------------------------------- ewah/ewah_io.c | 10 -- ewah/ewok.h | 25 ----- 4 files changed, 296 deletions(-)
Quoted 6 lines
Quoted 1 line
base-commit:
fc54c1af3ec09bab8b8ea09768c2da4069b7f53eThanks.
ewah_clear()can become file-scope static, andrlwit_discharge_empty()can be eliminated. I do not know if either is worth doing, though.
With Peff's patches, this is true. When I applied your diff to my patch alone we could not do that.
If you want to create a commit with the below, I'm happy to add my "Reviewed-by: Derrick Stolee <[email protected]>"
Good team effort today!
Quoted 92 lines
ewah/ewah_bitmap.c | 20 ++++++++++++-------- ewah/ewah_rlw.c | 8 -------- ewah/ewok.h | 6 ------ ewah/ewok_rlw.h | 1 - 4 files changed, 12 insertions(+), 23 deletions(-)ewah/ewah_bitmap.c +12
-8@@ -276,6 +276,18 @@ void ewah_each_bit(struct ewah_bitmap *self, void (*callback)(size_t, void*), vo } } +/** +* Clear all the bits in the bitmap. Does not free or resize +* memory. +*/ +static void ewah_clear (struct ewah_bitmap *self) +{ + self->buffer_size =1 ; + self->buffer[0 ] =0 ; + self->bit_size =0 ; + self->rlw = self->buffer; +} +struct ewah_bitmap *ewah_new (void ) {struct ewah_bitmap *self;@@ -288,14 +300,6 @@ struct ewah_bitmap *ewah_new(void)return self; } -void ewah_clear (struct ewah_bitmap *self) -{ - self->buffer_size =1 ; - self->buffer[0 ] =0 ; - self->bit_size =0 ; - self->rlw = self->buffer; -} -void ewah_free (struct ewah_bitmap *self) {if (!self)ewah/ewah_rlw.c +0
-8@@ -104,11 +104,3 @@ size_t rlwit_discharge(return index; } - -void rlwit_discharge_empty (struct rlw_iterator *it,struct ewah_bitmap *out) -{ -while (rlwit_word_size (it) >0 ) { -ewah_add_empty_words (out,0 ,rlwit_word_size (it)); -rlwit_discard_first_words (it,rlwit_word_size (it)); - } -}ewah/ewok.h +0
-6@@ -72,12 +72,6 @@ void ewah_pool_free(struct ewah_bitmap *self);*/ struct ewah_bitmap *ewah_new (void ); -/** -* Clear all the bits in the bitmap. Does not free or resize -* memory. -*/ -void ewah_clear (struct ewah_bitmap *self); -/** * Free all the memory of the bitmap */ ewah/ewok_rlw.h +0
-1@@ -98,7 +98,6 @@ void rlwit_init(struct rlw_iterator *it, struct ewah_bitmap *bitmap);void rlwit_discard_first_words (struct rlw_iterator *it,size_t x);size_t rlwit_discharge (struct rlw_iterator *it,struct ewah_bitmap *out,size_t max,int negate); -void rlwit_discharge_empty (struct rlw_iterator *it,struct ewah_bitmap *out);static inline size_t rlwit_word_size (struct rlw_iterator *it) {
Re: [PATCH v2 0/7] Delete unused methods in EWAH bitmap
Quoted 6 lines · Derrick Stolee
Quoted 3 lines
ewah_clear()can become file-scope static, andrlwit_discharge_empty()can be eliminated. I do not know if either is worth doing, though.With Peff's patches, this is true. When I applied your diff to my patch alone we could not do that.
Yeah, as I organized the patches on two topics in this order:
jk/ewah-bounds-check (build on 'maint')
Peff's 1/3
Peff's 4/3ds/ewah-cleanup (build on top of the above)
7 patches in this series
Peff's 2/3
Peff's 3/3at the end, these two changes become possible. Again, I am not sure if these are worth doing, so I'll leave it out of these two series, at least for now.
This is a tangent, but I too felt that roaring paper quite a pleasant read ;-)
Re: [PATCH v2 0/7] Delete unused methods in EWAH bitmap
Quoted 11 lines · Junio C Hamano
Quoted 6 lines · Derrick Stolee
Quoted 3 lines
ewah_clear()can become file-scope static, andrlwit_discharge_empty()can be eliminated. I do not know if either is worth doing, though.With Peff's patches, this is true. When I applied your diff to my patch alone we could not do that.
Yeah, as I organized the patches on two topics in this order:
Quoted 8 lines
jk/ewah-bounds-check (build on 'maint')
Peff's 1/3 Peff's 4/3ds/ewah-cleanup (build on top of the above)
7 patches in this series Peff's 2/3 Peff's 3/3
Thanks, I wasn't sure if I should resend mine on top, but it looks like you've got it all organized already.
Quoted 3 lines
at the end, these two changes become possible. Again, I am not sure if these are worth doing, so I'll leave it out of these two series, at least for now.
IMHO the extra cleanups you showed are worth doing.
-Peff
Re: [PATCH 3/3] ewah: drop ewah_serialize_native function
In reply to Ramsay JonesQuoted 9 lines · Ramsay Jones
Quoted 5 lines · Jeff King
We don't call this function, and never have. The on-disk bitmap format uses network-byte-order integers, meaning that we cannot use the native-byte-order format written here.
Let's drop it in the name of simplicity.
Hmm, if you are in the mood to drop ewah dead code, how about:
Quoted 9 lines
ewah/bitmap.o-bitmap_clear
ewah/bitmap.o-bitmap_each_bitewah/ewah_bitmap.o - ewah_and ewah/ewah_bitmap.o - ewah_and_not ewah/ewah_bitmap.o - ewah_not ewah/ewah_bitmap.o - ewah_or... in addition to these *(de)serialize* functions. ;-)
Normally, I would say we should keep this folder as close to the "original" [1] as possible, so we could more easily take improvements to that library. However, it appears that code is not being updated. Perhaps this is in favor of other EWAH libraries [2] or other compressed bitmap formats [3].
For that reason, I agree we should clean this up. We shouldn't block Peff's patch for that reason. I'll send a patch that deletes these methods.
Thanks,
-Stolee:
[1] https://github.com/vmg/libewok
Re: [PATCH 3/3] ewah: drop ewah_serialize_native function
Quoted 9 lines · Derrick Stolee
Quoted 9 lines
Hmm, if you are in the mood to drop ewah dead code, how about:
ewah/bitmap.o-bitmap_clear
ewah/bitmap.o-bitmap_each_bitewah/ewah_bitmap.o - ewah_and ewah/ewah_bitmap.o - ewah_and_not ewah/ewah_bitmap.o - ewah_not ewah/ewah_bitmap.o - ewah_or
Quoted 7 lines
Quoted 2 lines
... in addition to these *(de)serialize* functions. ;-)
Normally, I would say we should keep this folder as close to the "original"
[1] as possible, so we could more easily take improvements to that library. However, it appears that code is not being updated. Perhaps this is in favor of other EWAH libraries [2] or other compressed bitmap formats [3].
The ewok library was written specifically for Git, as a port of Daniel Lemire's original EWAH work, since at the time there was no pure-C implementation of EWAH (that might even still be the case -- I don't know).
We pulled it out into a separate library with the thought that maybe other people would find it useful. But I don't specifically know of any other users of the library, nor do I think Vicent has spent any time on it since writing it for Git (I know I haven't).
So yeah, I think it is fine to just consider this "our" code and chop it up as we see fit (and you can see we've already tweaked it for things like allocating consistently with our other code).
One thing that gave me pause on ripping out more code is that I have some bitmap-related patches on my send-to-upstream list, and I wasn't sure if they used any of this code. But I checked against your patches, and no, this can all go (which makes sense -- my patches are about using .bitmap files in more places, so they build at a higher level).
So your patches look good to me, modulo the declarations that Ramsay noticed should be removed, too.
-Peff
Re: [PATCH 3/3] ewah: drop ewah_serialize_native function
Quoted 8 lines · Jeff King
One thing that gave me pause on ripping out more code is that I have some bitmap-related patches on my send-to-upstream list, and I wasn't sure if they used any of this code. But I checked against your patches, and no, this can all go (which makes sense -- my patches are about using .bitmap files in more places, so they build at a higher level).
So your patches look good to me, modulo the declarations that Ramsay noticed should be removed, too.
I'll queue your 1/3 and 4/3 (without 2&3/3) for now and let Derrick and you handle the removal of unused stuff separately on top, so that the fix-proper can graduate earlier than the rest.
Thanks.
Re: [PATCH 3/3] ewah: drop ewah_serialize_native function
Quoted 8 lines · Junio C Hamano
Quoted 6 lines · Jeff King
One thing that gave me pause on ripping out more code is that I have some bitmap-related patches on my send-to-upstream list, and I wasn't sure if they used any of this code. But I checked against your patches, and no, this can all go (which makes sense -- my patches are about using .bitmap files in more places, so they build at a higher level).
Quoted 6 lines
Quoted 2 lines
So your patches look good to me, modulo the declarations that Ramsay noticed should be removed, too.
I'll queue your 1/3 and 4/3 (without 2&3/3) for now and let Derrick and you handle the removal of unused stuff separately on top, so that the fix-proper can graduate earlier than the rest.
Thanks, that sounds good. 2/3 is sort-of-related in that it has an integer overflow bug like the one in 1/3. But the fact that it is not used at all makes it very low priority. ;)
-Peff
[PATCH 4/3] ewah: adjust callers of ewah_read_mmap()
In reply to Jeff KingQuoted 10 lines · Jeff King
Yep. We also fail to check if we even have enough bytes to read the
buffer_sizein the first place.Here are some patches. The first one fixes the problem you found. The second one drops some dead code that has a related problem. And the third just drops some dead code that I noticed in the same file. :)
[1/3]:
ewah_read_mmap: bounds-check mmap reads [2/3]: ewah: dropewah_deserializefunction [3/3]: ewah: dropewah_serialize_nativefunction
Actually, we'd want this one on top. Arguably it could be squashed into patch 1.
-- >8 --
Subject: ewah: adjust callers of ewah_read_mmap()
The return value of ewah_read_mmap() is now an ssize_t, since we could (in theory) process up to 32GB of data. This would never happen in practice, but a corrupt or malicious .bitmap or index file could convince us to do so.
Let's make sure that we don't stuff the value into an int, which would cause us to incorrectly move our pointer forward. We'd always move too little, since negative values are used for reporting errors. So the worst case is just that we end up reporting a corrupt file, not an out-of-bounds read.
--- dir.c | 3 ++- pack-bitmap.c | 2 +- 2 files changed, 3 insertions(+), 2 deletions(-)
dir.c +2 -1
@@ -2725,7 +2725,8 @@ struct untracked_cache *read_untracked_extension(const void *data, unsigned longstruct read_data rd;const unsigned char *next = data, *end = (const unsigned char *)data + sz;const char *ident; -int ident_len, len; +int ident_len; +ssize_t len;const char *exclude_per_dir;if (sz <=1 || end[-1 ] !='\0' )
pack-bitmap.c +1 -1
@@ -125,7 +125,7 @@ static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index) {struct ewah_bitmap *b =ewah_pool_new (); -int bitmap_size =ewah_read_mmap (b, +ssize_t bitmap_size =ewah_read_mmap (b, index->map + index->map_pos, index->map_size - index->map_pos);
Signature · 1 line
2.18.0.rc2.534.g53d976aeb8
Re: [PATCH 4/3] ewah: adjust callers of ewah_read_mmap()
Quoted 4 lines · Jeff King
The return value of
ewah_read_mmap()is now anssize_t, since we could (in theory) process up to 32GB of data. This would never happen in practice, but a corrupt or malicious .bitmap or index file could convince us to do so.
Aside: Why a 32GB limit? Usually I see 32-bit issues limiting by 2 (signed) or 4 GB (unsigned). Is there something specifically in the bitmap format that stops at this size?
Thanks,
-Stolee
Re: [PATCH 4/3] ewah: adjust callers of ewah_read_mmap()
Quoted 9 lines · Derrick Stolee
Quoted 4 lines · Jeff King
The return value of
ewah_read_mmap()is now anssize_t, since we could (in theory) process up to 32GB of data. This would never happen in practice, but a corrupt or malicious .bitmap or index file could convince us to do so.Aside: Why a 32GB limit? Usually I see 32-bit issues limiting by 2 (signed) or 4 GB (unsigned). Is there something specifically in the bitmap format that stops at this size?
The proposed log message for 1/3 has this bit
- check the size for integer overflow (this should be impossible on 64-bit, as the size is given as a 32-bit count of 8-byte words, but is possible on a 32-bit system)
4 Giga 8-byte words makes 32 Giga bytes, I'd guess.
Re: [PATCH 4/3] ewah: adjust callers of ewah_read_mmap()
Quoted 12 lines · Junio C Hamano
Quoted 9 lines · Derrick Stolee
Quoted 4 lines · Jeff King
The return value of
ewah_read_mmap()is now anssize_t, since we could (in theory) process up to 32GB of data. This would never happen in practice, but a corrupt or malicious .bitmap or index file could convince us to do so.Aside: Why a 32GB limit? Usually I see 32-bit issues limiting by 2 (signed) or 4 GB (unsigned). Is there something specifically in the bitmap format that stops at this size?
Quoted 8 lines
The proposed log message for 1/3 has this bit
- check the size for integer overflow (this should be impossible on 64-bit, as the size is given as a 32-bit count of 8-byte words, but is possible on a 32-bit system)
4 Giga 8-byte words makes 32 Giga bytes, I'd guess.
Yes, exactly. It's definitely an odd size. I think using the same varints we use in the packfile would be more efficient (and they're already variable-length records), though we tend to have few enough of these that it probably doesn't matter.
I think a more useful change for the bitmap format would be some kind of index. IIRC, right now readers have to linearly scan the whole file in order to use a single bitmap.
With Stolee's commit-metadata files, we could potentially move to storing reachability bitmaps as a data element there. But there are two complications:
- the bitmaps themselves are dependent on having an ordered list of objects (one per bit) to talk about. And that's why they're integrated with packfiles, since that provides a constrained universe with a set ordering.
- the existing storage isn't entirely independent between bitmaps. Some of them are basically "deltas" off of nearby bitmaps.
-Peff
Re: [PATCH 4/3] ewah: adjust callers of ewah_read_mmap()
Quoted 33 lines · Jeff King
Quoted 10 lines · Junio C Hamano
Quoted 8 lines · Derrick Stolee
Quoted 4 lines · Jeff King
The return value of
ewah_read_mmap()is now anssize_t, since we could (in theory) process up to 32GB of data. This would never happen in practice, but a corrupt or malicious .bitmap or index file could convince us to do so.Aside: Why a 32GB limit? Usually I see 32-bit issues limiting by 2 (signed) or 4 GB (unsigned). Is there something specifically in the bitmap format that stops at this size?
Quoted 8 lines
The proposed log message for 1/3 has this bit
- check the size for integer overflow (this should be impossible on 64-bit, as the size is given as a 32-bit count of 8-byte words, but is possible on a 32-bit system)
4 Giga 8-byte words makes 32 Giga bytes, I'd guess.
Yes, exactly. It's definitely an odd size. I think using the same varints we use in the packfile would be more efficient (and they're already variable-length records), though we tend to have few enough of these that it probably doesn't matter.
I think a more useful change for the bitmap format would be some kind of index. IIRC, right now readers have to linearly scan the whole file in order to use a single bitmap.
With Stolee's commit-metadata files, we could potentially move to storing reachability bitmaps as a data element there. But there are two complications:
Quoted 7 lines
- the bitmaps themselves are dependent on having an ordered list of objects (one per bit) to talk about. And that's why they're integrated with packfiles, since that provides a constrained universe with a set ordering.
- the existing storage isn't entirely independent between bitmaps. Some of them are basically "deltas" off of nearby bitmaps.
The VSTS reachability bitmap is different from the Git bitmap in a few ways.
1. It uses Roaring+Run bitmaps [1] instead of EWAH bitmap. This format is simpler (in my opinion) in several ways, especially in how it splits the bitmap into 16-bit address ranges and compresses each on its own. This makes set containment queries much faster, as we can navigate directly to the region that is important (and then binary search if that chunk is an "array" or "run" chunk). I say this is simpler because I can explain the entire compression format to you in five minutes and a whiteboard. The paper [2] is a simple enough read (start at the "Roaring Bitmap" section at the end of page 4).
2. Our file uses a chunk-based approach similar to the commit-graph file: one chunk is simply a list of the commits that have bitmaps. Another chunk is the raw binary data of all bitmaps concatenated together. The last chunk connects the other two chunks by a) providing an offset into the binary data for the bitmap at that commit, and b) the commit that provides a delta base for the bitmap.
If we are considering changing the reachability bitmap, then I'm very intrigued. I think the number one thing to consider is to use the multi-pack-index as a reference point (with a stable object order) so the objects can be repacked independently from the reachability bitmap computation. If we are changing the model at that level, then it is worth thinking about other questions, like how we index the file or how we compress the bitmaps.
Thanks,
-Stolee
[1] https://roaringbitmap.org/about/
[2] https://arxiv.org/abs/1603.06549
Consistently faster and smaller compressed bitmaps with Roaring
Re: [PATCH 4/3] ewah: adjust callers of ewah_read_mmap()
Quoted 7 lines · Derrick Stolee
If we are considering changing the reachability bitmap, then I'm very intrigued. I think the number one thing to consider is to use the multi-pack-index as a reference point (with a stable object order) so the objects can be repacked independently from the reachability bitmap computation. If we are changing the model at that level, then it is worth thinking about other questions, like how we index the file or how we compress the bitmaps.
I'm open to a new format if it provides significant improvements over the existing one. I think the existing bitmaps have served us well for several years, but they do have a few weaknesses. Some of which I mentioned before, but the most obvious one is that being very pack-oriented they require repacking to update (and don't handle cross-pack reachability at all). I know that doesn't fly for Windows-sized repos at all, but it would also be nice if we could do incremental updates more cheaply (e.g., after every push instead of just once a day).
The Roaring stuff looks really interesting. I'm curious about the stable object order you guys use. Because EWAH is basically run-length-encoding, it benefits hugely from having the bitmaps in pack order (where there's a enormous locality with respect to reachability) as opposed to sha1 order (where it's essentially random).
Is your stable object order based on traversing the commit graph? Or does Roaring do a sufficiently better job of compressing the jumbled sha1 order?
-Peff
Re: [PATCH 4/3] ewah: adjust callers of ewah_read_mmap()
In reply to Jeff KingQuoted 31 lines · Jeff King
Quoted 10 lines · Jeff King
Yep. We also fail to check if we even have enough bytes to read the
buffer_sizein the first place.Here are some patches. The first one fixes the problem you found. The second one drops some dead code that has a related problem. And the third just drops some dead code that I noticed in the same file. :)
[1/3]:
ewah_read_mmap: bounds-check mmap reads [2/3]: ewah: dropewah_deserializefunction [3/3]: ewah: dropewah_serialize_nativefunctionActually, we'd want this one on top. Arguably it could be squashed into patch 1.
-- >8 --
Subject: ewah: adjust callers ofewah_read_mmap()The return value of
ewah_read_mmap()is now anssize_t, since we could (in theory) process up to 32GB of data. This would never happen in practice, but a corrupt or malicious .bitmap or index file could convince us to do so.Let's make sure that we don't stuff the value into an int, which would cause us to incorrectly move our pointer forward. We'd always move too little, since negative values are used for reporting errors. So the worst case is just that we end up reporting a corrupt file, not an out-of-bounds read.
Quoted 2 lines
Signed-off-by Jeff King <[email protected]>---
Makes sense.
Quoted 30 lines
dir.c | 3 ++- pack-bitmap.c | 2 +- 2 files changed, 3 insertions(+), 2 deletions(-)dir.c +2
-1@@ -2725,7 +2725,8 @@ struct untracked_cache *read_untracked_extension(const void *data, unsigned longstruct read_data rd;const unsigned char *next = data, *end = (const unsigned char *)data + sz;const char *ident; -int ident_len, len; +int ident_len; +ssize_t len;const char *exclude_per_dir;if (sz <=1 || end[-1 ] !='\0' )pack-bitmap.c +1
-1@@ -125,7 +125,7 @@ static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index) {struct ewah_bitmap *b =ewah_pool_new (); -int bitmap_size =ewah_read_mmap (b, +ssize_t bitmap_size =ewah_read_mmap (b, index->map + index->map_pos, index->map_size - index->map_pos);
Quoted 6 lines · Jeff King
Quoted 1 line · Luat Nguyen
Recently, I’ve found a security issue related to out-of-bound read at function named
ewah_read_mmapThanks, this is definitely a bug worth addressing. But note...
Quoted 7 lines
Quoted 1 line
Assume that, an attacker can put malicious
./git/indexinto a repo by somehow.We generally don't consider .git/index (or pack .bitmap files, which also use this implementation) to be a major part of Git's attack surface, since they are generated locally. And if you can write to somebody's .git directory, there are already much easier ways to execute arbitrary code.
Thanks for giving a fair assessment on the gravity of the issue, to which I agree fully, and also fixes and clean-ups.
Quoted 21 lines
Quoted 3 lines
Since there is lack of check whether the remaining size of
ptris equal tobuffer_sizeor not.Yep. We also fail to check if we even have enough bytes to read the
buffer_sizein the first place.Here are some patches. The first one fixes the problem you found. The second one drops some dead code that has a related problem. And the third just drops some dead code that I noticed in the same file. :)
[1/3]:
ewah_read_mmap: bounds-check mmap reads [2/3]: ewah: dropewah_deserializefunction [3/3]: ewah: dropewah_serialize_nativefunctionewah/ewah_io.c | 106 ++++++++-------------------------------- ewah/ewok.h | 4 +- t/t5310-pack-bitmaps.sh | 13 +++++ 3 files changed, 35 insertions(+), 88 deletions(-)-Peff
Greetings, all:
Just curious if there was any additional comment on this potential OOB? I may have missed it and if so, apologies for the ask.
Cheers,
Ed
-----Original Message-----
From: [email protected] [mailto:[email protected]] On Behalf Of Luat Nguyen
Sent: Thursday, June 14, 2018 7:00 PM
To: [email protected]
Subject: security: potential out-of-bound read at ewah_io.c |ewah_read_mmap|
Hi folks,
Recently, I’ve found a security issue related to out-of-bound read at function named ewah_read_mmap
Assume that, an attacker can put malicious ./git/index into a repo by somehow.
Since there is lack of check whether the remaining size of ptris equal to buffer_size or not.
So 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.
Leads to infoleak. You can find more details and asan crash below.
# xxd .git/index
00000000: 4449 5243 0000 0002 0000 0000 4653 4d4e DIRC........FSMN
00000010: 0000 0024 0000 0001 1538 2489 c8fc 3616 ...$.....8$...6.
00000020: 0000 0014 0000 0000 0000 2000 4141 .......... .AA
^ evil size here = 0x2000***** SNIP CODE *****
int ewah_read_mmap(struct ewah_bitmap *self, const void *map, size_t len) { …
self->buffer_size = self->alloc_size = get_be32(ptr); ptr += sizeof(uint32_t); … memcpy(self->buffer, ptr, self->buffer_size * sizeof(eword_t));
[memory map]
0x7f990eca3000 0x7f990eca4000 r--p 1000 0 /media/sf_Fuzz/vuln_repo/.git/index <— where `ptr` is placed
0x7f990eca4000 0x7f990eca5000 r--p 1000 25000 /lib/x86_64-linux-gnu/ld-2.23.so <— memcpy will reach here
0x7f990eca5000 0x7f990eca6000 rw-p 1000 26000 /lib/x86_64-linux-gnu/ld-2.23.so <— and here [ ASAN log ]
root@guest:/media/sf_SHARE/vuln_repo# /media/sf_SHARE/git-master-asan/git status =================================================================
==4324==ERROR: AddressSanitizer: unknown-crash on address 0x7f6f235b0000 at pc 0x0000004bba79 bp 0x7ffc75e68850 sp 0x7ffc75e68000 READ of size 65536 at 0x7f6f235b0000 thread T0
#0 0x4bba78 in __asan_memcpy /tmp/final/llvm.src/projects/compiler-rt/lib/asan/asan_interceptors_memintrinsics.cc:23:3
#1 0x8c910e in ewah_read_mmap /media/sf_SHARE/git-master-asan/ewah/ewah_io.c:144:2
#2 0x8e2534 in read_fsmonitor_extension /media/sf_SHARE/git-master-asan/fsmonitor.c:46:8
#3 0xa05862 in read_index_extension /media/sf_SHARE/git-master-asan/read-cache.c:1615:3
#4 0xa046f3 in do_read_index /media/sf_SHARE/git-master-asan/read-cache.c:1872:7
#5 0xa03325 in read_index_from /media/sf_SHARE/git-master-asan/read-cache.c:1913:8
#6 0xa03231 in read_index /media/sf_SHARE/git-master-asan/read-cache.c:1634:9
#7 0x9de5e8 in read_index_preload /media/sf_SHARE/git-master-asan/preload-index.c:119:15
#8 0x566cc6 in cmd_status /media/sf_SHARE/git-master-asan/builtin/commit.c:1358:2
#9 0x4ede8c in run_builtin /media/sf_SHARE/git-master-asan/git.c:417:11
#10 0x4ea939 in handle_builtin /media/sf_SHARE/git-master-asan/git.c:632:8
#11 0x4ed655 in run_argv /media/sf_SHARE/git-master-asan/git.c:684:4
#12 0x4ea037 in cmd_main /media/sf_SHARE/git-master-asan/git.c:761:19
#13 0x759c8b in main /media/sf_SHARE/git-master-asan/common-main.c:45:9
#14 0x7f6f2243382f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
#15 0x41c268 in _start (/media/sf_SHARE/git-master-asan/git+0x41c268)Address 0x7f6f235b0000 is a wild pointer.
SUMMARY: 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:
0x0fee646adfb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0fee646adfc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0fee646adfd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0fee646adfe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
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
0x0fee646ae010: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
0x0fee646ae020: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
0x0fee646ae030: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
0x0fee646ae040: fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
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):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa Freed heap region: fd Stack left redzone: f1 Stack mid redzone: f2 Stack right redzone: f3 Stack after return: f5 Stack use after scope: f8 Global redzone: f9 Global init order: f6 Poisoned by user: f7 Container overflow: fc Array cookie: ac Intra object redzone: bb ASan internal: fe Left alloca redzone: ca Right alloca redzone: cb
==4324==ABORTING
root@guest:/media/sf_SHARE/vuln_repo#
Regards,
Luat Nguyen.
______________________________________________________________________
The 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.
______________________________________________________________________
Quoted 2 lines · Edwin
Just curious if there was any additional comment on this potential OOB? I may have missed it and if so, apologies for the ask.
The fix is in master, and should be part of the upcoming v2.18. See commit 9d2e330b17 (ewah_read_mmap: bounds-check mmap reads, 2018-06-14).
-Peff