Date:	Thu, 17 Dec 2015 14:31:40 -0800
From:	Doug Anderson <dianders@...omium.org>
To:	Russell King <linux@....linux.org.uk>
Cc:	Tomasz Figa <tfiga@...omium.org>,
	Marek Szyprowski <m.szyprowski@...sung.com>,
	Pawel Osciak <pawel@...iak.com>,
	Dmitry Torokhov <dmitry.torokhov@...il.com>,
	Douglas Anderson <dianders@...omium.org>,
	Will Deacon <will.deacon@....com>,
	Andrew Morton <akpm@...ux-foundation.org>,
	David Rientjes <rientjes@...gle.com>,
	Carlo Caione <carlo@...one.org>,
	Laurent Pinchart <laurent.pinchart+renesas@...asonboard.com>,
	mike.looijmans@...ic.nl, lorenx4@...il.com,
	"linux-arm-kernel@...ts.infradead.org" 
	<linux-arm-kernel@...ts.infradead.org>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH] ARM: dma-mapping: Just allocate one chunk at a time

Hi,

On Thu, Dec 17, 2015 at 12:30 PM, Douglas Anderson
<dianders@...omium.org> wrote:
> The __iommu_alloc_buffer() is expected to be called to allocate pretty
> sizeable buffers.  Upon simple tests of video I saw it trying to
> allocate 4,194,304 bytes.  The function tries to be efficient about this
> by starting out allocating large chunks and then moving to smaller and
> smaller chunk sizes until it succeeds.
>
> The current function is very, very slow.
>
> One problem is the way it keeps trying and trying to allocate big
> chunks.  Imagine a very fragmented memory that has 4M free but no
> contiguous pages at all.  Further imagine allocating 4M (1024 pages).
> We'll do the following memory allocations:
> - For page 1:
>   - Try to allocate order 10 (no retry)
>   - Try to allocate order 9 (no retry)
>   - ...
>   - Try to allocate order 0 (with retry, but not needed)
> - For page 2:
>   - Try to allocate order 9 (no retry)
>   - Try to allocate order 8 (no retry)
>   - ...
>   - Try to allocate order 0 (with retry, but not needed)
> - ...
> - ...
>
> Total number of calls to alloc() calls for this case is:
>   sum(int(math.log(i, 2)) + 1 for i in range(1, 1025))
>   => 9228
>
> The above is obviously worse case, but given how slow alloc can be we
> really want to try to avoid even somewhat bad cases.  I timed the old
> code with a device under memory pressure and it wasn't hard to see it
> take more than 24 seconds to allocate 4 megs of memory (!!).
>
> A second problem (and maybe even more important) is that allocating big
> chunks when we don't need them is just not a good idea anyway.  The
> first thing we do with these big chunks is break them into smaller
> chunks!  If we allocate small chunks:
> - The memory manager doesn't need to work so hard to give us big chunks.
> - We can save the big chunks for those that really need them and this
>   code can make great use of all the small chunks sitting around.
>
> Let's simplify by just allocating one page at a time.  We may make more
> total allocate calls but it works way better.  In real world tests that
> used to sometimes see a 24 second allocation call I can now see at most
> 250 ms.

Off-list I talked to Dmitry about this a little bit and he pointed out
that contiguous chunks actually give a benefit to the IOMMU.  I don't
think the benefit outweighs the cost in this case, but I'm happy to
hear what others have to say.  I did some quick printouts and it turns
out that even when requesting page at a time the memory manager
(unsurprisingly) can in many cases still give us pages that are
contiguous.

Also I'm happy to post up
<https://chromium-review.googlesource.com/#/c/319210/> which sorts the
array and could possibly give us larger chunks of contiguous memory.


-Doug
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists