WARNING! Access to this system is limited to authorised users only.
Unauthorised users may be subject to prosecution.
Unauthorised access to this system is a criminal offence under Australian law (Federal Crimes Act 1914 Part VIA)
It is a criminal offence to:
(1) Obtain access to data without authority. -Penalty 2 years imprisonment.
(2) Damage, delete, alter or insert data without authority. -Penalty 10 years imprisonment.
User activity is monitored and recorded. Anyone using this system expressly consents to such monitoring and recording.

To protect your data, the CISO officer has suggested users to enable 2FA as soon as possible.
Currently 2.4% of users enabled 2FA.

mod.rs 25.4 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
use heap::immix::MUTATORS;
use heap::immix::N_MUTATORS;
use heap::immix::ImmixMutatorLocal;
use heap::immix::ImmixSpace;
use heap::freelist::FreeListSpace;
use objectmodel;
21
use common::gctype::*;
22
use heap::Space;
qinsoon's avatar
qinsoon committed
23
use MY_GC;
qinsoon's avatar
qinsoon committed
24 25

use utils::{Address, ObjectReference};
qinsoon's avatar
qinsoon committed
26
use utils::POINTER_SIZE;
27

28
use std::sync::atomic::{AtomicIsize, AtomicBool, Ordering};
29 30
use std::sync::{Arc, Mutex, Condvar, RwLock};

qinsoon's avatar
qinsoon committed
31
use crossbeam::sync::chase_lev::*;
32 33 34 35 36 37 38 39 40 41
use std::sync::mpsc;
use std::sync::mpsc::channel;
use std::thread;

use std::sync::atomic;

lazy_static! {
    static ref STW_COND : Arc<(Mutex<usize>, Condvar)> = {
        Arc::new((Mutex::new(0), Condvar::new()))
    };
qinsoon's avatar
qinsoon committed
42

43 44 45
    static ref ROOTS : RwLock<Vec<ObjectReference>> = RwLock::new(vec![]);
}

qinsoon's avatar
qinsoon committed
46
pub static ENABLE_GC: AtomicBool = atomic::ATOMIC_BOOL_INIT;
47

qinsoon's avatar
qinsoon committed
48 49
static CONTROLLER: AtomicIsize = atomic::ATOMIC_ISIZE_INIT;
const NO_CONTROLLER: isize = -1;
50

qinsoon's avatar
qinsoon committed
51
pub fn init(n_gcthreads: usize) {
52
    CONTROLLER.store(NO_CONTROLLER, Ordering::SeqCst);
qinsoon's avatar
qinsoon committed
53 54

    GC_THREADS.store(n_gcthreads, Ordering::SeqCst);
55 56 57 58
}

pub fn trigger_gc() {
    trace!("Triggering GC...");
qinsoon's avatar
qinsoon committed
59

60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
    for mut m in MUTATORS.write().unwrap().iter_mut() {
        if m.is_some() {
            m.as_mut().unwrap().set_take_yield(true);
        }
    }
}

use std::os::raw::c_void;
#[cfg(target_arch = "x86_64")]
#[link(name = "gc_clib_x64")]
extern "C" {
    pub fn malloc_zero(size: usize) -> *const c_void;
    fn immmix_get_stack_ptr() -> Address;
    pub fn set_low_water_mark();
    fn get_low_water_mark() -> Address;
    fn get_registers() -> *const Address;
    fn get_registers_count() -> i32;
}

79 80 81 82 83 84 85 86 87 88 89
#[cfg(target_arch = "aarch64")]
#[link(name = "gc_clib_aarch64")]
extern "C" {
    pub fn malloc_zero(size: usize) -> *const c_void;
    fn immmix_get_stack_ptr() -> Address;
    pub fn set_low_water_mark();
    fn get_low_water_mark() -> Address;
    fn get_registers() -> *const Address;
    fn get_registers_count() -> i32;
}

