On 2013-10-15 05:11, Michel Fortin wrote:

> mprotect isn't available at all with the iOS SDK. So making this
> collector work on iOS (and the iOS Simulator) would require a different
> codegen.

I haven't tried compiling anything and I don't know if I'm looking in the correct file but this file:

/Applications/Xcode.app/Contents/Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS7.0.sdk/usr/include/sys/mman.h

Does contain "mprotect".

-- 
/Jacob Carlborg

On 2013-10-15 02:20:49 +0000, "deadalnix" <deadalnix@gmail.com> said:

> It will indeed cause trouble for code that mutate a large amount of shared pointers. I'd say that such code is probably asking for trouble in the first place, but as always, no silver bullet. I still think solution is the one that fit D the best.

I think there's a small mistake in your phrasing, but it makes a difference.

When the collector is running, it needs to know about any mutation for pointers to its shared memory pool, including pointers that are themselves thread-local but point to shared memory. So COW will be trouble for code that mutate a large amount of **pages containing pointers to shared memory**. And this which includes **pointers to immutable data** because immutable is implicitly shared. And this includes **pointers to const data** since those pointers might point to immutable (thus shared) memory.

So any memory page susceptible of containing pointers to shared memory would need to use COW during collection. Which means all the thread's stacks, and also all objects with a pointer to shared, immutable, and const data. At this point I think it is fair to approximate this to almost all memory that could contain pointers.

-- 
Michel Fortin
michel.fortin@michelf.ca
http://michelf.ca

On 2013-10-15 07:28:16 +0000, Jacob Carlborg <doob@me.com> said:

> On 2013-10-15 05:11, Michel Fortin wrote:
> 
>> mprotect isn't available at all with the iOS SDK. So making this
>> collector work on iOS (and the iOS Simulator) would require a different
>> codegen.
> 
> I haven't tried compiling anything and I don't know if I'm looking in the correct file but this file:
> 
> /Applications/Xcode.app/Contents/Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS7.0.sdk/usr/include/sys/mman.h

Does 
> 
> contain "mprotect".

You're right. Yes it does exist. I was confused.

Not only it does exist, but it lets you set the executable bit. I find that depressing, since I'm pretty sure App Store apps are prevented from setting the executable bit, and I'd tend to think now that they're blocking it by checking for references to mprotect it in the executable when submitting to the App Store. And by doing it this way they probably wouldn't be able to distinguish between setting the executable bit or making a page read-only.

Also, someone would need to check that Windows Phone apps and Windows 8-style (Metro) apps can access mprotect (or equivalent) too. They're sandboxed just as heavily and statically checked upon submission the same way.

Could some game consoles out there block it too?

-- 
Michel Fortin
michel.fortin@michelf.ca
http://michelf.ca

On Tuesday, 15 October 2013 at 11:03:01 UTC, Michel Fortin wrote:
> On 2013-10-15 02:20:49 +0000, "deadalnix" <deadalnix@gmail.com> said:
>
>> It will indeed cause trouble for code that mutate a large amount of shared pointers. I'd say that such code is probably asking for trouble in the first place, but as always, no silver bullet. I still think solution is the one that fit D the best.
>
> I think there's a small mistake in your phrasing, but it makes a difference.
>
> When the collector is running, it needs to know about any mutation for pointers to its shared memory pool, including pointers that are themselves thread-local but point to shared memory. So COW will be trouble for code that mutate a large amount of **pages containing pointers to shared memory**. And this which includes **pointers to immutable data** because immutable is implicitly shared. And this includes **pointers to const data** since those pointers might point to immutable (thus shared) memory.
>

No, that is the beauty of it :D

Consider you have pointer from Tl -> shared -> immutable and TL -> immutable.

I'm not covering TL collection here (It seem to be obvious that it doesn't require to stop the world). So the starting point is that we have the roots in all TL heaps/stacks, and we want to collect shared/immutable without blocking the worlds.

TL heap may get new pointers to the shared heap, but they can only come from the shared heap itself or new allocations. At this point, you consider every new allocations as live.

Reading a pointer from the shared heap and copy it to the TL heap isn't problematic in itself, but then we have a problem if this pointer is now updated in the shared heap, as the GC may never scan this pointer.

This is why you need to track pointer writes to the shared heap. The write value itself isn't important : it come from either new alloc that are live, or from somewhere else in the shared heap (so it will be scanned as we track writes).

> So any memory page susceptible of containing pointers to shared memory would need to use COW during collection. Which means all the thread's stacks, and also all objects with a pointer to shared, immutable, and const data. At this point I think it is fair to approximate this to almost all memory that could contain pointers.

No, only the shared one, that is the beauty of the technique. Not that I'm not making that up myself, it is how GC used to work in the Caml family for a while, and it has proven itself really efficient (in Caml family, most data are either immutable or thread local, and the shared heap typically small).

