This patch introduces a ARPTableBase template element. The old ARPTable is then defined as:
class ARPTable : public ARPTableBase<IPAddress> Where IPAddress is the network level id that must be mapped to and EtherAddress (not part of the template). If a specific use case is provided I could further generalize the template adding a second argument for the l2 address to be mapped to l3 address. Signed-off-by: Roberto Riggio<[email protected]> -- diff -urN '--exclude=.git' click.upstream/elements/ethernet/arptable.cc click/elements/ethernet/arptable.cc --- click.upstream/elements/ethernet/arptable.cc 2011-02-24 09:15:16.755988001 +0100 +++ click/elements/ethernet/arptable.cc 2011-02-04 11:22:26.422339000 +0100 @@ -1,5 +1,5 @@ /* - * arptable.{cc,hh} -- ARP resolver element + * arptablebase.{cc,hh} -- ARP resolver element * Eddie Kohler * * Copyright (c) 1999-2000 Massachusetts Institute of Technology @@ -18,10 +18,8 @@ */ #include<click/config.h> -#include "arpquerier.hh" -#include<clicknet/ether.h> +#include "arptable.hh" #include<click/etheraddress.hh> -#include<click/ipaddress.hh> #include<click/confparse.hh> #include<click/bitvector.hh> #include<click/straccum.hh> @@ -31,319 +29,13 @@ CLICK_DECLS ARPTable::ARPTable() - : _entry_capacity(0), _packet_capacity(2048), _expire_timer(this) { - _entry_count = _packet_count = _drops = 0; } ARPTable::~ARPTable() { } -int -ARPTable::configure(Vector<String> &conf, ErrorHandler *errh) -{ - Timestamp timeout(300); - if (cp_va_kparse(conf, this, errh, - "CAPACITY", 0, cpUnsigned,&_packet_capacity, - "ENTRY_CAPACITY", 0, cpUnsigned,&_entry_capacity, - "TIMEOUT", 0, cpTimestamp,&timeout, - cpEnd)< 0) - return -1; - set_timeout(timeout); - if (_timeout_j) { - _expire_timer.initialize(this); - _expire_timer.schedule_after_sec(_timeout_j / CLICK_HZ); - } - return 0; -} - -void -ARPTable::cleanup(CleanupStage) -{ - clear(); -} - -void -ARPTable::clear() -{ - // Walk the arp cache table and free any stored packets and arp entries. - for (Table::iterator it = _table.begin(); it; ) { - ARPEntry *ae = _table.erase(it); - while (Packet *p = ae->_head) { - ae->_head = p->next(); - p->kill(); - ++_drops; - } - _alloc.deallocate(ae); - } - _entry_count = _packet_count = 0; - _age.__clear(); -} - -void -ARPTable::take_state(Element *e, ErrorHandler *errh) -{ - ARPTable *arpt = (ARPTable *)e->cast("ARPTable"); - if (!arpt) - return; - if (_table.size()> 0) { - errh->error("late take_state"); - return; - } - - _table.swap(arpt->_table); - _age.swap(arpt->_age); - _entry_count = arpt->_entry_count; - _packet_count = arpt->_packet_count; - _drops = arpt->_drops; - _alloc.swap(arpt->_alloc); - - arpt->_entry_count = 0; - arpt->_packet_count = 0; -} - -void -ARPTable::slim(click_jiffies_t now) -{ - ARPEntry *ae; - - // Delete old entries. - while ((ae = _age.front()) - && (ae->expired(now, _timeout_j) - || (_entry_capacity&& _entry_count> _entry_capacity))) { - _table.erase(ae->_ip); - _age.pop_front(); - - while (Packet *p = ae->_head) { - ae->_head = p->next(); - p->kill(); - --_packet_count; - ++_drops; - } - - _alloc.deallocate(ae); - --_entry_count; - } - - // Mark entries for polling, and delete packets to make space. - while (_packet_capacity&& _packet_count> _packet_capacity) { - while (ae->_head&& _packet_count> _packet_capacity) { - Packet *p = ae->_head; - if (!(ae->_head = p->next())) - ae->_tail = 0; - p->kill(); - --_packet_count; - ++_drops; - } - ae = ae->_age_link.next(); - } -} - -void -ARPTable::run_timer(Timer *timer) -{ - // Expire any old entries, and make sure there's room for at least one - // packet. - _lock.acquire_write(); - slim(click_jiffies()); - _lock.release_write(); - if (_timeout_j) - timer->schedule_after_sec(_timeout_j / CLICK_HZ + 1); -} - -ARPTable::ARPEntry * -ARPTable::ensure(IPAddress ip, click_jiffies_t now) -{ - _lock.acquire_write(); - Table::iterator it = _table.find(ip); - if (!it) { - void *x = _alloc.allocate(); - if (!x) { - _lock.release_write(); - return 0; - } - - ++_entry_count; - if (_entry_capacity&& _entry_count> _entry_capacity) - slim(now); - - ARPEntry *ae = new(x) ARPEntry(ip); - ae->_live_at_j = now; - ae->_polled_at_j = ae->_live_at_j - CLICK_HZ; - _table.set(it, ae); - - _age.push_back(ae); - } - return it.get(); -} - -int -ARPTable::insert(IPAddress ip, const EtherAddressð, Packet **head) -{ - click_jiffies_t now = click_jiffies(); - ARPEntry *ae = ensure(ip, now); - if (!ae) - return -ENOMEM; - - ae->_eth = eth; - ae->_known = !eth.is_broadcast(); - - ae->_live_at_j = now; - ae->_polled_at_j = ae->_live_at_j - CLICK_HZ; - - if (ae->_age_link.next()) { - _age.erase(ae); - _age.push_back(ae); - } - - if (head) { - *head = ae->_head; - ae->_head = ae->_tail = 0; - for (Packet *p = *head; p; p = p->next()) - --_packet_count; - } - - _table.balance(); - _lock.release_write(); - return 0; -} - -int -ARPTable::append_query(IPAddress ip, Packet *p) -{ - click_jiffies_t now = click_jiffies(); - ARPEntry *ae = ensure(ip, now); - if (!ae) - return -ENOMEM; - - if (ae->known(now, _timeout_j)) { - _lock.release_write(); - return -EAGAIN; - } - - // Since we're still trying to send to this address, keep the entry just - // this side of expiring. This fixes a bug reported 5 Nov 2009 by Seiichi - // Tetsukawa, and verified via testie, where the slim() below could delete - // the "ae" ARPEntry when "ae" was the oldest entry in the system. - if (_timeout_j) { - click_jiffies_t live_at_j_min = now - _timeout_j; - if (click_jiffies_less(ae->_live_at_j, live_at_j_min)) { - ae->_live_at_j = live_at_j_min; - // Now move "ae" to the right position in the list by walking - // forward over other elements (potentially expensive?). - ARPEntry *ae_next = ae->_age_link.next(), *next = ae_next; - while (next&& click_jiffies_less(next->_live_at_j, ae->_live_at_j)) - next = next->_age_link.next(); - if (ae_next != next) { - _age.erase(ae); - _age.insert(next /* might be null */, ae); - } - } - } - - ++_packet_count; - if (_packet_capacity&& _packet_count> _packet_capacity) - slim(now); - - if (ae->_tail) - ae->_tail->set_next(p); - else - ae->_head = p; - ae->_tail = p; - p->set_next(0); - - int r; - if (!click_jiffies_less(now, ae->_polled_at_j + CLICK_HZ / 10)) { - ae->_polled_at_j = now; - r = 1; - } else - r = 0; - - _table.balance(); - _lock.release_write(); - return r; -} - -IPAddress -ARPTable::reverse_lookup(const EtherAddressð) -{ - _lock.acquire_read(); - - IPAddress ip; - for (Table::iterator it = _table.begin(); it; ++it) - if (it->_eth == eth) { - ip = it->_ip; - break; - } - - _lock.release_read(); - return ip; -} - -String -ARPTable::read_handler(Element *e, void *user_data) -{ - ARPTable *arpt = (ARPTable *) e; - StringAccum sa; - click_jiffies_t now = click_jiffies(); - switch (reinterpret_cast<uintptr_t>(user_data)) { - case h_table: - for (ARPEntry *ae = arpt->_age.front(); ae; ae = ae->_age_link.next()) { - int ok = ae->known(now, arpt->_timeout_j); - sa<< ae->_ip<< ' '<< ok<< ' '<< ae->_eth<< '' - << Timestamp::make_jiffies(now - ae->_live_at_j)<< '\n'; - } - break; - } - return sa.take_string(); -} - -int -ARPTable::write_handler(const String&str, Element *e, void *user_data, ErrorHandler *errh) -{ - ARPTable *arpt = (ARPTable *) e; - switch (reinterpret_cast<uintptr_t>(user_data)) { - case h_insert: { - IPAddress ip; - EtherAddress eth; - if (cp_va_space_kparse(str, arpt, errh, - "IP", cpkP+cpkM, cpIPAddress,&ip, - "ETH", cpkP+cpkM, cpEtherAddress,ð, - cpEnd)< 0) - return -1; - arpt->insert(ip, eth); - return 0; - } - case h_delete: { - IPAddress ip; - if (cp_va_space_kparse(str, arpt, errh, - "IP", cpkP+cpkM, cpIPAddress,&ip, - cpEnd)< 0) - return -1; - arpt->insert(ip, EtherAddress::make_broadcast()); // XXX? - return 0; - } - case h_clear: - arpt->clear(); - return 0; - default: - return -1; - } -} - -void -ARPTable::add_handlers() -{ - add_read_handler("table", read_handler, h_table); - add_data_handlers("drops", Handler::OP_READ,&_drops); - add_data_handlers("count", Handler::OP_READ,&_entry_count); - add_data_handlers("length", Handler::OP_READ,&_packet_count); - add_write_handler("insert", write_handler, h_insert); - add_write_handler("delete", write_handler, h_delete); - add_write_handler("clear", write_handler, h_clear); -} - CLICK_ENDDECLS EXPORT_ELEMENT(ARPTable) ELEMENT_MT_SAFE(ARPTable) diff -urN '--exclude=.git' click.upstream/elements/ethernet/arptable.hh click/elements/ethernet/arptable.hh --- click.upstream/elements/ethernet/arptable.hh 2011-02-24 09:15:16.755988001 +0100 +++ click/elements/ethernet/arptable.hh 2011-02-04 11:22:26.422339000 +0100 @@ -7,6 +7,13 @@ #include<click/sync.hh> #include<click/timer.hh> #include<click/list.hh> +#include<click/config.h> +#include<click/confparse.hh> +#include<click/bitvector.hh> +#include<click/straccum.hh> +#include<click/router.hh> +#include<click/error.hh> +#include<click/glue.hh> CLICK_DECLS /* @@ -81,12 +88,13 @@ ARPQuerier */ -class ARPTable : public Element { public: +template<typename T> +class ARPTableBase : public Element { public: - ARPTable(); - ~ARPTable(); + ARPTableBase(); + ~ARPTableBase(); - const char *class_name() const { return "ARPTable"; } + const char *class_name() const { return "ARPTableBase"; } int configure(Vector<String> &, ErrorHandler *); bool can_live_reconfigure() const { return true; } @@ -94,11 +102,11 @@ void add_handlers(); void cleanup(CleanupStage); - int lookup(IPAddress ip, EtherAddress *eth, uint32_t poll_timeout_j); - EtherAddress lookup(IPAddress ip); - IPAddress reverse_lookup(const EtherAddressð); - int insert(IPAddress ip, const EtherAddress&en, Packet **head = 0); - int append_query(IPAddress ip, Packet *p); + int lookup(T ip, EtherAddress *eth, uint32_t poll_timeout_j); + EtherAddress lookup(T ip); + T reverse_lookup(const EtherAddressð); + int insert(T ip, const EtherAddress&en, Packet **head = 0); + int append_query(T ip, Packet *p); void clear(); uint32_t capacity() const { @@ -142,7 +150,7 @@ static int write_handler(const String&str, Element *e, void *user_data, ErrorHandler *errh); struct ARPEntry { // This structure is now larger than I'd like - IPAddress _ip; // (40B) but probably still fine. + T _ip; // (40B) but probably still fine. ARPEntry *_hashnext; EtherAddress _eth; bool _known; @@ -151,8 +159,8 @@ Packet *_head; Packet *_tail; List_member<ARPEntry> _age_link; - typedef IPAddress key_type; - typedef IPAddress key_const_reference; + typedef T key_type; + typedef T key_const_reference; key_const_reference hashkey() const { return _ip; } @@ -163,17 +171,19 @@ bool known(click_jiffies_t now, uint32_t timeout_j) const { return _known&& !expired(now, timeout_j); } - ARPEntry(IPAddress ip) + ARPEntry(T ip) : _ip(ip), _hashnext(), _eth(EtherAddress::make_broadcast()), _known(false), _head(), _tail() { } }; - private: + protected: ReadWriteLock _lock; typedef HashContainer<ARPEntry> Table; + typedef typename Table::iterator TIter; + Table _table; typedef List<ARPEntry,&ARPEntry::_age_link> AgeList; AgeList _age; @@ -186,17 +196,18 @@ SizedHashAllocator<sizeof(ARPEntry)> _alloc; Timer _expire_timer; - ARPEntry *ensure(IPAddress ip, click_jiffies_t now); + ARPEntry *ensure(T ip, click_jiffies_t now); void slim(click_jiffies_t now); }; -inline int -ARPTable::lookup(IPAddress ip, EtherAddress *eth, uint32_t poll_timeout_j) +template<typename T> +inline int +ARPTableBase<T>::lookup(T ip, EtherAddress *eth, uint32_t poll_timeout_j) { _lock.acquire_read(); int r = -1; - if (Table::iterator it = _table.find(ip)) { + if (TIter it = _table.find(ip)) { click_jiffies_t now = click_jiffies(); if (it->known(now, _timeout_j)) { *eth = it->_eth; @@ -213,8 +224,9 @@ return r; } +template<typename T> inline EtherAddress -ARPTable::lookup(IPAddress ip) +ARPTableBase<T>::lookup(T ip) { EtherAddress eth; if (lookup(ip,ð, 0)>= 0) @@ -223,5 +235,343 @@ return EtherAddress::make_broadcast(); } +template<typename T> +ARPTableBase<T>::ARPTableBase() + : _entry_capacity(0), _packet_capacity(2048), _expire_timer(this) +{ + _entry_count = _packet_count = _drops = 0; +} + +template<typename T> +ARPTableBase<T>::~ARPTableBase() +{ +} + +template<typename T> +int +ARPTableBase<T>::configure(Vector<String> &conf, ErrorHandler *errh) +{ + Timestamp timeout(300); + if (cp_va_kparse(conf, this, errh, + "CAPACITY", 0, cpUnsigned,&_packet_capacity, + "ENTRY_CAPACITY", 0, cpUnsigned,&_entry_capacity, + "TIMEOUT", 0, cpTimestamp,&timeout, + cpEnd)< 0) + return -1; + set_timeout(timeout); + if (_timeout_j) { + _expire_timer.initialize(this); + _expire_timer.schedule_after_sec(_timeout_j / CLICK_HZ); + } + return 0; +} + +template<typename T> +void +ARPTableBase<T>::cleanup(CleanupStage) +{ + clear(); +} + +template<typename T> +void +ARPTableBase<T>::clear() +{ + // Walk the arp cache table and free any stored packets and arp entries. + for (TIter it = _table.begin(); it; ) { + ARPEntry *ae = _table.erase(it); + while (Packet *p = ae->_head) { + ae->_head = p->next(); + p->kill(); + ++_drops; + } + _alloc.deallocate(ae); + } + _entry_count = _packet_count = 0; + _age.__clear(); +} + +template<typename T> +void +ARPTableBase<T>::take_state(Element *e, ErrorHandler *errh) +{ + ARPTableBase<T> *arpt = (ARPTableBase<T> *)e->cast("ARPTableBase"); + if (!arpt) + return; + if (_table.size()> 0) { + errh->error("late take_state"); + return; + } + + _table.swap(arpt->_table); + _age.swap(arpt->_age); + _entry_count = arpt->_entry_count; + _packet_count = arpt->_packet_count; + _drops = arpt->_drops; + _alloc.swap(arpt->_alloc); + + arpt->_entry_count = 0; + arpt->_packet_count = 0; +} + +template<typename T> +void +ARPTableBase<T>::slim(click_jiffies_t now) +{ + ARPEntry *ae; + + // Delete old entries. + while ((ae = _age.front()) + && (ae->expired(now, _timeout_j) + || (_entry_capacity&& _entry_count> _entry_capacity))) { + _table.erase(ae->_ip); + _age.pop_front(); + + while (Packet *p = ae->_head) { + ae->_head = p->next(); + p->kill(); + --_packet_count; + ++_drops; + } + + _alloc.deallocate(ae); + --_entry_count; + } + + // Mark entries for polling, and delete packets to make space. + while (_packet_capacity&& _packet_count> _packet_capacity) { + while (ae->_head&& _packet_count> _packet_capacity) { + Packet *p = ae->_head; + if (!(ae->_head = p->next())) + ae->_tail = 0; + p->kill(); + --_packet_count; + ++_drops; + } + ae = ae->_age_link.next(); + } +} + +template<typename T> +void +ARPTableBase<T>::run_timer(Timer *timer) +{ + // Expire any old entries, and make sure there's room for at least one + // packet. + _lock.acquire_write(); + slim(click_jiffies()); + _lock.release_write(); + if (_timeout_j) + timer->schedule_after_sec(_timeout_j / CLICK_HZ + 1); +} + +template<typename T> +typename ARPTableBase<T>::ARPEntry* +ARPTableBase<T>::ensure(T ip, click_jiffies_t now) +{ + _lock.acquire_write(); + TIter it = _table.find(ip); + if (!it) { + void *x = _alloc.allocate(); + if (!x) { + _lock.release_write(); + return 0; + } + + ++_entry_count; + if (_entry_capacity&& _entry_count> _entry_capacity) + slim(now); + + ARPEntry *ae = new(x) ARPEntry(ip); + ae->_live_at_j = now; + ae->_polled_at_j = ae->_live_at_j - CLICK_HZ; + _table.set(it, ae); + + _age.push_back(ae); + } + return it.get(); +} + +template<typename T> +int +ARPTableBase<T>::insert(T ip, const EtherAddressð, Packet **head) +{ + click_jiffies_t now = click_jiffies(); + ARPEntry *ae = ensure(ip, now); + if (!ae) + return -ENOMEM; + + ae->_eth = eth; + ae->_known = !eth.is_broadcast(); + + ae->_live_at_j = now; + ae->_polled_at_j = ae->_live_at_j - CLICK_HZ; + + if (ae->_age_link.next()) { + _age.erase(ae); + _age.push_back(ae); + } + + if (head) { + *head = ae->_head; + ae->_head = ae->_tail = 0; + for (Packet *p = *head; p; p = p->next()) + --_packet_count; + } + + _table.balance(); + _lock.release_write(); + return 0; +} + +template<typename T> +int +ARPTableBase<T>::append_query(T ip, Packet *p) +{ + click_jiffies_t now = click_jiffies(); + ARPEntry *ae = ensure(ip, now); + if (!ae) + return -ENOMEM; + + if (ae->known(now, _timeout_j)) { + _lock.release_write(); + return -EAGAIN; + } + + // Since we're still trying to send to this address, keep the entry just + // this side of expiring. This fixes a bug reported 5 Nov 2009 by Seiichi + // Tetsukawa, and verified via testie, where the slim() below could delete + // the "ae" ARPEntry when "ae" was the oldest entry in the system. + if (_timeout_j) { + click_jiffies_t live_at_j_min = now - _timeout_j; + if (click_jiffies_less(ae->_live_at_j, live_at_j_min)) { + ae->_live_at_j = live_at_j_min; + // Now move "ae" to the right position in the list by walking + // forward over other elements (potentially expensive?). + ARPEntry *ae_next = ae->_age_link.next(), *next = ae_next; + while (next&& click_jiffies_less(next->_live_at_j, ae->_live_at_j)) + next = next->_age_link.next(); + if (ae_next != next) { + _age.erase(ae); + _age.insert(next /* might be null */, ae); + } + } + } + + ++_packet_count; + if (_packet_capacity&& _packet_count> _packet_capacity) + slim(now); + + if (ae->_tail) + ae->_tail->set_next(p); + else + ae->_head = p; + ae->_tail = p; + p->set_next(0); + + int r; + if (!click_jiffies_less(now, ae->_polled_at_j + CLICK_HZ / 10)) { + ae->_polled_at_j = now; + r = 1; + } else + r = 0; + + _table.balance(); + _lock.release_write(); + return r; +} + +template<typename T> +T +ARPTableBase<T>::reverse_lookup(const EtherAddressð) +{ + _lock.acquire_read(); + + T ip; + for (TIter it = _table.begin(); it; ++it) + if (it->_eth == eth) { + ip = it->_ip; + break; + } + + _lock.release_read(); + return ip; +} + +template<typename T> +String +ARPTableBase<T>::read_handler(Element *e, void *user_data) +{ + ARPTableBase *arpt = (ARPTableBase *) e; + StringAccum sa; + click_jiffies_t now = click_jiffies(); + switch (reinterpret_cast<uintptr_t>(user_data)) { + case h_table: + for (ARPEntry *ae = arpt->_age.front(); ae; ae = ae->_age_link.next()) { + int ok = ae->known(now, arpt->_timeout_j); + sa<< ae->_ip<< ' '<< ok<< ' '<< ae->_eth<< '' + << Timestamp::make_jiffies(now - ae->_live_at_j)<< '\n'; + } + break; + } + return sa.take_string(); +} + +template<typename T> +int +ARPTableBase<T>::write_handler(const String&str, Element *e, void *user_data, ErrorHandler *errh) +{ + ARPTableBase<T> *arpt = (ARPTableBase<T> *) e; + switch (reinterpret_cast<uintptr_t>(user_data)) { + case h_insert: { + IPAddress ip; + EtherAddress eth; + if (cp_va_space_kparse(str, arpt, errh, + "IP", cpkP+cpkM, cpIPAddress,&ip, + "ETH", cpkP+cpkM, cpEtherAddress,ð, + cpEnd)< 0) + return -1; + arpt->insert(ip, eth); + return 0; + } + case h_delete: { + IPAddress ip; + if (cp_va_space_kparse(str, arpt, errh, + "IP", cpkP+cpkM, cpIPAddress,&ip, + cpEnd)< 0) + return -1; + arpt->insert(ip, EtherAddress::make_broadcast()); // XXX? + return 0; + } + case h_clear: + arpt->clear(); + return 0; + default: + return -1; + } +} + +template<typename T> +void +ARPTableBase<T>::add_handlers() +{ + add_read_handler("table", read_handler, h_table); + add_data_handlers("drops", Handler::OP_READ,&_drops); + add_data_handlers("count", Handler::OP_READ,&_entry_count); + add_data_handlers("length", Handler::OP_READ,&_packet_count); + add_write_handler("insert", write_handler, h_insert); + add_write_handler("delete", write_handler, h_delete); + add_write_handler("clear", write_handler, h_clear); +} + +class ARPTable : public ARPTableBase<IPAddress> { public: + + ARPTable(); + ~ARPTable(); + + const char *class_name() const { return "ARPTable"; } + +}; + CLICK_ENDDECLS #endif _______________________________________________ click mailing list [email protected] https://amsterdam.lcs.mit.edu/mailman/listinfo/click
