Changeset 261179 in webkit


Ignore:
Timestamp:
May 5, 2020, 10:08:29 AM (5 years ago)
Author:
mark.lam@apple.com
Message:

Allow Bitmap to use up to a UCPURegister word size for internal bit storage.
​https://bugs.webkit.org/show_bug.cgi?id=211328
<rdar://problem/62755865>

Reviewed by Yusuke Suzuki.

Source/JavaScriptCore:

  • assembler/CPU.h:

Source/WTF:

  1. Moved the definition of CPURegister and UCPURegister down into WTF. Added CPU(REGISTER64) and CPU(REGISTER32) for determining what size a CPU general purpose register is.
  1. Updated Bitmap so that it will automatically choose the minimal required word size for the number of bits it needs to store. This means the Bitmap can automatically choose a WordType from uint8_t up to UCPURegister. Previously, the WordType is always uint32_t by default.

This should improve perf with use of Bitmap on 64-bit platforms. The size
optimization is necessary to prevent bloat on 64-bit platforms which would have
resulted if we simply set the default to always be UCPURegister.

  1. Added a check in findRunOfZeros() for handling the edge case where the requested runLength exceeds the bitmapSize.
  1. Fixed a bug in count() that was unnecessarily casting the bits to unsigned instead of just using the Bitmap WordType. As a result, when using a WordType of uint64_t, it was discarding bits from the count.
  1. Fixed invert() to leave the bits beyond bitmapSize untouched. Fixed isFull() to ignore the bits beyond bitmapSize.

By fixing invert() to leave those bits as 0, isEmpty() and hash() will
continue to work. Otherwise, inverting those bits will cause isEmpty() to
always fail, and hash()'s result may be different for the same set of bit
values within bitmapSize.

isFull(), on the other hand, checks for set bits in the words. Since there
may be 0 valued bits beyond bitmapSize, isFull() needs to be fixed to ignore
those.

  • WTF.xcodeproj/project.pbxproj:
  • wtf/Bitmap.h:

(WTF::WordType>::invert):
(WTF::WordType>::findRunOfZeros const):
(WTF::WordType>::count const):
(WTF::WordType>::isFull const):

  • wtf/CMakeLists.txt:
  • wtf/PlatformCPU.h:
  • wtf/PlatformUse.h:
  • wtf/StdIntExtras.h: Copied from Source/WTF/wtf/StdIntExtras.h.

Tools:

Added API tests for WTF::Bitmap to make sure that Bitmap is behaving correctly.
Since Bitmap is used in critical infrastructure like the GC, it is important to
ensure that there are no latent bugs.

  • TestWebKitAPI/CMakeLists.txt:
  • TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
  • TestWebKitAPI/Tests/WTF/Bitmap.cpp: Added.

(TestWebKitAPI::countBits):
(TestWebKitAPI::testBitmapSize):
(TestWebKitAPI::testBitmapConstructedEmpty):
(TestWebKitAPI::testBitmapSetGet):
(TestWebKitAPI::testBitmapTestAndSet):
(TestWebKitAPI::testBitmapTestAndClear):
(TestWebKitAPI::testBitmapConcurrentTestAndSet):
(TestWebKitAPI::testBitmapConcurrentTestAndClear):
(TestWebKitAPI::testBitmapClear):
(TestWebKitAPI::testBitmapClearAll):
(TestWebKitAPI::testBitmapInvert):
(TestWebKitAPI::testBitmapFindRunOfZeros):
(TestWebKitAPI::testBitmapCount):
(TestWebKitAPI::testBitmapIsEmpty):
(TestWebKitAPI::testBitmapIsFull):
(TestWebKitAPI::testBitmapMerge):
(TestWebKitAPI::testBitmapFilter):
(TestWebKitAPI::testBitmapExclude):
(TestWebKitAPI::testBitmapConcurrentFilter):
(TestWebKitAPI::testBitmapSubsumes):
(TestWebKitAPI::testBitmapForEachSetBit):
(TestWebKitAPI::testBitmapFindBit):
(TestWebKitAPI::testBitmapIteration):
(TestWebKitAPI::testBitmapMergeAndClear):
(TestWebKitAPI::testBitmapSetAndClear):
(TestWebKitAPI::testBitmapOperatorEqual):
(TestWebKitAPI::testBitmapOperatorNotEqual):
(TestWebKitAPI::testBitmapHash):
(TestWebKitAPI::TEST):

