Created attachment 286030 [details] [review]
Replace MetaStackWindow with a 64-bit "stack ID"

Putting X windows and pointers to MetaWindows into a union had a number of
problems:

 - It caused awkward initialization and conditionalization
 - There was no way to refer to Wayland windows (represented by
   MetaWindow *) in the past, which is necessary for the MetaStackTracker
   algorithms
 - We never even cleaned up old MetaStackWindow so there could be
   records in MetaStackWindow pointing to freed MetaWindow.

Replace MetaStackWindow with a 64-bit "stack ID" which is:

 - The XID for X Windows
 - a "window stamp" for Wayland windows - window stamps are assigned
   for all MetaWindow and are unique across the life of the process.

Created attachment 286031 [details] [review]
MetaStackTracker: eliminate the resynchronization process

The step where we requery the stacking order from the server than combine
it in an arbitrary fashion with Wayland windows can be eliminated by observing
that we are the final authority for Wayland window stacking - so if we
apply each X event that we receive from the X server to our stack in a
way that leaves the X windows ordered in the same way as on the server,
and apply events that we have stored locally in a way that doesn't affect
the ordering of X windows, than we have a fully correct ordering of windows.

Ordering this in the order of first applying the X event and then applying the
local portion also means that as long as we had an up-to-date view of the X
stack the composite operation will be identical to what was requested.

Created attachment 286032 [details] [review]
Move manipulation of the X stack to MetaStackTracker

Since MetaStackTracker is the code that knows about the current X stacking order
and the relationship between X windows and Wayland windows, it's cleaner to
encapsulate stack manipulation in MetaStackTracker rather than have the calling
code make the X calls and only call into MetaStackTracker to inform it about
the changes.

Created attachment 286033 [details] [review]
Remove cache of last stacking order in stack.c

stack.c kept it's own record of the last stacking it requested, so that
restacking could be done with minimal moves, but we already have a better
view of the stacking order with the stack tracker, so use that instead.

This allows eliminating the special case for the first restack.

Created attachment 286034 [details] [review]
stack.c: remove obsolete handling of override-redirect windows

There was still code in stack.c to handle skipping override-redirect windows,
but since quite a while ago, meta_stack_add() is not called for OR windows
since they are outside our stacking control. Add an assertion and remove
unnecessary code.

Created attachment 286035 [details] [review]
Move logic for syncing the stack to the X server into MetaStackTracker

stack.c:sync_stack_to_xserver had both code for assembling the desired stack, and
code for enforcing the desired stack on the actual stack of X and Wayland windows;
the latter part is properly the domain of stack-tracker.c; moving the code to
apply the stack there both simplifies it and keeps stack.c more manageable.

Created attachment 286036 [details] [review]
MetaStackTracker: make functions used only internally static

Now that all actual stack shuffle is handled inside stack-tracker.c, we can make
meta_stack_tracker_record_[raise_above/lower_below] internal to that file and
remove the unused meta_stack_tracker_record_lower().

Created attachment 286037 [details] [review]
MetaStackTracker: optimize out unnecessary X restacking

We have a quite accurate view of the X stack, so there's no good reason to ask
the X server to do restacking that has no effect. (Restackings that have no
effect on either X windows or Wayland windows were generally optimized out in
the synchronization code, but in other cases like moving an X window that is
only beneath Wayland windows to the top of the stack we would make such
requests.)

Removing such requests:
 - Is a small efficiency win in itself
 - Allows us to immediately go ahead and apply Wayland changes to the verified stack
 - Prevents queued Wayland changes piling up waiting for an X event that will never
   be received, since the X server will not send confirmation of no-op restacks.

There's an unlikely corner case here that's bugging me a bit. In some cases, we can't avoid making a no-op X call - for example, if we have:

 undecorated window B
 undecorated window A

and try to lower window B to the bottom, but window A vanishes before the X server gets our request. In this case, we'll queue a prediction for that X move, and that will just stick around until something else happens with the X stack.

Since the X prediction is hanging around, any subsequent operations on Wayland windows (theoretically the user keeps on using their desktop for days and never touches another X app) get queued up behind the X prediction.

The fix is pretty simple - once we finish the restack process, if we have queued X requests, force a property change on the timestamp_pinging_window and when we receive the PropertyNotify, call out to MetaStackTracker to check for stale predictions.

But is it worth even those 10-20 lines of code? I haven't decided yet.

Review of attachment 286030 [details] [review]:

Small nit. Otherwise looks good, and smart idea :)

::: src/core/window.c
@@ +74,3 @@
+// Each window has a "stamp" which is a non-recycled 64-bit ID. They
+// start after the end of the XID space so that, for stacking
+// we can keep a guint64 that represents one or the other

Use C-style comments /* */ here.

Can you add this to the commit message about why stamps and XIDs will never collide?

You might also want to point out here that XIDs are guaranteed to only be 28 bits wide, as per spec?

Review of attachment 286031 [details] [review]:

OK.

Review of attachment 286032 [details] [review]:

Yeah, I like this.

Review of attachment 286033 [details] [review]:

OK.

Review of attachment 286034 [details] [review]:

::: src/core/stack.c
@@ -1215,3 @@
 
