[RFC/FYI] reliable markers (hooks/probes/taps/...)

[RFC/FYI] reliable markers (hooks/probes/taps/...)

[Werner Almesberger]

A while ago, there was some discussion on various mechanisms for
inserting taps for debuggers, tracing, security monitors, etc.
into the kernel.

Here's a pretty light-weight approach I call "reliable markers":

 - they provide only the code locations, the rest is up to the
   debugger (or such)
 - gcc won't move them out of the code path (unlike C labels)
 - they force arguments to be where gcc says they are (in the
   DWARF2 information)
 - markers in inline functions get replicated, so one can easily
   set breakpoints
 - zero overhead if disabled at compile-time
 - relatively small overhead if enabled at compile time (uses a
   memory clobber which constrains optimizations, no other code
   or run-time data is added)

I'm using them for umlsim, http://umlsim.sourceforge.net/
The umlsim control process reads the usual DWARF2 debugging
information, and can then also do things like:

 - set breakpoints, a bit like kprobes
 - call functions in the kernel (usually from the idle task)
 - force a function to return
 - read and write arguments and variables

Below is a patch with the markers and two usage examples in the
kernel. On the umlsim side (uses a Perl/C-ish script language),
they would be used like this:

run/ping-peek.umlsim:

...
$brk_a_out = break($a.daemon_write.entry);	<--- breakpoint
...
        $pkt = $grab_outgoing_packet();		(see below)
        $enqueue($$,$pkt,$delay);
        $$.return (*skb)->len;			<--- return from function
...

include/nettap.umlsim:

global $grab_outgoing_packet = function
{
    return (unsigned char [(*skb)->len]) (*skb)->data; <-- access arg & var
};

umlsim is still in its infancy, but this should illustrate how
much can be done with such simple breakpoint support, plus the
debugging information gcc already provides.

- Werner

---------------------------------- cut here -----------------------------------

--- /dev/null	Thu Aug 30 17:30:55 2001
+++ linux-2.5.66/include/linux/markers.h	Thu Apr  3 03:51:22 2003
@@ -0,0 +1,55 @@
+/*
+ * include/linux/markers.h - Reliable code markers (labels)
+ *
+ * Written 2003 by Werner Almesberger, Caltech Netlab FAST project
+ */
+
+#ifndef _LINUX_MARKERS_H
+#define _LINUX_MARKERS_H
+
+#include <linux/config.h>
+
+#ifdef CONFIG_MARKERS
+
+/*
+ * __MARKER(name) generates an entry in the ".dbg_markers" section with the
+ * following content:
+ *
+ * Offset Length (bytes)
+ *    0     4	marker address
+ *    4     4	pointer to function name (__func__) in .rodata
+ *    8    >1	file name (\0-terminated)
+ *   var.  0-3	padding bytes (all zero, to speed up searches)
+ *   var.  >1	label name (\0-terminated)
+ *   var.  0-3	padding bytes (all zero, to speed up searches)
+ */
+
+
+#define __MARKER(name) \
+  __asm__ __volatile__( \
+    "1:\n" \
+    "\t.pushsection .dbg_markers,\"\",@progbits\n" \
+    "\t.long 1b\n" \
+    "\t.long %0\n" \
+    "\t.asciz \"" __FILE__ "\"\n" \
+    "\t.align 4,0\n" \
+    "\t.asciz \"" #name "\"\n" \
+    "\t.align 4,0\n" \
+    "\t.popsection\n" : : "m" (*__func__) : "memory")
+
+/*
+ * MARKER protects __MARKER against multiple uses of the same marker name
+ * within the same function.
+ */
+
+#define MARKER(name) \
+  do { __marker_##name: __attribute__((unused)) \
+       __MARKER(name); } while (0)
+
+#else /* CONFIG_MARKERS */
+
+#define MARKER(name)
+
+#endif /* !CONFIG_MARKERS */
+
+#endif /* _LINUX_MARKERS_H */
--- linux-2.5.66/net/core/dev.c.orig	Thu Apr  3 03:17:21 2003
+++ linux-2.5.66/net/core/dev.c	Thu Apr  3 04:24:40 2003
@@ -107,6 +107,7 @@
 #include <linux/kmod.h>
 #include <linux/module.h>
 #include <linux/kallsyms.h>
