1// SPDX-License-Identifier: MIT
2
3// Package faultfs is an in-memory fsys.FS for tests. It models a page cache in
4// front of durable storage and can inject failures in writes, syncs and
5// directory and file operations, delay syncs, count syncs and simulate a power
6// loss.
7//
8// Durability model: file bytes become durable on Sync or SyncAll; directory
9// operations (create, rename, remove, mkdir) become durable on SyncDir of the
10// directory that contains them. PowerLoss discards everything that is not.
11//
12// All methods are safe for concurrent use.
13package faultfs
14
15import (
16 "errors"
17 "io"
18 "io/fs"
19 "maps"
20 "math/rand/v2"
21 "os"
22 "path/filepath"
23 "slices"
24 "sort"
25 "sync"
26 "time"
27
28 "bnema.dev/ermite-kv/internal/fsys"
29)
30
31// ErrPowerLoss is returned by handles that were open when PowerLoss was called.
32var ErrPowerLoss = errors.New("faultfs: handle invalidated by power loss")
33
34// ErrInjected is the default error of injected failures.
35var ErrInjected = errors.New("faultfs: injected failure")
36
37const defaultPageSize = 4096
38
39// OpKind identifies a file-system operation other than Write and Sync, whose
40// failures are injected with FailOp.
41type OpKind uint8
42
43// Operations that FailOp can fail.
44const (
45 OpSyncDir OpKind = iota
46 OpRename
47 OpRemove
48 OpTruncate
49 OpOpenFile
50 numOps
51)
52
53func (k OpKind) String() string {
54 switch k {
55 case OpSyncDir:
56 return "SyncDir"
57 case OpRename:
58 return "Rename"
59 case OpRemove:
60 return "Remove"
61 case OpTruncate:
62 return "Truncate"
63 case OpOpenFile:
64 return "OpenFile"
65 }
66 return "unknown"
67}
68
69// opCall designates the n-th call of an operation kind.
70type opCall struct {
71 kind OpKind
72 n int
73}
74
75type node struct {
76 data []byte // current content (page cache)
77 durable []byte // content as of the last successful sync
78 truncated bool // data was truncated since the last sync
79}
80
81type nsOp struct {
82 kind byte // 'c' create, 'r' rename, 'd' remove, 'm' mkdir
83 path string
84 oldPath string // rename source
85 n *node // created, removed or renamed node
86 prev *node // node replaced by a rename
87 dirs map[string]bool
88}
89
90// FS is an in-memory file system with fault injection.
91type FS struct {
92 mu sync.Mutex
93 files map[string]*node
94 dirs map[string]bool
95 locks map[string]bool
96 ns []*nsOp // directory operations not yet made durable
97 epoch uint64 // incremented by PowerLoss
98
99 writes, syncs, syncAlls int
100 failWrite map[int]writeFault // by absolute write number
101 failSync map[int]error // by absolute sync number (Sync+SyncAll)
102 syncDelay time.Duration
103 nSyncCalls int
104 dropOnSyncFail bool
105
106 opCalls [numOps]int // calls so far, by kind
107 failOps map[opCall]error // by kind and absolute call number
108}
109
110type writeFault struct {
111 keep int // bytes stored before failing; <0 means a plain failure
112 err error
113}
114
115var _ fsys.FS = (*FS)(nil)
116
117// New returns an empty file system.
118func New() *FS {
119 return &FS{
120 files: map[string]*node{},
121 dirs: map[string]bool{"/": true, ".": true},
122 locks: map[string]bool{},
123 failWrite: map[int]writeFault{},
124 failSync: map[int]error{},
125 failOps: map[opCall]error{},
126 }
127}
128
129// FailWrite makes the n-th Write call from now (1 = the next one) fail with
130// err (ErrInjected if nil) without storing any byte.
131func (f *FS) FailWrite(n int, err error) {
132 if err == nil {
133 err = ErrInjected
134 }
135 f.mu.Lock()
136 defer f.mu.Unlock()
137 f.failWrite[f.writes+n] = writeFault{keep: -1, err: err}
138}
139
140// ShortWrite makes the n-th Write call from now store only its first keep
141// bytes and return (keep, io.ErrShortWrite). A call shorter than keep+1 bytes
142// is unaffected.
143func (f *FS) ShortWrite(n, keep int) {
144 f.mu.Lock()
145 defer f.mu.Unlock()
146 f.failWrite[f.writes+n] = writeFault{keep: keep, err: io.ErrShortWrite}
147}
148
149// FailSync makes the n-th Sync or SyncAll call from now (1 = the next one)
150// fail with err (ErrInjected if nil). Nothing becomes durable.
151func (f *FS) FailSync(n int, err error) {
152 if err == nil {
153 err = ErrInjected
154 }
155 f.mu.Lock()
156 defer f.mu.Unlock()
157 f.failSync[f.nSyncCalls+n] = err
158}
159
160// FailOp makes the n-th call from now (1 = the next one) of the operation
161// kind fail with err (ErrInjected if nil). A failed call has no effect. Every
162// call counts, whether or not it would have failed anyway.
163func (f *FS) FailOp(kind OpKind, n int, err error) {
164 if err == nil {
165 err = ErrInjected
166 }
167 f.mu.Lock()
168 defer f.mu.Unlock()
169 f.failOps[opCall{kind, f.opCalls[kind] + n}] = err
170}
171
172// OpCalls returns the number of calls of the operation kind so far.
173func (f *FS) OpCalls(kind OpKind) int {
174 f.mu.Lock()
175 defer f.mu.Unlock()
176 return f.opCalls[kind]
177}
178
179// injected counts a call of kind and returns the error to fail it with, if
180// any. It must be called with f.mu held.
181func (f *FS) injected(kind OpKind) error {
182 f.opCalls[kind]++
183 c := opCall{kind, f.opCalls[kind]}
184 err, ok := f.failOps[c]
185 if ok {
186 delete(f.failOps, c)
187 }
188 return err
189}
190
191// DropOnSyncFailure selects what a failed Sync or SyncAll does to the data
192// that was not yet durable. By default it stays in the page cache and a later
193// successful sync makes it durable. When enabled, it is dropped, as on
194// systems that mark the pages clean after a write-back error ("fsyncgate"):
195// the file reverts to its last durable content, and the data is gone even if
196// a later sync succeeds.
197func (f *FS) DropOnSyncFailure(drop bool) {
198 f.mu.Lock()
199 f.dropOnSyncFail = drop
200 f.mu.Unlock()
201}
202
203// SetSyncDelay makes every Sync and SyncAll block for d before taking effect.
204func (f *FS) SetSyncDelay(d time.Duration) {
205 f.mu.Lock()
206 f.syncDelay = d
207 f.mu.Unlock()
208}
209
210// Writes returns the number of Write calls so far.
211func (f *FS) Writes() int { f.mu.Lock(); defer f.mu.Unlock(); return f.writes }
212
213// Syncs returns the number of Sync (fdatasync) calls so far.
214func (f *FS) Syncs() int { f.mu.Lock(); defer f.mu.Unlock(); return f.syncs }
215
216// SyncAlls returns the number of SyncAll (fsync) calls so far.
217func (f *FS) SyncAlls() int { f.mu.Lock(); defer f.mu.Unlock(); return f.syncAlls }
218
219// PowerLossOptions tunes PowerLoss.
220type PowerLossOptions struct {
221 // KeepPages keeps a random subset of the unsynced pages of each file.
222 // Dropped pages inside the kept range read as zeros.
223 KeepPages bool
224 // ZeroFill keeps the unsynced size extension: the file keeps its length
225 // and every unsynced page that is not kept reads as zeros.
226 ZeroFill bool
227 // PageSize is the page granularity; 0 means 4096.
228 PageSize int
229 // Rand drives KeepPages; nil uses a fixed seed.
230 Rand *rand.Rand
231}
232
233// PowerLoss simulates a power failure: file bytes written after their last
234// sync are dropped (see PowerLossOptions) and directory operations done after
235// the last SyncDir of their directory are undone. Open handles become invalid
236// and locks are released.
237func (f *FS) PowerLoss(o PowerLossOptions) {
238 f.mu.Lock()
239 defer f.mu.Unlock()
240 if o.PageSize <= 0 {
241 o.PageSize = defaultPageSize
242 }
243 if o.Rand == nil {
244 o.Rand = rand.New(rand.NewPCG(1, 2))
245 }
246 for i := len(f.ns) - 1; i >= 0; i-- {
247 f.undo(f.ns[i])
248 }
249 f.ns = nil
250 // Drop entries whose parent directory did not survive.
251 for again := true; again; {
252 again = false
253 for d := range f.dirs {
254 if !f.dirs[filepath.Dir(d)] {
255 delete(f.dirs, d)
256 again = true
257 }
258 }
259 }
260 for p := range f.files {
261 if !f.dirs[filepath.Dir(p)] {
262 delete(f.files, p)
263 }
264 }
265 // Crash files in path order so a seeded Rand gives reproducible results.
266 seen := map[*node]bool{}
267 for _, p := range slices.Sorted(maps.Keys(f.files)) {
268 n := f.files[p]
269 if !seen[n] {
270 seen[n] = true
271 n.crash(o)
272 }
273 }
274 f.locks = map[string]bool{}
275 f.epoch++
276}
277
278func (f *FS) undo(op *nsOp) {
279 switch op.kind {
280 case 'c':
281 delete(f.files, op.path)
282 case 'm':
283 delete(f.dirs, op.path)
284 case 'd':
285 f.files[op.path] = op.n
286 case 'r':
287 f.files[op.oldPath] = op.n
288 if op.prev != nil {
289 f.files[op.path] = op.prev
290 } else {
291 delete(f.files, op.path)
292 }
293 }
294}
295
296func (n *node) crash(o PowerLossOptions) {
297 defer func() {
298 n.durable = append([]byte(nil), n.data...)
299 n.truncated = false
300 }()
301 if n.truncated || len(n.data) <= len(n.durable) {
302 n.data = append([]byte(nil), n.durable...)
303 return
304 }
305 off, end := len(n.durable), len(n.data)
306 out := append(make([]byte, 0, end), n.durable...)
307 out = append(out, make([]byte, end-off)...) // zero-filled extension
308 kept := off
309 for p := off / o.PageSize; p*o.PageSize < end; p++ {
310 lo, hi := max(p*o.PageSize, off), min((p+1)*o.PageSize, end)
311 if o.KeepPages && o.Rand.IntN(2) == 0 {
312 copy(out[lo:hi], n.data[lo:hi])
313 kept = hi
314 }
315 }
316 if o.ZeroFill {
317 kept = end
318 }
319 n.data = out[:kept]
320}
321
322// WriteFile creates or replaces a durable file (and its parent directories)
323// without going through fault injection. It is meant for test setup.
324func (f *FS) WriteFile(name string, data []byte) {
325 name = filepath.Clean(name)
326 f.mu.Lock()
327 defer f.mu.Unlock()
328 f.mkdirAll(filepath.Dir(name), true)
329 f.files[name] = &node{
330 data: append([]byte(nil), data...),
331 durable: append([]byte(nil), data...),
332 }
333}
334
335// ReadFile returns a copy of the current content of name.
336func (f *FS) ReadFile(name string) ([]byte, bool) {
337 f.mu.Lock()
338 defer f.mu.Unlock()
339 n, ok := f.files[filepath.Clean(name)]
340 if !ok {
341 return nil, false
342 }
343 return append([]byte(nil), n.data...), true
344}
345
346// DurableFile returns a copy of the content of name that would survive a
347// power loss right now, ignoring directory entries.
348func (f *FS) DurableFile(name string) ([]byte, bool) {
349 f.mu.Lock()
350 defer f.mu.Unlock()
351 n, ok := f.files[filepath.Clean(name)]
352 if !ok {
353 return nil, false
354 }
355 return append([]byte(nil), n.durable...), true
356}
357
358func (f *FS) journal(op *nsOp, dirs ...string) {
359 op.dirs = map[string]bool{}
360 for _, d := range dirs {
361 op.dirs[d] = true
362 }
363 f.ns = append(f.ns, op)
364}
365
366// mkdirAll creates dir and parents; with durable set nothing is journaled.
367func (f *FS) mkdirAll(dir string, durable bool) {
368 for d := dir; !f.dirs[d]; d = filepath.Dir(d) {
369 f.dirs[d] = true
370 if !durable {
371 f.journal(&nsOp{kind: 'm', path: d}, filepath.Dir(d))
372 }
373 }
374}
375
376// OpenFile implements fsys.FS. Supported flags: O_RDONLY, O_WRONLY, O_RDWR,
377// O_CREATE, O_EXCL, O_TRUNC. Writing handles append.
378func (f *FS) OpenFile(name string, flag int, perm os.FileMode) (fsys.File, error) {
379 name = filepath.Clean(name)
380 f.mu.Lock()
381 defer f.mu.Unlock()
382 if err := f.injected(OpOpenFile); err != nil {
383 return nil, &fs.PathError{Op: "open", Path: name, Err: err}
384 }
385 n, ok := f.files[name]
386 switch {
387 case f.dirs[name]:
388 return nil, &fs.PathError{Op: "open", Path: name, Err: errors.New("is a directory")}
389 case ok && flag&os.O_CREATE != 0 && flag&os.O_EXCL != 0:
390 return nil, &fs.PathError{Op: "open", Path: name, Err: fs.ErrExist}
391 case !ok && flag&os.O_CREATE == 0:
392 return nil, &fs.PathError{Op: "open", Path: name, Err: fs.ErrNotExist}
393 case !ok:
394 if !f.dirs[filepath.Dir(name)] {
395 return nil, &fs.PathError{Op: "open", Path: name, Err: fs.ErrNotExist}
396 }
397 n = &node{}
398 f.files[name] = n
399 f.journal(&nsOp{kind: 'c', path: name, n: n}, filepath.Dir(name))
400 }
401 acc := flag & (os.O_WRONLY | os.O_RDWR)
402 if flag&os.O_TRUNC != 0 && acc != 0 {
403 f.truncate(n, 0)
404 }
405 return &file{fs: f, n: n, epoch: f.epoch, write: acc != 0, read: acc != os.O_WRONLY}, nil
406}
407
408// Rename implements fsys.FS.
409func (f *FS) Rename(oldpath, newpath string) error {
410 oldpath, newpath = filepath.Clean(oldpath), filepath.Clean(newpath)
411 f.mu.Lock()
412 defer f.mu.Unlock()
413 if err := f.injected(OpRename); err != nil {
414 return &os.LinkError{Op: "rename", Old: oldpath, New: newpath, Err: err}
415 }
416 n, ok := f.files[oldpath]
417 if !ok {
418 return &os.LinkError{Op: "rename", Old: oldpath, New: newpath, Err: fs.ErrNotExist}
419 }
420 if !f.dirs[filepath.Dir(newpath)] {
421 return &os.LinkError{Op: "rename", Old: oldpath, New: newpath, Err: fs.ErrNotExist}
422 }
423 if oldpath == newpath {
424 return nil
425 }
426 prev := f.files[newpath]
427 delete(f.files, oldpath)
428 f.files[newpath] = n
429 f.journal(&nsOp{kind: 'r', path: newpath, oldPath: oldpath, n: n, prev: prev},
430 filepath.Dir(oldpath), filepath.Dir(newpath))
431 return nil
432}
433
434// Remove implements fsys.FS. It only removes files.
435func (f *FS) Remove(name string) error {
436 name = filepath.Clean(name)
437 f.mu.Lock()
438 defer f.mu.Unlock()
439 if err := f.injected(OpRemove); err != nil {
440 return &fs.PathError{Op: "remove", Path: name, Err: err}
441 }
442 n, ok := f.files[name]
443 if !ok {
444 return &fs.PathError{Op: "remove", Path: name, Err: fs.ErrNotExist}
445 }
446 delete(f.files, name)
447 f.journal(&nsOp{kind: 'd', path: name, n: n}, filepath.Dir(name))
448 return nil
449}
450
451// ReadDir implements fsys.FS.
452func (f *FS) ReadDir(dir string) ([]string, error) {
453 dir = filepath.Clean(dir)
454 f.mu.Lock()
455 defer f.mu.Unlock()
456 if !f.dirs[dir] {
457 return nil, &fs.PathError{Op: "readdir", Path: dir, Err: fs.ErrNotExist}
458 }
459 var names []string
460 for p := range f.files {
461 if filepath.Dir(p) == dir {
462 names = append(names, filepath.Base(p))
463 }
464 }
465 for p := range f.dirs {
466 if p != dir && filepath.Dir(p) == dir {
467 names = append(names, filepath.Base(p))
468 }
469 }
470 sort.Strings(names)
471 return names, nil
472}
473
474// MkdirAll implements fsys.FS.
475func (f *FS) MkdirAll(dir string, _ os.FileMode) error {
476 dir = filepath.Clean(dir)
477 f.mu.Lock()
478 defer f.mu.Unlock()
479 if _, ok := f.files[dir]; ok {
480 return &fs.PathError{Op: "mkdir", Path: dir, Err: errors.New("not a directory")}
481 }
482 f.mkdirAll(dir, false)
483 return nil
484}
485
486// SyncDir implements fsys.FS.
487func (f *FS) SyncDir(dir string) error {
488 dir = filepath.Clean(dir)
489 f.mu.Lock()
490 defer f.mu.Unlock()
491 if err := f.injected(OpSyncDir); err != nil {
492 return &fs.PathError{Op: "sync", Path: dir, Err: err}
493 }
494 if !f.dirs[dir] {
495 return &fs.PathError{Op: "sync", Path: dir, Err: fs.ErrNotExist}
496 }
497 keep := f.ns[:0]
498 for _, op := range f.ns {
499 delete(op.dirs, dir)
500 if len(op.dirs) > 0 {
501 keep = append(keep, op)
502 }
503 }
504 clear(f.ns[len(keep):])
505 f.ns = keep
506 return nil
507}
508
509// Lock implements fsys.FS. The lock is exclusive per path within this FS.
510func (f *FS) Lock(path string) (io.Closer, error) {
511 path = filepath.Clean(path)
512 f.mu.Lock()
513 defer f.mu.Unlock()
514 if f.locks[path] {
515 return nil, fsys.ErrLocked
516 }
517 if _, ok := f.files[path]; !ok {
518 if !f.dirs[filepath.Dir(path)] {
519 return nil, &fs.PathError{Op: "open", Path: path, Err: fs.ErrNotExist}
520 }
521 n := &node{}
522 f.files[path] = n
523 f.journal(&nsOp{kind: 'c', path: path, n: n}, filepath.Dir(path))
524 }
525 f.locks[path] = true
526 return &lock{fs: f, path: path, epoch: f.epoch}, nil
527}
528
529type lock struct {
530 fs *FS
531 path string
532 epoch uint64
533 once sync.Once
534}
535
536func (l *lock) Close() error {
537 l.once.Do(func() {
538 l.fs.mu.Lock()
539 defer l.fs.mu.Unlock()
540 if l.fs.epoch == l.epoch {
541 delete(l.fs.locks, l.path)
542 }
543 })
544 return nil
545}
546
547func (f *FS) truncate(n *node, size int64) {
548 if size < int64(len(n.data)) {
549 n.data = n.data[:size]
550 n.truncated = true
551 } else {
552 n.data = append(n.data, make([]byte, size-int64(len(n.data)))...)
553 }
554}
555
556type file struct {
557 fs *FS
558 n *node
559 epoch uint64
560 read, write bool
561 closed bool
562}
563
564// check must be called with fs.mu held.
565func (h *file) check() error {
566 switch {
567 case h.closed:
568 return os.ErrClosed
569 case h.epoch != h.fs.epoch:
570 return ErrPowerLoss
571 }
572 return nil
573}
574
575func (h *file) Write(p []byte) (int, error) {
576 f := h.fs
577 f.mu.Lock()
578 defer f.mu.Unlock()
579 if err := h.check(); err != nil {
580 return 0, err
581 }
582 if !h.write {
583 return 0, &fs.PathError{Op: "write", Err: fs.ErrPermission}
584 }
585 f.writes++
586 if wf, ok := f.failWrite[f.writes]; ok {
587 delete(f.failWrite, f.writes)
588 switch {
589 case wf.keep < 0:
590 return 0, wf.err
591 case wf.keep < len(p):
592 h.n.data = append(h.n.data, p[:wf.keep]...)
593 return wf.keep, wf.err
594 }
595 }
596 h.n.data = append(h.n.data, p...)
597 return len(p), nil
598}
599
600func (h *file) ReadAt(p []byte, off int64) (int, error) {
601 h.fs.mu.Lock()
602 defer h.fs.mu.Unlock()
603 if err := h.check(); err != nil {
604 return 0, err
605 }
606 if !h.read {
607 return 0, &fs.PathError{Op: "read", Err: fs.ErrPermission}
608 }
609 if off < 0 {
610 return 0, errors.New("faultfs: negative offset")
611 }
612 if off >= int64(len(h.n.data)) {
613 return 0, io.EOF
614 }
615 n := copy(p, h.n.data[off:])
616 if n < len(p) {
617 return n, io.EOF
618 }
619 return n, nil
620}
621
622func (h *file) Sync() error { return h.sync(false) }
623func (h *file) SyncAll() error { return h.sync(true) }
624
625func (h *file) sync(all bool) error {
626 f := h.fs
627 f.mu.Lock()
628 if err := h.check(); err != nil {
629 f.mu.Unlock()
630 return err
631 }
632 f.nSyncCalls++
633 if all {
634 f.syncAlls++
635 } else {
636 f.syncs++
637 }
638 if err, ok := f.failSync[f.nSyncCalls]; ok {
639 delete(f.failSync, f.nSyncCalls)
640 if f.dropOnSyncFail {
641 h.n.data = append([]byte(nil), h.n.durable...)
642 h.n.truncated = false
643 }
644 f.mu.Unlock()
645 return err
646 }
647 d := f.syncDelay
648 f.mu.Unlock()
649 if d > 0 {
650 time.Sleep(d)
651 }
652 f.mu.Lock()
653 defer f.mu.Unlock()
654 if err := h.check(); err != nil {
655 return err
656 }
657 n := h.n
658 if !n.truncated && len(n.data) >= len(n.durable) {
659 n.durable = append(n.durable, n.data[len(n.durable):]...)
660 } else {
661 n.durable = append(n.durable[:0], n.data...)
662 }
663 n.truncated = false
664 return nil
665}
666
667func (h *file) Truncate(size int64) error {
668 h.fs.mu.Lock()
669 defer h.fs.mu.Unlock()
670 if err := h.check(); err != nil {
671 return err
672 }
673 if err := h.fs.injected(OpTruncate); err != nil {
674 return &fs.PathError{Op: "truncate", Err: err}
675 }
676 if !h.write || size < 0 {
677 return &fs.PathError{Op: "truncate", Err: fs.ErrInvalid}
678 }
679 h.fs.truncate(h.n, size)
680 return nil
681}
682
683func (h *file) Size() (int64, error) {
684 h.fs.mu.Lock()
685 defer h.fs.mu.Unlock()
686 if err := h.check(); err != nil {
687 return 0, err
688 }
689 return int64(len(h.n.data)), nil
690}
691
692func (h *file) Close() error {
693 h.fs.mu.Lock()
694 defer h.fs.mu.Unlock()
695 if h.closed {
696 return os.ErrClosed
697 }
698 h.closed = true
699 return nil
700}