src/doc/nomicon/src/vec/vec-alloc.md

   1 # Allocating Memory
   2
   3 Using `NonNull` throws a wrench in an important feature of Vec (and indeed all of
   4 the std collections): creating an empty Vec doesn't actually allocate at all. This
   5 is not the same as allocating a zero-sized memory block, which is not allowed by
   6 the global allocator (it results in undefined behavior!). So if we can't allocate,
   7 but also can't put a null pointer in `ptr`, what do we do in `Vec::new`? Well, we
   8 just put some other garbage in there!
   9
  10 This is perfectly fine because we already have `cap == 0` as our sentinel for no
  11 allocation. We don't even need to handle it specially in almost any code because
  12 we usually need to check if `cap > len` or `len > 0` anyway. The recommended
  13 Rust value to put here is `mem::align_of::<T>()`. `NonNull` provides a convenience
  14 for this: `NonNull::dangling()`. There are quite a few places where we'll
  15 want to use `dangling` because there's no real allocation to talk about but
  16 `null` would make the compiler do bad things.
  17
  18 So:
  19
  20 <!-- ignore: explanation code -->
  21 ```rust,ignore
  22 use std::mem;
  23
  24 impl<T> Vec<T> {
  25     fn new() -> Self {
  26         assert!(mem::size_of::<T>() != 0, "We're not ready to handle ZSTs");
  27         Vec {
  28             ptr: NonNull::dangling(),
  29             len: 0,
  30             cap: 0,
  31             _marker: PhantomData,
  32         }
  33     }
  34 }
  35 # fn main() {}
  36 ```
  37
  38 I slipped in that assert there because zero-sized types will require some
  39 special handling throughout our code, and I want to defer the issue for now.
  40 Without this assert, some of our early drafts will do some Very Bad Things.
  41
  42 Next we need to figure out what to actually do when we *do* want space. For that,
  43 we use the global allocation functions [`alloc`][alloc], [`realloc`][realloc],
  44 and [`dealloc`][dealloc] which are available in stable Rust in
  45 [`std::alloc`][std_alloc]. These functions are expected to become deprecated in
  46 favor of the methods of [`std::alloc::Global`][Global] after this type is stabilized.
  47
  48 We'll also need a way to handle out-of-memory (OOM) conditions. The standard
  49 library provides a function [`alloc::handle_alloc_error`][handle_alloc_error],
  50 which will abort the program in a platform-specific manner.
  51 The reason we abort and don't panic is because unwinding can cause allocations
  52 to happen, and that seems like a bad thing to do when your allocator just came
  53 back with "hey I don't have any more memory".
  54
  55 Of course, this is a bit silly since most platforms don't actually run out of
  56 memory in a conventional way. Your operating system will probably kill the
  57 application by another means if you legitimately start using up all the memory.
  58 The most likely way we'll trigger OOM is by just asking for ludicrous quantities
  59 of memory at once (e.g. half the theoretical address space). As such it's
  60 *probably* fine to panic and nothing bad will happen. Still, we're trying to be
  61 like the standard library as much as possible, so we'll just kill the whole
  62 program.
  63
  64 Okay, now we can write growing. Roughly, we want to have this logic:
  65
  66 ```text
  67 if cap == 0:
  68     allocate()
  69     cap = 1
  70 else:
  71     reallocate()
  72     cap *= 2
  73 ```
  74
  75 But Rust's only supported allocator API is so low level that we'll need to do a
  76 fair bit of extra work. We also need to guard against some special
  77 conditions that can occur with really large allocations or empty allocations.
  78
  79 In particular, `ptr::offset` will cause us a lot of trouble, because it has
  80 the semantics of LLVM's GEP inbounds instruction. If you're fortunate enough to
  81 not have dealt with this instruction, here's the basic story with GEP: alias
  82 analysis, alias analysis, alias analysis. It's super important to an optimizing
  83 compiler to be able to reason about data dependencies and aliasing.
  84
  85 As a simple example, consider the following fragment of code:
  86
  87 <!-- ignore: simplified code -->
  88 ```rust,ignore
  89 *x *= 7;
  90 *y *= 3;
  91 ```
  92
  93 If the compiler can prove that `x` and `y` point to different locations in
  94 memory, the two operations can in theory be executed in parallel (by e.g.
  95 loading them into different registers and working on them independently).
  96 However the compiler can't do this in general because if x and y point to
  97 the same location in memory, the operations need to be done to the same value,
  98 and they can't just be merged afterwards.
  99
 100 When you use GEP inbounds, you are specifically telling LLVM that the offsets
 101 you're about to do are within the bounds of a single "allocated" entity. The
 102 ultimate payoff being that LLVM can assume that if two pointers are known to
 103 point to two disjoint objects, all the offsets of those pointers are *also*
 104 known to not alias (because you won't just end up in some random place in
 105 memory). LLVM is heavily optimized to work with GEP offsets, and inbounds
 106 offsets are the best of all, so it's important that we use them as much as
 107 possible.
 108
 109 So that's what GEP's about, how can it cause us trouble?
 110
 111 The first problem is that we index into arrays with unsigned integers, but
 112 GEP (and as a consequence `ptr::offset`) takes a signed integer. This means
 113 that half of the seemingly valid indices into an array will overflow GEP and
 114 actually go in the wrong direction! As such we must limit all allocations to
 115 `isize::MAX` elements. This actually means we only need to worry about
 116 byte-sized objects, because e.g. `> isize::MAX` `u16`s will truly exhaust all of
 117 the system's memory. However in order to avoid subtle corner cases where someone
 118 reinterprets some array of `< isize::MAX` objects as bytes, std limits all
 119 allocations to `isize::MAX` bytes.
 120
 121 On all 64-bit targets that Rust currently supports we're artificially limited
 122 to significantly less than all 64 bits of the address space (modern x64
 123 platforms only expose 48-bit addressing), so we can rely on just running out of
 124 memory first. However on 32-bit targets, particularly those with extensions to
 125 use more of the address space (PAE x86 or x32), it's theoretically possible to
 126 successfully allocate more than `isize::MAX` bytes of memory.
 127
 128 However since this is a tutorial, we're not going to be particularly optimal
 129 here, and just unconditionally check, rather than use clever platform-specific
 130 `cfg`s.
 131
 132 The other corner-case we need to worry about is empty allocations. There will
 133 be two kinds of empty allocations we need to worry about: `cap = 0` for all T,
 134 and `cap > 0` for zero-sized types.
 135
 136 These cases are tricky because they come
 137 down to what LLVM means by "allocated". LLVM's notion of an
 138 allocation is significantly more abstract than how we usually use it. Because
 139 LLVM needs to work with different languages' semantics and custom allocators,
 140 it can't really intimately understand allocation. Instead, the main idea behind
 141 allocation is "doesn't overlap with other stuff". That is, heap allocations,
 142 stack allocations, and globals don't randomly overlap. Yep, it's about alias
 143 analysis. As such, Rust can technically play a bit fast and loose with the notion of
 144 an allocation as long as it's *consistent*.
 145
 146 Getting back to the empty allocation case, there are a couple of places where
 147 we want to offset by 0 as a consequence of generic code. The question is then:
 148 is it consistent to do so? For zero-sized types, we have concluded that it is
 149 indeed consistent to do a GEP inbounds offset by an arbitrary number of
 150 elements. This is a runtime no-op because every element takes up no space,
 151 and it's fine to pretend that there's infinite zero-sized types allocated
 152 at `0x01`. No allocator will ever allocate that address, because they won't
 153 allocate `0x00` and they generally allocate to some minimal alignment higher
 154 than a byte. Also generally the whole first page of memory is
 155 protected from being allocated anyway (a whole 4k, on many platforms).
 156
 157 However what about for positive-sized types? That one's a bit trickier. In
 158 principle, you can argue that offsetting by 0 gives LLVM no information: either
 159 there's an element before the address or after it, but it can't know which.
 160 However we've chosen to conservatively assume that it may do bad things. As
 161 such we will guard against this case explicitly.
 162
 163 *Phew*
 164
 165 Ok with all the nonsense out of the way, let's actually allocate some memory:
 166
 167 <!-- ignore: simplified code -->
 168 ```rust,ignore
 169 use std::alloc::{self, Layout};
 170
 171 impl<T> Vec<T> {
 172     fn grow(&mut self) {
 173         let (new_cap, new_layout) = if self.cap == 0 {
 174             (1, Layout::array::<T>(1).unwrap())
 175         } else {
 176             // This can't overflow since self.cap <= isize::MAX.
 177             let new_cap = 2 * self.cap;
 178
 179             // `Layout::array` checks that the number of bytes is <= usize::MAX,
 180             // but this is redundant since old_layout.size() <= isize::MAX,
 181             // so the `unwrap` should never fail.
 182             let new_layout = Layout::array::<T>(new_cap).unwrap();
 183             (new_cap, new_layout)
 184         };
 185
 186         // Ensure that the new allocation doesn't exceed `isize::MAX` bytes.
 187         assert!(new_layout.size() <= isize::MAX as usize, "Allocation too large");
 188
 189         let new_ptr = if self.cap == 0 {
 190             unsafe { alloc::alloc(new_layout) }
 191         } else {
 192             let old_layout = Layout::array::<T>(self.cap).unwrap();
 193             let old_ptr = self.ptr.as_ptr() as *mut u8;
 194             unsafe { alloc::realloc(old_ptr, old_layout, new_layout.size()) }
 195         };
 196
 197         // If allocation fails, `new_ptr` will be null, in which case we abort.
 198         self.ptr = match NonNull::new(new_ptr as *mut T) {
 199             Some(p) => p,
 200             None => alloc::handle_alloc_error(new_layout),
 201         };
 202         self.cap = new_cap;
 203     }
 204 }
 205 # fn main() {}
 206 ```
 207
 208 [Global]: ../../std/alloc/struct.Global.html
 209 [handle_alloc_error]: ../../alloc/alloc/fn.handle_alloc_error.html
 210 [alloc]: ../../alloc/alloc/fn.alloc.html
 211 [realloc]: ../../alloc/alloc/fn.realloc.html
 212 [dealloc]: ../../alloc/alloc/fn.dealloc.html
 213 [std_alloc]: ../../alloc/alloc/index.html