lib.rs 14.5 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1
// Copyright 2017 The Australian National University
qinsoon's avatar
qinsoon committed
2
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
3
4
5
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
qinsoon's avatar
qinsoon committed
6
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
7
//     http://www.apache.org/licenses/LICENSE-2.0
qinsoon's avatar
qinsoon committed
8
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
9
10
11
12
13
14
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

qinsoon's avatar
qinsoon committed
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//! # An Immix garbage collector implementation
//!
//! This crate implements a garbage collector for Zebu. We carefully designed
//! the interface so the garbage collector is a standalone crate from the VM,
//! and it should be able to reuse easily outside Zebu project.
//!
//! The GC implements immix for small object allocation/reclamation, and
//! treadmill for large objects. It uses an object model with 64-bits object header
//! before the start of the object. Allocation always returns an ObjectReference
//! pointing to the start of the object.
//!
//! The idea of the GC implementation is discussed in the paper: Rust as a language
//! for high performance GC implementation (ISMM'16).
//!
//! A user who tries to use this GC (Zebu or other user) should do the following:
//!
//! 1. initialize the GC by calling gc_init()
//! 2. for a running mutator thread, call new_mutator() to create a mutator
//!    (and store it somewhere in TLS). And call set_low_water_mark() to inform
//!    the GC so that when it conservatively scans stack, it will not scan beyond
//!    the low water mark
//! 3. insert yieldpoint() occasionally in the code so that the GC can synchronise
//!    with the thread, or insert yieldpoint_slow() if user decides to implement an inlined
//!    fastpath
//! 4. call alloc_fast() to ask for allocation, or alloc_slow()
//!    if user decides to implement an inlined fastpath
//! 5. the allocation may trigger a GC, and it is guaranteed to return a valid address
//! 6. call init_object() or init_hybrid() to initialize the object
//! 7. when the thread quits, call drop_mutator() to properly destroy a mutator.
//!
//! Other utility functions provided by the GC:
//!
//! * explicit control of root set - add_to_root()/remove_root():
//!   the GC treats stacks and registers as default root set, however the client may
//!   explicitly add references as root
//! * explicit control of object movement/liveness - pin_object()/unpin_object():
//!   the GC will keep the object alive, and in place (does not move it)
//! * capability of persisting the heap as a relocatable boot image - persist_heap():
//!   the GC will traverse the heap from given roots, and dump all reachable objects
//!   in a structured way so that the user can use the data structure to access every
//!   object and persist them in their own approach
//!
//! Issues (going to be fixed in a major GC rewrite):
//!
//! * currently collection is disabled: due to bugs (and the fact that we are going to
//!   majorly change the GC)
//! * we are using a 64-bits header for each object, we will switch to sidemap object
//!   model (Issue #12)
//! * we are allocating the whole heap, and initialize it all at once during startup. We
//!   should allow dynamic growth of heap (Issue #56)
//! * pin/unpin operations is different from Mu spec (Issue #33)
//! * we are using some utility C functions (heap/gc/clib_(architecture).c/.S) to help acquire
//!   some information for GC. And those C functions are not returning accurate results
//!   (Issue #21)

70
71
#[macro_use]
extern crate rodal;
qinsoon's avatar
qinsoon committed
72
extern crate mu_utils as utils;
qinsoon's avatar
qinsoon committed
73
74
75
76
77
78
79
#[macro_use]
extern crate lazy_static;
#[macro_use]
extern crate log;
extern crate simple_logger;
extern crate aligned_alloc;
extern crate crossbeam;
80
81
#[macro_use]
extern crate field_offset;
qinsoon's avatar
qinsoon committed
82

qinsoon's avatar
qinsoon committed
83
use common::gctype::GCType;
qinsoon's avatar
qinsoon committed
84
use common::objectdump;
qinsoon's avatar
qinsoon committed
85
use heap::immix::BYTES_IN_LINE;
qinsoon's avatar
qinsoon committed
86
87
88
89
use heap::immix::ImmixSpace;
use heap::immix::ImmixMutatorLocal;
use heap::freelist;
use heap::freelist::FreeListSpace;
90
use utils::LinkedHashSet;
91
use utils::Address;
qinsoon's avatar
qinsoon committed
92
use utils::ObjectReference;
93

