Skip Menu |
 
Ticket metadata
The Basics
Id: 2100
Status: resolved
Priority: 0/
Queue: OpenSSL-Bugs

Custom Fields
Milestone: (no value)
Subsystem: (no value)
Severity: (no value)
Broken in: (no value)

People
Owner: Nobody in particular
Requestors: Greg
James Baker
Cc:
AdminCc:

More about the requestors

Greg

Comments about this user: No comment entered about this user
Groups this user belongs to
  • Everyone
  • Unprivileged

James Baker

Comments about this user: No comment entered about this user
Groups this user belongs to
  • Everyone
  • Unprivileged

New reminder:
Subject:
Owner:
Due:

Dates
Created: Fri Nov 13 09:13:31 2009
Starts: Not set
Started: Not set
Last Contact: Tue Sep 09 20:50:24 2014
Due: Not set
Closed: Tue Sep 09 20:50:24 2014
Updated: Tue Sep 09 20:50:25 2014 by Rich Salz



Subject: RAND_poll can be incredibly slow on Windows7 due to Heap32Next
Date: Fri, 13 Nov 2009 02:20:00 +0000
To: "rt@openssl.org" <rt@openssl.org>
From: James Baker <jbaker@tableausoftware.com>
Download rand_win.cpp
text/plain 9.7k

Message body is not shown because sender requested not to inline it.

Download (untitled) / with headers
text/plain 1.3k
bug report (first time, please forgive any faux-paus)
64-bit Windows 7 Ultimate
affects openssl/crypto/rand/rand_win.c from at least 2005 (v1.4.5) to current 0.9.8 and 1.0.0

Even when doing the absolute minimum heap traversal, RAND_poll walks the first 80 entries of the first heap list to generate entropy without checking how much time it's taking. This can easily take more than a minute to execute with a moderate-to-large heap size.

Expected behavior: RAND_poll needs to be limited to taking only a few seconds while still gathering enough entropy. Suggested remedies: A) find an alternate method of heap list traversal or B) find an alternate source of entropy

The cause is the usage of Heap32Next: my testing shows that performance of Heap32Next is linear w/r/t the number of heap entries in the first heap list. Each invocation of Heap32Next (on Win7, contrasted with XP and Vista) can easily take more than 1 second - graphs of the performance of Heap32Next are here: http://thenewjamesbaker.blogspot.com/2009/11/performance-of-heap32next-on-64-bit.html

This report springs from this openssl-users thread: http://groups.google.com/group/mailing.openssl.users/browse_thread/thread/b38d72135da93951/d3cf46fe6311ddbb

