Herodotus

(It's a work in progress.)

Herodotus is a project for tracking and linking analytic and synthetic facts about (the releases of) a package. The tracking is to be done independently per package. (Sisyphus is an example of a repository of packages where this can be applied.)

(Herodotus is inspired by, and partly based in the implementation, on herodotos tool. Note the different spelling of the name of this tool and of our project. Named after Herodotus.)

Introduction

Which computed or external meta-information for a package is tracked

• Analytic facts (computed from the "internal" content of package releases):

• Static analysis of the C/C++ code (warnings):

• by coccinelle
• by cppcheck
• ...

• Discovery of source files which are not used during the build of the package (by means of strace or by the access time)
• ...

• Synthetic facts (added "externally" by maintainers)

• Resolutions for the warnings from the static analysis (a reason why they are invalid or a fix).
• ...

Representation

• Each fact is linked to the corresponding Git (Gear) commit or tag.
• (The facts can be stored in the same Git repository in a separate branch.)
• If the "same" fact appears for several releases, all its occurrences are linked together, so that a maintainer can view them as a single fact. Only when the facts change between releases, it should need attention.

User interfaces

• Files (obtained via Git), org-mode editor (Emacs; org-mode is like a personal wiki)
• ...

Implementation details

The core: herodotos tool

herodotos tool runs the analyzers for different releases and then links identical facts (modulo the diff, i.e., the changes of the source code).

Description of herodotos tool

• http://coccinelle.lip6.fr/papers/aosd10.pdf
• https://kernelnewbies.org/NicolasPalix (its developer; this page has a short description of the tool)

herodotos in ALT repos

herodotos in p8

•  p8, test-only task #243195 herodotos

(or: test-only task #257760 herodotos with the optional dependency on gumtree excluded because it is missing in p8, so that one can install it)

Requires:

•  p8 ocaml-bolt (Upstream: downloads; darcs get http://bolt.x9c.fr/)
•  p8 ocaml-parmap
•  p8 (works, but not quite ready) ocaml-postgresql

Requires (for counting LOC; this dependency became optional in recent herodotos versions):

•  p8 sloccount

Needed mainly for reproducing the author's experiments with Linux sources as a way of testing herodotos:

•  p8 coccinelle with support for embedded Python

Needed optionally for better correlation:

•  p8 gumtree

Requires:

•  p8 cgum

herodotos in p9

•  p9 herodotos

Requires:

•  p9, test-only task #243204 ocaml-bolt (Upstream: downloads; darcs get http://bolt.x9c.fr/)
•  p9 ocaml-parmap
•  p9 (another version, ok?) ocaml-postgresql

Requires (for counting LOC; this dependency became optional in recent herodotos versions):

•  p9 sloccount

Needed mainly for reproducing the author's experiments with Linux sources as a way of testing herodotos:

•  p9 coccinelle with support for embedded Python

Needed optionally for better correlation:

•  p9 gumtree

Requires:

•  p9 cgum

herodotos in Sisyphus

•  sisyphus herodotos

Requires:

•  sisyphus, test-only task #243205 ocaml-bolt (Upstream: downloads; darcs get http://bolt.x9c.fr/)
•  sisyphus ocaml-parmap
•  sisyphus (another version, ok?) ocaml-postgresql

Requires (for counting LOC; this dependency became optional in recent herodotos versions):

•  sisyphus sloccount

Needed mainly for reproducing the author's experiments with Linux sources as a way of testing herodotos:

•  sisyphus, test-only task #243259 coccinelle with support for embedded Python

Needed optionally for better correlation:

•  sisyphus gumtree

Requires:

•  sisyphus cgum

How to try herodotos

If you want to try the herodotos tool, try to reproduce the authors' work https://github.com/coccinelle/faults-in-linux . (It is more recent; the older work http://coccinelle.lip6.fr/papers/aosd10.pdf with their data and configuration is not suitable for the current herodotos 0.8+ version.)

See a concrete example: /How to try herodotos.

coccinelle support

coccinelle is natively supported by herodotos tool.

Actually, herodotos tool can work with any analyzer which gives output in the org-mode format.

coccinelle in Sisyphus

•  coccinelle

cppcheck support

• cppcheck is supported by flycheck (an Emacs package)
• flycheck can be hacked to output the information in the format suitable for herodotos tool (org-mode)

So, we could easily get the support for any analyzer known to flycheck.

cppcheck in Sisyphus

•  cppcheck
•  emacs-mode-flycheck
•  flycheck output in org-mode format

Discovery of source files which are not used during the build of the package

Either builds under strace can be used to discover files which are not used, or the access time (an idea by boyarsh@, which has already been probably implemented by him).

Extensions to be implemented

Ad hoc sources for herodotos

Ad hoc ways to feed herodotos some specific sources (which are not covered by the configuration "*SCM" and "versions" parameters):

 herodotos preinit-add git REPO TAG
 herodotos preinit-add rpm-bp FILE
 herodotos preinit-add srpm FILE

More; easy to implement; but not really needed much (as for now):

 herodotos preinit-add rpm-bp+gear REPO TAG
 herodotos preinit-add srpm+gear REPO TAG

Here, the way the git option is processed is similar to how the git: sources from the configuration are treated. (An exercise in implementing preinit-add on the base of the existing code.)

The rpm-bp option would invoke rpm to prepare the source tree (with all the patches applied etc. by performing the prep stage with rpmbuild -bp, optionally under hasher); the srpm option is about a stupid unpacking of an .src.rpm and of the archives it contains. The +gear options are about getting the srpm from a Gear repo.

More methods for herodotos to get sources

In the spirit of the current way to write the configuration file, in addition to git: (combined with versions to select the tags), one could implement more methods for herodotos to get sources from some other kinds of repositories:

•  rpm-bp+gear: (or srpm+gear:)
•  the Sisyphus (and branches) archive (whereby the repo index might help to learn the releases and their place in the archive).

This could be useful for a more automated study of packages from Sisyphus and branches.

Usage

Herodotus as server

Think of the work with Herodotus as a server (which is in some respect similar to girar).

The main task of the server is to store the analysis of a package (for each known package) in a "normal" form, i.e., after having done the best effort of correlating the analyses for each known version (release) of the package.

The stored analysis of a package can be updated upon request with new information. Most commonly, the new information is:

• a new analysis of a specific new version (release) of the package;
• or additional manual correlations between warnings from the old analyses.

After getting new information, the Herodotus server must "normalize" it (i.e., make the best effort to automatically correlate) and save.

The Herodotus server uses a Git repository for each package as a way to store the current and past states of the analysis of this package.

Action: "update" (performed by the server)

(Applicable for each individual package. Parameter: a branch name, which is to be updated.)

Result

a "normal" (automatically correlated) analysis in the top commit of the specified branch (on the server).

Input

a Git commit with analysis results (and optional correlations) in herodotos format. (The old head of the Git branch on the server should be an ancestor of this new Git commit.)

The Git commit that comes as an input to the "update" action can be created by the "analyze" action described below.

Action: "analyze" (performed anywhere)

(Applicable for each version (release) of each individual package.)

Result

a Git commit containing an analysis of the specified version (release) of the package in herodotos format.

Input

a herodotos config with a specification of the version (release) of the package to be analyzed.

Commonly, one creates the commit with the analysis of a new version (release) on top of a previous commit with old analyses.

Manual action: edit the analyses or correlations in herodotos format

A special Emacs mode (extension to org-mode) can be used to do this conveniently, side-by-side with exploring the actual corresponding source code.

herodotus-server commands

herodotus-server.git contains scripts and related data that represent the model of Herodotus as a server.

• herodotus-update
• herodotus-helper-analyze-each (automatically runs cppcheck for each known version (release) of a package)

herodotus-helper-analyze-each

herodotus-helper-analyze-each STEM PKGNAME

automatically runs cppcheck for each known version (release) of a package (and saves the results).

It is to be run inside a Git repository. It is possibly an empty directory. It will re-initialized as a Git repo.

STEM is the stem of the Git branch name, which will be used to save the results. (At the same time, it is used to get the sources from this branch in the ALT archive.)

PKGNAME is the name of the package to be analyzed. (The srpms are taken from the ALT archive.)

Example of a one-shot use of herodotus-helper-analyze-each

Example: analyze each release in the history of package "anacron" in ALT c7 branch:

$ mkdir anacron
$ cd anacron/
$ /home/imz/wip/2018-10-herodotos-cppcheck/herodotus-server/herodotus-helper-analyze-each c7 anacron

What herodotus-helper-analyze-each has done internally

(It has invoked various tools in a way similar to how the author of herodotos used it to analyze the Linux kernel sources.)

It has looked up the list of the known versions (releases) in c7/index/src/a/anacron/d-t-s-evr.list under /usr/src/HERODOTOS/INPUT/anacron/../ALT/repo/ (the path is constructed according to the configuration in study.hc.base from herodotus-server.git); here is what it has seen there (so that you better understand what has been going on):

$ cat /usr/src/HERODOTOS/INPUT/anacron/../ALT/repo/c7/index/src/a/anacron/d-t-s-evr.list 
1381657390	105852	-	1:2.3-alt6
$

It has cached the unpacked/"prepared" sources of each of the releases under /usr/src/HERODOTOS/INPUT/anacron/

$ ls -l /usr/src/HERODOTOS/INPUT/anacron/
total 0
drwxrwxrwx 5 imz imz 260 дек 21  2018 anacron-1@2.3-alt6
$

(One kind of trick or another is needed if you want to share the cache between multiple users of the system. TODO: describe them in details.)

Then it has run the analyzer on each of the versions (releases) of the sources; in this case, it has been cppcheck (according to the configuration in study.hc.base from herodotus-server.git).

Results of herodotus-helper-analyze-each

It has made a Git commit with the results:

$ git ls-files
.depend
.depend.erase
.depend.patterns
.projects_study.hc
RESULTS/anacron/.depend.Linux
RESULTS/anacron/Linux_cppcheck.orig.org
RESULTS/anacron/anacron-1@2.3-alt6/Linux_cppcheck.log
RESULTS/anacron/anacron-1@2.3-alt6/Linux_cppcheck.orig.org
study.hc
$

It has saved the analysis (done by cppcheck) of each release, namely, of the single known release in this case:

$ cat RESULTS/anacron/anacron-1\@2.3-alt6/Linux_cppcheck.orig.org 
* TODO [[view:/usr/src/HERODOTOS/INPUT/anacron/anacron-1@2.3-alt6/anacron/matchrx.c::face=ovl-face1::linb=52::colb=1::cole=2][Memory leak: sub_offsets]]
$

(TODO: of course, analyzing deleted packages seems like a strange behavior, so it should be fixed. But we show it here nevertheless just for the demonstration of the structure of the results.)

All results from all releases will be put together in a single common file after correlation (the "update" action on the Herodotus server), which we haven't done yet; so, it is empty for now:

$ wc -l RESULTS/anacron/Linux_cppcheck.orig.org
0 RESULTS/anacron/Linux_cppcheck.orig.org
$

Test example: correlating cppcheck histories for each package in a repository branch

Installation

herodotos tool

The herodotos tool is installed from the task mentioned above in #herodotos_in_p8:

apt-repo test 257760 herodotos

or a locally-built package:

rpm -Uhv ~imz/hasher-p8-herodotos/repo/x86_64/RPMS.hasher/herodotos-0.8.0.0.21-alt1.x86_64.rpm

herodotus-server

For now, I use a locally checked-out copy of herodotus-server:

# ls -l /space/home/herodotus/bin/
total 8
lrwxrwxrwx 1 herodotus herodotus 87 ноя  9  2018 herodotus-helper-analyze-each -> /home/imz/wip/2018-10-herodotos-cppcheck/herodotus-server/herodotus-helper-analyze-each
lrwxrwxrwx 1 herodotus herodotus 74 ноя  9  2018 update -> /home/imz/wip/2018-10-herodotos-cppcheck/herodotus-server/herodotus-update

The "analyze" action is usually run by other users, so they must use the complete path to herodotus-helper-analyze-each.

(Remark: herodotus-helper-analyze-each determines the name of the analyzed package from the current working dir. The current working will be used to save the results of the analysis. After it determined the name of the package, it gets the list of releases from a local mirror of /ALT/repo/, and the source packages (if not cached already) from a local mirror of the repo.)

Cache of unpacked sources

Whenever you invoke the "analysis" action of herodotos tool, it unpacks the sources to be analyzed.

According to the study.hc.base template from herodotus-server package, the "cache" of the unpacked sources is located under /usr/src/HERODOTOS/INPUT/ (one directory per project/package; one subdir per release):

projects="/usr/src/HERODOTOS/INPUT"

The same location (in the "cache") will appear in the paths in the results (in the .org format) of the "analyze" or "correlate" actions. So, if you explore the warnings in the results and want to view the corresponding source code, Emacs will open the file in the cache.

This location must be writable by all users who run the "analyze" action themselves and readable (and maybe writable) by the "herodotus" user, under which the server runs the "correlate" action.

There are better clever ways to achieve the needed permissions, but I won't describe them now. The simplest way is to have the permissions like this (recursively):

# ls -ld /usr/src/HERODOTOS/INPUT/
drwxrwxrwx 813 herodotus herodotus 16260 дек 23  2018 /usr/src/HERODOTOS/INPUT/

ALT/repo

In my Git repo herodotos, I have a helper script for mounting /ALT/repo, which is needed to get the list of the releases of a package and to get the srpms: herodotos/scm/alt_archive.mount.

There are different possibilities (to use the public mirror via ftp, or a private one via ssh); here is an example:

sshfs -o ro,allow_other,kernel_cache team.alt:/ALT/repo /usr/src/HERODOTOS/INPUT/ALT/repo

It is found according to study.hc.base from herodotus-server package:

project Linux {

 // Too old (archived under /alt0/repo/sisyphus/task/archive and not available -- FIXME)
 local_scm = STRINGIFY(unpack+alt_archive:../ALT/repo c7 PKGNAME)
...

(When it is working with "project" under /usr/src/HERODOTOS/INPUT/, as decribed above, according to this configuration line, to find the source repo, it must go one dir up and look for ALT/repo there.)

pregirar

pregirar is a package with utilities that help to run the analysis in parallel.

Running the analysis

Preparation

$ pwd
/home/imz/wip/2018-10-herodotos-cppcheck
$ mkdir ANALYSES.4
$ cp -av ANALYSES.3/n* -t ANALYSES.4/
'ANALYSES.3/n' -> 'ANALYSES.4/n'
'ANALYSES.3/n-a-k' -> 'ANALYSES.4/n-a-k'
'ANALYSES.3/n-l-z' -> 'ANALYSES.4/n-l-z'
$ cd ANALYSES.4
$ make -f ../ANALYSES.mk mkdirs -o n_v_r-a-k -o n_v_r-l-z
mkdir -p GEARS
(cd GEARS && xargs mkdir -p) <n
$

Running in parallel

pregirar helps to run in parallel.

I run the following under screen screen in a dir ANALYSES.4 (created above).

pregirar-in_each-parallel 31 31 analyze-each /home/imz/wip/2018-10-herodotos-cppcheck/herodotus-server/herodotus-helper-analyze-each c7 <n

Evaluation of the test

Logs of the failed tasks

Compare the logs of the tasks that finished with an error:

diff -r ANALYSES.{2,3}/in_each-analyze-each/error | less

or (to see new failed tasks):

diff -qr ANALYSES.{2,3}/in_each-analyze-each/error | fgrep Only | less

Compare both the "error" and success" logs:

diff -qr ANALYSES.{2,3}/in_each-analyze-each -x archive | fgrep Only | less

archive is excluded because they might have been different number of tries in different tests.

Comapring the RESULTS

diff -r ANALYSES.{2,3}/GEARS  -x .git -x .projects_study.hc -x filelist  -x sloc_hashes -x top_dir -x Linux_cppcheck.log | less

In this diff, you basically see which RESULTS are absent (or what their diff is).

• Comparing the Linux_cppcheck.log files is not quite useful, because the timings always differ.
• -x filelist -x sloc_hashes -x top_dir is to exclude the working files of sloccount, which might fail sometimes. (FIXME)
• .projects_study.hc might differ due to failed sloccount (it includes the number of lines of code)...

Exploring analysis results

Here is an illustrated example of exploring analysis results (from svace) in Herodotus with emacs.

Step 1: find the corresponding .org-file

Step 2: the .org-file opened in org-mode

Step 3: look at the source code by clicking an item

Step 4: label the warning as a BUG after thinking about it (with C-c C-t keys)