|
From: Felix S. <fel...@we...> - 2008-10-28 10:53:59
|
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Dear, does anybody know how to work with threads and valgrind? I try to put a thread back into the synchronization queue? is this possible? can you help me please? Greetings fs_pontix -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (MingW32) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iEYEARECAAYFAkkG7j8ACgkQmH8OAwYoDBnRTQCcC0GnEHzjsCBVTqjwyjFIplNl +DgAnRo8v+1MP7lJ0zuXQa9LGkM7nrnC =k/gu -----END PGP SIGNATURE----- |
|
From: Felix S. <fel...@we...> - 2008-10-28 15:56:39
|
Dear, can I get the range of the addressspace including core, tool and client program? i want to track every line (cache line size) thanks pontix_fs |
|
From: Bart V. A. <bar...@gm...> - 2008-10-28 16:19:42
|
On Tue, Oct 28, 2008 at 4:56 PM, Felix Schmidt <fel...@we...> wrote: > can I get the range of the addressspace including core, tool and > client program? > i want to track every line (cache line size) Something like the information in /proc/self/maps ? Bart. |
|
From: Felix S. <fel...@we...> - 2008-10-28 16:23:16
|
Well, i want to shadow memory. the granularity should be cacheline size Bart Van Assche schrieb: > On Tue, Oct 28, 2008 at 4:56 PM, Felix Schmidt > <fel...@we...> wrote: >> can I get the range of the addressspace including core, tool and >> client program? i want to track every line (cache line size) > > Something like the information in /proc/self/maps ? > > Bart. > |
|
From: Nicholas N. <nj...@cs...> - 2008-10-28 23:16:09
|
On Tue, 28 Oct 2008, Bart Van Assche wrote: > On Tue, Oct 28, 2008 at 4:56 PM, Felix Schmidt <fel...@we...> wrote: >> can I get the range of the addressspace including core, tool and >> client program? >> i want to track every line (cache line size) > > Something like the information in /proc/self/maps ? Run with the -d option. You'll get lots of debugging output, including some "aspacem" lines which show the memory layout at the program's start and end. That might be what you want. Nick |
|
From: Bart V. A. <bar...@gm...> - 2008-10-28 16:21:11
|
On Tue, Oct 28, 2008 at 11:49 AM, Felix Schmidt <fel...@we...> wrote: > does anybody know how to work with threads and valgrind? I try to put > a thread back into the synchronization queue? > is this possible? can you help me please? Valgrind tools are single-threaded, while multithreaded clients are already supported by Valgrind since a very long time. Bart. |
|
From: Felix S. <fel...@we...> - 2008-10-28 16:24:12
|
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 I know that valgrind tools are single threaded, but not the client program! I want to put the client threads back to the queue Bart Van Assche schrieb: > On Tue, Oct 28, 2008 at 11:49 AM, Felix Schmidt > <fel...@we...> wrote: >> does anybody know how to work with threads and valgrind? I try to >> put a thread back into the synchronization queue? is this >> possible? can you help me please? > > Valgrind tools are single-threaded, while multithreaded clients are > already supported by Valgrind since a very long time. > > Bart. > -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (MingW32) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iEYEARECAAYFAkkHPKMACgkQmH8OAwYoDBmDrwCdFZSRvq1Gv1QbHp1JdzL3lhfE jv0An0RvNPJ/lOrWhcb0bj+DlarMoMf9 =Vw8e -----END PGP SIGNATURE----- |
|
From: Julian S. <js...@ac...> - 2008-10-28 16:39:46
|
On Tuesday 28 October 2008, Felix Schmidt wrote: > I know that valgrind tools are single threaded, but not the client > program! > > I want to put the client threads back to the queue What does that mean? I don't understand. J |
|
From: Felix S. <fel...@we...> - 2008-10-28 16:46:56
|
the client program is multithreaded. valgrind serialize the execution of the client program (code) - a thread is running - a hook comes up - the valgrind tool makes a decision, wether the thread can run along or another thread will resume its work how can i tell the valgrind scheduler to stop the current thread and start the next one? fs Julian Seward schrieb: > On Tuesday 28 October 2008, Felix Schmidt wrote: > >> I know that valgrind tools are single threaded, but not the client >> program! >> >> I want to put the client threads back to the queue >> > > What does that mean? I don't understand. > > J > > > |
|
From: Julian S. <js...@ac...> - 2008-10-28 17:01:52
|
On Tuesday 28 October 2008, Felix Schmidt wrote: > the client program is multithreaded. > valgrind serialize the execution of the client program (code) > > - a thread is running > - a hook comes up > - the valgrind tool makes a decision, wether the thread can run along or > another thread will resume its work > > how can i tell the valgrind scheduler to stop the current thread and > start the next one? You can't. The kernel chooses which thread runs next, not Valgrind. The only thing Valgrind does is to guarantee that only one thread runs at once. But it does not make scheduling decisions. J |
|
From: Darryl M. <dar...@ne...> - 2008-10-29 03:45:25
|
Julian Seward wrote:
> On Tuesday 28 October 2008, Felix Schmidt wrote:
>> how can i tell the valgrind scheduler to stop the current thread and
>> start the next one?
>
> You can't. The kernel chooses which thread runs next, not Valgrind.
> The only thing Valgrind does is to guarantee that only one thread
> runs at once. But it does not make scheduling decisions.
If I understand the OPs plight correctly; he wants (like I do) to
hint/instruct valgrind what choice it should make and/or force a
reschedule on demand.
I can see good use for this myself for all modules in VG
(memcheck/helgrind/etc...).
At the bottom of this email is a code representation of such an API.
<helgrind-soap-box-mode>
This would lead into then having a way to notify HelGrind at moments of
interest and regions of memory to check access of. For example when a
threading lock is taken (a mutex) you want to suspend the current thread
(that took the lock) and let every other thread run as far as they can
to try to expose a memory access.
Ideally you'd:
* take the lock
* instruct valgrind explicitly what memory to scrutinize (pointer plus
length with allowed access mode)
* instruct valgrind to keep this thread blocked for a period of time
and let other threads run (in an attempt to violate the memory rules you
defined in the point above)
* then pass control back to this thread, to actually do its work
* then remove the lock (unlock)
* then ask valgrind to examine, summarize and report on that window of
time in relation to this locking scenario.
The problem with not explicitly defining all memory you know you are (or
you might) access during the critical region is that you rely on the
actual bug to occur and a certain about of valgrind reverse engineering.
Where as if I can explicitly mark out the worst case memory access
scenario that this lock is meant to protect (for example the whole
buffer space "char buffer[1024];", as opposed to just the bits it
accessed) and
If I can control thread scheduling to some degree so that I can allow
all other threads to run for a bit I can then write a testcase to
agressively exposed threading bugs in my code.
I have not been able to find HelGrind as-is that useful in supporting
multi-threaded debugging exercises.
</helgrind-soap-box-mode>
Fictitious code representation of such an API:
/* This is an application defined thread scheduler callback function */
int
my_scheduler_implementation(tid_t current_tid, int event, struct
argument_return_data *data) {
if(some_external_flag && event == VG_EVENT_USER1) {
tid_t next_tid = pick_next_tid_by_magic();
/* there maybe other data to pass back to VG */
data->next_tid = next_tid;
return VG_SCHED_RETURN;
}
return VG_SCHED_DEFAULT; /* just let vg do whatever it does by default
for this event type */
}
extern int vg_thread_control(int event, void *event_arg);
/* I demarcate the start of the region of execution where I want some
explicit control over scheduling, this allows vg to init hooks if there
ends up being a speed penalty for using this API */
vg_thread_control(VG_ENABLE_EXPLICT_RESCHED_MODE,
&my_scheduler_implementation);
/* your basic explict switch */
tid_t tid = 12345;
vg_thread_control(VG_SWITCH_TO_THREAD, &tid);
/* your basic attempt to let another thread have the CPU */
vg_thread_control(VG_YIELD);
/* application specific meaning to custom scheduler or treat as yield */
vg_thread_control(VG_EVENT_USER1);
/* I'm done with needing explict control go back to VG default behavor */
vg_thread_control(VG_DISABLE_EXPLICIT_RESHED_MODE);
VG would keep an LRU list of most recently run threads, forcing
switching to a thread puts that thread in control and at the top of the
list. Yeilding CPU from a thread attempts to pass control to the next
thread down the LRU list (than the current thread executing). When it
drops off the bottom of the list VG would do whatever it currently does
now (which is always the scheduler of last resort).
When it drops off the bottom of the list it might pass another event to
my_scheduler_implementation(event=VG_LAST_RESORT) to give it one last
notification.
Then when VGs default scheduler selects the next thread to run there is
also another event simply to notify the custom scheduler this is
happening (for which the return value is ignored).
There are obviously problems with blocked threads being continuously
selected by the custom scheduler to run next. Maybe the custom
scheduler should have access to a thread map showing a list of all
threads, their threadid and their runnable state. If it selects a
blocked/stopped thread for execution this is treated as a "faux-pas"
resulting in VG using its default scheduler to select the next runnable.
Food for though I hope,
Darryl
|
|
From: Julian S. <js...@ac...> - 2008-10-29 11:01:27
|
On Wednesday 29 October 2008, Darryl Miles wrote: [...] I see what you're saying. However ... > Then when VGs default scheduler selects the next thread to run there is > also another event simply to notify the custom scheduler this is > happening (for which the return value is ignored). you still seem to assume that Valgrind has some control over which thread runs next. And it doesn't. A long time ago, in versions prior to 2.2.0, V did do thread scheduling, by running all application threads in one OS-level thread, but those days are long gone. Nowadays, if an application creates N threads running natively, it will have N threads when running on Valgrind too. In that case, Valgrind is somewhat irrelevant. An equivalent problem (it seems to me) is this: for a threaded program running natively, how do you force the Linux kernel to run a thread of your choice next, when there is more than one runnable thread? I don't know how. You can do sys_yield(), but that's only a hint to the kernel; it doesn't _force_ anything to happen. FWIW, the ability to force the kernel to run one specific thread would really make some parts of Helgrind simpler, so it's not like I'm unmotivated to discover how to do so. Regarding Helgrind not finding threading bugs: we have now a pretty good understanding of the various race detection algorithms that have been implemented in the framework (helgrind-3.3, drd, helgrind-3.4, HGDEV branch) and their strengths and weaknesses. If you have some examples of cases where a race has not been detected, and you think it should have been, and you can condense it down to a manageable sized test program, I'd be interested to see it. J |
|
From: Tom H. <to...@co...> - 2008-10-29 11:13:35
|
Julian Seward wrote: > On Wednesday 29 October 2008, Darryl Miles wrote: > [...] > > I see what you're saying. However ... > >> Then when VGs default scheduler selects the next thread to run there is >> also another event simply to notify the custom scheduler this is >> happening (for which the return value is ignored). > > you still seem to assume that Valgrind has some control over which > thread runs next. And it doesn't. A long time ago, in versions prior > to 2.2.0, V did do thread scheduling, by running all application threads > in one OS-level thread, but those days are long gone. Nowadays, if > an application creates N threads running natively, it will have N threads > when running on Valgrind too. True, but we can control which threads are runnable - we already do so to ensure that only one thread runs at once. > In that case, Valgrind is somewhat irrelevant. An equivalent problem > (it seems to me) is this: for a threaded program running natively, > how do you force the Linux kernel to run a thread of your choice > next, when there is more than one runnable thread? I don't know > how. You can do sys_yield(), but that's only a hint to the kernel; > it doesn't _force_ anything to happen. You force it by ensuring that all threads except the one you want to run are blocking on some resource. That way the kernel has no choice about which thread to schedule. I'm not saying it's a good idea to support this at all mind, just that it may well be possible. Tom -- Tom Hughes (to...@co...) http://www.compton.nu/ |
|
From: Darryl M. <dar...@ne...> - 2008-10-29 13:15:31
|
Julian Seward wrote: > On Wednesday 29 October 2008, Darryl Miles wrote: > [...] > > I see what you're saying. However ... > >> Then when VGs default scheduler selects the next thread to run there is >> also another event simply to notify the custom scheduler this is >> happening (for which the return value is ignored). > > you still seem to assume that Valgrind has some control over which > thread runs next. And it doesn't. A long time ago, in versions prior > to 2.2.0, V did do thread scheduling, by running all application threads > in one OS-level thread, but those days are long gone. Nowadays, if > an application creates N threads running natively, it will have N threads > when running on Valgrind too. I had read somewhere that there wasn't concurrent execution of the target executable when run under valgrind but simulated concurrently (ala Uni processor system) I do not know how things are implemented. I also presume that at all times valgrind has control. For example of valgrind needed to execute a kernel call; there is nothing wrong with that even if it blocks. But valgrind must check for some intercept flag when the system call returns. This way conceptually the target executable doesn't see the return from system call just yet and valgrind can block/suspend it internally until that thread is allowed to run again. In relation to restricting CPUs Linux there is: sched_setaffinity(2) I practice I don't want the Linux kernel to run any thread of choice since I'm thinking valgrind would intercept thread creation and thread exit, all system calls, etc... so all these interception points have to do is check for an interrupt flag if its set then a slower path executes to work out who/why/what cause the flow of execution to be interrupted. But you are 100% correct I do not know how valgrind is really implemented in this regard but I agree with Tim it is possible. > Regarding Helgrind not finding threading bugs: we have now a pretty > good understanding of the various race detection algorithms that have > been implemented in the framework (helgrind-3.3, drd, helgrind-3.4, > HGDEV branch) and their strengths and weaknesses. If you have some > examples of cases where a race has not been detected, and you think > it should have been, and you can condense it down to a manageable > sized test program, I'd be interested to see it. Its machine code level threading issues I wish it to find via basic memory access checks. I'm sort of happy I am somewhat proficient with using posix threading primitives and designing modular sub-systems which interact with data in an organized way. So that level of threading problem while nice isn't exactly what I'm trying to use valgrinds view of whats going on to assist me with. The things I would like to use valgrind for is to verify correctness of say a threadpooler and other such specialized multi-threaded code, custom intra-thread interactions not necessarily using pure posix compliant API but sometimes direct assembler calls. I can setup testcases to present specific scenarios and extend the time spent locked. Im some situations it is okay for one thread to write and multiple threads to read the same location. In some situations I'd like VG to report the sequence of memory accesses made in the explicitly described group even if no access rules were no violated. This is so I can prove my test cases are thorough enough to create a specific access pattern that I expect to see. This is sort of like having not just ALLOW_READ, ALLOW_WRITE access mode bits but also REPORT_READ, REPORT_WRITE and TRIGGER_READ, TRIGGER_WRITE meaning that you want a report of the access pattern or not and in the case of trigger if access to these locations would trigger a report on all locations with report set. Maybe it sounds complex but it really isn't. What I can do is audit the memory access of the specific locations I am interested in. This is what valgrind is really good at. I just want to extend that with control of threads too. Darryl |
|
From: tom f. <tf...@al...> - 2008-11-03 03:42:29
|
(Re-send -- only sent to Darryl the first time (oops!))
First, you've pointed out an error in my earlier mail. I definitely
meant `unlock; syscall; lock' in my implementation idea, but got
confused. I mention it inline, but some of the answers above it might
not make sense, so I wanted to clarify up front.
Darryl Miles <dar...@ne...> writes:
> tom fogal wrote:
> > Darryl Miles <dar...@ne...> writes:
> >> tom fogal wrote:
> > It doesn't; I wrote this before I understood your `acquire a
> > VG-internal lock at syscall entry' implementation, and didn't come
> > back and edit.
> >
> > I don't see how that's not a scheduler. Each thread essentially has a
> > valgrind-specific state -- whether or not you'd like it to artifically
> > suspend or not -- and valgrind should choose at various points whether
> > or not to pause or delay the thread based on that information.
>
> System calls would be left to run, i.e. any thread that wanted to jump
> into a system call should be left to do so (T1) but in the act of doing
> this at least one thread that was artificially blocked in user-space (in
> valgrind scheduler code) would be released to run (T2).
yes, but *which* thread? You must somehow choose `T2' from a set of
threads. I call that a scheduler.
> On the return from syscall of that first thread (T1) it would by default
> be intercepted and a simple check made.
[snip]
I still maintain that with the vg_runnable_thread lock, you don't
really need to check anything -- just acquire and release the lock,
let the kernel worry about everything. There doesn't seem to be a
need to check anything in that scheme.
> I'm not averse to calling the valgrind thread management a "scheduler"
> it's just not a parallel scheduler to the one in the kernel,
I did not mean to imply parallel in relation to the kernel.
Originally, I meant parallel with respect to the application, since it
would be possible for two threads of this managed application to be
running this scheduling code at the same time. You wouldn't want
thread A to decide thread B should run, and thread B to decide thread
A to run.
It's a moot point now; the locking-based implementation bypasses the
need for any sort of scheduling logic inside valgrind, and I'm taking
it as a given that you're going to go with that implementation at this
point.
> >> Note that you could then obtain/influence threading control with the
> >> vg_scheduler_pre_client_hook() and the vg_scheduler_post_client_hook().
> >
> > Yes.. but you don't need to. The locks around the syscall already
> > assure you that only one thread can run.
>
[snip]
>
> "The locks around syscalls" I'm not sure on that terminology, I don't
> intend to make syscalls mutually exclusive, far from it. My design
> states the opposite of this.
>
> The terminology I have used was to "intercept" syscalls, i.e. allow vg
> to do something before and after (aka wrapper).
See the next answer, but ...
I never meant to imply these were different. I still don't understand
how what you label a wrapper is different from the `lock around
syscalls' idea. I'm just saying that the wrapper code *will be* a
lock/unlock (err, unlock/lock, see below) -- that is, giving the
implementation instead of the abstract.
> The design I hold up
> for discussion allows all threads to be inside the kernel at the same
> time, we deal with serializing application/client code on the "return
> from syscall". We don't need to serialize kernel calls nor put locks
> around them, I'm not sure where this misunderstanding comes from I don't
> think its from me. That will cause deadlocks.
Ahh, it sounds like you want something more of an `unlock; syscall;
lock' type of implementation. I was being dumb in the earlier mail;
in retrospect, you'd obviously to unlock first and lock after. I
somehow managed to think that my locking scheme would do that, when it
blatantly didn't.
(Case in point -- threads are too hard! ;)
> The mutexes you proposed were there to protect tiny fragments of
> application/client code so that only one thread of application/client
> code was running at any one time. They are not there to do anything in
> relation to syscalls, unfact during syscall entry you'd need to release
> that lock so allow another user-space thread to run. I still cite my
> technique is better and the logical progression after you try your mutex
> approach that way and find out performance sucks to much.
Your technique has no proposed implementation, and a couple of us have
spoken up now saying that having valgrind do scheduling is a big
no-no.
The purpose of using the mutex at every syscall is just to provide a
convenient place to limit the parallelism via this lock. The
alternative is per-instruction, or just per-basic-block, both of which
are likely to give terrible performance.
There's nothing particularly special about syscalls. I just figured
they'd be easy since valgrind already has some smarts for wrapping
them.
> > Well, it doesn't add it to an internal data structure, as far as I
> > know .. just reports it immediately. Yes though, seems like most of
> > the pieces you want are already there.
>
> This is where you STM sounds good, a transaction log (or journal) of all
> access. This
Didn't finish?
> I'm proposing an internal data structure would be added for this
> functionality, I understand it may not currently work that way.
Sure. This is the hash table I think I've brought up once now.
Though thinking about it again, a linked list or an array sounds like
a better data structure, since there is an implied ordering, and
fast random access is not needed/relevant.
Anyway, choice of data structure is your concern, do what you want
<g>.
> > It's just that jumping to timeouts normally means mucking with
> > signals, which I gather is painful in something like valgrind. I
> > could be wrong there.
>
> futex() doesn't use signals, but allows a thread to go to sleep with the
> ability to receive a wakeup-now event.
>
> nanosleep() also allows for a delay. Without use of signals.
>
> alarm() in many version of Unix require the use of signals, of which the
> SIGALRM might be something the application/client is using so needs
> special care.
I think POSIX allows sleep (and probably *sleep) to be implemented via
SIGALRM. Unverified.
> >> Now if ALL code is instrumented under emulation then there may not be a
> >> need to intercept syscalls if we can ensure control is passed back to
> >> valgrind BEFORE application/client code.
> >
> > I don't think this is possible, for the reasons mentioned at the very
> > top of this email -- we can't know when/where a context switch will
> > `jump back to', and the code is already translated at that point.
>
> Ah I don't understand the correlation between needing to know when a
> context switch occurs, ensuring valgrind has CPU control at the time we
> need it to and the instrumentation/translation.
Okay.. here's a quick summary of how /I/ think valgrind works.
Hopefully a valgrind hacker can correct me, at least as is relevant to
this discussion. Say we have this code from a user:
.LCFI2:
movl %edi, -20(%rbp)
movq %rsi, -32(%rbp)
cmpl $2, -20(%rbp)
jne .L2
movl $42, -8(%rbp)
movl $19, -4(%rbp)
Valgrind probably gets this in two chunks, because there's two basic
blocks here (movl through jne, and the two movls). So, upon first
entering the function with these basic blocks, or maybe upon first
loading in this chunk of code, valgrind translates this. I'm not
really sure when/how, but that's not important.
Anyway, this gets changed into VG's VEX instruction set. Then VG adds
instrumentation:
VEX-ish
mov reg edi to argument 1
mov reg esi to argument 3
compare two to argument 3
if flags says they're equal, jump to L2
instrumented VEX:
mov reg edi to argument 1
mov reg esi to argument 3
check shadow bits of argument 3
if flags says they're equal, jump to L2
(i'm skipping the second BB.) finally, VG translates it back to intel
asm:
.LCFI2-modified:
movl %edi, -20(%rbp)
movq %rsi, -32(%rbp)
cmpl $0, $shadow # i've got no clue, but you get the idea
pushl -20(%rbp)
calll vg-invalid-shadow
addl 8, %rsp
cmpl $2, -20(%rbp)
jne .L2
Now, eventually, the CPU starts to execute LCFI2-modified. Say it
gets through the second movq. Then it gets context-switched. Then
the process comes back and starts to compare 0 with the shadow bits.
How can we know we got context switched after the movq and came back
at the compare? There's no notification of this. But what if some
other thread came in and did something which means we don't want this
thread to run anymore? In your original proposal, we'd want to run
some sort of scheduler here. Things don't work that way though --
it's not like we jump to valgrind upon return from a context switch,
and then valgrind jumps into the user code. Rather, the user code is
`valgrindified', and the modified code is what gets executed.
This is why I think of valgrind as more of a JIT than an emulator. It
doesn't really have complete control `all the time' -- it just gets to
control what will happen in the future. That's subtly different, but
very important to the kind of thing you want to do.
That's why I was thinking you might need to add extra instrumentation
around every instruction -- you can't know /where/ a context switch is
going to hit you, and you want to run this little scheduling thing
every time that happens. Even then, you're still screwed, because by
adding instructions to check this.. you need to check between those
instructions too, since they can't check and call the scheduler
atomically.
Thus, I don't currently see how this could possibly work without
having a thread hold an exclusive lock while running application code.
The logical place to grab that lock (to me) is upon return from every
call that valgrind can possibly wrap.
-tom
|
|
From: Felix S. <fel...@we...> - 2008-10-31 13:21:16
|
There is an internal possibility to yield a thread the header pub_core_scheduler.h defines a function called VG_(vg_yield) but i do not find a possibility to include this function to my tool my approach to this problem is: 1) defining a wrapper function maybe in pub_tool_threadstate.h (VG_(yield_thread)) 2) in coregrind/m_threadstate.h i will include pub_core_scheduler.h and implement the function defined in step one 3) the implementation of function (defined in 1) is simple, you have to call VG_(vg_yield)(); what du you think about this approach? fs |
|
From: Nicholas N. <nj...@cs...> - 2008-10-31 21:21:55
|
On Fri, 31 Oct 2008, Felix Schmidt wrote: > There is an internal possibility to yield a thread > > the header pub_core_scheduler.h defines a function called > VG_(vg_yield) but i do not find > a possibility to include this function to my tool > > my approach to this problem is: > > 1) defining a wrapper function maybe in pub_tool_threadstate.h > (VG_(yield_thread)) > 2) in coregrind/m_threadstate.h i will include pub_core_scheduler.h > and implement the function defined in step one > 3) the implementation of function (defined in 1) is simple, you have > to call VG_(vg_yield)(); > > what du you think about this approach? For most modules there is a pub_core_*.h file and a pub_tool_*.h. The latter contains tool-visible things. Over time, lots of things have been moved from a pub_core_*.h file to a pub_tool_*.h file as they've proved useful to tools. In this case, there currently is no pub_tool_scheduler.h. Probably the best thing is to create one, and put VG_(vg_yield)() in it. Nick |
|
From: Julian S. <js...@ac...> - 2008-10-31 22:04:36
|
On Friday 31 October 2008, Nicholas Nethercote wrote: > On Fri, 31 Oct 2008, Felix Schmidt wrote: > > There is an internal possibility to yield a thread > > > > the header pub_core_scheduler.h defines a function called > > VG_(vg_yield) but i do not find > > a possibility to include this function to my tool > > > > my approach to this problem is: > > > > 1) defining a wrapper function maybe in pub_tool_threadstate.h > > (VG_(yield_thread)) > > 2) in coregrind/m_threadstate.h i will include pub_core_scheduler.h > > and implement the function defined in step one > > 3) the implementation of function (defined in 1) is simple, you have > > to call VG_(vg_yield)(); > > > > what du you think about this approach? > > For most modules there is a pub_core_*.h file and a pub_tool_*.h. The > latter contains tool-visible things. Over time, lots of things have been > moved from a pub_core_*.h file to a pub_tool_*.h file as they've proved > useful to tools. > > In this case, there currently is no pub_tool_scheduler.h. Probably the > best thing is to create one, and put VG_(vg_yield)() in it. I don't think this will work as-is. Simply doing sys_yield does not cause the big-lock to be released, so in any case no other thread can run and the kernel will have to reschedule this thread and no other. J |
|
From: Julian S. <js...@ac...> - 2008-10-31 22:04:26
|
> > In that case, Valgrind is somewhat irrelevant. An equivalent problem > > (it seems to me) is this: for a threaded program running natively, > > how do you force the Linux kernel to run a thread of your choice > > next, when there is more than one runnable thread? I don't know > > how. You can do sys_yield(), but that's only a hint to the kernel; > > it doesn't _force_ anything to happen. > > You force it by ensuring that all threads except the one you want to run > are blocking on some resource. That way the kernel has no choice about > which thread to schedule. Yes, I guess so. Although I'm not sure how this could be implemented. The trick with the pipe in sema.c implements a lock well enough, but how does one implement a lock in which (1) the unlocker can control which thread gets the lock next, and (2) that signalling is somehow implied to the kernel, so as to force it to "decide" on our behalf? I'm not sure. Also, deciding ourselves which thread is next to run is dangerous. If we decide to run thread X (and cause all the rest to be blocked), but for some reason that we don't anticipate, the kernel believes X to be blocked, then the system will deadlock. You may remember, a long time ago (in 2.4.0 days) there was at one point a patch (committed, and later removed) which changed the exit order of threads in so that (iirc) the root thread for the process was not allowed to exit until all other threads had exited. This was in order that shell scripts, etc, waiting for the root thread to finish, would be guaranteed that the final error messages, stats, etc, were printed before the root thread exited. But this effectively added inter-thread dependencies which were not present in the original program, and caused complex threaded apps to sometimes deadlock at exit, most notably OpenOffice. As a result of that I'm leery about screwing with thread scheduling at all. IMO we should leave that stuff entirely to the kernel. I think the original poster (Felix) would do well to explain what problem he is trying to solve by scheduling threads himself. Perhaps then we could think of some other solution. J |
|
From: Darryl M. <dar...@ne...> - 2008-11-01 06:34:09
|
Julian Seward wrote: > Yes, I guess so. Although I'm not sure how this could be implemented. > The trick with the pipe in sema.c implements a lock well enough, but how > does one implement a lock in which (1) the unlocker can control which > thread gets the lock next, and (2) that signalling is somehow implied to > the kernel, so as to force it to "decide" on our behalf? I'm not sure. > > Also, deciding ourselves which thread is next to run is dangerous. > If we decide to run thread X (and cause all the rest to be blocked), but > for some reason that we don't anticipate, the kernel believes X to be > blocked, then the system will deadlock. Are you in "user code" or in "kernel code" ? The point I am making is that all system calls must be allowed to run immediately and allowed to block inside the kernel; this means the act of invoking a kernel call must always release/ensure at least one other thread that should be running in "user code" is unblocked to run (just in case this thread blocks inside the kernel). Then on the return from the system call the current thread checks to see if it is still allowed to run, if it is not allowed to run it suspends itself. So at all times where thread runnability is being manipulated (specifically being artificially suspended) we are never in "kernel code" and always in "user code". Following the above rules there is no chance of deadlock that I can see. The deadlock I am referring to is the one where a system call blocks and it was the only thread running in the process and that situation is due to artificial manipulation by valgrind of runability. Where as the applications view of the runtime behavior at that moment is that at least one other thread is runnable (and should be running). There is also the possibility of valgrind creating a thread management thread that always runs, but it would ideally to be hidden to the application. This maybe hard to do. > You may remember, a long time ago (in 2.4.0 days) there was at one point > a patch (committed, and later removed) which changed the exit order of > threads in so that (iirc) the root thread for the process was > not allowed to exit until all other threads had exited. This was in order > that shell scripts, etc, waiting for the root thread to finish, would be > guaranteed that the final error messages, stats, etc, were printed before > the root thread exited. But this effectively added inter-thread dependencies > which were not present in the original program, and caused complex threaded > apps to sometimes deadlock at exit, most notably OpenOffice. Are you sure this patch was only needed due to the way Linux 2.2/2.4/early-2.6 worked with LinuxThreads. i.e. each thread has a unique PID which meant that once the main thread died things could go wrong for waitpid() which shell scripts use in the way you describe. But since NPTL later-2.6 all threads in the process share the PID and only when ALL threads exit does the process exit. I think this also means that the main thread can exit early; but in practice most applications like the concept of a "main thread" to hang everything else off. > As a result of that I'm leery about screwing with thread scheduling at > all. IMO we should leave that stuff entirely to the kernel. > > I think the original poster (Felix) would do well to explain what > problem he is trying to solve by scheduling threads himself. Perhaps > then we could think of some other solution. Yes maybe there is some millage in this too, maybe the Kernel has an API already to do the sort of thread manipulation we are looking for and we just don't know it. That is the ability to control/suspend thread execution/scheduling within a process (possibly itself, possibly another process) but doing so in a way that is not observable to the application. This might have other uses outside debugging but mainly targeted at debugging. One basic idea like this might be for the kernel to send a signal to the process whenever a kernel needs to block (i.e. put the process to sleep). But that signal delivery must be synchronous (i.e. it must occur and complete before that thread is allowed to run again), which I think is pretty much an anti-pattern for the way signals work, they'd have to create as new task runnable state "blocked-pending-synchronous-signal-delivery". Also a sync signal queue might need to take priority over the async signal queue. Then you've got the desire for basic control to hint/force runnability control. In short the above is basically the fictitious API I wrote out (in my previous email to this thread) but implemented in the context of kernel verses userspace (as opposed to application verses valgrind). Where the callback function I defined my_scheduler_implementation() becomes a signal handler and all the vg_thread_control() stuff become system calls. Darryl |
|
From: tom f. <tf...@al...> - 2008-11-01 17:06:10
|
Darryl Miles <dar...@ne...> writes:
> Julian Seward wrote:
> > Yes, I guess so. Although I'm not sure how this could be implemented.
> > The trick with the pipe in sema.c implements a lock well enough, but how
> > does one implement a lock in which (1) the unlocker can control which
> > thread gets the lock next, and (2) that signalling is somehow implied to
> > the kernel, so as to force it to "decide" on our behalf? I'm not sure.
> >
> > Also, deciding ourselves which thread is next to run is dangerous.
> > If we decide to run thread X (and cause all the rest to be blocked), but
> > for some reason that we don't anticipate, the kernel believes X to be
> > blocked, then the system will deadlock.
>
> Are you in "user code" or in "kernel code" ? The point I am making is
> that all system calls must be allowed to run immediately and allowed to
> block inside the kernel; this means the act of invoking a kernel call
> must always release/ensure at least one other thread that should be
> running in "user code" is unblocked to run (just in case this thread
> blocks inside the kernel).
>
> Then on the return from the system call the current thread checks to see
> if it is still allowed to run, if it is not allowed to run it suspends
> itself.
You miss his point. Say we have two threads:
T1 T2
pthread_mutex_lock(&m); pthread_mutex_lock(&m);
ht->add(key, value); ht->remove(key);
pthread_mutex_unlock(&m); pthread_mutex_unlock(&m);
Now say thread 1 acquires the lock. Finally, this logic of valgrind
deciding which thread to run decides (through bug or otherwise) that
thread 2 should run. Both threads are currently paused. Then:
The kernel decides to wake thread 1. Valgrind sees `runnable thread'
!= `current thread', and does a sched_yield(). The kernel decides to
wake thread 1. Valgrind sees `runnable thread' != `current thread',
and does a sched_yield(). The kernel decides to wake thread 1 ...
That was two threads, with one lock. Think of how difficult getting
this right would be for 10 threads and 10 locks -- and that's still a
small program!
The only way I can see to fix this is to have some sort of scheduling
logic inside valgrind itself, which takes into account which threads
hold which locks (or shmem semaphores, or anything else that might
block the app). Julian's argument (correct me if I'm wrong) was that
creating such a scheduling algorithm is going to be extremely
difficult.
[snip -- lots of stuff I'm clueless about]
> That is the ability to control/suspend thread execution/scheduling
> within a process (possibly itself, possibly another process) but doing
> so in a way that is not observable to the application. This might have
> other uses outside debugging but mainly targeted at debugging.
Could you write a wrapper application which fork/execs your chosen
application? This wrapper could use ptrace to start/pause the
application, and you could communicate with it however you choose, or
even just programmatically specify what you'd like.
.. actually, that sounds a lot like gdb, to be honest. Maybe I'm
missing something.
-tom
|
|
From: Darryl M. <dar...@ne...> - 2008-11-01 22:53:16
|
tom fogal wrote:
> Darryl Miles <dar...@ne...> writes:
>> Julian Seward wrote:
>> Then on the return from the system call the current thread checks to see
>> if it is still allowed to run, if it is not allowed to run it suspends
>> itself.
>
> You miss his point. Say we have two threads:
>
> T1 T2
> pthread_mutex_lock(&m); pthread_mutex_lock(&m);
> ht->add(key, value); ht->remove(key);
> pthread_mutex_unlock(&m); pthread_mutex_unlock(&m);
>
> Now say thread 1 acquires the lock. Finally, this logic of valgrind
> deciding which thread to run decides (through bug or otherwise) that
> thread 2 should run. Both threads are currently paused. Then:
>
> The kernel decides to wake thread 1. Valgrind sees `runnable thread'
> != `current thread', and does a sched_yield(). The kernel decides to
> wake thread 1. Valgrind sees `runnable thread' != `current thread',
> and does a sched_yield(). The kernel decides to wake thread 1 ...
Remember my rule: All threads in a kernel system call are running (and
maybe put to asleep inside the kernel if it so wishes). As soon as the
kernel passing back control via system call return you always intercept
with valgrind doing a "Can I still run check? Yes=carry on, No=go to
sleep under valgrind's control".
Why would valgrind keep waking up the wrong thread, it wont do that with
round-robin since it knows that T2 is blocked in the kernel (waiting for
the lock).
As stated in the rules in my previous email the entry point for a
systemcall into the kernel MUST wake up at least one other thread (that
is in user-space) in the process. Well the only other thread in your
situation is T1, so when the futex() syscall is made by T2 (during the
lock) this will implicitly cause T1 to be woken up. T1 may run some
more and in turn call a syscall itself which wakes up another thread,
etc... a cascade. You get a situation where:
* Its possible for ALL threads to be inside a system call (its not
relevant that they are blocking system calls or not, it doesn't matter,
a thread inside a system call is beyond the control of valgrind)
* That zero or one thread is running in user space executing
application/valgrind code at all times. Once you have control down to 1
thread valgrind really has complete control of thread execution of
application/client code from that vantage point. Which was the goal.
* That between zero and process_thread_count-1 threads in userspace
are in a valgrind scheduling queue, waiting to be dispersed. This queue
is in effect an artificial suspension. Anything in the this should be
executing application/client code right now. That is what the
application/client code is expecting to be happening.
So given a walk though of my previous description of the mechanism and
your example scenario do you still see there is a problem ?
We don't actually decide what runs next the kernel still does. Don't
forget all blocking waits happen inside the kernel, for most
applications that are not consuming any CPU they will have all threads
inside a syscall blocking on something. This will remain true in the
scheme I propose.
What we want from valgrind is not strictly the ability to suspend a
thread or force only a certain thread to run. We want the ability to
make the target thread we are monitoring/debugging some threading issue
on to become the LOWEST priority thread to run right after acquiring a
lock/resource.
We then want to attempt/allow all other thread that can run to have a go
until they either block or run out of timeslice(s).
I already artificially do this sort of things in my code when debugging
by doing:
pthread_mutex_lock(&m);
// Artifically enlarge the window when the lock is held
// in an attempt to catch the program out
nanosleep({3,0}, NULL); // its more complex than this due to EINTR
ht->add(key, value);
pthread_mutex_unlock(&m);
What I don't get at the unlock is an audit trail of access to memory I
am interested in. A chronological order of read/write access with
thread_id, pointer to start and length of access. This is what valgrind
does so well.
No one is saying we'd use this mechanism to stop a thread forever, they
are HINTS to the scheduling to lean a particular way during the decision
making process. If there is nothing else to run it doesn't matter what
scheduling algorithm you have, when there is only one thread that can
run, then that thread must run.
struct timeval tv = { 5, 0 };
vg_thread_control(VG_THREAD_YEILD, &tv);
What this might mean is yield my timeslice to any/all other threads (in
preference to us, we/current-thread temporarily adopts a priority of
"absolute last resort", but only for a limited amount of time) in so
doing we don't get passed control for at least 5 seconds, providing
there is some other thread that can run. If there is just no other
thread that can run then we will get back control sooner.
> The only way I can see to fix this is to have some sort of scheduling
> logic inside valgrind itself, which takes into account which threads
> hold which locks (or shmem semaphores, or anything else that might
> block the app). Julian's argument (correct me if I'm wrong) was that
> creating such a scheduling algorithm is going to be extremely
> difficult.
Can we intercept all application/client system calls on a whim ? The
entry points this and other threads use to make system calls we need to
flip to another table. This includes the ability to flip the syscall
exit code of already running threads that are currently blocked in the
kernel. Can that be done ? on a whim, or is there a minor penalty to
memcheck users by leaving some hook in place to allow for it, if so then
a command line option would be needed, since I would not want to see any
penalty when not using this support.
By modifying the exit code (of an already running system call) that
thread will participate in the thread control scheme upon its next
return to user-space.
This is all so that there is zero penalty to valgrind users who do not
use any thread control API.
When I call the:
/* I demarcate the start of the region of execution where I
* want some explicit control over scheduling, this allows
* vg to init hooks if there ends up being a speed penalty
* for using this API
*/
vg_thread_control(VG_ENABLE_EXPLICT_RESCHED_MODE,
&my_scheduler_implementation);
This has the effect of flipping all syscall entry points for all threads.
If threads are in application/client code already can they be
interrupted too ? I'm guessing there must be the equivalent of IPI
inside valgrind http://en.wikipedia.org/wiki/Interprocessor_interrupt
to manage the global emulation state. The emulator has a way be being
interrupted with world events (stuff that affects all threads) and
causes execution of application/client code to stop for a moment while
the interrupt is processed.
>> That is the ability to control/suspend thread execution/scheduling
>> within a process (possibly itself, possibly another process) but doing
>> so in a way that is not observable to the application. This might have
>> other uses outside debugging but mainly targeted at debugging.
>
> Could you write a wrapper application which fork/execs your chosen
> application? This wrapper could use ptrace to start/pause the
> application, and you could communicate with it however you choose, or
> even just programmatically specify what you'd like.
>
> .. actually, that sounds a lot like gdb, to be honest. Maybe I'm
> missing something.
Yes you are missing the part about valgrind being able to audit
read/write memory accesses at asm level in byte granularity. The bit
valgrind does well, gdb can only tell you if the page is valid or not.
Also the part about the application/client code being cooperative and
interactive in the debugging process, i.e. the ability to call functions
that solely exist to communicate with the debugger (ala
vg_thread_control()). This is like dynamic breakpoints/watchpoints
yadda yadda. "Hey look at me debugger, I'm about to do something that
you should be looking at!"
Getting a full audit of all read/write access over your target locations
between arbitrary point A and point B is really what this is all about.
From that information the development can then:
* Create valgrind specific testcases to show up the imperfections of
their design (or target to verify concern).
* Manually see what read/write events took place in relation to their
expected access patterns. Half the battle with debugging multi-threaded
application is just that you can not see what is going on.
Darryl
|
|
From: Julian S. <js...@ac...> - 2008-11-01 23:49:30
|
> Remember my rule: All threads in a kernel system call are running (and
> maybe put to asleep inside the kernel if it so wishes). As soon as the
> kernel passing back control via system call return you always intercept
> with valgrind doing a "Can I still run check? Yes=carry on, No=go to
> sleep under valgrind's control".
>
> Why would valgrind keep waking up the wrong thread, it wont do that with
> round-robin since it knows that T2 is blocked in the kernel (waiting for
> the lock).
I can't claim to really understand this, but I do have a couple of
questions:
* "it knows that T2 is blocked in the kernel"
how does V know that a syscall it is about do perform (on behalf
of the client application) will or will not block?
AFAICT that is unknowable from user space. And how would it
distinguish a block from merely a long wait?
* "No=go to sleep under valgrind's control"
how?
-------
Overall I have to say my feeling is that messing with the kernel's
scheduling is a losing proposition. We went to those kinds of places
in earlier years of the project, and it was always a massive PITA
and source of fragility.
It also seems to me that both you and Felix want to control the
scheduling as a way of shaking out threading-related bugs in applications
(but correct me if I'm wrong). FWIW, if that is indeed the case,
I would suggest that you'd be better off looking into race detection
algorithms which are more scheduling-independent and/or can understand
atomic instructions better (I think you mentioned something about them
earlier in the thread).
Do you have any concise fragments of code illustrating what problem
it is you are really trying to solve?
J
|
|
From: Darryl M. <dar...@ne...> - 2008-11-02 03:30:00
|
Julian Seward wrote: > I can't claim to really understand this, but I do have a couple of > questions: > > * "it knows that T2 is blocked in the kernel" > how does V know that a syscall it is about do perform (on behalf > of the client application) will or will not block? > AFAICT that is unknowable from user space. And how would it > distinguish a block from merely a long wait? It would work on the basis that Valgrind knows a syscall is being performed, its running the application/client under emulation and it has already intercepted the entrypoints to all syscalls. Valgrind already does a similar thing (but at a higher level up) for malloc/free/realloc etc. The application/client thinks it is calling the libc malloc, but it is not, it is calling valgrind's implementation. There is nothing to stop interception of anything in this way so that valgrind can do some work on entry and do some more work on exit. This is what I mean by syscall interception. > * "No=go to sleep under valgrind's control" > how? Valgrind has a list of threads, when valgrind decides it doesn't want to run this thread for a while it puts it to sleep using the same standard mechanisms that already exist (syscalls like futexes etc...). > Overall I have to say my feeling is that messing with the kernel's > scheduling is a losing proposition. We went to those kinds of places > in earlier years of the project, and it was always a massive PITA > and source of fragility. While the proposition of having complete authoritative control of thread scheduling sounds nice to have in your toolbag, its not required. What is really wanted is the ability to hint/bend the thread scheduler decisions in ways that don't violate basic runtime rules but can make debugging easier. We might hint that we want the current thread to yield CPU time to all other threads. One interpretation of this hint is that we want the scheduler to go out of its way to see to it that every other thread is given an opportunity to run (possibly for a number of occasions) before it returns control back to the current thread. We might even by willing to take a sleep/delay hit to give other threads even more time to wake up, should they not be in a runnable state just now. This is what my nanosleep() after gaining lock. Now that sort of hinting is useful to getting nearer the goal of proving multi-threaded application design. You can make the window of time for worst case scenario much larger in an attempt to trip things up when running testcases. > It also seems to me that both you and Felix want to control the > scheduling as a way of shaking out threading-related bugs in applications > (but correct me if I'm wrong). FWIW, if that is indeed the case, > I would suggest that you'd be better off looking into race detection > algorithms which are more scheduling-independent and/or can understand > atomic instructions better (I think you mentioned something about them > earlier in the thread). The biggest problem is that I would have thought valgrind is in the ideal position to be able to provide an audit of whats going on, if you so instruct valgrind about what you are interested in. Having it reverse engineer a program at runtime sounds great and all and for memcheck that approach works well. But if there is some specific threading issue that I'm looking to test I'd prefer to explicitly define a set of rules, then define a point A and point B and then ask valgrind to report (all of this to be done at runtime). In some cases I want it to also report on what happened even when no bug/problem was detected. So I can debug my instructions at configuring valgrind. So I can prove my testcase is actually testing and doing the correct thing. > Do you have any concise fragments of code illustrating what problem > it is you are really trying to solve? "Concise" might seem a little subjective. Certainly I've code that I'd like to better prove it is doing what I expect/think it to be doing. A simple audit of memory access would go a long way to achieving that. That is the main problem I'm trying to solve a tool that I can audit memory access with, it doesn't matter what the code actually is I just want to see "thread_id, pointer, length, mode(read or write)" in a list. I can take over from there. The data reported needs to be the memory's view of the world, which then brings in the issue well the only way to get a consist and 100% accurate log is to ensure only one thread is running application/client code at any one time. Which brings us back to reason we need threading control. Speaking in relation to atomic instructions and all that, At one layer there is the ability to prove custom threading primitives on a given platform. These being custom building blocks to supplement the limited primitives pthread provides for a given specialist task. For example the pthread implementation on Linux didn't always have a rwlock so we'd have to roll our own. Now we have rwlock the next specialist primitive of the month might be a fair_double_locking_doobery (whatever one of those is!). Then at another level is application usage of and interaction between a one or more primitives and data/memory. While making life better on the issue of debugging custom lower layer primitives is a worthy goal; most of my time (and I guess other peoples) is spent debugging applications using standard primitives. So to save getting off track feel free to stick with the goal of making life better in the domain of "application usage of standard threading primitives". Save the notion that valgrind can assist in debugging custom threading primitives for another day. Darryl |
|
From: tom f. <tf...@al...> - 2008-11-02 00:35:23
|
Darryl Miles <dar...@ne...> writes:
> tom fogal wrote:
> > Darryl Miles <dar...@ne...> writes:
> >> Julian Seward wrote:
> >> Then on the return from the system call the current thread checks to see
> >> if it is still allowed to run, if it is not allowed to run it suspends
> >> itself.
> >
> > You miss his point. Say we have two threads:
> >
> > T1 T2
> > pthread_mutex_lock(&m); pthread_mutex_lock(&m);
> > ht->add(key, value); ht->remove(key);
> > pthread_mutex_unlock(&m); pthread_mutex_unlock(&m);
> >
> > Now say thread 1 acquires the lock. Finally, this logic of valgrind
> > deciding which thread to run decides (through bug or otherwise) that
> > thread 2 should run. Both threads are currently paused. Then:
> >
> > The kernel decides to wake thread 1. Valgrind sees `runnable thread'
> > != `current thread', and does a sched_yield(). The kernel decides to
> > wake thread 1. Valgrind sees `runnable thread' != `current thread',
> > and does a sched_yield(). The kernel decides to wake thread 1 ...
One thing I neglected to think about earlier is how one would do a
`Can I still run?' check. There is no notification to a user process
when a context switch comes back.
Remember that valgrind instruments instructions.
> Remember my rule: All threads in a kernel system call are running (and
> maybe put to asleep inside the kernel if it so wishes). As soon as the
> kernel passing back control via system call return you always intercept
> with valgrind doing a "Can I still run check? Yes=carry on, No=go to
> sleep under valgrind's control".
>
> Why would valgrind keep waking up the wrong thread, it wont do that with
> round-robin since it knows that T2 is blocked in the kernel (waiting for
> the lock).
I had a long diatribe about how you essentially want the JVM's safe
points and how ridiculously difficult it will be, as you'd have to
write a parallel scheduler. Which I still think is true, in your
general case of the choosing which thread to run.
You really don't need that functionality though. All you want is to
guarantee that <= 1 thread is running, at all times.
A solution to your issue -- introduce a new mutex, within valgrind.
Wrap every function you possibly can. Acquire the lock before the
function, and release it after the function.
An example. User code:
T1 T2
some_system_call() acquire(&m1)
acquire(&m1) sys_call();
... do stuff ... whatever
release(&m1) release(&m1)
would translate to:
acquire(&vg_runnable_thread) acquire(&vg_runnable_thread)
some_system_call() acquire(&m1)
release(&vg_runnable_thread) release(&vg_runnable_thread)
acquire(&vg_runnable_thread) acquire(&vg_runnable_thread)
acquire(&m1) sys_call()
release(&vg_runnable_thread) release(&vg_runnable_thread)
... do stuff ... whatever
acquire(&vg_runnable_thread) acquire(&vg_runnable_thread)
release(&m1) release(&m1)
release(&vg_runnable_thread) release(&vg_runnable_thread)
I think that's safe. Think.
Notes:
* `acquire' is of course really pthread_mutex_lock, which is
itself of course a user-available function which you must wrap.
* the lock is not acquired for user-code: `do stuff' might be a
for loop which sums an array, for example, and you'd probably
want it to be able to execute concurrently with `whatever'.
* Otherwise -- where does it stop? You could acquire/release
around every *instruction*, I suppose, but that's
crazy-painful, performance wise.
There is a bit of a race at the beginning of a thread's lifetime --
threads may execute concurrently until they call something which is
wrappable.
In this scheme, you don't get to control which thread runs. But I
think Julian stressed, and I stress now, that you really don't want to
do that.
> pthread_mutex_lock(&m);
> // Artifically enlarge the window when the lock is held
> // in an attempt to catch the program out
> nanosleep({3,0}, NULL); // its more complex than this due to EINTR
> ht->add(key, value);
> pthread_mutex_unlock(&m);
>
> What I don't get at the unlock is an audit trail of access to memory I
> am interested in. A chronological order of read/write access with
> thread_id, pointer to start and length of access. This is what valgrind
> does so well.
It sounds like, if you wanted to do this, you *would* need to lock at
every instruction, since you'd need some kind of global hash table or
other data structure which would maintain this list.
By the way, have you heard of software transactional memory? ``STM''.
I'm not sure if there are any open-source systems which implement it.
However, an STM system must keep exactly this, except they of course
do it to provide better parallelism than the absurdity that is
threads.
Thinking about those gives me the idea that you could probably avoid
this wrapping in regions of code which could provably not r/w a shared
variable, perhaps by knowing that the thread holds no locks.
> No one is saying we'd use this mechanism to stop a thread forever, they
> are HINTS to the scheduling to lean a particular way during the decision
> making process. [snip]
If you only need a hint, not a hard guarantee, change your wrappers to
set and restore the thread priority instead of grab a lock. I imagine
that'd be much cheaper.
> struct timeval tv = { 5, 0 };
> vg_thread_control(VG_THREAD_YEILD, &tv);
>
> What this might mean is yield my timeslice to any/all other threads (in
> preference to us, we/current-thread temporarily adopts a priority of
> "absolute last resort", but only for a limited amount of time) in so
> doing we don't get passed control for at least 5 seconds, providing
> there is some other thread that can run. If there is just no other
> thread that can run then we will get back control sooner.
Implementing a timeout would probably be pretty hard..
> > The only way I can see to fix this is to have some sort of scheduling
> > logic inside valgrind itself [snip]
>
> Can we intercept all application/client system calls on a whim ?
> The entry points this and other threads use to make system calls we
> need to flip to another table. This includes the ability to flip
> the syscall exit code of already running threads that are currently
> blocked in the kernel.
[snip]
> By modifying the exit code (of an already running system call) that
> thread will participate in the thread control scheme upon its next
> return to user-space.
[snip]
I am not following this at all. Why would we ever want to modify the
return values of a system call?
> If threads are in application/client code already can they be
> interrupted too ? I'm guessing there must be the equivalent of IPI
> inside valgrind http://en.wikipedia.org/wiki/Interprocessor_interrupt
> to manage the global emulation state.
Valgrind reads in instructions, translates them, does its fancy magic
on them, translates them back, and spits them back out. Then the CPU
runs the new instruction stream.
I'm not sure how you're thinking it works, but it doesn't sound like
the instructions can `change' action based on an event, because
they're already a bunch of instructions. Like a JIT though, there
might be some way to cause future translations to have different
output.
>From a quick glance at nulgrind, I'd guesstimate the atomic unit
valgrind operates on is a basic block.
> >> That is the ability to control/suspend thread execution/scheduling
> >> within a process (possibly itself, possibly another process) but doing
> >> so in a way that is not observable to the application. This might have
> >> other uses outside debugging but mainly targeted at debugging.
> >
> > Could you write a wrapper application which fork/execs your chosen
> > application? This wrapper could use ptrace to start/pause the
> > application, and you could communicate with it however you choose, or
> > even just programmatically specify what you'd like.
> >
> > .. actually, that sounds a lot like gdb, to be honest. Maybe I'm
> > missing something.
>
> Yes you are missing the part about valgrind being able to audit
> read/write memory accesses at asm level in byte granularity. The bit
> valgrind does well, gdb can only tell you if the page is valid or not.
>
> Also the part about the application/client code being cooperative and
> interactive in the debugging process, i.e. the ability to call functions
> that solely exist to communicate with the debugger (ala
> vg_thread_control()). This is like dynamic breakpoints/watchpoints
> yadda yadda. "Hey look at me debugger, I'm about to do something that
> you should be looking at!"
Maybe looking at hacking gdb would be a quicker route to your goal.
You might be able to add code which says, `when a lock at address X
is acquired, automatically add watchpoints on address[es] ABC; when X
is unlocked, delete watchpoint[s] ABC'.
Anyway, I'm getting closer and closer to believing you want an STM-like
system, but to detect threading bugs instead of make multithreaded
programming easier. So I think you should googly around for some of
those first and see if those ideas can be applied in VG / gdb.
(I'd be very interested in what you find.)
Best,
-tom
|