Solved

Dynamic/Double Mem Allocation

Posted on 2007-11-15
33
346 Views
Last Modified: 2010-04-15
Hey guys!
 
I found an interesting snippet of C code, which once implemented, would aid one's understanding of C memory allocation. The requirement involves coming up with implementations for the function declarations below, followed by a test program. The implementations should validate: DEF my_def = CreateDEF(); my_def->abc->c = 5;
 
void FreeDEF(ABC *pabc);
 
DEF *CreateDEF(void);
 
typedef struct DEF {
    ABC *abc;    
    int d;
    int e;
    int f;    
};
 
typedef struct ABC {
    int      a;
    int      b;
    int      c;
};
0
Comment
Question by:Koraxen
  • 5
  • 5
  • 5
  • +4
33 Comments
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 20296441
is this a homework? the single malloc requirement is mandatory?
It wont be an elegant solution.

The most common solution will be use 2 mallocs, first a malloc() to create the DEF structure, and then a second malloc to create the ABC structure, finally store the pointer to ABC into the DEF.
For this approach, FreeDEF() function should have two free() calls.

For this specific example, to store ABC as a pointer makes no much sense, would be simpler:
typedef struct {
      int d;
      int e;
      int f;
      ABC abc;  /* without a pointer */
} DEF;
 
so you can create with a single malloc. Waiting for your feedback...
0
 
LVL 5

Expert Comment

by:abith
ID: 20296541
allocate memory for a void*v with sizeof(ABC) + sizeof(DEF);
      void *v = malloc(sizeof (ABC) + sizeof(DEF));

assign v's address + sizeof(ABC) to *oDEF
      DEF *d = (DEF*) ((char*)v + sizeof(ABC));

then assign v's address to oDef->abc
              d->abc = (ABC*)v ;

now, the whole memory is pointed by d->abc.
so when you pass this to FreeDEF, expected memory will get destroyed.

NOTE: i dont find any use of this!!? anyway its good for learning
0
 

Author Comment

by:Koraxen
ID: 20296559
The requirement is to use a single malloc. It has no practical use, except to get acquainted malloc, pointers, etc.

It looks like abith proposed a solution though, but I haven't understood it yet.

Abith, is this what you are suggesting? :

DEF *CreateDEF (void) {

    void *v = malloc(sizeof (ABC) + sizeof(DEF));

    DEF *d = (DEF*) ((char*)v + sizeof(ABC));

    d->abc = (ABC*)v ;

}

 

void FreeDEF (ABC *pabc) {

 

}

Open in new window

0
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 20296579
you forgot the return value:


DEF *CreateDEF (void) {

    void *v = malloc(sizeof (ABC) + sizeof(DEF));

    DEF *d = (DEF*) ((char*)v + sizeof(ABC));

    d->abc = (ABC*)v ;

    return d;   /* <---- this */

}

Open in new window

0
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 20296586
but will be a bit cleaner:
DEF *CreateDEF (void) {

    ABC *abc = (ABC *)malloc(sizeof (ABC) + sizeof(DEF));

    DEF *def = (DEF*)((char*)abc + sizeof(ABC));

    def->a   = abc;

    return def;

}

Open in new window

0
 
LVL 5

Accepted Solution

by:
abith earned 200 total points
ID: 20296593
>>    void *v = malloc(sizeof (ABC) + sizeof(DEF));
             Allocating memory with size of ABC and DEF.
>>    DEF *d = (DEF*) ((char*)v + sizeof(ABC));
              since your FreeDEF function param is ABC, ABC should have all memory, so that we can delete. so in the next line ( d->abc = (ABC*)v ; )i am assinging *v to d->abc.
              But d should have memroy, so that we can access d->abc. so i am taking the memory after the sizeof ABC and assining to d.
          >> ((char*)v + sizeof(ABC));
             Since v is void* we can not increment/decrement address position. so i am just converting to char* and adding the sizeof (ABC) bytes to point the memory location after ABC.

if you dont understand still, please mention the place where you are getting struggle.
0
 
LVL 5

Expert Comment

by:abith
ID: 20296603
>>Abith, is this what you are suggesting? :
Yes
0
 
LVL 5

