distributed-arp-table.c 30 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066
  1. /* Copyright (C) 2011-2013 B.A.T.M.A.N. contributors:
  2. *
  3. * Antonio Quartulli
  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 <linux/if_ether.h>
  20. #include <linux/if_arp.h>
  21. #include <net/arp.h>
  22. #include "main.h"
  23. #include "hash.h"
  24. #include "distributed-arp-table.h"
  25. #include "hard-interface.h"
  26. #include "originator.h"
  27. #include "send.h"
  28. #include "types.h"
  29. #include "translation-table.h"
  30. #include "unicast.h"
  31. static void batadv_dat_purge(struct work_struct *work);
  32. /**
  33. * batadv_dat_start_timer - initialise the DAT periodic worker
  34. * @bat_priv: the bat priv with all the soft interface information
  35. */
  36. static void batadv_dat_start_timer(struct batadv_priv *bat_priv)
  37. {
  38. INIT_DELAYED_WORK(&bat_priv->dat.work, batadv_dat_purge);
  39. queue_delayed_work(batadv_event_workqueue, &bat_priv->dat.work,
  40. msecs_to_jiffies(10000));
  41. }
  42. /**
  43. * batadv_dat_entry_free_ref - decrements the dat_entry refcounter and possibly
  44. * free it
  45. * @dat_entry: the oentry to free
  46. */
  47. static void batadv_dat_entry_free_ref(struct batadv_dat_entry *dat_entry)
  48. {
  49. if (atomic_dec_and_test(&dat_entry->refcount))
  50. kfree_rcu(dat_entry, rcu);
  51. }
  52. /**
  53. * batadv_dat_to_purge - checks whether a dat_entry has to be purged or not
  54. * @dat_entry: the entry to check
  55. *
  56. * Returns true if the entry has to be purged now, false otherwise
  57. */
  58. static bool batadv_dat_to_purge(struct batadv_dat_entry *dat_entry)
  59. {
  60. return batadv_has_timed_out(dat_entry->last_update,
  61. BATADV_DAT_ENTRY_TIMEOUT);
  62. }
  63. /**
  64. * __batadv_dat_purge - delete entries from the DAT local storage
  65. * @bat_priv: the bat priv with all the soft interface information
  66. * @to_purge: function in charge to decide whether an entry has to be purged or
  67. * not. This function takes the dat_entry as argument and has to
  68. * returns a boolean value: true is the entry has to be deleted,
  69. * false otherwise
  70. *
  71. * Loops over each entry in the DAT local storage and delete it if and only if
  72. * the to_purge function passed as argument returns true
  73. */
  74. static void __batadv_dat_purge(struct batadv_priv *bat_priv,
  75. bool (*to_purge)(struct batadv_dat_entry *))
  76. {
  77. spinlock_t *list_lock; /* protects write access to the hash lists */
  78. struct batadv_dat_entry *dat_entry;
  79. struct hlist_node *node_tmp;
  80. struct hlist_head *head;
  81. uint32_t i;
  82. if (!bat_priv->dat.hash)
  83. return;
  84. for (i = 0; i < bat_priv->dat.hash->size; i++) {
  85. head = &bat_priv->dat.hash->table[i];
  86. list_lock = &bat_priv->dat.hash->list_locks[i];
  87. spin_lock_bh(list_lock);
  88. hlist_for_each_entry_safe(dat_entry, node_tmp, head,
  89. hash_entry) {
  90. /* if an helper function has been passed as parameter,
  91. * ask it if the entry has to be purged or not
  92. */
  93. if (to_purge && !to_purge(dat_entry))
  94. continue;
  95. hlist_del_rcu(&dat_entry->hash_entry);
  96. batadv_dat_entry_free_ref(dat_entry);
  97. }
  98. spin_unlock_bh(list_lock);
  99. }
  100. }
  101. /**
  102. * batadv_dat_purge - periodic task that deletes old entries from the local DAT
  103. * hash table
  104. * @work: kernel work struct
  105. */
  106. static void batadv_dat_purge(struct work_struct *work)
  107. {
  108. struct delayed_work *delayed_work;
  109. struct batadv_priv_dat *priv_dat;
  110. struct batadv_priv *bat_priv;
  111. delayed_work = container_of(work, struct delayed_work, work);
  112. priv_dat = container_of(delayed_work, struct batadv_priv_dat, work);
  113. bat_priv = container_of(priv_dat, struct batadv_priv, dat);
  114. __batadv_dat_purge(bat_priv, batadv_dat_to_purge);
  115. batadv_dat_start_timer(bat_priv);
  116. }
  117. /**
  118. * batadv_compare_dat - comparing function used in the local DAT hash table
  119. * @node: node in the local table
  120. * @data2: second object to compare the node to
  121. *
  122. * Returns 1 if the two entry are the same, 0 otherwise
  123. */
  124. static int batadv_compare_dat(const struct hlist_node *node, const void *data2)
  125. {
  126. const void *data1 = container_of(node, struct batadv_dat_entry,
  127. hash_entry);
  128. return (memcmp(data1, data2, sizeof(__be32)) == 0 ? 1 : 0);
  129. }
  130. /**
  131. * batadv_arp_hw_src - extract the hw_src field from an ARP packet
  132. * @skb: ARP packet
  133. * @hdr_size: size of the possible header before the ARP packet
  134. *
  135. * Returns the value of the hw_src field in the ARP packet
  136. */
  137. static uint8_t *batadv_arp_hw_src(struct sk_buff *skb, int hdr_size)
  138. {
  139. uint8_t *addr;
  140. addr = (uint8_t *)(skb->data + hdr_size);
  141. addr += ETH_HLEN + sizeof(struct arphdr);
  142. return addr;
  143. }
  144. /**
  145. * batadv_arp_ip_src - extract the ip_src field from an ARP packet
  146. * @skb: ARP packet
  147. * @hdr_size: size of the possible header before the ARP packet
  148. *
  149. * Returns the value of the ip_src field in the ARP packet
  150. */
  151. static __be32 batadv_arp_ip_src(struct sk_buff *skb, int hdr_size)
  152. {
  153. return *(__be32 *)(batadv_arp_hw_src(skb, hdr_size) + ETH_ALEN);
  154. }
  155. /**
  156. * batadv_arp_hw_dst - extract the hw_dst field from an ARP packet
  157. * @skb: ARP packet
  158. * @hdr_size: size of the possible header before the ARP packet
  159. *
  160. * Returns the value of the hw_dst field in the ARP packet
  161. */
  162. static uint8_t *batadv_arp_hw_dst(struct sk_buff *skb, int hdr_size)
  163. {
  164. return batadv_arp_hw_src(skb, hdr_size) + ETH_ALEN + 4;
  165. }
  166. /**
  167. * batadv_arp_ip_dst - extract the ip_dst field from an ARP packet
  168. * @skb: ARP packet
  169. * @hdr_size: size of the possible header before the ARP packet
  170. *
  171. * Returns the value of the ip_dst field in the ARP packet
  172. */
  173. static __be32 batadv_arp_ip_dst(struct sk_buff *skb, int hdr_size)
  174. {
  175. return *(__be32 *)(batadv_arp_hw_src(skb, hdr_size) + ETH_ALEN * 2 + 4);
  176. }
  177. /**
  178. * batadv_hash_dat - compute the hash value for an IP address
  179. * @data: data to hash
  180. * @size: size of the hash table
  181. *
  182. * Returns the selected index in the hash table for the given data
  183. */
  184. static uint32_t batadv_hash_dat(const void *data, uint32_t size)
  185. {
  186. const unsigned char *key = data;
  187. uint32_t hash = 0;
  188. size_t i;
  189. for (i = 0; i < 4; i++) {
  190. hash += key[i];
  191. hash += (hash << 10);
  192. hash ^= (hash >> 6);
  193. }
  194. hash += (hash << 3);
  195. hash ^= (hash >> 11);
  196. hash += (hash << 15);
  197. return hash % size;
  198. }
  199. /**
  200. * batadv_dat_entry_hash_find - looks for a given dat_entry in the local hash
  201. * table
  202. * @bat_priv: the bat priv with all the soft interface information
  203. * @ip: search key
  204. *
  205. * Returns the dat_entry if found, NULL otherwise
  206. */
  207. static struct batadv_dat_entry *
  208. batadv_dat_entry_hash_find(struct batadv_priv *bat_priv, __be32 ip)
  209. {
  210. struct hlist_head *head;
  211. struct batadv_dat_entry *dat_entry, *dat_entry_tmp = NULL;
  212. struct batadv_hashtable *hash = bat_priv->dat.hash;
  213. uint32_t index;
  214. if (!hash)
  215. return NULL;
  216. index = batadv_hash_dat(&ip, hash->size);
  217. head = &hash->table[index];
  218. rcu_read_lock();
  219. hlist_for_each_entry_rcu(dat_entry, head, hash_entry) {
  220. if (dat_entry->ip != ip)
  221. continue;
  222. if (!atomic_inc_not_zero(&dat_entry->refcount))
  223. continue;
  224. dat_entry_tmp = dat_entry;
  225. break;
  226. }
  227. rcu_read_unlock();
  228. return dat_entry_tmp;
  229. }
  230. /**
  231. * batadv_dat_entry_add - add a new dat entry or update it if already exists
  232. * @bat_priv: the bat priv with all the soft interface information
  233. * @ip: ipv4 to add/edit
  234. * @mac_addr: mac address to assign to the given ipv4
  235. */
  236. static void batadv_dat_entry_add(struct batadv_priv *bat_priv, __be32 ip,
  237. uint8_t *mac_addr)
  238. {
  239. struct batadv_dat_entry *dat_entry;
  240. int hash_added;
  241. dat_entry = batadv_dat_entry_hash_find(bat_priv, ip);
  242. /* if this entry is already known, just update it */
  243. if (dat_entry) {
  244. if (!batadv_compare_eth(dat_entry->mac_addr, mac_addr))
  245. memcpy(dat_entry->mac_addr, mac_addr, ETH_ALEN);
  246. dat_entry->last_update = jiffies;
  247. batadv_dbg(BATADV_DBG_DAT, bat_priv,
  248. "Entry updated: %pI4 %pM\n", &dat_entry->ip,
  249. dat_entry->mac_addr);
  250. goto out;
  251. }
  252. dat_entry = kmalloc(sizeof(*dat_entry), GFP_ATOMIC);
  253. if (!dat_entry)
  254. goto out;
  255. dat_entry->ip = ip;
  256. memcpy(dat_entry->mac_addr, mac_addr, ETH_ALEN);
  257. dat_entry->last_update = jiffies;
  258. atomic_set(&dat_entry->refcount, 2);
  259. hash_added = batadv_hash_add(bat_priv->dat.hash, batadv_compare_dat,
  260. batadv_hash_dat, &dat_entry->ip,
  261. &dat_entry->hash_entry);
  262. if (unlikely(hash_added != 0)) {
  263. /* remove the reference for the hash */
  264. batadv_dat_entry_free_ref(dat_entry);
  265. goto out;
  266. }
  267. batadv_dbg(BATADV_DBG_DAT, bat_priv, "New entry added: %pI4 %pM\n",
  268. &dat_entry->ip, dat_entry->mac_addr);
  269. out:
  270. if (dat_entry)
  271. batadv_dat_entry_free_ref(dat_entry);
  272. }
  273. #ifdef CONFIG_BATMAN_ADV_DEBUG
  274. /**
  275. * batadv_dbg_arp - print a debug message containing all the ARP packet details
  276. * @bat_priv: the bat priv with all the soft interface information
  277. * @skb: ARP packet
  278. * @type: ARP type
  279. * @hdr_size: size of the possible header before the ARP packet
  280. * @msg: message to print together with the debugging information
  281. */
  282. static void batadv_dbg_arp(struct batadv_priv *bat_priv, struct sk_buff *skb,
  283. uint16_t type, int hdr_size, char *msg)
  284. {
  285. struct batadv_unicast_4addr_packet *unicast_4addr_packet;
  286. struct batadv_bcast_packet *bcast_pkt;
  287. uint8_t *orig_addr;
  288. __be32 ip_src, ip_dst;
  289. if (msg)
  290. batadv_dbg(BATADV_DBG_DAT, bat_priv, "%s\n", msg);
  291. ip_src = batadv_arp_ip_src(skb, hdr_size);
  292. ip_dst = batadv_arp_ip_dst(skb, hdr_size);
  293. batadv_dbg(BATADV_DBG_DAT, bat_priv,
  294. "ARP MSG = [src: %pM-%pI4 dst: %pM-%pI4]\n",
  295. batadv_arp_hw_src(skb, hdr_size), &ip_src,
  296. batadv_arp_hw_dst(skb, hdr_size), &ip_dst);
  297. if (hdr_size == 0)
  298. return;
  299. /* if the ARP packet is encapsulated in a batman packet, let's print
  300. * some debug messages
  301. */
  302. unicast_4addr_packet = (struct batadv_unicast_4addr_packet *)skb->data;
  303. switch (unicast_4addr_packet->u.header.packet_type) {
  304. case BATADV_UNICAST:
  305. batadv_dbg(BATADV_DBG_DAT, bat_priv,
  306. "* encapsulated within a UNICAST packet\n");
  307. break;
  308. case BATADV_UNICAST_4ADDR:
  309. batadv_dbg(BATADV_DBG_DAT, bat_priv,
  310. "* encapsulated within a UNICAST_4ADDR packet (src: %pM)\n",
  311. unicast_4addr_packet->src);
  312. switch (unicast_4addr_packet->subtype) {
  313. case BATADV_P_DAT_DHT_PUT:
  314. batadv_dbg(BATADV_DBG_DAT, bat_priv, "* type: DAT_DHT_PUT\n");
  315. break;
  316. case BATADV_P_DAT_DHT_GET:
  317. batadv_dbg(BATADV_DBG_DAT, bat_priv, "* type: DAT_DHT_GET\n");
  318. break;
  319. case BATADV_P_DAT_CACHE_REPLY:
  320. batadv_dbg(BATADV_DBG_DAT, bat_priv,
  321. "* type: DAT_CACHE_REPLY\n");
  322. break;
  323. case BATADV_P_DATA:
  324. batadv_dbg(BATADV_DBG_DAT, bat_priv, "* type: DATA\n");
  325. break;
  326. default:
  327. batadv_dbg(BATADV_DBG_DAT, bat_priv, "* type: Unknown (%u)!\n",
  328. unicast_4addr_packet->u.header.packet_type);
  329. }
  330. break;
  331. case BATADV_BCAST:
  332. bcast_pkt = (struct batadv_bcast_packet *)unicast_4addr_packet;
  333. orig_addr = bcast_pkt->orig;
  334. batadv_dbg(BATADV_DBG_DAT, bat_priv,
  335. "* encapsulated within a BCAST packet (src: %pM)\n",
  336. orig_addr);
  337. break;
  338. default:
  339. batadv_dbg(BATADV_DBG_DAT, bat_priv,
  340. "* encapsulated within an unknown packet type (0x%x)\n",
  341. unicast_4addr_packet->u.header.packet_type);
  342. }
  343. }
  344. #else
  345. static void batadv_dbg_arp(struct batadv_priv *bat_priv, struct sk_buff *skb,
  346. uint16_t type, int hdr_size, char *msg)
  347. {
  348. }
  349. #endif /* CONFIG_BATMAN_ADV_DEBUG */
  350. /**
  351. * batadv_is_orig_node_eligible - check whether a node can be a DHT candidate
  352. * @res: the array with the already selected candidates
  353. * @select: number of already selected candidates
  354. * @tmp_max: address of the currently evaluated node
  355. * @max: current round max address
  356. * @last_max: address of the last selected candidate
  357. * @candidate: orig_node under evaluation
  358. * @max_orig_node: last selected candidate
  359. *
  360. * Returns true if the node has been elected as next candidate or false othrwise
  361. */
  362. static bool batadv_is_orig_node_eligible(struct batadv_dat_candidate *res,
  363. int select, batadv_dat_addr_t tmp_max,
  364. batadv_dat_addr_t max,
  365. batadv_dat_addr_t last_max,
  366. struct batadv_orig_node *candidate,
  367. struct batadv_orig_node *max_orig_node)
  368. {
  369. bool ret = false;
  370. int j;
  371. /* Check if this node has already been selected... */
  372. for (j = 0; j < select; j++)
  373. if (res[j].orig_node == candidate)
  374. break;
  375. /* ..and possibly skip it */
  376. if (j < select)
  377. goto out;
  378. /* sanity check: has it already been selected? This should not happen */
  379. if (tmp_max > last_max)
  380. goto out;
  381. /* check if during this iteration an originator with a closer dht
  382. * address has already been found
  383. */
  384. if (tmp_max < max)
  385. goto out;
  386. /* this is an hash collision with the temporary selected node. Choose
  387. * the one with the lowest address
  388. */
  389. if ((tmp_max == max) && max_orig_node &&
  390. (batadv_compare_eth(candidate->orig, max_orig_node->orig) > 0))
  391. goto out;
  392. ret = true;
  393. out:
  394. return ret;
  395. }
  396. /**
  397. * batadv_choose_next_candidate - select the next DHT candidate
  398. * @bat_priv: the bat priv with all the soft interface information
  399. * @cands: candidates array
  400. * @select: number of candidates already present in the array
  401. * @ip_key: key to look up in the DHT
  402. * @last_max: pointer where the address of the selected candidate will be saved
  403. */
  404. static void batadv_choose_next_candidate(struct batadv_priv *bat_priv,
  405. struct batadv_dat_candidate *cands,
  406. int select, batadv_dat_addr_t ip_key,
  407. batadv_dat_addr_t *last_max)
  408. {
  409. batadv_dat_addr_t max = 0, tmp_max = 0;
  410. struct batadv_orig_node *orig_node, *max_orig_node = NULL;
  411. struct batadv_hashtable *hash = bat_priv->orig_hash;
  412. struct hlist_head *head;
  413. int i;
  414. /* if no node is eligible as candidate, leave the candidate type as
  415. * NOT_FOUND
  416. */
  417. cands[select].type = BATADV_DAT_CANDIDATE_NOT_FOUND;
  418. /* iterate over the originator list and find the node with closest
  419. * dat_address which has not been selected yet
  420. */
  421. for (i = 0; i < hash->size; i++) {
  422. head = &hash->table[i];
  423. rcu_read_lock();
  424. hlist_for_each_entry_rcu(orig_node, head, hash_entry) {
  425. /* the dht space is a ring and addresses are unsigned */
  426. tmp_max = BATADV_DAT_ADDR_MAX - orig_node->dat_addr +
  427. ip_key;
  428. if (!batadv_is_orig_node_eligible(cands, select,
  429. tmp_max, max,
  430. *last_max, orig_node,
  431. max_orig_node))
  432. continue;
  433. if (!atomic_inc_not_zero(&orig_node->refcount))
  434. continue;
  435. max = tmp_max;
  436. if (max_orig_node)
  437. batadv_orig_node_free_ref(max_orig_node);
  438. max_orig_node = orig_node;
  439. }
  440. rcu_read_unlock();
  441. }
  442. if (max_orig_node) {
  443. cands[select].type = BATADV_DAT_CANDIDATE_ORIG;
  444. cands[select].orig_node = max_orig_node;
  445. batadv_dbg(BATADV_DBG_DAT, bat_priv,
  446. "dat_select_candidates() %d: selected %pM addr=%u dist=%u\n",
  447. select, max_orig_node->orig, max_orig_node->dat_addr,
  448. max);
  449. }
  450. *last_max = max;
  451. }
  452. /**
  453. * batadv_dat_select_candidates - selects the nodes which the DHT message has to
  454. * be sent to
  455. * @bat_priv: the bat priv with all the soft interface information
  456. * @ip_dst: ipv4 to look up in the DHT
  457. *
  458. * An originator O is selected if and only if its DHT_ID value is one of three
  459. * closest values (from the LEFT, with wrap around if needed) then the hash
  460. * value of the key. ip_dst is the key.
  461. *
  462. * Returns the candidate array of size BATADV_DAT_CANDIDATE_NUM
  463. */
  464. static struct batadv_dat_candidate *
  465. batadv_dat_select_candidates(struct batadv_priv *bat_priv, __be32 ip_dst)
  466. {
  467. int select;
  468. batadv_dat_addr_t last_max = BATADV_DAT_ADDR_MAX, ip_key;
  469. struct batadv_dat_candidate *res;
  470. if (!bat_priv->orig_hash)
  471. return NULL;
  472. res = kmalloc(BATADV_DAT_CANDIDATES_NUM * sizeof(*res), GFP_ATOMIC);
  473. if (!res)
  474. return NULL;
  475. ip_key = (batadv_dat_addr_t)batadv_hash_dat(&ip_dst,
  476. BATADV_DAT_ADDR_MAX);
  477. batadv_dbg(BATADV_DBG_DAT, bat_priv,
  478. "dat_select_candidates(): IP=%pI4 hash(IP)=%u\n", &ip_dst,
  479. ip_key);
  480. for (select = 0; select < BATADV_DAT_CANDIDATES_NUM; select++)
  481. batadv_choose_next_candidate(bat_priv, res, select, ip_key,
  482. &last_max);
  483. return res;
  484. }
  485. /**
  486. * batadv_dat_send_data - send a payload to the selected candidates
  487. * @bat_priv: the bat priv with all the soft interface information
  488. * @skb: payload to send
  489. * @ip: the DHT key
  490. * @packet_subtype: unicast4addr packet subtype to use
  491. *
  492. * In this function the skb is copied by means of pskb_copy() and is sent as
  493. * unicast packet to each of the selected candidates
  494. *
  495. * Returns true if the packet is sent to at least one candidate, false otherwise
  496. */
  497. static bool batadv_dat_send_data(struct batadv_priv *bat_priv,
  498. struct sk_buff *skb, __be32 ip,
  499. int packet_subtype)
  500. {
  501. int i;
  502. bool ret = false;
  503. int send_status;
  504. struct batadv_neigh_node *neigh_node = NULL;
  505. struct sk_buff *tmp_skb;
  506. struct batadv_dat_candidate *cand;
  507. cand = batadv_dat_select_candidates(bat_priv, ip);
  508. if (!cand)
  509. goto out;
  510. batadv_dbg(BATADV_DBG_DAT, bat_priv, "DHT_SEND for %pI4\n", &ip);
  511. for (i = 0; i < BATADV_DAT_CANDIDATES_NUM; i++) {
  512. if (cand[i].type == BATADV_DAT_CANDIDATE_NOT_FOUND)
  513. continue;
  514. neigh_node = batadv_orig_node_get_router(cand[i].orig_node);
  515. if (!neigh_node)
  516. goto free_orig;
  517. tmp_skb = pskb_copy(skb, GFP_ATOMIC);
  518. if (!batadv_unicast_4addr_prepare_skb(bat_priv, tmp_skb,
  519. cand[i].orig_node,
  520. packet_subtype)) {
  521. kfree_skb(tmp_skb);
  522. goto free_neigh;
  523. }
  524. send_status = batadv_send_skb_packet(tmp_skb,
  525. neigh_node->if_incoming,
  526. neigh_node->addr);
  527. if (send_status == NET_XMIT_SUCCESS) {
  528. /* count the sent packet */
  529. switch (packet_subtype) {
  530. case BATADV_P_DAT_DHT_GET:
  531. batadv_inc_counter(bat_priv,
  532. BATADV_CNT_DAT_GET_TX);
  533. break;
  534. case BATADV_P_DAT_DHT_PUT:
  535. batadv_inc_counter(bat_priv,
  536. BATADV_CNT_DAT_PUT_TX);
  537. break;
  538. }
  539. /* packet sent to a candidate: return true */
  540. ret = true;
  541. }
  542. free_neigh:
  543. batadv_neigh_node_free_ref(neigh_node);
  544. free_orig:
  545. batadv_orig_node_free_ref(cand[i].orig_node);
  546. }
  547. out:
  548. kfree(cand);
  549. return ret;
  550. }
  551. /**
  552. * batadv_dat_hash_free - free the local DAT hash table
  553. * @bat_priv: the bat priv with all the soft interface information
  554. */
  555. static void batadv_dat_hash_free(struct batadv_priv *bat_priv)
  556. {
  557. if (!bat_priv->dat.hash)
  558. return;
  559. __batadv_dat_purge(bat_priv, NULL);
  560. batadv_hash_destroy(bat_priv->dat.hash);
  561. bat_priv->dat.hash = NULL;
  562. }
  563. /**
  564. * batadv_dat_init - initialise the DAT internals
  565. * @bat_priv: the bat priv with all the soft interface information
  566. */
  567. int batadv_dat_init(struct batadv_priv *bat_priv)
  568. {
  569. if (bat_priv->dat.hash)
  570. return 0;
  571. bat_priv->dat.hash = batadv_hash_new(1024);
  572. if (!bat_priv->dat.hash)
  573. return -ENOMEM;
  574. batadv_dat_start_timer(bat_priv);
  575. return 0;
  576. }
  577. /**
  578. * batadv_dat_free - free the DAT internals
  579. * @bat_priv: the bat priv with all the soft interface information
  580. */
  581. void batadv_dat_free(struct batadv_priv *bat_priv)
  582. {
  583. cancel_delayed_work_sync(&bat_priv->dat.work);
  584. batadv_dat_hash_free(bat_priv);
  585. }
  586. /**
  587. * batadv_dat_cache_seq_print_text - print the local DAT hash table
  588. * @seq: seq file to print on
  589. * @offset: not used
  590. */
  591. int batadv_dat_cache_seq_print_text(struct seq_file *seq, void *offset)
  592. {
  593. struct net_device *net_dev = (struct net_device *)seq->private;
  594. struct batadv_priv *bat_priv = netdev_priv(net_dev);
  595. struct batadv_hashtable *hash = bat_priv->dat.hash;
  596. struct batadv_dat_entry *dat_entry;
  597. struct batadv_hard_iface *primary_if;
  598. struct hlist_head *head;
  599. unsigned long last_seen_jiffies;
  600. int last_seen_msecs, last_seen_secs, last_seen_mins;
  601. uint32_t i;
  602. primary_if = batadv_seq_print_text_primary_if_get(seq);
  603. if (!primary_if)
  604. goto out;
  605. seq_printf(seq, "Distributed ARP Table (%s):\n", net_dev->name);
  606. seq_printf(seq, " %-7s %-13s %5s\n", "IPv4", "MAC",
  607. "last-seen");
  608. for (i = 0; i < hash->size; i++) {
  609. head = &hash->table[i];
  610. rcu_read_lock();
  611. hlist_for_each_entry_rcu(dat_entry, head, hash_entry) {
  612. last_seen_jiffies = jiffies - dat_entry->last_update;
  613. last_seen_msecs = jiffies_to_msecs(last_seen_jiffies);
  614. last_seen_mins = last_seen_msecs / 60000;
  615. last_seen_msecs = last_seen_msecs % 60000;
  616. last_seen_secs = last_seen_msecs / 1000;
  617. seq_printf(seq, " * %15pI4 %14pM %6i:%02i\n",
  618. &dat_entry->ip, dat_entry->mac_addr,
  619. last_seen_mins, last_seen_secs);
  620. }
  621. rcu_read_unlock();
  622. }
  623. out:
  624. if (primary_if)
  625. batadv_hardif_free_ref(primary_if);
  626. return 0;
  627. }
  628. /**
  629. * batadv_arp_get_type - parse an ARP packet and gets the type
  630. * @bat_priv: the bat priv with all the soft interface information
  631. * @skb: packet to analyse
  632. * @hdr_size: size of the possible header before the ARP packet in the skb
  633. *
  634. * Returns the ARP type if the skb contains a valid ARP packet, 0 otherwise
  635. */
  636. static uint16_t batadv_arp_get_type(struct batadv_priv *bat_priv,
  637. struct sk_buff *skb, int hdr_size)
  638. {
  639. struct arphdr *arphdr;
  640. struct ethhdr *ethhdr;
  641. __be32 ip_src, ip_dst;
  642. uint8_t *hw_src, *hw_dst;
  643. uint16_t type = 0;
  644. /* pull the ethernet header */
  645. if (unlikely(!pskb_may_pull(skb, hdr_size + ETH_HLEN)))
  646. goto out;
  647. ethhdr = (struct ethhdr *)(skb->data + hdr_size);
  648. if (ethhdr->h_proto != htons(ETH_P_ARP))
  649. goto out;
  650. /* pull the ARP payload */
  651. if (unlikely(!pskb_may_pull(skb, hdr_size + ETH_HLEN +
  652. arp_hdr_len(skb->dev))))
  653. goto out;
  654. arphdr = (struct arphdr *)(skb->data + hdr_size + ETH_HLEN);
  655. /* Check whether the ARP packet carries a valid
  656. * IP information
  657. */
  658. if (arphdr->ar_hrd != htons(ARPHRD_ETHER))
  659. goto out;
  660. if (arphdr->ar_pro != htons(ETH_P_IP))
  661. goto out;
  662. if (arphdr->ar_hln != ETH_ALEN)
  663. goto out;
  664. if (arphdr->ar_pln != 4)
  665. goto out;
  666. /* Check for bad reply/request. If the ARP message is not sane, DAT
  667. * will simply ignore it
  668. */
  669. ip_src = batadv_arp_ip_src(skb, hdr_size);
  670. ip_dst = batadv_arp_ip_dst(skb, hdr_size);
  671. if (ipv4_is_loopback(ip_src) || ipv4_is_multicast(ip_src) ||
  672. ipv4_is_loopback(ip_dst) || ipv4_is_multicast(ip_dst) ||
  673. ipv4_is_zeronet(ip_src) || ipv4_is_lbcast(ip_src) ||
  674. ipv4_is_zeronet(ip_dst) || ipv4_is_lbcast(ip_dst))
  675. goto out;
  676. hw_src = batadv_arp_hw_src(skb, hdr_size);
  677. if (is_zero_ether_addr(hw_src) || is_multicast_ether_addr(hw_src))
  678. goto out;
  679. /* we don't care about the destination MAC address in ARP requests */
  680. if (arphdr->ar_op != htons(ARPOP_REQUEST)) {
  681. hw_dst = batadv_arp_hw_dst(skb, hdr_size);
  682. if (is_zero_ether_addr(hw_dst) ||
  683. is_multicast_ether_addr(hw_dst))
  684. goto out;
  685. }
  686. type = ntohs(arphdr->ar_op);
  687. out:
  688. return type;
  689. }
  690. /**
  691. * batadv_dat_snoop_outgoing_arp_request - snoop the ARP request and try to
  692. * answer using DAT
  693. * @bat_priv: the bat priv with all the soft interface information
  694. * @skb: packet to check
  695. *
  696. * Returns true if the message has been sent to the dht candidates, false
  697. * otherwise. In case of true the message has to be enqueued to permit the
  698. * fallback
  699. */
  700. bool batadv_dat_snoop_outgoing_arp_request(struct batadv_priv *bat_priv,
  701. struct sk_buff *skb)
  702. {
  703. uint16_t type = 0;
  704. __be32 ip_dst, ip_src;
  705. uint8_t *hw_src;
  706. bool ret = false;
  707. struct batadv_dat_entry *dat_entry = NULL;
  708. struct sk_buff *skb_new;
  709. if (!atomic_read(&bat_priv->distributed_arp_table))
  710. goto out;
  711. type = batadv_arp_get_type(bat_priv, skb, 0);
  712. /* If the node gets an ARP_REQUEST it has to send a DHT_GET unicast
  713. * message to the selected DHT candidates
  714. */
  715. if (type != ARPOP_REQUEST)
  716. goto out;
  717. batadv_dbg_arp(bat_priv, skb, type, 0, "Parsing outgoing ARP REQUEST");
  718. ip_src = batadv_arp_ip_src(skb, 0);
  719. hw_src = batadv_arp_hw_src(skb, 0);
  720. ip_dst = batadv_arp_ip_dst(skb, 0);
  721. batadv_dat_entry_add(bat_priv, ip_src, hw_src);
  722. dat_entry = batadv_dat_entry_hash_find(bat_priv, ip_dst);
  723. if (dat_entry) {
  724. skb_new = arp_create(ARPOP_REPLY, ETH_P_ARP, ip_src,
  725. bat_priv->soft_iface, ip_dst, hw_src,
  726. dat_entry->mac_addr, hw_src);
  727. if (!skb_new)
  728. goto out;
  729. skb_reset_mac_header(skb_new);
  730. skb_new->protocol = eth_type_trans(skb_new,
  731. bat_priv->soft_iface);
  732. bat_priv->stats.rx_packets++;
  733. bat_priv->stats.rx_bytes += skb->len + ETH_HLEN;
  734. bat_priv->soft_iface->last_rx = jiffies;
  735. netif_rx(skb_new);
  736. batadv_dbg(BATADV_DBG_DAT, bat_priv, "ARP request replied locally\n");
  737. ret = true;
  738. } else {
  739. /* Send the request on the DHT */
  740. ret = batadv_dat_send_data(bat_priv, skb, ip_dst,
  741. BATADV_P_DAT_DHT_GET);
  742. }
  743. out:
  744. if (dat_entry)
  745. batadv_dat_entry_free_ref(dat_entry);
  746. return ret;
  747. }
  748. /**
  749. * batadv_dat_snoop_incoming_arp_request - snoop the ARP request and try to
  750. * answer using the local DAT storage
  751. * @bat_priv: the bat priv with all the soft interface information
  752. * @skb: packet to check
  753. * @hdr_size: size of the encapsulation header
  754. *
  755. * Returns true if the request has been answered, false otherwise
  756. */
  757. bool batadv_dat_snoop_incoming_arp_request(struct batadv_priv *bat_priv,
  758. struct sk_buff *skb, int hdr_size)
  759. {
  760. uint16_t type;
  761. __be32 ip_src, ip_dst;
  762. uint8_t *hw_src;
  763. struct sk_buff *skb_new;
  764. struct batadv_dat_entry *dat_entry = NULL;
  765. bool ret = false;
  766. int err;
  767. if (!atomic_read(&bat_priv->distributed_arp_table))
  768. goto out;
  769. type = batadv_arp_get_type(bat_priv, skb, hdr_size);
  770. if (type != ARPOP_REQUEST)
  771. goto out;
  772. hw_src = batadv_arp_hw_src(skb, hdr_size);
  773. ip_src = batadv_arp_ip_src(skb, hdr_size);
  774. ip_dst = batadv_arp_ip_dst(skb, hdr_size);
  775. batadv_dbg_arp(bat_priv, skb, type, hdr_size,
  776. "Parsing incoming ARP REQUEST");
  777. batadv_dat_entry_add(bat_priv, ip_src, hw_src);
  778. dat_entry = batadv_dat_entry_hash_find(bat_priv, ip_dst);
  779. if (!dat_entry)
  780. goto out;
  781. skb_new = arp_create(ARPOP_REPLY, ETH_P_ARP, ip_src,
  782. bat_priv->soft_iface, ip_dst, hw_src,
  783. dat_entry->mac_addr, hw_src);
  784. if (!skb_new)
  785. goto out;
  786. /* to preserve backwards compatibility, here the node has to answer
  787. * using the same packet type it received for the request. This is due
  788. * to that if a node is not using the 4addr packet format it may not
  789. * support it.
  790. */
  791. if (hdr_size == sizeof(struct batadv_unicast_4addr_packet))
  792. err = batadv_unicast_4addr_send_skb(bat_priv, skb_new,
  793. BATADV_P_DAT_CACHE_REPLY);
  794. else
  795. err = batadv_unicast_send_skb(bat_priv, skb_new);
  796. if (!err) {
  797. batadv_inc_counter(bat_priv, BATADV_CNT_DAT_CACHED_REPLY_TX);
  798. ret = true;
  799. }
  800. out:
  801. if (dat_entry)
  802. batadv_dat_entry_free_ref(dat_entry);
  803. if (ret)
  804. kfree_skb(skb);
  805. return ret;
  806. }
  807. /**
  808. * batadv_dat_snoop_outgoing_arp_reply - snoop the ARP reply and fill the DHT
  809. * @bat_priv: the bat priv with all the soft interface information
  810. * @skb: packet to check
  811. */
  812. void batadv_dat_snoop_outgoing_arp_reply(struct batadv_priv *bat_priv,
  813. struct sk_buff *skb)
  814. {
  815. uint16_t type;
  816. __be32 ip_src, ip_dst;
  817. uint8_t *hw_src, *hw_dst;
  818. if (!atomic_read(&bat_priv->distributed_arp_table))
  819. return;
  820. type = batadv_arp_get_type(bat_priv, skb, 0);
  821. if (type != ARPOP_REPLY)
  822. return;
  823. batadv_dbg_arp(bat_priv, skb, type, 0, "Parsing outgoing ARP REPLY");
  824. hw_src = batadv_arp_hw_src(skb, 0);
  825. ip_src = batadv_arp_ip_src(skb, 0);
  826. hw_dst = batadv_arp_hw_dst(skb, 0);
  827. ip_dst = batadv_arp_ip_dst(skb, 0);
  828. batadv_dat_entry_add(bat_priv, ip_src, hw_src);
  829. batadv_dat_entry_add(bat_priv, ip_dst, hw_dst);
  830. /* Send the ARP reply to the candidates for both the IP addresses that
  831. * the node got within the ARP reply
  832. */
  833. batadv_dat_send_data(bat_priv, skb, ip_src, BATADV_P_DAT_DHT_PUT);
  834. batadv_dat_send_data(bat_priv, skb, ip_dst, BATADV_P_DAT_DHT_PUT);
  835. }
  836. /**
  837. * batadv_dat_snoop_incoming_arp_reply - snoop the ARP reply and fill the local
  838. * DAT storage only
  839. * @bat_priv: the bat priv with all the soft interface information
  840. * @skb: packet to check
  841. * @hdr_size: siaze of the encapsulation header
  842. */
  843. bool batadv_dat_snoop_incoming_arp_reply(struct batadv_priv *bat_priv,
  844. struct sk_buff *skb, int hdr_size)
  845. {
  846. uint16_t type;
  847. __be32 ip_src, ip_dst;
  848. uint8_t *hw_src, *hw_dst;
  849. bool ret = false;
  850. if (!atomic_read(&bat_priv->distributed_arp_table))
  851. goto out;
  852. type = batadv_arp_get_type(bat_priv, skb, hdr_size);
  853. if (type != ARPOP_REPLY)
  854. goto out;
  855. batadv_dbg_arp(bat_priv, skb, type, hdr_size,
  856. "Parsing incoming ARP REPLY");
  857. hw_src = batadv_arp_hw_src(skb, hdr_size);
  858. ip_src = batadv_arp_ip_src(skb, hdr_size);
  859. hw_dst = batadv_arp_hw_dst(skb, hdr_size);
  860. ip_dst = batadv_arp_ip_dst(skb, hdr_size);
  861. /* Update our internal cache with both the IP addresses the node got
  862. * within the ARP reply
  863. */
  864. batadv_dat_entry_add(bat_priv, ip_src, hw_src);
  865. batadv_dat_entry_add(bat_priv, ip_dst, hw_dst);
  866. /* if this REPLY is directed to a client of mine, let's deliver the
  867. * packet to the interface
  868. */
  869. ret = !batadv_is_my_client(bat_priv, hw_dst);
  870. out:
  871. if (ret)
  872. kfree_skb(skb);
  873. /* if ret == false -> packet has to be delivered to the interface */
  874. return ret;
  875. }
  876. /**
  877. * batadv_dat_drop_broadcast_packet - check if an ARP request has to be dropped
  878. * (because the node has already got the reply via DAT) or not
  879. * @bat_priv: the bat priv with all the soft interface information
  880. * @forw_packet: the broadcast packet
  881. *
  882. * Returns true if the node can drop the packet, false otherwise
  883. */
  884. bool batadv_dat_drop_broadcast_packet(struct batadv_priv *bat_priv,
  885. struct batadv_forw_packet *forw_packet)
  886. {
  887. uint16_t type;
  888. __be32 ip_dst;
  889. struct batadv_dat_entry *dat_entry = NULL;
  890. bool ret = false;
  891. const size_t bcast_len = sizeof(struct batadv_bcast_packet);
  892. if (!atomic_read(&bat_priv->distributed_arp_table))
  893. goto out;
  894. /* If this packet is an ARP_REQUEST and the node already has the
  895. * information that it is going to ask, then the packet can be dropped
  896. */
  897. if (forw_packet->num_packets)
  898. goto out;
  899. type = batadv_arp_get_type(bat_priv, forw_packet->skb, bcast_len);
  900. if (type != ARPOP_REQUEST)
  901. goto out;
  902. ip_dst = batadv_arp_ip_dst(forw_packet->skb, bcast_len);
  903. dat_entry = batadv_dat_entry_hash_find(bat_priv, ip_dst);
  904. /* check if the node already got this entry */
  905. if (!dat_entry) {
  906. batadv_dbg(BATADV_DBG_DAT, bat_priv,
  907. "ARP Request for %pI4: fallback\n", &ip_dst);
  908. goto out;
  909. }
  910. batadv_dbg(BATADV_DBG_DAT, bat_priv,
  911. "ARP Request for %pI4: fallback prevented\n", &ip_dst);
  912. ret = true;
  913. out:
  914. if (dat_entry)
  915. batadv_dat_entry_free_ref(dat_entry);
  916. return ret;
  917. }