Structured Data IIHeterogenous DataSept. 26, 2000Topics• Structure Allocation• Alignment• Unions• Byte Ordering• Byte Operations• IA32/Linux Memory Organization• Understanding C declarationsclass09.ppt15-213“The course that gives CMU its Zip!”CS 213 F’00– 2 –class09.pptBasic Data TypesIntegral• Stored & operated on in general registers• Signed vs. unsigned depends on instructions usedIntel GAS Bytes Cbyte b 1 [unsigned] charword w 2 [unsigned] shortdouble word l 4 [unsigned] int, char *quad word 8Floating Point• Stored & operated on in floating point registersIntel GAS Bytes CSingle s 4 floatDouble l 8 doubleExtended t 10/12 long doubleCS 213 F’00– 3 –class09.pptstruct rec { int i; int a[3]; int *p;};Assembly# %eax = val# %edx = rmovl %eax,(%edx) # Mem[r] = valvoidset_i(struct rec *r, int val){ r->i = val;}StructuresConcept• Contiguously-allocated region of memory• Refer to members within structure by names• Members may be of different typesAccessing Structure MemberMemory Layouti a p0 4 1620CS 213 F’00– 4 –class09.pptstruct rec { int i; int a[3]; int *p;};# %ecx = idx# %edx = rleal 0(,%ecx,4),%eax # 4*idxleal 4(%eax,%edx),%eax # r+4*idx+4int *find_a (struct rec *r, int idx){ return &r->a[idx];}Generating Pointer to Structure MemberGenerating Pointer toArray Element• Offset of each structuremember determined atcompile timei a p0 4 16r + 4 + 4*idxrCS 213 F’00– 5 –class09.pptstruct rec { int i; int a[3]; int *p;}; # %edx = rmovl (%edx),%ecx # r->ileal 0(,%ecx,4),%eax # 4*(r->i)leal 4(%edx,%eax),%eax # r+4+4*(r->i)movl %eax,16(%edx) # Update r->pvoidset_p(struct rec *r){ r->p = &r->a[r->i];}Structure Referencing (Cont.)C Codei a0 4 16Element ii a p0 4 16CS 213 F’00– 6 –class09.pptAlignmentAligned Data• Primitive data type requires K bytes• Address must be multiple of K• Required on some machines; advised on IA32–treated differently by Linux and Windows!Motivation for Aligning Data• Memory accessed by (aligned) double or quad-words–Inefficient to load or store datum that spans quad word boundaries–Virtual memory very tricky when datum spans 2 pagesCompiler• Inserts gaps in structure to ensure correct alignment of fieldsCS 213 F’00– 7 –class09.pptSpecific Cases of AlignmentSize of Primitive Data Type:•1 byte (e.g., char)–no restrictions on address•2 bytes (e.g., short)–lowest 1 bit of address must be 02•4 bytes (e.g., int, float, char *, etc.)–lowest 2 bits of address must be 002•8 bytes (e.g., double)–Windows (and most other OS’s & instruction sets):»lowest 3 bits of address must be 0002–Linux:»lowest 2 bits of address must be 002»i.e. treated the same as a 4 byte primitive data type•12 bytes (long double)–Linux:»lowest 2 bits of address must be 002»i.e. treated the same as a 4 byte primitive data typeCS 213 F’00– 8 –class09.pptstruct S1 { char c; int i[2]; double v;} *p;Satisfying Alignment with StructuresOffsets Within Structure• Must satisfy element’s alignment requirementOverall Structure Placement• Each structure has alignment requirement K–Largest alignment of any element• Initial address & structure length must bemultiples of KExample (under Windows):• K = 8, due to double elementc i[0] i[1] vp+0 p+4 p+8 p+16 p+24Multiple of 4 Multiple of 8Multiple of 8 Multiple of 8CS 213 F’00– 9 –class09.pptLinux vs. WindowsWindows (including Cygwin):• K = 8, due to double elementLinux:• K = 4; double treated like a 4-byte data typestruct S1 { char c; int i[2]; double v;} *p;c i[0] i[1] vp+0 p+4 p+8 p+16 p+24Multiple of 4 Multiple of 8Multiple of 8Multiple of 8c i[0] i[1]p+0 p+4 p+8Multiple of 4 Multiple of 4Multiple of 4vp+12 p+20Multiple of 4CS 213 F’00– 10 –class09.pptEffect of Overall Alignment Requirementci[0] i[1]xp+0 p+12p+8 p+16 Windows: p+24Linux: p+20struct S2 { double x; int i[2]; char c;} *p;struct S3 { float x[2]; int i[2]; char c;} *p;ci[0] i[1]p+0 p+12p+8 p+16 p+20x[0] x[1]p+4p must be multiple of: 8 for Windows4 for Linuxp must be multiple of 4 (in either OS)CS 213 F’00– 11 –class09.pptOrdering Elements Within Structurestruct S4 { char c1; double v; char c2; int i;} *p;struct S5 { double v; char c1; char c2; int i;} *p;c1 ivp+0 p+20p+8 p+16 p+24c2c1 ivp+0 p+12p+8 p+16c210 bytes wasted space in Windows2 bytes wasted spaceCS 213 F’00– 12 –class09.pptArrays of StructuresPrinciple• Allocated by repeating allocation forarray type• In general, may nest arrays & structuresto arbitrary deptha[0]a+0a[1] a[2]a+12 a+24 a+36• • •a+12 a+20a+16 a+24struct S6 { short i; float v; short j;} a[10];a[1].i a[1].ja[1].vCS 213 F’00– 13 –class09.pptAccessing Element within Array• Compute offset to start of structure– Compute 12*i as 4*(i+2i)• Access element according to its offset withinstructure– Offset by 8– Assembler gives displacement as a + 8» Linker must set actual valuea[0]a+0a[i]a+12i• • • • • •short get_j(int idx){ return a[idx].j;}# %eax = idxleal (%eax,%eax,2),%eax # 3*idxmovswl a+8(,%eax,4),%eaxa+12i a+12i+8struct S6 { short i; float v; short j;} a[10];a[i].i a[i].ja[i].vCS 213 F’00– 14 –class09.pptSatisfying Alignment within StructureAchieving Alignment• Starting address of structure array must bemultiple of worst-case alignment for any element– a must be multiple of 4• Offset of element within structure must be multipleof element’s alignment requirement– v’s offset of 4 is a multiple of 4• Overall size of structure must be multiple of worst-case alignment for any element–Structure padded with unused space to be 12 bytesstruct S6 { short i; float v; short j;} a[10];a[0]a+0a[i]a+12i• • • • • •a+12i a+12i+4a[1].i a[1].ja[1].vMultiple of 4Multiple of 4CS 213 F’00– 15 –class09.pptUnion AllocationPrinciples• Overlay union elements• Allocate according to largest element• Can only use one field at a timeunion U1 { char c; int i[2]; double v;} *up;ci[0] i[1]vup+0 up+4 up+8struct S1 { char c; int i[2]; double v;} *sp;c i[0] i[1] vsp+0 sp+4 sp+8 sp+16 sp+24(Windows alignment)CS 213 F’00– 16 –class09.pptImplementing “Tagged” Union• Structure can hold 3kinds of data• Only one form at anygiven time• Identify particular kindwith flag typetypedef enum { CHAR, INT, DBL } utype;typedef struct { utype type; union { char c; int i[2]; double v; } e;} store_ele, *store_ptr;store_ele
View Full Document
Unlocking...