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

[Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxx>]

:>     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

    Hmm.  This is the bit that was giving you trouble I assume:

    if (map->hint != &map->header) {
	/*
	 * Make a quick check to see if we are already looking at the
	 * entry we ewant (which is usually the case).
	 */
	tmp = map->hint;
	if (address >= tmp->start && address < tmp->end) {
		*entry = tmp;
		return(TRUE);
	}
    }

    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);
        }

    And while you are at it, get rid of the SAVE_HINT macro junk and just
    use a direct assignment to map->hint :-)

    Test it and then resubmit the whole cleaned up and hinted patch.

					-Matt
					Matthew Dillon 
					<dillon@xxxxxxxxxxxxx>