binary geo ranges base cache

1 files changed, 407 insertions, 52 deletions

diff --git a/src/http/modules/ngx_http_geo_module.c b/src/http/modules/ngx_http_geo_module.c
index cab7b09da..bcb783979 100644
--- a/src/http/modules/ngx_http_geo_module.c
+++ b/src/http/modules/ngx_http_geo_module.c
@@ -17,7 +17,7 @@ typedef struct {
 
 
 typedef struct {
-    ngx_http_geo_range_t            *low[0x10000];
+    ngx_http_geo_range_t           **low;
     ngx_http_variable_value_t       *default_value;
 } ngx_http_geo_high_ranges_t;
 
@@ -25,26 +25,38 @@ typedef struct {
 typedef struct {
     ngx_str_node_t                   sn;
     ngx_http_variable_value_t       *value;
+    size_t                           offset;
 } ngx_http_geo_variable_value_node_t;
 
 
 typedef struct {
     ngx_http_variable_value_t       *value;
     ngx_str_t                       *net;
-    ngx_http_geo_high_ranges_t      *high;
+    ngx_http_geo_high_ranges_t       high;
     ngx_radix_tree_t                *tree;
     ngx_rbtree_t                     rbtree;
     ngx_rbtree_node_t                sentinel;
     ngx_array_t                     *proxies;
     ngx_pool_t                      *pool;
     ngx_pool_t                      *temp_pool;
+
+    size_t                           data_size;
+
+    ngx_str_t                        include_name;
+    ngx_uint_t                       includes;
+    ngx_uint_t                       entries;
+
+    unsigned                         ranges:1;
+    unsigned                         outside_entries:1;
+    unsigned                         allow_binary_include:1;
+    unsigned                         binary_include:1;
 } ngx_http_geo_conf_ctx_t;
 
 
 typedef struct {
     union {
         ngx_radix_tree_t            *tree;
-        ngx_http_geo_high_ranges_t  *high;
+        ngx_http_geo_high_ranges_t   high;
     } u;
 
     ngx_array_t                     *proxies;
@@ -73,6 +85,13 @@ static char *ngx_http_geo_add_proxy(ngx_conf_t *cf,
     ngx_http_geo_conf_ctx_t *ctx, ngx_cidr_t *cidr);
 static ngx_int_t ngx_http_geo_cidr_value(ngx_conf_t *cf, ngx_str_t *net,
     ngx_cidr_t *cidr);
+static char *ngx_http_geo_include(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
+    ngx_str_t *name);
+static ngx_int_t ngx_http_geo_include_binary_base(ngx_conf_t *cf,
+    ngx_http_geo_conf_ctx_t *ctx, ngx_str_t *name);
+static void ngx_http_geo_create_binary_base(ngx_http_geo_conf_ctx_t *ctx);
+static u_char *ngx_http_geo_copy_values(u_char *base, u_char *p,
+    ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
 
 
 static ngx_command_t  ngx_http_geo_commands[] = {
@@ -119,6 +138,20 @@ ngx_module_t  ngx_http_geo_module = {
 };
 
 
+typedef struct {
+    u_char    GEORNG[6];
+    u_char    version;
+    u_char    ptr_size;
+    uint32_t  endianess;
+    uint32_t  crc32;
+} ngx_http_geo_header_t;
+
+
+static ngx_http_geo_header_t  ngx_http_geo_header = {
+    { 'G', 'E', 'O', 'R', 'N', 'G' }, 0, sizeof(void *), 0x12345678, 0
+};
+
+
 /* AF_INET only */
 
 static ngx_int_t
@@ -151,11 +184,11 @@ ngx_http_geo_range_variable(ngx_http_request_t *r, ngx_http_variable_value_t *v,
     ngx_uint_t             n;
     ngx_http_geo_range_t  *range;
 
-    *v = *ctx->u.high->default_value;
+    *v = *ctx->u.high.default_value;
 
     addr = ngx_http_geo_addr(r, ctx);
 
-    range = ctx->u.high->low[addr >> 16];
+    range = ctx->u.high.low[addr >> 16];
 
     if (range) {
         n = addr & 0xffff;
@@ -304,6 +337,8 @@ ngx_http_geo_block(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
         return NGX_CONF_ERROR;
     }
 
+    ngx_memzero(&ctx, sizeof(ngx_http_geo_conf_ctx_t));
+
     ctx.temp_pool = ngx_create_pool(16384, cf->log);
     if (ctx.temp_pool == NULL) {
         return NGX_CONF_ERROR;
@@ -311,10 +346,11 @@ ngx_http_geo_block(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
 
     ngx_rbtree_init(&ctx.rbtree, &ctx.sentinel, ngx_str_rbtree_insert_value);
 
-    ctx.high = NULL;
-    ctx.tree = NULL;
-    ctx.proxies = NULL;
     ctx.pool = cf->pool;
+    ctx.data_size = sizeof(ngx_http_geo_header_t)
+                  + sizeof(ngx_http_variable_value_t)
+                  + 0x10000 * sizeof(ngx_http_geo_range_t *);
+    ctx.allow_binary_include = 1;
 
     save = *cf;
     cf->pool = pool;
@@ -328,24 +364,35 @@ ngx_http_geo_block(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
 
     geo->proxies = ctx.proxies;
 
-    if (ctx.high) {
+    if (ctx.high.low) {
 
-        for (i = 0; i < 0x10000; i++) {
-            a = (ngx_array_t *) ctx.high->low[i];
+        if (!ctx.binary_include) {
+            for (i = 0; i < 0x10000; i++) {
+                a = (ngx_array_t *) ctx.high.low[i];
 
-            if (a == NULL || a->nelts == 0) {
-                continue;
-            }
+                if (a == NULL || a->nelts == 0) {
+                    continue;
+                }
 
-            len = a->nelts * sizeof(ngx_http_geo_range_t);
+                len = a->nelts * sizeof(ngx_http_geo_range_t);
 
-            ctx.high->low[i] = ngx_palloc(cf->pool, len + sizeof(void *));
-            if (ctx.high->low[i] == NULL) {
-                return NGX_CONF_ERROR;
+                ctx.high.low[i] = ngx_palloc(cf->pool, len + sizeof(void *));
+                if (ctx.high.low[i] == NULL) {
+                    return NGX_CONF_ERROR;
+                }
+
+                p = (void **) ngx_cpymem(ctx.high.low[i], a->elts, len);
+                *p = NULL;
+                ctx.data_size += len + sizeof(void *);
             }
 
-            p = (void **) ngx_cpymem(ctx.high->low[i], a->elts, len);
-            *p = NULL;
+            if (ctx.allow_binary_include
+                && !ctx.outside_entries
+                && ctx.entries > 100000
+                && ctx.includes == 1)
+            {
+                ngx_http_geo_create_binary_base(&ctx);
+            }
         }
 
         geo->u.high = ctx.high;
@@ -353,13 +400,13 @@ ngx_http_geo_block(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
         var->get_handler = ngx_http_geo_range_variable;
         var->data = (uintptr_t) geo;
 
+        if (ctx.high.default_value == NULL) {
+            ctx.high.default_value = &ngx_http_variable_null_value;
+        }
+
         ngx_destroy_pool(ctx.temp_pool);
         ngx_destroy_pool(pool);
 
-        if (ctx.high->default_value == NULL) {
-            ctx.high->default_value = &ngx_http_variable_null_value;
-        }
-
     } else {
         if (ctx.tree == NULL) {
             ctx.tree = ngx_radix_tree_create(cf->pool, -1);
@@ -396,7 +443,7 @@ static char *
 ngx_http_geo(ngx_conf_t *cf, ngx_command_t *dummy, void *conf)
 {
     char                     *rv;
-    ngx_str_t                *value, file;
+    ngx_str_t                *value;
     ngx_cidr_t                cidr;
     ngx_http_geo_conf_ctx_t  *ctx;
 
@@ -415,11 +462,7 @@ ngx_http_geo(ngx_conf_t *cf, ngx_command_t *dummy, void *conf)
                 goto failed;
             }
 
-            ctx->high = ngx_pcalloc(ctx->pool,
-                                    sizeof(ngx_http_geo_high_ranges_t));
-            if (ctx->high == NULL) {
-                goto failed;
-            }
+            ctx->ranges = 1;
 
             rv = NGX_CONF_OK;
 
@@ -435,20 +478,7 @@ ngx_http_geo(ngx_conf_t *cf, ngx_command_t *dummy, void *conf)
 
     if (ngx_strcmp(value[0].data, "include") == 0) {
 
-        file.len = value[1].len++;
-
-        file.data = ngx_pstrdup(ctx->temp_pool, &value[1]);
-        if (file.data == NULL) {
-            goto failed;
-        }
-
-        if (ngx_conf_full_name(cf->cycle, &file, 1) != NGX_OK) {
-            goto failed;
-        }
-
-        ngx_log_debug1(NGX_LOG_DEBUG_CORE, cf->log, 0, "include %s", file.data);
-
-        rv = ngx_conf_parse(cf, &file);
+        rv = ngx_http_geo_include(cf, ctx, &value[1]);
 
         goto done;
 
@@ -463,7 +493,7 @@ ngx_http_geo(ngx_conf_t *cf, ngx_command_t *dummy, void *conf)
         goto done;
     }
 
-    if (ctx->high) {
+    if (ctx->ranges) {
         rv = ngx_http_geo_range(cf, ctx, value);
 
     } else {
@@ -495,20 +525,38 @@ ngx_http_geo_range(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
 
     if (ngx_strcmp(value[0].data, "default") == 0) {
 
-        if (ctx->high->default_value) {
+        if (ctx->high.default_value) {
             ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
                 "duplicate default geo range value: \"%V\", old value: \"%v\"",
-                &value[1], ctx->high->default_value);
+                &value[1], ctx->high.default_value);
         }
 
-        ctx->high->default_value = ngx_http_geo_value(cf, ctx, &value[1]);
-        if (ctx->high->default_value == NULL) {
+        ctx->high.default_value = ngx_http_geo_value(cf, ctx, &value[1]);
+        if (ctx->high.default_value == NULL) {
             return NGX_CONF_ERROR;
         }
 
         return NGX_CONF_OK;
     }
 
+    if (ctx->binary_include) {
+        ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
+            "binary geo range base \"%s\" may not be mixed with usual entries",
+            ctx->include_name.data);
+        return NGX_CONF_ERROR;
+    }
+
+    if (ctx->high.low == NULL) {
+        ctx->high.low = ngx_pcalloc(ctx->pool,
+                                    0x10000 * sizeof(ngx_http_geo_range_t *));
+        if (ctx->high.low == NULL) {
+            return NGX_CONF_ERROR;
+        }
+    }
+
+    ctx->entries++;
+    ctx->outside_entries = 1;
+
     if (ngx_strcmp(value[0].data, "delete") == 0) {
         net = &value[1];
         del = 1;
@@ -603,7 +651,7 @@ ngx_http_geo_add_range(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
             e = 0xffff;
         }
 
-        a = (ngx_array_t *) ctx->high->low[h];
+        a = (ngx_array_t *) ctx->high.low[h];
 
         if (a == NULL) {
             a = ngx_array_create(ctx->temp_pool, 64,
@@ -612,7 +660,7 @@ ngx_http_geo_add_range(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
                 return NGX_CONF_ERROR;
             }
 
-            ctx->high->low[h] = (ngx_http_geo_range_t *) a;
+            ctx->high.low[h] = (ngx_http_geo_range_t *) a;
         }
 
         i = a->nelts;
@@ -800,7 +848,7 @@ ngx_http_geo_delete_range(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
             e = 0xffff;
         }
 
-        a = (ngx_array_t *) ctx->high->low[h];
+        a = (ngx_array_t *) ctx->high.low[h];
 
         if (a == NULL) {
             warn = 1;
@@ -964,9 +1012,13 @@ ngx_http_geo_value(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
     gvvn->sn.str.len = val->len;
     gvvn->sn.str.data = val->data;
     gvvn->value = val;
+    gvvn->offset = 0;
 
     ngx_rbtree_insert(&ctx->rbtree, &gvvn->sn.node);
 
+    ctx->data_size += ngx_align(sizeof(ngx_http_variable_value_t) + value->len,
+                                sizeof(void *));
+
     return val;
 }
 
@@ -1030,3 +1082,306 @@ ngx_http_geo_cidr_value(ngx_conf_t *cf, ngx_str_t *net, ngx_cidr_t *cidr)
 
     return NGX_OK;
 }
+
+
+static char *
+ngx_http_geo_include(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
+    ngx_str_t *name)
+{
+    char       *rv;
+    ngx_str_t   file;
+
+    file.len = name->len + 4;
+    file.data = ngx_pnalloc(ctx->temp_pool, name->len + 5);
+    if (file.data == NULL) {
+        return NGX_CONF_ERROR;
+    }
+
+    ngx_sprintf(file.data, "%V.bin%Z", name);
+
+    if (ngx_conf_full_name(cf->cycle, &file, 1) != NGX_OK) {
+        return NGX_CONF_ERROR;
+    }
+
+    ngx_log_debug1(NGX_LOG_DEBUG_CORE, cf->log, 0, "include %s", file.data);
+
+    switch (ngx_http_geo_include_binary_base(cf, ctx, &file)) {
+    case NGX_OK:
+        return NGX_CONF_OK;
+    case NGX_ERROR:
+        return NGX_CONF_ERROR;
+    default:
+        break;
+    }
+
+    file.len -= 4;
+    file.data[file.len] = '\0';
+
+    ctx->include_name = file;
+
+    if (ctx->outside_entries) {
+        ctx->allow_binary_include = 0;
+    }
+
+    ngx_log_debug1(NGX_LOG_DEBUG_CORE, cf->log, 0, "include %s", file.data);
+
+    rv = ngx_conf_parse(cf, &file);
+
+    ctx->includes++;
+    ctx->outside_entries = 0;
+
+    return rv;
+}
+
+
+static ngx_int_t
+ngx_http_geo_include_binary_base(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
+    ngx_str_t *name)
+{
+    u_char                     *base;
+    size_t                      size, len;
+    ssize_t                     n;
+    uint32_t                    crc32;
+    ngx_err_t                   err;
+    ngx_int_t                   rc;
+    ngx_uint_t                  i;
+    ngx_file_t                  file;
+    ngx_file_info_t             fi;
+    ngx_http_geo_range_t       *range, **ranges;
+    ngx_http_geo_header_t      *header;
+    ngx_http_variable_value_t  *vv;
+
+    ngx_memzero(&file, sizeof(ngx_file_t));
+    file.name = *name;
+    file.log = cf->log;
+
+    file.fd = ngx_open_file(name->data, NGX_FILE_RDONLY, 0, 0);
+    if (file.fd == NGX_INVALID_FILE) {
+        err = ngx_errno;
+        if (err != NGX_ENOENT) {
+            ngx_conf_log_error(NGX_LOG_CRIT, cf, err,
+                               ngx_open_file_n " \"%s\" failed", name->data);
+        }
+        return NGX_DECLINED;
+    }
+
+    if (ctx->outside_entries) {
+        ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
+            "binary geo range base \"%s\" may not be mixed with usual entries",
+            name->data);
+        rc = NGX_ERROR;
+        goto done;
+    }
+
+    if (ngx_fd_info(file.fd, &fi) == NGX_FILE_ERROR) {
+        ngx_conf_log_error(NGX_LOG_CRIT, cf, ngx_errno,
+                           ngx_fd_info_n " \"%s\" failed", name->data);
+        goto failed;
+    }
+
+    size = (size_t) ngx_file_size(&fi);
+
+    base = ngx_palloc(ctx->pool, size);
+    if (base == NULL) {
+        goto failed;
+    }
+
+    n = ngx_read_file(&file, base, size, 0);
+
+    if (n == NGX_ERROR) {
+        ngx_conf_log_error(NGX_LOG_CRIT, cf, ngx_errno,
+                           ngx_read_file_n " \"%s\" failed", name->data);
+        goto failed;
+    }
+
+    if ((size_t) n != size) {
+        ngx_conf_log_error(NGX_LOG_CRIT, cf, 0,
+            ngx_read_file_n " \"%s\" returned only %z bytes instead of %z",
+            name->data, n, size);
+        goto failed;
+    }
+
+    header = (ngx_http_geo_header_t *) base;
+
+    if (ngx_memcmp(&ngx_http_geo_header, header, 12) != 0) {
+        ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
+             "incompatible binary geo range base \"%s\"", name->data);
+        goto failed;
+    }
+
+    ngx_crc32_init(crc32);
+
+    vv = (ngx_http_variable_value_t *) (base + sizeof(ngx_http_geo_header_t));
+
+    while(vv->data) {
+        len = ngx_align(sizeof(ngx_http_variable_value_t) + vv->len,
+                        sizeof(void *));
+        ngx_crc32_update(&crc32, (u_char *) vv, len);
+        vv->data += (size_t) base;
+        vv = (ngx_http_variable_value_t *) ((u_char *) vv + len);
+    }
+    ngx_crc32_update(&crc32, (u_char *) vv, sizeof(ngx_http_variable_value_t));
+    vv++;
+
+    ranges = (ngx_http_geo_range_t **) vv;
+
+    for (i = 0; i < 0x10000; i++) {
+        ngx_crc32_update(&crc32, (u_char *) &ranges[i], sizeof(void *));
+        if (ranges[i]) {
+            ranges[i] = (ngx_http_geo_range_t *)
+                            ((u_char *) ranges[i] + (size_t) base);
+        }
+    }
+
+    range = (ngx_http_geo_range_t *) &ranges[0x10000];
+
+    while ((u_char *) range < base + size) {
+        while (range->value) {
+            ngx_crc32_update(&crc32, (u_char *) range,
+                             sizeof(ngx_http_geo_range_t));
+            range->value = (ngx_http_variable_value_t *)
+                               ((u_char *) range->value + (size_t) base);
+            range++;
+        }
+        ngx_crc32_update(&crc32, (u_char *) range, sizeof(void *));
+        range = (ngx_http_geo_range_t *) ((u_char *) range + sizeof(void *));
+    }
+
+    ngx_crc32_final(crc32);
+
+    if (crc32 != header->crc32) {
+        ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
+                  "CRC32 mismatch in binary geo range base \"%s\"", name->data);
+        goto failed;
+    }
+
+    ngx_conf_log_error(NGX_LOG_NOTICE, cf, 0,
+                       "using binary geo range base \"%s\"", name->data);
+
+    ctx->include_name = *name;
+    ctx->binary_include = 1;
+    ctx->high.low = ranges;
+    rc = NGX_OK;
+
+    goto done;
+
+failed:
+
+    rc = NGX_DECLINED;
+
+done:
+
+    if (ngx_close_file(file.fd) == NGX_FILE_ERROR) {
+        ngx_log_error(NGX_LOG_ALERT, cf->log, ngx_errno,
+                      ngx_close_file_n " \"%s\" failed", name->data);
+    }
+
+    return rc;
+}
+
+
+static void
+ngx_http_geo_create_binary_base(ngx_http_geo_conf_ctx_t *ctx)
+{
+    u_char                              *p;
+    uint32_t                             hash;
+    ngx_str_t                            s;
+    ngx_uint_t                           i;
+    ngx_file_mapping_t                   fm;
+    ngx_http_geo_range_t                *r, *range, **ranges;
+    ngx_http_geo_header_t               *header;
+    ngx_http_geo_variable_value_node_t  *gvvn;
+
+    fm.name = ngx_pnalloc(ctx->temp_pool, ctx->include_name.len + 5);
+    if (fm.name == NULL) {
+        return;
+    }
+
+    ngx_sprintf(fm.name, "%V.bin%Z", &ctx->include_name);
+
+    fm.size = ctx->data_size;
+    fm.log = ctx->pool->log;
+
+    ngx_log_error(NGX_LOG_NOTICE, fm.log, 0,
+                  "creating binary geo range base \"%s\"", fm.name);
+
+    if (ngx_create_file_mapping(&fm) != NGX_OK) {
+        return;
+    }
+
+    p = ngx_cpymem(fm.addr, &ngx_http_geo_header,
+                   sizeof(ngx_http_geo_header_t));
+
+    p = ngx_http_geo_copy_values(fm.addr, p, ctx->rbtree.root,
+                                 ctx->rbtree.sentinel);
+
+    p += sizeof(ngx_http_variable_value_t);
+
+    ranges = (ngx_http_geo_range_t **) p;
+
+    p += 0x10000 * sizeof(ngx_http_geo_range_t *);
+
+    for (i = 0; i < 0x10000; i++) {
+        r = ctx->high.low[i];
+        if (r == NULL) {
+            continue;
+        }
+
+        range = (ngx_http_geo_range_t *) p;
+        ranges[i] = (ngx_http_geo_range_t *) (p - (u_char *) fm.addr);
+
+        do {
+            s.len = r->value->len;
+            s.data = r->value->data;
+            hash = ngx_crc32_long(s.data, s.len);
+            gvvn = (ngx_http_geo_variable_value_node_t *)
+                        ngx_str_rbtree_lookup(&ctx->rbtree, &s, hash);
+
+            range->value = (ngx_http_variable_value_t *) gvvn->offset;
+            range->start = r->start;
+            range->end = r->end;
+            range++;
+
+        } while ((++r)->value);
+
+        range->value = NULL;
+
+        p = (u_char *) range + sizeof(void *);
+    }
+
+    header = fm.addr;
+    header->crc32 = ngx_crc32_long((u_char *) fm.addr
+                                       + sizeof(ngx_http_geo_header_t),
+                                   fm.size - sizeof(ngx_http_geo_header_t));
+
+    ngx_close_file_mapping(&fm);
+}
+
+
+static u_char *
+ngx_http_geo_copy_values(u_char *base, u_char *p, ngx_rbtree_node_t *node,
+    ngx_rbtree_node_t *sentinel)
+{
+    ngx_http_variable_value_t           *vv;
+    ngx_http_geo_variable_value_node_t  *gvvn;
+
+    if (node == sentinel) {
+        return p;
+    }
+
+    gvvn = (ngx_http_geo_variable_value_node_t *) node;
+    gvvn->offset = p - base;
+
+    vv = (ngx_http_variable_value_t *) p;
+    *vv = *gvvn->value;
+    p += sizeof(ngx_http_variable_value_t);
+    vv->data = (u_char *) (p - base);
+
+    p = ngx_cpymem(p, gvvn->sn.str.data, gvvn->sn.str.len);
+
+    p = ngx_align_ptr(p, sizeof(void *));
+
+    p = ngx_http_geo_copy_values(base, p, node->left, sentinel);
+
+    return ngx_http_geo_copy_values(base, p, node->right, sentinel);
+}