gfx/wr/webrender/src/intern.rs

   1 /* This Source Code Form is subject to the terms of the Mozilla Public
   2  * License, v. 2.0. If a copy of the MPL was not distributed with this
   3  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   4
   5 //! The interning module provides a generic data structure
   6 //! interning container. It is similar in concept to a
   7 //! traditional string interning container, but it is
   8 //! specialized to the WR thread model.
   9 //!
  10 //! There is an Interner structure, that lives in the
  11 //! scene builder thread, and a DataStore structure
  12 //! that lives in the frame builder thread.
  13 //!
  14 //! Hashing, interning and handle creation is done by
  15 //! the interner structure during scene building.
  16 //!
  17 //! Delta changes for the interner are pushed during
  18 //! a transaction to the frame builder. The frame builder
  19 //! is then able to access the content of the interned
  20 //! handles quickly, via array indexing.
  21 //!
  22 //! Epoch tracking ensures that the garbage collection
  23 //! step which the interner uses to remove items is
  24 //! only invoked on items that the frame builder thread
  25 //! is no longer referencing.
  26 //!
  27 //! Items in the data store are stored in a traditional
  28 //! free-list structure, for content access and memory
  29 //! usage efficiency.
  30 //!
  31 //! The epoch is incremented each time a scene is
  32 //! built. The most recently used scene epoch is
  33 //! stored inside each handle. This is then used for
  34 //! cache invalidation.
  35
  36 use crate::internal_types::FastHashMap;
  37 use malloc_size_of::MallocSizeOf;
  38 use std::fmt::Debug;
  39 use std::hash::Hash;
  40 use std::marker::PhantomData;
  41 use std::{ops, u64};
  42 use crate::util::VecHelper;
  43 use crate::profiler::TransactionProfile;
  44
  45 #[cfg_attr(feature = "capture", derive(Serialize))]
  46 #[cfg_attr(feature = "replay", derive(Deserialize))]
  47 #[derive(Debug, Copy, Clone, Hash, MallocSizeOf, PartialEq, Eq)]
  48 struct Epoch(u32);
  49
  50 /// A list of updates to be applied to the data store,
  51 /// provided by the interning structure.
  52 #[cfg_attr(feature = "capture", derive(Serialize))]
  53 #[cfg_attr(feature = "replay", derive(Deserialize))]
  54 #[derive(MallocSizeOf)]
  55 pub struct UpdateList<S> {
  56     /// Items to insert.
  57     pub insertions: Vec<Insertion<S>>,
  58
  59     /// Items to remove.
  60     pub removals: Vec<Removal>,
  61 }
  62
  63 #[cfg_attr(feature = "capture", derive(Serialize))]
  64 #[cfg_attr(feature = "replay", derive(Deserialize))]
  65 #[derive(MallocSizeOf)]
  66 pub struct Insertion<S> {
  67     pub index: usize,
  68     pub uid: ItemUid,
  69     pub value: S,
  70 }
  71
  72 #[cfg_attr(feature = "capture", derive(Serialize))]
  73 #[cfg_attr(feature = "replay", derive(Deserialize))]
  74 #[derive(MallocSizeOf)]
  75 pub struct Removal {
  76     pub index: usize,
  77     pub uid: ItemUid,
  78 }
  79
  80 impl<S> UpdateList<S> {
  81     fn new() -> UpdateList<S> {
  82         UpdateList {
  83             insertions: Vec::new(),
  84             removals: Vec::new(),
  85         }
  86     }
  87
  88     fn take_and_preallocate(&mut self) -> UpdateList<S> {
  89         UpdateList {
  90             insertions: self.insertions.take_and_preallocate(),
  91             removals: self.removals.take_and_preallocate(),
  92         }
  93     }
  94 }
  95
  96 /// A globally, unique identifier
  97 #[cfg_attr(feature = "capture", derive(Serialize))]
  98 #[cfg_attr(feature = "replay", derive(Deserialize))]
  99 #[derive(Debug, Copy, Clone, Eq, Hash, MallocSizeOf, PartialEq)]
 100 pub struct ItemUid {
 101     uid: u64,
 102 }
 103
 104 impl ItemUid {
 105     // Intended for debug usage only
 106     pub fn get_uid(&self) -> u64 {
 107         self.uid
 108     }
 109 }
 110
 111 #[cfg_attr(feature = "capture", derive(Serialize))]
 112 #[cfg_attr(feature = "replay", derive(Deserialize))]
 113 #[derive(Debug, Hash, MallocSizeOf, PartialEq, Eq)]
 114 pub struct Handle<I> {
 115     index: u32,
 116     epoch: Epoch,
 117     _marker: PhantomData<I>,
 118 }
 119
 120 impl<I> Clone for Handle<I> {
 121     fn clone(&self) -> Self {
 122         Handle {
 123             index: self.index,
 124             epoch: self.epoch,
 125             _marker: self._marker,
 126         }
 127     }
 128 }
 129
 130 impl<I> Copy for Handle<I> {}
 131
 132 impl<I> Handle<I> {
 133     pub fn uid(&self) -> ItemUid {
 134         ItemUid {
 135             // The index in the freelist + the epoch it was interned generates a stable
 136             // unique id for an interned element.
 137             uid: ((self.index as u64) << 32) | self.epoch.0 as u64
 138         }
 139     }
 140 }
 141
 142 pub trait InternDebug {
 143     fn on_interned(&self, _uid: ItemUid) {}
 144 }
 145
 146 /// The data store lives in the frame builder thread. It
 147 /// contains a free-list of items for fast access.
 148 #[cfg_attr(feature = "capture", derive(Serialize))]
 149 #[cfg_attr(feature = "replay", derive(Deserialize))]
 150 #[derive(MallocSizeOf)]
 151 pub struct DataStore<I: Internable> {
 152     items: Vec<Option<I::StoreData>>,
 153 }
 154
 155 impl<I: Internable> Default for DataStore<I> {
 156     fn default() -> Self {
 157         DataStore {
 158             items: Vec::new(),
 159         }
 160     }
 161 }
 162
 163 impl<I: Internable> DataStore<I> {
 164     /// Apply any updates from the scene builder thread to
 165     /// this data store.
 166     pub fn apply_updates(
 167         &mut self,
 168         update_list: UpdateList<I::Key>,
 169         profile: &mut TransactionProfile,
 170     ) {
 171         for insertion in update_list.insertions {
 172             self.items
 173                 .entry(insertion.index)
 174                 .set(Some(insertion.value.into()));
 175         }
 176
 177         for removal in update_list.removals {
 178             self.items[removal.index] = None;
 179         }
 180
 181         profile.set(I::PROFILE_COUNTER, self.items.len());
 182     }
 183 }
 184
 185 /// Retrieve an item from the store via handle
 186 impl<I: Internable> ops::Index<Handle<I>> for DataStore<I> {
 187     type Output = I::StoreData;
 188     fn index(&self, handle: Handle<I>) -> &I::StoreData {
 189         self.items[handle.index as usize].as_ref().expect("Bad datastore lookup")
 190     }
 191 }
 192
 193 /// Retrieve a mutable item from the store via handle
 194 /// Retrieve an item from the store via handle
 195 impl<I: Internable> ops::IndexMut<Handle<I>> for DataStore<I> {
 196     fn index_mut(&mut self, handle: Handle<I>) -> &mut I::StoreData {
 197         self.items[handle.index as usize].as_mut().expect("Bad datastore lookup")
 198     }
 199 }
 200
 201 #[cfg_attr(feature = "capture", derive(Serialize))]
 202 #[cfg_attr(feature = "replay", derive(Deserialize))]
 203 #[derive(MallocSizeOf)]
 204 struct ItemDetails<I> {
 205     /// Frame that this element was first interned
 206     interned_epoch: Epoch,
 207     /// Last frame this element was referenced (used to GC intern items)
 208     last_used_epoch: Epoch,
 209     /// Index into the freelist this item is located
 210     index: usize,
 211     /// Type marker for create_handle method
 212     _marker: PhantomData<I>,
 213 }
 214
 215 impl<I> ItemDetails<I> {
 216     /// Construct a stable handle value from the item details
 217     fn create_handle(&self) -> Handle<I> {
 218         Handle {
 219             index: self.index as u32,
 220             epoch: self.interned_epoch,
 221             _marker: PhantomData,
 222         }
 223     }
 224 }
 225
 226 /// The main interning data structure. This lives in the
 227 /// scene builder thread, and handles hashing and interning
 228 /// unique data structures. It also manages a free-list for
 229 /// the items in the data store, which is synchronized via
 230 /// an update list of additions / removals.
 231 #[cfg_attr(feature = "capture", derive(Serialize))]
 232 #[cfg_attr(feature = "replay", derive(Deserialize))]
 233 #[derive(MallocSizeOf)]
 234 pub struct Interner<I: Internable> {
 235     /// Uniquely map an interning key to a handle
 236     map: FastHashMap<I::Key, ItemDetails<I>>,
 237     /// List of free slots in the data store for re-use.
 238     free_list: Vec<usize>,
 239     /// Pending list of updates that need to be applied.
 240     update_list: UpdateList<I::Key>,
 241     /// The current epoch for the interner.
 242     current_epoch: Epoch,
 243     /// The information associated with each interned
 244     /// item that can be accessed by the interner.
 245     local_data: Vec<I::InternData>,
 246 }
 247
 248 impl<I: Internable> Default for Interner<I> {
 249     fn default() -> Self {
 250         Interner {
 251             map: FastHashMap::default(),
 252             free_list: Vec::new(),
 253             update_list: UpdateList::new(),
 254             current_epoch: Epoch(1),
 255             local_data: Vec::new(),
 256         }
 257     }
 258 }
 259
 260 impl<I: Internable> Interner<I> {
 261     /// Intern a data structure, and return a handle to
 262     /// that data. The handle can then be stored in the
 263     /// frame builder, and safely accessed via the data
 264     /// store that lives in the frame builder thread.
 265     /// The provided closure is invoked to build the
 266     /// local data about an interned structure if the
 267     /// key isn't already interned.
 268     pub fn intern<F>(
 269         &mut self,
 270         data: &I::Key,
 271         fun: F,
 272     ) -> Handle<I> where F: FnOnce() -> I::InternData {
 273         // Use get_mut rather than entry here to avoid
 274         // cloning the (sometimes large) key in the common
 275         // case, where the data already exists in the interner.
 276         if let Some(details) = self.map.get_mut(data) {
 277             // Update the last referenced frame for this element
 278             details.last_used_epoch = self.current_epoch;
 279             // Return a stable handle value for dependency checking
 280             return details.create_handle();
 281         }
 282
 283         // We need to intern a new data item. First, find out
 284         // if there is a spare slot in the free-list that we
 285         // can use. Otherwise, append to the end of the list.
 286         let index = match self.free_list.pop() {
 287             Some(index) => index,
 288             None => self.local_data.len(),
 289         };
 290
 291         // Generate a handle for access via the data store.
 292         let handle = Handle {
 293             index: index as u32,
 294             epoch: self.current_epoch,
 295             _marker: PhantomData,
 296         };
 297
 298         let uid = handle.uid();
 299
 300         // Add a pending update to insert the new data.
 301         self.update_list.insertions.push(Insertion {
 302             index,
 303             uid,
 304             value: data.clone(),
 305         });
 306
 307         #[cfg(debug_assertions)]
 308         data.on_interned(uid);
 309
 310         // Store this handle so the next time it is
 311         // interned, it gets re-used.
 312         self.map.insert(data.clone(), ItemDetails {
 313             interned_epoch: self.current_epoch,
 314             last_used_epoch: self.current_epoch,
 315             index,
 316             _marker: PhantomData,
 317         });
 318
 319         // Create the local data for this item that is
 320         // being interned.
 321         self.local_data.entry(index).set(fun());
 322
 323         handle
 324     }
 325
 326     /// Retrieve the pending list of updates for an interner
 327     /// that need to be applied to the data store. Also run
 328     /// a GC step that removes old entries.
 329     pub fn end_frame_and_get_pending_updates(&mut self) -> UpdateList<I::Key> {
 330         let mut update_list = self.update_list.take_and_preallocate();
 331
 332         let free_list = &mut self.free_list;
 333         let current_epoch = self.current_epoch.0;
 334
 335         // First, run a GC step. Walk through the handles, and
 336         // if we find any that haven't been used for some time,
 337         // remove them. If this ever shows up in profiles, we
 338         // can make the GC step partial (scan only part of the
 339         // map each frame). It also might make sense in the
 340         // future to adjust how long items remain in the cache
 341         // based on the current size of the list.
 342         self.map.retain(|_, details| {
 343             if details.last_used_epoch.0 + 10 < current_epoch {
 344                 // To expire an item:
 345                 //  - Add index to the free-list for re-use.
 346                 //  - Add an update to the data store to invalidate this slot.
 347                 //  - Remove from the hash map.
 348                 free_list.push(details.index);
 349                 update_list.removals.push(Removal {
 350                     index: details.index,
 351                     uid: details.create_handle().uid(),
 352                 });
 353                 return false;
 354             }
 355
 356             true
 357         });
 358
 359         // Begin the next epoch
 360         self.current_epoch = Epoch(self.current_epoch.0 + 1);
 361
 362         update_list
 363     }
 364 }
 365
 366 /// Retrieve the local data for an item from the interner via handle
 367 impl<I: Internable> ops::Index<Handle<I>> for Interner<I> {
 368     type Output = I::InternData;
 369     fn index(&self, handle: Handle<I>) -> &I::InternData {
 370         &self.local_data[handle.index as usize]
 371     }
 372 }
 373
 374 /// Meta-macro to enumerate the various interner identifiers and types.
 375 ///
 376 /// IMPORTANT: Keep this synchronized with the list in mozilla-central located at
 377 /// gfx/webrender_bindings/webrender_ffi.h
 378 ///
 379 /// Note that this could be a lot less verbose if concat_idents! were stable. :-(
 380 #[macro_export]
 381 macro_rules! enumerate_interners {
 382     ($macro_name: ident) => {
 383         $macro_name! {
 384             clip: ClipIntern,
 385             prim: PrimitiveKeyKind,
 386             normal_border: NormalBorderPrim,
 387             image_border: ImageBorder,
 388             image: Image,
 389             yuv_image: YuvImage,
 390             line_decoration: LineDecoration,
 391             linear_grad: LinearGradient,
 392             radial_grad: RadialGradient,
 393             conic_grad: ConicGradient,
 394             picture: Picture,
 395             text_run: TextRun,
 396             filter_data: FilterDataIntern,
 397             backdrop: Backdrop,
 398             polygon: PolygonIntern,
 399         }
 400     }
 401 }
 402
 403 macro_rules! declare_interning_memory_report {
 404     ( $( $name:ident: $ty:ident, )+ ) => {
 405         ///
 406         #[repr(C)]
 407         #[derive(AddAssign, Clone, Debug, Default)]
 408         pub struct InternerSubReport {
 409             $(
 410                 ///
 411                 pub $name: usize,
 412             )+
 413         }
 414     }
 415 }
 416
 417 enumerate_interners!(declare_interning_memory_report);
 418
 419 /// Memory report for interning-related data structures.
 420 /// cbindgen:derive-eq=false
 421 /// cbindgen:derive-ostream=false
 422 #[repr(C)]
 423 #[derive(Clone, Debug, Default)]
 424 pub struct InterningMemoryReport {
 425     ///
 426     pub interners: InternerSubReport,
 427     ///
 428     pub data_stores: InternerSubReport,
 429 }
 430
 431 impl ::std::ops::AddAssign for InterningMemoryReport {
 432     fn add_assign(&mut self, other: InterningMemoryReport) {
 433         self.interners += other.interners;
 434         self.data_stores += other.data_stores;
 435     }
 436 }
 437
 438 // The trick to make trait bounds configurable by features.
 439 mod dummy {
 440     #[cfg(not(feature = "capture"))]
 441     pub trait Serialize {}
 442     #[cfg(not(feature = "capture"))]
 443     impl<T> Serialize for T {}
 444     #[cfg(not(feature = "replay"))]
 445     pub trait Deserialize<'a> {}
 446     #[cfg(not(feature = "replay"))]
 447     impl<'a, T> Deserialize<'a> for T {}
 448 }
 449 #[cfg(feature = "capture")]
 450 use serde::Serialize as InternSerialize;
 451 #[cfg(not(feature = "capture"))]
 452 use self::dummy::Serialize as InternSerialize;
 453 #[cfg(feature = "replay")]
 454 use serde::Deserialize as InternDeserialize;
 455 #[cfg(not(feature = "replay"))]
 456 use self::dummy::Deserialize as InternDeserialize;
 457
 458 /// Implement `Internable` for a type that wants to participate in interning.
 459 pub trait Internable: MallocSizeOf {
 460     type Key: Eq + Hash + Clone + Debug + MallocSizeOf + InternDebug + InternSerialize + for<'a> InternDeserialize<'a>;
 461     type StoreData: From<Self::Key> + MallocSizeOf + InternSerialize + for<'a> InternDeserialize<'a>;
 462     type InternData: MallocSizeOf + InternSerialize + for<'a> InternDeserialize<'a>;
 463
 464     // Profile counter indices, see the list in profiler.rs
 465     const PROFILE_COUNTER: usize;
 466 }