aboutsummaryrefslogtreecommitdiffstats
path: root/net
diff options
context:
space:
mode:
authorAllan Stephens <allan.stephens@windriver.com>2011-02-25 18:42:52 -0500
committerPaul Gortmaker <paul.gortmaker@windriver.com>2011-03-13 16:35:17 -0400
commit672d99e19a12b703c9e2d71ead8fb8b8a85a3886 (patch)
treecca078684f8adee7450cadcb565176f0a8b111ff /net
parentf831c963b5c20bec230edce89e25f369996be5db (diff)
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>
Diffstat (limited to 'net')
-rw-r--r--net/tipc/name_distr.c6
-rw-r--r--net/tipc/net.c15
-rw-r--r--net/tipc/net.h4
-rw-r--r--net/tipc/node.c70
-rw-r--r--net/tipc/node.h30
5 files changed, 70 insertions, 55 deletions
diff --git a/net/tipc/name_distr.c b/net/tipc/name_distr.c
index f2086f684b34..1b70d5d051d0 100644
--- a/net/tipc/name_distr.c
+++ b/net/tipc/name_distr.c
@@ -109,11 +109,9 @@ static void named_cluster_distribute(struct sk_buff *buf)
109{ 109{
110 struct sk_buff *buf_copy; 110 struct sk_buff *buf_copy;
111 struct tipc_node *n_ptr; 111 struct tipc_node *n_ptr;
112 u32 n_num;
113 112
114 for (n_num = 1; n_num <= tipc_highest_node; n_num++) { 113 list_for_each_entry(n_ptr, &tipc_node_list, list) {
115 n_ptr = tipc_nodes[n_num]; 114 if (tipc_node_has_active_links(n_ptr)) {
116 if (n_ptr && tipc_node_has_active_links(n_ptr)) {
117 buf_copy = skb_copy(buf, GFP_ATOMIC); 115 buf_copy = skb_copy(buf, GFP_ATOMIC);
118 if (!buf_copy) 116 if (!buf_copy)
119 break; 117 break;
diff --git a/net/tipc/net.c b/net/tipc/net.c
index b5b337f5516d..cce8d086f173 100644
--- a/net/tipc/net.c
+++ b/net/tipc/net.c
@@ -39,6 +39,7 @@
39#include "name_distr.h" 39#include "name_distr.h"
40#include "subscr.h" 40#include "subscr.h"
41#include "port.h" 41#include "port.h"
42#include "node.h"
42#include "config.h" 43#include "config.h"
43 44
44/* 45/*
@@ -108,27 +109,21 @@
108*/ 109*/
109 110
110DEFINE_RWLOCK(tipc_net_lock); 111DEFINE_RWLOCK(tipc_net_lock);
111struct tipc_node **tipc_nodes;
112u32 tipc_highest_node;
113atomic_t tipc_num_links; 112atomic_t tipc_num_links;
114 113
115static int net_start(void) 114static int net_start(void)
116{ 115{
117 tipc_nodes = kcalloc(4096, sizeof(*tipc_nodes), GFP_ATOMIC);
118 tipc_highest_node = 0;
119 atomic_set(&tipc_num_links, 0); 116 atomic_set(&tipc_num_links, 0);
120 117
121 return tipc_nodes ? 0 : -ENOMEM; 118 return 0;
122} 119}
123 120
124static void net_stop(void) 121static void net_stop(void)
125{ 122{
126 u32 n_num; 123 struct tipc_node *node, *t_node;
127 124
128 for (n_num = 1; n_num <= tipc_highest_node; n_num++) 125 list_for_each_entry_safe(node, t_node, &tipc_node_list, list)
129 tipc_node_delete(tipc_nodes[n_num]); 126 tipc_node_delete(node);
130 kfree(tipc_nodes);
131 tipc_nodes = NULL;
132} 127}
133 128
134static void net_route_named_msg(struct sk_buff *buf) 129static void net_route_named_msg(struct sk_buff *buf)
diff --git a/net/tipc/net.h b/net/tipc/net.h
index b52b9748b5e2..0ba6093fb6ce 100644
--- a/net/tipc/net.h
+++ b/net/tipc/net.h
@@ -37,10 +37,6 @@
37#ifndef _TIPC_NET_H 37#ifndef _TIPC_NET_H
38#define _TIPC_NET_H 38#define _TIPC_NET_H
39 39
40struct tipc_node;
41
42extern struct tipc_node **tipc_nodes;
43extern u32 tipc_highest_node;
44extern atomic_t tipc_num_links; 40extern atomic_t tipc_num_links;
45 41
46extern rwlock_t tipc_net_lock; 42extern rwlock_t tipc_net_lock;
diff --git a/net/tipc/node.c b/net/tipc/node.c
index 64976f2e3c66..22aeb2b7ad00 100644
--- a/net/tipc/node.c
+++ b/net/tipc/node.c
@@ -44,9 +44,31 @@ static void node_established_contact(struct tipc_node *n_ptr);
44 44
45static DEFINE_SPINLOCK(node_create_lock); 45static DEFINE_SPINLOCK(node_create_lock);
46 46
47static struct hlist_head node_htable[NODE_HTABLE_SIZE];
48LIST_HEAD(tipc_node_list);
49static u32 tipc_num_nodes;
47u32 tipc_own_tag; 50u32 tipc_own_tag;
48 51
49/** 52/**
53 * tipc_node_find - locate specified node object, if it exists
54 */
55
56struct tipc_node *tipc_node_find(u32 addr)
57{
58 struct tipc_node *node;
59 struct hlist_node *pos;
60
61 if (unlikely(!in_own_cluster(addr)))
62 return NULL;
63
64 hlist_for_each_entry(node, pos, &node_htable[tipc_hashfn(addr)], hash) {
65 if (node->addr == addr)
66 return node;
67 }
68 return NULL;
69}
70
71/**
50 * tipc_node_create - create neighboring node 72 * tipc_node_create - create neighboring node
51 * 73 *
52 * Currently, this routine is called by neighbor discovery code, which holds 74 * Currently, this routine is called by neighbor discovery code, which holds
@@ -58,8 +80,7 @@ u32 tipc_own_tag;
58 80
59struct tipc_node *tipc_node_create(u32 addr) 81struct tipc_node *tipc_node_create(u32 addr)
60{ 82{
61 struct tipc_node *n_ptr; 83 struct tipc_node *n_ptr, *temp_node;
62 u32 n_num;
63 84
64 spin_lock_bh(&node_create_lock); 85 spin_lock_bh(&node_create_lock);
65 86
@@ -78,12 +99,19 @@ struct tipc_node *tipc_node_create(u32 addr)
78 99
79 n_ptr->addr = addr; 100 n_ptr->addr = addr;
80 spin_lock_init(&n_ptr->lock); 101 spin_lock_init(&n_ptr->lock);
102 INIT_HLIST_NODE(&n_ptr->hash);
103 INIT_LIST_HEAD(&n_ptr->list);
81 INIT_LIST_HEAD(&n_ptr->nsub); 104 INIT_LIST_HEAD(&n_ptr->nsub);
82 105
83 n_num = tipc_node(addr); 106 hlist_add_head(&n_ptr->hash, &node_htable[tipc_hashfn(addr)]);
84 tipc_nodes[n_num] = n_ptr; 107
85 if (n_num > tipc_highest_node) 108 list_for_each_entry(temp_node, &tipc_node_list, list) {
86 tipc_highest_node = n_num; 109 if (n_ptr->addr < temp_node->addr)
110 break;
111 }
112 list_add_tail(&n_ptr->list, &temp_node->list);
113
114 tipc_num_nodes++;
87 115
88 spin_unlock_bh(&node_create_lock); 116 spin_unlock_bh(&node_create_lock);
89 return n_ptr; 117 return n_ptr;
@@ -91,18 +119,11 @@ struct tipc_node *tipc_node_create(u32 addr)
91 119
92void tipc_node_delete(struct tipc_node *n_ptr) 120void tipc_node_delete(struct tipc_node *n_ptr)
93{ 121{
94 u32 n_num; 122 list_del(&n_ptr->list);
95 123 hlist_del(&n_ptr->hash);
96 if (!n_ptr)
97 return;
98
99 n_num = tipc_node(n_ptr->addr);
100 tipc_nodes[n_num] = NULL;
101 kfree(n_ptr); 124 kfree(n_ptr);
102 125
103 while (!tipc_nodes[tipc_highest_node]) 126 tipc_num_nodes--;
104 if (--tipc_highest_node == 0)
105 break;
106} 127}
107 128
108 129
@@ -379,7 +400,6 @@ struct sk_buff *tipc_node_get_nodes(const void *req_tlv_area, int req_tlv_space)
379 struct tipc_node *n_ptr; 400 struct tipc_node *n_ptr;
380 struct tipc_node_info node_info; 401 struct tipc_node_info node_info;
381 u32 payload_size; 402 u32 payload_size;
382 u32 n_num;
383 403
384 if (!TLV_CHECK(req_tlv_area, req_tlv_space, TIPC_TLV_NET_ADDR)) 404 if (!TLV_CHECK(req_tlv_area, req_tlv_space, TIPC_TLV_NET_ADDR))
385 return tipc_cfg_reply_error_string(TIPC_CFG_TLV_ERROR); 405 return tipc_cfg_reply_error_string(TIPC_CFG_TLV_ERROR);
@@ -390,15 +410,14 @@ struct sk_buff *tipc_node_get_nodes(const void *req_tlv_area, int req_tlv_space)
390 " (network address)"); 410 " (network address)");
391 411
392 read_lock_bh(&tipc_net_lock); 412 read_lock_bh(&tipc_net_lock);
393 if (!tipc_nodes) { 413 if (!tipc_num_nodes) {
394 read_unlock_bh(&tipc_net_lock); 414 read_unlock_bh(&tipc_net_lock);
395 return tipc_cfg_reply_none(); 415 return tipc_cfg_reply_none();
396 } 416 }
397 417
398 /* For now, get space for all other nodes */ 418 /* For now, get space for all other nodes */
399 419
400 payload_size = TLV_SPACE(sizeof(node_info)) * 420 payload_size = TLV_SPACE(sizeof(node_info)) * tipc_num_nodes;
401 (tipc_highest_node - 1);
402 if (payload_size > 32768u) { 421 if (payload_size > 32768u) {
403 read_unlock_bh(&tipc_net_lock); 422 read_unlock_bh(&tipc_net_lock);
404 return tipc_cfg_reply_error_string(TIPC_CFG_NOT_SUPPORTED 423 return tipc_cfg_reply_error_string(TIPC_CFG_NOT_SUPPORTED
@@ -412,9 +431,8 @@ struct sk_buff *tipc_node_get_nodes(const void *req_tlv_area, int req_tlv_space)
412 431
413 /* Add TLVs for all nodes in scope */ 432 /* Add TLVs for all nodes in scope */
414 433
415 for (n_num = 1; n_num <= tipc_highest_node; n_num++) { 434 list_for_each_entry(n_ptr, &tipc_node_list, list) {
416 n_ptr = tipc_nodes[n_num]; 435 if (!tipc_in_scope(domain, n_ptr->addr))
417 if (!n_ptr || !tipc_in_scope(domain, n_ptr->addr))
418 continue; 436 continue;
419 node_info.addr = htonl(n_ptr->addr); 437 node_info.addr = htonl(n_ptr->addr);
420 node_info.up = htonl(tipc_node_is_up(n_ptr)); 438 node_info.up = htonl(tipc_node_is_up(n_ptr));
@@ -433,7 +451,6 @@ struct sk_buff *tipc_node_get_links(const void *req_tlv_area, int req_tlv_space)
433 struct tipc_node *n_ptr; 451 struct tipc_node *n_ptr;
434 struct tipc_link_info link_info; 452 struct tipc_link_info link_info;
435 u32 payload_size; 453 u32 payload_size;
436 u32 n_num;
437 454
438 if (!TLV_CHECK(req_tlv_area, req_tlv_space, TIPC_TLV_NET_ADDR)) 455 if (!TLV_CHECK(req_tlv_area, req_tlv_space, TIPC_TLV_NET_ADDR))
439 return tipc_cfg_reply_error_string(TIPC_CFG_TLV_ERROR); 456 return tipc_cfg_reply_error_string(TIPC_CFG_TLV_ERROR);
@@ -472,11 +489,10 @@ struct sk_buff *tipc_node_get_links(const void *req_tlv_area, int req_tlv_space)
472 489
473 /* Add TLVs for any other links in scope */ 490 /* Add TLVs for any other links in scope */
474 491
475 for (n_num = 1; n_num <= tipc_highest_node; n_num++) { 492 list_for_each_entry(n_ptr, &tipc_node_list, list) {
476 u32 i; 493 u32 i;
477 494
478 n_ptr = tipc_nodes[n_num]; 495 if (!tipc_in_scope(domain, n_ptr->addr))
479 if (!n_ptr || !tipc_in_scope(domain, n_ptr->addr))
480 continue; 496 continue;
481 tipc_node_lock(n_ptr); 497 tipc_node_lock(n_ptr);
482 for (i = 0; i < MAX_BEARERS; i++) { 498 for (i = 0; i < MAX_BEARERS; i++) {
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 @@
2 * net/tipc/node.h: Include file for TIPC node management routines 2 * net/tipc/node.h: Include file for TIPC node management routines
3 * 3 *
4 * Copyright (c) 2000-2006, Ericsson AB 4 * Copyright (c) 2000-2006, Ericsson AB
5 * Copyright (c) 2005, Wind River Systems 5 * Copyright (c) 2005, 2010-2011, Wind River Systems
6 * All rights reserved. 6 * All rights reserved.
7 * 7 *
8 * Redistribution and use in source and binary forms, with or without 8 * Redistribution and use in source and binary forms, with or without
@@ -46,7 +46,8 @@
46 * struct tipc_node - TIPC node structure 46 * struct tipc_node - TIPC node structure
47 * @addr: network address of node 47 * @addr: network address of node
48 * @lock: spinlock governing access to structure 48 * @lock: spinlock governing access to structure
49 * @next: pointer to next node in sorted list of cluster's nodes 49 * @hash: links to adjacent nodes in unsorted hash chain
50 * @list: links to adjacent nodes in sorted list of cluster's nodes
50 * @nsub: list of "node down" subscriptions monitoring node 51 * @nsub: list of "node down" subscriptions monitoring node
51 * @active_links: pointers to active links to node 52 * @active_links: pointers to active links to node
52 * @links: pointers to all links to node 53 * @links: pointers to all links to node
@@ -69,7 +70,8 @@
69struct tipc_node { 70struct tipc_node {
70 u32 addr; 71 u32 addr;
71 spinlock_t lock; 72 spinlock_t lock;
72 struct tipc_node *next; 73 struct hlist_node hash;
74 struct list_head list;
73 struct list_head nsub; 75 struct list_head nsub;
74 struct link *active_links[2]; 76 struct link *active_links[2];
75 struct link *links[MAX_BEARERS]; 77 struct link *links[MAX_BEARERS];
@@ -90,8 +92,23 @@ struct tipc_node {
90 } bclink; 92 } bclink;
91}; 93};
92 94
95#define NODE_HTABLE_SIZE 512
96extern struct list_head tipc_node_list;
97
98/*
99 * A trivial power-of-two bitmask technique is used for speed, since this
100 * operation is done for every incoming TIPC packet. The number of hash table
101 * entries has been chosen so that no hash chain exceeds 8 nodes and will
102 * usually be much smaller (typically only a single node).
103 */
104static inline unsigned int tipc_hashfn(u32 addr)
105{
106 return addr & (NODE_HTABLE_SIZE - 1);
107}
108
93extern u32 tipc_own_tag; 109extern u32 tipc_own_tag;
94 110
111struct tipc_node *tipc_node_find(u32 addr);
95struct tipc_node *tipc_node_create(u32 addr); 112struct tipc_node *tipc_node_create(u32 addr);
96void tipc_node_delete(struct tipc_node *n_ptr); 113void tipc_node_delete(struct tipc_node *n_ptr);
97struct tipc_node *tipc_node_attach_link(struct link *l_ptr); 114struct tipc_node *tipc_node_attach_link(struct link *l_ptr);
@@ -104,13 +121,6 @@ int tipc_node_is_up(struct tipc_node *n_ptr);
104struct sk_buff *tipc_node_get_links(const void *req_tlv_area, int req_tlv_space); 121struct sk_buff *tipc_node_get_links(const void *req_tlv_area, int req_tlv_space);
105struct sk_buff *tipc_node_get_nodes(const void *req_tlv_area, int req_tlv_space); 122struct sk_buff *tipc_node_get_nodes(const void *req_tlv_area, int req_tlv_space);
106 123
107static inline struct tipc_node *tipc_node_find(u32 addr)
108{
109 if (likely(in_own_cluster(addr)))
110 return tipc_nodes[tipc_node(addr)];
111 return NULL;
112}
113
114static inline void tipc_node_lock(struct tipc_node *n_ptr) 124static inline void tipc_node_lock(struct tipc_node *n_ptr)
115{ 125{
116 spin_lock_bh(&n_ptr->lock); 126 spin_lock_bh(&n_ptr->lock);