fakefs.go 21 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938
  1. // Copyright (C) 2018 The Syncthing Authors.
  2. //
  3. // This Source Code Form is subject to the terms of the Mozilla Public
  4. // License, v. 2.0. If a copy of the MPL was not distributed with this file,
  5. // You can obtain one at https://mozilla.org/MPL/2.0/.
  6. package fs
  7. import (
  8. "context"
  9. "errors"
  10. "fmt"
  11. "hash/fnv"
  12. "io"
  13. "io/ioutil"
  14. "math/rand"
  15. "net/url"
  16. "os"
  17. "path/filepath"
  18. "strconv"
  19. "strings"
  20. "sync"
  21. "testing"
  22. "time"
  23. )
  24. // see readShortAt()
  25. const randomBlockShift = 14 // 128k
  26. // fakefs is a fake filesystem for testing and benchmarking. It has the
  27. // following properties:
  28. //
  29. // - File metadata is kept in RAM. Specifically, we remember which files and
  30. // directories exist, their dates, permissions and sizes. Symlinks are
  31. // not supported.
  32. //
  33. // - File contents are generated pseudorandomly with just the file name as
  34. // seed. Writes are discarded, other than having the effect of increasing
  35. // the file size. If you only write data that you've read from a file with
  36. // the same name on a different fakefs, you'll never know the difference...
  37. //
  38. // - We totally ignore permissions - pretend you are root.
  39. //
  40. // - The root path can contain URL query-style parameters that pre populate
  41. // the filesystem at creation with a certain amount of random data:
  42. //
  43. // files=n to generate n random files (default 0)
  44. // maxsize=n to generate files up to a total of n MiB (default 0)
  45. // sizeavg=n to set the average size of random files, in bytes (default 1<<20)
  46. // seed=n to set the initial random seed (default 0)
  47. // insens=b "true" makes filesystem case-insensitive Windows- or OSX-style (default false)
  48. // latency=d to set the amount of time each "disk" operation takes, where d is time.ParseDuration format
  49. //
  50. // - Two fakefs:s pointing at the same root path see the same files.
  51. //
  52. type fakefs struct {
  53. counters fakefsCounters
  54. uri string
  55. mut sync.Mutex
  56. root *fakeEntry
  57. insens bool
  58. withContent bool
  59. latency time.Duration
  60. }
  61. type fakefsCounters struct {
  62. Chmod int64
  63. Lchown int64
  64. Chtimes int64
  65. Create int64
  66. DirNames int64
  67. Lstat int64
  68. Mkdir int64
  69. MkdirAll int64
  70. Open int64
  71. OpenFile int64
  72. ReadSymlink int64
  73. Remove int64
  74. RemoveAll int64
  75. Rename int64
  76. }
  77. var (
  78. fakefsMut sync.Mutex
  79. fakefsFs = make(map[string]*fakefs)
  80. )
  81. func newFakeFilesystem(rootURI string, _ ...Option) *fakefs {
  82. fakefsMut.Lock()
  83. defer fakefsMut.Unlock()
  84. root := rootURI
  85. var params url.Values
  86. uri, err := url.Parse(rootURI)
  87. if err == nil {
  88. root = uri.Path
  89. params = uri.Query()
  90. }
  91. if fs, ok := fakefsFs[rootURI]; ok {
  92. // Already have an fs at this path
  93. return fs
  94. }
  95. fs := &fakefs{
  96. uri: "fake://" + rootURI,
  97. root: &fakeEntry{
  98. name: "/",
  99. entryType: fakeEntryTypeDir,
  100. mode: 0700,
  101. mtime: time.Now(),
  102. children: make(map[string]*fakeEntry),
  103. },
  104. }
  105. files, _ := strconv.Atoi(params.Get("files"))
  106. maxsize, _ := strconv.Atoi(params.Get("maxsize"))
  107. sizeavg, _ := strconv.Atoi(params.Get("sizeavg"))
  108. seed, _ := strconv.Atoi(params.Get("seed"))
  109. fs.insens = params.Get("insens") == "true"
  110. fs.withContent = params.Get("content") == "true"
  111. if sizeavg == 0 {
  112. sizeavg = 1 << 20
  113. }
  114. if files > 0 || maxsize > 0 {
  115. // Generate initial data according to specs. Operations in here
  116. // *look* like file I/O, but they are not. Do not worry that they
  117. // might fail.
  118. rng := rand.New(rand.NewSource(int64(seed)))
  119. var createdFiles int
  120. var writtenData int64
  121. for (files == 0 || createdFiles < files) && (maxsize == 0 || writtenData>>20 < int64(maxsize)) {
  122. dir := filepath.Join(fmt.Sprintf("%02x", rng.Intn(255)), fmt.Sprintf("%02x", rng.Intn(255)))
  123. file := fmt.Sprintf("%016x", rng.Int63())
  124. fs.MkdirAll(dir, 0755)
  125. fd, _ := fs.Create(filepath.Join(dir, file))
  126. createdFiles++
  127. fsize := int64(sizeavg/2 + rng.Intn(sizeavg))
  128. fd.Truncate(fsize)
  129. writtenData += fsize
  130. ftime := time.Unix(1000000000+rng.Int63n(10*365*86400), 0)
  131. fs.Chtimes(filepath.Join(dir, file), ftime, ftime)
  132. }
  133. }
  134. // Also create a default folder marker for good measure
  135. fs.Mkdir(".stfolder", 0700)
  136. // We only set the latency after doing the operations required to create
  137. // the filesystem initially.
  138. fs.latency, _ = time.ParseDuration(params.Get("latency"))
  139. fakefsFs[root] = fs
  140. return fs
  141. }
  142. type fakeEntryType int
  143. const (
  144. fakeEntryTypeFile fakeEntryType = iota
  145. fakeEntryTypeDir
  146. fakeEntryTypeSymlink
  147. )
  148. // fakeEntry is an entry (file or directory) in the fake filesystem
  149. type fakeEntry struct {
  150. name string
  151. entryType fakeEntryType
  152. dest string // for symlinks
  153. size int64
  154. mode FileMode
  155. uid int
  156. gid int
  157. mtime time.Time
  158. children map[string]*fakeEntry
  159. content []byte
  160. }
  161. func (fs *fakefs) entryForName(name string) *fakeEntry {
  162. // bug: lookup doesn't work through symlinks.
  163. if fs.insens {
  164. name = UnicodeLowercase(name)
  165. }
  166. name = filepath.ToSlash(name)
  167. if name == "." || name == "/" {
  168. return fs.root
  169. }
  170. name = strings.Trim(name, "/")
  171. comps := strings.Split(name, "/")
  172. entry := fs.root
  173. for _, comp := range comps {
  174. if entry.entryType != fakeEntryTypeDir {
  175. return nil
  176. }
  177. var ok bool
  178. entry, ok = entry.children[comp]
  179. if !ok {
  180. return nil
  181. }
  182. }
  183. return entry
  184. }
  185. func (fs *fakefs) Chmod(name string, mode FileMode) error {
  186. fs.mut.Lock()
  187. defer fs.mut.Unlock()
  188. fs.counters.Chmod++
  189. time.Sleep(fs.latency)
  190. entry := fs.entryForName(name)
  191. if entry == nil {
  192. return os.ErrNotExist
  193. }
  194. entry.mode = mode
  195. return nil
  196. }
  197. func (fs *fakefs) Lchown(name string, uid, gid int) error {
  198. fs.mut.Lock()
  199. defer fs.mut.Unlock()
  200. fs.counters.Lchown++
  201. time.Sleep(fs.latency)
  202. entry := fs.entryForName(name)
  203. if entry == nil {
  204. return os.ErrNotExist
  205. }
  206. entry.uid = uid
  207. entry.gid = gid
  208. return nil
  209. }
  210. func (fs *fakefs) Chtimes(name string, atime time.Time, mtime time.Time) error {
  211. fs.mut.Lock()
  212. defer fs.mut.Unlock()
  213. fs.counters.Chtimes++
  214. time.Sleep(fs.latency)
  215. entry := fs.entryForName(name)
  216. if entry == nil {
  217. return os.ErrNotExist
  218. }
  219. entry.mtime = mtime
  220. return nil
  221. }
  222. func (fs *fakefs) create(name string) (*fakeEntry, error) {
  223. fs.mut.Lock()
  224. defer fs.mut.Unlock()
  225. fs.counters.Create++
  226. time.Sleep(fs.latency)
  227. if entry := fs.entryForName(name); entry != nil {
  228. if entry.entryType == fakeEntryTypeDir {
  229. return nil, os.ErrExist
  230. } else if entry.entryType == fakeEntryTypeSymlink {
  231. return nil, errors.New("following symlink not supported")
  232. }
  233. entry.size = 0
  234. entry.mtime = time.Now()
  235. entry.mode = 0666
  236. entry.content = nil
  237. if fs.withContent {
  238. entry.content = make([]byte, 0)
  239. }
  240. return entry, nil
  241. }
  242. dir := filepath.Dir(name)
  243. base := filepath.Base(name)
  244. entry := fs.entryForName(dir)
  245. if entry == nil {
  246. return nil, os.ErrNotExist
  247. }
  248. new := &fakeEntry{
  249. name: base,
  250. mode: 0666,
  251. mtime: time.Now(),
  252. }
  253. if fs.insens {
  254. base = UnicodeLowercase(base)
  255. }
  256. if fs.withContent {
  257. new.content = make([]byte, 0)
  258. }
  259. entry.children[base] = new
  260. return new, nil
  261. }
  262. func (fs *fakefs) Create(name string) (File, error) {
  263. entry, err := fs.create(name)
  264. if err != nil {
  265. return nil, err
  266. }
  267. if fs.insens {
  268. return &fakeFile{fakeEntry: entry, presentedName: filepath.Base(name)}, nil
  269. }
  270. return &fakeFile{fakeEntry: entry}, nil
  271. }
  272. func (fs *fakefs) CreateSymlink(target, name string) error {
  273. entry, err := fs.create(name)
  274. if err != nil {
  275. return err
  276. }
  277. entry.entryType = fakeEntryTypeSymlink
  278. entry.dest = target
  279. return nil
  280. }
  281. func (fs *fakefs) DirNames(name string) ([]string, error) {
  282. fs.mut.Lock()
  283. defer fs.mut.Unlock()
  284. fs.counters.DirNames++
  285. time.Sleep(fs.latency)
  286. entry := fs.entryForName(name)
  287. if entry == nil {
  288. return nil, os.ErrNotExist
  289. }
  290. names := make([]string, 0, len(entry.children))
  291. for _, child := range entry.children {
  292. names = append(names, child.name)
  293. }
  294. return names, nil
  295. }
  296. func (fs *fakefs) Lstat(name string) (FileInfo, error) {
  297. fs.mut.Lock()
  298. defer fs.mut.Unlock()
  299. fs.counters.Lstat++
  300. time.Sleep(fs.latency)
  301. entry := fs.entryForName(name)
  302. if entry == nil {
  303. return nil, os.ErrNotExist
  304. }
  305. info := &fakeFileInfo{*entry}
  306. if fs.insens {
  307. info.name = filepath.Base(name)
  308. }
  309. return info, nil
  310. }
  311. func (fs *fakefs) Mkdir(name string, perm FileMode) error {
  312. fs.mut.Lock()
  313. defer fs.mut.Unlock()
  314. fs.counters.Mkdir++
  315. time.Sleep(fs.latency)
  316. dir := filepath.Dir(name)
  317. base := filepath.Base(name)
  318. entry := fs.entryForName(dir)
  319. key := base
  320. if entry == nil {
  321. return os.ErrNotExist
  322. }
  323. if entry.entryType != fakeEntryTypeDir {
  324. return os.ErrExist
  325. }
  326. if fs.insens {
  327. key = UnicodeLowercase(key)
  328. }
  329. if _, ok := entry.children[key]; ok {
  330. return os.ErrExist
  331. }
  332. entry.children[key] = &fakeEntry{
  333. name: base,
  334. entryType: fakeEntryTypeDir,
  335. mode: perm,
  336. mtime: time.Now(),
  337. children: make(map[string]*fakeEntry),
  338. }
  339. return nil
  340. }
  341. func (fs *fakefs) MkdirAll(name string, perm FileMode) error {
  342. fs.mut.Lock()
  343. defer fs.mut.Unlock()
  344. fs.counters.MkdirAll++
  345. time.Sleep(fs.latency)
  346. name = filepath.ToSlash(name)
  347. name = strings.Trim(name, "/")
  348. comps := strings.Split(name, "/")
  349. entry := fs.root
  350. for _, comp := range comps {
  351. key := comp
  352. if fs.insens {
  353. key = UnicodeLowercase(key)
  354. }
  355. next, ok := entry.children[key]
  356. if !ok {
  357. new := &fakeEntry{
  358. name: comp,
  359. entryType: fakeEntryTypeDir,
  360. mode: perm,
  361. mtime: time.Now(),
  362. children: make(map[string]*fakeEntry),
  363. }
  364. entry.children[key] = new
  365. next = new
  366. } else if next.entryType != fakeEntryTypeDir {
  367. return errors.New("not a directory")
  368. }
  369. entry = next
  370. }
  371. return nil
  372. }
  373. func (fs *fakefs) Open(name string) (File, error) {
  374. fs.mut.Lock()
  375. defer fs.mut.Unlock()
  376. fs.counters.Open++
  377. time.Sleep(fs.latency)
  378. entry := fs.entryForName(name)
  379. if entry == nil || entry.entryType != fakeEntryTypeFile {
  380. return nil, os.ErrNotExist
  381. }
  382. if fs.insens {
  383. return &fakeFile{fakeEntry: entry, presentedName: filepath.Base(name)}, nil
  384. }
  385. return &fakeFile{fakeEntry: entry}, nil
  386. }
  387. func (fs *fakefs) OpenFile(name string, flags int, mode FileMode) (File, error) {
  388. if flags&os.O_CREATE == 0 {
  389. return fs.Open(name)
  390. }
  391. fs.mut.Lock()
  392. defer fs.mut.Unlock()
  393. fs.counters.OpenFile++
  394. time.Sleep(fs.latency)
  395. dir := filepath.Dir(name)
  396. base := filepath.Base(name)
  397. entry := fs.entryForName(dir)
  398. key := base
  399. if entry == nil {
  400. return nil, os.ErrNotExist
  401. } else if entry.entryType != fakeEntryTypeDir {
  402. return nil, errors.New("not a directory")
  403. }
  404. if fs.insens {
  405. key = UnicodeLowercase(key)
  406. }
  407. if flags&os.O_EXCL != 0 {
  408. if _, ok := entry.children[key]; ok {
  409. return nil, os.ErrExist
  410. }
  411. }
  412. newEntry := &fakeEntry{
  413. name: base,
  414. mode: mode,
  415. mtime: time.Now(),
  416. }
  417. if fs.withContent {
  418. newEntry.content = make([]byte, 0)
  419. }
  420. entry.children[key] = newEntry
  421. return &fakeFile{fakeEntry: newEntry}, nil
  422. }
  423. func (fs *fakefs) ReadSymlink(name string) (string, error) {
  424. fs.mut.Lock()
  425. defer fs.mut.Unlock()
  426. fs.counters.ReadSymlink++
  427. time.Sleep(fs.latency)
  428. entry := fs.entryForName(name)
  429. if entry == nil {
  430. return "", os.ErrNotExist
  431. } else if entry.entryType != fakeEntryTypeSymlink {
  432. return "", errors.New("not a symlink")
  433. }
  434. return entry.dest, nil
  435. }
  436. func (fs *fakefs) Remove(name string) error {
  437. fs.mut.Lock()
  438. defer fs.mut.Unlock()
  439. fs.counters.Remove++
  440. time.Sleep(fs.latency)
  441. if fs.insens {
  442. name = UnicodeLowercase(name)
  443. }
  444. entry := fs.entryForName(name)
  445. if entry == nil {
  446. return os.ErrNotExist
  447. }
  448. if len(entry.children) != 0 {
  449. return errors.New("not empty")
  450. }
  451. entry = fs.entryForName(filepath.Dir(name))
  452. delete(entry.children, filepath.Base(name))
  453. return nil
  454. }
  455. func (fs *fakefs) RemoveAll(name string) error {
  456. fs.mut.Lock()
  457. defer fs.mut.Unlock()
  458. fs.counters.RemoveAll++
  459. time.Sleep(fs.latency)
  460. if fs.insens {
  461. name = UnicodeLowercase(name)
  462. }
  463. entry := fs.entryForName(filepath.Dir(name))
  464. if entry == nil {
  465. return nil // all tested real systems exibit this behaviour
  466. }
  467. // RemoveAll is easy when the file system uses garbage collection under
  468. // the hood... We even get the correct semantics for open fd:s for free.
  469. delete(entry.children, filepath.Base(name))
  470. return nil
  471. }
  472. func (fs *fakefs) Rename(oldname, newname string) error {
  473. fs.mut.Lock()
  474. defer fs.mut.Unlock()
  475. fs.counters.Rename++
  476. time.Sleep(fs.latency)
  477. oldKey := filepath.Base(oldname)
  478. newKey := filepath.Base(newname)
  479. if fs.insens {
  480. oldKey = UnicodeLowercase(oldKey)
  481. newKey = UnicodeLowercase(newKey)
  482. }
  483. p0 := fs.entryForName(filepath.Dir(oldname))
  484. if p0 == nil {
  485. return os.ErrNotExist
  486. }
  487. entry := p0.children[oldKey]
  488. if entry == nil {
  489. return os.ErrNotExist
  490. }
  491. p1 := fs.entryForName(filepath.Dir(newname))
  492. if p1 == nil {
  493. return os.ErrNotExist
  494. }
  495. dst, ok := p1.children[newKey]
  496. if ok {
  497. if fs.insens && newKey == oldKey {
  498. // case-only in-place rename
  499. entry.name = filepath.Base(newname)
  500. return nil
  501. }
  502. if dst.entryType == fakeEntryTypeDir {
  503. return errors.New("is a directory")
  504. }
  505. }
  506. p1.children[newKey] = entry
  507. entry.name = filepath.Base(newname)
  508. delete(p0.children, oldKey)
  509. return nil
  510. }
  511. func (fs *fakefs) Stat(name string) (FileInfo, error) {
  512. return fs.Lstat(name)
  513. }
  514. func (fs *fakefs) SymlinksSupported() bool {
  515. return false
  516. }
  517. func (fs *fakefs) Walk(name string, walkFn WalkFunc) error {
  518. return errors.New("not implemented")
  519. }
  520. func (fs *fakefs) Watch(path string, ignore Matcher, ctx context.Context, ignorePerms bool) (<-chan Event, <-chan error, error) {
  521. return nil, nil, ErrWatchNotSupported
  522. }
  523. func (fs *fakefs) Hide(name string) error {
  524. return nil
  525. }
  526. func (fs *fakefs) Unhide(name string) error {
  527. return nil
  528. }
  529. func (fs *fakefs) Glob(pattern string) ([]string, error) {
  530. // gnnh we don't seem to actually require this in practice
  531. return nil, errors.New("not implemented")
  532. }
  533. func (fs *fakefs) Roots() ([]string, error) {
  534. return []string{"/"}, nil
  535. }
  536. func (fs *fakefs) Usage(name string) (Usage, error) {
  537. return Usage{}, errors.New("not implemented")
  538. }
  539. func (fs *fakefs) Type() FilesystemType {
  540. return FilesystemTypeFake
  541. }
  542. func (fs *fakefs) URI() string {
  543. return fs.uri
  544. }
  545. func (fs *fakefs) SameFile(fi1, fi2 FileInfo) bool {
  546. // BUG: real systems base file sameness on path, inodes, etc
  547. // we try our best, but FileInfo just doesn't have enough data
  548. // so there be false positives, especially on Windows
  549. // where ModTime is not that precise
  550. var ok bool
  551. if fs.insens {
  552. ok = UnicodeLowercase(fi1.Name()) == UnicodeLowercase(fi2.Name())
  553. } else {
  554. ok = fi1.Name() == fi2.Name()
  555. }
  556. return ok && fi1.ModTime().Equal(fi2.ModTime()) && fi1.Mode() == fi2.Mode() && fi1.IsDir() == fi2.IsDir() && fi1.IsRegular() == fi2.IsRegular() && fi1.IsSymlink() == fi2.IsSymlink() && fi1.Owner() == fi2.Owner() && fi1.Group() == fi2.Group()
  557. }
  558. func (fs *fakefs) resetCounters() {
  559. fs.mut.Lock()
  560. fs.counters = fakefsCounters{}
  561. fs.mut.Unlock()
  562. }
  563. func (fs *fakefs) reportMetricsPerOp(b *testing.B) {
  564. fs.reportMetricsPer(b, 1, "op")
  565. }
  566. func (fs *fakefs) reportMetricsPer(b *testing.B, divisor float64, unit string) {
  567. fs.mut.Lock()
  568. defer fs.mut.Unlock()
  569. b.ReportMetric(float64(fs.counters.Lstat)/divisor/float64(b.N), "Lstat/"+unit)
  570. b.ReportMetric(float64(fs.counters.DirNames)/divisor/float64(b.N), "DirNames/"+unit)
  571. }
  572. // fakeFile is the representation of an open file. We don't care if it's
  573. // opened for reading or writing, it's all good.
  574. type fakeFile struct {
  575. *fakeEntry
  576. mut sync.Mutex
  577. rng io.Reader
  578. seed int64
  579. offset int64
  580. seedOffs int64
  581. presentedName string // present (i.e. != "") on insensitive fs only
  582. }
  583. func (f *fakeFile) Close() error {
  584. return nil
  585. }
  586. func (f *fakeFile) Read(p []byte) (int, error) {
  587. f.mut.Lock()
  588. defer f.mut.Unlock()
  589. return f.readShortAt(p, f.offset)
  590. }
  591. func (f *fakeFile) ReadAt(p []byte, offs int64) (int, error) {
  592. f.mut.Lock()
  593. defer f.mut.Unlock()
  594. // ReadAt is spec:ed to always read a full block unless EOF or failure,
  595. // so we must loop. It's also not supposed to affect the seek position,
  596. // but that would make things annoying or inefficient in terms of
  597. // generating the appropriate RNG etc so I ignore that. In practice we
  598. // currently don't depend on that aspect of it...
  599. var read int
  600. for {
  601. n, err := f.readShortAt(p[read:], offs+int64(read))
  602. read += n
  603. if err != nil {
  604. return read, err
  605. }
  606. if read == len(p) {
  607. return read, nil
  608. }
  609. }
  610. }
  611. func (f *fakeFile) readShortAt(p []byte, offs int64) (int, error) {
  612. // Here be a certain amount of magic... We want to return pseudorandom,
  613. // predictable data so that a read from the same offset in the same file
  614. // always returns the same data. But the RNG is a stream, and reads can
  615. // be random.
  616. //
  617. // We split the file into "blocks" numbered by "seedNo", where each
  618. // block becomes an instantiation of the RNG, seeded with the hash of
  619. // the file number plus the seedNo (block number). We keep the RNG
  620. // around in the hope that the next read will be sequential to this one
  621. // and we can continue reading from the same RNG.
  622. //
  623. // When that's not the case we create a new RNG for the block we are in,
  624. // read as many bytes from it as necessary to get to the right offset,
  625. // and then serve the read from there. We limit the length of the read
  626. // to the end of the block, as another RNG needs to be created to serve
  627. // the next block.
  628. //
  629. // The size of the blocks are a matter of taste... Larger blocks give
  630. // better performance for sequential reads, but worse for random reads
  631. // as we often need to generate and throw away a lot of data at the
  632. // start of the block to serve a given read. 128 KiB blocks fit
  633. // reasonably well with the type of IO Syncthing tends to do.
  634. if f.entryType == fakeEntryTypeDir {
  635. return 0, errors.New("is a directory")
  636. }
  637. if offs >= f.size {
  638. return 0, io.EOF
  639. }
  640. if f.content != nil {
  641. n := copy(p, f.content[int(offs):])
  642. f.offset = offs + int64(n)
  643. return n, nil
  644. }
  645. // Lazily calculate our main seed, a simple 64 bit FNV hash our file
  646. // name.
  647. if f.seed == 0 {
  648. hf := fnv.New64()
  649. hf.Write([]byte(f.name))
  650. f.seed = int64(hf.Sum64())
  651. }
  652. // Check whether the read is a continuation of an RNG we already have or
  653. // we need to set up a new one.
  654. seedNo := offs >> randomBlockShift
  655. minOffs := seedNo << randomBlockShift
  656. nextBlockOffs := (seedNo + 1) << randomBlockShift
  657. if f.rng == nil || f.offset != offs || seedNo != f.seedOffs {
  658. // This is not a straight read continuing from a previous one
  659. f.rng = rand.New(rand.NewSource(f.seed + seedNo))
  660. // If the read is not at the start of the block, discard data
  661. // accordingly.
  662. diff := offs - minOffs
  663. if diff > 0 {
  664. lr := io.LimitReader(f.rng, diff)
  665. io.Copy(ioutil.Discard, lr)
  666. }
  667. f.offset = offs
  668. f.seedOffs = seedNo
  669. }
  670. size := len(p)
  671. // Don't read past the end of the file
  672. if offs+int64(size) > f.size {
  673. size = int(f.size - offs)
  674. }
  675. // Don't read across the block boundary
  676. if offs+int64(size) > nextBlockOffs {
  677. size = int(nextBlockOffs - offs)
  678. }
  679. f.offset += int64(size)
  680. return f.rng.Read(p[:size])
  681. }
  682. func (f *fakeFile) Seek(offset int64, whence int) (int64, error) {
  683. f.mut.Lock()
  684. defer f.mut.Unlock()
  685. if f.entryType == fakeEntryTypeDir {
  686. return 0, errors.New("is a directory")
  687. }
  688. f.rng = nil
  689. switch whence {
  690. case io.SeekCurrent:
  691. f.offset += offset
  692. case io.SeekEnd:
  693. f.offset = f.size - offset
  694. case io.SeekStart:
  695. f.offset = offset
  696. }
  697. if f.offset < 0 {
  698. f.offset = 0
  699. return f.offset, errors.New("seek before start")
  700. }
  701. if f.offset > f.size {
  702. f.offset = f.size
  703. return f.offset, io.EOF
  704. }
  705. return f.offset, nil
  706. }
  707. func (f *fakeFile) Write(p []byte) (int, error) {
  708. f.mut.Lock()
  709. offs := f.offset
  710. f.mut.Unlock()
  711. return f.WriteAt(p, offs)
  712. }
  713. func (f *fakeFile) WriteAt(p []byte, off int64) (int, error) {
  714. f.mut.Lock()
  715. defer f.mut.Unlock()
  716. if f.entryType == fakeEntryTypeDir {
  717. return 0, errors.New("is a directory")
  718. }
  719. if f.content != nil {
  720. if len(f.content) < int(off)+len(p) {
  721. newc := make([]byte, int(off)+len(p))
  722. copy(newc, f.content)
  723. f.content = newc
  724. }
  725. copy(f.content[int(off):], p)
  726. }
  727. f.rng = nil
  728. f.offset = off + int64(len(p))
  729. if f.offset > f.size {
  730. f.size = f.offset
  731. }
  732. return len(p), nil
  733. }
  734. func (f *fakeFile) Name() string {
  735. if f.presentedName != "" {
  736. return f.presentedName
  737. }
  738. return f.name
  739. }
  740. func (f *fakeFile) Truncate(size int64) error {
  741. f.mut.Lock()
  742. defer f.mut.Unlock()
  743. if f.content != nil {
  744. f.content = f.content[:int(size)]
  745. }
  746. f.rng = nil
  747. f.size = size
  748. if f.offset > size {
  749. f.offset = size
  750. }
  751. return nil
  752. }
  753. func (f *fakeFile) Stat() (FileInfo, error) {
  754. info := &fakeFileInfo{*f.fakeEntry}
  755. if f.presentedName != "" {
  756. info.name = f.presentedName
  757. }
  758. return info, nil
  759. }
  760. func (f *fakeFile) Sync() error {
  761. return nil
  762. }
  763. // fakeFileInfo is the stat result.
  764. type fakeFileInfo struct {
  765. fakeEntry // intentionally a copy of the struct
  766. }
  767. func (f *fakeFileInfo) Name() string {
  768. return f.name
  769. }
  770. func (f *fakeFileInfo) Mode() FileMode {
  771. return f.mode
  772. }
  773. func (f *fakeFileInfo) Size() int64 {
  774. return f.size
  775. }
  776. func (f *fakeFileInfo) ModTime() time.Time {
  777. return f.mtime
  778. }
  779. func (f *fakeFileInfo) IsDir() bool {
  780. return f.entryType == fakeEntryTypeDir
  781. }
  782. func (f *fakeFileInfo) IsRegular() bool {
  783. return f.entryType == fakeEntryTypeFile
  784. }
  785. func (f *fakeFileInfo) IsSymlink() bool {
  786. return f.entryType == fakeEntryTypeSymlink
  787. }
  788. func (f *fakeFileInfo) Owner() int {
  789. return f.uid
  790. }
  791. func (f *fakeFileInfo) Group() int {
  792. return f.gid
  793. }