1// Copyright 2016 Keybase Inc. All rights reserved. 2// Use of this source code is governed by a BSD 3// license that can be found in the LICENSE file. 4 5package libkbfs 6 7import ( 8 "encoding/json" 9 "fmt" 10 "io/ioutil" 11 "os" 12 sysPath "path" 13 "runtime/debug" 14 "sort" 15 "strings" 16 "sync" 17 "time" 18 19 "github.com/keybase/client/go/kbfs/data" 20 "github.com/keybase/client/go/kbfs/idutil" 21 "github.com/keybase/client/go/kbfs/kbfsblock" 22 "github.com/keybase/client/go/kbfs/kbfscrypto" 23 "github.com/keybase/client/go/kbfs/kbfsmd" 24 "github.com/keybase/client/go/kbfs/kbfssync" 25 "github.com/keybase/client/go/kbfs/ldbutils" 26 "github.com/keybase/client/go/kbfs/libcontext" 27 "github.com/keybase/client/go/protocol/keybase1" 28 "github.com/keybase/go-codec/codec" 29 "github.com/pkg/errors" 30 "github.com/syndtr/goleveldb/leveldb" 31 "github.com/syndtr/goleveldb/leveldb/storage" 32 "golang.org/x/net/context" 33) 34 35// CtxCRTagKey is the type used for unique context tags related to 36// conflict resolution 37type CtxCRTagKey int 38 39type failModeForTesting int 40 41const ( 42 // CtxCRIDKey is the type of the tag for unique operation IDs 43 // related to conflict resolution 44 CtxCRIDKey CtxCRTagKey = iota 45 46 // If the number of outstanding unmerged revisions that need to be 47 // resolved together is greater than this number, then block 48 // unmerged writes to make sure we don't get *too* unmerged. 49 // TODO: throttle unmerged writes before resorting to complete 50 // blockage. 51 crMaxRevsThresholdDefault = 500 52 53 // How long we're allowed to block writes for if we exceed the max 54 // revisions threshold. 55 crMaxWriteLockTime = 10 * time.Second 56 57 // Where in config.StorageRoot() we store information about failed conflict 58 // resolutions. 59 conflictResolverRecordsDir = "kbfs_conflicts" 60 conflictResolverRecordsVersionString = "v1" 61 conflictResolverRecordsDB = "kbfsConflicts.leveldb" 62 63 // If we have failed at CR 10 times, probably it's never going to work and 64 // we should give up. 65 maxConflictResolutionAttempts = 10 66 67 alwaysFailCR failModeForTesting = iota 68 doNotAlwaysFailCR 69) 70 71// ErrTooManyCRAttempts is an error that indicates that CR has failed 72// too many times, and it being stopped. 73var ErrTooManyCRAttempts = errors.New( 74 "too many attempts at conflict resolution on this TLF") 75 76// ErrCRFailForTesting indicates that CR is disabled for a test. 77var ErrCRFailForTesting = errors.New( 78 "conflict resolution failed because test requested it") 79 80// CtxCROpID is the display name for the unique operation 81// conflict resolution ID tag. 82const CtxCROpID = "CRID" 83 84type conflictInput struct { 85 unmerged kbfsmd.Revision 86 merged kbfsmd.Revision 87} 88 89var errNoCRDB = errors.New("could not record CR attempt because no DB is open") 90 91// ConflictResolver is responsible for resolving conflicts in the 92// background. 93type ConflictResolver struct { 94 config Config 95 fbo *folderBranchOps 96 prepper folderUpdatePrepper 97 log traceLogger 98 deferLog traceLogger 99 maxRevsThreshold int 100 101 inputChanLock sync.RWMutex 102 inputChan chan conflictInput 103 104 // resolveGroup tracks the outstanding resolves. 105 resolveGroup kbfssync.RepeatedWaitGroup 106 107 inputLock sync.Mutex 108 currInput conflictInput 109 currCancel context.CancelFunc 110 lockNextTime bool 111 canceledCount int 112 113 failModeLock sync.RWMutex 114 failModeForTesting failModeForTesting 115} 116 117// NewConflictResolver constructs a new ConflictResolver (and launches 118// any necessary background goroutines). 119func NewConflictResolver( 120 config Config, fbo *folderBranchOps) *ConflictResolver { 121 // make a logger with an appropriate module name 122 branchSuffix := "" 123 if fbo.branch() != data.MasterBranch { 124 branchSuffix = " " + string(fbo.branch()) 125 } 126 tlfStringFull := fbo.id().String() 127 log := config.MakeLogger( 128 fmt.Sprintf("CR %s%s", tlfStringFull[:8], branchSuffix)) 129 130 cr := &ConflictResolver{ 131 config: config, 132 fbo: fbo, 133 prepper: folderUpdatePrepper{ 134 config: config, 135 folderBranch: fbo.folderBranch, 136 blocks: &fbo.blocks, 137 log: log, 138 vlog: config.MakeVLogger(log), 139 }, 140 log: traceLogger{log}, 141 deferLog: traceLogger{log.CloneWithAddedDepth(1)}, 142 maxRevsThreshold: crMaxRevsThresholdDefault, 143 currInput: conflictInput{ 144 unmerged: kbfsmd.RevisionUninitialized, 145 merged: kbfsmd.RevisionUninitialized, 146 }, 147 } 148 149 if fbo.bType == standard && config.Mode().ConflictResolutionEnabled() { 150 cr.startProcessing(libcontext.BackgroundContextWithCancellationDelayer()) 151 } 152 return cr 153} 154 155func (cr *ConflictResolver) startProcessing(baseCtx context.Context) { 156 cr.inputChanLock.Lock() 157 defer cr.inputChanLock.Unlock() 158 159 if cr.inputChan != nil { 160 return 161 } 162 cr.inputChan = make(chan conflictInput) 163 go cr.processInput(baseCtx, cr.inputChan) 164} 165 166func (cr *ConflictResolver) stopProcessing() { 167 cr.inputChanLock.Lock() 168 defer cr.inputChanLock.Unlock() 169 170 if cr.inputChan == nil { 171 return 172 } 173 close(cr.inputChan) 174 cr.inputChan = nil 175} 176 177// cancelExistingLocked must be called while holding cr.inputLock. 178func (cr *ConflictResolver) cancelExistingLocked(ci conflictInput) bool { 179 // The input is only interesting if one of the revisions is 180 // greater than what we've looked at to date. 181 if ci.unmerged <= cr.currInput.unmerged && 182 ci.merged <= cr.currInput.merged { 183 return false 184 } 185 if cr.currCancel != nil { 186 cr.currCancel() 187 } 188 return true 189} 190 191// ForceCancel cancels any currently-running CR, regardless of what 192// its inputs were. 193func (cr *ConflictResolver) ForceCancel() { 194 cr.inputLock.Lock() 195 defer cr.inputLock.Unlock() 196 if cr.currCancel != nil { 197 cr.currCancel() 198 } 199} 200 201// processInput processes conflict resolution jobs from the given 202// channel until it is closed. This function uses a parameter for the 203// channel instead of accessing cr.inputChan directly so that it 204// doesn't have to hold inputChanLock. 205func (cr *ConflictResolver) processInput(baseCtx context.Context, 206 inputChan <-chan conflictInput) { 207 208 // Start off with a closed prevCRDone, so that the first CR call 209 // doesn't have to wait. 210 prevCRDone := make(chan struct{}) 211 close(prevCRDone) 212 defer func() { 213 cr.inputLock.Lock() 214 defer cr.inputLock.Unlock() 215 if cr.currCancel != nil { 216 cr.currCancel() 217 } 218 _ = libcontext.CleanupCancellationDelayer(baseCtx) 219 }() 220 for ci := range inputChan { 221 ctx := CtxWithRandomIDReplayable(baseCtx, CtxCRIDKey, CtxCROpID, cr.log) 222 223 valid := func() bool { 224 cr.inputLock.Lock() 225 defer cr.inputLock.Unlock() 226 valid := cr.cancelExistingLocked(ci) 227 if !valid { 228 return false 229 } 230 cr.log.CDebugf(ctx, "New conflict input %v following old "+ 231 "input %v", ci, cr.currInput) 232 cr.currInput = ci 233 ctx, cr.currCancel = context.WithCancel(ctx) 234 return true 235 }() 236 if !valid { 237 cr.log.CDebugf(ctx, "Ignoring uninteresting input: %v", ci) 238 cr.resolveGroup.Done() 239 continue 240 } 241 242 waitChan := prevCRDone 243 prevCRDone = make(chan struct{}) // closed when doResolve finishes 244 go func(ci conflictInput, done chan<- struct{}) { 245 defer cr.resolveGroup.Done() 246 defer close(done) 247 // Wait for the previous CR without blocking any 248 // Resolve callers, as that could result in deadlock 249 // (KBFS-1001). 250 select { 251 case <-waitChan: 252 case <-ctx.Done(): 253 cr.log.CDebugf(ctx, "Resolution canceled before starting") 254 // The next attempt will still need to wait on the old 255 // one, in case it hasn't finished yet. So wait for 256 // it here, before we close our own `done` channel. 257 <-waitChan 258 return 259 } 260 cr.doResolve(ctx, ci) 261 }(ci, prevCRDone) 262 } 263} 264 265// Resolve takes the latest known unmerged and merged revision 266// numbers, and kicks off the resolution process. 267func (cr *ConflictResolver) Resolve(ctx context.Context, 268 unmerged kbfsmd.Revision, merged kbfsmd.Revision) { 269 cr.inputChanLock.RLock() 270 defer cr.inputChanLock.RUnlock() 271 272 // CR can end up trying to cancel itself via the SyncAll call, so 273 // prevent that from happening. 274 if crOpID := ctx.Value(CtxCRIDKey); crOpID != nil { 275 cr.log.CDebugf(ctx, "Ignoring self-resolve during CR") 276 return 277 } 278 279 if cr.inputChan == nil { 280 return 281 } 282 283 // Call Add before cancelling existing CR in order to prevent the 284 // resolveGroup from becoming briefly empty and allowing things waiting 285 // on it to believe that CR has finished. 286 cr.resolveGroup.Add(1) 287 288 ci := conflictInput{unmerged, merged} 289 func() { 290 cr.inputLock.Lock() 291 defer cr.inputLock.Unlock() 292 // Cancel any running CR before we return, so the caller can be 293 // confident any ongoing CR superseded by this new input will be 294 // canceled before it releases any locks it holds. 295 // 296 // TODO: return early if this returns false, and log something 297 // using a newly-pass-in context. 298 _ = cr.cancelExistingLocked(ci) 299 }() 300 301 cr.inputChan <- ci 302} 303 304// Wait blocks until the current set of submitted resolutions are 305// complete (though not necessarily successful), or until the given 306// context is canceled. 307func (cr *ConflictResolver) Wait(ctx context.Context) error { 308 return cr.resolveGroup.Wait(ctx) 309} 310 311// Shutdown cancels any ongoing resolutions and stops any background 312// goroutines. 313func (cr *ConflictResolver) Shutdown() { 314 cr.stopProcessing() 315} 316 317// Pause cancels any ongoing resolutions and prevents any new ones from 318// starting. 319func (cr *ConflictResolver) Pause() { 320 cr.stopProcessing() 321} 322 323// Restart re-enables conflict resolution, with a base context for CR 324// operations. baseCtx must have a cancellation delayer. 325func (cr *ConflictResolver) Restart(baseCtx context.Context) { 326 cr.startProcessing(baseCtx) 327} 328 329// BeginNewBranch resets any internal state to be ready to accept 330// resolutions from a new branch. 331func (cr *ConflictResolver) BeginNewBranch() { 332 cr.inputLock.Lock() 333 defer cr.inputLock.Unlock() 334 // Reset the curr input so we don't ignore a future CR 335 // request that uses the same revision number (i.e., 336 // because the previous CR failed to flush due to a 337 // conflict). 338 cr.currInput = conflictInput{} 339} 340 341func (cr *ConflictResolver) checkDone(ctx context.Context) error { 342 select { 343 case <-ctx.Done(): 344 return ctx.Err() 345 default: 346 return nil 347 } 348} 349 350func (cr *ConflictResolver) getMDs( 351 ctx context.Context, lState *kbfssync.LockState, 352 writerLocked bool) (unmerged []ImmutableRootMetadata, 353 merged []ImmutableRootMetadata, err error) { 354 // First get all outstanding unmerged MDs for this device. 355 var branchPoint kbfsmd.Revision 356 if writerLocked { 357 branchPoint, unmerged, err = 358 cr.fbo.getUnmergedMDUpdatesLocked(ctx, lState) 359 } else { 360 branchPoint, unmerged, err = 361 cr.fbo.getUnmergedMDUpdates(ctx, lState) 362 } 363 if err != nil { 364 return nil, nil, err 365 } 366 367 for i, md := range unmerged { 368 newMd, err := reembedBlockChangesIntoCopyIfNeeded( 369 ctx, cr.config.Codec(), cr.config.BlockCache(), 370 cr.config.BlockOps(), cr.config.Mode(), md, cr.log) 371 if err != nil { 372 return nil, nil, err 373 } 374 unmerged[i] = newMd 375 } 376 377 if len(unmerged) > 0 && unmerged[0].BID() == kbfsmd.PendingLocalSquashBranchID { 378 cr.log.CDebugf(ctx, "Squashing local branch") 379 return unmerged, nil, nil 380 } 381 382 // Now get all the merged MDs, starting from after the branch 383 // point. We fetch the branch point (if possible) to make sure 384 // it's the right predecessor of the unmerged branch. TODO: stop 385 // fetching the branch point and remove the successor check below 386 // once we fix KBFS-1664. 387 fetchFrom := branchPoint + 1 388 if branchPoint >= kbfsmd.RevisionInitial { 389 fetchFrom = branchPoint 390 } 391 merged, err = getMergedMDUpdates( 392 ctx, cr.fbo.config, cr.fbo.id(), fetchFrom, nil) 393 if err != nil { 394 return nil, nil, err 395 } 396 397 if len(unmerged) > 0 { 398 err := merged[0].CheckValidSuccessor( 399 merged[0].mdID, unmerged[0].ReadOnly()) 400 if err != nil { 401 cr.log.CDebugf(ctx, "Branch point (rev=%d, mdID=%s) is not a "+ 402 "valid successor for unmerged rev %d (mdID=%s, bid=%s)", 403 merged[0].Revision(), merged[0].mdID, unmerged[0].Revision(), 404 unmerged[0].mdID, unmerged[0].BID()) 405 return nil, nil, err 406 } 407 } 408 409 // Remove branch point. 410 if len(merged) > 0 && fetchFrom == branchPoint { 411 merged = merged[1:] 412 } 413 414 return unmerged, merged, nil 415} 416 417// updateCurrInput assumes that both unmerged and merged are 418// non-empty. 419func (cr *ConflictResolver) updateCurrInput(ctx context.Context, 420 unmerged, merged []ImmutableRootMetadata) (err error) { 421 cr.inputLock.Lock() 422 defer cr.inputLock.Unlock() 423 // check done while holding the lock, so we know for sure if 424 // we've already been canceled and replaced by a new input. 425 err = cr.checkDone(ctx) 426 if err != nil { 427 return err 428 } 429 430 prevInput := cr.currInput 431 defer func() { 432 // reset the currInput if we get an error below 433 if err != nil { 434 cr.currInput = prevInput 435 } 436 }() 437 438 rev := unmerged[len(unmerged)-1].bareMd.RevisionNumber() 439 if rev < cr.currInput.unmerged { 440 return fmt.Errorf("Unmerged revision %d is lower than the "+ 441 "expected unmerged revision %d", rev, cr.currInput.unmerged) 442 } 443 cr.currInput.unmerged = rev 444 445 if len(merged) > 0 { 446 rev = merged[len(merged)-1].bareMd.RevisionNumber() 447 if rev < cr.currInput.merged { 448 return fmt.Errorf("Merged revision %d is lower than the "+ 449 "expected merged revision %d", rev, cr.currInput.merged) 450 } 451 } else { 452 rev = kbfsmd.RevisionUninitialized 453 } 454 cr.currInput.merged = rev 455 456 // Take the lock right away next time if either there are lots of 457 // unmerged revisions, or this is a local squash and we won't 458 // block for very long. 459 // 460 // TODO: if there are a lot of merged revisions, and they keep 461 // coming, we might consider doing a "partial" resolution, writing 462 // the result back to the unmerged branch (basically "rebasing" 463 // it). See KBFS-1896. 464 if (len(unmerged) > cr.maxRevsThreshold) || 465 (len(unmerged) > 0 && unmerged[0].BID() == kbfsmd.PendingLocalSquashBranchID) { 466 cr.lockNextTime = true 467 } 468 return nil 469} 470 471func (cr *ConflictResolver) makeChains(ctx context.Context, 472 unmerged, merged []ImmutableRootMetadata) ( 473 unmergedChains, mergedChains *crChains, err error) { 474 unmergedChains, err = newCRChainsForIRMDs( 475 ctx, cr.config.Codec(), cr.config, unmerged, &cr.fbo.blocks, true) 476 if err != nil { 477 return nil, nil, err 478 } 479 480 // Make sure we don't try to unref any blocks that have already 481 // been GC'd in the merged branch. 482 for _, md := range merged { 483 for _, op := range md.data.Changes.Ops { 484 _, isGCOp := op.(*GCOp) 485 if !isGCOp { 486 continue 487 } 488 for _, ptr := range op.Unrefs() { 489 unmergedChains.doNotUnrefPointers[ptr] = true 490 } 491 } 492 } 493 494 // If there are no new merged changes, don't make any merged 495 // chains. 496 if len(merged) == 0 { 497 return unmergedChains, newCRChainsEmpty(nil), nil 498 } 499 500 mergedChains, err = newCRChainsForIRMDs( 501 ctx, cr.config.Codec(), cr.config, merged, &cr.fbo.blocks, true) 502 if err != nil { 503 return nil, nil, err 504 } 505 506 // Make the chain summaries. Identify using the unmerged chains, 507 // since those are most likely to be able to identify a node in 508 // the cache. 509 unmergedSummary := unmergedChains.summary(unmergedChains, cr.fbo.nodeCache) 510 mergedSummary := mergedChains.summary(unmergedChains, cr.fbo.nodeCache) 511 512 // Ignore CR summaries for pending local squashes. 513 if len(unmerged) == 0 || unmerged[0].BID() != kbfsmd.PendingLocalSquashBranchID { 514 cr.fbo.status.setCRSummary(unmergedSummary, mergedSummary) 515 } 516 return unmergedChains, mergedChains, nil 517} 518 519// A helper class that implements sort.Interface to sort paths by 520// descending path length. 521type crSortedPaths []data.Path 522 523// Len implements sort.Interface for crSortedPaths 524func (sp crSortedPaths) Len() int { 525 return len(sp) 526} 527 528// Less implements sort.Interface for crSortedPaths 529func (sp crSortedPaths) Less(i, j int) bool { 530 return len(sp[i].Path) > len(sp[j].Path) 531} 532 533// Swap implements sort.Interface for crSortedPaths 534func (sp crSortedPaths) Swap(i, j int) { 535 sp[j], sp[i] = sp[i], sp[j] 536} 537 538func createdFileWithConflictingWrite(unmergedChains, mergedChains *crChains, 539 unmergedOriginal, mergedOriginal data.BlockPointer) bool { 540 mergedChain := mergedChains.byOriginal[mergedOriginal] 541 unmergedChain := unmergedChains.byOriginal[unmergedOriginal] 542 if mergedChain == nil || unmergedChain == nil { 543 return false 544 } 545 546 unmergedWriteRange := unmergedChain.getCollapsedWriteRange() 547 mergedWriteRange := mergedChain.getCollapsedWriteRange() 548 // Are they exactly equivalent? 549 if writeRangesEquivalent(unmergedWriteRange, mergedWriteRange) { 550 unmergedChain.removeSyncOps() 551 return false 552 } 553 554 // If the unmerged one is just a truncate, we can safely ignore 555 // the unmerged chain. 556 if len(unmergedWriteRange) == 1 && unmergedWriteRange[0].isTruncate() && 557 unmergedWriteRange[0].Off == 0 { 558 unmergedChain.removeSyncOps() 559 return false 560 } 561 562 // If the merged one is just a truncate, we can safely ignore 563 // the merged chain. 564 if len(mergedWriteRange) == 1 && mergedWriteRange[0].isTruncate() && 565 mergedWriteRange[0].Off == 0 { 566 mergedChain.removeSyncOps() 567 return false 568 } 569 570 return true 571} 572 573// createdFileWithNonzeroSizes checks two possibly-conflicting 574// createOps and returns true if the corresponding file has non-zero 575// directory entry sizes in both the unmerged and merged branch. We 576// need to check this sometimes, because a call to 577// `createdFileWithConflictingWrite` might not have access to syncOps 578// that have been resolved away in a previous iteration. See 579// KBFS-2825 for details. 580func (cr *ConflictResolver) createdFileWithNonzeroSizes( 581 ctx context.Context, unmergedChains, mergedChains *crChains, 582 unmergedChain *crChain, mergedChain *crChain, 583 unmergedCop, mergedCop *createOp) (bool, error) { 584 lState := makeFBOLockState() 585 // The pointers on the ops' final paths aren't necessarily filled 586 // in, so construct our own partial paths using the chain 587 // pointers, which are enough to satisfy `GetEntry`. 588 mergedPath := data.Path{ 589 FolderBranch: mergedCop.getFinalPath().FolderBranch, 590 Path: []data.PathNode{ 591 {BlockPointer: mergedChain.mostRecent, 592 Name: data.NewPathPartString("", nil)}, 593 {BlockPointer: data.ZeroPtr, Name: mergedCop.obfuscatedNewName()}, 594 }, 595 } 596 kmd := mergedChains.mostRecentChainMDInfo 597 mergedEntry, err := cr.fbo.blocks.GetEntry(ctx, lState, kmd, mergedPath) 598 if _, noExists := errors.Cause(err).(idutil.NoSuchNameError); noExists { 599 return false, nil 600 } else if err != nil { 601 return false, err 602 } 603 604 kmd = unmergedChains.mostRecentChainMDInfo 605 unmergedPath := data.Path{ 606 FolderBranch: mergedCop.getFinalPath().FolderBranch, 607 Path: []data.PathNode{ 608 {BlockPointer: unmergedChain.mostRecent, 609 Name: data.NewPathPartString("", nil)}, 610 {BlockPointer: data.ZeroPtr, Name: mergedCop.obfuscatedNewName()}, 611 }, 612 } 613 unmergedEntry, err := cr.fbo.blocks.GetEntry(ctx, lState, kmd, unmergedPath) 614 if _, noExists := errors.Cause(err).(idutil.NoSuchNameError); noExists { 615 return false, nil 616 } else if err != nil { 617 return false, err 618 } 619 620 if mergedEntry.Size > 0 && unmergedEntry.Size > 0 { 621 cr.log.CDebugf(ctx, 622 "Not merging files named %s with non-zero sizes "+ 623 "(merged=%d unmerged=%d)", 624 unmergedCop.NewName, mergedEntry.Size, unmergedEntry.Size) 625 return true, nil 626 } 627 return false, nil 628} 629 630// checkPathForMerge checks whether the given unmerged chain and path 631// contains any newly-created subdirectories that were created 632// simultaneously in the merged branch as well. If so, it recursively 633// checks that directory as well. It returns a slice of any new 634// unmerged paths that need to be checked for conflicts later in 635// conflict resolution, for all subdirectories of the given path. 636func (cr *ConflictResolver) checkPathForMerge(ctx context.Context, 637 unmergedChain *crChain, unmergedPath data.Path, 638 unmergedChains, mergedChains *crChains) ([]data.Path, error) { 639 mergedChain, ok := mergedChains.byOriginal[unmergedChain.original] 640 if !ok { 641 // No corresponding merged chain means we don't have to merge 642 // any directories. 643 return nil, nil 644 } 645 646 // Find instances of the same directory being created in both 647 // branches. Only merge completely new directories -- anything 648 // involving a rename will result in a conflict for now. 649 // 650 // TODO: have a better merge strategy for renamed directories! 651 mergedCreates := make(map[string]*createOp) 652 for _, op := range mergedChain.ops { 653 cop, ok := op.(*createOp) 654 if !ok || len(cop.Refs()) == 0 || cop.renamed { 655 continue 656 } 657 mergedCreates[cop.NewName] = cop 658 } 659 660 if len(mergedCreates) == 0 { 661 return nil, nil 662 } 663 664 var newUnmergedPaths []data.Path 665 toDrop := make(map[int]bool) 666 for i, op := range unmergedChain.ops { 667 cop, ok := op.(*createOp) 668 if !ok || len(cop.Refs()) == 0 || cop.renamed { 669 continue 670 } 671 672 // Is there a corresponding merged create with the same type? 673 mergedCop, ok := mergedCreates[cop.NewName] 674 if !ok || mergedCop.Type != cop.Type { 675 continue 676 } 677 unmergedOriginal := cop.Refs()[0] 678 mergedOriginal := mergedCop.Refs()[0] 679 if cop.Type != data.Dir { 680 // Only merge files if they don't both have writes. 681 // Double-check the directory blocks to see if the files 682 // have non-zero sizes, because an earlier resolution 683 // might have collapsed all the sync ops away. 684 if createdFileWithConflictingWrite(unmergedChains, mergedChains, 685 unmergedOriginal, mergedOriginal) { 686 continue 687 } 688 conflicts, err := cr.createdFileWithNonzeroSizes( 689 ctx, unmergedChains, mergedChains, unmergedChain, mergedChain, 690 cop, mergedCop) 691 if err != nil { 692 return nil, err 693 } 694 if conflicts { 695 continue 696 } 697 } 698 699 toDrop[i] = true 700 701 cr.log.CDebugf(ctx, "Merging name %s (%s) in %v (unmerged original %v "+ 702 "changed to %v)", cop.NewName, cop.Type, unmergedChain.mostRecent, 703 unmergedOriginal, mergedOriginal) 704 // Change the original to match the merged original, so we can 705 // check for conflicts later. Note that the most recent will 706 // stay the same, so we can still match the unmerged path 707 // correctly. 708 err := unmergedChains.changeOriginal(unmergedOriginal, mergedOriginal) 709 if _, notFound := errors.Cause(err).(NoChainFoundError); notFound { 710 unmergedChains.toUnrefPointers[unmergedOriginal] = true 711 continue 712 } 713 if err != nil { 714 return nil, err 715 } else if unmergedOriginal == mergedOriginal { 716 cr.log.CDebugf(ctx, 717 "Treating self-conflicting directory like a normal conflict") 718 } 719 720 unmergedChain, ok := unmergedChains.byOriginal[mergedOriginal] 721 if !ok { 722 return nil, fmt.Errorf("Change original (%v -> %v) didn't work", 723 unmergedOriginal, mergedOriginal) 724 } 725 newPath := unmergedPath.ChildPath( 726 cop.obfuscatedNewName(), unmergedChain.mostRecent, 727 unmergedChain.obfuscator) 728 if cop.Type == data.Dir { 729 // recurse for this chain 730 newPaths, err := cr.checkPathForMerge(ctx, unmergedChain, newPath, 731 unmergedChains, mergedChains) 732 if err != nil { 733 return nil, err 734 } 735 // Add any further subdirectories that need merging under this 736 // subdirectory. 737 newUnmergedPaths = append(newUnmergedPaths, newPaths...) 738 } else { 739 // Set the path for all child ops 740 unrefedOrig := false 741 for _, op := range unmergedChain.ops { 742 op.setFinalPath(newPath) 743 _, isSyncOp := op.(*syncOp) 744 // If a later write overwrites the original, take it 745 // out of the unmerged created list so it can be 746 // properly unreferenced. 747 if !unrefedOrig && isSyncOp { 748 unrefedOrig = true 749 delete(unmergedChains.createdOriginals, mergedOriginal) 750 } 751 } 752 } 753 // Then add this create's path. 754 newUnmergedPaths = append(newUnmergedPaths, newPath) 755 } 756 757 // Remove the unneeded create ops 758 if len(toDrop) > 0 { 759 newOps := make([]op, 0, len(unmergedChain.ops)-len(toDrop)) 760 for i, op := range unmergedChain.ops { 761 if toDrop[i] { 762 cr.log.CDebugf(ctx, 763 "Dropping double create unmerged operation: %s", op) 764 } else { 765 newOps = append(newOps, op) 766 } 767 } 768 unmergedChain.ops = newOps 769 } 770 771 return newUnmergedPaths, nil 772} 773 774// findCreatedDirsToMerge finds directories that were created in both 775// the unmerged and merged branches, and resets the original unmerged 776// pointer to match the original merged pointer. It returns a slice of 777// new unmerged paths that need to be combined with the unmergedPaths 778// slice. 779func (cr *ConflictResolver) findCreatedDirsToMerge(ctx context.Context, 780 unmergedPaths []data.Path, unmergedChains, mergedChains *crChains) ( 781 []data.Path, error) { 782 var newUnmergedPaths []data.Path 783 for _, unmergedPath := range unmergedPaths { 784 unmergedChain, ok := 785 unmergedChains.byMostRecent[unmergedPath.TailPointer()] 786 if !ok { 787 return nil, fmt.Errorf("findCreatedDirsToMerge: No unmerged chain "+ 788 "for most recent %v", unmergedPath.TailPointer()) 789 } 790 791 newPaths, err := cr.checkPathForMerge(ctx, unmergedChain, unmergedPath, 792 unmergedChains, mergedChains) 793 if err != nil { 794 return nil, err 795 } 796 newUnmergedPaths = append(newUnmergedPaths, newPaths...) 797 } 798 return newUnmergedPaths, nil 799} 800 801type createMapKey struct { 802 ptr data.BlockPointer 803 name string 804} 805 806// addChildBlocksIfIndirectFile adds refblocks for all child blocks of 807// the given file. It will return an error if called with a pointer 808// that doesn't represent a file. 809func (cr *ConflictResolver) addChildBlocksIfIndirectFile( 810 ctx context.Context, lState *kbfssync.LockState, unmergedChains *crChains, 811 currPath data.Path, op op) error { 812 // For files with indirect pointers, add all child blocks 813 // as refblocks for the re-created file. 814 infos, err := cr.fbo.blocks.GetIndirectFileBlockInfos( 815 ctx, lState, unmergedChains.mostRecentChainMDInfo, currPath) 816 if err != nil { 817 return err 818 } 819 if len(infos) > 0 { 820 cr.log.CDebugf(ctx, "Adding child pointers for recreated "+ 821 "file %s", currPath) 822 for _, info := range infos { 823 op.AddRefBlock(info.BlockPointer) 824 } 825 } 826 return nil 827} 828 829// resolvedMergedPathTail takes an unmerged path, and returns as much 830// of the tail-end of the corresponding merged path that it can, using 831// only information within the chains. It may not be able to return a 832// complete chain if, for example, a directory was changed in the 833// unmerged branch but not in the merged branch, and so the merged 834// chain would not have enough information to construct the merged 835// branch completely. This function returns the partial path, as well 836// as the most recent pointer to the first changed node in the merged 837// chains (which can be subsequently used to find the beginning of the 838// merged path). 839// 840// The given unmerged path should be for a node that wasn't created 841// during the unmerged branch. 842// 843// It is also possible for directories used in the unmerged path to 844// have been completely removed from the merged path. In this case, 845// they need to be recreated. So this function also returns a slice 846// of create ops that will need to be replayed in the merged branch 847// for the conflicts to be resolved; all of these ops have their 848// writer info set to the given one. 849func (cr *ConflictResolver) resolveMergedPathTail(ctx context.Context, 850 lState *kbfssync.LockState, unmergedPath data.Path, 851 unmergedChains, mergedChains *crChains, 852 currUnmergedWriterInfo writerInfo) ( 853 data.Path, data.BlockPointer, []*createOp, error) { 854 unmergedOriginal, err := 855 unmergedChains.originalFromMostRecent(unmergedPath.TailPointer()) 856 if err != nil { 857 cr.log.CDebugf(ctx, "Couldn't find original pointer for %v", 858 unmergedPath.TailPointer()) 859 return data.Path{}, data.BlockPointer{}, nil, err 860 } 861 862 var recreateOps []*createOp // fill in backwards, and reverse at the end 863 currOriginal := unmergedOriginal 864 currPath := unmergedPath 865 mergedPath := data.Path{ 866 FolderBranch: unmergedPath.FolderBranch, 867 Path: nil, // fill in backwards, and reverse at the end 868 ChildObfuscator: cr.fbo.makeObfuscator(), 869 } 870 871 // First find the earliest merged parent. 872 for mergedChains.isDeleted(currOriginal) { 873 cr.log.CDebugf(ctx, "%v was deleted in the merged branch (%s)", 874 currOriginal, currPath) 875 if !currPath.HasValidParent() { 876 return data.Path{}, data.BlockPointer{}, nil, 877 fmt.Errorf("Couldn't find valid merged parent path for %v", 878 unmergedOriginal) 879 } 880 881 // If this node has been deleted, we need to search 882 // backwards in the path to find the latest node that 883 // hasn't been deleted and re-recreate nodes upward from 884 // there. 885 name := currPath.TailName() 886 mergedPath.Path = append(mergedPath.Path, data.PathNode{ 887 BlockPointer: currOriginal, 888 Name: name, 889 }) 890 parentPath := *currPath.ParentPath() 891 parentOriginal, err := 892 unmergedChains.originalFromMostRecent(parentPath.TailPointer()) 893 if err != nil { 894 cr.log.CDebugf(ctx, "Couldn't find original pointer for %v", 895 parentPath.TailPointer()) 896 return data.Path{}, data.BlockPointer{}, nil, err 897 } 898 899 // Drop the merged rmOp since we're recreating it, and we 900 // don't want to replay that notification locally. 901 if mergedChain, ok := mergedChains.byOriginal[parentOriginal]; ok { 902 mergedMostRecent, err := 903 mergedChains.mostRecentFromOriginalOrSame(currOriginal) 904 if err != nil { 905 return data.Path{}, data.BlockPointer{}, nil, err 906 } 907 outer: 908 for i, op := range mergedChain.ops { 909 ro, ok := op.(*rmOp) 910 if !ok { 911 continue 912 } 913 // Use the unref'd pointer, and not the name, to identify 914 // the operation, since renames might have happened on the 915 // merged branch. 916 for _, unref := range ro.Unrefs() { 917 if unref != mergedMostRecent { 918 continue 919 } 920 921 mergedChain.ops = 922 append(mergedChain.ops[:i], mergedChain.ops[i+1:]...) 923 break outer 924 } 925 } 926 } else { 927 // If there's no chain, then likely a previous resolution 928 // removed an entire directory tree, and so the individual 929 // rm operations aren't listed. In that case, there's no 930 // rm op to remove. 931 cr.log.CDebugf(ctx, "No corresponding merged chain for parent "+ 932 "%v; skipping rm removal", parentOriginal) 933 } 934 935 de, err := cr.fbo.blocks.GetEntry( 936 ctx, lState, unmergedChains.mostRecentChainMDInfo, currPath) 937 if err != nil { 938 return data.Path{}, data.BlockPointer{}, nil, err 939 } 940 co, err := newCreateOp(name.Plaintext(), parentOriginal, de.Type) 941 if err != nil { 942 return data.Path{}, data.BlockPointer{}, nil, err 943 } 944 co.AddSelfUpdate(parentOriginal) 945 co.setFinalPath(parentPath) 946 co.AddRefBlock(currOriginal) 947 co.setWriterInfo(currUnmergedWriterInfo) 948 949 if co.Type != data.Dir { 950 err = cr.addChildBlocksIfIndirectFile(ctx, lState, 951 unmergedChains, currPath, co) 952 if err != nil { 953 return data.Path{}, data.BlockPointer{}, nil, err 954 } 955 956 // Delete any sync/setattr ops on the removed, merged file. 957 if mergedChain, ok := mergedChains.byOriginal[currOriginal]; ok { 958 mergedChains.removeChain(mergedChain.mostRecent) 959 } 960 } 961 962 // If this happens to have been renamed on the unmerged 963 // branch, drop the rm half of the rename operation; just 964 // leave it as a create. 965 if ri, ok := unmergedChains.renamedOriginals[currOriginal]; ok { 966 oldParent, ok := unmergedChains.byOriginal[ri.originalOldParent] 967 if !ok { 968 cr.log.CDebugf(ctx, "Couldn't find chain for original "+ 969 "old parent: %v", ri.originalOldParent) 970 return data.Path{}, data.BlockPointer{}, nil, 971 errors.WithStack(NoChainFoundError{ri.originalOldParent}) 972 } 973 for _, op := range oldParent.ops { 974 ro, ok := op.(*rmOp) 975 if !ok { 976 continue 977 } 978 if ro.OldName == ri.oldName { 979 ro.dropThis = true 980 break 981 } 982 } 983 984 // Replace the create op with the new recreate op, 985 // which contains the proper refblock. 986 newParent, ok := unmergedChains.byOriginal[ri.originalNewParent] 987 if !ok { 988 cr.log.CDebugf(ctx, "Couldn't find chain for original new "+ 989 "parent: %v", ri.originalNewParent) 990 return data.Path{}, data.BlockPointer{}, nil, 991 errors.WithStack(NoChainFoundError{ri.originalNewParent}) 992 } 993 for i, op := range newParent.ops { 994 oldCo, ok := op.(*createOp) 995 if !ok { 996 continue 997 } 998 if oldCo.NewName == ri.newName { 999 newParent.ops[i] = co 1000 break 1001 } 1002 } 1003 } else { 1004 recreateOps = append(recreateOps, co) 1005 } 1006 1007 currOriginal = parentOriginal 1008 currPath = parentPath 1009 } 1010 1011 // Now we have the latest pointer along the path that is 1012 // shared between the branches. Our next step is to find the 1013 // current merged path to the most recent version of that 1014 // original. We can do that as follows: 1015 // * If the pointer has been changed in the merged branch, we 1016 // can search for it later using fbo.blocks.SearchForNodes 1017 // * If it hasn't been changed, check if it has been renamed to 1018 // somewhere else. If so, use fbo.blocks.SearchForNodes on 1019 // that parent later. 1020 // * Otherwise, iterate up the path towards the root. 1021 var mostRecent data.BlockPointer 1022 for i := len(currPath.Path) - 1; i >= 0; i-- { 1023 currOriginal, err := unmergedChains.originalFromMostRecent( 1024 currPath.Path[i].BlockPointer) 1025 if err != nil { 1026 cr.log.CDebugf(ctx, "Couldn't find original pointer for %v", 1027 currPath.Path[i]) 1028 return data.Path{}, data.BlockPointer{}, nil, err 1029 } 1030 1031 // Has it changed in the merged branch? 1032 mostRecent, err = mergedChains.mostRecentFromOriginal(currOriginal) 1033 if err == nil { 1034 break 1035 } 1036 1037 mergedPath.Path = append(mergedPath.Path, data.PathNode{ 1038 BlockPointer: currOriginal, 1039 Name: currPath.Path[i].Name, 1040 }) 1041 1042 // Has it been renamed? 1043 if originalParent, newName, ok := 1044 mergedChains.renamedParentAndName(currOriginal); ok { 1045 cr.log.CDebugf(ctx, "%v has been renamed in the merged branch", 1046 currOriginal) 1047 mostRecentParent, err := 1048 mergedChains.mostRecentFromOriginal(originalParent) 1049 if err != nil { 1050 cr.log.CDebugf(ctx, "Couldn't find original pointer for %v", 1051 originalParent) 1052 return data.Path{}, data.BlockPointer{}, nil, err 1053 } 1054 mostRecent = mostRecentParent 1055 // update the name for this renamed node 1056 mergedPath.Path[len(mergedPath.Path)-1].Name = 1057 data.NewPathPartString(newName, mergedPath.Obfuscator()) 1058 break 1059 } 1060 } 1061 1062 // reverse the merged path 1063 for i, j := 0, len(mergedPath.Path)-1; i < j; i, j = i+1, j-1 { 1064 mergedPath.Path[i], mergedPath.Path[j] = 1065 mergedPath.Path[j], mergedPath.Path[i] 1066 } 1067 1068 // reverse recreateOps 1069 for i, j := 0, len(recreateOps)-1; i < j; i, j = i+1, j-1 { 1070 recreateOps[i], recreateOps[j] = recreateOps[j], recreateOps[i] 1071 } 1072 1073 return mergedPath, mostRecent, recreateOps, nil 1074} 1075 1076// resolveMergedPaths maps each tail most recent pointer for all the 1077// given unmerged paths to a corresponding path in the merged branch. 1078// The merged branch may be missing some nodes that have been deleted; 1079// in that case, the merged path will contain placeholder path nodes 1080// using the original pointers for those directories. 1081// 1082// This function also returns a set of createOps that can be used to 1083// recreate the missing directories in the merged branch. If the 1084// parent directory needing the create has been deleted, then the 1085// unref ptr in the createOp contains the original pointer for the 1086// directory rather than the most recent merged pointer. 1087// 1088// It also potentially returns a new slice of unmerged paths that the 1089// caller should combine with the existing slice, corresponding to 1090// deleted unmerged chains that still have relevant operations to 1091// resolve. 1092func (cr *ConflictResolver) resolveMergedPaths(ctx context.Context, 1093 lState *kbfssync.LockState, unmergedPaths []data.Path, 1094 unmergedChains, mergedChains *crChains, 1095 currUnmergedWriterInfo writerInfo) ( 1096 map[data.BlockPointer]data.Path, []*createOp, []data.Path, error) { 1097 // maps each most recent unmerged pointer to the corresponding 1098 // most recent merged path. 1099 mergedPaths := make(map[data.BlockPointer]data.Path) 1100 1101 chainsToSearchFor := make(map[data.BlockPointer][]data.BlockPointer) 1102 var ptrs []data.BlockPointer 1103 1104 // While we're at it, find any deleted unmerged directory chains 1105 // containing operations, where the corresponding merged chain has 1106 // changed. The unmerged rm ops will need to be re-applied in 1107 // that case. 1108 var newUnmergedPaths []data.Path 1109 for original, unmergedChain := range unmergedChains.byOriginal { 1110 if !unmergedChains.isDeleted(original) || len(unmergedChain.ops) == 0 || 1111 unmergedChain.isFile() { 1112 continue 1113 } 1114 mergedChain, ok := mergedChains.byOriginal[original] 1115 if !ok || len(mergedChain.ops) == 0 || 1116 mergedChains.isDeleted(original) { 1117 continue 1118 } 1119 1120 cr.log.CDebugf(ctx, "A modified unmerged path %v was deleted but "+ 1121 "also modified in the merged branch %v", 1122 unmergedChain.mostRecent, mergedChain.mostRecent) 1123 1124 // We know that everything in the directory has been removed, 1125 // so only rm ops matter. 1126 var newOps []op 1127 for _, op := range unmergedChain.ops { 1128 if rop, ok := op.(*rmOp); ok { 1129 newOps = append(newOps, rop) 1130 } 1131 } 1132 unmergedChain.ops = newOps 1133 1134 // Fake the unmerged path, it doesn't matter 1135 unmergedPath := data.Path{ 1136 FolderBranch: cr.fbo.folderBranch, 1137 Path: []data.PathNode{ 1138 {BlockPointer: unmergedChain.mostRecent}, 1139 }, 1140 ChildObfuscator: cr.fbo.makeObfuscator(), 1141 } 1142 chainsToSearchFor[mergedChain.mostRecent] = 1143 append(chainsToSearchFor[mergedChain.mostRecent], 1144 unmergedChain.mostRecent) 1145 ptrs = append(ptrs, mergedChain.mostRecent) 1146 newUnmergedPaths = append(newUnmergedPaths, unmergedPath) 1147 } 1148 1149 // Skip out early if there's nothing to do. 1150 if len(unmergedPaths) == 0 && len(ptrs) == 0 { 1151 return mergedPaths, nil, nil, nil 1152 } 1153 1154 // For each unmerged path, find the corresponding most recent 1155 // pointer in the merged path. Track which entries need to be 1156 // re-created. 1157 var recreateOps []*createOp 1158 createsSeen := make(map[createMapKey]bool) 1159 // maps a merged most recent pointer to the set of unmerged most 1160 // recent pointers that need some of their path filled in. 1161 for _, p := range unmergedPaths { 1162 mergedPath, mostRecent, ops, err := cr.resolveMergedPathTail( 1163 ctx, lState, p, unmergedChains, mergedChains, 1164 currUnmergedWriterInfo) 1165 if err != nil { 1166 return nil, nil, nil, err 1167 } 1168 1169 // Save any recreateOps we've haven't seen yet. 1170 for _, op := range ops { 1171 key := createMapKey{op.Dir.Unref, op.NewName} 1172 if _, ok := createsSeen[key]; ok { 1173 continue 1174 } 1175 createsSeen[key] = true 1176 recreateOps = append(recreateOps, op) 1177 } 1178 1179 // At the end of this process, we are left with a merged path 1180 // that begins just after mostRecent. We will fill this in 1181 // later with the searchFromNodes result. 1182 mergedPaths[p.TailPointer()] = mergedPath 1183 if !mergedPath.IsValid() { 1184 // Temporary debugging for KBFS-2507. 1185 cr.log.CDebugf(ctx, "Adding invalid merged path for %v "+ 1186 "(may be temporary)", p.TailPointer()) 1187 } 1188 1189 if mostRecent.IsInitialized() { 1190 // Remember to fill in the corresponding mergedPath once we 1191 // get mostRecent's full path. 1192 chainsToSearchFor[mostRecent] = 1193 append(chainsToSearchFor[mostRecent], p.TailPointer()) 1194 } 1195 } 1196 1197 // Now we can search for all the merged paths that need to be 1198 // updated due to unmerged operations. Start with a clean node 1199 // cache for the merged branch. 1200 newPtrs := make(map[data.BlockPointer]bool) 1201 for ptr := range mergedChains.byMostRecent { 1202 newPtrs[ptr] = true 1203 } 1204 for ptr := range chainsToSearchFor { 1205 ptrs = append(ptrs, ptr) 1206 } 1207 1208 if len(ptrs) == 0 { 1209 // Nothing to search for 1210 return mergedPaths, recreateOps, newUnmergedPaths, nil 1211 } 1212 1213 mergedNodeCache := newNodeCacheStandard(cr.fbo.folderBranch) 1214 mergedNodeCache.SetObfuscatorMaker(cr.fbo.makeObfuscator) 1215 nodeMap, _, err := cr.fbo.blocks.SearchForNodes( 1216 ctx, mergedNodeCache, ptrs, newPtrs, 1217 mergedChains.mostRecentChainMDInfo, 1218 mergedChains.mostRecentChainMDInfo.GetRootDirEntry().BlockPointer) 1219 if err != nil { 1220 return nil, nil, nil, err 1221 } 1222 1223 for ptr, n := range nodeMap { 1224 if n == nil { 1225 // All the pointers we're looking for should definitely be 1226 // findable in the merged branch somewhere. 1227 return nil, nil, nil, NodeNotFoundError{ptr} 1228 } 1229 1230 p := mergedNodeCache.PathFromNode(n) 1231 for _, unmergedMostRecent := range chainsToSearchFor[ptr] { 1232 // Prepend the found path to the existing path 1233 mergedPath := mergedPaths[unmergedMostRecent] 1234 if !mergedPath.IsValid() { 1235 // Temporary debugging for KBFS-2507. 1236 cr.log.CDebugf(ctx, "Populating merged path for %v with %v", 1237 unmergedMostRecent, p.Path) 1238 } 1239 1240 newPath := make([]data.PathNode, len(p.Path)+len(mergedPath.Path)) 1241 copy(newPath[:len(p.Path)], p.Path) 1242 copy(newPath[len(p.Path):], mergedPath.Path) 1243 mergedPath.FolderBranch = cr.fbo.folderBranch 1244 mergedPath.Path = newPath 1245 mergedPaths[unmergedMostRecent] = mergedPath 1246 1247 // update the final paths for those corresponding merged 1248 // chains 1249 mergedMostRecent := mergedPath.TailPointer() 1250 chain, ok := mergedChains.byMostRecent[mergedMostRecent] 1251 if !ok { 1252 // it's ok for the merged path not to exist because we 1253 // might still need to create it. 1254 continue 1255 } 1256 for _, op := range chain.ops { 1257 op.setFinalPath(mergedPath) 1258 } 1259 } 1260 } 1261 1262 return mergedPaths, recreateOps, newUnmergedPaths, nil 1263} 1264 1265// buildChainsAndPaths make crChains for both the unmerged and merged 1266// branches since the branch point, the corresponding full paths for 1267// those changes, any new recreate ops, and returns the MDs used to 1268// compute all this. Note that even if err is nil, the merged MD list 1269// might be non-nil to allow for better error handling. 1270// 1271// This always returns the merged MDs, even in an error case, to allow 1272// the caller's error-handling code to unstage if necessary. 1273func (cr *ConflictResolver) buildChainsAndPaths( 1274 ctx context.Context, lState *kbfssync.LockState, writerLocked bool) ( 1275 unmergedChains, mergedChains *crChains, unmergedPaths []data.Path, 1276 mergedPaths map[data.BlockPointer]data.Path, recreateOps []*createOp, 1277 unmerged, merged []ImmutableRootMetadata, err error) { 1278 // Fetch the merged and unmerged MDs 1279 unmerged, merged, err = cr.getMDs(ctx, lState, writerLocked) 1280 if err != nil { 1281 return nil, nil, nil, nil, nil, nil, nil, err 1282 } 1283 1284 if len(unmerged) == 0 { 1285 cr.log.CDebugf(ctx, "Skipping merge process due to empty MD list") 1286 return nil, nil, nil, nil, nil, nil, merged, nil 1287 } 1288 1289 // Update the current input to reflect the MDs we'll actually be 1290 // working with. 1291 err = cr.updateCurrInput(ctx, unmerged, merged) 1292 if err != nil { 1293 return nil, nil, nil, nil, nil, nil, merged, err 1294 } 1295 1296 // Canceled before we start the heavy lifting? 1297 err = cr.checkDone(ctx) 1298 if err != nil { 1299 return nil, nil, nil, nil, nil, nil, merged, err 1300 } 1301 1302 // Make the chains 1303 unmergedChains, mergedChains, err = cr.makeChains(ctx, unmerged, merged) 1304 if err != nil { 1305 return nil, nil, nil, nil, nil, nil, merged, err 1306 } 1307 1308 // TODO: if the root node didn't change in either chain, we can 1309 // short circuit the rest of the process with a really easy 1310 // merge... 1311 1312 // Get the full path for every most recent unmerged pointer with a 1313 // chain of unmerged operations, and which was not created or 1314 // deleted within in the unmerged branch. 1315 unmergedPaths, err = unmergedChains.getPaths(ctx, &cr.fbo.blocks, 1316 cr.log, cr.fbo.nodeCache, false, cr.config.Mode().IsTestMode()) 1317 if err != nil { 1318 return nil, nil, nil, nil, nil, nil, merged, err 1319 } 1320 1321 // Add in any directory paths that were created in both branches. 1322 newUnmergedPaths, err := cr.findCreatedDirsToMerge(ctx, unmergedPaths, 1323 unmergedChains, mergedChains) 1324 if err != nil { 1325 return nil, nil, nil, nil, nil, nil, merged, err 1326 } 1327 unmergedPaths = append(unmergedPaths, newUnmergedPaths...) 1328 if len(newUnmergedPaths) > 0 { 1329 sort.Sort(crSortedPaths(unmergedPaths)) 1330 } 1331 1332 // Mark the recreate ops as being authored by the current user. 1333 kbpki := cr.config.KBPKI() 1334 session, err := kbpki.GetCurrentSession(ctx) 1335 if err != nil { 1336 return nil, nil, nil, nil, nil, nil, merged, err 1337 } 1338 1339 currUnmergedWriterInfo := newWriterInfo( 1340 session.UID, session.VerifyingKey, unmerged[len(unmerged)-1].Revision(), 1341 cr.fbo.oa()) 1342 1343 // Find the corresponding path in the merged branch for each of 1344 // these unmerged paths, and the set of any createOps needed to 1345 // apply these unmerged operations in the merged branch. 1346 mergedPaths, recreateOps, newUnmergedPaths, err = cr.resolveMergedPaths( 1347 ctx, lState, unmergedPaths, unmergedChains, mergedChains, 1348 currUnmergedWriterInfo) 1349 if err != nil { 1350 return nil, nil, nil, nil, nil, nil, merged, err 1351 } 1352 unmergedPaths = append(unmergedPaths, newUnmergedPaths...) 1353 if len(newUnmergedPaths) > 0 { 1354 sort.Sort(crSortedPaths(unmergedPaths)) 1355 } 1356 1357 return unmergedChains, mergedChains, unmergedPaths, mergedPaths, 1358 recreateOps, unmerged, merged, nil 1359} 1360 1361// addRecreateOpsToUnmergedChains inserts each recreateOp, into its 1362// appropriate unmerged chain, creating one if it doesn't exist yet. 1363// It also adds entries as necessary to mergedPaths, and returns a 1364// slice of new unmergedPaths to be added. 1365func (cr *ConflictResolver) addRecreateOpsToUnmergedChains(ctx context.Context, 1366 recreateOps []*createOp, unmergedChains, mergedChains *crChains, 1367 mergedPaths map[data.BlockPointer]data.Path) ([]data.Path, error) { 1368 if len(recreateOps) == 0 { 1369 return nil, nil 1370 } 1371 1372 // First create a lookup table that maps every block pointer in 1373 // every merged path to a corresponding key in the mergedPaths map. 1374 keys := make(map[data.BlockPointer]data.BlockPointer) 1375 for ptr, p := range mergedPaths { 1376 for _, node := range p.Path { 1377 keys[node.BlockPointer] = ptr 1378 } 1379 } 1380 1381 var newUnmergedPaths []data.Path 1382 for _, rop := range recreateOps { 1383 // If rop.Dir.Unref is a merged most recent pointer, look up the 1384 // original. Otherwise rop.Dir.Unref is the original. Use the 1385 // original to look up the appropriate unmerged chain and stick 1386 // this op at the front. 1387 origTargetPtr, err := 1388 mergedChains.originalFromMostRecentOrSame(rop.Dir.Unref) 1389 if err != nil { 1390 return nil, err 1391 } 1392 1393 chain, ok := unmergedChains.byOriginal[origTargetPtr] 1394 if !ok { 1395 return nil, fmt.Errorf("recreateOp for %v has no chain", 1396 origTargetPtr) 1397 } 1398 if len(chain.ops) == 0 { 1399 newUnmergedPaths = append(newUnmergedPaths, rop.getFinalPath()) 1400 } 1401 chain.ops = append([]op{rop}, chain.ops...) 1402 1403 // Look up the corresponding unmerged most recent pointer, and 1404 // check whether there's a merged path for it yet. If not, 1405 // create one by looking it up in the lookup table (created 1406 // above) and taking the appropriate subpath. 1407 _, ok = mergedPaths[chain.mostRecent] 1408 if !ok { 1409 mergedMostRecent := chain.original 1410 if !mergedChains.isDeleted(chain.original) { 1411 if mChain, ok := mergedChains.byOriginal[chain.original]; ok { 1412 mergedMostRecent = mChain.mostRecent 1413 } 1414 } 1415 key, ok := keys[mergedMostRecent] 1416 if !ok { 1417 return nil, fmt.Errorf("Couldn't find a merged path "+ 1418 "containing the target of a recreate op: %v", 1419 mergedMostRecent) 1420 } 1421 currPath := mergedPaths[key] 1422 for currPath.TailPointer() != mergedMostRecent && 1423 currPath.HasValidParent() { 1424 currPath = *currPath.ParentPath() 1425 } 1426 mergedPaths[chain.mostRecent] = currPath 1427 } 1428 } 1429 1430 return newUnmergedPaths, nil 1431} 1432 1433// convertCreateIntoSymlink finds the create operation for the given 1434// node in the chain, and makes it into one that creates a new symlink 1435// (for directories) or a file copy. It also removes the 1436// corresponding remove operation from the old parent chain. 1437func (cr *ConflictResolver) convertCreateIntoSymlinkOrCopy(ctx context.Context, 1438 ptr data.BlockPointer, info renameInfo, chain *crChain, 1439 unmergedChains, mergedChains *crChains, symPath string) error { 1440 found := false 1441outer: 1442 for _, op := range chain.ops { 1443 if cop, ok := op.(*createOp); ok { 1444 if !cop.renamed || cop.NewName != info.newName { 1445 continue 1446 } 1447 1448 oldType := cop.Type 1449 if cop.Type == data.Dir { 1450 cop.Type = data.Sym 1451 cop.crSymPath = symPath 1452 cop.RefBlocks = nil 1453 } else { 1454 cop.forceCopy = true 1455 } 1456 cop.renamed = false 1457 1458 newInfo := renameInfo{ 1459 originalOldParent: info.originalNewParent, 1460 oldName: info.newName, 1461 originalNewParent: info.originalOldParent, 1462 newName: info.oldName, 1463 } 1464 if newInfo2, ok := mergedChains.renamedOriginals[ptr]; ok { 1465 // If this node was already moved in the merged 1466 // branch, we need to tweak the merged branch's rename 1467 // info so that it looks like it's being renamed from 1468 // the new unmerged location. 1469 newInfo = newInfo2 1470 newInfo.originalOldParent = info.originalNewParent 1471 newInfo.oldName = info.newName 1472 } else { 1473 // invert the op in the merged chains 1474 invertCreate, err := newRmOp(info.newName, 1475 info.originalNewParent, oldType) 1476 if err != nil { 1477 return err 1478 } 1479 err = invertCreate.Dir.setRef(info.originalNewParent) 1480 if err != nil { 1481 return err 1482 } 1483 invertRm, err := newCreateOp(info.oldName, 1484 info.originalOldParent, cop.Type) 1485 if err != nil { 1486 return err 1487 } 1488 err = invertRm.Dir.setRef(info.originalOldParent) 1489 if err != nil { 1490 return err 1491 } 1492 invertRm.renamed = true 1493 invertRm.AddRefBlock(ptr) 1494 1495 mergedNewMostRecent, err := mergedChains. 1496 mostRecentFromOriginalOrSame(info.originalNewParent) 1497 if err != nil { 1498 return err 1499 } 1500 mergedOldMostRecent, err := mergedChains. 1501 mostRecentFromOriginalOrSame(info.originalOldParent) 1502 if err != nil { 1503 return err 1504 } 1505 err = prependOpsToChain( 1506 mergedOldMostRecent, mergedChains, invertRm) 1507 if err != nil { 1508 return err 1509 } 1510 err = prependOpsToChain( 1511 mergedNewMostRecent, mergedChains, invertCreate) 1512 if err != nil { 1513 return err 1514 } 1515 } 1516 cr.log.CDebugf(ctx, "Putting new merged rename info "+ 1517 "%v -> %v (symPath: %v)", ptr, newInfo, 1518 data.NewPathPartString(symPath, chain.obfuscator)) 1519 mergedChains.renamedOriginals[ptr] = newInfo 1520 1521 // Fix up the corresponding rmOp to make sure 1522 // that it gets dropped 1523 oldParentChain := 1524 unmergedChains.byOriginal[info.originalOldParent] 1525 for _, oldOp := range oldParentChain.ops { 1526 ro, ok := oldOp.(*rmOp) 1527 if !ok { 1528 continue 1529 } 1530 if ro.OldName == info.oldName { 1531 // No need to copy since this createOp 1532 // must have been created as part of 1533 // conflict resolution. 1534 ro.dropThis = true 1535 break 1536 } 1537 } 1538 1539 found = true 1540 break outer 1541 } 1542 } 1543 if !found { 1544 return fmt.Errorf("fixRenameConflicts: couldn't find "+ 1545 "rename op corresponding to %v,%s", ptr, info.newName) 1546 } 1547 return nil 1548} 1549 1550// crConflictCheckQuick checks whether the two given chains have any 1551// direct conflicts. TODO: currently this is a little pessimistic 1552// because it assumes any set attrs are in conflict, when in reality 1553// they can be for different attributes, or the same attribute with 1554// the same value. 1555func crConflictCheckQuick(unmergedChain, mergedChain *crChain) bool { 1556 return unmergedChain != nil && mergedChain != nil && 1557 ((unmergedChain.hasSyncOp() && mergedChain.hasSyncOp()) || 1558 (unmergedChain.hasSetAttrOp() && mergedChain.hasSetAttrOp())) 1559} 1560 1561func (cr *ConflictResolver) getSingleUnmergedPath( 1562 ctx context.Context, unmergedChains *crChains, chain *crChain) ( 1563 data.Path, error) { 1564 // Reuse some code by creating a new chains object 1565 // consisting of only this node. 1566 newChains := newCRChainsEmpty(cr.fbo.makeObfuscator) 1567 newChains.byOriginal[chain.original] = chain 1568 newChains.byMostRecent[chain.mostRecent] = chain 1569 // Fake out the rest of the chains to populate newPtrs. 1570 for _, c := range unmergedChains.byOriginal { 1571 if c.original == chain.original { 1572 continue 1573 } 1574 newChain := &crChain{ 1575 original: c.original, 1576 mostRecent: c.mostRecent, 1577 obfuscator: newChains.makeObfuscator(), 1578 } 1579 newChains.byOriginal[c.original] = newChain 1580 newChains.byMostRecent[c.mostRecent] = newChain 1581 } 1582 newChains.mostRecentChainMDInfo = unmergedChains.mostRecentChainMDInfo 1583 unmergedPaths, err := newChains.getPaths(ctx, &cr.fbo.blocks, 1584 cr.log, cr.fbo.nodeCache, false, cr.config.Mode().IsTestMode()) 1585 if err != nil { 1586 return data.Path{}, err 1587 } 1588 1589 if len(unmergedPaths) != 1 { 1590 return data.Path{}, fmt.Errorf("Couldn't find the unmerged path for %v", 1591 chain.original) 1592 } 1593 return unmergedPaths[0], nil 1594} 1595 1596// fixRenameConflicts checks every unmerged createOp associated with a 1597// rename to see if it will cause a cycle. If so, it makes it a 1598// symlink create operation instead. It also checks whether a 1599// particular node had been renamed in both branches; if so, it will 1600// copy files, and use symlinks for directories. 1601func (cr *ConflictResolver) fixRenameConflicts(ctx context.Context, 1602 unmergedChains, mergedChains *crChains, 1603 mergedPaths map[data.BlockPointer]data.Path) ([]data.Path, error) { 1604 // For every renamed block pointer in the unmerged chains: 1605 // * Check if any BlockPointer in its merged path contains a relative of 1606 // itself 1607 // * If so, replace the corresponding unmerged create operation with a 1608 // symlink creation to the new merged path instead. 1609 // So, if in the merged branch someone did `mv b/ a/` and in the unmerged 1610 // branch someone did `mv a/ b/`, the conflict resolution would end up with 1611 // `a/b/a` where the second a is a symlink to "../". 1612 // 1613 // To calculate what the symlink should be, consider the following: 1614 // * The unmerged path for the new parent of ptr P is u_1/u_2/.../u_n 1615 // * u_i is the largest i <= n such that the corresponding block 1616 // can be mapped to a node in merged branch (pointer m_j). 1617 // * The full path to m_j in the merged branch is m_1/m_2/m_3/.../m_j 1618 // * For a rename cycle to occur, some m_x where x <= j must be a 1619 // descendant of P's original pointer. 1620 // * The full merged path to the parent of the second copy of P will 1621 // then be: m_1/m_2/.../m_x/.../m_j/u_i+1/.../u_n. 1622 // * Then, the symlink to put under P's name in u_n is "../"*((n-i)+(j-x)) 1623 // In the case that u_n is a directory that was newly-created in the 1624 // unmerged branch, we also need to construct a complete corresponding 1625 // merged path, for use in later stages (like executing actions). This 1626 // merged path is just m_1/.../m_j/u_i+1/.../u_n, using the most recent 1627 // unmerged pointers. 1628 var newUnmergedPaths []data.Path 1629 var removeRenames []data.BlockPointer 1630 var doubleRenames []data.BlockPointer // merged most recent ptrs 1631 for ptr, info := range unmergedChains.renamedOriginals { 1632 if unmergedChains.isDeleted(ptr) { 1633 continue 1634 } 1635 1636 // Also, we need to get the merged paths for anything that was 1637 // renamed in both branches, if they are different. 1638 if mergedInfo, ok := mergedChains.renamedOriginals[ptr]; ok && 1639 (info.originalNewParent != mergedInfo.originalNewParent || 1640 info.newName != mergedInfo.newName) { 1641 mergedMostRecent, err := 1642 mergedChains.mostRecentFromOriginalOrSame(ptr) 1643 if err != nil { 1644 return nil, err 1645 } 1646 1647 doubleRenames = append(doubleRenames, mergedMostRecent) 1648 continue 1649 } 1650 1651 // If this node was modified in both branches, we need to fork 1652 // the node, so we can get rid of the unmerged remove op and 1653 // force a copy on the create op. 1654 unmergedChain := unmergedChains.byOriginal[ptr] 1655 mergedChain := mergedChains.byOriginal[ptr] 1656 if crConflictCheckQuick(unmergedChain, mergedChain) { 1657 cr.log.CDebugf(ctx, "File that was renamed on the unmerged "+ 1658 "branch from %s -> %s has conflicting edits, forking "+ 1659 "(original ptr %v)", 1660 data.NewPathPartString(info.oldName, unmergedChain.obfuscator), 1661 data.NewPathPartString(info.newName, unmergedChain.obfuscator), 1662 ptr) 1663 oldParent := unmergedChains.byOriginal[info.originalOldParent] 1664 for _, op := range oldParent.ops { 1665 ro, ok := op.(*rmOp) 1666 if !ok { 1667 continue 1668 } 1669 if ro.OldName == info.oldName { 1670 ro.dropThis = true 1671 break 1672 } 1673 } 1674 newParent := unmergedChains.byOriginal[info.originalNewParent] 1675 for _, npOp := range newParent.ops { 1676 co, ok := npOp.(*createOp) 1677 if !ok { 1678 continue 1679 } 1680 if co.NewName == info.newName && co.renamed { 1681 co.forceCopy = true 1682 co.renamed = false 1683 co.AddRefBlock(unmergedChain.mostRecent) 1684 co.DelRefBlock(ptr) 1685 // Clear out the ops on the file itself, as we 1686 // will be doing a fresh create instead. 1687 unmergedChain.ops = nil 1688 break 1689 } 1690 } 1691 // Reset the chain of the forked file to the most recent 1692 // pointer, since we want to avoid any local notifications 1693 // linking the old version of the file to the new one. 1694 if ptr != unmergedChain.mostRecent { 1695 err := unmergedChains.changeOriginal( 1696 ptr, unmergedChain.mostRecent) 1697 if err != nil { 1698 return nil, err 1699 } 1700 unmergedChains.createdOriginals[unmergedChain.mostRecent] = true 1701 } 1702 continue 1703 } 1704 1705 // The merged path is keyed by the most recent unmerged tail 1706 // pointer. 1707 parent, err := 1708 unmergedChains.mostRecentFromOriginal(info.originalNewParent) 1709 if err != nil { 1710 return nil, err 1711 } 1712 1713 mergedPath, ok := mergedPaths[parent] 1714 unmergedWalkBack := 0 // (n-i) in the equation above 1715 var unmergedPath data.Path 1716 if !ok { 1717 // If this parent was newly created in the unmerged 1718 // branch, we need to look up its earliest parent that 1719 // existed in both branches. 1720 if !unmergedChains.isCreated(info.originalNewParent) { 1721 // There should definitely be a merged path for this 1722 // parent, since it doesn't have a create operation. 1723 return nil, fmt.Errorf("fixRenameConflicts: couldn't find "+ 1724 "merged path for %v", parent) 1725 } 1726 1727 chain := unmergedChains.byOriginal[info.originalNewParent] 1728 unmergedPath, err = cr.getSingleUnmergedPath( 1729 ctx, unmergedChains, chain) 1730 if err != nil { 1731 return nil, err 1732 } 1733 // Look backwards to find the first parent with a merged path. 1734 n := len(unmergedPath.Path) - 1 1735 for i := n; i >= 0; i-- { 1736 mergedPath, ok = mergedPaths[unmergedPath.Path[i].BlockPointer] 1737 if ok { 1738 unmergedWalkBack = n - i 1739 break 1740 } 1741 } 1742 if !ok { 1743 return nil, fmt.Errorf("fixRenameConflicts: couldn't find any "+ 1744 "merged path for any parents of %v", parent) 1745 } 1746 } 1747 1748 for x, pn := range mergedPath.Path { 1749 original, err := 1750 mergedChains.originalFromMostRecent(pn.BlockPointer) 1751 if err != nil { 1752 // This node wasn't changed in the merged branch 1753 original = pn.BlockPointer 1754 } 1755 1756 if original != ptr { 1757 continue 1758 } 1759 1760 // If any node on this path matches the renamed pointer, 1761 // we have a cycle. 1762 chain, ok := unmergedChains.byMostRecent[parent] 1763 if !ok { 1764 return nil, fmt.Errorf("fixRenameConflicts: no chain for "+ 1765 "parent %v", parent) 1766 } 1767 1768 j := len(mergedPath.Path) - 1 1769 // (j-x) in the above equation 1770 mergedWalkBack := j - x 1771 walkBack := unmergedWalkBack + mergedWalkBack 1772 1773 // Mark this as a symlink, and the resolver 1774 // will take care of making it a symlink in 1775 // the merged branch later. No need to copy 1776 // since this createOp must have been created 1777 // as part of conflict resolution. 1778 symPath := "./" + strings.Repeat("../", walkBack) 1779 cr.log.CDebugf(ctx, "Creating symlink %s at merged path %s", 1780 data.NewPathPartString(symPath, chain.obfuscator), mergedPath) 1781 1782 err = cr.convertCreateIntoSymlinkOrCopy(ctx, ptr, info, chain, 1783 unmergedChains, mergedChains, symPath) 1784 if err != nil { 1785 return nil, err 1786 } 1787 1788 if unmergedWalkBack > 0 { 1789 cr.log.CDebugf(ctx, "Adding new unmerged path %s", 1790 unmergedPath) 1791 newUnmergedPaths = append(newUnmergedPaths, 1792 unmergedPath) 1793 // Fake a merged path to make sure these 1794 // actions will be taken. 1795 mergedLen := len(mergedPath.Path) 1796 pLen := mergedLen + unmergedWalkBack 1797 p := data.Path{ 1798 FolderBranch: mergedPath.FolderBranch, 1799 Path: make([]data.PathNode, pLen), 1800 ChildObfuscator: cr.fbo.makeObfuscator(), 1801 } 1802 unmergedStart := len(unmergedPath.Path) - 1803 unmergedWalkBack 1804 copy(p.Path[:mergedLen], mergedPath.Path) 1805 copy(p.Path[mergedLen:], 1806 unmergedPath.Path[unmergedStart:]) 1807 mergedPaths[unmergedPath.TailPointer()] = p 1808 if !p.IsValid() { 1809 // Temporary debugging for KBFS-2507. 1810 cr.log.CDebugf(ctx, "Added invalid unmerged path for %v", 1811 unmergedPath.TailPointer()) 1812 } 1813 } 1814 1815 removeRenames = append(removeRenames, ptr) 1816 } 1817 } 1818 1819 // A map from merged most recent pointers of the parent 1820 // directories of files that have been forked, to a list of child 1821 // pointers within those directories that need their merged paths 1822 // fixed up. 1823 forkedFromMergedRenames := make(map[data.BlockPointer][]data.PathNode) 1824 1825 // Check the merged renames to see if any of them affect a 1826 // modified file that the unmerged branch did not rename. If we 1827 // find one, fork the file and leave the unmerged version under 1828 // its unmerged name. 1829 for ptr, info := range mergedChains.renamedOriginals { 1830 if mergedChains.isDeleted(ptr) { 1831 continue 1832 } 1833 1834 // Skip double renames, already dealt with them above. 1835 if unmergedInfo, ok := unmergedChains.renamedOriginals[ptr]; ok && 1836 (info.originalNewParent != unmergedInfo.originalNewParent || 1837 info.newName != unmergedInfo.newName) { 1838 continue 1839 } 1840 1841 // If this is a file that was modified in both branches, we 1842 // need to fork the file and tell the unmerged copy to keep 1843 // its current name. 1844 unmergedChain := unmergedChains.byOriginal[ptr] 1845 mergedChain := mergedChains.byOriginal[ptr] 1846 if crConflictCheckQuick(unmergedChain, mergedChain) { 1847 cr.log.CDebugf(ctx, "File that was renamed on the merged "+ 1848 "branch from %s -> %s has conflicting edits, forking "+ 1849 "(original ptr %v)", 1850 data.NewPathPartString(info.oldName, unmergedChain.obfuscator), 1851 data.NewPathPartString(info.newName, unmergedChain.obfuscator), 1852 ptr) 1853 var unmergedParentPath data.Path 1854 for _, op := range unmergedChain.ops { 1855 switch realOp := op.(type) { 1856 case *syncOp: 1857 realOp.keepUnmergedTailName = true 1858 unmergedParentPath = *op.getFinalPath().ParentPath() 1859 case *setAttrOp: 1860 realOp.keepUnmergedTailName = true 1861 unmergedParentPath = *op.getFinalPath().ParentPath() 1862 } 1863 } 1864 if unmergedParentPath.IsValid() { 1865 // Reset the merged path for this file back to the 1866 // merged path corresponding to the unmerged parent. 1867 // Put the merged parent path on the list of paths to 1868 // search for. 1869 unmergedParent := unmergedParentPath.TailPointer() 1870 if _, ok := mergedPaths[unmergedParent]; !ok { 1871 upOriginal := unmergedChains.originals[unmergedParent] 1872 mergedParent, err := 1873 mergedChains.mostRecentFromOriginalOrSame(upOriginal) 1874 if err != nil { 1875 return nil, err 1876 } 1877 oldPPS := data.NewPathPartString( 1878 info.oldName, unmergedParentPath.Obfuscator()) 1879 forkedFromMergedRenames[mergedParent] = 1880 append(forkedFromMergedRenames[mergedParent], 1881 data.PathNode{ 1882 BlockPointer: unmergedChain.mostRecent, 1883 Name: oldPPS, 1884 }) 1885 newUnmergedPaths = 1886 append(newUnmergedPaths, unmergedParentPath) 1887 } 1888 } 1889 } 1890 } 1891 1892 for _, ptr := range removeRenames { 1893 delete(unmergedChains.renamedOriginals, ptr) 1894 } 1895 1896 numRenamesToCheck := len(doubleRenames) + len(forkedFromMergedRenames) 1897 if numRenamesToCheck == 0 { 1898 return newUnmergedPaths, nil 1899 } 1900 1901 // Make chains for the new merged parents of all the double renames. 1902 newPtrs := make(map[data.BlockPointer]bool) 1903 ptrs := make([]data.BlockPointer, len(doubleRenames), numRenamesToCheck) 1904 copy(ptrs, doubleRenames) 1905 for ptr := range forkedFromMergedRenames { 1906 ptrs = append(ptrs, ptr) 1907 } 1908 // Fake out the rest of the chains to populate newPtrs 1909 for ptr := range mergedChains.byMostRecent { 1910 newPtrs[ptr] = true 1911 } 1912 1913 mergedNodeCache := newNodeCacheStandard(cr.fbo.folderBranch) 1914 mergedNodeCache.SetObfuscatorMaker(cr.fbo.makeObfuscator) 1915 nodeMap, _, err := cr.fbo.blocks.SearchForNodes( 1916 ctx, mergedNodeCache, ptrs, newPtrs, 1917 mergedChains.mostRecentChainMDInfo, 1918 mergedChains.mostRecentChainMDInfo.GetRootDirEntry().BlockPointer) 1919 if err != nil { 1920 return nil, err 1921 } 1922 1923 for _, ptr := range doubleRenames { 1924 // Find the merged paths 1925 node, ok := nodeMap[ptr] 1926 if !ok || node == nil { 1927 return nil, fmt.Errorf("Couldn't find merged path for "+ 1928 "doubly-renamed pointer %v", ptr) 1929 } 1930 1931 original, err := 1932 mergedChains.originalFromMostRecentOrSame(ptr) 1933 if err != nil { 1934 return nil, err 1935 } 1936 unmergedInfo, ok := unmergedChains.renamedOriginals[original] 1937 if !ok { 1938 return nil, fmt.Errorf("fixRenameConflicts: can't find the "+ 1939 "unmerged rename info for %v during double-rename resolution", 1940 original) 1941 } 1942 mergedInfo, ok := mergedChains.renamedOriginals[original] 1943 if !ok { 1944 return nil, fmt.Errorf("fixRenameConflicts: can't find the "+ 1945 "merged rename info for %v during double-rename resolution", 1946 original) 1947 } 1948 1949 // If any node on this path matches the renamed pointer, 1950 // we have a cycle. 1951 chain, ok := unmergedChains.byOriginal[unmergedInfo.originalNewParent] 1952 if !ok { 1953 return nil, fmt.Errorf("fixRenameConflicts: no chain for "+ 1954 "parent %v", unmergedInfo.originalNewParent) 1955 } 1956 1957 // For directories, the symlinks traverse down the merged path 1958 // to the first common node, and then back up to the new 1959 // parent/name. TODO: what happens when some element along 1960 // the merged path also got renamed by the unmerged branch? 1961 // The symlink would likely be wrong in that case. 1962 mergedPathOldParent, ok := mergedPaths[chain.mostRecent] 1963 if !ok { 1964 return nil, fmt.Errorf("fixRenameConflicts: couldn't find "+ 1965 "merged path for old parent %v", chain.mostRecent) 1966 } 1967 mergedPathNewParent := mergedNodeCache.PathFromNode(node) 1968 symPath := "./" 1969 newParentStart := 0 1970 outer: 1971 for i := len(mergedPathOldParent.Path) - 1; i >= 0; i-- { 1972 mostRecent := mergedPathOldParent.Path[i].BlockPointer 1973 for j, pnode := range mergedPathNewParent.Path { 1974 original, err := 1975 unmergedChains.originalFromMostRecentOrSame(mostRecent) 1976 if err != nil { 1977 return nil, err 1978 } 1979 mergedMostRecent, err := 1980 mergedChains.mostRecentFromOriginalOrSame(original) 1981 if err != nil { 1982 return nil, err 1983 } 1984 if pnode.BlockPointer == mergedMostRecent { 1985 newParentStart = j 1986 break outer 1987 } 1988 } 1989 symPath += "../" 1990 } 1991 // Move up directories starting from beyond the common parent, 1992 // to right before the actual node. 1993 for i := newParentStart + 1; i < len(mergedPathNewParent.Path)-1; i++ { 1994 symPath += mergedPathNewParent.Path[i].Name.Plaintext() + "/" 1995 } 1996 symPath += mergedInfo.newName 1997 1998 err = cr.convertCreateIntoSymlinkOrCopy(ctx, original, unmergedInfo, 1999 chain, unmergedChains, mergedChains, symPath) 2000 if err != nil { 2001 return nil, err 2002 } 2003 } 2004 2005 for ptr, pathNodes := range forkedFromMergedRenames { 2006 // Find the merged paths 2007 node, ok := nodeMap[ptr] 2008 if !ok || node == nil { 2009 return nil, fmt.Errorf("Couldn't find merged path for "+ 2010 "forked parent pointer %v", ptr) 2011 } 2012 2013 mergedPathNewParent := mergedNodeCache.PathFromNode(node) 2014 for _, pNode := range pathNodes { 2015 mergedPath := mergedPathNewParent.ChildPath( 2016 pNode.Name, pNode.BlockPointer, cr.fbo.makeObfuscator()) 2017 mergedPaths[pNode.BlockPointer] = mergedPath 2018 } 2019 } 2020 2021 return newUnmergedPaths, nil 2022} 2023 2024// addMergedRecreates drops any unmerged operations that remove a node 2025// that was modified in the merged branch, and adds a create op to the 2026// merged chain so that the node will be re-created locally. 2027func (cr *ConflictResolver) addMergedRecreates(ctx context.Context, 2028 unmergedChains, mergedChains *crChains, 2029 mostRecentMergedWriterInfo writerInfo) error { 2030 for _, unmergedChain := range unmergedChains.byMostRecent { 2031 // First check for nodes that have been deleted in the unmerged 2032 // branch, but modified in the merged branch, and drop those 2033 // unmerged operations. 2034 for _, untypedOp := range unmergedChain.ops { 2035 ro, ok := untypedOp.(*rmOp) 2036 if !ok { 2037 continue 2038 } 2039 2040 // Perhaps the rm target has been renamed somewhere else, 2041 // before eventually being deleted. In this case, we have 2042 // to look up the original by iterating over 2043 // renamedOriginals. 2044 if len(ro.Unrefs()) == 0 { 2045 for original, info := range unmergedChains.renamedOriginals { 2046 if info.originalOldParent == unmergedChain.original && 2047 info.oldName == ro.OldName && 2048 unmergedChains.isDeleted(original) { 2049 ro.AddUnrefBlock(original) 2050 break 2051 } 2052 } 2053 } 2054 2055 for _, ptr := range ro.Unrefs() { 2056 unrefOriginal, err := 2057 unmergedChains.originalFromMostRecentOrSame(ptr) 2058 if err != nil { 2059 return err 2060 } 2061 2062 if c, ok := mergedChains.byOriginal[unrefOriginal]; ok { 2063 ro.dropThis = true 2064 // Need to prepend a create here to the merged parent, 2065 // in order catch any conflicts. 2066 parentOriginal := unmergedChain.original 2067 name := ro.OldName 2068 if newParent, newName, ok := 2069 mergedChains.renamedParentAndName(unrefOriginal); ok { 2070 // It was renamed in the merged branch, so 2071 // recreate with the new parent and new name. 2072 parentOriginal = newParent 2073 name = newName 2074 } else if info, ok := 2075 unmergedChains.renamedOriginals[unrefOriginal]; ok { 2076 // It was only renamed in the old parent, so 2077 // use the old parent and original name. 2078 parentOriginal = info.originalOldParent 2079 name = info.oldName 2080 } 2081 chain, ok := mergedChains.byOriginal[parentOriginal] 2082 if !ok { 2083 return fmt.Errorf("Couldn't find chain for parent %v "+ 2084 "of merged entry %v we're trying to recreate", 2085 parentOriginal, unrefOriginal) 2086 } 2087 t := data.Dir 2088 if c.isFile() { 2089 // TODO: how to fix this up for executables 2090 // and symlinks? Only matters for checking 2091 // conflicts if something with the same name 2092 // is created on the unmerged branch. 2093 t = data.File 2094 } 2095 co, err := newCreateOp(name, chain.original, t) 2096 if err != nil { 2097 return err 2098 } 2099 err = co.Dir.setRef(chain.original) 2100 if err != nil { 2101 return err 2102 } 2103 co.AddRefBlock(c.mostRecent) 2104 co.setWriterInfo(mostRecentMergedWriterInfo) 2105 chain.ensurePath(co, chain.mostRecent) 2106 chain.ops = append([]op{co}, chain.ops...) 2107 cr.log.CDebugf(ctx, "Re-created rm'd merge-modified node "+ 2108 "%v with operation %s in parent %v", unrefOriginal, co, 2109 parentOriginal) 2110 } 2111 } 2112 2113 } 2114 } 2115 return nil 2116} 2117 2118// getActionsToMerge returns the set of actions needed to merge each 2119// unmerged chain of operations, in a map keyed by the tail pointer of 2120// the corresponding merged path. 2121func (cr *ConflictResolver) getActionsToMerge( 2122 ctx context.Context, unmergedChains, mergedChains *crChains, 2123 mergedPaths map[data.BlockPointer]data.Path) ( 2124 map[data.BlockPointer]crActionList, error) { 2125 actionMap := make(map[data.BlockPointer]crActionList) 2126 for unmergedMostRecent, unmergedChain := range unmergedChains.byMostRecent { 2127 original := unmergedChain.original 2128 // If this is a file that has been deleted in the merged 2129 // branch, a corresponding recreate op will take care of it, 2130 // no need to do anything here. 2131 2132 // We don't need the "ok" value from this lookup because it's 2133 // fine to pass a nil mergedChain into crChain.getActionsToMerge. 2134 mergedChain := mergedChains.byOriginal[original] 2135 mergedPath, ok := mergedPaths[unmergedMostRecent] 2136 if !ok { 2137 // This most likely means that the file was created or 2138 // deleted in the unmerged branch and thus has no 2139 // corresponding merged path yet. 2140 continue 2141 } 2142 if !mergedPath.IsValid() { 2143 cr.log.CWarningf(ctx, "Ignoring invalid merged path for %v "+ 2144 "(original=%v)", unmergedMostRecent, original) 2145 continue 2146 } 2147 2148 actions, err := unmergedChain.getActionsToMerge( 2149 ctx, cr.config.ConflictRenamer(), mergedPath, 2150 mergedChain) 2151 if err != nil { 2152 return nil, err 2153 } 2154 2155 if len(actions) > 0 { 2156 actionMap[mergedPath.TailPointer()] = actions 2157 } 2158 } 2159 2160 return actionMap, nil 2161} 2162 2163// collapseActions combines file updates with their parent directory 2164// updates, because conflict resolution only happens within a 2165// directory (i.e., files are merged directly, they are just 2166// renamed/copied). It also collapses each action list to get rid of 2167// redundant actions. It returns a slice of additional unmerged paths 2168// that should be included in the overall list of unmergedPaths. 2169func collapseActions(unmergedChains *crChains, unmergedPaths []data.Path, 2170 mergedPaths map[data.BlockPointer]data.Path, 2171 actionMap map[data.BlockPointer]crActionList) (newUnmergedPaths []data.Path) { 2172 for unmergedMostRecent, chain := range unmergedChains.byMostRecent { 2173 // Find the parent directory path and combine 2174 p, ok := mergedPaths[unmergedMostRecent] 2175 if !ok { 2176 continue 2177 } 2178 2179 fileActions := actionMap[p.TailPointer()] 2180 2181 // If this is a directory with setAttr(mtime)-related actions, 2182 // just those action should be collapsed into the parent. 2183 if !chain.isFile() { 2184 var parentActions crActionList 2185 var otherDirActions crActionList 2186 for _, action := range fileActions { 2187 moved := false 2188 switch realAction := action.(type) { 2189 case *copyUnmergedAttrAction: 2190 if realAction.attr[0] == mtimeAttr && !realAction.moved { 2191 realAction.moved = true 2192 parentActions = append(parentActions, realAction) 2193 moved = true 2194 } 2195 case *renameUnmergedAction: 2196 if realAction.causedByAttr == mtimeAttr && 2197 !realAction.moved { 2198 realAction.moved = true 2199 parentActions = append(parentActions, realAction) 2200 moved = true 2201 } 2202 } 2203 if !moved { 2204 otherDirActions = append(otherDirActions, action) 2205 } 2206 } 2207 if len(parentActions) == 0 { 2208 // A directory with no mtime actions, so treat it 2209 // normally. 2210 continue 2211 } 2212 fileActions = parentActions 2213 if len(otherDirActions) > 0 { 2214 actionMap[p.TailPointer()] = otherDirActions 2215 } else { 2216 delete(actionMap, p.TailPointer()) 2217 } 2218 } else { 2219 // Mark the copyUnmergedAttrActions as moved, so they 2220 // don't get moved again by the parent. 2221 for _, action := range fileActions { 2222 if realAction, ok := action.(*copyUnmergedAttrAction); ok { 2223 realAction.moved = true 2224 } 2225 } 2226 } 2227 2228 parentPath := *p.ParentPath() 2229 mergedParent := parentPath.TailPointer() 2230 parentActions, wasParentActions := actionMap[mergedParent] 2231 combinedActions := append(parentActions, fileActions...) 2232 actionMap[mergedParent] = combinedActions 2233 if chain.isFile() { 2234 mergedPaths[unmergedMostRecent] = parentPath 2235 delete(actionMap, p.TailPointer()) 2236 } 2237 if !wasParentActions { 2238 // The parent isn't yet represented in our data 2239 // structures, so we have to make sure its actions get 2240 // executed. 2241 // 2242 // Find the unmerged path to get the unmerged parent. 2243 for _, unmergedPath := range unmergedPaths { 2244 if unmergedPath.TailPointer() != unmergedMostRecent { 2245 continue 2246 } 2247 unmergedParentPath := *unmergedPath.ParentPath() 2248 unmergedParent := unmergedParentPath.TailPointer() 2249 unmergedParentChain := 2250 unmergedChains.byMostRecent[unmergedParent] 2251 // If this is a file, only add a new unmerged path if 2252 // the parent has ops; otherwise it will confuse the 2253 // resolution code and lead to stray blocks. 2254 if !chain.isFile() || len(unmergedParentChain.ops) > 0 { 2255 newUnmergedPaths = 2256 append(newUnmergedPaths, unmergedParentPath) 2257 } 2258 // File merged paths were already updated above. 2259 if !chain.isFile() { 2260 mergedPaths[unmergedParent] = parentPath 2261 } 2262 break 2263 } 2264 } 2265 } 2266 2267 for ptr, actions := range actionMap { 2268 actionMap[ptr] = actions.collapse() 2269 } 2270 return newUnmergedPaths 2271} 2272 2273func (cr *ConflictResolver) computeActions(ctx context.Context, 2274 unmergedChains, mergedChains *crChains, unmergedPaths []data.Path, 2275 mergedPaths map[data.BlockPointer]data.Path, recreateOps []*createOp, 2276 mostRecentMergedWriterInfo writerInfo) ( 2277 map[data.BlockPointer]crActionList, []data.Path, error) { 2278 // Process all the recreateOps, adding them to the appropriate 2279 // unmerged chains. 2280 newUnmergedPaths, err := cr.addRecreateOpsToUnmergedChains( 2281 ctx, recreateOps, unmergedChains, mergedChains, mergedPaths) 2282 if err != nil { 2283 return nil, nil, err 2284 } 2285 2286 // Fix any rename cycles by turning the corresponding unmerged 2287 // createOp into a symlink entry type. 2288 moreNewUnmergedPaths, err := cr.fixRenameConflicts(ctx, unmergedChains, 2289 mergedChains, mergedPaths) 2290 if err != nil { 2291 return nil, nil, err 2292 } 2293 newUnmergedPaths = append(newUnmergedPaths, moreNewUnmergedPaths...) 2294 2295 // Recreate any modified merged nodes that were rm'd in the 2296 // unmerged branch. 2297 if err := cr.addMergedRecreates( 2298 ctx, unmergedChains, mergedChains, 2299 mostRecentMergedWriterInfo); err != nil { 2300 return nil, nil, err 2301 } 2302 2303 actionMap, err := cr.getActionsToMerge( 2304 ctx, unmergedChains, mergedChains, mergedPaths) 2305 if err != nil { 2306 return nil, nil, err 2307 } 2308 2309 // Finally, merged the file actions back into their parent 2310 // directory action list, and collapse everything together. 2311 moreNewUnmergedPaths = 2312 collapseActions(unmergedChains, unmergedPaths, mergedPaths, actionMap) 2313 return actionMap, append(newUnmergedPaths, moreNewUnmergedPaths...), nil 2314} 2315 2316func (cr *ConflictResolver) makeFileBlockDeepCopy(ctx context.Context, 2317 lState *kbfssync.LockState, chains *crChains, 2318 mergedMostRecent data.BlockPointer, parentPath data.Path, 2319 name data.PathPartString, ptr data.BlockPointer, blocks fileBlockMap, 2320 dirtyBcache data.DirtyBlockCacheSimple) (data.BlockPointer, error) { 2321 kmd := chains.mostRecentChainMDInfo 2322 2323 // Use a `nil` childObfuscator here, since this is for a file and 2324 // files can't have children to obfuscate, by defintion. 2325 file := parentPath.ChildPath(name, ptr, nil) 2326 oldInfos, err := cr.fbo.blocks.getIndirectFileBlockInfosLocked( 2327 ctx, lState, kmd, file) 2328 if err != nil { 2329 return data.BlockPointer{}, err 2330 } 2331 2332 newPtr, allChildPtrs, err := cr.fbo.blocks.deepCopyFileLocked( 2333 ctx, lState, kmd, file, dirtyBcache, cr.config.DataVersion()) 2334 if err != nil { 2335 return data.BlockPointer{}, err 2336 } 2337 2338 block, err := dirtyBcache.Get(ctx, cr.fbo.id(), newPtr, cr.fbo.branch()) 2339 if err != nil { 2340 return data.BlockPointer{}, err 2341 } 2342 fblock, isFileBlock := block.(*data.FileBlock) 2343 if !isFileBlock { 2344 return data.BlockPointer{}, NotFileBlockError{ptr, cr.fbo.branch(), file} 2345 } 2346 2347 // Mark this as having been created during this chain, so that 2348 // later during block accounting we can infer the origin of the 2349 // block. 2350 chains.createdOriginals[newPtr] = true 2351 // If this file was created within the branch, we should clean up 2352 // all the old block pointers. 2353 original, err := chains.originalFromMostRecentOrSame(ptr) 2354 if err != nil { 2355 return data.BlockPointer{}, err 2356 } 2357 newlyCreated := chains.isCreated(original) 2358 if newlyCreated { 2359 chains.toUnrefPointers[original] = true 2360 for _, oldInfo := range oldInfos { 2361 chains.toUnrefPointers[oldInfo.BlockPointer] = true 2362 } 2363 } 2364 2365 cr.log.CDebugf(ctx, "putTopBlock: %s", name) 2366 err = blocks.putTopBlock(ctx, mergedMostRecent, name, fblock) 2367 if err != nil { 2368 return data.BlockPointer{}, err 2369 } 2370 2371 for _, childPtr := range allChildPtrs { 2372 chains.createdOriginals[childPtr] = true 2373 } 2374 2375 return newPtr, nil 2376} 2377 2378func (cr *ConflictResolver) doOneAction( 2379 ctx context.Context, lState *kbfssync.LockState, 2380 unmergedChains, mergedChains *crChains, unmergedPath data.Path, 2381 mergedPaths map[data.BlockPointer]data.Path, chargedTo keybase1.UserOrTeamID, 2382 actionMap map[data.BlockPointer]crActionList, dbm dirBlockMap, 2383 doneActions map[data.BlockPointer]bool, newFileBlocks fileBlockMap, 2384 dirtyBcache data.DirtyBlockCacheSimple) error { 2385 unmergedMostRecent := unmergedPath.TailPointer() 2386 unmergedChain, ok := 2387 unmergedChains.byMostRecent[unmergedMostRecent] 2388 if !ok { 2389 return fmt.Errorf("Couldn't find unmerged chain for %v", 2390 unmergedMostRecent) 2391 } 2392 2393 // If this is a file that has been deleted in the merged 2394 // branch, a corresponding recreate op will take care of it, 2395 // no need to do anything here. 2396 2397 // find the corresponding merged path 2398 mergedPath, ok := mergedPaths[unmergedMostRecent] 2399 if !ok { 2400 // This most likely means that the file was created or 2401 // deleted in the unmerged branch and thus has no 2402 // corresponding merged path yet. 2403 return nil 2404 } 2405 if unmergedChain.isFile() { 2406 // The unmerged path is actually the parent (the merged 2407 // path was already corrected above). 2408 unmergedPath = *unmergedPath.ParentPath() 2409 } 2410 2411 // Now get the directory blocks. For unmerged directories, we 2412 // can use a nil local block cache, because unmerged blocks 2413 // should never be changed during the CR process (since 2414 // they're just going away). This call will lock `blockLock`, 2415 // and the subsequent `newDirData` calls can assume it's 2416 // locked already. 2417 var unmergedDir *data.DirData 2418 unmergedDir, cleanupFn := cr.fbo.blocks.newDirDataWithDBM( 2419 lState, unmergedPath, chargedTo, 2420 unmergedChains.mostRecentChainMDInfo, newDirBlockMapMemory()) 2421 defer cleanupFn() 2422 2423 if unmergedPath.TailPointer() == mergedPath.TailPointer() { 2424 // recreateOps update the merged paths using original 2425 // pointers; but if other stuff happened in the merged 2426 // block before it was deleted (such as other removes) we 2427 // want to preserve those. Therefore, we don't want the 2428 // unmerged block to remain in the local block cache. 2429 // Below we'll replace it with a new one instead. 2430 err := dbm.deleteBlock(ctx, unmergedPath.TailPointer()) 2431 if err != nil { 2432 return err 2433 } 2434 cr.log.CDebugf(ctx, "Removing block for %v from the local cache", 2435 unmergedPath.TailPointer()) 2436 } 2437 2438 blockExists, err := dbm.hasBlock(ctx, mergedPath.TailPointer()) 2439 if err != nil { 2440 return err 2441 } 2442 // If this is a recreate op and we haven't yet made a new 2443 // block for it, then make a new one and put it in the local 2444 // block cache. 2445 if mergedChains.isDeleted(mergedPath.TailPointer()) && !blockExists { 2446 err := dbm.putBlock( 2447 ctx, mergedPath.TailPointer(), data.NewDirBlock().(*data.DirBlock)) 2448 if err != nil { 2449 return err 2450 } 2451 } 2452 mergedDir := cr.fbo.blocks.newDirDataWithDBMLocked( 2453 lState, mergedPath, chargedTo, 2454 mergedChains.mostRecentChainMDInfo, dbm) 2455 // Force the top block into the `dbm`. `folderUpdatePrepper` 2456 // requires this, even if the block isn't modified, to 2457 // distinguish it from a file block. 2458 _, err = mergedDir.GetTopBlock(ctx, data.BlockWrite) 2459 if err != nil { 2460 return err 2461 } 2462 2463 actions := actionMap[mergedPath.TailPointer()] 2464 if len(actions) > 0 && !doneActions[mergedPath.TailPointer()] { 2465 // Make sure we don't try to execute the same actions twice. 2466 doneActions[mergedPath.TailPointer()] = true 2467 2468 // Any file block copies, keyed by their new temporary block 2469 // IDs, and later we will ready them. 2470 unmergedFetcher := func( 2471 ctx context.Context, name data.PathPartString, 2472 ptr data.BlockPointer) (data.BlockPointer, error) { 2473 return cr.makeFileBlockDeepCopy(ctx, lState, unmergedChains, 2474 mergedPath.TailPointer(), unmergedPath, name, ptr, 2475 newFileBlocks, dirtyBcache) 2476 } 2477 mergedFetcher := func( 2478 ctx context.Context, name data.PathPartString, 2479 ptr data.BlockPointer) (data.BlockPointer, error) { 2480 return cr.makeFileBlockDeepCopy(ctx, lState, mergedChains, 2481 mergedPath.TailPointer(), mergedPath, name, 2482 ptr, newFileBlocks, dirtyBcache) 2483 } 2484 2485 // Execute each action and save the modified ops back into 2486 // each chain. 2487 for _, action := range actions { 2488 // Make sure we don't get stuck inside a large action list 2489 // for a long time, if the actions are slow to complete. 2490 err := cr.checkDone(ctx) 2491 if err != nil { 2492 return err 2493 } 2494 2495 swap, newPtr, err := action.swapUnmergedBlock( 2496 ctx, unmergedChains, mergedChains, unmergedDir) 2497 if err != nil { 2498 return err 2499 } 2500 uDir := unmergedDir 2501 if swap { 2502 cr.log.CDebugf(ctx, "Swapping out dir %v for %v", 2503 newPtr, unmergedPath.TailPointer()) 2504 if newPtr == data.ZeroPtr { 2505 // Use the merged `dirData`. 2506 uDir = mergedDir 2507 } else { 2508 // Use the specified `dirData`, and supply a 2509 // `nil` local block cache to ensure that a) 2510 // only clean blocks are used, as blocks in 2511 // the `dbm` might have already been touched 2512 // by previous actions, and b) no new blocks 2513 // are cached. 2514 newPath := data.Path{ 2515 FolderBranch: mergedPath.FolderBranch, 2516 Path: []data.PathNode{{ 2517 BlockPointer: newPtr, Name: mergedPath.TailName()}}, 2518 ChildObfuscator: cr.fbo.makeObfuscator(), 2519 } 2520 uDir = cr.fbo.blocks.newDirDataWithDBMLocked( 2521 lState, newPath, chargedTo, 2522 mergedChains.mostRecentChainMDInfo, 2523 newDirBlockMapMemory()) 2524 } 2525 } 2526 2527 unrefs, err := action.do( 2528 ctx, unmergedFetcher, mergedFetcher, uDir, mergedDir) 2529 if err != nil { 2530 return err 2531 } 2532 for _, info := range unrefs { 2533 unmergedChains.toUnrefPointers[info.BlockPointer] = true 2534 } 2535 } 2536 } 2537 2538 // Now update the ops related to this exact path (not the ops 2539 // for its parent!). 2540 for _, action := range actions { 2541 // Make sure we don't get stuck inside a large action list 2542 // for a long time, if the actions are slow to complete. 2543 err := cr.checkDone(ctx) 2544 if err != nil { 2545 return err 2546 } 2547 2548 // unmergedMostRecent is for the correct pointer, but 2549 // mergedPath may be for the parent in the case of files 2550 // so we need to find the real mergedMostRecent pointer. 2551 mergedMostRecent := unmergedChain.original 2552 mergedChain, ok := mergedChains.byOriginal[unmergedChain.original] 2553 if ok { 2554 mergedMostRecent = mergedChain.mostRecent 2555 } 2556 2557 err = action.updateOps( 2558 ctx, unmergedMostRecent, mergedMostRecent, 2559 unmergedDir, mergedDir, unmergedChains, mergedChains) 2560 if err != nil { 2561 return err 2562 } 2563 } 2564 return nil 2565} 2566 2567func (cr *ConflictResolver) doActions(ctx context.Context, 2568 lState *kbfssync.LockState, unmergedChains, mergedChains *crChains, 2569 unmergedPaths []data.Path, mergedPaths map[data.BlockPointer]data.Path, 2570 actionMap map[data.BlockPointer]crActionList, dbm dirBlockMap, 2571 newFileBlocks fileBlockMap, dirtyBcache data.DirtyBlockCacheSimple) error { 2572 mergedMD := mergedChains.mostRecentChainMDInfo 2573 chargedTo, err := chargedToForTLF( 2574 ctx, cr.config.KBPKI(), cr.config.KBPKI(), cr.config, 2575 mergedMD.GetTlfHandle()) 2576 if err != nil { 2577 return err 2578 } 2579 2580 // For each set of actions: 2581 // * Find the corresponding chains 2582 // * Make a reference to each slice of ops 2583 // * Get the unmerged block. 2584 // * Get the merged block if it's not already in the local cache, and 2585 // make a copy. 2586 // * Get the merged block 2587 // * Do each action, updating the ops references to the returned ones 2588 // At the end, the local block cache should contain all the 2589 // updated merged blocks. A future phase will update the pointers 2590 // in standard Merkle-tree-fashion. 2591 doneActions := make(map[data.BlockPointer]bool) 2592 for _, unmergedPath := range unmergedPaths { 2593 // Make sure we don't get stuck inside a large unmerged list for 2594 // a long time, if the actions are slow to complete. 2595 err := cr.checkDone(ctx) 2596 if err != nil { 2597 return err 2598 } 2599 2600 err = cr.doOneAction( 2601 ctx, lState, unmergedChains, mergedChains, unmergedPath, 2602 mergedPaths, chargedTo, actionMap, dbm, doneActions, newFileBlocks, 2603 dirtyBcache) 2604 if err != nil { 2605 return err 2606 } 2607 } 2608 return nil 2609} 2610 2611type crRenameHelperKey struct { 2612 parentOriginal data.BlockPointer 2613 name string 2614} 2615 2616// makeRevertedOps changes the BlockPointers of the corresponding 2617// operations for the given set of paths back to their originals, 2618// which allows other parts of conflict resolution to more easily 2619// build up the local and remote notifications needed. Also, it 2620// reverts rm/create pairs back into complete rename operations, for 2621// the purposes of notification, so this should only be called after 2622// all conflicts and actions have been resolved. It returns the 2623// complete slice of reverted operations. 2624func (cr *ConflictResolver) makeRevertedOps(ctx context.Context, 2625 lState *kbfssync.LockState, sortedPaths []data.Path, chains *crChains, 2626 otherChains *crChains) ([]op, error) { 2627 var ops []op 2628 // Build a map of directory {original, name} -> renamed original. 2629 // This will help us map create ops to the corresponding old 2630 // parent. 2631 renames := make(map[crRenameHelperKey]data.BlockPointer) 2632 for original, ri := range chains.renamedOriginals { 2633 renames[crRenameHelperKey{ri.originalNewParent, ri.newName}] = original 2634 } 2635 2636 // Insert the operations starting closest to the root, so 2637 // necessary directories are created first. 2638 for i := len(sortedPaths) - 1; i >= 0; i-- { 2639 ptr := sortedPaths[i].TailPointer() 2640 chain, ok := chains.byMostRecent[ptr] 2641 if !ok { 2642 return nil, fmt.Errorf("makeRevertedOps: Couldn't find chain "+ 2643 "for %v", ptr) 2644 } 2645 2646 chainLoop: 2647 for _, op := range chain.ops { 2648 // Skip any rms that were part of a rename 2649 if rop, ok := op.(*rmOp); ok && len(rop.Unrefs()) == 0 { 2650 continue 2651 } 2652 2653 // Turn the create half of a rename back into a full rename. 2654 if cop, ok := op.(*createOp); ok && cop.renamed { 2655 renameOriginal, ok := renames[crRenameHelperKey{ 2656 chain.original, cop.NewName}] 2657 if !ok { 2658 if cop.crSymPath != "" || cop.Type == data.Sym { 2659 // For symlinks created by the CR process, we 2660 // expect the rmOp to have been removed. For 2661 // existing symlinks that were simply moved, 2662 // there is no benefit in combining their 2663 // create and rm ops back together since there 2664 // is no corresponding node. 2665 continue 2666 } 2667 return nil, fmt.Errorf("Couldn't find corresponding "+ 2668 "renamed original for %v, %s", 2669 chain.original, cop.NewName) 2670 } 2671 2672 if otherChains.isDeleted(renameOriginal) || 2673 chains.isCreated(renameOriginal) { 2674 // If we are re-instating a deleted node, or 2675 // dealing with a node that was created entirely 2676 // in this branch, just use the create op. 2677 op = chains.copyOpAndRevertUnrefsToOriginals(cop) 2678 if cop.Type != data.Dir { 2679 renameMostRecent, err := 2680 chains.mostRecentFromOriginalOrSame(renameOriginal) 2681 if err != nil { 2682 return nil, err 2683 } 2684 2685 err = cr.addChildBlocksIfIndirectFile(ctx, lState, 2686 chains, cop.getFinalPath().ChildPath( 2687 cop.obfuscatedNewName(), renameMostRecent, 2688 cr.fbo.makeObfuscator()), op) 2689 if err != nil { 2690 return nil, err 2691 } 2692 } 2693 } else { 2694 ri, ok := chains.renamedOriginals[renameOriginal] 2695 if !ok { 2696 return nil, fmt.Errorf("Couldn't find the rename info "+ 2697 "for original %v", renameOriginal) 2698 } 2699 2700 rop, err := newRenameOp(ri.oldName, ri.originalOldParent, 2701 ri.newName, ri.originalNewParent, renameOriginal, 2702 cop.Type) 2703 if err != nil { 2704 return nil, err 2705 } 2706 chain.ensurePath(rop, chain.mostRecent) 2707 // Set the Dir.Ref fields to be the same as the Unref 2708 // -- they will be fixed up later. 2709 rop.AddSelfUpdate(ri.originalOldParent) 2710 if ri.originalNewParent != ri.originalOldParent { 2711 rop.AddSelfUpdate(ri.originalNewParent) 2712 } 2713 for _, ptr := range cop.Unrefs() { 2714 origPtr, err := chains.originalFromMostRecentOrSame(ptr) 2715 if err != nil { 2716 return nil, err 2717 } 2718 rop.AddUnrefBlock(origPtr) 2719 } 2720 op = rop 2721 2722 // If this renames from a source that's been 2723 // deleted by a previous op, we should replace the 2724 // delete with this. 2725 for i, prevOp := range ops { 2726 rmop, ok := prevOp.(*rmOp) 2727 if !ok { 2728 continue 2729 } 2730 2731 if rop.OldDir.Unref == rmop.Dir.Unref && 2732 rop.OldName == rmop.OldName { 2733 ops[i] = op 2734 continue chainLoop 2735 } 2736 } 2737 2738 } 2739 } else { 2740 op = chains.copyOpAndRevertUnrefsToOriginals(op) 2741 // The dir of renamed setAttrOps must be reverted to 2742 // the new parent's original pointer. 2743 if sao, ok := op.(*setAttrOp); ok { 2744 if newDir, _, ok := 2745 otherChains.renamedParentAndName(sao.File); ok { 2746 err := sao.Dir.setUnref(newDir) 2747 if err != nil { 2748 return nil, err 2749 } 2750 } 2751 } 2752 } 2753 2754 ops = append(ops, op) 2755 } 2756 } 2757 2758 return ops, nil 2759} 2760 2761// createResolvedMD creates a MD update that will be merged into the 2762// main folder as the resolving commit. It contains all of the 2763// unmerged operations, as well as a "dummy" operation at the end 2764// which will catch all of the BlockPointer updates. A later phase 2765// will move all of those updates into their proper locations within 2766// the other operations. 2767func (cr *ConflictResolver) createResolvedMD(ctx context.Context, 2768 lState *kbfssync.LockState, unmergedPaths []data.Path, 2769 unmergedChains, mergedChains *crChains, 2770 mostRecentMergedMD ImmutableRootMetadata) (*RootMetadata, error) { 2771 err := cr.checkDone(ctx) 2772 if err != nil { 2773 return nil, err 2774 } 2775 2776 newMD, err := mostRecentMergedMD.MakeSuccessor( 2777 ctx, cr.config.MetadataVersion(), cr.config.Codec(), 2778 cr.config.KeyManager(), cr.config.KBPKI(), 2779 cr.config.KBPKI(), cr.config, mostRecentMergedMD.MdID(), true) 2780 if err != nil { 2781 return nil, err 2782 } 2783 2784 var newPaths []data.Path 2785 for original, chain := range unmergedChains.byOriginal { 2786 added := false 2787 for i, op := range chain.ops { 2788 if cop, ok := op.(*createOp); ok { 2789 // We need to add in any creates that happened 2790 // within newly-created directories (which aren't 2791 // being merged with other newly-created directories), 2792 // to ensure that the overall Refs are correct and 2793 // that future CR processes can check those create ops 2794 // for conflicts. 2795 if unmergedChains.isCreated(original) && 2796 !mergedChains.isCreated(original) { 2797 // Shallowly copy the create op and update its 2798 // directory to the most recent pointer -- this won't 2799 // work with the usual revert ops process because that 2800 // skips chains which are newly-created within this 2801 // branch. 2802 newCreateOp := *cop 2803 newCreateOp.Dir, err = makeBlockUpdate( 2804 chain.mostRecent, chain.mostRecent) 2805 if err != nil { 2806 return nil, err 2807 } 2808 chain.ops[i] = &newCreateOp 2809 if !added { 2810 newPaths = append(newPaths, data.Path{ 2811 FolderBranch: cr.fbo.folderBranch, 2812 Path: []data.PathNode{{ 2813 BlockPointer: chain.mostRecent}}, 2814 ChildObfuscator: cr.fbo.makeObfuscator(), 2815 }) 2816 added = true 2817 } 2818 } 2819 if cop.Type == data.Dir || len(cop.Refs()) == 0 { 2820 continue 2821 } 2822 // Add any direct file blocks too into each create op, 2823 // which originated in later unmerged syncs. 2824 ptr, err := 2825 unmergedChains.mostRecentFromOriginalOrSame(cop.Refs()[0]) 2826 if err != nil { 2827 return nil, err 2828 } 2829 trackSyncPtrChangesInCreate( 2830 ptr, chain, unmergedChains, cop.NewName) 2831 } 2832 } 2833 } 2834 if len(newPaths) > 0 { 2835 // Put the new paths at the beginning so they are processed 2836 // last in sorted order. 2837 unmergedPaths = append(newPaths, unmergedPaths...) 2838 } 2839 2840 ops, err := cr.makeRevertedOps( 2841 ctx, lState, unmergedPaths, unmergedChains, mergedChains) 2842 if err != nil { 2843 return nil, err 2844 } 2845 2846 cr.log.CDebugf(ctx, "Remote notifications: %v", ops) 2847 for _, op := range ops { 2848 cr.log.CDebugf(ctx, "%s: refs %v", op, op.Refs()) 2849 newMD.AddOp(op) 2850 } 2851 2852 // Add a final dummy operation to collect all of the block updates. 2853 newMD.AddOp(newResolutionOp()) 2854 2855 return newMD, nil 2856} 2857 2858// resolveOnePath figures out the new merged path, in the resolved 2859// folder, for a given unmerged pointer. For each node on the path, 2860// see if the node has been renamed. If so, see if there's a 2861// resolution for it yet. If there is, complete the path using that 2862// resolution. If not, recurse. 2863func (cr *ConflictResolver) resolveOnePath(ctx context.Context, 2864 unmergedMostRecent data.BlockPointer, 2865 unmergedChains, mergedChains, resolvedChains *crChains, 2866 mergedPaths, resolvedPaths map[data.BlockPointer]data.Path) (data.Path, error) { 2867 if p, ok := resolvedPaths[unmergedMostRecent]; ok { 2868 return p, nil 2869 } 2870 2871 // There should always be a merged path, because we should only be 2872 // calling this with pointers that were updated in the unmerged 2873 // branch. 2874 resolvedPath, ok := mergedPaths[unmergedMostRecent] 2875 if !ok { 2876 var ptrsToAppend []data.BlockPointer 2877 var namesToAppend []data.PathPartString 2878 next := unmergedMostRecent 2879 for len(mergedPaths[next].Path) == 0 { 2880 newPtrs := make(map[data.BlockPointer]bool) 2881 ptrs := []data.BlockPointer{unmergedMostRecent} 2882 for ptr := range unmergedChains.byMostRecent { 2883 newPtrs[ptr] = true 2884 } 2885 2886 mdInfo := unmergedChains.mostRecentChainMDInfo 2887 nodeMap, cache, err := cr.fbo.blocks.SearchForNodes( 2888 ctx, cr.fbo.nodeCache, ptrs, newPtrs, 2889 mdInfo, mdInfo.GetRootDirEntry().BlockPointer) 2890 if err != nil { 2891 return data.Path{}, err 2892 } 2893 n := nodeMap[unmergedMostRecent] 2894 if n == nil { 2895 return data.Path{}, fmt.Errorf("resolveOnePath: Couldn't find "+ 2896 "merged path for %v", unmergedMostRecent) 2897 } 2898 p := cache.PathFromNode(n) 2899 ptrsToAppend = append(ptrsToAppend, next) 2900 namesToAppend = append(namesToAppend, p.TailName()) 2901 next = p.ParentPath().TailPointer() 2902 } 2903 resolvedPath = mergedPaths[next] 2904 for i, ptr := range ptrsToAppend { 2905 resolvedPath = resolvedPath.ChildPath( 2906 namesToAppend[i], ptr, cr.fbo.makeObfuscator()) 2907 } 2908 } 2909 2910 i := len(resolvedPath.Path) - 1 2911 for i >= 0 { 2912 mergedMostRecent := resolvedPath.Path[i].BlockPointer 2913 original, err := 2914 mergedChains.originalFromMostRecentOrSame(mergedMostRecent) 2915 if err != nil { 2916 return data.Path{}, err 2917 } 2918 2919 origNewParent, newName, renamed := 2920 resolvedChains.renamedParentAndName(original) 2921 if !renamed { 2922 i-- 2923 continue 2924 } 2925 unmergedNewParent, err := 2926 unmergedChains.mostRecentFromOriginalOrSame(origNewParent) 2927 if err != nil { 2928 return data.Path{}, err 2929 } 2930 2931 // Is the new parent resolved yet? 2932 parentPath, err := cr.resolveOnePath(ctx, unmergedNewParent, 2933 unmergedChains, mergedChains, resolvedChains, mergedPaths, 2934 resolvedPaths) 2935 if err != nil { 2936 return data.Path{}, err 2937 } 2938 2939 // Reset the resolved path 2940 newPathLen := len(parentPath.Path) + len(resolvedPath.Path) - i 2941 newResolvedPath := data.Path{ 2942 FolderBranch: resolvedPath.FolderBranch, 2943 Path: make([]data.PathNode, newPathLen), 2944 ChildObfuscator: cr.fbo.makeObfuscator(), 2945 } 2946 copy(newResolvedPath.Path[:len(parentPath.Path)], parentPath.Path) 2947 copy(newResolvedPath.Path[len(parentPath.Path):], resolvedPath.Path[i:]) 2948 i = len(parentPath.Path) - 1 2949 newNamePPS := data.NewPathPartString( 2950 newName, newResolvedPath.Obfuscator()) 2951 newResolvedPath.Path[i+1].Name = newNamePPS 2952 resolvedPath = newResolvedPath 2953 } 2954 2955 resolvedPaths[unmergedMostRecent] = resolvedPath 2956 return resolvedPath, nil 2957} 2958 2959type rootMetadataWithKeyAndTimestamp struct { 2960 *RootMetadata 2961 key kbfscrypto.VerifyingKey 2962 localTimestamp time.Time 2963} 2964 2965func (rmd rootMetadataWithKeyAndTimestamp) LastModifyingWriterVerifyingKey() kbfscrypto.VerifyingKey { 2966 return rmd.key 2967} 2968 2969func (rmd rootMetadataWithKeyAndTimestamp) LocalTimestamp() time.Time { 2970 return rmd.localTimestamp 2971} 2972 2973// makePostResolutionPaths returns the full paths to each unmerged 2974// pointer, taking into account any rename operations that occurred in 2975// the merged branch. 2976func (cr *ConflictResolver) makePostResolutionPaths(ctx context.Context, 2977 md *RootMetadata, unmergedChains, mergedChains *crChains, 2978 mergedPaths map[data.BlockPointer]data.Path) (map[data.BlockPointer]data.Path, error) { 2979 err := cr.checkDone(ctx) 2980 if err != nil { 2981 return nil, err 2982 } 2983 2984 session, err := cr.config.KBPKI().GetCurrentSession(ctx) 2985 if err != nil { 2986 return nil, err 2987 } 2988 2989 // No need to run any identifies on these chains, since we 2990 // have already finished all actions. 2991 resolvedChains, err := newCRChains( 2992 ctx, cr.config.Codec(), cr.config, 2993 []chainMetadata{rootMetadataWithKeyAndTimestamp{md, 2994 session.VerifyingKey, cr.config.Clock().Now()}}, 2995 &cr.fbo.blocks, false) 2996 if err != nil { 2997 return nil, err 2998 } 2999 3000 // If there are no renames, we don't need to fix any of the paths 3001 if len(resolvedChains.renamedOriginals) == 0 { 3002 return mergedPaths, nil 3003 } 3004 3005 resolvedPaths := make(map[data.BlockPointer]data.Path) 3006 for ptr, oldP := range mergedPaths { 3007 p, err := cr.resolveOnePath(ctx, ptr, unmergedChains, mergedChains, 3008 resolvedChains, mergedPaths, resolvedPaths) 3009 if err != nil { 3010 return nil, err 3011 } 3012 cr.log.CDebugf(ctx, "Resolved path for %v from %v to %v", 3013 ptr, oldP.Path, p.Path) 3014 } 3015 3016 return resolvedPaths, nil 3017} 3018 3019// getOpsForLocalNotification returns the set of operations that this 3020// node will need to send local notifications for, in order to 3021// transition from the staged state to the merged state. 3022func (cr *ConflictResolver) getOpsForLocalNotification(ctx context.Context, 3023 lState *kbfssync.LockState, md *RootMetadata, 3024 unmergedChains, mergedChains *crChains, 3025 updates map[data.BlockPointer]data.BlockPointer) ( 3026 []op, error) { 3027 dummyOp := newResolutionOp() 3028 newPtrs := make(map[data.BlockPointer]bool) 3029 for mergedMostRecent, newMostRecent := range updates { 3030 // `updates` contains the pointer updates needed for devices 3031 // on the merged branch to update; we have to find the 3032 // original of the entire branch to find the corresponding 3033 // unmerged most recent. 3034 original, err := 3035 mergedChains.originalFromMostRecentOrSame(mergedMostRecent) 3036 if err != nil { 3037 return nil, err 3038 } 3039 chain, ok := unmergedChains.byOriginal[original] 3040 if ok { 3041 // If this unmerged node was updated in the resolution, 3042 // track that update here. 3043 dummyOp.AddUpdate(chain.mostRecent, newMostRecent) 3044 } else { 3045 dummyOp.AddUpdate(original, newMostRecent) 3046 } 3047 newPtrs[newMostRecent] = true 3048 } 3049 3050 var ptrs []data.BlockPointer 3051 chainsToUpdate := make(map[data.BlockPointer]data.BlockPointer) 3052 chainsToAdd := make(map[data.BlockPointer]*crChain) 3053 for ptr, chain := range mergedChains.byMostRecent { 3054 if newMostRecent, ok := updates[chain.original]; ok { 3055 ptrs = append(ptrs, newMostRecent) 3056 chainsToUpdate[chain.mostRecent] = newMostRecent 3057 // This update was already handled above. 3058 continue 3059 } 3060 3061 // If the node changed in both branches, but NOT in the 3062 // resolution, make sure the local notification uses the 3063 // unmerged most recent pointer as the unref. 3064 original := chain.original 3065 if c, ok := unmergedChains.byOriginal[chain.original]; ok { 3066 original = c.mostRecent 3067 updates[chain.original] = chain.mostRecent 3068 3069 // If the node pointer didn't change in the merged chain 3070 // (e.g., due to a setattr), fast forward its most-recent 3071 // pointer to be the unmerged most recent pointer, so that 3072 // local notifications work correctly. 3073 if chain.original == chain.mostRecent { 3074 ptrs = append(ptrs, c.mostRecent) 3075 chainsToAdd[c.mostRecent] = chain 3076 delete(mergedChains.byMostRecent, chain.mostRecent) 3077 chain.mostRecent = c.mostRecent 3078 } 3079 } 3080 3081 newPtrs[ptr] = true 3082 dummyOp.AddUpdate(original, chain.mostRecent) 3083 updates[original] = chain.mostRecent 3084 ptrs = append(ptrs, chain.mostRecent) 3085 } 3086 for ptr, chain := range chainsToAdd { 3087 mergedChains.byMostRecent[ptr] = chain 3088 } 3089 3090 // If any nodes changed only in the unmerged branch, make sure we 3091 // update the pointers in the local ops (e.g., renameOp.Renamed) 3092 // to the latest local most recent. 3093 for original, chain := range unmergedChains.byOriginal { 3094 if _, ok := updates[original]; !ok { 3095 updates[original] = chain.mostRecent 3096 } 3097 } 3098 3099 // Update the merged chains so they all have the new most recent 3100 // pointer. 3101 for mostRecent, newMostRecent := range chainsToUpdate { 3102 chain, ok := mergedChains.byMostRecent[mostRecent] 3103 if !ok { 3104 continue 3105 } 3106 delete(mergedChains.byMostRecent, mostRecent) 3107 chain.mostRecent = newMostRecent 3108 mergedChains.byMostRecent[newMostRecent] = chain 3109 } 3110 3111 // We need to get the complete set of updated merged paths, so 3112 // that we can correctly order the chains from the root outward. 3113 mergedNodeCache := newNodeCacheStandard(cr.fbo.folderBranch) 3114 mergedNodeCache.SetObfuscatorMaker(cr.fbo.makeObfuscator) 3115 nodeMap, _, err := cr.fbo.blocks.SearchForNodes( 3116 ctx, mergedNodeCache, ptrs, newPtrs, 3117 md, md.data.Dir.BlockPointer) 3118 if err != nil { 3119 return nil, err 3120 } 3121 mergedPaths := make([]data.Path, 0, len(nodeMap)) 3122 for _, node := range nodeMap { 3123 if node == nil { 3124 continue 3125 } 3126 mergedPaths = append(mergedPaths, mergedNodeCache.PathFromNode(node)) 3127 } 3128 sort.Sort(crSortedPaths(mergedPaths)) 3129 3130 ops, err := cr.makeRevertedOps( 3131 ctx, lState, mergedPaths, mergedChains, unmergedChains) 3132 if err != nil { 3133 return nil, err 3134 } 3135 newOps, err := fixOpPointersForUpdate(ops, updates, mergedChains) 3136 if err != nil { 3137 return nil, err 3138 } 3139 newOps[0] = dummyOp 3140 return newOps, err 3141} 3142 3143// finalizeResolution finishes the resolution process, making the 3144// resolution visible to any nodes on the merged branch, and taking 3145// the local node out of staged mode. 3146func (cr *ConflictResolver) finalizeResolution(ctx context.Context, 3147 lState *kbfssync.LockState, md *RootMetadata, 3148 unmergedChains, mergedChains *crChains, 3149 updates map[data.BlockPointer]data.BlockPointer, 3150 bps blockPutState, blocksToDelete []kbfsblock.ID, writerLocked bool) error { 3151 err := cr.checkDone(ctx) 3152 if err != nil { 3153 return err 3154 } 3155 3156 // Fix up all the block pointers in the merged ops to work well 3157 // for local notifications. Make a dummy op at the beginning to 3158 // convert all the merged most recent pointers into unmerged most 3159 // recent pointers. 3160 newOps, err := cr.getOpsForLocalNotification( 3161 ctx, lState, md, unmergedChains, 3162 mergedChains, updates) 3163 if err != nil { 3164 return err 3165 } 3166 3167 cr.log.CDebugf(ctx, "Local notifications: %v", newOps) 3168 3169 if writerLocked { 3170 return cr.fbo.finalizeResolutionLocked( 3171 ctx, lState, md, bps, newOps, blocksToDelete) 3172 } 3173 return cr.fbo.finalizeResolution( 3174 ctx, lState, md, bps, newOps, blocksToDelete) 3175} 3176 3177// completeResolution pushes all the resolved blocks to the servers, 3178// computes all remote and local notifications, and finalizes the 3179// resolution process. 3180func (cr *ConflictResolver) completeResolution(ctx context.Context, 3181 lState *kbfssync.LockState, unmergedChains, mergedChains *crChains, 3182 unmergedPaths []data.Path, mergedPaths map[data.BlockPointer]data.Path, 3183 mostRecentUnmergedMD, mostRecentMergedMD ImmutableRootMetadata, 3184 dbm dirBlockMap, newFileBlocks fileBlockMap, 3185 dirtyBcache data.DirtyBlockCacheSimple, bps blockPutState, 3186 writerLocked bool) (err error) { 3187 md, err := cr.createResolvedMD( 3188 ctx, lState, unmergedPaths, unmergedChains, 3189 mergedChains, mostRecentMergedMD) 3190 if err != nil { 3191 return err 3192 } 3193 3194 resolvedPaths, err := cr.makePostResolutionPaths(ctx, md, unmergedChains, 3195 mergedChains, mergedPaths) 3196 if err != nil { 3197 return err 3198 } 3199 3200 err = cr.checkDone(ctx) 3201 if err != nil { 3202 return err 3203 } 3204 3205 // Find any paths that don't have any ops associated with them, 3206 // and avoid making new blocks for them in the resolution. 3207 // Without this, we will end up with an extraneous block update 3208 // for the directory with no ops. Then, if this resolution ends 3209 // up going through ANOTHER resolution later, which sees no ops 3210 // need resolving and short-circuits the resolution process, we 3211 // could end up accidentally unreferencing a merged directory 3212 // block that's still in use. See KBFS-2825 for details. 3213 hasChildOps := make(map[data.BlockPointer]bool) 3214 for _, p := range unmergedPaths { 3215 chain := unmergedChains.byMostRecent[p.TailPointer()] 3216 if len(chain.ops) == 0 { 3217 continue 3218 } 3219 for _, pn := range p.Path { 3220 hasChildOps[pn.BlockPointer] = true 3221 } 3222 } 3223 for ptr := range resolvedPaths { 3224 if !hasChildOps[ptr] { 3225 cr.log.CDebugf(ctx, 3226 "Removing resolved path for op-less unmerged block pointer %v", 3227 ptr) 3228 delete(resolvedPaths, ptr) 3229 } 3230 } 3231 3232 updates, blocksToDelete, err := cr.prepper.prepUpdateForPaths( 3233 ctx, lState, md, unmergedChains, mergedChains, 3234 mostRecentUnmergedMD, mostRecentMergedMD, resolvedPaths, dbm, 3235 newFileBlocks, dirtyBcache, bps, prepFolderCopyIndirectFileBlocks) 3236 if err != nil { 3237 return err 3238 } 3239 3240 // Can only do this after prepUpdateForPaths, since 3241 // prepUpdateForPaths calls fixOpPointersForUpdate, and the ops 3242 // may be invalid until then. 3243 err = md.data.checkValid() 3244 if err != nil { 3245 return err 3246 } 3247 3248 defer func() { 3249 if err != nil { 3250 cr.fbo.fbm.cleanUpBlockState( 3251 md.ReadOnly(), bps, blockDeleteOnMDFail) 3252 } 3253 }() 3254 3255 err = cr.checkDone(ctx) 3256 if err != nil { 3257 return err 3258 } 3259 3260 // Put all the blocks. TODO: deal with recoverable block errors? 3261 cacheType := DiskBlockAnyCache 3262 if cr.config.IsSyncedTlf(md.TlfID()) { 3263 cacheType = DiskBlockSyncCache 3264 } 3265 _, err = doBlockPuts( 3266 ctx, cr.config.BlockServer(), cr.config.BlockCache(), 3267 cr.config.Reporter(), cr.log, cr.deferLog, md.TlfID(), 3268 md.GetTlfHandle().GetCanonicalName(), bps, cacheType) 3269 if err != nil { 3270 return err 3271 } 3272 3273 err = cr.finalizeResolution(ctx, lState, md, unmergedChains, 3274 mergedChains, updates, bps, blocksToDelete, writerLocked) 3275 if err != nil { 3276 return err 3277 } 3278 return nil 3279} 3280 3281const conflictRecordVersion = 1 3282 3283type conflictRecord struct { 3284 Version int `json:"-"` 3285 Time time.Time 3286 Merged string 3287 Unmerged string 3288 ErrorTime time.Time 3289 ErrorString string 3290 PanicString string 3291 codec.UnknownFieldSetHandler `json:"-"` 3292} 3293 3294func getAndDeserializeConflicts(config Config, db *ldbutils.LevelDb, 3295 key []byte) ([]conflictRecord, error) { 3296 if db == nil { 3297 return nil, errors.New("No conflict DB given") 3298 } 3299 conflictsSoFarSerialized, err := db.Get(key, nil) 3300 var conflictsSoFar []conflictRecord 3301 switch errors.Cause(err) { 3302 case leveldb.ErrNotFound: 3303 conflictsSoFar = nil 3304 case nil: 3305 err = config.Codec().Decode(conflictsSoFarSerialized, &conflictsSoFar) 3306 if err != nil { 3307 return nil, err 3308 } 3309 default: 3310 return nil, err 3311 } 3312 return conflictsSoFar, nil 3313} 3314 3315func serializeAndPutConflicts(config Config, db *ldbutils.LevelDb, 3316 key []byte, conflicts []conflictRecord) error { 3317 if db == nil { 3318 return errors.New("No conflict DB given") 3319 } 3320 3321 conflictsSerialized, err := config.Codec().Encode(conflicts) 3322 if err != nil { 3323 return err 3324 } 3325 return db.Put(key, conflictsSerialized, nil) 3326} 3327 3328func isCRStuckFromRecords(conflictsSoFar []conflictRecord) bool { 3329 // If we're exactly at the threshold, make sure the last attempt 3330 // has completed. 3331 if len(conflictsSoFar) == maxConflictResolutionAttempts+1 { 3332 return !conflictsSoFar[len(conflictsSoFar)-1].ErrorTime.IsZero() 3333 } 3334 return len(conflictsSoFar) > maxConflictResolutionAttempts 3335} 3336 3337func (cr *ConflictResolver) isStuckWithDbAndConflicts() ( 3338 db *ldbutils.LevelDb, key []byte, conflictsSoFar []conflictRecord, 3339 isStuck bool, err error) { 3340 db = cr.config.GetConflictResolutionDB() 3341 if db == nil { 3342 return nil, nil, nil, false, errNoCRDB 3343 } 3344 key = cr.fbo.id().Bytes() 3345 conflictsSoFar, err = getAndDeserializeConflicts(cr.config, db, key) 3346 if err != nil { 3347 return nil, nil, nil, false, err 3348 } 3349 3350 return db, key, conflictsSoFar, isCRStuckFromRecords(conflictsSoFar), nil 3351} 3352 3353func (cr *ConflictResolver) isStuck() (bool, error) { 3354 _, _, _, isStuck, err := cr.isStuckWithDbAndConflicts() 3355 return isStuck, err 3356} 3357 3358func (cr *ConflictResolver) recordStartResolve(ci conflictInput) error { 3359 db, key, conflictsSoFar, isStuck, err := cr.isStuckWithDbAndConflicts() 3360 if err != nil { 3361 return err 3362 } 3363 if isStuck { 3364 return ErrTooManyCRAttempts 3365 } 3366 conflictsSoFar = append(conflictsSoFar, conflictRecord{ 3367 Version: conflictRecordVersion, 3368 Time: cr.config.Clock().Now(), 3369 Merged: ci.merged.String(), 3370 Unmerged: ci.unmerged.String(), 3371 }) 3372 return serializeAndPutConflicts(cr.config, db, key, conflictsSoFar) 3373} 3374 3375// recordFinishResolve does one of two things: 3376// - in the event of success, it deletes the DB entry that recorded conflict 3377// resolution attempts for this resolver 3378// - in the event of failure, it logs that CR failed and tries to record the 3379// failure to the DB. 3380func (cr *ConflictResolver) recordFinishResolve( 3381 ctx context.Context, ci conflictInput, 3382 panicVar interface{}, receivedErr error) { 3383 db, key, _, wasStuck, err := cr.isStuckWithDbAndConflicts() 3384 if err != nil { 3385 cr.log.CWarningf(ctx, "could not record CR result: %+v", err) 3386 return 3387 } 3388 3389 // If we neither errored nor panicked, this CR succeeded and we can wipe 3390 // the DB entry. 3391 if (receivedErr == nil || receivedErr == context.Canceled) && 3392 panicVar == nil { 3393 err := db.Delete(key, nil) 3394 if err != nil { 3395 cr.log.CWarningf(ctx, 3396 "Could not record conflict resolution success: %v", err) 3397 } 3398 3399 if wasStuck { 3400 cr.config.SubscriptionManagerPublisher().PublishChange(keybase1.SubscriptionTopic_FAVORITES) 3401 cr.config.Reporter().NotifyFavoritesChanged(ctx) 3402 cr.config.SubscriptionManagerPublisher().PublishChange( 3403 keybase1.SubscriptionTopic_FILES_TAB_BADGE) 3404 } 3405 return 3406 } 3407 3408 defer func() { 3409 // If we can't record the failure to the CR DB, at least log it. 3410 if err != nil { 3411 cr.log.CWarningf(ctx, 3412 "Could not record conflict resolution failure [%v/%v]: %v", 3413 receivedErr, panicVar, err) 3414 } 3415 // If we recovered from a panic, keep panicking. 3416 if panicVar != nil { 3417 panic(panicVar) 3418 } 3419 }() 3420 3421 // Otherwise we need to decode the most recent entry, modify it, and put it 3422 // back in the DB. 3423 var conflictsSoFar []conflictRecord 3424 conflictsSoFar, err = getAndDeserializeConflicts(cr.config, db, key) 3425 if err != nil { 3426 return 3427 } 3428 3429 thisCR := &conflictsSoFar[len(conflictsSoFar)-1] 3430 thisCR.ErrorTime = cr.config.Clock().Now() 3431 if receivedErr != nil { 3432 thisCR.ErrorString = fmt.Sprintf("%+v", receivedErr) 3433 } 3434 if panicVar != nil { 3435 thisCR.PanicString = fmt.Sprintf("panic(%s). stack: %s", panicVar, 3436 debug.Stack()) 3437 } 3438 3439 err = serializeAndPutConflicts(cr.config, db, key, conflictsSoFar) 3440 if err != nil { 3441 cr.log.CWarningf(ctx, 3442 "Could not record conflict resolution success: %+v", err) 3443 return 3444 } 3445 3446 if !wasStuck && isCRStuckFromRecords(conflictsSoFar) { 3447 cr.config.SubscriptionManagerPublisher().PublishChange(keybase1.SubscriptionTopic_FAVORITES) 3448 cr.config.Reporter().NotifyFavoritesChanged(ctx) 3449 cr.config.SubscriptionManagerPublisher().PublishChange( 3450 keybase1.SubscriptionTopic_FILES_TAB_BADGE) 3451 cr.config.GetPerfLog().CDebugf( 3452 ctx, "Conflict resolution failed too many times for %s", 3453 cr.fbo.id()) 3454 } 3455} 3456 3457func (cr *ConflictResolver) makeDiskBlockCache(ctx context.Context) ( 3458 dbc *DiskBlockCacheLocal, cleanupFn func(context.Context), err error) { 3459 if cr.config.IsTestMode() { 3460 // Enable the disk limiter if one doesn't exist yet. 3461 _ = cr.config.(*ConfigLocal).EnableDiskLimiter(os.TempDir()) 3462 3463 dbc, err = newDiskBlockCacheLocalForTest( 3464 cr.config, crDirtyBlockCacheLimitTrackerType) 3465 if err != nil { 3466 return nil, nil, err 3467 } 3468 cleanupFn = func(ctx context.Context) { 3469 <-dbc.Shutdown(ctx) 3470 } 3471 } else { 3472 tempDir, err := ioutil.TempDir( 3473 cr.config.StorageRoot(), ConflictStorageRootPrefix) 3474 if err != nil { 3475 return nil, nil, err 3476 } 3477 dirCleanupFn := func(_ context.Context) { 3478 err := os.RemoveAll(tempDir) 3479 if err != nil { 3480 cr.log.CDebugf(ctx, "Error cleaning up tempdir %s: %+v", 3481 tempDir, err) 3482 } 3483 } 3484 dbc, err = newDiskBlockCacheLocal( 3485 cr.config, crDirtyBlockCacheLimitTrackerType, tempDir, cr.config.Mode()) 3486 if err != nil { 3487 dirCleanupFn(ctx) 3488 return nil, nil, err 3489 } 3490 cleanupFn = func(ctx context.Context) { 3491 dbc.Shutdown(ctx) 3492 dirCleanupFn(ctx) 3493 } 3494 } 3495 3496 err = dbc.WaitUntilStarted() 3497 if err != nil { 3498 if cleanupFn != nil { 3499 cleanupFn(ctx) 3500 } 3501 return nil, nil, err 3502 } 3503 3504 return dbc, cleanupFn, nil 3505} 3506 3507func (cr *ConflictResolver) getFailModeForTesting() failModeForTesting { 3508 cr.failModeLock.RLock() 3509 defer cr.failModeLock.RUnlock() 3510 return cr.failModeForTesting 3511} 3512 3513func (cr *ConflictResolver) setFailModeForTesting(mode failModeForTesting) { 3514 cr.failModeLock.Lock() 3515 defer cr.failModeLock.Unlock() 3516 cr.failModeForTesting = mode 3517} 3518 3519// CRWrapError wraps an error that happens during conflict resolution. 3520type CRWrapError struct { 3521 err error 3522} 3523 3524// Error implements the error interface for CRWrapError. 3525func (e CRWrapError) Error() string { 3526 return "Conflict resolution error: " + e.err.Error() 3527} 3528 3529func (cr *ConflictResolver) doResolve(ctx context.Context, ci conflictInput) { 3530 var err error 3531 ctx = cr.config.MaybeStartTrace(ctx, "CR.doResolve", 3532 fmt.Sprintf("%s %+v", cr.fbo.folderBranch, ci)) 3533 defer func() { cr.config.MaybeFinishTrace(ctx, err) }() 3534 3535 err = cr.recordStartResolve(ci) 3536 switch errors.Cause(err) { 3537 case ErrTooManyCRAttempts: 3538 cr.log.CWarningf(ctx, 3539 "Too many failed CR attempts for folder: %v", cr.fbo.id()) 3540 cr.config.GetPerfLog().CDebugf( 3541 ctx, "Conflict resolution failed too many times for %v", err) 3542 return 3543 case nil: 3544 defer func() { 3545 r := recover() 3546 cr.recordFinishResolve(ctx, ci, r, err) 3547 }() 3548 default: 3549 cr.log.CWarningf(ctx, 3550 "Could not record conflict resolution attempt: %+v", err) 3551 } 3552 3553 cr.log.CDebugf(ctx, "Starting conflict resolution with input %+v", ci) 3554 lState := makeFBOLockState() 3555 defer func() { 3556 cr.deferLog.CDebugf(ctx, "Finished conflict resolution: %+v", err) 3557 if err != nil { 3558 head := cr.fbo.getTrustedHead(ctx, lState, mdNoCommit) 3559 if head == (ImmutableRootMetadata{}) { 3560 panic("doResolve: head is nil (should be impossible)") 3561 } 3562 handle := head.GetTlfHandle() 3563 cr.config.Reporter().ReportErr( 3564 ctx, handle.GetCanonicalName(), handle.Type(), 3565 WriteMode, CRWrapError{err}) 3566 if err == context.Canceled { 3567 cr.inputLock.Lock() 3568 defer cr.inputLock.Unlock() 3569 cr.canceledCount++ 3570 // TODO: decrease threshold for pending local squashes? 3571 if cr.canceledCount > cr.maxRevsThreshold { 3572 cr.lockNextTime = true 3573 } 3574 } 3575 } else { 3576 // We finished successfully, so no need to lock next time. 3577 cr.inputLock.Lock() 3578 defer cr.inputLock.Unlock() 3579 cr.lockNextTime = false 3580 cr.canceledCount = 0 3581 } 3582 }() 3583 3584 // Canceled before we even got started? 3585 err = cr.checkDone(ctx) 3586 if err != nil { 3587 return 3588 } 3589 3590 if cr.getFailModeForTesting() == alwaysFailCR { 3591 err = ErrCRFailForTesting 3592 return 3593 } 3594 3595 var mergedMDs []ImmutableRootMetadata 3596 3597 // Check if we need to deploy the nuclear option and completely 3598 // block unmerged writes while we try to resolve. 3599 doLock := func() bool { 3600 cr.inputLock.Lock() 3601 defer cr.inputLock.Unlock() 3602 return cr.lockNextTime 3603 }() 3604 if doLock { 3605 cr.log.CDebugf(ctx, "Blocking unmerged writes due to large amounts "+ 3606 "of unresolved state") 3607 cr.fbo.blockUnmergedWrites(lState) 3608 defer cr.fbo.unblockUnmergedWrites(lState) 3609 err = cr.checkDone(ctx) 3610 if err != nil { 3611 return 3612 } 3613 3614 // Sync everything from memory to the journal. 3615 err = cr.fbo.syncAllLocked(ctx, lState, NoExcl) 3616 if err != nil { 3617 return 3618 } 3619 3620 // Don't let us hold the lock for too long though 3621 var cancel context.CancelFunc 3622 ctx, cancel = context.WithTimeout(ctx, crMaxWriteLockTime) 3623 defer cancel() 3624 cr.log.CDebugf(ctx, "Unmerged writes blocked") 3625 } else { 3626 // Sync everything from memory to the journal. 3627 err = cr.fbo.syncAllUnlocked(ctx, lState) 3628 if err != nil { 3629 return 3630 } 3631 } 3632 3633 // Step 1: Build the chains for each branch, as well as the paths 3634 // and necessary extra recreate ops. The result of this step is: 3635 // * A set of conflict resolution "chains" for both the unmerged and 3636 // merged branches 3637 // * A map containing, for each changed unmerged node, the full path to 3638 // the corresponding merged node. 3639 // * A set of "recreate" ops that must be applied on the merged branch 3640 // to recreate any directories that were modified in the unmerged 3641 // branch but removed in the merged branch. 3642 unmergedChains, mergedChains, unmergedPaths, mergedPaths, recOps, 3643 unmergedMDs, mergedMDs, err := 3644 cr.buildChainsAndPaths(ctx, lState, doLock) 3645 if err != nil { 3646 return 3647 } 3648 if len(unmergedMDs) == 0 { 3649 // TODO: This is probably due to an extra Resolve() call that 3650 // got queued during a resolution (but too late to cancel it), 3651 // and executed after the resolution completed successfully. 3652 cr.log.CDebugf(ctx, "No unmerged updates at all, so we must not be "+ 3653 "unmerged after all") 3654 return 3655 } 3656 if len(mergedPaths) == 0 || len(mergedMDs) == 0 { 3657 var mostRecentMergedMD ImmutableRootMetadata 3658 if len(mergedMDs) > 0 { 3659 mostRecentMergedMD = mergedMDs[len(mergedMDs)-1] 3660 } else { 3661 branchPoint := unmergedMDs[0].Revision() - 1 3662 mostRecentMergedMD, err = GetSingleMD(ctx, cr.config, cr.fbo.id(), 3663 kbfsmd.NullBranchID, branchPoint, kbfsmd.Merged, nil) 3664 if err != nil { 3665 return 3666 } 3667 } 3668 // TODO: All the other variables returned by 3669 // buildChainsAndPaths may also be nil, in which case 3670 // completeResolution will deref a nil pointer. Fix 3671 // this! 3672 // 3673 // nothing to do 3674 cr.log.CDebugf(ctx, "No updates to resolve, so finishing") 3675 dbm := newDirBlockMapMemory() 3676 newFileBlocks := newFileBlockMapMemory() 3677 bps := newBlockPutStateMemory(0) 3678 err = cr.completeResolution(ctx, lState, unmergedChains, 3679 mergedChains, unmergedPaths, mergedPaths, 3680 unmergedMDs[len(unmergedMDs)-1], mostRecentMergedMD, dbm, 3681 newFileBlocks, nil, bps, doLock) 3682 return 3683 } 3684 3685 err = cr.checkDone(ctx) 3686 if err != nil { 3687 return 3688 } 3689 3690 if status, _, err := cr.fbo.status.getStatus(ctx, nil); err == nil { 3691 if statusString, err := json.Marshal(status); err == nil { 3692 ci := func() conflictInput { 3693 cr.inputLock.Lock() 3694 defer cr.inputLock.Unlock() 3695 return cr.currInput 3696 }() 3697 cr.log.CInfof(ctx, "Current status during conflict resolution "+ 3698 "(input %v): %s", ci, statusString) 3699 } 3700 } 3701 cr.log.CDebugf(ctx, "Recreate ops: %s", recOps) 3702 3703 mostRecentMergedMD := mergedMDs[len(mergedMDs)-1] 3704 3705 mostRecentMergedWriterInfo := newWriterInfo( 3706 mostRecentMergedMD.LastModifyingWriter(), 3707 mostRecentMergedMD.LastModifyingWriterVerifyingKey(), 3708 mostRecentMergedMD.Revision(), cr.fbo.oa()) 3709 3710 // Step 2: Figure out which actions need to be taken in the merged 3711 // branch to best reflect the unmerged changes. The result of 3712 // this step is a map containing, for each node in the merged path 3713 // that will be updated during conflict resolution, a set of 3714 // "actions" to be applied to the merged branch. Each of these 3715 // actions contains the logic needed to manipulate the data into 3716 // the final merged state, including the resolution of any 3717 // conflicts that occurred between the two branches. 3718 actionMap, newUnmergedPaths, err := cr.computeActions( 3719 ctx, unmergedChains, mergedChains, unmergedPaths, mergedPaths, 3720 recOps, mostRecentMergedWriterInfo) 3721 if err != nil { 3722 return 3723 } 3724 3725 // Insert the new unmerged paths as needed 3726 if len(newUnmergedPaths) > 0 { 3727 unmergedPaths = append(unmergedPaths, newUnmergedPaths...) 3728 sort.Sort(crSortedPaths(unmergedPaths)) 3729 } 3730 3731 err = cr.checkDone(ctx) 3732 if err != nil { 3733 return 3734 } 3735 3736 cr.log.CDebugf(ctx, "Action map: %v", actionMap) 3737 3738 // Step 3: Apply the actions by looking up the corresponding 3739 // unmerged dir entry and copying it to a copy of the 3740 // corresponding merged block. Keep these dirty block copies in a 3741 // local dirty cache, keyed by corresponding merged most recent 3742 // pointer. 3743 // 3744 // At the same time, construct two sets of ops: one that will be 3745 // put into the final MD object that gets merged, and one that 3746 // needs to be played through as notifications locally to get any 3747 // local caches synchronized with the final merged state. 3748 // 3749 // * This will be taken care of by each crAction.updateOps() 3750 // method, which modifies the unmerged and merged ops for a 3751 // particular chain. After all the crActions are applied, the 3752 // "unmerged" ops need to be pushed as part of the MD update, 3753 // while the "merged" ops need to be applied locally. 3754 3755 // newFileBlocks contains the copies of the file blocks we need to 3756 // sync. If a block is indirect, we need to put it and add new 3757 // references for all indirect pointers inside it. If it is not 3758 // an indirect block, just add a new reference to the block. 3759 dbc, cleanupFn, err := cr.makeDiskBlockCache(ctx) 3760 if err != nil { 3761 return 3762 } 3763 if cleanupFn != nil { 3764 defer cleanupFn(ctx) 3765 } 3766 dirtyBcache := newDirtyBlockCacheDisk( 3767 cr.config, dbc, mergedChains.mostRecentChainMDInfo, cr.fbo.branch()) 3768 newFileBlocks := newFileBlockMapDisk( 3769 dirtyBcache, mergedChains.mostRecentChainMDInfo) 3770 // dbm contains the modified directory blocks we need to sync 3771 dbm := newDirBlockMapDisk(dirtyBcache, mergedChains.mostRecentChainMDInfo) 3772 3773 err = cr.doActions(ctx, lState, unmergedChains, mergedChains, 3774 unmergedPaths, mergedPaths, actionMap, dbm, newFileBlocks, dirtyBcache) 3775 if err != nil { 3776 return 3777 } 3778 3779 err = cr.checkDone(ctx) 3780 if err != nil { 3781 return 3782 } 3783 cr.log.CDebugf(ctx, "Executed all actions, %d updated directory blocks", 3784 dbm.numBlocks()) 3785 3786 // Step 4: finish up by syncing all the blocks, computing and 3787 // putting the final resolved MD, and issuing all the local 3788 // notifications. 3789 bps := newBlockPutStateDisk( 3790 0, cr.config, dbc, mergedChains.mostRecentChainMDInfo) 3791 err = cr.completeResolution(ctx, lState, unmergedChains, mergedChains, 3792 unmergedPaths, mergedPaths, unmergedMDs[len(unmergedMDs)-1], 3793 mostRecentMergedMD, dbm, newFileBlocks, dirtyBcache, bps, doLock) 3794 if err != nil { 3795 return 3796 } 3797 3798 // TODO: If conflict resolution fails after some blocks were put, 3799 // remember these and include them in the later resolution so they 3800 // don't count against the quota forever. (Though of course if we 3801 // completely fail, we'll need to rely on a future complete scan 3802 // to clean up the quota anyway . . .) 3803} 3804 3805func (cr *ConflictResolver) clearConflictRecords(ctx context.Context) error { 3806 db, key, _, wasStuck, err := cr.isStuckWithDbAndConflicts() 3807 if err != nil { 3808 return err 3809 } 3810 3811 err = db.Delete(key, nil) 3812 if err != nil { 3813 return err 3814 } 3815 3816 if wasStuck { 3817 cr.config.SubscriptionManagerPublisher().PublishChange(keybase1.SubscriptionTopic_FAVORITES) 3818 cr.config.Reporter().NotifyFavoritesChanged(ctx) 3819 cr.config.SubscriptionManagerPublisher().PublishChange( 3820 keybase1.SubscriptionTopic_FILES_TAB_BADGE) 3821 } 3822 return nil 3823} 3824 3825func openCRDBInternal(config Config) (*ldbutils.LevelDb, error) { 3826 if config.IsTestMode() { 3827 return ldbutils.OpenLevelDb(storage.NewMemStorage(), config.Mode()) 3828 } 3829 err := os.MkdirAll(sysPath.Join(config.StorageRoot(), 3830 conflictResolverRecordsDir, conflictResolverRecordsVersionString), 3831 os.ModePerm) 3832 if err != nil { 3833 return nil, err 3834 } 3835 3836 stor, err := storage.OpenFile(sysPath.Join(config.StorageRoot(), 3837 conflictResolverRecordsDir, conflictResolverRecordsVersionString, 3838 conflictResolverRecordsDB), false) 3839 3840 if err != nil { 3841 return nil, err 3842 } 3843 3844 return ldbutils.OpenLevelDb(stor, config.Mode()) 3845} 3846 3847func openCRDB(config Config) (db *ldbutils.LevelDb) { 3848 db, err := openCRDBInternal(config) 3849 if err != nil { 3850 config.MakeLogger("").CWarningf(context.Background(), 3851 "Could not open conflict resolver DB. "+ 3852 "Perhaps multiple KBFS instances are being run concurrently"+ 3853 "? Error: %+v", err) 3854 } 3855 return db 3856} 3857