|
From: Graydon H. <gr...@po...> - 2006-08-26 03:49:42
Attachments:
vg-mempool-move-and-sanity-check-2006-08-25.patch
|
Hi,
In the process of tracking down and killing Every Last Way In Which
Mozilla's Memory Pools Don't Quite Fit Valgrind's Assumptions, I found
myself composing this patch. It has three main parts:
- Logging mempool requests and their contexts on verbosity levels > 2
- Sanity checking mempool structures before and after mutations
(turns out that in a program with nontrivial client requests, it's
easy to corrupt the basic non-overlap assumption in a mempool)
- Two more client requests, needed to support such madness as
realloc()'ing a mempool:
- One to move a mempool to a new anchor address
- One to move (and optionally resize) a chunk within a mempool
There will be at least one more horrible patch after this, to teach the
leak scanner how to handle pointers with tag bits, and probably one to
teach it to ignore regions marked as non-pointer-containing (this often
assuages people's fears when you discuss the possibility of a false
positive in a pointer-scanner).
But those patches are still in the works. This one is ready, as far as I
can tell.
-graydon
|
|
From: Graydon H. <gr...@po...> - 2006-08-26 04:23:15
Attachments:
vg-mempool-move-and-sanity-check-2-2006-08-25.patch
|
Graydon Hoare wrote: > Hi, > > In the process of tracking down and killing Every Last Way In Which > Mozilla's Memory Pools Don't Quite Fit Valgrind's Assumptions, I found > myself composing this patch. ... And of course, this is the patch that actually applies to something nearly-like your SVN head. -graydon |
|
From: Julian S. <js...@ac...> - 2006-08-27 12:42:44
|
Graydon This is good stuff. I'm keen to fold it into the mainline if it's what you need to track down space leaks in Mozilla. Will wait until you have a complete patch-set though. My only reservation is that one result of this will be that you are the only person in the universe who really understands Valgrind's mempool-based leak detection now. Is it possible you could supply an overview of the resulting state/functionality/usage-guidelines of the mempool stuff, something that I could convert into user-level documentation? The manual's current table of contents is at http://www.valgrind.org/docs/manual/manual.html and I was thinking of perhaps adding a subsection "3.7 Mempools: describing and working with custom allocators", or some such. J On Saturday 26 August 2006 04:49, Graydon Hoare wrote: > Hi, > > In the process of tracking down and killing Every Last Way In Which > Mozilla's Memory Pools Don't Quite Fit Valgrind's Assumptions, I found > myself composing this patch. It has three main parts: > > - Logging mempool requests and their contexts on verbosity levels > 2 > > - Sanity checking mempool structures before and after mutations > (turns out that in a program with nontrivial client requests, it's > easy to corrupt the basic non-overlap assumption in a mempool) > > - Two more client requests, needed to support such madness as > realloc()'ing a mempool: > - One to move a mempool to a new anchor address > - One to move (and optionally resize) a chunk within a mempool > > There will be at least one more horrible patch after this, to teach the > leak scanner how to handle pointers with tag bits, and probably one to > teach it to ignore regions marked as non-pointer-containing (this often > assuages people's fears when you discuss the possibility of a false > positive in a pointer-scanner). > > But those patches are still in the works. This one is ready, as far as I > can tell. > > -graydon |
|
From: Graydon H. <gr...@po...> - 2006-08-29 00:26:48
|
Julian Seward wrote: > Graydon > > This is good stuff. I'm keen to fold it into the mainline if it's what > you need to track down space leaks in Mozilla. Will wait until you have > a complete patch-set though. > > My only reservation is that one result of this will be that you are > the only person in the universe who really understands Valgrind's > mempool-based leak detection now. Is it possible you could supply > an overview of the resulting state/functionality/usage-guidelines of > the mempool stuff, something that I could convert into user-level > documentation? > > The manual's current table of contents is at > http://www.valgrind.org/docs/manual/manual.html > and I was thinking of perhaps adding a subsection "3.7 Mempools: > describing and working with custom allocators", or some such. Certainly. Is this sufficient? 3.7 Mempools: describing and working with custom allocators Some programs use custom memory allocators, often for performance reasons. There are many different sorts of memory pool, so memcheck attempts to reason about them using a very loose, abstract model. We use the following terminology when describing custom allocation systems: - Custom allocation involves a set of independend "memory pools". - Memcheck's notion of a a memory pool consists of a single "anchor address" and a set of non-overlapping "chunks" associated with the anchor address. - Typically a pool's anchor address is the address of a book-keeping "header" structure. - Typically the pool's chunks are drawn from a contiguous "superblock" acquired through the system malloc() or mmap(). Keep in mind that the last two points above say "typically": the valgrind mempool client request API is intentionally vague about the exact structure of a mempool. There is no specific mention made of headers or superblocks. Nevertheless, the following picture may help elucidate the intention of the terms in the API: "pool" (anchor address) | v +--------+---+ | header | o | +--------+-|-+ | v superblock +------+---+--------------+---+------------------+ | |rzB| allocation |rzB| | +------+---+--------------+---+------------------+ ^ ^ | | "addr" "addr"+"size" Note that the header and the superblock may be contiguous or discontiguous, and there may be multiple superblocks associated with a single header; such variations are opaque to memcheck. The API only requires that your allocation scheme can present sensible values of "pool", "addr" and "size". Typically, before making client requests related to mempools, a client program will have allocated such a header and superblock for their mempool, and marked the superblock NOACCESS using the VALGRIND_MAKE_MEM_NOACCESS client request. When dealing with mempools, the goal is to maintain a particular invariant condition: that memcheck believes the unallocated portions of the pool's superblock (including redzones) are NOACCESS. To maintain this invariant, the client program must ensure that the superblock *starts* that way; memcheck cannot make it so, since memcheck never explicitly learns about the superblock of a pool, only the allocated chunks within the pool. Once the header and superblock for a pool are established and properly marked, there are a number of client requests programs can use to inform memcheck about changes to the state of a mempool: VALGRIND_CREATE_MEMPOOL(pool, rzB, is_zeroed) This request registers the address "pool" as the anchor address for a memory pool. It also provides a size "rzB", specifying how large the redzones placed around chunks allocated from the pool should be. Finally, it provides an "is_zeroed" flag that specifies whether the pool's chunks are zeroed (more precisely: defined) when allocated. Upon completion of this request, no chunks are associated with the pool; the request simply tells memcheck that the pool exists, so that subsequent calls can refer to it as a pool. VALGRIND_DESTROY_MEMPOOL(pool) This request tells memcheck that a pool is being torn down. Memcheck then removes all records of chunks associated with the pool, as well as its record of the pool's existence. While destroying its records of a mempool, memcheck resets the redzones of any live chunks in the pool to NOACCESS. VALGRIND_MEMPOOL_ALLOC(pool, addr, size) This request informs memcheck that a "size"-byte chunk has been allocated at "addr", and associates the chunk with the specified "pool". If the pool was created with nonzero "rzB" redzones, memcheck will mark the "rzB" bytes before and after the chunk as NOACCESS. If the pool was created with the "is_zeroed" flag set, memcheck will mark the chunk as DEFINED, otherwise memcheck will mark the chunk as UNDEFINED. VALGRIND_MEMPOOL_FREE(pool, addr) This request informs memcheck that the chunk at "addr" should no longer be considered allocated. Memcheck will mark the chunk associated with "addr" as NOACCESS, and delete its record of the chunk's existence. VALGRIND_MEMPOOL_TRIM(pool, addr, size) This request "trims" the chunks associated with "pool". The request only operates on chunks associated with "pool". Trimming is formally defined as: - All chunks entirely inside the range [addr,addr+size) are preserved. - All chunks entirely outside the range [addr,addr+size) are discarded, as though VALGRIND_MEMPOOL_FREE was called on them. - All other chunks are intersected with the range [addr,addr+size); areas outside the intersection are marked as NOACCESS, as though they had been independently freed with VALGRIND_MEMPOOL_FREE. This is a somewhat rare request, but can be useful in implementing the type of mass-free operations common in custom LIFO allocators. VALGRIND_MOVE_MEMPOOL(poolA, poolB) This request informs memcheck that the pool previously anchored at address "poolA" has moved to anchor address "poolB". This is a rare request, typically only needed if you realloc() the header of a mempool. No memory-status bits are altered by this request. VALGRIND_MEMPOOL_CHANGE(pool, addrA, addrB, size) This request informs memcheck that the chunk previously allocated at address "addrA" within "pool" has been moved and/or resized, and should be changed to cover the region [addrB,addrB+size). This is a rare request, typically only needed if you realloc() a superblock or wish to extend a chunk without changing its memory-status bits. No memory-status bits are altered by this request. |
|
From: Graydon H. <gr...@po...> - 2006-09-08 23:43:26
Attachments:
vg-mempool-move-and-sanity-check-2006-09-08.patch
|
Here's an update to the mempool move / change client requests and sanity
checking. The following changes are present:
- Added one more (hopefully last) client request, a predicate to
test whether a mempool anchor address is currently tracked.
It turns out mozilla's arena-using code is sufficiently inconsistent
in its assumptions that it's very difficult to phrase the valgrind
client-request annotations without this request. Namely: sometime
arena-init and arena-free operations are assumed to be idempotent.
- Fixed a very rapid tool-memory leak in the mempool sanity check
routine. The previous version of the patch I posted would use all
memory even on my Very Beefy Test Machine within ~15 minutes of
browsing with firefox.
- Added a little logging code to print the counts of pools and chunks
active every ~10000 sanity checks, when running with -v.
You'll also need to tack on this paragraph to the suggested mempool
client-request documentation I posted:
VALGRIND_MEMPOOL_EXISTS(pool)
This request informs the caller whether or not memcheck is currently
tracking a mempool at anchor address "pool". It evaluates to 1 when
there is a mempool associated with that address, 0 otherwise. This is a
rare request, only useful in circumstances when client code might have
lost track of the set of active mempools.
Thanks,
-graydon
|
|
From: Julian S. <js...@ac...> - 2006-10-05 16:24:12
|
Looks fine. The only problem I can see is that you #included coregrind/pub_core_options.h into memcheck/mc_malloc_wrappers.c, which totally breaks the core/tool abstraction :-) Tools are only allowed to include pub_tool_*.h. But AFAICS it's only to provide debugging printing (for the mempools machinery itself) at -v -v and above. So how about if I just hardwire a fixed backtrace depth, say 16, in place of those uses of VG_(clo_backtrace_size) ? J On Saturday 09 September 2006 00:43, Graydon Hoare wrote: > Here's an update to the mempool move / change client requests and sanity > checking. The following changes are present: > > - Added one more (hopefully last) client request, a predicate to > test whether a mempool anchor address is currently tracked. > It turns out mozilla's arena-using code is sufficiently inconsistent > in its assumptions that it's very difficult to phrase the valgrind > client-request annotations without this request. Namely: sometime > arena-init and arena-free operations are assumed to be idempotent. > > - Fixed a very rapid tool-memory leak in the mempool sanity check > routine. The previous version of the patch I posted would use all > memory even on my Very Beefy Test Machine within ~15 minutes of > browsing with firefox. > > - Added a little logging code to print the counts of pools and chunks > active every ~10000 sanity checks, when running with -v. > > You'll also need to tack on this paragraph to the suggested mempool > client-request documentation I posted: > > VALGRIND_MEMPOOL_EXISTS(pool) > > This request informs the caller whether or not memcheck is currently > tracking a mempool at anchor address "pool". It evaluates to 1 when > there is a mempool associated with that address, 0 otherwise. This is a > rare request, only useful in circumstances when client code might have > lost track of the set of active mempools. > > Thanks, > > -graydon |
|
From: Graydon H. <gr...@po...> - 2006-10-05 17:46:20
|
Julian Seward wrote: > Looks fine. The only problem I can see is that you #included > coregrind/pub_core_options.h into memcheck/mc_malloc_wrappers.c, > which totally breaks the core/tool abstraction :-) Tools are > only allowed to include pub_tool_*.h. > > But AFAICS it's only to provide debugging printing (for the mempools > machinery itself) at -v -v and above. So how about if I just hardwire > a fixed backtrace depth, say 16, in place of those uses of > VG_(clo_backtrace_size) ? Sure. I was just trying to conform to house style; whatever works for you. -graydon |
|
From: Julian S. <js...@ac...> - 2006-10-05 18:04:06
|
Committed, including your documentation stuff (r6196 and 6197). Thanks for that. At some point (no hurry) it would be good if you could confirm that a clean checkout of the trunk now works as you intend viz-a-viz mozilla's memory pools. J On Thursday 05 October 2006 18:45, Graydon Hoare wrote: > Julian Seward wrote: > > Looks fine. The only problem I can see is that you #included > > coregrind/pub_core_options.h into memcheck/mc_malloc_wrappers.c, > > which totally breaks the core/tool abstraction :-) Tools are > > only allowed to include pub_tool_*.h. > > > > But AFAICS it's only to provide debugging printing (for the mempools > > machinery itself) at -v -v and above. So how about if I just hardwire > > a fixed backtrace depth, say 16, in place of those uses of > > VG_(clo_backtrace_size) ? > > Sure. I was just trying to conform to house style; whatever works for you. > > -graydon |