go_vm/
gc.rs

1// Copyright 2022 The Goscript Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5use super::instruction::ValueType;
6use super::objects::*;
7use super::value::{GosValue, RCQueue, RCount, IRC};
8use std::cell::Ref;
9use std::cell::RefCell;
10use std::convert::TryFrom;
11use std::rc::{Rc, Weak};
12
13pub struct GcContainer {
14    inner: Rc<RefCell<Vec<GcWeak>>>,
15}
16
17impl GcContainer {
18    pub fn new() -> GcContainer {
19        GcContainer {
20            inner: Rc::new(RefCell::new(Vec::new())),
21        }
22    }
23
24    pub fn add_array(&self, arr: &Rc<(GosArrayObj, RCount)>) {
25        self.add_weak(GcWeak::new_array(arr))
26    }
27
28    pub fn add_closure(&self, cls: &Rc<(ClosureObj, RCount)>) {
29        self.add_weak(GcWeak::new_closure(cls))
30    }
31
32    pub fn add_map(&self, m: &Rc<(MapObj, RCount)>) {
33        self.add_weak(GcWeak::new_map(m))
34    }
35
36    pub fn add_struct(&self, s: &Rc<(StructObj, RCount)>) {
37        self.add_weak(GcWeak::new_struct(s))
38    }
39
40    #[inline]
41    pub(crate) fn add_weak(&self, w: GcWeak) {
42        self.inner.borrow_mut().push(w);
43    }
44
45    fn borrow_data(&self) -> Ref<Vec<GcWeak>> {
46        self.inner.borrow()
47    }
48}
49
50#[derive(Clone)]
51pub(crate) enum GcWeak {
52    Array(Weak<(GosArrayObj, RCount)>),
53    Closure(Weak<(ClosureObj, RCount)>),
54    Map(Weak<(MapObj, RCount)>),
55    Struct(Weak<(StructObj, RCount)>),
56    // todo:
57    // GC doesn't support channel for now, because we can't access the
58    // underlying objects (unless we don't use smol::channel and write
59    // it ourself).
60    // but memory leaking circles that involve channels should be very
61    // rare, so in practice we may not need it at all.
62    //Channel(Weak<(RefCell<ChannelObj>, RCount)>),
63}
64
65impl GcWeak {
66    pub fn new_array(arr: &Rc<(GosArrayObj, RCount)>) -> GcWeak {
67        GcWeak::Array(Rc::downgrade(arr))
68    }
69
70    pub fn new_closure(cls: &Rc<(ClosureObj, RCount)>) -> GcWeak {
71        GcWeak::Closure(Rc::downgrade(cls))
72    }
73
74    pub fn new_map(m: &Rc<(MapObj, RCount)>) -> GcWeak {
75        GcWeak::Map(Rc::downgrade(m))
76    }
77
78    pub fn new_struct(s: &Rc<(StructObj, RCount)>) -> GcWeak {
79        GcWeak::Struct(Rc::downgrade(s))
80    }
81
82    fn to_gosv(&self) -> Option<GosValue> {
83        match &self {
84            GcWeak::Array(w) => w.upgrade().map(|v| {
85                v.1.set(i32::try_from(w.strong_count()).unwrap() - 1);
86                GosValue::from_gos_array(v)
87            }),
88            GcWeak::Closure(w) => w.upgrade().map(|v| {
89                v.1.set(i32::try_from(w.strong_count()).unwrap() - 1);
90                GosValue::from_closure(Some(v))
91            }),
92            GcWeak::Map(w) => w.upgrade().map(|v| {
93                v.1.set(i32::try_from(w.strong_count()).unwrap() - 1);
94                GosValue::from_map(Some(v))
95            }),
96            GcWeak::Struct(w) => w.upgrade().map(|v| {
97                v.1.set(i32::try_from(w.strong_count()).unwrap() - 1);
98                GosValue::from_struct(v)
99            }),
100        }
101    }
102}
103
104fn children_ref_sub_one(val: &GosValue) {
105    match val.typ() {
106        ValueType::Array => val
107            .as_gos_array()
108            .0
109            .borrow_data_mut()
110            .iter()
111            .for_each(|obj| obj.ref_sub_one()),
112        ValueType::Closure => match val.as_closure() {
113            Some(cls) => cls.0.ref_sub_one(),
114            None => {}
115        },
116        ValueType::Map => match val.as_map() {
117            Some(m) => m.0.borrow_data().iter().for_each(|(k, v)| {
118                k.ref_sub_one();
119                v.ref_sub_one();
120            }),
121            None => {}
122        },
123        ValueType::Struct => val
124            .as_struct()
125            .0
126            .borrow_fields()
127            .iter()
128            .for_each(|obj| obj.ref_sub_one()),
129        _ => unreachable!(),
130    };
131}
132
133fn children_mark_dirty(val: &GosValue, queue: &mut RCQueue) {
134    match val.typ() {
135        ValueType::Array => val
136            .as_gos_array()
137            .0
138            .borrow_data_mut()
139            .iter()
140            .for_each(|obj| obj.mark_dirty(queue)),
141        ValueType::Closure => match val.as_closure() {
142            Some(cls) => cls.0.mark_dirty(queue),
143            None => {}
144        },
145        ValueType::Map => match val.as_map() {
146            Some(m) => m.0.borrow_data().iter().for_each(|(k, v)| {
147                k.mark_dirty(queue);
148                v.mark_dirty(queue);
149            }),
150            None => {}
151        },
152        ValueType::Struct => val
153            .as_struct()
154            .0
155            .borrow_fields()
156            .iter()
157            .for_each(|obj| obj.mark_dirty(queue)),
158        _ => unreachable!(),
159    };
160}
161
162/// break_cycle clears all values held by containers
163fn break_cycle(val: &GosValue) {
164    match val.typ() {
165        ValueType::Array => val.as_gos_array().0.borrow_data_mut().clear(),
166        ValueType::Map => match val.as_map() {
167            Some(m) => m.0.borrow_data_mut().clear(),
168            None => {}
169        },
170        ValueType::Struct => val.as_struct().0.borrow_fields_mut().clear(),
171        ValueType::Closure => {}
172        _ => unreachable!(),
173    };
174}
175
176/// put the non-zero-rc on the left, and the others on the right
177fn partition_to_scan(to_scan: &mut Vec<GosValue>) -> usize {
178    let len = to_scan.len();
179    if len == 0 {
180        return 0;
181    }
182    let mut p0 = 0;
183    let mut p1 = len - 1;
184    loop {
185        while p0 < len - 1 && to_scan[p0].rc() > 0 {
186            p0 += 1;
187        }
188        while p1 > 1 && to_scan[p1].rc() <= 0 {
189            p1 -= 1;
190        }
191        if p0 >= p1 {
192            break;
193        }
194        to_scan.swap(p0, p1);
195    }
196    p0
197}
198
199pub(crate) fn collect(objs: &GcContainer) {
200    let mut to_scan: Vec<GosValue> = objs
201        .borrow_data()
202        .iter()
203        .filter_map(|o| o.to_gosv())
204        .collect();
205    //print!("objs before GC: {}\n", to_scan.len());
206    for v in to_scan.iter() {
207        children_ref_sub_one(v);
208    }
209
210    let boundary = partition_to_scan(&mut to_scan);
211    for i in boundary..to_scan.len() {
212        to_scan[i].set_rc(-(i as IRC));
213    }
214
215    let mut queue: RCQueue = RCQueue::new();
216    for i in 0..boundary {
217        children_mark_dirty(&to_scan[i], &mut queue);
218    }
219
220    loop {
221        if let Some(i) = queue.pop_front() {
222            let obj = &to_scan[(-i) as usize];
223            obj.set_rc(666);
224            children_mark_dirty(&obj, &mut queue);
225        } else {
226            break;
227        }
228    }
229
230    for obj in to_scan.into_iter() {
231        if obj.rc() <= 0 {
232            break_cycle(&obj);
233        }
234    }
235
236    let _result: Vec<GosValue> = objs
237        .borrow_data()
238        .iter()
239        .filter_map(|o| o.to_gosv())
240        .collect();
241    //print!("objs left after GC: {}\n", result.len());
242}
go_vm/gc.rs

go_vm/
gc.rs
