?
Solved

another explanation needed

Posted on 2003-04-01
19
Medium Priority
?
239 Views
Last Modified: 2010-04-01
void allocate(int*& p)
{
   p = new int[10];
}

void main() //...WinMain(...)
{
   int* p;  
   allocate(p);
   
   /*do something on p*/
   /*.................*/
   
   
   delete [] p; // access violation(console/win32)???
                // if not - why not, if yes - why?
}

0
Comment
Question by:podoboq
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 9
  • 6
  • 4
19 Comments
 
LVL 48

Expert Comment

by:AlexFM
ID: 8245842
No access violation.

void allocate(int*& p)  // & - by reference

Pointer int* p is passed by reference to allocate functon. Line
p = new int[10];
changes the original value of pointer passed from main function.
delete[] p works as expected.
0
 
LVL 48

Expert Comment

by:AlexFM
ID: 8245852
If this is not clear:

& means that function works with the same variable which is passed to it and not with copy.
0
 
LVL 12

Expert Comment

by:Salte
ID: 8245908
reference types in C++ are variables that references other variables.

It you have a type T (any type) then:

T x;

allocates an object of type T named x.

T & y = x;

Allocates an object of type reference to T named y and it is set to reference x.

y = foo;

will now call the assignment operator of type T on whatever object y references, i.e. x. so the above is exactly the same as if you had written:

x = foo;

In your case:

int * p;

allocate(p);

p is passed by reference so whenever the p in allocate is modified it actually modifies the variable p defined in the function that calls allcoate.

so after that call the variable p will point to an array and so delete [] p will work as expected.

Alf
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:podoboq
ID: 8245921
and what if
void allocate(itn&*);
is in DLL? then DLL has its own heap. how to free mem?

0
 

Author Comment

by:podoboq
ID: 8245972
so the app has a heap. do functions allocate mem using that very heap? what happens to function vars(locals) after exiting function?
what about global and static vars?
0
 
LVL 12

Accepted Solution

by:
Salte earned 500 total points
ID: 8245987
If a DLL has its own heap or not depends on the platform.

If the DLL uses its own heap it is probably best to let the DLL delete the object also, call a DLL function that will destroy the object:

instead of simply:

delete [] p;

do:

destroy(p);

and let destroy be a function in the DLL that do the delete []:

extern "C" void __stdcall destroy(int * p)
{
   delete [] p;
}

void be a typical PC windows DLL function to destroy the array.

Alf
0
 
LVL 48

Expert Comment

by:AlexFM
ID: 8245990
There is no heap in Dll. Each process has one heap (may be more, if additional heap is allocated). Dll is part of the process.
0
 

Author Comment

by:podoboq
ID: 8246012
and what if
void allocate(itn&*);
is in DLL? then DLL has its own heap. how to free mem?

0
 

Author Comment

by:podoboq
ID: 8246045
>There is no heap in Dll
thats not quite true

_CrtIsValidHeapPointer assertion fails
0
 
LVL 48

Expert Comment

by:AlexFM
ID: 8246152
EE bosses are talking about technical qualification tests for experts. If this is a test, I failed, and my account will be closed soon. Actually, I need to confess, I don't know exactly what is Dll.
0
 
LVL 12

Expert Comment

by:Salte
ID: 8246255
Ok, here is the deal with variables and where to find them.

for global variables (outside of functions and outside of classes), they are allocated on the .data segment and possibly an .rodata segment for read only data if the system support that (typically const objects).

The name of this segment doesn't have to be .data but on Unix that is the name that is used and it is also the name used in Windows. Other systems may use other names.

For static variables anywhere (in classes, in functions or in global places) they are also allocated space in .data or .rodata.

Function code is placed in .text segment which contain all the machine instructions for the function bodies etc.

In addition there's a segment .bss which is used for large data objects that are initialized with all 0. The executable can be smaller if such objects are placed in .bss since .bss is all zero the segment isn't actually stored in the executable file, only the size of the segment is stored in it and the system loader allocate space for it when it loads the executable into your process virtual memory space.

In addition there are portions of memory used by OS and other stuff for other purpose.

