Delay breaking out of the parse loop when max_tree_depth is hit #3100

stevecheckoway · 2024-01-16T01:40:48Z

When a token causes a node to be added to the DOM which increases the depth of the DOM to exceed the max_tree_depth and the token needs to be reprocessed, memory is leaked. By delaying breaking out of the loop until after the token has been completely handled, this appears to fix the leak.

Fixes #3098

What problem is this PR intended to solve?
#3098

Have you included adequate test coverage?
No! I don't know how to test this. Help is appreciated here.

Does this change affect the behavior of either the C or the Java implementations?

Fixes a bug in the C implementation.

More investigation is needed to be sure it actually fixes the issue, however.

When a token causes a node to be added to the DOM which increases the depth of the DOM to exceed the `max_tree_depth` _and_ the token needs to be reprocessed, memory is leaked. By delaying breaking out of the loop until after the token has been completely handled, this appears to fix the leak. Fixes sparklemotion#3098

flavorjones · 2024-01-16T14:48:47Z

@stevecheckoway If you can add a test case (like I did in 84f1706 for example), then the test:memcheck rake task will run the test suite under valgrind and should detect any leaked memory (it uses https://github.com/Shopify/ruby_memcheck which is quite good at this point).

flavorjones · 2024-01-16T14:55:11Z

OK - more explicit instructions on how to reproduce. Add this to test/test_memory_usage.rb:

    it "libgumbo max depth exceeded" do
      html = '<html><body>'

      memwatch(__method__) do
        begin
          Nokogiri::HTML5.parse(html, max_tree_depth: 1)
        rescue ArgumentError
        end
      end
    end

then run:

bundle exec rake test:memory_suite TESTOPTS=-n/MEMORY_SUITE.*max.depth/

which will show you memory utilization (vmsize) over many loops:

memwatch: test_0016_libgumbo max depth exceeded: (n=1        0) 776528 Kb
memwatch: test_0016_libgumbo max depth exceeded: (n=2   189200) 776564 Kb, Δ +36
memwatch: test_0016_libgumbo max depth exceeded: (n=3   378400) 791372 Kb, Δ +14808
memwatch: test_0016_libgumbo max depth exceeded: (n=4   567600) 798104 Kb, Δ +6732
memwatch: test_0016_libgumbo max depth exceeded: (n=5   756800) 804968 Kb, Δ +6864
memwatch: test_0016_libgumbo max depth exceeded: (n=6   946000) 811832 Kb, Δ +6864
memwatch: test_0016_libgumbo max depth exceeded: (n=7  1135200) 818696 Kb, Δ +6864
memwatch: test_0016_libgumbo max depth exceeded: (n=8  1324400) 825560 Kb, Δ +6864
memwatch: test_0016_libgumbo max depth exceeded: (n=9  1513600) 832424 Kb, Δ +6864
memwatch: test_0016_libgumbo max depth exceeded: (n=10 1702800) 839288 Kb, Δ +6864
memwatch: test_0016_libgumbo max depth exceeded: (n=11 1892000) 846152 Kb, Δ +6864
memwatch: test_0016_libgumbo max depth exceeded: elapsed 10.110214s
memwatch: test_0016_libgumbo max depth exceeded: slope = 38.90984 (r^2 = 0.992)
F

Finished in 21.766011s, 0.0459 runs/s, 0.1378 assertions/s.

  1) Failure:
MEMORY_SUITE#test_0016_libgumbo max depth exceeded [/home/flavorjones/code/oss/nokogiri/test/helper.rb:368]:
best-fit slope 38.90983509513742 (r^2=0.9923971127588868) should be close to zero

or to get valgrind to dump more detailed info:

bundle exec rake test:memcheck TESTOPTS=-n/MEMORY_SUITE.*max.depth/

which emits:

1 runs, 1 assertions, 0 failures, 0 errors, 0 skips
32,144 bytes in 4,018 blocks are definitely lost in loss record 33,645 of 33,761
  malloc (vg_replace_malloc.c:381)
 *gumbo_alloc (util.c:25)
 *gumbo_vector_init (vector.c:28)
 *start_new_tag (tokenizer.c:694)
 *handle_tag_open_state (tokenizer.c:1074)
 *gumbo_lex (tokenizer.c:3414)
 *gumbo_parse_with_options (parser.c:4765)
 *perform_parse (gumbo.c:94)
 *parse (gumbo.c:332)
  call_cfunc_6 (vm_insnhelper.c:2992)
  vm_call_cfunc_with_frame (vm_insnhelper.c:3268)
  vm_sendish (vm_insnhelper.c:5080)
  vm_exec_core (insns.def:820)
  rb_vm_exec (vm.c:2374)

