191682 - Cookie manager uses O(2n^2) algorithm to display cookies

Status: RESOLVED FIXED

(Core :: Networking: Cookies, defect)

Description

[[e-mail]]

So um... I can't believe we do this.

We have an O(2n^2) cookie list traversal algorithm, for displaying the cookies
in cookie manager. So for 300 cookies (the maximum allowed), we perform ~180,000
operations instead of ~300.

The fix is trivial. 6 line patch attached. Tested, works fine.

A brief summary of how we manage to do this:
1) The js code for the cookie manager calls
nsCookieEnumerator::HasMoreElements() for each cookie in the list. In turn, this
calls COOKIE_Count(), which you'd think just returns the number of cookies in
the list (an O(1) operation). But it actually calls
cookie_RemoveExpiredCookies(), which traverses the entire list and removes
expired cookies. So we have O(n^2).

2) Furthermore, the js code then calls ::GetNext(), which calls
COOKIE_Enumerate() to get the specified cookie. Which then calls COOKIE_Count()
again. Sigh...

The fix just adds a member variable to nsCookieEnumerator, which stores the
result of COOKIE_Count() in the ctor. So we still remove expired cookies, but
only each time you load the cookie manager, not as we display each cookie. Note
that a |new nsCookieEnumerator| is instanced by nsCookieManager::GetEnumerator()
every time you open the cookie manager, so the fix works fine.

Comment 1

[[e-mail]]

Attachment: 6-line fix

Comment 2

[[e-mail]]

Low-hanging fruit, should result in a noticeable speedup of the cookie manager.

Setting blocking1.3b?, marking severity major.

Comment 3

[[e-mail]]

biesi asked me why I removed the bounds check in COOKIE_Enumerate (last change
in the diff).

It was never actually necessary - probably just a placeholder to force removal
of expired cookies (though it must have been obvious to whoever put it there,
that that'd result in O(n^2)...)

We do a bounds check on the very next line (the diff doesn't have enough
context). See
http://lxr.mozilla.org/seamonkey/source/extensions/cookie/nsCookies.cpp#2049. I
put the cookie_list nullcheck there just to be pedantic, so we don't end up
dereferencing a null list.

requesting sr=darin

Comment 4

[Boris Zbarsky [:bzbarsky]]

> the diff doesn't have enough context

"diff -u8" (or -u6 or -u10 or whatever provides reasonable context; -u3 almost
never does) is your friend.  More importantly, it is the reviewer's friend.  A
befriended reviewer is a nice friendly reviewer. ;)

Comment 5

[[e-mail]]

Attachment: Same patch w/ diff -u8

>"diff -u8" (or -u6 or -u10 or whatever provides reasonable context; -u3 almost

>never does) is your friend.  More importantly, it is the reviewer's friend.  A

>befriended reviewer is a nice friendly reviewer. ;)

Yeah, I'm just being lazy ;)

patch with diff -u8 attached, to keep reviewers nice and friendly.

Comment 6

[Michiel van Leeuwen (email: mvl+moz@)]

Comment on attachment 113375 [details] [diff] [review]
Same patch w/ diff -u8

>-        nsCookieEnumerator() : mCookieCount(0) 
>+        nsCookieEnumerator() : mCookieAt(0),
>+                               mCookieCount(COOKIE_Count())
>         {
>         }
> 
>         NS_IMETHOD HasMoreElements(PRBool *result) 
>         {
>-            *result = COOKIE_Count() > mCookieCount;
>+            *result = mCookieCount > mCookieAt;
>             return NS_OK;
>         }

This looks like a possible race condition to me. IS a cookie is removed while
you are looping over the list, HasMoreElements can return true, while in fact
there are no more cookies.
And why not just call the expire function from the constructor? That would be
less obscure.

Comment 7

