Re: Re-visiting the DOM tree depth limit in layout

[Boris Zbarsky]

On 9/15/17 6:35 AM, Henri Sivonen wrote:

I'm assuming that anonymous frames count towards the
limit and a display: table-cell that doesn't belong to a table ends up
creating 5 frames. Correct?


Yes for both.  It creates a table, table-row-group, table-row, 
table-cell, and a block inside the table cell.



and the numbers probably end up being such that the HTML parser won't be able to
protect against nested table-cells hitting the frame construction
limit without setting the HTML parser limit to something unreasonably
low.


In fairness, we're trying to protect against incompetence here, not 
malice.  And the chance of someone actually accidentally producing that 
many nested table-cells is pretty low...


-Boris
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Ted Mielczarek]

On Thu, Sep 14, 2017, at 02:23 AM, Henri Sivonen wrote:
> Do I understand correctly that this is an address space issue only and
> Windows doesn't actually physically map the pages belonging to the
> stack until they are written to? That is, do I understand correctly
> that there's no obstacle for growing the maximum stack size on 64-bit
> Windows to the kind of numbers that Mac and Linux already have?
> 
> Is there a reason why a larger stack size is OK on 32-bit Linux but
> wouldn't be OK on 32-bit Windows? (Seems kinda weird that both
> defaults would just happen to be exactly perfect even when they are so
> different.)

One notable difference is that by default the 32-bit Linux kernel
provides 3GB of usable address space to programs and reserves 1GB for
the kernel[1], but the 32-bit Windows kernel only provides 2GB of usable
address space, reserving the other 2GB for the kernel[2]. It's possible
to increase that to 3GB by changing a boot parameter, but I doubt that's
a common occurrence. On both operating systems 32-bit applications
running on a 64-bit kernel get access to a full 4GB of address space.

-Ted

1.
https://www.quora.com/Why-do-32-bit-Linux-kernels-only-recognize-3GB-of-RAM
2.
https://msdn.microsoft.com/en-us/library/windows/desktop/aa366912(v=vs.85).aspx
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Henri Sivonen]

Also, it seems that Android doesn't use the Linux stack defaults.

Is the stack size under our control on Android?

On Fri, Sep 15, 2017 at 1:35 PM, Henri Sivonen  wrote:
> On Fri, Sep 15, 2017 at 12:26 PM, Henri Sivonen  wrote:
>> From black-box testing, it seems that some part of layout has gotten a
>> new << 200 depth limit for nested display:table-cell some time between
>> September 11 and September 14.
>>
>> To save myself the trouble of bisecting this, does anyone know which
>> patch did this and why?
>
> The above was based on running the wrong apk. Please disregard.
>
> However, investigating further showed that with display: table-cell
> the depth limit takes effect at a DOM depth that's about 1/5 of the
> stated limit. I'm assuming that anonymous frames count towards the
> limit and a display: table-cell that doesn't belong to a table ends up
> creating 5 frames. Correct?
>
> I guess this means that empirically finding the crash threshold for
> display: table-cell is more complicated than I thought and the numbers
> probably end up being such that the HTML parser won't be able to
> protect against nested table-cells hitting the frame construction
> limit without setting the HTML parser limit to something unreasonably
> low.
>
> Since we run unrelated sites in the same content process, we should
> avoid content process crashes more carefully than Chromium. Still, in
> some ways, crashing the content process indeed can be less confusing
> UX than parts of the page going silently missing. If we are going to
> keep *some* depth limit at which the frame constructor makes content
> not show up, it seems to me that it would be appropriate to make the
> frame constructor signal to the browser UI that it hit the limit so
> that the browser UI could show an infobar about parts of the page
> being omitted. I was investigating this very area and *still* I got
> confused by content disappearing and started to doubt my test case.
>
> --
> Henri Sivonen
> hsivo...@hsivonen.fi
> https://hsivonen.fi/



-- 
Henri Sivonen
hsivo...@hsivonen.fi
https://hsivonen.fi/
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Henri Sivonen]

On Fri, Sep 15, 2017 at 12:26 PM, Henri Sivonen  wrote:
> From black-box testing, it seems that some part of layout has gotten a
> new << 200 depth limit for nested display:table-cell some time between
> September 11 and September 14.
>
> To save myself the trouble of bisecting this, does anyone know which
> patch did this and why?

The above was based on running the wrong apk. Please disregard.

