Repository navigation
Consider using SortedList instead of Dictionary in HttpHeaders #62846
Description
Activity
This may require a custom
SortedListimplementation (or improvements to the existing collection).
Using the existing implementation as-is would likely be worse (for example it boxes the enumerator)Well that's unfortunate. Aside from boxing the enumerator, are there other known issues?
An insertion has
O(n)runtime, so I think that disqualifies this type of collection from a DOS security perspective as well.An insertion has O(n) runtime, so I think that disqualifies this type of collection from a DOS security perspective as well.
I'm not sure it matters. We limit the size of the response headers that we will accept, so there's a bound on the total number of headers we will add. While O(n^2) isn't great, it's not necessarily a DOS as long as n is smallish.
Another alternative here might be to simply have an unsorted list of key value pairs. This has cheap insertion but makes both lookup and removal expensive. That might not be a bad tradeoff though. And if we did it this way, we could actually preserve the original header ordering, which seems like a nice benefit.
For stuff like YARP we would want to just enumerate the raw headers and not worry about grouping by header name, which means that "raw enumeration" for these sorts of scenarios would be cheap as well. Unfortunately we defined the NonValidated collection to group by header name as well...
Reacted by Miha Zupan, Cory Nelson and Sergey IvanovWhile O(n^2) isn't great, it's not necessarily a DOS as long as n is smallish.
Right, but as of right now
ncould still reach a few thousand by default which isn't ideal.Reacted by GSPPAn insertion has
O(n)runtime, so I think that disqualifies this type of collection from a DOS security perspective as well..... do we insert headers singly, or as a range?
Using the existing implementation as-is would likely be worse (for example it boxes the enumerator)
Are you referring to the non generic
SortedList?SortedList<K,V>should not do this.The generic as well. The enumerator is a struct, but the type is not publicly exposed so the
GetEnumeratorreturns anIEnumerator.
Triage:
- Would be nice to save some memory if we don't hurt CPU too much
- It may help with order of headers - we had few issues in the space
Further design discussion:
- Idea: Could we have a list/array as backing field and create something like Dictionary for string lookups? (they are rare)
- In extreme case we might want to add another API, which would return multiple headers (not happening today), unsorted
- Or perhaps just add another
IEnumerable<string, string>
Similarly,
ConcurrentDictionary<K, V>boxes its enumerator: https://docs.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentdictionary-2.getenumerator?view=net-6.0I noticed this in the same trace. It's a small impact in this case because we only enumerate the concurrent dictionary when scavenging connections.
I'm not sure why these collections were implemented so that their enumerators must be boxed. Is this simply an oversight? Can we fix it? It's a breaking change, but a very small one...
Reacted by Miha ZupanFor a dictionary approach maybe dotnet/aspnetcore#31360 is also of interest (the
AdaptiveCapacityDictionary).It's a breaking change, but a very small one...
It's a binary breaking change. I don't think it's that small. Anyone enumerating one of these today would fail at run time.
Similarly, ConcurrentDictionary<K, V> boxes its enumerator:
Reacted by Miha ZupanIt's a binary breaking change. I don't think it's that small. Anyone enumerating one of these today would fail at run time.
Makes sense, thanks for clarifying.
Reacted by Stephen Toub- ghost locked as resolved and limited conversation to collaborators
on Feb 19, 2022
The Dictionary we allocate in HttpHeaders for the headers table seems to use a significant amount of memory. Since the headers table itself is typically not that large, it seems reasonable to use SortedList instead and trade off reduced memory usage for a small amount of added CPU cost on update and retrieval -- I doubt this added CPU cost is significant, whereas the memory savings may be significant.