database: Log how long it took to retrieve an AS
[people/ms/libloc.git] / src / database.c
index 928ed85..e5460da 100644 (file)
@@ -21,7 +21,9 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
+#include <sys/mman.h>
 #include <sys/types.h>
+#include <time.h>
 #include <unistd.h>
 
 #include <loc/libloc.h>
@@ -38,166 +40,17 @@ struct loc_database {
 
        FILE* file;
        unsigned int version;
+       time_t created_at;
        off_t vendor;
        off_t description;
 
        // ASes in the database
-       struct loc_as** as;
+       struct loc_database_as_v0* as_v0;
        size_t as_count;
 
        struct loc_stringpool* pool;
 };
 
-LOC_EXPORT int loc_database_new(struct loc_ctx* ctx, struct loc_database** database, size_t pool_size) {
-       struct loc_database* db = calloc(1, sizeof(*db));
-       if (!db)
-               return -ENOMEM;
-
-       // Reference context
-       db->ctx = loc_ref(ctx);
-       db->refcount = 1;
-
-       DEBUG(db->ctx, "Database allocated at %p\n", db);
-
-       // Create string pool
-       int r = loc_stringpool_new(db->ctx, &db->pool, pool_size);
-       if (r) {
-               loc_database_unref(db);
-               return r;
-       }
-
-       *database = db;
-
-       return 0;
-}
-
-LOC_EXPORT int loc_database_open(struct loc_ctx* ctx, struct loc_database** database, FILE* f) {
-       int r = loc_database_new(ctx, database, 0);
-       if (r)
-               return r;
-
-       return loc_database_read(*database, f);
-}
-
-LOC_EXPORT struct loc_database* loc_database_ref(struct loc_database* db) {
-       db->refcount++;
-
-       return db;
-}
-
-static void loc_database_free(struct loc_database* db) {
-       DEBUG(db->ctx, "Releasing database %p\n", db);
-
-       // Remove references to all ASes
-       if (db->as) {
-               for (unsigned int i = 0; i < db->as_count; i++) {
-                       loc_as_unref(db->as[i]);
-               }
-               free(db->as);
-       }
-
-       loc_stringpool_unref(db->pool);
-
-       // Close file
-       if (db->file)
-               fclose(db->file);
-
-       loc_unref(db->ctx);
-       free(db);
-}
-
-LOC_EXPORT struct loc_database* loc_database_unref(struct loc_database* db) {
-       if (--db->refcount > 0)
-               return NULL;
-
-       loc_database_free(db);
-       return NULL;
-}
-
-LOC_EXPORT const char* loc_database_get_vendor(struct loc_database* db) {
-       return loc_stringpool_get(db->pool, db->vendor);
-}
-
-LOC_EXPORT int loc_database_set_vendor(struct loc_database* db, const char* vendor) {
-       // Add the string to the string pool
-       off_t offset = loc_stringpool_add(db->pool, vendor);
-       if (offset < 0)
-               return offset;
-
-       db->vendor = offset;
-       return 0;
-}
-
-LOC_EXPORT const char* loc_database_get_description(struct loc_database* db) {
-       return loc_stringpool_get(db->pool, db->description);
-}
-
-LOC_EXPORT int loc_database_set_description(struct loc_database* db, const char* description) {
-       // Add the string to the string pool
-       off_t offset = loc_stringpool_add(db->pool, description);
-       if (offset < 0)
-               return offset;
-
-       db->description = offset;
-       return 0;
-}
-
-LOC_EXPORT size_t loc_database_count_as(struct loc_database* db) {
-       return db->as_count;
-}
-
-static int loc_database_has_as(struct loc_database* db, struct loc_as* as) {
-       for (unsigned int i = 0; i < db->as_count; i++) {
-               if (loc_as_cmp(as, db->as[i]) == 0)
-                       return i;
-       }
-
-       return -1;
-}
-
-static int __loc_as_cmp(const void* as1, const void* as2) {
-       return loc_as_cmp(*(struct loc_as**)as1, *(struct loc_as**)as2);
-}
-
-static void loc_database_sort_ases(struct loc_database* db) {
-       qsort(db->as, db->as_count, sizeof(*db->as), __loc_as_cmp);
-}
-
-static struct loc_as* __loc_database_add_as(struct loc_database* db, struct loc_as* as) {
-       // Check if AS exists already
-       int i = loc_database_has_as(db, as);
-       if (i >= 0) {
-               loc_as_unref(as);
-
-               // Select already existing AS
-               as = db->as[i];
-
-               return loc_as_ref(as);
-       }
-
-       db->as_count++;
-
-       // Make space for the new entry
-       db->as = realloc(db->as, sizeof(*db->as) * db->as_count);
-
-       // Add the new entry at the end
-       db->as[db->as_count - 1] = loc_as_ref(as);
-
-       // Sort everything
-       loc_database_sort_ases(db);
-
-       return as;
-}
-
-LOC_EXPORT struct loc_as* loc_database_add_as(struct loc_database* db, uint32_t number) {
-       struct loc_as* as;
-       int r = loc_as_new(db->ctx, db->pool, &as, number);
-       if (r)
-               return NULL;
-
-       return __loc_database_add_as(db, as);
-}
-
 static int loc_database_read_magic(struct loc_database* db) {
        struct loc_database_magic magic;
 
@@ -230,33 +83,18 @@ static int loc_database_read_magic(struct loc_database* db) {
 
 static int loc_database_read_as_section_v0(struct loc_database* db,
                off_t as_offset, size_t as_length) {
-       struct loc_database_as_v0 dbobj;
-
-       // Read from the start of the section
-       int r = fseek(db->file, as_offset, SEEK_SET);
-       if (r)
-               return r;
-
-       // Read all ASes
-       size_t as_count = as_length / sizeof(dbobj);
-       for (unsigned int i = 0; i < as_count; i++) {
-               size_t bytes_read = fread(&dbobj, 1, sizeof(dbobj), db->file);
-               if (bytes_read < sizeof(dbobj)) {
-                       ERROR(db->ctx, "Could not read an AS object\n");
-                       return -ENOMSG;
-               }
+       DEBUG(db->ctx, "Reading AS section from %jd (%zu bytes)\n", as_offset, as_length);
 
-               // Allocate a new AS
-               struct loc_as* as;
-               r = loc_as_new_from_database_v0(db->ctx, db->pool, &as, &dbobj);
-               if (r)
-                       return r;
+       if (as_length > 0) {
+               db->as_v0 = mmap(NULL, as_length, PROT_READ,
+                       MAP_SHARED, fileno(db->file), as_offset);
 
-               // Attach it to the database
-               as = __loc_database_add_as(db, as);
-               loc_as_unref(as);
+               if (db->as_v0 == MAP_FAILED)
+                       return -errno;
        }
 
+       db->as_count = as_length / sizeof(*db->as_v0);
+
        INFO(db->ctx, "Read %zu ASes from the database\n", db->as_count);
 
        return 0;
@@ -274,6 +112,7 @@ static int loc_database_read_header_v0(struct loc_database* db) {
        }
 
        // Copy over data
+       db->created_at  = be64toh(header.created_at);
        db->vendor      = ntohl(header.vendor);
        db->description = ntohl(header.description);
 
@@ -281,7 +120,8 @@ static int loc_database_read_header_v0(struct loc_database* db) {
        off_t pool_offset  = ntohl(header.pool_offset);
        size_t pool_length = ntohl(header.pool_length);
 
-       int r = loc_stringpool_read(db->pool, db->file, pool_offset, pool_length);
+       int r = loc_stringpool_open(db->ctx, &db->pool,
+               db->file, pool_length, pool_offset);
        if (r)
                return r;
 
@@ -307,25 +147,34 @@ static int loc_database_read_header(struct loc_database* db) {
        }
 }
 
-LOC_EXPORT int loc_database_read(struct loc_database* db, FILE* f) {
-       // Copy the file pointer and work on that so we don't care if
-       // the calling function closes the file
+static FILE* copy_file_pointer(FILE* f) {
        int fd = fileno(f);
 
        // Make a copy
        fd = dup(fd);
 
-       // Retrieve a file pointer
-       db->file = fdopen(fd, "r");
-       if (!db->file)
-               return -errno;
+       return fdopen(fd, "r");
+}
 
-       int r = fseek(db->file, 0, SEEK_SET);
-       if (r)
-               return r;
+LOC_EXPORT int loc_database_new(struct loc_ctx* ctx, struct loc_database** database, FILE* f) {
+       struct loc_database* db = calloc(1, sizeof(*db));
+       if (!db)
+               return -ENOMEM;
+
+       // Reference context
+       db->ctx = loc_ref(ctx);
+       db->refcount = 1;
+
+       DEBUG(db->ctx, "Database object allocated at %p\n", db);
+
+       // Copy the file pointer and work on that so we don't care if
+       // the calling function closes the file
+       db->file = copy_file_pointer(f);
+       if (!db->file)
+               goto FAIL;
 
        // Read magic bytes
-       r = loc_database_read_magic(db);
+       int r = loc_database_read_magic(db);
        if (r)
                return r;
 
@@ -334,89 +183,130 @@ LOC_EXPORT int loc_database_read(struct loc_database* db, FILE* f) {
        if (r)
                return r;
 
+       *database = db;
+
        return 0;
+
+FAIL:
+       loc_database_unref(db);
+
+       return -errno;
 }
 
-static void loc_database_make_magic(struct loc_database* db, struct loc_database_magic* magic) {
-       // Copy magic bytes
-       for (unsigned int i = 0; i < strlen(LOC_DATABASE_MAGIC); i++)
-               magic->magic[i] = LOC_DATABASE_MAGIC[i];
+LOC_EXPORT struct loc_database* loc_database_ref(struct loc_database* db) {
+       db->refcount++;
 
-       // Set version
-       magic->version = htons(LOC_DATABASE_VERSION);
+       return db;
 }
 
-static int loc_database_write_pool(struct loc_database* db, struct loc_database_header_v0* header, off_t* offset, FILE* f) {
-       // Save the offset of the pool section
-       DEBUG(db->ctx, "Pool starts at %jd bytes\n", *offset);
-       header->pool_offset = htonl(*offset);
+static void loc_database_free(struct loc_database* db) {
+       DEBUG(db->ctx, "Releasing database %p\n", db);
 
-       // Write the pool
-       size_t pool_length = loc_stringpool_write(db->pool, f);
-       *offset += pool_length;
+       // Removing all ASes
+       if (db->as_v0) {
+               int r = munmap(db->as_v0, db->as_count * sizeof(*db->as_v0));
+               if (r)
+                       ERROR(db->ctx, "Could not unmap AS section: %s\n", strerror(errno));
+       }
 
-       DEBUG(db->ctx, "Pool has a length of %zu bytes\n", pool_length);
-       header->pool_length = htonl(pool_length);
+       loc_stringpool_unref(db->pool);
 
-       return 0;
+       // Close file
+       if (db->file)
+               fclose(db->file);
+
+       loc_unref(db->ctx);
+       free(db);
 }
 
-LOC_EXPORT int loc_database_write(struct loc_database* db, FILE* f) {
-       struct loc_database_magic magic;
-       loc_database_make_magic(db, &magic);
+LOC_EXPORT struct loc_database* loc_database_unref(struct loc_database* db) {
+       if (--db->refcount > 0)
+               return NULL;
 
-       // Make the header
-       struct loc_database_header_v0 header;
-       header.vendor      = htonl(db->vendor);
-       header.description = htonl(db->description);
+       loc_database_free(db);
+       return NULL;
+}
 
-       int r;
-       off_t offset = 0;
+LOC_EXPORT time_t loc_database_created_at(struct loc_database* db) {
+       return db->created_at;
+}
 
-       // Start writing at the beginning of the file
-       r = fseek(f, 0, SEEK_SET);
-       if (r)
-               return r;
+LOC_EXPORT const char* loc_database_get_vendor(struct loc_database* db) {
+       return loc_stringpool_get(db->pool, db->vendor);
+}
 
-       // Write the magic
-       offset += fwrite(&magic, 1, sizeof(magic), f);
+LOC_EXPORT const char* loc_database_get_description(struct loc_database* db) {
+       return loc_stringpool_get(db->pool, db->description);
+}
 
-       // Skip the space we need to write the header later
-       r = fseek(f, sizeof(header), SEEK_CUR);
-       if (r) {
-               DEBUG(db->ctx, "Could not seek to position after header\n");
-               return r;
-       }
-       offset += sizeof(header);
+LOC_EXPORT size_t loc_database_count_as(struct loc_database* db) {
+       return db->as_count;
+}
 
-       // Move to next page boundary
-       while (offset % LOC_DATABASE_PAGE_SIZE > 0)
-               offset += fwrite("", 1, 1, f);
+// Returns the AS at position pos
+static int loc_database_fetch_as(struct loc_database* db, struct loc_as** as, off_t pos) {
+       if ((size_t)pos >= db->as_count)
+               return -EINVAL;
 
-       // Write pool
-       r = loc_database_write_pool(db, &header, &offset, f);
-       if (r)
-               return r;
+       DEBUG(db->ctx, "Fetching AS at position %jd\n", pos);
 
-       // Write all ASes
-       header.as_offset = htonl(offset);
+       int r;
+       switch (db->version) {
+               case 0:
+                       r = loc_as_new_from_database_v0(db->ctx, db->pool, as, db->as_v0 + pos);
+                       break;
 
-       struct loc_database_as_v0 dbas;
-       for (unsigned int i = 0; i < db->as_count; i++) {
-               // Convert AS into database format
-               loc_as_to_database_v0(db->as[i], &dbas);
+               default:
+                       return -1;
+       }
 
-               // Write to disk
-               offset += fwrite(&dbas, 1, sizeof(dbas), f);
+       if (r == 0) {
+               DEBUG(db->ctx, "Got AS%u\n", loc_as_get_number(*as));
        }
-       header.as_length = htonl(db->as_count * sizeof(dbas));
 
-       // Write the header
-       r = fseek(f, sizeof(magic), SEEK_SET);
-       if (r)
-               return r;
+       return r;
+}
 
-       offset += fwrite(&header, 1, sizeof(header), f);
+// Performs a binary search to find the AS in the list
+LOC_EXPORT int loc_database_get_as(struct loc_database* db, struct loc_as** as, uint32_t number) {
+       off_t lo = 0;
+       off_t hi = db->as_count - 1;
 
-       return 0;
+       // Save start time
+       clock_t start = clock();
+
+       while (lo <= hi) {
+               off_t i = (lo + hi) / 2;
+
+               // Fetch AS in the middle between lo and hi
+               int r = loc_database_fetch_as(db, as, i);
+               if (r)
+                       return r;
+
+               // Check if this is a match
+               uint32_t as_number = loc_as_get_number(*as);
+               if (as_number == number) {
+                       clock_t end = clock();
+
+                       // Log how fast this has been
+                       DEBUG(db->ctx, "Found AS%u in %.8fs\n", as_number,
+                               (double)(end - start) / CLOCKS_PER_SEC);
+
+                       return 0;
+               }
+
+               // If it wasn't, we release the AS and
+               // adjust our search pointers
+               loc_as_unref(*as);
+
+               if (as_number < number) {
+                       lo = i + 1;
+               } else
+                       hi = i - 1;
+       }
+
+       // Nothing found
+       *as = NULL;
+
+       return 1;
 }