Linux kernel 3.x call-graphs with ncc-2.8

ncc  is a compiler, built specifically to extracts call-graph information from source code. One strong feature is analysis of function pointers. Call graphs can help explore and learn large code bases, which makes it especially useful for the Linux kernel. ncc comes with documentation on extracting call-graphs from 2.6 kernels, apparently tested circa 2008. We set out to test ncc on newer kernels (3.10.25)

Summary

ncc needs work to support the Linux kernel, while I solved some problems, more work needs to be done to complete the kernel compile.

__asm__ volatile and goto

ncc 1.8 does not support “__asm__ volatile” and __asm__ goto”, used in one of the first files compiled, kernel/bounds.c. To fix, add these to the function “__asm___statement” in ncc’s “parser.C”:

static NormPtr __asm___statement (NormPtr p)
{
	NormPtr ast = p + 1;
	if ((CODE [p] == RESERVED_goto) || (CODE [p] == RESERVED_volatile)) {
	  p++;
	  ast++;
	}
	if (CODE [p] != '(') syntax_error (p, "__asm__ '('");
	p = skip_parens (p);

BUILD_BUG_ON_ZERO and BUILD_BUG_ON_NULL

The ncc compiler doesn’t handle these compile-time checks well. Disabled them in include/linux/bug.h:

//#define BUILD_BUG_ON_ZERO(e) (sizeof(struct { int :-!!(e); }))
//#define BUILD_BUG_ON_NULL(e) ((void *)sizeof(struct { int :-!!(e); }))
#define BUILD_BUG_ON_ZERO(e) (0)
#define BUILD_BUG_ON_NULL(e) ((void*)0)

nccar argument parsing

ncc emulates ar to link together collections of collected metadata. In the process, ncc makes assumptions on archive names (ending with .a or .o), however the kernel makefiles use filenames like “.28948.tmp”. This causes a segfault in ncc’s ar code. To fix, see highlighted lines below in “preproc.C”:

static bool istmp (char *f)
{
	int i = strlen (f);
	if (i < 4) return false;
	return (strcmp(&f[i-4], ".tmp") == 0);
}
static void nccar (int argc, char **argv)
{
	/*
	 * we take the simple usage:
	 *   ar [max-four-options] archive-file.[ao] obj1.o obj2.o ...
	 */
	int i, j;
	if (strchr (argv [1], 'x'))
		return nccar_x (argc-1, argv+1);
	if (!strchr (argv [1], 'r')) {
		for (i = 1; i < 5 && i < argc; i++)
			if (isobj (argv [i])) {
				openout (argv [i], "a");
				LINK (&argv [i + 1], argc - i - 1);
				stripout (argv [i]);
				return;
			}
		fprintf (stderr, "nccar: Nothing to do\n");
	} else {
		for (i = 1; i < 5 && i < argc; i++)
		  if (isobj (argv [i]) || istmp(argv[i]))
				break;

Turning off compiler optimizations

For some big files, ncc sputters and segfaults; I saw this with “init/init_task.c”. The core dump doesn’t help much in finding the root cause of this segfault. When I compiled ncc with -O0 with icc, the segfault never came and ncc carried on. When I recompiled ncc with the default optimization, the kernel compilation continued.

Running ncc on the kernel

After copying a .config file to the desired directory, ran the kernel compilation with:

make O=~/huge/linux-build-ncc HOSTCC="ncc -ncgcc -ncfabs -ncld" CC="ncc -ncfabs -ncgcc -ncld -ncspp" AR=nccar LD=nccld SHELL="sh -vx"

 A typeof error

The compilation encounters these types of problems (“* not effective”):

* not effective
/mnt/sdb1/yonch/src/linux-stable/arch/x86/kvm/vmx.c (8276): expression ncc-error:": : : "memory" ) ; ( ( crash_vmclear_loaded_vmcss ) ) = ( __typeof__ ( * ( crash_vmclear_local_loaded_vmcss ) ) * ) ( ( crash_vmclear_local_loaded_vmcss ) ) ; } while "
ncc-error :  expression trivial for typeof() 
/mnt/sdb1/yonch/src/linux-stable/arch/x86/kvm/vmx.c (8276): syntax error:"r ) goto out7 ; do { __asm__ ( "" : : : "memory" ) ; ( ( crash_vmclear_loaded_vmcss ) ) = ( __typeof__ ( * ( crash_vmclear_local_loaded_vmcss ) ) * ) ( ( crash_vmclear_local_loaded_vmcss ) ) ; } while ( 0 ) ; vmx_disable_intercept_for_msr ( 3221225728 , false ) "
make[3]: *** [arch/x86/kvm/vmx.o] Error 1

Apparently ncc doesn’t like the rcu_assign_pointer in kvm/vmx.c

        rcu_assign_pointer(crash_vmclear_loaded_vmcss,
                           crash_vmclear_local_loaded_vmcss);

Which seems to be defined in include/linux/rcupdate.h:

#define __rcu_assign_pointer(p, v, space) \
	do { \
		smp_wmb(); \
		(p) = (typeof(*v) __force space *)(v); \
	} while (0)

To work-around, I’ve removed the parentheses containing the typeof here and in include/asm-generic/percpu.h:

 /* Weird cast keeps both GCC and sparse happy. */
 #define SHIFT_PERCPU_PTR(__p, __offset)        ({                      
        __verify_pcpu_ptr((__p));                                       \
-       RELOC_HIDE((typeof(*(__p)) __kernel __force *)(__p), (__offset)); \
+       RELOC_HIDE((__p), (__offset)); \
 })
 #endif

and also in “arch/x86/include/asm/percpu.h”:

--- a/arch/x86/include/asm/percpu.h
+++ b/arch/x86/include/asm/percpu.h
@@ -59,7 +59,7 @@
        asm volatile("add " __percpu_arg(1) ", %0"      \
                     : "=r" (tcp_ptr__)                 \
                     : "m" (this_cpu_off), "0" (ptr));  \
-       (typeof(*(ptr)) __kernel __force *)tcp_ptr__;   \
+       (typeof(ptr))(tcp_ptr__);       \
 })

