Page MenuHomePhabricator

Make SmallVector assert if it cannot grow.
ClosedPublic

Authored by browneee on Apr 6 2020, 3:27 PM.

Details

Summary

Context:

/// Double the size of the allocated memory, guaranteeing space for at
/// least one more element or MinSize if specified.
void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }

void push_back(const T &Elt) {
  if (LLVM_UNLIKELY(this->size() >= this->capacity()))
    this->grow();
  memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T));
  this->set_size(this->size() + 1);
}

When grow is called in push_back() without a MinSize specified, this is
relying on the guarantee of space for at least one more element.

There is an edge case bug where the SmallVector is already at its maximum size
and push_back() calls grow() with default MinSize of zero. Grow is unable to
provide space for one more element, but push_back() assumes the additional
element it will be available. This can result in silent memory corruption, as
this->end() will be an invalid pointer and the program may continue executing.

Another alternative to fix would be to remove the default argument from
grow(), which would mean several changing grow() to grow(this->size()+1)
in several places.

No test case added because it would require allocating ~4GB.

Diff Detail

Unit TestsFailed

TimeTest
11,540 mslldb-api.commands/expression/import-std-module/basic::Unknown Unit Message ("")
Script: -- /usr/bin/python /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/lldb/test/API/dotest.py --arch x86_64 -s /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-traces -S nm -u CXXFLAGS -u CFLAGS --env ARCHIVER=/usr/bin/ar --env OBJCOPY=/usr/bin/objcopy --env LLVM_LIBS_DIR=/mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./lib --build-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-build.noindex --lldb-module-cache-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-build.noindex/module-cache-lldb/lldb-api --clang-module-cache-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-build.noindex/module-cache-clang/lldb-api --executable /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/lldb --compiler /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/clang --dsymutil /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/dsymutil --filecheck /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/FileCheck --lldb-libs-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./lib /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/lldb/test/API/commands/expression/import-std-module/basic -p TestImportStdModule.py
3,610 mslldb-api.commands/expression/import-std-module/conflicts::Unknown Unit Message ("")
Script: -- /usr/bin/python /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/lldb/test/API/dotest.py --arch x86_64 -s /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-traces -S nm -u CXXFLAGS -u CFLAGS --env ARCHIVER=/usr/bin/ar --env OBJCOPY=/usr/bin/objcopy --env LLVM_LIBS_DIR=/mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./lib --build-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-build.noindex --lldb-module-cache-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-build.noindex/module-cache-lldb/lldb-api --clang-module-cache-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-build.noindex/module-cache-clang/lldb-api --executable /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/lldb --compiler /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/clang --dsymutil /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/dsymutil --filecheck /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/FileCheck --lldb-libs-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./lib /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/lldb/test/API/commands/expression/import-std-module/conflicts -p TestStdModuleWithConflicts.py
5,630 mslldb-api.commands/expression/import-std-module/deque-basic::Unknown Unit Message ("")
Script: -- /usr/bin/python /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/lldb/test/API/dotest.py --arch x86_64 -s /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-traces -S nm -u CXXFLAGS -u CFLAGS --env ARCHIVER=/usr/bin/ar --env OBJCOPY=/usr/bin/objcopy --env LLVM_LIBS_DIR=/mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./lib --build-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-build.noindex --lldb-module-cache-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-build.noindex/module-cache-lldb/lldb-api --clang-module-cache-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-build.noindex/module-cache-clang/lldb-api --executable /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/lldb --compiler /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/clang --dsymutil /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/dsymutil --filecheck /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/FileCheck --lldb-libs-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./lib /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/lldb/test/API/commands/expression/import-std-module/deque-basic -p TestDequeFromStdModule.py
5,490 mslldb-api.commands/expression/import-std-module/deque-dbg-info-content::Unknown Unit Message ("")
Script: -- /usr/bin/python /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/lldb/test/API/dotest.py --arch x86_64 -s /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-traces -S nm -u CXXFLAGS -u CFLAGS --env ARCHIVER=/usr/bin/ar --env OBJCOPY=/usr/bin/objcopy --env LLVM_LIBS_DIR=/mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./lib --build-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-build.noindex --lldb-module-cache-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-build.noindex/module-cache-lldb/lldb-api --clang-module-cache-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-build.noindex/module-cache-clang/lldb-api --executable /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/lldb --compiler /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/clang --dsymutil /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/dsymutil --filecheck /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/FileCheck --lldb-libs-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./lib /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/lldb/test/API/commands/expression/import-std-module/deque-dbg-info-content -p TestDbgInfoContentDequeFromStdModule.py
5,210 mslldb-api.commands/expression/import-std-module/forward_list::Unknown Unit Message ("")
Script: -- /usr/bin/python /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/lldb/test/API/dotest.py --arch x86_64 -s /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-traces -S nm -u CXXFLAGS -u CFLAGS --env ARCHIVER=/usr/bin/ar --env OBJCOPY=/usr/bin/objcopy --env LLVM_LIBS_DIR=/mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./lib --build-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-build.noindex --lldb-module-cache-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-build.noindex/module-cache-lldb/lldb-api --clang-module-cache-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/lldb-test-build.noindex/module-cache-clang/lldb-api --executable /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/lldb --compiler /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/clang --dsymutil /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/dsymutil --filecheck /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./bin/FileCheck --lldb-libs-dir /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/build/./lib /mnt/disks/ssd0/agent/workspace/amd64_debian_testing_clang8/lldb/test/API/commands/expression/import-std-module/forward_list -p TestForwardListFromStdModule.py
View Full Test Results (41 Failed)

