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 */
 46struct reference {
 47	void *object;
 48	spinlock_t lock;
 49	u32 ref;
 50};
 51
 52/**
 53 * struct tipc_ref_table - table of TIPC object reference entries
 54 * @entries: pointer to array of reference entries
 55 * @capacity: array index of first unusable entry
 56 * @init_point: array index of first uninitialized entry
 57 * @first_free: array index of first unused object reference entry
 58 * @last_free: array index of last unused object reference entry
 59 * @index_mask: bitmask for array index portion of reference values
 60 * @start_mask: initial value for instance value portion of reference values
 61 */
 62struct ref_table {
 63	struct reference *entries;
 64	u32 capacity;
 65	u32 init_point;
 66	u32 first_free;
 67	u32 last_free;
 68	u32 index_mask;
 69	u32 start_mask;
 70};
 71
 72/*
 73 * Object reference table consists of 2**N entries.
 74 *
 75 * State	Object ptr	Reference
 76 * -----        ----------      ---------
 77 * In use        non-NULL       XXXX|own index
 78 *				(XXXX changes each time entry is acquired)
 79 * Free            NULL         YYYY|next free index
 80 *				(YYYY is one more than last used XXXX)
 81 * Uninitialized   NULL         0
 82 *
 83 * Entry 0 is not used; this allows index 0 to denote the end of the free list.
 84 *
 85 * Note that a reference value of 0 does not necessarily indicate that an
 86 * entry is uninitialized, since the last entry in the free list could also
 87 * have a reference value of 0 (although this is unlikely).
 88 */
 89
 90static struct ref_table tipc_ref_table;
 91
 92static DEFINE_SPINLOCK(ref_table_lock);
 93
 94/**
 95 * tipc_ref_table_init - create reference table for objects
 96 */
 97int tipc_ref_table_init(u32 requested_size, u32 start)
 98{
 99	struct reference *table;
100	u32 actual_size;
101
102	/* account for unused entry, then round up size to a power of 2 */
103
104	requested_size++;
105	for (actual_size = 16; actual_size < requested_size; actual_size <<= 1)
106		/* do nothing */ ;
107
108	/* allocate table & mark all entries as uninitialized */
109	table = vzalloc(actual_size * sizeof(struct reference));
110	if (table == NULL)
111		return -ENOMEM;
112
113	tipc_ref_table.entries = table;
114	tipc_ref_table.capacity = requested_size;
115	tipc_ref_table.init_point = 1;
116	tipc_ref_table.first_free = 0;
117	tipc_ref_table.last_free = 0;
118	tipc_ref_table.index_mask = actual_size - 1;
119	tipc_ref_table.start_mask = start & ~tipc_ref_table.index_mask;
120
121	return 0;
122}
123
124/**
125 * tipc_ref_table_stop - destroy reference table for objects
126 */
127void tipc_ref_table_stop(void)
128{
129	vfree(tipc_ref_table.entries);
130	tipc_ref_table.entries = NULL;
131}
132
133/**
134 * tipc_ref_acquire - create reference to an object
135 *
136 * Register an object pointer in reference table and lock the object.
137 * Returns a unique reference value that is used from then on to retrieve the
138 * object pointer, or to determine that the object has been deregistered.
139 *
140 * Note: The object is returned in the locked state so that the caller can
141 * register a partially initialized object, without running the risk that
142 * the object will be accessed before initialization is complete.
143 */
144u32 tipc_ref_acquire(void *object, spinlock_t **lock)
145{
146	u32 index;
147	u32 index_mask;
148	u32 next_plus_upper;
149	u32 ref;
150	struct reference *entry = NULL;
151
152	if (!object) {
153		pr_err("Attempt to acquire ref. to non-existent obj\n");
154		return 0;
155	}
156	if (!tipc_ref_table.entries) {
157		pr_err("Ref. table not found in acquisition attempt\n");
158		return 0;
159	}
160
161	/* take a free entry, if available; otherwise initialize a new entry */
162	spin_lock_bh(&ref_table_lock);
163	if (tipc_ref_table.first_free) {
164		index = tipc_ref_table.first_free;
165		entry = &(tipc_ref_table.entries[index]);
166		index_mask = tipc_ref_table.index_mask;
167		next_plus_upper = entry->ref;
168		tipc_ref_table.first_free = next_plus_upper & index_mask;
169		ref = (next_plus_upper & ~index_mask) + index;
170	} else if (tipc_ref_table.init_point < tipc_ref_table.capacity) {
171		index = tipc_ref_table.init_point++;
172		entry = &(tipc_ref_table.entries[index]);
173		spin_lock_init(&entry->lock);
174		ref = tipc_ref_table.start_mask + index;
175	} else {
176		ref = 0;
177	}
178	spin_unlock_bh(&ref_table_lock);
179
180	/*
181	 * Grab the lock so no one else can modify this entry
182	 * While we assign its ref value & object pointer
183	 */
184	if (entry) {
185		spin_lock_bh(&entry->lock);
186		entry->ref = ref;
187		entry->object = object;
188		*lock = &entry->lock;
189		/*
190		 * keep it locked, the caller is responsible
191		 * for unlocking this when they're done with it
192		 */
193	}
194
195	return ref;
196}
197
198/**
199 * tipc_ref_discard - invalidate references to an object
200 *
201 * Disallow future references to an object and free up the entry for re-use.
202 * Note: The entry's spin_lock may still be busy after discard
203 */
204void tipc_ref_discard(u32 ref)
205{
206	struct reference *entry;
207	u32 index;
208	u32 index_mask;
209
210	if (!tipc_ref_table.entries) {
211		pr_err("Ref. table not found during discard attempt\n");
212		return;
213	}
214
215	index_mask = tipc_ref_table.index_mask;
216	index = ref & index_mask;
217	entry = &(tipc_ref_table.entries[index]);
218
219	spin_lock_bh(&ref_table_lock);
220
221	if (!entry->object) {
222		pr_err("Attempt to discard ref. to non-existent obj\n");
223		goto exit;
224	}
225	if (entry->ref != ref) {
226		pr_err("Attempt to discard non-existent reference\n");
227		goto exit;
228	}
229
230	/*
231	 * mark entry as unused; increment instance part of entry's reference
232	 * to invalidate any subsequent references
233	 */
234	entry->object = NULL;
235	entry->ref = (ref & ~index_mask) + (index_mask + 1);
236
237	/* append entry to free entry list */
238	if (tipc_ref_table.first_free == 0)
239		tipc_ref_table.first_free = index;
240	else
241		tipc_ref_table.entries[tipc_ref_table.last_free].ref |= index;
242	tipc_ref_table.last_free = index;
243
244exit:
245	spin_unlock_bh(&ref_table_lock);
246}
247
248/**
249 * tipc_ref_lock - lock referenced object and return pointer to it
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}