From 6a5cc111713cec1d0e1edf9b8a1e64eb17105d9c Mon Sep 17 00:00:00 2001 From: Sami Kiminki Date: Wed, 6 May 2015 17:50:34 +0300 Subject: gpu: nvgpu: Optimize validate_fixed_buffer Function validate_fixed_buffer used to do a linear search for collision detection of already mapped buffers. Optimize this by doing a nice logarithmic search instead. Change-Id: Ifbf2ec015741d44883da27bc6f8cc090c48da145 Signed-off-by: Sami Kiminki Reviewed-on: http://git-master/r/739682 Reviewed-by: Terje Bergstrom Tested-by: Terje Bergstrom --- drivers/gpu/nvgpu/gk20a/mm_gk20a.c | 42 ++++++++++++++++++++++++++------------ 1 file changed, 29 insertions(+), 13 deletions(-) (limited to 'drivers') diff --git a/drivers/gpu/nvgpu/gk20a/mm_gk20a.c b/drivers/gpu/nvgpu/gk20a/mm_gk20a.c index 5e1505c4..735c262a 100644 --- a/drivers/gpu/nvgpu/gk20a/mm_gk20a.c +++ b/drivers/gpu/nvgpu/gk20a/mm_gk20a.c @@ -1054,6 +1054,27 @@ static struct mapped_buffer_node *find_mapped_buffer_range_locked( return NULL; } +/* find the first mapped buffer with GPU VA less than addr */ +static struct mapped_buffer_node *find_mapped_buffer_less_than_locked( + struct rb_root *root, u64 addr) +{ + struct rb_node *node = root->rb_node; + struct mapped_buffer_node *ret = NULL; + + while (node) { + struct mapped_buffer_node *mapped_buffer = + container_of(node, struct mapped_buffer_node, node); + if (mapped_buffer->addr >= addr) + node = node->rb_left; + else { + ret = mapped_buffer; + node = node->rb_right; + } + } + + return ret; +} + #define BFR_ATTRS (sizeof(nvmap_bfr_param)/sizeof(nvmap_bfr_param[0])) struct buffer_attrs { @@ -1165,19 +1186,14 @@ static int validate_fixed_buffer(struct vm_gk20a *vm, return -EINVAL; } - /* check that this mappings does not collide with existing - * mappings by checking the overlapping area between the current - * buffer and all other mapped buffers */ - - list_for_each_entry(buffer, - &va_node->va_buffers_list, va_buffers_list) { - s64 begin = max(buffer->addr, map_offset); - s64 end = min(buffer->addr + - buffer->size, map_offset + map_size); - if (end - begin > 0) { - gk20a_warn(dev, "overlapping buffer map requested"); - return -EINVAL; - } + /* check that this mapping does not collide with existing + * mappings by checking the buffer with the highest GPU VA + * that is less than our buffer end */ + buffer = find_mapped_buffer_less_than_locked( + &vm->mapped_buffers, map_offset + map_size); + if (buffer && buffer->addr + buffer->size > map_offset) { + gk20a_warn(dev, "overlapping buffer map requested"); + return -EINVAL; } return 0; -- cgit v1.2.2