redb/tree_store/page_store/
layout.rs

Help
1use crate::tree_store::page_store::region::RegionHeader;
2use std::ops::Range;
3
4fn round_up_to_multiple_of(value: u64, multiple: u64) -> u64 {
5    if value % multiple == 0 {
6        value
7    } else {
8        value + multiple - value % multiple
9    }
10}
11
12// Regions are laid out starting with the allocator state header, followed by the pages aligned
13// to the next page
14#[derive(Clone, Copy, Debug, Eq, PartialEq)]
15pub(super) struct RegionLayout {
16    num_pages: u32,
17    // Offset where data pages start
18    header_pages: u32,
19    page_size: u32,
20}
21
22impl RegionLayout {
23    pub(super) fn new(num_pages: u32, header_pages: u32, page_size: u32) -> Self {
24        assert!(num_pages > 0);
25        Self {
26            num_pages,
27            header_pages,
28            page_size,
29        }
30    }
31
32    pub(super) fn calculate(
33        desired_usable_bytes: u64,
34        page_capacity: u32,
35        page_size: u32,
36    ) -> RegionLayout {
37        assert!(desired_usable_bytes <= u64::from(page_capacity) * u64::from(page_size));
38        let header_pages = RegionHeader::header_pages_expensive(page_size, page_capacity);
39        let num_pages =
40            round_up_to_multiple_of(desired_usable_bytes, page_size.into()) / u64::from(page_size);
41
42        Self {
43            num_pages: num_pages.try_into().unwrap(),
44            header_pages,
45            page_size,
46        }
47    }
48
49    fn full_region_layout(page_capacity: u32, page_size: u32) -> RegionLayout {
50        let header_pages = RegionHeader::header_pages_expensive(page_size, page_capacity);
51
52        Self {
53            num_pages: page_capacity,
54            header_pages,
55            page_size,
56        }
57    }
58
59    pub(super) fn data_section(&self) -> Range<u64> {
60        let header_bytes = u64::from(self.header_pages) * u64::from(self.page_size);
61        header_bytes..(header_bytes + self.usable_bytes())
62    }
63
64    pub(super) fn get_header_pages(&self) -> u32 {
65        self.header_pages
66    }
67
68    pub(super) fn num_pages(&self) -> u32 {
69        self.num_pages
70    }
71
72    pub(super) fn page_size(&self) -> u32 {
73        self.page_size
74    }
75
76    pub(super) fn len(&self) -> u64 {
77        u64::from(self.header_pages) * u64::from(self.page_size) + self.usable_bytes()
78    }
79
80    pub(super) fn usable_bytes(&self) -> u64 {
81        u64::from(self.page_size) * u64::from(self.num_pages)
82    }
83}
84
85#[derive(Clone, Copy, Debug)]
86pub(crate) struct DatabaseLayout {
87    full_region_layout: RegionLayout,
88    num_full_regions: u32,
89    trailing_partial_region: Option<RegionLayout>,
90}
91
92impl DatabaseLayout {
93    pub(super) fn new(
94        full_regions: u32,
95        full_region: RegionLayout,
96        trailing_region: Option<RegionLayout>,
97    ) -> Self {
98        Self {
99            full_region_layout: full_region,
100            num_full_regions: full_regions,
101            trailing_partial_region: trailing_region,
102        }
103    }
104
105    pub(super) fn reduce_last_region(&mut self, pages: u32) {
106        if let Some(ref mut trailing) = self.trailing_partial_region {
107            assert!(pages <= trailing.num_pages);
108            trailing.num_pages -= pages;
109            if trailing.num_pages == 0 {
110                self.trailing_partial_region = None;
111            }
112        } else {
113            self.num_full_regions -= 1;
114            let full_layout = self.full_region_layout;
115            if full_layout.num_pages > pages {
116                self.trailing_partial_region = Some(RegionLayout::new(
117                    full_layout.num_pages - pages,
118                    full_layout.header_pages,
119                    full_layout.page_size,
120                ));
121            }
122        }
123    }
124
125    pub(super) fn recalculate(
126        file_len: u64,
127        region_header_pages_u32: u32,
128        region_max_data_pages_u32: u32,
129        page_size_u32: u32,
130    ) -> Self {
131        let page_size = u64::from(page_size_u32);
132        let region_header_pages = u64::from(region_header_pages_u32);
133        let region_max_data_pages = u64::from(region_max_data_pages_u32);
134        // Super-header
135        let mut remaining = file_len - page_size;
136        let full_region_size = (region_header_pages + region_max_data_pages) * page_size;
137        let full_regions = remaining / full_region_size;
138        remaining -= full_regions * full_region_size;
139        let trailing = if remaining >= (region_header_pages + 1) * page_size {
140            remaining -= region_header_pages * page_size;
141            let remaining: u32 = remaining.try_into().unwrap();
142            let data_pages = remaining / page_size_u32;
143            assert!(data_pages < region_max_data_pages_u32);
144            Some(RegionLayout::new(
145                data_pages,
146                region_header_pages_u32,
147                page_size_u32,
148            ))
149        } else {
150            None
151        };
152        let full_layout = RegionLayout::new(
153            region_max_data_pages_u32,
154            region_header_pages_u32,
155            page_size_u32,
156        );
157
158        Self {
159            full_region_layout: full_layout,
160            num_full_regions: full_regions.try_into().unwrap(),
161            trailing_partial_region: trailing,
162        }
163    }
164
165    pub(super) fn calculate(desired_usable_bytes: u64, page_capacity: u32, page_size: u32) -> Self {
166        let full_region_layout = RegionLayout::full_region_layout(page_capacity, page_size);
167        if desired_usable_bytes <= full_region_layout.usable_bytes() {
168            // Single region layout
169            let region_layout =
170                RegionLayout::calculate(desired_usable_bytes, page_capacity, page_size);
171            DatabaseLayout {
172                full_region_layout,
173                num_full_regions: 0,
174                trailing_partial_region: Some(region_layout),
175            }
176        } else {
177            // Multi region layout
178            let full_regions = desired_usable_bytes / full_region_layout.usable_bytes();
179            let remaining_desired =
180                desired_usable_bytes - full_regions * full_region_layout.usable_bytes();
181            assert!(full_regions > 0);
182            let trailing_region = if remaining_desired > 0 {
183                Some(RegionLayout::calculate(
184                    remaining_desired,
185                    page_capacity,
186                    page_size,
187                ))
188            } else {
189                None
190            };
191            if let Some(ref region) = trailing_region {
192                // All regions must have the same header size
193                assert_eq!(region.header_pages, full_region_layout.header_pages);
194            }
195            DatabaseLayout {
196                full_region_layout,
197                num_full_regions: full_regions.try_into().unwrap(),
198                trailing_partial_region: trailing_region,
199            }
200        }
201    }
202
203    pub(super) fn full_region_layout(&self) -> &RegionLayout {
204        &self.full_region_layout
205    }
206
207    pub(super) fn trailing_region_layout(&self) -> Option<&RegionLayout> {
208        self.trailing_partial_region.as_ref()
209    }
210
211    pub(super) fn num_full_regions(&self) -> u32 {
212        self.num_full_regions
213    }
214
215    pub(super) fn num_regions(&self) -> u32 {
216        if self.trailing_partial_region.is_some() {
217            self.num_full_regions + 1
218        } else {
219            self.num_full_regions
220        }
221    }
222
223    pub(super) fn len(&self) -> u64 {
224        let last = self.num_regions() - 1;
225        self.region_base_address(last) + self.region_layout(last).len()
226    }
227
228    pub(super) fn usable_bytes(&self) -> u64 {
229        let trailing = self
230            .trailing_partial_region
231            .as_ref()
232            .map(RegionLayout::usable_bytes)
233            .unwrap_or_default();
234        u64::from(self.num_full_regions) * self.full_region_layout.usable_bytes() + trailing
235    }
236
237    pub(super) fn region_base_address(&self, region: u32) -> u64 {
238        assert!(region < self.num_regions());
239        u64::from(self.full_region_layout.page_size())
240            + u64::from(region) * self.full_region_layout.len()
241    }
242
243    pub(super) fn region_layout(&self, region: u32) -> RegionLayout {
244        assert!(region < self.num_regions());
245        if region == self.num_full_regions {
246            self.trailing_partial_region.unwrap()
247        } else {
248            self.full_region_layout
249        }
250    }
251}
252
253#[cfg(test)]
254mod test {
255    use crate::tree_store::page_store::layout::RegionLayout;
256
257    #[test]
258    fn full_layout() {
259        let layout = RegionLayout::full_region_layout(512, 4096);
260        assert_eq!(layout.num_pages, 512);
261        assert_eq!(layout.page_size, 4096);
262    }
263}
redb/tree_store/page_store/layout.rs

redb/tree_store/page_store/
layout.rs
