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]

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.

--
Ian Collins

[BartC]

"jacob navia" <ja...@spamsink.net> wrote in message
news:jpbocm$unk$1...@speranza.aioe.org...

> 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));

--
Bartc

[Ike Naar]

On 2012-05-20, jacob navia <ja...@spamsink.net> wrote:
> 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?

--
i...@sdf.lonestar.org
SDF Public Access UNIX System - http://sdf.lonestar.org

[jacob navia]

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

> On 2012-05-20, jacob navia<ja...@spamsink.net> wrote:
>> 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.
>

How could I know that?


I just receive an address from the client program.

>> if (idx< 0) return -1; // element not in the heap
>
> Always false because idx has an unsigned type.
>

OOOPS. Thanks!

>> 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) ?
>

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.

[pete]

Since idx is assigned the value of the difference
between 2 pointer values,
and especially also because there is some chance
that that value might be negative,
then ptrdiff_t seems like the right choice for the type of idx.

--
pete

[pete]

[Ike Naar]

On 2012-05-20, jacob navia <ja...@spamsink.net> wrote:

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

>> On 2012-05-20, jacob navia<ja...@spamsink.net> wrote:
>>> 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.
>
> 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 :

> On 2012-05-20, jacob navia<ja...@spamsink.net> wrote:
>> Le 20/05/12 23:58, Ike Naar a ?crit :
>>> On 2012-05-20, jacob navia<ja...@spamsink.net> wrote:
>>>> 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.
>>
>> 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.
>

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]

On 05/21/12 08:08 PM, jacob navia wrote:
> Le 21/05/12 08:39, Ike Naar a �crit :

>> On 2012-05-20, jacob navia<ja...@spamsink.net> wrote:
>>> Le 20/05/12 23:58, Ike Naar a ?crit :
>>>> On 2012-05-20, jacob navia<ja...@spamsink.net> wrote:
>>>>> 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.
>>>
>>> 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.
>>
> 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.

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.

--
Ian Collins

[Tim Rentsch]

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.