Reference counting question

[OSR_Community_User]

Had a question, though this is not related to Windows
as such. Would appreciate an answer very much, because
it would improve some part of my skills alteast.

If an object needs to be deleted, there are multiple
ways of freeing this object if there is more than one
thread that references it. One way, is to use
reference counting on the object.

As an example, say Object A is something that can be
accessed by multiple threads. Now if we just define a
hold and release function which hands out/releases
reference counts, the one that releases the last
reference frees the object. What if there is also
another requirement that states: References should be
handed out only if the object is say active. If some
external event marked the object inactive, references
should not be handed out. The example in my case is an
IO, and the IO can be say marked inactive because of
an Abort call, and any further references to the IO
should not be handed out to any other thread after the
an abort has been received. Now this means that the
function that hands references should check for the
“state” of the command(which now needs to be
synchronized with the hold and release functions
anywhere the “state” is set) and hand out references
atomically and the release function should indicate
via a return value that the reference count is down to
zero so its time to free the object. Now there are
other conditions also, and this solution starts to get
uglier, because every release is followed by a check
to free. And also making a thread go to sleep to wait
for the reference count to go to zero is not viable,
because of the number of threads that could
potentially sleep in this case. Is there any other
solution that could free these objects when the last
reference is released? One might be garbage
collection, but its not very appealing. I am sure
there will be a better way some of you will be able to
come up with. Any ideas?

---

Do you Yahoo!?
Yahoo! Small Business - Try our new resources site!
http://smallbusiness.yahoo.com/resources/

[Loren_Wilton]

I admit to reading yor post quickly, but I didn’t quite follow why you
changed from having the reference count decrementor stop deleting the object
on zero count, and went to some external method of doing that.

If I could design the object from scratch, I would put all of the holds into
object state. These would then cause the incrementor to refuse to increment
the count, and presumably return some indication that you shouldn’t be
referencing the object.

I don’t see how the decrementor would be affected by holds, unless it was
supposed to keep the object around until all holds had been cleared as well
as the reference count at zero. The trivial way to handle this would be to
have the state setting and clearing functions internally increment the
reference count (regardless of hold state) and then call the decrementor
after the state was set or cleared. This way, if the last hold is cleared
after the last user has decremented the count, the decrementor will delete
the object. (Note that you possibly have to worry about reenterancy here
and the possibility of trying to double-delete the object.)

If the object state MUST be external tot he object for some reason, I’d go
with an object manager or object factory, and have it maintain reference
counts, as well as a list of objects on hold; or maybe a list of all
objects. It can then internally synchronize holds, access permissions, and
object deletion. This could be viewed as a form of garbage collection,
except that it is specific to the object type in question, and is only
activated when the normal deletion path fails for some reason or other.

The object manager approach will require locking for safety. Keeping the
state in the object itself and having it self-delete can probably be
synchronized in most cases simply with an atomic increment and decrement.

Loren

[OSR_Community_User]

Thanks for the quick reply Loren. Response embedded:

— Loren Wilton wrote:
> I admit to reading yor post quickly, but I didn’t
> quite follow why you
> changed from having the reference count decrementor
> stop deleting the object
> on zero count, and went to some external method of
> doing that.

Both of them can actually be combined. Its just that
sometimes, I need to wait for an external event to
happen before I can free the object context. So doing
it in one go is not the way I can go with. Thats why i
need to do the reference counting separate from the
freeing.

> If I could design the object from scratch, I would
> put all of the holds into
> object state. These would then cause the
> incrementor to refuse to increment
> the count, and presumably return some indication
> that you shouldn’t be
> referencing the object.
>
Yes I am doing that already. The return value of the
hold function checks the state and returns an error if
the state does not allow for the hold. So refcnt and
state of the object are tightly coupled.

> I don’t see how the decrementor would be affected by
> holds, unless it was
> supposed to keep the object around until all holds
> had been cleared as well
> as the reference count at zero.
I am confused by this statement. A hold basically
means that the ref cnt has been incremented by 1.

The trivial way to
> handle this would be to
> have the state setting and clearing functions
> internally increment the
> reference count (regardless of hold state) and then
> call the decrementor
> after the state was set or cleared. This way, if
> the last hold is cleared
> after the last user has decremented the count, the
> decrementor will delete
> the object. (Note that you possibly have to worry
> about reenterancy here
> and the possibility of trying to double-delete the
> object.)
The state once set, is not unset in this case atleast.
So its easier in that case. So like if an abort comes
in, the IO is aborted or say timed out. Period. Does
not change.

>
> If the object state MUST be external tot he object
> for some reason, I’d go
> with an object manager or object factory, and have
> it maintain reference
> counts, as well as a list of objects on hold; or
> maybe a list of all
> objects. It can then internally synchronize holds,
> access permissions, and
> object deletion. This could be viewed as a form of
> garbage collection,
> except that it is specific to the object type in
> question, and is only
> activated when the normal deletion path fails for
> some reason or other.
>
> The object manager approach will require locking for
> safety. Keeping the
> state in the object itself and having it self-delete
> can probably be
> synchronized in most cases simply with an atomic
> increment and decrement.
>
The object state does not have to be external, but
releasing the holds has to depend on the state, but at
the same time, it has to not free the object if the
reference count goes down to zero. I have done for now
by not freeing the object if it is waiting for the
external event and doing it later. I think I have
effectively done what you are recommending(i.e. when
you would design it from scratch) but it just means a
lot of states and a lot of state changes in a lot of
places in the code, and state checking in the hold and
release function, which seemed kinda ugly. Was looking
to see if there is a better way?
Could you please explain the object factory in a
little more detail?

> Loren
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as:
> xxxxx@yahoo.com
> To unsubscribe send a blank email to
> xxxxx@lists.osr.com
>

