143939 - [cookies] move to hashtables

Status: RESOLVED FIXED

(Core :: Networking: Cookies, enhancement, P2)

Description

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

COOKIE_GetCookie is slow -- it's taking about 1% of the non-idle page load time
on the main thread when running through 40 URLs somewhat like the jrgm test, but
live.

I'll attach a jprof profile showing the time spent within COOKIE_GetCookie.  I
admit to having a lot of stored cookies -- 243, to be exact, of which 155 are
domain cookies.

It seems like it would be nice to use a hashtable here for the host cookies, and
either a hashtable (where you would do multiple lookups) or a lexicographic tree
(where the child lists would be hashtables when they're larger than a certain
size) for the domain cookies -- probably the former would be simpler and fast
enough.

Comment 1

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: jprof profile of time within COOKIE_GetCookie

Comment 2

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

The places to start looking at the profile are:
http://bugzilla.mozilla.org/showattachment.cgi?attach_id=83274#flat
http://bugzilla.mozilla.org/showattachment.cgi?attach_id=83274#83971

Comment 3

[Samir Gehani]

Nav triage team: nsbeta1-

Comment 4

[[e-mail]]

Will be taken care of when we move to hashtables as part of the backend cookie
rewrite.

Comment 5

[[e-mail]]

taking

Comment 6

[Cathleen]

Dan, do you have patch ready for review  (cookie backend re-write)?  

I think the risk of re-write could be pretty high, but if reviews show it's good
to land, then we most likely need to try for early 1.4alpha, so that the code
can be baked on trunk, and we would have time to iron out unforeseen issues.

Comment 7

[[e-mail]]

cathleen:

I've posted a reply to your comment in bug 187304 (tracking bug for the
rewrite)... take a look :)

Comment 8

[[e-mail]]

i have a patch in hand for this. i need to polish it a tad more before it's
ready for review.

codesize will be neutral (which is great, because the hashtable code is more
complex... but we get some neat savings in a few places), and perf will be
greatly improved. my earlier measurements indicate about a 2x speedup in
GetCookie() for moderately-sized lists, and i expect a large improvement in
SetCookie() (mostly because of reworked semantics, owing to the cheaper list
operations).

darin, what's your schedule looking like for the freeze? if we can get this in,
it would be neat... but i don't want to bog you down with all these patches :)

Comment 9

[[e-mail]]

Attachment: patch v1 (readable; for review only)

ok, here it is. this patch is diffed against a bunch of other things in my
tree, so don't try to apply it. for review purposes only. ;)

(if you want to test it, just let me know and i can diff up my tree for you.)

the patch is mostly refactoring and shuffling of code, to optimize everything
for the capabilities the hashtables provide (see e.g. AddInternal()). the
architecture i've chosen is a hashtable of Host() entries (which means they
keep the leading dot if they are domain cookies). the nsCookie's themselves are
stored as a linked list within the nsCookieEntry hash entryclass, which is
optimal for the common case of one or two cookies per domain. (using a
voidarray would be bloaty for this case). so, to find all the cookies for a
given URL (say in GetCookie()), you just walk up the domain levels by looking
for '.' in the host URI, and do a hash lookup at each stage. you then traverse
the linked list.

another nice little win is killing off our custom nsCookieEnumerator class for
nsICookieManager::GetEnumerator()... we just roll an nsCOMArray and grab an
enumerator off that. overall, this patch is codesize-neutral (actually it
reduces it a tad).

Comment 10

[Benjamin Smedberg]

Comment on attachment 133188 [details] [diff] [review]
patch v1 (readable; for review only)

>-nsCookieService *nsCookieService::gCookieService = nsnull;
>+static nsCookieService *gCookieService = nsnull;

As I mentioned on IRC, file-scoped statics are considered deprecated in the C++
standard, so leave the static class member.

>+  if (gCookieService) {
>+    NS_ADDREF(gCookieService);
>+    if (NS_FAILED(gCookieService->Init())) {
>+      NS_RELEASE(gCookieService);
>+    }
>+  }
> 
>   return gCookieService;
> }

If gCookieService->Init fails, you need to null out gCookieService so that this
method doesn't return an bad pointer.

