A new direction...

[Adek336]

This sounds interesting! I would love to see such system in action, for once..

Well, instead of names you could pass integers. An array would hold the proper info, and you wouldn't spend time on searching for the object by name.

Then again, if we used integers we might as well stick to pointers, which are more effective and useful. If something happened to the integer, a wrong object would be found. If a string would happen to be damaged, the program would know about it through an error message from the object manager.

That being said- it might be only a matter of checking, if we've got the proper object, huh?

Code: Select all

struct
 {
    uint64 id;    //the offset in the array of objects, a unique id
    uint64 magic;  //something like the multiboot checksum for a struct
    uint64 crc;   //the crc of 
    uint64 object_type; //if another object_type is found in the array, report error
    char name[200];      //compare this name and the value in the array. if do not match, lookup the name
 } MemoryPointerReplacementType;

Beside the id member, only one of the others would need to be included in the struct. Especially the last one, char name[200] seems a clever way to have the objects represented by their names. Most of the time, only a single check would need to be performed if it is the correct object. Those rare moments, where the id was incorrect, the manager would perform a lookup. This would boost speed for mystran's design.

Cheers,
Adrian

[Colonel Kernel]

Why not use a traditional garbage collection scheme instead? The performance would be much, much better than using indirect handles through a table. There is no overhead for referencing objects, since pointers are used under the hood. As for moving things around in memory, a GC will usually freeze all running threads, find all the "roots" (static, stack-based, and register-based pointers to objects), create a graph of all reachable objects from the roots, then collect the unreachable ones and compact memory.

Actually, this is another argument for not doing any of this stuff in the kernel -- all threads in the system would have to be suspended while the GC runs, rather than just all the threads in the process whose address space is being cleaned up.

[Dreamsmith]

As for moving things around in memory, a GC will usually freeze all running threads, find all the "roots" (static, stack-based, and register-based pointers to objects), create a graph of all reachable objects from the roots, then collect the unreachable ones and compact memory.

Actually, this is another argument for not doing any of this stuff in the kernel -- all threads in the system would have to be suspended while the GC runs, rather than just all the threads in the process whose address space is being cleaned up.

No no no. Extremely naive, simple, and primitive GC might do this. Industrial quality GC goes NOT require ANY threads to be suspended during garbage collection. If you're controlling the language rather than just providing a GC collection library to a language that doesn't have built in GC, there's no reason at all whatsoever to suspend anything while collecting garbage. With language support for it, you can do it completely safely and transparently while threads continue to run.

[Colonel Kernel]

No no no. Extremely naive, simple, and primitive GC might do this. Industrial quality GC goes NOT require ANY threads to be suspended during garbage collection.

Are the JVM and CLR not industrial quality then? AFAIK, this is how they work.

If you're controlling the language rather than just providing a GC collection library to a language that doesn't have built in GC, there's no reason at all whatsoever to suspend anything while collecting garbage. With language support for it, you can do it completely safely and transparently while threads continue to run.

What is it about controlling the language that allows you to do this? How does it eliminate the fundamental race conditions involved in moving shared blocks of memory around in the heap...? I'm not talking about add-on GC libraries here, I'm talking about (popular) modern OO VMs...

[mystran]

Well, instead of names you could pass integers. An array would hold the proper info, and you wouldn't spend time on searching for the object by name.

Ofcourse you'd use integers. The best way would probably be a simple pointer to pointer.

Then again, if we used integers we might as well stick to pointers, which are more effective and useful. If something happened to the integer, a wrong object would be found. If a string would happen to be damaged, the program would know about it through an error message from the object manager.

Like, my idea would be that have pointers to entries in one large table.. and have table entries that aren't resident in memory point to a zero-page or something.

Now, if the object is resident, you have a pointer to pointer to object. You therefore take a small performance penalty from the extra indirection. However, some garbage-collected languages/systems do it this way anyway, since it allows one to move objects around, which is nice for reducing heap fragmentation. If the object is not resident, then you have pointer to pointer to NULL, and you get a trap to VMM when dereferencing it. VMM can page the object in, fix the pointer, and resume.

If you use direct pointers, you are limited to 4GB total address space. If you dereference through an intermediate pointer, you can put any object in memory anywhere, as long as you have less than 4GB of objects in total mapped.

And I am NOT agaist traditional GC's. I just had this idea about how to get around the address space size limit. You can still collect garbage any way you want. But if you use direct pointers, you have to fit all stuff into 4GB, which would means you pretty much need separate address spaces for separate processes.

And indeed, a good GC does NOT suspend anything when collecting. There needs to be some amount of synchronization, but locks can be kept to a few cycles now and then, so the performance penalty is next to none (although to fully optimize this you need VMM support for it).

As for causing small delays now and then, with uniprocessor your only option is timesharing, which means that obviously when the collector runs, your other threads do not. The point is that garbage collector can be just like any other regular thread: it can be pre-empted at any time.

[Legend]

But I guess not while working on one object, perhaps between two objects, or not?

[Dreamsmith]

What is it about controlling the language that allows you to do this? How does it eliminate the fundamental race conditions involved in moving shared blocks of memory around in the heap...?

