1// This module provides a relatively simple thread-safe pool of reusable
2// objects. For the most part, it's implemented by a stack represented by a
3// Mutex<Vec<T>>. It has one small trick: because unlocking a mutex is somewhat
4// costly, in the case where a pool is accessed by the first thread that tried
5// to get a value, we bypass the mutex. Here are some benchmarks showing the
6// difference.
7//
8// 2022-10-15: These benchmarks are from the old regex crate and they aren't
9// easy to reproduce because some rely on older implementations of Pool that
10// are no longer around. I've left the results here for posterity, but any
11// enterprising individual should feel encouraged to re-litigate the way Pool
12// works. I am not at all certain it is the best approach.
13//
14// 1) misc::anchored_literal_long_non_match 21 (18571 MB/s)
15// 2) misc::anchored_literal_long_non_match 107 (3644 MB/s)
16// 3) misc::anchored_literal_long_non_match 45 (8666 MB/s)
17// 4) misc::anchored_literal_long_non_match 19 (20526 MB/s)
18//
19// (1) represents our baseline: the master branch at the time of writing when
20// using the 'thread_local' crate to implement the pool below.
21//
22// (2) represents a naive pool implemented completely via Mutex<Vec<T>>. There
23// is no special trick for bypassing the mutex.
24//
25// (3) is the same as (2), except it uses Mutex<Vec<Box<T>>>. It is twice as
26// fast because a Box<T> is much smaller than the T we use with a Pool in this
27// crate. So pushing and popping a Box<T> from a Vec is quite a bit faster
28// than for T.
29//
30// (4) is the same as (3), but with the trick for bypassing the mutex in the
31// case of the first-to-get thread.
32//
33// Why move off of thread_local? Even though (4) is a hair faster than (1)
34// above, this was not the main goal. The main goal was to move off of
35// thread_local and find a way to *simply* re-capture some of its speed for
36// regex's specific case. So again, why move off of it? The *primary* reason is
37// because of memory leaks. See https://github.com/rust-lang/regex/issues/362
38// for example. (Why do I want it to be simple? Well, I suppose what I mean is,
39// "use as much safe code as possible to minimize risk and be as sure as I can
40// be that it is correct.")
41//
42// My guess is that the thread_local design is probably not appropriate for
43// regex since its memory usage scales to the number of active threads that
44// have used a regex, where as the pool below scales to the number of threads
45// that simultaneously use a regex. While neither case permits contraction,
46// since we own the pool data structure below, we can add contraction if a
47// clear use case pops up in the wild. More pressingly though, it seems that
48// there are at least some use case patterns where one might have many threads
49// sitting around that might have used a regex at one point. While thread_local
50// does try to reuse space previously used by a thread that has since stopped,
51// its maximal memory usage still scales with the total number of active
52// threads. In contrast, the pool below scales with the total number of threads
53// *simultaneously* using the pool. The hope is that this uses less memory
54// overall. And if it doesn't, we can hopefully tune it somehow.
55//
56// It seems that these sort of conditions happen frequently
57// in FFI inside of other more "managed" languages. This was
58// mentioned in the issue linked above, and also mentioned here:
59// https://github.com/BurntSushi/rure-go/issues/3. And in particular, users
60// confirm that disabling the use of thread_local resolves the leak.
61//
62// There were other weaker reasons for moving off of thread_local as well.
63// Namely, at the time, I was looking to reduce dependencies. And for something
64// like regex, maintenance can be simpler when we own the full dependency tree.
65//
66// Note that I am not entirely happy with this pool. It has some subtle
67// implementation details and is overall still observable (even with the
68// thread owner optimization) in benchmarks. If someone wants to take a crack
69// at building something better, please file an issue. Even if it means a
70// different API. The API exposed by this pool is not the minimal thing that
71// something like a 'Regex' actually needs. It could adapt to, for example,
72// an API more like what is found in the 'thread_local' crate. However, we do
73// really need to support the no-std alloc-only context, or else the regex
74// crate wouldn't be able to support no-std alloc-only. However, I'm generally
75// okay with making the alloc-only context slower (as it is here), although I
76// do find it unfortunate.
77
78/*!
79A thread safe memory pool.
80
81The principal type in this module is a [`Pool`]. It main use case is for
82holding a thread safe collection of mutable scratch spaces (usually called
83`Cache` in this crate) that regex engines need to execute a search. This then
84permits sharing the same read-only regex object across multiple threads while
85having a quick way of reusing scratch space in a thread safe way. This avoids
86needing to re-create the scratch space for every search, which could wind up
87being quite expensive.
88*/
89
90/// A thread safe pool that works in an `alloc`-only context.
91///
92/// Getting a value out comes with a guard. When that guard is dropped, the
93/// value is automatically put back in the pool. The guard provides both a
94/// `Deref` and a `DerefMut` implementation for easy access to an underlying
95/// `T`.
96///
97/// A `Pool` impls `Sync` when `T` is `Send` (even if `T` is not `Sync`). This
98/// is possible because a pool is guaranteed to provide a value to exactly one
99/// thread at any time.
100///
101/// Currently, a pool never contracts in size. Its size is proportional to the
102/// maximum number of simultaneous uses. This may change in the future.
103///
104/// A `Pool` is a particularly useful data structure for this crate because
105/// many of the regex engines require a mutable "cache" in order to execute
106/// a search. Since regexes themselves tend to be global, the problem is then:
107/// how do you get a mutable cache to execute a search? You could:
108///
109/// 1. Use a `thread_local!`, which requires the standard library and requires
110/// that the regex pattern be statically known.
111/// 2. Use a `Pool`.
112/// 3. Make the cache an explicit dependency in your code and pass it around.
113/// 4. Put the cache state in a `Mutex`, but this means only one search can
114/// execute at a time.
115/// 5. Create a new cache for every search.
116///
117/// A `thread_local!` is perhaps the best choice if it works for your use case.
118/// Putting the cache in a mutex or creating a new cache for every search are
119/// perhaps the worst choices. Of the remaining two choices, whether you use
120/// this `Pool` or thread through a cache explicitly in your code is a matter
121/// of taste and depends on your code architecture.
122///
123/// # Warning: may use a spin lock
124///
125/// When this crate is compiled _without_ the `std` feature, then this type
126/// may used a spin lock internally. This can have subtle effects that may
127/// be undesirable. See [Spinlocks Considered Harmful][spinharm] for a more
128/// thorough treatment of this topic.
129///
130/// [spinharm]: https://matklad.github.io/2020/01/02/spinlocks-considered-harmful.html
131///
132/// # Example
133///
134/// This example shows how to share a single hybrid regex among multiple
135/// threads, while also safely getting exclusive access to a hybrid's
136/// [`Cache`](crate::hybrid::regex::Cache) without preventing other searches
137/// from running while your thread uses the `Cache`.
138///
139/// ```
140/// use regex_automata::{
141/// hybrid::regex::{Cache, Regex},
142/// util::{lazy::Lazy, pool::Pool},
143/// Match,
144/// };
145///
146/// static RE: Lazy<Regex> =
147/// Lazy::new(|| Regex::new("foo[0-9]+bar").unwrap());
148/// static CACHE: Lazy<Pool<Cache>> =
149/// Lazy::new(|| Pool::new(|| RE.create_cache()));
150///
151/// let expected = Some(Match::must(0, 3..14));
152/// assert_eq!(expected, RE.find(&mut CACHE.get(), b"zzzfoo12345barzzz"));
153/// ```
154pub struct Pool<T, F = fn() -> T>(alloc::boxed::Box<inner::Pool<T, F>>);
155
156impl<T, F> Pool<T, F> {
157 /// Create a new pool. The given closure is used to create values in
158 /// the pool when necessary.
159 pub fn new(create: F) -> Pool<T, F> {
160 Pool(alloc::boxed::Box::new(inner::Pool::new(create)))
161 }
162}
163
164impl<T: Send, F: Fn() -> T> Pool<T, F> {
165 /// Get a value from the pool. The caller is guaranteed to have
166 /// exclusive access to the given value. Namely, it is guaranteed that
167 /// this will never return a value that was returned by another call to
168 /// `get` but was not put back into the pool.
169 ///
170 /// When the guard goes out of scope and its destructor is called, then
171 /// it will automatically be put back into the pool. Alternatively,
172 /// [`PoolGuard::put`] may be used to explicitly put it back in the pool
173 /// without relying on its destructor.
174 ///
175 /// Note that there is no guarantee provided about which value in the
176 /// pool is returned. That is, calling get, dropping the guard (causing
177 /// the value to go back into the pool) and then calling get again is
178 /// *not* guaranteed to return the same value received in the first `get`
179 /// call.
180 #[inline]
181 pub fn get(&self) -> PoolGuard<'_, T, F> {
182 PoolGuard(self.0.get())
183 }
184}
185
186impl<T: core::fmt::Debug, F> core::fmt::Debug for Pool<T, F> {
187 fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
188 f.debug_tuple(name:"Pool").field(&self.0).finish()
189 }
190}
191
192/// A guard that is returned when a caller requests a value from the pool.
193///
194/// The purpose of the guard is to use RAII to automatically put the value
195/// back in the pool once it's dropped.
196pub struct PoolGuard<'a, T: Send, F: Fn() -> T>(inner::PoolGuard<'a, T, F>);
197
198impl<'a, T: Send, F: Fn() -> T> PoolGuard<'a, T, F> {
199 /// Consumes this guard and puts it back into the pool.
200 ///
201 /// This circumvents the guard's `Drop` implementation. This can be useful
202 /// in circumstances where the automatic `Drop` results in poorer codegen,
203 /// such as calling non-inlined functions.
204 #[inline]
205 pub fn put(this: PoolGuard<'_, T, F>) {
206 inner::PoolGuard::put(this.0);
207 }
208}
209
210impl<'a, T: Send, F: Fn() -> T> core::ops::Deref for PoolGuard<'a, T, F> {
211 type Target = T;
212
213 #[inline]
214 fn deref(&self) -> &T {
215 self.0.value()
216 }
217}
218
219impl<'a, T: Send, F: Fn() -> T> core::ops::DerefMut for PoolGuard<'a, T, F> {
220 #[inline]
221 fn deref_mut(&mut self) -> &mut T {
222 self.0.value_mut()
223 }
224}
225
226impl<'a, T: Send + core::fmt::Debug, F: Fn() -> T> core::fmt::Debug
227 for PoolGuard<'a, T, F>
228{
229 fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
230 f.debug_tuple(name:"PoolGuard").field(&self.0).finish()
231 }
232}
233
234#[cfg(feature = "std")]
235mod inner {
236 use core::{
237 cell::UnsafeCell,
238 panic::{RefUnwindSafe, UnwindSafe},
239 sync::atomic::{AtomicUsize, Ordering},
240 };
241
242 use alloc::{boxed::Box, vec, vec::Vec};
243
244 use std::{sync::Mutex, thread_local};
245
246 /// An atomic counter used to allocate thread IDs.
247 ///
248 /// We specifically start our counter at 3 so that we can use the values
249 /// less than it as sentinels.
250 static COUNTER: AtomicUsize = AtomicUsize::new(3);
251
252 /// A thread ID indicating that there is no owner. This is the initial
253 /// state of a pool. Once a pool has an owner, there is no way to change
254 /// it.
255 static THREAD_ID_UNOWNED: usize = 0;
256
257 /// A thread ID indicating that the special owner value is in use and not
258 /// available. This state is useful for avoiding a case where the owner
259 /// of a pool calls `get` before putting the result of a previous `get`
260 /// call back into the pool.
261 static THREAD_ID_INUSE: usize = 1;
262
263 /// This sentinel is used to indicate that a guard has already been dropped
264 /// and should not be re-dropped. We use this because our drop code can be
265 /// called outside of Drop and thus there could be a bug in the internal
266 /// implementation that results in trying to put the same guard back into
267 /// the same pool multiple times, and *that* could result in UB if we
268 /// didn't mark the guard as already having been put back in the pool.
269 ///
270 /// So this isn't strictly necessary, but this let's us define some
271 /// routines as safe (like PoolGuard::put_imp) that we couldn't otherwise
272 /// do.
273 static THREAD_ID_DROPPED: usize = 2;
274
275 /// The number of stacks we use inside of the pool. These are only used for
276 /// non-owners. That is, these represent the "slow" path.
277 ///
278 /// In the original implementation of this pool, we only used a single
279 /// stack. While this might be okay for a couple threads, the prevalence of
280 /// 32, 64 and even 128 core CPUs has made it untenable. The contention
281 /// such an environment introduces when threads are doing a lot of searches
282 /// on short haystacks (a not uncommon use case) is palpable and leads to
283 /// huge slowdowns.
284 ///
285 /// This constant reflects a change from using one stack to the number of
286 /// stacks that this constant is set to. The stack for a particular thread
287 /// is simply chosen by `thread_id % MAX_POOL_STACKS`. The idea behind
288 /// this setup is that there should be a good chance that accesses to the
289 /// pool will be distributed over several stacks instead of all of them
290 /// converging to one.
291 ///
292 /// This is not a particularly smart or dynamic strategy. Fixing this to a
293 /// specific number has at least two downsides. First is that it will help,
294 /// say, an 8 core CPU more than it will a 128 core CPU. (But, crucially,
295 /// it will still help the 128 core case.) Second is that this may wind
296 /// up being a little wasteful with respect to memory usage. Namely, if a
297 /// regex is used on one thread and then moved to another thread, then it
298 /// could result in creating a new copy of the data in the pool even though
299 /// only one is actually needed.
300 ///
301 /// And that memory usage bit is why this is set to 8 and not, say, 64.
302 /// Keeping it at 8 limits, to an extent, how much unnecessary memory can
303 /// be allocated.
304 ///
305 /// In an ideal world, we'd be able to have something like this:
306 ///
307 /// * Grow the number of stacks as the number of concurrent callers
308 /// increases. I spent a little time trying this, but even just adding an
309 /// atomic addition/subtraction for each pop/push for tracking concurrent
310 /// callers led to a big perf hit. Since even more work would seemingly be
311 /// required than just an addition/subtraction, I abandoned this approach.
312 /// * The maximum amount of memory used should scale with respect to the
313 /// number of concurrent callers and *not* the total number of existing
314 /// threads. This is primarily why the `thread_local` crate isn't used, as
315 /// as some environments spin up a lot of threads. This led to multiple
316 /// reports of extremely high memory usage (often described as memory
317 /// leaks).
318 /// * Even more ideally, the pool should contract in size. That is, it
319 /// should grow with bursts and then shrink. But this is a pretty thorny
320 /// issue to tackle and it might be better to just not.
321 /// * It would be nice to explore the use of, say, a lock-free stack
322 /// instead of using a mutex to guard a `Vec` that is ultimately just
323 /// treated as a stack. The main thing preventing me from exploring this
324 /// is the ABA problem. The `crossbeam` crate has tools for dealing with
325 /// this sort of problem (via its epoch based memory reclamation strategy),
326 /// but I can't justify bringing in all of `crossbeam` as a dependency of
327 /// `regex` for this.
328 ///
329 /// See this issue for more context and discussion:
330 /// https://github.com/rust-lang/regex/issues/934
331 const MAX_POOL_STACKS: usize = 8;
332
333 thread_local!(
334 /// A thread local used to assign an ID to a thread.
335 static THREAD_ID: usize = {
336 let next = COUNTER.fetch_add(1, Ordering::Relaxed);
337 // SAFETY: We cannot permit the reuse of thread IDs since reusing a
338 // thread ID might result in more than one thread "owning" a pool,
339 // and thus, permit accessing a mutable value from multiple threads
340 // simultaneously without synchronization. The intent of this panic
341 // is to be a sanity check. It is not expected that the thread ID
342 // space will actually be exhausted in practice. Even on a 32-bit
343 // system, it would require spawning 2^32 threads (although they
344 // wouldn't all need to run simultaneously, so it is in theory
345 // possible).
346 //
347 // This checks that the counter never wraps around, since atomic
348 // addition wraps around on overflow.
349 if next == 0 {
350 panic!("regex: thread ID allocation space exhausted");
351 }
352 next
353 };
354 );
355
356 /// This puts each stack in the pool below into its own cache line. This is
357 /// an absolutely critical optimization that tends to have the most impact
358 /// in high contention workloads. Without forcing each mutex protected
359 /// into its own cache line, high contention exacerbates the performance
360 /// problem by causing "false sharing." By putting each mutex in its own
361 /// cache-line, we avoid the false sharing problem and the affects of
362 /// contention are greatly reduced.
363 #[derive(Debug)]
364 #[repr(C, align(64))]
365 struct CacheLine<T>(T);
366
367 /// A thread safe pool utilizing std-only features.
368 ///
369 /// The main difference between this and the simplistic alloc-only pool is
370 /// the use of std::sync::Mutex and an "owner thread" optimization that
371 /// makes accesses by the owner of a pool faster than all other threads.
372 /// This makes the common case of running a regex within a single thread
373 /// faster by avoiding mutex unlocking.
374 pub(super) struct Pool<T, F> {
375 /// A function to create more T values when stack is empty and a caller
376 /// has requested a T.
377 create: F,
378 /// Multiple stacks of T values to hand out. These are used when a Pool
379 /// is accessed by a thread that didn't create it.
380 ///
381 /// Conceptually this is `Mutex<Vec<Box<T>>>`, but sharded out to make
382 /// it scale better under high contention work-loads. We index into
383 /// this sequence via `thread_id % stacks.len()`.
384 stacks: Vec<CacheLine<Mutex<Vec<Box<T>>>>>,
385 /// The ID of the thread that owns this pool. The owner is the thread
386 /// that makes the first call to 'get'. When the owner calls 'get', it
387 /// gets 'owner_val' directly instead of returning a T from 'stack'.
388 /// See comments elsewhere for details, but this is intended to be an
389 /// optimization for the common case that makes getting a T faster.
390 ///
391 /// It is initialized to a value of zero (an impossible thread ID) as a
392 /// sentinel to indicate that it is unowned.
393 owner: AtomicUsize,
394 /// A value to return when the caller is in the same thread that
395 /// first called `Pool::get`.
396 ///
397 /// This is set to None when a Pool is first created, and set to Some
398 /// once the first thread calls Pool::get.
399 owner_val: UnsafeCell<Option<T>>,
400 }
401
402 // SAFETY: Since we want to use a Pool from multiple threads simultaneously
403 // behind an Arc, we need for it to be Sync. In cases where T is sync,
404 // Pool<T> would be Sync. However, since we use a Pool to store mutable
405 // scratch space, we wind up using a T that has interior mutability and is
406 // thus itself not Sync. So what we *really* want is for our Pool<T> to by
407 // Sync even when T is not Sync (but is at least Send).
408 //
409 // The only non-sync aspect of a Pool is its 'owner_val' field, which is
410 // used to implement faster access to a pool value in the common case of
411 // a pool being accessed in the same thread in which it was created. The
412 // 'stack' field is also shared, but a Mutex<T> where T: Send is already
413 // Sync. So we only need to worry about 'owner_val'.
414 //
415 // The key is to guarantee that 'owner_val' can only ever be accessed from
416 // one thread. In our implementation below, we guarantee this by only
417 // returning the 'owner_val' when the ID of the current thread matches the
418 // ID of the thread that first called 'Pool::get'. Since this can only ever
419 // be one thread, it follows that only one thread can access 'owner_val' at
420 // any point in time. Thus, it is safe to declare that Pool<T> is Sync when
421 // T is Send.
422 //
423 // If there is a way to achieve our performance goals using safe code, then
424 // I would very much welcome a patch. As it stands, the implementation
425 // below tries to balance safety with performance. The case where a Regex
426 // is used from multiple threads simultaneously will suffer a bit since
427 // getting a value out of the pool will require unlocking a mutex.
428 //
429 // We require `F: Send + Sync` because we call `F` at any point on demand,
430 // potentially from multiple threads simultaneously.
431 unsafe impl<T: Send, F: Send + Sync> Sync for Pool<T, F> {}
432
433 // If T is UnwindSafe, then since we provide exclusive access to any
434 // particular value in the pool, the pool should therefore also be
435 // considered UnwindSafe.
436 //
437 // We require `F: UnwindSafe + RefUnwindSafe` because we call `F` at any
438 // point on demand, so it needs to be unwind safe on both dimensions for
439 // the entire Pool to be unwind safe.
440 impl<T: UnwindSafe, F: UnwindSafe + RefUnwindSafe> UnwindSafe for Pool<T, F> {}
441
442 // If T is UnwindSafe, then since we provide exclusive access to any
443 // particular value in the pool, the pool should therefore also be
444 // considered RefUnwindSafe.
445 //
446 // We require `F: UnwindSafe + RefUnwindSafe` because we call `F` at any
447 // point on demand, so it needs to be unwind safe on both dimensions for
448 // the entire Pool to be unwind safe.
449 impl<T: UnwindSafe, F: UnwindSafe + RefUnwindSafe> RefUnwindSafe
450 for Pool<T, F>
451 {
452 }
453
454 impl<T, F> Pool<T, F> {
455 /// Create a new pool. The given closure is used to create values in
456 /// the pool when necessary.
457 pub(super) fn new(create: F) -> Pool<T, F> {
458 // FIXME: Now that we require 1.65+, Mutex::new is available as
459 // const... So we can almost mark this function as const. But of
460 // course, we're creating a Vec of stacks below (we didn't when I
461 // originally wrote this code). It seems like the best way to work
462 // around this would be to use a `[Stack; MAX_POOL_STACKS]` instead
463 // of a `Vec<Stack>`. I refrained from making this change at time
464 // of writing (2023/10/08) because I was making a lot of other
465 // changes at the same time and wanted to do this more carefully.
466 // Namely, because of the cache line optimization, that `[Stack;
467 // MAX_POOL_STACKS]` would be quite big. It's unclear how bad (if
468 // at all) that would be.
469 //
470 // Another choice would be to lazily allocate the stacks, but...
471 // I'm not so sure about that. Seems like a fair bit of complexity?
472 //
473 // Maybe there's a simple solution I'm missing.
474 //
475 // ... OK, I tried to fix this. First, I did it by putting `stacks`
476 // in an `UnsafeCell` and using a `Once` to lazily initialize it.
477 // I benchmarked it and everything looked okay. I then made this
478 // function `const` and thought I was just about done. But the
479 // public pool type wraps its inner pool in a `Box` to keep its
480 // size down. Blech.
481 //
482 // So then I thought that I could push the box down into this
483 // type (and leave the non-std version unboxed) and use the same
484 // `UnsafeCell` technique to lazily initialize it. This has the
485 // downside of the `Once` now needing to get hit in the owner fast
486 // path, but maybe that's OK? However, I then realized that we can
487 // only lazily initialize `stacks`, `owner` and `owner_val`. The
488 // `create` function needs to be put somewhere outside of the box.
489 // So now the pool is a `Box`, `Once` and a function. Now we're
490 // starting to defeat the point of boxing in the first place. So I
491 // backed out that change too.
492 //
493 // Back to square one. I maybe we just don't make a pool's
494 // constructor const and live with it. It's probably not a huge
495 // deal.
496 let mut stacks = Vec::with_capacity(MAX_POOL_STACKS);
497 for _ in 0..stacks.capacity() {
498 stacks.push(CacheLine(Mutex::new(vec![])));
499 }
500 let owner = AtomicUsize::new(THREAD_ID_UNOWNED);
501 let owner_val = UnsafeCell::new(None); // init'd on first access
502 Pool { create, stacks, owner, owner_val }
503 }
504 }
505
506 impl<T: Send, F: Fn() -> T> Pool<T, F> {
507 /// Get a value from the pool. This may block if another thread is also
508 /// attempting to retrieve a value from the pool.
509 #[inline]
510 pub(super) fn get(&self) -> PoolGuard<'_, T, F> {
511 // Our fast path checks if the caller is the thread that "owns"
512 // this pool. Or stated differently, whether it is the first thread
513 // that tried to extract a value from the pool. If it is, then we
514 // can return a T to the caller without going through a mutex.
515 //
516 // SAFETY: We must guarantee that only one thread gets access
517 // to this value. Since a thread is uniquely identified by the
518 // THREAD_ID thread local, it follows that if the caller's thread
519 // ID is equal to the owner, then only one thread may receive this
520 // value. This is also why we can get away with what looks like a
521 // racy load and a store. We know that if 'owner == caller', then
522 // only one thread can be here, so we don't need to worry about any
523 // other thread setting the owner to something else.
524 let caller = THREAD_ID.with(|id| *id);
525 let owner = self.owner.load(Ordering::Acquire);
526 if caller == owner {
527 // N.B. We could also do a CAS here instead of a load/store,
528 // but ad hoc benchmarking suggests it is slower. And a lot
529 // slower in the case where `get_slow` is common.
530 self.owner.store(THREAD_ID_INUSE, Ordering::Release);
531 return self.guard_owned(caller);
532 }
533 self.get_slow(caller, owner)
534 }
535
536 /// This is the "slow" version that goes through a mutex to pop an
537 /// allocated value off a stack to return to the caller. (Or, if the
538 /// stack is empty, a new value is created.)
539 ///
540 /// If the pool has no owner, then this will set the owner.
541 #[cold]
542 fn get_slow(
543 &self,
544 caller: usize,
545 owner: usize,
546 ) -> PoolGuard<'_, T, F> {
547 if owner == THREAD_ID_UNOWNED {
548 // This sentinel means this pool is not yet owned. We try to
549 // atomically set the owner. If we do, then this thread becomes
550 // the owner and we can return a guard that represents the
551 // special T for the owner.
552 //
553 // Note that we set the owner to a different sentinel that
554 // indicates that the owned value is in use. The owner ID will
555 // get updated to the actual ID of this thread once the guard
556 // returned by this function is put back into the pool.
557 let res = self.owner.compare_exchange(
558 THREAD_ID_UNOWNED,
559 THREAD_ID_INUSE,
560 Ordering::AcqRel,
561 Ordering::Acquire,
562 );
563 if res.is_ok() {
564 // SAFETY: A successful CAS above implies this thread is
565 // the owner and that this is the only such thread that
566 // can reach here. Thus, there is no data race.
567 unsafe {
568 *self.owner_val.get() = Some((self.create)());
569 }
570 return self.guard_owned(caller);
571 }
572 }
573 let stack_id = caller % self.stacks.len();
574 // We try to acquire exclusive access to this thread's stack, and
575 // if so, grab a value from it if we can. We put this in a loop so
576 // that it's easy to tweak and experiment with a different number
577 // of tries. In the end, I couldn't see anything obviously better
578 // than one attempt in ad hoc testing.
579 for _ in 0..1 {
580 let mut stack = match self.stacks[stack_id].0.try_lock() {
581 Err(_) => continue,
582 Ok(stack) => stack,
583 };
584 if let Some(value) = stack.pop() {
585 return self.guard_stack(value);
586 }
587 // Unlock the mutex guarding the stack before creating a fresh
588 // value since we no longer need the stack.
589 drop(stack);
590 let value = Box::new((self.create)());
591 return self.guard_stack(value);
592 }
593 // We're only here if we could get access to our stack, so just
594 // create a new value. This seems like it could be wasteful, but
595 // waiting for exclusive access to a stack when there's high
596 // contention is brutal for perf.
597 self.guard_stack_transient(Box::new((self.create)()))
598 }
599
600 /// Puts a value back into the pool. Callers don't need to call this.
601 /// Once the guard that's returned by 'get' is dropped, it is put back
602 /// into the pool automatically.
603 #[inline]
604 fn put_value(&self, value: Box<T>) {
605 let caller = THREAD_ID.with(|id| *id);
606 let stack_id = caller % self.stacks.len();
607 // As with trying to pop a value from this thread's stack, we
608 // merely attempt to get access to push this value back on the
609 // stack. If there's too much contention, we just give up and throw
610 // the value away.
611 //
612 // Interestingly, in ad hoc benchmarking, it is beneficial to
613 // attempt to push the value back more than once, unlike when
614 // popping the value. I don't have a good theory for why this is.
615 // I guess if we drop too many values then that winds up forcing
616 // the pop operation to create new fresh values and thus leads to
617 // less reuse. There's definitely a balancing act here.
618 for _ in 0..10 {
619 let mut stack = match self.stacks[stack_id].0.try_lock() {
620 Err(_) => continue,
621 Ok(stack) => stack,
622 };
623 stack.push(value);
624 return;
625 }
626 }
627
628 /// Create a guard that represents the special owned T.
629 #[inline]
630 fn guard_owned(&self, caller: usize) -> PoolGuard<'_, T, F> {
631 PoolGuard { pool: self, value: Err(caller), discard: false }
632 }
633
634 /// Create a guard that contains a value from the pool's stack.
635 #[inline]
636 fn guard_stack(&self, value: Box<T>) -> PoolGuard<'_, T, F> {
637 PoolGuard { pool: self, value: Ok(value), discard: false }
638 }
639
640 /// Create a guard that contains a value from the pool's stack with an
641 /// instruction to throw away the value instead of putting it back
642 /// into the pool.
643 #[inline]
644 fn guard_stack_transient(&self, value: Box<T>) -> PoolGuard<'_, T, F> {
645 PoolGuard { pool: self, value: Ok(value), discard: true }
646 }
647 }
648
649 impl<T: core::fmt::Debug, F> core::fmt::Debug for Pool<T, F> {
650 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
651 f.debug_struct("Pool")
652 .field("stacks", &self.stacks)
653 .field("owner", &self.owner)
654 .field("owner_val", &self.owner_val)
655 .finish()
656 }
657 }
658
659 /// A guard that is returned when a caller requests a value from the pool.
660 pub(super) struct PoolGuard<'a, T: Send, F: Fn() -> T> {
661 /// The pool that this guard is attached to.
662 pool: &'a Pool<T, F>,
663 /// This is Err when the guard represents the special "owned" value.
664 /// In which case, the value is retrieved from 'pool.owner_val'. And
665 /// in the special case of `Err(THREAD_ID_DROPPED)`, it means the
666 /// guard has been put back into the pool and should no longer be used.
667 value: Result<Box<T>, usize>,
668 /// When true, the value should be discarded instead of being pushed
669 /// back into the pool. We tend to use this under high contention, and
670 /// this allows us to avoid inflating the size of the pool. (Because
671 /// under contention, we tend to create more values instead of waiting
672 /// for access to a stack of existing values.)
673 discard: bool,
674 }
675
676 impl<'a, T: Send, F: Fn() -> T> PoolGuard<'a, T, F> {
677 /// Return the underlying value.
678 #[inline]
679 pub(super) fn value(&self) -> &T {
680 match self.value {
681 Ok(ref v) => &**v,
682 // SAFETY: This is safe because the only way a PoolGuard gets
683 // created for self.value=Err is when the current thread
684 // corresponds to the owning thread, of which there can only
685 // be one. Thus, we are guaranteed to be providing exclusive
686 // access here which makes this safe.
687 //
688 // Also, since 'owner_val' is guaranteed to be initialized
689 // before an owned PoolGuard is created, the unchecked unwrap
690 // is safe.
691 Err(id) => unsafe {
692 // This assert is *not* necessary for safety, since we
693 // should never be here if the guard had been put back into
694 // the pool. This is a sanity check to make sure we didn't
695 // break an internal invariant.
696 debug_assert_ne!(THREAD_ID_DROPPED, id);
697 (*self.pool.owner_val.get()).as_ref().unwrap_unchecked()
698 },
699 }
700 }
701
702 /// Return the underlying value as a mutable borrow.
703 #[inline]
704 pub(super) fn value_mut(&mut self) -> &mut T {
705 match self.value {
706 Ok(ref mut v) => &mut **v,
707 // SAFETY: This is safe because the only way a PoolGuard gets
708 // created for self.value=None is when the current thread
709 // corresponds to the owning thread, of which there can only
710 // be one. Thus, we are guaranteed to be providing exclusive
711 // access here which makes this safe.
712 //
713 // Also, since 'owner_val' is guaranteed to be initialized
714 // before an owned PoolGuard is created, the unwrap_unchecked
715 // is safe.
716 Err(id) => unsafe {
717 // This assert is *not* necessary for safety, since we
718 // should never be here if the guard had been put back into
719 // the pool. This is a sanity check to make sure we didn't
720 // break an internal invariant.
721 debug_assert_ne!(THREAD_ID_DROPPED, id);
722 (*self.pool.owner_val.get()).as_mut().unwrap_unchecked()
723 },
724 }
725 }
726
727 /// Consumes this guard and puts it back into the pool.
728 #[inline]
729 pub(super) fn put(this: PoolGuard<'_, T, F>) {
730 // Since this is effectively consuming the guard and putting the
731 // value back into the pool, there's no reason to run its Drop
732 // impl after doing this. I don't believe there is a correctness
733 // problem with doing so, but there's definitely a perf problem
734 // by redoing this work. So we avoid it.
735 let mut this = core::mem::ManuallyDrop::new(this);
736 this.put_imp();
737 }
738
739 /// Puts this guard back into the pool by only borrowing the guard as
740 /// mutable. This should be called at most once.
741 #[inline(always)]
742 fn put_imp(&mut self) {
743 match core::mem::replace(&mut self.value, Err(THREAD_ID_DROPPED)) {
744 Ok(value) => {
745 // If we were told to discard this value then don't bother
746 // trying to put it back into the pool. This occurs when
747 // the pop operation failed to acquire a lock and we
748 // decided to create a new value in lieu of contending for
749 // the lock.
750 if self.discard {
751 return;
752 }
753 self.pool.put_value(value);
754 }
755 // If this guard has a value "owned" by the thread, then
756 // the Pool guarantees that this is the ONLY such guard.
757 // Therefore, in order to place it back into the pool and make
758 // it available, we need to change the owner back to the owning
759 // thread's ID. But note that we use the ID that was stored in
760 // the guard, since a guard can be moved to another thread and
761 // dropped. (A previous iteration of this code read from the
762 // THREAD_ID thread local, which uses the ID of the current
763 // thread which may not be the ID of the owning thread! This
764 // also avoids the TLS access, which is likely a hair faster.)
765 Err(owner) => {
766 // If we hit this point, it implies 'put_imp' has been
767 // called multiple times for the same guard which in turn
768 // corresponds to a bug in this implementation.
769 assert_ne!(THREAD_ID_DROPPED, owner);
770 self.pool.owner.store(owner, Ordering::Release);
771 }
772 }
773 }
774 }
775
776 impl<'a, T: Send, F: Fn() -> T> Drop for PoolGuard<'a, T, F> {
777 #[inline]
778 fn drop(&mut self) {
779 self.put_imp();
780 }
781 }
782
783 impl<'a, T: Send + core::fmt::Debug, F: Fn() -> T> core::fmt::Debug
784 for PoolGuard<'a, T, F>
785 {
786 fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
787 f.debug_struct("PoolGuard")
788 .field("pool", &self.pool)
789 .field("value", &self.value)
790 .finish()
791 }
792 }
793}
794
795// FUTURE: We should consider using Mara Bos's nearly-lock-free version of this
796// here: https://gist.github.com/m-ou-se/5fdcbdf7dcf4585199ce2de697f367a4.
797//
798// One reason why I did things with a "mutex" below is that it isolates the
799// safety concerns to just the Mutex, where as the safety of Mara's pool is a
800// bit more sprawling. I also expect this code to not be used that much, and
801// so is unlikely to get as much real world usage with which to test it. That
802// means the "obviously correct" lever is an important one.
803//
804// The specific reason to use Mara's pool is that it is likely faster and also
805// less likely to hit problems with spin-locks, although it is not completely
806// impervious to them.
807//
808// The best solution to this problem, probably, is a truly lock free pool. That
809// could be done with a lock free linked list. The issue is the ABA problem. It
810// is difficult to avoid, and doing so is complex. BUT, the upshot of that is
811// that if we had a truly lock free pool, then we could also use it above in
812// the 'std' pool instead of a Mutex because it should be completely free the
813// problems that come from spin-locks.
814#[cfg(not(feature = "std"))]
815mod inner {
816 use core::{
817 cell::UnsafeCell,
818 panic::{RefUnwindSafe, UnwindSafe},
819 sync::atomic::{AtomicBool, Ordering},
820 };
821
822 use alloc::{boxed::Box, vec, vec::Vec};
823
824 /// A thread safe pool utilizing alloc-only features.
825 ///
826 /// Unlike the std version, it doesn't seem possible(?) to implement the
827 /// "thread owner" optimization because alloc-only doesn't have any concept
828 /// of threads. So the best we can do is just a normal stack. This will
829 /// increase latency in alloc-only environments.
830 pub(super) struct Pool<T, F> {
831 /// A stack of T values to hand out. These are used when a Pool is
832 /// accessed by a thread that didn't create it.
833 stack: Mutex<Vec<Box<T>>>,
834 /// A function to create more T values when stack is empty and a caller
835 /// has requested a T.
836 create: F,
837 }
838
839 // If T is UnwindSafe, then since we provide exclusive access to any
840 // particular value in the pool, it should therefore also be considered
841 // RefUnwindSafe.
842 impl<T: UnwindSafe, F: UnwindSafe> RefUnwindSafe for Pool<T, F> {}
843
844 impl<T, F> Pool<T, F> {
845 /// Create a new pool. The given closure is used to create values in
846 /// the pool when necessary.
847 pub(super) const fn new(create: F) -> Pool<T, F> {
848 Pool { stack: Mutex::new(vec![]), create }
849 }
850 }
851
852 impl<T: Send, F: Fn() -> T> Pool<T, F> {
853 /// Get a value from the pool. This may block if another thread is also
854 /// attempting to retrieve a value from the pool.
855 #[inline]
856 pub(super) fn get(&self) -> PoolGuard<'_, T, F> {
857 let mut stack = self.stack.lock();
858 let value = match stack.pop() {
859 None => Box::new((self.create)()),
860 Some(value) => value,
861 };
862 PoolGuard { pool: self, value: Some(value) }
863 }
864
865 #[inline]
866 fn put(&self, guard: PoolGuard<'_, T, F>) {
867 let mut guard = core::mem::ManuallyDrop::new(guard);
868 if let Some(value) = guard.value.take() {
869 self.put_value(value);
870 }
871 }
872
873 /// Puts a value back into the pool. Callers don't need to call this.
874 /// Once the guard that's returned by 'get' is dropped, it is put back
875 /// into the pool automatically.
876 #[inline]
877 fn put_value(&self, value: Box<T>) {
878 let mut stack = self.stack.lock();
879 stack.push(value);
880 }
881 }
882
883 impl<T: core::fmt::Debug, F> core::fmt::Debug for Pool<T, F> {
884 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
885 f.debug_struct("Pool").field("stack", &self.stack).finish()
886 }
887 }
888
889 /// A guard that is returned when a caller requests a value from the pool.
890 pub(super) struct PoolGuard<'a, T: Send, F: Fn() -> T> {
891 /// The pool that this guard is attached to.
892 pool: &'a Pool<T, F>,
893 /// This is None after the guard has been put back into the pool.
894 value: Option<Box<T>>,
895 }
896
897 impl<'a, T: Send, F: Fn() -> T> PoolGuard<'a, T, F> {
898 /// Return the underlying value.
899 #[inline]
900 pub(super) fn value(&self) -> &T {
901 self.value.as_deref().unwrap()
902 }
903
904 /// Return the underlying value as a mutable borrow.
905 #[inline]
906 pub(super) fn value_mut(&mut self) -> &mut T {
907 self.value.as_deref_mut().unwrap()
908 }
909
910 /// Consumes this guard and puts it back into the pool.
911 #[inline]
912 pub(super) fn put(this: PoolGuard<'_, T, F>) {
913 // Since this is effectively consuming the guard and putting the
914 // value back into the pool, there's no reason to run its Drop
915 // impl after doing this. I don't believe there is a correctness
916 // problem with doing so, but there's definitely a perf problem
917 // by redoing this work. So we avoid it.
918 let mut this = core::mem::ManuallyDrop::new(this);
919 this.put_imp();
920 }
921
922 /// Puts this guard back into the pool by only borrowing the guard as
923 /// mutable. This should be called at most once.
924 #[inline(always)]
925 fn put_imp(&mut self) {
926 if let Some(value) = self.value.take() {
927 self.pool.put_value(value);
928 }
929 }
930 }
931
932 impl<'a, T: Send, F: Fn() -> T> Drop for PoolGuard<'a, T, F> {
933 #[inline]
934 fn drop(&mut self) {
935 self.put_imp();
936 }
937 }
938
939 impl<'a, T: Send + core::fmt::Debug, F: Fn() -> T> core::fmt::Debug
940 for PoolGuard<'a, T, F>
941 {
942 fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
943 f.debug_struct("PoolGuard")
944 .field("pool", &self.pool)
945 .field("value", &self.value)
946 .finish()
947 }
948 }
949
950 /// A spin-lock based mutex. Yes, I have read spinlocks cosnidered
951 /// harmful[1], and if there's a reasonable alternative choice, I'll
952 /// happily take it.
953 ///
954 /// I suspect the most likely alternative here is a Treiber stack, but
955 /// implementing one correctly in a way that avoids the ABA problem looks
956 /// subtle enough that I'm not sure I want to attempt that. But otherwise,
957 /// we only need a mutex in order to implement our pool, so if there's
958 /// something simpler we can use that works for our `Pool` use case, then
959 /// that would be great.
960 ///
961 /// Note that this mutex does not do poisoning.
962 ///
963 /// [1]: https://matklad.github.io/2020/01/02/spinlocks-considered-harmful.html
964 #[derive(Debug)]
965 struct Mutex<T> {
966 locked: AtomicBool,
967 data: UnsafeCell<T>,
968 }
969
970 // SAFETY: Since a Mutex guarantees exclusive access, as long as we can
971 // send it across threads, it must also be Sync.
972 unsafe impl<T: Send> Sync for Mutex<T> {}
973
974 impl<T> Mutex<T> {
975 /// Create a new mutex for protecting access to the given value across
976 /// multiple threads simultaneously.
977 const fn new(value: T) -> Mutex<T> {
978 Mutex {
979 locked: AtomicBool::new(false),
980 data: UnsafeCell::new(value),
981 }
982 }
983
984 /// Lock this mutex and return a guard providing exclusive access to
985 /// `T`. This blocks if some other thread has already locked this
986 /// mutex.
987 #[inline]
988 fn lock(&self) -> MutexGuard<'_, T> {
989 while self
990 .locked
991 .compare_exchange(
992 false,
993 true,
994 Ordering::AcqRel,
995 Ordering::Acquire,
996 )
997 .is_err()
998 {
999 core::hint::spin_loop();
1000 }
1001 // SAFETY: The only way we're here is if we successfully set
1002 // 'locked' to true, which implies we must be the only thread here
1003 // and thus have exclusive access to 'data'.
1004 let data = unsafe { &mut *self.data.get() };
1005 MutexGuard { locked: &self.locked, data }
1006 }
1007 }
1008
1009 /// A guard that derefs to &T and &mut T. When it's dropped, the lock is
1010 /// released.
1011 #[derive(Debug)]
1012 struct MutexGuard<'a, T> {
1013 locked: &'a AtomicBool,
1014 data: &'a mut T,
1015 }
1016
1017 impl<'a, T> core::ops::Deref for MutexGuard<'a, T> {
1018 type Target = T;
1019
1020 #[inline]
1021 fn deref(&self) -> &T {
1022 self.data
1023 }
1024 }
1025
1026 impl<'a, T> core::ops::DerefMut for MutexGuard<'a, T> {
1027 #[inline]
1028 fn deref_mut(&mut self) -> &mut T {
1029 self.data
1030 }
1031 }
1032
1033 impl<'a, T> Drop for MutexGuard<'a, T> {
1034 #[inline]
1035 fn drop(&mut self) {
1036 // Drop means 'data' is no longer accessible, so we can unlock
1037 // the mutex.
1038 self.locked.store(false, Ordering::Release);
1039 }
1040 }
1041}
1042
1043#[cfg(test)]
1044mod tests {
1045 use core::panic::{RefUnwindSafe, UnwindSafe};
1046
1047 use alloc::{boxed::Box, vec, vec::Vec};
1048
1049 use super::*;
1050
1051 #[test]
1052 fn oibits() {
1053 fn assert_oitbits<T: Send + Sync + UnwindSafe + RefUnwindSafe>() {}
1054 assert_oitbits::<Pool<Vec<u32>>>();
1055 assert_oitbits::<Pool<core::cell::RefCell<Vec<u32>>>>();
1056 assert_oitbits::<
1057 Pool<
1058 Vec<u32>,
1059 Box<
1060 dyn Fn() -> Vec<u32>
1061 + Send
1062 + Sync
1063 + UnwindSafe
1064 + RefUnwindSafe,
1065 >,
1066 >,
1067 >();
1068 }
1069
1070 // Tests that Pool implements the "single owner" optimization. That is, the
1071 // thread that first accesses the pool gets its own copy, while all other
1072 // threads get distinct copies.
1073 #[cfg(feature = "std")]
1074 #[test]
1075 fn thread_owner_optimization() {
1076 use std::{cell::RefCell, sync::Arc, vec};
1077
1078 let pool: Arc<Pool<RefCell<Vec<char>>>> =
1079 Arc::new(Pool::new(|| RefCell::new(vec!['a'])));
1080 pool.get().borrow_mut().push('x');
1081
1082 let pool1 = pool.clone();
1083 let t1 = std::thread::spawn(move || {
1084 let guard = pool1.get();
1085 guard.borrow_mut().push('y');
1086 });
1087
1088 let pool2 = pool.clone();
1089 let t2 = std::thread::spawn(move || {
1090 let guard = pool2.get();
1091 guard.borrow_mut().push('z');
1092 });
1093
1094 t1.join().unwrap();
1095 t2.join().unwrap();
1096
1097 // If we didn't implement the single owner optimization, then one of
1098 // the threads above is likely to have mutated the [a, x] vec that
1099 // we stuffed in the pool before spawning the threads. But since
1100 // neither thread was first to access the pool, and because of the
1101 // optimization, we should be guaranteed that neither thread mutates
1102 // the special owned pool value.
1103 //
1104 // (Technically this is an implementation detail and not a contract of
1105 // Pool's API.)
1106 assert_eq!(vec!['a', 'x'], *pool.get().borrow());
1107 }
1108
1109 // This tests that if the "owner" of a pool asks for two values, then it
1110 // gets two distinct values and not the same one. This test failed in the
1111 // course of developing the pool, which in turn resulted in UB because it
1112 // permitted getting aliasing &mut borrows to the same place in memory.
1113 #[test]
1114 fn thread_owner_distinct() {
1115 let pool = Pool::new(|| vec!['a']);
1116
1117 {
1118 let mut g1 = pool.get();
1119 let v1 = &mut *g1;
1120 let mut g2 = pool.get();
1121 let v2 = &mut *g2;
1122 v1.push('b');
1123 v2.push('c');
1124 assert_eq!(&mut vec!['a', 'b'], v1);
1125 assert_eq!(&mut vec!['a', 'c'], v2);
1126 }
1127 // This isn't technically guaranteed, but we
1128 // expect to now get the "owned" value (the first
1129 // call to 'get()' above) now that it's back in
1130 // the pool.
1131 assert_eq!(&mut vec!['a', 'b'], &mut *pool.get());
1132 }
1133
1134 // This tests that we can share a guard with another thread, mutate the
1135 // underlying value and everything works. This failed in the course of
1136 // developing a pool since the pool permitted 'get()' to return the same
1137 // value to the owner thread, even before the previous value was put back
1138 // into the pool. This in turn resulted in this test producing a data race.
1139 #[cfg(feature = "std")]
1140 #[test]
1141 fn thread_owner_sync() {
1142 let pool = Pool::new(|| vec!['a']);
1143 {
1144 let mut g1 = pool.get();
1145 let mut g2 = pool.get();
1146 std::thread::scope(|s| {
1147 s.spawn(|| {
1148 g1.push('b');
1149 });
1150 s.spawn(|| {
1151 g2.push('c');
1152 });
1153 });
1154
1155 let v1 = &mut *g1;
1156 let v2 = &mut *g2;
1157 assert_eq!(&mut vec!['a', 'b'], v1);
1158 assert_eq!(&mut vec!['a', 'c'], v2);
1159 }
1160
1161 // This isn't technically guaranteed, but we
1162 // expect to now get the "owned" value (the first
1163 // call to 'get()' above) now that it's back in
1164 // the pool.
1165 assert_eq!(&mut vec!['a', 'b'], &mut *pool.get());
1166 }
1167
1168 // This tests that if we move a PoolGuard that is owned by the current
1169 // thread to another thread and drop it, then the thread owner doesn't
1170 // change. During development of the pool, this test failed because the
1171 // PoolGuard assumed it was dropped in the same thread from which it was
1172 // created, and thus used the current thread's ID as the owner, which could
1173 // be different than the actual owner of the pool.
1174 #[cfg(feature = "std")]
1175 #[test]
1176 fn thread_owner_send_drop() {
1177 let pool = Pool::new(|| vec!['a']);
1178 // Establishes this thread as the owner.
1179 {
1180 pool.get().push('b');
1181 }
1182 std::thread::scope(|s| {
1183 // Sanity check that we get the same value back.
1184 // (Not technically guaranteed.)
1185 let mut g = pool.get();
1186 assert_eq!(&vec!['a', 'b'], &*g);
1187 // Now push it to another thread and drop it.
1188 s.spawn(move || {
1189 g.push('c');
1190 })
1191 .join()
1192 .unwrap();
1193 });
1194 // Now check that we're still the owner. This is not technically
1195 // guaranteed by the API, but is true in practice given the thread
1196 // owner optimization.
1197 assert_eq!(&vec!['a', 'b', 'c'], &*pool.get());
1198 }
1199}
1200