develooper Front page | perl.perl5.porters | Postings from June 2013

Re: Storable refactoring, was Re: [perl #118139] Storable in DESTROYblocks

Thread Previous | Thread Next
Nicholas Clark
June 4, 2013 11:29
Re: Storable refactoring, was Re: [perl #118139] Storable in DESTROYblocks
Message ID:
On Wed, May 29, 2013 at 07:22:17PM +0200, Salvador Fandino wrote:

> Initially my plan was to send the patch to p5p once those bugs have been
> solved but as this bug report is here and people is already trying to
> solve it, I think is a good time to tell the world about my work on
> Storable :-)

Yes. Thanks for tracking perl5-porters to make sure that duplication of work
didn't happen (at least, not for more than a day)

I've skimmed your changes and wow, you have been busy.

> - Break the context into a two structures store_cxt and retrieve_cxt.

Good. I had wondered how possible this was.

> - Use a perl SV as the output buffer when storing to memory (the old
> structure has a O(N^2) performance.

I'd seen the existing implementation, and thought that using an SV had the
potential to simplify a chunk of the resource management code. I hadn't
realised that the old structure was O(bad)

> I think the most important change is moving the context object into the
> C stack because it was and absolute nightmare:
> It seems that initially, probably to simplify the code, Storable used
> some global variables to keep the context while recursing (note that the
> context is reset in every call so no data is shared between successive
> calls to store or retrieve functions).

I had guessed this based on evidence such as this:

#define kbuf	(cxt->keybuf).arena
#define ksiz	(cxt->keybuf).asiz

I was tempted to eliminate such #defines by doing search and replace on their
use points, as (within code that one controls completely) the short term
gains of just using a macro to avoid touching code later on don't seem to
outweigh the obfuscation costs of doing so. But as you've been refactoring,
this would just conflict.

> Then, perl got support for threads and the context was moved to thread
> storage and the funny thing is that, probably for performance reasons,
> also passed from call to call when recursing!

This seems to have been the case. The context structure was first added in
this release:

Tue Sep 14 22:13:28 MEST 1999   Raphael Manfredi <>

        Integrated "thread-safe" patch from Murray Nesbitt.
        Note that this may not be very efficient for threaded code,
        see comment in the code.

        Try to avoid compilation warning on 64-bit CPUs. Can't test it,
        since I don't have access to such machines.

but with a per-function dPERINTERP

That got replaced with a cxt parameter in this revision:

Sun Jul 30 12:59:17 MEST 2000   Raphael Manfredi <>

    First revision of Storable 0.7.

        The serializing format is new, known as version 2.0.  It is fully
        backward compatible with 0.6.  Earlier formats are deprecated and
        have not even been tested: next version will drop pre-0.6 format.

        Changes since 0.6@11:

        - Moved interface to the "beta" status.  Some tiny parts are still
          subject to change, but nothing important enough to warrant an "alpha"
          status any longer.

        - Slightly reduced the size of the Storable image by factorizing
          object class names and removing final object storage notification due
          to a redesign of the blessed object storing.

        - Classes can now redefine how they wish their instances to be serialized
          and/or deep cloned.  Serializing hooks are written in Perl code.

        - The engine is now fully re-entrant.

> Then, Storable got the hooks STORABLE_freeze and STORABLE_thaw, so in
> order to make it reentrant, the context was moved into some kind of
> perl-thread stack.

The hooks were also added in that revision.

> I believe it is the worst case of code rot I have ever seen!!!

Please don't temp people to find you stronger examples.

But thanks for your analysis of what went wrong.

> With my changes, the context is created when store or freeze functions
> are called on the C stack and passed from function to function when
> recurring. The temporal structures are mortalized so that they are freed
> when the code comes back to Perl-land.
> I might have introduced new bugs but IMO, now, the code is pretty much
> simpler and bugs should also be much easier to fix than before.

Yes, this seems like a much more sane solution.

> If you agree that having that into blead is a good idea, I think that
> the way to follow is to release it to CPAN as a development version
> first so that it can be tested (I have been testing it myself with all
> the latest perls on the 5.6 5.8, 5.10, 5.12, 5.14, 5.16, 5.18 and 5.19
> series with and without threads)

I think it would be good, once it's been thoroughly tested. You've said that
you've got an outstanding known bug of the 64 bit IV case for 32 bit
platforms. I'd agree with Leon here:

On Wed, May 29, 2013 at 07:39:50PM +0200, Leon Timmermans wrote:

> A CPAN smoke may be helpful :-)

I think that the way to go is probably

1) fix what you know to be broken
2) we put it in blead as a smoke-me branch and see what the various platform
   testers make of it. Fix those bugs
3) Put out a dev release, see what the CPAN testers make of it on various
   platforms and various versions. Fix any bugs
