---
# System prepended metadata

title: Windows `cache_arena.rs` panic

---

## The Panic

![](https://hackmd.io/_uploads/SkG8fJbih.jpg)

## Investigation

Lighthouse is panicking with an out-of-bounds slice access at position `144115188075905177`. Let's call that position `p`.

In binary, `p` isn't very interesting:

```python
>>> math.log2(p)
57.00000000000049
>>> bin(p)
'0b1000000000000000000000000000000000000000001100000010011001'
```

If the slice contained `u8`, a slice of length `p` would be 144 petabytes. So, it seems that we're getting a *wildly* incorrect slice index.



The panic is the last line of [this function](https://github.com/sigp/lighthouse/blob/dfcb3363c757671eb19d5f8e519b4b94ac74677a/consensus/cached_tree_hash/src/cache_arena.rs#L184):

```rust
    /// Mutably iterate through all values in some allocation.
    fn iter_mut(&mut self, alloc_id: usize) -> Result<impl Iterator<Item = &mut T>, Error> {
        let range = self.range(alloc_id)?;
        Ok(self.backing[range].iter_mut())
    }
```

It must be [`Self::range`](https://github.com/sigp/lighthouse/blob/dfcb3363c757671eb19d5f8e519b4b94ac74677a/consensus/cached_tree_hash/src/cache_arena.rs#L161C1-L174C6) that's giving us `p`:

```rust
    /// Returns the range in `self.backing` that is occupied by some allocation.
    fn range(&self, alloc_id: usize) -> Result<Range<usize>, Error> {
        let start = *self
            .offsets
            .get(alloc_id)
            .ok_or(Error::UnknownAllocId(alloc_id))?;
        let end = self
            .offsets
            .get(alloc_id + 1)
            .copied()
            .unwrap_or(self.backing.len());

        Ok(start..end)
    }
```

Therefore, `p` must be either:

1. A value in `self.offsets`.
2. The length of `self.backing`.

The type of `self.backing` is `Vec<Hash256>`, so the user would need about 4,611 *petabytes* of RAM to allocate that slice. The Blue Waters supercomputer at the University of Illinois boasts 1.5 petabytes of RAM, so let's assume that the user *is not* running a super computer and therefore (2) is impossible because a slice of that length would never have been allocated in the first place.

Therefore, `p` must be a value in `self.offsets`. There are three places where `self.offsets` is set:

1. It is [instantiated](https://github.com/sigp/lighthouse/blob/dfcb3363c757671eb19d5f8e519b4b94ac74677a/consensus/cached_tree_hash/src/cache_arena.rs#L43) in `Self::alloc` based on the length of a`self.backing`.
2. It is [mutated](https://github.com/sigp/lighthouse/blob/dfcb3363c757671eb19d5f8e519b4b94ac74677a/consensus/cached_tree_hash/src/cache_arena.rs#L58) in `Self::grow`.
2. It is [mutated](https://github.com/sigp/lighthouse/blob/dfcb3363c757671eb19d5f8e519b4b94ac74677a/consensus/cached_tree_hash/src/cache_arena.rs#L67-L83) in `Self::shrink`.

We must rule out (1) for the same reason we ruled out the previous (1); the user has (unfortuately) not hijacked the worlds largest supercomputer and installed Windows and Lighthouse on it.

Subsequently, we must look at the [only use](https://github.com/sigp/lighthouse/blob/dfcb3363c757671eb19d5f8e519b4b94ac74677a/consensus/cached_tree_hash/src/cache_arena.rs#L113) of `Self::grow`:

```rust
Ordering::Less => self.grow(alloc_id, self.backing.len() - prev_len)?,
```

Ah ha! Unchecked subtraction! It's an underflow!

Oh wait, if we [zoom out](https://github.com/sigp/lighthouse/blob/dfcb3363c757671eb19d5f8e519b4b94ac74677a/consensus/cached_tree_hash/src/cache_arena.rs#L111-L115) we can see there's a `std::cmp::Ord::cmp` preventing underflow:

```rust
        match prev_len.cmp(&self.backing.len()) {
            Ordering::Greater => self.shrink(alloc_id, prev_len - self.backing.len())?,
            Ordering::Less => self.grow(alloc_id, self.backing.len() - prev_len)?,
            Ordering::Equal => {}
        }
```

To get an underflow we'd need `self.backing.len()` to be *less than* `prev_len`. But the `match` statement prevents us from trying to subtract when that's the case ([example playground]([self_backing_len](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=ca456252e7a6e17c622cfd11293d2df1)) showing `Ord::cmp` behaviour).

Therefore, `Self::grow` can only be called by a value that is less than `self.backing.len()`. The not-a-super-computer argument rules out `Self::grow`.

Now, let us look at the [only use](https://github.com/sigp/lighthouse/blob/dfcb3363c757671eb19d5f8e519b4b94ac74677a/consensus/cached_tree_hash/src/cache_arena.rs#L112) of `Self::shrink`:

```rust
Ordering::Greater => self.shrink(alloc_id, prev_len - self.backing.len())?,
```

Spoiler, it's from the previous `match` statement. I'll repeat it here for readability:

```rust
        match prev_len.cmp(&self.backing.len()) {
            Ordering::Greater => self.shrink(alloc_id, prev_len - self.backing.len())?,
            Ordering::Less => self.grow(alloc_id, self.backing.len() - prev_len)?,
            Ordering::Equal => {}
        }
```

The `Ord::cmp` means that there is no underflow in `prev_len - self.backing.len()`. If we scroll up a few lines we can see `prev_len` being [instantiated](https://github.com/sigp/lighthouse/blob/dfcb3363c757671eb19d5f8e519b4b94ac74677a/consensus/cached_tree_hash/src/cache_arena.rs#L107C1-L107C1):

```rust
let prev_len = self.backing.len();
```

As long as we believe the `match` statement prevents underflow, we must believe that the value being provided to `Self::shrink` is *less than* `self.backing.len()`. The not-a-super-computer argument saves us again.

## Conclusion

In my analysis, I can't see how it's possible to index `self.backing` with a value that is longer than it's length.

Although my analysis could be wrong, I also note that we haven't meaningfully modified this code in years and we've never seen this panic before.

Therefore, I am presently concluding that there is an issue with the user's hardware causing some sort of memory or compute corruption.