__________________________________
Do you Yahoo!?
Yahoo! Small Business - Try our new resources site!
http://smallbusiness.yahoo.com/resources/

[Loren_Wilton]

Ok. I think I may be missing some key point here, so I can’t claim this
will be exactly on the mark, but it might be close. Let me see how close I
come to understanding:

You have an object. People can reference it. When the last person stops
referencing it, you would like to automatically delete it. However,
sometimes there is some external reason why the thing can’t be deleted just
at that time, and some later external event will allow the final deletion.
When the object is in this strange state, we also want to prohibit anyone
new from trying to reference the object. (But I don’t know if we have to
force existing references to invalid, or if they can be maintained.)

Is that close?

There are several ways to do this. I the simplest method can be handled
completely in the object (if we are speaking in C++ terms), or can be
handled by some accessor functions dedicated to the object, if we are
speaking C.

Let us assume every instance of the object contains two hunks of state:

LONG reference_count;
BOOL broken;

Let us assume some functions:

BOOL ReferenceObject (object *thing)
{
InterlockedIncrement (&thing->reference_count);
if (thing->broken)
{
DereferenceObject (thing);
return FALSE;
}
return TRUE;
}

VOID DereferenceObject (object *thing)
{
if (InterlockedDecrement (&thing->reference_count) == 0)
free (thing);
}

VOID SetBroken (object* thing)
{
if (thing->broken) return; // only break it once!
InterlockedIncrement (&thing->reference_count);
if (thing->broken) // only count once
InterlockedDecrement &(thing->reference_count);
thing->broken = TRUE;
}

VOID UnsetBroken (object *thing)
{
// Once broken it is always broken. This gets called to free the
broken thing.
ASSERT (thing->broken && thing->reference_count == 1);
DereferenceObject (thing);
}

This lets any number of people reference the object while it isn’t broken.
Once it is broken (by calling SetBroken) there can be no new references.
Anyone who is holding a long-term reference needs to look for themselves
occasionally to see if the thing has become broken, and possibly release the
reference at that point. (You probably don’t have any long-term references;
I’m speaking general case.)

The object is always freed automatically when the reference count goes to
zero. To allow the object to be manually freed later when we set it broken,
we increment the reference count when we break it. The non-zero reference
count will prevent it from being freed when the last normal reference
disappears.

When the later event occurs that will allow the object to be freed, we
“unbreak” it, which really only decrements the reference count. Since the
count should have been exactly 1 at this point, this will cause the object
to be freed.

This requires two separate hunks of state in the object; I have the
impression you are using the reference count somehow for both hunks of
state. That won’t work in this method.

If you can only have one hunk of state in the object itself, you will need
to maintain the broken state elsewhere. In that case, I would have a
funciton that breaks the object and adds the object pointer to a list. I
would have a second function that can walk the list looking for a specific
object pointer and remove it from the list and delete the object. I’d have
a third function to handle the normal dereference. It would check if the
object is in the list when the count goes to zero, and if it isn’t, delete
the object right then.

Note all of this requires careful locking; the code above for maintaining
the state in the object requires minimal locking. Note though there is a
potential race condition between the time someone gets a pointer to an
object and the time they get the reference count incremented on the object.
Potentially it could get deleted in that time window!

Loren

[OSR_Community_User]

>> I admit to reading yor post quickly, but I didn’t

> quite follow why you
> changed from having the reference count decrementor
> stop deleting the object
> on zero count, and went to some external method of
> doing that.

Both of them can actually be combined. Its just that
sometimes, I need to wait for an external event to
happen before I can free the object context. So doing
it in one go is not the way I can go with. Thats why i
need to do the reference counting separate from the
freeing.

In this case the “external event” has a reference to the object right?
Once the event happens, it releases its reference to the object, which
then gets deleted as the reference count goes to zero. I also don’t see
the need for an external method of object deletion.

Chuck

[OSR_Community_User]

Mark,
The synchronization object you are describing here exists in the windows
kernel and it is called IO_REMOVE_LOCK.
It’s behavior is very simple:
IoAcquireRemoveLock() increments the reference counter
IoReleaseRemoveLock() decrements the reference counter
IoReleaseRemoveLockAndWait() decrements the reference counter, puts the
object into a state that will fail IoAcquireRemoveLock() and waits until the
reference counter reaches 0.

So every one who uses the object can use IoAcquireRemoveLock() and
IoReleaseRemoveLock() to manage the refernce count and when someone wants to
remove the object (or cancel the IO in your case) he simply calls
IoReleaseRemoveLockAndWait() and when it returns he deletes the object.

This machinsm is widly used in the windows kernel to prevent deletion of
devices that still have IO to complete.

I hope this was what you were looking for,
Shahar

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Mark Lobo
Sent: Wednesday, March 16, 2005 4:21 AM
To: Windows System Software Devs Interest List
Subject: [ntdev] Reference counting question

Had a question, though this is not related to Windows as such. Would
appreciate an answer very much, because it would improve some part of my
skills alteast.

If an object needs to be deleted, there are multiple ways of freeing this
object if there is more than one thread that references it. One way, is to
use reference counting on the object.

As an example, say Object A is something that can be accessed by multiple
threads. Now if we just define a hold and release function which hands
out/releases reference counts, the one that releases the last reference
frees the object. What if there is also another requirement that states:
References should be handed out only if the object is say active. If some
external event marked the object inactive, references should not be handed
out. The example in my case is an IO, and the IO can be say marked inactive
because of an Abort call, and any further references to the IO should not be
handed out to any other thread after the an abort has been received. Now
this means that the function that hands references should check for the
“state” of the command(which now needs to be synchronized with the hold and
release functions anywhere the “state” is set) and hand out references
atomically and the release function should indicate via a return value that
the reference count is down to zero so its time to free the object. Now
there are other conditions also, and this solution starts to get uglier,
because every release is followed by a check to free. And also making a
thread go to sleep to wait for the reference count to go to zero is not
viable, because of the number of threads that could potentially sleep in
this case. Is there any other solution that could free these objects when
the last reference is released? One might be garbage collection, but its not
very appealing. I am sure there will be a better way some of you will be
able to come up with. Any ideas?

