Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2015 Nicira, Inc.
3 : : *
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:
7 : : *
8 : : * http://www.apache.org/licenses/LICENSE-2.0
9 : : *
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.
15 : : */
16 : :
17 : : #ifndef MAC_LEARNING_H
18 : : #define MAC_LEARNING_H 1
19 : :
20 : : #include <time.h>
21 : : #include "heap.h"
22 : : #include "openvswitch/hmap.h"
23 : : #include "openvswitch/list.h"
24 : : #include "ovs-atomic.h"
25 : : #include "ovs-thread.h"
26 : : #include "packets.h"
27 : : #include "timeval.h"
28 : :
29 : : /* MAC learning table
30 : : * ==================
31 : : *
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.
39 : : *
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.
46 : : *
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. Please refer to the description of SLB bonding in
50 : : * vswitchd/INTERNALS for an explanation.
51 : : *
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
58 : : * long.
59 : : *
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).
73 : : *
74 : : *
75 : : * Thread-safety
76 : : * =============
77 : : *
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).
87 : : */
88 : :
89 : : struct mac_learning;
90 : :
91 : : /* Default maximum size of a MAC learning table, in entries. */
92 : : #define MAC_DEFAULT_MAX 2048
93 : :
94 : : /* Time, in seconds, before expiring a mac_entry due to inactivity. */
95 : : #define MAC_ENTRY_DEFAULT_IDLE_TIME 300
96 : :
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
100 : :
101 : : /* A MAC learning table entry.
102 : : * Guarded by owning 'mac_learning''s rwlock. */
103 : : struct mac_entry {
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. */
109 : :
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. */
113 : :
114 : : /* Learned port.
115 : : *
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. */
119 : : };
120 : :
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);
124 : :
125 : : /* Information about client-provided port pointers (the 'port' member), to
126 : : * allow for per-port fairness.
127 : : *
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. */
135 : : };
136 : :
137 : : /* Sets a gratuitous ARP lock on 'mac' that will expire in
138 : : * MAC_GRAT_ARP_LOCK_TIME seconds. */
139 : 6 : static inline void mac_entry_set_grat_arp_lock(struct mac_entry *mac)
140 : : {
141 : 6 : mac->grat_arp_lock = time_now() + MAC_GRAT_ARP_LOCK_TIME;
142 : 6 : }
143 : :
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 : 0 : static inline bool mac_entry_is_grat_arp_locked(const struct mac_entry *mac)
147 : : {
148 : 0 : return time_now() < mac->grat_arp_lock;
149 : : }
150 : :
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;
162 : :
163 : : /* Fairness.
164 : : *
165 : : * Both of these data structures include the same "struct
166 : : * mac_learning_port" but indexed differently.
167 : : *
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
172 : : * fairness.
173 : : *
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. */
177 : : };
178 : :
179 : : int mac_entry_age(const struct mac_learning *ml, const struct mac_entry *e)
180 : : OVS_REQ_RDLOCK(ml->rwlock);
181 : :
182 : : /* Basics. */
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 *);
186 : :
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);
190 : :
191 : : /* Configuration. */
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);
200 : :
201 : : /* Learning. */
202 : : bool mac_learning_may_learn(const struct mac_learning *ml,
203 : : const struct eth_addr src_mac,
204 : : uint16_t vlan)
205 : : OVS_REQ_RDLOCK(ml->rwlock);
206 : : struct mac_entry *mac_learning_insert(struct mac_learning *ml,
207 : : const struct eth_addr src,
208 : : uint16_t vlan)
209 : : OVS_REQ_WRLOCK(ml->rwlock);
210 : :
211 : : /* Lookup. */
212 : : struct mac_entry *mac_learning_lookup(const struct mac_learning *ml,
213 : : const struct eth_addr dst,
214 : : uint16_t vlan)
215 : : OVS_REQ_RDLOCK(ml->rwlock);
216 : :
217 : : /* Flushing. */
218 : : void mac_learning_expire(struct mac_learning *ml, struct mac_entry *e)
219 : : OVS_REQ_WRLOCK(ml->rwlock);
220 : : void mac_learning_flush(struct mac_learning *ml) OVS_REQ_WRLOCK(ml->rwlock);
221 : :
222 : : /* Inlines. */
223 : :
224 : : static inline void *
225 : 41516 : mac_entry_get_port(const struct mac_learning *ml OVS_UNUSED,
226 : : const struct mac_entry *e)
227 : : OVS_REQ_RDLOCK(ml->rwlock)
228 : : {
229 [ + + ]: 41516 : return e->mlport ? e->mlport->port : NULL;
230 : : }
231 : :
232 : : #endif /* mac-learning.h */
|
