Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #91437 > unrolled thread

Extending C with GC?

Back to article view | Back to comp.lang.c

Contents

  Extending C with GC? luser droog <luser.droog@gmail.com> - 2016-07-31 15:31 -0700
    Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-07-31 15:52 -0700
      Re: Extending C with GC? Tim Rentsch <txr@alumni.caltech.edu> - 2016-07-31 17:21 -0700
      Re: Extending C with GC? Jean-Marc Bourguet <jm@bourguet.org> - 2016-08-01 20:34 +0200
        Re: Extending C with GC? supercat@casperkitty.com - 2016-08-01 12:14 -0700
        Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-01 12:46 -0700
          Re: Extending C with GC? "James R. Kuyper" <jameskuyper@verizon.net> - 2016-08-01 15:56 -0400
            Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-01 14:28 -0700
          Re: Extending C with GC? Jean-Marc Bourguet <jm@bourguet.org> - 2016-08-01 23:37 +0200
            Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-01 15:03 -0700
            Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-02 00:11 +0200
              Re: Extending C with GC? "James R. Kuyper" <jameskuyper@verizon.net> - 2016-08-01 18:19 -0400
                Re: Extending C with GC? BGB <cr88192@hotmail.com> - 2016-08-02 12:46 -0500
      Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-03 15:26 -0700
        Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-03 15:49 -0700
          Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-04 14:07 +1200
            Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-03 19:26 -0700
              Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-04 14:55 +1200
            Re: Extending C with GC? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-08-03 20:38 -0700
              Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-04 05:10 -0700
                Re: Extending C with GC? Siri Cruise <chine.bleu@yahoo.com> - 2016-08-04 05:57 -0700
                  Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-04 06:13 -0700
                Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-05 07:24 +1200
                  Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-04 12:47 -0700
                    Re: Extending C with GC? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-08-04 23:32 -0700
                      Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-05 10:09 +0100
                    Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-05 20:32 +1200
                      Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-05 06:14 -0700
                        Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-06 04:14 -0700
                          Re: Extending C with GC? Melzzzzz <mel@zzzzz.com> - 2016-08-06 13:23 +0200
                            Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-06 04:38 -0700
                          Re: Extending C with GC? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-08-06 04:34 -0700
                            Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-06 05:28 -0700
                              Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-06 06:05 -0700
                                Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-06 06:12 -0700
                            Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-06 14:02 +0100
                              Re: Extending C with GC? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-08-06 06:11 -0700
                                Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-06 14:50 +0100
                                  Re: Extending C with GC? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-08-06 07:57 -0700
                                    Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-06 17:02 +0100
                                Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-06 19:20 +0200
                              Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-06 14:27 +0100
                                Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-06 14:45 +0100
                                Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-06 09:59 -0700
                                  Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-06 19:38 +0100
                                    Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-06 17:03 -0700
                                      Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-07 09:54 +0100
                                        Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-07 21:53 +1200
                                          Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-07 11:34 +0100
                                            Re: Extending C with GC? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-08-07 12:06 +0000
                                            Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-07 14:10 +0100
                                              Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-07 15:38 +0100
                                                Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-07 14:32 -0700
                                                  Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-07 23:44 +0100
                                                    Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-07 16:12 -0700
                                                      Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-08 01:42 +0100
                                                        Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-07 18:56 -0700
                                                          Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-08 10:20 +0100
                                                            Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-08 09:39 -0700
                                                Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-08 02:30 +0100
                                              Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-07 20:15 +0100
                                                Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-08 01:24 +0100
                                                  Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-08 02:08 +0100
                                                    Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-07 18:49 -0700
                                                    Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-08 03:28 +0100
                                                      Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-08 12:14 +0100
                                            Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-08 07:37 +1200
                                              Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-07 20:56 +0100
                                                Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-08 08:11 +1200
                                                  Re: Extending C with GC? Melzzzzz <mel@zzzzz.com> - 2016-08-07 22:19 +0200
                                                  Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-07 22:23 +0100
                                                    Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-07 14:29 -0700
                                                      Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-07 22:36 +0100
                                                        Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-07 15:04 -0700
                                                        Re: Extending C with GC? jameskuyper@verizon.net - 2016-08-07 15:19 -0700
                                                          Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-08 00:04 +0100
                                                            Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-07 16:20 -0700
                                                            Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-08 15:21 +1200
                                                              Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-08 10:35 +0100
                                                                Re: Extending C with GC? Gareth Owen <gwowen@gmail.com> - 2016-08-08 18:13 +0100
                                                                  Re: Extending C with GC? supercat@casperkitty.com - 2016-08-08 11:53 -0700
                                                                    Re: Extending C with GC? raltbos@xs4all.nl (Richard Bos) - 2016-08-10 12:58 +0000
                                                                      Re: Extending C with GC? supercat@casperkitty.com - 2016-08-10 07:05 -0700
                                                                      Re: Extending C with GC? Ken Brody <kenbrody@spamcop.net> - 2016-08-10 12:29 -0400
                                                                  Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-08 21:15 +0100
                                                          Re: Extending C with GC? supercat@casperkitty.com - 2016-08-08 08:57 -0700
                                                        Re: Extending C with GC? luser droog <luser.droog@gmail.com> - 2016-08-07 15:37 -0700
                                                    Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-07 14:58 -0700
                                                    Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-08 15:26 +1200
                                                      Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-08 10:26 +0200
                                                        Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-08 21:13 +1200
                                                          Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-08 10:41 +0100
                                                          Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-08 12:00 +0200
                                                            Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-08 22:07 +1200
                                                            Re: Extending C with GC? David Brown <david.brown@hesbynett.no> - 2016-08-08 12:57 +0200
                                                            Re: Extending C with GC? Gareth Owen <gwowen@gmail.com> - 2016-08-08 18:12 +0100
                                                        Re: Extending C with GC? Ian Collins <ian-news@hotmail.com> - 2016-08-08 21:25 +1200
                                                          Re: Extending C with GC? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-08-08 02:57 -0700
                                            Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-07 13:28 -0700
                                        Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-07 05:42 -0700
                                Re: Extending C with GC? Florian Weimer <fw@deneb.enyo.de> - 2016-08-07 11:49 +0200
                              Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-06 19:18 +0200
                                Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-06 12:35 -0700
                            Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-06 19:27 +0200
                              Re: Extending C with GC? "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2016-08-06 10:55 -0700
                              Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-06 12:31 -0700
        Re: Extending C with GC? James Kuyper <jameskuyper@verizon.net> - 2016-08-03 22:36 -0400
          Re: Extending C with GC? David Brown <david.brown@hesbynett.no> - 2016-08-04 10:57 +0200
            Re: Extending C with GC? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-08-04 04:09 -0700
              Re: Extending C with GC? David Brown <david.brown@hesbynett.no> - 2016-08-04 14:01 +0200
          Re: Extending C with GC? supercat@casperkitty.com - 2016-08-04 07:52 -0700
        Re: Extending C with GC? Tim Rentsch <txr@alumni.caltech.edu> - 2016-08-04 08:57 -0700
          Re: Extending C with GC? supercat@casperkitty.com - 2016-08-04 09:19 -0700
            Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-04 12:30 -0700
              Re: Extending C with GC? supercat@casperkitty.com - 2016-08-04 15:21 -0700
                Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-04 16:50 -0700
                  Re: Extending C with GC? supercat@casperkitty.com - 2016-08-05 07:31 -0700
            Re: Extending C with GC? Tim Rentsch <txr@alumni.caltech.edu> - 2016-08-05 16:01 -0700
          Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-04 21:00 +0200
            Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-04 20:26 +0100
              Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-05 10:37 +0200
                Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-05 15:52 +0100
                Re: Extending C with GC? antispam@math.uni.wroc.pl - 2016-08-21 00:09 +0000
                  Re: Extending C with GC? Gareth Owen <gwowen@gmail.com> - 2016-08-21 08:58 +0100
                  Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-21 10:48 +0200
                  Re: Extending C with GC? "Pascal J. Bourguignon" <pjb@informatimago.com> - 2016-08-21 19:58 +0200
                  Re: Extending C with GC? supercat@casperkitty.com - 2016-08-22 08:46 -0700
                    Re: Extending C with GC? Öö Tiib <ootiib@hot.ee> - 2016-08-26 02:24 -0700
                      Re: Extending C with GC? supercat@casperkitty.com - 2016-08-26 13:37 -0700
                        Re: Extending C with GC? Melzzzzz <mel@zzzzz.com> - 2016-08-27 00:41 +0200
                        Re: Extending C with GC? Öö Tiib <ootiib@hot.ee> - 2016-08-28 06:12 -0700
              Re: Extending C with GC? BartC <bc@freeuk.com> - 2016-08-05 10:06 +0100
                Re: Extending C with GC? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-05 15:26 +0100
            Re: Extending C with GC? Tim Rentsch <txr@alumni.caltech.edu> - 2016-08-05 08:11 -0700
              Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-05 17:43 +0200
                Re: Extending C with GC? Tim Rentsch <txr@alumni.caltech.edu> - 2016-08-05 15:28 -0700
          Re: Extending C with GC? BGB <cr88192@hotmail.com> - 2016-08-04 17:11 -0500
    Re: Extending C with GC? Tim Rentsch <txr@alumni.caltech.edu> - 2016-07-31 17:35 -0700
    Re: Extending C with GC? jacobnavia <jacob@jacob.remcomp.fr> - 2016-08-01 07:45 +0200
      Re: Extending C with GC? Keith Thompson <kst-u@mib.org> - 2016-08-01 08:49 -0700
      Re: Extending C with GC? supercat@casperkitty.com - 2016-08-01 09:06 -0700
        Re: Extending C with GC? Aleksandar Kuktin <akuktin@gmail.com> - 2016-08-05 18:11 +0000
          Re: Extending C with GC? luser droog <luser.droog@gmail.com> - 2016-08-05 11:24 -0700
    Re: Extending C with GC? "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-08-08 22:12 -0700

