Mercurial > hg > nginx-quic
view src/core/ngx_radix_tree.c @ 6673:e4c1f5b32868
Event pipe: do not set file's thread_handler if not needed.
This fixes a problem with aio threads and sendfile with aio_write switched
off, as observed with range requests after fc72784b1f52 (1.9.13). Potential
problems with sendfile in threads were previously described in 9fd738b85fad,
and this seems to be one of them.
The problem occurred as file's thread_handler was set to NULL by event pipe
code after a sendfile thread task was scheduled. As a result, no sendfile
completion code was executed, and the same buffer was additionally sent
using non-threaded sendfile. Fix is to avoid modifying file's thread_handler
if aio_write is switched off.
Note that with "aio_write on" it is still possible that sendfile will use
thread_handler as set by event pipe. This is believed to be safe though,
as handlers used are compatible.
author | Maxim Dounin <mdounin@mdounin.ru> |
---|---|
date | Thu, 01 Sep 2016 20:05:23 +0300 |
parents | 3be3de31d7dd |
children |
line wrap: on
line source
/* * Copyright (C) Igor Sysoev * Copyright (C) Nginx, Inc. */ #include <ngx_config.h> #include <ngx_core.h> static ngx_radix_node_t *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_node_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; } #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) { ngx_radix_node_t *p; if (tree->free) { p = 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 = (ngx_radix_node_t *) tree->start; tree->start += sizeof(ngx_radix_node_t); tree->size -= sizeof(ngx_radix_node_t); return p; }