Avoid modifying stack in sk_find.
Bug: 828680
Change-Id: Iae5d0a9bf938a67bfd69a720126ab431d79e43ec
Reviewed-on: https://boringssl-review.googlesource.com/27304
Commit-Queue: Steven Valdez <svaldez@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
Reviewed-by: David Benjamin <davidben@google.com>
diff --git a/crypto/asn1/a_strnid.c b/crypto/asn1/a_strnid.c
index 379a79f..efbf0fa 100644
--- a/crypto/asn1/a_strnid.c
+++ b/crypto/asn1/a_strnid.c
@@ -223,6 +223,7 @@
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;
diff --git a/crypto/stack/stack.c b/crypto/stack/stack.c
index f6b4412..7aa3218 100644
--- a/crypto/stack/stack.c
+++ b/crypto/stack/stack.c
@@ -223,7 +223,7 @@
return NULL;
}
-int sk_find(_STACK *sk, size_t *out_index, void *p) {
+int sk_find(const _STACK *sk, size_t *out_index, void *p) {
if (sk == NULL) {
return 0;
}
@@ -245,7 +245,17 @@
return 0;
}
- sk_sort(sk);
+ if (!sk_is_sorted(sk)) {
+ for (size_t i = 0; i < sk->num; i++) {
+ if (sk->comp((const void **)&p, (const void **)&sk->data[i]) == 0) {
+ if (out_index) {
+ *out_index = i;
+ }
+ return 1;
+ }
+ }
+ return 0;
+ }
// sk->comp is a function that takes pointers to pointers to elements, but
// qsort and bsearch take a comparison function that just takes pointers to
diff --git a/crypto/x509/by_dir.c b/crypto/x509/by_dir.c
index 635b851..b3bfffe 100644
--- a/crypto/x509/by_dir.c
+++ b/crypto/x509/by_dir.c
@@ -387,6 +387,7 @@
*/
CRYPTO_MUTEX_lock_write(&xl->store_ctx->objs_lock);
tmp = NULL;
+ sk_X509_OBJECT_sort(xl->store_ctx->objs);
if (sk_X509_OBJECT_find(xl->store_ctx->objs, &idx, &stmp)) {
tmp = sk_X509_OBJECT_value(xl->store_ctx->objs, idx);
}
@@ -404,6 +405,7 @@
*/
if (!hent) {
htmp.hash = h;
+ sk_BY_DIR_HASH_sort(ent->hashes);
if (sk_BY_DIR_HASH_find(ent->hashes, &idx, &htmp))
hent = sk_BY_DIR_HASH_value(ent->hashes, idx);
}
@@ -422,6 +424,7 @@
ok = 0;
goto finish;
}
+ sk_BY_DIR_HASH_sort(ent->hashes);
} else if (hent->suffix < k)
hent->suffix = k;
diff --git a/crypto/x509/x509_lu.c b/crypto/x509/x509_lu.c
index 1a841db..ea01427 100644
--- a/crypto/x509/x509_lu.c
+++ b/crypto/x509/x509_lu.c
@@ -473,6 +473,7 @@
}
size_t idx;
+ sk_X509_OBJECT_sort(h);
if (!sk_X509_OBJECT_find(h, &idx, &stmp))
return -1;
@@ -604,6 +605,7 @@
size_t idx, i;
X509_OBJECT *obj;
+ sk_X509_OBJECT_sort(h);
if (!sk_X509_OBJECT_find(h, &idx, x)) {
return NULL;
}
diff --git a/crypto/x509/x509_trs.c b/crypto/x509/x509_trs.c
index c7dfcad..f899424 100644
--- a/crypto/x509/x509_trs.c
+++ b/crypto/x509/x509_trs.c
@@ -158,6 +158,7 @@
tmp.trust = id;
if (!trtable)
return -1;
+ sk_X509_TRUST_sort(trtable);
if (!sk_X509_TRUST_find(trtable, &idx, &tmp)) {
return -1;
}
diff --git a/crypto/x509/x509_vpm.c b/crypto/x509/x509_vpm.c
index 43353c6..84ec838 100644
--- a/crypto/x509/x509_vpm.c
+++ b/crypto/x509/x509_vpm.c
@@ -614,6 +614,7 @@
} else {
size_t idx;
+ sk_X509_VERIFY_PARAM_sort(param_table);
if (sk_X509_VERIFY_PARAM_find(param_table, &idx, param)) {
ptmp = sk_X509_VERIFY_PARAM_value(param_table, idx);
X509_VERIFY_PARAM_free(ptmp);
@@ -649,6 +650,7 @@
pm.name = (char *)name;
if (param_table) {
size_t idx;
+ sk_X509_VERIFY_PARAM_sort(param_table);
if (sk_X509_VERIFY_PARAM_find(param_table, &idx, &pm))
return sk_X509_VERIFY_PARAM_value(param_table, idx);
}
diff --git a/crypto/x509v3/pcy_cache.c b/crypto/x509v3/pcy_cache.c
index b8a4be2..755c079 100644
--- a/crypto/x509v3/pcy_cache.c
+++ b/crypto/x509v3/pcy_cache.c
@@ -93,6 +93,7 @@
/*
* Duplicate policy OIDs are illegal: reject if matches found.
*/
+ sk_X509_POLICY_DATA_sort(cache->data);
if (OBJ_obj2nid(data->valid_policy) == NID_any_policy) {
if (cache->anyPolicy) {
ret = -1;
@@ -262,6 +263,7 @@
X509_POLICY_DATA tmp;
tmp.valid_policy = (ASN1_OBJECT *)id;
+ sk_X509_POLICY_DATA_sort(cache->data);
if (!sk_X509_POLICY_DATA_find(cache->data, &idx, &tmp))
return NULL;
return sk_X509_POLICY_DATA_value(cache->data, idx);
diff --git a/crypto/x509v3/pcy_node.c b/crypto/x509v3/pcy_node.c
index b3edfe4..6682282 100644
--- a/crypto/x509v3/pcy_node.c
+++ b/crypto/x509v3/pcy_node.c
@@ -83,6 +83,7 @@
n.valid_policy = (ASN1_OBJECT *)id;
l.data = &n;
+ sk_X509_POLICY_NODE_sort(nodes);
if (!sk_X509_POLICY_NODE_find(nodes, &idx, &l))
return NULL;
diff --git a/crypto/x509v3/pcy_tree.c b/crypto/x509v3/pcy_tree.c
index 256fe88..136b45f 100644
--- a/crypto/x509v3/pcy_tree.c
+++ b/crypto/x509v3/pcy_tree.c
@@ -543,9 +543,11 @@
*pnodes = policy_node_cmp_new();
if (!*pnodes)
return 0;
- } else if (sk_X509_POLICY_NODE_find(*pnodes, NULL, pcy))
+ } else {
+ sk_X509_POLICY_NODE_sort(*pnodes);
+ if (sk_X509_POLICY_NODE_find(*pnodes, NULL, pcy))
return 1;
-
+ }
if (!sk_X509_POLICY_NODE_push(*pnodes, pcy))
return 0;
diff --git a/crypto/x509v3/v3_lib.c b/crypto/x509v3/v3_lib.c
index 8f5435d..d5eda3d 100644
--- a/crypto/x509v3/v3_lib.c
+++ b/crypto/x509v3/v3_lib.c
@@ -116,6 +116,7 @@
if (!ext_list)
return NULL;
+ sk_X509V3_EXT_METHOD_sort(ext_list);
if (!sk_X509V3_EXT_METHOD_find(ext_list, &idx, &tmp))
return NULL;
return sk_X509V3_EXT_METHOD_value(ext_list, idx);
diff --git a/crypto/x509v3/v3_purp.c b/crypto/x509v3/v3_purp.c
index 324de85..f70a804 100644
--- a/crypto/x509v3/v3_purp.c
+++ b/crypto/x509v3/v3_purp.c
@@ -205,6 +205,7 @@
if (!xptable)
return -1;
+ sk_X509_PURPOSE_sort(xptable);
if (!sk_X509_PURPOSE_find(xptable, &idx, &tmp))
return -1;
return idx + X509_PURPOSE_COUNT;
diff --git a/crypto/x509v3/v3_utl.c b/crypto/x509v3/v3_utl.c
index 7d109ee..589e296 100644
--- a/crypto/x509v3/v3_utl.c
+++ b/crypto/x509v3/v3_utl.c
@@ -650,6 +650,7 @@
if (!*sk)
return 0;
/* Don't add duplicates */
+ sk_OPENSSL_STRING_sort(*sk);
if (sk_OPENSSL_STRING_find(*sk, NULL, (char *)email->data))
return 1;
emtmp = BUF_strdup((char *)email->data);
diff --git a/include/openssl/stack.h b/include/openssl/stack.h
index 625f66e..6975db6 100644
--- a/include/openssl/stack.h
+++ b/include/openssl/stack.h
@@ -163,12 +163,17 @@
OPENSSL_EXPORT void *sk_delete_ptr(_STACK *sk, void *p);
// sk_find returns the first value in the stack equal to |p|. If a comparison
-// function has been set on the stack, then equality is defined by it and the
-// stack will be sorted if need be so that a binary search can be used.
-// Otherwise pointer equality is used. If a matching element is found, its
-// index is written to |*out_index| (if |out_index| is not NULL) and one is
-// returned. Otherwise zero is returned.
-OPENSSL_EXPORT int sk_find(_STACK *sk, size_t *out_index, void *p);
+// function has been set on the stack, equality is defined by it, otherwise
+// pointer equality is used. If the stack is sorted, then a binary search is
+// used, otherwise a linear search is performed. If a matching element is found,
+// its index is written to
+// |*out_index| (if |out_index| is not NULL) and one is returned. Otherwise zero
+// is returned.
+//
+// Note this differs from OpenSSL. The type signature is slightly different, and
+// OpenSSL's sk_find will implicitly sort |sk| if it has a comparison function
+// defined.
+OPENSSL_EXPORT int sk_find(const _STACK *sk, size_t *out_index, void *p);
// sk_shift removes and returns the first element in the stack, or returns NULL
// if the stack is empty.
@@ -302,8 +307,8 @@
} \
\
static inline OPENSSL_UNUSED int sk_##name##_find( \
- STACK_OF(name) *sk, size_t *out_index, ptrtype p) { \
- return sk_find((_STACK *)sk, out_index, (void *)p); \
+ const STACK_OF(name) *sk, size_t *out_index, ptrtype p) { \
+ return sk_find((const _STACK *)sk, out_index, (void *)p); \
} \
\
static inline OPENSSL_UNUSED ptrtype sk_##name##_shift(STACK_OF(name) *sk) { \
diff --git a/ssl/handshake_server.cc b/ssl/handshake_server.cc
index 5f2f41f..7ade8fc 100644
--- a/ssl/handshake_server.cc
+++ b/ssl/handshake_server.cc
@@ -334,7 +334,7 @@
SSL_HANDSHAKE *hs, const SSL_CLIENT_HELLO *client_hello,
const struct ssl_cipher_preference_list_st *server_pref) {
SSL *const ssl = hs->ssl;
- STACK_OF(SSL_CIPHER) *prio, *allow;
+ const STACK_OF(SSL_CIPHER) *prio, *allow;
// in_group_flags will either be NULL, or will point to an array of bytes
// which indicate equal-preference groups in the |prio| stack. See the
// comment about |in_group_flags| in the |ssl_cipher_preference_list_st|
diff --git a/ssl/ssl_file.cc b/ssl/ssl_file.cc
index bafa64a..ca4b0be 100644
--- a/ssl/ssl_file.cc
+++ b/ssl/ssl_file.cc
@@ -165,6 +165,7 @@
}
// Check for duplicates.
+ sk_X509_NAME_sort(sk);
if (sk_X509_NAME_find(sk, NULL, xn)) {
continue;
}
@@ -223,6 +224,7 @@
}
// Check for duplicates.
+ sk_X509_NAME_sort(stack);
if (sk_X509_NAME_find(stack, NULL, xn)) {
continue;
}