90
pub fn stack_scan() -> Vec<ObjectReference> {
91
    trace!("stack scanning...");
qinsoon's avatar
qinsoon committed
92 93
    let stack_ptr: Address = unsafe { immmix_get_stack_ptr() };

94 95 96
    if cfg!(debug_assertions) {
        if !stack_ptr.is_aligned_to(8) {
            use std::process;
qinsoon's avatar
qinsoon committed
97 98 99 100 101
            println!(
                "trying to scanning stack, however the current stack pointer is 0x{:x}, \
                 which is not aligned to 8bytes",
                stack_ptr
            );
102 103 104
            process::exit(102);
        }
    }
qinsoon's avatar
qinsoon committed
105 106 107

    let low_water_mark: Address = unsafe { get_low_water_mark() };

108 109
    let mut cursor = stack_ptr;
    let mut ret = vec![];
110

qinsoon's avatar
qinsoon committed
111 112 113 114 115
    let gccontext_guard = MY_GC.read().unwrap();
    let gccontext = gccontext_guard.as_ref().unwrap();

    let immix_space = gccontext.immix_space.clone();
    let lo_space = gccontext.lo_space.clone();
qinsoon's avatar
qinsoon committed
116

117
    while cursor < low_water_mark {
qinsoon's avatar
qinsoon committed
118 119
        let value: Address = unsafe { cursor.load::<Address>() };

120
        if immix_space.is_valid_object(value) || lo_space.is_valid_object(value) {
qinsoon's avatar
qinsoon committed
121
            ret.push(unsafe { value.to_object_reference() });
122
        }
qinsoon's avatar
qinsoon committed
123

124
        cursor = cursor + POINTER_SIZE;
125
    }
qinsoon's avatar
qinsoon committed
126

127
    let roots_from_stack = ret.len();
qinsoon's avatar
qinsoon committed
128 129 130 131

    let registers_count = unsafe { get_registers_count() };
    let registers = unsafe { get_registers() };

132
    for i in 0..registers_count {
qinsoon's avatar
qinsoon committed
133 134 135 136
        let value = unsafe { *registers.offset(i as isize) };

        if immix_space.is_valid_object(value) || lo_space.is_valid_object(value) {
            ret.push(unsafe { value.to_object_reference() });
137 138
        }
    }
qinsoon's avatar
qinsoon committed
139

140
    let roots_from_registers = ret.len() - roots_from_stack;
qinsoon's avatar
qinsoon committed
141 142 143 144 145 146 147

    trace!(
        "roots: {} from stack, {} from registers",
        roots_from_stack,
        roots_from_registers
    );

148 149 150 151 152 153
    ret
}

#[inline(never)]
pub fn sync_barrier(mutator: &mut ImmixMutatorLocal) {
    let controller_id = CONTROLLER.compare_and_swap(-1, mutator.id() as isize, Ordering::SeqCst);
qinsoon's avatar
qinsoon committed
154 155 156 157 158 159 160

    trace!(
        "Mutator{} saw the controller is {}",
        mutator.id(),
        controller_id
    );

161 162
    // prepare the mutator for gc - return current block (if it has)
    mutator.prepare_for_gc();
qinsoon's avatar
qinsoon committed
163

164
    // user thread call back to prepare for gc
qinsoon's avatar
qinsoon committed
165 166
    //    USER_THREAD_PREPARE_FOR_GC.read().unwrap()();

167
    if controller_id != NO_CONTROLLER {
168 169 170 171 172 173
        // scan its stack
        {
            let mut thread_roots = stack_scan();
            ROOTS.write().unwrap().append(&mut thread_roots);
        }

174 175
        // this thread will block
        block_current_thread(mutator);
qinsoon's avatar
qinsoon committed
176

177
        // reset current mutator
178
        mutator.reset_after_gc();
179 180 181
    } else {
        // this thread is controller
        // other threads should block
182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198

        // init roots
        {
            let mut roots = ROOTS.write().unwrap();
            // clear existing roots (roots from last gc)
            roots.clear();

            // add explicity roots
            let gc = MY_GC.read().unwrap();
            for objref in gc.as_ref().unwrap().roots.iter() {
                roots.push(*objref);
            }

            // scan its stack
            let mut thread_roots = stack_scan();
            roots.append(&mut thread_roots);
        }
qinsoon's avatar
qinsoon committed
199

200 201 202
        // wait for all mutators to be blocked
        let &(ref lock, ref cvar) = &*STW_COND.clone();
        let mut count = 0;
qinsoon's avatar
qinsoon committed
203 204 205 206 207

        trace!(
            "expect {} mutators to park",
            *N_MUTATORS.read().unwrap() - 1
        );
208
        while count < *N_MUTATORS.read().unwrap() - 1 {
qinsoon's avatar
qinsoon committed
209
            let new_count = { *lock.lock().unwrap() };
210
            if new_count != count {
211 212 213 214
                count = new_count;
                trace!("count = {}", count);
            }
        }
qinsoon's avatar
qinsoon committed
215

216
        trace!("everyone stopped, gc will start");
qinsoon's avatar
qinsoon committed
217

218 219
        // roots->trace->sweep
        gc();
qinsoon's avatar
qinsoon committed
220

221 222 223 224 225 226 227 228 229 230
        // mutators will resume
        CONTROLLER.store(NO_CONTROLLER, Ordering::SeqCst);
        for mut t in MUTATORS.write().unwrap().iter_mut() {
            if t.is_some() {
                let t_mut = t.as_mut().unwrap();
                t_mut.set_take_yield(false);
                t_mut.set_still_blocked(false);
            }
        }
        // every mutator thread will reset themselves, so only reset current mutator here
231
        mutator.reset_after_gc();
232 233 234 235 236 237 238 239 240 241 242 243

        // resume
        {
            let mut count = lock.lock().unwrap();
            *count = 0;
            cvar.notify_all();
        }
    }
}

