database: Unmap all mapped sections when freeing database
[people/ms/libloc.git] / src / database.c
1 /*
2         libloc - A library to determine the location of someone on the Internet
3
4         Copyright (C) 2017 IPFire Development Team <info@ipfire.org>
5
6         This library is free software; you can redistribute it and/or
7         modify it under the terms of the GNU Lesser General Public
8         License as published by the Free Software Foundation; either
9         version 2.1 of the License, or (at your option) any later version.
10
11         This library is distributed in the hope that it will be useful,
12         but WITHOUT ANY WARRANTY; without even the implied warranty of
13         MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14         Lesser General Public License for more details.
15 */
16
17 #include <arpa/inet.h>
18 #include <endian.h>
19 #include <errno.h>
20 #include <netinet/in.h>
21 #include <stddef.h>
22 #include <stdint.h>
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include <sys/mman.h>
27 #include <sys/types.h>
28 #include <time.h>
29 #include <unistd.h>
30
31 #include <loc/libloc.h>
32 #include <loc/as.h>
33 #include <loc/database.h>
34 #include <loc/format.h>
35 #include <loc/network.h>
36 #include <loc/private.h>
37 #include <loc/stringpool.h>
38
39 struct loc_database {
40         struct loc_ctx* ctx;
41         int refcount;
42
43         unsigned int version;
44         time_t created_at;
45         off_t vendor;
46         off_t description;
47
48         // ASes in the database
49         struct loc_database_as_v0* as_v0;
50         size_t as_count;
51
52         // Network tree
53         struct loc_database_network_node_v0* network_nodes_v0;
54         size_t network_nodes_count;
55
56         // Networks
57         struct loc_database_network_v0* networks_v0;
58         size_t networks_count;
59
60         struct loc_stringpool* pool;
61 };
62
63 static int loc_database_read_magic(struct loc_database* db, FILE* f) {
64         struct loc_database_magic magic;
65
66         // Read from file
67         size_t bytes_read = fread(&magic, 1, sizeof(magic), f);
68
69         // Check if we have been able to read enough data
70         if (bytes_read < sizeof(magic)) {
71                 ERROR(db->ctx, "Could not read enough data to validate magic bytes\n");
72                 DEBUG(db->ctx, "Read %zu bytes, but needed %zu\n", bytes_read, sizeof(magic));
73                 return -ENOMSG;
74         }
75
76         // Compare magic bytes
77         if (memcmp(LOC_DATABASE_MAGIC, magic.magic, strlen(LOC_DATABASE_MAGIC)) == 0) {
78                 DEBUG(db->ctx, "Magic value matches\n");
79
80                 // Parse version
81                 db->version = be16toh(magic.version);
82                 DEBUG(db->ctx, "Database version is %u\n", db->version);
83
84                 return 0;
85         }
86
87         ERROR(db->ctx, "Database format is not compatible\n");
88
89         // Return an error
90         return 1;
91 }
92
93 static int loc_database_read_as_section_v0(struct loc_database* db,
94                 FILE* f, const struct loc_database_header_v0* header) {
95         off_t as_offset  = be32toh(header->as_offset);
96         size_t as_length = be32toh(header->as_length);
97
98         DEBUG(db->ctx, "Reading AS section from %jd (%zu bytes)\n", as_offset, as_length);
99
100         if (as_length > 0) {
101                 db->as_v0 = mmap(NULL, as_length, PROT_READ,
102                         MAP_SHARED, fileno(f), as_offset);
103
104                 if (db->as_v0 == MAP_FAILED)
105                         return -errno;
106         }
107
108         db->as_count = as_length / sizeof(*db->as_v0);
109
110         INFO(db->ctx, "Read %zu ASes from the database\n", db->as_count);
111
112         return 0;
113 }
114
115 static int loc_database_read_network_nodes_section_v0(struct loc_database* db,
116                 FILE* f, const struct loc_database_header_v0* header) {
117         off_t network_nodes_offset  = be32toh(header->network_tree_offset);
118         size_t network_nodes_length = be32toh(header->network_tree_length);
119
120         DEBUG(db->ctx, "Reading network nodes section from %jd (%zu bytes)\n",
121                 network_nodes_offset, network_nodes_length);
122
123         if (network_nodes_length > 0) {
124                 db->network_nodes_v0 = mmap(NULL, network_nodes_length, PROT_READ,
125                         MAP_SHARED, fileno(f), network_nodes_offset);
126
127                 if (db->network_nodes_v0 == MAP_FAILED)
128                         return -errno;
129         }
130
131         db->network_nodes_count = network_nodes_length / sizeof(*db->network_nodes_v0);
132
133         INFO(db->ctx, "Read %zu network nodes from the database\n", db->network_nodes_count);
134
135         return 0;
136 }
137
138 static int loc_database_read_networks_section_v0(struct loc_database* db,
139                 FILE* f, const struct loc_database_header_v0* header) {
140         off_t networks_offset  = be32toh(header->network_data_offset);
141         size_t networks_length = be32toh(header->network_data_length);
142
143         DEBUG(db->ctx, "Reading networks section from %jd (%zu bytes)\n",
144                 networks_offset, networks_length);
145
146         if (networks_length > 0) {
147                 db->networks_v0 = mmap(NULL, networks_length, PROT_READ,
148                         MAP_SHARED, fileno(f), networks_offset);
149
150                 if (db->networks_v0 == MAP_FAILED)
151                         return -errno;
152         }
153
154         db->networks_count = networks_length / sizeof(*db->networks_v0);
155
156         INFO(db->ctx, "Read %zu networks from the database\n", db->networks_count);
157
158         return 0;
159 }
160
161 static int loc_database_read_header_v0(struct loc_database* db, FILE* f) {
162         struct loc_database_header_v0 header;
163
164         // Read from file
165         size_t size = fread(&header, 1, sizeof(header), f);
166
167         if (size < sizeof(header)) {
168                 ERROR(db->ctx, "Could not read enough data for header\n");
169                 return -ENOMSG;
170         }
171
172         // Copy over data
173         db->created_at  = be64toh(header.created_at);
174         db->vendor      = be32toh(header.vendor);
175         db->description = be32toh(header.description);
176
177         // Open pool
178         off_t pool_offset  = be32toh(header.pool_offset);
179         size_t pool_length = be32toh(header.pool_length);
180
181         int r = loc_stringpool_open(db->ctx, &db->pool,
182                 f, pool_length, pool_offset);
183         if (r)
184                 return r;
185
186         // AS section
187         r = loc_database_read_as_section_v0(db, f, &header);
188         if (r)
189                 return r;
190
191         // Network Nodes
192         r = loc_database_read_network_nodes_section_v0(db, f, &header);
193         if (r)
194                 return r;
195
196         // Networks
197         r = loc_database_read_networks_section_v0(db, f, &header);
198         if (r)
199                 return r;
200
201         return 0;
202 }
203
204 static int loc_database_read_header(struct loc_database* db, FILE* f) {
205         switch (db->version) {
206                 case 0:
207                         return loc_database_read_header_v0(db, f);
208
209                 default:
210                         ERROR(db->ctx, "Incompatible database version: %u\n", db->version);
211                         return 1;
212         }
213 }
214
215 static int loc_database_read(struct loc_database* db, FILE* f) {
216         clock_t start = clock();
217
218         // Read magic bytes
219         int r = loc_database_read_magic(db, f);
220         if (r)
221                 return r;
222
223         // Read the header
224         r = loc_database_read_header(db, f);
225         if (r)
226                 return r;
227
228         clock_t end = clock();
229
230         INFO(db->ctx, "Opened database in %.8fs\n",
231                 (double)(end - start) / CLOCKS_PER_SEC);
232
233         return 0;
234 }
235
236 LOC_EXPORT int loc_database_new(struct loc_ctx* ctx, struct loc_database** database, FILE* f) {
237         // Fail on invalid file handle
238         if (!f)
239                 return -EINVAL;
240
241         struct loc_database* db = calloc(1, sizeof(*db));
242         if (!db)
243                 return -ENOMEM;
244
245         // Reference context
246         db->ctx = loc_ref(ctx);
247         db->refcount = 1;
248
249         DEBUG(db->ctx, "Database object allocated at %p\n", db);
250
251         int r = loc_database_read(db, f);
252         if (r) {
253                 loc_database_unref(db);
254                 return r;
255         }
256
257         *database = db;
258
259         return 0;
260 }
261
262 LOC_EXPORT struct loc_database* loc_database_ref(struct loc_database* db) {
263         db->refcount++;
264
265         return db;
266 }
267
268 static void loc_database_free(struct loc_database* db) {
269         int r;
270
271         DEBUG(db->ctx, "Releasing database %p\n", db);
272
273         // Removing all ASes
274         if (db->as_v0) {
275                 r = munmap(db->as_v0, db->as_count * sizeof(*db->as_v0));
276                 if (r)
277                         ERROR(db->ctx, "Could not unmap AS section: %s\n", strerror(errno));
278         }
279
280         // Remove mapped network sections
281         if (db->networks_v0) {
282                 r = munmap(db->networks_v0, db->networks_count * sizeof(*db->networks_v0));
283                 if (r)
284                         ERROR(db->ctx, "Could not unmap networks section: %s\n", strerror(errno));
285         }
286
287         // Remove mapped network nodes section
288         if (db->network_nodes_v0) {
289                 r = munmap(db->network_nodes_v0, db->network_nodes_count * sizeof(*db->network_nodes_v0));
290                 if (r)
291                         ERROR(db->ctx, "Could not unmap network nodes section: %s\n", strerror(errno));
292         }
293
294         loc_stringpool_unref(db->pool);
295
296         loc_unref(db->ctx);
297         free(db);
298 }
299
300 LOC_EXPORT struct loc_database* loc_database_unref(struct loc_database* db) {
301         if (--db->refcount > 0)
302                 return NULL;
303
304         loc_database_free(db);
305         return NULL;
306 }
307
308 LOC_EXPORT time_t loc_database_created_at(struct loc_database* db) {
309         return db->created_at;
310 }
311
312 LOC_EXPORT const char* loc_database_get_vendor(struct loc_database* db) {
313         return loc_stringpool_get(db->pool, db->vendor);
314 }
315
316 LOC_EXPORT const char* loc_database_get_description(struct loc_database* db) {
317         return loc_stringpool_get(db->pool, db->description);
318 }
319
320 LOC_EXPORT size_t loc_database_count_as(struct loc_database* db) {
321         return db->as_count;
322 }
323
324 // Returns the AS at position pos
325 static int loc_database_fetch_as(struct loc_database* db, struct loc_as** as, off_t pos) {
326         if ((size_t)pos >= db->as_count)
327                 return -EINVAL;
328
329         DEBUG(db->ctx, "Fetching AS at position %jd\n", pos);
330
331         int r;
332         switch (db->version) {
333                 case 0:
334                         r = loc_as_new_from_database_v0(db->ctx, db->pool, as, db->as_v0 + pos);
335                         break;
336
337                 default:
338                         return -1;
339         }
340
341         if (r == 0) {
342                 DEBUG(db->ctx, "Got AS%u\n", loc_as_get_number(*as));
343         }
344
345         return r;
346 }
347
348 // Performs a binary search to find the AS in the list
349 LOC_EXPORT int loc_database_get_as(struct loc_database* db, struct loc_as** as, uint32_t number) {
350         off_t lo = 0;
351         off_t hi = db->as_count - 1;
352
353         // Save start time
354         clock_t start = clock();
355
356         while (lo <= hi) {
357                 off_t i = (lo + hi) / 2;
358
359                 // Fetch AS in the middle between lo and hi
360                 int r = loc_database_fetch_as(db, as, i);
361                 if (r)
362                         return r;
363
364                 // Check if this is a match
365                 uint32_t as_number = loc_as_get_number(*as);
366                 if (as_number == number) {
367                         clock_t end = clock();
368
369                         // Log how fast this has been
370                         DEBUG(db->ctx, "Found AS%u in %.8fs\n", as_number,
371                                 (double)(end - start) / CLOCKS_PER_SEC);
372
373                         return 0;
374                 }
375
376                 // If it wasn't, we release the AS and
377                 // adjust our search pointers
378                 loc_as_unref(*as);
379
380                 if (as_number < number) {
381                         lo = i + 1;
382                 } else
383                         hi = i - 1;
384         }
385
386         // Nothing found
387         *as = NULL;
388
389         return 1;
390 }
391
392 // Returns the network at position pos
393 static int loc_database_fetch_network(struct loc_database* db, struct loc_network** network, struct in6_addr* address, off_t pos) {
394         if ((size_t)pos >= db->networks_count)
395                 return -EINVAL;
396
397         DEBUG(db->ctx, "Fetching network at position %jd\n", pos);
398
399         int r;
400         switch (db->version) {
401                 case 0:
402                         r = loc_network_new_from_database_v0(db->ctx, network, address, db->networks_v0 + pos);
403                         break;
404
405                 default:
406                         return -1;
407         }
408
409         if (r == 0) {
410                 char* string = loc_network_str(*network);
411                 DEBUG(db->ctx, "Got network %s\n", string);
412                 free(string);
413         }
414
415         return r;
416 }
417
418 static int __loc_database_lookup_leaf_node(struct loc_database* db, const struct in6_addr* address,
419                 struct loc_network** network, struct in6_addr* network_address,
420                 const struct loc_database_network_node_v0* node) {
421         // Check if this node is a leaf node
422         if (node->zero != htobe32(0xffffffff))
423                 return 1;
424
425         DEBUG(db->ctx, "Node is a leaf: %jd\n", node - db->network_nodes_v0);
426
427         // Fetch the network
428         int r = loc_database_fetch_network(db, network,
429                 network_address, be32toh(node->one));
430         if (r)
431                 return r;
432
433         // Check if the given IP address is inside the network
434         r = loc_network_match_address(*network, address);
435         if (r) {
436                 DEBUG(db->ctx, "Searched address is not part of the network\n");
437
438                 loc_network_unref(*network);
439                 *network = NULL;
440                 return 1;
441         }
442
443         // A network was found and the IP address matches
444         return 0;
445 }
446
447 // Returns the highest result available
448 static int __loc_database_lookup_max(struct loc_database* db, const struct in6_addr* address,
449                 struct loc_network** network, struct in6_addr* network_address,
450                 const struct loc_database_network_node_v0* node, int level) {
451
452         // If the node is a leaf node, we end here
453         int r = __loc_database_lookup_leaf_node(db, address, network, network_address, node);
454         if (r <= 0)
455                 return r;
456
457         off_t node_index;
458
459         // Try to go down the ones path first
460         if (node->one) {
461                 node_index = be32toh(node->one);
462                 in6_addr_set_bit(network_address, level, 1);
463
464                 // Check boundaries
465                 if (node_index > 0 && (size_t)node_index <= db->network_nodes_count) {
466                         r = __loc_database_lookup_max(db, address, network, network_address,
467                                 db->network_nodes_v0 + node_index, level + 1);
468
469                         // Abort when match was found or error
470                         if (r <= 0)
471                                 return r;
472                 }
473         }
474
475         // ... and if that fails, we try to go down one step on a zero
476         // branch and then try the ones again...
477         if (node->zero) {
478                 node_index = be32toh(node->zero);
479                 in6_addr_set_bit(network_address, level, 0);
480
481                 // Check boundaries
482                 if (node_index > 0 && (size_t)node_index <= db->network_nodes_count) {
483                         r = __loc_database_lookup_max(db, address, network, network_address,
484                                 db->network_nodes_v0 + node_index, level + 1);
485
486                         // Abort when match was found or error
487                         if (r <= 0)
488                                 return r;
489                 }
490         }
491
492         // End of path
493         return 1;
494 }
495
496 // Searches for an exact match along the path
497 static int __loc_database_lookup(struct loc_database* db, const struct in6_addr* address,
498                 struct loc_network** network, struct in6_addr* network_address,
499                 const struct loc_database_network_node_v0* node, int level) {
500         // If the node is a leaf node, we end here
501         int r = __loc_database_lookup_leaf_node(db, address, network, network_address, node);
502         if (r <= 0)
503                 return r;
504
505         off_t node_index;
506
507         // Follow the path
508         int bit = in6_addr_get_bit(address, level);
509         in6_addr_set_bit(network_address, level, bit);
510
511         if (bit == 0)
512                 node_index = be32toh(node->zero);
513         else
514                 node_index = be32toh(node->one);
515
516         // If we point back to root, the path ends here
517         if (node_index == 0) {
518                 DEBUG(db->ctx, "Tree ends here\n");
519                 return 1;
520         }
521
522         // Check boundaries
523         if ((size_t)node_index >= db->network_nodes_count)
524                 return -EINVAL;
525
526         // Move on to the next node
527         r = __loc_database_lookup(db, address, network, network_address,
528                 db->network_nodes_v0 + node_index, level + 1);
529
530         // End here if a result was found
531         if (r == 0)
532                 return r;
533
534         // Raise any errors
535         else if (r < 0)
536                 return r;
537
538         DEBUG(db->ctx, "Could not find an exact match at %u\n", level);
539
540         // If nothing was found, we have to search for an inexact match
541         return __loc_database_lookup_max(db, address, network, network_address, node, level);
542 }
543
544 LOC_EXPORT int loc_database_lookup(struct loc_database* db,
545                 struct in6_addr* address, struct loc_network** network) {
546         struct in6_addr network_address;
547         memset(&network_address, 0, sizeof(network_address));
548
549         *network = NULL;
550
551         // Save start time
552         clock_t start = clock();
553
554         int r = __loc_database_lookup(db, address, network, &network_address,
555                 db->network_nodes_v0, 0);
556
557         clock_t end = clock();
558
559         // Log how fast this has been
560         DEBUG(db->ctx, "Executed network search in %.8fs\n",
561                 (double)(end - start) / CLOCKS_PER_SEC);
562
563         return r;
564 }
565
566 LOC_EXPORT int loc_database_lookup_from_string(struct loc_database* db,
567                 const char* string, struct loc_network** network) {
568         struct in6_addr address;
569
570         int r = loc_parse_address(db->ctx, string, &address);
571         if (r)
572                 return r;
573
574         return loc_database_lookup(db, &address, network);
575 }