Naked Steel House Invaders
Introduction
Naked steel programming is programming on {hardware} with out an Working System. On this put up, I’ll share a few of the studying I gained after programming a House Invaders-like sport in Rust. The sport can run on a desktop or on Raspberry PI 3B+, and it comes with zero dynamic allocations.
The plan for this put up is as follows: first I’ll briefly clarify how the mission is ready up and the way cargo is used to properly decouple the working system code from the sport code. Then I’ll discuss implementing House Invaders in Rust. It seems that sport growth is sophisticated! Within the final half, I’ll dive into the main points of the fundamental models that have been carried out with the intention to help the sport on a naked steel. I may also discuss methods used to enhance the code velocity and attain an excellent body charge.
After studying this text, I hope you’ll acquire a deeper understanding of writing unsafe Rust, embedded methods, and what it takes to jot down your personal kernel. I don’t assume any prior data of unsafe Rust or working methods implementation, although it will be useful to higher perceive the article. Ultimately, I’ve additionally posted some assets that I’ve collected whereas placing this mission collectively, in addition to some extra assets that might assist you get began on endeavor related initiatives.
I hope this mission can encourage you to writing your personal kernel or naked steel program!
The code for this mission will be discovered on GitHub.
Demo
This sport is operating on a Raspberry Pi 3B+ and linked to my monitor with an HDMI cable:
Targets of this mission
I have been writing an Working System (OS) in rust on the facet for some time now. The issue with it’s that the scope is fairly broad. It is also very exhausting to outline when it is “performed”. Then again, writing a sport on naked steel has important benefits. It has a transparent scope and will be thought of full. This mission began as a facet mission of my working system Iris OS.
The objectives for this mission are:
- Write a sport for Raspberry Pi on naked steel.
- Enhance my data of Working Techniques and embedded programming.
- Improve my understanding of (unsafe) Rust.
As a facet impact, I additionally gained extra data on learn how to write video games. ????
Naked Steel programming
Programming on naked steel includes writing a program that may run with out an working system, instantly on the {hardware}. An OS exposes some APIs (system calls) that packages can use to realize sure duties.
Some examples embody:
- Studying or writing bytes from the disk.
- Getting the time.
- Connecting to an internet site utilizing a socket.
Not having an OS signifies that we have to deal with all the main points of the interplay with the {hardware}.
Firstly, we have to perceive the underlying {hardware} out there and learn how to work together with it. Usually, that is what drivers are for. There are some interfaces that one may question to get details about the underlying {hardware}. On this case, as a result of I am operating this solely on a Raspberry Pi 3 B+, we have already got data in regards to the {hardware}. This considerably simplifies issues.
For instance, I do know that my platform has 4 cores, so both I park 3 out of 4 cores or I might want to implement a method to deal with a number of cores.
A “course of” will be regarded as a unit of labor that will get assigned to any out there core utilizing a course of scheduler technique.
Listed below are extra issues that the OS does for you:
- Implements the “course of” abstraction.
- Manages consumer processes and assigns them to CPUs.
- Manages the out there RAM and allocates reminiscence to every course of.
- Takes care of the interrupts.
- Ensures nobody is eavesdropping in your reminiscence by utilizing digital reminiscence.
All of that is additionally carried out to be as environment friendly as attainable. If the worth produced by a pc will be derived from the time {that a} user-level course of is operating, when kernel code is operating, it is “stealing” helpful time.
In naked steel programming, you do not have all of those good options. It actually depends upon how complicated your program must be. As we will see later, House Invaders was carried out with out many of those options. The primary motive why that is attainable is as a result of we’re operating a single, specialised program.
I imagine naked steel programming is generally utilized in embedded methods.
House invaders
This sport was launched in 1978, manner earlier than my birthdate. It is a enjoyable and difficult sport that was initially developed for arcades. At this level, there are numerous variations, however mine is impressed by the unique one:
As we destroy extra enemies, they begin getting sooner and sooner. Curiously, this was not explicitly coded within the preliminary model of the sport however was a facet impact of getting much less computation to undertake (therefore the sport loop was capable of run sooner).
Whereas programming the sport, Nishikado found that the processor was capable of render every body of the alien’s animation graphics sooner when there have been fewer aliens on the display. Because the alien’s positions up to date after every body, this brought on the aliens to maneuver throughout the display at an rising velocity as increasingly have been destroyed. Slightly than design a compensation for the velocity enhance, he determined that it was a function, not a bug, and stored it as a difficult gameplay mechanism.
Wikipedia
This twist made the sport extra enjoyable and difficult!
Undertaking construction
When implementing one thing with out an underlying working system, you aren’t allowed to make use of the rust’s commonplace library. This is because of the truth that the usual library makes use of system calls. System calls are API supplied by the Working System. No OS, no system calls no commonplace library. When writing a rust program, we are able to choose out from utilizing the usual library by utilizing a #[no_std] macro.
When going no_std, you can’t even use the rust’s testing framework, which will be annoying. Additionally, testing our sport on {hardware} on each iteration may be very time-consuming. The trail I made a decision to comply with is to implement the mission in two crates:
- house invaders crate: implements house invaders. It’s added as a dependency to the kernel crate which runs it within the kernel’s fundamental() operate.
- the kernel crate: a binary that will get compiled and might run on the Raspberry pi.
This division permits implementing every crate independently. Should you carried out your personal kernel, (I hope) it shouldn’t be a giant effort to run House Invaders crate on high of it.
House Invaders crate comes with std and no_std function flags.
The House invaders crate has two options: no_std and std. With std enabled, I’ve pulled in a dependency that provides you a window with a framebuffer, and was capable of “very” rapidly construct the sport. After I used to be happy with the sport, I began implementing the kernel half. Doing issues high down has its profit as we will see later.
House Invaders implementation
I take pleasure in enjoying video games every so often, however have not spent a lot time constructing one. Normally when constructing a brand new mission, I like having one thing that works and progressively broaden it and add new use circumstances (see Gall’s legislation). That is nonetheless doable in sport dev, I imagine, nevertheless it’s very time-consuming. I’ve typically discovered myself sprinkling magic numbers right here and there to make the whole lot work appropriately. I am not saying that it isn’t attainable, nevertheless it’s relatively time-consuming. Particularly as a result of as I used to be testing the sport, I discovered increasingly use circumstances and edge circumstances.
Sport dev
The essential framework for sport growth is to have for loop, also called “the sport loop”; that does two issues:
- run some “enterprise” logic to calculate the following state.
- draw the most recent out there body to the framebuffer.
I want to briefly discuss an vital idea strictly associated to the sport loop that I needed to struggle with very quickly.
Let’s assume that we run this large loop 30 instances in a second, and we wished to see our enemy transfer 4 pixels per second. Then we may simply add 1 pixel each time the loop is run. However what if the loop takes lower than 1/4 of a second to run? As we kill enemies, we have to do much less work; therefore the loop will run sooner. This might make our enemies transfer sooner than 4 pixels in a second! Humorous sufficient, this was additionally the unique story behind the truth that within the unique sport, as you killed enemies, they began transferring sooner.
But when we wish to maintain the ratio fixed, we have to use the delta milliseconds.
What’s delta time
Any time we run the loop, we calculate how a lot time has handed between now and the earlier loop. We want then to make use of this info to calculate how a lot distance the enemy has traveled. It isn’t exhausting to know in case you do not forget that
distance (pixels) = velocity (pixels/milliseconds) * time handed (milliseconds)
This poses a small challenge as a result of pixels are discrete. Therefore, we have to retailer the coordinates as a f64, however any time we want the actor’s coordinates, we have to solid this quantity to an u32.
Additionally, the enterprise logic can run “as quick as attainable” whereas the drawing half ought to run at a sure charge restricted velocity, say 30 instances per second (FPS).
So the whole lot is continually in motion, and infrequently we draw a constant scene to a body.
Actor
An actor is something that must be drawn to the display and holds some frequent strategies for frequent transformations. It must be known as in at the least two moments, one throughout enterprise logic replace and the second throughout draw.
To attract the barricade, I’ve manually written the indexes and used rustfmt::skip to see what it appears to be like like:
#[rustfmt::skip]
const OFFSETS: [(f64, f64); TOTAL_BLOCKS_PER_BARRICADE] = [
(1.0, 0.0), (2.0, 0.0), (3.0, 0.0), (4.0, 0.0),
(0.0, 1.0), (1.0, 1.0), (2.0, 1.0), (3.0, 1.0), (4.0, 1.0), (5.0, 1.0),
(0.0, 2.0), (1.0, 2.0), (4.0, 2.0), (5.0, 2.0),
];
I hope you may see the “sprite” of the barricade!
every of those coordinates will get translated to a single block that may be shot away.
FrameBuffer and Double Buffering
I used to be capable of finding a pleasant and easy implementation in rust known as “minifb” that provides you entry to a framebuffer inside a window, plus some strategies to get the consumer’s enter. This was tremendous helpful when growing in std!
The framebuffer itself is only a large array during which every coordinate [x][y] maps to a pixel within the interface. A pixel is represented as an RGBA utilizing 4 bytes or an u32.
Within the sport loop, after we calculated the following state and we wish to draw it out, it’d take a while to render. As an example we’re attempting to attract the motion of the shoot from a hero. We might want to set a pixel to white, and the earlier pixel to black. This isn’t atomic, and in between these two operations, the consumer will see that the shot is 2 pixels lengthy for a really brief time period.
What we are able to do about that is to make use of the double buffering method. Now we have the framebuffer as “entrance” buffer and a second “again” buffer. The second buffer is the following body. After we draw the whole lot in there, we are able to simply exchange the again buffer with the second buffer. If the system you are utilizing helps it, it is perhaps adequate to simply swap the 2 pointers to attract the brand new interface. On this case, I have not checked, so I simply reset the entrance buffer (setting the whole lot to zero) and replica the again buffer to it. Spoiler: this needed to be improved on the raspberry facet. Extra on this within the efficiency part.
QA
Even when a operate respects some expectations, the ultimate sport may nonetheless be damaged in some humorous manner. And each time I made a change, I used to be attempting to do some QA. These are some conduct that I used to be testing:
-
When the sport begins, the hero’s ship is positioned on the heart of the display, and aliens begin on the left, transferring to the correct.
-
If any alien reaches the underside of the display, the sport is over.
-
When the hero shoots a shot, it strikes upward till it hits an enemy or goes off the display.
-
When an enemy is hit, each the enemy and the shot disappear.
-
If a shot is fired by an enemy, it will possibly solely hit the hero.
-
When all enemies are defeated, the sport is over.
-
After a column of enemies is defeated, the remaining enemies can transfer one column additional.
-
As soon as the sport is over, it resets to the place to begin.
-
The hero mustn’t surpass the facet of the display.
-
Periodically, an enemy might shoot a shot.
-
Each time an alien is shot, the excessive rating will increase.
-
If the participant wins, the sport resets, and the rating is tracked.
-
Barricades are added in entrance of the hero.
-
Each time an alien is killed, the remainder velocity up by 2%
and so forth! I discovered this train very helpful to make sure the standard of the ultimate sport, although I ought to have performed extra with the unique sport to make my model nearer to it. Subsequently, that is my private taste of House Invaders!
To allocate or to not allocate
When we have to make use of the RAM, our program has two methods: allocate on the heap or on the stack.
Each are their benefits and downsides. In garbage-collected languages, you do not spend a lot time to consider this.
All of the reminiscence that we wish to allocate on the stack have to be identified at compile time. For instance, we already know what number of enemies we wish to draw on the display, so we are able to retailer them on the stack. However this array is mounted: as enemies get destroyed, we can’t shrink our array. Therefore, if we use a stack allotted construction, we would wish to traverse via it absolutely, no matter how lots of the enemies are alive.
It is very important know that whereas stack is taken care by your compiler, the heap allocator (or dynamic reminiscence allocator) needs to be carried out. When compiling a std program, rust already gives its personal reminiscence allocator, however we’re free to implement our personal for particular use circumstances (squeeze efficiency, discover reminiscence leaks, and many others.).
This sport and kernel use solely static stack allocations. There aren’t any heap allotted structs like String, Vecs, and so forth. This not solely helps with efficiency, nevertheless it allowed me to get away with out implementing an allocator. Extra on this in a second.
Kernel Implementation
Earlier than beginning, we have to perceive which options we might want to implement so as to have the ability to run house invaders.
Initially, we do not want a consumer house. The sport can safely run in kernel stage. If we had the sport operating in consumer house, we’d mainly be implementing unikernels.
We do not want consumer house as a result of we’re operating solely a single “factor”. Consumer house provides you isolation, security, portability and extra. In consumer mode, totally different processes cannot see one another’s reminiscence. Should you run the whole lot in kernel mode, the whole lot can learn and write the whole lot, which isn’t ultimate in case you’re planning to run some untrusted code. That is additionally the explanation why kernel modules can crash your system and eBPF is so cool!
With the intention to get a framebuffer, we have to discuss to raspberry pi’s GPU. To take action, there’s a cool interface known as mailbox. We have to implement a driver to make use of it to ship messages and obtain responses. The Raspberry’s GPU is a closed supply, however it’s mainly operating its personal working system. When the kernel boots up, it is begin operating the instruction at deal with 0x80_000. That is after the GPU has accomplished its personal initialization.
For the stack, we are able to use 0x80_000 as a stack pointer, and the stack will continue to grow downwards.
We additionally want a driver to make use of the UART. UART is only a serial interface that enables to switch information. Raspberry comes with a mini uart and a full-blown pl011 appropriate uart. We’ll use the latter. The serial interface is used as “commonplace output” for our prints and to take the enter from the consumer.
Lastly, we have to implement a small interface to get the readings from the timer.
To recap:
- mailbox for the framebuffer
- uart: keyboard enter and prints output
- timer: to get the delta time
Probably, I may add some apcpi help to permit the shutdown of the system, however the concept is that as quickly because the system boots up it’s going to run house invaders in an infinite loop.
Logging
Contained in the house invaders crate, I wanted to do some println!() requires debugging causes. It is at all times good to know that one thing is going on. println!() is a macro which will get changed with a std name. It’s in actual fact not out there in no-std. Contained in the kernel code, I already had a println! Macro that will write to the serial port. So ideally, my house invaders lib would have println! Calls, and would let the consumer of the library determine which implementation to make use of: std in case I wished to run it on my laptop computer or my kernel’s in case I wished to run it on raspberry pi.
After scratching my head for a second, I spotted that that is precisely what the rust’s log library is doing! Fortunately, implementing a logger is sort of straightforward. The one caveat is that I had to make use of “log::set_logger_racy(self`) to make it work. I’ve not but investigated what’s up with that, however after studying the Security necessities, this needs to be a secure utilization. The logging occurs utilizing the UART serial. The UART will get initialized as soon as firstly of this system, after which it may be used to ship and obtain bytes.
Allocator
An allocator will be created by implementing the GlobalAllocator trait which comes with two capabilities:
unsafe fn alloc(&self, structure: Structure) -> *mut u8;
unsafe fn dealloc(&self, ptr: *mut u8, structure: Structure);
Within the preliminary part, I carried out a bump allocator which operates in keeping with the next algorithm: A pointer to the present head of the heap reminiscence is maintained. Upon invoking the ‘alloc’ operate, the top is shifted to ‘structure.measurement’, and the earlier pointer is returned. Then again, when the ‘dealloc’ operate is named, no motion is taken, leading to a technical reminiscence leak.
You is perhaps considering that we are going to run out of reminiscence sooner or later, and you’d be completely appropriate! Bump allocators work properly so long as you have already got details about the quantity of reminiscence you may have to allocate. In real-life situations, bump allocators have their very own place as extremely environment friendly allocation mechanisms. In case your want revolves round swift execution with minimal extra duties and you’re conscious of the precise reminiscence necessities, choosing a bump allocator is perhaps an appropriate determination.
To make use of a dynamic allocator In Rust, we are able to apply the #[global_allocator] macro to a static object that implements the World Allocator trait.
This permits us to utilize the contents of the alloc crate, similar to Vec, String, and others!
I wasn’t actually performing any allocations within the sport; nonetheless, ultimately, I nonetheless wanted an allocator to align the sprite photos to an u32 to stop encountering Undefined Conduct.
The sprites are encoded as RGBA, so utilizing u32 will not be solely extra easy but additionally a lot sooner. To get an RGBA bitmap out of a picture, it was adequate to open it with GIMP and export/save as “information” file leaving all of the default choices.
Having a linker script, I thought of attempting to align the sprites to u32 there. Nonetheless, this method leaves the potential for std to stay misaligned. Luckily, I stumbled upon this good macro that extends the performance include_bytes!(), and enabled me to remove all of the remaining allocations. I made a couple of changes to acquire a &[u32]:
#[macro_use]
mod macros {
#[repr(C)] // assure 'bytes' comes after '_align'
pub struct AlignedAs<Align, Bytes: ?Sized> {
pub _align: [Align; 0],
pub bytes: Bytes,
}
#[macro_export]
macro_rules! include_bytes_align_as {
($align_ty:ty, $path:literal) => {{
// const block expression to encapsulate the static
use $crate::macros::AlignedAs;
// this task is made attainable by CoerceUnsized
static ALIGNED: &AlignedAs<$align_ty, [u8]> = &AlignedAs {
_align: [],
bytes: *include_bytes!($path),
};
let as_u8 = &ALIGNED.bytes;
// security: the alignment is assured by the above const block expression
unsafe { core::slice::from_raw_parts(as_u8.as_ptr().solid::<u32>(), as_u8.len() / 4) }
}};
}
}
// utilization:
pub static ENEMY_SPRITE: &[u32] =
crate::include_bytes_align_as!(u32, "../../../belongings/alien.information");
I may have additionally gone with a [u8] and written them in units of 4, however this method is way more handy and affords higher efficiency!
At this level, so far as I used to be involved, an allocator was not wanted anymore.
One side that proved relatively bothersome is that in case you try and take away the World Allocator, and if there’s a component like a crate or a format!() operate that depends on alloc, the Rust compiler will elevate an error relating to the absent allocator, nevertheless it will not let you know why one is important. If the alloc pinpointing the precise dependency can grow to be fairly vexing. One potential decision when alloc is hid inside your dependencies is to retrieve all of them and conduct a seek for “alloc”. Normally when a crate must the alloc create, it is normally properly marketed of their README. On this case, a format!() used to jot down the rating string was forcing me to maintain the allocator round.
To pinpoint the alloc utilization, I attempted valgrind’s dhat device. It is fairly neat, although on this case it didn’t instantly level out the problem. After putting in the dependencies I run it like this valgrind --tool=dhat goal/debug/space_invaders; this generates a dhat.out.strdup operate, which was a adequate trace for me. This book section has extra data on this device. This can be a pattern for single hint:
Pricey GPU, I hope this Request finds you properly.
The mailbox interface is generally undocumented {hardware}. Fortunately, the property interface is outlined and comes with numerous goodies, and some of them I wanted to make use of.
It really works like this: the mailbox is memory-mapped, and amongst others, it has 3 registers that curiosity us – write, learn, and standing.
First, you create a buffer with some format described on the wiki web page. After checking utilizing the standing register that the mailbox will not be full, we are able to write the deal with to our request struct within the write register.
When the GPU has accomplished the response, the learn register will include our request’s deal with, and the standing register will change to not empty. However now the struct will include the GPU’s response, not our request anymore.
The format of the request appears to be like like this:
u32: complete buffer measurement in bytes.u32: needs to be 0x0 for requests.- [all our tags]
u32: all0x0– the tip tagu8: extra padding wanted to align to u32.
That is just a few conference we have to comply with when writing tags. Tags are the precise requests for service we’re asking the GPU.
It took me some trial and error to get a few of these messages proper. I’ve solely added capabilities so as to add particular providers I wanted, crucial being the framebuffer.
Timer
Raspberry Pi 3B+’s BCM2837 ARM CPU comes with two timers: one is the Arm Timer, and the opposite is particular to this CPU (Broadcom). These timers begin ticking once we join the facility. For a full working system, timers are very important to implement preemptive scheduling. Earlier than switching to userspace, the kernel will register an interrupt that may tick in a set period of time (known as quanta). When dealing with the interrupt, the kernel will permit the scheduler to run and determine which unit of labor to allocate subsequent on this CPU. In my case, I haven’t got the idea of a “course of” or “thread” however I nonetheless want a timer to calculate the delta milliseconds.
The specification on learn how to use this timer is described within the doc known as “BCM2837 ARM Peripherals,” chapter 12, web page 172. It makes use of memory-mapped IO. The vital registers are two u32 that collectively give us the microseconds since boot.
As a result of this includes a read_volatile and a few shifts to get the u64 proper, this operation is sort of environment friendly.
Random
At this level, you is perhaps questioning why I didn’t point out the motive force to implement random, used, for instance, to determine when our enemies needs to be capturing.
One may, for instance, determine to implement a pseudorandom quantity generator, however even for that, I’d nonetheless want a “random” seeding quantity.
Raspberry does include an RNG generator. However I’ve determined to get away with implementing it by merely having a set array of 10 numbers with some random values. In every iteration, we choose the following quantity and select an alive enemy from the checklist of alive enemies. That is chosen to shoot within the subsequent loop.
Why 10? It appeared sufficient.
Why not implement a driver for random? I do have this driver already carried out for my OS. However I’ve determined to not do it to maintain the sport quick and the general code easy.
The RNG requires entropy, so each time we ask for a random quantity, we have to look ahead to some entropy. So ideally, I ought to have most likely additionally included an implementation for an RNG. I’ve written an implementation for the well-known MT19937 RNG here, however once more, I did wish to maintain the code as small as attainable. Let me know if the random does not really feel sufficient random! And here is the compulsory xkcd:
UART
The UART (Common Asynchronous Receiver/Transmitter) is a chip that handles the serial port communication. The motive force was taken from the superb rust-embedded tutorial. The specification will be discovered on the doc “PrimeCell UART (PL011) Technical Reference Handbook” r1p5.
Booting up
When the Raspberry is powered up, the GPU begins and initializes the whole lot. When it is prepared, the CPU will begin executing the instruction at deal with 0x80_000. The preliminary boot script is written in meeting in boot.rs. Raspberry has 4 cores. As a result of it is a Symmetric Multiprocessor, all cores begin operating the instruction saved at deal with 0x80_000. For the sport, I solely wanted one core. There’s a particular instruction known as “mrs” to learn the coprocessor information. I’ve used it to get the present core ID, and to park 3 out of 4 cores.
The “bss” (block began by image) part of reminiscence is used for static variables that aren’t initialized with any worth and is meant to be zeroed out. The usual conference is that the working system or runtime initializes this reminiscence to zero earlier than this system begins executing.
Should you have been to depend on variables within the bss part being initialized to particular non-zero values, it may result in undefined conduct as a result of these variables may include arbitrary information. This will result in unpredictable leads to your program. Zeroing out the bss part helps be certain that this system behaves constantly.
The reminiscence will be allotted on the stack or on the heap. Normally the heap grows from decrease numbers to increased numbers, and the stack is the alternative. As a result of our code begins at 0x80_0000, we are able to use this deal with for the stack pointer register. The Stack will continue to grow to 0.
Aside from zeroing out the bss, the meeting can be organising the stack pointer. And this is sufficient to change over to the rust code. [mod.rs](http://mod.rs) has a _start_rust operate that is named from the meeting. This is the reason we want the prefix:
#[no_mangle]
pub unsafe extern "C" _start_rust()
#[no_mangle] is required to stop the compiler from mangling the capabilities names. It normally does it to get a novel title for every operate within the code base. extern "C" is required to permit rust code to be known as from the meeting. Verify the rust embedded book for more information.
At this level, it is going to change exception stage.
Should you’re acquainted with x86’s ring, there is a related idea in ARM known as exception stage. Exception ranges are used to implement separation between kernel and consumer house. The degrees are:
- 0 = consumer,
- 1 = kernel,
- 2 = hypervisor – the preliminary stage
- 3 = Safe monitor (normally unused)
On this code, I change to kernel stage for a selected motive that I’ll talk about in a bit (spoiler: enabling mmu).
In case you are questioning why it is known as “exception stage” properly, it is as a result of it is largely associated to “exceptions” also called interrupts. When one thing unhealthy within the present stage (say, consumer stage) occurs, the management of the system is handed to the upper exception stage (kernel stage). To modify again to the decrease stage, we have to “return” from the exception. That is performed utilizing the “eret” meeting operate. That is additionally what we have to do to go from stage 2 to stage 1. We load the registers with information that we count on there and the final name from this operate is arm::eret();.
After the setup is accomplished, we are able to begin initializing our drivers. To get output we want the UART so it isn’t a shock that it will get initialized first proper earlier than the logger. As defined later, for efficiency causes, I used the mailbox to get the cpu’s max clock charge and ship one other request to replace the present clock charge to that worth.
The primary is named, however this crate has #[no_std] and #[no_main]: this operate is simply arbitrarily chosen. The kernel stage initialization is accomplished, now we are able to request a framebuffer utilizing the mailbox and begin the sport. ????
Make it work, make it proper, make it quick!
Apart from my intentional effort to keep away from utilizing the heap, I have not put in a lot effort to make the sport extra environment friendly. Curiously, it ran fairly easily on my laptop computer (capped to 30fps). Nonetheless, once I ran it on my Raspberry Pi for the primary time, the sport loop took 300ms to finish! My objective was to realize 15 frames per second, which might imply round 66ms per body. 15 fps or 1000/15 = 66ms.
Right here are some things that I attempted, a few of them helped a few of them appeared ineffective although intuitively sound (to me). Ultimately, the loop was operating in about 22ms at which level I’ve stopped profiling.
Step one was to know what was taking time. To profile the code, I’ve added prints with time from the start of the loop to that time. Clearly, more often than not was spent within the clear and drawing part.
Direct Reminiscence Entry (DMA)
I’ve additionally thought of implementing help for DMA with the intention to effectively switch the again buffer to the entrance buffer.
DMA would seemingly have been useful on this situation (though I will by no means know for certain), nevertheless it truthfully felt like a little bit of a chance. I tried to seek out pattern implementations, and so they did not seem overly complicated, aside from involving quite a few registers and choices. The dilemma I confronted was that investing time into implementing DMA, solely for the aim of getting a duplicate buffer operate, may find yourself being wasted effort if the development did not match my excessive expectations.
Moreover, DMA tends to shine when used asynchronously. Since I hadn’t carried out interrupts into my system, integrating code to handle the asynchronous side or choosing a synchronous implementation (much like what I did with the mailbox) would have been needed. Nonetheless, I nonetheless wasn’t solely sure that DMA would supply the specified advantages on this context. Because of this, I explored another possibility.
Double Buffering, however quick!
My double buffering was high-quality on the desktop, however on the raspberry copy this big array may be very gradual!
The Raspberry Pi’s framebuffer helps an optimization known as “panning.” On this method, we request a framebuffer with double the peak of the bodily display. The presently undisplayed portion of the display serves because the again buffer. After the drawing is completed on this again buffer, we are able to use a mailbox request to tell the GPU to “pan” to the offscreen a part of the buffer by altering the “digital framebuffer peak offset.” This intelligent method eliminates the necessity for a resource-intensive copy operation!
Single Instruction A number of Knowledge
SIMD (Single Instruction, A number of Knowledge) contains particular directions that the compiler can make the most of to reinforce code’s effectivity. These directions operate by executing a single instruction throughout a number of information parts. As an example, if we possess a vector or a considerable array requiring every component to be incremented by 4, using SIMD would allow this job to be achieved with only a single instruction, assuming the CPU helps such capabilities.
My concept was to make use of a SIMD to enhance the effectivity of the buffer reset.
Raspberry Pi comes with the Nitro extension, which is basically SIMD for the Arm structure. Nonetheless, I wasn’t ready to make use of it successfully. The reset operation needed to be risky, resulting in display flickering. That is my assumption, and I have not delved additional to discover learn how to use these capabilities extra successfully.
This can be a very good put up in case you’re interested in SIMD: https://thinkingeek.com/2021/08/22/raspberry-vectors-part-9/ and the specs will be discovered right here https://developer.arm.com/documentation/den0018/a/.
Ultimately, I wasn’t capable of optimize this reset which presently appears to be like like this:
let slice_ptr = (&mut self.raw_buffer()).as_mut_ptr();
for i in 0..self.single_screen_len() {
unsafe {
core::ptr::write_volatile(slice_ptr.add(i), 0);
}
}
Seems there’s extra hanging fruit, and this operation is already environment friendly sufficient.
Knowledge and Instruction cache strains
Switching to kernel mode is especially needed as a result of it permits enabling the Reminiscence Administration Unit (MMU) which is required to allow the info and instruction caches.
Because of the cortex_a crate, enabling the MMU is so simple as SCTLR_EL1.modify(SCTLR_EL1::C::Cacheable + SCTLR_EL1::I::Cacheable);.
The efficiency enchancment ensuing from including caching, as anticipated, was fairly important.
Within the present state of the system (at commit d168b9), the everyday time taken per loop cycle is round 33 ms. If I have been to disable these caches, that point would enhance to 76 ms per loop.
Overclocking
At Raspberry Pi’s startup, it begins with a restricted clock charge. This enchancment is sort of easy and requires simply a few mailbox messages:
- Fetch the utmost clock charge.
- Set the specified clock charge.
And that is all it takes!
Within the present (“ultimate”) system state, if I run the sport with out overclocking, it will possibly nonetheless deal with a cycle in round 33 ms. So, maybe on this scenario, it may not be a revolutionary change.
Inlining performed fallacious and learn how to do it proper
In your favourite compiled programming language, whenever you wish to name a operate, the compiler will break it down into varied directions/steps to be adopted:
- Write the operate’s arguments to the stack.
- Write the worth of the PROCESS COUNTER plus 1 to the stack.
- Jumps to the operate’s location.
- Run the operate’s code.
- when the operate is accomplished, execute “ret” operate to pop the final stack body and set the PC to the situation on the stack.
This mechanism introduces some overhead.
Another choice is to “inline” the operate. As an alternative of leaping to that location, the compiler can determine to repeat the operate’s directions and place them instantly within the spot of the operate name. This manner, you are successfully “operating” the operate’s directions however avoiding the overhead of leaping round. Fairly fascinating!
Every operate name is substituted with the precise code of the operate. Subsequently, in case you’re solely calling that operate in a single location, there’s nonetheless just one occasion of those directions. Nonetheless, if the operate is named from quite a few totally different locations, this leads to duplicated directions. This duplication can result in a rise in each the dimensions of your compiled binary and the compilation time.
Throughout a selected part of the sport’s growth, I wished to check it on a Raspberry Pi. As you may recall, the loop took roughly 300ms to execute, making the sport unplayable. To deal with this, I started so as to add the ‘inline’ attribute to capabilities that, in my opinion, have been essential to the hot-path. I instantly seen an enchancment within the delta time.
After I was doing the ultimate optimizations, I actually wanted to discover a strategy to go from 114 ms or 8 fps (very laggy sport) to one thing round 66 ms or 15 fps (an “okay” sport).
I first began by eradicating all inlines. The sport was operating very slowly. Then I began including them again one after the other, operating the sport after every change and seeing how the delta was doing. If there was no enchancment, I merely eliminated it. It seems that only a few locations have been truly serving to. Should you grep the code, you may see there are only a few locations which might be inlined.
I used to be fairly stunned when, after introducing ‘inline’ to sure capabilities, the loop time truly elevated by a major quantity. My assumption is that this may very well be attributed to department mispredictions. This understanding performed an important position in decreasing the loop’s length to roughly 72ms from the sooner 114ms.
It’s true: make it work, make it proper, make it quick. “Make it quick” is final as a result of it is (normally) exhausting to foretell which code will should be optimized.
Abstractions are cool once they’re free
I added some abstractions right here and there to make the code extra readable. Considered one of them was a Pixel, outlined as coordinates and shade. By eradicating this abstraction and limiting the usage of the Coordinates struct, the ultimate loop went from 72 ms all the way down to one thing like 33 ms. I’ve additionally reworked some for loops to be extra cache pleasant to get it all the way down to 26 ms per loop time.
On this case, the abstraction was solely including overhead when copying the info round, due to this fact, eliminating it was the correct name.
Operating the mission
Some ultimate notes on learn how to run this factor.
Desktop
After testing the repo, you may simply open a terminal and use:
cargo run --package space_invaders --bin space_invaders --features std
to run house invaders in your desktop. Linux, Mac and Home windows are supported.
{Hardware}
If you wish to run on a Raspberry PI, then you will want:
- A Raspberry PI 3B+. Newer fashions may work after small tweaks
- An HDMI cable and monitor.
- A USB Serial Output linked to your Raspberry Pi and inserted in your laptop computer.
To run it on the {hardware}, I have been utilizing the good instruments carried out in https://github.com/rust-embedded/rust-raspberrypi-OS-tutorials. The deal-breaker for me is the chainboot. Chain booting is basically chain loading:
Chain loading is a technique utilized by pc packages to interchange the presently executing program with a brand new program, utilizing a standard information space to go info from the present program to the brand new program. It happens in a number of areas of computing.
So as a substitute of constructing the kernel, mount the filesystem, copy the kernel there and powerup the system, utilizing chainbooting there’s a minimal kernel that may:
- learn from uart
- write the whole lot from enter to a selected location (0x80_000, the beginning of the kernel)
- soar on the primary kernel instruction.
This considerably cuts down time from constructing the kernel to operating it on {hardware}.
Briefly:
- set up Raspberry Pi OS (ex Raspbian) to an sd card.
- Obtain the repository.
- Exchange kernel8.img within the sd with the one supplied within the belongings folder (belongings/kernel8-chainboot.img) within the repo.
- Join the usb serial output to Raspberry pi just like the picture beneath. Join the HDMI as properly.
- Run
make chainboot. - Join the usb to your laptop computer and wait. After the switch is accomplished, the display will begin exhibiting house invaders!
QEMU
I have not tried to run this mission on QEMU. Though the make qemu command is on the market, organising the show would require some extra configuration. I selected to not give attention to making it work there as a result of my earlier experiences have proven that QEMU’s emulation of the Raspberry Pi might not at all times be solely correct. As in, even when the mission runs properly on QEMU, it may not carry out as anticipated on the precise {hardware}.
Conclusions
Nicely, this has been enjoyable! This mission is a facet mission out of an working system I have been writing on the facet for some time. As a part of that, I’ve additionally written and launched a vfat driver. On this mission, I’ve carried out a House Invaders on naked steel in Rust. The mission consists of the sport and the kernel in two totally different crates. The sport will be run on a desktop utilizing the std function flag. There aren’t any dynamic allocations, and all options that have been used at kernel stage to help the sport have been the mailbox driver for getting a framebuffer from the GPU, a UART driver to get serial enter and output and the timer driver to calculate the passage of time.
After rapidly prototyping the sport in std, I proceeded to implement the kernel facet. Since I hadn’t designed it with efficiency in thoughts, the sport was operating very slowly, due to this fact, I began exploring methods to reinforce the sport’s velocity. Implementing strategies like double buffering with panning, caching, inlining, and minimizing overhead considerably improved total efficiency. Consequently, the sport can now obtain a excessive frames per second (fps) charge, though it is using only a single CPU core.
I used to be capable of attain the objectives that I initially set for myself:
- Write a sport for Raspberry Pi on naked steel, with out utilizing any working system.
- Enhance my data in Working Techniques and embedded programming.
- Improve my understanding of (unsafe) Rust.
- and eventually, as a facet impact, study extra about learn how to write video games.
I have been fascinated about studying WebAssembly for some time, so perhaps for someday sooner or later, I want to attempt to port this sport there. One other concept I had thought of however deferred for the longer term was so as to add an “on-line” international excessive rating. On the finish of the sport, customers can submit their scores to a backend. This might require including some “display” navigation on the sport and an ethernet driver + tcp/ip stack on the kernel.
Should you made it up to now, I would love to thanks! When you’ve got questions or feedback, please attain out on Twitter, Mastodon and even by way of e mail. See you subsequent time!
Acknowledgments
This mission makes use of instruments and data from Andre Richter‘s wonderful tutorial https://github.com/rust-embedded/rust-raspberrypi-OS-tutorials. Within the rust group we’re fortunate to have numerous cool OS initiatives, so lately it’s tremendous straightforward to get your palms soiled with OS growth. The motive force for the UART, make file and minipush have been taken from the above repository.