Whatever virtual memory is not used by OS, nor by .data, .rodata, .text and .bss is available as heap and stack. Typically a large portion of this is allocated as combined heap stack and the stack start at the top and grows down while the heap starts at the bottom and grows up. There are no fixed size of these two so if a program uses lots of stack but little heap or if the program uses lots of heap but little stack it will work OK in either way, only when the heap limit and the stack limit collide will the program run out of heap memory. Well, one of the heaps.

The program can also use other pockets of free memory space to allocate a heap or for other uses if it wants to. For example a program can load DLLs or it can map a file into memory so that reading that memory is a fast and easy way to read the file. Many systems such as windows and unix (including Linux) support this 'mapping file to memory' feature. All of these can allocate blocks of virtual memory and reserve it for its use. A heap allocator can also do the same and allocate a block of memory so that next time you do a new it might allocate a block from that memory instead.

So on most systems a DLL will not have its own heap space but use the same heap as the main executable program and so which one deletes the block may appear the same. However, there may be reasons why you would want the DLL to delete the block anyway. If for example the main .exe has overloaded new and delete the DLL will not make use of those overloaded versions but use the standard new and delete from the C++ run time library. If so it is a bad idea to have your overloaded delete delete an object that was allocated by a standard new and not your overloaded new. Similarly it is a bad idea to let the DLL delete an object that was allocated by your overloaded new. In some cases that might work but that depends on how the overload was done and how it works. The general rule is that whoever allocate an object should be the one that delete it.

When your program runs it also have a stack, in fact it may have more than one stack if you run several threads. If you declare local variables in a function they will be allocated on the stack along with arguments to the function and temporary variables. Typically a stack frame will also have some system pointers pointing back to previous stack frame, return address etc so a stack frame will typically look like this:

      arg[n]
      arg[n-1]
      ....
      arg[2]
      arg[1]
      return addr
f---> previous stack frame
      local variables
      temporary variables
sp --> unused space.

The f--> points to an approximate location where the stack frame pointer typically points. The return address is then at offset +4, arg1 at offset +8, arg2 at offset 8 + sizeof(arg1) etc. (these offsets may differ slightly from machine to another, but typically arg1 has a higher offset than return addr and arg2 come at a higher address than arg1 - unless the order of the arguments are reversed).

This is one example of a C and C++ style stack frame. Often a platform provide more than one "calling convention" such as __cdecl __stdcall, __fastcall etc and these might all differ from the above in one or more respects. The above stack frame layout support the concept of variable number of arguments and is therefore the form used for __cdecl functions in windows.

When calling a subroutine or function you simply use the unused space to store the parameter values to the function and then issue a CALL or similar machine instruction so that the function is called. The CALL instruction will typically push the return address on the stack just after the parameters and then the first thing the function does after the call is to push the stack frame pointer onto the stack after the return address and then copy the stack free pointer into the stack frame pointer and set the stack free pointer to point past the local variables and temporary variables that the function itself need space for. Well, this is one way to do it, again __cdecl, __stdcall etc will do things slightly differently, for example in __cdecl I believe it is the caller that sets up the stack frame instead of the called function, similarly, when the function return it is the caller that will fix up the stack back again.

To return from a frame as above the stack frame pointer is copied into the stack free register (the register that points to the unused part of the stack) and the stack frame register retrieves the stored value from the stack and then the function returns using the return addr stored on the stack. Again, the differences in "calling convention" will do this slightly differently. Note that this will automatically make the stack frame that the function used free and any local variables allocated on it will be automatically deallocated by the above procedure.

Due to these differences it is very important that you never attempt to call a function that was defined as __stdcall by declaring it as __cdecl or vice versa. To ensure that this is very difficult to do most compilers that do support more than one calling convention will give them slightly different names to the linker so that it is impossible to call the right function using wrong calling convention. The linker will simply not see the names as matching and won't link the call to the function.

so to allocate an array on the stack you do:

void do_something()
{
   int arr[10];

}

such an array do not need to be deallocated, it is automatically reclaimed when the function returns (as per the explanation above).

Alf
0
 

Author Comment

