How do pointers stay valid when objects move in memory?

Question

Imagine in C I allocate two structs on the heap. One of the structs has a field which holds a pointer to the other struct.

As far as I know, data in the heap may move, thus addresses of things change. For example, defragmentation on the heap may occur, moving the second struct to a different place in the heap.

This help understanding what I'm talking about https://en.m.wikibooks.org/wiki/Memory_Management/Memory_Compacting

The point to this struct would now be wrong (i.e. holding the wrong memory address).

I don't mean this question as specific to C, but more general: at any time, the platform may decide to move things around. How do pointers stay valid?

Answer 1

The key concept here is virtual memory. Your pointers do not point to a physical address, but rather to a virtual one in the virtual address space of your process. What you said is correct, data may get moved around, even swapped out to disk and then mapped again into the physical memory onto another frame, but the virtual address that your pointer points to stays always the same.

Answer 2

The C standard does not permit the implementation to (spontaneously) move things around in such a way that would invalidate an existing pointer. It's possible that an implementation could exist that does "defragment" the heap, but I don't know of any implementations that do.

I said "spontaneously" because realloc() calls in your code may actually cause the object to move; that's why realloc returns a pointer. If the pointer returned by realloc is different from the original pointer, the original pointer (and any pointers that aliased it) are invalid. But this is something you have to keep track of in your own code.

Managed languages (Java, C#, Python, whatever) may (or may not) deal with heap fragmentation by adding an additional level of indirection and/or keeping track of pointers into the heap. That way the language runtime can update all the pointers to object X when X moves to a different place. That would be taken care of by the garbage collection system.

It would be somewhat unusual for a C implementation to provide a garbage collector, and probably can't be done in a standards conformant way due to all the things you can (safely) do with pointers. So the premise of your question, that the heap may be spontaneously defragmented by the implementation, is not valid.