[dev-servo] Servo Cross-Compile to ARM
Dear Servo Developers! My name is Edit Balint, I'm a software developer at University of Szeged, Hungary. We have a research project regarding Servo and Rust. Our main goal is to cross-compile and run Servo on ARM Linux (not Android). We have several issues with the cross-compiling procedure. Is there any guide how to achieve this? Any help would be appreciated. Best regards: Edit Balint ___ dev-servo mailing list dev-servo@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-servo
Re: [dev-servo] Servo Cross-Compile to ARM
I suspect the main issue will just be getting a reliable cross compiler on ARM for the arm linux ABI. I think Luqman has been working on that, but IRC (#rust or #rust-internals) or the rust-dev mailing list may be a better place to ask. jack. On Thu, Feb 13, 2014 at 6:16 AM, Edit Balint wrote: > Dear Servo Developers! > > My name is Edit Balint, I'm a software developer at University of Szeged, > Hungary. > We have a research project regarding Servo and Rust. > Our main goal is to cross-compile and run Servo on ARM Linux (not Android). > We have several issues with the cross-compiling procedure. Is there any > guide how to achieve this? > > Any help would be appreciated. > > Best regards: > Edit Balint > ___ > dev-servo mailing list > dev-servo@lists.mozilla.org > https://lists.mozilla.org/listinfo/dev-servo ___ dev-servo mailing list dev-servo@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-servo
[dev-servo] Parallel hazards with absolutely positioned blocks
Hi everyone, Pradeep's excellent pull request [1] for absolute positioning raised some thorny issues relating to solving geometry constraints for absolutely positioned blocks in a parallel setting. The fundamental issue is that absolute positioning can depend not only on width and height of the containing block, but also the top/left/right position of the hypothetical box created by its static position. This is in conflict with our two-direction approach for computing widths and heights: widths are computed *top-down*, so that kids' widths depend on parents' widths, but heights are computed *bottom-up*, so that parents' heights depend on kids' heights. There are two basic approaches to dealing with absolutely-positioned frames: (1) parent the absolutely-positioned frame to its containing block, and keep track of a separate "hypothetical frame" (which is what Gecko seems to do, with `nsHTMLReflowState::CalculateHypotheticalBox()` and `nsFrameManager::GetPlaceholderFrameFor()`), or (2) keep track of the containing block separately from the parent and use the "hypothetical frame" as the real frame, which is WebKit's approach (see the comments in `RenderObject::container()` and `RenderBox::computePositionedLogicalWidth()`). The pull request #1681 takes approach #2. It deals with the parallel hazard by deferring height computation of absolutely positioned blocks until display list construction time (which is top-down). However, this has a problem in that the overflow for the containing block cannot be correctly calculated, because the height is not yet known. This will make it impossible for us to construct the display list only for frames in the visible region, since that depends on having correct overflow information. After some thought I've begun to think that approach #2 (WebKit's approach) is a dead-end in a parallel setting. The fundamental problem is that the height of an absolutely-positioned block cannot be determined without knowing the height of its containing block (if `top` and `bottom` are specified). Yet knowing the overflow region of *at least* the containing block depends on knowing the height of the absolutely-positioned blocks for which it is the containing block. I say "at least" because if we were to adopt WebKit's approach (putting the absolutely-positioned frame at its hypothetical static location) then potentially many more intervening blocks would have their overflow regions depend on their absolutely positioned descendants: ^height +--+ overflow | +---+ containing block |<+ | | ++-+ | | || overflow | | |v | | |+---+ | | || block | | direction| |+---+---+ | of| || overflow | traversal| |v | | |+---+ | | || block | | | |+---+---+ | | || overflow | | |v | | | ++| | +->+ absolutely positioned flow ++ | ++ That's a potentially unbounded amount of extra information that needs to travel in the opposite direction to the traversal. By contrast, approach #1 (Gecko's approach) avoids the unbounded amount of information flow in the opposite direction to the traversal. The height and overflow region only need to travel one step: from containing block to its immediate absolutely positioned flow child and back. This can be implemented by simply moving the computation of height and overflow of absolutely-positioned frames to the parent. This loses a small amount of parallelism during the assign-heights phase, but it should be small with fixed overhead. Width assignment becomes potentially trickier with absolute positioning. Recall that in Servo actual width computation is a top-down traversal. But because the width of an absolutely-positioned frame can depend on its hypothetical frame's static position, it is possible that an absolutely-positioned frame will not have its width ready by the time the traversal wants to compute it, because its hypothetical frame has not yet been reached. This can be remedied by simply (a) having containing blocks *not* enqueue their absolutely-positioned kids in the usual manner during the parallel top-down traversal and (b) having the *hypothetical* frame be the frame responsible for computing its associated absolutely positioned frame's width, and enqueuing its kids. Unfortunately, I don't know o
Re: [dev-servo] Parallel hazards with absolutely positioned blocks
On 2/13/14 4:48 PM, Patrick Walton wrote: The pull request #1681 takes approach #2. It deals with the parallel hazard by deferring height computation of absolutely positioned blocks until display list construction time (which is top-down). I sort of think that the right time to do absolutely positioned stuff in general is in a completely separate pass after the "main" layout is done. We've run into this in Gecko as well; that's what held up supporting relpos table-cell as an abs pos containing block. The way table (or flexbox, I suspect) layout works is that you do a pass, do some layout, then go back and fix up all your sizes. You need to either do the abs pos stuff _after_ the fixup or at least fix it up after the fixup, and the latter starts placing constraints on exactly how you can do your fixup. So the way I was envisioning layout with abspos stuff involved is that you go through without descending into abspos kids and do layout. Whenever you see an abspos kid during this process you add it to a list. Then you go through this list (this part should parallelize pretty nicely, btw, except for the overflow area updates on parents) and reflow them all, since now you know their containing block sizes, and you update overflow areas. Again, if there are abs pos kids you add to a list, etc. None of this really pins down anything about what you actually store as the containing block vs hypothetical box bits. The only requirement is that you be able to get to both pieces of information quickly when you go to reflow the abs-pos box. Anyway, for now I'm inclined to just not handle hypothetical boxes and just make up some values (e.g. zero) where the spec says to calculate their positions. This will almost certainly break the Web s/almost //, fwiw. ;) -Boris ___ dev-servo mailing list dev-servo@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-servo
Re: [dev-servo] Parallel hazards with absolutely positioned blocks
On Fri, Feb 14, 2014 at 11:42 AM, Boris Zbarsky wrote: > On 2/13/14 4:48 PM, Patrick Walton wrote: > >> The pull request #1681 takes approach #2. It deals with the parallel >> hazard by deferring height computation of absolutely positioned blocks >> until display list construction time (which is top-down). >> > > I sort of think that the right time to do absolutely positioned stuff in > general is in a completely separate pass after the "main" layout is done. > > We've run into this in Gecko as well; that's what held up supporting > relpos table-cell as an abs pos containing block. The way table (or > flexbox, I suspect) layout works is that you do a pass, do some layout, > then go back and fix up all your sizes. You need to either do the abs pos > stuff _after_ the fixup or at least fix it up after the fixup, and the > latter starts placing constraints on exactly how you can do your fixup. > > So the way I was envisioning layout with abspos stuff involved is that you > go through without descending into abspos kids and do layout. Whenever you > see an abspos kid during this process you add it to a list. > Yes, that's a nice way to think about it. There are two problems with it: 1) CSS Exclusions. But you need to do multipass layout for exclusions anyway, so that has to be solved with an exclusions-specific pass, so never mind. 2) Fragmentation. With something like overflow:fragments, absolute positioning can affect the number of fragments you generate, which can affect the size of the container of the fragments. Let me use this opportunity to remind people that fragmentation and writing-mode are stuff we should be building into Servo now-ish because they affect everything else. Rob -- Jtehsauts tshaei dS,o n" Wohfy Mdaon yhoaus eanuttehrotraiitny eovni le atrhtohu gthot sf oirng iyvoeu rs ihnesa.r"t sS?o Whhei csha iids teoa stiheer :p atroa lsyazye,d 'mYaonu,r "sGients uapr,e tfaokreg iyvoeunr, 'm aotr atnod sgaoy ,h o'mGee.t" uTph eann dt hwea lmka'n? gBoutt uIp waanndt wyeonut thoo mken.o w ___ dev-servo mailing list dev-servo@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-servo
Re: [dev-servo] Parallel hazards with absolutely positioned blocks
> By contrast, approach #1 (Gecko's approach) avoids the unbounded amount of > information flow in the opposite direction to the traversal. The height and > overflow region only need to travel one step: from containing block to its > immediate absolutely positioned flow child and back. This can be implemented > by simply moving the computation of height and overflow of > absolutely-positioned frames to the parent. This loses a small amount of > parallelism during the assign-heights phase, but it should be small with > fixed overhead. I think we talked about this a bit at the work week and had also settled on this idea. > This can be remedied by simply (a) having containing blocks > *not* enqueue their absolutely-positioned kids in the usual manner during > the parallel top-down traversal and (b) having the *hypothetical* frame be > the frame responsible for computing its associated absolutely positioned > frame's width, and enqueuing its kids. > > Unfortunately, I don't know off the top of my head the best way to enforce > that this logic is correct in the Rust type system. Tthe other issue is that there's no reason we can't mix the traversals. Once we've done assign_widths on a leaf node, for example, we should be able to enqueue assign_heights on the leaf node immediately. But we'll need to enforce that we don't enqueue the abspos child of a containing block until it's hypothetical flow is finished, not to mention that we may attempt to enqueue it *before* the hypothetical child has even gotten to assign widths, much less assign heights. I'm not sure how to enforce this in the type system, but we can certainly express the invariants in the enqueuing function somehow. > There is one minor issue of reference counting flows: there will need to be > a reference from the absolutely-positioned flow to its hypothetical flow (so > that the flow can find its static position if need be) and vice versa (so > that width can be assigned as above). At least one of these references must > be a strong reference. This is not too big of an issue because we need to > reference count flows for incremental reflow at some point anyway. I assume having the strong reference be the one from hypothetical up to the abspos flow child of the containing block is easiest since flow tree construction is bottom up. Incremental flow tree construction will have to be pretty careful not to leave a pointer dangling. We might blow away a subtree that contains the hypothetical flow but not the abspos kid. Perhaps the containing block has only weak pointers to its abspos kids, and they are really owned by the their hypothetical flow. I assume we can measure the overhead pretty easily on real pages similar to how we're discussing measuring float impact on parallelism. My rough guess is that the overhead will be proportional to the depth differential between the containing block and the hypothetical flow. Or perhaps proportional to the size of the subtree to the depth of the hypothetical flow. > I'm assuming you swapped #1 and #2 here. > positions. This will almost certainly break the Web, so I'm not suggesting > that we do this for the long run, but I think landing complicated work like > this is best done piecemeal. +1 as long as we do this work in the short term. jack. ___ dev-servo mailing list dev-servo@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-servo
Re: [dev-servo] Parallel hazards with absolutely positioned blocks
> Let me use this opportunity to remind people that fragmentation and > writing-mode are stuff we should be building into Servo now-ish because > they affect everything else. writing-mode is already on the list for next quarter, but fragments is slated for the quarter after that. I'll try and bump it up. jack. ___ dev-servo mailing list dev-servo@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-servo
Re: [dev-servo] Parallel hazards with absolutely positioned blocks
On 2/13/14 2:42 PM, Boris Zbarsky wrote:
Then you go through this list (this part should parallelize pretty
nicely, btw, except for the overflow area updates on parents) and reflow
them all, since now you know their containing block sizes, and you
update overflow areas. Again, if there are abs pos kids you add to a
list, etc.
I have a couple of concerns about this from a performance point of view.
1. This creates multiple sequential barriers, which can result in a
parallelism hazard. As an extreme case, consider:
div { position: absolute; }
...
This will effectively result in fully sequential layout because you have
to wait until layout to finish to start working on the new absolutely
positioned kids you found, and so on.
2. The overhead of updating parents' overflow areas over and over again.
In fact a page like above will result in O(n^2) updates of parents'
overflow areas where n is the number of nodes, unless I'm missing something.
Can we tweak the algorithm in some way to avoid these hazards?
Patrick
___
dev-servo mailing list
dev-servo@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-servo
Re: [dev-servo] Parallel hazards with absolutely positioned blocks
For the first concern, I realized that pages like that are going to be
sequential no matter what we do, of course, because of the way parallel tree
traversals work. So never mind there. The O(n^2) update of overflow areas still
concerns me though.
Patrick Walton wrote:
>On 2/13/14 2:42 PM, Boris Zbarsky wrote:
>> Then you go through this list (this part should parallelize pretty
>> nicely, btw, except for the overflow area updates on parents) and
>reflow
>> them all, since now you know their containing block sizes, and you
>> update overflow areas. Again, if there are abs pos kids you add to a
>> list, etc.
>
>I have a couple of concerns about this from a performance point of
>view.
>
>1. This creates multiple sequential barriers, which can result in a
>parallelism hazard. As an extreme case, consider:
>
> div { position: absolute; }
>
> ...
>
>This will effectively result in fully sequential layout because you
>have
>to wait until layout to finish to start working on the new absolutely
>positioned kids you found, and so on.
>
>2. The overhead of updating parents' overflow areas over and over
>again.
>In fact a page like above will result in O(n^2) updates of parents'
>overflow areas where n is the number of nodes, unless I'm missing
>something.
>
>Can we tweak the algorithm in some way to avoid these hazards?
>
>Patrick
>
>___
>dev-servo mailing list
>dev-servo@lists.mozilla.org
>https://lists.mozilla.org/listinfo/dev-servo
--
Sent from my Android phone with K-9 Mail. Please excuse my brevity.
___
dev-servo mailing list
dev-servo@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-servo
Re: [dev-servo] Parallel hazards with absolutely positioned blocks
Here's an idea for how to leverage the leaf-set-removal proposal to optimize
this algorithm:
1. When assigning widths for parents, don't enqueue absolutely positioned kids
to have their widths assigned.
2. Absolutely positioned kids of a node should not be counted as outstanding
children-to-be-reflowed for the purposes of height assignment. The effect of
this is that height may be computed for a node once all of its in-flow children
have had their heights computed; it need not wait on absolutely positioned
children.
3. After assigning heights for parents that have absolutely positioned kids,
don't store overflow for them (or their ancestors) right away, because their
overflow regions *do* depend on the overflow regions of their absolutely
positioned kids. Instead, for each such parent, store an atomic count X of
absolutely positioned kids inside it, and enqueue assign-*widths* for all of
the parent's absolutely positioned kids.
4. After assigning widths for a leaf, start assigning heights for it
immediately. (This is the leaf-set removal proposal.)
5. After assigning heights for an absolutely positioned frame, do *not*
decrement its parent's count of outstanding children-to-be-reflowed (as that
number should be zero). Instead decrement X (the atomic count of
absolutely-positioned kids) on the parent. If zero, then compute overflow for
the parent and all of its ancestors.
I believe this algorithm or something like it can achieve the goal of
performing layout for absolutely positioned frames after all of the frames it
could possibly depend on, without the subtle invariants of my first proposal.
It's essentially the same as bz's algorithm but without the explicit list;
rather it uses the parallel work queue as the list. It also avoids the O(n^2)
hazard by computing overflow for each frame exactly once.
How does this sound?
Patrick
Patrick Walton wrote:
>For the first concern, I realized that pages like that are going to be
>sequential no matter what we do, of course, because of the way parallel
>tree traversals work. So never mind there. The O(n^2) update of
>overflow areas still concerns me though.
>
>Patrick Walton wrote:
>>On 2/13/14 2:42 PM, Boris Zbarsky wrote:
>>> Then you go through this list (this part should parallelize pretty
>>> nicely, btw, except for the overflow area updates on parents) and
>>reflow
>>> them all, since now you know their containing block sizes, and you
>>> update overflow areas. Again, if there are abs pos kids you add to
>a
>>> list, etc.
>>
>>I have a couple of concerns about this from a performance point of
>>view.
>>
>>1. This creates multiple sequential barriers, which can result in a
>>parallelism hazard. As an extreme case, consider:
>>
>> div { position: absolute; }
>>
>> ...
>>
>>This will effectively result in fully sequential layout because you
>>have
>>to wait until layout to finish to start working on the new absolutely
>>positioned kids you found, and so on.
>>
>>2. The overhead of updating parents' overflow areas over and over
>>again.
>>In fact a page like above will result in O(n^2) updates of parents'
>>overflow areas where n is the number of nodes, unless I'm missing
>>something.
>>
>>Can we tweak the algorithm in some way to avoid these hazards?
>>
>>Patrick
>>
>>___
>>dev-servo mailing list
>>dev-servo@lists.mozilla.org
>>https://lists.mozilla.org/listinfo/dev-servo
>
>--
>Sent from my Android phone with K-9 Mail. Please excuse my brevity.
--
Sent from my Android phone with K-9 Mail. Please excuse my brevity.
___
dev-servo mailing list
dev-servo@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-servo
Re: [dev-servo] Parallel hazards with absolutely positioned blocks
On 2/13/14 5:56 PM, Robert O'Callahan wrote: 2) Fragmentation. With something like overflow:fragments, absolute positioning can affect the number of fragments you generate, which can affect the size of the container of the fragments. Ugh. I thought one of the points of absolute positioning was to not affect the layout of anything If that's not the case anymore, that's _really_ annoying. Let me use this opportunity to remind people that fragmentation and writing-mode are stuff we should be building into Servo now-ish because they affect everything else. Yes! -Boris ___ dev-servo mailing list dev-servo@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-servo
Re: [dev-servo] Parallel hazards with absolutely positioned blocks
On 2/13/14 6:45 PM, Patrick Walton wrote:
1. This creates multiple sequential barriers, which can result in a
parallelism hazard. As an extreme case, consider:
div { position: absolute; }
...
This will effectively result in fully sequential layout because you have
to wait until layout to finish to start working on the new absolutely
positioned kids you found, and so on.
Well, so...
In this testcase you can't really start laying out the child div until
you're done figuring out the size of the parent div (which then
determines the size of the containing block for the child), right? I
think that's a fundamental serialization issue in the spec for abspos
stuff, but willing to be proved wrong. The good news is that such deep
apspos nesting is a pretty rare case...
There are, I guess, special cases where you can know the size of the
parent before you've finished laying out its kids. By the same token,
there are cases, like tables, where you don't know it even after you've
finished the kids, because there's some nonlocal thing like row height
assignment waiting to happen.
You can try to deal with the latter by redoing the abspos layout if/when
the size changes; it just might be more complicated to do that.
2. The overhead of updating parents' overflow areas over and over again.
In fact a page like above will result in O(n^2) updates of parents'
overflow areas where n is the number of nodes, unless I'm missing
something.
I believe you're right.
Can we tweak the algorithm in some way to avoid these hazards?
I will think on it.
The fragmentation issue worries me more. :(
-Boris
___
dev-servo mailing list
dev-servo@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-servo
Re: [dev-servo] Parallel hazards with absolutely positioned blocks
On Fri, Feb 14, 2014 at 12:53 PM, Patrick Walton wrote: > For the first concern, I realized that pages like that are going to be > sequential no matter what we do, of course, because of the way parallel > tree traversals work. So never mind there. The O(n^2) update of overflow > areas still concerns me though. > In Gecko we have the OverflowChangedTracker to avoid this. I presume it can be parallelized. Rob -- Jtehsauts tshaei dS,o n" Wohfy Mdaon yhoaus eanuttehrotraiitny eovni le atrhtohu gthot sf oirng iyvoeu rs ihnesa.r"t sS?o Whhei csha iids teoa stiheer :p atroa lsyazye,d 'mYaonu,r "sGients uapr,e tfaokreg iyvoeunr, 'm aotr atnod sgaoy ,h o'mGee.t" uTph eann dt hwea lmka'n? gBoutt uIp waanndt wyeonut thoo mken.o w ___ dev-servo mailing list dev-servo@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-servo
Re: [dev-servo] Parallel hazards with absolutely positioned blocks
On Fri, Feb 14, 2014 at 1:43 PM, Boris Zbarsky wrote: > On 2/13/14 5:56 PM, Robert O'Callahan wrote: > >> 2) Fragmentation. With something like overflow:fragments, absolute >> positioning can affect the number of fragments you generate, which can >> affect the size of the container of the fragments. >> > > Ugh. I thought one of the points of absolute positioning was to not > affect the layout of anything If that's not the case anymore, that's > _really_ annoying. Well, I'm not 100% sure. I wonder what David thinks. Rob -- Jtehsauts tshaei dS,o n" Wohfy Mdaon yhoaus eanuttehrotraiitny eovni le atrhtohu gthot sf oirng iyvoeu rs ihnesa.r"t sS?o Whhei csha iids teoa stiheer :p atroa lsyazye,d 'mYaonu,r "sGients uapr,e tfaokreg iyvoeunr, 'm aotr atnod sgaoy ,h o'mGee.t" uTph eann dt hwea lmka'n? gBoutt uIp waanndt wyeonut thoo mken.o w ___ dev-servo mailing list dev-servo@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-servo