by:podoboq
ID: 8246313
thanks all
0
 

Author Comment

by:podoboq
ID: 8246400
by the way:

void do_something()
{
  int arr[10];

}
such an array do not need to be deallocated, it is automatically reclaimed when the function returns (as per the explanation above).

it looks correct, we all know that, but what can you tell about that:

int* do_something()
{
  int arr[]={0,1,2,3,4,5,6};
  return arr;

}

void main()
{
   int i = do_something()[4]; // i = 4!!!
}

how it works then?







0
 

Author Comment

by:podoboq
ID: 8246446
by the way:

void do_something()
{
  int arr[10];

}
such an array do not need to be deallocated, it is automatically reclaimed when the function returns (as per the explanation above).

it looks correct, we all know that, but what can you tell about that:

int* do_something()
{
  int arr[]={0,1,2,3,4,5,6};
  return arr;

}

void main()
{
   int i = do_something()[4]; // i = 4!!!
}

how it works then?







0
 
LVL 12

Expert Comment

by:Salte
ID: 8246689
AlexFM,

DLL = Dynamically Linked Library

it's the same as .so files under unixes.

The issue of wether or not a DLL share a heap with the main executable depends partly on what you mean by 'heap'.

If a heap is a set of functions that manipulate a block of area and give out slices of it as the program needs them and able to reclaim them when the program no longer needs them then there are good reasons why a DLL and .exe should not share the heap.

The .exe heap may be overloaded to some user defined heap. This heap is completely unknown to the DLL and the DLL can also be used by other .exe files which do not use this overloaded heap and so it is best to let the DLL use its own heap.

The DLL may use an overloaded heap but the .exe has no access to that and doesn't want it either. Again the DLL and the .EXE need their own heap.

Both the DLL and the .EXE may use an overloaded heap but they use different overloads. Again, the same story.

The heap is managed by linking in some library code that defines functions for this. The standard C++ library  export operator new and operator delete that can be used by users but they can also define their own and if so then their program will be linked without the standard C++ library version.

Typically the standard C++ library version calls malloc to actually allocate the space. malloc() is a low level C library set of functions to manipulate a heap.

Typically malloc() operate by a set of data structures used by its own purposes and it has a set of functions to export its functionality. The DLL and the .EXE may both independently of each other load separate versions of this malloc library.

Hope this explains why even though they may share the same memory area they have separate heaps. Each malloc library will then use the system allocator to allocate a portion of virtual memory for use by its own use. The system allocator is a platform dependent set of functions to manipulate the virtual memory and allocate chunks of it for use by heap.

Win32 have a function and Unix has another function to fascilitate this. However, a portable malloc version uses the functionality to map a file to memory to allocate space for a heap. This function can also be used without a file to just allocate a portion of virtual memory for whatever use you might want and malloc() uses it to create its data structures for heap.

Writing a good memory allcoator is hard. Not because it is very difficult to do but because there are many conflicting concerns. It must be safe, it must be fast, it must be efficient in memory usage, it must not create fragmented memory etc etc etc.

A simple memory allocator is simply one that have a heap from base to end and the unused pointer pointing in between those two and pointing to the unused part. A simple malloc may then simply do:

void * malloc(size_t sz)
{
   unsigned char * p = unused;
   unused = p + sz;
   return (void *)p;
}

A free function cannot give the space back to unused though because you may have allocated space after it. If you allocate A and then B and then free A then you can't set unused to point to A since that would make block B unused but it is still in use, One way to solve that is to have a freelist:

struct entry {
   entry * next;
};

and insert the free'd block into a free list:

void free(void * p)
{
   struct entry * e = (entry *)p;
   e -> next = freelist;
   freelist = p;
}

However, this raises the issue that when you allocate you should probably first check the freelist and so you want to amend the malloc function. One problem is that you need to ensure that a free list entry is big enough for the current request and thus every block must have a size stored somewhere. So you amend the malloc function like this:

// replace entry with this:
struct block {
   size_t sz;
   block * next;
};

