[Intel-gfx] [PATCH 08/66] drm/i915: Make the stale cached active node available for any timeline

[Chris Wilson]

Quoting Tvrtko Ursulin (2020-07-29 15:22:26)
> 
> On 29/07/2020 14:42, Chris Wilson wrote:
> >>          parent = NULL;
> >>          p = &ref->tree.rb_node;
> >>          while (*p) {
> >>                  parent = *p;
> >>
> >>                  node = rb_entry(parent, struct active_node, node);
> >>                  if (node->timeline == idx) {
> >>                          kmem_cache_free(global.slab_cache, prealloc);
> >>                          goto out;
> >>                  }
> >>
> >>                  if (node->timeline < idx)
> >>                          p = &parent->rb_right;
> >>                  else
> >>                          p = &parent->rb_left;
> >>                          WRITE_ONCE(ref->cache, it);
> >>                          break;
> >>                  }
> >>          }
> >> ...
> >>
> >> Tree walk could be consolidated between the two.
> > 
> > This tree walk is subtly different, as we aren't just interested in the
> > node, but its parent. The exact repetitions have been consolidated into
> > __active_lookup.
> 
> It returns the previous/parent node if idx is not found so yeah, common 
> helper would need to have two out parameters. One returns the match, or 
> NULL, another returns the previous/parent node. You think that is not 
> worth it?

I remember in the past wanting to keep the lookup separate from
insertion as the compiler generated better code if we didn't track the
parent pointer.
-Chris