Page 1 of 8  [1] 2 3 4 5 6 7 8  Next page →

#91437 — Extending C with GC?

In a recent thread that touched upon closures, it was made apparent
that automatic storage reclamation would be a practical necessity
to support closures. 

So how would C work with a garbage collector? How do existing 
extensions work? Is there a new allocator function to allow a
"mixed" style, where you manually free the things that are easy
and rely on the GC for the things that are hard? Or does it 
take-over malloc(), if so what does free() do?

Since I use C primarily as the implementation language for other
programming languages, I'd love to stop writing gc code.

[toc] | [next] | [standalone]

#91440

luser droog <luser.droog@gmail.com> writes:
> In a recent thread that touched upon closures, it was made apparent
> that automatic storage reclamation would be a practical necessity
> to support closures. 
>
> So how would C work with a garbage collector? How do existing 
> extensions work? Is there a new allocator function to allow a
> "mixed" style, where you manually free the things that are easy
> and rely on the GC for the things that are hard? Or does it 
> take-over malloc(), if so what does free() do?
>
> Since I use C primarily as the implementation language for other
> programming languages, I'd love to stop writing gc code.

There is a narrow technical point that implies that garbage
collection is incompatible with conformance to the C standard.

GC depends on the ability to detect that a chunk of memory is no
longer in use, and can be recovered.  There are various methods
to do this, but basically if there's currently nothing pointing to
a chunk of memory, it's considered safe to assume that that chunk
can be reclaimed.

