Unchecked deallocation issues

Unchecked deallocation issues

[ejijott]

First some code:

<snip>
  type node;
  type storage is access node;
  type node is
    record
      left:  storage;
      right: storage;
      item:  string(1..50);
      len:   integer := -1;
      count: integer := 0;
    end record;
</snip>

<snip>
        procedure case_delete( Parent : in out Storage; Node: in out
Storage; Direction:Integer ) is
            tempnode:Storage;
        begin
            if Node.left = null and Node.right = null then
                if Direction = 0 then
                    Free(Node);
                    Node:=null;
                else
                    Free(Node);
                    Node:=null;
                end if;
            elsif Node.left /= null xor Node.right /= null then
                if Node.left = null then
                    if Direction = 0 then
                        parent.left:=Node.right;
                        Free(node);
                    else
                        parent.right:=Node.right;
                        Free(node);
                    end if;
                else
                    if Direction = 0 then
                        parent.left:=Node.left;
                        Free(node);
                    else
                        parent.right:=Node.left;
                        Free(node);
                    end if;
                end if;
            else
                put_line("two children");
            end if;
        end case_delete;
</snip>

Free() is implemented as:
procedure Free is new UNCHECKED_DEALLOCATION( Node, Storage);

When I enter case_delete() parent is, obviously, the parent of the
matching node to delete and direction is wheter the matching node is on
the left or right of the parent.

Right.. code snippet above is a part of my BST Remove() handling. The
issue I'm having is using unchecked deallocation... what im figuring
here is that my Free() procedure frees the part of memory that contains
my value, but does nothing to the pointer itself. So, if I just call
Free() on an value-pointed-to and directly after print out
value-pointed-to it _could_ still print out whatever it contains, but
it could change at any time due to the fact that that part of memory is
part of the pool again? And to solve this, I should set the pointer of
the pointed-to-value to null ... is my implementation of this correct,
as in this snippet:

<snip>
                    Free(Node);
                    Node:=null;
</snip>

But, somehow, this doesn't feel right to me. With the snippet above, am
I really setting the pointer to null, or the variable of type Storage
to null?

I tried my code by deleting a leafnode and then inserting a new with
the same value and it ended up in the same position, but I fear that I
have fundamentally misunderstood the use of unchecked deallocation.. or
have I? :)

Thanks in advance!

Re: Unchecked deallocation issues

[Jeffrey R. Carter]

ejijott@gmail.com wrote:

> Right.. code snippet above is a part of my BST Remove() handling. The
> issue I'm having is using unchecked deallocation... what im figuring
> here is that my Free() procedure frees the part of memory that contains
> my value, but does nothing to the pointer itself. So, if I just call
> Free() on an value-pointed-to and directly after print out
> value-pointed-to it _could_ still print out whatever it contains, but
> it could change at any time due to the fact that that part of memory is
> part of the pool again? And to solve this, I should set the pointer of
> the pointed-to-value to null ... is my implementation of this correct,
> as in this snippet:
> 
>                     Free(Node);
>                     Node:=null;

ARM 13.11.2: "After executing Free(X), the value of X is null. [where Free is an 
instantiation of Ada.Unchecked_Deallocation]"

-- 
Jeff Carter
"Why don't you bore a hole in yourself and let the sap run out?"
Horse Feathers
49

Re: Unchecked deallocation issues

[Jeffrey R. Carter]

ejijott@gmail.com wrote:

>         procedure case_delete( Parent : in out Storage; Node: in out
> Storage; Direction:Integer ) is
> 
> When I enter case_delete() parent is, obviously, the parent of the
> matching node to delete and direction is wheter the matching node is on
> the left or right of the parent.

Integer has at least 2 ** 16 values, and probably 2 ** 32 values, and your 
structure has 2 directions. That seems like a lot of opportunities for errors.

You should use something with 2 values for indicating directions. You could use

On_Left : in Boolean

On_Left indicates the matching node is on the left of Parent; not On_Left 
indicates that it's on the right.

Perhaps better is to define your own type to indicate this:

type Direction_ID is (Left, Right);

Direction : in Direction_ID

-- 
Jeff Carter
"Why don't you bore a hole in yourself and let the sap run out?"
Horse Feathers
49

Re: Unchecked deallocation issues

[ejijott]

Mhmm, hmm. Tried using just Free(Node) and indeed Node goes null..
which puzzles me even more.. the litterature im using states that
(freely translated from swedish):