-  /* All X windows should be in some stacking order */
-  if (x11_stacked->len != stack->xwindows->len - n_override_redirect)

You should probably keep this warning, just remove the n_override_redirect.

Review of attachment 286035 [details] [review]:

I'm not going to review this one in-depth because it's particularly weedy. I'll just trust that you got it right.

Review of attachment 286036 [details] [review]:

Nice.

Review of attachment 286037 [details] [review]:

::: src/core/stack-tracker.c
@@ +539,3 @@
    * unverified X operations...
    */
+  if (op->any.serial == 0 &&

Oh, you sneak :)

I'm not sure I like applying these stack ops, since I'm not sure they can't affect Wayland windows; I'd rather fizzle it out entirely if we never made any request to X server:

    /* We use this bizarre combination of an X11 window with a serial
     * of 0 to mark a "no-op" request to make the code below easier
     * to read. Don't do anything in that case. */
    if (META_STACK_ID_IS_X11 (op->any.window) && op->any.serial == 0)
      return;

(Though I'm not sure -- is 0 a valid serial in the case of wraparound?)

(In reply to comment #17)
> Review of attachment 286037 [details] [review]:
> 
> ::: src/core/stack-tracker.c
> @@ +539,3 @@
>     * unverified X operations...
>     */
> +  if (op->any.serial == 0 &&
> 
> Oh, you sneak :)

I thought about splitting this out, but it doesn't really make a lot of sense without the rest of the patch. The idea is that if you have a stack op that has *no* X component to it, and no queued operations, then we know that we can just go ahead and apply it to the verified stack - we'd unconditionally apply it the next time we received an event from the X server anyways.

Previously, even though op->any.serial == 0 already corresponded to "no X action performed", it was *also* possible to check it as !META_STACK_ID_IS_X11(op->any.window) because we were doing X operations on all stack operations on X windows, whether they needed it or not.

> I'm not sure I like applying these stack ops, since I'm not sure they can't
> affect Wayland windows; I'd rather fizzle it out entirely if we never made any
> request to X server:
> 
>     /* We use this bizarre combination of an X11 window with a serial
>      * of 0 to mark a "no-op" request to make the code below easier
>      * to read. Don't do anything in that case. */

Previously we could have:

 window=wayland_window, sibling=x_window, serial==0

as an operation with no X compenent, this just adds more possibilities, such as window=x_window, sibling=wayland_window. This doesn't seem bizarre to me, but maybe "If this is a wayland operation" can be clarified - to "if the stacking operation doesn't involve reordering X windows"

>     if (META_STACK_ID_IS_X11 (op->any.window) && op->any.serial == 0)
>       return;

Fizzling it out wouldn't work - this is not a no-op request, it's a request with no X component, e.g. if I have
 
  wayland_window
  x_window_1
  x_window_2

Raising x_window_1 above wayland_window. 
 
> (Though I'm not sure -- is 0 a valid serial in the case of wraparound?)

There's definitely not good handling of serial wrap-around here. Wraparound is a bit screwy, if the last serial is 0xFFFFFFFF, then XNextRequest() will return 0, but then xcb internally does a no-op request to hide the serial==0xFFFFFFFF request, so the application request actually has a serial of 1. I don't know if the old libX11 code did that too or not.

If we wanted to make Mutter wrap-safe, then I'd probably do what XCB does internally and extend serials to 64-bits - have get_next_serial(), get_event_serial(event) wrappers, rather than trying to fight it piece-meal. If Mutter does 10 X requests per drawing frame, then it's about 60 days of continuous drawing to wrap around.

The commit message sounds like you're simply fizzling out no-op requests where the X server stacking order isn't changing, though after a re-read of your comment, your wording is correct. It's misleading to people who have no idea what's going on, like me :)

Added:

 Since such operations may still have an effect on the relative stacking of X
 and Wayland windows, we need to continue applying them to the local stack.

to the commit message and updated the comment to:

  /* If this operation doesn't involve restacking X windows then it's                                                                       
   * implicitly verified. We can apply it immediately unless there                                                                          
   * are outstanding X restacks that haven't yet been confirmed.                                                                            
   */

I decided against fixing the corner case I pointed out - it bothers me to
leave something only 99.9% correct that I could make 100% correct, but I
can't justify making the stack-tracker code more complex to fix something
that's so unlikely to make a difference.

Attachment 286030 [details] pushed as 73573a8 - Replace MetaStackWindow with a 64-bit "stack ID"
Attachment 286031 [details] pushed as cb66cf6 - MetaStackTracker: eliminate the resynchronization process
Attachment 286032 [details] pushed as 3457366 - Move manipulation of the X stack to MetaStackTracker
Attachment 286033 [details] pushed as 9401196 - Remove cache of last stacking order in stack.c
Attachment 286034 [details] pushed as 301acac - stack.c: remove obsolete handling of override-redirect windows
Attachment 286035 [details] pushed as 04bc846 - Move logic for syncing the stack to the X server into MetaStackTracker
Attachment 286036 [details] pushed as 87779ed - MetaStackTracker: make functions used only internally static
Attachment 286037 [details] pushed as f163a15 - MetaStackTracker: optimize out unnecessary X restacking