carlos / platform Public

Clone
git clone https://amadan.net/carlos/platform

Plain git — no account needed to clone.

Download

Download this file

1package genselect
2
3import (
4 "bytes"
5 "context"
6 "encoding/json"
7 "errors"
8 "fmt"
9 "io"
10 "strconv"
11 "strings"
12 "time"
13
14 "github.com/carlosframework/platform/internal/hostclaim"
15 "github.com/carlosframework/platform/internal/lease"
16 "github.com/superfly/ltx"
17)
18
19var (
20 ErrListing = errors.New("genselect: incomplete or invalid listing")
21 ErrDisagreement = errors.New("genselect: marker and holder disagree")
22 ErrIncarnation = errors.New("genselect: marker incarnation mismatch")
23 ErrMarker = errors.New("genselect: malformed marker")
24 ErrVersionID = errors.New("genselect: immutable version id required")
25 ErrDeleteMarker = errors.New("genselect: selected version is a delete marker")
26 ErrPinnedMissing = errors.New("genselect: pinned snapshot version missing")
27 ErrPinnedMismatch = errors.New("genselect: pinned snapshot mismatch")
28 ErrGap = errors.New("genselect: non-contiguous ltx files")
29 ErrEmpty = errors.New("genselect: no restorable data")
30 ErrRegion = errors.New("genselect: baseline belongs to another region")
31 ErrCovered = errors.New("genselect: local baseline is covered")
32 ErrInput = errors.New("genselect: invalid input")
33 ErrRoot = errors.New("genselect: invalid root")
34)
35
36type Reader interface {
37 ListVersions(context.Context, string, string) ([]lease.ObjectVersion, error)
38 GetVersion(context.Context, string, string, string) ([]byte, error)
39 OpenVersion(context.Context, string, string, string) (io.ReadCloser, error)
40}
41
42var _ Reader = (lease.VersionedStore)(nil)
43
44type Pin struct {
45 SnapshotKey string `json:"snapshot_key"`
46 SnapshotVersion string `json:"snapshot_version"`
47 SnapshotTXID uint64 `json:"snapshot_txid"`
48 SnapshotCRC64 uint64 `json:"snapshot_crc64"`
49}
50
51type Marker struct {
52 Op string `json:"op"`
53 Incarnation string `json:"incarnation"`
54 Host string `json:"host"`
55 Box string `json:"box"`
56 InstalledAt time.Time `json:"installed_at"`
57 ManifestSHA256 string `json:"manifest_sha256"`
58 Pin
59}
60
61// PreparedPin is supplied only from an authorized, completed build journal.
62// The caller binds this exact generation and pin to the authorized holder,
63// operation and destination region before calling SelectPrepared.
64type PreparedPin struct {
65 Generation string
66 SnapshotKey string
67 SnapshotVersion string
68 SnapshotTXID uint64
69 SnapshotCRC64 uint64
70}
71
72type Request struct {
73 Bucket, Region, Host string
74 Holder hostclaim.Holder
75}
76
77type File struct {
78 Key string `json:"key"`
79 VersionID string `json:"version_id"`
80 Level int `json:"level"`
81 MinTXID uint64 `json:"min_txid"`
82 MaxTXID uint64 `json:"max_txid"`
83 Size int64 `json:"size"`
84}
85
86type Plan struct {
87 Generation string
88 Files []File
89 Root *File
90 Marker *Marker
91 MarkerVersion string
92 Pin *Pin
93 MaxTXID uint64
94 MaxLevel0TXID uint64
95}
96
97type candidate struct {
98 generation, region string
99 covered bool
100}
101
102func origin(g string) string {
103 if g == "" {
104 return hostclaim.RootGeneration
105 }
106 return g
107}
108
109func component(s string) bool {
110 return s != "" && s != "." && s != ".." && !strings.ContainsAny(s, "/\\\x00")
111}
112
113func generation(s string) bool { return component(s) && s != hostclaim.RootGeneration }
114
115func versionID(s string) bool { return strings.TrimSpace(s) != "" && s != "null" }
116
117// prefix is a generation's prefix under location. Twins of the rule:
118// hostbox.GenerationPrefix and moves.ReplicaSource (whose keep is
119// coordinates' level-file test); the three change together.
120func prefix(location, gen string) string {
121 if gen == hostclaim.RootGeneration {
122 return location
123 }
124 return location + "g-" + gen + "/"
125}
126
127func coordinates(key, base string) (File, bool) {
128 if !strings.HasPrefix(key, base) {
129 return File{}, false
130 }
131 parts := strings.Split(strings.TrimPrefix(key, base), "/")
132 if len(parts) != 2 || len(parts[0]) != 4 {
133 return File{}, false
134 }
135 level, err := strconv.ParseUint(parts[0], 16, 16)
136 if err != nil || level > 9 || fmt.Sprintf("%04x", level) != parts[0] {
137 return File{}, false
138 }
139 min, max, err := ltx.ParseFilename(parts[1])
140 if err != nil || min == 0 || min > max || ltx.FormatFilename(min, max) != parts[1] {
141 return File{}, false
142 }
143 return File{Key: key, Level: int(level), MinTXID: uint64(min), MaxTXID: uint64(max)}, true
144}
145
146func exactFile(v lease.ObjectVersion, base string) (File, error) {
147 f, ok := coordinates(v.Key, base)
148 if !ok || v.Size < 0 {
149 return File{}, ErrListing
150 }
151 if !versionID(v.VersionID) {
152 return File{}, ErrVersionID
153 }
154 if v.DeleteMarker {
155 return File{}, ErrDeleteMarker
156 }
157 f.VersionID, f.Size = v.VersionID, v.Size
158 return f, nil
159}
160
161func requestLocation(s Reader, req Request) (string, error) {
162 h := req.Holder
163 location := strings.TrimSuffix(h.Location, "/")
164 if s == nil || req.Bucket == "" || req.Region == "" || !component(req.Host) || !component(h.Incarnation) ||
165 (location != "instances/"+req.Host && location != "instances/"+req.Host+"/"+h.Incarnation) ||
166 (h.Generation != "" && !generation(h.Generation)) {
167 return "", ErrInput
168 }
169 return location + "/", nil
170}
171
172func listVersions(ctx context.Context, s Reader, bucket, base string) ([]lease.ObjectVersion, map[string]lease.ObjectVersion, error) {
173 // VersionedStore drains all pages before returning. Never use partial data.
174 versions, err := s.ListVersions(ctx, bucket, base)
175 if err != nil {
176 return nil, nil, fmt.Errorf("%w: %w", ErrListing, err)
177 }
178 latest := make(map[string]lease.ObjectVersion)
179 keys := make(map[string]bool)
180 for _, v := range versions {
181 if !strings.HasPrefix(v.Key, base) {
182 return nil, nil, ErrListing
183 }
184 keys[v.Key] = true
185 if v.IsLatest {
186 if _, exists := latest[v.Key]; exists {
187 return nil, nil, ErrListing
188 }
189 latest[v.Key] = v
190 }
191 }
192 for k := range keys {
193 if _, ok := latest[k]; !ok {
194 return nil, nil, ErrListing
195 }
196 }
197 return versions, latest, nil
198}
199
200// Select resolves the ordinary baseline using the marker and unfinished run.
201// It returns identities only. The consumer must verify every complete file.
202func Select(ctx context.Context, s Reader, req Request) (*Plan, error) {
203 location, err := requestLocation(s, req)
204 if err != nil {
205 return nil, err
206 }
207 versions, latest, err := listVersions(ctx, s, req.Bucket, location)
208 if err != nil {
209 return nil, err
210 }
211 h := req.Holder
212 p := &Plan{Files: []File{}}
213 markerGen := hostclaim.RootGeneration
214 if mv, ok := latest[location+"generation.json"]; ok {
215 if !versionID(mv.VersionID) {
216 return nil, ErrVersionID
217 }
218 if mv.DeleteMarker {
219 return nil, ErrDeleteMarker
220 }
221 data, err := s.GetVersion(ctx, req.Bucket, mv.Key, mv.VersionID)
222 if err != nil {
223 return nil, fmt.Errorf("%w: %w", ErrMarker, err)
224 }
225 var fields map[string]json.RawMessage
226 if err := json.Unmarshal(data, &fields); err != nil {
227 return nil, ErrMarker
228 }
229 if raw, ok := fields["snapshot_txid"]; !ok || string(raw) == "null" {
230 return nil, ErrMarker
231 }
232 var m Marker
233 dec := json.NewDecoder(bytes.NewReader(data))
234 // Unknown additive fields are allowed. Malformed/trailing JSON is not.
235 if err := dec.Decode(&m); err != nil {
236 return nil, fmt.Errorf("%w: %w", ErrMarker, err)
237 }
238 if err := dec.Decode(new(any)); err != io.EOF {
239 return nil, ErrMarker
240 }
241 if m.Incarnation != h.Incarnation {
242 return nil, ErrIncarnation
243 }
244 if m.Host != req.Host || !generation(m.Op) || m.Box == "" || m.InstalledAt.IsZero() {
245 return nil, ErrMarker
246 }
247 markerGen, p.Marker, p.MarkerVersion = m.Op, &m, mv.VersionID
248 }
249 run, err := unfinished(h, markerGen, req.Region)
250 if err != nil {
251 return nil, err
252 }
253 selected := candidate{generation: markerGen, region: req.Region}
254 for _, c := range run {
255 if c.region != "" && c.region != req.Region {
256 continue
257 }
258 if c.covered {
259 return nil, ErrCovered
260 }
261 if c.generation == markerGen || hasObject(latest, location, c.generation) {
262 selected = c
263 break
264 }
265 }
266 p.Generation = selected.generation
267 base := prefix(location, p.Generation)
268 var pin *Pin
269 if p.Marker != nil && p.Generation == markerGen {
270 cp := p.Marker.Pin
271 pin = &cp
272 }
273 return selectFiles(ctx, s, req.Bucket, base, versions, latest, p, pin)
274}
275
276// SelectPrepared restores only the explicitly authorized prepared generation.
277// It never reads the marker or walks admissions, and never chooses a baseline.
278func SelectPrepared(ctx context.Context, s Reader, req Request, prepared PreparedPin) (*Plan, error) {
279 location, err := requestLocation(s, req)
280 if err != nil {
281 return nil, err
282 }
283 if !generation(prepared.Generation) {
284 return nil, ErrInput
285 }
286 // Empty prepared roots require a separate bootstrap protocol, not fallback.
287 if prepared.SnapshotTXID == 0 {
288 return nil, ErrPinnedMismatch
289 }
290 base := prefix(location, prepared.Generation)
291 versions, latest, err := listVersions(ctx, s, req.Bucket, base)
292 if err != nil {
293 return nil, err
294 }
295 pin := &Pin{SnapshotKey: prepared.SnapshotKey, SnapshotVersion: prepared.SnapshotVersion,
296 SnapshotTXID: prepared.SnapshotTXID, SnapshotCRC64: prepared.SnapshotCRC64}
297 p := &Plan{Generation: prepared.Generation, Files: []File{}}
298 return selectFiles(ctx, s, req.Bucket, base, versions, latest, p, pin)
299}
300
301// GenerationMax is the loss boundary of generation gen in a restore
302// (platform-1e's ruling on #236): the highest TXID of that exact generation
303// under location among the restore plan's selected files (a selected
304// historical pinned version counts, since the plan holds it). It never
305// lists the bucket. A generation the plan holds no file of, which is every
306// generation but the plan's own, is 0 and nil: every write in it is lost.
307// "" and hostclaim.RootGeneration are the location's own level files, the
308// legacy root. A plan file whose recorded coordinates are not its key's is
309// ErrInput. The claim writer's loss restore point (hostbox.Writer) and
310// moves' loss baseline validator read it alike.
311func GenerationMax(p *Plan, location, gen string) (uint64, error) {
312 location = strings.TrimSuffix(location, "/")
313 if p == nil || location == "" || (gen != "" && gen != hostclaim.RootGeneration && !generation(gen)) {
314 return 0, ErrInput
315 }
316 for _, part := range strings.Split(location, "/") {
317 if !component(part) {
318 return 0, ErrInput
319 }
320 }
321 base := prefix(location+"/", origin(gen))
322 max := uint64(0)
323 for _, f := range p.Files {
324 c, ok := coordinates(f.Key, base)
325 if !ok {
326 continue // another generation's file
327 }
328 if c.Level != f.Level || c.MinTXID != f.MinTXID || c.MaxTXID != f.MaxTXID {
329 return 0, ErrInput
330 }
331 if f.MaxTXID > max {
332 max = f.MaxTXID
333 }
334 }
335 return max, nil
336}
337
338// currentFile reads one latest version under base: a current level file
339// (ok), not one (a retention tombstone, another generation's key, a marker),
340// or a key shaped as a level file that does not parse (ErrListing). Select
341// and GenerationMax read the coordinates through it alone.
342func currentFile(v lease.ObjectVersion, base string) (File, bool, error) {
343 if _, ok := coordinates(v.Key, base); !ok {
344 if strings.HasPrefix(v.Key, base) {
345 parts := strings.Split(strings.TrimPrefix(v.Key, base), "/")
346 if len(parts) == 2 && len(parts[0]) == 4 && strings.HasSuffix(parts[1], ".ltx") {
347 if level, e := strconv.ParseUint(parts[0], 16, 16); e == nil && level <= 9 {
348 return File{}, false, ErrListing
349 }
350 }
351 }
352 return File{}, false, nil
353 }
354 if v.DeleteMarker {
355 return File{}, false, nil
356 } // Retention tombstones are not current files.
357 f, err := exactFile(v, base)
358 if err != nil {
359 return File{}, false, err
360 }
361 return f, true, nil
362}
363
364// Both entry points share exact-version root selection and continuation.
365func selectFiles(ctx context.Context, s Reader, bucket, base string, versions []lease.ObjectVersion,
366 latest map[string]lease.ObjectVersion, p *Plan, pin *Pin) (*Plan, error) {
367 if pin != nil {
368 if pin.SnapshotTXID == 0 {
369 if pin.SnapshotKey != "" || pin.SnapshotVersion != "" || pin.SnapshotCRC64 != 0 {
370 return nil, ErrPinnedMismatch
371 }
372 } else {
373 f, ok := coordinates(pin.SnapshotKey, base)
374 if !ok || f.Level != 9 || f.MinTXID != 1 || f.MaxTXID != pin.SnapshotTXID {
375 return nil, ErrPinnedMismatch
376 }
377 if !versionID(pin.SnapshotVersion) {
378 return nil, ErrVersionID
379 }
380 }
381 p.Pin = pin
382 }
383 var current []File
384 for _, v := range latest {
385 f, ok, err := currentFile(v, base)
386 if err != nil {
387 return nil, err
388 }
389 if !ok {
390 continue
391 }
392 if f.Level == 9 && f.MinTXID != 1 {
393 return nil, ErrRoot
394 }
395 current = append(current, f)
396 if f.Level == 0 && f.MaxTXID > p.MaxLevel0TXID {
397 p.MaxLevel0TXID = f.MaxTXID
398 }
399 }
400 floor := uint64(0)
401 if pin != nil {
402 floor = pin.SnapshotTXID
403 }
404 for _, f := range current {
405 // A late duplicate at the pinned key never replaces its acknowledged version.
406 if pin != nil && floor > 0 && f.Key == pin.SnapshotKey {
407 continue
408 }
409 if f.Level == 9 && f.MinTXID == 1 && f.MaxTXID >= floor && (p.Root == nil || better(f, *p.Root)) {
410 cp := f
411 p.Root = &cp
412 }
413 }
414 pinned := false
415 if p.Root == nil && floor > 0 {
416 var pv *lease.ObjectVersion
417 for _, v := range versions {
418 if v.Key == pin.SnapshotKey && v.VersionID == pin.SnapshotVersion {
419 cp := v
420 pv = &cp
421 break
422 }
423 }
424 if pv == nil {
425 return nil, ErrPinnedMissing
426 }
427 f, err := exactFile(*pv, base)
428 if err != nil {
429 return nil, err
430 }
431 p.Root, pinned = &f, true
432 }
433 if p.Root != nil {
434 if err := checkRoot(ctx, s, bucket, *p.Root, pinned); err != nil {
435 return nil, err
436 }
437 p.Files = append(p.Files, *p.Root)
438 p.MaxTXID = p.Root.MaxTXID
439 }
440 for {
441 var best *File
442 for _, f := range current {
443 if f.Level == 9 || p.MaxTXID == ^uint64(0) || !ltx.IsContiguous(ltx.TXID(p.MaxTXID), ltx.TXID(f.MinTXID), ltx.TXID(f.MaxTXID)) {
444 continue
445 }
446 if best == nil || better(f, *best) {
447 cp := f
448 best = &cp
449 }
450 }
451 if best == nil {
452 break
453 }
454 if p.Root == nil {
455 if err := checkRoot(ctx, s, bucket, *best, false); err != nil {
456 return nil, err
457 }
458 cp := *best
459 p.Root = &cp
460 }
461 p.Files = append(p.Files, *best)
462 p.MaxTXID = best.MaxTXID
463 }
464 for _, f := range current {
465 if f.Level < 9 && f.MaxTXID > p.MaxTXID {
466 return nil, ErrGap
467 }
468 }
469 if len(p.Files) == 0 {
470 return nil, ErrEmpty
471 }
472 return p, nil
473}
474
475func unfinished(h hostclaim.Holder, marker, region string) ([]candidate, error) {
476 gen := origin(h.Generation)
477 if gen == marker {
478 return []candidate{{generation: marker, region: region}}, nil
479 }
480 var out []candidate
481 covered := false
482 seen := map[string]bool{}
483 for i := len(h.Admissions) - 1; i >= 0; i-- {
484 a := h.Admissions[i]
485 if origin(a.Generation) != gen || a.Region != region {
486 return nil, ErrDisagreement
487 }
488 if a.Mode == "warm" {
489 if origin(a.Predecessor) != gen || a.PredecessorRegion != region {
490 return nil, ErrDisagreement
491 }
492 continue
493 }
494 if a.Mode != "cold" || !generation(a.Generation) || seen[gen] {
495 return nil, ErrDisagreement
496 }
497 seen[gen] = true
498 out = append(out, candidate{generation: gen, region: region, covered: covered})
499 gen, region, covered = origin(a.Predecessor), a.PredecessorRegion, a.Covered
500 if gen == marker {
501 return append(out, candidate{generation: gen, region: region, covered: covered}), nil
502 }
503 if !generation(gen) || region == "" {
504 return nil, ErrDisagreement
505 }
506 }
507 return nil, ErrDisagreement
508}
509
510func hasObject(latest map[string]lease.ObjectVersion, location, gen string) bool {
511 base := prefix(location, gen)
512 for k := range latest {
513 if !strings.HasPrefix(k, base) {
514 continue
515 }
516 if gen == hostclaim.RootGeneration {
517 if _, ok := coordinates(k, base); !ok {
518 continue
519 }
520 }
521 return true
522 }
523 return false
524}
525
526func better(a, b File) bool {
527 if a.MaxTXID != b.MaxTXID {
528 return a.MaxTXID > b.MaxTXID
529 }
530 if a.MinTXID != b.MinTXID {
531 return a.MinTXID < b.MinTXID
532 }
533 return a.Level > b.Level
534}
535
536func checkRoot(ctx context.Context, s Reader, bucket string, f File, pinned bool) error {
537 category := ErrRoot
538 if pinned {
539 category = ErrPinnedMismatch
540 }
541 rc, err := s.OpenVersion(ctx, bucket, f.Key, f.VersionID)
542 if err != nil {
543 if errors.Is(err, lease.ErrIsDeleteMarker) {
544 return fmt.Errorf("%w: %w", ErrDeleteMarker, err)
545 }
546 if pinned && errors.Is(err, lease.ErrMirrorNotFound) {
547 return fmt.Errorf("%w: %w", ErrPinnedMissing, err)
548 }
549 return fmt.Errorf("%w: %w", category, err)
550 }
551 dec := ltx.NewDecoder(rc)
552 err = dec.DecodeHeader()
553 closeErr := rc.Close()
554 if err != nil {
555 return fmt.Errorf("%w: %w", category, err)
556 }
557 if closeErr != nil {
558 return fmt.Errorf("%w: %w", category, closeErr)
559 }
560 h := dec.Header()
561 if uint64(h.MinTXID) != f.MinTXID || uint64(h.MaxTXID) != f.MaxTXID {
562 return category
563 }
564 return nil
565}
566