x509: sort stacks before finds
authorPauli <pauli@openssl.org>
Thu, 27 Apr 2023 00:58:50 +0000 (10:58 +1000)
committerPauli <pauli@openssl.org>
Mon, 1 May 2023 07:14:42 +0000 (17:14 +1000)
commitefe0222f5c9e07167aeac80d4d5e3d67aa8f1f36
treebd29251ff5e6cf9d0994fc9a7797b8c5db7dd051
parent07f9c81d20f2c972dd454e2343634586d3aa88a1
x509: sort stacks before finds

x509_trust.c, x509_vpm.c and v3_lib.c don't have a lock for their sorts.
This is no worse than the existing code which sorted silently without locks.

Addition is quadratic time in by_dir.c and v3_purp.c.  However, this
is an improvement over the older O(n^2 log n) code where each find also
sorted the stack.  Also note that v3_purp.c is limited to a maximum of
10 items, so quadratic behaviour isn't terrible.

Reviewed-by: Tomas Mraz <tomas@openssl.org>
Reviewed-by: Todd Short <todd.short@me.com>
(Merged from https://github.com/openssl/openssl/pull/20842)
crypto/x509/by_dir.c
crypto/x509/pcy_cache.c
crypto/x509/pcy_tree.c
crypto/x509/v3_addr.c
crypto/x509/v3_lib.c
crypto/x509/x509_trust.c
crypto/x509/x509_vpm.c