1 /*
2 * Copyright 1991-1998 by Open Software Foundation, Inc.
3 * All Rights Reserved
4 *
5 * Permission to use, copy, modify, and distribute this software and
6 * its documentation for any purpose and without fee is hereby granted,
7 * provided that the above copyright notice appears in all copies and
8 * that both the copyright notice and this permission notice appear in
9 * supporting documentation.
10 *
11 * OSF DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE
12 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
13 * FOR A PARTICULAR PURPOSE.
14 *
15 * IN NO EVENT SHALL OSF BE LIABLE FOR ANY SPECIAL, INDIRECT, OR
16 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
17 * LOSS OF USE, DATA OR PROFITS, WHETHER IN ACTION OF CONTRACT,
18 * NEGLIGENCE, OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
19 * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20 */
21 /*
22 * MkLinux
23 */
24 /* CMU_HIST */
25 /*
26 * Revision 2.5.3.1 92/03/03 16:18:21 jeffreyh
27 * Changes from TRUNK
28 * [92/02/26 11:40:47 jeffreyh]
29 *
30 * Revision 2.6 92/01/14 16:44:15 rpd
31 * Changed ipc_hash_info for CountInOut.
32 * [92/01/14 rpd]
33 *
34 * Revision 2.5 91/05/14 16:32:08 mrt
35 * Correcting copyright
36 *
37 * Revision 2.4 91/02/05 17:21:29 mrt
38 * Changed to new Mach copyright
39 * [91/02/01 15:44:42 mrt]
40 *
41 * Revision 2.3 91/01/08 15:13:20 rpd
42 * Changed ipc_info_bucket_t to hash_info_bucket_t.
43 * [91/01/02 rpd]
44 *
45 * Revision 2.2 90/06/02 14:49:47 rpd
46 * Created for new IPC.
47 * [90/03/26 20:54:50 rpd]
48 *
49 */
50 /* CMU_ENDHIST */
51 /*
52 * Mach Operating System
53 * Copyright (c) 1991,1990,1989 Carnegie Mellon University
54 * All Rights Reserved.
55 *
56 * Permission to use, copy, modify and distribute this software and its
57 * documentation is hereby granted, provided that both the copyright
58 * notice and this permission notice appear in all copies of the
59 * software, derivative works or modified versions, and any portions
60 * thereof, and that both notices appear in supporting documentation.
61 *
62 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
63 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
64 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
65 *
66 * Carnegie Mellon requests users of this software to return to
67 *
68 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
69 * School of Computer Science
70 * Carnegie Mellon University
71 * Pittsburgh PA 15213-3890
72 *
73 * any improvements or extensions that they make and grant Carnegie Mellon
74 * the rights to redistribute these changes.
75 */
76 /*
77 */
78 /*
79 * File: ipc/ipc_hash.c
80 * Author: Rich Draves
81 * Date: 1989
82 *
83 * Entry hash table operations.
84 */
85 #include <sys/mach/mach_types.h>
86 #include <sys/mach/port.h>
87 #include <sys/mach/ipc/port.h>
88 #include <sys/mach/ipc/ipc_space.h>
89 #include <sys/mach/ipc/ipc_object.h>
90 #include <sys/mach/ipc/ipc_entry.h>
91 #include <sys/mach/ipc/ipc_hash.h>
92 #include <sys/mach/ipc/ipc_init.h>
93 #if 0
94 #include <mach_ipc_debug.h>
95 #endif
96 #if MACH_IPC_DEBUG
97 #include <mach/kern_return.h>
98 #include <mach_debug/hash_info.h>
99 #include <vm/vm_map.h>
100 #include <vm/vm_kern.h>
101 #include <vm/vm_user.h>
102 #endif /* MACH_IPC_DEBUG */
103
104 /*
105 * Forward declarations
106 */
107 /* Lookup (space, obj) in local hash table */
108 boolean_t ipc_hash_local_lookup(
109 ipc_space_t space,
110 ipc_object_t obj,
111 mach_port_name_t *namep,
112 ipc_entry_t *entryp);
113
114
115
116 /* Insert an entry into the global reverse hash table */
117 void ipc_hash_local_insert(
118 ipc_space_t space,
119 ipc_object_t obj,
120 mach_port_name_t name,
121 ipc_entry_t entry);
122
123 /* Delete an entry from the local reverse hash table */
124 void ipc_hash_local_delete(
125 ipc_space_t space,
126 ipc_object_t obj,
127 mach_port_index_t index,
128 ipc_entry_t entry);
129
130 /*
131 * Routine: ipc_hash_lookup
132 * Purpose:
133 * Converts (space, obj) -> (name, entry).
134 * Returns TRUE if an entry was found.
135 * Conditions:
136 * The space must be locked (read or write) throughout.
137 */
138
139 boolean_t
ipc_hash_lookup(ipc_space_t space,ipc_object_t obj,mach_port_name_t * namep,ipc_entry_t * entryp)140 ipc_hash_lookup(
141 ipc_space_t space,
142 ipc_object_t obj,
143 mach_port_name_t *namep,
144 ipc_entry_t *entryp)
145 {
146 boolean_t rv;
147
148 rv = ipc_hash_local_lookup(space, obj, namep, entryp);
149 return (rv);
150 }
151
152 /*
153 * Routine: ipc_hash_insert
154 * Purpose:
155 * Inserts an entry into the appropriate reverse hash table,
156 * so that ipc_hash_lookup will find it.
157 * Conditions:
158 * The space must be write-locked.
159 */
160
161 void
ipc_hash_insert(ipc_space_t space,ipc_object_t obj,mach_port_name_t name,ipc_entry_t entry)162 ipc_hash_insert(
163 ipc_space_t space,
164 ipc_object_t obj,
165 mach_port_name_t name,
166 ipc_entry_t entry)
167 {
168
169 ipc_hash_local_insert(space, obj, name, entry);
170 }
171
172 /*
173 * Routine: ipc_hash_delete
174 * Purpose:
175 * Deletes an entry from the appropriate reverse hash table.
176 * Conditions:
177 * The space must be write-locked.
178 */
179
180 void
ipc_hash_delete(ipc_space_t space,ipc_object_t obj,mach_port_name_t name,ipc_entry_t entry)181 ipc_hash_delete(
182 ipc_space_t space,
183 ipc_object_t obj,
184 mach_port_name_t name,
185 ipc_entry_t entry)
186 {
187
188 ipc_hash_local_delete(space, obj, name, entry);
189 }
190
191 /*
192 * The global reverse hash table holds splay tree entries.
193 * It is a simple open-chaining hash table with singly-linked buckets.
194 * Each bucket is locked separately, with an exclusive lock.
195 * Within each bucket, move-to-front is used.
196 */
197
198 typedef natural_t ipc_hash_index_t;
199
200
201 /*
202 * Each space has a local reverse hash table, which holds
203 * entries from the space's table. In fact, the hash table
204 * just uses a field (ie_index) in the table itself.
205 *
206 * The local hash table is an open-addressing hash table,
207 * which means that when a collision occurs, instead of
208 * throwing the entry into a bucket, the entry is rehashed
209 * to another position in the table. In this case the rehash
210 * is very simple: linear probing (ie, just increment the position).
211 * This simple rehash makes deletions tractable (they're still a pain),
212 * but it means that collisions tend to build up into clumps.
213 *
214 * Because at least one entry in the table (index 0) is always unused,
215 * there will always be room in the reverse hash table. If a table
216 * with n slots gets completely full, the reverse hash table will
217 * have one giant clump of n-1 slots and one free slot somewhere.
218 * Because entries are only entered into the reverse table if they
219 * are pure send rights (not receive, send-once, port-set,
220 * or dead-name rights), and free entries of course aren't entered,
221 * I expect the reverse hash table won't get unreasonably full.
222 *
223 * Ordered hash tables (Amble & Knuth, Computer Journal, v. 17, no. 2,
224 * pp. 135-142.) may be desirable here. They can dramatically help
225 * unsuccessful lookups. But unsuccessful lookups are almost always
226 * followed by insertions, and those slow down somewhat. They
227 * also can help deletions somewhat. Successful lookups aren't affected.
228 * So possibly a small win; probably nothing significant.
229 */
230
231 #define IH_LOCAL_HASH(obj, size) \
232 ((((mach_port_index_t) (obj)) >> 6) % (size))
233
234 /*
235 * Routine: ipc_hash_local_lookup
236 * Purpose:
237 * Converts (space, obj) -> (name, entry).
238 * Looks in the space's local table, for table entries.
239 * Returns TRUE if an entry was found.
240 * Conditions:
241 * The space must be locked (read or write) throughout.
242 */
243
244 boolean_t
ipc_hash_local_lookup(ipc_space_t space,ipc_object_t obj,mach_port_name_t * namep,ipc_entry_t * entryp)245 ipc_hash_local_lookup(
246 ipc_space_t space,
247 ipc_object_t obj,
248 mach_port_name_t *namep,
249 ipc_entry_t *entryp)
250 {
251 ipc_entry_t *table, entry;
252 ipc_entry_num_t size;
253 mach_port_index_t hindex;
254
255 assert(space != IS_NULL);
256 assert(obj != IO_NULL);
257
258 table = space->is_table;
259 size = space->is_table_size;
260 hindex = IH_LOCAL_HASH(obj, size);
261
262 entry = table[hindex];
263 while (entry != NULL) {
264 if (entry->ie_object == obj) {
265 *namep = entry->ie_name;
266 *entryp = entry;
267 return TRUE;
268 }
269
270 entry = entry->ie_link;
271 }
272
273 return FALSE;
274 }
275
276 /*
277 * Routine: ipc_hash_local_insert
278 * Purpose:
279 * Inserts an entry into the space's reverse hash table.
280 * Conditions:
281 * The space must be write-locked.
282 */
283
284 void
ipc_hash_local_insert(ipc_space_t space,ipc_object_t obj,mach_port_index_t index __unused,ipc_entry_t entry)285 ipc_hash_local_insert(
286 ipc_space_t space,
287 ipc_object_t obj,
288 mach_port_index_t index __unused,
289 ipc_entry_t entry)
290 {
291 ipc_entry_t *table, entryp;
292 ipc_entry_num_t size;
293 mach_port_index_t hindex;
294
295 assert(space != IS_NULL);
296 assert(obj != IO_NULL);
297
298 table = space->is_table;
299 size = space->is_table_size;
300 hindex = IH_LOCAL_HASH(obj, size);
301
302 assert(entry->ie_object == obj);
303
304 if ((entryp = table[hindex]) != NULL)
305 entry->ie_link = entryp;
306
307 table[hindex] = entry;
308 entry->ie_index = hindex;
309 }
310
311 /*
312 * Routine: ipc_hash_local_delete
313 * Purpose:
314 * Deletes an entry from the space's reverse hash table.
315 * Conditions:
316 * The space must be write-locked.
317 */
318
319 void
ipc_hash_local_delete(ipc_space_t space,ipc_object_t obj,mach_port_index_t index __unused,ipc_entry_t entry)320 ipc_hash_local_delete(
321 ipc_space_t space,
322 ipc_object_t obj,
323 mach_port_index_t index __unused,
324 ipc_entry_t entry)
325 {
326 ipc_entry_t *table, entryp;
327 ipc_entry_num_t size;
328 mach_port_index_t hindex;
329
330 assert(index != MACH_PORT_NAME_NULL);
331 assert(space != IS_NULL);
332 assert(obj != IO_NULL);
333
334 table = space->is_table;
335 size = space->is_table_size;
336 hindex = IH_LOCAL_HASH(obj, size);
337
338 assert(entry->ie_object == obj);
339
340 if ((entryp = table[hindex]) == entry) {
341 table[hindex] = entry->ie_link;
342 return;
343 }
344 while (entryp->ie_link != NULL) {
345 if (entryp->ie_link == entry) {
346 entryp->ie_link = entry->ie_link;
347 break;
348 }
349 entryp = entryp->ie_link;
350 }
351 }
352
353 /*
354 * Routine: ipc_hash_init
355 * Purpose:
356 * Initialize the global reverse hash table implementation.
357 */
358
359 void
ipc_hash_init(void)360 ipc_hash_init(void)
361 {
362 }
363
364 #if MACH_IPC_DEBUG
365
366 /*
367 * Routine: ipc_hash_info
368 * Purpose:
369 * Return information about the global reverse hash table.
370 * Fills the buffer with as much information as possible
371 * and returns the desired size of the buffer.
372 * Conditions:
373 * Nothing locked. The caller should provide
374 * possibly-pageable memory.
375 */
376
377
378 ipc_hash_index_t
ipc_hash_info(hash_info_bucket_t * info,mach_msg_type_number_t count)379 ipc_hash_info(
380 hash_info_bucket_t *info,
381 mach_msg_type_number_t count)
382 {
383 ipc_hash_index_t i;
384
385 if (ipc_hash_global_size < count)
386 count = ipc_hash_global_size;
387
388 for (i = 0; i < count; i++) {
389 ipc_hash_global_bucket_t bucket = &ipc_hash_global_table[i];
390 unsigned int bucket_count = 0;
391 ipc_tree_entry_t entry;
392
393 ihgb_lock(bucket);
394 for (entry = bucket->ihgb_head;
395 entry != ITE_NULL;
396 entry = entry->ite_next)
397 bucket_count++;
398 ihgb_unlock(bucket);
399
400 /* don't touch pageable memory while holding locks */
401 info[i].hib_count = bucket_count;
402 }
403
404 return ipc_hash_global_size;
405 }
406
407 #endif /* MACH_IPC_DEBUG */
408