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 75static struct ref_table tipc_ref_table = { NULL }; 76 77static DEFINE_RWLOCK(ref_table_lock); 78 79/** 80 * tipc_ref_table_init - create reference table for objects 81 */ 82 83int tipc_ref_table_init(u32 requested_size, u32 start) 84{ 85 struct reference *table; 86 u32 actual_size; 87 88 /* account for unused entry, then round up size to a power of 2 */ 89 90 requested_size++; 91 for (actual_size = 16; actual_size < requested_size; actual_size <<= 1) 92 /* do nothing */ ; 93 94 /* allocate table & mark all entries as uninitialized */ 95 96 table = __vmalloc(actual_size * sizeof(struct reference), 97 GFP_KERNEL | __GFP_HIGHMEM | __GFP_ZERO, PAGE_KERNEL); 98 if (table == NULL) 99 return -ENOMEM; 100 101 tipc_ref_table.entries = table; 102 tipc_ref_table.capacity = requested_size; 103 tipc_ref_table.init_point = 1; 104 tipc_ref_table.first_free = 0; 105 tipc_ref_table.last_free = 0; 106 tipc_ref_table.index_mask = actual_size - 1; 107 tipc_ref_table.start_mask = start & ~tipc_ref_table.index_mask; 108 109 return 0; 110} 111 112/** 113 * tipc_ref_table_stop - destroy reference table for objects 114 */ 115 116void tipc_ref_table_stop(void) 117{ 118 if (!tipc_ref_table.entries) 119 return; 120 121 vfree(tipc_ref_table.entries); 122 tipc_ref_table.entries = NULL; 123} 124 125/** 126 * tipc_ref_acquire - create reference to an object 127 * 128 * Register an object pointer in reference table and lock the object. 129 * Returns a unique reference value that is used from then on to retrieve the 130 * object pointer, or to determine that the object has been deregistered. 131 * 132 * Note: The object is returned in the locked state so that the caller can 133 * register a partially initialized object, without running the risk that 134 * the object will be accessed before initialization is complete. 135 */ 136 137u32 tipc_ref_acquire(void *object, spinlock_t **lock) 138{ 139 u32 index; 140 u32 index_mask; 141 u32 next_plus_upper; 142 u32 ref; 143 struct reference *entry = NULL; 144 145 if (!object) { 146 err("Attempt to acquire reference to non-existent object\n"); 147 return 0; 148 } 149 if (!tipc_ref_table.entries) { 150 err("Reference table not found during acquisition attempt\n"); 151 return 0; 152 } 153 154 /* take a free entry, if available; otherwise initialize a new entry */ 155 156 write_lock_bh(&ref_table_lock); 157 if (tipc_ref_table.first_free) { 158 index = tipc_ref_table.first_free; 159 entry = &(tipc_ref_table.entries[index]); 160 index_mask = tipc_ref_table.index_mask; 161 next_plus_upper = entry->ref; 162 tipc_ref_table.first_free = next_plus_upper & index_mask; 163 ref = (next_plus_upper & ~index_mask) + index; 164 } 165 else if (tipc_ref_table.init_point < tipc_ref_table.capacity) { 166 index = tipc_ref_table.init_point++; 167 entry = &(tipc_ref_table.entries[index]); 168 spin_lock_init(&entry->lock); 169 ref = tipc_ref_table.start_mask + index; 170 } 171 else { 172 ref = 0; 173 } 174 write_unlock_bh(&ref_table_lock); 175 176 /* 177 * Grab the lock so no one else can modify this entry 178 * While we assign its ref value & object pointer 179 */ 180 if (entry) { 181 spin_lock_bh(&entry->lock); 182 entry->ref = ref; 183 entry->object = object; 184 *lock = &entry->lock; 185 /* 186 * keep it locked, the caller is responsible 187 * for unlocking this when they're done with it 188 */ 189 } 190 191 return ref; 192} 193 194/** 195 * tipc_ref_discard - invalidate references to an object 196 * 197 * Disallow future references to an object and free up the entry for re-use. 198 * Note: The entry's spin_lock may still be busy after discard 199 */ 200 201void tipc_ref_discard(u32 ref) 202{ 203 struct reference *entry; 204 u32 index; 205 u32 index_mask; 206 207 if (!tipc_ref_table.entries) { 208 err("Reference table not found during discard attempt\n"); 209 return; 210 } 211 212 index_mask = tipc_ref_table.index_mask; 213 index = ref & index_mask; 214 entry = &(tipc_ref_table.entries[index]); 215 216 write_lock_bh(&ref_table_lock); 217 218 if (!entry->object) { 219 err("Attempt to discard reference to non-existent object\n"); 220 goto exit; 221 } 222 if (entry->ref != ref) { 223 err("Attempt to discard non-existent reference\n"); 224 goto exit; 225 } 226 227 /* 228 * mark entry as unused; increment instance part of entry's reference 229 * to invalidate any subsequent references 230 */ 231 232 entry->object = NULL; 233 entry->ref = (ref & ~index_mask) + (index_mask + 1); 234 235 /* append entry to free entry list */ 236 237 if (tipc_ref_table.first_free == 0) 238 tipc_ref_table.first_free = index; 239 else 240 tipc_ref_table.entries[tipc_ref_table.last_free].ref |= index; 241 tipc_ref_table.last_free = index; 242 243exit: 244 write_unlock_bh(&ref_table_lock); 245} 246 247/** 248 * tipc_ref_lock - lock referenced object and return pointer to it 249 */ 250 251void *tipc_ref_lock(u32 ref) 252{ 253 if (likely(tipc_ref_table.entries)) { 254 struct reference *entry; 255 256 entry = &tipc_ref_table.entries[ref & 257 tipc_ref_table.index_mask]; 258 if (likely(entry->ref != 0)) { 259 spin_lock_bh(&entry->lock); 260 if (likely((entry->ref == ref) && (entry->object))) 261 return entry->object; 262 spin_unlock_bh(&entry->lock); 263 } 264 } 265 return NULL; 266} 267 268/** 269 * tipc_ref_unlock - unlock referenced object 270 */ 271 272void tipc_ref_unlock(u32 ref) 273{ 274 if (likely(tipc_ref_table.entries)) { 275 struct reference *entry; 276 277 entry = &tipc_ref_table.entries[ref & 278 tipc_ref_table.index_mask]; 279 if (likely((entry->ref == ref) && (entry->object))) 280 spin_unlock_bh(&entry->lock); 281 else 282 err("Attempt to unlock non-existent reference\n"); 283 } 284} 285 286/** 287 * tipc_ref_deref - return pointer referenced object (without locking it) 288 */ 289 290void *tipc_ref_deref(u32 ref) 291{ 292 if (likely(tipc_ref_table.entries)) { 293 struct reference *entry; 294 295 entry = &tipc_ref_table.entries[ref & 296 tipc_ref_table.index_mask]; 297 if (likely(entry->ref == ref)) 298 return entry->object; 299 } 300 return NULL; 301} 302