admin/mruby-mruby
1
0
Fork 0
mirror of https://github.com/mruby/mruby synced 2026-06-08 16:11:16 +00:00
Code Issues Packages Projects Releases Wiki Activity
18,905 Commits 6 Branches 38 Tags
master
Commit Graph

44 Commits

Author SHA1 Message Date
Yukihiro "Matz" Matsumoto fbaedfeaad test/hash.rb: remove Hash#freeze before Hash#rehash; ref #6485 2025-03-08 11:25:49 +09:00
Yukihiro "Matz" Matsumoto 6037e50298 test/hash: update tests to new hash format 2024-12-21 08:53:57 +09:00
Yukihiro "Matz" Matsumoto 5387b74be7 hash.c (mrb_hash_to_s): put spaces around => 
CRuby 3.4 puts spaces around `=>` since for example `{:a!=>2}` can be
confusing where to separate tokens.  mruby should follow the behavior.

Many tests in `test/t` directory assumed no spaces around `=>`, so we
needed to fix them too.
 2024-11-11 11:07:43 +09:00
Yukihiro "Matz" Matsumoto 313c5a31ac test/hash.rb: add tests for Hash#assoc and Hash#rassoc 2024-07-18 15:09:49 +09:00
John Bampton 983a13f342 Fix typo in test/t/hash.rb 2024-04-21 22:21:57 +10:00
Yukihiro "Matz" Matsumoto a638a71c72 test/hash.rb: remove some inspect/to_s tests 
CRuby does prohibits Hash modification during iteration, so remove those
self modifying inspect/to_s.
 2023-06-17 17:56:41 +09:00
Yukihiro "Matz" Matsumoto 0565bbf85a test/hash.rb: test Hash#merge that takes multiple arguments. 2022-06-18 08:30:26 +09:00
Yukihiro "Matz" Matsumoto 6c76926d05 parse.y: allow value omission in Hash literals introduced in Ruby3.1. 
`{x:, y:}` now is a syntax sugar of `{x: x, y: y}`.

This fix also includes the update of #4815 fix.
 2021-09-13 11:04:27 +09:00
Yukihiro "Matz" Matsumoto c0d63ea09f hash.c: Hash#shift to return nil when a hash is empty. 
It used to be return the default value if available, but it should
ignore the default value for behavior consistency. CRuby will adopt
this behavior too in the future. [ruby-bugs:16908]
 2021-03-17 15:14:23 +09:00
KOBAYASHI Shuji 28eb6271ba Fix heap-buffer-overflow for small Hash (HT) in Hash#rehash 
### Example

##### example.rb

```ruby
h = {}
(1..17).each{h[_1] = _1}
(1..16).each{h.delete(_1)}
h.rehash
```

##### ASAN report

