2016/09/12

Perl Parser Plugins 3 - Optrees

<< First | < Prev | Next >

So far we've seen how to interact with the perl parser to introduce new keywords. We've seen how we can allow that keyword to be enabled or disabled in lexical scopes. But our newly-introduced syntax still doesn't actually do anything yet. Today lets change that, and actually provide some new syntax which really does something.

Optrees

To understand the operation of any parser plugin (or at least, one that actually does anything), we first have to understand some more internals of how perl works; a little of how the parser interprets source code, and some detail about how the runtime actually works. I won't go into a lot of detail in this post, only as much as needed for this next example. I'll expand a lot more on it in later posts.

Every piece of code in a perl program (i.e. the body of every named and anonymous function, and the top-level code in every file) is represented by an optree; a tree-shaped structure of individual nodes called ops. The structure of this optree broadly relates to the syntactic nature of the code it was compiled from - it is the parser's job to take the textual form of the program and generate these trees. Each op in the tree has an overall type which determines its runtime behaviour, and may have additional arguments, flags that alter its behaviour, and child ops that relate to it. The particular fields relating to each op depend on the type of that op.

To execute the code in one of these optrees the interpreter walks the tree structure, invoking built-in functions determined by the type of each op in the tree. These functions implement the behaviour of the optree by having side-effects on the interpreter state, which may include global variables, the symbol table, or the state of the temporary value stack.

For example, let us consider the following arithmetic expression:

(1 + 2) * 3

This expression involves an addition, a multiplication, and three constant values. To express this expression as an optree requires three kinds of ops - a OP_ADD op represents the addition, a OP_MULT the multiplication, and each constant is represented by its own OP_CONST. These are arranged in a tree structure, with the OP_MULT at the toplevel whose children are the OP_ADD and one of the OP_CONSTs, the OP_ADD having the other two OP_CONSTs. The tree structure looks something like:

OP_MULT:
  +-- OP_ADD
  |     +-- OP_CONST (IV=1)
  |     +-- OP_CONST (IV=2)
  +-- OP_CONST (IV=3)
Side note: it is unlikely that a real program would ever actually contain an optree like this one, because the compiler will fold the constants out into a single constant value. But this will serve fine as a simple example to demonstrate how it works.

You may recall from the previous post that we implemented a keyword plugin that simply created a new OP_NULL optree; i.e. an optree that doesn't do anything. If we now change this to construct an OP_CONST we can build a keyword that behaves like a symbolic constant; placing it into an expression will yield the value of that constant. This returned op will then be inserted into the optree of the function containing the syntax that invoked our plugin, to be executed at this point in the tree when that function is run.

To start with, we'll adjust the main plugin hook function to recognise a new keyword; this time tau:

static int MY_keyword_plugin(pTHX_ char *kw, STRLEN kwlen,
    OP **op_ptr)
{
  HV *hints = GvHV(PL_hintgv);
  if(kwlen == 3 && strEQ(kw, "tau") &&
     hints && hv_fetchs(hints, "tmp/tau", 0))
    return tau_keyword(op_ptr);

  return (*next_keyword_plugin)(aTHX_ kw, kwlen, op_ptr);
}

Now we can hook this up to a new keyword implementation function that constructs an optree with a OP_CONST set to the required value, and tells the parser that it behaves like an expression:

#include <math.h>

static int tau_keyword(OP **op_ptr)
{
  *op_ptr = newSVOP(OP_CONST, 0, newSVnv(2 * M_PI));
  return KEYWORD_PLUGIN_EXPR;
}

We can now use this new keyword in an expression as if it was a regular constant:

$ perl -E 'use tmp; say "Tau is ", tau'
Tau is 6.28318530717959

Of course, so far we could have done this just as easily with a normal constant, such as one provided by use constant. However, since this is now implemented by a keyword plugin, it can do many exciting things not available to normal perl code. In the next part we'll explore this further.

<< First | < Prev | Next >

2016/08/26

Perl Parser Plugins 2 - Lexical Hints

<< First | < Prev | Next >

In the previous post we saw the introduction to how the perl parser engine can be extended, letting us hook a new function in that gets invoked whenever perl sees something that might be a keyword. The code in the previous post didn't actually add any new functionality. Today we're going to take a look at how new things can actually be added.

A Trivial Keyword

Possibly the simplest form of keyword plugin is one that doesn't actually do anything, other than consume the keyword that controls it. For example, lets consider the following program, in which we've introduced the please keyword. It doesn't actually have any effect on the runtime behaviour of the program, but it lets us be a little more polite in our request to the interpreter.

use tmp;
use feature 'say';

please say "Hello, world!"

