bug in : hash = malloc(hash_size + 63) & ~63

[bob]

Code: Select all

// 1) bug
hash = malloc(hash_size + 63) & ~63;
// 2) should be -
hash = (malloc(hash_size + 64) & ~63) + 64;

I have some sort of segmentation fault, etc when the original pointer from malloc() was free()'ed - main() did not exit with a clear status 0; 2) solves the problem.

Of course you can only free what malloc returns, without masking it.

Code: Select all

memory = malloc(hash_size + 63);
hash = memory & ~63;
...
free(memory); // ok
free(hash); // wrong

my free() is ok - free(memory), the original saved pointer returned from malloc().

I don't know much about hex/binary arithmetic or about address alignment. I only do what is recommended, try to align my TT start address to 64/128 bytes so that when I do multi-probe of hash at TT, TT+1,TT+2,TT+3, all 4 would be in the same cache-line.

I have to think a little about Bob's reply. I don't get it yet.

What I mean in my original post is this:
with your code above as example, the address of the block we can write to starts from 'memory'. But the address 'hash' is before the address 'memory' or hash < memory. So if we store a hash record with :
hash[0] = ...something;
that slot is outside (before) the block allocated by malloc(). This means memory corruption of some 64 bytes of data just before 'memory'.

I am not sure as I still am thinking about Bob's reply.

Rasjid

I do not see how you can get an address "before" the malloc'ed memory.

Again,

Code: Select all

mem = malloc(N+63);
aligned_mem = (mem + 63) & ~63;

Unless I am overlooking something due to a "senior moment" I don't see how that can fail. My current code can malloc() and free() things over and over as you change sides, with no problems at all...

I'm going to write a bit of C code to check the original and aligned addresses... More in a bit...