In standard C, it's perfectly legal to take a pointer value, write
it to a file, set the pointer variable to NULL, and later read the
original pointer value back from the file.

    void *ptr = malloc(some_size);
    assert(ptr != NULL);
    fprintf(some_file, "%p\n", (void*)ptr);
    ptr = NULL;
    /* Now nothing in memory refers to the allocated memory, but a
     * pointer value has been saved in the file.
     */
    ...
    fscanf("%p", &ptr);
    /* Now we have a valid pointer to the allocated chunk of memory */

Or you can break a pointer value down into a sequence of bytes,
scatter those bytes into separate objects, and then collect them
back into a valid pointer value.

A GC system cannot track all possible ways to store a pointer value,
and therefore cannot always know that a given chunk of memory can
never be used again.

Does this mean that GC can't be used with C?  No.  There are
real-world implementations of GC for C, such as Boehm GC.
If you're using such a system, you just have make sure that you
have an active in-memory pointer to any memory you don't want to
be garbage-collected.  This usually doesn't cause any problems.

Would this be a barrier to including GC in a future C standard?  No.
If a future C standard included some form of GC, it could change
the rules to allow for it.

Another point: Some GC implementations will occasionally (and
unpredictably) require a significant amount of time to scan
memory and look for garbage.  This could be unacceptable in some
applications, such as real-time systems where such a delay can be
literally deadly.  There needs to be a way to disable GC to avoid
that kind of problem.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#91446

Keith Thompson <kst-u@mib.org> writes:

> luser droog <luser.droog@gmail.com> writes:
>> In a recent thread that touched upon closures, it was made apparent
>> that automatic storage reclamation would be a practical necessity
>> to support closures.
>>
>> So how would C work with a garbage collector?  How do existing
>> extensions work?  Is there a new allocator function to allow a
>> "mixed" style, where you manually free the things that are easy
>> and rely on the GC for the things that are hard?  Or does it
>> take-over malloc(), if so what does free() do?
>>
>> Since I use C primarily as the implementation language for other
>> programming languages, I'd love to stop writing gc code.
>
> There is a narrow technical point that implies that garbage
> collection is incompatible with conformance to the C standard.
>
> [..explanation and discussion..]
>
> Would this be a barrier to including GC in a future C standard?  No.
> If a future C standard included some form of GC, it could change
> the rules to allow for it.

Nice summary, thank you for writing it.

> Another point:  Some GC implementations will occasionally (and
> unpredictably) require a significant amount of time to scan
> memory and look for garbage.  This could be unacceptable in some
> applications, such as real-time systems where such a delay can be
> literally deadly.  There needs to be a way to disable GC to avoid
> that kind of problem.

Note that there are garbage collection algorithms that guarantee
real-time performance at every collection point (obviously under
some set of constraints about memory use and available memory,
etc).  It would be possible to use such GC even in systems that
require real-time performance guarantees, although admittedly
that would require some care to ensure the constraints are met.

[toc] | [prev] | [next] | [standalone]

#91508

Keith Thompson <kst-u@mib.org> writes:

> GC depends on the ability to detect that a chunk of memory is no
> longer in use, and can be recovered.  There are various methods
> to do this, but basically if there's currently nothing pointing to
> a chunk of memory, it's considered safe to assume that that chunk
> can be reclaimed.
>
> In standard C, it's perfectly legal to take a pointer value, write
> it to a file, set the pointer variable to NULL, and later read the
> original pointer value back from the file.