4) Once we think that there are no bugs (or we've reclassified all "bugs" as
   "known changes" and think that they aren't worrying), run a CPAN smoke
   to try to find any surprises

Then release it for real.

In that I'm vary wary of a large-scale refactoring of something rather low
in the dependency chain, with the potential for data loss. I'd be a lot more
confident if we've smoked CPAN, and nothing surprising happens. But that's
relatively expensive, so do it as a final validation step after getting the
cheaper tests clean first.

That will take some time. Given that the changes made in the branch
smoke-me/nicholas/rt-118139 fix the immediate bug, and make the code
no worse than it was before, I think the right thing to do is to merge
this to blead, and make a CPAN release. The changes to the XS are small,
and I think will be an easy conflict to resolve.

However, the changes in the branch smoke-me/nicholas/Storable start to be
more significant, and conflict with what you've been doing (without solving
the real problem, as you have), so I think the best thing to do is to
abandon them, instead of merging them. Except, that is, for the last change,
which I think you've got (attached, but I think it will conflict as-is).

This code isn't just redundant, it's technically undefined behaviour:

#if (PATCHLEVEL <= 6)

#if defined(USE_ITHREADS)

        ENTER; { \
        PerlInterpreter *orig_perl = PERL_GET_CONTEXT; \
        SAVESPTR(orig_perl); \
        qsort((char *) AvARRAY(av), len, sizeof(SV *), sortcmp); \
        } LEAVE;

#else /* ! USE_ITHREADS */

It was added in a refactoring which was discussed on this list in 2004.
A couple of messages whose neighbours in the thread give some context:

Whilst I participated in that thread back then, I wasn't aware of the
mechanism of ithreads, and hence why the advice given and code it resulted
in was wrong. Aha, experience (and hindsight).

From the commit message on the attached patch:

For 5.6.x and earlier, the interpreter context saving/restoring is not needed
prior to calling qsort(), as within the thread there is only one interpreter
in play.

Moreover, the SAVESPTR(orig_perl); in the removed code is not just pointless,
it's technically undefined behaviour. All that the SAVESPTR() macro will do
is ensure that the value of *(&orig_perl) is restored at scope exit. It
won't actually restore the interpreter context - that would need a call
to PERL_SET_CONTEXT with the value of origperl. The undefined behaviour is
because the LEAVE; which causes the scope pop action happens outside the
block, hence orig_perl has gone out of scope, and the address &orig_perl
(saved on the scope stack, written to by LEAVE), now points to invalid
memory. It is, however, quite hard to even get gcc's ASAN to trap this.

This code is likely unreachable anyway. It's only compiled in for 5.6.x and
earlier with USE_ITHREADS. ithreads was not useful until 5.8.0.

However, it takes quite a bit of effort to prove anything into viewing the
existing code as undefined behaviour. I guess that the nested block that the
macro creates is folded into the surrounding block, hence the automatic
variables within the nested block aren't seen as going out of scope until
later. I had to make the code into a static function (and hack the
pre-processor to force compilation on post-5.6) like this:

@@ -1032,16 +1032,22 @@ static const char byteorderstr_56[] = {BYTEORDER_BYTES_56, 0};
  * sortsv is not available ( <= 5.6.1 ).
-#if (PATCHLEVEL <= 6)
+static int sortcmp(const void *a, const void *b);
 #if defined(USE_ITHREADS)
+static sorted(pTHX_ AV *av, STRLEN len)
+    PerlInterpreter *orig_perl = PERL_GET_CONTEXT;
+    SAVESPTR(orig_perl);
+    qsort((char *) AvARRAY(av), len, sizeof(SV *), sortcmp);
 #define STORE_HASH_SORT \
         ENTER; { \
-        PerlInterpreter *orig_perl = PERL_GET_CONTEXT; \
-        SAVESPTR(orig_perl); \
-        PERL_SET_CONTEXT(aTHX); \
-        qsort((char *) AvARRAY(av), len, sizeof(SV *), sortcmp); \
+           sorted(aTHX_ av, len);              \
         } LEAVE;
 #else /* ! USE_ITHREADS */
@@ -1051,13 +1057,6 @@ static const char byteorderstr_56[] = {BYTEORDER_BYTES_56, 0};
 #endif  /* USE_ITHREADS */
-#else /* PATCHLEVEL > 6 */
-#define STORE_HASH_SORT \
-        sortsv(AvARRAY(av), len, Perl_sv_cmp);  
-#endif /* PATCHLEVEL <= 6 */
 static int store(pTHX_ stcxt_t *cxt, SV *sv);
 static SV *retrieve(pTHX_ stcxt_t *cxt, const char *cname);

[plus a couple more to ensure that static sortcmp was compiled]

with which I can finally provoke my test program into exploding:

