It isn't listed in the article, but I wrote about this in my blog also: http://blog.reverberate.org/2013/05/deep-wizardry-stack-unwi...

What's the simplified explanation how perf uses CPU performance counters to know what functions are called. I mean, what kind of book-keeping is going on that allows it to map instructions executed to symbols (functions) called?

Perf uses hardware performance counters to interrupt on some instructions and records their program counter: http://stackoverflow.com/questions/28661430/how-does-a-syste.... It uses symbol lists from ELF files to find functions for every recorded program counter (http://www.brendangregg.com/perf.html#Symbols), like nm (https://sourceware.org/binutils/docs/binutils/nm.html), and can also use debugging information to get source file names and lines like addr2line (https://sourceware.org/binutils/docs/binutils/addr2line.html).