Age | Commit message (Collapse) | Author |
|
st.c: retry operations if rebuilt
Calling the .eql? and .hash methods during a Hash operation can
result in a thread switch or a signal handler to run: allowing
one execution context to rebuild the hash table while another is
still reading or writing the table. This results in a
use-after-free bug affecting the thread_safe-0.3.6 test suite
and likely other bugs.
This bug did not affect users of commonly keys (String, Symbol,
Fixnum) as those are optimized to avoid method dispatch
for .eql? and .hash methods.
A separate version of this change needs to be ported to Ruby 2.3.x
which had a different implementation of st.c but was affected
by the same bug.
* st.c: Add comment about table rebuilding during comparison.
(DO_PTR_EQUAL_CHECK): New macro.
(REBUILT_TABLE_ENTRY_IND, REBUILT_TABLE_BIN_IND): New macros.
(find_entry, find_table_entry_ind, find_table_bin_ind): Use new
macros. Return the rebuild flag.
(find_table_bin_ptr_and_reserve): Ditto.
(st_lookup, st_get_key, st_insert, st_insert2): Retry the
operation if the table was rebuilt.
(st_general_delete, st_shift, st_update, st_general_foreach):
Ditto.
(st_rehash_linear, st_rehash_indexed): Use DO_PTR_EQUAL_CHECK.
Return the rebuild flag.
(st_rehash): Retry the operation if the table was rebuilt.
[ruby-core:85510] [Ruby trunk Bug#14357]
Thanks to Vit Ondruch for reporting the bug.
From: Vladimir Makarov <vmakarov@redhat.com>
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/branches/ruby_2_4@63805 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
st.c: fix num_entries
* st.c (st_insert2): should manage num_entries when the key is
undefined, as well as st_insert().
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/branches/ruby_2_4@61328 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* st.c (st_hash): suppress unused label warning on 32bit
platforms. fix up r57134.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@57138 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
Previous implementation had an issues:
- macros murmur1 assumes murmur_step takes rotation value
as a second argument
- but murmur_step second argument is "next block"
- this makes st_hash_uint and st_hash_end to not mix high bits of
hash value into lower bits
- this leads to pure hash behavior on doubles and mixing hashes using
st_hash_uint.
It didn't matter when bins amount were prime numbers, but it hurts
when bins are powers of two.
Mistake were created cause of attempt to co-exist Murmur1 and Murmur2
in a same code.
Change it to single hash-function implementation.
- block function is in a spirit of Murmur functions,
but handles inter-block dependency a bit better (imho).
- final block is read in bit more optimal way on CPU with unaligned word access,
- final block is mixed in simple way,
- finalizer is taken from MurmurHash3 (it makes most of magic :) )
(64bit finalizer is taken from
http://zimbry.blogspot.ru/2011/09/better-bit-mixing-improving-on.html)
Also remove ST_USE_FNV1: it lacks implementation of many functions,
and looks to be abandoned
Author: Sokolov Yura aka funny_falcon <funny.falcon@gmail.com>
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@57134 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
patched by Ken Takata [ruby-core:78558]
https://github.com/k-takata/Onigmo/commit/44e3c0a16da1116be641ea807c1202434b743ace
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@57065 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* st.h (struct st_hash_type): Remove strong_hash.
(struct st_table): Remove inside_rebuild_p and curr_hash.
* st.c (do_hash): Use type->hash instead of curr_hash.
(make_tab_empty): Remove setting up curr_hash.
(st_init_table_with_size): Remove setting up inside_rebuild_p.
(rebuild_table): Remove clearing inside_rebuild_p.
(reset_entry_hashes, HIT_THRESHOULD_FOR_STRONG_HASH): Remove code
recognizing a denial attack and switching to strong hash.
* hash.c (rb_dbl_long_hash, rb_objid_hash, rb_ident_hash): Use
rb_hash_start to randomize the hash.
(str_seed): Remove.
(any_hash): Remove strong_p and use always rb_str_hash for
strings.
(any_hash_weak, rb_any_hash_weak): Remove.
(st_hash_type objhash): Remove rb_any_hash_weak.
based on the patch by Vladimir N Makarov <vmakarov@redhat.com> at
[ruby-core:78490]. [Bug #13002]
* test/ruby/test_hash.rb (test_wrapper): objects other than special
constants should be able to be wrapped.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@56992 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* st.c (do_hash): remove unnecessary variable and cast.
* hash.c, numeric.c, st.c: adjust style and indent.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@56991 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
From: Vladimir Makarov <vmakarov@redhat.com>
By Vladimir's estimation, this requires at least 64 GB of memory
to reproduce this bug due to the hash sizes required. So there
is no new test case (and I am unable to test it, myself).
* st.c (get_bins_num): avoid out-of-bounds on shift by using correct type
[ruby-core:78139] [Bug #12939]
* st.c (get_allocated_entries): ditto
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@56793 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
[Feature #12142]
See header of st.c for improvment details.
You can see all of code history here:
<https://github.com/vnmakarov/ruby/tree/hash_tables_with_open_addressing>
This improvement is discussed at
<https://bugs.ruby-lang.org/issues/12142>
with many people, especially with Yura Sokolov.
* st.c: improve st_table.
* include/ruby/st.h: ditto.
* internal.h, numeric.c, hash.c (rb_dbl_long_hash): extract a function.
* ext/-test-/st/foreach/foreach.c: catch up this change.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@56650 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
and define CONSTFUNC and PUREFUNC if available.
Note that I don't add those options as default because
it still shows many false-positive (it seems not to consider
longjmp).
* vm_eval.c (stack_check): get rb_thread_t* as an argument
to avoid duplicate call of GET_THREAD().
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@54952 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
Released GCC 6.0 fixed the issue.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69291
[ruby-core:72211] [Bug #11831] [Bug #11979]
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@54855 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* st.c (stat_col): get rid of NaN.
* st.c (collision_check): define before used.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@54438 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* include/ruby/defines.h, st.c: disable unaligned word access with
gcc 6 or later. [Bug #11831]
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@53546 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
Minor size reduction on 32-bit x86:
text data bss dec hex filename
13742 24 0 13766 35c6 st.o
14166 24 0 14190 376e st-orig.o
Public API change to be proposed separately.
* st.c (find_entry): constify st_table*
(find_packed_index_from): ditto
(find_packed_index): ditto
(get_keys): ditto
(get_values): ditto
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@51438 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* st.c (EQUAL, st_delete_safe): fix arguments order to compare
function, searching key is the first and stored key is the
second always.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@51364 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
variable used). I think that these are wrong, but should shut them
up.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@51105 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
This improves the bm_vm2_bighash benchmark significantly by
removing branches during insert, but slows down anything
requiring iteration with the more complex loop termination
checking.
Speedup ratio of 1.10 - 1.20 is typical for the vm2_bighash
benchmark.
v3 - st_head calculates list_head address in two steps
to avoid a bug in old gcc 4.4 (Debian 4.4.7-2)
bug which incorrectly warned with:
warning: dereferencing pointer ‘({anonymous})’ does break
strict-aliasing rules
* include/ruby/st.h (struct st_table): hide struct list_head
* st.c (struct st_table_entry): adjust struct
(head, tail): remove shortcut macros
(st_head): new wrapper function
(st_init_table_with_size): adjust to new struct and API
(st_clear): ditto
(add_direct): ditto
(unpack_entries): ditto
(rehash): ditto
(st_copy): ditto
(remove_entry): ditto
(st_shift): ditto
(st_foreach_check): ditto
(st_foreach): ditto
(get_keys): ditto
(get_values): ditto
(st_values_check): ditto
(st_reverse_foreach_check): ditto (unused)
(st_reverse_foreach): ditto (unused)
[ruby-core:69726] [Misc #10278]
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@51064 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
This reverts commit r51044
Still getting failure notices from ko1's CI machine.
ref: g3qkqn
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@51045 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
This improves the bm_vm2_bighash benchmark significantly by
removing branches during insert, but slows down anything
requiring iteration with the more complex loop termination
checking.
Speedup ratio of 1.10 - 1.20 is typical for the vm2_bighash
benchmark.
* include/ruby/st.h (struct st_table): hide struct list_head
* st.c (struct st_table_entry): adjust struct
(head, tail): remove shortcut macros
(st_head): new wrapper function
(st_init_table_with_size): adjust to new struct and API
(st_clear): ditto
(add_direct): ditto
(unpack_entries): ditto
(rehash): ditto
(st_copy): ditto
(remove_entry): ditto
(st_shift): ditto
(st_foreach_check): ditto
(st_foreach): ditto
(get_keys): ditto
(get_values): ditto
(st_values_check): ditto
(st_reverse_foreach_check): ditto (unused)
(st_reverse_foreach): ditto (unused)
[ruby-core:69726] [Misc #10278]
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@51044 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
I suspect the build failures with r51034 ("st.c: use ccan linked-list")
on ko1's CI machine was due to me forgetting to update common.mk :x
Lets see what happens when I only include ccan/list/list.h
Will followup with appropriate reverts or reinstating the
rest of r51034 along with a common.mk update as I watch CI
build.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@51041 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
Maybe this will stop mysterious CI failures from ko1@sasada-8core:
リビジョン 51034 です。
make[1]: ディレクトリ `/mnt/sdb1/ruby/build' に入ります
../trunk/revision.h unchanged
make[1]: ディレクトリ `/mnt/sdb1/ruby/build' から出ます
make[1]: ディレクトリ `/mnt/sdb1/ruby/build' に入ります
config.guess already exists
config.sub already exists
generating ../trunk/ext/ripper/ripper.c
make[2]: ディレクトリ `/mnt/sdb1/ruby/trunk/ext/ripper' に入ります
extracting ripper.y from ../../parse.y
id.h not found in ["../.."]
make[2]: *** [ripper.y] エラー 1
make[2]: ディレクトリ `/mnt/sdb1/ruby/trunk/ext/ripper' から出ます
make[1]: *** [../trunk/ext/ripper/ripper.c] エラー 2
make[1]: ディレクトリ `/mnt/sdb1/ruby/build' から出ます
make: [up] エラー 2 (無視されました)
make: *** [.rbconfig.time] セグメンテーション違反です
Command exited with non-zero status 2
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@51035 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
This improves the bm_vm2_bighash benchmark significantly by
removing branches during insert, but slows down anything
requiring iteration with the more complex loop termination
checking.
Speedup ratio of 1.10 - 1.20 is typical for the vm2_bighash
benchmark.
* include/ruby/st.h (struct st_table): hide struct list_head
* st.c (struct st_table_entry): adjust struct
(head, tail): remove shortcut macros
(st_head): new wrapper function
(st_init_table_with_size): adjust to new struct and API
(st_clear): ditto
(add_direct): ditto
(unpack_entries): ditto
(rehash): ditto
(st_copy): ditto
(remove_entry): ditto
(st_shift): ditto
(st_foreach_check): ditto
(st_foreach): ditto
(get_keys): ditto
(get_values): ditto
(st_values_check): ditto
(st_reverse_foreach_check): ditto (unused)
(st_reverse_foreach): ditto (unused)
[ruby-core:69726] [Misc #10278]
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@51034 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* hash.c (rb_ident_hash): move compare_by_identity specific
function from st.c.
* hash.c (rb_ident_hash_new): ditto from thread.c.
* st.c (st_numhash): remove ruby's Hash specific implementation.
* thread.c (recursive_list_access): use rb_ident_hash_new().
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@49386 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* st.c (st_numhash): mix float value for flonum
* hash.c (rb_any_hash): ditto
* benchmark/bm_hash_aref_flo.rb: new benchmark
* benchmark/bm_hash_ident_flo.rb: ditto
[Bug #10761]
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@49376 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
includable without prior inclusion.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@48447 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* st.c: include "internal.h" for STATIC_ASSERT.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@48393 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* st.c (st_reverse_foreach): update as st_foreach().
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@47788 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
Reduces object size slightly on x86-64:
text data bss dec hex filename
2782359 22400 71880 2876639 2be4df ruby.orig
2781831 22400 71880 2876111 2be2cf ruby.pow2
And on 32-bit x86:
text data bss dec hex filename
2814751 12100 30552 2857403 2b99bb ruby.orig
2814051 12100 30552 2856703 2b96ff ruby.pow2
This is not a performance-critical function, but the
smaller icache footprint seems worth it.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@47767 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@47675 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* node.c (F_CUSTOM2): unused.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@47673 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* include/ruby/defines.h, siphash.c, st.c (UNALIGNED_WORD_ACCESS):
add PowerPC64 too, which is capable to access unaligned words.
patched by Gustavo Frederico Temple Pedrosa in [ruby-core:63937].
[Feature #10081]
* regint.h (PLATFORM_UNALIGNED_WORD_ACCESS): ditto.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@46915 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* st.c (st_update): old_key is uninitialized by jump to the label
unpacked.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@46725 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* st.c (st_update): remove equality checks, callers should ensure
the equality, otherwise the behavior is undefined.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@46723 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* st.c (st_update): re-calculate hash_val before adding if key was
changed, otherwise cannot access the newly added element if it
has different hash value.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@46722 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* st.c (st_update): fix a bug that the key was not updated even if
it was changed by the callback function.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@46720 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* configure.in (with-jemalloc): also check for header, for ABIs
which JEMALLOC_MANGLE is needed, i.e., Mach-O and PE-COFF
platforms. [ruby-core:62939] [Feature #9113]
* include/ruby/missing.h: include alternative malloc header to
replace memory management functions.
* dln.c, io.c, parse.y, st.c: undef malloc family before
re-definition to suppress warnings.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@46354 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
from top to current. [ruby-dev:48047] [Bug #9646]
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@45642 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@45481 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* st.c (hash_pos): use bitwise AND to avoid slow modulo op
(new_size): power-of-two sizes for hash_pos change
(st_numhash): adjust for common keys due to lack of prime modulo
[Feature #9425]
* hash.c (rb_any_hash): right shift for symbols
* benchmark/bm_hash_aref_miss.rb: added to show improvement
* benchmark/bm_hash_aref_sym_long.rb: ditto
* benchmark/bm_hash_aref_str.rb: ditto
* benchmark/bm_hash_aref_sym.rb: ditto
* benchmark/bm_hash_ident_num.rb: added to prevent regression
* benchmark/bm_hash_ident_obj.rb: ditto
* benchmark/bm_hash_ident_str.rb: ditto
* benchmark/bm_hash_ident_sym.rb: ditto
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@45384 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@45336 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@45266 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* st.c (hash_pos): extract mapping hash values to hash bins index.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@44634 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@44009 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* include/ruby/st.h: add prototypes for above.
* hash.c (rb_hash_values): use st_values_check() for performance
improvement if VALUE and st_data_t are compatible.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@43895 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* include/ruby/st.h: define modified prototype.
* hash.c (rb_hash_keys): use modified st_keys().
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@43894 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* hash.c (rb_hash_keys): use st_keys() for performance improvement
if st_data_t and VALUE are compatible.
* st.h: define macro ST_DATA_COMPATIBLE_P() to predicate whether
st_data_t and passed type are compatible.
* configure.in: check existence of builtin function to use in
ST_DATA_COMPATIBLE_P().
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@43885 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* hash.c (foreach_safe_i, hash_foreach_iter): deal with error detected
by ST_CHECK.
* st.c (st_foreach_check): call with non-error argument in normal case.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@43674 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
* st.c: revert st_keys() at r43238. VALUE cannot be in st.c.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@43243 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
Hash#keys and Array#uniq.
* st.h: ditto.
* hash.c (rb_hash_keys): use st_keys().
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@43238 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|
|
(st_locale_insensitive_strncasecmp): Renamed from st_strncasecmp.
* include/ruby/st.h: Follow above changes.
* include/ruby/ruby.h: Ditto.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@42012 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
|