Expert Comment

by:abith
ID: 20296606
With returning  d

DEF *CreateDEF (void) {
.....
return d;
}
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20296716
>> It has no practical use

Oh, it does. It avoids having to call malloc more than once. Allocating memory has a certain overhead ... If you can make one call instead of two, then you won some time. If you can do 1 call instead of 1000, then you've won quite a bit of time.

For performance critical applications that need to allocate a lot of small blocks of memory, this is an often used technique.
0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 100 total points
ID: 20296821
#include <stdlib.h>
typedef struct {
  int      a;
  int      b;
  int      c;
} ABC;

typedef struct {
  int d;
  int e;
  int f;
  ABC *abc;
} DEF;
DEF *CreateDEF (void) {
  struct ABCDEF{
    ABC abc;
    DEF def;
  } *abcdef = (struct ABCDEF *)malloc(sizeof(struct ABCDEF));
  abcdef->def.abc = &abcdef->abc;
  return &abcdef->def;
}
main(){
  DEF *pdef = CreateDEF ();
  pdef->abc->a =  10;
}
0
 
LVL 11

Assisted Solution

by:lbertacco
lbertacco earned 100 total points
ID: 20297042
In my opinion the simplest code is:
...
DEF *CreateDEF (void) {
  DEF *def_p=(DEF*)malloc(sizeof(DEF)+sizeof(ABC));
  if(def_p!=NULL) def_p->abc=(ABC*)((char *)def_p+sizeof(DEF));
  return def_p;
}

Which is similar to previous posts but allocating DEF in the lower part and ABC in the higher part, which seems more natural to me as DEF "contains" ABC. Also this reduce assignments and pointer ops.

Ozo idea is also nice but I don't see any advantage with respect to my "more direct" code.

0
 
LVL 84

Expert Comment

by:ozo
ID: 20297110
putting them in a struct ensures that any alignment requirements are satisfied.
the assignments and ops seem equivalent.

the check for def_p!=NULL properly avoids undefined behaviour in CreateDEF
but it doesn't help if it would then be used as
//    DEF *pdef = CreateDEF ();
//        pdef->abc->a =  10;
0
 
LVL 11

Expert Comment

by:lbertacco
ID: 20297202
>putting them in a struct ensures that any alignment requirements are satisfied.
If your compiler is aligning, then also the sizeof operator rounds up the size of structs to guarantee proper alignments, if it's not aligning then even putting them on a struct doesn't align them. So it shouldn't make any difference at all. Can you come up with an example where it actually makes a difference?

>the assignments and ops seem equivalent.

Agree

>the check for def_p!=NULL properly avoids undefined behaviour in CreateDEF
>but it doesn't help if it would then be used as
Agree on this too, but in general the idea is to write your functions so that they always work ok, and leave it to the user to decide whether to checks for exceptions or not (for example you may decide not to check for null pointers in sample or test code - as in the case of this post -, but of course you do check in production code)
0
 
LVL 84

Expert Comment

by:ozo
ID: 20297350
sizeof(DEF) accounts for alignment requirements of DEF, but not alignment requirements of ABC
In this case, the requirements are probably at least as strict on most implementations, so this example shouldn't make an actual difference.

To be safe if the requirement is to be used as
//    DEF *pdef = CreateDEF ();
//        pdef->abc->a =  10;
the function should probably exit if the malloc fails.

(BTW, why is my comment marked as "Proposed Solution"?)
0
 

Author Comment

by:Koraxen
ID: 20298666
Not sure why your post is marked as proposed solution ozo, I havent marked anything yet.

And would the free method just require doing what's in the snippet below?

Or should it be more complicated?
void FreeDEF (ABC *pabc) {

    free(pabc);

}

Open in new window

0
 
LVL 11

Expert Comment

by:lbertacco
ID: 20299213
Yes, since you allocated it with a single call to malloc, you just need to call "free" once.
However, since the function in named FreeDEF, it is probably supposed to be passed a pointer to DEF not to ABC. Also, be carefull to call free() passing it the pointer as returned by malloc.
That is, if you use my code, than you shoud call "free(pdef)", which is passing the same pointer returned by CreateDEF() as in:

void FreeDEF(DEF *pdef) {
free(pdef);
}

main() {
...
    DEF *pdef = CreateDEF ();
    pdef->abc->a =  10;
    FreeDEF(pdef);
...


If you use Ozo's version, you should call "free(pdef->abc)" (more confusing?) as in
void FreeDEF(DEF *pdef) {
free(pdef->abc);
}

main() {
...
    DEF *pdef = CreateDEF ();
    pdef->abc->a =  10;
    FreeDEF(pdef);
...

0
Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

 

Author Comment

by:Koraxen
ID: 20302107
An extension to this question would now include running the following code:

What does the last line do? I'm unsure about what *(int*) means.
DEF *pdef = CreateDEF();

int value;
 

value = (int) pdef;

value += 8;
 

*(int *) value =  10;

Open in new window

0
 
LVL 84

Expert Comment

by:ozo
ID: 20302136
(int*) casts value into a pointer to an integer
and the * dereferences that pointer
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20302149
>> What does the last line do?

It interpretes value as a pointer to int, then dereferences it, and stores 10 in there.

It is quite "dangerous", and not recommended to do this though. Especially because of this line :

value = (int) pdef;
0
 
LVL 84

Expert Comment

by:ozo
ID: 20302203
maybe you meant to say value += offsetof(DEF,f)
0
 
LVL 11

Expert Comment

by:lbertacco
ID: 20303632
Anyway the effect is that initially value is the memory address of pdef, and since "d" is the first member of pdef (so it has the same memory address of pdef) value is also the memory address of pdef->d.
Then you add 8 to value, and since each integer (on a 32bit machine) takes 4 bytes, adding 8 essentially getting the memory address of "f". In other words, member "d" is at the same memory address as the def struct, "e" is stored 4 bytes above that, and "f" is 4 bytes further above "e", so it is 8 bytes above the start of the def struct.
So now the value variable has the address of pdef->f.
Finally you cast value to a pointer to integer and dereference it, which means that you are storing value 10 at the address stored in value, and the overall net effect is the same as
pdef->f=10;
that is, you set the f member of def to 10.
0
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 100 total points
ID: 20328775
>>>> putting them in a struct ensures that any alignment
>>>> requirements are satisfied. the assignments and ops seem equivalent.

ozo was right that depending on alignment, his solution gives different sizes and different addresses to that of lbertacco but nevertheless for lbertacco's solution all structs were properly aligned.

 Assume we have an alignment of 16 bytes, an integer size of 4 and a pointer size of 8. Then DEF was aligned like

  0   4   8      16
  d   e   f       abc

and has size 24. That is *not* a multiple of 16 as lbertacco has suggested.

ABC was aligned  

  0   4   8  
  a   b   c

and has a size of 12.

So with ozo's solution we have  &def.abc == &def + 24 as the struct ABC correctly was aligned at 16byte boundary while with lbertacco's solution we have  &def.abc == &def + 20;

I made

    struct ABC
    {
        int a;
        int b;
        int c;
    };
    struct DEF
    {
        int d;
        int e;
        int f;
        ABC * pabc;
    };

    struct ABCDEF
    {
      DEF def;
      ABC abc;
   };

   ABCDEF abcdef;

and had address 0x12fde8 both for 'abcdef' and 'abcdef.def' and the 'abcdef.abc' correctly was aligned with 16 bytes alignment at address 0x12fdfc and 'abcdef.def.pabc' at  0x12fdf4.  None of the addresses was a multiple of 16 what means that - at least with my compiler - pointers to structures can have any address even an odd byte address.

    char buf[100] = { 0 };
    abcdef.def.pabc = (ABC*)&buf[1];
    abcdef.abc.a = 1;
    abcdef.abc.b = 2;
    abcdef.abc.c = 3;

    *(abcdef.def.pabc) = abcdef.abc;

The struct correctly was assigned though any of the integers of the left side of the assignment was at an odd address.

Regards, Alex






   
0
 
LVL 11

Expert Comment

by:lbertacco
ID: 20329748
There are some imprecisions. a) I never said that sizeof rounds up to a multiple of 16. It rounds up to whatever your compiler is aligning. b) as you see, in ozo container struct, the abc struct is not aligned to a multiple of 16; indeed it's not aligning more than the sizeof operator rounds up. c) the address 0x12fde8 is not very meaningful as the fact that it's a multiple of something doesn't mean that the compiler placed it on that alignment on a purpose. d) as the def struct is a multiple of 8, you cannot use it to see if the compiler is aligning to a multiple of 8 or anything smaller than that as this struct would align naturally to 8 even if the compiler doesn't do anything.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20329978
>>>> It rounds up to whatever your compiler is aligning
Maybe I still misunderstand you but I can can set struct aligning to 16 bytes and nevertheless I get a size of 12 for a struct with 3 integers. There is no 'round up'; it simply is the size of the struct.

