Bruce Hoult | 14 Jun 08:48 2016

Re: [Gc] Difference between boehm gc algorithm and mark-n-sweep

It's certainly mark-n-sweep, though optimised in some ways to reduce pause times and generally be friendly to multi-level memory hierarchies (e.g. virtual memory paging, when bdwgc was young, though it's more about L3 cache and RAM and even TLB now).

e.g.

- mark bits are not stored with the objects, so a memory page filled with dead objects will not be touched at all during the mark phase.

- the sweep is done incrementally, with each page being swept (and its free list created) at the moment that the first new object will be allocated from that page after the previous GC.


On Mon, Jun 13, 2016 at 9:53 PM, Vladimir Miloserdov <milosvova <at> gmail.com> wrote:
Hello

I'm new to this GC and I'm curious about the difference between
collector algorithm it uses and regular mark-n-sweep algo. The only
thing I'm able to find is that it uses "modified mark-n-sweep". Could
you please help me?

Regards,
Vladimir
_______________________________________________
bdwgc mailing list
bdwgc-ZwoEplunGu1I4Lznb4ZCK0B+6BGkLq7r@public.gmane.org
https://lists.opendylan.org/mailman/listinfo/bdwgc

--
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.


_______________________________________________
bdwgc mailing list
bdwgc@...
https://lists.opendylan.org/mailman/listinfo/bdwgc
Vladimir Miloserdov | 13 Jun 20:53 2016
Picon
Gravatar

[Gc] Difference between boehm gc algorithm and mark-n-sweep

Hello

I'm new to this GC and I'm curious about the difference between
collector algorithm it uses and regular mark-n-sweep algo. The only
thing I'm able to find is that it uses "modified mark-n-sweep". Could
you please help me?

Regards,
Vladimir
Basile Starynkevitch | 25 May 10:20 2016
Picon

[Gc] using a lot of finalizers?

Hello,

In my MELT monitor (see https://github.com/bstarynk/melt-monitor-2015/ 
for details) I am having a lot finalizers. You might consider (GC-wise) 
that it is sort-of some Lisp (but multi-threaded, with a small thread 
pool of about half a dozen threads) interpreter.

Basically, I have (conceptually) a lot of immutable GC-ed values 
(allocated with GC_MALLOC) and some mutable GC-ed "items" (also 
allocated with GC_MALLOC). Those items are registering a finalizer with 
GC_REGISTER_FINALIZER_IGNORE_SELF at creation time.

In the event I would have a large (e.g. a dozen of gigabytes) GC heap, 
is it acceptable to have many (e.g. half a million) of items with 
finalizers and much more (e.g. several millions) values.

So my question becomes: can I have many items, each having registered a 
finalizer, or is it not acceptable performance-wise?

Or should I put a lot of design effort to avoid finalizers?

My blind guess is that since "gc/gc_cpp.h" is using 
GC_REGISTER_FINALIZER_IGNORE_SELF it should be acceptable to have a lot 
of finalizers.

Regards.

--

-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mine, sont seulement les miennes} ***
Chris Metcalf | 2 May 17:41 2016

[Gc] [PATCH] Implement the basic atomic primitives for the tilegx/tilepro cpus.

* src/Makefile.am (nobase_private_HEADERS): Add tile.h.
* src/atomic_ops.h: Include tile.h file.
* src/atomic_ops/sysdeps/gcc/tile.h: New file.
---
For libatomic_ops:

This patch is an updated version of the CentOS 6 patch that we have
been carrying as part of our own CentOS-like distribution since 2012.

 src/Makefile.am                   |    1 +
 src/atomic_ops.h                  |    3 ++
 src/atomic_ops/sysdeps/gcc/tile.h |   52 +++++++++++++++++++++++++++++++++++++
 3 files changed, 56 insertions(+), 0 deletions(-)
 create mode 100644 src/atomic_ops/sysdeps/gcc/tile.h

diff --git a/src/Makefile.am b/src/Makefile.am
index d463427..8971370 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
 <at>  <at>  -84,6 +84,7  <at>  <at>  nobase_private_HEADERS = atomic_ops/ao_version.h \
           atomic_ops/sysdeps/gcc/s390.h \
           atomic_ops/sysdeps/gcc/sh.h \
           atomic_ops/sysdeps/gcc/sparc.h \
