A tool for measuring the performance of false dependencies in store forwarding

measure-store-buffer-false-dependencies.py

# Test address matching in store forwarding
#
# This tests a mechanism discussed in these references:
#
# * US Patent 2008/0082765 A1
#     https://patentimages.storage.googleapis.com/73/b9/bf/b258f3e3985f47/US20080082765A1.pdf
# * Fallout: Leaking Data on Meltdown-resistant CPUs
#     https://mdsattacks.com/files/fallout.pdf
# * Stack Overflow: What are the microarchitectural details behind MSBDS (Fallout)?
#     https://stackoverflow.com/a/56213609
#
# To get precise performance numbers, we want to set up a test harness that 
# has a fairly rigid/deterministic latency, but allows us to control how many
# outstanding stores are in the store buffer.
#
# We do this by combining a chain of long-but-constant latency instructions (here
# a chain of vsqrtpd's, run on zero input) with a series of stores. The stores
# come after the sqrts in the loop, and should all hit the L1D. They will remain in
# the store buffer until the sqrts retire, though, after which they should
# generally retire at 1/cycle. This happens "asynchronously", so as long as the
# store buffer isn't full (causing a stall if another store executes), these
# instructions aren't usually part of the dependency chain.
#
# To tie this all together, and make one long dependency chain across iterations of
# a loop, we add to an address based on the results of the sqrt chain (always
# zero), load from the address into a vector register (giving zero again), and
# use that result for the next chain.
#
# This technique is a variation on/inspired by Henry Wong's technique for measuring
# on-chip buffers: http://blog.stuffedcow.net/2013/05/measuring-rob-capacity/
# Though without the dual pointer-chasing used in his method, this ends up looking
# pretty different, and more like a traditional dependency chain latency test.
# Additionally, I got the idea of using vpsqrtd from Paul Khuong in this tweet:
#   https://mobile.twitter.com/pkhuong/status/1265433916791558146
#
# Now that we have the setup, the 'payload' is the pattern of addresses stored to,
# along with the address of the single load in the dependency chain. To measure
# the behavior described in the references above, we want to generate a bunch
# of stores that match the "loosenet" but not the "finenet". For each store in
# the store buffer, a load will try to match with the most recent store that
# has the same low 12 bits. The high address bits are then compared for a
# match, otherwise the load is re-dispatched to match the next older store. The
# number of stores, and their size/scalarity, are controlled by knobs below.
#
# Within this group of stores, we put a single store that does in fact match
# the eventual load from [rbp]. By doing this we can control how many
# re-dispatches take place.

# Number of sqrts in each iteration of the main dependency chain. This number
# times the latency of vsqrtpd(0) in cycles should be larger than the size of
# the store buffer divided by the number of stores per cycle (usually one)
N_SQRTS = 5
# Offset of a falsely-dependent address
# Negative since we store to the stack, which grows downwards
ALIAS_OFFSET = -4096
SCALAR = 1
SIZE = 4
# Compensation factor for rdtsc not counting actual cycles:
#   Turbo frequency / base (rdtsc) frequency
# Probably need to change this for other machines...
DETURBO = 2.9 / 2.4

# How many stores to insert (all in the range are tested)
# This should have many values both above and below the size of the store buffer
STORE_COUNTS = range(1, 65, 1)
# How many stores back to put a matching, forward-able store
FWD_INDICES = range(1, 8)

# Generate a C file that calls each function in the assembly
with open('_run.c', 'w') as f:
    f.write('#include <stdint.h>\n')
    f.write('#include <stdio.h>\n')
    f.write('\n')
    f.write('const uint64_t count = 1 << 8;\n')
    f.write('const uint64_t n_iters = 1 << 11;\n')
    f.write('\n')

    f.write('int main() {\n')
    for n_stores in STORE_COUNTS:
        f.write('printf("%02d");\n' % n_stores)
        # Call each function for this row, print the results
        for fwd_idx in FWD_INDICES:
            fn = 'test_store_buffer%02d_%02d' % (n_stores, fwd_idx)
            f.write('extern uint64_t %s();\n' % fn)
            f.write('printf(",%%10.6f", (float)%s() * %s / n_iters);\n' % (fn, DETURBO))
        f.write('puts("");\n')
        f.write('fflush(stdout);\n')
    f.write('}\n')

