Skip to content

/ servo

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

LayoutWorker stack overflow when running Dromaeo #6824

Closed
notriddle opened this issue Jul 29, 2015 · 4 comments
Closed

LayoutWorker stack overflow when running Dromaeo #6824

notriddle opened this issue Jul 29, 2015 · 4 comments
Labels
A-layout/uncategorized I-panic

Comments

@notriddle
Copy link
Contributor

@notriddle notriddle commented Jul 29, 2015

(This output from the test harness for #6759).

ERROR:net_traits::image::base: stb_image failed: stbi_load_from_memory failed
ERROR:net_traits::image::base: stb_image failed: stbi_load_from_memory failed
ERROR:net_traits::image::base: stb_image failed: stbi_load_from_memory failed
[dromaeo] Mesh Transform
[dromaeo] Mesh Transform
[dromaeo] Mesh Transform
[dromaeo] Mesh Transform
[dromaeo] Mesh Transform
[dromaeo] 3D Raytrace
[dromaeo] 3D Raytrace
[dromaeo] 3D Raytrace
[dromaeo] 3D Raytrace
[dromaeo] 3D Raytrace
[dromaeo] Convert pixels to canvas
[dromaeo] Convert pixels to canvas
[dromaeo] Convert pixels to canvas
[dromaeo] Convert pixels to canvas
[dromaeo] Convert pixels to canvas
[dromaeo] AES Encrypt
[dromaeo] AES Encrypt
[dromaeo] AES Encrypt
[dromaeo] AES Encrypt
[dromaeo] AES Encrypt
[dromaeo] AES Decrypt
[dromaeo] AES Decrypt
[dromaeo] AES Decrypt
[dromaeo] AES Decrypt
[dromaeo] AES Decrypt
[dromaeo] Array Construction, []
[dromaeo] Array Construction, []
[dromaeo] Array Construction, []
[dromaeo] Array Construction, []
[dromaeo] Array Construction, []
[dromaeo] Array Construction, new Array()
[dromaeo] Array Construction, new Array()
[dromaeo] Array Construction, new Array()
[dromaeo] Array Construction, new Array()
[dromaeo] Array Construction, new Array()
[dromaeo] Array Construction, unshift
[dromaeo] Array Construction, unshift
[dromaeo] Array Construction, unshift
[dromaeo] Array Construction, unshift
[dromaeo] Array Construction, unshift
[dromaeo] Array Construction, splice
[dromaeo] Array Construction, splice
[dromaeo] Array Construction, splice
[dromaeo] Array Construction, splice
[dromaeo] Array Construction, splice
[dromaeo] Array Deconstruction, shift
[dromaeo] Array Deconstruction, shift
[dromaeo] Array Deconstruction, shift
[dromaeo] Array Deconstruction, shift
[dromaeo] Array Deconstruction, shift
[dromaeo] Array Deconstruction, splice
[dromaeo] Array Deconstruction, splice
[dromaeo] Array Deconstruction, splice
[dromaeo] Array Deconstruction, splice
[dromaeo] Array Deconstruction, splice
[dromaeo] Array Construction, push
[dromaeo] Array Construction, push
[dromaeo] Array Construction, push
[dromaeo] Array Construction, push
[dromaeo] Array Construction, push
[dromaeo] Array Deconstruction, pop
[dromaeo] Array Deconstruction, pop
[dromaeo] Array Deconstruction, pop
[dromaeo] Array Deconstruction, pop
[dromaeo] Array Deconstruction, pop
[dromaeo] Convert String to Base 64
[dromaeo] Convert String to Base 64
[dromaeo] Convert String to Base 64
[dromaeo] Convert String to Base 64
[dromaeo] Convert String to Base 64
[dromaeo] Convert Base 64 to String
[dromaeo] Convert Base 64 to String
[dromaeo] Convert Base 64 to String
[dromaeo] Convert Base 64 to String
[dromaeo] Convert Base 64 to String
[dromaeo] Bitwise And
[dromaeo] Bitwise And
[dromaeo] Bitwise And
[dromaeo] Bitwise And
[dromaeo] Bitwise And
[dromaeo] Normal eval
[dromaeo] Normal eval
[dromaeo] Normal eval
[dromaeo] Normal eval
[dromaeo] Normal eval
[dromaeo] new Function
[dromaeo] new Function
[dromaeo] new Function
[dromaeo] new Function
[dromaeo] new Function
[dromaeo] 3bit bits in byte
[dromaeo] 3bit bits in byte
[dromaeo] 3bit bits in byte
[dromaeo] 3bit bits in byte
[dromaeo] 3bit bits in byte
[dromaeo] Bit in byte (2)
[dromaeo] Bit in byte (2)
[dromaeo] Bit in byte (2)
[dromaeo] Bit in byte (2)
[dromaeo] Bit in byte (2)
[dromaeo] Homo sapiens alu
[dromaeo] Homo sapiens alu
[dromaeo] Homo sapiens alu
[dromaeo] Homo sapiens alu
[dromaeo] Homo sapiens alu
[dromaeo] IUB ambiguity codes
[dromaeo] IUB ambiguity codes
[dromaeo] IUB ambiguity codes
[dromaeo] IUB ambiguity codes
[dromaeo] IUB ambiguity codes
[dromaeo] Homo sapiens frequency
[dromaeo] Homo sapiens frequency
[dromaeo] Homo sapiens frequency
[dromaeo] Homo sapiens frequency
[dromaeo] Homo sapiens frequency
[dromaeo] DNA Match (1)
[dromaeo] DNA Match (1)
[dromaeo] DNA Match (1)
[dromaeo] DNA Match (1)
[dromaeo] DNA Match (1)
[dromaeo] DNA Match (2)
[dromaeo] DNA Match (2)
[dromaeo] DNA Match (2)
[dromaeo] DNA Match (2)
[dromaeo] DNA Match (2)
[dromaeo] DNA Match (3)
[dromaeo] DNA Match (3)
[dromaeo] DNA Match (3)
[dromaeo] DNA Match (3)
[dromaeo] DNA Match (3)
[dromaeo] DNA Replace
[dromaeo] DNA Replace
[dromaeo] DNA Replace
[dromaeo] DNA Replace
[dromaeo] DNA Replace
[dromaeo] getAttribute
[dromaeo] getAttribute
[dromaeo] getAttribute
[dromaeo] getAttribute
[dromaeo] getAttribute
[dromaeo] element.property
[dromaeo] element.property
[dromaeo] element.property
[dromaeo] element.property
[dromaeo] element.property
[dromaeo] setAttribute
[dromaeo] setAttribute
[dromaeo] setAttribute
[dromaeo] setAttribute
[dromaeo] setAttribute
[dromaeo] element.property = value
[dromaeo] element.property = value
[dromaeo] element.property = value
[dromaeo] element.property = value
[dromaeo] element.property = value
[dromaeo] element.expando = value
[dromaeo] element.expando = value
[dromaeo] element.expando = value
[dromaeo] element.expando = value
[dromaeo] element.expando = value
[dromaeo] element.expando
[dromaeo] element.expando
[dromaeo] element.expando
[dromaeo] element.expando
[dromaeo] element.expando
[dromaeo] Prototype - addClassName
[dromaeo] Prototype - addClassName
[dromaeo] Prototype - addClassName
[dromaeo] Prototype - addClassName
[dromaeo] Prototype - addClassName
[dromaeo] Prototype - removeClassName
[dromaeo] Prototype - removeClassName
[dromaeo] Prototype - removeClassName
[dromaeo] Prototype - removeClassName
[dromaeo] Prototype - removeClassName
[dromaeo] Prototype - hasClassName
[dromaeo] Prototype - hasClassName
[dromaeo] Prototype - hasClassName
[dromaeo] Prototype - hasClassName
[dromaeo] Prototype - hasClassName
[dromaeo] Prototype - readAttribute
[dromaeo] Prototype - readAttribute
[dromaeo] Prototype - readAttribute
[dromaeo] Prototype - readAttribute
[dromaeo] Prototype - readAttribute
[dromaeo] Prototype - writeAttribute
[dromaeo] Prototype - writeAttribute
[dromaeo] Prototype - writeAttribute
[dromaeo] Prototype - writeAttribute
[dromaeo] Prototype - writeAttribute
[dromaeo] jQuery - addClass
[dromaeo] jQuery - addClass
[dromaeo] jQuery - addClass
[dromaeo] jQuery - addClass
[dromaeo] jQuery - addClass
[dromaeo] jQuery - removeClass
[dromaeo] jQuery - removeClass
[dromaeo] jQuery - removeClass
[dromaeo] jQuery - removeClass
[dromaeo] jQuery - removeClass
[dromaeo] jQuery - hasClass x10
[dromaeo] jQuery - hasClass x10
[dromaeo] jQuery - hasClass x10
[dromaeo] jQuery - hasClass x10
[dromaeo] jQuery - hasClass x10
[dromaeo] jQuery - attr(class) x100
[dromaeo] jQuery - attr(class) x100
[dromaeo] jQuery - attr(class) x100
[dromaeo] jQuery - attr(class) x100
[dromaeo] jQuery - attr(class) x100
[dromaeo] jQuery - attr(class,test)
[dromaeo] jQuery - attr(class,test)
[dromaeo] jQuery - attr(class,test)
[dromaeo] jQuery - attr(class,test)
[dromaeo] jQuery - attr(class,test)
[dromaeo] jQuery - removeAttribute
[dromaeo] jQuery - removeAttribute
[dromaeo] jQuery - removeAttribute
[dromaeo] jQuery - removeAttribute
[dromaeo] jQuery - removeAttribute
[dromaeo] Prototype - observe
[dromaeo] Prototype - observe
[dromaeo] Prototype - observe
[dromaeo] Prototype - observe
[dromaeo] Prototype - observe
[dromaeo] Prototype - fire
[dromaeo] Prototype - fire
[dromaeo] Prototype - fire
[dromaeo] Prototype - fire
[dromaeo] Prototype - fire
[dromaeo] Prototype - stopObserving
[dromaeo] Prototype - stopObserving
[dromaeo] Prototype - stopObserving
[dromaeo] Prototype - stopObserving
[dromaeo] Prototype - stopObserving
[dromaeo] jQuery - bind
[dromaeo] jQuery - bind
[dromaeo] jQuery - bind
[dromaeo] jQuery - bind
[dromaeo] jQuery - bind
[dromaeo] jQuery - trigger
[dromaeo] jQuery - trigger
[dromaeo] jQuery - trigger
[dromaeo] jQuery - trigger
[dromaeo] jQuery - trigger
[dromaeo] jQuery - unbind x10
[dromaeo] jQuery - unbind x10
[dromaeo] jQuery - unbind x10
[dromaeo] jQuery - unbind x10
[dromaeo] jQuery - unbind x10
[dromaeo] createElement
[dromaeo] createElement
[dromaeo] createElement
[dromaeo] createElement
[dromaeo] createElement
[dromaeo] createTextNode
[dromaeo] createTextNode
[dromaeo] createTextNode
[dromaeo] createTextNode
[dromaeo] createTextNode
[dromaeo] innerHTML
[dromaeo] innerHTML
[dromaeo] innerHTML
[dromaeo] innerHTML
[dromaeo] innerHTML
[dromaeo] cloneNode
[dromaeo] cloneNode
[dromaeo] cloneNode
[dromaeo] cloneNode
[dromaeo] cloneNode
[dromaeo] appendChild
[dromaeo] appendChild
[dromaeo] appendChild
[dromaeo] appendChild
[dromaeo] appendChild
[dromaeo] insertBefore
[dromaeo] insertBefore
[dromaeo] insertBefore
[dromaeo] insertBefore
[dromaeo] insertBefore
[dromaeo] Prototype - update()
[dromaeo] Prototype - update()
[dromaeo] Prototype - update()
[dromaeo] Prototype - update()
[dromaeo] Prototype - update()
[dromaeo] Prototype - before

thread 'LayoutWorker worker 1/3' has overflowed its stack

And this is the top of the stack trace, reported by gdb:

#2  0x0000555555dc77a3 in alloc..arc..Arc$LT$collections..vec..Vec$LT$style..properties..PropertyDeclaration$GT$$GT$::drop.36455::h8826625025fa18b5 ()
#3  0x0000555555dc776b in selectors..matching..DeclarationBlock$LT$collections..vec..Vec$LT$style..properties..PropertyDeclaration$GT$$GT$::drop.36452::h28b914465fda845e ()
#4  0x00005555561087d1 in layout::mem::forget<selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>> (t=...)
    at src/libcore/mem.rs:111
#5  0x0000555556108709 in layout::ptr::swap<selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>> (
    x=0x7fff027b6f00, y=0x7fff027b6f00) at src/libcore/ptr.rs:163
