path: root/src/arch/cache.md

# cache

Caches are organized by the following components
- `sets`
- `ways`
- `entries`

Each `set` consists of one or more `ways` and  a `way` is a single slot which
can hold an `entry`.
```
S-set / W-way cache

         +----------------- .. -----------+
SET 0    | WAY 0 | WAY 1 |      | WAY W-1 |
         +----------------- .. -----------+
SET 1    | WAY 0 | WAY 1 |      | WAY W-1 |
         +----------------- .. -----------+
..       |                                |
         +----------------- .. -----------+
SET S-1  | WAY 0 | WAY 1 |      | WAY W-1 |
         +----------------- .. -----------+
```

In general a cache is described by the number of `sets S` and the number of
`ways W`. Depending on the values for `S` and `W` caches can be further
classified.
- `W=1` is a `direct-mapped` cache, which means that each entry can be placed
  at exactly **ONE** location in the cache. It is also called a _one-way set
  associative_ cache.
- `S>1 & W>1` is a `W-way set associative` cache, which consists of S sets where
  each set consists of W ways. Each entry maps to a **UNIQUE** set, but to
  **ANY** way in that set.
- `S=1` is a `fully-associative` cache, which means that each entry can be
  placed at **ANY** location in the cache.

To determine which set an entry falls into, a `hash function` is applied on the
`key` which is associated with the entry. The set is then given by applying the
modulo operation to the hash value `hash % num_sets`.

The following figure illustrates the different cache classes and gives an
example which entries the given hash value `5` can map to.
```
direct-mapped      2-way set associative      fully-associative

HASH=5 (IDX=5%4)   HASH=5 (IDX=5%4)           HASH=5 (only one IDX)
|                  |                          |
|    S=4, W=1      |   S=4, W=2               |   S=1, W=4
|    +--------+    |   +--------+--------+    |   +--------+--------+--------+--------+
|   0|        |    |  0|        |        |    `->0| xxxxxx | xxxxxx | xxxxxx | xxxxxx |
|    +--------+    |   +--------+--------+        +--------+--------+--------+--------+
`- >1| xxxxxx |    `->1| xxxxxx | xxxxxx |
     +--------+        +--------+--------+
    2|        |       2|        |        |
     +--------+        +--------+--------+
    3|        |       3|        |        |
     +--------+        +--------+--------+
```

## CPU (hardware) caches
The number of sets in a hardware cache is usually a power of two. The `address`
acts as the key and some bits in the address are used to select the set in the
cache. The hash function in this case is simple, as it just extracts the bits
from the address which are used to select the set.

The `address` is usually split up into the `{ TAG, IDX, OFF }` bits which are
used to lookup an entry in the cache.

The `IDX` bits are used to index into the corresponding set, where the `TAG`
bits are then compared against the stored `TAG` bits in each way. If any way
holds an entry with the matching `TAG` bits, the lookup is a `HIT`, else a
`MISS`.

In case the entry is in the cache, the `OFF` bits are used to index into the
cache line. Hence, the number of offset bits available define the cache line
size.

The following gives an example for _64-bit addresses_ and a _direct-mapped_ cache.
```
        63                      0
        +-----------------------+
ADDR:   |  TAG  |  IDX  |  OFF  |
        +-----------------------+
            |       |       `------------------,
            |       |                          |
            |       |    CACHE                 |
            |       |    +----------------+    |
            |       |    | TAG | CACHE_LN |    |
            |       |    +----------------+    |
            |       |    | TAG | CACHE_LN |    |
            |       |    +----------------+    |
            |       |    | ..             |    |
            |       |    +----------------+    |
            |       `--> | TAG | CACHE_LN |    |
            |            +----------------+    |
            |               |     |            |
            |               v     v            |
            `-------------> =     + <----------`
                            |     |
                            v     v
                           HIT?  DATA


OFF bits: ln2 (cache_line_sz)
IDX bits: ln2 (num_sets)
TAG bits: 64 - IDX bits - OFF bits
```

The total size of a cache can be computed by `cache_line_sz * num_sets * num_ways`.
```
Example
  SETS: 64        => 6 IDX bits
  WAYS: 8
  LINE: 64 bytes  => 6 OFF bits

  SIZE: 64 sets * 8 ways * 64 bytes => 32k bytes
```

## Hardware caches with virtual memory
In the context of _virtual memory_, caches can be placed at different location
in the memory path, either _before_ or _after_ the `virtual address (VA)` to
`physical address (PA)` translation. Each placement has different properties
discussed in the following.

If the cache is placed _before_ the `VA -> PA` translation, it is called
`virtually indexed virtually tagged (VIVT)` cache, as it is indexed by a virtual
address and data in the cache is tagged with the virtual address as well.

The benefit of VIVT caches is that lookups are very fast as there is no need to
wait for the result of the address translation. However, VIVT caches may suffer
from the following problems.
- `synonyms`: different VAs map to the same PA. This can happen in a single
  address space (same page table), if for example a process maps the same file
  at different VAs (also commonly referred to as _aliasing_ or _cache-line
  sharing_). This can also happen in different address spaces (different page
  tables), if for example pages are shared between two processes.
  ```
  PT1
  +-------+
  |       |        PHYSMEM          PT2
  +-------+        +-------+        +-------+
  |  VA1  |---,    |       |        |       |
  +-------+   |    +-------+        +-------+
  |       |   +--->|  PA1  |<-------|  VA3  |
  +-------+   |    +-------+        +-------+
  |  VA2  |---`    |       |        |       |
  +-------+        +-------+        +-------+
  |       |
  +-------+

  Assume VA1 != VA2 != VA3

  CACHE
   TAG     DATA
  +-------+-------------+        Problems:
  |  VA1  | Copy of PA1 |        * multiple copies of the same data.
  |  VA3  | Copy of PA1 |        * write through one VA and read through a
  |       |             |          different VA results in reading stale data.
  |  VA2  | Copy of PA1 |
  +-------+-------------+
  ```
