ceremonyclient/pebble/vfs/errorfs/dsl.go
Cassandra Heart 2e2a1e4789
v1.2.0 (#31)
2024-01-03 01:31:42 -06:00

301 lines
9.3 KiB
Go

// Copyright 2023 The LevelDB-Go and Pebble Authors. All rights reserved. Use
// of this source code is governed by a BSD-style license that can be found in
// the LICENSE file.
package errorfs
import (
"encoding/binary"
"fmt"
"go/token"
"hash/maphash"
"math/rand"
"path/filepath"
"strconv"
"sync"
"github.com/cockroachdb/errors"
"github.com/cockroachdb/pebble/internal/dsl"
)
// Predicate encodes conditional logic that determines whether to inject an
// error.
type Predicate = dsl.Predicate[Op]
// PathMatch returns a predicate that returns true if an operation's file path
// matches the provided pattern according to filepath.Match.
func PathMatch(pattern string) Predicate {
return &pathMatch{pattern: pattern}
}
type pathMatch struct {
pattern string
}
func (pm *pathMatch) String() string {
return fmt.Sprintf("(PathMatch %q)", pm.pattern)
}
func (pm *pathMatch) Evaluate(op Op) bool {
matched, err := filepath.Match(pm.pattern, op.Path)
if err != nil {
// Only possible error is ErrBadPattern, indicating an issue with
// the test itself.
panic(err)
}
return matched
}
var (
// Reads is a predicate that returns true iff an operation is a read
// operation.
Reads Predicate = opKindPred{kind: OpIsRead}
// Writes is a predicate that returns true iff an operation is a write
// operation.
Writes Predicate = opKindPred{kind: OpIsWrite}
)
type opFileReadAt struct {
// offset configures the predicate to evaluate to true only if the
// operation's offset exactly matches offset.
offset int64
}
func (o *opFileReadAt) String() string {
return fmt.Sprintf("(FileReadAt %d)", o.offset)
}
func (o *opFileReadAt) Evaluate(op Op) bool {
return op.Kind == OpFileReadAt && o.offset == op.Offset
}
type opKindPred struct {
kind OpReadWrite
}
func (p opKindPred) String() string { return p.kind.String() }
func (p opKindPred) Evaluate(op Op) bool { return p.kind == op.Kind.ReadOrWrite() }
// Randomly constructs a new predicate that pseudorandomly evaluates to true
// with probability p using randomness determinstically derived from seed.
//
// The predicate is deterministic with respect to file paths: its behavior for a
// particular file is deterministic regardless of intervening evaluations for
// operations on other files. This can be used to ensure determinism despite
// nondeterministic concurrency if the concurrency is constrained to separate
// files.
func Randomly(p float64, seed int64) Predicate {
rs := &randomSeed{p: p, rootSeed: seed}
rs.mu.perFilePrng = make(map[string]*rand.Rand)
return rs
}
type randomSeed struct {
// p defines the probability of an error being injected.
p float64
rootSeed int64
mu struct {
sync.Mutex
h maphash.Hash
perFilePrng map[string]*rand.Rand
}
}
func (rs *randomSeed) String() string {
if rs.rootSeed == 0 {
return fmt.Sprintf("(Randomly %.2f)", rs.p)
}
return fmt.Sprintf("(Randomly %.2f %d)", rs.p, rs.rootSeed)
}
func (rs *randomSeed) Evaluate(op Op) bool {
rs.mu.Lock()
defer rs.mu.Unlock()
prng, ok := rs.mu.perFilePrng[op.Path]
if !ok {
// This is the first time an operation has been performed on the file at
// this path. Initialize the per-file prng by computing a deterministic
// hash of the path.
rs.mu.h.Reset()
var b [8]byte
binary.LittleEndian.PutUint64(b[:], uint64(rs.rootSeed))
if _, err := rs.mu.h.Write(b[:]); err != nil {
panic(err)
}
if _, err := rs.mu.h.WriteString(op.Path); err != nil {
panic(err)
}
seed := rs.mu.h.Sum64()
prng = rand.New(rand.NewSource(int64(seed)))
rs.mu.perFilePrng[op.Path] = prng
}
return prng.Float64() < rs.p
}
// ParseDSL parses the provided string using the default DSL parser.
func ParseDSL(s string) (Injector, error) {
return defaultParser.Parse(s)
}
var defaultParser = NewParser()
// NewParser constructs a new parser for an encoding of a lisp-like DSL
// describing error injectors.
//
// Errors:
// - ErrInjected is the only error currently supported by the DSL.
//
// Injectors:
// - <ERROR>: An error by itself is an injector that injects an error every
// time.
// - (<ERROR> <PREDICATE>) is an injector that injects an error only when
// the operation satisfies the predicate.
//
// Predicates:
// - Reads is a constant predicate that evalutes to true iff the operation is a
// read operation (eg, Open, Read, ReadAt, Stat)
// - Writes is a constant predicate that evaluates to true iff the operation is
// a write operation (eg, Create, Rename, Write, WriteAt, etc).
// - (PathMatch <STRING>) is a predicate that evalutes to true iff the
// operation's file path matches the provided shell pattern.
// - (OnIndex <INTEGER>) is a predicate that evaluates to true only on the n-th
// invocation.
// - (And <PREDICATE> [PREDICATE]...) is a predicate that evaluates to true
// iff all the provided predicates evaluate to true. And short circuits on
// the first predicate to evaluate to false.
// - (Or <PREDICATE> [PREDICATE]...) is a predicate that evaluates to true iff
// at least one of the provided predicates evaluates to true. Or short
// circuits on the first predicate to evaluate to true.
// - (Not <PREDICATE>) is a predicate that evaluates to true iff its provided
// predicates evaluates to false.
// - (Randomly <FLOAT> [INTEGER]) is a predicate that pseudorandomly evaluates
// to true. The probability of evaluating to true is determined by the
// required float argument (must be ≤1). The optional second parameter is a
// pseudorandom seed, for adjusting the deterministic randomness.
// - Operation-specific:
// (OpFileReadAt <INTEGER>) is a predicate that evaluates to true iff
// an operation is a file ReadAt call with an offset that's exactly equal.
//
// Example: (ErrInjected (And (PathMatch "*.sst") (OnIndex 5))) is a rule set
// that will inject an error on the 5-th I/O operation involving an sstable.
func NewParser() *Parser {
p := &Parser{
predicates: dsl.NewPredicateParser[Op](),
injectors: dsl.NewParser[Injector](),
}
p.predicates.DefineConstant("Reads", func() dsl.Predicate[Op] { return Reads })
p.predicates.DefineConstant("Writes", func() dsl.Predicate[Op] { return Writes })
p.predicates.DefineFunc("PathMatch",
func(p *dsl.Parser[dsl.Predicate[Op]], s *dsl.Scanner) dsl.Predicate[Op] {
pattern := s.ConsumeString()
s.Consume(token.RPAREN)
return PathMatch(pattern)
})
p.predicates.DefineFunc("OpFileReadAt",
func(p *dsl.Parser[dsl.Predicate[Op]], s *dsl.Scanner) dsl.Predicate[Op] {
return parseFileReadAtOp(s)
})
p.predicates.DefineFunc("Randomly",
func(p *dsl.Parser[dsl.Predicate[Op]], s *dsl.Scanner) dsl.Predicate[Op] {
return parseRandomly(s)
})
p.AddError(ErrInjected)
return p
}
// A Parser parses the error-injecting DSL. It may be extended to include
// additional errors through AddError.
type Parser struct {
predicates *dsl.Parser[dsl.Predicate[Op]]
injectors *dsl.Parser[Injector]
}
// Parse parses the error injection DSL, returning the parsed injector.
func (p *Parser) Parse(s string) (Injector, error) {
return p.injectors.Parse(s)
}
// AddError defines a new error that may be used within the DSL parsed by
// Parse and will inject the provided error.
func (p *Parser) AddError(le LabelledError) {
// Define the error both as a constant that unconditionally injects the
// error, and as a function that injects the error only if the provided
// predicate evaluates to true.
p.injectors.DefineConstant(le.Label, func() Injector { return le })
p.injectors.DefineFunc(le.Label,
func(_ *dsl.Parser[Injector], s *dsl.Scanner) Injector {
pred := p.predicates.ParseFromPos(s, s.Scan())
s.Consume(token.RPAREN)
return le.If(pred)
})
}
// LabelledError is an error that also implements Injector, unconditionally
// injecting itself. It implements String() by returning its label. It
// implements Error() by returning its underlying error.
type LabelledError struct {
error
Label string
predicate Predicate
}
// String implements fmt.Stringer.
func (le LabelledError) String() string {
if le.predicate == nil {
return le.Label
}
return fmt.Sprintf("(%s %s)", le.Label, le.predicate.String())
}
// MaybeError implements Injector.
func (le LabelledError) MaybeError(op Op) error {
if le.predicate == nil || le.predicate.Evaluate(op) {
return le
}
return nil
}
// If returns an Injector that returns the receiver error if the provided
// predicate evalutes to true.
func (le LabelledError) If(p Predicate) Injector {
le.predicate = p
return le
}
func parseFileReadAtOp(s *dsl.Scanner) *opFileReadAt {
lit := s.Consume(token.INT).Lit
off, err := strconv.ParseInt(lit, 10, 64)
if err != nil {
panic(err)
}
s.Consume(token.RPAREN)
return &opFileReadAt{offset: off}
}
func parseRandomly(s *dsl.Scanner) Predicate {
lit := s.Consume(token.FLOAT).Lit
p, err := strconv.ParseFloat(lit, 64)
if err != nil {
panic(err)
} else if p > 1.0 {
// NB: It's not possible for p to be less than zero because we don't
// try to parse the '-' token.
panic(errors.Newf("errorfs: Randomly proability p must be within p ≤ 1.0"))
}
var seed int64
tok := s.Scan()
switch tok.Kind {
case token.RPAREN:
case token.INT:
seed, err = strconv.ParseInt(tok.Lit, 10, 64)
if err != nil {
panic(err)
}
s.Consume(token.RPAREN)
default:
panic(errors.Errorf("errorfs: unexpected token %s; expected RPAREN | FLOAT", tok.String()))
}
return Randomly(p, seed)
}