[openssl/openssl] e59165: crypto/x509: replace O(N^2) RFC 3779 canonicalisat...

  Branch: refs/heads/master
  Home:   https://github.com/openssl/openssl
  Commit: e59165a1e3df2f1cbe223406ea4fb40025e54d8a
      https://github.com/openssl/openssl/commit/e59165a1e3df2f1cbe223406ea4fb40025e54d8a
  Author: Niels Provos <[email protected]>
  Date:   2026-07-03 (Fri, 03 Jul 2026)

  Changed paths:
    M crypto/x509/v3_addr.c
    M crypto/x509/v3_asid.c
    M test/v3ext.c

  Log Message:
  -----------
  crypto/x509: replace O(N^2) RFC 3779 canonicalisation merge with linear sweep

ASIdentifierChoice_canonize and IPAddressOrRanges_canonize previously
merged adjacent entries with an in-place loop that called
sk_..._delete() after each merge, making the merge O(N^2) due to the
per-merge stack shift.

Replace the merge with a single linear sweep using a write index
distinct from the read cursor: mergeable entries fold into the
previous output's upper bound in O(1), non-mergeable entries are slid
forward into the write slot, and the source slot is set to NULL so the
ASN.1 free machinery cannot double-free on a subsequent abort.
Canonicalisation is now O(N log N) overall, bounded by the existing
sort.

Mixed-state-on-error safety is provided by the caller's normal
teardown path: OPENSSL_sk_pop unlinks without freeing, OPENSSL_sk_set
replaces without freeing the displaced value, and
ossl_asn1_item_embed_free no-ops on NULL slots, so returning early on
an inner failure leaves the stack in a state that the choice's normal
free path handles cleanly.

New regression tests in test/v3ext.c at N=8192 cover the all-merge,
no-merge, interleaved (slide-forward), range-merge,
overlap-mid-sweep, and inverted-range-mid-sweep paths; the
mixed-state teardown invariant is exercised under ASan + UBSan.

Reviewed-by: Paul Dale <[email protected]>
Reviewed-by: Bob Beck <[email protected]>
MergeDate: Fri Jul  3 19:20:01 2026
(Merged from https://github.com/openssl/openssl/pull/31147)



To unsubscribe from these emails, change your notification settings at https://github.com/openssl/openssl/settings/notifications

-- 
You received this message because you are subscribed to the Google Groups "openssl-commits" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
To view this discussion visit https://groups.google.com/a/openssl.org/d/msgid/openssl-commits/openssl/openssl/push/refs/heads/master/ff6b86-e59165%40github.com.