Re: ReBranch - a record-replay debugging tool

Re: ReBranch - a record-replay debugging tool

[Pedro Alves]

On Thursday 09 June 2011 12:57:18, pi3orama@gmail.com wrote:
> Thank you for your advise. I have changed license, added a COPYING file in  
> the code, and added copyright header into every source files.

Thanks a bunch!

One detail.  Files that had been derived from other GPL files
should not lose the original copyright notice.  Of course
you can _add_ a note on your own copyright.  That is, e.g.,
on exception.h|c, I suggest something like:

/* Copyright (C) 1986, 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1996,
   1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
   2009, 2010, 2011 Free Software Foundation, Inc.

   Copyright (C) 2009, 2010, 2011 Nan Wang
 
   This file is part of ReBranch.  Originally based on exceptions.c from GDB.
*/

(there may be other files, I really haven't checked)


Still very much looking forward for a high level outline of ReBranch's
record/replay strategy, and how it differs from GDB's target record. :-)

-- 
Pedro Alves

Re: ReBranch - a record-replay debugging tool

[pi3orama]

I have add GDB's copyright notice back, you can check for it in the git
repository: https://gitorious.org/rebranch

A comparison of GDB record/replay and ReBranch has been added to the
google code site.

A pdf describe the mechanism of ReBranch has been uploaded to the site
and google doc:

http://rebranch.googlecode.com/hg/wiki/rebranch.pdf

https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B1hummTQgSY1NTVhY2FkM2MtZDkxZi00ZDVhLTljNTQtMTZhMjZiMDI3ODZi&hl=en_US

Thank you for your kindly advise.

> On Thursday 09 June 2011 12:57:18, pi3orama@gmail.com wrote:
>> Thank you for your advise. I have changed license, added a COPYING file in  
>> the code, and added copyright header into every source files.
> Thanks a bunch!
>
> One detail.  Files that had been derived from other GPL files
> should not lose the original copyright notice.  Of course
> you can _add_ a note on your own copyright.  That is, e.g.,
> on exception.h|c, I suggest something like:
>
> /* Copyright (C) 1986, 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1996,
>    1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
>    2009, 2010, 2011 Free Software Foundation, Inc.
>
>    Copyright (C) 2009, 2010, 2011 Nan Wang
>  
>    This file is part of ReBranch.  Originally based on exceptions.c from GDB.
> */
>
> (there may be other files, I really haven't checked)
>
>
> Still very much looking forward for a high level outline of ReBranch's
> record/replay strategy, and how it differs from GDB's target record. :-)
>

Re: ReBranch - a record-replay debugging tool

[Joel Brobecker]

> One detail.  Files that had been derived from other GPL files
> should not lose the original copyright notice.  Of course
> you can _add_ a note on your own copyright.  That is, e.g.,
> on exception.h|c, I suggest something like:
> 
> /* Copyright (C) 1986, 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1996,
>    1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
>    2009, 2010, 2011 Free Software Foundation, Inc.
> 
>    Copyright (C) 2009, 2010, 2011 Nan Wang
                                    ^^^^^^^^

If the files are going to be contributed to the GDB project,
I think we'll want the copyright to say FSF, no?

-- 
Joel

Re: ReBranch - a record-replay debugging tool

[Pedro Alves]

On Thursday 09 June 2011 15:36:51, Joel Brobecker wrote:
> > One detail.  Files that had been derived from other GPL files
> > should not lose the original copyright notice.  Of course
> > you can _add_ a note on your own copyright.  That is, e.g.,
> > on exception.h|c, I suggest something like:
> > 
> > /* Copyright (C) 1986, 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1996,
> >    1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
> >    2009, 2010, 2011 Free Software Foundation, Inc.
> > 
> >    Copyright (C) 2009, 2010, 2011 Nan Wang
>                                     ^^^^^^^^
> 
> If the files are going to be contributed to the GDB project,
> I think we'll want the copyright to say FSF, no?

The files in question are heavily modified and repurposed for
ReBranch.  I was under the impression that the tool wanted to
remain a separate project.  But if Nan is planning on assigning
the copyright to the FSF, yes.  Of course, that'd be super cool,
as that way we could import bits into gdb/gdbserver proper
where it would make sense.  (Not that I know which bits would
that be.)  Nan, let us know if that's the case.

-- 
Pedro Alves

Re: ReBranch - a record-replay debugging tool

[pi3orama]

I posted the email to gdb mailing list because:

I want people to know the tool and to use it;
I want developers to be interested in it and help me to improve it, or
even takeover the project (because I won't have enough time to
maintain it).

In my opinion, I want ReBranch to be remain a separate project because
most of ReBranch code is different from gdb, and hard to be integrated
into it (I think). However, currently the gdb replayer itself is a
modified version of gdbserver, the code and replay performance are
both bad (because gdb doesn't support control-flow only debugging
now). If someone can help me to implement it in gdb, then I can remove
the ugly gdbserver patch code from ReBranch, it will be perfect.

About the recording side code, if contribute it to FSF means the
project can be known to and be used by more users, and more developers
can help to improve it, why not to do it?

> On Thu, Jun 9, 2011 at 10:50 PM, Pedro Alves <pedro@codesourcery.com> wrote:
>>
>> On Thursday 09 June 2011 15:36:51, Joel Brobecker wrote:
>> > > One detail.  Files that had been derived from other GPL files
>> > > should not lose the original copyright notice.  Of course
>> > > you can _add_ a note on your own copyright.  That is, e.g.,
>> > > on exception.h|c, I suggest something like:
>> > >
>> > > /* Copyright (C) 1986, 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1996,
>> > >    1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
>> > >    2009, 2010, 2011 Free Software Foundation, Inc.
>> > >
>> > >    Copyright (C) 2009, 2010, 2011 Nan Wang
>> >                                     ^^^^^^^^
>> >
>> > If the files are going to be contributed to the GDB project,
>> > I think we'll want the copyright to say FSF, no?
>>
>> The files in question are heavily modified and repurposed for
>> ReBranch.  I was under the impression that the tool wanted to
>> remain a separate project.  But if Nan is planning on assigning
>> the copyright to the FSF, yes.  Of course, that'd be super cool,
>> as that way we could import bits into gdb/gdbserver proper
>> where it would make sense.  (Not that I know which bits would
>> that be.)  Nan, let us know if that's the case.
>>
>> --
>> Pedro Alves
>

Re: ReBranch - a record-replay debugging tool

[Pedro Alves]

On Thursday 09 June 2011 17:06:44, pi3orama wrote:
> However, currently the gdb replayer itself is a modified version of gdbserver, the code and replay performance are both bad (because gdb doesn't support control-flow only debugging now). If someone can help me to implement it in gdb, then I can remove the ugly gdbserver patch code from ReBranch, it will be perfect.

Can you clarify what do you mean by "control-flow only debugging"?

(Note: I haven't had the time yet to read your document on ReBranch,
so I don't really know how it works or why would you need gdbserver
for replay)

-- 
Pedro Alves

Re: ReBranch - a record-replay debugging tool

[pi3orama]

Yes, you are right.

(P.S:
On the perspective of user processes, all IO interactions are come from
system calls, so for single thread processes, most of the time recording
system calls is enough for data-flow. The only exception I have seen is
vmsplice(): it temporary makes shared memory between 2 processes.)

> Hi,
>
> For data flow, recording syscall is not enough. There may be IO interaction.
> I think your current implementation looks like a PC tracing, replaying tool.
>
> Robert
>
>> From: pi3orama <pi3orama@gmail.com>
>> To: paawan oza <paawan1982@yahoo.com>
>> Date: Fri, 10 Jun 2011 17:34:23 +0800
>> Subject: Re: ReBranch - a record-replay debugging tool
>> In multi-thread situation, nearly all data-flow information is lost
>> because of propagation. However, in single thread situation, signal
>> processing and system call results are all recorded and replayed, all
>> data-flow info can still be restored.
>>
>>> ok got that point.
>>> so in conclusion, any data-flow info which is reponsible for crash may not be
>>> caught by rebranch, or there is a way ?
>>>
>>> Regards,
>>> Oza.

Re: ReBranch - a record-replay debugging tool

[Robert Bu]

Hi,

For data flow, recording syscall is not enough. There may be IO interaction.
I think your current implementation looks like a PC tracing, replaying tool.

Robert

>From: pi3orama <pi3orama@gmail.com>
>To: paawan oza <paawan1982@yahoo.com>
>Date: Fri, 10 Jun 2011 17:34:23 +0800
>Subject: Re: ReBranch - a record-replay debugging tool
>In multi-thread situation, nearly all data-flow information is lost
>because of propagation. However, in single thread situation, signal
>processing and system call results are all recorded and replayed, all
>data-flow info can still be restored.
>
>> ok got that point.
>> so in conclusion, any data-flow info which is reponsible for crash may not be
>> caught by rebranch, or there is a way ?
>>
>> Regards,
>> Oza.

Re: ReBranch - a record-replay debugging tool

[pi3orama]

In multi-thread situation, nearly all data-flow information is lost
because of propagation. However, in single thread situation, signal
processing and system call results are all recorded and replayed, all
data-flow info can still be restored.

> ok got that point.
> so in conclusion, any data-flow info which is reponsible for crash may not be 
> caught by rebranch, or there is a way ?
>
> Regards,
> Oza.
>
>
>
>
> ----- Original Message ----
> From: pi3orama <pi3orama@gmail.com>
> To: paawan oza <paawan1982@yahoo.com>
> Cc: gdb@sourceware.org
> Sent: Fri, June 10, 2011 1:43:11 PM
> Subject: Re: ReBranch - a record-replay debugging tool
>
>
>> data-flow info is not recorded because assumption is: many of the 
>> non-deterministic bugs are control-flow level.
>>
>> so, if you do not have/or minial data-flow info, and if you only set 
>> link/branch 
>>
>> registers and instruction pointers, 
>>
>> then while replaying, do you think that program may not behave as in previous 
>> run because of loss of data flow info. 
>>
>> especially it may not take some of the branches which it previously took.
>>
>> because in you pdf example
>>
>> switch (X)   /* here branch is recorded but not X where X might have been 
>> changed before it, and when you reply it may take different branch */
>>
>> let me know if my thinking is ok in this sense.
>>
>> Regards,
>> Oza.
> ReBranch twists the branch if it goes to different target during replay.
> in my example, if switch statement goes to another case during replay,
> ReBranch will force the control flow back to the one in log. This is
> done by gdbserver patch.
>
>>
>> ----- Original Message ----
>> From: pi3orama <pi3orama@gmail.com>
>> To: paawan oza <paawan1982@yahoo.com>; Nan Wang <pi3orama@gmail.com>
>> Cc: gdb@sourceware.org
>> Sent: Fri, June 10, 2011 7:25:09 AM
>> Subject: Re: Re: ReBranch - a record-replay debugging tool
>>
>> Hi,
>> ReBranch instruments all indirect branch instruction (such as jnz, jmp
>> *0x12345, call *%eax..., and syscall), records their branch targets.
>> For system calls, ReBranch also record their results (for write(),
>> ReBranch records its return value; for read(), ReBranch records its
>> return value as well as the data it retrieves). It also records the
>> result of 'rdtsc'.
>>
>> All instrumentation is done dynamically at runtime -- no recompilation
>> or relinking is required.
>>
>> On , paawan oza <paawan1982@yahoo.com> wrote:
>>> Hi,
>>>
>>>
>>>
>>> Is it something like you do an instrumentation in object code....mostly at
>>> all
>>>
>>> control flows and system calls.
>>>
>>> and record some things.
>>>
>>> so indirectly you do not record every instruction, but you need to modify
>>> object
>>>
>>> code by binary instrumentation.
>>>
>>>
>>>
>>> but what I fail to understand is; what all do you record ?
>>>
>>>
>>>
>>>
>>>
>>> Regards,
>>>
>>> Oza.
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> ----- Original Message ----
>>>
>>> From: Nan Wang pi3orama@gmail.com>
>>>
>>> To: Pedro Alves pedro@codesourcery.com>; gdb@sourceware.org
>>>
>>> Sent: Thu, June 9, 2011 10:09:09 PM
>>>
>>> Subject: Re: ReBranch - a record-replay debugging tool
>>>
>>>
>>>
>>> What I mean "control-flow only debugging" is:
>>>
>>>
>>>
>>> Sometimes user only use GDB's control-flow functions, such as 'c', 'b',
>>>
>>> 'n', 's' ... to watch how the program get to the bug. He or she doesn't
>>>
>>> care the variable name, the memory and some data-flow information.
>>>
>>>
>>>
>>> ReBranch demands "control-flow only debugging" because it only records
>>>
>>> every branch instruction. In current implementation (the modified
>>>
>>> version of gdbserver), the replayer still need to create a process and
>>>
>>> use ptrace to control it. When data-flow have error (caused by data-race
>>>
>>> in multi threading situation), the ptraced process will generate
>>>
>>> segfault for every instructions, which slows down the performance.
>>>
>>>
>>>
>>> ReBranch have a GUI replayer -- ReBranchK -- which is a simple
>>>
>>> control-flow-only debugging tool. ReBranchK doesn't really create the
>>>
>>> process and debug it. It 'executes' the program virtually by reads the
>>>
>>> log and shows corresponding source code. It implements 's', 'b' and 'c'
>>>
>>> command. However, when writing ReBranchK, I found that, without stack
>>>
>>> information, many useful control-flow command such as 'n' and 'bt' are
>>>
>>> hard to be implemented. Therefore, I hope someone help me to put this
>>>
>>> "control-flow only debugging" function into gdbserver.
>>>
>>>> Can you clarify what do you mean by "control-flow only debugging"?
>>>> (Note: I haven't had the time yet to read your document on ReBranch,
>>>> so I don't really know how it works or why would you need gdbserver
>>>> for replay)

Re: ReBranch - a record-replay debugging tool

[paawan oza]

ok got that point.
so in conclusion, any data-flow info which is reponsible for crash may not be 
caught by rebranch, or there is a way ?

Regards,
Oza.




----- Original Message ----
From: pi3orama <pi3orama@gmail.com>
To: paawan oza <paawan1982@yahoo.com>
Cc: gdb@sourceware.org
Sent: Fri, June 10, 2011 1:43:11 PM
Subject: Re: ReBranch - a record-replay debugging tool


> data-flow info is not recorded because assumption is: many of the 
> non-deterministic bugs are control-flow level.
>
> so, if you do not have/or minial data-flow info, and if you only set 
>link/branch 
>
> registers and instruction pointers, 
>
> then while replaying, do you think that program may not behave as in previous 
> run because of loss of data flow info. 
>
> especially it may not take some of the branches which it previously took.
>
> because in you pdf example
>
> switch (X)   /* here branch is recorded but not X where X might have been 
> changed before it, and when you reply it may take different branch */
>
> let me know if my thinking is ok in this sense.
>
> Regards,
> Oza.

ReBranch twists the branch if it goes to different target during replay.
in my example, if switch statement goes to another case during replay,
ReBranch will force the control flow back to the one in log. This is
done by gdbserver patch.

>
>
> ----- Original Message ----
> From: pi3orama <pi3orama@gmail.com>
> To: paawan oza <paawan1982@yahoo.com>; Nan Wang <pi3orama@gmail.com>
> Cc: gdb@sourceware.org
> Sent: Fri, June 10, 2011 7:25:09 AM
> Subject: Re: Re: ReBranch - a record-replay debugging tool
>
> Hi,
> ReBranch instruments all indirect branch instruction (such as jnz, jmp
> *0x12345, call *%eax..., and syscall), records their branch targets.
> For system calls, ReBranch also record their results (for write(),
> ReBranch records its return value; for read(), ReBranch records its
> return value as well as the data it retrieves). It also records the
> result of 'rdtsc'.
>
> All instrumentation is done dynamically at runtime -- no recompilation
> or relinking is required.
>
> On , paawan oza <paawan1982@yahoo.com> wrote:
>> Hi,
>>
>>
>>
>> Is it something like you do an instrumentation in object code....mostly at
>> all
>>
>> control flows and system calls.
>>
>> and record some things.
>>
>> so indirectly you do not record every instruction, but you need to modify
>> object
>>
>> code by binary instrumentation.
>>
>>
>>
>> but what I fail to understand is; what all do you record ?
>>
>>
>>
>>
>>
>> Regards,
>>
>> Oza.
>>
>>
>>
>>
>>
>>
>>
>> ----- Original Message ----
>>
>> From: Nan Wang pi3orama@gmail.com>
>>
>> To: Pedro Alves pedro@codesourcery.com>; gdb@sourceware.org
>>
>> Sent: Thu, June 9, 2011 10:09:09 PM
>>
>> Subject: Re: ReBranch - a record-replay debugging tool
>>
>>
>>
>> What I mean "control-flow only debugging" is:
>>
>>
>>
>> Sometimes user only use GDB's control-flow functions, such as 'c', 'b',
>>
>> 'n', 's' ... to watch how the program get to the bug. He or she doesn't
>>
>> care the variable name, the memory and some data-flow information.
>>
>>
>>
>> ReBranch demands "control-flow only debugging" because it only records
>>
>> every branch instruction. In current implementation (the modified
>>
>> version of gdbserver), the replayer still need to create a process and
>>
>> use ptrace to control it. When data-flow have error (caused by data-race
>>
>> in multi threading situation), the ptraced process will generate
>>
>> segfault for every instructions, which slows down the performance.
>>
>>
>>
>> ReBranch have a GUI replayer -- ReBranchK -- which is a simple
>>
>> control-flow-only debugging tool. ReBranchK doesn't really create the
>>
>> process and debug it. It 'executes' the program virtually by reads the
>>
>> log and shows corresponding source code. It implements 's', 'b' and 'c'
>>
>> command. However, when writing ReBranchK, I found that, without stack
>>
>> information, many useful control-flow command such as 'n' and 'bt' are
>>
>> hard to be implemented. Therefore, I hope someone help me to put this
>>
>> "control-flow only debugging" function into gdbserver.
>>
>>> Can you clarify what do you mean by "control-flow only debugging"?
>>> (Note: I haven't had the time yet to read your document on ReBranch,
>>> so I don't really know how it works or why would you need gdbserver
>>> for replay)
>>

Re: ReBranch - a record-replay debugging tool

[pi3orama]

> data-flow info is not recorded because assumption is: many of the 
> non-deterministic bugs are control-flow level.
>
> so, if you do not have/or minial data-flow info, and if you only set link/branch 
> registers and instruction pointers, 
>
> then while replaying, do you think that program may not behave as in previous 
> run because of loss of data flow info. 
>
> especially it may not take some of the branches which it previously took.
>
> because in you pdf example
>
> switch (X)   /* here branch is recorded but not X where X might have been 
> changed before it, and when you reply it may take different branch */
>
> let me know if my thinking is ok in this sense.
>
> Regards,
> Oza.

ReBranch twists the branch if it goes to different target during replay.
in my example, if switch statement goes to another case during replay,
ReBranch will force the control flow back to the one in log. This is
done by gdbserver patch.

>
>
> ----- Original Message ----
> From: pi3orama <pi3orama@gmail.com>
> To: paawan oza <paawan1982@yahoo.com>; Nan Wang <pi3orama@gmail.com>
> Cc: gdb@sourceware.org
> Sent: Fri, June 10, 2011 7:25:09 AM
> Subject: Re: Re: ReBranch - a record-replay debugging tool
>
> Hi,
> ReBranch instruments all indirect branch instruction (such as jnz, jmp
> *0x12345, call *%eax..., and syscall), records their branch targets.
> For system calls, ReBranch also record their results (for write(),
> ReBranch records its return value; for read(), ReBranch records its
> return value as well as the data it retrieves). It also records the
> result of 'rdtsc'.
>
> All instrumentation is done dynamically at runtime -- no recompilation
> or relinking is required.
>
> On , paawan oza <paawan1982@yahoo.com> wrote:
>> Hi,
>>
>>
>>
>> Is it something like you do an instrumentation in object code....mostly at
>> all
>>
>> control flows and system calls.
>>
>> and record some things.
>>
>> so indirectly you do not record every instruction, but you need to modify
>> object
>>
>> code by binary instrumentation.
>>
>>
>>
>> but what I fail to understand is; what all do you record ?
>>
>>
>>
>>
>>
>> Regards,
>>
>> Oza.
>>
>>
>>
>>
>>
>>
>>
>> ----- Original Message ----
>>
>> From: Nan Wang pi3orama@gmail.com>
>>
>> To: Pedro Alves pedro@codesourcery.com>; gdb@sourceware.org
>>
>> Sent: Thu, June 9, 2011 10:09:09 PM
>>
>> Subject: Re: ReBranch - a record-replay debugging tool
>>
>>
>>
>> What I mean "control-flow only debugging" is:
>>
>>
>>
>> Sometimes user only use GDB's control-flow functions, such as 'c', 'b',
>>
>> 'n', 's' ... to watch how the program get to the bug. He or she doesn't
>>
>> care the variable name, the memory and some data-flow information.
>>
>>
>>
>> ReBranch demands "control-flow only debugging" because it only records
>>
>> every branch instruction. In current implementation (the modified
>>
>> version of gdbserver), the replayer still need to create a process and
>>
>> use ptrace to control it. When data-flow have error (caused by data-race
>>
>> in multi threading situation), the ptraced process will generate
>>
>> segfault for every instructions, which slows down the performance.
>>
>>
>>
>> ReBranch have a GUI replayer -- ReBranchK -- which is a simple
>>
>> control-flow-only debugging tool. ReBranchK doesn't really create the
>>
>> process and debug it. It 'executes' the program virtually by reads the
>>
>> log and shows corresponding source code. It implements 's', 'b' and 'c'
>>
>> command. However, when writing ReBranchK, I found that, without stack
>>
>> information, many useful control-flow command such as 'n' and 'bt' are
>>
>> hard to be implemented. Therefore, I hope someone help me to put this
>>
>> "control-flow only debugging" function into gdbserver.
>>
>>> Can you clarify what do you mean by "control-flow only debugging"?
>>> (Note: I haven't had the time yet to read your document on ReBranch,
>>> so I don't really know how it works or why would you need gdbserver
>>> for replay)
>>

Re: ReBranch - a record-replay debugging tool

[pi3orama]

>> ReBranch demands "control-flow only debugging" because it only records
>> every branch instruction. In current implementation (the modified
>> version of gdbserver), the replayer still need to create a process and
>> use ptrace to control it. When data-flow have error (caused by data-race
>> in multi threading situation), the ptraced process will generate
> IIUC, you have an assumption there that "during record, program runs
> correctly, while during replace, program may run incorrectly",
> otherwise, you can't find the problem by comparing control-flow.
>
> The first half of assumption is OK, but the second half, which is more
> important, might not be.  Some research works are focusing on how to
> expose/trigger non-deterministic program's faults.  Your current
> approach in replaying looks fine, but if you want to find more bugs in
> replay, that might be the way to go.
>

I don't think I have those assumption...

Yes, ReBranch doesn't trigger non-deterministic bugs. In fact it doesn't
know whether the program runs correctly or fault. ReBranch's job is to
faithfully record and replay the execution. If problems raise during
execution, ReBranch allows it to raise again in replay, and allows
developers to look into its control flow. Which converts
non-deterministic bugs into deterministic bugs. Developers can then
replay the program many time to find the bug. Without such a
record/replay tool, developers are hard to do this: when they notice the
bug and apply GDB, the bug will disappear.
>> segfault for every instructions, which slows down the performance.
>>
> I don't understand why "process will generate segfault for every
> instruction"?
>

Nearly every memory accessing instructions will segfault a while after a
new thread creation.

Currently, although all threads can be recorded, ReBranch is unable to
replay them simultaneously. Users can only replay and watch one thread
at a time. Therefore, because of the lost of IPC from shared memory,
sometimes ReBranch have to twist branch because the replayed thread
doesn't have the same data-flow as the original one. The effect can
propagate. For example, during original execution, a thread get a
pointer from another thread, then retrieve some data structure by it,
then do some computation. During replay, it won't get correct pointer
because there's no the other thread, but corresponding branch
instructions are twisted, so it will retrieve data from a invalid
address. A segfault is generated, then ReBranch intercepts it, let the
replay continue. So the following computation will be invalid, force
ReBranch twist more branches. In our experience, the propagate is very
fast. After the return from pthread_create function, the segfault
problem have already heavily slows down the replay speed.

>> ReBranch have a GUI replayer -- ReBranchK -- which is a simple
>> control-flow-only debugging tool. ReBranchK doesn't really create the
>> process and debug it. It 'executes' the program virtually by reads the
>> log and shows corresponding source code. It implements 's', 'b' and 'c'
>> command. However, when writing ReBranchK, I found that, without stack
>> information, many useful control-flow command such as 'n' and 'bt' are
>> hard to be implemented. Therefore, I hope someone help me to put this
>> "control-flow only debugging" function into gdbserver.
> IIUC, you want to put your replayer function into gdbserver, in which,
> record log file, and checkpoints are input.  User can connect to this
> special gdbsever to debug.  Is that correct?

Yes. Especially, I want gdbserver can handle stack frame information to
implement 'n', 'bt' and 'finish' commands.

> Generally speaking, gdbserver supports multiple archs, so is your record
> log file format and checkpoints portable?

I hope they are portable. However, currently checkpoint files and log
files are all platform specific. Checkpoint files contain some CPU
specific information; log files contain some platform specific system
call information.

Re: ReBranch - a record-replay debugging tool

[Yao Qi]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset=GB2312, Size: 2352 bytes --]

On 06/10/2011 12:39 AM, Nan Wang wrote:
> What I mean "control-flow only debugging" is:
> 
> Sometimes user only use GDB's control-flow functions, such as 'c', 'b',
> 'n', 's' ... to watch how the program get to the bug. He or she doesn't
> care the variable name, the memory and some data-flow information.
> 

"control-flow only" is a good idea, and I think that is the reason why
your overhead, both on time and space, is so small.   Good work!

> ReBranch demands "control-flow only debugging" because it only records
> every branch instruction. In current implementation (the modified
> version of gdbserver), the replayer still need to create a process and
> use ptrace to control it. When data-flow have error (caused by data-race
> in multi threading situation), the ptraced process will generate

IIUC, you have an assumption there that "during record, program runs
correctly, while during replace, program may run incorrectly",
otherwise, you can't find the problem by comparing control-flow.

The first half of assumption is OK, but the second half, which is more
important, might not be.  Some research works are focusing on how to
expose/trigger non-deterministic program's faults.  Your current
approach in replaying looks fine, but if you want to find more bugs in
replay, that might be the way to go.

> segfault for every instructions, which slows down the performance.
> 

I don't understand why "process will generate segfault for every
instruction"?

> ReBranch have a GUI replayer -- ReBranchK -- which is a simple
> control-flow-only debugging tool. ReBranchK doesn't really create the
> process and debug it. It 'executes' the program virtually by reads the
> log and shows corresponding source code. It implements 's', 'b' and 'c'
> command. However, when writing ReBranchK, I found that, without stack
> information, many useful control-flow command such as 'n' and 'bt' are
> hard to be implemented. Therefore, I hope someone help me to put this
> "control-flow only debugging" function into gdbserver.

IIUC, you want to put your replayer function into gdbserver, in which,
record log file, and checkpoints are input.  User can connect to this
special gdbsever to debug.  Is that correct?

Generally speaking, gdbserver supports multiple archs, so is your record
log file format and checkpoints portable?

-- 
Yao (ÆëÒ¢)

Re: ReBranch - a record-replay debugging tool

[paawan oza]

Hi,

Is it something like you do an instrumentation in object code....mostly at all 
control flows and system calls.
and record some things.
so indirectly you do not record every instruction, but you need to modify object 
code by binary instrumentation.

but what I fail to understand is; what all do you record ?


Regards,
Oza.



----- Original Message ----
From: Nan Wang <pi3orama@gmail.com>
To: Pedro Alves <pedro@codesourcery.com>; gdb@sourceware.org
Sent: Thu, June 9, 2011 10:09:09 PM
Subject: Re: ReBranch - a record-replay debugging tool

What I mean "control-flow only debugging" is:

Sometimes user only use GDB's control-flow functions, such as 'c', 'b',
'n', 's' ... to watch how the program get to the bug. He or she doesn't
care the variable name, the memory and some data-flow information.

ReBranch demands "control-flow only debugging" because it only records
every branch instruction. In current implementation (the modified
version of gdbserver), the replayer still need to create a process and
use ptrace to control it. When data-flow have error (caused by data-race
in multi threading situation), the ptraced process will generate
segfault for every instructions, which slows down the performance.

ReBranch have a GUI replayer -- ReBranchK -- which is a simple
control-flow-only debugging tool. ReBranchK doesn't really create the
process and debug it. It 'executes' the program virtually by reads the
log and shows corresponding source code. It implements 's', 'b' and 'c'
command. However, when writing ReBranchK, I found that, without stack
information, many useful control-flow command such as 'n' and 'bt' are
hard to be implemented. Therefore, I hope someone help me to put this
"control-flow only debugging" function into gdbserver.
> Can you clarify what do you mean by "control-flow only debugging"?
>
> (Note: I haven't had the time yet to read your document on ReBranch,
> so I don't really know how it works or why would you need gdbserver
> for replay)
>

Re: ReBranch - a record-replay debugging tool

[Nan Wang]

What I mean "control-flow only debugging" is:

Sometimes user only use GDB's control-flow functions, such as 'c', 'b',
'n', 's' ... to watch how the program get to the bug. He or she doesn't
care the variable name, the memory and some data-flow information.

ReBranch demands "control-flow only debugging" because it only records
every branch instruction. In current implementation (the modified
version of gdbserver), the replayer still need to create a process and
use ptrace to control it. When data-flow have error (caused by data-race
in multi threading situation), the ptraced process will generate
segfault for every instructions, which slows down the performance.

ReBranch have a GUI replayer -- ReBranchK -- which is a simple
control-flow-only debugging tool. ReBranchK doesn't really create the
process and debug it. It 'executes' the program virtually by reads the
log and shows corresponding source code. It implements 's', 'b' and 'c'
command. However, when writing ReBranchK, I found that, without stack
information, many useful control-flow command such as 'n' and 'bt' are
hard to be implemented. Therefore, I hope someone help me to put this
"control-flow only debugging" function into gdbserver.
> Can you clarify what do you mean by "control-flow only debugging"?
>
> (Note: I haven't had the time yet to read your document on ReBranch,
> so I don't really know how it works or why would you need gdbserver
> for replay)
>

Re: ReBranch - a record-replay debugging tool

[pi3orama]

I've changed the description in the site.

Only replay phase use gdbserver, recording phase is standalone. In fact,
there is a GUI tool (rebranchk.tcl) which allow users to replay without GDB.

> Hi,
>
> in the site it says:
>
>
> GDB
> The replay is driven by GDB, nearly all GDB commands are useable. 
>
> Do I understand that recording is adopted differently ?
>
> Regards,Oza.
>
>
>
> ________________________________
> From: Pedro Alves <pedro@codesourcery.com>
> To: gdb@sourceware.org
> Cc: pi3orama <pi3orama@gmail.com>
> Sent: Thu, June 9, 2011 2:57:20 PM
> Subject: Re: ReBranch - a record-replay debugging tool
>
> On Thursday 09 June 2011 08:21:47, pi3orama wrote:
>> Hi,
>>
>> I developed a new record-replay tool -- ReBranch
>> (http://code.google.com/p/rebranch/), which focus on debugging
>> non-deterministic bugs. ReBranch can record the outgoing addresses of
>> every branch instructions, and recreate the whole control flow when
>> debugging. I have use it to fix some bugs in real open source projects
>> such as lighttpd and memcached. Unfortunately, few people knows this
>> project at google code, so nearly no one uses it.
> Nice!
>
>> I know that GDB has its own record-replay. However, I still believe
>> ReBranch is useful: ReBranch focus on recording in production systems,
>> its record performance is better than GDB's recording, it can record
>> whole program path (GDB can only record part of it), and most important,
>> ReBranch can be used in multi-threading programs.
> Can you outline ReBranch's record/replay strategy, and how it differs
> from GDB's record?
>
>> I send this mail because I eagerly expect people to use my tool on their
>> developing process, and help me to improve it. And also, I want the
>> replay tool to be more integrated with GDB -- currently ReBranch use a
>> modified gdbserver to do the replay work, however, because ReBranch only
>> records control-flow, the replay performance is far from prefect.
> Since it based on modified gdbserver sources, making it a derivative
> work, it must be GPLv3, right?  I ask because the website says
> MIT license.
>

Re: ReBranch - a record-replay debugging tool

[pi3orama]

Thank you for your advise. I have changed license, added a COPYING file
in the code, and added copyright header into every source files.
> On Thursday 09 June 2011 11:57:45, pi3orama wrote:
>> I used to think that MIT license is compatible with GPLv3. I have
>> changed the license. Sorry for the problem.
> Thanks!   It's compatible, but the GPL requires that the combination 
> is released under the same GNU GPL version.  See:
>
> <http://www.gnu.org/licenses/gpl-faq.html>
>
> Can you also please update your LICENSE file in the sources?  To comply
> with the GPL you need to include a copy of the GPL license -- you'll
> usually find it in a file named COPYING, e.g.,
> see src/gdb/COPYING -- you can simply import that file into
> your tree.
>
> Also, could you please do a general look over the sources and
> make sure not to lose the copyright header and license in files
> based on FSF/GPL's sources?  E.g, your src/host/exception.h and
> src/host/exception.c are obviously based on
> gdb's exceptions.h/exceptions.c.
>
> You seem to have a lot of good stuff here.  Looking forward to
> have you cooperating with the GDB project!
>

Re: ReBranch - a record-replay debugging tool

[Pedro Alves]

On Thursday 09 June 2011 11:57:45, pi3orama wrote:
> I used to think that MIT license is compatible with GPLv3. I have
> changed the license. Sorry for the problem.

Thanks!   It's compatible, but the GPL requires that the combination 
is released under the same GNU GPL version.  See:

<http://www.gnu.org/licenses/gpl-faq.html>

Can you also please update your LICENSE file in the sources?  To comply
with the GPL you need to include a copy of the GPL license -- you'll
usually find it in a file named COPYING, e.g.,
see src/gdb/COPYING -- you can simply import that file into
your tree.

Also, could you please do a general look over the sources and
make sure not to lose the copyright header and license in files
based on FSF/GPL's sources?  E.g, your src/host/exception.h and
src/host/exception.c are obviously based on
gdb's exceptions.h/exceptions.c.

You seem to have a lot of good stuff here.  Looking forward to
have you cooperating with the GDB project!

-- 
Pedro Alves

Re: ReBranch - a record-replay debugging tool

[paawan oza]

Hi,

in the site it says:


GDB
The replay is driven by GDB, nearly all GDB commands are useable. 

Do I understand that recording is adopted differently ?

Regards,Oza.



________________________________
From: Pedro Alves <pedro@codesourcery.com>
To: gdb@sourceware.org
Cc: pi3orama <pi3orama@gmail.com>
Sent: Thu, June 9, 2011 2:57:20 PM
Subject: Re: ReBranch - a record-replay debugging tool

On Thursday 09 June 2011 08:21:47, pi3orama wrote:
> Hi,
> 
> I developed a new record-replay tool -- ReBranch
> (http://code.google.com/p/rebranch/), which focus on debugging
> non-deterministic bugs. ReBranch can record the outgoing addresses of
> every branch instructions, and recreate the whole control flow when
> debugging. I have use it to fix some bugs in real open source projects
> such as lighttpd and memcached. Unfortunately, few people knows this
> project at google code, so nearly no one uses it.

Nice!

> 
> I know that GDB has its own record-replay. However, I still believe
> ReBranch is useful: ReBranch focus on recording in production systems,
> its record performance is better than GDB's recording, it can record
> whole program path (GDB can only record part of it), and most important,
> ReBranch can be used in multi-threading programs.

Can you outline ReBranch's record/replay strategy, and how it differs
from GDB's record?

> I send this mail because I eagerly expect people to use my tool on their
> developing process, and help me to improve it. And also, I want the
> replay tool to be more integrated with GDB -- currently ReBranch use a
> modified gdbserver to do the replay work, however, because ReBranch only
> records control-flow, the replay performance is far from prefect.

Since it based on modified gdbserver sources, making it a derivative
work, it must be GPLv3, right?  I ask because the website says
MIT license.

-- 
Pedro Alves

Re: ReBranch - a record-replay debugging tool

[Pedro Alves]

On Thursday 09 June 2011 08:21:47, pi3orama wrote:
> Hi,
> 
> I developed a new record-replay tool -- ReBranch
> (http://code.google.com/p/rebranch/), which focus on debugging
> non-deterministic bugs. ReBranch can record the outgoing addresses of
> every branch instructions, and recreate the whole control flow when
> debugging. I have use it to fix some bugs in real open source projects
> such as lighttpd and memcached. Unfortunately, few people knows this
> project at google code, so nearly no one uses it.

Nice!

> 
> I know that GDB has its own record-replay. However, I still believe
> ReBranch is useful: ReBranch focus on recording in production systems,
> its record performance is better than GDB's recording, it can record
> whole program path (GDB can only record part of it), and most important,
> ReBranch can be used in multi-threading programs.

Can you outline ReBranch's record/replay strategy, and how it differs
from GDB's record?

> I send this mail because I eagerly expect people to use my tool on their
> developing process, and help me to improve it. And also, I want the
> replay tool to be more integrated with GDB -- currently ReBranch use a
> modified gdbserver to do the replay work, however, because ReBranch only
> records control-flow, the replay performance is far from prefect.

Since it based on modified gdbserver sources, making it a derivative
work, it must be GPLv3, right?  I ask because the website says
MIT license.

-- 
Pedro Alves

ReBranch - a record-replay debugging tool

[pi3orama]

Hi,

I developed a new record-replay tool -- ReBranch
(http://code.google.com/p/rebranch/), which focus on debugging
non-deterministic bugs. ReBranch can record the outgoing addresses of
every branch instructions, and recreate the whole control flow when
debugging. I have use it to fix some bugs in real open source projects
such as lighttpd and memcached. Unfortunately, few people knows this
project at google code, so nearly no one uses it.

I know that GDB has its own record-replay. However, I still believe
ReBranch is useful: ReBranch focus on recording in production systems,
its record performance is better than GDB's recording, it can record
whole program path (GDB can only record part of it), and most important,
ReBranch can be used in multi-threading programs.

I send this mail because I eagerly expect people to use my tool on their
developing process, and help me to improve it. And also, I want the
replay tool to be more integrated with GDB -- currently ReBranch use a
modified gdbserver to do the replay work, however, because ReBranch only
records control-flow, the replay performance is far from prefect.

Any suggestion is welcome. Thank you!