[ANNOUNCE] Linux-tracecalls, a new tool for Kernel development, released

[ANNOUNCE] Linux-tracecalls, a new tool for Kernel development, released

[Carl Spalletta]

>From http://www.linuxrd.com/~carl/cgi-bin/lnxtc.pl?help

"'LINUX-TRACECALLS' finds all call chains leading to a given function in the Linux
kernel, to some arbitrary depth. It consists of two parts - a set of specially
prepared cscope databases for the kernel source tree, and a perl program, 'lnxtc.pl',
to do the call chain discovery based on the information in the cscope DBs."

"It works, in part, by expanding function-yielding macros and by mangling function names
with the name of the file containing the function's definition, prior to creating the
cscope files."

"It is believed to be highly accurate.."

Re: [ANNOUNCE] Linux-tracecalls, a new tool for Kernel development, released

[Horst von Brand]

Carl Spalletta <cspalletta@yahoo.com> said:
> >From http://www.linuxrd.com/~carl/cgi-bin/lnxtc.pl?help

[...]

> "It works, in part, by expanding function-yielding macros and by mangling
> function names with the name of the file containing the function's
> definition, prior to creating the cscope files."

If it can't find out where a function could be called through a pointer
(very common due to the OOP-in-C style in the kernel) it has no chance.
-- 
Dr. Horst H. von Brand                   User #22616 counter.li.org
Departamento de Informatica                     Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria              +56 32 654239
Casilla 110-V, Valparaiso, Chile                Fax:  +56 32 797513

Re: [ANNOUNCE] Linux-tracecalls, a new tool for Kernel development, released

[Carl Spalletta]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset=us-ascii, Size: 2926 bytes --]

--- Horst von Brand <vonbrand@inf.utfsm.cl> wrote:

> If it can't find out where a function could be called through a pointer
> (very common due to the OOP-in-C style in the kernel) it has no chance.

Dear Horst,

  No chance of what?

  You do raise an interesting point. Linux-tracecalls already does "find out where a
function could be called through a pointer" internally.  Therefore, it would be trivial
to add some indication to the the head of the call chain that the subsearch aborted
because a callback was detected; and I shall do so in the next release of the tool
(which will shortly after kernel.org kernel 2.6.11 is released). 

  The fact that the tool at this stage of development does not do something that it
was never designed to do, does not make it worthless. Moreover, I believe the burden
of your comments to be ill-considered for the following reasons:

  The functions you refer to are the callbacks that I have explicitly referred
to at http://www.linuxrd.com/~carl/linux-tracecalls :

        “Also, by design, 'linux-tracecalls' will stop tracing when it reaches
         a syscall, a gcc-builtin function or a callback.”

  I should have further pointed out, were it not so obvious, that if the call
chain as produced by the tool begins with function ‘F’ (ie 'F' is the oldest ancestor
of the initial target function) then:

    1)  You have been saved all the work of doing the tracing manually to that
        point, not only for that particular chain but for all the chains leading
        to your initial target function.

    2)  You can then manually check at function ‘F’ to see if there is a callback
        behind it.

    3)  If you find there is a callback behind ‘F’ then you can do another query
        using the actual function represented by the callback as a new initial
        target.

    4)  Callbacks - due to the OOP implications you have pointed out - are in most
        cases ultimately invoked due to syscalls and the core part of the kernel
        generally  (drivers do use OOP of course but it is not the absolute necessity
        there it is in the case of, for example, the VFS).

        That being so the paths to the callbacks are generally short ; thus the tool
        is doing most of the work for you in any case, even in the minority of cases
        involving a callback.

    5)  The tool has also done all the macro expansions of function-yielding macros
        for you, which due to the recursive nature of kernel header files is a major
        job in itself.

  At some future date I would like to add the capabilities you suggest - however
'lnxtc.pl' is presently over 800 lines of code and what you are suggesting is at
least an order of magnitude harder than what has been accomplished already, so it
won't be next week

  If this tool is really as useless as you suggest then I shall discontinue development.

  But I strongly disagree.  NIH?