LayoutTests:

editing/undo-manager/undo-manager-delete-stale-undo-items.html exposed a bug in
this patch. However, when a failure occurs, this test runs perpetually until it
times out. There's no need to do this. After a finite number of GC cycles,
unreachable objects should be collected. This is especially so because
GCController.collect() does a synchronous full GC.

Added a cap of 10 GC tries, and fail out if the test does not see the expected
result. This allows the test to fail fast and avoid the costly time out.

  • editing/undo-manager/undo-manager-delete-stale-undo-items.html:
Location:
trunk
Files:
2 added
13 edited

Legend:

Unmodified
Added
Removed

  • trunk/LayoutTests/ChangeLog

    r261177 r261179  
     12020-05-05  Mark Lam  <mark.lam@apple.com>
     2
     3        Allow Bitmap to use up to a UCPURegister word size for internal bit storage.
     4        https://bugs.webkit.org/show_bug.cgi?id=211328
     5        <rdar://problem/62755865>
     6
     7        Reviewed by Yusuke Suzuki.
     8
     9        editing/undo-manager/undo-manager-delete-stale-undo-items.html exposed a bug in
     10        this patch.  However, when a failure occurs, this test runs perpetually until it
     11        times out.  There's no need to do this.  After a finite number of GC cycles,
     12        unreachable objects should be collected.  This is especially so because
     13        GCController.collect() does a synchronous full GC.
     14
     15        Added a cap of 10 GC tries, and fail out if the test does not see the expected
     16        result.  This allows the test to fail fast and avoid the costly time out.
     17
     18        * editing/undo-manager/undo-manager-delete-stale-undo-items.html:
     19
    1202020-05-05  Megan Gardner  <megan_gardner@apple.com>
    221

  • trunk/LayoutTests/editing/undo-manager/undo-manager-delete-stale-undo-items.html

    r261058 r261179  
    4949            const minimumNumberOfWrappersToCollectBeforePassing = 3 * undoItemCount - 300;
    5050            objectCountAfterClearingUndoStack = objectCountBeforeClearingUndoStack;
     51            var tries = 0;
    5152            while (objectCountBeforeClearingUndoStack - objectCountAfterClearingUndoStack < minimumNumberOfWrappersToCollectBeforePassing) {
    5253                await new Promise(resolve => setTimeout(resolve, 100));
    5354                objectCountAfterClearingUndoStack = objectCountAfterSimulatingMemoryPressureAndGarbageCollection();
     55                if (tries++ > 10)
     56                    break;
    5457            }
    5558

  • trunk/Source/JavaScriptCore/ChangeLog

    r261175 r261179  
     12020-05-05  Mark Lam  <mark.lam@apple.com>
     2
     3        Allow Bitmap to use up to a UCPURegister word size for internal bit storage.
     4        https://bugs.webkit.org/show_bug.cgi?id=211328
     5        <rdar://problem/62755865>
     6
     7        Reviewed by Yusuke Suzuki.
     8
     9        * assembler/CPU.h:
     10
    1112020-05-05  Keith Miller  <keith_miller@apple.com>
    212

  • trunk/Source/JavaScriptCore/assembler/CPU.h

    r261055 r261179  
    11/*
    2  * Copyright (C) 2008-2019 Apple Inc. All rights reserved.
     2 * Copyright (C) 2008-2020 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    2828#include "Options.h"
    2929#include <wtf/NumberOfCores.h>
     30#include <wtf/StdIntExtras.h>
    3031
    3132namespace JSC {
    32 
    33 #if USE(JSVALUE64)
    34 using CPURegister = int64_t;
    35 using UCPURegister = uint64_t;
    36 #else
    37 using CPURegister = int32_t;
    38 using UCPURegister = uint32_t;
    39 #endif
    4033
    4134using UCPUStrictInt32 = UCPURegister;

  • trunk/Source/WTF/ChangeLog

    r261170 r261179  
     12020-05-05  Mark Lam  <mark.lam@apple.com>
     2
     3        Allow Bitmap to use up to a UCPURegister word size for internal bit storage.
     4        https://bugs.webkit.org/show_bug.cgi?id=211328
     5        <rdar://problem/62755865>
     6
     7        Reviewed by Yusuke Suzuki.
     8
     9        1. Moved the definition of CPURegister and UCPURegister down into WTF.
     10           Added CPU(REGISTER64) and CPU(REGISTER32) for determining what size a CPU
     11           general purpose register is.
     12
     13        2. Updated Bitmap so that it will automatically choose the minimal required
     14           word size for the number of bits it needs to store.  This means the Bitmap
     15           can automatically choose a WordType from uint8_t up to UCPURegister.
     16           Previously, the WordType is always uint32_t by default.
     17
     18           This should improve perf with use of Bitmap on 64-bit platforms.  The size
     19           optimization is necessary to prevent bloat on 64-bit platforms which would have
     20           resulted if we simply set the default to always be UCPURegister.
     21
     22        3. Added a check in findRunOfZeros() for handling the edge case where the
     23           requested runLength exceeds the bitmapSize.
     24
     25        4. Fixed a bug in count() that was unnecessarily casting the bits to unsigned
     26           instead of just using the Bitmap WordType.  As a result, when using a WordType
     27           of uint64_t, it was discarding bits from the count.
     28
     29        5. Fixed invert() to leave the bits beyond bitmapSize untouched.
     30           Fixed isFull() to ignore the bits beyond bitmapSize.
     31
     32           By fixing invert() to leave those bits as 0, isEmpty() and hash() will
     33           continue to work.  Otherwise, inverting those bits will cause isEmpty() to
     34           always fail, and hash()'s result may be different for the same set of bit
     35           values within bitmapSize.
     36
     37           isFull(), on the other hand, checks for set bits in the words.  Since there
     38           may be 0 valued bits beyond bitmapSize, isFull() needs to be fixed to ignore
     39           those.
     40
     41        * WTF.xcodeproj/project.pbxproj:
     42        * wtf/Bitmap.h:
     43        (WTF::WordType>::invert):
     44        (WTF::WordType>::findRunOfZeros const):
     45        (WTF::WordType>::count const):
     46        (WTF::WordType>::isFull const):
     47        * wtf/CMakeLists.txt:
     48        * wtf/PlatformCPU.h:
     49        * wtf/PlatformUse.h:
     50        * wtf/StdIntExtras.h: Copied from Source/WTF/wtf/StdIntExtras.h.
     51
    1522020-05-05  Darin Adler  <darin@apple.com>
    253

  • trunk/Source/WTF/WTF.xcodeproj/project.pbxproj

    r261153 r261179  
    750750                FE86A8741E59440200111BBF /* ForbidHeapAllocation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ForbidHeapAllocation.h; sourceTree = "<group>"; };
    751751                FE8925AF1D00DAEC0046907E /* Indenter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Indenter.h; sourceTree = "<group>"; };
     752                FE97F6A8245CE5DD00C63FC6 /* StdIntExtras.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StdIntExtras.h; sourceTree = "<group>"; };
    752753                FEB6B035201BE0B600B958C1 /* PointerPreparations.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PointerPreparations.h; sourceTree = "<group>"; };
    753754                FEDACD3B1630F83F00C69634 /* StackStats.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StackStats.cpp; sourceTree = "<group>"; };
    … …  
    12331234                                313EDEC9778E49C9BEA91CFC /* StackTrace.cpp */,
    12341235                                EF7D6CD59D8642A8A0DA86AD /* StackTrace.h */,
     1236                                FE97F6A8245CE5DD00C63FC6 /* StdIntExtras.h */,
    12351237                                A8A47311151A825B004123FF /* StdLibExtras.h */,
    12361238                                FF0A436588954F3CB07DBECA /* StdList.h */,

  • trunk/Source/WTF/wtf/Bitmap.h

    r261073 r261179  
    2323#include <wtf/Atomics.h>
    2424#include <wtf/HashFunctions.h>
     25#include <wtf/StdIntExtras.h>
    2526#include <wtf/StdLibExtras.h>
    26 #include <stdint.h>
    2727#include <string.h>
     28#include <type_traits>
    2829
    2930namespace WTF {
    3031
    31 template<size_t bitmapSize, typename WordType = uint32_t>
     32template<size_t size>
     33using BitmapWordType = std::conditional_t<(size <= 32 && sizeof(UCPURegister) > sizeof(uint32_t)), uint32_t, UCPURegister>;
     34
     35template<size_t bitmapSize, typename WordType = BitmapWordType<bitmapSize>>
    3236class Bitmap final {
    3337    WTF_MAKE_FAST_ALLOCATED;
    3438   
    35     static_assert(sizeof(WordType) <= sizeof(unsigned), "WordType must not be bigger than unsigned");
     39    static_assert(sizeof(WordType) <= sizeof(UCPURegister), "WordType must not be bigger than the CPU atomic word size");
    3640public:
    3741    constexpr Bitmap();
    … …  
    231235    for (size_t i = 0; i < words; ++i)
    232236        bits[i] = ~bits[i];
     237    if constexpr (!!(bitmapSize % wordSize)) {
     238        constexpr size_t remainingBits = bitmapSize % wordSize;
     239        constexpr WordType mask = (static_cast<WordType>(1) << remainingBits) - 1;
     240        bits[words - 1] &= mask;
     241    }
    233242}
    234243
    … …  
    247256        runLength = 1;
    248257     
     258    if (runLength > bitmapSize)
     259        return -1;
     260
    249261    for (size_t i = 0; i <= (bitmapSize - runLength) ; i++) {
    250262        bool found = true;
    … …  
    270282    }
    271283    for (size_t i = start / wordSize; i < words; ++i)
    272         result += WTF::bitCount(static_cast<unsigned>(bits[i]));
     284        result += WTF::bitCount(bits[i]);
    273285    return result;
    274286}
    … …  
    287299{
    288300    for (size_t i = 0; i < words; ++i)
    289         if (~bits[i])
     301        if (~bits[i]) {
     302            if constexpr (!!(bitmapSize % wordSize)) {
     303                if (i == words - 1) {
     304                    constexpr size_t remainingBits = bitmapSize % wordSize;
     305                    constexpr WordType mask = (static_cast<WordType>(1) << remainingBits) - 1;
     306                    if ((bits[i] & mask) == mask)
     307                        return true;
     308                }
     309            }
    290310            return false;
     311        }
    291312    return true;
    292313}

  • trunk/Source/WTF/wtf/CMakeLists.txt

    r261055 r261179  
    239239    StackStats.h
    240240    StackTrace.h
     241    StdIntExtras.h
    241242    StdLibExtras.h
    242243    StdList.h

  • trunk/Source/WTF/wtf/PlatformCPU.h

    r259332 r261179  
    312312#endif
    313313
     314/* CPU general purpose register width. */
     315#if !defined(WTF_CPU_REGISTER64) && !defined(WTF_CPU_REGISTER32)
     316#if CPU(ADDRESS64) || CPU(ARM64)
     317#define WTF_CPU_REGISTER64 1
     318#else
     319#define WTF_CPU_REGISTER32 1
     320#endif
     321#endif
     322
    314323/* CPU(BIG_ENDIAN) or CPU(MIDDLE_ENDIAN) or neither, as appropriate. */
    315324

  • trunk/Source/WTF/wtf/PlatformUse.h

    r261170 r261179  
    132132#endif
    133133
    134 #if !defined(USE_JSVALUE64) && !defined(USE_JSVALUE32_64)
    135 #if CPU(ADDRESS64) || CPU(ARM64)
     134#if CPU(REGISTER64)
    136135#define USE_JSVALUE64 1
    137136#else
    138137#define USE_JSVALUE32_64 1
    139138#endif
    140 #endif /* !defined(USE_JSVALUE64) && !defined(USE_JSVALUE32_64) */
    141139
    142140#if USE(JSVALUE64)

  • trunk/Tools/ChangeLog

    r261159 r261179  
     12020-05-05  Mark Lam  <mark.lam@apple.com>
     2
     3        Allow Bitmap to use up to a UCPURegister word size for internal bit storage.
     4        https://bugs.webkit.org/show_bug.cgi?id=211328
     5        <rdar://problem/62755865>
     6
     7        Reviewed by Yusuke Suzuki.
     8
     9        Added API tests for WTF::Bitmap to make sure that Bitmap is behaving correctly.
     10        Since Bitmap is used in critical infrastructure like the GC, it is important to
     11        ensure that there are no latent bugs.
     12
     13        * TestWebKitAPI/CMakeLists.txt:
     14        * TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
     15        * TestWebKitAPI/Tests/WTF/Bitmap.cpp: Added.
     16        (TestWebKitAPI::countBits):
     17        (TestWebKitAPI::testBitmapSize):
     18        (TestWebKitAPI::testBitmapConstructedEmpty):
     19        (TestWebKitAPI::testBitmapSetGet):
     20        (TestWebKitAPI::testBitmapTestAndSet):
     21        (TestWebKitAPI::testBitmapTestAndClear):
     22        (TestWebKitAPI::testBitmapConcurrentTestAndSet):
     23        (TestWebKitAPI::testBitmapConcurrentTestAndClear):
     24        (TestWebKitAPI::testBitmapClear):
     25        (TestWebKitAPI::testBitmapClearAll):
     26        (TestWebKitAPI::testBitmapInvert):
     27        (TestWebKitAPI::testBitmapFindRunOfZeros):
     28        (TestWebKitAPI::testBitmapCount):
     29        (TestWebKitAPI::testBitmapIsEmpty):
     30        (TestWebKitAPI::testBitmapIsFull):
     31        (TestWebKitAPI::testBitmapMerge):
     32        (TestWebKitAPI::testBitmapFilter):
     33        (TestWebKitAPI::testBitmapExclude):
     34        (TestWebKitAPI::testBitmapConcurrentFilter):
     35        (TestWebKitAPI::testBitmapSubsumes):
     36        (TestWebKitAPI::testBitmapForEachSetBit):
     37        (TestWebKitAPI::testBitmapFindBit):
     38        (TestWebKitAPI::testBitmapIteration):
     39        (TestWebKitAPI::testBitmapMergeAndClear):
     40        (TestWebKitAPI::testBitmapSetAndClear):
     41        (TestWebKitAPI::testBitmapOperatorEqual):
     42        (TestWebKitAPI::testBitmapOperatorNotEqual):
     43        (TestWebKitAPI::testBitmapHash):
     44        (TestWebKitAPI::TEST):
     45
    1462020-05-05  Alexey Shvayka  <shvaikalesh@gmail.com>
    247

  • trunk/Tools/TestWebKitAPI/CMakeLists.txt

    r260277 r261179  
    2727
    2828    Tests/WTF/AtomString.cpp
     29    Tests/WTF/Bitmap.cpp
    2930    Tests/WTF/BloomFilter.cpp
    3031    Tests/WTF/BumpPointerAllocator.cpp

  • trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj

    r261141 r261179  
    11401140                F6F49C6B15545CA70007F39D /* DOMWindowExtensionNoCache_Bundle.cpp in Sources */ = {isa = PBXBuildFile; fileRef = F6F49C6615545C8D0007F39D /* DOMWindowExtensionNoCache_Bundle.cpp */; };
    11411141                F6FDDDD614241C6F004F1729 /* push-state.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = F6FDDDD514241C48004F1729 /* push-state.html */; };
     1142                FE2D9474245EB2F400E48135 /* Bitmap.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE2D9473245EB2DF00E48135 /* Bitmap.cpp */; };
    11421143/* End PBXBuildFile section */
    11431144
    … …  
    28032804                F6FDDDD214241AD4004F1729 /* PrivateBrowsingPushStateNoHistoryCallback.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = PrivateBrowsingPushStateNoHistoryCallback.cpp; sourceTree = "<group>"; };
    28042805                F6FDDDD514241C48004F1729 /* push-state.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = "push-state.html"; sourceTree = "<group>"; };
     2806                FE2D9473245EB2DF00E48135 /* Bitmap.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Bitmap.cpp; sourceTree = "<group>"; };
    28052807                FEB6F74E1B2BA44E009E4922 /* NakedPtr.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = NakedPtr.cpp; sourceTree = "<group>"; };
    28062808/* End PBXFileReference section */
    … …  
    39503952                                BC029B1A1486B23800817DA9 /* ns */,
    39513953                                26F1B44215CA434F00D1E4BF /* AtomString.cpp */,
     3954                                FE2D9473245EB2DF00E48135 /* Bitmap.cpp */,
    39523955                                E40019301ACE9B5C001B0A2A /* BloomFilter.cpp */,
    39533956                                0451A5A6235E438E009DF945 /* BumpPointerAllocator.cpp */,
    … …  
    47004703                                7C83DF591D0A590C00FEBCF3 /* ParkingLot.cpp in Sources */,
    47014704                                53EC25411E96FD87000831B9 /* PriorityQueue.cpp in Sources */,
     4705                                FE2D9474245EB2F400E48135 /* Bitmap.cpp in Sources */,
    47024706                                7C83DF131D0A590C00FEBCF3 /* RedBlackTree.cpp in Sources */,
    47034707                                7C83DF141D0A590C00FEBCF3 /* Ref.cpp in Sources */,
Note: See TracChangeset for help on using the changeset viewer.