nydus_utils/
inode_bitmap.rs

1// Copyright 2020 Ant Group. All rights reserved.
2// Copyright (C) 2021 Alibaba Cloud. All rights reserved.
3//
4// SPDX-License-Identifier: Apache-2.0
5
6use std::collections::BTreeMap;
7use std::fmt::{Debug, Display, Formatter};
8use std::sync::atomic::{AtomicU64, Ordering};
9use std::sync::RwLock;
10
11#[derive(Default)]
12pub struct InodeBitmap {
13    map: RwLock<BTreeMap<u64, AtomicU64>>,
14}
15
16impl Debug for InodeBitmap {
17    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
18        f.write_str(self.to_string().as_str())
19    }
20}
21
22impl Display for InodeBitmap {
23    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
24        f.write_str(
25            serde_json::json!({"inode_range": self.bitmap_to_array()})
26                .to_string()
27                .as_str(),
28        )
29    }
30}
31
32impl InodeBitmap {
33    pub fn new() -> Self {
34        Self::default()
35    }
36
37    #[inline(always)]
38    fn get_index_and_mask(ino: u64) -> (u64, u64) {
39        (ino >> 6, 1_u64 << (ino & 0x3f_u64))
40    }
41
42    #[inline(always)]
43    fn range_to_vec(start: u64, end: u64) -> Vec<u64> {
44        if start == end {
45            vec![start]
46        } else {
47            vec![start, end]
48        }
49    }
50
51    pub fn set(&self, ino: u64) {
52        let (index, mask) = Self::get_index_and_mask(ino);
53
54        let m = self.map.read().unwrap();
55        if let Some(v) = m.get(&index) {
56            v.fetch_or(mask, Ordering::Relaxed);
57            return;
58        }
59        drop(m);
60
61        let mut m = self.map.write().unwrap();
62        m.entry(index)
63            .or_insert_with(|| AtomicU64::new(0))
64            .fetch_or(mask, Ordering::Relaxed);
65    }
66
67    pub fn is_set(&self, ino: u64) -> bool {
68        let (index, mask) = InodeBitmap::get_index_and_mask(ino);
69        self.map
70            .read()
71            .unwrap()
72            .get(&index)
73            .is_some_and(|v| v.load(Ordering::Relaxed) & mask != 0)
74    }
75
76    pub fn clear(&self, ino: u64) {
77        let (index, mask) = InodeBitmap::get_index_and_mask(ino);
78        let m = self.map.read().unwrap();
79
80        if let Some(v) = m.get(&index) {
81            v.fetch_and(!mask, Ordering::Relaxed);
82        }
83    }
84
85    pub fn clear_all(&self) {
86        let m = self.map.read().unwrap();
87
88        for it in m.values() {
89            it.store(0_u64, Ordering::Relaxed);
90        }
91    }
92
93    /// "[[1,5],[8],[10],[100,199],...]"
94    fn bitmap_to_vec(&self, load: fn(&AtomicU64) -> u64) -> Vec<Vec<u64>> {
95        let m = self.map.read().unwrap();
96        let mut ret: Vec<Vec<u64>> = Vec::new();
97        let mut start: Option<u64> = None;
98        // 0 is an invalid inode number
99        let mut last: u64 = 0;
100
101        for it in m.iter() {
102            let base = it.0 << 6;
103            let mut v = load(it.1);
104
105            while v != 0 {
106                // trailing_zeros need rustup version >= 1.46
107                let ino = base + v.trailing_zeros() as u64;
108                v &= v - 1;
109                start = match start {
110                    None => Some(ino),
111                    Some(s) => {
112                        if ino != last + 1 {
113                            ret.push(InodeBitmap::range_to_vec(s, last));
114                            Some(ino)
115                        } else {
116                            Some(s)
117                        }
118                    }
119                };
120                last = ino;
121            }
122        }
123        if let Some(s) = start {
124            ret.push(InodeBitmap::range_to_vec(s, last));
125        }
126
127        ret
128    }
129
130    pub fn bitmap_to_array(&self) -> Vec<Vec<u64>> {
131        self.bitmap_to_vec(|v| v.load(Ordering::Relaxed))
132    }
133
134    pub fn bitmap_to_array_and_clear(&self) -> Vec<Vec<u64>> {
135        self.bitmap_to_vec(|v| v.fetch_and(0_u64, Ordering::Relaxed))
136    }
137}
138
139#[cfg(test)]
140mod tests {
141    use super::*;
142
143    #[test]
144    fn test_inode_bitmap() {
145        let empty: Vec<Vec<u64>> = Vec::new();
146        let m = InodeBitmap::new();
147        m.set(1);
148        m.set(2);
149        m.set(5);
150        assert_eq!(m.bitmap_to_array(), [vec![1, 2], vec![5]]);
151
152        assert!(m.is_set(2));
153        m.clear(2);
154        assert!(!m.is_set(2));
155        assert_eq!(m.bitmap_to_array(), [[1], [5]]);
156
157        m.set(65);
158        m.set(66);
159        m.set(4000);
160        m.set(40001);
161        m.set(40002);
162        m.set(40003);
163        assert_eq!(
164            m.bitmap_to_array(),
165            [
166                vec![1],
167                vec![5],
168                vec![65, 66],
169                vec![4000],
170                vec![40001, 40003]
171            ]
172        );
173
174        m.clear_all();
175        assert_eq!(m.bitmap_to_array(), empty);
176
177        m.set(65);
178        m.set(40001);
179        assert_eq!(m.bitmap_to_array(), [vec![65], vec![40001]]);
180
181        for i in 0..100000 {
182            m.set(i);
183        }
184        m.set(100002);
185        assert_eq!(
186            m.bitmap_to_array_and_clear(),
187            [vec![0, 99999], vec![100002]]
188        );
189        assert!(!m.is_set(9000));
190        assert_eq!(m.bitmap_to_array(), empty);
191    }
192}
nydus_utils/inode_bitmap.rs

nydus_utils/
inode_bitmap.rs
