33

I was reading a bit about garbage collectors and I am wondering if the garbage collector of a program scans the entire heap memory or what is allocated to it? If it reads the entire system memory, does it mean it is reading memory locations that are used by other applications? I understand that this does not make much sense security or performance wise.

If garbage collector only reads the memory that is allocated to it, how does it mark those areas?

Sorry for the rookie question, I am not a software engineer and this is pure out of my curiosity

4
  • 19
    In modern OSs, applications are isolated. It is usually not allowed for an application to touch other app's memory space. And I don't see why GC would want to touch other app's memory space.
    – Euphoric
    Aug 15 at 19:24
  • 3
    This presentation is old and Java-specific but I recommend it if you are serious about understanding GC: infoq.com/presentations/Understanding-Java-Garbage-Collection
    – JimmyJames
    Aug 15 at 20:31
  • 4
    This might be implementation specific and e.g. differ in Java and C#. Also, "entire memory" is a vague term, because it's not clear whether you understood the difference between physical RAM and virtual memory. Also, virtual memory will still not be scanned entirely: the C# GC will not scan the "native" memory like C++ allocated memory. Aug 16 at 17:20
  • What heap? If you mean the GCs own internal heap then yes, it scans the whole heap where it allocated objects in, eventually. If you mean what the C runtime calls heap then no. The GC scans only those parts of memory that it manages. Aug 17 at 13:48

7 Answers 7

58

I was reading a bit about garbage collectors and I am wondering if the garbage collector of a program scans the entire heap memory or what is allocated to it?

That depends on the garbage collector. There are many different kinds of garbage collectors.

For example, Reference Counting Garbage Collectors don't "scan" anything at all! In a Reference Counting Garbage Collector, the system counts references to objects, something like this:

SomeObject foo = new SomeObject();

Let's say, this new object was allocated at memory address 42. The GC records "there is 1 reference to the object at address 42".

SomeObject bar = foo;

Now, the GC records "there are 2 references to the object at address 42".

foo = null;

Now, the GC records "there is 1 reference to the object at address 42".

bar = null;

Now, the GC says "there are 0 references to the object at address 42, therefore, I can collect it".

At no point did the GC "scan" anything.

What you are probably thinking about is an extremely simplistic implementation of a so-called "Tracing Garbage Collector", namely the Mark-and-Sweep GC.

Any Tracing GC starts off with a set of objects that they know are always reachable. This is called the root set. The root set typically includes all global variables, the local variables, CPU registers, the stack, and some other stuff. For all of these objects, the GC looks at the instance variables and checks the objects that the instance variables point to. Then it checks those objects' instance variables, and so on and so forth.

This way, the GC "sees" all "live" objects, i.e. the objects that are reachable from the root set. What the GC does with those "live" objects depends on the kind of GC.

As I mentioned above, what you are thinking of is the most simplistic kind of Tracing GC, which is the Mark-and-Sweep GC. During the tracing phase I described above, the GC will "mark" all live objects by either setting a flag directly in the object header itself, or in a separate data structure.

Then, the GC will indeed "scan" the entire memory and find all objects and do one of two things:

  • If the object is marked, remove the mark.
  • If the object is unmarked, de-allocate the object.

After this "sweep" phase, you end up with all unreachable objects destroyed and all live objects unmarked, ready for the next "mark" phase.

But, as I mentioned, this is only one of many different kinds of Tracing GCs, and is a very simple one with many disadvantages. The two major disadvantages are that scanning the entire memory is expensive and leaving the live objects where they are and only collecting the dead objects in between leads to memory fragmentation.

Another very simple but much faster Tracing GC is Henry Baker's Semi-Space GC. The Semi-Space GC "wastes" half of the available memory, but gains a lot of performance for it. The way the Semi-Space GC works is that it divides the available memory into two halves, let's call them A and B. Only one of the two halves is active at any one time, meaning new objects only get allocated in one of the two halves.

We start out with half A: The GC "traces" the "live" objects just as described above, but instead of "marking" them, it copies them to half B. That way, once the "tracing" phase is done, there is no need to scan the entire memory anymore. We know that all live objects are in half B, so we can simply forget about half A completely. From now on, all new objects are allocated in half B. Until the next garbage collection cycle, when all live objects are copied to half A, and we forget about half B.

These are just two examples of Tracing GCs, and only one of those two scans the entire memory.

If it reads the entire system memory, does it mean it is reading memory locations that are used by other applications? I understand that this does not make much sense security or performance wise.

This is simply impossible. No modern Operating System allows a process to read another process's memory. (And when I say "modern", I mean "since the 1960s or so".)

