Commit | Line | Data |
---|---|---|
785ea114 AQ |
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 | } |