Question about memory allocation 
Author Message
 Question about memory allocation

It has been said on comp.lang.c that a C implementation is required to
allow a pointer to point (but not dereference) "one past" a valid block
of allocated memory.

Does this mean that in the following code,

T *ptr=malloc(SIZE * sizeof(T));
if (ptr) {
  ptr+SIZE; /* !!! */
  free(ptr);

Quote:
}

the line I've marked with !!! _must_ be a safe statement and not create
undefined behaviour, regardless of what type T is?

If so, then how does malloc() "know" how big this "safe area" has to be?
malloc() is only told how many bytes it must allocate, not what type
this memory will be used for.
Isn't it correct that the line I've marked with !!! computes an address
that is (SIZE*sizeof(T)) bytes after ptr?

If I say for example malloc(1100) then how will malloc() "know" whether
I'm allocating, for example, 11 items of 100 bytes each or 22 items of
50 bytes each? If I understand right then the "safe area" should be
100 bytes in the first case and 50 bytes in the last case.

Obviously a type in C can (theoretically) be arbitrarily large. Does
this mean that (theoretically) malloc() will have to reserve the
entire address space as a "safe area"?

I've obviously overlooked something of critical importance, but what is
it? I hope someone can understand what I'm babbling about. Thanks in
advance.

--

| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.*-*-*.com/ ~palaste       W++ B OP+                     |
\----------------------------------------- Finland rules! ------------/
"My absolute aspect is probably..."
   - Mato Valtonen



Sat, 12 Feb 2005 01:37:49 GMT  
 Question about memory allocation

Quote:
> It has been said on comp.lang.c that a C implementation is required to
> allow a pointer to point (but not dereference) "one past" a valid block
> of allocated memory.
> Does this mean that in the following code,
> T *ptr=malloc(SIZE * sizeof(T));
> if (ptr) {
>   ptr+SIZE; /* !!! */
>   free(ptr);
> }
> the line I've marked with !!! _must_ be a safe statement and not create
> undefined behaviour, regardless of what type T is?
> If so, then how does malloc() "know" how big this "safe area" has to be?
> malloc() is only told how many bytes it must allocate, not what type
> this memory will be used for.
> Isn't it correct that the line I've marked with !!! computes an address
> that is (SIZE*sizeof(T)) bytes after ptr?
> If I say for example malloc(1100) then how will malloc() "know" whether
> I'm allocating, for example, 11 items of 100 bytes each or 22 items of
> 50 bytes each? If I understand right then the "safe area" should be
> 100 bytes in the first case and 50 bytes in the last case.
> Obviously a type in C can (theoretically) be arbitrarily large. Does
> this mean that (theoretically) malloc() will have to reserve the
> entire address space as a "safe area"?
> I've obviously overlooked something of critical importance, but what is
> it? I hope someone can understand what I'm babbling about. Thanks in
> advance.