+          atomic_ops/sysdeps/gcc/tile.h \
           atomic_ops/sysdeps/gcc/x86.h \
         \
           atomic_ops/sysdeps/hpc/hppa.h \
diff --git a/src/atomic_ops.h b/src/atomic_ops.h
index ec02ba4..59f04ef 100644
--- a/src/atomic_ops.h
+++ b/src/atomic_ops.h
 <at>  <at>  -294,6 +294,9  <at>  <at> 
 # if defined(__hexagon__)
 #   include "atomic_ops/sysdeps/gcc/hexagon.h"
 # endif
+# if defined(__tile__)
+#   include "atomic_ops/sysdeps/gcc/tile.h"
+# endif /* __tile__ */
 #endif /* __GNUC__ && !AO_USE_PTHREAD_DEFS */

 #if (defined(__IBMC__) || defined(__IBMCPP__)) && !defined(__GNUC__) \
diff --git a/src/atomic_ops/sysdeps/gcc/tile.h b/src/atomic_ops/sysdeps/gcc/tile.h
new file mode 100644
index 0000000..28dc083
--- /dev/null
+++ b/src/atomic_ops/sysdeps/gcc/tile.h
 <at>  <at>  -0,0 +1,52  <at>  <at> 
+/*
+ * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
+ * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
+ *
+ * Permission is hereby granted to use or copy this program
+ * for any purpose,  provided the above notices are retained on all copies.
+ * Permission to modify the code and to distribute modified code is granted,
+ * provided the above notices are retained, and a notice that the code was
+ * modified is included with the above copyright notice.
+ */
+
+/* Minimal support for tile. */
+
+#if (((__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8)) \
+     || __clang_major__ > 3 \
+     || (__clang_major__ == 3 && __clang_minor__ >= 4)) \
+     && !defined(AO_DISABLE_GCC_ATOMICS))
+
+# include "generic.h"
+
+#else /* AO_DISABLE_GCC_ATOMICS */
+
+#include "../all_atomic_load_store.h"
+
+#include "../test_and_set_t_is_ao_t.h"
+
+
+AO_INLINE void
+AO_nop_full()
+{
+  __sync_synchronize();
+}
+#define AO_HAVE_nop_full
+
+
+AO_INLINE AO_t
+AO_fetch_and_add_full (volatile AO_t *p, AO_t incr)
+{
+  return __sync_fetch_and_add(p, incr);
+}
+#define AO_HAVE_fetch_and_add_full
+
+
+AO_INLINE int
+AO_compare_and_swap_full(volatile AO_t *addr,
+                         AO_t old, AO_t new_val) 
+{
+  return __sync_val_compare_and_swap(addr, old, new_val) == old;
+}
+#define AO_HAVE_compare_and_swap_full
+
+#endif
--

-- 
1.7.1
Chris Metcalf | 2 May 17:42 2016

[Gc] [PATCH] gcconfig.h: Add machine description for TILE-Gx and TILEPro

---
For bdwgc:

This patch is an updated version of the CentOS 6 patch that we have
been carrying as part of our own CentOS-like distribution since 2012.

 include/private/gcconfig.h |   48 ++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 48 insertions(+), 0 deletions(-)

diff --git a/include/private/gcconfig.h b/include/private/gcconfig.h
index 760f896..beac61c 100644
--- a/include/private/gcconfig.h
+++ b/include/private/gcconfig.h
 <at>  <at>  -574,6 +574,14  <at>  <at> 
 #    define HEXAGON
 #    define mach_type_known
 # endif
+# if defined(__tile__) && defined(LINUX)
+#   ifdef __tilegx__
+#      define TILEGX
+#   else
+#      define TILEPRO
+#   endif
+#   define mach_type_known
+# endif

 # if defined(SYMBIAN)
 #   define mach_type_known
 <at>  <at>  -635,6 +643,8  <at>  <at> 
                     /*             CRIS       ==> Axis Etrax            */
                     /*             M32R       ==> Renesas M32R          */
                     /*             HEXAGON    ==> Qualcomm Hexagon      */
