2 * Copyright (c) 2008, 2009 open80211s Ltd.
3 * Author: Luis Carlos Cobo <luisca@cozybit.com>
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 2 as
7 * published by the Free Software Foundation.
10 #include <linux/etherdevice.h>
11 #include <linux/list.h>
12 #include <linux/random.h>
13 #include <linux/slab.h>
14 #include <linux/spinlock.h>
15 #include <linux/string.h>
16 #include <net/mac80211.h>
17 #include "ieee80211_i.h"
20 #ifdef CONFIG_MAC80211_VERBOSE_MPATH_DEBUG
21 #define mpath_dbg(fmt, args...) printk(KERN_DEBUG fmt, ##args)
23 #define mpath_dbg(fmt, args...) do { (void)(0); } while (0)
26 /* There will be initially 2^INIT_PATHS_SIZE_ORDER buckets */
27 #define INIT_PATHS_SIZE_ORDER 2
29 /* Keep the mean chain length below this constant */
30 #define MEAN_CHAIN_LEN 2
32 #define MPATH_EXPIRED(mpath) ((mpath->flags & MESH_PATH_ACTIVE) && \
33 time_after(jiffies, mpath->exp_time) && \
34 !(mpath->flags & MESH_PATH_FIXED))
37 struct hlist_node list
;
39 /* This indirection allows two different tables to point to the same
40 * mesh_path structure, useful when resizing
42 struct mesh_path
*mpath
;
45 static struct mesh_table __rcu
*mesh_paths
;
46 static struct mesh_table __rcu
*mpp_paths
; /* Store paths for MPP&MAP */
48 int mesh_paths_generation
;
50 /* This lock will have the grow table function as writer and add / delete nodes
51 * as readers. RCU provides sufficient protection only when reading the table
52 * (i.e. doing lookups). Adding or adding or removing nodes requires we take
53 * the read lock or we risk operating on an old table. The write lock is only
54 * needed when modifying the number of buckets a table.
56 static DEFINE_RWLOCK(pathtbl_resize_lock
);
59 static inline struct mesh_table
*resize_dereference_mesh_paths(void)
61 return rcu_dereference_protected(mesh_paths
,
62 lockdep_is_held(&pathtbl_resize_lock
));
65 static inline struct mesh_table
*resize_dereference_mpp_paths(void)
67 return rcu_dereference_protected(mpp_paths
,
68 lockdep_is_held(&pathtbl_resize_lock
));
71 static int mesh_gate_add(struct mesh_table
*tbl
, struct mesh_path
*mpath
);
74 * CAREFUL -- "tbl" must not be an expression,
75 * in particular not an rcu_dereference(), since
76 * it's used twice. So it is illegal to do
77 * for_each_mesh_entry(rcu_dereference(...), ...)
79 #define for_each_mesh_entry(tbl, p, node, i) \
80 for (i = 0; i <= tbl->hash_mask; i++) \
81 hlist_for_each_entry_rcu(node, p, &tbl->hash_buckets[i], list)
84 static struct mesh_table
*mesh_table_alloc(int size_order
)
87 struct mesh_table
*newtbl
;
89 newtbl
= kmalloc(sizeof(struct mesh_table
), GFP_ATOMIC
);
93 newtbl
->hash_buckets
= kzalloc(sizeof(struct hlist_head
) *
94 (1 << size_order
), GFP_ATOMIC
);
96 if (!newtbl
->hash_buckets
) {
101 newtbl
->hashwlock
= kmalloc(sizeof(spinlock_t
) *
102 (1 << size_order
), GFP_ATOMIC
);
103 if (!newtbl
->hashwlock
) {
104 kfree(newtbl
->hash_buckets
);
109 newtbl
->size_order
= size_order
;
110 newtbl
->hash_mask
= (1 << size_order
) - 1;
111 atomic_set(&newtbl
->entries
, 0);
112 get_random_bytes(&newtbl
->hash_rnd
,
113 sizeof(newtbl
->hash_rnd
));
114 for (i
= 0; i
<= newtbl
->hash_mask
; i
++)
115 spin_lock_init(&newtbl
->hashwlock
[i
]);
116 spin_lock_init(&newtbl
->gates_lock
);
121 static void __mesh_table_free(struct mesh_table
*tbl
)
123 kfree(tbl
->hash_buckets
);
124 kfree(tbl
->hashwlock
);
128 static void mesh_table_free(struct mesh_table
*tbl
, bool free_leafs
)
130 struct hlist_head
*mesh_hash
;
131 struct hlist_node
*p
, *q
;
132 struct mpath_node
*gate
;
135 mesh_hash
= tbl
->hash_buckets
;
136 for (i
= 0; i
<= tbl
->hash_mask
; i
++) {
137 spin_lock_bh(&tbl
->hashwlock
[i
]);
138 hlist_for_each_safe(p
, q
, &mesh_hash
[i
]) {
139 tbl
->free_node(p
, free_leafs
);
140 atomic_dec(&tbl
->entries
);
142 spin_unlock_bh(&tbl
->hashwlock
[i
]);
145 spin_lock_bh(&tbl
->gates_lock
);
146 hlist_for_each_entry_safe(gate
, p
, q
,
147 tbl
->known_gates
, list
) {
148 hlist_del(&gate
->list
);
151 kfree(tbl
->known_gates
);
152 spin_unlock_bh(&tbl
->gates_lock
);
155 __mesh_table_free(tbl
);
158 static int mesh_table_grow(struct mesh_table
*oldtbl
,
159 struct mesh_table
*newtbl
)
161 struct hlist_head
*oldhash
;
162 struct hlist_node
*p
, *q
;
165 if (atomic_read(&oldtbl
->entries
)
166 < oldtbl
->mean_chain_len
* (oldtbl
->hash_mask
+ 1))
169 newtbl
->free_node
= oldtbl
->free_node
;
170 newtbl
->mean_chain_len
= oldtbl
->mean_chain_len
;
171 newtbl
->copy_node
= oldtbl
->copy_node
;
172 newtbl
->known_gates
= oldtbl
->known_gates
;
173 atomic_set(&newtbl
->entries
, atomic_read(&oldtbl
->entries
));
175 oldhash
= oldtbl
->hash_buckets
;
176 for (i
= 0; i
<= oldtbl
->hash_mask
; i
++)
177 hlist_for_each(p
, &oldhash
[i
])
178 if (oldtbl
->copy_node(p
, newtbl
) < 0)
184 for (i
= 0; i
<= newtbl
->hash_mask
; i
++) {
185 hlist_for_each_safe(p
, q
, &newtbl
->hash_buckets
[i
])
186 oldtbl
->free_node(p
, 0);
191 static u32
mesh_table_hash(u8
*addr
, struct ieee80211_sub_if_data
*sdata
,
192 struct mesh_table
*tbl
)
194 /* Use last four bytes of hw addr and interface index as hash index */
195 return jhash_2words(*(u32
*)(addr
+2), sdata
->dev
->ifindex
, tbl
->hash_rnd
)
202 * mesh_path_assign_nexthop - update mesh path next hop
204 * @mpath: mesh path to update
205 * @sta: next hop to assign
207 * Locking: mpath->state_lock must be held when calling this function
209 void mesh_path_assign_nexthop(struct mesh_path
*mpath
, struct sta_info
*sta
)
212 struct ieee80211_hdr
*hdr
;
213 struct sk_buff_head tmpq
;
216 rcu_assign_pointer(mpath
->next_hop
, sta
);
218 __skb_queue_head_init(&tmpq
);
220 spin_lock_irqsave(&mpath
->frame_queue
.lock
, flags
);
222 while ((skb
= __skb_dequeue(&mpath
->frame_queue
)) != NULL
) {
223 hdr
= (struct ieee80211_hdr
*) skb
->data
;
224 memcpy(hdr
->addr1
, sta
->sta
.addr
, ETH_ALEN
);
225 __skb_queue_tail(&tmpq
, skb
);
228 skb_queue_splice(&tmpq
, &mpath
->frame_queue
);
229 spin_unlock_irqrestore(&mpath
->frame_queue
.lock
, flags
);
232 static void prepare_for_gate(struct sk_buff
*skb
, char *dst_addr
,
233 struct mesh_path
*gate_mpath
)
235 struct ieee80211_hdr
*hdr
;
236 struct ieee80211s_hdr
*mshdr
;
237 int mesh_hdrlen
, hdrlen
;
240 hdr
= (struct ieee80211_hdr
*) skb
->data
;
241 hdrlen
= ieee80211_hdrlen(hdr
->frame_control
);
242 mshdr
= (struct ieee80211s_hdr
*) (skb
->data
+ hdrlen
);
244 if (!(mshdr
->flags
& MESH_FLAGS_AE
)) {
245 /* size of the fixed part of the mesh header */
248 /* make room for the two extended addresses */
249 skb_push(skb
, 2 * ETH_ALEN
);
250 memmove(skb
->data
, hdr
, hdrlen
+ mesh_hdrlen
);
252 hdr
= (struct ieee80211_hdr
*) skb
->data
;
254 /* we preserve the previous mesh header and only add
255 * the new addreses */
256 mshdr
= (struct ieee80211s_hdr
*) (skb
->data
+ hdrlen
);
257 mshdr
->flags
= MESH_FLAGS_AE_A5_A6
;
258 memcpy(mshdr
->eaddr1
, hdr
->addr3
, ETH_ALEN
);
259 memcpy(mshdr
->eaddr2
, hdr
->addr4
, ETH_ALEN
);
262 /* update next hop */
263 hdr
= (struct ieee80211_hdr
*) skb
->data
;
265 next_hop
= rcu_dereference(gate_mpath
->next_hop
)->sta
.addr
;
266 memcpy(hdr
->addr1
, next_hop
, ETH_ALEN
);
268 memcpy(hdr
->addr3
, dst_addr
, ETH_ALEN
);
273 * mesh_path_move_to_queue - Move or copy frames from one mpath queue to another
275 * This function is used to transfer or copy frames from an unresolved mpath to
276 * a gate mpath. The function also adds the Address Extension field and
277 * updates the next hop.
279 * If a frame already has an Address Extension field, only the next hop and
280 * destination addresses are updated.
282 * The gate mpath must be an active mpath with a valid mpath->next_hop.
284 * @mpath: An active mpath the frames will be sent to (i.e. the gate)
285 * @from_mpath: The failed mpath
286 * @copy: When true, copy all the frames to the new mpath queue. When false,
289 static void mesh_path_move_to_queue(struct mesh_path
*gate_mpath
,
290 struct mesh_path
*from_mpath
,
293 struct sk_buff
*skb
, *cp_skb
= NULL
;
294 struct sk_buff_head gateq
, failq
;
298 BUG_ON(gate_mpath
== from_mpath
);
299 BUG_ON(!gate_mpath
->next_hop
);
301 __skb_queue_head_init(&gateq
);
302 __skb_queue_head_init(&failq
);
304 spin_lock_irqsave(&from_mpath
->frame_queue
.lock
, flags
);
305 skb_queue_splice_init(&from_mpath
->frame_queue
, &failq
);
306 spin_unlock_irqrestore(&from_mpath
->frame_queue
.lock
, flags
);
308 num_skbs
= skb_queue_len(&failq
);
311 skb
= __skb_dequeue(&failq
);
313 cp_skb
= skb_copy(skb
, GFP_ATOMIC
);
315 __skb_queue_tail(&failq
, cp_skb
);
318 prepare_for_gate(skb
, gate_mpath
->dst
, gate_mpath
);
319 __skb_queue_tail(&gateq
, skb
);
322 spin_lock_irqsave(&gate_mpath
->frame_queue
.lock
, flags
);
323 skb_queue_splice(&gateq
, &gate_mpath
->frame_queue
);
324 mpath_dbg("Mpath queue for gate %pM has %d frames\n",
326 skb_queue_len(&gate_mpath
->frame_queue
));
327 spin_unlock_irqrestore(&gate_mpath
->frame_queue
.lock
, flags
);
332 spin_lock_irqsave(&from_mpath
->frame_queue
.lock
, flags
);
333 skb_queue_splice(&failq
, &from_mpath
->frame_queue
);
334 spin_unlock_irqrestore(&from_mpath
->frame_queue
.lock
, flags
);
338 static struct mesh_path
*path_lookup(struct mesh_table
*tbl
, u8
*dst
,
339 struct ieee80211_sub_if_data
*sdata
)
341 struct mesh_path
*mpath
;
342 struct hlist_node
*n
;
343 struct hlist_head
*bucket
;
344 struct mpath_node
*node
;
346 bucket
= &tbl
->hash_buckets
[mesh_table_hash(dst
, sdata
, tbl
)];
347 hlist_for_each_entry_rcu(node
, n
, bucket
, list
) {
349 if (mpath
->sdata
== sdata
&&
350 memcmp(dst
, mpath
->dst
, ETH_ALEN
) == 0) {
351 if (MPATH_EXPIRED(mpath
)) {
352 spin_lock_bh(&mpath
->state_lock
);
353 mpath
->flags
&= ~MESH_PATH_ACTIVE
;
354 spin_unlock_bh(&mpath
->state_lock
);
363 * mesh_path_lookup - look up a path in the mesh path table
364 * @dst: hardware address (ETH_ALEN length) of destination
365 * @sdata: local subif
367 * Returns: pointer to the mesh path structure, or NULL if not found
369 * Locking: must be called within a read rcu section.
371 struct mesh_path
*mesh_path_lookup(u8
*dst
, struct ieee80211_sub_if_data
*sdata
)
373 return path_lookup(rcu_dereference(mesh_paths
), dst
, sdata
);
376 struct mesh_path
*mpp_path_lookup(u8
*dst
, struct ieee80211_sub_if_data
*sdata
)
378 return path_lookup(rcu_dereference(mpp_paths
), dst
, sdata
);
383 * mesh_path_lookup_by_idx - look up a path in the mesh path table by its index
385 * @sdata: local subif, or NULL for all entries
387 * Returns: pointer to the mesh path structure, or NULL if not found.
389 * Locking: must be called within a read rcu section.
391 struct mesh_path
*mesh_path_lookup_by_idx(int idx
, struct ieee80211_sub_if_data
*sdata
)
393 struct mesh_table
*tbl
= rcu_dereference(mesh_paths
);
394 struct mpath_node
*node
;
395 struct hlist_node
*p
;
399 for_each_mesh_entry(tbl
, p
, node
, i
) {
400 if (sdata
&& node
->mpath
->sdata
!= sdata
)
403 if (MPATH_EXPIRED(node
->mpath
)) {
404 spin_lock_bh(&node
->mpath
->state_lock
);
405 node
->mpath
->flags
&= ~MESH_PATH_ACTIVE
;
406 spin_unlock_bh(&node
->mpath
->state_lock
);
415 static void mesh_gate_node_reclaim(struct rcu_head
*rp
)
417 struct mpath_node
*node
= container_of(rp
, struct mpath_node
, rcu
);
422 * mesh_gate_add - mark mpath as path to a mesh gate and add to known_gates
423 * @mesh_tbl: table which contains known_gates list
424 * @mpath: mpath to known mesh gate
426 * Returns: 0 on success
429 static int mesh_gate_add(struct mesh_table
*tbl
, struct mesh_path
*mpath
)
431 struct mpath_node
*gate
, *new_gate
;
432 struct hlist_node
*n
;
436 tbl
= rcu_dereference(tbl
);
438 hlist_for_each_entry_rcu(gate
, n
, tbl
->known_gates
, list
)
439 if (gate
->mpath
== mpath
) {
444 new_gate
= kzalloc(sizeof(struct mpath_node
), GFP_ATOMIC
);
450 mpath
->is_gate
= true;
451 mpath
->sdata
->u
.mesh
.num_gates
++;
452 new_gate
->mpath
= mpath
;
453 spin_lock_bh(&tbl
->gates_lock
);
454 hlist_add_head_rcu(&new_gate
->list
, tbl
->known_gates
);
455 spin_unlock_bh(&tbl
->gates_lock
);
457 mpath_dbg("Mesh path (%s): Recorded new gate: %pM. %d known gates\n",
458 mpath
->sdata
->name
, mpath
->dst
,
459 mpath
->sdata
->u
.mesh
.num_gates
);
467 * mesh_gate_del - remove a mesh gate from the list of known gates
468 * @tbl: table which holds our list of known gates
471 * Returns: 0 on success
473 * Locking: must be called inside rcu_read_lock() section
475 static int mesh_gate_del(struct mesh_table
*tbl
, struct mesh_path
*mpath
)
477 struct mpath_node
*gate
;
478 struct hlist_node
*p
, *q
;
480 tbl
= rcu_dereference(tbl
);
482 hlist_for_each_entry_safe(gate
, p
, q
, tbl
->known_gates
, list
)
483 if (gate
->mpath
== mpath
) {
484 spin_lock_bh(&tbl
->gates_lock
);
485 hlist_del_rcu(&gate
->list
);
486 call_rcu(&gate
->rcu
, mesh_gate_node_reclaim
);
487 spin_unlock_bh(&tbl
->gates_lock
);
488 mpath
->sdata
->u
.mesh
.num_gates
--;
489 mpath
->is_gate
= false;
490 mpath_dbg("Mesh path (%s): Deleted gate: %pM. "
491 "%d known gates\n", mpath
->sdata
->name
,
492 mpath
->dst
, mpath
->sdata
->u
.mesh
.num_gates
);
501 * mesh_path_add_gate - add the given mpath to a mesh gate to our path table
502 * @mpath: gate path to add to table
504 int mesh_path_add_gate(struct mesh_path
*mpath
)
506 return mesh_gate_add(mesh_paths
, mpath
);
510 * mesh_gate_num - number of gates known to this interface
513 int mesh_gate_num(struct ieee80211_sub_if_data
*sdata
)
515 return sdata
->u
.mesh
.num_gates
;
519 * mesh_path_add - allocate and add a new path to the mesh path table
520 * @addr: destination address of the path (ETH_ALEN length)
521 * @sdata: local subif
523 * Returns: 0 on success
525 * State: the initial state of the new path is set to 0
527 int mesh_path_add(u8
*dst
, struct ieee80211_sub_if_data
*sdata
)
529 struct ieee80211_if_mesh
*ifmsh
= &sdata
->u
.mesh
;
530 struct ieee80211_local
*local
= sdata
->local
;
531 struct mesh_table
*tbl
;
532 struct mesh_path
*mpath
, *new_mpath
;
533 struct mpath_node
*node
, *new_node
;
534 struct hlist_head
*bucket
;
535 struct hlist_node
*n
;
540 if (memcmp(dst
, sdata
->vif
.addr
, ETH_ALEN
) == 0)
541 /* never add ourselves as neighbours */
544 if (is_multicast_ether_addr(dst
))
547 if (atomic_add_unless(&sdata
->u
.mesh
.mpaths
, 1, MESH_MAX_MPATHS
) == 0)
551 new_mpath
= kzalloc(sizeof(struct mesh_path
), GFP_ATOMIC
);
555 new_node
= kmalloc(sizeof(struct mpath_node
), GFP_ATOMIC
);
559 read_lock_bh(&pathtbl_resize_lock
);
560 memcpy(new_mpath
->dst
, dst
, ETH_ALEN
);
561 new_mpath
->sdata
= sdata
;
562 new_mpath
->flags
= 0;
563 skb_queue_head_init(&new_mpath
->frame_queue
);
564 new_node
->mpath
= new_mpath
;
565 new_mpath
->timer
.data
= (unsigned long) new_mpath
;
566 new_mpath
->timer
.function
= mesh_path_timer
;
567 new_mpath
->exp_time
= jiffies
;
568 spin_lock_init(&new_mpath
->state_lock
);
569 init_timer(&new_mpath
->timer
);
571 tbl
= resize_dereference_mesh_paths();
573 hash_idx
= mesh_table_hash(dst
, sdata
, tbl
);
574 bucket
= &tbl
->hash_buckets
[hash_idx
];
576 spin_lock_bh(&tbl
->hashwlock
[hash_idx
]);
579 hlist_for_each_entry(node
, n
, bucket
, list
) {
581 if (mpath
->sdata
== sdata
&& memcmp(dst
, mpath
->dst
, ETH_ALEN
) == 0)
585 hlist_add_head_rcu(&new_node
->list
, bucket
);
586 if (atomic_inc_return(&tbl
->entries
) >=
587 tbl
->mean_chain_len
* (tbl
->hash_mask
+ 1))
590 mesh_paths_generation
++;
592 spin_unlock_bh(&tbl
->hashwlock
[hash_idx
]);
593 read_unlock_bh(&pathtbl_resize_lock
);
595 set_bit(MESH_WORK_GROW_MPATH_TABLE
, &ifmsh
->wrkq_flags
);
596 ieee80211_queue_work(&local
->hw
, &sdata
->work
);
601 spin_unlock_bh(&tbl
->hashwlock
[hash_idx
]);
602 read_unlock_bh(&pathtbl_resize_lock
);
607 atomic_dec(&sdata
->u
.mesh
.mpaths
);
611 static void mesh_table_free_rcu(struct rcu_head
*rcu
)
613 struct mesh_table
*tbl
= container_of(rcu
, struct mesh_table
, rcu_head
);
615 mesh_table_free(tbl
, false);
618 void mesh_mpath_table_grow(void)
620 struct mesh_table
*oldtbl
, *newtbl
;
622 write_lock_bh(&pathtbl_resize_lock
);
623 oldtbl
= resize_dereference_mesh_paths();
624 newtbl
= mesh_table_alloc(oldtbl
->size_order
+ 1);
627 if (mesh_table_grow(oldtbl
, newtbl
) < 0) {
628 __mesh_table_free(newtbl
);
631 rcu_assign_pointer(mesh_paths
, newtbl
);
633 call_rcu(&oldtbl
->rcu_head
, mesh_table_free_rcu
);
636 write_unlock_bh(&pathtbl_resize_lock
);
639 void mesh_mpp_table_grow(void)
641 struct mesh_table
*oldtbl
, *newtbl
;
643 write_lock_bh(&pathtbl_resize_lock
);
644 oldtbl
= resize_dereference_mpp_paths();
645 newtbl
= mesh_table_alloc(oldtbl
->size_order
+ 1);
648 if (mesh_table_grow(oldtbl
, newtbl
) < 0) {
649 __mesh_table_free(newtbl
);
652 rcu_assign_pointer(mpp_paths
, newtbl
);
653 call_rcu(&oldtbl
->rcu_head
, mesh_table_free_rcu
);
656 write_unlock_bh(&pathtbl_resize_lock
);
659 int mpp_path_add(u8
*dst
, u8
*mpp
, struct ieee80211_sub_if_data
*sdata
)
661 struct ieee80211_if_mesh
*ifmsh
= &sdata
->u
.mesh
;
662 struct ieee80211_local
*local
= sdata
->local
;
663 struct mesh_table
*tbl
;
664 struct mesh_path
*mpath
, *new_mpath
;
665 struct mpath_node
*node
, *new_node
;
666 struct hlist_head
*bucket
;
667 struct hlist_node
*n
;
672 if (memcmp(dst
, sdata
->vif
.addr
, ETH_ALEN
) == 0)
673 /* never add ourselves as neighbours */
676 if (is_multicast_ether_addr(dst
))
680 new_mpath
= kzalloc(sizeof(struct mesh_path
), GFP_ATOMIC
);
684 new_node
= kmalloc(sizeof(struct mpath_node
), GFP_ATOMIC
);
688 read_lock_bh(&pathtbl_resize_lock
);
689 memcpy(new_mpath
->dst
, dst
, ETH_ALEN
);
690 memcpy(new_mpath
->mpp
, mpp
, ETH_ALEN
);
691 new_mpath
->sdata
= sdata
;
692 new_mpath
->flags
= 0;
693 skb_queue_head_init(&new_mpath
->frame_queue
);
694 new_node
->mpath
= new_mpath
;
695 init_timer(&new_mpath
->timer
);
696 new_mpath
->exp_time
= jiffies
;
697 spin_lock_init(&new_mpath
->state_lock
);
699 tbl
= resize_dereference_mpp_paths();
701 hash_idx
= mesh_table_hash(dst
, sdata
, tbl
);
702 bucket
= &tbl
->hash_buckets
[hash_idx
];
704 spin_lock_bh(&tbl
->hashwlock
[hash_idx
]);
707 hlist_for_each_entry(node
, n
, bucket
, list
) {
709 if (mpath
->sdata
== sdata
&& memcmp(dst
, mpath
->dst
, ETH_ALEN
) == 0)
713 hlist_add_head_rcu(&new_node
->list
, bucket
);
714 if (atomic_inc_return(&tbl
->entries
) >=
715 tbl
->mean_chain_len
* (tbl
->hash_mask
+ 1))
718 spin_unlock_bh(&tbl
->hashwlock
[hash_idx
]);
719 read_unlock_bh(&pathtbl_resize_lock
);
721 set_bit(MESH_WORK_GROW_MPP_TABLE
, &ifmsh
->wrkq_flags
);
722 ieee80211_queue_work(&local
->hw
, &sdata
->work
);
727 spin_unlock_bh(&tbl
->hashwlock
[hash_idx
]);
728 read_unlock_bh(&pathtbl_resize_lock
);
738 * mesh_plink_broken - deactivates paths and sends perr when a link breaks
740 * @sta: broken peer link
742 * This function must be called from the rate control algorithm if enough
743 * delivery errors suggest that a peer link is no longer usable.
745 void mesh_plink_broken(struct sta_info
*sta
)
747 struct mesh_table
*tbl
;
748 static const u8 bcast
[ETH_ALEN
] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
749 struct mesh_path
*mpath
;
750 struct mpath_node
*node
;
751 struct hlist_node
*p
;
752 struct ieee80211_sub_if_data
*sdata
= sta
->sdata
;
754 __le16 reason
= cpu_to_le16(WLAN_REASON_MESH_PATH_DEST_UNREACHABLE
);
757 tbl
= rcu_dereference(mesh_paths
);
758 for_each_mesh_entry(tbl
, p
, node
, i
) {
760 if (rcu_dereference(mpath
->next_hop
) == sta
&&
761 mpath
->flags
& MESH_PATH_ACTIVE
&&
762 !(mpath
->flags
& MESH_PATH_FIXED
)) {
763 spin_lock_bh(&mpath
->state_lock
);
764 mpath
->flags
&= ~MESH_PATH_ACTIVE
;
766 spin_unlock_bh(&mpath
->state_lock
);
767 mesh_path_error_tx(sdata
->u
.mesh
.mshcfg
.element_ttl
,
768 mpath
->dst
, cpu_to_le32(mpath
->sn
),
769 reason
, bcast
, sdata
);
775 static void mesh_path_node_reclaim(struct rcu_head
*rp
)
777 struct mpath_node
*node
= container_of(rp
, struct mpath_node
, rcu
);
778 struct ieee80211_sub_if_data
*sdata
= node
->mpath
->sdata
;
780 del_timer_sync(&node
->mpath
->timer
);
781 atomic_dec(&sdata
->u
.mesh
.mpaths
);
786 /* needs to be called with the corresponding hashwlock taken */
787 static void __mesh_path_del(struct mesh_table
*tbl
, struct mpath_node
*node
)
789 struct mesh_path
*mpath
;
791 spin_lock(&mpath
->state_lock
);
792 mpath
->flags
|= MESH_PATH_RESOLVING
;
794 mesh_gate_del(tbl
, mpath
);
795 hlist_del_rcu(&node
->list
);
796 call_rcu(&node
->rcu
, mesh_path_node_reclaim
);
797 spin_unlock(&mpath
->state_lock
);
798 atomic_dec(&tbl
->entries
);
802 * mesh_path_flush_by_nexthop - Deletes mesh paths if their next hop matches
804 * @sta - mesh peer to match
806 * RCU notes: this function is called when a mesh plink transitions from
807 * PLINK_ESTAB to any other state, since PLINK_ESTAB state is the only one that
808 * allows path creation. This will happen before the sta can be freed (because
809 * sta_info_destroy() calls this) so any reader in a rcu read block will be
810 * protected against the plink disappearing.
812 void mesh_path_flush_by_nexthop(struct sta_info
*sta
)
814 struct mesh_table
*tbl
;
815 struct mesh_path
*mpath
;
816 struct mpath_node
*node
;
817 struct hlist_node
*p
;
821 read_lock_bh(&pathtbl_resize_lock
);
822 tbl
= resize_dereference_mesh_paths();
823 for_each_mesh_entry(tbl
, p
, node
, i
) {
825 if (rcu_dereference(mpath
->next_hop
) == sta
) {
826 spin_lock_bh(&tbl
->hashwlock
[i
]);
827 __mesh_path_del(tbl
, node
);
828 spin_unlock_bh(&tbl
->hashwlock
[i
]);
831 read_unlock_bh(&pathtbl_resize_lock
);
835 static void table_flush_by_iface(struct mesh_table
*tbl
,
836 struct ieee80211_sub_if_data
*sdata
)
838 struct mesh_path
*mpath
;
839 struct mpath_node
*node
;
840 struct hlist_node
*p
;
843 WARN_ON(!rcu_read_lock_held());
844 for_each_mesh_entry(tbl
, p
, node
, i
) {
846 if (mpath
->sdata
!= sdata
)
848 spin_lock_bh(&tbl
->hashwlock
[i
]);
849 __mesh_path_del(tbl
, node
);
850 spin_unlock_bh(&tbl
->hashwlock
[i
]);
855 * mesh_path_flush_by_iface - Deletes all mesh paths associated with a given iface
857 * This function deletes both mesh paths as well as mesh portal paths.
859 * @sdata - interface data to match
862 void mesh_path_flush_by_iface(struct ieee80211_sub_if_data
*sdata
)
864 struct mesh_table
*tbl
;
867 read_lock_bh(&pathtbl_resize_lock
);
868 tbl
= resize_dereference_mesh_paths();
869 table_flush_by_iface(tbl
, sdata
);
870 tbl
= resize_dereference_mpp_paths();
871 table_flush_by_iface(tbl
, sdata
);
872 read_unlock_bh(&pathtbl_resize_lock
);
877 * mesh_path_del - delete a mesh path from the table
879 * @addr: dst address (ETH_ALEN length)
880 * @sdata: local subif
882 * Returns: 0 if successful
884 int mesh_path_del(u8
*addr
, struct ieee80211_sub_if_data
*sdata
)
886 struct mesh_table
*tbl
;
887 struct mesh_path
*mpath
;
888 struct mpath_node
*node
;
889 struct hlist_head
*bucket
;
890 struct hlist_node
*n
;
894 read_lock_bh(&pathtbl_resize_lock
);
895 tbl
= resize_dereference_mesh_paths();
896 hash_idx
= mesh_table_hash(addr
, sdata
, tbl
);
897 bucket
= &tbl
->hash_buckets
[hash_idx
];
899 spin_lock_bh(&tbl
->hashwlock
[hash_idx
]);
900 hlist_for_each_entry(node
, n
, bucket
, list
) {
902 if (mpath
->sdata
== sdata
&&
903 memcmp(addr
, mpath
->dst
, ETH_ALEN
) == 0) {
904 __mesh_path_del(tbl
, node
);
911 mesh_paths_generation
++;
912 spin_unlock_bh(&tbl
->hashwlock
[hash_idx
]);
913 read_unlock_bh(&pathtbl_resize_lock
);
918 * mesh_path_tx_pending - sends pending frames in a mesh path queue
920 * @mpath: mesh path to activate
922 * Locking: the state_lock of the mpath structure must NOT be held when calling
925 void mesh_path_tx_pending(struct mesh_path
*mpath
)
927 if (mpath
->flags
& MESH_PATH_ACTIVE
)
928 ieee80211_add_pending_skbs(mpath
->sdata
->local
,
929 &mpath
->frame_queue
);
933 * mesh_path_send_to_gates - sends pending frames to all known mesh gates
935 * @mpath: mesh path whose queue will be emptied
937 * If there is only one gate, the frames are transferred from the failed mpath
938 * queue to that gate's queue. If there are more than one gates, the frames
939 * are copied from each gate to the next. After frames are copied, the
940 * mpath queues are emptied onto the transmission queue.
942 int mesh_path_send_to_gates(struct mesh_path
*mpath
)
944 struct ieee80211_sub_if_data
*sdata
= mpath
->sdata
;
945 struct hlist_node
*n
;
946 struct mesh_table
*tbl
;
947 struct mesh_path
*from_mpath
= mpath
;
948 struct mpath_node
*gate
= NULL
;
950 struct hlist_head
*known_gates
;
953 tbl
= rcu_dereference(mesh_paths
);
954 known_gates
= tbl
->known_gates
;
958 return -EHOSTUNREACH
;
960 hlist_for_each_entry_rcu(gate
, n
, known_gates
, list
) {
961 if (gate
->mpath
->sdata
!= sdata
)
964 if (gate
->mpath
->flags
& MESH_PATH_ACTIVE
) {
965 mpath_dbg("Forwarding to %pM\n", gate
->mpath
->dst
);
966 mesh_path_move_to_queue(gate
->mpath
, from_mpath
, copy
);
967 from_mpath
= gate
->mpath
;
970 mpath_dbg("Not forwarding %p\n", gate
->mpath
);
971 mpath_dbg("flags %x\n", gate
->mpath
->flags
);
975 hlist_for_each_entry_rcu(gate
, n
, known_gates
, list
)
976 if (gate
->mpath
->sdata
== sdata
) {
977 mpath_dbg("Sending to %pM\n", gate
->mpath
->dst
);
978 mesh_path_tx_pending(gate
->mpath
);
981 return (from_mpath
== mpath
) ? -EHOSTUNREACH
: 0;
985 * mesh_path_discard_frame - discard a frame whose path could not be resolved
987 * @skb: frame to discard
988 * @sdata: network subif the frame was to be sent through
990 * If the frame was being forwarded from another MP, a PERR frame will be sent
991 * to the precursor. The precursor's address (i.e. the previous hop) was saved
992 * in addr1 of the frame-to-be-forwarded, and would only be overwritten once
993 * the destination is successfully resolved.
995 * Locking: the function must me called within a rcu_read_lock region
997 void mesh_path_discard_frame(struct sk_buff
*skb
,
998 struct ieee80211_sub_if_data
*sdata
)
1000 struct ieee80211_hdr
*hdr
= (struct ieee80211_hdr
*) skb
->data
;
1001 struct mesh_path
*mpath
;
1003 __le16 reason
= cpu_to_le16(WLAN_REASON_MESH_PATH_NOFORWARD
);
1005 if (memcmp(hdr
->addr4
, sdata
->vif
.addr
, ETH_ALEN
) != 0) {
1011 mpath
= mesh_path_lookup(da
, sdata
);
1013 spin_lock_bh(&mpath
->state_lock
);
1015 spin_unlock_bh(&mpath
->state_lock
);
1018 mesh_path_error_tx(sdata
->u
.mesh
.mshcfg
.element_ttl
, skb
->data
,
1019 cpu_to_le32(sn
), reason
, ra
, sdata
);
1023 sdata
->u
.mesh
.mshstats
.dropped_frames_no_route
++;
1027 * mesh_path_flush_pending - free the pending queue of a mesh path
1029 * @mpath: mesh path whose queue has to be freed
1031 * Locking: the function must me called within a rcu_read_lock region
1033 void mesh_path_flush_pending(struct mesh_path
*mpath
)
1035 struct sk_buff
*skb
;
1037 while ((skb
= skb_dequeue(&mpath
->frame_queue
)) != NULL
)
1038 mesh_path_discard_frame(skb
, mpath
->sdata
);
1042 * mesh_path_fix_nexthop - force a specific next hop for a mesh path
1044 * @mpath: the mesh path to modify
1045 * @next_hop: the next hop to force
1047 * Locking: this function must be called holding mpath->state_lock
1049 void mesh_path_fix_nexthop(struct mesh_path
*mpath
, struct sta_info
*next_hop
)
1051 spin_lock_bh(&mpath
->state_lock
);
1052 mesh_path_assign_nexthop(mpath
, next_hop
);
1055 mpath
->hop_count
= 0;
1056 mpath
->exp_time
= 0;
1057 mpath
->flags
|= MESH_PATH_FIXED
;
1058 mesh_path_activate(mpath
);
1059 spin_unlock_bh(&mpath
->state_lock
);
1060 mesh_path_tx_pending(mpath
);
1063 static void mesh_path_node_free(struct hlist_node
*p
, bool free_leafs
)
1065 struct mesh_path
*mpath
;
1066 struct mpath_node
*node
= hlist_entry(p
, struct mpath_node
, list
);
1067 mpath
= node
->mpath
;
1070 del_timer_sync(&mpath
->timer
);
1076 static int mesh_path_node_copy(struct hlist_node
*p
, struct mesh_table
*newtbl
)
1078 struct mesh_path
*mpath
;
1079 struct mpath_node
*node
, *new_node
;
1082 new_node
= kmalloc(sizeof(struct mpath_node
), GFP_ATOMIC
);
1083 if (new_node
== NULL
)
1086 node
= hlist_entry(p
, struct mpath_node
, list
);
1087 mpath
= node
->mpath
;
1088 new_node
->mpath
= mpath
;
1089 hash_idx
= mesh_table_hash(mpath
->dst
, mpath
->sdata
, newtbl
);
1090 hlist_add_head(&new_node
->list
,
1091 &newtbl
->hash_buckets
[hash_idx
]);
1095 int mesh_pathtbl_init(void)
1097 struct mesh_table
*tbl_path
, *tbl_mpp
;
1099 tbl_path
= mesh_table_alloc(INIT_PATHS_SIZE_ORDER
);
1102 tbl_path
->free_node
= &mesh_path_node_free
;
1103 tbl_path
->copy_node
= &mesh_path_node_copy
;
1104 tbl_path
->mean_chain_len
= MEAN_CHAIN_LEN
;
1105 tbl_path
->known_gates
= kzalloc(sizeof(struct hlist_head
), GFP_ATOMIC
);
1106 INIT_HLIST_HEAD(tbl_path
->known_gates
);
1109 tbl_mpp
= mesh_table_alloc(INIT_PATHS_SIZE_ORDER
);
1111 mesh_table_free(tbl_path
, true);
1114 tbl_mpp
->free_node
= &mesh_path_node_free
;
1115 tbl_mpp
->copy_node
= &mesh_path_node_copy
;
1116 tbl_mpp
->mean_chain_len
= MEAN_CHAIN_LEN
;
1117 tbl_mpp
->known_gates
= kzalloc(sizeof(struct hlist_head
), GFP_ATOMIC
);
1118 INIT_HLIST_HEAD(tbl_mpp
->known_gates
);
1120 /* Need no locking since this is during init */
1121 RCU_INIT_POINTER(mesh_paths
, tbl_path
);
1122 RCU_INIT_POINTER(mpp_paths
, tbl_mpp
);
1127 void mesh_path_expire(struct ieee80211_sub_if_data
*sdata
)
1129 struct mesh_table
*tbl
;
1130 struct mesh_path
*mpath
;
1131 struct mpath_node
*node
;
1132 struct hlist_node
*p
;
1136 tbl
= rcu_dereference(mesh_paths
);
1137 for_each_mesh_entry(tbl
, p
, node
, i
) {
1138 if (node
->mpath
->sdata
!= sdata
)
1140 mpath
= node
->mpath
;
1141 if ((!(mpath
->flags
& MESH_PATH_RESOLVING
)) &&
1142 (!(mpath
->flags
& MESH_PATH_FIXED
)) &&
1143 time_after(jiffies
, mpath
->exp_time
+ MESH_PATH_EXPIRE
))
1144 mesh_path_del(mpath
->dst
, mpath
->sdata
);
1149 void mesh_pathtbl_unregister(void)
1151 /* no need for locking during exit path */
1152 mesh_table_free(rcu_dereference_raw(mesh_paths
), true);
1153 mesh_table_free(rcu_dereference_raw(mpp_paths
), true);