参考资料

信息的表示和处理

大小端的思考

下面的代码表示大小端的区别，这段代码通过转字符串的方式，强制将数字类型转换为字符类型，显示了其数字在该小端法机器中的存储顺序。

#include <stdio.h>

typedef unsigned char * byte_pointer;

void show_bytes(byte_pointer start, size_t len)
{
    size_t i;
    for (i = 0; i < len; i++)
    {
        printf("%.2x ", start[i]);  //表示整数必须用至少两个数字的十六进制格式输出
    }
    printf("\n");
}

void show_int(int x)
{
    show_bytes((byte_pointer)&x, sizeof(int));
}

void show_float(float x)
{
    show_bytes((byte_pointer)&x, sizeof(float));
}

void show_pointer(void *x)
{
    show_bytes((byte_pointer)&x, sizeof(void *));
}

void test_show_bytes(int val)
{
    int ival = val;  //int的12345
    float fval = (float)ival; //float的12345
    int *pval = &ival;  //int的12345的地址
    show_int(ival);   
    show_float(fval);
    show_pointer(pval);
}

int main()
{
    test_show_bytes(12345);
    return 0;
}

//结果
39 30 00 00
00 e4 40 46
d4 fd 61 00 00 00 00 00

思考一下，现在的机器大多数比较统一，基本采用的都是小端法，但是也存在大端法的显示，在不同机器上运行的时候需要考虑。

Swap

  • 下面这个交换函数是没有性能优化的，但是省去了中间变量，是怎么做到的？
void inpalce_swap(int *x, int *y)
{
    *y = *x ^ *y;
    *x = *x ^ *y;
    *y = *x ^ *y;
}
  • 我专门测了一下时间，确实没有优化，但还是挺神奇的。
#include <stdio.h>
#include <time.h>

void inpalce_swap(int *x, int *y)
{
    *y = *x ^ *y;
    *x = *x ^ *y;
    *y = *x ^ *y;
}

void swap(int *x, int *y)
{
    int mid = 0;
    mid = *x;
    *x = *y;
    *y = mid;
}

clock_t start1, stop1;
clock_t start2, stop2;
double duration1;
double duration2;
int main()
{

    int a = 3, b = 4;
    int c = 8, d = 9;
    long long n = 1000000001;
    printf("%d,%d |", a, b);
    printf("%d,%d\n", c, d);
    start1 = clock();
    for (int i = 0; i < n; i++)
    {
        inpalce_swap(&a, &b);
    }
    stop1 = clock();
    duration1 = ((double)(stop1 - start1)) / CLK_TCK;
    printf("%d,%d\n", a, b);
    printf("%f\n", duration1);

    start2 = clock();
    for (int i = 0; i < n; i++)
    {
        swap(&c, &d);
    }
    stop2 = clock();
    duration2 = ((double)(stop2 - start2)) / CLK_TCK;
    printf("%d,%d\n", c, d);
    printf("%f\n", duration2);   
    return 0;
}

//结果，可见没有显著的差别
3,4 |8,9
4,3
0.280000
9,8
0.274000

移位运算

#include <bitset>
#include <iostream>
using namespace std;

int main()
{
    unsigned short a = 0b0001;
    bitset<16> b1(a);
    cout << b1 << " " << a << endl;
    unsigned short b = a << 2;
    bitset<16> b2(b);
    cout << b2 << " " << b << endl;

    // C中的基本运算的优先级大于移位运算，则有：
    unsigned short sum = a << 1 + b << 1 ;
    //原本的结果为10，但会表示为(a << (1 + b)) << 1,这是c的编译规则定的
    bitset<16> b3(sum);
    cout << b3 << " " << sum << endl;
    return 0;
}

//输出结果为：
0000000000000001 1
0000000000000100 4
0000000001000000 64

整形

#include <bitset>
#include <iostream>
using namespace std;

int main()
{
    int64_t a = 9223372036854775807;  //等于long long 
    uint64_t b = 18446744073709551615; //等于 usigned long long 
    cout << sizeof(int64_t) << " " << sizeof(long long) << " " << a << endl;
    cout << sizeof(uint64_t) << " " << b;
    return 0;
}

//结果，多1就为负，没想到可以存这么多
8 8 9223372036854775807
8 18446744073709551615

浮点数部分

这部分计组有所涉猎，暂时不详读。

程序的机器级表示

汇编和机器码

对于如下代码

#include<stdio.h>

long mult2(long,long);

void mulstore(long x,long y, long *dest){
        long t = mult2(x,y);
        *dest =t;
}