Linux-tracecalls, a clarification

[Carl Spalletta]

http://www.linuxrd.com/~carl/cgi-bin/lnxtc.pl?help

--- Horst von Brand <vonbrand@inf.utfsm.cl> wrote:
> Re: [ANNOUNCE] Linux-tracecalls, a new tool for Kernel development, released 
> 
> If it can't find out where a function could be called through a pointer
> (very common due to the OOP-in-C style in the kernel) it has no chance.

Dear Doctor von Brand,

  I believe the following should clear up your misunderstanding, perhaps due
to my poor original choice of words.

Carl Spalletta

PATCH #2
--- lnxtc-2.6.10.pl-    2005-01-21 00:16:33.000000000 -0500
+++ lnxtc-2.6.10.pl     2005-01-21 00:50:11.000000000 -0500
@@ -517,10 +517,22 @@
     $leaf_node = 0;
     $debug and print STDERR "\ncscope line is $full_caller_cscope";

-    #Target is a callback
+    #TARGET IS A PSEUDO-CALLBACK, AN ARTIFACT OF CSCOPE:
+    #
+    #The name of an operations structure member, wrongly interpreted by
+    #cscope as the name of an actual function - it should be ignored,
+    #since it has been confused by cscope with the name of some actual
+    #caller. HOWEVER the callbacks are found anyway, under their actual names.
+    #and if any function pointed to by a callback is part of a chain to
+    #our initial target it _will_ be found, the same as any other caller.
+    #
     if($full_caller_cscope =~ /\w+\s*->\s*${target_filefunc}\s*\(/)
     {
-      $debug and print STDERR "callback $target_filefunc ignored.\n";
+      $debug and
+        print STDERR "pseudo-callback $target_filefunc ignored.\n";
       next;
     }

Re: Linux-tracecalls, a clarification

[Werner Almesberger]

Carl Spalletta wrote:
> +    #The name of an operations structure member, wrongly interpreted by
> +    #cscope as the name of an actual function - it should be ignored,
> +    #since it has been confused by cscope with the name of some actual
> +    #caller. HOWEVER the callbacks are found anyway, under their actual names.
> +    #and if any function pointed to by a callback is part of a chain to
> +    #our initial target it _will_ be found, the same as any other caller.

Hmm, but it doesn't seem to follow function pointers anyway. Example:

http://www.linuxrd.com/~carl/cgi-bin/lnxtc.pl?file=fs/jbd/transaction.c&func=do_get_write_access

should contain, among many others, this call chain:

fs/read_write.c:sys_read
  fs/read_write.c:vfs_read
    fs/ext3/file.c:ext3_file_operations.read =
    fs/read_write.c:do_sync_read
      fs/ext3/file.c:ext3_file_operations.aio_read =
      mm/filemap.c:generic_file_aio_read
        mm/filemap.c:__generic_file_aio_read
          include/linux/fs.h:do_generic_file_read
            mm/filemap.c:do_generic_mapping_read
              include/linux/fs.h:file_accessed
                include/linux/fs.h:touch_atime
                  fs/inode.c:update_atime
                    include/linux/fs.h:mark_inode_dirty_sync
                      fs/fs-writeback.c:__mark_inode_dirty
                        fs/ext3/super.c:ext3_sops.dirty_inode =
                        fs/ext3/inode.c:ext3_dirty_inode
                          include/linux/ext3_jbd.h:ext3_journal_get_write_access
                            fs/jbd/transaction.c:journal_get_write_access
                              fs/jbd/transaction.c:do_get_write_access

Note the three functions pointers that were used in this. This kind
of construct is extremely common in the kernel, and it's usually the
main source of confusion that will actually make one want to use a
call chain discovery tool.

I see that you're handling inline functions correctly.

Another thing that seems to be missing are macros. E.g. this query

http://www.linuxrd.com/~carl/cgi-bin/lnxtc.pl?file=include/linux/seqlock.h&func=seqcount_init

should probably have found the reference in fs.h (it's somewhat
obscured by #ifdefs, so, depending on how your tree was set up,
the response may actually be correct). Also, this query should have
returned something:

http://www.linuxrd.com/~carl/cgi-bin/lnxtc.pl?file=include/linux/blkdev.h&func=blk_queue_plugged

Since the call trees fan out very quickly (in either direction), I
think an interactive browser that lets you select which branch(es)
to follow (while remembering the chain you've already visited) would
be more useful than a huge dump that may require significant
post-processing.

It would also be nice to be able to go both ways, from called to
caller, and from caller to called. Again, the tricky bit here are
the function pointers.

I think that a tool that can handle the most common idioms found in
the kernel would be very useful.

- Werner

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

Re: Linux-tracecalls, a clarification

[Carl Spalletta]

Werner,
  Sorry for not responding to your excellent letter for so long.
Carl Spalletta


--- Werner Almesberger <wa@almesberger.net> wrote:

>> Subject: Re: Linux-tracecalls, a clarification

>>
http://www.linuxrd.com/~carl/cgi-bin/lnxtc.pl?file=fs/jbd/transaction.c&func=do_get_write_access
>> should contain, among many others, this call chain:
>> 
>> fs/read_write.c:sys_read
>>   fs/read_write.c:vfs_read
>>     fs/ext3/file.c:ext3_file_operations.read =
>>     fs/read_write.c:do_sync_read
>>       fs/ext3/file.c:ext3_file_operations.aio_read =
>>       mm/filemap.c:generic_file_aio_read
>>         mm/filemap.c:__generic_file_aio_read
>>           include/linux/fs.h:do_generic_file_read
>>             mm/filemap.c:do_generic_mapping_read
>>               include/linux/fs.h:file_accessed
>>                 include/linux/fs.h:touch_atime
>>                   fs/inode.c:update_atime
>>                     include/linux/fs.h:mark_inode_dirty_sync
>>                       fs/fs-writeback.c:__mark_inode_dirty
>>                         fs/ext3/super.c:ext3_sops.dirty_inode =
>>                         fs/ext3/inode.c:ext3_dirty_inode
>>                           include/linux/ext3_jbd.h:ext3_journal_get_write_access
>>                             fs/jbd/transaction.c:journal_get_write_access
>>                               fs/jbd/transaction.c:do_get_write_access
>> 
>> Note the three functions pointers that were used in this ..


This would require taking a callback such as this from fs/fs-writeback.c, line 65:

    sb->s_op->dirty_inode(inode);

and finding what functions could be in sb->s_op->dirty_inode, then branching backwards at
that point instead of terminating the search, as linux-tracecalls does here:

    fs/ext3/inode.c::ext3_dirty_inode
    fs/ext3/inode.c::ext3_mark_inode_dirty
    fs/ext3/inode.c::ext3_reserve_inode_write
    include/linux/ext3_jbd.h::__ext3_journal_get_write_access
    fs/jbd/transaction.c::journal_get_write_access
    fs/jbd/transaction.c::do_get_write_access

Note that linux-tracecalls does find the callback function 'ext3_dirty_inode' but does not
trace beyond it.  On the other hand since it is neither syscall, trap or interrupt handler it
is obvious that it involves a callback of some kind.  Also note that the sequence of calls found
by linux-tracecalls differs slightly from what you have adduced and appears to be correct,
although the discrepancy may be due to the kernel version being 2.6.11.6 instead of 2.6.10.

Now, I am not really happy using cscope as the search tool since it doesn't find all callers
e.g. it sometimes gags on functions having parameters of the type ptr-to-function, but it is
the best I could find, and moreover with the 'cscope -l' flag it runs in a kind of server or
daemon mode which makes it possible to avoid spawning thousands of cscope processes to do the
tracing at each level of the call chain.

But if I were to do it in cscope, it would mean translating that one callback into some larger
number of identical calls at the same point, ie instead of 

    sb->s_op->dirty_inode(inode);

the sourcefile at that point would read:

    fsFWDSLASHext3FWDSLASHsuperDOT_CFILEext3_dirty_inode(inode);
    fsFWDSLASHjffs2FWDSLASHsuperDOT_CFILEjffs2_dirty_inode(inode);
    fsFWDSLASHjfsFWDSLASHsuperDOT_CFILEjfs_dirty_inode(inode);
    fsFWDSLASHreiserfsFWDSLASHsuperDOT_CFILEreiserfs_dirty_inode(inode);

or, without the mangling:

    ext3_dirty_inode(inode);
    jffs2_dirty_inode(inode);
    jfs_dirty_inode(inode);
    reiserfs_dirty_inode(inode);

Certainly this is ugly, but it would yield valid results.  I would have to either use some gcc
flag(s) that would enable me to find all function calls resulting from statements evaluating
to type-ptr-to-function(arglist), and then find all '.funcptr = somefunction;' initializers or
other assignments to type ptr-to-function that could affect the evaluation of the callback;
or I would have to find the callbacks lexically. Then I would have to determine at the top of
each call chain if the terminating function could indeed be invoked from a callback and branch
accordingly.

I consider the compiler based approach better and more accurate but right now I haven't a clue as
to which compiler flags could ultimately yield the desired info. Would you have any suggestions?

Moreover I am, as I said, unhappy with cscope and I am not sure just how much further I want
to develop linux-tracecalls based on cscope. Although it is excellent for most purposes, I
consider it's support uncertain and of uneven quality, it was never intended for this purpose,
and I am afraid of building my house on sand.

It would certainly be nice if cscope understood the scoping rules of 'C', as well as _all_
function declarations and would return only valid callers, not just all functions that call
a target of a given name as it presently does.  See also this discussion:

 
groups.google.com/groups?hl=en&lr=&ie=UTF-8&q=interesting+failures+of+cscope&meta=group%3Dlinux.kernel


>> Another thing that seems to be missing are macros. E.g. this query
>> 
>> http://www.linuxrd.com/~carl/cgi-bin/lnxtc.pl?file=include/linux/seqlock.h&func=seqcount_init
>> 
>> should probably have found the reference in fs.h ..
>> Also, this query should have returned something:
>> 
>>
http://www.linuxrd.com/~carl/cgi-bin/lnxtc.pl?file=include/linux/blkdev.h&func=blk_queue_plugged


The process used to create the cscope DBs is compiler based - it uses the output from
-fdump-translation-unit to mangle the special source files that are used to construct the cscope
databases.  Since macros can be recursive and terminate in actual function calls the sourcefiles
are expanded before the dumps are made.  At the present time that results in a tradeoff -
the hidden function calls are revealed but the macros are lost.  So the output, conceptually,
is something that could be and in almost all cases is identical to a kernel stack backtrace.

The only exceptions would be 'impossible' branches embedded in the kernel code (by design or
otherwise).

However it certainly _is_ desirable to be able to flag those macros. 


>> Since the call trees fan out very quickly (in either direction), I
>> think an interactive browser that lets you select which branch(es)
>> to follow (while remembering the chain you've already visited) would
>> be more useful than a huge dump that may require significant
>> post-processing.
>> 
>> It would also be nice to be able to go both ways, from called to
>> caller, and from caller to called. Again, the tricky bit here are
>> the function pointers.


This is a good idea.  Probably it can be done as an extension of 'cbrowser' although my own
experience of cbrowser combined w/ cscope kernel databases created with the 'q' flag - which
I use for speed - has not been promising, since cbrowser stalls for long periods of time.  Perhaps
by eliminating that flag the performance might be improved; alternatively cbrowser may not scale
well to large DBs at all.

The primary enhancement to cbrowser, resulting from your suggestion, would involve unmangling the
function names (at least partially) before presentation, for the sake of clarity. E.g. the stmt

    fsFWDSLASHext3FWDSLASHsuperDOT_CFILEext3_dirty_inode(inode);

would become

    fs/ext3/super.c::ext3_dirty_inode(inode);


Thanks again, Werner! I have both enjoyed and profited from your remarks.