1 |
#ifndef lint |
2 |
static const char RCSid[] = "$Id$"; |
3 |
#endif |
4 |
|
5 |
|
6 |
/* |
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 |
$Id: ooccache.c,v 2.1 2016/05/17 17:39:47 rschregle Exp $ |
26 |
*/ |
27 |
|
28 |
|
29 |
#if !defined(_WIN32) && !defined(_WIN64) || defined(PMAP_OOC) |
30 |
/* No Windoze support for now */ |
31 |
|
32 |
#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 |
|
432 |
#endif /* NIX / PMAP_OOC */ |