However, investigating further showed that with display: table-cell
the depth limit takes effect at a DOM depth that's about 1/5 of the
stated limit. I'm assuming that anonymous frames count towards the
limit and a display: table-cell that doesn't belong to a table ends up
creating 5 frames. Correct?

I guess this means that empirically finding the crash threshold for
display: table-cell is more complicated than I thought and the numbers
probably end up being such that the HTML parser won't be able to
protect against nested table-cells hitting the frame construction
limit without setting the HTML parser limit to something unreasonably
low.

Since we run unrelated sites in the same content process, we should
avoid content process crashes more carefully than Chromium. Still, in
some ways, crashing the content process indeed can be less confusing
UX than parts of the page going silently missing. If we are going to
keep *some* depth limit at which the frame constructor makes content
not show up, it seems to me that it would be appropriate to make the
frame constructor signal to the browser UI that it hit the limit so
that the browser UI could show an infobar about parts of the page
being omitted. I was investigating this very area and *still* I got
confused by content disappearing and started to doubt my test case.

-- 
Henri Sivonen
hsivo...@hsivonen.fi
https://hsivonen.fi/
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Henri Sivonen]

>From black-box testing, it seems that some part of layout has gotten a
new << 200 depth limit for nested display:table-cell some time between
September 11 and September 14.

To save myself the trouble of bisecting this, does anyone know which
patch did this and why?

-- 
Henri Sivonen
hsivo...@hsivonen.fi
https://hsivonen.fi/
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Henri Sivonen]

On Thu, Sep 14, 2017 at 12:38 AM, Mike Hommey  wrote:
> We could also move the main thread loop to a thread that we create with
> a stack size we want, and leave the original main thread just waiting
> for it (joining it).

What kind of pitfalls are associated with this approach? Could Windows
itself interact with the original main thread in ways that really
would need to be targeted at the newly-created thread?

-- 
Henri Sivonen
hsivo...@hsivonen.fi
https://hsivonen.fi/
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Henri Sivonen]

On Thu, Sep 14, 2017 at 9:23 AM, Henri Sivonen  wrote:
> Is there a reason why a larger stack size is OK on 32-bit Linux but
> wouldn't be OK on 32-bit Windows? (Seems kinda weird that both
> defaults would just happen to be exactly perfect even when they are so
> different.)

https://msdn.microsoft.com/en-us/library/windows/desktop/ms686774(v=vs.85).aspx
indicates that the default stack size for threads is 1 MB on Windows.
Even if the problem is that changing the main thread's stack size
increases the default for threads, too, it still seems that both
defaults on 32-bit Linux are already higher.

On 32-bit Ubuntu, ulimit -s prints 8192, so the default for the main
thread is 8 MB.
http://man7.org/linux/man-pages/man3/pthread_create.3.html says that
the default stack size for threads on 32-bit x86 is 2 MB.

If we can get away with 2 MB stack size for threads that don't ask for
a custom stack size on 32-bit Linux, I'd hope we don't need to treat 1
MB as a hard limit on 32-bit Windows.

Or is there something that makes our default thread stack smaller than
the manual page says on 32-bit Linux?

-- 
Henri Sivonen
hsivo...@hsivonen.fi
https://hsivonen.fi/
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Jan de Mooij]

On Thu, Sep 14, 2017 at 8:23 AM, Henri Sivonen  wrote:

> Do I understand correctly that this is an address space issue only and
> Windows doesn't actually physically map the pages belonging to the
> stack until they are written to? That is, do I understand correctly
> that there's no obstacle for growing the maximum stack size on 64-bit
> Windows to the kind of numbers that Mac and Linux already have?
>

Correct, Windows reserves stack pages but does not commit them until the
guard page is touched.


> Is there a reason why a larger stack size is OK on 32-bit Linux but
> wouldn't be OK on 32-bit Windows?
>

One difference is that Linux does not reserve stack pages (if the heap
grows big it can use unused stack pages).


> The failure mode of parts of email text silently going missing when
> reading HTML email on a webmail app is *really* bad, so I'd like to
> get it fixed in 57 instead of waiting for a task that touches many
> more places getting completed further in the future.
>

We could get this fixed, then spend a few minutes in VMMap to check whether
there are any long-lived beckground threads with excessive stack sizes that
we could easily fix. I don't have a strong opinion on this btw - I just
wanted to point out that it affects threads other than the main thread.

