net/tipc/ref.c

   1 /*
   2  * net/tipc/ref.c: TIPC socket registry code
   3  *
   4  * Copyright (c) 1991-2006, 2014, 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 socket reference entry
  42  * @tsk: pointer to socket associated with reference entry
  43  * @ref: reference value for socket (combines instance & array index info)
  44  */
  45 struct reference {
  46         struct tipc_sock *tsk;
  47         u32 ref;
  48 };
  49
  50 /**
  51  * struct tipc_ref_table - table of TIPC socket reference entries
  52  * @entries: pointer to array of reference entries
  53  * @capacity: array index of first unusable entry
  54  * @init_point: array index of first uninitialized entry
  55  * @first_free: array index of first unused socket reference entry
  56  * @last_free: array index of last unused socket reference entry
  57  * @index_mask: bitmask for array index portion of reference values
  58  * @start_mask: initial value for instance value portion of reference values
  59  */
  60 struct ref_table {
  61         struct reference *entries;
  62         u32 capacity;
  63         u32 init_point;
  64         u32 first_free;
  65         u32 last_free;
  66         u32 index_mask;
  67         u32 start_mask;
  68 };
  69
  70 /*
  71  * Socket reference table consists of 2**N entries.
  72  *
  73  * State        Socket ptr      Reference
  74  * -----        ----------      ---------
  75  * In use        non-NULL       XXXX|own index
  76  *                              (XXXX changes each time entry is acquired)
  77  * Free            NULL         YYYY|next free index
  78  *                              (YYYY is one more than last used XXXX)
  79  * Uninitialized   NULL         0
  80  *
  81  * Entry 0 is not used; this allows index 0 to denote the end of the free list.
  82  *
  83  * Note that a reference value of 0 does not necessarily indicate that an
  84  * entry is uninitialized, since the last entry in the free list could also
  85  * have a reference value of 0 (although this is unlikely).
  86  */
  87
  88 static struct ref_table tipc_ref_table;
  89
  90 static DEFINE_RWLOCK(ref_table_lock);
  91
  92 /**
  93  * tipc_ref_table_init - create reference table for sockets
  94  */
  95 int tipc_ref_table_init(u32 requested_size, u32 start)
  96 {
  97         struct reference *table;
  98         u32 actual_size;
  99
 100         /* account for unused entry, then round up size to a power of 2 */
 101
 102         requested_size++;
 103         for (actual_size = 16; actual_size < requested_size; actual_size <<= 1)
 104                 /* do nothing */ ;
 105
 106         /* allocate table & mark all entries as uninitialized */
 107         table = vzalloc(actual_size * sizeof(struct reference));
 108         if (table == NULL)
 109                 return -ENOMEM;
 110
 111         tipc_ref_table.entries = table;
 112         tipc_ref_table.capacity = requested_size;
 113         tipc_ref_table.init_point = 1;
 114         tipc_ref_table.first_free = 0;
 115         tipc_ref_table.last_free = 0;
 116         tipc_ref_table.index_mask = actual_size - 1;
 117         tipc_ref_table.start_mask = start & ~tipc_ref_table.index_mask;
 118
 119         return 0;
 120 }
 121
 122 /**
 123  * tipc_ref_table_stop - destroy reference table for sockets
 124  */
 125 void tipc_ref_table_stop(void)
 126 {
 127         if (!tipc_ref_table.entries)
 128                 return;
 129         vfree(tipc_ref_table.entries);
 130         tipc_ref_table.entries = NULL;
 131 }
 132
 133 /* tipc_ref_acquire - create reference to a socket
 134  *
 135  * Register an socket pointer in the reference table.
 136  * Returns a unique reference value that is used from then on to retrieve the
 137  * socket pointer, or to determine if the socket has been deregistered.
 138  */
 139 u32 tipc_ref_acquire(struct tipc_sock *tsk)
 140 {
 141         u32 index;
 142         u32 index_mask;
 143         u32 next_plus_upper;
 144         u32 ref = 0;
 145         struct reference *entry;
 146
 147         if (unlikely(!tsk)) {
 148                 pr_err("Attempt to acquire ref. to non-existent obj\n");
 149                 return 0;
 150         }
 151         if (unlikely(!tipc_ref_table.entries)) {
 152                 pr_err("Ref. table not found in acquisition attempt\n");
 153                 return 0;
 154         }
 155
 156         /* Take a free entry, if available; otherwise initialize a new one */
 157         write_lock_bh(&ref_table_lock);
 158         index = tipc_ref_table.first_free;
 159         entry = &tipc_ref_table.entries[index];
 160
 161         if (likely(index)) {
 162                 index = tipc_ref_table.first_free;
 163                 entry = &(tipc_ref_table.entries[index]);
 164                 index_mask = tipc_ref_table.index_mask;
 165                 next_plus_upper = entry->ref;
 166                 tipc_ref_table.first_free = next_plus_upper & index_mask;
 167                 ref = (next_plus_upper & ~index_mask) + index;
 168                 entry->tsk = tsk;
 169         } else if (tipc_ref_table.init_point < tipc_ref_table.capacity) {
 170                 index = tipc_ref_table.init_point++;
 171                 entry = &(tipc_ref_table.entries[index]);
 172                 ref = tipc_ref_table.start_mask + index;
 173         }
 174
 175         if (ref) {
 176                 entry->ref = ref;
 177                 entry->tsk = tsk;
 178         }
 179         write_unlock_bh(&ref_table_lock);
 180         return ref;
 181 }
 182
 183 /* tipc_ref_discard - invalidate reference to an socket
 184  *
 185  * Disallow future references to an socket and free up the entry for re-use.
 186  */
 187 void tipc_ref_discard(u32 ref)
 188 {
 189         struct reference *entry;
 190         u32 index;
 191         u32 index_mask;
 192
 193         if (unlikely(!tipc_ref_table.entries)) {
 194                 pr_err("Ref. table not found during discard attempt\n");
 195                 return;
 196         }
 197
 198         index_mask = tipc_ref_table.index_mask;
 199         index = ref & index_mask;
 200         entry = &(tipc_ref_table.entries[index]);
 201
 202         write_lock_bh(&ref_table_lock);
 203
 204         if (unlikely(!entry->tsk)) {
 205                 pr_err("Attempt to discard ref. to non-existent socket\n");
 206                 goto exit;
 207         }
 208         if (unlikely(entry->ref != ref)) {
 209                 pr_err("Attempt to discard non-existent reference\n");
 210                 goto exit;
 211         }
 212
 213         /*
 214          * Mark entry as unused; increment instance part of entry's reference
 215          * to invalidate any subsequent references
 216          */
 217         entry->tsk = NULL;
 218         entry->ref = (ref & ~index_mask) + (index_mask + 1);
 219
 220         /* Append entry to free entry list */
 221         if (unlikely(tipc_ref_table.first_free == 0))
 222                 tipc_ref_table.first_free = index;
 223         else
 224                 tipc_ref_table.entries[tipc_ref_table.last_free].ref |= index;
 225         tipc_ref_table.last_free = index;
 226 exit:
 227         write_unlock_bh(&ref_table_lock);
 228 }
 229
 230 /* tipc_sk_get - find referenced socket and return pointer to it
 231  */
 232 struct tipc_sock *tipc_sk_get(u32 ref)
 233 {
 234         struct reference *entry;
 235         struct tipc_sock *tsk;
 236
 237         if (unlikely(!tipc_ref_table.entries))
 238                 return NULL;
 239         read_lock_bh(&ref_table_lock);
 240         entry = &tipc_ref_table.entries[ref & tipc_ref_table.index_mask];
 241         tsk = entry->tsk;
 242         if (likely(tsk && (entry->ref == ref)))
 243                 sock_hold(&tsk->sk);
 244         else
 245                 tsk = NULL;
 246         read_unlock_bh(&ref_table_lock);
 247         return tsk;
 248 }
 249
 250 /* tipc_sk_get_next - lock & return next socket after referenced one
 251 */
 252 struct tipc_sock *tipc_sk_get_next(u32 *ref)
 253 {
 254         struct reference *entry;
 255         struct tipc_sock *tsk = NULL;
 256         uint index = *ref & tipc_ref_table.index_mask;
 257
 258         read_lock_bh(&ref_table_lock);
 259         while (++index < tipc_ref_table.capacity) {
 260                 entry = &tipc_ref_table.entries[index];
 261                 if (!entry->tsk)
 262                         continue;
 263                 tsk = entry->tsk;
 264                 sock_hold(&tsk->sk);
 265                 *ref = entry->ref;
 266                 break;
 267         }
 268         read_unlock_bh(&ref_table_lock);
 269         return tsk;
 270 }