foreign
[Music]
welcome back to our next talk
uh which will be on what c and c plus
can do and when do you need assembly
this talk will be given by alexander
krizanovsky who is the ceo of tempesta
technologies and the architect of
tempesta fw a high performance open
source linux application delivery
controller
alexander is responsible for the design
and performance of several products in
the areas of network traffic processing
and databases
he designed the core architecture of a
web application firewall
mentioned in the gartner magic quadrant
maria db temporal data tables uh with
that over to you alexander
yeah uh do you see my screen shell
yes
i can go here um
okay okay
so
first first of all
we do a custom software development in
network security and that storage areas
in particular we um from time to time we
face tasks like to develop very fast
lego expressions engine about scaling
data structure on multi-core systems
various performance optimization and so
on so typically we work in
high performance area in network
security and data storages
also we develop our own product investor
w which is a hybrid of gp accelerate and
the firewall one of the main
targets for the project is to be able to
filter a massive
malicious traffic like s70 dos attacks
or web attacks
and
we have
one of the fastest or maybe the fastest
uh hpm parcel and uh so this talk will
be most uh reference to this to
suggestions about hp passing and uh
cryptography interior less handshakes
in our
tasks usually uh performances about most
about algorithms mathematics and so on
but also very important stuff is to uh
creatively and accurately uh
code on the program to make it fast and
optimize it so we do a lot of cnc plus
plus and sometimes we deal with assembly
uh for example if we um if you do a quad
review and you see a functions like is
digit uh you see that there are three
operations involved um
in the function and there's a hackers
delight
uh tricks when you can replace the
condition with only two operations so
uh
it doesn't make sense uh to use a more
sophisticated code uh than this um
when a straightforward code actually not
because modern compilers like gcc on
both the optimization levels are good uh
with such kind of optimization so we can
just
stick on
the simplest version of the code
the next example is let's consider this
uh two variants of
uh function
and um
you might be thinking
that uh both the function are equal or
not and in both of the
cases you are actually right
uh so let's um
let's uh
load
the program into
uh
into
uh compile explorer
and
one
is for clunk
as we see that both the
versions are pretty the same
uh function uh in assembly however if we
compare it with gcc
um let me do this
we see that rgc
um generates a bit different
uh code and it involves rbp
so actually
not always um
not not always
um this is the same code not always
generates the same results for different
compilers
uh
uh let's now
uh see what the
x8664
uh looks like uh first of all this
surprise color architecture means that
we can run multiple instructions in
parallel
uh this out for the executions and also
each instruction is
like if you see assembly code then this
is not the lowest level of the code and
the microphone processor splits
instruction into my corporations
and different instructions have
different latency and throughput latency
means
how how many cycles instruction takes in
dependency chain
and the throughput is how many
selections of the same kind can be run
in parallel
uh to visualize um
the ideas about
uh
modern x 8664 let's uh have a look on
lvm mca
um so this is a call uh why vm uh mca is
levm 2 it works just fine with gcc
and you actually can pass any assembly
code as input from levm
mc
so let's have a look what what it is
uh this report about uh the program
and uh first of all we see that the
dispatch vis for current architecture
this uh maximum six uh micro operations
per cycle and this is problem we see
almost uh six
microbes per cycle this good for
our program also this section
please how many sections per second
leverage are gone
uh this is also not so
bad
uh next we see the
assembly for this particular program uh
doesn't my um this
um it isn't important for now what was
the problem is but now let's observe
some
key characteristics of the program in
this report we see on first
column is how many micro operations are
involved in
in
particular instruction uh instruction
latency and
it's work of food
frankly i don't
trust
that
all the
instruction i have only one mac
operations but uh let's have a look on
latency we see that uh vector
instructions xml this uh
uh
this
uh 16 byte
vector operations
have very large uh latency
and
throughput
isn't bad this is a reciprocal
throughput it means that our transaction
of this kind can be run in parallel
um
okay it's uh
this instruction have more my mic
operations um
anyway
um
let's uh see a
timeline
for the
program let me make a
little
uh
smaller
uh this uh how the instructions are
executed by
uh
which is
are provided by mca
first of all we see that the first 7th
section
starts decoding at the same
time next is time to execute waiting for
execution and execute
here we
see that
this instruction this instruction
as executed are earlier than previous
instructions this
autofocus execution in action
uh however
uh
the instruction retired
return means that uh results of the
instruction are fixed in
final registers the final memory and we
see that all the instructions are always
retired
in
in sequence as instruction appeared in
the program
so uh let's back uh to the slides
uh thanks to out of vote execution we uh
have um
a spectacle attack
and we suspect an attack um
we
the spectral attacks use with um out of
forward execution let's uh uh let's
explore
uh one more example
let me award it in compiler explorer
here it is
let me choose a clank for this
experiment
and uh here we go this uh basic uh clan
captain uh compilation for this problem
this uh what we would expect
uh however in um out of order execution
array lengths might be
not fetched from the memory and the
while uh experience waiting for the
value of a length it might uh try to
speculatively try to execute uh the next
uh statement
so
uh if we long and actually offset is
larger than array lengths then cpu may
might uh store the
uh results of this profession's
instruction in the cpu cache and this um
data may be repeated by nataka
uh so uh to prevent such kind of attacks
we can add
command line options
it's um
line
[Music]
and
now now we have
legend epilogue
and this actually the trick
from the compiler to trick the
cpu
so if it goes
uh to the wrong uh branch then it sees
uh pause and defense which actually
uh clears the all the uh data crashed
uh so such
epiworks uh have a performance cost and
it might cost up to 15
performance this next uh attack which
were revealed couple of years ago is uh
main down and this is about um
page table isolation on the operating
system and this might cost up to 30
percent of uh performance
um
so if you do a code review uh and uh
suppose that performance very important
for you then you might be asking um
as on the early side in this
presentation
uh with the compiler is smart enough to
make uh optimization or not
typically
we can first
check
compiling documents this
document from levm about optimization
passes transformation phases
and
this documentation might give you an
idea what the compiler can do in
principle however
one compiler can do a lot of
optimizations not all of them can be
applied in particular case
and the compiler have
common line options uh providing
optimization information this um
[Music]
subtract of
gcm output about optimized vectorized um
optimizations and several missed uh
optimizations
uh once you have uh report you also
have a source file you have lines and
socks fast so you can have an ideas
which part of your sources are optimized
and not and with which uh strategies
uh also
uh reviewing the
assembly it's always helpful but usually
it's better to do this on last
as the last
try
uh so let's start about particle with
practical examples
about http um the first example is about
http parser
uh http passwords are typically encoded
as a
loop
uh in this slide there's this
while loop on input data and inside the
loop you have a bunch of switch
statements and
uh switch
guns on current state machine state and
input data
uh for nginx we have relatively small
state machine about 84
states however 14 psfw we need much
larger state machine and this magnitude
larger
uh the reason for larger set machine is
because we do a lot of security checks
in our
hp passes so
we
have
more than 900
states now can't pass
so
what compilers can do for such
large state machines
the first one is that we have
optimization of switch this well-known
optimization uh first of all is lookup
table so if your states uh which you use
in switch statements are arranged and
sequential
then your compiler can generate the
hookup
table
so we have a
jump bias
offset
and by the job we define the label where
we need to go so this like a double jump
however since we use uh input data as
i've said uh for jump this code is
vulnerable for spectral attack
uh the next optimization next variant of
switch table optimization is uh binary
search if your
states and switch statements aren't
arranged
and
have a non-consequent values then
compiler have to
fall back to
a binary search between the
labels
actually
modern compilers are smart enough to be
able to recognize the same pattern for
chains of yourself
use f's ifs and we have the same uh
pretty the same
uh code generated for
uh yourself
uh the next thing which we can uh do is
uh just to
replace uh switch statement by
uh go to
uh jumps
um
jcbo
will copy some uh code inside the
uh state machine
and we still need some
uh starting um
starting switch statement just to start
uh the state machine
and we
actually can go
uh faster
uh
she provides us um
labels as values so essentially you can
draw
in c just the same as you do in assembly
just
jump directly to particular
others in your code
so with this optimization we can move uh
significantly faster
so
uh
for pretty large uh
state machines
uh this link to
uh benchmark
uh if we compare uh
state state machines for or for seven or
twenty uh seven states then uh times are
more or less the same for very small
uh
state machines we uh go to given um
after automaton may might be even a bit
slower than
switch driving however for a very large
uh state machine or in this particular
case uh it's twice
uh smallest on our actual state machine
you can
move uh twice faster than a basic
switch driving state machine
uh
the main reason for this is
low um branch misses because we we drew
much lower
code transition
in the loop
then we have a much better
cash
much better characteristics of
cash missiles even uh we have
almost twice
bigger
uh code for go to driving aftermath on
we have uh
twice small number of
cash misses
next thing uh is
how to
how to properly code
a state machine this
clear for
http
uh semantics then uh first we have
hp method next we have uh some
hp headers and after that we have a http
body and we would expect that um
we
well
in in any case we always need to
uh
pass
hpm uh method and after that move to hp
headers so this no sense uh to place
hp um uh method of python after hp
headers so we have uh
we have a fixed sequence of states
however
uh compilers doesn't know about these
requirements about our semantics of
input data so it's um free to reorder
um code in its understanding of
optimization and in our
uh case we saw that
very improbable states uh are placed by
the compiler on the top of the state
machine the top of the set machine is a
interest point for the function and it's
very very hot so we we need to place the
hot
states closer to the beginning of the
function
and the first thing which we can do is
to use
compiler barrier which
prevents
compiler from reordering
however we can
it's not optimal
sorry uh it's not optimal to place
compiler barriers everywhere we want to
let compiler do optimization better and
actually we can
do this
using
using hot
hot labels
so
with um
with the uh hot and cold uh labels for
state machines we can arrange the the
parcel uh to
to make a compiler place particular
labels uh closer to the top of the
function or closer to the bottom of the
function
in this
case we found that
pgo isn't helpful because
profile guided optimization that
arranges your code according to the
profile profile data so if you spend
very little time in
hpm
method passing
and spend more time on your rain passing
than um profile guy that optimization
will place uh your rain passing uh
before the method by passing and that's
wrong because we always have to pass um
hp method before the url
and this um case when uh profile guide
optimization also not helpful because um
it's not aware about the input data
semantics
um
this uh skip it
says about alignment
so
actually
we uh
tried to experiment with uh data
alignment for example this uh checked
access
for example if we
convert a string to
integer this known penalty to access
integer uh non-aggregate integer and in
a very micro benchmark you might see
that almost
more than two times on regular
accessories slower than lignin however
if we try to encode this uh directly in
um
in the past we won't see any performance
improvement and the reason uh for that
uh this actually is that uh anaerobic
access is bit uh faster than alignment
the reason that
the additional code makes the
uh code
larger more sophisticated and
since you need to
align the diet in
every
string comparison the award of such
places around the past and the password
is significant so um the
big bigger code and more
complex code
may make the password slower
next thing is about
optimization uh compiler optimization
this size shows uh difference between o2
and o3
and those three uh adds um
particular flags for
uh optimization level
and not all the flux
uh improves uh performance in that there
are
um
the shown facts which makes the
performance works actually done
better
and we found that for http passer
all three uh generates
volkswagen o2
the
problem
uh
problem options are green and they're
about after vectorization let's
let's dig deeper into after
vectorization after vectorization is
about single instruction multiple data
so if you have uh
computation for example it's on the
uh picture on the slide if we have
uh two arrays of form elements and we
need to
add one race to another we can do this
in a single instruction with multiple
data however instructions while
instruction can operate like up to 32
appearance uh in the time
they're not for free first of all they
require a ligament they also have
additional latency as we saw in mci
output and actually not everything is
after vitalized this good talk from um
an ibm developer about this after
virtualization internals in lvm so if
you're interested about thanos i highly
recommend you to
watch the presentation
um
linux kernel
it's
known as uh optimized
part of
the optimizer software however it does
not use after vectorization
and uh
actually
the canon doesn't uh tries to avoid
single instruction multiple data as
possible
uh actually some code uh which ldm
benefits from uh single search multiple
data does uh use it like crypto api
uh however
uh single search multiple data is
managed by separate
cpu unit as a 14 point unit and it has a
separate contacts
so um
to be able to use uh fpu inside the
kernel uh we need to store
fpu contacts and restore this
optimization for the linux kernel so if
well um the modern user space code
is almost every uh user space poker
which you run is after with the after
vectorizer
so
having that uh cannot trust optimizes
and not to
uh spend resources on saving and
restoring uh fpu state for each uh
contact switch between the user space
and the kernel space and only when you
need to
to use a single structure multiple data
inside the kernel uh we call the kind of
you begin and cannot be you end and they
are actually very costly this
comparison uh between uh
when mem cpi and the meme cpi protected
by kind of pu
are beginning kind of premium end
uh however in team we tried to
play with after vectorization and we had
an idea uh that probably we might
benefit from
um after equalization of hp passer and
you have a look what
was
going on
uh
there are
several
uh documentation about after
vectorization the first one is about gcf
vectorization and also this very good
docs for real vm
uh vm docs are much more readable about
after week civilization stuff
basically we have two types of after
vectorization the first one is loop
after vectorization and the second one
is so for basic block after
vectorization or
slp
also jc provides a different
cost model for after vectorization and
this is
well since
single structure multiple data isn't for
free then compiler uh
lets you choose pc5
uh
how how um whether do you want
um single instruction multiple data in
many cases or not like
how aggressive a single instruction
multiple
after vectorization should behave
um
there are several
requirements for code to be artificially
realizable uh so
first you need uh to
have instructions which are after
vectorizable unique diligent uh you need
no uh data dependence uh between the
code
and preferably to have countable on long
groups however modern compilers can um
kind of after victories actually
uncountable loops
let's
see some examples
uh first of all i have
examples of two programs which are good
to
consider
the first one is
for basic box after exercise this um
simple pattern so if you see that there
are arrays of uniform um uniform
operation so in this case we have
h equal operations on almost equal
operation on the way this almost no uh
data dependency
uh well this um
this actual dependency between
uh different values
but um
in this one we have almost
no dependency
uh
anyway
uh one once which is that you do very
very very similar operations uh in
basic works then you might have ideas as
this code could be
uh after victorianized
let's see um
another example
uh this about loop also in this loop we
have
very similar
uh operations
uh on
number of
appearance so that's also a good
signature for to be artificialized
uh well
so
let's um
let's see or what we want to have with
um after vectorization
uh first of all uh let me to
compile the
basic
basic box
um
uh
so
uh in this um in this comment we i used
uh offline optimization for gc i also
adoptions to see
whether something is optimized and we
see that compiler says that we
have optimization and also i use the
strongest uh consistent uh course model
is unlimited
um in
song let's have a look what we
uh
what um
no
let's um
let's uh compile
first let's compile with uh
um
bb in
different versions
um
so i have two versions of the program
uh the first one is
plain
plain program so we have uh basic
function uh this by the way the
cryptography function and the next uh
program i have a restrict
access and i have a lignite uh hints for
the compiler that
uh the data
passed to the function will be aligned
and let's compare the assembly which
will be generated for both of them
functions
here we go
uh so the first thing which we might
notice is that
um
non-malignant
version generates code with a suffix hue
this move the q u is for an alignment
while
qa is for lignite access
what it means
to understand whether we have some
performance
uh improvement for for the function
let's compare
let's um
see on uh
internal uh documentation from both the
instruction this um made the qa
instruction and we have that on my
architecture skyway we have a latency
six and four put uh
0.5
for
alignment access we have the same data
so basically
this instruction are pretty the same and
we don't win any performance for
from using colligate data
i also checked the different uh
alignment instruction and
basically modern uh inter architectures
um
in most of the instruction uh provides
the same performance
also this almost um
equal instructions for
um research success and in this
particular case it seems we don't
have much uh performance benefit from a
restrict
keyword
that's
back to them
well let's have a look
uh one a couple of more examples
uh fortune to the um
modern couple compiler is also able to
um
uh
uh to optimize uh ship was plus sgl
uh algorithms and in this
particular case i used um
uh i used programs from
this blog post
which is that uh actually
we
we see some
uh some vectorization if we add um
if we want to compile them to
generate vxr2
then we see that um
compiler might generate even uh 32 uh
byte
code from the after vectorization
uh more algorithms of foster which are
vectorizable you can find on this uh
blog post and that's not
all them
uh not all the algorithms are actually
artifactorizable
however
uh with uh clunk this um
uh well i didn't show um
performance for
uh
for for loop
uh but um clunk actually are not able to
uh read uh to make reduce reduction
for
uh memory appearance
um oh no um we
end up
not to use after vectorization for hpm
passer and elliptic of cryptography
for hp pulse we
we have only a small optimization for
uh basic blocks because as we saw the
um
state machine as with uh switch uh
statements or go to drive and don't have
much uh vectorizable uh operations like
operation of the same kind also there
are no small loops which are
vectorizable for
uh
which are vectorizable so hp pulsar is
uh just not the kind of code which can
be utilizable elliptic
cryptography is actually a good
candidate for after utilization and if
you program math in here she postpones
and
typically benefit from
art vectorization however in our case as
well as for other cryptography libraries
the most of the mathematics is written
in already assembly
and the things is that um
we also didn't
uh go with after exterization form of
mathematics because
there's additional latency introduced by
uh some of this single search multiple
data and also we need to uh care about
uh alignment because scanner by default
is a rigorous for eight bytes while for
single selection multiple data we need a
ligament for 52 bytes
um
also the
specific
uh specific
considerations about legacy code for
example if you
might have a old
code which is sc only enable you need to
use with zero update by default
compilers are used with zero
uh
instructions and we can make the code
faster if we uh remove uh visible we can
get up to five performance uh better
uh
now we have
explanation why don't we use after
vectorization
and why we record mathematics in
assembly
uh actually
elliptic off and those are cryptography
used with very long integers
like integers of
two four six maybe more limbs limp is
usually unsigned wonk so for our 256 uh
bits arithmetic we have a volumes uh
four enzymes
foreign from linux but
all the libraries
move from the abstract
mpi representation to
go
always so if you can see the
c function we use with two limb
arithmetic so we have
number a and number b
ah
each of size two limbs and we need to
sum them
you might spend
some time to realize whether the smp add
function is correct because we need to
do uh some uh code with uh carry
uh however if we use assembly we can not
only
make the code
easier
using
carrier
carrier where additional but also we can
avoid
branching in the code also cpus provide
uh additional
uh
additional instruction to parallelize uh
two uh
two
additional chains uh thanks to uh
edx
instruction set
so in assembly we can uh
do much more efficient
uh efficient uh programming the last
thing which i want to to mention
is a problem which we recently faced on
linux system
and if your
program uses
spin locks in user space then you might
see that
if
one thread
acquires the spin lock and another
thread is spinning and waiting for this
spin walk so the waiting thread
uh quickly
uh just um spins in a bathroom loop
and
such processes which just
balance cpu are considered as batch
process buzz
linux cpu scheduler i suppose there are
interactive processors which are needed
sometime just periodically and your
monitoring system
is typically
considered by the system schedule as an
interactive uh process because it's uh
needs a speed timely only from time to
time
so
in this
case we
can use a perscad
time hist
to to
profile the system schedule and in this
in this case we saw that this
performance critical waiting process
which is spinning in
spin lock
and it's uh some point
uh while monitoring uh took the
cpu uh time and wake awakened the
process the process actually uh
received that the cpu time almost
100 milliseconds when it was awakened
and during that time another processes
uh
took place on the cpu uh so if you use
um
uh spin locks in user space in user
space we don't have primition control as
we have on in the candle space then uh
you you can face a huge tail latencies
well um that's
all um
what i had
so probably we have some time for
questions
so
our
in fact we're already over time
alexander there are two questions in the
question section on venulis
it would be good to
address those maybe in the chat
okay i will
thank you very much okay thank you very
much thank you okay everybody so now we
will have the tea break afternoon tea
break and back here
shortly
okay thank you bye thank you