Jan
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Henri Sivonen]

On Wed, Sep 13, 2017 at 5:19 PM, Jan de Mooij  wrote:
> On Wed, Sep 13, 2017 at 10:44 AM, Henri Sivonen 
> wrote:
>>
>> 3) Increase the run-time stack size on Windows such that 1026-deep
>> display: table-cell doesn't overflow the stack.
>
>
> On Windows, threads that are created without an explicit stack size also use
> the executable's stack size. So increasing our stack size will also affect a
> bunch of other threads and we risk an increase in virtual memory OOMs on
> Win32.

Do I understand correctly that this is an address space issue only and
Windows doesn't actually physically map the pages belonging to the
stack until they are written to? That is, do I understand correctly
that there's no obstacle for growing the maximum stack size on 64-bit
Windows to the kind of numbers that Mac and Linux already have?

Is there a reason why a larger stack size is OK on 32-bit Linux but
wouldn't be OK on 32-bit Windows? (Seems kinda weird that both
defaults would just happen to be exactly perfect even when they are so
different.)

How about we increase the stack size on 64-bit Windows to accommodate
1026-deep display: table-cell as on Linux and Mac and increase the
stack size on 32-bit Windows by just 20% to be able to deal with
600-deep (513 plus a little to accommodate innerHTML) display: block?
(After all, one can already overflow the stack on 32-bit Windows with
fewer than 200 display: table-cells, so the status-quo precedent
doesn't require us to make the depth limit prevent overflow on 32-bit
Windows in the all-table-cell case.) It would be sad not to be able to
match Blink's HTML parser-level magic number on 32-bit Windows, but
Blink's magic number is too close to what the current stack size on
32-bit Windows happens to allow, so we'd need to grow the stack limit
at least a little bit.

Do Windows anti-virus programs inject stuff on the stack and steal
stack space compared to my clean (Windows 10's Windows Defender) test
system?

> I filed bug 1257522 [0] two years ago to pass an explicit stack size
> for a number of background threads we create in Gecko, it would be nice to
> fix that first.

The failure mode of parts of email text silently going missing when
reading HTML email on a webmail app is *really* bad, so I'd like to
get it fixed in 57 instead of waiting for a task that touches many
more places getting completed further in the future.

On Thu, Sep 14, 2017 at 12:38 AM, Mike Hommey  wrote:
> On Wed, Sep 13, 2017 at 10:03:55AM -0700, Eric Rahm wrote:
>> Jan is right, increasing the stack size for all threads would cause a very
>> large memory regression. Lets not do that ;) Selectively increasing might
>> make sense but we'd need to keep an eye on how large of an increase we're
>> expecting.
>
> We could also move the main thread loop to a thread that we create with
> a stack size we want, and leave the original main thread just waiting
> for it (joining it).

Does Quantum DOM already mean that the threads that the frame
constructor runs on are explicitly-spawned and not the system-spawned
main thread? Are Quantum DOM main threads created in such a way that
it would be easy to add an explicit stack size request?

-- 
Henri Sivonen
hsivo...@hsivonen.fi
https://hsivonen.fi/
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Mike Hommey]

On Wed, Sep 13, 2017 at 10:03:55AM -0700, Eric Rahm wrote:
> Jan is right, increasing the stack size for all threads would cause a very
> large memory regression. Lets not do that ;) Selectively increasing might
> make sense but we'd need to keep an eye on how large of an increase we're
> expecting.

We could also move the main thread loop to a thread that we create with
a stack size we want, and leave the original main thread just waiting
for it (joining it).

Mike
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Eric Rahm]

Jan is right, increasing the stack size for all threads would cause a very
large memory regression. Lets not do that ;) Selectively increasing might
make sense but we'd need to keep an eye on how large of an increase we're
expecting.

-e

On Wed, Sep 13, 2017 at 7:19 AM, Jan de Mooij  wrote:

> On Wed, Sep 13, 2017 at 10:44 AM, Henri Sivonen 
> wrote:
>
> > 3) Increase the run-time stack size on Windows such that 1026-deep
> > display: table-cell doesn't overflow the stack.
> >
>
> On Windows, threads that are created without an explicit stack size also
> use the executable's stack size. So increasing our stack size will also
> affect a bunch of other threads and we risk an increase in virtual memory
> OOMs on Win32. I filed bug 1257522 [0] two years ago to pass an explicit
> stack size for a number of background threads we create in Gecko, it would
> be nice to fix that first.
>
> Jan
>
> [0] https://bugzilla.mozilla.org/show_bug.cgi?id=1257522
> ___
> dev-platform mailing list
> dev-platform@lists.mozilla.org
> https://lists.mozilla.org/listinfo/dev-platform
>
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Jan de Mooij]

