Unix Programming - memory allocation/alignment under linux

Author

memory allocation/alignment under linux

puzzlecracker

2005-01-18, 5:56 pm

Got Confused on the interview with memory alligment questions... PLEASE
HELP -- How much bytes of memory will structs below take on 32 bit
machine? What about 64 bit machine? Why is it different? (if it's
relevent, use standard size of datatypes)

a)

Code:
struct
{
short int a;
int b;
};

b)
Code:
struct{
short int a;
int b;
int somefunc();
virtual int func1();
};

c) Very Tricky (Hint: it is tricky with virtual function (or should I
say pointers to vtable...you should know something about vtables in
last but clever case))

Code:
struct{
short int a;
int b;
virtual int func_1();
virtual int func_2();
:
:
virtual int func_n();
};

Rich Teer

2005-01-18, 5:56 pm

On Tue, 18 Jan 2005, puzzlecracker wrote:

> Got Confused on the interview with memory alligment questions... PLEASE

Frankly, if you get a job based on the answers you get here for interview
questions, you won't last very long in that job. The guys employee tend
to know the answer to the technical questions they ask, so just be honest
and say you don't know. Beleive it or not, employers appreciate honesty...

Read some good programming books (my book, Solaris Systems Programming,
even has a section on memory alignment), and get some experience even
if it is a junior position. Greater rewards will come with time and
experience...

--
Rich Teer, SCNA, SCSA, author of "Solaris Systems Programming"

President,
Rite Online Inc.

Voice: +1 (250) 979-1638
URL: http://www.rite-group.com/rich

Måns Rullgård

2005-01-18, 5:56 pm

puzzlecracker

2005-01-18, 5:56 pm

M=E5ns Rullg=E5rd wrote:
> "puzzlecracker" <ironsel2000@gmail.com> writes:
>
PLEASE[vbcol=seagreen]
bit[vbcol=seagreen]
>
> Ask the compiler, use sizeof.
>
> --
> M=E5ns Rullg=E5rd
> mru@inprovide.com

> Ask the compiler, use sizeof.

I am not looking for that, but for an explantion. Can someone ballpark
me through it? Number is not what I'm looking for.
thanks

Regards,=20

..cracker

Måns Rullgård

2005-01-18, 5:56 pm

"puzzlecracker" <ironsel2000@gmail.com> writes:

> Måns Rullgård wrote:
>
> I am not looking for that, but for an explantion. Can someone ballpark
> me through it? Number is not what I'm looking for.

Alright, is there something specific you are confused about? For a
general run-down on struct member alignment, referring to a book (or
online equivalent) is probably best.

The question, as stated in your posting, can not be accurately
answered. The exact results depend on the particular CPU and compiler
being used, not only the word size. However, most reasonable CPUs and
compilers behave more or less the same way, so giving a likely answer
is possible.

--
Måns Rullgård
mru@inprovide.com

Paul Pluzhnikov

2005-01-18, 8:55 pm

Rich Teer <rich.teer@rite-group.com> writes:

> On Tue, 18 Jan 2005, puzzlecracker wrote:
>
>
> Frankly, if you get a job based on the answers you get here for interview
> questions, you won't last very long in that job.

Presumably OP has *already* flunked this interview, and is now
looking for info on how to improve himself for the next time (which
is a laudable goal).

While I know the answers the interviewer was likely looking for
(which are: 32-bit a: 8; b: 12; c:12; 64-bit a: 8; b:16; c:16),
I don't know any resources that would help OP arrive at the answers.

One source might be "The C++ Object Model" by Lippman. Others?

Cheers,
--
In order to understand recursion you must first understand recursion.
Remove /-nsp/ for email.

David Schwartz

2005-01-18, 8:55 pm

"Paul Pluzhnikov" <ppluzhnikov-nsp@charter.net> wrote in message
news:m3oefmck1c.fsf@salmon.parasoft.com...

> Presumably OP has *already* flunked this interview, and is now
> looking for info on how to improve himself for the next time (which
> is a laudable goal).
[snip]
> I don't know any resources that would help OP arrive at the answers.

It won't work. This question is cleverly arranged to check for
*experience* with working with 32-bit and 64-bit platforms. You can't read
the answer anywhere really. You could try to learn from a book all the
possible questions of this type, but ultimately it would be easier to just
get the experience that the question is trying to check for in the first
place.

DS

Pascal Bourguignon

2005-01-19, 2:48 am

"puzzlecracker" <ironsel2000@gmail.com> writes:

> Got Confused on the interview with memory alligment questions... PLEASE
> HELP -- How much bytes of memory will structs below take on 32 bit
> machine? What about 64 bit machine? Why is it different? (if it's
> relevent, use standard size of datatypes)

