Finding an index from an address

[jacob navia]

Hi

I have a heap of n objects of size Heap->ElementSize;

I receive from the client program an element to free, so
I have to put it in the free list. Since the heap is
just an array of n * ElementSize bytes, I find out
the index of the element to free from its address, then set
the bit to 1 to mark it as a free element.

Do you see anything wrong with this code?


static int AddToFreeList(ContainerHeap *heap,void *element)
{
char *p = heap->Heap;
char *elem = element;
size_t idx,byte;

idx = elem-p; // get the distance in bytes
if (idx < 0) return -1; // element not in the heap
idx /= heap->ElementSize; // Now in element size units
if (idx > l->Capacity) return -1; // element is not in the heap


byte = idx/8; // The byte in the bit map

// Set the bit in the bitmap to 1.
l->FreeMap[byte] |= (1 << (idx%8));

// Update counters
heap->Used--;
heap->FreeCount++;
return 1;
}

Specifically it is OK to use size_t?

 

[Ian Collins]

Hi

I have a heap of n objects of size Heap->ElementSize;

I receive from the client program an element to free, so
I have to put it in the free list. Since the heap is
just an array of n * ElementSize bytes, I find out
the index of the element to free from its address, then set
the bit to 1 to mark it as a free element.

Do you see anything wrong with this code?


static int AddToFreeList(ContainerHeap *heap,void *element)
{
char *p = heap->Heap;
char *elem = element;
size_t idx,byte;

idx = elem-p; // get the distance in bytes
if (idx< 0) return -1; // element not in the heap
idx /= heap->ElementSize; // Now in element size units
if (idx> l->Capacity) return -1; // element is not in the heap


byte = idx/8; // The byte in the bit map

// Set the bit in the bitmap to 1.
l->FreeMap[byte] |= (1<< (idx%8));

// Update counters
heap->Used--;
heap->FreeCount++;
return 1;
}

Specifically it is OK to use size_t?

To my eye it would be clearer to use const for the pointers and
initialise idx and byte where they are used:

size_t idx = elem-p;

and

const size_t byte = idx/8;

There's nothing wrong with using size_t in this context.

 

[BartC]

Hi

I have a heap of n objects of size Heap->ElementSize;

I receive from the client program an element to free, so
I have to put it in the free list. Since the heap is
just an array of n * ElementSize bytes, I find out
the index of the element to free from its address, then set
the bit to 1 to mark it as a free element.

Do you see anything wrong with this code?


static int AddToFreeList(ContainerHeap *heap,void *element)
{
char *p = heap->Heap;
char *elem = element;
size_t idx,byte;

idx = elem-p; // get the distance in bytes
if (idx < 0) return -1; // element not in the heap
idx /= heap->ElementSize; // Now in element size units
if (idx > l->Capacity) return -1; // element is not in the heap

Shouldn't this be >= rather than >?

And what is l? Does it only contain this one object, and a Freemap dedicated
to this object? If not, then I don't see how it can work as idx (and later
'byte') are offsets relative to this object.

byte = idx/8; // The byte in the bit map

// Set the bit in the bitmap to 1.
l->FreeMap[byte] |= (1 << (idx%8));

 

[Ike Naar]

Do you see anything wrong with this code?

static int AddToFreeList(ContainerHeap *heap,void *element)
{
char *p = heap->Heap;
char *elem = element;
size_t idx,byte;

idx = elem-p; // get the distance in bytes

Undefined behaviour if elem and p are not pointing to the same object.

if (idx < 0) return -1; // element not in the heap

Always false because idx has an unsigned type.

idx /= heap->ElementSize; // Now in element size units
if (idx > l->Capacity) return -1; // element is not in the heap

You don't check if the bit in the bitmap was already set (in other words
freeing an element that was already freed) ?

byte = idx/8; // The byte in the bit map

// Set the bit in the bitmap to 1.
l->FreeMap[byte] |= (1 << (idx%8));

// Update counters
heap->Used--;
heap->FreeCount++;
return 1;
}

Specifically it is OK to use size_t?

 

[jacob navia]

Le 20/05/12 23:58, Ike Naar a écrit :

Undefined behaviour if elem and p are not pointing to the same object.

How could I know that?


I just receive an address from the client program.

Always false because idx has an unsigned type.

OOOPS. Thanks!

You don't check if the bit in the bitmap was already set (in other words
freeing an element that was already freed) ?

YES, I should check for that of course. Didn't think about it.

Again Thanks.

 

[jacob navia]

Le 20/05/12 23:58, BartC a écrit :

Shouldn't this be >= rather than >?

YES. Thanks BartC.

And what is l? Does it only contain this one object, and a Freemap
dedicated
to this object? If not, then I don't see how it can work as idx (and later
'byte') are offsets relative to this object.

I mistyped heap with "l" when retyping.

 

[Ike Naar]

Le 20/05/12 23:58, Ike Naar a ?crit :

