8000 doc&fix: explain gc&fix macro · RustPython/RustPython@a98b40a · GitHub
[go: up one dir, main page]
Skip to content

Commit a98b40a

Browse files
discord9discord9
committed
doc&fix: explain gc&fix macro
1 parent 185d167 commit a98b40a

File tree

2 files changed

+108
-0
lines changed

2 files changed

+108
-0
lines changed

‎derive-impl/src/pytrace.rs

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
use proc_macro2::TokenStream;
2+
use quote::quote;
3+
use syn::{AttributeArgs, DeriveInput, Result};
4+
5+
/// also remove `#[notrace]` attr, and not trace corresponding field
6+
fn gen_trace_code(item: &mut DeriveInput) -> Result<TokenStream> {
7+
match &mut item.data {
8+
syn::Data::Struct(s) => {
9+
let fields = &mut s.fields;
10+
if let syn::Fields::Named(ref mut fields) = fields {
11+
let res: TokenStream = fields
12+
.named
13+
.iter_mut()
14+
.map(|f| {
15+
let name = f
16+
.ident
17+
.as_ref()
18+
.expect("Field should have a name in non-tuple struct");
19+
let mut do_trace = true;
20+
f.attrs.retain(|attr| {
21+
// remove #[notrace] and not trace this specifed field
22+
if attr.path.segments.last().unwrap().ident == "notrace" {
23+
do_trace = false;
24+
false
25+
} else {
26+
true
27+
}
28+
});
29+
if do_trace {
30+
quote!(
31+
::rustpython_vm::object::Trace::trace(&self.#name, tracer_fn);
32+
)
33+
} else {
34+
quote!()
35+
}
36+
})
37+
.collect();
38+
Ok(res)
39+
} else {
40+
panic!("Expect only Named fields")
41+
}
42+
}
43+
syn::Data::Enum(_) => todo!(),
44+
syn::Data::Union(_) => todo!(),
45+
}
46+
}
47+
48+
pub(crate) fn impl_pytrace(attr: AttributeArgs, mut item: DeriveInput) -> Result<TokenStream> {
49+
if !attr.is_empty() {
50+
panic!(
51+
"pytrace macro expect no attr(s), found {} attr(s)",
52+
attr.len()
53+
);
54+
}
55+
56+
let trace_code = gen_trace_code(&mut item)?;
57+
58+
let ty = &item.ident;
59+
60+
let ret = quote! {
61+
#item
62+
#[cfg(feature = "gc_bacon")]
63+
unsafe impl ::rustpython_vm::object::Trace for #ty {
64+
fn trace(&self, tracer_fn: &mut ::rustpython_vm::object::TracerFn) {
65+
#trace_code
66+
}
67+
}
68+
};
69+
Ok(ret)
70+
}

‎vm/src/object/gc/mod.rs

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,41 @@
1+
//! This is a simple stop-the-world coloring Garbage Collector implementation.
2+
//! Here is the basic idea:
3+
//! 1. We use a `Collector` to manage all the `GcObj`s.
4+
//! 2. We use a `GcHeader` to manage the `GcObj`'s color and ref count.
5+
//!
6+
//! And the basic algorithm is from this paper: Concurrent Cycle Collection in Reference Counted Systems David F.Bacon and V.T.Rajan
7+
//! the paper is here: https://dl.acm.org/doi/10.5555/646158.680003
8+
//! So let me explain the algorithm a bit in my word:
9+
//! Here I only implement the stop-the-world version of this algorithm, because concurrent version is a bit complex and require write barrier.
10+
//! So the basic ideas here is:
11+
//! 1. each object have three fields for GC, `buffered`(a bool), `color`(a enum), `ref_cnt`(a usize), the original paper have seven color,
12+
//! but in our sync version there only need four color, which is the following:
13+
//! | color | meaning |
14+
//! | ----- | ------- |
15+
//! | Black | In use or free |
16+
//! | Gray |Possible member of cycle |
17+
//! | White | Member of garbage cycle |
18+
//! | Purple| Possible root of cycle |
19+
//!
20+
//! All objects start out black:
21+
//! 1. when ref count is incremented, object is colored `Black`, since it is in use, it can not be garbage.
22+
//! 2. When ref count is decremented, if it reach zero, it is released, And recursively decrement ref count on all its children.
23+
//! else object is colored `Purple`, since it is considered to be a possible root of a garbage cycle(and buffered for delayed release).
24+
//! 3. When releasing a object, first color it as `Black`(So later delayed release can know to free it) if it's NOT buffered, free it now, else reserve it for delayed release.
25+
//! 4. Here comes the major Garbage Collection part, when certain condition is met(i.e. the root buffer is full or something else), we start a GC:
26+
//! The GC is in three phrase: mark roots, scan roots and finally collect roots
27+
//! 4.1. In mark roots phrase, we look at all object in root buffer, if it is `Purple` and still have non-zero
28+
//! ref count, we call `MarkGray` to color it `Gray` and recursively mark all its children as `Gray`,
29+
//! else it's pop out of buffer, and released if ref count is zero.
30+
//! there we have a lot of possible member of cycle.
31+
//! 4.2. Therefore we must found the real garbage cycle, hence the `ScanRoot` phrase,
32+
//! where we call `Scan` for every remaining object in root buffer,
33+
//! which will try and find live data in the cycle: if it finds a `Gray` object with ref count being non-zero,
34+
//! the object itself and all its children are colored `Black` and this part cycle is considered to be live. This is done by call `ScanBlack`.
35+
//! else if it is zero ref count `Gray` object, it is colored `White` and the cycle is considered to be garbage. The recurisve call of `Scan` continue.
36+
//! 4.3. CollectRoots, at this stage, there is no `Gray` object left, and all `White` object are garbage, we can simply go from root buffer and collect all `White` object for final garbage release,
37+
//! just need to note that when `CollectWhite` those `buffered` object do not need to be freed, since they are already buffered for later release.
38+
139
mod collector;
240
mod header;
341
mod trace;

0 commit comments

Comments
 (0)
0