"... using this technique to return dynamically allocated memory you,
yourself, is responsible for making sure that there will exist no
pointers to memory with undefined content".

In my binary tree, if I call Free() on, for example, an leaf .. would
the parents left/right point to "memory with undefined content"? And if
so, how would I go about to make it not point to that? Im guessing that
Free(parent.left) would be the same as calling Free(Node) since they
are both of type Storage? Or have I completly misunderstood the use of
the pointers?

What would an concrete example be of not making sure that there exists
no pointers to memory with undefined content? (I.e. screwing it up :) )

Re: Unchecked deallocation issues

[Alex R. Mosteo]

ejijott@gmail.com wrote:
> Mhmm, hmm. Tried using just Free(Node) and indeed Node goes null..
> which puzzles me even more.. the litterature im using states that
> (freely translated from swedish):
> 
> "... using this technique to return dynamically allocated memory you,
> yourself, is responsible for making sure that there will exist no
> pointers to memory with undefined content".
> 
> In my binary tree, if I call Free() on, for example, an leaf .. would
> the parents left/right point to "memory with undefined content"? And if
> so, how would I go about to make it not point to that? Im guessing that
> Free(parent.left) would be the same as calling Free(Node) since they
> are both of type Storage? Or have I completly misunderstood the use of
> the pointers?

Unchecked_Deallocation will nullify just the pointer passed to it. I.e., 
aliased pointers will not be accordingly nullified. It's plain and old 
allocate/free strategy.

declare
    type String_Access is access all String;
    procedure Free is new Ada.Unchecked_Deallocation
      (String, String_Access);
    A : String_Access := new String'("Hello");
    B : String_Access := A;
begin
    Free (A);
    --  Now A is null but B now points to deallocated space.
end; -- Disclaimer: not compiled.

> What would an concrete example be of not making sure that there exists
> no pointers to memory with undefined content? (I.e. screwing it up :) )

You can do it the old way; i.e. by hand. In that respect the package 
Gnat.Debug_Pools can be very handy to find problems.

I think there was an article about "Smart_Pointers" which specifically 
implement a pointer abstraction where freeing a pointer automatically 
nullified every aliased pointer to the same data.

[Sorry, I just can't find it now. It usually came near the top in google 
when looking for ada smart pointer but no more it seems].


(Not to be confused with some other smart pointers where the smart bit 
refers to automatic deallocation when references go to zero, a la Java. 
That would be, for example:

http://www.adapower.com/index.php?Command=Class&ClassID=Patterns&CID=276

)

Re: Unchecked deallocation issues

[Niklas Holsti]

ejijott@gmail.com wrote:
> Mhmm, hmm. Tried using just Free(Node) and indeed Node goes null..
> which puzzles me even more.. the litterature im using states that
> (freely translated from swedish):
> 
> "... using this technique to return dynamically allocated memory you,
> yourself, is responsible for making sure that there will exist no
> pointers to memory with undefined content".

You don't have to make sure that no such pointers *exist*; you 
only have to make sure that your program does not *use* such 
dangling pointer values. This is similar to the programmer's 
normal obligation not to use uninitialized variables.

> In my binary tree, if I call Free() on, for example, an leaf .. would
> the parents left/right point to "memory with undefined content"?

Yes.

> And if so, how would I go about to make it not point to that?

By setting it to null, for example. But the requirement is not to 
erase all such dangling pointers; the requirement is to write your 
program so that it does not use their dangling values. This can be 
ensured by the program logic, for example through setting other 
flag variables that mark the pointer "invalid" in some way before 
the program assigns a new, valid value to the pointer.

Still, it is certainly recommendable to null all the dangling 
pointers that you know of, because it will make it easier to 
detect program errors that make the program try to use such 
pointers -- an attempt to use null pointer will be detected 
(assuming run-time checks are on), a dangling non-null pointer is 
usually not detected. That's why (instances of) 
Unchecked_Deallocation set their parameter to null.

> Im guessing that
> Free(parent.left) would be the same as calling Free(Node) since they
> are both of type Storage?

Calling Free(parent.left) will deallocate the node accessed by 
parent.left and set the component parent.left to null. If your 
program has some other pointers that access the same node 
(parent.left, before it was deallocated) their values will not be 
nulled automatically and they will be left "dangling". You must 
write your program so that these dangling pointer values are not used.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .