[apple/xnu.git] / osfmk / ipc / ipc_entry.h

/*
 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
 * 
 * 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. 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_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.
 */
/*
 */
/*
 *	File:	ipc/ipc_entry.h
 *	Author:	Rich Draves
 *	Date:	1989
 *
 *	Definitions for translation entries, which represent
 *	tasks' capabilities for ports and port sets.
 */

#ifndef	_IPC_IPC_ENTRY_H_
#define _IPC_IPC_ENTRY_H_

#include <mach/port.h>
#include <mach/kern_return.h>
#include <kern/zalloc.h>
#include <ipc/port.h>
#include <ipc/ipc_table.h>
#include <ipc/ipc_types.h>

/*
 *	Spaces hold capabilities for ipc_object_t's.
 *	Each ipc_entry_t records a capability.  Most capabilities have
 *	small names, and the entries are elements of a table.
 *	Capabilities can have large names, and a splay tree holds
 *	those entries.  The cutoff point between the table and the tree
 *	is adjusted dynamically to minimize memory consumption.
 *
 *	The ie_index field of entries in the table implements
 *	a ordered hash table with open addressing and linear probing.
 *	This hash table converts (space, object) -> name.
 *	It is used independently of the other fields.
 *
 *	Free (unallocated) entries in the table have null ie_object
 *	fields.  The ie_bits field is zero except for IE_BITS_GEN.
 *	The ie_next (ie_request) field links free entries into a free list.
 *
 *	The first entry in the table (index 0) is always free.
 *	It is used as the head of the free list.
 */

typedef natural_t ipc_entry_bits_t;
typedef ipc_table_elems_t ipc_entry_num_t;	/* number of entries */

typedef struct ipc_entry {
	struct ipc_object *ie_object;
	ipc_entry_bits_t ie_bits;
	union {
		mach_port_index_t next;		/* next in freelist, or...  */
		ipc_table_index_t request;	/* dead name request notify */
	} index;
	union {
		mach_port_index_t table;
		struct ipc_tree_entry *tree;
	} hash;
} *ipc_entry_t;

#define	IE_NULL		((ipc_entry_t) 0)

#define	ie_request	index.request
#define	ie_next		index.next
#define	ie_index	hash.table

#define	IE_BITS_UREFS_MASK	0x0000ffff	/* 16 bits of user-reference */
#define	IE_BITS_UREFS(bits)	((bits) & IE_BITS_UREFS_MASK)

#define	IE_BITS_TYPE_MASK	0x001f0000	/* 5 bits of capability type */
#define	IE_BITS_TYPE(bits)	((bits) & IE_BITS_TYPE_MASK)

#define	IE_BITS_COLLISION	0x00800000	/* 1 bit for collisions */


#ifndef NO_PORT_GEN
#define	IE_BITS_GEN_MASK	0xff000000	/* 8 bits for generation */
#define	IE_BITS_GEN(bits)	((bits) & IE_BITS_GEN_MASK)
#define	IE_BITS_GEN_ONE		0x04000000	/* low bit of generation */
#define IE_BITS_NEW_GEN(old)	(((old) + IE_BITS_GEN_ONE) & IE_BITS_GEN_MASK)
#else
#define	IE_BITS_GEN_MASK	0
#define	IE_BITS_GEN(bits)	0
#define	IE_BITS_GEN_ONE		0
#define IE_BITS_NEW_GEN(old)	(old)
#endif	/* !USE_PORT_GEN */


#define	IE_BITS_RIGHT_MASK	0x007fffff	/* relevant to the right */

typedef struct ipc_tree_entry {
	struct ipc_entry ite_entry;
	mach_port_name_t ite_name;
	struct ipc_space *ite_space;
	struct ipc_tree_entry *ite_lchild;
	struct ipc_tree_entry *ite_rchild;
} *ipc_tree_entry_t;

#define	ITE_NULL	((ipc_tree_entry_t) 0)

#define	ite_bits	ite_entry.ie_bits
#define	ite_object	ite_entry.ie_object
#define	ite_request	ite_entry.ie_request
#define	ite_next	ite_entry.hash.tree

extern zone_t ipc_tree_entry_zone;

#define ite_alloc()	((ipc_tree_entry_t) zalloc(ipc_tree_entry_zone))
#define	ite_free(ite)	zfree(ipc_tree_entry_zone, (vm_offset_t) (ite))

/*
 * Exported interfaces
 */

