Antonio Quartulli | 785ea11 | 2011-11-23 11:35:44 +0100 | [diff] [blame^] | 1 | /* Copyright (C) 2011-2012 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 | |
| 20 | #include <linux/if_ether.h> |
| 21 | #include <linux/if_arp.h> |
| 22 | |
| 23 | #include "main.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 "unicast.h" |
| 30 | |
| 31 | /** |
| 32 | * batadv_hash_dat - compute the hash value for an IP address |
| 33 | * @data: data to hash |
| 34 | * @size: size of the hash table |
| 35 | * |
| 36 | * Returns the selected index in the hash table for the given data |
| 37 | */ |
| 38 | static uint32_t batadv_hash_dat(const void *data, uint32_t size) |
| 39 | { |
| 40 | const unsigned char *key = data; |
| 41 | uint32_t hash = 0; |
| 42 | size_t i; |
| 43 | |
| 44 | for (i = 0; i < 4; i++) { |
| 45 | hash += key[i]; |
| 46 | hash += (hash << 10); |
| 47 | hash ^= (hash >> 6); |
| 48 | } |
| 49 | |
| 50 | hash += (hash << 3); |
| 51 | hash ^= (hash >> 11); |
| 52 | hash += (hash << 15); |
| 53 | |
| 54 | return hash % size; |
| 55 | } |
| 56 | |
| 57 | /** |
| 58 | * batadv_is_orig_node_eligible - check whether a node can be a DHT candidate |
| 59 | * @res: the array with the already selected candidates |
| 60 | * @select: number of already selected candidates |
| 61 | * @tmp_max: address of the currently evaluated node |
| 62 | * @max: current round max address |
| 63 | * @last_max: address of the last selected candidate |
| 64 | * @candidate: orig_node under evaluation |
| 65 | * @max_orig_node: last selected candidate |
| 66 | * |
| 67 | * Returns true if the node has been elected as next candidate or false othrwise |
| 68 | */ |
| 69 | static bool batadv_is_orig_node_eligible(struct batadv_dat_candidate *res, |
| 70 | int select, batadv_dat_addr_t tmp_max, |
| 71 | batadv_dat_addr_t max, |
| 72 | batadv_dat_addr_t last_max, |
| 73 | struct batadv_orig_node *candidate, |
| 74 | struct batadv_orig_node *max_orig_node) |
| 75 | { |
| 76 | bool ret = false; |
| 77 | int j; |
| 78 | |
| 79 | /* Check if this node has already been selected... */ |
| 80 | for (j = 0; j < select; j++) |
| 81 | if (res[j].orig_node == candidate) |
| 82 | break; |
| 83 | /* ..and possibly skip it */ |
| 84 | if (j < select) |
| 85 | goto out; |
| 86 | /* sanity check: has it already been selected? This should not happen */ |
| 87 | if (tmp_max > last_max) |
| 88 | goto out; |
| 89 | /* check if during this iteration an originator with a closer dht |
| 90 | * address has already been found |
| 91 | */ |
| 92 | if (tmp_max < max) |
| 93 | goto out; |
| 94 | /* this is an hash collision with the temporary selected node. Choose |
| 95 | * the one with the lowest address |
| 96 | */ |
| 97 | if ((tmp_max == max) && |
| 98 | (batadv_compare_eth(candidate->orig, max_orig_node->orig) > 0)) |
| 99 | goto out; |
| 100 | |
| 101 | ret = true; |
| 102 | out: |
| 103 | return ret; |
| 104 | } |
| 105 | |
| 106 | /** |
| 107 | * batadv_choose_next_candidate - select the next DHT candidate |
| 108 | * @bat_priv: the bat priv with all the soft interface information |
| 109 | * @cands: candidates array |
| 110 | * @select: number of candidates already present in the array |
| 111 | * @ip_key: key to look up in the DHT |
| 112 | * @last_max: pointer where the address of the selected candidate will be saved |
| 113 | */ |
| 114 | static void batadv_choose_next_candidate(struct batadv_priv *bat_priv, |
| 115 | struct batadv_dat_candidate *cands, |
| 116 | int select, batadv_dat_addr_t ip_key, |
| 117 | batadv_dat_addr_t *last_max) |
| 118 | { |
| 119 | batadv_dat_addr_t max = 0, tmp_max = 0; |
| 120 | struct batadv_orig_node *orig_node, *max_orig_node = NULL; |
| 121 | struct batadv_hashtable *hash = bat_priv->orig_hash; |
| 122 | struct hlist_node *node; |
| 123 | struct hlist_head *head; |
| 124 | int i; |
| 125 | |
| 126 | /* if no node is eligible as candidate, leave the candidate type as |
| 127 | * NOT_FOUND |
| 128 | */ |
| 129 | cands[select].type = BATADV_DAT_CANDIDATE_NOT_FOUND; |
| 130 | |
| 131 | /* iterate over the originator list and find the node with closest |
| 132 | * dat_address which has not been selected yet |
| 133 | */ |
| 134 | for (i = 0; i < hash->size; i++) { |
| 135 | head = &hash->table[i]; |
| 136 | |
| 137 | rcu_read_lock(); |
| 138 | hlist_for_each_entry_rcu(orig_node, node, head, hash_entry) { |
| 139 | /* the dht space is a ring and addresses are unsigned */ |
| 140 | tmp_max = BATADV_DAT_ADDR_MAX - orig_node->dat_addr + |
| 141 | ip_key; |
| 142 | |
| 143 | if (!batadv_is_orig_node_eligible(cands, select, |
| 144 | tmp_max, max, |
| 145 | *last_max, orig_node, |
| 146 | max_orig_node)) |
| 147 | continue; |
| 148 | |
| 149 | if (!atomic_inc_not_zero(&orig_node->refcount)) |
| 150 | continue; |
| 151 | |
| 152 | max = tmp_max; |
| 153 | if (max_orig_node) |
| 154 | batadv_orig_node_free_ref(max_orig_node); |
| 155 | max_orig_node = orig_node; |
| 156 | } |
| 157 | rcu_read_unlock(); |
| 158 | } |
| 159 | if (max_orig_node) { |
| 160 | cands[select].type = BATADV_DAT_CANDIDATE_ORIG; |
| 161 | cands[select].orig_node = max_orig_node; |
| 162 | batadv_dbg(BATADV_DBG_DAT, bat_priv, |
| 163 | "dat_select_candidates() %d: selected %pM addr=%u dist=%u\n", |
| 164 | select, max_orig_node->orig, max_orig_node->dat_addr, |
| 165 | max); |
| 166 | } |
| 167 | *last_max = max; |
| 168 | } |
| 169 | |
| 170 | /** |
| 171 | * batadv_dat_select_candidates - selects the nodes which the DHT message has to |
| 172 | * be sent to |
| 173 | * @bat_priv: the bat priv with all the soft interface information |
| 174 | * @ip_dst: ipv4 to look up in the DHT |
| 175 | * |
| 176 | * An originator O is selected if and only if its DHT_ID value is one of three |
| 177 | * closest values (from the LEFT, with wrap around if needed) then the hash |
| 178 | * value of the key. ip_dst is the key. |
| 179 | * |
| 180 | * Returns the candidate array of size BATADV_DAT_CANDIDATE_NUM |
| 181 | */ |
| 182 | static struct batadv_dat_candidate * |
| 183 | batadv_dat_select_candidates(struct batadv_priv *bat_priv, __be32 ip_dst) |
| 184 | { |
| 185 | int select; |
| 186 | batadv_dat_addr_t last_max = BATADV_DAT_ADDR_MAX, ip_key; |
| 187 | struct batadv_dat_candidate *res; |
| 188 | |
| 189 | if (!bat_priv->orig_hash) |
| 190 | return NULL; |
| 191 | |
| 192 | res = kmalloc(BATADV_DAT_CANDIDATES_NUM * sizeof(*res), GFP_ATOMIC); |
| 193 | if (!res) |
| 194 | return NULL; |
| 195 | |
| 196 | ip_key = (batadv_dat_addr_t)batadv_hash_dat(&ip_dst, |
| 197 | BATADV_DAT_ADDR_MAX); |
| 198 | |
| 199 | batadv_dbg(BATADV_DBG_DAT, bat_priv, |
| 200 | "dat_select_candidates(): IP=%pI4 hash(IP)=%u\n", &ip_dst, |
| 201 | ip_key); |
| 202 | |
| 203 | for (select = 0; select < BATADV_DAT_CANDIDATES_NUM; select++) |
| 204 | batadv_choose_next_candidate(bat_priv, res, select, ip_key, |
| 205 | &last_max); |
| 206 | |
| 207 | return res; |
| 208 | } |
| 209 | |
| 210 | /** |
| 211 | * batadv_dat_send_data - send a payload to the selected candidates |
| 212 | * @bat_priv: the bat priv with all the soft interface information |
| 213 | * @skb: payload to send |
| 214 | * @ip: the DHT key |
| 215 | * @packet_subtype: unicast4addr packet subtype to use |
| 216 | * |
| 217 | * In this function the skb is copied by means of pskb_copy() and is sent as |
| 218 | * unicast packet to each of the selected candidates |
| 219 | * |
| 220 | * Returns true if the packet is sent to at least one candidate, false otherwise |
| 221 | */ |
| 222 | static bool batadv_dat_send_data(struct batadv_priv *bat_priv, |
| 223 | struct sk_buff *skb, __be32 ip, |
| 224 | int packet_subtype) |
| 225 | { |
| 226 | int i; |
| 227 | bool ret = false; |
| 228 | int send_status; |
| 229 | struct batadv_neigh_node *neigh_node = NULL; |
| 230 | struct sk_buff *tmp_skb; |
| 231 | struct batadv_dat_candidate *cand; |
| 232 | |
| 233 | cand = batadv_dat_select_candidates(bat_priv, ip); |
| 234 | if (!cand) |
| 235 | goto out; |
| 236 | |
| 237 | batadv_dbg(BATADV_DBG_DAT, bat_priv, "DHT_SEND for %pI4\n", &ip); |
| 238 | |
| 239 | for (i = 0; i < BATADV_DAT_CANDIDATES_NUM; i++) { |
| 240 | if (cand[i].type == BATADV_DAT_CANDIDATE_NOT_FOUND) |
| 241 | continue; |
| 242 | |
| 243 | neigh_node = batadv_orig_node_get_router(cand[i].orig_node); |
| 244 | if (!neigh_node) |
| 245 | goto free_orig; |
| 246 | |
| 247 | tmp_skb = pskb_copy(skb, GFP_ATOMIC); |
| 248 | if (!batadv_unicast_4addr_prepare_skb(bat_priv, tmp_skb, |
| 249 | cand[i].orig_node, |
| 250 | packet_subtype)) { |
| 251 | kfree_skb(tmp_skb); |
| 252 | goto free_neigh; |
| 253 | } |
| 254 | |
| 255 | send_status = batadv_send_skb_packet(tmp_skb, |
| 256 | neigh_node->if_incoming, |
| 257 | neigh_node->addr); |
| 258 | if (send_status == NET_XMIT_SUCCESS) |
| 259 | /* packet sent to a candidate: return true */ |
| 260 | ret = true; |
| 261 | free_neigh: |
| 262 | batadv_neigh_node_free_ref(neigh_node); |
| 263 | free_orig: |
| 264 | batadv_orig_node_free_ref(cand[i].orig_node); |
| 265 | } |
| 266 | |
| 267 | out: |
| 268 | kfree(cand); |
| 269 | return ret; |
| 270 | } |