Make ASN1_STRING_TABLE_add thread-safe and document.

This function is a little awkward. It mutates global data, so if two
libraries in the address space both attempt to define a custom OID, they
will conflict. But some existing code uses it so, as long as it does so,
we should make it thread-safe.

Along the way, I've switched it to a hash table and removed the ability
to overwrite existing entries. Previously, overwriting a built-in table
would crash (on platforms where const structures are write-protected).
Overwriting a dynamic table implemented this weird merging algorithm.
The one caller I've seen does not appear to need this feature.

I've also switched ASN1_STRING_TABLE_cleanup to a no-op, matching our
other global cleanup functions. This function is not safe to call
without global knowledge of all other uses of the library.

Update-Note: ASN1_STRING_TABLE_add no longer allows overwrite existing
entries. In most cases, this would crash or trigger a race condition
anyway.

Bug: 426
Change-Id: Ie024cca87feaef3ff10064b452f3a860844544da
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/49769
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/asn1/a_strnid.c b/crypto/asn1/a_strnid.c
index 62c2f5d..bc9226a 100644
--- a/crypto/asn1/a_strnid.c
+++ b/crypto/asn1/a_strnid.c
@@ -56,22 +56,23 @@
 
 #include <openssl/asn1.h>
 
-#include <stdlib.h>             /* For bsearch */
+#include <assert.h>
+#include <stdlib.h>
 #include <string.h>
 
 #include <openssl/err.h>
 #include <openssl/mem.h>
 #include <openssl/obj.h>
-#include <openssl/stack.h>
 
 #include "../internal.h"
+#include "../lhash/internal.h"
 #include "internal.h"
 
 
-DEFINE_STACK_OF(ASN1_STRING_TABLE)
+DEFINE_LHASH_OF(ASN1_STRING_TABLE)
 
-static STACK_OF(ASN1_STRING_TABLE) *stable = NULL;
-static void st_free(ASN1_STRING_TABLE *tbl);
+static LHASH_OF(ASN1_STRING_TABLE) *string_tables = NULL;
+static struct CRYPTO_STATIC_MUTEX string_tables_lock = CRYPTO_STATIC_MUTEX_INIT;
 
 void ASN1_STRING_set_default_mask(unsigned long mask)
 {
@@ -87,34 +88,36 @@
     return 1;
 }
 
+static const ASN1_STRING_TABLE *asn1_string_table_get(int nid);
+
 /*
  * The following function generates an ASN1_STRING based on limits in a
  * table. Frequently the types and length of an ASN1_STRING are restricted by
  * a corresponding OID. For example certificates and certificate requests.
  */
 
-ASN1_STRING *ASN1_STRING_set_by_NID(ASN1_STRING **out,
-                                    const unsigned char *in, int inlen,
-                                    int inform, int nid)
+ASN1_STRING *ASN1_STRING_set_by_NID(ASN1_STRING **out, const unsigned char *in,
+                                    int len, int inform, int nid)
 {
-    ASN1_STRING_TABLE *tbl;
     ASN1_STRING *str = NULL;
-    unsigned long mask;
     int ret;
-    if (!out)
+    if (!out) {
         out = &str;
-    tbl = ASN1_STRING_TABLE_get(nid);
-    if (tbl) {
-        mask = tbl->mask;
-        if (!(tbl->flags & STABLE_NO_MASK))
-            mask &= B_ASN1_UTF8STRING;
-        ret = ASN1_mbstring_ncopy(out, in, inlen, inform, mask,
-                                  tbl->minsize, tbl->maxsize);
-    } else {
-        ret = ASN1_mbstring_copy(out, in, inlen, inform, B_ASN1_UTF8STRING);
     }
-    if (ret <= 0)
+    const ASN1_STRING_TABLE *tbl = asn1_string_table_get(nid);
+    if (tbl != NULL) {
+        unsigned long mask = tbl->mask;
+        if (!(tbl->flags & STABLE_NO_MASK)) {
+            mask &= B_ASN1_UTF8STRING;
+        }
+        ret = ASN1_mbstring_ncopy(out, in, len, inform, mask, tbl->minsize,
+                                  tbl->maxsize);
+    } else {
+        ret = ASN1_mbstring_copy(out, in, len, inform, B_ASN1_UTF8STRING);
+    }
+    if (ret <= 0) {
         return NULL;
+    }
     return *out;
 }
 
@@ -159,91 +162,101 @@
     {NID_ms_csp_name, -1, -1, B_ASN1_BMPSTRING, STABLE_NO_MASK}
 };
 
