* net/tipc/name_table.c: TIPC name table code
*
* Copyright (c) 2000-2006, Ericsson AB
- * Copyright (c) 2004-2005, Wind River Systems
+ * Copyright (c) 2004-2008, 2010-2011, Wind River Systems
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
#include "core.h"
#include "config.h"
-#include "dbg.h"
#include "name_table.h"
#include "name_distr.h"
-#include "addr.h"
-#include "node_subscr.h"
#include "subscr.h"
#include "port.h"
-#include "cluster.h"
-#include "bcast.h"
static int tipc_nametbl_size = 1024; /* must be a power of 2 */
+/**
+ * struct name_info - name sequence publication info
+ * @node_list: circular list of publications made by own node
+ * @cluster_list: circular list of publications made by own cluster
+ * @zone_list: circular list of publications made by own zone
+ * @node_list_size: number of entries in "node_list"
+ * @cluster_list_size: number of entries in "cluster_list"
+ * @zone_list_size: number of entries in "zone_list"
+ *
+ * Note: The zone list always contains at least one entry, since all
+ * publications of the associated name sequence belong to it.
+ * (The cluster and node lists may be empty.)
+ */
+
+struct name_info {
+ struct list_head node_list;
+ struct list_head cluster_list;
+ struct list_head zone_list;
+ u32 node_list_size;
+ u32 cluster_list_size;
+ u32 zone_list_size;
+};
+
/**
* struct sub_seq - container for all published instances of a name sequence
* @lower: name sequence lower bound
* @upper: name sequence upper bound
- * @node_list: circular list of matching publications with >= node scope
- * @cluster_list: circular list of matching publications with >= cluster scope
- * @zone_list: circular list of matching publications with >= zone scope
+ * @info: pointer to name sequence publication info
*/
struct sub_seq {
u32 lower;
u32 upper;
- struct publication *node_list;
- struct publication *cluster_list;
- struct publication *zone_list;
+ struct name_info *info;
};
/**
u32 local_publ_count;
};
-static struct name_table table = { NULL } ;
+static struct name_table table;
static atomic_t rsv_publ_ok = ATOMIC_INIT(0);
DEFINE_RWLOCK(tipc_nametbl_lock);
static int hash(int x)
{
- return(x & (tipc_nametbl_size - 1));
+ return x & (tipc_nametbl_size - 1);
}
/**
spin_lock_init(&nseq->lock);
nseq->type = type;
nseq->sseqs = sseq;
- dbg("tipc_nameseq_create(): nseq = %p, type %u, ssseqs %p, ff: %u\n",
- nseq, type, nseq->sseqs, nseq->first_free);
nseq->alloc = 1;
INIT_HLIST_NODE(&nseq->ns_list);
INIT_LIST_HEAD(&nseq->subscriptions);
struct subscription *st;
struct publication *publ;
struct sub_seq *sseq;
+ struct name_info *info;
int created_subseq = 0;
sseq = nameseq_find_subseq(nseq, lower);
- dbg("nameseq_ins: for seq %p, {%u,%u}, found sseq %p\n",
- nseq, type, lower, sseq);
if (sseq) {
/* Lower end overlaps existing entry => need an exact match */
type, lower, upper);
return NULL;
}
+
+ info = sseq->info;
} else {
u32 inspos;
struct sub_seq *freesseq;
type, lower, upper);
return NULL;
}
- dbg("Allocated %u more sseqs\n", nseq->alloc);
memcpy(sseqs, nseq->sseqs,
nseq->alloc * sizeof(struct sub_seq));
kfree(nseq->sseqs);
nseq->sseqs = sseqs;
nseq->alloc *= 2;
}
- dbg("Have %u sseqs for type %u\n", nseq->alloc, type);
+
+ info = kzalloc(sizeof(*info), GFP_ATOMIC);
+ if (!info) {
+ warn("Cannot publish {%u,%u,%u}, no memory\n",
+ type, lower, upper);
+ return NULL;
+ }
+
+ INIT_LIST_HEAD(&info->node_list);
+ INIT_LIST_HEAD(&info->cluster_list);
+ INIT_LIST_HEAD(&info->zone_list);
/* Insert new sub-sequence */
- dbg("ins in pos %u, ff = %u\n", inspos, nseq->first_free);
sseq = &nseq->sseqs[inspos];
freesseq = &nseq->sseqs[nseq->first_free];
- memmove(sseq + 1, sseq, (freesseq - sseq) * sizeof (*sseq));
- memset(sseq, 0, sizeof (*sseq));
+ memmove(sseq + 1, sseq, (freesseq - sseq) * sizeof(*sseq));
+ memset(sseq, 0, sizeof(*sseq));
nseq->first_free++;
sseq->lower = lower;
sseq->upper = upper;
+ sseq->info = info;
created_subseq = 1;
}
- dbg("inserting {%u,%u,%u} from <0x%x:%u> into sseq %p(%u,%u) of seq %p\n",
- type, lower, upper, node, port, sseq,
- sseq->lower, sseq->upper, nseq);
/* Insert a publication: */
publ = publ_create(type, lower, upper, scope, node, port, key);
if (!publ)
return NULL;
- dbg("inserting publ %p, node=0x%x publ->node=0x%x, subscr->node=%p\n",
- publ, node, publ->node, publ->subscr.node);
-
- if (!sseq->zone_list)
- sseq->zone_list = publ->zone_list_next = publ;
- else {
- publ->zone_list_next = sseq->zone_list->zone_list_next;
- sseq->zone_list->zone_list_next = publ;
- }
+
+ list_add(&publ->zone_list, &info->zone_list);
+ info->zone_list_size++;
if (in_own_cluster(node)) {
- if (!sseq->cluster_list)
- sseq->cluster_list = publ->cluster_list_next = publ;
- else {
- publ->cluster_list_next =
- sseq->cluster_list->cluster_list_next;
- sseq->cluster_list->cluster_list_next = publ;
- }
+ list_add(&publ->cluster_list, &info->cluster_list);
+ info->cluster_list_size++;
}
if (node == tipc_own_addr) {
- if (!sseq->node_list)
- sseq->node_list = publ->node_list_next = publ;
- else {
- publ->node_list_next = sseq->node_list->node_list_next;
- sseq->node_list->node_list_next = publ;
- }
+ list_add(&publ->node_list, &info->node_list);
+ info->node_list_size++;
}
/*
* Any subscriptions waiting for notification?
*/
list_for_each_entry_safe(s, st, &nseq->subscriptions, nameseq_list) {
- dbg("calling report_overlap()\n");
tipc_subscr_report_overlap(s,
publ->lower,
publ->upper,
u32 node, u32 ref, u32 key)
{
struct publication *publ;
- struct publication *curr;
- struct publication *prev;
struct sub_seq *sseq = nameseq_find_subseq(nseq, inst);
+ struct name_info *info;
struct sub_seq *free;
struct subscription *s, *st;
int removed_subseq = 0;
if (!sseq)
return NULL;
- dbg("tipc_nameseq_remove_publ: seq: %p, sseq %p, {%u,%u}, key %u\n",
- nseq, sseq, nseq->type, inst, key);
+ info = sseq->info;
- /* Remove publication from zone scope list */
+ /* Locate publication, if it exists */
- prev = sseq->zone_list;
- publ = sseq->zone_list->zone_list_next;
- while ((publ->key != key) || (publ->ref != ref) ||
- (publ->node && (publ->node != node))) {
- prev = publ;
- publ = publ->zone_list_next;
- if (prev == sseq->zone_list) {
+ list_for_each_entry(publ, &info->zone_list, zone_list) {
+ if ((publ->key == key) && (publ->ref == ref) &&
+ (!publ->node || (publ->node == node)))
+ goto found;
+ }
+ return NULL;
- /* Prevent endless loop if publication not found */
+found:
+ /* Remove publication from zone scope list */
- return NULL;
- }
- }
- if (publ != sseq->zone_list)
- prev->zone_list_next = publ->zone_list_next;
- else if (publ->zone_list_next != publ) {
- prev->zone_list_next = publ->zone_list_next;
- sseq->zone_list = publ->zone_list_next;
- } else {
- sseq->zone_list = NULL;
- }
+ list_del(&publ->zone_list);
+ info->zone_list_size--;
/* Remove publication from cluster scope list, if present */
if (in_own_cluster(node)) {
- prev = sseq->cluster_list;
- curr = sseq->cluster_list->cluster_list_next;
- while (curr != publ) {
- prev = curr;
- curr = curr->cluster_list_next;
- if (prev == sseq->cluster_list) {
-
- /* Prevent endless loop for malformed list */
-
- err("Unable to de-list cluster publication\n"
- "{%u%u}, node=0x%x, ref=%u, key=%u)\n",
- publ->type, publ->lower, publ->node,
- publ->ref, publ->key);
- goto end_cluster;
- }
- }
- if (publ != sseq->cluster_list)
- prev->cluster_list_next = publ->cluster_list_next;
- else if (publ->cluster_list_next != publ) {
- prev->cluster_list_next = publ->cluster_list_next;
- sseq->cluster_list = publ->cluster_list_next;
- } else {
- sseq->cluster_list = NULL;
- }
+ list_del(&publ->cluster_list);
+ info->cluster_list_size--;
}
-end_cluster:
/* Remove publication from node scope list, if present */
if (node == tipc_own_addr) {
- prev = sseq->node_list;
- curr = sseq->node_list->node_list_next;
- while (curr != publ) {
- prev = curr;
- curr = curr->node_list_next;
- if (prev == sseq->node_list) {
-
- /* Prevent endless loop for malformed list */
-
- err("Unable to de-list node publication\n"
- "{%u%u}, node=0x%x, ref=%u, key=%u)\n",
- publ->type, publ->lower, publ->node,
- publ->ref, publ->key);
- goto end_node;
- }
- }
- if (publ != sseq->node_list)
- prev->node_list_next = publ->node_list_next;
- else if (publ->node_list_next != publ) {
- prev->node_list_next = publ->node_list_next;
- sseq->node_list = publ->node_list_next;
- } else {
- sseq->node_list = NULL;
- }
+ list_del(&publ->node_list);
+ info->node_list_size--;
}
-end_node:
/* Contract subseq list if no more publications for that subseq */
- if (!sseq->zone_list) {
+ if (list_empty(&info->zone_list)) {
+ kfree(info);
free = &nseq->sseqs[nseq->first_free--];
- memmove(sseq, sseq + 1, (free - (sseq + 1)) * sizeof (*sseq));
+ memmove(sseq, sseq + 1, (free - (sseq + 1)) * sizeof(*sseq));
removed_subseq = 1;
}
return;
while (sseq != &nseq->sseqs[nseq->first_free]) {
- struct publication *zl = sseq->zone_list;
- if (zl && tipc_subscr_overlap(s,sseq->lower,sseq->upper)) {
- struct publication *crs = zl;
+ if (tipc_subscr_overlap(s, sseq->lower, sseq->upper)) {
+ struct publication *crs;
+ struct name_info *info = sseq->info;
int must_report = 1;
- do {
+ list_for_each_entry(crs, &info->zone_list, zone_list) {
tipc_subscr_report_overlap(s,
sseq->lower,
sseq->upper,
crs->node,
must_report);
must_report = 0;
- crs = crs->zone_list_next;
- } while (crs != zl);
+ }
}
sseq++;
}
struct hlist_node *seq_node;
struct name_seq *ns;
- dbg("find_seq %u,(%u,0x%x) table = %p, hash[type] = %u\n",
- type, ntohl(type), type, table.types, hash(type));
-
seq_head = &table.types[hash(type)];
hlist_for_each_entry(ns, seq_node, seq_head, ns_list) {
- if (ns->type == type) {
- dbg("found %p\n", ns);
+ if (ns->type == type)
return ns;
- }
}
return NULL;
{
struct name_seq *seq = nametbl_find_seq(type);
- dbg("tipc_nametbl_insert_publ: {%u,%u,%u} found %p\n", type, lower, upper, seq);
if (lower > upper) {
warn("Failed to publish illegal {%u,%u,%u}\n",
type, lower, upper);
return NULL;
}
- dbg("Publishing {%u,%u,%u} from 0x%x\n", type, lower, upper, node);
- if (!seq) {
+ if (!seq)
seq = tipc_nameseq_create(type, &table.types[hash(type)]);
- dbg("tipc_nametbl_insert_publ: created %p\n", seq);
- }
if (!seq)
return NULL;
if (!seq)
return NULL;
- dbg("Withdrawing {%u,%u} from 0x%x\n", type, lower, node);
publ = tipc_nameseq_remove_publ(seq, lower, node, ref, key);
if (!seq->first_free && list_empty(&seq->subscriptions)) {
}
/*
- * tipc_nametbl_translate(): Translate tipc_name -> tipc_portid.
- * Very time-critical.
+ * tipc_nametbl_translate - translate name to port id
*
* Note: on entry 'destnode' is the search domain used during translation;
* on exit it passes back the node address of the matching port (if any)
u32 tipc_nametbl_translate(u32 type, u32 instance, u32 *destnode)
{
struct sub_seq *sseq;
- struct publication *publ = NULL;
+ struct name_info *info;
+ struct publication *publ;
struct name_seq *seq;
- u32 ref;
+ u32 ref = 0;
- if (!in_scope(*destnode, tipc_own_addr))
+ if (!tipc_in_scope(*destnode, tipc_own_addr))
return 0;
read_lock_bh(&tipc_nametbl_lock);
if (unlikely(!sseq))
goto not_found;
spin_lock_bh(&seq->lock);
+ info = sseq->info;
/* Closest-First Algorithm: */
if (likely(!*destnode)) {
- publ = sseq->node_list;
- if (publ) {
- sseq->node_list = publ->node_list_next;
-found:
- ref = publ->ref;
- *destnode = publ->node;
- spin_unlock_bh(&seq->lock);
- read_unlock_bh(&tipc_nametbl_lock);
- return ref;
- }
- publ = sseq->cluster_list;
- if (publ) {
- sseq->cluster_list = publ->cluster_list_next;
- goto found;
- }
- publ = sseq->zone_list;
- if (publ) {
- sseq->zone_list = publ->zone_list_next;
- goto found;
+ if (!list_empty(&info->node_list)) {
+ publ = list_first_entry(&info->node_list,
+ struct publication,
+ node_list);
+ list_move_tail(&publ->node_list,
+ &info->node_list);
+ } else if (!list_empty(&info->cluster_list)) {
+ publ = list_first_entry(&info->cluster_list,
+ struct publication,
+ cluster_list);
+ list_move_tail(&publ->cluster_list,
+ &info->cluster_list);
+ } else {
+ publ = list_first_entry(&info->zone_list,
+ struct publication,
+ zone_list);
+ list_move_tail(&publ->zone_list,
+ &info->zone_list);
}
}
/* Round-Robin Algorithm: */
else if (*destnode == tipc_own_addr) {
- publ = sseq->node_list;
- if (publ) {
- sseq->node_list = publ->node_list_next;
- goto found;
- }
+ if (list_empty(&info->node_list))
+ goto no_match;
+ publ = list_first_entry(&info->node_list, struct publication,
+ node_list);
+ list_move_tail(&publ->node_list, &info->node_list);
} else if (in_own_cluster(*destnode)) {
- publ = sseq->cluster_list;
- if (publ) {
- sseq->cluster_list = publ->cluster_list_next;
- goto found;
- }
+ if (list_empty(&info->cluster_list))
+ goto no_match;
+ publ = list_first_entry(&info->cluster_list, struct publication,
+ cluster_list);
+ list_move_tail(&publ->cluster_list, &info->cluster_list);
} else {
- publ = sseq->zone_list;
- if (publ) {
- sseq->zone_list = publ->zone_list_next;
- goto found;
- }
+ publ = list_first_entry(&info->zone_list, struct publication,
+ zone_list);
+ list_move_tail(&publ->zone_list, &info->zone_list);
}
+
+ ref = publ->ref;
+ *destnode = publ->node;
+no_match:
spin_unlock_bh(&seq->lock);
not_found:
- *destnode = 0;
read_unlock_bh(&tipc_nametbl_lock);
- return 0;
+ return ref;
}
/**
struct name_seq *seq;
struct sub_seq *sseq;
struct sub_seq *sseq_stop;
+ struct name_info *info;
int res = 0;
read_lock_bh(&tipc_nametbl_lock);
if (sseq->lower > upper)
break;
- publ = sseq->cluster_list;
- if (publ)
- do {
- if (publ->scope > limit)
- /* ignore out-of-scope publication */ ;
- else if (publ->node == tipc_own_addr)
- tipc_port_list_add(dports, publ->ref);
- else
- res = 1;
- publ = publ->cluster_list_next;
- } while (publ != sseq->cluster_list);
+
+ info = sseq->info;
+ list_for_each_entry(publ, &info->node_list, node_list) {
+ if (publ->scope <= limit)
+ tipc_port_list_add(dports, publ->ref);
+ }
+
+ if (info->cluster_list_size != info->node_list_size)
+ res = 1;
}
spin_unlock_bh(&seq->lock);
table.local_publ_count++;
publ = tipc_nametbl_insert_publ(type, lower, upper, scope,
tipc_own_addr, port_ref, key);
- if (publ && (scope != TIPC_NODE_SCOPE)) {
+ if (publ && (scope != TIPC_NODE_SCOPE))
tipc_named_publish(publ);
- }
write_unlock_bh(&tipc_nametbl_lock);
return publ;
}
{
struct publication *publ;
- dbg("tipc_nametbl_withdraw: {%u,%u}, key=%u\n", type, lower, key);
write_lock_bh(&tipc_nametbl_lock);
publ = tipc_nametbl_remove_publ(type, lower, tipc_own_addr, ref, key);
if (likely(publ)) {
write_lock_bh(&tipc_nametbl_lock);
seq = nametbl_find_seq(type);
- if (!seq) {
+ if (!seq)
seq = tipc_nameseq_create(type, &table.types[hash(type)]);
- }
- if (seq){
+ if (seq) {
spin_lock_bh(&seq->lock);
- dbg("tipc_nametbl_subscribe:found %p for {%u,%u,%u}\n",
- seq, type, s->seq.lower, s->seq.upper);
tipc_nameseq_subscribe(seq, s);
spin_unlock_bh(&seq->lock);
} else {
write_lock_bh(&tipc_nametbl_lock);
seq = nametbl_find_seq(s->seq.type);
- if (seq != NULL){
+ if (seq != NULL) {
spin_lock_bh(&seq->lock);
list_del_init(&s->nameseq_list);
spin_unlock_bh(&seq->lock);
u32 index)
{
char portIdStr[27];
- char *scopeStr;
- struct publication *publ = sseq->zone_list;
+ const char *scope_str[] = {"", " zone", " cluster", " node"};
+ struct publication *publ;
+ struct name_info *info;
tipc_printf(buf, "%-10u %-10u ", sseq->lower, sseq->upper);
- if (depth == 2 || !publ) {
+ if (depth == 2) {
tipc_printf(buf, "\n");
return;
}
- do {
- sprintf (portIdStr, "<%u.%u.%u:%u>",
+ info = sseq->info;
+
+ list_for_each_entry(publ, &info->zone_list, zone_list) {
+ sprintf(portIdStr, "<%u.%u.%u:%u>",
tipc_zone(publ->node), tipc_cluster(publ->node),
tipc_node(publ->node), publ->ref);
tipc_printf(buf, "%-26s ", portIdStr);
if (depth > 3) {
- if (publ->node != tipc_own_addr)
- scopeStr = "";
- else if (publ->scope == TIPC_NODE_SCOPE)
- scopeStr = "node";
- else if (publ->scope == TIPC_CLUSTER_SCOPE)
- scopeStr = "cluster";
- else
- scopeStr = "zone";
- tipc_printf(buf, "%-10u %s", publ->key, scopeStr);
+ tipc_printf(buf, "%-10u %s", publ->key,
+ scope_str[publ->scope]);
}
-
- publ = publ->zone_list_next;
- if (publ == sseq->zone_list)
- break;
-
- tipc_printf(buf, "\n%33s", " ");
- } while (1);
+ if (!list_is_last(&publ->zone_list, &info->zone_list))
+ tipc_printf(buf, "\n%33s", " ");
+ };
tipc_printf(buf, "\n");
}
static void nametbl_header(struct print_buf *buf, u32 depth)
{
- tipc_printf(buf, "Type ");
-
- if (depth > 1)
- tipc_printf(buf, "Lower Upper ");
- if (depth > 2)
- tipc_printf(buf, "Port Identity ");
- if (depth > 3)
- tipc_printf(buf, "Publication");
-
- tipc_printf(buf, "\n-----------");
-
- if (depth > 1)
- tipc_printf(buf, "--------------------- ");
- if (depth > 2)
- tipc_printf(buf, "-------------------------- ");
- if (depth > 3)
- tipc_printf(buf, "------------------");
-
+ const char *header[] = {
+ "Type ",
+ "Lower Upper ",
+ "Port Identity ",
+ "Publication Scope"
+ };
+
+ int i;
+
+ if (depth > 4)
+ depth = 4;
+ for (i = 0; i < depth; i++)
+ tipc_printf(buf, header[i]);
tipc_printf(buf, "\n");
}
}
}
-#if 0
-void tipc_nametbl_print(struct print_buf *buf, const char *str)
-{
- tipc_printf(buf, str);
- read_lock_bh(&tipc_nametbl_lock);
- nametbl_list(buf, 0, 0, 0, 0);
- read_unlock_bh(&tipc_nametbl_lock);
-}
-#endif
-
#define MAX_NAME_TBL_QUERY 32768
struct sk_buff *tipc_nametbl_get(const void *req_tlv_area, int req_tlv_space)
return buf;
}
-#if 0
-void tipc_nametbl_dump(void)
-{
- nametbl_list(TIPC_CONS, 0, 0, 0, 0);
-}
-#endif
-
int tipc_nametbl_init(void)
{
table.types = kcalloc(tipc_nametbl_size, sizeof(struct hlist_head),