Thursday, 22 October 2020

Proposal to add build graph output to GNU Make


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 -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/'
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
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" 

And we can generate a PNG from it:

$ dot -Tpng -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 file hardly contains any information about the rebuild:
strict digraph "all" {
  "all" -> "all-recursive" [label="forced: PHONY prerequisite"]
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 file from the all-am make goal, which holds the missing information:

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

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
  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)               

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
  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
  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

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:

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

  .text :
  } > flash

  .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 -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

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

Monday, 6 February 2017

Maps at FOSDEM

I went to FOSDEM again this year, my fourth year running. I go with a great group of friends and it is starting to become quite the tradition.

Maps meeting

FOSDEM lines up pretty well with the GNOME release cycle, in that after the conference we have about a month of time to get the last stuff in before the next 6 month development cycle comes to an end. With that in mind we had a quite quick and informal Maps meeting on what the immediate priorities where for the release and what we wanted to do after that.

Transit routing

We want to merge Marcus transit-routing branch this cycle. This will not add anything if there is no OpenTripPlaner server available. But our plan is to be able to add one to our service file so this can be turned on if we get some sponsorship or in any other way manage to solve the infrastructure needs. This will also be a way of disabling the functionality if we lose infrastructure, such as with our MapQuest tiles previously.

Geocoding / search as you type

We now have a Mapbox account. We could use the Mapbox geocoding API instead of Nominatim that we currently use. And with that we could achieve search-as-you-type functionality. The timing is right for a switch like this, since Collabora recently landed  a patch bomb on geocode-glib to make it handle custom backends through an interface. So we could write a Mapbox interface in Maps.

I did some prototyping with this during some FOSDEM talks and the (buggy) result can be seen in the video below.

An issue with using Mapbox geocoding service that I do not yet know if we can solve is that there does not appear to be a link between the id you get for a resulting place and the OpenStreetMap id. This makes it really hard for us to support editing the nodes you find.

Tile styles

Also since we have a Mapbox account it would be possible for us to make our own styles. For instance an hi-contrast style, a custom print style or a general GNOME style. This is a daunting task. But if anyone feel up for it, please let us know.

Mapbox GL Native

Thiago Santos from Mapbox held a talk about Mapbox GL Native which is a hardware-accelerated map rendering engine. It is written in C++-14 and has recently been ported to QT. Thiago talked about what is needed to port Mapbox GL Native to new platforms, and specifically called out GTK+ and GNOME Maps. Saying that it should be possible to make Mapbox GL Native work with our infrastructures.

Mapbox have written a blogpost outlining what needs to be true about a platform for Mapbox GL Native to be ported to it. Porting Mapbox GL Native to GLib land might be a nice GSoC or Outreachy project for GNOME/GTK+.

Monday, 22 August 2016

Maps is fast again!

I just released a bunch of Maps releases.
  • 3.21.90
  • 3.20.3
  • 3.18.4
  • 3.16.4
  • 3.14.4
  • 3.12.4
  • 3.10.4

All of them speeding up the fetching of tiles in two ways.
  1. By downloading a service file telling us where third-party tile servers are instead of using redirect by proxy
  2. Allowing for more consecutive HTTP requests
Number 2 is only available by using the (as of now unreleased) version 0.12.4 of libchamplain.

Once your distro of choice picks up one of these stable releases you should be back to at least the old Mapquest speed of Maps. And if your distro upgrades to latest libchamplain when it arrives you will see even greater speeds.

And as a bonus, the latest libchamplain release will bring horizontal map wrapping, courtesy of excellent GSoC student Marius Stanciu!

Sunday, 31 July 2016

Maps has tiles again

This is a short post to inform you all that Maps has tiles again. We now get our tiles from Mapbox, with whom we have made an agreement going forward. We access Mapbox through a GNOME based redirect, so that we could redirect to something else if a similar situation would arise again.

Maps has been released with the new tiles in the versions:

And I think at least Fedora has been updated.

So, while it was unfortunate that MapQuest closed down for us and we were caught off guard. We now have a better tile setup than before and more options going forward.

More information about our setup with Mapbox will come from a blog post on Planet GNOME soon. I will leave you with a taste of the new tiles.

Saturday, 16 July 2016

Getting a network trace from a single application

I recently wanted a way to get a network packet trace from a specific application. My googling showed me an old askubuntu thread that solved this by using Linux network namespaces.

You create a new network namespace, that will be isolated from your regular network, you use a virtual network interface and iptables to make the traffic from it reach your regular network. Then you start an application and wireshark in that namespace and then you have a trace of that application.

I took that idea and made it into a small program, hosted on github, nsntrace.

> nsntrace
usage: nsntrace [-o file] [-d device] [-u username] PROG [ARGS]
Perform network trace of a single process by using network namespaces.

-o file     send trace output to file (default nsntrace.pcap)
-d device   the network device to trace
-u username run PROG as username 

It does pretty much the same as the askubuntu thread above describes but with just one step.

> sudo nsntrace -d eth1 wget
Starting network trace of 'wget' on interface eth1.
Your IP address in this trace is
Use ctrl-c to end at any time.

--2016-07-15 12:12:17--
Location: [following]
--2016-07-15 12:12:17--
Length: unspecified [text/html]
Saving to: ‘index.html’

index.html                                         [ <=>                                                                                                   ]  10.72K  --.-KB/s   in 0.001s 

2016-07-15 12:12:17 (15.3 MB/s) - ‘index.html’ saved [10980]

Finished capturing 42 packets.

> tshark -r nsntrace.pcap -Y 'http.response or http.request'
16   0.998839 ->    HTTP 229 GET HTTP/1.1
20   1.010671 -> HTTP 324 HTTP/1.1 302 Moved Temporarily  (text/html)
22   1.010898 ->    HTTP 263 GET HTTP/1.1
31   1.051006 -> HTTP 71 HTTP/1.1 200 OK  (text/html)

If it is something you might have use for or find interesting, please check it out, and help out with patches. It turns out I have a lot to learn about networking and networking code.

All the best!

Maps and tiles

Hello all!

Right now we are having infrastructural problems with Maps. We can no longer use the MapQuest tiles, see mail thread from maps list archive here for more information.

We are working on getting past this and getting a working Maps application released soon. But this is also showing us more clear that we need to get a better grip around the tiles infrastructure if we want to have a Map application and/or a Map infrastructure in GNOME. We are having good discussions and I think we will get through this with a nice plan forward to prevent stuff like this happening. And also with a plan to do better in the future and do cooler stuff with tiles.

All the best!