#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 <mach_ipc_debug.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>
#endif
boolean_t ipc_hash_global_lookup(
ipc_space_t space,
ipc_object_t obj,
mach_port_name_t *namep,
ipc_tree_entry_t *entryp);
void ipc_hash_global_insert(
ipc_space_t space,
ipc_object_t obj,
mach_port_name_t name,
ipc_tree_entry_t entry);
void ipc_hash_local_delete(
ipc_space_t space,
ipc_object_t obj,
mach_port_index_t index,
ipc_entry_t entry);
boolean_t
ipc_hash_lookup(
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);
}
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);
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);
}
}
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);
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);
}
}
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_mutex_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) mutex_init(&(ihgb)->ihgb_lock_data, \
ETAP_IPC_IHGB)
#define ihgb_lock(ihgb) mutex_lock(&(ihgb)->ihgb_lock_data)
#define ihgb_unlock(ihgb) mutex_unlock(&(ihgb)->ihgb_lock_data)
ipc_hash_global_bucket_t ipc_hash_global_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)
{
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)) {
*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)) {
*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;
}
void
ipc_hash_global_insert(
ipc_space_t space,
ipc_object_t obj,
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);
entry->ite_next = bucket->ihgb_head;
bucket->ihgb_head = entry;
ihgb_unlock(bucket);
}
void
ipc_hash_global_delete(
ipc_space_t space,
ipc_object_t obj,
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) {
*last = this->ite_next;
break;
}
}
assert(this != ITE_NULL);
ihgb_unlock(bucket);
}
#define IH_LOCAL_HASH(obj, size) \
((((mach_port_index_t) (obj)) >> 6) % (size))
boolean_t
ipc_hash_local_lookup(
ipc_space_t space,
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;
assert(space != IS_NULL);
assert(obj != IO_NULL);
table = space->is_table;
size = space->is_table_size;
hindex = IH_LOCAL_HASH(obj, size);
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 (++hindex == size)
hindex = 0;
}
return FALSE;
}
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);
while (table[hindex].ie_index != 0) {
if (++hindex == size)
hindex = 0;
}
table[hindex].ie_index = index;
}
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);
while (table[hindex].ie_index != index) {
if (++hindex == size)
hindex = 0;
}
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);
index = table[dindex].ie_index;
if (index == 0)
break;
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;
}
}
void
ipc_hash_init(void)
{
ipc_hash_index_t i;
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;
}
ipc_hash_global_mask = ipc_hash_global_size - 1;
if ((ipc_hash_global_size & ipc_hash_global_mask) != 0) {
natural_t bit;
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;
}
}
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);
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
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);
info[i].hib_count = bucket_count;
}
return ipc_hash_global_size;
}
#endif