immix_space.rs 15.1 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
use heap::immix;
use heap::gc;
use utils::Address;
use common::AddressMap;
19
use utils::mem::malloc_zero;
qinsoon's avatar
qinsoon committed
20
use utils::mem::memmap;
21
use utils::mem::memsec;
22 23 24 25 26 27

use std::*;
use std::collections::LinkedList;
use std::sync::Mutex;
use std::sync::Arc;

qinsoon's avatar
qinsoon committed
28 29 30 31
// this table will be accessed through unsafe raw pointers. since Rust doesn't provide a
// data structure for such guarantees:
// 1. Non-overlapping segments of this table may be accessed parallelly from different mutator
//    threads
32 33 34 35
// 2. One element may be written into at the same time by different gc threads during tracing

#[derive(Clone)]
pub struct LineMarkTable {
qinsoon's avatar
qinsoon committed
36 37
    space_start: Address,
    ptr: *mut immix::LineMark,
38
    len: usize
39 40 41 42
}

#[derive(Clone)]
pub struct LineMarkTableSlice {
qinsoon's avatar
qinsoon committed
43
    ptr: *mut immix::LineMark,
44
    len: usize
45 46 47 48
}

impl LineMarkTable {
    pub fn new(space_start: Address, space_end: Address) -> LineMarkTable {
49
        let line_mark_table_len = (space_end - space_start) / immix::BYTES_IN_LINE;
50
        let line_mark_table = {
qinsoon's avatar
qinsoon committed
51 52 53
            let ret = unsafe {
                malloc_zero(mem::size_of::<immix::LineMark>() * line_mark_table_len)
            } as *mut immix::LineMark;
54
            let mut cursor = ret;
qinsoon's avatar
qinsoon committed
55

56
            for _ in 0..line_mark_table_len {
qinsoon's avatar
qinsoon committed
57 58 59 60
                unsafe {
                    *cursor = immix::LineMark::Free;
                }
                cursor = unsafe { cursor.offset(1) };
61
            }
qinsoon's avatar
qinsoon committed
62

63 64
            ret
        };
qinsoon's avatar
qinsoon committed
65 66 67 68

        LineMarkTable {
            space_start: space_start,
            ptr: line_mark_table,
69
            len: line_mark_table_len
qinsoon's avatar
qinsoon committed
70
        }
71
    }
qinsoon's avatar
qinsoon committed
72

73
    pub fn take_slice(&mut self, start: usize, len: usize) -> LineMarkTableSlice {
qinsoon's avatar
qinsoon committed
74 75
        LineMarkTableSlice {
            ptr: unsafe { self.ptr.offset(start as isize) },
76
            len: len
qinsoon's avatar
qinsoon committed
77
        }
78
    }
qinsoon's avatar
qinsoon committed
79

80 81 82 83
    #[inline(always)]
    #[allow(dead_code)]
    fn get(&self, index: usize) -> immix::LineMark {
        debug_assert!(index <= self.len);
qinsoon's avatar
qinsoon committed
84
        unsafe { *self.ptr.offset(index as isize) }
85
    }
qinsoon's avatar
qinsoon committed
86

87 88 89
    #[inline(always)]
    fn set(&self, index: usize, value: immix::LineMark) {
        debug_assert!(index <= self.len);
qinsoon's avatar
qinsoon committed
90
        unsafe { *self.ptr.offset(index as isize) = value };
91
    }
92 93

    pub fn index_to_address(&self, index: usize) -> Address {
94
        self.space_start + (index << immix::LOG_BYTES_IN_LINE)
95
    }
qinsoon's avatar
qinsoon committed
96

97 98
    #[inline(always)]
    pub fn mark_line_live(&self, addr: Address) {
99
        let line_table_index = (addr - self.space_start) >> immix::LOG_BYTES_IN_LINE;
qinsoon's avatar
qinsoon committed
100

101
        self.set(line_table_index, immix::LineMark::Live);
qinsoon's avatar
qinsoon committed
102

103 104 105 106
        if line_table_index < self.len - 1 {
            self.set(line_table_index + 1, immix::LineMark::ConservLive);
        }
    }
107

108 109
    #[inline(always)]
    pub fn mark_line_live2(&self, space_start: Address, addr: Address) {
110
        let line_table_index = (addr - space_start) >> immix::LOG_BYTES_IN_LINE;
111

112
        self.set(line_table_index, immix::LineMark::Live);
113

114 115
        if line_table_index < self.len - 1 {
            self.set(line_table_index + 1, immix::LineMark::ConservLive);
116
        }
117 118 119
    }
}