```console
$ bin/mruby example.rb
==52587==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000006998 at pc 0x55a29cddf96b bp 0x7fff7b1b1720 sp 0x7fff7b1b1710
READ of size 4 at 0x602000006998 thread T0
    #0 0x55a29cddf96a in ib_it_next /mruby/src/hash.c:639
    #1 0x55a29cde2ca2 in ht_rehash /mruby/src/hash.c:900
    #2 0x55a29cde379f in h_rehash /mruby/src/hash.c:996
    #3 0x55a29cde7f3d in mrb_hash_rehash /mruby/src/hash.c:1735
    #4 0x55a29ce77b62 in mrb_vm_exec /mruby/src/vm.c:1451
    #5 0x55a29ce5fa88 in mrb_vm_run /mruby/src/vm.c:981
    #6 0x55a29ceb87e1 in mrb_top_run /mruby/src/vm.c:2874
    #7 0x55a29cf36bdf in mrb_load_exec mrbgems/mruby-compiler/core/parse.y:6805
    #8 0x55a29cf36f25 in mrb_load_detect_file_cxt mrbgems/mruby-compiler/core/parse.y:6848
    #9 0x55a29cdba0a2 in main /mruby/mrbgems/mruby-bin-mruby/tools/mruby/mruby.c:347
    #10 0x7f24ef43b0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #11 0x55a29cdb4a6d in _start (/mruby/bin/mruby+0x2a3a6d)

0x602000006998 is located 0 bytes to the right of 8-byte region [0x602000006990,0x602000006998)
allocated by thread T0 here:
    #0 0x7f24f01cfffe in __interceptor_realloc (/lib/x86_64-linux-gnu/libasan.so.5+0x10dffe)
    #1 0x55a29ceb9440 in mrb_default_allocf /mruby/src/state.c:68
    #2 0x55a29cdba747 in mrb_realloc_simple /mruby/src/gc.c:228
    #3 0x55a29cdba928 in mrb_realloc /mruby/src/gc.c:242
    #4 0x55a29cde12e5 in ht_init /mruby/src/hash.c:749
    #5 0x55a29cde2b8e in ht_rehash /mruby/src/hash.c:897
    #6 0x55a29cde379f in h_rehash /mruby/src/hash.c:996
    #7 0x55a29cde7f3d in mrb_hash_rehash /mruby/src/hash.c:1735
    #8 0x55a29ce77b62 in mrb_vm_exec /mruby/src/vm.c:1451
    #9 0x55a29ce5fa88 in mrb_vm_run /mruby/src/vm.c:981
    #10 0x55a29ceb87e1 in mrb_top_run /mruby/src/vm.c:2874
    #11 0x55a29cf36bdf in mrb_load_exec mrbgems/mruby-compiler/core/parse.y:6805
    #12 0x55a29cf36f25 in mrb_load_detect_file_cxt mrbgems/mruby-compiler/core/parse.y:6848
    #13 0x55a29cdba0a2 in main /mruby/mrbgems/mruby-bin-mruby/tools/mruby/mruby.c:347
    #14 0x7f24ef43b0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
```
 2021-02-10 20:03:34 +09:00
KOBAYASHI Shuji f2d8db39be Reduce memory usage of Hash object 
## Implementation Summary

* Change entry list from segmented list to flat array.
* Change value of hash bucket from pointer to entry to index of entry list,
  and represent it by variable length bits according to capacity of hash
  buckets.
* Store management information about entry list and hash table to `struct
  RHash` as much as possible.

## Benchmark Summary

Only the results of typical situations on 64-bit Word-boxing are present
here. For more detailed information, including consideration, see below
(although most of the body is written in Japanese).

* https://shuujii.github.io/mruby-hash-benchmark

### Memory Usage

Lower value is better.

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 |          344B |          256B |   0.74419x |
|        40 |        1,464B |          840B |   0.57377x |
|       200 |        8,056B |        3,784B |   0.46971x |
|       500 |       17,169B |        9,944B |   0.57949x |

### Performance

Higher value is better.

#### `mrb_hash_set`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 |  1.41847M i/s |  1.36004M i/s |   0.95881x |
|        40 |  0.39224M i/s |  0.31888M i/s |   0.81296x |
|       200 |  0.03780M i/s |  0.04290M i/s |   1.13494x |
|       500 |  0.01225M i/s |  0.01314M i/s |   1.07275x |

#### `mrb_hash_get`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 | 26.05920M i/s | 30.19543M i/s |   1.15872x |
|        40 | 44.26420M i/s | 32.75781M i/s |   0.74005x |
|       200 | 44.55171M i/s | 31.56926M i/s |   0.70860x |
|       500 | 39.19250M i/s | 29.73806M i/s |   0.75877x |

#### `mrb_hash_each`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 | 25.11964M i/s | 30.34167M i/s |   1.20789x |
|        40 | 11.74253M i/s | 13.25539M i/s |   1.12884x |
|       200 |  2.01133M i/s |  2.97214M i/s |   1.47770x |
|       500 |  0.87411M i/s |  1.21178M i/s |   1.38631x |

