Thursday, 22 October 2020

Proposal to add build graph output to GNU Make

Background

In 2015 I worked as a consultant at a large company in Lund. My position was with the build team and one of our responsibilities was managing and maintaining the build system for their Android based phones.

The problem I was tasked with solving was the fact that running 'make' for a product after a successful build resulted in a lot of stuff being rebuilt unnecessarily.

A stock Android build tree behaved nicely: a second run of 'make' only produced a line about everything being up-to-date. But the company products were taking a good 15 minutes for a rebuild even if nothing had been changed.

The Android build system works by including all recipes to be built (programs / libraries / etc) using the GNU Make include directive, so that you end up with one giant Makefile that holds all rules for building the platform. Possibly to avoid the problems laid out in the paper Recursive make considered harmful.

As you can imagine this results in quite a large Makefile that is near impossible to debug. To help us out GNU Make has an option that helps you figure out what is going on with every decision it makes:

-p, --print-data-base       Print make's internal database.

This is very powerful and lets you investigate a lot about what Make is doing. It may be a bit too powerful though. It is a lot of information to digest. You can see example output from when I run it against the project from my last blog  post, riscv-asm-hello-morse in a gist here.

The bugs we found and the fixes we implemented were mostly about targets depending on non-existing files or depending on phony targets. The fixes were almost never the hard part, it was finding the bugs that was hard.

Lately I have been working a bit with the Yocto build system which uses Bitbake to build recipes. And Bitbake has a -g option to generate a dependency graph that lets you figure out why something was built.

I wondered if something similar could be made useful for GNU Make. So I attempted to implement it as:

  -g, --output-graph          Output (dot) graph of modified targets for each goal.

Here I might need to pause to inject that I am not the first person to have this idea:


And I am sure I am missing more submissions.

In my defense my approach is a bit different. I only want to include targets that have been updated from Make goals that have changed, which will trim the graph quite a bit. It is not an attempt to show the information from --print-database in a new way.

Example 1

If I use my proposal to generate a graph from the riscv project mentioned above:

$ make -g
riscv64-unknown-elf-as -march=rv32imac -mabi=ilp32 -g -o0  -c -o hello-morse.o hello-morse.S
riscv64-unknown-elf-as -march=rv32imac -mabi=ilp32 -g -o0  -c -o wait.o wait.S
riscv64-unknown-elf-as -march=rv32imac -mabi=ilp32 -g -o0  -c -o led.o led.S
riscv64-unknown-elf-as -march=rv32imac -mabi=ilp32 -g -o0  -c -o morse.o morse.S
riscv64-unknown-elf-ld hello-morse.o wait.o led.o morse.o -m elf32lriscv -nostartfiles -nostdlib -Thello-morse.lds -o hello-morse.elf
riscv64-unknown-elf-objcopy -O ihex hello-morse.elf hello-morse.hex
make: Writing dependency graph to '/home/jonas/sandbox/riscv/riscv-asm-hello-morse/all.dot'
The last line here (my bold) is new and added by my patch. If we now look at the graph generated by this build.
$ cat all.dot
strict digraph "all" {
  "hello-morse.elf" -> "hello-morse.o" 
  "hello-morse.elf" -> "wait.o" 
  "hello-morse.elf" -> "led.o" 
  "hello-morse.elf" -> "morse.o" 
  "hello-morse.hex" -> "hello-morse.elf" 
  "all" -> "hello-morse.hex" 
  "all"
}

And we can generate a PNG from it:

$ dot -Tpng all.dot -o all.png


And if I force a rebuild  and re-generate the PNG:

$ touch morse.S
$ make -g 



Example 2

In my last blog post I mentioned the freedom-e-sdk used to build software for the hifive1-revb board. I noticed that it had the same problem as the Android based build system above, it always rebuilt on a second 'make' run.

The graph for the second run looks like:



