Last modified: 2010-05-15 15:56:42 UTC

Wikimedia Bugzilla is closed!

Wikimedia has migrated from Bugzilla to Phabricator. Bug reports should be created and updated in Wikimedia Phabricator instead. Please create an account in Phabricator and add your Bugzilla email address to it.
Wikimedia Bugzilla is read-only. If you try to edit or create any bug report in Bugzilla you will be shown an intentional error message.
In order to access the Phabricator task corresponding to a Bugzilla report, just remove "static-" from its URL.
You could still run searches in Bugzilla or access your list of votes but bug reports will obviously not be up-to-date in Bugzilla.
Bug 7013 - function _DiffEngine->_lcs_pos() indefinite loop
function _DiffEngine->_lcs_pos() indefinite loop
Status: RESOLVED INVALID
Product: MediaWiki
Classification: Unclassified
History/Diffs (Other open bugs)
1.6.x
PC All
: Normal critical with 1 vote (vote)
: ---
Assigned To: Nobody - You can work on this!
:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2006-08-15 04:38 UTC by Dmitriy B
Modified: 2010-05-15 15:56 UTC (History)
0 users

See Also:
Web browser: ---
Mobile Platform: ---
Assignee Huggle Beta Tester: ---


Attachments

Description Dmitriy B 2006-08-15 04:38:11 UTC
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)
beg=1,mid=2,end=2,this->seq[mid]=2,ypos=0
beg=1,mid=2,end=2,this->seq[mid]=6,ypos=5
beg=3,mid=4,end=4,this->seq[mid]=4,ypos=2
beg=13,mid=14,end=14,this->seq[mid]=22,ypos=10
beg=11,mid=12,end=12,this->seq[mid]=20,ypos=9

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).
Comment 1 Tim Starling 2006-08-15 04:52:42 UTC
We need to know the input text. Can you provide it, or a link to it?
Comment 2 Dmitriy B 2006-08-15 04:58:38 UTC
The following url drops the server to indefinite loop:

http://www.pharmdatabase.org/index.php?
title=The_Effects_of_Tramadol_and_Morphine_on_Immune_Responses_and_Pain_After_Surgery_in_Cancer_Patients&diff=prev&ol
did=1382


If you tell me where, I can extract the required text from database.
Comment 3 Tim Starling 2006-08-15 05:20:10 UTC
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. 
Comment 4 Dmitriy B 2006-08-15 05:50:59 UTC
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 (http://haiku-os.org/forums/viewtopic.php?
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.
Comment 5 Dan Li 2006-08-15 17:12:50 UTC
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.
Comment 6 Dmitriy B 2006-08-15 17:32:16 UTC
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: http://www.pharmdatabase.org/qq.php
--source--
$beg=1;
$end=2;

echo "orig=".(($beg + $end) / 2).' ';
echo "int=";
echo (int)(($beg + $end) / 2);
--source--
I think it's better to replace (int) with a safer function.
Comment 7 Aryeh Gregor (not reading bugmail, please e-mail directly) 2006-08-15 17:34:18 UTC
float() should be what's used, if this is actually the case.
Comment 8 Dmitriy B 2006-08-15 17:44:55 UTC
I guess floor(), not float()
Comment 9 Dan Li 2006-08-15 17:47:29 UTC
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
4.4.3.
Comment 10 Aryeh Gregor (not reading bugmail, please e-mail directly) 2006-08-15 17:48:12 UTC
(In reply to comment #8)
> I guess floor(), not float()

D'oh, yes.  That's what I meant to type.
Comment 11 Dmitriy B 2006-08-15 17:59:01 UTC
(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 
PHP4.4.3.

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. 
Comment 12 Dan Li 2006-08-15 18:03:11 UTC
(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.
Comment 13 Dmitriy B 2006-08-15 18:15:45 UTC
This SHOULD be fixed. Please read warning at 
http://www.php.net/manual/en/language.types.integer.php#language.types.integer.casting
"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.
Comment 14 Dan Li 2006-08-15 18:24:32 UTC
(In reply to comment #13)
> This SHOULD be fixed. Please read warning at 
>
http://www.php.net/manual/en/language.types.integer.php#language.types.integer.casting
> "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.
Comment 15 Aryeh Gregor (not reading bugmail, please e-mail directly) 2006-08-15 18:29:10 UTC
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.
Comment 16 Dmitriy B 2006-08-15 18:30:44 UTC
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 :)
Comment 17 Dan Li 2006-08-15 18:34:19 UTC
(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.
http://www.php.net/manual/en/language.types.float.php#warn.float-precision
Comment 18 Aryeh Gregor (not reading bugmail, please e-mail directly) 2006-08-15 18:40:55 UTC
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.
Comment 19 Dan Li 2006-08-15 19:03:15 UTC
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.
Comment 20 Dmitriy B 2006-08-15 19:19:21 UTC
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.
Comment 21 Tim Starling 2006-08-22 17:07:50 UTC
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.
Comment 22 Tim Starling 2006-08-22 17:54:46 UTC
I've reported this as a PHP bug at http://bugs.php.net/bug.php?id=38548, 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? 
Comment 23 Dmitriy B 2006-08-22 18:09:54 UTC
I've created a page for this purposes (http://www.pharmdatabase.org/intval/). It produces the following results: 

intval(0.9)=int(1) 
floor(0.6)=float(0) 

The link to phpinfo() is also included there.
Comment 24 Dmitriy B 2006-08-22 21:53:50 UTC
I've contacted tony2001 at php.net. 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.

Note You need to log in before you can comment on or make changes to this bug.


Navigation
Links