On Wed, Sep 13, 2017 at 10:44 AM, Henri Sivonen 
wrote:

> 3) Increase the run-time stack size on Windows such that 1026-deep
> display: table-cell doesn't overflow the stack.
>

On Windows, threads that are created without an explicit stack size also
use the executable's stack size. So increasing our stack size will also
affect a bunch of other threads and we risk an increase in virtual memory
OOMs on Win32. I filed bug 1257522 [0] two years ago to pass an explicit
stack size for a number of background threads we create in Gecko, it would
be nice to fix that first.

Jan

[0] https://bugzilla.mozilla.org/show_bug.cgi?id=1257522
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Henri Sivonen]

On Sep 13, 2017 15:52, "Ben Kelly"  wrote:



On Wed, Sep 13, 2017 at 4:44 AM, Henri Sivonen  wrote:

> I suggest we do the following:
>
>  1) Change the HTML parser behave more like Blink's: Raise the limit
> to 513 elements deep and append elements violating the limit to the
> 512th element on the stack instead of dropping them. (Since the
> off-the-main-thread parser can't read from the DOM, the previous
> sentence is defined in terms of the stack and not in terms of looking
> up a parent as in Blink.) I already have the code for this.
>
>  2) Change the frame constructor limit to 1026. Rationale: This is
> notably larger than 513 by being 513 times two and just within what
> can be handled in the table-cell worst case on Mac and Linux with the
> existing run-time stack size limits.
>
>  3) Increase the run-time stack size on Windows such that 1026-deep
> display: table-cell doesn't overflow the stack.
>

Is it possible to have automated tests to verify these tunings remain valid
as the tree is changed over time?  Or maybe we already have those?


My plan is to write a reftest that will fail if 1) frame construction stops
too soon or 2) it crashes due to stack overflow. AFAICT, it has to be
skip-if debug, because the stack frames are substantially larger in debug
builds.
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Ben Kelly]

On Wed, Sep 13, 2017 at 4:44 AM, Henri Sivonen  wrote:

> I suggest we do the following:
>
>  1) Change the HTML parser behave more like Blink's: Raise the limit
> to 513 elements deep and append elements violating the limit to the
> 512th element on the stack instead of dropping them. (Since the
> off-the-main-thread parser can't read from the DOM, the previous
> sentence is defined in terms of the stack and not in terms of looking
> up a parent as in Blink.) I already have the code for this.
>
>  2) Change the frame constructor limit to 1026. Rationale: This is
> notably larger than 513 by being 513 times two and just within what
> can be handled in the table-cell worst case on Mac and Linux with the
> existing run-time stack size limits.
>
>  3) Increase the run-time stack size on Windows such that 1026-deep
> display: table-cell doesn't overflow the stack.
>

Is it possible to have automated tests to verify these tunings remain valid
as the tree is changed over time?  Or maybe we already have those?

Thanks.

Ben
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Henri Sivonen]

On Tue, Sep 12, 2017 at 12:46 PM, Henri Sivonen  wrote:
> On Tue, Sep 12, 2017 at 12:35 PM, Henri Sivonen  wrote:
>> I'm rather unhappy about the prospect of having to examine another
>> browser's HTML parser beyond reading the spec in order to achieve
>> interop. :-(
>
> Fortunately, not too complicated:
> https://cs.chromium.org/chromium/src/third_party/WebKit/Source/core/html/parser/HTMLConstructionSite.cpp?sq=306

I did some additional testing with
https://hsivonen.com/test/moz/deeptree/dom/ . The content process of
64-bit Chrome 61 on Windows 10 crashes when the depth is a bit over
2530. This happens at the same depth with display: block and display:
table-cell. Curiously, despite its lower crash threshold for
parser-generated trees, Edge can do over 4000 but slows to a crawl. (I
didn't have the patience to watch what the exact crash number was, but
unattended it did crash eventually.)

So even though the HTML parser-enforced depth in Chrome is 513
elements, Chrome's call stack can tolerate much deeper trees even on
Windows. This suggests that our frame constructor limit should be
larger than 513. In particular, this would help when the parser hits
the 513 limit in innerHTML.

I suggest we do the following:

 1) Change the HTML parser behave more like Blink's: Raise the limit
