Root/
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 | |
47 | struct 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 | |
64 | struct 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 | |
92 | static struct ref_table tipc_ref_table = { NULL }; |
93 | |
94 | static DEFINE_RWLOCK(ref_table_lock); |
95 | |
96 | /** |
97 | * tipc_ref_table_init - create reference table for objects |
98 | */ |
99 | |
100 | int 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 | |
133 | void 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 | |
154 | u32 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 | |
212 | void 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 | |
254 | exit: |
255 | write_unlock_bh(&ref_table_lock); |
256 | } |
257 | |
258 | /** |
259 | * tipc_ref_lock - lock referenced object and return pointer to it |
260 | */ |
261 | |
262 | void *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 | |
283 | void 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 | |
301 | void *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 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9