bat_iv_ogm.c 43 KB

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