Changeset 280668 in webkit

Timestamp:

Aug 4, 2021 3:53:54 PM (3 years ago)

Author:

fpizlo@apple.com

Message:

[libpas] medium size class lookup needs to correctly fence the counting lock read path
​https://bugs.webkit.org/show_bug.cgi?id=228799

Reviewed by Tadeu Zagallo.

The medium size class lookup does a binary search on a data structure that may mutate; we
catch that using a counting lock. But the algorithm wasn't fencing the tail end; it's supposed
to reread the count at the end but that read was not fenced.

This adds the fencing using pas_depend. I confirmed that the disassembly does the right thing.
It adds very little code.

Also rebased a test. Libpas tests are very specific about memory usage in some cases, and so
sometimes you will encounter a test run that requires limits to be adjusted. This happens
because some tests can sometimes create very complex heap layouts that really do use more
memory than we asserted, but the assertion had always worked because the test never ran with
the "wrong" kind of layout. This fixes a one-off test failure I saw when debugging this fix.

• libpas/src/libpas/pas_mutation_count.h:

(pas_mutation_count_matches_with_dependency):
(pas_mutation_count_matches): Deleted.

• libpas/src/libpas/pas_segregated_heap.c:

(medium_directory_tuple_for_index_impl):
(medium_directory_tuple_for_index_with_lock):
(pas_segregated_heap_medium_directory_tuple_for_index):

• libpas/src/test/ThingyAndUtilityHeapAllocationTests.cpp:

(std::addLargeHeapTests):

Location:

trunk/Source/bmalloc

Files:

• ChangeLog (modified) (1 diff)
• libpas/src/libpas/pas_mutation_count.h (modified) (1 diff)
• libpas/src/libpas/pas_segregated_heap.c (modified) (8 diffs)
• libpas/src/test/ThingyAndUtilityHeapAllocationTests.cpp (modified) (1 diff)

trunk/Source/bmalloc/ChangeLog

@@ +1 @@
+2021-08-04  Filip Pizlo  <fpizlo@apple.com>
+
+        [libpas] medium size class lookup needs to correctly fence the counting lock read path
+        https://bugs.webkit.org/show_bug.cgi?id=228799
+
+        Reviewed by Tadeu Zagallo.
+
+        The medium size class lookup does a binary search on a data structure that may mutate; we
+        catch that using a counting lock. But the algorithm wasn't fencing the tail end; it's supposed
+        to reread the count at the end but that read was not fenced.
+
+        This adds the fencing using pas_depend. I confirmed that the disassembly does the right thing.
+        It adds very little code.
+
+        Also rebased a test. Libpas tests are very specific about memory usage in some cases, and so
+        sometimes you will encounter a test run that requires limits to be adjusted. This happens
+        because some tests can sometimes create very complex heap layouts that really do use more
+        memory than we asserted, but the assertion had always worked because the test never ran with
+        the "wrong" kind of layout. This fixes a one-off test failure I saw when debugging this fix.
+
+        * libpas/src/libpas/pas_mutation_count.h:
+        (pas_mutation_count_matches_with_dependency):
+        (pas_mutation_count_matches): Deleted.
+        * libpas/src/libpas/pas_segregated_heap.c:
+        (medium_directory_tuple_for_index_impl):
+        (medium_directory_tuple_for_index_with_lock):
+        (pas_segregated_heap_medium_directory_tuple_for_index):
+        * libpas/src/test/ThingyAndUtilityHeapAllocationTests.cpp:
+        (std::addLargeHeapTests):
+
 2021-08-03  Filip Pizlo  <fpizlo@apple.com>
 

trunk/Source/bmalloc/libpas/src/libpas/pas_mutation_count.h

@@ -67 +67 @@
 }
 