OK, I see no flaw. I wrote a program that does the following: Varies the initial malloc() return address from 4096 to 4096 + 63. It then computes an aligned address as discussed, malloc return + 63 & ~63. I then print out the value added to address (0 - 63 to test all possible unaligned addresses), the address itself (4096 + the 0-63 value just given, then the aligned address, and the aligned address + 511 which is the range of valid addresses, and finally, the max valid address which is the original malloc() value + 63.

Here's the program, first:

Code: Select all

#include <stdio.h>
void main() {
  int i, mem, new;
  int size=512;
  int address = 4096;
  printf(" inc  orig  align  end  max\n");
  for (i=0; i<64; i++) {
    mem = address + i;
    new = (mem + 63) & ~63;
    printf("%4d  %4x  %4x  %4x  %4x\n",
           i, mem, new, new+size - 1, mem + size - 1 + 63);
  }
}

and here's the output:

Code: Select all

  inc  orig  align  end  max
   0  1000  1000  11ff  123e
   1  1001  1040  123f  123f
   2  1002  1040  123f  1240
   3  1003  1040  123f  1241
   4  1004  1040  123f  1242
   5  1005  1040  123f  1243
   6  1006  1040  123f  1244
   7  1007  1040  123f  1245
   8  1008  1040  123f  1246
   9  1009  1040  123f  1247
  10  100a  1040  123f  1248
  11  100b  1040  123f  1249
  12  100c  1040  123f  124a
  13  100d  1040  123f  124b
  14  100e  1040  123f  124c
  15  100f  1040  123f  124d
  16  1010  1040  123f  124e
  17  1011  1040  123f  124f
  18  1012  1040  123f  1250
  19  1013  1040  123f  1251
  20  1014  1040  123f  1252
  21  1015  1040  123f  1253
  22  1016  1040  123f  1254
  23  1017  1040  123f  1255
  24  1018  1040  123f  1256
  25  1019  1040  123f  1257
  26  101a  1040  123f  1258
  27  101b  1040  123f  1259
  28  101c  1040  123f  125a
  29  101d  1040  123f  125b
  30  101e  1040  123f  125c
  31  101f  1040  123f  125d
  32  1020  1040  123f  125e
  33  1021  1040  123f  125f
  34  1022  1040  123f  1260
  35  1023  1040  123f  1261
  36  1024  1040  123f  1262
  37  1025  1040  123f  1263
  38  1026  1040  123f  1264
  39  1027  1040  123f  1265
  40  1028  1040  123f  1266
  41  1029  1040  123f  1267
  42  102a  1040  123f  1268
  43  102b  1040  123f  1269
  44  102c  1040  123f  126a
  45  102d  1040  123f  126b
  46  102e  1040  123f  126c
  47  102f  1040  123f  126d
  48  1030  1040  123f  126e
  49  1031  1040  123f  126f
  50  1032  1040  123f  1270
  51  1033  1040  123f  1271
  52  1034  1040  123f  1272
  53  1035  1040  123f  1273
  54  1036  1040  123f  1274
  55  1037  1040  123f  1275
  56  1038  1040  123f  1276
  57  1039  1040  123f  1277
  58  103a  1040  123f  1278
  59  103b  1040  123f  1279
  60  103c  1040  123f  127a
  61  103d  1040  123f  127b 
  62  103e  1040  123f  127c
  63  103f  1040  123f  127d

My chess program will use the "align" address, which is always on a 64 byte boundary as you can see. Since I wanted 512 bytes, I will be using addresses from align to align + 511.

What I am looking for, and not seeing, is any case where "align" is less than "orig" which would be bad since "orig" is the value returned by malloc. And I am lookijng for any case where "end" is greater than "max" which would be a reference beyond the end of the malloc area. I don't see either of those conditions, meaning all of my accesses are within the region I actually allocated, although they clearly don't use the first bytes except for the case where the original address is already aligned properly.

So, again, exactly what am I missing here???

[Chan Rasjid]

Code: Select all

// 1) bug
hash = malloc(hash_size + 63) & ~63;
// 2) should be -
hash = (malloc(hash_size + 64) & ~63) + 64;

I have some sort of segmentation fault, etc when the original pointer from malloc() was free()'ed - main() did not exit with a clear status 0; 2) solves the problem.

Of course you can only free what malloc returns, without masking it.

Code: Select all

memory = malloc(hash_size + 63);
hash = memory & ~63;
...
free(memory); // ok
free(hash); // wrong

my free() is ok - free(memory), the original saved pointer returned from malloc().

I don't know much about hex/binary arithmetic or about address alignment. I only do what is recommended, try to align my TT start address to 64/128 bytes so that when I do multi-probe of hash at TT, TT+1,TT+2,TT+3, all 4 would be in the same cache-line.

I have to think a little about Bob's reply. I don't get it yet.

What I mean in my original post is this:
with your code above as example, the address of the block we can write to starts from 'memory'. But the address 'hash' is before the address 'memory' or hash < memory. So if we store a hash record with :
hash[0] = ...something;
that slot is outside (before) the block allocated by malloc(). This means memory corruption of some 64 bytes of data just before 'memory'.

I am not sure as I still am thinking about Bob's reply.

Rasjid

The Crafty 23.1 code shows how this works, look at utility.c and search for AlignedMalloc, for instance. Basically that translates into something like this, with "alignment=64":

Code: Select all

memory = size + 63;
aligned_memory = (memory + 63) & ~63;
// use 'aligned_memory'
// finally, free 'memory'

'memory' points to a block which is 63 bytes bigger than actually needed. 'aligned_memory' points to an address between 'memory' and 'memory + 63' since zeroing the lower 6 bits can at most reduce the address by 63. So there is no bug involved IMO.

Sven

It is not clear from the Crafty codes quoted there was an 'add 7' to the pointer. If there is, then it is ok. Bob just made a slip in his old post :

Code: Select all

hash = malloc(hash_size + 63) & ~63;// wrong
hash = ((malloc(hash_size + 64) & ~63) + 64;// still works
hash = (malloc(hash_size + 63) + 63) & ~63;//clean and tidy  

Thanks,
Rasjid

[hgm]

Did you miss the fact that I malloc 63 more than I need, then add 63 to the address before scrubbing the rightmost 6 bits?

I did not miss anything. I merely comment on the code Chan gave in the first post of this thread. That does not add anything to the address before scrubbing it. If that is different from the code you use in Crafty, then Chan missed it. And you missed that he missed it.

[Sven]

It is not clear from the Crafty codes quoted there was an 'add 7' to the pointer. If there is, then it is ok. Bob just made a slip in his old post :

Code: Select all

hash = malloc(hash_size + 63) & ~63;// wrong
hash = ((malloc(hash_size + 64) & ~63) + 64;// still works
hash = (malloc(hash_size + 63) + 63) & ~63;//clean and tidy

I can't see what you are referring to by "there was an 'add 7' to the pointer".

The old post you were referencing was probably this one containing the code snippet:

Code: Select all

t = malloc(size_needed + 63);
t = t +63 & ~63;

which is simply not what you quoted above with your comment "// wrong" (one "+ 63" missing as I already said) but is still not optimal since the original address returned by malloc() is not saved but overwritten by the aligned address, so a later free() does not release the right pointer. You may call this a "slip" indeed, although not being related to the alignment feature itself. Everything else is correct there.

Your "// still works" version does indeed work, too, but might look slightly less intuitive for some, and does always waste at least one byte of memory No big deal of course but I see no good reason to use 64 instead of the exact 63.

Sven

[Sven]

Did you miss the fact that I malloc 63 more than I need, then add 63 to the address before scrubbing the rightmost 6 bits?

I did not miss anything. I merely comment on the code Chan gave in the first post of this thread. That does not add anything to the address before scrubbing it. If that is different from the code you use in Crafty, then Chan missed it. And you missed that he missed it.

Good that I did not miss that you did not miss that Bob missed that Chan missed it

Sven

[Chan Rasjid]

It is not clear from the Crafty codes quoted there was an 'add 7' to the pointer. If there is, then it is ok. Bob just made a slip in his old post :

Code: Select all

hash = malloc(hash_size + 63) & ~63;// wrong
hash = ((malloc(hash_size + 64) & ~63) + 64;// still works
hash = (malloc(hash_size + 63) + 63) & ~63;//clean and tidy

I can't see what you are referring to by "there was an 'add 7' to the pointer".

The old post you were referencing was probably this one containing the code snippet:

Code: Select all

t = malloc(size_needed + 63);
t = t +63 & ~63;

which is simply not what you quoted above with your comment "// wrong" (one "+ 63" missing as I already said) but is still not optimal since the original address returned by malloc() is not saved but overwritten by the aligned address, so a later free() does not release the right pointer. You may call this a "slip" indeed, although not being related to the alignment feature itself. Everything else is correct there.

Your "// still works" version does indeed work, too, but might look slightly less intuitive for some, and does always waste at least one byte of memory No big deal of course but I see no good reason to use 64 instead of the exact 63.

Sven

"add 7" is a typo, should be "add 63".

I dig into archive as I recalled H.G posted about it long... time ago, but only got the post when Bob made a slip, without + 63, as in my first post.

The link you gave was when Bob was not asleep

Bob, being a professor, cannot show a malloc(size + 64), but I can


Rasjid

[wgarvin]

Crafty's AlignedMalloc() allocates N+(alignment-1) bytes from the heap. It keeps both the original pointer (used to free it later) and a pointer which is correctly rounded up to the next alignment boundary.

The function is correct as long as the alignment parameter is a power of two and the addition of (alignment-1) to the requested size N does not cause an integer overflow.
You could add this if you were paranoid:

Code: Select all

assert(alignment && (0 == (alignment&(alignment-1))) && (N < (~size_t(0) - alignment)));

[Sven]

Crafty's AlignedMalloc() allocates N+(alignment-1) bytes from the heap. It keeps both the original pointer (used to free it later) and a pointer which is correctly rounded up to the next alignment boundary.

The function is correct as long as the alignment parameter is a power of two and the addition of (alignment-1) to the requested size N does not cause an integer overflow.
You could add this if you were paranoid:

Code: Select all

assert(alignment && (0 == (alignment&(alignment-1))) && (N < (~size_t(0) - alignment)));

It is not paranoid. In 32 bit programs using this kind of code, requesting a size of 4 GB would already fire that assertion failure. So the surrounding code must either take care that such a huge value for N does not make it into that low level code, or change the low level code to cope with it by using a 64 bit approach.

Btw I would write three lines instead of one so that each single assert() becomes more readable.

Code: Select all

assert(alignment > 0);
assert(0 == (alignment&(alignment-1)));
assert(N < (~size_t(0) - alignment));

Sven