1/*
2 * Copyright (C) 2010-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. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "SharedStringHashStore.h"
28
29#include <algorithm>
30
31namespace WebKit {
32
33using namespace WebCore;
34
35const unsigned sharedStringHashTableMaxLoad = 2;
36
37static unsigned nextPowerOf2(unsigned v)
38{
39 // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
40 // Devised by Sean Anderson, Sepember 14, 2001
41
42 v--;
43 v |= v >> 1;
44 v |= v >> 2;
45 v |= v >> 4;
46 v |= v >> 8;
47 v |= v >> 16;
48 v++;
49
50 return v;
51}
52
53static unsigned tableSizeForKeyCount(unsigned keyCount)
54{
55 // We want the table to be at least half empty.
56 unsigned tableSize = nextPowerOf2(keyCount * sharedStringHashTableMaxLoad);
57
58 // Ensure that the table size is at least the size of a page.
59 size_t minimumTableSize = SharedMemory::systemPageSize() / sizeof(SharedStringHash);
60 if (tableSize < minimumTableSize)
61 return minimumTableSize;
62
63 return tableSize;
64}
65
66SharedStringHashStore::SharedStringHashStore(Client& client)
67 : m_client(client)
68 , m_pendingOperationsTimer(RunLoop::main(), this, &SharedStringHashStore::processPendingOperations)
69{
70}
71
72bool SharedStringHashStore::createSharedMemoryHandle(SharedMemory::Handle& handle)
73{
74 return m_table.sharedMemory()->createHandle(handle, SharedMemory::Protection::ReadOnly);
75}
76
77void SharedStringHashStore::scheduleAddition(SharedStringHash sharedStringHash)
78{
79 m_pendingOperations.append({ Operation::Add, sharedStringHash });
80
81 if (!m_pendingOperationsTimer.isActive())
82 m_pendingOperationsTimer.startOneShot(0_s);
83}
84
85void SharedStringHashStore::scheduleRemoval(WebCore::SharedStringHash sharedStringHash)
86{
87 m_pendingOperations.append({ Operation::Remove, sharedStringHash });
88
89 if (!m_pendingOperationsTimer.isActive())
90 m_pendingOperationsTimer.startOneShot(0_s);
91}
92
93bool SharedStringHashStore::contains(WebCore::SharedStringHash sharedStringHash)
94{
95 flushPendingChanges();
96 return m_table.contains(sharedStringHash);
97}
98
99void SharedStringHashStore::clear()
100{
101 m_pendingOperationsTimer.stop();
102 m_pendingOperations.clear();
103 m_keyCount = 0;
104 m_tableSize = 0;
105 m_table.clear();
106}
107
108void SharedStringHashStore::flushPendingChanges()
109{
110 if (!m_pendingOperationsTimer.isActive())
111 return;
112
113 m_pendingOperationsTimer.stop();
114 processPendingOperations();
115}
116
117void SharedStringHashStore::resizeTable(unsigned newTableSize)
118{
119 auto newTableMemory = SharedMemory::allocate(newTableSize * sizeof(SharedStringHash));
120 if (!newTableMemory) {
121 LOG_ERROR("Could not allocate shared memory for SharedStringHash table");
122 return;
123 }
124
125 memset(newTableMemory->data(), 0, newTableMemory->size());
126
127 RefPtr<SharedMemory> currentTableMemory = m_table.sharedMemory();
128 unsigned currentTableSize = m_tableSize;
129
130 m_table.setSharedMemory(newTableMemory.releaseNonNull());
131 m_tableSize = newTableSize;
132
133 if (currentTableMemory) {
134 ASSERT_UNUSED(currentTableSize, currentTableMemory->size() == currentTableSize * sizeof(SharedStringHash));
135
136 // Go through the current hash table and re-add all entries to the new hash table.
137 const SharedStringHash* currentSharedStringHashes = static_cast<const SharedStringHash*>(currentTableMemory->data());
138 for (unsigned i = 0; i < currentTableSize; ++i) {
139 auto sharedStringHash = currentSharedStringHashes[i];
140 if (!sharedStringHash)
141 continue;
142
143 bool didAddSharedStringHash = m_table.add(sharedStringHash);
144
145 // It should always be possible to add the SharedStringHash to a new table.
146 ASSERT_UNUSED(didAddSharedStringHash, didAddSharedStringHash);
147 }
148 }
149
150 for (auto& operation : m_pendingOperations) {
151 switch (operation.type) {
152 case Operation::Add:
153 if (m_table.add(operation.sharedStringHash))
154 ++m_keyCount;
155 break;
156 case Operation::Remove:
157 if (m_table.remove(operation.sharedStringHash))
158 --m_keyCount;
159 break;
160 }
161 }
162 m_pendingOperations.clear();
163
164 m_client.didInvalidateSharedMemory();
165}
166
167void SharedStringHashStore::processPendingOperations()
168{
169 unsigned currentTableSize = m_tableSize;
170 unsigned approximateNewHashCount = std::count_if(m_pendingOperations.begin(), m_pendingOperations.end(), [](auto& operation) {
171 return operation.type == Operation::Add;
172 });
173 // FIXME: The table can currently only grow. We should probably support shrinking it to save memory.
174 unsigned newTableSize = tableSizeForKeyCount(m_keyCount + approximateNewHashCount);
175
176 newTableSize = std::max(currentTableSize, newTableSize);
177
178 if (currentTableSize != newTableSize) {
179 resizeTable(newTableSize);
180 return;
181 }
182
183 Vector<SharedStringHash> addedSharedStringHashes;
184 Vector<SharedStringHash> removedSharedStringHashes;
185 addedSharedStringHashes.reserveInitialCapacity(approximateNewHashCount);
186 removedSharedStringHashes.reserveInitialCapacity(m_pendingOperations.size() - approximateNewHashCount);
187 for (auto& operation : m_pendingOperations) {
188 switch (operation.type) {
189 case Operation::Add:
190 if (m_table.add(operation.sharedStringHash)) {
191 addedSharedStringHashes.uncheckedAppend(operation.sharedStringHash);
192 ++m_keyCount;
193 }
194 break;
195 case Operation::Remove:
196 if (m_table.remove(operation.sharedStringHash)) {
197 removedSharedStringHashes.uncheckedAppend(operation.sharedStringHash);
198 --m_keyCount;
199 }
200 break;
201 }
202 }
203
204 m_pendingOperations.clear();
205
206 if (!addedSharedStringHashes.isEmpty() || !removedSharedStringHashes.isEmpty())
207 m_client.didUpdateSharedStringHashes(addedSharedStringHashes, removedSharedStringHashes);
208}
209
210} // namespace WebKit
211