qinsoon's avatar
qinsoon committed
94
use std::fmt;
95
96
use std::sync::Arc;
use std::sync::RwLock;
qinsoon's avatar
qinsoon committed
97
98
99
100
use std::sync::atomic::Ordering;

/// data structures for the GC and the user
pub mod common;
101

qinsoon's avatar
qinsoon committed
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/// object model (metadata for objects managed by the GC)
/// this allows the user to know some GC semantics, and to be able to implement
/// fastpath on their side
//  FIXME: this mod can be private (we expose it only because tests are using it)
//  we should consider moving those tests within the mod
pub mod objectmodel;
/// object header size (in byte)
pub use objectmodel::OBJECT_HEADER_SIZE;
/// offset from an object reference to the header (in byte, can be negative)
pub use objectmodel::OBJECT_HEADER_OFFSET;

/// the main GC crate, heap structures (including collection, immix space, freelist space)
//  FIXME: this mod can be private (we expose it only because tests are using it)
//  we should consider moving those tests within the mod
pub mod heap;

/// whether this GC will move objects?
/// (does an object have a fixed address once allocated before it is reclaimed)
qinsoon's avatar
qinsoon committed
120
pub const GC_MOVES_OBJECT: bool = false;
qinsoon's avatar
qinsoon committed
121

qinsoon's avatar
qinsoon committed
122
123
/// threshold for small objects. Use small object allocator (immix) for objects that
/// are smaller than this threshold. Otherwise use large object allocator (freelist)
qinsoon's avatar
qinsoon committed
124
pub const LARGE_OBJECT_THRESHOLD: usize = BYTES_IN_LINE;
qinsoon's avatar
qinsoon committed
125

qinsoon's avatar
qinsoon committed
126
127
/// the mutator that the user is supposed to put to every mutator thread
/// Most interface functions provided by the GC require a pointer to this mutator.
128
129
pub use heap::immix::ImmixMutatorLocal as Mutator;

qinsoon's avatar
qinsoon committed
130
//  these two offsets help user's compiler to generate inlined fastpath code
131

qinsoon's avatar
qinsoon committed
132
133
134
135
/// offset to the immix allocator cursor from its pointer
pub use heap::immix::CURSOR_OFFSET as ALLOCATOR_CURSOR_OFFSET;
/// offset to the immix allocator limit from its pointer
pub use heap::immix::LIMIT_OFFSET as ALLOCATOR_LIMIT_OFFSET;
136

qinsoon's avatar
qinsoon committed
137
138
//  the implementation of this GC will be changed dramatically in the future,
//  but the exposed interface is likely to stay the same.
139

qinsoon's avatar
qinsoon committed
140
/// initializes the GC
141
#[no_mangle]
qinsoon's avatar
qinsoon committed
142
pub extern "C" fn gc_init(immix_size: usize, lo_size: usize, n_gcthreads: usize, enable_gc: bool) {
143
144
    // init object model - init this first, since spaces may use it
    objectmodel::init();
qinsoon's avatar
qinsoon committed
145

146
147
148
    // init space size
    heap::IMMIX_SPACE_SIZE.store(immix_size, Ordering::SeqCst);
    heap::LO_SPACE_SIZE.store(lo_size, Ordering::SeqCst);
qinsoon's avatar
qinsoon committed
149

150
151
    let (immix_space, lo_space) = {
        let immix_space = Arc::new(ImmixSpace::new(immix_size));
qinsoon's avatar
qinsoon committed
152
        let lo_space = Arc::new(FreeListSpace::new(lo_size));
153

qinsoon's avatar
qinsoon committed
154
        heap::gc::init(n_gcthreads);
qinsoon's avatar
qinsoon committed
155

156
157
        (immix_space, lo_space)
    };
qinsoon's avatar
qinsoon committed
158

qinsoon's avatar
qinsoon committed
159
160
161
162
    *MY_GC.write().unwrap() = Some(GC {
        immix_space: immix_space,
        lo_space: lo_space,

163
        gc_types: vec![],
164
        roots: LinkedHashSet::new()
qinsoon's avatar
qinsoon committed
165
166
    });

167
168
169
170
171
172
    if enable_gc {
        heap::gc::ENABLE_GC.store(true, Ordering::Relaxed);
    } else {
        heap::gc::ENABLE_GC.store(false, Ordering::Relaxed);
    }

qinsoon's avatar
qinsoon committed
173
174
175
176
177
178
    info!(
        "heap is {} bytes (immix: {} bytes, lo: {} bytes) . ",
        immix_size + lo_size,
        immix_size,
        lo_size
    );
qinsoon's avatar
qinsoon committed
179
    info!("{} gc threads", n_gcthreads);
180
181
182
    if !enable_gc {
        warn!("GC disabled (panic when a collection is triggered)");
    }
183
184
}

