A question of programming technique in C - Programming Languages

On Wed, 05 Nov 2008 18:58:39 +0000, Ben Bacarisse
<ben.usenet@bsb.me.uk> wrote:
[color=blue]
>cri@tiac.net (Richard Harter) writes:[/color]
[snip]
[color=blue]
>
>I could not find anything to snip so there it is. Sorry. If I follow
>you, you are making a structure a bit like this:
>
>
> descriptor | locator bobble
> +--------+ | +--------+ +--------+
> | ----+-------->| ----+--------->|internal|
> | id: 34 | | | id: 34 | | data |
> +--------+ | +--------+ +--------+
> |
> user code | internal to the bobble implementation
>
>so that when a bobble is destroyed we get this picture:
>
> descriptor | locator
> +--------+ | +--------+
> | ----+-------->| |
> | id: 34 | | | id: 0 |
> +--------+ | +--------+
>
>so as to be able to detect invalid accesses. I understand that the
>first arrow may not be a pointer but some other kind of reference (you
>suggest an index). What I don't get is why the a more normal "double
>indirect" solution does not work for you:
>
> descriptor | locator bobble
> +--------+ | +--------+ +--------+
> | ----+-------->| ----+--------->|internal|
> +--------+ | +--------+ | data |
> | +--------+
>
>so that when a bobble is deleted, we simply set the second pointer to
>NULL:
>
> descriptor | locator
> +--------+ | +--------+
> | ----+-------->| NULL |
> +--------+ | +--------+
>
>I think everything would be clearer if you could say why this is not
>the right solution for your bobbles. The big advantage is that,
>outside, there is simply a pointer -- and a pointer to an opaque
>object at that.[/color]

Your presentation is very clear, thank you. Of course you could
use a pair of pointers. The problem is that you can never
release the locator unless you can guarantee that there are no
extant descriptors pointing to it. This creates a memory leak.
This may not matter; then again it may. I prefer code that
doesn't have memory leaks.

If that isn't clear, consider an environment in which the number
of bobbles is bounded, but which is continually creating and
deleting bobbles. Over time the number of locators grows
unboundedly.

You can avoid the leak by scanning all descriptors and deleting
all locators that no longer have a reference, but that doesn't
strike me as a sane tactic in C. It would be a different matter
if we were talking about a language with garbage collection but
we're not.


Richard Harter, [email]cri@tiac.net[/email]
[url]http://home.tiac.net/~cri[/url], [url]http://www.varinoma.com[/url]
Save the Earth now!!
It's the only planet with chocolate.

On Wed, 05 Nov 2008 10:36:02 GMT, "Bartc" <bc@freeuk.com> wrote:
[color=blue]
>"Bartc" <bc@freeuk.com> wrote in message
>news:7z5Qk.82734$E41.74102@text.news.virginmedia.com...[color=green]
>> "Richard Harter" <cri@tiac.net> wrote in message
>> news:4910af56.146445250@news.sbtc.net...[color=darkred]
>>>
>>>
>>> Suppose we are writing a program in C and that we have a
>>> particular kind of object (in the sense of OO programming) that I
>>>
>>> will call bobbles. Being well disciplined programmers (Ha!) we
>>> create a module to package our bobble related functions together.[/color]
>>[color=darkred]
>>> I am going to throw in one curve ball. Our program will contain
>>> references to created bobbles; we won't know where these are so
>>> they can go stale when we delete bobbles. The code will need to
>>> be able to detect that a reference has gone stale and deal with
>>> it appropriately.[/color]
>>
>> As I understand this problem: you may have a number of assorted
>> references to an object.
>>
>> These objects may be deleted, and you want to verify that an existing
>> reference still points to an undeleted object.
>>
>> Your idea of using a unique-id sounds reasonable, but, why not just use
>> the reference as the unique id?[/color]
>
>I've tried some ideas with actual code this time.
>
>I managed to get a workable system along the lines you've been discussing,
>but in this case using the serial number as the reference (so no pointers
>involved from the 'user' point of view). The interface seen looks like this:
>
>handle=newobj();
>setobj(handle,value);
>getobj(handle);
>delobj(handle);
>
>The key thing being that the handles must be unique and unrepeated during
>the lifetime of the program.[/color]

Yes, you can do that (using the id as a handle) but then you have
to map the id to the object address; to do that you will need
some sort of data structure to handle the map. At best it will
be costlier than using paired structures.


Richard Harter, [email]cri@tiac.net[/email]
[url]http://home.tiac.net/~cri[/url], [url]http://www.varinoma.com[/url]
Save the Earth now!!
It's the only planet with chocolate.