void * malloc(size_t sz)
{
   struct block * prev = 0;
   struct block * p = freelist;
   while (p != 0 && p -> sz < sz) {
      prev = p;
      p = p -> next;
   }
   if (p != 0) {
      // p -> sz >= sz
      // unlink p from freelist.
      if (prev == 0)
         freelist = p -> next;
      else
         prev -> next = p -> next;
      // return allocated block.
      return (void *) & p -> next;
   }
   // no entry in freelist.
   p = (block *)unused;
   // assuming that unused is declared as char *
   unused += sizeof(block *) + sz;
   return (void *) & p -> next;
}

Now this may work for a while but it has numerous problems, for one thing you do not check if unused reaches end of the heap and what to do if it does. Another problem is that if you want to allocate a block of 16 bytes and you find a block of 2000 bytes available you return that 2000 byte block for the 16 byte data thus waisting 1984 bytes.

There are several ways to solve that problem.

Another problem is also that when you free you just insert the element in the free list. If you have a block immediately before it in memory and/or immediately after it that is also free you should perhaps combine those into one bigger block.

There are several ways to solve that problem too.

About the end you simply should test if the new value for unused is > end and if it is you shouldn't just return the block but should return 0 (out of memory) or perhaps you should allcoate a bigger heap and try to allocate the object from the new bigger heap.


For the problem of wasting space there are several ways. One way is to split a block if it is too large. Specifically if it is so large that it can successfully be split into two blocks then you can split it and return the unused portion back into the freelist and return the part that fit exactly for the request.

Another way is to keep an array of freelists and keep one freelist for each size, well almost.

First off, on a typical machine you want the returned block to be such that a double value will be properly aligned at the start of the block. This is the way compilers with alignment likes it since they assume that all objects are such that offset 0 start at an double alignment unless the object is such that it require less. Since you don't know what the object is to be used for one should assume the worst case - which is double - and always return a pointer value that is always divisible by sizeof(double). To ensure this each block must be a multiple of sizeof(double). To be more specific I will use the PC architecture with sizeof(int) == 4 and sizeof(double) == 8 here. So if each address is a multiple of 8 then each block must also be a multiple of 8 so step 1 is that we do not allocate exactly the number of bytes the user request but we allocate a value that is >= that size but a multiple of 8:

sz = (sz + 7) & ~7;

ensures that the size is always a multiple of 8. Since we have multiple of 8 we can have an array of freelists, so that freelist[0] is a freelist of blocks that have 8 bytes available, freelist[1] is a freelist of blocks that have 16 bytes available, freelist[2] have 24 bytes available etc.

Of course we also need one entry of this array to have a freelist of 'all others' for the blocks that are much higher.

This makes it easy to pick an entry of possible size, if we need 8 bytes we simply check if freelist[0] has an entry, if it does we use it. If it doesn't we check if freelist[1] has an entry, if it does we divide it in two and put one into the freelist[0] and the other to the caller. If freelist[1] is also empty we check freelist[2], if found we divide it in two and put one entry (16 bytes) into freelist[1] and the other (8 bytes) to user. etc.

Similarly if we want 16 bytes, we first check freelist[1] and if none there we check the next list freelist[2] and if found we split and put one entry (8 bytes) into freelist[0] and the other to user etc.

If all freelists are empty we allocate from unused and then we allcoate exactly enough to make one 8 byte entry and also make sure that the allocated object is divisible by 8 and return that block to user.

When freeing the objects we can see if the object just before and just after the block is also free, if so we remove them from freelist, combine them into one bigger block and place it in freelist based on the new size of the combined block.

To combine objects based on address you could keep the freelist sorted on address of the block. However, that would require you to walk through the list. You could also make the objects like this:

// use this when the block is in use.
int sz;
char userdata[sz];
int sz; // store size here also at the end of the block.

// use this when the block is free:
int sz;
int freex; // index in freelist array for this block.
block * next; // next in freelist.
char not_used[sz - 8];
int sz; // size is here also at the end of the block.

Since size is stored both at the beginning of the block and at the end of the block it is easy for the allocator if it has a pointer to a block to check the size at the entry just before it and then subtract that pointer with sz bytes to get to the beginning of previous pointer.

