hsync.go 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564
  1. // Copyright © 2015-2016 Pierre Neidhardt <ambrevar@gmail.com>
  2. // Use of this file is governed by the license that can be found in LICENSE.
  3. /*
  4. TODO: Add support for multiple targets.
  5. TARGETS can be analyzed in parallel but beware of race conditions when a
  6. conflict arises. Example: t1 in TARGET matches s1 in SOURCE and is stored in the
  7. structure. t2 in TARGET matches s1 too. There is a conflict. We need to update
  8. s1, t1 and t2 at the same time until t1 != t2 or end of file is reached.
  9. TODO: If duplicate count is the same on both sides, we could still process.
  10. We should minimize the number of renames.
  11. TODO: Multi-threading: The main structure should be mutexed, but the checksums can be parallelized.
  12. TODO: Save on resident memory usage.
  13. Currently 200000 files in /usr will require ~100 MB.
  14. Shall we use a trie to store paths? Not sure it would save memory.
  15. TODO: Possible optimization: we can skip target (sub)folders where
  16. os.SameFile(sourceFolder, targetFolder) == true. Then we need to store source's
  17. FileInfo in a map.
  18. TODO: This program could be split in two: the analyzer and the renamer.
  19. References: dupd, dupfinder, fdupes, gotsync, rmlint, rsync.
  20. */
  21. package main
  22. import (
  23. "crypto/md5"
  24. "encoding/json"
  25. "flag"
  26. "fmt"
  27. "hash"
  28. "io"
  29. "io/ioutil"
  30. "log"
  31. "os"
  32. "path/filepath"
  33. )
  34. const (
  35. application = "hsync"
  36. copyright = "Copyright (C) 2015-2016 Pierre Neidhardt"
  37. blocksize = 4096
  38. separator = string(os.PathSeparator)
  39. )
  40. var version = "<tip>"
  41. const usage = `Filesystem hierarchy synchronizer
  42. Rename files in TARGET so that identical files found in SOURCE and TARGET have
  43. the same relative path.
  44. The main goal of the program is to make folders synchronization faster by
  45. sparing big file transfers when a simple rename suffices. It complements other
  46. synchronization programs that lack this capability.
  47. By default, files are not renamed and a preview is printed to standard output.
  48. False positives can happen, e.g. if two different files in SOURCE and TARGET are
  49. the only ones of this size. Use the preview to spot false positives and make sure
  50. all files get renamed properly.
  51. You can redirect the preview to a file. If you run the program using this
  52. preview file as SOURCE, the analysis will be skipped. This is useful if you want
  53. to tweak the result of the analysis.
  54. Notes:
  55. - Duplicate files in either folder are skipped.
  56. - Only regular files are processed. In particular, empty folders and symbolic
  57. links are ignored.
  58. `
  59. // We attach a hash digest to the path so that we can update partial hashes with
  60. // the rolling-checksum function.
  61. type fileID struct {
  62. path string
  63. h hash.Hash
  64. }
  65. var unsolvable = fileID{path: separator}
  66. // A fileMatch stores 2 fileID with matching content. A match can be partial and
  67. // further processing can disprove it.
  68. // - If 'sourceID==nil', this is a dummy match. It means that a file of the same
  69. // size with a longer partialHash has been processed.
  70. // - If 'targetID==nil', a match is yet to be found.
  71. // - If 'targetID==&unsolvable', several TARGET files conflict together for this
  72. // SOURCE file, the entry should be skipped.
  73. type fileMatch struct {
  74. sourceID *fileID
  75. targetID *fileID
  76. }
  77. // partialHash is used as a key to identify the file content.
  78. // The 'size' field should always be set, however the 'pos' and 'hash' fields
  79. // are computed only when required. No hash has been computed when 'pos==0'.
  80. type partialHash struct {
  81. size int64
  82. pos int64
  83. hash string
  84. }
  85. // rollingChecksum returns io.EOF on last roll.
  86. // The caller needs not open `file`; it needs to close it however. This manual
  87. // management avoids having to open and close the file repeatedly.
  88. func rollingChecksum(fid *fileID, key *partialHash, file **os.File) (err error) {
  89. if *file == nil {
  90. *file, err = os.Open(fid.path)
  91. if err != nil {
  92. return
  93. }
  94. }
  95. buf := [blocksize]byte{}
  96. n, err := (*file).ReadAt(buf[:], key.pos*blocksize)
  97. if err != nil && err != io.EOF {
  98. return
  99. }
  100. // Failure means fatal memory error, no need to handle it.
  101. _, _ = fid.h.Write(buf[:n])
  102. key.pos++
  103. key.hash = string(fid.h.Sum(nil))
  104. return
  105. }
  106. func newFileEntry(path string, size int64) (fileID, partialHash) {
  107. return fileID{path: path, h: md5.New()}, partialHash{size: size}
  108. }
  109. func visitSource(root string, entries map[partialHash]fileMatch) {
  110. // Change folder to 'root' so that 'root' does not get stored in fileID.path.
  111. oldroot, err := os.Getwd()
  112. if err != nil {
  113. log.Fatal(err)
  114. }
  115. err = os.Chdir(root)
  116. if err != nil {
  117. log.Fatal(err)
  118. }
  119. // Chdir to oldroot can fail: if so, the error will be caught in the subsequent Chdir.
  120. defer os.Chdir(oldroot)
  121. visitor := func(input string, info os.FileInfo, ignored error) error {
  122. if !info.Mode().IsRegular() {
  123. return nil
  124. }
  125. // Ignore empty files as they add a lot of unnecessary noise to the
  126. // duplicate detection and output.
  127. if info.Size() == 0 {
  128. return nil
  129. }
  130. inputID, inputKey := newFileEntry(input, info.Size())
  131. var err error
  132. var inputFile, conflictFile *os.File
  133. defer func() {
  134. if inputFile != nil {
  135. inputFile.Close()
  136. }
  137. }()
  138. defer func() {
  139. if conflictFile != nil {
  140. conflictFile.Close()
  141. }
  142. }()
  143. // Skip dummy matches.
  144. v, ok := entries[inputKey]
  145. for ok && v.sourceID == nil && err != io.EOF {
  146. err = rollingChecksum(&inputID, &inputKey, &inputFile)
  147. if err != nil && err != io.EOF {
  148. log.Println(err)
  149. return nil
  150. }
  151. v, ok = entries[inputKey]
  152. }
  153. if ok && v.sourceID == nil {
  154. log.Printf("Source duplicate (%x) '%v'\n", inputKey.hash, inputID.path)
  155. return nil
  156. } else if !ok {
  157. entries[inputKey] = fileMatch{sourceID: &inputID}
  158. return nil
  159. }
  160. // Else there is a conflict.
  161. conflictKey := inputKey
  162. conflictID := entries[inputKey].sourceID
  163. for inputKey == conflictKey && err == nil {
  164. // Set dummy value to mark the key as visited for future files.
  165. entries[inputKey] = fileMatch{}
  166. err = rollingChecksum(&inputID, &inputKey, &inputFile)
  167. if err != nil && err != io.EOF {
  168. // Read error. Drop input.
  169. log.Println(err)
  170. return nil
  171. }
  172. err = rollingChecksum(conflictID, &conflictKey, &conflictFile)
  173. if err != nil && err != io.EOF {
  174. // Read error. We will replace conflict with input.
  175. log.Println(err)
  176. break
  177. }
  178. }
  179. if inputKey == conflictKey && err == io.EOF {
  180. entries[inputKey] = fileMatch{}
  181. log.Printf("Source duplicate (%x) '%v'\n", inputKey.hash, inputID.path)
  182. log.Printf("Source duplicate (%x) '%v'\n", conflictKey.hash, conflictID.path)
  183. } else {
  184. // Resolved conflict.
  185. entries[inputKey] = fileMatch{sourceID: &inputID}
  186. if err == nil || err == io.EOF {
  187. // Re-add conflicting file except on read error.
  188. entries[conflictKey] = fileMatch{sourceID: conflictID}
  189. }
  190. }
  191. return nil
  192. }
  193. // Since we do not stop on read errors while walking, the returned error is
  194. // always nil.
  195. _ = filepath.Walk(".", visitor)
  196. }
  197. // See comments in visitSource.
  198. func visitTarget(root, sourceRoot string, entries map[partialHash]fileMatch) {
  199. oldroot, err := os.Getwd()
  200. if err != nil {
  201. log.Fatal(err)
  202. }
  203. err = os.Chdir(root)
  204. if err != nil {
  205. log.Fatal(err)
  206. }
  207. defer os.Chdir(oldroot)
  208. visitor := func(input string, info os.FileInfo, ignored error) error {
  209. if !info.Mode().IsRegular() {
  210. return nil
  211. }
  212. if info.Size() == 0 {
  213. return nil
  214. }
  215. inputID, inputKey := newFileEntry(input, info.Size())
  216. var err error
  217. var inputFile, conflictFile, sourceFile *os.File
  218. defer func() {
  219. if inputFile != nil {
  220. inputFile.Close()
  221. }
  222. }()
  223. defer func() {
  224. if conflictFile != nil {
  225. conflictFile.Close()
  226. }
  227. }()
  228. defer func() {
  229. if sourceFile != nil {
  230. sourceFile.Close()
  231. }
  232. }()
  233. // Skip dummy matches.
  234. v, ok := entries[inputKey]
  235. for ok && v.sourceID == nil && err != io.EOF {
  236. err = rollingChecksum(&inputID, &inputKey, &inputFile)
  237. if err != nil && err != io.EOF {
  238. log.Println(err)
  239. return nil
  240. }
  241. v, ok = entries[inputKey]
  242. }
  243. if ok && v.sourceID == nil {
  244. log.Printf("Target duplicate match (%x) '%v'\n", inputKey.hash, inputID.path)
  245. return nil
  246. } else if ok && v.targetID != nil && v.targetID == &unsolvable {
  247. // Unresolved conflict happened previously.
  248. log.Printf("Target duplicate (%x) '%v', source match '%v'\n", inputKey.hash, inputID.path, v.sourceID.path)
  249. return nil
  250. } else if !ok {
  251. // No matching file in source.
  252. return nil
  253. } else if v.targetID == nil {
  254. // First match.
  255. entries[inputKey] = fileMatch{sourceID: entries[inputKey].sourceID, targetID: &inputID}
  256. return nil
  257. }
  258. // Else there is a conflict.
  259. sourceKey := inputKey
  260. sourceID := entries[inputKey].sourceID
  261. conflictKey := inputKey
  262. conflictID := entries[inputKey].targetID
  263. for inputKey == conflictKey && inputKey == sourceKey && err == nil {
  264. // Set dummy value to mark the key as visited for future files.
  265. entries[inputKey] = fileMatch{}
  266. // Since we change folders, we don't have to store the root in fileID, nor
  267. // we have to compute sourceRoot's realpath to open the file from this
  268. // point.
  269. _ = os.Chdir(oldroot)
  270. err = os.Chdir(sourceRoot)
  271. if err != nil {
  272. log.Fatal(err)
  273. }
  274. err = rollingChecksum(sourceID, &sourceKey, &sourceFile)
  275. _ = os.Chdir(oldroot)
  276. err = os.Chdir(root)
  277. if err != nil {
  278. log.Fatal(err)
  279. }
  280. if err != nil && err != io.EOF {
  281. // Read error. Drop all entries.
  282. log.Println(err)
  283. return nil
  284. }
  285. err = rollingChecksum(&inputID, &inputKey, &inputFile)
  286. inputErr := err
  287. if err != nil && err != io.EOF {
  288. // Read error. Drop input.
  289. log.Println(err)
  290. // We don't break now as there is still a chance that the conflicting
  291. // file matches the source.
  292. }
  293. err = rollingChecksum(conflictID, &conflictKey, &conflictFile)
  294. if err != nil && err != io.EOF {
  295. // Read error. We will replace conflict with input if the latter has
  296. // been read correctly.
  297. log.Println(err)
  298. break
  299. }
  300. if inputErr != nil && inputErr != io.EOF {
  301. break
  302. }
  303. }
  304. if inputKey == sourceKey && inputKey == conflictKey && err == io.EOF {
  305. log.Printf("Target duplicate (%x) '%v', source match '%v'\n", inputKey.hash, inputID.path, v.sourceID.path)
  306. log.Printf("Target duplicate (%x) '%v', source match '%v'\n", conflictKey.hash, conflictID.path, v.sourceID.path)
  307. // We mark the source file with an unresolved conflict for future target files.
  308. entries[sourceKey] = fileMatch{sourceID: sourceID, targetID: &unsolvable}
  309. } else if inputKey == sourceKey && inputKey != conflictKey {
  310. // Resolution: drop conflicting entry.
  311. entries[sourceKey] = fileMatch{sourceID: sourceID, targetID: &inputID}
  312. } else if conflictKey == sourceKey && conflictKey != inputKey {
  313. // Resolution: drop input entry.
  314. entries[sourceKey] = fileMatch{sourceID: sourceID, targetID: conflictID}
  315. } else if conflictKey != sourceKey && inputKey != sourceKey {
  316. // Resolution: drop both entries.
  317. entries[sourceKey] = fileMatch{sourceID: sourceID}
  318. }
  319. // Else we drop all entries.
  320. return nil
  321. }
  322. _ = filepath.Walk(".", visitor)
  323. }
  324. // Rename files as specified in renameOps.
  325. // Chains and cycles may occur. See the implementation details.
  326. func processRenames(root string, renameOps, reverseOps map[string]string, clobber bool) {
  327. // Change folder since the renames are made relatively to 'root'.
  328. oldroot, err := os.Getwd()
  329. if err != nil {
  330. log.Fatal(err)
  331. }
  332. err = os.Chdir(root)
  333. if err != nil {
  334. log.Fatal(err)
  335. }
  336. defer os.Chdir(oldroot)
  337. for oldpath, newpath := range renameOps {
  338. if oldpath == newpath {
  339. continue
  340. }
  341. cycleMarker := oldpath
  342. // Go forward to the end of the chain or the cycle.
  343. for newpath != cycleMarker {
  344. _, ok := renameOps[newpath]
  345. if !ok {
  346. break
  347. }
  348. oldpath = newpath
  349. newpath = renameOps[newpath]
  350. }
  351. // If cycle, break it down to a chain.
  352. if cycleMarker == newpath {
  353. f, err := ioutil.TempFile(".", application)
  354. if err != nil {
  355. log.Fatal(err)
  356. }
  357. tmp := f.Name()
  358. f.Close()
  359. err = os.Rename(oldpath, tmp)
  360. if err != nil {
  361. log.Println(err)
  362. } else {
  363. log.Printf("Rename '%v' -> '%v'", oldpath, tmp)
  364. }
  365. // Plug temp file to the other end of the chain.
  366. reverseOps[cycleMarker] = tmp
  367. // During one loop over 'renameOps', we may process several operations in
  368. // case of chains and cycles. Remove rename operation so that no other
  369. // loop over 'renameOps' processes it again.
  370. delete(renameOps, oldpath)
  371. // Go backward.
  372. newpath = oldpath
  373. oldpath = reverseOps[oldpath]
  374. }
  375. // Process the chain of renames. Renaming can still fail, in which case we
  376. // output the error and go on with the chain.
  377. for oldpath != "" {
  378. err = os.MkdirAll(filepath.Dir(newpath), 0777)
  379. if err != nil {
  380. log.Println(err)
  381. } else {
  382. // There is a race condition between the existence check and the rename.
  383. // We could create a hard link to rename atomically without overwriting.
  384. // But 1) we need to remove the original link afterward, so we lose
  385. // atomicity, 2) hard links are not supported by all filesystems.
  386. exists := false
  387. if !clobber {
  388. _, err = os.Stat(newpath)
  389. if err == nil || os.IsExist(err) {
  390. exists = true
  391. }
  392. }
  393. if clobber || !exists {
  394. err := os.Rename(oldpath, newpath)
  395. if err != nil {
  396. log.Println(err)
  397. } else {
  398. log.Printf("Rename '%v' -> '%v'", oldpath, newpath)
  399. }
  400. } else {
  401. log.Printf("Destination exists, skip renaming: '%v' -> '%v'", oldpath, newpath)
  402. }
  403. }
  404. delete(renameOps, oldpath)
  405. newpath = oldpath
  406. oldpath = reverseOps[oldpath]
  407. }
  408. }
  409. }
  410. func init() {
  411. log.SetFlags(0)
  412. }
  413. func main() {
  414. flag.Usage = func() {
  415. fmt.Fprintf(os.Stderr, "Usage: %v SOURCE TARGET\n\n", os.Args[0])
  416. fmt.Fprintln(os.Stderr, usage)
  417. fmt.Fprintln(os.Stderr, "Options:")
  418. flag.PrintDefaults()
  419. }
  420. var flagClobber = flag.Bool("f", false, "Overwrite existing files in TARGETS.")
  421. var flagProcess = flag.Bool("p", false, "Rename the files in TARGETS.")
  422. var flagVersion = flag.Bool("v", false, "Print version and exit.")
  423. flag.Parse()
  424. if *flagVersion {
  425. fmt.Println(application, version, copyright)
  426. return
  427. }
  428. if flag.Arg(0) == "" || flag.Arg(1) == "" {
  429. flag.Usage()
  430. return
  431. }
  432. renameOps := make(map[string]string)
  433. reverseOps := make(map[string]string)
  434. s, err := os.Stat(flag.Arg(0))
  435. if err != nil {
  436. log.Fatal(err)
  437. }
  438. if s.IsDir() {
  439. entries := make(map[partialHash]fileMatch)
  440. log.Printf(":: Analyzing '%v'", flag.Arg(0))
  441. visitSource(flag.Arg(0), entries)
  442. log.Printf(":: Analyzing '%v'", flag.Arg(1))
  443. visitTarget(flag.Arg(1), flag.Arg(0), entries)
  444. for _, v := range entries {
  445. if v.targetID != nil && v.targetID != &unsolvable && v.targetID.path != v.sourceID.path {
  446. renameOps[v.targetID.path] = v.sourceID.path
  447. reverseOps[v.sourceID.path] = v.targetID.path
  448. }
  449. }
  450. } else {
  451. buf, err := ioutil.ReadFile(flag.Arg(0))
  452. if err != nil {
  453. log.Fatal(err)
  454. }
  455. err = json.Unmarshal(buf, &renameOps)
  456. if err != nil {
  457. log.Fatal(err)
  458. }
  459. for oldpath, newpath := range renameOps {
  460. if oldpath == newpath {
  461. delete(renameOps, oldpath)
  462. continue
  463. }
  464. _, err := os.Stat(flag.Arg(1) + separator + oldpath)
  465. if err != nil && os.IsNotExist(err) {
  466. // Remove non-existing entries.
  467. delete(renameOps, oldpath)
  468. continue
  469. }
  470. reverseOps[newpath] = oldpath
  471. }
  472. }
  473. if *flagProcess {
  474. log.Println(":: Processing renames")
  475. processRenames(flag.Arg(1), renameOps, reverseOps, *flagClobber)
  476. } else {
  477. log.Println(":: Previewing renames")
  478. // There should be no error.
  479. buf, _ := json.MarshalIndent(renameOps, "", "\t")
  480. // Failure means fatal I/O error, no need to handle it.
  481. _, _ = os.Stdout.Write(buf)
  482. fmt.Println()
  483. }
  484. }