include/libtfo/tfo.hh

Go to the documentation of this file.

#ifndef __TFO_HH__
#define __TFO_HH__

#include <libtfo/fibentry.hh>

#include <stdint.h>
#include <set>
#include <list>
#include <ext/hash_map>

using namespace std;
using namespace __gnu_cxx;

enum FibEntryUpdateType
{
    FIB_ENTRY_ADD,
    FIB_ENTRY_REMOVE,
    FIB_ENTRY_MODIFY
};

template <typename O,
         typename M, typename A, typename U,
         typename MHashFcn = hash<const M*>,
         typename MEqualFcn = equal_to<const M*>,
         typename AEqualFcn = equal_to<const A>
         >
class TFO
{
    public:
        typedef O owner_type;
        typedef M match_type;
        typedef A action_type;
        typedef U user_type;
        typedef void (*fib_modify_func) (O owner, FibEntry<M, A, U>* e);
        typedef void (*walk_const_callback_func) (O owner, const FibEntry<M, A, U>* e, void* user_data);
        typedef void (*walk_callback_func) (O owner, FibEntry<M, A, U>* e, void* user_data);

        inline TFO (O owner,
                         const uint32_t fib_capacity, const fib_modify_func fib_modify,
                         const uint32_t size_b2, const uint32_t size_b3)
            : _owner(owner),
            _fib_capacity(fib_capacity), _fib_modify(fib_modify),
            _size_b2(size_b2), _size_b3(size_b3)
        {
        }

        inline ~TFO (void)
        {
            for (typename _fib_hash_type::iterator i = _fib_entries.begin();
                 i != _fib_entries.end();
                )
            {
                FibEntry<M, A, U>* e = i->second;
                typename _fib_hash_type::iterator i_next = i;
                i_next++;
                _fib_entries.erase(i);
                i = i_next;
                delete e;
            }
        }

        inline int update_entry (const M& m, const A& a, const enum FibEntryUpdateType type)
        {
            typename _fib_hash_type::iterator i = _fib_entries.find(&m);

            switch (type)
            {
            case FIB_ENTRY_ADD:
            case FIB_ENTRY_MODIFY:
                {
                    // Check if entry is already there.
                    if (i != _fib_entries.end())
                    {
                        FibEntry<M, A, U>* e = i->second;

                        if (e->state() == FIB_ENTRY_STATE_INACTIVE)
                        {
                            // Entry is inactive, activate it.
                            e->action(a); // Update action, it might have changed.
                            e->old_action(a); // Also update old_action.
                            e->table(FIB_ENTRY_TABLE_SLOW);
                            _do_fib_modify(e, FIB_ENTRY_STATE_MOD_ADD);
                        }
                        else if (!_action_equal(e->action(), a))
                        {
                            // Action is different, modify it.
                            e->action(a);
                            _do_fib_modify(e, FIB_ENTRY_STATE_MOD_ACTION);
                        }

                        return 0; // Existing entry modified, or similar existing active entry found.
                    }

                    // Insert new entry.
                    FibEntry<M, A, U>* e = new FibEntry<M, A, U>(_size_b2, _size_b3, m, a);
                    _fib_entries[&e->match()] = e;

                    // New entries initially go into slow path.
                    e->table(FIB_ENTRY_TABLE_SLOW);
                    _do_fib_modify(e, FIB_ENTRY_STATE_MOD_ADD);
                    return 0; // New entry installed.
                }
                break;
            case FIB_ENTRY_REMOVE:
                {
                    if (i == _fib_entries.end())
                        return -1; // Entry not found.

                    FibEntry<M, A, U>* e = i->second;
                    if (!_action_equal(e->action(), a))
                        return 0; // Entry actions differ, we assume ours is more recent.

                    _do_fib_modify(e, FIB_ENTRY_STATE_MOD_REMOVE);
                    return 0; // Entry deactivated.
                }
                break;
            }

            return -1; // Should never reach here.
        }

        inline FibEntry<M, A, U>* get_entry (const M& m)
        {
            typename _fib_hash_type::iterator i = _fib_entries.find(&m);
            return i == _fib_entries.end() ? NULL : i->second;
        }