[Christian :Biesinger (don't email me, ping me on IRC)]

mvl: hmm, that is true, however GetNext would return a failure, because
COOKIE_Enumerate checks the current, real cookie count.

Comment 8

[[e-mail]]

Right. COOKIE_Enumerate always does an accurate bounds check, so if the list
shrunk somehow, it'll just return an NS_ERROR.

We could call RemoveExpiredCookies from the constructor, and then use the
realtime list count in HasMoreElements also. But then you just shift the race
from existing while the list is traversed, to existing every time between the
call to HasMoreElements and GetNext. Note that the current impl is sensitive to
the latter also.

I think whatever you do, there's going to be a vulnerability to the list
changing.  I'm not even sure why we're checking the count beforehand; we should
just be traversing the list until we reach the end, and returning a null cookie
to let the caller know, because any count is subject to change. The only true
way to make the cookiemanager display an accurate list under all circumstances
would be to lock the list, or set up cookiemanager to receive event
notifications when the list changes... neither are within the scope of this patch ;)

Comment 9

[[e-mail]]

hmm, which raises a quick question. Should we remove the assert in
COOKIE_Enumerate for "bad cookie index"? If it can happen during "ordinary
circumstances", perhaps it should just return an error, without asserting.

Comment 10

[Darin Fisher]

Comment on attachment 113361 [details] [diff] [review]
6-line fix

>Index: extensions/cookie/nsCookieManager.cpp

>+        nsCookieEnumerator() : mCookieAt(0),
>+                               mCookieCount(COOKIE_Count())

nit: how about "mCookieIndex" instead?	(i.e., the index of the enumeration)


>         NS_IMETHOD HasMoreElements(PRBool *result) 

so, this class is just reusing the nsISimpleEnumerator interface.  you should
double check all callers of this interface to make sure they will tolerate an
inconsistency between HasMoreElements and GetNext (i.e., make sure they trap
the return value of GetNext!)

also, what if someone loads a webpage that adds cookies while the cookie
manager is visible?  is it possible that the enumerator would then miss some
newly added cookies?

perhaps we should just fix this bug by making COOKIE_Count() return a cached
result.  other COOKIE_ methods (like the add and remove ones) could flag the
cached COOKIE_Count value as stale.  though... that could probably wait for
now if you are confident that this current patch will not regress anything.


>+        PRInt32 mCookieAt, mCookieCount;

nit:
	PRInt32 mCookie{At,Index};
	PRInt32 mCookieCount;

Comment 11

[Boris Zbarsky [:bzbarsky]]

> to make sure they will tolerate an inconsistency between HasMoreElements and
> GetNext

Erm... if we can avoid this inconsistency by caching the count in COOKIE_Count,
that would be vastly more preferable...  (I know the interface does not actually
specify that GetNext() will be successful after a true return from
HasMoreElements, but....)

Comment 12

[[e-mail]]

Yeah, you're right about the double-checking. See

http://lxr.mozilla.org/seamonkey/source/extensions/wallet/cookieviewer/CookieViewer.js#202

The JS won't die if a null cookie is returned from GetNext, but it sure doesn't
handle it properly. Adding an |if (!nextCookie) {break;}| inside the while loop
should take care of that. We probably shouldn't be using the nsISimpleEnumerator
interface anyway, since the list can change during enumeration, but that can
wait for a proper rewrite.

Per darin and bz's comments: COOKIE_Count() still encapsulates the removal of
expired cookies, but we could make a new function COOKIE_CountWithoutExpiring().
This would just return cookie_list->Count(). Note that it still doesn't solve
the underlying problem... if a cookie is added/removed, the indexing could still
get tainted. It'll just make it less likely to run off the end of the list - we
still need the nullcheck mentioned above.

Locking the list while enumerating (or copying it temporarily) is probably the
right solution, but that can wait...

darin, bz, what do you think?

Comment 13

[[e-mail]]

Attachment: Version 2

changes:
1) added nullcheck to js.
2) added new COOKIE_CountWithoutExpiring() function (yeah, I know it's ugly,
but it works for now...)
3) made the cookiemanager get the real list count each time through (of dubious
value I think, see my previous comment)
4) removed the out-of-bounds assertion in COOKIE_Enumerate, since it's a
"normal" condition.