Without writing pointers to files, which I've never met, there are at least
three techniques which I've met in the wild which don't play nice with GC:

- the old trick of using the or of the next and prev pointers as unique
  sibling link in a doubly linked list (to iterate, you need to keep the
  current and the previous node); AFAIK you don't even need to be
  implementation dependent for that
   
- the old trick of using low order bits of aligned pointers or high order
  bits when there is a large adress space to keep additional information
  (you depend of your implementation alignment structure for the first
  variant, you'll be cursed by the future maintainer of your code with the
  second -- ask those who have succeeded IBM 360 and MC68000 programmers)

- offsetting a pointer.  There are non-conformant variant (offsetting by
  negative value) and conformant one (offsetting by a positive value but
  staying in the allocated region)

Some of those may be manageable by GCs which allow to keep alive any block
as soon as there is a pointer to somewhere inside it.

> Would this be a barrier to including GC in a future C standard?  No.
> If a future C standard included some form of GC, it could change
> the rules to allow for it.

IIRC, there is something present in C++ for that (a kind of annotation
allowing the programmer to promise that they aren't using dirty tricks).  I
don't remember having seen someone using that.

Yours,

-- 
Jean-Marc

[toc] | [prev] | [next] | [standalone]

#91515

On Monday, August 1, 2016 at 1:35:02 PM UTC-5, Jean-Marc Bourguet wrote:
> - offsetting a pointer.  There are non-conformant variant (offsetting by
>   negative value) and conformant one (offsetting by a positive value but
>   staying in the allocated region)

Given something like:

    struct foo { char a1[8][8]; };
    char *p = malloc(64);
    struct foo *q = (struct foo*) p;
    char *r1 = q->a1[0];
    char *r2 = (char*)(q->a1[0]);
    char *r3 = (char*)&(q->a1[0]);

the Standard is quite clear that q->a1[0][n] is only defined for values
of n in the range 0 to 7.  I don't think it's clear on whether r1[n] is
defined for values of n beyond 7, and likewise r2[n] and r3[n].

[toc] | [prev] | [next] | [standalone]

#91519

Jean-Marc Bourguet <jm@bourguet.org> writes:
> Keith Thompson <kst-u@mib.org> writes:
>
>> GC depends on the ability to detect that a chunk of memory is no
>> longer in use, and can be recovered.  There are various methods
>> to do this, but basically if there's currently nothing pointing to
>> a chunk of memory, it's considered safe to assume that that chunk
>> can be reclaimed.
>>
>> In standard C, it's perfectly legal to take a pointer value, write
>> it to a file, set the pointer variable to NULL, and later read the
>> original pointer value back from the file.
>
> Without writing pointers to files, which I've never met, there are at least
> three techniques which I've met in the wild which don't play nice with GC:
>
> - the old trick of using the or of the next and prev pointers as unique
>   sibling link in a doubly linked list (to iterate, you need to keep the
>   current and the previous node); AFAIK you don't even need to be
>   implementation dependent for that

You mean xor, yes?

Storing the result of xor'ing two pointer values in a pointer object
could (in principle) cause problems if the result is a trap
representation.  I believe it's harmless in practice on most common
systems.

> - the old trick of using low order bits of aligned pointers or high order
>   bits when there is a large adress space to keep additional information
>   (you depend of your implementation alignment structure for the first
>   variant, you'll be cursed by the future maintainer of your code with the
>   second -- ask those who have succeeded IBM 360 and MC68000 programmers)

This also makes assumptions about how pointers are represented.  I've
worked on systems (Cray vector systems) where C pointers contained a
byte offset in the high-order 3 bits.

> - offsetting a pointer.  There are non-conformant variant (offsetting by
>   negative value) and conformant one (offsetting by a positive value but
>   staying in the allocated region)

Offsetting by a negative value is perfectly valid if the result still
points into the same object.  As for positive offsets, I can imagine
that something like:

    unsigned char *ptr = malloc(1024);
    assert(ptr != NULL);
    ptr += 32;

might cause headaches for a GC system.  (I don't know whether it does so
in practice.)

[...]

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#91522

On 08/01/2016 03:46 PM, Keith Thompson wrote:
> Jean-Marc Bourguet <jm@bourguet.org> writes:
...
>> - the old trick of using the or of the next and prev pointers as unique
>>   sibling link in a doubly linked list (to iterate, you need to keep the
>>   current and the previous node); AFAIK you don't even need to be
>>   implementation dependent for that
>
> You mean xor, yes?
>
> Storing the result of xor'ing two pointer values in a pointer object
> could (in principle) cause problems if the result is a trap
> representation.  I believe it's harmless in practice on most common
> systems.

Convert to uintptr_t before xor'ing, and convert back to the appropriate 
pointer type after recovering those values. Technically, void* must be 
used as an intermediate step. On many platforms those conversions will 
be unnecessary - however, on precisely those platforms, 
(uintptr_t)(void*)p will probably compile to a nop.

[toc] | [prev] | [next] | [standalone]

#91533

"James R. Kuyper" <jameskuyper@verizon.net> writes:
> On 08/01/2016 03:46 PM, Keith Thompson wrote:
>> Jean-Marc Bourguet <jm@bourguet.org> writes:
> ...
>>> - the old trick of using the or of the next and prev pointers as unique
>>>   sibling link in a doubly linked list (to iterate, you need to keep the
>>>   current and the previous node); AFAIK you don't even need to be
>>>   implementation dependent for that
>>
>> You mean xor, yes?
>>
>> Storing the result of xor'ing two pointer values in a pointer object
>> could (in principle) cause problems if the result is a trap
>> representation.  I believe it's harmless in practice on most common
>> systems.
>
> Convert to uintptr_t before xor'ing, and convert back to the appropriate 
> pointer type after recovering those values. Technically, void* must be 
> used as an intermediate step. On many platforms those conversions will 
> be unnecessary - however, on precisely those platforms, 
> (uintptr_t)(void*)p will probably compile to a nop.

Assuming that uintptr_t exists.  For 100% (rather than 99.9%)
portability, you can treat the pointer's representation as an array of
unsigned char.

Of course if you want to xor pointer values, you'll need to convert to
some integer type anyway.  It's probably reasonable to assume the
existence of uintptr_t and let the code fail to compile if it doesn't
exist.  (Assuming the xor trick is worthwhile in the first place.)

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#91535

Keith Thompson <kst-u@mib.org> writes:

>> - the old trick of using the or of the next and prev pointers as unique
>>   sibling link in a doubly linked list (to iterate, you need to keep the
>>   current and the previous node); AFAIK you don't even need to be
>>   implementation dependent for that
>
> You mean xor, yes?

Indeed.

> Storing the result of xor'ing two pointer values in a pointer object
> could (in principle) cause problems if the result is a trap
> representation.  I believe it's harmless in practice on most common
> systems.

I've always seen an unsigned type used (long unsigned and uintptr_t after
it was introduced, using uintptr_t should make you conformant if I'm not
mistaken).

