webrender/texture_pack/
mod.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
5mod guillotine;
6use crate::texture_cache::TextureCacheHandle;
7use crate::internal_types::FastHashMap;
8pub 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
14use api::units::*;
15use crate::internal_types::CacheTextureId;
16use euclid::{point2, size2, default::Box2D};
17use smallvec::SmallVec;
18
19pub use etagere::AllocatorOptions as ShelfAllocatorOptions;
20pub use etagere::BucketedAtlasAllocator as BucketedShelfAllocator;
21pub 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))]
27pub struct AllocId(pub u32);
28
29pub 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
48pub 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))]
69struct 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))]
81pub 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
88impl<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
218impl<Allocator: AtlasAllocator, TextureParameters> AtlasAllocatorList<TextureParameters> 
219for 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
245impl 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
275impl 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
305pub 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
314impl<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]
385fn 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}
webrender/texture_pack/mod.rs

webrender/texture_pack/
mod.rs
