1 // Copyright 2022 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef PARTITION_ALLOC_FREESLOT_BITMAP_H_
6 #define PARTITION_ALLOC_FREESLOT_BITMAP_H_
7
8 #include <climits>
9 #include <cstdint>
10 #include <utility>
11
12 #include "partition_alloc/freeslot_bitmap_constants.h"
13 #include "partition_alloc/partition_alloc_base/bits.h"
14 #include "partition_alloc/partition_alloc_base/compiler_specific.h"
15 #include "partition_alloc/partition_alloc_buildflags.h"
16 #include "partition_alloc/partition_alloc_constants.h"
17
18 #if BUILDFLAG(USE_FREESLOT_BITMAP)
19
20 namespace partition_alloc::internal {
21
GetFreeSlotBitmapAddressForPointer(uintptr_t ptr)22 PA_ALWAYS_INLINE uintptr_t GetFreeSlotBitmapAddressForPointer(uintptr_t ptr) {
23 uintptr_t super_page = ptr & kSuperPageBaseMask;
24 return SuperPageFreeSlotBitmapAddr(super_page);
25 }
26
27 // Calculates the cell address and the offset inside the cell corresponding to
28 // the |slot_start|.
29 PA_ALWAYS_INLINE std::pair<FreeSlotBitmapCellType*, size_t>
GetFreeSlotBitmapCellPtrAndBitIndex(uintptr_t slot_start)30 GetFreeSlotBitmapCellPtrAndBitIndex(uintptr_t slot_start) {
31 uintptr_t slot_superpage_offset = slot_start & kSuperPageOffsetMask;
32 uintptr_t superpage_bitmap_start =
33 GetFreeSlotBitmapAddressForPointer(slot_start);
34 uintptr_t cell_addr = base::bits::AlignDown(
35 superpage_bitmap_start +
36 (slot_superpage_offset / kSmallestBucket) / CHAR_BIT,
37 sizeof(FreeSlotBitmapCellType));
38 PA_DCHECK(cell_addr < superpage_bitmap_start + kFreeSlotBitmapSize);
39 size_t bit_index =
40 (slot_superpage_offset / kSmallestBucket) & kFreeSlotBitmapOffsetMask;
41 PA_DCHECK(bit_index < kFreeSlotBitmapBitsPerCell);
42 return {reinterpret_cast<FreeSlotBitmapCellType*>(cell_addr), bit_index};
43 }
44
45 // This bitmap marks the used slot as 0 and free one as 1. This is because we
46 // would like to set all the slots as "used" by default to prevent allocating a
47 // used slot when the freelist entry is overwritten. The state of the bitmap is
48 // expected to be synced with freelist (i.e. the bitmap is set to 1 if and only
49 // if the slot is in the freelist).
50
CellWithAOne(size_t n)51 PA_ALWAYS_INLINE FreeSlotBitmapCellType CellWithAOne(size_t n) {
52 return static_cast<FreeSlotBitmapCellType>(1) << n;
53 }
54
CellWithTrailingOnes(size_t n)55 PA_ALWAYS_INLINE FreeSlotBitmapCellType CellWithTrailingOnes(size_t n) {
56 return (static_cast<FreeSlotBitmapCellType>(1) << n) -
57 static_cast<FreeSlotBitmapCellType>(1);
58 }
59
60 // Returns true if the bit corresponding to |slot_start| is used( = 0)
FreeSlotBitmapSlotIsUsed(uintptr_t slot_start)61 PA_ALWAYS_INLINE bool FreeSlotBitmapSlotIsUsed(uintptr_t slot_start) {
62 auto [cell, bit_index] = GetFreeSlotBitmapCellPtrAndBitIndex(slot_start);
63 return (*cell & CellWithAOne(bit_index)) == 0;
64 }
65
66 // Mark the bit corresponding to |slot_start| as used( = 0).
FreeSlotBitmapMarkSlotAsUsed(uintptr_t slot_start)67 PA_ALWAYS_INLINE void FreeSlotBitmapMarkSlotAsUsed(uintptr_t slot_start) {
68 PA_CHECK(!FreeSlotBitmapSlotIsUsed(slot_start));
69 auto [cell, bit_index] = GetFreeSlotBitmapCellPtrAndBitIndex(slot_start);
70 *cell &= ~CellWithAOne(bit_index);
71 }
72
73 // Mark the bit corresponding to |slot_start| as free( = 1).
FreeSlotBitmapMarkSlotAsFree(uintptr_t slot_start)74 PA_ALWAYS_INLINE void FreeSlotBitmapMarkSlotAsFree(uintptr_t slot_start) {
75 PA_CHECK(FreeSlotBitmapSlotIsUsed(slot_start));
76 auto [cell, bit_index] = GetFreeSlotBitmapCellPtrAndBitIndex(slot_start);
77 *cell |= CellWithAOne(bit_index);
78 }
79
80 // Resets (= set to 0) all the bits corresponding to the slot-start addresses
81 // within [begin_addr, end_addr). |begin_addr| has to be the beginning of a
82 // slot, but |end_addr| does not.
FreeSlotBitmapReset(uintptr_t begin_addr,uintptr_t end_addr,uintptr_t slot_size)83 PA_ALWAYS_INLINE void FreeSlotBitmapReset(uintptr_t begin_addr,
84 uintptr_t end_addr,
85 uintptr_t slot_size) {
86 PA_DCHECK(begin_addr <= end_addr);
87 // |end_addr| has to be kSmallestBucket-aligned.
88 PA_DCHECK((end_addr & (kSmallestBucket - 1)) == 0u);
89 for (uintptr_t slot_start = begin_addr; slot_start < end_addr;
90 slot_start += slot_size) {
91 auto [cell, bit_index] = GetFreeSlotBitmapCellPtrAndBitIndex(slot_start);
92 *cell &= ~CellWithAOne(bit_index);
93 }
94
95 #if BUILDFLAG(PA_DCHECK_IS_ON)
96 // Checks if the cells that are meant to contain only unset bits are really 0.
97 auto [begin_cell, begin_bit_index] =
98 GetFreeSlotBitmapCellPtrAndBitIndex(begin_addr);
99 auto [end_cell, end_bit_index] =
100 GetFreeSlotBitmapCellPtrAndBitIndex(end_addr);
101
102 // The bits that should be marked to 0 are |begin_bit_index|th bit of
103 // |begin_cell| to |end_bit_index - 1|th bit of |end_cell|. We verify all the
104 // bits are set to 0 for the cells between [begin_cell + 1, end_cell). For the
105 // |begin_cell| and |end_cell|, we have to handle them separately to only
106 // check the partial bits.
107 // | begin_cell | |...| | end_cell |
108 // |11...100...0|0...0|...|0...0|0...01...1|
109 // ^ ^
110 // | |
111 // begin_addr end_addr
112
113 if (begin_cell == end_cell) {
114 PA_DCHECK((*begin_cell & (~CellWithTrailingOnes(begin_bit_index) &
115 CellWithTrailingOnes(end_bit_index))) == 0u);
116 return;
117 }
118
119 if (begin_bit_index != 0) {
120 // Checks the bits between [begin_bit_index, kFreeSlotBitmapBitsPerCell) in
121 // the begin_cell are 0
122 PA_DCHECK((*begin_cell & ~CellWithTrailingOnes(begin_bit_index)) == 0u);
123 ++begin_cell;
124 }
125
126 if (end_bit_index != 0) {
127 // Checks the bits between [0, end_bit_index) in the end_cell are 0
128 PA_DCHECK((*end_cell & CellWithTrailingOnes(end_bit_index)) == 0u);
129 }
130
131 for (FreeSlotBitmapCellType* cell = begin_cell; cell < end_cell; ++cell) {
132 PA_DCHECK(*cell == 0u);
133 }
134 #endif // BUILDFLAG(PA_DCHECK_IS_ON)
135 }
136
137 } // namespace partition_alloc::internal
138
139 #endif // BUILDFLAG(USE_FREESLOT_BITMAP)
140
141 #endif // PARTITION_ALLOC_FREESLOT_BITMAP_H_
142