pacc logo


You might expect, from the previous post, that I've been beavering away at converting an existing grammar to pacc. But you'd be wrong.

What I have been doing is cooking up a brand new grammar from scratch. Well, almost from scratch. As it happens, I already had the beginnings of a PEG parser for the language in question, written for Ian Piumarta's leg (a generator of recursive descent parsers from PEGs, and the direct inspiration for pacc). Yes, I am returning to The Project from which pacc is essentially a very long tangent. The Project has recently been named quux. (I do think pacc is more important than quux, although at present quux is at that delicious stage where the low-level stuff is in place, but none of the high-level stuff is set in stone, and it can be endlessly tweaked.)

Anyway, as usual trying to do new things with pacc reveals new bugs. And then (just before I went away for a week on holiday) I found what seemed to be a very odd heisenbug. Pacc appeared to be trying to allocate an absolutely enormous amount of memory. That was because a ref_t value had ended up with its start after its end! Running under gdb though, to try and find the problem, the bug vanished. It's a long time since I've had a proper heisenbug.

Fortunately, we have valgrind, and it didn't take me too long at all to find that I was using memory that had been realloc'd. And a little bit more playing led me to this test case:

P ← a:Number b:Number { a * b }
  / w:Word c:Number { c * strlen(ref_dup(w)) }

Number ← "five":Word { 5 } / "six":Word { 6 }

Word :: ref_t ← w:[a-z]+ " "* -> w

Remember that bound literals are implemented using semantic guards, so the Number rule is desugared to something like this:

Number ← _pacc_bl127:Word &{ ref_streq(_pacc_bl127,"five") } { 5 } / ...

Consider what happens with an input like "eight six". We successfully match "eight" against Word. Then the semantic guard kicks in, and we switch from parsing to evaluating long enough to bind _pacc_bl127. Since this is a ref_t, it's actually a pointer into the appropriate pacc_mid structure.

The semantic guard fails, and we're back to parsing. This will inevitably involve allocating more pacc_mid structures, by extending a hash bucket. Since hash buckets are malloc'd arrays, we need to realloc. This moves the pair of the values that our ref_t is pointing to, but of course the pointer doesn't get updated, and chaos ensues.

So how are we going to fix this? I've had several ideas. Let's start with a silly one. We keep track of every ref_t value. Every time we're about to reallocate a block, we scan each ref_t and see if it points into this block. If it does, update it after the block has moved. This could work, but it's far too much mechanism.

Here's a much more reasonable idea. Instead of ref() simply returning a pointer into the current pacc_mid structure, it could copy the 2 size_t values into a freshly allocated array, and return (a pointer to) that instead. This should work fine, and would be easy to implement. I have two minor misgivings. First, it makes ref() much more expensive than it currently is:

#define ref() (&cur->col)

The other snag is that (in an ideal world) something or other would eventually free that memory. Now, I'm aware that I have a general problem with freeing memory already, and this doesn't make it much worse. Still, I'm not happy with having pacc itself allocating memory that it doesn't know how to free. (I suppose I could keep a list of it all and do it.)

Taking a step back, why is this memory being moved anyway? Were this a university project, hash buckets would be implemented as a linked list, and the issue simply would not arise. The reason it's not is that I believe linked lists are disastrous for performance: every single element of the list is likely to involve a CPU cache miss and page fault. I don't think preferring vectors to lists is premature optimization.

But, what about a list of vectors? We could allocate a block of pacc_mid structures. When they've all been used, allocate a new block and link it to the last one. Nothing ever moves, and we avoid both the problem of invalid pointers, and the copying overhead. (In an ideal, ideal world, each block would be aligned on something that helps with caches, such as a 4k boundary. There are probably glibc-specific ways to do this, or perhaps it could be done with mmap(), but that's something to tackle another day.)

Let's give it a go. The next post describes the new implementation.

Last updated: 2015-07-19 07:17:18 UTC


Porting and packaging

One thing pacc needs is more users. And, perhaps, one way to get more users is to reduce the friction in getting started with pacc. An obvious lubricant is packaging. Read More...

Release relief

Looking at _pacc_coords(), I noticed that it seemed to have the same realloc() bug that I'd just fixed in _pacc_result(). However, the "list of arrays" trick really wasn't going to work here. Read More...

See more news articles