This is an archive of the discontinued LLVM Phabricator instance.

[Sema] Fix bug in TypeLocBuilder::pushImpl
ClosedPublic

Authored by ahatanak on Feb 2 2016, 10:54 PM.

Details

Summary

This patch fixes a bug in the code between line 117-126 of TypeLocBuilder.cpp which was causing the assert in line 132.

The bug manifests itself when an element of size=4 and alignment=4 is inserted first and then an element of size=28 and alignment=8 is inserted next. The code inserts a 4-byte padding at the tail of the first element before the second element is inserted, but that is incorrect and unnecessary since the second element is correctly aligned without any paddings (it can start at Index=32 because it's size is 28-bytes).

Diff Detail

Event Timeline

ahatanak updated this revision to Diff 46746.Feb 2 2016, 10:54 PM
ahatanak retitled this revision from to [Sema] Fix bug in TypeLocBuilder::pushImpl.
ahatanak updated this object.
ahatanak added reviewers: doug.gregor, rjmccall, vsk.
ahatanak added a subscriber: cfe-commits.
ahatanak updated this revision to Diff 47037.Feb 5 2016, 12:30 PM

Fixed a couple of bugs:

  • Make sure Capacity is a multiple of 8-byte.
  • "||=" isn't a valid operator. Use "||" instead.
ahatanak updated this revision to Diff 47413.Feb 9 2016, 6:34 PM

Rename and add variables. Add comments to make it clearer what the code is doing.

Hi Akira,

Can you give a high-level explanation of how this patch fixes the problem? This patch enforces that the capacity is 8-byte aligned, is it required to solve the alignment issue here?

Thanks,
Manman

Thanks for working on this!

Manman

lib/Sema/TypeLocBuilder.cpp
96

This patch seems to do two things:
1> simplify the logic of deciding when to remove padding and when to insert padding (via RemoveOrInsertPadding)
2> fix the correctness issue

We can fix the correctness issue first and then simplify the logic.

ahatanak updated this revision to Diff 48033.Feb 15 2016, 4:22 PM

The bug is in the handling of elements whose LocalAlignment is 8, so I've fixed just that part.

I'll resend a patch to simplify the logic of TypeLocBuilder::pushImpl later as it's not urgent.

manmanren added inline comments.Feb 15 2016, 6:01 PM
lib/Sema/TypeLocBuilder.cpp
115

Expand this comment a little?

122

The logic looks correct.

The above if, else if, else can be simplified by combining the first condition with the last else condition, because memmove(xx, xx, 0) will just do nothing.

if (CurrentlyHasPadding) {

// remove padding

} else {

// insert padding

}

If you write this part (LocalAlignment == 8) in the same form as how we handle LocalAlignment == 4, it may be better to understand. i.e depending on the following conditions (NumBytesAtAlign8 == 0) (Padding == 0) (LocalSize % 8 == 0)

To help understanding, we can add some high-level comments to the original code of handling "LocalAlignment == 4":
When NumBytesAtAlign8 is not zero, we make sure Index is 8-byte aligned at function exit by adding a 4-byte padding if necessary.

ahatanak updated this revision to Diff 48241.Feb 17 2016, 2:34 PM

Address some of Manman's review comments.

  • Add comments that explain what the code is doing (I should add some high-level comments too later).
  • Simplify the if-else statement.

I haven't implemented the other changes you've suggested, because I wasn't sure whether imitating the code in "LocalAlignment == 4" would improve readability of the code. For example, I can declare variable "unsigned Padding = NumBytesAtAlign4 %8", but the variable alone doesn't tell you whether there is padding or not (if we haven't inserted any 8-byte elements, we won't have any paddings, but NumBytesAtAlign4 % 8 can still be non-zero).

Maybe I didn't understand what you were suggesting. Could you elaborate a bit more on which part of this code is perhaps hard to understand and how we can improve it?

Hi Akira,

How about the following?

else if (LocalAlignment == 8) {
  if (NumBytesAtAlign8 == 0) {
    // We have not seen any 8-byte aligned element yet. There is no padding and we are either 4-byte
    // aligned or 8-byte aligned depending on NumBytesAtAlign4.
    // Add in 4 bytes padding if we are not 8-byte aligned including this element.
    if ((LocalSize + NumBytesAtAlign4) % 8 != 0) {
      memmove(&Buffer[Index - 4], &Buffer[Index], NumBytesAtAlign4);
      Index -= 4;
    }
  } else {
    unsigned Padding = NumBytesAtAlign4 % 8;
    if (Padding == 0) { 
      if (LocalSize % 8 == 0) {
        // Everything is set: there's no padding and we don't need to add
        // any.
      } else {
        assert(LocalSize % 8 == 4);
        // No existing padding; add in 4 bytes padding
        memmove(&Buffer[Index - 4], &Buffer[Index], NumBytesAtAlign4);
        Index -= 4;
      }
    } else {
      assert(Padding == 4);
      if (LocalSize % 8 == 0) {
        // Everything is set: there's 4 bytes padding and we don't need
        // to add any.
      } else {
        assert(LocalSize % 8 == 4);
        // There are 4 bytes padding, but we don't need any; remove it.
        memmove(&Buffer[Index + 4], &Buffer[Index], NumBytesAtAlign4);
        Index += 4;
      }
    }
  }
  // Forget about any padding.
  NumBytesAtAlign4 = 0;
  NumBytesAtAlign8 += LocalSize;
}

Note that the handling of NumBytesAtAlign8 != 0 is the same for LocalAlignment == 4 vs. LocalAlignment == 8.
Also mention in the commit message that the original code seems to assume LocalSize is a multiple of 8 when LocalAlignment is 8.

Cheers,
Manman

OK, I now understand what you meant.

How about the following?

else if (LocalAlignment == 8) {
  if (NumBytesAtAlign8 == 0) {
    // We have not seen any 8-byte aligned element yet. There is no padding and we are either 4-byte
    // aligned or 8-byte aligned depending on NumBytesAtAlign4.
    // Add in 4 bytes padding if we are not 8-byte aligned including this element.
    if ((LocalSize + NumBytesAtAlign4) % 8 != 0) {
      memmove(&Buffer[Index - 4], &Buffer[Index], NumBytesAtAlign4);
      Index -= 4;
    }

If Capacity is not a multiple of 8, (LocalSize + NumBytesAtAlign4) % 8 doesn't tell you whether the new element will be 8-byte aligned. For example, if Capacity==36, NumBytesAtAlign4==4, and LocalSize==8, (LocalSize + NumBytesAtAlign4) equals 12 but padding is not needed as the new element can start at Index=24. Note that it's possible to have a Capacity that isn't a multiple of 8 by calling TypeLocBuilder::reserve. I think padding is needed if the new index (Index - LocalSize) is not a multiple of 8.

If Capacity is not a multiple of 8, (LocalSize + NumBytesAtAlign4) % 8 doesn't tell you whether the new element will be 8-byte aligned. For example, if Capacity==36, NumBytesAtAlign4==4, and LocalSize==8, (LocalSize + NumBytesAtAlign4) equals 12 but padding is not needed as the new element can start at Index=24.

I was reading the numbers wrong.

Note that it's possible to have a Capacity that isn't a multiple of 8 by calling TypeLocBuilder::reserve. I think padding is needed if the new index (Index - LocalSize) is not a multiple of 8.

You are right, I missed the case where Capacity may not be 8-byte aligned.

ahatanak updated this revision to Diff 48384.Feb 18 2016, 12:15 PM

Address Manman's review comments. Handle elements with "LocalAlignment == 8" similarly to those with "LocalAlignment == 4".

ahatanak updated this revision to Diff 48387.Feb 18 2016, 12:38 PM

Fix indentation.

Thanks Akira,

LGTM.

Manman

This revision was automatically updated to reflect the committed changes.