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

[Nirmoy]

On 4/28/20 6:18 PM, Chris Wilson wrote:
> 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?


I just read about augmented rbtree quickly and yes it feels like so.  I 
will try to understand more

about it and will see if I can convert this logic to a 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?


Sorry,  yes we need that too. I will add next_hole_low_addr().


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


Yes that would be useful too.

I used ./tools/testing/selftests/drivers/gpu/drm_mm.sh to verify this patch.

> -Chris


Thanks for reviewing,

Nirmoy