xalloc/
bitmap.rs

1//
2// Copyright 2017 yvt, all rights reserved.
3//
4// Licensed under the MIT license <LICENSE-MIT or
5// http://opensource.org/licenses/MIT>. This file may
6// not be copied, modified,or distributed except
7// according to those terms.
8//
9//! Free space bitmap-based external memory allocator.
10//!
11//! [`BitmapAlloc`] uses a simple bitmap to track the allocation state, and
12//! relies on a naïve bit scan for allocation.
13//!
14//! ## Memory Overhead
15//!
16//! Since it uses a bitmap to track free space, it consumes a memory proportional
17//! to the size of the heap. The memory consumption is estimated to be roughly
18//! `size / 8` bytes, where `size` is the size of the heap measured by the
19//! number of allocation units.
20//!
21//! `BitmapAlloc` does not store information about individual allocated regions
22//! by itself. Therefore, `BitmapAlloc` would be preferred when the number of
23//! allocations is quite high and each allocation is very small (preferably,
24//! just one allocation unit).
25//!
26//! The following table shows the memory overhead comparison between `Tlsf` and
27//! `BitmapAlloc` with a varying number of allocations (assuming the heap is
28//! fully occupied).
29//!
30//! | `size` | # of allocations | `Tlsf` (bytes) | `BitmapAloc` (bytes) |
31//! | ------ | ---------------- | -------------- | -------------------- |
32//! | 1,024  | 0                | 1,118          | 128                  |
33//! |        | 1                | 1,174          | 128                  |
34//! |        | 256              | 15,454         | 128                  |
35//! |        | 1,024            | 58,462         | 128                  |
36//! | 65,536 | 0                | 1,118          | 8,192                |
37//! |        | 1                | 1,174          | 8,192                |
38//! |        | 1,024            | 58,462         | 8,192                |
39//! |        | 65,536           | 3,671,134      | 8,192                |
40//!
41//! ## Performance
42//!
43//! The allocation throughput is roughly the same as of jemalloc.
44use bitmaputils::*;
45use int::BinaryInteger;
46use std::ops::Range;
47
48/// Free space bitmap-based external memory allocator.
49///
50/// See [the module-level documentation] for more.
51///
52/// [the module-level documentation]: index.html
53#[derive(Debug, Clone)]
54pub struct BitmapAlloc {
55    bitmap: Vec<usize>,
56    size: usize,
57    next: usize,
58}
59
60/// A handle type to a region allocated in a `BitmapAlloc`.
61///
62/// `BitmapAllocRegion` returned by a `BitmapAlloc` only can be used with the
63/// same `BitmapAlloc`.
64#[derive(Debug, PartialEq, Eq, Hash)]
65pub struct BitmapAllocRegion {
66    range: Range<usize>,
67}
68
69impl BitmapAlloc {
70    /// Construct a `BitmapAlloc`.
71    pub fn new(size: usize) -> Self {
72        let width = <usize>::max_digits() as usize;
73        Self {
74            bitmap: vec![0; (size + width - 1) / width],
75            size,
76            next: 0,
77        }
78    }
79
80    /// Alias of [`alloc_next`].
81    ///
82    /// [`alloc_next`]: #method.alloc_next
83    pub fn alloc(&mut self, size: usize) -> Option<(BitmapAllocRegion, usize)> {
84        self.alloc_next(size)
85    }
86
87    /// Allocate a region of the size `size` using a Next-Fit strategy.
88    /// The time complexity is linear to the size of the heap.
89    ///
90    /// Returns a handle of the allocated region and its offset if the
91    /// allocation succeeds. Returns `None` otherwise.
92    ///
93    /// `size` must not be zero.
94    pub fn alloc_next(&mut self, size: usize) -> Option<(BitmapAllocRegion, usize)> {
95        let next = self.next;
96        self.alloc_inner(size, next)
97            .or_else(|| self.alloc_first(size))
98    }
99
100    /// Allocate a region of the size `size` using a First-Fit strategy.
101    /// The time complexity is linear to the size of the heap.
102    ///
103    /// Returns a handle of the allocated region and its offset if the
104    /// allocation succeeds. Returns `None` otherwise.
105    ///
106    /// `size` must not be zero.
107    pub fn alloc_first(&mut self, size: usize) -> Option<(BitmapAllocRegion, usize)> {
108        self.alloc_inner(size, 0)
109    }
110
111    fn alloc_inner(&mut self, size: usize, start: usize) -> Option<(BitmapAllocRegion, usize)> {
112        assert!(size != 0);
113
114        if start + size > self.size {
115            return None;
116        }
117
118        find_zeros(&self.bitmap, start, size).and_then(|offs| {
119            let range = offs..offs + size;
120            if range.end <= self.size {
121                set_bits_ranged(&mut self.bitmap, range.clone());
122                if range.end == self.size {
123                    self.next = 0;
124                } else {
125                    self.next = range.end;
126                }
127                Some((BitmapAllocRegion { range }, offs))
128            } else {
129                None
130            }
131        })
132    }
133
134    /// Deallocate the specified region.
135    ///
136    /// `r` must originate from the same instance of `BitmapAlloc`. Otherwise,
137    /// `BitmapAlloc` enters an inconsistent state and possibly panics, but does
138    /// not cause an undefined behavior.
139    pub fn dealloc_relaxed(&mut self, r: BitmapAllocRegion) {
140        // Optimize for stack-like usage
141        if self.next == r.range.end {
142            self.next = r.range.start;
143        }
144
145        clear_bits_ranged(&mut self.bitmap, r.range);
146    }
147}
xalloc/bitmap.rs

xalloc/
bitmap.rs
