Git import holds a budget of graph memory d45dab0484ea

- **Git import holds a budget of graph memory (#25).** A long-lived file's graph keeps every line it ever had, and the import shed a kept state's graphs only past 2 000 of them; it now also sheds them past 1.5 million atoms, and gives freed memory back after each merge. A 28 637-commit slice of VS Code imports at 5.1 GB instead of 16.9 GB, in 36 minutes instead of 61, with the same verify result. The dependency check no longer memoises every queried change's whole ancestry.

/// Give pages the program has freed back to the system. glibc keeps freed

/// memory in each thread's arena; after a large merge renders thousands of

/// files on many threads, that kept memory is most of the process's size

/// (#25). Elsewhere it does nothing.

pub fn release_freed_memory() {

    #[cfg(all(target_os = "linux", target_env = "gnu"))]

    // SAFETY: malloc_trim only returns free pages to the system; it is

    // safe to call at any time from any thread.

    unsafe {

        libc::malloc_trim(0);

    }

}

/// The atoms a kept state's built graphs may hold before they go back into

/// its history (#25): about a few hundred megabytes.

const KEPT_ATOMS: usize = 1_500_000;

        // Atoms a kept state's graphs may hold before they are shed;

        // OXY_IMPORT_KEPT_ATOMS overrides it, for measuring.

        let kept_atoms: usize = std::env::var("OXY_IMPORT_KEPT_ATOMS")

            .ok()

            .and_then(|v| v.parse().ok())

            .unwrap_or(KEPT_ATOMS);

                // Past a few thousand graphs, or past a budget of atoms: a

                // long-lived file's graph keeps every line it ever had, so a

                // handful of them can hold gigabytes (#25).

                if base.built_count() > KEPT_GRAPHS || base.built_atoms() > kept_atoms {

            // A merge renders thousands of files on many threads and frees

            // it all; the allocator keeps those pages unless asked to give

            // them back, and the next merge piles on top (#25).

            let before_trim = if trace { rss_mb() } else { 0 };

            if gc.parents.len() > 1 {

                crate::alloc_stats::release_freed_memory();

            }

                    .unwrap_or(0);

                let (edits, most) = kept

                    .get(gc.sha.as_str())

                    .map(|(st, _)| st.deferred_edit_count())

                    .unwrap_or((0, 0));

                let atoms = kept

                    .get(gc.sha.as_str())

                    .map(|(st, _)| st.built_atoms())

                    "trace {done} {} parents={} base={base_how} merged={merged} built={built} atoms={atoms} kept={} shed={shed} rss_mb={} before_trim_mb={before_trim} deferred_edits={edits} most={most}",

    /// Memoised transitive dependencies, bounded by the hashes they hold

    /// (each set is the whole history below a change, so keeping one for

    /// every change asked about grew with the square of history: #25). A

    /// mutex, not a `RefCell`, so a loaded state can be shared across

    /// threads by a host that caches it.

    closure: Mutex<ClosureMemo>,

    /// Each change's level: 0 with no dependencies, else one more than its

    /// highest dependency. A change can only depend on changes of lower

    /// level, which bounds the walk [`DepOracle::depends_on`] does.

    levels: Mutex<HashMap<ChangeHash, u32>>,

/// The closures kept, and how many hashes they hold in all.

#[derive(Default)]

struct ClosureMemo {

    sets: HashMap<ChangeHash, Arc<HashSet<ChangeHash>>>,

    held: usize,

}

/// The most hashes the closure memo holds before it starts again: a few

/// hundred megabytes at most.

const CLOSURE_MEMO_HASHES: usize = 4_000_000;

            closure: Mutex::new(ClosureMemo::default()),

            levels: Mutex::new(HashMap::new()),

    /// Atoms in this state's built graphs, live and deleted: what their

    /// memory follows, since a graph keeps every line its file ever had.

    pub fn built_atoms(&self) -> usize {

        self.files.values().map(|g| g.atom_count()).sum()

    }

    /// Edits held in the deferred histories of files not built, and the

    /// most any one file holds (for measuring, #25).

    pub fn deferred_edit_count(&self) -> (usize, usize) {

        let Some(d) = self.deferred.as_ref() else {

            return (0, 0);

        };

        let mut total = 0;

        let mut most = 0;

        for v in d.values() {

            let n: usize = v.body().edits.iter().map(|(_, e)| e.len()).sum();

            total += n;

            most = most.max(n);

        }

        (total, most)

    }

        {

            let mut m = self.closure.lock().unwrap();

            m.sets.clear();

            m.held = 0;

        }

        if let Some(c) = self.closure.lock().unwrap().sets.get(h) {

        let mut memo = self.closure.lock().unwrap();

        if memo.held + rc.len() > CLOSURE_MEMO_HASHES {

            memo.sets.clear();

            memo.held = 0;

        }

        memo.held += rc.len();

        memo.sets.insert(*h, rc.clone());

    /// `h`'s level (see `levels`), worked out for it and its ancestors not

    /// yet known, without recursion: histories are deeper than a stack. An

    /// unknown change has level 0.

    fn level(&self, h: &ChangeHash) -> u32 {

        let mut levels = self.levels.lock().unwrap();

        if let Some(l) = levels.get(h) {

            return *l;

        }

        let mut stack: Vec<(ChangeHash, bool)> = vec![(*h, false)];

        while let Some((c, expanded)) = stack.pop() {

            if levels.contains_key(&c) {

                continue;

            }

            let deps: &[ChangeHash] = self

                .changes

                .get(&c)

                .map(|m| m.deps.as_slice())

                .unwrap_or(&[]);

            if expanded {

                let l = deps

                    .iter()

                    .map(|d| levels.get(d).map_or(0, |l| l + 1))

                    .max()

                    .unwrap_or(0);

                levels.insert(c, l);

            } else {

                stack.push((c, true));

                for d in deps {

                    if !levels.contains_key(d) {

                        stack.push((*d, false));

                    }

                }

            }

        }

        levels[h]

    }

    /// Whether `a` depends on `b`, by a walk down from `a` that stops at

    /// changes no higher than `b`: they cannot have `b` below them. Nothing

    /// of the walk is kept, so asking about many pairs costs no more memory

    /// than one walk (#25); a closure already memoised answers at once.

        if a == b {

            return true;

        }

        if let Some(c) = self.closure.lock().unwrap().sets.get(a) {

            return c.contains(b);

        }

        if !self.changes.contains_key(b) {

            return false;

        }

        let lb = self.level(b);

        if self.level(a) <= lb {

            return false;

        }

        let mut seen: HashSet<ChangeHash> = HashSet::new();

        let mut stack: Vec<ChangeHash> = self

            .changes

            .get(a)

            .map(|m| m.deps.clone())

            .unwrap_or_default();

        while let Some(c) = stack.pop() {

            if c == *b {

                return true;

            }

            if !seen.insert(c) || self.level(&c) <= lb {

                continue;

            }

            if let Some(m) = self.changes.get(&c) {

                stack.extend(m.deps.iter().copied());

            }

        }

        false

    }

    /// The bounded walk of `depends_on` agrees with the closure on random

    /// graphs, and the memo stays within its bound.

    #[test]

    fn depends_on_matches_the_closure() {

        use rand::{Rng, SeedableRng};

        let mut rng = rand::rngs::StdRng::seed_from_u64(11);

        for _ in 0..10 {

            let mut st = State::new();

            let mut all: Vec<ChangeHash> = Vec::new();

            for _ in 0..80 {

                let deps: Vec<ChangeHash> =

                    all.iter().copied().filter(|_| rng.gen_bool(0.06)).collect();

                all.push(st.add(change(deps, vec![], vec![])).unwrap());

            }

            let unknown = ObjectRef([0xee; 32]);

            for a in &all {

                let want = st.closure(a).clone();

                st.closure.lock().unwrap().sets.clear();

                st.closure.lock().unwrap().held = 0;

                for b in all.iter().chain([&unknown]) {

                    assert_eq!(

                        st.depends_on(a, b),

                        a == b || want.contains(b),

                        "{a:?} on {b:?}"

                    );

                }

            }

            assert!(st.closure.lock().unwrap().held <= CLOSURE_MEMO_HASHES);

        }