SphynxCollexion.hpp

Go to the documentation of this file.

/*
    Copyright (c) 2009-2010 Christopher A. Taylor.  All rights reserved.

    Redistribution and use in source and binary forms, with or without
    modification, are permitted provided that the following conditions are met:

    * Redistributions of source code must retain the above copyright notice,
      this list of conditions and the following disclaimer.
    * Redistributions in binary form must reproduce the above copyright notice,
      this list of conditions and the following disclaimer in the documentation
      and/or other materials provided with the distribution.
    * Neither the name of LibCat nor the names of its contributors may be used
      to endorse or promote products derived from this software without
      specific prior written permission.

    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    POSSIBILITY OF SUCH DAMAGE.
*/

#ifndef CAT_SPHYNX_COLLEXION_HPP
#define CAT_SPHYNX_COLLEXION_HPP

#include <cat/threads/Mutex.hpp>
#include <cat/threads/RegionAllocator.hpp>
#include <cat/net/SphynxTransport.hpp>

namespace cat {


namespace sphynx {


/*
    The purpose of sphynx::Collexion and sphynx::CollexionIterator is to
    store lists of Connexion object references and iterate through them.

    Since the number of clients may be in the thousands, I feel it is
    important to scale effectively.  So in the Collexion data structure,
    insertion and removal are O(1) operations.  Also locks should be held
    for the smallest amount of time possible, so I have taken care to make
    locks short and reduce the amount of locking.  For example, the iterator
    caches large blocks of data instead of locking for each iteration.

    The design is optimized for cache usage, re-using common code to benefit
    from code cache and allocating and accessing table entries on cache line
    boundaries to double memory performance over a naive approach.
*/



template<class T>
class CollexionIterator;

template<class T>
struct CollexionElement
{
    // Number of active enumerators using this element
    // If references are held it cannot be deleted
    // so the KILL flag is set on the 'next' member and
    // the final enumerator to reduce the reference count
    // to zero is responsible for removal.
    u32 refcnt;

    // Bitfield:
    //  1 bit: COLLISION FLAG
    //  1 bit: KILL FLAG
    //  30 bits: Table index to next element in list + 1
    u32 next;

    // Data at this table element
    T *conn;
};

struct CollexionElement2
{
    // Previous table element in list + 1
    u32 last;

    // Hash of data pointer from main entry (so it doesn't need to be recalculated during growth)
    u32 hash;
};

template<class T>
class Collexion
{
    static const u32 COLLIDE_MASK = 0x80000000;
    static const u32 KILL_MASK = 0x40000000;
    static const u32 NEXT_MASK = 0x3fffffff;
    static const u32 MIN_ALLOCATED = 32;

private:
    // Number of used table elements
    u32 _used;

    // Number of allocated table elements
    u32 _allocated;

    // First table index in list of active elements
    u32 _first;

    // Primary table
    CollexionElement<T> *_table;

    // Secondary table, split off so that primary table elements will
    // fit on a cache line.  Contains data that is only accessed rarely.
    CollexionElement2 *_table2;

    // Table lock
    Mutex _lock;

protected:
    // Attempt to double size of hash table (does not hold lock)
    bool DoubleTable();

    // Hash a pointer to a 32-bit table key
    static CAT_INLINE u32 HashPtr(T *ptr)
    {
        u64 key = 0xBADdecafDEADbeef;

#if defined(CAT_WORD_64)
        key ^= *(u64*)&ptr;
#else
        key ^= *(u32*)&ptr;
#endif

        key = (~key) + (key << 18);
        key = key ^ (key >> 31);
        key = key * 21;
        key = key ^ (key >> 11);
        key = key + (key << 6);
        key = key ^ (key >> 22);
        return (u32)key;
    }

    // Common functions shared by interface for good code cache usage:

    // Unlink a table key
    void Unlink(u32 key);

    // Fill an iterator with the next set of data
    // Returns false if no data remains to fill
    void Fill(CollexionIterator<T> &iter, u32 first);

    // Find a hash table key based on data
    u32 Find(T *conn);

public:
    // Ctor zeros everything
    Collexion()
    {
        _first = 0;
        _used = 0;
        _allocated = 0;
        _table = 0;
        _table2 = 0;
    }

