1/* 2 * net/tipc/ref.c: TIPC object registry code 3 * 4 * Copyright (c) 1991-2006, Ericsson AB 5 * Copyright (c) 2004-2007, 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 37#include "core.h" 38#include "ref.h" 39 40/** 41 * struct reference - TIPC object reference entry 42 * @object: pointer to object associated with reference entry 43 * @lock: spinlock controlling access to object 44 * @ref: reference value for object (combines instance & array index info) 45 */ 46 47struct reference { 48 void *object; 49 spinlock_t lock; 50 u32 ref; 51}; 52 53/** 54 * struct tipc_ref_table - table of TIPC object reference entries 55 * @entries: pointer to array of reference entries 56 * @capacity: array index of first unusable entry 57 * @init_point: array index of first uninitialized entry 58 * @first_free: array index of first unused object reference entry 59 * @last_free: array index of last unused object reference entry 60 * @index_mask: bitmask for array index portion of reference values 61 * @start_mask: initial value for instance value portion of reference values 62 */ 63 64struct ref_table { 65 struct reference *entries; 66 u32 capacity; 67 u32 init_point; 68 u32 first_free; 69 u32 last_free; 70 u32 index_mask; 71 u32 start_mask; 72}; 73 74/* 75 * Object reference table consists of 2**N entries. 76 * 77 * State Object ptr Reference 78 * ----- ---------- --------- 79 * In use non-NULL XXXX|own index 80 * (XXXX changes each time entry is acquired) 81 * Free NULL YYYY|next free index 82 * (YYYY is one more than last used XXXX) 83 * Uninitialized NULL 0 84 * 85 * Entry 0 is not used; this allows index 0 to denote the end of the free list. 86 * 87 * Note that a reference value of 0 does not necessarily indicate that an 88 * entry is uninitialized, since the last entry in the free list could also 89 * have a reference value of 0 (although this is unlikely). 90 */ 91 92static struct ref_table tipc_ref_table = { NULL }; 93 94static DEFINE_RWLOCK(ref_table_lock); 95 96/** 97 * tipc_ref_table_init - create reference table for objects 98 */ 99 100int tipc_ref_table_init(u32 requested_size, u32 start) 101{ 102 struct reference *table; 103 u32 actual_size; 104 105 /* account for unused entry, then round up size to a power of 2 */ 106 107 requested_size++; 108 for (actual_size = 16; actual_size < requested_size; actual_size <<= 1) 109 /* do nothing */ ; 110 111 /* allocate table & mark all entries as uninitialized */ 112 113 table = __vmalloc(actual_size * sizeof(struct reference), 114 GFP_KERNEL | __GFP_HIGHMEM | __GFP_ZERO, PAGE_KERNEL); 115 if (table == NULL) 116 return -ENOMEM; 117 118 tipc_ref_table.entries = table; 119 tipc_ref_table.capacity = requested_size; 120 tipc_ref_table.init_point = 1; 121 tipc_ref_table.first_free = 0; 122 tipc_ref_table.last_free = 0; 123 tipc_ref_table.index_mask = actual_size - 1; 124 tipc_ref_table.start_mask = start & ~tipc_ref_table.index_mask; 125 126 return 0; 127} 128 129/** 130 * tipc_ref_table_stop - destroy reference table for objects 131 */ 132 133void tipc_ref_table_stop(void) 134{ 135 if (!tipc_ref_table.entries) 136 return; 137 138 vfree(tipc_ref_table.entries); 139 tipc_ref_table.entries = NULL; 140} 141 142/** 143 * tipc_ref_acquire - create reference to an object 144 * 145 * Register an object pointer in reference table and lock the object. 146 * Returns a unique reference value that is used from then on to retrieve the 147 * object pointer, or to determine that the object has been deregistered. 148 * 149 * Note: The object is returned in the locked state so that the caller can 150 * register a partially initialized object, without running the risk that 151 * the object will be accessed before initialization is complete. 152 */ 153 154u32 tipc_ref_acquire(void *object, spinlock_t **lock) 155{ 156 struct reference *entry; 157 u32 index; 158 u32 index_mask; 159 u32 next_plus_upper; 160 u32 ref; 161 162 if (!object) { 163 err("Attempt to acquire reference to non-existent object\n"); 164 return 0; 165 } 166 if (!tipc_ref_table.entries) { 167 err("Reference table not found during acquisition attempt\n"); 168 return 0; 169 } 170 171 /* take a free entry, if available; otherwise initialize a new entry */ 172 173 write_lock_bh(&ref_table_lock); 174 if (tipc_ref_table.first_free) { 175 index = tipc_ref_table.first_free; 176 entry = &(tipc_ref_table.entries[index]); 177 index_mask = tipc_ref_table.index_mask; 178 /* take lock in case a previous user of entry still holds it */ 179 spin_lock_bh(&entry->lock); 180 next_plus_upper = entry->ref; 181 tipc_ref_table.first_free = next_plus_upper & index_mask; 182 ref = (next_plus_upper & ~index_mask) + index; 183 entry->ref = ref; 184 entry->object = object; 185 *lock = &entry->lock; 186 } 187 else if (tipc_ref_table.init_point < tipc_ref_table.capacity) { 188 index = tipc_ref_table.init_point++; 189 entry = &(tipc_ref_table.entries[index]); 190 spin_lock_init(&entry->lock); 191 spin_lock_bh(&entry->lock); 192 ref = tipc_ref_table.start_mask + index; 193 entry->ref = ref; 194 entry->object = object; 195 *lock = &entry->lock; 196 } 197 else { 198 ref = 0; 199 } 200 write_unlock_bh(&ref_table_lock); 201 202 return ref; 203} 204 205/** 206 * tipc_ref_discard - invalidate references to an object 207 * 208 * Disallow future references to an object and free up the entry for re-use. 209 * Note: The entry's spin_lock may still be busy after discard 210 */ 211 212void tipc_ref_discard(u32 ref) 213{ 214 struct reference *entry; 215 u32 index; 216 u32 index_mask; 217 218 if (!tipc_ref_table.entries) { 219 err("Reference table not found during discard attempt\n"); 220 return; 221 } 222 223 index_mask = tipc_ref_table.index_mask; 224 index = ref & index_mask; 225 entry = &(tipc_ref_table.entries[index]); 226 227 write_lock_bh(&ref_table_lock); 228 229 if (!entry->object) { 230 err("Attempt to discard reference to non-existent object\n"); 231 goto exit; 232 } 233 if (entry->ref != ref) { 234 err("Attempt to discard non-existent reference\n"); 235 goto exit; 236 } 237 238 /* 239 * mark entry as unused; increment instance part of entry's reference 240 * to invalidate any subsequent references 241 */ 242 243 entry->object = NULL; 244 entry->ref = (ref & ~index_mask) + (index_mask + 1); 245 246 /* append entry to free entry list */ 247 248 if (tipc_ref_table.first_free == 0) 249 tipc_ref_table.first_free = index; 250 else 251 tipc_ref_table.entries[tipc_ref_table.last_free].ref |= index; 252 tipc_ref_table.last_free = index; 253 254exit: 255 write_unlock_bh(&ref_table_lock); 256} 257 258/** 259 * tipc_ref_lock - lock referenced object and return pointer to it 260 */ 261 262void *tipc_ref_lock(u32 ref) 263{ 264 if (likely(tipc_ref_table.entries)) { 265 struct reference *entry; 266 267 entry = &tipc_ref_table.entries[ref & 268 tipc_ref_table.index_mask]; 269 if (likely(entry->ref != 0)) { 270 spin_lock_bh(&entry->lock); 271 if (likely((entry->ref == ref) && (entry->object))) 272 return entry->object; 273 spin_unlock_bh(&entry->lock); 274 } 275 } 276 return NULL; 277} 278 279/** 280 * tipc_ref_unlock - unlock referenced object 281 */ 282 283void tipc_ref_unlock(u32 ref) 284{ 285 if (likely(tipc_ref_table.entries)) { 286 struct reference *entry; 287 288 entry = &tipc_ref_table.entries[ref & 289 tipc_ref_table.index_mask]; 290 if (likely((entry->ref == ref) && (entry->object))) 291 spin_unlock_bh(&entry->lock); 292 else 293 err("Attempt to unlock non-existent reference\n"); 294 } 295} 296 297/** 298 * tipc_ref_deref - return pointer referenced object (without locking it) 299 */ 300 301void *tipc_ref_deref(u32 ref) 302{ 303 if (likely(tipc_ref_table.entries)) { 304 struct reference *entry; 305 306 entry = &tipc_ref_table.entries[ref & 307 tipc_ref_table.index_mask]; 308 if (likely(entry->ref == ref)) 309 return entry->object; 310 } 311 return NULL; 312} 313 314