* Copyright (c) 2000-2004 Apple Computer, Inc. All rights reserved.
*
* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
- *
+ *
* This file contains Original Code and/or Modifications of Original Code
* as defined in and that are subject to the Apple Public Source License
* Version 2.0 (the 'License'). You may not use this file except in
* unlawful or unlicensed copies of an Apple operating system, or to
* circumvent, violate, or enable the circumvention or violation of, any
* terms of an Apple operating system software license agreement.
- *
+ *
* Please obtain a copy of the License at
* http://www.opensource.apple.com/apsl/ and read it before using this file.
- *
+ *
* The Original Code and all software distributed under the License are
* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
* Please see the License for the specific language governing rights and
* limitations under the License.
- *
+ *
* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
*/
/*
* @OSF_COPYRIGHT@
*/
-/*
+/*
* 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.
*/
#include <mach/boolean.h>
#include <mach/port.h>
-#include <kern/lock.h>
-#include <kern/kalloc.h>
#include <ipc/port.h>
#include <ipc/ipc_space.h>
#include <ipc/ipc_object.h>
#include <ipc/ipc_entry.h>
#include <ipc/ipc_hash.h>
#include <ipc/ipc_init.h>
+#include <os/hash.h>
#include <mach_ipc_debug.h>
-#if MACH_IPC_DEBUG
+#if MACH_IPC_DEBUG
#include <mach/kern_return.h>
#include <mach_debug/hash_info.h>
#include <vm/vm_map.h>
#include <vm/vm_kern.h>
-#endif /* MACH_IPC_DEBUG */
+#endif /* MACH_IPC_DEBUG */
/*
- * Forward declarations
+ * Forward declarations
*/
-/* Lookup (space, obj) in global hash table */
-boolean_t ipc_hash_global_lookup(
- ipc_space_t space,
- ipc_object_t obj,
- mach_port_name_t *namep,
- ipc_tree_entry_t *entryp);
-
-/* Insert an entry into the global reverse hash table */
-void ipc_hash_global_insert(
- ipc_space_t space,
- ipc_object_t obj,
- mach_port_name_t name,
- ipc_tree_entry_t entry);
-
/* Delete an entry from the local reverse hash table */
void ipc_hash_local_delete(
- ipc_space_t space,
- ipc_object_t obj,
- mach_port_index_t index,
- ipc_entry_t entry);
+ ipc_space_t space,
+ ipc_object_t obj,
+ mach_port_index_t index,
+ ipc_entry_t entry);
/*
* Routine: ipc_hash_lookup
boolean_t
ipc_hash_lookup(
- ipc_space_t space,
- ipc_object_t obj,
- mach_port_name_t *namep,
- ipc_entry_t *entryp)
+ ipc_space_t space,
+ ipc_object_t obj,
+ mach_port_name_t *namep,
+ ipc_entry_t *entryp)
{
- boolean_t rv;
-
- rv = ipc_hash_local_lookup(space, obj, namep, entryp);
- if (!rv) {
- assert(!is_fast_space(space) || space->is_tree_hash == 0);
- if (space->is_tree_hash > 0)
- rv = ipc_hash_global_lookup(space, obj, namep,
- (ipc_tree_entry_t *) entryp);
- }
- return (rv);
+ return ipc_hash_table_lookup(space->is_table, space->is_table_size, obj, namep, entryp);
}
/*
void
ipc_hash_insert(
- ipc_space_t space,
- ipc_object_t obj,
- mach_port_name_t name,
- ipc_entry_t entry)
+ ipc_space_t space,
+ ipc_object_t obj,
+ mach_port_name_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 {
- assert(!is_fast_space(space));
- ipc_hash_global_insert(space, obj, name,
- (ipc_tree_entry_t) entry);
- }
+ space->is_table_hashed++;
+ ipc_hash_table_insert(space->is_table, space->is_table_size, obj, index, entry);
}
/*
void
ipc_hash_delete(
- ipc_space_t space,
- ipc_object_t obj,
- mach_port_name_t name,
- ipc_entry_t entry)
+ ipc_space_t space,
+ ipc_object_t obj,
+ mach_port_name_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 {
- assert(!is_fast_space(space));
- 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.
- */
-
-typedef natural_t ipc_hash_index_t;
-
-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_lck_mtx_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) lck_mtx_init(&(ihgb)->ihgb_lock_data, &ipc_lck_grp, &ipc_lck_attr)
-#define ihgb_lock(ihgb) lck_mtx_lock(&(ihgb)->ihgb_lock_data)
-#define ihgb_unlock(ihgb) lck_mtx_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_name_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);
-
- assert(!is_fast_space(space));
- 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,
- __assert_only mach_port_name_t name,
- ipc_tree_entry_t entry)
-{
- ipc_hash_global_bucket_t bucket;
-
- assert(!is_fast_space(space));
- 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,
- __assert_only mach_port_name_t name,
- ipc_tree_entry_t entry)
-{
- ipc_hash_global_bucket_t bucket;
- ipc_tree_entry_t this, *last;
-
- assert(!is_fast_space(space));
- 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);
+ space->is_table_hashed--;
+ ipc_hash_table_delete(space->is_table, space->is_table_size, obj, index, entry);
}
/*
* So possibly a small win; probably nothing significant.
*/
-#define IH_LOCAL_HASH(obj, size) \
- ((mach_port_index_t)((((uintptr_t) (obj)) >> 6) % (size)))
+#define IH_TABLE_HASH(obj, size) \
+ ((mach_port_index_t)(os_hash_kernel_pointer(obj) % (size)))
/*
- * Routine: ipc_hash_local_lookup
+ * Routine: ipc_hash_table_lookup
* Purpose:
- * Converts (space, obj) -> (name, entry).
- * Looks in the space's local table, for table entries.
- * Returns TRUE if an entry was found.
+ * Converts (table, obj) -> (name, entry).
* Conditions:
- * The space must be locked (read or write) throughout.
+ * Must have read consistency on the table.
*/
boolean_t
-ipc_hash_local_lookup(
- ipc_space_t space,
- ipc_object_t obj,
- mach_port_name_t *namep,
- ipc_entry_t *entryp)
+ipc_hash_table_lookup(
+ ipc_entry_t table,
+ ipc_entry_num_t size,
+ ipc_object_t obj,
+ mach_port_name_t *namep,
+ ipc_entry_t *entryp)
{
- ipc_entry_t table;
- ipc_entry_num_t size;
- mach_port_index_t hindex, index;
+ mach_port_index_t hindex, index, hdist;
- assert(space != IS_NULL);
- assert(obj != IO_NULL);
+ if (obj == IO_NULL) {
+ return FALSE;
+ }
- table = space->is_table;
- size = space->is_table_size;
- hindex = IH_LOCAL_HASH(obj, size);
+ hindex = IH_TABLE_HASH(obj, size);
+ hdist = 0;
/*
* Ideally, table[hindex].ie_index is the name we want.
while ((index = table[hindex].ie_index) != 0) {
ipc_entry_t entry = &table[index];
- if (entry->ie_object == obj) {
- *entryp = entry;
- *namep = MACH_PORT_MAKE(index,
- IE_BITS_GEN(entry->ie_bits));
- return TRUE;
+ /*
+ * if our current displacement is strictly larger
+ * than the current slot one, then insertion would
+ * have stolen his place so we can't possibly exist.
+ */
+ if (hdist > table[hindex].ie_dist) {
+ return FALSE;
}
- if (++hindex == size)
+ /*
+ * If our current displacement is exactly the current
+ * slot displacement, then it can be a match, let's check.
+ */
+ if (hdist == table[hindex].ie_dist) {
+ assert(index < size);
+ if (entry->ie_object == obj) {
+ *entryp = entry;
+ *namep = MACH_PORT_MAKE(index,
+ IE_BITS_GEN(entry->ie_bits));
+ return TRUE;
+ }
+ } else {
+ assert(entry->ie_object != obj);
+ }
+
+ if (hdist < IPC_ENTRY_DIST_MAX) {
+ /* peg the displacement distance at IPC_ENTRY_DIST_MAX */
+ ++hdist;
+ }
+ if (++hindex == size) {
hindex = 0;
+ }
}
return FALSE;
}
/*
- * Routine: ipc_hash_local_insert
+ * Routine: ipc_hash_table_insert
* Purpose:
* Inserts an entry into the space's reverse hash table.
* Conditions:
*/
void
-ipc_hash_local_insert(
- ipc_space_t space,
- ipc_object_t obj,
- mach_port_index_t index,
- __assert_only ipc_entry_t entry)
+ipc_hash_table_insert(
+ ipc_entry_t table,
+ ipc_entry_num_t size,
+ ipc_object_t obj,
+ mach_port_index_t index,
+ __assert_only ipc_entry_t entry)
{
- ipc_entry_t table;
- ipc_entry_num_t size;
- mach_port_index_t hindex;
+ mach_port_index_t hindex, hdist;
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);
+ hindex = IH_TABLE_HASH(obj, size);
+ hdist = 0;
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.
+ *
+ * However, Robin Hood steals from the rich, and as we go
+ * through the clump, if we go over an item that is less
+ * displaced than we'd be, we steal his slot and
+ * keep inserting him in our stead.
*/
-
while (table[hindex].ie_index != 0) {
- if (++hindex == size)
+ if (table[hindex].ie_dist < hdist) {
+#define swap(a, b) ({ typeof(a) _tmp = (b); (b) = (a); (a) = _tmp; })
+ swap(hdist, table[hindex].ie_dist);
+ swap(index, table[hindex].ie_index);
+#undef swap
+ }
+ if (hdist < IPC_ENTRY_DIST_MAX) {
+ /* peg the displacement distance at IPC_ENTRY_DIST_MAX */
+ ++hdist;
+ }
+ if (++hindex == size) {
hindex = 0;
+ }
}
table[hindex].ie_index = index;
+ table[hindex].ie_dist = hdist;
}
/*
- * Routine: ipc_hash_local_delete
+ * Routine: ipc_hash_table_delete
* Purpose:
- * Deletes an entry from the space's reverse hash table.
+ * Deletes an entry from the table's reverse hash.
* Conditions:
- * The space must be write-locked.
+ * Exclusive access to the table.
*/
void
-ipc_hash_local_delete(
- ipc_space_t space,
- ipc_object_t obj,
- mach_port_index_t index,
- __assert_only ipc_entry_t entry)
+ipc_hash_table_delete(
+ ipc_entry_t table,
+ ipc_entry_num_t size,
+ ipc_object_t obj,
+ mach_port_index_t index,
+ __assert_only ipc_entry_t entry)
{
- ipc_entry_t table;
- ipc_entry_num_t size;
- mach_port_index_t hindex, dindex;
+ mach_port_index_t hindex, dindex, dist;
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);
+ hindex = IH_TABLE_HASH(obj, size);
assert(entry == &table[index]);
assert(entry->ie_object == obj);
*/
while (table[hindex].ie_index != index) {
- if (++hindex == size)
+ if (++hindex == size) {
hindex = 0;
+ }
}
/*
* 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;
+ for (;;) {
+ dindex = hindex + 1;
+ if (dindex == size) {
+ dindex = 0;
}
- 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;
-
- /* if not configured, initialize ipc_hash_global_size */
-
- if (ipc_hash_global_size == 0) {
- ipc_hash_global_size = ipc_tree_entry_max >> 8;
- if (ipc_hash_global_size < 32)
- ipc_hash_global_size = 32;
- }
-
- /* 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;
+ /*
+ * If the next element is empty or isn't displaced,
+ * then lookup will end on the next element anyway,
+ * so we can leave the hole right here, we're done
+ */
+ index = table[dindex].ie_index;
+ dist = table[dindex].ie_dist;
+ if (index == 0 || dist == 0) {
+ table[hindex].ie_index = 0;
+ table[hindex].ie_dist = 0;
+ return;
}
- }
-
- /* 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_size
- * Purpose:
- * Return the size of the global reverse hash table.
- */
-natural_t
-ipc_hash_size(void)
-{
- return ipc_hash_global_size;
-}
-
-/*
- * 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.
- */
+ /*
+ * Move this object closer to its own slot by occupying the hole.
+ * If its displacement was pegged, recompute it.
+ */
+ if (dist-- == IPC_ENTRY_DIST_MAX) {
+ uint32_t desired = IH_TABLE_HASH(table[index].ie_object, size);
+ if (hindex >= desired) {
+ dist = hindex - desired;
+ } else {
+ dist = hindex + size - desired;
+ }
+ if (dist > IPC_ENTRY_DIST_MAX) {
+ dist = IPC_ENTRY_DIST_MAX;
+ }
+ }
-ipc_hash_index_t
-ipc_hash_info(
- hash_info_bucket_t *info,
- natural_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;
+ /*
+ * Move the displaced element closer to its ideal bucket,
+ * and keep shifting elements back.
+ */
+ table[hindex].ie_index = index;
+ table[hindex].ie_dist = dist;
+ hindex = dindex;
}
-
- return ipc_hash_global_size;
}
-
-#endif /* MACH_IPC_DEBUG */
projects / apple / xnu.git / blobdiff