<div dir="ltr"><div><div>Hi,<br></div> here it is; implemented, documented, unit-tested, build-tested.<br></div>Permission to merge (as soon as the build farm confirms portability) ?<br></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jul 27, 2015 at 1:50 AM, Amos Jeffries <span dir="ltr"><<a href="mailto:squid3@treenet.co.nz" target="_blank">squid3@treenet.co.nz</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On 27/07/2015 8:47 a.m., Kinkie wrote:<br>
> On Sun, Jul 26, 2015 at 10:23 PM, Amos Jeffries <<a href="mailto:squid3@treenet.co.nz">squid3@treenet.co.nz</a>><br>
<div><div class="h5">> wrote:<br>
><br>
>> On 27/07/2015 4:48 a.m., Kinkie wrote:<br>
>>> HI,<br>
>>> the low-hanging fruits from Coverity's analysis have been picked, now<br>
>>> working on somewhat more complex fixes.<br>
>>> The attached patch takes a hint from two benign coverity defects to:<br>
>><br>
>>> - refactor Digest auth's field lookup table to use a std::map instead of<br>
>>> abusing httpHeaderFieldsInfo; this improves readability and size of the<br>
>>> code, and has the added small bonus of lowering the lookup cost from<br>
>> linear<br>
>>> to logarithmic<br>
>>><br>
>>> the Digest code has been run-tested. I'd like feedback on its style, as<br>
>>> httpHeaderFieldsInfo is abused similarly elswehere and I'm considering to<br>
>>> apply it elsewhere as well; it can then be further refined to get O(1)<br>
>> via<br>
>>> a carefully-chosen hash (via std::unsorted_map)<br>
>>><br>
>><br>
>> My thoughts: (sorry if its a bit rambling)<br>
>><br>
>> I dont like spawning lots of new classes for basic things. I know its<br>
>> essentially the C++ way. But applying pattern theory can go too far<br>
>> sometimes. And this patterns usage is one case where I can see exactly<br>
>> that happening.<br>
>><br>
>> You have a struct, a class, an enum and array. Thats a lot of custom<br>
>> infrastructure just to represent a simple set of name:id. We could as<br>
>> easily have std::map<const char*, enum> holding that directly and avoid<br>
>> all the local types except enum.<br>
>><br>
>> There are already 5 headers currently in Squid that need these same<br>
>> operations applied, and at least as many more that should but dont even<br>
>> use the current HttpHeaderFieldAttrs related types yet.<br>
>><br>
>><br>
>><br>
>> struct HttpDigestFieldAttrs should be a template class so we dont have<br>
>> to re-implement a new little struct for each enum.<br>
>><br>
>> BUT, notice that generalizing that same structure is also where the enum<br>
>> casting hack for HttpHeaderFieldAttrs comes from in the first place.<br>
>> The probkem was template style breaks with C++03 compilers thinking all<br>
>> enums are of "int" type. Enter lots of repeated-instantiation complaints<br>
>> from dumb compilers.<br>
>> I've not tried it with current C++11 compilers which are quite a bit<br>
>> smarter. It may work now (or not).<br>
>><br>
>> If *that* can be solved then refactoring HttpHeaderFieldAttrs to a<br>
>> template is better way forward. Maybe followed by replacing or<br>
>> refactoring the HttpHeaderFieldInfo bits to avoid the performance<br>
>> problem you identified.<br>
>><br>
><br>
> Hi,<br>
> no rambling, it's ok.<br>
> Actually, the performance improvement is just a nice byproduct, that's not<br>
> the objective at all, as I tried explaining in the merge proposal.<br>
> The actual problem I was addressing is the multiple C casts used to try and<br>
> coerce anything resembling a map<const char *, int> into an http/1 header<br>
> table, simply because there is code in squid which implements that map as a<br>
> header table (and rather naively, at that - linear scan is SO fifties ;) ).<br>
><br>
> In fact, I argue that the proposed version is actually simpler than the<br>
> previous code; it can maybe even be simplified further but not much<br>
> further, let's go over it a bit toghether if you want.<br>
<br>
</div></div>It looks that way for a single case. But multiply the number of<br>
type-specific little class and structs by 5, 10, 20 and the moving<br>
pieces get to be so many that we can't be sure all the manualy crafted<br>
bits actually all are doing the same thing.<br>
So when the compilers let that template simplfication happen we may<br>
discover multiple little hacks all over needing to fix.<br>
<span class=""><br>
><br>
> struct HttpDigestFieldAttrs is there simply to have a convenient<br>
> representation of the header table DigestAttrs. It makes no attempt to be<br>
> anything different. Can it be turned into<br>
> GenericInitializerFromStringTo<enum foo> ? Yes. Is it worth it for 3 LOC?<br>
> not so sure.<br>
><br>
> DigestFieldslookupTable_t is probably what you are lashing out at, I bet.<br>
<br>
</span>Its itching. :-)<br>
<span class=""><br>
> Yes, it could be made generic and templatized to represent a<br>
> SBuf-to-anything with a static table initializer. I haven't tried that as<br>
> that may be PMO and it may preclude turning the index from a map to an<br>
> unordered_map with a table-specific hasher (gperf-generated or<br>
> hand-written, it's rather trivial to do it in this and in many other cases<br>
> we care about).<br>
<br>
</span>I don't think that would be a problem. Since we dont need to change the<br>
stored node types under the maps feet. The type / header name is always<br>
pre-known, even when generating them dynamically as part of message parsing.<br>
<br>
<br>
Try these ...<br>
<br>
src/base/LookupTable.h:<br>
<br>
/**<br>
* SBuf -> enum lookup table.<br>
*/<br>
template<class EnumType><br>
class LookupTable {<br>
public:<br>
typedef struct Record_ {<br>
const char *name;<br>
EnumType id;<br>
} Record;<br>
<br>
LookupTable(const EnumType theInvalid, const Record data[]) :<br>
invalidValue(theInvalid)<br>
{<br>
for (auto i = 0; data[i].name != nullptr; ++i) {<br>
lookupTable[SBuf(data[i].name)] = data[i].id;<br>
}<br>
}<br>
<br>
EnumType lookup(const SBuf &key) const {<br>
auto r = lookupTable.find(key);<br>
if (r == lookupTable.end())<br>
return invalidValue;<br>
return r->second;<br>
}<br>
<br>
private:<br>
typedef std::map<const SBuf, EnumType> lookupTable_t;<br>
lookupTable_t lookupTable;<br>
EnumType invalidValue;<br>
};<br>
<br>
<br>
<br>
<br>
in src/auth/digest/Config.cc (or wherever else needs a table):<br>
<br>
static const LookupTable<http_digest_attr_type>::Record<br>
DigestAttrs_Exp[] = {<br>
{"username", DIGEST_USERNAME},<br>
{"realm", DIGEST_REALM},<br>
{"qop", DIGEST_QOP},<br>
{"algorithm", DIGEST_ALGORITHM},<br>
{"uri", DIGEST_URI},<br>
{"nonce", DIGEST_NONCE},<br>
{"nc", DIGEST_NC},<br>
{"cnonce", DIGEST_CNONCE},<br>
{"response", DIGEST_RESPONSE},<br>
{nullptr, DIGEST_ENUM_END}<br>
};<br>
<br>
LookupTable<http_digest_attr_type><br>
DigestFieldsLookupTable(DIGEST_ENUM_END, DigestAttrs_Exp);<br>
<br>
<br>
<br>
NOTE: range based for loops require begin/end operators. The default<br>
definitions dont work for templated things apparently.<br>
The constructor for loop is explicit now only because I could not be<br>
bothered creating new ones for the LookupTable<DataType>::Record type.<br>
<br>
Or we could be a bit fancy and use a while loop instead. Then magically<br>
derive the invalidValue from whatever array entry has the nullptr for<br>
its name.<br>
<span class=""><br>
<br>
><br>
> The patch has been build-tested successfully on all platforms we care<br>
> about, and run-tested (refactoring went in two phases: add new code,<br>
> assert() that it behaves like the old code and run-test, rip old code out).<br>
><br>
> IMVHO HttpHeaderFieldAttrs is poor legacy, and deserves a thankful and<br>
> merciful eviction from our code-base :)<br>
<br>
</span>Look closer. Its doing the exact same job as your HttpDigestFieldAttrs<br>
but for a different enum name. That job wont change so long as that<br>
other enum exists in Squid. And in your design we have a struct per enum<br>
either way.<br>
<br>
So applying this patch goes from x1 to x2 custom and slightly different<br>
instances of the pattern. They you get to the S-C header that needs its<br>
own version, now its got x3 instances. And so on.<br>
<br>
The code re-use is not a future need. Its already got somewhere between<br>
4 and 10 use cases existing in Squid that need to be updated. Then<br>
theres the headers we have not implemented specific code for yet.<br>
<br>
<br>
With my above template the pattern remains the same. Even uses almost<br>
all your code. But we only define the custom enum + name array, and<br>
instantiate a LookupTable from those.<br>
<br>
PS. You can probably even remove HttpHeaderFieldAttrs,<br>
HttpHeaderFieldInfo and friends entirely in favour of LookupTable<>.<br>
Though I saw some stats gathering also going on when I looked at those.<br>
Which is just another reason for it all to be kept identical/consistent<br>
- counting digest field value sightings is an (un)important as cache<br>
control ones.<br>
<span class="HOEnZb"><font color="#888888"><br>
Amos<br>
<br>
</font></span></blockquote></div><br><br clear="all"><br>-- <br><div class="gmail_signature"> Francesco</div>
</div>