- `homonyms`: same VA corresponds to different PAs. This is the standard case
  between two different address spaces (eg in a multi-tasking os), for example
  if the same VA is used in two different processes, but it maps to a different
  PA for each process.
  ```
  PT1              PHYSMEM          PT2
  +-------+        +-------+        +-------+
  |  VA1  |------->|  PA1  |    ,---|  VA2  |
  +-------+        +-------+    |   +-------+
  |       |        |       |    |   |       |
  |       |        +-------+    |   |       |
  |       |        |  PA2  |<---`   |       |
  +-------+        +-------+        +-------+

  Assume VA1 == VA2

  CACHE
   TAG     DATA
  +-------+-------------+        Problems:
  |  VA1  | Copy of PA1 |        * same VA from different address spaces map to
  |       |             |          different PA
  |       |             |        * read thorugh VA2 returns data from PA1
  +-------+-------------+          rather than from PA2
  ```

While `synonyms` may lead to accessing _stale_ data, if there is no hardware to
guarantee coherency between aliased entries, `homonyms` may lead to accessing
the _wrong_ data.

On one hand there are multiple counter measures to avoid `homonyms`, for example
physical tagging, tags could contain an address space identifier (ASID), or the
cache could be flushed on context switches (changing the page table).
Approaches like physical tagging and ASIDs work, as the same VA always maps to
the same index in the cache, which would then result in a cache miss in case of
the homonym.

Preventing `synonyms` on the other hand is harder, as neither physical tagging
nor ASIDs help in this case. Flushing the cache during context switches only
helps with the case where different address spaces alias shared pages, but it
won't help if the same PA is aliased by different VAs in a single address space.
There are to alternative approaches, one is to have hardware support to detect
synonyms and the other one is to have the operating system only allow shared
mappings with VAs that have the same index bits for the cache. However, the
latter only works for direct-mapped caches, as there is only a single location
where those VAs could map to in the cache.

If the cache is placed _after_ the `VA -> PA` translation, it is called
`physically indexed physically tagged (PIPT)` cache, as it is indexed by a
physical address and data in the cache is tagged with the physical address as
well.

Compared to VIVT caches, PIPT caches do not suffer from `synonyms` or
`homonyms`. However, their major drawback is that the lookup depends on the
result of the address translation, and hence the translation and the cache
lookup happen sequentially which greatly decreases access latency.

Between VIVT and PIPT caches there is also a hybrid approach called `virtually
indexed physically tagged (VIPT)` cache, where the cache lookup is done with a
virtual address and the data is tagged with the physical address.

The benefit of this approach is that the cache lookup and the address
translation can be done in parallel, and due to the physical tagging, `homonyms`
are not possible.

For VIPT caches, `synonyms` may still happen depending on how the cache is
constructed.
- if the `index` bits for the cache lookup, exceed the `page offset` in the
  virtual address, then `synonyms` are still possible.
- if all the `index` bits for the cache lookup fall into the `page offset` of
  the virtual address, then the bits used for the cache lookup won't change
  during the `VA -> PA` translation, and hence the cache effectively operates as
  a PIPT cache. The only downside is that the number of sets in the cache is
  limited by the page size.

### VIPT as PIPT example
The following example shows that for a system with `4k` pages and cache lines of
`64 bytes` a VIPT cache can have at most `64 sets` to still act as PIPT cache.
```
      63      12              0
      +-----------------------+
VA:   |       |     PG_OFF    |
      +-----------------------+
CACHE BITS:   | C_IDX | C_OFF |
              +---------------+

PAGE SIZE  : 4k
PAGE OFFSET: ln (PAGE SIZE) = 12 bits

CACHE LINE  : 64 bytes
CACHE OFFSET: ln (CACHE LINE) = 6 bits

CACHE INDEX: PG_OFF - C_OFF = 6 bits
CACHE SETS : 2^CACHE INDEX = 64 sets
```
The total cache size can be increased by adding additional ways, however that
also has a practical upper limit, as adding more ways reduces the latency.

## Cache info in Linux
```sh
# Info about different caches (size, ways, sets, type, ..).
lscpu -C
# NAME ONE-SIZE ALL-SIZE WAYS TYPE        LEVEL SETS PHY-LINE COHERENCY-SIZE
# L1d       32K     128K    8 Data            1   64        1             64
# L1i       32K     128K    8 Instruction     1   64        1             64
# L2       256K       1M    4 Unified         2 1024        1             64
# L3         6M       6M   12 Unified         3 8192        1             64

# Info about how caches are shared between cores / hw-threads. Identified by
# the same cache ids on the same level.
lscpu -e
# CPU  CORE  L1d:L1i:L2:L3  ONLINE
#   0     0  0:0:0:0           yes
#   1     1  1:1:1:0           yes
#   4     0  0:0:0:0           yes
#   5     1  1:1:1:0           yes
#
# => CPU 0,4 share L1d, L1i, L2 caches (here two hw-threads of a core).
```