#6  0x000055555610863d in layout::slice::[T].SliceExt::swap (self=..., a=160, b=160) at src/libcore/slice.rs:385
#7  0x0000555556108562 in layout::slice::[T]::swap (self=..., a=160, b=160) at src/libcollections/slice.rs:423
#8  0x0000555556107dd6 in layout::quicksort_helper<selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>,fn(&selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>, &selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>) -> core::cmp::Ordering> (arr=..., left=0, right=160, compare=0x7fff38fd9368)
    at /home/michael/Experiments/Rust/servo/.cargo/registry/src/github.com-0a35038f75765ae4/quicksort-1.0.0/lib.rs:48
#9  0x00005555561083c6 in layout::quicksort_helper<selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>,fn(&selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>, &selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>) -> core::cmp::Ordering> (arr=..., left=0, right=161, compare=0x7fff38fd9368)
    at /home/michael/Experiments/Rust/servo/.cargo/registry/src/github.com-0a35038f75765ae4/quicksort-1.0.0/lib.rs:66
#10 0x00005555561083c6 in layout::quicksort_helper<selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>,fn(&selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>, &selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>) -> core::cmp::Ordering> (arr=..., left=0, right=162, compare=0x7fff38fd9368)
    at /home/michael/Experiments/Rust/servo/.cargo/registry/src/github.com-0a35038f75765ae4/quicksort-1.0.0/lib.rs:66
