2010/2/3 Ariane van der Steldt <[email protected]>: > On Tue, Feb 02, 2010 at 01:21:55AM +0500, Anton Maksimenkov wrote: >> uvm_map_lookup_entry()... in uvm_map_findspace()... > > I'm pretty sure that function is bugged: I think it doesn't do > wrap-around on the search for an entry. > > 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.
2010/2/3 Owain Ainsworth <[email protected]>: > On Wed, Feb 03, 2010 at 04:33:50PM +0100, Ariane van der Steldt wrote: >> I'm pretty sure that function is bugged... > Yes. Henning has a bgpd core router where bgpd occasionally dies due to Let me introduce my idea. In fact, we have only two functions in uvm_map.c which make searching in maps. These are uvm_map_lookup_entry() and uvm_map_findspace(). The uvm_map_lookup_entry() do search by address (VA), while uvm_map_findspace() do search by free space. And we have a RB_HEAD(uvm_tree, vm_map_entry) rbhead, which is "indexed by address" (see uvm_compare()). Since that this RB_TREE provide a "searching by address" option to us. This is what the RB_TREE used for. But when we try to use that RB_TREE for track "free space" and to SEARCH by free space we do dirty and ugly things! Then we add a RB_AUGMENT hack (it is so ugly and hard to use right with others that you can't find it anywhere in source tree... exept the uvm_map.c) and other tricks... In the end we got very unclear uvm_map.c code in these places, which is very hard to understand and track, and which is overloaded and overcomplexed by that tricks and crutches. We must stop it, because it keeps hold our hands and brains. We can do things very clear and easy. Let me show how exactly. Let's just add second RB_TREE, which is "indexed by space", let's call it RB_HEAD(uvm_tree_by_space, vm_map_entry) rbhead_by_space, for example. That uvm_tree_by_space will contain vm_map_entry'es sorted by free space. And that uvm_tree_by_space will be used only in uvm_map_findspace() to search for vm_map_entry with needed free space. RB_NFIND() is our best friend here! Simple, reasonable fast, clearly and easy to understand. Actually, since we can have two or more vm_map_entry'es with equal space, so each RB_TREE element will be the list of vm_map_entry'es with that equal space. We can use some additional logic here when we push/pop vm_map_entry from that list we can pop vm_map_entry with smallest start address, for example. Then we must free the first RB_TREE (uvm_tree, "indexed by address") from tracking space/ownspace and other nasty tricks, and stop using it in uvm_map_findspace(). This uvm_tree must be used only in uvm_map_lookup_entry(). Again, RB_NFIND() is our best friend here (of course, in couple with RB_LEFT and other logic, etc). And again, simple, reasonable fast, clearly and easy to understand! And we can (and must) COMPLETELY STOP using RB_AUGMENT hack and forget about it as a bad dream, at last. If we decide that using of RB_TREE at each lookup/findspace is "heavy" when there are little of vm_map_entry'es in map, we can just use linear search in this case. And use RB_FIND/NFIND only when number of vm_map_entry'es will be bigger than some number. We can forget about "hint" and probably drop it's usage here in uvm_map.c (I'll review it later). RB_FIND/RB_NFIND will do their best, especially with "random allocation", especially when there will be many vm_map_entry'es in the map. So in the end. I have some pieces of "patch" in my mind, and I'll create diff with ideas introduced here. If you have any positives and negatives so please, say it here. -- antonvm
