Usage and output with memory pools

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Usage and output with memory pools

Marshall Lochbaum
Hello,

I have been working on the memory model for J (the programming
language). J uses a fairly standard memory pool system for small
allocations, with a number of pools which are allocated once needed and
store small values.

My additions are shown here:
https://github.com/iocane/unbox/commit/62a0e6dd0278a49398ec9de06f93896e32a25177
The J source is notoriously hard to read, so this is just intended as a
way to check if I've done anything obviously wrong with Valgrind's
client requests.

When run, valgrind gives a reasonable number of invalid read and write
errors. I haven't been able to verify any of them, so the output might
not be correct. My problem is that they don't give an instance of free
which caused the error like Valgrind does when working with only
malloc/free. The error message only indicates that the address is in one
of the memory pools. Valgrind states that the block is "recently
re-allocated", a term which I don't understand and which doesn't seem to
appear in any of the documentation.

==4888== Invalid write of size 8
==4888==    at 0x4C3117F: memset (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4888==    by 0x607CE9F: jtexta (m.c:359)
==4888==    by 0x623F2D9: jtpreparse (wc.c:268)
==4888==    by 0x6060F1A: jtcolon (cx.c:295)
==4888==    by 0x60209CB: jtdfs2 (au.c:32)
==4888==    by 0x607F269: jtconj (p.c:62)
==4888==    by 0x607FCFE: jtparsea (p.c:138)
==4888==    by 0x607F986: jtparse (p.c:117)
==4888==    by 0x6083349: jtimmex (px.c:37)
==4888==    by 0x626B120: jtline (xs.c:52)
==4888==    by 0x626B7E4: jtlinf (xs.c:86)
==4888==    by 0x626B8FB: jtscm00 (xs.c:94)
==4888==  Address 0x5c31230 is 4,368 bytes inside a recently re-allocated block of size 65,536 alloc'd
==4888==    at 0x4C2ABD0: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4888==    by 0x607AF72: jtma (m.c:182)
==4888==    by 0x607C241: jtga (m.c:285)
==4888==    by 0x6071756: jtevinit (i.c:81)
==4888==    by 0x6071E10: jtjinit3 (i.c:154)
==4888==    by 0x6071EAC: jtjinit2 (i.c:169)
==4888==    by 0x60731D3: JInit (io.c:278)
==4888==    by 0x4013DF: jeload (jeload.c:66)
==4888==    by 0x4011BF: main (jconsole.c:133)

What does this error mean? Am I using the memory pool functions
correctly? How do I find when the memory in question was freed, or was
it just never allocated?

Thanks for your help,
Marshall

------------------------------------------------------------------------------
Mobile security can be enabling, not merely restricting. Employees who
bring their own devices (BYOD) to work are irked by the imposition of MDM
restrictions. Mobile Device Manager Plus allows you to control only the
apps on BYO-devices by containerizing them, leaving personal data untouched!
https://ad.doubleclick.net/ddm/clk/304595813;131938128;j
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Reply | Threaded
Open this post in threaded view
|

Re: Usage and output with memory pools

John Reiser
>  ...  The error message only indicates that the address is in one
> of the memory pools. Valgrind states that the block is "recently
> re-allocated", a term which I don't understand and which doesn't seem to
> appear in any of the documentation.

> ==4888==  Address 0x5c31230 is 4,368 bytes inside a recently re-allocated block of size 65,536 alloc'd

One advantage of open source is that users can inspect the source code.
=====
$ grep -sr 'recently re-allocated' .
        ...
./memcheck/mc_errors.c:      We however detect and report that this is a recently re-allocated
./memcheck/mc_errors.c:            ai->Addr.Block.block_desc = "recently re-allocated block";
        ...
=====
Then edit memcheck/mc_errors.c to read the comments and the code.
Doing so helped me understand the message.


------------------------------------------------------------------------------
Mobile security can be enabling, not merely restricting. Employees who
bring their own devices (BYOD) to work are irked by the imposition of MDM
restrictions. Mobile Device Manager Plus allows you to control only the
apps on BYO-devices by containerizing them, leaving personal data untouched!
https://ad.doubleclick.net/ddm/clk/304595813;131938128;j
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Reply | Threaded
Open this post in threaded view
|

Re: Usage and output with memory pools

Marshall Lochbaum
Correct me if I've misread the code. It appears that for an address to
be in a recently re-allocated block, it must be contained in a freed
block as well as in an allocated block. How do I get Valgrind to tell me
about the freed block, like it does with malloc/free?

Marshall

On Thu, May 26, 2016 at 03:06:39AM -0700, John Reiser wrote:

> >  ...  The error message only indicates that the address is in one
> > of the memory pools. Valgrind states that the block is "recently
> > re-allocated", a term which I don't understand and which doesn't seem to
> > appear in any of the documentation.
>
> > ==4888==  Address 0x5c31230 is 4,368 bytes inside a recently re-allocated block of size 65,536 alloc'd
>
> One advantage of open source is that users can inspect the source code.
> =====
> $ grep -sr 'recently re-allocated' .
> ...
> ./memcheck/mc_errors.c:      We however detect and report that this is a recently re-allocated
> ./memcheck/mc_errors.c:            ai->Addr.Block.block_desc = "recently re-allocated block";
> ...
> =====
> Then edit memcheck/mc_errors.c to read the comments and the code.
> Doing so helped me understand the message.
>
>
> ------------------------------------------------------------------------------
> Mobile security can be enabling, not merely restricting. Employees who
> bring their own devices (BYOD) to work are irked by the imposition of MDM
> restrictions. Mobile Device Manager Plus allows you to control only the
> apps on BYO-devices by containerizing them, leaving personal data untouched!
> https://ad.doubleclick.net/ddm/clk/304595813;131938128;j
> _______________________________________________
> Valgrind-users mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/valgrind-users

------------------------------------------------------------------------------
Mobile security can be enabling, not merely restricting. Employees who
bring their own devices (BYOD) to work are irked by the imposition of MDM
restrictions. Mobile Device Manager Plus allows you to control only the
apps on BYO-devices by containerizing them, leaving personal data untouched!
https://ad.doubleclick.net/ddm/clk/304595813;131938128;j
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Reply | Threaded
Open this post in threaded view
|

Re: Usage and output with memory pools

John Reiser
=====recently.c
#include "valgrind/valgrind.h"
#include <stdlib.h>
#include <string.h>

int main()
{
     int *const m0 = malloc (1<<16);
     VALGRIND_CREATE_MEMPOOL(m0, (1<<16), 0);  // a new pool inside a malloc()ed block

     int *const m1 = (4368/sizeof(int)) + m0;  // point into the interior of the pool
     VALGRIND_MEMPOOL_ALLOC(m0, m1, 16);  // "allocate" a block of 16 bytes from the pool
     VALGRIND_MEMPOOL_FREE(m0, m1);  // free the allocated block immediately
     memset(m1, 0, 16);  // [error] write into the free()d block

     return 0;
}
=====

==2668== Invalid write of size 8
==2668==    at 0x4C2EFDF: memset (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==2668==    by 0x40090B: main (recently.c:13)
==2668==  Address 0x51f7150 is 4,368 bytes inside a recently re-allocated block of size 65,536 alloc'd
==2668==    at 0x4C28C50: malloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==2668==    by 0x4007BA: main (recently.c:7)

So valgrind is trying to say that memset is writing into a free()d block,
and that the corresponding allocation was moderately recent.
Consult "valgrind --help  |  grep freelist" for hints,
then refer to the documentation or the source code.

------------------------------------------------------------------------------
What NetFlow Analyzer can do for you? Monitors network bandwidth and traffic
patterns at an interface-level. Reveals which users, apps, and protocols are
consuming the most bandwidth. Provides multi-vendor support for NetFlow,
J-Flow, sFlow and other flows. Make informed decisions using capacity
planning reports. https://ad.doubleclick.net/ddm/clk/305295220;132659582;e
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Reply | Threaded
Open this post in threaded view
|

Re: Usage and output with memory pools

Marshall Lochbaum
Do you know whether what I want to do is possible with Valgrind, or are
you just offering generic advice? Neither of the freelist options
(freelist-vol and freelist-big-blocks) seem related, and indeed,
changing them doesn't affect Valgrind's output on either your test
program or J. I'm well aware that if I read all of Valgrind's source
code I will eventually determine whether it has the option that I want,
but that is a tall order just to be able to use the program.

>From my perspective I have attempted to use Valgrind as intended, and it
fails to provide the single most important piece of information for
diagnosing a use-after-free error. I'm having difficulty understanding
why anyone would even find the current output useful--it simply states
that the offending block was allocated from the memory pool. The actual
information is clearly accessible to Valgrind, and it refuses to show
it! Even if this is only the default behavior, it strikes me as
completely insane.

Marshall

On Thu, May 26, 2016 at 09:27:28PM -0700, John Reiser wrote:

> =====recently.c
> #include "valgrind/valgrind.h"
> #include <stdlib.h>
> #include <string.h>
>
> int main()
> {
>      int *const m0 = malloc (1<<16);
>      VALGRIND_CREATE_MEMPOOL(m0, (1<<16), 0);  // a new pool inside a malloc()ed block
>
>      int *const m1 = (4368/sizeof(int)) + m0;  // point into the interior of the pool
>      VALGRIND_MEMPOOL_ALLOC(m0, m1, 16);  // "allocate" a block of 16 bytes from the pool
>      VALGRIND_MEMPOOL_FREE(m0, m1);  // free the allocated block immediately
>      memset(m1, 0, 16);  // [error] write into the free()d block
>
>      return 0;
> }
> =====
>
> ==2668== Invalid write of size 8
> ==2668==    at 0x4C2EFDF: memset (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==2668==    by 0x40090B: main (recently.c:13)
> ==2668==  Address 0x51f7150 is 4,368 bytes inside a recently re-allocated block of size 65,536 alloc'd
> ==2668==    at 0x4C28C50: malloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==2668==    by 0x4007BA: main (recently.c:7)
>
> So valgrind is trying to say that memset is writing into a free()d block,
> and that the corresponding allocation was moderately recent.
> Consult "valgrind --help  |  grep freelist" for hints,
> then refer to the documentation or the source code.
>
> ------------------------------------------------------------------------------
> What NetFlow Analyzer can do for you? Monitors network bandwidth and traffic
> patterns at an interface-level. Reveals which users, apps, and protocols are
> consuming the most bandwidth. Provides multi-vendor support for NetFlow,
> J-Flow, sFlow and other flows. Make informed decisions using capacity
> planning reports. https://ad.doubleclick.net/ddm/clk/305295220;132659582;e
> _______________________________________________
> Valgrind-users mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/valgrind-users

------------------------------------------------------------------------------
What NetFlow Analyzer can do for you? Monitors network bandwidth and traffic
patterns at an interface-level. Reveals which users, apps, and protocols are
consuming the most bandwidth. Provides multi-vendor support for NetFlow,
J-Flow, sFlow and other flows. Make informed decisions using capacity
planning reports. https://ad.doubleclick.net/ddm/clk/305295220;132659582;e
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Reply | Threaded
Open this post in threaded view
|

Re: Usage and output with memory pools

John Reiser
On 06/01/2016, Marshall Lochbaum wrote:

> Do you know whether what I want to do is possible with Valgrind, or are
> you just offering generic advice? Neither of the freelist options
> (freelist-vol and freelist-big-blocks) seem related, and indeed,
> changing them doesn't affect Valgrind's output on either your test
> program or J. I'm well aware that if I read all of Valgrind's source
> code I will eventually determine whether it has the option that I want,
> but that is a tall order just to be able to use the program.
>
>>From my perspective I have attempted to use Valgrind as intended, and it
> fails to provide the single most important piece of information for
> diagnosing a use-after-free error. I'm having difficulty understanding
> why anyone would even find the current output useful--it simply states
> that the offending block was allocated from the memory pool. The actual
> information is clearly accessible to Valgrind, and it refuses to show
> it! Even if this is only the default behavior, it strikes me as
> completely insane.
>
> Marshall

Valgrind (memcheck) works very well and does provide the information you seek
(in this case, the traceback at free() for the use-after-free error),
IF you do not use a custom pool allocator.  When you use a custom pool
allocator, then the allocator must cooperate with memcheck for best results,
and even then the results might not be 100% equivalent.
Support for custom pool allocators is a newer feature whose implementation
might be incomplete.  Or, the lack of traceback at free() for use-after-free
with a custom pool allocator might be a bug: submit a bug report
with a small test case that reproduces the behavior you dislike.

At the lowest level of VALGRIND_MEMPOOL_ALLOC, the cooperation
is not as good as that provided by VALGRIND_MALLOCLIKE_BLOCK.
So you might try using VALGRIND_MALLOCLIKE_BLOCK; but note that
the "red" zones introduce some overhead that requires thoughtful usage.
You might also try the variations of the --keep-stacktraces parameter.

Some explanation appears in valgrind.h.  This is the top-level #include
that must be used to define VALGRIND_MEMPOOL_* macros, and it is reasonable
to expect that demanding users should have read and tried to understand it.
===== valgrind.h [excerpt; see the file for more]
/* Several Valgrind tools (Memcheck, Massif, Helgrind, DRD) rely on knowing
    when heap blocks are allocated in order to give accurate results.  This
    happens automatically for the standard allocator functions such as
    malloc(), calloc(), realloc(), memalign(), new, new[], free(), delete,
    delete[], etc.

    But if your program uses a custom allocator, this doesn't automatically
    happen, and Valgrind will not do as well. ...
=====

It seems to me that users of a custom pool allocator should appreciate
that memcheck integrates as well as it does.  After that, a pool allocator
that has good usability will have an easy mechanism for reverting
to ordinary malloc+free, for which memcheck provides excellent diagnosis.



------------------------------------------------------------------------------
What NetFlow Analyzer can do for you? Monitors network bandwidth and traffic
patterns at an interface-level. Reveals which users, apps, and protocols are
consuming the most bandwidth. Provides multi-vendor support for NetFlow,
J-Flow, sFlow and other flows. Make informed decisions using capacity
planning reports. https://ad.doubleclick.net/ddm/clk/305295220;132659582;e
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Reply | Threaded
Open this post in threaded view
|

Re: Usage and output with memory pools

Philippe Waroquiers
On Wed, 2016-06-01 at 10:19 -0700, John Reiser wrote:

> On 06/01/2016, Marshall Lochbaum wrote:
> >>From my perspective I have attempted to use Valgrind as intended, and it
> > fails to provide the single most important piece of information for
> > diagnosing a use-after-free error. I'm having difficulty understanding
> > why anyone would even find the current output useful--it simply states
> > that the offending block was allocated from the memory pool. The actual
> > information is clearly accessible to Valgrind, and it refuses to show
> > it! Even if this is only the default behavior, it strikes me as
> > completely insane.
> >
> > Marshall
>

> It seems to me that users of a custom pool allocator should appreciate
> that memcheck integrates as well as it does.  After that, a pool allocator
> that has good usability will have an easy mechanism for reverting
> to ordinary malloc+free, for which memcheck provides excellent diagnosis.

Yes, having a way to revert to standard malloc/free (e.g. using
a compile time option) will for sure be the best way to have the
'standard excellent' diagnosis.
Diagnostics with custom pools are a lot more limited:
  * less precise or absent malloc/free stack traces (as you have seen)
  * no redzone (so no buffer under/over-flow detection).

That being said, I am the last one that has modified that area of the
code, so here are some explanations about the difficulty of handling
properly custom pool allocator blocks.

Valgrind maintains a list of malloc-ed blocks, and a list of (recently)
freed blocks (configured with --freelist-vol= and
--freelist-big-blocks=)

For 'normal' blocks (handled with malloc/free), a byte of memory
will be either in the free list or on the malloc list, but never
on both lists at the same time.

For 'custom' blocks, the situation is a lot more complex:
when a block is freed, valgrind stores it as part of the freed
block list. However, nothing forbids the custom block allocator
to directly re-use this block for the next allocation.
valgrind does not have a full description of the way the custom
pool works. It just takes note of what is freed, and stores it
in the freed list. It also takes note of what is allocated, and
stores it in the malloc list. When a new custom block is malloc-ed,
valgrind does not re-scan the freed list to try to clean it from
the pieces of memory that the custom pool has re-used to provide
the new block (that would certainly be very costly in terms of cpu,
and is not clear that this can be implemented correctly for all pools).
So, in summary, for custom pool, the same byte of memory can be
(possibly) in one custom malloc-ed block, and 0, 1 or more free-d
blocks.

The description of an error has space to report 2 stack traces.
To fully report all possible blocks that are the possible source
of an error, an error should have a list of stacktraces, each associated
with a certain block.

Taking all these limitations into account (and including the fact that
properly/fully support all kinds of custom pool would be a lot of
effort),
the current code does some effort to report somewhat the fact that
the same byte of memory can be considered both malloc-ed and free-d.

Also, in your case, there is an additional difficulty:
the pool memory itself is allocated using the standard malloc.
So, that means that a byte of memory will *always* be found
via this malloc 'main' block, and then might be found in one
'custom malloc-ed' block, and potentially in several free-d blocks.

The "recently re-allocated block" is a (somewhat) desperate attempt
to report some more info than just : 'this memory is on a freed block'
or 'this memory is on a malloc block'  (which might be the main block
or the custom malloc block, depending on the order valgrind will find
the first one).

So, in summary: yes, the custom pool support has a lot of weaknesses.
Yes, an error description is limited to 2 stack traces.
It might be possible to improve all this, but not straightforward to
generalise. Moreover, this cannot slow down the normal/usal case
of the classical malloc/free.

Maybe what could be done is to give priority to the 'smaller/inner'
malloc-ed block, when the same byte of memory is found via 2 different
blocks (i.e. the 'main' block, and the custom block).
Then if also found on a freed block, report the mallock stack trace
of the first block, and the free stack trace of the second block.

That is however not straightforward, to at the end still end up with an
inferior diagnosis, compared to standard malloc/free.

Hoping this (long) explanation clarifies a little bit

Philippe




------------------------------------------------------------------------------
What NetFlow Analyzer can do for you? Monitors network bandwidth and traffic
patterns at an interface-level. Reveals which users, apps, and protocols are
consuming the most bandwidth. Provides multi-vendor support for NetFlow,
J-Flow, sFlow and other flows. Make informed decisions using capacity
planning reports. https://ad.doubleclick.net/ddm/clk/305295220;132659582;e
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users