Re: splay tree and red-black tree for vm_map entry lookups.
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
討論串 (同標題文章)
完整討論串 (本文為第 5 之 11 篇)：