On Tue, Feb 02, 2010 at 01:21:55AM +0500, Anton Maksimenkov wrote: > 2010/2/2 Anton Maksimenkov <[email protected]>: > > Overcomplicated using of RB_TREE in uvm_map_lookup_entry() making it > > hard to understand. > > I thinking about drop this RB_TREE out from uvm_map.c or completely > > rewrite using of this RB_TREE. > > Oh, sorry, I mean "in uvm_map_findspace()" of course.
I'm pretty sure that function is bugged: I think it doesn't do wrap-around on the search for an entry. (Should be easily provable, just hint=vm_map_max(map) when entering uvm_map_findspace().) You won't notice in kernel space, since every caller will set hint=vm_map_min(map), but I suspect a number of failed allocations in userspace are actually caused by that. > In uvm_map_lookup_entry() the use of RB_TREE is understandable. Both functions are rather complex. And both functions pre-date random allocation. All this map->hint business has no reason to remain, since random allocation is here to stay and the hint has a high failure rate since then (if it is used, which it usually isn't anyway). The RB_TREE code in uvm_map_findspace is a pretty good solution given the map entry struct. You will need to understand the RB_AUGMENT hack that is only used in this place of the kernel though. Ciao, -- Ariane