On 2013-10-15 18:32:01 +0000, "deadalnix" <deadalnix@gmail.com> said:

> No, that is the beauty of it :D
> 
> Consider you have pointer from Tl -> shared -> immutable and TL -> immutable.
> 
> I'm not covering TL collection here (It seem to be obvious that it doesn't require to stop the world). So the starting point is that we have the roots in all TL heaps/stacks, and we want to collect shared/immutable without blocking the worlds.
> 
> TL heap may get new pointers to the shared heap, but they can only come from the shared heap itself or new allocations. At this point, you consider every new allocations as live.
> 
> Reading a pointer from the shared heap and copy it to the TL heap isn't problematic in itself, but then we have a problem if this pointer is now updated in the shared heap, as the GC may never scan this pointer.
> 
> This is why you need to track pointer writes to the shared heap. The write value itself isn't important : it come from either new alloc that are live, or from somewhere else in the shared heap (so it will be scanned as we track writes).

But you still have to scan the thread-local heaps and stacks to find pointers to shared memory. If you don't stop those threads, how do you know one of these threads isn't moving a pointer value during the scan from one place the GC still has to scan to another that the GC has just scanned, making it so the GC never sees the pointer?

For instance:

	class A {
		// string is immutable and points to shared heap
		immutable(char)[] s;
	}

	A global;

	void func()
	{
		// GC scans the stack of this thread in the background
		// no reference to our string on the stack

		// moving string pointer to the stack
		// while the GC is running
		auto tmp = global.s;
		global.s = null;

		// GC scans the heap of this thread in the background
		// no reference to our string on the heap
		// (missed reference to our string now on the stack)
	}

The thread can move the pointer around while the GC is looking away and you'll end up with a pointer to a freed string. So you have to use COW for the thread's stack, or get notified of a pointer assignment somehow (or of a pointer move), or stop the thread while you're scanning its heap.

-- 
Michel Fortin
michel.fortin@michelf.ca
http://michelf.ca

Yes and no.

You obviously need to scan TL heaps at some point. When doing so you'll have a set of root that allow you to scan shared/immutable heap. What is going on in the TL heap become irrelevant once you have the root. And getting the roots from the TL heap is another problem altogether (any kind of GC can be used for that, stop the world, where the world is thread local, or another concurrent GC, the important point being that it is an independent problem).

Am 14.10.2013 22:59, schrieb Paulo Pinto:
>
>
> Well, if real time concurrent GC for Java systems is good enough for
> systems that control militar missile systems, maybe it is good enough
> for real-time audio as well.
>
> --
> Paulo

The problem is not that there are no GCs around in other languages which satisfy certain requirements. The problem is actually implementing them in D. I suggest that you read "The Garbage Collection Handbook" which explains this in deep detail. I'm currently reading it, and I might write an article about the entire D GC issue once I'm done with it.

On Oct 16, 2013, at 11:54 AM, Benjamin Thaut <code@benjamin-thaut.de> wrote:
> 
> The problem is not that there are no GCs around in other languages which satisfy certain requirements. The problem is actually implementing them in D. I suggest that you read "The Garbage Collection Handbook" which explains this in deep detail. I'm currently reading it, and I might write an article about the entire D GC issue once I'm done with it.

I think the short version is that D being able to directly call C code is a huge problem here.  Incremental GCs all rely on the GC being notified when pointers are changed.  We might be able to manage it for SafeD, but then SafeD would basically be its own language.

Am 16.10.2013 20:54, schrieb Benjamin Thaut:
> Am 14.10.2013 22:59, schrieb Paulo Pinto:
>>
>>
>> Well, if real time concurrent GC for Java systems is good enough for
>> systems that control militar missile systems, maybe it is good enough
>> for real-time audio as well.
>>
>> --
>> Paulo
>
> The problem is not that there are no GCs around in other languages which
> satisfy certain requirements. The problem is actually implementing them
> in D. I suggest that you read "The Garbage Collection Handbook" which
> explains this in deep detail. I'm currently reading it, and I might
> write an article about the entire D GC issue once I'm done with it.
>

I have read it when it came out in the late 90's.

My main focus areas in the university were compiler design, distributed systems and graphics programming.

Although, like many, I tend to do plain boring enterprise applications nowadays.


--
Paulo

On 2013-10-16 21:05, Sean Kelly wrote:

> I think the short version is that D being able to directly call C code is a huge problem here.  Incremental GCs all rely on the GC being notified when pointers are changed.  We might be able to manage it for SafeD, but then SafeD would basically be its own language.

One need to be very careful with the memory when interfacing with C code today. What about having a function that notifies the GC that a pointer has been updated?

-- 
/Jacob Carlborg