>> - offsetting a pointer.  There are non-conformant variant (offsetting by
>>   negative value) and conformant one (offsetting by a positive value but
>>   staying in the allocated region)
>
> Offsetting by a negative value is perfectly valid if the result still
> points into the same object.

In the context of a GC, I was thinking of negatively offsetting the result
of malloc() or equivalent.  It will confuse even the GC which can keep
alive a block with any pointer pointing inside it.

> As for positive offsets, I can imagine
> that something like:
>
>     unsigned char *ptr = malloc(1024);
>     assert(ptr != NULL);
>     ptr += 32;
>
> might cause headaches for a GC system.  (I don't know whether it does so
> in practice.)

I've seen both cases.  Obviously p += 2048 confuse everything I've heard
of.

Yours,

-- 
Jean-Marc

[toc] | [prev] | [next] | [standalone]

#91536

Jean-Marc Bourguet <jm@bourguet.org> writes:
> Keith Thompson <kst-u@mib.org> writes:
[...]
>> Offsetting by a negative value is perfectly valid if the result still
>> points into the same object.
>
> In the context of a GC, I was thinking of negatively offsetting the result
> of malloc() or equivalent.  It will confuse even the GC which can keep
> alive a block with any pointer pointing inside it.

That has undefined behavior as far as the C standard is concerned (just
computing `ptr-1`, for example, even if it's not used or dereferenced).
Once you've done that, even assuming nothing crashes, you no longer have
a pointer to the allocated memory and it's perfectly reasonable for a GC
system to relcaim it.

On the other hand, it might be reasonable in system-specific code to
peek at memory before the beginning of a malloc()ed block -- but then
you should still keep a copy of the original pointer returned by
malloc().

>> As for positive offsets, I can imagine
>> that something like:
>>
>>     unsigned char *ptr = malloc(1024);
>>     assert(ptr != NULL);
>>     ptr += 32;
>>
>> might cause headaches for a GC system.  (I don't know whether it does so
>> in practice.)
>
> I've seen both cases.  Obviously p += 2048 confuse everything I've heard
> of.

Again, that has undefined behavior.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#91537

Le 01/08/2016 à 23:37, Jean-Marc Bourguet a écrit :
[ snip ]

Look:

If you hide a pointer from the GC by some means, you risk that your 
memory will be collected and overwritten. Do not use any GC if you do 
things like that.

Isn't that an EASY rule?

I mean the GC remains OPTIONAL and if you do things like

O storing pointers on disk
O xoring or change the pointer value
O Encrypt the pointer with DES

and a LONG "etc" of things you can possibly do with pointers to alter 
their value

you just do not use the gc!!!

There are programs for instance that do not use memory allocation at all 
and get by with fixed size tables. In their environment, memory 
allocation can't be tolerated because of the possiblity of allocation 
failure is just impossible to afford. Real time systems, OS kernels, 
whatever.

Of course you can have BOTH worlds:

For some pointers ypu allocate manually, for others you allocate through 
the GC.

[toc] | [prev] | [next] | [standalone]

#91538

On 08/01/2016 06:11 PM, jacobnavia wrote:
> Le 01/08/2016 à 23:37, Jean-Marc Bourguet a écrit :
> [ snip ]
>
> Look:
>
> If you hide a pointer from the GC by some means, you risk that your
> memory will be collected and overwritten. Do not use any GC if you do
> things like that.
>
> Isn't that an EASY rule?

Absolutely trivial, and no-one has suggested otherwise. As Keith said 
just yesterday:

> Does this mean that GC can't be used with C?  No.  There are
> real-world implementations of GC for C, such as Boehm GC.
> If you're using such a system, you just have make sure that you
> have an active in-memory pointer to any memory you don't want to
> be garbage-collected.  This usually doesn't cause any problems.

The OP asked "Or does it take-over malloc()"; and the answer to that 
question is that doing so would render the implementation 
non-conforming. Not difficult to use, just "non-conforming". You've been 
talking almost exclusively about GC as a feature provided only for 
memory allocated using a function that is not part of the C standard 
library, for which no such issues arise.

[toc] | [prev] | [next] | [standalone]

#91573

On 8/1/2016 5:19 PM, James R. Kuyper wrote:
> On 08/01/2016 06:11 PM, jacobnavia wrote:
>> Le 01/08/2016 à 23:37, Jean-Marc Bourguet a écrit :
>> [ snip ]
>>
>> Look:
>>
>> If you hide a pointer from the GC by some means, you risk that your
>> memory will be collected and overwritten. Do not use any GC if you do
>> things like that.
>>
>> Isn't that an EASY rule?
>
> Absolutely trivial, and no-one has suggested otherwise. As Keith said
> just yesterday:
>
>> Does this mean that GC can't be used with C?  No.  There are
>> real-world implementations of GC for C, such as Boehm GC.
>> If you're using such a system, you just have make sure that you
>> have an active in-memory pointer to any memory you don't want to
>> be garbage-collected.  This usually doesn't cause any problems.
>
> The OP asked "Or does it take-over malloc()"; and the answer to that
> question is that doing so would render the implementation
> non-conforming. Not difficult to use, just "non-conforming". You've been
> talking almost exclusively about GC as a feature provided only for
> memory allocated using a function that is not part of the C standard
> library, for which no such issues arise.

yep, that is the case which makes sense, namely, the use of separate 
allocation functions.


OTOH, I will also note that I have recently made a newer script 
language/VM which currently does not use GC, due to the inability to 
have a "good" GC which does not pose issues with stalls/latency in 
real-time use cases (*), and the comparably rather high runtime overhead 
of reference counting.

currently it uses mostly manual MM and automatic storage duration, with 
a planned / partially-implemented region system.

it was originally planned to use implicit ref-counting, but for now this 
has been dropped due to far-reaching overhead concerns (overheads would 
have applied to pretty much anything heap-allocated).

it is possible though I could introduce a more explicit form of 
reference-counting, which is more opt-in instead (only applies to 
specific objects, namely those with a modifier to explicitly request 
reference-counting).


side note: actual scripting language is statically typed and loosely 
resembles some sort of C/Java hybrid, but is semantically closer to 
being a C/C# hybrid.


*: its design was originally intended for use in robots running on ARM 
based controllers, but at-present (due to my robot projects currently 
stalling out due to other reasons) I am using it for scripting in a game 
engine project (softer real-time).

(some of my existing robot projects use a C variant running in an 
interpreter for the script VM).


still trying to keep it reasonably friendly to "slightly harder" 
real-time uses though.

though, I have noted that it seems problematic that people define things 
(hard vs soft) mostly in terms of the "severity" of the consequences of 
missing real-time constraints, rather than the relative scale of the 
timeslice (and other factors that more directly effect engineering choices).

this leaves the robots as an odd case, as the "severity" of occasional 
missed deadlines isn't that severe (implying soft real-time), however 
the accuracy required for the time-slices is rather a bit smaller 
(microseconds), and it is a lot harder to uphold a "soft" 10us 
constraint than a "hard" 10ms (10000us) constraint.

like, in the former, it might be going 5us over-target (after running 
for 20us), and in the latter it might be failing to complete within a 
window of 500us before the target (say, it running for 19515 us).


even if, no, no one will die if a servo motor in a small robot jitters, 
or the occasional serial packet gets corrupt and needs to be 
discarded/resent, ...


then in a game, so long as frames keep happening preferably within 16ms 
(for the ever-important 60 fps), everyone is happy, but then stuff 
lagging is, well, also just part of the game... (here you mostly just 
don't want delays that are large enough to be noticeable to the user).

or such...

[toc] | [prev] | [next] | [standalone]

#91628

Keith Thompson <kst-u@mib.org> writes:
> luser droog <luser.droog@gmail.com> writes:
>> In a recent thread that touched upon closures, it was made apparent
>> that automatic storage reclamation would be a practical necessity
>> to support closures. 
>>
>> So how would C work with a garbage collector? How do existing 
>> extensions work? Is there a new allocator function to allow a
>> "mixed" style, where you manually free the things that are easy
>> and rely on the GC for the things that are hard? Or does it 
>> take-over malloc(), if so what does free() do?
>>
>> Since I use C primarily as the implementation language for other
>> programming languages, I'd love to stop writing gc code.
>
> There is a narrow technical point that implies that garbage
> collection is incompatible with conformance to the C standard.
>
> GC depends on the ability to detect that a chunk of memory is no
> longer in use, and can be recovered.  There are various methods
> to do this, but basically if there's currently nothing pointing to
> a chunk of memory, it's considered safe to assume that that chunk
> can be reclaimed.

[snip discussion of ways a pointer value can be "hidden" from a GC
system]

There's also an inverse problem, though it's not as severe.

A GC system that depends on scanning memory and registers looking
for in-use addresses can also get false positives.

A GC-aware program might build, say, a large binary tree in memory.
Let's say the root node is allocated at (void*)0xdeadbeef, and
the rest of the tree is accessible only via the root.  The program
might then set its only copy of the root pointer to NULL with the
expectation that the whole tree will then be garbage-collected.
But if something that looks like the address of the root node happens
to be stored elsewhere, it might never be collected, resulting in
a memory leak.

I believe that GC systems for some languages other than C can
deal with this, but I don't know how a C garbage collector could
avoid this problem in all cases.  Perhaps a compiler could provide
information that the GC can access at run time that tells it which
objects are actually pointers -- but I don't know (a) whether
compilers actually do this, or (b) whether it's even possible
in general.

I'm fairly sure this is a well known issue.  Perhaps there are
solutions I don't know about.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#91629

GC and C are fundamentally incompatible.  The only possibility of
employing GC in C is by API, and a hobbling of the benefits of C by
voluntary submission to protocol enforcement.

It cannot be done automatically without
transforming C into something else other than C.

-----
C is designed to be what it is.  Other things should be voluntary
layers subscribed to by purposeful choice, which is what we see with
various libraries and add-ons.

Best regards,
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#91631

On 08/ 4/16 10:49 AM, Rick C. Hodgin wrote:
> GC and C are fundamentally incompatible.  The only possibility of
> employing GC in C is by API, and a hobbling of the benefits of C by
> voluntary submission to protocol enforcement.

That's nonsense.

There's nothing stopping you linking a GC allocator library with your 
code.  People (including me) have been doing so for years.

-- 
Ian

[toc] | [prev] | [next] | [standalone]

#91632

On Wednesday, August 3, 2016 at 10:07:39 PM UTC-4, Ian Collins wrote:
> On 08/ 4/16 10:49 AM, Rick C. Hodgin wrote:
> > GC and C are fundamentally incompatible.  The only possibility of
> > employing GC in C is by API, and a hobbling of the benefits of C by
> > voluntary submission to protocol enforcement.
> 
> That's nonsense.
> 
> There's nothing stopping you linking a GC allocator library with your 
> code.  People (including me) have been doing so for years.

You gain a small temporal migration from free()'d blocks (assuming you
can free them in a parallel thread), but you lose all of the advantages
of having the things GC are used for in the first place.

    01:  // Use special link options to replace malloc() and free()
    02:  int main(int argc, char* argv[])
    03:  {
    04:      char *p1, *p2;
    05:      p1 = malloc(50);
    06:      p2 = p1;
    07:      free(p1);

             // Other code here

    98:      return(0);
    99:  }

After 07, the memory's no longer valid because it could be GC'd at any
time.  C provides no mechanisms to indicate or determine that a reference
to the memory block still exists in p2.

You're forced to operate through the API you've determined, and whatever
protocol you've setup regarding it, otherwise references to p2 could be
valid for a time, or not, but at some point they will no longer be valid,
even though they should be valid in a GC environment, because the hanging
reference still exists.

Best regards,
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#91634

On 08/ 4/16 02:26 PM, Rick C. Hodgin wrote:
> On Wednesday, August 3, 2016 at 10:07:39 PM UTC-4, Ian Collins wrote:
>> On 08/ 4/16 10:49 AM, Rick C. Hodgin wrote:
>>> GC and C are fundamentally incompatible.  The only possibility of
>>> employing GC in C is by API, and a hobbling of the benefits of C by
>>> voluntary submission to protocol enforcement.
>>
>> That's nonsense.
>>
>> There's nothing stopping you linking a GC allocator library with your
>> code.  People (including me) have been doing so for years.
>
> You gain a small temporal migration from free()'d blocks (assuming you
> can free them in a parallel thread), but you lose all of the advantages
> of having the things GC are used for in the first place.
>
>      01:  // Use special link options to replace malloc() and free()
>      02:  int main(int argc, char* argv[])
>      03:  {
>      04:      char *p1, *p2;
>      05:      p1 = malloc(50);
>      06:      p2 = p1;
>      07:      free(p1);
>
>               // Other code here
>
>      98:      return(0);
>      99:  }
>
> After 07, the memory's no longer valid because it could be GC'd at any
> time.

