Skip to content
Navigation Menu
{{ message }}
forked from osm2pgsql-dev/osm2pgsql
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathnode-ram-cache.cpp
More file actions
456 lines (401 loc) · 17.4 KB
/
Copy pathnode-ram-cache.cpp
File metadata and controls
456 lines (401 loc) · 17.4 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
/* Implements a node cache in ram, for the middle layers to use.
* It uses two different storage methods, one optimized for dense
* nodes (with respect to id) and the other for sparse representations.
*/
#include "config.h"
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "osmtypes.hpp"
#include "middle.hpp"
#include "node-ram-cache.hpp"
#include "util.hpp"
/* Here we use a similar storage structure as middle-ram, except we allow
* the array to be lossy so we can cap the total memory usage. Hence it is a
* combination of a sparse array with a priority queue
*
* Like middle-ram we have a number of blocks all storing PER_BLOCK
* ramNodes. However, here we also track the number of nodes in each block.
* Seperately we have a priority queue like structure when maintains a list
* of all the used block so we can easily find the block with the least
* nodes. The cache has two phases:
*
* Phase 1: Loading initially, usedBlocks < maxBlocks. In this case when a
* new block is needed we simply allocate it and put it in
* queue[usedBlocks-1] which is the bottom of the tree. Every node added
* increases it's usage. When we move onto the next block we percolate this
* block up the queue until it reaches its correct position. The invariant
* is that the priority tree is complete except for this last node. We do
* not permit adding nodes to any other block to preserve this invariant.
*
* Phase 2: Once we've reached the maximum number of blocks permitted, we
* change so that the block currently be inserted into is at the top of the
* tree. When a new block is needed we take the one at the end of the queue,
* as it is the one with the least number of nodes in it. When we move onto
* the next block we first push the just completed block down to it's
* correct position in the queue and then reuse the block that now at the
* head.
*
* The result being that at any moment we have in memory the top maxBlock
* blocks in terms of number of nodes in memory. This should maximize the
* number of hits in lookups.
*
* Complexity:
* Insert node: O(1)
* Lookup node: O(1)
* Add new block: O(log usedBlocks)
* Reuse old block: O(log maxBlocks)
*/
#define BLOCK_SHIFT 10
#define PER_BLOCK (((osmid_t)1) << BLOCK_SHIFT)
#define NUM_BLOCKS (((osmid_t)1) << (36 - BLOCK_SHIFT))
#define SAFETY_MARGIN 1024*PER_BLOCK*sizeof(struct ramNode)
static int id2block(osmid_t id)
{
/* + NUM_BLOCKS/2 allows for negative IDs */
return (id >> BLOCK_SHIFT) + NUM_BLOCKS/2;
}
static int id2offset(osmid_t id)
{
return id & (PER_BLOCK-1);
}
static osmid_t block2id(int block, int offset)
{
return (((osmid_t) block - NUM_BLOCKS/2) << BLOCK_SHIFT) + (osmid_t) offset;
}
#define Swap(a,b) { struct ramNodeBlock * __tmp = a; a = b; b = __tmp; }
void node_ram_cache::percolate_up( int pos )
{
int i = pos;
while( i > 0 )
{
int parent = (i-1)>>1;
if( queue[i]->used < queue[parent]->used )
{
Swap( queue[i], queue[parent] )
i = parent;
}
else
break;
}
}
struct ramNode *node_ram_cache::next_chunk(size_t count, size_t size) {
if ( (allocStrategy & ALLOC_DENSE_CHUNK) == 0 ) {
static size_t pos = 0;
char *result;
pos += count * size;
result = blockCache + cacheSize - pos + SAFETY_MARGIN;
return (struct ramNode *)result;
} else {
return (struct ramNode *)calloc(PER_BLOCK, sizeof(struct ramNode));
}
}
int node_ram_cache::set_sparse(osmid_t id, double lat, double lon, struct keyval *tags) {
if ((sizeSparseTuples > maxSparseTuples) || ( cacheUsed > cacheSize)) {
if ((allocStrategy & ALLOC_LOSSY) > 0)
return 1;
else {
fprintf(stderr, "\nNode cache size is too small to fit all nodes. Please increase cache size\n");
util::exit_nicely();
}
}
sparseBlock[sizeSparseTuples].id = id;
#ifdef FIXED_POINT
sparseBlock[sizeSparseTuples].coord.lat = util::double_to_fix(lat, scale_);
sparseBlock[sizeSparseTuples].coord.lon = util::double_to_fix(lon, scale_);
#else
sparseBlock[sizeSparseTuples].coord.lat = lat;
sparseBlock[sizeSparseTuples].coord.lon = lon;
#endif
sizeSparseTuples++;
cacheUsed += sizeof(struct ramNodeID);
storedNodes++;
return 0;
}
int node_ram_cache::set_dense(osmid_t id, double lat, double lon, struct keyval *tags) {
int block = id2block(id);
int offset = id2offset(id);
int i = 0;
if (maxBlocks == 0) return 1;
if (!blocks[block].nodes) {
if (((allocStrategy & ALLOC_SPARSE) > 0) && ( usedBlocks < maxBlocks) && ( cacheUsed > cacheSize)) {
/* TODO: It is more memory efficient to drop nodes from the sparse node cache than from the dense node cache */
}
if ((usedBlocks < maxBlocks ) && (cacheUsed < cacheSize)) {
/* if usedBlocks > 0 then the previous block is used up. Need to correctly handle it. */
if ( usedBlocks > 0 ) {
/* If sparse allocation is also set, then check if the previous block has sufficient density
* to store it in dense representation. If not, push all elements of the block
* to the sparse node cache and reuse memory of the previous block for the current block */
if ( ((allocStrategy & ALLOC_SPARSE) == 0) ||
((queue[usedBlocks - 1]->used / (double)(1<< BLOCK_SHIFT)) >
(sizeof(struct ramNode) / (double)sizeof(struct ramNodeID)))) {
/* Block has reached the level to keep it in dense representation */
/* We've just finished with the previous block, so we need to percolate it up the queue to its correct position */
/* Upto log(usedBlocks) iterations */
percolate_up( usedBlocks-1 );
blocks[block].nodes = next_chunk(PER_BLOCK, sizeof(struct ramNode));
} else {
/* previous block was not dense enough, so push it into the sparse node cache instead */
for (i = 0; i < (1 << BLOCK_SHIFT); i++) {
if (queue[usedBlocks -1]->nodes[i].lat || queue[usedBlocks -1]->nodes[i].lon) {
set_sparse(block2id(queue[usedBlocks - 1]->block_offset,i),
#ifdef FIXED_POINT
util::fix_to_double(queue[usedBlocks -1]->nodes[i].lat, scale_),
util::fix_to_double(queue[usedBlocks -1]->nodes[i].lon, scale_),
#else
queue[usedBlocks -1]->nodes[i].lat,
queue[usedBlocks -1]->nodes[i].lon,
#endif
NULL);
}
}
/* reuse previous block, as it's content is now in the dense representation */
storedNodes -= queue[usedBlocks - 1]->used;
blocks[block].nodes = queue[usedBlocks - 1]->nodes;
blocks[queue[usedBlocks - 1]->block_offset].nodes = NULL;
memset( blocks[block].nodes, 0, PER_BLOCK * sizeof(struct ramNode) );
usedBlocks--;
cacheUsed -= PER_BLOCK * sizeof(struct ramNode);
}
} else {
blocks[block].nodes = next_chunk(PER_BLOCK, sizeof(struct ramNode));
}
blocks[block].used = 0;
blocks[block].block_offset = block;
if (!blocks[block].nodes) {
fprintf(stderr, "Error allocating nodes\n");
util::exit_nicely();
}
queue[usedBlocks] = &blocks[block];
usedBlocks++;
cacheUsed += PER_BLOCK * sizeof(struct ramNode);
/* If we've just used up the last possible block we enter the
* transition and we change the invariant. To do this we percolate
* the newly allocated block straight to the head */
if (( usedBlocks == maxBlocks ) || ( cacheUsed > cacheSize ))
percolate_up( usedBlocks-1 );
} else {
if ((allocStrategy & ALLOC_LOSSY) == 0) {
fprintf(stderr, "\nNode cache size is too small to fit all nodes. Please increase cache size\n");
util::exit_nicely();
}
/* We've reached the maximum number of blocks, so now we push the
* current head of the tree down to the right level to restore the
* priority queue invariant. Upto log(maxBlocks) iterations */
i=0;
while( 2*i+1 < usedBlocks - 1 ) {
if( queue[2*i+1]->used <= queue[2*i+2]->used ) {
if( queue[i]->used > queue[2*i+1]->used ) {
Swap( queue[i], queue[2*i+1] );
i = 2*i+1;
}
else
break;
} else {
if( queue[i]->used > queue[2*i+2]->used ) {
Swap( queue[i], queue[2*i+2] );
i = 2*i+2;
} else
break;
}
}
/* Now the head of the queue is the smallest, so it becomes our replacement candidate */
blocks[block].nodes = queue[0]->nodes;
blocks[block].used = 0;
memset( blocks[block].nodes, 0, PER_BLOCK * sizeof(struct ramNode) );
/* Clear old head block and point to new block */
storedNodes -= queue[0]->used;
queue[0]->nodes = NULL;
queue[0]->used = 0;
queue[0] = &blocks[block];
}
} else {
/* Insert into an existing block. We can't allow this in general or it
* will break the invariant. However, it will work fine if all the
* nodes come in numerical order, which is the common case */
int expectedpos;
if (( usedBlocks < maxBlocks ) && (cacheUsed < cacheSize))
expectedpos = usedBlocks-1;
else
expectedpos = 0;
if( queue[expectedpos] != &blocks[block] ) {
if (!warn_node_order) {
fprintf( stderr, "WARNING: Found Out of order node %" PRIdOSMID " (%d,%d) - this will impact the cache efficiency\n", id, block, offset );
warn_node_order++;
}
return 1;
}
}
#ifdef FIXED_POINT
blocks[block].nodes[offset].lat = util::double_to_fix(lat, scale_);
blocks[block].nodes[offset].lon = util::double_to_fix(lon, scale_);
#else
blocks[block].nodes[offset].lat = lat;
blocks[block].nodes[offset].lon = lon;
#endif
blocks[block].used++;
storedNodes++;
return 0;
}
int node_ram_cache::get_sparse(struct osmNode *out, osmid_t id) {
int64_t pivotPos = sizeSparseTuples >> 1;
int64_t minPos = 0;
int64_t maxPos = sizeSparseTuples;
while (minPos <= maxPos) {
if ( sparseBlock[pivotPos].id == id ) {
#ifdef FIXED_POINT
out->lat = util::fix_to_double(sparseBlock[pivotPos].coord.lat, scale_);
out->lon = util::fix_to_double(sparseBlock[pivotPos].coord.lon, scale_);
#else
out->lat = sparseBlock[pivotPos].coord.lat;
out->lon = sparseBlock[pivotPos].coord.lon;
#endif
return 0;
}
if ( (pivotPos == minPos) || (pivotPos == maxPos)) return 1;
if ( sparseBlock[pivotPos].id > id ) {
maxPos = pivotPos;
pivotPos = minPos + ((maxPos - minPos) >> 1);
} else {
minPos = pivotPos;
pivotPos = minPos + ((maxPos - minPos) >> 1);
}
}
return 1;
}
int node_ram_cache::get_dense(struct osmNode *out, osmid_t id) {
int block = id2block(id);
int offset = id2offset(id);
if (!blocks[block].nodes)
return 1;
if (!blocks[block].nodes[offset].lat && !blocks[block].nodes[offset].lon)
return 1;
#ifdef FIXED_POINT
out->lat = util::fix_to_double(blocks[block].nodes[offset].lat, scale_);
out->lon = util::fix_to_double(blocks[block].nodes[offset].lon, scale_);
#else
out->lat = blocks[block].nodes[offset].lat;
out->lon = blocks[block].nodes[offset].lon;
#endif
return 0;
}
node_ram_cache::node_ram_cache( int strategy, int cacheSizeMB, int fixpointscale )
: allocStrategy(ALLOC_DENSE), blocks(NULL), usedBlocks(0),
maxBlocks(0), blockCache(NULL), queue(NULL), scale_(fixpointscale), sparseBlock(NULL),
maxSparseTuples(0), sizeSparseTuples(0), cacheUsed(0),
cacheSize(0), storedNodes(0), totalNodes(0), nodesCacheHits(0),
nodesCacheLookups(0), warn_node_order(0) {
blockCache = 0;
cacheUsed = 0;
cacheSize = (int64_t)cacheSizeMB*(1024*1024);
/* How much we can fit, and make sure it's odd */
maxBlocks = (cacheSize/(PER_BLOCK*sizeof(struct ramNode)));
maxSparseTuples = (cacheSize/sizeof(struct ramNodeID))+1;
allocStrategy = strategy;
if ((allocStrategy & ALLOC_DENSE) > 0 ) {
fprintf(stderr, "Allocating memory for dense node cache\n");
blocks = (struct ramNodeBlock *)calloc(NUM_BLOCKS,sizeof(struct ramNodeBlock));
if (!blocks) {
fprintf(stderr, "Out of memory for node cache dense index, try using \"--cache-strategy sparse\" instead \n");
util::exit_nicely();
}
queue = (struct ramNodeBlock **)calloc( maxBlocks,sizeof(struct ramNodeBlock *) );
/* Use this method of allocation if virtual memory is limited,
* or if OS allocs physical memory right away, rather than page by page
* once it is needed.
*/
if( (allocStrategy & ALLOC_DENSE_CHUNK) > 0 ) {
fprintf(stderr, "Allocating dense node cache in block sized chunks\n");
if (!queue) {
fprintf(stderr, "Out of memory, reduce --cache size\n");
util::exit_nicely();
}
} else {
fprintf(stderr, "Allocating dense node cache in one big chunk\n");
blockCache = (char *)calloc(maxBlocks + 1024,PER_BLOCK * sizeof(struct ramNode));
if (!queue || !blockCache) {
fprintf(stderr, "Out of memory for dense node cache, reduce --cache size\n");
util::exit_nicely();
}
}
}
/* Allocate the full amount of memory given by --cache parameter in one go.
* If both dense and sparse cache alloc is set, this will allocate up to twice
* as much virtual memory as specified by --cache. This relies on the OS doing
* lazy allocation of physical RAM. Extra accounting during setting of nodes is done
* to ensure physical RAM usage should roughly be no more than --cache
*/
if ((allocStrategy & ALLOC_SPARSE) > 0 ) {
fprintf(stderr, "Allocating memory for sparse node cache\n");
if (!blockCache) {
sparseBlock = (struct ramNodeID *)calloc(maxSparseTuples,sizeof(struct ramNodeID));
} else {
fprintf(stderr, "Sharing dense sparse\n");
sparseBlock = (struct ramNodeID *)blockCache;
}
if (!sparseBlock) {
fprintf(stderr, "Out of memory for sparse node cache, reduce --cache size\n");
util::exit_nicely();
}
}
#ifdef __MINGW_H
fprintf( stderr, "Node-cache: cache=%ldMB, maxblocks=%d*%d, allocation method=%i\n", (cacheSize >> 20), maxBlocks, PER_BLOCK*sizeof(struct ramNode), allocStrategy );
#else
fprintf( stderr, "Node-cache: cache=%ldMB, maxblocks=%d*%zd, allocation method=%i\n", (cacheSize >> 20), maxBlocks, PER_BLOCK*sizeof(struct ramNode), allocStrategy );
#endif
}
node_ram_cache::~node_ram_cache() {
int i;
fprintf( stderr, "node cache: stored: %" PRIdOSMID "(%.2f%%), storage efficiency: %.2f%% (dense blocks: %i, sparse nodes: %li), hit rate: %.2f%%\n",
storedNodes, 100.0f*storedNodes/totalNodes, 100.0f*storedNodes*sizeof(struct ramNode)/cacheUsed,
usedBlocks, sizeSparseTuples,
100.0f*nodesCacheHits/nodesCacheLookups );
if ( (allocStrategy & ALLOC_DENSE) > 0 ) {
if ( (allocStrategy & ALLOC_DENSE_CHUNK) > 0 ) {
for( i=0; i<usedBlocks; i++ ) {
free(queue[i]->nodes);
queue[i]->nodes = NULL;
}
} else {
free(blockCache);
blockCache = 0;
}
free(blocks);
free(queue);
}
if ( ((allocStrategy & ALLOC_SPARSE) > 0) && ((allocStrategy & ALLOC_DENSE) == 0)) {
free(sparseBlock);
}
}
int node_ram_cache::set(osmid_t id, double lat, double lon, struct keyval *tags) {
totalNodes++;
/* if ALLOC_DENSE and ALLOC_SPARSE are set, send it through
* ram_nodes_set_dense. If a block is non dense, it will automatically
* get pushed to the sparse cache if a block is sparse and ALLOC_SPARSE is set
*/
if ( (allocStrategy & ALLOC_DENSE) > 0 ) {
return set_dense(id, lat, lon, tags);
}
if ( (allocStrategy & ALLOC_SPARSE) > 0 )
return set_sparse(id, lat, lon, tags);
return 1;
}
int node_ram_cache::get(struct osmNode *out, osmid_t id) {
nodesCacheLookups++;
if ((allocStrategy & ALLOC_DENSE) > 0) {
if (get_dense(out,id) == 0) {
nodesCacheHits++;
return 0;
}
}
if ((allocStrategy & ALLOC_SPARSE) > 0) {
if (get_sparse(out,id) == 0) {
nodesCacheHits++;
return 0;
}
}
return 1;
}
You can’t perform that action at this time.