bugGNU Octave - Bugs: bug #66961, nchoosek crashes Octave

 
 

bug #66961: nchoosek crashes Octave

Submitter:  Andreas Bertsatos <pr0m1th3as>
Submitted:  Sat 29 Mar 2025 01:13:14 AM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Segfault, Bus Error, etc.
Status:  None Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * 10.1.0 Release: 
Operating System:  * GNU/Linux Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Mon 31 Mar 2025 12:17:40 PM UTC, comment #16: 

See also jwe's comment on a similar issue on Discord:
https://octave.discourse.group/t/octave-crashes-when-out-of-memory/4339/7

Markus Mützel <mmuetzel>
Group administrator
Sun 30 Mar 2025 11:36:46 AM UTC, comment #15: 

No. Malloc and OOM are different things. To get killed by OOM you need to actually "consume" the memory. And is a long (time-wise) process.

You can try to set /proc/sys/vm/overcommit_memory to "2" in your computer (so you disable overcomit and will start to get "error: out of memory or dimension too large for Octave's index type" sooner), but I cannot mathematically proof that it would guarantee you against  OOM kills.
As root:

echo 2 > /proc/sys/vm/overcommit_memory

To make it permanent you need to add it to /etc/sysctl.conf
(read "man sysctl.conf" for details).

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Sun 30 Mar 2025 11:05:10 AM UTC, comment #14: 

The only way we could circumvent this whole issue is to test malloc by spawning a child process and check whether it is killed or not and then do the actual malloc or return an error about memory limitation.

Of course, this would add some overhead, which I don't know how much it costs in terms of processing time. Nevertheless, it is the only secure way to ensure that OOM does not kill Octave when trying to allocate more memory than it is available.

I have no clue where and how such a patch would be applied. Is there a central place/function in Octave code for allocating memory for new variables in workspace?

Andreas Bertsatos <pr0m1th3as>
Sat 29 Mar 2025 05:32:39 PM UTC, comment #13: 

I think even with 64-bit indexes malloc would refuse to allocate a too large of memory. It depends on kernel tuning parameters starting with "/proc/sys/vm/overcommit_memory".
On my machine (with 32 Gb of RAM) "~2^44" appears to be the limit where malloc returns NULL.

 octave:5> a=zeros(2^44,1);
error: out of memory or dimension too large for Octave's index type
octave:6> a=zeros(2^43,1);
^C^Z[2]   Killed                  octave


For your try/catch in case of "nchoosek(1:50,10)" it tries to do zeros(2^33,1) (approximately)
and fails on your computer, but on mine it succeeds  and proceeds to eat RAM and gets killed by OOM.

Dmitri.
--


Dmitri A. Sergatskov <dasergatskov>
Sat 29 Mar 2025 04:49:23 PM UTC, comment #12: 

What do you mean by "forces Octave to quit"?
Is octave gets killed?

It works for me:

octave:1> a=zeros(2^32);
error: out of memory or dimension too large for Octave's index type
octave:2> a=zeros(2^32,1);
octave:3> a(2^32)
ans = 0


Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Sat 29 Mar 2025 04:43:26 PM UTC, comment #11: 

Yes, it is enableed

>> __octave_config_info__.ENABLE_64
ans = 1
>>

and no, "zeros (2^32, 1)" forces Octave to quit, even if no other variable is present in the workspace.

Andreas Bertsatos <pr0m1th3as>
Sat 29 Mar 2025 03:18:55 PM UTC, comment #10: 

Dis you enable 64-bit indexing?
What does " _octave_config_info_.ENABLE_64" return on your computer?
Does "zeros(2^32,1)" give you the same "requested array exceeds maximum possible variable size" error?

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Sat 29 Mar 2025 08:52:37 AM UTC, comment #9: 


comment #7:

> My point was that "c = nchoosek (1:50, 10);" most likely would crash your octave w/ or w/o your patch.


No, it does not

>> c = nchoosek (1:50, 10);
error: nchoosek: requested array exceeds maximum possible variable size
error: called from
    nchoosek at line 192 column 7


comment #8:

> What is the error message of the error that is caught in that case?


The error returned by "try...catch" block is

>> c = nchoosek (1:50, 10);
error: out of memory or dimension too large for Octave's index type
error: called from
    nchoosek at line 190 column 9


After some trial and error, I realized that Octave probably does some heuristics about max system memory but not available memory. For example

>> c = zeros (70000);
error: out of memory or dimension too large for Octave's index type
>> c = zeros (60000);
>>

The 60000x60000 load in my system's memory, but if I run the same command once more, then Octave is killed.


Andreas Bertsatos <pr0m1th3as>
Sat 29 Mar 2025 08:22:17 AM UTC, comment #8: 

Well, an increase in runtime of about 20% is hardly insignificant.

The fact that this check is only ever needed on some (or most?) Linux system means to me that there should be at least some kind of check whether the function should be made 20% slower.

1000000000000000000 is approx. 2^60. Your example tries to allocate an array with approx. 2^120 double precision floating point elements. That is well above the address space limit on 64-bit systems.

I agree with Dmitri in that it is easy to check whether the number of elements in an array are larger than the addressable memory (usually the 64-bit address space now-a-days). But it is less easy to check whether we would run into out-of-memory issues. Especially, if the OS is "lying" (over-provisioning) to Octave.

I haven't looked into the details of what is happening in this particular case. But I have a feeling that your patch only "accidentally" prevents an OOM situation.
What is the error message of the error that is caught in that case?

Markus Mützel <mmuetzel>
Group administrator
Sat 29 Mar 2025 08:08:56 AM UTC, comment #7: 

For "zeros(1000000000000000000)" it is easy to calcultate the total number of elements and refuse the operation is it exceed 2^32-1. It is not so easy for "nchoosek(SET,b).

My point was that "c = nchoosek (1:50, 10);" most likely would crash your octave w/ or w/o your patch.
 
Dmitri.
--


Dmitri A. Sergatskov <dasergatskov>
Sat 29 Mar 2025 07:51:59 AM UTC, comment #6: 

"c = nchoosek (1:50, 10);" crashes my system without the patch.

However, I tried with somewhat smaller array and I get the following timings (before and after the patch is applied)

>> tic; c = nchoosek (1:30,10); toc
Elapsed time is 5.03854 seconds.
>> tic; c = nchoosek (1:30,10); toc
Elapsed time is 6.16953 seconds.

I understand that this ~1.15 seconds is not insignificant, but keep in mind that this is very near the memory limit of my 32GB system. So, it's quite a large array. For smaller arrays, I get the following timings with the patch applied

>> tic; c = nchoosek (1:10,10); toc
Elapsed time is 0.00012207 seconds.
>> tic; c = nchoosek (1:20,10); toc
Elapsed time is 0.0390401 seconds.
>> tic; c = nchoosek (1:25,10); toc
Elapsed time is 0.678122 seconds.

Without the patch, I get

>> tic; c = nchoosek (1:10,10); toc
Elapsed time is 0.000125885 seconds.
>> tic; c = nchoosek (1:20,10); toc
Elapsed time is 0.031872 seconds.
>> tic; c = nchoosek (1:25,10); toc
Elapsed time is 0.555607 seconds.

IMHO, the overall overhead is insignificant in order to avoid a sudden exit, which might result in loosing your workspace and possibly other unsaved data in editor. From this point of view, whether it is an Octave crash or a system forced kill, is kind of irrelevant.

Apparently, it appears that my system does not kill Octave when I am trying to exceed memory allocation with 'zeros' and Octave gracefully handles this. That's why I used it in my "try...catch" workaround.
+verbatim

>> zeros(1000000000000000000)

error: out of memory or dimension too large for Octave's index type
-verbatim-
So there is something Octave is doing differently between the two cases, because with the "zeros" function, it catches the error and does not allow linux to kill it.

Andreas Bertsatos <pr0m1th3as>
Sat 29 Mar 2025 07:19:43 AM UTC, comment #5: 

I don't see a crash with Octave 10 on Windows:

>> c = nchoosek (1:50, 30);
error: out of memory or dimension too large for Octave's index type
error: called from
    nchoosek at line 195 column 7
>>


These kinds of "crashes" are a result of two factors that are present in the configuration of most Linux systems (unfortunately):

  • overprovisioning: The OS just ignores if memory allocations requested by any program are very large (larger than the currently available memory). It just assumes that there will be enough available memory when the allocated memory will finally be used (or the allocated memory won't be used in its entirety anyway). So, instead of failing the memory allocation (which could be detected by Octave), Octave has no way of knowing that the memory is low.
  • OOM killer: Most Linux distributions are using a service that is permanently checking if the system memory is getting low. That service is the out-of-memory killer. When the OOM killer detects that memory is getting low, it uses heuristics to kill processes that it "thinks" it can get rid of to restore system stability.


The combination of these two factors makes it look like Octave crashed. But it was actually killed by an OS service.

It might be nice if we could somehow prevent that from happening more generally. Maybe, some way to tell the OS to be less optimistic with its over-provisioning for Octave.
But last time I looked into it, I couldn't find a reliable way to do that.

When it comes to your patch: Did you run some performance checks? Try-catch has often a high run-time penalty. Also, adding a (recursive?) call in there might come with a run-time cost.
That is especially a potential concern because that kind of check is only needed depending on the OS configuration...

Markus Mützel <mmuetzel>
Group administrator
Sat 29 Mar 2025 07:14:37 AM UTC, comment #4: 

The patch looks helpful, but it does not completely solves the problem.

There are few issues here. One is exceeding octave addressable array size, another is OOM kill of (theoretically allowable) large memory usage. E.g. what do you get with your patch for "c = nchoosek (1:50, 10);" ?

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Sat 29 Mar 2025 02:06:39 AM UTC, comment #3: 


comment #1:

> I think this kind of issue comes up every now and then (could be memory, or could be some other system resource) and everytime the conclusion is that octave cannot do that.
>
> Dmitri.
> --
>

I am not sure what you mean by "octave cannot do that". Anyway, I hope the patch is helpful to circumvent this issue.

Andreas Bertsatos <pr0m1th3as>
Sat 29 Mar 2025 02:03:04 AM UTC, comment #2: 

I made a patch with a workaround to fix this issue.

(file #57079)

Andreas Bertsatos <pr0m1th3as>
Sat 29 Mar 2025 01:23:34 AM UTC, comment #1: 

I think this kind of issue comes up every now and then (could be memory, or could be some other system resource) and everytime the conclusion is that octave cannot do that.

Dmitri.
--


Dmitri A. Sergatskov <dasergatskov>
Sat 29 Mar 2025 01:13:14 AM UTC, original submission:  


c = nchoosek (1:50, 30)

crashes Octave, most likely due to reaching out of memory condition. Shouldn't be there some check to ensure that this does not happen? Found this on Octave 9.1, but also tested on 10.0.90 and it still results to crash.

promitheas@Mini-Workstation:~$ myoctave --gui
octave exited with signal 9
promitheas@Mini-Workstation:~$ myoctave
GNU Octave, version 10.0.90
Copyright (C) 1993-2025 The Octave Project Developers.
This is free software; see the source code for copying conditions.
There is ABSOLUTELY NO WARRANTY; not even for MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  For details, type 'warranty'.

Octave was configured for "x86_64-pc-linux-gnu".

Home page:            https://octave.org
Support resources:    https://octave.org/support
Improve Octave:       https://octave.org/get-involved

For changes from previous versions, type 'news'.

warning: function /home/promitheas/fminsearch.m shadows a core library function
octave:1> c = nchoosek(1:50, 30)
Killed


Andreas Bertsatos <pr0m1th3as>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #57079:  nchoosek.patch added by pr0m1th3as (2KiB - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by mmuetzel (Posted a comment)
  • -email is unavailable- added by dasergatskov (Posted a comment)
  • -email is unavailable- added by pr0m1th3as (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follows 1 latest change.

    Date Changed by Updated Field Previous Value => Replaced by
    2025-03-29 pr0m1th3as Attached File- Added nchoosek.patch, #57079

    Back to the top

    Powered by Savane 3.14-962f.
    Corresponding source code