Non-linear memory safety

[TylerBloom]

Hello, this will hopefully be the first part of a larger design discussion. I love the idea of being able to compile Rust code for the GBC; however, in order to do so safely, parts of the hardware need to be modeled at some level point.

Unlike most modern computers, the Gameboy had a non-linear memory space. In other words, multiple physical chips were mapped to the same memory addresses. This was controlled by various registers in the memory space. For example, the Gameboy Color had a WRAM selection register at 0xFF70. Changing this register would change what chip was used in the address range 0xD000..=0xDFFF.

Why is this an issue? Rust's memory safety rules assume that your memory safe does not have connections like this. That is, if you have mutable access to a given address/address slice, nothing can change the values you are pointing at except you. This is not true for the GB. If you have a reference into the WRAM address space, the value you are pointing at can be changed by writing to the selection register.

What am I proposing? We should provide a crate that models the hardware behavior for users. This would look something like a HAL (hardware abstraction layer). The goal of this library would be to capture the behavior of the hardware in a safe way so that users don't have to write unsafe code. Part of capturing the unsafe code would be us upholding the necessary safety rules, and handling non-linear memory safety would be a good starting point.

[zlfn]

@TylerBloom
It looks good. Maybe it's in the form of writing codes with GB assembly, wrapping that functions safely with Rust, right?
Honestly, I was going to entrust GBDK with all the memory management, and safe memory mapping is a point I've never thought about.
It looks like it's going to be a very big task, so can you recommend some reading materials to understand this?

[zlfn]

Thanks, I understood the concept. And I think it's a very neat and good idea. But there are a few points to think about.
First, GBDK's functions probably have their own assembly code to manage the WRAM (I don't know very exactly), and they most likely didn't assume that the user would access the memory "manually" (from GBDK's point of view). And this is "unsafe" on Rust's side either.
Second, Isn't there a chance of conflict with SDCC's array management? Are all arrays necessarily assigned through Safe tool? Anyway, I think we need to find out how each tools manage Gameboy's memory. GBDK might not be used, but SDCC is inevitable.

First of all, I'll research how to use an in-line assembly. (Also, I need to study more about Game Boy and the structure of the computer.) 🧑‍🎓

[TylerBloom]

they most likely didn't assume that the user would access the memory "manually"

It is understandable that GBDK would expect that from users (especially if they are accessing that area via an allocator). However, what I was saying doesn't require that you access it "manually". Because of Rust's aliasing rules, changing the memory bank while you have any reference into that bank is undefined behavior. C has much weaker rules around aliasing, so this is probably fine there.

Second, Isn't there a chance of conflict with SDCC's array management?

Yes, we need to be mindful of this. I'm still learning how everything works.

Are all arrays necessarily assigned through Safe tool?

This is a really good question. I think we should they to do this. One of Rust's core rules is that undefined behavior can not happen in safe Rust. I would like to maintain this rule; however, like you said, this is a large task.

Anyway, I think we need to find out how each tools manage Gameboy's memory. GBDK might not be used, but SDCC is inevitable

Yes, I definitely need to improve my knowledge of these tools. Do you think we can (or should) try to rewrite, fork, or edit these tools if we need to? This will depend on what the goal of this project becomes, of course.

What are the plans for testing this? Because Rust has many more rules than C, we should have a plan for testing to ensure we are upholding these rules. Of course, a good starting point for testing is getting a better understanding of the tools that we are using.

[zlfn]

I think we should they to do this. One of Rust's core rules is that undefined behavior can not happen in safe Rust. I would like to maintain this rule; however, like you said, this is a large task.

I agree. Maybe we can make some new collection types for Gameboy. (like gb::GBAray<u8> / gb::GBVec<u8>?)

Do you think we can (or should) try to rewrite, fork, or edit these tools if we need to? This will depend on what the goal of this project becomes, of course.

In the end, we may have to, but I want to avoid it right now.
SDCC and LLVM-CBE are projects that are maintained in a much larger team than ours, and it is easier to post-process the resulting C or ASM files for our purpose than to modify SDCC yet.

Probably we can modify GBDK, but I want to aim for independence from C library eventually.

What are the plans for testing this? Because Rust has many more rules than C, we should have a plan for testing to ensure we are upholding these rules. Of course, a good starting point for testing is getting a better understanding of the tools that we are using.

I haven't thought about how to 'test' this now. All we can see automatically in current project is whether the compilation works or not.
If I understand correctly, I think the test of the ROM file should be done with a whether the value went into the register or specific WRAM/VRAM address normally, is there an emulator to do this?

[TylerBloom]