---

Do you Yahoo!?
Yahoo! Small Business - Try our new resources site!
http://smallbusiness.yahoo.com/resources/

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@safend.com To unsubscribe
send a blank email to xxxxx@lists.osr.com

[Maxim_S_Shatskih]

I would better hold references on inactive objects too, simpler and
stabler.

Maxim Shatskih, Windows DDK MVP
StorageCraft Corporation
xxxxx@storagecraft.com
http://www.storagecraft.com

----- Original Message -----
From: “Mark Lobo”
To: “Windows System Software Devs Interest List”
Sent: Wednesday, March 16, 2005 5:20 AM
Subject: [ntdev] Reference counting question

>
> Had a question, though this is not related to Windows
> as such. Would appreciate an answer very much, because
> it would improve some part of my skills alteast.
>
> If an object needs to be deleted, there are multiple
> ways of freeing this object if there is more than one
> thread that references it. One way, is to use
> reference counting on the object.
>
> As an example, say Object A is something that can be
> accessed by multiple threads. Now if we just define a
> hold and release function which hands out/releases
> reference counts, the one that releases the last
> reference frees the object. What if there is also
> another requirement that states: References should be
> handed out only if the object is say active. If some
> external event marked the object inactive, references
> should not be handed out. The example in my case is an
> IO, and the IO can be say marked inactive because of
> an Abort call, and any further references to the IO
> should not be handed out to any other thread after the
> an abort has been received. Now this means that the
> function that hands references should check for the
> “state” of the command(which now needs to be
> synchronized with the hold and release functions
> anywhere the “state” is set) and hand out references
> atomically and the release function should indicate
> via a return value that the reference count is down to
> zero so its time to free the object. Now there are
> other conditions also, and this solution starts to get
> uglier, because every release is followed by a check
> to free. And also making a thread go to sleep to wait
> for the reference count to go to zero is not viable,
> because of the number of threads that could
> potentially sleep in this case. Is there any other
> solution that could free these objects when the last
> reference is released? One might be garbage
> collection, but its not very appealing. I am sure
> there will be a better way some of you will be able to
> come up with. Any ideas?
>
>
>
>
>
>
>
> __________________________________
> Do you Yahoo!?
> Yahoo! Small Business - Try our new resources site!
> http://smallbusiness.yahoo.com/resources/
>
> —
> Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@storagecraft.com
> To unsubscribe send a blank email to xxxxx@lists.osr.com

[OSR_Community_User]

Thanks Loren.
Inline text.

— Loren Wilton wrote:

> Ok. I think I may be missing some key point here,
> so I can’t claim this
> will be exactly on the mark, but it might be close.
> Let me see how close I
> come to understanding:
>
> You have an object. People can reference it. When
> the last person stops
> referencing it, you would like to automatically
> delete it. However,
> sometimes there is some external reason why the
> thing can’t be deleted just
> at that time, and some later external event will
> allow the final deletion.
> When the object is in this strange state, we also
> want to prohibit anyone
> new from trying to reference the object. (But I
> don’t know if we have to
> force existing references to invalid, or if they can
> be maintained.)
>
> Is that close?
>
Yes, you got that right Loren.

> There are several ways to do this. I the simplest
> method can be handled
> completely in the object (if we are speaking in C++
> terms), or can be
> handled by some accessor functions dedicated to the
> object, if we are
> speaking C.
>
> Let us assume every instance of the object contains
> two hunks of state:
>
> LONG reference_count;
> BOOL broken;
>
> Let us assume some functions:
>
> BOOL ReferenceObject (object *thing)
> {
> InterlockedIncrement (&thing->reference_count);
> if (thing->broken)
> {
> DereferenceObject (thing);
> return FALSE;
> }
> return TRUE;
> }
>
> VOID DereferenceObject (object thing)
> {
> if (InterlockedDecrement
> (&thing->reference_count) == 0)
> free (thing);
> }
>
> VOID SetBroken (object thing)
> {
> if (thing->broken) return; // only break
> it once!
> InterlockedIncrement (&thing->reference_count);
> if (thing->broken) // only count once
> InterlockedDecrement
> &(thing->reference_count);
> thing->broken = TRUE;
> }
>
> VOID UnsetBroken (object *thing)
> {
> // Once broken it is always broken. This
> gets called to free the
> broken thing.
> ASSERT (thing->broken && thing->reference_count
> == 1);
> DereferenceObject (thing);
> }
>
> This lets any number of people reference the object
> while it isn’t broken.
> Once it is broken (by calling SetBroken) there can
> be no new references.
> Anyone who is holding a long-term reference needs to
> look for themselves
> occasionally to see if the thing has become broken,
> and possibly release the
> reference at that point. (You probably don’t have
> any long-term references;
> I’m speaking general case.)
>
No that doesnt matter, but since the external events
can be many, one broken state doesnt help. I need
multiple brokens. I have used “state” for that though.
So depending on the state, the object is freed. So the
release function frees it ONLY if
1. Ref count is 0
2. State has all the right combination of flags set.

> The object is always freed automatically when the
> reference count goes to
> zero. To allow the object to be manually freed
> later when we set it broken,
> we increment the reference count when we break it.
> The non-zero reference
> count will prevent it from being freed when the last
> normal reference
> disappears.
>

