[PATCH 1/1] drm/mm: optimize rb_hole_addr rbtree search in high addr mode

[Chris Wilson]

Quoting Nirmoy Das (2020-04-28 17:04:23)
> Userspace can severely fragment rb_hole_addr rbtree by manipulating
> alignment while allocating buffers. Fragmented rb_hole_addr rbtree would
> result in large delays while allocating buffer object for a userspace
> application. It takes long time to find suitable hole because if we fail
> to find a suitable hole in the first attempt then we look for neighbouring
> nodes using rb_prev(). Traversing rbtree using rb_prev() can take really
> long time if the tree is fragmented.
> 
> This patch improves searches in fragmented rb_hole_addr rbtree by storing
> an extra field in drm_mm_node, max_hole_size. Each drm_mm_node now stores
> maximum hole size for its subtree in drm_mm_node->max_hole_size. Using
> drm_mm_node->max_hole_size, it is possible to eliminate complete
> subtree if that subtree is unable to serve a request hence reducing number
> of rb_prev() used.
> 
> Note: Implementation details of rb_hole_addr rbtree updates after a node
> removal and addition is borrowed from block/bfq-wf2q.c which is trying to
> achieve a similar goal.

Feels like it is an augmented rbtree?

> +static struct drm_mm_node *
> +next_hole_high_addr(struct drm_mm_node *entry, u64 size)
> +{
> +       struct rb_node *rb_node, *left_rb_node, *parent_rb_node;
> +       struct drm_mm_node *left_node;
> +
> +       if (!entry)
> +               return false;
> +
> +       rb_node = &entry->rb_hole_addr;
> +       if (rb_node->rb_left) {
> +               left_rb_node = rb_node->rb_left;
> +               parent_rb_node = rb_parent(rb_node);
> +               left_node = rb_entry(left_rb_node,
> +                                    struct drm_mm_node, rb_hole_addr);
> +               if ((left_node->max_hole_size < size ||
> +                    entry->size == entry->max_hole_size) &&
> +                   parent_rb_node && parent_rb_node->rb_left != rb_node)
> +                       return rb_hole_addr_to_node(parent_rb_node);
> +       }
> +
> +       return rb_hole_addr_to_node(rb_prev(rb_node));
> +}

The max_hole_size would equally apply to next_hole_low_addr(), right?

Sadly, I did not explore the fragmented search LOW/HIGH in test-drm_mm.c.
That would be a useful addition as well.
-Chris