From 16a5d1e4727db5c27a03d57d477512e07abe4988 Mon Sep 17 00:00:00 2001 From: Ethan Jackson Date: Fri, 22 Jul 2011 12:00:46 -0700 Subject: [PATCH] mac-learning: Simplify memory management. The mac-learning implementation used a free list to keep track of statically allocated table entries. This made the code slightly more difficult to understand than the more straightforward heap based strategy implemented by this patch. --- lib/mac-learning.c | 31 ++++++++++++++++--------------- lib/mac-learning.h | 4 +--- 2 files changed, 17 insertions(+), 18 deletions(-) diff --git a/lib/mac-learning.c b/lib/mac-learning.c index 5e05885e..bb84cfcc 100644 --- a/lib/mac-learning.c +++ b/lib/mac-learning.c @@ -103,16 +103,10 @@ struct mac_learning * mac_learning_create(void) { struct mac_learning *ml; - int i; ml = xmalloc(sizeof *ml); list_init(&ml->lrus); - list_init(&ml->free); hmap_init(&ml->table); - for (i = 0; i < MAC_MAX; i++) { - struct mac_entry *s = &ml->entries[i]; - list_push_front(&ml->free, &s->lru_node); - } ml->secret = random_uint32(); ml->flood_vlans = NULL; return ml; @@ -123,7 +117,14 @@ void mac_learning_destroy(struct mac_learning *ml) { if (ml) { + struct mac_entry *e, *next; + + HMAP_FOR_EACH_SAFE (e, next, hmap_node, &ml->table) { + hmap_remove(&ml->table, &e->hmap_node); + free(e); + } hmap_destroy(&ml->table); + bitmap_free(ml->flood_vlans); free(ml); } @@ -181,22 +182,22 @@ mac_learning_insert(struct mac_learning *ml, if (!e) { uint32_t hash = mac_table_hash(ml, src_mac, vlan); - if (!list_is_empty(&ml->free)) { - e = mac_entry_from_lru_node(ml->free.next); - } else { - e = mac_entry_from_lru_node(ml->lrus.next); - hmap_remove(&ml->table, &e->hmap_node); + if (hmap_count(&ml->table) >= MAC_MAX) { + get_lru(ml, &e); + mac_learning_expire(ml, e); } + e = xmalloc(sizeof *e); hmap_insert(&ml->table, &e->hmap_node, hash); memcpy(e->mac, src_mac, ETH_ADDR_LEN); e->vlan = vlan; e->tag = 0; e->grat_arp_lock = TIME_MIN; + } else { + list_remove(&e->lru_node); } /* Mark 'e' as recently used. */ - list_remove(&e->lru_node); list_push_back(&ml->lrus, &e->lru_node); e->expires = time_now() + MAC_ENTRY_IDLE_TIME; @@ -250,14 +251,13 @@ mac_learning_lookup(const struct mac_learning *ml, } } -/* Expires 'e' from the 'ml' hash table. 'e' must not already be on the free - * list. */ +/* Expires 'e' from the 'ml' hash table. */ void mac_learning_expire(struct mac_learning *ml, struct mac_entry *e) { hmap_remove(&ml->table, &e->hmap_node); list_remove(&e->lru_node); - list_push_front(&ml->free, &e->lru_node); + free(e); } /* Expires all the mac-learning entries in 'ml'. The tags in 'ml' are @@ -270,6 +270,7 @@ mac_learning_flush(struct mac_learning *ml) while (get_lru(ml, &e)){ mac_learning_expire(ml, e); } + hmap_shrink(&ml->table); } void diff --git a/lib/mac-learning.h b/lib/mac-learning.h index d2f28744..0263e498 100644 --- a/lib/mac-learning.h +++ b/lib/mac-learning.h @@ -36,7 +36,7 @@ /* A MAC learning table entry. */ struct mac_entry { struct hmap_node hmap_node; /* Node in a mac_learning hmap. */ - struct list lru_node; /* Element in 'lrus' or 'free' list. */ + struct list lru_node; /* Element in 'lrus' list. */ time_t expires; /* Expiration time. */ time_t grat_arp_lock; /* Gratuitous ARP lock expiration time. */ uint8_t mac[ETH_ADDR_LEN]; /* Known MAC address. */ @@ -76,10 +76,8 @@ static inline bool mac_entry_is_grat_arp_locked(const struct mac_entry *mac) /* MAC learning table. */ struct mac_learning { struct hmap table; /* Learning table. */ - struct list free; /* Not-in-use entries. */ struct list lrus; /* In-use entries, least recently used at the front, most recently used at the back. */ - struct mac_entry entries[MAC_MAX]; /* All entries. */ uint32_t secret; /* Secret for randomizing hash table. */ unsigned long *flood_vlans; /* Bitmap of learning disabled VLANs. */ }; -- 2.30.2