Window Management Abstraction

[elinorbgr]

Here is a brain dump of a potential idea for an abstraction in Smithay to do window management.

General structure

• The abstraction defines a logical space into which windows are positioned
• It logically corresponds to a "workspace", so it is meant to be instanciated multiple times if the compositor wants multiple workspaces
• The base unit it works with is a "window", centered around a toplevel surface. That object represents the whole window, including its subsurfaces, its popups (and their subsurfaces), and its children toplevel surfaces.
• It should be able to handle XWayland windows transparently
• Maybe we can decide to drop wl_shell support at this point and not worry about it?

Geometry and shell interactions

• Each window has a few important properties computed from the client requests and the compositor decision:
  • A location in the logical space
  • A geometry, defined as a rectangle relative to the location, it defines the actual content of the base toplevel surface defining this window. It corresponds to xdg_surface.set_geometry, and is the value that should be considered to reorganize the windows on the screen and such.
  • A current bounding box, defining the extends to which contents for this window are drawn. This corresponds to the smallest rectangle including all the buffers of all subsurfaces, popups, and child toplevels.
  • A max bounding box, set by the compositor, defining the maximum rectangle to which popups and child toplevels can extend beyond the base toplevel surface. Smithay should handle popup positioning and shell interactions with child toplevels so that the current bounding box never exceeds the set max bounding box. The max bounding box could typically be the rectangular location of the current monitor, to prevent popups from going offscreen or to an other monitor
• The global abstraction can also have an optionally set "limit", defined as an union and intersection of rectangles much like the wl_region attributes, defining a global boundary around where there can be content at all. This boundary is take into account in addition to the windows-wise limits to position popups and handle shell interactions (move, resize) with windows.
  • This global limit has two modes, strict, in which no content is allowed to move outside of the defined boundary, and relaxed in which only the base location of a window must be inside the defined boundary, but the window itself may have parts of it that go outside.
• When a window is maximized, the compositor will provide to this abstraction the rectangle defining the maximized output
• Compositors are expected to handle fullscreen windows by directly mapping a window to an output, bypassing this abstraction, and possibly using an other abstraction provided by Smithay to specifically handle fullscreen windows.

Drawing

• For drawing, the abstraction should provide a method for, given a rectangle representing the logical boundary of the monitor that will be drawn, iterate over all wl_surface whose content intersect with it. This iteration needs to be done in correct z-order (including all windows and popups), and should skip surfaces that are completely masked by other opaque surfaces (as specified by the clients telling that their surfaces are opaque). The iteration should also give easy access to the relevant metadata to draw each surface (such as its location relative to the output rectangle).

[cmeissl]

Is a workspace limited to a single output or can it span multiple outputs? I would expect the latter. How should the popup constrain work in case a window is shown half/half on two outputs? I think it would be better to show the popup on a single output in most cases then, but there could be some uses cases with (near) zero bezel displays where it could be shown across both.

[cmeissl]

As an example, sway spawns a popup on the output that has a majority of the window on it.
For example, if the window is 60% on the left monitor and 40% on the right one, it will be displayed on the left one. I think it is a good compromise. Most compositors would probably want a similar behavior, but I don't know if we should enforce something like that on the users.

What happens in sway when the window is moved? Like changing the current layout or splitting the view again?

[elinorbgr]

I don't know about the "popup spanning two monitors" point, unless there is fractional scaling in the picture, that should basically "just work".

Probably actually, the easy way would be to have a callback or an argument (depending on the API) such that the "maximum bounding box" is not global to the window, but optionally set per-popup at creation. This way, the compositor could simply choose whether it wants the popup to be only on one monitor or the other, and the window management abstraction does not need to know about monitors. It just has a bunch of rectangles.

[PolyMeilex]

What happens in sway when the window is moved? Like changing the current layout or splitting the view again?

It is simply moved with the window, no additional repositioning is done

[cmeissl]

I don't know about the "popup spanning two monitors" point, unless there is fractional scaling in the picture, that should basically "just work".

Probably actually, the easy way would be to have a callback or an argument (depending on the API) such that the "maximum bounding box" is not global to the window, but optionally set per-popup at creation. This way, the compositor could simply choose whether it wants the popup to be only on one monitor or the other, and the window management abstraction does not need to know about monitors. It just has a bunch of rectangles.

Yeah, maybe i mixed up something. If the pointer follows the same rules when moving to the second output it should be good. I just have some memories from such issues, maybe on windows in the past?, where moving the cursor to the output would instantly dismiss the nested menu.

[cmeissl]

I don't know about the "popup spanning two monitors" point, unless there is fractional scaling in the picture, that should basically "just work".

Probably actually, the easy way would be to have a callback or an argument (depending on the API) such that the "maximum bounding box" is not global to the window, but optionally set per-popup at creation. This way, the compositor could simply choose whether it wants the popup to be only on one monitor or the other, and the window management abstraction does not need to know about monitors. It just has a bunch of rectangles.