On Wed, 5 Nov 2008 00:37:50 -0800 (PST), Nick Keighley
<nick_keighley_nospam@hotmail.com> wrote:
[color=blue]
>On 4 Nov, 20:24, c...@tiac.net (Richard Harter) wrote:
>[color=green]
>> Suppose we are writing a program in C and that we have a
>> particular kind of object (in the sense of OO programming) that I
>> will call bobbles. =A0Being well disciplined programmers (Ha!) we
>> create a module to package our bobble related functions together.
>>
>> If we were using an OO based language there would be machinery in
>> place, constructors, destructors, and such like, to handle the
>> details of our module, but in C we have to roll our own.[/color]
>
>I seem to do a fair amount of rolling my own in C++ as well...
>(but then some argue C++ isn't a very good OO language)
>
>[color=green]
>> One of the things we need to do is to create functions that will
>> serve as constructors and destructors. =A0There are two things that
>> we have to take care of, specifying the interface, and writing
>> the function internals. =A0My concern is with specifying the
>> interface.
>>
>> I am going to throw in one curve ball. =A0Our program will contain
>> references to created bobbles; we won't know where these are so
>> they can go stale when we delete bobbles. =A0The code will need to
>> be able to detect that a reference has gone stale and deal with
>> it appropriately.[/color]
>
>I think your design is broken at this point.[/color]

I dare say you think that, but you are wrong to do so. First of
all, it is a requirement rather than design. Secondly it is a
quite normal requirement in an asynchronous message passing
environment with transient entities.
[color=blue]
>This isn't a C
>problem you'd have exactly the same issues with C++ despite
>it's "machinary".[/color]

C++ may will have the same issues; however the question at hand
is how to deal with the problem in C.




Richard Harter, [email]cri@tiac.net[/email]
[url]http://home.tiac.net/~cri[/url], [url]http://www.varinoma.com[/url]
Save the Earth now!!
It's the only planet with chocolate.

On Wed, 5 Nov 2008 00:49:04 -0800 (PST), Nick Keighley
<nick_keighley_nospam@hotmail.com> wrote:
[color=blue]
>On 5 Nov, 00:22, c...@tiac.net (Richard Harter) wrote:[color=green]
>> On Tue, 04 Nov 2008 16:43:49 -0500, Eric Sosman
>> <Eric.Sos...@sun.com> wrote:[color=darkred]
>> >Richard Harter wrote[/color][/color][/color]

[snip]
[color=blue][color=green][color=darkred]
>>>[/color]
>> At time A we create bobble X. =A0Space will be allocated for X as
>> needed, including a struct bobble_s.[/color]
>
>what's the difference between a bobble and a bobble_s?[/color]

Metaphysics. :-)

Presumably we represent a bobble in the software by sundry
storage objects. This can be done in various ways. One way is
to use a master structure that has pointers to auxilliary storage
objects. Bobble_s is the master structure for X; the complete
collection of bits and pieces of X is the storage representation
of X. What X is depends upon your philosophic stance.
[color=blue]
>
>[color=green]
>> At time B we schedule operation zeta to be performed on X at time
>> E. =A0Don't assume that X 'knows' that about the scheduled
>> operation.
>>
>> At time C we delete bobble X. =A0All space is deallocated.[/color]
>
>I'm not sure that'sa good idea. I think you need some sort
>of collection of valid Bobbles (the last big OO project I
>looked at called these Repositories). Operation zeta would be
>given an identifier for X and not a reference to the actual X.
>[color=green]
>> At time D we allocate bobble Y. =A0As it chances, Y has the same
>> address as X.[/color]
>
>but a different identity.
>[color=green]
>> At time E the program attempts to peform the scheduled operation
>> on X. =A0It has to be able to detect that X is no longer there even
>> though there is a bobble around with X's address.[/color]
>
>it asks the repository for X and provides the identifier.
>The repository fails to find X and signals an error.[/color]

Indeed. The issue at hand is designing the machinery for finding
X. In the method I ended up with the array of locator structs
serves as the repository.
[color=blue]
>
>[color=green]
>> Simply hashing the address into an integer won't work because the
>> addresses are the same. =A0Likewise using an opaque pointer doesn't
>> work. =A0That's the point of the "unique id" - it is different for
>> different bobbles even though they have the same address.[/color]
>
>apart from your solution looks slightly too complicated
>don't you actaully *have* a solution?
>
>You either ban the complete deletion of objects. Or objects
>have well known places they live and unique identity. Some
>OO books gone on quite a bit about identity.
>[color=green]
>> Of course you can use sequence numbers as keys in a hash table or
>> some kind of search tree, but that is relatively computationally
>> expensive compared to the descriptor/locator paired structs.[/color]
>
>I think if things can disappear behind your back then you're
>going to have to live with the full horror of GUIDs.[/color]

You might very well think that; I couldn't possibly comment.


Richard Harter, [email]cri@tiac.net[/email]
[url]http://home.tiac.net/~cri[/url], [url]http://www.varinoma.com[/url]
Save the Earth now!!
It's the only planet with chocolate.