120 121 122 123 124 125
impl Drop for LineMarkTable {
    fn drop(&mut self) {
        unsafe { memsec::free(self.ptr) }
    }
}

126 127 128 129
impl LineMarkTableSlice {
    #[inline(always)]
    pub fn get(&self, index: usize) -> immix::LineMark {
        debug_assert!(index <= self.len);
qinsoon's avatar
qinsoon committed
130
        unsafe { *self.ptr.offset(index as isize) }
131 132 133 134
    }
    #[inline(always)]
    pub fn set(&mut self, index: usize, value: immix::LineMark) {
        debug_assert!(index <= self.len);
qinsoon's avatar
qinsoon committed
135
        unsafe { *self.ptr.offset(index as isize) = value };
136 137 138 139 140 141 142 143 144
    }
    #[inline(always)]
    pub fn len(&self) -> usize {
        self.len
    }
}

#[repr(C)]
pub struct ImmixSpace {
qinsoon's avatar
qinsoon committed
145 146 147
    start: Address,
    end: Address,

148
    // these maps are writable at allocation, read-only at collection
qinsoon's avatar
qinsoon committed
149 150
    pub alloc_map: Arc<AddressMap<u8>>,

151
    // these maps are only for collection
qinsoon's avatar
qinsoon committed
152 153 154 155 156 157
    pub trace_map: Arc<AddressMap<u8>>,

    // this table will be accessed through unsafe raw pointers. since Rust doesn't provide a
    // data structure for such guarantees:
    // 1. Non-overlapping segments of this table may be accessed parallelly from different mutator
    //    threads
158
    // 2. One element may be written into at the same time by different gc threads during tracing
qinsoon's avatar
qinsoon committed
159 160 161 162
    pub line_mark_table: LineMarkTable,

    total_blocks: usize, // for debug use

163
    #[allow(dead_code)]
164
    mmap: memmap::MmapMut,
qinsoon's avatar
qinsoon committed
165
    usable_blocks: Mutex<LinkedList<Box<ImmixBlock>>>,
166
    used_blocks: Mutex<LinkedList<Box<ImmixBlock>>>
167 168 169
}

pub struct ImmixBlock {
qinsoon's avatar
qinsoon committed
170 171 172 173
    id: usize,
    state: immix::BlockMark,
    start: Address,

174
    // a segment of the big line mark table in ImmixSpace
175
    line_mark_table: LineMarkTableSlice
176 177
}

qinsoon's avatar
qinsoon committed
178
const SPACE_ALIGN: usize = 1 << 19;
179 180