>+  // begin hash lookup, walking up the subdomain levels.
>+  // we use nextDot to make sure we have at least one embedded dot remaining.
>+  while (nextDot) {
>+    nsCookieEntry *entry = mHostTable.GetEntry(currentDot);
>+    for (cookie = entry ? entry->Head() : nsnull; cookie; cookie = cookie->Next()) {

IMO this would be more readable if you moved "cookie = entry..." on its own
line before the "for", or even better, made this a while loop.

>+      // if the cookie is secure and the host scheme isn't, we can't send it
>+      if (cookie->IsSecure() & !isSecure) {
>+        continue;
>+      }

I have two questions about this... first, what is bitwise-& doing there?
second, shouldn't this test go in both directions? non-secure cookies should
not be fed to secure webpages.

>-    // check if the cookie has expired, and remove if so.
>-    // note that we do this *after* previous tests passed - so we're only removing
>-    // the ones that are relevant to this particular search.

Did you/do you need to add this logic back somewhere else? 

@ nsCookieService::Remove(const nsACString &aHost,
>+  if (!FindCookie(PromiseFlatCString(aHost),
>+                  PromiseFlatCString(aName),
>+                  PromiseFlatCString(aPath),
>+                  matchIter))
>+    return NS_ERROR_UNEXPECTED;

Is this truly an unexpected error? Wouldn't it make more sense to define/use a
"success" code "NS_COOKIE_NOT_FOUND"?

r=bsmedberg if you address the comments above

Comment 11

[[e-mail]]

thanks for the review bsmedberg! ;)

>If gCookieService->Init fails, you need to null out gCookieService so that this
>method doesn't return an bad pointer.

actually, NS_RELEASE() nulls the pointer...

>IMO this would be more readable if you moved "cookie = entry..." on its own
>line before the "for", or even better, made this a while loop.

yeah; i would've used the nsListIter helper class, only we don't need the extra
"prev" member here. i'll tidy it up.

>I have two questions about this... first, what is bitwise-& doing there?
>second, shouldn't this test go in both directions? non-secure cookies should
>not be fed to secure webpages.

great catch... i owe you one. i just fixed that to a logical-&& on trunk. as for
bidirectionality... the "secure" attribute on a cookie just means that the
browser should only send the cookie contents over a secure connection. it
doesn't mean that _only_ secure cookies can be sent over secure connections -
it's just a hint the server can use to say the cookie contents are sensitive.

>Did you/do you need to add this logic back somewhere else? 

nope... cookie expiry semantics have changed in this patch. previously, since we
were traversing the entire list anyway, we could expire old cookies in
GetCookie(); but now, we only want to traverse the entire list when it's
absolutely necessary. so we only expire cookies when we're trying to set a
cookie, and the list is full (300 cookies), to try and free up space. cookie
expiry should be a fairly rare event (distinct from deletion or replacement,
which can happen frequently).

>Is this truly an unexpected error? Wouldn't it make more sense to define/use a
>"success" code "NS_COOKIE_NOT_FOUND"?

yeah, i guess there are legitimate cases where this could happen... is it worth
defining a special returncode? how do i do that? ;)

thx again for the review!

Comment 12

[Benjamin Smedberg]

you would define your new error code in netwerk/base/public/nsNetError.h, in a
new section, adding a new section to the end.

#define NS_SUCCESS_COOKIE_NOT_FOUND \
    NS_ERROR_GENERATE_SUCCESS(NS_ERROR_MODULE_NETWORK, 80)

The other option, of course, is to return NS_OK... who cares if we can't delete
a cookie that doesn't exist?

Comment 13

[[e-mail]]

yeah, NS_OK sounds fine to me... can't think of a reason why the caller would
care  to know :)

Comment 14

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

Comment on attachment 133188 [details] [diff] [review]
patch v1 (readable; for review only)

Looks good to me too. r=mvl for what it is worth

Comment 15

[Darin Fisher]

Comment on attachment 133188 [details] [diff] [review]
patch v1 (readable; for review only)

>+struct nsListIter
>+{
>+  nsListIter() {}
...
>+  nsCookieEntry *entry;
>+  nsCookie      *prev;
>+  nsCookie      *current;
>+};
...
>+struct nsEnumerationData
>+{
>+  nsEnumerationData(nsInt64 aCurrentTime,
>+                    PRInt64 aOldestTime)
>+   : currentTime(aCurrentTime)
>+   , oldestTime(aOldestTime) {}
...
>+  nsListIter iter;
>+};

concerns me that |iter| will be uninitialized after normal construction
of a nsEnumerationData object.	maybe your default constructor should
null out nsListIter's fields.  in a perfect world this is overkill, but
it is easier to track down problems related to dereferencing a null pointer
than it is with dereferencing a junk pointer.


>+  // return cookies in order of path length; longest to shortest
>+  foundCookieList.Sort(compareCookiesByPath, nsnull);

maybe comment that this sorting is done per spec.


overall, this patch looks great! sr=darin

Comment 16

[[e-mail]]

landed for alpha. fixed!

Comment 17

[Alec Flett]

nice work - looks like this knocked down Ts on some platforms (also could have
been other checkins, but this looks like a good culprit)