object_alloc/lib.rs
1// Copyright 2017-2018 the authors. See the 'Copyright and license' section of the
2// README.md file at the top-level directory of this repository.
3//
4// Licensed under the Apache License, Version 2.0 (the LICENSE-APACHE file) or
5// the MIT license (the LICENSE-MIT file) at your option. This file may not be
6// copied, modified, or distributed except according to those terms.
7
8#![no_std]
9#![feature(alloc, allocator_api)]
10#![feature(core_intrinsics)]
11
12extern crate alloc;
13use alloc::alloc::Layout;
14use core::intrinsics::abort;
15use core::ptr::NonNull;
16
17/// Allocators which allocate objects of a particular type.
18///
19/// `ObjectAlloc`s provide an interface which is slightly different than the interface provided by
20/// a standard allocator. By definition, they are only capable of allocating objects of a
21/// particular type. Additionally, memory returned from a call to `alloc` is guaranteed to already
22/// be a valid, initialized instance of `T`. `ObjectAlloc`s may differ in how much flexibility they
23/// provide in specifying how allocated objects are initialized, and `ObjectAlloc`s obtained using
24/// `unsafe` constructors are allowed to break these initialization rules, allocating uninitialized
25/// or invalid objects.
26///
27/// These differences allow `ObjectAlloc`s to provide significant performance improvements over
28/// general-purpose allocators. First, only having to allocate objects of a particular size and
29/// alignment allows them to make optimizations that are not available to general-purpose
30/// allocators. Second, since `alloc` is required to return already-constructed objects, clients
31/// don't have to initialize allocated objects. This, coupled with an object-caching scheme for
32/// `dealloc`'d objects, allows many calls to `allloc` to avoid initialization altogether.
33///
34/// # Dropping
35///
36/// When an `ObjectAlloc` that allocates initialized objects is dropped, all cached `T` objects
37/// that have not yet been dropped are dropped. The order in which they are dropped is undefined.
38///
39/// # Use in unsafe code
40///
41/// Unsafe code may rely on the fact that objects allocated by an `ObjectAlloc` are initialized.
42/// Because of this, it must _not_ be possible for safe code to construct an `ObjectAlloc` that
43/// doesn't properly initialize objects, or else safe code could construct such an `ObjectAlloc`,
44/// pass it to a safe API that uses unsafe code under the hood (and that relies on the
45/// initialization behavior of `ObjectAlloc`s), and thus cause memory unsafety.
46///
47/// It is acceptable for implementors to provide constructors that produce `ObjectAlloc`s that do
48/// not abide by the initialization requirements, but these constructors must be `unsafe` so that
49/// they cannot be called from safe code.
50pub unsafe trait ObjectAlloc<T> {
51 /// Allocates an object of type `T`.
52 ///
53 /// If this `ObjectAlloc` was obtained using a safe constructor (as opposed to an `unsafe`
54 /// one), then the memory pointed to by the returned raw pointer is guaranteed to be a valid,
55 /// initialized instance of `T`. In particular, the returned object will be in one of the
56 /// following two states:
57 ///
58 /// * The result of a call to whatever initialization function was used to configure this
59 /// `ObjectAlloc`
60 /// * The same state as a `T` which was previously returned via a call to `dealloc`
61 ///
62 /// On the other hand, if this `ObjectAlloc` was obtained using an `unsafe` constructor, then
63 /// `alloc` may return uninitialized or invalid instances of `T` - the exact behavior should
64 /// be documented in the constructor.
65 ///
66 /// The memory returned by `alloc` is guaranteed to be aligned according to the requirements of
67 /// `T` (that is, according to `core::mem::align_of::<T>()`).
68 unsafe fn alloc(&mut self) -> Option<NonNull<T>>;
69
70 /// Deallocates an object previously returned by `alloc`.
71 ///
72 /// If `x` was not obtained through a call to `alloc`, or if `x` has already been `dealloc`'d,
73 /// the behavior of `dealloc` is undefined.
74 ///
75 /// It is valid for `x` to be cached and used to serve future calls to `alloc`. The only
76 /// guarantee that is made is that if this `ObjectAlloc` allocates initialized objects (unsafe
77 /// constructors are allowed to produce `ObjectAlloc`s that do not allocate initialized
78 /// objects), then `x` will be dropped at some point during the `ObjectAlloc`'s lifetime. This
79 /// may happen during this call to `dealloc`, when the `ObjectAlloc` itself is dropped, or some
80 /// time in between.
81 unsafe fn dealloc(&mut self, x: NonNull<T>);
82
83 /// Allocator-specific method for signalling an out-of-memory condition.
84 ///
85 /// `oom` aborts the thread or process, optionally performing cleanup or logging diagnostic
86 /// information before panicking or aborting.
87 ///
88 /// `oom` is meant to be used by clients which are unable to cope with an unsatisfied
89 /// allocation request, and wish to abandon computation rather than attempt to recover locally.
90 /// The allocator likely has more insight into why the request failed, and thus can likely
91 /// print more informative diagnostic information than the client could.
92 ///
93 /// Implementations of the `oom` method are discouraged from infinitely regressing in nested
94 /// calls to `oom`. In practice this means implementors should eschew allocating, especially
95 /// from `self` (directly or indirectly).
96 ///
97 /// Implementions of `alloc` are discouraged from panicking (or aborting) in the event of
98 /// memory exhaustion; instead they should return an error and let the client decide whether to
99 /// invoke this `oom` method in response.
100 fn oom(&mut self) -> ! {
101 unsafe { abort() }
102 }
103}
104
105/// An allocator for objects whose type or size is not known at compile time.
106///
107/// `UntypedObjectAlloc` is like `ObjectAlloc`, except that the size that it allocates may be
108/// configured at runtime. Also unlike `ObjectAlloc`, `UntypedObjectAlloc`s make no guarantees
109/// about initialization of objects. An individual implementation of `UntypedObjectAlloc` may
110/// decide to make such guarantees, but it is not required in order to be a correct implementation
111/// of this trait, and the correctness of unsafe code must not rely on this behavior.
112pub unsafe trait UntypedObjectAlloc {
113 /// Obtains the `Layout` of allocated objects.
114 ///
115 /// `layout` returns a `Layout` object describing objects allocated by this
116 /// `UntypedObjectAlloc`. All objects obtained via `alloc` are guaranteed to satisfy this
117 /// `Layout`.
118 fn layout(&self) -> Layout;
119
120 /// Allocates a new object.
121 ///
122 /// The memory returned by `alloc` is guaranteed to abide by the `Layout` returned from
123 /// `layout`.
124 unsafe fn alloc(&mut self) -> Option<NonNull<u8>>;
125
126 /// Deallocates an object previously returned by `alloc`.
127 ///
128 /// If `x` was not obtained through a call to `alloc`, or if `x` has already been `dealloc`'d,
129 /// the behavior of `dealloc` is undefined.
130 unsafe fn dealloc(&mut self, x: NonNull<u8>);
131
132 /// Allocator-specific method for signalling an out-of-memory condition.
133 ///
134 /// `oom` aborts the thread or process, optionally performing cleanup or logging diagnostic
135 /// information before panicking or aborting.
136 ///
137 /// `oom` is meant to be used by clients which are unable to cope with an unsatisfied
138 /// allocation request, and wish to abandon computation rather than attempt to recover locally.
139 /// The allocator likely has more insight into why the request failed, and thus can likely
140 /// print more informative diagnostic information than the client could.
141 ///
142 /// Implementations of the `oom` method are discouraged from infinitely regressing in nested
143 /// calls to `oom`. In practice this means implementors should eschew allocating, especially
144 /// from `self` (directly or indirectly).
145 ///
146 /// Implementions of `alloc` are discouraged from panicking (or aborting) in the event of
147 /// memory exhaustion; instead they should return an error and let the client decide whether to
148 /// invoke this `oom` method in response.
149 fn oom(&mut self) -> ! {
150 unsafe { abort() }
151 }
152}
153
154unsafe impl<T> UntypedObjectAlloc for ObjectAlloc<T> {
155 fn layout(&self) -> Layout {
156 // NOTE: This is safe because the layout method doesn't guarantee that it provides the most
157 // specific layout, but rather simply that all objects returned from alloc are guaranteed
158 // to satisfy by this layout. This particular ObjectAlloc could have been configured with a
159 // more strict alignment than T's alignment, but that's OK.
160 Layout::new::<T>()
161 }
162
163 unsafe fn alloc(&mut self) -> Option<NonNull<u8>> {
164 ObjectAlloc::alloc(self).map(|x| x.cast())
165 }
166
167 unsafe fn dealloc(&mut self, x: NonNull<u8>) {
168 ObjectAlloc::dealloc(self, x.cast());
169 }
170}