radiance · commit

compiler: Reject overflowing arena allocations

db9890711300e893e28e6e066a13f043a628a4fdc1ba5bb7c55bfd1b2ba33d4e

Check alignment and allocation-size arithmetic before updating an arena offset.
Reject element-count multiplication overflow in typed slice allocation. The
allocator now preserves its state when a request cannot fit.

Alexis Sellier committed 1 month ago 1 parent 85034f8f

lib/std/arch/rv64/asm/parser.rad +2 -11

    while a.scan.current.kind <> scanner::TokenKind::Eof {
        try parseItem(a);
    }
}

/// Align `value` upward to `alignment`, returning nil on u32 overflow.
fn checkedAlignUp(value: u32, alignment: u32) -> ?u32 {
    let padding = alignment - 1;
    if value > parser::U32_MAX - padding {
        return nil;
    }
    return mem::alignUp(value, alignment);
}

/// Advance the parser by one token, preserving the previous token.
unsafe fn advance(a: &mut super::Assembler) {
    set a.scan.previous = a.scan.current;
    set a.scan.current = scanner::next(&mut a.scan);
}

        case super::Section::Text => {
            if amount % rv64::INSTR_SIZE as u32 <> 0 {
                throw fail(a, "text alignment must be a multiple of 4");
            }
            let bytes = a.text.len * rv64::INSTR_SIZE as u32;
            let aligned = checkedAlignUp(bytes, amount) else {
            let aligned = mem::checkedAlignUp(bytes, amount) else {
                throw super::Error::TextOverflow;
            };
            let words = (aligned - bytes) / rv64::INSTR_SIZE as u32;
            try emit::emitTextPadding(a, words);
        }
        case super::Section::Data => {
            let aligned = checkedAlignUp(a.data.len, amount) else {
            let aligned = mem::checkedAlignUp(a.data.len, amount) else {
                throw super::Error::DataOverflow;
            };
            for _ in a.data.len..aligned {
                try emit::emitByte(a, 0);
            }

lib/std/lang/alloc.rad +9 -4

/// appropriate type and initializing the memory.
export fn alloc(arena: &mut Arena, size: u32, alignment: u32) -> *mut opaque throws (AllocError) {
    assert alignment > 0;
    assert size > 0;

    let aligned = mem::alignUp(arena.offset, alignment);
    let newOffset = aligned + size;

    if newOffset > arena.data.len as u32 {
    let aligned = mem::checkedAlignUp(arena.offset, alignment) else {
        throw AllocError::OutOfMemory;
    };
    if aligned > arena.data.len or size > arena.data.len - aligned {
        throw AllocError::OutOfMemory;
    }
    let newOffset = aligned + size;

    let base: *mut u8 = &mut arena.data[aligned];
    set arena.offset = newOffset;

    return base as *mut opaque;
}

/// Throws `AllocError` if the arena is exhausted.
export unsafe fn allocSlice(arena: &mut Arena, size: u32, alignment: u32, count: u32) -> *mut [opaque] throws (AllocError) {
    if count == 0 {
        return &mut [];
    }
    if size > mem::MAX_SIZE / count {
        throw AllocError::OutOfMemory;
    }
    let ptr = try alloc(arena, size * count, alignment);

    return @sliceOf(ptr, count);
}


lib/std/mem.rad +17 -0

//! Memory operations and alignment helpers.

/// Maximum byte size or offset that fits in the 32-bit memory interface.
export constant MAX_SIZE: u32 = 0xffffffff;

/// Memory error.
union MemoryError: Copy {
    /// Buffer is too small.
    BufferTooSmall,
}

/// Align value up to alignment boundary.
export fn alignUp(value: u32, alignment: u32) -> u32 {
    return (value + alignment - 1) & ~(alignment - 1);
}

/// Align `value` upward, or return nil if the result exceeds `MAX_SIZE`.
/// `alignment` must be a nonzero power of two.
export fn checkedAlignUp(value: u32, alignment: u32) -> ?u32 {
    assert alignment > 0;
    let padding = alignment - 1;
    assert (alignment & padding) == 0;
    if value > MAX_SIZE - padding {
        return nil;
    }
    return alignUp(value, alignment);
}

/// Align signed value up to alignment boundary.
export fn alignUpI32(value: i32, alignment: i32) -> i32 {
    return (value + alignment - 1) & ~(alignment - 1);
}


lib/std/tests.rad +14 -0

    try testing::expect(buffer[2] == 0);
}

// mem /////////////////////////////////////////////////////////////////////////

/// Checked alignment accepts representable results and rejects overflow.
@test fn testCheckedAlignUp() throws (testing::TestError) {
    let alignment: u32 = 16;
    let lastAligned = mem::MAX_SIZE - (alignment - 1);
    assert mem::checkedAlignUp(0, alignment) == 0;
    assert mem::checkedAlignUp(1, alignment) == alignment;
    assert mem::checkedAlignUp(alignment, alignment) == alignment;
    assert mem::checkedAlignUp(lastAligned - 1, alignment) == lastAligned;
    assert mem::checkedAlignUp(lastAligned, alignment) == lastAligned;
    assert mem::checkedAlignUp(lastAligned + 1, alignment) == nil;
    assert mem::checkedAlignUp(mem::MAX_SIZE, alignment) == nil;
    assert mem::checkedAlignUp(mem::MAX_SIZE, 1) == mem::MAX_SIZE;
}

@test fn testCopyFullSlice() throws (testing::TestError) {
    let mut xs: [u8; 3] = [1, 2, 3];
    let mut ys: [u8; 3] = [4, 5, 6];

    try! mem::copy(&mut xs[..], &ys[..]);

596	587		case super::Section::Text => {
597	588		if amount % rv64::INSTR_SIZE as u32 <> 0 {
598	589		throw fail(a, "text alignment must be a multiple of 4");
599	590		}
600	591		let bytes = a.text.len * rv64::INSTR_SIZE as u32;
601		-	let aligned = checkedAlignUp(bytes, amount) else {
	592	+	let aligned = mem::checkedAlignUp(bytes, amount) else {
602	593		throw super::Error::TextOverflow;
603	594		};
604	595		let words = (aligned - bytes) / rv64::INSTR_SIZE as u32;
605	596		try emit::emitTextPadding(a, words);
606	597		}
607	598		case super::Section::Data => {
608		-	let aligned = checkedAlignUp(a.data.len, amount) else {
	599	+	let aligned = mem::checkedAlignUp(a.data.len, amount) else {
609	600		throw super::Error::DataOverflow;
610	601		};
611	602		for _ in a.data.len..aligned {
612	603		try emit::emitByte(a, 0);
613	604		}

37	37		/// appropriate type and initializing the memory.
38	38		export fn alloc(arena: &mut Arena, size: u32, alignment: u32) -> *mut opaque throws (AllocError) {
39	39		assert alignment > 0;
40	40		assert size > 0;
41	41
42		-	let aligned = mem::alignUp(arena.offset, alignment);
43		-	let newOffset = aligned + size;
44		-
45		-	if newOffset > arena.data.len as u32 {
	42	+	let aligned = mem::checkedAlignUp(arena.offset, alignment) else {
	43	+	throw AllocError::OutOfMemory;
	44	+	};
	45	+	if aligned > arena.data.len or size > arena.data.len - aligned {
46	46		throw AllocError::OutOfMemory;
47	47		}
	48	+	let newOffset = aligned + size;
	49	+
48	50		let base: *mut u8 = &mut arena.data[aligned];
49	51		set arena.offset = newOffset;
50	52
51	53		return base as *mut opaque;
52	54		}

97	99		/// Throws `AllocError` if the arena is exhausted.
98	100		export unsafe fn allocSlice(arena: &mut Arena, size: u32, alignment: u32, count: u32) -> *mut [opaque] throws (AllocError) {
99	101		if count == 0 {
100	102		return &mut [];
101	103		}
	104	+	if size > mem::MAX_SIZE / count {
	105	+	throw AllocError::OutOfMemory;
	106	+	}
102	107		let ptr = try alloc(arena, size * count, alignment);
103	108
104	109		return @sliceOf(ptr, count);
105	110		}
106	111

35	40		/// Align value up to alignment boundary.
36	41		export fn alignUp(value: u32, alignment: u32) -> u32 {
37	42		return (value + alignment - 1) & ~(alignment - 1);
38	43		}
39	44
	45	+	/// Align `value` upward, or return nil if the result exceeds `MAX_SIZE`.
	46	+	/// `alignment` must be a nonzero power of two.
	47	+	export fn checkedAlignUp(value: u32, alignment: u32) -> ?u32 {
	48	+	assert alignment > 0;
	49	+	let padding = alignment - 1;
	50	+	assert (alignment & padding) == 0;
	51	+	if value > MAX_SIZE - padding {
	52	+	return nil;
	53	+	}
	54	+	return alignUp(value, alignment);
	55	+	}
	56	+
40	57		/// Align signed value up to alignment boundary.
41	58		export fn alignUpI32(value: i32, alignment: i32) -> i32 {
42	59		return (value + alignment - 1) & ~(alignment - 1);
43	60		}
44	61

217	217		try testing::expect(buffer[2] == 0);
218	218		}
219	219
220	220		// mem /////////////////////////////////////////////////////////////////////////
221	221
	222	+	/// Checked alignment accepts representable results and rejects overflow.
	223	+	@test fn testCheckedAlignUp() throws (testing::TestError) {
	224	+	let alignment: u32 = 16;
	225	+	let lastAligned = mem::MAX_SIZE - (alignment - 1);
	226	+	assert mem::checkedAlignUp(0, alignment) == 0;
	227	+	assert mem::checkedAlignUp(1, alignment) == alignment;
	228	+	assert mem::checkedAlignUp(alignment, alignment) == alignment;
	229	+	assert mem::checkedAlignUp(lastAligned - 1, alignment) == lastAligned;
	230	+	assert mem::checkedAlignUp(lastAligned, alignment) == lastAligned;
	231	+	assert mem::checkedAlignUp(lastAligned + 1, alignment) == nil;
	232	+	assert mem::checkedAlignUp(mem::MAX_SIZE, alignment) == nil;
	233	+	assert mem::checkedAlignUp(mem::MAX_SIZE, 1) == mem::MAX_SIZE;
	234	+	}
	235	+
222	236		@test fn testCopyFullSlice() throws (testing::TestError) {
223	237		let mut xs: [u8; 3] = [1, 2, 3];
224	238		let mut ys: [u8; 3] = [4, 5, 6];
225	239
226	240		try! mem::copy(&mut xs[..], &ys[..]);

27	27		while a.scan.current.kind <> scanner::TokenKind::Eof {
28	28		try parseItem(a);
29	29		}
30	30		}
31	31
32		-	/// Align `value` upward to `alignment`, returning nil on u32 overflow.
33		-	fn checkedAlignUp(value: u32, alignment: u32) -> ?u32 {
34		-	let padding = alignment - 1;
35		-	if value > parser::U32_MAX - padding {
36		-	return nil;
37		-	}
38		-	return mem::alignUp(value, alignment);
39		-	}
40		-
41	32		/// Advance the parser by one token, preserving the previous token.
42	33		unsafe fn advance(a: &mut super::Assembler) {
43	34		set a.scan.previous = a.scan.current;
44	35		set a.scan.current = scanner::next(&mut a.scan);
45	36		}

	1	+	//! Memory operations and alignment helpers.
	2	+
	3	+	/// Maximum byte size or offset that fits in the 32-bit memory interface.
	4	+	export constant MAX_SIZE: u32 = 0xffffffff;
	5	+
1	6		/// Memory error.
2	7		union MemoryError: Copy {
3	8		/// Buffer is too small.
4	9		BufferTooSmall,
5	10		}