third_party/WebKit/Source/platform/heap/SparseHeapBitmap.cpp - Issue 2570483002: Revert of Simple BlinkGC heap compaction.

Side by Side Diff: third_party/WebKit/Source/platform/heap/SparseHeapBitmap.cpp

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:

OLD	NEW
	(Empty)
1 // Copyright 2016 The Chromium Authors. All rights reserved.

2 // Use of this source code is governed by a BSD-style license that can be

3 // found in the LICENSE file.

4

5 #include "platform/heap/SparseHeapBitmap.h"

6

7 #include "wtf/PtrUtil.h"

8

9 namespace blink {

10

11 // Return the subtree/bitmap that covers the

12 // [address, address + size) range. Null if there is none.

13 SparseHeapBitmap* SparseHeapBitmap::hasRange(Address address, size_t size) {

14 DCHECK(!(reinterpret_cast<uintptr_t>(address) & s_pointerAlignmentMask));

15 SparseHeapBitmap* bitmap = this;

16 while (bitmap) {

17 // Interval starts after, \|m_right\| handles.

18 if (address > bitmap->end()) {

19 bitmap = bitmap->m_right.get();

20 continue;

21 }

22 // Interval starts within, \|bitmap\| is included in the resulting range.

23 if (address >= bitmap->base())

24 break;

25

26 Address right = address + size - 1;

27 // Interval starts before, but intersects with \|bitmap\|'s range.

28 if (right >= bitmap->base())

29 break;

30

31 // Interval is before entirely, for \|m_left\| to handle.

32 bitmap = bitmap->m_left.get();

33 }

34 return bitmap;

35 }

36

37 bool SparseHeapBitmap::isSet(Address address) {

38 DCHECK(!(reinterpret_cast<uintptr_t>(address) & s_pointerAlignmentMask));

39 SparseHeapBitmap* bitmap = this;

40 while (bitmap) {

41 if (address > bitmap->end()) {

42 bitmap = bitmap->m_right.get();

43 continue;

44 }

45 if (address >= bitmap->base()) {

46 if (bitmap->m_bitmap) {

47 return bitmap->m_bitmap->test((address - bitmap->base()) >>

48 s_pointerAlignmentInBits);

49 }

50 DCHECK(address == bitmap->base());

51 DCHECK_EQ(bitmap->size(), 1u);

52 return true;

53 }

54 bitmap = bitmap->m_left.get();

55 }

56 return false;

57 }

58

59 void SparseHeapBitmap::add(Address address) {

60 DCHECK(!(reinterpret_cast<uintptr_t>(address) & s_pointerAlignmentMask));

61 // \|address\| is beyond the maximum that this SparseHeapBitmap node can

62 // encompass.

63 if (address >= maxEnd()) {

64 if (!m_right) {

65 m_right = SparseHeapBitmap::create(address);

66 return;

67 }

68 m_right->add(address);

69 return;

70 }

71 // Same on the other side.

72 if (address < minStart()) {

73 if (!m_left) {

74 m_left = SparseHeapBitmap::create(address);

75 return;

76 }

77 m_left->add(address);

78 return;

79 }

80 if (address == base())

81 return;

82 // \|address\| can be encompassed by \|this\| by expanding its size.

83 if (address > base()) {

84 if (!m_bitmap)

85 createBitmap();

86 m_bitmap->set((address - base()) >> s_pointerAlignmentInBits);

87 return;

88 }

89 // Use \|address\| as the new base for this interval.

90 Address oldBase = swapBase(address);

91 createBitmap();

92 m_bitmap->set((oldBase - address) >> s_pointerAlignmentInBits);

93 }

94

95 void SparseHeapBitmap::createBitmap() {

96 DCHECK(!m_bitmap && size() == 1);

97 m_bitmap = WTF::makeUnique<std::bitset<s_bitmapChunkSize>>();

98 m_size = s_bitmapChunkRange;

99 m_bitmap->set(0);

100 }

101

102 size_t SparseHeapBitmap::intervalCount() const {

103 size_t count = 1;

104 if (m_left)

105 count += m_left->intervalCount();

106 if (m_right)

107 count += m_right->intervalCount();

108 return count;

109 }

110

111 } // namespace blink

OLD	NEW