Lines Matching +full:sub +full:- +full:node
4 * Copyright (c) 2000-2006, 2014-2018, Ericsson AB
5 * Copyright (c) 2004-2008, 2010-2014, Wind River Systems
47 #include "node.h"
51 * struct service_range - container for all bindings of a service range
55 * @max: largest 'upper' in this node subtree
56 * @local_publ: list of identical publications made from this node
58 * @all_publ: all publications identical to this one, whatever node and scope
59 * Used by round-robin lookup algorithm
71 * struct tipc_service - container for all published instances of a service type
90 #define service_range_upper(sr) ((sr)->upper)
99 ((sr)->lower <= (end) && (sr)->upper >= (start)) in RB_DECLARE_CALLBACKS_MAX()
102 * service_range_foreach_match - iterate over tipc service rbtree for each in RB_DECLARE_CALLBACKS_MAX()
109 for (sr = service_range_match_first((sc)->ranges.rb_node, \ in RB_DECLARE_CALLBACKS_MAX()
113 sr = service_range_match_next(&(sr)->tree_node, \
118 * service_range_match_first - find first service range matching a range
119 * @n: the root node of service range rbtree for searching
122 * Return: the leftmost service range node in the rbtree that overlaps the
132 if (!n || service_range_entry(n)->max < start)
136 l = n->rb_left;
137 if (l && service_range_entry(l)->max >= start) {
138 /* A leftmost overlap range node must be one in the left
146 /* No one in the left subtree can match, return if this node is
154 r = n->rb_right;
155 if (sr->lower <= end &&
156 r && service_range_entry(r)->max >= start) {
167 * service_range_match_next - find next service range matching a range
168 * @n: a node in service range rbtree from which the searching starts
171 * Return: the next service range node to the given node in the rbtree that
181 r = n->rb_right; in service_range_match_next()
182 if (r && service_range_entry(r)->max >= start) in service_range_match_next()
183 /* A next overlap range node must be one in the right in service_range_match_next()
185 * successor (- an ancestor) of this node cannot in service_range_match_next()
191 * ancestor of this node which is parent of a left-hand child. in service_range_match_next()
193 while ((p = rb_parent(n)) && n == p->rb_right) in service_range_match_next()
204 if (sr->lower <= end) { in service_range_match_next()
216 return x & (TIPC_NAMETBL_SIZE - 1); in hash()
220 * tipc_publ_create - create a publication structure
223 u32 scope, u32 node, u32 port, in tipc_publ_create() argument
231 publ->type = type; in tipc_publ_create()
232 publ->lower = lower; in tipc_publ_create()
233 publ->upper = upper; in tipc_publ_create()
234 publ->scope = scope; in tipc_publ_create()
235 publ->node = node; in tipc_publ_create()
236 publ->port = port; in tipc_publ_create()
237 publ->key = key; in tipc_publ_create()
238 INIT_LIST_HEAD(&publ->binding_sock); in tipc_publ_create()
239 INIT_LIST_HEAD(&publ->binding_node); in tipc_publ_create()
240 INIT_LIST_HEAD(&publ->local_publ); in tipc_publ_create()
241 INIT_LIST_HEAD(&publ->all_publ); in tipc_publ_create()
242 INIT_LIST_HEAD(&publ->list); in tipc_publ_create()
247 * tipc_service_create - create a service structure for the specified 'type'
260 spin_lock_init(&service->lock); in tipc_service_create()
261 service->type = type; in tipc_service_create()
262 service->ranges = RB_ROOT; in tipc_service_create()
263 INIT_HLIST_NODE(&service->service_list); in tipc_service_create()
264 INIT_LIST_HEAD(&service->subscriptions); in tipc_service_create()
265 hlist_add_head_rcu(&service->service_list, hd); in tipc_service_create()
269 /* tipc_service_find_range - find service range matching publication parameters
278 if (sr->lower == lower && sr->upper == upper) in tipc_service_find_range()
291 n = &sc->ranges.rb_node; in tipc_service_create_range()
295 if (lower == sr->lower && upper == sr->upper) in tipc_service_create_range()
297 if (sr->max < upper) in tipc_service_create_range()
298 sr->max = upper; in tipc_service_create_range()
299 if (lower <= sr->lower) in tipc_service_create_range()
300 n = &parent->rb_left; in tipc_service_create_range()
302 n = &parent->rb_right; in tipc_service_create_range()
307 sr->lower = lower; in tipc_service_create_range()
308 sr->upper = upper; in tipc_service_create_range()
309 sr->max = upper; in tipc_service_create_range()
310 INIT_LIST_HEAD(&sr->local_publ); in tipc_service_create_range()
311 INIT_LIST_HEAD(&sr->all_publ); in tipc_service_create_range()
312 rb_link_node(&sr->tree_node, parent, n); in tipc_service_create_range()
313 rb_insert_augmented(&sr->tree_node, &sc->ranges, &sr_callbacks); in tipc_service_create_range()
321 u32 node, u32 port, in tipc_service_insert_publ() argument
324 struct tipc_subscription *sub, *tmp; in tipc_service_insert_publ() local
333 first = list_empty(&sr->all_publ); in tipc_service_insert_publ()
336 list_for_each_entry(p, &sr->all_publ, all_publ) { in tipc_service_insert_publ()
337 if (p->key == key && (!p->node || p->node == node)) in tipc_service_insert_publ()
342 p = tipc_publ_create(type, lower, upper, scope, node, port, key); in tipc_service_insert_publ()
346 p->id = sc->publ_cnt++; in tipc_service_insert_publ()
347 if (in_own_node(net, node)) in tipc_service_insert_publ()
348 list_add(&p->local_publ, &sr->local_publ); in tipc_service_insert_publ()
349 list_add(&p->all_publ, &sr->all_publ); in tipc_service_insert_publ()
352 list_for_each_entry_safe(sub, tmp, &sc->subscriptions, service_list) { in tipc_service_insert_publ()
353 tipc_sub_report_overlap(sub, p->lower, p->upper, TIPC_PUBLISHED, in tipc_service_insert_publ()
354 p->port, p->node, p->scope, first); in tipc_service_insert_publ()
363 * tipc_service_remove_publ - remove a publication from a service
366 u32 node, u32 key) in tipc_service_remove_publ() argument
370 list_for_each_entry(p, &sr->all_publ, all_publ) { in tipc_service_remove_publ()
371 if (p->key != key || (node && node != p->node)) in tipc_service_remove_publ()
373 list_del(&p->all_publ); in tipc_service_remove_publ()
374 list_del(&p->local_publ); in tipc_service_remove_publ()
383 #define publication_after(pa, pb) time_after32((pa)->id, (pb)->id)
395 * tipc_service_subscribe - attach a subscription, and optionally
400 struct tipc_subscription *sub) in tipc_service_subscribe() argument
402 struct tipc_subscr *sb = &sub->evt.s; in tipc_service_subscribe()
414 tipc_sub_get(sub); in tipc_service_subscribe()
415 list_add(&sub->service_list, &service->subscriptions); in tipc_service_subscribe()
423 list_for_each_entry(p, &sr->all_publ, all_publ) { in tipc_service_subscribe()
425 list_add_tail(&p->list, &publ_list); in tipc_service_subscribe()
431 list_add_tail(&first->list, &publ_list); in tipc_service_subscribe()
437 tipc_sub_report_overlap(sub, p->lower, p->upper, in tipc_service_subscribe()
438 TIPC_PUBLISHED, p->port, p->node, in tipc_service_subscribe()
439 p->scope, true); in tipc_service_subscribe()
440 list_del_init(&p->list); in tipc_service_subscribe()
450 service_head = &nt->services[hash(type)]; in tipc_service_find()
452 if (service->type == type) in tipc_service_find()
460 u32 scope, u32 node, in tipc_nametbl_insert_publ() argument
474 sc = tipc_service_create(type, &nt->services[hash(type)]); in tipc_nametbl_insert_publ()
478 spin_lock_bh(&sc->lock); in tipc_nametbl_insert_publ()
480 scope, node, port, key); in tipc_nametbl_insert_publ()
481 spin_unlock_bh(&sc->lock); in tipc_nametbl_insert_publ()
487 u32 node, u32 key) in tipc_nametbl_remove_publ() argument
490 struct tipc_subscription *sub, *tmp; in tipc_nametbl_remove_publ() local
498 spin_lock_bh(&sc->lock); in tipc_nametbl_remove_publ()
502 p = tipc_service_remove_publ(sr, node, key); in tipc_nametbl_remove_publ()
507 last = list_empty(&sr->all_publ); in tipc_nametbl_remove_publ()
508 list_for_each_entry_safe(sub, tmp, &sc->subscriptions, service_list) { in tipc_nametbl_remove_publ()
509 tipc_sub_report_overlap(sub, lower, upper, TIPC_WITHDRAWN, in tipc_nametbl_remove_publ()
510 p->port, node, p->scope, last); in tipc_nametbl_remove_publ()
514 if (list_empty(&sr->all_publ)) { in tipc_nametbl_remove_publ()
515 rb_erase_augmented(&sr->tree_node, &sc->ranges, &sr_callbacks); in tipc_nametbl_remove_publ()
520 if (RB_EMPTY_ROOT(&sc->ranges) && list_empty(&sc->subscriptions)) { in tipc_nametbl_remove_publ()
521 hlist_del_init_rcu(&sc->service_list); in tipc_nametbl_remove_publ()
525 spin_unlock_bh(&sc->lock); in tipc_nametbl_remove_publ()
530 * tipc_nametbl_translate - perform service instance to socket translation
535 * - if translation is deferred to another node, leave 'dnode' unchanged and
537 * - if translation is attempted and succeeds, set 'dnode' to the publishing
538 * node and return the published (non-zero) port number
539 * - if translation is attempted and fails, set 'dnode' to 0 and return 0
541 * Note that for legacy users (node configured with Z.C.N address format) the
542 * 'closest-first' lookup algorithm must be maintained, i.e., if dnode is 0
548 bool legacy = tn->legacy_addr_format; in tipc_nametbl_translate()
555 u32 node = 0; in tipc_nametbl_translate() local
565 spin_lock_bh(&sc->lock); in tipc_nametbl_translate()
567 /* Select lookup algo: local, closest-first or round-robin */ in tipc_nametbl_translate()
569 list = &sr->local_publ; in tipc_nametbl_translate()
574 list_move_tail(&p->local_publ, &sr->local_publ); in tipc_nametbl_translate()
575 } else if (legacy && !*dnode && !list_empty(&sr->local_publ)) { in tipc_nametbl_translate()
576 list = &sr->local_publ; in tipc_nametbl_translate()
579 list_move_tail(&p->local_publ, &sr->local_publ); in tipc_nametbl_translate()
581 list = &sr->all_publ; in tipc_nametbl_translate()
584 list_move_tail(&p->all_publ, &sr->all_publ); in tipc_nametbl_translate()
586 port = p->port; in tipc_nametbl_translate()
587 node = p->node; in tipc_nametbl_translate()
589 * "true" round-robin will be performed as needed. in tipc_nametbl_translate()
593 spin_unlock_bh(&sc->lock); in tipc_nametbl_translate()
597 *dnode = node; in tipc_nametbl_translate()
616 spin_lock_bh(&sc->lock); in tipc_nametbl_lookup()
619 sr = service_range_match_first(sc->ranges.rb_node, instance, instance); in tipc_nametbl_lookup()
623 list_for_each_entry(p, &sr->all_publ, all_publ) { in tipc_nametbl_lookup()
624 if (p->scope != scope) in tipc_nametbl_lookup()
626 if (p->port == exclude && p->node == self) in tipc_nametbl_lookup()
628 tipc_dest_push(dsts, p->node, p->port); in tipc_nametbl_lookup()
632 list_move_tail(&p->all_publ, &sr->all_publ); in tipc_nametbl_lookup()
636 spin_unlock_bh(&sc->lock); in tipc_nametbl_lookup()
654 spin_lock_bh(&sc->lock); in tipc_nametbl_mc_lookup()
656 list_for_each_entry(p, &sr->local_publ, local_publ) { in tipc_nametbl_mc_lookup()
657 if (p->scope == scope || (!exact && p->scope < scope)) in tipc_nametbl_mc_lookup()
658 tipc_dest_push(dports, 0, p->port); in tipc_nametbl_mc_lookup()
661 spin_unlock_bh(&sc->lock); in tipc_nametbl_mc_lookup()
666 /* tipc_nametbl_lookup_dst_nodes - find broadcast destination nodes
667 * - Creates list of nodes that overlap the given multicast address
668 * - Determines if any node local destinations overlap
682 spin_lock_bh(&sc->lock); in tipc_nametbl_lookup_dst_nodes()
684 list_for_each_entry(p, &sr->all_publ, all_publ) { in tipc_nametbl_lookup_dst_nodes()
685 tipc_nlist_add(nodes, p->node); in tipc_nametbl_lookup_dst_nodes()
688 spin_unlock_bh(&sc->lock); in tipc_nametbl_lookup_dst_nodes()
693 /* tipc_nametbl_build_group - build list of communication group members
708 spin_lock_bh(&sc->lock); in tipc_nametbl_build_group()
709 for (n = rb_first(&sc->ranges); n; n = rb_next(n)) { in tipc_nametbl_build_group()
711 list_for_each_entry(p, &sr->all_publ, all_publ) { in tipc_nametbl_build_group()
712 if (p->scope != scope) in tipc_nametbl_build_group()
714 tipc_group_add_member(grp, p->node, p->port, p->lower); in tipc_nametbl_build_group()
717 spin_unlock_bh(&sc->lock); in tipc_nametbl_build_group()
722 /* tipc_nametbl_publish - add service binding to name table
734 spin_lock_bh(&tn->nametbl_lock); in tipc_nametbl_publish()
736 if (nt->local_publ_count >= TIPC_MAX_PUBL) { in tipc_nametbl_publish()
744 nt->local_publ_count++; in tipc_nametbl_publish()
747 rc_dests = nt->rc_dests; in tipc_nametbl_publish()
749 spin_unlock_bh(&tn->nametbl_lock); in tipc_nametbl_publish()
758 * tipc_nametbl_withdraw - withdraw a service binding
770 spin_lock_bh(&tn->nametbl_lock); in tipc_nametbl_withdraw()
774 nt->local_publ_count--; in tipc_nametbl_withdraw()
776 list_del_init(&p->binding_sock); in tipc_nametbl_withdraw()
782 rc_dests = nt->rc_dests; in tipc_nametbl_withdraw()
783 spin_unlock_bh(&tn->nametbl_lock); in tipc_nametbl_withdraw()
793 * tipc_nametbl_subscribe - add a subscription object to the name table
795 bool tipc_nametbl_subscribe(struct tipc_subscription *sub) in tipc_nametbl_subscribe() argument
797 struct name_table *nt = tipc_name_table(sub->net); in tipc_nametbl_subscribe()
798 struct tipc_net *tn = tipc_net(sub->net); in tipc_nametbl_subscribe()
799 struct tipc_subscr *s = &sub->evt.s; in tipc_nametbl_subscribe()
804 spin_lock_bh(&tn->nametbl_lock); in tipc_nametbl_subscribe()
805 sc = tipc_service_find(sub->net, type); in tipc_nametbl_subscribe()
807 sc = tipc_service_create(type, &nt->services[hash(type)]); in tipc_nametbl_subscribe()
809 spin_lock_bh(&sc->lock); in tipc_nametbl_subscribe()
810 tipc_service_subscribe(sc, sub); in tipc_nametbl_subscribe()
811 spin_unlock_bh(&sc->lock); in tipc_nametbl_subscribe()
818 spin_unlock_bh(&tn->nametbl_lock); in tipc_nametbl_subscribe()
823 * tipc_nametbl_unsubscribe - remove a subscription object from name table
825 void tipc_nametbl_unsubscribe(struct tipc_subscription *sub) in tipc_nametbl_unsubscribe() argument
827 struct tipc_net *tn = tipc_net(sub->net); in tipc_nametbl_unsubscribe()
828 struct tipc_subscr *s = &sub->evt.s; in tipc_nametbl_unsubscribe()
832 spin_lock_bh(&tn->nametbl_lock); in tipc_nametbl_unsubscribe()
833 sc = tipc_service_find(sub->net, type); in tipc_nametbl_unsubscribe()
837 spin_lock_bh(&sc->lock); in tipc_nametbl_unsubscribe()
838 list_del_init(&sub->service_list); in tipc_nametbl_unsubscribe()
839 tipc_sub_put(sub); in tipc_nametbl_unsubscribe()
842 if (RB_EMPTY_ROOT(&sc->ranges) && list_empty(&sc->subscriptions)) { in tipc_nametbl_unsubscribe()
843 hlist_del_init_rcu(&sc->service_list); in tipc_nametbl_unsubscribe()
846 spin_unlock_bh(&sc->lock); in tipc_nametbl_unsubscribe()
848 spin_unlock_bh(&tn->nametbl_lock); in tipc_nametbl_unsubscribe()
859 return -ENOMEM; in tipc_nametbl_init()
862 INIT_HLIST_HEAD(&nt->services[i]); in tipc_nametbl_init()
864 INIT_LIST_HEAD(&nt->node_scope); in tipc_nametbl_init()
865 INIT_LIST_HEAD(&nt->cluster_scope); in tipc_nametbl_init()
866 rwlock_init(&nt->cluster_scope_lock); in tipc_nametbl_init()
867 tn->nametbl = nt; in tipc_nametbl_init()
868 spin_lock_init(&tn->nametbl_lock); in tipc_nametbl_init()
873 * tipc_service_delete - purge all publications for a service and delete it
880 spin_lock_bh(&sc->lock); in tipc_service_delete()
881 rbtree_postorder_for_each_entry_safe(sr, tmpr, &sc->ranges, tree_node) { in tipc_service_delete()
882 list_for_each_entry_safe(p, tmp, &sr->all_publ, all_publ) { in tipc_service_delete()
883 tipc_service_remove_publ(sr, p->node, p->key); in tipc_service_delete()
886 rb_erase_augmented(&sr->tree_node, &sc->ranges, &sr_callbacks); in tipc_service_delete()
889 hlist_del_init_rcu(&sc->service_list); in tipc_service_delete()
890 spin_unlock_bh(&sc->lock); in tipc_service_delete()
905 spin_lock_bh(&tn->nametbl_lock); in tipc_nametbl_stop()
907 if (hlist_empty(&nt->services[i])) in tipc_nametbl_stop()
909 service_head = &nt->services[i]; in tipc_nametbl_stop()
914 spin_unlock_bh(&tn->nametbl_lock); in tipc_nametbl_stop()
931 list_for_each_entry(p, &sr->all_publ, all_publ) in __tipc_nl_add_nametable_publ()
932 if (p->key == *last_key) in __tipc_nl_add_nametable_publ()
934 if (p->key != *last_key) in __tipc_nl_add_nametable_publ()
935 return -EPIPE; in __tipc_nl_add_nametable_publ()
937 p = list_first_entry(&sr->all_publ, in __tipc_nl_add_nametable_publ()
942 list_for_each_entry_from(p, &sr->all_publ, all_publ) { in __tipc_nl_add_nametable_publ()
943 *last_key = p->key; in __tipc_nl_add_nametable_publ()
945 hdr = genlmsg_put(msg->skb, msg->portid, msg->seq, in __tipc_nl_add_nametable_publ()
949 return -EMSGSIZE; in __tipc_nl_add_nametable_publ()
951 attrs = nla_nest_start_noflag(msg->skb, TIPC_NLA_NAME_TABLE); in __tipc_nl_add_nametable_publ()
955 b = nla_nest_start_noflag(msg->skb, TIPC_NLA_NAME_TABLE_PUBL); in __tipc_nl_add_nametable_publ()
959 if (nla_put_u32(msg->skb, TIPC_NLA_PUBL_TYPE, service->type)) in __tipc_nl_add_nametable_publ()
961 if (nla_put_u32(msg->skb, TIPC_NLA_PUBL_LOWER, sr->lower)) in __tipc_nl_add_nametable_publ()
963 if (nla_put_u32(msg->skb, TIPC_NLA_PUBL_UPPER, sr->upper)) in __tipc_nl_add_nametable_publ()
965 if (nla_put_u32(msg->skb, TIPC_NLA_PUBL_SCOPE, p->scope)) in __tipc_nl_add_nametable_publ()
967 if (nla_put_u32(msg->skb, TIPC_NLA_PUBL_NODE, p->node)) in __tipc_nl_add_nametable_publ()
969 if (nla_put_u32(msg->skb, TIPC_NLA_PUBL_REF, p->port)) in __tipc_nl_add_nametable_publ()
971 if (nla_put_u32(msg->skb, TIPC_NLA_PUBL_KEY, p->key)) in __tipc_nl_add_nametable_publ()
974 nla_nest_end(msg->skb, b); in __tipc_nl_add_nametable_publ()
975 nla_nest_end(msg->skb, attrs); in __tipc_nl_add_nametable_publ()
976 genlmsg_end(msg->skb, hdr); in __tipc_nl_add_nametable_publ()
983 nla_nest_cancel(msg->skb, b); in __tipc_nl_add_nametable_publ()
985 nla_nest_cancel(msg->skb, attrs); in __tipc_nl_add_nametable_publ()
987 genlmsg_cancel(msg->skb, hdr); in __tipc_nl_add_nametable_publ()
989 return -EMSGSIZE; in __tipc_nl_add_nametable_publ()
1000 for (n = rb_first(&sc->ranges); n; n = rb_next(n)) { in __tipc_nl_service_range_list()
1002 if (sr->lower < *last_lower) in __tipc_nl_service_range_list()
1006 *last_lower = sr->lower; in __tipc_nl_service_range_list()
1029 head = &tn->nametbl->services[i]; in tipc_nl_service_list()
1035 return -EPIPE; in tipc_nl_service_list()
1044 spin_lock_bh(&service->lock); in tipc_nl_service_list()
1050 *last_type = service->type; in tipc_nl_service_list()
1051 spin_unlock_bh(&service->lock); in tipc_nl_service_list()
1054 spin_unlock_bh(&service->lock); in tipc_nl_service_list()
1063 struct net *net = sock_net(skb->sk); in tipc_nl_name_table_dump()
1064 u32 last_type = cb->args[0]; in tipc_nl_name_table_dump()
1065 u32 last_lower = cb->args[1]; in tipc_nl_name_table_dump()
1066 u32 last_key = cb->args[2]; in tipc_nl_name_table_dump()
1067 int done = cb->args[3]; in tipc_nl_name_table_dump()
1075 msg.portid = NETLINK_CB(cb->skb).portid; in tipc_nl_name_table_dump()
1076 msg.seq = cb->nlh->nlmsg_seq; in tipc_nl_name_table_dump()
1083 } else if (err != -EMSGSIZE) { in tipc_nl_name_table_dump()
1090 cb->prev_seq = 1; in tipc_nl_name_table_dump()
1094 cb->args[0] = last_type; in tipc_nl_name_table_dump()
1095 cb->args[1] = last_lower; in tipc_nl_name_table_dump()
1096 cb->args[2] = last_key; in tipc_nl_name_table_dump()
1097 cb->args[3] = done; in tipc_nl_name_table_dump()
1099 return skb->len; in tipc_nl_name_table_dump()
1102 struct tipc_dest *tipc_dest_find(struct list_head *l, u32 node, u32 port) in tipc_dest_find() argument
1107 if (dst->node == node && dst->port == port) in tipc_dest_find()
1113 bool tipc_dest_push(struct list_head *l, u32 node, u32 port) in tipc_dest_push() argument
1117 if (tipc_dest_find(l, node, port)) in tipc_dest_push()
1123 dst->node = node; in tipc_dest_push()
1124 dst->port = port; in tipc_dest_push()
1125 list_add(&dst->list, l); in tipc_dest_push()
1129 bool tipc_dest_pop(struct list_head *l, u32 *node, u32 *port) in tipc_dest_pop() argument
1137 *port = dst->port; in tipc_dest_pop()
1138 if (node) in tipc_dest_pop()
1139 *node = dst->node; in tipc_dest_pop()
1140 list_del(&dst->list); in tipc_dest_pop()
1145 bool tipc_dest_del(struct list_head *l, u32 node, u32 port) in tipc_dest_del() argument
1149 dst = tipc_dest_find(l, node, port); in tipc_dest_del()
1152 list_del(&dst->list); in tipc_dest_del()
1162 list_del(&dst->list); in tipc_dest_list_purge()