It depends on the compiler used:

> a)
>
> Code:
> struct
> {
> short int a;
> int b;
> };

{
struct { short int a; int b; } s;
printf("size a) = %d\n",CHAR_BIT*sizeof(s));
}

> b)
> Code:
> struct{
> short int a;
> int b;
> int somefunc();
> virtual int func1();
> };

{
struct{ short int a; int b; int somefunc(); virtual int func1(); } s;
printf("size b) = %d\n",CHAR_BIT*sizeof(s));
}

> c) Very Tricky (Hint: it is tricky with virtual function (or should I
> say pointers to vtable...you should know something about vtables in
> last but clever case))
>
> Code:
> struct{
> short int a;
> int b;
> virtual int func_1();
> virtual int func_2();
> :
> :
> virtual int func_n();
> };

{
struct{ short int a; int b; virtual int func_1(); virtual int func_2();
virtual int func_n(); } s;
printf("size c) = %d\n",CHAR_BIT*sizeof(s));
}

--
__Pascal Bourguignon__ http://www.informatimago.com/

This is a signature virus. Add me to your signature and help me to live

Bjørn Augestad

2005-01-19, 7:48 am

Pascal Bourguignon wrote:

> "puzzlecracker" <ironsel2000@gmail.com> writes:
>
>
-------------------^^^^^^
[snip]
[vbcol=seagreen]
> struct { short int a; int b; } s;
> printf("size a) = %d\n",CHAR_BIT*sizeof(s));
--------------------------^^^^^^^^

Shouldn't that be just "sizeof(s)"?
Or in extra pedantic mode:
printf("size a) = %lu\n", (unsigned long)sizeof(s));
(or %zu if supported)

Bjørn

[snip]

puzzlecracker

2005-01-19, 5:53 pm

>printf("size a) = %d\n",CHAR_BIT*sizeof(s));

why do you need a CHAR_BIT? doesn't sizeof returns the number of
bytes?

Måns Rullgård

2005-01-19, 5:53 pm

"puzzlecracker" <ironsel2000@gmail.com> writes:

>
> why do you need a CHAR_BIT? doesn't sizeof returns the number of
> bytes?

sizeof tells the size in units of sizeof(char). Thus, sizeof(char) is
always 1. A char is almost always 1 byte, but there are exceptions.

--
Måns Rullgård
mru@inprovide.com

Villy Kruse

2005-01-19, 5:53 pm

On Wed, 19 Jan 2005 16:25:03 +0100,
Måns Rullgård <mru@inprovide.com> wrote:

> "puzzlecracker" <ironsel2000@gmail.com> writes:
>
>
> sizeof tells the size in units of sizeof(char). Thus, sizeof(char) is
> always 1. A char is almost always 1 byte, but there are exceptions.
>

And a byte is almost always 1 octet, but there may be exceptions. An
octet, however, is always 8 bits.

Villy

Goran Larsson

2005-01-19, 5:53 pm

In article <yw1xmzv5zbjk.fsf@ford.inprovide.com>,
Måns Rullgård <mru@inprovide.com> wrote:

> sizeof tells the size in units of sizeof(char). Thus, sizeof(char) is
> always 1. A char is almost always 1 byte, but there are exceptions.

In C a char is always exactly 1 byte, no exceptions.

--
Göran Larsson http://www.mitt-eget.com/

Lew Pitcher

2005-01-19, 5:53 pm

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Goran Larsson wrote:
> In article <yw1xmzv5zbjk.fsf@ford.inprovide.com>,
> Måns Rullgård <mru@inprovide.com> wrote:
>
>
>
>
> In C a char is always exactly 1 byte, no exceptions.

But, in C, a byte is not necessarily 8 bits long.

CHAR_BITS is the constant that tells you how many bits there are in a byte.

- --

Lew Pitcher, IT Consultant, Enterprise Data Systems
Enterprise Technology Solutions, TD Bank Financial Group

