1// Copyright 2019 The go-ethereum Authors 2// This file is part of the go-ethereum library. 3// 4// The go-ethereum library is free software: you can redistribute it and/or modify 5// it under the terms of the GNU Lesser General Public License as published by 6// the Free Software Foundation, either version 3 of the License, or 7// (at your option) any later version. 8// 9// The go-ethereum library is distributed in the hope that it will be useful, 10// but WITHOUT ANY WARRANTY; without even the implied warranty of 11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12// GNU Lesser General Public License for more details. 13// 14// You should have received a copy of the GNU Lesser General Public License 15// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. 16 17package snapshot 18 19import ( 20 "bytes" 21 "fmt" 22 "sort" 23 24 "github.com/ethereum/go-ethereum/common" 25) 26 27// weightedIterator is a iterator with an assigned weight. It is used to prioritise 28// which account or storage slot is the correct one if multiple iterators find the 29// same one (modified in multiple consecutive blocks). 30type weightedIterator struct { 31 it Iterator 32 priority int 33} 34 35// weightedIterators is a set of iterators implementing the sort.Interface. 36type weightedIterators []*weightedIterator 37 38// Len implements sort.Interface, returning the number of active iterators. 39func (its weightedIterators) Len() int { return len(its) } 40 41// Less implements sort.Interface, returning which of two iterators in the stack 42// is before the other. 43func (its weightedIterators) Less(i, j int) bool { 44 // Order the iterators primarily by the account hashes 45 hashI := its[i].it.Hash() 46 hashJ := its[j].it.Hash() 47 48 switch bytes.Compare(hashI[:], hashJ[:]) { 49 case -1: 50 return true 51 case 1: 52 return false 53 } 54 // Same account/storage-slot in multiple layers, split by priority 55 return its[i].priority < its[j].priority 56} 57 58// Swap implements sort.Interface, swapping two entries in the iterator stack. 59func (its weightedIterators) Swap(i, j int) { 60 its[i], its[j] = its[j], its[i] 61} 62 63// fastIterator is a more optimized multi-layer iterator which maintains a 64// direct mapping of all iterators leading down to the bottom layer. 65type fastIterator struct { 66 tree *Tree // Snapshot tree to reinitialize stale sub-iterators with 67 root common.Hash // Root hash to reinitialize stale sub-iterators through 68 69 curAccount []byte 70 curSlot []byte 71 72 iterators weightedIterators 73 initiated bool 74 account bool 75 fail error 76} 77 78// newFastIterator creates a new hierarchical account or storage iterator with one 79// element per diff layer. The returned combo iterator can be used to walk over 80// the entire snapshot diff stack simultaneously. 81func newFastIterator(tree *Tree, root common.Hash, account common.Hash, seek common.Hash, accountIterator bool) (*fastIterator, error) { 82 snap := tree.Snapshot(root) 83 if snap == nil { 84 return nil, fmt.Errorf("unknown snapshot: %x", root) 85 } 86 fi := &fastIterator{ 87 tree: tree, 88 root: root, 89 account: accountIterator, 90 } 91 current := snap.(snapshot) 92 for depth := 0; current != nil; depth++ { 93 if accountIterator { 94 fi.iterators = append(fi.iterators, &weightedIterator{ 95 it: current.AccountIterator(seek), 96 priority: depth, 97 }) 98 } else { 99 // If the whole storage is destructed in this layer, don't 100 // bother deeper layer anymore. But we should still keep 101 // the iterator for this layer, since the iterator can contain 102 // some valid slots which belongs to the re-created account. 103 it, destructed := current.StorageIterator(account, seek) 104 fi.iterators = append(fi.iterators, &weightedIterator{ 105 it: it, 106 priority: depth, 107 }) 108 if destructed { 109 break 110 } 111 } 112 current = current.Parent() 113 } 114 fi.init() 115 return fi, nil 116} 117 118// init walks over all the iterators and resolves any clashes between them, after 119// which it prepares the stack for step-by-step iteration. 120func (fi *fastIterator) init() { 121 // Track which account hashes are iterators positioned on 122 var positioned = make(map[common.Hash]int) 123 124 // Position all iterators and track how many remain live 125 for i := 0; i < len(fi.iterators); i++ { 126 // Retrieve the first element and if it clashes with a previous iterator, 127 // advance either the current one or the old one. Repeat until nothing is 128 // clashing any more. 129 it := fi.iterators[i] 130 for { 131 // If the iterator is exhausted, drop it off the end 132 if !it.it.Next() { 133 it.it.Release() 134 last := len(fi.iterators) - 1 135 136 fi.iterators[i] = fi.iterators[last] 137 fi.iterators[last] = nil 138 fi.iterators = fi.iterators[:last] 139 140 i-- 141 break 142 } 143 // The iterator is still alive, check for collisions with previous ones 144 hash := it.it.Hash() 145 if other, exist := positioned[hash]; !exist { 146 positioned[hash] = i 147 break 148 } else { 149 // Iterators collide, one needs to be progressed, use priority to 150 // determine which. 151 // 152 // This whole else-block can be avoided, if we instead 153 // do an initial priority-sort of the iterators. If we do that, 154 // then we'll only wind up here if a lower-priority (preferred) iterator 155 // has the same value, and then we will always just continue. 156 // However, it costs an extra sort, so it's probably not better 157 if fi.iterators[other].priority < it.priority { 158 // The 'it' should be progressed 159 continue 160 } else { 161 // The 'other' should be progressed, swap them 162 it = fi.iterators[other] 163 fi.iterators[other], fi.iterators[i] = fi.iterators[i], fi.iterators[other] 164 continue 165 } 166 } 167 } 168 } 169 // Re-sort the entire list 170 sort.Sort(fi.iterators) 171 fi.initiated = false 172} 173 174// Next steps the iterator forward one element, returning false if exhausted. 175func (fi *fastIterator) Next() bool { 176 if len(fi.iterators) == 0 { 177 return false 178 } 179 if !fi.initiated { 180 // Don't forward first time -- we had to 'Next' once in order to 181 // do the sorting already 182 fi.initiated = true 183 if fi.account { 184 fi.curAccount = fi.iterators[0].it.(AccountIterator).Account() 185 } else { 186 fi.curSlot = fi.iterators[0].it.(StorageIterator).Slot() 187 } 188 if innerErr := fi.iterators[0].it.Error(); innerErr != nil { 189 fi.fail = innerErr 190 return false 191 } 192 if fi.curAccount != nil || fi.curSlot != nil { 193 return true 194 } 195 // Implicit else: we've hit a nil-account or nil-slot, and need to 196 // fall through to the loop below to land on something non-nil 197 } 198 // If an account or a slot is deleted in one of the layers, the key will 199 // still be there, but the actual value will be nil. However, the iterator 200 // should not export nil-values (but instead simply omit the key), so we 201 // need to loop here until we either 202 // - get a non-nil value, 203 // - hit an error, 204 // - or exhaust the iterator 205 for { 206 if !fi.next(0) { 207 return false // exhausted 208 } 209 if fi.account { 210 fi.curAccount = fi.iterators[0].it.(AccountIterator).Account() 211 } else { 212 fi.curSlot = fi.iterators[0].it.(StorageIterator).Slot() 213 } 214 if innerErr := fi.iterators[0].it.Error(); innerErr != nil { 215 fi.fail = innerErr 216 return false // error 217 } 218 if fi.curAccount != nil || fi.curSlot != nil { 219 break // non-nil value found 220 } 221 } 222 return true 223} 224 225// next handles the next operation internally and should be invoked when we know 226// that two elements in the list may have the same value. 227// 228// For example, if the iterated hashes become [2,3,5,5,8,9,10], then we should 229// invoke next(3), which will call Next on elem 3 (the second '5') and will 230// cascade along the list, applying the same operation if needed. 231func (fi *fastIterator) next(idx int) bool { 232 // If this particular iterator got exhausted, remove it and return true (the 233 // next one is surely not exhausted yet, otherwise it would have been removed 234 // already). 235 if it := fi.iterators[idx].it; !it.Next() { 236 it.Release() 237 238 fi.iterators = append(fi.iterators[:idx], fi.iterators[idx+1:]...) 239 return len(fi.iterators) > 0 240 } 241 // If there's no one left to cascade into, return 242 if idx == len(fi.iterators)-1 { 243 return true 244 } 245 // We next-ed the iterator at 'idx', now we may have to re-sort that element 246 var ( 247 cur, next = fi.iterators[idx], fi.iterators[idx+1] 248 curHash, nextHash = cur.it.Hash(), next.it.Hash() 249 ) 250 if diff := bytes.Compare(curHash[:], nextHash[:]); diff < 0 { 251 // It is still in correct place 252 return true 253 } else if diff == 0 && cur.priority < next.priority { 254 // So still in correct place, but we need to iterate on the next 255 fi.next(idx + 1) 256 return true 257 } 258 // At this point, the iterator is in the wrong location, but the remaining 259 // list is sorted. Find out where to move the item. 260 clash := -1 261 index := sort.Search(len(fi.iterators), func(n int) bool { 262 // The iterator always advances forward, so anything before the old slot 263 // is known to be behind us, so just skip them altogether. This actually 264 // is an important clause since the sort order got invalidated. 265 if n < idx { 266 return false 267 } 268 if n == len(fi.iterators)-1 { 269 // Can always place an elem last 270 return true 271 } 272 nextHash := fi.iterators[n+1].it.Hash() 273 if diff := bytes.Compare(curHash[:], nextHash[:]); diff < 0 { 274 return true 275 } else if diff > 0 { 276 return false 277 } 278 // The elem we're placing it next to has the same value, 279 // so whichever winds up on n+1 will need further iteraton 280 clash = n + 1 281 282 return cur.priority < fi.iterators[n+1].priority 283 }) 284 fi.move(idx, index) 285 if clash != -1 { 286 fi.next(clash) 287 } 288 return true 289} 290 291// move advances an iterator to another position in the list. 292func (fi *fastIterator) move(index, newpos int) { 293 elem := fi.iterators[index] 294 copy(fi.iterators[index:], fi.iterators[index+1:newpos+1]) 295 fi.iterators[newpos] = elem 296} 297 298// Error returns any failure that occurred during iteration, which might have 299// caused a premature iteration exit (e.g. snapshot stack becoming stale). 300func (fi *fastIterator) Error() error { 301 return fi.fail 302} 303 304// Hash returns the current key 305func (fi *fastIterator) Hash() common.Hash { 306 return fi.iterators[0].it.Hash() 307} 308 309// Account returns the current account blob. 310// Note the returned account is not a copy, please don't modify it. 311func (fi *fastIterator) Account() []byte { 312 return fi.curAccount 313} 314 315// Slot returns the current storage slot. 316// Note the returned slot is not a copy, please don't modify it. 317func (fi *fastIterator) Slot() []byte { 318 return fi.curSlot 319} 320 321// Release iterates over all the remaining live layer iterators and releases each 322// of thme individually. 323func (fi *fastIterator) Release() { 324 for _, it := range fi.iterators { 325 it.it.Release() 326 } 327 fi.iterators = nil 328} 329 330// Debug is a convencience helper during testing 331func (fi *fastIterator) Debug() { 332 for _, it := range fi.iterators { 333 fmt.Printf("[p=%v v=%v] ", it.priority, it.it.Hash()[0]) 334 } 335 fmt.Println() 336} 337 338// newFastAccountIterator creates a new hierarchical account iterator with one 339// element per diff layer. The returned combo iterator can be used to walk over 340// the entire snapshot diff stack simultaneously. 341func newFastAccountIterator(tree *Tree, root common.Hash, seek common.Hash) (AccountIterator, error) { 342 return newFastIterator(tree, root, common.Hash{}, seek, true) 343} 344 345// newFastStorageIterator creates a new hierarchical storage iterator with one 346// element per diff layer. The returned combo iterator can be used to walk over 347// the entire snapshot diff stack simultaneously. 348func newFastStorageIterator(tree *Tree, root common.Hash, account common.Hash, seek common.Hash) (StorageIterator, error) { 349 return newFastIterator(tree, root, account, seek, false) 350} 351