> When the later event occurs that will allow the
> object to be freed, we
> “unbreak” it, which really only decrements the
> reference count. Since the
> count should have been exactly 1 at this point, this
> will cause the object
> to be freed.
>
The broken state is probably cleaner because it means
there is no object lying around with a zero ref count.
The end result is the same.

> This requires two separate hunks of state in the
> object; I have the
> impression you are using the reference count somehow
> for both hunks of
> state. That won’t work in this method.
>
> If you can only have one hunk of state in the object
> itself, you will need
> to maintain the broken state elsewhere. In that
> case, I would have a
> funciton that breaks the object and adds the object
> pointer to a list. I
> would have a second function that can walk the list
> looking for a specific
> object pointer and remove it from the list and
> delete the object. I’d have
> a third function to handle the normal dereference.
> It would check if the
> object is in the list when the count goes to zero,
> and if it isn’t, delete
> the object right then.
>
> Note all of this requires careful locking; the code
> above for maintaining
> the state in the object requires minimal locking.
> Note though there is a
> potential race condition between the time someone
> gets a pointer to an
> object and the time they get the reference count
> incremented on the object.
> Potentially it could get deleted in that time
> window!
>

Yes, the locking is the most important. I did it in a
little different manner(state as opposed to broken)
and was wondering if there was a cleaner way, since it
requires setting states at various places. Broken
state kind of meets it(state in the object, broken for
multiple states, each broken holding one reference)

> Loren
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as:
> xxxxx@yahoo.com
> To unsubscribe send a blank email to
> xxxxx@lists.osr.com
>

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com

[OSR_Community_User]

Loren, on the careful locking scenario, I had a
question.

This object has an init and a deinit function. Outside
of the init function, you add the object to a
list(using a lock of course). Now deiniting and
freeing of the object, as we have discussed, is based
on reference count going to zero. deletion of the
object from the list should presumably be done not in
the deinit function, but independent of that.

Deletion from the list happens when you KNOW the
object is done(in my case its an IO object and I know
its either completed, thats the normal good case), so
I delete from the list there because I set a state
atomically which will cause no references to be handed
out to anyone else(say an abort request) and the call
the release function that decrements ref count and
frees it if zero.

Assume you have an external event which causes u to
walk that list. In this case, the event(the good
normal case described above) that should delete the
object from the list will never happen. The list is
walked using a lock which was used to add objects to
the list. Now the first thing to do while walking the
list is to get a reference to the object being
currently examined. If you get a successful reference,
then you go on, change the state atomically, and
release the object. Now if, for example, while
releasing the reference on object, it is the last
reference(because another thread which was holding one
reference freed it in the meanwhile), the object will
be freed(all conditions are met for the object to be
freed and this is the last reference). Now how do you
delete the object from the queue?
The only way I see is to actually check the reference
count inside the list walking function and delete it
IF it is 1(i.e. the only hold is the list walking
function itself), delete the object off the list, and
call the release function that frees the object, but
it kind of kills the object orientation being followed
w.r.t the object. Any better way to do this?

— Mark Lobo wrote:

> Thanks Loren.
> Inline text.
>
> — Loren Wilton wrote:
>
> > Ok. I think I may be missing some key point here,
> > so I can’t claim this
> > will be exactly on the mark, but it might be
> close.
> > Let me see how close I
> > come to understanding:
> >
> > You have an object. People can reference it.
> When
> > the last person stops
> > referencing it, you would like to automatically
> > delete it. However,
> > sometimes there is some external reason why the
> > thing can’t be deleted just
> > at that time, and some later external event will
> > allow the final deletion.
> > When the object is in this strange state, we also
> > want to prohibit anyone
> > new from trying to reference the object. (But I
> > don’t know if we have to
> > force existing references to invalid, or if they
> can
> > be maintained.)
> >
> > Is that close?
> >
> Yes, you got that right Loren.
>
> > There are several ways to do this. I the simplest
> > method can be handled
> > completely in the object (if we are speaking in
> C++
> > terms), or can be
> > handled by some accessor functions dedicated to
> the
> > object, if we are
> > speaking C.
> >
> > Let us assume every instance of the object
> contains
> > two hunks of state:
> >
> > LONG reference_count;
> > BOOL broken;
> >
> > Let us assume some functions:
> >
> > BOOL ReferenceObject (object *thing)
> > {
> > InterlockedIncrement
> (&thing->reference_count);
> > if (thing->broken)
> > {
> > DereferenceObject (thing);
> > return FALSE;
> > }
> > return TRUE;
> > }
> >
> > VOID DereferenceObject (object thing)
> > {
> > if (InterlockedDecrement
> > (&thing->reference_count) == 0)
> > free (thing);
> > }
> >
> > VOID SetBroken (object thing)
> > {
> > if (thing->broken) return; // only
> break
> > it once!
> > InterlockedIncrement
> (&thing->reference_count);
> > if (thing->broken) // only count once
> > InterlockedDecrement
> > &(thing->reference_count);
> > thing->broken = TRUE;
> > }
> >
> > VOID UnsetBroken (object *thing)
> > {
> > // Once broken it is always broken. This
> > gets called to free the
> > broken thing.
> > ASSERT (thing->broken &&
> thing->reference_count
> > == 1);
> > DereferenceObject (thing);
> > }
> >
> > This lets any number of people reference the
> object
> > while it isn’t broken.
> > Once it is broken (by calling SetBroken) there can
> > be no new references.
> > Anyone who is holding a long-term reference needs
> to
> > look for themselves
> > occasionally to see if the thing has become
> broken,
> > and possibly release the
> > reference at that point. (You probably don’t have
> > any long-term references;
> > I’m speaking general case.)
> >
> No that doesnt matter, but since the external events
> can be many, one broken state doesnt help. I need
> multiple brokens. I have used “state” for that
> though.
> So depending on the state, the object is freed. So
> the
> release function frees it ONLY if
> 1. Ref count is 0
> 2. State has all the right combination of flags set.
>
> > The object is always freed automatically when the
> > reference count goes to
> > zero. To allow the object to be manually freed
> > later when we set it broken,
> > we increment the reference count when we break it.
>
> > The non-zero reference
> > count will prevent it from being freed when the
> last
> > normal reference
> > disappears.
> >
>
> > When the later event occurs that will allow the
> > object to be freed, we
> > “unbreak” it, which really only decrements the
> > reference count. Since the
> > count should have been exactly 1 at this point,
> this
> > will cause the object
> > to be freed.
> >
> The broken state is probably cleaner because it
> means
> there is no object lying around with a zero ref
> count.
> The end result is the same.
>
> > This requires two separate hunks of state in the
> > object; I have the
> > impression you are using the reference count
> somehow
> > for both hunks of
> > state. That won’t work in this method.
> >
> > If you can only have one hunk of state in the
> object
> > itself, you will need
> > to maintain the broken state elsewhere. In that
> > case, I would have a
> > funciton that breaks the object and adds the
> object
> > pointer to a list. I
> > would have a second function that can walk the
> list
> > looking for a specific
> > object pointer and remove it from the list and
> > delete the object. I’d have
> > a third function to handle the normal dereference.
>
> > It would check if the
> > object is in the list when the count goes to zero,
> > and if it isn’t, delete
> > the object right then.
> >
> > Note all of this requires careful locking; the
> code
> > above for maintaining
> > the state in the object requires minimal locking.
> > Note though there is a
> > potential race condition between the time someone
> > gets a pointer to an
> > object and the time they get the reference count
> > incremented on the object.
> > Potentially it could get deleted in that time
> > window!
> >
>
> Yes, the locking is the most important. I did it in
> a
> little different manner(state as opposed to broken)
> and was wondering if there was a cleaner way, since
> it
> requires setting states at various places. Broken
> state kind of meets it(state in the object, broken
> for
> multiple states, each broken holding one reference)
>
> > Loren
> >
> >
>
=== message truncated ===

