Re: root in managed heap - C# Discussion Boards

Well what's the point of this forum? I have a book on PHP yet I still ask a lot of PHP questions at phpfreaks.com

Hi George,

these are all starting points when a GC scans for reachable objects:
- the root of the heap (or every heap if there are many holding managed objects)
- the current stack pointer for every thread in the process
- the CPU registers (holding data for the current thread, unless the GC itself is
running in a thread, so the current thread does not belong to the process of interest)

From each of these everything that could be a reference needs to be followed, just like
a web crawler would do when you give it one or more URLs.

Every object that one does not find with the above is declared dead and can be collected;
doing it this way avoids any problems with cyclic references (A holds ref to B, and B holds
ref to A; both are dead if the above algorithm never leads to either A or B).

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.

Thanks Luc,

1.

Luc Pattyn wrote:
the root of the heap (or every heap if there are many holding managed objects)

Sorry, I am confused, GC scans from the root of the heap (I thin it should scan from lowest address of the heap to the highest address of the heap), and scans for what? You only mentioned from where, but never mentioned what to do. Smile | :)

2.

Luc Pattyn wrote:
the current stack pointer for every thread in the process

Confusion the same as in (1) -- scan from current stack pointer to do what? Do you mean from the current stack pointer to scan for all available stack local variables?

regards,
George

Hi George,

1.
I was inaccurate for the heap; most systems use a variation of this scheme:
- stop all threads;
- walk the heap ONLY to mark all objects as dead;
- then perform the algorithm based on the thread stacks (and CPU registers),
marking the live objects as not-dead (see below);
- resume all threads;
- walk the heap to delete all objects that are still marked dead.
There are different schemes (e.g. for better real-time behavior, not really a Windows thing),
for better performance (with generations, implemented in MS .NET), etc. Some are completely
different (e.g. based on reference counts, which is very hard to get right
in cyclic situations). The last step (delete) can be delegated to another (low-prio)
thread.

2.
stack is easy: for each new thread the stack pointer is initialized to some value ("stack
base") and every time something gets pushed onto the stack, the pointer moves away from
that base (either up or down, depends on the CPU architecture).
So the GC will search the stack from its current position towards the stack base,
and threat every 4 or 8 bytes as a potential reference. If it falls outside the heaps,
if is definitely not a reference, hence it gets skipped. If it falls inside the range
of one of the heaps, some extra fields are checked, and if they match it is considered
an object, hence marked alive.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.

Thanks Luc,

Sorry I have a stupid and basic question. Threads are of different stacks, right? Means different stack pointer and stack base (not only for .Net threads, but also Windows native threads)?

regards,
George

Of course, each thread needs its own stack, since threads can be switched in and out
at (almost) any point during their execution, so they must keep their call chain information
independent of each other.

Therefore the kernel will unload and reload all the CPU registers, including the
stack pointer, when switching from one thread to another.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.

Thanks Luc,

I read your points before again. Your approach of checking whether an object is live or not in heap is to check whether there are any reference from stack.

I agree but I am not sure whether it is enough in general situations. Why you do not check whether there are reference from not only stack variable, but also from heap variable -- to decide whether an object is live or not? Smile | :)

--------------------
I was inaccurate for the heap; most systems use a variation of this scheme:
- stop all threads;
- walk the heap ONLY to mark all objects as dead;
- then perform the algorithm based on the thread stacks (and CPU registers),
marking the live objects as not-dead (see below);
- resume all threads;
- walk the heap to delete all objects that are still marked dead.
There are different schemes (e.g. for better real-time behavior, not really a Windows thing),
for better performance (with generations, implemented in MS .NET), etc. Some are completely
different (e.g. based on reference counts, which is very hard to get right
in cyclic situations). The last step (delete) can be delegated to another (low-prio)
thread.
--------------------

regards,
George

Hi George,

an object is alive if there is a (theoretical) probability that one of the process threads
will touch the object. Now where is a thread's knowledge about objects? it is in the data
it knows to access, i.e. the stack (containing stack frames from earlier methods that lead
to the invocation of the current method, and containing local variables for the current
method). It is not in other data, the thread would not know how to find other data, remember
there is no such thing as global variables in OO, so everything the thread is supposed to
work on must be given to it or created by it.

