#379 Passing qsort an extra argument causes a segfault

[Derek Lamb]

In PDL-2.00716:

pdl> random(10)->average(1) for (0..100)
#average doesn't take an argument, but at least ignores it.

pdl> random(10)->qsort(1) for (0..100)
Segmentation fault: 11

I've also gotten:

pdl> random(10)->qsort(1) for (0..100)
perl(88949,0x7fff76629300) malloc: *** error for object 0x7f918384b918: incorrect checksum for freed object - object was probably modified after being freed.
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6

It doesn't happen every time, which is why I put the postfix for() on there. Sometimes I change the for() range and that makes the segfault happen.

I see this present in 2.006 as well.

Loaded PDL v2.006 (supports bad values)
pdl> random(10)->qsort(1) for (0..100)
pdl> random(10)->qsort(1) for (0..100)
pdl> random(10)->qsort(1) for (0..100)
pdl> random(10)->qsort(1) for (0..100)
pdl> random(10)->qsort(1) for (0..100)
pdl> random(10)->qsort(1) for (0..1000)
DUMPING 0x7ffe1bfc4720     datatype: 0
   State: (503564880) DATAFLOW_F|NOMYDIMS|DONTTOUCHDATA|HDRCPY|TRACEDEBUG
Segmentation fault: 11

perldl -V attached for 2.00716.

[Chris Marshall]

Slightly modified the title to make it clear that the problem is calling qsort incorrectly results in a segfault (or other nasty behavior). Under the hood the internal qsort routines by type have two extra arguments. Maybe the extra top level one is being passed into the lower level processing.

[Chris Marshall]

I'm not sure I would categorize an invalid call of qsort that results in a segfault as a bug. It seems like more robust input argument processing to report such problems via appropriate error messages would be more of a feature request.

[Derek Lamb]

Most other routines that get called inappropriately notify the user, or ignore the inappropriate call, or fail silently. One routine segfaulting and killing an entire perldl session because I forgot the arrow operator '->' is unexpected to say the least. I don't really care whether it's called a Bug or Feature Request, just wanted to log it so it would get fixed eventually.

[Chris Marshall]

Looking at the pp_def for 'qsort' in ufunc.pd, I see two ways that the loop size is calculated:

    'qsort',
    HandleBad => 1,
    Inplace => 1,
    Pars => 'a(n); [o]b(n);',
    Code =>
    'PDL_Indx nn;
     loop(n) %{ $b() = $a(); %}
     nn = $COMP(__n_size)-1;
    ' . generic_qsort('b'),
    BadCode =>
    'register PDL_Indx nn = 0, nb = $SIZE(n) - 1;
     loop(n) %{
        if ( $ISGOOD(a()) ) { $b(n=>nn) = $a(); nn++; }
        else                { $SETBAD(b(n=>nb)); nb--; }
     %}
     if ( nn != 0 ) {
        nn -= 1;
     ' . generic_qsort('b') . ' }',

In the Code section it uses $COMP(__n_size) while in the BadCode section we have $SIZE(n) which seems clearer. I don't know if this is the origin of the non-error message here.

[Chris Marshall]

Lowering the priority to 5 ("don't care") since this is not critical for PDL-2.014

[Derek Lamb]

I investigated this further. As far as I can tell, the problem is that if qsort gets an argument passed, the argument is (understandably) taken to be the output piddle. If the argument IS a piddle that is either null or the correct size, everything works fine. If it is a piddle that is the wrong size then PP's dimension checking figures that out and reports an error. If it is just a perl scalar, no error gets reported.

That might be a bug in and of itself. But in most routines that doesn't cause a problem (see PDL::Primitive's norm(), which has a signature exactly the same as qsort). In qsort, the input is copied into the output (this is the looop(n) bit)--if the output is a scalar at the end of this loop it just has a value of the last element of the input. Then a pointer to the output "piddle" is passed to generic_qsort--it's no surprise that index tricks produce at some point an illegal memory access.

What I would like is a modifier in the Pars section that says "convert this SV to a piddle of the correct size if it doesn't exist already", but I'm not sure that exists. Any pointers (ha!) would be appreciated.

If I change the Code section of qsort to:

    'PDL_Indx nn;
     loop(n) %{ $b() = $a(); %}
     nn = $COMP(__n_size)-1;
     if ($PDL(a)->dims[0] != $PDL(b)->dims[0] && $PDL(a)->dims[0]!=0 && $PDL(b)->dims[0]!=1){
        pdl_barf("You likely passed a scalar argument to qsort, when you should have passed a piddle");
     }
    ' . generic_qsort('b'),

Then it avoids the segfaults. The 2nd and 3rd conditionals are to allow trivial qsorts of the form

$c = pdl(0.4);
$c->qsort;

in which the input $c is an empty piddle of shape [] and the output is a piddle of shape [1], as happens at the beginning of ufunc.t.

A similar solution will be needed for qsorti and probably qsortvec and qsortveci.

[Derek Lamb]

Fixed, I believe, on branch sf379-qsort-crash.