Closed Bug 1678762 Opened 4 years ago Closed 4 years ago

crlite processes new stashes in O(n^2), whereas it can be O(n)

Categories

(Core :: Security: PSM, defect, P1)

defect

Tracking

()

RESOLVED FIXED
85 Branch
Tracking Status
firefox84 --- fixed
firefox85 --- fixed

People

(Reporter: keeler, Assigned: keeler)

References

(Blocks 1 open bug)

Details

(Whiteboard: [psm-assigned])

Crash Data

Attachments

(1 file)

Currently, when RemoteSecuritySettings downloads multiple new stashes, it will add the first one, and reconstruct the in-memory representation of the issuer/serial hashmaps/sets, and then it will add the second one, and reconstruct the entire in-memory representation of the issuer/serial hashmaps/sets, and so on, re-doing all of the work each time. This is essentially O(n^2) work, whereas it should only require O(n).

Before this patch, when RemoteSecuritySettings would download multiple new
stashes, it would add the first one to cert_storage, which would reconstruct
the in-memory representation of all of the issuer/serial hashmaps/sets
(including preexisting ones), and then RemoteSecuritySettings would add the
second one, and cert_storage would reconstruct the entire in-memory
representation of the issuer/serial hashmaps/sets again, and so on, re-doing
all of the work each time. This is essentially O(n^2) work. This patch improves
both RemoteSecuritySettings and cert_storage to minimize this work, reducing it
to O(n).

Pushed by dkeeler@mozilla.com: https://hg.mozilla.org/integration/autoland/rev/b71f966519f1 crlite: be more efficient about processing new stashes r=kjacobs
Status: NEW → RESOLVED
Closed: 4 years ago
Resolution: --- → FIXED
Target Milestone: --- → 85 Branch

Comment on attachment 9189293 [details]
Bug 1678762 - crlite: be more efficient about processing new stashes r?kjacobs

Beta/Release Uplift Approval Request

  • User impact if declined: Periodic heavy CPU usage when processing new CRLite stashes.
  • Is this code covered by automated tests?: Yes
  • Has the fix been verified in Nightly?: No
  • Needs manual test from QE?: No
  • If yes, steps to reproduce:
  • List of other uplifts needed: None
  • Risk to taking this patch: Low
  • Why is the change risky/not risky? (and alternatives if risky): Relatively small change, covered by automated tests.
  • String changes made/needed:
Attachment #9189293 - Flags: approval-mozilla-beta?

Comment on attachment 9189293 [details]
Bug 1678762 - crlite: be more efficient about processing new stashes r?kjacobs

Thanks for including tests. Approved for 84.0b8.

Attachment #9189293 - Flags: approval-mozilla-beta? → approval-mozilla-beta+
Crash Signature: [@ shutdownhang | RtlAcquireSRWLockExclusive | std::sys::windows::c::AcquireSRWLockExclusive]
Crash Signature: [@ shutdownhang | RtlAcquireSRWLockExclusive | std::sys::windows::c::AcquireSRWLockExclusive] → [@ shutdownhang | RtlAcquireSRWLockExclusive | std::sys::windows::c::AcquireSRWLockExclusive] [@ arena_dalloc | core::ptr::drop_in_place<T> | cert_storage::SecurityState::load_crlite_stash | cert_storage::{{impl}}::run<T> | moz_task::{{impl}}::allocate::R…
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: