1 /*
2 * Copyright (c) 2015-2017, Intel Corporation
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included
12 * in all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
15 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
17 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
18 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
19 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20 * OTHER DEALINGS IN THE SOFTWARE.
21 */
22 //!
23 //! \file cm_hal_hashtable.cpp
24 //! \brief This modules implements a simple coalesced hash table used
25 //! for kernel search in dynamic state heap based CmHal.
26 //! It exposes hash table initialization, destruction,
27 //! registration, unregistration and search functions used to
28 //! speed up kernel search. The hash table size is currently
29 //! limited to 65535 (MAX uint16_t-1), and 2 keys may be used
30 //! iKUID (Kernel Unique Identifier - int32_t) and
31 //! CacheID (Arbitrary Kernel Cache ID - int32_t).
32 //! Given the dynamic nature of the ISH and kernel allocation,
33 //! the hash table is allowed to grow dynamically as needed.
34 //!
35
36 #include "cm_hal_hashtable.h"
37
Init()38 MOS_STATUS CmHashTable::Init()
39 {
40 MOS_STATUS eStatus = MOS_STATUS_SUCCESS;
41 PCM_HAL_HASH_TABLE_ENTRY pHashEntry = nullptr;
42
43 pHashEntry = (PCM_HAL_HASH_TABLE_ENTRY)MOS_AllocMemory(CM_HAL_HASHTABLE_INITIAL * sizeof(CM_HAL_HASH_TABLE_ENTRY));
44 if (!pHashEntry)
45 {
46 eStatus = MOS_STATUS_NO_SPACE;
47 return eStatus;
48 }
49
50
51 m_hashTable.pHashEntries = pHashEntry;
52 m_hashTable.wSize = CM_HAL_HASHTABLE_INITIAL;
53 m_hashTable.wFree = 1; // First free element = 1 (0 is reserved for nullptr; 0xffff could be used instead, but 0 makes it cleaner/easier to read/understand)
54 for (int i = 0; i < CM_HAL_HASHTABLE_INITIAL - 1; i++, pHashEntry++)
55 {
56 pHashEntry->UniqID = -1;
57 pHashEntry->CacheID = -1;
58 pHashEntry->wNext = i + 1;
59 pHashEntry->pData = nullptr;
60 }
61 pHashEntry--;
62 pHashEntry->wNext = 0;
63
64 return eStatus;
65 }
66
Free()67 void CmHashTable::Free()
68 {
69 if (m_hashTable.pHashEntries) MOS_FreeMemory(m_hashTable.pHashEntries);
70 }
71
SimpleHash(int32_t value)72 uint16_t CmHashTable::SimpleHash(int32_t value)
73 {
74 uint16_t wHash = ((value >> 16) ^ value) & 0xFFFF;
75 wHash = ((wHash >> 8) ^ wHash) & 0xFF;
76 return wHash;
77 }
78
Extend()79 MOS_STATUS CmHashTable::Extend()
80 {
81 uint16_t wEntry;
82 PCM_HAL_HASH_TABLE_ENTRY pEntry;
83 int32_t iPrevSize, iNewSize;
84 MOS_STATUS hr = MOS_STATUS_UNKNOWN;
85
86 if (m_hashTable.wSize >= CM_HAL_HASHTABLE_MAX)
87 {
88 goto finish;
89 }
90
91 iPrevSize = m_hashTable.wSize * sizeof(CM_HAL_HASH_TABLE_ENTRY);
92 iNewSize = iPrevSize + CM_HAL_HASHTABLE_INCREMENT * sizeof(CM_HAL_HASH_TABLE_ENTRY);
93 pEntry = (PCM_HAL_HASH_TABLE_ENTRY)MOS_AllocMemory(iNewSize);
94 if (!pEntry)
95 {
96 hr = MOS_STATUS_NO_SPACE;
97 goto finish;
98 }
99
100 // Transfer the hash entries to larger table, free old (smaller) table
101 MOS_SecureMemcpy(pEntry, iPrevSize, m_hashTable.pHashEntries, iPrevSize);
102 MOS_FreeMemory(m_hashTable.pHashEntries);
103 m_hashTable.pHashEntries = pEntry;
104
105 // Initialize entries
106 wEntry = m_hashTable.wSize + 1;
107 pEntry += m_hashTable.wSize;
108 for (int i = CM_HAL_HASHTABLE_INCREMENT; i > 0; i--, wEntry++, pEntry++)
109 {
110 pEntry->UniqID = -1;
111 pEntry->CacheID = -1;
112 pEntry->wNext = wEntry;
113 pEntry->pData = nullptr;
114 }
115 pEntry--;
116
117 // Update free list - new array is appended at the beginning of the free list, avoiding the need to traverse it.
118 pEntry->wNext = m_hashTable.wFree; // Last entry of newly created entries points to first pre-existing free entry
119 m_hashTable.wFree = m_hashTable.wSize; // Free list points to newly created array, which points to pre-existing array
120 m_hashTable.wSize += CM_HAL_HASHTABLE_INCREMENT; // Update size of the hash table
121
122 hr = MOS_STATUS_SUCCESS;
123
124 finish:
125 return hr;
126 }
Register(int32_t UniqID,int32_t CacheID,void * pData)127 MOS_STATUS CmHashTable::Register(int32_t UniqID, int32_t CacheID, void *pData)
128 {
129 uint16_t wHash;
130 uint16_t wEntry;
131 PCM_HAL_HASH_TABLE_ENTRY pEntry;
132 MOS_STATUS hr = MOS_STATUS_UNKNOWN;
133
134 wHash = SimpleHash(UniqID);
135
136 // Get new entry
137 wEntry = m_hashTable.wFree;
138
139 // Extend hash table, get new free entry
140 if (wEntry == 0)
141 {
142 hr = Extend();
143 if (hr != MOS_STATUS_SUCCESS)
144 goto finish;
145 wEntry = m_hashTable.wFree;
146 }
147
148 // Remove entry from free list
149 pEntry = m_hashTable.pHashEntries + wEntry;
150 m_hashTable.wFree = pEntry->wNext;
151
152 // Link hash entry
153 pEntry->UniqID = UniqID; // save unique id
154 pEntry->CacheID = CacheID; // save unique id
155 pEntry->pData = pData; // save pointer to data
156 pEntry->wNext = m_hashTable.wHead[wHash]; // points to next entry in same bucket
157 m_hashTable.wHead[wHash] = wEntry; // move entry to head of the bucket
158
159 hr = MOS_STATUS_SUCCESS;
160
161 finish:
162 return hr;
163 }
164
Search(int32_t UniqID,int32_t CacheID,uint16_t & wSearchIndex)165 void* CmHashTable::Search(int32_t UniqID, int32_t CacheID, uint16_t &wSearchIndex)
166 {
167 PCM_HAL_HASH_TABLE_ENTRY pEntry = nullptr;
168 void *pData = nullptr;
169 bool bFound;
170
171 // Get first entry, or continue previous search
172 if (wSearchIndex == 0 ||
173 wSearchIndex >= m_hashTable.wSize)
174 {
175 uint16_t wHash = SimpleHash(UniqID);
176 wSearchIndex = m_hashTable.wHead[wHash];
177 }
178
179 if (CacheID >= 0)
180 {
181 // Search for UniqID/CacheID
182 for (bFound = false; (wSearchIndex > 0) && (!bFound); wSearchIndex = pEntry->wNext)
183 {
184 pEntry = m_hashTable.pHashEntries + wSearchIndex;
185 bFound = (pEntry->UniqID == UniqID) && (pEntry->CacheID == CacheID);
186 }
187 }
188 else
189 {
190 // Search for UniqID (don't care about CacheID)
191 for (bFound = false; (wSearchIndex > 0) && (!bFound); wSearchIndex = pEntry->wNext)
192 {
193 pEntry = m_hashTable.pHashEntries + wSearchIndex;
194 bFound = (pEntry->UniqID == UniqID);
195 }
196 }
197
198 // Retrieve user data
199 if (bFound)
200 {
201 pData = pEntry->pData;
202 }
203
204 return pData;
205 }
206
Unregister(int32_t UniqID,int32_t CacheID)207 void* CmHashTable::Unregister(int32_t UniqID, int32_t CacheID)
208 {
209 uint16_t wHash;
210 uint16_t wEntry = 0;
211 uint16_t wSearchIndex;
212 PCM_HAL_HASH_TABLE_ENTRY pEntry, pPrevEntry;
213 void *pData = nullptr;
214
215
216 wHash = SimpleHash(UniqID);
217
218 // Search for UniqID/CacheID (hashing should significantly speedup this search)
219 pEntry = pPrevEntry = nullptr;
220 wSearchIndex = m_hashTable.wHead[wHash];
221 bool bFound;
222
223 if (CacheID >= 0)
224 {
225 // Search for UniqID/CacheID
226 for (bFound = false; (wSearchIndex > 0) && (!bFound); wSearchIndex = pEntry->wNext)
227 {
228 wEntry = wSearchIndex;
229 pEntry = m_hashTable.pHashEntries + wSearchIndex;
230 bFound = (pEntry->UniqID == UniqID) && (pEntry->CacheID == CacheID);
231 }
232 }
233 else
234 {
235 // Search for UniqID (don't care about CacheID)
236 for (bFound = false; (wSearchIndex > 0) && (!bFound); wSearchIndex = pEntry->wNext)
237 {
238 wEntry = wSearchIndex;
239 pEntry = m_hashTable.pHashEntries + wSearchIndex;
240 bFound = (pEntry->UniqID == UniqID);
241 }
242 }
243
244 // Entry found
245 if (wEntry > 0)
246 {
247 // Detach from hash list
248 m_hashTable.wHead[wHash] = pEntry->wNext;
249
250 // Move hash entry to free list
251 pEntry->wNext = m_hashTable.wFree;
252 m_hashTable.wFree = wEntry;
253 pData = pEntry->pData;
254 }
255
256 return pData;
257 }
258