Line data Source code
1 : // Copyright 2023 The LevelDB-Go and Pebble Authors. All rights reserved. Use
2 : // of this source code is governed by a BSD-style license that can be found in
3 : // the LICENSE file.
4 :
5 : package errorfs
6 :
7 : import (
8 : "encoding/binary"
9 : "fmt"
10 : "go/token"
11 : "hash/maphash"
12 : "math/rand"
13 : "path/filepath"
14 : "strconv"
15 : "sync"
16 :
17 : "github.com/cockroachdb/errors"
18 : "github.com/cockroachdb/pebble/internal/dsl"
19 : )
20 :
21 : // Predicate encodes conditional logic that determines whether to inject an
22 : // error.
23 : type Predicate = dsl.Predicate[Op]
24 :
25 : // PathMatch returns a predicate that returns true if an operation's file path
26 : // matches the provided pattern according to filepath.Match.
27 0 : func PathMatch(pattern string) Predicate {
28 0 : return &pathMatch{pattern: pattern}
29 0 : }
30 :
31 : type pathMatch struct {
32 : pattern string
33 : }
34 :
35 0 : func (pm *pathMatch) String() string {
36 0 : return fmt.Sprintf("(PathMatch %q)", pm.pattern)
37 0 : }
38 :
39 0 : func (pm *pathMatch) Evaluate(op Op) bool {
40 0 : matched, err := filepath.Match(pm.pattern, op.Path)
41 0 : if err != nil {
42 0 : // Only possible error is ErrBadPattern, indicating an issue with
43 0 : // the test itself.
44 0 : panic(err)
45 : }
46 0 : return matched
47 : }
48 :
49 : var (
50 : // Reads is a predicate that returns true iff an operation is a read
51 : // operation.
52 : Reads Predicate = opKindPred{kind: OpIsRead}
53 : // Writes is a predicate that returns true iff an operation is a write
54 : // operation.
55 : Writes Predicate = opKindPred{kind: OpIsWrite}
56 : )
57 :
58 : type opFileReadAt struct {
59 : // offset configures the predicate to evaluate to true only if the
60 : // operation's offset exactly matches offset.
61 : offset int64
62 : }
63 :
64 0 : func (o *opFileReadAt) String() string {
65 0 : return fmt.Sprintf("(FileReadAt %d)", o.offset)
66 0 : }
67 :
68 0 : func (o *opFileReadAt) Evaluate(op Op) bool {
69 0 : return op.Kind == OpFileReadAt && o.offset == op.Offset
70 0 : }
71 :
72 : type opKindPred struct {
73 : kind OpReadWrite
74 : }
75 :
76 0 : func (p opKindPred) String() string { return p.kind.String() }
77 1 : func (p opKindPred) Evaluate(op Op) bool { return p.kind == op.Kind.ReadOrWrite() }
78 :
79 : // Randomly constructs a new predicate that pseudorandomly evaluates to true
80 : // with probability p using randomness determinstically derived from seed.
81 : //
82 : // The predicate is deterministic with respect to file paths: its behavior for a
83 : // particular file is deterministic regardless of intervening evaluations for
84 : // operations on other files. This can be used to ensure determinism despite
85 : // nondeterministic concurrency if the concurrency is constrained to separate
86 : // files.
87 1 : func Randomly(p float64, seed int64) Predicate {
88 1 : rs := &randomSeed{p: p, rootSeed: seed}
89 1 : rs.mu.perFilePrng = make(map[string]*rand.Rand)
90 1 : return rs
91 1 : }
92 :
93 : type randomSeed struct {
94 : // p defines the probability of an error being injected.
95 : p float64
96 : rootSeed int64
97 : mu struct {
98 : sync.Mutex
99 : h maphash.Hash
100 : perFilePrng map[string]*rand.Rand
101 : }
102 : }
103 :
104 0 : func (rs *randomSeed) String() string {
105 0 : if rs.rootSeed == 0 {
106 0 : return fmt.Sprintf("(Randomly %.2f)", rs.p)
107 0 : }
108 0 : return fmt.Sprintf("(Randomly %.2f %d)", rs.p, rs.rootSeed)
109 : }
110 :
111 1 : func (rs *randomSeed) Evaluate(op Op) bool {
112 1 : rs.mu.Lock()
113 1 : defer rs.mu.Unlock()
114 1 : prng, ok := rs.mu.perFilePrng[op.Path]
115 1 : if !ok {
116 1 : // This is the first time an operation has been performed on the file at
117 1 : // this path. Initialize the per-file prng by computing a deterministic
118 1 : // hash of the path.
119 1 : rs.mu.h.Reset()
120 1 : var b [8]byte
121 1 : binary.LittleEndian.PutUint64(b[:], uint64(rs.rootSeed))
122 1 : if _, err := rs.mu.h.Write(b[:]); err != nil {
123 0 : panic(err)
124 : }
125 1 : if _, err := rs.mu.h.WriteString(op.Path); err != nil {
126 0 : panic(err)
127 : }
128 1 : seed := rs.mu.h.Sum64()
129 1 : prng = rand.New(rand.NewSource(int64(seed)))
130 1 : rs.mu.perFilePrng[op.Path] = prng
131 : }
132 1 : return prng.Float64() < rs.p
133 : }
134 :
135 : // ParseDSL parses the provided string using the default DSL parser.
136 0 : func ParseDSL(s string) (Injector, error) {
137 0 : return defaultParser.Parse(s)
138 0 : }
139 :
140 : var defaultParser = NewParser()
141 :
142 : // NewParser constructs a new parser for an encoding of a lisp-like DSL
143 : // describing error injectors.
144 : //
145 : // Errors:
146 : // - ErrInjected is the only error currently supported by the DSL.
147 : //
148 : // Injectors:
149 : // - <ERROR>: An error by itself is an injector that injects an error every
150 : // time.
151 : // - (<ERROR> <PREDICATE>) is an injector that injects an error only when
152 : // the operation satisfies the predicate.
153 : //
154 : // Predicates:
155 : // - Reads is a constant predicate that evalutes to true iff the operation is a
156 : // read operation (eg, Open, Read, ReadAt, Stat)
157 : // - Writes is a constant predicate that evaluates to true iff the operation is
158 : // a write operation (eg, Create, Rename, Write, WriteAt, etc).
159 : // - (PathMatch <STRING>) is a predicate that evalutes to true iff the
160 : // operation's file path matches the provided shell pattern.
161 : // - (OnIndex <INTEGER>) is a predicate that evaluates to true only on the n-th
162 : // invocation.
163 : // - (And <PREDICATE> [PREDICATE]...) is a predicate that evaluates to true
164 : // iff all the provided predicates evaluate to true. And short circuits on
165 : // the first predicate to evaluate to false.
166 : // - (Or <PREDICATE> [PREDICATE]...) is a predicate that evaluates to true iff
167 : // at least one of the provided predicates evaluates to true. Or short
168 : // circuits on the first predicate to evaluate to true.
169 : // - (Not <PREDICATE>) is a predicate that evaluates to true iff its provided
170 : // predicates evaluates to false.
171 : // - (Randomly <FLOAT> [INTEGER]) is a predicate that pseudorandomly evaluates
172 : // to true. The probability of evaluating to true is determined by the
173 : // required float argument (must be ≤1). The optional second parameter is a
174 : // pseudorandom seed, for adjusting the deterministic randomness.
175 : // - Operation-specific:
176 : // (OpFileReadAt <INTEGER>) is a predicate that evaluates to true iff
177 : // an operation is a file ReadAt call with an offset that's exactly equal.
178 : //
179 : // Example: (ErrInjected (And (PathMatch "*.sst") (OnIndex 5))) is a rule set
180 : // that will inject an error on the 5-th I/O operation involving an sstable.
181 1 : func NewParser() *Parser {
182 1 : p := &Parser{
183 1 : predicates: dsl.NewPredicateParser[Op](),
184 1 : injectors: dsl.NewParser[Injector](),
185 1 : }
186 1 : p.predicates.DefineConstant("Reads", func() dsl.Predicate[Op] { return Reads })
187 1 : p.predicates.DefineConstant("Writes", func() dsl.Predicate[Op] { return Writes })
188 1 : p.predicates.DefineFunc("PathMatch",
189 1 : func(p *dsl.Parser[dsl.Predicate[Op]], s *dsl.Scanner) dsl.Predicate[Op] {
190 0 : pattern := s.ConsumeString()
191 0 : s.Consume(token.RPAREN)
192 0 : return PathMatch(pattern)
193 0 : })
194 1 : p.predicates.DefineFunc("OpFileReadAt",
195 1 : func(p *dsl.Parser[dsl.Predicate[Op]], s *dsl.Scanner) dsl.Predicate[Op] {
196 0 : return parseFileReadAtOp(s)
197 0 : })
198 1 : p.predicates.DefineFunc("Randomly",
199 1 : func(p *dsl.Parser[dsl.Predicate[Op]], s *dsl.Scanner) dsl.Predicate[Op] {
200 0 : return parseRandomly(s)
201 0 : })
202 1 : p.AddError(ErrInjected)
203 1 : return p
204 : }
205 :
206 : // A Parser parses the error-injecting DSL. It may be extended to include
207 : // additional errors through AddError.
208 : type Parser struct {
209 : predicates *dsl.Parser[dsl.Predicate[Op]]
210 : injectors *dsl.Parser[Injector]
211 : }
212 :
213 : // Parse parses the error injection DSL, returning the parsed injector.
214 0 : func (p *Parser) Parse(s string) (Injector, error) {
215 0 : return p.injectors.Parse(s)
216 0 : }
217 :
218 : // AddError defines a new error that may be used within the DSL parsed by
219 : // Parse and will inject the provided error.
220 1 : func (p *Parser) AddError(le LabelledError) {
221 1 : // Define the error both as a constant that unconditionally injects the
222 1 : // error, and as a function that injects the error only if the provided
223 1 : // predicate evaluates to true.
224 1 : p.injectors.DefineConstant(le.Label, func() Injector { return le })
225 1 : p.injectors.DefineFunc(le.Label,
226 1 : func(_ *dsl.Parser[Injector], s *dsl.Scanner) Injector {
227 0 : pred := p.predicates.ParseFromPos(s, s.Scan())
228 0 : s.Consume(token.RPAREN)
229 0 : return le.If(pred)
230 0 : })
231 : }
232 :
233 : // LabelledError is an error that also implements Injector, unconditionally
234 : // injecting itself. It implements String() by returning its label. It
235 : // implements Error() by returning its underlying error.
236 : type LabelledError struct {
237 : error
238 : Label string
239 : predicate Predicate
240 : }
241 :
242 : // String implements fmt.Stringer.
243 0 : func (le LabelledError) String() string {
244 0 : if le.predicate == nil {
245 0 : return le.Label
246 0 : }
247 0 : return fmt.Sprintf("(%s %s)", le.Label, le.predicate.String())
248 : }
249 :
250 : // MaybeError implements Injector.
251 1 : func (le LabelledError) MaybeError(op Op) error {
252 1 : if le.predicate == nil || le.predicate.Evaluate(op) {
253 0 : return le
254 0 : }
255 1 : return nil
256 : }
257 :
258 : // If returns an Injector that returns the receiver error if the provided
259 : // predicate evalutes to true.
260 1 : func (le LabelledError) If(p Predicate) Injector {
261 1 : le.predicate = p
262 1 : return le
263 1 : }
264 :
265 0 : func parseFileReadAtOp(s *dsl.Scanner) *opFileReadAt {
266 0 : lit := s.Consume(token.INT).Lit
267 0 : off, err := strconv.ParseInt(lit, 10, 64)
268 0 : if err != nil {
269 0 : panic(err)
270 : }
271 0 : s.Consume(token.RPAREN)
272 0 : return &opFileReadAt{offset: off}
273 : }
274 :
275 0 : func parseRandomly(s *dsl.Scanner) Predicate {
276 0 : lit := s.Consume(token.FLOAT).Lit
277 0 : p, err := strconv.ParseFloat(lit, 64)
278 0 : if err != nil {
279 0 : panic(err)
280 0 : } else if p > 1.0 {
281 0 : // NB: It's not possible for p to be less than zero because we don't
282 0 : // try to parse the '-' token.
283 0 : panic(errors.Newf("errorfs: Randomly proability p must be within p ≤ 1.0"))
284 : }
285 :
286 0 : var seed int64
287 0 : tok := s.Scan()
288 0 : switch tok.Kind {
289 0 : case token.RPAREN:
290 0 : case token.INT:
291 0 : seed, err = strconv.ParseInt(tok.Lit, 10, 64)
292 0 : if err != nil {
293 0 : panic(err)
294 : }
295 0 : s.Consume(token.RPAREN)
296 0 : default:
297 0 : panic(errors.Errorf("errorfs: unexpected token %s; expected RPAREN | FLOAT", tok.String()))
298 : }
299 0 : return Randomly(p, seed)
300 : }
|