On Nov 4, 12:24 pm, c...@tiac.net (Richard Harter) wrote:[color=blue]
> Suppose we are writing a program in C and that we have a
> particular kind of object (in the sense of OO programming) that I
> will call bobbles.  Being well disciplined programmers (Ha!) we
> create a module to package our bobble related functions together.
>
> If we were using an OO based language there would be machinery in
> place, constructors, destructors, and such like, to handle the
> details of our module, but in C we have to roll our own.
>
> One of the things we need to do is to create functions that will
> serve as constructors and destructors.  There are two things that
> we have to take care of, specifying the interface, and writing
> the function internals.  My concern is with specifying the
> interface.
>
> I am going to throw in one curve ball.  Our program will contain
> references to created bobbles; we won't know where these are so
> they can go stale when we delete bobbles.  The code will need to
> be able to detect that a reference has gone stale and deal with
> it appropriately.[/color]

This is the whole idea behind "opaque handles". The problem is that
you need to allow for the possibility of live handles and obsolete
handles having a mixed existence during the lifetime of your program.

That being said, there is a typical "good enough for the real world"
solution that you can implement in pure C. You need a central "bobble
object management interface". The idea is that you maintain a single
instance shared hash table which maps from integers to bobble
pointers. So you would hash:

struct bobbleMap {
int64_t handle; /* INDEX */
struct bobble * entry; /* pointer to the real Bobble */
};

indexed by the value of handle (so the hash function can be trivial if
you want it to be). You would, as you suggest, issue new handles from
some incrementing counter. The point being that you have to hope that
the lifetime of your program is definitively shorter than the time it
takes for a 64-bit counter to wrap around (otherwise, this solution is
unsound).

In your main program you would just hang onto the 64 bit handle, and
pass it alone as the parameter to any operation you wanted to do on
the bobble. So each operation would first look up the bobble by
handle in the central hash table, and return an error code if the
entry was NULL, otherwise proceed with that operation on the actual
entry and return with whatever error code that operation issues
(hopefully success).

So you can implement a "closeHandle()" (which would modify the hash
table entry from a given handle to point to NULL after destroying the
bobble it was pointing to if any) function instead of a
destroyBobble() which would not exist as a public function even though
you would still create some sort of int64_t createBobble (...)
function. But to make sure that your system was sound you could still
implement a destroyAllBobbles (...) which would wipe everything out
(in the central hash table) at the "end of your program".

The problem is that this can be slow because you need to do a hash
look up every time you do something with your bobble.

Another solution is to literally track the references to each bobble
as you get references to them. So:

struct bobbleDescriptor {
struct bobbleDescriptor * prev; /* LINKED LIST OF DESCRIPTORS
*/
struct bobbleDescriptor * next; /* LINKED LIST OF DESCRIPTORS
*/
struct bobble * entry; /* pointer to the real bobble
*/
};

And you would gain access to each now descriptor from a previous
descriptor:

int openDescriptor (struct bobbleDescriptor * outBp,
struct bobbleDescriptor * inBp);

which you would use via:

struct bobbleDescriptor bd;

if (0 <= openDescriptor (&bd, oldDescriptor)) {
/* Success; I now use &bd as my handle to operations
modifying the bobble it references. */
}

This *inserts* the bd into the linked list described by the
oldDescriptor and points directly to the bobble (so its faster than a
hash table look up, for example.) You would "self remove" the
descriptor via:

int closeDescriptor (struct bobbleDescriptor * bp);

which would remove itself from the linked list and NULL out its own
references for safety reasons. Then finally you would create a
destructor:

int destroyBobble (struct bobbleDescriptor * bp);

which would walk the linked list and overwrite their bobble entries to
NULL, then free the bobble. So after calling this all the descriptors
for that bobble would have pointers to NULL instead of the bobble that
they used to be pointing to. In this way we can see how the lifetime
of a reference to a bobble can exceed that of the bobble itself.

It would almost be like how file handles are used in C today, if you
could imagine opening up a file multiple times and having the
underlying OS delete the file out from underneath you while all those
file handles were still open. Different OSes have different behaviors
if you do that, but ignore than and concentrate on the API and how it
would have to be implemented if it allowed for multiple handles being
opened on the same file and an external actor deleting the file on
you.

The final alternative which I am surprised Jacob Navia isn't harping
on here, obviously, is to use garbage collection and not free the
bobble at all (just put a flag in it that indicates that further use
of it is invalid). This is obviously not portable or implementable
with standard C, but you can see how this isn't even a serious
question in a GC language.

--
Paul Hsieh
[url]http://www.pobox.com/~qed/[/url]
[url]http://bstring.sf.net/[/url]

