205524 - Reading encrypted mail sent by N7.01 causes infinite memory leak

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Robert Relyea]

When reading large encrypted mail sent by N7.01 or Com 4.7 as one Chunk (instead
of piecemeal like N7), NSS uses all available memory to decrypt the message.

Comment 1

[Robert Relyea]

From ddrinan.
AOL Communicator decodes the mail contents by making *one* call to
NSS_CMSDecoder_Update(). When decoding large messages from N7 (> IMB), this call
takes a long time and exhausts virtual memory. What I see are lots (i.e.
hundreds, maybe thousands) of calls to the followind code in 
nss_cms_decoder_work_data()in nss/lib/smime/cmsdecode.c:
	if (storage->len == 0) {
	    dest = (unsigned char *)PORT_ArenaAlloc(p7dcx->cmsg->poolp, len);
	} else {
	    dest = (unsigned char *)PORT_ArenaGrow(p7dcx->cmsg->poolp, 
				  storage->data,
				  storage->len,
				  storage->len + len);
	}
An interesting fact is that a large message encrypted by an application which
makes a single call (like AOL Communicator) does not
generate as many calls to this function (I estimate somewhere less than 10 calls).

So the questions are: why does N7 generate so many calls to
nss_cms_decoder_work_data(), why does this call exhaust VM in AOL Communicator
and not on N7.

Comment 2

[Robert Relyea]

Individual data in arena's cannot be freed unless the whole arena is freed.
One thing that might be going on here is that the arena in question here is a
temporary arena.

In each call that N7 makes the arena is created used and freed, so it never
really grows. Photon making a single call may be defeating that. One easy
workaround may be simply to break up the photon calls when dealing with S/MIME
messages (call it in a loop with block sizes of 32K each rather than the whole
thing). I would suggest this might be a good solution for M5, then write a
separate bug against NSS for the real issue).

bob

Comment 3

[Robert Relyea]

from ddrinan:
I implemented Bob's proposed solution of breaking the message up into 32K
chunks. Unfortunately the problem still occurs with the exact same symptoms i.e.
mail exhausts VM.

Comment 4

[Robert Relyea]

Attachment: replace arena grow with code that grows memory nLog n, not n!

This patch is now checked into the NSS tip, however Photon is using NSS 3.7.x
and NSS is on NSS 3.9. Since this patch is deep in the CMS code, I suggest not
picking it up for N6 and 'baking' it internally for 'N7' since bugs in the
patch
may cause worse effects than the bug we are trying to fix.

Comment 5

[Robert Relyea]

Here are the size analysis for the two different scenarios...


Original Code:

Total Memory of Message: M
Size of Memory Increment: I
Number of allocation calls: n = M/I
Total Memory Allocated: T=M+ 1/2*M*(M-I)/I
   for I << M, this is approximately:
       T=M*(1+n/2)
   for I = M this is:
       T=M
----------------------------------------------
New Code:

Total Memory of Message: M
Size of Memory Increment: I
Number of alocation steps: n= Log2(M/I+1)
   for I << M This is approximently:
	n=Log2(M/I)
   for I = M this is:
	n=Log2(2) = 1
Total Memory Allocated:4*M-2*I*Log2(M/I+1)
   for I << M This is approximately:
	T=4*M
   for I = M this is:
      T=2*M
-----------------------------------------------

Examples: 

A.Read a Message sent with Netscape 7
which is 2 Meg in size, and uses 1k buffers
M=2M
I=1K

Original Code:
n=2048
T=2M*(1+1024)=2G

New Code:
n=11
T=8M 

B. Read a Message sent with Photon
which is 2Meg is size:
M=2M
I=2M

Original Code:
n=1
T=2M

New Code:
n=1
T=4M

Comment 6

[Robert Relyea]

BTW I think the N7 usually spoon feeds the decoder on the order of 16 bytes at a
time or so, for David's 32K buffers, NSS was still using 32Meg of memory! for
each block.

bob

Comment 7

[Robert Relyea]

Setting Priority & target Mileston (P1, 3.8.1)

Comment 8

[Wan-Teh Chang]

Comment on attachment 123148 [details] [diff] [review]
replace arena grow with code that grows memory nLog n, not n!

This patch is correct, but I'd like to suggest a change
to make it easier to understand.

The NSSCMSDecoderData structure is defined as two SECItem's,

  struct NSSCMSDecoderDataStr {
      SECItem data;	/* must be first */
      SECItem storage;
  };

But it really just needs to be a SECItem plus an unsigned
int that represents the actual buffer length:

  struct NSSCMSDecoderDataStr {
      SECItem data;	/* must be first */
      unsigned int buffer_len;
  };

