Valgrind, an open-source memory debugger

> Do all our ideas about function interception rely on symbol information?
> What if the symbols are stripped?  AIUI, symbols must be present in shared
> objects, so for normal libpthread.so use relying on symbols is ok.  But
> what if a program was statically linked with libpthread and then stripped?
> Does that just go in the too-hard basket?

I think it does.  If we are proposing to intercept interesting entry points,
and we have no way of finding them, well, it's impossible.  In the end this 
is a debugging/profiling tool, and as such it's reasonable to require users
to retain at least some minimal set of symbol definitions.

J

On Fri, 13 Aug 2004, Julian Seward wrote:
>
>> 1:1 vs. N:M Threading models?
>> -----------------------------
>> Bob suggested that Linux needs to one day use a multi-level threading
>> model (multiple user threads per kernel thread, also known as N:M),
>> although Jeremy noted that Solaris has apparently gone to a 1:1 (one
>> kernel thread per user thread).  Tom noted that Linux's NPTL uses 1:1
>> too, and Paul seconded it.
>>
>> Bob also noted that OSes using N:M will cause problems if Valgrind
>> relies on intercepting clone();  Jeremy agreed, and noted another
>> approach would be required.
>
> I didn't understand this at the time and still don't.  Presumably an
> N:M threads package at some point will ask the kernel to create a new
> kernel thread -- in which case we just intercept that request?  clone()
> is merely that mechanism for Linux.

The problem is that Valgrind will need to use some other mechanism to 
become aware of threads since creating a new thread would not require 
a system call.  System calls related to threads would be to create new 
"LWP"s, bind a thread to an LWP, or bind an LWP to a processor.

It sounds like N:M is now unlikly in Linux's future, but it is still 
used by some other operating systems, and it would be really cool if 
Valgrind could work with multiple operating systems.

Bob
======================================
Bob Friesenhahn
bfriesen@...
http://www.simplesystems.org/users/bfriesen

> >> Bob also noted that OSes using N:M will cause problems if Valgrind
> >> relies on intercepting clone();  Jeremy agreed, and noted another
> >> approach would be required.
> >
> > I didn't understand this at the time and still don't.  Presumably an
> > N:M threads package at some point will ask the kernel to create a new
> > kernel thread -- in which case we just intercept that request?  clone()
> > is merely that mechanism for Linux.
>
> The problem is that Valgrind will need to use some other mechanism to
> become aware of threads since creating a new thread would not require
> a system call.  System calls related to threads would be to create new
> "LWP"s, bind a thread to an LWP, or bind an LWP to a processor.

Uh, can you say what this mechanism is?  I just don't see how the kernel
can magically decide to create a new kernel thread without the user-space
library asking it to do so, in one way or another.

J

In message <200408131545.37570.jseward@...>
        Julian Seward <jseward@...> wrote:

>> The problem is that Valgrind will need to use some other mechanism to
>> become aware of threads since creating a new thread would not require
>> a system call.  System calls related to threads would be to create new
>> "LWP"s, bind a thread to an LWP, or bind an LWP to a processor.
>
> Uh, can you say what this mechanism is?  I just don't see how the kernel
> can magically decide to create a new kernel thread without the user-space
> library asking it to do so, in one way or another.

Indeed it can't, and valgrind would probably cope quite happily with
user space thread switching within each kernel thread, except possible
for the whole stack switch detection issue.

The pthread validation stuff probably does need to track thread
creation and switching even for user level threads so that it knows
which thread owns which mutex and so on.

Tom

-- 
Tom Hughes (thh@...)
Software Engineer, Cyberscience Corporation
http://www.cyberscience.com/

On Fri, 13 Aug 2004, Julian Seward wrote:

>
>>>> Bob also noted that OSes using N:M will cause problems if Valgrind
>>>> relies on intercepting clone();  Jeremy agreed, and noted another
>>>> approach would be required.
>>>
>>> I didn't understand this at the time and still don't.  Presumably an
>>> N:M threads package at some point will ask the kernel to create a new
>>> kernel thread -- in which case we just intercept that request?  clone()
>>> is merely that mechanism for Linux.
>>
>> The problem is that Valgrind will need to use some other mechanism to
>> become aware of threads since creating a new thread would not require
>> a system call.  System calls related to threads would be to create new
>> "LWP"s, bind a thread to an LWP, or bind an LWP to a processor.
>
> Uh, can you say what this mechanism is?  I just don't see how the kernel
> can magically decide to create a new kernel thread without the user-space
> library asking it to do so, in one way or another.

I am not sure what the mechanism would be, but I do observe that GDB 
is able to detect and list all of the threads under Solaris.  Perhaps 
this is done via information gained from the /proc filesystem.

It is true that some user-space action is necessary in order to create 
a kernel thread.  If Valgrind is intended to validate programs at the 
user-thread level (not always tied to a kernel thread), is this 
sufficient?

Bob
======================================
Bob Friesenhahn
bfriesen@...
http://www.simplesystems.org/users/bfriesen

In message <Pine.SOC.4.60.0408130948310.28066@...>
        Bob Friesenhahn <bfriesen@...> wrote:

> I am not sure what the mechanism would be, but I do observe that GDB
> is able to detect and list all of the threads under Solaris.  Perhaps
> this is done via information gained from the /proc filesystem.

I don't know about Solaris, but on some systems there is a special
debugging library for allowing debuggers to get hold of thread
details.

Tom

-- 
Tom Hughes (thh@...)
Software Engineer, Cyberscience Corporation
http://www.cyberscience.com/

On Fri, 13 Aug 2004, Tom Hughes wrote:

>>> The problem is that Valgrind will need to use some other mechanism to
>>> become aware of threads since creating a new thread would not require
>>> a system call.  System calls related to threads would be to create new
>>> "LWP"s, bind a thread to an LWP, or bind an LWP to a processor.
>>
>> Uh, can you say what this mechanism is?  I just don't see how the kernel
>> can magically decide to create a new kernel thread without the user-space
>> library asking it to do so, in one way or another.
>
> Indeed it can't, and valgrind would probably cope quite happily with
> user space thread switching within each kernel thread, except possible
> for the whole stack switch detection issue.
>
> The pthread validation stuff probably does need to track thread
> creation and switching even for user level threads so that it knows
> which thread owns which mutex and so on.

I think there's some confusion here.

- For the *core*, only kernel threads matter.  They're what Valgrind's
   scheduler will deal with (and sequentialise), they're what its
   ThreadState (or equivalent) will be in terms of, and they're what would
   get farmed out across multiple processors if Valgrind didn't
   sequentialise them.  I think this is Julian's point.

- However, for *tools*, knowing about the user-level threads is
   important.  Eg. Helgrind needs to know if two different user-level
   threads are accessing the same memory.  The two user-level threads may
   be in two different kernel threads, or not.

   Similarly, for the generic pthreads sanity checking that's currently in
   the core, it needs to know about user-level threads so that it can tell
   if one user-level thread locks a mutex, and then another unlocks it.

So, AFAICT, we do need to be able to spot eg. a user-level thread-switch 
in N:M, and that won't be visible just by spotting pthread_*() calls 
because it's happening inside the user-space scheduler.  Which means N:M 
does have an extra difficulty over 1:1.  I think this is Bob's point.

At least, that's how I understand it.  Does that clarify things?

N

I extracted the discussion on native kernel mapping for user threads
from the current thread so things will be clearer.

I dig a bit into all the issues, and found an interesting and evolutive
solution, still based on the user thread/kernel thread 1:1 mapping,
which, I hope, solves all the problems which have been raised.

