Skip to content
rachel/git-on-cloudflare
File

Blob: src/worker/git/pack/rewrite/ownership.ts

typescript413 lines
1import type { OrderedPackSnapshot } from "@/worker/git/operations/fetch/types";
2import type { Logger } from "@/worker/common/logger";
3 
4import { collectPackedObjectCandidates } from "@/worker/git/object-store";
5import type { PackHeaderEx } from "../packMeta";
6import {
7  copySelectionRow,
8  ensurePackReadState,
9  readSelectedHeader,
10  selectionKey,
11  setSelectionEntryIdentity,
12  storeSelectionHeader,
13  type PackReadState,
14  type RewriteOptions,
15  type SelectionTable,
16} from "./shared";
17 
18/**
19 * Planner-local OID owner table.
20 *
21 * This keeps canonical ownership keyed by the 20-byte object ID without
22 * materializing hex strings or per-entry JS objects. The table stores only
23 * live owner rows; duplicate rows are redirected and compacted later.
24 */
25export type SelectedOidLookup = {
26  count: number;
27  mask: number;
28  used: Uint8Array;
29  keys: Uint8Array;
30  owners: Int32Array;
31};
32 
33/**
34 * Duplicate-run probes may re-read the same candidate entry header multiple
35 * times while different rows converge onto the same OID. Cache a copied header
36 * per pack position so those probes stay request-local and bounded.
37 */
38export type DuplicateHeaderCache = Map<number, PackHeaderEx | null>;
39 
40export type SelectionStats = {
41  duplicateRedirects: number;
42  duplicateOwnerUpgrades: number;
43  duplicateOfsOwnerTakeovers: number;
44  duplicateHeaderProbes: number;
45};
46 
47export type ClaimOwnerResult =
48  | { kind: "unchanged"; canonicalized: boolean }
49  | { kind: "swapped" }
50  | { kind: "error" }
51  | { kind: "takeover"; canonicalized: boolean; previousOwnerSel: number }
52  | { kind: "redirect"; canonicalized: boolean; targetSel: number; upgradedOwner: boolean };
53 
54type FullDuplicateCandidate =
55  | { kind: "none" }
56  | { kind: "redirect"; targetSel: number }
57  | {
58      kind: "swap";
59      packSlot: number;
60      entryIndex: number;
61      offset: number;
62      nextOffset: number;
63      header: PackHeaderEx;
64    };
65 
66/** Smallest power-of-two table size for the open-addressed OID owner map. */
67function nextPowerOfTwo(value: number): number {
68  let out = 1;
69  while (out < value) out <<= 1;
70  return out;
71}
72 
73/** Hash a raw 20-byte object ID stored at `start` in `rawBytes`. */
74function hashOidAt(rawBytes: Uint8Array, start: number): number {
75  let hash = 2166136261;
76  for (let i = 0; i < 20; i++) {
77    hash ^= rawBytes[start + i]!;
78    hash = Math.imul(hash, 16777619);
79  }
80  return hash >>> 0;
81}
82 
83function slotKeyEquals(
84  keys: Uint8Array,
85  slot: number,
86  rawBytes: Uint8Array,
87  start: number
88): boolean {
89  const keyStart = slot * 20;
90  for (let i = 0; i < 20; i++) {
91    if (keys[keyStart + i] !== rawBytes[start + i]) return false;
92  }
93  return true;
94}
95 
96/** Create the planner's `OID -> owner selection slot` table. */
97export function createSelectedOidLookup(minimumEntries: number): SelectedOidLookup {
98  const slotCount = nextPowerOfTwo(Math.max(16, minimumEntries * 2));
99  return {
100    count: 0,
101    mask: slotCount - 1,
102    used: new Uint8Array(slotCount),
103    keys: new Uint8Array(slotCount * 20),
104    owners: new Int32Array(slotCount).fill(-1),
105  };
106}
107 
108/** Rebuild the owner map when it crosses the target load factor. */
109function rehashSelectedOidLookup(lookup: SelectedOidLookup, nextSlotCount: number): void {
110  const previousUsed = lookup.used;
111  const previousKeys = lookup.keys;
112  const previousOwners = lookup.owners;
113 
114  lookup.mask = nextSlotCount - 1;
115  lookup.used = new Uint8Array(nextSlotCount);
116  lookup.keys = new Uint8Array(nextSlotCount * 20);
117  lookup.owners = new Int32Array(nextSlotCount).fill(-1);
118  lookup.count = 0;
119 
120  for (let slot = 0; slot < previousUsed.length; slot++) {
121    if (!previousUsed[slot]) continue;
122    const keyStart = slot * 20;
123    setSelectedOidOwner(lookup, previousKeys, keyStart, previousOwners[slot]!);
124  }
125}
126 
127function ensureSelectedOidLookupCapacity(lookup: SelectedOidLookup): void {
128  if ((lookup.count + 1) * 10 <= lookup.used.length * 7) return;
129  rehashSelectedOidLookup(lookup, lookup.used.length * 2);
130}
131 
132/** Return the live owner row for an OID, or `-1` if the OID is unseen. */
133function findSelectedOidOwner(
134  lookup: SelectedOidLookup,
135  rawBytes: Uint8Array,
136  start: number
137): number {
138  let slot = hashOidAt(rawBytes, start) & lookup.mask;
139  while (lookup.used[slot]) {
140    if (slotKeyEquals(lookup.keys, slot, rawBytes, start)) {
141      return lookup.owners[slot]!;
142    }
143    slot = (slot + 1) & lookup.mask;
144  }
145  return -1;
146}
147 
148/** Install or replace the live owner row for an OID. */
149function setSelectedOidOwner(
150  lookup: SelectedOidLookup,
151  rawBytes: Uint8Array,
152  start: number,
153  ownerSel: number
154): void {
155  ensureSelectedOidLookupCapacity(lookup);
156 
157  let slot = hashOidAt(rawBytes, start) & lookup.mask;
158  while (lookup.used[slot]) {
159    if (slotKeyEquals(lookup.keys, slot, rawBytes, start)) {
160      lookup.owners[slot] = ownerSel;
161      return;
162    }
163    slot = (slot + 1) & lookup.mask;
164  }
165 
166  lookup.used[slot] = 1;
167  lookup.keys.set(rawBytes.subarray(start, start + 20), slot * 20);
168  lookup.owners[slot] = ownerSel;
169  lookup.count++;
170}
171 
172export function clonePackHeader(header: PackHeaderEx): PackHeaderEx {
173  return {
174    type: header.type,
175    sizeVarBytes: header.sizeVarBytes.slice(),
176    headerLen: header.headerLen,
177    baseOid: header.baseOid,
178    baseRel: header.baseRel,
179  };
180}
181 
182/**
183 * Read and memoize a duplicate candidate header.
184 *
185 * The rewrite pass already reads the live row header once. This memo is only
186 * for duplicate-run scans that would otherwise reread the same pack entry
187 * header multiple times while deciding which OID owner should survive.
188 */
189async function readDuplicateCandidateHeader(
190  cache: DuplicateHeaderCache,
191  stats: SelectionStats,
192  key: number,
193  readState: PackReadState,
194  offset: number
195): Promise<PackHeaderEx | null> {
196  const cached = cache.get(key);
197  if (cached !== undefined) return cached;
198 
199  stats.duplicateHeaderProbes++;
200  const header = await readSelectedHeader(readState, offset);
201  const cloned = header ? clonePackHeader(header) : null;
202  cache.set(key, cloned);
203  return cloned;
204}
205 
206export async function claimCanonicalOwner(
207  table: SelectionTable,
208  sel: number,
209  snapshot: OrderedPackSnapshot,
210  readerStates: Map<number, PackReadState>,
211  dedupMap: Map<number, number>,
212  oidOwners: SelectedOidLookup,
213  duplicateHeaderCache: DuplicateHeaderCache,
214  stats: SelectionStats,
215  env: Env,
216  log: Logger,
217  warnedFlags: Set<string>,
218  options?: RewriteOptions
219): Promise<ClaimOwnerResult> {
220  // The rewrite output still prefers a single live row per OID, but OFS-pinned
221  // rows may need to reclaim ownership so pack-local base chains stay valid.
222  // Resolve that ownership before wiring any new base edges.
223  const oidStart = sel * 20;
224  const ownerSel = findSelectedOidOwner(oidOwners, table.oidsRaw, oidStart);
225  if (ownerSel >= 0) {
226    const currentKey = selectionKey(table.packSlots[sel]!, table.entryIndices[sel]!);
227    if (ownerSel === sel) {
228      return { kind: "unchanged", canonicalized: false };
229    }
230 
231    if (table.ofsPinned[sel] && table.typeCodes[sel] >= 6 && !table.ofsPinned[ownerSel]) {
232      // OFS_DELTA children depend on the exact pack-local base position, not
233      // just the resulting OID. Let that exact row take ownership back so the
234      // later topology sort still sees the original acyclic within-pack chain.
235      stats.duplicateOfsOwnerTakeovers++;
236      setSelectedOidOwner(oidOwners, table.oidsRaw, oidStart, sel);
237      return {
238        kind: "takeover",
239        canonicalized: false,
240        previousOwnerSel: ownerSel,
241      };
242    }
243 
244    // Keep future exact pack-position lookups collapsed onto the current live
245    // owner. Without this, later base resolution can recreate an extra row for
246    // the same pack entry after ownership already converged.
247    dedupMap.set(currentKey, ownerSel);
248 
249    if (
250      !table.ofsPinned[ownerSel] &&
251      table.typeCodes[sel]! < 6 &&
252      table.typeCodes[ownerSel]! >= 6 &&
253      upgradeOwnerSelectionToFull(table, ownerSel, sel)
254    ) {
255      // Preserve the existing owner slot when a later full-object duplicate
256      // arrives. This upgrades the owner in place and keeps any already-wired
257      // `baseSlots` stable.
258      stats.duplicateOwnerUpgrades++;
259      setSelectedOidOwner(oidOwners, table.oidsRaw, oidStart, ownerSel);
260      return {
261        kind: "redirect",
262        canonicalized: true,
263        targetSel: ownerSel,
264        upgradedOwner: true,
265      };
266    }
267 
268    return {
269      kind: "redirect",
270      canonicalized: false,
271      targetSel: ownerSel,
272      upgradedOwner: false,
273    };
274  }
275 
276  if (!table.ofsPinned[sel] && (table.typeCodes[sel] === 6 || table.typeCodes[sel] === 7)) {
277    // Delta rows get one extra chance to become the canonical owner by
278    // locating a full-object duplicate anywhere in the snapshot.
279    const candidate = await tryCanonicalizeDeltaSelectionToFull(
280      table,
281      sel,
282      snapshot,
283      readerStates,
284      dedupMap,
285      duplicateHeaderCache,
286      stats,
287      env,
288      log,
289      warnedFlags,
290      options
291    );
292    if (candidate.kind === "redirect") {
293      // The best full-object duplicate is already selected elsewhere. Publish
294      // that row as the owner immediately so later duplicates short-circuit.
295      setSelectedOidOwner(oidOwners, table.oidsRaw, oidStart, candidate.targetSel);
296      return {
297        kind: "redirect",
298        canonicalized: true,
299        targetSel: candidate.targetSel,
300        upgradedOwner: false,
301      };
302    }
303    if (candidate.kind === "swap") {
304      // No selected full owner exists yet, so mutate the current row in place
305      // to the chosen full-object duplicate and keep this same `sel` alive.
306      const altPack = snapshot.packs[candidate.packSlot]!;
307      setSelectionEntryIdentity(table, sel, candidate.packSlot, candidate.entryIndex, altPack.idx);
308      if (
309        !storeSelectionHeader(table, sel, candidate.offset, candidate.nextOffset, candidate.header)
310      ) {
311        log.warn("rewrite:invalid-payload-length", {
312          packKey: altPack.packKey,
313          offset: candidate.offset,
314        });
315        return { kind: "error" };
316      }
317      table.baseSlots[sel] = -1;
318      setSelectedOidOwner(oidOwners, table.oidsRaw, oidStart, sel);
319      return { kind: "swapped" };
320    }
321  }
322 
323  setSelectedOidOwner(oidOwners, table.oidsRaw, oidStart, sel);
324  return { kind: "unchanged", canonicalized: false };
325}
326 
327function upgradeOwnerSelectionToFull(
328  table: SelectionTable,
329  ownerSel: number,
330  fullSel: number
331): boolean {
332  // Preserve the existing owner slot so previously wired `baseSlots` keep
333  // pointing at the same `sel`. Only the owner's pack position and header
334  // fields change to the newly observed full-object duplicate.
335  if (table.typeCodes[fullSel] >= 6 || table.typeCodes[ownerSel] < 6) return false;
336 
337  // Keep the owner slot's pin state intact: children may already require this
338  // exact selection slot to stay the canonical OFS-stable base.
339  copySelectionRow(table, ownerSel, fullSel, { preserveTargetOfsPinned: true });
340  table.baseSlots[ownerSel] = -1;
341  return true;
342}
343 
344async function tryCanonicalizeDeltaSelectionToFull(
345  table: SelectionTable,
346  sel: number,
347  snapshot: OrderedPackSnapshot,
348  readerStates: Map<number, PackReadState>,
349  dedupMap: Map<number, number>,
350  duplicateHeaderCache: DuplicateHeaderCache,
351  stats: SelectionStats,
352  env: Env,
353  log: Logger,
354  warnedFlags: Set<string>,
355  options?: RewriteOptions
356): Promise<FullDuplicateCandidate> {
357  const packSlot = table.packSlots[sel]!;
358  const entryIndex = table.entryIndices[sel]!;
359  const currentKey = selectionKey(packSlot, entryIndex);
360  const rawBytes = table.oidsRaw.subarray(sel * 20, sel * 20 + 20);
361 
362  // Scan duplicate runs in caller-provided snapshot order so tie-breaking
363  // stays deterministic. The first full-object duplicate wins; if it is
364  // already selected, redirect to that row instead of creating a second owner.
365  for (const candidate of collectPackedObjectCandidates(snapshot.packs, rawBytes)) {
366    if (candidate.packSlot === packSlot && candidate.objectIndex === entryIndex) continue;
367 
368    const altPack = snapshot.packs[candidate.packSlot]!;
369    const altReadState = await ensurePackReadState(
370      env,
371      altPack,
372      candidate.packSlot,
373      readerStates,
374      log,
375      warnedFlags,
376      options
377    );
378    const altKey = selectionKey(candidate.packSlot, candidate.objectIndex);
379    const altHeader = await readDuplicateCandidateHeader(
380      duplicateHeaderCache,
381      stats,
382      altKey,
383      altReadState,
384      candidate.offset
385    );
386    if (!altHeader || altHeader.type === 6 || altHeader.type === 7) continue;
387 
388    const existingOwner = dedupMap.get(altKey);
389    if (existingOwner !== undefined && existingOwner !== sel) {
390      // Keep the original position key pointing at the existing owner so any
391      // OFS bases already resolved against this slot continue to hit the
392      // canonical full-object selection after dead-slot compaction.
393      dedupMap.set(currentKey, existingOwner);
394      return { kind: "redirect", targetSel: existingOwner };
395    }
396 
397    // Replace the selected delta in-place with the verified full-object
398    // duplicate. The original position key intentionally keeps pointing at
399    // `sel` so future OFS lookups collapse onto the same live owner slot.
400    dedupMap.set(altKey, sel);
401    return {
402      kind: "swap",
403      packSlot: candidate.packSlot,
404      entryIndex: candidate.objectIndex,
405      offset: candidate.offset,
406      nextOffset: candidate.nextOffset,
407      header: altHeader,
408    };
409  }
410 
411  return { kind: "none" };
412}