impl ImmixSpace {
qinsoon's avatar
qinsoon committed
181
    pub fn new(space_size: usize) -> ImmixSpace {
182
        // acquire memory through mmap
183 184 185 186 187 188
        let mut anon_mmap: memmap::MmapMut =
            match memmap::MmapMut::map_anon(space_size + SPACE_ALIGN) {
                Ok(m) => m,
                Err(_) => panic!("failed to call mmap")
            };
        let start: Address = Address::from_ptr::<u8>(anon_mmap.as_mut_ptr()).align_up(SPACE_ALIGN);
qinsoon's avatar
qinsoon committed
189 190
        let end: Address = start + space_size;

191
        let line_mark_table = LineMarkTable::new(start, end);
qinsoon's avatar
qinsoon committed
192

qinsoon's avatar
qinsoon committed
193 194 195 196 197 198 199 200 201
        let trace_map = AddressMap::new(start, end);
        if cfg!(debug_assertions) {
            // access every of its cells
            trace_map.init_all(0);
        }
        let alloc_map = AddressMap::new(start, end);
        if cfg!(debug_assertions) {
            alloc_map.init_all(0);
        }
qinsoon's avatar
qinsoon committed
202

203
        let mut ret = ImmixSpace {
qinsoon's avatar
qinsoon committed
204 205
            start: start,
            end: end,
206 207 208
            mmap: anon_mmap,

            line_mark_table: line_mark_table,
qinsoon's avatar
qinsoon committed
209 210
            trace_map: Arc::new(trace_map),
            alloc_map: Arc::new(alloc_map),
211 212
            usable_blocks: Mutex::new(LinkedList::new()),
            used_blocks: Mutex::new(LinkedList::new()),
213
            total_blocks: 0
214
        };
qinsoon's avatar
qinsoon committed
215

216
        ret.init_blocks();
qinsoon's avatar
qinsoon committed
217

218 219
        ret
    }
qinsoon's avatar
qinsoon committed
220

221 222 223 224
    fn init_blocks(&mut self) -> () {
        let mut id = 0;
        let mut block_start = self.start;
        let mut line = 0;
qinsoon's avatar
qinsoon committed
225

226
        let mut usable_blocks_lock = self.usable_blocks.lock().unwrap();
qinsoon's avatar
qinsoon committed
227

228
        while block_start + immix::BYTES_IN_BLOCK <= self.end {
229
            usable_blocks_lock.push_back(Box::new(ImmixBlock {
qinsoon's avatar
qinsoon committed
230
                id: id,
231 232
                state: immix::BlockMark::Usable,
                start: block_start,
233
                line_mark_table: self.line_mark_table.take_slice(line, immix::LINES_IN_BLOCK)
234
            }));
qinsoon's avatar
qinsoon committed
235

236
            id += 1;
237
            block_start = block_start + immix::BYTES_IN_BLOCK;
238 239
            line += immix::LINES_IN_BLOCK;
        }
qinsoon's avatar
qinsoon committed
240

241 242
        self.total_blocks = id;
    }
qinsoon's avatar
qinsoon committed
243 244 245

