I understand the Heap memory divisions such as Young, tenured and Perm Gen. But I'm just curious from where is the memory used for performing the Garbage Collector itself? Is it from any of these memory spaces or in the thread stacks ?
The answer depends on what you mean by "the memory used for performing the Garbage Collect[ion]" ... and what garbage collector you are talking about.
The general answer is that different garbage collection algorithms use space differently. This is a very high level / simplified summary:
Just about all garbage collectors make use of one or more "mark" bits in each object's header to record that the object has been processed by the GC.
Copying collectors work by copying live objects from a "from" space to a "to" space, and in the simple case don't need any extra space.
Mark / sweep collectors work by recursively walking the graph of "reachable" objects. The recursion can be done explicitly (which requires a separate stack), or by means of a clever pointer-reversal trick (look up Cheney's algorithm).
Concurrent collectors typically require extra memory to track objects that get mutated while the garbage collector is running.
There are whole books on the topic of garbage collection. If you want to really understand how garbage collectors work under the hood, you've got a lot of reading to do.
In general, any additional memory that the GC needs to do its job will typically be allocated outside of the live heap spaces. Thread stack memory is not used ... apart from the thread stack for the garbage collection thread or threads themselves.
Your mention of "young", "tenured" and "permgen" suggests that you are talking about classical Java GCs. These are generational collectors, which is a subtype of copying collectors.
Garbage Collectors perform a search of the program's heap from its GC Roots in order to identify what is live.
There's a cunning trick that you can perform when undertaking this task that avoids requiring any stack memory at all for the traversal. When doing a DFS at any given node you need to know what your predecessor node was, so your invert the pointers within the heap structure itself. For example, if your heap looks like this:
A -> B
B -> C
B -> D
And you search from A, to B, to C. You invert the pointers, so they'll look like this:
B -> A
C -> B
B -> D
That way when doing a garbage collection you can walk a graph of arbitrary size, whilst only needing a constant amount of memory to do so. You only need two pointers in memory in order to walk any graph: One to reference your current node, and one for siblings.
Its a pretty neat trick.
Because Java was designed around the idea of having a virtual machine, there really isn't a single, correct answer for this question.
The only certainty is that the VM will implement the instruction set correctly. There are two JVM instructions,
newarray, that allocate space for objects and arrays. Anything beyond that is an implementation detail which is intended to remain hidden.
malloc() answer probably holds true in most implementations for POSIX-y environments (Unix, Windows, VxWorks, etc.), where the usual practice is for dynamically-allocated memory to be put on the host system's heap. Nothing in the JVM spec precludes implementations in other environments with other memory models:
The Java virtual machine assumes no particular type of automatic storage management system, and the storage management technique may be chosen according to the implementor's system requirements.
As long as the JVM implements something that appears to the Java program as a heap, all is good. The spec does explicitly state that there must be garbage collection, and on a hypothetical host with infinite memory, it would be completely unnecessary.
Any memory the GC itself needs to operate is either stack memory (for temporary computations it does), or from the "raw" heap, that is using the system
malloc, or manually calling