On 03/20/2012 03:00 PM, Andrea Arcangeli wrote:
On Thu, Feb 23, 2012 at 01:56:14PM -0800, Andrew Morton wrote:
We've been playing whack-a-mole with this search for many years. What
about developing a proper data structure with which to locate a
suitable-sized hole in O(log(N)) time?
I intended to implement it a couple of years ago.
It takes a change to the rbtree code so that when rb_erase and
rb_insert_color are called, proper methods are called to notify the
caller that there's been a rotation (probably calling a new
rb_insert_color_with_metadata(&method(left_rot, right_rot)) )
There are two issues here.
1) We also need the ability to search by address, so we can
merge free areas that are adjacent.
2) Hugetlb, shared mappings on architectures with virtually
indexed caches (eg. MIPS) need holes that are not only of
a certain size, but also fit a certain alignment.
To get (2) we are essentially back to tree walking. I am not
convinced that that is a lot better than what we are doing
today, or worth the extra complexity...
--
All rights reversed
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@xxxxxxxxx. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>