./perl -Ilib -MStorable -e '++$Storable::canonical; Storable::freeze({1..4})'
==3557== ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7fffc15ef370 at pc 0x7578d7 bp 0x7fffc15eede0 sp 0x7fffc15eedd8
WRITE of size 8 at 0x7fffc15ef370 thread T0
    #0 0x7578d6 (/home/nick/Perl/perl/perl+0x7578d6)
    #1 0x750fbe (/home/nick/Perl/perl/perl+0x750fbe)
    #2 0x7fdc07ac2e61 (/home/nick/Perl/perl/lib/auto/Storable/
    #3 0x7fdc07adbdd4 (/home/nick/Perl/perl/lib/auto/Storable/
    #4 0x7fdc07adc88c (/home/nick/Perl/perl/lib/auto/Storable/
    #5 0x7fdc07afcdc7 (/home/nick/Perl/perl/lib/auto/Storable/
    #6 0x68cbfe (/home/nick/Perl/perl/perl+0x68cbfe)
    #7 0x668793 (/home/nick/Perl/perl/perl+0x668793)
    #8 0x47d810 (/home/nick/Perl/perl/perl+0x47d810)
    #9 0x47c535 (/home/nick/Perl/perl/perl+0x47c535)
    #10 0x41a9ad (/home/nick/Perl/perl/perl+0x41a9ad)
    #11 0x7fdc0844bea4 (/lib/x86_64-linux-gnu/
    #12 0x41a748 (/home/nick/Perl/perl/perl+0x41a748)
Address 0x7fffc15ef370 is located at offset 208 in frame <Perl_leave_scope> of T0's stack:
  This frame has 3 object(s):
    [32, 40) 'arg0'
    [96, 104) 'arg1'
    [160, 168) 'arg2'
HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
      (longjmp and C++ exceptions *are* supported)
Shadow bytes around the buggy address:
  0x1000782b5e10: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000782b5e20: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000782b5e30: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000782b5e40: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000782b5e50: 00 00 00 00 f1 f1 f1 f1 00 f4 f4 f4 f2 f2 f2 f2
=>0x1000782b5e60: 00 f4 f4 f4 f2 f2 f2 f2 00 f4 f4 f4 f3 f3[f3]f3
  0x1000782b5e70: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000782b5e80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000782b5e90: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000782b5ea0: 00 00 f1 f1 f1 f1 01 f4 f4 f4 f2 f2 f2 f2 04 f4
  0x1000782b5eb0: f4 f4 f2 f2 f2 f2 04 f4 f4 f4 f2 f2 f2 f2 04 f4
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:     fa
  Heap righ redzone:     fb
  Freed Heap region:     fd
  Stack left redzone:    f1
  Stack mid redzone:     f2
  Stack right redzone:   f3
  Stack partial redzone: f4
  Stack after return:    f5
  Stack use after scope: f8
  Global redzone:        f9
  Global init order:     f6
  Poisoned by user:      f7
  ASan internal:         fe
==3557== ABORTING

(sadly this isn't in the glorious Technicolor that Address Sanitizer
delivers for its terminal output)

gdb shows that the address of orig_perl is the problem address which
ASAN is complaining about, and the backtrace from the fault point shows
that it's at the scope exit.

Breakpoint 1, sorted (my_perl=0x605c0000ee80, av=0x60620001b6e8, len=2)
    at Storable.xs:1041
1041        PerlInterpreter *orig_perl = PERL_GET_CONTEXT;
(gdb) p &orig_perl
$1 = (PerlInterpreter **) 0x7fffffffdf50
(gdb) c

Breakpoint 2, __asan_report_error (pc=7698647, bp=140737488345536, 
    sp=140737488345528, addr=140737488346960, is_write=true, access_size=8)
    at /home/nick/src/gcc-4.8.0/libsanitizer/asan/
628     /home/nick/src/gcc-4.8.0/libsanitizer/asan/ No such file or directory.
(gdb) up
#1  0x00007ffff4e5d967 in __asan::__asan_report_store8 (addr=<optimized out>)
    at /home/nick/src/gcc-4.8.0/libsanitizer/asan/
234     /home/nick/src/gcc-4.8.0/libsanitizer/asan/ No such file or directory.
(gdb) up
#2  0x00000000007578d7 in Perl_leave_scope (my_perl=0x605c0000ee80, base=22)
    at scope.c:942
942                 *(SV**)(ARG0_PTR)= ARG1_SV;
(gdb) p arg0.any_ptr
$2 = (void *) 0x7fffffffdf50
(gdb) up
#3  0x0000000000750fbf in Perl_pop_scope (my_perl=0x605c0000ee80)
    at scope.c:110
110         LEAVE_SCOPE(oldsave);

The code is redundant and buggy. It should go.

Nicholas Clark

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About