Chapter3 part2
3.8 Array Allocation and access
Arrays in C are one means of aggregating scalar data into larger data types. C uses a particularly simple implementation of arrays, and hence the translation into machine code is fairly straightforward. One unusual feature of C is that we can generate pointers to elements within arrays and perform arithmetic with these pointers. These are translated into address computations in machine code.
Optimizing compilers are particularly good at simplifying the address computations used by array indexing. This can make the correspondence between the C code and its translation into machine code somewhat difficult to decipher.
3.8.1 Basic Principles
For datatype T and integer constant N, consider a declaration of the form T a[n]
Let us denote the starting location as xa. The declaration has two effects. First, it allocates a contiguous region of L * N bytes in memory where L is the size of data type T. second, it introduces an identifier A that can be used as a pointer to the beginning of the array. The value of this pointer will be xa. The array elements can be accessed using an integer index ranging between 0 and N-1.
Array element i will be stored at address xa + L * i
pointer has size of 8 bytes
The memory referencing instructions of x86-64 are designed to simplify array access. For example, suppose E is an array of values of type int and we wish to evaluate E[i], where the address of E is stored in register %rdx and i is stored in register %rcx.
Then movl (%rdx, %rcx, 4), %eax
will perform the address computation xe + 4i, read that memory location, and copy the result to register %eax. The allowed scaling factors of 1,2,4,and 8 cover the sizes of the common primitive data types.
3.8.2 Pointer arithmetic
The unary operators '&' and '*' allow the generation and dereferencing of pointers. That is, for an expression Expr denoting some object, &Expr is a pointer giving the address of the object. FOr an expression AExpr denoting an address, *AExpr gives the value at that address. The expressions Expr and *&Expr are equivalent. The array subscripting operation can be applied to both arrays and pointers The array reference A[i] is identical to the expression *(A+i); It computes the address of the ith array element and then accesses this memory location. Expanding on our earlier example, suppose the starting address of integer array E and integer index i are stored in registers %rdx and %rcx, respectively. The following are some expressions involving E. We also show an assembly-code implementation of each expression, with the result being stored in either register %eax or register %rax
image.png
In these examples, we see that operations that return array values have type int, and hence involve 4-byte operations and registers (e.g. %eax). Those that return pointers have type int *, and hence involve 8-byte operations and registers. The final example shows that one can compute the difference of two pointers within the same data structure, with the result being data having type long and value equal to the difference of the two addresses divided by the size of the data type
3.8.3 Nested Arrays
The general principles of array allocation and referencing hold even when we create arrays of arrays. For example, the declaration
int A[5][3];
is equivalent to the declaration
typedef int row3_t [3];
row3_t A[5];
data type row3_t is defined to be an array of three integers. Array A contains five such elements, each requiring 12 bytes to store the three integers. The total array size is then 4 * 5 * 3 = 60 bytes.
The array elements are ordered in memory in row-major order, meaning all elements of row 0, which can be written A[0], followed by all elements of row 1 (A[1]), and. so on. This is illustrated in Figure 3.36.
figure 3.36
This ordering is a consequence of our nested declaration. Viewing A as an array of five elements, each of which is an array of three int's, we first have A[0], followed by A[1], and so on.
To access elements of multidimensional arrays, the compiler generates code to compute the offset of the desired element and then uses one of the MOV instructions with the start of the array as the base address
Fixed size arrays
Figure 3.37b contains a number of clever optimizations. It removes the integer index j and converts all array references to pointer derederences. this involves
- generating a pointer, which we have named Aptr, that points to successive elements in row i of A
- generating a pointer, which we have named Bptr, that points to successive elements in column k of B
-
Generating a pointer, which we have named Bend, that equals the value Bptr will have when it is time to terminate the loop. The initial value for Aptr is the address of the first element of row i of A, given by the C expression &A[i][0]. The initial value for Bptr is the address of the first element of column k of B, given by the C expression &B[0][k]. The value for Bend is the index of what would be the (n+1)st element in column j of B, given by the C expression &B[N][k].
figure3.37
Variable-size arrays
Historically, C only supported multidimensional arrays where the sizes (with the possible exception of the first dimension) could be determined at compile time.
Programmers requiring variable-size arrays had to allocate storage for these arrays using functions such as malloc or calloc, and they had to explicitly encode the mapping of multidimensional arrays into single-dimensino ones via row-major indexing, as expressed in Equation 3.1
C99 introduced the capability of having array dimension expressions that are computed as the array is being allocated.
In the C version of variable-size arrays, we can declare an array int A[expr1][expr2]
either as a local variable or as an argument to a function, and then the dimensions of the array are determined by evaluating the expressions expr1 and expr2 at the time the declaration is encountered. So, for example, we can write a function to access element i, j of an n x n array as follows:
int var_ele(long n, int A[n][n], long i, long j) {
return A[i][j];
}
The parameter n must precede the parameter A[n][n], so that the function can compute the array dimensions as the parameter is encountered.
Gcc generates code for this referencing function as
var_ele:
imulq %rdx, %rdi
leaq (%rsi, %rdi, 4), %rax
movl (%rax, %rcx, 4), %eax
ret
As the annotations show, this code computes the address of element i, j as xa + 4(n*i) + 4j
When variable-size arrays are referenced within a loop, the compiler can often opimize the index computations by exploiting the regularity of the access patterns. For example, Figure 3.38(a) shows C code to compute element i, k of the product of two n x n arrays A and B. Gcc generates assembly code, which we have recast into C figure 3.38b. This code follows a different style from the optimized code for the fixed-size array, but that is more an artifact of the choices made by the compiler, rather than a fundamental requirement for the two different functions. The code of Figure 3.38 retains loop variable j, both to detect when the loop has terminated and to index into an array consisting of the elements of row i of A.
The following is the assembly code for the loop of var_prod_ele:
figure3.38
3.9 Heterogeneous data structures
struct aggregate multiple objects into a single unit; unions, declared using the keyword union, allow an object to be referenced using several different types.
3.9.1 Structures
The C struct declaration creates a data type that groups objects of possibly different types into a single object. The different components of a structure are referenced by names. The implementation of structures is similar to that of arrays in that all of the components of a structure are stored in a contiguous region of memory and a pointer to a structure is the address of its first byte. The compiler maintains information about each structure type indicating the byte offset of each field. It generates references to structure elements using these offset of each field. It generates references to structure elements using these offsets as displacements in memory referencing instructions.
3.9.2 unions
Unions provide a way to circumvent the type system of C, allowing a single object to be referenced according to multiple types. The syntax of a union declaration is identical to that for structures, but its semantics are very different. Rather than having the different fields reference different blocks of memory, they all reference the same block.
Consider the following declarations:
struct S3 {
char c;
int i[2];
double v;
}
union U3 {
char c;
int i[2];
double v;
}
image.png
Data alignment
Restrictions on data in order to have a good memory performance
Buffer Overflow
Most common security issue is from buffer overflow
attacker can insert code they want to execute by buffer overflow
image.png
Internet worm (1988)
IM war(1999)
image.png
image.png
image.png
Worm run on itself, propagate itself to other computers
Virus add itself to other programs but does not run independently
How to mitigate buffer overflow?
- Avoid overflow vulnerabilities in code (use fgets instead of gets)
- Randomized stack offsets (ASLR)
- Avoid file to be executable
- Canaries (place special value on stack just beyond buffer
Summary
We have get a view of machine-level programming. We gain insights into both the compiler and its optimization capabilities, along with the machine, its data types, and its instruction set.
We also gotten mote complete picture of how the program stores data in different memory regions.
Machine level code is expressed as a sequence of instructions, each of which performs a single operation. Parts of the program state, such as registers and the run-time stack, are directly visible to the programmer.