#### `Hash#[]=`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 |  0.50095M i/s |  0.56490M i/s |   1.12764x |
|        40 |  0.19132M i/s |  0.18392M i/s |   0.96129x |
|       200 |  0.03624M i/s |  0.03256M i/s |   0.89860x |
|       500 |  0.01527M i/s |  0.01236M i/s |   0.80935x |
#### `Hash#[]`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 | 11.53211M i/s | 12.78806M i/s |   1.10891x |
|        40 | 15.26920M i/s | 13.37529M i/s |   0.87596x |
|       200 | 15.28550M i/s | 13.36410M i/s |   0.87430x |
|       500 | 14.57695M i/s | 12.75388M i/s |   0.87494x |

#### `Hash#each`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 |  0.30462M i/s |  0.27080M i/s |   0.88898x |
|        40 |  0.12912M i/s |  0.11704M i/s |   0.90642x |
|       200 |  0.02638M i/s |  0.02402M i/s |   0.91071x |
|       500 |  0.01066M i/s |  0.00959M i/s |   0.89953x |

#### `Hash#delete`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 |  7.84167M i/s |  6.96419M i/s |   0.88810x |
|        40 |  6.91292M i/s |  7.41427M i/s |   1.07252x |
|       200 |  3.75952M i/s |  7.32080M i/s |   1.94727x |
|       500 |  2.10754M i/s |  7.05963M i/s |   3.34970x |

#### `Hash#shift`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 | 14.66444M i/s | 13.18876M i/s |   0.89937x |
|        40 | 11.95124M i/s | 11.10420M i/s |   0.92913x |
|       200 |  5.53681M i/s |  7.88155M i/s |   1.42348x |
|       500 |  2.96728M i/s |  5.40405M i/s |   1.82121x |

#### `Hash#dup`

| Hash Size |   Baseline    |      New      |   Factor   |
|----------:|--------------:|--------------:|-----------:|
|        16 |  0.15063M i/s |  5.37889M i/s |  35.71024x |
|        40 |  0.06515M i/s |  3.38196M i/s |  51.91279x |
|       200 |  0.01359M i/s |  1.46538M i/s | 107.84056x |
|       500 |  0.00559M i/s |  0.75411M i/s | 134.88057x |

### Binary Size

Lower value is better.

|    File    |   Baseline    |      New      |  Factor   |
|:-----------|--------------:|--------------:|----------:|
| mruby      |      730,408B |      734,176B |  1.00519x |
| libmruby.a |    1,068,134B |    1,072,846B |  1.00441x |

## Other Fixes

The following issues have also been fixed in the parts where there was some
change this time.