fn block_current_thread(mutator: &mut ImmixMutatorLocal) {
    trace!("Mutator{} blocked", mutator.id());
qinsoon's avatar
qinsoon committed
244

245 246 247
    let &(ref lock, ref cvar) = &*STW_COND.clone();
    let mut count = lock.lock().unwrap();
    *count += 1;
qinsoon's avatar
qinsoon committed
248

249
    mutator.global.set_still_blocked(true);
qinsoon's avatar
qinsoon committed
250

251 252 253
    while mutator.global.is_still_blocked() {
        count = cvar.wait(count).unwrap();
    }
qinsoon's avatar
qinsoon committed
254

255 256 257
    trace!("Mutator{} unblocked", mutator.id());
}

qinsoon's avatar
qinsoon committed
258
pub static GC_COUNT: atomic::AtomicUsize = atomic::ATOMIC_USIZE_INIT;
259 260

fn gc() {
qinsoon's avatar
qinsoon committed
261
    if !ENABLE_GC.load(Ordering::SeqCst) {
262 263 264
        panic!("Triggering GC when GC is disabled");
    }

qinsoon's avatar
qinsoon committed
265 266
    GC_COUNT.store(
        GC_COUNT.load(atomic::Ordering::SeqCst) + 1,
267
        atomic::Ordering::SeqCst
qinsoon's avatar
qinsoon committed
268 269
    );

270
    trace!("GC starts");
qinsoon's avatar
qinsoon committed
271

272
    // creates root deque
qinsoon's avatar
qinsoon committed
273
    let mut roots: &mut Vec<ObjectReference> = &mut ROOTS.write().unwrap();
274
    trace!("total roots: {}", roots.len());
qinsoon's avatar
qinsoon committed
275

276 277
    // mark & trace
    {
qinsoon's avatar
qinsoon committed
278 279 280
        let gccontext_guard = MY_GC.read().unwrap();
        let gccontext = gccontext_guard.as_ref().unwrap();
        let (immix_space, lo_space) = (&gccontext.immix_space, &gccontext.lo_space);
qinsoon's avatar
qinsoon committed
281

282 283
        start_trace(&mut roots, immix_space.clone(), lo_space.clone());
    }
qinsoon's avatar
qinsoon committed
284

285
    trace!("trace done");
qinsoon's avatar
qinsoon committed
286

287 288
    // sweep
    {
qinsoon's avatar
qinsoon committed
289 290
        let gccontext_guard = MY_GC.read().unwrap();
        let gccontext = gccontext_guard.as_ref().unwrap();
291

qinsoon's avatar
qinsoon committed
292
        let ref immix_space = gccontext.immix_space;
293
        immix_space.sweep();
294

qinsoon's avatar
qinsoon committed
295
        let ref lo_space = gccontext.lo_space;
296
        lo_space.sweep();
297
    }
qinsoon's avatar
qinsoon committed
298

299 300 301 302
    objectmodel::flip_mark_state();
    trace!("GC finishes");
}