Event Timeline

browneee created this revision.Apr 6 2020, 3:27 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 6 2020, 3:27 PM
tellenbach added a subscriber: tellenbach.
tellenbach added inline comments.Apr 6 2020, 5:03 PM
llvm/lib/Support/SmallVector.cpp
43

Could you change this function's comment to include that the SmallVector needs to be able to grow by at least one element (please also change in llvm/include/llvm/ADT/SmallVector.h)? This is currently only documented for grow but your patch adds a restriction that should be documented locally.

52

Can you use Capacity directly and omit the function call?

browneee updated this revision to Diff 255557.Apr 6 2020, 6:03 PM
browneee marked 2 inline comments as done.

Added function comment on grow_pod.

browneee added inline comments.Apr 6 2020, 6:04 PM
llvm/lib/Support/SmallVector.cpp
52

I expect this call will be inlined, along with the existing calls to capacity() and size() in this function.
Using capacity() seems consistent with the rest of the SmallVector code.

tellenbach added inline comments.Apr 7 2020, 9:25 AM
llvm/include/llvm/ADT/SmallVector.h
49

Here is some word missing: This function will report a fatal error if it cannot increase capactity.?

llvm/lib/Support/SmallVector.cpp
42

Same here: A word is missing.

browneee updated this revision to Diff 255777.Apr 7 2020, 12:44 PM

Add "report a " to comments.

browneee marked 2 inline comments as done.Apr 7 2020, 12:45 PM
browneee marked an inline comment as done.Apr 8 2020, 10:17 AM

LGTM, thanks.

tellenbach accepted this revision.Apr 9 2020, 3:30 AM
This revision is now accepted and ready to land.Apr 9 2020, 3:30 AM

I am not a committer, please submit for me.

browneee abandoned this revision.Apr 10 2020, 11:11 AM

Incorporated into https://reviews.llvm.org/D77621 (because this is not submitted yet, and that change now moves this code).

browneee reclaimed this revision.Apr 21 2020, 10:01 AM
This revision is now accepted and ready to land.Apr 21 2020, 10:01 AM
browneee updated this revision to Diff 259041.Apr 21 2020, 10:02 AM

Update. Add check to SmallVectorTemplateBase<T, TriviallyCopyable>::grow too.

browneee updated this revision to Diff 259123.Apr 21 2020, 4:14 PM

Rebase to head.

Incorporated into https://reviews.llvm.org/D77621 (because this is not submitted yet, and that change now moves this code).

Based on this comment I thought you'd abandoned this patch...

Rebase to head.

But since you're updating here, I should note that the patch as it looks here is still working with UINT32_MAX instead of max_size(). It should be updated in light of https://reviews.llvm.org/D77621.

Incorporated into https://reviews.llvm.org/D77621 (because this is not submitted yet, and that change now moves this code).

Based on this comment I thought you'd abandoned this patch...

I should have been more explicit here. After D77621 was reverted, I picked it up again to make this change separately.

Rebase to head.

But since you're updating here, I should note that the patch as it looks here is still working with UINT32_MAX instead of max_size(). It should be updated in light of https://reviews.llvm.org/D77621.

Sorry, I didn't see this comment before pushing.

I think UINT32_MAX is consistent with existing usage in these functions. In D77621 the max_size() part of the change was necessary because it could vary. Here we can leave that change to a separate patch.