2 * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2015 Nicira, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at:
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 #ifndef MAC_LEARNING_H
18 #define MAC_LEARNING_H 1
22 #include "openvswitch/hmap.h"
23 #include "openvswitch/list.h"
24 #include "ovs-atomic.h"
25 #include "ovs-thread.h"
32 * A MAC learning table is a dictionary data structure that is specialized to
33 * map from an (Ethernet address, VLAN ID) pair to a user-provided pointer. In
34 * an Ethernet switch implementation, it used to keep track of the port on
35 * which a packet from a given Ethernet address was last seen. This knowledge
36 * is useful when the switch receives a packet to such an Ethernet address, so
37 * that the switch can send the packet directly to the correct port instead of
38 * having to flood it to every port.
40 * A few complications make the implementation into more than a simple wrapper
41 * around a hash table. First, and most simply, MAC learning can be disabled
42 * on a per-VLAN basis. (This is most useful for RSPAN; see
43 * ovs-vswitchd.conf.db(5) documentation of the "output_vlan" column in the
44 * Mirror table for more information.). The data structure maintains a bitmap
45 * to track such VLANs.
47 * Second, the implementation has the ability to "lock" a MAC table entry
48 * updated by a gratuitous ARP. This is a simple feature but the rationale for
49 * it is complicated. Refer to the description of SLB bonding in the
50 * 'ovs-vswitchd Internals' guide for an explanation.
52 * Third, the implementation expires entries that are idle for longer than a
53 * configurable amount of time. This is implemented by keeping all of the
54 * current table entries on a list ordered from least recently used (LRU) to
55 * most recently used (MRU). Each time a MAC entry is used, it is moved to the
56 * MRU end of the list. Periodically mac_learning_run() sweeps through the
57 * list starting from the LRU end, deleting each entry that has been idle too
60 * Finally, the number of MAC learning table entries has a configurable maximum
61 * size to prevent memory exhaustion. When a new entry must be inserted but
62 * the table is already full, the implementation uses an eviction strategy
63 * based on fairness: it chooses the port that currently has greatest number of
64 * learned MACs (choosing arbitrarily in case of a tie), and among that port's
65 * entries it evicts the least recently used. (This is a security feature
66 * because it prevents an attacker from forcing other ports' MACs out of the
67 * MAC learning table with a "MAC flooding attack" that causes the other ports'
68 * traffic to be flooded so that the attacker can easily sniff it.) The
69 * implementation of this feature is like a specialized form of the
70 * general-purpose "eviction groups" that OVS implements in OpenFlow (see the
71 * documentation of the "groups" column in the Flow_Table table in
72 * ovs-vswitchd.conf.db(5) for details).
78 * Many operations require the caller to take the MAC learning table's rwlock
79 * for writing (please refer to the Clang thread safety annotations). The
80 * important exception to this is mac_learning_lookup(), which only needs a
81 * read lock. This is useful for the common case where a MAC learning entry
82 * being looked up already exists and does not need an update. However,
83 * there's no deadlock-free way to upgrade a read lock to a write lock, so in
84 * the case where the lookup result means that an update is required, the
85 * caller must drop the read lock, take the write lock, and then repeat the
86 * lookup (in case some other thread has already made a change).
91 /* Default maximum size of a MAC learning table, in entries. */
92 #define MAC_DEFAULT_MAX 2048
94 /* Time, in seconds, before expiring a mac_entry due to inactivity. */
95 #define MAC_ENTRY_DEFAULT_IDLE_TIME 300
97 /* Time, in seconds, to lock an entry updated by a gratuitous ARP to avoid
98 * relearning based on a reflection from a bond slave. */
99 #define MAC_GRAT_ARP_LOCK_TIME 5
101 /* A MAC learning table entry.
102 * Guarded by owning 'mac_learning''s rwlock. */
104 struct hmap_node hmap_node
; /* Node in a mac_learning hmap. */
105 time_t expires
; /* Expiration time. */
106 time_t grat_arp_lock
; /* Gratuitous ARP lock expiration time. */
107 struct eth_addr mac
; /* Known MAC address. */
108 uint16_t vlan
; /* VLAN tag. */
110 /* The following are marked guarded to prevent users from iterating over or
111 * accessing a mac_entry without holding the parent mac_learning rwlock. */
112 struct ovs_list lru_node OVS_GUARDED
; /* Element in 'lrus' list. */
116 * The client-specified data is mlport->port. */
117 struct mac_learning_port
*mlport
;
118 struct ovs_list port_lru_node
; /* In mac_learning_port's "port_lru"s. */
121 static inline void *mac_entry_get_port(const struct mac_learning
*ml
,
122 const struct mac_entry
*);
123 void mac_entry_set_port(struct mac_learning
*, struct mac_entry
*, void *port
);
125 /* Information about client-provided port pointers (the 'port' member), to
126 * allow for per-port fairness.
128 * The client-provided pointer is opaque to the MAC-learning table, which never
129 * dereferences it. */
130 struct mac_learning_port
{
131 struct hmap_node hmap_node
; /* In mac_learning's "ports_by_ptr". */
132 struct heap_node heap_node
; /* In mac_learning's "ports_by_usage". */
133 void *port
; /* Client-provided port pointer. */
134 struct ovs_list port_lrus
; /* Contains "struct mac_entry"s by port_lru. */
137 /* Sets a gratuitous ARP lock on 'mac' that will expire in
138 * MAC_GRAT_ARP_LOCK_TIME seconds. */
139 static inline void mac_entry_set_grat_arp_lock(struct mac_entry
*mac
)
141 mac
->grat_arp_lock
= time_now() + MAC_GRAT_ARP_LOCK_TIME
;
144 /* Returns true if a gratuitous ARP lock is in effect on 'mac', false if none
145 * has ever been asserted or if it has expired. */
146 static inline bool mac_entry_is_grat_arp_locked(const struct mac_entry
*mac
)
148 return time_now() < mac
->grat_arp_lock
;
151 /* MAC learning table. */
152 struct mac_learning
{
153 struct hmap table
; /* Learning table. */
154 struct ovs_list lrus OVS_GUARDED
; /* In-use entries, LRU at front. */
155 uint32_t secret
; /* Secret for randomizing hash table. */
156 unsigned long *flood_vlans
; /* Bitmap of learning disabled VLANs. */
157 unsigned int idle_time
; /* Max age before deleting an entry. */
158 size_t max_entries
; /* Max number of learned MACs. */
159 struct ovs_refcount ref_cnt
;
160 struct ovs_rwlock rwlock
;
161 bool need_revalidate
;
165 * Both of these data structures include the same "struct
166 * mac_learning_port" but indexed differently.
168 * ports_by_usage is a per-port max-heap, in which the priority is the
169 * number of MAC addresses for the port. When the MAC learning table
170 * overflows, this allows us to evict a MAC entry from one of the ports
171 * that have the largest number of MAC entries, achieving a form of
174 * ports_by_ptr is a hash table indexed by the client-provided pointer. */
175 struct hmap ports_by_ptr
; /* struct mac_learning_port hmap_nodes. */
176 struct heap ports_by_usage
; /* struct mac_learning_port heap_nodes. */
179 int mac_entry_age(const struct mac_learning
*ml
, const struct mac_entry
*e
)
180 OVS_REQ_RDLOCK(ml
->rwlock
);
183 struct mac_learning
*mac_learning_create(unsigned int idle_time
);
184 struct mac_learning
*mac_learning_ref(const struct mac_learning
*);
185 void mac_learning_unref(struct mac_learning
*);
187 bool mac_learning_run(struct mac_learning
*ml
) OVS_REQ_WRLOCK(ml
->rwlock
);
188 void mac_learning_wait(struct mac_learning
*ml
)
189 OVS_REQ_RDLOCK(ml
->rwlock
);
192 bool mac_learning_set_flood_vlans(struct mac_learning
*ml
,
193 const unsigned long *bitmap
)
194 OVS_REQ_WRLOCK(ml
->rwlock
);
195 void mac_learning_set_idle_time(struct mac_learning
*ml
,
196 unsigned int idle_time
)
197 OVS_REQ_WRLOCK(ml
->rwlock
);
198 void mac_learning_set_max_entries(struct mac_learning
*ml
, size_t max_entries
)
199 OVS_REQ_WRLOCK(ml
->rwlock
);
202 bool mac_learning_may_learn(const struct mac_learning
*ml
,
203 const struct eth_addr src_mac
,
205 OVS_REQ_RDLOCK(ml
->rwlock
);
206 struct mac_entry
*mac_learning_insert(struct mac_learning
*ml
,
207 const struct eth_addr src
,
209 OVS_REQ_WRLOCK(ml
->rwlock
);
210 bool mac_learning_update(struct mac_learning
*ml
, struct eth_addr src
,
211 int vlan
, bool is_gratuitous_arp
, bool is_bond
,
213 OVS_EXCLUDED(ml
->rwlock
);
216 struct mac_entry
*mac_learning_lookup(const struct mac_learning
*ml
,
217 const struct eth_addr dst
,
219 OVS_REQ_RDLOCK(ml
->rwlock
);
222 void mac_learning_expire(struct mac_learning
*ml
, struct mac_entry
*e
)
223 OVS_REQ_WRLOCK(ml
->rwlock
);
224 void mac_learning_flush(struct mac_learning
*ml
) OVS_REQ_WRLOCK(ml
->rwlock
);
229 mac_entry_get_port(const struct mac_learning
*ml OVS_UNUSED
,
230 const struct mac_entry
*e
)
231 OVS_REQ_RDLOCK(ml
->rwlock
)
233 return e
->mlport
? e
->mlport
->port
: NULL
;
236 #endif /* mac-learning.h */