>>>> as you see, in ozo container struct, the abc struct is not aligned to a multiple of 16;
That was a mistake by me. I played wit 1 byte alignment when posting these addresses. With 16 byte alignment I got 0x12fddc for 'def' member and 0x12fdfc for 'abc' member and a size of 24 for the 'def'.

>>>> c) .... d) ....
I fear that these statements also were based on my wrong addresses.

Note, the results mean that your code is fully valid, as each member correctly was aligned within the structure it was defined in, regardless whether the start address of the struct is a multiple of the alignment or not.
0
 

Author Comment

by:Koraxen
ID: 20371583
My end solution put together:

void FreeDEF (ABC *pabc) {
      free(pabc); // Release resources
}

DEF *CreateDEF(void) {
        void *my_mem = malloc(sizeof (ABC) + sizeof(DEF)); // Double struct mem allocation
      DEF *my_def = (DEF)( sizeof(ABC) + (char*)my_mem );
      my_def->abc = (ABC*)my_mem ; // Provide memory for ABC
      return my_def; // Return DEF
}

0
 
LVL 5

Expert Comment

by:abith
ID: 20371615
this will work perfectly.

do you get any issue?
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20371922
>>>> My end solution put together:
That is pretty much the same as lbertacco posted above? And where most others refered to. What was the reason for reopening the thread?
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20371953
     DEF *my_def = (DEF)( sizeof(ABC) + (char*)my_mem );

Make that :

      DEF *my_def = (DEF*)( sizeof(ABC) + (char*)my_mem );
0
 

Author Comment

by:Koraxen
ID: 20374760
Was reopened because I was given additional requirements/constraints about the question, which I'm including in the final solution here:

DEF *CreateDEF(void) {
      void *my_mem = (void*)malloc(sizeof(ABC) * sizeof(DEF)); // Double struct mem allocation
      DEF *my_def = (DEF)( (int*)my_mem * 32 );
      my_def->abc = (ABC*)my_mem ; // Provide memory for ABC
      return my_def; // Return DEF
}
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20375298
>>>>     DEF *my_def = (DEF)( (int*)my_mem * 32 );

The statement doesn't compile for three reasons:
 
   - a int* cannot be multiplied with an int
   - a int* cannot be casted to a struct DEF
   - a struct DEF cannot be casted to a DEF*  

You most likely you want

     DEF *my_def = (DEF*)( (char*)my_mem + sizeof(ABC) );

But then you have to free with

  free(m_def ->abc);

what works but is strange and error-prone.


>>>> (int*)my_mem * 32

if you multiply a pointer with 32 the resulting address is normally invalid.  Can you explain?


0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20375339
I overlooked one more error:

>>>> malloc(sizeof(ABC) * sizeof(DEF));

Here you multiplied the sizes of both structs what never is a valid size for DEF + ABC  (even for arrays of ABC).


Why not

DEF *CreateDEF(void) {
      DEF *my_def = (DEF*)malloc(sizeof(DEF) + sizeof(ABC) * ); // Double struct mem allocation
      my_def->abc = (ABC*)((char*)my_def + sizeof(DEF)); // Provide memory for ABC
      return my_def; // Return DEF
}

as we already had it a few times above?

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20376057
Did you fix the error I pointed out in my previous post ?
0

Featured Post

6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Problem to scan all sheets 3 82
ShiftLeft challenge 21 66
SQL400 max size 5 57
C# code editing and collaboration 3 49
Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.

747 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

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now