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