If you control the language, it makes it very easy to ensure that all blocks of memory are properly colored. GC decides what can be collected and what can't based on its color. New memory allocations and references during GC are not a problem because they color the memory blocks in a way that allows the GC to know they're in use, even if they weren't when it started its mark phase. As for moving shared blocks of memory about -- don't. That's "stop and copy" GC, the most simple (and most primitive) form of garbage collection out there. Even simply switching to "mark and sweep" GC will give a dramatic improvement in speed and make implementing thread-safe GC much easier. You don't get the benefits of compacting the heap with "mark and sweep" GC, but if you want to be thread-friendly, you don't try to kill two birds with one stone. You use mark and sweep on the top level to free memory, and you use whatever generational GC algorithm you decide on for heap compaction.

(As far as my personal terminology goes, it's the point where generational algorithms are implemented that GC becomes "industrial strength". As for your question about whether JVM qualifies or not, I have no idea. I imagine it would depend on the JVM. Does whichever JVM you were refering to implement generational GC? Does it GC without suspending the system? If the answers to these are yes, then yes, it's industrial quality GC. If the answer to either is no, then no.)

[Dreamsmith]

Are the JVM and CLR not industrial quality then? AFAIK, this is how they work.

Ah, just figured out what you're refering to by CLR -- sorry, I'm not a Microsoft wonk, I know almost nothing about .Net and related stuff. I will say, when I'm refering to "industrial quality", I'm taking the word "industrial" seriously. You don't find many "industrial quality" algorithms implemented in any desktop OS -- it'd be overkill. Windows isn't an RTOS, expecting anything running under it to have an "industrial quality" implementation is silly -- no point if the OS itself can't give you the kind of timing guarentees you need. Implementing industrial quality GC is not a trivial task, and if you're going to turn around and run it under an OS like Windows, there'd be no point. I'd be surprised if CLR has anything more sophisticated than your typical toy GC...

[Colonel Kernel]

I get what you mean by industrial now. I didn't think that real-time GC was even possible.

The CLR uses a generational compacting GC. The literature claims that a typical run of the GC takes about as much time as it takes to satisfy a page fault. I'll see if I can dig up some links later today.

[Dreamsmith]

Interesting. I know Java was originally intended for embedded work, but got co-opted into the web-dodad and eventually "weblication" work. I've never really looked into CLR, I'd just heard it was Microsoft's answer to JVM. Are they also looking at getting this into the embedded arena? If so, they might actually put some more work into "industrial" concerns.

As for real time GC, yes, that's quite possible, and indeed quite a bit of work has been done in that area. It makes sense -- GC avoids a lot of the kinds of problems that can be real killers to embedded applications (in a low memory environment, memory leaks are serious problems), and it can actually be faster than traditional memory allocation in a lot of cases (e.g. think how often you're calling free() in some apps -- now imagine the time savings of simply removing all your free() calls). And it's really not too difficult to make mark and sweep GC thread-friendly. Implementing compacting generational GC on top of that gets tricky, but it can be done without disrupting the system.

I should add, under an RTOS, you don't even need to keep GC thread-friendly. In an RTOS, you know how much time you have before you need to deal with something else. In that case, you can just use incremental GC, only doing as much as you have time for before moving on.

[Colonel Kernel]

Here are links to the MSDN articles I mentioned. "Garbage Collection: Automatic Memory Management in the Microsoft .NET Framework".

Part One
Part Two

[Schol-R-LEA]

It could be pointed out that even with garbage collection, it can be useful to have more than one level of memory management. For example, one could have a system-level collector which manages large blocks of memory, while process level memory management could be used for fine-grained memory allocation. One could potentially break it down further to thread-level memory management, but that's probably not useful, as threads generally share at least some objects within a process. This would allow each process to have it's own memory policies, while still ensuring that at the top level memory is eventually reclaimed even while the process that used it is running. While not required under such a scheme, process level garbage collection (as opposed to manual memory deallocation) would still be preferred, as such an approach would still be potentially subject to certain kinds of memory leaks.

There would by necessity be some communication between levels, as the top level must know when there are no longer any references to any objects in a memory block, while the process level allocator must know what blocks are in fact still available to use.

One potential approach which I've thought of (which does not imply originality, as others have presumably discovered thios approach before) is to combine top-level memory allocation with the paging system in what might be called a "stop and don't copy" algorithm. Simply put, the top level manager would allocate memory as a full virtual memory page. Whenever a page is to be swapped in or out, the garbage collector would determine if there are any references to the area of memory the page is mapped to, and if not, it just deallocates the page instead of swapping it. The easiest way to handle this is to have the process level memory manager keep track of memory references across pages (which to the process level GC are simply blocks of available memory), and pass that information to the top-level collector when requested (i.e., after a page fault).

Since this is at this point just a concpet, I do not know all the subtleties and flaws in this approach. I do know it is potentially complicated by the fact that the process-level memory manager is running within the process, and thus sees the process's memory space as if it were contiguous whole system memory; for it to then have to deal with memory as separate blocks of a fixed size may be awkward. This can be a good thing, too, though, as it allows the process level garbage collector to be simpler than it would be otherwise; it can simply treat the blocks given to it by the top-level allocator as part of linear memory, and doesn't have to worry about the memory use of other processes.



Comments and criticisms welcome.