Fix low limits in aeqn

The aeqn class in ncc’s “cdb.C” has a hard-coded buffer size that is insufficient for processing “net/core/net_namespace.c”, resulting in a segfault. Increasing it seems to solve the problem:

Current fail

lib/vsprintf.c causes a segfault in cc_int_expression. The stack trace:

#0  0x00000000004030a8 in cc_int_expression () at ccexpr.C:1352
#1  0x0000000000414a72 in constant_int_expression (p=281344, r=@0x7ffff831a068: 20750928) at parser.C:1150
#2  0x00000000004140d2 in array_size_expression (p=281344, r=@0x7ffff831a068: 20750928) at parser.C:113
#3  0x000000000041661a in declarator::dirdcl (this=0x7ffff831a038) at parser.C:144
#4  0x000000000041a2cc in declarator::dcl (this=0x7ffff831a038) at parser.C:107
#5  0x00000000004168db in declarator::parse (this=0x7ffff831a038, i=281342) at parser.C:78
#6  0x0000000000417bfa in declarator::parse_dcl (this=0x7ffff831a038, p=281342) at parser.C:261
#7  0x00000000004187b2 in declaration::parse (this=0x7ffff831a030, p=281342) at parser.C:629
#8  0x0000000000415564 in parse_declaration (p=281341) at parser.C:1350
#9  0x00000000004155fe in compound_statement (p=281341) at parser.C:1360
#10 0x0000000000416241 in do_functions () at parser.C:1577
#11 0x000000000041634c in parse_translation_unit () at parser.C:1595
#12 0x0000000000416357 in parse_C () at parser.C:1600
#13 0x0000000000401cf0 in main (argc=75, argv=0x7ffff831a658) at main.C:128