Carnegie Mellon 1 Machine(Level,Programming,V:,Advanced,Topics,15#213:'Introduc0on'to'Computer'Systems'8th'Lecture,'Sep.'16,'2010'Instructors:''Randy'Bryant'&'Dave'O’Hallaron'Carnegie Mellon 2 Today, Structures, Alignment' Unions, Memory,Layout, Buffer,Overflow, Vulnerability' Protec0on'Carnegie Mellon 3 Structures,&,Alignment, Unaligned,Data, Aligned,Data, Primi0ve'data'type'requires'K'bytes' Address'must'be'mul0ple'of'K'c i[0] i[1] v 3,bytes, 4,bytes,p+0 p+4 p+8 p+16 p+24 MulIple,of,4, MulIple,of,8,MulIple,of,8, MulIple,of,8,c i[0] i[1] v p p+1 p+5 p+9 p+17 struct S1 { char c; int i[2]; double v; } *p;Carnegie Mellon 4 Alignment,Principles, Aligned,Data, Primi0ve'data'type'requires'K'bytes' Address'must'be'mul0ple'of'K' Required'on'some'machines;'advised'on'IA32' treated'differently'by'IA32'Linux,'x86#64'Linux,'and'Windows!' MoIvaIon,for,Aligning,Data, Memory'accessed'by'(aligned)'chunks'of'4'or'8'bytes'(system'dependent)' Inefficient'to'load'or'store'datum'that'spans'quad'word'boundaries' Virtual'memory'very'tricky'when'datum'spans'2'pages' Compiler, Inserts'gaps'in'structure'to'ensure'correct'alignment'of'fields'Carnegie Mellon 5 Specific,Cases,of,Alignment,(IA32), 1,byte:,char,,…, no'restric0ons'on'address' 2,bytes:,short,,…, lowest'1'bit'of'address'must'be'02' 4,bytes:,int,,float,,char *,,…, lowest'2'bits'of'address'must'be'002' 8,bytes:,double,,…, Windows'(and'most'other'OS’s'&'instruc0on'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'primi0ve'data'type' 12,bytes:,long double, Windows,'Linux:' lowest'2'bits'of'address'must'be'002' i.e.,'treated'the'same'as'a'4#byte'primi0ve'data'type'Carnegie Mellon 6 Specific,Cases,of,Alignment,(x86(64), 1,byte:,char,,…, no'restric0ons'on'address' 2,bytes:,short,,…, lowest'1'bit'of'address'must'be'02' 4,bytes:,int,,float,,…, lowest'2'bits'of'address'must'be'002' 8,bytes:,double,,char *,,…, Windows'&'Linux :' lowest'3'bits'of'address'must'be'0002' 16,bytes:,long double, Linux:' lowest'3'bits'of'address'must'be'0002' i.e.,'treated'the'same'as'a'8#byte'primi0ve'data'type'Carnegie Mellon 7 struct S1 { char c; int i[2]; double v; } *p; SaIsfying,Alignment,with,Structures, Within,structure:, Must'sa0sfy'each'element’s'alignment'requirement' Overall,structure,placement, Each'structure'has'alignment'requirement'K' K'='Largest'alignment'of'any'element' Ini0al'address'&'structure'length'must'be'mul0ples'of'K' Example,(under,Windows,or,x86(64):, K'='8,'due'to'double'element'c i[0] i[1] v 3,bytes, 4,bytes,p+0 p+4 p+8 p+16 p+24 MulIple,of,4, MulIple,of,8,MulIple,of,8, MulIple,of,8,Carnegie Mellon 8 Different,Alignment,ConvenIons, x86(64,or,IA32,Windows:, K'='8,'due'to'double'element' IA32,Linux, K'='4;'double'treated'like'a'4#byte'data'type'struct S1 { char c; int i[2]; double v; } *p; c 3,bytes,i[0] i[1] 4,bytes,v p+0 p+4 p+8 p+16 p+24 c 3,bytes,i[0] i[1] v p+0 p+4 p+8 p+12 p+20Carnegie Mellon 9 MeeIng,Overall,Alignment,Requirement, For,largest,alignment,requirement,K, Overall,structure,must,be,mulIple,of,K,struct S2 { double v; int i[2]; char c; } *p; v i[0] i[1] c 7'bytes'p+0 p+8 p+16 p+24Carnegie Mellon 10 Arrays,of,Structures, Overall,structure,length,mulIple,of,K, SaIsfy,alignment,requirement,,for,every,element,struct S2 { double v; int i[2]; char c; } a[10]; v i[0] i[1] c 7'bytes'a+24 a+32 a+40 a+48 a[0] a[1] a[2] • • • a+0! a+24! a+48! a+72!Carnegie Mellon 11 Accessing,Array,Elements, Compute,array,offset,12i, sizeof(S3),'including'alignment'spacers' Element,j,is,at,offset,8,within,structure, Assembler,gives,offset,a+8, Resolved'during'linking'struct S3 { short i; float v; short j; } a[10]; short get_j(int idx) { return a[idx].j; } # %eax = idx leal (%eax,%eax,2),%eax # 3*idx movswl a+8(,%eax,4),%eax a[0] • • • a[i] • • • a+0 a+12 a+12i i 2'bytes'v j 2'bytes'a+12i a+12i+8Carnegie Mellon 12 Saving,Space, Put,large,data,types,first, Effect,(K=4),struct S4 { char c; int i; char d; } *p; struct S5 { int i; char c; char d; } *p; c i 3,bytes,d 3,bytes,c i d 2,bytes,Carnegie Mellon 13 Today, Structures, Alignment' Unions, Memory,Layout, Buffer,Overflow, Vulnerability' Protec0on'Carnegie Mellon 14 Union,AllocaIon, Allocate,according,to,largest,element, Can,only,use,one,field,at,a,Ime,union U1 { char c; int i[2]; double v; } *up; struct S1 { char c; int i[2]; double v; } *sp; c 3'bytes'i[0] i[1] 4'bytes'v sp+0 sp+4 sp+8 sp+16 sp+24 c i[0] i[1] v up+0 up+4 up+8Carnegie Mellon 15 typedef union { float f; unsigned u; } bit_float_t; float bit2float(unsigned u) { bit_float_t arg; arg.u = u; return arg.f; } unsigned float2bit(float f) { bit_float_t arg; arg.f = f; return arg.u; } Using,Union,to,Access,Bit,Pa]erns,Same,as,(float) u,?,, Same,as,(unsigned) f,?,,u f 0 4Carnegie Mellon 16 Byte,Ordering,Revisited, Idea, Short/long/quad'words'stored'in'memory'as'2/4/8'consecu0ve'bytes' Which'is'most'(least)'significant?' Can'cause'problems'when'exchanging'binary'data'between'machines' Big,Endian, Most'significant'byte'has'lowest'address' Sparc' Li]le,Endian, Least'significant'byte'has'lowest'address' Intel'x86'Carnegie Mellon 17 Byte,Ordering,Example, union { unsigned char c[8]; unsigned short s[4]; unsigned int i[2]; unsigned long l[1]; } dw; c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] s[0] s[1] s[2] s[3] i[0] i[1] l[0] 32(bit,c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] s[0] s[1] s[2] s[3] i[0] i[1] l[0] 64(bit,Carnegie Mellon 18 Byte,Ordering,Example,(Cont).,int j; for (j = 0; j < 8; j++) dw.c[j] = 0xf0 + j; printf("Characters 0-7 == [0x%x,0x%x,0x%x,0x%x,0x%x,0x%x,0x%x,0x%x]\n", dw.c[0], dw.c[1], dw.c[2], dw.c[3], dw.c[4], dw.c[5], dw.c[6], dw.c[7]); printf("Shorts 0-3 == [0x%x,0x%x,0x%x,0x%x]\n",
View Full Document