Mercurial > hg > nginx-vendor-0-8

comparison src/core/ngx_hash.c @ 142:84910468f6de NGINX_0_3_18

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
nginx 0.3.18 *) Feature: the "server_names" directive supports the ".domain.tld" names. *) Feature: the "server_names" directive uses the hash for the "*.domain.tld" names and more effective hash for usual names. *) Change: the "server_names_hash_max_size" and "server_names_hash_bucket_size" directives. *) Change: the "server_names_hash" and "server_names_hash_threshold" directives were canceled. *) Feature: the "valid_referers" directive uses the hash site names. *) Change: now the "valid_referers" directive checks the site names only without the URI part. *) Bugfix: some ".domain.tld" names incorrectly processed by the ngx_http_map_module. *) Bugfix: segmentation fault was occurred if configuration file did not exist; bug appeared in 0.3.12. *) Bugfix: on 64-bit platforms segmentation fault may occurred on start; bug appeared in 0.3.16.
author Igor Sysoev <http://sysoev.ru>
date Mon, 26 Dec 2005 00:00:00 +0300
parents 55a211e5eeb7
children e1c6ac408b68
comparison
equal deleted inserted replaced
141:249e67502bf3 142:84910468f6de
156 hinit->name, hinit->name, hinit->bucket_size); 156 hinit->name, hinit->name, hinit->bucket_size);
157 return NGX_ERROR; 157 return NGX_ERROR;
158 } 158 }
159 } 159 }
160 160
161 test = ngx_alloc(hinit->max_size * sizeof(ngx_uint_t), hinit->pool->log); 161 test = ngx_alloc(hinit->max_size * sizeof(size_t), hinit->pool->log);
162 if (test == NULL) { 162 if (test == NULL) {
163 return NGX_ERROR; 163 return NGX_ERROR;
164 } 164 }
165 165
166 start = nelts / (ngx_cacheline_size / (2 * sizeof(void *)) - 1); 166 start = nelts / (ngx_cacheline_size / (2 * sizeof(void *)) - 1);
168 168
169 bucket_size = hinit->bucket_size - sizeof(void *); 169 bucket_size = hinit->bucket_size - sizeof(void *);
170 170
171 for (size = start; size < hinit->max_size; size++) { 171 for (size = start; size < hinit->max_size; size++) {
172 172
173 ngx_memzero(test, size * sizeof(ngx_uint_t)); 173 ngx_memzero(test, size * sizeof(size_t));
174 174
175 for (n = 0; n < nelts; n++) { 175 for (n = 0; n < nelts; n++) {
176 if (names[n].key.data == NULL) { 176 if (names[n].key.data == NULL) {
177 continue; 177 continue;
178 } 178 }
345 345
346 ngx_int_t 346 ngx_int_t
347 ngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, 347 ngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names,
348 ngx_uint_t nelts) 348 ngx_uint_t nelts)
349 { 349 {
350 size_t len; 350 size_t len, dot_len;
351 ngx_uint_t i, n, dot; 351 ngx_uint_t i, n, dot;
352 ngx_array_t curr_names, next_names; 352 ngx_array_t curr_names, next_names;
353 ngx_hash_key_t *name, *next_name; 353 ngx_hash_key_t *name, *next_name;
354 ngx_hash_init_t h; 354 ngx_hash_init_t h;
355 ngx_hash_wildcard_t *wdc; 355 ngx_hash_wildcard_t *wdc;
394 name->key_hash = hinit->key(name->key.data, name->key.len); 394 name->key_hash = hinit->key(name->key.data, name->key.len);
395 name->value = names[n].value; 395 name->value = names[n].value;
396 396
397 #if 0 397 #if 0
398 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, 398 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
399 "wc1: \"%V\"", &name->key); 399 "wc1: \"%V\" %ui", &name->key, dot);
400 #endif 400 #endif
401
402 dot_len = len + 1;
401 403
402 if (dot) { 404 if (dot) {
403 len++; 405 len++;
404 } 406 }
405 407
425 for (i = n + 1; i < nelts; i++) { 427 for (i = n + 1; i < nelts; i++) {
426 if (ngx_strncmp(names[n].key.data, names[i].key.data, len) != 0) { 428 if (ngx_strncmp(names[n].key.data, names[i].key.data, len) != 0) {
427 break; 429 break;
428 } 430 }
429 431
432 if (!dot
433 && names[i].key.len > len
434 && names[i].key.data[len] != '.')
435 {
436 break;
437 }
438
430 next_name = ngx_array_push(&next_names); 439 next_name = ngx_array_push(&next_names);
431 if (next_name == NULL) { 440 if (next_name == NULL) {
432 return NGX_ERROR; 441 return NGX_ERROR;
433 } 442 }
434 443
435 next_name->key.len = names[i].key.len - len; 444 next_name->key.len = names[i].key.len - dot_len;
436 next_name->key.data = names[i].key.data + len; 445 next_name->key.data = names[i].key.data + dot_len;
437 next_name->key_hash= 0; 446 next_name->key_hash= 0;
438 next_name->value = names[i].value; 447 next_name->value = names[i].value;
439 448
440 #if 0 449 #if 0
441 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, 450 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
442 "wc3: \"%V\"", &next_name->key); 451 "wc3: \"%V\"", &next_name->key);
443 #endif 452 #endif
444 } 453 }
445 454
446 if (next_names.nelts) { 455 if (next_names.nelts) {
456
447 h = *hinit; 457 h = *hinit;
448 h.hash = NULL; 458 h.hash = NULL;
449 459
450 if (ngx_hash_wildcard_init(&h, (ngx_hash_key_t *) next_names.elts, 460 if (ngx_hash_wildcard_init(&h, (ngx_hash_key_t *) next_names.elts,
451 next_names.nelts) 461 next_names.nelts)
457 wdc = (ngx_hash_wildcard_t *) h.hash; 467 wdc = (ngx_hash_wildcard_t *) h.hash;
458 468
459 if (names[n].key.len == len) { 469 if (names[n].key.len == len) {
460 wdc->value = names[n].value; 470 wdc->value = names[n].value;
461 #if 0 471 #if 0
462 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, 472 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
463 "wdc: \"%V\"", wdc->value); 473 "wdc: \"%V\"", wdc->value);
464 #endif 474 #endif
465 } 475 }
466 476
467 name->value = (void *) ((uintptr_t) wdc | (dot ? 1 : 3)); 477 name->value = (void *) ((uintptr_t) wdc | (dot ? 1 : 3));
468 } 478 }
679 hash->hash_size = best; 689 hash->hash_size = best;
680 hash->min_buckets = min_buckets; 690 hash->min_buckets = min_buckets;
681 691
682 return NGX_OK; 692 return NGX_OK;
683 } 693 }
694
695
696 ngx_int_t
697 ngx_hash_keys_array_init(ngx_hash_keys_arrays_t *ha, ngx_uint_t type)
698 {
699 ngx_uint_t asize;
700
701 if (type == NGX_HASH_SMALL) {
702 asize = 4;
703 ha->hsize = 107;
704
705 } else {
706 asize = NGX_HASH_LARGE_ASIZE;
707 ha->hsize = NGX_HASH_LARGE_HSIZE;
708 }
709
710 if (ngx_array_init(&ha->keys, ha->temp_pool, asize, sizeof(ngx_hash_key_t))
711 != NGX_OK)
712 {
713 return NGX_ERROR;
714 }
715
716 if (ngx_array_init(&ha->dns_wildcards, ha->temp_pool, asize,
717 sizeof(ngx_hash_key_t))
718 != NGX_OK)
719 {
720 return NGX_ERROR;
721 }
722
723 ha->keys_hash = ngx_pcalloc(ha->temp_pool, sizeof(ngx_array_t) * ha->hsize);
724 if (ha->keys_hash == NULL) {
725 return NGX_ERROR;
726 }
727
728 ha->dns_wildcards_hash = ngx_pcalloc(ha->temp_pool,
729 sizeof(ngx_array_t) * ha->hsize);
730 if (ha->dns_wildcards_hash == NULL) {
731 return NGX_ERROR;
732 }
733
734 return NGX_OK;
735 }
736
737
738 ngx_int_t
739 ngx_hash_add_key(ngx_hash_keys_arrays_t *ha, ngx_str_t *key, void *value,
740 ngx_uint_t flags)
741 {
742 size_t len;
743 ngx_str_t *name;
744 ngx_uint_t i, k, n, skip;
745 ngx_hash_key_t *hk;
746 u_char buf[2048];
747
748 if (!(flags & NGX_HASH_WILDCARD_KEY)) {
749
750 /* exact hash */
751
752 k = 0;
753
754 for (i = 0; i < key->len; i++) {
755 key->data[i] = ngx_tolower(key->data[i]);
756 k = ngx_hash(k, key->data[i]);
757 }
758
759 k %= ha->hsize;
760
761 /* check conflicts in exact hash */
762
763 name = ha->keys_hash[k].elts;
764
765 if (name) {
766 for (i = 0; i < ha->keys_hash[k].nelts; i++) {
767 if (key->len != name[i].len) {
768 continue;
769 }
770
771 if (ngx_strncmp(key->data, name[i].data, key->len) == 0) {
772 return NGX_BUSY;
773 }
774 }
775
776 } else {
777 if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4,
778 sizeof(ngx_str_t))
779 != NGX_OK)
780 {
781 return NGX_ERROR;
782 }
783 }
784
785 name = ngx_array_push(&ha->keys_hash[k]);
786 if (name == NULL) {
787 return NGX_ERROR;
788 }
789
790 *name = *key;
791
792 hk = ngx_array_push(&ha->keys);
793 if (hk == NULL) {
794 return NGX_ERROR;
795 }
796
797 hk->key = *key;
798 hk->key_hash = ngx_hash_key(key->data, key->len);
799 hk->value = value;
800
801 } else {
802
803 /* wildcard hash */
804
805 skip = (key->data[0] == '*') ? 2 : 1;
806 k = 0;
807
808 for (i = skip; i < key->len; i++) {
809 key->data[i] = ngx_tolower(key->data[i]);
810 k = ngx_hash(k, key->data[i]);
811 }
812
813 k %= ha->hsize;
814
815 if (skip == 1) {
816
817 /* check conflicts in exact hash for ".example.com" */
818
819 name = ha->keys_hash[k].elts;
820
821 if (name) {
822 len = key->len - skip;
823
824 for (i = 0; i < ha->keys_hash[k].nelts; i++) {
825 if (len != name[i].len) {
826 continue;
827 }
828
829 if (ngx_strncmp(&key->data[1], name[i].data, len) == 0) {
830 return NGX_BUSY;
831 }
832 }
833
834 } else {
835 if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4,
836 sizeof(ngx_str_t))
837 != NGX_OK)
838 {
839 return NGX_ERROR;
840 }
841 }
842
843 name = ngx_array_push(&ha->keys_hash[k]);
844 if (name == NULL) {
845 return NGX_ERROR;
846 }
847
848 name->len = key->len - 1;
849 name->data = ngx_palloc(ha->temp_pool, name->len);
850 if (name->data == NULL) {
851 return NGX_ERROR;
852 }
853
854 ngx_memcpy(name->data, &key->data[1], name->len);
855 }
856
857
858 /*
859 * convert "*.example.com" to "com.example.\0"
860 * and ".example.com" to "com.example\0"
861 */
862
863 len = 0;
864 n = 0;
865
866 for (i = key->len - 1; i; i--) {
867 if (key->data[i] == '.') {
868 ngx_memcpy(&buf[n], &key->data[i + 1], len);
869 n += len;
870 buf[n++] = '.';
871 len = 0;
872 continue;
873 }
874
875 len++;
876 }
877
878 if (len) {
879 ngx_memcpy(&buf[n], &key->data[1], len);
880 n += len;
881 }
882
883 buf[n] = '\0';
884
885
886 /* check conflicts in wildcard hash */
887
888 name = ha->dns_wildcards_hash[k].elts;
889
890 if (name) {
891 len = key->len - skip;
892
893 for (i = 0; i < ha->dns_wildcards_hash[k].nelts; i++) {
894 if (len != name[i].len) {
895 continue;
896 }
897
898 if (ngx_strncmp(key->data + skip, name[i].data, len) == 0) {
899 return NGX_BUSY;
900 }
901 }
902
903 } else {
904 if (ngx_array_init(&ha->dns_wildcards_hash[k], ha->temp_pool, 4,
905 sizeof(ngx_str_t))
906 != NGX_OK)
907 {
908 return NGX_ERROR;
909 }
910 }
911
912 name = ngx_array_push(&ha->dns_wildcards_hash[k]);
913 if (name == NULL) {
914 return NGX_ERROR;
915 }
916
917 name->len = key->len - skip;
918 name->data = ngx_palloc(ha->temp_pool, name->len);
919 if (name->data == NULL) {
920 return NGX_ERROR;
921 }
922 ngx_memcpy(name->data, key->data + skip, name->len);
923
924
925 ngx_memcpy(key->data, buf, key->len);
926 key->len--;
927
928 hk = ngx_array_push(&ha->dns_wildcards);
929 if (hk == NULL) {
930 return NGX_ERROR;
931 }
932
933 hk->key = *key;
934 hk->key_hash = 0;
935 hk->value = value;
936 }
937
938 return NGX_OK;
939 }