stevecheckoway · 2024-01-16T17:19:13Z

Thanks for the help with the test! I still need to make sure that without this change the test fails. Somehow none of the Linux machines in my house are set up as dev machines currently, but I'll test in a VM a bit later today.

flavorjones · 2024-01-16T20:24:07Z

@stevecheckoway please consider using the CI infrastructure, we run those memory tests (both flavors of memory leak test) in CI.

so you could push the repro to this branch, see it fail in CI, then push the fix to the branch, and see it pass.

let me know if I can help at all? (the output I posted above is actually from the repro so I can test it both ways locally very easily)

stevecheckoway · 2024-01-16T20:32:54Z

With this PR applied, I get

root@32cdd9ed4118:~/nokogiri# bundle exec rake test:memory_suite TESTOPTS=-n/MEMORY_SUITE.*max.depth/
/usr/local/bin/ruby -w -I"lib:test" /usr/local/lib/ruby/gems/3.3.0/gems/rake-13.1.0/lib/rake/rake_test_loader.rb "test/test_memory_usage.rb" -n/MEMORY_SUITE.*max.depth/
/root/nokogiri/test/helper.rb:46: version info:
---
warnings: []
nokogiri:
  version: 1.16.0
  cppflags:
  - "-I/root/nokogiri/ext/nokogiri"
  - "-I/root/nokogiri/ext/nokogiri/include"
  - "-I/root/nokogiri/ext/nokogiri/include/libxml2"
  ldflags: []
ruby:
  version: 3.3.0
  platform: aarch64-linux
  gem_platform: aarch64-linux
  description: ruby 3.3.0 (2023-12-25 revision 5124f9ac75) [aarch64-linux]
  engine: ruby
libxml:
  source: packaged
  precompiled: false
  patches:
  - 0001-Remove-script-macro-support.patch
  - 0002-Update-entities-to-remove-handling-of-ssi.patch
  - 0003-libxml2.la-is-in-top_builddir.patch
  - '0009-allow-wildcard-namespaces.patch'
  - 0010-update-config.guess-and-config.sub-for-libxml2.patch
  - 0011-rip-out-libxml2-s-libc_single_threaded-support.patch
  memory_management: ruby
  iconv_enabled: true
  compiled: 2.12.4
  loaded: 2.12.4
libxslt:
  source: packaged
  precompiled: false
  patches:
  - 0001-update-config.guess-and-config.sub-for-libxslt.patch
  datetime_enabled: true
  compiled: 1.1.39
  loaded: 1.1.39
other_libraries:
  libgumbo: 1.0.0-nokogiri
NOKOGIRI_TEST_GC_LEVEL: major
Run options: -n/MEMORY_SUITE.*max.depth/ --seed 27504

# Running:


memwatch: test_0016_libgumbo max depth exceeded: (n=1        0) 827480 Kb
memwatch: test_0016_libgumbo max depth exceeded: (n=2   304400) 827480 Kb, Δ +0
memwatch: test_0016_libgumbo max depth exceeded: (n=3   608800) 827480 Kb, Δ +0
memwatch: test_0016_libgumbo max depth exceeded: (n=4   913200) 827480 Kb, Δ +0
memwatch: test_0016_libgumbo max depth exceeded: (n=5  1217600) 827480 Kb, Δ +0
memwatch: test_0016_libgumbo max depth exceeded: (n=6  1522000) 827480 Kb, Δ +0
memwatch: test_0016_libgumbo max depth exceeded: (n=7  1826400) 827480 Kb, Δ +0
memwatch: test_0016_libgumbo max depth exceeded: (n=8  2130800) 827480 Kb, Δ +0
memwatch: test_0016_libgumbo max depth exceeded: (n=9  2435200) 827480 Kb, Δ +0
memwatch: test_0016_libgumbo max depth exceeded: (n=10 2739600) 827480 Kb, Δ +0
memwatch: test_0016_libgumbo max depth exceeded: (n=11 3044000) 827480 Kb, Δ +0
memwatch: test_0016_libgumbo max depth exceeded: elapsed 9.656810s
memwatch: test_0016_libgumbo max depth exceeded: slope = 0.00000 (r^2 = NaN)
.