185
186
187
188
189
190
/// destroys current GC instance
#[no_mangle]
pub extern "C" fn gc_destoy() {
    *MY_GC.write().unwrap() = None;
}

qinsoon's avatar
qinsoon committed
191
/// creates a mutator
192
#[no_mangle]
qinsoon's avatar
qinsoon committed
193
pub extern "C" fn new_mutator() -> ImmixMutatorLocal {
194
    ImmixMutatorLocal::new(MY_GC.read().unwrap().as_ref().unwrap().immix_space.clone())
195
196
}

qinsoon's avatar
qinsoon committed
197
198
199
200
/// destroys a mutator
/// Note the user has to explicitly drop mutator that they are not using, otherwise
/// the GC may not be able to stop all the mutators before GC, and ends up in an endless
/// pending status
201
202
#[no_mangle]
#[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
203
204
205
pub extern "C" fn drop_mutator(mutator: *mut ImmixMutatorLocal) {
    unsafe { mutator.as_mut().unwrap() }.destroy();

206
207
208
    // rust will reclaim the boxed mutator
}

qinsoon's avatar
qinsoon committed
209
210
211
/// sets low water mark for current thread
/// When the GC conservatively scans stack for root, it will not scan beyond the low
/// water mark
212
pub use heap::gc::set_low_water_mark;
213

qinsoon's avatar
qinsoon committed
214
/// adds an object reference to the root set
215
#[no_mangle]
216
#[inline(always)]
qinsoon's avatar
qinsoon committed
217
pub extern "C" fn add_to_root(obj: ObjectReference) {
218
219
220
221
    let mut gc = MY_GC.write().unwrap();
    gc.as_mut().unwrap().roots.insert(obj);
}

qinsoon's avatar
qinsoon committed
222
/// removes an object reference from the root set
223
#[no_mangle]
224
#[inline(always)]
qinsoon's avatar
qinsoon committed
225
pub extern "C" fn remove_root(obj: ObjectReference) {
226
227
228
229
    let mut gc = MY_GC.write().unwrap();
    gc.as_mut().unwrap().roots.remove(&obj);
}

qinsoon's avatar
qinsoon committed
230
/// pins an object so that it will be moved or reclaimed
231
#[no_mangle]
qinsoon's avatar
qinsoon committed
232
pub extern "C" fn muentry_pin_object(obj: ObjectReference) -> Address {
233
234
235
236
    add_to_root(obj);
    obj.to_address()
}

qinsoon's avatar
qinsoon committed
237
/// unpins an object so that it can be freely moved/reclaimed as normal objects
238
#[no_mangle]
qinsoon's avatar
qinsoon committed
239
240
pub extern "C" fn muentry_unpin_object(obj: Address) {
    remove_root(unsafe { obj.to_object_reference() });
241
242
}

qinsoon's avatar
qinsoon committed
243
/// a regular check to see if the mutator should stop for synchronisation
244
245
#[no_mangle]
#[inline(always)]
qinsoon's avatar
qinsoon committed
246
247
pub extern "C" fn yieldpoint(mutator: *mut ImmixMutatorLocal) {
    unsafe { mutator.as_mut().unwrap() }.yieldpoint();
248
249
}

qinsoon's avatar
qinsoon committed
250
251
252
/// the slowpath for yieldpoint
/// We assume for performance, the user will implement an inlined fastpath, we provide
/// constants, offsets to fields and this slowpath function for the user
253
254
#[no_mangle]
#[inline(never)]
qinsoon's avatar
qinsoon committed
255
256
pub extern "C" fn yieldpoint_slow(mutator: *mut ImmixMutatorLocal) {
    unsafe { mutator.as_mut().unwrap() }.yieldpoint_slow()
257
258
}

qinsoon's avatar
qinsoon committed
259
260
/// allocates an object in the immix space
//  size doesn't include HEADER_SIZE
261
#[inline(always)]
262
pub fn alloc(mutator: *mut ImmixMutatorLocal, size: usize, align: usize) -> ObjectReference {
qinsoon's avatar
qinsoon committed
263
264
    let addr = unsafe { &mut *mutator }.alloc(size, align);
    unsafe { addr.to_object_reference() }
265
266
}

