Yes, those are the problematic cases.  I think that making the symbols weak is 
“good enough” for the moment.  Longer term, we could do with a better solution. 
 Moving the implementations into another file is one option.  There is another 
longer term alternative: migrate OpenSSL away from lhash and safestack by 
introducing new internal functionality that replaces them.  We can’t remove 
either in case users user them but we could stop using them ourselves.

Lhash is based on a clever hash table that dynamically resizes (both increasing 
and decreasing) and amortises the rehashing costs over time.  If the OpenSSL 
source code is looked through, there are relatively few removals from the hash 
table.  I.e. the size decrease isn’t used much, if at all.  Likewise, the 
rehashing checks one bit in the hash for each item and moves it into one of two 
lists based based on the result.  I.e. rehashing should be a fast operation and 
amortising it doesn’t feel like a win.  On the down side, lhash runs with a 
fairly high level of loading (many entries relative to table size) and its 
collision resolution is a linked list (i.e. O(n) worst case instead of O(1)).  
There have also been improvements in hash technology since the lhash algorithm 
was created — cache coherent algorithms and lock free ones spring to mind.

Safestack isn’t a stack anymore.  It is used as a vector, an array substitute, 
a queue and more.  I don’t think I’ve seen it used as a stack but it probably 
is.  We should have separate data structures for the different uses, each 
optimised for its specific usage.

This would be a long path (and I’m hijacking this thread a bit), but it is 
something I’ve been wanting to do for a while now.

Dr Paul Dale | Cryptographer | Network Security & Encryption 
Phone +61 7 3031 7217
Oracle Australia

> On 27 Jan 2019, at 10:58 pm, Richard Levitte <> wrote:
> You're talking about these lines from safestack.h:
> and these from lhash.h:
> I didn't think of those when looking at the PR, but you're entirely
> correct that they are the direct cause of the issue, and should move
> to someplace internal.
> Cheers,
> Richard
> On Sun, 27 Jan 2019 12:30:07 +0100,
> Dr Paul Dale wrote:
>> I’d generally prefer functions over macros — I think that the ctrl calls 
>> e.g. would be better
>> wrapped with function to provide type checking.
>> The overhead of a function call is pretty light these days so inline 
>> functions are difficult to
>> justify (as anything except a premature optimisation?).
>> Both safestack and lhash are problematic cases.  The inline functions come 
>> from macros which I
>> view as okay.  The problem is that some of these macros are expanded in the 
>> header for common
>> cases (e.g. stack of stings).  We could address this by distinguishing 
>> between the function
>> declarations and their instantiation and move the latter into its own C file.
>> Pauli
>> -- 
>> Dr Paul Dale | Cryptographer | Network Security & Encryption 
>> Phone +61 7 3031 7217
>> Oracle Australia
>>    On 27 Jan 2019, at 8:33 pm, Tim Hudson <> wrote:
>>    From
>>    Tim - I think inline functions in public header files simply shouldn't be 
>> present.
>>    Matt - I agree
>>    Richard - I'm ambivalent... in the case of stack and lhash, the generated 
>> functions we made
>>    static inline expressly to get better C type safety, and to get away from 
>> the
>>     horror.
>>    It would be good to get a sense of the collective thoughts on the topic.
>>    Tim.
>>    _______________________________________________
>>    openssl-project mailing list
>> _______________________________________________
>> openssl-project mailing list
> -- 
> Richard Levitte
> OpenSSL Project
> _______________________________________________
> openssl-project mailing list

openssl-project mailing list

Reply via email to