Never mind, I think I understand it now. The pointers can only safely
point at the *beginning* of the "safe area", not at any other point
within it. So therefore in the above code, the line which I've marked
with !!! can say ptr+SIZE without malloc() having to "know" how big the
type T is.
It can be explained this way: saying ptr=malloc(SIZE) (assuming ptr is
a char*) gives you a block of memory containing the addresses
[ptr, ptr+SIZE[, i.e. a semi-closed discrete interval that is closed
at the beginning but open at the end. The "one past" rule says that
when merely pointing, not dereferencing, this interval is fully
closed, i.e. [ptr, ptr+SIZE]. Since a pointer's value "is" only the
address of a single byte, this single byte can be appended at the
end of this interval even if the type it is used through is bigger.

A consequence of this is that if the end of this interval does not
lie on a sizeof(T) boundary then the "one past" rule is invalid.
For example, in the following code,

int *ptr=malloc(7);
if (ptr) {
  ptr+2; /* !!! */
  free(ptr);

Quote:
}

assuming sizeof(int)==4, the line I've marked with !!! is _not_ safe,
it creates undefined behaviour, since ptr+2 is 8 bytes after ptr, but
the "safe area" that can be pointed at is only [(char*)ptr,
(char*)ptr+7].

--

| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste       W++ B OP+                     |
\----------------------------------------- Finland rules! ------------/
"The day Microsoft makes something that doesn't suck is probably the day they
start making vacuum cleaners."
   - Ernst Jan Plugge



Sat, 12 Feb 2005 01:49:44 GMT  
 Question about memory allocation

Quote:
> It has been said on comp.lang.c that a C implementation is required to
> allow a pointer to point (but not dereference) "one past" a valid block
> of allocated memory.

> Does this mean that in the following code,

> T *ptr=malloc(SIZE * sizeof(T));
> if (ptr) {
>   ptr+SIZE; /* !!! */
>   free(ptr);
> }

> the line I've marked with !!! _must_ be a safe statement and not create
> undefined behaviour, regardless of what type T is?

Yes.

Quote:
> If so, then how does malloc() "know" how big this "safe area" has to be?

In the same way that malloc() must return a pointer that is
properly aligned for an object of any type, the safe area must be
large enough for an object of any type.

In practice, it is only necessary that there be one byte in this
safe area.  Footnote 88 (in C99) gives a better description of
this idea than I can:

     88) Another way to approach pointer arithmetic is first to
         convert the pointer(s) to character pointer(s): In this
         scheme the integer expression added to or subtracted
         from the converted pointer is first multiplied by the
         size of the object originally pointed to, and the
         resulting pointer is converted back to the original
         type. For pointer subtraction, the result of the
         difference between the character pointers is similarly
         divided by the size of the object originally pointed to.

         When viewed in this way, an implementation need only
         provide one extra byte (which may overlap another object
         in the program) just after the end of the object in
         order to satisfy the ``one past the last element''
         requirements.

Quote:
> malloc() is only told how many bytes it must allocate, not what type
> this memory will be used for.
> Isn't it correct that the line I've marked with !!! computes an address
> that is (SIZE*sizeof(T)) bytes after ptr?

Yes.  But there's no reason, on the architectures I'm familiar
with, that a pointer's entire referenced object must be valid in
order for the pointer to be valid.
--
"I should killfile you where you stand, worthless human." --Kaz


Sat, 12 Feb 2005 01:47:55 GMT  
 Question about memory allocation
"Joona I Palaste"

Quote:
> It has been said on comp.lang.c that a C implementation is required to
> allow a pointer to point (but not dereference) "one past" a valid block
> of allocated memory.

> Does this mean that in the following code,

> T *ptr=malloc(SIZE * sizeof(T));
> if (ptr) {
>   ptr+SIZE; /* !!! */
>   free(ptr);
> }

> the line I've marked with !!! _must_ be a safe statement and not create
> undefined behaviour, regardless of what type T is?

Yes.

Quote:
> If so, then how does malloc() "know" how big this "safe area" has to be?
> malloc() is only told how many bytes it must allocate, not what type
> this memory will be used for.

There is no "safe area"; malloc only tries to allocate a contiguous block of
memory of the requested size.

Quote:
> Isn't it correct that the line I've marked with !!! computes an address
> that is (SIZE*sizeof(T)) bytes after ptr?

No, this is correct (well not exactly, but I know what you mean by this).

Quote:
> If I say for example malloc(1100) then how will malloc() "know" whether
> I'm allocating, for example, 11 items of 100 bytes each or 22 items of
> 50 bytes each?

It does not care, and does not have to know.

Quote:
> If I understand right then the "safe area" should be
> 100 bytes in the first case and 50 bytes in the last case.

No, there is no "safe area". The expression ptr+SIZE is pointing to the byte
immediately after the allocated block of memory.

Quote:
> Obviously a type in C can (theoretically) be arbitrarily large. Does
> this mean that (theoretically) malloc() will have to reserve the
> entire address space as a "safe area"?

> I've obviously overlooked something of critical importance, but what is
> it? I hope someone can understand what I'm babbling about. Thanks in
> advance.

Yes, you must be overlooking something. If you did not get it yet, try to draw a
picture of what is actually happening in the code you provided. am sure you
will see the light then.


Sat, 12 Feb 2005 02:05:51 GMT  
 Question about memory allocation
* Joona I Palaste
| It has been said on comp.lang.c that a C implementation is required to
| allow a pointer to point (but not dereference) "one past" a valid block
| of allocated memory.

Right: this holds for any addressable object.

| Does this mean that in the following code,
|
| T *ptr=malloc(SIZE * sizeof(T));
| if (ptr) {
|   ptr+SIZE; /* !!! */
|   free(ptr);
| }
|
| the line I've marked with !!! _must_ be a safe statement and not create
| undefined behaviour, regardless of what type T is?

Yes.  Whatever type the pointer is, the following holds (assuming
malloc() succeeds):

  (char *)(ptr + SIZE) - (char *)ptr == value_passed_to_malloc

| If so, then how does malloc() "know" how big this "safe area" has to be?

There needn't be any actual memory to point at.  You're guaranteed to
be able to form (and use) a pointer with the value of "one past" the
end of the object, but there needn't actually be anything "there" at
all.

| malloc() is only told how many bytes it must allocate, not what type
| this memory will be used for.
| Isn't it correct that the line I've marked with !!! computes an address
| that is (SIZE*sizeof(T)) bytes after ptr?
|
| If I say for example malloc(1100) then how will malloc() "know" whether
| I'm allocating, for example, 11 items of 100 bytes each or 22 items of
| 50 bytes each? If I understand right then the "safe area" should be
| 100 bytes in the first case and 50 bytes in the last case.

There isn't (necessarily) any "safe area" at all.  malloc() doesn't
need any special knowledge about what the memory it allocates will be
used for but it must be possible to form a pointer (of any object
type) to the "edge" of the memory returned by malloc().
The pointer that you're allowed to form needn't actually point to
anything, but it can be useful as an end-of-object marker.  In other
words, you can point here
                       |
                       |
   Some object         V
   ---------------------
   | B | Y | T | E | S | *
   --------------------- |
                         |
                         |
even if there's nothing here

Consider

  char array[SIZE], *p;

  for (p = array; p < sizeof array; p++)
  {
     /* ... */
  }

Without the one-past-the-end rule, loops like this would be invalid C.

Jeremy.



Sat, 12 Feb 2005 02:08:27 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. question about memory allocation

2. General Question about memory allocation

3. Question regarding memory allocation/deallocation

4. few questions about memory allocation

5. Questions on memory allocation and gets()

6. ## question on memory allocation for char strings ##

7. Question on memory allocation

8. Question about memory allocation.

9. question about memory allocation

10. Novice question about memory allocation

11. Tree memory allocation, pool memory allocation

12. URGENT Memory allocation question

 

 
Powered by phpBB® Forum Software