Safe ROM banking

[zlfn]

We are discussing about RAM banking and non-linear memory safety in #2
However, Game Boy also has non-linear ROM space, which means we need to do ROM banking to create programs over 32KB.

In GBDK, banking is done using one C file for one bank. But this is not the proper way for Rust, and it is very likely that Undefined Behavior will occur.
Therefore, I suggest the following method of using one struct per one ROM bank.

The underlying structure is similar to the nonlinear RAM banking proposed by @TylerBloom.

---

There are BankProvider trait and RomBankMap, where you can define structs to be banked. In the main() function, you will create only one RomBankMap at the top, similar to MemoryMap.

#[derive(Clone, Copy)]
pub struct Banks<'a> {
    phantom: PhantomData<&'a ()>
}

/// It's a little trick that makes sure the user only creates RomBankMap with Banks.
trait BanksTrait {}
impl BanksTrait for Banks<'_> {}

pub trait BankProvider {
    type Bank1: RomBank = DefaultBank;
    type Bank2: RomBank = DefaultBank;
    type Bank3: RomBank = DefaultBank;
    type Bank4: RomBank = DefaultBank;
    //TODO: bank5 .. bank63
    type Bank64: RomBank = DefaultBank;
}

#[allow(private_bounds)]
pub struct RomBankMap<T: BankProvider + BanksTrait> {
    bank1: T::Bank1,
    bank2: T::Bank2,
    bank3: T::Bank3,
    bank4: T::Bank4,
    // TODO: You might think it's a little weird, but bank5 to bank64 has to be declared in same
    // way.
    // I don't think it's a good code, but I couldn't think of better method.
    bank64: T::Bank64,
}

RomBankMap has 64 types and switch_to_bank functions (depending on the MBC type).

#[allow(private_bounds)]
impl<T: BankProvider + BanksTrait> RomBankMap<T> {
    /// This method should be called at the very start of your program in order to set up all the
    /// datas in ROM that need to be tracked and initialized.
    ///
    /// SAFETY:
    /// If this function is called multiple times, banking may become ambiguous.
    pub unsafe fn new() -> Self {
        RomBankMap {
            bank1: T::Bank1::create_bank(),
            bank2: T::Bank2::create_bank(),
            bank3: T::Bank3::create_bank(),
            bank4: T::Bank4::create_bank(),
            //TODO:  bank 5 .. bank63
            bank64: T::Bank64::create_bank(),
        }
    }

    /// Because this consume its own mutable reference, the bank struct's reference can only 
    /// be accessed one at a time.
    pub fn switch_to_bank1(&mut self) -> &mut T::Bank1 {
        unsafe {switch_rom(1)};
        &mut self.bank1
    }
    pub fn switch_to_bank2(&mut self) -> &mut T::Bank2 {
        unsafe {switch_rom(2)};
        &mut self.bank2
    }
    pub fn switch_to_bank3(&mut self) -> &mut T::Bank3 {
        unsafe {switch_rom(3)};
        &mut self.bank3
    }
    pub fn switch_to_bank4(&mut self) -> &mut T::Bank4 {
        unsafe {switch_rom(4)};
        &mut self.bank4
    }
    //TODO: bank5 .. bank63
    pub fn switch_to_bank64(&mut self) -> &mut T::Bank64 {
        unsafe {switch_rom(64)};
        &mut self.bank64
    }
}

User creates a struct and demonstrates that this struct will be banked by implementing the RomBank trait.

/// All ROM banks need to implement this trait.
pub trait RomBank {
    fn create_bank() -> Self;
}

///// Bank 1 /////
// Bank with no static value
pub struct SomeRomBank {}

impl RomBank for SomeRomBank {
    fn create_bank() -> Self {
        SomeRomBank {}
    }
}

impl SomeRomBank {
    // Each function in RomBank mustn't be inlined.
    #[inline(never)]
    pub fn some_bank1_function(&self) {
        unsafe {delay(100)};
    }
}

The bank constant can be used by importing &'static into the field via RomRef.

///A wrapper to ensure the lifetime of static data within RomBank's lifetime 
pub struct RomRef<'a, T> {
    static_ref: &'a T
}

impl<T> RomRef<'_, T> {
    pub fn new(reference: &'static T) -> Self {
        RomRef { static_ref: reference }
    }

    pub fn fetch(&self) -> &T {
        self.static_ref
    }
}

///// Bank 2 /////
// Bank with some static values
pub struct OtherRomBank<'a> {
    // All field's type of RomBank struct must be `RomRef`
    //
    // We can't force the Rust compiler to check this, but if you don't, you'll get 
    // a C compilation error or banking won't work properly.
    big_data: RomRef<'a, [u8;512]>,
}

// The static value in switching ROM must specify which struct use this value through
// `export_name` macro.
#[export_name="OtherRomBank BIG_DATA"]
static BIG_DATA: [u8;512] = [
    // SOME VERY BIG DATAs
];

