1/*
2 * Copyright (C) 2017 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include <wtf/Atomics.h>
29#include <wtf/FastMalloc.h>
30#include <wtf/HashFunctions.h>
31#include <wtf/Lock.h>
32#include <wtf/Noncopyable.h>
33#include <wtf/Vector.h>
34
35namespace WTF {
36
37// This is a concurrent hash-based set for pointers. It's optimized for:
38//
39// - High rate of contains() calls.
40// - High rate of add() calls that don't add anything new. add() calls that don't add anything (nop adds)
41// don't mutate the table at all.
42// - Not too many threads. I doubt this scales beyond ~4. Though, it may actually scale better than that
43// if the rate of nop adds is absurdly high.
44//
45// If we wanted this to scale better, the main change we'd have to make is how this table determines when
46// to resize. Right now it's a shared counter. We lock;xadd this counter. One easy way to make that
47// scalable is to require each thread that works with the ConcurrentPtrHashSet to register itself first.
48// Then each thread would have some data structure that has a counter. We could institute the policy that
49// each thread simply increments its own load counter, in its own data structure. Then, if any search to
50// resolve a collision does more than N iterations, we can compute a combined load by summing the load
51// counters of all of the thread data structures.
52//
53// ConcurrentPtrHashSet's main user, the GC, sees a 98% nop add rate in Speedometer. That's why this
54// focuses so much on cases where the table does not change.
55class ConcurrentPtrHashSet {
56 WTF_MAKE_NONCOPYABLE(ConcurrentPtrHashSet);
57 WTF_MAKE_FAST_ALLOCATED;
58
59public:
60 WTF_EXPORT_PRIVATE ConcurrentPtrHashSet();
61 WTF_EXPORT_PRIVATE ~ConcurrentPtrHashSet();
62
63 template<typename T>
64 bool contains(T value)
65 {
66 return containsImpl(cast(value));
67 }
68
69 template<typename T>
70 bool add(T value)
71 {
72 return addImpl(cast(value));
73 }
74
75 size_t size() const
76 {
77 return m_table.loadRelaxed()->load.loadRelaxed();
78 }
79
80 // Only call when you know that no other thread can call add(). This frees up memory without changing
81 // the contents of the table.
82 WTF_EXPORT_PRIVATE void deleteOldTables();
83
84 // Only call when you know that no other thread can call add(). This frees up all memory except for
85 // the smallest possible hashtable.
86 WTF_EXPORT_PRIVATE void clear();
87
88private:
89 struct Table {
90 WTF_MAKE_STRUCT_FAST_ALLOCATED;
91
92 static std::unique_ptr<Table> create(unsigned size);
93
94 unsigned maxLoad() const { return size / 2; }
95
96 unsigned size; // This is immutable.
97 unsigned mask; // This is immutable.
98 Atomic<unsigned> load;
99 Atomic<void*> array[1];
100 };
101
102 static unsigned hash(void* ptr)
103 {
104 return PtrHash<void*>::hash(ptr);
105 }
106
107 void initialize();
108
109 template<typename T>
110 void* cast(T value)
111 {
112 static_assert(sizeof(T) <= sizeof(void*), "type too big");
113 union {
114 void* ptr;
115 T value;
116 } u;
117 u.ptr = nullptr;
118 u.value = value;
119 return u.ptr;
120 }
121
122 bool containsImpl(void* ptr) const
123 {
124 Table* table = m_table.loadRelaxed();
125 unsigned mask = table->mask;
126 unsigned startIndex = hash(ptr) & mask;
127 unsigned index = startIndex;
128 for (;;) {
129 void* entry = table->array[index].loadRelaxed();
130 if (!entry)
131 return false;
132 if (entry == ptr)
133 return true;
134 index = (index + 1) & mask;
135 RELEASE_ASSERT(index != startIndex);
136 }
137 }
138
139 // Returns true if a new entry was added.
140 bool addImpl(void* ptr)
141 {
142 Table* table = m_table.loadRelaxed();
143 unsigned mask = table->mask;
144 unsigned startIndex = hash(ptr) & mask;
145 unsigned index = startIndex;
146 for (;;) {
147 void* entry = table->array[index].loadRelaxed();
148 if (!entry)
149 return addSlow(table, mask, startIndex, index, ptr);
150 if (entry == ptr)
151 return false;
152 index = (index + 1) & mask;
153 RELEASE_ASSERT(index != startIndex);
154 }
155 }
156
157 WTF_EXPORT_PRIVATE bool addSlow(Table* table, unsigned mask, unsigned startIndex, unsigned index, void* ptr);
158
159 void resizeIfNecessary();
160 bool resizeAndAdd(void* ptr);
161
162 Vector<std::unique_ptr<Table>, 4> m_allTables;
163 Atomic<Table*> m_table; // This is never null.
164 Lock m_lock; // We just use this to control resize races.
165};
166
167} // namespace WTF
168
169using WTF::ConcurrentPtrHashSet;
170