cjdrake / pyeda

Python EDA
BSD 2-Clause "Simplified" License
305 stars 55 forks source link

Segmentation fault in _orand_simplify #120

Closed lorek123 closed 9 years ago

lorek123 commented 9 years ago

I'm trying to extend the capability of sudoku solver to solve bigger puzzles. Unfortunately when i tried to create SudokuSolver for n=5 i'm getting:

from solver import SudokuSolver a = SudokuSolver(5)

Program received signal SIGSEGV, Segmentation fault. 0x00007ffff52f4b93 in _orand_simplify (op=0x5146220) at extension/boolexpr/simple.c:142 142 uniq[uniq_len++] = flat[i];

Could anyone help me with this bug? Here is the code https://gist.github.com/chaosk/d94a9855c727e830847a#file-solver-py

cjdrake commented 9 years ago

Thanks for the bug report. Are you using version 0.27.4, or master branch?

As a work-around, trying using version 0.26.0. Do something like pip install pyeda==0.26.0. The expressions in that version are pure Python.

cjdrake commented 9 years ago

You are constructing a very large expression here with N=5. I suspect the bug might be related to how in OR/AND simplification, two arrays are being allocated on the stack. I changed the flat and uniq array allocation to the heap, and N=5 didn't fail anymore.

cjdrake commented 9 years ago

I added a patch you can try on bugfix-120 branch.

lorek123 commented 9 years ago

thanks for patch, it's working for n=5 but it segfault for n=6:

from solver import SudokuSolver a = SudokuSolver(6)

Program received signal SIGSEGV, Segmentation fault. 0x00007ffff52f4679 in ExprNode_data (self=0x7ffff2cb67d0) at pyeda/boolalg/exprnodemodule.c:614

cjdrake commented 9 years ago

Looks like it might be a similar problem. The code in question is using a dynamic allocation on the stack:

        int i, j;
        ExprNode *nodes[self->ex->data.xs->length];
        PyObject *xs;

        for (i = 0; i < self->ex->data.xs->length; ++i) {
            nodes[i] = (ExprNode *) PyObject_CallObject((PyObject *) &ExprNode_T, NULL);
            if (nodes[i] == NULL) {
                for (j = 0; j < i; ++j)
                    Py_DECREF(nodes[j]);
                return NULL;
            }
            nodes[i]->ex = BoolExpr_IncRef(self->ex->data.xs->items[i]);
        }

Possibly a blanket bug title would be "stop doing dynamic allocations on the stack". Will provide a patch soon.

cjdrake commented 9 years ago

I pushed a couple commits on master, and updated the issue-120 branch. I tested that it works for both N=5 and N=6. The N=6 case took a few seconds for my laptop to complete :).

lorek123 commented 9 years ago

yeah, it's working now but not all fixes from branch "issue #120" are pushed to master. I know that it's time consuming, but for test purposes it's fine. Do you plan to add support for pickle for this project? It would be cool to save some of objects that are using pyeda to file.

cjdrake commented 9 years ago

The patch in issue-120 is not a complete fix, so I haven't merged it. I'm actually in the process of changing the simplification code right now. It should be faster for larger expressions such as yours, and it will get rid of the type of dynamic stack allocation that is causing the problem here.

As for pickle support, I haven't considered it yet. Feel free to write a new issue to describe the feature and usage. I definitely sounds like a worthwhile effort.

cjdrake commented 9 years ago

Just merged the changes into master. Getting to N=7 started maxing out my laptop's memory, but didn't segfault or leak memory.