int main(){

return 0;
}

可以用

$ gcc -Og -S mstore.c

生成，汇编代码如下mstore.s 文件

#mstore.s 文件

.file   "mstore.c"
        .text
        .globl  mulstore
        .type   mulstore, @function
mulstore:
        .LFB23:
                .cfi_startproc
                pushq   %rbx   
                .cfi_def_cfa_offset 16
                .cfi_offset 3, -16
                movq    %rdx, %rbx
                call    mult2@PLT
                movq    %rax, (%rbx)
                popq    %rbx
                .cfi_def_cfa_offset 8
                ret
                .cfi_endproc
        .LFE23:
                .size   mulstore, .-mulstore
                .globl  main
                .type   main, @function
main:
        .LFB24:
                .cfi_startproc
                movl    $0, %eax
                ret
                .cfi_endproc
        .LFE24:
                .size   main, .-main
                .ident  "GCC: (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0"
                .section        .note.GNU-stack,"",@progbits

可以用，以点开头的指令通常为伪指令，指导汇编器和链接器工作

gcc -Og -c mstore.s

生成对应的二进制机器码，是不可读的乱码

Linux中的反汇编器为，可以将二进制的机器码反汇编为汇编代码

$ objdump -d mstore.o  #以下显示为反汇编后的结果，右侧为汇编代码

mstore.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <mulstore>:
   0:	53                   	push   %rbx  
   1:	48 89 d3             	mov    %rdx,%rbx
   4:	e8 00 00 00 00       	callq  9 <mulstore+0x9>
   9:	48 89 03             	mov    %rax,(%rbx)
   c:	5b                   	pop    %rbx
   d:	c3                   	retq   

000000000000000e <main>:
   e:	b8 00 00 00 00       	mov    $0x0,%eax
  13:	c3                   	retq

可以看到上面的代码与之前有所不同，在于命令后面的q被省去了，有的添加了q，q表示大小指示符，是可以省略的。

使用

$ gcc -Og -S -masm=intel mstore.c

则可以显示Intel代码，省略了一些不必要的标识符

        .file   "mstore.c"
        .intel_syntax noprefix
        .text
        .globl  mulstore
        .type   mulstore, @function
mulstore:
        .LFB23:
                .cfi_startproc
                push    rbx        #入栈
                .cfi_def_cfa_offset 16
                .cfi_offset 3, -16
                mov     rbx, rdx
                call    mult2@PLT
                mov     QWORD PTR [rbx], rax
                pop     rbx       #出栈
                .cfi_def_cfa_offset 8
                ret
                .cfi_endproc
        .LFE23:
                .size   mulstore, .-mulstore
                .globl  main
                .type   main, @function
main:
        .LFB24:
                .cfi_startproc
                mov     eax, 0
                ret
                .cfi_endproc
        .LFE24:
                .size   main, .-main
                .ident  "GCC: (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0"
                .section        .note.GNU-stack,"",@progbits

循环操作

最近在学汇编的循环，顺便实验一下在gcc下生成的汇编代码

#include<stdio.h>

int main(){
        int a =0;
        while (a<10){
                a++;
        }
        printf("%d",a);
        return 0;
}

汇编代码如下

        .file   "mstore.c"
        .intel_syntax noprefix
        .text
        .section        .rodata.str1.1,"aMS",@progbits,1
.LC0:
        .string "%d"
        .text
        .globl  main
        .type   main, @function
main:
        .LFB23:
                .cfi_startproc
                sub     rsp, 8
                .cfi_def_cfa_offset 16
                mov     edx, 0
                jmp     .L2           #跳到转判断
        .L3:
                add     edx, 1        #循环体内语句
        .L2:
                cmp     edx, 9        #判断
                jle     .L3           #跳转回循环体
                lea     rsi, .LC0[rip]
                mov     edi, 1
                mov     eax, 0
                call    __printf_chk@PLT
                mov     eax, 0
                add     rsp, 8
                .cfi_def_cfa_offset 8
                ret
                .cfi_endproc
        .LFE23:
                .size   main, .-main
                .ident  "GCC: (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0"
                .section        .note.GNU-stack,"",@progbits

移位操作

long shift_left_rightn(long x,long n)
{
        x<<=4;
        x>>=n;
        return x;
}
int main(){

        return 0;
}

这里没有使用intel用的是asm

        .file   "mstore.c"
        .text
        .globl  shift_left_rightn
        .type   shift_left_rightn, @function