/* Search for entry in a space by name */
extern ipc_entry_t ipc_entry_lookup(
	ipc_space_t		space,
	mach_port_name_t	name);

/* Allocate an entry in a space */
extern kern_return_t ipc_entry_get(
	ipc_space_t		space,
	mach_port_name_t	*namep,
	ipc_entry_t		*entryp);

/* Allocate an entry in a space, growing the space if necessary */
extern kern_return_t ipc_entry_alloc(
	ipc_space_t		space,
	mach_port_name_t	*namep,
	ipc_entry_t		*entryp);

/* Allocate/find an entry in a space with a specific name */
extern kern_return_t ipc_entry_alloc_name(
	ipc_space_t		space,
	mach_port_name_t	name,
	ipc_entry_t		*entryp);

/* Deallocate an entry from a space */
extern void ipc_entry_dealloc(
	ipc_space_t		space,
	mach_port_name_t	name,
	ipc_entry_t		entry);

/* Grow the table in a space */
extern kern_return_t ipc_entry_grow_table(
	ipc_space_t	space,
	int		target_size);

#endif	/* _IPC_IPC_ENTRY_H_ */
Commit	Line	Data
1c79356b A	1	/*
	2	* Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
	3	*
	4	* @APPLE_LICENSE_HEADER_START@
	5	*
43866e37	6	* Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
1c79356b	7	*
43866e37 A	8	* This file contains Original Code and/or Modifications of Original Code
	9	* as defined in and that are subject to the Apple Public Source License
	10	* Version 2.0 (the 'License'). You may not use this file except in
	11	* compliance with the License. Please obtain a copy of the License at
	12	* http://www.opensource.apple.com/apsl/ and read it before using this
	13	* file.
	14	*
	15	* The Original Code and all software distributed under the License are
	16	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
1c79356b A	17	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
1c79356b A	18	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
43866e37 A	19	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	20	* Please see the License for the specific language governing rights and
	21	* limitations under the License.
1c79356b A	22	*
	23	* @APPLE_LICENSE_HEADER_END@
	24	*/
	25	/*
	26	* @OSF_COPYRIGHT@
	27	*/
	28	/*
	29	* Mach Operating System
	30	* Copyright (c) 1991,1990,1989 Carnegie Mellon University
	31	* All Rights Reserved.
	32	*
	33	* Permission to use, copy, modify and distribute this software and its
	34	* documentation is hereby granted, provided that both the copyright
	35	* notice and this permission notice appear in all copies of the
	36	* software, derivative works or modified versions, and any portions
	37	* thereof, and that both notices appear in supporting documentation.
	38	*
	39	* CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
	40	* CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
	41	* ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
	42	*
	43	* Carnegie Mellon requests users of this software to return to
	44	*
	45	* Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
	46	* School of Computer Science
	47	* Carnegie Mellon University
	48	* Pittsburgh PA 15213-3890
	49	*
	50	* any improvements or extensions that they make and grant Carnegie Mellon
	51	* the rights to redistribute these changes.
	52	*/
	53	/*
	54	*/
	55	/*
	56	* File: ipc/ipc_entry.h
	57	* Author: Rich Draves
	58	* Date: 1989
	59	*
	60	* Definitions for translation entries, which represent
	61	* tasks' capabilities for ports and port sets.
	62	*/
	63
	64	#ifndef _IPC_IPC_ENTRY_H_
	65	#define _IPC_IPC_ENTRY_H_
	66
	67	#include <mach/port.h>
	68	#include <mach/kern_return.h>
	69	#include <kern/zalloc.h>
	70	#include <ipc/port.h>
	71	#include <ipc/ipc_table.h>
	72	#include <ipc/ipc_types.h>
	73
	74	/*
	75	* Spaces hold capabilities for ipc_object_t's.
	76	* Each ipc_entry_t records a capability. Most capabilities have
	77	* small names, and the entries are elements of a table.
	78	* Capabilities can have large names, and a splay tree holds
	79	* those entries. The cutoff point between the table and the tree
	80	* is adjusted dynamically to minimize memory consumption.
	81	*
	82	* The ie_index field of entries in the table implements
	83	* a ordered hash table with open addressing and linear probing.
	84	* This hash table converts (space, object) -> name.
	85	* It is used independently of the other fields.
86	*
87	* Free (unallocated) entries in the table have null ie_object
88	* fields. The ie_bits field is zero except for IE_BITS_GEN.
89	* The ie_next (ie_request) field links free entries into a free list.
90	*
91	* The first entry in the table (index 0) is always free.
92	* It is used as the head of the free list.
93	*/
94
95	typedef natural_t ipc_entry_bits_t;
96	typedef ipc_table_elems_t ipc_entry_num_t; /* number of entries */
97
98	typedef struct ipc_entry {
99	struct ipc_object *ie_object;
100	ipc_entry_bits_t ie_bits;
101	union {
102	mach_port_index_t next; /* next in freelist, or... */
103	ipc_table_index_t request; /* dead name request notify */
104	} index;
105	union {
106	mach_port_index_t table;
107	struct ipc_tree_entry *tree;
108	} hash;
109	} *ipc_entry_t;
110
111	#define IE_NULL ((ipc_entry_t) 0)
112
113	#define ie_request index.request
114	#define ie_next index.next
115	#define ie_index hash.table
116
117	#define IE_BITS_UREFS_MASK 0x0000ffff /* 16 bits of user-reference */
118	#define IE_BITS_UREFS(bits) ((bits) & IE_BITS_UREFS_MASK)
119
120	#define IE_BITS_TYPE_MASK 0x001f0000 /* 5 bits of capability type */
121	#define IE_BITS_TYPE(bits) ((bits) & IE_BITS_TYPE_MASK)
122
123	#define IE_BITS_COLLISION 0x00800000 /* 1 bit for collisions */
124
125
126	#ifndef NO_PORT_GEN
127	#define IE_BITS_GEN_MASK 0xff000000 /* 8 bits for generation */
128	#define IE_BITS_GEN(bits) ((bits) & IE_BITS_GEN_MASK)
129	#define IE_BITS_GEN_ONE 0x04000000 /* low bit of generation */
130	#define IE_BITS_NEW_GEN(old) (((old) + IE_BITS_GEN_ONE) & IE_BITS_GEN_MASK)
131	#else
132	#define IE_BITS_GEN_MASK 0
133	#define IE_BITS_GEN(bits) 0
134	#define IE_BITS_GEN_ONE 0
135	#define IE_BITS_NEW_GEN(old) (old)
136	#endif /* !USE_PORT_GEN */
137
138
139	#define IE_BITS_RIGHT_MASK 0x007fffff /* relevant to the right */
140
141	typedef struct ipc_tree_entry {
142	struct ipc_entry ite_entry;
143	mach_port_name_t ite_name;
144	struct ipc_space *ite_space;
145	struct ipc_tree_entry *ite_lchild;
146	struct ipc_tree_entry *ite_rchild;
147	} *ipc_tree_entry_t;
148
149	#define ITE_NULL ((ipc_tree_entry_t) 0)
150
151	#define ite_bits ite_entry.ie_bits
152	#define ite_object ite_entry.ie_object
153	#define ite_request ite_entry.ie_request
154	#define ite_next ite_entry.hash.tree
155
156	extern zone_t ipc_tree_entry_zone;
157
158	#define ite_alloc() ((ipc_tree_entry_t) zalloc(ipc_tree_entry_zone))
159	#define ite_free(ite) zfree(ipc_tree_entry_zone, (vm_offset_t) (ite))
160
161	/*
162	* Exported interfaces
163	*/
164
165	/* Search for entry in a space by name */
166	extern ipc_entry_t ipc_entry_lookup(
167	ipc_space_t space,
168	mach_port_name_t name);
169
170	/* Allocate an entry in a space */
171	extern kern_return_t ipc_entry_get(
172	ipc_space_t space,
173	mach_port_name_t *namep,
174	ipc_entry_t *entryp);
175
176	/* Allocate an entry in a space, growing the space if necessary */
177	extern kern_return_t ipc_entry_alloc(
178	ipc_space_t space,
179	mach_port_name_t *namep,
180	ipc_entry_t *entryp);
181
182	/* Allocate/find an entry in a space with a specific name */
183	extern kern_return_t ipc_entry_alloc_name(
184	ipc_space_t space,
185	mach_port_name_t name,
186	ipc_entry_t *entryp);
187
188	/* Deallocate an entry from a space */
189	extern void ipc_entry_dealloc(
190	ipc_space_t space,
191	mach_port_name_t name,
192	ipc_entry_t entry);
193
194	/* Grow the table in a space */
195	extern kern_return_t ipc_entry_grow_table(
196	ipc_space_t space,
197	int target_size);
198
199	#endif /* _IPC_IPC_ENTRY_H_ */