But even if it were possible, it would not make sense. If the memory belongs to another process, then the GC has no idea what the objects that are in this memory even look like. But it needs to know what the objects look like in order to find all the instance variables and to know how to interpret those references. If it uses an internal marker flag inside the object itself, it also needs to know how to find that marker flag and how to set it. And that is assuming that the marker flag is even there at all! What happens if the application that owns that memory doesn't use marker flags?

Or, worse: what happens if the application that owns that memory does use a GC which uses marker flags. Now, the one GC is overwriting the other GC's markers!

If garbage collector only reads the memory that is allocated to it, how does it mark those areas?

There are two popular approaches.

The first approach is that there is flag in the object header of each object reserved for marking. During the "mark" phase, the GC sets this flag. The major advantage of this approach is that there is no separate bookkeeping involved and it is thus very simple: the mark is right there on the object itself. The major disadvantage is that objects are scattered all through the memory, and thus during the marking phase, the GC writes all over the entire memory. This means that there are "dirty" pages all over memory, in a multiprocessor system (which almost all systems are nowadays) this means that we have to notify the other CPU cores that we have modified some memory, we have polluted the cache with tons of writes that we will never need again, and so on.

The alternative is to keep a separate data structure where we keep a table of all marked objects. This has the disadvantage of more bookkeeping (we need to keep a relationship between the mark table and the objects) but it has the major advantage that we are only writing to one place in memory, which means we can keep this one piece of data in the cache all the time.

But again, not all GCs even have a concept of "marking" at all.

29
  • 6
    "Then, the GC will indeed "scan" the entire memory and find all objects." This is not really true or necessary. There's nothing to be done about 'dead' objects unless there was some sort of hook to notify about it's 'death'. Also, I consider reference counting to be much more simplistic than mark-sweep. I grant that it can be more performant but it's unable to guarantee all 'garbage' is freed.
    – JimmyJames
    Aug 15 at 20:22
  • 5
    The "Mark-and-Sweep GC" also has one advantage over simple reference counting: It removes objects with circular references, that are otherwise not referenced anywhere. Imagine a parent object having a reference to a child object, and vice versa. If both parent and child lose all external references, a simple ref counter GC would still mark them alive, since they reference each other. A Mark-and-Sweep GC would find no path from the root to the objects, and would delete them. (Note that weakrefs would solve this)
    – MechMK1
    Aug 16 at 11:24
  • 4
    Of course operating systems allow reading the memory of other processes. Not as a matter of course, but for instance the win32 debugging functions let you do just that. I think what you mean is there's no way for this to happen by accident.
    – Cubic
    Aug 16 at 12:08
  • 3
    @MasonWheeler My understanding is that the standard CPython runtime uses reference counting primarily with a generational collector as a backup to catch cycles. The combination is pretty pragmatic and performant. Cycles are relatively rare in most applications.
    – JimmyJames
    Aug 16 at 20:22
  • 3
    @MasonWheeler it may be down to the specific definition you use for GC, but Python has this to say: "The main garbage collection algorithm used by CPython is reference counting." so they consider it a GC. And you can disable the automated cycle counter and run it on demand, which will make it completely temporally deterministic.
    – Davidmh
    Aug 17 at 11:11
13

There are a lot of details in garbage collection. Lots lots lots lots lots. Each one of them has different behaviors, so it's hard to cover everything.

Garbage collectors almost universally scan the memory within a single process. This is for two natural reasons. One is that garbage collection is always closely tied to how the memory is laid out, and thus language-specific. The second is that the OS won't let you read someone else's memory anyway (without special steps).