No, I'll be collected when main returns...  With a collecting allocator, 
free is a no-op.

> C provides no mechanisms to indicate or determine that a reference
> to the memory block still exists in p2.

That's not how garbage collection works.  Nothing will be collected 
while p1 and p2 are active.

-- 
Ian

[toc] | [prev] | [next] | [standalone]

#91635

On Thursday, August 4, 2016 at 3:07:39 AM UTC+1, Ian Collins wrote:
> On 08/ 4/16 10:49 AM, Rick C. Hodgin wrote:
> > GC and C are fundamentally incompatible.  The only possibility of
> > employing GC in C is by API, and a hobbling of the benefits of C by
> > voluntary submission to protocol enforcement.
> 
> That's nonsense.
> 
> There's nothing stopping you linking a GC allocator library with your 
> code.  People (including me) have been doing so for years.
> 
There's a strong argument that garbage collection goes against the
"spirit of C". However you can add it, and an important practical
result is that you longer need this pattern

OBJECT *constructor()
{
   OBJECT *answer;
  
    ....
    if(answer->child[i].deeply[nested]->pointer == 0) // memory failure
        goto error_exit;
    ....
    return answer;
error_exit:
    destructor(answer); // partially constructed object
    return 0;
}

void destructor(OBJECT *obj)
{
    // mustn't have any dangling pointers in object,
    // must be clear what we "own" and what we just reference
    if(obj)  // must be robust to nulls however
    {
        free(obj);
    }
}