Finished in 11.662075s, 0.0857 runs/s, 0.1715 assertions/s.

1 runs, 2 assertions, 0 failures, 0 errors, 0 skips
Coverage report generated for Unit Tests to /root/nokogiri/coverage. 1292 / 2751 LOC (46.96%) covered.

Without it, I get

root@32cdd9ed4118:~/nokogiri# bundle exec rake test:memory_suite TESTOPTS=-n/MEMORY_SUITE.*max.depth/
/usr/local/bin/ruby -w -I"lib:test" /usr/local/lib/ruby/gems/3.3.0/gems/rake-13.1.0/lib/rake/rake_test_loader.rb "test/test_memory_usage.rb" -n/MEMORY_SUITE.*max.depth/
/root/nokogiri/test/helper.rb:46: version info:
---
warnings: []
nokogiri:
  version: 1.16.0
  cppflags:
  - "-I/root/nokogiri/ext/nokogiri"
  - "-I/root/nokogiri/ext/nokogiri/include"
  - "-I/root/nokogiri/ext/nokogiri/include/libxml2"
  ldflags: []
ruby:
  version: 3.3.0
  platform: aarch64-linux
  gem_platform: aarch64-linux
  description: ruby 3.3.0 (2023-12-25 revision 5124f9ac75) [aarch64-linux]
  engine: ruby
libxml:
  source: packaged
  precompiled: false
  patches:
  - 0001-Remove-script-macro-support.patch
  - 0002-Update-entities-to-remove-handling-of-ssi.patch
  - 0003-libxml2.la-is-in-top_builddir.patch
  - '0009-allow-wildcard-namespaces.patch'
  - 0010-update-config.guess-and-config.sub-for-libxml2.patch
  - 0011-rip-out-libxml2-s-libc_single_threaded-support.patch
  memory_management: ruby
  iconv_enabled: true
  compiled: 2.12.4
  loaded: 2.12.4
libxslt:
  source: packaged
  precompiled: false
  patches:
  - 0001-update-config.guess-and-config.sub-for-libxslt.patch
  datetime_enabled: true
  compiled: 1.1.39
  loaded: 1.1.39
other_libraries:
  libgumbo: 1.0.0-nokogiri
NOKOGIRI_TEST_GC_LEVEL: major
Run options: -n/MEMORY_SUITE.*max.depth/ --seed 15259

# Running:


memwatch: test_0016_libgumbo max depth exceeded: (n=1        0) 847256 Kb
memwatch: test_0016_libgumbo max depth exceeded: (n=2   317700) 857156 Kb, Δ +9900
memwatch: test_0016_libgumbo max depth exceeded: (n=3   635400) 867188 Kb, Δ +10032
memwatch: test_0016_libgumbo max depth exceeded: (n=4   953100) 877088 Kb, Δ +9900
memwatch: test_0016_libgumbo max depth exceeded: (n=5  1270800) 886988 Kb, Δ +9900
memwatch: test_0016_libgumbo max depth exceeded: (n=6  1588500) 896888 Kb, Δ +9900
memwatch: test_0016_libgumbo max depth exceeded: (n=7  1906200) 906920 Kb, Δ +10032
memwatch: test_0016_libgumbo max depth exceeded: (n=8  2223900) 916820 Kb, Δ +9900
memwatch: test_0016_libgumbo max depth exceeded: (n=9  2541600) 926720 Kb, Δ +9900
memwatch: test_0016_libgumbo max depth exceeded: (n=10 2859300) 936620 Kb, Δ +9900
memwatch: test_0016_libgumbo max depth exceeded: (n=11 3177000) 946520 Kb, Δ +9900
memwatch: test_0016_libgumbo max depth exceeded: elapsed 9.769324s
memwatch: test_0016_libgumbo max depth exceeded: slope = 32.00218 (r^2 = 1.000)
memwatch: test_0016_libgumbo max depth exceeded: best-fit slope 32.00217563739377 (r^2=0.9999984808465424) should be close to zero: retrying once