__________________________________
Do you Yahoo!?
Yahoo! Small Business - Try our new resources site!
http://smallbusiness.yahoo.com/resources/

[OSR_Community_User]

The way I have always done this is that the list has its own reference
to the object which is added upon insertion. Then, when you remove it
from the list, you release that reference.

d

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Mark Lobo
Sent: Wednesday, March 16, 2005 8:40 PM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] Reference counting question

Loren, on the careful locking scenario, I had a
question.

This object has an init and a deinit function. Outside
of the init function, you add the object to a
list(using a lock of course). Now deiniting and
freeing of the object, as we have discussed, is based
on reference count going to zero. deletion of the
object from the list should presumably be done not in
the deinit function, but independent of that.

Deletion from the list happens when you KNOW the
object is done(in my case its an IO object and I know
its either completed, thats the normal good case), so
I delete from the list there because I set a state
atomically which will cause no references to be handed
out to anyone else(say an abort request) and the call
the release function that decrements ref count and
frees it if zero.

Assume you have an external event which causes u to
walk that list. In this case, the event(the good
normal case described above) that should delete the
object from the list will never happen. The list is
walked using a lock which was used to add objects to
the list. Now the first thing to do while walking the
list is to get a reference to the object being
currently examined. If you get a successful reference,
then you go on, change the state atomically, and
release the object. Now if, for example, while
releasing the reference on object, it is the last
reference(because another thread which was holding one
reference freed it in the meanwhile), the object will
be freed(all conditions are met for the object to be
freed and this is the last reference). Now how do you
delete the object from the queue?
The only way I see is to actually check the reference
count inside the list walking function and delete it
IF it is 1(i.e. the only hold is the list walking
function itself), delete the object off the list, and
call the release function that frees the object, but
it kind of kills the object orientation being followed
w.r.t the object. Any better way to do this?

— Mark Lobo wrote:

> Thanks Loren.
> Inline text.
>
> — Loren Wilton wrote:
>
> > Ok. I think I may be missing some key point here,
> > so I can’t claim this
> > will be exactly on the mark, but it might be
> close.
> > Let me see how close I
> > come to understanding:
> >
> > You have an object. People can reference it.
> When
> > the last person stops
> > referencing it, you would like to automatically
> > delete it. However,
> > sometimes there is some external reason why the
> > thing can’t be deleted just
> > at that time, and some later external event will
> > allow the final deletion.
> > When the object is in this strange state, we also
> > want to prohibit anyone
> > new from trying to reference the object. (But I
> > don’t know if we have to
> > force existing references to invalid, or if they
> can
> > be maintained.)
> >
> > Is that close?
> >
> Yes, you got that right Loren.
>
> > There are several ways to do this. I the simplest
> > method can be handled
> > completely in the object (if we are speaking in
> C++
> > terms), or can be
> > handled by some accessor functions dedicated to
> the
> > object, if we are
> > speaking C.
> >
> > Let us assume every instance of the object
> contains
> > two hunks of state:
> >
> > LONG reference_count;
> > BOOL broken;
> >
> > Let us assume some functions:
> >
> > BOOL ReferenceObject (object *thing)
> > {
> > InterlockedIncrement
> (&thing->reference_count);
> > if (thing->broken)
> > {
> > DereferenceObject (thing);
> > return FALSE;
> > }
> > return TRUE;
> > }
> >
> > VOID DereferenceObject (object thing)
> > {
> > if (InterlockedDecrement
> > (&thing->reference_count) == 0)
> > free (thing);
> > }
> >
> > VOID SetBroken (object thing)
> > {
> > if (thing->broken) return; // only
> break
> > it once!
> > InterlockedIncrement
> (&thing->reference_count);
> > if (thing->broken) // only count once
> > InterlockedDecrement
> > &(thing->reference_count);
> > thing->broken = TRUE;
> > }
> >
> > VOID UnsetBroken (object *thing)
> > {
> > // Once broken it is always broken. This
> > gets called to free the
> > broken thing.
> > ASSERT (thing->broken &&
> thing->reference_count
> > == 1);
> > DereferenceObject (thing);
> > }
> >
> > This lets any number of people reference the
> object
> > while it isn’t broken.
> > Once it is broken (by calling SetBroken) there can
> > be no new references.
> > Anyone who is holding a long-term reference needs
> to
> > look for themselves
> > occasionally to see if the thing has become
> broken,
> > and possibly release the
> > reference at that point. (You probably don’t have
> > any long-term references;
> > I’m speaking general case.)
> >
> No that doesnt matter, but since the external events
> can be many, one broken state doesnt help. I need
> multiple brokens. I have used “state” for that
> though.
> So depending on the state, the object is freed. So
> the
> release function frees it ONLY if
> 1. Ref count is 0
> 2. State has all the right combination of flags set.
>
> > The object is always freed automatically when the
> > reference count goes to
> > zero. To allow the object to be manually freed
> > later when we set it broken,
> > we increment the reference count when we break it.
>
> > The non-zero reference
> > count will prevent it from being freed when the
> last
> > normal reference
> > disappears.
> >
>
> > When the later event occurs that will allow the
> > object to be freed, we
> > “unbreak” it, which really only decrements the
> > reference count. Since the
> > count should have been exactly 1 at this point,
> this
> > will cause the object
> > to be freed.
> >
> The broken state is probably cleaner because it
> means
> there is no object lying around with a zero ref
> count.
> The end result is the same.
>
> > This requires two separate hunks of state in the
> > object; I have the
> > impression you are using the reference count
> somehow
> > for both hunks of
> > state. That won’t work in this method.
> >
> > If you can only have one hunk of state in the
> object
> > itself, you will need
> > to maintain the broken state elsewhere. In that
> > case, I would have a
> > funciton that breaks the object and adds the
> object
> > pointer to a list. I
> > would have a second function that can walk the
> list
> > looking for a specific
> > object pointer and remove it from the list and
> > delete the object. I’d have
> > a third function to handle the normal dereference.
>
> > It would check if the
> > object is in the list when the count goes to zero,
> > and if it isn’t, delete
> > the object right then.
> >
> > Note all of this requires careful locking; the
> code
> > above for maintaining
> > the state in the object requires minimal locking.
> > Note though there is a
> > potential race condition between the time someone
> > gets a pointer to an
> > object and the time they get the reference count
> > incremented on the object.
> > Potentially it could get deleted in that time
> > window!
> >
>
> Yes, the locking is the most important. I did it in
> a
> little different manner(state as opposed to broken)
> and was wondering if there was a cleaner way, since
> it
> requires setting states at various places. Broken
> state kind of meets it(state in the object, broken
> for
> multiple states, each broken holding one reference)
>
> > Loren
> >
> >
>
=== message truncated ===

__________________________________
Do you Yahoo!?
Yahoo! Small Business - Try our new resources site!
http://smallbusiness.yahoo.com/resources/

—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@windows.microsoft.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

[Loren_Wilton]

> Yes, the locking is the most important. I did it in a

little different manner(state as opposed to broken)
and was wondering if there was a cleaner way, since it
requires setting states at various places. Broken
state kind of meets it(state in the object, broken for
multiple states, each broken holding one reference)

I may possibly be misunderstanding your ‘states’ here, but I see two
possible ways to deal with this that don’t really change my suggested
method:

enum states
{
ok = 0,
bad1,
bad2,
etc
}

union {
ulong state;
struct {
bad1 :1,
bad2 : 1,
bad3 : 1,
etc
};
}

In the enum case the bad states are mutually exclusive, but there are many
of them. However, any value other than 0 is ‘bad’ as far as the allocator
is concerned.

In the second case there are 32 possible simultaneous bad states, and again,
anything other than 0 for the union of all of the flags is bad for the
allocator.

All you would need to do would be to modify the SetBroken method to take a
‘why’ parameter. Or make a handful of specific functions that set explicit
case values.

In either case they would still increment the reference count, and
decrementing it after the wait would eventually free the item.

Loren

[OSR_Community_User]

The bit field is nice for clarity, but it has unintended side affects in
terms of code generation. A set in each field actually results in
retrieving the entire ULONG, OR in the bit (or clearing it on set to
zero) and then setting entire value back in the ULONG. That means that
each field access is not atomic. The end result is that using a bit fit
field like this is only safe if you synchronize access around get
field’s set with a common lock (ie a spinlock or KEVENT, what is
applicable).

If I were implementing your design requirements, I would have a
KSPIN_LOCK to synchronize access to both the refcount and state
variable. This way you can safely manipulate the count and then change
state in an atomic fashion. This also eliminates the need for using
InterlockedXxx operations when updating the refcount.

d

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Loren Wilton
Sent: Wednesday, March 16, 2005 9:32 PM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] Reference counting question

Yes, the locking is the most important. I did it in a
little different manner(state as opposed to broken)
and was wondering if there was a cleaner way, since it
requires setting states at various places. Broken
state kind of meets it(state in the object, broken for
multiple states, each broken holding one reference)

I may possibly be misunderstanding your ‘states’ here, but I see two
possible ways to deal with this that don’t really change my suggested
method:

enum states
{
ok = 0,
bad1,
bad2,
etc
}

