#include <mach_kdb.h>
#include <mach_debug.h>
#include <mach/kern_return.h>
#include <mach/port.h>
#include <kern/assert.h>
#include <kern/sched_prim.h>
#include <kern/zalloc.h>
#include <kern/misc_protos.h>
#if MACH_KDB
#include <kern/task.h>
#endif
#include <ipc/port.h>
#include <ipc/ipc_entry.h>
#include <ipc/ipc_space.h>
#include <ipc/ipc_splay.h>
#include <ipc/ipc_object.h>
#include <ipc/ipc_hash.h>
#include <ipc/ipc_table.h>
#include <ipc/ipc_port.h>
#include <string.h>
zone_t ipc_tree_entry_zone;
boolean_t ipc_entry_tree_collision(
ipc_space_t space,
mach_port_name_t name);
boolean_t
ipc_entry_tree_collision(
ipc_space_t space,
mach_port_name_t name)
{
mach_port_index_t index;
mach_port_name_t lower, upper;
assert(space->is_active);
ipc_splay_tree_bounds(&space->is_tree, name, &lower, &upper);
index = MACH_PORT_INDEX(name);
return (((lower != ~0) && (MACH_PORT_INDEX(lower) == index)) ||
((upper != 0) && (MACH_PORT_INDEX(upper) == index)));
}
ipc_entry_t
ipc_entry_lookup(
ipc_space_t space,
mach_port_name_t name)
{
mach_port_index_t index;
ipc_entry_t entry;
assert(space->is_active);
index = MACH_PORT_INDEX(name);
if (is_fast_space(space)) {
entry = &space->is_table[index];
if (IE_BITS_GEN(entry->ie_bits) != MACH_PORT_GEN(name) ||
IE_BITS_TYPE(entry->ie_bits) == MACH_PORT_TYPE_NONE)
entry = IE_NULL;
}
else
if (index < space->is_table_size) {
entry = &space->is_table[index];
if (IE_BITS_GEN(entry->ie_bits) != MACH_PORT_GEN(name))
if (entry->ie_bits & IE_BITS_COLLISION) {
assert(space->is_tree_total > 0);
goto tree_lookup;
} else
entry = IE_NULL;
else if (IE_BITS_TYPE(entry->ie_bits) == MACH_PORT_TYPE_NONE)
entry = IE_NULL;
} else if (space->is_tree_total == 0)
entry = IE_NULL;
else {
tree_lookup:
entry = (ipc_entry_t)
ipc_splay_tree_lookup(&space->is_tree, name);
if(entry != IE_NULL) {
if(!(IE_BITS_TYPE(entry->ie_bits)))
entry = IE_NULL;
}
}
assert((entry == IE_NULL) || IE_BITS_TYPE(entry->ie_bits));
return entry;
}
kern_return_t
ipc_entry_get(
ipc_space_t space,
mach_port_name_t *namep,
ipc_entry_t *entryp)
{
ipc_entry_t table;
mach_port_index_t first_free;
ipc_entry_t free_entry;
assert(space->is_active);
{
table = space->is_table;
first_free = table->ie_next;
if (first_free == 0)
return KERN_NO_SPACE;
free_entry = &table[first_free];
table->ie_next = free_entry->ie_next;
}
{
mach_port_name_t new_name;
mach_port_gen_t gen;
gen = IE_BITS_NEW_GEN(free_entry->ie_bits);
free_entry->ie_bits = gen;
free_entry->ie_request = 0;
new_name = MACH_PORT_MAKE(first_free, gen);
assert(MACH_PORT_VALID(new_name));
*namep = new_name;
}
assert(free_entry->ie_object == IO_NULL);
*entryp = free_entry;
return KERN_SUCCESS;
}
kern_return_t
ipc_entry_alloc(
ipc_space_t space,
mach_port_name_t *namep,
ipc_entry_t *entryp)
{
kern_return_t kr;
is_write_lock(space);
for (;;) {
if (!space->is_active) {
is_write_unlock(space);
return KERN_INVALID_TASK;
}
kr = ipc_entry_get(space, namep, entryp);
if (kr == KERN_SUCCESS)
return kr;
kr = ipc_entry_grow_table(space, ITS_SIZE_NONE);
if (kr != KERN_SUCCESS)
return kr;
}
}
kern_return_t
ipc_entry_alloc_name(
ipc_space_t space,
mach_port_name_t name,
ipc_entry_t *entryp)
{
mach_port_index_t index = MACH_PORT_INDEX(name);
mach_port_gen_t gen = MACH_PORT_GEN(name);
ipc_tree_entry_t tentry = ITE_NULL;
assert(MACH_PORT_VALID(name));
is_write_lock(space);
for (;;) {
ipc_entry_t entry;
ipc_tree_entry_t tentry2;
ipc_table_size_t its;
if (!space->is_active) {
is_write_unlock(space);
if (tentry) ite_free(tentry);
return KERN_INVALID_TASK;
}
if (index < space->is_table_size) {
ipc_entry_t table = space->is_table;
entry = &table[index];
if (index == 0) {
assert(!IE_BITS_TYPE(entry->ie_bits));
assert(!IE_BITS_GEN(entry->ie_bits));
} else if (IE_BITS_TYPE(entry->ie_bits)) {
if (IE_BITS_GEN(entry->ie_bits) == gen) {
*entryp = entry;
assert(!tentry);
return KERN_SUCCESS;
}
} else {
mach_port_index_t free_index, next_index;
for (free_index = 0;
(next_index = table[free_index].ie_next)
!= index;
free_index = next_index)
continue;
table[free_index].ie_next =
table[next_index].ie_next;
entry->ie_bits = gen;
entry->ie_request = 0;
*entryp = entry;
assert(entry->ie_object == IO_NULL);
if (is_fast_space(space))
assert(!tentry);
else if (tentry)
ite_free(tentry);
return KERN_SUCCESS;
}
}
if (is_fast_space(space)) {
is_write_unlock(space);
assert(!tentry);
return KERN_FAILURE;
}
if ((space->is_tree_total > 0) &&
((tentry2 = ipc_splay_tree_lookup(&space->is_tree, name))
!= ITE_NULL)) {
assert(tentry2->ite_space == space);
assert(IE_BITS_TYPE(tentry2->ite_bits));
*entryp = &tentry2->ite_entry;
if (tentry) ite_free(tentry);
return KERN_SUCCESS;
}
its = space->is_table_next;
if ((space->is_table_size <= index) &&
(index < its->its_size) &&
(((its->its_size - space->is_table_size) *
sizeof(struct ipc_entry)) <
((space->is_tree_small + 1) *
sizeof(struct ipc_tree_entry)))) {
kern_return_t kr;
kr = ipc_entry_grow_table(space, ITS_SIZE_NONE);
assert(kr != KERN_NO_SPACE);
if (kr != KERN_SUCCESS) {
if (tentry) ite_free(tentry);
return kr;
}
continue;
}
if (tentry != ITE_NULL) {
space->is_tree_total++;
if (index < space->is_table_size) {
entry = &space->is_table[index];
entry->ie_bits |= IE_BITS_COLLISION;
} else if ((index < its->its_size) &&
!ipc_entry_tree_collision(space, name))
space->is_tree_small++;
ipc_splay_tree_insert(&space->is_tree, name, tentry);
tentry->ite_bits = 0;
tentry->ite_request = 0;
tentry->ite_object = IO_NULL;
tentry->ite_space = space;
*entryp = &tentry->ite_entry;
return KERN_SUCCESS;
}
is_write_unlock(space);
tentry = ite_alloc();
if (tentry == ITE_NULL)
return KERN_RESOURCE_SHORTAGE;
is_write_lock(space);
}
}
void
ipc_entry_dealloc(
ipc_space_t space,
mach_port_name_t name,
ipc_entry_t entry)
{
ipc_entry_t table;
ipc_entry_num_t size;
mach_port_index_t index;
assert(space->is_active);
assert(entry->ie_object == IO_NULL);
assert(entry->ie_request == 0);
index = MACH_PORT_INDEX(name);
table = space->is_table;
size = space->is_table_size;
if (is_fast_space(space)) {
assert(index < size);
assert(entry == &table[index]);
assert(IE_BITS_GEN(entry->ie_bits) == MACH_PORT_GEN(name));
assert(!(entry->ie_bits & IE_BITS_COLLISION));
entry->ie_bits &= IE_BITS_GEN_MASK;
entry->ie_next = table->ie_next;
table->ie_next = index;
return;
}
if ((index < size) && (entry == &table[index])) {
assert(IE_BITS_GEN(entry->ie_bits) == MACH_PORT_GEN(name));
if (entry->ie_bits & IE_BITS_COLLISION) {
struct ipc_splay_tree small, collisions;
ipc_tree_entry_t tentry;
mach_port_name_t tname;
boolean_t pick;
ipc_entry_bits_t bits;
ipc_object_t obj;
ipc_splay_tree_split(&space->is_tree,
MACH_PORT_MAKE(index+1, 0),
&collisions);
ipc_splay_tree_split(&collisions,
MACH_PORT_MAKE(index, 0),
&small);
pick = ipc_splay_tree_pick(&collisions,
&tname, &tentry);
assert(pick);
assert(MACH_PORT_INDEX(tname) == index);
entry->ie_object = obj = tentry->ite_object;
entry->ie_bits = tentry->ite_bits|MACH_PORT_GEN(tname);
entry->ie_request = tentry->ite_request;
assert(tentry->ite_space == space);
if (IE_BITS_TYPE(tentry->ite_bits)==MACH_PORT_TYPE_SEND) {
ipc_hash_global_delete(space, obj,
tname, tentry);
ipc_hash_local_insert(space, obj,
index, entry);
}
ipc_splay_tree_delete(&collisions, tname, tentry);
assert(space->is_tree_total > 0);
space->is_tree_total--;
pick = ipc_splay_tree_pick(&collisions,
&tname, &tentry);
if (pick) {
entry->ie_bits |= IE_BITS_COLLISION;
ipc_splay_tree_join(&space->is_tree,
&collisions);
}
ipc_splay_tree_join(&space->is_tree, &small);
} else {
entry->ie_bits &= IE_BITS_GEN_MASK;
entry->ie_next = table->ie_next;
table->ie_next = index;
}
} else {
ipc_tree_entry_t tentry = (ipc_tree_entry_t) entry;
assert(tentry->ite_space == space);
ipc_splay_tree_delete(&space->is_tree, name, tentry);
assert(space->is_tree_total > 0);
space->is_tree_total--;
if (index < size) {
ipc_entry_t ientry = &table[index];
assert(ientry->ie_bits & IE_BITS_COLLISION);
if (!ipc_entry_tree_collision(space, name))
ientry->ie_bits &= ~IE_BITS_COLLISION;
} else if ((index < space->is_table_next->its_size) &&
!ipc_entry_tree_collision(space, name)) {
assert(space->is_tree_small > 0);
space->is_tree_small--;
}
}
}
kern_return_t
ipc_entry_grow_table(
ipc_space_t space,
int target_size)
{
ipc_entry_num_t osize, size, nsize, psize;
do {
boolean_t reallocated=FALSE;
ipc_entry_t otable, table;
ipc_table_size_t oits, its, nits;
mach_port_index_t i, free_index;
assert(space->is_active);
if (space->is_growing) {
assert_wait((event_t) space, THREAD_UNINT);
is_write_unlock(space);
thread_block((void (*)(void)) 0);
is_write_lock(space);
return KERN_SUCCESS;
}
otable = space->is_table;
its = space->is_table_next;
size = its->its_size;
oits = its - 1;
osize = oits->its_size;
if (target_size != ITS_SIZE_NONE) {
if (target_size <= osize) {
is_write_unlock(space);
return KERN_SUCCESS;
}
psize = osize;
while ((psize != size) && (target_size > size)) {
psize = size;
its++;
size = its->its_size;
}
if (psize == size) {
is_write_unlock(space);
return KERN_NO_SPACE;
}
}
nits = its + 1;
nsize = nits->its_size;
if (osize == size) {
is_write_unlock(space);
return KERN_NO_SPACE;
}
assert((osize < size) && (size <= nsize));
space->is_growing = TRUE;
is_write_unlock(space);
if (it_entries_reallocable(oits)) {
table = it_entries_realloc(oits, otable, its);
reallocated=TRUE;
}
else {
table = it_entries_alloc(its);
}
is_write_lock(space);
space->is_growing = FALSE;
if (table == IE_NULL) {
is_write_unlock(space);
thread_wakeup((event_t) space);
return KERN_RESOURCE_SHORTAGE;
}
if (!space->is_active) {
is_write_unlock(space);
thread_wakeup((event_t) space);
it_entries_free(its, table);
is_write_lock(space);
return KERN_SUCCESS;
}
assert(space->is_table == otable);
assert((space->is_table_next == its) ||
(target_size != ITS_SIZE_NONE));
assert(space->is_table_size == osize);
space->is_table = table;
space->is_table_size = size;
space->is_table_next = nits;
if (!reallocated)
(void) memcpy((void *) table, (const void *) otable,
osize * (sizeof(struct ipc_entry)));
for (i = 0; i < osize; i++)
table[i].ie_index = 0;
(void) memset((void *) (table + osize) , 0,
((size - osize) * (sizeof(struct ipc_entry))));
for (i = 0; i < osize; i++) {
ipc_entry_t entry = &table[i];
if (IE_BITS_TYPE(entry->ie_bits)==MACH_PORT_TYPE_SEND) {
ipc_hash_local_insert(space, entry->ie_object,
i, entry);
}
}
assert(!is_fast_space(space) || space->is_tree_total == 0);
if (space->is_tree_total > 0) {
mach_port_index_t index;
boolean_t delete;
struct ipc_splay_tree ignore;
struct ipc_splay_tree move;
struct ipc_splay_tree small;
ipc_entry_num_t nosmall;
ipc_tree_entry_t tentry;
ipc_splay_tree_split(&space->is_tree,
MACH_PORT_MAKE(nsize, 0),
&small);
ipc_splay_tree_split(&small,
MACH_PORT_MAKE(size, 0),
&move);
ipc_splay_tree_split(&move,
MACH_PORT_MAKE(osize, 0),
&ignore);
for (tentry = ipc_splay_traverse_start(&move);
tentry != ITE_NULL;
tentry = ipc_splay_traverse_next(&move, delete)) {
mach_port_name_t name;
mach_port_gen_t gen;
mach_port_type_t type;
ipc_entry_bits_t bits;
ipc_object_t obj;
ipc_entry_t entry;
name = tentry->ite_name;
gen = MACH_PORT_GEN(name);
index = MACH_PORT_INDEX(name);
assert(tentry->ite_space == space);
assert((osize <= index) && (index < size));
entry = &table[index];
bits = entry->ie_bits;
if (IE_BITS_TYPE(bits)) {
assert(IE_BITS_GEN(bits) != gen);
entry->ie_bits |= IE_BITS_COLLISION;
delete = FALSE;
continue;
}
bits = tentry->ite_bits;
type = IE_BITS_TYPE(bits);
assert(type != MACH_PORT_TYPE_NONE);
entry->ie_bits = bits | gen;
entry->ie_request = tentry->ite_request;
entry->ie_object = obj = tentry->ite_object;
if (type == MACH_PORT_TYPE_SEND) {
ipc_hash_global_delete(space, obj,
name, tentry);
ipc_hash_local_insert(space, obj,
index, entry);
}
space->is_tree_total--;
delete = TRUE;
}
ipc_splay_traverse_finish(&move);
nosmall = 0; index = 0;
for (tentry = ipc_splay_traverse_start(&small);
tentry != ITE_NULL;
tentry = ipc_splay_traverse_next(&small, FALSE)) {
mach_port_index_t nindex;
nindex = MACH_PORT_INDEX(tentry->ite_name);
if (nindex != index) {
nosmall++;
index = nindex;
}
}
ipc_splay_traverse_finish(&small);
assert(nosmall <= (nsize - size));
assert(nosmall <= space->is_tree_total);
space->is_tree_small = nosmall;
ipc_splay_tree_join(&space->is_tree, &small);
ipc_splay_tree_join(&space->is_tree, &move);
ipc_splay_tree_join(&space->is_tree, &ignore);
}
free_index = table[0].ie_next;
for (i = size-1; i >= osize; --i) {
ipc_entry_t entry = &table[i];
if (entry->ie_bits == 0) {
entry->ie_bits = IE_BITS_GEN_MASK;
entry->ie_next = free_index;
free_index = i;
}
}
table[0].ie_next = free_index;
is_write_unlock(space);
thread_wakeup((event_t) space);
it_entries_free(oits, otable);
is_write_lock(space);
if (!space->is_active || (space->is_table_next != nits))
return KERN_SUCCESS;
} while ((space->is_tree_small > 0) &&
(((nsize - size) * sizeof(struct ipc_entry)) <
(space->is_tree_small * sizeof(struct ipc_tree_entry))));
return KERN_SUCCESS;
}
#if MACH_KDB
#include <ddb/db_output.h>
#define printf kdbprintf
ipc_entry_t db_ipc_object_by_name(
task_t task,
mach_port_name_t name);
ipc_entry_t
db_ipc_object_by_name(
task_t task,
mach_port_name_t name)
{
ipc_space_t space = task->itk_space;
ipc_entry_t entry;
entry = ipc_entry_lookup(space, name);
if(entry != IE_NULL) {
iprintf("(task 0x%x, name 0x%x) ==> object 0x%x\n",
task, name, entry->ie_object);
return (ipc_entry_t) entry->ie_object;
}
return entry;
}
#endif