tipc: Convert node object array to a hash table

Replaces the dynamically allocated array of pointers to the cluster's
node objects with a static hash table. Hash collisions are resolved
using chaining, with a typical hash chain having only a single node,
to avoid degrading performance during processing of incoming packets.
The conversion to a hash table reduces the memory requirements for
TIPC's node table to approximately the same size it had prior to
the previous commit.

In addition to the hash table itself, TIPC now also maintains a
linked list for the node objects, sorted by ascending network address.
This list allows TIPC to continue sending responses to user space
applications that request node and link information in sorted order.
The list also improves performance when name table update messages are
sent by making it easier to identify the nodes that must be notified.

Signed-off-by: Allan Stephens <allan.stephens@windriver.com>
Signed-off-by: Paul Gortmaker <paul.gortmaker@windriver.com>

1 files changed, 20 insertions, 10 deletions

diff --git a/net/tipc/node.h b/net/tipc/node.h
index c510a2afcc67..02e4927216fa 100644
--- a/net/tipc/node.h
+++ b/net/tipc/node.h
@@ -2,7 +2,7 @@
  * net/tipc/node.h: Include file for TIPC node management routines
  *
  * Copyright (c) 2000-2006, Ericsson AB
- * Copyright (c) 2005, Wind River Systems
+ * Copyright (c) 2005, 2010-2011, Wind River Systems
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -46,7 +46,8 @@
  * struct tipc_node - TIPC node structure
  * @addr: network address of node
  * @lock: spinlock governing access to structure
- * @next: pointer to next node in sorted list of cluster's nodes
+ * @hash: links to adjacent nodes in unsorted hash chain
+ * @list: links to adjacent nodes in sorted list of cluster's nodes
  * @nsub: list of "node down" subscriptions monitoring node
  * @active_links: pointers to active links to node
  * @links: pointers to all links to node
@@ -69,7 +70,8 @@
 struct tipc_node {
         u32 addr;
         spinlock_t lock;
-        struct tipc_node *next;
+        struct hlist_node hash;
+        struct list_head list;
         struct list_head nsub;
         struct link *active_links[2];
         struct link *links[MAX_BEARERS];
@@ -90,8 +92,23 @@ struct tipc_node {
         } bclink;
 };
 
+#define NODE_HTABLE_SIZE 512
+extern struct list_head tipc_node_list;
+
+/*
+ * A trivial power-of-two bitmask technique is used for speed, since this
+ * operation is done for every incoming TIPC packet. The number of hash table
+ * entries has been chosen so that no hash chain exceeds 8 nodes and will
+ * usually be much smaller (typically only a single node).
+ */
+static inline unsigned int tipc_hashfn(u32 addr)
+{
+        return addr & (NODE_HTABLE_SIZE - 1);
+}
+
 extern u32 tipc_own_tag;
 
+struct tipc_node *tipc_node_find(u32 addr);
 struct tipc_node *tipc_node_create(u32 addr);
 void tipc_node_delete(struct tipc_node *n_ptr);
 struct tipc_node *tipc_node_attach_link(struct link *l_ptr);
@@ -104,13 +121,6 @@ int tipc_node_is_up(struct tipc_node *n_ptr);
 struct sk_buff *tipc_node_get_links(const void *req_tlv_area, int req_tlv_space);
 struct sk_buff *tipc_node_get_nodes(const void *req_tlv_area, int req_tlv_space);
 
-static inline struct tipc_node *tipc_node_find(u32 addr)
-{
-        if (likely(in_own_cluster(addr)))
-                return tipc_nodes[tipc_node(addr)];
-        return NULL;
-}
-
 static inline void tipc_node_lock(struct tipc_node *n_ptr)
 {
         spin_lock_bh(&n_ptr->lock);