Source code
Revision control
Copy as Markdown
Other Tools
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
//! Follower storage for items interned by the content process display list
//! builder. See `doc/dl-builder-interning.md` for the whole design.
//!
//! Content mints slot numbers per display list builder, starting at zero, so
//! two pipelines collide in a single store. The scene builder hands each
//! pipeline a dense `DlNamespace` the first time it sees one of that
//! pipeline's display lists, and a `DlHandle` is that namespace plus the
//! content slot. Because the handle names its namespace, one batch can
//! reference items from several pipelines.
//!
//! A `DlStore` is a pure follower: content allocates every slot and the store
//! only replays the deltas it is handed. Nothing here ever picks a slot, and
//! the inner level deliberately has no free list - if a store allocated for
//! itself the two sides would diverge with nothing able to notice.
// Handles are only minted once a primitive type moves its interning into the
// display list builder, so until then the store's read side has no caller.
#![allow(dead_code)]
use crate::intern::ItemUid;
use crate::internal_types::{FastHashMap, FastHashSet};
use api::interning::{BuildId, BuilderId};
use api::{FontRenderMode, IdNamespace, PipelineId};
use glyph_rasterizer::SharedFontResources;
use std::marker::PhantomData;
use std::{fmt, ops};
/// Every follower store the render backend holds, one line each: the field
/// name (the same one `enumerate_dl_interned_types!` in `webrender_api` uses
/// for the delta), the content key type, the value the store holds for it,
/// the profiler gauge set from the store's size, and the field of the
/// interning memory report it is accounted under.
///
/// Adding a type here and to the api-side list is all the plumbing a
/// primitive needs on the receiving side; see `doc/dl-builder-interning.md`.
#[macro_export]
macro_rules! enumerate_dl_stores {
($macro_name: ident) => {
$macro_name! {
}
}
}
/// The follower stores the scene builder itself reads, in the same shape as
/// `enumerate_dl_stores!` minus the gauge. Most types need none: scene
/// building only consumes a handle. Clips will, since clip chain building,
/// slice partitioning and hit testing read the clip's key.
#[macro_export]
macro_rules! enumerate_scene_dl_stores {
($macro_name: ident) => {
$macro_name! {
}
}
}
/// What a store needs to turn a content key into the value it holds.
pub struct DlResolveContext<'a> {
/// The id namespace the display list carrying the delta was submitted
/// with, for validating any resource key the interned item names.
pub id_namespace: IdNamespace,
pub fonts: &'a SharedFontResources,
pub default_font_render_mode: FontRenderMode,
}
/// A store value that can be built from its content key. Done where the delta
/// is applied, once per interned entry rather than once per scene build.
pub trait DlResolve<K>: Sized {
fn resolve(key: &K, ctx: &DlResolveContext) -> Self;
}
/// Dense index identifying one content display list builder's slot space.
/// Recycled when its pipeline goes away, so it stays small enough to index an
/// array with - unlike `IdNamespace`, which never recycles.
#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, MallocSizeOf)]
pub struct DlNamespace(pub u32);
/// A reference to one item interned by content: the slot content assigned it,
/// qualified by the namespace its builder was given.
#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
#[cfg_attr(any(feature = "capture", feature = "replay"), serde(bound = ""))]
pub struct DlHandle<K> {
pub namespace: DlNamespace,
pub slot: u32,
/// Which occupant of `namespace` this handle was minted against. Namespaces
/// are recycled, so a handle that outlives a retained scene into one built
/// after the recycle would otherwise read another pipeline's data with no
/// sign of anything wrong (invariant 4).
///
/// Debug only: it exists to catch that, and carrying it always would widen
/// the handle past two words for a case that should never happen.
#[cfg(debug_assertions)]
generation: u32,
_marker: PhantomData<K>,
}
// Hand-written rather than derived: the derives would demand the same trait of
// `K`, which is only ever a marker here.
impl<K> Copy for DlHandle<K> {}
impl<K> Clone for DlHandle<K> {
fn clone(&self) -> Self {
*self
}
}
impl<K> PartialEq for DlHandle<K> {
fn eq(&self, other: &Self) -> bool {
self.namespace == other.namespace && self.slot == other.slot
}
}
impl<K> Eq for DlHandle<K> {}
impl<K> std::hash::Hash for DlHandle<K> {
fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
self.namespace.hash(state);
self.slot.hash(state);
}
}
impl<K> fmt::Debug for DlHandle<K> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "DlHandle({}, {})", self.namespace.0, self.slot)
}
}
impl<K> malloc_size_of::MallocSizeOf for DlHandle<K> {
fn size_of(&self, _ops: &mut malloc_size_of::MallocSizeOfOps) -> usize {
0
}
}
impl<K> DlHandle<K> {
/// Names no entry; a lookup through it panics. Used where a handle field
/// has to exist but is never read, such as the clip tree's root sentinel.
pub const INVALID: Self = DlHandle {
namespace: DlNamespace(u32::MAX),
slot: u32::MAX,
#[cfg(debug_assertions)]
generation: 0,
_marker: PhantomData,
};
/// `generation` is what `DlBuilderMap::expect` returned alongside the
/// namespace. Taken even in release, where it is discarded, so that callers
/// do not have to know which build they are in.
pub fn new(namespace: DlNamespace, generation: u32, slot: u32) -> Self {
let _ = generation;
DlHandle {
namespace,
slot,
#[cfg(debug_assertions)]
generation,
_marker: PhantomData,
}
}
/// A handle into another store for an entry minted by the same builder:
/// same namespace (and generation), a slot of the other type. This is how
/// a content-side handle held *inside* an interned value - a clip's polygon
/// - is qualified, since it shares its owner's builder.
pub fn sibling<K2>(&self, slot: u32) -> DlHandle<K2> {
DlHandle {
namespace: self.namespace,
slot,
#[cfg(debug_assertions)]
generation: self.generation,
_marker: PhantomData,
}
}
}
/// What the scene builder tracks for each content display list builder.
struct BuilderState {
namespace: DlNamespace,
/// The builder whose stream we are following, once one has claimed this
/// pipeline. `None` until the first delta arrives.
builder: Option<BuilderId>,
/// Build number the next delta from that builder must carry.
expected_build: BuildId,
/// A builder that used to own this pipeline and was displaced by the
/// current one. Kept only to recognise it if it comes back, which is the
/// one shape of builder change that cannot be handled - see
/// `DeltaAction::Reset`.
displaced: Option<BuilderId>,
}
/// What the arrival of a display list's delta means for the stores.
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub enum DeltaAction {
/// The next delta in the stream we are following. Apply it.
Apply,
/// A different builder has taken over this pipeline and its slot numbering
/// starts again at zero, so the previous builder's entries have to go before
/// this delta lands: close the namespace, reopen it, then apply.
///
/// This is what a new content process, or any client that builds each
/// display list with a fresh builder, looks like from here. It is only sound
/// because the displaced builder never returns: its surviving entries are
/// dropped, and it would not re-mint them. Two builders alternating on one
/// pipeline is therefore still an error, and `check_delta` reports it as one.
Reset,
/// Not from the builder we follow, and interns nothing, so it can neither
/// disturb slot state nor be disturbed by it. Leave the stream alone.
Ignore,
}
/// Maps each pipeline to the state of the builder producing its display lists:
/// the namespace its slots live in, and where its delta stream has got to.
/// Lives on the scene builder; content knows nothing about either, so there is
/// no allocation round trip.
#[derive(Default)]
pub struct DlBuilderMap {
by_pipeline: FastHashMap<PipelineId, BuilderState>,
free: Vec<DlNamespace>,
/// Pipelines removed but not yet released; see `remove_pipeline`.
pending_removals: FastHashSet<PipelineId>,
next: u32,
/// How many times each namespace index has been handed to a builder. Stays
/// in step with the store's count, which advances on `open`, because every
/// bump here emits exactly one `Open`. See `DlHandle::generation`.
generations: Vec<u32>,
}
impl DlBuilderMap {
pub fn get(&self, pipeline_id: PipelineId) -> Option<DlNamespace> {
self.by_pipeline.get(&pipeline_id).map(|state| state.namespace)
}
/// The namespace of a pipeline that is being built into a scene, and its
/// generation, so it must have one: a namespace is allocated on the
/// pipeline's first display list and released at the same point the scene
/// stops referencing it.
pub fn expect(&self, pipeline_id: PipelineId) -> (DlNamespace, u32) {
let namespace = self
.get(pipeline_id)
.unwrap_or_else(|| panic!("no namespace for {:?}", pipeline_id));
(namespace, self.generations[namespace.0 as usize])
}
fn bump_generation(&mut self, namespace: DlNamespace) {
let index = namespace.0 as usize;
if index >= self.generations.len() {
self.generations.resize(index + 1, 0);
}
self.generations[index] += 1;
}
/// The namespace for this pipeline, allocating one if this is the first
/// display list seen for it. A `true` second element means it was just
/// allocated and the caller must open it on every store before applying
/// anything to it.
pub fn get_or_alloc(&mut self, pipeline_id: PipelineId) -> (DlNamespace, bool) {
// Live again, so any release owed for an earlier removal is off.
self.pending_removals.remove(&pipeline_id);
if let Some(state) = self.by_pipeline.get(&pipeline_id) {
return (state.namespace, false);
}
let namespace = self.free.pop().unwrap_or_else(|| {
let namespace = DlNamespace(self.next);
self.next += 1;
namespace
});
self.by_pipeline.insert(
pipeline_id,
BuilderState {
namespace,
builder: None,
expected_build: BuildId(0),
displaced: None,
},
);
self.bump_generation(namespace);
(namespace, true)
}
/// Work out what this display list's delta means for the stores, and record
/// that it arrived. A couple of comparisons per display list, which is what
/// stands between us and the failure modes in
/// `doc/dl-builder-interning.md`: a lost add panics far from the cause, a
/// lost remove leaks silently, and a duplicate add corrupts a live slot.
///
/// Builds are numbered consecutively even when they intern nothing, so a gap
/// in the stream we are following means a delta was dropped, repeated or
/// reordered. That is always a bug, so it panics.
///
/// A delta from a *different* builder means something else: slot numbering
/// is per builder and restarts at zero, so the two cannot share a slot
/// space. See `DeltaAction` for the three ways that resolves.
pub fn check_delta(
&mut self,
pipeline_id: PipelineId,
builder: BuilderId,
build: BuildId,
is_empty: bool,
) -> DeltaAction {
let state = self
.by_pipeline
.get_mut(&pipeline_id)
.expect("delta for a pipeline with no namespace");
// Set when the arm below decides this is a takeover; the generation bump
// needs `self` again, which `state` is still borrowing.
let mut reset_namespace = None;
let action = match state.builder {
Some(known) if known != builder => {
// An empty delta claims nothing, so leave the stream with the
// builder that owns it: this is Gecko clearing a pipeline
// through a throwaway builder.
if is_empty {
return DeltaAction::Ignore;
}
assert_ne!(
state.displaced,
Some(builder),
"two display list builders alternating on {:?}",
pipeline_id,
);
debug!(
"dl interning: builder change on {:?}, dropping its interned items",
pipeline_id,
);
state.displaced = Some(known);
state.builder = Some(builder);
reset_namespace = Some(state.namespace);
DeltaAction::Reset
}
Some(_) => {
assert_eq!(
build, state.expected_build,
"display list interning delta out of sequence for {:?}",
pipeline_id,
);
DeltaAction::Apply
}
None => {
// Nothing to be contiguous with yet, so adopt this builder and
// take its number as the start of the stream rather than
// demanding zero - its earlier builds may have interned
// nothing. An empty delta claims nothing, since it might be a
// throwaway builder's.
if is_empty {
return DeltaAction::Ignore;
}
state.builder = Some(builder);
DeltaAction::Apply
}
};
state.expected_build = BuildId(build.0 + 1);
if let Some(namespace) = reset_namespace {
self.bump_generation(namespace);
}
action
}
/// Note that a pipeline has been removed. Its namespace is *not* released
/// yet: removing a pipeline does not rebuild the scene, so the render
/// backend goes on drawing one whose primitives still reference it. Calling
/// `take_removals` at the next scene build is what releases it.
pub fn remove_pipeline(&mut self, pipeline_id: PipelineId) {
self.pending_removals.insert(pipeline_id);
}
/// Release everything `remove_pipeline` has noted since the last call, and
/// return the namespaces to close.
///
/// The caller must have just built a scene that references none of them.
/// Holding the ids until then is also what keeps invariant 4: a namespace
/// cannot be handed to another pipeline while a live scene still points
/// into it.
pub fn take_removals(&mut self) -> Vec<DlNamespace> {
let mut namespaces = Vec::new();
for pipeline_id in self.pending_removals.drain() {
if let Some(state) = self.by_pipeline.remove(&pipeline_id) {
self.free.push(state.namespace);
namespaces.push(state.namespace);
}
}
namespaces
}
}
/// One step of the resolved delta a scene builder hands to a store.
///
/// A namespace's lifetime rides the same op list as its contents so a store
/// cannot see the two out of order: `Open` before anything is put in a freshly
/// allocated namespace, `Close` at the point the scene stops referencing the
/// pipeline. `T` is the store's own view of an interned item, derived from the
/// content key by whoever built the list.
pub enum DlOp<T> {
Open(DlNamespace),
Insert {
namespace: DlNamespace,
slot: u32,
value: T,
},
Remove {
namespace: DlNamespace,
slot: u32,
},
Close(DlNamespace),
}
/// Turn one type's delta into store ops. Adds before removes, which cannot
/// conflict within a delta: a slot this build frees is only ever handed out
/// again by a later one.
pub fn resolve_into<K, T>(
ops: &mut Vec<DlOp<T>>,
namespace: DlNamespace,
delta: &api::interning::InternOps<K>,
mut resolve: impl FnMut(&K) -> T,
) {
for add in &delta.adds {
ops.push(DlOp::Insert {
namespace,
slot: add.slot,
value: resolve(&add.key),
});
}
for &slot in &delta.removes {
ops.push(DlOp::Remove { namespace, slot });
}
}
/// Adds and removes in one resolved op list. A close is not counted: it drops a
/// whole namespace at once, and totalling its slots would cost a lookup per op
/// for a number nothing acts on.
pub fn count_dl_ops<T>(ops: &[DlOp<T>]) -> (usize, usize) {
let mut insertions = 0;
let mut removals = 0;
for op in ops {
match op {
DlOp::Insert { .. } => insertions += 1,
DlOp::Remove { .. } => removals += 1,
DlOp::Open(..) | DlOp::Close(..) => {}
}
}
(insertions, removals)
}
/// Two-level store fed by the content interner's delta: an outer array indexed
/// by namespace, an inner array indexed by content slot.
pub struct DlStore<K, T> {
/// `None` is a namespace that was never opened or has been closed. Closing
/// drops a pipeline's entire slot array at once, which is what handles
/// teardown - a dead content process never sends removes of its own.
namespaces: Vec<Option<Vec<Option<Entry<T>>>>>,
/// How many times each namespace index has been opened. Kept in step with
/// the allocator's count so a handle's generation can be checked against
/// it; see `DlHandle::generation`. Debug only, like the field it checks.
#[cfg(debug_assertions)]
generations: Vec<u32>,
/// Next id to stamp on an inserted entry. Advanced once per insert and
/// never reused; see `DlStore::uid`.
next_uid: u64,
_marker: PhantomData<K>,
}
#[derive(MallocSizeOf)]
struct Entry<T> {
/// See `DlStore::uid`. Assigned when the entry is inserted and fixed for as
/// long as it lives.
uid: ItemUid,
value: T,
}
impl<K, T> Default for DlStore<K, T> {
fn default() -> Self {
DlStore {
namespaces: Vec::new(),
#[cfg(debug_assertions)]
generations: Vec::new(),
next_uid: 0,
_marker: PhantomData,
}
}
}
impl<K, T: malloc_size_of::MallocSizeOf> malloc_size_of::MallocSizeOf for DlStore<K, T> {
fn size_of(&self, ops: &mut malloc_size_of::MallocSizeOfOps) -> usize {
// Hand-written rather than derived, which would demand `K: MallocSizeOf`
// for the marker.
self.namespaces.size_of(ops)
}
}
impl<K, T> DlStore<K, T> {
/// Number of live entries across every open namespace.
pub fn len(&self) -> usize {
self.namespaces
.iter()
.filter_map(|slots| slots.as_ref())
.map(|slots| slots.iter().filter(|slot| slot.is_some()).count())
.sum()
}
/// Replay a resolved delta. The only way a store changes: it is applied in
/// the order given and never consulted about what it is asked to do.
pub fn apply(&mut self, ops: Vec<DlOp<T>>) {
for op in ops {
match op {
DlOp::Open(namespace) => self.open(namespace),
DlOp::Insert { namespace, slot, value } => {
self.insert(namespace, slot, value)
}
DlOp::Remove { namespace, slot } => self.remove(namespace, slot),
DlOp::Close(namespace) => self.close(namespace),
}
}
}
pub fn open(&mut self, namespace: DlNamespace) {
let index = namespace.0 as usize;
if index >= self.namespaces.len() {
self.namespaces.resize_with(index + 1, || None);
}
assert!(
self.namespaces[index].is_none(),
"namespace {} opened twice",
namespace.0,
);
self.namespaces[index] = Some(Vec::new());
#[cfg(debug_assertions)]
{
if index >= self.generations.len() {
self.generations.resize(index + 1, 0);
}
self.generations[index] += 1;
}
}
pub fn close(&mut self, namespace: DlNamespace) {
let slots = self
.namespaces
.get_mut(namespace.0 as usize)
.filter(|slots| slots.is_some())
.unwrap_or_else(|| panic!("namespace {} is not open", namespace.0));
*slots = None;
}
pub fn insert(&mut self, namespace: DlNamespace, slot: u32, value: T) {
let uid = ItemUid::from_counter(self.next_uid);
self.next_uid += 1;
let slots = self.slots_mut(namespace);
let slot = slot as usize;
if slot >= slots.len() {
slots.resize_with(slot + 1, || None);
}
assert!(
slots[slot].is_none(),
"add for an occupied slot {}:{}",
namespace.0,
slot,
);
slots[slot] = Some(Entry { uid, value });
}
pub fn remove(&mut self, namespace: DlNamespace, slot: u32) {
let slots = self.slots_mut(namespace);
let removed = slots
.get_mut(slot as usize)
.and_then(|entry| entry.take());
assert!(
removed.is_some(),
"remove for an empty slot {}:{}",
namespace.0,
slot,
);
}
pub fn get(&self, handle: DlHandle<K>) -> Option<&T> {
self.entry(handle).map(|entry| &entry.value)
}
/// Identity of an entry for tile cache dependency tracking, which needs two
/// things of it. It must be **stable**: an entry has to keep the same value
/// for as long as it lives, or every tile invalidates for nothing. And it
/// must be **distinct**: no two entries may share one, or a tile keeps
/// rendering what used to be in a recycled slot.
///
/// Nothing about the handle supplies both. `{namespace, slot}` repeats when a
/// slot is recycled, and adding the content build stamp does not fix it
/// either: a replacement builder (see `DeltaAction::Reset`) restarts slot and
/// build numbering, so the first entry of an unrelated display list reuses
/// the pair. An interner can pack an index with an epoch because it owns the
/// whole index space; a follower of per-builder slot numbering cannot.
///
/// So the store mints its own instead: a counter, advanced per insert and
/// never reused. Injective by construction, which a hash of the content would
/// not be - a collision there would silently leave a tile showing stale
/// content, and this is not a place to accept that. The cost is that a
/// takeover re-mints every uid, so its tiles invalidate; that is correct, just
/// conservative, and a takeover means the content process was replaced.
///
/// Panics on a handle with no entry, like `Index`: a primitive referencing a
/// slot no delta has filled is the failure this is meant to surface.
pub fn uid(&self, handle: DlHandle<K>) -> ItemUid {
self.entry(handle)
.unwrap_or_else(|| panic!("bad dl store lookup {:?}", handle))
.uid
}
/// Current occupant count for a namespace; see `DlHandle::generation`.
#[cfg(debug_assertions)]
pub fn generation(&self, namespace: DlNamespace) -> u32 {
self.generations.get(namespace.0 as usize).copied().unwrap_or(0)
}
fn entry(&self, handle: DlHandle<K>) -> Option<&Entry<T>> {
// A handle from before this namespace was recycled would otherwise read
// whatever now occupies the slot. See `DlHandle::generation`.
#[cfg(debug_assertions)]
debug_assert_eq!(
self.generations.get(handle.namespace.0 as usize).copied(),
Some(handle.generation),
"stale handle into a recycled namespace: {:?}",
handle,
);
self.namespaces
.get(handle.namespace.0 as usize)?
.as_ref()?
.get(handle.slot as usize)?
.as_ref()
}
fn slots_mut(&mut self, namespace: DlNamespace) -> &mut Vec<Option<Entry<T>>> {
self.namespaces
.get_mut(namespace.0 as usize)
.and_then(|slots| slots.as_mut())
.unwrap_or_else(|| panic!("namespace {} is not open", namespace.0))
}
}
impl<K, T> ops::Index<DlHandle<K>> for DlStore<K, T> {
type Output = T;
fn index(&self, handle: DlHandle<K>) -> &T {
self.get(handle)
.unwrap_or_else(|| panic!("bad dl store lookup {:?}", handle))
}
}
#[cfg(test)]
mod tests {
use super::*;
use malloc_size_of::MallocSizeOf;
use std::mem;
struct Key;
fn pipeline(id: u32) -> PipelineId {
PipelineId(1, id)
}
fn store() -> DlStore<Key, u32> {
DlStore::default()
}
/// A handle naming the namespace's current occupant, which is what a scene
/// built now would carry.
fn h(store: &DlStore<Key, u32>, namespace: DlNamespace, slot: u32) -> DlHandle<Key> {
DlHandle::new(namespace, store.generation(namespace), slot)
}
#[test]
fn handle_is_two_words() {
// Two words in release, where it is on the per-primitive path; a debug
// build carries the namespace generation as well.
let expected = if cfg!(debug_assertions) { 12 } else { 8 };
assert_eq!(mem::size_of::<DlHandle<Key>>(), expected, "DlHandle size changed");
}
#[test]
#[should_panic(expected = "stale handle")]
fn a_handle_into_a_recycled_namespace_panics() {
let mut store = store();
store.open(DlNamespace(0));
store.insert(DlNamespace(0), 0, 100);
let stale = h(&store, DlNamespace(0), 0);
// The pipeline goes away and the index is handed to another one. A
// retained scene still holding `stale` would otherwise read this
// pipeline's data as if it were its own.
store.close(DlNamespace(0));
store.open(DlNamespace(0));
store.insert(DlNamespace(0), 0, 200);
store.get(stale);
}
#[test]
fn a_pipeline_keeps_its_namespace_across_display_lists() {
let mut alloc = DlBuilderMap::default();
let (first, allocated) = alloc.get_or_alloc(pipeline(1));
assert!(allocated);
let (second, allocated) = alloc.get_or_alloc(pipeline(1));
assert!(!allocated, "the second display list reallocated the namespace");
assert_eq!(first, second);
}
#[test]
fn namespaces_are_dense_and_recycled() {
let mut alloc = DlBuilderMap::default();
let a = alloc.get_or_alloc(pipeline(1)).0;
let b = alloc.get_or_alloc(pipeline(2)).0;
assert_ne!(a, b);
assert!(a.0 < 2 && b.0 < 2, "namespaces are not dense: {:?} {:?}", a, b);
alloc.remove_pipeline(pipeline(1));
assert_eq!(alloc.take_removals(), vec![a]);
assert!(alloc.take_removals().is_empty(), "released twice");
let c = alloc.get_or_alloc(pipeline(3)).0;
assert_eq!(c, a, "the released namespace was not reused");
}
#[test]
fn a_removed_pipeline_holds_its_namespace_until_a_scene_is_built() {
let mut alloc = DlBuilderMap::default();
let a = alloc.get_or_alloc(pipeline(1)).0;
alloc.remove_pipeline(pipeline(1));
// Removing a pipeline does not rebuild the scene, so until one is built
// the render backend is still drawing primitives that point into `a`.
// Handing it to another pipeline now would alias them.
let b = alloc.get_or_alloc(pipeline(2)).0;
assert_ne!(b, a, "a namespace was reused while a live scene referenced it");
assert_eq!(alloc.take_removals(), vec![a]);
let c = alloc.get_or_alloc(pipeline(3)).0;
assert_eq!(c, a, "the released namespace was not reused");
}
#[test]
fn a_pipeline_that_comes_back_keeps_its_namespace() {
let mut alloc = DlBuilderMap::default();
let a = alloc.get_or_alloc(pipeline(1)).0;
alloc.remove_pipeline(pipeline(1));
// A new display list before the release lands means the pipeline is
// live again on the same namespace, so the release is off - closing it
// would drop entries the new list still references.
let (again, allocated) = alloc.get_or_alloc(pipeline(1));
assert_eq!(again, a);
assert!(!allocated, "the namespace was reallocated rather than kept");
assert!(alloc.take_removals().is_empty(), "a live pipeline was released");
}
fn builder(id: u64) -> BuilderId {
BuilderId(id)
}
/// A map with one pipeline whose stream has reached the given build.
fn tracking(build: u32) -> DlBuilderMap {
let mut map = DlBuilderMap::default();
map.get_or_alloc(pipeline(1));
assert_eq!(map.check_delta(pipeline(1), builder(7), BuildId(build), false), DeltaAction::Apply);
map
}
#[test]
fn a_contiguous_stream_is_accepted() {
let mut map = tracking(0);
// Including builds that interned nothing: those still advance the
// builder's counter, so they must advance ours.
assert_eq!(map.check_delta(pipeline(1), builder(7), BuildId(1), true), DeltaAction::Apply);
assert_eq!(map.check_delta(pipeline(1), builder(7), BuildId(2), false), DeltaAction::Apply);
assert_eq!(map.check_delta(pipeline(1), builder(7), BuildId(3), true), DeltaAction::Apply);
assert_eq!(map.check_delta(pipeline(1), builder(7), BuildId(4), false), DeltaAction::Apply);
}
#[test]
fn a_stream_may_start_partway_in() {
// Only a delta that interns something claims the stream, so the first
// one we track need not be build zero.
let mut map = tracking(9);
assert_eq!(map.check_delta(pipeline(1), builder(7), BuildId(10), false), DeltaAction::Apply);
}
#[test]
#[should_panic(expected = "out of sequence")]
fn a_dropped_delta_panics() {
let mut map = tracking(0);
map.check_delta(pipeline(1), builder(7), BuildId(2), false);
}
#[test]
#[should_panic(expected = "out of sequence")]
fn a_repeated_delta_panics() {
let mut map = tracking(0);
map.check_delta(pipeline(1), builder(7), BuildId(1), false);
map.check_delta(pipeline(1), builder(7), BuildId(1), false);
}
#[test]
fn a_second_builder_with_content_takes_over() {
let mut map = tracking(0);
// A client that builds every display list with a fresh builder, or a
// replaced content process. The new builder's slot numbering starts
// again, so the old entries have to be dropped rather than merged.
assert_eq!(
map.check_delta(pipeline(1), builder(8), BuildId(0), false),
DeltaAction::Reset,
);
assert_eq!(
map.check_delta(pipeline(1), builder(8), BuildId(1), false),
DeltaAction::Apply,
);
}
#[test]
#[should_panic(expected = "alternating")]
fn two_builders_alternating_panics() {
let mut map = tracking(0);
// Taking over is only sound because the displaced builder is gone. One
// that comes back would reference entries the takeover dropped and never
// re-mint them, so the store lookup would fail far from here.
map.check_delta(pipeline(1), builder(8), BuildId(0), false);
map.check_delta(pipeline(1), builder(7), BuildId(1), false);
}
#[test]
fn a_second_builder_sending_nothing_is_ignored() {
let mut map = tracking(0);
// Gecko's clear-display-list paths: a throwaway builder, an empty list,
// and so an empty delta. It must not disturb the real stream.
assert_eq!(
map.check_delta(pipeline(1), builder(8), BuildId(0), true),
DeltaAction::Ignore,
);
assert_eq!(map.check_delta(pipeline(1), builder(7), BuildId(1), false), DeltaAction::Apply);
}
#[test]
fn streams_are_tracked_per_pipeline() {
let mut map = DlBuilderMap::default();
map.get_or_alloc(pipeline(1));
map.get_or_alloc(pipeline(2));
// Two builders at different points in their own streams.
assert_eq!(map.check_delta(pipeline(1), builder(7), BuildId(4), false), DeltaAction::Apply);
assert_eq!(map.check_delta(pipeline(2), builder(8), BuildId(0), false), DeltaAction::Apply);
assert_eq!(map.check_delta(pipeline(1), builder(7), BuildId(5), false), DeltaAction::Apply);
assert_eq!(map.check_delta(pipeline(2), builder(8), BuildId(1), false), DeltaAction::Apply);
}
#[test]
fn applying_a_delta_replays_it_in_order() {
let mut store = store();
// One pipeline's whole life: opened on its first display list, filled,
// a slot recycled by a later build, then closed when it goes away.
store.apply(vec![
DlOp::Open(DlNamespace(0)),
DlOp::Insert { namespace: DlNamespace(0), slot: 0, value: 100 },
DlOp::Insert { namespace: DlNamespace(0), slot: 1, value: 200 },
]);
assert_eq!(store[h(&store, DlNamespace(0), 1)], 200);
store.apply(vec![
DlOp::Remove { namespace: DlNamespace(0), slot: 1 },
DlOp::Close(DlNamespace(0)),
DlOp::Open(DlNamespace(0)),
DlOp::Insert { namespace: DlNamespace(0), slot: 1, value: 300 },
]);
assert_eq!(store.get(h(&store, DlNamespace(0), 0)), None, "close kept a slot");
assert_eq!(store[h(&store, DlNamespace(0), 1)], 300);
}
#[test]
fn slots_are_addressed_per_namespace() {
let mut store = store();
store.open(DlNamespace(0));
store.open(DlNamespace(1));
// The same slot number in two namespaces is two different items.
store.insert(DlNamespace(0), 3, 100);
store.insert(DlNamespace(1), 3, 200);
assert_eq!(store[h(&store, DlNamespace(0), 3)], 100);
assert_eq!(store[h(&store, DlNamespace(1), 3)], 200);
}
#[test]
fn closing_drops_every_slot_in_the_namespace() {
let mut store = store();
store.open(DlNamespace(0));
store.insert(DlNamespace(0), 0, 100);
store.insert(DlNamespace(0), 7, 100);
store.close(DlNamespace(0));
assert_eq!(store.get(h(&store, DlNamespace(0), 0)), None);
// Reopening is a fresh, empty slot space, not the old one.
store.open(DlNamespace(0));
assert_eq!(store.get(h(&store, DlNamespace(0), 7)), None);
}
/// Drive the allocator and a store together through a pipeline going away
/// and its namespace being handed to a different one, which is the sequence
/// the two halves have to agree on.
fn recycle_across_pipelines() -> (DlBuilderMap, DlStore<Key, u32>, DlNamespace) {
let mut map = DlBuilderMap::default();
let mut store = store();
let (ns_a, allocated) = map.get_or_alloc(pipeline(1));
assert!(allocated);
store.open(ns_a);
store.insert(ns_a, 0, 100);
// Removed, then released at the next scene build.
map.remove_pipeline(pipeline(1));
for namespace in map.take_removals() {
store.close(namespace);
}
let (ns_b, allocated) = map.get_or_alloc(pipeline(2));
assert_eq!(ns_b, ns_a, "the index was not recycled");
assert!(allocated, "a recycled namespace must still be opened");
store.open(ns_b);
store.insert(ns_b, 0, 200);
(map, store, ns_b)
}
#[test]
fn a_recycled_namespace_serves_its_new_pipeline() {
let (map, store, namespace) = recycle_across_pipelines();
// Same index, same slot, but the second pipeline's data - the first
// pipeline's entry went with the close.
let (_, generation) = map.expect(pipeline(2));
assert_eq!(store[DlHandle::new(namespace, generation, 0)], 200);
}
#[test]
#[should_panic(expected = "stale handle")]
fn a_handle_from_the_previous_occupant_panics() {
let mut map = DlBuilderMap::default();
let mut store = store();
let (ns_a, _) = map.get_or_alloc(pipeline(1));
let stale = DlHandle::new(ns_a, map.expect(pipeline(1)).1, 0);
store.open(ns_a);
store.insert(ns_a, 0, 100);
map.remove_pipeline(pipeline(1));
for namespace in map.take_removals() {
store.close(namespace);
}
let (ns_b, _) = map.get_or_alloc(pipeline(2));
store.open(ns_b);
store.insert(ns_b, 0, 200);
// A scene retained from before the swap would read pipeline 2's run as
// if it were pipeline 1's.
store.get(stale);
}
#[test]
fn a_uid_is_fixed_for_an_entry_and_never_reused() {
let mut store = store();
store.open(DlNamespace(0));
store.open(DlNamespace(1));
store.insert(DlNamespace(0), 0, 100);
let first = store.uid(h(&store, DlNamespace(0), 0));
// Fixed while the entry lives: a tile must not invalidate for an entry
// that has not changed.
store.insert(DlNamespace(0), 1, 200);
assert_eq!(store.uid(h(&store, DlNamespace(0), 0)), first);
// Never handed out twice, whether the slot is recycled or the whole
// namespace is. Either would otherwise leave a tile rendering what used
// to be there.
store.remove(DlNamespace(0), 0);
store.insert(DlNamespace(0), 0, 300);
assert_ne!(store.uid(h(&store, DlNamespace(0), 0)), first);
store.close(DlNamespace(0));
store.open(DlNamespace(0));
store.insert(DlNamespace(0), 0, 100);
assert_ne!(store.uid(h(&store, DlNamespace(0), 0)), first);
// And not shared across namespaces, which per-builder slot numbering
// cannot distinguish on its own.
store.insert(DlNamespace(1), 0, 100);
assert_ne!(
store.uid(h(&store, DlNamespace(1), 0)),
store.uid(h(&store, DlNamespace(0), 0)),
);
}
#[test]
fn a_store_reports_its_live_entries_and_its_memory() {
use malloc_size_of::MallocSizeOfOps;
// Stand-in for the platform's malloc_usable_size: any non-zero answer
// for a live block is enough to tell a real measurement from a no-op.
extern "C" fn block_size(_ptr: *const std::os::raw::c_void) -> usize {
8
}
let mut store = store();
let mut ops = MallocSizeOfOps::new(block_size, None);
assert_eq!(store.len(), 0);
store.open(DlNamespace(0));
store.insert(DlNamespace(0), 0, 100);
store.insert(DlNamespace(0), 4, 200);
assert_eq!(store.len(), 2, "gaps between slots are not entries");
// The heap the entries sit in has to show up, or the memory report is a
// constant zero - which is what a hand-written `size_of` gets wrong.
assert!(store.size_of(&mut ops) > 0, "store reported no memory");
store.remove(DlNamespace(0), 0);
assert_eq!(store.len(), 1);
store.close(DlNamespace(0));
assert_eq!(store.len(), 0, "a closed namespace still counted");
}
#[test]
fn a_removed_slot_is_reusable_but_not_readable() {
let mut store = store();
store.open(DlNamespace(0));
store.insert(DlNamespace(0), 2, 100);
store.remove(DlNamespace(0), 2);
assert_eq!(store.get(h(&store, DlNamespace(0), 2)), None);
store.insert(DlNamespace(0), 2, 200);
assert_eq!(store[h(&store, DlNamespace(0), 2)], 200);
}
#[test]
#[should_panic(expected = "add for an occupied slot")]
fn a_duplicate_add_panics() {
let mut store = store();
store.open(DlNamespace(0));
store.insert(DlNamespace(0), 0, 100);
store.insert(DlNamespace(0), 0, 200);
}
#[test]
#[should_panic(expected = "remove for an empty slot")]
fn a_duplicate_remove_panics() {
let mut store = store();
store.open(DlNamespace(0));
store.insert(DlNamespace(0), 0, 100);
store.remove(DlNamespace(0), 0);
store.remove(DlNamespace(0), 0);
}
#[test]
#[should_panic(expected = "is not open")]
fn adding_to_a_closed_namespace_panics() {
let mut store = store();
store.open(DlNamespace(0));
store.close(DlNamespace(0));
store.insert(DlNamespace(0), 0, 100);
}
}