1/*
2Copyright (c) 2012, Broadcom Europe Ltd
3All rights reserved.
4
5Redistribution and use in source and binary forms, with or without
6modification, are permitted provided that the following conditions are met:
7 * Redistributions of source code must retain the above copyright
8 notice, this list of conditions and the following disclaimer.
9 * 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 * Neither the name of the copyright holder nor the
13 names of its contributors may be used to endorse or promote products
14 derived from this software without specific prior written permission.
15
16THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY
20DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26*/
27
28#include "interface/khronos/common/khrn_int_common.h"
29
30#include "interface/khronos/common/khrn_client_cache.h"
31#include "interface/khronos/common/khrn_client_platform.h"
32#include "interface/khronos/common/khrn_client_rpc.h"
33
34#include "interface/khronos/common/khrn_int_hash.h"
35#include "interface/khronos/common/khrn_int_util.h"
36
37#ifdef RPC_DIRECT
38#include "interface/khronos/glxx/glxx_int_impl.h"
39#endif
40
41#include <assert.h>
42
43#if defined(SIMPENROSE)
44#include "tools/v3d/simpenrose/simpenrose.h"
45#endif
46
47static void link_insert(CACHE_LINK_T *link, CACHE_LINK_T *prev, CACHE_LINK_T *next)
48{
49 vcos_assert(prev->next == next);
50 vcos_assert(next->prev == prev);
51
52 link->prev = prev;
53 link->next = next;
54 prev->next = link;
55 next->prev = link;
56}
57
58static void link_remove(CACHE_LINK_T *link)
59{
60 link->next->prev = link->prev;
61 link->prev->next = link->next;
62}
63
64static void tree_init(uint8_t *tree, int depth)
65{
66 int i;
67
68 tree[0] = depth + 1;
69
70 for (i = 1; i < 1 << depth; i++)
71 tree[i] = tree[i >> 1] - 1;
72}
73
74static int heap_avail(KHRN_CACHE_T *cache, int size)
75{
76 return cache->tree && cache->tree[1] >= size;
77}
78
79static int heap_alloc(KHRN_CACHE_T *cache, int size)
80{
81 int node, fixup;
82 int i;
83
84 assert(heap_avail(cache, size));
85
86 node = 1;
87 for (i = 0; i < cache->client_depth - size; i++) {
88 node <<= 1;
89 if (cache->tree[node + 1] >= size && (cache->tree[node] < size || cache->tree[node] > cache->tree[node + 1]))
90 node++;
91 }
92
93 cache->tree[node] = 0;
94
95 for (fixup = node; cache->tree[fixup ^ 1] < cache->tree [fixup >> 1]; fixup >>= 1)
96 cache->tree[fixup >> 1] = _max(cache->tree[fixup], cache->tree[fixup ^ 1]);
97
98 return node * (1 << (size - 1)) - (1 << (cache->client_depth - 1));
99}
100
101static void heap_free(KHRN_CACHE_T *cache, int block)
102{
103 int node = block + (1 << (cache->client_depth - 1));
104 int reset = 1;
105
106 while (cache->tree[node] > 0) {
107 node >>= 1;
108 reset++;
109 }
110
111 cache->tree[node] = reset;
112
113 while (cache->tree[node] == cache->tree[node ^ 1]) {
114 node >>= 1;
115 cache->tree[node] = cache->tree[node] + 1;
116 }
117
118 while (cache->tree[node] > cache->tree[node >> 1]) {
119 cache->tree[node >> 1] = cache->tree[node];
120 node >>= 1;
121 }
122}
123
124static uint32_t hash(const void *data, int len, int sig)
125{
126 int hash;
127
128// if (len > 256) // TODO: turn this on later
129// len = 256;
130
131 if (!((size_t)data & 3) && !(len & 3))
132 hash = khrn_hashword((uint32_t *)data, len >> 2, 0);
133 else
134 hash = khrn_hashlittle(data, len, 0);
135
136 return (hash & ~0xf) | sig;
137}
138
139int khrn_cache_init(KHRN_CACHE_T *cache)
140{
141 cache->tree = NULL;
142 cache->data = NULL;
143
144 cache->client_depth = 0;
145 cache->server_depth = 0;
146
147 cache->start.prev = NULL;
148 cache->start.next = &cache->end;
149 cache->end.prev = &cache->start;
150 cache->end.next = NULL;
151
152 return khrn_pointer_map_init(&cache->map, 64);
153}
154
155void khrn_cache_term(KHRN_CACHE_T *cache)
156{
157 khrn_platform_free(cache->tree);
158 khrn_platform_free(cache->data);
159
160 khrn_pointer_map_term(&cache->map);
161}
162
163static void send_create(CLIENT_THREAD_STATE_T *thread, int base)
164{
165 RPC_CALL1(glintCacheCreate_impl,
166 thread,
167 GLINTCACHECREATE_ID,
168 RPC_UINT(base));
169}
170
171static void send_delete(CLIENT_THREAD_STATE_T *thread, int base)
172{
173 RPC_CALL1(glintCacheDelete_impl,
174 thread,
175 GLINTCACHEDELETE_ID,
176 RPC_UINT(base));
177}
178
179static int send_grow(CLIENT_THREAD_STATE_T *thread)
180{
181 return RPC_BOOLEAN_RES(RPC_CALL0_RES(glintCacheGrow_impl,
182 thread,
183 GLINTCACHEGROW_ID));
184}
185
186static void send_data(CLIENT_THREAD_STATE_T *thread, int base, const void *data, int len)
187{
188 int off = 0;
189
190 while (len > 0) {
191 int chunk = _min(len, MERGE_BUFFER_SIZE-CLIENT_MAKE_CURRENT_SIZE-12-8);
192
193 RPC_CALL3_IN_CTRL(glintCacheData_impl,
194 thread,
195 GLINTCACHEDATA_ID,
196 RPC_UINT(base + off),
197 RPC_SIZEI(chunk),
198 (char *)data + off,
199 chunk);
200
201 off += chunk;
202 len -= chunk;
203 }
204}
205
206static void discard(CLIENT_THREAD_STATE_T *thread, KHRN_CACHE_T *cache, CACHE_ENTRY_T *entry)
207{
208 heap_free(cache, (int)((uint8_t *)entry - cache->data) >> CACHE_LOG2_BLOCK_SIZE);
209
210 khrn_pointer_map_delete(&cache->map, entry->key);
211
212 link_remove(&entry->link);
213
214 send_delete(thread, (int)((uint8_t *)entry - cache->data));
215}
216
217static void *relocate(void *data, void *user)
218{
219 return (uint8_t *)data - ((uint8_t **)user)[0] + ((uint8_t **)user)[1];
220}
221
222static void callback(KHRN_POINTER_MAP_T *map, uint32_t key, void *value, void *user)
223{
224 CACHE_ENTRY_T *entry = (CACHE_ENTRY_T *)value;
225
226 entry->link.prev = (CACHE_LINK_T *)relocate(entry->link.prev, user);
227 entry->link.next = (CACHE_LINK_T *)relocate(entry->link.next, user);
228
229 // Coverity has rightly pointed out that the allocations done in the next codeline can fail
230 // verify will only assert the code in debug mode. Use in release mode stays the same as before...
231 verify(khrn_pointer_map_insert(map, key, relocate(value, user)));
232}
233
234static int grow(CLIENT_THREAD_STATE_T *thread, KHRN_CACHE_T *cache)
235{
236 /*
237 try to grow the server cache
238 */
239
240 uint8_t *tree;
241 uint8_t *data;
242 int i;
243
244 if (cache->server_depth == cache->client_depth) {
245 if (cache->server_depth < CACHE_MAX_DEPTH && send_grow(thread))
246 cache->server_depth++;
247 else
248 return 0;
249 }
250
251 tree = (uint8_t *)khrn_platform_malloc(1 << (cache->client_depth + 1), "KHRN_CACHE_T.tree");
252 data = (uint8_t *)khrn_platform_malloc(1 << (cache->client_depth + CACHE_LOG2_BLOCK_SIZE), "KHRN_CACHE_T.data");
253
254 if (!tree || !data) {
255 khrn_platform_free(tree);
256 khrn_platform_free(data);
257 return 0;
258 }
259
260 /*
261 set up new tree structure
262 */
263
264 tree_init(tree, cache->client_depth + 1);
265
266 if (cache->client_depth) {
267 for (i = 1; i < 1 << cache->client_depth; i++)
268 tree[i ^ 3 << _msb(i)] = cache->tree[i];
269
270 tree[1] = tree[3] + (tree[2] == tree[3]);
271 }
272
273 /*
274 relocate pointermap and linked list pointers
275 */
276 {
277 uint8_t *user[2];
278 user[0] = cache->data;
279 user[1] = data;
280
281 khrn_pointer_map_iterate(&cache->map, callback, user);
282
283 cache->start.next->prev = &cache->start;
284 if (cache->start.next != &cache->end)
285 cache->start.next = (CACHE_LINK_T *)relocate(cache->start.next, user);
286
287 cache->end.prev->next = &cache->end;
288 if (cache->end.prev != &cache->start)
289 cache->end.prev = (CACHE_LINK_T *)relocate(cache->end.prev, user);
290 }
291
292 /*
293 set up new data block
294 */
295
296 if (cache->data)
297 platform_memcpy(data, cache->data, 1 << (cache->client_depth + CACHE_LOG2_BLOCK_SIZE - 1));
298
299 /*
300 free old blocks, update structure
301 */
302
303 khrn_platform_free(cache->tree);
304 khrn_platform_free(cache->data);
305
306 cache->tree = tree;
307 cache->data = data;
308
309 cache->client_depth++;
310
311 return 1;
312}
313
314#ifdef SIMPENROSE_RECORD_OUTPUT
315static bool xxx_first = true;
316#endif
317int khrn_cache_lookup(CLIENT_THREAD_STATE_T *thread, KHRN_CACHE_T *cache, const void *data, int len, int sig)
318{
319 int key = hash(data, len, sig);
320
321 CACHE_ENTRY_T *entry = (CACHE_ENTRY_T *)khrn_pointer_map_lookup(&cache->map, key);
322
323#ifdef SIMPENROSE_RECORD_OUTPUT
324 if (xxx_first)
325 {
326 /* Cannot grow cache while things are locked for recording. So grow it now as much as we think we'll need */
327 uint32_t i;
328 xxx_first = false;
329 for (i = 0; i < 15; i++)
330 grow(thread, cache);
331 }
332#endif
333
334 if (entry && entry->len >= len && !memcmp(entry->data, data, len)) {
335 /*
336 move link to end of discard queue
337 */
338
339 link_remove(&entry->link);
340 link_insert(&entry->link, cache->end.prev, &cache->end);
341 } else {
342 int size = _max(_msb(len + sizeof(CACHE_ENTRY_T) - 1) + 2 - CACHE_LOG2_BLOCK_SIZE, 1);
343 int block;
344
345 CACHE_LINK_T *link;
346
347 if (entry)
348 discard(thread, cache, entry);
349
350 while (!heap_avail(cache, size) && grow(thread, cache));
351
352 for (link = cache->start.next; link != &cache->end && !heap_avail(cache, size); link = link->next)
353 discard(thread, cache, (CACHE_ENTRY_T *)link);
354
355 if (!heap_avail(cache, size))
356 return -1;
357
358 block = heap_alloc(cache, size);
359
360 entry = (CACHE_ENTRY_T *)(cache->data + (block << CACHE_LOG2_BLOCK_SIZE));
361 entry->len = len;
362 entry->key = key;
363 platform_memcpy(entry->data, data, len);
364
365 if (!khrn_pointer_map_insert(&cache->map, key, entry)) {
366 heap_free(cache, block);
367 return -1;
368 }
369
370 link_insert(&entry->link, cache->end.prev, &cache->end);
371
372 send_create(thread, (int)((uint8_t *)entry - cache->data));
373 send_data(thread, (int)(entry->data - cache->data), data, len);
374 }
375
376 return (int)((uint8_t *)entry - cache->data);
377}
378
379int khrn_cache_get_entries(KHRN_CACHE_T *cache)
380{
381 return cache->map.entries;
382}
383