diff mbox

batman-adv: convert tt request list into hlist

Message ID 1434697758-8399-1-git-send-email-mareklindner@neomailbox.ch (mailing list archive)
State Superseded, archived
Headers

Commit Message

Marek Lindner June 19, 2015, 7:09 a.m. UTC 
  The tt request list does not require a double linked list, hence a
conversion to hlist saves memory without losing functionality.

Also, the list_del() call was changed to hlist_del_init() to allow
an adding an extra check prior to deletion in batadv_tt_req_node_new().

Signed-off-by: Marek Lindner <mareklindner@neomailbox.ch>
---
 net/batman-adv/main.c              |  2 +-
 net/batman-adv/translation-table.c | 29 +++++++++++++++++------------
 net/batman-adv/types.h             |  4 ++--
 3 files changed, 20 insertions(+), 15 deletions(-)

Comments

Antonio Quartulli June 19, 2015, 8 a.m. UTC | #1 
On 19/06/15 09:09, Marek Lindner wrote:
> The tt request list does not require a double linked list, hence a
> conversion to hlist saves memory without losing functionality.
> 
> Also, the list_del() call was changed to hlist_del_init() to allow
> an adding an extra check prior to deletion in batadv_tt_req_node_new().
> 
> Signed-off-by: Marek Lindner <mareklindner@neomailbox.ch>

Nice one :)

Acked-by: Antonio Quartulli <antonio@meshcoding.com>
Sven Eckelmann June 19, 2015, 9:23 a.m. UTC | #2 
On Friday 19 June 2015 15:09:18 Marek Lindner wrote:
> The tt request list does not require a double linked list, hence a
> conversion to hlist saves memory without losing functionality.
> 
> Also, the list_del() call was changed to hlist_del_init() to allow
> an adding an extra check prior to deletion in batadv_tt_req_node_new().
> 
> Signed-off-by: Marek Lindner <mareklindner@neomailbox.ch>

hlist_node is still double linked [1] (pprev is an "indirect" pointer to the
next pointer of the previous hlist_node in the list). The hlist_head is the
only one which has only one pointer. This is the reason why you can't add
things to the end of an hlist. But you can still add an hlist_node before
another hlist_node. This would be something which you could not do easily on a
"not double linked list"

Kind regards,
	Sven

[1] https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/include/linux/list.h?id=a54acb3a6f853e8394c4cb7b6a4d93c88f13eefd#n588
Sven Eckelmann June 19, 2015, 9:32 a.m. UTC | #3 
On Friday 19 June 2015 15:09:18 Marek Lindner wrote:
>  		spin_lock_bh(&bat_priv->tt.req_list_lock);
> -		list_del(&tt_req_node->list);
> +		/* only remove tt_req_node if it still is in the list */
> +		if (!hlist_unhashed(&tt_req_node->list))
> +			hlist_del_init(&tt_req_node->list);
>  		spin_unlock_bh(&bat_priv->tt.req_list_lock);
>  		kfree(tt_req_node);
>  	}

hlist_del_init doesn't require the hlist_unhashed check because this is
already done inside of this function [1].

Kind regards,
	Sven

[1] https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/include/linux/list.h?id=a54acb3a6f853e8394c4cb7b6a4d93c88f13eefd#n588
Marek Lindner June 19, 2015, 9:43 a.m. UTC | #4 
On Friday, June 19, 2015 11:32:00 Sven Eckelmann wrote:
> On Friday 19 June 2015 15:09:18 Marek Lindner wrote:
> >  		spin_lock_bh(&bat_priv->tt.req_list_lock);
> > 
> > -		list_del(&tt_req_node->list);
> > +		/* only remove tt_req_node if it still is in the list */
> > +		if (!hlist_unhashed(&tt_req_node->list))
> > +			hlist_del_init(&tt_req_node->list);
> > 
> >  		spin_unlock_bh(&bat_priv->tt.req_list_lock);
> >  		kfree(tt_req_node);
> >  	
> >  	}
> 
> hlist_del_init doesn't require the hlist_unhashed check because this is
> already done inside of this function [1].

Thanks! I did not know that. Will send a v2 shortly.

Cheers,
Marek
Sven Eckelmann June 19, 2015, 9:43 a.m. UTC | #5 
On Friday 19 June 2015 11:32:00 Sven Eckelmann wrote:
> [1] https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/include/linux/list.h?id=a54acb3a6f853e8394c4cb7b6a4d93c88f13eefd#n588

Correction:

https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/include/linux/list.h?id=a54acb3a6f853e8394c4cb7b6a4d93c88f13eefd#n630
diff mbox

Patch

diff --git a/net/batman-adv/main.c b/net/batman-adv/main.c
index 40750cb..d277ba7 100644
--- a/net/batman-adv/main.c
+++ b/net/batman-adv/main.c
@@ -148,7 +148,7 @@  int batadv_mesh_init(struct net_device *soft_iface)
 	INIT_HLIST_HEAD(&bat_priv->mcast.want_all_ipv6_list);
 #endif
 	INIT_LIST_HEAD(&bat_priv->tt.changes_list);
-	INIT_LIST_HEAD(&bat_priv->tt.req_list);
+	INIT_HLIST_HEAD(&bat_priv->tt.req_list);
 	INIT_LIST_HEAD(&bat_priv->tt.roam_list);
 #ifdef CONFIG_BATMAN_ADV_MCAST
 	INIT_HLIST_HEAD(&bat_priv->mcast.mla_list);