Another suggested change is to make NSSCMSDecoderData a
new member of the NSSCMSContentUnion, instead of using the
"void * pointer" member of that union.	This would require
modifying the cmst.h header file.

Comment 9

[Robert Relyea]

Attachment: Simplify memory patch by using only a buffer size count rather than a full secitem

This is an incremental patch on top of patch 123148 .
It includes the first part of Wan-Teh's suggestion. I did not implement the
second part because I want to keep the data structure localized to this .c
file, and not accessible from other .c files in this directory.

bob

Comment 10

[Wan-Teh Chang]

Comment on attachment 123322 [details] [diff] [review]
Simplify memory patch by using only a buffer size count rather than a full secitem

Bob, could you declare totalBufferSize as an *unsigned* int
and generate a new patch using cvs diff -u?  Thanks.

Comment 11

[Robert Relyea]

Attachment: Patch 123322 correct as wtc suggested.

Comment 12

[Nelson Bolyard (seldom reads bugmail)]

Now that your latest patch no longer uses two SECItems, another simplifying 
measure would be to use PORT_ArenaGrow to grow it, rather than effectively
duplicating PORT_ArenaGrow in this patch.

Comment 13

[Robert Relyea]

I actually purposefully did NOT use the grow code because I found it confusing.
The name implied that the memory would incrementally increase, which it did not,
leading to the original bug. You can see what is happenning with the current
code much more clearly.

bob

Comment 14

[Wan-Teh Chang]

Comment on attachment 123337 [details] [diff] [review]
Patch 123322 correct as wtc suggested.

r=wtc.	Do you want to implement Nelson's suggestion?

Comment 15

[Nelson Bolyard (seldom reads bugmail)]

The grow code doesn't allocate a new block if it is able to actually make the
previous allocation larger.  If the previously-allocated block that you're
trying to grow is the last one allocated in an arena, and there is adequate room
after it in the arena to grow it to the desired size, then the grow function
will enlarge the old allocation without allocating a whole new block and copying
all the data.
That seems desirable, even if it is slightly less straighforward.  

Comment 16

[Wan-Teh Chang]

Attachment: Use PORT_ArenaGrow

This is an incremental patch that should be applied on top
of the previous two patches.

1. Declare "needLen" as "unsigned int" instead of "int".
2. Use PORT_ArenaGrow except for the initial allocation.

Please review and test this patch.

Do you think we should make a similar change to the
PORT_ArenaGrow calls in cmsencode.c and cmsarray.c to
reduce memory usage?

Comment 17

[Robert Relyea]

I still don't believe the Grow is the right way to go. It confuses any readers
or reviewers into thinking the previous memory is freed. We know in this case it
does not have any benefit (or we wouldn't run into this problem).

I don't find the new code any easier or less complicated the the original patch.

I also think in the longer term, we should be looking at nelson's suggestion of
using a linked list or using the decoder's supplied memory.

bob

Comment 18

[Wan-Teh Chang]

Comment on attachment 123337 [details] [diff] [review]
Patch 123322 correct as wtc suggested.

Requesting mozilla 1.4 approval.  This patch is low risk.  It
reduces the memory usage when decrypting encrypted mail from
O(n^2) to O(n).  It only affects users who read encrypted mail.

Comment 19

[Nelson Bolyard (seldom reads bugmail)]

Bob, if using PORT_ArenaGrow confuses readers, then should we eliminate that 
function?  

I don't think anyone is confused by it.
I find the code that calls PORT_ArenaGrow less confusing than the alternative.

It is a function with a clear purpose.  It *DOES* have benefit in the case
where the the block to be grown is less than the arena's size and the new 
size after growing is also less than or equal to that arena's size.  
It doesn't free the previosuly used space in that case, it *reuses* it.

This is admittedly few cases (the doubling algorithm will quickly exceed the
standard arena size, causing all newly allocated blocks to be in their own 
arenas with no extra space in the arena), but it's more than zero cases.

The alternative code will never reuse the previously used space, even when
it could be reused.

Comment 20

[(not reading, please use [e-mail] instead)]

Comment on attachment 123337 [details] [diff] [review]
Patch 123322 correct as wtc suggested.

a=sspitzer

Comment 21

[Wan-Teh Chang]

Fix (attachment 123148 [details] [diff] [review] and attachment 123337 [details] [diff] [review]) checked into
NSS_3_7_BRANCH (3.7.5), NSS_3_8_BRANCH (3.8.1), NSS_CLIENT_TAG
(mozilla 1.4 final), and the tip (3.9).

Comment 22

[Wan-Teh Chang]

Marked the bug fixed.