#2100: RAND_poll can be incredibly slow on Windows7 due to Heap32Next

# Fri Nov 13 09:13:31 2009 James Baker - Ticket created

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.

Download (untitled) / with headers
text/html 5.8k

# Fri Nov 13 23:38:43 2009 James Baker - Correspondence added

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>

Download (untitled) / with headers
text/plain 12k

Message body is not shown because it is too large.

# Sat Jan 09 01:59:39 2010 James Baker - Correspondence added

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

# Tue Feb 09 16:10:14 2010 Greg - Ticket #2165: Ticket created

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

# Tue Feb 09 19:03:44 2010 Stephen Henson - Ticket #2165: Merged into ticket #2100

# Tue Feb 09 19:03:44 2010 Stephen Henson - Merged into ticket #2100

# Sat Feb 13 14:43:55 2010 Stephen Henson - Correspondence added

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

# Sat Feb 13 14:43:56 2010 The RT System itself - Status changed from 'new' to 'open'

# Sat Feb 13 17:14:26 2010 Greg - Correspondence added

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

# Mon Feb 15 03:28:37 2010 "Mounir IDRASSI" - Correspondence added

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.

# Sat Feb 20 19:37:29 2010 Greg - 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) / 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
>
>

# Sat May 08 22:12:16 2010 Roger Fulton - Correspondence added

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>

Download (untitled) / with headers
text/plain 3k

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
>>
>>

# Wed Jan 11 10:48:37 2012 Andre Heinecke - Correspondence added

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

Download openssl-workaround-bug-2100-mingw.diff
text/x-diff 507b

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