Sounds good, the callback could probably be even used for repositioning if the window is moved and the popup is reactive.

[cmeissl]

Input handling, like finding the surface and point under the pointer location could be added much like currently implemented in anvil.

[cmeissl]

Are use cases other than classic desktop style window management out of scope? Like mapping windows into a 3d space?

[elinorbgr]

3d-space and such are not a goal for this abstraction, but if we can split it into a few parts (like maybe the window representation can be made standalone?) such that some of these parts could be used by a compositor to implement a nonstandard window management, I think this would be a good think to do.

[cmeissl]

Sounds good. So maybe to have the window abstraction without any location information and a desktop like cointainer representing a workspace holding the windows and their location?

[Drakulix]

What kind of functionalities would this abstraction then give you? This just sounds like a smarter Vec<Window>, is that what you are proposing? So maybe we should split the concepts of layout and "storage"?

[cmeissl]

No, not at all. I did not mean the whole window management abstraction. But the input and drawing abstraction (a window) is usable on it's own outside of a workspace and if it does not already define a location it could be used outside of the window management abstraction.

[Drakulix]

Maybe we can decide to drop wl_shell support at this point and not worry about it?

Given that wl_shell is officially deprecated, I do not see why an abstraction like this should support it anymore. If users want to implement wl_shell the wayland-code is still there (and should likely be for some time, but we might want to mark it as deprecated as well).

[cmeissl]

What about output tracking for sending enter/leave? Maybe it is out of scope for this abstraction, but we should outline how it is possible to do it when using this abstraction. Otherwise we could easily end up with a similar solution like currently implemented in anvil where the output map needs to iterate all windows. This could be built more reactive.

[Drakulix]

Alright, I have had some time to think about damage tracking and optimizations in general, so here is a brain-dump, because I think this actually has a lot to do with our current idea of window management.

For drawing, the abstraction should provide a method for, given a rectangle representing the logical boundary of the monitor that will be drawn, iterate over all wl_surface whose content intersect with it. This iteration needs to be done in correct z-order (including all windows and popups), and should skip surfaces that are completely masked by other opaque surfaces (as specified by the clients telling that their surfaces are opaque). The iteration should also give easy access to the relevant metadata to draw each surface (such as its location relative to the output rectangle).

Damage Tracking

As @vberger pointed out, we can skip surfaces, which is in itself an optimization. Another one would be to simply skip a page-flip, if nothing has changed, but damage tracking goes far deeper.

1. We can do damage tracking on surfaces. When a surface is drawn at the same position we can only update the parts indicated by the client. We currently do this when updating the texture of an shm buffer. But we do not do this when drawing the texture to an output frame, which also applies to dmabufs.
2. We can do damage tracking for other changes of the frame. We currently treat each frame as a complete blank canvas, redrawing everything (or rather anvil does it this way). But e.g. if only one surface is moved, we just need to re-draw the previous position (with all contents that were previously hidden by that surface) and draw the surface on the new position. Nothing else needs to be updated.

Smithay's Renderer and Swapchain apis are almost compatible with this and a compositor could almost implement this already.
The key thing missing is, that the buffers returned by a swapchain do not encode any information about them. We do not know if the buffer was already rendered to previously, how many frames ago that was, or if it is a new buffer.

What is a buffer age?

Consider a frontbuffer A and a backbuffer B. Lets say we start our rendering loop by rendering everything to the backbuffer B and swap it with A. Now A is our backbuffer, but we cannot really utilize the damage tracking potential, because A was never drawn to, it contains nothing of value, that we could reuse. We need to render the whole frame again.
But once A has become the frontbuffer again, we get B as a backbuffer again and B has valuable contents. But they are older then what is now displayed through A. We need to apply the damage from the previous frame and the damage from this frame to the buffer to get a correct frame.

Now consider triple buffering or more... And our swapchain does not really tell us how many buffers are used in the background, all of this is an implementation detail. It just gives us the next buffer, which ever that is. Through buffer age we can communicate how old a buffer is (meaning how many rendering steps ago it was last used).

Fixing this is a first necessary step for damage tracking. Afterwards we just need to keep track of all those changes.

Ok, but that still sounds like a lot of book-keeping.

It is and I have been struggling with designing an abstraction to keep track of all those changes for the user.
The first idea I had, was to have some kind of DamageTracker object, that you can use to mark rectangles as dirty. The damage tracker could merge overlapping or relatively small rectangles and give you a plan on what you need to re-render.

That is very flexible, but still leaves a lot of responsibility with the user. Any changes to the compositor state need to mark the next frame as damaged correctly or outdated buffer contents may be used. Ideally the user does not need to see any of this and cannot misuse it.

Representing damage as a difference in state

So what do we need to do this for the user? We need to precisely know, what has changed between rendering at one frame and the next.

