Conditions based on uninitialized value in basiclu_obj_initialize() routine

[WalterLu3]

I was doing some testing on your factorization routines. (Specifically, I was doing tests on your basiclu_obj_* routines intead of basiclu_* routines.)

I was doing some factorization examples on simplex method by calling routines in the following order

  The HiGHs basis package contains the following steps
 1. basiclu_obj_initialize : to initialize the object it uses
 2. basiclu_obj_factorize : to factorize a currently given matrix
 3. basiclu_obj_solve_for_update (regular solve) : to get
      the basic feasible direction and rhs is entering column to add.
 4. basiclu_obj_solve_for_update (transpose solve) : to offer
       the column index to replace (leaving column).
 5. basiclu_obj_update : update the factor by the information of
       entering and leaving column in 3 and 4.
 6. can do this repeatedly (so go to 3). (There is an update
       number limit )

The routines work nicely and correctly, but when I run memory check (valgrind) on my small testing program, it has some complaint messages on the initialization routine. I’ve created a small example to reproduce the complaint message. The example just does basiclu_obj_initialize on a basiclu object and immediately free its memory using basiclu_obj_free.

// in order to run this, remember to change the dynamically loaded library to your library path.

#include <stdio.h> 
#include <dlfcn.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "basic_object.h"
#include "basiclu.h"

static lu_int (*dl_basiclu_obj_initialize)(struct basiclu_object*, 
                                           lu_int);

static void (*dl_basiclu_obj_free)(struct basiclu_object*);


int main(int argc, char **argv){
    struct basiclu_object obj ;
    // dimension of the matrix
    lu_int m = 5;

    // dynamically load the highs library
    void *libptr = dlopen("/home/parallels/repos/HiGHS/build/lib/libhighs.so", RTLD_NOW);

    if (libptr == NULL){
        perror("dlopen");
    }

    // initialize the workspace of the factorization
    dl_basiclu_obj_initialize = dlsym(libptr, "basiclu_obj_initialize");

    if (dl_basiclu_obj_initialize == NULL){
        perror("dlsym");
    }


    if (dl_basiclu_obj_initialize(&obj,m) != BASICLU_OK){
        printf("initialize error code : ");
        printf("%d", dl_basiclu_obj_initialize(&obj,m));
        printf("!!!\n");
    }

    dl_basiclu_obj_free = dlsym(libptr, "basiclu_obj_free");

    dl_basiclu_obj_free(&obj);
    return 0;
}

The complete code and headers can be found at https://github.com/WalterLu3/trivial_test/tree/main/test_HiGHS

The commands I run were :

gcc -o test initialize.c
valgrind --leak-check=yes ./test

and the message valgrind returns is the following

==35623== Memcheck, a memory error detector
==35623== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==35623== Using Valgrind-3.19.0 and LibVEX; rerun with -h for copyright info
==35623== Command: ./test
==35623== 
==35623== Conditional jump or move depends on uninitialised value(s)
==35623==    at 0x509A498: lu_load (in /home/parallels/repos/HiGHS/build/lib/libhighs.so.1.6.0)
==35623==    by 0x509ABFF: lu_initialize (in /home/parallels/repos/HiGHS/build/lib/libhighs.so.1.6.0)
==35623==    by 0x50A64DF: basiclu_obj_initialize (in /home/parallels/repos/HiGHS/build/lib/libhighs.so.1.6.0)
==35623==    by 0x10892F: main (in /home/parallels/repos/trivial_test/test_HiGHS/test)
==35623== 
==35623== Conditional jump or move depends on uninitialised value(s)
==35623==    at 0x509A4A0: lu_load (in /home/parallels/repos/HiGHS/build/lib/libhighs.so.1.6.0)
==35623==    by 0x509ABFF: lu_initialize (in /home/parallels/repos/HiGHS/build/lib/libhighs.so.1.6.0)
==35623==    by 0x50A64DF: basiclu_obj_initialize (in /home/parallels/repos/HiGHS/build/lib/libhighs.so.1.6.0)
==35623==    by 0x10892F: main (in /home/parallels/repos/trivial_test/test_HiGHS/test)
==35623== 
==35623== 
==35623== HEAP SUMMARY:
==35623==     in use at exit: 86,841 bytes in 22 blocks
==35623==   total heap usage: 422 allocs, 400 frees, 182,755 bytes allocated
==35623== 
==35623== LEAK SUMMARY:
==35623==    definitely lost: 0 bytes in 0 blocks
==35623==    indirectly lost: 0 bytes in 0 blocks
==35623==      possibly lost: 0 bytes in 0 blocks
==35623==    still reachable: 86,841 bytes in 22 blocks
==35623==         suppressed: 0 bytes in 0 blocks
==35623== Reachable blocks (those to which a pointer was found) are not shown.
==35623== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==35623== 
==35623== Use --track-origins=yes to see where uninitialised values come from
==35623== For lists of detected and suppressed errors, rerun with: -s
==35623== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

At a closer look, it is complaining that lu_load is having if-conditions that are dependent on variables that do not have initialized values. To be more specific, the following two if-conditions in lu_load lead to this message (in lu_internal.c):

if (this->marker > LU_INT_MAX-4)
{
   …
}
if (this->nupdate >= 0)
   …
else
   …

Since this->marker = xstore[BASICLU_MARKER] this->nupdate = xstore[BASICLU_NUPDATE]

valgrind is expecting xstore[BASICLU_MARKER] and xstore[BASICLU_NUPDATE] to have initialized values, but in the calling hierachy

basic_obj_initialize -> lu_initialize -> lu_load,

the lu_initialize routine does not initialize those two.

This issue does not appear when you use basiclu_initialize because users have to feed in their own xstore, and that in HiGHS code before basiclu_initialize is called, you run xstore_.resize so that the xstore vector actually has default value 0 (in src/ipm/ipx/basiclu_wrapper.cc).

I believe this is a quick fix with just adding some additional initializations of xstore in the lu_initialize routine or in the basiclu_obj_initialize routine. I saw that somewhere in HiGHS code you also called basiclu_obj_initialize although you do not use BasicluKernel as your default basis method. (I believe this is hidden in the constructor of the BasicLuHelper class, which is used as the factorization method of the ForrestTomlin class for LU update.)

Overall, I really like the basic_obj_* routines as they provide really nice interface for users who want to use basis routines, and I hope my feedback is helpful for your team.

[jajhall]

Thanks for this. I'll look at it in due course. Note that HiGHS has two sets of simplex linear algebra. In addition to basiclu (written for the interior point solver) there is also the HFactor class (written for the simplex solvers). Since I suspect that the HFactor class is (possibly only marginally) more efficient, I was going to replace the use of basiclu with use of the HFactor class.

[WalterLu3]

Thanks. Since I mainly write my applications in C, when I first looked at HiGHS code base, I directly looked for the basis routines that are exposed for C. What kind of basis factorization method and basis update method does HFactor use?

[jajhall]

HFactor uses triangularization followed by Markowitz for factorization, and then an efficient implementation of Forrest-Tomlin for basis update. HFactor isn't as simple as basiclu, as it's had a lot more added so that it can be called in different parts of HiGHS, handle rectangular matrices, and deal with changes in size of the basis matrix etc.

[WalterLu3]

Sounds amazing. By the way, I can also work on a patch for this issue if it is helpful for you. All the best.