+                    /*             TILEPRO    ==> Tilera TILEPro        */
+                    /*             TILEGX     ==> Tilera TILE-Gx        */

 
 /*
 <at>  <at>  -2572,6 +2582,44  <at>  <at> 
 #   endif
 # endif

+# ifdef TILEPRO
+#   define CPP_WORDSZ 32
+#   define MACH_TYPE "TILEPro"
+#   define ALIGNMENT 4
+#   define ALIGN_DOUBLE
+#   define PREFETCH(x) __insn_prefetch(x)
+#   define CACHE_LINE_SIZE 64
+#   define USE_GENERIC_PUSH_REGS
+#   ifdef LINUX
+#     define OS_TYPE "LINUX"
+      extern int __data_start[];
+#     define DATASTART (ptr_t)(__data_start)
+#     define LINUX_STACKBOTTOM
+#     define DYNAMIC_LOADING
+#   endif
+# endif
+
+# ifdef TILEGX
+#   define CPP_WORDSZ (__SIZEOF_POINTER__ * 8)
+#   define MACH_TYPE "TILE-Gx"
+#   define ALIGNMENT __SIZEOF_POINTER__
+#   if CPP_WORDSZ < 64
+#     define ALIGN_DOUBLE /* Guarantee 64-bit alignment for allocations. */
+      /* Take advantage of 64-bit stores. */
+#     define CLEAR_DOUBLE(x) ((*(long long *)(x)) = 0)
+#   endif
+#   define PREFETCH(x) __insn_prefetch_l1(x)
+#   define CACHE_LINE_SIZE 64
+#   define USE_GENERIC_PUSH_REGS
+#   ifdef LINUX
+#     define OS_TYPE "LINUX"
+      extern int __data_start[];
+#     define DATASTART (ptr_t)(__data_start)
+#     define LINUX_STACKBOTTOM
+#     define DYNAMIC_LOADING
+#   endif
+# endif
+
 #if defined(__GLIBC__) && !defined(DONT_USE_LIBC_PRIVATES)
   /* Use glibc's stack-end marker. */
 # define USE_LIBC_PRIVATES
--

-- 
1.7.1
Andy Li | 12 Apr 21:33 2016
Picon
Gravatar

[Gc] website is down

Hi,

The website, http://hboehm.info/gc/, is currently down.
Is it under maintenance or something? 

Best regards,
Andy
_______________________________________________
bdwgc mailing list
bdwgc@...
https://lists.opendylan.org/mailman/listinfo/bdwgc
Eric Lindblad | 27 Mar 20:11 2016
Picon

[Gc] gc / Interix

To Whom m it May Concern,

I would enquire if you might assess what are the appropriate gc code modifications for porting to the
Interix sub-system. I am on SFU 3.5 Interix (32 bit) where I appropriated getopt.h, inttypes.h and
stdint.h from SFU 6.0 Interix, but I realise that there also have been released amd64 and ia64 Interix
versions. Though presently my interests are gc as a dependency for running the pager/text browser w3m
(where a static gc is suitable) if the Microsoft Corp. developers would oblige my request and resuscitate
the Interix project - beginning with 8.1 Microsoft no longer enabled new Windows versions for Interix -
the gc port (including shared libraries and threading) might be useful for other applications to be run
under SFU/SUA Interix.

