mod.rs (15239B)
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 mod guillotine; 6 use crate::texture_cache::TextureCacheHandle; 7 use crate::internal_types::FastHashMap; 8 pub use guillotine::*; 9 10 /* This Source Code Form is subject to the terms of the Mozilla Public 11 * License, v. 2.0. If a copy of the MPL was not distributed with this 12 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 13 14 use api::units::*; 15 use crate::internal_types::CacheTextureId; 16 use euclid::{point2, size2, default::Box2D}; 17 use smallvec::SmallVec; 18 19 pub use etagere::AllocatorOptions as ShelfAllocatorOptions; 20 pub use etagere::BucketedAtlasAllocator as BucketedShelfAllocator; 21 pub use etagere::AtlasAllocator as ShelfAllocator; 22 23 /// ID of an allocation within a given allocator. 24 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] 25 #[cfg_attr(feature = "capture", derive(Serialize))] 26 #[cfg_attr(feature = "replay", derive(Deserialize))] 27 pub struct AllocId(pub u32); 28 29 pub trait AtlasAllocator { 30 /// Specific parameters of the allocator. 31 type Parameters; 32 /// Constructor 33 fn new(size: i32, parameters: &Self::Parameters) -> Self; 34 /// Allocate a rectangle. 35 fn allocate(&mut self, size: DeviceIntSize) -> Option<(AllocId, DeviceIntRect)>; 36 /// Deallocate a rectangle and return its size. 37 fn deallocate(&mut self, id: AllocId); 38 /// Return true if there is no live allocations. 39 fn is_empty(&self) -> bool; 40 /// Allocated area in pixels. 41 fn allocated_space(&self) -> i32; 42 /// Write a debug visualization of the atlas fitting in the provided rectangle. 43 /// 44 /// This is inserted in a larger dump so it shouldn't contain the xml start/end tags. 45 fn dump_into_svg(&self, rect: &Box2D<f32>, output: &mut dyn std::io::Write) -> std::io::Result<()>; 46 } 47 48 pub trait AtlasAllocatorList<TextureParameters> { 49 /// Allocate a rectangle. 50 /// 51 /// If allocation fails, call the provided callback, add a new allocator to the list and try again. 52 fn allocate( 53 &mut self, 54 size: DeviceIntSize, 55 texture_alloc_cb: &mut dyn FnMut(DeviceIntSize, &TextureParameters) -> CacheTextureId, 56 ) -> (CacheTextureId, AllocId, DeviceIntRect); 57 58 fn set_handle(&mut self, texture_id: CacheTextureId, alloc_id: AllocId, handle: &TextureCacheHandle); 59 60 /// Deallocate a rectangle and return its size. 61 fn deallocate(&mut self, texture_id: CacheTextureId, alloc_id: AllocId); 62 63 fn texture_parameters(&self) -> &TextureParameters; 64 } 65 66 /// A number of 2D textures (single layer), with their own atlas allocator. 67 #[cfg_attr(feature = "capture", derive(Serialize))] 68 #[cfg_attr(feature = "replay", derive(Deserialize))] 69 struct TextureUnit<Allocator> { 70 allocator: Allocator, 71 handles: FastHashMap<AllocId, TextureCacheHandle>, 72 texture_id: CacheTextureId, 73 // The texture might become empty during a frame where we copy items out 74 // of it, in which case we want to postpone deleting the texture to the 75 // next frame. 76 delay_deallocation: bool, 77 } 78 79 #[cfg_attr(feature = "capture", derive(Serialize))] 80 #[cfg_attr(feature = "replay", derive(Deserialize))] 81 pub struct AllocatorList<Allocator: AtlasAllocator, TextureParameters> { 82 units: SmallVec<[TextureUnit<Allocator>; 1]>, 83 size: i32, 84 atlas_parameters: Allocator::Parameters, 85 texture_parameters: TextureParameters, 86 } 87 88 impl<Allocator: AtlasAllocator, TextureParameters> AllocatorList<Allocator, TextureParameters> { 89 pub fn new( 90 size: i32, 91 atlas_parameters: Allocator::Parameters, 92 texture_parameters: TextureParameters, 93 ) -> Self { 94 AllocatorList { 95 units: SmallVec::new(), 96 size, 97 atlas_parameters, 98 texture_parameters, 99 } 100 } 101 102 pub fn allocate( 103 &mut self, 104 requested_size: DeviceIntSize, 105 texture_alloc_cb: &mut dyn FnMut(DeviceIntSize, &TextureParameters) -> CacheTextureId, 106 ) -> (CacheTextureId, AllocId, DeviceIntRect) { 107 // Try to allocate from one of the existing textures. 108 for unit in &mut self.units { 109 if let Some((alloc_id, rect)) = unit.allocator.allocate(requested_size) { 110 return (unit.texture_id, alloc_id, rect); 111 } 112 } 113 114 // Need to create a new texture to hold the allocation. 115 let texture_id = texture_alloc_cb(size2(self.size, self.size), &self.texture_parameters); 116 let unit_index = self.units.len(); 117 118 self.units.push(TextureUnit { 119 allocator: Allocator::new(self.size, &self.atlas_parameters), 120 handles: FastHashMap::default(), 121 texture_id, 122 delay_deallocation: false, 123 }); 124 125 let (alloc_id, rect) = self.units[unit_index] 126 .allocator 127 .allocate(requested_size) 128 .unwrap(); 129 130 (texture_id, alloc_id, rect) 131 } 132 133 pub fn deallocate(&mut self, texture_id: CacheTextureId, alloc_id: AllocId) { 134 let unit = self.units 135 .iter_mut() 136 .find(|unit| unit.texture_id == texture_id) 137 .expect("Unable to find the associated texture array unit"); 138 139 unit.handles.remove(&alloc_id); 140 unit.allocator.deallocate(alloc_id); 141 } 142 143 pub fn release_empty_textures<'l>(&mut self, texture_dealloc_cb: &'l mut dyn FnMut(CacheTextureId)) { 144 self.units.retain(|unit| { 145 if unit.allocator.is_empty() && !unit.delay_deallocation { 146 texture_dealloc_cb(unit.texture_id); 147 148 false 149 } else{ 150 unit.delay_deallocation = false; 151 true 152 } 153 }); 154 } 155 156 pub fn clear(&mut self, texture_dealloc_cb: &mut dyn FnMut(CacheTextureId)) { 157 for unit in self.units.drain(..) { 158 texture_dealloc_cb(unit.texture_id); 159 } 160 } 161 162 #[allow(dead_code)] 163 pub fn dump_as_svg(&self, output: &mut dyn std::io::Write) -> std::io::Result<()> { 164 use svg_fmt::*; 165 166 let num_arrays = self.units.len() as f32; 167 168 let text_spacing = 15.0; 169 let unit_spacing = 30.0; 170 let texture_size = self.size as f32 / 2.0; 171 172 let svg_w = unit_spacing * 2.0 + texture_size; 173 let svg_h = unit_spacing + num_arrays * (texture_size + text_spacing + unit_spacing); 174 175 writeln!(output, "{}", BeginSvg { w: svg_w, h: svg_h })?; 176 177 // Background. 178 writeln!(output, 179 " {}", 180 rectangle(0.0, 0.0, svg_w, svg_h) 181 .inflate(1.0, 1.0) 182 .fill(rgb(50, 50, 50)) 183 )?; 184 185 let mut y = unit_spacing; 186 for unit in &self.units { 187 writeln!(output, " {}", text(unit_spacing, y, format!("{:?}", unit.texture_id)).color(rgb(230, 230, 230)))?; 188 189 let rect = Box2D { 190 min: point2(unit_spacing, y), 191 max: point2(unit_spacing + texture_size, y + texture_size), 192 }; 193 194 unit.allocator.dump_into_svg(&rect, output)?; 195 196 y += unit_spacing + texture_size + text_spacing; 197 } 198 199 writeln!(output, "{}", EndSvg) 200 } 201 202 pub fn allocated_space(&self) -> i32 { 203 let mut accum = 0; 204 for unit in &self.units { 205 accum += unit.allocator.allocated_space(); 206 } 207 208 accum 209 } 210 211 pub fn allocated_textures(&self) -> usize { 212 self.units.len() 213 } 214 215 pub fn size(&self) -> i32 { self.size } 216 } 217 218 impl<Allocator: AtlasAllocator, TextureParameters> AtlasAllocatorList<TextureParameters> 219 for AllocatorList<Allocator, TextureParameters> { 220 fn allocate( 221 &mut self, 222 requested_size: DeviceIntSize, 223 texture_alloc_cb: &mut dyn FnMut(DeviceIntSize, &TextureParameters) -> CacheTextureId, 224 ) -> (CacheTextureId, AllocId, DeviceIntRect) { 225 self.allocate(requested_size, texture_alloc_cb) 226 } 227 228 fn set_handle(&mut self, texture_id: CacheTextureId, alloc_id: AllocId, handle: &TextureCacheHandle) { 229 let unit = self.units 230 .iter_mut() 231 .find(|unit| unit.texture_id == texture_id) 232 .expect("Unable to find the associated texture array unit"); 233 unit.handles.insert(alloc_id, handle.clone()); 234 } 235 236 fn deallocate(&mut self, texture_id: CacheTextureId, alloc_id: AllocId) { 237 self.deallocate(texture_id, alloc_id); 238 } 239 240 fn texture_parameters(&self) -> &TextureParameters { 241 &self.texture_parameters 242 } 243 } 244 245 impl AtlasAllocator for BucketedShelfAllocator { 246 type Parameters = ShelfAllocatorOptions; 247 248 fn new(size: i32, options: &Self::Parameters) -> Self { 249 BucketedShelfAllocator::with_options(size2(size, size), options) 250 } 251 252 fn allocate(&mut self, size: DeviceIntSize) -> Option<(AllocId, DeviceIntRect)> { 253 self.allocate(size.to_untyped()).map(|alloc| { 254 (AllocId(alloc.id.serialize()), alloc.rectangle.cast_unit()) 255 }) 256 } 257 258 fn deallocate(&mut self, id: AllocId) { 259 self.deallocate(etagere::AllocId::deserialize(id.0)); 260 } 261 262 fn is_empty(&self) -> bool { 263 self.is_empty() 264 } 265 266 fn allocated_space(&self) -> i32 { 267 self.allocated_space() 268 } 269 270 fn dump_into_svg(&self, rect: &Box2D<f32>, output: &mut dyn std::io::Write) -> std::io::Result<()> { 271 self.dump_into_svg(Some(&rect.to_i32().cast_unit()), output) 272 } 273 } 274 275 impl AtlasAllocator for ShelfAllocator { 276 type Parameters = ShelfAllocatorOptions; 277 278 fn new(size: i32, options: &Self::Parameters) -> Self { 279 ShelfAllocator::with_options(size2(size, size), options) 280 } 281 282 fn allocate(&mut self, size: DeviceIntSize) -> Option<(AllocId, DeviceIntRect)> { 283 self.allocate(size.to_untyped()).map(|alloc| { 284 (AllocId(alloc.id.serialize()), alloc.rectangle.cast_unit()) 285 }) 286 } 287 288 fn deallocate(&mut self, id: AllocId) { 289 self.deallocate(etagere::AllocId::deserialize(id.0)); 290 } 291 292 fn is_empty(&self) -> bool { 293 self.is_empty() 294 } 295 296 fn allocated_space(&self) -> i32 { 297 self.allocated_space() 298 } 299 300 fn dump_into_svg(&self, rect: &Box2D<f32>, output: &mut dyn std::io::Write) -> std::io::Result<()> { 301 self.dump_into_svg(Some(&rect.to_i32().cast_unit()), output) 302 } 303 } 304 305 pub struct CompactionChange { 306 pub handle: TextureCacheHandle, 307 pub old_tex: CacheTextureId, 308 pub old_rect: DeviceIntRect, 309 pub new_id: AllocId, 310 pub new_tex: CacheTextureId, 311 pub new_rect: DeviceIntRect, 312 } 313 314 impl<P> AllocatorList<ShelfAllocator, P> { 315 /// Attempt to move some allocations from a texture to another to reduce the number of textures. 316 pub fn try_compaction( 317 &mut self, 318 max_pixels: i32, 319 changes: &mut Vec<CompactionChange>, 320 ) { 321 // The goal here is to consolidate items in the first texture by moving them from the last. 322 323 if self.units.len() < 2 { 324 // Nothing to do we are already "compact". 325 return; 326 } 327 328 let last_unit = self.units.len() - 1; 329 let mut pixels = 0; 330 while let Some(alloc) = self.units[last_unit].allocator.iter().next() { 331 // For each allocation in the last texture, try to allocate it in the first one. 332 let new_alloc = match self.units[0].allocator.allocate(alloc.rectangle.size()) { 333 Some(new_alloc) => new_alloc, 334 None => { 335 // Stop when we fail to fit an item into the first texture. 336 // We could potentially fit another smaller item in there but we take it as 337 // an indication that the texture is more or less full, and we'll eventually 338 // manage to move the items later if they still exist as other items expire, 339 // which is what matters. 340 break; 341 } 342 }; 343 344 // The item was successfully reallocated in the first texture, we can proceed 345 // with removing it from the last. 346 347 // We keep track of the texture cache handle for each allocation, make sure 348 // the new allocation has the proper handle. 349 let alloc_id = AllocId(alloc.id.serialize()); 350 let new_alloc_id = AllocId(new_alloc.id.serialize()); 351 let handle = self.units[last_unit].handles.get(&alloc_id).unwrap().clone(); 352 self.units[0].handles.insert(new_alloc_id, handle.clone()); 353 354 // Remove the allocation for the last texture. 355 self.units[last_unit].handles.remove(&alloc_id); 356 self.units[last_unit].allocator.deallocate(alloc.id); 357 358 // Prevent the texture from being deleted on the same frame. 359 self.units[last_unit].delay_deallocation = true; 360 361 // Record the change so that the texture cache can do additional bookkeeping. 362 changes.push(CompactionChange { 363 handle, 364 old_tex: self.units[last_unit].texture_id, 365 old_rect: alloc.rectangle.cast_unit(), 366 new_id: AllocId(new_alloc.id.serialize()), 367 new_tex: self.units[0].texture_id, 368 new_rect: new_alloc.rectangle.cast_unit(), 369 }); 370 371 // We are not in a hurry to move all allocations we can in one go, as long as we 372 // eventually have a chance to move them all within a reasonable amount of time. 373 // It's best to spread the load over multiple frames to avoid sudden spikes, so we 374 // stop after we have passed a certain threshold. 375 pixels += alloc.rectangle.area(); 376 if pixels > max_pixels { 377 break; 378 } 379 } 380 } 381 382 } 383 384 #[test] 385 fn bug_1680769() { 386 let mut allocators: AllocatorList<ShelfAllocator, ()> = AllocatorList::new( 387 1024, 388 ShelfAllocatorOptions::default(), 389 (), 390 ); 391 392 let mut allocations = Vec::new(); 393 let mut next_id = CacheTextureId(0); 394 let alloc_cb = &mut |_: DeviceIntSize, _: &()| { 395 let texture_id = next_id; 396 next_id.0 += 1; 397 398 texture_id 399 }; 400 401 // Make some allocations, forcing the the creation of multiple textures. 402 for _ in 0..50 { 403 let alloc = allocators.allocate(size2(256, 256), alloc_cb); 404 allocators.set_handle(alloc.0, alloc.1, &TextureCacheHandle::Empty); 405 allocations.push(alloc); 406 } 407 408 // Deallocate everything. 409 // It should empty all atlases and we still have textures allocated because 410 // we haven't called release_empty_textures yet. 411 for alloc in allocations.drain(..) { 412 allocators.deallocate(alloc.0, alloc.1); 413 } 414 415 // Allocate something else. 416 // Bug 1680769 was causing this allocation to be duplicated and leaked in 417 // all textures. 418 allocations.push(allocators.allocate(size2(8, 8), alloc_cb)); 419 420 // Deallocate all known allocations. 421 for alloc in allocations.drain(..) { 422 allocators.deallocate(alloc.0, alloc.1); 423 } 424 425 // If we have leaked items, this won't manage to remove all textures. 426 allocators.release_empty_textures(&mut |_| {}); 427 428 assert_eq!(allocators.allocated_textures(), 0); 429 }