X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/6601e61aa18bf4f09af135ff61fc7f4771d23b06..2a1bd2d3eef5c7a7bb14f4bb9fdbca9a96ee4752:/osfmk/ipc/ipc_entry.h diff --git a/osfmk/ipc/ipc_entry.h b/osfmk/ipc/ipc_entry.h index 70f99b476..5601b84c8 100644 --- a/osfmk/ipc/ipc_entry.h +++ b/osfmk/ipc/ipc_entry.h @@ -1,49 +1,55 @@ /* * Copyright (c) 2000-2004 Apple Computer, Inc. All rights reserved. * - * @APPLE_LICENSE_HEADER_START@ - * - * The contents of this file constitute Original Code as defined in and - * are subject to the Apple Public Source License Version 1.1 (the - * "License"). You may not use this file except in compliance with the - * License. Please obtain a copy of the License at - * http://www.apple.com/publicsource and read it before using this file. - * - * This Original Code and all software distributed under the License are - * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER + * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ + * + * 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. The rights granted to you under the License + * may not be used to create, or enable the creation or redistribution of, + * unlawful or unlicensed copies of an Apple operating system, or to + * circumvent, violate, or enable the circumvention or violation of, any + * terms of an Apple operating system software license agreement. + * + * 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 OR NON-INFRINGEMENT. Please see the - * License for the specific language governing rights and limitations - * under the License. - * - * @APPLE_LICENSE_HEADER_END@ + * 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_OSREFERENCE_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. */ @@ -58,7 +64,7 @@ * tasks' capabilities for ports and port sets. */ -#ifndef _IPC_IPC_ENTRY_H_ +#ifndef _IPC_IPC_ENTRY_H_ #define _IPC_IPC_ENTRY_H_ #include @@ -74,12 +80,13 @@ * 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. + * + * The ie_dist field holds the distance to the desired spot, + * which is used to implement robin-hood hashing. + * * This hash table converts (space, object) -> name. * It is used independently of the other fields. * @@ -91,101 +98,179 @@ * It is used as the head of the free list. */ +#define IPC_ENTRY_DIST_BITS 12 +#define IPC_ENTRY_DIST_MAX ((1 << IPC_ENTRY_DIST_BITS) - 1) +#ifdef __LP64__ +#define IPC_ENTRY_INDEX_BITS 32 +#define IPC_ENTRY_INDEX_MAX (UINT32_MAX) +#else +#define IPC_ENTRY_INDEX_BITS 20 +#define IPC_ENTRY_INDEX_MAX ((1 << IPC_ENTRY_INDEX_BITS) - 1) +#endif + struct ipc_entry { - struct ipc_object *ie_object; - ipc_entry_bits_t ie_bits; + struct ipc_object *XNU_PTRAUTH_SIGNED_PTR("ipc_entry.ie_object") ie_object; + ipc_entry_bits_t ie_bits; + uint32_t ie_dist : IPC_ENTRY_DIST_BITS; + mach_port_index_t ie_index : IPC_ENTRY_INDEX_BITS; union { - mach_port_index_t next; /* next in freelist, or... */ - ipc_table_index_t request; /* dead name request notify */ + 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; }; -#define ie_request index.request -#define ie_next index.next -#define ie_index hash.table +#define ie_request index.request +#define ie_next index.next -#define IE_BITS_UREFS_MASK 0x0000ffff /* 16 bits of user-reference */ -#define IE_BITS_UREFS(bits) ((bits) & IE_BITS_UREFS_MASK) +#define IE_REQ_NONE 0 /* no request */ -#define IE_BITS_TYPE_MASK 0x001f0000 /* 5 bits of capability type */ -#define IE_BITS_TYPE(bits) ((bits) & IE_BITS_TYPE_MASK) +#define IE_BITS_UREFS_MASK 0x0000ffff /* 16 bits of user-reference */ +#define IE_BITS_UREFS(bits) ((bits) & IE_BITS_UREFS_MASK) -#define IE_BITS_COLLISION 0x00800000 /* 1 bit for collisions */ +#define IE_BITS_TYPE_MASK 0x001f0000 /* 5 bits of capability type */ +#define IE_BITS_TYPE(bits) ((bits) & IE_BITS_TYPE_MASK) +#define IE_BITS_EXTYPE_MASK 0x00200000 /* 1 bit for extended capability */ #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_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_ROLL_POS 22 /* LSB pos of generation rollover */ +#define IE_BITS_ROLL_BITS 2 /* number of generation rollover bits */ +#define IE_BITS_ROLL_MASK (((1 << IE_BITS_ROLL_BITS) - 1) << IE_BITS_ROLL_POS) +#define IE_BITS_ROLL(bits) ((((bits) & IE_BITS_ROLL_MASK) << 8) ^ IE_BITS_GEN_MASK) +/* + * Restart a generation counter with the specified bits for the rollover point. + * There are 4 different rollover points: + * bits rollover period + * 0 0 64 + * 0 1 48 + * 1 0 32 + * 1 1 16 + */ +static inline ipc_entry_bits_t +ipc_entry_new_rollpoint( + ipc_entry_bits_t rollbits) +{ + rollbits = (rollbits << IE_BITS_ROLL_POS) & IE_BITS_ROLL_MASK; + ipc_entry_bits_t newgen = IE_BITS_GEN_MASK + IE_BITS_GEN_ONE; + return newgen | rollbits; +} -#define IE_BITS_RIGHT_MASK 0x007fffff /* relevant to the right */ +/* + * Get the next gencount, modulo the entry's rollover point. If the sum rolls over, + * the caller should re-start the generation counter with a different rollpoint. + */ +static inline ipc_entry_bits_t +ipc_entry_new_gen( + ipc_entry_bits_t oldgen) +{ + ipc_entry_bits_t sum = (oldgen + IE_BITS_GEN_ONE) & IE_BITS_GEN_MASK; + ipc_entry_bits_t roll = oldgen & IE_BITS_ROLL_MASK; + ipc_entry_bits_t newgen = (sum % IE_BITS_ROLL(oldgen)) | roll; + return newgen; +} -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; -}; +/* Determine if a gencount has rolled over or not. */ +static inline boolean_t +ipc_entry_gen_rolled( + ipc_entry_bits_t oldgen, + ipc_entry_bits_t newgen) +{ + return (oldgen & IE_BITS_GEN_MASK) > (newgen & IE_BITS_GEN_MASK); +} -#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 +#else +#define IE_BITS_GEN_MASK 0 +#define IE_BITS_GEN(bits) 0 +#define IE_BITS_GEN_ONE 0 +#define IE_BITS_ROLL_POS 0 +#define IE_BITS_ROLL_MASK 0 +#define IE_BITS_ROLL(bits) (bits) + +static inline ipc_entry_bits_t +ipc_entry_new_rollpoint( + ipc_entry_bits_t rollbits) +{ + return 0; +} + +static inline ipc_entry_bits_t +ipc_entry_new_gen( + ipc_entry_bits_t oldgen) +{ + return 0; +} -extern zone_t ipc_tree_entry_zone; +static inline boolean_t +ipc_entry_gen_rolled( + ipc_entry_bits_t oldgen, + ipc_entry_bits_t newgen) +{ + return FALSE; +} -#define ite_alloc() ((ipc_tree_entry_t) zalloc(ipc_tree_entry_zone)) -#define ite_free(ite) zfree(ipc_tree_entry_zone, (ite)) +#endif /* !USE_PORT_GEN */ +#define IE_BITS_RIGHT_MASK 0x007fffff /* relevant to the right */ /* * 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); + ipc_space_t space, + mach_port_name_t name); + +/* Hold a number of entries in a locked space */ +extern kern_return_t ipc_entries_hold( + ipc_space_t space, + natural_t count); + +/* claim and initialize a held entry in a locked space */ +extern kern_return_t ipc_entry_claim( + ipc_space_t space, + mach_port_name_t *namep, + ipc_entry_t *entryp); /* 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); + 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); + 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); + 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); + ipc_space_t space, + mach_port_name_t name, + ipc_entry_t entry); + +/* Mark and entry modified in a space */ +extern void ipc_entry_modified( + 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, - ipc_table_elems_t target_size); + ipc_space_t space, + ipc_table_elems_t target_size); -#endif /* _IPC_IPC_ENTRY_H_ */ +/* mask on/off default entry generation bits */ +extern mach_port_name_t ipc_entry_name_mask( + mach_port_name_t name); +#endif /* _IPC_IPC_ENTRY_H_ */