To implement this plugin, we start by writing a keyword plugin hook function that recognises the please keyword, and invokes its custom handling function if it's found. It's purely a matter of style, but I like to write this as a small function for the plugin hook itself that simply recognises the keyword. If it finds the keyword it invokes a different function to actually implement the behaviour. This helps keep the code nice and neat.

static int (*next_keyword_plugin)(pTHX_ char *, STRLEN, OP **);

static int MY_keyword_plugin(pTHX_ char *kw, STRLEN kwlen,
    OP **op_ptr)
{
  if(kwlen == 6 && strEQ(kw, "please"))
    return please_keyword(op_ptr);

  return (*next_keyword_plugin)(aTHX_ kw, kwlen, op_ptr);
}

MODULE = tmp  PACKAGE = tmp

BOOT:
  next_keyword_plugin = PL_keyword_plugin;
  PL_keyword_plugin = &MY_keyword_plugin;

Next, we need to provide this please_keyword function that implements our required behaviour.

static int please_keyword(OP **op_ptr)
{
  *op_ptr = newOP(OP_NULL, 0);
  return KEYWORD_PLUGIN_STMT;
}

The last line of this function, the return statement, tells the perl parser that this plugin has consumed the keyword, and that the resulting syntactic structure should be considered as a statement. The effect of this resets the parser into wanting to find the start of a new statement following it, which lets it then see the say call as normal.

As mentioned in the previous post, a parser plugin provides new behaviour into the parse tree by using the op_ptr double-pointer argument, to give a new optree back to the parser to represent the code the plugin just parsed. Since our plugin doesn't actually do anything, we don't really need to construct an optree. But since there is no way to tell perl "nothing", instead we have to build a single op which does nothing; this is OP_NULL. Don't worry too much about this line of code; consider it simply as part of the required boilerplate here, and I'll expand more on the subject in a later post.

Lexical Hints

Implemented as it stands, there's one large problem with this syntax plugin. You may recall from part 1 that the plugin hook chain is global to the entire parser, and is invoked whenever code is found anywhere. This means that other code far away from our plugin will also get disturbed. For example, if the following code appears elsewhere when our module is loaded:

sub please { print @_; }

print "Before\n";
please "It works\n";
print "After\n";

__END__
Useless use of a constant ("It works\n") in void context at - line 4.
Before
After

This happens because our plugin has no knowledge of the lexical scope of the keywords; it will happily consume the keyword wherever it appears in any file, in any scope. This doesn't follow the usual way that perl code is parsed; ideally we would like our keywords to be enabled or disabled lexically. The lexical hints hash, %^H, can be used to provide this lexical scoping. We can make use of this by setting a lexical hint in this hash when the module is loaded, and having the XS code look for that hint to control whether it consumes the keyword.

We start by adding a import function to the perl module that loads the XS code, which sets this hint. There's a strong convention among CPAN modules, which must all share this one hash, about how to name keys within it. They are named using the controlling module's name, followed by a / symbol.

package tmp;

require XSLoader;
XSLoader::load( __PACKAGE__ );

sub import
{
  $^H{"tmp/please"}++;
}

The perl interpreter will now assist us with maintaining the value of %^H, ensuring that this key only has a true value during lexical scopes which have used our module. We can now extend the test function in the XS code to check for this condition. In XS code, the hints hash is accessible as the GvHV of PL_hintgv:

static int MY_keyword_plugin(pTHX_ char *kw, STRLEN kwlen,
    OP **op_ptr)
{
  HV *hints = GvHV(PL_hintgv);
  if(kwlen == 6 && strEQ(kw, "please") &&
     hints && hv_fetchs(hints, "tmp/please", 0))
    return please_keyword(op_ptr);

  return (*next_keyword_plugin)(aTHX_ kw, kwlen, op_ptr);
}

We now have a well-behaved syntax plugin which is properly aware of lexical scope. It only responds to its keyword in scopes where use tmp is in effect:

$ perl -wE '{use tmp; sub please { say @_ }; please "hello"}'
Useless use of a constant ("hello") in void context at -e line 1.

$ perl -wE '{use tmp;} sub please { say @_ }; please "hello"'
hello

Of course, we still haven't actually added any real behaviour yet but we're at least all set for having a lexically-scoped keyword we use to add that. We'll see how we can start to introduce new behaviour to the perl interpreter in part 3.

<< First | < Prev | Next >

2016/08/12

Perl Parser Plugins - part 1

<< First | < Prev | Next >

Today's subject is the parser plugins that were added to perl in 5.14. The parser plugin API itself is relatively small and modest, but the power it grants the user is enormous. To use this power however, you need to know and be familiar with a lot of the internals of the perl core.

