- Revision
- 286516
- Author
- fpi...@apple.com
- Date
- 2021-12-03 14:48:23 -0800 (Fri, 03 Dec 2021)
Log Message
[libpas] Bitfit allocator has a wrong assertion when a page's max_free is enough for the size of an allocation, not enough for that allocation's size class, and the object of that size is not aligned to the currently requested alignment
https://bugs.webkit.org/show_bug.cgi?id=233831
Reviewed by Yusuke Suzuki.
What a combination of conditions:
- We just failed bitfit allocation in a page, which gives us some max_free (aka largest_available), and the allocation had nontrivial alignment.
- The max_free is smaller than the size class.
- The max_free is larger than the requested size.
- The max_free object is not aligned to the requested alignment.
The code handles this fine, but has a wrong assertion about it.
This change fixes the assertion and adds a test that deterministically reproduced the issue.
* libpas/libpas.xcodeproj/project.pbxproj:
* libpas/src/libpas/pas_bitfit_allocator.c:
(pas_bitfit_allocator_finish_failing):
* libpas/src/libpas/pas_bitfit_allocator_inlines.h:
(pas_bitfit_allocator_try_allocate):
* libpas/src/test/BitfitTests.cpp: Added.
(std::getBitfitSizeClasses):
(std::assertSizeClasses):
(std::testAllocateAlignedSmallerThanSizeClassAndSmallerThanLargestAvailable):
(addBitfitTests):
* libpas/src/test/TestHarness.cpp:
(main):
Modified Paths
Added Paths
Diff
Modified: trunk/Source/bmalloc/ChangeLog (286515 => 286516)
--- trunk/Source/bmalloc/ChangeLog 2021-12-03 21:58:02 UTC (rev 286515)
+++ trunk/Source/bmalloc/ChangeLog 2021-12-03 22:48:23 UTC (rev 286516)
@@ -1,3 +1,34 @@
+2021-12-03 Filip Pizlo <fpi...@apple.com>
+
+ [libpas] Bitfit allocator has a wrong assertion when a page's max_free is enough for the size of an allocation, not enough for that allocation's size class, and the object of that size is not aligned to the currently requested alignment
+ https://bugs.webkit.org/show_bug.cgi?id=233831
+
+ Reviewed by Yusuke Suzuki.
+
+ What a combination of conditions:
+
+ - We just failed bitfit allocation in a page, which gives us some max_free (aka largest_available), and the allocation had nontrivial alignment.
+ - The max_free is smaller than the size class.
+ - The max_free is larger than the requested size.
+ - The max_free object is not aligned to the requested alignment.
+
+ The code handles this fine, but has a wrong assertion about it.
+
+ This change fixes the assertion and adds a test that deterministically reproduced the issue.
+
+ * libpas/libpas.xcodeproj/project.pbxproj:
+ * libpas/src/libpas/pas_bitfit_allocator.c:
+ (pas_bitfit_allocator_finish_failing):
+ * libpas/src/libpas/pas_bitfit_allocator_inlines.h:
+ (pas_bitfit_allocator_try_allocate):
+ * libpas/src/test/BitfitTests.cpp: Added.
+ (std::getBitfitSizeClasses):
+ (std::assertSizeClasses):
+ (std::testAllocateAlignedSmallerThanSizeClassAndSmallerThanLargestAvailable):
+ (addBitfitTests):
+ * libpas/src/test/TestHarness.cpp:
+ (main):
+
2021-12-02 Filip Pizlo <fpi...@apple.com>
[libpas] Update to 96f9f4c28dc119695311c7c6bd81ed1f3f4e260c (allow more specialization of partial versus exclusive allocation)
Modified: trunk/Source/bmalloc/libpas/libpas.xcodeproj/project.pbxproj (286515 => 286516)
--- trunk/Source/bmalloc/libpas/libpas.xcodeproj/project.pbxproj 2021-12-03 21:58:02 UTC (rev 286515)
+++ trunk/Source/bmalloc/libpas/libpas.xcodeproj/project.pbxproj 2021-12-03 22:48:23 UTC (rev 286516)
@@ -568,6 +568,7 @@
2C48132D273F4159006CAB55 /* ExpendableMemoryTests.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 2C48132C273F4159006CAB55 /* ExpendableMemoryTests.cpp */; };
2C85DC4127128F0F00367905 /* pas_try_allocate_intrinsic.h in Headers */ = {isa = PBXBuildFile; fileRef = 2C85DC4027128F0F00367905 /* pas_try_allocate_intrinsic.h */; };
2C91E5502718DA9A00D67FF9 /* pas_size_lookup_mode.h in Headers */ = {isa = PBXBuildFile; fileRef = 2C91E54F2718DA9A00D67FF9 /* pas_size_lookup_mode.h */; };
+ 2CE2AE35275A953E00D02BBC /* BitfitTests.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 2CE2AE34275A953E00D02BBC /* BitfitTests.cpp */; };
/* End PBXBuildFile section */
/* Begin PBXContainerItemProxy section */
@@ -1252,6 +1253,7 @@
2C48132C273F4159006CAB55 /* ExpendableMemoryTests.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ExpendableMemoryTests.cpp; sourceTree = "<group>"; };
2C85DC4027128F0F00367905 /* pas_try_allocate_intrinsic.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = pas_try_allocate_intrinsic.h; sourceTree = "<group>"; };
2C91E54F2718DA9A00D67FF9 /* pas_size_lookup_mode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = pas_size_lookup_mode.h; sourceTree = "<group>"; };
+ 2CE2AE34275A953E00D02BBC /* BitfitTests.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = BitfitTests.cpp; sourceTree = "<group>"; };
/* End PBXFileReference section */
/* Begin PBXFrameworksBuildPhase section */
@@ -1344,6 +1346,7 @@
isa = PBXGroup;
children = (
0FDEA45D228B651B0085E340 /* BitfieldVectorTests.cpp */,
+ 2CE2AE34275A953E00D02BBC /* BitfitTests.cpp */,
0F53181022C954ED003F7B6A /* BitvectorTests.cpp */,
0F31A66723E8B336002C0CA3 /* CartesianTreeTests.cpp */,
0FC682362129D4EB003C6A13 /* CoalignTests.cpp */,
@@ -2584,6 +2587,7 @@
0FF248FD230CC4CB0077202E /* IsoHeapPageSharingTests.cpp in Sources */,
0FD48B6723B589910026C46D /* IsoHeapPartialAndBaselineTests.cpp in Sources */,
0F5B6094235E919900CAE629 /* IsoHeapReservedMemoryTests.cpp in Sources */,
+ 2CE2AE35275A953E00D02BBC /* BitfitTests.cpp in Sources */,
0F5193E7266AE5D400483A2C /* JITHeapTests.cpp in Sources */,
0FC64191213745FA0040CE5E /* LargeFreeHeapTests.cpp in Sources */,
0FEB6668231C87BC009C001B /* LargeSharingPoolDump.cpp in Sources */,
Modified: trunk/Source/bmalloc/libpas/src/libpas/pas_bitfit_allocator.c (286515 => 286516)
--- trunk/Source/bmalloc/libpas/src/libpas/pas_bitfit_allocator.c 2021-12-03 21:58:02 UTC (rev 286515)
+++ trunk/Source/bmalloc/libpas/src/libpas/pas_bitfit_allocator.c 2021-12-03 22:48:23 UTC (rev 286516)
@@ -205,6 +205,8 @@
size_t largest_available,
pas_bitfit_page_config* config)
{
+ static const bool verbose = false;
+
pas_bitfit_directory* directory;
pas_bitfit_size_class* size_class;
pas_bitfit_view* new_view;
@@ -222,6 +224,11 @@
view_index = view->index;
+ if (verbose) {
+ pas_log("Finishing failing in view %p, size = %zu, alignment = %zu, largest_available = %zu\n",
+ view, size, alignment, largest_available);
+ }
+
/* If we're still on the view that the allocator was on and we found that this view no longer
has enough max_free for our size class, then tell everyone about this and bail.
@@ -242,8 +249,14 @@
pas_bitfit_directory_set_processed_max_free(
directory, index, largest_available >> config->base.min_align_shift,
"processing on finish_failing");
+
+ /* If we're doing an aligned allocation, then we might now skip over this view even though the
+ size we were allocating would have fit. The reason why we're doing it is that the largest size
+ we could have fit is smaller than the size class, and although it's big enough for the size being
+ requested, it's not aligned properly. */
+ PAS_TESTING_ASSERT(largest_available < size
+ || alignment > pas_page_base_config_min_align(config->base));
- PAS_TESTING_ASSERT(largest_available < size);
PAS_TESTING_ASSERT(largest_available < size_class->size);
current_size_class = size_class;
Modified: trunk/Source/bmalloc/libpas/src/libpas/pas_bitfit_allocator_inlines.h (286515 => 286516)
--- trunk/Source/bmalloc/libpas/src/libpas/pas_bitfit_allocator_inlines.h 2021-12-03 21:58:02 UTC (rev 286515)
+++ trunk/Source/bmalloc/libpas/src/libpas/pas_bitfit_allocator_inlines.h 2021-12-03 22:48:23 UTC (rev 286516)
@@ -88,6 +88,9 @@
allocator->view = view;
}
+ if (verbose)
+ pas_log("Allocating in view %p\n", view);
+
bytes_committed = 0;
bitfit_result = pas_bitfit_allocation_result_create_empty();
@@ -178,6 +181,8 @@
if (verbose)
pas_log("bitfit allocation succeeded with %p\n", (void*)bitfit_result.u.result);
+
+ PAS_TESTING_ASSERT(pas_is_aligned(bitfit_result.u.result, alignment));
return pas_fast_path_allocation_result_create_success(bitfit_result.u.result);
}
Added: trunk/Source/bmalloc/libpas/src/test/BitfitTests.cpp (0 => 286516)
--- trunk/Source/bmalloc/libpas/src/test/BitfitTests.cpp (rev 0)
+++ trunk/Source/bmalloc/libpas/src/test/BitfitTests.cpp 2021-12-03 22:48:23 UTC (rev 286516)
@@ -0,0 +1,169 @@
+/*
+ * Copyright (c) 2021 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "TestHarness.h"
+
+#if PAS_ENABLE_ISO
+
+#include "iso_heap.h"
+#include "iso_heap_innards.h"
+#include "pas_bitfit_heap.h"
+#include "pas_bitfit_size_class.h"
+#include "pas_heap.h"
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+vector<size_t> getBitfitSizeClasses()
+{
+ vector<size_t> result;
+
+ pas_bitfit_heap* heap = pas_compact_atomic_bitfit_heap_ptr_load_non_null(
+ &iso_common_primitive_heap.segregated_heap.bitfit_heap);
+
+ pas_bitfit_page_config_variant variant;
+ for (PAS_EACH_BITFIT_PAGE_CONFIG_VARIANT_ASCENDING(variant)) {
+ pas_bitfit_directory* directory = pas_bitfit_heap_get_directory(heap, variant);
+
+ for (pas_bitfit_size_class* sizeClass =
+ pas_compact_atomic_bitfit_size_class_ptr_load(&directory->largest_size_class);
+ sizeClass;
+ sizeClass = pas_compact_atomic_bitfit_size_class_ptr_load(&sizeClass->next_smaller))
+ result.push_back(sizeClass->size);
+ }
+
+ sort(result.begin(), result.end());
+
+ return result;
+}
+
+template<typename... Arguments>
+void assertSizeClasses(Arguments... sizeClasses)
+{
+ vector<size_t> expectedSizeClasses { sizeClasses... };
+ vector<size_t> actualSizeClasses = getBitfitSizeClasses();
+
+ if (actualSizeClasses.size() == expectedSizeClasses.size()) {
+ bool allGood = true;
+ for (size_t index = 0; index < actualSizeClasses.size(); ++index) {
+ if (actualSizeClasses[index] != expectedSizeClasses[index]) {
+ allGood = false;
+ break;
+ }
+ }
+ if (allGood)
+ return;
+ }
+
+ cout << "Expected size classes: ";
+ for (size_t index = 0; index < expectedSizeClasses.size(); ++index) {
+ if (index)
+ cout << ", ";
+ cout << expectedSizeClasses[index];
+ }
+ cout << "\n";
+ cout << "But got: ";
+ for (size_t index = 0; index < actualSizeClasses.size(); ++index) {
+ if (index)
+ cout << ", ";
+ cout << actualSizeClasses[index];
+ }
+ cout << "\n";
+ CHECK(!"Test failed");
+}
+
+void testAllocateAlignedSmallerThanSizeClassAndSmallerThanLargestAvailable(
+ size_t firstSize, size_t numFirstObjects, size_t indexOfObjectToFree,
+ size_t fillerObjectSize, size_t alignedSize, size_t numAlignedObjects)
+{
+ static constexpr bool verbose = false;
+
+ vector<void*> objects;
+ void* freedObject;
+ uintptr_t freedObjectBegin;
+ uintptr_t freedObjectEnd;
+
+ for (size_t index = 0; index < numFirstObjects; ++index) {
+ void* ptr = iso_allocate_common_primitive(firstSize);
+ if (verbose)
+ cout << "Adding first object " << ptr << "\n";
+ objects.push_back(ptr);
+ }
+
+ assertSizeClasses(firstSize);
+
+ freedObject = objects[indexOfObjectToFree];
+ iso_deallocate(freedObject);
+
+ freedObjectBegin = reinterpret_cast<uintptr_t>(freedObject);
+ freedObjectEnd = freedObjectBegin + firstSize;
+
+ vector<void*> fillerObjects;
+ bool didStartAllocatingInFreedObject = false;
+ for (;;) {
+ void* fillerObject = iso_allocate_common_primitive(fillerObjectSize);
+ uintptr_t fillerObjectBegin = reinterpret_cast<uintptr_t>(fillerObject);
+ uintptr_t fillerObjectEnd = fillerObjectBegin + fillerObjectSize;
+ if (verbose)
+ cout << "Allocated filler object " << fillerObject << "\n";
+ if (fillerObjectBegin >= freedObjectBegin && fillerObjectEnd <= freedObjectEnd) {
+ didStartAllocatingInFreedObject = true;
+ fillerObjects.push_back(fillerObject);
+ } else {
+ if (didStartAllocatingInFreedObject)
+ break;
+ }
+ }
+
+ CHECK_EQUAL(fillerObjects.size(), firstSize / fillerObjectSize);
+ assertSizeClasses(fillerObjectSize, firstSize);
+
+ for (size_t index = 1; index < fillerObjects.size(); ++index)
+ iso_deallocate(fillerObjects[index]);
+
+ for (size_t index = 0; index < numAlignedObjects; ++index) {
+ void* ptr = iso_allocate_common_primitive_with_alignment(alignedSize, alignedSize);;
+ if (verbose)
+ cout << "Allocated aligned object " << ptr << "\n";
+ }
+
+ assertSizeClasses(fillerObjectSize, firstSize);
+}
+
+} // anonymous namespace
+
+#endif // PAS_ENABLE_ISO
+
+void addBitfitTests()
+{
+#if PAS_ENABLE_ISO
+ ForceBitfit forceBitfit;
+
+ ADD_TEST(testAllocateAlignedSmallerThanSizeClassAndSmallerThanLargestAvailable(
+ 1056, 100, 0, 16, 1024, 100));
+#endif // PAS_ENABLE_ISO
+}
Modified: trunk/Source/bmalloc/libpas/src/test/TestHarness.cpp (286515 => 286516)
--- trunk/Source/bmalloc/libpas/src/test/TestHarness.cpp 2021-12-03 21:58:02 UTC (rev 286515)
+++ trunk/Source/bmalloc/libpas/src/test/TestHarness.cpp 2021-12-03 22:48:23 UTC (rev 286516)
@@ -335,6 +335,7 @@
} // anonymous namespace
void addBitfieldVectorTests();
+void addBitfitTests();
void addBitvectorTests();
void addCartesianTreeTests();
void addCoalignTests();
@@ -697,6 +698,7 @@
// Run the rest of the tests in alphabetical order.
ADD_SUITE(BitfieldVector);
+ ADD_SUITE(Bitfit);
ADD_SUITE(Bitvector);
ADD_SUITE(CartesianTree);
ADD_SUITE(Coalign);
