name_table.c 27 KB

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