wgpu_core/
identity.rs

1use alloc::vec::Vec;
2use core::{fmt::Debug, marker::PhantomData};
3
4use crate::{
5    id::{Id, Marker},
6    lock::{rank, Mutex},
7    Epoch, Index,
8};
9
10#[derive(Copy, Clone, Debug, PartialEq)]
11enum IdSource {
12    External,
13    Allocated,
14    None,
15}
16
17/// A simple structure to allocate [`Id`] identifiers.
18///
19/// Calling [`alloc`] returns a fresh, never-before-seen id. Calling [`release`]
20/// marks an id as dead; it will never be returned again by `alloc`.
21///
22/// `IdentityValues` returns `Id`s whose index values are suitable for use as
23/// indices into a `Vec<T>` that holds those ids' referents:
24///
25/// - Every live id has a distinct index value. Every live id's index
26///   selects a distinct element in the vector.
27///
28/// - `IdentityValues` prefers low index numbers. If you size your vector to
29///   accommodate the indices produced here, the vector's length will reflect
30///   the highwater mark of actual occupancy.
31///
32/// - `IdentityValues` reuses the index values of freed ids before returning
33///   ids with new index values. Freed vector entries get reused.
34///
35/// - The non-reuse property is achieved by storing an `epoch` alongside the
36///   index in an `Id`. Index values are reused, but only with a different
37///   epoch.
38///
39/// `IdentityValues` can also be used to track the count of IDs allocated by
40/// some external allocator. Combining internal and external allocation is not
41/// allowed; calling both `alloc` and `mark_as_used` on the same
42/// `IdentityValues` will result in a panic. The external mode is used when
43/// [playing back a trace of wgpu operations][player].
44///
45/// [`Id`]: crate::id::Id
46/// [`alloc`]: IdentityValues::alloc
47/// [`release`]: IdentityValues::release
48/// [player]: https://github.com/gfx-rs/wgpu/tree/trunk/player/
49#[derive(Debug)]
50pub(super) struct IdentityValues {
51    free: Vec<(Index, Epoch)>,
52    next_index: Index,
53    count: usize,
54    // Sanity check: The allocation logic works under the assumption that we don't
55    // do a mix of allocating ids from here and providing ids manually for the same
56    // storage container.
57    id_source: IdSource,
58}
59
60impl IdentityValues {
61    /// Allocate a fresh, never-before-seen ID.
62    ///
63    /// # Panics
64    ///
65    /// If `mark_as_used` has previously been called on this `IdentityValues`.
66    pub fn alloc<T: Marker>(&mut self) -> Id<T> {
67        assert!(
68            self.id_source != IdSource::External,
69            "Mix of internally allocated and externally provided IDs"
70        );
71        self.id_source = IdSource::Allocated;
72
73        self.count += 1;
74        match self.free.pop() {
75            Some((index, epoch)) => Id::zip(index, epoch + 1),
76            None => {
77                let index = self.next_index;
78                self.next_index += 1;
79                let epoch = 1;
80                Id::zip(index, epoch)
81            }
82        }
83    }
84
85    /// Increment the count of used IDs.
86    ///
87    /// # Panics
88    ///
89    /// If `alloc` has previously been called on this `IdentityValues`.
90    pub fn mark_as_used<T: Marker>(&mut self, id: Id<T>) -> Id<T> {
91        assert!(
92            self.id_source != IdSource::Allocated,
93            "Mix of internally allocated and externally provided IDs"
94        );
95        self.id_source = IdSource::External;
96
97        self.count += 1;
98        id
99    }
100
101    /// Free `id` and/or decrement the count of used IDs.
102    ///
103    /// Freed IDs will never be returned from `alloc` again.
104    pub fn release<T: Marker>(&mut self, id: Id<T>) {
105        if let IdSource::Allocated = self.id_source {
106            let (index, epoch) = id.unzip();
107            self.free.push((index, epoch));
108        }
109        self.count -= 1;
110    }
111
112    pub fn count(&self) -> usize {
113        self.count
114    }
115}
116
117#[derive(Debug)]
118pub struct IdentityManager<T: Marker> {
119    pub(super) values: Mutex<IdentityValues>,
120    _phantom: PhantomData<T>,
121}
122
123impl<T: Marker> IdentityManager<T> {
124    pub fn process(&self) -> Id<T> {
125        self.values.lock().alloc()
126    }
127    pub fn mark_as_used(&self, id: Id<T>) -> Id<T> {
128        self.values.lock().mark_as_used(id)
129    }
130    pub fn free(&self, id: Id<T>) {
131        self.values.lock().release(id)
132    }
133}
134
135impl<T: Marker> IdentityManager<T> {
136    pub fn new() -> Self {
137        Self {
138            values: Mutex::new(
139                rank::IDENTITY_MANAGER_VALUES,
140                IdentityValues {
141                    free: Vec::new(),
142                    next_index: 0,
143                    count: 0,
144                    id_source: IdSource::None,
145                },
146            ),
147            _phantom: PhantomData,
148        }
149    }
150}
151
152#[test]
153fn test_epoch_end_of_life() {
154    use crate::id;
155    let man = IdentityManager::<id::markers::Buffer>::new();
156    let id1 = man.process();
157    assert_eq!(id1.unzip(), (0, 1));
158    man.free(id1);
159    let id2 = man.process();
160    // confirm that the epoch 1 is no longer re-used
161    assert_eq!(id2.unzip(), (0, 2));
162}
wgpu_core/identity.rs

wgpu_core/
identity.rs
