How do pointers remain valid when objects move in memory?

Question

Imagine that in C, I allocate two structures on the heap. One of the structures has a field that contains a pointer to another structure.

As far as I know, the data on the heap can move around, so the addresses of things change. For example, defragmentation can occur on the heap, moving the second structure to another location on the heap.

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

Now the point in this structure will be incorrect (i.e. hold the wrong memory address).

I do not mean this question, specific to C, but more general: at any moment the platform can decide to move things. How do pointers work?

Answer 1

The key concept is virtual memory . Your pointers do not point to a physical address, but rather virtual to the virtual address space of your process. What you said is correct, data can be moved, even replaced by a disk, and then displayed again in physical memory on a different frame, but the virtual address pointed to by your pointer always remains unchanged.

Answer 2

When you see a pointer to C, you observe something similar to a memory address, but in practice there will be one, if not two levels of abstraction between this and the physical memory address.

This not only increases the security of operating systems, but also allows you to perform any fragmentation tasks (regardless of what they are), without changing what is observed in your C program.

Answer 3

The C standard does not allow an implementation to (spontaneously) move things in such a way as to invalidate an existing pointer. Perhaps there is an implementation that defragments the bunch, but I don't know any implementations that do.

I said "spontaneously" because calls to realloc() in your code can make the object move; therefore realloc returns a pointer. If the pointer returned by realloc is different from the original pointer, the original pointer (and any pointers that have its aliases) are invalid. But this is what you need to track in your own code.

Managed languages ​​(Java, C #, Python, independently) can (or cannot) handle heap fragmentation, adding an extra level of indirection and / or tracking pointers to the heap. Thus, the language runtime can update all pointers to an object X when X moves to another location. This will be taken care of by the garbage collection system.

It would be unusual if the C implementation provided a garbage collector and probably could not be executed in the standard way because of all the things you can (safely) do with pointers. Thus, the premise of your question that the heap may be defragmented by the implementation is invalid.