Mercurial > hg > nginx-vendor-1-0
comparison src/core/ngx_hash.c @ 142:84910468f6de NGINX_0_3_18
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 } |