How could I know that?

I just receive an address from the client program.

Trust the client, and make this a precondition of the function.

Or, if the heap is an array, change the interface so that the client
passes the index of the element, instead of a pointer to it.

Or, instead of representing the element to be deleted by a bare pointer,
use a descriptor that contains information about the heap the element
belongs to.

 

[jacob navia]

Le 21/05/12 08:39, Ike Naar a écrit :

Trust the client, and make this a precondition of the function.
dangerous

Or, if the heap is an array, change the interface so that the client
passes the index of the element, instead of a pointer to it.

client code uses a pointer since the heap allocates memory by giving a
pointer to it.

Or, instead of representing the element to be deleted by a bare pointer,
use a descriptor that contains information about the heap the element
belongs to.

It uses more memory.


Since the heap is a linear array, I test in my function if the
address is betweeen the start and the end of the array. If it is,
I calculate its index.

Then, I am sure it is OK. This doesn't use any
extra memory (your proposal 3) or doesn't trust blindlhy the
client (1) or changes the interface that now is "malloc like"
(2).

jacob

 

[Ian Collins]

Le 21/05/12 08:39, Ike Naar a écrit :

client code uses a pointer since the heap allocates memory by giving a
pointer to it.


It uses more memory.

Since the heap is a linear array, I test in my function if the
address is betweeen the start and the end of the array. If it is,
I calculate its index.

At this point it might be worth while checking that

p % heap->ElementSize == 0

as another guard against an invalid pointer. A duplicate free test as
suggested elsewhere would be worth adding as well.

 

[Tim Rentsch]

Hi

I have a heap of n objects of size Heap->ElementSize;

I receive from the client program an element to free, so
I have to put it in the free list. Since the heap is
just an array of n * ElementSize bytes, I find out
the index of the element to free from its address, then set
the bit to 1 to mark it as a free element.

Do you see anything wrong with this code?


static int AddToFreeList(ContainerHeap *heap,void *element)
{
char *p = heap->Heap;
char *elem = element;
size_t idx,byte;

idx = elem-p; // get the distance in bytes
if (idx < 0) return -1; // element not in the heap
idx /= heap->ElementSize; // Now in element size units
if (idx > l->Capacity) return -1; // element is not in the heap


byte = idx/8; // The byte in the bit map

// Set the bit in the bitmap to 1.
l->FreeMap[byte] |= (1 << (idx%8));

// Update counters
heap->Used--;
heap->FreeCount++;
return 1;
}

Specifically it is OK to use size_t?

I see lots of things that might be brought up in a code
review, but let me mention just three points.

First, granting that the nominal undefined behavior is acceptable
(and I have no problem with that), the range check comparisons can,
and I would argue should, be done without having to do a pointer
subtraction:

char *e = element, *base = ..., *limit = ...;

if( e < base || e >= limit ) return -1;

Even better if 'base' and 'limit' are stored in the structure
(and with an appropriate type) to begin with; the storage cost
of saving them is negligible.

Second, the question about size_t, and the /= on the calculated
index, are reflective of the "units" changing during the course
of the function. These concerns can be avoided by doing a single
index calculation after the range checks shown above (I am
using 'k' rather than 'idx'):

size_t k = (e-base) / heap->ElementSize;

Here I have used 'size_t' for the type, but it is always right
to use the same type as heap->Capacity, whatever type that
is, since the value for k is guaranteed to be less than
heap->Capacity (and greater than zero). The question about
what type to use then becomes trivial. This also allows
the variable to be made 'const' if that is desired.

Third, the setting of bits (a) is done in multiple steps, (b)
hardwires the constant 8 in the function body (and presumably
assuming that the bits are stored in an array of unsigned char
and CHAR_BIT == 8). This kind of bit-testing/setting/clearing
operations should be abstracted using macros that hide these
details and work for a range of unsigned types. Incorporating
the suggestion made else-thread to check the bit before setting
it, we would

if( ! IS_BIT_SET( heap->FreeMap, k ) ){
SET_BIT( heap->FreeMap, k );
... // set counters, etc
}

It isn't hard to write the IS_BIT_SET() and SET_BIT() macros
so that they work for different values of CHAR_BIT and for
unsigned types of different sizes, making the reasonable
assumption that these types have no padding bits (and that
assumption can be verified by a compile-time check).

Taking these three points into account, the resulting function
body would be:

char *e = element;

if( e < heap->base || e >= heap->limit ) return -1;

const size_t k = (e - heap->base) / heap->ElementSize;

if( ! IS_BIT_SET( heap->FreeMap, k ) ){
SET_BIT( heap->FreeMap, k );
heap->Used--;
heap->FreeCount++;
}

return 1;

Besides being shorter and simpler, I think a revision along
these lines makes it easier to decipher what the function is
doing. So not only are the various problems addressed, but
it's easy to see that they have been addressed.