This post will be a little different to most of my usual posts. Rather than announcing and demonstrating some code that's already written and available on CPAN or wherever, I shall today be writing about some code I'm currently in the progress of writing. I'm hoping this series of posts will contain useful information about the underlying subject of perl parser plugins and other internal details.

As a parser plugin would be written in C as part of an XS module, the reader is presumed to be at least somewhat familiar with C syntax, and to have at least a basic understanding of what an XS module is and how to go about creating one.

The PL_keyword_plugin Hook

The initial point of entry into the parser plugin system is a function pointer variable that's part of the interpreter core, called PL_keyword_plugin. This variable points to a function that the perl parser will invoke whenever it finds something that looks like it could be a keyword. It's typed as

int (*PL_keyword_plugin)(pTHX_
    char *keyword_ptr, STRLEN keyword_len,
    OP **op_ptr);

How it behaves is that whenever the parser finds a sequence of identifier-like characters that could be a keyword, it first asks the keyword plugin whether it wishes to handle it. The sequence of characters itself is passed in via the pointer and length pair. Because this is a pointer directly into the parser's working-space buffer, the keyword itself will not be NUL-terminated, and so the length argument is required too. The integer return value works with the op_ptr double-pointer value to let the plugin return its result back to the interpreter in the form of an optree. For today's post we won't concern ourselves with this optree, and instead write a plugin that doesn't actually do anything.

Side note:If you don't recognise what that pTHX_ macro is doing at the start of the argument list, don't worry too much about it. It exists to pass around the perl interpreter state if the perl is built with threads enabled. Just think of it as a curious quirk of writing C functions in the perl interpreter; the detail of its operation does not concern us too closely here.

To use this plugin API, we need to define our own custom handling function, and set this variable to its address so that the perl parser will invoke it. This following example implements a trivially tiny plugin; one that declines to process any keyword, but as a side-effect prints its name to the standard error stream, so we can see it in action.

static int MY_keyword_plugin(pTHX_ char *kw, STRLEN kwlen,
    OP **op_ptr)
{
  fprintf(stderr, "Keyword [%.*s]\n", kwlen, kw);
  return KEYWORD_PLUGIN_DECLINE;
}

MODULE = tmp  PACKAGE = tmp

BOOT:
  PL_keyword_plugin = &MY_keyword_plugin;

To test this out, I've compiled this little blob of XS code into a tiny module called tmp. The plugin's output can clearly be seen:

$ perl -Mtmp -e 'sub main { print "Hello, world\n" }  main()'
Keyword [sub]
Keyword [print]
Keyword [main]
Hello, world

Here we can see that the keyword was first informed about the sub. Because we declined to handle it, this was taken by the core perl parser which consumes the main identifier and opening brace in its usual manner. Next up is another candidate for being a keyword, print, which we also decline. The entire string literal does not look like a keyword, so the plugin wasn't invoked here. It is finally informed again of the main that appears at the top-level of the program, which it also declines.

From this initial example, we can see already how the parser plugin API is a lot more robust than earlier mechanisms, such as source filters. We haven't had to take any special precautions against false matches of keywords inside string literals, comments, or anything else like that. The perl parser core itself already invokes the plugin only in places where it expects there to be a real keyword, so all of that is taken care of already.

Hook Chains

The plugin we have created above has one critical flaw in it - it is very rude. It takes over control of the PL_keyword_plugin pointer, overwriting whatever else was there. If the containing program had already loaded a module that wanted to provide custom keyword parsing, our module has just destroyed its ability to do that.

The way we solve this in practice is to wrap the pre-existing parser hook with our own function; saving the old pointer value in a local variable within the plugin code, so if we don't want to handle the keyword we simply invoke the next function down the chain. The perl core helpfully initialises this variable to point to a function that simply declines any input, so the first module loaded doesn't have to take special precautions to check if it was set. It can safely chain to the next one in any circumstance.

We can now update our code to do this:

static int (*next_keyword_plugin)(pTHX_ char *, STRLEN, OP **);

static int MY_keyword_plugin(pTHX_ char *kw, STRLEN kwlen,
    OP **op_ptr)
{
  fprintf(stderr, "Keyword [%.*s]\n", kwlen, kw);

  return (*next_keyword_plugin)(aTHX_ kw, kwlen, op_ptr);
}

MODULE = tmp  PACKAGE = tmp

BOOT:
  next_keyword_plugin = PL_keyword_plugin;
  PL_keyword_plugin = &MY_keyword_plugin;

The plugin now behaves exactly as it did before, but this time if there had been any more plugins loaded before this one, they will be given a chance to run as well. Hopefully the next one that's loaded does this same logic, so that ours continues to work.