qinsoon's avatar
qinsoon committed
303 304
pub const PUSH_BACK_THRESHOLD: usize = 50;
pub static GC_THREADS: atomic::AtomicUsize = atomic::ATOMIC_USIZE_INIT;
305 306 307

#[allow(unused_variables)]
#[inline(never)]
qinsoon's avatar
qinsoon committed
308 309 310
pub fn start_trace(
    work_stack: &mut Vec<ObjectReference>,
    immix_space: Arc<ImmixSpace>,
311
    lo_space: Arc<FreeListSpace>
qinsoon's avatar
qinsoon committed
312
) {
313
    // creates root deque
314
    let (worker, stealer) = deque();
qinsoon's avatar
qinsoon committed
315

316 317 318 319 320
    while !work_stack.is_empty() {
        worker.push(work_stack.pop().unwrap());
    }

    loop {
qinsoon's avatar
qinsoon committed
321 322
        let (sender, receiver) = channel::<ObjectReference>();

323 324 325 326 327 328 329 330 331 332 333
        let mut gc_threads = vec![];
        for _ in 0..GC_THREADS.load(atomic::Ordering::SeqCst) {
            let new_immix_space = immix_space.clone();
            let new_lo_space = lo_space.clone();
            let new_stealer = stealer.clone();
            let new_sender = sender.clone();
            let t = thread::spawn(move || {
                start_steal_trace(new_stealer, new_sender, new_immix_space, new_lo_space);
            });
            gc_threads.push(t);
        }
qinsoon's avatar
qinsoon committed
334

335 336
        // only stealers own sender, when all stealers quit, the following loop finishes
        drop(sender);
qinsoon's avatar
qinsoon committed
337

338 339 340 341
        loop {
            let recv = receiver.recv();
            match recv {
                Ok(obj) => worker.push(obj),
342
                Err(_) => break
343 344
            }
        }
qinsoon's avatar
qinsoon committed
345

346 347
        match worker.try_pop() {
            Some(obj_ref) => worker.push(obj_ref),
348
            None => break
349 350 351 352 353
        }
    }
}

#[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
354 355 356 357
fn start_steal_trace(
    stealer: Stealer<ObjectReference>,
    job_sender: mpsc::Sender<ObjectReference>,
    immix_space: Arc<ImmixSpace>,
358
    lo_space: Arc<FreeListSpace>
qinsoon's avatar
qinsoon committed
359
) {
360
    use objectmodel;
qinsoon's avatar
qinsoon committed
361

362
    let mut local_queue = vec![];
363
    let mark_state = objectmodel::load_mark_state();
qinsoon's avatar
qinsoon committed
364

365 366 367 368 369 370 371 372 373
    loop {
        let work = {
            if !local_queue.is_empty() {
                local_queue.pop().unwrap()
            } else {
                let work = stealer.steal();
                match work {
                    Steal::Empty => return,
                    Steal::Abort => continue,
374
                    Steal::Data(obj) => obj
375 376 377
                }
            }
        };
qinsoon's avatar
qinsoon committed
378 379 380 381 382 383 384

        steal_trace_object(
            work,
            &mut local_queue,
            &job_sender,
            mark_state,
            &immix_space,
385
            &lo_space
qinsoon's avatar
qinsoon committed
386
        );
387
    }
qinsoon's avatar
qinsoon committed
388
}
389 390

