ktap: add tools/ktap/README.md file

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add ktap tutorial(tools/ktap/doc/tutorial.md)

This is detail documentation for ktap users, it contains:

- Basic introduction
- Requirements
- Language Syntax basics
- Built-in functions, libraries and variables
- Simple samples
- Design decision
- References

This tutorial is still keeping update, it would be a good
guide for ktap.

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add sample scripts(tools/ktap/samples/*)

The samples directory is organized by different subsystems,
similar with Dtrace toolkit(http://www.brendangregg.com/dtracetoolkit.html)

It contains:
- helloworld.kp: simple hello world program
- ansi: ansi library for screen display
- basic: some simple examples
- game: tetris game wrote by ktap
- interrupt: collect hardirq and softirq time
- io: open and io related scripts
- mem: kernel memory allocation scripts
- network: networking scripts
- profiling: stack profile and function profile
- schedule: schedule scripts.
        schedtimes.kp was inspired by Systemtap schedtimes.stp
- syscalls: tracing syscalls
        syslatl.kp/opensnoop.kp/syslist.kp was contributed by Brendan Gregg(from Dtrace toolkit)
- tracepoints: kernel tracepoint count and histogram
- userspace: uprobe(include SDT) scripts

Besides these samples, "ktap Examples" posted by Brendan Gregg
(http://www.brendangregg.com/ktap.html) also have many sample
scripts, he mentioned how to can make flame graph by ktap.

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add basic ktap types definition(include/uapi/ktap/ktap_types.h)

File 'include/ktap_types.h' is the basestone for ktap runtime
and userspace tool, it contains key structure definition for ktap.

1. ktap_val_t
   ktap_val_t is ktap value representaion in stack, and for object
   reference. Each value have a type, the type could be:
        nil, false, true, number, string, upval, proto, func,
        table, eventstr, kstrace, kip, uip.

   ktap_val_t structure occupy 16 bytes in x86_64.

2. ktap_number
   number type in ktap, it is 'long'.

3. ktap_str_t
   String type. All string in ktap is interned, it means ktap keeps
   a single copy for any string. Whenever a new string appears, ktap
   checks whether it already has a copy of that string and, if so,
   reuses that copy. Internalization makes operations like string
   comparison and table indexing very fast, but it slows down string creation.

   String is allocated from mempool(runtime/kp_mempool.c), not allocated
   by kmalloc, because we don't want dynamic allocate string in probe
   context.

   Real string buffer is appended after ktap_str_t.

4. ktap_proto_t
   prototype structure for ktap function.

5. ktap_upval_t
   The concept of upval is get from lua.
        var a = 1
        function f() {
                print(a)   <--- 'a' is upval in 'f'.
        }

6. ktap_func_t
   Instance of ktap_proto_t, also can be called as 'closure', it's
   created for each function prototype in runtime.
   ktap_func_t contains upvals array for access variables in upper
   scope layer.

7. ktap_tab_t
   ktap table(associative array) structure, it contains array part
   and hash part.
   Table is pre-allocated by vmalloc, table is not allowed to resize,
   it will report overflow when entries full.

8. ktap_state_t
   ktap context structure.
   There have many context in ktap runtime:
   1). mainthread conetxt
      mainthread context is the context in ktap thread.
   2). probe context
      ktap runtime pre-allocated percpu probe context.

9. ktap_global_state_t
   global state of ktap runtime, it's access by G(ks).

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add bytecode definition(include/uapi/ktap/ktap_bc.h)

ktap bytecode is based on luajit, a fast JIT for lua language.

There have a good detail introduction about luajit bytecode in
http://wiki.luajit.org/Bytecode-2.0

A single bytecode instruction is 32 bit wide and has an 8 bit
opcode field and several operand fields of 8 or 16 bit.
Instructions come in one of two formats:

 +----+----+----+----+
 | B  | C  | A  | OP | Format ABC
 +----+----+----+----+
 |    D    | A  | OP | Format AD
 +--------------------
 MSB               LSB

In-memory instructions are always stored in host byte order.

E.g. 0xbbccaa1e is the instruction with opcode 0x1e (ADDVV),
with operands A = 0xaa, B = 0xbb and C = 0xcc.

Bytecods:

1). Comparison ops
ISLT, ISGE, ISLE, ISGT, ISEQV, ISNEV, ISEQS, ISNES, ISEQN,
ISNEN, ISEQP, ISNEP

2). Unary Test and Copy ops
ISTC, ISFC, IST, ISF

3). Unary ops
MOV, NOT, UNM, LEN

4). Binary ops
ADDVN, SUBVN, MULVN, DIVVN, MODVN, ADDNV, SUBNV, MULNV, DIVNV, MODNV,
ADDVV, SUBVV, SUBVV, MULVV, DIVVV, MODVV, POW, CAT

5). Constant ops
KSTR, KCDATA, KSHORT, KNUM, KPRI, KNIL

6). Upvalue and Function ops
UGET, USETV, USETS, USETN, USETP, UCLO, FNEW

7). Table ops
TNEW, TDUP, GGET, GSET, TGETV, TGETS, TGETB, TSETV, TSETS, TSETB, TSETM

8). Calls and Vararg Handling (ktap do not support variable argument now)
CALLM, CALL, CALLMT, CALLT, ITERC, ITERN, VARG, ISNEXT

9). Returns (ktap don't support RETM now)
RETM, RET, RET0, RET1

10). Loops and branches (loop bytecode J* is not used in ktap)
FORI, JFORI, FORL, IFORL, JFORL, ITERL, IITERL, JITERL, LOOP, ILOOP, JLOOP, JMP

11). Function headers (All is not used in ktap)
FUNCF, IFUNCF, JFUNCF, FUNCV, JFUNCV, FUNCC, FUNCCW

12). ktap specific bytecodes
VARGN, VARGSTR, VPROBENAME, VPID, VTID, VUID, VCPU, VEXECNAME, GFUNC

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add ktap_arch.h and error header file(include/uapi/ktap/)

Simple arch related definition and error msg definition.

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add kernel module main entry(kernel/trace/ktap/ktap.[c|h])

ktap.c is ktapvm kernel module main entry,
it init ktap kernel module, create 'ktap' debugfs directory.

Userspace tool send ioctl command to '/sys/kernel/debug/ktap/ktapvm' file,
to control ktap runtime.

It will read bytecode trunk, validate and execute bytecode.

kp_vm_new_state
    kp_bcread
        kp_vm_validate_code
            kp_vm_call_proto

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add bytecode reader(kernel/trace/ktap/kp_bcread.[c|h])

Exposed function:
ktap_proto_t *kp_bcread(ktap_state_t *ks, unsigned char *buff, int len)

Function kp_bcread read bytecode from buff, and return
ktap top-level function prototype.

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add bytecode execution engine(kernel/trace/ktap/kp_vm.[c|h])

kp_vm.c is ktap runtime execution engine, it execute
all bytecodes and handle core vm stuff.

Exposed functions:

1). kp_vm_new_state:    allocate and init main context.
2). kp_vm_exit:         ktap main thread exit
3). kp_vm_register_lib: library and built-in functions register interface
4). kp_vm_validate_code:validate bytecode before execute
5). kp_vm_call:         dispatch and execute bytecode, called from probe context
6). kp_vm_call_proto:   called with a new proto, called when start.

ktap runtime pre-allocate context(ktap_state_t) for each cpu and
each probe context(process, irq, sirq, nmi), and pre-allocate
ktap stack memory for each ktap_state.

The key function is kp_vm_call, it dispatch and execute bytecodes.
Computed goto is used for fast dispatch instead of big switch.
All bytecode check its type in runtime, it will return if type mismatch.

Hotloop is checked when execute loop related bytecode, to forbid
deadloop, it limit can be set by module parameter.

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add string handling code(kernel/trace/ktap/kp_[str|mempool].[c|h])

Exposed functions:

1). kp_str_new:
        Return a interned string, failure if out of memory
        or exceed max string number(default 9999).
        It allocate memory from mempool, not kmalloc, because we
        don't want dynamic allocate string in probe context.

2). kp_str_resize:
        Initizate interned hash table g->strhash.

3). kp_str_fmt:
        Return a format string, called from 'printf' built-in function.

4). kp_mempool_init/kp_mempool_destroy/kp_mempool_alloc
        mempool is only service for string allocation currently.

All string in ktap is interned, it means ktap keeps
a single copy for any string. Whenever a new string appears, ktap
checks whether it already has a copy of that string and, if so,
reuses that copy. Internalization makes operations like string
comparison and table indexing very fast, but it slows down string creation.

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add table handling code(kernel/trace/ktap/kp_tab.[c|h])

ktap table is associative array, you can put any key value into
table and store any type value, for example:

var s = {}
s[1] = 1  <-- store number key and number value
s["key"] = "value"  <-- store string key and string value
s["key2"] = 1    <--- store string key and number value

Exposed functions:

1). kp_tab_new
        return a new allocated table
2). kp_tab_dup
        return a new allocated table with template table.
3). kp_tab_free
        free a table
4). kp_tab_clear
        clear entires of a table, not delete ktap_tab_t structure.
5). kp_tab_getint/kp_tab_setint/kp_tab_incrint
        get/set/inc with a int key
6). kp_tab_getstr/kp_tab_setstr/kp_tab_incrstr
        get/set/inc with a string key
7). kp_tab_get/kp_tab_set/kp_tab_incr
        get/set/inc with a key(variable type)
8). kp_tab_next
        table iterator
9). kp_tab_len
        return length of a table
10).kp_tab_print_hist
        print histogram of a table(value must be number)

All table operation is protect by spinlock.
Table cannot be resize, ktap runtime will report error once table
overflow.

ktap table performance is good, benchmark show that ktap table
operation performance is better than systemtap, especially
for string key(because all string is interned in ktap).

Note table is not aggregation in Systemtap and Dtrace, aggregation
use percpu buffer. ktap will introduce aggregation soon with
Dtrace aggregation syntax.

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add generic object handling code(kernel/trace/ktap/kp_obj.[c|h])

kp_obj.c include some common ktap object operation,
like object dump, object length.
It also include generic memory allocate code.

Exposed functions:
1). kp_malloc/kp_zalloc/kp_free

2). kp_obj_dump/kp_obj_show

3). kp_obj_rawequal

4). kp_obj_len

5). kp_obj_new
        allocate new object, all object is linked in G(ks)->allgc.

6). kp_obj_kstack2str
        convert kernel stack to string.

7). kp_obj_freeall
        free all object, called in kp_vm_exit.

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add ring buffer handling code(kernel/trace/ktap/kp_transport.[c|h])

ktap transport functionality is based on ftrace ring buffer.

All contents generated by ktap runtime will send to userspace
through this ring buffer.

Actually the concept of ktap transport is similar with ftrace,
for example, it will write event binary data into ring buffer
when use call: 'print(argstr)' or 'print(stack())', and the content
will be parse in consumer side, not producer side.

Userspace reader thread will consume content in ring buffer through
'/sys/kernel/debug/ktap/trace_pipe_$pid'

A lot of code in this file is duplicated with kernel trace_output.c.

Exposed functions:
1). kp_transport_init
2). kp_transport_exit
3). __kp_bputs/__kp_puts/kp_printf
4). kp_transport_write
5). kp_transport_event_write
        write a event content into ring buffer, called by: 'print(argstr)'
6). kp_transport_print_kstack
        write a kernel stack into ring buffer, called by: 'print(stack())'

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add events management(kernel/trace/ktap/kp_events.[c|h])

kp_events.c handle ktap events management(registry, destroy, event callback)

This file is core event management interface between ktap and kernel.

Exposed functions:
1). kp_events_init/kp_events_exit

2). kp_event_create_kprobe
        create kprobe event, for example:
                kdebug.kprobe("SyS_futex", function () {})

3). kp_event_create_tracepoint
        create tracepoint event, for example"
                kdebug.tracepoint("sys_futex_enter", function () {})

4). kp_event_create
        create perf backend event, for example:
                trace sched:sched_switch { print(argstr) }

        It call kernel function 'perf_event_create_kernel_counter' to
        register event(tracepoint/kprobe/uprobe)

5). kp_event_getarg
        get argument of event, from arg0 to arg9,
        only can be called in probe context.
                trace sched:sched_switch { print(arg0, arg1) }

6). kp_event_stringify/kp_event_tostr
        stringify argstr, sometimes if store argstr as key to table,
        then it need to stringify firstly, like below:
                var s={} trace sched:sched_switch { s[argstr] += 1 }
        (This is quite rare usage, but ktap support it)

Note:
Why ktap support 'kdebug.kprobe' and 'kdebug.tracepoint' when
it already support perf backend event(trace xxx {})?

Because benchmark shows raw kprobe and tracpoint interface is faster
than perf backed tracing, nearly 10+%, it's more fair to compare
with Systemtap by raw tracing syntax, not perf backend tracing.

perf backend tracing have a long code path before reach ktap callback,
and it need to copy event buffer firstly.

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add built-in functions and library(kernel/trace/ktap/lib_*.c)

ktap register built-in functions and library into table.

1). Built-in functions(lib_base,c):

print, printf, print_hist, pairs, len, delete, stack,
print_trace_clock, num_cpus, arch, kernel_v, kernel_string,
user_string, stringof, ipof, gettimeofday_ns, gettimeofday_us,
gettimeofday_ms, gettimeofday_s, curr_taskinfo, in_iowait,
in_interrupt, exit.

2). Ansi library(lib_ansi.c):

ansi.clear_screen
ansi.set_color
ansi.set_color2
ansi.set_color3
ansi.reset_color
ansi.new_line

3). kdebug library(lib_kdebug.c):

kdebug.trace_by_id
kdebug.trace_end
kdebug.tracepoint
kdebug.kprobe

4). net library(lib_net.c):

net.ip_sock_saddr
net.ip_sock_daddr
net.format_ip_addr

5). table library(lib_table.c):

table.new

6). timer library(lib_timer.c):

timer.profile
timer.tick

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add amalgamation build(kernel/trace/ktap/amalg.c)

This compiles the ktapvm as one huge C file and allows
GCC to generate faster and shorter code.

No amalgamation build in x86_64:
ktapvm.ko: 3.1M

amalgamation build in x86_64:
ktapvm.ko: 1.1M

User can set use amalgamation build or not in Makefile.

(Need to analyze further why have so big differences)

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add Makefile for kernel module(kernel/trace/ktap/Makefile)

This Makefile compiles kernel module and generate ktapvm.ko.

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add Kconfig(kernel/trace/ktap/Kconfig)

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add main file for ktap binary(tools/ktap/kp_main.c)

Main entry for userspace ktap tool.

[root@localhost ktap]# ./ktap
Usage: ktap [options] file [script args] -- cmd [args]
   or: ktap [options] -e one-liner  -- cmd [args]

Options and arguments:
  -o file        : send script output to file, instead of stderr
  -p pid         : specific tracing pid
  -C cpu         : cpu to monitor in system-wide
  -T             : show timestamp for event
  -V             : show version
  -v             : enable verbose mode
  -q             : suppress start tracing message
  -d             : dry run mode(register NULL callback to perf events)
  -s             : simple event tracing
  -b             : list byte codes
  -le [glob]     : list pre-defined events in system
  -lf DSO        : list available functions from DSO
  -lm DSO        : list available sdt notes from DSO
  file           : program read from script file
  -- cmd [args]  : workload to tracing

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>
ktap: add compiler(tools/ktap/kp_[lex|parse].[c|h])

ktap compiler is based on luajit, origin forked from lua.

The compiler use one pass compilation, it is very fast, and
the generated binary is very small.

[root@localhost ktap]# ll -h ktap
-rwxr-xr-x. 1 root root 83K Mar 27 06:09 ktap

The compiler is easy to hack, the code is very easy to understand.

Note that some bytecode in luajit is not used by ktap, it could
be remove in future.

More compiler hack soon:
1). aggregation
	@name[keys] = aggfunction(args)

2). multi-key table
	var s = {}
	s[key1, key2, key3] = value

3). C structure access

Signed-off-by: Jovi Zhangwei <jovi.zhangwei@gmail.com>