> which then causes the associated block to execute:
> 278 char *rchg1 = dd1->rchg;
> 279 long *rindex1 = dd1->rindex;
> 280
> 281 for (; off1 < lim1; off1++)
> 282 rchg1[rindex1[off1]] = 1;
> and then that's the end of the function!
> 308 return 0;
> 309 }
> It's completely relying on rchg to be filled with zeros before it's called :D
> that's definitely the issue here. ... or it looks like it to me now ...
> hopefully if i do that, then this assertion will pass and a new one will rise
> later.
Ok! So indeed wiping rchg did make that assertion pass.
@@ -839,6 +842,9 @@ private:
void do_diff()
{
auto xe = &this->xe;
+ // for now rchg is wiped as the git/xdiff algorithms assume this
+ std::memset(xe->xdf1.rchg - 1, 0, (size_t)(xe->xdf1.nrec + 2) *
sizeof(*xe->xdf1.rchg));
+ std::memset(xe->xdf2.rchg - 1, 0, (size_t)(xe->xdf2.nrec + 2) *
sizeof(*xe->xdf2.rchg));
switch (XDF_DIFF_ALG(xp.flags)) {
case XDF_PATIENCE_DIFF:
mustbe0(xdl_do_patience_diff(&xp, xe));
The next bug was a coding mistake in one of the consume loops, I wasn't walking
the linked list resulting in iterating the same node forever:
@@ -362,17 +362,20 @@ public:
/* if the classifier entry hash been consumed, recover it, then
classify the line. otherwise, classify the line, then update the line pointer
in case old lines are consumed. */
auto rchash_hi = (long) XDL_HASHLONG(crec->ha, cf->hbits);
- auto * rcrec_link = &cf.consumed_rchash[(size_t)rchash_hi];
+ xdlclass_t ** prev;
xdlclass_t * rcrec;
- while (*rcrec_link) {
- rcrec = *rcrec_link;
+ for (
+ prev = &cf.consumed_rchash[(size_t)rchash_hi];
+ (rcrec = *prev);
+ prev = &(*prev)->next
+ ) {
if (rcrec->ha == crec->ha && rcrec->size == crec->size) {
break;
};
}
- if (*rcrec_link) {
+ if (rcrec) {
assert(rcrec->next == nullptr && "hash collision in consumed
lines; should check for existing matching entry before using consumed entry");
- *rcrec_link = rcrec->next;
+ *prev = rcrec->next;
rcrec->line = crec->ptr;
That's two bugs fixed!
The next bug is a super-fun one: _a memory error_. I have so many memory checks
going on for this code. Here we have it:
$ ./diff_xdiff
[28/1799]
diff_main: Null case.
WINDOW RESIZE0=>2
consuming rec ptr 0x7f2942e00a00
consuming rec ptr 0x502000000250
WINDOW RESIZE2=>4
consuming rec ptr 0x7f2942e00a02
consuming rec ptr 0x502000000312
WINDOW RESIZE4=>8
consuming rec ptr 0x7f2942e00a04
consuming rec ptr 0x502000000334
diff_main: Equality.
WINDOW RESIZE0=>2
WINDOW RESIZE2=>4
WINDOW RESIZE4=>8
consuming rec ptr 0x7f2942e01200
consuming rec ptr 0x502000000550
consuming rec ptr 0x7f2942e01202
consuming rec ptr 0x502000000552
WINDOW RESIZE8=>16
consuming rec ptr 0x7f2942e01204
=================================================================
==15016==ERROR: AddressSanitizer: heap-use-after-free on address 0x5070000002f8
at pc 0x55d895dbd0a9 bp 0x7ffeba337450 sp 0x7ffeba337448
READ of size 8 at 0x5070000002f8 thread T0
#0 0x55d895dbd0a8 in
AsymmetricStreamingXDiff::assert_no_dangling_pointers()
/home/karl3/projects/zinc/src/diff_xdiff.cpp:765
#1 0x55d895dbf402 in
AsymmetricStreamingXDiff::extend_env(std::basic_string_view<char,
std::char_traits<char> >) /home/karl3/projects/zinc/src/diff_xdiff.cpp:818
#2 0x55d895d9667c in diff /home/karl3/projects/zinc/src/diff_xdiff.cpp:695
#3 0x55d895dec067 in
std::__n4861::coroutine_handle<zinc::__generator_promise_base<Diff,
zinc::generator<Diff, Diff, zinc::use_allocator_arg> > >::resume() const
/usr/include/c++/12/coroutine:244
#4 0x55d895dddad3 in zinc::__generator_promise_base<Diff,
zinc::generator<Diff, Diff, zinc::use_allocator_arg> >::resume()
../include/zinc/__generator.hpp:548
#5 0x55d895dcf32d in zinc::generator<Diff, Diff,
zinc::use_allocator_arg>::iterator::operator++()
../include/zinc/__generator.hpp:822
#6 0x55d895d9b7d3 in diff_main
/home/karl3/projects/zinc/src/diff_xdiff.cpp:1029
#7 0x55d895d9dbc8 in test_diff_xdiff()
/home/karl3/projects/zinc/src/diff_xdiff.cpp:1074
#8 0x55d895da4928 in main /home/karl3/projects/zinc/src/diff_xdiff.cpp:1108
#9 0x7f2944a33d67 in __libc_start_call_main
../sysdeps/nptl/libc_start_call_main.h:58
#10 0x7f2944a33e24 in __libc_start_main_impl ../csu/libc-start.c:360
#11 0x55d895d8c640 in _start
(/home/karl3/projects/zinc/src/diff_xdiff+0xb4640) (BuildId:
1dcce094fc42295839b19dfd2bae3a3a7afd2442)
0x5070000002f8 is located 56 bytes inside of 80-byte region
[0x5070000002c0,0x507000000310)
freed by thread T0 here:
#0 0x7f29458f3918 in free
../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:52
#1 0x55d895db5cb7 in DynamicXDFile::cha_consume_(long)
/home/karl3/projects/zinc/src/diff_xdiff.cpp:554
#2 0x55d895db331e in DynamicXDFile::consume(long)
/home/karl3/projects/zinc/src/diff_xdiff.cpp:463
#3 0x55d895d96edf in diff /home/karl3/projects/zinc/src/diff_xdiff.cpp:701
#4 0x55d895dec067 in
std::__n4861::coroutine_handle<zinc::__generator_promise_base<Diff,
zinc::generator<Diff, Diff, zinc::use_allocator_arg> > >::resume() const
/usr/include/c++/12/coroutine:244
#5 0x55d895dddad3 in zinc::__generator_promise_base<Diff,
zinc::generator<Diff, Diff, zinc::use_allocator_arg> >::resume()
../include/zinc/__generator.hpp:548
#6 0x55d895dcf32d in zinc::generator<Diff, Diff,
zinc::use_allocator_arg>::iterator::operator++()
../include/zinc/__generator.hpp:822
#7 0x55d895d9b7d3 in diff_main
/home/karl3/projects/zinc/src/diff_xdiff.cpp:1029
#8 0x55d895d9dbc8 in test_diff_xdiff()
/home/karl3/projects/zinc/src/diff_xdiff.cpp:1074
#9 0x55d895da4928 in main /home/karl3/projects/zinc/src/diff_xdiff.cpp:1108
#10 0x7f2944a33d67 in __libc_start_call_main
../sysdeps/nptl/libc_start_call_main.h:58
previously allocated by thread T0 here:
#0 0x7f29458f4c77 in malloc
../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:69
#1 0x55d895e12542 in xdl_cha_alloc
/home/karl3/projects/zinc/third_party/xdiff/xutils.c:101
#2 0x55d895dae6d4 in DynamicXDFile::extend_pre(s_xpparam*, long,
std::basic_string_view<char, std::char_traits<char> >)
/home/karl3/projects/zinc/src/diff_xdiff.cpp:357
#3 0x55d895db947b in
AsymmetricStreamingXDiff::AsymmetricStreamingXDiff(std::basic_string_view<char,
std::char_traits<char> >, long, unsigned long)
/home/karl3/projects/zinc/src/diff_xdiff.cpp:668
#4 0x55d895d9ab24 in diff_main
/home/karl3/projects/zinc/src/diff_xdiff.cpp:1018
#5 0x55d895d9dbc8 in test_diff_xdiff()
/home/karl3/projects/zinc/src/diff_xdiff.cpp:1074
#6 0x55d895da4928 in main /home/karl3/projects/zinc/src/diff_xdiff.cpp:1108
#7 0x7f2944a33d67 in __libc_start_call_main
../sysdeps/nptl/libc_start_call_main.h:58
SUMMARY: AddressSanitizer: heap-use-after-free
/home/karl3/projects/zinc/src/diff_xdiff.cpp:765 in
AsymmetricStreamingXDiff::assert_no_dangling_pointers()
One of the fun things about these memory errors (now in these modern times i
seem to have stumbled on when they actually get reported) is that there are
three separate stack traces: one for violation, one for deallocation, and one
for allocation.