#[inline(always)]
391
#[cfg(feature = "use-sidemap")]
qinsoon's avatar
qinsoon committed
392 393 394 395 396 397
pub fn steal_trace_object(
    obj: ObjectReference,
    local_queue: &mut Vec<ObjectReference>,
    job_sender: &mpsc::Sender<ObjectReference>,
    mark_state: u8,
    immix_space: &ImmixSpace,
398
    lo_space: &FreeListSpace
qinsoon's avatar
qinsoon committed
399
) {
qinsoon's avatar
qinsoon committed
400 401
    if cfg!(debug_assertions) {
        // check if this object in within the heap, if it is an object
qinsoon's avatar
qinsoon committed
402 403 404
        if !immix_space.is_valid_object(obj.to_address()) &&
            !lo_space.is_valid_object(obj.to_address())
        {
qinsoon's avatar
qinsoon committed
405
            use std::process;
qinsoon's avatar
qinsoon committed
406

qinsoon's avatar
qinsoon committed
407 408 409
            println!("trying to trace an object that is not valid");
            println!("address: 0x{:x}", obj);
            println!("---");
410 411
            println!("immix space: {}", immix_space);
            println!("lo space: {}", lo_space);
qinsoon's avatar
qinsoon committed
412

qinsoon's avatar
qinsoon committed
413 414
            println!("invalid object during tracing");
            process::exit(101);
qinsoon's avatar
qinsoon committed
415 416
        }
    }
qinsoon's avatar
qinsoon committed
417

418
    let addr = obj.to_address();
qinsoon's avatar
qinsoon committed
419

420 421
    let (alloc_map, space_start) = if immix_space.addr_in_space(addr) {
        // mark object
qinsoon's avatar
qinsoon committed
422 423 424 425
        objectmodel::mark_as_traced(
            immix_space.trace_map(),
            immix_space.start(),
            obj,
426
            mark_state
qinsoon's avatar
qinsoon committed
427
        );
428 429 430 431 432 433 434 435

        // mark line
        immix_space.line_mark_table.mark_line_live(addr);

        (immix_space.alloc_map(), immix_space.start())
    } else if lo_space.addr_in_space(addr) {
        // mark object
        objectmodel::mark_as_traced(lo_space.trace_map(), lo_space.start(), obj, mark_state);
436
        trace!("mark object @ {} to {}", obj, mark_state);
437 438

        (lo_space.alloc_map(), lo_space.start())
439
    } else {
440 441 442 443 444 445
        println!("unexpected address: {}", addr);
        println!("immix space: {}", immix_space);
        println!("lo space   : {}", lo_space);

        panic!("error during tracing object")
    };
qinsoon's avatar
qinsoon committed
446

447 448
    let mut base = addr;
    loop {
449
        let value = objectmodel::get_ref_byte(alloc_map, space_start, obj);
qinsoon's avatar
qinsoon committed
450 451
        let (ref_bits, short_encode) = (
            bit_utils::lower_bits_u8(value, objectmodel::REF_BITS_LEN),
452
            bit_utils::test_nth_bit_u8(value, objectmodel::SHORT_ENCODE_BIT)
qinsoon's avatar
qinsoon committed
453
        );
454
        match ref_bits {
qinsoon's avatar
qinsoon committed
455
            0b0000_0000 => {}
456
            0b0000_0001 => {
qinsoon's avatar
qinsoon committed
457 458 459 460 461 462 463
                steal_process_edge(
                    base,
                    0,
                    local_queue,
                    job_sender,
                    mark_state,
                    immix_space,
464
                    lo_space
qinsoon's avatar
qinsoon committed
465 466
                );
            }
467
            0b0000_0011 => {
qinsoon's avatar
qinsoon committed
468 469 470 471 472 473 474
                steal_process_edge(
                    base,
                    0,
                    local_queue,
                    job_sender,
                    mark_state,
                    immix_space,
475
                    lo_space
qinsoon's avatar
qinsoon committed
476 477 478 479 480 481 482 483
                );
                steal_process_edge(
                    base,
                    8,
                    local_queue,
                    job_sender,
                    mark_state,
                    immix_space,
484
                    lo_space
qinsoon's avatar
qinsoon committed
485 486
                );
            }
487
            0b0000_1111 => {
qinsoon's avatar
qinsoon committed
488 489 490 491 492 493 494
                steal_process_edge(
                    base,
                    0,
                    local_queue,
                    job_sender,
                    mark_state,
                    immix_space,
495
                    lo_space
qinsoon's avatar
qinsoon committed
496 497 498 499 500 501 502 503
                );
                steal_process_edge(
                    base,
                    8,
                    local_queue,
                    job_sender,
                    mark_state,
                    immix_space,
504
                    lo_space
qinsoon's avatar
qinsoon committed
505 506 507 508 509 510 511 512
                );
                steal_process_edge(
                    base,
                    16,
                    local_queue,
                    job_sender,
                    mark_state,
                    immix_space,
513
                    lo_space
qinsoon's avatar
qinsoon committed
514 515 516 517 518 519 520 521
                );
                steal_process_edge(
                    base,
                    24,
                    local_queue,
                    job_sender,
                    mark_state,
                    immix_space,
522
                    lo_space
qinsoon's avatar
qinsoon committed
523 524
                );
            }
525
            _ => {
526 527
                error!("unexpected ref_bits patterns: {:b}", ref_bits);
                unimplemented!()
528 529
            }
        }
530

531 532 533
        if short_encode {
            return;
        } else {
qinsoon's avatar
qinsoon committed
534
            base = base.plus(objectmodel::REF_BITS_LEN * POINTER_SIZE);
qinsoon's avatar
qinsoon committed
535
        }
536 537 538 539
    }
}