It must also be able to detect if a block is free or not. Since sz is always a multiple of 8 this is easiest handled by using one of the 3 available bits at the bottom of sz. For example sz | 1 is the stored size when the block is free, sz | 0 == sz is the stored size when the block is in use.

There, we're well on our way to implement an allocator.

Essentially, there are many choices here and one allcoator is likely to make a different choice from another allocator and it should be clear that these choices are to a large extent incompatible and if you allocate an object using one allocator it is devastating if you deallocate it using a different allocator.

So, always make sure that whatever module allocates an object should also - as a general rule - be the module that deallocates it.

There are exceptions to this rule, if you want to return a VB string to VB you might have to allcoate the string. It is then important that you use VB's allocator to allocate the string so that when VB deallocates the string it will use the corresponding deallocator. A similar situation exist with functions like strdup() and aprintf() of the glibc which allocates strings. It is then important that they document whatever method they use to allocate those strings and that you use the same method to deallocate them. For example strdup() uses malloc() so free() is correct - and not delete []. It is possible that on some implementations delete [] would work as free() and delete and delete [] might be compatible on those implementations but in general it won't. I often reimplement strdup for that reason so that I have a strdup that uses new:

namespace my {
char * strdup(const char * str)
{
   if (str == 0)
      return 0;
   size_t len = strlen(str)+1;
   char * s = new char[len];
   memcpy(s,str,len);
   return s;
}
};

using my::strdup() instead of standard strdup allows me to delete [] the strings instead of free()'ing them.

Alf
0
 
LVL 12

Expert Comment

by:Salte
ID: 8246798

it looks correct, we all know that, but what can you tell about that:

int* do_something()
{
 int arr[]={0,1,2,3,4,5,6};

This appears to be a non-standard extension. Since arr is not a static array it is allocated on the stack so initializing it with an aggregate appear to me to be non-standard. It is possible that the implementation copies the array to the stack before the user code start. That isn't standard C++ though since standard C++ would expect a static array if you initialize it with an aggregate.

If you initialize it with a constructor it would be standard C++ code and would be compiled into a call to the constructor when executing the definition of arr.

 return arr;

}

void main()
{
  int i = do_something()[4]; // i = 4!!!
}

how it works then? This doesn't really works. The stack area is now free()'d however, freeing the stack area doesn't erase it. It still has the values 0,1,2,3,4,5,6 or so until you start to call other functions to modify it. In your simple example you do not call any such functions and so it is quite possible that the returned array still exist, at least portions of it. It is possible that you would get some 'random' result if you tried to index element 0 of that array but it is also possible that that would work.

However, if you call a function and then try to access the array I am pretty sure that you would get wrong result if the array was copied to the stack.

So, the answer to your "how it works then?" is that "It doesn't work, it only appear to work in your specific example for your specific compiler"

Change the code to:

void call_some_other_func()
{
   int arr[50];

   for (int i = 0; i < 50; ++i) arr[50] = 0x53abcf73;
}

void main()
{
  int * a = do_something();
  call_some_other_func();
  int i = a[4]; // i == 4???? I think not.
}

my guess is that i would equal 0x53abcf73 and not 4 - proof that it really didn't work after all.

Alf
0
 

Author Comment

by:podoboq
ID: 8247094
cool:)))))
on my machine(NT5.2) a = 0x53abcf73 (ok, i got it - not necessary 0x53abcf73 and not 4 either:))

so...

void allocate(int*& p){
   p = new int[10];
   p[3] = 3;
}

void main(){
  int* p;  
  allocate(p);
  int t = p[3];
  ASSERT(3 == t); //...is ok.
}




0
 
LVL 12

Expert Comment

by:Salte
ID: 8247336
Yes :-)

Alf
0
 

Author Comment

by:podoboq
ID: 8248091
thank you much, salte, ive learned a lot today!
0

Featured Post

On Demand Webinar: Networking for the Cloud Era

Ready to improve network connectivity? Watch this webinar to learn how SD-WANs and a one-click instant connect tool can boost provisions, deployment, and management of your cloud connection.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
Suggested Courses

764 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question