[Spice-devel] [PATCH] RFC: Document display channel drawable trees, etc

Jonathon Jongsma jjongsma at redhat.com
Thu Jan 26 21:12:52 UTC 2017


On Thu, 2017-01-26 at 04:18 -0500, Frediano Ziglio wrote:
> > 
> > ---
> > I started looking into a bug related to surfaces and drawing, but
> > after a
> > little initial investigation, I realized that I didn't really
> > understand any
> > of
> > the code in this part of spice server. I discussed it a little bit
> > with
> > several
> > others who also didn't have a good understanding of this part of
> > the code. So
> > I
> > decided it needed to be documented so that we can understand it and
> > work on
> > it
> > effectively. I've spent several long days trying to understand the
> > details
> > and
> > trying to document them as well as I can. There is a lot of
> > confusing
> > terminology, and there are things I still don't fully understand,
> > but I
> > wanted
> > to send this out to get feedback from others. Is it helpful? Do you
> > see any
> > cases where I misinterpreted things? Can anybody solve any pieces
> > of the
> > puzzle
> > that I didn't quite figure out? etc. etc.
> > 
> > I know it's rather dense and will probably require others to spend
> > some
> > serious
> > time understanding the code, but I'd love to get some feedback on
> > it.
> > 
> 
> Take some time to find this post, so before get really buried on the
> ML...

Thanks for taking the time to review. Would love to hear from others as
well.

> 
> Some part are quite good and should be split and merged, other,
> particularly exclude_region have too much questions to solve.

Yeah, not a bad idea. Some discussion below.

> 
> >  server/display-channel-private.h |   5 +-
> >  server/display-channel.c         | 256
> >  +++++++++++++++++++++++++++++++++++++++
> >  server/display-channel.h         |  10 +-
> >  server/tree.c                    |  12 +-
> >  server/tree.h                    |   6 +
> >  5 files changed, 285 insertions(+), 4 deletions(-)
> > 
> > diff --git a/server/display-channel-private.h
> > b/server/display-channel-private.h
> > index 6e299b9..dc4d605 100644
> > --- a/server/display-channel-private.h
> > +++ b/server/display-channel-private.h
> > @@ -32,7 +32,10 @@ struct DisplayChannelPrivate
> >      int enable_jpeg;
> >      int enable_zlib_glz_wrap;
> >  
> > -    Ring current_list; /* Drawable */
> > +    /* A ring of pending drawables for this DisplayChannel,
> > regardless of which
> > +     * surface they're associated with. This list is mainly used
> > to flush older
> > +     * drawables when we need to make room for new drawables. */
> > +    Ring current_list;
> 
> is this list containing ALL drawables allocated ?
> Could be renamed to drawable_list ?

Not exactly, the list of all allocated drawables is
DisplayChannelPrivate::drawables. This is a list of all drawables that
are pending for any surface associated with this DisplayChannel. In
essence, it's roughly equivalent to the union of all
DisplayChannelPrivate::surfaces[i].current_list rings. But the
drawables are ordered by age so that if we want to find the oldest
drawable in the queue (regardless of which surface it's associated
with), we can just get the tail of this ring (see free_one_drawable()).
So as far as I can tell, it's just a convenience ring to avoid
iterating through all of the surfaces to find the oldest drawable.

> 
> Wondering what these "current" are...

As far as I understand, it's basically all of the QXL commands that
have been received from the device, but have not actually been drawn
yet. It's not a great name though...

> 
> >      uint32_t current_size;
> >  
> >      uint32_t drawable_count;
> > diff --git a/server/display-channel.c b/server/display-channel.c
> > index 6069883..83e76c1 100644
> > --- a/server/display-channel.c
> > +++ b/server/display-channel.c
> > @@ -393,6 +393,8 @@ static void current_add_drawable(DisplayChannel
> > *display,
> >      drawable->refs++;
> >  }
> >  
> > +/* Unrefs the drawable and removes it from any rings that it's in,
> > as well as
> > + * removing any associated shadow item */
> >  static void current_remove_drawable(DisplayChannel *display,
> > Drawable *item)
> 
> display_channel_remove_drawable ?
> display_channel_unlink_drawable ?

Definitely could use a better name. Not sure what the best would be. I
would personally like to refactor a lot of this code eventually, but
wanted to document it without any code changes first.