-static inline bool pas_mutation_count_matches(pas_mutation_count* mutation_count,
-                                              pas_mutation_count saved_mutation_count)
+static inline bool pas_mutation_count_matches_with_dependency(pas_mutation_count* mutation_count,
+                                                              pas_mutation_count saved_mutation_count,
+                                                              uintptr_t dependency)
 {
     pas_compiler_fence();
-    return mutation_count->count == saved_mutation_count.count;
+    return mutation_count[pas_depend(dependency)].count == saved_mutation_count.count;
 }
 

trunk/Source/bmalloc/libpas/src/libpas/pas_segregated_heap.c

@@ -235 +235 @@
 }
 
-static pas_segregated_heap_medium_directory_tuple*
+typedef struct {
+    pas_segregated_heap_medium_directory_tuple* tuple;
+    uintptr_t dependency;
+} medium_directory_tuple_for_index_impl_result;
+
+static PAS_ALWAYS_INLINE medium_directory_tuple_for_index_impl_result
 medium_directory_tuple_for_index_impl(
     pas_segregated_heap_rare_data* rare_data,
@@ -248 +253 @@
     unsigned end;
     pas_segregated_heap_medium_directory_tuple* best;
+    medium_directory_tuple_for_index_impl_result result;
     
     PAS_ASSERT(rare_data);
@@ -257 +263 @@
     end = num_medium_directories;
     best = NULL;
+
+    result.dependency = (uintptr_t)medium_directories;
     
     while (end > begin) {
         unsigned middle;
         pas_segregated_heap_medium_directory_tuple* directory;
+        unsigned begin_index;
+        unsigned end_index;
 
         middle = (begin + end) >> 1;
@@ -270 +280 @@
                     begin, end, middle, directory->begin_index, directory->end_index);
         }
-        
-        if (index < directory->begin_index) {
+
+        begin_index = directory->begin_index;
+        end_index = directory->end_index;
+        
+        result.dependency += begin_index + end_index;
+        
+        if (index < begin_index) {
             end = middle;
             best = directory;
@@ -277 +292 @@
         }
         
-        if (index > directory->end_index) {
+        if (index > end_index) {
             begin = middle + 1;
             continue;
         }
-        
-        return directory;
+
+        result.tuple = directory;
+        return result;
     }
 
     switch (search_mode) {
     case pas_segregated_heap_medium_size_directory_search_within_size_class_progression:
-        return NULL;
+        result.tuple = NULL;
+        return result;
         
     case pas_segregated_heap_medium_size_directory_search_least_greater_equal:
-        return best;
+        result.tuple = best;
+        return result;
     }
 
     PAS_ASSERT(!"Should not be reached");
-    return NULL;
+    result.tuple = NULL;
+    return result;
 }
 
@@ -319 +338 @@
         rare_data->num_medium_directories,
         index,
-        search_mode);
+        search_mode).tuple;
     
     pas_heap_lock_unlock_conditionally(heap_lock_hold_mode);
@@ -337 +356 @@
     pas_segregated_heap_medium_directory_tuple* medium_directories;
     unsigned num_medium_directories;
-    pas_segregated_heap_medium_directory_tuple* result;
+    medium_directory_tuple_for_index_impl_result result;
     
     rare_data = pas_segregated_heap_rare_data_ptr_load(&heap->rare_data);
@@ -362 +381 @@
         rare_data, medium_directories, num_medium_directories, index, search_mode);
     
-    if (pas_mutation_count_matches(&rare_data->mutation_count, saved_count))
-        return result;
+    if (pas_mutation_count_matches_with_dependency(
+            &rare_data->mutation_count, saved_count, result.dependency))
+        return result.tuple;
     
     return medium_directory_tuple_for_index_with_lock(

trunk/Source/bmalloc/libpas/src/test/ThingyAndUtilityHeapAllocationTests.cpp

@@ -2721 +2721 @@
                                         AllocationProgram::free("secondHalf")));
     ADD_TEST(testComplexLargeAllocation(IsolatedComplexAllocator(7, 1),
-                                        ExpectedBytes::upperBound(417792),
+                                        ExpectedBytes::upperBound(638976),
                                         AllocationProgram::allocate("boot", 40960, 1),
                                         AllocationProgram::free("boot"),