union {
ulong state;
struct {
bad1 :1,
bad2 : 1,
bad3 : 1,
etc
};
}

In the enum case the bad states are mutually exclusive, but there are
many
of them. However, any value other than 0 is ‘bad’ as far as the
allocator
is concerned.

In the second case there are 32 possible simultaneous bad states, and
again,
anything other than 0 for the union of all of the flags is bad for the
allocator.

All you would need to do would be to modify the SetBroken method to take
a
‘why’ parameter. Or make a handful of specific functions that set
explicit
case values.

In either case they would still increment the reference count, and
decrementing it after the wait would eventually free the item.

Loren

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@windows.microsoft.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

[Loren_Wilton]

There are of course a lot of ways to do this, and what follows is off the
top of my head design, so might have a hole in it; although I hope not.

If you have an object manager (as you have) then I think I’d have object
manager functions to allocate, free, and break the object. I think I would
have at least two lists, one for valid objects, and one for broken but
unfreed objects.

I think in the object I would have a reference count and a broken flag.
Even if you have multiple reasons for the object being broken, you may only
need a single flag in the object. You could have all of them there if
someone might care why the object is broken. On more thought, you don’t
neven need the broken state, unless someone really cares what it is. The
manager doesn’t need this information himself.

The manager’s allocate function would invent a new object and add it to the
object list, using a lock to add the pointer to the list, but doing the
allocation unlocked first. (Rely on the memory manager to do its own
locking, observing the general rule of holding as few locks as possible at
any time.)

People who have the object pointer would be able to operate on it directly.

People inquiring about the object would go thru an object manager lookup
function, which would reference the object list and return the object
pointer. This may or may not require grabbing the list lock, depending on
how you design things. The reference function would cause the reference
count in the object to be incremented. Note that object creatrion itself
probably increments the reference count.

Someone wanting to break an object would look it up in the normal way (thus
proving that it exists in the object list) and then call the manager’s
break-object function. This function will move the object from the first
list to the second list. It will also set the broken flag in the object, or
call an object routine to set the broken flag. (Doing that may not be
necessary.) It will also increment the reference count in the object. The
list movement would be under the list lock. Note that the initial lookup on
the object can be performed by the break-object function (it will have to do
it anyway) and the function can return an error if the object isn’t found.

All further references to the object will fail, since it is no longer in the
main object list. No special code for checking broken is required.
Existing referrers can still work, since they still have a pointer to the
object.

People that grow tired of talking to an object would call the object
manager’s dereference-object function, passing the pointer. The manager
will call the decrement use count function in the object. If the count goes
to zero the object will return a flag indicating that it is unreferenced.
If the return indicates that the object is unreferenced, the manager will
lock the lists, and delink the object from the appropriate list. Then after
releasing the lock, it will free the object, or call an object routine to
free the object.

Doing things in this order, memory management is never done when the list
lock is owned. Also, the object is not being deleted while it is still in
the list, and the forward link could become corrupt. Things are fairly
clean since referencing and dereferencing are done through the object
manager that owns the object list(s).

Diddling the state in the object can be done directly by the manager or by
object reference functions. I’d probably have the manager do it directly in
C (noting in the object defintion comments that these fields are used
directly by the manager), and probably do it with object functions in C++,
unless it was time-critical.

The only requirement here is that someone knows that they have to delete the
broken objects eventually. I think you had some case where broken objects
could be deleted immediately, but I;ve forgotten exactly what it was.
Hopefully it is fairly obvious where that would fit above.

Loren

[Loren_Wilton]

> The bit field is nice for clarity, but it has unintended side affects in

terms of code generation. A set in each field actually results in
retrieving the entire ULONG, OR in the bit (or clearing it on set to
zero) and then setting entire value back in the ULONG. That means that
each field access is not atomic. The end result is that using a bit fit
field like this is only safe if you synchronize access around get
field’s set with a common lock (ie a spinlock or KEVENT, what is
applicable).

If I were implementing your design requirements, I would have a
KSPIN_LOCK to synchronize access to both the refcount and state
variable. This way you can safely manipulate the count and then change
state in an atomic fashion. This also eliminates the need for using
InterlockedXxx operations when updating the refcount.

Good points and absolutely true; I should have pointed out that non-atomic
problem myself.

It actually can be done atomically on an X86 machine using a lock-bitset or
lock-bitreset op pair. However, like all interlocked ops, this takes a
cache hit in many architectures, and should be avoided as much as possible
in any critical path. I think in this case the VC++ compiler is actually
smart enough to generate the bitset or bitreset op to fiddle the bit (if you
use a constant state). But it doesn’t know about the lock prefix, so the
action isn’t atomic even though it is a single instruciton.

Loren

[OSR_Community_User]

Doron,
But in this case, its the same problem, isnt it.
Inside of the list walking function on an external
event that requires checking to see if the list can be
cleanedup , we call the release funcion, right? But
how does that help? We still have to manually, in the
list walking context, check if the ref count is
correct to delete it from the list or not. So doesnt
the problem still stay: i.e. how do I delete the
object from the list while walking the list itself to
say mark all objects with a certain state because of a
certain external event?

For example:
ObjHold(){
lock object
if condition{
refcnt++
unlock object
return true
}

unlock object
return false;
}

ObjRelease(){
lock object
refcnt –
if condition{
unlock object
ObjDeinit
ObjFree
return;
}
unlock object

}

ObjAddToList()
{
Locklist
add
unlocklist
}

ObjDeleteFromList()
{
Locklist
delete
unlocklist
}

markobjsinlist{
Locklist
get reference
Set object state /* This state causes no more ref to
be handed out */
// Now here we need to check to see if the object
// is GOING to be freed
lock object
if refcnt == 1
delete object from list
unlock object
release reference(which should free object)
unlocklist
}