to 513 elements deep and append elements violating the limit to the
512th element on the stack instead of dropping them. (Since the
off-the-main-thread parser can't read from the DOM, the previous
sentence is defined in terms of the stack and not in terms of looking
up a parent as in Blink.) I already have the code for this.

 2) Change the frame constructor limit to 1026. Rationale: This is
notably larger than 513 by being 513 times two and just within what
can be handled in the table-cell worst case on Mac and Linux with the
existing run-time stack size limits.

 3) Increase the run-time stack size on Windows such that 1026-deep
display: table-cell doesn't overflow the stack.

Thoughts?

-- 
Henri Sivonen
hsivo...@hsivonen.fi
https://hsivonen.fi/
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Henri Sivonen]

On Tue, Sep 12, 2017 at 12:35 PM, Henri Sivonen  wrote:
> I'm rather unhappy about the prospect of having to examine another
> browser's HTML parser beyond reading the spec in order to achieve
> interop. :-(

Fortunately, not too complicated:
https://cs.chromium.org/chromium/src/third_party/WebKit/Source/core/html/parser/HTMLConstructionSite.cpp?sq=306

-- 
Henri Sivonen
hsivo...@hsivonen.fi
https://hsivonen.fi/
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Henri Sivonen]

On Mon, Sep 11, 2017 at 5:37 PM, Geoffrey Sneddon  wrote:
> Chrome limits the DOM at 513 deep (where the root element is one
> deep), Safari likewise but doesn't paint anything. Edge appears to
> have no limit, so that TC simply hangs in an infinite loop (presumably
> it will eventually go OOM and crash, though I wonder if its
> performance isn't linear?).

Indeed, Chrome has a depth limit of 513 elements including the root
(with the depth extending to 514 when counting the text node leaves).

However, Blink does something more complex than Gecko in order to
enforce the limit. Consider the appearance of
https://hsivonen.com/test/moz/deeptree/font/4000.html in Firefox and
Chrome. The visual formatting of the page is as if Chrome didn't have
a depth limit.

I'm rather unhappy about the prospect of having to examine another
browser's HTML parser beyond reading the spec in order to achieve
interop. :-(

On Mon, Sep 11, 2017 at 5:24 PM, Boris Zbarsky  wrote:
> On 9/11/17 10:08 AM, Henri Sivonen wrote:
>>
>> What kind of style would have the maximum stack frame size? Is
>> display: table-cell enough to trigger the worst case?
>
>
> I suspect that display:table-cell is the worst case, but at only about 70%
> confidence.
>
> That said, I can't think of a worse case offhand.

Indeed, when the divs are styled as display: table-cell, the stack
overflows sooner than in the default styling case. So much so that our
current limit of 200 isn't enough to keep 32-bit Windows builds from
crashing with a stack overflow.

With the tests at https://hsivonen.com/test/moz/deeptree/ today, I see
the following:
Linux 64 (Ubuntu 16.04):
Plain div crashes between 3070 and 3080.
Div as table-cell crashes between 1080 and 1090.
The font crash threshold is somewhere above 4000.

Windows 64 (Windows 10):
Plain div crashes between 740 and 750.
Div as table-cell crashes between 240 and 250.
font crashes between 1910 and 1920

WoW (Windows 10):
Plain div crashes between 510 and 520.
Div as table-cell crashes somewhere below 200.
font crashes between 1480 and 1490

On Mon, Sep 11, 2017 at 6:39 PM, Jan de Mooij  wrote:
> On Mon, Sep 11, 2017 at 5:27 PM,  wrote:
>
>> On Monday, September 11, 2017 at 1:41:43 PM UTC+2, Henri Sivonen wrote:
>> > Can we ask Windows to give us more stack space?
>> > --
>> Don't know if it's possible to set it dynamically at runtime, but Visual
>> Studio supports setting it at compile time (in linker options).
>>
>
> Yes, we already set the stack size to 2 MB on Win64 [0].

Is there a reason not to increase the stack size on 32-bit Windows?

Is there a reason not to increase the stack size on 64-bit Windows to
the Linux/Mac ballpark?

-- 
Henri Sivonen
hsivo...@hsivonen.fi
https://hsivonen.fi/
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Bobby Holley]

Note also that, post-stylo, there are some very rough plans to investigate
rewriting the frame constructor in parallel Rust, which would likely move
us to a non-recursive model. But we probably won't start brainstorming the
details until the all-hands, have no idea if it will work, and even if it
does, it would be many months until we implemented and shipped it.

On Mon, Sep 11, 2017 at 5:49 AM, Boris Zbarsky  wrote:

> On 9/11/17 7:41 AM, Henri Sivonen wrote:
>
>> Frame construction runs recursive algorithms along the depth of the
>> DOM tree.
>>
>
> It's not just frame construction.  Recursive algorithms are all over the
> place in layout and DOM code.
>
> Frame construction may be a long pole here in terms of crashes due to a
> combination of several things:
>
> 1) Largish stack frames (not least because it stores a bunch of state in
> RAII things).
>
> 2) Frame construction itself having a depth check in ProcessChildren that
> prevents the frame tree from getting too deep (though it really only limits
> the depth the frame constructor itself is willing to go to).
>
> 3) Layout having a separate IsFrameTreeTooDeep check that makes it stop
> reflowing descendants at some point.
>
>
> There are three areas where changes could be made:
>>   1) We could re-calibrate the depth limit.
>>   2) The HTML parser could try harder to make the DOM rewrites keep
>> text nodes visible.
>>   3) The frame constructor could switch from a full-features recursive
>> algorithm to an iterative text node-only traversal near the depth
>> limit.
>>
>
> Option #3 won't really help with the third check I list above.  Maybe
> we'll construct frames for all the content, but we still won't lay it out,
> hence it won't be visible.
>
> I'd expect text node recovery (flattening out elements and just
>> considering text nodes) in the frame constructor to be a more robust
>> solution than trying to address the problem in the HTML parser. What's
>> the feasibility of such a frame constructor change?
>>
>
> Just doing that for initial construction is probably not too terrible.
>
> Making it behave correctly (read: not crash exploitably) in the face of
> dynamic mutations is pretty hard, because it would violate various layout
> and frame constructor invariants.  It might be more tractable than it used
> to be because maybe we can pretend like things are display:contents or
> something, but that means still doing stuff for all the ancestors of the
> textnodes, and in a non-recursive way.  It might be doable, though.
>
> My findings from testing with a very high limit so far are as follows:
>>
>
> What testcases were used?  The actual stack depth needed for frame
> construction and layout is highly styling-dependent, because it affects
> what codepaths are taken.  For example, I would expect something like this:
>
>   
>   
>
> To need less stack than something like this:
>
>   
>   div { display: table-cell }
>   
>
>   * Windows 64-bit: between 740 and 750.
>>   * 32-bit Firefox on 64-bit Windows 10: between 500 and 510.
>>   * 32-bit Firefox on 64-bit Windows 7: between 510 and 520.
>>
>
> Were those measurements done with PGO builds?  We need to make sure we do
> that, because PGO builds have quite different (and larger) stack frame
> sizes.
>
> As for other browsers:
>> I didn't find a depth limit for Chrome. (Tried up to 16000.)
>>
>
> Which version of Chrome?  Per comments in https://bugzilla.mozilla.org/s
> how_bug.cgi?id=485941 at least in their XML parser they do have a depth
> limit of about 5000, but that was apparently removed and then readded
> recently.  Of course they may have different behavior for XML and HTML.
>
> OK if I change the limit on a per-OS basis according to these numbers?
>>
>
> I'd really like to see testcases with: 1) Lots of nested inlines instead
> of lots of nested blocks and 2) my display:table-cell stress test to see
> what the numbers look like then.
>
> -Boris
>
> ___
> dev-platform mailing list
> dev-platform@lists.mozilla.org
> https://lists.mozilla.org/listinfo/dev-platform
>
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Jan de Mooij]

