net/tipc/ref.c

   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 #include "port.h"
  40 #include "subscr.h"
  41 #include "name_distr.h"
  42 #include "name_table.h"
  43 #include "config.h"
  44 #include "discover.h"
  45 #include "bearer.h"
  46 #include "node.h"
  47 #include "bcast.h"
  48
  49 /**
  50  * struct reference - TIPC object reference entry
  51  * @object: pointer to object associated with reference entry
  52  * @lock: spinlock controlling access to object
  53  * @data: reference value associated with object (or link to next unused entry)
  54  */
  55
  56 struct reference {
  57         void *object;
  58         spinlock_t lock;
  59         union {
  60                 u32 next_plus_upper;
  61                 u32 reference;
  62         } data;
  63 };
  64
  65 /**
  66  * struct tipc_ref_table - table of TIPC object reference entries
  67  * @entries: pointer to array of reference entries
  68  * @index_mask: bitmask for array index portion of reference values
  69  * @first_free: array index of first unused object reference entry
  70  * @last_free: array index of last unused object reference entry
  71  */
  72
  73 struct ref_table {
  74         struct reference *entries;
  75         u32 index_mask;
  76         u32 first_free;
  77         u32 last_free;
  78 };
  79
  80 /*
  81  * Object reference table consists of 2**N entries.
  82  *
  83  * A used entry has object ptr != 0, reference == XXXX|own index
  84  *                                   (XXXX changes each time entry is acquired)
  85  * A free entry has object ptr == 0, reference == YYYY|next free index
  86  *                                   (YYYY is one more than last used XXXX)
  87  *
  88  * Free list is initially chained from entry (2**N)-1 to entry 1.
  89  * Entry 0 is not used to allow index 0 to indicate the end of the free list.
  90  *
  91  * Note: Any accidental reference of the form XXXX|0--0 won't match entry 0
  92  * because entry 0's reference field has the form XXXX|1--1.
  93  */
  94
  95 static struct ref_table tipc_ref_table = { NULL };
  96
  97 static DEFINE_RWLOCK(ref_table_lock);
  98
  99 /**
 100  * tipc_ref_table_init - create reference table for objects
 101  */
 102
 103 int tipc_ref_table_init(u32 requested_size, u32 start)
 104 {
 105         struct reference *table;
 106         u32 sz = 1 << 4;
 107         u32 index_mask;
 108         int i;
 109
 110         while (sz < requested_size) {
 111                 sz <<= 1;
 112         }
 113         table = vmalloc(sz * sizeof(*table));
 114         if (table == NULL)
 115                 return -ENOMEM;
 116
 117         write_lock_bh(&ref_table_lock);
 118         index_mask = sz - 1;
 119         for (i = sz - 1; i >= 0; i--) {
 120                 table[i].object = NULL;
 121                 spin_lock_init(&table[i].lock);
 122                 table[i].data.next_plus_upper = (start & ~index_mask) + i - 1;
 123         }
 124         tipc_ref_table.entries = table;
 125         tipc_ref_table.index_mask = index_mask;
 126         tipc_ref_table.first_free = sz - 1;
 127         tipc_ref_table.last_free = 1;
 128         write_unlock_bh(&ref_table_lock);
 129         return TIPC_OK;
 130 }
 131
 132 /**
 133  * tipc_ref_table_stop - destroy reference table for objects
 134  */
 135
 136 void tipc_ref_table_stop(void)
 137 {
 138         if (!tipc_ref_table.entries)
 139                 return;
 140
 141         vfree(tipc_ref_table.entries);
 142         tipc_ref_table.entries = NULL;
 143 }
 144
 145 /**
 146  * tipc_ref_acquire - create reference to an object
 147  *
 148  * Return a unique reference value which can be translated back to the pointer
 149  * 'object' at a later time.  Also, pass back a pointer to the lock protecting
 150  * the object, but without locking it.
 151  */
 152
 153 u32 tipc_ref_acquire(void *object, spinlock_t **lock)
 154 {
 155         struct reference *entry;
 156         u32 index;
 157         u32 index_mask;
 158         u32 next_plus_upper;
 159         u32 reference = 0;
 160
 161         if (!object) {
 162                 err("Attempt to acquire reference to non-existent object\n");
 163                 return 0;
 164         }
 165         if (!tipc_ref_table.entries) {
 166                 err("Reference table not found during acquisition attempt\n");
 167                 return 0;
 168         }
 169
 170         write_lock_bh(&ref_table_lock);
 171         if (tipc_ref_table.first_free) {
 172                 index = tipc_ref_table.first_free;
 173                 entry = &(tipc_ref_table.entries[index]);
 174                 index_mask = tipc_ref_table.index_mask;
 175                 /* take lock in case a previous user of entry still holds it */
 176                 spin_lock_bh(&entry->lock);
 177                 next_plus_upper = entry->data.next_plus_upper;
 178                 tipc_ref_table.first_free = next_plus_upper & index_mask;
 179                 reference = (next_plus_upper & ~index_mask) + index;
 180                 entry->data.reference = reference;
 181                 entry->object = object;
 182                 if (lock != NULL)
 183                         *lock = &entry->lock;
 184                 spin_unlock_bh(&entry->lock);
 185         }
 186         write_unlock_bh(&ref_table_lock);
 187         return reference;
 188 }
 189
 190 /**
 191  * tipc_ref_discard - invalidate references to an object
 192  *
 193  * Disallow future references to an object and free up the entry for re-use.
 194  * Note: The entry's spin_lock may still be busy after discard
 195  */
 196
 197 void tipc_ref_discard(u32 ref)
 198 {
 199         struct reference *entry;
 200         u32 index;
 201         u32 index_mask;
 202
 203         if (!ref) {
 204                 err("Attempt to discard reference 0\n");
 205                 return;
 206         }
 207         if (!tipc_ref_table.entries) {
 208                 err("Reference table not found during discard attempt\n");
 209                 return;
 210         }
 211
 212         write_lock_bh(&ref_table_lock);
 213         index_mask = tipc_ref_table.index_mask;
 214         index = ref & index_mask;
 215         entry = &(tipc_ref_table.entries[index]);
 216
 217         if (!entry->object) {
 218                 err("Attempt to discard reference to non-existent object\n");
 219                 goto exit;
 220         }
 221         if (entry->data.reference != ref) {
 222                 err("Attempt to discard non-existent reference\n");
 223                 goto exit;
 224         }
 225
 226         /* mark entry as unused */
 227         entry->object = NULL;
 228         if (tipc_ref_table.first_free == 0)
 229                 tipc_ref_table.first_free = index;
 230         else
 231                 /* next_plus_upper is always XXXX|0--0 for last free entry */
 232                 tipc_ref_table.entries[tipc_ref_table.last_free].
 233                         data.next_plus_upper |= index;
 234         tipc_ref_table.last_free = index;
 235
 236         /* increment upper bits of entry to invalidate subsequent references */
 237         entry->data.next_plus_upper = (ref & ~index_mask) + (index_mask + 1);
 238 exit:
 239         write_unlock_bh(&ref_table_lock);
 240 }
 241
 242 /**
 243  * tipc_ref_lock - lock referenced object and return pointer to it
 244  */
 245
 246 void *tipc_ref_lock(u32 ref)
 247 {
 248         if (likely(tipc_ref_table.entries)) {
 249                 struct reference *r;
 250
 251                 r = &tipc_ref_table.entries[ref & tipc_ref_table.index_mask];
 252                 spin_lock_bh(&r->lock);
 253                 if (likely(r->data.reference == ref))
 254                         return r->object;
 255                 spin_unlock_bh(&r->lock);
 256         }
 257         return NULL;
 258 }
 259
 260 /**
 261  * tipc_ref_unlock - unlock referenced object
 262  */
 263
 264 void tipc_ref_unlock(u32 ref)
 265 {
 266         if (likely(tipc_ref_table.entries)) {
 267                 struct reference *r;
 268
 269                 r = &tipc_ref_table.entries[ref & tipc_ref_table.index_mask];
 270                 if (likely(r->data.reference == ref))
 271                         spin_unlock_bh(&r->lock);
 272                 else
 273                         err("tipc_ref_unlock() invoked using "
 274                             "obsolete reference\n");
 275         }
 276 }
 277
 278 /**
 279  * tipc_ref_deref - return pointer referenced object (without locking it)
 280  */
 281
 282 void *tipc_ref_deref(u32 ref)
 283 {
 284         if (likely(tipc_ref_table.entries)) {
 285                 struct reference *r;
 286
 287                 r = &tipc_ref_table.entries[ref & tipc_ref_table.index_mask];
 288                 if (likely(r->data.reference == ref))
 289                         return r->object;
 290         }
 291         return NULL;
 292 }
 293