Using comparison operators with pointers to check if it is within an address range?

Question

I'm implementing a function that deallocates a memory location that has been supplied to it, via a call to deallocate_cache(void *ptr).

My memory constructs for the task at hand are the following:

 22 typedef struct slab {
 23         void *addr;
 24         int bm[((SLAB_SIZE/8)/(8*sizeof(int)))+1]; // bitmap
 25         struct slab *next;
 26 } slab;

 39 typedef struct {
 40         int alloc_unit;
 41         slab S;
 42 } cache;

 45 typedef struct { // structure for the entire memory
 46         cache C[9];
 47         region *R;
 48 } memory;

Hence, I have a memory M, which contains caches c[0], c[1], ..., c[8], which in turn contain slabs. When one slab fills up through allocation, I allocate another one as a linked list element through the slab *next field.

For my deallocate_cache(void *ptr) to work correctly, I must first find out whether ptr is even in the range of the caches, and if so in which one it is. This is what I have so far:

 1.    // Check if ptr is in the range of (slab_addr, slab_size) for each slab in each cache
 2. int ci = 0, counter, coefficient, done, freeable;
 3. slab *look_ahead;
 4. for(; ci < 9; ci++){
 5.         void *max_addr = &M.C[ci].S + SLAB_SIZE; // The upper bound of the address range of the first slab
 6.         counter = 1;
 7.         look_ahead = &M.C[ci].S;
 8.         while(look_ahead->next != NULL){
 9.             if( ptr > look_ahead->addr && ptr > max_addr){ // Check ptr is greater than S.addr. If yes, it's a good bet it's in this cache.
10.                 look_ahead = look_ahead->next;
11.                 max_addr += SLAB_SIZE; // Now the upper bound of the address range of the following slab
12.                 counter++; // slab counter, 1-based counting
13.             }
14.             else {
15.                     done = 1;
16.                     break;
17.             }
18.         }
19.         if(done == 1) break;
20.
21. }

Unfortunately, and rather obviously, this does not work as intended. Is there any way I could use pointers like this to compare addresses, or check if the pointer is in a given address range? Or will I have to simply compare every single address in the maximum range I know I have allocated to? Any help is much appreciated.

Answer 1

First, you cannot add anything to or subtract anything from a pointer to void.

Pointer arithmetic is defined only for pointers that point to things of known sizes. void, unlike char or int or char* or struct slab, does not have a known size. And that's because adding to or subtracting from a pointer advances the address in the pointer by a multiple of the size of what the pointer points to.

So, if you have char* p; then p = p + 1; adds sizeof(char) (which is 1) to the address in the pointer, but if you have long* p; then p = p + 1; adds sizeof(long) (which typically is 2, 4 or 8) to the address in the pointer.

However odd, the same limitation applies to comparing pointers with >, <, >=, <=. The compared pointers must point to the same type, which can't be void.

I think you need to use pointers to char instead of pointers to void or cast the latter to the former in order to do pointer arithmetic.

Another important thing to note is that legally you can't compare pointers with >, <, >=, <= if these pointers do not point into the same array or into the same object (which can be aggregate like a structure). The C standard states that this amounts to undefined behavior.

So, if you allocate two objects separately (as declarations of separate objects or as separate calls to malloc() or similar), then you can't legally compare pointers to these two objects with >, <, >=, <=.

== and != can be done, however.

One common workaround for this comparison limitation is to cast pointers to uintptr_t, an unsigned integer type that is guaranteed to be able to hold a pointer, and perform regular arithmetic operations on this integer type and then, if needed, convert (cast) it back to a pointer type.

This, of course, will only work if your compiler defines pointer to integer and integer to pointer conversions meaningfully and guarantees that the integer values obtained from converting pointers to them are memory address.

Use this info to correct your code.