![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to ipc_hash.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / XNU / osfmk / ipc|
Return to ipc_hash.c CVS log | Up to [Apple XNU] / XNU / osfmk / ipc |
1.1 root 1: /*
2: * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * The contents of this file constitute Original Code as defined in and
7: * are subject to the Apple Public Source License Version 1.1 (the
8: * "License"). You may not use this file except in compliance with the
9: * License. Please obtain a copy of the License at
10: * http://www.apple.com/publicsource and read it before using this file.
11: *
12: * This Original Code and all software distributed under the License are
13: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
14: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
15: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
16: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
17: * License for the specific language governing rights and limitations
18: * under the License.
19: *
20: * @APPLE_LICENSE_HEADER_END@
21: */
22: /*
23: * @OSF_COPYRIGHT@
24: */
25: /*
26: * Mach Operating System
27: * Copyright (c) 1991,1990,1989 Carnegie Mellon University
28: * All Rights Reserved.
29: *
30: * Permission to use, copy, modify and distribute this software and its
31: * documentation is hereby granted, provided that both the copyright
32: * notice and this permission notice appear in all copies of the
33: * software, derivative works or modified versions, and any portions
34: * thereof, and that both notices appear in supporting documentation.
35: *
36: * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
37: * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
38: * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
39: *
40: * Carnegie Mellon requests users of this software to return to
41: *
42: * Software Distribution Coordinator or [email protected]
43: * School of Computer Science
44: * Carnegie Mellon University
45: * Pittsburgh PA 15213-3890
46: *
47: * any improvements or extensions that they make and grant Carnegie Mellon
48: * the rights to redistribute these changes.
49: */
50: /*
51: */
52: /*
53: * File: ipc/ipc_hash.c
54: * Author: Rich Draves
55: * Date: 1989
56: *
57: * Entry hash table operations.
58: */
59:
60: #include <mach/boolean.h>
61: #include <mach/port.h>
62: #include <kern/lock.h>
63: #include <kern/kalloc.h>
64: #include <ipc/port.h>
65: #include <ipc/ipc_space.h>
66: #include <ipc/ipc_object.h>
67: #include <ipc/ipc_entry.h>
68: #include <ipc/ipc_hash.h>
69: #include <ipc/ipc_init.h>
70:
71: #include <mach_ipc_debug.h>
72:
73: #if MACH_IPC_DEBUG
74: #include <mach/kern_return.h>
75: #include <mach_debug/hash_info.h>
76: #include <vm/vm_map.h>
77: #include <vm/vm_kern.h>
78: #include <vm/vm_user.h>
79: #endif /* MACH_IPC_DEBUG */
80:
81: /*
82: * Forward declarations
83: */
84:
85: /* Lookup (space, obj) in global hash table */
86: boolean_t ipc_hash_global_lookup(
87: ipc_space_t space,
88: ipc_object_t obj,
89: mach_port_name_t *namep,
90: ipc_tree_entry_t *entryp);
91:
92: /* Insert an entry into the global reverse hash table */
93: void ipc_hash_global_insert(
94: ipc_space_t space,
95: ipc_object_t obj,
96: mach_port_name_t name,
97: ipc_tree_entry_t entry);
98:
99: /* Delete an entry from the local reverse hash table */
100: void ipc_hash_local_delete(
101: ipc_space_t space,
102: ipc_object_t obj,
103: mach_port_index_t index,
104: ipc_entry_t entry);
105:
106: /*
107: * Routine: ipc_hash_lookup
108: * Purpose:
109: * Converts (space, obj) -> (name, entry).
110: * Returns TRUE if an entry was found.
111: * Conditions:
112: * The space must be locked (read or write) throughout.
113: */
114:
115: boolean_t
116: ipc_hash_lookup(
117: ipc_space_t space,
118: ipc_object_t obj,
119: mach_port_name_t *namep,
120: ipc_entry_t *entryp)
121: {
122: boolean_t rv;
123:
124: rv = ipc_hash_local_lookup(space, obj, namep, entryp);
125: if (!rv) {
126: assert(!is_fast_space(space) || space->is_tree_hash == 0);
127: if (space->is_tree_hash > 0)
128: rv = ipc_hash_global_lookup(space, obj, namep,
129: (ipc_tree_entry_t *) entryp);
130: }
131: return (rv);
132: }
133:
134: /*
135: * Routine: ipc_hash_insert
136: * Purpose:
137: * Inserts an entry into the appropriate reverse hash table,
138: * so that ipc_hash_lookup will find it.
139: * Conditions:
140: * The space must be write-locked.
141: */
142:
143: void
144: ipc_hash_insert(
145: ipc_space_t space,
146: ipc_object_t obj,
147: mach_port_name_t name,
148: ipc_entry_t entry)
149: {
150: mach_port_index_t index;
151:
152: index = MACH_PORT_INDEX(name);
153: if ((index < space->is_table_size) &&
154: (entry == &space->is_table[index]))
155: ipc_hash_local_insert(space, obj, index, entry);
156: else {
157: assert(!is_fast_space(space));
158: ipc_hash_global_insert(space, obj, name,
159: (ipc_tree_entry_t) entry);
160: }
161: }
162:
163: /*
164: * Routine: ipc_hash_delete
165: * Purpose:
166: * Deletes an entry from the appropriate reverse hash table.
167: * Conditions:
168: * The space must be write-locked.
169: */
170:
171: void
172: ipc_hash_delete(
173: ipc_space_t space,
174: ipc_object_t obj,
175: mach_port_name_t name,
176: ipc_entry_t entry)
177: {
178: mach_port_index_t index;
179:
180: index = MACH_PORT_INDEX(name);
181: if ((index < space->is_table_size) &&
182: (entry == &space->is_table[index]))
183: ipc_hash_local_delete(space, obj, index, entry);
184: else {
185: assert(!is_fast_space(space));
186: ipc_hash_global_delete(space, obj, name,
187: (ipc_tree_entry_t) entry);
188: }
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: ipc_hash_index_t ipc_hash_global_size;
201: ipc_hash_index_t ipc_hash_global_mask;
202:
203: #define IH_GLOBAL_HASH(space, obj) \
204: (((((ipc_hash_index_t) ((vm_offset_t)space)) >> 4) + \
205: (((ipc_hash_index_t) ((vm_offset_t)obj)) >> 6)) & \
206: ipc_hash_global_mask)
207:
208: typedef struct ipc_hash_global_bucket {
209: decl_mutex_data(, ihgb_lock_data)
210: ipc_tree_entry_t ihgb_head;
211: } *ipc_hash_global_bucket_t;
212:
213: #define IHGB_NULL ((ipc_hash_global_bucket_t) 0)
214:
215: #define ihgb_lock_init(ihgb) mutex_init(&(ihgb)->ihgb_lock_data, \
216: ETAP_IPC_IHGB)
217: #define ihgb_lock(ihgb) mutex_lock(&(ihgb)->ihgb_lock_data)
218: #define ihgb_unlock(ihgb) mutex_unlock(&(ihgb)->ihgb_lock_data)
219:
220: ipc_hash_global_bucket_t ipc_hash_global_table;
221:
222: /*
223: * Routine: ipc_hash_global_lookup
224: * Purpose:
225: * Converts (space, obj) -> (name, entry).
226: * Looks in the global table, for splay tree entries.
227: * Returns TRUE if an entry was found.
228: * Conditions:
229: * The space must be locked (read or write) throughout.
230: */
231:
232: boolean_t
233: ipc_hash_global_lookup(
234: ipc_space_t space,
235: ipc_object_t obj,
236: mach_port_name_t *namep,
237: ipc_tree_entry_t *entryp)
238: {
239: ipc_hash_global_bucket_t bucket;
240: ipc_tree_entry_t this, *last;
241:
242: assert(space != IS_NULL);
243: assert(obj != IO_NULL);
244:
245: assert(!is_fast_space(space));
246: bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)];
247: ihgb_lock(bucket);
248:
249: if ((this = bucket->ihgb_head) != ITE_NULL) {
250: if ((this->ite_object == obj) &&
251: (this->ite_space == space)) {
252: /* found it at front; no need to move */
253:
254: *namep = this->ite_name;
255: *entryp = this;
256: } else for (last = &this->ite_next;
257: (this = *last) != ITE_NULL;
258: last = &this->ite_next) {
259: if ((this->ite_object == obj) &&
260: (this->ite_space == space)) {
261: /* found it; move to front */
262:
263: *last = this->ite_next;
264: this->ite_next = bucket->ihgb_head;
265: bucket->ihgb_head = this;
266:
267: *namep = this->ite_name;
268: *entryp = this;
269: break;
270: }
271: }
272: }
273:
274: ihgb_unlock(bucket);
275: return this != ITE_NULL;
276: }
277:
278: /*
279: * Routine: ipc_hash_global_insert
280: * Purpose:
281: * Inserts an entry into the global reverse hash table.
282: * Conditions:
283: * The space must be write-locked.
284: */
285:
286: void
287: ipc_hash_global_insert(
288: ipc_space_t space,
289: ipc_object_t obj,
290: mach_port_name_t name,
291: ipc_tree_entry_t entry)
292: {
293: ipc_hash_global_bucket_t bucket;
294:
295:
296: assert(!is_fast_space(space));
297:
298:
299: assert(entry->ite_name == name);
300: assert(space != IS_NULL);
301: assert(entry->ite_space == space);
302: assert(obj != IO_NULL);
303: assert(entry->ite_object == obj);
304:
305: space->is_tree_hash++;
306: assert(space->is_tree_hash <= space->is_tree_total);
307:
308: bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)];
309: ihgb_lock(bucket);
310:
311: /* insert at front of bucket */
312:
313: entry->ite_next = bucket->ihgb_head;
314: bucket->ihgb_head = entry;
315:
316: ihgb_unlock(bucket);
317: }
318:
319: /*
320: * Routine: ipc_hash_global_delete
321: * Purpose:
322: * Deletes an entry from the global reverse hash table.
323: * Conditions:
324: * The space must be write-locked.
325: */
326:
327: void
328: ipc_hash_global_delete(
329: ipc_space_t space,
330: ipc_object_t obj,
331: mach_port_name_t name,
332: ipc_tree_entry_t entry)
333: {
334: ipc_hash_global_bucket_t bucket;
335: ipc_tree_entry_t this, *last;
336:
337: assert(!is_fast_space(space));
338:
339: assert(entry->ite_name == name);
340: assert(space != IS_NULL);
341: assert(entry->ite_space == space);
342: assert(obj != IO_NULL);
343: assert(entry->ite_object == obj);
344:
345: assert(space->is_tree_hash > 0);
346: space->is_tree_hash--;
347:
348: bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)];
349: ihgb_lock(bucket);
350:
351: for (last = &bucket->ihgb_head;
352: (this = *last) != ITE_NULL;
353: last = &this->ite_next) {
354: if (this == entry) {
355: /* found it; remove from bucket */
356:
357: *last = this->ite_next;
358: break;
359: }
360: }
361: assert(this != ITE_NULL);
362:
363: ihgb_unlock(bucket);
364: }
365:
366: /*
367: * Each space has a local reverse hash table, which holds
368: * entries from the space's table. In fact, the hash table
369: * just uses a field (ie_index) in the table itself.
370: *
371: * The local hash table is an open-addressing hash table,
372: * which means that when a collision occurs, instead of
373: * throwing the entry into a bucket, the entry is rehashed
374: * to another position in the table. In this case the rehash
375: * is very simple: linear probing (ie, just increment the position).
376: * This simple rehash makes deletions tractable (they're still a pain),
377: * but it means that collisions tend to build up into clumps.
378: *
379: * Because at least one entry in the table (index 0) is always unused,
380: * there will always be room in the reverse hash table. If a table
381: * with n slots gets completely full, the reverse hash table will
382: * have one giant clump of n-1 slots and one free slot somewhere.
383: * Because entries are only entered into the reverse table if they
384: * are pure send rights (not receive, send-once, port-set,
385: * or dead-name rights), and free entries of course aren't entered,
386: * I expect the reverse hash table won't get unreasonably full.
387: *
388: * Ordered hash tables (Amble & Knuth, Computer Journal, v. 17, no. 2,
389: * pp. 135-142.) may be desirable here. They can dramatically help
390: * unsuccessful lookups. But unsuccessful lookups are almost always
391: * followed by insertions, and those slow down somewhat. They
392: * also can help deletions somewhat. Successful lookups aren't affected.
393: * So possibly a small win; probably nothing significant.
394: */
395:
396: #define IH_LOCAL_HASH(obj, size) \
397: ((((mach_port_index_t) (obj)) >> 6) % (size))
398:
399: /*
400: * Routine: ipc_hash_local_lookup
401: * Purpose:
402: * Converts (space, obj) -> (name, entry).
403: * Looks in the space's local table, for table entries.
404: * Returns TRUE if an entry was found.
405: * Conditions:
406: * The space must be locked (read or write) throughout.
407: */
408:
409: boolean_t
410: ipc_hash_local_lookup(
411: ipc_space_t space,
412: ipc_object_t obj,
413: mach_port_name_t *namep,
414: ipc_entry_t *entryp)
415: {
416: ipc_entry_t table;
417: ipc_entry_num_t size;
418: mach_port_index_t hindex, index;
419:
420: assert(space != IS_NULL);
421: assert(obj != IO_NULL);
422:
423: table = space->is_table;
424: size = space->is_table_size;
425: hindex = IH_LOCAL_HASH(obj, size);
426:
427: /*
428: * Ideally, table[hindex].ie_index is the name we want.
429: * However, must check ie_object to verify this,
430: * because collisions can happen. In case of a collision,
431: * search farther along in the clump.
432: */
433:
434: while ((index = table[hindex].ie_index) != 0) {
435: ipc_entry_t entry = &table[index];
436:
437: if (entry->ie_object == obj) {
438: *entryp = entry;
439: *namep = MACH_PORT_MAKE(index,
440: IE_BITS_GEN(entry->ie_bits));
441: return TRUE;
442: }
443:
444: if (++hindex == size)
445: hindex = 0;
446: }
447:
448: return FALSE;
449: }
450:
451: /*
452: * Routine: ipc_hash_local_insert
453: * Purpose:
454: * Inserts an entry into the space's reverse hash table.
455: * Conditions:
456: * The space must be write-locked.
457: */
458:
459: void
460: ipc_hash_local_insert(
461: ipc_space_t space,
462: ipc_object_t obj,
463: mach_port_index_t index,
464: ipc_entry_t entry)
465: {
466: ipc_entry_t table;
467: ipc_entry_num_t size;
468: mach_port_index_t hindex;
469:
470: assert(index != 0);
471: assert(space != IS_NULL);
472: assert(obj != IO_NULL);
473:
474: table = space->is_table;
475: size = space->is_table_size;
476: hindex = IH_LOCAL_HASH(obj, size);
477:
478: assert(entry == &table[index]);
479: assert(entry->ie_object == obj);
480:
481: /*
482: * We want to insert at hindex, but there may be collisions.
483: * If a collision occurs, search for the end of the clump
484: * and insert there.
485: */
486:
487: while (table[hindex].ie_index != 0) {
488: if (++hindex == size)
489: hindex = 0;
490: }
491:
492: table[hindex].ie_index = index;
493: }
494:
495: /*
496: * Routine: ipc_hash_local_delete
497: * Purpose:
498: * Deletes an entry from the space's reverse hash table.
499: * Conditions:
500: * The space must be write-locked.
501: */
502:
503: void
504: ipc_hash_local_delete(
505: ipc_space_t space,
506: ipc_object_t obj,
507: mach_port_index_t index,
508: ipc_entry_t entry)
509: {
510: ipc_entry_t table;
511: ipc_entry_num_t size;
512: mach_port_index_t hindex, dindex;
513:
514: assert(index != MACH_PORT_NULL);
515: assert(space != IS_NULL);
516: assert(obj != IO_NULL);
517:
518: table = space->is_table;
519: size = space->is_table_size;
520: hindex = IH_LOCAL_HASH(obj, size);
521:
522: assert(entry == &table[index]);
523: assert(entry->ie_object == obj);
524:
525: /*
526: * First check we have the right hindex for this index.
527: * In case of collision, we have to search farther
528: * along in this clump.
529: */
530:
531: while (table[hindex].ie_index != index) {
532: if (++hindex == size)
533: hindex = 0;
534: }
535:
536: /*
537: * Now we want to set table[hindex].ie_index = 0.
538: * But if we aren't the last index in a clump,
539: * this might cause problems for lookups of objects
540: * farther along in the clump that are displaced
541: * due to collisions. Searches for them would fail
542: * at hindex instead of succeeding.
543: *
544: * So we must check the clump after hindex for objects
545: * that are so displaced, and move one up to the new hole.
546: *
547: * hindex - index of new hole in the clump
548: * dindex - index we are checking for a displaced object
549: *
550: * When we move a displaced object up into the hole,
551: * it creates a new hole, and we have to repeat the process
552: * until we get to the end of the clump.
553: */
554:
555: for (dindex = hindex; index != 0; hindex = dindex) {
556: for (;;) {
557: mach_port_index_t tindex;
558: ipc_object_t tobj;
559:
560: if (++dindex == size)
561: dindex = 0;
562: assert(dindex != hindex);
563:
564: /* are we at the end of the clump? */
565:
566: index = table[dindex].ie_index;
567: if (index == 0)
568: break;
569:
570: /* is this a displaced object? */
571:
572: tobj = table[index].ie_object;
573: assert(tobj != IO_NULL);
574: tindex = IH_LOCAL_HASH(tobj, size);
575:
576: if ((dindex < hindex) ?
577: ((dindex < tindex) && (tindex <= hindex)) :
578: ((dindex < tindex) || (tindex <= hindex)))
579: break;
580: }
581:
582: table[hindex].ie_index = index;
583: }
584: }
585:
586: /*
587: * Routine: ipc_hash_init
588: * Purpose:
589: * Initialize the reverse hash table implementation.
590: */
591:
592: void
593: ipc_hash_init(void)
594: {
595: ipc_hash_index_t i;
596:
597: /* if not configured, initialize ipc_hash_global_size */
598:
599: if (ipc_hash_global_size == 0) {
600: ipc_hash_global_size = ipc_tree_entry_max >> 8;
601: if (ipc_hash_global_size < 32)
602: ipc_hash_global_size = 32;
603: }
604:
605: /* make sure it is a power of two */
606:
607: ipc_hash_global_mask = ipc_hash_global_size - 1;
608: if ((ipc_hash_global_size & ipc_hash_global_mask) != 0) {
609: natural_t bit;
610:
611: /* round up to closest power of two */
612:
613: for (bit = 1;; bit <<= 1) {
614: ipc_hash_global_mask |= bit;
615: ipc_hash_global_size = ipc_hash_global_mask + 1;
616:
617: if ((ipc_hash_global_size & ipc_hash_global_mask) == 0)
618: break;
619: }
620: }
621:
622: /* allocate ipc_hash_global_table */
623:
624: ipc_hash_global_table = (ipc_hash_global_bucket_t)
625: kalloc((vm_size_t) (ipc_hash_global_size *
626: sizeof(struct ipc_hash_global_bucket)));
627: assert(ipc_hash_global_table != IHGB_NULL);
628:
629: /* and initialize it */
630:
631: for (i = 0; i < ipc_hash_global_size; i++) {
632: ipc_hash_global_bucket_t bucket;
633:
634: bucket = &ipc_hash_global_table[i];
635: ihgb_lock_init(bucket);
636: bucket->ihgb_head = ITE_NULL;
637: }
638: }
639:
640: #if MACH_IPC_DEBUG
641:
642: /*
643: * Routine: ipc_hash_info
644: * Purpose:
645: * Return information about the global reverse hash table.
646: * Fills the buffer with as much information as possible
647: * and returns the desired size of the buffer.
648: * Conditions:
649: * Nothing locked. The caller should provide
650: * possibly-pageable memory.
651: */
652:
653:
654: ipc_hash_index_t
655: ipc_hash_info(
656: hash_info_bucket_t *info,
657: mach_msg_type_number_t count)
658: {
659: ipc_hash_index_t i;
660:
661: if (ipc_hash_global_size < count)
662: count = ipc_hash_global_size;
663:
664: for (i = 0; i < count; i++) {
665: ipc_hash_global_bucket_t bucket = &ipc_hash_global_table[i];
666: unsigned int bucket_count = 0;
667: ipc_tree_entry_t entry;
668:
669: ihgb_lock(bucket);
670: for (entry = bucket->ihgb_head;
671: entry != ITE_NULL;
672: entry = entry->ite_next)
673: bucket_count++;
674: ihgb_unlock(bucket);
675:
676: /* don't touch pageable memory while holding locks */
677: info[i].hib_count = bucket_count;
678: }
679:
680: return ipc_hash_global_size;
681: }
682:
683: #endif /* MACH_IPC_DEBUG */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.