Well, I say "work".

Aside from spying on the keywords in the program, this parser plugin doesn't do anything useful yet. I shall start to explore what things the plugin can actually do in part 2.

<< First | < Prev | Next >

2016/06/08

Devel::MAT interactive debugging and filehandles

For a while now, I've been using Devel::MAT for all sorts of debugging tasks. Originally I wrote it in order to track down a single memory-leak case in a large program, but due to the very generic way it just captures as much of the perl process state as it can for later analysis, it turns out to be useful for a variety of other problems as well. Every time I try to debug a new sort of problem that it doesn't quite fit for, I end up adding more features and making a new release, so it's growing in ability quite nicely now.

A recent bug I was trying to fix involved leaking filehandles - a longrunning process ends up running out of spare filehandles and receives EMFILE trying to make a socket(2) call. So, newly added to Devel::MAT version 0.23 is tracking of file numbers associated with IO handles.

To start this session of bug-hunting, first I had to provoke the leak into happening, and capture a .pmat file from it. Provoking the leak proved to be quite easy by just artificially lowering the maximum file descriptor count using ulimit, and capturing the file was achieved using the usual Devel::MAT::Dumper options:

$ ulimit -n 64
$ perl -MDevel::MAT::Dumper=-eager_open,-dump_at_END,-dump_at_DIE ...

Sure enough, it didn't take long running my program before it died because of EMFILE, at which point a .pmat file appeared. Now we can take a look into it and find the problem. So I started by loading this into my new pmat interactive debugging shell, which wraps a number of commandline-type tools, allowing interactive application of them to the loaded file, without having to reload the file each and every time. This speeds up such debugging sessions a lot.

$ pmat run-tests.pl.pmat 
Perl memory dumpfile from perl 5.22.1
Heap contains 156829 objects
pmat> 

The first useful command to run here is io list to obtain a list of every IO SV that has at least one file number associated with it. This will correspond to the filehandles the kernel is complaining that we have too many of. These will be a good place to start to see if something is leaking that shouldn't.

pmat> io list
Addr                           ifileno  ofileno
IO() at 0xa2f378               -1       -1
IO() at 0x8cf540               0        -1
IO() at 0x8cf570               1        1
IO() at 0x8cf5d0               2        2
IO() at 0x16063f8              3        3
...
IO() at 0x3bf8e68              59       59
IO() at 0x3b7e548              60       60
IO() at 0x3bccda8              61       61
IO() at 0x3b57958              62       62
IO() at 0x3b4b950              63       63

