/* * Mach Operating System * Copyright (c) 1991,1990,1989 Carnegie Mellon University * All Rights Reserved. * * Permission to use, copy, modify and distribute this software and its * documentation is hereby granted, provided that both the copyright * notice and this permission notice appear in all copies of the * software, derivative works or modified versions, and any portions * thereof, and that both notices appear in supporting documentation. * * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. * * Carnegie Mellon requests users of this software to return to * * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU * School of Computer Science * Carnegie Mellon University * Pittsburgh PA 15213-3890 * * any improvements or extensions that they make and grant Carnegie Mellon * the rights to redistribute these changes. */ /* * File: ipc/ipc_hash.c * Author: Rich Draves * Date: 1989 * * Entry hash table operations. */ #include #include #include #include #include #include #include #include #include #include #include #include #if MACH_IPC_DEBUG #include #include #include #include #include #endif /* * Routine: ipc_hash_lookup * Purpose: * Converts (space, obj) -> (name, entry). * Returns TRUE if an entry was found. * Conditions: * The space must be locked (read or write) throughout. */ boolean_t ipc_hash_lookup( ipc_space_t space, ipc_object_t obj, mach_port_t *namep, ipc_entry_t *entryp) { return (ipc_hash_local_lookup(space, obj, namep, entryp) || ((space->is_tree_hash > 0) && ipc_hash_global_lookup(space, obj, namep, (ipc_tree_entry_t *) entryp))); } /* * Routine: ipc_hash_insert * Purpose: * Inserts an entry into the appropriate reverse hash table, * so that ipc_hash_lookup will find it. * Conditions: * The space must be write-locked. */ void ipc_hash_insert( ipc_space_t space, ipc_object_t obj, mach_port_t name, ipc_entry_t entry) { mach_port_index_t index; index = MACH_PORT_INDEX(name); if ((index < space->is_table_size) && (entry == &space->is_table[index])) ipc_hash_local_insert(space, obj, index, entry); else ipc_hash_global_insert(space, obj, name, (ipc_tree_entry_t) entry); } /* * Routine: ipc_hash_delete * Purpose: * Deletes an entry from the appropriate reverse hash table. * Conditions: * The space must be write-locked. */ void ipc_hash_delete( ipc_space_t space, ipc_object_t obj, mach_port_t name, ipc_entry_t entry) { mach_port_index_t index; index = MACH_PORT_INDEX(name); if ((index < space->is_table_size) && (entry == &space->is_table[index])) ipc_hash_local_delete(space, obj, index, entry); else ipc_hash_global_delete(space, obj, name, (ipc_tree_entry_t) entry); } /* * The global reverse hash table holds splay tree entries. * It is a simple open-chaining hash table with singly-linked buckets. * Each bucket is locked separately, with an exclusive lock. * Within each bucket, move-to-front is used. */ ipc_hash_index_t ipc_hash_global_size; ipc_hash_index_t ipc_hash_global_mask; #define IH_GLOBAL_HASH(space, obj) \ (((((ipc_hash_index_t) ((vm_offset_t)space)) >> 4) + \ (((ipc_hash_index_t) ((vm_offset_t)obj)) >> 6)) & \ ipc_hash_global_mask) typedef struct ipc_hash_global_bucket { decl_simple_lock_data(, ihgb_lock_data) ipc_tree_entry_t ihgb_head; } *ipc_hash_global_bucket_t; #define IHGB_NULL ((ipc_hash_global_bucket_t) 0) #define ihgb_lock_init(ihgb) simple_lock_init(&(ihgb)->ihgb_lock_data) #define ihgb_lock(ihgb) simple_lock(&(ihgb)->ihgb_lock_data) #define ihgb_unlock(ihgb) simple_unlock(&(ihgb)->ihgb_lock_data) ipc_hash_global_bucket_t ipc_hash_global_table; /* * Routine: ipc_hash_global_lookup * Purpose: * Converts (space, obj) -> (name, entry). * Looks in the global table, for splay tree entries. * Returns TRUE if an entry was found. * Conditions: * The space must be locked (read or write) throughout. */ boolean_t ipc_hash_global_lookup( ipc_space_t space, ipc_object_t obj, mach_port_t *namep, ipc_tree_entry_t *entryp) { ipc_hash_global_bucket_t bucket; ipc_tree_entry_t this, *last; assert(space != IS_NULL); assert(obj != IO_NULL); bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)]; ihgb_lock(bucket); if ((this = bucket->ihgb_head) != ITE_NULL) { if ((this->ite_object == obj) && (this->ite_space == space)) { /* found it at front; no need to move */ *namep = this->ite_name; *entryp = this; } else for (last = &this->ite_next; (this = *last) != ITE_NULL; last = &this->ite_next) { if ((this->ite_object == obj) && (this->ite_space == space)) { /* found it; move to front */ *last = this->ite_next; this->ite_next = bucket->ihgb_head; bucket->ihgb_head = this; *namep = this->ite_name; *entryp = this; break; } } } ihgb_unlock(bucket); return this != ITE_NULL; } /* * Routine: ipc_hash_global_insert * Purpose: * Inserts an entry into the global reverse hash table. * Conditions: * The space must be write-locked. */ void ipc_hash_global_insert( ipc_space_t space, ipc_object_t obj, mach_port_t name, ipc_tree_entry_t entry) { ipc_hash_global_bucket_t bucket; assert(entry->ite_name == name); assert(space != IS_NULL); assert(entry->ite_space == space); assert(obj != IO_NULL); assert(entry->ite_object == obj); space->is_tree_hash++; assert(space->is_tree_hash <= space->is_tree_total); bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)]; ihgb_lock(bucket); /* insert at front of bucket */ entry->ite_next = bucket->ihgb_head; bucket->ihgb_head = entry; ihgb_unlock(bucket); } /* * Routine: ipc_hash_global_delete * Purpose: * Deletes an entry from the global reverse hash table. * Conditions: * The space must be write-locked. */ void ipc_hash_global_delete( ipc_space_t space, ipc_object_t obj, mach_port_t name, ipc_tree_entry_t entry) { ipc_hash_global_bucket_t bucket; ipc_tree_entry_t this, *last; assert(entry->ite_name == name); assert(space != IS_NULL); assert(entry->ite_space == space); assert(obj != IO_NULL); assert(entry->ite_object == obj); assert(space->is_tree_hash > 0); space->is_tree_hash--; bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)]; ihgb_lock(bucket); for (last = &bucket->ihgb_head; (this = *last) != ITE_NULL; last = &this->ite_next) { if (this == entry) { /* found it; remove from bucket */ *last = this->ite_next; break; } } assert(this != ITE_NULL); ihgb_unlock(bucket); } /* * Each space has a local reverse hash table, which holds * entries from the space's table. In fact, the hash table * just uses a field (ie_index) in the table itself. * * The local hash table is an open-addressing hash table, * which means that when a collision occurs, instead of * throwing the entry into a bucket, the entry is rehashed * to another position in the table. In this case the rehash * is very simple: linear probing (ie, just increment the position). * This simple rehash makes deletions tractable (they're still a pain), * but it means that collisions tend to build up into clumps. * * Because at least one entry in the table (index 0) is always unused, * there will always be room in the reverse hash table. If a table * with n slots gets completely full, the reverse hash table will * have one giant clump of n-1 slots and one free slot somewhere. * Because entries are only entered into the reverse table if they * are pure send rights (not receive, send-once, port-set, * or dead-name rights), and free entries of course aren't entered, * I expect the reverse hash table won't get unreasonably full. * * Ordered hash tables (Amble & Knuth, Computer Journal, v. 17, no. 2, * pp. 135-142.) may be desirable here. They can dramatically help * unsuccessful lookups. But unsuccessful lookups are almost always * followed by insertions, and those slow down somewhat. They * also can help deletions somewhat. Successful lookups aren't affected. * So possibly a small win; probably nothing significant. */ #define IH_LOCAL_HASH(obj, size) \ ((((mach_port_index_t) (vm_offset_t) (obj)) >> 6) % (size)) /* * Routine: ipc_hash_local_lookup * Purpose: * Converts (space, obj) -> (name, entry). * Looks in the space's local table, for table entries. * Returns TRUE if an entry was found. * Conditions: * The space must be locked (read or write) throughout. */ boolean_t ipc_hash_local_lookup( ipc_space_t space, ipc_object_t obj, mach_port_t *namep, ipc_entry_t *entryp) { ipc_entry_t table; ipc_entry_num_t size; mach_port_index_t hindex, index; assert(space != IS_NULL); assert(obj != IO_NULL); table = space->is_table; size = space->is_table_size; hindex = IH_LOCAL_HASH(obj, size); /* * Ideally, table[hindex].ie_index is the name we want. * However, must check ie_object to verify this, * because collisions can happen. In case of a collision, * search farther along in the clump. */ while ((index = table[hindex].ie_index) != 0) { ipc_entry_t entry = &table[index]; if (entry->ie_object == obj) { *namep = MACH_PORT_MAKEB(index, entry->ie_bits); *entryp = entry; return TRUE; } if (++hindex == size) hindex = 0; } return FALSE; } /* * Routine: ipc_hash_local_insert * Purpose: * Inserts an entry into the space's reverse hash table. * Conditions: * The space must be write-locked. */ void ipc_hash_local_insert( ipc_space_t space, ipc_object_t obj, mach_port_index_t index, ipc_entry_t entry) { ipc_entry_t table; ipc_entry_num_t size; mach_port_index_t hindex; assert(index != 0); assert(space != IS_NULL); assert(obj != IO_NULL); table = space->is_table; size = space->is_table_size; hindex = IH_LOCAL_HASH(obj, size); assert(entry == &table[index]); assert(entry->ie_object == obj); /* * We want to insert at hindex, but there may be collisions. * If a collision occurs, search for the end of the clump * and insert there. */ while (table[hindex].ie_index != 0) { if (++hindex == size) hindex = 0; } table[hindex].ie_index = index; } /* * Routine: ipc_hash_local_delete * Purpose: * Deletes an entry from the space's reverse hash table. * Conditions: * The space must be write-locked. */ void ipc_hash_local_delete( ipc_space_t space, ipc_object_t obj, mach_port_index_t index, ipc_entry_t entry) { ipc_entry_t table; ipc_entry_num_t size; mach_port_index_t hindex, dindex; assert(index != MACH_PORT_NULL); assert(space != IS_NULL); assert(obj != IO_NULL); table = space->is_table; size = space->is_table_size; hindex = IH_LOCAL_HASH(obj, size); assert(entry == &table[index]); assert(entry->ie_object == obj); /* * First check we have the right hindex for this index. * In case of collision, we have to search farther * along in this clump. */ while (table[hindex].ie_index != index) { if (table[hindex].ie_index == 0) { static int gak = 0; if (gak == 0) { printf("gak! entry wasn't in hash table!\n"); gak = 1; } return; } if (++hindex == size) hindex = 0; } /* * Now we want to set table[hindex].ie_index = 0. * But if we aren't the last index in a clump, * this might cause problems for lookups of objects * farther along in the clump that are displaced * due to collisions. Searches for them would fail * at hindex instead of succeeding. * * So we must check the clump after hindex for objects * that are so displaced, and move one up to the new hole. * * hindex - index of new hole in the clump * dindex - index we are checking for a displaced object * * When we move a displaced object up into the hole, * it creates a new hole, and we have to repeat the process * until we get to the end of the clump. */ for (dindex = hindex; index != 0; hindex = dindex) { for (;;) { mach_port_index_t tindex; ipc_object_t tobj; if (++dindex == size) dindex = 0; assert(dindex != hindex); /* are we at the end of the clump? */ index = table[dindex].ie_index; if (index == 0) break; /* is this a displaced object? */ tobj = table[index].ie_object; assert(tobj != IO_NULL); tindex = IH_LOCAL_HASH(tobj, size); if ((dindex < hindex) ? ((dindex < tindex) && (tindex <= hindex)) : ((dindex < tindex) || (tindex <= hindex))) break; } table[hindex].ie_index = index; } } /* * Routine: ipc_hash_init * Purpose: * Initialize the reverse hash table implementation. */ void ipc_hash_init(void) { ipc_hash_index_t i; /* initialize ipc_hash_global_size */ ipc_hash_global_size = IPC_HASH_GLOBAL_SIZE; /* make sure it is a power of two */ ipc_hash_global_mask = ipc_hash_global_size - 1; if ((ipc_hash_global_size & ipc_hash_global_mask) != 0) { natural_t bit; /* round up to closest power of two */ for (bit = 1;; bit <<= 1) { ipc_hash_global_mask |= bit; ipc_hash_global_size = ipc_hash_global_mask + 1; if ((ipc_hash_global_size & ipc_hash_global_mask) == 0) break; } } /* allocate ipc_hash_global_table */ ipc_hash_global_table = (ipc_hash_global_bucket_t) kalloc((vm_size_t) (ipc_hash_global_size * sizeof(struct ipc_hash_global_bucket))); assert(ipc_hash_global_table != IHGB_NULL); /* and initialize it */ for (i = 0; i < ipc_hash_global_size; i++) { ipc_hash_global_bucket_t bucket; bucket = &ipc_hash_global_table[i]; ihgb_lock_init(bucket); bucket->ihgb_head = ITE_NULL; } } #if MACH_IPC_DEBUG /* * Routine: ipc_hash_info * Purpose: * Return information about the global reverse hash table. * Fills the buffer with as much information as possible * and returns the desired size of the buffer. * Conditions: * Nothing locked. The caller should provide * possibly-pageable memory. */ ipc_hash_index_t ipc_hash_info( hash_info_bucket_t *info, mach_msg_type_number_t count) { ipc_hash_index_t i; if (ipc_hash_global_size < count) count = ipc_hash_global_size; for (i = 0; i < count; i++) { ipc_hash_global_bucket_t bucket = &ipc_hash_global_table[i]; unsigned int bucket_count = 0; ipc_tree_entry_t entry; ihgb_lock(bucket); for (entry = bucket->ihgb_head; entry != ITE_NULL; entry = entry->ite_next) bucket_count++; ihgb_unlock(bucket); /* don't touch pageable memory while holding locks */ info[i].hib_count = bucket_count; } return ipc_hash_global_size; } #endif /* MACH_IPC_DEBUG */