# HG changeset patch # User Maxim Dounin # Date 1360585903 0 # Node ID 2f0862333985068745ccf4c0652643f9cc2dc80c # Parent 852f40088278651d4d04d1d007eacf627aef0ea9 Merge of r4993, r4994, r4997, r5000: geo ipv6 support. *) Geo: IPv6 support. The "ranges" mode is still limited to IPv4 only. *) Geo: properly initialize ngx_cidr_t when dealing with "default". *) Geo: made "default" affect both IPv4 and IPv6 when using prefixes. Previously, "default" was equivalent to specifying 0.0.0.0/0, now it's equivalent to specifying both 0.0.0.0/0 and ::/0 (if support for IPv6 is enabled) with the same value. *) Geo: improved code readability. diff --git a/src/core/ngx_radix_tree.c b/src/core/ngx_radix_tree.c --- a/src/core/ngx_radix_tree.c +++ b/src/core/ngx_radix_tree.c @@ -263,6 +263,203 @@ ngx_radix32tree_find(ngx_radix_tree_t *t } +#if (NGX_HAVE_INET6) + +ngx_int_t +ngx_radix128tree_insert(ngx_radix_tree_t *tree, u_char *key, u_char *mask, + uintptr_t value) +{ + u_char bit; + ngx_uint_t i; + ngx_radix_node_t *node, *next; + + i = 0; + bit = 0x80; + + node = tree->root; + next = tree->root; + + while (bit & mask[i]) { + if (key[i] & bit) { + next = node->right; + + } else { + next = node->left; + } + + if (next == NULL) { + break; + } + + bit >>= 1; + node = next; + + if (bit == 0) { + if (++i == 16) { + break; + } + + bit = 0x80; + } + } + + if (next) { + if (node->value != NGX_RADIX_NO_VALUE) { + return NGX_BUSY; + } + + node->value = value; + return NGX_OK; + } + + while (bit & mask[i]) { + next = ngx_radix_alloc(tree); + if (next == NULL) { + return NGX_ERROR; + } + + next->right = NULL; + next->left = NULL; + next->parent = node; + next->value = NGX_RADIX_NO_VALUE; + + if (key[i] & bit) { + node->right = next; + + } else { + node->left = next; + } + + bit >>= 1; + node = next; + + if (bit == 0) { + if (++i == 16) { + break; + } + + bit = 0x80; + } + } + + node->value = value; + + return NGX_OK; +} + + +ngx_int_t +ngx_radix128tree_delete(ngx_radix_tree_t *tree, u_char *key, u_char *mask) +{ + u_char bit; + ngx_uint_t i; + ngx_radix_node_t *node; + + i = 0; + bit = 0x80; + node = tree->root; + + while (node && (bit & mask[i])) { + if (key[i] & bit) { + node = node->right; + + } else { + node = node->left; + } + + bit >>= 1; + + if (bit == 0) { + if (++i == 16) { + break; + } + + bit = 0x80; + } + } + + if (node == NULL) { + return NGX_ERROR; + } + + if (node->right || node->left) { + if (node->value != NGX_RADIX_NO_VALUE) { + node->value = NGX_RADIX_NO_VALUE; + return NGX_OK; + } + + return NGX_ERROR; + } + + for ( ;; ) { + if (node->parent->right == node) { + node->parent->right = NULL; + + } else { + node->parent->left = NULL; + } + + node->right = tree->free; + tree->free = node; + + node = node->parent; + + if (node->right || node->left) { + break; + } + + if (node->value != NGX_RADIX_NO_VALUE) { + break; + } + + if (node->parent == NULL) { + break; + } + } + + return NGX_OK; +} + + +uintptr_t +ngx_radix128tree_find(ngx_radix_tree_t *tree, u_char *key) +{ + u_char bit; + uintptr_t value; + ngx_uint_t i; + ngx_radix_node_t *node; + + i = 0; + bit = 0x80; + value = NGX_RADIX_NO_VALUE; + node = tree->root; + + while (node) { + if (node->value != NGX_RADIX_NO_VALUE) { + value = node->value; + } + + if (key[i] & bit) { + node = node->right; + + } else { + node = node->left; + } + + bit >>= 1; + + if (bit == 0) { + i++; + bit = 0x80; + } + } + + return value; +} + +#endif + + static ngx_radix_node_t * ngx_radix_alloc(ngx_radix_tree_t *tree) { diff --git a/src/core/ngx_radix_tree.h b/src/core/ngx_radix_tree.h --- a/src/core/ngx_radix_tree.h +++ b/src/core/ngx_radix_tree.h @@ -36,11 +36,20 @@ typedef struct { ngx_radix_tree_t *ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate); + ngx_int_t ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask, uintptr_t value); ngx_int_t ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask); uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key); +#if (NGX_HAVE_INET6) +ngx_int_t ngx_radix128tree_insert(ngx_radix_tree_t *tree, + u_char *key, u_char *mask, uintptr_t value); +ngx_int_t ngx_radix128tree_delete(ngx_radix_tree_t *tree, + u_char *key, u_char *mask); +uintptr_t ngx_radix128tree_find(ngx_radix_tree_t *tree, u_char *key); +#endif + #endif /* _NGX_RADIX_TREE_H_INCLUDED_ */ diff --git a/src/http/modules/ngx_http_geo_module.c b/src/http/modules/ngx_http_geo_module.c --- a/src/http/modules/ngx_http_geo_module.c +++ b/src/http/modules/ngx_http_geo_module.c @@ -18,6 +18,14 @@ typedef struct { typedef struct { + ngx_radix_tree_t *tree; +#if (NGX_HAVE_INET6) + ngx_radix_tree_t *tree6; +#endif +} ngx_http_geo_trees_t; + + +typedef struct { ngx_http_geo_range_t **low; ngx_http_variable_value_t *default_value; } ngx_http_geo_high_ranges_t; @@ -35,6 +43,9 @@ typedef struct { ngx_str_t *net; ngx_http_geo_high_ranges_t high; ngx_radix_tree_t *tree; +#if (NGX_HAVE_INET6) + ngx_radix_tree_t *tree6; +#endif ngx_rbtree_t rbtree; ngx_rbtree_node_t sentinel; ngx_array_t *proxies; @@ -57,7 +68,7 @@ typedef struct { typedef struct { union { - ngx_radix_tree_t *tree; + ngx_http_geo_trees_t trees; ngx_http_geo_high_ranges_t high; } u; @@ -68,8 +79,8 @@ typedef struct { } ngx_http_geo_ctx_t; -static in_addr_t ngx_http_geo_addr(ngx_http_request_t *r, - ngx_http_geo_ctx_t *ctx); +static ngx_int_t ngx_http_geo_addr(ngx_http_request_t *r, + ngx_http_geo_ctx_t *ctx, ngx_addr_t *addr); static ngx_int_t ngx_http_geo_real_addr(ngx_http_request_t *r, ngx_http_geo_ctx_t *ctx, ngx_addr_t *addr); static char *ngx_http_geo_block(ngx_conf_t *cf, ngx_command_t *cmd, void *conf); @@ -82,6 +93,8 @@ static ngx_uint_t ngx_http_geo_delete_ra ngx_http_geo_conf_ctx_t *ctx, in_addr_t start, in_addr_t end); static char *ngx_http_geo_cidr(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx, ngx_str_t *value); +static char *ngx_http_geo_cidr_add(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx, + ngx_cidr_t *cidr, ngx_str_t *value, ngx_str_t *net); static ngx_http_variable_value_t *ngx_http_geo_value(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx, ngx_str_t *value); static char *ngx_http_geo_add_proxy(ngx_conf_t *cf, @@ -155,7 +168,7 @@ static ngx_http_geo_header_t ngx_http_g }; -/* AF_INET only */ +/* geo range is AF_INET only */ static ngx_int_t ngx_http_geo_cidr_variable(ngx_http_request_t *r, ngx_http_variable_value_t *v, @@ -163,10 +176,56 @@ ngx_http_geo_cidr_variable(ngx_http_requ { ngx_http_geo_ctx_t *ctx = (ngx_http_geo_ctx_t *) data; + in_addr_t inaddr; + ngx_addr_t addr; + struct sockaddr_in *sin; ngx_http_variable_value_t *vv; +#if (NGX_HAVE_INET6) + u_char *p; + struct in6_addr *inaddr6; +#endif + + if (ngx_http_geo_addr(r, ctx, &addr) != NGX_OK) { + vv = (ngx_http_variable_value_t *) + ngx_radix32tree_find(ctx->u.trees.tree, INADDR_NONE); + goto done; + } + + switch (addr.sockaddr->sa_family) { + +#if (NGX_HAVE_INET6) + case AF_INET6: + inaddr6 = &((struct sockaddr_in6 *) addr.sockaddr)->sin6_addr; + p = inaddr6->s6_addr; - vv = (ngx_http_variable_value_t *) - ngx_radix32tree_find(ctx->u.tree, ngx_http_geo_addr(r, ctx)); + if (IN6_IS_ADDR_V4MAPPED(inaddr6)) { + inaddr = p[12] << 24; + inaddr += p[13] << 16; + inaddr += p[14] << 8; + inaddr += p[15]; + + vv = (ngx_http_variable_value_t *) + ngx_radix32tree_find(ctx->u.trees.tree, inaddr); + + } else { + vv = (ngx_http_variable_value_t *) + ngx_radix128tree_find(ctx->u.trees.tree6, p); + } + + break; +#endif + + default: /* AF_INET */ + sin = (struct sockaddr_in *) addr.sockaddr; + inaddr = ntohl(sin->sin_addr.s_addr); + + vv = (ngx_http_variable_value_t *) + ngx_radix32tree_find(ctx->u.trees.tree, inaddr); + + break; + } + +done: *v = *vv; @@ -183,19 +242,56 @@ ngx_http_geo_range_variable(ngx_http_req { ngx_http_geo_ctx_t *ctx = (ngx_http_geo_ctx_t *) data; - in_addr_t addr; + in_addr_t inaddr; + ngx_addr_t addr; ngx_uint_t n; + struct sockaddr_in *sin; ngx_http_geo_range_t *range; +#if (NGX_HAVE_INET6) + u_char *p; + struct in6_addr *inaddr6; +#endif *v = *ctx->u.high.default_value; + if (ngx_http_geo_addr(r, ctx, &addr) == NGX_OK) { + + switch (addr.sockaddr->sa_family) { + +#if (NGX_HAVE_INET6) + case AF_INET6: + inaddr6 = &((struct sockaddr_in6 *) addr.sockaddr)->sin6_addr; + + if (IN6_IS_ADDR_V4MAPPED(inaddr6)) { + p = inaddr6->s6_addr; + + inaddr = p[12] << 24; + inaddr += p[13] << 16; + inaddr += p[14] << 8; + inaddr += p[15]; + + } else { + inaddr = INADDR_NONE; + } + + break; +#endif + + default: /* AF_INET */ + sin = (struct sockaddr_in *) addr.sockaddr; + inaddr = ntohl(sin->sin_addr.s_addr); + break; + } + + } else { + inaddr = INADDR_NONE; + } + if (ctx->u.high.low) { - addr = ngx_http_geo_addr(r, ctx); - - range = ctx->u.high.low[addr >> 16]; + range = ctx->u.high.low[inaddr >> 16]; if (range) { - n = addr & 0xffff; + n = inaddr & 0xffff; do { if (n >= (ngx_uint_t) range->start && n <= (ngx_uint_t) range->end) @@ -214,54 +310,25 @@ ngx_http_geo_range_variable(ngx_http_req } -static in_addr_t -ngx_http_geo_addr(ngx_http_request_t *r, ngx_http_geo_ctx_t *ctx) +static ngx_int_t +ngx_http_geo_addr(ngx_http_request_t *r, ngx_http_geo_ctx_t *ctx, + ngx_addr_t *addr) { - ngx_addr_t addr; - ngx_table_elt_t *xfwd; - struct sockaddr_in *sin; + ngx_table_elt_t *xfwd; - if (ngx_http_geo_real_addr(r, ctx, &addr) != NGX_OK) { - return INADDR_NONE; + if (ngx_http_geo_real_addr(r, ctx, addr) != NGX_OK) { + return NGX_ERROR; } xfwd = r->headers_in.x_forwarded_for; if (xfwd != NULL && ctx->proxies != NULL) { - (void) ngx_http_get_forwarded_addr(r, &addr, xfwd->value.data, + (void) ngx_http_get_forwarded_addr(r, addr, xfwd->value.data, xfwd->value.len, ctx->proxies, ctx->proxy_recursive); } -#if (NGX_HAVE_INET6) - - if (addr.sockaddr->sa_family == AF_INET6) { - u_char *p; - in_addr_t inaddr; - struct in6_addr *inaddr6; - - inaddr6 = &((struct sockaddr_in6 *) addr.sockaddr)->sin6_addr; - - if (IN6_IS_ADDR_V4MAPPED(inaddr6)) { - p = inaddr6->s6_addr; - - inaddr = p[12] << 24; - inaddr += p[13] << 16; - inaddr += p[14] << 8; - inaddr += p[15]; - - return inaddr; - } - } - -#endif - - if (addr.sockaddr->sa_family != AF_INET) { - return INADDR_NONE; - } - - sin = (struct sockaddr_in *) addr.sockaddr; - return ntohl(sin->sin_addr.s_addr); + return NGX_OK; } @@ -315,6 +382,9 @@ ngx_http_geo_block(ngx_conf_t *cf, ngx_c ngx_http_variable_t *var; ngx_http_geo_ctx_t *geo; ngx_http_geo_conf_ctx_t ctx; +#if (NGX_HAVE_INET6) + static struct in6_addr zero; +#endif value = cf->args->elts; @@ -445,7 +515,18 @@ ngx_http_geo_block(ngx_conf_t *cf, ngx_c } } - geo->u.tree = ctx.tree; + geo->u.trees.tree = ctx.tree; + +#if (NGX_HAVE_INET6) + if (ctx.tree6 == NULL) { + ctx.tree6 = ngx_radix_tree_create(cf->pool, -1); + if (ctx.tree6 == NULL) { + return NGX_CONF_ERROR; + } + } + + geo->u.trees.tree6 = ctx.tree6; +#endif var->get_handler = ngx_http_geo_cidr_variable; var->data = (uintptr_t) geo; @@ -461,6 +542,15 @@ ngx_http_geo_block(ngx_conf_t *cf, ngx_c } /* NGX_BUSY is okay (default was set explicitly) */ + +#if (NGX_HAVE_INET6) + if (ngx_radix128tree_insert(ctx.tree6, zero.s6_addr, zero.s6_addr, + (uintptr_t) &ngx_http_variable_null_value) + == NGX_ERROR) + { + return NGX_CONF_ERROR; + } +#endif } return rv; @@ -483,7 +573,12 @@ ngx_http_geo(ngx_conf_t *cf, ngx_command if (ngx_strcmp(value[0].data, "ranges") == 0) { - if (ctx->tree) { + if (ctx->tree +#if (NGX_HAVE_INET6) + || ctx->tree6 +#endif + ) + { ngx_conf_log_error(NGX_LOG_EMERG, cf, 0, "the \"ranges\" directive must be " "the first directive inside \"geo\" block"); @@ -921,11 +1016,10 @@ static char * ngx_http_geo_cidr(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx, ngx_str_t *value) { - ngx_int_t rc, del; - ngx_str_t *net; - ngx_uint_t i; - ngx_cidr_t cidr; - ngx_http_variable_value_t *val, *old; + char *rv; + ngx_int_t rc, del; + ngx_str_t *net; + ngx_cidr_t cidr; if (ctx->tree == NULL) { ctx->tree = ngx_radix_tree_create(ctx->pool, -1); @@ -934,57 +1028,108 @@ ngx_http_geo_cidr(ngx_conf_t *cf, ngx_ht } } +#if (NGX_HAVE_INET6) + if (ctx->tree6 == NULL) { + ctx->tree6 = ngx_radix_tree_create(ctx->pool, -1); + if (ctx->tree6 == NULL) { + return NGX_CONF_ERROR; + } + } +#endif + if (ngx_strcmp(value[0].data, "default") == 0) { - /* cidr.family = AF_INET; */ + cidr.family = AF_INET; cidr.u.in.addr = 0; cidr.u.in.mask = 0; - net = &value[0]; - } else { - if (ngx_strcmp(value[0].data, "delete") == 0) { - net = &value[1]; - del = 1; + rv = ngx_http_geo_cidr_add(cf, ctx, &cidr, &value[1], &value[0]); - } else { - net = &value[0]; - del = 0; - } - - if (ngx_http_geo_cidr_value(cf, net, &cidr) != NGX_OK) { - return NGX_CONF_ERROR; + if (rv != NGX_CONF_OK) { + return rv; } - if (cidr.family != AF_INET) { - ngx_conf_log_error(NGX_LOG_EMERG, cf, 0, - "\"geo\" supports IPv4 only"); - return NGX_CONF_ERROR; +#if (NGX_HAVE_INET6) + cidr.family = AF_INET6; + ngx_memzero(&cidr.u.in6, sizeof(ngx_in6_cidr_t)); + + rv = ngx_http_geo_cidr_add(cf, ctx, &cidr, &value[1], &value[0]); + + if (rv != NGX_CONF_OK) { + return rv; } +#endif + return NGX_CONF_OK; + } + + if (ngx_strcmp(value[0].data, "delete") == 0) { + net = &value[1]; + del = 1; + + } else { + net = &value[0]; + del = 0; + } + + if (ngx_http_geo_cidr_value(cf, net, &cidr) != NGX_OK) { + return NGX_CONF_ERROR; + } + + if (cidr.family == AF_INET) { cidr.u.in.addr = ntohl(cidr.u.in.addr); cidr.u.in.mask = ntohl(cidr.u.in.mask); - - if (del) { - if (ngx_radix32tree_delete(ctx->tree, cidr.u.in.addr, - cidr.u.in.mask) - != NGX_OK) - { - ngx_conf_log_error(NGX_LOG_WARN, cf, 0, - "no network \"%V\" to delete", net); - } - - return NGX_CONF_OK; - } } - val = ngx_http_geo_value(cf, ctx, &value[1]); + if (del) { + switch (cidr.family) { + +#if (NGX_HAVE_INET6) + case AF_INET6: + rc = ngx_radix128tree_delete(ctx->tree6, + cidr.u.in6.addr.s6_addr, + cidr.u.in6.mask.s6_addr); + break; +#endif + + default: /* AF_INET */ + rc = ngx_radix32tree_delete(ctx->tree, cidr.u.in.addr, + cidr.u.in.mask); + break; + } + + if (rc != NGX_OK) { + ngx_conf_log_error(NGX_LOG_WARN, cf, 0, + "no network \"%V\" to delete", net); + } + + return NGX_CONF_OK; + } + + return ngx_http_geo_cidr_add(cf, ctx, &cidr, &value[1], net); +} + + +static char * +ngx_http_geo_cidr_add(ngx_conf_t *cf, ngx_http_geo_conf_ctx_t *ctx, + ngx_cidr_t *cidr, ngx_str_t *value, ngx_str_t *net) +{ + ngx_int_t rc; + ngx_http_variable_value_t *val, *old; + + val = ngx_http_geo_value(cf, ctx, value); if (val == NULL) { return NGX_CONF_ERROR; } - for (i = 2; i; i--) { - rc = ngx_radix32tree_insert(ctx->tree, cidr.u.in.addr, cidr.u.in.mask, - (uintptr_t) val); + switch (cidr->family) { + +#if (NGX_HAVE_INET6) + case AF_INET6: + rc = ngx_radix128tree_insert(ctx->tree6, cidr->u.in6.addr.s6_addr, + cidr->u.in6.mask.s6_addr, + (uintptr_t) val); + if (rc == NGX_OK) { return NGX_CONF_OK; } @@ -996,18 +1141,66 @@ ngx_http_geo_cidr(ngx_conf_t *cf, ngx_ht /* rc == NGX_BUSY */ old = (ngx_http_variable_value_t *) - ngx_radix32tree_find(ctx->tree, cidr.u.in.addr); + ngx_radix128tree_find(ctx->tree6, + cidr->u.in6.addr.s6_addr); ngx_conf_log_error(NGX_LOG_WARN, cf, 0, - "duplicate network \"%V\", value: \"%v\", old value: \"%v\"", - net, val, old); + "duplicate network \"%V\", value: \"%v\", old value: \"%v\"", + net, val, old); - rc = ngx_radix32tree_delete(ctx->tree, cidr.u.in.addr, cidr.u.in.mask); + rc = ngx_radix128tree_delete(ctx->tree6, + cidr->u.in6.addr.s6_addr, + cidr->u.in6.mask.s6_addr); if (rc == NGX_ERROR) { ngx_conf_log_error(NGX_LOG_EMERG, cf, 0, "invalid radix tree"); return NGX_CONF_ERROR; } + + rc = ngx_radix128tree_insert(ctx->tree6, cidr->u.in6.addr.s6_addr, + cidr->u.in6.mask.s6_addr, + (uintptr_t) val); + + break; +#endif + + default: /* AF_INET */ + rc = ngx_radix32tree_insert(ctx->tree, cidr->u.in.addr, + cidr->u.in.mask, (uintptr_t) val); + + if (rc == NGX_OK) { + return NGX_CONF_OK; + } + + if (rc == NGX_ERROR) { + return NGX_CONF_ERROR; + } + + /* rc == NGX_BUSY */ + + old = (ngx_http_variable_value_t *) + ngx_radix32tree_find(ctx->tree, cidr->u.in.addr); + + ngx_conf_log_error(NGX_LOG_WARN, cf, 0, + "duplicate network \"%V\", value: \"%v\", old value: \"%v\"", + net, val, old); + + rc = ngx_radix32tree_delete(ctx->tree, + cidr->u.in.addr, cidr->u.in.mask); + + if (rc == NGX_ERROR) { + ngx_conf_log_error(NGX_LOG_EMERG, cf, 0, "invalid radix tree"); + return NGX_CONF_ERROR; + } + + rc = ngx_radix32tree_insert(ctx->tree, cidr->u.in.addr, + cidr->u.in.mask, (uintptr_t) val); + + break; + } + + if (rc == NGX_OK) { + return NGX_CONF_OK; } return NGX_CONF_ERROR;