source: subversion/applications/utils/export/osm2pgsql/middle-ram.c @ 26711

Last change on this file since 26711 was 26027, checked in by jonb, 9 years ago

osm2pgsql-64: fix memory corruption with 64 bit IDs in non-slim mode

File size: 11.7 KB
Line 
1/* Implements the mid-layer processing for osm2pgsql
2 * using several arrays in RAM. This is fastest if you
3 * have sufficient RAM+Swap.
4 *
5 * This layer stores data read in from the planet.osm file
6 * and is then read by the backend processing code to
7 * emit the final geometry-enabled output formats
8*/
9
10#include <stdio.h>
11#include <unistd.h>
12#include <stdlib.h>
13#include <string.h>
14#include <assert.h>
15#include <libpq-fe.h>
16
17#include "osmtypes.h"
18#include "middle.h"
19#include "middle-ram.h"
20
21#include "output-pgsql.h"
22
23/* Store +-20,000km Mercator co-ordinates as fixed point 32bit number with maximum precision */
24/* Scale is chosen such that 40,000 * SCALE < 2^32          */
25#define FIXED_POINT
26
27static int scale = 100;
28#define DOUBLE_TO_FIX(x) ((x) * scale)
29#define FIX_TO_DOUBLE(x) (((double)x) / scale)
30
31struct ramNode {
32#ifdef FIXED_POINT
33    int lon;
34    int lat;
35#else
36    double lon;
37    double lat;
38#endif
39};
40
41struct ramWay {
42    struct keyval *tags;
43    osmid_t *ndids;
44    int pending;
45};
46
47struct ramRel {
48    struct keyval *tags;
49    struct member *members;
50    int member_count;
51};
52
53/* Object storage now uses 2 levels of storage arrays.
54 *
55 * - Low level storage of 2^16 (~65k) objects in an indexed array
56 *   These are allocated dynamically when we need to first store data with
57 *   an ID in this block
58 *
59 * - Fixed array of 2^(32 - 16) = 65k pointers to the dynamically allocated arrays.
60 *
61 * This allows memory usage to be efficient and scale dynamically without needing to
62 * hard code maximum IDs. We now support an ID  range of -2^31 to +2^31.
63 * The negative IDs often occur in non-uploaded JOSM data or other data import scripts.
64 *
65 */
66
67#define BLOCK_SHIFT 14
68#define PER_BLOCK  (1 << BLOCK_SHIFT)
69#define NUM_BLOCKS (1 << (32 - BLOCK_SHIFT))
70
71static struct ramNode    *nodes[NUM_BLOCKS];
72static struct ramWay     *ways[NUM_BLOCKS];
73static struct ramRel     *rels[NUM_BLOCKS];
74
75static int node_blocks;
76static int way_blocks;
77
78static int way_out_count;
79static int rel_out_count;
80
81static inline osmid_t id2block(osmid_t id)
82{
83    // + NUM_BLOCKS/2 allows for negative IDs
84    return (id >> BLOCK_SHIFT) + NUM_BLOCKS/2;
85}
86
87static inline osmid_t id2offset(osmid_t id)
88{
89    return id & (PER_BLOCK-1);
90}
91
92static inline int block2id(int block, int offset)
93{
94    return ((block - NUM_BLOCKS/2) << BLOCK_SHIFT) + offset;
95}
96
97#define UNUSED  __attribute__ ((unused))
98static int ram_nodes_set(osmid_t id, double lat, double lon, struct keyval *tags UNUSED)
99{
100    int block  = id2block(id);
101    int offset = id2offset(id);
102
103    if (!nodes[block]) {
104        nodes[block] = calloc(PER_BLOCK, sizeof(struct ramNode));
105        if (!nodes[block]) {
106            fprintf(stderr, "Error allocating nodes\n");
107            exit_nicely();
108        }
109        node_blocks++;
110        //fprintf(stderr, "\tnodes(%zuMb)\n", node_blocks * sizeof(struct ramNode) * PER_BLOCK / 1000000);
111    }
112
113#ifdef FIXED_POINT
114    nodes[block][offset].lat = DOUBLE_TO_FIX(lat);
115    nodes[block][offset].lon = DOUBLE_TO_FIX(lon);
116#else
117    nodes[block][offset].lat = lat;
118    nodes[block][offset].lon = lon;
119#endif
120    return 0;
121}
122
123
124static int ram_nodes_get(struct osmNode *out, osmid_t id)
125{
126    int block  = id2block(id);
127    int offset = id2offset(id);
128
129    if (!nodes[block])
130        return 1;
131
132    if (!nodes[block][offset].lat && !nodes[block][offset].lon)
133        return 1;
134
135#ifdef FIXED_POINT
136    out->lat = FIX_TO_DOUBLE(nodes[block][offset].lat);
137    out->lon = FIX_TO_DOUBLE(nodes[block][offset].lon);
138#else
139    out->lat = nodes[block][offset].lat;
140    out->lon = nodes[block][offset].lon;
141#endif
142    return 0;
143}
144
145static int ram_ways_set(osmid_t id, osmid_t *nds, int nd_count, struct keyval *tags, int pending)
146{
147    int block  = id2block(id);
148    int offset = id2offset(id);
149    struct keyval *p;
150
151    if (!ways[block]) {
152        ways[block] = calloc(PER_BLOCK, sizeof(struct ramWay));
153        if (!ways[block]) {
154            fprintf(stderr, "Error allocating ways\n");
155            exit_nicely();
156        }
157        way_blocks++;
158        //fprintf(stderr, "\tways(%zuMb)\n", way_blocks * sizeof(struct ramWay) * PER_BLOCK / 1000000);
159    }
160
161    if (ways[block][offset].ndids) {
162        free(ways[block][offset].ndids);
163        ways[block][offset].ndids = NULL;
164    }
165
166    /* Copy into length prefixed array */
167    ways[block][offset].ndids = malloc( (nd_count+1)*sizeof(osmid_t) );
168    memcpy( ways[block][offset].ndids+1, nds, nd_count*sizeof(osmid_t) );
169    ways[block][offset].ndids[0] = nd_count;
170    ways[block][offset].pending = pending;
171
172    if (!ways[block][offset].tags) {
173        p = malloc(sizeof(struct keyval));
174        if (p) {
175            initList(p);
176            ways[block][offset].tags = p;
177        } else {
178            fprintf(stderr, "%s malloc failed\n", __FUNCTION__);
179            exit_nicely();
180        }
181    } else
182        resetList(ways[block][offset].tags);
183
184    cloneList(ways[block][offset].tags, tags);
185
186    return 0;
187}
188
189static int ram_relations_set(osmid_t id, struct member *members, int member_count, struct keyval *tags)
190{
191    struct keyval *p;
192    int block  = id2block(id);
193    int offset = id2offset(id);
194    if (!rels[block]) {
195        rels[block] = calloc(PER_BLOCK, sizeof(struct ramRel));
196        if (!rels[block]) {
197            fprintf(stderr, "Error allocating rels\n");
198            exit_nicely();
199        }
200    }
201
202    if (!rels[block][offset].tags) {
203        p = malloc(sizeof(struct keyval));
204        if (p) {
205            initList(p);
206            rels[block][offset].tags = p;
207        } else {
208            fprintf(stderr, "%s malloc failed\n", __FUNCTION__);
209            exit_nicely();
210        }
211    } else
212        resetList(rels[block][offset].tags);
213
214    cloneList(rels[block][offset].tags, tags);
215
216    if (!rels[block][offset].members)
217      free( rels[block][offset].members );
218
219    struct member *ptr = malloc(sizeof(struct member) * member_count);
220    if (ptr) {
221        memcpy( ptr, members, sizeof(struct member) * member_count );
222        rels[block][offset].member_count = member_count;
223        rels[block][offset].members = ptr;
224    } else {
225        fprintf(stderr, "%s malloc failed\n", __FUNCTION__);
226        exit_nicely();
227    }
228
229    return 0;
230}
231
232static int ram_nodes_get_list(struct osmNode *nodes, osmid_t *ndids, int nd_count)
233{
234    int i, count;
235
236    count = 0;
237    for( i=0; i<nd_count; i++ )
238    {
239        if (ram_nodes_get(&nodes[count], ndids[i]))
240            continue;
241
242        count++;
243    }
244    return count;
245}
246
247static void ram_iterate_relations(int (*callback)(osmid_t id, struct member *members, int member_count, struct keyval *tags, int))
248{
249    int block, offset;
250
251    fprintf(stderr, "\n");
252    for(block=NUM_BLOCKS-1; block>=0; block--) {
253        if (!rels[block])
254            continue;
255
256        for (offset=0; offset < PER_BLOCK; offset++) {
257            if (rels[block][offset].members) {
258                osmid_t id = block2id(block, offset);
259                rel_out_count++;
260                if (rel_out_count % 10 == 0)
261                    fprintf(stderr, "\rWriting relation (%u)", rel_out_count);
262
263                callback(id, rels[block][offset].members, rels[block][offset].member_count, rels[block][offset].tags, 0);
264            }
265            free(rels[block][offset].members);
266            rels[block][offset].members = NULL;
267            resetList(rels[block][offset].tags);
268            free(rels[block][offset].tags);
269            rels[block][offset].tags=NULL;
270        }
271        free(rels[block]);
272        rels[block] = NULL;
273    }
274
275    fprintf(stderr, "\rWriting relation (%u)\n", rel_out_count);
276}
277
278static void ram_iterate_ways(int (*callback)(osmid_t id, struct keyval *tags, struct osmNode *nodes, int count, int exists))
279{
280    int block, offset, ndCount = 0;
281    struct osmNode *nodes;
282
283    fprintf(stderr, "\n");
284    for(block=NUM_BLOCKS-1; block>=0; block--) {
285        if (!ways[block])
286            continue;
287
288        for (offset=0; offset < PER_BLOCK; offset++) {
289            if (ways[block][offset].ndids) {
290                way_out_count++;
291                if (way_out_count % 1000 == 0)
292                    fprintf(stderr, "\rWriting way (%uk)", way_out_count/1000);
293
294                if (ways[block][offset].pending) {
295                    /* First element contains number of nodes */
296                    nodes = malloc( sizeof(struct osmNode) * ways[block][offset].ndids[0]);
297                    ndCount = ram_nodes_get_list(nodes, ways[block][offset].ndids+1, ways[block][offset].ndids[0]);
298
299                    if (nodes) {
300                        osmid_t id = block2id(block, offset);
301                        callback(id, ways[block][offset].tags, nodes, ndCount, 0);
302                        free(nodes);
303                    }
304
305                    ways[block][offset].pending = 0;
306                }
307
308                if (ways[block][offset].tags) {
309                    resetList(ways[block][offset].tags);
310                    free(ways[block][offset].tags);
311                    ways[block][offset].tags = NULL;
312                }
313                if (ways[block][offset].ndids) {
314                    free(ways[block][offset].ndids);
315                    ways[block][offset].ndids = NULL;
316                }
317            }
318        }
319    }
320    fprintf(stderr, "\rWriting way (%uk)\n", way_out_count/1000);
321}
322
323/* Caller must free nodes_ptr and resetList(tags_ptr) */
324static int ram_ways_get(osmid_t id, struct keyval *tags_ptr, struct osmNode **nodes_ptr, int *count_ptr)
325{
326    int block = id2block(id), offset = id2offset(id), ndCount = 0;
327    struct osmNode *nodes;
328
329    if (!ways[block])
330        return 1;
331
332    if (ways[block][offset].ndids) {
333        /* First element contains number of nodes */
334        nodes = malloc( sizeof(struct osmNode) * ways[block][offset].ndids[0]);
335        ndCount = ram_nodes_get_list(nodes, ways[block][offset].ndids+1, ways[block][offset].ndids[0]);
336
337        if (ndCount) {
338            cloneList( tags_ptr, ways[block][offset].tags );
339            *nodes_ptr = nodes;
340            *count_ptr = ndCount;
341            return 0;
342        }
343    }
344    return 1;
345}
346
347// Marks the way so that iterate ways skips it
348static int ram_ways_done(osmid_t id)
349{
350    int block = id2block(id), offset = id2offset(id);
351
352    if (!ways[block])
353        return 1;
354
355    ways[block][offset].pending = 0;
356    return 0;
357}
358
359static void ram_analyze(void)
360{
361    /* No need */
362}
363
364static void ram_end(void)
365{
366    /* No need */
367}
368
369static int ram_start(const struct output_options *options)
370{
371    // latlong has a range of +-180, mercator +-20000
372    // The fixed poing scaling needs adjusting accordingly to
373    // be stored accurately in an int
374    scale = options->scale;
375   
376    fprintf( stderr, "Mid: Ram, scale=%d\n", scale );
377
378    return 0;
379}
380
381static void ram_stop(void)
382{
383    int i, j;
384
385    for (i=0; i<NUM_BLOCKS; i++) {
386        if (nodes[i]) {
387            free(nodes[i]);
388            nodes[i] = NULL;
389        }
390        if (ways[i]) {
391            for (j=0; j<PER_BLOCK; j++) {
392                if (ways[i][j].tags) {
393                    resetList(ways[i][j].tags);
394                    free(ways[i][j].tags);
395                }
396                if (ways[i][j].ndids)
397                    free(ways[i][j].ndids);
398            }
399            free(ways[i]);
400            ways[i] = NULL;
401        }
402    }
403}
404
405struct middle_t mid_ram = {
406    .start             = ram_start,
407    .stop              = ram_stop,
408    .end               = ram_end,
409    .cleanup           = ram_stop,
410    .analyze           = ram_analyze,
411    .nodes_set         = ram_nodes_set,
412#if 0
413    .nodes_get         = ram_nodes_get,
414#endif
415    .nodes_get_list    = ram_nodes_get_list,
416    .ways_set          = ram_ways_set,
417    .ways_get          = ram_ways_get,
418    .ways_done         = ram_ways_done,
419
420    .relations_set     = ram_relations_set,
421#if 0
422    .iterate_nodes     = ram_iterate_nodes,
423#endif
424    .iterate_ways      = ram_iterate_ways,
425    .iterate_relations = ram_iterate_relations
426};
427
Note: See TracBrowser for help on using the repository browser.