1 |
rschregle |
2.2 |
#ifndef lint |
2 |
|
|
static const char RCSid[] = "$Id$"; |
3 |
|
|
#endif |
4 |
|
|
|
5 |
|
|
|
6 |
rschregle |
2.1 |
/* |
7 |
|
|
======================================================================= |
8 |
|
|
Cache for out-of-core octree. |
9 |
|
|
|
10 |
|
|
Uses an LRU page replacement scheme. Page table nodes are stored in |
11 |
|
|
order of reference in a doubly linked list, with the most recently used |
12 |
|
|
(MRU) page at the head, and the least recently used (LRU) at the tail. |
13 |
|
|
|
14 |
|
|
Nodes are referenced by the page's base address via a hashtable for |
15 |
|
|
constant time access (in the absence of hash collisions). Hash |
16 |
|
|
collisions can be limited by adjusting the hashtable load factor |
17 |
|
|
OOC_CACHE_LOAD; this is the fraction of the number of pages that will |
18 |
|
|
actually be cached. |
19 |
|
|
|
20 |
|
|
Roland Schregle (roland.schregle@{hslu.ch, gmail.com}) |
21 |
|
|
(c) Lucerne University of Applied Sciences and Arts, |
22 |
|
|
supported by the Swiss National Science Foundation (SNSF, #147053) |
23 |
|
|
======================================================================= |
24 |
|
|
|
25 |
rschregle |
2.2 |
$Id: ooccache.c,v 2.1 2016/05/17 17:39:47 rschregle Exp $ |
26 |
rschregle |
2.1 |
*/ |
27 |
|
|
|
28 |
|
|
|
29 |
rschregle |
2.2 |
#if !defined(_WIN32) && !defined(_WIN64) || defined(PMAP_OOC) |
30 |
|
|
/* No Windoze support for now */ |
31 |
|
|
|
32 |
rschregle |
2.1 |
#include <stdlib.h> |
33 |
|
|
#include <unistd.h> |
34 |
|
|
#include "ooccache.h" |
35 |
|
|
|
36 |
|
|
|
37 |
|
|
|
38 |
|
|
static OOC_CacheIdx OOC_PrevPrime (OOC_CacheIdx n) |
39 |
|
|
/* Return largest prime number <= n */ |
40 |
|
|
{ |
41 |
|
|
OOC_CacheIdx n2 = n + 1, i; |
42 |
|
|
|
43 |
|
|
do { |
44 |
|
|
n2--; |
45 |
|
|
for (i = 2; n2 % i && i <= n2 >> 1; i++); |
46 |
|
|
} while (!(n2 % i)); |
47 |
|
|
|
48 |
|
|
return n2; |
49 |
|
|
} |
50 |
|
|
|
51 |
|
|
|
52 |
|
|
|
53 |
|
|
int OOC_CacheInit (OOC_Cache *cache, unsigned numPages, |
54 |
|
|
unsigned recPerPage, unsigned recSize) |
55 |
|
|
{ |
56 |
|
|
OOC_CacheIdx i; |
57 |
|
|
|
58 |
|
|
if (!cache) |
59 |
|
|
return -1; |
60 |
|
|
|
61 |
|
|
/* Clamp number of pages if necessary */ |
62 |
|
|
if (numPages < OOC_CACHE_MINPAGES) { |
63 |
|
|
numPages = OOC_CACHE_MINPAGES; |
64 |
|
|
fputs("OOC_CacheInit: clamping num pages to min\n", stderr); |
65 |
|
|
} |
66 |
|
|
|
67 |
|
|
if (numPages >= OOC_CACHEIDX_NULL) { |
68 |
|
|
numPages = OOC_CACHEIDX_NULL - 1; |
69 |
|
|
fputs("OOC_CacheInit: clamping num pages to max\n", stderr); |
70 |
|
|
} |
71 |
|
|
|
72 |
|
|
/* Round numPages to next prime to reduce hash clustering & collisions */ |
73 |
|
|
numPages = OOC_PrevPrime(numPages); |
74 |
|
|
|
75 |
|
|
cache -> recPerPage = recPerPage; |
76 |
|
|
cache -> numPages = numPages; |
77 |
|
|
cache -> recSize = recSize; |
78 |
|
|
cache -> pageSize = (unsigned long)cache -> recPerPage * |
79 |
|
|
cache -> recSize; |
80 |
|
|
cache -> pageCnt = 0; |
81 |
|
|
cache -> numHits = cache -> numReads = cache -> numColl = |
82 |
|
|
cache -> numRept = 0; |
83 |
|
|
cache -> mru = cache -> lru = OOC_CACHEIDX_NULL; |
84 |
|
|
cache -> lastKey = 0; |
85 |
|
|
cache -> lastPage = NULL; |
86 |
|
|
|
87 |
|
|
/* Allocate & init hashtable */ |
88 |
|
|
if (!(cache -> pageTable = calloc(numPages, sizeof(OOC_CacheNode)))) { |
89 |
|
|
perror("OOC_InitCache: failed pagetable allocation"); |
90 |
|
|
return -1; |
91 |
|
|
} |
92 |
|
|
|
93 |
|
|
for (i = 0; i < numPages; i++) { |
94 |
|
|
cache -> pageTable [i].data = NULL; |
95 |
|
|
cache -> pageTable [i].key = 0; |
96 |
|
|
cache -> pageTable [i].prev = cache -> pageTable [i].next = |
97 |
|
|
OOC_CACHEIDX_NULL; |
98 |
|
|
} |
99 |
|
|
|
100 |
|
|
#ifdef OOC_CACHE_STATS |
101 |
|
|
fprintf(stderr, |
102 |
|
|
"OOC_InitCache: caching %d pages @ %d records (%.2f Mb)\n", |
103 |
|
|
cache -> numPages, cache -> recPerPage, |
104 |
|
|
(float)cache -> numPages * cache -> pageSize / (1L << 20)); |
105 |
|
|
#endif |
106 |
|
|
|
107 |
|
|
return 0; |
108 |
|
|
} |
109 |
|
|
|
110 |
|
|
|
111 |
|
|
|
112 |
|
|
static OOC_CacheIdx OOC_CacheFind (OOC_Cache *cache, OOC_CacheKey key) |
113 |
|
|
/* Return index to pagetable node for given key; collisions are resolved |
114 |
|
|
* via the probe sequence defined by OOC_CACHE_NEXT() */ |
115 |
|
|
{ |
116 |
|
|
OOC_CacheIdx idx = OOC_CACHE_HASH(key, cache -> numPages); |
117 |
|
|
OOC_CacheNode *page = cache -> pageTable + idx; |
118 |
|
|
|
119 |
|
|
/* Find matching pagetable node starting from idx and stop at the first |
120 |
|
|
* empty node; a full table would result in an infinite loop! */ |
121 |
|
|
while (page -> data && page -> key != key) { |
122 |
|
|
idx = OOC_CACHE_NEXT(idx, cache -> numPages); |
123 |
|
|
page = cache -> pageTable + idx; |
124 |
|
|
cache -> numColl++; |
125 |
|
|
} |
126 |
|
|
|
127 |
|
|
return idx; |
128 |
|
|
} |
129 |
|
|
|
130 |
|
|
|
131 |
|
|
|
132 |
|
|
static void OOC_CacheUnlink (OOC_Cache *cache, OOC_CacheIdx pageIdx) |
133 |
|
|
/* Unlink page from history chain, updating LRU in cache if necessary */ |
134 |
|
|
{ |
135 |
|
|
OOC_CacheNode *page = cache -> pageTable + pageIdx; |
136 |
|
|
|
137 |
|
|
/* Unlink prev/next index */ |
138 |
|
|
if (page -> prev != OOC_CACHEIDX_NULL) |
139 |
|
|
cache -> pageTable [page -> prev].next = page -> next; |
140 |
|
|
|
141 |
|
|
if (page -> next != OOC_CACHEIDX_NULL) |
142 |
|
|
cache -> pageTable [page -> next].prev = page -> prev; |
143 |
|
|
|
144 |
|
|
/* Update LRU index */ |
145 |
|
|
if (pageIdx == cache -> lru) |
146 |
|
|
cache -> lru = page -> prev; |
147 |
|
|
} |
148 |
|
|
|
149 |
|
|
|
150 |
|
|
|
151 |
|
|
static void OOC_CacheRelink (OOC_Cache *cache, OOC_CacheIdx pageIdx) |
152 |
|
|
/* Update history chain with new page index */ |
153 |
|
|
{ |
154 |
|
|
OOC_CacheNode *page = cache -> pageTable + pageIdx; |
155 |
|
|
|
156 |
|
|
if (page -> prev != OOC_CACHEIDX_NULL) |
157 |
|
|
cache -> pageTable [page -> prev].next = pageIdx; |
158 |
|
|
|
159 |
|
|
if (page -> next != OOC_CACHEIDX_NULL) |
160 |
|
|
cache -> pageTable [page -> next].prev = pageIdx; |
161 |
|
|
} |
162 |
|
|
|
163 |
|
|
|
164 |
|
|
|
165 |
|
|
static void OOC_CacheSetMRU (OOC_Cache *cache, OOC_CacheIdx pageIdx) |
166 |
|
|
/* Set page as most recently used and move to head of history chain */ |
167 |
|
|
{ |
168 |
|
|
OOC_CacheNode *page = cache -> pageTable + pageIdx; |
169 |
|
|
|
170 |
|
|
OOC_CacheUnlink(cache, pageIdx); |
171 |
|
|
page -> prev = OOC_CACHEIDX_NULL; |
172 |
|
|
page -> next = cache -> mru; |
173 |
|
|
cache -> pageTable [cache -> mru].prev = pageIdx; |
174 |
|
|
cache -> mru = pageIdx; |
175 |
|
|
} |
176 |
|
|
|
177 |
|
|
|
178 |
|
|
|
179 |
|
|
static void *OOC_CacheDelete (OOC_Cache *cache, OOC_CacheIdx pageIdx) |
180 |
|
|
/* Delete cache node at pageIdx and tidy up fragmentation in pagetable to |
181 |
|
|
* minimise collisions. Returns pointer to deleted node's page data |
182 |
|
|
* |
183 |
|
|
* !!! Note cache -> pageCnt is NOT decremented as this is immediately |
184 |
|
|
* !!! followed by a call to OOC_CacheNew() in OOC_CacheData() */ |
185 |
|
|
{ |
186 |
|
|
OOC_CacheNode *page = cache -> pageTable + pageIdx, *nextPage; |
187 |
|
|
OOC_CacheIdx nextIdx; |
188 |
|
|
void *delData = page -> data, *nextData; |
189 |
|
|
|
190 |
|
|
/* Unlink page from history chain */ |
191 |
|
|
OOC_CacheUnlink(cache, pageIdx); |
192 |
|
|
|
193 |
|
|
/* Free pagetable node */ |
194 |
|
|
page -> data = NULL; |
195 |
|
|
|
196 |
|
|
nextIdx = OOC_CACHE_NEXT(pageIdx, cache -> numPages); |
197 |
|
|
nextPage = cache -> pageTable + nextIdx; |
198 |
|
|
|
199 |
|
|
/* Close gaps in probe sequence until empty node found */ |
200 |
|
|
while ((nextData = nextPage -> data)) { |
201 |
|
|
/* Mark next node as free and reprobe for its key */ |
202 |
|
|
nextPage -> data = NULL; |
203 |
|
|
pageIdx = OOC_CacheFind(cache, nextPage -> key); |
204 |
|
|
page = cache -> pageTable + pageIdx; |
205 |
|
|
|
206 |
|
|
/* Set page data pointer & reactivate page */ |
207 |
|
|
page -> data = nextData; |
208 |
|
|
|
209 |
|
|
if (pageIdx != nextIdx) { |
210 |
|
|
/* Next page maps to freed node; relocate to close gap and update |
211 |
|
|
* history chain and LRU/MRU if necessary */ |
212 |
|
|
page -> key = nextPage -> key; /* memcpy() faster ? */ |
213 |
|
|
page -> prev = nextPage -> prev; |
214 |
|
|
page -> next = nextPage -> next; |
215 |
|
|
OOC_CacheRelink(cache, pageIdx); |
216 |
|
|
|
217 |
|
|
if (cache -> lru == nextIdx) |
218 |
|
|
cache -> lru = pageIdx; |
219 |
|
|
|
220 |
|
|
if (cache -> mru == nextIdx) |
221 |
|
|
cache -> mru = pageIdx; |
222 |
|
|
} |
223 |
|
|
|
224 |
|
|
nextIdx = OOC_CACHE_NEXT(nextIdx, cache -> numPages); |
225 |
|
|
nextPage = cache -> pageTable + nextIdx; |
226 |
|
|
} |
227 |
|
|
|
228 |
|
|
return delData; |
229 |
|
|
} |
230 |
|
|
|
231 |
|
|
|
232 |
|
|
|
233 |
|
|
static OOC_CacheNode *OOC_CacheNew (OOC_Cache *cache, OOC_CacheIdx pageIdx, |
234 |
|
|
OOC_CacheKey pageKey, void *pageData) |
235 |
|
|
/* Init new pagetable node with given index, key and data. Returns pointer |
236 |
|
|
* to new node */ |
237 |
|
|
{ |
238 |
|
|
OOC_CacheNode *page = cache -> pageTable + pageIdx; |
239 |
|
|
|
240 |
|
|
page -> prev = page -> next = OOC_CACHEIDX_NULL; |
241 |
|
|
page -> key = pageKey; |
242 |
|
|
page -> data = pageData; |
243 |
|
|
|
244 |
|
|
return page; |
245 |
|
|
} |
246 |
|
|
|
247 |
|
|
|
248 |
|
|
|
249 |
|
|
#ifdef OOC_CACHE_CHECK |
250 |
|
|
static int OOC_CacheCheck (OOC_Cache *cache) |
251 |
|
|
/* Run sanity checks on hashtable and page list */ |
252 |
|
|
{ |
253 |
|
|
OOC_CacheIdx i, pageCnt = 0; |
254 |
|
|
OOC_CacheNode *page; |
255 |
|
|
|
256 |
|
|
/* Check pagetable mapping */ |
257 |
|
|
for (i = 0, page = cache->pageTable; i < cache->numPages; i++, page++) |
258 |
|
|
if (page -> data) { |
259 |
|
|
/* Check hash func maps page key to this node */ |
260 |
|
|
if (OOC_CacheFind(cache, page -> key) != i) { |
261 |
|
|
fputs("OOC_CacheCheck: hashing inconsistency\n", stderr); |
262 |
|
|
return -1; |
263 |
|
|
} |
264 |
|
|
|
265 |
|
|
pageCnt++; |
266 |
|
|
} |
267 |
|
|
|
268 |
|
|
if (pageCnt != cache -> pageCnt) { |
269 |
|
|
fputs("OOC_CacheCheck: pagetable count inconsistency\n", stderr); |
270 |
|
|
return -1; |
271 |
|
|
} |
272 |
|
|
|
273 |
|
|
if (cache -> mru == OOC_CACHEIDX_NULL || |
274 |
|
|
cache -> lru == OOC_CACHEIDX_NULL) { |
275 |
|
|
fputs("OOC_CacheCheck: undefined MRU/LRU\n", stderr); |
276 |
|
|
return -1; |
277 |
|
|
} |
278 |
|
|
|
279 |
|
|
pageCnt = 0; |
280 |
|
|
i = cache -> mru; |
281 |
|
|
|
282 |
|
|
/* Check page history */ |
283 |
|
|
while (i != OOC_CACHEIDX_NULL) { |
284 |
|
|
/* Check link to previous page (should be none for MRU) */ |
285 |
|
|
page = cache -> pageTable + i; |
286 |
|
|
|
287 |
|
|
if (i == cache -> mru) |
288 |
|
|
if (page -> prev != OOC_CACHEIDX_NULL) { |
289 |
|
|
fputs("OOC_CacheCheck: MRU inconsistency\n", stderr); |
290 |
|
|
return -1; |
291 |
|
|
} |
292 |
|
|
else; |
293 |
|
|
else if (page -> prev == OOC_CACHEIDX_NULL || |
294 |
|
|
cache -> pageTable [page -> prev].next != i) { |
295 |
|
|
fputs("OOC_CacheCheck: prev page inconsistency\n", stderr); |
296 |
|
|
return -1; |
297 |
|
|
} |
298 |
|
|
|
299 |
|
|
/* Check link to next page node (should be none for LRU) */ |
300 |
|
|
if (i == cache -> lru) |
301 |
|
|
if (page -> next != OOC_CACHEIDX_NULL) { |
302 |
|
|
fputs("OOC_CacheCheck: LRU inconsistency\n", stderr); |
303 |
|
|
return -1; |
304 |
|
|
} |
305 |
|
|
else; |
306 |
|
|
else if (page -> next != OOC_CACHEIDX_NULL && |
307 |
|
|
cache -> pageTable [page -> next].prev != i) { |
308 |
|
|
fputs("OOC_CacheCheck: next page inconsistency\n", stderr); |
309 |
|
|
return -1; |
310 |
|
|
} |
311 |
|
|
|
312 |
|
|
/* Check LRU is at tail of page history */ |
313 |
|
|
if (page -> next == OOC_CACHEIDX_NULL && i != cache -> lru) { |
314 |
|
|
fputs("OOC_CacheCheck: page history tail not LRU\n", stderr); |
315 |
|
|
return -1; |
316 |
|
|
} |
317 |
|
|
|
318 |
|
|
i = page -> next; |
319 |
|
|
pageCnt++; |
320 |
|
|
} |
321 |
|
|
|
322 |
|
|
if (pageCnt != cache -> pageCnt) { |
323 |
|
|
fputs("OOC_CacheCheck: page history count inconsistency\n", stderr); |
324 |
|
|
return -1; |
325 |
|
|
} |
326 |
|
|
|
327 |
|
|
return 0; |
328 |
|
|
} |
329 |
|
|
#endif |
330 |
|
|
|
331 |
|
|
|
332 |
|
|
|
333 |
|
|
void *OOC_CacheData (OOC_Cache *cache, FILE *file, unsigned long recIdx) |
334 |
|
|
{ |
335 |
|
|
const OOC_CacheKey pageKey = recIdx / cache -> recPerPage; |
336 |
|
|
OOC_CacheNode *page = NULL; |
337 |
|
|
|
338 |
|
|
/* We assume locality of reference, and that it's likely the same page |
339 |
|
|
* will therefore be accessed sequentially; in this case we just reuse |
340 |
|
|
* the pagetable index */ |
341 |
|
|
if (pageKey != cache -> lastKey || !cache -> pageCnt) { |
342 |
|
|
OOC_CacheIdx pageIdx = OOC_CacheFind(cache, pageKey); |
343 |
|
|
void *pageData; |
344 |
|
|
|
345 |
|
|
page = cache -> pageTable + pageIdx; |
346 |
|
|
|
347 |
|
|
if (!page -> data) { |
348 |
|
|
/* Page not cached; insert in pagetable */ |
349 |
|
|
const unsigned long filePos = cache -> pageSize * pageKey; |
350 |
|
|
|
351 |
|
|
if (cache -> pageCnt < OOC_CACHE_LOAD * cache -> numPages) { |
352 |
|
|
/* Cache not fully loaded; allocate new page data */ |
353 |
|
|
if (!(pageData = calloc(cache -> recPerPage, cache -> recSize))) { |
354 |
|
|
perror("OOC_CacheData: failed page allocation"); |
355 |
|
|
return NULL; |
356 |
|
|
} |
357 |
|
|
|
358 |
|
|
/* Init LRU and MRU if necessary */ |
359 |
|
|
if (cache -> mru == OOC_CACHEIDX_NULL || |
360 |
|
|
cache -> lru == OOC_CACHEIDX_NULL) |
361 |
|
|
cache -> mru = cache -> lru = pageIdx; |
362 |
|
|
|
363 |
|
|
cache -> pageCnt++; |
364 |
|
|
} |
365 |
|
|
else { |
366 |
|
|
/* Cache fully loaded; adding more entries would aggravate |
367 |
|
|
* hash collisions, so evict LRU page. We reuse its |
368 |
|
|
* allocated page data and then overwrite it. */ |
369 |
|
|
pageData = OOC_CacheDelete(cache, cache -> lru); |
370 |
|
|
|
371 |
|
|
/* Update page index as it may have moved forward in probe |
372 |
|
|
* sequence after deletion */ |
373 |
|
|
pageIdx = OOC_CacheFind(cache, pageKey); |
374 |
|
|
} |
375 |
|
|
|
376 |
|
|
/* Init new pagetable node, will be linked in history below */ |
377 |
|
|
page = OOC_CacheNew(cache, pageIdx, pageKey, pageData); |
378 |
|
|
|
379 |
|
|
/* Load page data from file; the last page may be truncated */ |
380 |
|
|
if (!pread(fileno(file), page -> data, cache -> pageSize, filePos)) { |
381 |
|
|
fputs("OOC_CacheData: failed seek/read from data stream", stderr); |
382 |
|
|
return NULL; |
383 |
|
|
} |
384 |
|
|
} |
385 |
|
|
else |
386 |
|
|
/* Page in cache */ |
387 |
|
|
cache -> numHits++; |
388 |
|
|
|
389 |
|
|
if (cache -> mru != pageIdx) |
390 |
|
|
/* Cached page is now most recently used; unlink and move to front |
391 |
|
|
* of history chain and update MRU */ |
392 |
|
|
OOC_CacheSetMRU(cache, pageIdx); |
393 |
|
|
|
394 |
|
|
/* Update last page to detect repeat accesses */ |
395 |
|
|
cache -> lastKey = pageKey; |
396 |
|
|
cache -> lastPage = page; |
397 |
|
|
} |
398 |
|
|
else { |
399 |
|
|
/* Repeated page, skip hashing and just reuse last page */ |
400 |
|
|
page = cache -> lastPage; |
401 |
|
|
cache -> numHits++; |
402 |
|
|
cache -> numRept++; |
403 |
|
|
} |
404 |
|
|
|
405 |
|
|
cache -> numReads++; |
406 |
|
|
|
407 |
|
|
#ifdef OOC_CACHE_CHECK |
408 |
|
|
if (OOC_CacheCheck(cache)) |
409 |
|
|
return NULL; |
410 |
|
|
#endif |
411 |
|
|
|
412 |
|
|
/* Return pointer to record within cached page */ |
413 |
|
|
return page -> data + (recIdx % cache -> recPerPage) * cache -> recSize; |
414 |
|
|
} |
415 |
|
|
|
416 |
|
|
|
417 |
|
|
|
418 |
|
|
void OOC_DeleteCache (OOC_Cache *cache) |
419 |
|
|
{ |
420 |
|
|
OOC_CacheIdx i; |
421 |
|
|
|
422 |
|
|
for (i = 0; i < cache -> numPages; i++) |
423 |
|
|
if (cache -> pageTable [i].data) |
424 |
|
|
free(cache -> pageTable [i].data); |
425 |
|
|
|
426 |
|
|
free(cache -> pageTable); |
427 |
|
|
cache -> pageTable = NULL; |
428 |
|
|
cache -> pageCnt = 0; |
429 |
|
|
cache -> mru = cache -> lru = OOC_CACHEIDX_NULL; |
430 |
|
|
} |
431 |
rschregle |
2.2 |
|
432 |
|
|
#endif /* NIX / PMAP_OOC */ |