#[inline(always)]
540
#[cfg(not(feature = "use-sidemap"))]
qinsoon's avatar
qinsoon committed
541 542 543 544 545 546
pub fn steal_trace_object(
    obj: ObjectReference,
    local_queue: &mut Vec<ObjectReference>,
    job_sender: &mpsc::Sender<ObjectReference>,
    mark_state: u8,
    immix_space: &ImmixSpace,
547
    lo_space: &FreeListSpace
qinsoon's avatar
qinsoon committed
548
) {
549 550
    if cfg!(debug_assertions) {
        // check if this object in within the heap, if it is an object
qinsoon's avatar
qinsoon committed
551 552 553
        if !immix_space.is_valid_object(obj.to_address()) &&
            !lo_space.is_valid_object(obj.to_address())
        {
554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584
            use std::process;

            println!("trying to trace an object that is not valid");
            println!("address: 0x{:x}", obj);
            println!("---");
            println!("immix space: {}", immix_space);
            println!("lo space: {}", lo_space);

            println!("invalid object during tracing");
            process::exit(101);
        }
    }

    let addr = obj.to_address();

    // mark object
    objectmodel::mark_as_traced(obj, mark_state);

    if immix_space.addr_in_space(addr) {
        // mark line
        immix_space.line_mark_table.mark_line_live(addr);
    } else if lo_space.addr_in_space(addr) {
        // do nothing
    } else {
        println!("unexpected address: {}", addr);
        println!("immix space: {}", immix_space);
        println!("lo space   : {}", lo_space);

        panic!("error during tracing object")
    }

585 586 587
    // this part of code has some duplication with code in objectdump
    // FIXME: remove the duplicate code - use 'Tracer' trait

qinsoon's avatar
qinsoon committed
588
    let hdr = unsafe { (addr + objectmodel::OBJECT_HEADER_OFFSET).load::<u64>() };
589 590 591 592 593 594 595 596

    if objectmodel::header_is_fix_size(hdr) {
        // fix sized type
        if objectmodel::header_has_ref_map(hdr) {
            // has ref map
            let ref_map = objectmodel::header_get_ref_map(hdr);

            match ref_map {
qinsoon's avatar
qinsoon committed
597
                0 => {}
598
                0b0000_0001 => {
qinsoon's avatar
qinsoon committed
599 600 601 602 603 604 605
                    steal_process_edge(
                        addr,
                        0,
                        local_queue,
                        job_sender,
                        mark_state,
                        immix_space,
606
                        lo_space
qinsoon's avatar
qinsoon committed
607
                    );
608 609
                }
                0b0000_0011 => {
qinsoon's avatar
qinsoon committed
610 611 612 613 614 615 616
                    steal_process_edge(
                        addr,
                        0,
                        local_queue,
                        job_sender,
                        mark_state,
                        immix_space,
617
                        lo_space
qinsoon's avatar
qinsoon committed
618 619 620 621 622 623 624 625
                    );
                    steal_process_edge(
                        addr,
                        8,
                        local_queue,
                        job_sender,
                        mark_state,
                        immix_space,
626
                        lo_space
qinsoon's avatar
qinsoon committed
627 628
                    );
                }
629
                0b0000_1111 => {
qinsoon's avatar
qinsoon committed
630 631 632 633 634 635 636
                    steal_process_edge(
                        addr,
                        0,
                        local_queue,
                        job_sender,
                        mark_state,
                        immix_space,
637
                        lo_space
qinsoon's avatar
qinsoon committed
638 639 640 641 642 643 644 645
                    );
                    steal_process_edge(
                        addr,
                        8,
                        local_queue,
                        job_sender,
                        mark_state,
                        immix_space,
646
                        lo_space
qinsoon's avatar
qinsoon committed
647 648 649 650 651 652 653 654
                    );
                    steal_process_edge(
                        addr,
                        16,
                        local_queue,
                        job_sender,
                        mark_state,
                        immix_space,
655
                        lo_space
qinsoon's avatar
qinsoon committed
656 657 658 659 660 661 662 663
                    );
                    steal_process_edge(
                        addr,
                        24,
                        local_queue,
                        job_sender,
                        mark_state,
                        immix_space,
664
                        lo_space
qinsoon's avatar
qinsoon committed
665 666
                    );
                }
667
                _ => {
668 669 670 671
                    warn!("ref bits fall into slow path: {:b}", ref_map);

                    let mut i = 0;
                    while i < objectmodel::REF_MAP_LENGTH {
qinsoon's avatar
qinsoon committed
672
                        let has_ref: bool = ((ref_map >> i) & 1) == 1;
673 674

                        if has_ref {
qinsoon's avatar
qinsoon committed
675 676 677 678 679 680 681
                            steal_process_edge(
                                addr,
                                i * POINTER_SIZE,
                                local_queue,
                                job_sender,
                                mark_state,
                                immix_space,
682
                                lo_space
qinsoon's avatar
qinsoon committed
683
                            );
684 685 686 687
                        }

                        i += 1;
                    }
688 689 690 691
                }
            }
        } else {
            // by type ID
692 693 694
            let gctype_id = objectmodel::header_get_gctype_id(hdr);

            let gc_lock = MY_GC.read().unwrap();
qinsoon's avatar
qinsoon committed
695 696
            let gctype: Arc<GCType> =
                gc_lock.as_ref().unwrap().gc_types[gctype_id as usize].clone();
697 698

            for offset in gctype.gen_ref_offsets() {
qinsoon's avatar
qinsoon committed
699 700 701 702 703 704 705
                steal_process_edge(
                    addr,
                    offset,
                    local_queue,
                    job_sender,
                    mark_state,
                    immix_space,
706
                    lo_space
qinsoon's avatar
qinsoon committed
707
                );
708
            }
709 710 711
        }
    } else {
        // hybrids
712
        let gctype_id = objectmodel::header_get_gctype_id(hdr);
qinsoon's avatar
qinsoon committed
713
        let var_length = objectmodel::header_get_hybrid_length(hdr);
714 715

        let gc_lock = MY_GC.read().unwrap();
qinsoon's avatar
qinsoon committed
716
        let gctype: Arc<GCType> = gc_lock.as_ref().unwrap().gc_types[gctype_id as usize].clone();
717

qinsoon's avatar
qinsoon committed
718
        for offset in gctype.gen_hybrid_ref_offsets(var_length) {
qinsoon's avatar
qinsoon committed
719 720 721 722 723 724 725
            steal_process_edge(
                addr,
                offset,
                local_queue,
                job_sender,
                mark_state,
                immix_space,
726
                lo_space
qinsoon's avatar
qinsoon committed
727
            );
728
        }
729 730 731 732 733
    }
}

