A bit of background

In the previous post post we looked at ways to determine the dependency tree for some binaries. We left the post with a bit of cliff hanger (very tiny cliff though).

My goal

Have a look at how big a dependency tree can get an impression on the complexity such a tree implies for a license compliance tool such as flict

Dependency tree for epiphany

In the previous post we saw the dependency tree for cairo:

This time we’re going to look at Epiphany. Why Epiphany? Well, guess the only reason is that in the previous posts about Yocto. Ok, get on with it.

$ dependencies.sh --png epiphany
Log file created: /home/hesa/.vinland/compliance-utils/elf-deps/epiphany.log
Created dot file: /home/hesa/.vinland/compliance-utils/elf-deps/epiphany.dot
Created png file: /home/hesa/.vinland/compliance-utils/elf-deps/epiphany.dot.png

Here’s the resulting graph:

Wow, pretty straight forward, isn’t it. NOT! It took dependencies.sh roughly 1 minute to finish.

How many deps are there in the tree?

$ grep "\->" /home/hesa/.vinland/compliance-utils/elf-deps/epiphany.dot | wc -l
418

418, not so bad. Or is it? dependencies.sh only lists uniq dependencies, to not clutter the image. If we grep in the log file instead.

$ grep "\->" /home/hesa/.vinland/compliance-utils/elf-deps/epiphany.log  | wc -l
25049

Uh oh, so the tree is big. Which dependencies are most frequent?

$ cat /home/hesa/.vinland/compliance-utils/elf-deps/epiphany.log | cut -d ">" -f 2 | sed -e 's,\",,g' -e 's,^[ ]*,,g' | sort | uniq -c | sort -rnk1 | head -10
   2548 libpcre.so.3
   2548 libglib-2.0.so.0
   2158 libz.so.1
   1509 libXdmcp.so.6
   1509 libxcb.so.1
   1509 libXau.so.6
   1509 libbsd.so.0
   1037 libX11.so.6
   1036 libffi.so.7
    972 libpng16.so.16

So, by various libraries libpcre.so.3 and libglib-2.0.so.0 are used 2548 times.

If we were to calculate all possible combinations of licenses we can say that we need to double the combinations per OR statement in the dependencies’ license expression. So if we have one occurance of an OR statement, we’d be having 25049*2 combinations. For 10 occurances 25049*2^10 we get 25650176, roughly 26 million combinations. This strategy does not scale well, when calulating license compliance for a dependency tree. More on this in coming posts. Now, let’s get on with checking out Epiphany.

dependencies.sh does not support listing licenses so we will instead look at a Yocto build (aha, now you know why we chose epiphany as example). The result will be a JSON file which we can grep a bit in.

$ time yocto-build-to-flict.sh epiphany -sp epiphany 
Created: 
 /home/hesa/.vinland/compliance-utils/artefacts/epiphany__epiphany__epiphany.json
... snip
real	14m37,315s
user	19m54,302s
sys	5m26,294s
$grep "name" .vinland/compliance-utils/artefacts/epiphany__epiphany__epiphany.json  | wc -l
37883
$ grep "|" .vinland/compliance-utils/artefacts/epiphany__epiphany__epiphany.json  | wc -l
1145
$ echo "(37883 - 1) * (2^1145)" | bc
18104141485031505357340087022429307367060022626789252731402359771731\
09368680902785270257796644765849559772516882329898204060309495707405\
82729370162112106165799960497273877259735617563052293623794226858174\
18411916754234981789303516952736885487069980198519498542990592226444\
45915801859319525404998071910924694965762816329523568712919126238700\
4531277824

So, calculating the dependencies took more than 14 minutes. Epiphany has 37882 dependencies (37883 names where one of them belongs to Epiphany). There are 1145 OR statements in the license expressions so we’ll end up with a lot of possible combinations. Really, a lot. Look at the number above if we write it on one line:

18104141485031505357340087022429307367060022626789252731402359771731093686809027852702577966447658495597725168823298982040603094957074058272937016211210616579996049727387725973561756305229362379422685817418411916754234981789303516952736885487069980198519498542990592226444459158018593195254049980719109246949657628163295235687129191262387004531277824

Conclusion

A dependency tree is a a nice way to look at dependencies, but it pretty fast blows up and get too big to be useful.

Using a dependency graph in flict is useful but we need another strategy for bigger components, such as the above mentioned Epiphany.

Side note on bash

We used dependencies.sh to create the dependency tree. A funny thing with this tool is that it took ages (well in some cases hours) to complete the calculation of the dependency tree.

We needed to cache things and some kind of Map to do this. In bash we can use associative array. Using this we managed to speed up the calculation if libcairo from roughly 6 hours to 1 minute and 11 seconds. Nice :)

Some words about coming posts

We will check ouf how we can feed flict with a JSON file of dependencies. With such a file can be used to calculate license compliance. And by coincidence yocto-build-to-flict.sh does this.

About the cover image

This post, we simply use one of the graphis produced by dependencies.sh.