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