I use WeirdX (http://www.jcraft.com/weirdx/) as a X Server with a tab window manager (twm).

Ohara for gc6.4.tar.gz on the Japanese webpage at http://air.s.kanazawa-u.ac.jp/~ohara/interix.html
in his "gc_interix.diff" (./configure --disable-threads --enable-cplusplus) has the following code:

# $OpenXM: OpenXM_contrib2/asir2000/gc_interix.diff,v 1.1 2004/02/27 18:32:21 ohara Exp $
--- include/private/gc_priv.h.orig	Tue Jun 24 14:11:42 2003
+++ include/private/gc_priv.h	Thu Feb 26 08:10:31 2004
 <at>  <at>  -19,6 +19,10  <at>  <at> 
 # ifndef GC_PRIVATE_H
 # define GC_PRIVATE_H

+#if defined(__INTERIX)
+#define __CYGWIN__
+#endif
+
 #if defined(mips) && defined(SYSTYPE_BSD) && defined(sony_news)
     /* sony RISC NEWS, NEWSOS 4 */
 #   define BSD_TIME

Where if one modifies include/private/gcconfig.h, it being obvious to add this '__INTERIX' clause 

# if defined(__INTERIX)
#   define I386
#   define INTERIX
#   define mach_type_known
# endif

which attends to the error message "include/private/gcconfig.h:456: error: parse error before '--'
token", on gc6.4.tar.gz, and, on newer versions, e.g.,  gc-7.2d.tar.gz, to the returned error message
"The collector has not been ported to this machine/OS combination.", for gc-6.8.tar.gz Martin Koeppe
(http://www.debian-interix.net/debian-interix/pool/unreleased35/main/libg/libgc/) has also
this code modification for include/private/gcconfig.h,

 #	undef STACK_GRAN
 #       define STACK_GRAN 0x10000
 #       define HEURISTIC1
+#   ifdef INTERIX
+#       define OS_TYPE "INTERIX"
+        extern int _data_start__[];
+        extern int _bss_end__[];
+#       define DATASTART ((ptr_t) _data_start__)
+#       define DATAEND   ((ptr_t) _bss_end__)
+#       define STACKBOTTOM ({ptr_t rv;           \
+             __asm __volatile ("movl %%fs:4,%%eax" \
+            :"=a"(rv)); rv;})
+#       define USE_MMAP
+#       define USE_MMAP_ANON
 #   endif
 #   ifdef OS2
 #	define OS_TYPE "OS2" 

and he adds this in configure.in.

 	AC_DEFINE(GC_AIX_THREADS)
 	AC_DEFINE(_REENTRANT)
 	;;
+     *-*-interix*)
+	AC_DEFINE(_REENTRANT)
+        ;;
      *-*-hpux11*)

Sincerely,
Eric Lindblad
http://www.nurmi-labs.blogspot.com

P.S. For some code compilation under Interix
one also adds the flag "-D_ALL_SOURCE".
Ivan Maidanski | 24 Mar 21:19 2016
Picon

[Gc] libatomic_ops CAS ordering constraints correspondence to C11 atomic ones

Hello Hans,

AO Readme.txt is a bit weak in respect to CAS ordering constraints. Let's fix it by mapping to C11 atomic memory ordering (based on common sense and inspection of libatomic_ops exsiting CAS assembly implementations).

Is the following correct?
|| AO CAS suffix || C11 CAS success || C11 CAS failure ||
| -            | __ATOMIC_RELAXED | __ATOMIC_RELAXED |
| acquire | __ATOMIC_ACQUIRE  | __ATOMIC_ACQUIRE |
| release | __ATOMIC_RELEASE  | __ATOMIC_RELAXED |
| full        | __ATOMIC_SEQ_CST  | __ATOMIC_ACQUIRE |

[1] https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html
[2] https://github.com/ivmai/libatomic_ops/blob/master/doc/README.txt 

--
Best regards,
Ivan
_______________________________________________
bdwgc mailing list
bdwgc@...
https://lists.opendylan.org/mailman/listinfo/bdwgc
John Mastro | 15 Mar 19:39 2016
Picon
Gravatar

[Gc] BDWGC and tagged pointers

Hello,

I suspect this question is quite basic, but I haven't been able to
figure it out on my own.

I'm implementing a small programming language and would like to use
BDWGC for garbage collection. I'm using tagged pointers, where the 3
least-significant bits can carry a type tag. The tagged value may be
either an immediate (e.g. an integer) or a pointer. In other words, I
have something like this:

    typedef intptr_t object;

    #define TAG_BITS 3
    #define VAL_MASK -(1 << TAG_BITS)

    enum obj_tag { TAG_INT = 1, TAG_LIST };

    typedef struct {
        object head, tail;
    } obj_list;

    #define make_integer(i)    (((i) << TAG_BITS) + TAG_INT)
    #define extract_integer(o) ((o) >> TAG_BITS)

    object make_list(object head, object tail)
    {
        obj_list *list = /* allocate it */;
        list->head = head;
        list->tail = tail;
        return ((intptr_t)list) + TAG_LIST;
    }

    #define extract_list(o) ((void *)((o) & VAL_MASK))

