1253211 - NSSTrustDomain_TraverseCertificates() runs in O(n²) time

Status: UNCONFIRMED

(NSS :: Libraries, defect, P3)

Description

[David Woodhouse]

User Agent: Mozilla/5.0 (X11; Fedora; Linux x86_64; rv:44.0) Gecko/20100101 Firefox/44.0
Build ID: 20160126084239

Steps to reproduce:

I put 11186 user S/MIME certificates into a token.

(Actually, this is the corporate Exchange addressbook, with all contacts' X.509 certificates available through a PKCS#11 token. See https://bugzilla.gnome.org/show_bug.cgi?id=704246 for the full details).


Actual results:

Functions like PK11_ListCerts() and PK11_FindCertsFromEmailAddress() take tens of seconds to complete:

[dwoodhou@i7 nssdb]$ cat pkcs11.txt
# Gr. This shouldn't be necessary since it *is* in the system configuration
# but NSS doesn't obey the system configuration (NSS bug #248722).
library=/home/dwmw2/git/evolution-pkcs11/src/.libs/evolution-pkcs11.so
name=Evolution
NSS=trustOrder=100

[dwoodhou@i7 nssdb]$ time certutil -d sql:`pwd` -L --email=[e-mail] &>/dev/null

real	0m20.995s
user	0m19.870s
sys	0m1.091s



Expected results:

It should have been faster.

Like this:

[dwoodhou@i7 nssdb]$ time p11tool --list-all-certs "pkcs11:token=Evolution%20Contact%20Certificates;object=$ADDR"  &> /dev/null

real	0m0.410s
user	0m0.252s
sys	0m0.092s


OK, that's a little unfair since it relies on a sane CKA_SUBJECT and you weren't. So it should be at *least* as fast as this, which is only *one* order of magnitude faster:

[dwoodhou@i7 nssdb]$ time p11tool --list-all-certs "pkcs11:token=Evolution%20Contact%20Certificates"  &> /dev/null

And yeah, that's a tiny bit unfair too since you're actually *filtering* the results not just spitting them out. But if you look at the perf report for the run, you'll see that it's spending most of its time in nssToken_TraverseCertificates() building up the lists, and *not* in FindCertsEmailCallback().
real	0m2.551s
user	0m1.784s
sys	0m0.705s

Comment 1

[David Woodhouse]

If we were to use a hash table instead of a simple linked list for collecting the results, that should make it a lot saner.

But in this case, there *was* only one result. We're building up a huge list of candidates, eliminating duplicates in O(n²) time, only to *then* apply the filter and cut them down to one. Why not apply the match filter *first*?

Comment 2

[varunnaganathan912]

Attachment: changed the implementation of storage of objects to a hash map

Comment 3

[David Woodhouse]

This looks like a very good first effort; thanks. There are some cosmetic things to fix, like function and structure names, and making functions static, and consistent indentation. But it works nicely — and reduces the time taken for 'certutil -L' from 20 seconds to 10 seconds for my test case. Importantly, putting code in the *token* in the hot part of the profile, not NSS :)

Now is the time to go through it and check on all the details — in particular, are you freeing everything correctly? Run it in valgrind --leak-check=full both before and after your patch, and check that there's nothing to be concerned about.

Also, go through and *validate* your assumptions. We assert that changing from using that PRCList, to the two PLHashTables, will have no problematic effect on the behaviour. So prove it, to yourself at least.

Firstly, we're changing the *ordering* of the output. Does that matter? I suspect not. But a patch submission should explicitly call out that change in behaviour, for people to think about.

Secondly, I spot a theoretical problem with our second hash table used for find_instance_in_collection(). What if an object is added to a collection, and then someone *else* calls nssPKIObject_AddInstance() on it? Now, in the old code that instance was automatically included in the collection, and find_instance_in_collection() would find it. In the new code, it isn't in the hash table. Is that OK? (Does it even *happen*, and do we care?)

And what does it mean in practice... well, if that new instance *is* now added to the collection, and we end up in add_object_instance() for it, it looks like we'll call nssPKIObject_AddInstance() again. Is *that* OK and will it do nothing as we'd hope?

One option is to drop the second hash table and the find_instance_in_collection() function, and make add_object_instance() *always* use ->getUIDFromInstance() and look up the *object* in the object hash table. Bob, I'm guessing that's expensive, which is why we were looking for the instance first?

Comment 4

[David Woodhouse]

The same thing can also happen when nssPKIObjectCollection_AddObject() is called with an object that already has instances (and won't it always?). You want to add the *instances* as well as the object.

Comment 5

[varunnaganathan912]

Attachment: changed the implementation of storage of objects to a hash map

Comment 6

[varunnaganathan912]

Attachment: changed the implementation of storage of objects to a hash map

Fixed the indentation problems and the unnecessary typecasting as suggested by David.

Comment 7

[Robert Relyea]

Comment on attachment 8729844 [details] [diff] [review]
changed the implementation of storage of objects to a hash map

Review of attachment 8729844 [details] [diff] [review]:
-----------------------------------------------------------------

Very good use of PLHashes.

the new code is simplier to read than the old one, bug keeps the changes in the isolated helper functions.
Only minor tweaks, and that just improves the efficiency

::: lib/pki/pkibase.c
@@ +53,5 @@
> +      /* hash function can be improved */
> +      hashvalue =  hashvalue ^ uid[i].size;
> +  }
> +  return hashvalue; 
> +}

Yes, the biggest issue here is if uid sizes are relatively the same. You could wind up with as few as 2 hash buckets. Hashing the values (or part of the values) would be better.

You've already correctly identified this as an area for improvement.

@@ +63,5 @@
> +  const nssCryptokiObject *key = arg;
> +  /* hash function can be improved */
> +  PLHashNumber hashvalue =  (PLHashNumber)((unsigned long)key->token) ^ (PLHashNumber)((unsigned long)key->handle);
> +  return hashvalue;
> +}

This one is a fine hash.

Comment 8

[jbonnafo]

Hello,
May i help in order to get the proposed patch landing?
Thanks,