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