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: 2021-07-14 12:00 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: cmb (profile)
Status: Wont fix Package: Scripting Engine problem
PHP Version: 5.3.3 OS: Vista, Linux
Private report: No CVE-ID: None
Welcome back! If you're the original bug submitter, here's where you can edit the bug or add additional notes.
If you forgot your password, you can retrieve your password here.
Password:
Status:
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

Pull Requests

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:
 [2021-07-14 12:00 UTC] cmb@php.net
-Status: Open +Status: Wont fix -Assigned To: +Assigned To: cmb
 [2021-07-14 12:00 UTC] cmb@php.net
> The crash is caused by C stack overflow during deletion of very
> deep data structure. It's probably unfixable.

That.
 
PHP Copyright © 2001-2025 The PHP Group
All rights reserved.
Last updated: Thu Jul 03 00:01:35 2025 UTC