(Opinions expressed here are my own, not my employer's)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (MingW32)

iD8DBQFB7o17agVFX4UWr64RAvkzAJ0Zigx7zHf3
sxWH//uLI9gqZFk3KACgoHDM
SPO96CdccuxerNprtKYPnM8=
=UZHY
-----END PGP SIGNATURE-----

Måns Rullgård

2005-01-19, 5:53 pm

Lew Pitcher <Lew.Pitcher@td.com> writes:

> Goran Larsson wrote:
>
> But, in C, a byte is not necessarily 8 bits long.

What, exactly, is the definition of a byte? Whatever the answer,
sizeof(char) is always 1, but the number of bits is implementation
specific.

> CHAR_BITS is the constant that tells you how many bits there are in a byte.

--
Måns Rullgård
mru@inprovide.com

Lew Pitcher

2005-01-19, 5:53 pm

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Måns Rullgård wrote:
> Lew Pitcher <Lew.Pitcher@td.com> writes:
>
>
>
>
> What, exactly, is the definition of a byte? Whatever the answer,
> sizeof(char) is always 1, but the number of bits is implementation
> specific.

In the C standard, a "byte" is defined as an "addressable unit of data
storage large enough to hold any member of the basic character
set of the execution environment". No maximum width is ascribed to a
"byte", although a minimum width is implied by both the above
definition, and the definition of the constants used in limits.h

[vbcol=seagreen]

CHAR_BIT is explicitly defined by the C standard as the "number of bits
for smallest object that is not a bit-field (byte)". The minimum value
for this constant is 8, implying that a conforming compiler must allow
/at least/ bits to a byte.

In other words, the ISO C standard dictates that
- - a 'byte' can hold 8 bits /or more/.
- - a 'byte' is the unit of storage for a C char entity, and
- - sizeof measures sizes in units of char width.

- --

Lew Pitcher, IT Consultant, Enterprise Data Systems
Enterprise Technology Solutions, TD Bank Financial Group

(Opinions expressed here are my own, not my employer's)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (MingW32)

iD8DBQFB7p5NagVFX4UWr64RAhISAKCcESjYpNsG
ogWGNU2/Qft6BvgWGwCeOnKO
7BkGOqlWy2OI3bg3z0xM5cU=
=5EoS
-----END PGP SIGNATURE-----

Pascal Bourguignon

2005-01-19, 5:53 pm

Bjørn Augestad <boa@metasystems.no> writes:

> Pascal Bourguignon wrote:
>
> -------------------^^^^^^
> [snip]
>
> --------------------------^^^^^^^^
>
> Shouldn't that be just "sizeof(s)"?

Oops, indeed, I don't know why I read 'bit'.

> Or in extra pedantic mode:
> printf("size a) = %lu\n", (unsigned long)sizeof(s));
> (or %zu if supported)
>
> Bjørn

--
__Pascal Bourguignon__ http://www.informatimago.com/

In a World without Walls and Fences,
who needs Windows and Gates?

Lew Pitcher

2005-01-19, 5:53 pm

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Pascal Bourguignon wrote:[vbcol=seagreen]
> Bjørn Augestad <boa@metasystems.no> writes:
>
>

Only if you are willing to accept that a byte is not necessarily 8 bits
long.

[snip]

- --

Lew Pitcher, IT Consultant, Enterprise Data Systems
Enterprise Technology Solutions, TD Bank Financial Group

(Opinions expressed here are my own, not my employer's)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (MingW32)

iD8DBQFB7qv+agVFX4UWr64RAsQLAKDdHdablT1l
LwyuFSqR0hETrxLPSwCgoUtW
gLCWTljSNhLcb50lh2SR3s8=
=zTst
-----END PGP SIGNATURE-----

jjf@bcs.org.uk

2005-01-20, 2:54 am

M=E5ns Rullg=E5rd wrote:
>
> What, exactly, is the definition of a byte?

It depends on the context. In C it is "addressable unit of data
storage large enough to hold any member of the basic character
set of the execution environment" and it has a number of properties:
- it is possible to express the address of each individual byte of
an object uniquely.
- a byte is composed of a contiguous sequence of bits, the number of
which is implementation defined. The least significant bit is called
the low-order bit; the most significant bit is called the high-order
bit.
- the size of a char is one byte.

Roger Leigh

2005-01-20, 5:58 pm

On 2005-01-18, puzzlecracker <ironsel2000@gmail.com> wrote:
> Got Confused on the interview with memory alligment questions... PLEASE
> HELP -- How much bytes of memory will structs below take on 32 bit
> machine? What about 64 bit machine? Why is it different? (if it's
> relevent, use standard size of datatypes)

Which Linux? i386, IA-64, amd64, ARM, MIPS, SPARC32/64, PA-RISC, Alpha??
Each will potentially be different.

> Code:
> struct
> {
> short int a;
> int b;
> };

Assuming 32-bit Intel, "short int" is 16-bits, and "int" is 32 bits. We
would expect int to be aligned on a word boundary (4 bytes), giving this
arrangement:

size running total
-------------------------
a 2 2
[pad] 2 4
b 4 8

To test this, write a simple program which will tell you what really
happens.

#include <stdio.h>
#include <stdint.h>

struct test
{
short int a;
int b;
} /* __attribute__ ((packed)) */;

#define SOFFSET(struct_type, member_name) \
((unsigned long) ((uint8_t *) &((struct_type*)0)->member_name))

int main(void)
{
printf("Member a size: %lu\n", (unsigned long) sizeof(short int));
printf("Member a offset: %lu\n", (unsigned long) SOFFSET(struct test, a));
printf("Member b size: %lu\n", (unsigned long) sizeof(int));
printf("Member b offset: %lu\n", (unsigned long) SOFFSET(struct test, b));
printf("Structure size: %lu\n", (unsigned long) sizeof(struct test));
return 0;
}

Note that compiler options will also affect structure alignment.
Uncomment the "__attribute__ ((packed))" comment, and recompile.
Notice there is now no padding.

For the other questions, repeat as above. Note that (as any
good C++ text will tell you), if the class contains any
virtual functions, each type instance of the object must contain
a pointer to the class structure (virtual call table), i.e.
one extra pointer.

Regards,
Roger

--
Roger Leigh

Printing on GNU/Linux? http://gimp-print.sourceforge.net/
GPG Public Key: 0x25BFB848. Please sign and encrypt your mail.

Grumble

2005-01-20, 5:58 pm

Roger Leigh wrote:

> #define SOFFSET(struct_type, member_name) \
> ((unsigned long) ((uint8_t *) &((struct_type*)0)->member_name))

This might not work. Use offsetof() instead.

http://www.opengroup.org/onlinepubs...s/stddef.h.html

--
Regards, Grumble

Måns Rullgård

2005-01-20, 5:58 pm

Grumble <devnull@kma.eu.org> writes:

> Roger Leigh wrote:
>
>
> This might not work. Use offsetof() instead.

GCC uses something very similar to the macro above.

--
Måns Rullgård
mru@inprovide.com

Roger Leigh

2005-01-20, 5:58 pm

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Grumble <devnull@kma.eu.org> writes:

> Roger Leigh wrote:
>
>
> This might not work. Use offsetof() instead.

I should have done so, but I thought showing how it might be
implemented would be instructive.

Out of interest, what could cause it to fail? By my understanding,
getting the address of any struct member should always work, and even
though it's a cast of NULL, this should be legal providing we don't
dereference it.

Regards,
Roger

- --
Roger Leigh
Printing on GNU/Linux? http://gimp-print.sourceforge.net/
Debian GNU/Linux http://www.debian.org/
GPG Public Key: 0x25BFB848. Please sign and encrypt your mail.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)
Comment: Processed by Mailcrypt 3.5.8 <http://mailcrypt.sourceforge.net/>

iD8DBQFB7/svVcFcaSW/uEgRAvkdAKDxuBr7sdnxSnWeR/gNeChkFz2voACeOD3G
wi2YnKYDoFydI3j0axSSeKU=
=WRst
-----END PGP SIGNATURE-----

Grumble

2005-01-21, 2:51 am

Roger Leigh wrote:

> Grumble wrote:
>
>
> I should have done so, but I thought showing how it might be
> implemented would be instructive.
>
> Out of interest, what could cause it to fail? By my understanding,
> getting the address of any struct member should always work, and even
> though it's a cast of NULL, this should be legal providing we don't
> dereference it.

As far as I understand, you do dereference NULL :-)

&((struct_type*)0)->member_name

is equivalent to

struct_type *p = NULL;
struct_type s = *p;
some_type memb = s.member_name;
return &memb;

Here's what the C police has to say about the matter:
http://www.google.ca/groups? thread...r /> d5@4ax.com
(Click "See this message in context" for the entire sub-thread.)

--
Regards, Grumble

Roger Leigh

2005-01-21, 5:52 pm

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Grumble <devnull@kma.eu.org> writes:

> Roger Leigh wrote:
>
> As far as I understand, you do dereference NULL :-)

<homer>D'oh!</homer>

> Here's what the C police has to say about the matter:
> http://www.google.ca/groups? thread...r /> d5@4ax.com

That was a very interesting read. While it's technically wrong, it
appears an optimising compiler will optimise it to a single address
with no dereference. Checking <stddef.h> for gcc-3.4 on GNU/Linux
shows they use exactly the same macro (with slightly different names
and types), so it looks like I got away with the undefined behaviour
on this plaform.

Thanks!
Roger

- --
Roger Leigh
Printing on GNU/Linux? http://gimp-print.sourceforge.net/
Debian GNU/Linux http://www.debian.org/
GPG Public Key: 0x25BFB848. Please sign and encrypt your mail.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)
Comment: Processed by Mailcrypt 3.5.8 <http://mailcrypt.sourceforge.net/>

iD8DBQFB8Vc/VcFcaSW/uEgRAnJuAKC8lMoVHvl/8zN1MmvGLFWBEv4UxQCbB1yp
LInPymnKoYnZJmEXZfdg/J8=
=XWX8
-----END PGP SIGNATURE-----