php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Bug #53237 LinkedList max nodes Segmentation fault
Submitted: 2010-11-03 16:53 UTC Modified: 2017-10-24 07:55 UTC
Votes:1
Avg. Score:5.0 ± 0.0
Reproduced:1 of 1 (100.0%)
Same Version:0 (0.0%)
Same OS:1 (100.0%)
From: lifinsky at yandex dot ru Assigned:
Status: Open Package: Scripting Engine problem
PHP Version: 5.3.3 OS: Vista, Linux
Private report: No CVE-ID: None
View Add Comment Developer Edit
Welcome! If you don't have a Git account, you can't do anything here.
You can add a comment by following this link or if you reported this bug, you can edit this bug over here.
(description)
Block user comment
Status: Assign to:
Package:
Bug Type:
Summary:
From: lifinsky at yandex dot ru
New email:
PHP Version: OS:

 

 [2010-11-03 16:53 UTC] lifinsky at yandex dot ru
Description:
------------
I test linkedList performance and memory usage on Windows Vista Premium with PHP 5.3.3. When list length > 34860 I have server fatal Error ( Segmentation fault) and my fast-cgi script closed. I try test on Linux (PHP 5.2.6) but have some error if length ~ 32735. This error is not related with memory limit.

Test script:
---------------
class LinkedList { 
	private $_length = 0;
	private $_head;
	private $_tail;
	public function add($data) {
		$node = (object) array('data' => $data, 'next' => null);
		if ($this->_length == 0) {
			$this->_head = $node;
			$this->_tail = $node;
		} else {
			$this->_tail->next = $node;
			$this->_tail = $node;
		}
		$this->_length++;
	}
}


$a = new LinkedList();
$startMemory = memory_get_usage();
$start = microtime(true);
for ($i = 1; $i <= 34860; $i++) {
	$a->add($i);
}
$endMemory = memory_get_usage();
$end = microtime(true);
print(($end - $start) . '<br />');
print((int) (($endMemory - $startMemory) / 1024) . '<br />');

Expected result:
----------------
If length = 34860 I got 

0.12323784828186
11276


Patches

Add a Patch

Pull Requests

Add a Pull Request

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2010-11-03 22:01 UTC] felipe@php.net
-Status: Open +Status: Assigned -Package: SPL related +Package: Scripting Engine problem -Assigned To: +Assigned To: dmitry
 [2010-11-03 22:01 UTC] felipe@php.net
I noticed crash is caused by following part:
  $this->_tail->next = $node;
  $this->_tail = $node; // without this line, no crash
 [2010-11-04 09:45 UTC] lifinsky at yandex dot ru
Without this line we will not have LinkedList

Example in JSON Format:

{
    data: 1
    next: {
        data: 2
        next: {
            data: 3
            next: ...
        }
    }
}
 [2011-01-12 08:16 UTC] dmitry@php.net
The crash is caused by C stack overflow during deletion of very deep data structure. It's probably unfixable.
 [2017-10-24 07:55 UTC] kalle@php.net
-Status: Assigned +Status: Open -Assigned To: dmitry +Assigned To:
 
PHP Copyright © 2001-2019 The PHP Group
All rights reserved.
Last updated: Wed Sep 18 11:01:30 2019 UTC