qinsoon's avatar
qinsoon committed
267
268
/// allocates an object in the immix space
//  size doesn't include HEADER_SIZE
269
#[no_mangle]
qinsoon's avatar
qinsoon committed
270
271
272
pub extern "C" fn muentry_alloc_fast(
    mutator: *mut ImmixMutatorLocal,
    size: usize,
273
    align: usize
qinsoon's avatar
qinsoon committed
274
) -> ObjectReference {
275
    let ret = alloc(mutator, size, align);
qinsoon's avatar
qinsoon committed
276
277
278
279
280
281
282
    trace!(
        "muentry_alloc_fast(mutator: {:?}, size: {}, align: {}) = {}",
        mutator,
        size,
        align,
        ret
    );
283
284

    ret
285
286
}

qinsoon's avatar
qinsoon committed
287
288
289
290
291
/// allocates an object with slowpath in the immix space
#[no_mangle]
#[inline(never)]
//  this function is supposed to be called by an inlined fastpath
//  size includes HEADER_SIZE, return value is NOT offset by HEADER_OFFSET
qinsoon's avatar
qinsoon committed
292
293
294
pub extern "C" fn muentry_alloc_slow(
    mutator: *mut ImmixMutatorLocal,
    size: usize,
295
    align: usize
qinsoon's avatar
qinsoon committed
296
297
298
299
300
301
302
303
304
) -> Address {
    let ret = unsafe { &mut *mutator }.try_alloc_from_local(size, align);
    trace!(
        "muentry_alloc_slow(mutator: {:?}, size: {}, align: {}) = {}",
        mutator,
        size,
        align,
        ret
    );
qinsoon's avatar
qinsoon committed
305
306
307
308
309
310
311

    ret
}

/// allocates an object in the freelist space (large object space)
#[no_mangle]
//  size doesn't include HEADER_SIZE
qinsoon's avatar
qinsoon committed
312
313
314
pub extern "C" fn muentry_alloc_large(
    mutator: *mut ImmixMutatorLocal,
    size: usize,
315
    align: usize
qinsoon's avatar
qinsoon committed
316
317
318
319
320
) -> ObjectReference {
    let ret = freelist::alloc_large(
        size,
        align,
        unsafe { mutator.as_mut().unwrap() },
321
        MY_GC.read().unwrap().as_ref().unwrap().lo_space.clone()
qinsoon's avatar
qinsoon committed
322
323
324
325
326
327
328
329
330
331
    );
    trace!(
        "muentry_alloc_large(mutator: {:?}, size: {}, align: {}) = {}",
        mutator,
        size,
        align,
        ret
    );

    unsafe { ret.to_object_reference() }
qinsoon's avatar
qinsoon committed
332
333
}

334
335
336
337
338
339
340
341
#[no_mangle]
//  size doesn't include HEADER_SIZE
pub extern "C" fn muentry_alloc_any(
    mutator: *mut ImmixMutatorLocal,
    size: usize,
    align: usize
) -> ObjectReference {
    let actual_size = size + OBJECT_HEADER_SIZE;
qinsoon's avatar
fix    
qinsoon committed
342
343
    if actual_size <= LARGE_OBJECT_THRESHOLD {
        muentry_alloc_fast(mutator, size, align)
344
    } else {
qinsoon's avatar
fix    
qinsoon committed
345
        muentry_alloc_large(mutator, size, align)
346
347
348
    }
}

qinsoon's avatar
qinsoon committed
349
/// initializes a fix-sized object
350
#[no_mangle]
351
#[inline(never)]
qinsoon's avatar
qinsoon committed
352
353
354
pub extern "C" fn muentry_init_object(
    mutator: *mut ImmixMutatorLocal,
    obj: ObjectReference,
355
    encode: u64
qinsoon's avatar
qinsoon committed
356
357
) {
    unsafe { &mut *mutator }.init_object(obj.to_address(), encode);
358
359
}