The basic idea is that:
- Each user thread is mapped to a kernel thread (you'd have guessed it ;-)
- But they do not run simultaneously: we schedule them using the
   current round-robin scheduler, so only one is running at a given time.

Benefits are:
- We keep the current reproductibility
- No locking required for A, V bits & Co
- Syscalls are performed in the current thread
- Signal handling is native and simpler, light wrappers will do it
- Thread handling also greatly simplified: no more user threads
- Tools do not need to be thread-aware
- No overhead compared to current solution
- MT coredumps and gdb attaching should work

In a second step (for people who like small steps ;-),
this architecture could be slightly modified to allow concurrent
execution of the user threads, using the kernel scheduler.
Of course this has to be an 'advanced' option, well-documented,
and we certainly do not want it to be the default, because:

- It won't help for single-threaded progs (just slowdown)
- It requires adequate (slower) protection mechanisms for metadata
- It requires tools and core to be thread-aware
- And all the issues we have discussed.

(But I think this can be discussed later)

As of the code sample, thank you. I had not in mind people writing
concurrently partially-initialized data to the same memory address...
But yes, after all the things I have seen, it may be unreasonable,
yet surely people do it....

So I've tested implementing simple spinlocks in a test program,
to protect (mem + V) like atomic updating, and the results I have
seem reasonable, e.g:

- tight loop, around:
      movl data, mem
      movl Vdata, Vmem

- versus a tight loop around spinlocked code:
    lck: xor  %eax, %eax
         xchg (lock), %eax
         jz lck
         movl data, mem
         movl Vdata, Vmem
         movl $1, (lock)

Gives the following slowdown:

                                  UP Athlon   SMP PII
No concurrency:                   x 3.3       x  4.8
2 threads write, tight loop:      x 7.1       x 11.2

Which seems acceptable (at least for me), considering that:
- The test code is rather unoptimized
- If implemented one day, we will have to take into account:
   o  the relative slowdown considered along with other instrumentation
      slowdown and UCode translation not requiring locking
      (e.g. inter-register ops)
   o  The fact that there will not be one the spinlock protecting
      the whole memory space, but many, protecting smaller memory
      ranges (e.g. one page, or 16 bytes, or whatever), so the slowdown
      will be almost equal to the "no concurrency" test scheme
- This will probably not be the default behaviour, even for MT programs

Which based on the median "30 times slowdown" of memcheck
(valgrind2003.ps, is-it still up-to date ?) and a very crude
computation, could lead to a 65 times slowdown for the athlon (if the
double memory access (mem + Vmem) is accounted for half of the
original slowdown. (which is probably even worse than the worst
case imaginable case, but I have no figures)

If you are interested by my test code, I could post it or put it somewhere
accessible.

Anyway, thank you guys for exercising my mind ;-) and of course
comment and question abundantly on that, I'd be glad to dig a bit
more or explain things if I was not clear.

Cheers

-- 
Eric

> > I am not sure what the mechanism would be, but I do observe that GDB
> > is able to detect and list all of the threads under Solaris.  Perhaps
> > this is done via information gained from the /proc filesystem.
> 
> I don't know about Solaris, but on some systems there is a special
> debugging library for allowing debuggers to get hold of thread
> details.

According to a friend who knows these things, Solaris was the originator
of the whole thread_db library (which is used by gdb to get this
information.)

Regards,
 Robert.

On Fri, 2004-08-13 at 21:27 +0200, Eric Estievenart wrote:
> Benefits are:
> - We keep the current reproductibility
> - No locking required for A, V bits & Co
> - Syscalls are performed in the current thread
> - Signal handling is native and simpler, light wrappers will do it
> - Thread handling also greatly simplified: no more user threads
> - Tools do not need to be thread-aware
> - No overhead compared to current solution

Um, there's a big problem though.  SCHED_RR tasks are real-time threads:
they take priority over all other non-RR (or FIFO) threads.  This means
that Valgrind will completely take over the CPU and prevent anything
other than higher-priority RT threads from running.

Also, on SMP machines, you'll still get concurrent RR threads on each
CPU.

> - MT coredumps and gdb attaching should work

(Valgrind already generates MT coredumps if the client faults - it has
to be done "manually", since the kernel doesn't know how to extract the
virtual state.)

> Which based on the median "30 times slowdown" of memcheck
> (valgrind2003.ps, is-it still up-to date ?) and a very crude
> computation, could lead to a 65 times slowdown f	or the athlon (if the
> double memory access (mem + Vmem) is accounted for half of the
> original slowdown. (which is probably even worse than the worst
> case imaginable case, but I have no figures)

The other thing to consider is the effect of increased code size - this
seems to be a large part of the base overhead (ie, the performance of
nulgrind).  

For UP machines, you might be able to get it faster if you can do
without xchg, since that is an implicitly LOCKed instruction (add to
memory is probably enough).

I did some similar experiments a while ago.  Rather than putting a
spinlock around everything unconditionally, I experimented with adding a
4-state sharing protocol for memory.  For this I have a lock for each 4k
of user address space (an arbitrary choice, which happens to be the page
size).  The lock can be in one of the following states:
      * untouched - nobody has touched this memory
      * private - only one thread has ever touched the memory
      * shared/unlocked - multiple threads have touched the memory, but
        its currently unlocked
      * shared/locked - ditto, but someone is currently locking it
There's also an owner ID packed into the word, so that it can tell who
currently owns it in the private state, so it knows to put it into the
shared state.

The rationale for this is that, even in MT programs, almost all memory
accesses (dynamically) are not to shared memory locations.  For example,
one of the hottest memory access areas are to the stack, but people
generally don't to MT access between thread stacks, so they should be
able to run unlocked.

The state transition between untouched/private and shared would be
handled by regenerating the basic block, so that the instrumentation is
converted from using unlocked to locked access (alternatively, you could
generate both, and keep a per-BB state bit saying which mode to use).

The tricky part is efficiently determining when a state transition is
needed, and making that transition threadsafe in the presence of
multiple CPUs.  I'll see if I can dig up my ideas, but I was never
completely confident in the algorithms, nor happy with the efficiency.

	J

On Fri, 2004-08-13 at 16:05 +0100, Nicholas Nethercote wrote:
> I think there's some confusion here.
> 
> - For the *core*, only kernel threads matter.  They're what Valgrind's
>    scheduler will deal with (and sequentialise), they're what its
>    ThreadState (or equivalent) will be in terms of, and they're what would
>    get farmed out across multiple processors if Valgrind didn't
>    sequentialise them.  I think this is Julian's point.
> 
> - However, for *tools*, knowing about the user-level threads is
>    important.  Eg. Helgrind needs to know if two different user-level
>    threads are accessing the same memory.  The two user-level threads may
>    be in two different kernel threads, or not.
> 
>    Similarly, for the generic pthreads sanity checking that's currently in
>    the core, it needs to know about user-level threads so that it can tell
>    if one user-level thread locks a mutex, and then another unlocks it.
> 
> So, AFAICT, we do need to be able to spot eg. a user-level thread-switch 
> in N:M, and that won't be visible just by spotting pthread_*() calls 
> because it's happening inside the user-space scheduler.  Which means N:M 
> does have an extra difficulty over 1:1.  I think this is Bob's point.
> 
> At least, that's how I understand it.  Does that clarify things?

Exactly so.

To handle M:N, we need to be able to observe when the thread's
implementation is doing a context switch between two app-level threads.
This is the same problem we have currently with people doing longjmp-
based user-level threading (NS4, for example).

	J

Jeremy Fitzhardinge wrote:

> Um, there's a big problem though.  SCHED_RR tasks are real-time threads:
> they take priority over all other non-RR (or FIFO) threads.  This means
> that Valgrind will completely take over the CPU and prevent anything
> other than higher-priority RT threads from running.

Huh ? When I spoke of the RR scheduler, I was speaking of current
V internal scheduler loop:

for(ever)
         for(each_thread)
                 if runnable
                         run it
         if (nothing ran)
                 idle()

which would become a loop for each user/native thread:

run_user_thread()
{
    for(;;)
    {
       wait for condition "I am the _only_ one allowed to run"
       run a few translated blocks
       select the next thread to run, and signal it.
    }
}

So when we intercept a clone(), we perform the syscall, and ajust
the new thread to run that loop. Since we will not allow it to run
immediately, it will have to wait until the current thread has
reached is quota of blocks to execute, and the scheduler has
granted it the right to run a bit. That way there is always one
and only one user thread running user code, all the others
are waiting on a mutex/cond/semaphore or whatever we put to
synchronize them.

> (Valgrind already generates MT coredumps if the client faults - it has
> to be done "manually", since the kernel doesn't know how to extract the
> virtual state.)

I didn't know that. I suppose that "manually" implies painful thinks
which have probably been tricky to debug, and may be as painful to maintain
if the thread handling scheme changes... Except with native thread mapping,
which would make this code useless.

> The other thing to consider is the effect of increased code size - this
> seems to be a large part of the base overhead (ie, the performance of
> nulgrind).  

Yes, but people may have to buy a bit more ram if they want to
do that ! Anyway this should be optional, so....

> For UP machines, you might be able to get it faster if you can do
> without xchg, since that is an implicitly LOCKed instruction (add to
> memory is probably enough).

I completely agree. My sample code is suboptimal, but the point
was to show that with such a very simple code, the slowdown
would be acceptable. Of course, with a better algorithm, we can
reduce the code size and bus locks.

 > ....
> The tricky part is efficiently determining when a state transition is
> needed, and making that transition threadsafe in the presence of
> multiple CPUs.  I'll see if I can dig up my ideas, but I was never
> completely confident in the algorithms, nor happy with the efficiency.

Indeed this is complex. I'm not an expert on such things, but by
curiosity (and real interest) I'll try to document myself a bit.

Cheers

-- 
Eric

On Sat, 2004-08-14 at 01:04 +0200, Eric Estievenart wrote:
> 
> Jeremy Fitzhardinge wrote:
> 
> > Um, there's a big problem though.  SCHED_RR tasks are real-time threads:
> > they take priority over all other non-RR (or FIFO) threads.  This means
> > that Valgrind will completely take over the CPU and prevent anything
> > other than higher-priority RT threads from running.
> 
> Huh ? When I spoke of the RR scheduler, I was speaking of current
> V internal scheduler loop:

Sorry, I thought you meant the kernel RR sched.

OK, I see, you mean run the scheduler in multiple kernel threads,
handing it off to a new clone thread when wants to switch app threads.

It makes context switching a bit more expensive (since that would
require a syscall where none is needed now), but I'd be surprised if
it's a huge deal.

There's still complexity with syscall handling though.  If the thread is
about to block in the a syscall, it needs to pass the baton off to
another thread in another LWP so it can make progress.  So we still need
to pay attention to whether a syscall is blockable.  Which means we
still need to pay attention to signal state, and dealing with signal
delivery properly.

Hm, I'm not sure it actually avoids the complexity of the proxy LWP
stuff.

> > (Valgrind already generates MT coredumps if the client faults - it has
> > to be done "manually", since the kernel doesn't know how to extract the
> > virtual state.)
> 
> I didn't know that. I suppose that "manually" implies painful thinks
> which have probably been tricky to debug, and may be as painful to maintain
> if the thread handling scheme changes... Except with native thread mapping,
> which would make this code useless.

It isn't that complex - the kernel doesn't know anything about glibc's
threads anyway, so the kernel dumper can't be thread-library specific.
So the Valgrind one doesn't need to be either.  It just emits the
appropriate data like the kernel would, and gdb has the job of matching
it up with the thread library's state.

> > The other thing to consider is the effect of increased code size - this
> > seems to be a large part of the base overhead (ie, the performance of
> > nulgrind).  
> 
> Yes, but people may have to buy a bit more ram if they want to
> do that ! Anyway this should be optional, so....

No, that's not my point.  Larger code size means more icache misses, and
so results in slower execution - not to mention that more instructions
take more time to load.  My point is that nulgrind has about 5x code
expansion, and a 5x increase in execution time.

	J

In message <Pine.LNX.4.60.0408132347070.25189@...>
          Nicholas Nethercote <njn25@...> wrote:

> In vg_syscalls.c, I see:
> 
>     SYSBA(getgroups32,           MayBlock),
>     SYSBA(getgroups,             0),
> 
> Surely they should be be MayBlock, or both be 0?

Both should be zero I think. I can't think of any reason why that
call should block.

Tom

-- 
Tom Hughes (thh@...)
Software Engineer, Cyberscience Corporation
http://www.cyberscience.com/

CVS commit by thughes: 

Move __pthread_clock_gettime and __pthread_clock_settime back to
the GLIBC_2.2.3 section which is where they were in glibc before
they were moved to GLIBC_PRIVATE around the 2.2.5 time frame.

This makes older systems work correctly as librt will be looking
for the symbols with that version. In order to make newer systems
work we make GLIBC_PRIVATE a child of the most recent version in
the file (currently GLIBC_2.3.3) so that a librt which is looking
for the symbols with a version of GLIBC_PRIVATE will find them.

The real glibc pthread libraries have GLIBC_PRIVATE as a child of
the most recent version anyway, so this shouldn't cause any problems
and with this change librt seems to be OK both on old RedHat 7.1 systems
with glibc 2.2.3 and on Fedora Core 2 systems with glibc 2.3.3.

Hopefully this will fix FAQ 3.4 but I haven't removed that just yet.

CCMAIL: 86696-done@...


  M +6 -2      vg_libpthread.vs   1.8


--- valgrind/coregrind/vg_libpthread.vs  #1.7:1.8
@@ -156,4 +156,9 @@
     # Extensions.
     pthread_getattr_np;
+    # These are in GLIBC_PRIVATE in the real library now but keep them 
+    # here for now for backwards compatibiltiy - they will still be
+    # visible to programs linked agianst newer libraries because of
+    # the inheritance into GLIB_PRIVATE in this library.
+    __pthread_clock_gettime; __pthread_clock_settime;
   } GLIBC_2.2;
 
@@ -194,5 +199,4 @@
   GLIBC_PRIVATE {
     __pthread_initialize_minimal; __pthread_cleanup_upto;
-    __pthread_clock_gettime; __pthread_clock_settime;
     __pthread_unwind;
-  };
+  } GLIBC_2.3.3;

