1 /* 2 * Copyright (c) 2017 Apple 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 #ifndef _OS_REFCNT_H_ 30 #define _OS_REFCNT_H_ 31 32 /* 33 * os_refcnt reference counting API 34 * 35 * Two flavors are provided: atomic and locked. Atomic internally uses C11 atomic 36 * operations and requires no external synchronization, whereas the locked flavor 37 * assumes the refcnt object is locked by the caller. It is NOT safe to 38 * mix-and-match locked and atomic calls. 39 * 40 * 'refgrp's are a way to (hierarchically) group like refcount objects for 41 * debugging purposes. The group keeps track of the total number and aggregate 42 * reference count of member refcounts, and the "rlog=" boot-arg is used to enable 43 * refcount logging by group name. Named groups can be created explicitly with 44 * os_refgrp_decl(), or implicitly by passing NULL for the refgrp when 45 * initializing a refcnt object. In the latter case, the group name is the same as 46 * the function enclosing the init call. Groups are only available on DEV or DEBUG 47 * builds, and are otherwise compiled out. 48 */ 49 50 #include <stdatomic.h> 51 #include <stdbool.h> 52 #include <stdint.h> 53 #include <os/base.h> 54 55 struct os_refcnt; 56 struct os_refgrp; 57 typedef struct os_refcnt os_refcnt_t; 58 59 /* type of the internal counter */ 60 typedef uint32_t os_ref_count_t; 61 typedef _Atomic(os_ref_count_t) os_ref_atomic_t; 62 63 /* 64 * OS_REF_INITIALIZER 65 * OS_REF_ATOMIC_INITIALIZER 66 * 67 * Static initializers that create refcnt objects with safe initial values for use 68 * between declaration and initialization (os_ref*_init()). Equivalent to zeroing. 69 */ 70 71 #ifndef KERNEL 72 # include <stdlib.h> 73 # include <stdio.h> 74 # ifndef __improbable 75 # define __improbable(x) x 76 # endif 77 # ifndef panic 78 # define panic(x, ...) do { fprintf(stderr, x, __VA_ARGS__); abort(); } while (0) 79 # endif 80 #endif 81 82 #ifndef OS_REFCNT_DEBUG 83 # if DEVELOPMENT || DEBUG 84 # define OS_REFCNT_DEBUG 1 85 # else 86 # define OS_REFCNT_DEBUG 0 87 # endif 88 #endif 89 90 #if __has_attribute(diagnose_if) 91 # define os_error_if(cond, msg) __attribute__((diagnose_if((cond), (msg), "error"))) 92 #else 93 # define os_error_if(...) 94 #endif 95 96 __BEGIN_DECLS 97 98 /* 99 * os_ref_init: initialize an os_refcnt with a count of 1 100 * os_ref_init_count: initialize an os_refcnt with a specific count >= 1 101 */ 102 #define os_ref_init(rc, grp) os_ref_init_count((rc), (grp), 1) 103 static void os_ref_init_count(struct os_refcnt *, struct os_refgrp *, os_ref_count_t count) 104 os_error_if(count == 0, "Reference count must be non-zero initialized"); 105 106 /* 107 * os_refgrp_decl(qual, var, name, parent): declare a refgroup object 'var' with 108 * given name string and parent group. 109 */ 110 111 /* 112 * 113 * os_ref_retain: acquire a reference (increment reference count by 1) atomically. 114 * 115 * os_ref_release: release a reference (decrement reference count) atomically and 116 * return the new count. Memory is synchronized such that the dealloc block 117 * (i.e. code handling the final release() == 0 call) sees up-to-date memory 118 * with respect to all prior release()s on the same refcnt object. This 119 * memory ordering is sufficient for most use cases. 120 * 121 * os_ref_release_relaxed: same as release() but with weaker relaxed memory ordering. 122 * This can be used when the dealloc block is already synchronized with other 123 * accesses to the object (for example, with a lock). 124 * 125 * os_ref_release_live: release a reference that is guaranteed not to be the last one. 126 */ 127 static void os_ref_retain(struct os_refcnt *); 128 static os_ref_count_t os_ref_release(struct os_refcnt *) OS_WARN_RESULT; 129 static os_ref_count_t os_ref_release_relaxed(struct os_refcnt *) OS_WARN_RESULT; 130 static void os_ref_release_live(struct os_refcnt *); 131 132 /* 133 * os_ref_retain_try: a variant of atomic retain that fails for objects with a 134 * zero reference count. The caller must therefore ensure that the object 135 * remains alive for any possible retain_try() caller, usually by using a 136 * lock protecting both the retain and dealloc paths. This variant is useful 137 * for objects stored in a collection, because no lock is required on the 138 * release() side until the object is deallocated. 139 */ 140 static bool os_ref_retain_try(struct os_refcnt *) OS_WARN_RESULT; 141 142 /* 143 * os_ref_retain_locked: acquire a reference on an object protected by a held 144 * lock. The caller must ensure mutual exclusivity of retain_locked() and 145 * release_locked() calls on the same object. 146 * 147 * os_ref_release_locked: release a reference on an object protected by a held 148 * lock. 149 */ 150 static void os_ref_retain_locked(struct os_refcnt *); 151 static os_ref_count_t os_ref_release_locked(struct os_refcnt *) OS_WARN_RESULT; 152 153 /* 154 * os_ref_get_count: return the current reference count. This is unsafe for 155 * synchronization. 156 */ 157 static os_ref_count_t os_ref_get_count(struct os_refcnt *rc); 158 159 160 /*! 161 * @brief 162 * Type for scalable percpu refcounts. 163 * 164 * @discussion 165 * percpu refcounts are scalable refcounts that do not contend on retain/release 166 * but require O(ncpu) storage. 167 * 168 * They also require to be explicitly "killed" with @c os_pcpu_ref_kill() before 169 * the "last reference" detection logic kicks in, in which case the refcount 170 * decays to a regular (contending) atomic refcount. 171 * 172 * This type of refcount is typically useful for objects that are in low 173 * numbers, but are accessed frequently and must be protected against deletion, 174 * when options like SMR critical sections can't be used. 175 */ 176 typedef uintptr_t os_pcpu_ref_t; 177 178 /*! 179 * @brief 180 * Initializes a scalable refcount. 181 * 182 * @discussion 183 * The refcount is initialized with the value "1" and marked "live". 184 * 185 * This reference is supposed to be dropped with @c os_pcpu_ref_kill(), 186 * which will mark it as "dead", which is required for os_pcpu_ref_release() 187 * to become precise. 188 * 189 * The refcount must be destroyed with @c os_pcpu_ref_destroy() once 190 * @c os_pcpu_ref_release() returns 0. 191 */ 192 extern void os_pcpu_ref_init(os_pcpu_ref_t *ref, struct os_refgrp *grp); 193 194 /*! 195 * @brief 196 * "Kill" the initial reference of a percpu refcount. 197 * 198 * @discussion 199 * This drops the "creation" reference of the refcount made by 200 * @c os_pcpu_ref_init(). 201 * 202 * Once a percpu refcount is "killed" it becomes a regular atomic refcount 203 * in order to do precise detection of the last reference drop. 204 * 205 * This returns the resulting refcount value, like @c os_pcpu_ref_release() does. 206 */ 207 extern os_ref_count_t os_pcpu_ref_kill(os_pcpu_ref_t ref, struct os_refgrp *grp) __result_use_check; 208 209 /*! 210 * @brief 211 * Wait for a killed refcount to hit 0. 212 * 213 * @discussion 214 * Waiting for object death must happen after the refcount has been "killed". 215 * 216 * There can only be at most a single waiter, given that it is expected that 217 * waiter will free resources, and having two waiters would cause use-after-free 218 * accesses. 219 * 220 * Having two waiters, or waiting on a live refcount will result into 221 * a kernel panic. 222 */ 223 extern void os_pcpu_ref_wait_for_death(os_pcpu_ref_t ref); 224 225 /*! 226 * @brief 227 * Destroy a scalable refcount once it has been killed and reached 0. 228 * 229 * @discussion 230 * This must be called to destroy a scalable refcount. 231 * 232 * It is legal to release a scalable refcount when: 233 * - @c os_pcpu_ref_kill() was called and returned 0; 234 * - @c os_pcpu_ref_kill() was called and @c os_pcpu_ref_release() returned 0; 235 * - the refcount was initialized with @c os_pcpu_ref_init() and never used nor 236 * killed. 237 */ 238 extern void os_pcpu_ref_destroy(os_pcpu_ref_t *ref, struct os_refgrp *grp); 239 240 /*! 241 * @brief 242 * Returns the value of the refcount. 243 * 244 * @discussion 245 * If the refcount is still live (hasn't been killed yet), 246 * then this function returns a "very large" value. 247 */ 248 extern os_ref_count_t os_pcpu_ref_count(os_pcpu_ref_t ref); 249 250 /*! 251 * @brief 252 * Acquires a +1 reference on the specified percpu refcount. 253 */ 254 extern void os_pcpu_ref_retain(os_pcpu_ref_t ref, struct os_refgrp *grp); 255 256 /*! 257 * @brief 258 * Tries to acquire a +1 reference on the specified percpu refcount. 259 * 260 * @discussion 261 * Unlike a typical refcount, this function will fail as soon as 262 * @c os_pcpu_ref_kill() has been called, rather than because 263 * the refcount hit 0. 264 */ 265 extern bool os_pcpu_ref_retain_try(os_pcpu_ref_t ref, struct os_refgrp *grp) __result_use_check; 266 267 /*! 268 * @brief 269 * Release an acquired reference, knowing it is not the last one. 270 */ 271 extern void os_pcpu_ref_release_live(os_pcpu_ref_t ref, struct os_refgrp *grp); 272 273 /*! 274 * @brief 275 * Release an acquired reference. 276 * 277 * @discussion 278 * If the refcount is "live" the returned value will be a "very large number" 279 * that isn't really accurate. 280 * 281 * Once the refcount has been "killed" then this returns an accurate view of the 282 * refcount. 283 */ 284 extern os_ref_count_t os_pcpu_ref_release(os_pcpu_ref_t ref, struct os_refgrp *grp) __result_use_check; 285 286 287 #if XNU_KERNEL_PRIVATE 288 #pragma GCC visibility push(hidden) 289 290 /* 291 * Raw API that uses a plain atomic counter (os_ref_atomic_t) and a separate 292 * refgroup. This can be used in situations where the refcount object must be 293 * fixed size, for example for embedding in structures with ABI stability 294 * requirements. 295 */ 296 297 #define os_ref_init_raw(rc, grp) os_ref_init_count_raw((rc), (grp), 1) 298 static void os_ref_init_count_raw(os_ref_atomic_t *, struct os_refgrp *, os_ref_count_t count) 299 os_error_if(count == 0, "Reference count must be non-zero initialized"); 300 static void os_ref_retain_floor(struct os_refcnt *, os_ref_count_t f) 301 os_error_if(!__builtin_constant_p(f) || f == 0, "refcount floor must be >= 1"); 302 static void os_ref_retain_raw(os_ref_atomic_t *, struct os_refgrp *); 303 static void os_ref_retain_floor_raw(os_ref_atomic_t *, os_ref_count_t f, struct os_refgrp *) 304 os_error_if(!__builtin_constant_p(f) || f == 0, "refcount floor must be >= 1"); 305 static os_ref_count_t os_ref_release_raw(os_ref_atomic_t *, struct os_refgrp *) OS_WARN_RESULT; 306 static os_ref_count_t os_ref_release_raw_relaxed(os_ref_atomic_t *, struct os_refgrp *) OS_WARN_RESULT; 307 static void os_ref_release_live_raw(os_ref_atomic_t *, struct os_refgrp *); 308 static bool os_ref_retain_try_raw(os_ref_atomic_t *, struct os_refgrp *) OS_WARN_RESULT; 309 static bool os_ref_retain_floor_try_raw(os_ref_atomic_t *, os_ref_count_t f, struct os_refgrp *) OS_WARN_RESULT 310 os_error_if(!__builtin_constant_p(f) || f == 0, "refcount floor must be >= 1"); 311 static void os_ref_retain_locked_raw(os_ref_atomic_t *, struct os_refgrp *); 312 static void os_ref_retain_floor_locked_raw(os_ref_atomic_t *, os_ref_count_t f, struct os_refgrp *) 313 os_error_if(!__builtin_constant_p(f) || f == 0, "refcount floor must be >= 1"); 314 static os_ref_count_t os_ref_release_locked_raw(os_ref_atomic_t *, struct os_refgrp *) OS_WARN_RESULT; 315 static os_ref_count_t os_ref_get_count_raw(os_ref_atomic_t *rc); 316 317 318 /* 319 * Bitwise API: like the raw API, but allows some bits in the refcount value to be 320 * reserved for other purposes. 'b' defines the number of trailing (LSB) reserved 321 * bits, which the refcnt_raw API will never modify (except at init()). 322 * 323 * It is assumed that users of this API always use atomic ops on the 324 * os_ref_atomic_t (or hold a lock for the locked variants), and never modify the 325 * top (32 - 'b') bits. 326 * 327 * Due to guard bits, the maximum reference count is 2^(28 - 'b') - 1, and the 328 * maximum 'b' is 26 bits. This API can also be used just to limit the max 329 * refcount. 330 * 331 * The "*_raw_mask" APIs return the raw bit pattern of the refcount (with a type 332 * of uint32_t), that the caller is supposed to decode. Other APIs that return 333 * os_ref_count_t return a normalized refcount where the trailing bits have been 334 * removed. 335 * 336 * "locked" variants aren't provided as the point of these interfaces 337 * is to combine flags into a refcount and be able to manipulate both 338 * atomically with respect to each other. 339 */ 340 341 /* Initialize the reference count and reserved bits */ 342 #define os_ref_init_mask(rc, b, grp, bits) os_ref_init_count_mask((rc), (b), (grp), 1, bits) 343 void os_ref_init_count_mask(os_ref_atomic_t *rc, uint32_t b, struct os_refgrp *grp, 344 os_ref_count_t init_count, uint32_t init_bits) 345 os_error_if(init_count == 0, "Reference count must be non-zero initialized") 346 os_error_if(b > 26, "Bitwise reference count limited to 26 bits") 347 os_error_if(init_bits >= (1U << b), "Bits out of range"); 348 349 static uint32_t os_ref_get_raw_mask(os_ref_atomic_t *rc); 350 static uint32_t os_ref_get_bits_mask(os_ref_atomic_t *rc, uint32_t b); 351 static os_ref_count_t os_ref_get_count_mask(os_ref_atomic_t *rc, uint32_t b); 352 353 static void 354 os_ref_retain_mask(os_ref_atomic_t *rc, uint32_t b, struct os_refgrp *grp); 355 static void 356 os_ref_retain_acquire_mask(os_ref_atomic_t *rc, uint32_t b, struct os_refgrp *grp); 357 static uint32_t 358 os_ref_retain_try_mask(os_ref_atomic_t *, uint32_t b, uint32_t reject_mask, 359 struct os_refgrp *grp) OS_WARN_RESULT; 360 static bool 361 os_ref_retain_try_acquire_mask(os_ref_atomic_t *, uint32_t b, uint32_t reject_mask, 362 struct os_refgrp *grp) OS_WARN_RESULT; 363 364 static uint32_t 365 os_ref_release_raw_mask(os_ref_atomic_t *rc, uint32_t b, struct os_refgrp *grp) OS_WARN_RESULT; 366 static uint32_t 367 os_ref_release_raw_relaxed_mask(os_ref_atomic_t *rc, uint32_t b, struct os_refgrp *grp) OS_WARN_RESULT; 368 static os_ref_count_t 369 os_ref_release_mask(os_ref_atomic_t *rc, uint32_t b, struct os_refgrp *grp) OS_WARN_RESULT; 370 static os_ref_count_t 371 os_ref_release_relaxed_mask(os_ref_atomic_t *rc, uint32_t b, struct os_refgrp *grp) OS_WARN_RESULT; 372 static uint32_t 373 os_ref_release_live_raw_mask(os_ref_atomic_t *rc, uint32_t b, struct os_refgrp *grp); 374 static void 375 os_ref_release_live_mask(os_ref_atomic_t *rc, uint32_t b, struct os_refgrp *grp); 376 377 #pragma GCC visibility pop 378 #endif /* XNU_KERNEL_PRIVATE */ 379 380 __END_DECLS 381 382 #include <os/refcnt_internal.h> 383 #endif 384