6d399373bf3a866ed99fcfba9dc506e0496527fe
[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 <endian.h>
18 #include <errno.h>
19 #include <stddef.h>
20 #include <stdint.h>
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <string.h>
24 #include <sys/mman.h>
25 #include <sys/types.h>
26 #include <time.h>
27 #include <unistd.h>
28
29 #include <loc/libloc.h>
30 #include <loc/as.h>
31 #include <loc/database.h>
32 #include <loc/format.h>
33 #include <loc/private.h>
34 #include <loc/stringpool.h>
35
36 struct loc_database {
37         struct loc_ctx* ctx;
38         int refcount;
39
40         unsigned int version;
41         time_t created_at;
42         off_t vendor;
43         off_t description;
44
45         // ASes in the database
46         struct loc_database_as_v0* as_v0;
47         size_t as_count;
48
49         // Network tree
50         struct loc_database_network_node_v0* network_nodes_v0;
51         size_t network_nodes_count;
52
53         struct loc_stringpool* pool;
54 };
55
56 static int loc_database_read_magic(struct loc_database* db, FILE* f) {
57         struct loc_database_magic magic;
58
59         // Read from file
60         size_t bytes_read = fread(&magic, 1, sizeof(magic), f);
61
62         // Check if we have been able to read enough data
63         if (bytes_read < sizeof(magic)) {
64                 ERROR(db->ctx, "Could not read enough data to validate magic bytes\n");
65                 DEBUG(db->ctx, "Read %zu bytes, but needed %zu\n", bytes_read, sizeof(magic));
66                 return -ENOMSG;
67         }
68
69         // Compare magic bytes
70         if (memcmp(LOC_DATABASE_MAGIC, magic.magic, strlen(LOC_DATABASE_MAGIC)) == 0) {
71                 DEBUG(db->ctx, "Magic value matches\n");
72
73                 // Parse version
74                 db->version = be16toh(magic.version);
75                 DEBUG(db->ctx, "Database version is %u\n", db->version);
76
77                 return 0;
78         }
79
80         ERROR(db->ctx, "Database format is not compatible\n");
81
82         // Return an error
83         return 1;
84 }
85
86 static int loc_database_read_as_section_v0(struct loc_database* db,
87                 FILE* f, const struct loc_database_header_v0* header) {
88         off_t as_offset  = be32toh(header->as_offset);
89         size_t as_length = be32toh(header->as_length);
90
91         DEBUG(db->ctx, "Reading AS section from %jd (%zu bytes)\n", as_offset, as_length);
92
93         if (as_length > 0) {
94                 db->as_v0 = mmap(NULL, as_length, PROT_READ,
95                         MAP_SHARED, fileno(f), as_offset);
96
97                 if (db->as_v0 == MAP_FAILED)
98                         return -errno;
99         }
100
101         db->as_count = as_length / sizeof(*db->as_v0);
102
103         INFO(db->ctx, "Read %zu ASes from the database\n", db->as_count);
104
105         return 0;
106 }
107
108 static int loc_database_read_network_nodes_section_v0(struct loc_database* db,
109                 FILE* f, const struct loc_database_header_v0* header) {
110         off_t network_nodes_offset  = be32toh(header->network_tree_offset);
111         size_t network_nodes_length = be32toh(header->network_tree_length);
112
113         DEBUG(db->ctx, "Reading network nodes section from %jd (%zu bytes)\n",
114                 network_nodes_offset, network_nodes_length);
115
116         if (network_nodes_length > 0) {
117                 db->network_nodes_v0 = mmap(NULL, network_nodes_length, PROT_READ,
118                         MAP_SHARED, fileno(f), network_nodes_offset);
119
120                 if (db->network_nodes_v0 == MAP_FAILED)
121                         return -errno;
122         }
123
124         db->network_nodes_count = network_nodes_length / sizeof(*db->network_nodes_v0);
125
126         INFO(db->ctx, "Read %zu network nodes from the database\n", db->network_nodes_count);
127
128         return 0;
129 }
130
131 static int loc_database_read_header_v0(struct loc_database* db, FILE* f) {
132         struct loc_database_header_v0 header;
133
134         // Read from file
135         size_t size = fread(&header, 1, sizeof(header), f);
136
137         if (size < sizeof(header)) {
138                 ERROR(db->ctx, "Could not read enough data for header\n");
139                 return -ENOMSG;
140         }
141
142         // Copy over data
143         db->created_at  = be64toh(header.created_at);
144         db->vendor      = be32toh(header.vendor);
145         db->description = be32toh(header.description);
146
147         // Open pool
148         off_t pool_offset  = be32toh(header.pool_offset);
149         size_t pool_length = be32toh(header.pool_length);
150
151         int r = loc_stringpool_open(db->ctx, &db->pool,
152                 f, pool_length, pool_offset);
153         if (r)
154                 return r;
155
156         // AS section
157         r = loc_database_read_as_section_v0(db, f, &header);
158         if (r)
159                 return r;
160
161         // Network Nodes
162         r = loc_database_read_network_nodes_section_v0(db, f, &header);
163         if (r)
164                 return r;
165
166         return 0;
167 }
168
169 static int loc_database_read_header(struct loc_database* db, FILE* f) {
170         switch (db->version) {
171                 case 0:
172                         return loc_database_read_header_v0(db, f);
173
174                 default:
175                         ERROR(db->ctx, "Incompatible database version: %u\n", db->version);
176                         return 1;
177         }
178 }
179
180 static int loc_database_read(struct loc_database* db, FILE* f) {
181         clock_t start = clock();
182
183         // Read magic bytes
184         int r = loc_database_read_magic(db, f);
185         if (r)
186                 return r;
187
188         // Read the header
189         r = loc_database_read_header(db, f);
190         if (r)
191                 return r;
192
193         clock_t end = clock();
194
195         INFO(db->ctx, "Opened database in %.8fs\n",
196                 (double)(end - start) / CLOCKS_PER_SEC);
197
198         return 0;
199 }
200
201 LOC_EXPORT int loc_database_new(struct loc_ctx* ctx, struct loc_database** database, FILE* f) {
202         // Fail on invalid file handle
203         if (!f)
204                 return -EINVAL;
205
206         struct loc_database* db = calloc(1, sizeof(*db));
207         if (!db)
208                 return -ENOMEM;
209
210         // Reference context
211         db->ctx = loc_ref(ctx);
212         db->refcount = 1;
213
214         DEBUG(db->ctx, "Database object allocated at %p\n", db);
215
216         int r = loc_database_read(db, f);
217         if (r) {
218                 loc_database_unref(db);
219                 return r;
220         }
221
222         *database = db;
223
224         return 0;
225 }
226
227 LOC_EXPORT struct loc_database* loc_database_ref(struct loc_database* db) {
228         db->refcount++;
229
230         return db;
231 }
232
233 static void loc_database_free(struct loc_database* db) {
234         DEBUG(db->ctx, "Releasing database %p\n", db);
235
236         // Removing all ASes
237         if (db->as_v0) {
238                 int r = munmap(db->as_v0, db->as_count * sizeof(*db->as_v0));
239                 if (r)
240                         ERROR(db->ctx, "Could not unmap AS section: %s\n", strerror(errno));
241         }
242
243         loc_stringpool_unref(db->pool);
244
245         loc_unref(db->ctx);
246         free(db);
247 }
248
249 LOC_EXPORT struct loc_database* loc_database_unref(struct loc_database* db) {
250         if (--db->refcount > 0)
251                 return NULL;
252
253         loc_database_free(db);
254         return NULL;
255 }
256
257 LOC_EXPORT time_t loc_database_created_at(struct loc_database* db) {
258         return db->created_at;
259 }
260
261 LOC_EXPORT const char* loc_database_get_vendor(struct loc_database* db) {
262         return loc_stringpool_get(db->pool, db->vendor);
263 }
264
265 LOC_EXPORT const char* loc_database_get_description(struct loc_database* db) {
266         return loc_stringpool_get(db->pool, db->description);
267 }
268
269 LOC_EXPORT size_t loc_database_count_as(struct loc_database* db) {
270         return db->as_count;
271 }
272
273 // Returns the AS at position pos
274 static int loc_database_fetch_as(struct loc_database* db, struct loc_as** as, off_t pos) {
275         if ((size_t)pos >= db->as_count)
276                 return -EINVAL;
277
278         DEBUG(db->ctx, "Fetching AS at position %jd\n", pos);
279
280         int r;
281         switch (db->version) {
282                 case 0:
283                         r = loc_as_new_from_database_v0(db->ctx, db->pool, as, db->as_v0 + pos);
284                         break;
285
286                 default:
287                         return -1;
288         }
289
290         if (r == 0) {
291                 DEBUG(db->ctx, "Got AS%u\n", loc_as_get_number(*as));
292         }
293
294         return r;
295 }
296
297 // Performs a binary search to find the AS in the list
298 LOC_EXPORT int loc_database_get_as(struct loc_database* db, struct loc_as** as, uint32_t number) {
299         off_t lo = 0;
300         off_t hi = db->as_count - 1;
301
302         // Save start time
303         clock_t start = clock();
304
305         while (lo <= hi) {
306                 off_t i = (lo + hi) / 2;
307
308                 // Fetch AS in the middle between lo and hi
309                 int r = loc_database_fetch_as(db, as, i);
310                 if (r)
311                         return r;
312
313                 // Check if this is a match
314                 uint32_t as_number = loc_as_get_number(*as);
315                 if (as_number == number) {
316                         clock_t end = clock();
317
318                         // Log how fast this has been
319                         DEBUG(db->ctx, "Found AS%u in %.8fs\n", as_number,
320                                 (double)(end - start) / CLOCKS_PER_SEC);
321
322                         return 0;
323                 }
324
325                 // If it wasn't, we release the AS and
326                 // adjust our search pointers
327                 loc_as_unref(*as);
328
329                 if (as_number < number) {
330                         lo = i + 1;
331                 } else
332                         hi = i - 1;
333         }
334
335         // Nothing found
336         *as = NULL;
337
338         return 1;
339 }