Of course, as soon as an object A is marked "alive", all its data members must also be
inspected; object A could contain references to other objects B, C, ... and being alive itself,
those would automatically be alive too.
Example: a local variable of type List may be passed in as an argument to a method,
and the List may contain any number of Control objects; each of those Controls in turn
would have names, texts, fonts, whatever.

Typical app example: a windows app starting up has one thread, no objects (apart from the
command line args that are passed to static main). It creates a new MyForm
then passes it to Application.Run to make it visible and give it a message pump.
The form may create new threads and pass parameters to them, etc. So new objects get
created and most of the time somehow linked to existing objects through the class members
of MyForm and others.

But there is no magic way to keep objects alive; if none of the threads has any reference
to a specific object, then none of them will be able to touch it ever again, hence the
object is dead.
Well actually there are some methods such as GC.KeepAlive() to mark objects for special cases,
e.g. when the managed world wants to pass an object to unmanaged (native) code and wants
to object to stay alive even when the managed side no longer holds a reference to it.

Final remark: the cyclic reference example I gave earlier (A holds ref to B, B holds ref to A,
none of the threads knows about the existence of A and B, hence both A and B are dead)
proves that you cannot simply walk the heap and decide about live and dead for objects,
since doing so would keep A and B alive no matter what.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.

Hi Luc,

Your reply is great! However I do not fully agree with two more comments.

1.

Luc Pattyn wrote:
there is no such thing as global variables in OO

We can have global/static variables in C#. I think such kinds of variables are exception to your thread-touched live rule. Means, those global/static variables will always live from process begin to process ends. Any comments?

2.

Luc Pattyn wrote:
proves that you cannot simply walk the heap and decide about live and dead for objects,
since doing so would keep A and B alive no matter what.

I do not agree. I think we can still prove A and B are dead since we can not touch them from any threads. Why do you think we can not prove anything? Smile | :)

regards,
George

Hi George,

1.
yes, static data members of a class are globals once the class got loaded, and as such
they remain alive as long as the class does; which is as long as the AppDomain does where
the class got loaded; which is until you unload the AppDomain. (By default there is just
the one AppDomain, and you may not even be aware of it).
So, yes, all these static members form another base for the GC the look for live objects.
I see you are getting the picture quite well.

2.
if you were to try and prove the island formed by objects A and B is reachable/unreachable
(and hence alive/dead), you would have to build the entire reference graph and study its
connectivity. If you find several loose groups, you would still have to find out which
groups are reachable (from the stack and the globals) and which are not. Simply looking
at four objects interconnected two-by-two (i.e. A---B and C---D) cannot possibly tell
you which group is alive or dead. So there is nothing much to be gained by studying the
heap itself.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.

Thanks Luc,

1.

In your sample before,

--------------------
Final remark: the cyclic reference example I gave earlier (A holds ref to B, B holds ref to A,
none of the threads knows about the existence of A and B, hence both A and B are dead)
--------------------

Do you mean we can not identify whether A and B are live or not? Why we can not identify? I think from your algorithm, at the beginning, mark all objects as dead, then if no variables refer A or B, they will be dead. It is easy to jusge live and dead in the situation you mentioned above, why you think we can not judge?

2.

In C# all the variables must be wrapped in class {}, so it is why you think there is no global variable in C# -- all belong to class context?

regards,
George

Hi George,

you somehow misunderstood a few things.

1.
the algorithm I described will perfectly judge live/dead on a A---B cluster.
What I said or meant to say is it would not be sufficient to just look at the objects
themselves, you really need to start looking from the known world i.e. stacks and globals.

2.
a class is not an object, a class is not alive; it is either loaded and initialized, or not.
As soon as the class got initialized all static members that have initializers have been
created and are alive (until the class, hence AppDomain, gets removed).

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.

Thanks Luc,

Two more comments. Smile | :)

1.

Luc Pattyn wrote:
1.
the algorithm I described will perfectly judge live/dead on a A---B cluster.
What I said or meant to say is it would not be sufficient to just look at the objects
themselves, you really need to start looking from the known world i.e. stacks and globals.

I understand your points now. Your points are, we should not just look at the object themselves, but also whether there are live stack/static variables refer to them, right?

If yes, I think from your algoriothm, cyclic referenced dead variables could be detected, since no one refers to either A or B, right?

2.