    pub fn return_used_block(&self, old: Box<ImmixBlock>) {
        // Unsafe and raw pointers are used to transfer ImmixBlock to/from each Mutator.
246
        // This avoids explicit ownership transferring
qinsoon's avatar
qinsoon committed
247 248 249 250
        // If we explicitly transfer ownership, the function needs to own the Mutator in order to
        // move the ImmixBlock out of it (see ImmixMutatorLocal.alloc_from_global()),
        // and this will result in passing the Mutator object as value
        // (instead of a borrowed reference) all the way in the allocation
251 252
        self.used_blocks.lock().unwrap().push_front(old);
    }
qinsoon's avatar
qinsoon committed
253

254 255
    #[allow(unreachable_code)]
    pub fn get_next_usable_block(&self) -> Option<Box<ImmixBlock>> {
qinsoon's avatar
qinsoon committed
256 257
        let res_new_block: Option<Box<ImmixBlock>> =
            { self.usable_blocks.lock().unwrap().pop_front() };
258 259 260
        if res_new_block.is_none() {
            // should unlock, and call GC here
            gc::trigger_gc();
qinsoon's avatar
qinsoon committed
261

262 263 264
            None
        } else {
            res_new_block
qinsoon's avatar
qinsoon committed
265
        }
266
    }
qinsoon's avatar
qinsoon committed
267

268
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
269
    #[allow(unused_assignments)]
270 271 272 273
    pub fn sweep(&self) {
        let mut free_lines = 0;
        let mut usable_blocks = 0;
        let mut full_blocks = 0;
qinsoon's avatar
qinsoon committed
274

275
        let mut used_blocks_lock = self.used_blocks.lock().unwrap();
276

277
        let mut usable_blocks_lock = self.usable_blocks.lock().unwrap();
278
        usable_blocks = usable_blocks_lock.len();
qinsoon's avatar
qinsoon committed
279 280

        let mut live_blocks: LinkedList<Box<ImmixBlock>> = LinkedList::new();
281 282 283

        while !used_blocks_lock.is_empty() {
            let mut block = used_blocks_lock.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
284

285
            let mut has_free_lines = false;
qinsoon's avatar
qinsoon committed
286

287 288 289
            {
                let mut cur_line_mark_table = block.line_mark_table_mut();
                for i in 0..cur_line_mark_table.len() {
qinsoon's avatar
qinsoon committed
290 291 292
                    if cur_line_mark_table.get(i) != immix::LineMark::Live &&
                        cur_line_mark_table.get(i) != immix::LineMark::ConservLive
                    {
293 294
                        has_free_lines = true;
                        cur_line_mark_table.set(i, immix::LineMark::Free);
qinsoon's avatar
qinsoon committed
295

296 297 298
                        free_lines += 1;
                    }
                }
qinsoon's avatar
qinsoon committed
299

300 301
                // release the mutable borrow of 'block'
            }
qinsoon's avatar
qinsoon committed
302

303 304 305 306 307 308 309 310 311 312 313
            if has_free_lines {
                block.set_state(immix::BlockMark::Usable);
                usable_blocks += 1;

                usable_blocks_lock.push_front(block);
            } else {
                block.set_state(immix::BlockMark::Full);
                full_blocks += 1;
                live_blocks.push_front(block);
            }
        }
qinsoon's avatar
qinsoon committed
314

315
        used_blocks_lock.append(&mut live_blocks);
qinsoon's avatar
qinsoon committed
316

317
        if cfg!(debug_assertions) {
318
            debug!("---immix space---");
qinsoon's avatar
qinsoon committed
319 320 321 322 323 324
            debug!(
                "free lines    = {} of {} total ({} blocks)",
                free_lines,
                self.total_blocks * immix::LINES_IN_BLOCK,
                self.total_blocks
            );
qinsoon's avatar
qinsoon committed
325 326
            debug!("usable blocks = {}", usable_blocks);
            debug!("full blocks   = {}", full_blocks);
327
        }
qinsoon's avatar
qinsoon committed
328

329 330
        if full_blocks == self.total_blocks {
            println!("Out of memory in Immix Space");
qinsoon's avatar
qinsoon committed
331
            process::exit(1);
332
        }
qinsoon's avatar
qinsoon committed
333

334 335
        debug_assert!(full_blocks + usable_blocks == self.total_blocks);
    }
qinsoon's avatar
qinsoon committed
336

337 338 339 340 341 342
    pub fn start(&self) -> Address {
        self.start
    }
    pub fn end(&self) -> Address {
        self.end
    }
qinsoon's avatar
qinsoon committed
343

344 345 346 347 348 349 350 351 352 353
    pub fn line_mark_table(&self) -> &LineMarkTable {
        &self.line_mark_table
    }

    #[inline(always)]
    pub fn addr_in_space(&self, addr: Address) -> bool {
        addr >= self.start && addr < self.end
    }
}

354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376
use heap::Space;
impl Space for ImmixSpace {
    #[inline(always)]
    fn start(&self) -> Address {
        self.start
    }

    #[inline(always)]
    fn end(&self) -> Address {
        self.end
    }

    #[inline(always)]
    fn alloc_map(&self) -> *mut u8 {
        self.alloc_map.ptr
    }

    #[inline(always)]
    fn trace_map(&self) -> *mut u8 {
        self.trace_map.ptr
    }
}

377
impl ImmixBlock {
qinsoon's avatar
qinsoon committed
378
    pub fn get_next_available_line(&self, cur_line: usize) -> Option<usize> {
379 380 381
        let mut i = cur_line;
        while i < self.line_mark_table.len {
            match self.line_mark_table.get(i) {
qinsoon's avatar
qinsoon committed
382 383 384 385 386 387
                immix::LineMark::Free => {
                    return Some(i);
                }
                _ => {
                    i += 1;
                }
388 389 390 391
            }
        }
        None
    }
qinsoon's avatar
qinsoon committed
392 393

    pub fn get_next_unavailable_line(&self, cur_line: usize) -> usize {
394 395 396
        let mut i = cur_line;
        while i < self.line_mark_table.len {
            match self.line_mark_table.get(i) {
qinsoon's avatar
qinsoon committed
397 398 399 400 401 402
                immix::LineMark::Free => {
                    i += 1;
                }
                _ => {
                    return i;
                }
403 404 405 406
            }
        }
        i
    }
407 408 409 410 411

