[PATCH] drm/mm: revert "Break long searches in fragmented address spaces"

[Chris Wilson]

Quoting Christian König (2020-04-01 08:29:34)
> Am 31.03.20 um 15:19 schrieb Chris Wilson:
> > Quoting Daniel Vetter (2020-03-31 11:38:50)
> >> On Tue, Mar 31, 2020 at 11:20 AM Chris Wilson <chris at chris-wilson.co.uk> wrote:
> >>> Quoting Daniel Vetter (2020-03-31 10:16:18)
> >>>> On Tue, Mar 31, 2020 at 10:59:45AM +0200, Christian König wrote:
> >>>>> A not so gentle ping, since this pretty much broke all TTM based drivers.
> >>>>>
> >>>>> Could we revert this for now?
> >>>> Always ack for revert.
> >>>>
> >>>> Acked-by: Daniel Vetter <daniel.vetter at ffwll.ch>
> >>> So you didn't check the earlier patch either?
> >> I did, but wasn't super sold on the idea of more flags to smack an r-b
> >> onto it, so figured I'll throw the default ack-for-revert on this
> >> meanwhile.
> > We allow userspace to poison the drm_mm at roughly 8K intervals, a
> > search space of 35b with typically O(N^2) behaviour and each node
> > traversal (rb_next/rb_prev) will itself be costly. Even our simple tests
> > can generate a search of several minutes before our patience runs out.o
> > Any drm_mm that allows for userspace to control alignment can be
> > arbitrarily fragmented, hence a raised eyebrow that this search would be
> > allowed in atomic context.
> 
> Wow, that is indeed quite a lot.
> 
> What is the criteria use for ordering the tree? Just the size or is that 
> size+alignment?

The tree is just size. Alignment is a little used parameter, but there's
a requirement for userspace to be able to control it -- although it is
strictly the older interface, it is still open to abuse.

Converting the tree to [size, ffs(addr)] would help for many, but on top
of that we have zones in the drm_mm, so search-in-range can be abused on
top of search-for-alignment.
 
> Never looked into this, but maybe we have a low hanging fruit for an 
> improvement here?

A bit -- alignment is so rarely used in practice, optimising it was not
a concern, just someone else has now noticed the potential for abuse.
They ran a test, get bored and complained that it didn't respond to ^C
for a long period of time and from that derive a proof-of-concept test to
show how it can be used by one client to upset another :|
 
> I'm not 100% sure, but moving away from atomic context wouldn't be that 
> easy.

Fair enough. I would not worry unless the layout is controllable by the
user -- but we probably want some other means of bounding the search.
-Chris