1 /*
2 * Copyright (c) 2000-2004 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28 /*
29 * @OSF_COPYRIGHT@
30 */
31 /*
32 * Mach Operating System
33 * Copyright (c) 1991,1990,1989 Carnegie Mellon University
34 * All Rights Reserved.
35 *
36 * Permission to use, copy, modify and distribute this software and its
37 * documentation is hereby granted, provided that both the copyright
38 * notice and this permission notice appear in all copies of the
39 * software, derivative works or modified versions, and any portions
40 * thereof, and that both notices appear in supporting documentation.
41 *
42 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
43 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
44 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
45 *
46 * Carnegie Mellon requests users of this software to return to
47 *
48 * Software Distribution Coordinator or [email protected]
49 * School of Computer Science
50 * Carnegie Mellon University
51 * Pittsburgh PA 15213-3890
52 *
53 * any improvements or extensions that they make and grant Carnegie Mellon
54 * the rights to redistribute these changes.
55 */
56 /*
57 */
58 /*
59 * File: ipc/ipc_entry.h
60 * Author: Rich Draves
61 * Date: 1989
62 *
63 * Definitions for translation entries, which represent
64 * tasks' capabilities for ports and port sets.
65 */
66
67 #ifndef _IPC_IPC_ENTRY_H_
68 #define _IPC_IPC_ENTRY_H_
69
70 #include <mach/mach_types.h>
71 #include <mach/port.h>
72 #include <mach/kern_return.h>
73
74 #include <kern/kern_types.h>
75 #include <kern/kalloc.h>
76 #include <kern/smr_types.h>
77
78 #include <ipc/ipc_types.h>
79
80 /*
81 * Spaces hold capabilities for ipc_object_t's.
82 * Each ipc_entry_t records a capability. Most capabilities have
83 * small names, and the entries are elements of a table.
84 *
85 * The ie_index field of entries in the table implements
86 * a ordered hash table with open addressing and linear probing.
87 *
88 * The ie_dist field holds the distance to the desired spot,
89 * which is used to implement robin-hood hashing.
90 *
91 * This hash table converts (space, object) -> name.
92 * It is used independently of the other fields.
93 *
94 * Free (unallocated) entries in the table have null ie_object
95 * fields. The ie_bits field is zero except for IE_BITS_GEN.
96 * The ie_next (ie_request) field links free entries into a free list.
97 *
98 * The first entry in the table (index 0) is always free.
99 * It is used as the head of the free list.
100 */
101
102 #define IPC_ENTRY_DIST_BITS 12
103 #define IPC_ENTRY_DIST_MAX ((1 << IPC_ENTRY_DIST_BITS) - 1)
104 #define IPC_ENTRY_INDEX_BITS 32
105 #define IPC_ENTRY_INDEX_MAX (UINT32_MAX)
106
107 struct ipc_entry {
108 union {
109 struct ipc_object *XNU_PTRAUTH_SIGNED_PTR("ipc_entry.ie_object") ie_object;
110 struct ipc_port *XNU_PTRAUTH_SIGNED_PTR("ipc_entry.ie_object") ie_port;
111 struct ipc_pset *XNU_PTRAUTH_SIGNED_PTR("ipc_entry.ie_object") ie_pset;
112 struct ipc_object *XNU_PTRAUTH_SIGNED_PTR("ipc_entry.ie_object") volatile ie_volatile_object;
113 struct ipc_entry_table *XNU_PTRAUTH_SIGNED_PTR("ipc_entry.ie_self") ie_self;
114 };
115 union {
116 struct {
117 ipc_entry_bits_t ie_bits;
118 union {
119 mach_port_index_t ie_next; /* next in freelist, or... */
120 ipc_table_index_t ie_request; /* dead name request notify */
121 };
122
123 /* hash fields */
124 uint32_t ie_dist;
125 mach_port_index_t ie_index;
126 };
127 struct smr_node ie_smr_node;
128 };
129 };
130
131 #define IPC_ENTRY_TABLE_MIN 32
132 #define IPC_ENTRY_TABLE_PERIOD 16
133 KALLOC_ARRAY_TYPE_DECL(ipc_entry_table, struct ipc_entry);
134
135 #define IE_REQ_NONE 0 /* no request */
136
137 #define IE_BITS_UREFS_MASK 0x0000ffff /* 16 bits of user-reference */
138 #define IE_BITS_UREFS(bits) ((bits) & IE_BITS_UREFS_MASK)
139
140 #define IE_BITS_TYPE_MASK 0x001f0000 /* 5 bits of capability type */
141 #define IE_BITS_TYPE(bits) ((bits) & IE_BITS_TYPE_MASK)
142
143 #define IE_BITS_EXTYPE_MASK 0x00200000 /* 1 bit for extended capability */
144
145 #ifndef NO_PORT_GEN
146 #define IE_BITS_GEN_MASK 0xff000000 /* 8 bits for generation */
147 #define IE_BITS_GEN(bits) ((bits) & IE_BITS_GEN_MASK)
148 #define IE_BITS_GEN_ONE 0x04000000 /* low bit of generation */
149 #define IE_BITS_ROLL_POS 22 /* LSB pos of generation rollover */
150 #define IE_BITS_ROLL_BITS 2 /* number of generation rollover bits */
151 #define IE_BITS_ROLL_MASK (((1 << IE_BITS_ROLL_BITS) - 1) << IE_BITS_ROLL_POS)
152 #define IE_BITS_ROLL(bits) ((((bits) & IE_BITS_ROLL_MASK) << 8) ^ IE_BITS_GEN_MASK)
153
154 /*
155 * Restart a generation counter with the specified bits for the rollover point.
156 * There are 4 different rollover points:
157 * bits rollover period
158 * 0 0 64
159 * 0 1 48
160 * 1 0 32
161 * 1 1 16
162 */
163 static inline ipc_entry_bits_t
ipc_entry_new_rollpoint(ipc_entry_bits_t rollbits)164 ipc_entry_new_rollpoint(
165 ipc_entry_bits_t rollbits)
166 {
167 rollbits = (rollbits << IE_BITS_ROLL_POS) & IE_BITS_ROLL_MASK;
168 ipc_entry_bits_t newgen = IE_BITS_GEN_MASK + IE_BITS_GEN_ONE;
169 return newgen | rollbits;
170 }
171
172 /*
173 * Get the next gencount, modulo the entry's rollover point. If the sum rolls over,
174 * the caller should re-start the generation counter with a different rollpoint.
175 */
176 static inline ipc_entry_bits_t
ipc_entry_new_gen(ipc_entry_bits_t oldgen)177 ipc_entry_new_gen(
178 ipc_entry_bits_t oldgen)
179 {
180 ipc_entry_bits_t sum = (oldgen + IE_BITS_GEN_ONE) & IE_BITS_GEN_MASK;
181 ipc_entry_bits_t roll = oldgen & IE_BITS_ROLL_MASK;
182 ipc_entry_bits_t newgen = (sum % IE_BITS_ROLL(oldgen)) | roll;
183 return newgen;
184 }
185
186 /* Determine if a gencount has rolled over or not. */
187 static inline boolean_t
ipc_entry_gen_rolled(ipc_entry_bits_t oldgen,ipc_entry_bits_t newgen)188 ipc_entry_gen_rolled(
189 ipc_entry_bits_t oldgen,
190 ipc_entry_bits_t newgen)
191 {
192 return (oldgen & IE_BITS_GEN_MASK) > (newgen & IE_BITS_GEN_MASK);
193 }
194
195 #else
196 #define IE_BITS_GEN_MASK 0
197 #define IE_BITS_GEN(bits) 0
198 #define IE_BITS_GEN_ONE 0
199 #define IE_BITS_ROLL_POS 0
200 #define IE_BITS_ROLL_MASK 0
201 #define IE_BITS_ROLL(bits) (bits)
202
203 static inline ipc_entry_bits_t
ipc_entry_new_rollpoint(ipc_entry_bits_t rollbits)204 ipc_entry_new_rollpoint(
205 ipc_entry_bits_t rollbits)
206 {
207 return 0;
208 }
209
210 static inline ipc_entry_bits_t
ipc_entry_new_gen(ipc_entry_bits_t oldgen)211 ipc_entry_new_gen(
212 ipc_entry_bits_t oldgen)
213 {
214 return 0;
215 }
216
217 static inline boolean_t
ipc_entry_gen_rolled(ipc_entry_bits_t oldgen,ipc_entry_bits_t newgen)218 ipc_entry_gen_rolled(
219 ipc_entry_bits_t oldgen,
220 ipc_entry_bits_t newgen)
221 {
222 return FALSE;
223 }
224
225 #endif /* !USE_PORT_GEN */
226
227 #define IE_BITS_RIGHT_MASK 0x007fffff /* relevant to the right */
228 /*
229 * Exported interfaces
230 */
231
232 extern unsigned int ipc_entry_table_count_max(void) __pure2;
233
234 /* Search for entry in a space by name */
235 extern ipc_entry_t ipc_entry_lookup(
236 ipc_space_t space,
237 mach_port_name_t name);
238
239 /* Hold a number of entries in a locked space */
240 extern kern_return_t ipc_entries_hold(
241 ipc_space_t space,
242 natural_t count);
243
244 /* claim and initialize a held entry in a locked space */
245 extern kern_return_t ipc_entry_claim(
246 ipc_space_t space,
247 ipc_object_t object,
248 mach_port_name_t *namep,
249 ipc_entry_t *entryp);
250
251 /* Allocate an entry in a space, growing the space if necessary */
252 extern kern_return_t ipc_entry_alloc(
253 ipc_space_t space,
254 ipc_object_t object,
255 mach_port_name_t *namep,
256 ipc_entry_t *entryp);
257
258 /* Allocate/find an entry in a space with a specific name */
259 extern kern_return_t ipc_entry_alloc_name(
260 ipc_space_t space,
261 mach_port_name_t name,
262 ipc_entry_t *entryp);
263
264 /* Deallocate an entry from a space */
265 extern void ipc_entry_dealloc(
266 ipc_space_t space,
267 ipc_object_t object,
268 mach_port_name_t name,
269 ipc_entry_t entry);
270
271 /* Mark and entry modified in a space */
272 extern void ipc_entry_modified(
273 ipc_space_t space,
274 mach_port_name_t name,
275 ipc_entry_t entry);
276
277 /* Grow the table in a space */
278 extern kern_return_t ipc_entry_grow_table(
279 ipc_space_t space,
280 ipc_table_elems_t target_size);
281
282 /* mask on/off default entry generation bits */
283 extern mach_port_name_t ipc_entry_name_mask(
284 mach_port_name_t name);
285 #endif /* _IPC_IPC_ENTRY_H_ */
286