-static int sk_table_cmp(const ASN1_STRING_TABLE **a,
-                        const ASN1_STRING_TABLE **b)
+static int table_cmp(const ASN1_STRING_TABLE *a, const ASN1_STRING_TABLE *b)
 {
-    return (*a)->nid - (*b)->nid;
+    if (a->nid < b->nid) {
+        return -1;
+    }
+    if (a->nid > b->nid) {
+        return 1;
+    }
+    return 0;
 }
 
-static int table_cmp(const void *in_a, const void *in_b)
+static int table_cmp_void(const void *a, const void *b)
 {
-    const ASN1_STRING_TABLE *a = in_a;
-    const ASN1_STRING_TABLE *b = in_b;
-    return a->nid - b->nid;
+    return table_cmp(a, b);
 }
 
-ASN1_STRING_TABLE *ASN1_STRING_TABLE_get(int nid)
+static uint32_t table_hash(const ASN1_STRING_TABLE *tbl)
 {
-    int found;
-    size_t idx;
-    ASN1_STRING_TABLE *ttmp;
-    ASN1_STRING_TABLE fnd;
-    fnd.nid = nid;
-
-    ttmp =
-        bsearch(&fnd, tbl_standard,
-                sizeof(tbl_standard) / sizeof(ASN1_STRING_TABLE),
-                sizeof(ASN1_STRING_TABLE), table_cmp);
-    if (ttmp)
-        return ttmp;
-    if (!stable)
-        return NULL;
-    sk_ASN1_STRING_TABLE_sort(stable);
-    found = sk_ASN1_STRING_TABLE_find(stable, &idx, &fnd);
-    if (!found)
-        return NULL;
-    return sk_ASN1_STRING_TABLE_value(stable, idx);
+    return OPENSSL_hash32(&tbl->nid, sizeof(tbl->nid));   
 }
 
