Tag Archives: C

Parse BPF_ARRAY macro in bcc

Published / by nanxiao / Leave a Comment

BPF_ARRAY is a very common macro used in bcc scripts. To analyze it, I put all BPF_ARRAY related macros in an example file:

// Changes to the macro require changes in BFrontendAction classes
#define BPF_F_TABLE(_table_type, _key_type, _leaf_type, _name, _max_entries, _flags) \
struct _name##_table_t { \
  _key_type key; \
  _leaf_type leaf; \
  _leaf_type * (*lookup) (_key_type *); \
  _leaf_type * (*lookup_or_init) (_key_type *, _leaf_type *); \
  int (*update) (_key_type *, _leaf_type *); \
  int (*insert) (_key_type *, _leaf_type *); \
  int (*delete) (_key_type *); \
  void (*call) (void *, int index); \
  void (*increment) (_key_type); \
  int (*get_stackid) (void *, u64); \
  _leaf_type data[_max_entries]; \
  int flags; \
}; \
__attribute__((section("maps/" _table_type))) \
struct _name##_table_t _name = { .flags = (_flags) }

#define BPF_TABLE(_table_type, _key_type, _leaf_type, _name, _max_entries) \
BPF_F_TABLE(_table_type, _key_type, _leaf_type, _name, _max_entries, 0);

#define BPF_ARRAY1(_name) \
  BPF_TABLE("array", int, u64, _name, 10240)
#define BPF_ARRAY2(_name, _leaf_type) \
  BPF_TABLE("array", int, _leaf_type, _name, 10240)
#define BPF_ARRAY3(_name, _leaf_type, _size) \
  BPF_TABLE("array", int, _leaf_type, _name, _size)

// helper for default-variable macro function
#define BPF_ARRAYX(_1, _2, _3, NAME, ...) NAME

// Define an array function, some arguments optional
// BPF_ARRAY(name, leaf_type=u64, size=10240)
#define BPF_ARRAY(...) \
  BPF_ARRAYX(__VA_ARGS__, BPF_ARRAY3, BPF_ARRAY2, BPF_ARRAY1)(__VA_ARGS__)

enum stat_types {
  S_COUNT = 1,
  S_MAXSTAT
};

void main(void)
{
  BPF_ARRAY(stats, u64, S_MAXSTAT + 1); 
}

Use gcc -E to preprocess it (I have formatted code to make it clear):

# 1 "test.c"
# 1 "<built-in>"
# 1 "<command-line>"
# 31 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 32 "<command-line>" 2
# 1 "test.c"
# 38 "test.c"
enum stat_types {
    S_COUNT = 1,
    S_MAXSTAT
};

void main(void)
{
    struct stats_table_t { 
      int key; 
      u64 leaf; 
      u64 * (*lookup) (int *); 
      u64 * (*lookup_or_init) (int *, u64 *); 
      int (*update) (int *, u64 *); 
      int (*insert) (int *, u64 *); 
      int (*delete) (int *);
      void (*call) (void *, int index); 
      void (*increment) (int); 
      int (*get_stackid) (void *, u64); 
      u64 data[S_MAXSTAT + 1]; 
      int flags; 
    }; 
    __attribute__((section("maps/" "array"))) struct stats_table_t stats = { .flags = (0) };;
}

Let’s analyze how the final result is got:

(1)

BPF_ARRAY(stats, u64, S_MAXSTAT + 1)    

will be expanded to (__VA_ARGS__ will be replaced by all arguments):

BPF_ARRAYX(stats, u64, S_MAXSTAT + 1, BPF_ARRAY3, BPF_ARRAY2, BPF_ARRAY1)(stats, u64, S_MAXSTAT + 1)

(2) According to:

// helper for default-variable macro function
#define BPF_ARRAYX(_1, _2, _3, NAME, ...) NAME

BPF_ARRAYX(stats, u64, S_MAXSTAT + 1, BPF_ARRAY3, BPF_ARRAY2, BPF_ARRAY1)(stats, u64, S_MAXSTAT + 1) will be replaced by following code:

BPF_ARRAY3(stats, u64, S_MAXSTAT + 1)

We can compared it to BPF_ARRAY1 (both _leaf_type and size have default values) and BPF_ARRAY2 (only size have default value.).

(3) Convert BPF_ARRAY3 to final BPF_F_TABLE is more straightforward, so I won’t drill that down.

