Re: Modified floppies can crash Linux (fwd)

Re: Modified floppies can crash Linux (fwd)

[Colin Plumb]

Something that might be helpful when fixing this:

A very efficient way to detect loops in a chain is to compare each element
chain[i] with chain[j], where j is the largest power of 2 less than i.

E.g.

void
traverse_linked_list(struct linked_list *p)
{
	struct linked_list *bookmark = NULL;
	unsigned counter = 0;

	while (p && p != bookmark) {
		process_node(p);
		counter++;
		if (!(counter & (counter-1))	/* Is counter a power of 2? */
			bookmark = p;
		p = p->next;
	}
	if (p) {
		/* We have processed part of the chain twice, but
		 * at least we can escape the loop.
		 */
		printk("Bad chain, aborting traversal.");
	}
}

Hacking this into kernel code is left as an exercise for the reader...
-- 
	-Colin

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu