sanakirja/
debug.rs

1use log::*;
2use sanakirja_core::btree::*;
3use sanakirja_core::*;
4use std::collections::HashSet;
5use std::fs::File;
6use std::io::{BufWriter, Write};
7use std::path::Path;
8
9use crate::L64;
10
11pub fn debug<
12    P: AsRef<Path>,
13    T: LoadPage,
14    K: Storable + ?Sized + std::fmt::Debug,
15    V: Storable + ?Sized + std::fmt::Debug,
16    PP: BTreePage<K, V>,
17>(
18    t: &T,
19    db: &[&Db_<K, V, PP>],
20    p: P,
21    recurse: bool,
22) where
23    T::Error: std::fmt::Debug,
24{
25    let f = File::create(p.as_ref()).unwrap();
26    let mut buf = BufWriter::new(f);
27    writeln!(&mut buf, "digraph{{").unwrap();
28    let mut h = HashSet::new();
29    for db in db {
30        print_page::<T, K, V, PP>(
31            t,
32            &mut h,
33            &mut buf,
34            &unsafe { t.load_page(db.db.into()) }.unwrap(),
35            recurse,
36        );
37    }
38    writeln!(&mut buf, "}}").unwrap();
39}
40
41fn print_page<
42    T: LoadPage,
43    K: Storable + ?Sized + std::fmt::Debug,
44    V: Storable + ?Sized + std::fmt::Debug,
45    P: BTreePage<K, V>,
46>(
47    txn: &T,
48    pages: &mut HashSet<u64>,
49    buf: &mut BufWriter<File>,
50    p: &CowPage,
51    print_children: bool,
52) where
53    T::Error: std::fmt::Debug,
54{
55    if !pages.contains(&p.offset) {
56        pages.insert(p.offset);
57
58        writeln!(
59            buf,
60            "subgraph cluster{} {{\nlabel=\"Page {}, rc \
61             {} {}\";\ncolor=black;",
62            p.offset,
63            p.offset,
64            txn.rc(p.offset).unwrap(),
65            unsafe { u64::from_le(*(p.data as *const u64).add(1)) & 0xfff }
66        )
67        .unwrap();
68        let mut h = Vec::new();
69        let mut edges = Vec::new();
70        print_cursor::<T, K, V, P>(txn, buf, &mut edges, &mut h, p);
71
72        writeln!(buf, "}}").unwrap();
73        for p in edges.iter() {
74            writeln!(buf, "{}", p).unwrap()
75        }
76        if print_children {
77            for p in h.iter() {
78                print_page::<T, K, V, P>(txn, pages, buf, &p, print_children)
79            }
80        }
81    }
82}
83
84fn print_cursor<
85    T: LoadPage,
86    K: Storable + ?Sized + std::fmt::Debug,
87    V: Storable + ?Sized + std::fmt::Debug,
88    P: BTreePage<K, V>,
89>(
90    txn: &T,
91    buf: &mut dyn Write,
92    edges: &mut Vec<String>,
93    pages: &mut Vec<CowPage>,
94    p: &CowPage,
95) where
96    T::Error: std::fmt::Debug,
97{
98    let mut cursor = P::cursor_first(p);
99    let mut i = 0;
100    let l = P::left_child(p.as_page(), &cursor);
101    if l > 0 {
102        if let Ok(page) = unsafe { txn.load_page(l) } {
103            pages.push(page);
104        }
105        edges.push(format!(
106            "n_{}_{}->n_{}_0[color=\"ForestGreen\"];",
107            p.offset, i, l
108        ))
109    }
110    while let Some((key, val, r)) = P::next(txn, p.as_page(), &mut cursor) {
111        if i > 0 {
112            writeln!(
113                buf,
114                "n_{}_{}->n_{}_{}[color=\"blue\"];",
115                p.offset,
116                i - 1,
117                p.offset,
118                i
119            )
120            .unwrap();
121        }
122        writeln!(
123            buf,
124            "n_{}_{}[label=\"{}: {:?} -> {:?}\"];",
125            p.offset, i, i, key, val
126        )
127        .unwrap();
128        if r > 0 {
129            pages.push(unsafe { txn.load_page(r).unwrap() });
130            edges.push(format!("n_{}_{}->n_{}_0[color=\"red\"];", p.offset, i, r))
131        };
132        i += 1
133    }
134}
135
136pub trait Check: core::fmt::Debug {
137    fn add_refs<T: LoadPage>(
138        &self,
139        _txn: &T,
140        _refs: &mut std::collections::BTreeMap<u64, usize>,
141    ) -> Result<(), T::Error>
142    where
143        T::Error: std::fmt::Debug,
144    {
145        Ok(())
146    }
147}
148
149impl Check for u64 {}
150impl Check for () {}
151
152impl<
153        K: Check + Ord + UnsizedStorable + ?Sized,
154        V: Check + Ord + UnsizedStorable + ?Sized,
155        P: BTreePage<K, V> + std::fmt::Debug,
156    > Check for Db_<K, V, P>
157{
158    fn add_refs<T: LoadPage>(
159        &self,
160        txn: &T,
161        pages: &mut std::collections::BTreeMap<u64, usize>,
162    ) -> Result<(), T::Error>
163    where
164        T::Error: std::fmt::Debug,
165    {
166        use std::collections::btree_map::Entry;
167        let mut stack = vec![self.db];
168        while let Some(p) = stack.pop() {
169            match pages.entry(p.into()) {
170                Entry::Vacant(e) => {
171                    debug!("add_refs: 0x{:x}", p);
172                    e.insert(1);
173                    let p = unsafe { txn.load_page(p.into())? };
174                    let mut c = P::cursor_first(&p);
175                    let l: u64 = P::left_child(p.as_page(), &c);
176                    if l > 0 {
177                        stack.push(core::num::NonZeroU64::new(l).unwrap());
178                    }
179                    let mut kv = None;
180                    while let Some((k, v, r)) = P::next(txn, p.as_page(), &mut c) {
181                        debug!("{:?} {:?} {:?}", k, v, kv);
182                        if let Some((k_, v_)) = kv {
183                            // Test whether the elements on the page are in order.
184                            debug!("{:?} {:?} {:?}", k_ > k, k_ == k, v_ > v);
185                            if k_ > k || (k_ == k && v_ > v) {
186                                debug(txn, &[self], "debug_ord", true);
187                                panic!("{:?} {:?} {:?} {:?} {:?}", kv, k_, v_, k_ > k, v_ > v);
188                            }
189                        }
190                        k.add_refs(txn, pages)?;
191                        v.add_refs(txn, pages)?;
192                        kv = Some((k, v));
193                        if r > 0 {
194                            stack.push(core::num::NonZeroU64::new(r).unwrap())
195                        }
196                    }
197                }
198                Entry::Occupied(mut e) => {
199                    e.insert(e.get() + 1);
200                }
201            }
202        }
203        Ok(())
204    }
205}
206
207type B = page::Page<L64, ()>;
208
209pub fn check_free_mut(
210    txn: &crate::MutTxn<&crate::Env>,
211    refs: &std::collections::BTreeMap<u64, usize>,
212) {
213    let db_free: Option<Db<L64, ()>> = if txn.free > 0 {
214        let db_free = unsafe { Db::from_page(txn.free) };
215        let mut curs: Cursor<_, _, B> = Cursor::new(txn, &db_free).unwrap();
216        while let Some((k, _)) = curs.next(txn).unwrap() {
217            assert!(refs.get(&k.as_u64()).is_none())
218        }
219        Some(db_free)
220    } else {
221        None
222    };
223    debug!("{:?}", db_free);
224    for (r, _) in refs.iter() {
225        assert!(*r < txn.length)
226    }
227    let env = txn.env;
228    let len = txn.length;
229
230    for i in env.roots.len() as u64..(len >> 12) {
231        let page = i << 12;
232        if refs.contains_key(&page) {
233            continue;
234        } else if let Some(ref f) = db_free {
235            if let Some((x, _)) = get(txn, f, &L64(page.to_le()), None).unwrap() {
236                if x.as_u64() == page {
237                    continue;
238                }
239            }
240        } else if txn.free_owned_pages.iter().any(|x| *x == page) {
241            continue;
242        } else if txn.free_pages.iter().any(|x| *x == page) {
243            continue;
244        }
245        panic!("page not found: 0x{:x} (total length 0x{:x})", page, len);
246    }
247}
248
249pub fn check_free<B: std::borrow::Borrow<crate::Env>>(
250    txn: &crate::Txn<B>,
251    refs: &std::collections::BTreeMap<u64, usize>,
252) {
253    let env = txn.env.borrow();
254    let (db_free, length): (Option<Db<L64, ()>>, _) = unsafe {
255        let hdr = &*(env.mmaps.lock()[0].ptr.add(txn.root * PAGE_SIZE)
256            as *const crate::environment::GlobalHeader);
257        (
258            if hdr.free_db != 0 {
259                Some(Db::from_page(u64::from_le(hdr.free_db)))
260            } else {
261                None
262            },
263            u64::from_le(hdr.length),
264        )
265    };
266    debug!("db_free: {:?}", db_free);
267    for (r, _) in refs.iter() {
268        debug!("r = 0x{:x}, length = 0x{:x}", r, length);
269        assert!(*r < length)
270    }
271    for i in env.roots.len() as u64..(length >> 12) {
272        let page = i << 12;
273        if refs.contains_key(&page) {
274            continue;
275        } else if let Some(ref f) = db_free {
276            if let Some((x, _)) = get(txn, f, &L64(page.to_le()), None).unwrap() {
277                if x.as_u64() == page {
278                    continue;
279                }
280            }
281        }
282        panic!("page not found: 0x{:x} (total length 0x{:x})", page, length);
283    }
284    if let Some(ref db_free) = db_free {
285        let mut free = HashSet::new();
286        for p in iter(txn, db_free, None).unwrap() {
287            assert!(free.insert(*p.unwrap().0))
288        }
289    }
290}
291
292pub fn add_free_refs<B: std::borrow::Borrow<crate::Env>>(
293    txn: &crate::Txn<B>,
294    pages: &mut std::collections::BTreeMap<u64, usize>,
295) -> Result<(), crate::Error> {
296    let env = txn.env.borrow();
297    unsafe {
298        let p = &*(env.mmaps.lock()[0].ptr.add(txn.root * PAGE_SIZE)
299            as *const crate::environment::GlobalHeader);
300        if p.free_db != 0 {
301            debug!("add_free_refs: free = 0x{:x}", p.free_db);
302            let free_db: Db<L64, ()> = Db::from_page(u64::from_le(p.free_db));
303            free_db.add_refs(txn, pages)?;
304        }
305        if p.rc_db != 0 {
306            debug!("add_free_refs: rc = 0x{:x}", p.rc_db);
307            let rc_db: Db<L64, ()> = Db::from_page(u64::from_le(p.rc_db));
308            rc_db.add_refs(txn, pages)?;
309        }
310    };
311    Ok(())
312}
313
314pub fn add_free_refs_mut<B: std::borrow::Borrow<crate::Env>>(
315    txn: &crate::MutTxn<B>,
316    pages: &mut std::collections::BTreeMap<u64, usize>,
317) -> Result<(), crate::Error> {
318    if txn.free != 0 {
319        debug!("add_free_refs: free = 0x{:x}", txn.free);
320        let free_db: Db<L64, ()> = unsafe { Db::from_page(txn.free) };
321        free_db.add_refs(txn, pages)?;
322    }
323    if let Some(ref rc) = txn.rc {
324        debug!("add_free_refs: rc = 0x{:x}", rc.db);
325        rc.add_refs(txn, pages)?;
326    }
327    Ok(())
328}
329
330pub fn check_refs<B: std::borrow::Borrow<crate::Env>>(
331    txn: &crate::MutTxn<B>,
332    refs: &std::collections::BTreeMap<u64, usize>,
333) {
334    for (p, r) in refs.iter() {
335        if *r >= 2 {
336            assert_eq!(txn.rc(*p).unwrap(), *r as u64);
337        } else {
338            assert_eq!(txn.rc(*p).unwrap(), 0);
339        }
340    }
341}
sanakirja/debug.rs

sanakirja/
debug.rs