shift_left_rightn:
        .LFB23:
                .cfi_startproc
                movq    %rdi, %rax
                salq    $4, %rax    #这里是移位的语句
                movl    %esi, %ecx
                sarq    %cl, %rax   #这里是移位的语句
                ret
                .cfi_endproc
        .LFE23:
                .size   shift_left_rightn, .-shift_left_rightn
                .globl  main
                .type   main, @function
main:
        .LFB24:
                .cfi_startproc
                movl    $0, %eax
                ret
                .cfi_endproc
        .LFE24:
                .size   main, .-main
                .ident  "GCC: (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0"
                .section        .note.GNU-stack,"",@progbits

GDB使用

$ gdb [文件名]

理解指针

#include<stdio.h>

long shift_left_rightn(long x,long n)
{
        int *a = &x;
        *a = 1;
        return x;
}

int main(){

        return 0;
}

汇编代码如下,看了很多汇编的代码之后，就可以看出一个函数都有LFB和LFE两个块，所有的注释都会被省略。

        .intel_syntax noprefix
        .text
        .globl  shift_left_rightn
        .type   shift_left_rightn, @function
shift_left_rightn:
        .LFB23:
                .cfi_startproc
                mov     QWORD PTR -8[rsp], rdi
                mov     DWORD PTR -8[rsp], 1
                mov     rax, QWORD PTR -8[rsp]
                ret
                .cfi_endproc
        .LFE23:
                .size   shift_left_rightn, .-shift_left_rightn
                .globl  main
                .type   main, @function
main:
        .LFB24:
                .cfi_startproc
                mov     eax, 0
                ret
                .cfi_endproc
        .LFE24:
                .size   main, .-main
                .ident  "GCC: (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0"
                .section        .note.GNU-stack,"",@progbits

汇编语法部分

这部分暂时不看，因为学校的80x86ams的汇编还没有学完，学完后再看理解更深。

函数指针

函数指针定义的时候要使得其外部的函数的参数和返回类型均一致，如下：

#include<stdio.h>

long add(long x,long n)
{
        x = x+n;
        return x;
}

int main(){
        int a = 1,b=1;
        long (*f)(long x,long n) = add; //一个函数指针，初始化为add函数
        a = (*f)(a,b);
        printf("%d",a);
        return 0;
}

有高人指点将上述代码改为, 也可运行

#include <stdio.h>

long add(int x, int n)
{
        return x + n;
}
int main()
{
        printf("Hello World\n");
        // void * test_add = add;
        // long value = ((long (*)(int x, int y))(test_add))(0x41, 0x42);
        typedef long function_t(int, int);
        function_t(*test_add) = add;
        long value = test_add(0x41, 0x42);  //这里用十六进制表示传入的参数
        printf("0x%lx\n", value);
        return 0;
}

内存越界引用和缓冲区溢出

这里要先了解一下函数调用栈

参考：https://z.itpub.net/article/detail/50503CAA1CDDA808A925D5758BD1B0A4

下面是一个缓冲区越界的例子，通常c中的很多库函数并没有指定缓冲区的大小，就会存在缓冲区buff(就是中间变量)越界的情况，导致栈空间的其他数据被破坏。

#include <stdio.h>

//库函数gets的实现
char * gets(char *s)
{
        int c;
        char  *dest = s;
        while((c = getchar()) != '\n'  && c != EOF)
        {
                *dest++ = c;
        }
        if(c == EOF && dest  == s )
        {
                return NULL;
        }
        *dest++ = '\0';
        return s;
}

void echo()
{
        char buf[8];
        gets(buf);
        puts(buf);
}

int main()
{
        echo();
        return 0;
}

echo:  ;echo函数
.LFB24:
        .cfi_startproc
        pushq   %rbx
        .cfi_def_cfa_offset 16
        .cfi_offset 3, -16
        subq    $16, %rsp
        .cfi_def_cfa_offset 32
        movq    %fs:40, %rax
        movq    %rax, 8(%rsp)
        xorl    %eax, %eax
        movq    %rsp, %rbx
        movq    %rbx, %rdi
        call    gets
        movq    %rbx, %rdi
        call    puts@PLT
        movq    8(%rsp), %rax
        xorq    %fs:40, %rax
        jne     .L11
        addq    $16, %rsp
        .cfi_remember_state
        .cfi_def_cfa_offset 16
        popq    %rbx
        .cfi_def_cfa_offset 8
        ret
.L11:
        .cfi_restore_state
        call    __stack_chk_fail@PLT
        .cfi_endproc
