summaryrefslogtreecommitdiff
path: root/ipc/ipc_hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'ipc/ipc_hash.c')
-rw-r--r--ipc/ipc_hash.c486
1 files changed, 0 insertions, 486 deletions
diff --git a/ipc/ipc_hash.c b/ipc/ipc_hash.c
deleted file mode 100644
index 87952a79..00000000
--- a/ipc/ipc_hash.c
+++ /dev/null
@@ -1,486 +0,0 @@
-/*
- * 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 <kern/printf.h>
-#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 <ipc/ipc_types.h>
-
-#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>
-#include <vm/vm_user.h>
-#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 mapping from objects to entries
- * from the space's table. This used to be a hash table.
- */
-
-#define IPC_LOCAL_HASH_INVARIANT(S, O, N, E) \
- MACRO_BEGIN \
- assert(IE_BITS_TYPE((E)->ie_bits) == MACH_PORT_TYPE_SEND || \
- IE_BITS_TYPE((E)->ie_bits) == MACH_PORT_TYPE_SEND_RECEIVE || \
- IE_BITS_TYPE((E)->ie_bits) == MACH_PORT_TYPE_NONE); \
- assert((E)->ie_object == (O)); \
- assert((E)->ie_index == (N)); \
- assert(&(S)->is_table[N] == (E)); \
- MACRO_END
-
-/*
- * 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)
-{
- assert(space != IS_NULL);
- assert(obj != IO_NULL);
-
- *entryp = ipc_reverse_lookup(space, obj);
- if (*entryp != IE_NULL) {
- *namep = (*entryp)->ie_index;
- IPC_LOCAL_HASH_INVARIANT(space, obj, *namep, *entryp);
- return TRUE;
- }
- 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)
-{
- kern_return_t kr;
- assert(index != 0);
- assert(space != IS_NULL);
- assert(obj != IO_NULL);
-
- entry->ie_index = index;
- IPC_LOCAL_HASH_INVARIANT(space, obj, index, entry);
- kr = ipc_reverse_insert(space, obj, entry);
- assert(kr == 0);
-}
-
-/*
- * 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 removed;
- assert(index != MACH_PORT_NULL);
- assert(space != IS_NULL);
- assert(obj != IO_NULL);
-
- IPC_LOCAL_HASH_INVARIANT(space, obj, index, entry);
- removed = ipc_reverse_remove(space, obj);
- assert(removed == entry);
-}
-
-/*
- * 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 */
generated by cgit v1.2.3 (git 2.44.0) at 2024-04-27 07:58:08 +0000