On Mon, Sep 11, 2017 at 5:27 PM,  wrote:

> On Monday, September 11, 2017 at 1:41:43 PM UTC+2, Henri Sivonen wrote:
> > Can we ask Windows to give us more stack space?
> > --
> Don't know if it's possible to set it dynamically at runtime, but Visual
> Studio supports setting it at compile time (in linker options).
>

Yes, we already set the stack size to 2 MB on Win64 [0]. In case it helps,
in bug 1257234 I added some code to detect the main thread stack size on
Windows (for JS recursion limits).

Jan

[0]
http://searchfox.org/mozilla-central/rev/00fa5dacedb925022f53d025121f1a919508e7ce/config/config.mk#422



> ___
> dev-platform mailing list
> dev-platform@lists.mozilla.org
> https://lists.mozilla.org/listinfo/dev-platform
>
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[khagaroth]

On Monday, September 11, 2017 at 1:41:43 PM UTC+2, Henri Sivonen wrote:
> Can we ask Windows to give us more stack space?
> -- 
Don't know if it's possible to set it dynamically at runtime, but Visual Studio 
supports setting it at compile time (in linker options).

___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Geoffrey Sneddon]

On Mon, Sep 11, 2017 at 3:08 PM, Henri Sivonen  wrote:
>> Per comments in
>> https://bugzilla.mozilla.org/show_bug.cgi?id=485941 at least in their XML
>> parser they do have a depth limit of about 5000, but that was apparently
>> removed and then readded recently.  Of course they may have different
>> behavior for XML and HTML.
>
> Maybe they have a limit that preserves text node visibility (as our
> HTML parser does when the workaround works as designed).
>
> I guess I should add some JS that computes the DOM depth.