-int ASN1_STRING_TABLE_add(int nid,
-                          long minsize, long maxsize, unsigned long mask,
-                          unsigned long flags)
+static const ASN1_STRING_TABLE *asn1_string_table_get(int nid)
 {
-    ASN1_STRING_TABLE *tmp;
-    char new_nid = 0;
-    flags &= ~STABLE_FLAGS_MALLOC;
-    if (!stable)
-        stable = sk_ASN1_STRING_TABLE_new(sk_table_cmp);
-    if (!stable) {
-        OPENSSL_PUT_ERROR(ASN1, ERR_R_MALLOC_FAILURE);
+    ASN1_STRING_TABLE key;
+    key.nid = nid;
+    const ASN1_STRING_TABLE *tbl =
+        bsearch(&key, tbl_standard, OPENSSL_ARRAY_SIZE(tbl_standard),
+                sizeof(ASN1_STRING_TABLE), table_cmp_void);
+    if (tbl != NULL) {
+        return tbl;
+    }
+
+    CRYPTO_STATIC_MUTEX_lock_read(&string_tables_lock);
+    if (string_tables != NULL) {
+        tbl = lh_ASN1_STRING_TABLE_retrieve(string_tables, &key);
+    }
+    CRYPTO_STATIC_MUTEX_unlock_read(&string_tables_lock);
+    /* Note returning |tbl| without the lock is only safe because
+     * |ASN1_STRING_TABLE_add| cannot modify or delete existing entries. If we
+     * wish to support that, this function must copy the result under a lock. */
+    return tbl;
+}
+
+int ASN1_STRING_TABLE_add(int nid, long minsize, long maxsize,
+                          unsigned long mask, unsigned long flags)
+{
+    /* Existing entries cannot be overwritten. */
+    if (asn1_string_table_get(nid) != NULL) {
+        OPENSSL_PUT_ERROR(ASN1, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
         return 0;
     }
-    if (!(tmp = ASN1_STRING_TABLE_get(nid))) {
-        tmp = OPENSSL_malloc(sizeof(ASN1_STRING_TABLE));
-        if (!tmp) {
-            OPENSSL_PUT_ERROR(ASN1, ERR_R_MALLOC_FAILURE);
-            return 0;
+
+    int ret = 0;
+    CRYPTO_STATIC_MUTEX_lock_write(&string_tables_lock);
+
+    if (string_tables == NULL) {
+        string_tables = lh_ASN1_STRING_TABLE_new(table_hash, table_cmp);
+        if (string_tables == NULL) {
+            goto err;
         }
-        tmp->flags = flags | STABLE_FLAGS_MALLOC;
-        tmp->nid = nid;
-        tmp->minsize = tmp->maxsize = -1;
-        new_nid = 1;
-    } else
-        tmp->flags = (tmp->flags & STABLE_FLAGS_MALLOC) | flags;
-    if (minsize != -1)
-        tmp->minsize = minsize;
-    if (maxsize != -1)
-        tmp->maxsize = maxsize;
-    tmp->mask = mask;
-    if (new_nid)
-        sk_ASN1_STRING_TABLE_push(stable, tmp);
-    return 1;
+    } else {
+        /* Check again for an existing entry. One may have been added while
+         * unlocked. */
+        ASN1_STRING_TABLE key;
+        key.nid = nid;
+        if (lh_ASN1_STRING_TABLE_retrieve(string_tables, &key) != NULL) {
+            OPENSSL_PUT_ERROR(ASN1, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
+            goto err;
+        }
+    }
+
+    ASN1_STRING_TABLE *tbl = OPENSSL_malloc(sizeof(ASN1_STRING_TABLE));
+    if (tbl == NULL) {
+        goto err;
+    }
+    tbl->nid = nid;
+    tbl->flags = flags;
+    tbl->minsize = minsize;
+    tbl->maxsize = maxsize;
+    tbl->mask = mask;
+    ASN1_STRING_TABLE *old_tbl;
+    if (!lh_ASN1_STRING_TABLE_insert(string_tables, &old_tbl, tbl)) {
+        OPENSSL_free(tbl);
+        goto err;
+    }
+    assert(old_tbl == NULL);
+    ret = 1;
+
+err:
+    CRYPTO_STATIC_MUTEX_unlock_write(&string_tables_lock);
+    return ret;
 }
 
 void ASN1_STRING_TABLE_cleanup(void)
 {
-    STACK_OF(ASN1_STRING_TABLE) *tmp;
-    tmp = stable;
-    if (!tmp)
-        return;
-    stable = NULL;
-    sk_ASN1_STRING_TABLE_pop_free(tmp, st_free);
-}
-
-static void st_free(ASN1_STRING_TABLE *tbl)
-{
-    if (tbl->flags & STABLE_FLAGS_MALLOC)
-        OPENSSL_free(tbl);
 }
 
 void asn1_get_string_table_for_testing(const ASN1_STRING_TABLE **out_ptr,
diff --git a/crypto/asn1/asn1_test.cc b/crypto/asn1/asn1_test.cc
index 439afc6..7c37cb6 100644
--- a/crypto/asn1/asn1_test.cc
+++ b/crypto/asn1/asn1_test.cc
@@ -32,6 +32,10 @@
 #include "../test/test_util.h"
 #include "internal.h"
 
+#if defined(OPENSSL_THREADS)
+#include <thread>
+#endif
+
 
 // kTag128 is an ASN.1 structure with a universal tag with number 128.
 static const uint8_t kTag128[] = {
@@ -1160,11 +1164,11 @@
 TEST(ASN1Test, StringByCustomNID) {
   // This test affects library-global state. We rely on nothing else in the test
   // suite using these OIDs.
-  int nid1 = OBJ_create("1.2.840.113554.4.1.72585.1000", "custom OID 1",
-                        "custom OID 1");
+  int nid1 = OBJ_create("1.2.840.113554.4.1.72585.1000", "custom OID 1000",
+                        "custom OID 1000");
   ASSERT_NE(NID_undef, nid1);
-  int nid2 = OBJ_create("1.2.840.113554.4.1.72585.1001", "custom OID 2",
-                        "custom OID 2");
+  int nid2 = OBJ_create("1.2.840.113554.4.1.72585.1001", "custom OID 1001",
+                        "custom OID 1001");
   ASSERT_NE(NID_undef, nid2);
 
   // Values registered in the string table should be picked up.
@@ -1200,8 +1204,53 @@
   EXPECT_EQ(V_ASN1_UTF8STRING, ASN1_STRING_type(str.get()));
   EXPECT_EQ(Bytes("12345"), Bytes(ASN1_STRING_get0_data(str.get()),
                                   ASN1_STRING_length(str.get())));
+
+  // Overriding existing entries, built-in or custom, is an error.
+  EXPECT_FALSE(
+      ASN1_STRING_TABLE_add(NID_countryName, -1, -1, DIRSTRING_TYPE, 0));
+  EXPECT_FALSE(ASN1_STRING_TABLE_add(nid1, -1, -1, DIRSTRING_TYPE, 0));
 }
 
+#if defined(OPENSSL_THREADS)
+TEST(ASN1Test, StringByCustomNIDThreads) {
+  // This test affects library-global state. We rely on nothing else in the test
+  // suite using these OIDs.
+  int nid1 = OBJ_create("1.2.840.113554.4.1.72585.1002", "custom OID 1002",
+                        "custom OID 1002");
+  ASSERT_NE(NID_undef, nid1);
+  int nid2 = OBJ_create("1.2.840.113554.4.1.72585.1003", "custom OID 1003",
+                        "custom OID 1003");
+  ASSERT_NE(NID_undef, nid2);
+
+  std::vector<std::thread> threads;
+  threads.emplace_back([&] {
+    ASSERT_TRUE(ASN1_STRING_TABLE_add(nid1, 5, 10, V_ASN1_PRINTABLESTRING,
+                                      STABLE_NO_MASK));
+    bssl::UniquePtr<ASN1_STRING> str(ASN1_STRING_set_by_NID(
+        nullptr, reinterpret_cast<const uint8_t *>("12345"), 5, MBSTRING_UTF8,
+        nid1));
+    ASSERT_TRUE(str);
+    EXPECT_EQ(V_ASN1_PRINTABLESTRING, ASN1_STRING_type(str.get()));
+    EXPECT_EQ(Bytes("12345"), Bytes(ASN1_STRING_get0_data(str.get()),
+                                    ASN1_STRING_length(str.get())));
+  });
+  threads.emplace_back([&] {
+    ASSERT_TRUE(ASN1_STRING_TABLE_add(nid2, 5, 10, V_ASN1_PRINTABLESTRING,
+                                      STABLE_NO_MASK));
+    bssl::UniquePtr<ASN1_STRING> str(ASN1_STRING_set_by_NID(
+        nullptr, reinterpret_cast<const uint8_t *>("12345"), 5, MBSTRING_UTF8,
+        nid2));
+    ASSERT_TRUE(str);
+    EXPECT_EQ(V_ASN1_PRINTABLESTRING, ASN1_STRING_type(str.get()));
+    EXPECT_EQ(Bytes("12345"), Bytes(ASN1_STRING_get0_data(str.get()),
+                                    ASN1_STRING_length(str.get())));
+  });
+  for (auto &thread : threads) {
+    thread.join();
+  }
+}
+#endif  // OPENSSL_THREADS
+
 // Test that multi-string types correctly encode negative ENUMERATED.
 // Multi-string types cannot contain INTEGER, so we only test ENUMERATED.
 TEST(ASN1Test, NegativeEnumeratedMultistring) {
diff --git a/crypto/asn1/internal.h b/crypto/asn1/internal.h
index cab0c77..dcb6fcf 100644
--- a/crypto/asn1/internal.h
+++ b/crypto/asn1/internal.h
@@ -175,6 +175,14 @@
  * ASN.1 PrintableString, and zero otherwise. */
 int asn1_is_printable(uint32_t value);
 
+typedef struct {
+  int nid;
+  long minsize;
+  long maxsize;
+  unsigned long mask;
+  unsigned long flags;
+} ASN1_STRING_TABLE;
+
 /* asn1_get_string_table_for_testing sets |*out_ptr| and |*out_len| to the table
  * of built-in |ASN1_STRING_TABLE| values. It is exported for testing. */
 OPENSSL_EXPORT void asn1_get_string_table_for_testing(
diff --git a/include/openssl/asn1.h b/include/openssl/asn1.h
index 4f6fb3b..0f22de1 100644
--- a/include/openssl/asn1.h
+++ b/include/openssl/asn1.h
@@ -370,6 +370,50 @@
                                        int len, int inform, unsigned long mask,
                                        long minsize, long maxsize);
 
+// ASN1_STRING_set_by_NID behaves like |ASN1_mbstring_ncopy|, but determines
+// |mask|, |minsize|, and |maxsize| based on |nid|. When |nid| is a recognized
+// X.509 attribute type, it will pick a suitable ASN.1 string type and bounds.
+// For most attribute types, it preferentially chooses UTF8String. If |nid| is
+// unrecognized, it uses UTF8String by default.
+//
+// Slightly unlike |ASN1_mbstring_ncopy|, this function interprets |out| and
+// returns its result as follows: If |out| is NULL, it returns a newly-allocated
+// |ASN1_STRING| containing the result. If |out| is non-NULL and
+// |*out| is NULL, it additionally sets |*out| to the result. If both |out| and
+// |*out| are non-NULL, it instead updates the object at |*out| and returns
+// |*out|. In all cases, it returns NULL on error.
+//
+// This function supports the following NIDs: |NID_countryName|,
+// |NID_dnQualifier|, |NID_domainComponent|, |NID_friendlyName|,
+// |NID_givenName|, |NID_initials|, |NID_localityName|, |NID_ms_csp_name|,
+// |NID_name|, |NID_organizationalUnitName|, |NID_organizationName|,
+// |NID_pkcs9_challengePassword|, |NID_pkcs9_emailAddress|,
+// |NID_pkcs9_unstructuredAddress|, |NID_pkcs9_unstructuredName|,
+// |NID_serialNumber|, |NID_stateOrProvinceName|, and |NID_surname|. Additional
+// NIDs may be registered with |ASN1_STRING_set_by_NID|, but it is recommended
+// to call |ASN1_mbstring_ncopy| directly instead.
+OPENSSL_EXPORT ASN1_STRING *ASN1_STRING_set_by_NID(ASN1_STRING **out,
+                                                   const unsigned char *in,
+                                                   int len, int inform,
+                                                   int nid);
+
+// STABLE_NO_MASK causes |ASN1_STRING_TABLE_add| to allow types other than
+// UTF8String.
+#define STABLE_NO_MASK 0x02
+
+// ASN1_STRING_TABLE_add registers the corresponding parameters with |nid|, for
+// use with |ASN1_STRING_set_by_NID|. It returns one on success and zero on
+// error. It is an error to call this function if |nid| is a built-in NID, or
+// was already registered by a previous call.
+//
+// WARNING: This function affects global state in the library. If two libraries
+// in the same address space register information for the same OID, one call
+// will fail. Prefer directly passing the desired parametrs to
+// |ASN1_mbstring_copy| or |ASN1_mbstring_ncopy| instead.
+OPENSSL_EXPORT int ASN1_STRING_TABLE_add(int nid, long minsize, long maxsize,
+                                         unsigned long mask,
+                                         unsigned long flags);
+
 // TODO(davidben): Expand and document function prototypes generated in macros.
 
 
@@ -839,6 +883,30 @@
                                            unsigned long flags);
 
 
+// Deprecated functions.
+
+// ASN1_PRINTABLE_type interprets |len| bytes from |s| as a Latin-1 string. It
+// returns the first of |V_ASN1_PRINTABLESTRING|, |V_ASN1_IA5STRING|, or
+// |V_ASN1_T61STRING| that can represent every character. If |len| is negative,
+// |strlen(s)| is used instead.
+//
+// TODO(davidben): Remove this once all copies of Conscrypt have been updated
+// past https://github.com/google/conscrypt/pull/1032.
+OPENSSL_EXPORT int ASN1_PRINTABLE_type(const unsigned char *s, int len);
+
+// ASN1_STRING_set_default_mask does nothing.
+OPENSSL_EXPORT void ASN1_STRING_set_default_mask(unsigned long mask);
+
+// ASN1_STRING_set_default_mask_asc returns one.
+OPENSSL_EXPORT int ASN1_STRING_set_default_mask_asc(const char *p);
+
+// ASN1_STRING_get_default_mask returns |B_ASN1_UTF8STRING|.
+OPENSSL_EXPORT unsigned long ASN1_STRING_get_default_mask(void);
+
+// ASN1_STRING_TABLE_cleanup does nothing.
+OPENSSL_EXPORT void ASN1_STRING_TABLE_cleanup(void);
+
+
 // Underdocumented functions.
 //
 // The following functions are not yet documented and organized.
@@ -863,17 +931,6 @@
   unsigned alias_only_on_next_parse : 1;
 } ASN1_ENCODING;
 
-#define STABLE_FLAGS_MALLOC 0x01
-#define STABLE_NO_MASK 0x02
-
-typedef struct asn1_string_table_st {
-  int nid;
-  long minsize;
-  long maxsize;
-  unsigned long mask;
-  unsigned long flags;
-} ASN1_STRING_TABLE;
-
 // Declarations for template structures: for full definitions
 // see asn1t.h
 typedef struct ASN1_TEMPLATE_st ASN1_TEMPLATE;
@@ -1114,12 +1171,6 @@
                                                int len, const char *sn,
                                                const char *ln);
 
-// ASN1_PRINTABLE_type interprets |len| bytes from |s| as a Latin-1 string. It
-// returns the first of |V_ASN1_PRINTABLESTRING|, |V_ASN1_IA5STRING|, or
-// |V_ASN1_T61STRING| that can represent every character. If |len| is negative,
-// |strlen(s)| is used instead.
-OPENSSL_EXPORT int ASN1_PRINTABLE_type(const unsigned char *s, int len);
-
 OPENSSL_EXPORT unsigned long ASN1_tag2bit(int tag);
 
 // SPECIALS
@@ -1146,24 +1197,6 @@
 OPENSSL_EXPORT ASN1_STRING *ASN1_item_pack(void *obj, const ASN1_ITEM *it,
                                            ASN1_OCTET_STRING **oct);
 
-// ASN1_STRING_set_default_mask does nothing.
-OPENSSL_EXPORT void ASN1_STRING_set_default_mask(unsigned long mask);
-
-// ASN1_STRING_set_default_mask_asc returns one.
-OPENSSL_EXPORT int ASN1_STRING_set_default_mask_asc(const char *p);
-
-// ASN1_STRING_get_default_mask returns |B_ASN1_UTF8STRING|.
-OPENSSL_EXPORT unsigned long ASN1_STRING_get_default_mask(void);
-
-OPENSSL_EXPORT ASN1_STRING *ASN1_STRING_set_by_NID(ASN1_STRING **out,
-                                                   const unsigned char *in,
-                                                   int inlen, int inform,
-                                                   int nid);
-OPENSSL_EXPORT ASN1_STRING_TABLE *ASN1_STRING_TABLE_get(int nid);
-OPENSSL_EXPORT int ASN1_STRING_TABLE_add(int, long, long, unsigned long,
-                                         unsigned long);
-OPENSSL_EXPORT void ASN1_STRING_TABLE_cleanup(void);
-
 // ASN1 template functions
 
 // Old API compatible functions