* [Heap use-after-free in `Hash#value?`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-hash-value-md)
* [Heap use-after-free in `ht_hash_equal`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-ht_hash_equal-md)
* [Heap use-after-free in `ht_hash_func`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-ht_hash_func-md)
* [Heap use-after-free in `mrb_hash_merge`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-mrb_hash_merge-md)
* [Self-replacement does not work for `Hash#replace`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-self-replacement-does-not-work-for-hash-replace-md)
* [Repeated deletes and inserts increase memory usage of `Hash`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-repeated-deletes-and-inserts-increase-memory-usage-of-hash-md)
* [`Hash#rehash` does not reindex completely](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-hash-rehash-does-not-reindex-completely-md)
* `mrb_hash_delete_key` does not cause an error for frozen object
* `mrb_hash_new_capa` does not allocate required space first
* [`mrb_os_memsize_of_hash_table` result is incorrect](https://github.com/mruby/mruby/pull/5032#discussion_r457994075)
 2020-11-10 15:21:49 +09:00
Yukihiro "Matz" Matsumoto d605b72c1d Merge branch 'master' into i110/inspect-recursion 2019-07-17 10:35:41 +09:00
KOBAYASHI Shuji fbad7a1595 Use FrozenError instead of RuntimeError in frozen object modification test 2019-03-19 20:48:32 +09:00
Yukihiro "Matz" Matsumoto cca19532c5 Remove Kernel#class_defined? which is not available in CRuby; #3829 2019-01-03 11:34:35 +09:00
Yukihiro "Matz" Matsumoto 82e00ce60f Hash#delete should return the deleted value; fix #4133 2018-10-12 08:25:54 +09:00
Ichito Nagata 2af92d0ebc Let inspect recursion do the right thing 2018-06-04 11:25:10 +09:00
YAMAMOTO Masaya dcd5d0ffec Test for MRB_WITHOUT_FLOAT 2017-10-11 17:58:11 +09:00
Takashi Kokubun 10bb7ad693 Implement Object#freeze 2016-12-11 03:44:15 +09:00
Shugo Maeda 338e0ff52d Copy default_proc by Hash#dup. 2016-12-07 22:39:20 +09:00
Yutaka HARA 3f83ec64a8 Add test for recently fixed bugs 2016-12-01 14:55:26 +09:00
Sayed Abdelhaleem f5f48d9400 protect NoMethodError from calling to_hash in replace 2016-01-27 21:17:33 +02:00
Yukihiro "Matz" Matsumoto 698b3c925d add Hash#rehash to handle key modification; ref #2945 2015-09-10 23:03:53 +09:00
take_cheeze ec5b055694 Move direct superclass checking to test/t/superclass.rb. 2014-06-15 15:02:21 +09:00
Jun Hiroe ab2ce33859 Fix Hash test 2014-05-12 20:47:44 +09:00
yui-knk 658a00ba49 Change to raise TypeError (Hash#merge, #merge!) 2014-05-10 10:18:15 +09:00
Nobuyoshi Nakada ab67c57f65 remove trailing spaces 2014-04-30 09:50:14 +09:00
Yukihiro "Matz" Matsumoto 59cd24d41f Hash#replace should copy default as well; close #2004 2014-04-04 12:14:23 +09:00
Yukihiro "Matz" Matsumoto 8cfd5f17da merge test code from #2003 2014-04-04 11:06:11 +09:00
Yukihiro "Matz" Matsumoto b868ce8a77 Hash#shift may return any entries 2014-03-15 15:01:17 +09:00
ksss d7b179475b fix #1823 2014-03-08 17:51:21 +09:00
ksss cab1f734ef Fix behavior Hash#eql? 2014-03-07 11:08:24 +09:00
Li Yazhou 7ab0506795 add test for Hash#dup 2014-02-14 13:26:19 +08:00
Jun Hiroe 284dc1be09 I fix order of actual and expect test value in hash.rb. 2013-08-02 20:54:21 +09:00
Daniel Bovensiepen b1c309cc87 Improve Hash Tests 2013-06-15 00:54:58 +08:00
Masaki Muranaka 71cc4e13bf Add more test cases for test coverage. 2013-05-08 13:22:35 +09:00
Masaki Muranaka e129a4c8ef Add test cases. 2013-04-02 11:43:30 +09:00
Daniel Bovensiepen 0c2d74020a Add more superclass tests 2012-06-03 23:31:53 +08:00
Daniel Bovensiepen 2c58690df1 Add test cases for Hash 2012-06-02 23:39:00 +08:00
Yukihiro Matsumoto 1ac22054bc remove debug print 2012-05-30 16:25:51 +09:00
Yukihiro Matsumoto a4a48e3da1 specify allocating array size for Hash#values 2012-05-30 16:12:32 +09:00
Daniel Bovensiepen 31e9705022 Add Test cases for Literals, Enumeration, Exceptions and clean line endings 2012-05-29 01:20:46 +08:00
Yukihiro Matsumoto 52b2d092d3 test t/*.rb spacing fix 2012-05-23 12:00:49 +09:00
Daniel Bovensiepen e1e072b800 Fix Hash#shift return value from Hash to Array 2012-05-20 13:18:34 +08:00
Daniel Bovensiepen d45ecc3270 Complete ISO test cases for Hash, Range, String and Symbol 2012-05-19 23:18:42 +08:00