Re: [RFC PATCH] Add CRC checksum for RCU lists
On Fri, Sep 21, 2007 at 05:32:08PM -0400, Steven Rostedt wrote: > > -- > On Fri, 21 Sep 2007, Paul E. McKenney wrote: > > > On Thu, Sep 20, 2007 at 02:34:11PM -0400, Steven Rostedt wrote: > > > In recent development of the RT kernel, some of our experimental code > > > corrupted the rcu header. But the side effect (crashing) didn't rear its > > > ugly head until way after the fact. Discussing this with Paul, he > > > suggested that RCU should have a "self checking" mechanism to detect > > > these kind of issues. He also suggested putting in a CRC into the > > > rcu_head structure. > > > > > > This patch does so. > > > > Very cool!!! > > Thanks :-) > > > > This patch also takes care to update the crc when rcu_head items are > > > moved from list to list and whenever the next pointer is modified due to > > > addition. > > > > We can only be thankful that it is not possible to cancel outstanding > > RCU callbacks... > > true > > > Looks good -- a few suggestions for better fault coverage interspersed > > below. But would be useful as is. (And it would be good to apply after > > the preempt/boost patches, which are currently undergoing integration > > with the CPU hotplug patches -- the good news is that this integration > > eliminates the need for patch #4!) > > > > Acked-by: Paul E. McKenney <[EMAIL PROTECTED]> > > Thanks, but this is still going to go through changes, from your comments > as well as your latest patches. Good point... > > > Signed-off-by: Steven Rostedt <[EMAIL PROTECTED]> > > > > > > diff --git a/include/linux/rcupdate.h b/include/linux/rcupdate.h > > > index fe17d7d..baca7e6 100644 > > > --- a/include/linux/rcupdate.h > > > +++ b/include/linux/rcupdate.h > > > @@ -50,13 +50,81 @@ > > > struct rcu_head { > > > struct rcu_head *next; > > > void (*func)(struct rcu_head *head); > > > +#ifdef CONFIG_RCU_CRC_HEADER_CHECK > > > + /* > > > + * Checks are made in C files knowing that "next" is > > > + * the first element. So keep it the first element. > > > + */ > > > + unsigned long crc; > > > + void *caller; > > > +#endif > > > }; > > > > Looks good, but one question -- why not include the caller in the CRC? > > Not a big deal either way, but would catch a few more cases of corruption. > > Also, as things stand, the caller pointer can be silently corrupted, > > which might causes confusion if someone had to examine the RCU callback > > lists from a crash dump. > > One reason was that the caller was an addition. I originally didn't have > it, but during my tests, the output was basically useless. It didn't give > any hint to where things went wrong, so I added it. The CRC is to check > the rcu is working, not really the checker itself. > > Note, it helped us out lately with Peter's latest file_table patches in > -rt. With this patch applied, it triggered corruption. That was due to the > union in the fs.h between the llist and rcu_head there was a dependency > in the llist where the rcu_head would not grow. The llist can still do a > spin lock on the lock _after_ the item was added to the call_rcu. Because > of that union, the locking of the lock corrupted the crc. Set it to one. > > You'll see patches from Peter soon to get rid of that dependency. Look forward to seeing them! > > Interchanging the order of "crc" and "caller" would change the strategy, > > if I understand correctly. > > yep. > > > > > > -#define RCU_HEAD_INIT{ .next = NULL, .func = NULL } > > > +#ifdef CONFIG_RCU_CRC_HEADER_CHECK > > > + > > > +#define RCU_CRC_MAGIC 0xC4809168UL > > > > Very magic indeed -- Google doesn't find it, other than in your > > patch. ;-) > > Paul, I'm disappointed in you. That number doesn't ring a bell at all?? > > (hint, ignore the 'C' that was added by me). Well, once Kyle spilled the beans, it was pretty obvious. ;-) Might well be a first!!! > > > +static inline unsigned long rcu_crc_calc(struct rcu_head *head) > > > +{ > > > + unsigned int *p = (unsigned int*)head; /* 32 bit */ > > > + unsigned long crc = RCU_CRC_MAGIC; > > > + > > > + for (p=(void *)head; (void*)p < (void*)>crc; p++) > > > + crc ^= *p; > > > + return crc; > > > +} > > > > Why initialize "p" twice? (Once in the declaration, and once in the > > "for" loop, but with different casts.) > > Why? probably because I was half asleep when writing it ;-) > Will fix. > > > > +static inline void rcu_crc_check(struct rcu_head *head) > > > +{ > > > + static int once; > > > + if (unlikely(head->crc != rcu_crc_calc(head)) && !once) { > > > + once++; > > > > Do we want exactly one (give or take concurrent checks), or do we want > > the first ten or so? Sometimes having a modest sample rather than > > exactly one is helpful. > > I added that because during testing, it would flood the serial console. I > can modify this to whatever deems fit. Perhaps more hits will give a > better clue to what went wrong. I could also just add a print_ratelimit to > it too. Agreed -- using the
Re: [RFC PATCH] Add CRC checksum for RCU lists
On Sat, Sep 22, 2007 at 03:04:47AM -0400, Kyle Moffett wrote: > On Sep 21, 2007, at 17:32:08, Steven Rostedt wrote: > >On Fri, 21 Sep 2007, Paul E. McKenney wrote: > >>On Thu, Sep 20, 2007 at 02:34:11PM -0400, Steven Rostedt wrote: > >>>-#define RCU_HEAD_INIT { .next = NULL, .func = NULL } > >>>+#ifdef CONFIG_RCU_CRC_HEADER_CHECK > >>>+ > >>>+#define RCU_CRC_MAGIC 0xC4809168UL > >> > >>Very magic indeed -- Google doesn't find it, other than in your > >>patch. ;-) > > > >Paul, I'm disappointed in you. That number doesn't ring a bell at > >all?? > > > >(hint, ignore the 'C' that was added by me). > > LOL! The RCU patent number; very clever indeed! Y'know, I newer did figure this one out! I like it!!! ;-) Thanx, Paul - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [RFC PATCH] Add CRC checksum for RCU lists
On Sep 21, 2007, at 17:32:08, Steven Rostedt wrote: On Fri, 21 Sep 2007, Paul E. McKenney wrote: On Thu, Sep 20, 2007 at 02:34:11PM -0400, Steven Rostedt wrote: -#define RCU_HEAD_INIT { .next = NULL, .func = NULL } +#ifdef CONFIG_RCU_CRC_HEADER_CHECK + +#define RCU_CRC_MAGIC 0xC4809168UL Very magic indeed -- Google doesn't find it, other than in your patch. ;-) Paul, I'm disappointed in you. That number doesn't ring a bell at all?? (hint, ignore the 'C' that was added by me). LOL! The RCU patent number; very clever indeed! Cheers, Kyle Moffett - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [RFC PATCH] Add CRC checksum for RCU lists
On Sep 21, 2007, at 17:32:08, Steven Rostedt wrote: On Fri, 21 Sep 2007, Paul E. McKenney wrote: On Thu, Sep 20, 2007 at 02:34:11PM -0400, Steven Rostedt wrote: -#define RCU_HEAD_INIT { .next = NULL, .func = NULL } +#ifdef CONFIG_RCU_CRC_HEADER_CHECK + +#define RCU_CRC_MAGIC 0xC4809168UL Very magic indeed -- Google doesn't find it, other than in your patch. ;-) Paul, I'm disappointed in you. That number doesn't ring a bell at all?? (hint, ignore the 'C' that was added by me). LOL! The RCU patent number; very clever indeed! Cheers, Kyle Moffett - To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [RFC PATCH] Add CRC checksum for RCU lists
On Sat, Sep 22, 2007 at 03:04:47AM -0400, Kyle Moffett wrote: On Sep 21, 2007, at 17:32:08, Steven Rostedt wrote: On Fri, 21 Sep 2007, Paul E. McKenney wrote: On Thu, Sep 20, 2007 at 02:34:11PM -0400, Steven Rostedt wrote: -#define RCU_HEAD_INIT { .next = NULL, .func = NULL } +#ifdef CONFIG_RCU_CRC_HEADER_CHECK + +#define RCU_CRC_MAGIC 0xC4809168UL Very magic indeed -- Google doesn't find it, other than in your patch. ;-) Paul, I'm disappointed in you. That number doesn't ring a bell at all?? (hint, ignore the 'C' that was added by me). LOL! The RCU patent number; very clever indeed! Y'know, I newer did figure this one out! I like it!!! ;-) Thanx, Paul - To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [RFC PATCH] Add CRC checksum for RCU lists
On Fri, Sep 21, 2007 at 05:32:08PM -0400, Steven Rostedt wrote: -- On Fri, 21 Sep 2007, Paul E. McKenney wrote: On Thu, Sep 20, 2007 at 02:34:11PM -0400, Steven Rostedt wrote: In recent development of the RT kernel, some of our experimental code corrupted the rcu header. But the side effect (crashing) didn't rear its ugly head until way after the fact. Discussing this with Paul, he suggested that RCU should have a self checking mechanism to detect these kind of issues. He also suggested putting in a CRC into the rcu_head structure. This patch does so. Very cool!!! Thanks :-) This patch also takes care to update the crc when rcu_head items are moved from list to list and whenever the next pointer is modified due to addition. We can only be thankful that it is not possible to cancel outstanding RCU callbacks... true Looks good -- a few suggestions for better fault coverage interspersed below. But would be useful as is. (And it would be good to apply after the preempt/boost patches, which are currently undergoing integration with the CPU hotplug patches -- the good news is that this integration eliminates the need for patch #4!) Acked-by: Paul E. McKenney [EMAIL PROTECTED] Thanks, but this is still going to go through changes, from your comments as well as your latest patches. Good point... Signed-off-by: Steven Rostedt [EMAIL PROTECTED] diff --git a/include/linux/rcupdate.h b/include/linux/rcupdate.h index fe17d7d..baca7e6 100644 --- a/include/linux/rcupdate.h +++ b/include/linux/rcupdate.h @@ -50,13 +50,81 @@ struct rcu_head { struct rcu_head *next; void (*func)(struct rcu_head *head); +#ifdef CONFIG_RCU_CRC_HEADER_CHECK + /* + * Checks are made in C files knowing that next is + * the first element. So keep it the first element. + */ + unsigned long crc; + void *caller; +#endif }; Looks good, but one question -- why not include the caller in the CRC? Not a big deal either way, but would catch a few more cases of corruption. Also, as things stand, the caller pointer can be silently corrupted, which might causes confusion if someone had to examine the RCU callback lists from a crash dump. One reason was that the caller was an addition. I originally didn't have it, but during my tests, the output was basically useless. It didn't give any hint to where things went wrong, so I added it. The CRC is to check the rcu is working, not really the checker itself. Note, it helped us out lately with Peter's latest file_table patches in -rt. With this patch applied, it triggered corruption. That was due to the union in the fs.h between the llist and rcu_head there was a dependency in the llist where the rcu_head would not grow. The llist can still do a spin lock on the lock _after_ the item was added to the call_rcu. Because of that union, the locking of the lock corrupted the crc. Set it to one. You'll see patches from Peter soon to get rid of that dependency. Look forward to seeing them! Interchanging the order of crc and caller would change the strategy, if I understand correctly. yep. -#define RCU_HEAD_INIT{ .next = NULL, .func = NULL } +#ifdef CONFIG_RCU_CRC_HEADER_CHECK + +#define RCU_CRC_MAGIC 0xC4809168UL Very magic indeed -- Google doesn't find it, other than in your patch. ;-) Paul, I'm disappointed in you. That number doesn't ring a bell at all?? (hint, ignore the 'C' that was added by me). Well, once Kyle spilled the beans, it was pretty obvious. ;-) Might well be a first!!! +static inline unsigned long rcu_crc_calc(struct rcu_head *head) +{ + unsigned int *p = (unsigned int*)head; /* 32 bit */ + unsigned long crc = RCU_CRC_MAGIC; + + for (p=(void *)head; (void*)p (void*)head-crc; p++) + crc ^= *p; + return crc; +} Why initialize p twice? (Once in the declaration, and once in the for loop, but with different casts.) Why? probably because I was half asleep when writing it ;-) Will fix. +static inline void rcu_crc_check(struct rcu_head *head) +{ + static int once; + if (unlikely(head-crc != rcu_crc_calc(head)) !once) { + once++; Do we want exactly one (give or take concurrent checks), or do we want the first ten or so? Sometimes having a modest sample rather than exactly one is helpful. I added that because during testing, it would flood the serial console. I can modify this to whatever deems fit. Perhaps more hits will give a better clue to what went wrong. I could also just add a print_ratelimit to it too. Agreed -- using the already-defined print_ratelimit() sounds much better than reinventing the wheel. And I know that it doesn't matter in this case, but I cannot stop myself from pointing out the possibility of making once be an atomic_t that is initialized to (say) -10, then making the !once
Re: [RFC PATCH] Add CRC checksum for RCU lists
-- On Fri, 21 Sep 2007, Paul E. McKenney wrote: > On Thu, Sep 20, 2007 at 02:34:11PM -0400, Steven Rostedt wrote: > > In recent development of the RT kernel, some of our experimental code > > corrupted the rcu header. But the side effect (crashing) didn't rear its > > ugly head until way after the fact. Discussing this with Paul, he > > suggested that RCU should have a "self checking" mechanism to detect > > these kind of issues. He also suggested putting in a CRC into the > > rcu_head structure. > > > > This patch does so. > > Very cool!!! Thanks :-) > > > This patch also takes care to update the crc when rcu_head items are > > moved from list to list and whenever the next pointer is modified due to > > addition. > > We can only be thankful that it is not possible to cancel outstanding > RCU callbacks... true > Looks good -- a few suggestions for better fault coverage interspersed > below. But would be useful as is. (And it would be good to apply after > the preempt/boost patches, which are currently undergoing integration > with the CPU hotplug patches -- the good news is that this integration > eliminates the need for patch #4!) > > Acked-by: Paul E. McKenney <[EMAIL PROTECTED]> Thanks, but this is still going to go through changes, from your comments as well as your latest patches. > > > Signed-off-by: Steven Rostedt <[EMAIL PROTECTED]> > > > > diff --git a/include/linux/rcupdate.h b/include/linux/rcupdate.h > > index fe17d7d..baca7e6 100644 > > --- a/include/linux/rcupdate.h > > +++ b/include/linux/rcupdate.h > > @@ -50,13 +50,81 @@ > > struct rcu_head { > > struct rcu_head *next; > > void (*func)(struct rcu_head *head); > > +#ifdef CONFIG_RCU_CRC_HEADER_CHECK > > + /* > > +* Checks are made in C files knowing that "next" is > > +* the first element. So keep it the first element. > > +*/ > > + unsigned long crc; > > + void *caller; > > +#endif > > }; > > Looks good, but one question -- why not include the caller in the CRC? > Not a big deal either way, but would catch a few more cases of corruption. > Also, as things stand, the caller pointer can be silently corrupted, > which might causes confusion if someone had to examine the RCU callback > lists from a crash dump. One reason was that the caller was an addition. I originally didn't have it, but during my tests, the output was basically useless. It didn't give any hint to where things went wrong, so I added it. The CRC is to check the rcu is working, not really the checker itself. Note, it helped us out lately with Peter's latest file_table patches in -rt. With this patch applied, it triggered corruption. That was due to the union in the fs.h between the llist and rcu_head there was a dependency in the llist where the rcu_head would not grow. The llist can still do a spin lock on the lock _after_ the item was added to the call_rcu. Because of that union, the locking of the lock corrupted the crc. Set it to one. You'll see patches from Peter soon to get rid of that dependency. > > Interchanging the order of "crc" and "caller" would change the strategy, > if I understand correctly. yep. > > > -#define RCU_HEAD_INIT { .next = NULL, .func = NULL } > > +#ifdef CONFIG_RCU_CRC_HEADER_CHECK > > + > > +#define RCU_CRC_MAGIC 0xC4809168UL > > Very magic indeed -- Google doesn't find it, other than in your > patch. ;-) Paul, I'm disappointed in you. That number doesn't ring a bell at all?? (hint, ignore the 'C' that was added by me). > > > +static inline unsigned long rcu_crc_calc(struct rcu_head *head) > > +{ > > + unsigned int *p = (unsigned int*)head; /* 32 bit */ > > + unsigned long crc = RCU_CRC_MAGIC; > > + > > + for (p=(void *)head; (void*)p < (void*)>crc; p++) > > + crc ^= *p; > > + return crc; > > +} > > Why initialize "p" twice? (Once in the declaration, and once in the > "for" loop, but with different casts.) Why? probably because I was half asleep when writing it ;-) Will fix. > > > +static inline void rcu_crc_check(struct rcu_head *head) > > +{ > > + static int once; > > + if (unlikely(head->crc != rcu_crc_calc(head)) && !once) { > > + once++; > > Do we want exactly one (give or take concurrent checks), or do we want > the first ten or so? Sometimes having a modest sample rather than > exactly one is helpful. I added that because during testing, it would flood the serial console. I can modify this to whatever deems fit. Perhaps more hits will give a better clue to what went wrong. I could also just add a print_ratelimit to it too. > > And I know that it doesn't matter in this case, but I cannot stop myself > from pointing out the possibility of making "once" be an atomic_t > that is initialized to (say) -10, then making the !once check be an > atomic_add_return(). (Whew! Good to get that off my chest!!!) Would you prefer the above or the print_ratelimit? Maybe 10 would be best. I really don't have a preference. > > Now back to real problems. ;-) >
Re: [RFC PATCH] Add CRC checksum for RCU lists
On Thu, Sep 20, 2007 at 02:34:11PM -0400, Steven Rostedt wrote: > In recent development of the RT kernel, some of our experimental code > corrupted the rcu header. But the side effect (crashing) didn't rear its > ugly head until way after the fact. Discussing this with Paul, he > suggested that RCU should have a "self checking" mechanism to detect > these kind of issues. He also suggested putting in a CRC into the > rcu_head structure. > > This patch does so. Very cool!!! > Since there is a bit of overhead with adding this checking, I made it a > config option that would best be turned on for any development that uses > RCU callbacks. > > The way this works is when CRC is configured, two elements are added to > the rcu_head. A crc (long to be consistent, although it only uses a > 32bit value) and a caller. The caller is location of who called the > call_rcu, which is very useful when a corruption does occur. Although, > another item may have corrupted the rcu_head, from my experience (the > crash we had), there are several of the same items that do the call_rcu > together. Good point, having the caller could give a good clue as to which piece of code was mishandling callbacks. > On call_rcu, the checksum is created of the next pointer and the > function to call. The checksum algorithm is simply a XOR of some magic > number with each 4 bytes of the next and func pointer of the rcu_head. > This is then placed into the crc of the rcu_head as well as the return > address. > > Various stages of RCU handling does a checksum of the RCU lists to make > sure that everything is what it expects it to be. Again, this does have > a slight performance impact (although I haven't noticed it with various > tasks, but I'm sure any benchmark will), so should be turned off on > production systems. This is focused on development only. Good approach! > This patch also takes care to update the crc when rcu_head items are > moved from list to list and whenever the next pointer is modified due to > addition. We can only be thankful that it is not possible to cancel outstanding RCU callbacks... > This is against the lastest git (as of this morning) so it does not > include Paul's recent patches for RCU preempt and RCU boost. For this > reason, this is a RFC patch since it would be better to apply this after > those other patches make it upstream. I do have a version of this patch > for the RT kernel that includes Paul's other patches. Looks good -- a few suggestions for better fault coverage interspersed below. But would be useful as is. (And it would be good to apply after the preempt/boost patches, which are currently undergoing integration with the CPU hotplug patches -- the good news is that this integration eliminates the need for patch #4!) Acked-by: Paul E. McKenney <[EMAIL PROTECTED]> > Signed-off-by: Steven Rostedt <[EMAIL PROTECTED]> > > diff --git a/include/linux/rcupdate.h b/include/linux/rcupdate.h > index fe17d7d..baca7e6 100644 > --- a/include/linux/rcupdate.h > +++ b/include/linux/rcupdate.h > @@ -50,13 +50,81 @@ > struct rcu_head { > struct rcu_head *next; > void (*func)(struct rcu_head *head); > +#ifdef CONFIG_RCU_CRC_HEADER_CHECK > + /* > + * Checks are made in C files knowing that "next" is > + * the first element. So keep it the first element. > + */ > + unsigned long crc; > + void *caller; > +#endif > }; Looks good, but one question -- why not include the caller in the CRC? Not a big deal either way, but would catch a few more cases of corruption. Also, as things stand, the caller pointer can be silently corrupted, which might causes confusion if someone had to examine the RCU callback lists from a crash dump. Interchanging the order of "crc" and "caller" would change the strategy, if I understand correctly. > -#define RCU_HEAD_INIT{ .next = NULL, .func = NULL } > +#ifdef CONFIG_RCU_CRC_HEADER_CHECK > + > +#define RCU_CRC_MAGIC 0xC4809168UL Very magic indeed -- Google doesn't find it, other than in your patch. ;-) > +static inline unsigned long rcu_crc_calc(struct rcu_head *head) > +{ > + unsigned int *p = (unsigned int*)head; /* 32 bit */ > + unsigned long crc = RCU_CRC_MAGIC; > + > + for (p=(void *)head; (void*)p < (void*)>crc; p++) > + crc ^= *p; > + return crc; > +} Why initialize "p" twice? (Once in the declaration, and once in the "for" loop, but with different casts.) > +static inline void rcu_crc_check(struct rcu_head *head) > +{ > + static int once; > + if (unlikely(head->crc != rcu_crc_calc(head)) && !once) { > + once++; Do we want exactly one (give or take concurrent checks), or do we want the first ten or so? Sometimes having a modest sample rather than exactly one is helpful. And I know that it doesn't matter in this case, but I cannot stop myself from pointing out the possibility of making "once" be an atomic_t that is initialized to (say) -10, then making the !once
Re: [RFC PATCH] Add CRC checksum for RCU lists
-- > > This has been wondering me some time. Kernel oopses also use [<%p>], > but what really for are two sort of braces needed? I believe the notation of [] has always been a representation of instruction pointer. Seems that's what's used for all outputs of instruction pointers that I've seen (well most really). -- Steve - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [RFC PATCH] Add CRC checksum for RCU lists
On Sep 21 2007 14:02, Peter Zijlstra wrote: >> +if (unlikely(head->crc != rcu_crc_calc(head)) && !once) { >> +once++; >> +printk("BUG: RCU check failed!"); >> +if (head->caller) >> +printk(" (caller=%p)", >> + head->caller); > > char sym[KSYM_SYMBOL_LEN]; > sprint_symbol(sym, head->caller); > printk(" (caller: [<%p>] %s)", head->caller, sym); This has been wondering me some time. Kernel oopses also use [<%p>], but what really for are two sort of braces needed? - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [RFC PATCH] Add CRC checksum for RCU lists
-- On Fri, 21 Sep 2007, Peter Zijlstra wrote: > On Thu, 20 Sep 2007 14:34:11 -0400 Steven Rostedt <[EMAIL PROTECTED]> > wrote: > > > > +static inline void rcu_crc_check(struct rcu_head *head) > > +{ > > + static int once; > > + if (unlikely(head->crc != rcu_crc_calc(head)) && !once) { > > + once++; > > + printk("BUG: RCU check failed!"); > > + if (head->caller) > > + printk(" (caller=%p)", > > + head->caller); > > char sym[KSYM_SYMBOL_LEN]; > sprint_symbol(sym, head->caller); > printk(" (caller: [<%p>] %s)", head->caller, sym); > Yes, good point! Although I may do it this way: printk(" (caller: [<%p>]", head->caller); print_symbol(" %s)\n", (unsigned long)head->caller); and eliminate the temp variable. -- Steve > > + printk("\n"); > > + printk(" CRC was %08lx, expected %08lx\n", > > + head->crc, rcu_crc_calc(head)); > > + printk(" %p %p\n", > > + head->next, head->func); > > + dump_stack(); > > + } > > +} > > - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [RFC PATCH] Add CRC checksum for RCU lists
On Thu, 20 Sep 2007 14:34:11 -0400 Steven Rostedt <[EMAIL PROTECTED]> wrote: > +static inline void rcu_crc_check(struct rcu_head *head) > +{ > + static int once; > + if (unlikely(head->crc != rcu_crc_calc(head)) && !once) { > + once++; > + printk("BUG: RCU check failed!"); > + if (head->caller) > + printk(" (caller=%p)", > +head->caller); char sym[KSYM_SYMBOL_LEN]; sprint_symbol(sym, head->caller); printk(" (caller: [<%p>] %s)", head->caller, sym); > + printk("\n"); > + printk(" CRC was %08lx, expected %08lx\n", > +head->crc, rcu_crc_calc(head)); > + printk(" %p %p\n", > +head->next, head->func); > + dump_stack(); > + } > +} - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [RFC PATCH] Add CRC checksum for RCU lists
On Sep 21 2007 14:02, Peter Zijlstra wrote: +if (unlikely(head-crc != rcu_crc_calc(head)) !once) { +once++; +printk(BUG: RCU check failed!); +if (head-caller) +printk( (caller=%p), + head-caller); char sym[KSYM_SYMBOL_LEN]; sprint_symbol(sym, head-caller); printk( (caller: [%p] %s), head-caller, sym); This has been wondering me some time. Kernel oopses also use [%p], but what really for are two sort of braces needed? - To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [RFC PATCH] Add CRC checksum for RCU lists
-- On Fri, 21 Sep 2007, Peter Zijlstra wrote: On Thu, 20 Sep 2007 14:34:11 -0400 Steven Rostedt [EMAIL PROTECTED] wrote: +static inline void rcu_crc_check(struct rcu_head *head) +{ + static int once; + if (unlikely(head-crc != rcu_crc_calc(head)) !once) { + once++; + printk(BUG: RCU check failed!); + if (head-caller) + printk( (caller=%p), + head-caller); char sym[KSYM_SYMBOL_LEN]; sprint_symbol(sym, head-caller); printk( (caller: [%p] %s), head-caller, sym); Yes, good point! Although I may do it this way: printk( (caller: [%p], head-caller); print_symbol( %s)\n, (unsigned long)head-caller); and eliminate the temp variable. -- Steve + printk(\n); + printk( CRC was %08lx, expected %08lx\n, + head-crc, rcu_crc_calc(head)); + printk( %p %p\n, + head-next, head-func); + dump_stack(); + } +} - To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [RFC PATCH] Add CRC checksum for RCU lists
-- This has been wondering me some time. Kernel oopses also use [%p], but what really for are two sort of braces needed? I believe the notation of [some-hex-number] has always been a representation of instruction pointer. Seems that's what's used for all outputs of instruction pointers that I've seen (well most really). -- Steve - To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [RFC PATCH] Add CRC checksum for RCU lists
On Thu, Sep 20, 2007 at 02:34:11PM -0400, Steven Rostedt wrote: In recent development of the RT kernel, some of our experimental code corrupted the rcu header. But the side effect (crashing) didn't rear its ugly head until way after the fact. Discussing this with Paul, he suggested that RCU should have a self checking mechanism to detect these kind of issues. He also suggested putting in a CRC into the rcu_head structure. This patch does so. Very cool!!! Since there is a bit of overhead with adding this checking, I made it a config option that would best be turned on for any development that uses RCU callbacks. The way this works is when CRC is configured, two elements are added to the rcu_head. A crc (long to be consistent, although it only uses a 32bit value) and a caller. The caller is location of who called the call_rcu, which is very useful when a corruption does occur. Although, another item may have corrupted the rcu_head, from my experience (the crash we had), there are several of the same items that do the call_rcu together. Good point, having the caller could give a good clue as to which piece of code was mishandling callbacks. On call_rcu, the checksum is created of the next pointer and the function to call. The checksum algorithm is simply a XOR of some magic number with each 4 bytes of the next and func pointer of the rcu_head. This is then placed into the crc of the rcu_head as well as the return address. Various stages of RCU handling does a checksum of the RCU lists to make sure that everything is what it expects it to be. Again, this does have a slight performance impact (although I haven't noticed it with various tasks, but I'm sure any benchmark will), so should be turned off on production systems. This is focused on development only. Good approach! This patch also takes care to update the crc when rcu_head items are moved from list to list and whenever the next pointer is modified due to addition. We can only be thankful that it is not possible to cancel outstanding RCU callbacks... This is against the lastest git (as of this morning) so it does not include Paul's recent patches for RCU preempt and RCU boost. For this reason, this is a RFC patch since it would be better to apply this after those other patches make it upstream. I do have a version of this patch for the RT kernel that includes Paul's other patches. Looks good -- a few suggestions for better fault coverage interspersed below. But would be useful as is. (And it would be good to apply after the preempt/boost patches, which are currently undergoing integration with the CPU hotplug patches -- the good news is that this integration eliminates the need for patch #4!) Acked-by: Paul E. McKenney [EMAIL PROTECTED] Signed-off-by: Steven Rostedt [EMAIL PROTECTED] diff --git a/include/linux/rcupdate.h b/include/linux/rcupdate.h index fe17d7d..baca7e6 100644 --- a/include/linux/rcupdate.h +++ b/include/linux/rcupdate.h @@ -50,13 +50,81 @@ struct rcu_head { struct rcu_head *next; void (*func)(struct rcu_head *head); +#ifdef CONFIG_RCU_CRC_HEADER_CHECK + /* + * Checks are made in C files knowing that next is + * the first element. So keep it the first element. + */ + unsigned long crc; + void *caller; +#endif }; Looks good, but one question -- why not include the caller in the CRC? Not a big deal either way, but would catch a few more cases of corruption. Also, as things stand, the caller pointer can be silently corrupted, which might causes confusion if someone had to examine the RCU callback lists from a crash dump. Interchanging the order of crc and caller would change the strategy, if I understand correctly. -#define RCU_HEAD_INIT{ .next = NULL, .func = NULL } +#ifdef CONFIG_RCU_CRC_HEADER_CHECK + +#define RCU_CRC_MAGIC 0xC4809168UL Very magic indeed -- Google doesn't find it, other than in your patch. ;-) +static inline unsigned long rcu_crc_calc(struct rcu_head *head) +{ + unsigned int *p = (unsigned int*)head; /* 32 bit */ + unsigned long crc = RCU_CRC_MAGIC; + + for (p=(void *)head; (void*)p (void*)head-crc; p++) + crc ^= *p; + return crc; +} Why initialize p twice? (Once in the declaration, and once in the for loop, but with different casts.) +static inline void rcu_crc_check(struct rcu_head *head) +{ + static int once; + if (unlikely(head-crc != rcu_crc_calc(head)) !once) { + once++; Do we want exactly one (give or take concurrent checks), or do we want the first ten or so? Sometimes having a modest sample rather than exactly one is helpful. And I know that it doesn't matter in this case, but I cannot stop myself from pointing out the possibility of making once be an atomic_t that is initialized to (say) -10, then making the !once check be an atomic_add_return(). (Whew! Good to get that off my chest!!!) Now back to real
Re: [RFC PATCH] Add CRC checksum for RCU lists
-- On Fri, 21 Sep 2007, Paul E. McKenney wrote: On Thu, Sep 20, 2007 at 02:34:11PM -0400, Steven Rostedt wrote: In recent development of the RT kernel, some of our experimental code corrupted the rcu header. But the side effect (crashing) didn't rear its ugly head until way after the fact. Discussing this with Paul, he suggested that RCU should have a self checking mechanism to detect these kind of issues. He also suggested putting in a CRC into the rcu_head structure. This patch does so. Very cool!!! Thanks :-) This patch also takes care to update the crc when rcu_head items are moved from list to list and whenever the next pointer is modified due to addition. We can only be thankful that it is not possible to cancel outstanding RCU callbacks... true Looks good -- a few suggestions for better fault coverage interspersed below. But would be useful as is. (And it would be good to apply after the preempt/boost patches, which are currently undergoing integration with the CPU hotplug patches -- the good news is that this integration eliminates the need for patch #4!) Acked-by: Paul E. McKenney [EMAIL PROTECTED] Thanks, but this is still going to go through changes, from your comments as well as your latest patches. Signed-off-by: Steven Rostedt [EMAIL PROTECTED] diff --git a/include/linux/rcupdate.h b/include/linux/rcupdate.h index fe17d7d..baca7e6 100644 --- a/include/linux/rcupdate.h +++ b/include/linux/rcupdate.h @@ -50,13 +50,81 @@ struct rcu_head { struct rcu_head *next; void (*func)(struct rcu_head *head); +#ifdef CONFIG_RCU_CRC_HEADER_CHECK + /* +* Checks are made in C files knowing that next is +* the first element. So keep it the first element. +*/ + unsigned long crc; + void *caller; +#endif }; Looks good, but one question -- why not include the caller in the CRC? Not a big deal either way, but would catch a few more cases of corruption. Also, as things stand, the caller pointer can be silently corrupted, which might causes confusion if someone had to examine the RCU callback lists from a crash dump. One reason was that the caller was an addition. I originally didn't have it, but during my tests, the output was basically useless. It didn't give any hint to where things went wrong, so I added it. The CRC is to check the rcu is working, not really the checker itself. Note, it helped us out lately with Peter's latest file_table patches in -rt. With this patch applied, it triggered corruption. That was due to the union in the fs.h between the llist and rcu_head there was a dependency in the llist where the rcu_head would not grow. The llist can still do a spin lock on the lock _after_ the item was added to the call_rcu. Because of that union, the locking of the lock corrupted the crc. Set it to one. You'll see patches from Peter soon to get rid of that dependency. Interchanging the order of crc and caller would change the strategy, if I understand correctly. yep. -#define RCU_HEAD_INIT { .next = NULL, .func = NULL } +#ifdef CONFIG_RCU_CRC_HEADER_CHECK + +#define RCU_CRC_MAGIC 0xC4809168UL Very magic indeed -- Google doesn't find it, other than in your patch. ;-) Paul, I'm disappointed in you. That number doesn't ring a bell at all?? (hint, ignore the 'C' that was added by me). +static inline unsigned long rcu_crc_calc(struct rcu_head *head) +{ + unsigned int *p = (unsigned int*)head; /* 32 bit */ + unsigned long crc = RCU_CRC_MAGIC; + + for (p=(void *)head; (void*)p (void*)head-crc; p++) + crc ^= *p; + return crc; +} Why initialize p twice? (Once in the declaration, and once in the for loop, but with different casts.) Why? probably because I was half asleep when writing it ;-) Will fix. +static inline void rcu_crc_check(struct rcu_head *head) +{ + static int once; + if (unlikely(head-crc != rcu_crc_calc(head)) !once) { + once++; Do we want exactly one (give or take concurrent checks), or do we want the first ten or so? Sometimes having a modest sample rather than exactly one is helpful. I added that because during testing, it would flood the serial console. I can modify this to whatever deems fit. Perhaps more hits will give a better clue to what went wrong. I could also just add a print_ratelimit to it too. And I know that it doesn't matter in this case, but I cannot stop myself from pointing out the possibility of making once be an atomic_t that is initialized to (say) -10, then making the !once check be an atomic_add_return(). (Whew! Good to get that off my chest!!!) Would you prefer the above or the print_ratelimit? Maybe 10 would be best. I really don't have a preference. Now back to real problems. ;-) (Note to self...) The way this is coded could possibly result in false positives. Suppose that the last element in a given callback list has its CRC
[RFC PATCH] Add CRC checksum for RCU lists
In recent development of the RT kernel, some of our experimental code corrupted the rcu header. But the side effect (crashing) didn't rear its ugly head until way after the fact. Discussing this with Paul, he suggested that RCU should have a "self checking" mechanism to detect these kind of issues. He also suggested putting in a CRC into the rcu_head structure. This patch does so. Since there is a bit of overhead with adding this checking, I made it a config option that would best be turned on for any development that uses RCU callbacks. The way this works is when CRC is configured, two elements are added to the rcu_head. A crc (long to be consistent, although it only uses a 32bit value) and a caller. The caller is location of who called the call_rcu, which is very useful when a corruption does occur. Although, another item may have corrupted the rcu_head, from my experience (the crash we had), there are several of the same items that do the call_rcu together. On call_rcu, the checksum is created of the next pointer and the function to call. The checksum algorithm is simply a XOR of some magic number with each 4 bytes of the next and func pointer of the rcu_head. This is then placed into the crc of the rcu_head as well as the return address. Various stages of RCU handling does a checksum of the RCU lists to make sure that everything is what it expects it to be. Again, this does have a slight performance impact (although I haven't noticed it with various tasks, but I'm sure any benchmark will), so should be turned off on production systems. This is focused on development only. This patch also takes care to update the crc when rcu_head items are moved from list to list and whenever the next pointer is modified due to addition. This is against the lastest git (as of this morning) so it does not include Paul's recent patches for RCU preempt and RCU boost. For this reason, this is a RFC patch since it would be better to apply this after those other patches make it upstream. I do have a version of this patch for the RT kernel that includes Paul's other patches. Signed-off-by: Steven Rostedt <[EMAIL PROTECTED]> diff --git a/include/linux/rcupdate.h b/include/linux/rcupdate.h index fe17d7d..baca7e6 100644 --- a/include/linux/rcupdate.h +++ b/include/linux/rcupdate.h @@ -50,13 +50,81 @@ struct rcu_head { struct rcu_head *next; void (*func)(struct rcu_head *head); +#ifdef CONFIG_RCU_CRC_HEADER_CHECK + /* +* Checks are made in C files knowing that "next" is +* the first element. So keep it the first element. +*/ + unsigned long crc; + void *caller; +#endif }; -#define RCU_HEAD_INIT { .next = NULL, .func = NULL } +#ifdef CONFIG_RCU_CRC_HEADER_CHECK + +#define RCU_CRC_MAGIC 0xC4809168UL + +static inline unsigned long rcu_crc_calc(struct rcu_head *head) +{ + unsigned int *p = (unsigned int*)head; /* 32 bit */ + unsigned long crc = RCU_CRC_MAGIC; + + for (p=(void *)head; (void*)p < (void*)>crc; p++) + crc ^= *p; + return crc; +} + +static inline void rcu_crc_check(struct rcu_head *head) +{ + static int once; + if (unlikely(head->crc != rcu_crc_calc(head)) && !once) { + once++; + printk("BUG: RCU check failed!"); + if (head->caller) + printk(" (caller=%p)", + head->caller); + printk("\n"); + printk(" CRC was %08lx, expected %08lx\n", + head->crc, rcu_crc_calc(head)); + printk(" %p %p\n", + head->next, head->func); + dump_stack(); + } +} + +static inline void rcu_assign_crc(struct rcu_head *head) +{ + head->crc = rcu_crc_calc(head); + head->caller = __builtin_return_address(0); +} + +static inline void rcu_check_list(struct rcu_head *head) +{ + int loop; + for (loop = 0; +head != NULL && loop < 100; +head=head->next, loop++) + rcu_crc_check(head); +} + +# define RCU_CRC_INIT , .crc = RCU_CRC_MAGIC +# define RCU_CRC_SET(ptr) (ptr)->crc = RCU_CRC_MAGIC + +#else +# define rcu_crc_calc(head) 0 +# define rcu_crc_check(head) do { } while(0) +# define rcu_assign_crc(head) do { } while(0) +# define rcu_check_list(head) do { } while(0) +# define RCU_CRC_INIT +# define RCU_CRC_SET(ptr) do { } while(0) +#endif /* CONFIG_RCU_CRC_HEADER_CHECK */ + +#define RCU_HEAD_INIT { .next = NULL, .func = NULL RCU_CRC_INIT } #define RCU_HEAD(head) struct rcu_head head = RCU_HEAD_INIT -#define INIT_RCU_HEAD(ptr) do { \ - (ptr)->next = NULL; (ptr)->func = NULL; \ -} while (0) +#define INIT_RCU_HEAD(ptr) do {\ + (ptr)->next = NULL; (ptr)->func = NULL; \ + RCU_CRC_SET(ptr); \ + } while (0) diff --git a/kernel/rcupdate.c b/kernel/rcupdate.c index 2c2dd84..4c3cc9c 100644 ---
[RFC PATCH] Add CRC checksum for RCU lists
In recent development of the RT kernel, some of our experimental code corrupted the rcu header. But the side effect (crashing) didn't rear its ugly head until way after the fact. Discussing this with Paul, he suggested that RCU should have a self checking mechanism to detect these kind of issues. He also suggested putting in a CRC into the rcu_head structure. This patch does so. Since there is a bit of overhead with adding this checking, I made it a config option that would best be turned on for any development that uses RCU callbacks. The way this works is when CRC is configured, two elements are added to the rcu_head. A crc (long to be consistent, although it only uses a 32bit value) and a caller. The caller is location of who called the call_rcu, which is very useful when a corruption does occur. Although, another item may have corrupted the rcu_head, from my experience (the crash we had), there are several of the same items that do the call_rcu together. On call_rcu, the checksum is created of the next pointer and the function to call. The checksum algorithm is simply a XOR of some magic number with each 4 bytes of the next and func pointer of the rcu_head. This is then placed into the crc of the rcu_head as well as the return address. Various stages of RCU handling does a checksum of the RCU lists to make sure that everything is what it expects it to be. Again, this does have a slight performance impact (although I haven't noticed it with various tasks, but I'm sure any benchmark will), so should be turned off on production systems. This is focused on development only. This patch also takes care to update the crc when rcu_head items are moved from list to list and whenever the next pointer is modified due to addition. This is against the lastest git (as of this morning) so it does not include Paul's recent patches for RCU preempt and RCU boost. For this reason, this is a RFC patch since it would be better to apply this after those other patches make it upstream. I do have a version of this patch for the RT kernel that includes Paul's other patches. Signed-off-by: Steven Rostedt [EMAIL PROTECTED] diff --git a/include/linux/rcupdate.h b/include/linux/rcupdate.h index fe17d7d..baca7e6 100644 --- a/include/linux/rcupdate.h +++ b/include/linux/rcupdate.h @@ -50,13 +50,81 @@ struct rcu_head { struct rcu_head *next; void (*func)(struct rcu_head *head); +#ifdef CONFIG_RCU_CRC_HEADER_CHECK + /* +* Checks are made in C files knowing that next is +* the first element. So keep it the first element. +*/ + unsigned long crc; + void *caller; +#endif }; -#define RCU_HEAD_INIT { .next = NULL, .func = NULL } +#ifdef CONFIG_RCU_CRC_HEADER_CHECK + +#define RCU_CRC_MAGIC 0xC4809168UL + +static inline unsigned long rcu_crc_calc(struct rcu_head *head) +{ + unsigned int *p = (unsigned int*)head; /* 32 bit */ + unsigned long crc = RCU_CRC_MAGIC; + + for (p=(void *)head; (void*)p (void*)head-crc; p++) + crc ^= *p; + return crc; +} + +static inline void rcu_crc_check(struct rcu_head *head) +{ + static int once; + if (unlikely(head-crc != rcu_crc_calc(head)) !once) { + once++; + printk(BUG: RCU check failed!); + if (head-caller) + printk( (caller=%p), + head-caller); + printk(\n); + printk( CRC was %08lx, expected %08lx\n, + head-crc, rcu_crc_calc(head)); + printk( %p %p\n, + head-next, head-func); + dump_stack(); + } +} + +static inline void rcu_assign_crc(struct rcu_head *head) +{ + head-crc = rcu_crc_calc(head); + head-caller = __builtin_return_address(0); +} + +static inline void rcu_check_list(struct rcu_head *head) +{ + int loop; + for (loop = 0; +head != NULL loop 100; +head=head-next, loop++) + rcu_crc_check(head); +} + +# define RCU_CRC_INIT , .crc = RCU_CRC_MAGIC +# define RCU_CRC_SET(ptr) (ptr)-crc = RCU_CRC_MAGIC + +#else +# define rcu_crc_calc(head) 0 +# define rcu_crc_check(head) do { } while(0) +# define rcu_assign_crc(head) do { } while(0) +# define rcu_check_list(head) do { } while(0) +# define RCU_CRC_INIT +# define RCU_CRC_SET(ptr) do { } while(0) +#endif /* CONFIG_RCU_CRC_HEADER_CHECK */ + +#define RCU_HEAD_INIT { .next = NULL, .func = NULL RCU_CRC_INIT } #define RCU_HEAD(head) struct rcu_head head = RCU_HEAD_INIT -#define INIT_RCU_HEAD(ptr) do { \ - (ptr)-next = NULL; (ptr)-func = NULL; \ -} while (0) +#define INIT_RCU_HEAD(ptr) do {\ + (ptr)-next = NULL; (ptr)-func = NULL; \ + RCU_CRC_SET(ptr); \ + } while (0) diff --git a/kernel/rcupdate.c b/kernel/rcupdate.c index 2c2dd84..4c3cc9c 100644 --- a/kernel/rcupdate.c +++