qinsoon's avatar
qinsoon committed
360
/// initializes a hybrid type object
qinsoon's avatar
qinsoon committed
361
362
#[no_mangle]
#[inline(never)]
qinsoon's avatar
qinsoon committed
363
364
365
366
pub extern "C" fn muentry_init_hybrid(
    mutator: *mut ImmixMutatorLocal,
    obj: ObjectReference,
    encode: u64,
367
    length: u64
qinsoon's avatar
qinsoon committed
368
369
) {
    unsafe { &mut *mutator }.init_hybrid(obj.to_address(), encode, length);
qinsoon's avatar
qinsoon committed
370
371
}

qinsoon's avatar
qinsoon committed
372
373
/// forces gc to happen
/// (this is not a 'hint' - world will be stopped, and heap traversal will start)
374
#[no_mangle]
qinsoon's avatar
qinsoon committed
375
pub extern "C" fn force_gc() {
qinsoon's avatar
qinsoon committed
376
377
    heap::gc::trigger_gc();
}
378

qinsoon's avatar
qinsoon committed
379
380
381
/// traces reachable objects and record them as a data structure
/// so that the user can inspect the reachable heap and persist it in their way
#[no_mangle]
qinsoon's avatar
qinsoon committed
382
pub extern "C" fn persist_heap(roots: Vec<Address>) -> objectdump::HeapDump {
qinsoon's avatar
qinsoon committed
383
384
385
386
387
388
    objectdump::HeapDump::from_roots(roots)
}

/// GC represents the context for the current running GC instance
struct GC {
    immix_space: Arc<ImmixSpace>,
qinsoon's avatar
qinsoon committed
389
390
    lo_space: Arc<FreeListSpace>,
    gc_types: Vec<Arc<GCType>>,
391
    roots: LinkedHashSet<ObjectReference>
qinsoon's avatar
qinsoon committed
392
393
394
395
396
397
398
399
400
401
402
403
404
}

lazy_static! {
    static ref MY_GC : RwLock<Option<GC>> = RwLock::new(None);
}

impl fmt::Debug for GC {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "GC\n").unwrap();
        write!(f, "{}", self.immix_space).unwrap();

        write!(f, "{}", self.lo_space)
    }
405
406
}

qinsoon's avatar
qinsoon committed
407
408
409
// the following API functions may get removed in the future

/// prints current GC context for debugging
410
#[no_mangle]
qinsoon's avatar
qinsoon committed
411
pub extern "C" fn print_gc_context() {
qinsoon's avatar
qinsoon committed
412
413
    println!("{:?}", MY_GC.read().unwrap().as_ref().unwrap());
}
414

qinsoon's avatar
qinsoon committed
415
416
/// gets immix space and freelist space
#[no_mangle]
qinsoon's avatar
qinsoon committed
417
pub extern "C" fn get_spaces() -> (Arc<ImmixSpace>, Arc<FreeListSpace>) {
qinsoon's avatar
qinsoon committed
418
419
420
421
    let space_lock = MY_GC.read().unwrap();
    let space = space_lock.as_ref().unwrap();

    (space.immix_space.clone(), space.lo_space.clone())
422
423
}

qinsoon's avatar
qinsoon committed
424
/// informs GC of a GCType
qinsoon's avatar
qinsoon committed
425
#[no_mangle]
qinsoon's avatar
qinsoon committed
426
pub extern "C" fn add_gc_type(mut ty: GCType) -> Arc<GCType> {
qinsoon's avatar
qinsoon committed
427
428
429
430
431
432
433
434
435
436
437
    let mut gc_guard = MY_GC.write().unwrap();
    let mut gc = gc_guard.as_mut().unwrap();

    let index = gc.gc_types.len() as u32;
    ty.id = index;

    let ty = Arc::new(ty);

    gc.gc_types.push(ty.clone());

    ty
438
}
439

qinsoon's avatar
qinsoon committed
440
/// gets the encoding for a given GC type (by ID)
441
#[no_mangle]
qinsoon's avatar
qinsoon committed
442
pub extern "C" fn get_gc_type_encode(id: u32) -> u64 {
qinsoon's avatar
qinsoon committed
443
    let gc_lock = MY_GC.read().unwrap();
qinsoon's avatar
qinsoon committed
444
    let ref gctype = gc_lock.as_ref().unwrap().gc_types[id as usize];
qinsoon's avatar
qinsoon committed
445
446
447
448
449
450

    if gctype.is_hybrid() {
        objectmodel::gen_hybrid_gctype_encode(gctype, 0) // fake length
    } else {
        objectmodel::gen_gctype_encode(gctype)
    }
qinsoon's avatar
qinsoon committed
451
}