Kerninst API Programming Guide

Introduction

This document describes the Kerninst Application Program Interface (KAPI), which allows the programmer to build tools for modifying an OS kernel on the fly. There are many reasons why you may want to do this. To name a few: performance profiling (inject timers at selected locations in the kernel), tracing (insert calls to tracing routines anywhere you want), dynamic code optimization (replace a function with a better-optimized version on the fly).

System Requirements

• UltraSparc I, II, or III processor
• Solaris 7 or 8
• 64-bit sparcv9 and 32-bit sparcv8.
• Uni- and Multiprocessor systems
• GNU Compiler Suite gcc/g++ version 2.95.3.

Overview

A typical KAPI-based system is shown in Figure 1. The end user launches and interacts with a C++-written instrumentation tool to instrument the kernel of a machine on the network. Later, we will refer to this tool as the mutator. The goal of this document is to describe how programmers can write their own mutators.

The mutator translates end user's requests into calls to KAPI. The API itself is represented by two files. The first is a C++ header, kapi.h, which defines the interface available to the mutators. The second file is a C++ library, libkerninstapi.a, which contains the implementation of the interface. Typically, mutators #include kapi.h and link against libkerninstapi.a.

One of the key features of KAPI is support for remote instrumentation. A mutator can run on one machine and instrument another machine's kernel over the network. To support this functionality, the system contains the third component, the Kerninst daemon, or kerninstd. Kerninstd listens for incoming network connections from mutators and performs their instrumentation requests. This structure allows the programmer to offload some costly operations from the machine being instrumented onto the front-end machine running the mutator.

Finally, to implement certain low-level operations that cannot be done from the user space, we install a small kernel driver on a machine being instrumented. This driver creates the /dev/kerninst device node to communicate with kerninstd.

Installation

1. Un-tar the distribution on the target machine
   $ gzip -cd kapi-0.7.0-sparcv9.tar.gz | tar xvf -
2. Install the kernel driver as root
   # cd kapi-0.7.0-sparcv9/bin
   # ./install_driver
3. Run kerninstd as root
   # ./kerninstd
   After it starts, remember the listen port number that kerninstd prints out.
4. Build and run the test tool to count the number of entries to the kmem_alloc function, which is in the genunix kernel module. Provide the host name and the kerninstd port number as arguments.
   $ cd kapi-0.7.0-sparcv9/examples
   $ make
   $ ./count_func "host" "port" genunix kmem_alloc

Simple Example

This section provides a brief overview of the Kerninst programming interface by showing how the count_func tool is implemented. The tool allows the user to monitor how often a particular kernel function is executed. It does this by injecting a small fragment of code at the entry point of the chosen kernel function to increment a counter every time the function is invoked. The implementation of this tool follows a pattern representative of many other instrumentation tools. We summarize the main steps below. See examples/count_func.C for details.