Use the same method you can analyze other macros, such as BPF_HASH. Hope this small post can give you a tip!

The subtlety of building ANTLR C runtime library

Published / by nanxiao / Leave a Comment

If you want to use ANTLR C runtime library, you should pay attention that it will be compiled to 32-bit library by default even in 64-bit platform:

# ./configure
......
# make
make  all-am
make[1]: Entering directory '/root/Project/libantlr3c-3.4'
/bin/sh ./libtool  --tag=CC   --mode=compile gcc -DHAVE_CONFIG_H -I. -Iinclude    -m32  -O2  -Wall -MT antlr3baserecognizer.lo -MD -MP -MF .deps/antlr3baserecognizer.Tpo -c -o antlr3baserecognizer.lo `test -f 'src/antlr3baserecognizer.c' || echo './'`src/antlr3baserecognizer.c
libtool: compile:  gcc -DHAVE_CONFIG_H -I. -Iinclude -m32 -O2 -Wall -MT antlr3baserecognizer.lo -MD -MP -MF .deps/antlr3baserecognizer.Tpo -c src/antlr3baserecognizer.c  -fPIC -DPIC -o .libs/antlr3baserecognizer.o
In file included from /usr/include/features.h:434:0,
                 from /usr/include/bits/libc-header-start.h:33,
                 from /usr/include/stdio.h:28,
                 from include/antlr3defs.h:248,
                 from include/antlr3baserecognizer.h:39,
                 from src/antlr3baserecognizer.c:9:
/usr/include/gnu/stubs.h:7:11: fatal error: gnu/stubs-32.h: No such file or directory
 # include <gnu/stubs-32.h>
           ^~~~~~~~~~~~~~~~
compilation terminated.
make[1]: *** [Makefile:449: antlr3baserecognizer.lo] Error 1
make[1]: Leaving directory '/root/Project/libantlr3c-3.4'
make: *** [Makefile:308: all] Error 2

In order to build 64-bit library, you should specify --enable-64bit option during configure stage:

./configure --enable-64bit

Then it will be generated to 64-bit library.

What is the effect of extern “C”?

Published / by nanxiao / 1 Comment on What is the effect of extern “C”?

I often see the following code in C header files:

#ifdef __cplusplus
extern "C" {
#endif

......

#ifdef __cplusplus
}
#endif

What does it mean? Since there is __cplusplus marco, it must be related to C++ compilation. Let’s see a simple program (print.c):

$ cat print.c
#include <stdio.h>

void print(void)
{
        printf("Hello world!\n");
}

Use gcc to generate object file:

$ gcc -c print.c
$ 

Then create a main.cpp file which calls print() in its main() function:

$ cat main.cpp
extern void print(void);

int main(void)
{
        print();
        return 0;
}

Compile main.cpp and link with print.o:

$ g++ main.cpp print.o
/tmp/cc60fu19.o: In function `main':
main.cpp:(.text+0x5): undefined reference to `print()'
collect2: error: ld returned 1 exit status

It is weird, right? the print() function must be defined in print.o, why can’t g++ find it? Let’s do a simple magic, add "C" in extern void print(void);:

$ cat main.cpp
extern "C" void print(void);

int main(void)
{
        print();
        return 0;
}

Try compile main.cpp again:

$ g++ main.cpp print.o
$ ./a.out
Hello world!

It is OK now! The root cause is related to name mangling. To be simplified, when compile C++ code, the names of functions, global variables, etc will be modified, not the same as original format. While compile C code, this won’t happen. The function of extern "C" is to tell C++ compiler search the original name, not the mangled ones. To get a sense of name mangling, you can check the print() name in object file:

$ readelf -s print.o | grep print
 1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS print.c
 9: 0000000000000000    17 FUNC    GLOBAL DEFAULT    1 print

Then use g++ to compile print.c, and check function name again:

$ g++ -c print.c
$ readelf -s print.o | grep print
 1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS print.c
 9: 0000000000000000    17 FUNC    GLOBAL DEFAULT    1 _Z5printv

You can see the print() function name is actually _Z5printv when use g++ to generate the object file.

References:
Why do we use extern “C”?;
In C++ source, what is the effect of extern “C”?.

