gix-mailmap: Quadratic .mailmap parsing in Snapshot::from_bytes allows a CPU denial of service

Summary

Building a Snapshot from a .mailmap file is quadratic in the number of entries. Snapshot::from_bytes parses each line and inserts it into a Vec that is kept sorted, using binary_search_by to find the position and then Vec::insert to place it. The search is fast but the insert shifts every following element, so a file whose keys are ordered to always land at the front costs O(n²) element moves overall.

A .mailmap lives at the root of a repository and its contents are set by whoever authored the repo. Any tool that resolves author identities through gitoxide (log, blame, shortlog) loads it, so a crafted file turns a normal operation on an untrusted repository into a long CPU burn on a single core.

Proof of concept

// Cargo.toml:  gix-mailmap = "=0.34.1"
use std::time::Instant;

fn main() {
    let n = 100_000;
    // One mapping per line, counting down so each new email sorts
    // before every entry already stored, forcing an insert at index 0.
    let mut mailmap = String::new();
    for i in (0..n).rev() {
        mailmap.push_str(&format!("Name <e{i:09}@x>\n"));
    }
    let start = Instant::now();
    let snapshot = gix_mailmap::Snapshot::from_bytes(mailmap.as_bytes());
    println!("{} entries in {:?}", snapshot.iter().count(), start.elapsed());
}

Measured on release builds against the published crate:

n =  20000  (0.4 MB)   1.1 s
n =  50000  (1.0 MB)   7.1 s
n = 100000  (2.0 MB)  30.0 s

The same entries in ascending order (each appended at the end, no shift) parse in 0.12 s at n = 100000, which isolates the cost to the insert rather than the parse. Doubling n quadruples the time.

Impact

One crafted .mailmap of a few megabytes pins a core for tens of seconds; because the cost is quadratic, ~10 MB reaches the order of ten minutes. The memory stays linear, so this is CPU only. It matters most where gitoxide processes repositories it did not author, for example a hosting or analysis service that runs blame or shortlog on user-supplied repos, where one repository blocks a worker. For an interactive CLI the effect is a recoverable hang.

git's own C mailmap loader collects the entries and sorts once, so this scaling is specific to gitoxide.