ref.c 6.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210
  1. /*
  2. * net/tipc/ref.c: TIPC object registry code
  3. *
  4. * Copyright (c) 1991-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 "ref.h"
  38. #include "port.h"
  39. #include "subscr.h"
  40. #include "name_distr.h"
  41. #include "name_table.h"
  42. #include "config.h"
  43. #include "discover.h"
  44. #include "bearer.h"
  45. #include "node.h"
  46. #include "bcast.h"
  47. /*
  48. * Object reference table consists of 2**N entries.
  49. *
  50. * A used entry has object ptr != 0, reference == XXXX|own index
  51. * (XXXX changes each time entry is acquired)
  52. * A free entry has object ptr == 0, reference == YYYY|next free index
  53. * (YYYY is one more than last used XXXX)
  54. *
  55. * Free list is initially chained from entry (2**N)-1 to entry 1.
  56. * Entry 0 is not used to allow index 0 to indicate the end of the free list.
  57. *
  58. * Note: Any accidental reference of the form XXXX|0--0 won't match entry 0
  59. * because entry 0's reference field has the form XXXX|1--1.
  60. */
  61. struct ref_table tipc_ref_table = { NULL };
  62. static DEFINE_RWLOCK(ref_table_lock);
  63. /**
  64. * tipc_ref_table_init - create reference table for objects
  65. */
  66. int tipc_ref_table_init(u32 requested_size, u32 start)
  67. {
  68. struct reference *table;
  69. u32 sz = 1 << 4;
  70. u32 index_mask;
  71. int i;
  72. while (sz < requested_size) {
  73. sz <<= 1;
  74. }
  75. table = vmalloc(sz * sizeof(*table));
  76. if (table == NULL)
  77. return -ENOMEM;
  78. write_lock_bh(&ref_table_lock);
  79. index_mask = sz - 1;
  80. for (i = sz - 1; i >= 0; i--) {
  81. table[i].object = NULL;
  82. spin_lock_init(&table[i].lock);
  83. table[i].data.next_plus_upper = (start & ~index_mask) + i - 1;
  84. }
  85. tipc_ref_table.entries = table;
  86. tipc_ref_table.index_mask = index_mask;
  87. tipc_ref_table.first_free = sz - 1;
  88. tipc_ref_table.last_free = 1;
  89. write_unlock_bh(&ref_table_lock);
  90. return TIPC_OK;
  91. }
  92. /**
  93. * tipc_ref_table_stop - destroy reference table for objects
  94. */
  95. void tipc_ref_table_stop(void)
  96. {
  97. if (!tipc_ref_table.entries)
  98. return;
  99. vfree(tipc_ref_table.entries);
  100. tipc_ref_table.entries = NULL;
  101. }
  102. /**
  103. * tipc_ref_acquire - create reference to an object
  104. *
  105. * Return a unique reference value which can be translated back to the pointer
  106. * 'object' at a later time. Also, pass back a pointer to the lock protecting
  107. * the object, but without locking it.
  108. */
  109. u32 tipc_ref_acquire(void *object, spinlock_t **lock)
  110. {
  111. struct reference *entry;
  112. u32 index;
  113. u32 index_mask;
  114. u32 next_plus_upper;
  115. u32 reference = 0;
  116. if (!object) {
  117. err("Attempt to acquire reference to non-existent object\n");
  118. return 0;
  119. }
  120. if (!tipc_ref_table.entries) {
  121. err("Reference table not found during acquisition attempt\n");
  122. return 0;
  123. }
  124. write_lock_bh(&ref_table_lock);
  125. if (tipc_ref_table.first_free) {
  126. index = tipc_ref_table.first_free;
  127. entry = &(tipc_ref_table.entries[index]);
  128. index_mask = tipc_ref_table.index_mask;
  129. /* take lock in case a previous user of entry still holds it */
  130. spin_lock_bh(&entry->lock);
  131. next_plus_upper = entry->data.next_plus_upper;
  132. tipc_ref_table.first_free = next_plus_upper & index_mask;
  133. reference = (next_plus_upper & ~index_mask) + index;
  134. entry->data.reference = reference;
  135. entry->object = object;
  136. if (lock != 0)
  137. *lock = &entry->lock;
  138. spin_unlock_bh(&entry->lock);
  139. }
  140. write_unlock_bh(&ref_table_lock);
  141. return reference;
  142. }
  143. /**
  144. * tipc_ref_discard - invalidate references to an object
  145. *
  146. * Disallow future references to an object and free up the entry for re-use.
  147. * Note: The entry's spin_lock may still be busy after discard
  148. */
  149. void tipc_ref_discard(u32 ref)
  150. {
  151. struct reference *entry;
  152. u32 index;
  153. u32 index_mask;
  154. if (!ref) {
  155. err("Attempt to discard reference 0\n");
  156. return;
  157. }
  158. if (!tipc_ref_table.entries) {
  159. err("Reference table not found during discard attempt\n");
  160. return;
  161. }
  162. write_lock_bh(&ref_table_lock);
  163. index_mask = tipc_ref_table.index_mask;
  164. index = ref & index_mask;
  165. entry = &(tipc_ref_table.entries[index]);
  166. if (!entry->object) {
  167. err("Attempt to discard reference to non-existent object\n");
  168. goto exit;
  169. }
  170. if (entry->data.reference != ref) {
  171. err("Attempt to discard non-existent reference\n");
  172. goto exit;
  173. }
  174. /* mark entry as unused */
  175. entry->object = NULL;
  176. if (tipc_ref_table.first_free == 0)
  177. tipc_ref_table.first_free = index;
  178. else
  179. /* next_plus_upper is always XXXX|0--0 for last free entry */
  180. tipc_ref_table.entries[tipc_ref_table.last_free].data.next_plus_upper
  181. |= index;
  182. tipc_ref_table.last_free = index;
  183. /* increment upper bits of entry to invalidate subsequent references */
  184. entry->data.next_plus_upper = (ref & ~index_mask) + (index_mask + 1);
  185. exit:
  186. write_unlock_bh(&ref_table_lock);
  187. }