124923 - The dynamic oid hash table (oid_d_hash in secoid.c) is not thread-safe

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P2)

Description

[Wan-Teh Chang]

In secoid.c, there are two hash tables for OIDs.  One is
static (oidhash), and the other is dynamic (oid_d_hash).

The static table (oidhash) is never changed after it has
been constructed.  Therefore, we can do lookups in the
static table with PL_HashTableLookupConst without using
a lock.

The dynamic table (oid_d_hash) gets modified (new entries
added) when the user loads new crypto modules.  It needs
to be protected by a lock.

Bob, do we need to fix this in NSS 3.4?

Comment 1

[Wan-Teh Chang]

Assigned the bug to Bishakha.

Comment 2

[Wan-Teh Chang]

Changed the QA contact to Bishakha.

Comment 3

[Wan-Teh Chang]

Set target milestone to NSS 3.5.

Comment 4

[Wan-Teh Chang]

Moved to 3.7.

Comment 5

[Wan-Teh Chang]

Moved to target milestone 3.8 because the original
NSS 3.7 release has been renamed 3.8.

Comment 6

[Nelson Bolyard (seldom reads bugmail)]

Remove target milestone of 3.8, since these bugs didn't get into that release.

Comment 7

[Nelson Bolyard (seldom reads bugmail)]

I plan to fix this feature for NSS 3.10, so that pp and certutil can use it.

Comment 8

[Nelson Bolyard (seldom reads bugmail)]

Here are a number of related issues that I intend to fix while fixing this
bug:

1. SECOID_AddEntry must be declared in a public header file.
2. SECOID_AddEntry must be exported.
3. SECOID_AddEntry must update the hash table to include the new entry.
4. There must be some way for the caller of SECOID_AddEntry to obtain the 
   new SECOidTag of the new dynamicly allocated entry.  One way to do this 
   is for SECOID_AddEntry to return the new SECOidTag, rather than a SECStatus. 
   It could return SEC_OID_UNKNOWN for failure.
5. SECOID_AddEntry should take arguments to allow the mechanism and 
   supportedExtension members of the struct SECOidDataStr to be properly 
   initialized.  Perhaps it should just take a struct SECOidDataStr as its
   input argument, and set the SECOidTag in the "offset" member of that struct.
4. The existing code in SECOID_Shutdown leaks memory allocated for the 
   OID and the OID descriptions, which are pointed to by the dynamic hash 
   table entry.  All the memory allocated by SECOID_AddEntry should be 
   allocated from a PLArenaPool.  SECOID_Shutdown should free that ArenaPool.  
5. I intend to use NSS reader/writer locks to protect the dynamic OID table
   and the associate PL Hash table.  

Comment 9

[Nelson Bolyard (seldom reads bugmail)]

Attachment: patch v1 - reimplement dynamic OID code

This code is a near total rewrite of the code that maintains and queries the 
table of dynamic OIDs.	It work in my tests, by I haven't done multi-threaded
testing yet.

Comment 10

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 139967 [details] [diff] [review]
patch v1 - reimplement dynamic OID code 

Please review.	This patch assumes that the patch for bug  231881 is already
applied (or checked in).

Comment 11

[Nelson Bolyard (seldom reads bugmail)]

Patch v1 above provides the same functionality as the original code,
but in a thread safe manner, and without leaks.  
However, it occurs to me that this code is missing some basic sanity
checks on the input, which are not added in patch v1, such as:
- no check to see if the OID being added is already present
- no check to see if the description has non-zero length
- no check to see if the supportedExtension member has a valid value.
So, I will prepare a patch part 2, to be applied on top of patch v1 above,
to add the missing checks.

Comment 12

[Robert Relyea]

Comment on attachment 139967 [details] [diff] [review]
patch v1 - reimplement dynamic OID code 

First, this patch is generally good, I have two comments (one minor).

There are lots of places throughout the code where the following code appears:

if (!dynOid && secoid_InitDynOidData() != SECSuccess) {
    return SECFailure;
}

The comment in Shutdown() seems to indicate on first reading that we don't
always initialize the Dynamic OID system. Is this the intent, or does the
comment really mean "Well if we get here, we've failed to ever initialize the
oid system, even after serveral attempts (including this one)"?

It seems to me that in most places we make this call, we could simply check the
dynOidLock. If it doesn't exist we need not continue. 2 exceptions are:

1) the call in SECOID_AddEntry would naturally need to initalize the
DynOidData,

and
2) The call in secoid_init(). It appears this is to produce the side effect of
serializing access  to secoid_init()?, but I'm not so sure it accomplishes
this?