    // Dtor releases dangling memory
    ~Collexion();

    // Returns true if table is empty
    CAT_INLINE bool IsEmpty() { return _used == 0; }

    // Insert Connexion object, return false if already present or out of memory
    bool Insert(T *conn);

    // Remove Connexion object from list if it exists
    bool Remove(T *conn);

    // Begin iterating through list
    void Begin(CollexionIterator<T> &iter);

    // Iterate
    void Next(CollexionIterator<T> &iter, bool refill = true);
};



template<class T>
class CollexionIterator
{
    friend class Collexion<T>;

    static const u32 MAX_CACHE = 256;

    // Parent Collexion object
    Collexion<T> *_parent;

    // First and last hash table indices in parent
    u32 _first, _last;

    // Stores the size of the parent when snapshot was taken,
    // will invalidate _first and _last if table changed size
    u32 _prev_allocated;

    // Connexion object cache, to avoid locking and unlocking a lot
    T *_cache[MAX_CACHE];

    // Offset into cache and total elements in cache
    // Will grab another cache once offset reaches total
    u32 _offset, _total;

public:
    // Smart pointer -style accessors
    CAT_INLINE T *Get() throw() { return _cache[_offset]; }
    CAT_INLINE T *operator->() throw() { return _cache[_offset]; }
    CAT_INLINE T &operator*() throw() { return *_cache[_offset]; }
    CAT_INLINE operator T*() { return _cache[_offset]; }

public:
    // Ctor: Grabs first cache of Connexions
    CollexionIterator(Collexion<T> &begin);

    // Dtor: Calls Release()
    ~CollexionIterator();

    // Iterate to next Connexion object in list
    CollexionIterator &operator++();

