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 Software.Distribution@CS.CMU.EDU |
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_object *XNU_PTRAUTH_SIGNED_PTR("ipc_entry.ie_object" ) volatile ie_volatile_object; |
111 | struct ipc_entry_table *XNU_PTRAUTH_SIGNED_PTR("ipc_entry.ie_self" ) ie_self; |
112 | }; |
113 | union { |
114 | struct { |
115 | ipc_entry_bits_t ie_bits; |
116 | union { |
117 | mach_port_index_t ie_next; /* next in freelist, or... */ |
118 | ipc_table_index_t ie_request; /* dead name request notify */ |
119 | }; |
120 | |
121 | /* hash fields */ |
122 | uint32_t ie_dist; |
123 | mach_port_index_t ie_index; |
124 | }; |
125 | struct smr_node ie_smr_node; |
126 | }; |
127 | }; |
128 | |
129 | #define IPC_ENTRY_TABLE_MIN 32 |
130 | #define IPC_ENTRY_TABLE_PERIOD 16 |
131 | KALLOC_ARRAY_TYPE_DECL(ipc_entry_table, struct ipc_entry); |
132 | |
133 | #define IE_REQ_NONE 0 /* no request */ |
134 | |
135 | #define IE_BITS_UREFS_MASK 0x0000ffff /* 16 bits of user-reference */ |
136 | #define IE_BITS_UREFS(bits) ((bits) & IE_BITS_UREFS_MASK) |
137 | |
138 | #define IE_BITS_TYPE_MASK 0x001f0000 /* 5 bits of capability type */ |
139 | #define IE_BITS_TYPE(bits) ((bits) & IE_BITS_TYPE_MASK) |
140 | |
141 | #define IE_BITS_EXTYPE_MASK 0x00200000 /* 1 bit for extended capability */ |
142 | |
143 | #ifndef NO_PORT_GEN |
144 | #define IE_BITS_GEN_MASK 0xff000000 /* 8 bits for generation */ |
145 | #define IE_BITS_GEN(bits) ((bits) & IE_BITS_GEN_MASK) |
146 | #define IE_BITS_GEN_ONE 0x04000000 /* low bit of generation */ |
147 | #define IE_BITS_ROLL_POS 22 /* LSB pos of generation rollover */ |
148 | #define IE_BITS_ROLL_BITS 2 /* number of generation rollover bits */ |
149 | #define IE_BITS_ROLL_MASK (((1 << IE_BITS_ROLL_BITS) - 1) << IE_BITS_ROLL_POS) |
150 | #define IE_BITS_ROLL(bits) ((((bits) & IE_BITS_ROLL_MASK) << 8) ^ IE_BITS_GEN_MASK) |
151 | |
152 | /* |
153 | * Restart a generation counter with the specified bits for the rollover point. |
154 | * There are 4 different rollover points: |
155 | * bits rollover period |
156 | * 0 0 64 |
157 | * 0 1 48 |
158 | * 1 0 32 |
159 | * 1 1 16 |
160 | */ |
161 | static inline ipc_entry_bits_t |
162 | ipc_entry_new_rollpoint( |
163 | ipc_entry_bits_t rollbits) |
164 | { |
165 | rollbits = (rollbits << IE_BITS_ROLL_POS) & IE_BITS_ROLL_MASK; |
166 | ipc_entry_bits_t newgen = IE_BITS_GEN_MASK + IE_BITS_GEN_ONE; |
167 | return newgen | rollbits; |
168 | } |
169 | |
170 | /* |
171 | * Get the next gencount, modulo the entry's rollover point. If the sum rolls over, |
172 | * the caller should re-start the generation counter with a different rollpoint. |
173 | */ |
174 | static inline ipc_entry_bits_t |
175 | ipc_entry_new_gen( |
176 | ipc_entry_bits_t oldgen) |
177 | { |
178 | ipc_entry_bits_t sum = (oldgen + IE_BITS_GEN_ONE) & IE_BITS_GEN_MASK; |
179 | ipc_entry_bits_t roll = oldgen & IE_BITS_ROLL_MASK; |
180 | ipc_entry_bits_t newgen = (sum % IE_BITS_ROLL(oldgen)) | roll; |
181 | return newgen; |
182 | } |
183 | |
184 | /* Determine if a gencount has rolled over or not. */ |
185 | static inline boolean_t |
186 | ipc_entry_gen_rolled( |
187 | ipc_entry_bits_t oldgen, |
188 | ipc_entry_bits_t newgen) |
189 | { |
190 | return (oldgen & IE_BITS_GEN_MASK) > (newgen & IE_BITS_GEN_MASK); |
191 | } |
192 | |
193 | #else |
194 | #define IE_BITS_GEN_MASK 0 |
195 | #define IE_BITS_GEN(bits) 0 |
196 | #define IE_BITS_GEN_ONE 0 |
197 | #define IE_BITS_ROLL_POS 0 |
198 | #define IE_BITS_ROLL_MASK 0 |
199 | #define IE_BITS_ROLL(bits) (bits) |
200 | |
201 | static inline ipc_entry_bits_t |
202 | ipc_entry_new_rollpoint( |
203 | ipc_entry_bits_t rollbits) |
204 | { |
205 | return 0; |
206 | } |
207 | |
208 | static inline ipc_entry_bits_t |
209 | ipc_entry_new_gen( |
210 | ipc_entry_bits_t oldgen) |
211 | { |
212 | return 0; |
213 | } |
214 | |
215 | static inline boolean_t |
216 | ipc_entry_gen_rolled( |
217 | ipc_entry_bits_t oldgen, |
218 | ipc_entry_bits_t newgen) |
219 | { |
220 | return FALSE; |
221 | } |
222 | |
223 | #endif /* !USE_PORT_GEN */ |
224 | |
225 | #define IE_BITS_RIGHT_MASK 0x007fffff /* relevant to the right */ |
226 | /* |
227 | * Exported interfaces |
228 | */ |
229 | |
230 | extern unsigned int ipc_entry_table_count_max(void) __pure2; |
231 | |
232 | /* Search for entry in a space by name */ |
233 | extern ipc_entry_t ipc_entry_lookup( |
234 | ipc_space_t space, |
235 | mach_port_name_t name); |
236 | |
237 | /* Hold a number of entries in a locked space */ |
238 | extern kern_return_t ipc_entries_hold( |
239 | ipc_space_t space, |
240 | natural_t count); |
241 | |
242 | /* claim and initialize a held entry in a locked space */ |
243 | extern kern_return_t ipc_entry_claim( |
244 | ipc_space_t space, |
245 | ipc_object_t object, |
246 | mach_port_name_t *namep, |
247 | ipc_entry_t *entryp); |
248 | |
249 | /* Allocate an entry in a space, growing the space if necessary */ |
250 | extern kern_return_t ipc_entry_alloc( |
251 | ipc_space_t space, |
252 | ipc_object_t object, |
253 | mach_port_name_t *namep, |
254 | ipc_entry_t *entryp); |
255 | |
256 | /* Allocate/find an entry in a space with a specific name */ |
257 | extern kern_return_t ipc_entry_alloc_name( |
258 | ipc_space_t space, |
259 | mach_port_name_t name, |
260 | ipc_entry_t *entryp); |
261 | |
262 | /* Deallocate an entry from a space */ |
263 | extern void ipc_entry_dealloc( |
264 | ipc_space_t space, |
265 | ipc_object_t object, |
266 | mach_port_name_t name, |
267 | ipc_entry_t entry); |
268 | |
269 | /* Mark and entry modified in a space */ |
270 | extern void ipc_entry_modified( |
271 | ipc_space_t space, |
272 | mach_port_name_t name, |
273 | ipc_entry_t entry); |
274 | |
275 | /* Grow the table in a space */ |
276 | extern kern_return_t ipc_entry_grow_table( |
277 | ipc_space_t space, |
278 | ipc_table_elems_t target_size); |
279 | |
280 | /* mask on/off default entry generation bits */ |
281 | extern mach_port_name_t ipc_entry_name_mask( |
282 | mach_port_name_t name); |
283 | #endif /* _IPC_IPC_ENTRY_H_ */ |
284 | |