Re: [TEST PATCH 3/3] lib bitmap region restructure

[Paul Mundt <lethal@linux-sh.org>]

On Fri, Jan 20, 2006 at 01:56:43AM -0800, Paul Jackson wrote:
> Ah - I guess my problem is that I believed James code comment:
> 
>  * This is used to allocate a memory region from a bitmap.  The idea is
>  * that the region has to be 1<<order sized and 1<<order aligned (this
>  * makes the search algorithm much faster).
> 
> I thought this meant that it was a design requirement (the "idea")
> to have the alignment always be (1 << order).  Apparently it was
> just a useful performance tweak, for the sub-word sizes.
> 
> Apparently for the multiword case you are adding, you recommend going
> for tighter packing of the allocated regions, rather than extending
> the alignment constraint past a single word.
> 
From a performance point of view going the (1 << order) route for
alignment and searching is much faster. I'm not too tightly bound to the
notion of tightly packing the allocated regions, that was just the
behaviour my implementation was following originally.

Speeding up the searches should take priority for this, though I expect
there's going to be very few corner cases where the search time is of
real relevance (primarily given the fact that it can only handle the <=
BITS_PER_LONG case now).

To give you an example of my use case, I have a 64MB chunk of address
space at a fixed virtual range in the SH-4 processors, which can be
accessed by both the kernel and userspace (unfortunately the address
range is in the mapped peripheral space, which exceeds TASK_SIZE, so
relying even on a custom ->get_unmapped_area() to prep the VMA location
and ->mmap() to setup the mappings simply isn't going to work).

Based off of this, I've got a bitmap for covering this space that both
the kernel and userspace interfaces hook in to to carve up the address
space amongst themselves, and it's not uncommon to map large memory
apertures (32M or so) through this space all at once, particularly in the
case where VRAM is remapped to parallelize with DMA for faster
throughput.

> The performance of bitmap_find_free_region() becomes essentially
> O(N**2) rather than O(Log2 N).  The search loop would scan forward
> with REG_OP_ISFREE from each word in succession, until it found
> the requested sequence of free words, rather than scanning just
> from the words on (1 << order) bits alignment.  Since it looks in
> more places, the worst case times are longer.
> 
Yes, I think given this your patch 3/3 should be mostly fine as is. I've
gotten around to testing it in practice now and everything seems to hold
up. I'll clean up the comments a bit and submit the patch set to Andrew,
who I'm sure is rather tired of hearing about this by now :-)

Attachment: pgpkLftttXeCg.pgp
Description: PGP signature