Comment 14

[[e-mail]]

Attachment: Final patch

final patch, per darin's comments on IRC.

It turns out the cookieservice and cookiemanager UI (js) are running on the
same thread. so the cookie list can't actually change while cookiemanager is
open. This means we can go back to caching the count in the enumerator (like
the first patch), but I kept the assertion removal and the nullcheck addition,
just for good practice.

Ready for r/sr?

Comment 15

[Darin Fisher]

Comment on attachment 113424 [details] [diff] [review]
Final patch

>Index: extensions/cookie/nsCookies.cpp

>-  NS_ASSERTION(count >= 0 && count < cookie_list->Count(), "bad cookie index");
>   if (count < 0 || count >= cookie_list->Count()) {
>     return NS_ERROR_UNEXPECTED;
>   }

so can we keep this assertion now that we are confident that the cookie
count will never change during enumeration?

    if (count < 0 ... ) {
      NS_ERROR("bad cookie index");
      return NS_ERROR_UNEXPECTED;
    }


>Index: extensions/cookie/nsCookieManager.cpp

>+        // note: COOKIE_Count() also removes expired cookies from the list
>+        nsCookieEnumerator() : mCookieIndex(0),
>+                               mCookieCount(COOKIE_Count())

nit: please add a juicy comment here explaining why the cookie count is
static over the lifetime of this object.

sr=darin with those changes.

Comment 16

[[e-mail]]

Attachment: Final final patch

adds the NS_ERROR back in, and gives a juicier comment block.

Comment 17

[[e-mail]]

Comment on attachment 113427 [details] [diff] [review]
Final final patch

carrying over r/sr, requesting a= for checkin to 1.3b.

This is a low-risk patch that fixes a pretty big perf blunder, O(2n^2), when
displaying cookies in the cookiemanager. It fixes the algorithm to be O(n) and
adds a few safety checks.

Comment 18

[Daniel Veditz [:dveditz]]

We really want to be done w/1.3b and this problem has been there for a long time
-- I have to say it's not blocking 1.3b

I'll leave the 1.3b approval request for now though, it looks safe enough if
1.3b is going to drag on and on, or we could get it in 1.3 final.

Comment 19

[[e-mail]]

yeah, I agree about 1.3b. I wasn't sure whether you guys had had enough already,
or whether I could sneak this one by, so I thought I'd give it a shot ;)

either one sounds fine to me.

Comment 20

[Asa Dotzler [:asa]]

Comment on attachment 113427 [details] [diff] [review]
Final final patch

This can wait until we open for 1.4alpha development. Please hold off on
landing until then. Thanks.

Comment 21

[Matthias Versen [:Matti]]

*** Bug 147266 has been marked as a duplicate of this bug. ***

Comment 22

[[e-mail]]

Attachment: Same patch, no bitrot

Carrying over r=biesi/sr=darin. Ready for checkin to 1.4a...

Comment 23

[Christian :Biesinger (don't email me, ping me on IRC)]

Checking in extensions/cookie/nsCookieManager.cpp;
/cvsroot/mozilla/extensions/cookie/nsCookieManager.cpp,v  <--  nsCookieManager.cpp
new revision: 1.18; previous revision: 1.17
done
Checking in extensions/cookie/nsCookies.cpp;
/cvsroot/mozilla/extensions/cookie/nsCookies.cpp,v  <--  nsCookies.cpp
new revision: 1.97; previous revision: 1.96
done
Checking in extensions/wallet/cookieviewer/CookieViewer.js;
/cvsroot/mozilla/extensions/wallet/cookieviewer/CookieViewer.js,v  <-- 
CookieViewer.js
new revision: 1.76; previous revision: 1.75
done