Can anyone explain to me how valgrind works exactly? I mean, how does it know when memory is leaking, allocated and freed?
Valgrind basically runs your application in a "sandbox." While running in this sandbox, it is able to insert its own instructions to do advanced debugging and profiling.
From the manual:
Your program is then run on a synthetic CPU provided by the Valgrind core. As new code is executed for the first time, the core hands the code to the selected tool. The tool adds its own instrumentation code to this and hands the result back to the core, which coordinates the continued execution of this instrumented code.
So basically, valgrind provides a virtual processor that executes your application. However, before your application instructions are processed, they are passed to tools (such as memcheck). These tools are kind of like plugins, and they are able to modify your application before it is run on the processor.
The great thing about this approach is that you don't have to modify or relink your program at all to run it in valgrind. It does cause your program to run slower, however valgrind isn't meant to measure performance or run during normal execution of your application, so this isn't really an issue.