Jonathan Adams's Weblog

The FBT provider, opensolaris source, and fun with the environment

The FBT provider, opensolaris source, and fun with the environment

Now that opensolaris is out there, it's quite a bit easier for folks to use DTrace's FBT provider. FBT provides "function boundary tracing", i.e. it has probes for the entry and exit for almost every function in the kernel. This is amazingly powerful and flexible, but it leads to it being hard to use: with over 20,000 functions on a typical Solaris box, it's very hard to know where to start, especially without access to the source code.

With OpenSolaris, the source code is available. So to illustrate how you can use this newly available information to get something done, I thought I'd use a classic question: How can I examine and muck with the environment?

To start off, we need a plan of attack; since dtrace doesn't have any way of looping over datastructures, typically if you want to walk some datastructure, you just find a place where the kernel is already doing so, and use probes there to sneak a peak at the data as it goes by. The initial environment for a process is set up in the exec(2) system call, so lets see if we can find where we read in the data from the user process.

Looking at the source, exece() calls exec_common(), which is the main workhorse. There doesn't seem to be any direct mucking of the environment, but there is:

    222 	ua.fname = fname;
    223 	ua.argp = argp;
    224 	ua.envp = envp;
    225 
    226 	if ((error = gexec(&vp, &ua, &args, NULL, 0, &execsz,
    227 	    exec_file, p->p_cred)) != 0) {

   1303 	if (envp != NULL) {
   1304 		for (;;) {
   1305 			if (stk_getptr(args, envp, &sp))
   1306 				return (EFAULT);
   1307 			if (sp == NULL)
   1308 				break;
   1309 			if ((error = stk_add(args, sp, UIO_USERSPACE)) != 0)
   1310 				return (error);
   1311 			envp += ptrsize;
   1312 		}
   1313 	}

1. First, use fbt::stk_copyin:entry to stash a copy of the envp pointer.
2. Second, use fbt::stk_getptr:entry to watch for reads from the stored envp address.
3. Third, use fbt::stk_add:entry and fbt::stk_add:return to print out the environment.
4. Lastly, use fbt::stk_copyin:return to clean up.

#!/usr/sbin/dtrace -s

#pragma D option quiet

fbt::stk_copyin:entry
{
	self->envp = (uintptr_t)args[0]->envp;
}

fbt::stk_getptr:entry
/ self->envp != 0 /
{
	/* check if we're looking at envp or envp+1 */
	self->on = ((arg1 - self->envp) <= sizeof (uint64_t));

	/* update envp if we're on */
	self->envp = self->on ? arg1 : self->envp;
}

fbt::stk_add:entry
/ self->on && args[2] == UIO_USERSPACE /
{
	self->ptr = arg1;
}

fbt::stk_add:return
/ self->ptr != 0 /
{
	printf("%.79s\n", copyinstr(self->ptr));
	self->ptr = 0;
	self->on = 0;
}

fbt::stk_copyin:return
{
	self->envp = 0;
	self->on = 0;
}

dtrace: error on enabled probe ID 4 (ID 12535: fbt:genunix:stk_add:entry):
invalid address (0x1818000) in action #1 at DIF offset 28

Now, looking at the environment is fun, but it would be even more interesting to change the environment of a process while it is being execed. This requires a bit more work, and access to the destructive action copyout(). I'm going to start with a script which requires a recent version of Solaris (snv_15+, or the OpenSolaris release), because Bryan introduced some nice string handling stuff recently. We'll adapt the script to S10 afterwards.

Lets start by saying we want to change the name of the environment variable "FOO" to "BAR", but leave the value the same. The basic idea is simple; copyin() the string in the fbt::stk_add:entry probe, and if it's the one we want to change, copyout() the changes. The kernel will then proceed to copyin() the changed string, and use it for the environment of the process. The complication is the same as before; what if the page hasn't yet been touched, or the copyout() operation fails (for example, if the string isn't writable)?

There's no simple solution, so I'm just going to check *afterwards* that we didn't miss changing it, and kill -9 the process if we did. It's vile, but effective. Here's the script:

#!/usr/sbin/dtrace -s

#pragma D option quiet
#pragma D option destructive

self uintptr_t ptr;

inline int interesting = (strtok(copyinstr(self->ptr), "=") == "FOO");

fbt::stk_copyin:entry
{
	self->envp = (uintptr_t)args[0]->envp;
}

fbt::stk_getptr:entry
/ self->envp != 0 /
{
	/* check if we're looking at envp or envp+1 */
	self->on = ((arg1 - self->envp) <= sizeof (uint64_t));

	/* update envp if we're on */
	self->envp = self->on ? arg1 : self->envp;
	self->ptr = 0;
}

fbt::stk_add:entry
/ self->on && args[2] == UIO_USERSPACE /
{
	self->ptr = arg1;
	self->didit = 0;
}

fbt::stk_add:entry
/ self->ptr != 0 && interesting /
{
	printf("%d: %s: changed env \"%s\"\n",
	    pid, execname, copyinstr(self->ptr));
	copyout("BAR", self->ptr, 3);		/* 3 == strlen("BAR") */
	self->didit = 1;
}

fbt::stk_add:return
/ self->ptr != 0 && interesting && !self->didit /
{
	printf("%d: %s: killed, env \"%s\" couldn't be changed\n",
	    pid, execname, copyinstr(self->ptr));
	raise(9);
}

fbt::stk_copyin:return
{
	self->envp = 0;
	self->on = 0;
	self->ptr = 0;
}

inline int interesting =
    ((self->str = copyinstr(self->ptr), "=")[0] == 'F' &&
    self->str[1] == 'O' &&
    self->str[2] == 'O' &&
    self->str[3] == '=');
...
fbt::stk_copyin:return
{
	self->envp = 0;
	self->on = 0;
	self->ptr = 0;
	self->str = 0;
}

Technorati Tag: Dtrace
Technorati Tag: OpenSolaris
Technorati Tag: Solaris

Posted at 04:24PM Jun 30, 2005 by jwadams in Solaris  |  Comments[2]

macros and powers of two

Unlike many userland applications, there are large portions of the kernel that need to do bit-level manipulations. These generally fall into a few distinct areas:

• Drivers communicating with hardware
• Hash functions, bitmasks, and other high-performance algorithms
• Memory allocators, page manipulators, etc.

The main low-level allocators in Solaris are kmem and vmem; kmem handles your standard page-backed memory allocation, while vmem handles the more abstract concept of allocating from spaces of integers. kmem actually layers on top of vmem, but the details are beyond the scope of this blog entry.

While implementing vmem, Jeff Bonwick introduced a set of handy macros for dealing with things relative to powers of two. The macros live in uts/common/sys/sysmacros.h, and are defined thusly:

/*
 * Macros for various sorts of alignment and rounding when the alignment
 * is known to be a power of 2.
 */
#define	P2ALIGN(x, align)		((x) & -(align))
#define	P2PHASE(x, align)		((x) & ((align) - 1))
#define	P2NPHASE(x, align)		(-(x) & ((align) - 1))
#define	P2ROUNDUP(x, align)		(-(-(x) & -(align)))
#define	P2END(x, align)			(-(~(x) & -(align)))
#define	P2PHASEUP(x, align, phase)	((phase) - (((phase) - (x)) & -(align)))
#define	P2CROSS(x, y, align)		(((x) ^ (y)) > (align) - 1)
/*
 * Determine whether two numbers have the same high-order bit.
 */
#define	P2SAMEHIGHBIT(x, y)		(((x) ^ (y)) < ((x) & (y)))

-x = ~x + 1

        x = ...xxxxx10000...
      x-1 = ...xxxxx01111...
       ~x = ...XXXXX01111...
-x = ~x+1 = ...XXXXX10000...

From the above, here are some trivial relations between the various functions:

P2ALIGN(x, align)   = x - P2PHASE(x, align)
P2ROUNDUP(x, align) = x + P2NPHASE(x, align)
P2END(x, align)     = P2ALIGN(x, align) + align

Finally, the one drawback of these macros is the fact that they are macros. This means that (as usual) the argument parsing can leave much to be desired. The biggest problem is that there is no type enforcement; if x, y, or align are not unsigned integers of the same width, bad results can occur. Hence the (recently added) macros, P2*_TYPED, defined underneath the originals, which allow an explicit type to be specified.

Despite this drawback, these macros tend to be much clearer than the same things done by hand in the code. They probably aren't used enough, in fact.

Footnotes

[1] Of course, zero doesn't have a lowest set bit, but you can treat it as being 2^bits, and get the same answer.

Technorati Tag: OpenSolaris
Technorati Tag: Solaris

Posted at 01:31PM Jun 15, 2005 by jwadams in Solaris  |  Comments[1]

  4840780 ::findleaks oversized leak reporting needs overhaul
  4849669 ::findleaks' cleanup code needs work
  4931271 kmem walkers and ::findleaks use large amounts of memory
  5030758 ::findleaks should have an option to display the stack traces

I'll use the term "target" when talking about the other side of ::findleaks's implementation. The non-static target interfaces all start with leaky_subr_.

The target interface is a link-time, functional binding; during the compilation process, alternate versions of the target routines are linked against essentially the same "generic" framework. This is less flexible than doing some kind of dynamic binding (i.e. using function pointers), but is sufficiently general as long as only one target interfaces is required for a given dmod.

The public interface

The top layer of interface consists of the dcmds (D commands) and walkers exported by the genunix and libumem dmods. In the genunix dmod, these are defined in .../modules/genunix/genunix.c:

static const mdb_dcmd_t dcmds[] = {
...
	/* from leaky.c + leaky_subr.c */
	{ "findleaks", FINDLEAKS_USAGE,
	    "search for potential kernel memory leaks", findleaks,
	    findleaks_help },
...
static const mdb_walker_t walkers[] = {
...
	/* from leaky.c + leaky_subr.c */
	{ "leak", "given a leaked bufctl or vmem_seg, find leaks w/ same "
	    "stack trace",
		leaky_walk_init, leaky_walk_step, leaky_walk_fini },
	{ "leakbuf", "given a leaked bufctl or vmem_seg, walk buffers for "
	    "leaks w/ same stack trace",
		leaky_walk_init, leaky_buf_walk_step, leaky_walk_fini },

First up: initialize, estimate, slurp in the buffers

When ::findleaks is invoked, mdb(1) calls findleaks(), which validates its arguments, calls leaky_cleanup() to clean up any interrupted state, then checks if there is cached data. If not, we start the run in earnest.

The first call into the target interface is here:

	if ((ret = leaky_subr_estimate(&est)) != DCMD_OK)
		return (ret);

Shiny new estimate in hand, ::findleaks allocates a (possibly huge) array of leak_mtab_ts, calls into the target to fill it, and sorts the result:

	lk_mtab = mdb_zalloc(est * sizeof (leak_mtab_t), UM_SLEEP | UM_GC);
	lmp = lk_mtab;

	if ((ret = leaky_subr_fill(&lmp)) != DCMD_OK)
		return (ret);

	lk_nbuffers = lmp - lk_mtab;

	qsort(lk_mtab, lk_nbuffers, sizeof (leak_mtab_t), leaky_mtabcmp);

Stage two: find everything reachable

::findleaks is, at its heart, a simulation of a conservative garbage collection run. All of the lk_mtab entries start in the "unmarked" state; that is, they are not known to be reachable. We call into the target:

	if ((ret = leaky_subr_run()) != DCMD_OK)
		return (ret);

While the interface for leaky_grep() has a simple description, it invites a spectrum of implementation possibilities, each with different trade-offs in speed, memory usage, and maintainability.^[1] Any findleaks run spends virtually all of its time and energy in leaky_grep(), so it is worth the effort of optimizing. The most straightforward implementation is something like:

leaky_grep(addr, size)
	allocate a buffer of size bytes
	read [addr, size) into the buffer
	for each pointer in buffer {
		look up mtab entry
		if it is marked, continue
		mark it
		leaky_grep(mtab's base, mtab's size);
	}
	free the buffer

Instead of storing a buffer for each recursive step, the current algorithm uses a single small (16 kbyte) buffer. The following comment describes how we use the buffer:

		/*
		 * The buffer looks like:  ('+'s are unscanned data)
		 *
		 * -----------------------------++++++++++++++++
		 * |				|		|
		 * buf				cur		end
		 *
		 * cur scans forward.  When we encounter a new buffer, and
		 * it will fit behind "cur", we read it in and back up cur,
		 * processing it immediately.
		 */

Stage three: collect the leaks

Once leaky_subr_run() returns successfully, we're on the home stretch. First, we scan the lk_mtab array for unmarked buffers, and report them to the target implementation:

	for (i = 0; i < lk_nbuffers; i++) {
		if (LK_MARKED(lk_mtab[i].lkm_base))
			continue;
		leaky_subr_add_leak(&lk_mtab[i]);
	}

	leaky_sort();

Final stage: report the leaks

Once leaky_sort has completed, the results have been stored and cached in static data. leaky_dump() dumps the data, using the algorithm explained in .../modules/genunix/leaky_impl.h:

 * void leaky_subr_dump_start(type)
 * void leaky_subr_dump(lkb, verbose)
 * void leaky_subr_dump_end(type)
 *	Used to dump the table of discovered leaks.  invoked as:
 *
 *		for i in 0 .. LK_NUM_TYPES
 *			leaky_subr_dump_start(i)
 *			for lkb in (possibly a subset of) the type i leaks
 *				leaky_subr_dump(lkb, 0)
 *			leaky_subr_dump_end(i)
 *
 *	leaky_subr_dump_start()/end() are always invoked for each type, even
 *	if there are no leaks of that type.  If '-d' was passed to
 *	::findleaks, then we loop through the sequence of lkbs:
 *
 *		for i in 0 .. LK_NUM_TYPES
 *			for lkb of type i, same subset and order as above
 *				leaky_subr_dump(lkb, 1)
 *
 *	leaky_subr_dump() can use the leaks chained off of lkb_next to
 *	access coalesced leaks.  lkb_dups is the length of the dup list.

Conclusion and Final Thoughts

The generic findleaks code is compact (913 lines), and for the most part without external dependency.^[3] It is a useful shell for running the leak processing, but knows nothing of how to discover allocated buffers, root sets, or any other implementation details. All such external dependencies are covered by the target implementations. (It should be possible to do a target implementation for any allocator which has enough state to track all allocated buffers.)

One interesting aspect of this re-working is that the "target" interface places a huge set of requirements on the generic framework; given just the contents of .../modules/genunix/leaky_impl.h, someone writing a clean-room implementation of leaky.c would be constrained to writing something extremely similar to what is there today. On the other hand, the target implementation is less constrained by the target interface. Instead, it is mostly determined by how it must retrieve the needed data from the process, memory image, or core file mdb(1) is running against. This trade off of flexibility on two sided of a software interface is a common pattern, and interesting to see on a smaller scale.

Footnotes:

[1] Interestingly, speed is pretty low on the priority list, especially in the post-mortem case: ::findleaks, when run against a dump, is almost entirely I/O bound.
[2] Which will blow out the stack, causing a core dump. Simple recursion removal techniques lead you to the original leaky_grep() implementation: an iterative form of the same algorithm, with the stack of pending work stored on the heap. This implementation served ::findleaks well, until kmdb's memory constraints came along.
[3] Ignoring the "verbose" output, the only external calls not part of the target interface is the call to mdb_vread() in leaky_grep(), which reads from the program's address space, and mdb_getopts(), used to parse the arguments to ::findleaks.

Technorati Tag: OpenSolaris
Technorati Tag: Solaris
Technorati Tag: mdb

Posted at 10:35AM Jun 14, 2005 by jwadams in Solaris  |  Comments[3]