net/batman-adv/network-coding.c

   1 /* Copyright (C) 2012-2013 B.A.T.M.A.N. contributors:
   2  *
   3  * Martin Hundebøll, Jeppe Ledet-Pedersen
   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
  20 #include <linux/debugfs.h>
  21
  22 #include "main.h"
  23 #include "hash.h"
  24 #include "network-coding.h"
  25 #include "send.h"
  26 #include "originator.h"
  27 #include "hard-interface.h"
  28
  29 static struct lock_class_key batadv_nc_coding_hash_lock_class_key;
  30
  31 static void batadv_nc_worker(struct work_struct *work);
  32
  33 /**
  34  * batadv_nc_start_timer - initialise the nc periodic worker
  35  * @bat_priv: the bat priv with all the soft interface information
  36  */
  37 static void batadv_nc_start_timer(struct batadv_priv *bat_priv)
  38 {
  39         queue_delayed_work(batadv_event_workqueue, &bat_priv->nc.work,
  40                            msecs_to_jiffies(10));
  41 }
  42
  43 /**
  44  * batadv_nc_init - initialise coding hash table and start house keeping
  45  * @bat_priv: the bat priv with all the soft interface information
  46  */
  47 int batadv_nc_init(struct batadv_priv *bat_priv)
  48 {
  49         bat_priv->nc.timestamp_fwd_flush = jiffies;
  50
  51         if (bat_priv->nc.coding_hash)
  52                 return 0;
  53
  54         bat_priv->nc.coding_hash = batadv_hash_new(128);
  55         if (!bat_priv->nc.coding_hash)
  56                 goto err;
  57
  58         batadv_hash_set_lock_class(bat_priv->nc.coding_hash,
  59                                    &batadv_nc_coding_hash_lock_class_key);
  60
  61         INIT_DELAYED_WORK(&bat_priv->nc.work, batadv_nc_worker);
  62         batadv_nc_start_timer(bat_priv);
  63
  64         return 0;
  65
  66 err:
  67         return -ENOMEM;
  68 }
  69
  70 /**
  71  * batadv_nc_init_bat_priv - initialise the nc specific bat_priv variables
  72  * @bat_priv: the bat priv with all the soft interface information
  73  */
  74 void batadv_nc_init_bat_priv(struct batadv_priv *bat_priv)
  75 {
  76         atomic_set(&bat_priv->network_coding, 1);
  77         bat_priv->nc.min_tq = 200;
  78         bat_priv->nc.max_fwd_delay = 10;
  79 }
  80
  81 /**
  82  * batadv_nc_init_orig - initialise the nc fields of an orig_node
  83  * @orig_node: the orig_node which is going to be initialised
  84  */
  85 void batadv_nc_init_orig(struct batadv_orig_node *orig_node)
  86 {
  87         INIT_LIST_HEAD(&orig_node->in_coding_list);
  88         INIT_LIST_HEAD(&orig_node->out_coding_list);
  89         spin_lock_init(&orig_node->in_coding_list_lock);
  90         spin_lock_init(&orig_node->out_coding_list_lock);
  91 }
  92
  93 /**
  94  * batadv_nc_node_free_rcu - rcu callback to free an nc node and remove
  95  *  its refcount on the orig_node
  96  * @rcu: rcu pointer of the nc node
  97  */
  98 static void batadv_nc_node_free_rcu(struct rcu_head *rcu)
  99 {
 100         struct batadv_nc_node *nc_node;
 101
 102         nc_node = container_of(rcu, struct batadv_nc_node, rcu);
 103         batadv_orig_node_free_ref(nc_node->orig_node);
 104         kfree(nc_node);
 105 }
 106
 107 /**
 108  * batadv_nc_node_free_ref - decrements the nc node refcounter and possibly
 109  * frees it
 110  * @nc_node: the nc node to free
 111  */
 112 static void batadv_nc_node_free_ref(struct batadv_nc_node *nc_node)
 113 {
 114         if (atomic_dec_and_test(&nc_node->refcount))
 115                 call_rcu(&nc_node->rcu, batadv_nc_node_free_rcu);
 116 }
 117
 118 /**
 119  * batadv_nc_path_free_ref - decrements the nc path refcounter and possibly
 120  * frees it
 121  * @nc_path: the nc node to free
 122  */
 123 static void batadv_nc_path_free_ref(struct batadv_nc_path *nc_path)
 124 {
 125         if (atomic_dec_and_test(&nc_path->refcount))
 126                 kfree_rcu(nc_path, rcu);
 127 }
 128
 129 /**
 130  * batadv_nc_packet_free - frees nc packet
 131  * @nc_packet: the nc packet to free
 132  */
 133 static void batadv_nc_packet_free(struct batadv_nc_packet *nc_packet)
 134 {
 135         if (nc_packet->skb)
 136                 kfree_skb(nc_packet->skb);
 137
 138         batadv_nc_path_free_ref(nc_packet->nc_path);
 139         kfree(nc_packet);
 140 }
 141
 142 /**
 143  * batadv_nc_to_purge_nc_node - checks whether an nc node has to be purged
 144  * @bat_priv: the bat priv with all the soft interface information
 145  * @nc_node: the nc node to check
 146  *
 147  * Returns true if the entry has to be purged now, false otherwise
 148  */
 149 static bool batadv_nc_to_purge_nc_node(struct batadv_priv *bat_priv,
 150                                        struct batadv_nc_node *nc_node)
 151 {
 152         if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
 153                 return true;
 154
 155         return batadv_has_timed_out(nc_node->last_seen, BATADV_NC_NODE_TIMEOUT);
 156 }
 157
 158 /**
 159  * batadv_nc_to_purge_nc_path_coding - checks whether an nc path has timed out
 160  * @bat_priv: the bat priv with all the soft interface information
 161  * @nc_path: the nc path to check
 162  *
 163  * Returns true if the entry has to be purged now, false otherwise
 164  */
 165 static bool batadv_nc_to_purge_nc_path_coding(struct batadv_priv *bat_priv,
 166                                               struct batadv_nc_path *nc_path)
 167 {
 168         if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
 169                 return true;
 170
 171         /* purge the path when no packets has been added for 10 times the
 172          * max_fwd_delay time
 173          */
 174         return batadv_has_timed_out(nc_path->last_valid,
 175                                     bat_priv->nc.max_fwd_delay * 10);
 176 }
 177
 178 /**
 179  * batadv_nc_purge_orig_nc_nodes - go through list of nc nodes and purge stale
 180  *  entries
 181  * @bat_priv: the bat priv with all the soft interface information
 182  * @list: list of nc nodes
 183  * @lock: nc node list lock
 184  * @to_purge: function in charge to decide whether an entry has to be purged or
 185  *            not. This function takes the nc node as argument and has to return
 186  *            a boolean value: true if the entry has to be deleted, false
 187  *            otherwise
 188  */
 189 static void
 190 batadv_nc_purge_orig_nc_nodes(struct batadv_priv *bat_priv,
 191                               struct list_head *list,
 192                               spinlock_t *lock,
 193                               bool (*to_purge)(struct batadv_priv *,
 194                                                struct batadv_nc_node *))
 195 {
 196         struct batadv_nc_node *nc_node, *nc_node_tmp;
 197
 198         /* For each nc_node in list */
 199         spin_lock_bh(lock);
 200         list_for_each_entry_safe(nc_node, nc_node_tmp, list, list) {
 201                 /* if an helper function has been passed as parameter,
 202                  * ask it if the entry has to be purged or not
 203                  */
 204                 if (to_purge && !to_purge(bat_priv, nc_node))
 205                         continue;
 206
 207                 batadv_dbg(BATADV_DBG_NC, bat_priv,
 208                            "Removing nc_node %pM -> %pM\n",
 209                            nc_node->addr, nc_node->orig_node->orig);
 210                 list_del_rcu(&nc_node->list);
 211                 batadv_nc_node_free_ref(nc_node);
 212         }
 213         spin_unlock_bh(lock);
 214 }
 215
 216 /**
 217  * batadv_nc_purge_orig - purges all nc node data attached of the given
 218  *  originator
 219  * @bat_priv: the bat priv with all the soft interface information
 220  * @orig_node: orig_node with the nc node entries to be purged
 221  * @to_purge: function in charge to decide whether an entry has to be purged or
 222  *            not. This function takes the nc node as argument and has to return
 223  *            a boolean value: true is the entry has to be deleted, false
 224  *            otherwise
 225  */
 226 void batadv_nc_purge_orig(struct batadv_priv *bat_priv,
 227                           struct batadv_orig_node *orig_node,
 228                           bool (*to_purge)(struct batadv_priv *,
 229                                            struct batadv_nc_node *))
 230 {
 231         /* Check ingoing nc_node's of this orig_node */
 232         batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->in_coding_list,
 233                                       &orig_node->in_coding_list_lock,
 234                                       to_purge);
 235
 236         /* Check outgoing nc_node's of this orig_node */
 237         batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->out_coding_list,
 238                                       &orig_node->out_coding_list_lock,
 239                                       to_purge);
 240 }
 241
 242 /**
 243  * batadv_nc_purge_orig_hash - traverse entire originator hash to check if they
 244  *  have timed out nc nodes
 245  * @bat_priv: the bat priv with all the soft interface information
 246  */
 247 static void batadv_nc_purge_orig_hash(struct batadv_priv *bat_priv)
 248 {
 249         struct batadv_hashtable *hash = bat_priv->orig_hash;
 250         struct hlist_head *head;
 251         struct batadv_orig_node *orig_node;
 252         uint32_t i;
 253
 254         if (!hash)
 255                 return;
 256
 257         /* For each orig_node */
 258         for (i = 0; i < hash->size; i++) {
 259                 head = &hash->table[i];
 260
 261                 rcu_read_lock();
 262                 hlist_for_each_entry_rcu(orig_node, head, hash_entry)
 263                         batadv_nc_purge_orig(bat_priv, orig_node,
 264                                              batadv_nc_to_purge_nc_node);
 265                 rcu_read_unlock();
 266         }
 267 }
 268
 269 /**
 270  * batadv_nc_purge_paths - traverse all nc paths part of the hash and remove
 271  *  unused ones
 272  * @bat_priv: the bat priv with all the soft interface information
 273  * @hash: hash table containing the nc paths to check
 274  * @to_purge: function in charge to decide whether an entry has to be purged or
 275  *            not. This function takes the nc node as argument and has to return
 276  *            a boolean value: true is the entry has to be deleted, false
 277  *            otherwise
 278  */
 279 static void batadv_nc_purge_paths(struct batadv_priv *bat_priv,
 280                                   struct batadv_hashtable *hash,
 281                                   bool (*to_purge)(struct batadv_priv *,
 282                                                    struct batadv_nc_path *))
 283 {
 284         struct hlist_head *head;
 285         struct hlist_node *node_tmp;
 286         struct batadv_nc_path *nc_path;
 287         spinlock_t *lock; /* Protects lists in hash */
 288         uint32_t i;
 289
 290         for (i = 0; i < hash->size; i++) {
 291                 head = &hash->table[i];
 292                 lock = &hash->list_locks[i];
 293
 294                 /* For each nc_path in this bin */
 295                 spin_lock_bh(lock);
 296                 hlist_for_each_entry_safe(nc_path, node_tmp, head, hash_entry) {
 297                         /* if an helper function has been passed as parameter,
 298                          * ask it if the entry has to be purged or not
 299                          */
 300                         if (to_purge && !to_purge(bat_priv, nc_path))
 301                                 continue;
 302
 303                         /* purging an non-empty nc_path should never happen, but
 304                          * is observed under high CPU load. Delay the purging
 305                          * until next iteration to allow the packet_list to be
 306                          * emptied first.
 307                          */
 308                         if (!unlikely(list_empty(&nc_path->packet_list))) {
 309                                 net_ratelimited_function(printk,
 310                                                          KERN_WARNING
 311                                                          "Skipping free of non-empty nc_path (%pM -> %pM)!\n",
 312                                                          nc_path->prev_hop,
 313                                                          nc_path->next_hop);
 314                                 continue;
 315                         }
 316
 317                         /* nc_path is unused, so remove it */
 318                         batadv_dbg(BATADV_DBG_NC, bat_priv,
 319                                    "Remove nc_path %pM -> %pM\n",
 320                                    nc_path->prev_hop, nc_path->next_hop);
 321                         hlist_del_rcu(&nc_path->hash_entry);
 322                         batadv_nc_path_free_ref(nc_path);
 323                 }
 324                 spin_unlock_bh(lock);
 325         }
 326 }
 327
 328 /**
 329  * batadv_nc_hash_key_gen - computes the nc_path hash key
 330  * @key: buffer to hold the final hash key
 331  * @src: source ethernet mac address going into the hash key
 332  * @dst: destination ethernet mac address going into the hash key
 333  */
 334 static void batadv_nc_hash_key_gen(struct batadv_nc_path *key, const char *src,
 335                                    const char *dst)
 336 {
 337         memcpy(key->prev_hop, src, sizeof(key->prev_hop));
 338         memcpy(key->next_hop, dst, sizeof(key->next_hop));
 339 }
 340
 341 /**
 342  * batadv_nc_hash_choose - compute the hash value for an nc path
 343  * @data: data to hash
 344  * @size: size of the hash table
 345  *
 346  * Returns the selected index in the hash table for the given data.
 347  */
 348 static uint32_t batadv_nc_hash_choose(const void *data, uint32_t size)
 349 {
 350         const struct batadv_nc_path *nc_path = data;
 351         uint32_t hash = 0;
 352
 353         hash = batadv_hash_bytes(hash, &nc_path->prev_hop,
 354                                  sizeof(nc_path->prev_hop));
 355         hash = batadv_hash_bytes(hash, &nc_path->next_hop,
 356                                  sizeof(nc_path->next_hop));
 357
 358         hash += (hash << 3);
 359         hash ^= (hash >> 11);
 360         hash += (hash << 15);
 361
 362         return hash % size;
 363 }
 364
 365 /**
 366  * batadv_nc_hash_compare - comparing function used in the network coding hash
 367  *  tables
 368  * @node: node in the local table
 369  * @data2: second object to compare the node to
 370  *
 371  * Returns 1 if the two entry are the same, 0 otherwise
 372  */
 373 static int batadv_nc_hash_compare(const struct hlist_node *node,
 374                                   const void *data2)
 375 {
 376         const struct batadv_nc_path *nc_path1, *nc_path2;
 377
 378         nc_path1 = container_of(node, struct batadv_nc_path, hash_entry);
 379         nc_path2 = data2;
 380
 381         /* Return 1 if the two keys are identical */
 382         if (memcmp(nc_path1->prev_hop, nc_path2->prev_hop,
 383                    sizeof(nc_path1->prev_hop)) != 0)
 384                 return 0;
 385
 386         if (memcmp(nc_path1->next_hop, nc_path2->next_hop,
 387                    sizeof(nc_path1->next_hop)) != 0)
 388                 return 0;
 389
 390         return 1;
 391 }
 392
 393 /**
 394  * batadv_nc_hash_find - search for an existing nc path and return it
 395  * @hash: hash table containing the nc path
 396  * @data: search key
 397  *
 398  * Returns the nc_path if found, NULL otherwise.
 399  */
 400 static struct batadv_nc_path *
 401 batadv_nc_hash_find(struct batadv_hashtable *hash,
 402                     void *data)
 403 {
 404         struct hlist_head *head;
 405         struct batadv_nc_path *nc_path, *nc_path_tmp = NULL;
 406         int index;
 407
 408         if (!hash)
 409                 return NULL;
 410
 411         index = batadv_nc_hash_choose(data, hash->size);
 412         head = &hash->table[index];
 413
 414         rcu_read_lock();
 415         hlist_for_each_entry_rcu(nc_path, head, hash_entry) {
 416                 if (!batadv_nc_hash_compare(&nc_path->hash_entry, data))
 417                         continue;
 418
 419                 if (!atomic_inc_not_zero(&nc_path->refcount))
 420                         continue;
 421
 422                 nc_path_tmp = nc_path;
 423                 break;
 424         }
 425         rcu_read_unlock();
 426
 427         return nc_path_tmp;
 428 }
 429
 430 /**
 431  * batadv_nc_send_packet - send non-coded packet and free nc_packet struct
 432  * @nc_packet: the nc packet to send
 433  */
 434 static void batadv_nc_send_packet(struct batadv_nc_packet *nc_packet)
 435 {
 436         batadv_send_skb_packet(nc_packet->skb,
 437                                nc_packet->neigh_node->if_incoming,
 438                                nc_packet->nc_path->next_hop);
 439         nc_packet->skb = NULL;
 440         batadv_nc_packet_free(nc_packet);
 441 }
 442
 443 /**
 444  * batadv_nc_fwd_flush - Checks the timestamp of the given nc packet.
 445  * @bat_priv: the bat priv with all the soft interface information
 446  * @nc_path: the nc path the packet belongs to
 447  * @nc_packet: the nc packet to be checked
 448  *
 449  * Checks whether the given nc packet has hit its forward timeout. If so, the
 450  * packet is no longer delayed, immediately sent and the entry deleted from the
 451  * queue. Has to be called with the appropriate locks.
 452  *
 453  * Returns false as soon as the entry in the fifo queue has not been timed out
 454  * yet and true otherwise.
 455  */
 456 static bool batadv_nc_fwd_flush(struct batadv_priv *bat_priv,
 457                                 struct batadv_nc_path *nc_path,
 458                                 struct batadv_nc_packet *nc_packet)
 459 {
 460         unsigned long timeout = bat_priv->nc.max_fwd_delay;
 461
 462         /* Packets are added to tail, so the remaining packets did not time
 463          * out and we can stop processing the current queue
 464          */
 465         if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_ACTIVE &&
 466             !batadv_has_timed_out(nc_packet->timestamp, timeout))
 467                 return false;
 468
 469         /* Send packet */
 470         batadv_inc_counter(bat_priv, BATADV_CNT_FORWARD);
 471         batadv_add_counter(bat_priv, BATADV_CNT_FORWARD_BYTES,
 472                            nc_packet->skb->len + ETH_HLEN);
 473         list_del(&nc_packet->list);
 474         batadv_nc_send_packet(nc_packet);
 475
 476         return true;
 477 }
 478
 479 /**
 480  * batadv_nc_process_nc_paths - traverse given nc packet pool and free timed out
 481  *  nc packets
 482  * @bat_priv: the bat priv with all the soft interface information
 483  * @hash: to be processed hash table
 484  * @process_fn: Function called to process given nc packet. Should return true
 485  *              to encourage this function to proceed with the next packet.
 486  *              Otherwise the rest of the current queue is skipped.
 487  */
 488 static void
 489 batadv_nc_process_nc_paths(struct batadv_priv *bat_priv,
 490                            struct batadv_hashtable *hash,
 491                            bool (*process_fn)(struct batadv_priv *,
 492                                               struct batadv_nc_path *,
 493                                               struct batadv_nc_packet *))
 494 {
 495         struct hlist_head *head;
 496         struct batadv_nc_packet *nc_packet, *nc_packet_tmp;
 497         struct batadv_nc_path *nc_path;
 498         bool ret;
 499         int i;
 500
 501         if (!hash)
 502                 return;
 503
 504         /* Loop hash table bins */
 505         for (i = 0; i < hash->size; i++) {
 506                 head = &hash->table[i];
 507
 508                 /* Loop coding paths */
 509                 rcu_read_lock();
 510                 hlist_for_each_entry_rcu(nc_path, head, hash_entry) {
 511                         /* Loop packets */
 512                         spin_lock_bh(&nc_path->packet_list_lock);
 513                         list_for_each_entry_safe(nc_packet, nc_packet_tmp,
 514                                                  &nc_path->packet_list, list) {
 515                                 ret = process_fn(bat_priv, nc_path, nc_packet);
 516                                 if (!ret)
 517                                         break;
 518                         }
 519                         spin_unlock_bh(&nc_path->packet_list_lock);
 520                 }
 521                 rcu_read_unlock();
 522         }
 523 }
 524
 525 /**
 526  * batadv_nc_worker - periodic task for house keeping related to network coding
 527  * @work: kernel work struct
 528  */
 529 static void batadv_nc_worker(struct work_struct *work)
 530 {
 531         struct delayed_work *delayed_work;
 532         struct batadv_priv_nc *priv_nc;
 533         struct batadv_priv *bat_priv;
 534         unsigned long timeout;
 535
 536         delayed_work = container_of(work, struct delayed_work, work);
 537         priv_nc = container_of(delayed_work, struct batadv_priv_nc, work);
 538         bat_priv = container_of(priv_nc, struct batadv_priv, nc);
 539
 540         batadv_nc_purge_orig_hash(bat_priv);
 541         batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash,
 542                               batadv_nc_to_purge_nc_path_coding);
 543
 544         timeout = bat_priv->nc.max_fwd_delay;
 545
 546         if (batadv_has_timed_out(bat_priv->nc.timestamp_fwd_flush, timeout)) {
 547                 batadv_nc_process_nc_paths(bat_priv, bat_priv->nc.coding_hash,
 548                                            batadv_nc_fwd_flush);
 549                 bat_priv->nc.timestamp_fwd_flush = jiffies;
 550         }
 551
 552         /* Schedule a new check */
 553         batadv_nc_start_timer(bat_priv);
 554 }
 555
 556 /**
 557  * batadv_can_nc_with_orig - checks whether the given orig node is suitable for
 558  *  coding or not
 559  * @bat_priv: the bat priv with all the soft interface information
 560  * @orig_node: neighboring orig node which may be used as nc candidate
 561  * @ogm_packet: incoming ogm packet also used for the checks
 562  *
 563  * Returns true if:
 564  *  1) The OGM must have the most recent sequence number.
 565  *  2) The TTL must be decremented by one and only one.
 566  *  3) The OGM must be received from the first hop from orig_node.
 567  *  4) The TQ value of the OGM must be above bat_priv->nc.min_tq.
 568  */
 569 static bool batadv_can_nc_with_orig(struct batadv_priv *bat_priv,
 570                                     struct batadv_orig_node *orig_node,
 571                                     struct batadv_ogm_packet *ogm_packet)
 572 {
 573         if (orig_node->last_real_seqno != ogm_packet->seqno)
 574                 return false;
 575         if (orig_node->last_ttl != ogm_packet->header.ttl + 1)
 576                 return false;
 577         if (!batadv_compare_eth(ogm_packet->orig, ogm_packet->prev_sender))
 578                 return false;
 579         if (ogm_packet->tq < bat_priv->nc.min_tq)
 580                 return false;
 581
 582         return true;
 583 }
 584
 585 /**
 586  * batadv_nc_find_nc_node - search for an existing nc node and return it
 587  * @orig_node: orig node originating the ogm packet
 588  * @orig_neigh_node: neighboring orig node from which we received the ogm packet
 589  *  (can be equal to orig_node)
 590  * @in_coding: traverse incoming or outgoing network coding list
 591  *
 592  * Returns the nc_node if found, NULL otherwise.
 593  */
 594 static struct batadv_nc_node
 595 *batadv_nc_find_nc_node(struct batadv_orig_node *orig_node,
 596                         struct batadv_orig_node *orig_neigh_node,
 597                         bool in_coding)
 598 {
 599         struct batadv_nc_node *nc_node, *nc_node_out = NULL;
 600         struct list_head *list;
 601
 602         if (in_coding)
 603                 list = &orig_neigh_node->in_coding_list;
 604         else
 605                 list = &orig_neigh_node->out_coding_list;
 606
 607         /* Traverse list of nc_nodes to orig_node */
 608         rcu_read_lock();
 609         list_for_each_entry_rcu(nc_node, list, list) {
 610                 if (!batadv_compare_eth(nc_node->addr, orig_node->orig))
 611                         continue;
 612
 613                 if (!atomic_inc_not_zero(&nc_node->refcount))
 614                         continue;
 615
 616                 /* Found a match */
 617                 nc_node_out = nc_node;
 618                 break;
 619         }
 620         rcu_read_unlock();
 621
 622         return nc_node_out;
 623 }
 624
 625 /**
 626  * batadv_nc_get_nc_node - retrieves an nc node or creates the entry if it was
 627  *  not found
 628  * @bat_priv: the bat priv with all the soft interface information
 629  * @orig_node: orig node originating the ogm packet
 630  * @orig_neigh_node: neighboring orig node from which we received the ogm packet
 631  *  (can be equal to orig_node)
 632  * @in_coding: traverse incoming or outgoing network coding list
 633  *
 634  * Returns the nc_node if found or created, NULL in case of an error.
 635  */
 636 static struct batadv_nc_node
 637 *batadv_nc_get_nc_node(struct batadv_priv *bat_priv,
 638                        struct batadv_orig_node *orig_node,
 639                        struct batadv_orig_node *orig_neigh_node,
 640                        bool in_coding)
 641 {
 642         struct batadv_nc_node *nc_node;
 643         spinlock_t *lock; /* Used to lock list selected by "int in_coding" */
 644         struct list_head *list;
 645
 646         /* Check if nc_node is already added */
 647         nc_node = batadv_nc_find_nc_node(orig_node, orig_neigh_node, in_coding);
 648
 649         /* Node found */
 650         if (nc_node)
 651                 return nc_node;
 652
 653         nc_node = kzalloc(sizeof(*nc_node), GFP_ATOMIC);
 654         if (!nc_node)
 655                 return NULL;
 656
 657         if (!atomic_inc_not_zero(&orig_neigh_node->refcount))
 658                 goto free;
 659
 660         /* Initialize nc_node */
 661         INIT_LIST_HEAD(&nc_node->list);
 662         memcpy(nc_node->addr, orig_node->orig, ETH_ALEN);
 663         nc_node->orig_node = orig_neigh_node;
 664         atomic_set(&nc_node->refcount, 2);
 665
 666         /* Select ingoing or outgoing coding node */
 667         if (in_coding) {
 668                 lock = &orig_neigh_node->in_coding_list_lock;
 669                 list = &orig_neigh_node->in_coding_list;
 670         } else {
 671                 lock = &orig_neigh_node->out_coding_list_lock;
 672                 list = &orig_neigh_node->out_coding_list;
 673         }
 674
 675         batadv_dbg(BATADV_DBG_NC, bat_priv, "Adding nc_node %pM -> %pM\n",
 676                    nc_node->addr, nc_node->orig_node->orig);
 677
 678         /* Add nc_node to orig_node */
 679         spin_lock_bh(lock);
 680         list_add_tail_rcu(&nc_node->list, list);
 681         spin_unlock_bh(lock);
 682
 683         return nc_node;
 684
 685 free:
 686         kfree(nc_node);
 687         return NULL;
 688 }
 689
 690 /**
 691  * batadv_nc_update_nc_node - updates stored incoming and outgoing nc node structs
 692  *  (best called on incoming OGMs)
 693  * @bat_priv: the bat priv with all the soft interface information
 694  * @orig_node: orig node originating the ogm packet
 695  * @orig_neigh_node: neighboring orig node from which we received the ogm packet
 696  *  (can be equal to orig_node)
 697  * @ogm_packet: incoming ogm packet
 698  * @is_single_hop_neigh: orig_node is a single hop neighbor
 699  */
 700 void batadv_nc_update_nc_node(struct batadv_priv *bat_priv,
 701                               struct batadv_orig_node *orig_node,
 702                               struct batadv_orig_node *orig_neigh_node,
 703                               struct batadv_ogm_packet *ogm_packet,
 704                               int is_single_hop_neigh)
 705 {
 706         struct batadv_nc_node *in_nc_node = NULL, *out_nc_node = NULL;
 707
 708         /* Check if network coding is enabled */
 709         if (!atomic_read(&bat_priv->network_coding))
 710                 goto out;
 711
 712         /* accept ogms from 'good' neighbors and single hop neighbors */
 713         if (!batadv_can_nc_with_orig(bat_priv, orig_node, ogm_packet) &&
 714             !is_single_hop_neigh)
 715                 goto out;
 716
 717         /* Add orig_node as in_nc_node on hop */
 718         in_nc_node = batadv_nc_get_nc_node(bat_priv, orig_node,
 719                                            orig_neigh_node, true);
 720         if (!in_nc_node)
 721                 goto out;
 722
 723         in_nc_node->last_seen = jiffies;
 724
 725         /* Add hop as out_nc_node on orig_node */
 726         out_nc_node = batadv_nc_get_nc_node(bat_priv, orig_neigh_node,
 727                                             orig_node, false);
 728         if (!out_nc_node)
 729                 goto out;
 730
 731         out_nc_node->last_seen = jiffies;
 732
 733 out:
 734         if (in_nc_node)
 735                 batadv_nc_node_free_ref(in_nc_node);
 736         if (out_nc_node)
 737                 batadv_nc_node_free_ref(out_nc_node);
 738 }
 739
 740 /**
 741  * batadv_nc_get_path - get existing nc_path or allocate a new one
 742  * @bat_priv: the bat priv with all the soft interface information
 743  * @hash: hash table containing the nc path
 744  * @src: ethernet source address - first half of the nc path search key
 745  * @dst: ethernet destination address - second half of the nc path search key
 746  *
 747  * Returns pointer to nc_path if the path was found or created, returns NULL
 748  * on error.
 749  */
 750 static struct batadv_nc_path *batadv_nc_get_path(struct batadv_priv *bat_priv,
 751                                                  struct batadv_hashtable *hash,
 752                                                  uint8_t *src,
 753                                                  uint8_t *dst)
 754 {
 755         int hash_added;
 756         struct batadv_nc_path *nc_path, nc_path_key;
 757
 758         batadv_nc_hash_key_gen(&nc_path_key, src, dst);
 759
 760         /* Search for existing nc_path */
 761         nc_path = batadv_nc_hash_find(hash, (void *)&nc_path_key);
 762
 763         if (nc_path) {
 764                 /* Set timestamp to delay removal of nc_path */
 765                 nc_path->last_valid = jiffies;
 766                 return nc_path;
 767         }
 768
 769         /* No existing nc_path was found; create a new */
 770         nc_path = kzalloc(sizeof(*nc_path), GFP_ATOMIC);
 771
 772         if (!nc_path)
 773                 return NULL;
 774
 775         /* Initialize nc_path */
 776         INIT_LIST_HEAD(&nc_path->packet_list);
 777         spin_lock_init(&nc_path->packet_list_lock);
 778         atomic_set(&nc_path->refcount, 2);
 779         nc_path->last_valid = jiffies;
 780         memcpy(nc_path->next_hop, dst, ETH_ALEN);
 781         memcpy(nc_path->prev_hop, src, ETH_ALEN);
 782
 783         batadv_dbg(BATADV_DBG_NC, bat_priv, "Adding nc_path %pM -> %pM\n",
 784                    nc_path->prev_hop,
 785                    nc_path->next_hop);
 786
 787         /* Add nc_path to hash table */
 788         hash_added = batadv_hash_add(hash, batadv_nc_hash_compare,
 789                                      batadv_nc_hash_choose, &nc_path_key,
 790                                      &nc_path->hash_entry);
 791
 792         if (hash_added < 0) {
 793                 kfree(nc_path);
 794                 return NULL;
 795         }
 796
 797         return nc_path;
 798 }
 799
 800 /**
 801  * batadv_nc_skb_add_to_path - buffer skb for later encoding / decoding
 802  * @skb: skb to add to path
 803  * @nc_path: path to add skb to
 804  * @neigh_node: next hop to forward packet to
 805  * @packet_id: checksum to identify packet
 806  *
 807  * Returns true if the packet was buffered or false in case of an error.
 808  */
 809 static bool batadv_nc_skb_add_to_path(struct sk_buff *skb,
 810                                       struct batadv_nc_path *nc_path,
 811                                       struct batadv_neigh_node *neigh_node,
 812                                       __be32 packet_id)
 813 {
 814         struct batadv_nc_packet *nc_packet;
 815
 816         nc_packet = kzalloc(sizeof(*nc_packet), GFP_ATOMIC);
 817         if (!nc_packet)
 818                 return false;
 819
 820         /* Initialize nc_packet */
 821         nc_packet->timestamp = jiffies;
 822         nc_packet->packet_id = packet_id;
 823         nc_packet->skb = skb;
 824         nc_packet->neigh_node = neigh_node;
 825         nc_packet->nc_path = nc_path;
 826
 827         /* Add coding packet to list */
 828         spin_lock_bh(&nc_path->packet_list_lock);
 829         list_add_tail(&nc_packet->list, &nc_path->packet_list);
 830         spin_unlock_bh(&nc_path->packet_list_lock);
 831
 832         return true;
 833 }
 834
 835 /**
 836  * batadv_nc_skb_forward - try to code a packet or add it to the coding packet
 837  *  buffer
 838  * @skb: data skb to forward
 839  * @neigh_node: next hop to forward packet to
 840  * @ethhdr: pointer to the ethernet header inside the skb
 841  *
 842  * Returns true if the skb was consumed (encoded packet sent) or false otherwise
 843  */
 844 bool batadv_nc_skb_forward(struct sk_buff *skb,
 845                            struct batadv_neigh_node *neigh_node,
 846                            struct ethhdr *ethhdr)
 847 {
 848         const struct net_device *netdev = neigh_node->if_incoming->soft_iface;
 849         struct batadv_priv *bat_priv = netdev_priv(netdev);
 850         struct batadv_unicast_packet *packet;
 851         struct batadv_nc_path *nc_path;
 852         __be32 packet_id;
 853         u8 *payload;
 854
 855         /* Check if network coding is enabled */
 856         if (!atomic_read(&bat_priv->network_coding))
 857                 goto out;
 858
 859         /* We only handle unicast packets */
 860         payload = skb_network_header(skb);
 861         packet = (struct batadv_unicast_packet *)payload;
 862         if (packet->header.packet_type != BATADV_UNICAST)
 863                 goto out;
 864
 865         /* Find or create a nc_path for this src-dst pair */
 866         nc_path = batadv_nc_get_path(bat_priv,
 867                                      bat_priv->nc.coding_hash,
 868                                      ethhdr->h_source,
 869                                      neigh_node->addr);
 870
 871         if (!nc_path)
 872                 goto out;
 873
 874         /* Add skb to nc_path */
 875         packet_id = batadv_skb_crc32(skb, payload + sizeof(*packet));
 876         if (!batadv_nc_skb_add_to_path(skb, nc_path, neigh_node, packet_id))
 877                 goto free_nc_path;
 878
 879         /* Packet is consumed */
 880         return true;
 881
 882 free_nc_path:
 883         batadv_nc_path_free_ref(nc_path);
 884 out:
 885         /* Packet is not consumed */
 886         return false;
 887 }
 888
 889 /**
 890  * batadv_nc_free - clean up network coding memory
 891  * @bat_priv: the bat priv with all the soft interface information
 892  */
 893 void batadv_nc_free(struct batadv_priv *bat_priv)
 894 {
 895         cancel_delayed_work_sync(&bat_priv->nc.work);
 896         batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash, NULL);
 897         batadv_hash_destroy(bat_priv->nc.coding_hash);
 898 }
 899
 900 /**
 901  * batadv_nc_nodes_seq_print_text - print the nc node information
 902  * @seq: seq file to print on
 903  * @offset: not used
 904  */
 905 int batadv_nc_nodes_seq_print_text(struct seq_file *seq, void *offset)
 906 {
 907         struct net_device *net_dev = (struct net_device *)seq->private;
 908         struct batadv_priv *bat_priv = netdev_priv(net_dev);
 909         struct batadv_hashtable *hash = bat_priv->orig_hash;
 910         struct batadv_hard_iface *primary_if;
 911         struct hlist_head *head;
 912         struct batadv_orig_node *orig_node;
 913         struct batadv_nc_node *nc_node;
 914         int i;
 915
 916         primary_if = batadv_seq_print_text_primary_if_get(seq);
 917         if (!primary_if)
 918                 goto out;
 919
 920         /* Traverse list of originators */
 921         for (i = 0; i < hash->size; i++) {
 922                 head = &hash->table[i];
 923
 924                 /* For each orig_node in this bin */
 925                 rcu_read_lock();
 926                 hlist_for_each_entry_rcu(orig_node, head, hash_entry) {
 927                         seq_printf(seq, "Node:      %pM\n", orig_node->orig);
 928
 929                         seq_printf(seq, " Ingoing:  ");
 930                         /* For each in_nc_node to this orig_node */
 931                         list_for_each_entry_rcu(nc_node,
 932                                                 &orig_node->in_coding_list,
 933                                                 list)
 934                                 seq_printf(seq, "%pM ",
 935                                            nc_node->addr);
 936                         seq_printf(seq, "\n");
 937
 938                         seq_printf(seq, " Outgoing: ");
 939                         /* For out_nc_node to this orig_node */
 940                         list_for_each_entry_rcu(nc_node,
 941                                                 &orig_node->out_coding_list,
 942                                                 list)
 943                                 seq_printf(seq, "%pM ",
 944                                            nc_node->addr);
 945                         seq_printf(seq, "\n\n");
 946                 }
 947                 rcu_read_unlock();
 948         }
 949
 950 out:
 951         if (primary_if)
 952                 batadv_hardif_free_ref(primary_if);
 953         return 0;
 954 }
 955
 956 /**
 957  * batadv_nc_init_debugfs - create nc folder and related files in debugfs
 958  * @bat_priv: the bat priv with all the soft interface information
 959  */
 960 int batadv_nc_init_debugfs(struct batadv_priv *bat_priv)
 961 {
 962         struct dentry *nc_dir, *file;
 963
 964         nc_dir = debugfs_create_dir("nc", bat_priv->debug_dir);
 965         if (!nc_dir)
 966                 goto out;
 967
 968         file = debugfs_create_u8("min_tq", S_IRUGO | S_IWUSR, nc_dir,
 969                                  &bat_priv->nc.min_tq);
 970         if (!file)
 971                 goto out;
 972
 973         file = debugfs_create_u32("max_fwd_delay", S_IRUGO | S_IWUSR, nc_dir,
 974                                   &bat_priv->nc.max_fwd_delay);
 975         if (!file)
 976                 goto out;
 977
 978         return 0;
 979
 980 out:
 981         return -ENOMEM;
 982 }