Attached is rand_win.cpp, a test harness I used in MSVC2005 to instrument a stripped-down version of RAND_poll.
Subject: RE: [openssl.org #2100] AutoReply: RAND_poll can be incredibly slow on Windows7 due to Heap32Next
Date: Fri, 13 Nov 2009 22:38:17 +0000
To: "rt@openssl.org" <rt@openssl.org>
From: James Baker <jbaker@tableausoftware.com>

Message body is not shown because it is too large.

Subject: RE: [openssl.org #2100] AutoReply: RAND_poll can be incredibly slow on Windows7 due to Heap32Next
Date: Sat, 9 Jan 2010 00:55:59 +0000
To: "rt@openssl.org" <rt@openssl.org>
From: James Baker <jbaker@tableausoftware.com>
Download (untitled) / with headers
text/plain 1.1k
I don't have time to write for you a new entropy source to replace the heap walking.
I've patched my local rand_win.c to time-limit the inner loop in the same manner as the outer, and do not plan to spend any more time on this issue.

James

P.S. I am surprised that no one else uses OpenSSL on Windows enough to notice this bug? The test code attached to this ticket performs the same on every physical/VM Win7 box I can get my hands on.

I went and searched for responses, the only thing I found was this response to the dev list, which I am not on:

Show quoted text
-----Original Message-----
James Baker via RT wrote:
[SNIP]

James,
you post is interesting to me but I would like to ask you to post
unified diff format with changes (please search internet for "unified
diff").
It you environment is limited please use some public available/free
sites for code review.

ROumen
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-...@openssl.org
Automated List Manager majord...@openssl.org
Subject: RAND_Poll is very slow on Windows
Date: Mon, 8 Feb 2010 09:22:46 -0800
To: rt@openssl.org
From: ghazel@gmail.com
Download (untitled) / with headers
text/plain 910b
I'm using "Library: OpenSSL 0.9.8l 5 Nov 2009" on Windows 7.

RAND_Poll is taking a -very- long time to complete (~80 seconds) on my
process which only has 80MB (or so) allocated. By sampling the stack,
I can see RAND_Poll is walking the Win32 Heap. This problem occurs
with many tiny allocations instead of few large allocations.

I bumped my head on this while profiling a Ruby on Rails application
of all things - the first request would hang for almost two minutes.

What is the right way to fix this? Modify the Ruby openssl module to
call RAND_Poll as soon as it initializes OpenSSL? Fix RAND_Poll to
walk fewer steps on the Heap? Fix RAND_Poll to walk faster? Fix
RAND_Poll to use some other strategy for its task than Heap walking?

You can see the theme here, which caused me to file this request. I
also filed it with Ruby, however, just in case:
http://redmine.ruby-lang.org/issues/show/2721

-Greg
Download (untitled) / with headers
text/plain 1.2k
Show quoted text
> [ghazel@gmail.com - Tue Feb 09 16:10:14 2010]:
>
> I'm using "Library: OpenSSL 0.9.8l 5 Nov 2009" on Windows 7.
>
> RAND_Poll is taking a -very- long time to complete (~80 seconds) on my
> process which only has 80MB (or so) allocated. By sampling the stack,
> I can see RAND_Poll is walking the Win32 Heap. This problem occurs
> with many tiny allocations instead of few large allocations.
>

I don't have access to Windows 7 at the moment so I can't test this
myself. I've heard that the Windows 7 behaviour is not a bug and the
only reason previous versions weren't so slow is that *they* are buggy.

I'd suggest you try one workaround mentioned above. Include a time limit
on the inner loop. You can do this by duplicating the GetTickCount line.
I.e. in rand_win.c at about line 530 you add the line indicated:

while (heap_next(&hentry)
--------------> && (!good || (GetTickCount()-starttime)<MAXDELAY)
&& --entrycnt > 0);

If that makes the delay more tolerable I'll commit it as a temporary fix
for now. Longer term we need to find an alternative technique for
additional entropy gathering.

Steve.
--
Dr Stephen N. Henson. OpenSSL project core developer.
Commercial tech support now available see: http://www.openssl.org
CC: jbaker@tableausoftware.com, openssl-dev@openssl.org
Subject: Re: [openssl.org #2100] RAND_poll can be incredibly slow on Windows7 due to Heap32Next
Date: Sat, 13 Feb 2010 08:13:51 -0800
To: rt@openssl.org
From: ghazel@gmail.com
Download (untitled) / with headers
text/plain 1022b
Show quoted text
> I don't have access to Windows 7 at the moment so I can't test this
> myself. I've heard that the Windows 7 behaviour is not a bug and the
> only reason previous versions weren't so slow is that *they* are buggy.
>
> I'd suggest you try one workaround mentioned above. Include a time limit
> on the inner loop. You can do this by duplicating the GetTickCount line.
> I.e. in rand_win.c at about line 530 you add the line indicated:
>
>                while (heap_next(&hentry)
> -------------->         && (!good || (GetTickCount()-starttime)<MAXDELAY)
>                                                        && --entrycnt > 0);
>
> If that makes the delay more tolerable I'll commit it as a temporary fix
> for now. Longer term we need to find an alternative technique for
> additional entropy gathering.

I do not yet have an OpenSSL build environment set up. If you have any
Windows environment, could you compile a DLL with the change, and I'll
test it on Windows 7?

-Greg
CC: openssl-dev@openssl.org, ghazel@gmail.com
Subject: Re: [openssl.org #2100] RAND_poll can be incredibly slow on Windows7 due to Heap32Next
Date: Mon, 15 Feb 2010 03:21:46 +0100
To: rt@openssl.org
From: Mounir IDRASSI <mounir.idrassi@idrix.net>
Download (untitled) / with headers
text/plain 1.6k
Hi,

Just in case you still don't have a version of libeay32.dll with the
patch, I'm attaching with this email the one I have just compiled by
applying the suggested patch to the latest snapshot of the 0.9.8 source
tree.

Cheers,

--
Mounir IDRASSI
IDRIX
http://www.idrix.fr


On 2/13/2010 5:13 PM, ghazel@gmail.com wrote:
Show quoted text
>> I don't have access to Windows 7 at the moment so I can't test this
>> myself. I've heard that the Windows 7 behaviour is not a bug and the
>> only reason previous versions weren't so slow is that *they* are buggy.
>>
>> I'd suggest you try one workaround mentioned above. Include a time limit
>> on the inner loop. You can do this by duplicating the GetTickCount line.
>> I.e. in rand_win.c at about line 530 you add the line indicated:
>>
>> while (heap_next(&hentry)
>> --------------> && (!good || (GetTickCount()-starttime)<MAXDELAY)
>> && --entrycnt> 0);
>>
>> If that makes the delay more tolerable I'll commit it as a temporary fix
>> for now. Longer term we need to find an alternative technique for
>> additional entropy gathering.
>>
> I do not yet have an OpenSSL build environment set up. If you have any
> Windows environment, could you compile a DLL with the change, and I'll
> test it on Windows 7?
>
> -Greg
> ______________________________________________________________________
> OpenSSL Project http://www.openssl.org
> Development Mailing List openssl-dev@openssl.org
> Automated List Manager majordomo@openssl.org
>

--
--
Mounir IDRASSI
IDRIX
http://www.idrix.fr
Download libeay32.7z
application/octet-stream 350.3k

Message body not shown because it is not plain text.

Download rand_win.diff
text/plain 671b

Message body is not shown because sender requested not to inline it.

CC: rt@openssl.org, openssl-dev@openssl.org
Subject: Re: [openssl.org #2100] RAND_poll can be incredibly slow on Windows7 due to Heap32Next
Date: Sat, 20 Feb 2010 10:36:52 -0800
To: Mounir IDRASSI <mounir.idrassi@idrix.net>
From: ghazel@gmail.com
Download (untitled) / with headers
text/plain 2.1k
Thank you!

This is a vast improvement for me. What used to take 75 seconds now
takes 2. It still seems to scale with the number of allocations, so I
can make it take 20 seconds by doing 10 times the allocations.
However, that takes 750 seconds with the old version.

-Greg

On Sun, Feb 14, 2010 at 6:21 PM, Mounir IDRASSI
<mounir.idrassi@idrix.net> wrote:
Show quoted text
> Hi,
>
> Just in case you still don't have a version of libeay32.dll with the patch,
> I'm attaching with this email the one I have just compiled by applying the
> suggested patch to the latest snapshot of the 0.9.8 source tree.
>
> Cheers,
>
> --
> Mounir IDRASSI
> IDRIX
> http://www.idrix.fr
>
>
> On 2/13/2010 5:13 PM, ghazel@gmail.com wrote:
>>>
>>> I don't have access to Windows 7 at the moment so I can't test this
>>> myself. I've heard that the Windows 7 behaviour is not a bug and the
>>> only reason previous versions weren't so slow is that *they* are buggy.
>>>
>>> I'd suggest you try one workaround mentioned above. Include a time limit
>>> on the inner loop. You can do this by duplicating the GetTickCount line.
>>> I.e. in rand_win.c at about line 530 you add the line indicated:
>>>
>>>                while (heap_next(&hentry)
>>> -------------->           &&  (!good ||
>>> (GetTickCount()-starttime)<MAXDELAY)
>>>                                                        &&  --entrycnt>
>>>  0);
>>>
>>> If that makes the delay more tolerable I'll commit it as a temporary fix
>>> for now. Longer term we need to find an alternative technique for
>>> additional entropy gathering.
>>>
>>
>> I do not yet have an OpenSSL build environment set up. If you have any
>> Windows environment, could you compile a DLL with the change, and I'll
>> test it on Windows 7?
>>
>> -Greg
>> ______________________________________________________________________
>> OpenSSL Project                                 http://www.openssl.org
>> Development Mailing List                       openssl-dev@openssl.org
>> Automated List Manager                           majordomo@openssl.org
>>
>
> --
> --
> Mounir IDRASSI
> IDRIX
> http://www.idrix.fr
>
>
Subject: Re: [openssl.org #2100] RAND_poll can be incredibly slow on Windows7 due to Heap32Next
Date: Sat, 08 May 2010 12:33:20 -0700
To: rt@openssl.org,openssl-dev@openssl.org
From: Roger Fulton <roger@personaltechaid.com>
To find (at least) two people who are still having very slow response, even with the 1.0.0 version from www.slproweb.com/products/Win32OpenSSL.html , see the thread at http://eudorabb.qualcomm.com/showthread.php?t=14440 . In that forum, I am user "burningbush," and my first post to that thread is message #8.

The specific binary I tested with is the one contained in this package:
www.slproweb.com/download/Win32OpenSSL_Light-1_0_0.exe

OS: Windows 7 Ultimate, 64-bit. Eudora: 7.1.0.9, paid mode.

- Roger Fulton

Show quoted text
>Sat Feb 20 19:37:29 2010 ghazel@gmail.com - Correspondence added
>CC: rt@openssl.org, openssl-dev@openssl.org
>Subject: Re: [openssl.org #2100] RAND_poll can be incredibly slow on Windows7 due to Heap32Next
>Date: Sat, 20 Feb 2010 10:36:52 -0800
>To: Mounir IDRASSI <mounir.idrassi@idrix.net>
>From: ghazel@gmail.com
>Download (untitled)
>text/plain 2.1k
>Thank you!
>
>This is a vast improvement for me. What used to take 75 seconds now
>takes 2. It still seems to scale with the number of allocations, so I
>can make it take 20 seconds by doing 10 times the allocations.
>However, that takes 750 seconds with the old version.
>
>-Greg
>
>On Sun, Feb 14, 2010 at 6:21 PM, Mounir IDRASSI
><mounir.idrassi@idrix.net> wrote:
>> Hi,
>>
>> Just in case you still don't have a version of libeay32.dll with the patch,
>> I'm attaching with this email the one I have just compiled by applying the
>> suggested patch to the latest snapshot of the 0.9.8 source tree.
>>
>> Cheers,
>>
>> --
>> Mounir IDRASSI
>> IDRIX
>> http://www.idrix.fr
>>
>>
>> On 2/13/2010 5:13 PM, ghazel@gmail.com wrote:
>>>>
>>>> I don't have access to Windows 7 at the moment so I can't test this
>>>> myself. I've heard that the Windows 7 behaviour is not a bug and the
>>>> only reason previous versions weren't so slow is that *they* are buggy.
>>>>
>>>> I'd suggest you try one workaround mentioned above. Include a time limit
>>>> on the inner loop. You can do this by duplicating the GetTickCount line.
>>>> I.e. in rand_win.c at about line 530 you add the line indicated:
>>>>
>>>> while (heap_next(&hentry)
>>>> --------------> && (!good ||
>>>> (GetTickCount()-starttime)<MAXDELAY)
>>>> && --entrycnt>
>>>> 0);
>>>>
>>>> If that makes the delay more tolerable I'll commit it as a temporary fix
>>>> for now. Longer term we need to find an alternative technique for
>>>> additional entropy gathering.
>>>>
>>>
>>> I do not yet have an OpenSSL build environment set up. If you have any
>>> Windows environment, could you compile a DLL with the change, and I'll
>>> test it on Windows 7?
>>>
>>> -Greg
>>> ______________________________________________________________________
>>> OpenSSL Project http://www.openssl.org
>>> Development Mailing List openssl-dev@openssl.org
>>> Automated List Manager majordomo@openssl.org
>>>
>>
>> --
>> --
>> Mounir IDRASSI
>> IDRIX
>> http://www.idrix.fr
>>
>>
Subject: [openssl.org #2100] RAND_poll can be incredibly slow on Windows7 due to Heap32Next
Date: Wed, 11 Jan 2012 10:41:19 +0100
To: rt@openssl.org
From: Andre Heinecke <aheinecke@intevation.de>
Download (untitled) / with headers
text/plain 400b
The workaround for this issue is hat was added for 0.9.8m is only applied in
an #ifdef _MSC_VER codebranch.
This bug is also triggered when building openssl in mingw so it should be
applied for this, too. It might account for reports that users are still
running into this problem with recent versions.

Attached patch for crytpo/rand/rand_win.c adds the timeout check there, too.

Regards,
Andre

Message body is not shown because sender requested not to inline it.

timer-limiting for windows heap-walking, etc., seems to have been implemented some time ago.
Closing ticket.
-- 
Rich Salz, OpenSSL dev team; rsalz@openssl.org