Potential bug in BG_alloc and proposed patch

[clearer]

I came across a bit of code that I found strange: in BG_alloc in src/game/bg_alloc.c I found the following line of code:

Code: [Select]

allocsize = (size + sizeof(int) + ROUNDBITS) & ~ROUNDBITS
ROUNDBITS is #defined (bad style really, use an enum instead) to 31.

The above code has at least three potential interpretation depending on what kind of machine it's compiled on (to be fair, one of them is not likely to happen):
16 bit implementations:

Code: [Select]

allocsize = (size + 16 + 31) & ~31 = (size + 47) & 0xFFE032 bit implementations:

Code: [Select]

allocsize = (size + 32 + 31) & ~31 = (size + 63) & 0xFFFFE064 bit implementations:

Code: [Select]

allocsize = (size + 64 + 31) & ~31 = (size + 95) & 0xFFFFFFFFE0
This appears to do the following: add a random number to size, that's at least 31 or larger. Set the lower 5 bits to 0 (i.e. make sure it's on a 32 byte boundary). It's bugged however: consider the case of size = 1:
16 bit: allocsize = (1 + 47) & 0xFFE0 = 48 & 0xFFE0 = 32
32 bit: allocsize = (1 + 63) & 0xFFFFFE0 = 64 & 0xFFFFFE0 =64
64 bit: allocsize = (1 + 94) & 0xFFFFFFFFFFFFE0 = 95 & 0xFFFFFE0 =64

So for both 32 and 64 bit allocsize is too large (well, at least it's not too small).

An implementation that doesn't have the above bug could be:

Code: [Select]

allocsize = (size + ROUNDBITS) & ~ROUNDBITS;16 bit: allocsize = (1 + 31) & 0xFFE0 = 32 & 0xFFE0 = 32
32 bit: allocsize = (1 + 31) & 0xFFFFFE0 = 32 & 0xFFFFFE0 =32
64 bit: allocsize = (1 + 31) & 0xFFFFFFFFFFFFE0 = 32 & 0xFFFFFE0 =32

Also, size really should be either a size_t or some other unsigned type.

[gimhael]

I think the code is fine as it is.

The allocator wants to store an extra int in each allocated block and also allocate only even multiples of 32-byte, so it has to add the size of an int + max. 31 bytes of padding to the memory block. This is calculated by adding 31 and then rounding down to the next smaller multiple of 32 with the and operator.

The 64 bit implementation simply needs more space for that extra int, so the number of allocated bytes has to be higher.

Also the sizeof(int) is practically always 4 in this case, because this is in QVM code, which is run on a virtual 32-bit machine, the only possible exception is if you compile it to a 64bit dll.

On the other hand the type of the size parameter (and consequently the allocsize variable) should arguably be an unsigned integer, or the code should check for size < 0 errors.

[Crava_Loft]

[deleted]

[gimhael]

Theoretically the argument to BG_alloc may be read from a network packet, a map file etc., which are out of control of the QVM writer. In this case I'd prefer an ERR_DROP message to a corrupted heap.

[clearer]

I think the code is fine as it is.

The allocator wants to store an extra int in each allocated block and also allocate only even multiples of 32-byte, so it has to add the size of an int + max. 31 bytes of padding to the memory block. This is calculated by adding 31 and then rounding down to the next smaller multiple of 32 with the and operator.

The 64 bit implementation simply needs more space for that extra int, so the number of allocated bytes has to be higher.

I haven't got an intimate knowledge about the working of the allocator -- I just thought it was weird that it would be different depending on the architecture. What exactly do you mean with 'the number of allocated bytes has to be higher'? Higher than what? The number of allocated bytes for 32 and 64 bits is the same for size = 1 (allocating 64 bytes).

Also the sizeof(int) is practically always 4 in this case, because this is in QVM code, which is run on a virtual 32-bit machine, the only possible exception is if you compile it to a 64bit dll.

Again, no intimate knowledge, I just thought it was weird how it worked. I didn't even know that it was only used in a virtual machine.

Anyway, if no-one likes it, feel free to ignore it. It was an attempt to help, not to be annoying :-).

[gimhael]

I didn't want to flame. You suggested to remove the +sizeof(int) from the allocsize and I wanted to explain that it is there for a reason.

On the other hand I think that your last sentence (signedness of the size parameter) is in fact a potential problem and should be fixed.