|
From: Scott L. <sc...@sw...> - 2005-06-07 17:18:16
|
Hello all... I've been using Valgrind for what seems like several years now, and it's extremely helpful. I've recently run into a situation where the necessary information is not being reported, although I know that Valgrind has access to it. In a report of this form: ==10199== Conditional jump or move depends on uninitialised value(s) ==10199== at 0x816EAA4: foobar (abc.c:1202) ==10199== by 0x816EBEB: zigzag (def.c:1256) ==10199== by 0x816E726: bazquuz (xyz.c:1049) Why doesn't Valgrind tell me WHAT is uninitialized? I.e., what I really want to see is this: ==10199== Conditional jump or move depends on uninitialised value(s) ==10199== at 0x816EAA4: foobar (abc.c:1202) ==10199== by 0x816EBEB: zigzag (def.c:1256) ==10199== by 0x816E726: bazquuz (xyz.c:1049) ==10199== Address 0x1BB16B5C is 4 bytes within a block of size 512 ==10199== alloc'd at 0x1BB16B58: malloc (vg_replace-malloc.c:131) ==10199== by 0x819CA55: badfunction (memory1.c:154) That would allow me to instantly pinpoint the problem. It could also make similar reports for variables (both auto and static). Is there some reason why Valgrind doesn't tell me this information? Surely it has access to it. The current behavior isn't helpful. Thanks, Scott -- Scott Long <sc...@sw...> Software Engineer SwiftView, Inc. (971) 223-2639 |
|
From: Julian S. <js...@ac...> - 2005-06-07 17:32:45
|
> Is there some reason why Valgrind doesn't tell me this information? > Surely it has access to it. The current behavior isn't helpful. No, it doesn't have that info readily to hand. See sec 3.5 in http://www.valgrind.org/docs/manual/mc_main.html to understand what Memcheck is really doing. That said, you can find out what you want using the VALGRIND_CHECK_DEFINED client request. See sec 3.7 of the same page for details. J |
|
From: Nicholas N. <nj...@cs...> - 2005-06-08 17:17:40
|
On Tue, 7 Jun 2005, Julian Seward wrote: >> Is there some reason why Valgrind doesn't tell me this information? >> Surely it has access to it. The current behavior isn't helpful. > > No, it doesn't have that info readily to hand. See sec 3.5 > in http://www.valgrind.org/docs/manual/mc_main.html to understand > what Memcheck is really doing. In short, the undefined value is in a register, so you can't necessarily say anything about an uninitialised memory location. Nick |
|
From: John R.
|
> ... the necessary information is not being reported, although I know that > Valgrind has access to it. No, not directly, not with the current strategy and implementation. > ... What I really want to see is this: > > ==10199== Conditional jump or move depends on uninitialised value(s) > ==10199== at 0x816EAA4: foobar (abc.c:1202) > ==10199== by 0x816EBEB: zigzag (def.c:1256) > ==10199== by 0x816E726: bazquuz (xyz.c:1049) > ==10199== Address 0x1BB16B5C is 4 bytes within a block of size 512 > ==10199== alloc'd at 0x1BB16B58: malloc (vg_replace-malloc.c:131) > ==10199== by 0x819CA55: badfunction (memory1.c:154) > > That would allow me to instantly pinpoint the problem. It could also > make similar reports for variables (both auto and static). Memcheck waits until as late as possible (just before the program relies on the uninit value) before complaining. In addition to some theoretic beauty, this prevents "false positive" complaints. But as you experience, it is not always the most helpful for finding and fixing problems. Memcheck ought to have an _option_ to check and report as soon as possible: immediately upon each memory fetch. This would require patience in dealing with "false positive" complaints (such as copy of structures with holes, speculative loads that are later ignored, etc.) but probably it would help you in this and similar cases. Other memory checkers work this way. -- |
|
From: Scott L. <sc...@sw...> - 2005-06-08 18:18:48
|
John Reiser wrote: > Memcheck waits until as late as possible (just before the program relies > on the uninit value) before complaining. In addition to some theoretic > beauty, this prevents "false positive" complaints. But as you experience, > it is not always the most helpful for finding and fixing problems. I'll throw an idea out there... Each register could carry with it the last memory address it was loaded from. This address is either "NONE" (if the register has been set via an immediate MOV, or other similar operation), or an actual address. Register copies would copy this address to the new register, as well. Then, if the uninitialized register is used, the last known address could be reported. Obviously, this can't work in all cases. Here's one case it wouldn't work (using bastardized AT&T syntax): mov [uninitialized_val], eax add [uninitialized_val], eax In that case, eax consists of a "mixture" of two uninitialized values. Only one of these could be reported (probably the second one). However, not all is lost. The developer would fix the reported case, re-run, and then the other uninitialized value would be reported. Does this idea have any merit? -- Scott Long <sc...@sw...> Software Engineer SwiftView, Inc. (971) 223-2639 |
|
From: Nicholas N. <nj...@cs...> - 2005-06-09 08:26:31
|
On Wed, 8 Jun 2005, John Reiser wrote: > Memcheck ought to have an _option_ to check and report as soon as possible: > immediately upon each memory fetch. This would require patience in dealing > with "false positive" complaints (such as copy of structures with holes, > speculative loads that are later ignored, etc.) but probably it would > help you in this and similar cases. Other memory checkers work this way. I've said before that I tried this once, and got hundreds of error reports even for tiny programs like 'true'. So I don't think it's practical. N |
|
From: Scott L. <sc...@sw...> - 2005-06-09 15:38:03
|
John Reiser wrote: > Other people do think it is practical. They pay money to use it. > Purify works this way. The no-recompile mode of Insure++ works this way. > Customers tolerate the small fraction of false positive complaints, > partly because of the bulls-eye identification of the instruction > which first loaded the uninit bits. So is there any comment on my idea, here? Let each register track the last memory location it was loaded from, and report that location if the uninitialized register is used. If there is something fundamental that makes that idea unfeasible I'd be very interested to hear what it is. As far as I can tell, it's a good solution which would avoid false positives and would probably be trivial to implement. -- Scott Long <sc...@sw...> Software Engineer SwiftView, Inc. (971) 223-2639 |
|
From: Julian S. <js...@ac...> - 2005-06-09 15:56:03
|
> So is there any comment on my idea, here? Let each register track the > last memory location it was loaded from, and report that location if the > uninitialized register is used. > > If there is something fundamental that makes that idea unfeasible I'd be > very interested to hear what it is. As far as I can tell, it's a good > solution which would avoid false positives and would probably be trivial > to implement. It sounds like it needs potentially unbounded storage associated with each register in order to work. Supposing a register r contains the sum of values from a large range of memory locations, some of which are defined and some are undefined. How do you choose which of the undefined locations to tag the register with? J |
|
From: Scott L. <sc...@sw...> - 2005-06-09 16:07:12
|
Julian Seward wrote: > It sounds like it needs potentially unbounded storage associated with > each register in order to work. Supposing a register r contains the > sum of values from a large range of memory locations, some of which > are defined and some are undefined. How do you choose which of the > undefined locations to tag the register with? As I said in my original post, I don't think this is a problem. Pick one arbitrarily (to make it simple, just use the most recent). The developer will fix that error. Memcheck is run again, and now the next error is reported. In nearly all realistic cases, only a few uninitialized values will be involved. But consider this extreme case: int uninitialized_array[10000]; int sum = 0; for(i = 0; i < 10000; i++) sum += uninitialized_array[i]; do_something(sum); Obviously, fixing each uninitialized value one at a time will take aeons. However, an intelligent developer will spot the pattern and fix the general error (which is that the entire array is uninitialized). I really can't see any problems with this approach. -- Scott Long <sc...@sw...> Software Engineer SwiftView, Inc. (971) 223-2639 |
|
From: Nicholas N. <nj...@cs...> - 2005-06-09 16:26:28
|
On Thu, 9 Jun 2005, Scott Long wrote: >> It sounds like it needs potentially unbounded storage associated with >> each register in order to work. Supposing a register r contains the >> sum of values from a large range of memory locations, some of which >> are defined and some are undefined. How do you choose which of the >> undefined locations to tag the register with? > > As I said in my original post, I don't think this is a problem. Pick one > arbitrarily (to make it simple, just use the most recent). The developer will > fix that error. Memcheck is run again, and now the next error is reported. In > nearly all realistic cases, only a few uninitialized values will be involved. It sounds to me like a good compromise. Patches are welcome! N |
|
From: Scott L. <sc...@sw...> - 2005-06-09 16:31:00
|
Nicholas Nethercote wrote: > On Thu, 9 Jun 2005, Scott Long wrote: >> As I said in my original post, I don't think this is a problem. Pick >> one arbitrarily (to make it simple, just use the most recent). The >> developer will fix that error. Memcheck is run again, and now the next >> error is reported. In nearly all realistic cases, only a few >> uninitialized values will be involved. > > > It sounds to me like a good compromise. Patches are welcome! I'd love to, but it'll take me weeks to rummage through the code enough to understand the right way to do it. I'll come back to this the next time I have enough free time, but I will need some help identifying the proper places to make the changes. Please note that I am simply offering an idea, not making demands. There's too much of that crap going around... -- Scott Long <sc...@sw...> Software Engineer SwiftView, Inc. (971) 223-2639 |
|
From: Nicholas N. <nj...@cs...> - 2005-07-02 19:18:41
|
On Thu, 9 Jun 2005, Scott Long wrote: > So is there any comment on my idea, here? Let each register track the last > memory location it was loaded from, and report that location if the > uninitialized register is used. > > If there is something fundamental that makes that idea unfeasible I'd be very > interested to hear what it is. As far as I can tell, it's a good solution > which would avoid false positives and would probably be trivial to implement. I've given this some more thought. It's not trivial, for two reasons: - Every register now has to be shadowed by two extra values, one holding the V bits for Memcheck's validity checking, and the other holding the address. And every operation has to be shadowed by an extra operation that propagates the addresses to the result. The extra shadow operation would not be trivial -- eg. if you add two values A and B, and only one B is undefined, you'd need to propagate the address shadowing B to the result. If A and B were both defined or both undefined, you could propagate either. So, every register value now requires two shadow values, and every operations requires two shadow operations. This would require a non-trivial amount of effort to code up, and would have some runtime cost. - Converting the address to something more useful is not easy in general. It is easy when the address is within a heap block -- we can use the existing machinery to say "address X is 100 bytes into a 200 byte heap block allocated at Y". But if the address is on the stack or a static value, just saying "address X on the stack/in static memory" is not very helpful. Valgrind does have some support for identifying variables, but it only works with stabs debugging information. It's also possible that most undefined values are loaded from heap blocks, in which case bad messages about stack and static values aren't very important. [I was also wondering if it would be better to record the address of the instruction that does the loading, rather than the address from which the value was loaded. That way the messages would say "undefined value X used on line Y, and it was loaded from memory on line Z.] So it's not that straightforward. But it's certainly possible, and it would be very interesting to see how difficult it is, what the performance effect is, and if the resulting messages are genuinely helpful. (Perhaps I should scream "no! it will never work, fool!" in order to motivate someone into implementing it to prove me wrong :) ---- Having written all that... When diagnosing undefined value errors, you don't really want to know the address that the value was loaded from. Sometimes that will tell you, eg. if you malloc some memory, forget to initialise it, then load it and use it straight-away in a dangerous way -- the address mentioned by the error message will be that of the heap block that was the root cause of the problem. But if you copy that value first to the stack, then load it and use it dangerously, the address mentioned by the error message would be the stack address, which is not the root cause of the problem. Every undefined value was caused to be undefined by one or more events of undefined value creation. Eg. undefined value A came into being as part of a heap block allocated by malloc(). If A is added to a defined value B, the result would be an undefined value C. C's why-am-I-undefined event is still the same as A's, however. In the case where you have Z = X + Y and both X and Y are undefined, you can arbitrarily choose X's event or Y's event to become Z's event. (If the programmer fixed one and reran Memcheck, the other undefined event would then rear its head, if you see what I mean.) So rather than passing around extra memory addresses, it would be better to pass around "tokens" that record the event that caused the undefined value to come into existence. What are these events? Well, allocating a heap block with malloc() is an obvious one. Shrinking the stack passed some previously defined values is another one. You would shadow all undefined values with one of these tokens, and you'd propagate them in the (hopefully) obvious ways. One key idea here, which Scott pointed out, is that rather than having to record the full history of each undefined value, we only need to record one single undefined-value-causing event, even if the undefined value can be traced back to more than one undefined-value event. That's enough to give a better error message. The problem with this "token" idea is that I'm assuming every value can be shadowed with a token, including values in memory. If a token was the size of a pointer, this would blow out Memcheck's memory requirements too much. Scott's second key idea is that you can approximate this by recording the extra "token" only for registers. So tokens have possibly incomplete histories, since the passing of values through memory breaks that history. But perhaps undefined values don't pass in and out of memory very much, or perhaps the truncated history recorded from the most recent load is enough in a lot of cases. A third key idea is that this extra "token" only needs to be recorded for values which are undefined. So there's some potential for compression of representation there. Anyway, I've probably lost everyone by now, but I've come to appreciate some of the subtleties of this problem more now. Thanks, Scott :) N |
|
From: John R.
|
Nicholas Nethercote wrote:
> On Wed, 8 Jun 2005, John Reiser wrote:
>
>> Memcheck ought to have an _option_ to check and report as soon as
>> possible:
>> immediately upon each memory fetch. This would require patience in
>> dealing
>> with "false positive" complaints (such as copy of structures with holes,
>> speculative loads that are later ignored, etc.) but probably it would
>> help you in this and similar cases. Other memory checkers work this way.
>
>
> I've said before that I tried this once, and got hundreds of error
> reports even for tiny programs like 'true'. So I don't think it's
> practical.
Other people do think it is practical. They pay money to use it.
Purify works this way. The no-recompile mode of Insure++ works this way.
Customers tolerate the small fraction of false positive complaints,
partly because of the bulls-eye identification of the instruction
which first loaded the uninit bits. Some software quality policies
strongly encourage "never access uninit bits (for any reason.)"
Applying this policy to the most troublesome case (bit fields) can
_increase_ efficiency, particularly because gcc still generates
less-than-optimal code for sequences of assignments to adjacent
bit fields.
In most cases, 'true' is a shell builtin. Running the no-recompile
mode of Insure++ on "/bin/bash -c true" reports 1 READ_UNINIT_MEM error
from __gconv_transform_utf8_internal(), and two leaks from _dl_allocate_tls_storage().
The READ_UNINIT is genuine (bash 2.05b.0(1), /lib/tls/libc-2.3.2.so).
Compiling the C code
main() { exit(0); }
and running under the no-recompile mode of Insure++ gives no READ_UNINIT_MEM
errors, and the same two leaks. Please give a reproducible example of
your claim of "hundreds of errors."
--
|
|
From: Paul P. <ppl...@gm...> - 2005-06-09 14:49:01
|
n 6/9/05, John Reiser <jr...@bi...> wrote: > Other people do think it is practical. They pay money to use it. > Purify works this way. The no-recompile mode of Insure++ works this way. Not really: most customers I deal with suppress READ_UNINIT_MEMs=20 right away :-( They do have an option of turning it back on, though. > Running the no-recompile > mode of Insure++ on "/bin/bash -c true" reports 1 READ_UNINIT_MEM error But I think that's simply because Chaperon applies significant effort=20 to "cull out" the other RUMs (via various heuristics). If Chaperon didn't have its own mempcy(), memset(), etc. there probably would be=20 many more RUMs reported. Cheers, |
|
From: John R.
|
Paul Pluzhnikov wrote: >>Running the no-recompile >>mode of Insure++ on "/bin/bash -c true" reports 1 READ_UNINIT_MEM error > > > But I think that's simply because Chaperon applies significant effort > to "cull out" the other RUMs (via various heuristics). If Chaperon > didn't have its own mempcy(), memset(), etc. there probably would be > many more RUMs reported. The practical effect of Chaperon reducing the "clutter" caused by speculation in known routines of glibc (and generally in stereotypical code for bitfields) is much the same as the practical effect of memcheck's default suppressions for glibc, libX11, etc. Typical usage is willing to overlook these cases, and both checkers oblige by default. -- |