dtrace discuss - Aug 2011 - Using dtrace to follow a kernel linked list

I''m looking for an example of how one could write a dtrace probe
that could follow something like a NULL terminated linked list.

For example:

struct list {
     struct list *next;
     void *data;
};

struct list *list_root;


Assuming I had "list_root" available, but I wanted to know how long
the linked list is, how can I do this in a dtrace probe?

If I had looping constructs, it would be obvious:

int
count_list(struct list *list)
{
     int i;

     for (i = 0; list != NULL; list = list->next)
         ++i;

     return i;
}

In the dtrace scripting language there are no loop constructs, but is
there a way to add a new provider than can loop?

Thank you,
Lida Horn

On Fri, Aug 19, 2011 at 01:34:36PM -0700, Lida Horn
wrote:
> I''m looking for an example of how one could write a dtrace probe
> that could follow something like a NULL terminated linked list.
> 
> For example:
> 
> struct list {
>     struct list *next;
>     void *data;
> };
> 
> struct list *list_root;
> 
> 
> Assuming I had "list_root" available, but I wanted to know how
long
> the linked list is, how can I do this in a dtrace probe?
> 
> If I had looping constructs, it would be obvious:
> 
> int
> count_list(struct list *list)
> {
>     int i;
> 
>     for (i = 0; list != NULL; list = list->next)
>         ++i;
> 
>     return i;
> }
> 
> In the dtrace scripting language there are no loop constructs, but is
> there a way to add a new provider than can loop?
Generally, you can do this using something like:

my:probe:matching:func
{
	this->list = /* some way to get initial list */;
	this->length = 0;
}

my:probe:matching:func / this->list != NULL / {
	this->list = this->list->next; this->length++;
}
my:probe:matching:func / this->list != NULL / {
	this->list = this->list->next; this->length++;
}
my:probe:matching:func / this->list != NULL / {
	this->list = this->list->next; this->length++;
}
my:probe:matching:func / this->list != NULL / {
	this->list = this->list->next; this->length++;
}
/* repeat N times, where N is the max list length */

my:probe:matching:func / this->list != NULL / {
	/* list was longer than our maximum length */
	@overflow = count();
}
my:probe:matching:func / this->list == NULL / {
	/* use this->count as the length of the list */
}


(Enablings for a probe are guaranteed to execute in program order, and this->
variables are valid between enablings of the same probe.)

Cheers,
- jonathan

Thank you for your reply, however I had
realized I could do something like that, but it a
stanza per iteration of the loop and if the loop
can be large (in the case I was looking at well over
4000 entries) the number of stanzas is prohibitive.

I''m looking for a way to actually follow the chain
all the way to the end without a hard limit
and without a huge dtrace script.

Regards,
Lida Horn


requires On 8/19/2011 2:46 PM, Jonathan Adams wrote:
> On Fri, Aug 19, 2011 at 01:34:36PM -0700, Lida Horn wrote:
>> I''m looking for an example of how one could write a dtrace
probe
>> that could follow something like a NULL terminated linked list.
>>
>> For example:
>>
>> struct list {
>>      struct list *next;
>>      void *data;
>> };
>>
>> struct list *list_root;
>>
>>
>> Assuming I had "list_root" available, but I wanted to know
how long
>> the linked list is, how can I do this in a dtrace probe?
>>
>> If I had looping constructs, it would be obvious:
>>
>> int
>> count_list(struct list *list)
>> {
>>      int i;
>>
>>      for (i = 0; list != NULL; list = list->next)
>>          ++i;
>>
>>      return i;
>> }
>>
>> In the dtrace scripting language there are no loop constructs, but is
>> there a way to add a new provider than can loop?
> Generally, you can do this using something like:
>
> my:probe:matching:func
> {
> 	this->list = /* some way to get initial list */;
> 	this->length = 0;
> }
>
> my:probe:matching:func / this->list != NULL / {
> 	this->list = this->list->next; this->length++;
> }
> my:probe:matching:func / this->list != NULL / {
> 	this->list = this->list->next; this->length++;
> }
> my:probe:matching:func / this->list != NULL / {
> 	this->list = this->list->next; this->length++;
> }
> my:probe:matching:func / this->list != NULL / {
> 	this->list = this->list->next; this->length++;
> }
> /* repeat N times, where N is the max list length */
>
> my:probe:matching:func / this->list != NULL / {
> 	/* list was longer than our maximum length */
> 	@overflow = count();
> }
> my:probe:matching:func / this->list == NULL / {
> 	/* use this->count as the length of the list */
> }
>
>
> (Enablings for a probe are guaranteed to execute in program order, and
this->
> variables are valid between enablings of the same probe.)
>
> Cheers,
> - jonathan
>
>

You may be able to combine Jonathan''s link-following method with a tick
probe to iterate over an arbitrarily long list over time. There''s a
chance the list can change out from under you, but it should get close to what
you want.

my:probe:matching:func
{
   this->list = /* some way to get initial list */;
   this->length = 0;
}