And this is where our current ideas for window management come in. What @vberger has described in its first brain dump already keeps track of everything we need. We have a representation of an output (or workspace), which keeps track of windows (not surfaces, because we need a position to do this correctly) and keeps track of z-order.

If we can encode this into a struct that just keeps track of this state, make that easily clonable and cheaply storable, we can implement a diffing algorithm between two of these "rendering-states".

Roughtly such an algorithm would do something similar to:

• We first iterate through our windows front to back. If a new window has appeared, we mark its bounding box as damaged. If a window was removed, we mark its old bounding box as damaged. If a window is still present at the same position we translate the damage of all of its surfaces into workspace coordinates.
• We then optionally optimize our collected damage, by merging overlapping rectangles until we hit a certain threshold of maximum rectangles.
• For each rectangle in our list we then figure out, which surfaces are overlapping, drop the ones hidden and re-draw (the required parts of) the rest.

If the buffer age gets older, we just diff between more states and accumulate the damage.

I have not looked into wlroots scene-api, but I imagine this is roughly what they are doing. But I do not see any value in representing the window structure as a graph (instead of a z-ordered array), since smithay is very shell agnostic. For tiling compositors a graph obviously makes a lot of sense, because everything fits into containers and you may easily figure if one part of the tree did remain completely unchanged.

Our approach could be a little worse in performance for large surface counts, but I do not think it could be that bad for real world usecases.

Does that mean custom rendering steps are becoming impossible?

Not necessarily, no. First of all, I think it is easy enough to let the user insert arbitrary textures in the list of objects to compare against. E.g. for backgrounds or our FPS tracker. (Most of that stuff could be done with layer shell instead, but that might be not the easiest way.)

Are use cases other than classic desktop style window management out of scope? Like mapping windows into a 3d space?

3D-Rendering however will likely not be able to make much use of damage tracking, but I do not think that this is that bad. E.g. if you want a fancy rotating cube transition between workspaces, you can just render the transition manually without any damage tracking. Since the perspective of the windows likely shifts with every frame, there is not much to track anyway. And once the animation is over and you are back to more traditional layouts, you can use our damage tracking abstractions again. Maybe you need an extra call to mark the whole frame as damaged, but that should be about it.

Like this you can get fancy animations and still a lot of optimizations in between.

Also the user is of course not required to use any of this.

This means however that smithay will only use the render_texture_at function of our Renderer trait (and potentially a new render_texture_at_with_damage variant). render_texture with a matrix will not really work for any of this and is incompatible with simpler renderers (e.g. software rendering) anyway. So I propose, that we move render_texture into Gles2Renderer and remove it from the Renderer-api.

Moving stuff out of anvil into smithay

So what exactly needs to be done, after introducing buffer age in smithay?

I guess anvil will become a lot smaller.

What is currently anvil/src/drawing.rs would need to move completely into smithay, because we need a function to draw surface trees. And that function will be made damage aware and could become part of the public api. Again to make smithay composible and parts of it re-usable. anvil/src/render.rs is probably the function, that will be replaced by our diff-and-render algorithm.

Next anvil/src/window_map.rs will be replaced by the Window abstraction and output_map largely by the workspace abstraction. The user would then pair a surface, renderer, swapchain and a workspace and smithay would render it. If one of these change (with exception of the renderer), the whole thing resets any damage tracking.

To make this whole setup easier, I should probably build a generalized BufferedSurface abstraction, that will unify the different surfaces, once we only have a gbm-backend, x11-backend and wayland-backend, which all operate on dmabufs and the Swapchain api.
(Again this does not mean, we have to drop the winit-backend or any custom surfaces still using the EGLSurface api, but we will probably not support this for damage tracking. Technically this is possible, eglSwapBuffersWithDamage is a thing and we do not need to rule out this possibility just yet, but it is a lower priority.)

Then the whole abstraction just needs a function to get the next buffer + its age. Pair that with a workspace, which keeps track of previous rendering-states (releasing them, once it sees a buffer age, that is younger then any state it still has) and smithay does all the hard stuff for you.

Any feedback on this is welcome.

[DemiMarie]

Would it be possible to support multiple render targets per output? With wlroots, writing a rootless compositor requires creating a bunch of fake wlr_output objects, which is rather annoying. It would be nice if Smithay had native support for this.

[DemiMarie]

To clarify, by “output” I mean “what an application should see in wl_output”.

[Drakulix]

Would it be possible to support multiple render targets per output?

If we abstract a "workspace" in terms of "a space, that is contains windows at their logical positions", that does not cleanly map to an output anyway. I would expect there to be some kind of API to then attach a workspace to a surface and maybe some helpers to automatically create wl_outputs for these surfaces. But the later can be totally optional, there is no need for tight coupling here.

[i509VCB]

This has been done I believe?

We could probably mark this as resolved?