splay tree and red-black tree for vm_map entry lookups.

[Eirik Nygaard]

On Wed, Jan 19, 2005 at 11:12:56AM -0800, Matthew Dillon wrote:
> 
> :>     Lets go with the red-black approach.   I will patch it in and start
> :>     testing it myself.  It looks like NetBSD has done their homework though
> :>     and I expect we will be able to commit it by the end of the week.
> :
> :I did add some code that used the hint, but for some reason it made my computer
> :go crazy at boot, and the login just went dead, could enter a login name but
> :'login:' just poped back out. I am having some trouble seeing why this could go
> :so bad. The hint code is in this patch:
> :http://leaf.dragonflybsd.org/~eirikn/vm_map-rb-tree-netbsd-eirikn-hint.patch
> :
> :-- 
> :Eirik Nygaard
> 
[...]
>     Then the only reason it could possibly fail is if the hint is
>     not being reset back to &map->header (or to some other valid entry)
>     when the entry it represents is deleted.
> 
>     This is occuring because the hint code is depending on
>     vm_map_lookup_entry() to set the hint in the case where the lookup fails,
>     and you removed that part of the code, thus leaving the hint set to
>     the entry you are about to delete.
> 
>     But it was very fragile code anyway.  I recommend just setting the
>     hint unconditionally in vm_map_delete() rather then depending on an
>     undocumented side effect of vm_map_lookup_entry():
> 
>         if (!vm_map_lookup_entry(map, start, &first_entry)) {
>                 entry = first_entry->next;
>                 SAVE_HINT(map, &map->header);	<<<<<< ADDME
>         } else {
>                 entry = first_entry;
>                 vm_map_clip_start(map, entry, start, countp);
>                 /*
>                  * Fix the lookup hint now, rather than each time though the
>                  * loop.
>                  */
>                 SAVE_HINT(map, entry->prev);
>         }

I did the same as vm_map_lookup_entry() did, and the else { } does above and
set the hint one entry back in the list.

> 
>     And while you are at it, get rid of the SAVE_HINT macro junk and just
>     use a direct assignment to map->hint :-)
Sure thing.
> 
>     Test it and then resubmit the whole cleaned up and hinted patch.
Works a lot better now (I can log in and everything).

http://leaf.dragonflybsd.org/~eirikn/vm_map-rb-tree-netbsd-eirikn-hint.patch

-- 
Eirik Nygaard