name_table.c 28 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084
  1. /*
  2. * net/tipc/name_table.c: TIPC name table code
  3. *
  4. * Copyright (c) 2000-2006, Ericsson AB
  5. * Copyright (c) 2004-2005, Wind River Systems
  6. * All rights reserved.
  7. *
  8. * Redistribution and use in source and binary forms, with or without
  9. * modification, are permitted provided that the following conditions are met:
  10. *
  11. * 1. Redistributions of source code must retain the above copyright
  12. * notice, this list of conditions and the following disclaimer.
  13. * 2. Redistributions in binary form must reproduce the above copyright
  14. * notice, this list of conditions and the following disclaimer in the
  15. * documentation and/or other materials provided with the distribution.
  16. * 3. Neither the names of the copyright holders nor the names of its
  17. * contributors may be used to endorse or promote products derived from
  18. * this software without specific prior written permission.
  19. *
  20. * Alternatively, this software may be distributed under the terms of the
  21. * GNU General Public License ("GPL") version 2 as published by the Free
  22. * Software Foundation.
  23. *
  24. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  25. * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27. * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  28. * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  29. * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  30. * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  31. * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  32. * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  33. * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  34. * POSSIBILITY OF SUCH DAMAGE.
  35. */
  36. #include "core.h"
  37. #include "config.h"
  38. #include "dbg.h"
  39. #include "name_table.h"
  40. #include "name_distr.h"
  41. #include "addr.h"
  42. #include "node_subscr.h"
  43. #include "subscr.h"
  44. #include "port.h"
  45. #include "cluster.h"
  46. #include "bcast.h"
  47. static int tipc_nametbl_size = 1024; /* must be a power of 2 */
  48. /**
  49. * struct sub_seq - container for all published instances of a name sequence
  50. * @lower: name sequence lower bound
  51. * @upper: name sequence upper bound
  52. * @node_list: circular list of matching publications with >= node scope
  53. * @cluster_list: circular list of matching publications with >= cluster scope
  54. * @zone_list: circular list of matching publications with >= zone scope
  55. */
  56. struct sub_seq {
  57. u32 lower;
  58. u32 upper;
  59. struct publication *node_list;
  60. struct publication *cluster_list;
  61. struct publication *zone_list;
  62. };
  63. /**
  64. * struct name_seq - container for all published instances of a name type
  65. * @type: 32 bit 'type' value for name sequence
  66. * @sseq: pointer to dynamically-sized array of sub-sequences of this 'type';
  67. * sub-sequences are sorted in ascending order
  68. * @alloc: number of sub-sequences currently in array
  69. * @first_free: array index of first unused sub-sequence entry
  70. * @ns_list: links to adjacent name sequences in hash chain
  71. * @subscriptions: list of subscriptions for this 'type'
  72. * @lock: spinlock controlling access to name sequence structure
  73. */
  74. struct name_seq {
  75. u32 type;
  76. struct sub_seq *sseqs;
  77. u32 alloc;
  78. u32 first_free;
  79. struct hlist_node ns_list;
  80. struct list_head subscriptions;
  81. spinlock_t lock;
  82. };
  83. /**
  84. * struct name_table - table containing all existing port name publications
  85. * @types: pointer to fixed-sized array of name sequence lists,
  86. * accessed via hashing on 'type'; name sequence lists are *not* sorted
  87. * @local_publ_count: number of publications issued by this node
  88. */
  89. struct name_table {
  90. struct hlist_head *types;
  91. u32 local_publ_count;
  92. };
  93. static struct name_table table = { NULL } ;
  94. static atomic_t rsv_publ_ok = ATOMIC_INIT(0);
  95. DEFINE_RWLOCK(tipc_nametbl_lock);
  96. static int hash(int x)
  97. {
  98. return(x & (tipc_nametbl_size - 1));
  99. }
  100. /**
  101. * publ_create - create a publication structure
  102. */
  103. static struct publication *publ_create(u32 type, u32 lower, u32 upper,
  104. u32 scope, u32 node, u32 port_ref,
  105. u32 key)
  106. {
  107. struct publication *publ = kzalloc(sizeof(*publ), GFP_ATOMIC);
  108. if (publ == NULL) {
  109. warn("Publication creation failure, no memory\n");
  110. return NULL;
  111. }
  112. publ->type = type;
  113. publ->lower = lower;
  114. publ->upper = upper;
  115. publ->scope = scope;
  116. publ->node = node;
  117. publ->ref = port_ref;
  118. publ->key = key;
  119. INIT_LIST_HEAD(&publ->local_list);
  120. INIT_LIST_HEAD(&publ->pport_list);
  121. INIT_LIST_HEAD(&publ->subscr.nodesub_list);
  122. return publ;
  123. }
  124. /**
  125. * tipc_subseq_alloc - allocate a specified number of sub-sequence structures
  126. */
  127. static struct sub_seq *tipc_subseq_alloc(u32 cnt)
  128. {
  129. struct sub_seq *sseq = kcalloc(cnt, sizeof(struct sub_seq), GFP_ATOMIC);
  130. return sseq;
  131. }
  132. /**
  133. * tipc_nameseq_create - create a name sequence structure for the specified 'type'
  134. *
  135. * Allocates a single sub-sequence structure and sets it to all 0's.
  136. */
  137. static struct name_seq *tipc_nameseq_create(u32 type, struct hlist_head *seq_head)
  138. {
  139. struct name_seq *nseq = kzalloc(sizeof(*nseq), GFP_ATOMIC);
  140. struct sub_seq *sseq = tipc_subseq_alloc(1);
  141. if (!nseq || !sseq) {
  142. warn("Name sequence creation failed, no memory\n");
  143. kfree(nseq);
  144. kfree(sseq);
  145. return NULL;
  146. }
  147. spin_lock_init(&nseq->lock);
  148. nseq->type = type;
  149. nseq->sseqs = sseq;
  150. dbg("tipc_nameseq_create(): nseq = %p, type %u, ssseqs %p, ff: %u\n",
  151. nseq, type, nseq->sseqs, nseq->first_free);
  152. nseq->alloc = 1;
  153. INIT_HLIST_NODE(&nseq->ns_list);
  154. INIT_LIST_HEAD(&nseq->subscriptions);
  155. hlist_add_head(&nseq->ns_list, seq_head);
  156. return nseq;
  157. }
  158. /**
  159. * nameseq_find_subseq - find sub-sequence (if any) matching a name instance
  160. *
  161. * Very time-critical, so binary searches through sub-sequence array.
  162. */
  163. static struct sub_seq *nameseq_find_subseq(struct name_seq *nseq,
  164. u32 instance)
  165. {
  166. struct sub_seq *sseqs = nseq->sseqs;
  167. int low = 0;
  168. int high = nseq->first_free - 1;
  169. int mid;
  170. while (low <= high) {
  171. mid = (low + high) / 2;
  172. if (instance < sseqs[mid].lower)
  173. high = mid - 1;
  174. else if (instance > sseqs[mid].upper)
  175. low = mid + 1;
  176. else
  177. return &sseqs[mid];
  178. }
  179. return NULL;
  180. }
  181. /**
  182. * nameseq_locate_subseq - determine position of name instance in sub-sequence
  183. *
  184. * Returns index in sub-sequence array of the entry that contains the specified
  185. * instance value; if no entry contains that value, returns the position
  186. * where a new entry for it would be inserted in the array.
  187. *
  188. * Note: Similar to binary search code for locating a sub-sequence.
  189. */
  190. static u32 nameseq_locate_subseq(struct name_seq *nseq, u32 instance)
  191. {
  192. struct sub_seq *sseqs = nseq->sseqs;
  193. int low = 0;
  194. int high = nseq->first_free - 1;
  195. int mid;
  196. while (low <= high) {
  197. mid = (low + high) / 2;
  198. if (instance < sseqs[mid].lower)
  199. high = mid - 1;
  200. else if (instance > sseqs[mid].upper)
  201. low = mid + 1;
  202. else
  203. return mid;
  204. }
  205. return low;
  206. }
  207. /**
  208. * tipc_nameseq_insert_publ -
  209. */
  210. static struct publication *tipc_nameseq_insert_publ(struct name_seq *nseq,
  211. u32 type, u32 lower, u32 upper,
  212. u32 scope, u32 node, u32 port, u32 key)
  213. {
  214. struct subscription *s;
  215. struct subscription *st;
  216. struct publication *publ;
  217. struct sub_seq *sseq;
  218. int created_subseq = 0;
  219. sseq = nameseq_find_subseq(nseq, lower);
  220. dbg("nameseq_ins: for seq %p, {%u,%u}, found sseq %p\n",
  221. nseq, type, lower, sseq);
  222. if (sseq) {
  223. /* Lower end overlaps existing entry => need an exact match */
  224. if ((sseq->lower != lower) || (sseq->upper != upper)) {
  225. warn("Cannot publish {%u,%u,%u}, overlap error\n",
  226. type, lower, upper);
  227. return NULL;
  228. }
  229. } else {
  230. u32 inspos;
  231. struct sub_seq *freesseq;
  232. /* Find where lower end should be inserted */
  233. inspos = nameseq_locate_subseq(nseq, lower);
  234. /* Fail if upper end overlaps into an existing entry */
  235. if ((inspos < nseq->first_free) &&
  236. (upper >= nseq->sseqs[inspos].lower)) {
  237. warn("Cannot publish {%u,%u,%u}, overlap error\n",
  238. type, lower, upper);
  239. return NULL;
  240. }
  241. /* Ensure there is space for new sub-sequence */
  242. if (nseq->first_free == nseq->alloc) {
  243. struct sub_seq *sseqs = tipc_subseq_alloc(nseq->alloc * 2);
  244. if (!sseqs) {
  245. warn("Cannot publish {%u,%u,%u}, no memory\n",
  246. type, lower, upper);
  247. return NULL;
  248. }
  249. dbg("Allocated %u more sseqs\n", nseq->alloc);
  250. memcpy(sseqs, nseq->sseqs,
  251. nseq->alloc * sizeof(struct sub_seq));
  252. kfree(nseq->sseqs);
  253. nseq->sseqs = sseqs;
  254. nseq->alloc *= 2;
  255. }
  256. dbg("Have %u sseqs for type %u\n", nseq->alloc, type);
  257. /* Insert new sub-sequence */
  258. dbg("ins in pos %u, ff = %u\n", inspos, nseq->first_free);
  259. sseq = &nseq->sseqs[inspos];
  260. freesseq = &nseq->sseqs[nseq->first_free];
  261. memmove(sseq + 1, sseq, (freesseq - sseq) * sizeof (*sseq));
  262. memset(sseq, 0, sizeof (*sseq));
  263. nseq->first_free++;
  264. sseq->lower = lower;
  265. sseq->upper = upper;
  266. created_subseq = 1;
  267. }
  268. dbg("inserting {%u,%u,%u} from <0x%x:%u> into sseq %p(%u,%u) of seq %p\n",
  269. type, lower, upper, node, port, sseq,
  270. sseq->lower, sseq->upper, nseq);
  271. /* Insert a publication: */
  272. publ = publ_create(type, lower, upper, scope, node, port, key);
  273. if (!publ)
  274. return NULL;
  275. dbg("inserting publ %p, node=0x%x publ->node=0x%x, subscr->node=%p\n",
  276. publ, node, publ->node, publ->subscr.node);
  277. if (!sseq->zone_list)
  278. sseq->zone_list = publ->zone_list_next = publ;
  279. else {
  280. publ->zone_list_next = sseq->zone_list->zone_list_next;
  281. sseq->zone_list->zone_list_next = publ;
  282. }
  283. if (in_own_cluster(node)) {
  284. if (!sseq->cluster_list)
  285. sseq->cluster_list = publ->cluster_list_next = publ;
  286. else {
  287. publ->cluster_list_next =
  288. sseq->cluster_list->cluster_list_next;
  289. sseq->cluster_list->cluster_list_next = publ;
  290. }
  291. }
  292. if (node == tipc_own_addr) {
  293. if (!sseq->node_list)
  294. sseq->node_list = publ->node_list_next = publ;
  295. else {
  296. publ->node_list_next = sseq->node_list->node_list_next;
  297. sseq->node_list->node_list_next = publ;
  298. }
  299. }
  300. /*
  301. * Any subscriptions waiting for notification?
  302. */
  303. list_for_each_entry_safe(s, st, &nseq->subscriptions, nameseq_list) {
  304. dbg("calling report_overlap()\n");
  305. tipc_subscr_report_overlap(s,
  306. publ->lower,
  307. publ->upper,
  308. TIPC_PUBLISHED,
  309. publ->ref,
  310. publ->node,
  311. created_subseq);
  312. }
  313. return publ;
  314. }
  315. /**
  316. * tipc_nameseq_remove_publ -
  317. *
  318. * NOTE: There may be cases where TIPC is asked to remove a publication
  319. * that is not in the name table. For example, if another node issues a
  320. * publication for a name sequence that overlaps an existing name sequence
  321. * the publication will not be recorded, which means the publication won't
  322. * be found when the name sequence is later withdrawn by that node.
  323. * A failed withdraw request simply returns a failure indication and lets the
  324. * caller issue any error or warning messages associated with such a problem.
  325. */
  326. static struct publication *tipc_nameseq_remove_publ(struct name_seq *nseq, u32 inst,
  327. u32 node, u32 ref, u32 key)
  328. {
  329. struct publication *publ;
  330. struct publication *curr;
  331. struct publication *prev;
  332. struct sub_seq *sseq = nameseq_find_subseq(nseq, inst);
  333. struct sub_seq *free;
  334. struct subscription *s, *st;
  335. int removed_subseq = 0;
  336. if (!sseq)
  337. return NULL;
  338. dbg("tipc_nameseq_remove_publ: seq: %p, sseq %p, {%u,%u}, key %u\n",
  339. nseq, sseq, nseq->type, inst, key);
  340. /* Remove publication from zone scope list */
  341. prev = sseq->zone_list;
  342. publ = sseq->zone_list->zone_list_next;
  343. while ((publ->key != key) || (publ->ref != ref) ||
  344. (publ->node && (publ->node != node))) {
  345. prev = publ;
  346. publ = publ->zone_list_next;
  347. if (prev == sseq->zone_list) {
  348. /* Prevent endless loop if publication not found */
  349. return NULL;
  350. }
  351. }
  352. if (publ != sseq->zone_list)
  353. prev->zone_list_next = publ->zone_list_next;
  354. else if (publ->zone_list_next != publ) {
  355. prev->zone_list_next = publ->zone_list_next;
  356. sseq->zone_list = publ->zone_list_next;
  357. } else {
  358. sseq->zone_list = NULL;
  359. }
  360. /* Remove publication from cluster scope list, if present */
  361. if (in_own_cluster(node)) {
  362. prev = sseq->cluster_list;
  363. curr = sseq->cluster_list->cluster_list_next;
  364. while (curr != publ) {
  365. prev = curr;
  366. curr = curr->cluster_list_next;
  367. if (prev == sseq->cluster_list) {
  368. /* Prevent endless loop for malformed list */
  369. err("Unable to de-list cluster publication\n"
  370. "{%u%u}, node=0x%x, ref=%u, key=%u)\n",
  371. publ->type, publ->lower, publ->node,
  372. publ->ref, publ->key);
  373. goto end_cluster;
  374. }
  375. }
  376. if (publ != sseq->cluster_list)
  377. prev->cluster_list_next = publ->cluster_list_next;
  378. else if (publ->cluster_list_next != publ) {
  379. prev->cluster_list_next = publ->cluster_list_next;
  380. sseq->cluster_list = publ->cluster_list_next;
  381. } else {
  382. sseq->cluster_list = NULL;
  383. }
  384. }
  385. end_cluster:
  386. /* Remove publication from node scope list, if present */
  387. if (node == tipc_own_addr) {
  388. prev = sseq->node_list;
  389. curr = sseq->node_list->node_list_next;
  390. while (curr != publ) {
  391. prev = curr;
  392. curr = curr->node_list_next;
  393. if (prev == sseq->node_list) {
  394. /* Prevent endless loop for malformed list */
  395. err("Unable to de-list node publication\n"
  396. "{%u%u}, node=0x%x, ref=%u, key=%u)\n",
  397. publ->type, publ->lower, publ->node,
  398. publ->ref, publ->key);
  399. goto end_node;
  400. }
  401. }
  402. if (publ != sseq->node_list)
  403. prev->node_list_next = publ->node_list_next;
  404. else if (publ->node_list_next != publ) {
  405. prev->node_list_next = publ->node_list_next;
  406. sseq->node_list = publ->node_list_next;
  407. } else {
  408. sseq->node_list = NULL;
  409. }
  410. }
  411. end_node:
  412. /* Contract subseq list if no more publications for that subseq */
  413. if (!sseq->zone_list) {
  414. free = &nseq->sseqs[nseq->first_free--];
  415. memmove(sseq, sseq + 1, (free - (sseq + 1)) * sizeof (*sseq));
  416. removed_subseq = 1;
  417. }
  418. /* Notify any waiting subscriptions */
  419. list_for_each_entry_safe(s, st, &nseq->subscriptions, nameseq_list) {
  420. tipc_subscr_report_overlap(s,
  421. publ->lower,
  422. publ->upper,
  423. TIPC_WITHDRAWN,
  424. publ->ref,
  425. publ->node,
  426. removed_subseq);
  427. }
  428. return publ;
  429. }
  430. /**
  431. * tipc_nameseq_subscribe: attach a subscription, and issue
  432. * the prescribed number of events if there is any sub-
  433. * sequence overlapping with the requested sequence
  434. */
  435. void tipc_nameseq_subscribe(struct name_seq *nseq, struct subscription *s)
  436. {
  437. struct sub_seq *sseq = nseq->sseqs;
  438. list_add(&s->nameseq_list, &nseq->subscriptions);
  439. if (!sseq)
  440. return;
  441. while (sseq != &nseq->sseqs[nseq->first_free]) {
  442. struct publication *zl = sseq->zone_list;
  443. if (zl && tipc_subscr_overlap(s,sseq->lower,sseq->upper)) {
  444. struct publication *crs = zl;
  445. int must_report = 1;
  446. do {
  447. tipc_subscr_report_overlap(s,
  448. sseq->lower,
  449. sseq->upper,
  450. TIPC_PUBLISHED,
  451. crs->ref,
  452. crs->node,
  453. must_report);
  454. must_report = 0;
  455. crs = crs->zone_list_next;
  456. } while (crs != zl);
  457. }
  458. sseq++;
  459. }
  460. }
  461. static struct name_seq *nametbl_find_seq(u32 type)
  462. {
  463. struct hlist_head *seq_head;
  464. struct hlist_node *seq_node;
  465. struct name_seq *ns;
  466. dbg("find_seq %u,(%u,0x%x) table = %p, hash[type] = %u\n",
  467. type, ntohl(type), type, table.types, hash(type));
  468. seq_head = &table.types[hash(type)];
  469. hlist_for_each_entry(ns, seq_node, seq_head, ns_list) {
  470. if (ns->type == type) {
  471. dbg("found %p\n", ns);
  472. return ns;
  473. }
  474. }
  475. return NULL;
  476. };
  477. struct publication *tipc_nametbl_insert_publ(u32 type, u32 lower, u32 upper,
  478. u32 scope, u32 node, u32 port, u32 key)
  479. {
  480. struct name_seq *seq = nametbl_find_seq(type);
  481. dbg("tipc_nametbl_insert_publ: {%u,%u,%u} found %p\n", type, lower, upper, seq);
  482. if (lower > upper) {
  483. warn("Failed to publish illegal {%u,%u,%u}\n",
  484. type, lower, upper);
  485. return NULL;
  486. }
  487. dbg("Publishing {%u,%u,%u} from 0x%x\n", type, lower, upper, node);
  488. if (!seq) {
  489. seq = tipc_nameseq_create(type, &table.types[hash(type)]);
  490. dbg("tipc_nametbl_insert_publ: created %p\n", seq);
  491. }
  492. if (!seq)
  493. return NULL;
  494. return tipc_nameseq_insert_publ(seq, type, lower, upper,
  495. scope, node, port, key);
  496. }
  497. struct publication *tipc_nametbl_remove_publ(u32 type, u32 lower,
  498. u32 node, u32 ref, u32 key)
  499. {
  500. struct publication *publ;
  501. struct name_seq *seq = nametbl_find_seq(type);
  502. if (!seq)
  503. return NULL;
  504. dbg("Withdrawing {%u,%u} from 0x%x\n", type, lower, node);
  505. publ = tipc_nameseq_remove_publ(seq, lower, node, ref, key);
  506. if (!seq->first_free && list_empty(&seq->subscriptions)) {
  507. hlist_del_init(&seq->ns_list);
  508. kfree(seq->sseqs);
  509. kfree(seq);
  510. }
  511. return publ;
  512. }
  513. /*
  514. * tipc_nametbl_translate(): Translate tipc_name -> tipc_portid.
  515. * Very time-critical.
  516. *
  517. * Note: on entry 'destnode' is the search domain used during translation;
  518. * on exit it passes back the node address of the matching port (if any)
  519. */
  520. u32 tipc_nametbl_translate(u32 type, u32 instance, u32 *destnode)
  521. {
  522. struct sub_seq *sseq;
  523. struct publication *publ = NULL;
  524. struct name_seq *seq;
  525. u32 ref;
  526. if (!in_scope(*destnode, tipc_own_addr))
  527. return 0;
  528. read_lock_bh(&tipc_nametbl_lock);
  529. seq = nametbl_find_seq(type);
  530. if (unlikely(!seq))
  531. goto not_found;
  532. sseq = nameseq_find_subseq(seq, instance);
  533. if (unlikely(!sseq))
  534. goto not_found;
  535. spin_lock_bh(&seq->lock);
  536. /* Closest-First Algorithm: */
  537. if (likely(!*destnode)) {
  538. publ = sseq->node_list;
  539. if (publ) {
  540. sseq->node_list = publ->node_list_next;
  541. found:
  542. ref = publ->ref;
  543. *destnode = publ->node;
  544. spin_unlock_bh(&seq->lock);
  545. read_unlock_bh(&tipc_nametbl_lock);
  546. return ref;
  547. }
  548. publ = sseq->cluster_list;
  549. if (publ) {
  550. sseq->cluster_list = publ->cluster_list_next;
  551. goto found;
  552. }
  553. publ = sseq->zone_list;
  554. if (publ) {
  555. sseq->zone_list = publ->zone_list_next;
  556. goto found;
  557. }
  558. }
  559. /* Round-Robin Algorithm: */
  560. else if (*destnode == tipc_own_addr) {
  561. publ = sseq->node_list;
  562. if (publ) {
  563. sseq->node_list = publ->node_list_next;
  564. goto found;
  565. }
  566. } else if (in_own_cluster(*destnode)) {
  567. publ = sseq->cluster_list;
  568. if (publ) {
  569. sseq->cluster_list = publ->cluster_list_next;
  570. goto found;
  571. }
  572. } else {
  573. publ = sseq->zone_list;
  574. if (publ) {
  575. sseq->zone_list = publ->zone_list_next;
  576. goto found;
  577. }
  578. }
  579. spin_unlock_bh(&seq->lock);
  580. not_found:
  581. *destnode = 0;
  582. read_unlock_bh(&tipc_nametbl_lock);
  583. return 0;
  584. }
  585. /**
  586. * tipc_nametbl_mc_translate - find multicast destinations
  587. *
  588. * Creates list of all local ports that overlap the given multicast address;
  589. * also determines if any off-node ports overlap.
  590. *
  591. * Note: Publications with a scope narrower than 'limit' are ignored.
  592. * (i.e. local node-scope publications mustn't receive messages arriving
  593. * from another node, even if the multcast link brought it here)
  594. *
  595. * Returns non-zero if any off-node ports overlap
  596. */
  597. int tipc_nametbl_mc_translate(u32 type, u32 lower, u32 upper, u32 limit,
  598. struct port_list *dports)
  599. {
  600. struct name_seq *seq;
  601. struct sub_seq *sseq;
  602. struct sub_seq *sseq_stop;
  603. int res = 0;
  604. read_lock_bh(&tipc_nametbl_lock);
  605. seq = nametbl_find_seq(type);
  606. if (!seq)
  607. goto exit;
  608. spin_lock_bh(&seq->lock);
  609. sseq = seq->sseqs + nameseq_locate_subseq(seq, lower);
  610. sseq_stop = seq->sseqs + seq->first_free;
  611. for (; sseq != sseq_stop; sseq++) {
  612. struct publication *publ;
  613. if (sseq->lower > upper)
  614. break;
  615. publ = sseq->cluster_list;
  616. if (publ && (publ->scope <= limit))
  617. do {
  618. if (publ->node == tipc_own_addr)
  619. tipc_port_list_add(dports, publ->ref);
  620. else
  621. res = 1;
  622. publ = publ->cluster_list_next;
  623. } while (publ != sseq->cluster_list);
  624. }
  625. spin_unlock_bh(&seq->lock);
  626. exit:
  627. read_unlock_bh(&tipc_nametbl_lock);
  628. return res;
  629. }
  630. /**
  631. * tipc_nametbl_publish_rsv - publish port name using a reserved name type
  632. */
  633. int tipc_nametbl_publish_rsv(u32 ref, unsigned int scope,
  634. struct tipc_name_seq const *seq)
  635. {
  636. int res;
  637. atomic_inc(&rsv_publ_ok);
  638. res = tipc_publish(ref, scope, seq);
  639. atomic_dec(&rsv_publ_ok);
  640. return res;
  641. }
  642. /**
  643. * tipc_nametbl_publish - add name publication to network name tables
  644. */
  645. struct publication *tipc_nametbl_publish(u32 type, u32 lower, u32 upper,
  646. u32 scope, u32 port_ref, u32 key)
  647. {
  648. struct publication *publ;
  649. if (table.local_publ_count >= tipc_max_publications) {
  650. warn("Publication failed, local publication limit reached (%u)\n",
  651. tipc_max_publications);
  652. return NULL;
  653. }
  654. if ((type < TIPC_RESERVED_TYPES) && !atomic_read(&rsv_publ_ok)) {
  655. warn("Publication failed, reserved name {%u,%u,%u}\n",
  656. type, lower, upper);
  657. return NULL;
  658. }
  659. write_lock_bh(&tipc_nametbl_lock);
  660. table.local_publ_count++;
  661. publ = tipc_nametbl_insert_publ(type, lower, upper, scope,
  662. tipc_own_addr, port_ref, key);
  663. if (publ && (scope != TIPC_NODE_SCOPE)) {
  664. tipc_named_publish(publ);
  665. }
  666. write_unlock_bh(&tipc_nametbl_lock);
  667. return publ;
  668. }
  669. /**
  670. * tipc_nametbl_withdraw - withdraw name publication from network name tables
  671. */
  672. int tipc_nametbl_withdraw(u32 type, u32 lower, u32 ref, u32 key)
  673. {
  674. struct publication *publ;
  675. dbg("tipc_nametbl_withdraw: {%u,%u}, key=%u\n", type, lower, key);
  676. write_lock_bh(&tipc_nametbl_lock);
  677. publ = tipc_nametbl_remove_publ(type, lower, tipc_own_addr, ref, key);
  678. if (likely(publ)) {
  679. table.local_publ_count--;
  680. if (publ->scope != TIPC_NODE_SCOPE)
  681. tipc_named_withdraw(publ);
  682. write_unlock_bh(&tipc_nametbl_lock);
  683. list_del_init(&publ->pport_list);
  684. kfree(publ);
  685. return 1;
  686. }
  687. write_unlock_bh(&tipc_nametbl_lock);
  688. err("Unable to remove local publication\n"
  689. "(type=%u, lower=%u, ref=%u, key=%u)\n",
  690. type, lower, ref, key);
  691. return 0;
  692. }
  693. /**
  694. * tipc_nametbl_subscribe - add a subscription object to the name table
  695. */
  696. void tipc_nametbl_subscribe(struct subscription *s)
  697. {
  698. u32 type = s->seq.type;
  699. struct name_seq *seq;
  700. write_lock_bh(&tipc_nametbl_lock);
  701. seq = nametbl_find_seq(type);
  702. if (!seq) {
  703. seq = tipc_nameseq_create(type, &table.types[hash(type)]);
  704. }
  705. if (seq){
  706. spin_lock_bh(&seq->lock);
  707. dbg("tipc_nametbl_subscribe:found %p for {%u,%u,%u}\n",
  708. seq, type, s->seq.lower, s->seq.upper);
  709. tipc_nameseq_subscribe(seq, s);
  710. spin_unlock_bh(&seq->lock);
  711. } else {
  712. warn("Failed to create subscription for {%u,%u,%u}\n",
  713. s->seq.type, s->seq.lower, s->seq.upper);
  714. }
  715. write_unlock_bh(&tipc_nametbl_lock);
  716. }
  717. /**
  718. * tipc_nametbl_unsubscribe - remove a subscription object from name table
  719. */
  720. void tipc_nametbl_unsubscribe(struct subscription *s)
  721. {
  722. struct name_seq *seq;
  723. write_lock_bh(&tipc_nametbl_lock);
  724. seq = nametbl_find_seq(s->seq.type);
  725. if (seq != NULL){
  726. spin_lock_bh(&seq->lock);
  727. list_del_init(&s->nameseq_list);
  728. spin_unlock_bh(&seq->lock);
  729. if ((seq->first_free == 0) && list_empty(&seq->subscriptions)) {
  730. hlist_del_init(&seq->ns_list);
  731. kfree(seq->sseqs);
  732. kfree(seq);
  733. }
  734. }
  735. write_unlock_bh(&tipc_nametbl_lock);
  736. }
  737. /**
  738. * subseq_list: print specified sub-sequence contents into the given buffer
  739. */
  740. static void subseq_list(struct sub_seq *sseq, struct print_buf *buf, u32 depth,
  741. u32 index)
  742. {
  743. char portIdStr[27];
  744. char *scopeStr;
  745. struct publication *publ = sseq->zone_list;
  746. tipc_printf(buf, "%-10u %-10u ", sseq->lower, sseq->upper);
  747. if (depth == 2 || !publ) {
  748. tipc_printf(buf, "\n");
  749. return;
  750. }
  751. do {
  752. sprintf (portIdStr, "<%u.%u.%u:%u>",
  753. tipc_zone(publ->node), tipc_cluster(publ->node),
  754. tipc_node(publ->node), publ->ref);
  755. tipc_printf(buf, "%-26s ", portIdStr);
  756. if (depth > 3) {
  757. if (publ->node != tipc_own_addr)
  758. scopeStr = "";
  759. else if (publ->scope == TIPC_NODE_SCOPE)
  760. scopeStr = "node";
  761. else if (publ->scope == TIPC_CLUSTER_SCOPE)
  762. scopeStr = "cluster";
  763. else
  764. scopeStr = "zone";
  765. tipc_printf(buf, "%-10u %s", publ->key, scopeStr);
  766. }
  767. publ = publ->zone_list_next;
  768. if (publ == sseq->zone_list)
  769. break;
  770. tipc_printf(buf, "\n%33s", " ");
  771. } while (1);
  772. tipc_printf(buf, "\n");
  773. }
  774. /**
  775. * nameseq_list: print specified name sequence contents into the given buffer
  776. */
  777. static void nameseq_list(struct name_seq *seq, struct print_buf *buf, u32 depth,
  778. u32 type, u32 lowbound, u32 upbound, u32 index)
  779. {
  780. struct sub_seq *sseq;
  781. char typearea[11];
  782. sprintf(typearea, "%-10u", seq->type);
  783. if (depth == 1) {
  784. tipc_printf(buf, "%s\n", typearea);
  785. return;
  786. }
  787. for (sseq = seq->sseqs; sseq != &seq->sseqs[seq->first_free]; sseq++) {
  788. if ((lowbound <= sseq->upper) && (upbound >= sseq->lower)) {
  789. tipc_printf(buf, "%s ", typearea);
  790. subseq_list(sseq, buf, depth, index);
  791. sprintf(typearea, "%10s", " ");
  792. }
  793. }
  794. }
  795. /**
  796. * nametbl_header - print name table header into the given buffer
  797. */
  798. static void nametbl_header(struct print_buf *buf, u32 depth)
  799. {
  800. tipc_printf(buf, "Type ");
  801. if (depth > 1)
  802. tipc_printf(buf, "Lower Upper ");
  803. if (depth > 2)
  804. tipc_printf(buf, "Port Identity ");
  805. if (depth > 3)
  806. tipc_printf(buf, "Publication");
  807. tipc_printf(buf, "\n-----------");
  808. if (depth > 1)
  809. tipc_printf(buf, "--------------------- ");
  810. if (depth > 2)
  811. tipc_printf(buf, "-------------------------- ");
  812. if (depth > 3)
  813. tipc_printf(buf, "------------------");
  814. tipc_printf(buf, "\n");
  815. }
  816. /**
  817. * nametbl_list - print specified name table contents into the given buffer
  818. */
  819. static void nametbl_list(struct print_buf *buf, u32 depth_info,
  820. u32 type, u32 lowbound, u32 upbound)
  821. {
  822. struct hlist_head *seq_head;
  823. struct hlist_node *seq_node;
  824. struct name_seq *seq;
  825. int all_types;
  826. u32 depth;
  827. u32 i;
  828. all_types = (depth_info & TIPC_NTQ_ALLTYPES);
  829. depth = (depth_info & ~TIPC_NTQ_ALLTYPES);
  830. if (depth == 0)
  831. return;
  832. if (all_types) {
  833. /* display all entries in name table to specified depth */
  834. nametbl_header(buf, depth);
  835. lowbound = 0;
  836. upbound = ~0;
  837. for (i = 0; i < tipc_nametbl_size; i++) {
  838. seq_head = &table.types[i];
  839. hlist_for_each_entry(seq, seq_node, seq_head, ns_list) {
  840. nameseq_list(seq, buf, depth, seq->type,
  841. lowbound, upbound, i);
  842. }
  843. }
  844. } else {
  845. /* display only the sequence that matches the specified type */
  846. if (upbound < lowbound) {
  847. tipc_printf(buf, "invalid name sequence specified\n");
  848. return;
  849. }
  850. nametbl_header(buf, depth);
  851. i = hash(type);
  852. seq_head = &table.types[i];
  853. hlist_for_each_entry(seq, seq_node, seq_head, ns_list) {
  854. if (seq->type == type) {
  855. nameseq_list(seq, buf, depth, type,
  856. lowbound, upbound, i);
  857. break;
  858. }
  859. }
  860. }
  861. }
  862. #if 0
  863. void tipc_nametbl_print(struct print_buf *buf, const char *str)
  864. {
  865. tipc_printf(buf, str);
  866. read_lock_bh(&tipc_nametbl_lock);
  867. nametbl_list(buf, 0, 0, 0, 0);
  868. read_unlock_bh(&tipc_nametbl_lock);
  869. }
  870. #endif
  871. #define MAX_NAME_TBL_QUERY 32768
  872. struct sk_buff *tipc_nametbl_get(const void *req_tlv_area, int req_tlv_space)
  873. {
  874. struct sk_buff *buf;
  875. struct tipc_name_table_query *argv;
  876. struct tlv_desc *rep_tlv;
  877. struct print_buf b;
  878. int str_len;
  879. if (!TLV_CHECK(req_tlv_area, req_tlv_space, TIPC_TLV_NAME_TBL_QUERY))
  880. return tipc_cfg_reply_error_string(TIPC_CFG_TLV_ERROR);
  881. buf = tipc_cfg_reply_alloc(TLV_SPACE(MAX_NAME_TBL_QUERY));
  882. if (!buf)
  883. return NULL;
  884. rep_tlv = (struct tlv_desc *)buf->data;
  885. tipc_printbuf_init(&b, TLV_DATA(rep_tlv), MAX_NAME_TBL_QUERY);
  886. argv = (struct tipc_name_table_query *)TLV_DATA(req_tlv_area);
  887. read_lock_bh(&tipc_nametbl_lock);
  888. nametbl_list(&b, ntohl(argv->depth), ntohl(argv->type),
  889. ntohl(argv->lowbound), ntohl(argv->upbound));
  890. read_unlock_bh(&tipc_nametbl_lock);
  891. str_len = tipc_printbuf_validate(&b);
  892. skb_put(buf, TLV_SPACE(str_len));
  893. TLV_SET(rep_tlv, TIPC_TLV_ULTRA_STRING, NULL, str_len);
  894. return buf;
  895. }
  896. #if 0
  897. void tipc_nametbl_dump(void)
  898. {
  899. nametbl_list(TIPC_CONS, 0, 0, 0, 0);
  900. }
  901. #endif
  902. int tipc_nametbl_init(void)
  903. {
  904. int array_size = sizeof(struct hlist_head) * tipc_nametbl_size;
  905. table.types = kmalloc(array_size, GFP_ATOMIC);
  906. if (!table.types)
  907. return -ENOMEM;
  908. write_lock_bh(&tipc_nametbl_lock);
  909. memset(table.types, 0, array_size);
  910. table.local_publ_count = 0;
  911. write_unlock_bh(&tipc_nametbl_lock);
  912. return 0;
  913. }
  914. void tipc_nametbl_stop(void)
  915. {
  916. u32 i;
  917. if (!table.types)
  918. return;
  919. /* Verify name table is empty, then release it */
  920. write_lock_bh(&tipc_nametbl_lock);
  921. for (i = 0; i < tipc_nametbl_size; i++) {
  922. if (!hlist_empty(&table.types[i]))
  923. err("tipc_nametbl_stop(): hash chain %u is non-null\n", i);
  924. }
  925. kfree(table.types);
  926. table.types = NULL;
  927. write_unlock_bh(&tipc_nametbl_lock);
  928. }