Now there is a flaw with the logic above that if
someone ELSE is holding a reference to this while the
list is being walked, who deletes the object from the
list? Also the above way of deletion, to be simply
put is very ugly. I hope I was clear with my question?

— Doron Holan wrote:

> The way I have always done this is that the list has
> its own reference
> to the object which is added upon insertion. Then,
> when you remove it
> from the list, you release that reference.
>
> d
>
> -----Original Message-----
> From: xxxxx@lists.osr.com
> [mailto:xxxxx@lists.osr.com] On Behalf
> Of Mark Lobo
> Sent: Wednesday, March 16, 2005 8:40 PM
> To: Windows System Software Devs Interest List
> Subject: Re: [ntdev] Reference counting question
>
>
> Loren, on the careful locking scenario, I had a
> question.
>
> This object has an init and a deinit function.
> Outside
> of the init function, you add the object to a
> list(using a lock of course). Now deiniting and
> freeing of the object, as we have discussed, is
> based
> on reference count going to zero. deletion of the
> object from the list should presumably be done not
> in
> the deinit function, but independent of that.
>
> Deletion from the list happens when you KNOW the
> object is done(in my case its an IO object and I
> know
> its either completed, thats the normal good case),
> so
> I delete from the list there because I set a state
> atomically which will cause no references to be
> handed
> out to anyone else(say an abort request) and the
> call
> the release function that decrements ref count and
> frees it if zero.
>
> Assume you have an external event which causes u to
> walk that list. In this case, the event(the good
> normal case described above) that should delete the
> object from the list will never happen. The list is
> walked using a lock which was used to add objects to
> the list. Now the first thing to do while walking
> the
> list is to get a reference to the object being
> currently examined. If you get a successful
> reference,
> then you go on, change the state atomically, and
> release the object. Now if, for example, while
> releasing the reference on object, it is the last
> reference(because another thread which was holding
> one
> reference freed it in the meanwhile), the object
> will
> be freed(all conditions are met for the object to be
> freed and this is the last reference). Now how do
> you
> delete the object from the queue?
> The only way I see is to actually check the
> reference
> count inside the list walking function and delete it
> IF it is 1(i.e. the only hold is the list walking
> function itself), delete the object off the list,
> and
> call the release function that frees the object, but
> it kind of kills the object orientation being
> followed
> w.r.t the object. Any better way to do this?
>
>
> — Mark Lobo wrote:
>
> > Thanks Loren.
> > Inline text.
> >
> > — Loren Wilton wrote:
> >
> > > Ok. I think I may be missing some key point
> here,
> > > so I can’t claim this
> > > will be exactly on the mark, but it might be
> > close.
> > > Let me see how close I
> > > come to understanding:
> > >
> > > You have an object. People can reference it.
> > When
> > > the last person stops
> > > referencing it, you would like to automatically
> > > delete it. However,
> > > sometimes there is some external reason why the
> > > thing can’t be deleted just
> > > at that time, and some later external event will
> > > allow the final deletion.
> > > When the object is in this strange state, we
> also
> > > want to prohibit anyone
> > > new from trying to reference the object. (But I
> > > don’t know if we have to
> > > force existing references to invalid, or if they
> > can
> > > be maintained.)
> > >
> > > Is that close?
> > >
> > Yes, you got that right Loren.
> >
> > > There are several ways to do this. I the
> simplest
> > > method can be handled
> > > completely in the object (if we are speaking in
> > C++
> > > terms), or can be
> > > handled by some accessor functions dedicated to
> > the
> > > object, if we are
> > > speaking C.
> > >
> > > Let us assume every instance of the object
> > contains
> > > two hunks of state:
> > >
> > > LONG reference_count;
> > > BOOL broken;
> > >
> > > Let us assume some functions:
> > >
> > > BOOL ReferenceObject (object *thing)
> > > {
> > > InterlockedIncrement
> > (&thing->reference_count);
> > > if (thing->broken)
> > > {
> > > DereferenceObject (thing);
> > > return FALSE;
> > > }
> > > return TRUE;
> > > }
> > >
> > > VOID DereferenceObject (object thing)
> > > {
> > > if (InterlockedDecrement
> > > (&thing->reference_count) == 0)
> > > free (thing);
> > > }
> > >
> > > VOID SetBroken (object thing)
> > > {
> > > if (thing->broken) return; // only
> > break
> > > it once!
> > > InterlockedIncrement
> > (&thing->reference_count);
> > > if (thing->broken) // only count once
> > > InterlockedDecrement
> > > &(thing->reference_count);
> > > thing->broken = TRUE;
> > > }
> > >
> > > VOID UnsetBroken (object *thing)
> > > {
> > > // Once broken it is always broken. This
> > > gets called to free the
> > > broken thing.
> > > ASSERT (thing->broken &&
> > thing->reference_count
> > > == 1);
> > > DereferenceObject (thing);
> > > }
> > >
> > > This lets any number of people reference the
> > object
> > > while it isn’t broken.
> > > Once it is broken (by calling SetBroken) there
> can
> > > be no new references.
> > > Anyone who is holding a long-term reference
> needs
> > to
> > > look for themselves
> > > occasionally to see if the thing has become
> > broken,
> > > and possibly release the
> > > reference at that point. (You probably don’t
> have
> > > any long-term references;
> > > I’m speaking general case.)
> > >
> > No that doesnt matter, but since the external
> events
> > can be many, one broken state doesnt help. I need
> > multiple brokens. I have used “state” for that
> > though.
> > So depending on the state, the object is freed. So
>
=== message truncated ===

__________________________________
Do you Yahoo!?
Yahoo! Small Business - Try our new resources site!
http://smallbusiness.yahoo.com/resources/