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