The differences between using gcc/g++ to compile *.c/*.cpp files

Published / by nanxiao / Leave a Comment

I bump into Compiling a C++ program with gcc today, and think it is a very interesting topic. So I do the following tests:

(1) Create a canonical C source file:

$ cat main.c
#include <stdio.h>

void hello(void)
{
        printf("Hello World!\n");
}

int main(void)
{
        hello();
}

Use gcc to compile it and search hello in symbol table of executable file:

$ gcc main.c
$ readelf -s a.out | grep hello
53: 00000000004004f6    17 FUNC    GLOBAL DEFAULT   13 hello

Then use g++ to compile it and also search hello in a.out:

$ g++ main.c
$ readelf -s a.out | grep hello
54: 0000000000400526    17 FUNC    GLOBAL DEFAULT   13 _Z5hellov

Since hello is name mangled to _Z5hellov when using g++, we can make sure that g++ will compile *.c file as C++.

(2) Modify main.c to a standard C++ file:

$ cat main.cpp
#include <iostream>

void hello(void)
{
        std::cout << "Hello, world!" << std::endl;
}

int main(void)
{
        hello();
}

Use gcc to compile it:

$ gcc main.cpp
/tmp/cccAb8IH.o: In function `hello()':
main.cpp:(.text+0xa): undefined reference to `std::cout'
main.cpp:(.text+0xf): undefined reference to `std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)'
main.cpp:(.text+0x14): undefined reference to `std::basic_ostream<char, std::char_traits<char> >& std::endl<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&)'
main.cpp:(.text+0x1c): undefined reference to `std::ostream::operator<<(std::ostream& (*)(std::ostream&))'
/tmp/cccAb8IH.o: In function `__static_initialization_and_destruction_0(int, int)':
main.cpp:(.text+0x56): undefined reference to `std::ios_base::Init::Init()'
main.cpp:(.text+0x65): undefined reference to `std::ios_base::Init::~Init()'
collect2: error: ld returned 1 exit status

We can see there are many link errors. The reason is when gcc compiles *.cpp file, it will employ C++ compiler, but it only use defaults C and gcc helpers libraries during linkage stage, and won’t use stdc++ library. Modify the command, then all is OK:

$ gcc main.cpp -lstdc++
$ readelf -s a.out | grep hello
41: 00000000004007f7    21 FUNC    LOCAL  DEFAULT   13 _GLOBAL__sub_I__Z5hellov
59: 0000000000400786    35 FUNC    GLOBAL DEFAULT   13 _Z5hellov

Certainly , since it is a regular C++ file, use g++ will undoubtedly be OK:

$ g++ main.cpp
$ readelf -s a.out | grep hello
41: 0000000000400817    21 FUNC    LOCAL  DEFAULT   13 _GLOBAL__sub_I__Z5hellov
59: 00000000004007a6    35 FUNC    GLOBAL DEFAULT   13 _Z5hellov

(3) Modify the above file name from main.cpp to main.c.

$ cat main.c
#include <iostream>

void hello(void)
{
        std::cout << "Hello, world!" << std::endl;
}

int main(void)
{
        hello();
}

Use g++ to compile it:

$ g++ main.c
$ readelf -s a.out | grep hello
41: 0000000000400817    21 FUNC    LOCAL  DEFAULT   13 _GLOBAL__sub_I__Z5hellov
59: 00000000004007a6    35 FUNC    GLOBAL DEFAULT   13 _Z5hellov

All is OK, and the stdc++ library will be used during linkage stage.

Use gcc instead:

$ gcc main.c
main.c:1:20: fatal error: iostream: No such file or directory

                    ^
compilation terminated.

This error identifies gcc always uses standard C compiler to *.c file, so it can’t find C++ related header files.

P.S. my gcc version:

$ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-pc-linux-gnu/6.3.1/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: /build/gcc-multilib/src/gcc/configure --prefix=/usr --libdir=/usr/lib --libexecdir=/usr/lib --mandir=/usr/share/man --infodir=/usr/share/info --with-bugurl=https://bugs.archlinux.org/ --enable-languages=c,c++,ada,fortran,go,lto,objc,obj-c++ --enable-shared --enable-threads=posix --enable-libmpx --with-system-zlib --with-isl --enable-__cxa_atexit --disable-libunwind-exceptions --enable-clocale=gnu --disable-libstdcxx-pch --disable-libssp --enable-gnu-unique-object --enable-linker-build-id --enable-lto --enable-plugin --enable-install-libiberty --with-linker-hash-style=gnu --enable-gnu-indirect-function --enable-multilib --disable-werror --enable-checking=release
Thread model: posix
gcc version 6.3.1 20170109 (GCC)

 

Resolve “Runtime Error” problem when hackinging in hackerrank

Published / by nanxiao / Leave a Comment

A few days ago, I was trying to resolve the classic maximum subarray conundrum in hackerrankand bumped into an interesting issue. When I submitted the solution, one testcase would fail. But if I ran the testcase individually, the result is right. After discussing in the IRC and Support, it seems the code didn’t pass some memory/time limit constraint in the environment, so I began to optimize my code.

My initial Go code is like this:

package main
import "fmt"
import "math"
import "os"

func MaxNonConArray(s []int) int {
    var max int

    if len(s) < 1 {
        return 0
    }

    for _, v := range s {
        if v > 0 {
            max += v
        }
    }

    if max == 0 {
        max = s[0]
        for _, v := range s[1:] {
            if v > max {
                max = v
            }
        } 
    }
    return max
}

func MaxConArray(s []int) int {
    var max int

    if len(s) > 0 {
        max = s[0]
        currMax := s[0]
        for _, v := range s[1:] {
            currMax = int(math.Max(float64(currMax+v), float64(v)))
            max = int(math.Max(float64(currMax), float64(max)))
        }
    }
    return max
}


func main() {
 //Enter your code here. Read input from STDIN. Print output to STDOUT
    num := 0
    s := [][]int(nil)

    _, err := fmt.Scanf("%d", &num)
    if err != nil {
        os.Exit(1)
    }

    s = make([][]int, num)
    for i := 0; i < len(s); i++ {
        n := 0
        _, err := fmt.Scanf("%d", &n)
        if err != nil {
            os.Exit(1)
        }

        s[i] = make([]int, n)
        for j := 0; j < n; j++ {
            _, err := fmt.Scanf("%d", &s[i][j])
            if err != nil {
                os.Exit(1)
            }
        }
    }

    for i := 0; i < len(s); i++ {
        fmt.Println(MaxConArray(s[i]), MaxNonConArray(s[i]))
    }
}

The main function would allocate a two-dimension slice to accommodate all the input elements. Suddenly I realized a one-dimension slice should be enough, and it could be reused after the wanted value was calculated. So the main code was changed like this:

func main() {
    //Enter your code here. Read input from STDIN. Print output to STDOUT
    var num int

    _, err := fmt.Scanf("%d", &num)
    if err != nil {
        os.Exit(1)
    }

    for i := 0; i < num; i++ {
        var n int
        _, err := fmt.Scanf("%d", &n)
        if err != nil {
            os.Exit(1)
        }

        s := make([]int, n)
        for j := 0; j < n; j++ {
            _, err := fmt.Scanf("%d", &s[j])
            if err != nil {
                os.Exit(1)
            }
        }
        fmt.Println(MaxConArray(s), MaxNonConArray(s))
    }
}

Unfortunately, this time the testcase still can’t pass. So I resorted to C programming language:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int maxNonConSubArray(int *array, int n) {
    int max = 0;

    if (n > 0) {
        for (int i = 0; i < n; i++) {
            if (array[i] > 0) {
                max += array[i];
            }
        }

        if (max == 0) {
            max = array[0];
            for (int i = 1; i < n; i++) {
                if (array[i] > max) {
                    max = array[i];
                }
            }
        }
    }

    return max;
}

int MaxConSubArray(int *array, int n) {
    int max = 0, currMax = 0;

    if (n > 0) {
        max = currMax = array[0];
        for (int i = 1; i < n; i++) {
            currMax = (currMax + array[i]) > array[i] ? (currMax + array[i]) : array[i];
            max = max > currMax ? max : currMax;
        }
    }
    return max;
}

int main() {
    int num = 0;
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    if (scanf("%d", &num) != 1) {
        return 1;
    }

    for (int i = 0; i < num; i++) {
        int n = 0, *array = NULL;

        if (scanf("%d", &n) != 1) {
            return 1;
        }

        array = calloc(n, sizeof(int));
        if (array == NULL) {
            return 1;
        }
        for (int j = 0; j < n; j++) {
            if (scanf("%d", array + j) != 1) {
                return 1;
            }
        }
        printf("%d %d\n",MaxConSubArray(array, n), maxNonConSubArray(array, n));
        free(array);
    }
    return 0;
}

In the C code, I need to manage memory manually, and this time, the testcase didn’t complain, and the submission was success.