[squid-dev] [PATCH] Coverity fixes, part 3

[Amos Jeffries]

On 27/07/2015 8:47 a.m., Kinkie wrote:
> On Sun, Jul 26, 2015 at 10:23 PM, Amos Jeffries <squid3 at treenet.co.nz>
> wrote:
> 
>> On 27/07/2015 4:48 a.m., Kinkie wrote:
>>> HI,
>>>   the low-hanging fruits from Coverity's analysis have been picked, now
>>> working on somewhat more complex fixes.
>>> The attached patch takes a hint from two benign coverity defects to:
>>
>>> - refactor Digest auth's field lookup table to use a std::map instead of
>>> abusing httpHeaderFieldsInfo; this improves readability and size of the
>>> code, and has the added small bonus of lowering the lookup cost from
>> linear
>>> to logarithmic
>>>
>>> the Digest code has been run-tested. I'd like feedback on its style, as
>>> httpHeaderFieldsInfo is abused similarly elswehere and I'm considering to
>>> apply it elsewhere as well; it can then be further refined to get O(1)
>> via
>>> a carefully-chosen hash (via std::unsorted_map)
>>>
>>
>> My thoughts: (sorry if its a bit rambling)
>>
>> I dont like spawning lots of new classes for basic things. I know its
>> essentially the C++ way. But applying pattern theory can go too far
>> sometimes. And this patterns usage is one case where I can see exactly
>> that happening.
>>
>> You have a struct, a class, an enum and array. Thats a lot of custom
>> infrastructure just to represent a simple set of name:id. We could as
>> easily have std::map<const char*, enum> holding that directly and avoid
>> all the local types except enum.
>>
>> There are already 5 headers currently in Squid that need these same
>> operations applied, and at least as many more that should but dont even
>> use the current HttpHeaderFieldAttrs related types yet.
>>
>>
>>
>> struct HttpDigestFieldAttrs should be a template class so we dont have
>> to re-implement a new little struct for each enum.
>>
>> BUT, notice that generalizing that same structure is also where the enum
>> casting hack for HttpHeaderFieldAttrs comes from in the first place.
>>  The probkem was template style breaks with C++03 compilers thinking all
>> enums are of "int" type. Enter lots of repeated-instantiation complaints
>> from dumb compilers.
>>  I've not tried it with current C++11 compilers which are quite a bit
>> smarter. It may work now (or not).
>>
>> If *that* can be solved then refactoring HttpHeaderFieldAttrs to a
>> template is better way forward. Maybe followed by replacing or
>> refactoring the HttpHeaderFieldInfo bits to avoid the performance
>> problem you identified.
>>
> 
> Hi,
>   no rambling, it's ok.
> Actually, the performance improvement is just a nice byproduct, that's not
> the objective at all, as I tried explaining in the merge proposal.
> The actual problem I was addressing is the multiple C casts used to try and
> coerce anything resembling a map<const char *, int> into an http/1 header
> table, simply because there is code in squid which implements that map as a
> header table (and rather naively, at that - linear scan is SO fifties ;) ).
> 
> In fact, I argue that the proposed version is actually simpler than the
> previous code; it can maybe even be simplified further but not much
> further, let's go over it a bit toghether if you want.

It looks that way for a single case. But multiply the number of
type-specific little class and structs by 5, 10, 20 and the moving
pieces get to be so many that we can't be sure all the manualy crafted
bits actually all are doing the same thing.
So when the compilers let that template simplfication happen we may
discover multiple little hacks all over needing to fix.

> 
> struct HttpDigestFieldAttrs is there simply to have a convenient
> representation of the header table DigestAttrs. It makes no attempt to be
> anything different. Can it be turned into
> GenericInitializerFromStringTo<enum foo> ? Yes. Is it worth it for 3 LOC?
> not so sure.
> 
> DigestFieldslookupTable_t is probably what you are lashing out at, I bet.

Its itching. :-)

> Yes, it could be made generic and templatized to represent a
> SBuf-to-anything with a static table initializer. I haven't tried that as
> that may be PMO and it may preclude turning the index from a map to an
> unordered_map with a table-specific hasher (gperf-generated or
> hand-written, it's rather trivial to do it in this and in many other cases
> we care about).

I don't think that would be a problem. Since we dont need to change the
stored node types under the maps feet. The type / header name is always
pre-known, even when generating them dynamically as part of message parsing.


Try these ...

src/base/LookupTable.h:

/**
 * SBuf -> enum lookup table.
 */
template<class EnumType>
class LookupTable {
public:
    typedef struct Record_ {
        const char *name;
        EnumType id;
    } Record;

    LookupTable(const EnumType theInvalid, const Record data[]) :
        invalidValue(theInvalid)
    {
        for (auto i = 0; data[i].name != nullptr; ++i) {
            lookupTable[SBuf(data[i].name)] = data[i].id;
        }
    }

    EnumType lookup(const SBuf &key) const {
        auto r = lookupTable.find(key);
        if (r == lookupTable.end())
            return invalidValue;
        return r->second;
    }

private:
    typedef std::map<const SBuf, EnumType> lookupTable_t;
    lookupTable_t lookupTable;
    EnumType invalidValue;
};




in src/auth/digest/Config.cc (or wherever else needs a table):

static const LookupTable<http_digest_attr_type>::Record
  DigestAttrs_Exp[] = {
    {"username", DIGEST_USERNAME},
    {"realm", DIGEST_REALM},
    {"qop", DIGEST_QOP},
    {"algorithm", DIGEST_ALGORITHM},
    {"uri", DIGEST_URI},
    {"nonce", DIGEST_NONCE},
    {"nc", DIGEST_NC},
    {"cnonce", DIGEST_CNONCE},
    {"response", DIGEST_RESPONSE},
    {nullptr, DIGEST_ENUM_END}
};

LookupTable<http_digest_attr_type>
DigestFieldsLookupTable(DIGEST_ENUM_END, DigestAttrs_Exp);



NOTE: range based for loops require begin/end operators. The default
definitions dont work for templated things apparently.
The constructor for loop is explicit now only because I could not be
bothered creating new ones for the LookupTable<DataType>::Record type.

Or we could be a bit fancy and use a while loop instead. Then magically
derive the invalidValue from whatever array entry has the nullptr for
its name.


> 
> The patch has been build-tested successfully on all platforms we care
> about, and run-tested (refactoring went in two phases: add new code,
> assert() that it behaves like the old code and run-test, rip old code out).
> 
> IMVHO HttpHeaderFieldAttrs is poor legacy, and deserves a thankful and
> merciful eviction from our code-base :)

Look closer. Its doing the exact same job as your HttpDigestFieldAttrs
but for a different enum name. That job wont change so long as that
other enum exists in Squid. And in your design we have a struct per enum
either way.

So applying this patch goes from x1 to x2 custom and slightly different
instances of the pattern. They you get to the S-C header that needs its
own version, now its got x3 instances. And so on.

The code re-use is not a future need. Its already got somewhere between
4 and 10 use cases existing in Squid that need to be updated. Then
theres the headers we have not implemented specific code for yet.


With my above template the pattern remains the same. Even uses almost
all your code. But we only define the custom enum + name array, and
instantiate a LookupTable from those.

PS. You can probably even remove HttpHeaderFieldAttrs,
HttpHeaderFieldInfo and friends entirely in favour of LookupTable<>.
Though I saw some stats gathering also going on when I looked at those.
Which is just another reason for it all to be kept identical/consistent
- counting digest field value sightings is an (un)important as cache
control ones.

Amos