php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Bug #80861 erronous array key overflow in 2D array (only with JIT)
Submitted: 2021-03-14 08:47 UTC Modified: 2021-03-17 11:31 UTC
From: tbali0524 at gmail dot com Assigned: dmitry (profile)
Status: Closed Package: JIT
PHP Version: 8.0.3 OS: Windows 10 (x86_64)
Private report: No CVE-ID: None
 [2021-03-14 08:47 UTC] tbali0524 at gmail dot com
Description:
------------
Below code is excerpt from my implementation of D. Knuth's DLX algorithm for exact cover solver, run from CLI
- without JIT, the code runs fine (with the code excerpt in this bug report, the output is nothing.)
- with JIT, it fails with tons of warnings like
    PHP Warning:  Undefined array key 1235698926592 in C:\Coding\v\jit_bug.php on line 95
- but array keys are confirmed to be within bounds, possible overflow in JIT?
    - error is not present if the 2D array is much smaller
- PHP versions tested: v8.0.3, v8.0.2 (installed via XAMPP)
- OS: Windows 10 (x86_64)
- Invoke: php jit_bug.php > out.txt 2>&1
- PHP.ini settings:
    opcache.enable=1
    opcache.enable_cli=1
    opcache.jit_buffer_size=128M
    opcache.jit=tracing


Test script:
---------------
link to test script (to be tun CLI only, so rename after download)
https://www.aviationfanatic.com/tmp/jit_bug.php.txt

Expected result:
----------------
with the code excerpt in this bug report, the output is nothing.

Actual result:
--------------
with JIT, it fails with tons of warnings like
    PHP Warning:  Undefined array key 1235698926592 in C:\Coding\v\jit_bug.php on line 92
- but array keys are confirmed to be within bounds

Patches

Pull Requests

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2021-03-14 13:18 UTC] danack@php.net
Someone should change this site to say that although short repro cases are better, longer ones are fine also...


<?php

/*
Below code is excerpt from my implementation of D. Knuth's DLX algorithm for exact cover solver, run from CLI
- without JIT, the code runs fine (with the code excerpt in this bug report, the output is nothing.)
- with JIT, it fails with tons of warnings like
    PHP Warning:  Undefined array key 1235698926592 in C:\Coding\v\jit_bug.php on line 95
- but array keys are confirmed to be within bounds, possible overflow in JIT?
    - error is not present if the 2D array is much smaller
- PHP versions tested: v8.0.3, v8.0.2 (installed via XAMPP)
- OS: Windows 10 (x86_64)
- Invoke: php jit_bug.php > out.txt 2>&1
- PHP.ini settings:
    opcache.enable=1
    opcache.enable_cli=1
    opcache.jit_buffer_size=128M
    opcache.jit=tracing
*/

// note: when this is commented out, the code runs fine!
declare(strict_types=1);

// --------------------------------------------------------------------
class Node
{
    public $column = null;
    public $left = null;
    public $right = null;
    public $up = null;
    public $down = null;

    public static function joinLR(Node $a, Node $b): void
    {
        $a->right = $b;
        $b->left = $a;
    }

    public static function joinDU(Node $a, Node $b): void
    {
        $a->up = $b;
        $b->down = $a;
    }
}

// --------------------------------------------------------------------
class Column extends Node
{
    public function __construct()
    {
        $this->column = $this;
        $this->up = $this;
        $this->down = $this;
    }
}

// --------------------------------------------------------------------
class Matrix
{
    public $head = null;

    public function __construct()
    {
        $this->head = new Node();
        Node::joinLR($this->head, $this->head);
    }

    // $from is array[][] of bool
    public static function fromArray(array $from): Matrix
    {
        $m = new Matrix();
        $rowCount = count($from);
        if ($rowCount == 0) {
            return $m;
        }
        $columnCount = count($from[0]);
        if ($columnCount == 0) {
            return $m;
        }
        // we generate 2D double linked circular list of nodes from the input 2D bool array
        // might be not relevant for the bug
        $c = new Column();
        Node::joinLR($m->head, $c);
        for ($j = 1; $j < $columnCount; $j++) {
            $nextCol = new Column();
            Node::joinLR($c, $nextCol);
            $c = $c->right;
        }
        Node::joinLR($c, $m->head);
        $c = $m->head->right;
        error_log("These are the array bounds: $rowCount * $columnCount");
        for ($j = 0; $j < $columnCount; $j++) {
            $prev = $c;
            for ($i = 0; $i < $rowCount; $i++) {
                // next line generates the warnings despite $i and $j is within bounds
                if ($from[$i][$j]) {
                    $node = new Node();
                    $node->column = $c;
                    Node::joinDU($node, $prev);
                    Node::joinLR($node, $node);
                    $prev = $node;
                    // ... code to generate $m excluded
                }
            }
            Node::joinDU($c, $prev);
            $c = $c->right;
        }
        return $m;
    }
}

// --------------------------------------------------------------------
// simple driver code - fills up a 2D bool matrix and calls the static matrix constructing function above
for ($y = 0; $y < 100; $y++) {
    for ($x = 0; $x < 177; $x++) {
        $a[$y][$x] = true;
    }
}
$m = Matrix::fromArray($a);
 [2021-03-17 09:56 UTC] nikic@php.net
-Assigned To: +Assigned To: cmb
 [2021-03-17 09:56 UTC] nikic@php.net
Can't reproduce on Ubuntu with current PHP-8.0. @cmb Can you reproduce this on Windows?
 [2021-03-17 11:31 UTC] cmb@php.net
-Assigned To: cmb +Assigned To: dmitry
 [2021-03-17 11:31 UTC] cmb@php.net
I can reproduce with a ZTS build (NTS appears to be fine).  It
happens to me also with strict_types=0.  The actual undefined array
keys differ from run to run.

Dmitry, could you please have a look?
 [2021-03-17 20:00 UTC] dmitry@php.net
Automatic comment on behalf of dmitry@zend.com
Revision: http://git.php.net/?p=php-src.git;a=commit;h=7e494d92258b0150e228bae82021a92b64e415b8
Log: Fixed bug #80861 (erronous array key overflow in 2D array with JIT)
 [2021-03-17 20:00 UTC] dmitry@php.net
-Status: Assigned +Status: Closed
 
PHP Copyright © 2001-2024 The PHP Group
All rights reserved.
Last updated: Mon Oct 14 09:01:27 2024 UTC