Which helps us see that the build is forced because Make cannot find the libmetal-pico.a file. And looking at the Makefile we find that, yes, it does not check if the bsp support picolibc before depending on libmetal-pico.a. Fixing that will make rebuilding on the second 'make' run go away.

Example 3

If I want to track what happens on rebuild of the Make project itself I run into an issue.
$ touch src/file.c
$ make -g
The resulting all.dot file hardly contains any information about the rebuild:
strict digraph "all" {
  "all" -> "all-recursive" [label="forced: PHONY prerequisite"]
  "all"
}
The problem is that the make process is using make to build sub-targets, this comes from the all-recursive target. In order to solve this we need to tell, in this case automake, that all calls to make should use the -g option.
$ touch src/file.c
$ AM_MAKEFLAGS="-g" make -g

This gives us an additional all-am.dot file from the all-am make goal, which holds the missing information:

strict digraph "all-am" {
  "make" -> "src/file.o" 
  "all-am" -> "make" 
  "all-am"
}

Status and feedback

I have submitted this proposal to the GNU Make project. The maintainers will decide if this is something that is worthwhile and something they could consider maintaining.

You can also find the implementation in my Make fork at GitHub, here.

I would love to hear your thoughts on this. Is this something you would find useful? Please comment here or drop me a line on Twitter (@jonasdn) with your opinions!

Wednesday, 12 August 2020

Getting to know RISC-V through the hifive1-revb board

I have been interested in the RISC-V architecture for a while. RISC-V is an  Instruction Set Architecture, like ARM, MIPS or x86, but it is developed and provided under an open source license.

A couple of weeks ago the hifive1-revb development board I ordered from Crowd Supply arrived and I have been using it to get to know RISC-V a bit. The small get-to-know-the-board project I settled on was to use the LEDs on the board to blink HELLO in morse code using RISC-V assembly.

The HiFive1 Rev B and its components, which are described in the getting started guide


Getting to know the development board

Starting with a new development board (or micro-controller) is a bit like getting to know a new API. The problem, like with many other areas, is knowing what information you need and where to find it.

Simply put -  you are not supposed to just know how to talk to or get software onto a board that is put in front of you.

Your best bet is always that the vendor will provide information on which extra hardware is required (cables, power supplies, ...), how to develop software for the board and how to get that software onto the board. 

The hifive1 revb comes with a getting started guide that tells us that only a micro-USB cable is needed for power, communication, debugging and getting software onto the board.

J-Link OB connectivity

The reason we can get all that with just an USB cable is that the hifive1 revb comes with a J-Link OB from Segger. This chip is mounted on the the development board and connected to the RISC-V core (FE310-G002) via a JTAG (standard port-thingie for debugging) and a serial port. This makes interacting with the board quite pleasant.

The getting started guide also tells us how to develop software for the board. It points us to the Freedom E SDK which is maintained by SiFive and provides libraries and build systems for making developing software for any and all of SiFive's development boards.

Since I wanted to get to know RISC-V a bit on my own I chose to not use the Freedom E SDK (but I glanced at it when my own stuff failed to work).

Making a LED shine red

The development board includes a FE310-G002 RISC-V core, and the SiFive page for the board links us to the manual for that core as well as the schematics of the board itself.

After looking around a bit in the schematics one can find the part that tells us about the LEDs, from that we see that the red LED is connected to GPIO_22. A GPIO is a digital port on the CPU that is not dedicated to a specific function, it can be used to control any peripheral of your choosing,

LED schematics

Next up is looking at the GPIO section of the FE301-002 manual. And the interesting part for us is the GPIO memory map. 

RISC-V uses memory mapped I/O which means that the same memory address space, and the same instructions, are used to talk to both memory and devices. The GPIO memory map will tell us how to interface with the GPIO controller of the FE3001-002.


From the manual we can read that the base address of the GPIO instance is 0x10012000,
and that there are 32 GPIOs. We also get the offsets to a bunch of registers that control different things about the GPIOs. All registers are 32 bits wide. This means that if we wanted to enable a GPIO as an output,  we would write a bit-mask detailing which GPIO we wanted to enable to the offset 0x08 of address 0x10012000.