impl RomBank for OtherRomBank<'_> {
    fn create_bank() -> Self {
        OtherRomBank { 
            big_data: RomRef::new(&BIG_DATA),
        }
    }
}

Then, you can do safe banking as below.

#[no_mangle]
pub extern fn main() {
    let mut rom_bank: RomBankMap<Banks> = unsafe {RomBankMap::<Banks>::new()};

    // Switch to Bank 1
    let bank1 = rom_bank.switch_to_bank1();
    bank1.some_bank1_function();

    // Switch to Bank 2
    let bank2 = rom_bank.switch_to_bank2();
    bank2.some_bank2_function();
    bank2.other_bank2_function();

    let bank2_ref = bank2.big_data.fetch();
    unsafe {test_function(bank2_ref.as_ptr() as *const u8)};
    
    // Switch to Bank 1
    let bank1: &SomeRomBank = rom_bank.switch_to_bank1();
    bank1.some_bank1_function();

    // This is not invalid because of the lifetime
    // bank2.some_bank2_function();

    // This is not invalid too
    // unsafe {test_function(bank2_ref.as_ptr() as *const u8)};
}

You can check complete prototype in https://github.com/zlfn/rust-gb/tree/rom-banking/source/src
It works, but there is no process yet to parse the C file and divide it into several ROMs, so banking is not actually done.

[TylerBloom]

This idea is interesting, but I'm unsure how well it will work. I can see a few main issues. Each ROM bank has 32 KiB. How does the user know the final size of their function? There are a lot of compiler optimizations that change functions in hard-to-predict ways. Function inlining, for example, will completely erase some functions and put their contents into the calling function. Another problem is generic functions. Through (monomorphization)[https://en.wikipedia.org/wiki/Monomorphization, a copy of a generic function will be created for each type it is called with.

There are parts of this idea that I really like. It seems like if you have several functions that are in the same bank, you don't need to worry about switching between banks if you call them in a row. I think this can be done through post-processing. I think we will need to write a tool to look at the object files, break them apart, organize them into banks, and pass the result to the GB assembler. If we do this, we can even optimize the banks. This would be a lot of work, but I think it is easier than trying to force function locations into the type system.

[TylerBloom]

Thinking about this a bit more. We certainly need to solve this through post-processing. Consider this example:

pub struct Foo(u8);

impl Foo {
  const fn new() -> Self {
    Self(0)
  }
}

pub fn get_foo() -> &'static Foo {
  static FOO: Foo = Foo::new();
  &FOO
}

The reference to FOO is only valid while the ROM bank is loaded. If we can fit all static data into the first (non-switchable) ROM bank, this is completely safe. But, if FOO exists in one of the other banks, we need to track its usage during post-processing. Honestly, this seems like the most difficult problem so far. If you have other ideas on how to solve this, I'm interested in hearing what you think!

[zlfn]

I think it's very hard to find a heuristic algorithm to separate functions and constants into several ROMs as you mentioned.

For example, consider a situation where a very large constant is used in several functions. This "very large constant" must be 1) located in the same ROM as the function that uses it, or 2) used only by the function in the first ROM. If the sum of the sizes of the functions and constants does not fit in one ROM, it can also be divided into two ROMs, consisting of (constant and function set 1) and (constant and function set 2)

In addition, if certain functions run frequently in succession, they should be placed in the same ROM for optimization. Similarly, if (function 1/ function 2) and (function 1/ function 3) are frequently used together, both ROMs may contain function 1.

Considering the calling relationships between functions, it is necessary to set a cost and optimize the separation of each function into different ROMs. I think it's going to resemble an unbounded multiple/multi-objective 0-1 knapsack problem. Maybe we can construct a polynomial-time algorithm, but it will be a really difficult problem.

In contrast, my solution is much easier to implement. All we need to do is simply replace text and separate files based on symbols. All ROM optimization and capacity guarantees are left to the user, so there is no need to create optimization algorithms.

How about implementing my solution first, and then developing an auto-ROM separating algorithm later? ROM banking is a must-have feature, but there is still too much work to do to devote a lot of time to it in the early stages of the project.

[TylerBloom]

I think it's very hard to find a heuristic algorithm to separate functions and constants into several ROMs as you mentioned.

There are applications that implement this. Facebook, for example, has an application BOLT (now maintained by LLVM) that does similar things. We would need to implement one ourselves, but it is certainly possible (though, that it would be a fair amount of work).

How about implementing my solution first, and then developing an auto-ROM separating algorithm later? ROM banking is a must-have feature, but there is still too much work to do to devote a lot of time to it in the early stages of the project.

I like this solution. I don't think having user-optimized/organized ROM banks is a good long-term solution, but implementing a better solution would take significantly longer.