Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1055)

Unified Diff: third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h

Issue 2570483002: Revert of Simple BlinkGC heap compaction. (Closed)
Patch Set: Created 4 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h
diff --git a/third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h b/third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h
deleted file mode 100644
index bdc267296e1ce0bcaa66cc1b8dd6a43a941c8fb5..0000000000000000000000000000000000000000
--- a/third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h
+++ /dev/null
@@ -1,136 +0,0 @@
-// Copyright 2016 The Chromium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file.
-
-#ifndef SparseHeapBitmap_h
-#define SparseHeapBitmap_h
-
-#include "platform/heap/BlinkGC.h"
-#include "platform/heap/HeapPage.h"
-#include "wtf/Alignment.h"
-#include "wtf/PtrUtil.h"
-#include <bitset>
-#include <memory>
-
-namespace blink {
-
-// A sparse bitmap of heap addresses where the (very few) addresses that are
-// set are likely to be in small clusters. The abstraction is tailored to
-// support heap compaction, assuming the following:
-//
-// - Addresses will be bitmap-marked from lower to higher addresses.
-// - Bitmap lookups are performed for each object that is compacted
-// and moved to some new location, supplying the (base, size)
-// pair of the object's heap allocation.
-// - If the sparse bitmap has any marked addresses in that range, it
-// returns a sub-bitmap that can be quickly iterated over to check which
-// addresses within the range are actually set.
-// - The bitmap is needed to support something that is very rarely done
-// by the current Blink codebase, which is to have nested collection
-// part objects. Consequently, it is safe to assume sparseness.
-//
-// Support the above by having a sparse bitmap organized as a binary
-// tree with nodes covering fixed size ranges via a simple bitmap/set.
-// That is, each SparseHeapBitmap node will contain a bitmap/set for
-// some fixed size range, along with pointers to SparseHeapBitmaps
-// for addresses on each side its range.
-//
-// This bitmap tree isn't kept balanced across the Address additions
-// made.
-//
-class PLATFORM_EXPORT SparseHeapBitmap {
- public:
- static std::unique_ptr<SparseHeapBitmap> create(Address base) {
- return WTF::wrapUnique(new SparseHeapBitmap(base));
- }
-
- ~SparseHeapBitmap() {}
-
- // Return the sparse bitmap subtree that at least covers the
- // [address, address + size) range, or nullptr if none.
- //
- // The returned SparseHeapBitmap can be used to quickly lookup what
- // addresses in that range are set or not; see |isSet()|. Its
- // |isSet()| behavior outside that range is not defined.
- SparseHeapBitmap* hasRange(Address, size_t);
-
- // True iff |address| is set for this SparseHeapBitmap tree.
- bool isSet(Address);
-
- // Mark |address| as present/set.
- void add(Address);
-
- // The assumed minimum alignment of the pointers being added. Cannot
- // exceed |log2(allocationGranularity)|; having it be equal to
- // the platform pointer alignment is what's wanted.
- static const int s_pointerAlignmentInBits = WTF_ALIGN_OF(void*) == 8 ? 3 : 2;
- static const size_t s_pointerAlignmentMask =
- (0x1u << s_pointerAlignmentInBits) - 1;
-
- // Represent ranges in 0x100 bitset chunks; bit I is set iff Address
- // |m_base + I * (0x1 << s_pointerAlignmentInBits)| has been added to the
- // |SparseHeapBitmap|.
- static const size_t s_bitmapChunkSize = 0x100;
-
- // A SparseHeapBitmap either contains a single Address or a bitmap
- // recording the mapping for [m_base, m_base + s_bitmapChunkRange)
- static const size_t s_bitmapChunkRange = s_bitmapChunkSize
- << s_pointerAlignmentInBits;
-
- // Return the number of nodes; for debug stats.
- size_t intervalCount() const;
-
- private:
- explicit SparseHeapBitmap(Address base) : m_base(base), m_size(1) {
- DCHECK(!(reinterpret_cast<uintptr_t>(m_base) & s_pointerAlignmentMask));
- static_assert(s_pointerAlignmentMask <= allocationMask,
- "address shift exceeds heap pointer alignment");
- // For now, only recognize 8 and 4.
- static_assert(WTF_ALIGN_OF(void*) == 8 || WTF_ALIGN_OF(void*) == 4,
- "unsupported pointer alignment");
- }
-
- Address base() const { return m_base; }
- size_t size() const { return m_size; }
- Address end() const { return base() + (m_size - 1); }
-
- Address maxEnd() const { return base() + s_bitmapChunkRange; }
-
- Address minStart() const {
- // If this bitmap node represents the sparse [m_base, s_bitmapChunkRange)
- // range, do not allow it to be "left extended" as that would entail
- // having to shift down the contents of the std::bitset somehow.
- //
- // This shouldn't be a real problem as any clusters of set addresses
- // will be marked while iterating from lower to higher addresses, hence
- // "left extension" are unlikely to be common.
- if (m_bitmap)
- return base();
- return (m_base > reinterpret_cast<Address>(s_bitmapChunkRange))
- ? (base() - s_bitmapChunkRange + 1)
- : nullptr;
- }
-
- Address swapBase(Address address) {
- DCHECK(!(reinterpret_cast<uintptr_t>(address) & s_pointerAlignmentMask));
- Address oldBase = m_base;
- m_base = address;
- return oldBase;
- }
-
- void createBitmap();
-
- Address m_base;
- // Either 1 or |s_bitmapChunkRange|.
- size_t m_size;
-
- // If non-null, contains a bitmap for addresses within [m_base, m_size)
- std::unique_ptr<std::bitset<s_bitmapChunkSize>> m_bitmap;
-
- std::unique_ptr<SparseHeapBitmap> m_left;
- std::unique_ptr<SparseHeapBitmap> m_right;
-};
-
-} // namespace blink
-
-#endif // SparseHeapBitmap_h

Powered by Google App Engine
This is Rietveld 408576698