1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at https://mozilla.org/MPL/2.0/. */
#ifndef RADIX_TREE_H
#define RADIX_TREE_H
#include "mozilla/ThreadSafety.h"
#include "Constants.h"
#include "Utils.h"
#include "BaseAlloc.h"
#include "Mutex.h"
// ***************************************************************************
// Radix tree data structures.
//
// The number of bits passed to the template is the number of significant bits
// in an address to do a radix lookup with.
//
// An address is looked up by splitting it in kBitsPerLevel bit chunks, except
// the most significant bits, where the bit chunk is kBitsAtLevel1 which can be
// different if Bits is not a multiple of kBitsPerLevel.
//
// With e.g. sizeof(void*)=4, Bits=16 and kBitsPerLevel=8, an address is split
// like the following:
// 0x12345678 -> mRoot[0x12][0x34]
template <size_t Bits>
class AddressRadixTree {
// Size of each radix tree node (as a power of 2).
// This impacts tree depth.
#ifdef HAVE_64BIT_BUILD
static const size_t kNodeSize = kCacheLineSize;
#else
static const size_t kNodeSize = 16_KiB;
#endif
static const size_t kBitsPerLevel = LOG2(kNodeSize) - LOG2(sizeof(void*));
static const size_t kBitsAtLevel1 =
(Bits % kBitsPerLevel) ? Bits % kBitsPerLevel : kBitsPerLevel;
static const size_t kHeight = (Bits + kBitsPerLevel - 1) / kBitsPerLevel;
static_assert(kBitsAtLevel1 + (kHeight - 1) * kBitsPerLevel == Bits,
"AddressRadixTree parameters don't work out");
Mutex mLock MOZ_UNANNOTATED;
// We guard only the single slot creations and assume read-only is safe
// at any time.
void** mRoot = nullptr;
public:
// Note that the constructor does not initialise the mutex.
constexpr AddressRadixTree() {}
bool Init() MOZ_REQUIRES(gInitLock) MOZ_EXCLUDES(mLock);
inline void* Get(void* aAddr) MOZ_EXCLUDES(mLock);
// Returns whether the value was properly set.
inline bool Set(void* aAddr, void* aValue) MOZ_EXCLUDES(mLock);
inline bool Unset(void* aAddr) MOZ_EXCLUDES(mLock) {
return Set(aAddr, nullptr);
}
private:
// GetSlotInternal is agnostic wrt mLock and used directly only in DEBUG
// code.
inline void** GetSlotInternal(void* aAddr, bool aCreate);
inline void** GetSlotIfExists(void* aAddr) MOZ_EXCLUDES(mLock) {
return GetSlotInternal(aAddr, false);
}
inline void** GetOrCreateSlot(void* aAddr) MOZ_REQUIRES(mLock) {
return GetSlotInternal(aAddr, true);
}
};
template <size_t Bits>
bool AddressRadixTree<Bits>::Init() {
mLock.Init();
mRoot = (void**)sBaseAlloc.calloc(1 << kBitsAtLevel1, sizeof(void*));
return mRoot;
}
template <size_t Bits>
void** AddressRadixTree<Bits>::GetSlotInternal(void* aAddr, bool aCreate) {
uintptr_t key = reinterpret_cast<uintptr_t>(aAddr);
uintptr_t subkey;
unsigned i, lshift, height, bits;
void** node;
void** child;
for (i = lshift = 0, height = kHeight, node = mRoot; i < height - 1;
i++, lshift += bits, node = child) {
bits = i ? kBitsPerLevel : kBitsAtLevel1;
subkey = (key << lshift) >> ((sizeof(void*) << 3) - bits);
child = (void**)node[subkey];
if (!child && aCreate) {
child = (void**)sBaseAlloc.calloc(1 << kBitsPerLevel, sizeof(void*));
if (child) {
node[subkey] = child;
}
}
if (!child) {
return nullptr;
}
}
// node is a leaf, so it contains values rather than node
// pointers.
bits = i ? kBitsPerLevel : kBitsAtLevel1;
subkey = (key << lshift) >> ((sizeof(void*) << 3) - bits);
return &node[subkey];
}
template <size_t Bits>
void* AddressRadixTree<Bits>::Get(void* aAddr) {
void* ret = nullptr;
void** slot = GetSlotIfExists(aAddr);
if (slot) {
ret = *slot;
}
#ifdef MOZ_DEBUG
MutexAutoLock lock(mLock);
// Suppose that it were possible for a jemalloc-allocated chunk to be
// munmap()ped, followed by a different allocator in another thread re-using
// overlapping virtual memory, all without invalidating the cached rtree
// value. The result would be a false positive (the rtree would claim that
// jemalloc owns memory that it had actually discarded). I don't think this
// scenario is possible, but the following assertion is a prudent sanity
// check.
if (!slot) {
// In case a slot has been created in the meantime.
slot = GetSlotInternal(aAddr, false);
}
if (slot) {
// The MutexAutoLock above should act as a memory barrier, forcing
// the compiler to emit a new read instruction for *slot.
MOZ_ASSERT(ret == *slot);
} else {
MOZ_ASSERT(ret == nullptr);
}
#endif
return ret;
}
template <size_t Bits>
bool AddressRadixTree<Bits>::Set(void* aAddr, void* aValue) {
MutexAutoLock lock(mLock);
void** slot = GetOrCreateSlot(aAddr);
if (slot) {
*slot = aValue;
}
return slot;
}
#endif /* ! RADIX_TREE_H */
|