memwatch: test_0016_libgumbo max depth exceeded: (n=1        0) 946520 Kb
memwatch: test_0016_libgumbo max depth exceeded: (n=2   317700) 956552 Kb, Δ +10032
memwatch: test_0016_libgumbo max depth exceeded: (n=3   635400) 966584 Kb, Δ +10032
memwatch: test_0016_libgumbo max depth exceeded: (n=4   953100) 976484 Kb, Δ +9900
memwatch: test_0016_libgumbo max depth exceeded: (n=5  1270800) 986384 Kb, Δ +9900
memwatch: test_0016_libgumbo max depth exceeded: (n=6  1588500) 996284 Kb, Δ +9900
memwatch: test_0016_libgumbo max depth exceeded: (n=7  1906200) 1006316 Kb, Δ +10032
memwatch: test_0016_libgumbo max depth exceeded: (n=8  2223900) 1016216 Kb, Δ +9900
memwatch: test_0016_libgumbo max depth exceeded: (n=9  2541600) 1026116 Kb, Δ +9900
memwatch: test_0016_libgumbo max depth exceeded: (n=10 2859300) 1036016 Kb, Δ +9900
memwatch: test_0016_libgumbo max depth exceeded: (n=11 3177000) 1045916 Kb, Δ +9900
memwatch: test_0016_libgumbo max depth exceeded: elapsed 10.056210s
memwatch: test_0016_libgumbo max depth exceeded: slope = 32.02151 (r^2 = 1.000)
F

Finished in 21.830877s, 0.0458 runs/s, 0.1374 assertions/s.

  1) Failure:
MEMORY_SUITE#test_0016_libgumbo max depth exceeded [test/helper.rb:368]:
best-fit slope 32.02151463644948 (r^2=0.9999968048815574) should be close to zero

1 runs, 3 assertions, 1 failures, 0 errors, 0 skips
Coverage report generated for Unit Tests to /root/nokogiri/coverage. 1292 / 2751 LOC (46.96%) covered.
rake aborted!
Command failed with status (1): [ruby -w -I"lib:test" /usr/local/lib/ruby/gems/3.3.0/gems/rake-13.1.0/lib/rake/rake_test_loader.rb "test/test_memory_usage.rb" -n/MEMORY_SUITE.*max.depth/]
/root/nokogiri/rakelib/test.rake:95:in `ruby'
/usr/local/bin/bundle:25:in `load'
/usr/local/bin/bundle:25:in `<main>'
Tasks: TOP => test:memory_suite
(See full trace by running task with --trace)

If this looks good to you, I think we should commit this and then figure out what's causing

Assertion failed: (tag != GUMBO_TAG_UNKNOWN || name), function node_qualified_tagname_is, file parser.c, line 602.

when running clusterfuzz-testcase-minimized-parse_fuzzer-6659463909867520.

flavorjones · 2024-01-16T20:41:27Z

If this looks good to you

Yes! Ship it.

stevecheckoway · 2024-01-17T01:43:33Z

@stevecheckoway please consider using the CI infrastructure, we run those memory tests (both flavors of memory leak test) in CI.

so you could push the repro to this branch, see it fail in CI, then push the fix to the branch, and see it pass.

Oh good idea. I'll do that in the future.

Add test

2e26a72

stevecheckoway force-pushed the max-tree-depth-memory-leak branch from 4d1a082 to 2e26a72 Compare January 16, 2024 16:05

stevecheckoway marked this pull request as ready for review January 16, 2024 20:33

flavorjones approved these changes Jan 16, 2024

View reviewed changes

stevecheckoway merged commit 598f99f into sparklemotion:main Jan 17, 2024
126 checks passed

stevecheckoway deleted the max-tree-depth-memory-leak branch January 17, 2024 01:44

flavorjones added this to the v1.16.x patch releases milestone Jan 30, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Delay breaking out of the parse loop when max_tree_depth is hit #3100

Delay breaking out of the parse loop when max_tree_depth is hit #3100

stevecheckoway commented Jan 16, 2024

flavorjones commented Jan 16, 2024

flavorjones commented Jan 16, 2024 •

edited

stevecheckoway commented Jan 16, 2024

flavorjones commented Jan 16, 2024

stevecheckoway commented Jan 16, 2024

flavorjones commented Jan 16, 2024

stevecheckoway commented Jan 17, 2024

Delay breaking out of the parse loop when max_tree_depth is hit #3100

Delay breaking out of the parse loop when max_tree_depth is hit #3100

Conversation

stevecheckoway commented Jan 16, 2024

flavorjones commented Jan 16, 2024

flavorjones commented Jan 16, 2024 • edited

stevecheckoway commented Jan 16, 2024

flavorjones commented Jan 16, 2024

stevecheckoway commented Jan 16, 2024

flavorjones commented Jan 16, 2024

stevecheckoway commented Jan 17, 2024

flavorjones commented Jan 16, 2024 •

edited