# Generate an assembly file with a bunch of test functions
with open('_storebuf.s', 'w') as f:
    f.write('''
.intel_syntax noprefix

.global _count
.global _n_iters
''')

    for fwd_idx in FWD_INDICES:
        for n_stores in STORE_COUNTS:
            name = '%02d_%02d' % (n_stores, fwd_idx)

            # Generate the store offsets. All but the one at -fwd_idx are
            # ALIAS_OFFSET away (provided there are enough stores for fwd_idx
            # to exist), each of which should be false dependencies. These offsets
            # can be tweaked for fun or profit.
            # OK, maybe not profit... and actually, probably not fun either
            offsets = [ALIAS_OFFSET for i in range(n_stores)]
            if fwd_idx < len(offsets):
                offsets[-fwd_idx] = 0

            # Generate the actual store instructions based on the SCALAR/SIZE settings
            if SCALAR:
                if SIZE == 1:
                    reg = 'r11b'
                    ptr = 'BYTE'
                elif SIZE == 4:
                    reg = 'r11d'
                    ptr = 'DWORD'
                else:
                    reg = 'r11'
                    ptr = 'QWORD'
                lines = ['mov %s PTR [rbp+%s], %s' % (ptr, offset, reg) for offset in offsets]
                chain = 'vpbroadcast%s ymm0, %s PTR [rbp]' % (ptr[0].lower(), ptr)
            else:
                reg = 'ymm1'
                ptr = 'YMMWORD'
                lines = ['vmovdqu %s PTR [rbp+%s], %s' % (ptr, offset, reg) for offset in offsets]
                chain = 'vmovdqu ymm0, %s PTR [rbp]' % ptr
            lines = '\n    '.join(lines)

            # Generate chain instructions to link the FP/memory dependency chains.
            # Extract the first lane of ymm0 (should always be zero), add it to rbp,
            # then load ymm with the value of rbp (also zero; load controlled by SCALAR/SIZE)
            chain = ['vpextrq r10, xmm0, 0', 'add rbp, r10', chain]
            chain = '\n    '.join(chain)

            # Generate the main dependency chain: a bunch of expensive but deterministic ops
            work = []
            work += ['vsqrtpd ymm0, ymm0' for _ in range(N_SQRTS)]
            work = '\n    '.join(work)

            # Push/pop some callee-saved regs just in case
            regs = [12, 13, 14, 15]
            pushes = '\n'.join('push r%s' % r for r in regs)
            pops = '\n'.join('pop r%s' % r for r in regs[::-1])

            f.write('''
.global _test_store_buffer{n}
_test_store_buffer{n}:
    push rbp
    mov  rbp,rsp
    {pushes}

    # Align rbp
    sub rbp, 127
    and rbp, -32

    # Initialize counters etc
    mov rcx, [rip+_count]
    xor r11, r11
    mov r13, -1
    vxorps ymm0, ymm0, ymm0
    vxorps ymm1, ymm0, ymm0

    # Make sure to store 0 at rbp
    vmovdqu YMMWORD PTR [rbp], ymm0

    # Outer loop
L{n}_1:

        # Start counter
        rdtsc
        mov r8, rdx
        shl r8, 32
        or r8, rax

        # Inner loop
        mov r12, [rip+_n_iters]
    L{n}_3:
            {work}

            {lines}

            {chain}
        sub r12, 1
        jnz L{n}_3

        # End counter
        rdtsc
        mov r9, rdx
        shl r9, 32
        or r9, rax
        sub r9, r8

        # Update minimum
        cmp r13, r9
        cmova r13, r9

    sub rcx, 1
    jnz L{n}_1

    # Return minimum
    mov rax, r13

    {pops}
    pop rbp
    ret    
'''.format(n=name, pushes=pushes, pops=pops, lines=lines, work=work, chain=chain))

results-hsw.csv