        inline int update_hits (const M& m, const uint64_t& hits, const enum FibEntryHitsUpdateType type = FIB_ENTRY_HITS_ADD)
        {
            typename _fib_hash_type::iterator i = _fib_entries.find(&m);
            if (i == _fib_entries.end())
                return -1;

            i->second->update_hits(hits, type);

            return 0;
        }

        void bin_complete (void)
        {
            _fib_multiset_b1_type b1_set;
            _fib_multiset_b2_type b2_set;
            _fib_multiset_b3_type b3_set;

            for (typename _fib_hash_type::iterator i = _fib_entries.begin();
                 i != _fib_entries.end();
                )
            {
                FibEntry<M, A, U>* e = i->second;

                // Compute final b1, b2, b3 counters by calling bin_complete for all entries.
                e->bin_complete();

                if (e->state() == FIB_ENTRY_STATE_INACTIVE)
                {
                    typename _fib_hash_type::iterator i_next = i;
                    i_next++;

                    // This entry is inactive. Decrement TTL and remove if necessary.
                    if (e->ttl_decrement() == 0)
                    {
                        _fib_entries.erase(i);
                        delete e;
                    }

                    i = i_next;
                    continue;
                }

                // Create sorted sets of entries by b1, b2, b3 counters
                b1_set.insert(e);
                b2_set.insert(e);
                b3_set.insert(e);

                ++i;
            }

            // Apply selection strategy.
            _fib_set_type top_n;
            typename _fib_multiset_b1_type::reverse_iterator i_b1 = b1_set.rbegin();
            typename _fib_multiset_b2_type::reverse_iterator i_b2 = b2_set.rbegin();
            typename _fib_multiset_b3_type::reverse_iterator i_b3 = b3_set.rbegin();

            // Round-robin select popular entries (1).
            for (uint32_t i = 0, all_in = 0;
                 top_n.size() < _fib_capacity && all_in != 0x7;
                 ++i)
            {
                switch (i % 3)
                {
                case 0:
                    if (i_b1 != b1_set.rend())
                        top_n.insert(*i_b1++);
                    else
                        all_in |= 1 << 0;
                    break;
                case 1:
                    if (i_b2 != b2_set.rend())
                        top_n.insert(*i_b2++);
                    else
                        all_in |= 1 << 1;
                    break;
                case 2:
                    if (i_b3 != b3_set.rend())
                        top_n.insert(*i_b3++);
                    else
                        all_in |= 1 << 2;
                    break;
                }
            }

            // Compute difference (2), sorted by popularity (3).
            _fib_multiset_b1_type top_n_adds;
            _fib_multiset_b1_type top_n_rems;
            for (typename _fib_hash_type::iterator i = _fib_entries.begin();
                 i != _fib_entries.end();
                 ++i)
            {
                FibEntry<M, A, U>* e = i->second;
                if (e->state() == FIB_ENTRY_STATE_INACTIVE)
                    continue;

                if (top_n.find(e) != top_n.end())
                {
                    if (e->table() == FIB_ENTRY_TABLE_SLOW)
                    {
                        top_n_adds.insert(e);
                    }
                }
                else
                {
                    if (e->table() == FIB_ENTRY_TABLE_FAST)
                    {
                        top_n_rems.insert(e);
                    }
                }
            }

            // Select high-value FIB cache changes (4).
            list<FibEntry<M, A, U>* > top_n_mods;
            typename _fib_multiset_b1_type::reverse_iterator i_adds = top_n_adds.rbegin();
            typename _fib_multiset_b1_type::iterator i_rems = top_n_rems.begin();

            // If there are more additions than removals, select those extra additions starting
            // at the most promising ones.
            for (int i = top_n_adds.size() - top_n_rems.size(); i > 0; --i)
            {
                FibEntry<M, A, U>* e = *i_adds++;
                e->table(FIB_ENTRY_TABLE_FAST);
                top_n_mods.push_front(e);
            }

            // If there are more removals than additions, select those extra removals starting
            // at the least promising ones.
            for (int i = top_n_rems.size() - top_n_adds.size(); i > 0; --i)
            {
                FibEntry<M, A, U>* e = *i_rems++;
                e->table(FIB_ENTRY_TABLE_SLOW);
                top_n_mods.push_back(e);
            }

            // Finally select all significant changes.
            while (i_adds != top_n_adds.rend() &&
                   i_rems != top_n_rems.end())
            {
                FibEntry<M, A, U>* e_add = *i_adds++;
                FibEntry<M, A, U>* e_rem = *i_rems++;

                if (e_add->hits_b1() > (e_rem->hits_b1() * 2))
                {
                    e_add->table(FIB_ENTRY_TABLE_FAST);
                    top_n_mods.push_front(e_add);

                    e_rem->table(FIB_ENTRY_TABLE_SLOW);
                    top_n_mods.push_back(e_rem);
                }
                else
                    break;
            }

            // Apply modifications: alternate between removing from fast path and adding to fast path.
            for (bool front = false; top_n_mods.size(); front = !front)
            {
                FibEntry<M, A, U>* e;

                if (front)
                { e = top_n_mods.front(); top_n_mods.pop_front(); }
                else
                { e = top_n_mods.back(); top_n_mods.pop_back(); }

                _do_fib_modify(e, FIB_ENTRY_STATE_MOD_MOVE);
            }
        }

