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 */
90void 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
105boolean_t
106ipc_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
124void
125ipc_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
145void
146ipc_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
199boolean_t
200ipc_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
249void
250ipc_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
289void
290ipc_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