+#include <linux/markers.h>
 #ifdef CONFIG_NET_RADIO
 #include <linux/wireless.h>		/* Note : will define WIRELESS_EXT */
 #include <net/iw_handler.h>
@@ -1471,6 +1472,7 @@
 	int ret = NET_RX_DROP;
 	unsigned short type = skb->protocol;
 
+	MARKER(entry);
 	if (!skb->stamp.tv_sec)
 		do_gettimeofday(&skb->stamp);
 
--- linux-2.5.66/arch/um/Kconfig.orig	Thu Apr  3 03:50:05 2003
+++ linux-2.5.66/arch/um/Kconfig	Thu Apr  3 04:20:43 2003
@@ -363,5 +363,29 @@
         If you're involved in UML kernel development and want to use gcov,
         say Y.  If you're unsure, say N.
 
+config UMLSIM
+	bool "Enable umlsim support"
+	default n
+	help
+	umlsim uses a UML kernel for event-driven simulations. This
+	option adds code to support virtual time (boot command-line
+	option 'vtime'), and to inform the umlsim control program
+	when the kernel is idle.
+
+	A kernel containing umlsim support can also be used without
+	virtual time and umlsim.
+
+	See <http://umlsim.sourceforge.net/> for more details.
+
+config MARKERS
+	bool "Enable reliable markers"
+	default UMLSIM
+	help
+	Reliable markers are used to mark potential breakpoint locations.
+	Debuggers (or debugger-like programs, such as umlsim) need
+	specific code if they want to use reliable markers.
+
+	If you're not using umlsim, you probably want to say N. If you're
+	using this kernel with umlsim, say Y.
 endmenu
 
--- linux-2.5.66/arch/um/drivers/daemon_kern.c.orig	Thu Apr  3 04:26:47 2003
+++ linux-2.5.66/arch/um/drivers/daemon_kern.c	Thu Apr  3 04:31:10 2003
@@ -9,6 +9,7 @@
 #include "linux/init.h"
 #include "linux/netdevice.h"
 #include "linux/etherdevice.h"
+#include "linux/markers.h"
 #include "net_kern.h"
 #include "net_user.h"
 #include "daemon.h"
@@ -54,6 +55,7 @@
 static int daemon_write(int fd, struct sk_buff **skb,
 			struct uml_net_private *lp)
 {
+	MARKER(entry);
 	return(daemon_user_write(fd, (*skb)->data, (*skb)->len, 
 				 (struct daemon_data *) &lp->user));
 }

-- 
  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina         wa@almesberger.net /
/_http://www.almesberger.net/____________________________________________/

Re: [RFC/FYI] reliable markers (hooks/probes/taps/...)

[Werner Almesberger]

I wrote:
> Here's a pretty light-weight approach I call "reliable markers":

Turns out that the memory clobber didn't make them particularly
reliable. Here's a better version. Usage:

MARKER(label_name,var...);

Where var... is an optional comma-separated list of arguments or
variables that may be accessed (read or modified) while at this
breakpoint.

(This is just for demonstration. For serious use, one would generate
a markers.h that can handle more than just four arguments.)

- Werner

---------------------------------- cut here -----------------------------------

