projects / GitHub / mt8127 / android_kernel_alcatel_ttab.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
batman-adv: Replace bitarray operations with bitmap
[GitHub/mt8127/android_kernel_alcatel_ttab.git] / net / batman-adv / bat_iv_ogm.c
1 /*
2 * Copyright (C) 2007-2012 B.A.T.M.A.N. contributors:
3 *
4 * Marek Lindner, Simon Wunderlich
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of version 2 of the GNU General Public
8 * License as published by the Free Software Foundation.
9 *
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
18 * 02110-1301, USA
19 *
20 */
21
22 #include "main.h"
23 #include "translation-table.h"
24 #include "ring_buffer.h"
25 #include "originator.h"
26 #include "routing.h"
27 #include "gateway_common.h"
28 #include "gateway_client.h"
29 #include "hard-interface.h"
30 #include "send.h"
31 #include "bat_algo.h"
32
33 static void bat_iv_ogm_init(struct hard_iface *hard_iface)
34 {
35 struct batman_ogm_packet *batman_ogm_packet;
36
37 hard_iface->packet_len = BATMAN_OGM_LEN;
38 hard_iface->packet_buff = kmalloc(hard_iface->packet_len, GFP_ATOMIC);
39
40 batman_ogm_packet = (struct batman_ogm_packet *)hard_iface->packet_buff;
41 batman_ogm_packet->header.packet_type = BAT_OGM;
42 batman_ogm_packet->header.version = COMPAT_VERSION;
43 batman_ogm_packet->header.ttl = 2;
44 batman_ogm_packet->flags = NO_FLAGS;
45 batman_ogm_packet->tq = TQ_MAX_VALUE;
46 batman_ogm_packet->tt_num_changes = 0;
47 batman_ogm_packet->ttvn = 0;
48 }
49
50 static void bat_iv_ogm_init_primary(struct hard_iface *hard_iface)
51 {
52 struct batman_ogm_packet *batman_ogm_packet;
53
54 batman_ogm_packet = (struct batman_ogm_packet *)hard_iface->packet_buff;
55 batman_ogm_packet->flags = PRIMARIES_FIRST_HOP;
56 batman_ogm_packet->header.ttl = TTL;
57 }
58
59 static void bat_iv_ogm_update_mac(struct hard_iface *hard_iface)
60 {
61 struct batman_ogm_packet *batman_ogm_packet;
62
63 batman_ogm_packet = (struct batman_ogm_packet *)hard_iface->packet_buff;
64 memcpy(batman_ogm_packet->orig,
65 hard_iface->net_dev->dev_addr, ETH_ALEN);
66 memcpy(batman_ogm_packet->prev_sender,
67 hard_iface->net_dev->dev_addr, ETH_ALEN);
68 }
69
70 /* when do we schedule our own ogm to be sent */
71 static unsigned long bat_iv_ogm_emit_send_time(const struct bat_priv *bat_priv)
72 {
73 return jiffies + msecs_to_jiffies(
74 atomic_read(&bat_priv->orig_interval) -
75 JITTER + (random32() % 2*JITTER));
76 }
77
78 /* when do we schedule a ogm packet to be sent */
79 static unsigned long bat_iv_ogm_fwd_send_time(void)
80 {
81 return jiffies + msecs_to_jiffies(random32() % (JITTER/2));
82 }
83
84 /* apply hop penalty for a normal link */
85 static uint8_t hop_penalty(uint8_t tq, const struct bat_priv *bat_priv)
86 {
87 int hop_penalty = atomic_read(&bat_priv->hop_penalty);
88 return (tq * (TQ_MAX_VALUE - hop_penalty)) / (TQ_MAX_VALUE);
89 }
90
91 /* is there another aggregated packet here? */
92 static int bat_iv_ogm_aggr_packet(int buff_pos, int packet_len,
93 int tt_num_changes)
94 {
95 int next_buff_pos = buff_pos + BATMAN_OGM_LEN + tt_len(tt_num_changes);
96
97 return (next_buff_pos <= packet_len) &&
98 (next_buff_pos <= MAX_AGGREGATION_BYTES);
99 }
100
101 /* send a batman ogm to a given interface */
102 static void bat_iv_ogm_send_to_if(struct forw_packet *forw_packet,
103 struct hard_iface *hard_iface)
104 {
105 struct bat_priv *bat_priv = netdev_priv(hard_iface->soft_iface);
106 char *fwd_str;
107 uint8_t packet_num;
108 int16_t buff_pos;
109 struct batman_ogm_packet *batman_ogm_packet;
110 struct sk_buff *skb;
111
112 if (hard_iface->if_status != IF_ACTIVE)
113 return;
114
115 packet_num = 0;
116 buff_pos = 0;
117 batman_ogm_packet = (struct batman_ogm_packet *)forw_packet->skb->data;
118
119 /* adjust all flags and log packets */
120 while (bat_iv_ogm_aggr_packet(buff_pos, forw_packet->packet_len,
121 batman_ogm_packet->tt_num_changes)) {
122
123 /* we might have aggregated direct link packets with an
124 * ordinary base packet */
125 if ((forw_packet->direct_link_flags & (1 << packet_num)) &&
126 (forw_packet->if_incoming == hard_iface))
127 batman_ogm_packet->flags |= DIRECTLINK;
128 else
129 batman_ogm_packet->flags &= ~DIRECTLINK;
130
131 fwd_str = (packet_num > 0 ? "Forwarding" : (forw_packet->own ?
132 "Sending own" :
133 "Forwarding"));
134 bat_dbg(DBG_BATMAN, bat_priv,
135 "%s %spacket (originator %pM, seqno %d, TQ %d, TTL %d, IDF %s, ttvn %d) on interface %s [%pM]\n",
136 fwd_str, (packet_num > 0 ? "aggregated " : ""),
137 batman_ogm_packet->orig,
138 ntohl(batman_ogm_packet->seqno),
139 batman_ogm_packet->tq, batman_ogm_packet->header.ttl,
140 (batman_ogm_packet->flags & DIRECTLINK ?
141 "on" : "off"),
142 batman_ogm_packet->ttvn, hard_iface->net_dev->name,
143 hard_iface->net_dev->dev_addr);
144
145 buff_pos += BATMAN_OGM_LEN +
146 tt_len(batman_ogm_packet->tt_num_changes);
147 packet_num++;
148 batman_ogm_packet = (struct batman_ogm_packet *)
149 (forw_packet->skb->data + buff_pos);
150 }
151
152 /* create clone because function is called more than once */
153 skb = skb_clone(forw_packet->skb, GFP_ATOMIC);
154 if (skb)
155 send_skb_packet(skb, hard_iface, broadcast_addr);
156 }
157
158 /* send a batman ogm packet */
159 static void bat_iv_ogm_emit(struct forw_packet *forw_packet)
160 {
161 struct hard_iface *hard_iface;
162 struct net_device *soft_iface;
163 struct bat_priv *bat_priv;
164 struct hard_iface *primary_if = NULL;
165 struct batman_ogm_packet *batman_ogm_packet;
166 unsigned char directlink;
167
168 batman_ogm_packet = (struct batman_ogm_packet *)
169 (forw_packet->skb->data);
170 directlink = (batman_ogm_packet->flags & DIRECTLINK ? 1 : 0);
171
172 if (!forw_packet->if_incoming) {
173 pr_err("Error - can't forward packet: incoming iface not specified\n");
174 goto out;
175 }
176
177 soft_iface = forw_packet->if_incoming->soft_iface;
178 bat_priv = netdev_priv(soft_iface);
179
180 if (forw_packet->if_incoming->if_status != IF_ACTIVE)
181 goto out;
182
183 primary_if = primary_if_get_selected(bat_priv);
184 if (!primary_if)
185 goto out;
186
187 /* multihomed peer assumed */
188 /* non-primary OGMs are only broadcasted on their interface */
189 if ((directlink && (batman_ogm_packet->header.ttl == 1)) ||
190 (forw_packet->own && (forw_packet->if_incoming != primary_if))) {
191
192 /* FIXME: what about aggregated packets ? */
193 bat_dbg(DBG_BATMAN, bat_priv,
194 "%s packet (originator %pM, seqno %d, TTL %d) on interface %s [%pM]\n",
195 (forw_packet->own ? "Sending own" : "Forwarding"),
196 batman_ogm_packet->orig,
197 ntohl(batman_ogm_packet->seqno),
198 batman_ogm_packet->header.ttl,
199 forw_packet->if_incoming->net_dev->name,
200 forw_packet->if_incoming->net_dev->dev_addr);
201
202 /* skb is only used once and than forw_packet is free'd */
203 send_skb_packet(forw_packet->skb, forw_packet->if_incoming,
204 broadcast_addr);
205 forw_packet->skb = NULL;
206
207 goto out;
208 }
209
210 /* broadcast on every interface */
211 rcu_read_lock();
212 list_for_each_entry_rcu(hard_iface, &hardif_list, list) {
213 if (hard_iface->soft_iface != soft_iface)
214 continue;
215
216 bat_iv_ogm_send_to_if(forw_packet, hard_iface);
217 }
218 rcu_read_unlock();
219
220 out:
221 if (primary_if)
222 hardif_free_ref(primary_if);
223 }
224
225 /* return true if new_packet can be aggregated with forw_packet */
226 static bool bat_iv_ogm_can_aggregate(const struct batman_ogm_packet
227 *new_batman_ogm_packet,
228 struct bat_priv *bat_priv,
229 int packet_len, unsigned long send_time,
230 bool directlink,
231 const struct hard_iface *if_incoming,
232 const struct forw_packet *forw_packet)
233 {
234 struct batman_ogm_packet *batman_ogm_packet;
235 int aggregated_bytes = forw_packet->packet_len + packet_len;
236 struct hard_iface *primary_if = NULL;
237 bool res = false;
238
239 batman_ogm_packet = (struct batman_ogm_packet *)forw_packet->skb->data;
240
241 /**
242 * we can aggregate the current packet to this aggregated packet
243 * if:
244 *
245 * - the send time is within our MAX_AGGREGATION_MS time
246 * - the resulting packet wont be bigger than
247 * MAX_AGGREGATION_BYTES
248 */
249
250 if (time_before(send_time, forw_packet->send_time) &&
251 time_after_eq(send_time + msecs_to_jiffies(MAX_AGGREGATION_MS),
252 forw_packet->send_time) &&
253 (aggregated_bytes <= MAX_AGGREGATION_BYTES)) {
254
255 /**
256 * check aggregation compatibility
257 * -> direct link packets are broadcasted on
258 * their interface only
259 * -> aggregate packet if the current packet is
260 * a "global" packet as well as the base
261 * packet
262 */
263
264 primary_if = primary_if_get_selected(bat_priv);
265 if (!primary_if)
266 goto out;
267
268 /* packets without direct link flag and high TTL
269 * are flooded through the net */
270 if ((!directlink) &&
271 (!(batman_ogm_packet->flags & DIRECTLINK)) &&
272 (batman_ogm_packet->header.ttl != 1) &&
273
274 /* own packets originating non-primary
275 * interfaces leave only that interface */
276 ((!forw_packet->own) ||
277 (forw_packet->if_incoming == primary_if))) {
278 res = true;
279 goto out;
280 }
281
282 /* if the incoming packet is sent via this one
283 * interface only - we still can aggregate */
284 if ((directlink) &&
285 (new_batman_ogm_packet->header.ttl == 1) &&
286 (forw_packet->if_incoming == if_incoming) &&
287
288 /* packets from direct neighbors or
289 * own secondary interface packets
290 * (= secondary interface packets in general) */
291 (batman_ogm_packet->flags & DIRECTLINK ||
292 (forw_packet->own &&
293 forw_packet->if_incoming != primary_if))) {
294 res = true;
295 goto out;
296 }
297 }
298
299 out:
300 if (primary_if)
301 hardif_free_ref(primary_if);
302 return res;
303 }
304
305 /* create a new aggregated packet and add this packet to it */
306 static void bat_iv_ogm_aggregate_new(const unsigned char *packet_buff,
307 int packet_len, unsigned long send_time,
308 bool direct_link,
309 struct hard_iface *if_incoming,
310 int own_packet)
311 {
312 struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
313 struct forw_packet *forw_packet_aggr;
314 unsigned char *skb_buff;
315
316 if (!atomic_inc_not_zero(&if_incoming->refcount))
317 return;
318
319 /* own packet should always be scheduled */
320 if (!own_packet) {
321 if (!atomic_dec_not_zero(&bat_priv->batman_queue_left)) {
322 bat_dbg(DBG_BATMAN, bat_priv,
323 "batman packet queue full\n");
324 goto out;
325 }
326 }
327
328 forw_packet_aggr = kmalloc(sizeof(*forw_packet_aggr), GFP_ATOMIC);
329 if (!forw_packet_aggr) {
330 if (!own_packet)
331 atomic_inc(&bat_priv->batman_queue_left);
332 goto out;
333 }
334
335 if ((atomic_read(&bat_priv->aggregated_ogms)) &&
336 (packet_len < MAX_AGGREGATION_BYTES))
337 forw_packet_aggr->skb = dev_alloc_skb(MAX_AGGREGATION_BYTES +
338 sizeof(struct ethhdr));
339 else
340 forw_packet_aggr->skb = dev_alloc_skb(packet_len +
341 sizeof(struct ethhdr));
342
343 if (!forw_packet_aggr->skb) {
344 if (!own_packet)
345 atomic_inc(&bat_priv->batman_queue_left);
346 kfree(forw_packet_aggr);
347 goto out;
348 }
349 skb_reserve(forw_packet_aggr->skb, sizeof(struct ethhdr));
350
351 INIT_HLIST_NODE(&forw_packet_aggr->list);
352
353 skb_buff = skb_put(forw_packet_aggr->skb, packet_len);
354 forw_packet_aggr->packet_len = packet_len;
355 memcpy(skb_buff, packet_buff, packet_len);
356
357 forw_packet_aggr->own = own_packet;
358 forw_packet_aggr->if_incoming = if_incoming;
359 forw_packet_aggr->num_packets = 0;
360 forw_packet_aggr->direct_link_flags = NO_FLAGS;
361 forw_packet_aggr->send_time = send_time;
362
363 /* save packet direct link flag status */
364 if (direct_link)
365 forw_packet_aggr->direct_link_flags |= 1;
366
367 /* add new packet to packet list */
368 spin_lock_bh(&bat_priv->forw_bat_list_lock);
369 hlist_add_head(&forw_packet_aggr->list, &bat_priv->forw_bat_list);
370 spin_unlock_bh(&bat_priv->forw_bat_list_lock);
371
372 /* start timer for this packet */
373 INIT_DELAYED_WORK(&forw_packet_aggr->delayed_work,
374 send_outstanding_bat_ogm_packet);
375 queue_delayed_work(bat_event_workqueue,
376 &forw_packet_aggr->delayed_work,
377 send_time - jiffies);
378
379 return;
380 out:
381 hardif_free_ref(if_incoming);
382 }
383
384 /* aggregate a new packet into the existing ogm packet */
385 static void bat_iv_ogm_aggregate(struct forw_packet *forw_packet_aggr,
386 const unsigned char *packet_buff,
387 int packet_len, bool direct_link)
388 {
389 unsigned char *skb_buff;
390
391 skb_buff = skb_put(forw_packet_aggr->skb, packet_len);
392 memcpy(skb_buff, packet_buff, packet_len);
393 forw_packet_aggr->packet_len += packet_len;
394 forw_packet_aggr->num_packets++;
395
396 /* save packet direct link flag status */
397 if (direct_link)
398 forw_packet_aggr->direct_link_flags |=
399 (1 << forw_packet_aggr->num_packets);
400 }
401
402 static void bat_iv_ogm_queue_add(struct bat_priv *bat_priv,
403 unsigned char *packet_buff,
404 int packet_len, struct hard_iface *if_incoming,
405 int own_packet, unsigned long send_time)
406 {
407 /**
408 * _aggr -> pointer to the packet we want to aggregate with
409 * _pos -> pointer to the position in the queue
410 */
411 struct forw_packet *forw_packet_aggr = NULL, *forw_packet_pos = NULL;
412 struct hlist_node *tmp_node;
413 struct batman_ogm_packet *batman_ogm_packet;
414 bool direct_link;
415
416 batman_ogm_packet = (struct batman_ogm_packet *)packet_buff;
417 direct_link = batman_ogm_packet->flags & DIRECTLINK ? 1 : 0;
418
419 /* find position for the packet in the forward queue */
420 spin_lock_bh(&bat_priv->forw_bat_list_lock);
421 /* own packets are not to be aggregated */
422 if ((atomic_read(&bat_priv->aggregated_ogms)) && (!own_packet)) {
423 hlist_for_each_entry(forw_packet_pos, tmp_node,
424 &bat_priv->forw_bat_list, list) {
425 if (bat_iv_ogm_can_aggregate(batman_ogm_packet,
426 bat_priv, packet_len,
427 send_time, direct_link,
428 if_incoming,
429 forw_packet_pos)) {
430 forw_packet_aggr = forw_packet_pos;
431 break;
432 }
433 }
434 }
435
436 /* nothing to aggregate with - either aggregation disabled or no
437 * suitable aggregation packet found */
438 if (!forw_packet_aggr) {
439 /* the following section can run without the lock */
440 spin_unlock_bh(&bat_priv->forw_bat_list_lock);
441
442 /**
443 * if we could not aggregate this packet with one of the others
444 * we hold it back for a while, so that it might be aggregated
445 * later on
446 */
447 if ((!own_packet) &&
448 (atomic_read(&bat_priv->aggregated_ogms)))
449 send_time += msecs_to_jiffies(MAX_AGGREGATION_MS);
450
451 bat_iv_ogm_aggregate_new(packet_buff, packet_len,
452 send_time, direct_link,
453 if_incoming, own_packet);
454 } else {
455 bat_iv_ogm_aggregate(forw_packet_aggr, packet_buff,
456 packet_len, direct_link);
457 spin_unlock_bh(&bat_priv->forw_bat_list_lock);
458 }
459 }
460
461 static void bat_iv_ogm_forward(struct orig_node *orig_node,
462 const struct ethhdr *ethhdr,
463 struct batman_ogm_packet *batman_ogm_packet,
464 int directlink, struct hard_iface *if_incoming)
465 {
466 struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
467 struct neigh_node *router;
468 uint8_t in_tq, in_ttl, tq_avg = 0;
469 uint8_t tt_num_changes;
470
471 if (batman_ogm_packet->header.ttl <= 1) {
472 bat_dbg(DBG_BATMAN, bat_priv, "ttl exceeded\n");
473 return;
474 }
475
476 router = orig_node_get_router(orig_node);
477
478 in_tq = batman_ogm_packet->tq;
479 in_ttl = batman_ogm_packet->header.ttl;
480 tt_num_changes = batman_ogm_packet->tt_num_changes;
481
482 batman_ogm_packet->header.ttl--;
483 memcpy(batman_ogm_packet->prev_sender, ethhdr->h_source, ETH_ALEN);
484
485 /* rebroadcast tq of our best ranking neighbor to ensure the rebroadcast
486 * of our best tq value */
487 if (router && router->tq_avg != 0) {
488
489 /* rebroadcast ogm of best ranking neighbor as is */
490 if (!compare_eth(router->addr, ethhdr->h_source)) {
491 batman_ogm_packet->tq = router->tq_avg;
492
493 if (router->last_ttl)
494 batman_ogm_packet->header.ttl =
495 router->last_ttl - 1;
496 }
497
498 tq_avg = router->tq_avg;
499 }
500
501 if (router)
502 neigh_node_free_ref(router);
503
504 /* apply hop penalty */
505 batman_ogm_packet->tq = hop_penalty(batman_ogm_packet->tq, bat_priv);
506
507 bat_dbg(DBG_BATMAN, bat_priv,
508 "Forwarding packet: tq_orig: %i, tq_avg: %i, tq_forw: %i, ttl_orig: %i, ttl_forw: %i\n",
509 in_tq, tq_avg, batman_ogm_packet->tq, in_ttl - 1,
510 batman_ogm_packet->header.ttl);
511
512 batman_ogm_packet->seqno = htonl(batman_ogm_packet->seqno);
513 batman_ogm_packet->tt_crc = htons(batman_ogm_packet->tt_crc);
514
515 /* switch of primaries first hop flag when forwarding */
516 batman_ogm_packet->flags &= ~PRIMARIES_FIRST_HOP;
517 if (directlink)
518 batman_ogm_packet->flags |= DIRECTLINK;
519 else
520 batman_ogm_packet->flags &= ~DIRECTLINK;
521
522 bat_iv_ogm_queue_add(bat_priv, (unsigned char *)batman_ogm_packet,
523 BATMAN_OGM_LEN + tt_len(tt_num_changes),
524 if_incoming, 0, bat_iv_ogm_fwd_send_time());
525 }
526
527 static void bat_iv_ogm_schedule(struct hard_iface *hard_iface,
528 int tt_num_changes)
529 {
530 struct bat_priv *bat_priv = netdev_priv(hard_iface->soft_iface);
531 struct batman_ogm_packet *batman_ogm_packet;
532 struct hard_iface *primary_if;
533 int vis_server;
534
535 vis_server = atomic_read(&bat_priv->vis_mode);
536 primary_if = primary_if_get_selected(bat_priv);
537
538 batman_ogm_packet = (struct batman_ogm_packet *)hard_iface->packet_buff;
539
540 /* change sequence number to network order */
541 batman_ogm_packet->seqno =
542 htonl((uint32_t)atomic_read(&hard_iface->seqno));
543
544 batman_ogm_packet->ttvn = atomic_read(&bat_priv->ttvn);
545 batman_ogm_packet->tt_crc = htons((uint16_t)
546 atomic_read(&bat_priv->tt_crc));
547 if (tt_num_changes >= 0)
548 batman_ogm_packet->tt_num_changes = tt_num_changes;
549
550 if (vis_server == VIS_TYPE_SERVER_SYNC)
551 batman_ogm_packet->flags |= VIS_SERVER;
552 else
553 batman_ogm_packet->flags &= ~VIS_SERVER;
554
555 if ((hard_iface == primary_if) &&
556 (atomic_read(&bat_priv->gw_mode) == GW_MODE_SERVER))
557 batman_ogm_packet->gw_flags =
558 (uint8_t)atomic_read(&bat_priv->gw_bandwidth);
559 else
560 batman_ogm_packet->gw_flags = NO_FLAGS;
561
562 atomic_inc(&hard_iface->seqno);
563
564 slide_own_bcast_window(hard_iface);
565 bat_iv_ogm_queue_add(bat_priv, hard_iface->packet_buff,
566 hard_iface->packet_len, hard_iface, 1,
567 bat_iv_ogm_emit_send_time(bat_priv));
568
569 if (primary_if)
570 hardif_free_ref(primary_if);
571 }
572
573 static void bat_iv_ogm_orig_update(struct bat_priv *bat_priv,
574 struct orig_node *orig_node,
575 const struct ethhdr *ethhdr,
576 const struct batman_ogm_packet
577 *batman_ogm_packet,
578 struct hard_iface *if_incoming,
579 const unsigned char *tt_buff,
580 int is_duplicate)
581 {
582 struct neigh_node *neigh_node = NULL, *tmp_neigh_node = NULL;
583 struct neigh_node *router = NULL;
584 struct orig_node *orig_node_tmp;
585 struct hlist_node *node;
586 uint8_t bcast_own_sum_orig, bcast_own_sum_neigh;
587
588 bat_dbg(DBG_BATMAN, bat_priv,
589 "update_originator(): Searching and updating originator entry of received packet\n");
590
591 rcu_read_lock();
592 hlist_for_each_entry_rcu(tmp_neigh_node, node,
593 &orig_node->neigh_list, list) {
594 if (compare_eth(tmp_neigh_node->addr, ethhdr->h_source) &&
595 (tmp_neigh_node->if_incoming == if_incoming) &&
596 atomic_inc_not_zero(&tmp_neigh_node->refcount)) {
597 if (neigh_node)
598 neigh_node_free_ref(neigh_node);
599 neigh_node = tmp_neigh_node;
600 continue;
601 }
602
603 if (is_duplicate)
604 continue;
605
606 spin_lock_bh(&tmp_neigh_node->tq_lock);
607 ring_buffer_set(tmp_neigh_node->tq_recv,
608 &tmp_neigh_node->tq_index, 0);
609 tmp_neigh_node->tq_avg =
610 ring_buffer_avg(tmp_neigh_node->tq_recv);
611 spin_unlock_bh(&tmp_neigh_node->tq_lock);
612 }
613
614 if (!neigh_node) {
615 struct orig_node *orig_tmp;
616
617 orig_tmp = get_orig_node(bat_priv, ethhdr->h_source);
618 if (!orig_tmp)
619 goto unlock;
620
621 neigh_node = create_neighbor(orig_node, orig_tmp,
622 ethhdr->h_source, if_incoming);
623
624 orig_node_free_ref(orig_tmp);
625 if (!neigh_node)
626 goto unlock;
627 } else
628 bat_dbg(DBG_BATMAN, bat_priv,
629 "Updating existing last-hop neighbor of originator\n");
630
631 rcu_read_unlock();
632
633 orig_node->flags = batman_ogm_packet->flags;
634 neigh_node->last_valid = jiffies;
635
636 spin_lock_bh(&neigh_node->tq_lock);
637 ring_buffer_set(neigh_node->tq_recv,
638 &neigh_node->tq_index,
639 batman_ogm_packet->tq);
640 neigh_node->tq_avg = ring_buffer_avg(neigh_node->tq_recv);
641 spin_unlock_bh(&neigh_node->tq_lock);
642
643 if (!is_duplicate) {
644 orig_node->last_ttl = batman_ogm_packet->header.ttl;
645 neigh_node->last_ttl = batman_ogm_packet->header.ttl;
646 }
647
648 bonding_candidate_add(orig_node, neigh_node);
649
650 /* if this neighbor already is our next hop there is nothing
651 * to change */
652 router = orig_node_get_router(orig_node);
653 if (router == neigh_node)
654 goto update_tt;
655
656 /* if this neighbor does not offer a better TQ we won't consider it */
657 if (router && (router->tq_avg > neigh_node->tq_avg))
658 goto update_tt;
659
660 /* if the TQ is the same and the link not more symmetric we
661 * won't consider it either */
662 if (router && (neigh_node->tq_avg == router->tq_avg)) {
663 orig_node_tmp = router->orig_node;
664 spin_lock_bh(&orig_node_tmp->ogm_cnt_lock);
665 bcast_own_sum_orig =
666 orig_node_tmp->bcast_own_sum[if_incoming->if_num];
667 spin_unlock_bh(&orig_node_tmp->ogm_cnt_lock);
668
669 orig_node_tmp = neigh_node->orig_node;
670 spin_lock_bh(&orig_node_tmp->ogm_cnt_lock);
671 bcast_own_sum_neigh =
672 orig_node_tmp->bcast_own_sum[if_incoming->if_num];
673 spin_unlock_bh(&orig_node_tmp->ogm_cnt_lock);
674
675 if (bcast_own_sum_orig >= bcast_own_sum_neigh)
676 goto update_tt;
677 }
678
679 update_route(bat_priv, orig_node, neigh_node);
680
681 update_tt:
682 /* I have to check for transtable changes only if the OGM has been
683 * sent through a primary interface */
684 if (((batman_ogm_packet->orig != ethhdr->h_source) &&
685 (batman_ogm_packet->header.ttl > 2)) ||
686 (batman_ogm_packet->flags & PRIMARIES_FIRST_HOP))
687 tt_update_orig(bat_priv, orig_node, tt_buff,
688 batman_ogm_packet->tt_num_changes,
689 batman_ogm_packet->ttvn,
690 batman_ogm_packet->tt_crc);
691
692 if (orig_node->gw_flags != batman_ogm_packet->gw_flags)
693 gw_node_update(bat_priv, orig_node,
694 batman_ogm_packet->gw_flags);
695
696 orig_node->gw_flags = batman_ogm_packet->gw_flags;
697
698 /* restart gateway selection if fast or late switching was enabled */
699 if ((orig_node->gw_flags) &&
700 (atomic_read(&bat_priv->gw_mode) == GW_MODE_CLIENT) &&
701 (atomic_read(&bat_priv->gw_sel_class) > 2))
702 gw_check_election(bat_priv, orig_node);
703
704 goto out;
705
706 unlock:
707 rcu_read_unlock();
708 out:
709 if (neigh_node)
710 neigh_node_free_ref(neigh_node);
711 if (router)
712 neigh_node_free_ref(router);
713 }
714
715 static int bat_iv_ogm_calc_tq(struct orig_node *orig_node,
716 struct orig_node *orig_neigh_node,
717 struct batman_ogm_packet *batman_ogm_packet,
718 struct hard_iface *if_incoming)
719 {
720 struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
721 struct neigh_node *neigh_node = NULL, *tmp_neigh_node;
722 struct hlist_node *node;
723 uint8_t total_count;
724 uint8_t orig_eq_count, neigh_rq_count, tq_own;
725 int tq_asym_penalty, ret = 0;
726
727 /* find corresponding one hop neighbor */
728 rcu_read_lock();
729 hlist_for_each_entry_rcu(tmp_neigh_node, node,
730 &orig_neigh_node->neigh_list, list) {
731
732 if (!compare_eth(tmp_neigh_node->addr, orig_neigh_node->orig))
733 continue;
734
735 if (tmp_neigh_node->if_incoming != if_incoming)
736 continue;
737
738 if (!atomic_inc_not_zero(&tmp_neigh_node->refcount))
739 continue;
740
741 neigh_node = tmp_neigh_node;
742 break;
743 }
744 rcu_read_unlock();
745
746 if (!neigh_node)
747 neigh_node = create_neighbor(orig_neigh_node,
748 orig_neigh_node,
749 orig_neigh_node->orig,
750 if_incoming);
751
752 if (!neigh_node)
753 goto out;
754
755 /* if orig_node is direct neighbor update neigh_node last_valid */
756 if (orig_node == orig_neigh_node)
757 neigh_node->last_valid = jiffies;
758
759 orig_node->last_valid = jiffies;
760
761 /* find packet count of corresponding one hop neighbor */
762 spin_lock_bh(&orig_node->ogm_cnt_lock);
763 orig_eq_count = orig_neigh_node->bcast_own_sum[if_incoming->if_num];
764 neigh_rq_count = neigh_node->real_packet_count;
765 spin_unlock_bh(&orig_node->ogm_cnt_lock);
766
767 /* pay attention to not get a value bigger than 100 % */
768 total_count = (orig_eq_count > neigh_rq_count ?
769 neigh_rq_count : orig_eq_count);
770
771 /* if we have too few packets (too less data) we set tq_own to zero */
772 /* if we receive too few packets it is not considered bidirectional */
773 if ((total_count < TQ_LOCAL_BIDRECT_SEND_MINIMUM) ||
774 (neigh_rq_count < TQ_LOCAL_BIDRECT_RECV_MINIMUM))
775 tq_own = 0;
776 else
777 /* neigh_node->real_packet_count is never zero as we
778 * only purge old information when getting new
779 * information */
780 tq_own = (TQ_MAX_VALUE * total_count) / neigh_rq_count;
781
782 /* 1 - ((1-x) ** 3), normalized to TQ_MAX_VALUE this does
783 * affect the nearly-symmetric links only a little, but
784 * punishes asymmetric links more. This will give a value
785 * between 0 and TQ_MAX_VALUE
786 */
787 tq_asym_penalty = TQ_MAX_VALUE - (TQ_MAX_VALUE *
788 (TQ_LOCAL_WINDOW_SIZE - neigh_rq_count) *
789 (TQ_LOCAL_WINDOW_SIZE - neigh_rq_count) *
790 (TQ_LOCAL_WINDOW_SIZE - neigh_rq_count)) /
791 (TQ_LOCAL_WINDOW_SIZE *
792 TQ_LOCAL_WINDOW_SIZE *
793 TQ_LOCAL_WINDOW_SIZE);
794
795 batman_ogm_packet->tq = ((batman_ogm_packet->tq * tq_own
796 * tq_asym_penalty) /
797 (TQ_MAX_VALUE * TQ_MAX_VALUE));
798
799 bat_dbg(DBG_BATMAN, bat_priv,
800 "bidirectional: orig = %-15pM neigh = %-15pM => own_bcast = %2i, real recv = %2i, local tq: %3i, asym_penalty: %3i, total tq: %3i\n",
801 orig_node->orig, orig_neigh_node->orig, total_count,
802 neigh_rq_count, tq_own, tq_asym_penalty, batman_ogm_packet->tq);
803
804 /* if link has the minimum required transmission quality
805 * consider it bidirectional */
806 if (batman_ogm_packet->tq >= TQ_TOTAL_BIDRECT_LIMIT)
807 ret = 1;
808
809 out:
810 if (neigh_node)
811 neigh_node_free_ref(neigh_node);
812 return ret;
813 }
814
815 /* processes a batman packet for all interfaces, adjusts the sequence number and
816 * finds out whether it is a duplicate.
817 * returns:
818 * 1 the packet is a duplicate
819 * 0 the packet has not yet been received
820 * -1 the packet is old and has been received while the seqno window
821 * was protected. Caller should drop it.
822 */
823 static int bat_iv_ogm_update_seqnos(const struct ethhdr *ethhdr,
824 const struct batman_ogm_packet
825 *batman_ogm_packet,
826 const struct hard_iface *if_incoming)
827 {
828 struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
829 struct orig_node *orig_node;
830 struct neigh_node *tmp_neigh_node;
831 struct hlist_node *node;
832 int is_duplicate = 0;
833 int32_t seq_diff;
834 int need_update = 0;
835 int set_mark, ret = -1;
836
837 orig_node = get_orig_node(bat_priv, batman_ogm_packet->orig);
838 if (!orig_node)
839 return 0;
840
841 spin_lock_bh(&orig_node->ogm_cnt_lock);
842 seq_diff = batman_ogm_packet->seqno - orig_node->last_real_seqno;
843
844 /* signalize caller that the packet is to be dropped. */
845 if (window_protected(bat_priv, seq_diff,
846 &orig_node->batman_seqno_reset))
847 goto out;
848
849 rcu_read_lock();
850 hlist_for_each_entry_rcu(tmp_neigh_node, node,
851 &orig_node->neigh_list, list) {
852
853 is_duplicate |= bat_test_bit(tmp_neigh_node->real_bits,
854 orig_node->last_real_seqno,
855 batman_ogm_packet->seqno);
856
857 if (compare_eth(tmp_neigh_node->addr, ethhdr->h_source) &&
858 (tmp_neigh_node->if_incoming == if_incoming))
859 set_mark = 1;
860 else
861 set_mark = 0;
862
863 /* if the window moved, set the update flag. */
864 need_update |= bit_get_packet(bat_priv,
865 tmp_neigh_node->real_bits,
866 seq_diff, set_mark);
867
868 tmp_neigh_node->real_packet_count =
869 bitmap_weight(tmp_neigh_node->real_bits,
870 TQ_LOCAL_WINDOW_SIZE);
871 }
872 rcu_read_unlock();
873
874 if (need_update) {
875 bat_dbg(DBG_BATMAN, bat_priv,
876 "updating last_seqno: old %d, new %d\n",
877 orig_node->last_real_seqno, batman_ogm_packet->seqno);
878 orig_node->last_real_seqno = batman_ogm_packet->seqno;
879 }
880
881 ret = is_duplicate;
882
883 out:
884 spin_unlock_bh(&orig_node->ogm_cnt_lock);
885 orig_node_free_ref(orig_node);
886 return ret;
887 }
888
889 static void bat_iv_ogm_process(const struct ethhdr *ethhdr,
890 struct batman_ogm_packet *batman_ogm_packet,
891 const unsigned char *tt_buff,
892 struct hard_iface *if_incoming)
893 {
894 struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
895 struct hard_iface *hard_iface;
896 struct orig_node *orig_neigh_node, *orig_node;
897 struct neigh_node *router = NULL, *router_router = NULL;
898 struct neigh_node *orig_neigh_router = NULL;
899 int has_directlink_flag;
900 int is_my_addr = 0, is_my_orig = 0, is_my_oldorig = 0;
901 int is_broadcast = 0, is_bidirectional, is_single_hop_neigh;
902 int is_duplicate;
903 uint32_t if_incoming_seqno;
904
905 /* Silently drop when the batman packet is actually not a
906 * correct packet.
907 *
908 * This might happen if a packet is padded (e.g. Ethernet has a
909 * minimum frame length of 64 byte) and the aggregation interprets
910 * it as an additional length.
911 *
912 * TODO: A more sane solution would be to have a bit in the
913 * batman_ogm_packet to detect whether the packet is the last
914 * packet in an aggregation. Here we expect that the padding
915 * is always zero (or not 0x01)
916 */
917 if (batman_ogm_packet->header.packet_type != BAT_OGM)
918 return;
919
920 /* could be changed by schedule_own_packet() */
921 if_incoming_seqno = atomic_read(&if_incoming->seqno);
922
923 has_directlink_flag = (batman_ogm_packet->flags & DIRECTLINK ? 1 : 0);
924
925 is_single_hop_neigh = (compare_eth(ethhdr->h_source,
926 batman_ogm_packet->orig) ? 1 : 0);
927
928 bat_dbg(DBG_BATMAN, bat_priv,
929 "Received BATMAN packet via NB: %pM, IF: %s [%pM] (from OG: %pM, via prev OG: %pM, seqno %d, ttvn %u, crc %u, changes %u, td %d, TTL %d, V %d, IDF %d)\n",
930 ethhdr->h_source, if_incoming->net_dev->name,
931 if_incoming->net_dev->dev_addr, batman_ogm_packet->orig,
932 batman_ogm_packet->prev_sender, batman_ogm_packet->seqno,
933 batman_ogm_packet->ttvn, batman_ogm_packet->tt_crc,
934 batman_ogm_packet->tt_num_changes, batman_ogm_packet->tq,
935 batman_ogm_packet->header.ttl,
936 batman_ogm_packet->header.version, has_directlink_flag);
937
938 rcu_read_lock();
939 list_for_each_entry_rcu(hard_iface, &hardif_list, list) {
940 if (hard_iface->if_status != IF_ACTIVE)
941 continue;
942
943 if (hard_iface->soft_iface != if_incoming->soft_iface)
944 continue;
945
946 if (compare_eth(ethhdr->h_source,
947 hard_iface->net_dev->dev_addr))
948 is_my_addr = 1;
949
950 if (compare_eth(batman_ogm_packet->orig,
951 hard_iface->net_dev->dev_addr))
952 is_my_orig = 1;
953
954 if (compare_eth(batman_ogm_packet->prev_sender,
955 hard_iface->net_dev->dev_addr))
956 is_my_oldorig = 1;
957
958 if (is_broadcast_ether_addr(ethhdr->h_source))
959 is_broadcast = 1;
960 }
961 rcu_read_unlock();
962
963 if (batman_ogm_packet->header.version != COMPAT_VERSION) {
964 bat_dbg(DBG_BATMAN, bat_priv,
965 "Drop packet: incompatible batman version (%i)\n",
966 batman_ogm_packet->header.version);
967 return;
968 }
969
970 if (is_my_addr) {
971 bat_dbg(DBG_BATMAN, bat_priv,
972 "Drop packet: received my own broadcast (sender: %pM)\n",
973 ethhdr->h_source);
974 return;
975 }
976
977 if (is_broadcast) {
978 bat_dbg(DBG_BATMAN, bat_priv,
979 "Drop packet: ignoring all packets with broadcast source addr (sender: %pM)\n",
980 ethhdr->h_source);
981 return;
982 }
983
984 if (is_my_orig) {
985 unsigned long *word;
986 int offset;
987
988 orig_neigh_node = get_orig_node(bat_priv, ethhdr->h_source);
989 if (!orig_neigh_node)
990 return;
991
992 /* neighbor has to indicate direct link and it has to
993 * come via the corresponding interface */
994 /* save packet seqno for bidirectional check */
995 if (has_directlink_flag &&
996 compare_eth(if_incoming->net_dev->dev_addr,
997 batman_ogm_packet->orig)) {
998 offset = if_incoming->if_num * NUM_WORDS;
999
1000 spin_lock_bh(&orig_neigh_node->ogm_cnt_lock);
1001 word = &(orig_neigh_node->bcast_own[offset]);
1002 bat_set_bit(word,
1003 if_incoming_seqno -
1004 batman_ogm_packet->seqno - 2);
1005 orig_neigh_node->bcast_own_sum[if_incoming->if_num] =
1006 bitmap_weight(word, TQ_LOCAL_WINDOW_SIZE);
1007 spin_unlock_bh(&orig_neigh_node->ogm_cnt_lock);
1008 }
1009
1010 bat_dbg(DBG_BATMAN, bat_priv,
1011 "Drop packet: originator packet from myself (via neighbor)\n");
1012 orig_node_free_ref(orig_neigh_node);
1013 return;
1014 }
1015
1016 if (is_my_oldorig) {
1017 bat_dbg(DBG_BATMAN, bat_priv,
1018 "Drop packet: ignoring all rebroadcast echos (sender: %pM)\n",
1019 ethhdr->h_source);
1020 return;
1021 }
1022
1023 orig_node = get_orig_node(bat_priv, batman_ogm_packet->orig);
1024 if (!orig_node)
1025 return;
1026
1027 is_duplicate = bat_iv_ogm_update_seqnos(ethhdr, batman_ogm_packet,
1028 if_incoming);
1029
1030 if (is_duplicate == -1) {
1031 bat_dbg(DBG_BATMAN, bat_priv,
1032 "Drop packet: packet within seqno protection time (sender: %pM)\n",
1033 ethhdr->h_source);
1034 goto out;
1035 }
1036
1037 if (batman_ogm_packet->tq == 0) {
1038 bat_dbg(DBG_BATMAN, bat_priv,
1039 "Drop packet: originator packet with tq equal 0\n");
1040 goto out;
1041 }
1042
1043 router = orig_node_get_router(orig_node);
1044 if (router)
1045 router_router = orig_node_get_router(router->orig_node);
1046
1047 /* avoid temporary routing loops */
1048 if (router && router_router &&
1049 (compare_eth(router->addr, batman_ogm_packet->prev_sender)) &&
1050 !(compare_eth(batman_ogm_packet->orig,
1051 batman_ogm_packet->prev_sender)) &&
1052 (compare_eth(router->addr, router_router->addr))) {
1053 bat_dbg(DBG_BATMAN, bat_priv,
1054 "Drop packet: ignoring all rebroadcast packets that may make me loop (sender: %pM)\n",
1055 ethhdr->h_source);
1056 goto out;
1057 }
1058
1059 /* if sender is a direct neighbor the sender mac equals
1060 * originator mac */
1061 orig_neigh_node = (is_single_hop_neigh ?
1062 orig_node :
1063 get_orig_node(bat_priv, ethhdr->h_source));
1064 if (!orig_neigh_node)
1065 goto out;
1066
1067 orig_neigh_router = orig_node_get_router(orig_neigh_node);
1068
1069 /* drop packet if sender is not a direct neighbor and if we
1070 * don't route towards it */
1071 if (!is_single_hop_neigh && (!orig_neigh_router)) {
1072 bat_dbg(DBG_BATMAN, bat_priv,
1073 "Drop packet: OGM via unknown neighbor!\n");
1074 goto out_neigh;
1075 }
1076
1077 is_bidirectional = bat_iv_ogm_calc_tq(orig_node, orig_neigh_node,
1078 batman_ogm_packet, if_incoming);
1079
1080 bonding_save_primary(orig_node, orig_neigh_node, batman_ogm_packet);
1081
1082 /* update ranking if it is not a duplicate or has the same
1083 * seqno and similar ttl as the non-duplicate */
1084 if (is_bidirectional &&
1085 (!is_duplicate ||
1086 ((orig_node->last_real_seqno == batman_ogm_packet->seqno) &&
1087 (orig_node->last_ttl - 3 <= batman_ogm_packet->header.ttl))))
1088 bat_iv_ogm_orig_update(bat_priv, orig_node, ethhdr,
1089 batman_ogm_packet, if_incoming,
1090 tt_buff, is_duplicate);
1091
1092 /* is single hop (direct) neighbor */
1093 if (is_single_hop_neigh) {
1094
1095 /* mark direct link on incoming interface */
1096 bat_iv_ogm_forward(orig_node, ethhdr, batman_ogm_packet,
1097 1, if_incoming);
1098
1099 bat_dbg(DBG_BATMAN, bat_priv,
1100 "Forwarding packet: rebroadcast neighbor packet with direct link flag\n");
1101 goto out_neigh;
1102 }
1103
1104 /* multihop originator */
1105 if (!is_bidirectional) {
1106 bat_dbg(DBG_BATMAN, bat_priv,
1107 "Drop packet: not received via bidirectional link\n");
1108 goto out_neigh;
1109 }
1110
1111 if (is_duplicate) {
1112 bat_dbg(DBG_BATMAN, bat_priv,
1113 "Drop packet: duplicate packet received\n");
1114 goto out_neigh;
1115 }
1116
1117 bat_dbg(DBG_BATMAN, bat_priv,
1118 "Forwarding packet: rebroadcast originator packet\n");
1119 bat_iv_ogm_forward(orig_node, ethhdr, batman_ogm_packet,
1120 0, if_incoming);
1121
1122 out_neigh:
1123 if ((orig_neigh_node) && (!is_single_hop_neigh))
1124 orig_node_free_ref(orig_neigh_node);
1125 out:
1126 if (router)
1127 neigh_node_free_ref(router);
1128 if (router_router)
1129 neigh_node_free_ref(router_router);
1130 if (orig_neigh_router)
1131 neigh_node_free_ref(orig_neigh_router);
1132
1133 orig_node_free_ref(orig_node);
1134 }
1135
1136 static void bat_iv_ogm_receive(struct hard_iface *if_incoming,
1137 struct sk_buff *skb)
1138 {
1139 struct batman_ogm_packet *batman_ogm_packet;
1140 struct ethhdr *ethhdr;
1141 int buff_pos = 0, packet_len;
1142 unsigned char *tt_buff, *packet_buff;
1143
1144 packet_len = skb_headlen(skb);
1145 ethhdr = (struct ethhdr *)skb_mac_header(skb);
1146 packet_buff = skb->data;
1147 batman_ogm_packet = (struct batman_ogm_packet *)packet_buff;
1148
1149 /* unpack the aggregated packets and process them one by one */
1150 do {
1151 /* network to host order for our 32bit seqno and the
1152 orig_interval */
1153 batman_ogm_packet->seqno = ntohl(batman_ogm_packet->seqno);
1154 batman_ogm_packet->tt_crc = ntohs(batman_ogm_packet->tt_crc);
1155
1156 tt_buff = packet_buff + buff_pos + BATMAN_OGM_LEN;
1157
1158 bat_iv_ogm_process(ethhdr, batman_ogm_packet,
1159 tt_buff, if_incoming);
1160
1161 buff_pos += BATMAN_OGM_LEN +
1162 tt_len(batman_ogm_packet->tt_num_changes);
1163
1164 batman_ogm_packet = (struct batman_ogm_packet *)
1165 (packet_buff + buff_pos);
1166 } while (bat_iv_ogm_aggr_packet(buff_pos, packet_len,
1167 batman_ogm_packet->tt_num_changes));
1168 }
1169
1170 static struct bat_algo_ops batman_iv __read_mostly = {
1171 .name = "BATMAN IV",
1172 .bat_ogm_init = bat_iv_ogm_init,
1173 .bat_ogm_init_primary = bat_iv_ogm_init_primary,
1174 .bat_ogm_update_mac = bat_iv_ogm_update_mac,
1175 .bat_ogm_schedule = bat_iv_ogm_schedule,
1176 .bat_ogm_emit = bat_iv_ogm_emit,
1177 .bat_ogm_receive = bat_iv_ogm_receive,
1178 };
1179
1180 int __init bat_iv_init(void)
1181 {
1182 return bat_algo_register(&batman_iv);
1183 }
kernel source for telekom puls (alcatel/mediatek)