:::tick-5000 / this->list != NULL / {
   this->list = this->list->next; this->length++;
}

:::tick-5000 / this->list == NULL / {
   /* use this->count as the length of the list */
   trace(this->length);
   exit(0);
}

I''m not sure how to verify that the tick probe has fired in the
appropriate "this" context. If tick fires in the wrong context, you
could use any high frequency probe in the right context (fbt::: ?) to accomplish
the same thing.

Kevin


On Aug 19, 2011, at 3:43 PM, Lida Horn <Lida.Horn at oracle.com> wrote:
> Thank you for your reply, however I had
> realized I could do something like that, but it a
> stanza per iteration of the loop and if the loop
> can be large (in the case I was looking at well over
> 4000 entries) the number of stanzas is prohibitive.
> 
> I''m looking for a way to actually follow the chain
> all the way to the end without a hard limit
> and without a huge dtrace script.
> 
> Regards,
> Lida Horn
> 
> 
> requires On 8/19/2011 2:46 PM, Jonathan Adams wrote:
>> On Fri, Aug 19, 2011 at 01:34:36PM -0700, Lida Horn wrote:
>>> I''m looking for an example of how one could write a dtrace
probe
>>> that could follow something like a NULL terminated linked list.
>>> 
>>> For example:
>>> 
>>> struct list {
>>>     struct list *next;
>>>     void *data;
>>> };
>>> 
>>> struct list *list_root;
>>> 
>>> 
>>> Assuming I had "list_root" available, but I wanted to
know how long
>>> the linked list is, how can I do this in a dtrace probe?
>>> 
>>> If I had looping constructs, it would be obvious:
>>> 
>>> int
>>> count_list(struct list *list)
>>> {
>>>     int i;
>>> 
>>>     for (i = 0; list != NULL; list = list->next)
>>>         ++i;
>>> 
>>>     return i;
>>> }
>>> 
>>> In the dtrace scripting language there are no loop constructs, but
is
>>> there a way to add a new provider than can loop?
>> Generally, you can do this using something like:
>> 
>> my:probe:matching:func
>> {
>>    this->list = /* some way to get initial list */;
>>    this->length = 0;
>> }
>> 
>> my:probe:matching:func / this->list != NULL / {
>>    this->list = this->list->next; this->length++;
>> }
>> my:probe:matching:func / this->list != NULL / {
>>    this->list = this->list->next; this->length++;
>> }
>> my:probe:matching:func / this->list != NULL / {
>>    this->list = this->list->next; this->length++;
>> }
>> my:probe:matching:func / this->list != NULL / {
>>    this->list = this->list->next; this->length++;
>> }
>> /* repeat N times, where N is the max list length */
>> 
>> my:probe:matching:func / this->list != NULL / {
>>    /* list was longer than our maximum length */
>>    @overflow = count();
>> }
>> my:probe:matching:func / this->list == NULL / {
>>    /* use this->count as the length of the list */
>> }
>> 
>> 
>> (Enablings for a probe are guaranteed to execute in program order, and
this->
>> variables are valid between enablings of the same probe.)
>> 
>> Cheers,
>> - jonathan
>> 
>> 
> 
> _______________________________________________
> dtrace-discuss mailing list
> dtrace-discuss at opensolaris.org
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.opensolaris.org/pipermail/dtrace-discuss/attachments/20110820/b139734f/attachment.html>

On Fri, Aug 19, 2011 at 4:34 PM, Lida Horn <Lida.Horn at oracle.com>
wrote:
> I''m looking for an example of how one could write a dtrace probe
> that could follow something like a NULL terminated linked list.
>
If this is a list with short-lived entries (e.g., one of the hash
buckets in the sleep queue), you can approximate the length of the
list at any given time.  Increment a variable on entry to the
list_insert() function and decrement it on entry to the list_delete()
function.  Don''t let the value drop below 0, and eventually
you''ll
have a decent approximation to the length of the list.  (If the real
length of the list ever drops to 0 while you''re observing,
you''ll end
up with an accurate measurement.)

The example below does this.  It''s a script I used to look at the
average and max lengths of hash buckets in the sleep queue (the
self->bucket computation in the cv_block:entry clause is the old hash
function for the sleep queue):

fbt::cv_block:entry
{
       self->bucket = (((uintptr_t)(arg0) >> 2) +
              ((uintptr_t)(arg0) >> 9) & 511) + 1;
}

fbt::sleepq_insert:entry
/self->bucket/
{
       length[self->bucket]++;
       @r[self->bucket] = max(length[self->bucket]);
       @q[self->bucket] = avg(length[self->bucket]);
       bucket[arg1] = self->bucket;
       self->bucket = 0;
}

fbt::sleepq_unlink:entry
/ length[bucket[arg1]] > 0 /
{
       length[bucket[arg1]]--;
}

END
{
       trunc(@r,20);
       trunc(@q, 20);
	printf(?MAX:\n?);
	printa(@r);
	printf(?AVG:\n?);
	printa(@q);
}

Chad