Well sure enough, we do seem to have our full allocation of 64 filehandles, and luckily for us they seem to be perl-visible ones (lucky because Devel::MAT can't peek into the inner workings of lower-level C libraries, which could have been the reason here). The first few handles will be the usual STDIN, STDOUT and friends, and some socket handles that the process itself is supposed to be hanging onto, so our leak likely relates to the higher-numbered ones. Lets pick a random candidate near the end, and see if we can investigate further what it's doing still hanging around.

The identify command takes the address of an SV, and tries to walk back up the references chain, looking for what refers to it, so we can find out what's still holding it.

pmat> identify 0x3bf8e68
IO() at 0x3bf8e68 is:
└─the io of GLOB(%*I) at 0x282f118, which is:
  ├─the referrant of REF() at 0x3b7ef98, which is:
  │ └─value {write_handle} of HASH(29) at 0x3b577c0, which is (*A):
  │   └─the referrant of REF() at 0x3476cc0, which is:
  │     └─element [0] of ARRAY(1) at 0x3bbc120, which is:
  │       └─the referrant of REF() at 0x1f81eb8, which is:
  │         └─the lexical $conns of PAD(23) at 0x3bcc658, which is:
  │           └─pad at depth 1 of CODE(PP,C) at 0x3b4c2b0, which is:
  │             └─the referrant of REF() at 0x3bbb358, which is:
  │               └─the lexical $on_closed of PAD(14) at 0x3bcc6a0, which is:
  │                 └─pad at depth 1 of CODE(PP,C) at 0x1cfa850, which is:
  │                   └─the referrant of REF() at 0x3b63698, which is:
  │                     └─value {on_closed} of HASH(29) at 0x3b577c0, which is:
  │                       └─already found as *A
  └─the referrant of REF() at 0x3bf8550, which is:
    └─value {read_handle} of HASH(29) at 0x3b577c0, which is:
      └─already found as *A

This looks suspect. The SV identified with the *A marker appears later on in its own referrant chain. That sounds like a cyclic reference. Lets look at that one in more detail.

HASH(29) at 0x3b577c0 is:
└─the referrant of REF() at 0x3476cc0, which is:
  └─element [0] of ARRAY(1) at 0x3bbc120, which is:
    └─the referrant of REF() at 0x1f81eb8, which is:
      └─the lexical $conns of PAD(23) at 0x3bcc658, which is:
        └─pad at depth 1 of CODE(PP,C) at 0x3b4c2b0, which is:
          └─the referrant of REF() at 0x3bbb358, which is:
            └─the lexical $on_closed of PAD(14) at 0x3bcc6a0, which is:
              └─pad at depth 1 of CODE(PP,C) at 0x1cfa850, which is:
                └─the referrant of REF() at 0x3b63698, which is:
                  └─value {on_closed} of HASH(29) at 0x3b577c0, which is:
                    └─already found circularly

Indeed, this is the classic identify shape of a leaked cyclic reference; a single linear chain of references that loops back onto itself. Just because we have a cycle though doesn't necessarily mean that's bad. Creating a reference cycle in Perl is only bad if nothing ever cleans it up again. Cyclic references can be perfectly safe, provided something cleans them up again at some point. To determine what's wrong with this one and why it didn't get cleaned up requires some inspection of the code that created it. As this particular cycle involves two lexical scalars in two closures we can use the show command lets us see more detail about these two CODE SVs.

pmat> show 0x3b4c2b0
CODE(PP,C) at 0x3b4c2b0 with refcount 1
  name=&Net::Async::HTTP::__ANON__
  stash=STASH(66) at 0x12fe9c0
  glob=GLOB(*) at 0x1b4eaf0
  location=/home/leo/lib/perl5/Net/Async/HTTP.pm line 422
  no scope
  no padlist
  no padnames
  pad[0]=PAD(23) at 0x3bcc658
Referenced globs:
  GLOB(@I) at 0x8b1ea0, GLOB(&*) at 0x1b40bf0

pmat> show 0x1cfa850
CODE(PP,C) at 0x1cfa850 with refcount 1
  name=&Net::Async::HTTP::Connection::__ANON__
  stash=STASH(65) at 0x1a3cac0
  glob=GLOB(*) at 0x1ab35f0
  location=/home/leo/lib/perl5/Net/Async/HTTP/Connection.pm line 62
  no scope
  no padlist
  no padnames
  pad[0]=PAD(14) at 0x3bcc6a0

We can now take a peek at the first of these closures by looking in the source code at the indicated line number; which appears to be the on_closed event handler of the Net::Async::HTTP instance:

      on_closed => sub {
         my $conn = shift;
         my $http = $conn->parent;
 
         $conn->remove_from_parent;
         @$conns = grep { $_ != $conn } @$conns;
 
         if( my $next = first { !$_->connecting } @$ready_queue ) {
            # Requeue another connection attempt as there's still more to do
            $http->get_connection( %args, ready => $next );
         }
      },

Sure enough, there's the $conns lexical that the identification trace suggested was the culprit. Indeed, this code should in fact have removed the connection from that array when it runs, thus breaking the cycle and allowing all these instances to be reclaimed, avoiding a leak. That the leak happened suggests this cleanup code did not in fact execute.

At this point, we can apply some analysis of the code changes leading up to this leak being introduced in the first place. On this occasion, the change was itself a workaround for another bug involving connection pooling and reuse in the HTTP client, by instead using a single-shot HTTP client for each individual request, which is added to the IO::Async::Loop instance and then removed when it is done.

Looking again at the above cleanup code which we expect didn't run, and with knowledge of the code change and the basics of how IO::Async::Notifiers work, we surmise that the code doesn't run because the file handle is never actually explicitly closed. In normal operation with longlived HTTP clients, this isn't a problem as either the client times out and closes the connection itself, or the server does and we're informed of an EOF to close it. These two cases give the on_closed code its opportunity to run, thus avoiding a resource leak in the normal case.

But in our one-shot HTTP client that then gets removed, this never happens. The connection remains open at the point that the client gets removed from the loop, wherein it now has no opportunity to be informed that the server closed it, so the cleanup code never runs. This one now looks like quite an easy fix; just ->close all the remaining connections at the time the client is removed from the loop, by making use of the _remove_from_loop method:

sub _remove_from_loop
{
   my $self = shift;

   foreach my $conn ( map { @$_ } values %{ $self->{connections} } ) {
      $conn->close;
   }

   $self->SUPER::_remove_from_loop( @_ );
}

In fact, this is the very bugfix that was added to make release Net::Async::HTTP version 0.41.

So there we have it - a real-world example of an actual bug that was found and fixed with the help of Devel::MAT.