.LFE24:
        .size   echo, .-echo
        .globl  main
        .type   main, @function

更常见的是使用fgets函数,指定了输出的边界，不会导致越界

#define N 101
char str[N];
FILE *fp = fopen("D:\\demo.txt", "r");
fgets(str, N, fp);
//表示从 D:\\demo.txt 中读取 100 个字符，并保存到字符数组 str 中。

但是类似gets的函数有很多，在实际使用中要小心。这里和攻击代码有关，著名的蠕虫病毒就是其中的一个例子，通过缓冲区溢出来返回执行自己的攻击代码，在将其复制传播。

对抗缓冲区溢出攻击

栈随机化

  • 攻击者既要插入代码，也要插入指向这段代码的指针，指针也是攻击字符串的一部分。产生这个指针需要知道这个字符串放置的栈地址。

  • 栈地址过去很容易预测，不同机器之间栈位置是相当固定的，容易导致攻击者可以攻击许多机器。

  • 栈随机化的目的就是使得栈的位置在程序每次运行时都有变化。

  • 实现方式：

    1. 程序开始时分配一段0~n字节之间的随机大小的空间，(使用分配函数alloca在栈上分配指定字节数量的空间)
    2. 程序不会使用这段空间，但是它会导致程序每次执行时后续的栈位置发生变化。
    3. 分配的范围必须足够大，才能获得足够多的栈地址变化，但是又需要小不至于浪费空间。

  • 具体表现在Linux中，就是变量的地址在多次执行后会在一个范围内不断变化，这类技术叫做地址空间布局随机化ASLR。

    //mstore.c
    #include<stdio.h>
    int main()
    {
            long local;
            printf("local at %p\n",&local);
            return 0;
    }

    touch 一个文件 + 一个参数即可，chmod +x 为可执行文件

    #!/bin/bash
    echo "---------start shell---"

    for((i =1;i <= $1; i++))
    do
      ./a.out $item
    done

  • 栈随机化能增加黑客攻击的难度，但是黑客依然可以通过no op操作来滑过从而找到实际的程序的起始地址。

栈破坏检测

  • 当函数超越局部缓冲区边界时，就说明栈已经被破坏。在c没有可靠的方法组织对数组边界写。但是我们能够在发生越界写的时候，检测到
  • gcc加入了栈保护机制
  • 思想
    1. 在栈帧的中任何局部缓冲区与栈状态之间存储一个特殊的随机的金丝雀值，也称为哨兵值。
    2. 如果该值改变了，说明程序被破坏，异常终止
  • 现在的做法通常将金丝雀的值放到一个只读的空间中，这样就可以在程序结束后做对比。

限制可执行代码区域

  • 栈可以标记可读和可写
  • 但是会带来性能损失
  • AMD使用了NX位，来标记执不执行

处理器体系结构

最近在学计组，这部分就暂时不看了

进程控制块PCB

这是我在Linux0.01的源码中，找到的与进程控制块相关的数据结构，PCB通常指的就是这样数据结构的数据

struct task_struct {
/* these are hardcoded - don't touch */
	long state;	/* -1 unrunnable, 0 runnable, >0 stopped */
	long counter;
	long priority;
	long signal;
	fn_ptr sig_restorer;
	fn_ptr sig_fn[32];
/* various fields */
	int exit_code;
	unsigned long end_code,end_data,brk,start_stack;
	long pid,father,pgrp,session,leader;
	unsigned short uid,euid,suid;
	unsigned short gid,egid,sgid;
	long alarm;
	long utime,stime,cutime,cstime,start_time;
	unsigned short used_math;
/* file system info */
	int tty;		/* -1 if no tty, so it must be signed */
	unsigned short umask;
	struct m_inode * pwd;
	struct m_inode * root;
	unsigned long close_on_exec;
	struct file * filp[NR_OPEN];
/* ldt for this task 0 - zero 1 - cs 2 - ds&ss */
	struct desc_struct ldt[3];
/* tss for this task */
	struct tss_struct tss;
};

优化程序性能

如何编写高效程序

  1. 选择一组适当的算法和数据结构
  2. 编写编译器能够有效优化，从而转化成高效可执行代码的源代码
  3. 针对处理运算量特别大的计算，将一个任务分成多个任务
  4. 在做了很多优化后，依然要尽量保持程序的可读性和模块性

如何进行程序优化

  1. 消除不必要的工作
  2. 利用处理器提供的指令集并行能力，同时执行多条指令

内存别名使用

$ gcc -Og [文件名]

