Mercurial > hg > nginx
view src/core/ngx_radix_tree.c @ 4576:876e6b0814a5
Fixed signed integer overflows in timer code (ticket #145).
Integer overflow is undefined behaviour in C and this indeed caused
problems on Solaris/SPARC (at least in some cases). Fix is to
subtract unsigned integers instead, and then cast result to a signed
one, which is implementation-defined behaviour and used to work.
Strictly speaking, we should compare (unsigned) result with the maximum
value of the corresponding signed integer type instead, this will be
defined behaviour. This will require much more changes though, and
considered to be overkill for now.
author | Maxim Dounin <mdounin@mdounin.ru> |
---|---|
date | Fri, 06 Apr 2012 23:46:09 +0000 |
parents | d620f497c50f |
children | efa334556803 |
line wrap: on
line source
/* * Copyright (C) Igor Sysoev * Copyright (C) Nginx, Inc. */ #include <ngx_config.h> #include <ngx_core.h> static void *ngx_radix_alloc(ngx_radix_tree_t *tree); ngx_radix_tree_t * ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate) { uint32_t key, mask, inc; ngx_radix_tree_t *tree; tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)); if (tree == NULL) { return NULL; } tree->pool = pool; tree->free = NULL; tree->start = NULL; tree->size = 0; tree->root = ngx_radix_alloc(tree); if (tree->root == NULL) { return NULL; } tree->root->right = NULL; tree->root->left = NULL; tree->root->parent = NULL; tree->root->value = NGX_RADIX_NO_VALUE; if (preallocate == 0) { return tree; } /* * Preallocation of first nodes : 0, 1, 00, 01, 10, 11, 000, 001, etc. * increases TLB hits even if for first lookup iterations. * On 32-bit platforms the 7 preallocated bits takes continuous 4K, * 8 - 8K, 9 - 16K, etc. On 64-bit platforms the 6 preallocated bits * takes continuous 4K, 7 - 8K, 8 - 16K, etc. There is no sense to * to preallocate more than one page, because further preallocation * distributes the only bit per page. Instead, a random insertion * may distribute several bits per page. * * Thus, by default we preallocate maximum * 6 bits on amd64 (64-bit platform and 4K pages) * 7 bits on i386 (32-bit platform and 4K pages) * 7 bits on sparc64 in 64-bit mode (8K pages) * 8 bits on sparc64 in 32-bit mode (8K pages) */ if (preallocate == -1) { switch (ngx_pagesize / sizeof(ngx_radix_tree_t)) { /* amd64 */ case 128: preallocate = 6; break; /* i386, sparc64 */ case 256: preallocate = 7; break; /* sparc64 in 32-bit mode */ default: preallocate = 8; } } mask = 0; inc = 0x80000000; while (preallocate--) { key = 0; mask >>= 1; mask |= 0x80000000; do { if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE) != NGX_OK) { return NULL; } key += inc; } while (key); inc >>= 1; } return tree; } ngx_int_t ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask, uintptr_t value) { uint32_t bit; ngx_radix_node_t *node, *next; bit = 0x80000000; node = tree->root; next = tree->root; while (bit & mask) { if (key & bit) { next = node->right; } else { next = node->left; } if (next == NULL) { break; } bit >>= 1; node = next; } if (next) { if (node->value != NGX_RADIX_NO_VALUE) { return NGX_BUSY; } node->value = value; return NGX_OK; } while (bit & mask) { 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 & bit) { node->right = next; } else { node->left = next; } bit >>= 1; node = next; } node->value = value; return NGX_OK; } ngx_int_t ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask) { uint32_t bit; ngx_radix_node_t *node; bit = 0x80000000; node = tree->root; while (node && (bit & mask)) { if (key & bit) { node = node->right; } else { node = node->left; } bit >>= 1; } 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_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key) { uint32_t bit; uintptr_t value; ngx_radix_node_t *node; bit = 0x80000000; value = NGX_RADIX_NO_VALUE; node = tree->root; while (node) { if (node->value != NGX_RADIX_NO_VALUE) { value = node->value; } if (key & bit) { node = node->right; } else { node = node->left; } bit >>= 1; } return value; } static void * ngx_radix_alloc(ngx_radix_tree_t *tree) { char *p; if (tree->free) { p = (char *) tree->free; tree->free = tree->free->right; return p; } if (tree->size < sizeof(ngx_radix_node_t)) { tree->start = ngx_pmemalign(tree->pool, ngx_pagesize, ngx_pagesize); if (tree->start == NULL) { return NULL; } tree->size = ngx_pagesize; } p = tree->start; tree->start += sizeof(ngx_radix_node_t); tree->size -= sizeof(ngx_radix_node_t); return p; }