Maybe we can make some new collection types for Gameboy. (like gb::GBAray / gb::GBVec?)

We very likely need a new collection type. I don't know what that collection should looks like or how you would use it. Once I get a better understanding on the tools, I'll be more certain. One idea that I thought of was an having a API similar to std::thread::scope. This would give the user access to a bank and we can ensure that if data is leaked from the inner scope, it must be cloned. Again, how this interacts with the tools, I don't know yet.

Everything you said about managing and editing the dependencies makes sense. If we can avoid extra work, we should.

If I understand correctly, I think the test of the ROM file should be done with a whether the value went into the register or specific WRAM/VRAM address normally, is there an emulator to do this?

I'm working on an emulator, in Rust. It is still a work in progress, but I'm getting close to being able to test full it with games. The actual emulator logic is its own crate, so we can use it for testing without needing to also pull in the whole UI. Here's a link to it:

https://github.com/TylerBloom/specte-rs/tree/main/spirit

[zlfn]

I think we need to understand the tools too, so I'm going to start by creating an API that allows direct (unsafe) access to the WRAM and see how Rust codes are compiled into C codes and how SDCC deals with that codes.

It's nice that you're creating an emulator that can test the rom.
I hope it can be used for unit testing for this project!

[zlfn]

I have implemented a simple idea sketch of BankArray.
If you have any feedback, please leave it.
https://github.com/zlfn/rust-gb/blob/main/source/src/memory.rs

/// Array corresponding to the memory of each bank
pub struct BankArray<T> {
    bank: MemBank,
    size: usize,
    ptr: *mut T,
}

BankArray is an array assigned to a particular bank space that has an address and size together.
It can be created unsafely from raw pointers at this time, if we implement the allocator in the future, we will be able to create it safely.

I haven't thought of safe referencing for this collection yet. I've implemented the safe (with bound) Index trait, but it's not safe if the bank changes.
I think it would be good to do it in a similar way to the aforementioned std::thread::scope, and I think we can also manage it through lifetime, which feels like "Bank is don't change during this lifetime range."

What's troubling is that the stack of sm83 is in the WRAM where banking is done. If we switch the bank, the stack looks like it's going to be broken. (I've never tested it, so I'm not sure.) In addition, arrays sized at compilation time appear to be stored in the stack. Therefore, the stack can become very large.

[zlfn]

I suggest the form as below. The big picture is the same as the code in your PR

1. BankManager now can used for non-banked RAM area, such as WRAM0 (0xC000-) or HRAM. bank_start_addr is now bank_addr: Range<u16> and has both start and end. And bank_selection_addr is now Optional. When bank_selection_addr is None, this means no bank switching occurs for that area.
   BankManager now manages the entire specific RAM area, rather than the bank.

#[non_exhaustive]
pub struct BankManager {
    bank_selection_addr: Option<u16>,
    bank_addr: Range<u16>,
}

2. MemoryMap has Option<BankManager> for each external_ram, work_ram_1, work_ram_0, high_ram. Some means that the area will be used in rust-gb. None means that the area will be used by an external dependencies, so it will not be used in rust-gb.

#[non_exhaustive]
pub struct MemoryMap {
    /// The manager for the external RAM banks
    pub external_ram: Option<BankManager>,
    /// The manager for the work RAM banks
    pub work_ram_1: Option<BankManager>,
    pub work_ram_0: Option<BankManager>,
    /// The manager for the high RAM banks
    pub high_ram: Option<BankManager>
}

3. MemoryMap::new() receives usage areas for each RAM areas. This function is unsafe, and this mean we have to ensure that it is not invaded by the program stack or other tools when using this area.

For Example,