#[inline(always)]
#[cfg(feature = "use-sidemap")]
qinsoon's avatar
qinsoon committed
734 735 736 737 738 739 740
pub fn steal_process_edge(
    base: Address,
    offset: usize,
    local_queue: &mut Vec<ObjectReference>,
    job_sender: &mpsc::Sender<ObjectReference>,
    mark_state: u8,
    immix_space: &ImmixSpace,
741
    lo_space: &FreeListSpace
qinsoon's avatar
qinsoon committed
742
) {
qinsoon's avatar
qinsoon committed
743
    let field_addr = base.plus(offset);
qinsoon's avatar
qinsoon committed
744 745
    let edge = unsafe { field_addr.load::<ObjectReference>() };

qinsoon's avatar
qinsoon committed
746
    if cfg!(debug_assertions) {
qinsoon's avatar
qinsoon committed
747
        use std::process;
qinsoon's avatar
qinsoon committed
748
        // check if this object in within the heap, if it is an object
qinsoon's avatar
qinsoon committed
749 750 751
        if !edge.to_address().is_zero() && !immix_space.is_valid_object(edge.to_address()) &&
            !lo_space.is_valid_object(edge.to_address())
        {
qinsoon's avatar
qinsoon committed
752
            println!("trying to follow an edge that is not a valid object");
qinsoon's avatar
qinsoon committed
753
            println!("edge address: 0x{:x} from 0x{:x}", edge, field_addr);
qinsoon's avatar
qinsoon committed
754 755
            println!("base address: 0x{:x}", base);
            println!("---");
756
            if immix_space.addr_in_space(base) {
qinsoon's avatar
qinsoon committed
757 758 759 760
                objectmodel::print_object(
                    base,
                    immix_space.start(),
                    immix_space.trace_map(),
761
                    immix_space.alloc_map()
qinsoon's avatar
qinsoon committed
762
                );
763 764 765
                println!("---");
                println!("immix space:{}", immix_space);
            } else if lo_space.addr_in_space(base) {
qinsoon's avatar
qinsoon committed
766 767 768 769
                objectmodel::print_object(
                    base,
                    lo_space.start(),
                    lo_space.trace_map(),
770
                    lo_space.alloc_map()
qinsoon's avatar
qinsoon committed
771
                );
772 773 774 775 776
                println!("---");
                println!("lo space:{}", lo_space);
            } else {
                println!("not in immix/lo space")
            }
qinsoon's avatar
qinsoon committed
777

qinsoon's avatar
qinsoon committed
778 779
            println!("invalid object during tracing");
            process::exit(101);
qinsoon's avatar
qinsoon committed
780 781
        }
    }
782

783
    if !edge.to_address().is_zero() {
qinsoon's avatar
qinsoon committed
784 785 786 787 788
        if immix_space.addr_in_space(edge.to_address()) &&
            !objectmodel::is_traced(
                immix_space.trace_map(),
                immix_space.start(),
                edge,
789
                mark_state
qinsoon's avatar
qinsoon committed
790
            ) {
791 792 793 794 795
            if local_queue.len() >= PUSH_BACK_THRESHOLD {
                job_sender.send(edge).unwrap();
            } else {
                local_queue.push(edge);
            }
qinsoon's avatar
qinsoon committed
796 797 798 799 800
        } else if lo_space.addr_in_space(edge.to_address()) &&
                   !objectmodel::is_traced(
                lo_space.trace_map(),
                lo_space.start(),
                edge,
801
                mark_state
qinsoon's avatar
qinsoon committed
802
            ) {
803 804 805 806
            if local_queue.len() >= PUSH_BACK_THRESHOLD {
                job_sender.send(edge).unwrap();
            } else {
                local_queue.push(edge);
807 808 809
            }
        }
    }
810 811 812 813
}

