Summary of Bug

Items from a nested store prefix iterator are added to other existing (still open and in use) store prefix iterators. This causes these other iterators to provide entries outside their intended range.

Version

v0.46.8

Steps to Reproduce

I found this because one of our unit tests started failing when we bumped our SDK to version v0.46.8. I'll try to describe it as succinctly as possible, but will also provide code at the bottom.

The function being testing named IterateRecordSpecsForOwner. It iterates over some index entries in state in order to get some specific "contract specification ids"; I will refer to this as the "outside iterator". For each contract specification id, it then iterates over the record specification's in state; I will refer to these ones as the "inside iterator(s)".

The iterators are created using sdk.KVStorePrefixIterator. The inside iterators are created, fully used, and closed while the outside iterator is still open and being used, i.e. the iterators are nested. The same store is provided for both, but different prefixes are provided that don't overlap.

There are three types of state entries involved in this unit test:

1. An account address to contract specification id index. Keys: <type byte (32)><address length><address><contract specification id>.
2. Contract specifications. Keys: <type byte (3)><contract spec id>. These aren't directly involved in the iteration, but are needed as part of setup.
3. Record specifications. Keys: <type byte (5)><contract spec id><record spec name hash>.

The outer iterator is prefixed with <type byte (32)><address length><address>. It's .Key()s are expected to be <contract specification id>s.

The inside iterator is prefixed with <type byte (5)><contract spec id>. The entries it provides are expected to be record specifications.

The unit test that's failing has the following set up:

1. Two account addresses: account 1, and account 2.
2. Three contract specifications in state: contract spec 0 (associated with account 1), contract spec 1 (associated with account 2), and contract spec 2 (associated with both account 1 and 2).
3. Six record specifications in state: two for each contract specification.
4. Four index entries: account 1 -> contract spec 0, account 1 -> contract spec 2, account 2 -> contract spec 1, account 2 -> contract spec 2.