MemoryMap::new(
    None, //ERAM
    Some(BankManager::new(Some(0xFFFF), 0xD000..0xDE00), //WRAM1
    None,  //WRAM0
    None //HRAM
)

means that we will use WRAM1 area from address 0xD000..0xDE00 and we can ensure that area is not invaded by stack or other tools. (Because the program stack is used from the high address in WRAM1, it is equivalent to guaranteeing that the stack size does not exceed 0x200)

4. MemoryMap::default() provides a memory area that can be guaranteed in advance that it is not invaded by GBDK or SDCC, and in general, this function will be used.
   The example below provides only ERAM and WRAM0. This is a non-used area from GBDK or SDCC, at least as far as I understand, but it could be changed if we understand SDCC and GBDK better.

pub unsafe fn default() -> Self {
    Self {
        external_ram: Some(BankManager::new(Some(0x0000), 0xA000..0xAFFF)),
        work_ram_1: None,
        work_ram_0: Some(BankManager::new(None, 0xC000..0xCFFF)),
        high_ram: None,
    }
}

Because this function must be called at the beginning of the program, it will be able to provide a macro like #[tokio::main] as you mentioned.

You can check out my ideas here.
https://github.com/zlfn/rust-gb/blob/memory-safety/source/src/memory.rs

I hope you can let me know what you think.

[TylerBloom]

I wish we could make it clear that WRAM is unsafe and ERAM is safe, while accessing both with the same forms of API. Is there a way to do that?

I agree with the first part of this sentence. Our toolchain is managing the stack and WRAM, so we should limit how much we allow our users to access WRAM. Perhaps, we should entirely restrict their access.

How can we design these multiple RAM banking? We might use multiple BankManagers. However, If it were to be separated like that, I think the code can become very promiscuous

It is my goal that we have a BankManager for each group of switchable banks. For example, we would have a manager for the eRAM and the eROM (we would have to wrap them in different types to make sure that the eROM is read-only, but that's easy).

I think it is a good idea to have very exacting code to model the strange memory model of the GB. After that, we work to make the API easier to use. This is a common pattern for embedded/#[no_std] architectures. Communities start with a very low level layer of abstraction to make everything safer to work with, and then they develop layers of tools to make things nice and easy to use. If you try to do both at the same time, you are very likely to have premature optimizations, which we really don't want.

I wanted to say this before I discuss my thoughts on your points because I wanted it to be clear what my goals are.

BankManager now can used for non-banked RAM area, such as WRAM0 (0xC000-) or HRAM. bank_start_addr is now bank_addr: Range and has both start and end. And bank_selection_addr is now Optional. When bank_selection_addr is None, this means no bank switching occurs for that area.

I have several problems with this. First, we want to avoid runtime checks like having Options at this low level. Having an option would mean that we have to check this every time we try to allocate an object into this region of memory or index into it. This check would have to happen for every BankManager. We know at compile time if the BankManager has None or Some selection address; therefore, we should encode that difference as two different types. If you look at my PR, you will see that I checked the BankManager to be a zero-sized type by using associated constants.

Second, BankManagers need to have the special BankPtr type to carry around the bank number. This is not the case for HRAM and (non-banked) WRAM. HRAM pointers only need to be a u8, and WRAM pointers are u16. If we model these regions of memory with BankManagers, we would either need to waste memory for their pointer or we would need to add methods to BankManager that could take a u8 or u16 as pointers. However, this would require the users to track when they should be using which pointer type, but we can enforce this at compile time instead of runtime by modeling each of these regions with their own type and their own pointer type. (It might be helpful to model this with a trait.)

MemoryMap has Option for each external_ram, work_ram_1, work_ram_0, high_ram. Some means that the area will be used in rust-gb. None means that the area will be used by an external dependencies, so it will not be used in rust-gb.

I think this could be helpful, but I have some questions. Let's say HRAM is being managed by some external dependency. Is this dependency something that our users are adding or is this a dependency that we are using in the build process? If it is one of our dependencies, we should try to model this at compile time by just not including it in the memory map.

MemoryMap::new() receives usage areas for each RAM areas. This function is unsafe, and this mean we have to ensure that it is not invaded by the program stack or other tools when using this area.

If we don't model the WRAM (because it is managed by a build dependency), we don't need to worry about this. Also, if we model each memory region with stronger types, we can better ensure safety requirements at compile time.

[zlfn]

Note: After I posted the reply, I was experimenting with this and that and realized that my design wasn't very good. Now I understand why we need your design. And I think that's the best thing.

I have several problems with this. First, we want to avoid runtime checks like having Options at this low level. Having an option would mean that we have to check this every time we try to allocate an object into this region of memory or index into it. This check would have to happen for every BankManager. We know at compile time if the BankManager has None or Some selection address; therefore, we should encode that difference as two different types. If you look at my PR, you will see that I checked the BankManager to be a zero-sized type by using associated constants.

I agree, but then why don't we rename MemoryManager as ExternalRamManager or BankingMemoryManager?
For now, MemoryManager only manages ExternalRAM, so I think that's a more intuitive name.

I think this could be helpful, but I have some questions. Let's say HRAM is being managed by some external dependency. Is this dependency something that our users are adding or is this a dependency that we are using in the build process? If it is one of our dependencies, we should try to model this at compile time by just not including it in the memory map.

I intended the dependency added by the user. I hope users could add their custom ASM/C codes (because there's a limit to what we can do with Rust code). But external ASM/C codes can manipulate HRAM separately from Rust codes and safety.
I planned that memory areas that used by dependencies used in the build process will be excluded from MemoryMap::default().

If we don't model the WRAM (because it is managed by a build dependency), we don't need to worry about this. Also, if we model each memory region with stronger types, we can better ensure safety requirements at compile time.

Honestly, it's still hard to be sure to what extent WorkRam is managed by dependencies and how efficiently dependencies use WorkRam.
I know that stack data is stored in WorkRam1 (banking work ram), but isn't it a waste to give up all areas of WorkRam just because the dependency uses WorkRam? Don't you have any plans to create a way for users to access WorkRam?

And I have one more question. I know Game Boy has multiple MBC types, and unlike WRAM, ERAM is managed by MBC in many ways. How do you plan to handle this?

[zlfn]

https://gbdk-2020.github.io/gbdk-2020/docs/api/docs_rombanking_mbcs.html

It's a little off topic, but it's a task to think about ROM banking not only variables but also functions.

GBDK specifies ROM/RAM banking as separate C files, with far_pointer of a structure similar to BankPtr. (Of course, it is not safe.)
It's not suitable for Rust, but I think it'll be a reference.
Anyway, similar to GBDK, it is necessary to properly specify the ROM and RAM numbers in which each function and variable will be stored and provide an API that can be used safely.
I think what it would be like if it felt like below. (I didn't think about the implementation.)

struct RomBank1 {}
struct RomBank2 {}

struct RomBank {
    bank1: RomBank1,
    bank2: RomBank2,
}

impl RomBank1 {
    fn some_bank1_functions() {}
}

impl RomBank2 {
    fn some_bank2_functions() {}
}

fn main() {
    // some rom_bank providing logics....
    let rom_bank: &mut RomBank = BankManager.get_rom_bank();
    let rom_bank_1: &mut RomBank1 = rom_bank.get_bank_1();
    rom_bank_1.some_bank1_functions();
}

The current toolchain requires multiple asm files to process rom-banking across multiple functions, so we may need to add post-processing logic for compiled C files.

Also, GBDK specify the MBC to be used as a argument in the compilation time. If rust-gb adopts this structure, it will not be easy to check the compilation time bound of ROM/RAM banking number. I think it would be good to model each MBC and provide it as each library. (Or supporting only banking for MBC5 is an easy and appropriate option.)

MORE: GBDK doesn't seem to offer the ability to handle WRAM either. As you said, it might be better not to provide WRAM access.

[TylerBloom]

I agree, but then why don't we rename MemoryManager as ExternalRamManager or BankingMemoryManager?
For now, MemoryManager only manages ExternalRAM, so I think that's a more intuitive name.

Sure. The naming for all of the types could be improved. ExternalRamBankManager is a much better name than my original name.

But external ASM/C codes can manipulate HRAM separately from Rust codes and safety.

This is true and a good point. That said, any external ASM/C codes you might use would be wrapped in an unsafe block. Also, the new function for the memory map is also unsafe. Maybe we could say "we assume you will not allocate this region to external code" will be part of the safety requirements of those blocks. I don't know. Perhaps we can define an ExternalAllocation type to help with this. Let's say you expect some ASM/C to use a region of. You can allocate that region with a type to make the rest of the Rust code respect that allocation without needing to add support for slicing parts of memory.

I think that having user-defined ASM/C code that manages an entire part of the memory map (besides WRAM) will be difficult to design around. It is probably worth doing, but we should give this more thought.

Honestly, it's still hard to be sure to what extent WorkRam is managed by dependencies and how efficiently dependencies use WorkRam.
I know that stack data is stored in WorkRam1 (banking work ram), but isn't it a waste to give up all areas of WorkRam just because the dependency uses WorkRam? Don't you have any plans to create a way for users to access WorkRam?

I also don't know how much our build dependencies will manage WRAM, and we definitely need to keep investigating this. That said, this feels like a premature optimization. I think modelling the rest of the GB's resources should be the focus. After that, we should improve how we model and manage WRAM. You are right that it is probably a waste not to give Rust access to WRAM.

And I have one more question. I know Game Boy has multiple MBC types, and unlike WRAM, ERAM is managed by MBC in many ways. How do you plan to handle this?

This is a really good question. I don't know how we should model this. I don't know how much control we want to give users over this. The crate that we make available could have features that would control what kind of MBC they have. But, how would they define how many ROM and RAM banks they have? I think we could start by assuming they want the max and then optimizing after that.

The current toolchain requires multiple asm files to process rom-banking across multiple functions, so we may need to add post-processing logic for compiled C files.

I have been thinking about this too. I think you're right. We will need to do some kind of post-processing to make sure the correct ROM bank is selected. Luckily, I think we have complete control over this. I don't think users need to worry about it (but we can provide a way for this to control this info if they would like).