... which I think is pretty standard/boring. However, I believe I need
to teach BDWGC about this tagging, so it knows these `object` values may
(or may not) represent pointers, and I'm not sure how to do that.

Are there any documents, examples, or other help on how to accomplish
this?

Thanks,

John Mastro
Marek Vasut | 11 Mar 23:56 2016
Picon
Picon

[Gc] [PATCH] Add nios2 support via gcc helper

Add initial nios2 architecture support.

Signed-off-by: Marek Vasut <marex@...>
---
V2: Update the licensing text to match the rest
---
 src/Makefile.am                    |  1 +
 src/atomic_ops.h                   |  3 +++
 src/atomic_ops/sysdeps/gcc/nios2.h | 17 +++++++++++++++++
 3 files changed, 21 insertions(+)
 create mode 100644 src/atomic_ops/sysdeps/gcc/nios2.h

diff --git a/src/Makefile.am b/src/Makefile.am
index fc09b27..d463427 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
 <at>  <at>  -79,6 +79,7  <at>  <at>  nobase_private_HEADERS = atomic_ops/ao_version.h \
           atomic_ops/sysdeps/gcc/ia64.h \
           atomic_ops/sysdeps/gcc/m68k.h \
           atomic_ops/sysdeps/gcc/mips.h \
+          atomic_ops/sysdeps/gcc/nios2.h \
           atomic_ops/sysdeps/gcc/powerpc.h \
           atomic_ops/sysdeps/gcc/s390.h \
           atomic_ops/sysdeps/gcc/sh.h \
diff --git a/src/atomic_ops.h b/src/atomic_ops.h
index 33fe00e..ec02ba4 100644
--- a/src/atomic_ops.h
+++ b/src/atomic_ops.h
 <at>  <at>  -262,6 +262,9  <at>  <at> 
 # if defined(__m68k__)
 #   include "atomic_ops/sysdeps/gcc/m68k.h"
 # endif /* __m68k__ */
+# if defined(__nios2__)
+#   include "atomic_ops/sysdeps/gcc/nios2.h"
+# endif /* __nios2__ */
 # if defined(__powerpc__) || defined(__ppc__) || defined(__PPC__) \
      || defined(__powerpc64__) || defined(__ppc64__)
 #   include "atomic_ops/sysdeps/gcc/powerpc.h"
diff --git a/src/atomic_ops/sysdeps/gcc/nios2.h b/src/atomic_ops/sysdeps/gcc/nios2.h
new file mode 100644
index 0000000..7fb7400
--- /dev/null
+++ b/src/atomic_ops/sysdeps/gcc/nios2.h
 <at>  <at>  -0,0 +1,17  <at>  <at> 
+/*
+ * Copyright (C) 2016 Marek Vasut <marex@...>
+ *
+ * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
+ * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
+ *
+ * Permission is hereby granted to use or copy this program
+ * for any purpose,  provided the above notices are retained on all copies.
+ * Permission to modify the code and to distribute modified code is granted,
+ * provided the above notices are retained, and a notice that the code was
+ * modified is included with the above copyright notice.
+ */
+
+#include "../test_and_set_t_is_ao_t.h"
+#include "generic.h"
+
+#define AO_T_IS_INT
--

-- 
2.7.0
sigint | 10 Mar 10:22 2016
Picon

[Gc] Wrong __data_start/_end pair Abort


Hi,

when I compile and run the following code, I get a message and an Abort. 
When I run it in gdb

$ cat test.c

#include "gc.h"

int main () {
     int *p;
     GC_INIT():
     p = GC_MALLOC(sizeof(int));
     return 0;
}

$ gcc test.c -lgc

$ ./a.out
Wrong __data_start/_end pair
Aborted

$ uname -a
Linux localhost 3.10.49 #1 SMP PREEMPT Mon Nov 16 12:46:20 CST 2015 
armv71 Android

Any suggestion on how to proceed. gdb did not show anything interesting.

Thanks.

Gmane