foo()
{
   OBJECT *obj = constructor(1, "two", &three);
   if(!obj)
     goto error_exit:
  
   destructor(obj);
   return answer;
   error_exit:
     destructor(obj);
     return -1;  // conventional error code for "out of memory
}

That's quite a bit of code, and it's all boiler plate memory
management.

[toc] | [prev] | [next] | [standalone]

#91642

On Wednesday, August 3, 2016 at 11:38:44 PM UTC-4, Malcolm McLean wrote:
> On Thursday, August 4, 2016 at 3:07:39 AM UTC+1, Ian Collins wrote:
> > On 08/ 4/16 10:49 AM, Rick C. Hodgin wrote:
> > > GC and C are fundamentally incompatible.  The only possibility of
> > > employing GC in C is by API, and a hobbling of the benefits of C by
> > > voluntary submission to protocol enforcement.
> > 
> > That's nonsense.
> > 
> > There's nothing stopping you linking a GC allocator library with your 
> > code.  People (including me) have been doing so for years.
> > 
> There's a strong argument that garbage collection goes against the
> "spirit of C". However you can add it, and an important practical
> result is that you longer need this pattern
> 
> OBJECT *constructor()
> {
>    OBJECT *answer;
>   
>     ....
>     if(answer->child[i].deeply[nested]->pointer == 0) // memory failure
>         goto error_exit;
>     ....
>     return answer;
> error_exit:
>     destructor(answer); // partially constructed object
>     return 0;
> }
> 
> void destructor(OBJECT *obj)
> {
>     // mustn't have any dangling pointers in object,
>     // must be clear what we "own" and what we just reference
>     if(obj)  // must be robust to nulls however
>     {
>         free(obj);
>     }
> }
> 
> foo()
> {
>    OBJECT *obj = constructor(1, "two", &three);
>    if(!obj)
>      goto error_exit:
>   
>    destructor(obj);
>    return answer;
>    error_exit:
>      destructor(obj);
>      return -1;  // conventional error code for "out of memory
> }
> 
> That's quite a bit of code, and it's all boiler plate memory
> management.

API:

    constructor();
    destructor();

Protocol:

    Use of new structure
    Strict adherence to calling constructor() to create something.
    Strict adherence to calling destructor() to destroy something.

It's a layer added on top of C, an API plus protocol which is voluntarily
adhered to for use.  It is not part of C in any way, except that the code
related to the API is written in C.

The only way GC could be introduced in C directly, is to change the
fundamental nature of how it creates, uses, and releases memory, and
that would be a hobbling of C's direct-access model.

Best regards,
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

Page 1 of 8  [1] 2 3 4 5 6 7 8  Next page →

Back to top | Article view | comp.lang.c

csiph-web