[asan] Avoid redundant poisoning checks in __sanitizer_contiguous_container_find_bad_address

[i.baravy]

Summary

__sanitizer_contiguous_container_find_bad_address computes three regions of a container to check for poisoning: begin, middle, end. The issue is that in current design the first region can be significantly larger than kMaxRangeToCheck.

Proposed patch fixes a typo to calculate the first region properly.

[vitalybuka]

Could you please also update some test to cover new behavior?

lib/asan/asan_poisoning.cc

423

Could you please combine these
for (uptr i = r2_beg; i < mid; i++)
for (uptr i = mid; i < r2_end; i++)

into
for (uptr i = r2_beg; i < r2_end; i++)

[i.baravy]

Merge cycles for adjacent regions.

[eugenis]

lib/asan/asan_poisoning.cc

423

But these loops check for opposite conditions. Now it is simply wrong: bytes after mid must be poisoned.

[vitalybuka]

lib/asan/asan_poisoning.cc

423

Oh, I didn't notice this, please undo this part.

[m.ostapenko]

lib/asan/asan_poisoning.cc

416

Why do you need all these changes (416, 417, 418)? If I read the code correctly, originally ASan checks bytes around beg, mid and end. What's incorrect here? Overlapping of memory ranges isn't a big deal here IMHO.

[i.baravy]

Revert merging cycles.

[i.baravy]

Thank you for the review, guys!

Vitaly,
could you suggest a test to update, please? I have no idea how to test this typo.

[filcab]

In D27061#605225, @i.baravy wrote:

Thank you for the review, guys!

Vitaly,
could you suggest a test to update, please? I have no idea how to test this typo.

I'm unsure you can easily test this since, due to the CHECK_LE(mid, end); (and no overflow), we know that end + kMaxRangeToCheck is bigger than mid, so we'll always get mid.
Maybe you can test it by having more than 64 bytes between beg and mid, and poisoning the 33rd byte. That way you know the check shouldn't be able to figure it out and you can check for lack of error (which is what should happen).
Of course, you'd need to add comments explaining you're testing that exact case, and any change to kMaxRangeToCheck would need a change in the test.

[eugenis]

In D27061#605247, @filcab wrote:

In D27061#605225, @i.baravy wrote:

Thank you for the review, guys!

Vitaly,
could you suggest a test to update, please? I have no idea how to test this typo.

I'm unsure you can easily test this since, due to the CHECK_LE(mid, end); (and no overflow), we know that end + kMaxRangeToCheck is bigger than mid, so we'll always get mid.
Maybe you can test it by having more than 64 bytes between beg and mid, and poisoning the 33rd byte. That way you know the check shouldn't be able to figure it out and you can check for lack of error (which is what should happen).
Of course, you'd need to add comments explaining you're testing that exact case, and any change to kMaxRangeToCheck would need a change in the test.

I don't think such test adds any value. I'm fine w/o any test changes.

lib/asan/asan_poisoning.cc

416

Well, with this change we get the same result with less work, so why not?

lib/asan/asan_poisoning.cc

const void *__sanitizer_contiguous_container_find_bad_address(
   uptr end = reinterpret_cast<uptr>(end_p);
   uptr mid = reinterpret_cast<uptr>(mid_p);
   CHECK_LE(beg, mid);
   CHECK_LE(mid, end);
   // Check some bytes starting from beg, some bytes around mid, and some bytes
   // ending with end.
   uptr kMaxRangeToCheck = 32;
   uptr r1_beg = beg;
-  uptr r1_end = Min(end + kMaxRangeToCheck, mid);
-  uptr r2_beg = Max(beg, mid - kMaxRangeToCheck);
-  uptr r2_end = Min(end, mid + kMaxRangeToCheck);
-  uptr r3_beg = Max(end - kMaxRangeToCheck, mid);
+  uptr r1_end = Min(beg + kMaxRangeToCheck, mid);
+  uptr r2_beg = Max(r1_end, mid - kMaxRangeToCheck/2);
+  uptr r2_end = Min(end, mid + kMaxRangeToCheck/2);
+  uptr r3_beg = Max(r2_end, end - kMaxRangeToCheck);
   uptr r3_end = end;
   for (uptr i = r1_beg; i < r1_end; i++)
     if (AddressIsPoisoned(i))
       return reinterpret_cast<const void *>(i);
   for (uptr i = r2_beg; i < mid; i++)
     if (AddressIsPoisoned(i))
       return reinterpret_cast<const void *>(i);
   for (uptr i = mid; i < r2_end; i++)
     if (!AddressIsPoisoned(i))
       return reinterpret_cast<const void *>(i);
   for (uptr i = r3_beg; i < r3_end; i++)
     if (!AddressIsPoisoned(i))
       return reinterpret_cast<const void *>(i);