Signed-off-by: Luis Carlos Cobo <[email protected]>
---
net/mac80211/mesh.h | 283 +++++++++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 283 insertions(+), 0 deletions(-)
create mode 100644 net/mac80211/mesh.h
diff --git a/net/mac80211/mesh.h b/net/mac80211/mesh.h
new file mode 100644
index 0000000..ac89237
--- /dev/null
+++ b/net/mac80211/mesh.h
@@ -0,0 +1,283 @@
+/*
+ * Copyright (c) 2008 open80211s Ltd.
+ * Authors: Luis Carlos Cobo <[email protected]>
+ * Javier Cardona <[email protected]>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+#ifndef IEEE80211S_H
+#define IEEE80211S_H
+
+#include "ieee80211_i.h"
+#include <linux/jhash.h>
+
+extern int mesh_allocated;
+
+/* Data structures */
+
+/**
+ * enum mesh_path_flags - mac80211 mesh path flags
+ *
+ *
+ *
+ * @MESH_PATH_ACTIVE: the mesh path is can be used for forwarding
+ * @MESH_PATH_RESOLVED: the discovery process is running for this mesh path
+ * @MESH_PATH_DSN_VALID: the mesh path contains a valid destination sequence
+ * number
+ * @MESH_PATH_FIXED: the mesh path has been manually set and should not be
+ * modified
+ * @MESH_PATH_RESOLVED: the mesh path can has been resolved
+ * @MESH_PATH_DELETE: the mesh path is scheduled to be deleted
+ *
+ * MESH_PATH_RESOLVED and MESH_PATH_DELETE are used by the mesh path timer to
+ * decide when to stop or cancel the mesh path discovery.
+ */
+enum mesh_path_flags {
+ MESH_PATH_ACTIVE = BIT(0),
+ MESH_PATH_RESOLVING = BIT(1),
+ MESH_PATH_DSN_VALID = BIT(2),
+ MESH_PATH_FIXED = BIT(3),
+ MESH_PATH_RESOLVED = BIT(4),
+ MESH_PATH_DELETE = BIT(5),
+};
+
+/**
+ * struct mesh_path - mac80211 mesh path structure
+ *
+ * @dst: mesh path destination mac address
+ * @dev: mesh path device
+ * @next_hop: mesh neighbor to which frames for this destination will be
+ * forwarded
+ * @timer: mesh path discovery timer
+ * @frame_queue: pending queue for frames sent to this destination while the
+ * path is unresolved
+ * @dsn: destination sequence number of the destination
+ * @metric: current metric to this destination
+ * @hop_count: hops to destination
+ * @exp_time: in jiffies, when the path will expire or when it expired
+ * @discovery_timeout: timeout (lapse in jiffies) used for the last discovery
+ * retry
+ * @discovery_retries: number of discovery retries
+ * @flags: mesh path flags, as specified on &enum mesh_path_flags
+ * @state_lock: mesh pat state lock
+ *
+ *
+ * The combination of dst and dev is unique in the mesh path table. A reference
+ * to the next_hop sta will be kept and in case this sta is removed, the
+ * mesh_path structure must be also removed or substitued in a rcu safe way
+ */
+struct mesh_path {
+ u8 dst[ETH_ALEN];
+ struct net_device *dev;
+ struct sta_info *next_hop;
+ struct timer_list timer;
+ struct sk_buff_head frame_queue;
+ struct rcu_head rcu;
+ u32 dsn;
+ u32 metric;
+ u8 hop_count;
+ unsigned long exp_time;
+ u32 discovery_timeout;
+ u8 discovery_retries;
+ enum mesh_path_flags flags;
+ spinlock_t state_lock;
+};
+
+/**
+ * struct mesh_table
+ *
+ * @hash_buckets: array of hash buckets of the table
+ * @hashwlock: array of locks to protect write operations, one per bucket
+ * @hash_mask: 2^size_order - 1, used to compute hash idx
+ * @hash_rnd: random value used for hash computations
+ * @entries: number of entries in the table
+ * @free_node: function to free nodes of the table
+ * @copy_node: fuction to copy nodes of the table
+ * @size_order: determines size of the table, there will be 2^size_order hash
+ * buckets
+ * @mean_chain_len: maximum average length for the hash buckets' list, if it is
+ * reached, the table will grow
+ */
+struct mesh_table {
+ /* Number of buckets will be 2^N */
+ struct hlist_head *hash_buckets;
+ spinlock_t *hashwlock; /* One per bucket, for add/del */
+ unsigned int hash_mask; /* (2^size_order) - 1 */
+ __u32 hash_rnd; /* Used for hash generation */
+ atomic_t entries; /* Up to MAX_MESH_NEIGHBOURS */
+ void (*free_node) (struct hlist_node *p, bool free_leafs);
+ void (*copy_node) (struct hlist_node *p, struct mesh_table *newtbl);
+ int size_order;
+ int mean_chain_len;
+};
+
+/* Recent multicast cache */
+/* RMC_BUCKETS must be a power of 2, maximum 256 */
+#define RMC_BUCKETS 256
+#define RMC_QUEUE_MAX_LEN 4
+#define RMC_TIMEOUT (3 * HZ)
+
+/**
+ * struct rmc_entry - entry in the Recent Multicast Cache
+ *
+ * @seqnum: mesh sequence number of the frame
+ * @exp_time: expiration time of the entry, in jiffies
+ * @sa: source address of the frame
+ *
+ * The Recent Multicast Cache keeps track of the latest multicast frames that
+ * have been received by a mesh interface and discards received multicast frames
+ * that are found in the cache.
+ */
+struct rmc_entry {
+ struct list_head list;
+ u32 seqnum;
+ unsigned long exp_time;
+ u8 sa[ETH_ALEN];
+};
+
+struct mesh_rmc {
+ struct rmc_entry bucket[RMC_BUCKETS];
+ u8 idx_mask;
+};
+
+
+/* Mesh IEs constants */
+#define MESH_CFG_LEN 19
+
+/*
+ * MESH_CFG_COMP_LEN Includes:
+ * - Active path selection protocol ID.
+ * - Active path selection metric ID.
+ * - Congestion control mode identifier.
+ * - Channel precedence.
+ * Does not include mesh capabilities, which may vary across nodes in the same
+ * mesh
+ */
+#define MESH_CFG_CMP_LEN 17
+
+/* Default values, timeouts in ms */
+#define MESH_TTL 5
+#define MESH_MAX_RETR 3
+#define MESH_RET_T 100
+#define MESH_CONF_T 100
+#define MESH_HOLD_T 100
+
+#define MESH_PATH_TIMEOUT 5000
+/* Minimum interval between two consecutive PREQs originated by the same
+ * interface
+ */
+#define MESH_PREQ_MIN_INT 10
+#define MESH_DIAM_TRAVERSAL_TIME 50
+/* Paths will be refreshed if they are closer than PATH_REFRESH_TIME to their
+ * expiration
+ */
+#define MESH_PATH_REFRESH_TIME 1000
+#define MESH_MIN_DISCOVERY_TIMEOUT (2 * MESH_DIAM_TRAVERSAL_TIME)
+
+#define MESH_MAX_PREQ_RETRIES 4
+#define MESH_PATH_EXPIRE (600 * HZ)
+
+/* Default maximum number of established plinks per interface */
+#define MESH_MAX_ESTAB_PLINKS 32
+
+/* Default maximum number of plinks per interface */
+#define MESH_MAX_PLINKS 256
+
+/* Maximum number of paths per interface */
+#define MESH_MAX_MPATHS 1024
+
+/* Pending ANA approval */
+#define PLINK_CATEGORY 30
+#define MESH_PATH_SEL_CATEGORY 32
+
+/* Mesh Header Flags */
+#define IEEE80211S_FLAGS_AE 0x3
+
+/* Public interfaces */
+/* Various */
+u8 mesh_id_hash(u8 *mesh_id, int mesh_id_len);
+int ieee80211_get_mesh_hdrlen(struct ieee80211s_hdr *meshhdr);
+int ieee80211_new_mesh_header(struct ieee80211s_hdr *meshhdr,
+ struct ieee80211_sub_if_data *sdata);
+int mesh_rmc_check(u8 *addr, struct ieee80211s_hdr *mesh_hdr,
+ struct net_device *dev);
+bool mesh_matches_local(struct ieee802_11_elems *ie, struct net_device *dev);
+void mesh_ids_set_default(struct ieee80211_if_sta *sta);
+void mesh_mgmt_ies_add(struct sk_buff *skb, struct net_device *dev);
+void mesh_rmc_free(struct net_device *dev);
+int mesh_rmc_init(struct net_device *dev);
+void ieee80211s_init(void);
+void ieee80211s_stop(void);
+/* Mesh paths */
+int mesh_nexthop_lookup(u8 *next_hop, struct sk_buff *skb,
+ struct net_device *dev);
+void mesh_path_start_discovery(struct net_device *dev);
+struct mesh_path *mesh_path_lookup(u8 *dst, struct net_device *dev);
+struct mesh_path *mesh_path_lookup_by_idx(int idx, struct net_device *dev);
+void mesh_path_fix_nexthop(struct mesh_path *mpath, struct sta_info *next_hop);
+void mesh_path_expire(struct net_device *dev);
+void mesh_path_flush(struct net_device *dev);
+void mesh_rx_path_sel_frame(struct net_device *dev, struct ieee80211_mgmt *mgmt,
+ size_t len);
+int mesh_path_add(u8 *dst, struct net_device *dev);
+/* Mesh plinks */
+void mesh_neighbour_update(u8 *hw_addr, u64 rates, struct net_device *dev,
+ bool add);
+bool mesh_peer_accepts_plinks(struct ieee802_11_elems *ie,
+ struct net_device *dev);
+void mesh_accept_plinks_update(struct net_device *dev);
+struct sta_info *mesh_plink_add(u8 *hw_addr, u64 rates, struct net_device *dev);
+void mesh_plink_broken(struct sta_info *sta);
+void mesh_plink_deactivate(struct sta_info *sta);
+int mesh_plink_open(struct sta_info *sta);
+int mesh_plink_close(struct sta_info *sta);
+void mesh_plink_block(struct sta_info *sta);
+void mesh_rx_plink_frame(struct net_device *dev, struct ieee80211_mgmt *mgmt,
+ size_t len, struct ieee80211_rx_status *rx_status);
+
+/* Private interfaces */
+/* Mesh tables */
+struct mesh_table *mesh_table_alloc(int size_order);
+void mesh_table_free(struct mesh_table *tbl, bool free_leafs);
+struct mesh_table *mesh_table_grow(struct mesh_table *tbl);
+u32 mesh_table_hash(u8 *addr, struct net_device *dev, struct mesh_table *tbl);
+/* Mesh paths */
+int mesh_path_error_tx(u8 *dest, __le32 dest_dsn, u8 *ra,
+ struct net_device *dev);
+void mesh_path_assign_nexthop(struct mesh_path *mpath, struct sta_info *sta);
+void mesh_path_flush_pending(struct mesh_path *mpath);
+void mesh_path_tx_pending(struct mesh_path *mpath);
+int mesh_pathtbl_init(void);
+void mesh_pathtbl_unregister(void);
+int mesh_path_del(u8 *addr, struct net_device *dev);
+void mesh_path_timer(unsigned long data);
+void mesh_path_flush_by_nexthop(struct sta_info *sta);
+void mesh_path_discard_frame(struct sk_buff *skb, struct net_device *dev);
+
+static inline int mesh_plink_free_count(struct ieee80211_sub_if_data *sdata)
+{
+ return sdata->u.sta.mshcfg.dot11MeshMaxPeerLinks -
+ atomic_read(&sdata->u.sta.mshstats.estab_plinks);
+}
+
+static inline bool mesh_plink_availables(struct ieee80211_sub_if_data *sdata)
+{
+ return (min(mesh_plink_free_count(sdata),
+ MESH_MAX_PLINKS - sdata->local->num_sta)) > 0;
+}
+
+static inline void mesh_path_activate(struct mesh_path *mpath)
+{
+ mpath->flags |= MESH_PATH_ACTIVE | MESH_PATH_RESOLVED;
+}
+
+#define for_each_mesh_entry(x, p, node, i) \
+ for (i = 0; i <= x->hash_mask; i++) \
+ hlist_for_each_entry_rcu(node, p, &x->hash_buckets[i], list)
+
+#define MESH_PREQ(skb) (skb->cb + 30)
+
+#endif /* IEEE80211S_H */
--
1.5.2.5
On Fri, 2008-02-22 at 17:23 +0100, Johannes Berg wrote:
> I don't think I fully understand that. The mesh path points to a sta
> structure, so when that sta is removed, the corresponding mesh path must
> also be deleted. I think I need to look closer at where that is done to
> understand how it could be substituted.
In sta_info_free() we call mesh_plink_deactivate(sta), which calls
mesh_path_flush_by_nexthop(). There is where you could substitute the
mesh path (copy it with next_hop pointing to NULL, substitute pointer,
rcu_synchronize()). However there is not much to gain. Since mesh paths
are freed if inactive sooner than mesh peer links are, this will
actually only happen when mesh peer links are either deleted from user
land or because a specific "peer link close" frame is received.
--
Luis Carlos Cobo Rus GnuPG ID: 44019B60
cozybit Inc.
On Thu, 2008-02-21 at 20:08 -0800, Luis Carlos Cobo wrote:
>
> + *
> + * The combination of dst and dev is unique in the mesh path table. A reference
> + * to the next_hop sta will be kept and in case this sta is removed, the
> + * mesh_path structure must be also removed or substitued in a rcu safe way
> + */
I don't think I fully understand that. The mesh path points to a sta
structure, so when that sta is removed, the corresponding mesh path must
also be deleted. I think I need to look closer at where that is done to
understand how it could be substituted.
johannes
On Mon, 2008-02-25 at 11:16 -0800, Luis Carlos Cobo wrote:
> On Fri, 2008-02-22 at 17:23 +0100, Johannes Berg wrote:
> > I don't think I fully understand that. The mesh path points to a sta
> > structure, so when that sta is removed, the corresponding mesh path must
> > also be deleted. I think I need to look closer at where that is done to
> > understand how it could be substituted.
>
> In sta_info_free() we call mesh_plink_deactivate(sta), which calls
> mesh_path_flush_by_nexthop(). There is where you could substitute the
> mesh path (copy it with next_hop pointing to NULL, substitute pointer,
> rcu_synchronize()). However there is not much to gain. Since mesh paths
> are freed if inactive sooner than mesh peer links are, this will
> actually only happen when mesh peer links are either deleted from user
> land or because a specific "peer link close" frame is received.
Yup. I think I understand it now, but I had to add a "force" parameter
there so that the path is actually completely removed when a STA info is
destroyed.
johannes