1 | /* |
2 | * Copyright (c) 2000-2004 Apple Computer, Inc. All rights reserved. |
3 | * |
4 | * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ |
5 | * |
6 | * This file contains Original Code and/or Modifications of Original Code |
7 | * as defined in and that are subject to the Apple Public Source License |
8 | * Version 2.0 (the 'License'). You may not use this file except in |
9 | * compliance with the License. The rights granted to you under the License |
10 | * may not be used to create, or enable the creation or redistribution of, |
11 | * unlawful or unlicensed copies of an Apple operating system, or to |
12 | * circumvent, violate, or enable the circumvention or violation of, any |
13 | * terms of an Apple operating system software license agreement. |
14 | * |
15 | * Please obtain a copy of the License at |
16 | * http://www.opensource.apple.com/apsl/ and read it before using this file. |
17 | * |
18 | * The Original Code and all software distributed under the License are |
19 | * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER |
20 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, |
21 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, |
22 | * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. |
23 | * Please see the License for the specific language governing rights and |
24 | * limitations under the License. |
25 | * |
26 | * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ |
27 | */ |
28 | /* |
29 | * @OSF_COPYRIGHT@ |
30 | */ |
31 | /* |
32 | * Mach Operating System |
33 | * Copyright (c) 1991,1990,1989 Carnegie Mellon University |
34 | * All Rights Reserved. |
35 | * |
36 | * Permission to use, copy, modify and distribute this software and its |
37 | * documentation is hereby granted, provided that both the copyright |
38 | * notice and this permission notice appear in all copies of the |
39 | * software, derivative works or modified versions, and any portions |
40 | * thereof, and that both notices appear in supporting documentation. |
41 | * |
42 | * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" |
43 | * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR |
44 | * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. |
45 | * |
46 | * Carnegie Mellon requests users of this software to return to |
47 | * |
48 | * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU |
49 | * School of Computer Science |
50 | * Carnegie Mellon University |
51 | * Pittsburgh PA 15213-3890 |
52 | * |
53 | * any improvements or extensions that they make and grant Carnegie Mellon |
54 | * the rights to redistribute these changes. |
55 | */ |
56 | /* |
57 | */ |
58 | /* |
59 | * File: ipc/ipc_hash.c |
60 | * Author: Rich Draves |
61 | * Date: 1989 |
62 | * |
63 | * Entry hash table operations. |
64 | */ |
65 | |
66 | #include <mach/boolean.h> |
67 | #include <mach/port.h> |
68 | #include <kern/kalloc.h> |
69 | #include <ipc/port.h> |
70 | #include <ipc/ipc_space.h> |
71 | #include <ipc/ipc_object.h> |
72 | #include <ipc/ipc_entry.h> |
73 | #include <ipc/ipc_hash.h> |
74 | #include <ipc/ipc_init.h> |
75 | |
76 | #include <mach_ipc_debug.h> |
77 | |
78 | #if MACH_IPC_DEBUG |
79 | #include <mach/kern_return.h> |
80 | #include <mach_debug/hash_info.h> |
81 | #include <vm/vm_map.h> |
82 | #include <vm/vm_kern.h> |
83 | #endif /* MACH_IPC_DEBUG */ |
84 | |
85 | /* |
86 | * Forward declarations |
87 | */ |
88 | |
89 | /* Delete an entry from the local reverse hash table */ |
90 | void ipc_hash_local_delete( |
91 | ipc_space_t space, |
92 | ipc_object_t obj, |
93 | mach_port_index_t index, |
94 | ipc_entry_t entry); |
95 | |
96 | /* |
97 | * Routine: ipc_hash_lookup |
98 | * Purpose: |
99 | * Converts (space, obj) -> (name, entry). |
100 | * Returns TRUE if an entry was found. |
101 | * Conditions: |
102 | * The space must be locked (read or write) throughout. |
103 | */ |
104 | |
105 | boolean_t |
106 | ipc_hash_lookup( |
107 | ipc_space_t space, |
108 | ipc_object_t obj, |
109 | mach_port_name_t *namep, |
110 | ipc_entry_t *entryp) |
111 | { |
112 | return ipc_hash_table_lookup(space->is_table, space->is_table_size, obj, namep, entryp); |
113 | } |
114 | |
115 | /* |
116 | * Routine: ipc_hash_insert |
117 | * Purpose: |
118 | * Inserts an entry into the appropriate reverse hash table, |
119 | * so that ipc_hash_lookup will find it. |
120 | * Conditions: |
121 | * The space must be write-locked. |
122 | */ |
123 | |
124 | void |
125 | ipc_hash_insert( |
126 | ipc_space_t space, |
127 | ipc_object_t obj, |
128 | mach_port_name_t name, |
129 | ipc_entry_t entry) |
130 | { |
131 | mach_port_index_t index; |
132 | |
133 | index = MACH_PORT_INDEX(name); |
134 | ipc_hash_table_insert(space->is_table, space->is_table_size, obj, index, entry); |
135 | } |
136 | |
137 | /* |
138 | * Routine: ipc_hash_delete |
139 | * Purpose: |
140 | * Deletes an entry from the appropriate reverse hash table. |
141 | * Conditions: |
142 | * The space must be write-locked. |
143 | */ |
144 | |
145 | void |
146 | ipc_hash_delete( |
147 | ipc_space_t space, |
148 | ipc_object_t obj, |
149 | mach_port_name_t name, |
150 | ipc_entry_t entry) |
151 | { |
152 | mach_port_index_t index; |
153 | |
154 | index = MACH_PORT_INDEX(name); |
155 | ipc_hash_table_delete(space->is_table, space->is_table_size, obj, index, entry); |
156 | } |
157 | |
158 | /* |
159 | * Each space has a local reverse hash table, which holds |
160 | * entries from the space's table. In fact, the hash table |
161 | * just uses a field (ie_index) in the table itself. |
162 | * |
163 | * The local hash table is an open-addressing hash table, |
164 | * which means that when a collision occurs, instead of |
165 | * throwing the entry into a bucket, the entry is rehashed |
166 | * to another position in the table. In this case the rehash |
167 | * is very simple: linear probing (ie, just increment the position). |
168 | * This simple rehash makes deletions tractable (they're still a pain), |
169 | * but it means that collisions tend to build up into clumps. |
170 | * |
171 | * Because at least one entry in the table (index 0) is always unused, |
172 | * there will always be room in the reverse hash table. If a table |
173 | * with n slots gets completely full, the reverse hash table will |
174 | * have one giant clump of n-1 slots and one free slot somewhere. |
175 | * Because entries are only entered into the reverse table if they |
176 | * are pure send rights (not receive, send-once, port-set, |
177 | * or dead-name rights), and free entries of course aren't entered, |
178 | * I expect the reverse hash table won't get unreasonably full. |
179 | * |
180 | * Ordered hash tables (Amble & Knuth, Computer Journal, v. 17, no. 2, |
181 | * pp. 135-142.) may be desirable here. They can dramatically help |
182 | * unsuccessful lookups. But unsuccessful lookups are almost always |
183 | * followed by insertions, and those slow down somewhat. They |
184 | * also can help deletions somewhat. Successful lookups aren't affected. |
185 | * So possibly a small win; probably nothing significant. |
186 | */ |
187 | |
188 | #define IH_TABLE_HASH(obj, size) \ |
189 | ((mach_port_index_t)((((uintptr_t) (obj)) >> 6) % (size))) |
190 | |
191 | /* |
192 | * Routine: ipc_hash_table_lookup |
193 | * Purpose: |
194 | * Converts (table, obj) -> (name, entry). |
195 | * Conditions: |
196 | * Must have read consistency on the table. |
197 | */ |
198 | |
199 | boolean_t |
200 | ipc_hash_table_lookup( |
201 | ipc_entry_t table, |
202 | ipc_entry_num_t size, |
203 | ipc_object_t obj, |
204 | mach_port_name_t *namep, |
205 | ipc_entry_t *entryp) |
206 | { |
207 | mach_port_index_t hindex, index; |
208 | |
209 | if (obj == IO_NULL) { |
210 | return FALSE; |
211 | } |
212 | |
213 | hindex = IH_TABLE_HASH(obj, size); |
214 | |
215 | /* |
216 | * Ideally, table[hindex].ie_index is the name we want. |
217 | * However, must check ie_object to verify this, |
218 | * because collisions can happen. In case of a collision, |
219 | * search farther along in the clump. |
220 | */ |
221 | |
222 | while ((index = table[hindex].ie_index) != 0) { |
223 | ipc_entry_t entry; |
224 | |
225 | assert(index < size); |
226 | entry = &table[index]; |
227 | if (entry->ie_object == obj) { |
228 | *entryp = entry; |
229 | *namep = MACH_PORT_MAKE(index, |
230 | IE_BITS_GEN(entry->ie_bits)); |
231 | return TRUE; |
232 | } |
233 | |
234 | if (++hindex == size) |
235 | hindex = 0; |
236 | } |
237 | |
238 | return FALSE; |
239 | } |
240 | |
241 | /* |
242 | * Routine: ipc_hash_table_insert |
243 | * Purpose: |
244 | * Inserts an entry into the space's reverse hash table. |
245 | * Conditions: |
246 | * The space must be write-locked. |
247 | */ |
248 | |
249 | void |
250 | ipc_hash_table_insert( |
251 | ipc_entry_t table, |
252 | ipc_entry_num_t size, |
253 | ipc_object_t obj, |
254 | mach_port_index_t index, |
255 | __assert_only ipc_entry_t entry) |
256 | { |
257 | mach_port_index_t hindex; |
258 | |
259 | assert(index != 0); |
260 | assert(obj != IO_NULL); |
261 | |
262 | hindex = IH_TABLE_HASH(obj, size); |
263 | |
264 | assert(entry == &table[index]); |
265 | assert(entry->ie_object == obj); |
266 | |
267 | /* |
268 | * We want to insert at hindex, but there may be collisions. |
269 | * If a collision occurs, search for the end of the clump |
270 | * and insert there. |
271 | */ |
272 | |
273 | while (table[hindex].ie_index != 0) { |
274 | if (++hindex == size) |
275 | hindex = 0; |
276 | } |
277 | |
278 | table[hindex].ie_index = index; |
279 | } |
280 | |
281 | /* |
282 | * Routine: ipc_hash_table_delete |
283 | * Purpose: |
284 | * Deletes an entry from the table's reverse hash. |
285 | * Conditions: |
286 | * Exclusive access to the table. |
287 | */ |
288 | |
289 | void |
290 | ipc_hash_table_delete( |
291 | ipc_entry_t table, |
292 | ipc_entry_num_t size, |
293 | ipc_object_t obj, |
294 | mach_port_index_t index, |
295 | __assert_only ipc_entry_t entry) |
296 | { |
297 | mach_port_index_t hindex, dindex; |
298 | |
299 | assert(index != MACH_PORT_NULL); |
300 | assert(obj != IO_NULL); |
301 | |
302 | hindex = IH_TABLE_HASH(obj, size); |
303 | |
304 | assert(entry == &table[index]); |
305 | assert(entry->ie_object == obj); |
306 | |
307 | /* |
308 | * First check we have the right hindex for this index. |
309 | * In case of collision, we have to search farther |
310 | * along in this clump. |
311 | */ |
312 | |
313 | while (table[hindex].ie_index != index) { |
314 | if (++hindex == size) |
315 | hindex = 0; |
316 | } |
317 | |
318 | /* |
319 | * Now we want to set table[hindex].ie_index = 0. |
320 | * But if we aren't the last index in a clump, |
321 | * this might cause problems for lookups of objects |
322 | * farther along in the clump that are displaced |
323 | * due to collisions. Searches for them would fail |
324 | * at hindex instead of succeeding. |
325 | * |
326 | * So we must check the clump after hindex for objects |
327 | * that are so displaced, and move one up to the new hole. |
328 | * |
329 | * hindex - index of new hole in the clump |
330 | * dindex - index we are checking for a displaced object |
331 | * |
332 | * When we move a displaced object up into the hole, |
333 | * it creates a new hole, and we have to repeat the process |
334 | * until we get to the end of the clump. |
335 | */ |
336 | |
337 | for (dindex = hindex; index != 0; hindex = dindex) { |
338 | for (;;) { |
339 | mach_port_index_t tindex; |
340 | ipc_object_t tobj; |
341 | |
342 | if (++dindex == size) |
343 | dindex = 0; |
344 | assert(dindex != hindex); |
345 | |
346 | /* are we at the end of the clump? */ |
347 | |
348 | index = table[dindex].ie_index; |
349 | if (index == 0) |
350 | break; |
351 | |
352 | /* is this a displaced object? */ |
353 | |
354 | tobj = table[index].ie_object; |
355 | assert(tobj != IO_NULL); |
356 | tindex = IH_TABLE_HASH(tobj, size); |
357 | |
358 | if ((dindex < hindex) ? |
359 | ((dindex < tindex) && (tindex <= hindex)) : |
360 | ((dindex < tindex) || (tindex <= hindex))) |
361 | break; |
362 | } |
363 | |
364 | table[hindex].ie_index = index; |
365 | } |
366 | } |
367 | |
368 | |