In RISC-V assembly that would look something like this:

.section .text

.equ GPIO_BASE, 0x10012000 # Memory address of FE310-G002 GPIO
.equ GPIO_RED,  0x400000   # (00000000010000000000000000000000)

.global led_init
led_init:
  li t0, GPIO_BASE # li: load the constant GPIO_BASE into t0
  li t1, GPIO_RED  # Load the constant GPIO_RED into t1

  sw t1, 0x08(t0)  # To enable GPIO_RED we write a 32bit word with
                   # the 22nd bit set to offset 0x08 (output_en)
 
  sw t1, 0x40(t0)  # We make the GPIO "active high", by writing
                   # to offset 0x40 (out_xor)               
  ret

The li (load immediate) instruction will load the value of the constant into a (temporary) register. And the sw (store word) instruction will write that value to the given offset of the address found in the register.

The write to the register at offset 0x40 (output_xor) will make the GPIO active high, meaning that writing a 1 to the GPIO will make its output high, the other way around is the default.

If we now want to turn on the LED we write 0x4000000 (bit 22 set) to offset 0x0c of the GPIO_BASE address.


Making our program wait

In order to find out how we can implement a function that will wait for a fixed number of milliseconds we need to turn to the FE301-002 manual again, there we can find the mtime register. 

The mtime register contains the number of cycles performed since the Real Time Clock started. The mtime register is accessed through address 0x200bff8 and we can find out that the frequency of the RTC is 32768 kHz from reading the RTC chapter of the manual.

Knowing all this, we can put together a function that will wait until the RTC has counted enough cycles to satisfy our waiting time. In RISC-V assembly that might be expressed like this:

.section .text

.equ MTIME_REG, 0x200bff8 # memory address of MTIME register
.equ RTC_FREQ, 33

.global wait_ms
#
# Arguments:
#   - a0: number of milliseconds to busy wait
#
wait_ms:
  li s0, MTIME_REG # li: load the constant MTIME_REG into s0
  lw s1, 0(s0)     # lw: load the value at offset 0 of MTIME_REG,
                   # to get the number of cycles counted by the RTC
              
  li s2, RTC_FREQ  # Load the constant RTC_FREQ into S2
  mul s2, s2, a0   # Multiply milliseconds with the frequency
                   # to get cycles to wait
                       
  add s2, s1, s2   # Add cycles to wait to cycles counted
cmp:
  lw s1, 0(s0)     # Load current number of cycles into s1
  blt s1, s2, cmp  # If current number of cycles are lower
                   # than target, keep looping
  ret


Getting the software onto the board

Now we have gathered all the information we need from the schematics and manual, and we have put together some clever code to make the board perform our desired actions. Now it is time to get the source into a shape that the board can understand.

First we need to get a toolchain capable of handling code for the RISC-V architecture. The getting started guide tells us that you can get it from the SiFive website. It is also possible to get a toolchain through regular software distribution channels.

For Fedora you might try:

# dnf install gcc-riscv64-linux-gnu

And for Ubuntu maybe:

# apt install gcc-riscv64-unknown-elf

Using this we can compile our programs. There are still some gotchas though.

We need to tell the compiler or assembler in detail what platform we are building the software for, in our case we can find this information in the manual, it tells us that FE3001-G002 is a 32 bit RISC-V with the I, M, A and C extensions.

This can be translated to the command line of the assembler in this way:

# riscv64-unknown-elf-as -march=rv32imac -mabi=ilp32 \
  -c -o wait.o wait.S

The -mabi=ilp32 flag tells the assembler that ints longs and pointers are all 32 bits in size.

After this we can generate object code for the correct platform. But we need to link it together to create a binary that can run on our hifive1-revb board. The way we do this is by using the linker (ld) program.

