BitstreamWriter: Better assertion when a block's abbrev code size is too small
AcceptedPublic

Authored by jordan_rose on Oct 11 2017, 5:34 PM.

Details

Summary

Before: ((Val & ~(~0U >> (32-NumBits))) == 0 && "High bits set!")
After: (Abbrev <= (~0U >> (32-CurCodeSize)) && "Block code length is too small")

The same check, but earlier and with a better error message for this specific use case. (I was originally going to put this in EmitAbbrev instead, but realized that it's possible for some overly clever soul to have a block that just never uses high-abbrev records.)

Diff Detail

Repository
rL LLVM
jordan_rose created this revision.Oct 11 2017, 5:34 PM

Reviving this old review. I'd like *someone* to tell me I didn't miss something.

See inline notes.
Also, the edge case with CurCodeSize == 32, if that is possible, should be added.

include/llvm/Bitcode/BitstreamWriter.h
303

What is the expected range of CurCodeSize values?
This has UB if CurCodeSize == 32.
It would be much safer to just use the variant with subtraction:

assert(Abbrev <= (~(~0U >> (32-CurCodeSize))) && "Block code length is too small");
unittests/Bitcode/BitstreamWriterTest.cpp
65

I'd expect to see three tests.
One last valid one, the invalid one, and the next after the first invalid one.
So 3U, 4U, 5U.

jordan_rose added inline comments.Wed, Jun 13, 2:06 PM
include/llvm/Bitcode/BitstreamWriter.h
303

Good point. I don't think anyone's trying to use 32-bit record codes, but the spec doesn't seem to impose a limit. I'll switch it.

unittests/Bitcode/BitstreamWriterTest.cpp
65

This is just an arbitrary data value. What makes this too big is the CodeLen of 2 above. But I can certainly test overflowing a CodeLen of 3 as well.

jordan_rose added inline comments.Wed, Jun 13, 2:07 PM
unittests/Bitcode/BitstreamWriterTest.cpp
65

Oh, I see what you mean. Values 0-3 have a special meaning in bitstream mode, so I can't actually do that test, but I'll add one for overflowing 3.

lebedev.ri added inline comments.Wed, Jun 13, 2:14 PM
unittests/Bitcode/BitstreamWriterTest.cpp
65

Values 0-3 have a special meaning in bitstream mode

Right, so do that for CodeLen = 3, it will still be 3 values :)

jordan_rose edited the summary of this revision. (Show Details)
jordan_rose added a reviewer: lebedev.ri.

Took recommendation about the form of the check, pumped up the tests.

lebedev.ri added inline comments.Wed, Jun 13, 11:29 PM
unittests/Bitcode/BitstreamWriterTest.cpp
75–182

This looks rather monstrous, with a lot of duplication.
I was suggesting to just do:

TEST(BitstreamWriterTest, trapOnSmallAbbrevUsingBlockInfo_CodeLength3_Ok) {
  SmallString<64> Buffer;
  BitstreamWriter W(Buffer);
  W.EnterBlockInfoBlock();
  auto Abbrev = std::make_shared<BitCodeAbbrev>();
  Abbrev->Add(BitCodeAbbrevOp(2U);
  (void)W.EmitBlockInfoAbbrev(bitc::FIRST_APPLICATION_BLOCKID,
                              std::move(Abbrev));
  W.ExitBlock();
  W.EnterSubblock(bitc::FIRST_APPLICATION_BLOCKID, /*CodeLen*/3);
  W.EmitRecordWithAbbrev(Abbrev, makeArrayRef(2U));
  W.ExitBlock();
}

TEST(BitstreamWriterTest, trapOnSmallAbbrevUsingBlockInfo_CodeLength3_LastOk) {
  SmallString<64> Buffer;
  BitstreamWriter W(Buffer);
  W.EnterBlockInfoBlock();
  auto Abbrev = std::make_shared<BitCodeAbbrev>();
  Abbrev->Add(BitCodeAbbrevOp(3U);
  (void)W.EmitBlockInfoAbbrev(bitc::FIRST_APPLICATION_BLOCKID,
                              std::move(Abbrev));
  W.ExitBlock();
  W.EnterSubblock(bitc::FIRST_APPLICATION_BLOCKID, /*CodeLen*/3);
  W.EmitRecordWithAbbrev(Abbrev, makeArrayRef(3U));
  W.ExitBlock();
}

TEST(BitstreamWriterTest, trapOnSmallAbbrevUsingBlockInfo_CodeLength3_NotOk) {
  SmallString<64> Buffer;
  BitstreamWriter W(Buffer);
  W.EnterBlockInfoBlock();
  auto Abbrev = std::make_shared<BitCodeAbbrev>();
  Abbrev->Add(BitCodeAbbrevOp(4U);
  (void)W.EmitBlockInfoAbbrev(bitc::FIRST_APPLICATION_BLOCKID,
                              std::move(Abbrev));
  W.ExitBlock();
  W.EnterSubblock(bitc::FIRST_APPLICATION_BLOCKID, /*CodeLen*/3);
  W.EmitRecordWithAbbrev(Abbrev, makeArrayRef(4U));
  W.ExitBlock();

TEST(BitstreamWriterTest, trapOnSmallAbbrevUsingBlockInfo_CodeLength3_NoOverFlow) {
  SmallString<64> Buffer;
  BitstreamWriter W(Buffer);
  W.EnterBlockInfoBlock();
  auto Abbrev = std::make_shared<BitCodeAbbrev>();
  Abbrev->Add(BitCodeAbbrevOp(4294967295U); // i32 -1 
  (void)W.EmitBlockInfoAbbrev(bitc::FIRST_APPLICATION_BLOCKID,
                              std::move(Abbrev));
  W.ExitBlock();
  W.EnterSubblock(bitc::FIRST_APPLICATION_BLOCKID, /*CodeLen*/32);
  W.EmitRecordWithAbbrev(Abbrev, makeArrayRef(4294967295U));
  W.ExitBlock();
}
jordan_rose added inline comments.Thu, Jun 14, 9:30 AM
unittests/Bitcode/BitstreamWriterTest.cpp
75–182

The values in the abbreviation have nothing to do with the abbreviation codes themselves; in order to get to code 8 you have to actually register 5 abbreviations. (0-3 are reserved.) I could probably pull out some of this into helper functions but I didn't feel like it was going to be super important.

lebedev.ri accepted this revision.Sat, Jun 16, 1:42 AM

I would still like to see a test with CodeLen=32, and even a single call to EmitRecordWithAbbrevImpl()
(ubsan would then have caught the ub in the initial approach), but otherwise this seems reasonable to me.
I have no expertise in this code, so *please* wait for someone else to review this, too.

include/llvm/Bitcode/BitstreamWriter.h
303

I think you want to move this assert to before the first use of Abbrev (before line 301)

unittests/Bitcode/BitstreamWriterTest.cpp
75–182

Oh duh, i knew that, but kinda forgot :)

This revision is now accepted and ready to land.Sat, Jun 16, 1:42 AM