1
2/*
3 * Copyright (C) Igor Sysoev
4 * Copyright (C) Nginx, Inc.
5 */
6
7
8#include <ngx_config.h>
9#include <ngx_core.h>
10#include <ngx_http.h>
11
12
13typedef struct {
14    ngx_http_variable_value_t       *value;
15    u_short                          start;
16    u_short                          end;
17} ngx_http_geo_range_t;
18
19
20typedef struct {
21    ngx_radix_tree_t                *tree;
22#if (NGX_HAVE_INET6)
23    ngx_radix_tree_t                *tree6;
24#endif
25} ngx_http_geo_trees_t;
26
27
28typedef struct {
29    ngx_http_geo_range_t           **low;
30    ngx_http_variable_value_t       *default_value;
31} ngx_http_geo_high_ranges_t;
32
33
34typedef struct {
35    ngx_str_node_t                   sn;
36    ngx_http_variable_value_t       *value;
37    size_t                           offset;
38} ngx_http_geo_variable_value_node_t;
39
40
41typedef struct {
42    ngx_http_variable_value_t       *value;
43    ngx_str_t                       *net;
44    ngx_http_geo_high_ranges_t       high;
45    ngx_radix_tree_t                *tree;
46#if (NGX_HAVE_INET6)
47    ngx_radix_tree_t                *tree6;
48#endif
49    ngx_rbtree_t                     rbtree;
50    ngx_rbtree_node_t                sentinel;
51    ngx_array_t                     *proxies;
52    ngx_pool_t                      *pool;
53    ngx_pool_t                      *temp_pool;
54
55    size_t                           data_size;
56
57    ngx_str_t                        include_name;
58    ngx_uint_t                       includes;
59    ngx_uint_t                       entries;
60
61    unsigned                         ranges:1;
62    unsigned                         outside_entries:1;
63    unsigned                         allow_binary_include:1;
64    unsigned                         binary_include:1;
65    unsigned                         proxy_recursive:1;
66} ngx_http_geo_conf_ctx_t;
67
68
69typedef struct {
70    union {
71        ngx_http_geo_trees_t         trees;
72        ngx_http_geo_high_ranges_t   high;
73    } u;
74
75    ngx_array_t                     *proxies;
76    unsigned                         proxy_recursive:1;
77
78    ngx_int_t                        index;
79} ngx_http_geo_ctx_t;
80
81
82static ngx_int_t ngx_http_geo_addr(ngx_http_request_t *r,
83    ngx_http_geo_ctx_t *ctx, ngx_addr_t *addr);
84static ngx_int_t ngx_http_geo_real_addr(ngx_http_request_t *r,
85    ngx_http_geo_ctx_t *ctx, ngx_addr_t *addr);
86static char *ngx_http_geo_block(ngx_conf_t *cf, ngx_command_t *cmd, void *conf);
87static char *ngx_http_geo(ngx_conf_t *cf, ngx_command_t *dummy, void *conf);
88static char *ngx_http_geo_range(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
89    ngx_str_t *value);
90static char *ngx_http_geo_add_range(ngx_conf_t *cf,
91    ngx_http_geo_conf_ctx_t *ctx, in_addr_t start, in_addr_t end);
92static ngx_uint_t ngx_http_geo_delete_range(ngx_conf_t *cf,
93    ngx_http_geo_conf_ctx_t *ctx, in_addr_t start, in_addr_t end);
94static char *ngx_http_geo_cidr(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
95    ngx_str_t *value);
96static char *ngx_http_geo_cidr_add(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
97    ngx_cidr_t *cidr, ngx_str_t *value, ngx_str_t *net);
98static ngx_http_variable_value_t *ngx_http_geo_value(ngx_conf_t *cf,
99    ngx_http_geo_conf_ctx_t *ctx, ngx_str_t *value);
100static char *ngx_http_geo_add_proxy(ngx_conf_t *cf,
101    ngx_http_geo_conf_ctx_t *ctx, ngx_cidr_t *cidr);
102static ngx_int_t ngx_http_geo_cidr_value(ngx_conf_t *cf, ngx_str_t *net,
103    ngx_cidr_t *cidr);
104static char *ngx_http_geo_include(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
105    ngx_str_t *name);
106static ngx_int_t ngx_http_geo_include_binary_base(ngx_conf_t *cf,
107    ngx_http_geo_conf_ctx_t *ctx, ngx_str_t *name);
108static void ngx_http_geo_create_binary_base(ngx_http_geo_conf_ctx_t *ctx);
109static u_char *ngx_http_geo_copy_values(u_char *base, u_char *p,
110    ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
111
112
113static ngx_command_t  ngx_http_geo_commands[] = {
114
115    { ngx_string("geo"),
116      NGX_HTTP_MAIN_CONF|NGX_CONF_BLOCK|NGX_CONF_TAKE12,
117      ngx_http_geo_block,
118      NGX_HTTP_MAIN_CONF_OFFSET,
119      0,
120      NULL },
121
122      ngx_null_command
123};
124
125
126static ngx_http_module_t  ngx_http_geo_module_ctx = {
127    NULL,                                  /* preconfiguration */
128    NULL,                                  /* postconfiguration */
129
130    NULL,                                  /* create main configuration */
131    NULL,                                  /* init main configuration */
132
133    NULL,                                  /* create server configuration */
134    NULL,                                  /* merge server configuration */
135
136    NULL,                                  /* create location configuration */
137    NULL                                   /* merge location configuration */
138};
139
140
141ngx_module_t  ngx_http_geo_module = {
142    NGX_MODULE_V1,
143    &ngx_http_geo_module_ctx,              /* module context */
144    ngx_http_geo_commands,                 /* module directives */
145    NGX_HTTP_MODULE,                       /* module type */
146    NULL,                                  /* init master */
147    NULL,                                  /* init module */
148    NULL,                                  /* init process */
149    NULL,                                  /* init thread */
150    NULL,                                  /* exit thread */
151    NULL,                                  /* exit process */
152    NULL,                                  /* exit master */
153    NGX_MODULE_V1_PADDING
154};
155
156
157typedef struct {
158    u_char    GEORNG[6];
159    u_char    version;
160    u_char    ptr_size;
161    uint32_t  endianness;
162    uint32_t  crc32;
163} ngx_http_geo_header_t;
164
165
166static ngx_http_geo_header_t  ngx_http_geo_header = {
167    { 'G', 'E', 'O', 'R', 'N', 'G' }, 0, sizeof(void *), 0x12345678, 0
168};
169
170
171/* geo range is AF_INET only */
172
173static ngx_int_t
174ngx_http_geo_cidr_variable(ngx_http_request_t *r, ngx_http_variable_value_t *v,
175    uintptr_t data)
176{
177    ngx_http_geo_ctx_t *ctx = (ngx_http_geo_ctx_t *) data;
178
179    in_addr_t                   inaddr;
180    ngx_addr_t                  addr;
181    struct sockaddr_in         *sin;
182    ngx_http_variable_value_t  *vv;
183#if (NGX_HAVE_INET6)
184    u_char                     *p;
185    struct in6_addr            *inaddr6;
186#endif
187
188    if (ngx_http_geo_addr(r, ctx, &addr) != NGX_OK) {
189        vv = (ngx_http_variable_value_t *)
190                  ngx_radix32tree_find(ctx->u.trees.tree, INADDR_NONE);
191        goto done;
192    }
193
194    switch (addr.sockaddr->sa_family) {
195
196#if (NGX_HAVE_INET6)
197    case AF_INET6:
198        inaddr6 = &((struct sockaddr_in6 *) addr.sockaddr)->sin6_addr;
199        p = inaddr6->s6_addr;
200
201        if (IN6_IS_ADDR_V4MAPPED(inaddr6)) {
202            inaddr = p[12] << 24;
203            inaddr += p[13] << 16;
204            inaddr += p[14] << 8;
205            inaddr += p[15];
206
207            vv = (ngx_http_variable_value_t *)
208                      ngx_radix32tree_find(ctx->u.trees.tree, inaddr);
209
210        } else {
211            vv = (ngx_http_variable_value_t *)
212                      ngx_radix128tree_find(ctx->u.trees.tree6, p);
213        }
214
215        break;
216#endif
217
218    default: /* AF_INET */
219        sin = (struct sockaddr_in *) addr.sockaddr;
220        inaddr = ntohl(sin->sin_addr.s_addr);
221
222        vv = (ngx_http_variable_value_t *)
223                  ngx_radix32tree_find(ctx->u.trees.tree, inaddr);
224
225        break;
226    }
227
228done:
229
230    *v = *vv;
231
232    ngx_log_debug1(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
233                   "http geo: %v", v);
234
235    return NGX_OK;
236}
237
238
239static ngx_int_t
240ngx_http_geo_range_variable(ngx_http_request_t *r, ngx_http_variable_value_t *v,
241    uintptr_t data)
242{
243    ngx_http_geo_ctx_t *ctx = (ngx_http_geo_ctx_t *) data;
244
245    in_addr_t              inaddr;
246    ngx_addr_t             addr;
247    ngx_uint_t             n;
248    struct sockaddr_in    *sin;
249    ngx_http_geo_range_t  *range;
250#if (NGX_HAVE_INET6)
251    u_char                *p;
252    struct in6_addr       *inaddr6;
253#endif
254
255    *v = *ctx->u.high.default_value;
256
257    if (ngx_http_geo_addr(r, ctx, &addr) == NGX_OK) {
258
259        switch (addr.sockaddr->sa_family) {
260
261#if (NGX_HAVE_INET6)
262        case AF_INET6:
263            inaddr6 = &((struct sockaddr_in6 *) addr.sockaddr)->sin6_addr;
264
265            if (IN6_IS_ADDR_V4MAPPED(inaddr6)) {
266                p = inaddr6->s6_addr;
267
268                inaddr = p[12] << 24;
269                inaddr += p[13] << 16;
270                inaddr += p[14] << 8;
271                inaddr += p[15];
272
273            } else {
274                inaddr = INADDR_NONE;
275            }
276
277            break;
278#endif
279
280        default: /* AF_INET */
281            sin = (struct sockaddr_in *) addr.sockaddr;
282            inaddr = ntohl(sin->sin_addr.s_addr);
283            break;
284        }
285
286    } else {
287        inaddr = INADDR_NONE;
288    }
289
290    if (ctx->u.high.low) {
291        range = ctx->u.high.low[inaddr >> 16];
292
293        if (range) {
294            n = inaddr & 0xffff;
295            do {
296                if (n >= (ngx_uint_t) range->start
297                    && n <= (ngx_uint_t) range->end)
298                {
299                    *v = *range->value;
300                    break;
301                }
302            } while ((++range)->value);
303        }
304    }
305
306    ngx_log_debug1(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
307                   "http geo: %v", v);
308
309    return NGX_OK;
310}
311
312
313static ngx_int_t
314ngx_http_geo_addr(ngx_http_request_t *r, ngx_http_geo_ctx_t *ctx,
315    ngx_addr_t *addr)
316{
317    ngx_array_t  *xfwd;
318
319    if (ngx_http_geo_real_addr(r, ctx, addr) != NGX_OK) {
320        return NGX_ERROR;
321    }
322
323    xfwd = &r->headers_in.x_forwarded_for;
324
325    if (xfwd->nelts > 0 && ctx->proxies != NULL) {
326        (void) ngx_http_get_forwarded_addr(r, addr, xfwd, NULL,
327                                           ctx->proxies, ctx->proxy_recursive);
328    }
329
330    return NGX_OK;
331}
332
333
334static ngx_int_t
335ngx_http_geo_real_addr(ngx_http_request_t *r, ngx_http_geo_ctx_t *ctx,
336    ngx_addr_t *addr)
337{
338    ngx_http_variable_value_t  *v;
339
340    if (ctx->index == -1) {
341        ngx_log_debug1(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
342                       "http geo started: %V", &r->connection->addr_text);
343
344        addr->sockaddr = r->connection->sockaddr;
345        addr->socklen = r->connection->socklen;
346        /* addr->name = r->connection->addr_text; */
347
348        return NGX_OK;
349    }
350
351    v = ngx_http_get_flushed_variable(r, ctx->index);
352
353    if (v == NULL || v->not_found) {
354        ngx_log_debug0(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
355                       "http geo not found");
356
357        return NGX_ERROR;
358    }
359
360    ngx_log_debug1(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
361                   "http geo started: %v", v);
362
363    if (ngx_parse_addr(r->pool, addr, v->data, v->len) == NGX_OK) {
364        return NGX_OK;
365    }
366
367    return NGX_ERROR;
368}
369
370
371static char *
372ngx_http_geo_block(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
373{
374    char                     *rv;
375    size_t                    len;
376    ngx_str_t                *value, name;
377    ngx_uint_t                i;
378    ngx_conf_t                save;
379    ngx_pool_t               *pool;
380    ngx_array_t              *a;
381    ngx_http_variable_t      *var;
382    ngx_http_geo_ctx_t       *geo;
383    ngx_http_geo_conf_ctx_t   ctx;
384#if (NGX_HAVE_INET6)
385    static struct in6_addr    zero;
386#endif
387
388    value = cf->args->elts;
389
390    geo = ngx_palloc(cf->pool, sizeof(ngx_http_geo_ctx_t));
391    if (geo == NULL) {
392        return NGX_CONF_ERROR;
393    }
394
395    name = value[1];
396
397    if (name.data[0] != '$') {
398        ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
399                           "invalid variable name \"%V\"", &name);
400        return NGX_CONF_ERROR;
401    }
402
403    name.len--;
404    name.data++;
405
406    if (cf->args->nelts == 3) {
407
408        geo->index = ngx_http_get_variable_index(cf, &name);
409        if (geo->index == NGX_ERROR) {
410            return NGX_CONF_ERROR;
411        }
412
413        name = value[2];
414
415        if (name.data[0] != '$') {
416            ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
417                               "invalid variable name \"%V\"", &name);
418            return NGX_CONF_ERROR;
419        }
420
421        name.len--;
422        name.data++;
423
424    } else {
425        geo->index = -1;
426    }
427
428    var = ngx_http_add_variable(cf, &name, NGX_HTTP_VAR_CHANGEABLE);
429    if (var == NULL) {
430        return NGX_CONF_ERROR;
431    }
432
433    pool = ngx_create_pool(NGX_DEFAULT_POOL_SIZE, cf->log);
434    if (pool == NULL) {
435        return NGX_CONF_ERROR;
436    }
437
438    ngx_memzero(&ctx, sizeof(ngx_http_geo_conf_ctx_t));
439
440    ctx.temp_pool = ngx_create_pool(NGX_DEFAULT_POOL_SIZE, cf->log);
441    if (ctx.temp_pool == NULL) {
442        return NGX_CONF_ERROR;
443    }
444
445    ngx_rbtree_init(&ctx.rbtree, &ctx.sentinel, ngx_str_rbtree_insert_value);
446
447    ctx.pool = cf->pool;
448    ctx.data_size = sizeof(ngx_http_geo_header_t)
449                  + sizeof(ngx_http_variable_value_t)
450                  + 0x10000 * sizeof(ngx_http_geo_range_t *);
451    ctx.allow_binary_include = 1;
452
453    save = *cf;
454    cf->pool = pool;
455    cf->ctx = &ctx;
456    cf->handler = ngx_http_geo;
457    cf->handler_conf = conf;
458
459    rv = ngx_conf_parse(cf, NULL);
460
461    *cf = save;
462
463    geo->proxies = ctx.proxies;
464    geo->proxy_recursive = ctx.proxy_recursive;
465
466    if (ctx.ranges) {
467
468        if (ctx.high.low && !ctx.binary_include) {
469            for (i = 0; i < 0x10000; i++) {
470                a = (ngx_array_t *) ctx.high.low[i];
471
472                if (a == NULL) {
473                    continue;
474                }
475
476                if (a->nelts == 0) {
477                    ctx.high.low[i] = NULL;
478                    continue;
479                }
480
481                len = a->nelts * sizeof(ngx_http_geo_range_t);
482
483                ctx.high.low[i] = ngx_palloc(cf->pool, len + sizeof(void *));
484                if (ctx.high.low[i] == NULL) {
485                    return NGX_CONF_ERROR;
486                }
487
488                ngx_memcpy(ctx.high.low[i], a->elts, len);
489                ctx.high.low[i][a->nelts].value = NULL;
490                ctx.data_size += len + sizeof(void *);
491            }
492
493            if (ctx.allow_binary_include
494                && !ctx.outside_entries
495                && ctx.entries > 100000
496                && ctx.includes == 1)
497            {
498                ngx_http_geo_create_binary_base(&ctx);
499            }
500        }
501
502        if (ctx.high.default_value == NULL) {
503            ctx.high.default_value = &ngx_http_variable_null_value;
504        }
505
506        geo->u.high = ctx.high;
507
508        var->get_handler = ngx_http_geo_range_variable;
509        var->data = (uintptr_t) geo;
510
511        ngx_destroy_pool(ctx.temp_pool);
512        ngx_destroy_pool(pool);
513
514    } else {
515        if (ctx.tree == NULL) {
516            ctx.tree = ngx_radix_tree_create(cf->pool, -1);
517            if (ctx.tree == NULL) {
518                return NGX_CONF_ERROR;
519            }
520        }
521
522        geo->u.trees.tree = ctx.tree;
523
524#if (NGX_HAVE_INET6)
525        if (ctx.tree6 == NULL) {
526            ctx.tree6 = ngx_radix_tree_create(cf->pool, -1);
527            if (ctx.tree6 == NULL) {
528                return NGX_CONF_ERROR;
529            }
530        }
531
532        geo->u.trees.tree6 = ctx.tree6;
533#endif
534
535        var->get_handler = ngx_http_geo_cidr_variable;
536        var->data = (uintptr_t) geo;
537
538        ngx_destroy_pool(ctx.temp_pool);
539        ngx_destroy_pool(pool);
540
541        if (ngx_radix32tree_insert(ctx.tree, 0, 0,
542                                   (uintptr_t) &ngx_http_variable_null_value)
543            == NGX_ERROR)
544        {
545            return NGX_CONF_ERROR;
546        }
547
548        /* NGX_BUSY is okay (default was set explicitly) */
549
550#if (NGX_HAVE_INET6)
551        if (ngx_radix128tree_insert(ctx.tree6, zero.s6_addr, zero.s6_addr,
552                                    (uintptr_t) &ngx_http_variable_null_value)
553            == NGX_ERROR)
554        {
555            return NGX_CONF_ERROR;
556        }
557#endif
558    }
559
560    return rv;
561}
562
563
564static char *
565ngx_http_geo(ngx_conf_t *cf, ngx_command_t *dummy, void *conf)
566{
567    char                     *rv;
568    ngx_str_t                *value;
569    ngx_cidr_t                cidr;
570    ngx_http_geo_conf_ctx_t  *ctx;
571
572    ctx = cf->ctx;
573
574    value = cf->args->elts;
575
576    if (cf->args->nelts == 1) {
577
578        if (ngx_strcmp(value[0].data, "ranges") == 0) {
579
580            if (ctx->tree
581#if (NGX_HAVE_INET6)
582                || ctx->tree6
583#endif
584               )
585            {
586                ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
587                                   "the \"ranges\" directive must be "
588                                   "the first directive inside \"geo\" block");
589                goto failed;
590            }
591
592            ctx->ranges = 1;
593
594            rv = NGX_CONF_OK;
595
596            goto done;
597        }
598
599        else if (ngx_strcmp(value[0].data, "proxy_recursive") == 0) {
600            ctx->proxy_recursive = 1;
601            rv = NGX_CONF_OK;
602            goto done;
603        }
604    }
605
606    if (cf->args->nelts != 2) {
607        ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
608                           "invalid number of the geo parameters");
609        goto failed;
610    }
611
612    if (ngx_strcmp(value[0].data, "include") == 0) {
613
614        rv = ngx_http_geo_include(cf, ctx, &value[1]);
615
616        goto done;
617
618    } else if (ngx_strcmp(value[0].data, "proxy") == 0) {
619
620        if (ngx_http_geo_cidr_value(cf, &value[1], &cidr) != NGX_OK) {
621            goto failed;
622        }
623
624        rv = ngx_http_geo_add_proxy(cf, ctx, &cidr);
625
626        goto done;
627    }
628
629    if (ctx->ranges) {
630        rv = ngx_http_geo_range(cf, ctx, value);
631
632    } else {
633        rv = ngx_http_geo_cidr(cf, ctx, value);
634    }
635
636done:
637
638    ngx_reset_pool(cf->pool);
639
640    return rv;
641
642failed:
643
644    ngx_reset_pool(cf->pool);
645
646    return NGX_CONF_ERROR;
647}
648
649
650static char *
651ngx_http_geo_range(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
652    ngx_str_t *value)
653{
654    u_char      *p, *last;
655    in_addr_t    start, end;
656    ngx_str_t   *net;
657    ngx_uint_t   del;
658
659    if (ngx_strcmp(value[0].data, "default") == 0) {
660
661        if (ctx->high.default_value) {
662            ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
663                "duplicate default geo range value: \"%V\", old value: \"%v\"",
664                &value[1], ctx->high.default_value);
665        }
666
667        ctx->high.default_value = ngx_http_geo_value(cf, ctx, &value[1]);
668        if (ctx->high.default_value == NULL) {
669            return NGX_CONF_ERROR;
670        }
671
672        return NGX_CONF_OK;
673    }
674
675    if (ctx->binary_include) {
676        ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
677            "binary geo range base \"%s\" cannot be mixed with usual entries",
678            ctx->include_name.data);
679        return NGX_CONF_ERROR;
680    }
681
682    if (ctx->high.low == NULL) {
683        ctx->high.low = ngx_pcalloc(ctx->pool,
684                                    0x10000 * sizeof(ngx_http_geo_range_t *));
685        if (ctx->high.low == NULL) {
686            return NGX_CONF_ERROR;
687        }
688    }
689
690    ctx->entries++;
691    ctx->outside_entries = 1;
692
693    if (ngx_strcmp(value[0].data, "delete") == 0) {
694        net = &value[1];
695        del = 1;
696
697    } else {
698        net = &value[0];
699        del = 0;
700    }
701
702    last = net->data + net->len;
703
704    p = ngx_strlchr(net->data, last, '-');
705
706    if (p == NULL) {
707        goto invalid;
708    }
709
710    start = ngx_inet_addr(net->data, p - net->data);
711
712    if (start == INADDR_NONE) {
713        goto invalid;
714    }
715
716    start = ntohl(start);
717
718    p++;
719
720    end = ngx_inet_addr(p, last - p);
721
722    if (end == INADDR_NONE) {
723        goto invalid;
724    }
725
726    end = ntohl(end);
727
728    if (start > end) {
729        goto invalid;
730    }
731
732    if (del) {
733        if (ngx_http_geo_delete_range(cf, ctx, start, end)) {
734            ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
735                               "no address range \"%V\" to delete", net);
736        }
737
738        return NGX_CONF_OK;
739    }
740
741    ctx->value = ngx_http_geo_value(cf, ctx, &value[1]);
742
743    if (ctx->value == NULL) {
744        return NGX_CONF_ERROR;
745    }
746
747    ctx->net = net;
748
749    return ngx_http_geo_add_range(cf, ctx, start, end);
750
751invalid:
752
753    ngx_conf_log_error(NGX_LOG_EMERG, cf, 0, "invalid range \"%V\"", net);
754
755    return NGX_CONF_ERROR;
756}
757
758
759/* the add procedure is optimized to add a growing up sequence */
760
761static char *
762ngx_http_geo_add_range(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
763    in_addr_t start, in_addr_t end)
764{
765    in_addr_t              n;
766    ngx_uint_t             h, i, s, e;
767    ngx_array_t           *a;
768    ngx_http_geo_range_t  *range;
769
770    for (n = start; n <= end; n = (n + 0x10000) & 0xffff0000) {
771
772        h = n >> 16;
773
774        if (n == start) {
775            s = n & 0xffff;
776        } else {
777            s = 0;
778        }
779
780        if ((n | 0xffff) > end) {
781            e = end & 0xffff;
782
783        } else {
784            e = 0xffff;
785        }
786
787        a = (ngx_array_t *) ctx->high.low[h];
788
789        if (a == NULL) {
790            a = ngx_array_create(ctx->temp_pool, 64,
791                                 sizeof(ngx_http_geo_range_t));
792            if (a == NULL) {
793                return NGX_CONF_ERROR;
794            }
795
796            ctx->high.low[h] = (ngx_http_geo_range_t *) a;
797        }
798
799        i = a->nelts;
800        range = a->elts;
801
802        while (i) {
803
804            i--;
805
806            if (e < (ngx_uint_t) range[i].start) {
807                continue;
808            }
809
810            if (s > (ngx_uint_t) range[i].end) {
811
812                /* add after the range */
813
814                range = ngx_array_push(a);
815                if (range == NULL) {
816                    return NGX_CONF_ERROR;
817                }
818
819                range = a->elts;
820
821                ngx_memmove(&range[i + 2], &range[i + 1],
822                            (a->nelts - 2 - i) * sizeof(ngx_http_geo_range_t));
823
824                range[i + 1].start = (u_short) s;
825                range[i + 1].end = (u_short) e;
826                range[i + 1].value = ctx->value;
827
828                goto next;
829            }
830
831            if (s == (ngx_uint_t) range[i].start
832                && e == (ngx_uint_t) range[i].end)
833            {
834                ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
835                    "duplicate range \"%V\", value: \"%v\", old value: \"%v\"",
836                    ctx->net, ctx->value, range[i].value);
837
838                range[i].value = ctx->value;
839
840                goto next;
841            }
842
843            if (s > (ngx_uint_t) range[i].start
844                && e < (ngx_uint_t) range[i].end)
845            {
846                /* split the range and insert the new one */
847
848                range = ngx_array_push(a);
849                if (range == NULL) {
850                    return NGX_CONF_ERROR;
851                }
852
853                range = ngx_array_push(a);
854                if (range == NULL) {
855                    return NGX_CONF_ERROR;
856                }
857
858                range = a->elts;
859
860                ngx_memmove(&range[i + 3], &range[i + 1],
861                            (a->nelts - 3 - i) * sizeof(ngx_http_geo_range_t));
862
863                range[i + 2].start = (u_short) (e + 1);
864                range[i + 2].end = range[i].end;
865                range[i + 2].value = range[i].value;
866
867                range[i + 1].start = (u_short) s;
868                range[i + 1].end = (u_short) e;
869                range[i + 1].value = ctx->value;
870
871                range[i].end = (u_short) (s - 1);
872
873                goto next;
874            }
875
876            if (s == (ngx_uint_t) range[i].start
877                && e < (ngx_uint_t) range[i].end)
878            {
879                /* shift the range start and insert the new range */
880
881                range = ngx_array_push(a);
882                if (range == NULL) {
883                    return NGX_CONF_ERROR;
884                }
885
886                range = a->elts;
887
888                ngx_memmove(&range[i + 1], &range[i],
889                            (a->nelts - 1 - i) * sizeof(ngx_http_geo_range_t));
890
891                range[i + 1].start = (u_short) (e + 1);
892
893                range[i].start = (u_short) s;
894                range[i].end = (u_short) e;
895                range[i].value = ctx->value;
896
897                goto next;
898            }
899
900            if (s > (ngx_uint_t) range[i].start
901                && e == (ngx_uint_t) range[i].end)
902            {
903                /* shift the range end and insert the new range */
904
905                range = ngx_array_push(a);
906                if (range == NULL) {
907                    return NGX_CONF_ERROR;
908                }
909
910                range = a->elts;
911
912                ngx_memmove(&range[i + 2], &range[i + 1],
913                            (a->nelts - 2 - i) * sizeof(ngx_http_geo_range_t));
914
915                range[i + 1].start = (u_short) s;
916                range[i + 1].end = (u_short) e;
917                range[i + 1].value = ctx->value;
918
919                range[i].end = (u_short) (s - 1);
920
921                goto next;
922            }
923
924            s = (ngx_uint_t) range[i].start;
925            e = (ngx_uint_t) range[i].end;
926
927            ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
928                         "range \"%V\" overlaps \"%d.%d.%d.%d-%d.%d.%d.%d\"",
929                         ctx->net,
930                         h >> 8, h & 0xff, s >> 8, s & 0xff,
931                         h >> 8, h & 0xff, e >> 8, e & 0xff);
932
933            return NGX_CONF_ERROR;
934        }
935
936        /* add the first range */
937
938        range = ngx_array_push(a);
939        if (range == NULL) {
940            return NGX_CONF_ERROR;
941        }
942
943        range = a->elts;
944
945        ngx_memmove(&range[1], &range[0],
946                    (a->nelts - 1) * sizeof(ngx_http_geo_range_t));
947
948        range[0].start = (u_short) s;
949        range[0].end = (u_short) e;
950        range[0].value = ctx->value;
951
952    next:
953
954        if (h == 0xffff) {
955            break;
956        }
957    }
958
959    return NGX_CONF_OK;
960}
961
962
963static ngx_uint_t
964ngx_http_geo_delete_range(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
965    in_addr_t start, in_addr_t end)
966{
967    in_addr_t              n;
968    ngx_uint_t             h, i, s, e, warn;
969    ngx_array_t           *a;
970    ngx_http_geo_range_t  *range;
971
972    warn = 0;
973
974    for (n = start; n <= end; n = (n + 0x10000) & 0xffff0000) {
975
976        h = n >> 16;
977
978        if (n == start) {
979            s = n & 0xffff;
980        } else {
981            s = 0;
982        }
983
984        if ((n | 0xffff) > end) {
985            e = end & 0xffff;
986
987        } else {
988            e = 0xffff;
989        }
990
991        a = (ngx_array_t *) ctx->high.low[h];
992
993        if (a == NULL || a->nelts == 0) {
994            warn = 1;
995            goto next;
996        }
997
998        range = a->elts;
999        for (i = 0; i < a->nelts; i++) {
1000
1001            if (s == (ngx_uint_t) range[i].start
1002                && e == (ngx_uint_t) range[i].end)
1003            {
1004                ngx_memmove(&range[i], &range[i + 1],
1005                            (a->nelts - 1 - i) * sizeof(ngx_http_geo_range_t));
1006
1007                a->nelts--;
1008
1009                break;
1010            }
1011
1012            if (i == a->nelts - 1) {
1013                warn = 1;
1014            }
1015        }
1016
1017    next:
1018
1019        if (h == 0xffff) {
1020            break;
1021        }
1022    }
1023
1024    return warn;
1025}
1026
1027
1028static char *
1029ngx_http_geo_cidr(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
1030    ngx_str_t *value)
1031{
1032    char        *rv;
1033    ngx_int_t    rc, del;
1034    ngx_str_t   *net;
1035    ngx_cidr_t   cidr;
1036
1037    if (ctx->tree == NULL) {
1038        ctx->tree = ngx_radix_tree_create(ctx->pool, -1);
1039        if (ctx->tree == NULL) {
1040            return NGX_CONF_ERROR;
1041        }
1042    }
1043
1044#if (NGX_HAVE_INET6)
1045    if (ctx->tree6 == NULL) {
1046        ctx->tree6 = ngx_radix_tree_create(ctx->pool, -1);
1047        if (ctx->tree6 == NULL) {
1048            return NGX_CONF_ERROR;
1049        }
1050    }
1051#endif
1052
1053    if (ngx_strcmp(value[0].data, "default") == 0) {
1054        cidr.family = AF_INET;
1055        cidr.u.in.addr = 0;
1056        cidr.u.in.mask = 0;
1057
1058        rv = ngx_http_geo_cidr_add(cf, ctx, &cidr, &value[1], &value[0]);
1059
1060        if (rv != NGX_CONF_OK) {
1061            return rv;
1062        }
1063
1064#if (NGX_HAVE_INET6)
1065        cidr.family = AF_INET6;
1066        ngx_memzero(&cidr.u.in6, sizeof(ngx_in6_cidr_t));
1067
1068        rv = ngx_http_geo_cidr_add(cf, ctx, &cidr, &value[1], &value[0]);
1069
1070        if (rv != NGX_CONF_OK) {
1071            return rv;
1072        }
1073#endif
1074
1075        return NGX_CONF_OK;
1076    }
1077
1078    if (ngx_strcmp(value[0].data, "delete") == 0) {
1079        net = &value[1];
1080        del = 1;
1081
1082    } else {
1083        net = &value[0];
1084        del = 0;
1085    }
1086
1087    if (ngx_http_geo_cidr_value(cf, net, &cidr) != NGX_OK) {
1088        return NGX_CONF_ERROR;
1089    }
1090
1091    if (cidr.family == AF_INET) {
1092        cidr.u.in.addr = ntohl(cidr.u.in.addr);
1093        cidr.u.in.mask = ntohl(cidr.u.in.mask);
1094    }
1095
1096    if (del) {
1097        switch (cidr.family) {
1098
1099#if (NGX_HAVE_INET6)
1100        case AF_INET6:
1101            rc = ngx_radix128tree_delete(ctx->tree6,
1102                                         cidr.u.in6.addr.s6_addr,
1103                                         cidr.u.in6.mask.s6_addr);
1104            break;
1105#endif
1106
1107        default: /* AF_INET */
1108            rc = ngx_radix32tree_delete(ctx->tree, cidr.u.in.addr,
1109                                        cidr.u.in.mask);
1110            break;
1111        }
1112
1113        if (rc != NGX_OK) {
1114            ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
1115                               "no network \"%V\" to delete", net);
1116        }
1117
1118        return NGX_CONF_OK;
1119    }
1120
1121    return ngx_http_geo_cidr_add(cf, ctx, &cidr, &value[1], net);
1122}
1123
1124
1125static char *
1126ngx_http_geo_cidr_add(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
1127    ngx_cidr_t *cidr, ngx_str_t *value, ngx_str_t *net)
1128{
1129    ngx_int_t                   rc;
1130    ngx_http_variable_value_t  *val, *old;
1131
1132    val = ngx_http_geo_value(cf, ctx, value);
1133
1134    if (val == NULL) {
1135        return NGX_CONF_ERROR;
1136    }
1137
1138    switch (cidr->family) {
1139
1140#if (NGX_HAVE_INET6)
1141    case AF_INET6:
1142        rc = ngx_radix128tree_insert(ctx->tree6, cidr->u.in6.addr.s6_addr,
1143                                     cidr->u.in6.mask.s6_addr,
1144                                     (uintptr_t) val);
1145
1146        if (rc == NGX_OK) {
1147            return NGX_CONF_OK;
1148        }
1149
1150        if (rc == NGX_ERROR) {
1151            return NGX_CONF_ERROR;
1152        }
1153
1154        /* rc == NGX_BUSY */
1155
1156        old = (ngx_http_variable_value_t *)
1157                   ngx_radix128tree_find(ctx->tree6,
1158                                         cidr->u.in6.addr.s6_addr);
1159
1160        ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
1161              "duplicate network \"%V\", value: \"%v\", old value: \"%v\"",
1162              net, val, old);
1163
1164        rc = ngx_radix128tree_delete(ctx->tree6,
1165                                     cidr->u.in6.addr.s6_addr,
1166                                     cidr->u.in6.mask.s6_addr);
1167
1168        if (rc == NGX_ERROR) {
1169            ngx_conf_log_error(NGX_LOG_EMERG, cf, 0, "invalid radix tree");
1170            return NGX_CONF_ERROR;
1171        }
1172
1173        rc = ngx_radix128tree_insert(ctx->tree6, cidr->u.in6.addr.s6_addr,
1174                                     cidr->u.in6.mask.s6_addr,
1175                                     (uintptr_t) val);
1176
1177        break;
1178#endif
1179
1180    default: /* AF_INET */
1181        rc = ngx_radix32tree_insert(ctx->tree, cidr->u.in.addr,
1182                                    cidr->u.in.mask, (uintptr_t) val);
1183
1184        if (rc == NGX_OK) {
1185            return NGX_CONF_OK;
1186        }
1187
1188        if (rc == NGX_ERROR) {
1189            return NGX_CONF_ERROR;
1190        }
1191
1192        /* rc == NGX_BUSY */
1193
1194        old = (ngx_http_variable_value_t *)
1195                   ngx_radix32tree_find(ctx->tree, cidr->u.in.addr);
1196
1197        ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
1198              "duplicate network \"%V\", value: \"%v\", old value: \"%v\"",
1199              net, val, old);
1200
1201        rc = ngx_radix32tree_delete(ctx->tree,
1202                                    cidr->u.in.addr, cidr->u.in.mask);
1203
1204        if (rc == NGX_ERROR) {
1205            ngx_conf_log_error(NGX_LOG_EMERG, cf, 0, "invalid radix tree");
1206            return NGX_CONF_ERROR;
1207        }
1208
1209        rc = ngx_radix32tree_insert(ctx->tree, cidr->u.in.addr,
1210                                    cidr->u.in.mask, (uintptr_t) val);
1211
1212        break;
1213    }
1214
1215    if (rc == NGX_OK) {
1216        return NGX_CONF_OK;
1217    }
1218
1219    return NGX_CONF_ERROR;
1220}
1221
1222
1223static ngx_http_variable_value_t *
1224ngx_http_geo_value(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
1225    ngx_str_t *value)
1226{
1227    uint32_t                             hash;
1228    ngx_http_variable_value_t           *val;
1229    ngx_http_geo_variable_value_node_t  *gvvn;
1230
1231    hash = ngx_crc32_long(value->data, value->len);
1232
1233    gvvn = (ngx_http_geo_variable_value_node_t *)
1234               ngx_str_rbtree_lookup(&ctx->rbtree, value, hash);
1235
1236    if (gvvn) {
1237        return gvvn->value;
1238    }
1239
1240    val = ngx_palloc(ctx->pool, sizeof(ngx_http_variable_value_t));
1241    if (val == NULL) {
1242        return NULL;
1243    }
1244
1245    val->len = value->len;
1246    val->data = ngx_pstrdup(ctx->pool, value);
1247    if (val->data == NULL) {
1248        return NULL;
1249    }
1250
1251    val->valid = 1;
1252    val->no_cacheable = 0;
1253    val->not_found = 0;
1254
1255    gvvn = ngx_palloc(ctx->temp_pool,
1256                      sizeof(ngx_http_geo_variable_value_node_t));
1257    if (gvvn == NULL) {
1258        return NULL;
1259    }
1260
1261    gvvn->sn.node.key = hash;
1262    gvvn->sn.str.len = val->len;
1263    gvvn->sn.str.data = val->data;
1264    gvvn->value = val;
1265    gvvn->offset = 0;
1266
1267    ngx_rbtree_insert(&ctx->rbtree, &gvvn->sn.node);
1268
1269    ctx->data_size += ngx_align(sizeof(ngx_http_variable_value_t) + value->len,
1270                                sizeof(void *));
1271
1272    return val;
1273}
1274
1275
1276static char *
1277ngx_http_geo_add_proxy(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
1278    ngx_cidr_t *cidr)
1279{
1280    ngx_cidr_t  *c;
1281
1282    if (ctx->proxies == NULL) {
1283        ctx->proxies = ngx_array_create(ctx->pool, 4, sizeof(ngx_cidr_t));
1284        if (ctx->proxies == NULL) {
1285            return NGX_CONF_ERROR;
1286        }
1287    }
1288
1289    c = ngx_array_push(ctx->proxies);
1290    if (c == NULL) {
1291        return NGX_CONF_ERROR;
1292    }
1293
1294    *c = *cidr;
1295
1296    return NGX_CONF_OK;
1297}
1298
1299
1300static ngx_int_t
1301ngx_http_geo_cidr_value(ngx_conf_t *cf, ngx_str_t *net, ngx_cidr_t *cidr)
1302{
1303    ngx_int_t  rc;
1304
1305    if (ngx_strcmp(net->data, "255.255.255.255") == 0) {
1306        cidr->family = AF_INET;
1307        cidr->u.in.addr = 0xffffffff;
1308        cidr->u.in.mask = 0xffffffff;
1309
1310        return NGX_OK;
1311    }
1312
1313    rc = ngx_ptocidr(net, cidr);
1314
1315    if (rc == NGX_ERROR) {
1316        ngx_conf_log_error(NGX_LOG_EMERG, cf, 0, "invalid network \"%V\"", net);
1317        return NGX_ERROR;
1318    }
1319
1320    if (rc == NGX_DONE) {
1321        ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
1322                           "low address bits of %V are meaningless", net);
1323    }
1324
1325    return NGX_OK;
1326}
1327
1328
1329static char *
1330ngx_http_geo_include(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
1331    ngx_str_t *name)
1332{
1333    char       *rv;
1334    ngx_str_t   file;
1335
1336    file.len = name->len + 4;
1337    file.data = ngx_pnalloc(ctx->temp_pool, name->len + 5);
1338    if (file.data == NULL) {
1339        return NGX_CONF_ERROR;
1340    }
1341
1342    ngx_sprintf(file.data, "%V.bin%Z", name);
1343
1344    if (ngx_conf_full_name(cf->cycle, &file, 1) != NGX_OK) {
1345        return NGX_CONF_ERROR;
1346    }
1347
1348    if (ctx->ranges) {
1349        ngx_log_debug1(NGX_LOG_DEBUG_CORE, cf->log, 0, "include %s", file.data);
1350
1351        switch (ngx_http_geo_include_binary_base(cf, ctx, &file)) {
1352        case NGX_OK:
1353            return NGX_CONF_OK;
1354        case NGX_ERROR:
1355            return NGX_CONF_ERROR;
1356        default:
1357            break;
1358        }
1359    }
1360
1361    file.len -= 4;
1362    file.data[file.len] = '\0';
1363
1364    ctx->include_name = file;
1365
1366    if (ctx->outside_entries) {
1367        ctx->allow_binary_include = 0;
1368    }
1369
1370    ngx_log_debug1(NGX_LOG_DEBUG_CORE, cf->log, 0, "include %s", file.data);
1371
1372    rv = ngx_conf_parse(cf, &file);
1373
1374    ctx->includes++;
1375    ctx->outside_entries = 0;
1376
1377    return rv;
1378}
1379
1380
1381static ngx_int_t
1382ngx_http_geo_include_binary_base(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx,
1383    ngx_str_t *name)
1384{
1385    u_char                     *base, ch;
1386    time_t                      mtime;
1387    size_t                      size, len;
1388    ssize_t                     n;
1389    uint32_t                    crc32;
1390    ngx_err_t                   err;
1391    ngx_int_t                   rc;
1392    ngx_uint_t                  i;
1393    ngx_file_t                  file;
1394    ngx_file_info_t             fi;
1395    ngx_http_geo_range_t       *range, **ranges;
1396    ngx_http_geo_header_t      *header;
1397    ngx_http_variable_value_t  *vv;
1398
1399    ngx_memzero(&file, sizeof(ngx_file_t));
1400    file.name = *name;
1401    file.log = cf->log;
1402
1403    file.fd = ngx_open_file(name->data, NGX_FILE_RDONLY, 0, 0);
1404    if (file.fd == NGX_INVALID_FILE) {
1405        err = ngx_errno;
1406        if (err != NGX_ENOENT) {
1407            ngx_conf_log_error(NGX_LOG_CRIT, cf, err,
1408                               ngx_open_file_n " \"%s\" failed", name->data);
1409        }
1410        return NGX_DECLINED;
1411    }
1412
1413    if (ctx->outside_entries) {
1414        ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
1415            "binary geo range base \"%s\" cannot be mixed with usual entries",
1416            name->data);
1417        rc = NGX_ERROR;
1418        goto done;
1419    }
1420
1421    if (ctx->binary_include) {
1422        ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
1423            "second binary geo range base \"%s\" cannot be mixed with \"%s\"",
1424            name->data, ctx->include_name.data);
1425        rc = NGX_ERROR;
1426        goto done;
1427    }
1428
1429    if (ngx_fd_info(file.fd, &fi) == NGX_FILE_ERROR) {
1430        ngx_conf_log_error(NGX_LOG_CRIT, cf, ngx_errno,
1431                           ngx_fd_info_n " \"%s\" failed", name->data);
1432        goto failed;
1433    }
1434
1435    size = (size_t) ngx_file_size(&fi);
1436    mtime = ngx_file_mtime(&fi);
1437
1438    ch = name->data[name->len - 4];
1439    name->data[name->len - 4] = '\0';
1440
1441    if (ngx_file_info(name->data, &fi) == NGX_FILE_ERROR) {
1442        ngx_conf_log_error(NGX_LOG_CRIT, cf, ngx_errno,
1443                           ngx_file_info_n " \"%s\" failed", name->data);
1444        goto failed;
1445    }
1446
1447    name->data[name->len - 4] = ch;
1448
1449    if (mtime < ngx_file_mtime(&fi)) {
1450        ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
1451                           "stale binary geo range base \"%s\"", name->data);
1452        goto failed;
1453    }
1454
1455    base = ngx_palloc(ctx->pool, size);
1456    if (base == NULL) {
1457        goto failed;
1458    }
1459
1460    n = ngx_read_file(&file, base, size, 0);
1461
1462    if (n == NGX_ERROR) {
1463        ngx_conf_log_error(NGX_LOG_CRIT, cf, ngx_errno,
1464                           ngx_read_file_n " \"%s\" failed", name->data);
1465        goto failed;
1466    }
1467
1468    if ((size_t) n != size) {
1469        ngx_conf_log_error(NGX_LOG_CRIT, cf, 0,
1470            ngx_read_file_n " \"%s\" returned only %z bytes instead of %z",
1471            name->data, n, size);
1472        goto failed;
1473    }
1474
1475    header = (ngx_http_geo_header_t *) base;
1476
1477    if (size < 16 || ngx_memcmp(&ngx_http_geo_header, header, 12) != 0) {
1478        ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
1479             "incompatible binary geo range base \"%s\"", name->data);
1480        goto failed;
1481    }
1482
1483    ngx_crc32_init(crc32);
1484
1485    vv = (ngx_http_variable_value_t *) (base + sizeof(ngx_http_geo_header_t));
1486
1487    while (vv->data) {
1488        len = ngx_align(sizeof(ngx_http_variable_value_t) + vv->len,
1489                        sizeof(void *));
1490        ngx_crc32_update(&crc32, (u_char *) vv, len);
1491        vv->data += (size_t) base;
1492        vv = (ngx_http_variable_value_t *) ((u_char *) vv + len);
1493    }
1494    ngx_crc32_update(&crc32, (u_char *) vv, sizeof(ngx_http_variable_value_t));
1495    vv++;
1496
1497    ranges = (ngx_http_geo_range_t **) vv;
1498
1499    for (i = 0; i < 0x10000; i++) {
1500        ngx_crc32_update(&crc32, (u_char *) &ranges[i], sizeof(void *));
1501        if (ranges[i]) {
1502            ranges[i] = (ngx_http_geo_range_t *)
1503                            ((u_char *) ranges[i] + (size_t) base);
1504        }
1505    }
1506
1507    range = (ngx_http_geo_range_t *) &ranges[0x10000];
1508
1509    while ((u_char *) range < base + size) {
1510        while (range->value) {
1511            ngx_crc32_update(&crc32, (u_char *) range,
1512                             sizeof(ngx_http_geo_range_t));
1513            range->value = (ngx_http_variable_value_t *)
1514                               ((u_char *) range->value + (size_t) base);
1515            range++;
1516        }
1517        ngx_crc32_update(&crc32, (u_char *) range, sizeof(void *));
1518        range = (ngx_http_geo_range_t *) ((u_char *) range + sizeof(void *));
1519    }
1520
1521    ngx_crc32_final(crc32);
1522
1523    if (crc32 != header->crc32) {
1524        ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
1525                  "CRC32 mismatch in binary geo range base \"%s\"", name->data);
1526        goto failed;
1527    }
1528
1529    ngx_conf_log_error(NGX_LOG_NOTICE, cf, 0,
1530                       "using binary geo range base \"%s\"", name->data);
1531
1532    ctx->include_name = *name;
1533    ctx->binary_include = 1;
1534    ctx->high.low = ranges;
1535    rc = NGX_OK;
1536
1537    goto done;
1538
1539failed:
1540
1541    rc = NGX_DECLINED;
1542
1543done:
1544
1545    if (ngx_close_file(file.fd) == NGX_FILE_ERROR) {
1546        ngx_log_error(NGX_LOG_ALERT, cf->log, ngx_errno,
1547                      ngx_close_file_n " \"%s\" failed", name->data);
1548    }
1549
1550    return rc;
1551}
1552
1553
1554static void
1555ngx_http_geo_create_binary_base(ngx_http_geo_conf_ctx_t *ctx)
1556{
1557    u_char                              *p;
1558    uint32_t                             hash;
1559    ngx_str_t                            s;
1560    ngx_uint_t                           i;
1561    ngx_file_mapping_t                   fm;
1562    ngx_http_geo_range_t                *r, *range, **ranges;
1563    ngx_http_geo_header_t               *header;
1564    ngx_http_geo_variable_value_node_t  *gvvn;
1565
1566    fm.name = ngx_pnalloc(ctx->temp_pool, ctx->include_name.len + 5);
1567    if (fm.name == NULL) {
1568        return;
1569    }
1570
1571    ngx_sprintf(fm.name, "%V.bin%Z", &ctx->include_name);
1572
1573    fm.size = ctx->data_size;
1574    fm.log = ctx->pool->log;
1575
1576    ngx_log_error(NGX_LOG_NOTICE, fm.log, 0,
1577                  "creating binary geo range base \"%s\"", fm.name);
1578
1579    if (ngx_create_file_mapping(&fm) != NGX_OK) {
1580        return;
1581    }
1582
1583    p = ngx_cpymem(fm.addr, &ngx_http_geo_header,
1584                   sizeof(ngx_http_geo_header_t));
1585
1586    p = ngx_http_geo_copy_values(fm.addr, p, ctx->rbtree.root,
1587                                 ctx->rbtree.sentinel);
1588
1589    p += sizeof(ngx_http_variable_value_t);
1590
1591    ranges = (ngx_http_geo_range_t **) p;
1592
1593    p += 0x10000 * sizeof(ngx_http_geo_range_t *);
1594
1595    for (i = 0; i < 0x10000; i++) {
1596        r = ctx->high.low[i];
1597        if (r == NULL) {
1598            continue;
1599        }
1600
1601        range = (ngx_http_geo_range_t *) p;
1602        ranges[i] = (ngx_http_geo_range_t *) (p - (u_char *) fm.addr);
1603
1604        do {
1605            s.len = r->value->len;
1606            s.data = r->value->data;
1607            hash = ngx_crc32_long(s.data, s.len);
1608            gvvn = (ngx_http_geo_variable_value_node_t *)
1609                        ngx_str_rbtree_lookup(&ctx->rbtree, &s, hash);
1610
1611            range->value = (ngx_http_variable_value_t *) gvvn->offset;
1612            range->start = r->start;
1613            range->end = r->end;
1614            range++;
1615
1616        } while ((++r)->value);
1617
1618        range->value = NULL;
1619
1620        p = (u_char *) range + sizeof(void *);
1621    }
1622
1623    header = fm.addr;
1624    header->crc32 = ngx_crc32_long((u_char *) fm.addr
1625                                       + sizeof(ngx_http_geo_header_t),
1626                                   fm.size - sizeof(ngx_http_geo_header_t));
1627
1628    ngx_close_file_mapping(&fm);
1629}
1630
1631
1632static u_char *
1633ngx_http_geo_copy_values(u_char *base, u_char *p, ngx_rbtree_node_t *node,
1634    ngx_rbtree_node_t *sentinel)
1635{
1636    ngx_http_variable_value_t           *vv;
1637    ngx_http_geo_variable_value_node_t  *gvvn;
1638
1639    if (node == sentinel) {
1640        return p;
1641    }
1642
1643    gvvn = (ngx_http_geo_variable_value_node_t *) node;
1644    gvvn->offset = p - base;
1645
1646    vv = (ngx_http_variable_value_t *) p;
1647    *vv = *gvvn->value;
1648    p += sizeof(ngx_http_variable_value_t);
1649    vv->data = (u_char *) (p - base);
1650
1651    p = ngx_cpymem(p, gvvn->sn.str.data, gvvn->sn.str.len);
1652
1653    p = ngx_align_ptr(p, sizeof(void *));
1654
1655    p = ngx_http_geo_copy_values(base, p, node->left, sentinel);
1656
1657    return ngx_http_geo_copy_values(base, p, node->right, sentinel);
1658}
1659