xref: /xnu-8792.61.2/osfmk/ipc/ipc_hash.c (revision 42e220869062b56f8d7d0726fd4c88954f87902c)

/*
 * 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
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * 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,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * 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  [email protected]
 *  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 <mach/boolean.h>
#include <mach/port.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/kern_return.h>
#include <mach_debug/hash_info.h>
#include <vm/vm_map.h>
#include <vm/vm_kern.h>

/*
 * Forward declarations
 */

/* 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);

/*
 *	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_name_t        *namep,
	ipc_entry_t             *entryp)
{
	return ipc_hash_table_lookup(is_active_table(space), obj, namep, 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_name_t        name,
	ipc_entry_t             entry)
{
	mach_port_index_t index;

	index = MACH_PORT_INDEX(name);
	space->is_table_hashed++;
	ipc_hash_table_insert(is_active_table(space), obj, index, 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_name_t        name,
	ipc_entry_t             entry)
{
	mach_port_index_t index;

	index = MACH_PORT_INDEX(name);
	space->is_table_hashed--;
	ipc_hash_table_delete(is_active_table(space), obj, index, entry);
}

/*
 *	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_TABLE_HASH(obj, size)                                \
	        ((mach_port_index_t)(os_hash_kernel_pointer(obj) % (size)))

/*
 *	Routine:	ipc_hash_table_lookup
 *	Purpose:
 *		Converts (table, obj) -> (name, entry).
 *	Conditions:
 *		Must have read consistency on the table.
 */

boolean_t
ipc_hash_table_lookup(
	ipc_entry_table_t       array,
	ipc_object_t            obj,
	mach_port_name_t        *namep,
	ipc_entry_t             *entryp)
{
	mach_port_index_t hindex, index, hdist;
	ipc_entry_t       table = ipc_entry_table_base(array);
	ipc_entry_num_t   size  = ipc_entry_table_count(array);

	if (obj == IO_NULL) {
		return FALSE;
	}

	hindex = IH_TABLE_HASH(obj, size);
	hdist  = 0;

	/*
	 *	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 = index < size ? &table[index] : IE_NULL;

		/*
		 * 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 our current displacement is exactly the current
		 * slot displacement, then it can be a match, let's check.
		 */
		if (hdist == table[hindex].ie_dist) {
			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_table_insert
 *	Purpose:
 *		Inserts an entry into the space's reverse hash table.
 *	Conditions:
 *		The space must be write-locked.
 */

void
ipc_hash_table_insert(
	ipc_entry_table_t               array,
	ipc_object_t                    obj,
	mach_port_index_t               index,
	__assert_only ipc_entry_t       entry)
{
	mach_port_index_t hindex, hdist;
	ipc_entry_t       table = ipc_entry_table_base(array);
	ipc_entry_num_t   size  = ipc_entry_table_count(array);

	assert(index != 0);
	assert(obj != IO_NULL);

	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 (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_table_delete
 *	Purpose:
 *		Deletes an entry from the table's reverse hash.
 *	Conditions:
 *		Exclusive access to the table.
 */

void
ipc_hash_table_delete(
	ipc_entry_table_t               array,
	ipc_object_t                    obj,
	mach_port_index_t               index,
	__assert_only ipc_entry_t       entry)
{
	mach_port_index_t hindex, dindex, dist;
	ipc_entry_t       table = ipc_entry_table_base(array);
	ipc_entry_num_t   size  = ipc_entry_table_count(array);

	assert(index != MACH_PORT_NULL);
	assert(obj != IO_NULL);

	hindex = IH_TABLE_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 (++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 + 1;
		if (dindex == size) {
			dindex = 0;
		}

		/*
		 * 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;
		}

		/*
		 * 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;
			}
		}

		/*
		 * 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;
	}
}