Luc Pattyn wrote:
2.
a class is not an object, a class is not alive; it is either loaded and initialized, or not.
As soon as the class got initialized all static members that have initializers have been
created and are alive (until the class, hence AppDomain, gets removed).

Sorry, I have not made my question clear. My points is, all the variables in C# must be defined into class brackets -- { and }, e.g. we can not define a variable outside class brackets into namespace brackets directly, right?

regards,
George

Hi George,

yes to all.
there are no variables in a namespace, just types (classes, structs, ...)
all variables are inside classes, i.e. when non-static they are inside an object (= an instance
of that class); and when static they are "global" i.e. they are not inside another object,
so you access them (if public) with classnmame.varname so you don't need a reference to
anything, just names.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.

Cool, Luc.

So, the conclusion for this dicussion is, roots (or say, object instances pointed by rules) must be live. Right? Smile | :)

regards,
George

Hi all,

I want to use FileStream.Read method to read a file but I want it in such a way that I will read a chunk of the whole file instead of reading it all at once.

For instance, I want to read 1KB of data (out of the 1MB), and say do something to that 1KB then proceed to the next 1KB.

Please advise. Thanks! Smile | :)

It is said that the most complex structures built by mankind are software systems. This is not generally appreciated because most people cannot see them. Maybe that's a good thing because if we saw them as buildings, we'd deem many of them unsafe.

huh?! FileStream.Read works exactly like that! Did you even look at the documentation?
"Reads a block of bytes from the stream and writes the data in a given buffer."

Work @ Network integrated solutions | Flickr | A practical use of the MVC pattern

Woops, yeah, I've looked at the documentation at MSDN. I've figured it out eventually. Smile | :)

It is said that the most complex structures built by mankind are software systems. This is not generally appreciated because most people cannot see them. Maybe that's a good thing because if we saw them as buildings, we'd deem many of them unsafe.

I have a class called Category which extends ToolStripMenuItem. It also overrides ToolStripMenuItem' ToString method via "new public string ToString () {}". I have an array of Categories and I add them to the combobox: this.cmb_categories.Items.AddRange (categories);

But when I show the form there's two items in the list like there should be but there's no text. I also have a button, that when click calls the ToString method of the selected category but I keep getting a NullReferenceException. I've tried calling Update(), Invalidate(), PerformLayout () and Refresh () on the combo box but it's not working. I've also tried switching from .Net 3.5 to .Net 2.0 but that's not working either.

Jordanwb wrote:
It also overrides ToolStripMenuItem' ToString method via "new public string ToString () {}".

That is a contradiction, it is either override or new. And it seems you want override.
Have it return a constant (say return "aha";) to convince yourself it gets called.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.

Tried "public override string ToString ()" and it doesn't work either. Still wouldn't explain the NullReferenceException.

The NullRefExc has nothing to do with the .NET version, it indicates there is a bug in
your code. Either single-step through it, or look at the Exception.ToString() output
to pinpoint the exact line that causes it.

And publish the Exception as well as (the relevant parts of) your code here if you want
detailed help.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.

I'm no longer getting the NullReferenceException for some strange reason, but if I use "new public string ToString ()" or "public override string ToString ()", text isn't showing up in the ComboBox.

I need to see some code in order to have a chance helping you any further.
Did you single-step the relevant code? did you look at intermediate results?

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.

Okee Dokey.

Category class (irrelevant code ommitted)

<code>
public class Category : ToolStripMenuItem
{
public Category(int id, string name)
{
this.id = id;
this.Text = name;

this.sub_items = new List<Program>();
}

public override string ToString()
{
return this.Text;
}
}
</code>

Where I add the Categories to the ComboBox:

<code>
public partial class RemoveCategory : Form
{
public RemoveCategory(AccessReader database, HashMap<int, Category> categories)
{
InitializeComponent();

this.database = database;
this.categories = categories;

this.cmb_categories.Items.AddRange(categories.ToArray());
this.cmb_categories.SelectedIndex = 0;
}
}
</code>

The HashMap class is a class that I made that maps a key (in this case int) to a value (in this case Category), the ToArray() method returns an array of Categories that contain all the values in the HashMap. In the callback for when the button is clicked, the SelectedItem property of the ComboBox is no long returning null but is returning an object which is casted into a Category.