After setup, IterateRecordSpecsForOwner is called for account 1. It is expected to iterate over four record specs: two each from contract specs 0 and 2. Instead, the second value provided by the outer iterator is a record spec entry (which it fails to decode since it's expecting only index entries).

In IntelliJ, i used the debugger on the unit test in question to investigate.

I verified that the store has everything expected, i.e. store.parent.cache = {map[string]*cachekv.cValue} has all twelve items (store = {types.KVStore | *gaskv.Store} , and store.parent = {types.KVStore | *cachekv.Store}).

Here's what I'm seeing as it runs:

1. Outside iterator created.
2. .Valid() called on outside iterator: returns true.
3. .Key() called on outside iterator: returns the first index key as expected (account 1 -> contract spec 0).
   Here's what the debugger had to say about the outside iterator:

   it = {db.Iterator | *gaskv.gasIterator} 
    gasMeter = {types.GasMeter | *types.infiniteGasMeter} InfiniteGasMeter:\n  consumed: 104913
    gasConfig = {types.GasConfig}
    parent = {db.Iterator | *internal.cacheMergeIterator}
     parent = {db.Iterator | *iavl.UnsavedFastIterator}
     cache = {db.Iterator | *internal.memIterator}
      iter = {btree.GenericIter[internal.item]}
       tr = {*btree.BTreeG[internal.item] | 0x14000e32380}
        cow = {uint64} 178
        mu = {*sync.RWMutex | 0x140005ae408}
        root = {*btree.node[internal.item] | 0x14001cded80}
         cow = {uint64} 178
         count = {int} 2
         items = {[]internal.item} len:2, cap:2
          0 = {internal.item}
           key = {[]uint8} len:39, cap:48
           value = {[]uint8} len:1, cap:1
          1 = {internal.item}
           key = {[]uint8} len:39, cap:48
           value = {[]uint8} len:1, cap:1
         children = {*[]*btree.node[internal.item] | 0x0} nil
        count = {int} 2
   

   Not shown here is that it.parent.parent = {db.Iterator | *iavl.UnsavedFastIterator} .Valid() is false, but it.parent.cache .Valid() is true.
   Also not included is that,it.parent.cache.iter.stack[0]: .i = 0 and .n.items has 2 entries: the two index entries expected.
4. An inside iterator is created for the first contract specification id.
5. The inside iterator steps through its two entries and is then invalid and closed.
6. .Next() called on outside iterator.
7. .Valid() called on outside iterator: returns true.
8. .Key() called on outside iterator: returns the key for the second record specification that was seen in step 5.
   Here's what the debugger had to say about the outside iterator now:

   it = {db.Iterator | *gaskv.gasIterator} 
    gasMeter = {types.GasMeter | *types.infiniteGasMeter} InfiniteGasMeter:\n  consumed: 106539
    gasConfig = {types.GasConfig}
    parent = {db.Iterator | *internal.cacheMergeIterator}
     parent = {db.Iterator | *iavl.UnsavedFastIterator}
     cache = {db.Iterator | *internal.memIterator}
      iter = {btree.GenericIter[internal.item]}
       tr = {*btree.BTreeG[internal.item] | 0x14000e32380}
        cow = {uint64} 178
        mu = {*sync.RWMutex | 0x140005ae408}
        root = {*btree.node[internal.item] | 0x14001cded80}
         cow = {uint64} 178
         count = {int} 4
         items = {[]internal.item} len:4, cap:4
          0 = {internal.item}
           key = {[]uint8} len:33, cap:48
           value = {[]uint8} len:121, cap:121
          1 = {internal.item}
           key = {[]uint8} len:33, cap:48
           value = {[]uint8} len:121, cap:121
          2 = {internal.item}
           key = {[]uint8} len:39, cap:48
           value = {[]uint8} len:1, cap:1
          3 = {internal.item}
           key = {[]uint8} len:39, cap:48
           value = {[]uint8} len:1, cap:1
         children = {*[]*btree.node[internal.item] | 0x0} nil
        count = {int} 4
   

   Here again, it.parent.parent .Valid() is false and it.parent.cache .Valid() is true.
   Also not included in that,it.parent.cache.iter.stack[0]: .i = 1, .n.items has 4 entries: the two record specs seen in step 5, then the two index entries.
   The it.parent.cache.iter.tr.root.items entries are [0] = the first record spec seen by the inside iterator, [1] = the second record spec seen, [2] = the first index entry seen, [3] = the original second index entry (this is what the iterator is expected to be on right now).
   At this point, store.parent.unsortedCache = {map[string]struct{}} has eight items, and store.parent.sortedCache = {*internal.BTree | 0x14000fec4d0} has the four items that the outside iterator now has.
9. Test fails due to an unexpected .Key() from the outside iterator.

Code

The unit test: TestIterateRecordSpecsForOwner
All assertions in that test fail, the first of which is on line 396.

IterateRecordSpecsForOwner:

// IterateRecordSpecsForOwner processes all record specs owned by an address using a given handler.
func (k Keeper) IterateRecordSpecsForOwner(ctx sdk.Context, ownerAddress sdk.AccAddress, handler func(recordSpecID types.MetadataAddress) (stop bool)) error {
	var recordItErr error
	contractItErr := k.IterateContractSpecsForOwner(ctx, ownerAddress, func(contractSpecID types.MetadataAddress) bool {
		needToStop := false
		recordItErr = k.IterateRecordSpecsForContractSpec(ctx, contractSpecID, func(recordSpecID types.MetadataAddress) bool {
			needToStop = handler(recordSpecID)
			return needToStop
		})
		if recordItErr != nil {
			return true
		}
		return needToStop
	})
	if recordItErr != nil {
		return recordItErr
	}
	if contractItErr != nil {
		return contractItErr
	}
	return nil
}

IterateContractSpecsForOwner:

// IterateContractSpecsForOwner processes all contract specs owned by an address using a given handler.
func (k Keeper) IterateContractSpecsForOwner(ctx sdk.Context, ownerAddress sdk.AccAddress, handler func(contractSpecID types.MetadataAddress) (stop bool)) error {
	store := ctx.KVStore(k.storeKey)
	prefix := types.GetAddressContractSpecCacheIteratorPrefix(ownerAddress)
	it := sdk.KVStorePrefixIterator(store, prefix)
	defer it.Close()
	for ; it.Valid(); it.Next() {
		var contractSpecID types.MetadataAddress
		if err := contractSpecID.Unmarshal(it.Key()[len(prefix):]); err != nil {
			return err
		}
		if handler(contractSpecID) {
			break
		}
	}
	return nil
}

IterateRecordSpecsForContractSpec:

// IterateRecordSpecsForContractSpec processes all record specs for a contract spec using a given handler.
func (k Keeper) IterateRecordSpecsForContractSpec(ctx sdk.Context, contractSpecID types.MetadataAddress, handler func(recordSpecID types.MetadataAddress) (stop bool)) error {
	store := ctx.KVStore(k.storeKey)
	prefix, err := contractSpecID.ContractSpecRecordSpecIteratorPrefix()
	if err != nil {
		return err
	}
	it := sdk.KVStorePrefixIterator(store, prefix)
	defer it.Close()
	for ; it.Valid(); it.Next() {
		var recordSpecID types.MetadataAddress
		if err := recordSpecID.Unmarshal(it.Key()); err != nil {
			return err
		}
		if handler(recordSpecID) {
			break
		}
	}
	return nil
}