diff options
Diffstat (limited to 'gfx/wr/webrender/src/texture_pack/mod.rs')
| -rw-r--r-- | gfx/wr/webrender/src/texture_pack/mod.rs | 441 |
1 files changed, 441 insertions, 0 deletions
diff --git a/gfx/wr/webrender/src/texture_pack/mod.rs b/gfx/wr/webrender/src/texture_pack/mod.rs new file mode 100644 index 0000000000..f89a82b0a1 --- /dev/null +++ b/gfx/wr/webrender/src/texture_pack/mod.rs @@ -0,0 +1,441 @@ +/* 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 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +mod guillotine; +use crate::texture_cache::TextureCacheHandle; +use crate::internal_types::FastHashMap; +pub use guillotine::*; + +/* 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 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +use api::units::*; +use crate::internal_types::CacheTextureId; +use euclid::{point2, size2, default::Box2D}; +use smallvec::SmallVec; + +pub use etagere::AllocatorOptions as ShelfAllocatorOptions; +pub use etagere::BucketedAtlasAllocator as BucketedShelfAllocator; +pub use etagere::AtlasAllocator as ShelfAllocator; + +/// ID of an allocation within a given allocator. +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] +#[cfg_attr(feature = "capture", derive(Serialize))] +#[cfg_attr(feature = "replay", derive(Deserialize))] +pub struct AllocId(pub u32); + +pub trait AtlasAllocator { + /// Specific parameters of the allocator. + type Parameters; + /// Constructor + fn new(size: i32, parameters: &Self::Parameters) -> Self; + /// Allocate a rectangle. + fn allocate(&mut self, size: DeviceIntSize) -> Option<(AllocId, DeviceIntRect)>; + /// Deallocate a rectangle and return its size. + fn deallocate(&mut self, id: AllocId); + /// Return true if there is no live allocations. + fn is_empty(&self) -> bool; + /// Allocated area in pixels. + fn allocated_space(&self) -> i32; + /// Write a debug visualization of the atlas fitting in the provided rectangle. + /// + /// This is inserted in a larger dump so it shouldn't contain the xml start/end tags. + fn dump_into_svg(&self, rect: &Box2D<f32>, output: &mut dyn std::io::Write) -> std::io::Result<()>; +} + +pub trait AtlasAllocatorList<TextureParameters> { + /// Allocate a rectangle. + /// + /// If allocation fails, call the provided callback, add a new allocator to the list and try again. + fn allocate( + &mut self, + size: DeviceIntSize, + texture_alloc_cb: &mut dyn FnMut(DeviceIntSize, &TextureParameters) -> CacheTextureId, + ) -> (CacheTextureId, AllocId, DeviceIntRect); + + fn set_handle(&mut self, texture_id: CacheTextureId, alloc_id: AllocId, handle: &TextureCacheHandle); + + fn remove_handle(&mut self, texture_id: CacheTextureId, alloc_id: AllocId); + + /// Deallocate a rectangle and return its size. + fn deallocate(&mut self, texture_id: CacheTextureId, alloc_id: AllocId); + + fn texture_parameters(&self) -> &TextureParameters; +} + +/// A number of 2D textures (single layer), with their own atlas allocator. +#[cfg_attr(feature = "capture", derive(Serialize))] +#[cfg_attr(feature = "replay", derive(Deserialize))] +struct TextureUnit<Allocator> { + allocator: Allocator, + handles: FastHashMap<AllocId, TextureCacheHandle>, + texture_id: CacheTextureId, + // The texture might become empty during a frame where we copy items out + // of it, in which case we want to postpone deleting the texture to the + // next frame. + delay_deallocation: bool, +} + +#[cfg_attr(feature = "capture", derive(Serialize))] +#[cfg_attr(feature = "replay", derive(Deserialize))] +pub struct AllocatorList<Allocator: AtlasAllocator, TextureParameters> { + units: SmallVec<[TextureUnit<Allocator>; 1]>, + size: i32, + atlas_parameters: Allocator::Parameters, + texture_parameters: TextureParameters, +} + +impl<Allocator: AtlasAllocator, TextureParameters> AllocatorList<Allocator, TextureParameters> { + pub fn new( + size: i32, + atlas_parameters: Allocator::Parameters, + texture_parameters: TextureParameters, + ) -> Self { + AllocatorList { + units: SmallVec::new(), + size, + atlas_parameters, + texture_parameters, + } + } + + pub fn allocate( + &mut self, + requested_size: DeviceIntSize, + texture_alloc_cb: &mut dyn FnMut(DeviceIntSize, &TextureParameters) -> CacheTextureId, + ) -> (CacheTextureId, AllocId, DeviceIntRect) { + // Try to allocate from one of the existing textures. + for unit in &mut self.units { + if let Some((alloc_id, rect)) = unit.allocator.allocate(requested_size) { + return (unit.texture_id, alloc_id, rect); + } + } + + // Need to create a new texture to hold the allocation. + let texture_id = texture_alloc_cb(size2(self.size, self.size), &self.texture_parameters); + let unit_index = self.units.len(); + + self.units.push(TextureUnit { + allocator: Allocator::new(self.size, &self.atlas_parameters), + handles: FastHashMap::default(), + texture_id, + delay_deallocation: false, + }); + + let (alloc_id, rect) = self.units[unit_index] + .allocator + .allocate(requested_size) + .unwrap(); + + (texture_id, alloc_id, rect) + } + + pub fn deallocate(&mut self, texture_id: CacheTextureId, alloc_id: AllocId) { + let unit = self.units + .iter_mut() + .find(|unit| unit.texture_id == texture_id) + .expect("Unable to find the associated texture array unit"); + + unit.handles.remove(&alloc_id); + unit.allocator.deallocate(alloc_id); + } + + pub fn release_empty_textures<'l>(&mut self, texture_dealloc_cb: &'l mut dyn FnMut(CacheTextureId)) { + self.units.retain(|unit| { + if unit.allocator.is_empty() && !unit.delay_deallocation { + texture_dealloc_cb(unit.texture_id); + + false + } else{ + unit.delay_deallocation = false; + true + } + }); + } + + pub fn clear(&mut self, texture_dealloc_cb: &mut dyn FnMut(CacheTextureId)) { + for unit in self.units.drain(..) { + texture_dealloc_cb(unit.texture_id); + } + } + + #[allow(dead_code)] + pub fn dump_as_svg(&self, output: &mut dyn std::io::Write) -> std::io::Result<()> { + use svg_fmt::*; + + let num_arrays = self.units.len() as f32; + + let text_spacing = 15.0; + let unit_spacing = 30.0; + let texture_size = self.size as f32 / 2.0; + + let svg_w = unit_spacing * 2.0 + texture_size; + let svg_h = unit_spacing + num_arrays * (texture_size + text_spacing + unit_spacing); + + writeln!(output, "{}", BeginSvg { w: svg_w, h: svg_h })?; + + // Background. + writeln!(output, + " {}", + rectangle(0.0, 0.0, svg_w, svg_h) + .inflate(1.0, 1.0) + .fill(rgb(50, 50, 50)) + )?; + + let mut y = unit_spacing; + for unit in &self.units { + writeln!(output, " {}", text(unit_spacing, y, format!("{:?}", unit.texture_id)).color(rgb(230, 230, 230)))?; + + let rect = Box2D { + min: point2(unit_spacing, y), + max: point2(unit_spacing + texture_size, y + texture_size), + }; + + unit.allocator.dump_into_svg(&rect, output)?; + + y += unit_spacing + texture_size + text_spacing; + } + + writeln!(output, "{}", EndSvg) + } + + pub fn allocated_space(&self) -> i32 { + let mut accum = 0; + for unit in &self.units { + accum += unit.allocator.allocated_space(); + } + + accum + } + + pub fn allocated_textures(&self) -> usize { + self.units.len() + } + + pub fn size(&self) -> i32 { self.size } +} + +impl<Allocator: AtlasAllocator, TextureParameters> AtlasAllocatorList<TextureParameters> +for AllocatorList<Allocator, TextureParameters> { + fn allocate( + &mut self, + requested_size: DeviceIntSize, + texture_alloc_cb: &mut dyn FnMut(DeviceIntSize, &TextureParameters) -> CacheTextureId, + ) -> (CacheTextureId, AllocId, DeviceIntRect) { + self.allocate(requested_size, texture_alloc_cb) + } + + fn set_handle(&mut self, texture_id: CacheTextureId, alloc_id: AllocId, handle: &TextureCacheHandle) { + let unit = self.units + .iter_mut() + .find(|unit| unit.texture_id == texture_id) + .expect("Unable to find the associated texture array unit"); + unit.handles.insert(alloc_id, handle.clone()); + } + + fn remove_handle(&mut self, texture_id: CacheTextureId, alloc_id: AllocId) { + let unit = self.units + .iter_mut() + .find(|unit| unit.texture_id == texture_id) + .expect("Unable to find the associated texture array unit"); + unit.handles.remove(&alloc_id); + } + + fn deallocate(&mut self, texture_id: CacheTextureId, alloc_id: AllocId) { + self.deallocate(texture_id, alloc_id); + } + + fn texture_parameters(&self) -> &TextureParameters { + &self.texture_parameters + } +} + +impl AtlasAllocator for BucketedShelfAllocator { + type Parameters = ShelfAllocatorOptions; + + fn new(size: i32, options: &Self::Parameters) -> Self { + BucketedShelfAllocator::with_options(size2(size, size), options) + } + + fn allocate(&mut self, size: DeviceIntSize) -> Option<(AllocId, DeviceIntRect)> { + self.allocate(size.to_untyped()).map(|alloc| { + (AllocId(alloc.id.serialize()), alloc.rectangle.cast_unit()) + }) + } + + fn deallocate(&mut self, id: AllocId) { + self.deallocate(etagere::AllocId::deserialize(id.0)); + } + + fn is_empty(&self) -> bool { + self.is_empty() + } + + fn allocated_space(&self) -> i32 { + self.allocated_space() + } + + fn dump_into_svg(&self, rect: &Box2D<f32>, output: &mut dyn std::io::Write) -> std::io::Result<()> { + self.dump_into_svg(Some(&rect.to_i32().cast_unit()), output) + } +} + +impl AtlasAllocator for ShelfAllocator { + type Parameters = ShelfAllocatorOptions; + + fn new(size: i32, options: &Self::Parameters) -> Self { + ShelfAllocator::with_options(size2(size, size), options) + } + + fn allocate(&mut self, size: DeviceIntSize) -> Option<(AllocId, DeviceIntRect)> { + self.allocate(size.to_untyped()).map(|alloc| { + (AllocId(alloc.id.serialize()), alloc.rectangle.cast_unit()) + }) + } + + fn deallocate(&mut self, id: AllocId) { + self.deallocate(etagere::AllocId::deserialize(id.0)); + } + + fn is_empty(&self) -> bool { + self.is_empty() + } + + fn allocated_space(&self) -> i32 { + self.allocated_space() + } + + fn dump_into_svg(&self, rect: &Box2D<f32>, output: &mut dyn std::io::Write) -> std::io::Result<()> { + self.dump_into_svg(Some(&rect.to_i32().cast_unit()), output) + } +} + +pub struct CompactionChange { + pub handle: TextureCacheHandle, + pub old_id: AllocId, + pub old_tex: CacheTextureId, + pub old_rect: DeviceIntRect, + pub new_id: AllocId, + pub new_tex: CacheTextureId, + pub new_rect: DeviceIntRect, +} + +impl<P> AllocatorList<ShelfAllocator, P> { + /// Attempt to move some allocations from a texture to another to reduce the number of textures. + pub fn try_compaction( + &mut self, + max_pixels: i32, + changes: &mut Vec<CompactionChange>, + ) { + // The goal here is to consolidate items in the first texture by moving them from the last. + + if self.units.len() < 2 { + // Nothing to do we are already "compact". + return; + } + + let last_unit = self.units.len() - 1; + let mut pixels = 0; + while let Some(alloc) = self.units[last_unit].allocator.iter().next() { + // For each allocation in the last texture, try to allocate it in the first one. + let new_alloc = match self.units[0].allocator.allocate(alloc.rectangle.size()) { + Some(new_alloc) => new_alloc, + None => { + // Stop when we fail to fit an item into the first texture. + // We could potentially fit another smaller item in there but we take it as + // an indication that the texture is more or less full, and we'll eventually + // manage to move the items later if they still exist as other items expire, + // which is what matters. + break; + } + }; + + // The item was successfully reallocated in the first texture, we can proceed + // with removing it from the last. + + // We keep track of the texture cache handle for each allocation, make sure + // the new allocation has the proper handle. + let alloc_id = AllocId(alloc.id.serialize()); + let new_alloc_id = AllocId(new_alloc.id.serialize()); + let handle = self.units[last_unit].handles.get(&alloc_id).unwrap().clone(); + self.units[0].handles.insert(new_alloc_id, handle.clone()); + + // Remove the allocation for the last texture. + self.units[last_unit].handles.remove(&alloc_id); + self.units[last_unit].allocator.deallocate(alloc.id); + + // Prevent the texture from being deleted on the same frame. + self.units[last_unit].delay_deallocation = true; + + // Record the change so that the texture cache can do additional bookkeeping. + changes.push(CompactionChange { + handle, + old_id: AllocId(alloc.id.serialize()), + old_tex: self.units[last_unit].texture_id, + old_rect: alloc.rectangle.cast_unit(), + new_id: AllocId(new_alloc.id.serialize()), + new_tex: self.units[0].texture_id, + new_rect: new_alloc.rectangle.cast_unit(), + }); + + // We are not in a hurry to move all allocations we can in one go, as long as we + // eventually have a chance to move them all within a reasonable amount of time. + // It's best to spread the load over multiple frames to avoid sudden spikes, so we + // stop after we have passed a certain threshold. + pixels += alloc.rectangle.area(); + if pixels > max_pixels { + break; + } + } + } + +} + +#[test] +fn bug_1680769() { + let mut allocators: AllocatorList<ShelfAllocator, ()> = AllocatorList::new( + 1024, + ShelfAllocatorOptions::default(), + (), + ); + + let mut allocations = Vec::new(); + let mut next_id = CacheTextureId(0); + let alloc_cb = &mut |_: DeviceIntSize, _: &()| { + let texture_id = next_id; + next_id.0 += 1; + + texture_id + }; + + // Make some allocations, forcing the the creation of multiple textures. + for _ in 0..50 { + let alloc = allocators.allocate(size2(256, 256), alloc_cb); + allocators.set_handle(alloc.0, alloc.1, &TextureCacheHandle::Empty); + allocations.push(alloc); + } + + // Deallocate everything. + // It should empty all atlases and we still have textures allocated because + // we haven't called release_empty_textures yet. + for alloc in allocations.drain(..) { + allocators.deallocate(alloc.0, alloc.1); + } + + // Allocate something else. + // Bug 1680769 was causing this allocation to be duplicated and leaked in + // all textures. + allocations.push(allocators.allocate(size2(8, 8), alloc_cb)); + + // Deallocate all known allocations. + for alloc in allocations.drain(..) { + allocators.deallocate(alloc.0, alloc.1); + } + + // If we have leaked items, this won't manage to remove all textures. + allocators.release_empty_textures(&mut |_| {}); + + assert_eq!(allocators.allocated_textures(), 0); +} |