#11 0x00005555561083c6 in layout::quicksort_helper<selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>,fn(&selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>, &selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>) -> core::cmp::Ordering> (arr=..., left=0, right=163, compare=0x7fff38fd9368)
    at /home/michael/Experiments/Rust/servo/.cargo/registry/src/github.com-0a35038f75765ae4/quicksort-1.0.0/lib.rs:66
#12 0x00005555561083c6 in layout::quicksort_helper<selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>,fn(&selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>, &selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>) -> core::cmp::Ordering> (arr=..., left=0, right=164, compare=0x7fff38fd9368)
    at /home/michael/Experiments/Rust/servo/.cargo/registry/src/github.com-0a35038f75765ae4/quicksort-1.0.0/lib.rs:66
#13 0x00005555561083c6 in layout::quicksort_helper<selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>,fn(&selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>, &selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>) -> core::cmp::Ordering> (arr=..., left=0, right=165, compare=0x7fff38fd9368)
    at /home/michael/Experiments/Rust/servo/.cargo/registry/src/github.com-0a35038f75765ae4/quicksort-1.0.0/lib.rs:66
#14 0x00005555561083c6 in layout::quicksort_helper<selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>,fn(&selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>, &selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>) -> core::cmp::Ordering> (arr=..., left=0, right=166, compare=0x7fff38fd9368)
    at /home/michael/Experiments/Rust/servo/.cargo/registry/src/github.com-0a35038f75765ae4/quicksort-1.0.0/lib.rs:66
