1

I referred this, this and this SO posts before asking this question:

While teaching dynamic memory allocation to a friend, I wrote a simple program, whose snippet is below:

matrix = (int**) malloc (sizeof(int*) * m);
for (i = 0; i < m; ++i)
matrix[i] = (int*) malloc (sizeof(int) * n);

for (i = 0; i < m; ++i)
  for (j = 0; j < n; ++j)
      matrix[i][j] = rand() % 100; /*some random value*/


for (i = 0; i < m; ++i)
{
  for (j = 0; j < n; ++j)
  {
      printf("(%8u)%-5d", &matrix[i][j], matrix[i][j]);
  }

  /* Print element just after the first row*/
  printf("(%8u)%-5d", matrix[i] + n, *(matrix[i] + n));

  /* Print second NEXT element just after the first row*/
  printf("(%8u)%-5d", matrix[i] + n + 1, *(matrix[i] + n + 1));
}

When I run this program as

unmesh@unmesh-laptop:~/teaching/C/Day3$ ./matrix
Enter number of rows: 3
Enter number of columns: 3

(141189144)1    (141189148)2    (141189152)3    **(141189156)17**   (141189160)2    

(141189160)2    (141189164)3    (141189168)4    **(141189172)17**   (141189176)3    

(141189176)3    (141189180)4    (141189184)5    (141189188)135105(141189192)0

I am curious about the value 17. If I am not mistaking, there are three calls to malloc in this invocation, So memory may not be contiguous as can be observed. But I run the program with m=n=4 or m=n=5, then I can see the value 25 after each row. For m=n=6 and m=n=7, value 33 is observed.

More interesting is the fact that when n is odd (n=3 / n=5 ..) this value is stored immediately after the row ends. example row when m=n=3 

Values  1        2       3       17  
Address 100      104    108     112  

Next row starts from 116

When n is even, it is stored after 4 bytes example row when m=n=2 

Values  1        2       0       17  
Address 100      104    108     112  

Next row starts from 116

Question is where do these values 17/25/33 come from ? Why are they always the same ? I hope they are not garbage and must have some meaning .. I fail to deduce. Please help.

Community
  • 1
  • 1
Trojosh
  • 565
  • 1
  • 5
  • 15
  • It's not something that's stored after each row, it's stored _before_ each row. Bookkeeping data from `malloc`. The value is `(number_of_elements / 2 + 1)*8 + 1`, or, better `number_of_used_8_byte_blocks*8+1`, but I'm not sure why the `+1` there. – Daniel Fischer Mar 08 '13 at 18:46
  • Daniel, +1 for the formula :-) – Trojosh Mar 08 '13 at 20:05

1 Answers1

2

You're seeing the internal bookkeeping information malloc stores to keep track of blocks that have been allocated. The precise nature and size of this information varies from system to system, but it is often the case that malloc rounds up the size requested so that, when combined with its bookkeeping info, the resulting block is a multiple of the largest alignment generally required for your machine. In your case, it looks like the alignment is 8 bytes (two ints), leading to the even/odd behavior you see. The 17/25/33 values you see are likely the sizes of the allocated blocks (including the padding and size info) with the lowest bit set to indicate an in-use block.

Chris Dodd
  • 119,907
  • 13
  • 134
  • 226
  • Thanks Chris, That gave some insight. Could you please explain why these values are always odd then ? e.q. If I ask malloc(8) say for 2 integers, no padding is necessary for this block, then how would malloc calculate 17 ? And why this value remains same for n=3 ? Am going to look for malloc implementation too. I will repost if I come up with definitive answer – Trojosh Mar 08 '13 at 19:51
  • Daniel and Chris, See if this explanation fits or not : According to Daniel's comment, I think +1 in formula is for telling that nth byte is free (for allocation). i.e. e.g. n=2, For every row malloc allocates 16 bytes (8 + 4 (for bookkeeping) + 4(padding)) and malloc knows that 17th byte from here is free when n=3, for every row malloc allocates 16 bytes again (12 + 4(book keeping) + no padding) and again it knows that the next free block of memory is 17th byte.. – Trojosh Mar 08 '13 at 20:13
  • @Trojosh I think Chris is right that the set lowest bit indicates the block is in use. Apart from that, the `malloc` of your implementation seems to allocate in multiples of 8 bytes, so it's the usable size of the allocated block, plus the four bytes for the bookkeeping (plus the use-indicator). – Daniel Fischer Mar 08 '13 at 20:28