I wrote a test for this years ago; I've thrown it up at
.

Chrome limits the DOM at 513 deep (where the root element is one
deep), Safari likewise but doesn't paint anything. Edge appears to
have no limit, so that TC simply hangs in an infinite loop (presumably
it will eventually go OOM and crash, though I wonder if its
performance isn't linear?).

/g
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Boris Zbarsky]

On 9/11/17 10:08 AM, Henri Sivonen wrote:

What kind of style would have the maximum stack frame size? Is
display: table-cell enough to trigger the worst case?


I suspect that display:table-cell is the worst case, but at only about 
70% confidence.


That said, I can't think of a worse case offhand.


Also, now that a stack overflow crashes the content process but not
the whole browser, a limit that's small enough never to overflow the
stack even with worst-case styling probably leads to worse user
experience than a higher limit that could crash the content process
with worst-case styling but that causes emails to render in the common
case.


That's possible, yes.


64-bit Ubuntu-shipped Chromium 60 and 64-bit Google-shipped Chrome 60
on Windows 10.


OK. I think the XML parser stack depth limit is back in 61...


I guess I should add some JS that computes the DOM depth.


That would certainly be useful data, if you are willing to do it.

-Boris
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Henri Sivonen]

On Mon, Sep 11, 2017 at 3:49 PM, Boris Zbarsky  wrote:
>> I'd expect text node recovery (flattening out elements and just
>> considering text nodes) in the frame constructor to be a more robust
>> solution than trying to address the problem in the HTML parser. What's
>> the feasibility of such a frame constructor change?
>
>
> Just doing that for initial construction is probably not too terrible.
>
> Making it behave correctly (read: not crash exploitably) in the face of
> dynamic mutations is pretty hard, because it would violate various layout
> and frame constructor invariants.

I see. :-(

>> My findings from testing with a very high limit so far are as follows:
>
>
> What testcases were used?  The actual stack depth needed for frame
> construction and layout is highly styling-dependent, because it affects what
> codepaths are taken.  For example, I would expect something like this:
>
>   
>   

It was s without any custom styling:
https://hsivonen.com/test/moz/deeptree/

> To need less stack than something like this:
>
>   
>   div { display: table-cell }
>   

What kind of style would have the maximum stack frame size? Is
display: table-cell enough to trigger the worst case?

Also, now that a stack overflow crashes the content process but not
the whole browser, a limit that's small enough never to overflow the
stack even with worst-case styling probably leads to worse user
experience than a higher limit that could crash the content process
with worst-case styling but that causes emails to render in the common
case.

>>   * Windows 64-bit: between 740 and 750.
>>   * 32-bit Firefox on 64-bit Windows 10: between 500 and 510.
>>   * 32-bit Firefox on 64-bit Windows 7: between 510 and 520.
>
>
> Were those measurements done with PGO builds?  We need to make sure we do
> that, because PGO builds have quite different (and larger) stack frame
> sizes.

For platforms that offer a PGO option on try, yes:
https://treeherder.mozilla.org/#/jobs?repo=try=43cfdbbb164b0638d21fca054d5facc894633deb=130001915
https://treeherder.mozilla.org/#/jobs?repo=try=40d92f2beae262ce502d9c57a0e5666157c584f9=130032494

>> As for other browsers:
>> I didn't find a depth limit for Chrome. (Tried up to 16000.)
>
>
> Which version of Chrome?

64-bit Ubuntu-shipped Chromium 60 and 64-bit Google-shipped Chrome 60
on Windows 10.

> Per comments in
> https://bugzilla.mozilla.org/show_bug.cgi?id=485941 at least in their XML
> parser they do have a depth limit of about 5000, but that was apparently
> removed and then readded recently.  Of course they may have different
> behavior for XML and HTML.

Maybe they have a limit that preserves text node visibility (as our
HTML parser does when the workaround works as designed).

I guess I should add some JS that computes the DOM depth.

-- 
Henri Sivonen
hsivo...@hsivonen.fi
https://hsivonen.fi/
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Boris Zbarsky]