#15 0x00005555561083c6 in layout::quicksort_helper<selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>,fn(&selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>, &selectors::matching::DeclarationBlock<collections::vec::Vec<style::properties::PropertyDeclaration>>) -> core::cmp::Ordering> (arr=..., left=0, right=167, compare=0x7fff38fd9368)
@notriddle
Copy link
Contributor Author

@notriddle notriddle commented Jul 29, 2015

FYI, you'll want my modified Dromaeo, for automated mode and console output.
@jdm
Copy link
Member

@jdm jdm commented Jul 29, 2015

@pcwalton does the quicksort_helper look like it's working correctly to you? Each stack frame shows it decreasing the value for right by 1.
@notriddle
Copy link
Contributor Author

@notriddle notriddle commented Jul 29, 2015

After modifying rust-selectors to use an introsort implementation instead, it gets past that one (it fails on another one for an unrelated reason).
@notriddle notriddle mentioned this issue Jul 30, 2015
Merged
bors-servo pushed a commit to servo/rust-selectors that referenced this issue Jul 31, 2015
bors-servo
Auto merge of #43 - notriddle:introsort, r=SimonSapin
Loading status checks…
1527c2e 
Use an introspective sort

Rust-selectors currently uses a naive recursive quicksort. This algorithm performs O(n^2) comparisons when the list is already sorted, and, worse, creates O(n^2) stack frames, as seen in servo/servo#6824.

Let's be smarter.

<!-- Reviewable:start -->
[<img src="https://reviewable.io/review_button.png" height=40 alt="Review on Reviewable"/>](https://reviewable.io/reviews/servo/rust-selectors/43)
<!-- Reviewable:end -->
@notriddle
Copy link
Contributor Author

@notriddle notriddle commented Aug 1, 2015

Fixed by servo/rust-selectors#43
@notriddle notriddle closed this Aug 1, 2015
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
A-layout/uncategorized I-panic
Projects
None yet
Milestone
No milestone
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants
@jdm @notriddle
You can’t perform that action at this time.