lkml.org 
[lkml]   [1998]   [Mar]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: Modified floppies can crash Linux (fwd)
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

\
 
 \ /
  Last update: 2005-03-22 13:41    [W:0.012 / U:1.252 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site