crlite processes new stashes in O(n^2), whereas it can be O(n)
Categories
(Core :: Security: PSM, defect, P1)
Tracking
()
People
(Reporter: keeler, Assigned: keeler)
References
(Blocks 1 open bug)
Details
(Whiteboard: [psm-assigned])
Crash Data
Attachments
(1 file)
(deleted),
text/x-phabricator-request
|
RyanVM
:
approval-mozilla-beta+
|
Details |
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).
![]() |
Assignee | |
Comment 1•4 years ago
|
||
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
Comment 3•4 years ago
|
||
bugherder |
![]() |
Assignee | |
Comment 4•4 years ago
|
||
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:
Comment 5•4 years ago
|
||
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.
Updated•4 years ago
|
Updated•4 years ago
|
Description
•