• Poul-Henning Kamp's avatar
    Add preliminary version of lock-less tree based lookup (see below) · 406186fa
    Poul-Henning Kamp authored
    Enable SHA256 digests by default, and put it in the objhead.  This
    increases the size of the objhead by 32 bytes, but may drop
    a bit again later, when other now unnecessary fields go away.
    
    Test SHA256 for correct operation on startup.
    
    About the "critbit" lookup:
    
    To enable this, use "-hcritbit" argument.
    
    "Crit Bit" trees, are also known under various other names, the original
    version of the idea is probably the PATRICIA tree.
    
    The basic concept is a tree structure which has nodes only where necessary
    to tell the indices apart.
    
    Our version of it, has some additional bells and whistles.
    
    First lookups do not require any locks until we reach the objhead
    we were looking for, or until we need to insert one which wasn't
    there.
    
    Second, the branch nodes are part of the objhead, as all but the
    very first will need one, this saves malloc operations big time.
    
    Now the down-sides:
    
    There are still missing bits, amongst these the "cooling off" list,
    for objheads that have been dereferenced, but where the branch-node
    is not.  Currently we just leak that memory.
    
    There is a race relating to node deref and unlocked lookup that is
    not closed, weird things may happen until I fix it.
    
    I'd be interested to hear how long it survives before it croaks,
    but apart from that, would not advocate that you use it, until
    I fix those remaining issues.
    
    
    
    git-svn-id: http://www.varnish-cache.org/svn/trunk@3454 d4fa192b-c00b-0410-8231-f00ffab90ce4
    406186fa
Makefile.am 1.84 KB