--- /dev/null	Thu Aug 30 17:30:55 2001
+++ linux-2.5.66/include/linux/markers.h	Fri Apr  4 20:36:39 2003
@@ -0,0 +1,134 @@
+/*
+ * include/linux/markers.h - Reliable code markers (labels)
+ *
+ * Written 2003 by Werner Almesberger, Caltech Netlab FAST project
+ */
+
+#ifndef _LINUX_MARKERS_H
+#define _LINUX_MARKERS_H
+
+#include <linux/config.h>
+
+#ifdef CONFIG_MARKERS
+
+/*
+ * __marker_clobber_* macros are machine-generated. If you need to change them,
+ * use the build process from umlsim, which generates the kernel header file as
+ * umlsim/lib/markers_kernel.h
+ *
+ * umlsim can be found at http://umlsim.sourceforge.net/
+ */
+
+/*
+ * The following construct iterates over a variable-length list of variable
+ * names, and converts them to the clobber syntax.
+ */
+
+#define __marker_clobber_do_0_end(...)
+#define __marker_clobber_do_1_end(...)
+#define __marker_clobber_do_2_end(...)
+#define __marker_clobber_do_3_end(...)
+#define __marker_clobber_do_4_end(...)
+#define __marker_clobber_do_0_(car,...) \
+  , "+m"(car) __marker_clobber_map_1((__VA_ARGS__), ,##__VA_ARGS__ end)
+#define __marker_clobber_do_1_(car,...) \
+  , "+m"(car) __marker_clobber_map_2((__VA_ARGS__), ,##__VA_ARGS__ end)
+#define __marker_clobber_do_2_(car,...) \
+  , "+m"(car) __marker_clobber_map_3((__VA_ARGS__), ,##__VA_ARGS__ end)
+#define __marker_clobber_do_3_(car,...) \
+  , "+m"(car) __marker_clobber_map_4((__VA_ARGS__), ,##__VA_ARGS__ end)
+#define __marker_clobber_do_4_(car,...) \
+  , "+m"(car) __marker_clobber_map_5((__VA_ARGS__), ,##__VA_ARGS__ end)
+#define __marker_clobber_map_0(list,op,...) __marker_clobber_do_0_##op list
+#define __marker_clobber_map_1(list,op,...) __marker_clobber_do_1_##op list
+#define __marker_clobber_map_2(list,op,...) __marker_clobber_do_2_##op list
+#define __marker_clobber_map_3(list,op,...) __marker_clobber_do_3_##op list
+#define __marker_clobber_map_4(list,op,...) __marker_clobber_do_4_##op list
+
+/* redefine, without the comma */
+#undef __marker_clobber_do_0_
+#define __marker_clobber_do_0_(car,...) \
+  "+m"(car) __marker_clobber_map_1((__VA_ARGS__), ,##__VA_ARGS__ end)
+
+#define __marker_clobbers(...) \
+  __marker_clobber_map_0((__VA_ARGS__), ,##__VA_ARGS__ end)
+
+
+/*
+ * And another one: this one simply counts the number of arguments.
+ * We need this to skip past the clobbers in the asm statement.
+ *
+ * We can't use named arguments (supported starting with gcc 3.1), because
+ * trying to do so crashes gcc ...
+ */
+
+#define __marker_count_do_0_end(...) "0"
+#define __marker_count_do_1_end(...) "1"
+#define __marker_count_do_2_end(...) "2"
+#define __marker_count_do_3_end(...) "3"
+#define __marker_count_do_4_end(...) "4"
+#define __marker_count_do_0_(car,...) \
+  __marker_count_1((__VA_ARGS__), ,##__VA_ARGS__ end)
+#define __marker_count_do_1_(car,...) \
+  __marker_count_2((__VA_ARGS__), ,##__VA_ARGS__ end)
+#define __marker_count_do_2_(car,...) \
+  __marker_count_3((__VA_ARGS__), ,##__VA_ARGS__ end)
+#define __marker_count_do_3_(car,...) \
+  __marker_count_4((__VA_ARGS__), ,##__VA_ARGS__ end)
+#define __marker_count_do_4_(car,...) \
+  __marker_count_5((__VA_ARGS__), ,##__VA_ARGS__ end)
+#define __marker_count_0(list,op,...) __marker_count_do_0_##op list
+#define __marker_count_1(list,op,...) __marker_count_do_1_##op list
+#define __marker_count_2(list,op,...) __marker_count_do_2_##op list
+#define __marker_count_3(list,op,...) __marker_count_do_3_##op list
+#define __marker_count_4(list,op,...) __marker_count_do_4_##op list
+#define __marker_count(...) __marker_count_0((__VA_ARGS__), ,##__VA_ARGS__ end)
+
+
+/*
+ * __MARKER(name,args...) generates an entry in the ".dbg_markers" section with
+ * the following content:
+ *
+ * Offset Length (bytes)
+ *    0     4	marker address
+ *    4     4	pointer to function name (__func__) in .rodata
+ *    8    >1	file name (\0-terminated)
+ *   var.  0-3	padding bytes (all zero, to speed up searches)
+ *   var.  >1	label name (\0-terminated)
+ *   var.  0-3	padding bytes (all zero, to speed up searches)
+ *
+ * The (optional) list of arguments contains the names of variables that will
+ * be accessed from the debugger while the program is stopped at this
+ * breakpoint.
+ */
+
+
+#define __MARKER(name,...) \
+  __asm__ __volatile__( \
+    "1:\n" \
+    "\t.pushsection .dbg_markers,\"\",@progbits\n" \
+    "\t.long 1b\n" \
+    "\t.long %" __marker_count(__VA_ARGS__) "\n" \
+    "\t.asciz \"" __FILE__ "\"\n" \
+    "\t.align 4,0\n" \
+    "\t.asciz \"" #name "\"\n" \
+    "\t.align 4,0\n" \
+    "\t.popsection\n" \
+    : __marker_clobbers(__VA_ARGS__) : [fn] "m" (*__func__) : "memory")
+
+/*
+ * MARKER protects __MARKER against multiple uses of the same marker name
+ * within the same function.
+ */
+
+#define MARKER(name,...) \
+  do { __marker_##name: __attribute__((unused)) \
+       __MARKER(name,__VA_ARGS__); } while (0)
+
+#else /* CONFIG_MARKERS */
+
+#define MARKER(...)
+
+#endif /* !CONFIG_MARKERS */
+
+#endif /* _LINUX_MARKERS_H */
--- linux-2.5.66/net/core/dev.c.orig	Thu Apr  3 03:17:21 2003
+++ linux-2.5.66/net/core/dev.c	Fri Apr  4 21:30:27 2003
@@ -107,6 +107,7 @@
 #include <linux/kmod.h>
 #include <linux/module.h>
 #include <linux/kallsyms.h>
+#include <linux/markers.h>
 #ifdef CONFIG_NET_RADIO
 #include <linux/wireless.h>		/* Note : will define WIRELESS_EXT */
 #include <net/iw_handler.h>
@@ -1471,6 +1472,7 @@
 	int ret = NET_RX_DROP;
 	unsigned short type = skb->protocol;
 
+	MARKER(entry,skb);
 	if (!skb->stamp.tv_sec)
 		do_gettimeofday(&skb->stamp);
 
--- linux-2.5.66/arch/um/Kconfig.orig	Thu Apr  3 03:50:05 2003
+++ linux-2.5.66/arch/um/Kconfig	Thu Apr  3 04:20:43 2003
@@ -363,5 +363,29 @@
         If you're involved in UML kernel development and want to use gcov,
         say Y.  If you're unsure, say N.
 
+config UMLSIM
+	bool "Enable umlsim support"
+	default n
+	help
+	umlsim uses a UML kernel for event-driven simulations. This
+	option adds code to support virtual time (boot command-line
+	option 'vtime'), and to inform the umlsim control program
+	when the kernel is idle.
+
+	A kernel containing umlsim support can also be used without
+	virtual time and umlsim.
+
+	See <http://umlsim.sourceforge.net/> for more details.
+
+config MARKERS
+	bool "Enable reliable markers"
+	default UMLSIM
+	help
+	Reliable markers are used to mark potential breakpoint locations.
+	Debuggers (or debugger-like programs, such as umlsim) need
+	specific code if they want to use reliable markers.
+
+	If you're not using umlsim, you probably want to say N. If you're
+	using this kernel with umlsim, say Y.
 endmenu
 
--- linux-2.5.66/arch/um/drivers/daemon_kern.c.orig	Thu Apr  3 04:26:47 2003
+++ linux-2.5.66/arch/um/drivers/daemon_kern.c	Fri Apr  4 21:30:58 2003
@@ -9,6 +9,7 @@
 #include "linux/init.h"
 #include "linux/netdevice.h"
 #include "linux/etherdevice.h"
+#include "linux/markers.h"
 #include "net_kern.h"
 #include "net_user.h"
 #include "daemon.h"
@@ -54,6 +55,7 @@
 static int daemon_write(int fd, struct sk_buff **skb,
 			struct uml_net_private *lp)
 {
+	MARKER(entry,skb);
 	return(daemon_user_write(fd, (*skb)->data, (*skb)->len, 
 				 (struct daemon_data *) &lp->user));
 }

-- 
  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina         wa@almesberger.net /
/_http://www.almesberger.net/____________________________________________/

Re: [RFC/FYI] reliable markers (hooks/probes/taps/...)

[Karim Yaghmour]

Werner Almesberger wrote:
> 
> I wrote:
> > Here's a pretty light-weight approach I call "reliable markers":
> 
> Turns out that the memory clobber didn't make them particularly
> reliable. Here's a better version. Usage:
> 
> MARKER(label_name,var...);
> 
> Where var... is an optional comma-separated list of arguments or
> variables that may be accessed (read or modified) while at this
> breakpoint.
> 
> (This is just for demonstration. For serious use, one would generate
> a markers.h that can handle more than just four arguments.)

Very interesting.

We've already got a small program that does this for LTT statements
which we plan to use in the future: genevent.
http://www.listserv.shafik.org/pipermail/ltt-dev/2003-January/000408.html

genevent is pretty much straight forward. You type:
$ ./genevent default.event
$ ls default*
-rw-rw-r--    1 karim    karim         392 Apr  5 11:58 default.c
-rw-rw-r--    1 karim    karim        6892 Apr  5 11:56 default.event
-rw-rw-r--    1 karim    karim       18328 Apr  5 11:58 default.h

The default.event file contains declarations about each event. Here's
an example:
//TRACE_EV_SYSCALL_ENTRY
event(TRACE_EV_SYSCALL_ENTRY, "Entry in a given system call",
      field(syscall_id, "Syscall entry number in entry.S", uint(1)),
      field(address, "Address from which call was made", uint(4))
     );

And genevent creates the following entries in the default.h for it:
/****  structure and trace function for event: TRACE_EV_SYSCALL_ENTRY  ****/

__attribute__((packed)) struct TRACE_EV_SYSCALL_ENTRY_default_1{
  uint8_t syscall_id; /* Syscall entry number in entry.S */
  uint32_t address; /* Address from which call was made */
};

static inline void trace_default_TRACE_EV_SYSCALL_ENTRY(uint8_t syscall_id, uint32_t address){
  int bufLength = sizeof(struct TRACE_EV_SYSCALL_ENTRY_default_1);
  char buff[bufLength];
  struct TRACE_EV_SYSCALL_ENTRY_default_1 * __1 = (struct TRACE_EV_SYSCALL_ENTRY_default_1 *)buff;

  //initialize structs
  __1->syscall_id =  syscall_id;
  __1->address =  address;


  //call trace function
  trace_new(facility_default, TRACE_EV_SYSCALL_ENTRY, bufLength, buff);
};

Also, genevent automatically generates an enum for all the events
described in the .event file:
enum default_event {
  TRACE_EV_START,
  TRACE_EV_SYSCALL_ENTRY,
  TRACE_EV_SYSCALL_EXIT,
  TRACE_EV_TRAP_ENTRY,
...

Obviously the word "trace" is used throughout, but it can easily be
replaced by "marker" if this mechanism were generalized.

The intent is to have a .event file in every directory where there are
traced events in files (which are the equivalent of "markers" in your
scheme). During the build, the various headers would be created and
all the code would be generated on the fly.

Of course this is just a begining. We're open to suggestions and
contributions.

Cheers,

Karim

===================================================
                 Karim Yaghmour
               karim@opersys.com
      Embedded and Real-Time Linux Expert
===================================================

Re: [RFC/FYI] reliable markers (hooks/probes/taps/...)

[Werner Almesberger]

Karim Yaghmour wrote:
> We've already got a small program that does this for LTT statements
> which we plan to use in the future: genevent.

This looks like a clear improvement, and the markup needed in the
kernel is also pretty straightforward.

But my approach actually goes a bit further: I don't even need to
know types, because I can extract them from debugging information.
Clearly, there is a limit on how useful this is. E.g. if a variable
changes its type from "int" to "struct something *", anything using
it will need to know. But at least changes like "int" -> "unsigned
long" or -> "whatever_t" don't need to be synchronized.

Furthermore, the markers are for desperate cases, where the
debugging information does not allow us to find arguments or
variables, or even the location for placing the breakpoint. On
function entry, it should be possible to access arguments without
any markup in the code. I'll examine that part soon.

Generally, my idea is to gather as much useful information from
debugging data as possible. A few observations so far (based on
using DWARF2 information; all this is on the kernel, with the usual
optimizations):

 - gcc provides accurate type and name information

 - location of static or extern functions is accurate, but there
   doesn't seem to be a reliable means for determining where the
   function prologue ends [10000]

 - the location of inlined functions is less accurate than for
   non-inlined functions [10003]

 - labels (as in "goto foo;") are completely erratic (that's one
   reason for markers) [10001, 10002, 10003]

 - variable locations information is frequently only useful if
   we're after the prologue, and it does not accurately reflect
   register copies, and such (that's another reason for markers)
   [10005]

 - call frame information seems to be almost sufficient for
   emulating a function return. "Almost" because I also need to
   analyze the add N,%esp instruction following the call. I'm
   not sure yet if there isn't a better way, though.

The numbers in square brackets are the gcc PRs I've submitted.
(http://gcc.gnu.org/cgi-bin/gnatsweb.pl)

Without optimization, some things look better, of course.

I'm not sure how much help we can expect from the gcc side. Some
of these things may just be too hard to fix. And others can't be
usefully fixed at all (e.g. the markers tell gcc where the focal
points are, where it has to relax optimization for accessibility).

Some thing I haven't looked at yet:

 - using line numbers to specify locations. With optimization, I
   expect total disaster here. Also, line numbers are too volatile
   for few things but manual debugging.

 - passing structures as arguments, or returning them from functions

 - unusual (i.e. large) alignment settings. Perhaps I'll eventually
   need to know CFLAGS in order to reconstruct some things.

> Of course this is just a begining. We're open to suggestions and
> contributions.

Same thing here :-) My goal is to reduce the markup that has to
be done on the kernel to the bare minimum. The "reliable markers"
are the least intrusive way I could think of for handling those
cases where nothing else works (e.g. in the middle of a function).

It would be nice to have a "global" clobber, though. I.e. one that
flushes and invalidates all values cached in registers, and that
forces all evaluations happening prior in the nominal execution
flow to be carried out, including initialization of function-local
variables. That way, reliable markers wouldn't need the list of
things that might be looked at.

- Werner

-- 
  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina         wa@almesberger.net /
/_http://www.almesberger.net/____________________________________________/