Group Project 5 - Cache Wars
CS 3410 Spring 2017
Due: 11:59pm, Friday, April 21st, 2017
Reminder: you must work in a group of two for this project. You don't need to have the same partner as the earlier projects.
This assignment will help you and your partner further hone your
skills as elite programmers. Your goal is to program a multicore Hogwarts house bot who will race against an opponent to fill memory. This game simultaneously tests your knowledge of computer systems, your
programming skills, and your ability to protect programs from being
hacked.
At the end of the project we will hold a
tournament pitting all your House bots against each other for the 3410 cup, and the top bots
will receive not only bragging rights but actual bonus points on the
assignment. Plus we will be holding a banquet (read: pizza
and soda) for all while we watch the tournament!
Listen to this as you read the intro:
As time wears on in the Wizarding world, magic stays a constant, unchanging force, while technology
advances ever onward. The Ministry of Magic has noticed the Muggles and their technological prowess,
and so have decided to start a new magical education that melds technology and magic in ways never
seen before.
Thus, new Houses arise in Hogwarts School of Witchcraft and Wizardry, each hoping to be the one
to empower the wizarding world through technology. But only one can win the House Cup, a coveted prize
awarded to the highest performing House of the year.
What to submit
- the source code in C, with comments, for your House
- a Makefile so we can build your code - the first additional "FLAGS_" line in the Makefil will be the one used to
determine what flags to compile your bot with and what your bot will be named for the tournament
Game Overview
The game is played by two Houses, each with four cores (witches/wizards). All eight
cores are in a single shared memory space, running on a
simulated 8-core MIPS machine using a small, partitioned,
direct-mapped data memory cache. To simulate 8 MIPS CPUs simultaneously, one
instruction of core 0 is executed, then one instruction of core 1, and so
forth.
Each House is assigned a payload
, a particular byte
of data. The goal of the game is to fill as much memory (any section - theirs or their opponents) with their
House's payload, while simultaneously trying to impede the progress of the
other House. All access to data memory goes through a very small cache,
and there is a large penalty for missing the cache, so a clever House bot
will need to carefully optimize its algorithms for filling
memory. Each core can normally only read and write its own team's half
of the memory space using its own half of the data cache. However, a
core can don_cloak
to put on an invisibility cloak and enter the opponent's memory, which enables the core to
take advantage and read and write the opponent's half of memory space and data cache.
The House has several resources at their disposal to aid
in their mission. Each House can use any of its four cores to cast an Expelliarmus spell,
which disarms the opposing House and stalls its cores for a short
period of time. A core can also set a PETRIFICUS_TOTALUS to different memory locations-
this is a spell that can be set at a certain spot, if encountered by a core of
either House, will be cast and paralyze the core for a long period of
time, rendering them unable to do anything.
Each House supplies a single MIPS executable program. At the
beginning of the game, the simulator starts each by calling the
function
void __start(int core_id, int num_crashed, unsigned char payload);
Each of the four cores devoted to one House will invoke the function
when it first boots, passing its core_id
(a number from 0 to 3), and
the House's payload
(from 0 to 239). If a core ever crashes, it
will simply reset and invoke the function again.
The num_crashes
parameter is 0 when a core first boots, and
is incremented each time the core crashes.
A core can don_cloak
to infiltrate the opponent's memory
space by calling
void don_cloak();
and can retreat back to its own memory space by calling
void retreat();
Invoking don_cloak
can potentially let a House obtain more points and fill memory
more quickly, because it can take advantage of the opponent's memory
cache, and can also be used to impede the progress of the opponent by
interfering with their use of that same cache. However, these tactics
come with risks. Whenever a core is in don_cloak
mode, its core_id
is written into a taunt[]
array that is available to its
opponent. Additionally, it is possible to detect the presence of a snooper by looking at cache usage statistics and timing
information. A core can accuse one of its opponent's cores
of wearing an invisibility cloak by calling:
int tip_off_filch(int opponent_core_id);
If an opponent's core is caught by Filch under the invisibility cloak, he will assign that core to clean the dungeons for the rest
of the game to teach them some respect (aka, essentially locking up the core for the rest of the game).
If a core attempts to tip_off_filch
on a core that is not
wearing an invisibility cloak, the accusing core stalls for
100,000 (STALL_ON_DISTRACTED) cycles as Filch scolds them for wasting his time.
A core can plant a PETRIFICUS_TOTALUS by writing 0xF0 to a
location in memory. PETRIFICUS_TOTALUS spells are set up immediately once 0xF0 is
written to a memory address, but due to the intense work to learn and cast the spell, the core will rest for 100
(STALL_TO_CAST_PETRIFICUS_TOTALUS) cycles before executing the next
instruction. PETRIFICUS_TOTALUS are triggered when any core attempts to
write to a memory location that currently holds the trap byte (even cores of the House who planted them). Such an
attempt causes the write to fail and the writing core to be stalled
for 1,000,000 (STALL_ON_PARALYZED) cycles. Since the write
fails, multiple cores can be stalled by the same PETRIFICUS_TOTALUS. PETRIFICUS_TOTALUS are not triggered by reading memory. Due to
the effort required to cast the spell, each House can set
up at most 15 (PETRIFICUS_TOTALUS_PER_TEAM) PETRIFICUS_TOTALUS.
The upper 4 MB (4 * STACK_SIZE) of memory is protected from PETRIFICUS_TOTALUS.
A core can neutralize a PETRIFICUS_TOTALUS by blocking the spell. It does so by writing 0xF2 to the PETRIFICUS_TOTALUS memory location. However, it takes some time to set up the counterspell, so it requires 100
(STALL_TO_BLOCK_PETRIFICUS_TOTALUS) cycles. This will not
retroactively un-stall any core that has already fallen victim to a PETRIFICUS_TOTALUS
at that location, but will of course save you from being pestered there in the future.
Houses can also temporarily disarm their opponents by using
EXPELLIARMUS. This is done by writing the byte 0xF1 into a
location in memory. When the EXPELLIARMUS is cast in one half of
memory, any opponent cores who try to write to that half of memory
during the next 100 (DISARM_DURATION) cycles will be
disarmed down for 300 (STALL_WHEN_DISARMED) cycles. Since it takes
so much effort to cast the spell, each House's cores can make at most 30 (DISARMS_PER_TEAM) casts of this spell.
The race ends when one House manages to fill the equivalent of half
of its data memory with its payload
, or after a fixed number of
cycles, whichever comes first. The House having the most memory filled
with its payload
wins the match and the rights to proceed in
the Cache Wars 3410 Cup tournament. But beware...for if
you do win the tournament, a great challenge awaits.
Game Details: Memory mapping and layout
The simulator makes it seem like all four of your House's cores live
in the lower half of the memory address space (addresses below
0x80000000). The first 1 MB of this memory is read-only, and is where
the text segment of your MIPS executable is loaded. The next 31 MB is
read-write memory, where global variables and stacks are
placed. Global variables are typically placed near the bottom of this
segment by the compiler, and the stacks are initialized to near the
top of the segment and grow down. All four of the cores of a House
share this same space, and share the same global variables. Your
opponent is mapped into the upper half of the memory address space
(addresses starting at 0x80000000), with an identical layout.
Program stacks: The four program stacks for the four cores
on a team are initially spaced evenly near the top of the 31 MB
read-write segment (though your code can set $sp to anything you like
once it starts executing). The stacks are spaced 1 MB apart; this is
plenty of space for most programs, but if you invoke a deeply recursive
function, the call stacks can overwrite each other.
Status and cores: The simulator keeps track of the
information about each team and each core, and maps this data into
part of the 1 MB read-only memory region, where your House can access
it, and where your opponent can access it when it is
in don_cloak
mode. This includes information about your
current score (how many bytes of memory currently contain your
team's payload
), how many cycles are left remaining in the
game, the contents of all four of your core's register files, and
statistics about cache misses and stalls for each of your four
cores. Some of this information is available in other places as
well: your team's payload
is passed to __start()
, for
example; and cache statistics are also accessible via a system
call.
Physical addresses: Both Houses view the lower half of
memory as their own, and both access their own code, data, and stacks
using addresses below 0x80000000. These, of course, are virtual
addresses. In actuality, the first player's virtual addresses
correspond directly to physical memory addresses, while the second
player's virtual addresses are mapped in reverse: virtual address
0x00001234, for example, is mapped to physical addresses 0x80001234,
and virtual address 0x80001234 is mapped to physical address
0x00001234. This virtual to physical mapping is completely transparent
to the program.
Caches: Instruction fetch is assumed to use an infinitely
large cache with no miss penalty. All loads and stores to memory done
by the program use a data cache. Cache hits are serviced in a single
cycle, with no processor stalls. Cache misses cause roughly 100 cycles
of processor stalling. The data cache is direct-mapped and physically
tagged, with 4 cache lines, and a 256 byte block size, for a total of
1024 bytes of cache. However, the data cache is
partitioned, with the first 2 lines used to cache the lower half of
physical memory (the first player's half), and the last 2 lines used to cache
the upper half of physical memory (the second player's half).
Cache Management: The version of MIPS we are using (MIPS-I)
lacks instructions to manage the cache, but we have provided system
calls instead. A House can call
void invalidate(void *ptr);
to remove from the cache any block containing the data pointed to
by ptr
. This only works if the House has access to the
memory in question at the time the call is made. Similarly, when a
House calls
void prefetch(void *ptr);
the cache will start to fetch the block containing the given
address into the cache. The call returns immediately with no stalling,
and roughly 100 cycles later the data will arrive in the cache and be
available for use. This call only works if the House actually has
access to the specified block of memory. For each cache line, there
can be at most one outstanding fetch in progress. Prefetch requests
are ignored if a fetch is already in progress for that line (in this
context, "fetch" means either an earlier prefetch, or a core waiting
on the cache line to fill because of a cache miss), and actual data
fetch requests (e.g. from load/store instructions, rather than
prefetch requests) supersede any prefetch requests that are in
progress. There are additional system calls to read the current cache
tags and the tags for lines that are being fetched. This same
information is also available in the memory mapped
data-structures.
We have provided a header file (described below) containing various
useful macros for accessing your own code and data segments, and those
of your opponent. The header also describes in detail the memory
layout, cache organization, and available system calls.
Pointer arithmetic in C: When performing pointer
arithmetic in C, the compiler implicitly multiplies by the size of the
data type that is pointed to. For instance:
char *byteptr = (char *)0x1000;
byteptr[3] = 0xFF; // store one byte at memory three BYTES after ptr, so address 0x1000+3 = 0x1003
byteptr += 5; // increments pointer by five BYTES, to address 0x1005
int *wordptr = (int *)0x1000;
wordptr[3] = 0xFFFFFFFF; // store one word at memory three WORDS after ptr, so address 0x1000+12 = 0x100c
wordptr += 5; // increments pointer by five WORDS, to address 0x1000+20 = 0x1014
From this, we can see that the following code is almost certainly a
bug (two bugs, in fact), since the first statement advances by 12
cache lines instead of 3 cache lines, and the second statement
advances by 8 cache lines instead of 2 cache lines:
int *ptr = (int *)HOME_DATA_START + 3*CACHE_LINE;
ptr += 2*CACHE_LINE;
To advance by 3 cache lines (first statement) or 2 cache lines
(second statement) when using integer pointers, one could do:
int *ptr = (int *)(HOME_DATA_START + 3*CACHE_LINE);
ptr = (int *)((int)ptr + 2*CACHE_LINE);
Or:
int *ptr = (int *)HOME_DATA_START + (3*CACHE_LINE)/4;
ptr += (2*CACHE_LINE)/4;
Basic Strategy
Design code that makes efficient use of the data cache to fill
memory quickly, and find clever ways to beat your opponents, stop them
from posting their payload
, and interfere with your opponent's
cache usage. And although you cannot directly modify your opponent's
registers, you can modify their call stack and global
variables. Coupled with what you know about exploiting programs, you
may even be able to get your opponent to work for you. At the same
time, you need to be on the lookout for cores from your opponent's
team. Because all of these tasks require processing time and access to
memory, you will need to carefully plan how to coordinate use of these
scarce resources.
To get started, we will supply several example teams that employ
some basic strategies. Their source code can be found in the same
directory as the Cache Wars simulator. The example teams
are:
- noop: The simplest House there is; it does nothing.
- greedy: Fills its own half of memory and the opponent's
half using a simple loop with a random start address.
- taunter: Doesn't try to win, but instead dedicates all its
cores to annoying the opponent by (a) reading and writing
randomly within opponent's half of memory in order to fill
opponent's cache with garbage and (b) overwriting return
addresses on the opponent's stack with random values.
- fbi: Dedicates one core to watching for opponent's
cores, with the other three cooperating to filling its own half
of memory. Catches greedy.
- titfortat: Initially behaves like fbi. But whenever it
catches a opponent's core, it goes on the offensive and tries
to fill up opponent's half of memory. This requires some
inter-core communication through global variables.
Note: these teams do not do a particularly good job making effective use of
the cache. For instance, most write a single byte at a time to memory, and take
only a little care to ensure that their Houses don't compete with each other for
cache lines.
Playing the Game
All of these instructions must be done on the VM or through SSH. For
this project, just as Buffer Overflow, it is particularly
important the work is done through either of these means as system behavior may be different on different systems
git pull
from your repository to get the project 5
codebase.
Inside the p5
directory are two executables, cachewarsHP
and cachevall
,
and a directory house_bots/
. Within house_bots/
should be a Makefile
and the folder src/
. Within src/
, you will
find sample course Houses that are described above. You will code
your own House's tactic within this folder.
Each team should create a single program, written in C and compiled
into a MIPS binary executable. The four cores on a team all share the
same code (though your program can obviously do different things
depending on the core_id
parameter it receives from the
simulator). Going up from the src/
directory
(cd ..
), and typing make
will compile all
the Houses within the src/
directory.
**Important!** By default, your new House will not be optimized
by the compiler. You can (and should) tell the Makefile to compile your
House with optimizations enabled. We highly recommend using the -O3 optimization
flag (the letter "O", not the number "0"). For example, if my House is
named XYZ
, I would add the following line to the Makefile.
FLAGS_XYZ = -O3
We have already included these optimizations in the Makefile for the course Houses,
so you can look at those to make sure you're doing it correctly
In the main directory you will also find cachewarsHP
, the
simulator used to play the game. The simulator cachewarsHP
takes two arguments, the names of the teams in the match, for
example:
$ ./cachewarsHP house_bots/bin/greedy house_bots/bin/fbi
You will also find simple shell script cachevall
which
takes the name of a single team and pits it against every other team
in turn. This lets you compare how one team does in comparison to all
the others:
$ ./cachevall house_bots/bin/greedy house_bots/bin
Compilers don't always produce the code you expect them to, so you
will likely want to read the compiled assembly. As you have seen
before, you can decompile compiled code using objdump:
$ mipsel-linux-objdump -xdl house_bots/bin/greedy
Finally you have two tools at your disposition. First, you will
want to read the cachewarsHP.h
header file in
the house_bots/src
directory. It is the only header file you
should import into your House programs, besides any you might write
yourself, but it is designed to be all you will need. It contains the
basic functions don_cloak
, tip_off_filch
,
retreat
and so on, along with various other system calls
like printf
and rand
. But more importantly, its
comment describes in detail how your program is laid out in memory and
how simulator statistics and other data is mapped into your address
space.
Your second major tool is the cachewarsHP
simulator which
has several useful command line options. Type ./cachewarsHP
with no arguments to see a list.
Getting Started
As with many other 3410 projects, this writeup is quite long and a bit
intimidating at first. However, you don't necessarily need to even
know everything in this writeup to do well on this project (though if you're
aiming to win the 3410 cup, you probably will).
Probably the best place to get started is to look at the greedy bot. Make
sure you understand what it's doing. Generate the MIPS assembly code and check
out what that does. As described above, it's only writing 1 byte at a time - how
could you improve that?
Next, make sure you understand how the cache works, ignoring prefetch and invalidate
for now. You have 4 bots to use - what would be the most efficient method to write such that
you take full advantage of the cache lines?
Now dive into prefetch - how can you use this to reduce the amount of time your cores will
be sitting around doing nothing just waiting to be able to write?
Now start developing a strategy. In no particular order, how can you best play defense
and stop the opponent's cores from writing to your memory? What's the best strategy to write to
your opponents memory? How can you best utilize the spells available to you? What other clever
techniques can you find to come out on top?
Finally, have fun with this project! There's lots of techniques that can be successful, so play
around and get creative, and we'll see you at the tournament!
FAQ
- If I cast a PETRIFICUS_TOTALUS on my opponent's side and I activate it (write to that location in memory), what will happen?
You will be stalled for 1,000,000 cycles.
- If I cast an EXPELLIARMUS and within 100 cycles I cast another one, do the durations overlap or accumulate?
The durations will accumulate, so the duration will increase by 100 cycles.
- I want to access my own stack, or my opponent's stack. How do I know where it is?
To start off, for each core there is a mips_core_data structure which contains an array R. This array stores the content of the registers for that core. Work from there.
- How do we determine what addresses the opponent currently has in the
cache?
Use the rdctag
function to read a cache tag. Check titfortat.c
for an
example of the proper usage.
- What is the policy for coherence between the cache and memory?
-
The cache is write-allocate: If you want to write to an address, it
must be in the cache first (and therefore you suffer a cache miss if it
wasn't in there already).
The cache is write-through: Once a line is in the cache, any writes to it
immediately appear in memory (and therefore immediately increase your
score).
Finally, the cache automatically updates from memory: In particular, if you
have the taunt array in cache, and a new House enters don_cloak mode, the taunt
array in cache updates immediately.
- How should we time our prefetches? How does prefetching work, anyway?
-
It's possible to prefetch too early, such that the line you prefetch
arrives in the cache while you're still working on a different line. In
this case, you'll doubly penalize yourself, as you'll suffer a miss for
the line you're currently accessing, and then miss on the line you meant
to prefetch in the first place. Oops! Don't do that.
If you prefetch slightly late, you only lose the difference. If address
0x01000000 is not in the cache, but you prefetch it, wait 50 cycles, then try
to write to/read from it, you'll still miss but only stall 50 cycles instead of
the usual 100, since 50 of the cycles were alerady taken up by the prefetch.
This is why prefetching is beneficial. If you run the simulator in "very
verbose mode" via simulate -vvvv
, you'll see messages like "upgrades existing
prefetch", and this is the meaning of that message.
On the other hand, if address 0x01000400 is in the cache, you prefetch
0x01000200, then try to read/write 0x01000000, the prefetch is canceled, You
miss 0x01000000, and stall the full 100 cycles, no matter how far along the
prefetch was.
- Can I call prefetch, but continue working on the line currently in the cache?
Of course. prefetch(ptr)
does not automatically call invalidate(ptr)
; that's why they're separate function calls. The line currently in the cache is still valid until the prefetch finishes.
- Since only one prefetch can be in progress for a line at a time, what happens if we call prefetch twice?
-
The earlier one sticks. The writeup states "prefetch requests are ignored if a fetch is already in progress for that line", and in this context "fetch" means either an earlier prefetch or a core waiting on the cache line to fill due to a cache miss.
- What activates a PETRIFICUS_TOTALUS, reading or writing?
-
PETRIFICUS_TOTALUS are triggered when any core attempts to write to a memory location that currently holds the trap byte.
Such an attempt causes the write to fail and the writing core to be stalled for 1,000,000 (STALL_ON_PARALYZED) cycles.
Since the write fails, multiple cores can be trapped at the same memory location.
PETRIFICUS_TOTALUS are not triggered by reading memory.
Examples
Here are some visualizations of some of the example bots competing against each other.
Grading
Your grade for this assignment will have three parts.
- 50 points for designing a House that beats all of the
example teams above every time it plays them.
- 50 points for designing a House that beats several secret
course Houses. These course Houses will use several different
techniques and be of varying difficulty. You should program
defensively for various strategies that you think may arise. If
you beat at least one of the secret course Houses, you are
guaranteed at least 20 points out of the 50.
- Bonus!! for designing one of the top Houses in the 3410
tournament. The tournament will pair your team against others in
series. The overall elimination strategy will be either double
elimination or all-pairs depending on the final plans for the
showdown party.
Good luck!