| Message ID | 20211201142918.921493-64-Liam.Howlett@oracle.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | Introducing the Maple Tree | expand |
On 12/1/21 15:30, Liam Howlett wrote: > From: "Matthew Wilcox (Oracle)" <willy@infradead.org> > > Replace the O(n.log(n)) loop with an O(n) loop. Not true? > Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org> > Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com> Acked-by: Vlastimil Babka <vbabka@suse.cz> > --- > drivers/gpu/drm/i915/gem/i915_gem_userptr.c | 14 +++++--------- > 1 file changed, 5 insertions(+), 9 deletions(-) > > diff --git a/drivers/gpu/drm/i915/gem/i915_gem_userptr.c b/drivers/gpu/drm/i915/gem/i915_gem_userptr.c > index 3173c9f9a040..39960973c130 100644 > --- a/drivers/gpu/drm/i915/gem/i915_gem_userptr.c > +++ b/drivers/gpu/drm/i915/gem/i915_gem_userptr.c > @@ -425,12 +425,11 @@ static const struct drm_i915_gem_object_ops i915_gem_userptr_ops = { > static int > probe_range(struct mm_struct *mm, unsigned long addr, unsigned long len) > { > - const unsigned long end = addr + len; > + VMA_ITERATOR(vmi, mm, addr); > struct vm_area_struct *vma; > - int ret = -EFAULT; > > mmap_read_lock(mm); > - for (vma = find_vma(mm, addr); vma; vma = vma->vm_next) { > + for_each_vma_range(vmi, vma, addr + len) { > /* Check for holes, note that we also update the addr below */ > if (vma->vm_start > addr) > break; > @@ -438,16 +437,13 @@ probe_range(struct mm_struct *mm, unsigned long addr, unsigned long len) > if (vma->vm_flags & (VM_PFNMAP | VM_MIXEDMAP)) > break; > > - if (vma->vm_end >= end) { > - ret = 0; > - break; > - } > - > addr = vma->vm_end; > } > mmap_read_unlock(mm); > > - return ret; > + if (vma) > + return -EFAULT; > + return 0; > } > > /*
On Thu, Jan 20, 2022 at 03:59:11PM +0100, Vlastimil Babka wrote: > On 12/1/21 15:30, Liam Howlett wrote: > > From: "Matthew Wilcox (Oracle)" <willy@infradead.org> > > > > Replace the O(n.log(n)) loop with an O(n) loop. > > Not true? Oh, right, that should have been just the linked-list walk. I misread it as calling find_vma() for each iteration instead of just the first one. Liam, do you mind updating the changelog here? I wonder whether we want a "for_each_contiguous_vma()" that will stop on a hole. It seems like a relatively sensible thing to do -- walk across a contiguous range of memory and stop if there's no VMA mapping a page. Like gup(), for example. > > Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org> > > Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com> > > Acked-by: Vlastimil Babka <vbabka@suse.cz> > > > --- > > drivers/gpu/drm/i915/gem/i915_gem_userptr.c | 14 +++++--------- > > 1 file changed, 5 insertions(+), 9 deletions(-) > > > > diff --git a/drivers/gpu/drm/i915/gem/i915_gem_userptr.c b/drivers/gpu/drm/i915/gem/i915_gem_userptr.c > > index 3173c9f9a040..39960973c130 100644 > > --- a/drivers/gpu/drm/i915/gem/i915_gem_userptr.c > > +++ b/drivers/gpu/drm/i915/gem/i915_gem_userptr.c > > @@ -425,12 +425,11 @@ static const struct drm_i915_gem_object_ops i915_gem_userptr_ops = { > > static int > > probe_range(struct mm_struct *mm, unsigned long addr, unsigned long len) > > { > > - const unsigned long end = addr + len; > > + VMA_ITERATOR(vmi, mm, addr); > > struct vm_area_struct *vma; > > - int ret = -EFAULT; > > > > mmap_read_lock(mm); > > - for (vma = find_vma(mm, addr); vma; vma = vma->vm_next) { > > + for_each_vma_range(vmi, vma, addr + len) { > > /* Check for holes, note that we also update the addr below */ > > if (vma->vm_start > addr) > > break; > > @@ -438,16 +437,13 @@ probe_range(struct mm_struct *mm, unsigned long addr, unsigned long len) > > if (vma->vm_flags & (VM_PFNMAP | VM_MIXEDMAP)) > > break; > > > > - if (vma->vm_end >= end) { > > - ret = 0; > > - break; > > - } > > - > > addr = vma->vm_end; > > } > > mmap_read_unlock(mm); > > > > - return ret; > > + if (vma) > > + return -EFAULT; > > + return 0; > > } > > > > /* >
* Matthew Wilcox <willy@infradead.org> [220120 10:50]: > On Thu, Jan 20, 2022 at 03:59:11PM +0100, Vlastimil Babka wrote: > > On 12/1/21 15:30, Liam Howlett wrote: > > > From: "Matthew Wilcox (Oracle)" <willy@infradead.org> > > > > > > Replace the O(n.log(n)) loop with an O(n) loop. > > > > Not true? > > Oh, right, that should have been just the linked-list walk. > I misread it as calling find_vma() for each iteration instead > of just the first one. Liam, do you mind updating the changelog > here? I will update the changelog for v5. > > I wonder whether we want a "for_each_contiguous_vma()" that > will stop on a hole. It seems like a relatively sensible thing > to do -- walk across a contiguous range of memory and stop if > there's no VMA mapping a page. Like gup(), for example. Hmm, so search for a non-zero gap across a range might be a reasonable implementation. > > > > Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org> > > > Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com> > > > > Acked-by: Vlastimil Babka <vbabka@suse.cz> > > > > > --- > > > drivers/gpu/drm/i915/gem/i915_gem_userptr.c | 14 +++++--------- > > > 1 file changed, 5 insertions(+), 9 deletions(-) > > > > > > diff --git a/drivers/gpu/drm/i915/gem/i915_gem_userptr.c b/drivers/gpu/drm/i915/gem/i915_gem_userptr.c > > > index 3173c9f9a040..39960973c130 100644 > > > --- a/drivers/gpu/drm/i915/gem/i915_gem_userptr.c > > > +++ b/drivers/gpu/drm/i915/gem/i915_gem_userptr.c > > > @@ -425,12 +425,11 @@ static const struct drm_i915_gem_object_ops i915_gem_userptr_ops = { > > > static int > > > probe_range(struct mm_struct *mm, unsigned long addr, unsigned long len) > > > { > > > - const unsigned long end = addr + len; > > > + VMA_ITERATOR(vmi, mm, addr); > > > struct vm_area_struct *vma; > > > - int ret = -EFAULT; > > > > > > mmap_read_lock(mm); > > > - for (vma = find_vma(mm, addr); vma; vma = vma->vm_next) { > > > + for_each_vma_range(vmi, vma, addr + len) { > > > /* Check for holes, note that we also update the addr below */ > > > if (vma->vm_start > addr) > > > break; > > > @@ -438,16 +437,13 @@ probe_range(struct mm_struct *mm, unsigned long addr, unsigned long len) > > > if (vma->vm_flags & (VM_PFNMAP | VM_MIXEDMAP)) > > > break; > > > > > > - if (vma->vm_end >= end) { > > > - ret = 0; > > > - break; > > > - } > > > - > > > addr = vma->vm_end; > > > } > > > mmap_read_unlock(mm); > > > > > > - return ret; > > > + if (vma) > > > + return -EFAULT; > > > + return 0; > > > } > > > > > > /* > > >
diff --git a/drivers/gpu/drm/i915/gem/i915_gem_userptr.c b/drivers/gpu/drm/i915/gem/i915_gem_userptr.c index 3173c9f9a040..39960973c130 100644 --- a/drivers/gpu/drm/i915/gem/i915_gem_userptr.c +++ b/drivers/gpu/drm/i915/gem/i915_gem_userptr.c @@ -425,12 +425,11 @@ static const struct drm_i915_gem_object_ops i915_gem_userptr_ops = { static int probe_range(struct mm_struct *mm, unsigned long addr, unsigned long len) { - const unsigned long end = addr + len; + VMA_ITERATOR(vmi, mm, addr); struct vm_area_struct *vma; - int ret = -EFAULT; mmap_read_lock(mm); - for (vma = find_vma(mm, addr); vma; vma = vma->vm_next) { + for_each_vma_range(vmi, vma, addr + len) { /* Check for holes, note that we also update the addr below */ if (vma->vm_start > addr) break; @@ -438,16 +437,13 @@ probe_range(struct mm_struct *mm, unsigned long addr, unsigned long len) if (vma->vm_flags & (VM_PFNMAP | VM_MIXEDMAP)) break; - if (vma->vm_end >= end) { - ret = 0; - break; - } - addr = vma->vm_end; } mmap_read_unlock(mm); - return ret; + if (vma) + return -EFAULT; + return 0; } /*