gc.py python
581 lines 22.4 KB
Raw
sha256:cf6265cea8c21d9228d90dec13ef6ec2dab5103d466db9cc4590681832de4bf8 docs(KD-STAGING): sync governance after KD-6b DONE Human 13 days ago
1 """Garbage collection — prune unreachable objects from the object store.
2
3 Muse uses a content-addressed object store: every file snapshot is stored as a
4 SHA-256-addressed blob under ``.muse/objects/``. Over time, after branch
5 deletions, rebases, and abandoned experiments, objects that are no longer
6 reachable from any live commit accumulate. This module identifies and removes
7 them.
8
9 Reachability
10 ------------
11 An object is *reachable* if it can be reached by following the graph from any
12 live ref (branch HEAD, tag, or the current HEAD):
13
14 branch HEAD → CommitRecord → SnapshotRecord → manifest → object SHA-256
15
16 Any object not in the reachable set is *loose garbage* and is safe to delete.
17
18 ``--full`` mode
19 ---------------
20 By default ``muse gc`` only prunes file-content blobs (``.muse/objects/``).
21 With ``--full`` it also prunes:
22
23 - Orphaned commit records (``.muse/commits/*.msgpack``) — commits not reachable
24 from any live branch ref or tag by following ``parent_commit_id`` links.
25 - Orphaned snapshot manifests (``.muse/snapshots/*.msgpack``) — snapshots not
26 referenced by any reachable commit.
27
28 This mirrors ``git prune`` / ``git gc``, which removes all unreachable loose
29 objects regardless of type.
30
31 Safety
32 ------
33 The GC walk is always performed **before** any deletion. The ``dry_run``
34 option shows what *would* be deleted without touching the store, making it safe
35 to run frequently in CI or by agents to estimate bloat.
36
37 A ``grace_period_seconds`` guard (default 30 s) prevents deleting objects that
38 were written within the last N seconds. This closes the TOCTOU window where a
39 concurrent ``muse commit`` has written a blob to the object store but not yet
40 created the commit record — without the grace period, GC would see the blob as
41 unreachable and delete it mid-commit, causing data loss.
42
43 Symlink safety
44 --------------
45 Every prefix directory and object file is checked with ``is_symlink()`` before
46 being treated as a real object. A crafted symlink inside ``.muse/objects/``
47 cannot cause GC to read or delete files outside the repository.
48
49 Return value
50 ------------
51 ``GcResult`` is a typed dataclass with integer counts and the list of collected
52 IDs. The CLI command renders it; the plumbing layer can expose it as JSON.
53 """
54
55 from __future__ import annotations
56
57 import json
58 import logging
59 import pathlib
60 import time
61 from collections import deque
62 from dataclasses import dataclass, field
63
64 import msgpack
65
66 from muse.core.store import get_all_commits, read_snapshot
67
68 logger = logging.getLogger(__name__)
69
70 # Maximum size of stash.json we will read during the reachability walk.
71 # This mirrors the cap in muse/cli/commands/stash.py.
72 _MAX_STASH_BYTES: int = 64 * 1024 * 1024 # 64 MiB
73
74 # Default number of seconds to protect recently-written objects from GC.
75 # See the "Safety" section of the module docstring.
76 _DEFAULT_GRACE_PERIOD_SECONDS: int = 30
77
78
79 # ---------------------------------------------------------------------------
80 # Result type
81 # ---------------------------------------------------------------------------
82
83
84 @dataclass
85 class GcResult:
86 """Statistics from one garbage-collection pass."""
87
88 # Blob store (.muse/objects/)
89 reachable_count: int = 0
90 collected_count: int = 0
91 collected_bytes: int = 0
92
93 # Commit store (.muse/commits/) — populated only with --full
94 commits_reachable: int = 0
95 commits_collected: int = 0
96 commits_collected_bytes: int = 0
97
98 # Snapshot store (.muse/snapshots/) — populated only with --full
99 snapshots_reachable: int = 0
100 snapshots_collected: int = 0
101 snapshots_collected_bytes: int = 0
102
103 elapsed_seconds: float = 0.0
104 grace_period_seconds: int = _DEFAULT_GRACE_PERIOD_SECONDS
105 collected_ids: list[str] = field(default_factory=list)
106 dry_run: bool = False
107 full: bool = False
108
109
110 # ---------------------------------------------------------------------------
111 # Reachability walk — blobs (conservative: all commits in store)
112 # ---------------------------------------------------------------------------
113
114
115 def _collect_reachable_objects(
116 repo_root: pathlib.Path,
117 ) -> set[str]:
118 """Return the set of all object SHA-256 IDs reachable from any live ref.
119
120 Uses the conservative walk (all commits in the store) so that orphaned
121 commits don't cause their blobs to be deleted when ``--full`` is not set.
122
123 Sources walked:
124
125 - Every snapshot file stored in ``.muse/snapshots/`` — raw manifest values
126 are read without hash verification so that objects are retained even when
127 a commit's ``snapshot_id`` field is corrupt (bit-flip or earlier store bug).
128 This is conservative: orphaned snapshots (not referenced by any commit)
129 keep their objects alive until they themselves are pruned by ``muse gc
130 --full``.
131 - Every entry in ``.muse/stash.json`` (stashed work writes objects before
132 the stash entry is committed, so they would otherwise be GCed).
133
134 The stash file is protected by a symlink guard and a size cap to match the
135 defences in ``muse stash`` itself.
136 """
137 reachable: set[str] = set()
138
139 # ── All snapshot files (raw, no hash verification) ────────────────────────
140 # Reading raw manifests (bypassing _verify_snapshot_id) is intentional here:
141 # GC must never delete an object that is referenced in ANY snapshot on disk,
142 # even a corrupt or orphaned one. If we relied on read_snapshot (which
143 # verifies the hash), a commit with a corrupt snapshot_id field pointing to a
144 # non-existent snapshot would cause its objects to be silently GCed.
145 snapshots_dir = repo_root / ".muse" / "snapshots"
146 if snapshots_dir.is_dir():
147 for snap_path in snapshots_dir.glob("*.msgpack"):
148 # Symlink guard: skip symlinks to prevent traversal attacks.
149 if snap_path.is_symlink():
150 logger.warning("⚠️ gc: skipping symlink snapshot file %s", snap_path.name)
151 continue
152 try:
153 raw_data = msgpack.unpackb(snap_path.read_bytes(), raw=False)
154 manifest = raw_data.get("manifest", {})
155 if isinstance(manifest, dict):
156 for oid in manifest.values():
157 if isinstance(oid, str) and oid:
158 reachable.add(oid)
159 except Exception as exc:
160 logger.debug("gc: could not read snapshot %s — skipped: %s", snap_path.name, exc)
161
162 # ── Stash ─────────────────────────────────────────────────────────────────
163 _collect_stash_objects(repo_root, reachable)
164
165 return reachable
166
167
168 def _collect_stash_objects(repo_root: pathlib.Path, reachable: set[str]) -> None:
169 """Add object IDs from stash.json into *reachable* in-place."""
170 stash_path = repo_root / ".muse" / "stash.json"
171 if not stash_path.exists():
172 return
173 if stash_path.is_symlink():
174 logger.warning("⚠️ .muse/stash.json is a symlink — skipping during GC walk")
175 return
176 try:
177 size = stash_path.stat().st_size
178 if size > _MAX_STASH_BYTES:
179 logger.warning(
180 "⚠️ .muse/stash.json is %.1f MiB — exceeds cap; skipping stash walk",
181 size / (1024 * 1024),
182 )
183 return
184 entries = json.loads(stash_path.read_text(encoding="utf-8"))
185 if isinstance(entries, list):
186 for entry in entries:
187 if isinstance(entry, dict):
188 manifest = entry.get("manifest")
189 if isinstance(manifest, dict):
190 for object_id in manifest.values():
191 if isinstance(object_id, str):
192 reachable.add(object_id)
193 except (OSError, json.JSONDecodeError) as exc:
194 logger.warning("⚠️ Could not read stash.json during GC walk: %s", exc)
195
196
197 # ---------------------------------------------------------------------------
198 # Reachability walk — commits + snapshots (for --full)
199 # ---------------------------------------------------------------------------
200
201
202 def _collect_reachable_commits(repo_root: pathlib.Path) -> set[str]:
203 """Return all commit IDs reachable from any live branch ref or tag.
204
205 Walks ``parent_commit_id`` and ``parent2_commit_id`` links in each commit
206 record (read as raw msgpack to survive any schema evolution). Corrupt or
207 missing files are skipped with a warning — they are not added to the
208 reachable set but are also not deleted (the grace period covers the window).
209 """
210 reachable: set[str] = set()
211 commits_dir = repo_root / ".muse" / "commits"
212 if not commits_dir.exists():
213 return reachable
214
215 # Collect all live tips: branch refs + tags
216 tips: list[str] = []
217 refs_dir = repo_root / ".muse" / "refs" / "heads"
218 if refs_dir.exists():
219 for ref_path in refs_dir.rglob("*"):
220 if ref_path.is_file() and not ref_path.is_symlink():
221 tip = ref_path.read_text().strip()
222 if tip:
223 tips.append(tip)
224
225 tags_dir = repo_root / ".muse" / "tags"
226 if tags_dir.exists():
227 for tag_path in tags_dir.glob("*.msgpack"):
228 if tag_path.is_symlink() or not tag_path.is_file():
229 continue
230 try:
231 tag_data = msgpack.unpackb(tag_path.read_bytes(), raw=False)
232 cid = tag_data.get("commit_id") or tag_data.get("target")
233 if cid:
234 tips.append(cid)
235 except Exception:
236 pass
237
238 # BFS through parent links
239 queue: deque[str] = deque(tips)
240 while queue:
241 cid = queue.popleft()
242 if cid in reachable:
243 continue
244 reachable.add(cid)
245
246 commit_path = commits_dir / f"{cid}.msgpack"
247 if not commit_path.exists() or commit_path.is_symlink():
248 continue
249 try:
250 data = msgpack.unpackb(commit_path.read_bytes(), raw=False)
251 except Exception as exc:
252 logger.warning("⚠️ Could not read commit %s during GC walk: %s", cid[:12], exc)
253 continue
254
255 p1 = data.get("parent_commit_id")
256 p2 = data.get("parent2_commit_id")
257 if p1:
258 queue.append(p1)
259 if p2:
260 queue.append(p2)
261
262 return reachable
263
264
265 def _collect_reachable_snapshots(
266 repo_root: pathlib.Path,
267 reachable_commits: set[str],
268 ) -> tuple[set[str], set[str]]:
269 """Return ``(reachable_snapshot_ids, reachable_object_ids)`` from reachable commits.
270
271 Also folds in any snapshot IDs referenced by stash entries.
272 """
273 reachable_snaps: set[str] = set()
274 reachable_objs: set[str] = set()
275 commits_dir = repo_root / ".muse" / "commits"
276
277 for cid in reachable_commits:
278 commit_path = commits_dir / f"{cid}.msgpack"
279 if not commit_path.exists() or commit_path.is_symlink():
280 continue
281 try:
282 data = msgpack.unpackb(commit_path.read_bytes(), raw=False)
283 except Exception:
284 continue
285 snap_id = data.get("snapshot_id")
286 if not snap_id:
287 continue
288 reachable_snaps.add(snap_id)
289 snap = read_snapshot(repo_root, snap_id)
290 if snap is not None:
291 for object_id in snap.manifest.values():
292 reachable_objs.add(object_id)
293 else:
294 # read_snapshot returned None — the snapshot file may be corrupt
295 # (hash verification failed) but still contains valid object IDs.
296 # Read the raw manifest without verification to retain its objects:
297 # it is always safer to keep objects than to silently lose them.
298 snap_path = repo_root / ".muse" / "snapshots" / f"{snap_id}.msgpack"
299 if snap_path.is_file() and not snap_path.is_symlink():
300 try:
301 raw_snap = msgpack.unpackb(snap_path.read_bytes(), raw=False)
302 manifest = raw_snap.get("manifest", {})
303 if isinstance(manifest, dict):
304 for oid in manifest.values():
305 if isinstance(oid, str) and oid:
306 reachable_objs.add(oid)
307 logger.critical(
308 "❌ gc: snapshot %s failed hash verification — "
309 "its objects were retained conservatively. "
310 "Run `muse verify-pack` to audit the store.",
311 snap_id[:8],
312 )
313 except Exception as exc:
314 logger.critical(
315 "❌ gc: could not read corrupt snapshot %s — "
316 "some objects may have been lost: %s",
317 snap_id[:8], exc,
318 )
319
320 # Stash snapshot IDs
321 _collect_stash_objects(repo_root, reachable_objs)
322
323 return reachable_snaps, reachable_objs
324
325
326 # ---------------------------------------------------------------------------
327 # Store enumeration helpers
328 # ---------------------------------------------------------------------------
329
330
331 _HEX_CHARS: frozenset[str] = frozenset("0123456789abcdef")
332
333
334 def _is_hex(s: str) -> bool:
335 """Return True iff every character of *s* is a lowercase hex digit."""
336 return bool(s) and all(c in _HEX_CHARS for c in s)
337
338
339 def _list_stored_objects(
340 repo_root: pathlib.Path,
341 *,
342 grace_period_seconds: int = _DEFAULT_GRACE_PERIOD_SECONDS,
343 ) -> list[tuple[str, pathlib.Path]]:
344 """Return ``(object_id, path)`` for every valid SHA-256 object in the store.
345
346 Only **real files** (not symlinks) whose name + parent prefix form a
347 64-char lowercase hex string are included. Stray files (editor temporaries,
348 macOS ``.DS_Store``, etc.) are silently skipped.
349
350 Symlink guard
351 ~~~~~~~~~~~~~
352 Both prefix directories and object files are rejected if they are symlinks.
353 Without this guard a crafted symlink inside ``.muse/objects/`` could cause
354 GC to ``unlink()`` a file anywhere on the filesystem — a silent data
355 destruction vector.
356
357 Grace period
358 ~~~~~~~~~~~~
359 Objects whose ``mtime`` is within *grace_period_seconds* seconds of now are
360 excluded from the returned list even if they are not currently reachable.
361 This closes the TOCTOU window where a concurrent ``muse commit`` has written
362 a blob but not yet created the commit record.
363
364 Args:
365 repo_root: Repository root (contains ``.muse/``).
366 grace_period_seconds: Number of seconds before an object becomes
367 eligible for collection. Default: 30 s.
368 """
369 objects_dir = repo_root / ".muse" / "objects"
370 if not objects_dir.exists():
371 return []
372
373 cutoff = time.time() - grace_period_seconds
374 pairs: list[tuple[str, pathlib.Path]] = []
375
376 for prefix_dir in objects_dir.iterdir():
377 prefix = prefix_dir.name
378 # Reject symlinks — a symlink-to-dir would pass is_dir() but must not.
379 if prefix_dir.is_symlink() or not prefix_dir.is_dir():
380 continue
381 if len(prefix) != 2 or not _is_hex(prefix):
382 continue
383
384 for obj_file in prefix_dir.iterdir():
385 rest = obj_file.name
386 # Reject symlinks — unlink()ing a symlink-to-file outside the repo
387 # would silently delete an unrelated file.
388 if obj_file.is_symlink() or not obj_file.is_file():
389 continue
390 if len(rest) != 62 or not _is_hex(rest):
391 continue
392
393 # Grace period: protect objects written in the last N seconds.
394 try:
395 if obj_file.stat().st_mtime > cutoff:
396 continue
397 except OSError:
398 # File disappeared between iterdir() and stat() — skip.
399 continue
400
401 object_id = prefix + rest
402 pairs.append((object_id, obj_file))
403
404 return pairs
405
406
407 def _list_stored_msgpack(
408 directory: pathlib.Path,
409 *,
410 grace_period_seconds: int = _DEFAULT_GRACE_PERIOD_SECONDS,
411 ) -> list[tuple[str, pathlib.Path]]:
412 """Return ``(stem, path)`` for every non-symlink ``.msgpack`` file in *directory*.
413
414 Applies the same grace-period and symlink guards as ``_list_stored_objects``.
415 """
416 if not directory.exists():
417 return []
418
419 cutoff = time.time() - grace_period_seconds
420 pairs: list[tuple[str, pathlib.Path]] = []
421
422 for p in directory.glob("*.msgpack"):
423 if p.is_symlink() or not p.is_file():
424 continue
425 try:
426 if p.stat().st_mtime > cutoff:
427 continue
428 except OSError:
429 continue
430 pairs.append((p.stem, p))
431
432 return pairs
433
434
435 # ---------------------------------------------------------------------------
436 # Public API
437 # ---------------------------------------------------------------------------
438
439
440 def run_gc(
441 repo_root: pathlib.Path,
442 *,
443 dry_run: bool = False,
444 grace_period_seconds: int = _DEFAULT_GRACE_PERIOD_SECONDS,
445 full: bool = False,
446 ) -> GcResult:
447 """Prune unreachable objects from the Muse object store.
448
449 Args:
450 repo_root: Root of the Muse repository (``.muse/`` lives here).
451 dry_run: When ``True``, report what *would* be deleted
452 without actually removing anything.
453 grace_period_seconds: Objects written within the last N seconds are
454 never deleted, even if currently unreachable.
455 Protects concurrent ``muse commit`` operations.
456 Default: 30 s.
457 full: When ``True``, also prune orphaned commit records
458 (``.muse/commits/``) and snapshot manifests
459 (``.muse/snapshots/``), mirroring ``git prune``.
460
461 Returns:
462 A ``GcResult`` with counts and the list of collected object IDs.
463 """
464 t0 = time.monotonic()
465 result = GcResult(dry_run=dry_run, grace_period_seconds=grace_period_seconds, full=full)
466
467 if full:
468 # --full: tight reachability — only objects reachable from live refs.
469 reachable_commits = _collect_reachable_commits(repo_root)
470 reachable_snaps, reachable_objs = _collect_reachable_snapshots(
471 repo_root, reachable_commits
472 )
473
474 result.commits_reachable = len(reachable_commits)
475 result.snapshots_reachable = len(reachable_snaps)
476 result.reachable_count = len(reachable_objs)
477
478 # Prune orphaned commits
479 commits_dir = repo_root / ".muse" / "commits"
480 for cid, commit_path in _list_stored_msgpack(
481 commits_dir, grace_period_seconds=grace_period_seconds
482 ):
483 if cid not in reachable_commits:
484 try:
485 size = commit_path.stat().st_size
486 except OSError:
487 size = 0
488 result.commits_collected += 1
489 result.commits_collected_bytes += size
490 if not dry_run:
491 try:
492 commit_path.unlink()
493 except OSError as exc:
494 logger.warning(
495 "⚠️ Could not remove commit %s: %s", cid[:12], exc
496 )
497
498 # Prune orphaned snapshots
499 snapshots_dir = repo_root / ".muse" / "snapshots"
500 for snap_id, snap_path in _list_stored_msgpack(
501 snapshots_dir, grace_period_seconds=grace_period_seconds
502 ):
503 if snap_id not in reachable_snaps:
504 try:
505 size = snap_path.stat().st_size
506 except OSError:
507 size = 0
508 result.snapshots_collected += 1
509 result.snapshots_collected_bytes += size
510 if not dry_run:
511 try:
512 snap_path.unlink()
513 except OSError as exc:
514 logger.warning(
515 "⚠️ Could not remove snapshot %s: %s", snap_id[:12], exc
516 )
517
518 # Prune unreachable blobs (tighter set: only from reachable commits)
519 stored = _list_stored_objects(repo_root, grace_period_seconds=grace_period_seconds)
520 for object_id, obj_path in stored:
521 if object_id not in reachable_objs:
522 try:
523 size = obj_path.stat().st_size
524 except OSError:
525 size = 0
526 result.collected_ids.append(object_id)
527 result.collected_bytes += size
528 result.collected_count += 1
529 if not dry_run:
530 try:
531 obj_path.unlink()
532 try:
533 if not any(obj_path.parent.iterdir()):
534 obj_path.parent.rmdir()
535 except OSError:
536 pass
537 except OSError as exc:
538 logger.warning(
539 "⚠️ Could not remove object %s: %s", object_id[:12], exc
540 )
541
542 else:
543 # Default: conservative blob-only GC using all commits in the store.
544 reachable = _collect_reachable_objects(repo_root)
545 stored = _list_stored_objects(repo_root, grace_period_seconds=grace_period_seconds)
546
547 result.reachable_count = len(reachable)
548
549 for object_id, obj_path in stored:
550 if object_id not in reachable:
551 try:
552 size = obj_path.stat().st_size
553 except OSError:
554 size = 0
555 result.collected_ids.append(object_id)
556 result.collected_bytes += size
557 result.collected_count += 1
558 if not dry_run:
559 try:
560 obj_path.unlink()
561 try:
562 if not any(obj_path.parent.iterdir()):
563 obj_path.parent.rmdir()
564 except OSError:
565 pass
566 except OSError as exc:
567 logger.warning(
568 "⚠️ Could not remove object %s: %s", object_id[:12], exc
569 )
570
571 result.elapsed_seconds = time.monotonic() - t0
572 logger.info(
573 "gc: %d reachable blobs, %d %s, full=%s, grace=%ds, %.3fs elapsed",
574 result.reachable_count,
575 result.collected_count,
576 "would be removed" if dry_run else "removed",
577 full,
578 grace_period_seconds,
579 result.elapsed_seconds,
580 )
581 return result
File History 1 commit
sha256:cf6265cea8c21d9228d90dec13ef6ec2dab5103d466db9cc4590681832de4bf8 docs(KD-STAGING): sync governance after KD-6b DONE Human 13 days ago