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
_______________________________________________
dri-devel mailing list
dri-devel@xxxxxxxxxxxxxxxxxxxxx
https://lists.freedesktop.org/mailman/listinfo/dri-devel
