Using dtrace to follow a kernel linked list

[Lida Horn]

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

[Jonathan Adams]

Post by Lida Horn
I'm looking for an example of how one could write a dtrace probe
that could follow something like a NULL terminated linked list.
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?
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

[Lida Horn]

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

Post by Jonathan Adams

Post by Lida Horn
I'm looking for an example of how one could write a dtrace probe
that could follow something like a NULL terminated linked list.
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?
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?

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

[Kevin Colwell]

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

Post by Lida Horn
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

Post by Jonathan Adams

Post by Lida Horn
I'm looking for an example of how one could write a dtrace probe
that could follow something like a NULL terminated linked list.
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?
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?

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

[Chad Mynhier]

Post by Lida Horn
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