> > > Could not read `malloc3.stderr.exp'
> > > make: *** [regtest] Error 2
> >
> > Is this just a local config thing, Tom?
>
> Not sure what it was - I've rerun it and it seems fine.

Bogon caused by NFS not working correctly, maybe, if you are
using NFS?

J

In message <200408132104.01484.jseward@...>
          Julian Seward <jseward@...> wrote:

> > > > Could not read `malloc3.stderr.exp'
> > > > make: *** [regtest] Error 2
> > >
> > > Is this just a local config thing, Tom?
> >
> > Not sure what it was - I've rerun it and it seems fine.
> 
> Bogon caused by NFS not working correctly, maybe, if you are using NFS?

No NFS involved. Maybe /tmp was full or something.

Tom

-- 
Tom Hughes (thh@...)
Software Engineer, Cyberscience Corporation
http://www.cyberscience.com/

In message <Pine.LNX.4.60.0408131747440.10911@...>
          Nicholas Nethercote <njn25@...> wrote:

> the difference is that ftruncate64() uses a 64-bit 'length'.  Also
> 
>     int fstat64(int filedes, struct stat64 *buf);
>     int fstat  (int filedes, struct stat   *buf);
> 
> is similar.
> 
> But fstat64() confuses me -- I don't understand how it's different to
> fstat().  Looking at the kernel source, it's something to do with
> BITS_PER_LONG...

The difference is that the stat64 structure contains 64 bit
size members but the stat structure only has 32 bit size members.

> And then there are the 32-suffix ones.  What is the difference between eg.
> chown() and chown32(), or getgid() and getgid32()?

Both chown and getgid deal with 16 bit uid/gid values and use the
special overflow token for uid/gid values which are too large. The
ones with the 32 suffix use 32 bit uid/gid values.

Oddly in the kernel source the routines are sys_getgid16 and sys_getgid
and so on...

Tom

-- 
Tom Hughes (thh@...)
Software Engineer, Cyberscience Corporation
http://www.cyberscience.com/