上述代码中的-Og是在调用gcc并使用一组基本优化，打开优化标志会使编译器尝试以牺牲编译时间和调试程序的能力为代价来提高性能和/或代码大小。

  • 在编译器不知道代码的特殊情况下，只能考虑最保守的情况
#include<stdio.h>
void swap(long *xp,long *yp)
{
        *xp = *xp + *yp;
        *yp = *xp - *yp;
        *xp = *xp - *yp;
}

如果调用时xp等于yp，会有什么效果？

image-20220421174116445.png

函数调用

long f()
    
long func1()
{
    return f()+f()+f()+f();
}

long func2()
{
    return 4*f();
}

  • fun1和fun2等价嘛？性能有什么不同？编译器可不可以将func1优化为fun2

    这里其实更复杂，单纯的看fun2是比fun1要好的，但是编译器的角度，它不能这样优化，因为考虑到函数调用次数，也会影响全局变量的某些值，比如全局变量x，在f中加一个x的指针的++，这样优化了就错误了

就是这些是编译器优化容易错误的两个种情况，就是自己在写代码的时候优化应该更谨慎

//内敛函数替换优化函数调用

long counter  = 0;

long func1in(){
   	long t = counter++;
    t += counter++;
    t += counter++;
    t += counter++;
    return t;
}

//上述函数可被编译器优化为如下函数，gcc -Og 表示使用gcc编译器进行优化

long func1opt()
{
    long t = 4 * counter + 6;
    counter += 4;
    return t;
}

循环展开

void psum1(float a[],float p[],long n)  //前缀和函数
{
    long i;
    p[0] = a[0];
    for (int i = 1; i < n; i++)
    {
        p[i] = p[i - 1] + a[i];
    }
}

void psum2(float a[],float p[],long n)  //循环展开后的前缀和函数
{
    long i;
    p[0] = a[0];
    for (i = 1; i < n - 1;i+=2)
    {
        float mid_val = p[i - 1] + a[i];  
        p[i] = mid_val;                 //同时计算两个位置的值
        p[i + 1] = mid_val + a[i + 1];
    }
    //这样同时计算的越多越好嘛？
}

循环低效率消除

//需要多次计算，但是其值不变的，用变量保存
#define OP +
#define IDENT 0

void combine1(vec_ptr v,data_t *dest)
{
    long i;
    *dest = IDENT;
    for(i = 0 ;i < vec_length(v) ;i++)  //每一次循环都会判断并计算这个函数
    {
        data_t val;
        get_vec_element(v,i,&val);
        *dest = *dest OP val;
    }
}


void combine2(vec_ptr v,data_t *dest)
{
    long i;
    long length = vec_length(v);  //这里是一个优化
    *dest = IDENT;
    for(i = 0 ;i < length ;i++)
    {
        data_t val;
        get_vec_element(v,i,&val);
        *dest = *dest OP val;
    }
}

存储层次结构

  • 充分利用存储器的局部性原理，编写的程序要近可能的访问最近使用过的或最邻近的数据

  • 了解高速缓存结构使得程序运行得快分为两步

    1. 让最常见的情况运行得快，即更多的关注反复被执行的部分

    2. 尽量减少每个循环内部的缓存不命中数量

链接

链接是将各种代码收集组合成为单一文件的过程，可以在编译时链接也可也在加载时、甚至是运行时链接。

首先有以下文件

//main.c
#include<stdio.h>

int sum(int *a ,int n);
int array[2] = {1,2};

int main(){
        int val = sum(array,2);
        printf("sum = %d",val);
        return val;
}
//sum.c
int sum(int *a, int n)
{
        int i,s=0;

        for(i = 0 ; i < n ; i++){
                s +=a[i];
        }
        return s;
}

在Linux下使用gcc完成编译和链接

$ gcc -Og -o prog mian.c sum.c

添加-v 参数可以看到链接的全过程：

  1. 首先C预处理器(cpp),将原程序翻译为一个ASCII码中间文件main.i
  2. 驱动程序运行cc1，将main.i翻译为一个ASCII汇编语言文件main.s
  3. 驱动程序运行汇编器(as), 将main.s翻译成一个可重定位目标文件main.o
  4. 驱动再次经过上述过程产生sum.o
  5. 运行链接器ld,将main.o和sum.o以及一些必要的系统目标文件组合起来，创建一个可执行文件prog(-o 文件名定义，默认a.out)

在C++和java中，链接器的符号的重整，使得函数可以被重载，其内部会添加其他字符来区分。

可执行文件

加载器的工作原理