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 [email protected]
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 <ipc/port.h>
69 #include <ipc/ipc_space.h>
70 #include <ipc/ipc_object.h>
71 #include <ipc/ipc_entry.h>
72 #include <ipc/ipc_hash.h>
73 #include <ipc/ipc_init.h>
74 #include <os/hash.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
ipc_hash_lookup(ipc_space_t space,ipc_object_t obj,mach_port_name_t * namep,ipc_entry_t * entryp)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(is_active_table(space), 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
ipc_hash_insert(ipc_space_t space,ipc_object_t obj,mach_port_name_t name,ipc_entry_t entry)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 space->is_table_hashed++;
135 ipc_hash_table_insert(is_active_table(space), obj, index, entry);
136 }
137
138 /*
139 * Routine: ipc_hash_delete
140 * Purpose:
141 * Deletes an entry from the appropriate reverse hash table.
142 * Conditions:
143 * The space must be write-locked.
144 */
145
146 void
ipc_hash_delete(ipc_space_t space,ipc_object_t obj,mach_port_name_t name,ipc_entry_t entry)147 ipc_hash_delete(
148 ipc_space_t space,
149 ipc_object_t obj,
150 mach_port_name_t name,
151 ipc_entry_t entry)
152 {
153 mach_port_index_t index;
154
155 index = MACH_PORT_INDEX(name);
156 space->is_table_hashed--;
157 ipc_hash_table_delete(is_active_table(space), obj, index, entry);
158 }
159
160 /*
161 * Each space has a local reverse hash table, which holds
162 * entries from the space's table. In fact, the hash table
163 * just uses a field (ie_index) in the table itself.
164 *
165 * The local hash table is an open-addressing hash table,
166 * which means that when a collision occurs, instead of
167 * throwing the entry into a bucket, the entry is rehashed
168 * to another position in the table. In this case the rehash
169 * is very simple: linear probing (ie, just increment the position).
170 * This simple rehash makes deletions tractable (they're still a pain),
171 * but it means that collisions tend to build up into clumps.
172 *
173 * Because at least one entry in the table (index 0) is always unused,
174 * there will always be room in the reverse hash table. If a table
175 * with n slots gets completely full, the reverse hash table will
176 * have one giant clump of n-1 slots and one free slot somewhere.
177 * Because entries are only entered into the reverse table if they
178 * are pure send rights (not receive, send-once, port-set,
179 * or dead-name rights), and free entries of course aren't entered,
180 * I expect the reverse hash table won't get unreasonably full.
181 *
182 * Ordered hash tables (Amble & Knuth, Computer Journal, v. 17, no. 2,
183 * pp. 135-142.) may be desirable here. They can dramatically help
184 * unsuccessful lookups. But unsuccessful lookups are almost always
185 * followed by insertions, and those slow down somewhat. They
186 * also can help deletions somewhat. Successful lookups aren't affected.
187 * So possibly a small win; probably nothing significant.
188 */
189
190 #define IH_TABLE_HASH(obj, size) \
191 ((mach_port_index_t)(os_hash_kernel_pointer(obj) % (size)))
192
193 /*
194 * Routine: ipc_hash_table_lookup
195 * Purpose:
196 * Converts (table, obj) -> (name, entry).
197 * Conditions:
198 * Must have read consistency on the table.
199 */
200
201 boolean_t
ipc_hash_table_lookup(ipc_entry_t table,ipc_object_t obj,mach_port_name_t * namep,ipc_entry_t * entryp)202 ipc_hash_table_lookup(
203 ipc_entry_t table,
204 ipc_object_t obj,
205 mach_port_name_t *namep,
206 ipc_entry_t *entryp)
207 {
208 mach_port_index_t hindex, index, hdist;
209 ipc_entry_num_t size = table->ie_size;
210
211 if (obj == IO_NULL) {
212 return FALSE;
213 }
214
215 hindex = IH_TABLE_HASH(obj, size);
216 hdist = 0;
217
218 /*
219 * Ideally, table[hindex].ie_index is the name we want.
220 * However, must check ie_object to verify this,
221 * because collisions can happen. In case of a collision,
222 * search farther along in the clump.
223 */
224
225 while ((index = table[hindex].ie_index) != 0) {
226 ipc_entry_t entry = &table[index];
227
228 /*
229 * if our current displacement is strictly larger
230 * than the current slot one, then insertion would
231 * have stolen his place so we can't possibly exist.
232 */
233 if (hdist > table[hindex].ie_dist) {
234 return FALSE;
235 }
236
237 /*
238 * If our current displacement is exactly the current
239 * slot displacement, then it can be a match, let's check.
240 */
241 if (hdist == table[hindex].ie_dist) {
242 assert(index < size);
243 if (entry->ie_object == obj) {
244 *entryp = entry;
245 *namep = MACH_PORT_MAKE(index,
246 IE_BITS_GEN(entry->ie_bits));
247 return TRUE;
248 }
249 } else {
250 assert(entry->ie_object != obj);
251 }
252
253 if (hdist < IPC_ENTRY_DIST_MAX) {
254 /* peg the displacement distance at IPC_ENTRY_DIST_MAX */
255 ++hdist;
256 }
257 if (++hindex == size) {
258 hindex = 0;
259 }
260 }
261
262 return FALSE;
263 }
264
265 /*
266 * Routine: ipc_hash_table_insert
267 * Purpose:
268 * Inserts an entry into the space's reverse hash table.
269 * Conditions:
270 * The space must be write-locked.
271 */
272
273 void
ipc_hash_table_insert(ipc_entry_t table,ipc_object_t obj,mach_port_index_t index,__assert_only ipc_entry_t entry)274 ipc_hash_table_insert(
275 ipc_entry_t table,
276 ipc_object_t obj,
277 mach_port_index_t index,
278 __assert_only ipc_entry_t entry)
279 {
280 mach_port_index_t hindex, hdist;
281 ipc_entry_num_t size = table->ie_size;
282
283 assert(index != 0);
284 assert(obj != IO_NULL);
285
286 hindex = IH_TABLE_HASH(obj, size);
287 hdist = 0;
288
289 assert(entry == &table[index]);
290 assert(entry->ie_object == obj);
291
292 /*
293 * We want to insert at hindex, but there may be collisions.
294 * If a collision occurs, search for the end of the clump
295 * and insert there.
296 *
297 * However, Robin Hood steals from the rich, and as we go
298 * through the clump, if we go over an item that is less
299 * displaced than we'd be, we steal his slot and
300 * keep inserting him in our stead.
301 */
302 while (table[hindex].ie_index != 0) {
303 if (table[hindex].ie_dist < hdist) {
304 #define swap(a, b) ({ typeof(a) _tmp = (b); (b) = (a); (a) = _tmp; })
305 swap(hdist, table[hindex].ie_dist);
306 swap(index, table[hindex].ie_index);
307 #undef swap
308 }
309 if (hdist < IPC_ENTRY_DIST_MAX) {
310 /* peg the displacement distance at IPC_ENTRY_DIST_MAX */
311 ++hdist;
312 }
313 if (++hindex == size) {
314 hindex = 0;
315 }
316 }
317
318 table[hindex].ie_index = index;
319 table[hindex].ie_dist = hdist;
320 }
321
322 /*
323 * Routine: ipc_hash_table_delete
324 * Purpose:
325 * Deletes an entry from the table's reverse hash.
326 * Conditions:
327 * Exclusive access to the table.
328 */
329
330 void
ipc_hash_table_delete(ipc_entry_t table,ipc_object_t obj,mach_port_index_t index,__assert_only ipc_entry_t entry)331 ipc_hash_table_delete(
332 ipc_entry_t table,
333 ipc_object_t obj,
334 mach_port_index_t index,
335 __assert_only ipc_entry_t entry)
336 {
337 mach_port_index_t hindex, dindex, dist;
338 ipc_entry_num_t size = table->ie_size;
339
340 assert(index != MACH_PORT_NULL);
341 assert(obj != IO_NULL);
342
343 hindex = IH_TABLE_HASH(obj, size);
344
345 assert(entry == &table[index]);
346 assert(entry->ie_object == obj);
347
348 /*
349 * First check we have the right hindex for this index.
350 * In case of collision, we have to search farther
351 * along in this clump.
352 */
353
354 while (table[hindex].ie_index != index) {
355 if (++hindex == size) {
356 hindex = 0;
357 }
358 }
359
360 /*
361 * Now we want to set table[hindex].ie_index = 0.
362 * But if we aren't the last index in a clump,
363 * this might cause problems for lookups of objects
364 * farther along in the clump that are displaced
365 * due to collisions. Searches for them would fail
366 * at hindex instead of succeeding.
367 *
368 * So we must check the clump after hindex for objects
369 * that are so displaced, and move one up to the new hole.
370 *
371 * hindex - index of new hole in the clump
372 * dindex - index we are checking for a displaced object
373 *
374 * When we move a displaced object up into the hole,
375 * it creates a new hole, and we have to repeat the process
376 * until we get to the end of the clump.
377 */
378
379 for (;;) {
380 dindex = hindex + 1;
381 if (dindex == size) {
382 dindex = 0;
383 }
384
385 /*
386 * If the next element is empty or isn't displaced,
387 * then lookup will end on the next element anyway,
388 * so we can leave the hole right here, we're done
389 */
390 index = table[dindex].ie_index;
391 dist = table[dindex].ie_dist;
392 if (index == 0 || dist == 0) {
393 table[hindex].ie_index = 0;
394 table[hindex].ie_dist = 0;
395 return;
396 }
397
398 /*
399 * Move this object closer to its own slot by occupying the hole.
400 * If its displacement was pegged, recompute it.
401 */
402 if (dist-- == IPC_ENTRY_DIST_MAX) {
403 uint32_t desired = IH_TABLE_HASH(table[index].ie_object, size);
404 if (hindex >= desired) {
405 dist = hindex - desired;
406 } else {
407 dist = hindex + size - desired;
408 }
409 if (dist > IPC_ENTRY_DIST_MAX) {
410 dist = IPC_ENTRY_DIST_MAX;
411 }
412 }
413
414 /*
415 * Move the displaced element closer to its ideal bucket,
416 * and keep shifting elements back.
417 */
418 table[hindex].ie_index = index;
419 table[hindex].ie_dist = dist;
420 hindex = dindex;
421 }
422 }
423