1// Copyright 2015 The etcd Authors 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package v2store 16 17import ( 18 "fmt" 19 "path" 20 "strings" 21 "sync" 22 23 "go.etcd.io/etcd/server/v3/etcdserver/api/v2error" 24) 25 26type EventHistory struct { 27 Queue eventQueue 28 StartIndex uint64 29 LastIndex uint64 30 rwl sync.RWMutex 31} 32 33func newEventHistory(capacity int) *EventHistory { 34 return &EventHistory{ 35 Queue: eventQueue{ 36 Capacity: capacity, 37 Events: make([]*Event, capacity), 38 }, 39 } 40} 41 42// addEvent function adds event into the eventHistory 43func (eh *EventHistory) addEvent(e *Event) *Event { 44 eh.rwl.Lock() 45 defer eh.rwl.Unlock() 46 47 eh.Queue.insert(e) 48 49 eh.LastIndex = e.Index() 50 51 eh.StartIndex = eh.Queue.Events[eh.Queue.Front].Index() 52 53 return e 54} 55 56// scan enumerates events from the index history and stops at the first point 57// where the key matches. 58func (eh *EventHistory) scan(key string, recursive bool, index uint64) (*Event, *v2error.Error) { 59 eh.rwl.RLock() 60 defer eh.rwl.RUnlock() 61 62 // index should be after the event history's StartIndex 63 if index < eh.StartIndex { 64 return nil, 65 v2error.NewError(v2error.EcodeEventIndexCleared, 66 fmt.Sprintf("the requested history has been cleared [%v/%v]", 67 eh.StartIndex, index), 0) 68 } 69 70 // the index should come before the size of the queue minus the duplicate count 71 if index > eh.LastIndex { // future index 72 return nil, nil 73 } 74 75 offset := index - eh.StartIndex 76 i := (eh.Queue.Front + int(offset)) % eh.Queue.Capacity 77 78 for { 79 e := eh.Queue.Events[i] 80 81 if !e.Refresh { 82 ok := e.Node.Key == key 83 84 if recursive { 85 // add tailing slash 86 nkey := path.Clean(key) 87 if nkey[len(nkey)-1] != '/' { 88 nkey = nkey + "/" 89 } 90 91 ok = ok || strings.HasPrefix(e.Node.Key, nkey) 92 } 93 94 if (e.Action == Delete || e.Action == Expire) && e.PrevNode != nil && e.PrevNode.Dir { 95 ok = ok || strings.HasPrefix(key, e.PrevNode.Key) 96 } 97 98 if ok { 99 return e, nil 100 } 101 } 102 103 i = (i + 1) % eh.Queue.Capacity 104 105 if i == eh.Queue.Back { 106 return nil, nil 107 } 108 } 109} 110 111// clone will be protected by a stop-world lock 112// do not need to obtain internal lock 113func (eh *EventHistory) clone() *EventHistory { 114 clonedQueue := eventQueue{ 115 Capacity: eh.Queue.Capacity, 116 Events: make([]*Event, eh.Queue.Capacity), 117 Size: eh.Queue.Size, 118 Front: eh.Queue.Front, 119 Back: eh.Queue.Back, 120 } 121 122 copy(clonedQueue.Events, eh.Queue.Events) 123 return &EventHistory{ 124 StartIndex: eh.StartIndex, 125 Queue: clonedQueue, 126 LastIndex: eh.LastIndex, 127 } 128 129} 130