> 
> >  {
> >      /* todo: move all to unref? */
> > @@ -422,6 +424,7 @@ static void drawable_remove_from_pipes(Drawable
> > *drawable)
> >      }
> >  }
> >  
> > +/* This function should never be called for Shadow TreeItems */
> >  static void current_remove(DisplayChannel *display, TreeItem
> > *item)
> >  {
> >      TreeItem *now = item;
> > @@ -439,22 +442,38 @@ static void current_remove(DisplayChannel
> > *display,
> > TreeItem *item)
> >          } else {
> >              Container *now_as_container = CONTAINER(now);
> >  
> > +            /* This is a questionable assert. It relies several
> > assumptions
> > +             * to ensure that this function is never called for a
> > +             * TREE_ITEM_TYPE_SHADOW item.  */
> >              spice_assert(now->type == TREE_ITEM_TYPE_CONTAINER);
> >  
> >              if ((ring_item = ring_get_head(&now_as_container-
> > >items))) {
> > +                /* descend into the container's child ring and
> > continue
> > +                 * iterating and removing those children */
> >                  now = SPICE_CONTAINEROF(ring_item, TreeItem,
> > siblings_link);
> >                  continue;
> >              }
> > +            /* This item is a container but it has no children, so
> > reset our
> > +             * iterator to the item's previous sibling and free
> > this empty
> > +             * container */
> 
> Why a container without child? Maybe the result of other
> processing?

This is one of those confusing loops that jumps down to a different
ring in the middle of the loop and then comes back up a level when it's
finished. So this container is empty because we just removed all of its
children and then moved back up a level. I think it would be a lot
easier to follow if this was just written as recursive function rather
than manipulating a loop variable to point to a different container as
we're iterating. I find that very confusing, and it's done several
other times in this file.

> 
> >              ring_item = now->siblings_link.prev;
> >              container_free(now_as_container);
> >          }
> >          if (now == item) {
> > +            /* This is true if the initial @item was a DRAWABLE,
> > or if @item
> > +             * was a container and we've finished iterating over
> > all of that
> > +             * container's children and returned back up to the
> > parent and
> > +             * freed it (see below) */
> >              return;
> >          }
> >  
> > +        /* Increment the iterator to the next sibling. Note that
> > if an item was
> > +         * removed above, ring_item will have been reset to the
> > item before the
> > +         * item that was removed */
> >          if ((ring_item = ring_next(&container_of_now->items,
> > ring_item))) {
> >              now = SPICE_CONTAINEROF(ring_item, TreeItem,
> > siblings_link);
> >          } else {
> > +            /* there is no next sibling, so move one level up the
> > tree */
> >              now = &container_of_now->base;
> >          }
> >      }
> > @@ -467,10 +486,23 @@ static void current_remove_all(DisplayChannel
> > *display,
> > int surface_id)
> >  
> >      while ((ring_item = ring_get_head(ring))) {
> >          TreeItem *now = SPICE_CONTAINEROF(ring_item, TreeItem,
> >          siblings_link);
> > +        /* NOTE: current_remove() should never be called on Shadow
> > type items
> > +         * or we will hit an assert. Fortunately, the 'current'
> > ring is ordered
> > +         * in such a way that a DrawItem will always be placed
> > before its
> > +         * associated Shadow in the tree. Since removing a
> > DrawItem will also
> > +         * result in the associated Shadow item being removed from
> > the tree,
> > +         * this loop will never call current_remove() on a Shadow
> > item unless
> > +         * we change the order that items are inserted into the
> > tree */
> >          current_remove(display, now);
> >      }
> >  }
> >  
> > +/* Replace an existing Drawable in the tree with a new drawable
> > that is
> > + * equivalent. The new drawable is also added to the pipe.
> > + *
> > + * This function can fail if the items aren't actually equivalent
> > (e.g. either
> > + * item has a shadow, they have different effects, etc)
> > + */
> >  static int current_add_equal(DisplayChannel *display, DrawItem
> > *item,
> >  TreeItem *other)
> >  {
> >      DrawItem *other_draw_item;
> > @@ -490,6 +522,9 @@ static int current_add_equal(DisplayChannel
> > *display,
> > DrawItem *item, TreeItem *
> >      other_drawable = SPICE_CONTAINEROF(other_draw_item, Drawable,
> >      tree_item);
> >  
> >      if (item->effect == QXL_EFFECT_OPAQUE) {
> > +        /* check whether the new item can safely replace the other
> > drawable at
> > +         * the same position in the pipe, or whether it should be
> > added to the
> > +         * end of the queue */
> >          int add_after = !!other_drawable->stream &&
> >                          is_drawable_independent_from_surfaces(draw
> > able);
> >          stream_maintenance(display, drawable, other_drawable);
> 
> Here questions about how stream are handled raise. Why stream need
> special
> handling?

Yes, I admit that for this first stab at documentation, I didn't even
dig into streams or really try to understand them yet. So my
understanding is incomplete


> 
> > @@ -553,6 +588,47 @@ static int current_add_equal(DisplayChannel
> > *display,
> > DrawItem *item, TreeItem *
> >      return FALSE;
> >  }
> >  
> > +/* This function excludes the region from a single TreeItem
> > + *
> > + * If there is overlap between @rgn and the @item region, remove
> > the
> > + *
> > + * overlapping intersection from both @rgn and the item's region
> > (XXX WHY???)
> > + *
> > + * However, if the item is a DrawItem that has a shadow, we add an
> > additional
> > + * region to @rgn: the intersection of the shadow item's region
> > with @rgn if
> > + * @rgn was shifted over by the delta between the DrawItem and the
> > Shadow.
> > + * [WORKING THEORY: since the destination region for a COPY_BITS
> > operation was
> > + * excluded, we no longer need the source region that corresponds
> > with that
> > + * copy operation, so we can also exclude any drawables that
> > affect that
> > + * region. Not sure if that actually makes sense... ]
> > + *
> > + * If the item is a Shadow, we store the intersection between @rgn
> > and the
> > + * Shadow's region in Shadow::on_hold and remove that region from
> > @rgn. This is
> > + * done since a Shadow represents the source region for a
> > COPY_BITS operation,
> > + * and we need to make sure that this source region stays up-to-
> > date until the
> > + * copy operation is executed.
> > + *
> > + * Consider the following case:
> > + *  1) the surface is fully black at the beginning
> > + *  2) we add a new item to the tree which paints region A white
> > + *  3) we add a new item to the tree which copies region A to
> > region B
> > + *  4) we add another new item to teh tree painting region A blue.
> > + *
> > + * After all operations are completed, region A should be blue,
> > and region B
> > + * should be white. If there were no copy operation (step 3), we
> > could simply
> > + * eliminate step 2 when we add item 4 to the tree, since step 4
> > overwrites the
> > + * same region with a different color. However, if we did
> > eliminate step 2,
> > + * region B would be black after all operations were completed. So
> > these
> > + * regions that would normally be excluded are put "on hold" if
> > they are part
> > + * of a source region for a copy operation.
> > + *
> > + * @display: the display channel
> > + * @ring: a fallback toplevel ring???
> > + * @item: the tree item to exclude from @rgn
> > + * @rgn: the region to exclude (?)
> > + * @top_ring: ?
> > + * @frame_candidate: ?
> > + */
> 
> Need time to read again all this but looks like there is a lot of
> mechanical
> "understanding" but no real understanding of the intention of these 2
> (__exclude_region and exclude_region) functions.

Exactly right. I have a significantly better understanding than I did
at the beginning, but I feel there's still some important concepts that
I'm not quite able to grasp yet that would make things much more clear.

> 
> >  static void __exclude_region(DisplayChannel *display, Ring *ring,
> > TreeItem
> >  *item, QRegion *rgn,
> >                               Ring **top_ring, Drawable
> > *frame_candidate)
> >  {
> > @@ -560,51 +636,79 @@ static void __exclude_region(DisplayChannel
> > *display,
> > Ring *ring, TreeItem *item
> >      stat_start(&display->priv->__exclude_stat, start_time);
> >  
> >      region_clone(&and_rgn, rgn);
> > +    /* find intersection of the @rgn argument with the region of
> > the @item arg */
> >      region_and(&and_rgn, &item->rgn);
> >      if (!region_is_empty(&and_rgn)) {
> >          if (IS_DRAW_ITEM(item)) {
> >              DrawItem *draw = DRAW_ITEM(item);
> >  
> >              if (draw->effect == QXL_EFFECT_OPAQUE) {
> > +                /* remove the intersection from the original @rgn
> > */
> >                  region_exclude(rgn, &and_rgn);
> >              }
> >  
> >              if (draw->shadow) {
> > +                /* this item represents the destination of a
> > COPY_BITS
> > +                 * operation. 'shadow' represents the source item
> > for the copy
> > +                 * operation */
> >                  Shadow *shadow;
> >                  int32_t x = item->rgn.extents.x1;
> >                  int32_t y = item->rgn.extents.y1;
> >  
> > +                /* remove the intersection from the item's region
> > */
> >                  region_exclude(&draw->base.rgn, &and_rgn);
> >                  shadow = draw->shadow;
> > +                /* shift the intersected region by the difference
> > between the
> > +                 * source and destination regions */
> >                  region_offset(&and_rgn, shadow-
> > >base.rgn.extents.x1 - x,
> >                                shadow->base.rgn.extents.y1 - y);
> > +                /* remove the shifted intersection region from the
> > source
> > +                 * (shadow) item's region. If the destination is
> > excluded, we
> > +                 * can also exclude the corresponding area from
> > the source
> > */
> >                  region_exclude(&shadow->base.rgn, &and_rgn);
> > +                /* find the intersection between the shifted
> > intersection
> > +                 * region and the Shadow's 'on_hold' region. This
> > represents
> > +                 * the portion of the Shadow's region that we just
> > removed that
> > +                 * is currently stored in on_hold. */
> >                  region_and(&and_rgn, &shadow->on_hold);
> >                  if (!region_is_empty(&and_rgn)) {
> > +                    /* Since we removed a portion of the Shadow's
> > region, we
> > +                     * can also remove that portion from on_hold
> > */
> >                      region_exclude(&shadow->on_hold, &and_rgn);
> > +                    /* Since this region is no longer "on hold",
> > add it back to
> > +                     * the @rgn argument */
> >                      region_or(rgn, &and_rgn);
> >                      // in flat representation of current, shadow
> > is always
> >                      his owner next
> > +                    // XXX: what does that mean?
> >                      if (!tree_item_contained_by(&shadow->base,
> > *top_ring)) {
> >                          *top_ring =
> > tree_item_container_items(&shadow->base,
> >                          ring);
> >                      }
> >                  }
> >              } else {
> > +                /* XXX: ??? */
> >                  if (frame_candidate) {
> >                      Drawable *drawable = SPICE_CONTAINEROF(draw,
> > Drawable,
> >                      tree_item);
> >                      stream_maintenance(display, frame_candidate,
> > drawable);
> >                  }
> > +                /* Remove the intersection from the DrawItem's
> > region */
> >                  region_exclude(&draw->base.rgn, &and_rgn);
> >              }
> >          } else if (item->type == TREE_ITEM_TYPE_CONTAINER) {
> > +            /* excludes the intersection between 'rgn' and item-
> > >rgn from the
> > +             * item's region */
> >              region_exclude(&item->rgn, &and_rgn);
> >  
> >              if (region_is_empty(&item->rgn)) {  //assume container
> > removal
> >              will follow
> >                  Shadow *shadow;
> >  
> > +                /* exclude the intersection from the 'rgn'
> > argument as well,
> > +                 * but only if the item is now empty... WHY??? */
> >                  region_exclude(rgn, &and_rgn);
> >                  if ((shadow = tree_item_find_shadow(item))) {
> > +                    /* add the shadow's on_hold region back to the
> > 'rgn' argument */
> >                      region_or(rgn, &shadow->on_hold);
> >                      if (!tree_item_contained_by(&shadow->base,
> > *top_ring)) {
> > +                        /* what is top_ring used for??? */
> >                          *top_ring =
> > tree_item_container_items(&shadow->base,
> >                          ring);
> >                      }
> >                  }
> > @@ -614,14 +718,43 @@ static void __exclude_region(DisplayChannel
> > *display,
> > Ring *ring, TreeItem *item
> >  
> >              spice_assert(item->type == TREE_ITEM_TYPE_SHADOW);
> >              shadow = SHADOW(item);
> > +            /* Since a Shadow represents the source region for a
> > COPY_BITS
> > +             * operation, we need to make sure that we don't
> > remove existing
> > +             * drawables that draw to this source region. If we
> > did, it would
> > +             * affect the copy operation. So we remove the
> > intersection between
> > +             * @rgn and item->rgn from the @rgn argument to avoid
> > excluding
> > +             * these drawables */
> >              region_exclude(rgn, &and_rgn);
> > +            /* adds this intersection to on_hold */
> >              region_or(&shadow->on_hold, &and_rgn);
> >          }
> >      }
> > +    /* clean up memory */
> >      region_destroy(&and_rgn);
> >      stat_add(&display->priv->__exclude_stat, start_time);
> >  }
> >  
> > +/* This function iterates through the given @ring starting at
> > @ring_item and
> > + * continuing until reaching @last, and calls __exclude_item() on
> > each item.
> > + * Any items that have an empty region as a result of the
> > __exclude_region()
> > + * call are removed from the tree.
> > + *
> 
> Just as a ring of goes also inside containers ?
> Also... when does a container is created ?

Good questions. I documented a little about container creation
somewhere else in this patch. Essentially if there is already an opaque
item in the tree and we add a new drawable to the tree that fits
entirely inside that existing opaque item, we will create a new
container to hold both of these items. So Containers get created
dynamically as we add new drawables to the tree.

> How are items arranged in the tree ?

There's a top ring that holds TreeItems. As new drawables get added, a
new DrawItem is created for the drawable, and it will either be placed
in the top ring, or in the ring of a container whose bounds contain the
new drawable (as described above). If the Drawable is a COPY_BITS
operation, it will have a Shadow TreeItem, which is placed at the same
level in the tree heirarchy as its associated DrawItem, but is placed
immediately after it. It's not clear to me what happens to the shadow
if a Drawable that has a shadow is moved to a new container (as I
described above)...


> 
> > + * XXX: I still don't have a great conceptual understanding of
> > what we're
> > + * trying to do by calling this function.
> > + *
> 
> This is the problem.
> Maybe is creating an hole in the current "painting" ?
> Let's define the painting the result of the screen resulting from the
> drawing of
> the drawables, so at the beginning we could have a screen
> 
> +---------------+
> >               |
> >               |
> >               |
> >               |
> >               |
> 
> +---------------+
> 
> we draw an icon (very small, Drawable1)
> 
> +---------------+
> >               |
> >   +           |
> >               |
> >               |
> >               |
> 
> +---------------+
> 
> Then we draw a window a big bigger on it (Drawable2)
> 
> +---------------+
> >  +---+        |
> >  |   |        |
> >  +---+        |
> >               |
> >               |
> 
> +---------------+
> 
> both Drawable1 and Drawable2 are opaque. Before adding Drawable2 we
> basically remove all
> drawables under Drawable2 region. Maybe this is a call to
> exclude_region(... region_of_Drawable1 ...) ?

Yeah, I think this is basically correct. We no longer need to draw
Drawable1, because it became totally obscured by Drawable2 before we
had a chance to draw it. So we can safely remove it from the tree and
discard it. But this function also has several other side-effects (such
as modifying @rgn, so there's a lot going on and it's hard to keep
track of it all.

> 
> > + * @ring: every time this function is called, @ring is a Surface's
> > 'current'
> > + *      ring, or to the ring of children of a container within
> > that ring.
> > + * @ring_item: callers usually call this argument 'exclude_base'.
> > We will
> > + *      iterate through the tree starting at this item
> > + * @rgn: callers usually call this 'exclude_rgn' -- it appears to
> > be the region
> > + *      we want to exclude from existing items in the tree. It is
> > an in/out
> > + *      parameter and it may be modified as the result of calling
> > this function
> > + * @last: We will stop iterating at this item, and the function
> > will return the
> > + *      next item after iteration is complete (which may be
> > different than the
> > + *      passed value if that item was removed from the tree
> > + * @frame_candidate: usually callers pass NULL, sometimes it's the
> > drawable
> > + *      that's being added to the 'current' ring. What is its
> > purpose?
> > + */
> >  static void exclude_region(DisplayChannel *display, Ring *ring,
> > RingItem
> >  *ring_item,
> >                             QRegion *rgn, TreeItem **last, Drawable
> >                             *frame_candidate)
> >  {
> > @@ -640,40 +773,60 @@ static void exclude_region(DisplayChannel
> > *display,
> > Ring *ring, RingItem *ring_i
> >  
> >          spice_assert(!region_is_empty(&now->rgn));
> >  
> > +        /* check whether the ring_item item intersects the passed-
> > in region */
> >          if (region_intersects(rgn, &now->rgn)) {
> > +            /* remove the overlapping portions of region and now-
> > >rgn, among
> > +             * other things. See documentation for
> > __exclude_region() */
> >              __exclude_region(display, ring, now, rgn, &top_ring,
> >              frame_candidate);
> >  
> >              if (region_is_empty(&now->rgn)) {
> > +                /* __exclude_region() does not remove the region
> > of shadow-type
> > +                 * items */
> >                  spice_assert(now->type != TREE_ITEM_TYPE_SHADOW);
> >                  ring_item = now->siblings_link.prev;
> > +                /* if __exclude_region() removed the entire region
> > for this
> > +                 * sibling item, remove it from the 'current' tree
> > */
> >                  current_remove(display, now);
> >                  if (last && *last == now) {
> > +                    /* the caller wanted to stop at this item, but
> > this item
> > +                     * has been removed, so we set @last to the
> > next item */
> >                      SPICE_VERIFY(SPICE_OFFSETOF(TreeItem,
> > siblings_link) ==
> >                      0);
> >                      *last = (TreeItem *)ring_next(ring,
> > ring_item);
> >                  }
> >              } else if (now->type == TREE_ITEM_TYPE_CONTAINER) {
> > +                /* if this sibling is a container type, descend
> > into the
> > +                 * container's child ring and continue iterating
> > */
> >                  Container *container = CONTAINER(now);
> >                  if ((ring_item = ring_get_head(&container-
> > >items))) {
> >                      ring = &container->items;
> >                      spice_assert(SPICE_CONTAINEROF(ring_item,
> > TreeItem,
> >                      siblings_link)->container);
> >                      continue;
> >                  }
> > +                /* container had no children, so reset ring_item
> > to the
> > +                 * container itself */
> >                  ring_item = &now->siblings_link;
> >              }
> >  
> >              if (region_is_empty(rgn)) {
> > +                /* __exclude_region() removed the entire region
> > from 'rgn', so
> > +                 * no need to continue checking further items in
> > the tree */
> 
> I fail to understand, maybe I miss some knowledge about
> __exclude_region,
> so __exclude_region changed rgn and now->rgn ?

Yes, it modifies both of these parameters. But I don't fully understand
why.

> 
> >                  stat_add(&display->priv->exclude_stat,
> > start_time);
> >                  return;
> >              }
> >          }
> >  
> >          SPICE_VERIFY(SPICE_OFFSETOF(TreeItem, siblings_link) ==
> > 0);
> > +        /* if this is the last item to check, or if the current
> > ring is
> > +         * completed, don't go any further */
> >          while ((last && *last == (TreeItem *)ring_item) ||
> >                 !(ring_item = ring_next(ring, ring_item))) {
> > +            /* we're currently iterating the top ring, so we're
> > done */
> >              if (ring == top_ring) {
> >                  stat_add(&display->priv->exclude_stat,
> > start_time);
> >                  return;
> >              }
> > +            /* we're iterating through a container child ring, so
> > climb one
> > +             * level up the heirarchy and continue iterating that
> > ring */
> 
> Ok, so this function iterate all the tree from top to bottom.
> 
> >              ring_item = &container->base.siblings_link;
> >              container = container->base.container;
> >              ring = (container) ? &container->items : top_ring;
> > @@ -681,6 +834,8 @@ static void exclude_region(DisplayChannel
> > *display, Ring
> > *ring, RingItem *ring_i
> >      }
> >  }
> >  
> > +/* Add a @drawable (with a shadow) to the current ring.
> 
> Which current ring are we taking about? Surface, DisplayChannel ?

In this case, we always pass Surface::current (which is the tree) as
the @ring argument. So the DrawItem gets added to this ring. However,
the function eventually also adds the Drawable to Surface::current_list
and DisplayChannelPriv::current_list. So I guess you could say that it
adds it to *all* of the 'current' lists, but only the first one is
passed as an argument (I'm not quite sure why that one is treated
specially...)

> 
> > + * The return value indicates whether the new item should be added
> > to the pipe */
> >  static int current_add_with_shadow(DisplayChannel *display, Ring
> > *ring,
> >  Drawable *item)
> >  {
> >      stat_start(&display->priv->add_stat, start_time);
> > @@ -707,11 +862,19 @@ static int
> > current_add_with_shadow(DisplayChannel
> > *display, Ring *ring, Drawable
> >          stream_detach_behind(display, &shadow->base.rgn, NULL);
> >      }
> >  
> > +    /* Prepend the shadow to the beginning of the current ring */
> >      ring_add(ring, &shadow->base.siblings_link);
> > +    /* Prepend the draw item to the beginning of the current ring.
> > NOTE: this
> > +     * means that the drawable is placed *before* its associated
> > shadow in the
> > +     * tree. Changing this order will violate several unstated
> > assumptions
> > */
> >      current_add_drawable(display, item, ring);
> >      if (item->tree_item.effect == QXL_EFFECT_OPAQUE) {
> >          QRegion exclude_rgn;
> >          region_clone(&exclude_rgn, &item->tree_item.base.rgn);
> > +        /* Since the new drawable is opaque, remove overlapped
> > regions from all
> > +         * items already in the tree.  Start iterating through the
> > tree
> > +         * starting with the shadow item to avoid excluding the
> > new item
> > +         * itself */
> >          exclude_region(display, ring, &shadow->base.siblings_link,
> >          &exclude_rgn, NULL, NULL);
> >          region_destroy(&exclude_rgn);
> >          streams_update_visible_region(display, item);
> > @@ -724,6 +887,8 @@ static int
> > current_add_with_shadow(DisplayChannel
> > *display, Ring *ring, Drawable
> >      return TRUE;
> >  }
> >  
> > +/* Add a @drawable (without a shadow) to the current ring.
> > + * The return value indicates whether the new item should be added
> > to the pipe */
> >  static int current_add(DisplayChannel *display, Ring *ring,
> > Drawable
> >  *drawable)
> >  {
> >      DrawItem *item = &drawable->tree_item;
> > @@ -736,54 +901,116 @@ static int current_add(DisplayChannel
> > *display, Ring
> > *ring, Drawable *drawable)
> >      region_init(&exclude_rgn);
> >      now = ring_next(ring, ring);
> >  
> > +    /* check whether the new drawable region intersects any of the
> > items
> > +     * already in the 'current' ring */
> >      while (now) {
> >          TreeItem *sibling = SPICE_CONTAINEROF(now, TreeItem,
> > siblings_link);
> >          int test_res;
> >  
> >          if (!region_bounds_intersects(&item->base.rgn, &sibling-
> > >rgn)) {
> > +            /* the bounds of the two items are totally disjoint,
> > so no need to
> > +             * check further. check the next item */
> >              now = ring_next(ring, now);
> >              continue;
> >          }
> > +        /* bounds overlap, but check whether the regions actually
> > overlap */
> >          test_res = region_test(&item->base.rgn, &sibling->rgn,
> >          REGION_TEST_ALL);
> >          if (!(test_res & REGION_TEST_SHARED)) {
> > +            /* there's no overlap of the regions between these two
> > items. Move
> > +             * on to the next one. */
> >              now = ring_next(ring, now);
> >              continue;
> >          } else if (sibling->type != TREE_ITEM_TYPE_SHADOW) {
> > +            /* there is an overlap between the two regions */
> > +            /* NOTE: Shadow types represent a source region for a
> > COPY_BITS
> > +             * operation, they don't represent a region that will
> > be drawn.
> > +             * Therefore, we don't check for overlap between the
> > new
> > +             * DrawItem and any shadow items */
> >              if (!(test_res & REGION_TEST_RIGHT_EXCLUSIVE) &&
> >                                                     !(test_res &
> >                                                     REGION_TEST_LEF
> > T_EXCLUSIVE)
> >                                                     &&
> >                                                     current_add_equ
> > al(display,
> >                                                     item, sibling))
> > {
> > +                /* the regions were equivalent, so we just
> > replaced the other
> > +                 * drawable with the new one */
> >                  stat_add(&display->priv->add_stat, start_time);
> > +                /* Caller doesn't need to add the new drawable to
> > the pipe,
> > +                 * since current_add_equal already added it to the
> > pipe */
> >                  return FALSE;
> >              }
> >  
> >              if (!(test_res & REGION_TEST_RIGHT_EXCLUSIVE) && item-
> > >effect ==
> >              QXL_EFFECT_OPAQUE) {
> > +                /* the new drawable is opaque and entirely
> > contains the sibling item */
> >                  Shadow *shadow;
> >                  int skip = now == exclude_base;
> >  
> >                  if ((shadow = tree_item_find_shadow(sibling))) {
> > +                    /* The sibling item was the destination of a
> > COPY_BITS operation */
> >                      if (exclude_base) {
> > +                        /* During a previous iteration through
> > this loop, an
> > +                         * obscured sibling item was removed from
> > the tree, and
> > +                         * exclude_base was set to the item
> > immediately after
> > +                         * the removed item (see below). This time
> > through the
> > +                         * loop, we encountered another sibling
> > that was
> > +                         * completely obscured, so we call
> > exclude_region()
> > +                         * using the previously saved item as our
> > starting
> > +                         * point. @exlude_rgn will be the union of
> > any previous
> > +                         * 'on_hold' regions from the shadows of
> > previous
> > +                         * iterations
> > +                         *
> > +                         * XXX: why do we only only call
> > exclude_region() for
> > +                         * the previous item if the next item is
> > obscured and
> > +                         * has a shadow???
> > +                         */
> >                          TreeItem *next = sibling;
> > +                        /* XXX: What is the intent of this call?
> > */
> 
> I miss something in this function.

yeah, I'm hoping somebody else can help me understand this part of the
code. I studied it for a long time, and I still don't have a good
understanding, I'm afraid.

> 
> >                          exclude_region(display, ring,
> > exclude_base,
> >                          &exclude_rgn, &next, NULL);
> >                          if (next != sibling) {
> > +                            /* the @next param is only changed if
> > the given item
> > +                             * was removed as a side-effect of
> > calling
> > +                             * exclude_region(), so update our
> > loop variable
> > */
> >                              now = next ? &next->siblings_link :
> > NULL;
> >                              exclude_base = NULL;
> >                              continue;
> >                          }
> >                      }
> > +                    /* Since the destination item (sibling) of the
> > COPY_BITS
> > +                     * operation is fully obscured, we no longer
> > need the
> > +                     * source item (shadow) anymore. shadow-
> > >on_hold represents
> > +                     * a region that would normally have been
> > excluded by a
> > +                     * previous call to __exclude_region() (see
> > documentation
> > +                     * for that function), but was put on hold to
> > make sure we
> > +                     * kept the source region up to date. Now that
> > we no longer
> > +                     * need this source region, this "on hold"
> > region can be
> > +                     * safely excluded again. */
> >                      region_or(&exclude_rgn, &shadow->on_hold);
> >                  }
> >                  now = now->prev;
> > +                /* remove the obscured sibling from the 'current'
> > tree, which
> > +                 * will also remove its shadow (if any) */
> >                  current_remove(display, sibling);
> > +                /* advance the loop variable */
> >                  now = ring_next(ring, now);
> >                  if (shadow || skip) {
> > +                    /* XXX: don't understand this exclude_base
> > stuff
> > +                     * 'now' is currently set to the the item
> > immediately AFTER
> > +                     * the obscured sibling that we just removed.
> > Why is this
> > +                     * item used as an 'exclude_base'??
> > +                     */
> >                      exclude_base = now;
> >                  }
> >                  continue;
> >              }
> >  
> >              if (!(test_res & REGION_TEST_LEFT_EXCLUSIVE) &&
> >              is_opaque_item(sibling)) {
> > +                /* the sibling item is opaque and entirely
> > contains the new drawable */
> >                  Container *container;
> >  
> > +                /* XXX: still don't understand this exclude_base
> > stuff. The
> > +                 * first time through, @exclude_base will be NULL,
> > but
> > +                 * subsequent loops may set it to something.
> > +                 * In addition, @exclude_rgn starts out empty, but
> > previous
> > +                 * iterations of this loop may have added various
> > +                 * Shadow::on_hold regions to it.
> > +                 */
> >                  if (exclude_base) {
> >                      exclude_region(display, ring, exclude_base,
> >                      &exclude_rgn, NULL, NULL);
> >                      region_clear(&exclude_rgn);
> > @@ -791,13 +1018,20 @@ static int current_add(DisplayChannel
> > *display, Ring
> > *ring, Drawable *drawable)
> >                  }
> >                  if (sibling->type == TREE_ITEM_TYPE_CONTAINER) {
> >                      container = CONTAINER(sibling);
> > +                    /* NOTE: here, ring is reset to the ring of
> > the container's children */
> >                      ring = &container->items;
> > +                    /* if the sibling item is a container, place
> > the new
> > +                     * drawable into that container */
> >                      item->base.container = container;
> > +                    /* Start iterating over the container's
> > children to see if
> > +                     * any of them intersect this new drawable */
> >                      now = ring_next(ring, ring);
> >                      continue;
> >                  }
> >                  spice_assert(IS_DRAW_ITEM(sibling));
> >                  if (!DRAW_ITEM(sibling)->container_root) {
> > +                    /* Create a new container to hold the sibling
> > and the new
> > +                     * drawable */
> >                      container = container_new(DRAW_ITEM(sibling));
> >                      if (!container) {
> >                          spice_warning("create new container
> > failed");
> > @@ -805,17 +1039,32 @@ static int current_add(DisplayChannel
> > *display, Ring
> > *ring, Drawable *drawable)
> >                          return FALSE;
> >                      }
> >                      item->base.container = container;
> > +                    /* reset 'ring' to the container's children
> > ring, so that
> > +                     * we can add the new drawable to this ring
> > below */
> >                      ring = &container->items;
> >                  }
> >              }
> >          }
> > +        /* If we've gotten here, that means that:
> > +         *  - the new item is not opaque
> > +         *  - We just created a container to hold the new drawable
> > and the
> > +         *    sibling that encloses it
> > +         *  - ??? */
> >          if (!exclude_base) {
> >              exclude_base = now;
> >          }
> >          break;
> >      }
> > +    /* we've removed any obscured siblings and figured out which
> > ring the new
> > +     * drawable needs to be added to, so let's add it. */
> >      if (item->effect == QXL_EFFECT_OPAQUE) {
> > +        /* @exclude_rgn may contain the union of on_hold regions
> > from any
> > +         * Shadows that were associated with DrawItems that were
> > removed from
> > +         * the tree.  Add the new item's region to that */
> >          region_or(&exclude_rgn, &item->base.rgn);
> > +        /* XXX: Why do we need to call exclude_region() here
> > again? I thought
> > +         * we had just iterated the whole list above to check for
> > region
> > +         * intersections between this new item and existing
> > items... */
> >          exclude_region(display, ring, exclude_base, &exclude_rgn,
> > NULL,
> >          drawable);
> >          stream_trace_update(display, drawable);
> >          streams_update_visible_region(display, drawable);
> > @@ -1623,6 +1872,8 @@ static void surface_update_dest(RedSurface
> > *surface,
> > const SpiceRect *area)
> >      canvas->ops->read_bits(canvas, dest, -stride, area);
> >  }
> >  
> > +/* Draws all drawables associated with @surface, starting from the
> > tail of the
> > + * ring, and stopping after it draws @last */
> 
> Tail of which ring? And how is this ring sorted? I suppose
> we draw from elder to newer.

Right. I should probably have mentioned it in the comment. It's the
tail of the Surface::current_list, which is the flat list (not the
tree) that holds Drawables for this surface. For all of these rings,
new items are added to the head. So that means that the tail should be
the oldest drawable.

> 
> >  static void draw_until(DisplayChannel *display, RedSurface
> > *surface,
> >  Drawable *last)
> >  {
> >      RingItem *ring_item;
> > @@ -1646,6 +1897,11 @@ static void draw_until(DisplayChannel
> > *display,
> > RedSurface *surface, Drawable *l
> >      } while (now != last);
> >  }
> >  
> > +/* Find the first Drawable in the @current ring that intersects
> > the given
> > + * @area, starting at item @from (or the head of the ring if @from
> > is NULL).
> > + *
> > + * NOTE: this function expects @current to be a ring of Drawables,
> > and more
> > + * specifically an instance of Surface::current_list (not
> > Surface::current)
> 
> Definitively we need better names, too many current!

Indeed. But I guess there is a reason for the similar names: they all
basically hold the same items, just organized a bit differently
(although 'current' also holds extra items -- shadows and containers).

Surface::current: a heirarchical tree of drawables (and supporting
containers, etc) for this surface
Surface::current_list: a flat list of drawables for this surface
DisplayChannel::current_list: a flat list of all drawables for all
surfaces of this channel.

So, all drawables are added to all three of these lists.

> 
> > */
> >  static Drawable* current_find_intersects_rect(Ring *current,
> > RingItem *from,
> >                                                const SpiceRect
> > *area)
> >  {
> > diff --git a/server/display-channel.h b/server/display-channel.h
> > index ba83e8c..d7184a7 100644
> > --- a/server/display-channel.h
> > +++ b/server/display-channel.h
> > @@ -162,8 +162,14 @@ typedef struct DrawContext {
> >  
> >  typedef struct RedSurface {
> >      uint32_t refs;
> > -    Ring current; /* TreeItem */
> > -    Ring current_list; /* Drawable */
> > +    /* A Ring representing a hierarchical tree structure. This
> > tree includes
> > +     * DrawItems, Containers, and Shadows. It is used to
> > efficiently determine
> > +     * which drawables overlap, and to exclude regions of
> > drawables that are
> > +     * obscured by other drawables */
> > +    Ring current;
> > +    /* A ring of pending Drawables associated with this surface.
> > This ring is
> > +     * actually used for drawing */
> 
> Is this just containing drawabled, right? Not the tree?
> Why this is used for drawing and not the tree?
> Does if have a specific order?

Yes, current_list only holds Drawables. And it is ordered by the order
we received the commands from the device.

My understanding is that the tree ("current") is basically just a
convenient representation that makes it more efficient to calculate
which drawables intersect/overlap. When exclude_region() is called, it
uses this hierarchical tree to eliminate obscured drawables from the
tree. When they are removed from the tree, they are also removed from
the other lists (and from the pipe). But pretty much all other
operations (e.g. drawing) use the flat current_list. I think this is
because it is ordered by age, and we want to draw the commands in the
order they were received. 

> I though that the drawing was done using pipe items.

Well, the drawables are sent to the client via pipe items so that the
client can draw them. But when I say "drawing" above, I'm talking about
e.g. drawable_draw(). This function appears to draw the given drawable
to the surface's canvas (on the server side).  Again, my understanding
here is incomplete. Presumably we need to keep a cache of the surface
on the server side in case we need to send the full surface image to a
client, or something like that? Probably that stuff should be
documented as well.

> 
> > +    Ring current_list;
> >      DrawContext context;
> >  
> >      Ring depend_on_me;
> > diff --git a/server/tree.c b/server/tree.c
> > index ea11000..cc3a96f 100644
> > --- a/server/tree.c
> > +++ b/server/tree.c
> > @@ -185,6 +185,9 @@ void tree_item_dump(TreeItem *item)
> >      tree_foreach(item, dump_item, &di);
> >  }
> >  
> > +/* Creates a new Shadow item for the given DrawItem, with an
> > offset of @delta.
> > + * A shadow represents a source region for a COPY_BITS operation,
> > while the
> > + * DrawItem represents the destination region for the operation */
> >  Shadow* shadow_new(DrawItem *item, const SpicePoint *delta)
> >  {
> >      spice_return_val_if_fail(item->shadow == NULL, NULL);
> > @@ -205,6 +208,11 @@ Shadow* shadow_new(DrawItem *item, const
> > SpicePoint
> > *delta)
> >      return shadow;
> >  }
> >  
> > +/* Create a new container to hold @item and insert @item into this
> > container.
> > + *
> > + * NOTE: This function assumes that @item is already inside a
> > different Ring,
> > + * so it removes @item from that ring before inserting it into the
> > new
> > + * container */
> >  Container* container_new(DrawItem *item)
> >  {
> >      Container *container = spice_new(Container, 1);
> > @@ -268,6 +276,8 @@ Shadow* tree_item_find_shadow(TreeItem *item)
> >      return DRAW_ITEM(item)->shadow;
> >  }
> >  
> > +/* return the Ring containing siblings of item, falling back to
> > @ring if @item
> > + * does not have a container */
> >  Ring *tree_item_container_items(TreeItem *item, Ring *ring)
> >  {
> >      return (item->container) ? &item->container->items : ring;
> > @@ -281,7 +291,7 @@ int tree_item_contained_by(TreeItem *item, Ring
> > *ring)
> >          if (now == ring) {
> >              return TRUE;
> >          }
> > -    } while ((item = &item->container->base));
> > +    } while ((item = &item->container->base)); /* move up one
> > level */
> >  
> >      return FALSE;
> >  }
> 
> Comments on this file seems ready to be pushed.
> 
> > diff --git a/server/tree.h b/server/tree.h
> > index 35b78ab..e579dd0 100644
> > --- a/server/tree.h
> > +++ b/server/tree.h
> > @@ -43,12 +43,18 @@ struct TreeItem {
> >      RingItem siblings_link;
> >      uint32_t type;
> >      Container *container;
> > +    /* rgn holds the region of the item. As additional items get
> > added to the
> > +     * tree, this region may be modified to represent the portion
> > of the item
> > +     * that is not obscured by other items */
> 
> so it's the visible region, not the original one.

Yes. But I should probably note that the Drawable's region is never
modified. The TreeItem's region starts off as a clone of the Drawable's
region and is modified as new drawables are added. When the TreeItem's
region finally becomes empty, we know that the drawable is fully
obscured and we can discard the given drawable from the tree. 

> 
> >      QRegion rgn;
> >  };
> >  
> >  /* A region "below" a copy, or the src region of the copy */
> >  struct Shadow {
> >      TreeItem base;
> > +    /* holds the union of all parts of this source region that
> > have been
> > +     * obscured by a drawable item that has been subsequently
> > added to the tree
> > +     */
> >      QRegion on_hold;
> 
> basically here, opposite to rgn we hold the not visible region...
> I would ask why.


I have a semi-understanding (or at least a partial working theory)
about this field that I documented elsewhere as part of
__exclude_region(). I'll reproduce it here:


    -----------
    If the item is a Shadow, we store the intersection between @rgn and
    the Shadow's region in Shadow::on_hold and remove that region from
    @rgn. This is done since a Shadow represents the source region for a
    COPY_BITS operation, and we need to make sure that this source
    region stays up-to-date until the copy operation is executed.

    Consider the following case:
     1) the surface is fully black at the beginning
     2) we add a new item to the tree which paints region A white
     3) we add a new item to the tree which copies region A to region B
     4) we add another new item to teh tree painting region A blue.

    After all operations are completed, region A should be blue, and
    region B should be white. If there were no copy operation (step 3),
    we could simply eliminate step 2 when we add item 4 to the tree,
    since step 4 overwrites the same region with a different color.
    However, if we did eliminate step 2, region B would be black after
    all operations were completed. So these regions that would normally
    be excluded are put "on hold" if they are part of a source region
    for a copy operation.
    ------------

This was just my attempt to understand this field from reading the code
(for a long time). My understanding is still incomplete, and I'd love
to hear whether it makes sense to others.


Thanks,
Jonathon


More information about the Spice-devel mailing list