|
From: Markus S. <ma...@bl...> - 2008-02-16 09:35:41
|
Hello valgrind developers, I've been studying the source code of valgrind to figure out how it deals with processes and threads. And I'd like to make sure my understanding is correct. From the system call wrappers, I conclude that a fork() (or rather clone) is passed down to the kernel, so that you end up with two processes, both covered by valgrind, but running independently from there on. For threads, there is an internal scheduler, sort of simulating the kernel's scheduler. Having more control over the threads and when to execute or interrupt them. I would like to simulate the scheduler, or even influence it, to be able to reproducibly test execution of concurrent code. Because as commodity hardware gets more and more CPU cores, multi-threaded code will get more and more common. And to be able to test different conditions between threads of execution, I would like to control the scheduler to be able to reproducibly get into a certain state. While that seems doable and just a question of how to control the scheduler, I'm somewhat suspicious about processes. I would like to do the very same for programs that fork, and control interaction of the separate processes. How hard would it be to allow valcore to not pass down the clone call to the kernel, but instead simulate concurrency with its own scheduler? Or maybe still pass on the clone call on to the kernel, but coordinate the scheduling between the valcore processes? And yet another line of thought: being able to control the scheduling between threads and processes, wouldn't it be feasible to even simulate more CPU cores than I really have available, by simply switching after every single instruction? I realize that this would slow down execution a lot. However, it would probably allow to simulate what could happen on a 64-way system on a laptop - at least WRT the CPUs. I hope I made clear what I have in mind. Please feel free to comment, critic, applaud, bash or do all together. Regards Markus |
|
From: Bart V. A. <bar...@gm...> - 2008-02-16 10:43:03
|
On Feb 16, 2008 10:35 AM, Markus Schiltknecht <ma...@bl...> wrote: > I would like to simulate the scheduler, or even influence it, to be able > to reproducibly test execution of concurrent code. Because as commodity > hardware gets more and more CPU cores, multi-threaded code will get more > and more common. And to be able to test different conditions between > threads of execution, I would like to control the scheduler to be able > to reproducibly get into a certain state. This makes me wonder why you would like to do this ? Is it because you want to be able to debug race conditions in concurrent code ? In that case, please have a look at the exp-drd project -- this might be what you are looking for. Note: what you have in mind has already been implemented some time ago, but only for the i386 architecture. Please have a look at the following information in case you are not yet familiar with it: * Michiel Ronsse and Koen De Bosschere, RecPlay: a fully integrated practical record/replay system, ACM Transactions on Computer Systems (TOCS), Volume 17 , Issue 2 (May 1999). See also http://portal.acm.org/citation.cfm?doid=312203.312214 or http://escher.elis.ugent.be/publ/Edocs/DOC/P099_084.pdf. * DIOTA, Dynamic Instrumentation, Optimisation and Transformation of Applications, http://www.elis.ugent.be/diota. Note: I started from Valgrind instead of DIOTA for implementing exp-drd because Valgrind has a more modular design (clear separation between core and tools, and designed such that it is portable to new instruction set architectures). Bart Van Assche. |
|
From: Markus S. <ma...@bl...> - 2008-02-16 12:10:11
|
Hello Bart, Bart Van Assche wrote: > This makes me wonder why you would like to do this ? Is it because you > want to be able to debug race conditions in concurrent code ? In that > case, please have a look at the exp-drd project -- this might be what > you are looking for. Thanks, I've taken a look at that. But I'm more after debugging logical errors, which can occur or not, depending on non-deterministic runtime behavior of parallel programs. > Note: what you have in mind has already been implemented some time > ago, but only for the i386 architecture. Please have a look at the > following information in case you are not yet familiar with it: > * Michiel Ronsse and Koen De Bosschere, RecPlay: a fully integrated > practical record/replay system, ACM Transactions on Computer Systems > (TOCS), Volume 17 , Issue 2 (May 1999). See also > http://portal.acm.org/citation.cfm?doid=312203.312214 or > http://escher.elis.ugent.be/publ/Edocs/DOC/P099_084.pdf. Hm.. looks interesting, but unfortunately I cannot find the full document anywhere. Let alone source code. > * DIOTA, Dynamic Instrumentation, Optimisation and Transformation of > Applications, http://www.elis.ugent.be/diota. Oh, nice, thanks for that pointer. It's record/playback mechanism could help me. Although, that doesn't support multiple processes at all. I've also taken another look at gdb, which can now handle multiple forked processes just perfectly (at least on Linux and HP-UX, it seems). I could automate that so it executes the target program just up to the point where I want full control, then let it execute a single process at a time, just in the order I need it to check for that certain state. However, a gdb solution would be limited to Linux and HP-UX. And it feels a little hackish to use a debugger to control scheduling of the target program. Valgrind feels like the better place to start with. Regards Markus |
|
From: Julian S. <js...@ac...> - 2008-02-16 12:11:05
|
On Saturday 16 February 2008 11:43, Bart Van Assche wrote: > On Feb 16, 2008 10:35 AM, Markus Schiltknecht <ma...@bl...> wrote: > > I would like to simulate the scheduler, or even influence it, to be able > > to reproducibly test execution of concurrent code. Because as commodity > > hardware gets more and more CPU cores, multi-threaded code will get more > > and more common. And to be able to test different conditions between > > threads of execution, I would like to control the scheduler to be able > > to reproducibly get into a certain state. > > This makes me wonder why you would like to do this ? Indeed; it seems a bit pointless to mess with the scheduler. In any case it does not control the order in which threads run -- the kernel does that. It only really ensures that one thread runs at any one time. You'd be better off trying out one of the threading tools in 3.3.0 (Helgrind or Exp-drd). J |
|
From: Markus S. <ma...@bl...> - 2008-02-16 12:40:52
|
Hello Julian,
Julian Seward wrote:
> Indeed; it seems a bit pointless to mess with the scheduler. In
> any case it does not control the order in which threads run --
> the kernel does that. It only really ensures that one thread
> runs at any one time.
Aha, so the valgrind's internal "scheduler" doesn't do the deciding, but
just blocks threads appropriately, right? However, properly blocking,
you could override the kernel's decisions, in a way.
But after a fork, do the two processes still serialize their execution
slots? Or do they run independently?
> You'd be better off trying out one of the threading tools in 3.3.0
> (Helgrind or Exp-drd).
I think those don't serve my needs. First of all, I'm fiddling with
multiple processes, not multiple threads. Second, I'm not after race
conditions on shared memory access, which can be detected automatically.
But I want to check the outcome of a parallel program against an
expected result. That may depend on the scheduling (but should not) as
well as on other events. As bugs triggered by rare scheduling decisions
are very hard to reproduce, I'm looking for something to force uncommon
scheduling.
Favorably even in conjunction with being able to control outside events.
So that I could write expected execution plans, somewhat like:
- after starting, I'm expecting a fork()
- let the parent receive data on a socket
- expect the child to get a signal SIGUSR2
- interrupt the parent
- expect the parent to get back a signal SIGUSR2
- let the parent continue
- expect data packet X from parent via socket
In the scenario above, I let the child do the processing, first, and
only allow the parent to do it's processing after the child finished
(which it signals to the parent). The other extreme variant would be:
- after starting, I'm expecting a fork()
- let the parent receive data on a socket
- expect the child to get a signal SIGUSR2
- interrupt the child
- let the parent process until it waits for the
SIGUSR2 from the child.
- let the child continue
- expect the parent to get back a signal SIGUSR2
- let the parent continue as well
- expect data packet X from parent via socket
Now, this is largely simplified, as it involves only two signals, which
the child and parent use to synchronize. However, in practice, I'm
facing more processes as well as multiple states. I'd like to test every
possible combination thereof.
If you know of a better way to do that, I'd be curious to know, too. But
so far, even when looking for "automated debugging" and things like
that, I didn't find anything close to what I'm looking for.
Regards
Markus
|
|
From: Bart V. A. <bar...@gm...> - 2008-02-16 13:25:25
|
On Feb 16, 2008 1:40 PM, Markus Schiltknecht <ma...@bl...> wrote: > I think those don't serve my needs. First of all, I'm fiddling with > multiple processes, not multiple threads. Second, I'm not after race > conditions on shared memory access, which can be detected automatically. > But I want to check the outcome of a parallel program against an > expected result. That may depend on the scheduling (but should not) as > well as on other events. As bugs triggered by rare scheduling decisions > are very hard to reproduce, I'm looking for something to force uncommon > scheduling. If you want to record and replay the order of events in multiple cooperating processes, you will have to do the following: - Find out which information is exchanged between the threads of a single process and that affects the behavior of a that process, just like exp-drd does. - Find out which information is exchanged between processes that affects the behavior of the group of processes. This can include socket communication, POSIX signals, data read from or written to files, file locking, ... Maybe it's a better idea to implement a daemon process that collects and replays this kind of information at the level of the Valgrind tool than to let the client processes collect and replay this information. As far as I now a record/replay mechanism for groups of processes has not yet been implemented. This looks like an interesting research topic. Bart Van Assche. |
|
From: Nicholas N. <nj...@cs...> - 2008-02-16 20:57:13
|
On Sat, 16 Feb 2008, Markus Schiltknecht wrote: > Aha, so the valgrind's internal "scheduler" doesn't do the deciding, but > just blocks threads appropriately, right? However, properly blocking, > you could override the kernel's decisions, in a way. I guess so. > But after a fork, do the two processes still serialize their execution > slots? Or do they run independently? Independently, as I understand it. > But I want to check the outcome of a parallel program against an > expected result. That may depend on the scheduling (but should not) as > well as on other events. As bugs triggered by rare scheduling decisions > are very hard to reproduce, I'm looking for something to force uncommon > scheduling. Valgrind really only does intra-process simulation/emulation. It seems to me you'd need something that simulates/emulates multiple processes. Maybe a whole system simulator of some kind -- Bochs or SimICS? Nick |
|
From: Markus S. <ma...@bl...> - 2008-02-17 10:08:53
|
Hi, Nicholas Nethercote wrote: > Valgrind really only does intra-process simulation/emulation. It seems > to me you'd need something that simulates/emulates multiple processes. > Maybe a whole system simulator of some kind -- Bochs or SimICS? Yes, I'm partly working with system virtualization for the mentioned testing I'm doing. I prefer qemu or kvm over xen and bochs, but they all offer about the same: they simulate a full system. That's too much and therefore often too complex to setup (you need harddisks, a LiveCD or a root NFS mount, from which your virtual system can start from. All of which are troublesome to setup. And they often require root privileges and are tied to a certain OS). I'm just asking myself: if valgrind can handle multiple threads, why shouldn't it also handle multiple processes? Granted, you'd need to setup some sharded memory or something to be able to do IPC between these valgrind processes. However, what bugs me more is, that there would need to be an interface to valgrind, to control the internal scheduler (to be able to start and stop threads or processes based on some external events). Regards Markus |
|
From: Bart V. A. <bar...@gm...> - 2008-02-17 10:20:00
|
On Feb 17, 2008 11:05 AM, Markus Schiltknecht <ma...@bl...> wrote: > However, what bugs me more is, that there would need to be an interface > to valgrind, to control the internal scheduler (to be able to start and > stop threads or processes based on some external events). I think that it is possible to implement a record/replay tool for multiple processes without modifying the Valgrind scheduler. During the recording phase you can gather information about any event that influences interprocess ordering by intercepting system calls like recv(), send(), sendto(), kill(), ... During the replay phase you can intercept the same system calls and delay their execution in such a way that scheduling during replay matches scheduling during the recording phase. Bart. |
|
From: Markus S. <ma...@bl...> - 2008-02-17 10:38:28
|
Hi,
Bart Van Assche wrote:
> I think that it is possible to implement a record/replay tool for
> multiple processes without modifying the Valgrind scheduler. During
> the recording phase you can gather information about any event that
> influences interprocess ordering by intercepting system calls like
> recv(), send(), sendto(), kill(), ... During the replay phase you can
> intercept the same system calls and delay their execution in such a
> way that scheduling during replay matches scheduling during the
> recording phase.
Hm.. that's a point. But using mainly shared memory for inter process
communication, this won't help, because there's no (or only few) system
calling involved. So the scheduling might very well differ.
I'm also unclear on how easy it would be to "construct" the wanted
situations. Especially if the underlying code changes, so that the
issued system calls suddenly don't match the recorded ones anymore.
But yeah, extending that scheme to not only system calls, but also
events like entering a function or hitting a trace point could help.
Coupled with a loose recording definition, more event based, like:
- after entering function foo execute until syscall signal() is
issued, then interrupt the process (thread) until condition bar
is reached.
These are the kinds of rules which would allow me to specifically test
certain situations which a natural scheduler reaches only very rarely,
but could lead to an error.
Thanks for making me think more about record/replay, looks like I should
investigate somewhat more on what exists in that area.
Regards
Markus
|
|
From: Bart V. A. <bar...@gm...> - 2008-02-17 16:25:04
|
On Feb 17, 2008 11:35 AM, Markus Schiltknecht <ma...@bl...> wrote: > Hm.. that's a point. But using mainly shared memory for inter process > communication, this won't help, because there's no (or only few) system > calling involved. So the scheduling might very well differ. Regarding sharing memory between processes: record/replay techniques for multithreaded processes are well known and have been documented. The challenge with memory that is shared between processes is how to share the recorded event data between the processes. > I'm also unclear on how easy it would be to "construct" the wanted > situations. Especially if the underlying code changes, so that the > issued system calls suddenly don't match the recorded ones anymore. I'm not sure that it is possible to develop record/replay techniques when different binaries are involved during the record and the replay phase. Bart. |