The linker will put the code at the memory address that we tell it to. This is done by way of a linker script. A linker script is always used when ld is used. Most of the time we are not aware of it, because we are developing in a standard environment where we do not need to be concerned about the memory layout of the system. But even so, a linker script is being used. One can find out what the default built-in linker script is by running ld with the --verbose flag.

The default linker script I got when I ran the riscv64-unknown-elf-ld program without specifying a linker script can be seen in this gist.

I am sure (actually I am not) there are people for whom linker scripts come natural and that they can wake up at all hours of the night to write one. But I am not one of them. Enough time usually passes between me having to write one that I end up googling all the basics every time. For people wanting to learn more about them, I can recommend the excellent blog post: From Zero to main(): Demystifying Firmware Linker Scripts by François Baldassari.

I wanted to write the smallest possible linker script I could get away with for the hifive1-revb board, and I ended up with this:

MEMORY
{
  flash	(rx) : ORIGIN = 0x20010000, LENGTH = 512M
}

SECTIONS
{
  .text :
  {
    *(.text)
  } > flash

  .rodata :
  {
    *(.rodata)
  } > flash
}

So first I define a memory region called flash and tell the linker that the start of this region is at address 0x20010000. This is taken from the FE310-G002 manual, the Freedom E SDK and google, where I found out that the current bootloader code of the hifive1-revb will jump to 0x20010000 (if anyone can find an official source for this, please comment).

Then I tell the linker that there are two sections, one called .text (this is by convention where the machine code lives) and one called .rodata (this is where const data is kept). And both of them should reside in flash.

This makes ld place our code at address 0x2001000 where the bootloader of the development board expects it to be.

With all this known, we can perform the linking:

# riscv64-unknown-elf-ld hello-morse.o  -m elf32lriscv -nostartfiles \
  -nostdlib -Thello-morse.lds -o hello-morse.elf

We specify our linker script using the -T flag. The output of this command is an elf executable which is all well and good. But it is not what we want to upload to our board. The board wants a binary in hex format, we can get that from an elf using the objcopy command.

# riscv64-unknown-elf-objcopy -O ihex hello-morse.elf hello-morse.hex

And now we are ready to use tools from Segger, you can download the  J-Link Software and Documentation Pack from the Segger website.

And the magic incantation to have it download your software to the development board is as follows:

$ JLinkExe 
SEGGER J-Link Commander V6.40 (Compiled Oct 26 2018 15:08:38)
DLL version V6.40, compiled Oct 26 2018 15:08:28

Connecting to J-Link via USB...O.K.
Firmware: J-Link OB-K22-SiFive compiled Nov 22 2019 12:57:38
Hardware version: V1.00
S/N: 979014353
VTref=3.300V


Type "connect" to establish a target connection, '?' for help
J-Link>connect
Please specify device / core. <Default>: FE310
Type '?' for selection dialog
Device>FE310
Please specify target interface:
  J) JTAG (Default)
TIF>
Device position in JTAG chain (IRPre,DRPre) <Default>: -1,-1 => Auto-detect
JTAGConf>
Specify target interface speed [kHz]. <Default>: 4000 kHz
Speed>
Device "FE310" selected.


Connecting to target via JTAG
TotalIRLen = 5, IRPrint = 0x01
JTAG chain detection found 1 devices:
 #0 Id: 0x20000913, IRLen: 05, Unknown device
Version: 0.13, AddrBits: 7, DataBits: 32, IdleClks: 5, Stat: 0
ISA: RV32I+ACMU
RISC-V identified.
J-Link>loadfile hello-morse.hex
Downloading file [hello-morse.hex]...
Comparing flash   [100%] Done.

We ask the JLink software to connect and get a series of questions in return. We tell the software that our device is a FE310 and after that answer the default (JTAG, auto-detect, 4000 kHz).

After this we issue a loadfile command with our hex file as argument, and we are off!

The complete, heavily commented, assembly source and Makefile for the hello morse program can be found at my github here.

Thank you for reading! Below is a video of the hifive1-revb blinking some morse!