    // Releases reference to any outstanding Connexions
    void Release();
};



template<class T>
bool Collexion<T>::DoubleTable()
{
    u32 new_allocated = _allocated << 1;
    if (new_allocated < MIN_ALLOCATED) new_allocated = MIN_ALLOCATED;

    // Allocate secondary table
    u32 new_bytes2 = sizeof(CollexionElement2) * new_allocated;
    CollexionElement2 *new_table2 = reinterpret_cast<CollexionElement2*>(
        RegionAllocator::ii->Acquire(new_bytes2) );

    if (!new_table2) return false;

    // Allocate primary table
    u32 new_bytes = sizeof(CollexionElement<T>) * new_allocated;
    CollexionElement<T> *new_table = reinterpret_cast<CollexionElement<T> *>(
        RegionAllocator::ii->Acquire(new_bytes) );

    if (!new_table)
    {
        RegionAllocator::ii->Release(new_table2);
        return false;
    }

    CAT_CLR(new_table, new_bytes);

    u32 new_first = 0;

    if (_table && _table2)
    {
        // For each entry in the old table,
        u32 ii = _first, mask = _allocated - 1;

        while (ii)
        {
            --ii;
            CollexionElement<T> *oe = &_table[ii];
            u32 hash = _table2[ii].hash;
            u32 key = hash & mask;

            // While collisions occur,
            while (new_table[key].conn)
            {
                // Mark collision
                new_table[key].next |= COLLIDE_MASK;

                // Walk collision list
                key = (key * COLLISION_MULTIPLIER + COLLISION_INCREMENTER) & mask;
            }

            // Fill new table element
            new_table[key].conn = oe->conn;
            new_table2[key].hash = hash;
            // new_table[key].refcnt is already zero

            // Link new element to new list
            if (new_first)
            {
                new_table[key].next |= new_first;
                new_table2[new_first - 1].last = key;
            }
            // new_table[key].next is already zero so no need to zero it here
            new_first = key + 1;

            // Get next old table entry
            ii = oe->next & NEXT_MASK;
        }

        // Zero head->last
        new_table2[new_first - 1].last = 0;
    }

    // Resulting linked list starting with _first-1 will extend until e->next == 0

    if (_table2) RegionAllocator::ii->Release(_table2);
    if (_table) RegionAllocator::ii->Release(_table);

    _table = new_table;
    _table2 = new_table2;
    _allocated = new_allocated;
    _first = new_first;
    return true;
}

template<class T>
Collexion<T>::~Collexion()
{
    if (_table2)
    {
        RegionAllocator::ii->Release(_table2);
    }

    // If table doesn't exist, return
    if (!_table) return;

    // For each allocated table entry,
    for (u32 ii = 0; ii < _allocated; ++ii)
    {
        // Get Connexion object
        T *conn = _table[ii].conn;

        // If object is valid, release it
        if (conn) conn->ReleaseRef();
    }

    // Release table memory
    RegionAllocator::ii->Release(_table);
}

template<class T>
bool Collexion<T>::Insert(T *conn)
{
    u32 hash = HashPtr(conn);
    conn->AddRef();

    AutoMutex lock(_lock);

    // If more than half of the table will be used,
    if (_used >= (_allocated >> 1))
    {
        // Double the size of the table (O(1) allocation pattern)
        // Growing pains are softened by careful design
        if (!DoubleTable())
        {
            // On growth failure, return false
            lock.Release();

            conn->ReleaseRef();

            return false;
        }
    }

    // Mask off high bits to make table key from hash
    u32 mask = _allocated - 1;
    u32 key = hash & mask;

    // While empty table entry not found,
    while (_table[key].conn)
    {
        // If Connexion object is already in the table,
        if (_table[key].conn == conn)
        {
            // Return false on duplicate
            lock.Release();

            conn->ReleaseRef();

            return false;
        }

        // Mark as a collision
        _table[key].next |= COLLIDE_MASK;

        // Walk collision list
        key = (key * COLLISION_MULTIPLIER + COLLISION_INCREMENTER) & mask;
    }

    // Fill new element
    _table[key].conn = conn;
    _table[key].refcnt = 0;
    _table2[key].hash = hash;
    _table2[key].last = 0;

    // Link new element to front of list
    if (_first) _table2[_first - 1].last = key + 1;
    _table[key].next = (_table[key].next & COLLIDE_MASK) | _first;
    _first = key + 1;

    ++_used;
    return true;
}

template<class T>
void Collexion<T>::Unlink(u32 key)
{
    // Clear reference
    _table[key].conn = 0;

    // Unlink from active list
    u32 next = _table[key].next & NEXT_MASK;
    u32 last = _table2[key].last;

    if (last) _table[last-1].next = (_table[last-1].next & ~NEXT_MASK) | next;
    else _first = next;
    if (next) _table2[next-1].last = last;

    // If this key was a leaf on a collision wind,
    if (!(_table[key].next & COLLIDE_MASK))
    {
        u32 mask = _allocated - 1;

        do
        {
            // Go backwards through the collision list one step
            key = ((key + COLLISION_INCRINVERSE) * COLLISION_MULTINVERSE) & mask;

            // Stop where collision list stops
            if (!(_table[key].next & COLLIDE_MASK))
                break;

            // Turn off collision key for previous entry
            _table[key].next &= ~COLLIDE_MASK;

        } while (!_table[key].conn);
    }

    // Update number of used elements
    --_used;
}

template<class T>
bool Collexion<T>::Remove(T *conn)
{
    u32 hash = HashPtr(conn);

    AutoMutex lock(_lock);

    // If table doesn't exist,
    if (!_allocated) return false;

    // Mask off high bits to make table key from hash
    u32 mask = _allocated - 1;
    u32 key = hash & mask;

    // While target table entry not found,
    for (;;)
    {
        // If target was found,
        if (_table[key].conn == conn)
        {
            if (_table[key].refcnt)
            {
                // Mark it killed so iterator can clean it up when it's finished
                _table[key].next |= KILL_MASK;
            }
            else
            {
                Unlink(key);

                lock.Release();

                conn->ReleaseRef();
            }

            // Return success
            return true;
        }

        if (!(_table[key].next & COLLIDE_MASK))
        {
            break; // End of collision list
        }

        // Walk collision list
        key = (key * COLLISION_MULTIPLIER + COLLISION_INCREMENTER) & mask;
    }

    // Return failure: not found
    return false;
}

template<class T>
void Collexion<T>::Fill(CollexionIterator<T> &iter, u32 first)
{
    u32 key = first;

    // Find first list element that does not want to die
    while (key && (_table[key-1].next & KILL_MASK))
    {
        // Go to next
        key = _table[key-1].next & NEXT_MASK;
    }

    iter._offset = 0;

    // If no elements in table,
    if (!key)
    {
        // Return empty set
        iter._cache[0] = 0;
        iter._total = 0;
        iter._first = 0;
        iter._last = 0;
        return;
    }

    // Remember size of hash table in case it grows before iterator is done
    iter._prev_allocated = _allocated;

    // Remember first key for next iteration
    iter._first = key;

    // For each of the first MAX_CACHE elements in the table, copy the data pointer to cache
    u32 ii = 0, final = 0;

    do
    {
        // If element does not want to die,
        if (!(_table[key-1].next & KILL_MASK))
        {
            // Copy data pointer
            iter._cache[ii] = _table[key-1].conn;

            // Increment reference count for element
            _table[key-1].refcnt++;

            // Remember key as the next iteration starting point
            final = key;

            // Check if copy is complete
            if (++ii >= CollexionIterator<T>::MAX_CACHE) break;
        }

        // Go to next key
        key = _table[key-1].next & NEXT_MASK;

    } while (key);

    // Record number of elements written
    iter._total = ii;

    // Remember next key for next iteration
    iter._last = final;
}

template<class T>
void Collexion<T>::Begin(CollexionIterator<T> &iter)
{
    iter._parent = this;

    AutoMutex lock(_lock);

    Fill(iter, _first);
}

// Find a hash table key based on data
template<class T>
u32 Collexion<T>::Find(T *conn)
{
    u32 mask = _allocated - 1;
    u32 key = HashPtr(conn) & mask;

    // Find the object in the collision list starting at the expected location
    while (_table[key].conn != conn)
    {
        // If at the end of the collision list,
        if (!(_table[key].next & COLLIDE_MASK))
            break; // Should never happen

        // Walk collision list
        key = (key * COLLISION_MULTIPLIER + COLLISION_INCREMENTER) & mask;
    }

    return key;
}

template<class T>
void Collexion<T>::Next(CollexionIterator<T> &iter, bool refill)
{
    T *release_list[CollexionIterator<T>::MAX_CACHE];
    u32 release_ii = 0;

    u32 key = iter._first;
    u32 last = iter._last;

    // If iteration is done,
    if (!key) return;

    AutoMutex lock(_lock);

    // If hash table changed size (rare),
    if (iter._prev_allocated != _allocated)
    {
        // iter._first and iter._last are invalid
        // ...but we can find them again based on the cached pointers!
        key = Find(iter._cache[0]) + 1;
        last = Find(iter._cache[iter._total - 1]) + 1;
    }

    last = _table[last-1].next & NEXT_MASK;

    // Release any table elements that want to die now
    do 
    {
        u32 flags = _table[key-1].next;

        // If reference count is now zero for this element,
        if (0 == --_table[key-1].refcnt)
        {
            // If element wants to die,
            if (flags & KILL_MASK)
            {
                // Prepare to release data after lock is released
                release_list[release_ii++] = _table[key-1].conn;

                Unlink(key-1);
            }
        }

        key = flags & NEXT_MASK;

    } while (key != last);

    // Fill iterator starting with next key
    if (refill) Fill(iter, key);

    lock.Release();

    if (!refill)
    {
        // Return empty set
        iter._cache[0] = 0;
        iter._total = 0;
        iter._offset = 0;
        iter._first = 0;
        iter._last = 0;
    }

    // Release data awaiting destruction
    for (u32 ii = 0; ii < release_ii; ++ii)
    {
        release_list[ii]->ReleaseRef();
    }
}



template<class T>
CollexionIterator<T>::CollexionIterator(Collexion<T> &begin)
{
    begin.Begin(*this);
}

template<class T>
CollexionIterator<T>::~CollexionIterator()
{
    Release();
}

template<class T>
CollexionIterator<T> &CollexionIterator<T>::operator++()
{
    if (++_offset >= _total)
    {
        _parent->Next(*this, true);
    }

    return *this;
}

template<class T>
void CollexionIterator<T>::Release()
{
    if (_parent)
    {
        _parent->Next(*this, false);
        _parent = 0;
    }
}


} // namespace sphynx


} // namespace cat

#endif // CAT_SPHYNX_COLLEXION_HPP