DragonFly bugs List (threaded) for 2009-01
DragonFly BSD
DragonFly bugs List (threaded) for 2009-01
[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]

Re: Hammer boot cannot load modules anymore


From: Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxx>
Date: Sat, 10 Jan 2009 14:10:06 -0800 (PST)

:Michael Neumann wrote:
:> hammerread /dev/ad0s1a /boot/modules
:>=20
:> It hits the right boundary ("hit right boundary (52), resetting search =
:
:> to"), and goes into an infinite loop.
:
:ah, good.  could you send me the log so that i can trace what is going wr=
:ong?
:
:thanks
:   simon

    I see some possible issues in hammerread.c.  In the B-Tree search
    code, e.g. starting at around line 439, 'n' and 'e' can get out of
    sync.  For example, if node->count is 0 e can wind up bogus. 

    the while loop here is also bogus. If n == node->count then 'e'
    is invalid at a leaf.  The right hand boundary element AT 
    elm[node->count] only exists for internal nodes, not for leaf
    nodes.

	    // Skip deleted elements
	    while (n <= node->count && e->base.delete_tid != 0) {

    What I recommend is to properly track 'n' through that entire
    bit of code.  So for example, instead of:

	    // unless we stopped right on the left side, we need to back off a bit
	    if (n > 0)
		    e = &node->elms[n - 1];

    You would have:

	    if (n > 0)
		    e = &node->elms[--n];

    Then the if (r > 1) check lower down makes more sense, as the worst
    that can happen is n becomes equal to node->count (and 'e' becomes
    invalid at that point but presumably the rest of the checks would
    take care of it.
    
    Then this bit of code:

        // Skip deleted elements
        while (n <= node->count && e->base.delete_tid != 0) {
                e++;
                n++;
        }

    Should be '<', not '<='.  e being invalid when n == node->count.

        // Skip deleted elements
        while (n < node->count && e->base.delete_tid != 0) {
                e++;
                n++;
        }

    And this bit of code:

	if (n > node->count) {
	    ...
	    hit right boundary 
	}

    should be:

	KKASSERT(n <= node->count);
	if (n == node->count) {
	    ...
	    hit right boundary 
	}

    There may also be an issue on the right boundary code.  What you have
    to do is recurse up the tree, returning to the parent element and then
    moving on to the next parent index.  This recursion can go all the
    way to root if the 'next' index in the parent also hits the right 
    hand boundary.  You exhaust the space in the search when you loop up
    to get the next element in the parent and the parent is root and
    it is already on the right hand boundary, meaning there is no next
    element.

						-Matt





[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]