Where do malloc() and free() store allocated sizes and addresses?

This is up to the implementation of the standard library, of course. So your best bet would probably be to dig through the source of the library (glibc is the default on Linux) and see if you can figure it out. It is probably not going to be trivial.

There are lots of ways in which malloc/free can store the size of the memory area. For example, it might be stored just before the area returned by malloc. Or it might be stored in a lookup table elsewhere. Or it might be stored implicitly: some areas might be reserved for specific sizes of allocations.

To find out how the C library in Linux (glibc) does this, get the source code from http://ftp.gnu.org/gnu/glibc/ and look at the malloc/malloc.c file. There is some documentation at the top, and it refers to A Memory Allocator by Doug Lea.