![[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 Darwin 0.x] / kernel / ipc|
Return to ipc_hash.c CVS log | Up to [Apple Darwin 0.x] / kernel / ipc |
1.1 root 1: /*
2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7: * Reserved. This file contains Original Code and/or Modifications of
8: * Original Code as defined in and that are subject to the Apple Public
9: * Source License Version 1.1 (the "License"). You may not use this file
10: * except in compliance with the License. Please obtain a copy of the
11: * License at http://www.apple.com/publicsource and read it before using
12: * this file.
13: *
14: * The Original Code and all software distributed under the License are
15: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19: * License for the specific language governing rights and limitations
20: * under the License.
21: *
22: * @APPLE_LICENSE_HEADER_END@
23: */
24:
25: /*
26: * Copyright (c) 1995, 1994, 1993, 1992, 1991, 1990
27: * Open Software Foundation, Inc.
28: *
29: * Permission to use, copy, modify, and distribute this software and
30: * its documentation for any purpose and without fee is hereby granted,
31: * provided that the above copyright notice appears in all copies and
32: * that both the copyright notice and this permission notice appear in
33: * supporting documentation, and that the name of ("OSF") or Open Software
34: * Foundation not be used in advertising or publicity pertaining to
35: * distribution of the software without specific, written prior permission.
36: *
37: * OSF DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE
38: * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
39: * FOR A PARTICULAR PURPOSE. IN NO EVENT SHALL OSF BE LIABLE FOR ANY
40: * SPECIAL, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
41: * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
42: * ACTION OF CONTRACT, NEGLIGENCE, OR OTHER TORTIOUS ACTION, ARISING
43: * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE
44: */
45: /*
46: * OSF Research Institute MK6.1 (unencumbered) 1/31/1995
47: */
48: /*
49: * Mach Operating System
50: * Copyright (c) 1991,1990,1989 Carnegie Mellon University
51: * All Rights Reserved.
52: *
53: * Permission to use, copy, modify and distribute this software and its
54: * documentation is hereby granted, provided that both the copyright
55: * notice and this permission notice appear in all copies of the
56: * software, derivative works or modified versions, and any portions
57: * thereof, and that both notices appear in supporting documentation.
58: *
59: * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
60: * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
61: * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
62: *
63: * Carnegie Mellon requests users of this software to return to
64: *
65: * Software Distribution Coordinator or [email protected]
66: * School of Computer Science
67: * Carnegie Mellon University
68: * Pittsburgh PA 15213-3890
69: *
70: * any improvements or extensions that they make and grant Carnegie Mellon
71: * the rights to redistribute these changes.
72: */
73: /*
74: * File: ipc/ipc_hash.c
75: * Author: Rich Draves
76: * Date: 1989
77: *
78: * Entry hash table operations.
79: */
80:
81: #include <mach/boolean.h>
82: #include <mach/port.h>
83: #include <kern/lock.h>
84: #include <kern/kalloc.h>
85: #include <ipc/port.h>
86: #include <ipc/ipc_space.h>
87: #include <ipc/ipc_object.h>
88: #include <ipc/ipc_entry.h>
89: #include <ipc/ipc_hash.h>
90: #include <ipc/ipc_init.h>
91:
92: /*
93: * Forward declarations
94: */
95:
96: /* Lookup (space, obj) in global hash table */
97: boolean_t ipc_hash_global_lookup(
98: ipc_space_t space,
99: ipc_object_t obj,
100: mach_port_t *namep,
101: ipc_tree_entry_t *entryp);
102:
103: /* Insert an entry into the global reverse hash table */
104: void ipc_hash_global_insert(
105: ipc_space_t space,
106: ipc_object_t obj,
107: mach_port_t name,
108: ipc_tree_entry_t entry);
109:
110: /* Delete an entry from the local reverse hash table */
111: void ipc_hash_local_delete(
112: ipc_space_t space,
113: ipc_object_t obj,
114: mach_port_index_t index,
115: ipc_entry_t entry);
116:
117: /*
118: * Routine: ipc_hash_lookup
119: * Purpose:
120: * Converts (space, obj) -> (name, entry).
121: * Returns TRUE if an entry was found.
122: * Conditions:
123: * The space must be locked (read or write) throughout.
124: */
125:
126: boolean_t
127: ipc_hash_lookup(
128: ipc_space_t space,
129: ipc_object_t obj,
130: mach_port_t *namep,
131: ipc_entry_t *entryp)
132: {
133: boolean_t rv;
134:
135: rv = ipc_hash_local_lookup(space, obj, namep, entryp);
136: if (!rv) {
137: if (space->is_tree_hash > 0)
138: rv = ipc_hash_global_lookup(space, obj, namep,
139: (ipc_tree_entry_t *) entryp);
140: }
141: return (rv);
142: }
143:
144: /*
145: * Routine: ipc_hash_insert
146: * Purpose:
147: * Inserts an entry into the appropriate reverse hash table,
148: * so that ipc_hash_lookup will find it.
149: * Conditions:
150: * The space must be write-locked.
151: */
152:
153: void
154: ipc_hash_insert(
155: ipc_space_t space,
156: ipc_object_t obj,
157: mach_port_t name,
158: ipc_entry_t entry)
159: {
160: mach_port_index_t index;
161:
162: index = MACH_PORT_INDEX(name);
163: if ((index < space->is_table_size) &&
164: (entry == &space->is_table[index]))
165: ipc_hash_local_insert(space, obj, index, entry);
166: else {
167: ipc_hash_global_insert(space, obj, name,
168: (ipc_tree_entry_t) entry);
169: }
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
181: ipc_hash_delete(
182: ipc_space_t space,
183: ipc_object_t obj,
184: mach_port_t name,
185: ipc_entry_t entry)
186: {
187: mach_port_index_t index;
188:
189: index = MACH_PORT_INDEX(name);
190: if ((index < space->is_table_size) &&
191: (entry == &space->is_table[index]))
192: ipc_hash_local_delete(space, obj, index, entry);
193: else {
194: ipc_hash_global_delete(space, obj, name,
195: (ipc_tree_entry_t) entry);
196: }
197: }
198:
199: /*
200: * The global reverse hash table holds splay tree entries.
201: * It is a simple open-chaining hash table with singly-linked buckets.
202: * Each bucket is locked separately, with an exclusive lock.
203: * Within each bucket, move-to-front is used.
204: */
205:
206: typedef unsigned int ipc_hash_index_t;
207:
208: ipc_hash_index_t ipc_hash_global_size;
209: ipc_hash_index_t ipc_hash_global_mask;
210:
211: #define IH_GLOBAL_HASH(space, obj) \
212: (((((ipc_hash_index_t) (space)) >> 4) + \
213: (((ipc_hash_index_t) (obj)) >> 6)) & \
214: ipc_hash_global_mask)
215:
216: typedef struct ipc_hash_global_bucket {
217: decl_simple_lock_data(, ihgb_lock_data)
218: ipc_tree_entry_t ihgb_head;
219: } *ipc_hash_global_bucket_t;
220:
221: #define IHGB_NULL ((ipc_hash_global_bucket_t) 0)
222:
223: #define ihgb_lock_init(ihgb) simple_lock_init(&(ihgb)->ihgb_lock_data)
224: #define ihgb_lock(ihgb) simple_lock(&(ihgb)->ihgb_lock_data)
225: #define ihgb_unlock(ihgb) simple_unlock(&(ihgb)->ihgb_lock_data)
226:
227: ipc_hash_global_bucket_t ipc_hash_global_table;
228:
229: /*
230: * Routine: ipc_hash_global_lookup
231: * Purpose:
232: * Converts (space, obj) -> (name, entry).
233: * Looks in the global table, for splay tree entries.
234: * Returns TRUE if an entry was found.
235: * Conditions:
236: * The space must be locked (read or write) throughout.
237: */
238:
239: boolean_t
240: ipc_hash_global_lookup(
241: ipc_space_t space,
242: ipc_object_t obj,
243: mach_port_t *namep,
244: ipc_tree_entry_t *entryp)
245: {
246: ipc_hash_global_bucket_t bucket;
247: ipc_tree_entry_t this, *last;
248:
249: assert(space != IS_NULL);
250: assert(obj != IO_NULL);
251:
252: bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)];
253: ihgb_lock(bucket);
254:
255: if ((this = bucket->ihgb_head) != ITE_NULL) {
256: if ((this->ite_object == obj) &&
257: (this->ite_space == space)) {
258: /* found it at front; no need to move */
259:
260: *namep = this->ite_name;
261: *entryp = this;
262: } else for (last = &this->ite_next;
263: (this = *last) != ITE_NULL;
264: last = &this->ite_next) {
265: if ((this->ite_object == obj) &&
266: (this->ite_space == space)) {
267: /* found it; move to front */
268:
269: *last = this->ite_next;
270: this->ite_next = bucket->ihgb_head;
271: bucket->ihgb_head = this;
272:
273: *namep = this->ite_name;
274: *entryp = this;
275: break;
276: }
277: }
278: }
279:
280: ihgb_unlock(bucket);
281: return this != ITE_NULL;
282: }
283:
284: /*
285: * Routine: ipc_hash_global_insert
286: * Purpose:
287: * Inserts an entry into the global reverse hash table.
288: * Conditions:
289: * The space must be write-locked.
290: */
291:
292: void
293: ipc_hash_global_insert(
294: ipc_space_t space,
295: ipc_object_t obj,
296: mach_port_t name,
297: ipc_tree_entry_t entry)
298: {
299: ipc_hash_global_bucket_t bucket;
300:
301: assert(entry->ite_name == name);
302: assert(space != IS_NULL);
303: assert(entry->ite_space == space);
304: assert(obj != IO_NULL);
305: assert(entry->ite_object == obj);
306:
307: space->is_tree_hash++;
308: assert(space->is_tree_hash <= space->is_tree_total);
309:
310: bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)];
311: ihgb_lock(bucket);
312:
313: /* insert at front of bucket */
314:
315: entry->ite_next = bucket->ihgb_head;
316: bucket->ihgb_head = entry;
317:
318: ihgb_unlock(bucket);
319: }
320:
321: /*
322: * Routine: ipc_hash_global_delete
323: * Purpose:
324: * Deletes an entry from the global reverse hash table.
325: * Conditions:
326: * The space must be write-locked.
327: */
328:
329: void
330: ipc_hash_global_delete(
331: ipc_space_t space,
332: ipc_object_t obj,
333: mach_port_t name,
334: ipc_tree_entry_t entry)
335: {
336: ipc_hash_global_bucket_t bucket;
337: ipc_tree_entry_t this, *last;
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_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: *namep = MACH_PORT_MAKEB(index, entry->ie_bits);
439: *entryp = entry;
440: return TRUE;
441: }
442:
443: if (++hindex == size)
444: hindex = 0;
445: }
446:
447: return FALSE;
448: }
449:
450: /*
451: * Routine: ipc_hash_local_insert
452: * Purpose:
453: * Inserts an entry into the space's reverse hash table.
454: * Conditions:
455: * The space must be write-locked.
456: */
457:
458: void
459: ipc_hash_local_insert(
460: ipc_space_t space,
461: ipc_object_t obj,
462: mach_port_index_t index,
463: ipc_entry_t entry)
464: {
465: ipc_entry_t table;
466: ipc_entry_num_t size;
467: mach_port_index_t hindex;
468:
469: assert(index != 0);
470: assert(space != IS_NULL);
471: assert(obj != IO_NULL);
472:
473: table = space->is_table;
474: size = space->is_table_size;
475: hindex = IH_LOCAL_HASH(obj, size);
476:
477: assert(entry == &table[index]);
478: assert(entry->ie_object == obj);
479:
480: /*
481: * We want to insert at hindex, but there may be collisions.
482: * If a collision occurs, search for the end of the clump
483: * and insert there.
484: */
485:
486: while (table[hindex].ie_index != 0) {
487: if (++hindex == size)
488: hindex = 0;
489: }
490:
491: table[hindex].ie_index = index;
492: }
493:
494: /*
495: * Routine: ipc_hash_local_delete
496: * Purpose:
497: * Deletes an entry from the space's reverse hash table.
498: * Conditions:
499: * The space must be write-locked.
500: */
501:
502: void
503: ipc_hash_local_delete(
504: ipc_space_t space,
505: ipc_object_t obj,
506: mach_port_index_t index,
507: ipc_entry_t entry)
508: {
509: ipc_entry_t table;
510: ipc_entry_num_t size;
511: mach_port_index_t hindex, dindex;
512:
513: assert(index != MACH_PORT_NULL);
514: assert(space != IS_NULL);
515: assert(obj != IO_NULL);
516:
517: table = space->is_table;
518: size = space->is_table_size;
519: hindex = IH_LOCAL_HASH(obj, size);
520:
521: assert(entry == &table[index]);
522: assert(entry->ie_object == obj);
523:
524: /*
525: * First check we have the right hindex for this index.
526: * In case of collision, we have to search farther
527: * along in this clump.
528: */
529:
530: while (table[hindex].ie_index != index) {
531: if (++hindex == size)
532: hindex = 0;
533: }
534:
535: /*
536: * Now we want to set table[hindex].ie_index = 0.
537: * But if we aren't the last index in a clump,
538: * this might cause problems for lookups of objects
539: * farther along in the clump that are displaced
540: * due to collisions. Searches for them would fail
541: * at hindex instead of succeeding.
542: *
543: * So we must check the clump after hindex for objects
544: * that are so displaced, and move one up to the new hole.
545: *
546: * hindex - index of new hole in the clump
547: * dindex - index we are checking for a displaced object
548: *
549: * When we move a displaced object up into the hole,
550: * it creates a new hole, and we have to repeat the process
551: * until we get to the end of the clump.
552: */
553:
554: for (dindex = hindex; index != 0; hindex = dindex) {
555: for (;;) {
556: mach_port_index_t tindex;
557: ipc_object_t tobj;
558:
559: if (++dindex == size)
560: dindex = 0;
561: assert(dindex != hindex);
562:
563: /* are we at the end of the clump? */
564:
565: index = table[dindex].ie_index;
566: if (index == 0)
567: break;
568:
569: /* is this a displaced object? */
570:
571: tobj = table[index].ie_object;
572: assert(tobj != IO_NULL);
573: tindex = IH_LOCAL_HASH(tobj, size);
574:
575: if ((dindex < hindex) ?
576: ((dindex < tindex) && (tindex <= hindex)) :
577: ((dindex < tindex) || (tindex <= hindex)))
578: break;
579: }
580:
581: table[hindex].ie_index = index;
582: }
583: }
584:
585: /*
586: * Routine: ipc_hash_init
587: * Purpose:
588: * Initialize the reverse hash table implementation.
589: */
590:
591: void
592: ipc_hash_init(void)
593: {
594: ipc_hash_index_t i;
595:
596: /* if not configured, initialize ipc_hash_global_size */
597:
598: if (ipc_hash_global_size == 0) {
599: ipc_hash_global_size = ipc_tree_entry_max >> 8;
600: if (ipc_hash_global_size < 32)
601: ipc_hash_global_size = 32;
602: }
603:
604: /* make sure it is a power of two */
605:
606: ipc_hash_global_mask = ipc_hash_global_size - 1;
607: if ((ipc_hash_global_size & ipc_hash_global_mask) != 0) {
608: unsigned int bit;
609:
610: /* round up to closest power of two */
611:
612: for (bit = 1;; bit <<= 1) {
613: ipc_hash_global_mask |= bit;
614: ipc_hash_global_size = ipc_hash_global_mask + 1;
615:
616: if ((ipc_hash_global_size & ipc_hash_global_mask) == 0)
617: break;
618: }
619: }
620:
621: /* allocate ipc_hash_global_table */
622:
623: ipc_hash_global_table = (ipc_hash_global_bucket_t)
624: kalloc((vm_size_t) (ipc_hash_global_size *
625: sizeof(struct ipc_hash_global_bucket)));
626: assert(ipc_hash_global_table != IHGB_NULL);
627:
628: /* and initialize it */
629:
630: for (i = 0; i < ipc_hash_global_size; i++) {
631: ipc_hash_global_bucket_t bucket;
632:
633: bucket = &ipc_hash_global_table[i];
634: ihgb_lock_init(bucket);
635: bucket->ihgb_head = ITE_NULL;
636: }
637: }
638:
639: #include <mach_ipc_debug.h>
640: #if MACH_IPC_DEBUG
641:
642: #include <mach/kern_return.h>
643: #include <mach_debug/hash_info.h>
644: #include <vm/vm_map.h>
645: #include <vm/vm_kern.h>
646: #include <vm/vm_user.h>
647:
648: /*
649: * Routine: ipc_hash_info
650: * Purpose:
651: * Return information about the global reverse hash table.
652: * Fills the buffer with as much information as possible
653: * and returns the desired size of the buffer.
654: * Conditions:
655: * Nothing locked. The caller should provide
656: * possibly-pageable memory.
657: */
658:
659: unsigned int
660: ipc_hash_info(
661: hash_info_bucket_t *info,
662: unsigned int count)
663: {
664: ipc_hash_index_t i;
665:
666: if (ipc_hash_global_size < count)
667: count = ipc_hash_global_size;
668:
669: for (i = 0; i < count; i++) {
670: ipc_hash_global_bucket_t bucket = &ipc_hash_global_table[i];
671: unsigned int bucket_count = 0;
672: ipc_tree_entry_t entry;
673:
674: ihgb_lock(bucket);
675: for (entry = bucket->ihgb_head;
676: entry != ITE_NULL;
677: entry = entry->ite_next)
678: bucket_count++;
679: ihgb_unlock(bucket);
680:
681: /* don't touch pageable memory while holding locks */
682: info[i].hib_count = bucket_count;
683: }
684:
685: return ipc_hash_global_size;
686: }
687:
688: #endif /* MACH_IPC_DEBUG */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.