    pub fn lazy_zeroing(&mut self) {
        let line_mark_table = self.line_mark_table();
        for i in 0..line_mark_table.len {
            if line_mark_table.get(i) == immix::LineMark::Free {
qinsoon's avatar
qinsoon committed
412
                let line_start: Address = self.start + (i << immix::LOG_BYTES_IN_LINE);
413 414 415 416 417 418 419 420

                // zero the line
                unsafe {
                    memsec::memzero(line_start.to_ptr_mut::<u8>(), immix::BYTES_IN_LINE);
                }
            }
        }
    }
qinsoon's avatar
qinsoon committed
421

422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451
    pub fn id(&self) -> usize {
        self.id
    }
    pub fn start(&self) -> Address {
        self.start
    }
    pub fn set_state(&mut self, mark: immix::BlockMark) {
        self.state = mark;
    }
    #[inline(always)]
    pub fn line_mark_table(&self) -> &LineMarkTableSlice {
        &self.line_mark_table
    }
    #[inline(always)]
    pub fn line_mark_table_mut(&mut self) -> &mut LineMarkTableSlice {
        &mut self.line_mark_table
    }
}

/// Using raw pointers forbid the struct being shared between threads
/// we ensure the raw pointers won't be an issue, so we allow Sync/Send on ImmixBlock
unsafe impl Sync for ImmixBlock {}
unsafe impl Send for ImmixBlock {}
unsafe impl Sync for ImmixSpace {}
unsafe impl Send for ImmixSpace {}

impl fmt::Display for ImmixSpace {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "ImmixSpace\n").unwrap();
        write!(f, "range={:#X} ~ {:#X}\n", self.start, self.end).unwrap();
qinsoon's avatar
qinsoon committed
452

453
        // print table by vec
qinsoon's avatar
qinsoon committed
454 455 456 457 458 459 460 461 462 463 464
        //        write!(f, "table={{\n").unwrap();
        //        for i in 0..self.line_mark_table_len {
        //            write!(f, "({})", i).unwrap();
        //            write!(f, "{:?},", unsafe{*self.line_mark_table.offset(i as isize)}).unwrap();
        //            if i % immix::BYTES_IN_LINE == immix::BYTES_IN_LINE - 1 {
        //                write!(f, "\n").unwrap();
        //            }
        //        }
        //        write!(f, "\n}}\n").unwrap();


465
        write!(f, "t_ptr={:?}\n", self.line_mark_table.ptr).unwrap();
qinsoon's avatar
qinsoon committed
466 467 468 469 470 471 472 473
        //        write!(f, "usable blocks:\n").unwrap();
        //        for b in self.usable_blocks.iter() {
        //            write!(f, "  {}\n", b).unwrap();
        //        }
        //        write!(f, "used blocks:\n").unwrap();
        //        for b in self.used_blocks.iter() {
        //            write!(f, "  {}\n", b).unwrap();
        //        }
474 475 476 477 478
        write!(f, "done\n")
    }
}

impl fmt::Display for ImmixBlock {
qinsoon's avatar
qinsoon committed
479
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
480 481 482 483 484 485 486 487
        write!(
            f,
            "ImmixBlock#{}(state={:?}, address=0x{:X})",
            self.id,
            self.state,
            self.start
        )
    }
qinsoon's avatar
qinsoon committed
488 489 490
}

impl fmt::Debug for ImmixBlock {
491
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
qinsoon's avatar
qinsoon committed
492 493 494 495 496 497 498 499 500
        write!(
            f,
            "ImmixBlock#{}(state={:?}, address={:#X}, line_table={:?}",
            self.id,
            self.state,
            self.start,
            self.line_mark_table.ptr
        ).unwrap();

501 502 503 504 505 506
        write!(f, "[").unwrap();
        for i in 0..immix::LINES_IN_BLOCK {
            write!(f, "{:?},", self.line_mark_table.get(i)).unwrap();
        }
        write!(f, "]")
    }
507
}