On 9/11/17 7:41 AM, Henri Sivonen wrote:

Frame construction runs recursive algorithms along the depth of the
DOM tree.


It's not just frame construction.  Recursive algorithms are all over the 
place in layout and DOM code.


Frame construction may be a long pole here in terms of crashes due to a 
combination of several things:


1) Largish stack frames (not least because it stores a bunch of state in 
RAII things).


2) Frame construction itself having a depth check in ProcessChildren 
that prevents the frame tree from getting too deep (though it really 
only limits the depth the frame constructor itself is willing to go to).


3) Layout having a separate IsFrameTreeTooDeep check that makes it stop 
reflowing descendants at some point.




There are three areas where changes could be made:
  1) We could re-calibrate the depth limit.
  2) The HTML parser could try harder to make the DOM rewrites keep
text nodes visible.
  3) The frame constructor could switch from a full-features recursive
algorithm to an iterative text node-only traversal near the depth
limit.


Option #3 won't really help with the third check I list above.  Maybe 
we'll construct frames for all the content, but we still won't lay it 
out, hence it won't be visible.



I'd expect text node recovery (flattening out elements and just
considering text nodes) in the frame constructor to be a more robust
solution than trying to address the problem in the HTML parser. What's
the feasibility of such a frame constructor change?


Just doing that for initial construction is probably not too terrible.

Making it behave correctly (read: not crash exploitably) in the face of 
dynamic mutations is pretty hard, because it would violate various 
layout and frame constructor invariants.  It might be more tractable 
than it used to be because maybe we can pretend like things are 
display:contents or something, but that means still doing stuff for all 
the ancestors of the textnodes, and in a non-recursive way.  It might be 
doable, though.



My findings from testing with a very high limit so far are as follows:


What testcases were used?  The actual stack depth needed for frame 
construction and layout is highly styling-dependent, because it affects 
what codepaths are taken.  For example, I would expect something like this:


  
  

To need less stack than something like this:

  
  div { display: table-cell }
  


  * Windows 64-bit: between 740 and 750.
  * 32-bit Firefox on 64-bit Windows 10: between 500 and 510.
  * 32-bit Firefox on 64-bit Windows 7: between 510 and 520.


Were those measurements done with PGO builds?  We need to make sure we 
do that, because PGO builds have quite different (and larger) stack 
frame sizes.



As for other browsers:
I didn't find a depth limit for Chrome. (Tried up to 16000.)


Which version of Chrome?  Per comments in 
https://bugzilla.mozilla.org/show_bug.cgi?id=485941 at least in their 
XML parser they do have a depth limit of about 5000, but that was 
apparently removed and then readded recently.  Of course they may have 
different behavior for XML and HTML.



OK if I change the limit on a per-OS basis according to these numbers?


I'd really like to see testcases with: 1) Lots of nested inlines instead 
of lots of nested blocks and 2) my display:table-cell stress test to see 
what the numbers look like then.


-Boris
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: Re-visiting the DOM tree depth limit in layout

[Henri Sivonen]

On Mon, Sep 11, 2017 at 2:41 PM, Henri Sivonen  wrote:
>  * Firefox opt build on x86_64 Linux crashes when the DOM depth is
> between 3000 and 3100.
>  * Mac: between 3900 and 4000.

32-bit Linux: between 3900 and 4000

-- 
Henri Sivonen
hsivo...@hsivonen.fi
https://hsivonen.fi/
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform