Can malloc be relied on to return contiguous memory, and how do I properly call it?

Question

Before I get started, yes I have read a possible duplicate, malloc being weird in linux, cplusplus.com on malloc and done some searching on google.

I have a scientific computing problem that requires a very large 2D array. I'm following code found in a copy of "Numerical Recipes in C", and am having a problem with unallocated memory in the middle of my 2D array. I am working in Windows, and am using c++ with MSVC 2012.

Here is my 2D array allocation

  unsigned long nrl=0;
  unsigned long nrh=749774;
  unsigned long ncl=0
  unsigned long nch=250657;
  unsigned long i, nrow=nrh-nrl+1,ncol=nch-ncl+1;
  double **m;
  if((size_t)(nrow*ncol)<(size_t)nrow){
    m=NULL;
    return m;
  }
  /*allocate pointers to rows*/
  m=(double **)malloc((size_t)(nrow)*sizeof(double*));
  if (!m){
    m=NULL;
    return m;
  }

  /*allocate rows and set pointers to them*/
  m[nrl]=(double *) malloc((size_t)((nrow*ncol)*sizeof(double)));
  if(!m[nrl]){  
    free(m[nrl]);
    free(m);
    m=NULL;
    return m;
  }
  for(i=nrl+1;i<=nrh;i++)m[i]=m[i-1]+ncol;
  /*The 2D array should now be callable as m[nrow][ncol]*/
  /*Pseudo-code below*/
  m[0][0] == Good, allocated memory
  m[125][200923] == Unallocated, crashes program
  m[nrh-1][nch-1] == Good, allocated memory

I am currently relying on malloc to return NULL if memory allocation fails (I do actually get NULL values if I try to allocate very very large arrays.

Also, I have attempted double *m = new double[nch*nrh], but that gives me a memory allocation error. I am open to any suggestions for alternative implementations, but I need to be able to know whether the allocation works and reallocate a smaller block if necessary.

EDIT:

This is a c function, but the majority of my code is in c++.

UPDATE:

Thanks to David, I was able to fix the problem. Changing my overflow check from

if((size_t)(nrow*ncol)<(size_t)nrow)

to

if(SIZE_MAX/nrow < ncol || SIZE_MAX/ncol < nrow || nrow*ncol<nrow)

allows malloc to fail when it should.

awell you are trying to allocate 1.36 tebibytes of data so yeah, that'll give you a meory allocation error. — IdeaHat, Sep 22 '14 at 14:30
Makes more sense to `((size_t)nrow)*((size_t)ncol)` than `(size_t)(nrow*ncol)`. — chux - Reinstate Monica, Sep 22 '14 at 14:31
no need to cast i think. they are `int` eventually. you should pay attention to overflow problem instead if the array is big. and if it's big, i think you don't need to consider the continuous allocation too, since you want it to be continuous only when all of your data fits in the cache. — Jason Hu, Sep 22 '14 at 14:44
It is very unfortunate that you are using MSVC because they are not standard conforming. With a real modern C compiler you have real 2D dynamic matrices and you don't have to use these fake matrices that you are using. In C99 this would just be `double (*m)[ncol] = malloc(sizeof(double[nrow][ncol]));`. No multiple allocation, no explcit size computation, ... Also don't use a C++ compiler to compile C. These are two different languages. — Jens Gustedt, Sep 22 '14 at 15:12
@JensGustedt It's not so much the choice of MSVC that has led to this, rather the fact that the code comes from NR and is utterly ancient. — David Heffernan, Sep 22 '14 at 15:32
@DavidHeffernan NR **is** ancient, and I promise to find a more modern solution next time. — Riet, Sep 22 '14 at 15:40
@Riet NR has its place. Eigen is pretty tasty. Out of interest, what is the problem at hand? — David Heffernan, Sep 22 '14 at 15:51
It's to calculate the conductivity of a battery electrode with the current collector still attached, including probe geometry and 3D effects. There's an analytical solution, but it requires a lot of Fourier terms and this matrix is to find the Fourier coefficients. We're working on exactly how many we need and can use, thus the ridiculous matrix size. — Riet, Sep 22 '14 at 16:04

David Heffernan · Accepted Answer · 2014-09-22T14:44:46.930

4

I'm guessing that you have a 32 bit process. Do note that nrow*ncol*sizeof(double) is (a lot!) greater than 2^32. You are actually attempting to allocate 1400 GB, which I rather imagine comes as a surprise to you.

It's most likely not possible to allocate that much memory, and certainly not in a 32 bit process. Your code appears to run because (nrow*ncol)*sizeof(double) suffers from integer overflow and so your call to malloc succeeds but doesn't allocate the memory that you expect it to. In fact, even in a 64 bit process you have overflow, because nrow*ncol is evaluated with 32 bit arithmetic because you declared nrow and ncol to be unsigned long. They should really be size_t.

Anyway, you are going to need to reconsider your entire approach to your problem. Can you really expect to do anything useful with a 1400 GB dense matrix?

edited Sep 22 '14 at 14:44

answered Sep 22 '14 at 14:32

David Heffernan

601,492
42
1,072
1,490

Note: DOS 16-bit machines (in huge memory model) can allocate > 64k memory. IOW, being a "32 bit machine" does not limit memory to 4Gbyte. Memory capacity, though typically related to possessor integer size, are independent factors. – chux - Reinstate Monica Sep 22 '14 at 14:37
32 or 64 bit doesn't really matter in this case...Sure you CAN fit 1.36 tebibytes in a 64 bit address space, but Windows 8 only supports up to 512 gibibytes. Windows Server 2012 can support up to 4 tebibibytes, but I'd guess if the person could afford that hardware the question would be very different. – IdeaHat Sep 22 '14 at 14:37
@MadScienceDreams Well, it kind of does matter in that the failure mode is different. On 64 bit the call to malloc would fail because at least the `size_t` that was passed was the intended value. – David Heffernan Sep 22 '14 at 14:39
@MadScienceDreams Well, that's modulo first converting nrow and ncol to be `size_t`. – David Heffernan Sep 22 '14 at 14:41
If `size_t` is 64 bit and `long` is 32, overflow occurs with `nrow*ncol` before casting to 64-bit. – chux - Reinstate Monica Sep 22 '14 at 14:41
@chux Yes, I realised that too – David Heffernan Sep 22 '14 at 14:43
Very much appreciated. I realized that it shouldn't be able to allocate that much memory, and that I probably wouldn't really need that much anyways. I expected this piece of code to return NULL so that I could reallocate and make it small enough to fit in available resources. Again, many thanks! – Riet Sep 22 '14 at 15:38
On a 64-bit system, `unsigned long` can be either 32 or 64 bits. I think it's usually 64 bits on Linux, 32 on Windows. – Keith Thompson Sep 22 '14 at 16:02
@Keith That's right but we knew this was Windows because question mentions msvc. So I took that fact implicitly. – David Heffernan Sep 22 '14 at 16:09

Can malloc be relied on to return contiguous memory, and how do I properly call it?

1 Answers1