memory leak in createExprtree

[fserra]

I don't remember why we (or I) decided to use CONST expressions to represent exponents of POW expressions.

So, for instance, to represent z^2 where z is the third variable of some problem, the code is like:

    int nops = 3; 
    CSIP_OP ops[] = {VARIDX, CONST, POW};
    int children[] = {2, 0, 0, 1};
    int begin[] = {0, 1, 2, 4};
    double values[] = {2.0};

see test.c::test_nlp

However, that CONST expression is never used when creating the expression tree, since when creating the POW expression the code looks directly into values:

        case SCIP_EXPR_REALPOWER:
            assert(2 == begin[i + 1] - begin[i]);
            {
                double exponent;
                // the second child is the exponent which is a const
                exponent = values[children[begin[children[begin[i] + 1]]]];
                printf("Seeing a power with exponent %g (nchild %d)\n", exponent, begin[i+1] - begin[i]);
                SCIP_in_CSIP(SCIPexprCreate(SCIPblkmem(scip), &exprs[i],
                                            ops[i], exprs[children[begin[i]]], exponent));
            }
            break;

This of course produces a memory leak, since the created CONST expression is never used, hence, never freed

[rschwarz]

I don't see the memory leak. Is it because nobody frees values? In your snippet, that should be on the stack anyways.

The test you mention is not part of CSIP, is it? Do you have a proposal for a change? Can the exponent of POW also be another, general expression? Otherwise, we might just drop it and let POW have two children.

By the way, I'm again confused by the data structure. Why is the children array of size 4, and not 2 or 3?

[fserra]

To see the memory leak, you have to compile scip with NOBLKMEM=true and then run make valgrind on CSIP

The leak is because of &expr[i], but when creating the CONST expression, not the POW

Can the exponent of POW also be another, general expression?

No, the exponent of POW can only be a number, which the data structure is representing as a CONST, which creates and expr, which doesn't get freed, nor used. The comment says // the second child is the exponent which is a const, but we never use it as a child for POW.

The test is part of CSIP.

An ugly fix is to store which expressions got used while creating the constraint and then free all the ones that were not used. A more elegant would be to not use CONSTs for exponents of POWs

As for the data structure:

    int nops = 3; 
    CSIP_OP ops[] = {VARIDX, CONST, POW};
    int children[] = {2, 0, 0, 1};
    int begin[] = {0, 1, 2, 4};
    double values[] = {2.0};

the children say which are the children of each operator. So, the children of VARIDX is only 2, which means the third variables (starting from 0)
Then, the children of CONST is 0, which is the first entry of values
The, the children of POW is 0 and 1, meaning, the first expr (the VARIDX) and the second expr (the CONST)
This information (of which children belongs to whom) is stored in begin

[rschwarz]

If the CONST is treated specially within creation of POW, could you not also give it special treatment, when the POW expression is freed?

[fserra]

The problem is that POW doesn't know CONST, nobody knows CONST. Here

exponent = values[children[begin[children[begin[i] + 1]]]];

the code is getting the exponent directly from the values array. This, in principle, should be forbidden, and the only one who should have access to the values array is a CONST expression.

However, when creating an expression of type POW I cannot give it an expression for the exponent. And this is the issue. I am using CONST as something it is not supposed to.

So, we can change the data structure so that whenever and operation has type POW then it can refer to the values array. Or, we can leave as it is and after the creation of the expression tree, free all expressions that where created and not used... like the CONST in this case

[rschwarz]

and after the creation of the expression tree, free all expressions that where created and not used... like the CONST in this case

If you can access them like that (and assert that they are CONST), why not :-|

[fserra]

Yes, it is just that we actually don't need the CONST for creating a POW... I can't remember why I did like that :(... maybe was simpler for julia... anyway, that fix is the easiest, since I don't have to touch the julia side, so I'll do that

[rschwarz]

I was just running make test again with both SCIP and CSIP compiled in debug mode. It seems that memory is not freed properly:

  test_nlp
[src/blockmemshell/memory.c:2503] ERROR: 56 bytes (1 elements of size 56) not freed. First Allocator: src/scip/cons_components.c:2466
[src/blockmemshell/memory.c:2503] ERROR: 264 bytes (11 elements of size 24) not freed. First Allocator: src/scip/cons_nonlinear.c:9463
[src/blockmemshell/memory.c:2503] ERROR: 16 bytes (1 elements of size 16) not freed. First Allocator: src/nlpi/expr.c:11977
[src/blockmemshell/memory.c:2503] ERROR: 8 bytes (1 elements of size 8) not freed. First Allocator: src/scip/cons_bounddisjunction.c:3109
[src/blockmemshell/memory.c:2521] ERROR: 344 bytes not freed in total.
  test_quadobj

Is this related to this issue, or maybe a problem in SCIP itself?

[rschwarz]

I have stumbled on the same issue again, as I'm migrating this code to the new SCIP.jl.

I would say that the bug (causing the memory leak) is not a problem in CSIP, but only in the way that CSIP is used. So, really, the data in the test case is wrong, and our MathProgBase code for transforming expressions from Julia to CSIP has the actual issue. There, we need special treatment of power expressions.