The other commement is related to that test. No Error code is set in any of the
failure cases. This is a minor comment because the code that this replaces also
set no error code in the equivalent cases.

Comment 13

[Nelson Bolyard (seldom reads bugmail)]

Attachment: patch v2 - unified and context diffs

This patch is quite a bit different than the previous one.
I included both unified and context diffs, to try to make it easier to review.
I think this addresses all the review comments.  
It may generate some new ones :)

Comment 14

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 140130 [details] [diff] [review]
patch v2 - unified and context diffs

Bob, please review again.
Beware, This patch is quite a bit different.  Thanks.

Comment 15

[Nelson Bolyard (seldom reads bugmail)]

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

Comment 16

[Robert Relyea]

Comment on attachment 140130 [details] [diff] [review]
patch v2 - unified and context diffs

Yes, looks good.

Two minor nits in the comments:
imiiialized -> initialized
lcok ->lock

Comment 17

[Wan-Teh Chang]

Comment on attachment 140130 [details] [diff] [review]
patch v2 - unified and context diffs

1. SECOID_AddEntry doesn't need to call
secoid_InitDynOidData because NSS initialization
calls secoid_Init, which calls secoid_InitDynOidData.

Remove lines 2-4 in the comment before the definition
of secoid_InitDynOidData.

2. secoid_Init should call secoid_InitDynOidData
as follows:

      if (oidhash) {
	return SECSuccess;
      }
+ 
+     if (secoid_InitDynOidData() != SECSuccess) {
+	return SECFailure;
+     }

We might want to rename secoid_Init as SECOID_Init
and declare it in secoid.h.

3. In secoid_InitDynOidData, dynOidLock should be
created with a NSSRWLock_New call.  When we create
dynOidPool, we don't need to lock dynOidLock.

4. The old comment "Worry: what about thread safety..."
should be deleted.

5. In secoid_FindDynamic and secoid_FindDynamicByTag,
testing dynOidTable without a lock is not thread-safe.
This "double-checked locking" pattern is now considered
broken.  See
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
or search for "double checked locking" in the
comp.programming.threads newsgroup, for articles
written by David Butenhof.

6. In secoid_FindDynamic, we should test dynOidHash,
not dynOidTable, before the PL_HashTableLookup call,
right?

7. In SECOID_Shutdown, you don't need to lock
dynOidLock when you destroy the data structures.
This can simplify the code.

Comment 18

[Nelson Bolyard (seldom reads bugmail)]

I checked patch v2 in before I received wtc's comments (by email).
I will address the latest review comments in a separate patch/checkin.

/cvsroot/mozilla/security/nss/lib/util/secasn1t.h,v  <--  secasn1t.h
new revision: 1.8; previous revision: 1.7

/cvsroot/mozilla/security/nss/lib/util/secoid.c,v  <--  secoid.c
new revision: 1.26; previous revision: 1.25

/cvsroot/mozilla/security/nss/lib/util/secoid.h,v  <--  secoid.h
new revision: 1.5; previous revision: 1.4

Comment 19

[Nelson Bolyard (seldom reads bugmail)]

I disagree with some of the suggestions in comment 17.  Let me take
them point by point.

1. I deliberately coded this in a way that does not depend on
secoid_Init calling secoid_InitDynOidData.  This is defensive
programming against future changes.

Comment lines 2-4 before secoid_InitDynOidData are there to
discourage subsequent programmers from changing the code to the
more obvious (but wrong) test.

2. What if secoid_Init gets called twice?

3. creating dynOidLock with a NSSRWLock_New call would not be
thread safe.  Nothing in this function or in secoid_Init prevents
this function from being called simultaneously by two threads.
That is precisely why nssRWLock_AtomicCreate exists.

4. done.

5. The situation described in the cited paper requires that the
code inside the double-checked block *create* the object that was
not found.  It is not safe precisely because the code inside the
double-checked code block alters the condition that is checked.
However, the code in secoid_FindDynamic and secoid_FindDynamicByTag
does NOT alter the double-checked value, and so is not vulnerable
to the issues described in that article.

6. Yes.  I'll change it.

7. If all code in NSS (and code that uses it) was correct with
respect to locks, I would agree.  However, I have a great deal of
experience with locking issues in NSS (and apps that use it) that
has taught me to take extra defensive precautions against
ill-behaved code, especially in the area of destroying locks and
the data they protect.  You'll see this same sort of login in SSL
too.

Comment 20

[Nelson Bolyard (seldom reads bugmail)]

/cvsroot/mozilla/security/nss/lib/util/secoid.c,v  <--  secoid.c
new revision: 1.27; previous revision: 1.26

Made (some) changes suggested in above review comments.