Open sfstewman opened 4 years ago
I'm not familiar enough with sid's error handling to know the best way to fix this.
One approach that essentially bypasses sid would be to create an "arena" for allocating AST nodes at each parse. The arena would essentially be a bump allocator. On an error or a call to ast_free
, every object in the arena would be freed.
Looking at the first few backtraces I wonder if there's a ast_free
missing if ast_rewrite
fails in https://github.com/katef/libfsm/blob/main/src/libre/re.c#L116-L118.
For the error in src/re/main.c:653
there's a fsm_free
missing in all error exits (return EXIT_FAILURE;
) in https://github.com/katef/libfsm/blob/main/src/re/main.c#L659-L990.
So no real need for a pooled allocator, when you just ensure allocated resources are free'd on all error paths.
Looking at the first few backtraces I wonder if there's a
ast_free
missing ifast_rewrite
fails in https://github.com/katef/libfsm/blob/main/src/libre/re.c#L116-L118.
There is an ast_free
missing there, but if parsing fails, it never gets to that point. The leaks reported here are in the parser itself.
I'm not familiar enough with sid's error handling to know the best way to fix this.
It is possible to define in parser.act
:
%actions%
<fail> = @{
@!;
@};
<ast-free>: (node :ast_expr) -> () = @{
ast_expr_free(@node);
@};
Then, in the various parser.sid
files, ensure that any rule that can potentially fail after an allocation is wrapped to produce this pattern:
node = ...;
{
...
##
<ast-free>(node);
<fail>();
};
This is similar to C++'s try { ... } catch { ast_expr_free(node); throw; }
, although of course C++ has other ways to avoid the need for this.
Thanks for the idea @hvdijk! @katef also mentioned that. The downside is that the sid code ends up littered with try/catch blocks, and if you miss one you still have a leak.
I'm proposing #252 as an alternative. It's not quite complete (the thread safety bit), but it's less invasive overall.
The (imo minor) downside is that you don't release the AST nodes immediately, which could cause memory pressure if the regular expression is exceptionally large. We can improve this with a free list, but it's a fundamental downside of pooling allocation and releasing all at once. I think that's a worthwhile trade-off for the AST. Even large regular expressions have relatively small ASTs.
Looking at the first few backtraces I wonder if there's a
ast_free
missing ifast_rewrite
fails in https://github.com/katef/libfsm/blob/main/src/libre/re.c#L116-L118.For the error in
src/re/main.c:653
there's afsm_free
missing in all error exits (return EXIT_FAILURE;
) in https://github.com/katef/libfsm/blob/main/src/re/main.c#L659-L990.So no real need for a pooled allocator, when you just ensure allocated resources are free'd on all error paths.
The failure happens well before ast_rewrite. The sid parser hits an error. In this case, \c
is currently unimplemented and the error is triggered by the <err-unsupported>
action.
Thanks for the idea @hvdijk! @katef also mentioned that. The downside is that the sid code ends up littered with try/catch blocks, and if you miss one you still have a leak.
I'm proposing #252 as an alternative. It's not quite complete (the thread safety bit), but it's less invasive overall.
That is true, it is easy to miss a spot.
The fundamental problem is that the parser stores state in local variables, but sid does not appear to provide a way to automatically invoke cleanup actions when any local variable is discarded because of an error condition. There are three ways around that: use a parser generator that does support that (that could still be sid, if it does have this functionality hidden somewhere, if its output were to be interpreted as C++ code or using GCC/clang's cleanup
extension, or if sid were extended), manually write all the cleanup actions (what I suggested), or finding a way to keep track of allocated expressions that works even when variables are discarded (like you did).
Keeping track of all allocations in a separate list is certainly a nice, correct and easy to implement approach as well (without inspecting your PR in detail), and by pooling expressions together like you did, you reduce a lot of the overhead.
Another way to keep track of allocated expressions is to never return pointers that are not attached to a tree, by making actions take enough info so that whenever a new node is constructed, it can be attached to the tree immediately, even if further processing is going to fail. This would make it hard to miss a spot, but the downside of that is that it is possibly an even more invasive change.
The (imo minor) downside is that you don't release the AST nodes immediately, which could cause memory pressure if the regular expression is exceptionally large. We can improve this with a free list, but it's a fundamental downside of pooling allocation and releasing all at once. I think that's a worthwhile trade-off for the AST. Even large regular expressions have relatively small ASTs.
When constructing ASTs manually though, not from a regex, it is possible to repeatedly create and destroy expressions before the construction is complete. In that case, it becomes more important to not keep allocating more and more memory. This is not something the parser does, but it is something I am doing on a branch I have not (yet) created a PR for. I think your PR would be easy to extend to support that, so please do not take this as an argument against the pool approach :)
(I accidentally edited your comment instead of replying, sorry about that! Let me try to fix that...)
A quite decisive argument against a pool allocator is that it interferes with normal memory checker instrumentation and may hide buffer overread, double-free and uninitialized memory read/write issues. A famous example of this was the OpenSSL Heartbleed bug.
The only real upshot for a pool allocator that I see would be the reduction of memory management calls, which could mean a large win on performance for large expressions.
On the other side: Keeping the allocator as is and writing a small tool to construct ASTs from some input string (and freeing it again) is an easy task which can be combined with a fuzzer like AFL+ to find memory leak issues in the AST construction code easily.
Thus going forward I'd lean more towards trying to get the generated parser code right (and have tooling to check this), than to risk hiding those bugs.
@BenBE you're probably right about missing points where we should free, but don't currently (unrelated to the leaks during bad parses). I know I cut some corners for those. We should definitely be doing that properly as far as each program's main.c goes, regardless.
Doing this in the parser: if actions in the parser are rewritten to take :ast_expr &
reference parameters, instead of returning :ast_expr
by value, it is possible to avoid a lot of the cleanup that would otherwise be needed and structure it in a way that makes it easy to verify it covers all cases. I have put up a proof of concept that implements this only for the PCRE parser as https://github.com/hvdijk/libfsm/commit/06078792f29c60002fdb42c955e30321869ce95c. The idea is that the :ast_expr &
parameter is guaranteed to be cleaned up by the caller, so does not need to be handled by the code that causes it a node to be constructed. There are only a few places that do node = <ast-expr>;
, and for those places, it is easy to inspect that they guarantee either that an action will be invoked that takes over the responsibility to manage node
, whether by inserting into the tree or by freeing it on error. (The option for pooled allocations may still be a good one; it mainly just did not sit right with me that sid would have such a fundamental limitation.)
A quite decisive argument against a pool allocator is that it interferes with normal memory checker instrumentation and may hide buffer overread, double-free and uninitialized memory read/write issues. A famous example of this was the OpenSSL Heartbleed bug.
@BenBE, I appreciate you taking the time to comment. It's clear that you feel passionately about this. IMO, few things in software lead to a "quite decisive argument." Mostly we just live in the world of trade-offs, and an offline FSM manipulation package focused on DFA transformation and codegen will make different choices than OpenSSL.
In terms of the downsides you list, consider that they're less a problem in this codebase than in others:
ast_expr_release()
if becomes useful for AST rewriting, but as of right now, the rewriting rules are fairly limited in scope, and I didn't see an upside to adding release and free list.calloc
for allocation, which has the upside of initializing the values to a known quantity and the downside of defeating checks for uninitialized memory.Custom allocators are also quite common, which is why ASAN and other instrumentation tools provide hooks that otherwise reduce or eliminate the downsides you mention. It would certainly be good for us to use these hooks in the places we have custom allocation when building with ASAN enabled.
The only real upshot for a pool allocator that I see would be the reduction of memory management calls, which could mean a large win on performance for large expressions.
I would consider these to be the upsides:
/[foo/
in the PCRE dialect).sid
code (both act and sid files) with lots of ##
error handling cases. This strikes me as a maintenance nightmare. I haven't looked closely at @hvdijk's alternative, which sounds promising but does seem to invert the natural flow of allocation. Both of these require quite a few changes to the structure of all existing parsers.On the other side: Keeping the allocator as is and writing a small tool to construct ASTs from some input string (and freeing it again) is an easy task which can be combined with a fuzzer like AFL+ to find memory leak issues in the AST construction code easily.
We're actively fuzzing the code for various things. LSAN checking would be another good thing to add to the list.
However, you don't have to fuzz the code to find obvious leaks. I'm still chasing down leaks that LSAN finds in the current build+tests outside of parsing.
Thus going forward I'd lean more towards trying to get the generated parser code right (and have tooling to check this), than to risk hiding those bugs.
As always, please feel free to file a PR that addresses this bug in a way that you would prefer. I find it a lot more helpful to have technical arguments about concrete code.
@hvdijk thanks for the POC there, that's super helpful.
It seems like there are two things going on in your diff;
free()
happens to inside each action;- <ast-make-group>: (e :ast_expr) -> (node :ast_expr) = @{
+ <ast-make-group>: (node :ast_expr &, e :ast_expr) -> () = @{
Since node
there is already a pointer type, I'm not sure I understand (2). What does introducing the reference give us? Unless I misunderstand, I think we could do (1) (and destructively free arguments) without switching to references.
The idea is that after node = <ast-expr>();
, node
is a null pointer. No expression is constructed yet at that point, this merely declares that node
is a local variable in which an expression can be held. It's when <ast-make-xxx>(&node);
is invoked that node
gets assigned a non-null value. If you pass node
by value, that does not work: an expression would be created, but after <ast-make-xxx>(node)
would be done, node
would still be a null pointer.
I'm not sure I follow. If we're returning -> (node :ast_expr)
wouldn't we bind that to a new variable in the .sid file?
a = <ast-expr>; // NULL
b = <ast-make-group(a); // would free a on error, per the idea for (1)
I think I see why you're doing this - do you then continue with the parse, after an allocation failure? Just passing around the reference to NULL
?
Excuse me thinking aloud here, two alternate ways to get the idea of failing exposed:
<ast-make-group>: (e :ast_expr) -> (e :err, node :ast_expr);
. I don't like this, of course.@!
in an action (meaning an allocation error, not just a syntax error). Then still returning just -> (node :ast_expr)
, and NULL
is an in-band value.The exceptions bubble up, so we don't need an ##
alt for every production. But we would need to be sure we hadn't allocated something else in the same alt:
x = <f>;
y = <g>; // when <g> raises @!, we need to free `x`
We could handle just those cases explicitly perhaps, by wrapping them locally. But that's super messy.
I don't like the idea of a grammar file having to know about memory allocation at all. Its purpose is to describe a grammar, and this gets in the way.
I think I see why you're doing this - do you then continue with the parse, after an allocation failure?
After an allocation failure I still end the parse as before. I'm doing this to significantly reduce the number of places we need cleanup actions, and to make the locations where we need cleanup actions easily identifiable with a simple search, to address @sfstewman's concern that it would otherwise be too easy to miss a cleanup action and still end up with a leak on certain hard to find inputs (and it's good to be concerned about that!).
Returning an error status:
That could be a good idea too. The exceptions discard the local variables without performing any cleanup actions, so if we can avoid exceptions entirely, we can avoid using cleanup actions to handle the local variables being discarded.
I don't like the idea of a grammar file having to know about memory allocation at all. Its purpose is to describe a grammar, and this gets in the way.
I agree! Ideally this would be purely part of parser.act
, where somehow we would specify what happens when an :ast_expr
is discarded. Unfortunately sid does not support this, so we have to manually write code to track the variables. We can either do that inside the parser or outside of it. The pooling PR shows how this can be done outside of it, I am trying to show how it can be done inside of it.
I agree! Ideally this would be purely part of
parser.act
, where somehow we would specify what happens when an:ast_expr
is discarded. Unfortunately sid does not support this, so we have to manually write code to track the variables. We can either do that inside the parser or outside of it. The pooling PR shows how this can be done outside of it, I am trying to show how it can be done inside of it.
It's good to see how sid
can be adapted to this! The problem does make me wish (yet again...) that C had something like RAII or defer for things like this. I'm not sure which approach I prefer. I think the pooling PR (with some revisions) may be simpler, but this approach is certainly more in keeping with the rest of the libfsm.
Oh! This is a bit nasty, but we do actually have a way to run cleanup code without modifying sid: all sid-generated exceptions are guaranteed to be preceded by the RESTORE_LEXER
macro, which we can hook into! Then it's just a matter of ensuring the same cleanup code is also run anywhere we explicitly invoke @!
. This would allow us to avoid the need for explicit <ast-free>
in the parser.sid
files. I will attempt to update my POC to implement this!
Oh dear :)
where somehow we would specify what happens when an
:ast_expr
is discarded.
Do you think we could add this to sid somehow? There are similar %sections% for implementing copying, %assignments%
, etc. Maybe we could have one for destructors? Maybe that's just too much work.
I do like the references idea, I want to be clear about that.
Here's the RESTORE_LEXER
hack: https://github.com/katef/libfsm/commit/8dfe6124892aa18b826c9193f8c265f3aa6d26e9 (comment edited to point to an updated version) ! This builds on the refcounted expression trees I had already implemented on another branch. Beware, it's still a work in progress, it's not fully correct yet.
Do you think we could add this to sid somehow? There are similar %sections% for implementing copying, %assignments%, etc. Maybe we could have one for destructors? Maybe that's just too much work.
This should be relatively easy to add to sid for someone already familiar with its internals!
This is really quite an incredible diff. I'm amazed that it works.
Yeah, it is quite nasty. It manages to keep a relatively clean parser.sid though, so it does have that going for it.
Okay, well thank you everybody for all the input here.
I could imagine adding a %destructors%
style section to sid, to provide action for freeing each type. But honestly I don't want to put the work into that, when somehow we haven't managed to need it so far. I did a lot of work on sid some time ago, and going back to that feels like such a digression from what I want to be doing now.
The pool allocation system gets my vote, so far. Mostly because I think it's the simplest to understand, and perhaps the most maintainable idea without raising the barrier for concepts that're strange and difficult for new people. If we ever want to replace it in the future, it's easy to see where it is, what it does, and what its surface area touches.
I do need it to be thread safe though, so let's pass in a handle for a pool, rather than the global_pool
at file scope.
Thanks for trying out the proof of concepts here, I'm finding it difficult to think clearly at the moment, and seeing those laid out really does help.
@katef sounds good. I do like the idea of a %destructors%
section, but I also have no desire to learn enough of the insides of sid
to design or implement it.
I'm still hunting other leaks, but as soon as I reach a good stopping place, I'll clean up the pooled allocation scheme:
-DASAN
is used. This isn't a perfect solution, but should help with many of the issues that @BenBE has raised.I could imagine adding a
%destructors%
style section to sid, to provide action for freeing each type. But honestly I don't want to put the work into that, when somehow we haven't managed to need it so far. I did a lot of work on sid some time ago, and going back to that feels like such a digression from what I want to be doing now.
Yeah, that makes sense. The main reason it has not really been a problem is that sid-generated parsers are almost always part of a utility where if parsing fails, the utility will abort fairly quickly and free any lingering resources implicitly, but here it is part of a library, so that logic does not hold.
Just a note on %destructors%
if that is implemented at some point in the future: it may be easiest to do if %constructors%
are added as well. This would simplify the implementation: sid could run a constructor action whenever a block is entered and a destructor action whenever a block is exited, without keeping track of whether the variable has been assigned to yet.
I just had a realisation that there is another way to keep track of constructed nodes, without a pool, without sid extensions, and without resorting to hacks: just keep a list of nodes that have been constructed but not yet attached to any other node, and update that list when attaching to other nodes, like so: https://github.com/hvdijk/libfsm/commit/87aaad11221f0a049b08432fad54f821b8e714b7 This only modifies ast.h
to add a single new field, and parser.act
, everything else is left intact, tests pass, and valgrind reports no leaks for any of the syntax error tests in the test suite. (As before, I'm not saying this is better than the pool, I wanted to see that it could be done.)
@hvdijk I really like that idea, more than the pool
When the
sid
parser encounters an error, it does not appear to free any partially-constructed pieces of the AST tree.I found this working with
cvtpcre
with ASAN enabled, but it's easily triggered withre
if ASAN is enabled:Except for the 4096-byte
struct fsm
allocation, all of the allocations are done within thesid
parser, and all are partial allocations of the