Before I begin, please disregard whether compaction would even be viable inside AVR. I am just brainstorming here.
Assume a heap that has fragmented memory. I want to compact all live objects. I would first compact live objects in terms of physical address, and then update reference pointers. It is this second step that I am trying to work out here.
Firstly, to even identify a live object, we'll need some sort of mark-algorithm. Assume we have perfect garbage collection and any dereferenced pointers are immediately removed. My idea was to maintain an array of pointers, where every newly allocated object is added to this array. This array would then hold all live objects. In order to access these objects, you must go through this array as the root stack pointers just point to these array pointers.
Then when the memory is physically compacted, the array pointers are updated to their new address. This array could be stored in a reserved area that won't be compacted itself (possibly between the heap and the .bss segment).
How realistic is this array in terms of size? Would my math be correct in saying you'd need (heap size/pointer size) number of array values? Have I just misunderstood how pointers work (very possible)?