#[inline(always)]
#[cfg(not(feature = "use-sidemap"))]
qinsoon's avatar
qinsoon committed
814 815 816 817 818 819 820
pub fn steal_process_edge(
    base: Address,
    offset: usize,
    local_queue: &mut Vec<ObjectReference>,
    job_sender: &mpsc::Sender<ObjectReference>,
    mark_state: u8,
    immix_space: &ImmixSpace,
821
    lo_space: &FreeListSpace
qinsoon's avatar
qinsoon committed
822
) {
823
    let field_addr = base + offset;
qinsoon's avatar
qinsoon committed
824
    let edge = unsafe { field_addr.load::<ObjectReference>() };
825 826 827 828

    if cfg!(debug_assertions) {
        use std::process;
        // check if this object in within the heap, if it is an object
qinsoon's avatar
qinsoon committed
829 830 831
        if !edge.to_address().is_zero() && !immix_space.is_valid_object(edge.to_address()) &&
            !lo_space.is_valid_object(edge.to_address())
        {
832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862
            println!("trying to follow an edge that is not a valid object");
            println!("edge address: 0x{:x} from 0x{:x}", edge, field_addr);
            println!("base address: 0x{:x}", base);
            println!("---");
            if immix_space.addr_in_space(base) {
                objectmodel::print_object(base);
                objectmodel::print_object(edge.to_address());
                println!("---");
                println!("immix space:{}", immix_space);
            } else if lo_space.addr_in_space(base) {
                objectmodel::print_object(base);
                println!("---");
                println!("lo space:{}", lo_space);
            } else {
                println!("not in immix/lo space")
            }

            println!("invalid object during tracing");
            process::exit(101);
        }
    }

    if !edge.to_address().is_zero() {
        if !objectmodel::is_traced(edge, mark_state) {
            if local_queue.len() >= PUSH_BACK_THRESHOLD {
                job_sender.send(edge).unwrap();
            } else {
                local_queue.push(edge);
            }
        }
    }
863
}