alice.pds.demo.boltless.dev
This repository has no description
1use super::DecodeEntry;
2
3#[cfg(feature = "pack-cache-lru-dynamic")]
4mod memory {
5 use std::num::NonZeroUsize;
6
7 use clru::WeightScale;
8
9 use super::DecodeEntry;
10 use crate::cache::set_vec_to_slice;
11
12 struct Entry {
13 data: Vec<u8>,
14 kind: gix_object::Kind,
15 compressed_size: usize,
16 }
17
18 type Key = (u32, u64);
19 struct CustomScale;
20
21 impl WeightScale<Key, Entry> for CustomScale {
22 fn weight(&self, _key: &Key, value: &Entry) -> usize {
23 value.data.len()
24 }
25 }
26
27 /// An LRU cache with hash map backing and an eviction rule based on the memory usage for object data in bytes.
28 pub struct MemoryCappedHashmap {
29 inner: clru::CLruCache<Key, Entry, std::collections::hash_map::RandomState, CustomScale>,
30 free_list: Vec<Vec<u8>>,
31 debug: gix_features::cache::Debug,
32 }
33
34 impl MemoryCappedHashmap {
35 /// Return a new instance which evicts least recently used items if it uses more than `memory_cap_in_bytes`
36 /// object data.
37 pub fn new(memory_cap_in_bytes: usize) -> MemoryCappedHashmap {
38 MemoryCappedHashmap {
39 inner: clru::CLruCache::with_config(
40 clru::CLruCacheConfig::new(
41 NonZeroUsize::new(memory_cap_in_bytes).expect("non zero"),
42 )
43 .with_scale(CustomScale),
44 ),
45 free_list: Vec::new(),
46 debug: gix_features::cache::Debug::new(format!(
47 "MemoryCappedHashmap({memory_cap_in_bytes}B)"
48 )),
49 }
50 }
51 }
52
53 impl DecodeEntry for MemoryCappedHashmap {
54 fn put(
55 &mut self,
56 pack_id: u32,
57 offset: u64,
58 data: &[u8],
59 kind: gix_object::Kind,
60 compressed_size: usize,
61 ) {
62 self.debug.put();
63 let Some(data) = set_vec_to_slice(self.free_list.pop().unwrap_or_default(), data)
64 else {
65 return;
66 };
67 let res = self.inner.put_with_weight(
68 (pack_id, offset),
69 Entry {
70 data,
71 kind,
72 compressed_size,
73 },
74 );
75 match res {
76 Ok(Some(previous_entry)) => self.free_list.push(previous_entry.data),
77 Ok(None) => {}
78 Err((_key, value)) => self.free_list.push(value.data),
79 }
80 }
81
82 fn get(
83 &mut self,
84 pack_id: u32,
85 offset: u64,
86 out: &mut Vec<u8>,
87 ) -> Option<(gix_object::Kind, usize)> {
88 let res = self.inner.get(&(pack_id, offset)).and_then(|e| {
89 set_vec_to_slice(out, &e.data)?;
90 Some((e.kind, e.compressed_size))
91 });
92 if res.is_some() {
93 self.debug.hit();
94 } else {
95 self.debug.miss();
96 }
97 res
98 }
99 }
100}
101
102#[cfg(feature = "pack-cache-lru-dynamic")]
103pub use memory::MemoryCappedHashmap;
104
105#[cfg(feature = "pack-cache-lru-static")]
106mod _static {
107 use super::DecodeEntry;
108 use crate::cache::set_vec_to_slice;
109 struct Entry {
110 pack_id: u32,
111 offset: u64,
112 data: Vec<u8>,
113 kind: gix_object::Kind,
114 compressed_size: usize,
115 }
116
117 /// A cache using a least-recently-used implementation capable of storing the `SIZE` most recent objects.
118 /// The cache must be small as the search is 'naive' and the underlying data structure is a linked list.
119 /// Values of 64 seem to improve performance.
120 pub struct StaticLinkedList<const SIZE: usize> {
121 inner: uluru::LRUCache<Entry, SIZE>,
122 last_evicted: Vec<u8>,
123 debug: gix_features::cache::Debug,
124 /// the amount of bytes we are currently holding, taking into account the capacities of all Vecs we keep.
125 mem_used: usize,
126 /// The total amount of memory we should be able to hold with all entries combined.
127 mem_limit: usize,
128 }
129
130 impl<const SIZE: usize> StaticLinkedList<SIZE> {
131 /// Create a new list with a memory limit of `mem_limit` in bytes. If 0, there is no memory limit.
132 pub fn new(mem_limit: usize) -> Self {
133 StaticLinkedList {
134 inner: Default::default(),
135 last_evicted: Vec::new(),
136 debug: gix_features::cache::Debug::new(format!("StaticLinkedList<{SIZE}>")),
137 mem_used: 0,
138 mem_limit: if mem_limit == 0 {
139 usize::MAX
140 } else {
141 mem_limit
142 },
143 }
144 }
145 }
146
147 impl<const SIZE: usize> Default for StaticLinkedList<SIZE> {
148 fn default() -> Self {
149 Self::new(96 * 1024 * 1024)
150 }
151 }
152
153 impl<const SIZE: usize> DecodeEntry for StaticLinkedList<SIZE> {
154 fn put(
155 &mut self,
156 pack_id: u32,
157 offset: u64,
158 data: &[u8],
159 kind: gix_object::Kind,
160 compressed_size: usize,
161 ) {
162 // We cannot possibly hold this much.
163 if data.len() > self.mem_limit {
164 return;
165 }
166 // If we could hold it but are at limit, all we can do is make space.
167 let mem_free = self.mem_limit - self.mem_used;
168 if data.len() > mem_free {
169 // prefer freeing free-lists instead of clearing our cache
170 let free_list_cap = self.last_evicted.len();
171 self.last_evicted = Vec::new();
172 // still not enough? clear everything
173 if data.len() > mem_free + free_list_cap {
174 self.inner.clear();
175 self.mem_used = 0;
176 } else {
177 self.mem_used -= free_list_cap;
178 }
179 }
180 self.debug.put();
181 let mut v = std::mem::take(&mut self.last_evicted);
182 self.mem_used -= v.capacity();
183 if set_vec_to_slice(&mut v, data).is_none() {
184 return;
185 }
186 self.mem_used += v.capacity();
187 if let Some(previous) = self.inner.insert(Entry {
188 offset,
189 pack_id,
190 data: v,
191 kind,
192 compressed_size,
193 }) {
194 // No need to adjust capacity as we already counted it.
195 self.last_evicted = previous.data;
196 }
197 }
198
199 fn get(
200 &mut self,
201 pack_id: u32,
202 offset: u64,
203 out: &mut Vec<u8>,
204 ) -> Option<(gix_object::Kind, usize)> {
205 let res = self.inner.lookup(|e: &mut Entry| {
206 if e.pack_id == pack_id && e.offset == offset {
207 set_vec_to_slice(&mut *out, &e.data)?;
208 Some((e.kind, e.compressed_size))
209 } else {
210 None
211 }
212 });
213 if res.is_some() {
214 self.debug.hit();
215 } else {
216 self.debug.miss();
217 }
218 res
219 }
220 }
221
222 #[cfg(test)]
223 mod tests {
224 use super::*;
225
226 #[test]
227 fn no_limit() {
228 let c = StaticLinkedList::<10>::new(0);
229 assert_eq!(
230 c.mem_limit,
231 usize::MAX,
232 "zero is automatically turned into a large limit that is equivalent to unlimited"
233 );
234 }
235
236 #[test]
237 fn journey() {
238 let mut c = StaticLinkedList::<10>::new(100);
239 assert_eq!(c.mem_limit, 100);
240 assert_eq!(c.mem_used, 0);
241
242 // enough memory for normal operation
243 let mut last_mem_used = 0;
244 for _ in 0..10 {
245 c.put(0, 0, &[0], gix_object::Kind::Blob, 1);
246 assert!(c.mem_used > last_mem_used);
247 last_mem_used = c.mem_used;
248 }
249 assert_eq!(c.mem_used, 80, "there is a minimal vec size");
250 assert_eq!(c.inner.len(), 10);
251 assert_eq!(c.last_evicted.len(), 0);
252
253 c.put(
254 0,
255 0,
256 &(0..20).collect::<Vec<_>>(),
257 gix_object::Kind::Blob,
258 1,
259 );
260 assert_eq!(c.inner.len(), 10);
261 assert_eq!(c.mem_used, 80 + 20);
262 assert_eq!(c.last_evicted.len(), 1);
263
264 c.put(
265 0,
266 0,
267 &(0..50).collect::<Vec<_>>(),
268 gix_object::Kind::Blob,
269 1,
270 );
271 assert_eq!(c.inner.len(), 1, "cache clearance wasn't necessary");
272 assert_eq!(c.last_evicted.len(), 0, "the free list was cleared");
273 assert_eq!(c.mem_used, 50);
274
275 c.put(
276 0,
277 0,
278 &(0..101).collect::<Vec<_>>(),
279 gix_object::Kind::Blob,
280 1,
281 );
282 assert_eq!(
283 c.inner.len(),
284 1,
285 "objects that won't ever fit within the memory limit are ignored"
286 );
287 }
288 }
289}
290
291#[cfg(feature = "pack-cache-lru-static")]
292pub use _static::StaticLinkedList;