The most naïve solutions for garbage collection do indeed look at everything in the process's memory, but that's obviously slow. Faster solutions do exist. The most common is a "generational" garbage collector. It has been observed that most objects have a very short lifespan, so putting young objects in a "nursery" lets you quickly reclaim memory as efficiently as possible. With a generational garbage collector, one only scans all of memory when one has to (when doing the shorter cheaper scan isn't sufficient).

There are also lots of clever tricks to avoid scanning extra memory. One of them is "card marking." Whenever a reference is updated, the language sets a bit on a "card," which is just an array in memory. During a garbage collection, only cards that have been marked could possibly have changed what they were referring to, so you can avoid scanning all of the data managed by the unmarked cards.

But don't think those are the only approaches. We've come up with countless different ways to do garbage collection, each with their own pros and cons.

0
9

No garbage collector scans the entire memory. Because, when reading some random memory content, it is not possible to guess if it's used or not. So garbage collection goes through objects or list of objects that were previously allocated and created to see if they are still used.

Most of the GC algorithms belong to the more general family of marking algorithms: very naively, objects referenced in variables that are still alive are marked as used. The marking is then propagated to all the related objects, and so on until there is no new object to be marked. The unmarked objects can then be discarded. The marking usually takes the form of a flag or a counter in some technical data that describes each object. The marking and cleaning can be done at once, or incrementally, or at every referencing/dereferencing.

But this is very simplified, and a book would not be sufficient to describe all the existing object management strategies and the garbage collection algorithms (not to speak of the more than 700 patents on the topic, e.g. this one). But here already a compact overview.

9

Top-level, GC is specific to the application. It doesn't really make much sense for a Python application to be scanning a Java application's memory space, even if it was allowed to do so. Also, not all memory in a system is 'heap'.

Broadly, while there are many different approaches and strategies to garbage collection, we can generalize. Without getting into the weeds of GC algorithms, the idea that it's scanning even the entire memory space that it's allocated is a little off. In a mark-sweep-compact, the approach is to start from 'roots' that are inherent to the application and look at everything that they point to and then everything those point to, and everything those point to, etc. until all 'live' objects are found. That's the 'marking' phase. Everything that's not marked is considered garbage. The live objects are then moved around in a way similar to defragmenting a disk drive and the remaining heap is then considered free space.

In a way, I think the term garbage-collection is a bit of a misnomer. The point of GC is really about keeping track of what is still in use, not really finding garbage, or 'collecting' it. A good example of this is the copy-collector approach. In that design, you keep 2 (or more) spaces where new objects (structures, whatever) are allocated. When on of the spaces fills up, the live objects are identified (see paragraph above) and copied to the other 'side' which becomes the new area for allocation. Nothing specific is done with the 'garbage'; it is simply forgotten and the memory that it occupied is used for new allocations. There are some minor caveats to that but at a high level, there's really no 'collecting' of unused memory, it's just being tracked as available for use.

0

Your program, including the garbage collector, will not be able to access memory belonging to other processes unless you have a totally ancient OS. Plus the garbage collector has no reason at all to look at the memory of other processes.

In a primitive garbage collector, every chunk of memory is identified as “free”, “examined” or “used”. The garbage collector marks everything that isn’t “free” as “examined”, then systematically turns memory that can be accessed from “examined” to “used”, and when there is nothing left to mark “used”, everything “examined” is marked “free”.

Now a garbage collector is used a lot for example by any Java program, so it is a prime target for optimisation, and to use any trick in the book to make it run faster. Not visiting all memory if avoidable would help, so a good garbage collector will try to avoid it.

0

The Garbage collector needs to know which part of memory is a pointer (and how it is encoded), and what spans of the address space are effectively allocated. Those informations are known only to the application or its virtual machine.

Therefore, a GC can't scan the whole memory. If the GC is VM-based, it could effectively span multiple applications, provided they share a common address space. For security reason, it is rarely the case.

As for marking, there are multiple ways to achieve that (bitmap, position-size table, etc). It depends on the GC implementation and the memory-manager of the language or VM.

-1

A garbage collector only need to scan the memory which have been actively allocated by the program. It does not need to scan unused memory or memory used by other processes on the system.

When heap memory is allocated, e.g by malloc in C or new Foo() in Java, the language runtime keeps track of what memory areas has been allocated. In its simplest form, it just keeps a list of the memory regions with start and end addresses. (Ideally there is only a single region which grows when new memory is allocated, but since memory can be freed in the middle of a region, you end up with multiple regions over time)

A mark-and-sweep garbage collector scans the stack for pointers and then recursively follows these pointers and mark all objects it meets. Then it scans the allocated memory, and if some allocated objects have not been marked, the memory is freed.

So even a naive mark-and-sweep garbage collector only need to scan the memory which have been actively allocated by the program at some point.

4
  • "Then it scans the allocated memory, and if some allocated objects have not been marked, the memory is freed." What is the purpose of 'scanning' for dead objects here? There are two scenarios for free memory: it was never used or it isn't being used anymore. In either case, it's free. Once you know where the live allocations are, the free space is simply the complement of that.
    – JimmyJames
    Aug 17 at 18:34
  • @JimmyJames: Depending on the language, the GC might need to call destructors on the objects before freeing the memory.
    – JacquesB
    Aug 17 at 18:41
  • 1
    Sure but that's a extremely naive and inefficient approach unless you have a very small allocation space. If you have one object with a destructor (or some other hook on it's collection), looking through the entire allocation space for them is like the GC equivalent of bubblesort. It's far more efficient to keep list of objects or just objects with these 'hooks' and again, once you have the set of live object, the dead ones are simply the complement of that.
    – JimmyJames
    Aug 17 at 18:51
  • @JimmyJames Yes, what I describe is a naïve mark-and-sweep implementation. GC is a huge area with numerous different algorithms and optimizations available.
    – JacquesB
    Aug 18 at 5:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.