Paul Hsieh wrote:[color=blue]
> On Nov 4, 12:24 pm, c...@tiac.net (Richard Harter) wrote:[/color]
[color=blue][color=green]
>> I am going to throw in one curve ball. Our program will contain
>> references to created bobbles; we won't know where these are so
>> they can go stale when we delete bobbles. The code will need to
>> be able to detect that a reference has gone stale and deal with
>> it appropriately.[/color][/color]
[color=blue]
> The final alternative which I am surprised Jacob Navia isn't harping
> on here, obviously, is to use garbage collection and not free the
> bobble at all (just put a flag in it that indicates that further use
> of it is invalid). This is obviously not portable or implementable
> with standard C, but you can see how this isn't even a serious
> question in a GC language.[/color]

I thought the main point was the possibility of references to deleted
objects still existing, and being able to trap attempts to use those.

With GC surely the objects would never be deleted in that case, and would
continue to occupy memory.

--
Bartc

In comp.lang.c Richard Harter <cri@tiac.net> wrote:
[color=blue]
> Er, the serial number approach was part of the original proposal.[/color]

Yes, but with a double indirection through intermediate structures
that I thought was unnecessary.

--
pa at panix dot com

On Nov 5, 4:05 pm, "Bartc" <b...@freeuk.com> wrote:[color=blue]
> Paul Hsieh wrote:[color=green]
> > On Nov 4, 12:24 pm, c...@tiac.net (Richard Harter) wrote:[color=darkred]
> >> I am going to throw in one curve ball. Our program will contain
> >> references to created bobbles; we won't know where these are so
> >> they can go stale when we delete bobbles. The code will need to
> >> be able to detect that a reference has gone stale and deal with
> >> it appropriately.[/color]
> > The final alternative which I am surprised Jacob Navia isn't harping
> > on here, obviously, is to use garbage collection and not free the
> > bobble at all (just put a flag in it that indicates that further use
> > of it is invalid).  This is obviously not portable or implementable
> > with standard C, but you can see how this isn't even a serious
> > question in a GC language.[/color]
>
> I thought the main point was the possibility of references to deleted
> objects still existing, and being able to trap attempts to use those.
>
> With GC surely the objects would never be deleted in that case, and would
> continue to occupy memory.[/color]

Well, not necessarily. If it were implemented as:

typedef struct tagBobbleHolder {
struct bobble * entry;
} * bobbleHandle_t;

And you would create a struct tagBobbleHolder for each bobble, and use
a pointer to it (i.e., bobbleHandle_t) as your handle with the
solutions I outline above. Then we would be set. So:

int action (bobbleHandle_t bp) {
if (!bp || !*bp) return ERR_BOBBLE_NOT_ALIVE;
return realAction (bp->entry);
}

int closeBobble (bobbleHandle_t bp) {
if (!bp || !*bp) return ERR_BOBBLE_NOT_ALIVE;
bp->entry = NULL; /* GC can clean bobble immediately */
bp = NULL; /* GC will get around to cleaning the refs */
return ERR_BOBBLE_OK; /* == 0 */
}

void server (bobbleHandle_t bp) {
bobbleHandle_t lbp = bp;
someFunctionWhichDoesWhoKnowsWhat (lbp);
action (lbp);
lpb = NULL;
}

So we can see that no matter what someFunctionWhichDoesWhoKnowsWhat ()
does, including closing *lpb the GC will tear things down exactly as
they should with the only "wasted memory" the extra pointers that
these guys are all passing around. But that becomes proportional to
the number of containers, or threads or whatever which clearly are
already wasting more than that amount of memory by their very
existence.

--
Paul Hsieh
[url]http://www.pobox.com/~qed/[/url]
[url]http://bstring.sf.net/[/url]

[email]cri@tiac.net[/email] (Richard Harter) writes:
[color=blue]
> On Wed, 05 Nov 2008 18:58:39 +0000, Ben Bacarisse
> <ben.usenet@bsb.me.uk> wrote:[/color]
<snip>[color=blue][color=green]
>>... What I don't get is why the a more normal "double
>>indirect" solution does not work for you:
>>[/color][/color]
<snip some diagrams>[color=blue][color=green]
>>
>>I think everything would be clearer if you could say why this is not
>>the right solution for your bobbles. The big advantage is that,
>>outside, there is simply a pointer -- and a pointer to an opaque
>>object at that.[/color]
>
> Your presentation is very clear, thank you. Of course you could
> use a pair of pointers. The problem is that you can never
> release the locator unless you can guarantee that there are no
> extant descriptors pointing to it. This creates a memory leak.
> This may not matter; then again it may. I prefer code that
> doesn't have memory leaks.[/color]

Yes, that was also clear to me but I can't see how your organisation
avoids this problem. I am sure that is my fault, but I don't see how
right now.

--
Ben.