Page MenuHomePhabricator

function _DiffEngine->_lcs_pos() indefinite loop
Closed, InvalidPublic


Author: daditto

Hi, I've started investigating my timeout issues when I click on some diffs. And after some debugging, I
came to the following result. There's situation for indefinite loop in _DiffEngine->_lcs_pos() function
on line 930.
I made some debug logging on when the function goes to indefinite loop:
(each of these values are not changed during while loop and stay until the process is killed)

As you see in all these cases while ($beg < $end) will last forever.

This issue is critical, because this hangs the servers up. Few of search engine bots can hang apache
server in a few minutes (if there's no php time limit).

Version: 1.6.x
Severity: critical
Platform: PC



Event Timeline

bzimport raised the priority of this task from to Medium.Nov 21 2014, 9:22 PM
bzimport set Reference to bz7013.
bzimport added a subscriber: Unknown Object (MLST).

We need to know the input text. Can you provide it, or a link to it?

daditto wrote:

The following url drops the server to indefinite loop:

If you tell me where, I can extract the required text from database.

I can't reproduce it on my server. It may be that your copy of DifferenceEngine.php or perhaps even PHP itself is
corrupted. I suggest you try reinstalling MediaWiki, and if that doesn't work, upgrade PHP.

daditto wrote:

No, it may not be. The DifferenceEngine.php is directly from distribuition tar.gz. Neither PHP is corrupted. Why do
you suppose that something is mysteriously wrong, while I'm telling you exactly where the loop becomes indefinite and
what values are required to reproduce it. Why don't you just take a closer look at the code and fix it, so the loop
won't become endless with any values? Well, anyway I got skills to fix it for myself, but what will the other people
think when they meet a trouble like this (
p=6622&sid=a70c2976bdec1b3c5d5e7eb7d4278f63). Another PHP corrupted? This is ridiculous... Guys fix the code, I am
telling you this loop ain't no good. Even a few 'if's could fix it.

Thanks for your time.

dto wrote:

I don't think I got skills to replicate the loop, perhaps somebody could help
out? (Especially since the wikitext for the page is indefinite; I can't view it.)

The link seems to work as well.

daditto wrote:

I've just checked the loop at Windows computer and it seems to work smoothly.

The problem is with:

$mid = (int)(($beg + $end) / 2);

with values $beg=1 and $end=2, on windows pc $mid becomes 1 and it becomes 2 on linux PC.
I guess it's the difference on how (int) works on different PHP/OS versions.

To test it I put the following script on my server:

echo "orig=".(($beg + $end) / 2).' ';
echo "int=";
echo (int)(($beg + $end) / 2);
I think it's better to replace (int) with a safer function.

ayg wrote:

float() should be what's used, if this is actually the case.

daditto wrote:

I guess floor(), not float()

dto wrote:

Yeah, he probably meant floor().

Anyways, Tim Starling's original suggestion (upgrade PHP) should fix it. My
server's running PHP 5.1.4 on Win XP Pro SP2 (the one included with XAMPP), and
the example script outputs "orig=1.5 int=1" as expected. You're running on PHP

ayg wrote:

(In reply to comment #8)

I guess floor(), not float()

D'oh, yes. That's what I meant to type.

daditto wrote:

(In reply to comment #9)

Anyways, Tim Starling's original suggestion (upgrade PHP) should fix it. Myserver's running PHP 5.1.4 on Win XP Pro

SP2 (the one included with XAMPP), andthe example script outputs "orig=1.5 int=1" as expected. You're running on

Well, guys. The PHP 4.4.3 was released on [03-Aug-2006] and it's the latest PHP4 version. It may happen, that latest
PHP5 branch version will come with the same problem. I am not asking for solution of my problem, I've already floor-ed
it :) Think about the others. I guess you have some people that use PHP4 branch too.

dto wrote:

(In reply to comment #11)

Think about the others. I guess you have some people that use PHP4 branch too.

I'm pretty sure that 1.7.x and later do not support php4, but I guess this could
be fixed in the 1.6.x branch.

daditto wrote:

This SHOULD be fixed. Please read warning at
"Never cast an unknown fraction to integer, as this can sometimes lead to unexpected results."

It's a bad practice. And you can never know what will happen with a new PHP5 release. It may also be OS dependent. So
if you use same (int) conversions in a 1.7.x version, you should think about fixing it too. Thanks.

dto wrote:

(In reply to comment #13)

This SHOULD be fixed. Please read warning at

"Never cast an unknown fraction to integer, as this can sometimes lead to

unexpected results."

That warning still applies even if you use floor(). floor((0.1+0.7)*10),
intval((0.1+0.7)*10), (int)((0.1+0.7)*10) all evaluate to 7. The only way to get
around that is to use integers.

ayg wrote:

No, floor() returns a float, not an integer. The warning doesn't apply. The
example does apply, but seems to be irrelevant to the bug in question.

daditto wrote:

Allright. I think you should think about rewriting this loop in the way that the indefinite loop won't be possible.
Sounds reasonable to me :)

dto wrote:

(In reply to comment #15)

No, floor() returns a float, not an integer.

I chose to interpret "7." as "7." for floor and as "7"+[period] for intval and
(int). =P

The warning doesn't apply.

If you click on the link, it does.

ayg wrote:

Well, the warning "Never cast an unknown fraction to integer" doesn't apply,
because we aren't casting to integer. The warning "never trust floating number
results to the last digit" doesn't apply, either, since the issue is floor(($beg
+ $end) / 2) where $beg and $end are integers (or floats with no decimal
places). You aren't trusting the last digit; the last digit could be 1 or 5 or
7, it's being dropped regardless. You're only trusting the *second*-to-last
digit, namely the unit place, and that's safe. If you disagree, please suggest
what could go wrong in the loop in question by flooring.

dto wrote:

I forgot to say that I agree with "The example does apply, but seems to be
irrelevant to the bug in question." I just wanted to say something about the
float() return value type technicality.

Yes, I agree that the unit digit can be trusted in this case, since we're only
dividing by 2. However, I'd rather use intval instead of floor if intval works
correctly (i.e. rounds down) in php4 (Dmitriy?), since intval returns an
integer, and that's the type that $mid, $beg, and $end are supposed to be.

daditto wrote:

intval() has the same effect (rounds up) as (int) on my server. I think that if you decide to stick to integers, you
should assume that it maybe rounded up and somehow modify the loop accordingly, so it won't be indefinite.

Division by two is exact with binary floating point numbers, which is what these
are, so the result of adding two integers and dividing by two is exact and
reproducible. According to the PHP manual:

"When converting from float to integer, the number will be rounded towards zero."

so intval(0.8) and intval(0.4) should both produce zero. So this is a PHP bug.
That's ok, we're accustomed to working around PHP bugs, I'll change it to
floor() in DifferenceEngine.php.

Fractions such as 0.7 and 0.3 cannot be represented exactly in binary form, but
all of the integers can be, as long as they fit in the mantissa. Division by two
can always be represented exactly, it's just a decrement of the exponent. So
floor($n+0.5) where $n is an integer produces a floating-point number which is
exactly equal to $n, as long as $n is less than about 2^51.

This is all quite complex, and I can understand the authors of the PHP manual
wanting to put a bit of fear into programmers who don't understand it. But it's
complete nonsense to suggest that conversions from floating point to integer
should be avoided entirely. PHP doesn't have an integer division operator, so
you couldn't avoid them if you wanted to.

I've reported this as a PHP bug at, and
it's being met with the expected amount of incredulity. I can't reproduce it.
Dmitriy B, can you tell us whether floor(0.6) returns 0 or 1?

daditto wrote:

I've created a page for this purposes ( It produces the following results:


The link to phpinfo() is also included there.

daditto wrote:

I've contacted tony2001 at There seem to be a problem with compiler or somehow the way php was compiled on
the server. I'm trying to locate where the problem is exactly. Anyway this issue has nothing to wikimedia and this bug
can be closed here. Thank you all for your time and cooperation.