1. The tool attaches to the kernel on the target machine
2. The instrumentation point is located (the entry point to the kmem_alloc function, which is in the genunix module).
3. Space to hold the value of the counter is allocated and initialized to zero.
4. The instrumentation code to increment this counter is generated. Similarly to the Dyninst API, the code here is expressed in the AST (Abstract Syntax Tree) form. The code in the AST form is best visualized as a tree, with intermediate nodes representing the operators in the expression and leaves representing the operands. The post-order traversal of the tree (evaluate children, compute your own value from the children's value) will produce the desired value of the entire expression. Kerninst API provides primitives to construct arbitrary complex expressions. See "Class kapi_snippet and its subclasses" for the complete list of supported code constructs.
5. The generated expression is converted to the machine code and inserted at the point of interest. Whenever the function is entered, the instrumentation code will now be executed.
6. The mutator enters the main loop where it handles events coming from the API and peeks at the value of the counter printing it out every second.

Interface

As mentioned above, KAPI is structured as a collection of C++ classes. Many of these classes directly correspond to the major instrumentation abstractions: kernel modules, functions, basic blocks, instrumentation points, code expressions, kernel memory regions. Naturally, they allow the programmer to query and manipulate the corresponding objects. At the top of the hierarchy is the kapi_manager class that serves both as the object farm and the entry point to the API -- most instrumentation activities are carried out with the help of kapi_manager.

Most methods of KAPI classes are synchronous -- they wait for the requested action to complete. However, there are a few methods that are asynchronous: they initiate an operation and return to the caller immediately. Later on, the caller will be notified of a completion event via a callback. To support the callback functionality, every instrumentation tool has to handle KAPI events periodically. There are several ways this functionality can be integrated in the mutator. See "Handling API Events" for details.

As a general rule, each method that can fail returns an error code of the ierr integer type. Zero corresponds to successful completion, negative values -- to various errors. Below we describe the interface of each API class. Refer to the API header, kapi.h, for further details.

Class kapi_manager

Kapi_manager is the main class in the hierarchy. It is the entry point for most instrumentation activities: allocating/freeing kernel memory, copying to and from kernel memory, browsing through kernel code (locating modules and functions), instrumenting/de-instrumenting, handling instrumentation events, dispatching callbacks.

Initialization/De-initialization

Constructs an uninitialized instance of kapi_manager. Call attach() on this instance to initialize it.

This method attaches kapi_manager to the kernel on a specified machine. All KAPI actions should be carried out only in the attached state.

This method will detach from the kernel, remove remaining instrumentation and perform other clean-up tasks. Typically, it is called on exit from a tool.

Operations on kernel memory

Allocate a region of kernel memory of nbytes bytes. Returns the starting address (integer) of the region. Returns zero if allocation fails.

Free the region starting at addr. Addr should have been previously returned by kapi_manager::malloc(). Returns error code if the free request fails.

Copy nbytes bytes from the kernel space starting at address from_addr, into the user-level buffer specified by the to_addr.

Copy data in the opposite direction (from user to the kernel). Notice the difference in types for kernel and user addresses: kernel addresses are integers, user addresses are pointers.

If the client and the kernel run on architectures with different byte ordering, this routine byte-swaps the provided user data to match the kernel byte ordering.

Similarly to the method above, this routine converts the data copied from the kernel to match byte ordering of the client.

Operations on kernel code structures

Returns the total number of modules loaded in the kernel.

Finds a kernel module with this name. Fills-in the provided *mod object to represent this module in the API. The kapi_module object can be used to locate functions, ... Returns an error code if the module was not found.

Retrieves a vector of all modules in the kernel.

Finds the function starting at addr and initializes *func. Returns an error code if the function was not found.

ierr findModuleAndFunctionByAddress(kptr_t addr,
			            kapi_module *mod, kapi_function *func);

Finds a module which has a function starting at addr. Fills-in both *mod and *func objects. Returns an error code if the function was not found.

Instrumentation-related methods

Inserts the snippet at the specified point in the kernel and return its handle. A positive return value represents a valid snippet handle, negative -- an error encountered.

Removes a previously-inserted snippet. Returns an error code if the handle is invalid.

Uploads a snippet into the kernel, but does not splice it yet. It can later be spliced at any of the given points. The points vector may be empty (which will generate code that can be spliced anywhere) at the expense of having less efficient instrumentation.

Remote a previously-uploaded snippet. Returns an error code if the handle is invalid.

Finds where the snippet has been uploaded. Returns zero if the handle is invalid.

Fills-in the kapi_point object to represent the instrumentation point at the specified kernel address. When instrumenting well-defined points like function entry/exit, it is recommended to use point-location methods of the kapi_function and kapi_basic_block classes instead.

Finds unusual instrumentation points that may be of interest to users: context switch code, system call path, ... Presently, only the switch-in-out points are implemented. Fills-in the provided vector with points found.

Data Sampling

KAPI provides routines for peeking at kernel data at periodic intervals. The following methods implement this functionality.

struct kapi_mem_region {
    kptr_t addr;
    unsigned nbytes;
};

typedef int (*data_callback_t)(unsigned reqid, uint64_t time_of_sample,
                               const uint64_t *sampled_values, unsigned numvalues);

Starts copying memory from the kernel periodically, every ms milliseconds. Returns the request handle. The memory to sample is specified as a set of disjoint regions of type kapi_mem_region. When a sample arrives, the provided "cback" callback will be invoked with the contents of the regions concatenated in one vector. We assume that we are sampling a collection of 64-bit integers, so the data is converted accordingly if the daemon and the client run on different architectures. If ms is zero then sample just once.

Stops the sampling request given a handle. Returns an error code if the handle is invalid.

Changes the sampling interval for a given request to new_ms. Two special cases: if new_ms is zero we stop sampling. If old_ms was 0 and new_ms is non-zero we start sampling. Returns an error code if the handle is invalid.

Handling API events

To support the callback functionality, the API needs to receive control periodically and handle pending events. The programmer's responsibility is to wait or poll to see if there are any events to be handled and invoke the handleEvents() method if so.

Handle pending events

KAPI provides two different ways to wait for incoming events: waitForEvents() and getEventQueueDescriptor()/select(). You can use a way, which better fits your application structure.

Waits for incoming events (callbacks and data samples). timeoutMilliseconds specifies the maximum amount of time you want to wait (set it to 0 if you do not want to block or to UINT_MAX to wait forever). Returns 1 if events are pending, 0 if timed out, < 0 on error.

Alternative way of waiting for events. Returns a file descriptor that you can add to read_fds and error_fds and call select() on them.

Handling Indirect Calls

The code analysis framework of KAPI allows the programmer to walk the static call graph of the kernel by starting at a top-level function, descending into its callees, and so on. See kapi_function::getCallees() for details. Unfortunately, kernel code is full of indirect calls, which targets are not known in advance. As a result, the static approach of kapi_function::getCallees() may not be able to find all callees.

Fortunately, KAPI provides primitives for discovering such callees at run time by instrumenting the corresponding call sites and snooping on destination addresses as the calls are made. To use this feature, the programmer needs to install a watchpoint on a callsite of interest with watchCalleesAt(addr), let the kernel run for a while, remove the watchpoint with unWatchCalleesAt(addr) and retrieve the accumulated callee information with getCalleesForSite().

Collect callee addresses for a given callsite of an indirect call. Use kapi_function::getCallees() to find such callsites for a given function.

Stop collecting callee addresses for a given callsite

Fill-in the supplied vectors with callee addresses and execution counts collected so far. The callsite must be in the unwatched state or this method will return an error

Support for disassembly

KAPI provides some support for code disassembly. The programmer can disassemble a function, a basic block or an arbitrary region of code. The results are returned as an instance of kapi_disass_object, which is a collection of kapi_disass_chunk instances. Each kapi_disass_chunk represents disassembly of a contiguous region of code and is a collection of kapi_disass_insn objects. Finally, a kapi_disass_insn object contains textual representation of disassembly results for an individual instruction.

Disassembles a function or a basic block within the function. Fills-in the provided kapi_disass_object. Set bbid to bbid_t(-1) to disassemble the entire function. Can disassemble either the current, possibly instrumented, function or the original image, before any instrumentation took place.

Disassembles the specified range of addresses and fills-in the disass object

Class kapi_module

This class represents a kernel module -- a logically-connected group of functions. We assume that the entire kernel is made of kernel modules, which is true of Solaris.

Constructs an uninitialized instance of kapi_module. The instance will be filled-in by the parent class kapi_manager (via findModule)

Fills-in the module name. Returns not_enough_space if the actual module name is longer than max_len_bytes.

Some modules have short descriptions defined for them. This method fills-in the module description, if any, into desc. Returns not_enough_space if the actual module description is longer than max_len_bytes.

Returns the number of functions in the module

Finds a function with this name in the module and fills-in *func. Returns an error code if the function was not found.

Fills-in a vector of all functions in the module

Class kapi_function

This class corresponds to a kernel function. It allows the programmer to navigate through function's resources: basic blocks and instrumentation points.

Constructs an uninitialized instance of a kapi_function object. The instance should be filled-in later via calls to kapi_module::findFunction, kapi_manager::findFunctionByAddress, or kapi_manager::findModuleAndFunctionByAddress.

Returns the address of the function's entry point

Fills-in the function name. Returns not_enough_space if the actual name is longer than max_len_bytes.

Returns the number of basic blocks in the function

Finds the basic block starting at addr and fills-in *bb. Returns an error code if no basic block starts at addr.

Within the function, all basic blocks are enumerated (0 to N). This method fills-in *bb given it sequential id. Returns an error code if bbid is greater than N.

Converts the starting address of a basic block into its sequential id. Returns bbid_t(-1) if no basic block starts at addr.

Fills-in a vector of all basic blocks in the function.

Fills-in a vector of entry points of the function. Typically, this vector contains only one element.

Fills-in a vector of exit points of the function. Contrary to the entry point, this vector can easily contain more than one element.

Some functions can not be analyzed and hence instrumented at this time. Attempts to instrument them will return an error.

There can be several names mapping to the same address. This method returns the number of aliases, including the primary name.

Fills-in the ialias^th alias name into buffer. Returns an error code if there is no such alias or if there is not enough space to store its name.

ierr getCallees(const kapi_vector<bbid_t> *blocks,
		kapi_vector<kptr_t> *regCallsFromAddr,
		kapi_vector<kptr_t> *regCallsToAddr,
		kapi_vector<kptr_t> *interprocBranchesFromAddr,
		kapi_vector<kptr_t> *interprocBranchesToAddr,
		kapi_vector<kptr_t> *unanalyzableCallsFromAddr) const;

Finds and reports all callees of this function. For each call we try to determine its source address (the address of the call instruction) as well as its destination address (the address of the callee). Both regular calls, indirect calls (unanalyzableCallsFromAddr) and interprocedural branches are located. If the blocks argument is not NULL, only calls made in these basic blocks are reported. See "Handling Indirect Calls" for information on how to discover targets of indirect calls.

Class kapi_basic_block

This class represents a basic block of kernel code.

Constructs an uninitialized instance of the basic block object. The instance should be filled-in later via calls to kapi_function::findBasicBlock or kapi_function::findBasicBlockById.

Returns the start address of the basic block

Returns the address after the last instruction in the basic block.

Returns the exit address of the block. Basically, you need to insertSnippet at that address to catch the exit from the block. Thanks to delay slots, it may or may not correspond to the last instruction in the block.

Class kapi_point

This class represents an instrumentation point -- location in the kernel code where we can insert instrumentation.

Creates an uninitialized instance of the kapi_point object. The instance should be filled-in later via calls to kapi_function::findEntryPoint, kapi_manager::createInstPointAtAddr and such.

Returns the address at which the instrumentation will be inserted.

Class kapi_snippet and its subclasses

kapi_snippet is the base class of every instrumentation code construct in KAPI. This class is seldom used directly. Typically, an appropriate subclass is used instead.

Class kapi_const_expr

This class represents a constant integer expression with value val.

Class kapi_int_variable

This class represents a 64-bit integer variable in the kernel space.

Declares a variable stored at the pre-allocated kernel address specified by addr. Use kapi_manager::malloc(sizeof(kapi_int_t)) to allocate space first.

Declares an integer scalar variable v[index], which is an element of a vector, starting at address v. The exact location of the variable is determined at run time after the index expression is evaluated.

Declares an integer variable, which location is specified by addr_expr and will be known only at run time.

Class kapi_arith_expr

This class allows the programmer to construct binary arithmetic expressions.

Declares a binary expression, combining the values of lOpd and rOpd with the operation specified by "kind". The following binary operations are currently supported.

enum kapi_arith_operation {
    kapi_plus,
    kapi_minus,
    kapi_times,
    kapi_divide,
    kapi_bit_and,
    kapi_bit_or,
    kapi_shift_left,
    kapi_shift_right,
    kapi_atomic_assign,
    kapi_assign
};

Class kapi_sequence_expr

This class the programmer to chain multiple expressions together.

Declares a sequence expression. Expressions in the exprs vector will be evaluated in the order they are stored in the vector.

Class kapi_bool_expr

This class allows the programmer to construct boolean expressions.

Declares a constant boolean expression, with a given value

Declares a binary boolean expression, which applies relation "kind" to the values of lOpd and rOpd. The following relations are currently supported.

enum kapi_relation {
    kapi_lt,
    kapi_eq,
    kapi_gt,
    kapi_le,
    kapi_ne,
    kapi_ge,
    kapi_log_and,
    kapi_log_or
};

Class kapi_if_expr

This class allows the programmer to construct if-then and if-then-else expressions.

Declares an if-then expression. The boolean cond expression is used to decide if trueClause should be executed.

Declares an if-then-else expression. The boolean cond expression is used to decide whether to execute the trueClause or the falseClause expression.

Class kapi_param_expr

Declares an expression with value equal to the n^th parameter of a function being instrumented. The first parameter corresponds to n equal to zero. This snippet type is valid only at points that are entries to subroutines.

Class kapi_retval_expr

Declares an expression with value equal to the return value of a func, which is being instrumented. This snippet type is valid only at points that are exits from subroutines.

Class kapi_call_expr

Declares a call expression to call a function starting at entryAddr and pass given arguments to it.

Class kapi_ret_expr

Declares a return statement, which is useful for generating subroutines on the fly. Do not confuse this statement with kapi_retval_expr.

Class kapi_hwcounter_expr

Declares an expression equal to the value of a hardware counter at the moment of evaluation. The following hardware counters are currently supported.

typedef enum {
    HWC_NONE = 0, // No counter selected
    HWC_TICKS = 1, // Processor cycle counter
    HWC_DCACHE_VREADS = 2, // The number of D-cache read references
    HWC_DCACHE_VWRITES = 3, // The number of D-cache write references
    HWC_DCACHE_VREAD_HITS = 4, // D-cache read hits
    HWC_DCACHE_VWRITE_HITS = 5, // D-cache write hits
    HWC_ICACHE_VREFS = 6, // Instruction cache references
    HWC_ICACHE_VHITS = 7, // Instruction cache hits
    HWC_ICACHE_STALL_CYCLES = 8, // Cycles stalled handling I-cache misses
    HWC_BRANCH_MISPRED_VSTALL_CYCLES = 9, // Cycles stalled handling branch mispredictions
    HWC_ECACHE_VREFS = 10, // L2 cache references
    HWC_ECACHE_VHITS = 11, // L2 cache hits
    HWC_ECACHE_VREAD_HITS = 12, // L2 cache read hits
    HWC_VINSNS = 13 // The number of instructions completed
} kapi_hwcounter_kind;

Note: accessing hardware counters through KAPI is a two-step process. First, a counter should be selected in the CPU. See the kapi_hwcounter_set class for directions on how to do that. Second, the instrumentation code that accesses the counter is generated visa kapi_hwcounter_expr and inserted in the kernel.

Measuring wall-clock time is quite easy with the kapi_hwcounter_expr described above. However, when measuring CPU time, one has to exclude the time that accumulated while the thread was blocked. To implement virtualized timers, we need to stop the timer on context switch out: when the thread that started the timer is being preempted. Later, we need to restart the timer, when the thread is being switched back in. Luckily, KAPI already provides some support for virtualized timers.

To use virtualized timers provided by KAPI, the programmer needs to follow a four-step process. First, a timer instance should be allocated in the kernel memory. It should then be initialized following a well-defined layout. Second, the timer address should be appended to the all_vtimers vector in the kernel space. If the vector does not exist yet, it should be allocated and properly initialized. Third, the context switch points should be located via kapi_manager::findSpecialPoints. Instances of kapi_vtimer_cswitch_expr should be inserted at all these points. Finally, the timer start/stop code should be generated and inserted into a function of interest. Refer to vtimer_example.C for further details.

Class kapi_vtimer_cswitch_expr

Declares an expression that saves/restores virtual timers on switch-out/switch-in. It uses the address of the all_vtimers vector to locate the timers that need stopping/restarting. This expression should be inserted both at context switch-out points (ptype = kapi_cswitch_out) and context switch in (ptype = kapi_cswitch_in)

Class kapi_cpuid_expr

Declares an expression that evaluates to the id of the CPU that executed this code.

Class kapi_pid_expr

Declares an expression that evaluates to the process id of the executing thread. Kernel threads have pid of zero.

Class kapi_vector

This class is a container used to hold objects used by the API. It provides a small subset of the STL vector interface and serves as an intermediary between the programmer and the internal vector representation in KAPI.

Creates an empty vector.

Appends item to the end of the vector

Returns the number of elements in the vector

Returns a reference to the i^th element of the vector.

Return iterators to the start and end of the vector.

Remove all elements from the vector

Class kapi_hwcounter_set

This class represents and manipulates the set of hardware counters currently selected in the CPU.

Constructs an empty counter set. Notice that it does not match the current state of counters in the CPU. See readConfig().

Synchronizes the set with the processor state by reading what counters are actually enabled there.

Inserts a counter in the set. Since the number of active counters is typically limited and some counters conflict with each other, the insertion may force another counter out of the set. The old value is returned. Notice that the insert() method does not change the state of counters in the CPU -- all changes need to be committed with a later writeConfig().

Removes the counter from the set

Checks to see if the given counter can be enabled with no conflicts: without forcing another counter from the set.

Writes the current selection of counters into the CPU state.

Class kapi_disass_object

This class is the top-level interface to disassembly. It represents a collection of kapi_disass_chunks.

Constructs an uninitialized disassembly object. Use kapi_manager::getDisassObject to populate it.

Return iterators to the start/end of the kapi_disass_chunk collection.

Class kapi_disass_chunk

This class represents a collection of kapi_disass_insns. It should not be constructed directly -- kapi_disass_object does that for you.

Return iterators to the start/end of the kapi_disass_insn collection.

Class kapi_disass_insn

This class contains textual representation of a disassembled instruction. It should not be constructed directly -- kapi_disass_chunk does that for you.

Returns the textual representation of the instruction

Returns the binary representation of the instruction

Returns the size of the binary representation

True iff insn is a call and we know its destination

If the instruction is a call, this method returns the name of the function it is calling