1 /* Copyright (C) 2011-2015 B.A.T.M.A.N. contributors:
2  *
3  * Simon Wunderlich
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of version 2 of the GNU General Public
7  * License as published by the Free Software Foundation.
8  *
9  * This program is distributed in the hope that it will be useful, but
10  * WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, see <http://www.gnu.org/licenses/>.
16  */
17 
18 #include "bridge_loop_avoidance.h"
19 #include "main.h"
20 
21 #include <linux/atomic.h>
22 #include <linux/byteorder/generic.h>
23 #include <linux/compiler.h>
24 #include <linux/crc16.h>
25 #include <linux/errno.h>
26 #include <linux/etherdevice.h>
27 #include <linux/fs.h>
28 #include <linux/if_arp.h>
29 #include <linux/if_ether.h>
30 #include <linux/if_vlan.h>
31 #include <linux/jhash.h>
32 #include <linux/jiffies.h>
33 #include <linux/kernel.h>
34 #include <linux/list.h>
35 #include <linux/lockdep.h>
36 #include <linux/netdevice.h>
37 #include <linux/rculist.h>
38 #include <linux/rcupdate.h>
39 #include <linux/seq_file.h>
40 #include <linux/skbuff.h>
41 #include <linux/slab.h>
42 #include <linux/spinlock.h>
43 #include <linux/stddef.h>
44 #include <linux/string.h>
45 #include <linux/workqueue.h>
46 #include <net/arp.h>
47 
48 #include "hard-interface.h"
49 #include "hash.h"
50 #include "originator.h"
51 #include "packet.h"
52 #include "translation-table.h"
53 
54 static const uint8_t batadv_announce_mac[4] = {0x43, 0x05, 0x43, 0x05};
55 
56 static void batadv_bla_periodic_work(struct work_struct *work);
57 static void
58 batadv_bla_send_announce(struct batadv_priv *bat_priv,
59 			 struct batadv_bla_backbone_gw *backbone_gw);
60 
61 /* return the index of the claim */
62 static inline uint32_t batadv_choose_claim(const void *data, uint32_t size)
63 {
64 	struct batadv_bla_claim *claim = (struct batadv_bla_claim *)data;
65 	uint32_t hash = 0;
66 
67 	hash = jhash(&claim->addr, sizeof(claim->addr), hash);
68 	hash = jhash(&claim->vid, sizeof(claim->vid), hash);
69 
70 	return hash % size;
71 }
72 
73 /* return the index of the backbone gateway */
74 static inline uint32_t batadv_choose_backbone_gw(const void *data,
75 						 uint32_t size)
76 {
77 	const struct batadv_bla_claim *claim = (struct batadv_bla_claim *)data;
78 	uint32_t hash = 0;
79 
80 	hash = jhash(&claim->addr, sizeof(claim->addr), hash);
81 	hash = jhash(&claim->vid, sizeof(claim->vid), hash);
82 
83 	return hash % size;
84 }
85 
86 /* compares address and vid of two backbone gws */
87 static int batadv_compare_backbone_gw(const struct hlist_node *node,
88 				      const void *data2)
89 {
90 	const void *data1 = container_of(node, struct batadv_bla_backbone_gw,
91 					 hash_entry);
92 	const struct batadv_bla_backbone_gw *gw1 = data1, *gw2 = data2;
93 
94 	if (!batadv_compare_eth(gw1->orig, gw2->orig))
95 		return 0;
96 
97 	if (gw1->vid != gw2->vid)
98 		return 0;
99 
100 	return 1;
101 }
102 
103 /* compares address and vid of two claims */
104 static int batadv_compare_claim(const struct hlist_node *node,
105 				const void *data2)
106 {
107 	const void *data1 = container_of(node, struct batadv_bla_claim,
108 					 hash_entry);
109 	const struct batadv_bla_claim *cl1 = data1, *cl2 = data2;
110 
111 	if (!batadv_compare_eth(cl1->addr, cl2->addr))
112 		return 0;
113 
114 	if (cl1->vid != cl2->vid)
115 		return 0;
116 
117 	return 1;
118 }
119 
120 /* free a backbone gw */
121 static void
122 batadv_backbone_gw_free_ref(struct batadv_bla_backbone_gw *backbone_gw)
123 {
124 	if (atomic_dec_and_test(&backbone_gw->refcount))
125 		kfree_rcu(backbone_gw, rcu);
126 }
127 
128 /* finally deinitialize the claim */
129 static void batadv_claim_free_rcu(struct rcu_head *rcu)
130 {
131 	struct batadv_bla_claim *claim;
132 
133 	claim = container_of(rcu, struct batadv_bla_claim, rcu);
134 
135 	batadv_backbone_gw_free_ref(claim->backbone_gw);
136 	kfree(claim);
137 }
138 
139 /* free a claim, call claim_free_rcu if its the last reference */
140 static void batadv_claim_free_ref(struct batadv_bla_claim *claim)
141 {
142 	if (atomic_dec_and_test(&claim->refcount))
143 		call_rcu(&claim->rcu, batadv_claim_free_rcu);
144 }
145 
146 /**
147  * batadv_claim_hash_find
148  * @bat_priv: the bat priv with all the soft interface information
149  * @data: search data (may be local/static data)
150  *
151  * looks for a claim in the hash, and returns it if found
152  * or NULL otherwise.
153  */
154 static struct batadv_bla_claim
155 *batadv_claim_hash_find(struct batadv_priv *bat_priv,
156 			struct batadv_bla_claim *data)
157 {
158 	struct batadv_hashtable *hash = bat_priv->bla.claim_hash;
159 	struct hlist_head *head;
160 	struct batadv_bla_claim *claim;
161 	struct batadv_bla_claim *claim_tmp = NULL;
162 	int index;
163 
164 	if (!hash)
165 		return NULL;
166 
167 	index = batadv_choose_claim(data, hash->size);
168 	head = &hash->table[index];
169 
170 	rcu_read_lock();
171 	hlist_for_each_entry_rcu(claim, head, hash_entry) {
172 		if (!batadv_compare_claim(&claim->hash_entry, data))
173 			continue;
174 
175 		if (!atomic_inc_not_zero(&claim->refcount))
176 			continue;
177 
178 		claim_tmp = claim;
179 		break;
180 	}
181 	rcu_read_unlock();
182 
183 	return claim_tmp;
184 }
185 
186 /**
187  * batadv_backbone_hash_find - looks for a claim in the hash
188  * @bat_priv: the bat priv with all the soft interface information
189  * @addr: the address of the originator
190  * @vid: the VLAN ID
191  *
192  * Returns claim if found or NULL otherwise.
193  */
194 static struct batadv_bla_backbone_gw *
195 batadv_backbone_hash_find(struct batadv_priv *bat_priv,
196 			  uint8_t *addr, unsigned short vid)
197 {
198 	struct batadv_hashtable *hash = bat_priv->bla.backbone_hash;
199 	struct hlist_head *head;
200 	struct batadv_bla_backbone_gw search_entry, *backbone_gw;
201 	struct batadv_bla_backbone_gw *backbone_gw_tmp = NULL;
202 	int index;
203 
204 	if (!hash)
205 		return NULL;
206 
207 	ether_addr_copy(search_entry.orig, addr);
208 	search_entry.vid = vid;
209 
210 	index = batadv_choose_backbone_gw(&search_entry, hash->size);
211 	head = &hash->table[index];
212 
213 	rcu_read_lock();
214 	hlist_for_each_entry_rcu(backbone_gw, head, hash_entry) {
215 		if (!batadv_compare_backbone_gw(&backbone_gw->hash_entry,
216 						&search_entry))
217 			continue;
218 
219 		if (!atomic_inc_not_zero(&backbone_gw->refcount))
220 			continue;
221 
222 		backbone_gw_tmp = backbone_gw;
223 		break;
224 	}
225 	rcu_read_unlock();
226 
227 	return backbone_gw_tmp;
228 }
229 
230 /* delete all claims for a backbone */
231 static void
232 batadv_bla_del_backbone_claims(struct batadv_bla_backbone_gw *backbone_gw)
233 {
234 	struct batadv_hashtable *hash;
235 	struct hlist_node *node_tmp;
236 	struct hlist_head *head;
237 	struct batadv_bla_claim *claim;
238 	int i;
239 	spinlock_t *list_lock;	/* protects write access to the hash lists */
240 
241 	hash = backbone_gw->bat_priv->bla.claim_hash;
242 	if (!hash)
243 		return;
244 
245 	for (i = 0; i < hash->size; i++) {
246 		head = &hash->table[i];
247 		list_lock = &hash->list_locks[i];
248 
249 		spin_lock_bh(list_lock);
250 		hlist_for_each_entry_safe(claim, node_tmp,
251 					  head, hash_entry) {
252 			if (claim->backbone_gw != backbone_gw)
253 				continue;
254 
255 			batadv_claim_free_ref(claim);
256 			hlist_del_rcu(&claim->hash_entry);
257 		}
258 		spin_unlock_bh(list_lock);
259 	}
260 
261 	/* all claims gone, initialize CRC */
262 	backbone_gw->crc = BATADV_BLA_CRC_INIT;
263 }
264 
265 /**
266  * batadv_bla_send_claim - sends a claim frame according to the provided info
267  * @bat_priv: the bat priv with all the soft interface information
268  * @mac: the mac address to be announced within the claim
269  * @vid: the VLAN ID
270  * @claimtype: the type of the claim (CLAIM, UNCLAIM, ANNOUNCE, ...)
271  */
272 static void batadv_bla_send_claim(struct batadv_priv *bat_priv, uint8_t *mac,
273 				  unsigned short vid, int claimtype)
274 {
275 	struct sk_buff *skb;
276 	struct ethhdr *ethhdr;
277 	struct batadv_hard_iface *primary_if;
278 	struct net_device *soft_iface;
279 	uint8_t *hw_src;
280 	struct batadv_bla_claim_dst local_claim_dest;
281 	__be32 zeroip = 0;
282 
283 	primary_if = batadv_primary_if_get_selected(bat_priv);
284 	if (!primary_if)
285 		return;
286 
287 	memcpy(&local_claim_dest, &bat_priv->bla.claim_dest,
288 	       sizeof(local_claim_dest));
289 	local_claim_dest.type = claimtype;
290 
291 	soft_iface = primary_if->soft_iface;
292 
293 	skb = arp_create(ARPOP_REPLY, ETH_P_ARP,
294 			 /* IP DST: 0.0.0.0 */
295 			 zeroip,
296 			 primary_if->soft_iface,
297 			 /* IP SRC: 0.0.0.0 */
298 			 zeroip,
299 			 /* Ethernet DST: Broadcast */
300 			 NULL,
301 			 /* Ethernet SRC/HW SRC:  originator mac */
302 			 primary_if->net_dev->dev_addr,
303 			 /* HW DST: FF:43:05:XX:YY:YY
304 			  * with XX   = claim type
305 			  * and YY:YY = group id
306 			  */
307 			 (uint8_t *)&local_claim_dest);
308 
309 	if (!skb)
310 		goto out;
311 
312 	ethhdr = (struct ethhdr *)skb->data;
313 	hw_src = (uint8_t *)ethhdr + ETH_HLEN + sizeof(struct arphdr);
314 
315 	/* now we pretend that the client would have sent this ... */
316 	switch (claimtype) {
317 	case BATADV_CLAIM_TYPE_CLAIM:
318 		/* normal claim frame
319 		 * set Ethernet SRC to the clients mac
320 		 */
321 		ether_addr_copy(ethhdr->h_source, mac);
322 		batadv_dbg(BATADV_DBG_BLA, bat_priv,
323 			   "bla_send_claim(): CLAIM %pM on vid %d\n", mac,
324 			   BATADV_PRINT_VID(vid));
325 		break;
326 	case BATADV_CLAIM_TYPE_UNCLAIM:
327 		/* unclaim frame
328 		 * set HW SRC to the clients mac
329 		 */
330 		ether_addr_copy(hw_src, mac);
331 		batadv_dbg(BATADV_DBG_BLA, bat_priv,
332 			   "bla_send_claim(): UNCLAIM %pM on vid %d\n", mac,
333 			   BATADV_PRINT_VID(vid));
334 		break;
335 	case BATADV_CLAIM_TYPE_ANNOUNCE:
336 		/* announcement frame
337 		 * set HW SRC to the special mac containg the crc
338 		 */
339 		ether_addr_copy(hw_src, mac);
340 		batadv_dbg(BATADV_DBG_BLA, bat_priv,
341 			   "bla_send_claim(): ANNOUNCE of %pM on vid %d\n",
342 			   ethhdr->h_source, BATADV_PRINT_VID(vid));
343 		break;
344 	case BATADV_CLAIM_TYPE_REQUEST:
345 		/* request frame
346 		 * set HW SRC and header destination to the receiving backbone
347 		 * gws mac
348 		 */
349 		ether_addr_copy(hw_src, mac);
350 		ether_addr_copy(ethhdr->h_dest, mac);
351 		batadv_dbg(BATADV_DBG_BLA, bat_priv,
352 			   "bla_send_claim(): REQUEST of %pM to %pM on vid %d\n",
353 			   ethhdr->h_source, ethhdr->h_dest,
354 			   BATADV_PRINT_VID(vid));
355 		break;
356 	}
357 
358 	if (vid & BATADV_VLAN_HAS_TAG)
359 		skb = vlan_insert_tag(skb, htons(ETH_P_8021Q),
360 				      vid & VLAN_VID_MASK);
361 
362 	skb_reset_mac_header(skb);
363 	skb->protocol = eth_type_trans(skb, soft_iface);
364 	batadv_inc_counter(bat_priv, BATADV_CNT_RX);
365 	batadv_add_counter(bat_priv, BATADV_CNT_RX_BYTES,
366 			   skb->len + ETH_HLEN);
367 	soft_iface->last_rx = jiffies;
368 
369 	netif_rx(skb);
370 out:
371 	if (primary_if)
372 		batadv_hardif_free_ref(primary_if);
373 }
374 
375 /**
376  * batadv_bla_get_backbone_gw
377  * @bat_priv: the bat priv with all the soft interface information
378  * @orig: the mac address of the originator
379  * @vid: the VLAN ID
380  * @own_backbone: set if the requested backbone is local
381  *
382  * searches for the backbone gw or creates a new one if it could not
383  * be found.
384  */
385 static struct batadv_bla_backbone_gw *
386 batadv_bla_get_backbone_gw(struct batadv_priv *bat_priv, uint8_t *orig,
387 			   unsigned short vid, bool own_backbone)
388 {
389 	struct batadv_bla_backbone_gw *entry;
390 	struct batadv_orig_node *orig_node;
391 	int hash_added;
392 
393 	entry = batadv_backbone_hash_find(bat_priv, orig, vid);
394 
395 	if (entry)
396 		return entry;
397 
398 	batadv_dbg(BATADV_DBG_BLA, bat_priv,
399 		   "bla_get_backbone_gw(): not found (%pM, %d), creating new entry\n",
400 		   orig, BATADV_PRINT_VID(vid));
401 
402 	entry = kzalloc(sizeof(*entry), GFP_ATOMIC);
403 	if (!entry)
404 		return NULL;
405 
406 	entry->vid = vid;
407 	entry->lasttime = jiffies;
408 	entry->crc = BATADV_BLA_CRC_INIT;
409 	entry->bat_priv = bat_priv;
410 	atomic_set(&entry->request_sent, 0);
411 	atomic_set(&entry->wait_periods, 0);
412 	ether_addr_copy(entry->orig, orig);
413 
414 	/* one for the hash, one for returning */
415 	atomic_set(&entry->refcount, 2);
416 
417 	hash_added = batadv_hash_add(bat_priv->bla.backbone_hash,
418 				     batadv_compare_backbone_gw,
419 				     batadv_choose_backbone_gw, entry,
420 				     &entry->hash_entry);
421 
422 	if (unlikely(hash_added != 0)) {
423 		/* hash failed, free the structure */
424 		kfree(entry);
425 		return NULL;
426 	}
427 
428 	/* this is a gateway now, remove any TT entry on this VLAN */
429 	orig_node = batadv_orig_hash_find(bat_priv, orig);
430 	if (orig_node) {
431 		batadv_tt_global_del_orig(bat_priv, orig_node, vid,
432 					  "became a backbone gateway");
433 		batadv_orig_node_free_ref(orig_node);
434 	}
435 
436 	if (own_backbone) {
437 		batadv_bla_send_announce(bat_priv, entry);
438 
439 		/* this will be decreased in the worker thread */
440 		atomic_inc(&entry->request_sent);
441 		atomic_set(&entry->wait_periods, BATADV_BLA_WAIT_PERIODS);
442 		atomic_inc(&bat_priv->bla.num_requests);
443 	}
444 
445 	return entry;
446 }
447 
448 /* update or add the own backbone gw to make sure we announce
449  * where we receive other backbone gws
450  */
451 static void
452 batadv_bla_update_own_backbone_gw(struct batadv_priv *bat_priv,
453 				  struct batadv_hard_iface *primary_if,
454 				  unsigned short vid)
455 {
456 	struct batadv_bla_backbone_gw *backbone_gw;
457 
458 	backbone_gw = batadv_bla_get_backbone_gw(bat_priv,
459 						 primary_if->net_dev->dev_addr,
460 						 vid, true);
461 	if (unlikely(!backbone_gw))
462 		return;
463 
464 	backbone_gw->lasttime = jiffies;
465 	batadv_backbone_gw_free_ref(backbone_gw);
466 }
467 
468 /**
469  * batadv_bla_answer_request - answer a bla request by sending own claims
470  * @bat_priv: the bat priv with all the soft interface information
471  * @primary_if: interface where the request came on
472  * @vid: the vid where the request came on
473  *
474  * Repeat all of our own claims, and finally send an ANNOUNCE frame
475  * to allow the requester another check if the CRC is correct now.
476  */
477 static void batadv_bla_answer_request(struct batadv_priv *bat_priv,
478 				      struct batadv_hard_iface *primary_if,
479 				      unsigned short vid)
480 {
481 	struct hlist_head *head;
482 	struct batadv_hashtable *hash;
483 	struct batadv_bla_claim *claim;
484 	struct batadv_bla_backbone_gw *backbone_gw;
485 	int i;
486 
487 	batadv_dbg(BATADV_DBG_BLA, bat_priv,
488 		   "bla_answer_request(): received a claim request, send all of our own claims again\n");
489 
490 	backbone_gw = batadv_backbone_hash_find(bat_priv,
491 						primary_if->net_dev->dev_addr,
492 						vid);
493 	if (!backbone_gw)
494 		return;
495 
496 	hash = bat_priv->bla.claim_hash;
497 	for (i = 0; i < hash->size; i++) {
498 		head = &hash->table[i];
499 
500 		rcu_read_lock();
501 		hlist_for_each_entry_rcu(claim, head, hash_entry) {
502 			/* only own claims are interesting */
503 			if (claim->backbone_gw != backbone_gw)
504 				continue;
505 
506 			batadv_bla_send_claim(bat_priv, claim->addr, claim->vid,
507 					      BATADV_CLAIM_TYPE_CLAIM);
508 		}
509 		rcu_read_unlock();
510 	}
511 
512 	/* finally, send an announcement frame */
513 	batadv_bla_send_announce(bat_priv, backbone_gw);
514 	batadv_backbone_gw_free_ref(backbone_gw);
515 }
516 
517 /**
518  * batadv_bla_send_request - send a request to repeat claims
519  * @backbone_gw: the backbone gateway from whom we are out of sync
520  *
521  * When the crc is wrong, ask the backbone gateway for a full table update.
522  * After the request, it will repeat all of his own claims and finally
523  * send an announcement claim with which we can check again.
524  */
525 static void batadv_bla_send_request(struct batadv_bla_backbone_gw *backbone_gw)
526 {
527 	/* first, remove all old entries */
528 	batadv_bla_del_backbone_claims(backbone_gw);
529 
530 	batadv_dbg(BATADV_DBG_BLA, backbone_gw->bat_priv,
531 		   "Sending REQUEST to %pM\n", backbone_gw->orig);
532 
533 	/* send request */
534 	batadv_bla_send_claim(backbone_gw->bat_priv, backbone_gw->orig,
535 			      backbone_gw->vid, BATADV_CLAIM_TYPE_REQUEST);
536 
537 	/* no local broadcasts should be sent or received, for now. */
538 	if (!atomic_read(&backbone_gw->request_sent)) {
539 		atomic_inc(&backbone_gw->bat_priv->bla.num_requests);
540 		atomic_set(&backbone_gw->request_sent, 1);
541 	}
542 }
543 
544 /**
545  * batadv_bla_send_announce
546  * @bat_priv: the bat priv with all the soft interface information
547  * @backbone_gw: our backbone gateway which should be announced
548  *
549  * This function sends an announcement. It is called from multiple
550  * places.
551  */
552 static void batadv_bla_send_announce(struct batadv_priv *bat_priv,
553 				     struct batadv_bla_backbone_gw *backbone_gw)
554 {
555 	uint8_t mac[ETH_ALEN];
556 	__be16 crc;
557 
558 	memcpy(mac, batadv_announce_mac, 4);
559 	crc = htons(backbone_gw->crc);
560 	memcpy(&mac[4], &crc, 2);
561 
562 	batadv_bla_send_claim(bat_priv, mac, backbone_gw->vid,
563 			      BATADV_CLAIM_TYPE_ANNOUNCE);
564 }
565 
566 /**
567  * batadv_bla_add_claim - Adds a claim in the claim hash
568  * @bat_priv: the bat priv with all the soft interface information
569  * @mac: the mac address of the claim
570  * @vid: the VLAN ID of the frame
571  * @backbone_gw: the backbone gateway which claims it
572  */
573 static void batadv_bla_add_claim(struct batadv_priv *bat_priv,
574 				 const uint8_t *mac, const unsigned short vid,
575 				 struct batadv_bla_backbone_gw *backbone_gw)
576 {
577 	struct batadv_bla_claim *claim;
578 	struct batadv_bla_claim search_claim;
579 	int hash_added;
580 
581 	ether_addr_copy(search_claim.addr, mac);
582 	search_claim.vid = vid;
583 	claim = batadv_claim_hash_find(bat_priv, &search_claim);
584 
585 	/* create a new claim entry if it does not exist yet. */
586 	if (!claim) {
587 		claim = kzalloc(sizeof(*claim), GFP_ATOMIC);
588 		if (!claim)
589 			return;
590 
591 		ether_addr_copy(claim->addr, mac);
592 		claim->vid = vid;
593 		claim->lasttime = jiffies;
594 		claim->backbone_gw = backbone_gw;
595 
596 		atomic_set(&claim->refcount, 2);
597 		batadv_dbg(BATADV_DBG_BLA, bat_priv,
598 			   "bla_add_claim(): adding new entry %pM, vid %d to hash ...\n",
599 			   mac, BATADV_PRINT_VID(vid));
600 		hash_added = batadv_hash_add(bat_priv->bla.claim_hash,
601 					     batadv_compare_claim,
602 					     batadv_choose_claim, claim,
603 					     &claim->hash_entry);
604 
605 		if (unlikely(hash_added != 0)) {
606 			/* only local changes happened. */
607 			kfree(claim);
608 			return;
609 		}
610 	} else {
611 		claim->lasttime = jiffies;
612 		if (claim->backbone_gw == backbone_gw)
613 			/* no need to register a new backbone */
614 			goto claim_free_ref;
615 
616 		batadv_dbg(BATADV_DBG_BLA, bat_priv,
617 			   "bla_add_claim(): changing ownership for %pM, vid %d\n",
618 			   mac, BATADV_PRINT_VID(vid));
619 
620 		claim->backbone_gw->crc ^= crc16(0, claim->addr, ETH_ALEN);
621 		batadv_backbone_gw_free_ref(claim->backbone_gw);
622 	}
623 	/* set (new) backbone gw */
624 	atomic_inc(&backbone_gw->refcount);
625 	claim->backbone_gw = backbone_gw;
626 
627 	backbone_gw->crc ^= crc16(0, claim->addr, ETH_ALEN);
628 	backbone_gw->lasttime = jiffies;
629 
630 claim_free_ref:
631 	batadv_claim_free_ref(claim);
632 }
633 
634 /* Delete a claim from the claim hash which has the
635  * given mac address and vid.
636  */
637 static void batadv_bla_del_claim(struct batadv_priv *bat_priv,
638 				 const uint8_t *mac, const unsigned short vid)
639 {
640 	struct batadv_bla_claim search_claim, *claim;
641 
642 	ether_addr_copy(search_claim.addr, mac);
643 	search_claim.vid = vid;
644 	claim = batadv_claim_hash_find(bat_priv, &search_claim);
645 	if (!claim)
646 		return;
647 
648 	batadv_dbg(BATADV_DBG_BLA, bat_priv, "bla_del_claim(): %pM, vid %d\n",
649 		   mac, BATADV_PRINT_VID(vid));
650 
651 	batadv_hash_remove(bat_priv->bla.claim_hash, batadv_compare_claim,
652 			   batadv_choose_claim, claim);
653 	batadv_claim_free_ref(claim); /* reference from the hash is gone */
654 
655 	claim->backbone_gw->crc ^= crc16(0, claim->addr, ETH_ALEN);
656 
657 	/* don't need the reference from hash_find() anymore */
658 	batadv_claim_free_ref(claim);
659 }
660 
661 /* check for ANNOUNCE frame, return 1 if handled */
662 static int batadv_handle_announce(struct batadv_priv *bat_priv,
663 				  uint8_t *an_addr, uint8_t *backbone_addr,
664 				  unsigned short vid)
665 {
666 	struct batadv_bla_backbone_gw *backbone_gw;
667 	uint16_t crc;
668 
669 	if (memcmp(an_addr, batadv_announce_mac, 4) != 0)
670 		return 0;
671 
672 	backbone_gw = batadv_bla_get_backbone_gw(bat_priv, backbone_addr, vid,
673 						 false);
674 
675 	if (unlikely(!backbone_gw))
676 		return 1;
677 
678 	/* handle as ANNOUNCE frame */
679 	backbone_gw->lasttime = jiffies;
680 	crc = ntohs(*((__be16 *)(&an_addr[4])));
681 
682 	batadv_dbg(BATADV_DBG_BLA, bat_priv,
683 		   "handle_announce(): ANNOUNCE vid %d (sent by %pM)... CRC = %#.4x\n",
684 		   BATADV_PRINT_VID(vid), backbone_gw->orig, crc);
685 
686 	if (backbone_gw->crc != crc) {
687 		batadv_dbg(BATADV_DBG_BLA, backbone_gw->bat_priv,
688 			   "handle_announce(): CRC FAILED for %pM/%d (my = %#.4x, sent = %#.4x)\n",
689 			   backbone_gw->orig,
690 			   BATADV_PRINT_VID(backbone_gw->vid),
691 			   backbone_gw->crc, crc);
692 
693 		batadv_bla_send_request(backbone_gw);
694 	} else {
695 		/* if we have sent a request and the crc was OK,
696 		 * we can allow traffic again.
697 		 */
698 		if (atomic_read(&backbone_gw->request_sent)) {
699 			atomic_dec(&backbone_gw->bat_priv->bla.num_requests);
700 			atomic_set(&backbone_gw->request_sent, 0);
701 		}
702 	}
703 
704 	batadv_backbone_gw_free_ref(backbone_gw);
705 	return 1;
706 }
707 
708 /* check for REQUEST frame, return 1 if handled */
709 static int batadv_handle_request(struct batadv_priv *bat_priv,
710 				 struct batadv_hard_iface *primary_if,
711 				 uint8_t *backbone_addr,
712 				 struct ethhdr *ethhdr, unsigned short vid)
713 {
714 	/* check for REQUEST frame */
715 	if (!batadv_compare_eth(backbone_addr, ethhdr->h_dest))
716 		return 0;
717 
718 	/* sanity check, this should not happen on a normal switch,
719 	 * we ignore it in this case.
720 	 */
721 	if (!batadv_compare_eth(ethhdr->h_dest, primary_if->net_dev->dev_addr))
722 		return 1;
723 
724 	batadv_dbg(BATADV_DBG_BLA, bat_priv,
725 		   "handle_request(): REQUEST vid %d (sent by %pM)...\n",
726 		   BATADV_PRINT_VID(vid), ethhdr->h_source);
727 
728 	batadv_bla_answer_request(bat_priv, primary_if, vid);
729 	return 1;
730 }
731 
732 /* check for UNCLAIM frame, return 1 if handled */
733 static int batadv_handle_unclaim(struct batadv_priv *bat_priv,
734 				 struct batadv_hard_iface *primary_if,
735 				 uint8_t *backbone_addr,
736 				 uint8_t *claim_addr, unsigned short vid)
737 {
738 	struct batadv_bla_backbone_gw *backbone_gw;
739 
740 	/* unclaim in any case if it is our own */
741 	if (primary_if && batadv_compare_eth(backbone_addr,
742 					     primary_if->net_dev->dev_addr))
743 		batadv_bla_send_claim(bat_priv, claim_addr, vid,
744 				      BATADV_CLAIM_TYPE_UNCLAIM);
745 
746 	backbone_gw = batadv_backbone_hash_find(bat_priv, backbone_addr, vid);
747 
748 	if (!backbone_gw)
749 		return 1;
750 
751 	/* this must be an UNCLAIM frame */
752 	batadv_dbg(BATADV_DBG_BLA, bat_priv,
753 		   "handle_unclaim(): UNCLAIM %pM on vid %d (sent by %pM)...\n",
754 		   claim_addr, BATADV_PRINT_VID(vid), backbone_gw->orig);
755 
756 	batadv_bla_del_claim(bat_priv, claim_addr, vid);
757 	batadv_backbone_gw_free_ref(backbone_gw);
758 	return 1;
759 }
760 
761 /* check for CLAIM frame, return 1 if handled */
762 static int batadv_handle_claim(struct batadv_priv *bat_priv,
763 			       struct batadv_hard_iface *primary_if,
764 			       uint8_t *backbone_addr, uint8_t *claim_addr,
765 			       unsigned short vid)
766 {
767 	struct batadv_bla_backbone_gw *backbone_gw;
768 
769 	/* register the gateway if not yet available, and add the claim. */
770 
771 	backbone_gw = batadv_bla_get_backbone_gw(bat_priv, backbone_addr, vid,
772 						 false);
773 
774 	if (unlikely(!backbone_gw))
775 		return 1;
776 
777 	/* this must be a CLAIM frame */
778 	batadv_bla_add_claim(bat_priv, claim_addr, vid, backbone_gw);
779 	if (batadv_compare_eth(backbone_addr, primary_if->net_dev->dev_addr))
780 		batadv_bla_send_claim(bat_priv, claim_addr, vid,
781 				      BATADV_CLAIM_TYPE_CLAIM);
782 
783 	/* TODO: we could call something like tt_local_del() here. */
784 
785 	batadv_backbone_gw_free_ref(backbone_gw);
786 	return 1;
787 }
788 
789 /**
790  * batadv_check_claim_group
791  * @bat_priv: the bat priv with all the soft interface information
792  * @primary_if: the primary interface of this batman interface
793  * @hw_src: the Hardware source in the ARP Header
794  * @hw_dst: the Hardware destination in the ARP Header
795  * @ethhdr: pointer to the Ethernet header of the claim frame
796  *
797  * checks if it is a claim packet and if its on the same group.
798  * This function also applies the group ID of the sender
799  * if it is in the same mesh.
800  *
801  * returns:
802  *	2  - if it is a claim packet and on the same group
803  *	1  - if is a claim packet from another group
804  *	0  - if it is not a claim packet
805  */
806 static int batadv_check_claim_group(struct batadv_priv *bat_priv,
807 				    struct batadv_hard_iface *primary_if,
808 				    uint8_t *hw_src, uint8_t *hw_dst,
809 				    struct ethhdr *ethhdr)
810 {
811 	uint8_t *backbone_addr;
812 	struct batadv_orig_node *orig_node;
813 	struct batadv_bla_claim_dst *bla_dst, *bla_dst_own;
814 
815 	bla_dst = (struct batadv_bla_claim_dst *)hw_dst;
816 	bla_dst_own = &bat_priv->bla.claim_dest;
817 
818 	/* if announcement packet, use the source,
819 	 * otherwise assume it is in the hw_src
820 	 */
821 	switch (bla_dst->type) {
822 	case BATADV_CLAIM_TYPE_CLAIM:
823 		backbone_addr = hw_src;
824 		break;
825 	case BATADV_CLAIM_TYPE_REQUEST:
826 	case BATADV_CLAIM_TYPE_ANNOUNCE:
827 	case BATADV_CLAIM_TYPE_UNCLAIM:
828 		backbone_addr = ethhdr->h_source;
829 		break;
830 	default:
831 		return 0;
832 	}
833 
834 	/* don't accept claim frames from ourselves */
835 	if (batadv_compare_eth(backbone_addr, primary_if->net_dev->dev_addr))
836 		return 0;
837 
838 	/* if its already the same group, it is fine. */
839 	if (bla_dst->group == bla_dst_own->group)
840 		return 2;
841 
842 	/* lets see if this originator is in our mesh */
843 	orig_node = batadv_orig_hash_find(bat_priv, backbone_addr);
844 
845 	/* dont accept claims from gateways which are not in
846 	 * the same mesh or group.
847 	 */
848 	if (!orig_node)
849 		return 1;
850 
851 	/* if our mesh friends mac is bigger, use it for ourselves. */
852 	if (ntohs(bla_dst->group) > ntohs(bla_dst_own->group)) {
853 		batadv_dbg(BATADV_DBG_BLA, bat_priv,
854 			   "taking other backbones claim group: %#.4x\n",
855 			   ntohs(bla_dst->group));
856 		bla_dst_own->group = bla_dst->group;
857 	}
858 
859 	batadv_orig_node_free_ref(orig_node);
860 
861 	return 2;
862 }
863 
864 /**
865  * batadv_bla_process_claim
866  * @bat_priv: the bat priv with all the soft interface information
867  * @primary_if: the primary hard interface of this batman soft interface
868  * @skb: the frame to be checked
869  *
870  * Check if this is a claim frame, and process it accordingly.
871  *
872  * returns 1 if it was a claim frame, otherwise return 0 to
873  * tell the callee that it can use the frame on its own.
874  */
875 static int batadv_bla_process_claim(struct batadv_priv *bat_priv,
876 				    struct batadv_hard_iface *primary_if,
877 				    struct sk_buff *skb)
878 {
879 	struct batadv_bla_claim_dst *bla_dst, *bla_dst_own;
880 	uint8_t *hw_src, *hw_dst;
881 	struct vlan_hdr *vhdr, vhdr_buf;
882 	struct ethhdr *ethhdr;
883 	struct arphdr *arphdr;
884 	unsigned short vid;
885 	int vlan_depth = 0;
886 	__be16 proto;
887 	int headlen;
888 	int ret;
889 
890 	vid = batadv_get_vid(skb, 0);
891 	ethhdr = eth_hdr(skb);
892 
893 	proto = ethhdr->h_proto;
894 	headlen = ETH_HLEN;
895 	if (vid & BATADV_VLAN_HAS_TAG) {
896 		/* Traverse the VLAN/Ethertypes.
897 		 *
898 		 * At this point it is known that the first protocol is a VLAN
899 		 * header, so start checking at the encapsulated protocol.
900 		 *
901 		 * The depth of the VLAN headers is recorded to drop BLA claim
902 		 * frames encapsulated into multiple VLAN headers (QinQ).
903 		 */
904 		do {
905 			vhdr = skb_header_pointer(skb, headlen, VLAN_HLEN,
906 						  &vhdr_buf);
907 			if (!vhdr)
908 				return 0;
909 
910 			proto = vhdr->h_vlan_encapsulated_proto;
911 			headlen += VLAN_HLEN;
912 			vlan_depth++;
913 		} while (proto == htons(ETH_P_8021Q));
914 	}
915 
916 	if (proto != htons(ETH_P_ARP))
917 		return 0; /* not a claim frame */
918 
919 	/* this must be a ARP frame. check if it is a claim. */
920 
921 	if (unlikely(!pskb_may_pull(skb, headlen + arp_hdr_len(skb->dev))))
922 		return 0;
923 
924 	/* pskb_may_pull() may have modified the pointers, get ethhdr again */
925 	ethhdr = eth_hdr(skb);
926 	arphdr = (struct arphdr *)((uint8_t *)ethhdr + headlen);
927 
928 	/* Check whether the ARP frame carries a valid
929 	 * IP information
930 	 */
931 	if (arphdr->ar_hrd != htons(ARPHRD_ETHER))
932 		return 0;
933 	if (arphdr->ar_pro != htons(ETH_P_IP))
934 		return 0;
935 	if (arphdr->ar_hln != ETH_ALEN)
936 		return 0;
937 	if (arphdr->ar_pln != 4)
938 		return 0;
939 
940 	hw_src = (uint8_t *)arphdr + sizeof(struct arphdr);
941 	hw_dst = hw_src + ETH_ALEN + 4;
942 	bla_dst = (struct batadv_bla_claim_dst *)hw_dst;
943 	bla_dst_own = &bat_priv->bla.claim_dest;
944 
945 	/* check if it is a claim frame in general */
946 	if (memcmp(bla_dst->magic, bla_dst_own->magic,
947 		   sizeof(bla_dst->magic)) != 0)
948 		return 0;
949 
950 	/* check if there is a claim frame encapsulated deeper in (QinQ) and
951 	 * drop that, as this is not supported by BLA but should also not be
952 	 * sent via the mesh.
953 	 */
954 	if (vlan_depth > 1)
955 		return 1;
956 
957 	/* check if it is a claim frame. */
958 	ret = batadv_check_claim_group(bat_priv, primary_if, hw_src, hw_dst,
959 				       ethhdr);
960 	if (ret == 1)
961 		batadv_dbg(BATADV_DBG_BLA, bat_priv,
962 			   "bla_process_claim(): received a claim frame from another group. From: %pM on vid %d ...(hw_src %pM, hw_dst %pM)\n",
963 			   ethhdr->h_source, BATADV_PRINT_VID(vid), hw_src,
964 			   hw_dst);
965 
966 	if (ret < 2)
967 		return ret;
968 
969 	/* become a backbone gw ourselves on this vlan if not happened yet */
970 	batadv_bla_update_own_backbone_gw(bat_priv, primary_if, vid);
971 
972 	/* check for the different types of claim frames ... */
973 	switch (bla_dst->type) {
974 	case BATADV_CLAIM_TYPE_CLAIM:
975 		if (batadv_handle_claim(bat_priv, primary_if, hw_src,
976 					ethhdr->h_source, vid))
977 			return 1;
978 		break;
979 	case BATADV_CLAIM_TYPE_UNCLAIM:
980 		if (batadv_handle_unclaim(bat_priv, primary_if,
981 					  ethhdr->h_source, hw_src, vid))
982 			return 1;
983 		break;
984 
985 	case BATADV_CLAIM_TYPE_ANNOUNCE:
986 		if (batadv_handle_announce(bat_priv, hw_src, ethhdr->h_source,
987 					   vid))
988 			return 1;
989 		break;
990 	case BATADV_CLAIM_TYPE_REQUEST:
991 		if (batadv_handle_request(bat_priv, primary_if, hw_src, ethhdr,
992 					  vid))
993 			return 1;
994 		break;
995 	}
996 
997 	batadv_dbg(BATADV_DBG_BLA, bat_priv,
998 		   "bla_process_claim(): ERROR - this looks like a claim frame, but is useless. eth src %pM on vid %d ...(hw_src %pM, hw_dst %pM)\n",
999 		   ethhdr->h_source, BATADV_PRINT_VID(vid), hw_src, hw_dst);
1000 	return 1;
1001 }
1002 
1003 /* Check when we last heard from other nodes, and remove them in case of
1004  * a time out, or clean all backbone gws if now is set.
1005  */
1006 static void batadv_bla_purge_backbone_gw(struct batadv_priv *bat_priv, int now)
1007 {
1008 	struct batadv_bla_backbone_gw *backbone_gw;
1009 	struct hlist_node *node_tmp;
1010 	struct hlist_head *head;
1011 	struct batadv_hashtable *hash;
1012 	spinlock_t *list_lock;	/* protects write access to the hash lists */
1013 	int i;
1014 
1015 	hash = bat_priv->bla.backbone_hash;
1016 	if (!hash)
1017 		return;
1018 
1019 	for (i = 0; i < hash->size; i++) {
1020 		head = &hash->table[i];
1021 		list_lock = &hash->list_locks[i];
1022 
1023 		spin_lock_bh(list_lock);
1024 		hlist_for_each_entry_safe(backbone_gw, node_tmp,
1025 					  head, hash_entry) {
1026 			if (now)
1027 				goto purge_now;
1028 			if (!batadv_has_timed_out(backbone_gw->lasttime,
1029 						  BATADV_BLA_BACKBONE_TIMEOUT))
1030 				continue;
1031 
1032 			batadv_dbg(BATADV_DBG_BLA, backbone_gw->bat_priv,
1033 				   "bla_purge_backbone_gw(): backbone gw %pM timed out\n",
1034 				   backbone_gw->orig);
1035 
1036 purge_now:
1037 			/* don't wait for the pending request anymore */
1038 			if (atomic_read(&backbone_gw->request_sent))
1039 				atomic_dec(&bat_priv->bla.num_requests);
1040 
1041 			batadv_bla_del_backbone_claims(backbone_gw);
1042 
1043 			hlist_del_rcu(&backbone_gw->hash_entry);
1044 			batadv_backbone_gw_free_ref(backbone_gw);
1045 		}
1046 		spin_unlock_bh(list_lock);
1047 	}
1048 }
1049 
1050 /**
1051  * batadv_bla_purge_claims
1052  * @bat_priv: the bat priv with all the soft interface information
1053  * @primary_if: the selected primary interface, may be NULL if now is set
1054  * @now: whether the whole hash shall be wiped now
1055  *
1056  * Check when we heard last time from our own claims, and remove them in case of
1057  * a time out, or clean all claims if now is set
1058  */
1059 static void batadv_bla_purge_claims(struct batadv_priv *bat_priv,
1060 				    struct batadv_hard_iface *primary_if,
1061 				    int now)
1062 {
1063 	struct batadv_bla_claim *claim;
1064 	struct hlist_head *head;
1065 	struct batadv_hashtable *hash;
1066 	int i;
1067 
1068 	hash = bat_priv->bla.claim_hash;
1069 	if (!hash)
1070 		return;
1071 
1072 	for (i = 0; i < hash->size; i++) {
1073 		head = &hash->table[i];
1074 
1075 		rcu_read_lock();
1076 		hlist_for_each_entry_rcu(claim, head, hash_entry) {
1077 			if (now)
1078 				goto purge_now;
1079 			if (!batadv_compare_eth(claim->backbone_gw->orig,
1080 						primary_if->net_dev->dev_addr))
1081 				continue;
1082 			if (!batadv_has_timed_out(claim->lasttime,
1083 						  BATADV_BLA_CLAIM_TIMEOUT))
1084 				continue;
1085 
1086 			batadv_dbg(BATADV_DBG_BLA, bat_priv,
1087 				   "bla_purge_claims(): %pM, vid %d, time out\n",
1088 				   claim->addr, claim->vid);
1089 
1090 purge_now:
1091 			batadv_handle_unclaim(bat_priv, primary_if,
1092 					      claim->backbone_gw->orig,
1093 					      claim->addr, claim->vid);
1094 		}
1095 		rcu_read_unlock();
1096 	}
1097 }
1098 
1099 /**
1100  * batadv_bla_update_orig_address
1101  * @bat_priv: the bat priv with all the soft interface information
1102  * @primary_if: the new selected primary_if
1103  * @oldif: the old primary interface, may be NULL
1104  *
1105  * Update the backbone gateways when the own orig address changes.
1106  */
1107 void batadv_bla_update_orig_address(struct batadv_priv *bat_priv,
1108 				    struct batadv_hard_iface *primary_if,
1109 				    struct batadv_hard_iface *oldif)
1110 {
1111 	struct batadv_bla_backbone_gw *backbone_gw;
1112 	struct hlist_head *head;
1113 	struct batadv_hashtable *hash;
1114 	__be16 group;
1115 	int i;
1116 
1117 	/* reset bridge loop avoidance group id */
1118 	group = htons(crc16(0, primary_if->net_dev->dev_addr, ETH_ALEN));
1119 	bat_priv->bla.claim_dest.group = group;
1120 
1121 	/* purge everything when bridge loop avoidance is turned off */
1122 	if (!atomic_read(&bat_priv->bridge_loop_avoidance))
1123 		oldif = NULL;
1124 
1125 	if (!oldif) {
1126 		batadv_bla_purge_claims(bat_priv, NULL, 1);
1127 		batadv_bla_purge_backbone_gw(bat_priv, 1);
1128 		return;
1129 	}
1130 
1131 	hash = bat_priv->bla.backbone_hash;
1132 	if (!hash)
1133 		return;
1134 
1135 	for (i = 0; i < hash->size; i++) {
1136 		head = &hash->table[i];
1137 
1138 		rcu_read_lock();
1139 		hlist_for_each_entry_rcu(backbone_gw, head, hash_entry) {
1140 			/* own orig still holds the old value. */
1141 			if (!batadv_compare_eth(backbone_gw->orig,
1142 						oldif->net_dev->dev_addr))
1143 				continue;
1144 
1145 			ether_addr_copy(backbone_gw->orig,
1146 					primary_if->net_dev->dev_addr);
1147 			/* send an announce frame so others will ask for our
1148 			 * claims and update their tables.
1149 			 */
1150 			batadv_bla_send_announce(bat_priv, backbone_gw);
1151 		}
1152 		rcu_read_unlock();
1153 	}
1154 }
1155 
1156 /* periodic work to do:
1157  *  * purge structures when they are too old
1158  *  * send announcements
1159  */
1160 static void batadv_bla_periodic_work(struct work_struct *work)
1161 {
1162 	struct delayed_work *delayed_work;
1163 	struct batadv_priv *bat_priv;
1164 	struct batadv_priv_bla *priv_bla;
1165 	struct hlist_head *head;
1166 	struct batadv_bla_backbone_gw *backbone_gw;
1167 	struct batadv_hashtable *hash;
1168 	struct batadv_hard_iface *primary_if;
1169 	int i;
1170 
1171 	delayed_work = container_of(work, struct delayed_work, work);
1172 	priv_bla = container_of(delayed_work, struct batadv_priv_bla, work);
1173 	bat_priv = container_of(priv_bla, struct batadv_priv, bla);
1174 	primary_if = batadv_primary_if_get_selected(bat_priv);
1175 	if (!primary_if)
1176 		goto out;
1177 
1178 	batadv_bla_purge_claims(bat_priv, primary_if, 0);
1179 	batadv_bla_purge_backbone_gw(bat_priv, 0);
1180 
1181 	if (!atomic_read(&bat_priv->bridge_loop_avoidance))
1182 		goto out;
1183 
1184 	hash = bat_priv->bla.backbone_hash;
1185 	if (!hash)
1186 		goto out;
1187 
1188 	for (i = 0; i < hash->size; i++) {
1189 		head = &hash->table[i];
1190 
1191 		rcu_read_lock();
1192 		hlist_for_each_entry_rcu(backbone_gw, head, hash_entry) {
1193 			if (!batadv_compare_eth(backbone_gw->orig,
1194 						primary_if->net_dev->dev_addr))
1195 				continue;
1196 
1197 			backbone_gw->lasttime = jiffies;
1198 
1199 			batadv_bla_send_announce(bat_priv, backbone_gw);
1200 
1201 			/* request_sent is only set after creation to avoid
1202 			 * problems when we are not yet known as backbone gw
1203 			 * in the backbone.
1204 			 *
1205 			 * We can reset this now after we waited some periods
1206 			 * to give bridge forward delays and bla group forming
1207 			 * some grace time.
1208 			 */
1209 
1210 			if (atomic_read(&backbone_gw->request_sent) == 0)
1211 				continue;
1212 
1213 			if (!atomic_dec_and_test(&backbone_gw->wait_periods))
1214 				continue;
1215 
1216 			atomic_dec(&backbone_gw->bat_priv->bla.num_requests);
1217 			atomic_set(&backbone_gw->request_sent, 0);
1218 		}
1219 		rcu_read_unlock();
1220 	}
1221 out:
1222 	if (primary_if)
1223 		batadv_hardif_free_ref(primary_if);
1224 
1225 	queue_delayed_work(batadv_event_workqueue, &bat_priv->bla.work,
1226 			   msecs_to_jiffies(BATADV_BLA_PERIOD_LENGTH));
1227 }
1228 
1229 /* The hash for claim and backbone hash receive the same key because they
1230  * are getting initialized by hash_new with the same key. Reinitializing
1231  * them with to different keys to allow nested locking without generating
1232  * lockdep warnings
1233  */
1234 static struct lock_class_key batadv_claim_hash_lock_class_key;
1235 static struct lock_class_key batadv_backbone_hash_lock_class_key;
1236 
1237 /* initialize all bla structures */
1238 int batadv_bla_init(struct batadv_priv *bat_priv)
1239 {
1240 	int i;
1241 	uint8_t claim_dest[ETH_ALEN] = {0xff, 0x43, 0x05, 0x00, 0x00, 0x00};
1242 	struct batadv_hard_iface *primary_if;
1243 	uint16_t crc;
1244 	unsigned long entrytime;
1245 
1246 	spin_lock_init(&bat_priv->bla.bcast_duplist_lock);
1247 
1248 	batadv_dbg(BATADV_DBG_BLA, bat_priv, "bla hash registering\n");
1249 
1250 	/* setting claim destination address */
1251 	memcpy(&bat_priv->bla.claim_dest.magic, claim_dest, 3);
1252 	bat_priv->bla.claim_dest.type = 0;
1253 	primary_if = batadv_primary_if_get_selected(bat_priv);
1254 	if (primary_if) {
1255 		crc = crc16(0, primary_if->net_dev->dev_addr, ETH_ALEN);
1256 		bat_priv->bla.claim_dest.group = htons(crc);
1257 		batadv_hardif_free_ref(primary_if);
1258 	} else {
1259 		bat_priv->bla.claim_dest.group = 0; /* will be set later */
1260 	}
1261 
1262 	/* initialize the duplicate list */
1263 	entrytime = jiffies - msecs_to_jiffies(BATADV_DUPLIST_TIMEOUT);
1264 	for (i = 0; i < BATADV_DUPLIST_SIZE; i++)
1265 		bat_priv->bla.bcast_duplist[i].entrytime = entrytime;
1266 	bat_priv->bla.bcast_duplist_curr = 0;
1267 
1268 	if (bat_priv->bla.claim_hash)
1269 		return 0;
1270 
1271 	bat_priv->bla.claim_hash = batadv_hash_new(128);
1272 	bat_priv->bla.backbone_hash = batadv_hash_new(32);
1273 
1274 	if (!bat_priv->bla.claim_hash || !bat_priv->bla.backbone_hash)
1275 		return -ENOMEM;
1276 
1277 	batadv_hash_set_lock_class(bat_priv->bla.claim_hash,
1278 				   &batadv_claim_hash_lock_class_key);
1279 	batadv_hash_set_lock_class(bat_priv->bla.backbone_hash,
1280 				   &batadv_backbone_hash_lock_class_key);
1281 
1282 	batadv_dbg(BATADV_DBG_BLA, bat_priv, "bla hashes initialized\n");
1283 
1284 	INIT_DELAYED_WORK(&bat_priv->bla.work, batadv_bla_periodic_work);
1285 
1286 	queue_delayed_work(batadv_event_workqueue, &bat_priv->bla.work,
1287 			   msecs_to_jiffies(BATADV_BLA_PERIOD_LENGTH));
1288 	return 0;
1289 }
1290 
1291 /**
1292  * batadv_bla_check_bcast_duplist
1293  * @bat_priv: the bat priv with all the soft interface information
1294  * @skb: contains the bcast_packet to be checked
1295  *
1296  * check if it is on our broadcast list. Another gateway might
1297  * have sent the same packet because it is connected to the same backbone,
1298  * so we have to remove this duplicate.
1299  *
1300  * This is performed by checking the CRC, which will tell us
1301  * with a good chance that it is the same packet. If it is furthermore
1302  * sent by another host, drop it. We allow equal packets from
1303  * the same host however as this might be intended.
1304  */
1305 int batadv_bla_check_bcast_duplist(struct batadv_priv *bat_priv,
1306 				   struct sk_buff *skb)
1307 {
1308 	int i, curr, ret = 0;
1309 	__be32 crc;
1310 	struct batadv_bcast_packet *bcast_packet;
1311 	struct batadv_bcast_duplist_entry *entry;
1312 
1313 	bcast_packet = (struct batadv_bcast_packet *)skb->data;
1314 
1315 	/* calculate the crc ... */
1316 	crc = batadv_skb_crc32(skb, (u8 *)(bcast_packet + 1));
1317 
1318 	spin_lock_bh(&bat_priv->bla.bcast_duplist_lock);
1319 
1320 	for (i = 0; i < BATADV_DUPLIST_SIZE; i++) {
1321 		curr = (bat_priv->bla.bcast_duplist_curr + i);
1322 		curr %= BATADV_DUPLIST_SIZE;
1323 		entry = &bat_priv->bla.bcast_duplist[curr];
1324 
1325 		/* we can stop searching if the entry is too old ;
1326 		 * later entries will be even older
1327 		 */
1328 		if (batadv_has_timed_out(entry->entrytime,
1329 					 BATADV_DUPLIST_TIMEOUT))
1330 			break;
1331 
1332 		if (entry->crc != crc)
1333 			continue;
1334 
1335 		if (batadv_compare_eth(entry->orig, bcast_packet->orig))
1336 			continue;
1337 
1338 		/* this entry seems to match: same crc, not too old,
1339 		 * and from another gw. therefore return 1 to forbid it.
1340 		 */
1341 		ret = 1;
1342 		goto out;
1343 	}
1344 	/* not found, add a new entry (overwrite the oldest entry)
1345 	 * and allow it, its the first occurrence.
1346 	 */
1347 	curr = (bat_priv->bla.bcast_duplist_curr + BATADV_DUPLIST_SIZE - 1);
1348 	curr %= BATADV_DUPLIST_SIZE;
1349 	entry = &bat_priv->bla.bcast_duplist[curr];
1350 	entry->crc = crc;
1351 	entry->entrytime = jiffies;
1352 	ether_addr_copy(entry->orig, bcast_packet->orig);
1353 	bat_priv->bla.bcast_duplist_curr = curr;
1354 
1355 out:
1356 	spin_unlock_bh(&bat_priv->bla.bcast_duplist_lock);
1357 
1358 	return ret;
1359 }
1360 
1361 /**
1362  * batadv_bla_is_backbone_gw_orig
1363  * @bat_priv: the bat priv with all the soft interface information
1364  * @orig: originator mac address
1365  * @vid: VLAN identifier
1366  *
1367  * Check if the originator is a gateway for the VLAN identified by vid.
1368  *
1369  * Returns true if orig is a backbone for this vid, false otherwise.
1370  */
1371 bool batadv_bla_is_backbone_gw_orig(struct batadv_priv *bat_priv, uint8_t *orig,
1372 				    unsigned short vid)
1373 {
1374 	struct batadv_hashtable *hash = bat_priv->bla.backbone_hash;
1375 	struct hlist_head *head;
1376 	struct batadv_bla_backbone_gw *backbone_gw;
1377 	int i;
1378 
1379 	if (!atomic_read(&bat_priv->bridge_loop_avoidance))
1380 		return false;
1381 
1382 	if (!hash)
1383 		return false;
1384 
1385 	for (i = 0; i < hash->size; i++) {
1386 		head = &hash->table[i];
1387 
1388 		rcu_read_lock();
1389 		hlist_for_each_entry_rcu(backbone_gw, head, hash_entry) {
1390 			if (batadv_compare_eth(backbone_gw->orig, orig) &&
1391 			    backbone_gw->vid == vid) {
1392 				rcu_read_unlock();
1393 				return true;
1394 			}
1395 		}
1396 		rcu_read_unlock();
1397 	}
1398 
1399 	return false;
1400 }
1401 
1402 /**
1403  * batadv_bla_is_backbone_gw
1404  * @skb: the frame to be checked
1405  * @orig_node: the orig_node of the frame
1406  * @hdr_size: maximum length of the frame
1407  *
1408  * bla_is_backbone_gw inspects the skb for the VLAN ID and returns 1
1409  * if the orig_node is also a gateway on the soft interface, otherwise it
1410  * returns 0.
1411  */
1412 int batadv_bla_is_backbone_gw(struct sk_buff *skb,
1413 			      struct batadv_orig_node *orig_node, int hdr_size)
1414 {
1415 	struct batadv_bla_backbone_gw *backbone_gw;
1416 	unsigned short vid;
1417 
1418 	if (!atomic_read(&orig_node->bat_priv->bridge_loop_avoidance))
1419 		return 0;
1420 
1421 	/* first, find out the vid. */
1422 	if (!pskb_may_pull(skb, hdr_size + ETH_HLEN))
1423 		return 0;
1424 
1425 	vid = batadv_get_vid(skb, hdr_size);
1426 
1427 	/* see if this originator is a backbone gw for this VLAN */
1428 	backbone_gw = batadv_backbone_hash_find(orig_node->bat_priv,
1429 						orig_node->orig, vid);
1430 	if (!backbone_gw)
1431 		return 0;
1432 
1433 	batadv_backbone_gw_free_ref(backbone_gw);
1434 	return 1;
1435 }
1436 
1437 /* free all bla structures (for softinterface free or module unload) */
1438 void batadv_bla_free(struct batadv_priv *bat_priv)
1439 {
1440 	struct batadv_hard_iface *primary_if;
1441 
1442 	cancel_delayed_work_sync(&bat_priv->bla.work);
1443 	primary_if = batadv_primary_if_get_selected(bat_priv);
1444 
1445 	if (bat_priv->bla.claim_hash) {
1446 		batadv_bla_purge_claims(bat_priv, primary_if, 1);
1447 		batadv_hash_destroy(bat_priv->bla.claim_hash);
1448 		bat_priv->bla.claim_hash = NULL;
1449 	}
1450 	if (bat_priv->bla.backbone_hash) {
1451 		batadv_bla_purge_backbone_gw(bat_priv, 1);
1452 		batadv_hash_destroy(bat_priv->bla.backbone_hash);
1453 		bat_priv->bla.backbone_hash = NULL;
1454 	}
1455 	if (primary_if)
1456 		batadv_hardif_free_ref(primary_if);
1457 }
1458 
1459 /**
1460  * batadv_bla_rx
1461  * @bat_priv: the bat priv with all the soft interface information
1462  * @skb: the frame to be checked
1463  * @vid: the VLAN ID of the frame
1464  * @is_bcast: the packet came in a broadcast packet type.
1465  *
1466  * bla_rx avoidance checks if:
1467  *  * we have to race for a claim
1468  *  * if the frame is allowed on the LAN
1469  *
1470  * in these cases, the skb is further handled by this function and
1471  * returns 1, otherwise it returns 0 and the caller shall further
1472  * process the skb.
1473  */
1474 int batadv_bla_rx(struct batadv_priv *bat_priv, struct sk_buff *skb,
1475 		  unsigned short vid, bool is_bcast)
1476 {
1477 	struct ethhdr *ethhdr;
1478 	struct batadv_bla_claim search_claim, *claim = NULL;
1479 	struct batadv_hard_iface *primary_if;
1480 	int ret;
1481 
1482 	ethhdr = eth_hdr(skb);
1483 
1484 	primary_if = batadv_primary_if_get_selected(bat_priv);
1485 	if (!primary_if)
1486 		goto handled;
1487 
1488 	if (!atomic_read(&bat_priv->bridge_loop_avoidance))
1489 		goto allow;
1490 
1491 	if (unlikely(atomic_read(&bat_priv->bla.num_requests)))
1492 		/* don't allow broadcasts while requests are in flight */
1493 		if (is_multicast_ether_addr(ethhdr->h_dest) && is_bcast)
1494 			goto handled;
1495 
1496 	ether_addr_copy(search_claim.addr, ethhdr->h_source);
1497 	search_claim.vid = vid;
1498 	claim = batadv_claim_hash_find(bat_priv, &search_claim);
1499 
1500 	if (!claim) {
1501 		/* possible optimization: race for a claim */
1502 		/* No claim exists yet, claim it for us!
1503 		 */
1504 		batadv_handle_claim(bat_priv, primary_if,
1505 				    primary_if->net_dev->dev_addr,
1506 				    ethhdr->h_source, vid);
1507 		goto allow;
1508 	}
1509 
1510 	/* if it is our own claim ... */
1511 	if (batadv_compare_eth(claim->backbone_gw->orig,
1512 			       primary_if->net_dev->dev_addr)) {
1513 		/* ... allow it in any case */
1514 		claim->lasttime = jiffies;
1515 		goto allow;
1516 	}
1517 
1518 	/* if it is a broadcast ... */
1519 	if (is_multicast_ether_addr(ethhdr->h_dest) && is_bcast) {
1520 		/* ... drop it. the responsible gateway is in charge.
1521 		 *
1522 		 * We need to check is_bcast because with the gateway
1523 		 * feature, broadcasts (like DHCP requests) may be sent
1524 		 * using a unicast packet type.
1525 		 */
1526 		goto handled;
1527 	} else {
1528 		/* seems the client considers us as its best gateway.
1529 		 * send a claim and update the claim table
1530 		 * immediately.
1531 		 */
1532 		batadv_handle_claim(bat_priv, primary_if,
1533 				    primary_if->net_dev->dev_addr,
1534 				    ethhdr->h_source, vid);
1535 		goto allow;
1536 	}
1537 allow:
1538 	batadv_bla_update_own_backbone_gw(bat_priv, primary_if, vid);
1539 	ret = 0;
1540 	goto out;
1541 
1542 handled:
1543 	kfree_skb(skb);
1544 	ret = 1;
1545 
1546 out:
1547 	if (primary_if)
1548 		batadv_hardif_free_ref(primary_if);
1549 	if (claim)
1550 		batadv_claim_free_ref(claim);
1551 	return ret;
1552 }
1553 
1554 /**
1555  * batadv_bla_tx
1556  * @bat_priv: the bat priv with all the soft interface information
1557  * @skb: the frame to be checked
1558  * @vid: the VLAN ID of the frame
1559  *
1560  * bla_tx checks if:
1561  *  * a claim was received which has to be processed
1562  *  * the frame is allowed on the mesh
1563  *
1564  * in these cases, the skb is further handled by this function and
1565  * returns 1, otherwise it returns 0 and the caller shall further
1566  * process the skb.
1567  *
1568  * This call might reallocate skb data.
1569  */
1570 int batadv_bla_tx(struct batadv_priv *bat_priv, struct sk_buff *skb,
1571 		  unsigned short vid)
1572 {
1573 	struct ethhdr *ethhdr;
1574 	struct batadv_bla_claim search_claim, *claim = NULL;
1575 	struct batadv_hard_iface *primary_if;
1576 	int ret = 0;
1577 
1578 	primary_if = batadv_primary_if_get_selected(bat_priv);
1579 	if (!primary_if)
1580 		goto out;
1581 
1582 	if (!atomic_read(&bat_priv->bridge_loop_avoidance))
1583 		goto allow;
1584 
1585 	if (batadv_bla_process_claim(bat_priv, primary_if, skb))
1586 		goto handled;
1587 
1588 	ethhdr = eth_hdr(skb);
1589 
1590 	if (unlikely(atomic_read(&bat_priv->bla.num_requests)))
1591 		/* don't allow broadcasts while requests are in flight */
1592 		if (is_multicast_ether_addr(ethhdr->h_dest))
1593 			goto handled;
1594 
1595 	ether_addr_copy(search_claim.addr, ethhdr->h_source);
1596 	search_claim.vid = vid;
1597 
1598 	claim = batadv_claim_hash_find(bat_priv, &search_claim);
1599 
1600 	/* if no claim exists, allow it. */
1601 	if (!claim)
1602 		goto allow;
1603 
1604 	/* check if we are responsible. */
1605 	if (batadv_compare_eth(claim->backbone_gw->orig,
1606 			       primary_if->net_dev->dev_addr)) {
1607 		/* if yes, the client has roamed and we have
1608 		 * to unclaim it.
1609 		 */
1610 		batadv_handle_unclaim(bat_priv, primary_if,
1611 				      primary_if->net_dev->dev_addr,
1612 				      ethhdr->h_source, vid);
1613 		goto allow;
1614 	}
1615 
1616 	/* check if it is a multicast/broadcast frame */
1617 	if (is_multicast_ether_addr(ethhdr->h_dest)) {
1618 		/* drop it. the responsible gateway has forwarded it into
1619 		 * the backbone network.
1620 		 */
1621 		goto handled;
1622 	} else {
1623 		/* we must allow it. at least if we are
1624 		 * responsible for the DESTINATION.
1625 		 */
1626 		goto allow;
1627 	}
1628 allow:
1629 	batadv_bla_update_own_backbone_gw(bat_priv, primary_if, vid);
1630 	ret = 0;
1631 	goto out;
1632 handled:
1633 	ret = 1;
1634 out:
1635 	if (primary_if)
1636 		batadv_hardif_free_ref(primary_if);
1637 	if (claim)
1638 		batadv_claim_free_ref(claim);
1639 	return ret;
1640 }
1641 
1642 int batadv_bla_claim_table_seq_print_text(struct seq_file *seq, void *offset)
1643 {
1644 	struct net_device *net_dev = (struct net_device *)seq->private;
1645 	struct batadv_priv *bat_priv = netdev_priv(net_dev);
1646 	struct batadv_hashtable *hash = bat_priv->bla.claim_hash;
1647 	struct batadv_bla_claim *claim;
1648 	struct batadv_hard_iface *primary_if;
1649 	struct hlist_head *head;
1650 	uint32_t i;
1651 	bool is_own;
1652 	uint8_t *primary_addr;
1653 
1654 	primary_if = batadv_seq_print_text_primary_if_get(seq);
1655 	if (!primary_if)
1656 		goto out;
1657 
1658 	primary_addr = primary_if->net_dev->dev_addr;
1659 	seq_printf(seq,
1660 		   "Claims announced for the mesh %s (orig %pM, group id %#.4x)\n",
1661 		   net_dev->name, primary_addr,
1662 		   ntohs(bat_priv->bla.claim_dest.group));
1663 	seq_printf(seq, "   %-17s    %-5s    %-17s [o] (%-6s)\n",
1664 		   "Client", "VID", "Originator", "CRC");
1665 	for (i = 0; i < hash->size; i++) {
1666 		head = &hash->table[i];
1667 
1668 		rcu_read_lock();
1669 		hlist_for_each_entry_rcu(claim, head, hash_entry) {
1670 			is_own = batadv_compare_eth(claim->backbone_gw->orig,
1671 						    primary_addr);
1672 			seq_printf(seq, " * %pM on %5d by %pM [%c] (%#.4x)\n",
1673 				   claim->addr, BATADV_PRINT_VID(claim->vid),
1674 				   claim->backbone_gw->orig,
1675 				   (is_own ? 'x' : ' '),
1676 				   claim->backbone_gw->crc);
1677 		}
1678 		rcu_read_unlock();
1679 	}
1680 out:
1681 	if (primary_if)
1682 		batadv_hardif_free_ref(primary_if);
1683 	return 0;
1684 }
1685 
1686 int batadv_bla_backbone_table_seq_print_text(struct seq_file *seq, void *offset)
1687 {
1688 	struct net_device *net_dev = (struct net_device *)seq->private;
1689 	struct batadv_priv *bat_priv = netdev_priv(net_dev);
1690 	struct batadv_hashtable *hash = bat_priv->bla.backbone_hash;
1691 	struct batadv_bla_backbone_gw *backbone_gw;
1692 	struct batadv_hard_iface *primary_if;
1693 	struct hlist_head *head;
1694 	int secs, msecs;
1695 	uint32_t i;
1696 	bool is_own;
1697 	uint8_t *primary_addr;
1698 
1699 	primary_if = batadv_seq_print_text_primary_if_get(seq);
1700 	if (!primary_if)
1701 		goto out;
1702 
1703 	primary_addr = primary_if->net_dev->dev_addr;
1704 	seq_printf(seq,
1705 		   "Backbones announced for the mesh %s (orig %pM, group id %#.4x)\n",
1706 		   net_dev->name, primary_addr,
1707 		   ntohs(bat_priv->bla.claim_dest.group));
1708 	seq_printf(seq, "   %-17s    %-5s %-9s (%-6s)\n",
1709 		   "Originator", "VID", "last seen", "CRC");
1710 	for (i = 0; i < hash->size; i++) {
1711 		head = &hash->table[i];
1712 
1713 		rcu_read_lock();
1714 		hlist_for_each_entry_rcu(backbone_gw, head, hash_entry) {
1715 			msecs = jiffies_to_msecs(jiffies -
1716 						 backbone_gw->lasttime);
1717 			secs = msecs / 1000;
1718 			msecs = msecs % 1000;
1719 
1720 			is_own = batadv_compare_eth(backbone_gw->orig,
1721 						    primary_addr);
1722 			if (is_own)
1723 				continue;
1724 
1725 			seq_printf(seq, " * %pM on %5d %4i.%03is (%#.4x)\n",
1726 				   backbone_gw->orig,
1727 				   BATADV_PRINT_VID(backbone_gw->vid), secs,
1728 				   msecs, backbone_gw->crc);
1729 		}
1730 		rcu_read_unlock();
1731 	}
1732 out:
1733 	if (primary_if)
1734 		batadv_hardif_free_ref(primary_if);
1735 	return 0;
1736 }
1737