        void walk_entries (walk_const_callback_func f, void* user_data = NULL)
        {
            for (typename _fib_hash_type::const_iterator i = _fib_entries.begin();
                 i != _fib_entries.end();
                 ++i)
            {
                f(_owner, i->second, user_data);
            }
        }

        void walk_entries (walk_callback_func f, void* user_data = NULL)
        {
            for (typename _fib_hash_type::iterator i = _fib_entries.begin();
                 i != _fib_entries.end();
                 ++i)
            {
                f(_owner, i->second, user_data);
            }
        }

    private:
        O _owner;

        uint32_t _fib_capacity;
        fib_modify_func _fib_modify;

        uint32_t _size_b2;
        uint32_t _size_b3;

        AEqualFcn _action_equal;

        typedef hash_map<const M*, FibEntry<M, A, U>*, MHashFcn, MEqualFcn> _fib_hash_type;
        _fib_hash_type _fib_entries;

        typedef set<FibEntry<M, A, U>*> _fib_set_type;

        struct _fib_entry_b1_lt
        {
            bool operator() (FibEntry<M, A, U>* a, FibEntry<M, A, U>* b)
            { return a->hits_b1() < b->hits_b1(); }
        };
        typedef multiset<FibEntry<M, A, U>*, _fib_entry_b1_lt> _fib_multiset_b1_type;

        struct _fib_entry_b2_lt
        {
            bool operator() (FibEntry<M, A, U>* a, FibEntry<M, A, U>* b)
            { return a->hits_b2() < b->hits_b2(); }
        };
        typedef multiset<FibEntry<M, A, U>*, _fib_entry_b2_lt> _fib_multiset_b2_type;

        struct _fib_entry_b3_lt
        {
            bool operator() (FibEntry<M, A, U>* a, FibEntry<M, A, U>* b)
            { return a->hits_b3() < b->hits_b3(); }
        };
        typedef multiset<FibEntry<M, A, U>*, _fib_entry_b3_lt> _fib_multiset_b3_type;
        inline void _do_fib_modify (FibEntry<M, A, U>* e, enum FibEntryState s)
        {
            e->state(s);
            _fib_modify(_owner, e);

            switch (s)
            {
            case FIB_ENTRY_STATE_MOD_ADD:
                e->ttl(0);
                e->state(FIB_ENTRY_STATE_ACTIVE);
                break;
            case FIB_ENTRY_STATE_MOD_MOVE:
                e->state(FIB_ENTRY_STATE_ACTIVE);
                break;
            case FIB_ENTRY_STATE_MOD_ACTION:
                e->old_action(e->action());
                e->state(FIB_ENTRY_STATE_ACTIVE);
                break;
            case FIB_ENTRY_STATE_MOD_REMOVE:
                e->ttl(_size_b3);
                e->state(FIB_ENTRY_STATE_INACTIVE);
                break;
            default:
                break;
            }
        }
};

#endif