Bug 152828 – Replace HTTPHeaderMap by HTTPHeaderList

• Component: WebCore Misc.
• Status: RESOLVED WONTFIX

[youenn fablet]

As discussed in bug 152384, a header set container should:
- support several headers with the same name
- retain insertion order for headers with the same name
- support several headers with the same name and value

It might be better to use a list container than a map container as currently done in HTTPHeaderMap, and the container name could be updated accordingly.

[Alex Christensen]

We also need to keep information about the first header with each name so that set, get, contains, etc. don't have to search the whole list every time they are called.

[youenn fablet]

(In reply to comment #1)
> We also need to keep information about the first header with each name so
> that set, get, contains, etc. don't have to search the whole list every time
> they are called.

Keeping the first index would optimize the case of get and contains.
set and remove would remain O(n), at least in a worst case scenario.
It would also slow down append().

I would first like to have a simple functional HTTPHeaderList with a clean API. Then it could be optimized internally to handle large sets.

For instance, keeping-first-index mechanism might be triggered when header set size is above a given threshold. Or it can be done lazily when a header is actually get.

[Alex Christensen]

(In reply to comment #2)
> (In reply to comment #1)
> > We also need to keep information about the first header with each name so
> > that set, get, contains, etc. don't have to search the whole list every time
> > they are called.
> 
> Keeping the first index would optimize the case of get and contains.
> set and remove would remain O(n), at least in a worst case scenario.
> It would also slow down append().
We should also keep track of which headers only have one header in the list with the given name, so set and remove will be O(1) for headers with a unique name.  Headers with a non-unique name will still be O(n), but remove needs to be O(n) anyways to update the structures.
> 
> I would first like to have a simple functional HTTPHeaderList with a clean
> API. Then it could be optimized internally to handle large sets.
This would be a performance regression until the optimizations are done.  I don't think we should do this.
> 
> For instance, keeping-first-index mechanism might be triggered when header
> set size is above a given threshold. 
This would make it hard to find bugs that only appear in large lists or near the threshold.  I don't think we should do this.  Optimizing for small lists is a premature optimization.
> Or it can be done lazily when a header is actually get.
This would make get slow.

Basically, we should not use data structures that assume that the number of headers will always stay small.  This is a bad assumption unless you can verify that there is no important use of many headers on the entire internet.

[youenn fablet]

> > I would first like to have a simple functional HTTPHeaderList with a clean
> > API. Then it could be optimized internally to handle large sets.
> This would be a performance regression until the optimizations are done.  I
> don't think we should do this.

I don't fully agree here.
Practically speaking, it would be a small performance improvement, except for one hypothetical case.
I am not against supporting this hypothetical case.
But there is a tradeoff here, the question is then how valuable is it to support it compared to complexity/maintenance cost?

In libsoup, the headers are stored as arrays.
Some headers are made specific (Content-Type, Content-Length) to be retrieved quickly.
IIRC, lazy optimization is also done to retrieve quickly combined header values.

Libcurl is lower-level so does not provide direct get/remove API but the principle is similar.

A list of header is good in the sense that it is fast to build and above layer can rearrange it for their own needs.
From a web application POV, it can do its own optimization, like always using append(), building their own map to have fast get()...
Web applications benefit from being built on top of a thin layer.

WebKit is using get() on header names found in HTTPHeaderNames.in.
To take that into account, we can optimize get() for some/all of those header names.

This can be achieved using dedicated member fields, or an additional hashmap<HTTPHeaderName, index> or even a vector given the number of common header names (< 100).
For those "indexed" header names, a header entry could also store the index to the next header with the same name.

> > For instance, keeping-first-index mechanism might be triggered when header
> > set size is above a given threshold. 
> This would make it hard to find bugs that only appear in large lists or near
> the threshold.

I agree in general. At the same time, it does not sound too difficult to add suffficient test coverage for it.

> > Or it can be done lazily when a header is actually get.
> This would make get slow.

get would be slow the first time only, and only if number of headers N is very large.
If we look at a typical case when processing a message (request or response), there will be N append operations and M get operations. 
But M is much smaller than N when N becomes large.
Having a fast append is appealing, having an amortized fast get sounds reasonnable to me.

[youenn fablet]

Created attachment 268688 [details]
WIP

[WebKit Commit Bot]

Attachment 268688 [details] did not pass style-queue:


ERROR: Source/WebKit2/WebProcess/Plugins/PluginController.h:65:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/platform/network/HTTPHeaderList.h:43:  Should be indented on a separate line, with the colon or comma first on that line.  [whitespace/indent] [4]
Total errors found: 2 in 82 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[youenn fablet]

(In reply to comment #5)
> Created attachment 268688 [details]
> WIP

Current patch does not contain any optimization for large arrays.

The add/set/get of HTTPHeaderMap should map to combine/set/getAllAsCombined of HTTPHeaderList.

append() is not used as it would probably increase chances for behavior changes.

[Build Bot]

Comment on attachment 268688 [details]
WIP

Attachment 268688 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.webkit.org/results/678978

New failing tests:
http/tests/misc/authentication-redirect-4/authentication-sent-to-redirect-same-origin-url.html
http/tests/misc/authentication-redirect-2/authentication-sent-to-redirect-same-origin.html
http/tests/security/401-logout/401-logout.php
http/tests/misc/authentication-redirect-1/authentication-sent-to-redirect-cross-origin.html
http/tests/misc/authentication-redirect-3/authentication-sent-to-redirect-same-origin-with-location-credentials.html
http/tests/misc/401-alternative-content.php
http/tests/loading/authentication-after-redirect-stores-wrong-credentials/authentication-after-redirect-stores-wrong-credentials.html
http/tests/xmlhttprequest/failed-auth.html
http/tests/xmlhttprequest/remember-bad-password.html
http/tests/loading/basic-auth-resend-wrong-credentials.html
http/tests/loading/basic-credentials-sent-automatically.html

[Build Bot]

Created attachment 268689 [details]
Archive of layout-test-results from ews104 for mac-yosemite-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: ews104  Port: mac-yosemite-wk2  Platform: Mac OS X 10.10.5

[Alex Christensen]

Comment on attachment 268688 [details]
WIP

View in context: https://bugs.webkit.org/attachment.cgi?id=268688&action=review

I know this is WIP, but here is some initial feedback.

> Source/WebCore/ChangeLog:9
> +        TODO: Remove HTTPHeaderMap.h/.c

Please do in this patch.

> Source/WebCore/ChangeLog:13
> +        * WebCore.order:

It's not necessary to touch WebCore.order.

> Source/WebKit2/ChangeLog:52
> +        * mac/WebKit2.order:

No need to touch this, either.

> Source/WebCore/platform/network/HTTPHeaderList.cpp:44
> +/*

Please don't include commented-out code like this.

> Source/WebCore/platform/network/HTTPHeaderList.h:121
> +    Vector<HTTPHeader> m_headers;

I'm still not entirely convinced that this is the right structure for something like this.  There are a lot of unnecessary loops searching through this whole list.

> Source/WebCore/platform/network/ResourceRequestBase.cpp:256
> +    // FIXME: we should be using append.
>      m_httpHeaderFields.set(name, value);

Is this true?  What if it already has a header with the same name.  The existing behavior would overwrite that header, right?

> Source/WebCore/platform/network/ResourceRequestBase.cpp:464
> -    m_httpHeaderFields.add(name, value);
> +    m_httpHeaderFields.combine(name, value);

Please justify and test all functional changes like this.

> Source/WebCore/platform/network/cf/ResourceResponseCFNet.cpp:63
> +    fprintf(stderr, "addToHTTPHeaderList %s: %s\n", key, value);

Please remove.

> Source/WebKit2/WebProcess/Plugins/PluginProxy.h:49
> +

Unnecessary whitespace before and after.

> Tools/TestWebKitAPI/Tests/WebCore/HTTPHeaderList.cpp:44
> +TEST_F(HTTPHeaderListTest, AppendTest)

API tests like this are great!

[youenn fablet]

(In reply to comment #10)
> Comment on attachment 268688 [details]
> WIP
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=268688&action=review
> 
> I know this is WIP, but here is some initial feedback.

Thanks for the review.

> 
> > Source/WebCore/ChangeLog:9
> > +        TODO: Remove HTTPHeaderMap.h/.c
> 
> Please do in this patch.

Sure, it is just a reminder for me actually.
I'll do that at the end.

> 
> > Source/WebCore/ChangeLog:13
> > +        * WebCore.order:
> 
> It's not necessary to touch WebCore.order.

If so, can the file be removed?

> > Source/WebKit2/ChangeLog:52
> > +        * mac/WebKit2.order:
> 
> No need to touch this, either.

Ditto, can we remove this file?

> > Source/WebCore/platform/network/HTTPHeaderList.cpp:44
> > +/*
> 
> Please don't include commented-out code like this.

Sure.

> > Source/WebCore/platform/network/HTTPHeaderList.h:121
> > +    Vector<HTTPHeader> m_headers;
> 
> I'm still not entirely convinced that this is the right structure for
> something like this.  There are a lot of unnecessary loops searching through
> this whole list.

Let's continue discussing this.

The patch is already big, hence why I would prefer to tackle it as a subsequent patch.
Optimizing it should only impact HTTPHeaderList.h/.cpp.

> > Source/WebCore/platform/network/ResourceRequestBase.cpp:256
> > +    // FIXME: we should be using append.
> >      m_httpHeaderFields.set(name, value);
> 
> Is this true?  What if it already has a header with the same name.  The
> existing behavior would overwrite that header, right?

Right the current behavior is to overwrite the header and this patch is keeping this behavior.
Ideally, internally, we should try use as much as possible append and get, not set and getAllAsCombined.
I will remove the FIXME here and keep it only in HTTPHeaderList.

> > Source/WebCore/platform/network/ResourceRequestBase.cpp:464
> > -    m_httpHeaderFields.add(name, value);
> > +    m_httpHeaderFields.combine(name, value);
> 
> Please justify and test all functional changes like this.

This is not a functional change actually.
HTTPHeaderMap::add is doing the same as HTTPHeaderField::combine.
Again here, I would prefer WebKit to use HTTPHeaderField::append but this will certainly break WebKit code.

> > Source/WebCore/platform/network/cf/ResourceResponseCFNet.cpp:63
> > +    fprintf(stderr, "addToHTTPHeaderList %s: %s\n", key, value);
> 
> Please remove.

Sure

> 
> > Source/WebKit2/WebProcess/Plugins/PluginProxy.h:49
> > +
> 
> Unnecessary whitespace before and after.

OK

[youenn fablet]

> This is not a functional change actually.
> HTTPHeaderMap::add is doing the same as HTTPHeaderField::combine.
> Again here, I would prefer WebKit to use HTTPHeaderField::append but this
> will certainly break WebKit code.

s/HTTPHeaderField/HTTPHeaderList/

[youenn fablet]

Created attachment 268771 [details]
WIP2

[WebKit Commit Bot]

Attachment 268771 [details] did not pass style-queue:


ERROR: Source/WebKit2/WebProcess/Plugins/PluginController.h:65:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/platform/network/HTTPHeaderList.h:43:  Should be indented on a separate line, with the colon or comma first on that line.  [whitespace/indent] [4]
Total errors found: 2 in 83 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Build Bot]

Comment on attachment 268771 [details]
WIP2

Attachment 268771 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.webkit.org/results/682908

New failing tests:
http/tests/xmlhttprequest/failed-auth.html

[Build Bot]

Created attachment 268775 [details]
Archive of layout-test-results from ews103 for mac-yosemite

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: ews103  Port: mac-yosemite  Platform: Mac OS X 10.10.5

[Build Bot]

Comment on attachment 268771 [details]
WIP2

Attachment 268771 [details] did not pass mac-debug-ews (mac):
Output: http://webkit-queues.webkit.org/results/682893

New failing tests:
http/tests/xmlhttprequest/failed-auth.html

[Build Bot]

Created attachment 268776 [details]
Archive of layout-test-results from ews117 for mac-yosemite

The attached test failures were seen while running run-webkit-tests on the mac-debug-ews.
Bot: ews117  Port: mac-yosemite  Platform: Mac OS X 10.10.5

[Build Bot]

Comment on attachment 268771 [details]
WIP2

Attachment 268771 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.webkit.org/results/682912

New failing tests:
http/tests/xmlhttprequest/failed-auth.html

[Build Bot]

Created attachment 268777 [details]
Archive of layout-test-results from ews104 for mac-yosemite-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: ews104  Port: mac-yosemite-wk2  Platform: Mac OS X 10.10.5

[youenn fablet]

Created attachment 268778 [details]
Fixing mac and test

[WebKit Commit Bot]

Attachment 268778 [details] did not pass style-queue:


ERROR: Source/WebKit2/WebProcess/Plugins/PluginController.h:65:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/platform/network/HTTPHeaderList.h:43:  Should be indented on a separate line, with the colon or comma first on that line.  [whitespace/indent] [4]
Total errors found: 2 in 81 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Alex Christensen]

(In reply to comment #11)
> > > Source/WebCore/ChangeLog:13
> > > +        * WebCore.order:
> > 
> > It's not necessary to touch WebCore.order.
> 
> If so, can the file be removed?
No, I think it's updated and used about once a year.  It needs to be there, but it's ok if it has stale symbol names most of the year.
> 
> > > Source/WebKit2/ChangeLog:52
> > > +        * mac/WebKit2.order:
> > 
> > No need to touch this, either.
> 
> Ditto, can we remove this file?
No.
> > > Source/WebCore/platform/network/HTTPHeaderList.h:121
> > > +    Vector<HTTPHeader> m_headers;
> > 
> > I'm still not entirely convinced that this is the right structure for
> > something like this.  There are a lot of unnecessary loops searching through
> > this whole list.
> 
> Let's continue discussing this.
> 
> The patch is already big, hence why I would prefer to tackle it as a
> subsequent patch.
> Optimizing it should only impact HTTPHeaderList.h/.cpp.
The patch won't be too big to review an land with this optimization, and it will be replacing an optimized data structure with another optimized data structure, which will hopefully prevent any performance regressions, however temporary.

[youenn fablet]

> > The patch is already big, hence why I would prefer to tackle it as a
> > subsequent patch.
> > Optimizing it should only impact HTTPHeaderList.h/.cpp.
> The patch won't be too big to review an land with this optimization, and it
> will be replacing an optimized data structure with another optimized data
> structure, which will hopefully prevent any performance regressions, however
> temporary.

The current code is expecting a map structure and is optimized accordingly.
set() is used extensively for instance which is ok for a map but expensive compared to append() for a list.

Another example is operator==, which is currently o(n2) because mac-wk2 is apparently not keeping the order of headers in the case of authentication.
If we can fix that, then operator== can use Vector operator==.

I am not opposed to update this patch as follows:
- Add a m_next field to HTTPHeader to keep the information for the next header with same name
- Add a HashMap<HTTPHeaderName, size_t> to keep position of the first header.

Would it work for you?

[Alex Christensen]

(In reply to comment #24)
> I am not opposed to update this patch as follows:
> - Add a m_next field to HTTPHeader to keep the information for the next
> header with same name
> - Add a HashMap<HTTPHeaderName, size_t> to keep position of the first header.
> 
> Would it work for you?
I think that would be good.

[youenn fablet]

Created attachment 268963 [details]
Adding optimization

[WebKit Commit Bot]

Attachment 268963 [details] did not pass style-queue:


ERROR: Source/WebKit2/WebProcess/Plugins/PluginController.h:65:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/platform/network/HTTPHeaderList.h:44:  Should be indented on a separate line, with the colon or comma first on that line.  [whitespace/indent] [4]
Total errors found: 2 in 81 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[youenn fablet]

Created attachment 268965 [details]
Tentative win fix

[youenn fablet]

(In reply to comment #26)
> Created attachment 268963 [details]
> Adding optimization

Patch introduces a map that stores for each present header common name, the position of the first corresponding header and whether there are multiple headers with this name.

The code is not using String move constructor where it could.
This might bring some limited benefits.

[WebKit Commit Bot]

Attachment 268965 [details] did not pass style-queue:


ERROR: Source/WebKit2/WebProcess/Plugins/PluginController.h:65:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/platform/network/HTTPHeaderList.h:44:  Should be indented on a separate line, with the colon or comma first on that line.  [whitespace/indent] [4]
Total errors found: 2 in 82 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Alex Christensen]

Comment on attachment 268965 [details]
Tentative win fix

View in context: https://bugs.webkit.org/attachment.cgi?id=268965&action=review

> Source/WebCore/ChangeLog:16
> +        Moving from header member acces to getter/setter.

access

> Source/WebCore/platform/network/HTTPHeaderList.cpp:2
> + * Copyright (C) 2015 Canon Inc.

2016

> Source/WebCore/platform/network/HTTPHeaderList.cpp:56
> +    // FIXME: We cannot use a.m_headers == b.m_headers, as at least one Mac HTTP backend is not keeping header order.

This is a big problem.  CFNetwork uses a dictionary to keep track of the headers in an NSHTTPRequest, which means that even if we use this new-and-improved order-retaining multiple-header-with-same-name-allowing structure to keep track of our headers, the order might not be retained when actually sending the request.

> Source/WebCore/platform/network/HTTPHeaderList.h:2
> + * Copyright (C) 2015 Canon Inc.

2016

> Source/WebCore/platform/network/HTTPHeaderList.h:41
> +class HTTPHeader {

I think this class is significant enough to be put in its own header/cpp.

[Chris Dumez]

Comment on attachment 268965 [details]
Tentative win fix

View in context: https://bugs.webkit.org/attachment.cgi?id=268965&action=review

> Source/WebCore/ChangeLog:10
> +        meaningful in case of several headers with the same name inserted.

HTTPHeaderMap was also keep the insertion order in this case, right? if HTTPHeaderMap::add() gets called several times with the same HTTP Header name, we'll just append the new value to the existing value (comma-separated). Therefore, we already have an ordered list of values for a given HTTP Header name.

[Chris Dumez]

Comment on attachment 268965 [details]
Tentative win fix

View in context: https://bugs.webkit.org/attachment.cgi?id=268965&action=review

>> Source/WebCore/ChangeLog:10
>> +        meaningful in case of several headers with the same name inserted.
> 
> HTTPHeaderMap was also keep the insertion order in this case, right? if HTTPHeaderMap::add() gets called several times with the same HTTP Header name, we'll just append the new value to the existing value (comma-separated). Therefore, we already have an ordered list of values for a given HTTP Header name.

Also, according to http://tools.ietf.org/html/rfc7230#section-3.2.2 (which replaces RFC2616):
"The order in which header fields with differing field names are received is not significant."
and
"A sender MUST NOT generate multiple header fields with the same field name in a message unless either the entire field value for that header field is defined as a comma-separated list [i.e., #(values)] or the header field is a well-known exception (as noted below)."

So it seems to me our current approach of merging separate fields that have the same name into a comma-separated value is correct (does not change the meaning).

[youenn fablet]

(In reply to comment #32)
> Comment on attachment 268965 [details]
> Tentative win fix
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=268965&action=review
> 
> > Source/WebCore/ChangeLog:10
> > +        meaningful in case of several headers with the same name inserted.
> 
> HTTPHeaderMap was also keep the insertion order in this case, right? if
> HTTPHeaderMap::add() gets called several times with the same HTTP Header
> name, we'll just append the new value to the existing value
> (comma-separated). Therefore, we already have an ordered list of values for
> a given HTTP Header name.

Right, but the map will not keep the insertion order for other headers.
This order is not meaningful at the HTTP level, except for some very specific headers (Set-Cookie, maybe others headers).

But the API defined to handle headers in the fetch API is defined so that header insertion order is preserved. Appending a header or combining it will lead to two different header sets at the fetch API level, although this will be semantically equivalent when serialized at the protocol level.

There are different approaches that can be taken:
1. Have a specific header structure for fetch API (a list) and translate it into HTTPHeaderMap, that will be used for the mac network binding.
2. Have an abstract header structure that matches the fetch API (a list) used within WebKit, network bindings taking it and mapping it to whatever structures they have. Mac binding would combine headers at that time.
3. Change the fetch API spec (see https://github.com/whatwg/fetch/issues/189 for instance) to match something closer to HTTPHeaderMap

I would like to avoid option 1 if possible.

[youenn fablet]

> So it seems to me our current approach of merging separate fields that have
> the same name into a comma-separated value is correct (does not change the
> meaning).

Right, it does not change the meaning at the protocol level, except maybe Set-Cookie.

[youenn fablet]

> This is a big problem.  CFNetwork uses a dictionary to keep track of the
> headers in an NSHTTPRequest, which means that even if we use this
> new-and-improved order-retaining multiple-header-with-same-name-allowing
> structure to keep track of our headers, the order might not be retained when
> actually sending the request.

There is no need to retain the order of the headers with different names at the network level. So this is safe.

I agree that the current operator== is not very nice.

The issue here is that a first HTTPHeaderList is built from Mac network layer. And another one is built and compared to the first one in the context of Authentication Challenge.
I have not yet checked the root of the problem, why this happens and potential solutions.

[youenn fablet]

> 3. Change the fetch API spec (see https://github.com/whatwg/fetch/issues/189
> for instance) to match something closer to HTTPHeaderMap

Corresponding thread is at: https://lists.w3.org/Archives/Public/www-archive/2016Jan/0006.html

[youenn fablet]

(In reply to comment #37)
> > 3. Change the fetch API spec (see https://github.com/whatwg/fetch/issues/189
> > for instance) to match something closer to HTTPHeaderMap
> 
> Corresponding thread is at:
> https://lists.w3.org/Archives/Public/www-archive/2016Jan/0006.html

The Fetch spec should be changed so that the Headers API will stop exposing multiple headers with the same name. get should for instance return a combined value and iteration should be done lexicographically.

Behind it, the structure may be a map or a list, so HTTPHeaderMap is directly usable as is.

Using a list has some advantages though:
- For requests, keeping headers as the web app is entering them may give some small benefits: not combining headers (if supported) may give better HPACK compression, serializing more important headers first may help proxy processing.
- It is conceptually a thinner layer that tries to do less to let higher levels do more and better). For instance, it has one less hashmap internally.
- It maps well with libcurl & libsoup
- Lexicographical iteration is probably more straightforward

That said, given past discussions, I am not planning to push it further.