diff --git a/net/batman-adv/translation-table.c b/net/batman-adv/translation-table.c
index 2de4784..9f43e44 100644
--- a/net/batman-adv/translation-table.c
+++ b/net/batman-adv/translation-table.c
@@ -2203,12 +2203,13 @@  static u32 batadv_tt_local_crc(struct batadv_priv *bat_priv,
 
 static void batadv_tt_req_list_free(struct batadv_priv *bat_priv)
 {
-	struct batadv_tt_req_node *node, *safe;
+	struct batadv_tt_req_node *node;
+	struct hlist_node *safe;
 
 	spin_lock_bh(&bat_priv->tt.req_list_lock);
 
-	list_for_each_entry_safe(node, safe, &bat_priv->tt.req_list, list) {
-		list_del(&node->list);
+	hlist_for_each_entry_safe(node, safe, &bat_priv->tt.req_list, list) {
+		hlist_del_init(&node->list);
 		kfree(node);
 	}
 
@@ -2238,13 +2239,14 @@  static void batadv_tt_save_orig_buffer(struct batadv_priv *bat_priv,
 
 static void batadv_tt_req_purge(struct batadv_priv *bat_priv)
 {
-	struct batadv_tt_req_node *node, *safe;
+	struct batadv_tt_req_node *node;
+	struct hlist_node *safe;
 
 	spin_lock_bh(&bat_priv->tt.req_list_lock);
-	list_for_each_entry_safe(node, safe, &bat_priv->tt.req_list, list) {
+	hlist_for_each_entry_safe(node, safe, &bat_priv->tt.req_list, list) {
 		if (batadv_has_timed_out(node->issued_at,
 					 BATADV_TT_REQUEST_TIMEOUT)) {
-			list_del(&node->list);
+			hlist_del_init(&node->list);
 			kfree(node);
 		}
 	}
@@ -2266,7 +2268,7 @@  batadv_tt_req_node_new(struct batadv_priv *bat_priv,
 	struct batadv_tt_req_node *tt_req_node_tmp, *tt_req_node = NULL;
 
 	spin_lock_bh(&bat_priv->tt.req_list_lock);
-	list_for_each_entry(tt_req_node_tmp, &bat_priv->tt.req_list, list) {
+	hlist_for_each_entry(tt_req_node_tmp, &bat_priv->tt.req_list, list) {
 		if (batadv_compare_eth(tt_req_node_tmp, orig_node) &&
 		    !batadv_has_timed_out(tt_req_node_tmp->issued_at,
 					  BATADV_TT_REQUEST_TIMEOUT))
@@ -2280,7 +2282,7 @@  batadv_tt_req_node_new(struct batadv_priv *bat_priv,
 	ether_addr_copy(tt_req_node->addr, orig_node->orig);
 	tt_req_node->issued_at = jiffies;
 
-	list_add(&tt_req_node->list, &bat_priv->tt.req_list);
+	hlist_add_head(&tt_req_node->list, &bat_priv->tt.req_list);
 unlock:
 	spin_unlock_bh(&bat_priv->tt.req_list_lock);
 	return tt_req_node;
@@ -2531,7 +2533,9 @@  out:
 		batadv_hardif_free_ref(primary_if);
 	if (ret && tt_req_node) {
 		spin_lock_bh(&bat_priv->tt.req_list_lock);
-		list_del(&tt_req_node->list);
+		/* only remove tt_req_node if it still is in the list */
+		if (!hlist_unhashed(&tt_req_node->list))
+			hlist_del_init(&tt_req_node->list);
 		spin_unlock_bh(&bat_priv->tt.req_list_lock);
 		kfree(tt_req_node);
 	}
@@ -2927,7 +2931,8 @@  static void batadv_handle_tt_response(struct batadv_priv *bat_priv,
 				      struct batadv_tvlv_tt_data *tt_data,
 				      u8 *resp_src, u16 num_entries)
 {
-	struct batadv_tt_req_node *node, *safe;
+	struct batadv_tt_req_node *node;
+	struct hlist_node *safe;
 	struct batadv_orig_node *orig_node = NULL;
 	struct batadv_tvlv_tt_change *tt_change;
 	u8 *tvlv_ptr = (u8 *)tt_data;
@@ -2965,10 +2970,10 @@  static void batadv_handle_tt_response(struct batadv_priv *bat_priv,
 
 	/* Delete the tt_req_node from pending tt_requests list */
 	spin_lock_bh(&bat_priv->tt.req_list_lock);
-	list_for_each_entry_safe(node, safe, &bat_priv->tt.req_list, list) {
+	hlist_for_each_entry_safe(node, safe, &bat_priv->tt.req_list, list) {
 		if (!batadv_compare_eth(node->addr, resp_src))
 			continue;
-		list_del(&node->list);
+		hlist_del_init(&node->list);
 		kfree(node);
 	}
 
diff --git a/net/batman-adv/types.h b/net/batman-adv/types.h
index da4c738..76fe31f 100644
--- a/net/batman-adv/types.h
+++ b/net/batman-adv/types.h
@@ -537,7 +537,7 @@  struct batadv_priv_tt {
 	struct list_head changes_list;
 	struct batadv_hashtable *local_hash;
 	struct batadv_hashtable *global_hash;
-	struct list_head req_list;
+	struct hlist_head req_list;
 	struct list_head roam_list;
 	spinlock_t changes_list_lock; /* protects changes */
 	spinlock_t req_list_lock; /* protects req_list */
@@ -1006,7 +1006,7 @@  struct batadv_tt_change_node {
 struct batadv_tt_req_node {
 	u8 addr[ETH_ALEN];
 	unsigned long issued_at;
-	struct list_head list;
+	struct hlist_node list;
 };
 
 /**