OSDev.org

Hi. I'm trying to implement GC. but i have to know whether the specific address is being accessed. is there anything like CR2 register? Like when i access a invalid address it will trigger irq 0xE. and the address will be stored in CR2 regiser. and i want to get something like it.

On Intel (and presumably other architectures), each page table entry has an accessed "A" bit that you can use for this purpose.

See https://wiki.osdev.org/Paging for some details.

kzinti wrote:On Intel (and presumably other architectures), each page table entry has an accessed "A" bit that you can use for this purpose.

See https://wiki.osdev.org/Paging for some details.

helpful! but is there anyway to get it more accurate? the minimum class size can be 8 bytes but the page size is 4096bytes

Well you can mark the page as "not present" by not setting the P bit. Then you will get page faults and you can record which address is being accessed (and determine if it is for a read or a write). But this is not going to be efficient as a page fault on every memory access is rather expensive.

You can also just make the page read-only, In this case you will only get page fault son writes (and can use the Accessed bit to detect if there were any reads). This is probably what you want for a GC. But I don't think you'll get better than 4KB granularity.

For GC, surely you want to know whether the address is capable of being accessed rather than if it actually has been accessed?

iansjack wrote:For GC, surely you want to know whether the address is capable of being accessed rather than if it actually has been accessed?

There are many optimization tricks that can be done in a GC implementation by unmapping pages or mapping them read-only.

For example once you compact objects into a new location, you can unmap the old location pages of these objects and if anything still holds reference to them, it will trigger page faults and you can lazily fix up these references.

There are other tricks, but I have a hard time remembering the details as it has been over 20 years since I looked at implementing GCs.

Weather or not using page faults is efficient with modern processors would be a good question.

Yes, but then you are asking whether a particular page has been accessed, which is easy, rather than a particular address.

1) About the question whether there is a way to know if a sub-page byte range has been accessed, the answer is no. Why, you may ask, such a feature does not exist? Let's say that there was a way to (for example) get the information of which bytes in RAM have been accessed since you told the hardware to start monitoring. Then for each byte (8 bits) there would exist one more bit holding the "have been accessed" information, so a 8GB System that would need plus 1GB of storage. I think that the problem is obvious.
2) As iansjack explained, for a GC you don't care if the object has been accessed but whether it can be accessed.
(An object may not get accessed for several passes of the GC, yet it may be referenced by a static variable and therefore it should remain in the RAM as it can get accessed in the future) So how you can do that? https://en.wikipedia.org/wiki/Garbage_c ... r_science), specifically, take a look at the Strategies Section.

The 2 most common approaches are:
A) Tracing For high level (and Object Oriented) programing languages: .NET (C#, VB, F#), Java, ...
Basically, you start at the "Roots" (all the places that an object can be immediately accessed, i.e. registers, static varables, stack, ...) and then for each object you find, you mark it as "accessible". Then you continue by checking each object's fields for pointers to further objects until each and every accessible object has been marked "accessible". Then you free the rest of the memory.
B) Reference Counting For lower level environments (not particularly for Object Oriented), the Windows kernel uses that for objects that can be accessed by several components and/or programs such as: files, events, threads, ...
Basically, when you want to firstly access the object (i.e. you open a file, represented by an object) you increment a counter in the object's header by one. When you don't want the object anymore (i.e. close the file) you decrement the counter by one. When the counter reaches zero (i.e. none is operating on the file) the object gets freed.

Footnotes:
1) In both strategies I am skipping many minor (yet important) details, check the links for a better description and different sub-strategies.
2) Many people refer to "Tracing Garbage Collection" as "Garbage Collection".
3) About kzinti's (last) answer, I think that you need to first implement a GC that works and then try to use those kinds of tricks. (In my opinion, without any testing whatsoever, I think that using page-faults for lazy reference updates is just to slow. I am actually interested in that so if anyone can provide further information on that it would be really helpful).

Coconut9 wrote: 2) As iansjack explained, for a GC you don't care if the object has been accessed but whether it can be accessed.
(An object may not get accessed for several passes of the GC, yet it may be referenced by a static variable and therefore it should remain in the RAM as it can get accessed in the future) So how you can do that? https://en.wikipedia.org/wiki/Garbage_c ... r_science), specifically, take a look at the Strategies Section.

The 2 most common approaches are:
A) Tracing For high level (and Object Oriented) programing languages: .NET (C#, VB, F#), Java, ...
Basically, you start at the "Roots" (all the places that an object can be immediately accessed, i.e. registers, static varables, stack, ...) and then for each object you find, you mark it as "accessible". Then you continue by checking each object's fields for pointers to further objects until each and every accessible object has been marked "accessible". Then you free the rest of the memory.

My kernel uses a tracing garbage collector.

It started out as a simple slab allocator, with each page in the heap having the same type (or size) of object, and it struck me that it would be simple (and fast) to take an arbitrary pointer, and determine exactly which slab it came from so it can be marked as in use.

As an experiment, I investigated going the whole hog and implementing a full garbage collector, with optional per-object finalizer. Global GC roots are annotated in the C source and put in their own section in the linker script, making it easy to determine the global roots. From the global roots, we can reach all the active threads, and their corresponding register and stack state, and therefore trace to all live objects. I have weak references for use in caches, and the each physical page is described by a GC'd structure, so even the physical memory frames are managed by the GC (free'd in the finalizer).

It was a couple of weeks of evenings work from concept to working GC.

My slab allocator/GC is less than 700 lines of code C code, which can be found here. Feel free to peruse.

A full GC cycle is:

• slab_gc_begin()
• slab_gc()
• slab_gc_end()

Caveats:

This GC is similar to the Boehm GC, in that it is a conservative garbage collector that traces from the roots anything that may look like a pointer, ruling a reference out as a heap reference based on whether it points into the heap region, and if it does, marking such memory as in use (whether the referenced being traced is a pointer or just some integer that happens to also look like a heap pointer. There may be denial of service security implications of this, so we have to make sure we don't reference and trace user provided data.

The GC is essentially stop the world, as my kernel is uniprocessor. In mitigation, GC can be run in idle time, to keep memory available, and prevent stalls from memory shortages triggering a GC cycle.

The GC has no concurrency, so as and when I do SMP, I'll have to stop kernel level threads on other processors, though there is no reason user level threads cannot continue in parallel.