Distinguishing pointers and data on the heap is the first problem any garbage collector needs to solve. The GC needs to follow pointers in order to discover live objects.
Broadly speaking, there are two approaches to identifying references vs. non-references:
Metadata that tells you whether a variable is a reference variable or otherwise. This metadata will also tell you where the variable is, whether in a register for some duration, or in a memory location. Such metadata is generated during code generation. Generally speaking, the code generated will be done conscious of the need for this metadata, and this can have some minor affects on the register and memory location choices so that the metadata is not overly complex. Still, all the info that the identifier of the object roots needs is to know whether each memory location is a pointer or not, wherever a method is suspended (e.g. at call sites, suspend on the stack).
Guessing, which is accomplished by looking at the values to see if they might be in the range of the garbage collected heap. Such an approach, in order to be correct, must be conservative, so assuming certain values as being pointers even if they might not be. Such an approach might be found in approaches to garbage collection for C/C++ (yes, they exist!) where the compiler isn't known to help, and we have to worry about integers that hold pointers. This would probably not be used for other languages that are more designed to support the metadata approach. (Also note that guessing precludes compaction as we cannot risk to modify integers that look like pointers.)
As long as we can identify what class an object comes from, we can find all of its pointers.
In garbage collected runtimes, we will often find that the object model prescribes that the first slot of the object is a vtable pointer or other class reference. Such a reference is basically hidden from the user, though used to perform casts, virtual method calls, find interfaces, and locate references within the object.
The garbage collector works in two phases: the mark phase, and the sweep phase. In the mark phase, the garbage collector starts walks object references in order to find objects that are still reachable. The garbage collector starts at a few basic places where the object references are stored and given names (the stack, and global storage, and static storage), and then traverses references in the objects.
Certain references are seen as live roots, so anything these roots reach (or could reach) is live, and should be considered live and thus not be collected. The roots constitute all threads (i.e. their stacks, aka activations, aka stack frames), and also all static/global variables. The metadata we're taking about above describes stack frames, and static/global variables.
I don't see how you can traverse objects, and know that it is ready to be garbage collected or not. Any tips on understanding that part would be of help
We don't: any traversed objects are necessarily considered live. The trick then is to identify the objects that are not traversed from the latest traversal that starts at these roots. Thus, the objects are tagged as live, or unknown/dead. (During traversal we have live vs. unvisited, and post traversal we have live vs. dead.) Sometimes the bit for this tag is stolen from the vtable or class pointer in the first slot, since there are (generally broadly speaking) bits that should always be zero at the LSB of such pointers (the pointers then have to be used more carefully). During the trace, objects that are known to be reachable are marked as such, while objects that are not remain unmodified.
You might think that all objects would need to be marked as unreachable first, in order to identify the ones that are not reached, and yet most GC algorithms don't call out this initialization, though this is because there is a trick that can be used which is to reverse the sense of this live/unknown bit on every GC collection traversal: thus the visited nodes are marked "1" on one GC collection (and the ones marked "0" are collected as garbage) while on the next collection, we use "0" to mark the reachable ones, and the unreachable ones still hold "1" from the prior collection.
You can see from this that it is necessary to be able to find the remaining untraversed objects, which can be done by traversing the heap in memory order, given that typically object models prescribe that each object has a vtable reference or class pointer in the first slot, so you can easily tell how large the object is and thus where the next object is located sequentially in the gc heap.
Even in the case where metadata identifies roots, used as the start of live objects (traversal), these roots may be conservative in the sense that some of the roots might not actually be used later on. So, while in a metadata oriented approach we know for sure whether a variable is a reference or not, we don't really know if the variable will or will not be used later in the algorithm of the code (i.e. the threads). In this sense there is some conservatism in this approach. Some compiler/optimization approaches (e.g. incorporated into the metadata) can reduce the window of potential liveness, such that even though some variables may still hold a reference it is known not to be used, for example, after the last use of the variable even if its storage location still holds a reference.
