GC constraint solving should be parallel
[WebKit-https.git] / Source / WTF / wtf / ConcurrentPtrHashSet.h
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
35 namespace 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.
55 class ConcurrentPtrHashSet {
56     WTF_MAKE_NONCOPYABLE(ConcurrentPtrHashSet);
57     WTF_MAKE_FAST_ALLOCATED;
58
59 public:
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     
88 private:
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
169 using WTF::ConcurrentPtrHashSet;