diff options
author | Allan Stephens <allan.stephens@windriver.com> | 2011-05-30 10:48:48 -0400 |
---|---|---|
committer | Paul Gortmaker <paul.gortmaker@windriver.com> | 2011-06-24 16:18:16 -0400 |
commit | f6f0a4d2d05f758f011a506731e84160d140304b (patch) | |
tree | 48f3853dbf7b35d1bd3f85ab61a0c841180e05b6 /net/tipc | |
parent | b52124a50fa7b870a3d1a18a8ff56273c7d690dd (diff) |
tipc: Convert name table publication lists to standard kernel lists
Modifies the main circular linked lists of publications used in TIPC's
name table to use the standard kernel linked list type. This change
simplifies the deletion of an existing publication by eliminating
the need to search up to three lists to locate the publication.
The use of standard list routines also helps improve the readability
of the name table code by make it clearer what each list operation
being performed is actually doing.
Signed-off-by: Allan Stephens <allan.stephens@windriver.com>
Signed-off-by: Paul Gortmaker <paul.gortmaker@windriver.com>
Diffstat (limited to 'net/tipc')
-rw-r--r-- | net/tipc/name_table.c | 240 | ||||
-rw-r--r-- | net/tipc/name_table.h | 14 |
2 files changed, 90 insertions, 164 deletions
diff --git a/net/tipc/name_table.c b/net/tipc/name_table.c index 9cd58f8318f1..7d85cc1ace0e 100644 --- a/net/tipc/name_table.c +++ b/net/tipc/name_table.c | |||
@@ -2,7 +2,7 @@ | |||
2 | * net/tipc/name_table.c: TIPC name table code | 2 | * net/tipc/name_table.c: TIPC name table code |
3 | * | 3 | * |
4 | * Copyright (c) 2000-2006, Ericsson AB | 4 | * Copyright (c) 2000-2006, Ericsson AB |
5 | * Copyright (c) 2004-2008, Wind River Systems | 5 | * Copyright (c) 2004-2008, 2010-2011, Wind River Systems |
6 | * All rights reserved. | 6 | * All rights reserved. |
7 | * | 7 | * |
8 | * Redistribution and use in source and binary forms, with or without | 8 | * Redistribution and use in source and binary forms, with or without |
@@ -58,9 +58,9 @@ static int tipc_nametbl_size = 1024; /* must be a power of 2 */ | |||
58 | */ | 58 | */ |
59 | 59 | ||
60 | struct name_info { | 60 | struct name_info { |
61 | struct publication *node_list; | 61 | struct list_head node_list; |
62 | struct publication *cluster_list; | 62 | struct list_head cluster_list; |
63 | struct publication *zone_list; | 63 | struct list_head zone_list; |
64 | u32 node_list_size; | 64 | u32 node_list_size; |
65 | u32 cluster_list_size; | 65 | u32 cluster_list_size; |
66 | u32 zone_list_size; | 66 | u32 zone_list_size; |
@@ -311,6 +311,10 @@ static struct publication *tipc_nameseq_insert_publ(struct name_seq *nseq, | |||
311 | return NULL; | 311 | return NULL; |
312 | } | 312 | } |
313 | 313 | ||
314 | INIT_LIST_HEAD(&info->node_list); | ||
315 | INIT_LIST_HEAD(&info->cluster_list); | ||
316 | INIT_LIST_HEAD(&info->zone_list); | ||
317 | |||
314 | /* Insert new sub-sequence */ | 318 | /* Insert new sub-sequence */ |
315 | 319 | ||
316 | sseq = &nseq->sseqs[inspos]; | 320 | sseq = &nseq->sseqs[inspos]; |
@@ -330,33 +334,17 @@ static struct publication *tipc_nameseq_insert_publ(struct name_seq *nseq, | |||
330 | if (!publ) | 334 | if (!publ) |
331 | return NULL; | 335 | return NULL; |
332 | 336 | ||
337 | list_add(&publ->zone_list, &info->zone_list); | ||
333 | info->zone_list_size++; | 338 | info->zone_list_size++; |
334 | if (!info->zone_list) | ||
335 | info->zone_list = publ->zone_list_next = publ; | ||
336 | else { | ||
337 | publ->zone_list_next = info->zone_list->zone_list_next; | ||
338 | info->zone_list->zone_list_next = publ; | ||
339 | } | ||
340 | 339 | ||
341 | if (in_own_cluster(node)) { | 340 | if (in_own_cluster(node)) { |
341 | list_add(&publ->cluster_list, &info->cluster_list); | ||
342 | info->cluster_list_size++; | 342 | info->cluster_list_size++; |
343 | if (!info->cluster_list) | ||
344 | info->cluster_list = publ->cluster_list_next = publ; | ||
345 | else { | ||
346 | publ->cluster_list_next = | ||
347 | info->cluster_list->cluster_list_next; | ||
348 | info->cluster_list->cluster_list_next = publ; | ||
349 | } | ||
350 | } | 343 | } |
351 | 344 | ||
352 | if (node == tipc_own_addr) { | 345 | if (node == tipc_own_addr) { |
346 | list_add(&publ->node_list, &info->node_list); | ||
353 | info->node_list_size++; | 347 | info->node_list_size++; |
354 | if (!info->node_list) | ||
355 | info->node_list = publ->node_list_next = publ; | ||
356 | else { | ||
357 | publ->node_list_next = info->node_list->node_list_next; | ||
358 | info->node_list->node_list_next = publ; | ||
359 | } | ||
360 | } | 348 | } |
361 | 349 | ||
362 | /* | 350 | /* |
@@ -390,8 +378,6 @@ static struct publication *tipc_nameseq_remove_publ(struct name_seq *nseq, u32 i | |||
390 | u32 node, u32 ref, u32 key) | 378 | u32 node, u32 ref, u32 key) |
391 | { | 379 | { |
392 | struct publication *publ; | 380 | struct publication *publ; |
393 | struct publication *curr; | ||
394 | struct publication *prev; | ||
395 | struct sub_seq *sseq = nameseq_find_subseq(nseq, inst); | 381 | struct sub_seq *sseq = nameseq_find_subseq(nseq, inst); |
396 | struct name_info *info; | 382 | struct name_info *info; |
397 | struct sub_seq *free; | 383 | struct sub_seq *free; |
@@ -403,96 +389,38 @@ static struct publication *tipc_nameseq_remove_publ(struct name_seq *nseq, u32 i | |||
403 | 389 | ||
404 | info = sseq->info; | 390 | info = sseq->info; |
405 | 391 | ||
406 | /* Remove publication from zone scope list */ | 392 | /* Locate publication, if it exists */ |
407 | 393 | ||
408 | prev = info->zone_list; | 394 | list_for_each_entry(publ, &info->zone_list, zone_list) { |
409 | publ = info->zone_list->zone_list_next; | 395 | if ((publ->key == key) && (publ->ref == ref) && |
410 | while ((publ->key != key) || (publ->ref != ref) || | 396 | (!publ->node || (publ->node == node))) |
411 | (publ->node && (publ->node != node))) { | 397 | goto found; |
412 | prev = publ; | 398 | } |
413 | publ = publ->zone_list_next; | 399 | return NULL; |
414 | if (prev == info->zone_list) { | ||
415 | 400 | ||
416 | /* Prevent endless loop if publication not found */ | 401 | found: |
402 | /* Remove publication from zone scope list */ | ||
417 | 403 | ||
418 | return NULL; | 404 | list_del(&publ->zone_list); |
419 | } | ||
420 | } | ||
421 | if (publ != info->zone_list) | ||
422 | prev->zone_list_next = publ->zone_list_next; | ||
423 | else if (publ->zone_list_next != publ) { | ||
424 | prev->zone_list_next = publ->zone_list_next; | ||
425 | info->zone_list = publ->zone_list_next; | ||
426 | } else { | ||
427 | info->zone_list = NULL; | ||
428 | } | ||
429 | info->zone_list_size--; | 405 | info->zone_list_size--; |
430 | 406 | ||
431 | /* Remove publication from cluster scope list, if present */ | 407 | /* Remove publication from cluster scope list, if present */ |
432 | 408 | ||
433 | if (in_own_cluster(node)) { | 409 | if (in_own_cluster(node)) { |
434 | prev = info->cluster_list; | 410 | list_del(&publ->cluster_list); |
435 | curr = info->cluster_list->cluster_list_next; | ||
436 | while (curr != publ) { | ||
437 | prev = curr; | ||
438 | curr = curr->cluster_list_next; | ||
439 | if (prev == info->cluster_list) { | ||
440 | |||
441 | /* Prevent endless loop for malformed list */ | ||
442 | |||
443 | err("Unable to de-list cluster publication\n" | ||
444 | "{%u%u}, node=0x%x, ref=%u, key=%u)\n", | ||
445 | publ->type, publ->lower, publ->node, | ||
446 | publ->ref, publ->key); | ||
447 | goto end_cluster; | ||
448 | } | ||
449 | } | ||
450 | if (publ != info->cluster_list) | ||
451 | prev->cluster_list_next = publ->cluster_list_next; | ||
452 | else if (publ->cluster_list_next != publ) { | ||
453 | prev->cluster_list_next = publ->cluster_list_next; | ||
454 | info->cluster_list = publ->cluster_list_next; | ||
455 | } else { | ||
456 | info->cluster_list = NULL; | ||
457 | } | ||
458 | info->cluster_list_size--; | 411 | info->cluster_list_size--; |
459 | } | 412 | } |
460 | end_cluster: | ||
461 | 413 | ||
462 | /* Remove publication from node scope list, if present */ | 414 | /* Remove publication from node scope list, if present */ |
463 | 415 | ||
464 | if (node == tipc_own_addr) { | 416 | if (node == tipc_own_addr) { |
465 | prev = info->node_list; | 417 | list_del(&publ->node_list); |
466 | curr = info->node_list->node_list_next; | ||
467 | while (curr != publ) { | ||
468 | prev = curr; | ||
469 | curr = curr->node_list_next; | ||
470 | if (prev == info->node_list) { | ||
471 | |||
472 | /* Prevent endless loop for malformed list */ | ||
473 | |||
474 | err("Unable to de-list node publication\n" | ||
475 | "{%u%u}, node=0x%x, ref=%u, key=%u)\n", | ||
476 | publ->type, publ->lower, publ->node, | ||
477 | publ->ref, publ->key); | ||
478 | goto end_node; | ||
479 | } | ||
480 | } | ||
481 | if (publ != info->node_list) | ||
482 | prev->node_list_next = publ->node_list_next; | ||
483 | else if (publ->node_list_next != publ) { | ||
484 | prev->node_list_next = publ->node_list_next; | ||
485 | info->node_list = publ->node_list_next; | ||
486 | } else { | ||
487 | info->node_list = NULL; | ||
488 | } | ||
489 | info->node_list_size--; | 418 | info->node_list_size--; |
490 | } | 419 | } |
491 | end_node: | ||
492 | 420 | ||
493 | /* Contract subseq list if no more publications for that subseq */ | 421 | /* Contract subseq list if no more publications for that subseq */ |
494 | 422 | ||
495 | if (!info->zone_list) { | 423 | if (list_empty(&info->zone_list)) { |
496 | kfree(info); | 424 | kfree(info); |
497 | free = &nseq->sseqs[nseq->first_free--]; | 425 | free = &nseq->sseqs[nseq->first_free--]; |
498 | memmove(sseq, sseq + 1, (free - (sseq + 1)) * sizeof(*sseq)); | 426 | memmove(sseq, sseq + 1, (free - (sseq + 1)) * sizeof(*sseq)); |
@@ -530,12 +458,12 @@ static void tipc_nameseq_subscribe(struct name_seq *nseq, struct subscription *s | |||
530 | return; | 458 | return; |
531 | 459 | ||
532 | while (sseq != &nseq->sseqs[nseq->first_free]) { | 460 | while (sseq != &nseq->sseqs[nseq->first_free]) { |
533 | struct publication *zl = sseq->info->zone_list; | 461 | if (tipc_subscr_overlap(s, sseq->lower, sseq->upper)) { |
534 | if (zl && tipc_subscr_overlap(s, sseq->lower, sseq->upper)) { | 462 | struct publication *crs; |
535 | struct publication *crs = zl; | 463 | struct name_info *info = sseq->info; |
536 | int must_report = 1; | 464 | int must_report = 1; |
537 | 465 | ||
538 | do { | 466 | list_for_each_entry(crs, &info->zone_list, zone_list) { |
539 | tipc_subscr_report_overlap(s, | 467 | tipc_subscr_report_overlap(s, |
540 | sseq->lower, | 468 | sseq->lower, |
541 | sseq->upper, | 469 | sseq->upper, |
@@ -544,8 +472,7 @@ static void tipc_nameseq_subscribe(struct name_seq *nseq, struct subscription *s | |||
544 | crs->node, | 472 | crs->node, |
545 | must_report); | 473 | must_report); |
546 | must_report = 0; | 474 | must_report = 0; |
547 | crs = crs->zone_list_next; | 475 | } |
548 | } while (crs != zl); | ||
549 | } | 476 | } |
550 | sseq++; | 477 | sseq++; |
551 | } | 478 | } |
@@ -616,9 +543,9 @@ u32 tipc_nametbl_translate(u32 type, u32 instance, u32 *destnode) | |||
616 | { | 543 | { |
617 | struct sub_seq *sseq; | 544 | struct sub_seq *sseq; |
618 | struct name_info *info; | 545 | struct name_info *info; |
619 | struct publication *publ = NULL; | 546 | struct publication *publ; |
620 | struct name_seq *seq; | 547 | struct name_seq *seq; |
621 | u32 ref; | 548 | u32 ref = 0; |
622 | 549 | ||
623 | if (!tipc_in_scope(*destnode, tipc_own_addr)) | 550 | if (!tipc_in_scope(*destnode, tipc_own_addr)) |
624 | return 0; | 551 | return 0; |
@@ -635,52 +562,56 @@ u32 tipc_nametbl_translate(u32 type, u32 instance, u32 *destnode) | |||
635 | 562 | ||
636 | /* Closest-First Algorithm: */ | 563 | /* Closest-First Algorithm: */ |
637 | if (likely(!*destnode)) { | 564 | if (likely(!*destnode)) { |
638 | publ = info->node_list; | 565 | if (!list_empty(&info->node_list)) { |
639 | if (publ) { | 566 | publ = list_first_entry(&info->node_list, |
640 | info->node_list = publ->node_list_next; | 567 | struct publication, |
641 | found: | 568 | node_list); |
642 | ref = publ->ref; | 569 | list_move_tail(&publ->node_list, |
643 | *destnode = publ->node; | 570 | &info->node_list); |
644 | spin_unlock_bh(&seq->lock); | 571 | } else if (!list_empty(&info->cluster_list)) { |
645 | read_unlock_bh(&tipc_nametbl_lock); | 572 | publ = list_first_entry(&info->cluster_list, |
646 | return ref; | 573 | struct publication, |
647 | } | 574 | cluster_list); |
648 | publ = info->cluster_list; | 575 | list_move_tail(&publ->cluster_list, |
649 | if (publ) { | 576 | &info->cluster_list); |
650 | info->cluster_list = publ->cluster_list_next; | 577 | } else if (!list_empty(&info->zone_list)) { |
651 | goto found; | 578 | publ = list_first_entry(&info->zone_list, |
652 | } | 579 | struct publication, |
653 | publ = info->zone_list; | 580 | zone_list); |
654 | if (publ) { | 581 | list_move_tail(&publ->zone_list, |
655 | info->zone_list = publ->zone_list_next; | 582 | &info->zone_list); |
656 | goto found; | 583 | } else |
657 | } | 584 | goto no_match; |
658 | } | 585 | } |
659 | 586 | ||
660 | /* Round-Robin Algorithm: */ | 587 | /* Round-Robin Algorithm: */ |
661 | else if (*destnode == tipc_own_addr) { | 588 | else if (*destnode == tipc_own_addr) { |
662 | publ = info->node_list; | 589 | if (list_empty(&info->node_list)) |
663 | if (publ) { | 590 | goto no_match; |
664 | info->node_list = publ->node_list_next; | 591 | publ = list_first_entry(&info->node_list, struct publication, |
665 | goto found; | 592 | node_list); |
666 | } | 593 | list_move_tail(&publ->node_list, &info->node_list); |
667 | } else if (in_own_cluster(*destnode)) { | 594 | } else if (in_own_cluster(*destnode)) { |
668 | publ = info->cluster_list; | 595 | if (list_empty(&info->cluster_list)) |
669 | if (publ) { | 596 | goto no_match; |
670 | info->cluster_list = publ->cluster_list_next; | 597 | publ = list_first_entry(&info->cluster_list, struct publication, |
671 | goto found; | 598 | cluster_list); |
672 | } | 599 | list_move_tail(&publ->cluster_list, &info->cluster_list); |
673 | } else { | 600 | } else { |
674 | publ = info->zone_list; | 601 | if (list_empty(&info->zone_list)) |
675 | if (publ) { | 602 | goto no_match; |
676 | info->zone_list = publ->zone_list_next; | 603 | publ = list_first_entry(&info->zone_list, struct publication, |
677 | goto found; | 604 | zone_list); |
678 | } | 605 | list_move_tail(&publ->zone_list, &info->zone_list); |
679 | } | 606 | } |
607 | |||
608 | ref = publ->ref; | ||
609 | *destnode = publ->node; | ||
610 | no_match: | ||
680 | spin_unlock_bh(&seq->lock); | 611 | spin_unlock_bh(&seq->lock); |
681 | not_found: | 612 | not_found: |
682 | read_unlock_bh(&tipc_nametbl_lock); | 613 | read_unlock_bh(&tipc_nametbl_lock); |
683 | return 0; | 614 | return ref; |
684 | } | 615 | } |
685 | 616 | ||
686 | /** | 617 | /** |
@@ -721,13 +652,9 @@ int tipc_nametbl_mc_translate(u32 type, u32 lower, u32 upper, u32 limit, | |||
721 | break; | 652 | break; |
722 | 653 | ||
723 | info = sseq->info; | 654 | info = sseq->info; |
724 | publ = info->node_list; | 655 | list_for_each_entry(publ, &info->node_list, node_list) { |
725 | if (publ) { | 656 | if (publ->scope <= limit) |
726 | do { | 657 | tipc_port_list_add(dports, publ->ref); |
727 | if (publ->scope <= limit) | ||
728 | tipc_port_list_add(dports, publ->ref); | ||
729 | publ = publ->node_list_next; | ||
730 | } while (publ != info->node_list); | ||
731 | } | 658 | } |
732 | 659 | ||
733 | if (info->cluster_list_size != info->node_list_size) | 660 | if (info->cluster_list_size != info->node_list_size) |
@@ -868,16 +795,19 @@ static void subseq_list(struct sub_seq *sseq, struct print_buf *buf, u32 depth, | |||
868 | { | 795 | { |
869 | char portIdStr[27]; | 796 | char portIdStr[27]; |
870 | const char *scope_str[] = {"", " zone", " cluster", " node"}; | 797 | const char *scope_str[] = {"", " zone", " cluster", " node"}; |
871 | struct publication *publ = sseq->info->zone_list; | 798 | struct publication *publ; |
799 | struct name_info *info; | ||
872 | 800 | ||
873 | tipc_printf(buf, "%-10u %-10u ", sseq->lower, sseq->upper); | 801 | tipc_printf(buf, "%-10u %-10u ", sseq->lower, sseq->upper); |
874 | 802 | ||
875 | if (depth == 2 || !publ) { | 803 | if (depth == 2) { |
876 | tipc_printf(buf, "\n"); | 804 | tipc_printf(buf, "\n"); |
877 | return; | 805 | return; |
878 | } | 806 | } |
879 | 807 | ||
880 | do { | 808 | info = sseq->info; |
809 | |||
810 | list_for_each_entry(publ, &info->zone_list, zone_list) { | ||
881 | sprintf(portIdStr, "<%u.%u.%u:%u>", | 811 | sprintf(portIdStr, "<%u.%u.%u:%u>", |
882 | tipc_zone(publ->node), tipc_cluster(publ->node), | 812 | tipc_zone(publ->node), tipc_cluster(publ->node), |
883 | tipc_node(publ->node), publ->ref); | 813 | tipc_node(publ->node), publ->ref); |
@@ -886,13 +816,9 @@ static void subseq_list(struct sub_seq *sseq, struct print_buf *buf, u32 depth, | |||
886 | tipc_printf(buf, "%-10u %s", publ->key, | 816 | tipc_printf(buf, "%-10u %s", publ->key, |
887 | scope_str[publ->scope]); | 817 | scope_str[publ->scope]); |
888 | } | 818 | } |
889 | 819 | if (!list_is_last(&publ->zone_list, &info->zone_list)) | |
890 | publ = publ->zone_list_next; | 820 | tipc_printf(buf, "\n%33s", " "); |
891 | if (publ == sseq->info->zone_list) | 821 | }; |
892 | break; | ||
893 | |||
894 | tipc_printf(buf, "\n%33s", " "); | ||
895 | } while (1); | ||
896 | 822 | ||
897 | tipc_printf(buf, "\n"); | 823 | tipc_printf(buf, "\n"); |
898 | } | 824 | } |
diff --git a/net/tipc/name_table.h b/net/tipc/name_table.h index d228bd682655..62d77e5e902e 100644 --- a/net/tipc/name_table.h +++ b/net/tipc/name_table.h | |||
@@ -2,7 +2,7 @@ | |||
2 | * net/tipc/name_table.h: Include file for TIPC name table code | 2 | * net/tipc/name_table.h: Include file for TIPC name table code |
3 | * | 3 | * |
4 | * Copyright (c) 2000-2006, Ericsson AB | 4 | * Copyright (c) 2000-2006, Ericsson AB |
5 | * Copyright (c) 2004-2005, Wind River Systems | 5 | * Copyright (c) 2004-2005, 2010-2011, Wind River Systems |
6 | * All rights reserved. | 6 | * All rights reserved. |
7 | * | 7 | * |
8 | * Redistribution and use in source and binary forms, with or without | 8 | * Redistribution and use in source and binary forms, with or without |
@@ -61,9 +61,9 @@ struct port_list; | |||
61 | * @subscr: subscription to "node down" event (for off-node publications only) | 61 | * @subscr: subscription to "node down" event (for off-node publications only) |
62 | * @local_list: adjacent entries in list of publications made by this node | 62 | * @local_list: adjacent entries in list of publications made by this node |
63 | * @pport_list: adjacent entries in list of publications made by this port | 63 | * @pport_list: adjacent entries in list of publications made by this port |
64 | * @node_list: next matching name seq publication with >= node scope | 64 | * @node_list: adjacent matching name seq publications with >= node scope |
65 | * @cluster_list: next matching name seq publication with >= cluster scope | 65 | * @cluster_list: adjacent matching name seq publications with >= cluster scope |
66 | * @zone_list: next matching name seq publication with >= zone scope | 66 | * @zone_list: adjacent matching name seq publications with >= zone scope |
67 | * | 67 | * |
68 | * Note that the node list, cluster list, and zone list are circular lists. | 68 | * Note that the node list, cluster list, and zone list are circular lists. |
69 | */ | 69 | */ |
@@ -79,9 +79,9 @@ struct publication { | |||
79 | struct tipc_node_subscr subscr; | 79 | struct tipc_node_subscr subscr; |
80 | struct list_head local_list; | 80 | struct list_head local_list; |
81 | struct list_head pport_list; | 81 | struct list_head pport_list; |
82 | struct publication *node_list_next; | 82 | struct list_head node_list; |
83 | struct publication *cluster_list_next; | 83 | struct list_head cluster_list; |
84 | struct publication *zone_list_next; | 84 | struct list_head zone_list; |
85 | }; | 85 | }; |
86 | 86 | ||
87 | 87 | ||