蓝色的笔记本

一、性能

1.1 在分层存储结构中，随着存储容量的增加，延迟也随之增加。参考

从数据可以看出，L1缓存和主存访问速度相差200倍。

二、缓存行

CPU缓存的基本单位是缓存行，主存数据和缓存的映射存在下列关系：

2.1 直接映射缓存

1、 index用于计算在哪一个缓存行
2、 offset用于计算在缓存行的哪个字节
3、 tag用于判断缓存是否命中（假设0x7f6601 和 0x8f6602两个地址，低位都一样，缓存行和字节偏移都命中了，tag不命中）

缺点：
图中，cache缓存8行数据，当访问第0行、第8行、第16行时，缓存无法命中，每次都要去主存加载，发生缓存颠簸

2.2 多路组相连

这是一个两路组相连的示意图：

1、index定位组
2、组内依次对tag进行对比（可以通过硬件并行比较增加性能）

三、缓存一致性

3.1 问题描述：

处理器 1 读 X ：从内存读取24并缓存
处理器 2 读 X ：从内存读取24并缓存
处理器 1 写 X = 32 ：更新自己的缓存
处理器 3 读 X = ？

如何保证缓存的一致性？参考

3.2 解决方案

3.1.1 嗅探-Snooping Solution(Snoopy Bus)

根据写操作对缓存数据的影响嗅探协议可分为：
Write-invalidate：
当处理器写入数据时，所有的独立缓存将通过总线嗅探得到通知，并标志自己的缓存失效。这保证了全局只有一份缓存是有效的。

• MSI
• MESI
• MOSI
• MOESI
• MESIF

Write-update：
当处理器写入数据时，所有的独立缓存将通过总线嗅探得到通知，并更新自己的缓存。通过总线广播给所有的缓存造成了总线繁忙，所以不常见。

3.1.2 目录-Directory-Based Schemes

3.2 MESI协议参考

MESI是四个状态的首字母缩写，在缓存行中用2个bit标志该缓存行的状态。

• M:Modified（只存在当前缓存行，已被修改，和主存不一致，需要更新回主存）
• E:Exclusive（只存在当前缓存行，和主存一致）
• S:Shared（其他缓存行也存在该数据，和主存一致）
• I:Invalid（此缓存行失效）

MESI的状态迁移：

四、参考文献

0.Java角度理解CPU缓存
1.Cache的基本原理
2.每个开发者需要知道的数据
3.硬件角度看内存屏障
4.软件角度内存屏障
5.stackoverflow-How do cache lines work?
6.courses-pdf

一、概述

很多时候我们都有一个疑问：一个对象在内存中占用多大的空间呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

$ jdk8-64/java -jar jol-cli.jar internals java.lang.Object
# Running 64-bit HotSpot VM.
# Using compressed oop with 3-bit shift.
# Using compressed klass with 3-bit shift.

Instantiated the sample instance via default constructor.

java.lang.Object object internals:
 OFFSET  SIZE   TYPE DESCRIPTION                  VALUE
      0     4        (object header)              05 00 00 00 # Mark word
      4     4        (object header)              00 00 00 00 # Mark word
      8     4        (object header)              00 10 00 00 # (not mark word)
     12     4        (loss due to the next object alignment)
Instance size: 16 bytes
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total

通过OpenJDK的Java-Object-Layout我们看到java.lang.Object的一个实例占用16 bytes。

同样的java.lang.Boolean类型占用的字节数：

1
2
3
4
5
6
7

java.lang.Boolean object internals:
 OFFSET  SIZE      TYPE DESCRIPTION                               VALUE
      0    12           (object header)                           N/A
     12     1   boolean Boolean.value                             N/A
     13     3           (loss due to the next object alignment)
Instance size: 16 bytes
Space losses: 0 bytes internal + 3 bytes external = 3 bytes total

1
2
3

[HEADER: 12 bytes]  12 
[value:   1 byte ]  13
[padding: 3 bytes]  16

其实一个对象通常由三块组成，分别是：对象头、实例数据和对齐填充。

二、对象头（object header）

在前面通过JOL打印输出的关于java.lang.Object信息中，我们看到object header占用12字节，但是输出并没有包含详细的结构信息，我们可以通过Hotspot的源码了解到对象头包含两个部分：mark word和class word。

2.1 mark word：

mark word在32位和64位机分别占32位和64位，当其中锁标志位的值不同时，它前面的bit存储不同的含义。

• 存储对象的gc年龄信息
• 存储Hashcode
• 存储锁信息

2.2 class word:

代码运行的时候，对象只是一串字节，我们可以通过class-word获取一些对象的元信息，它存储指向方法区中表示对象类型的指针，比如以下使用场景：

• 运行时类型检查
• 决定对象大小
• 计算接口调用的目标类

2.3 数组长度：

如果是数组类型，对象头会额外存储数组的长度信息。

• 快速计算对象的大小
• 数组边界检查

三、实例数据和对齐填充

实例数据即我们在代码中声明的变量等信息，它的存储受到一些规则的约束以及虚拟机参数的控制。

3.1 没有属性的类的内存布局

规则一：每个对象都是八字节对齐。

从前面Object的输出中，我们看到，当一个对象只有头部信息时占用16byte，刚好是8的整数倍。

3.2 Object子类的内存布局

跟在对象头后面的类属性按照它们的大小在内存中排序，例如：int是4字节、long是8字节。采用字节对齐可以提高性能，因为从内存读取4字节到4字节的寄存器性能更好。

为了节约内存，Sun的虚拟机在分配对象字段的时候和它们声明的顺序不同，有如下顺序规则：

1、double和long类型
2、int和float
3、short和char
4、boolean和byte
5、reference

为什么可以优化内存呢？我们看一下这个例子：

1
2
3
4
5
6
7

class MyClass {
    byte a;
    int c;
    boolean d;
    long e;
    Object f;        
}

它的对象布局如下：

1
2
3
4
5
6
7
8
9

[HEADER:  8 bytes]  8
[a:       1 byte ]  9
[padding: 3 bytes] 12
[c:       4 bytes] 16
[d:       1 byte ] 17
[padding: 7 bytes] 24
[e:       8 bytes] 32
[f:       4 bytes] 36
[padding: 4 bytes] 40

总共使用了40字节内存，其中14个用于内存对齐而浪费掉。如果重排顺序则：

1
2
3
4
5
6
7
8

[HEADER:  8 bytes]  8
[e:       8 bytes] 16
[c:       4 bytes] 20
[a:       1 byte ] 21
[d:       1 byte ] 22
[padding: 2 bytes] 24
[f:       4 bytes] 28
[padding: 4 bytes] 32

经过优化后只有6个字节用于对齐填充，总内存也只有32byte。

3.3 子类的内存布局

规则三：继承结构中属于不同类的字段不混合在一起。父类优先，子类其次。

1
2
3
4
5
6
7
8
9

class A {
   long a;
   int b;
   int c;
}

class B extends A {
   long d;
}

B类的布局如下：

1
2
3
4
5

[HEADER:  8 bytes]  8
[a:       8 bytes] 16
[b:       4 bytes] 20
[c:       4 bytes] 24
[d:       8 bytes] 32

如果父类的字段不符合4字节对齐。

规则四：父类的最后一个字段和子类第一个字段之间必须4字节对齐。

1
2
3
4
5
6
7

class A {
   byte a;
}

class B {
   byte b;
}

1
2
3
4
5

[HEADER:  8 bytes]  8
[a:       1 byte ]  9
[padding: 3 bytes] 12
[b:       1 byte ] 13
[padding: 3 bytes] 16

a后面的3个字节就是为了使其4字节对齐。这3个字节只能浪费不能给B使用。

最后一个规则可以用于节约一些内存空间：当子类的第一个属性是long或者double类型且父类没有以8字节边界结束。

规则五：子类的第一个字段是doubel或long且父类没有以8字节边界结束，JVM打破2的规则，先存储int、short、byte、reference来填补空缺。

例如：

1
2
3
4
5
6
7
8
9

class A {
  byte a;
}

class B {
  long b;
  short c;  
  byte d;
}

内存布局如下：

1
2
3
4
5
6
7

[HEADER:  8 bytes]  8
[a:       1 byte ]  9
[padding: 3 bytes] 12
[c:       2 bytes] 14
[d:       1 byte ] 15
[padding: 1 byte ] 16
[b:       8 bytes] 24

在字节12的位置，A类结束了。JVM打破2的规则放入short和byte类型，节约了4字节中的3个字节，否则将浪费掉。

3.4 数组的内存布局

数组类型有一个额外的头部字段保存数组的长度，接下来是数组的元素，数组作为普通对象也是8字节对齐的。

这是byte[3]的布局：

1
2
3
4
5

[HEADER:  12 bytes] 12
[[0]:      1 byte ] 13
[[1]:      1 byte ] 14
[[2]:      1 byte ] 15
[padding:  1 byte ] 16

这是long[3]的布局:

1
2
3
4
5

[HEADER:  12 bytes] 12
[padding:  4 bytes] 16
[[0]:      8 bytes] 24
[[1]:      8 bytes] 32
[[2]:      8 bytes] 40

3.5 内部类的内存布局

非静态内部类有一个额外的隐藏字段，持有外部类的引用。这个字段是一个常规的引用,它符合对象在内存布局的规则。内部类因此有4字节额外的开销。

一、概述

synchronized作为Java内建的关键字和锁机制，理解和使用它是必要的也是有难度的。个人认为深入理解此关键字在于以下几个方面：

• 基础层面：正确理解对象锁和类锁，并熟练使用
• 能力提升：
  • 了解对象的内存布局，观察锁如何影响对象的内存布局
  • 了解锁优化，锁升级及其过程
• 更上一层楼：OpenJDK源码走读

本文只是记录和翻译了一些英文文档的内容，作为笔记以后翻阅。详细内容可看原文。

二、对象锁和类锁

1.1 对象锁：修饰代码块和实例方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

static class ObjectLock {
        public void test1() {
            synchronized (this) {//此代码块锁住当前对象
                int i = 5;
                while (i-- > 0) {
                    System.out.println(Thread.currentThread().getName() + " : " + i);
                    try {
                        Thread.sleep(500);
                    } catch (InterruptedException ie) {
                    }
                }
            }
        }

        public synchronized void test2() {
            int i = 5;
            while (i-- > 0) {
                System.out.println(Thread.currentThread().getName() + " : " + i);
                try {
                    Thread.sleep(500);
                } catch (InterruptedException ie) {
                }
            }
        }
}

1.2 类锁:修饰代码块和静态方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

 static class ClazzLock {
        public void test1() {
            synchronized (ClazzLock.class) {//此代码块锁住class类
                int i = 5;
                while (i-- > 0) {
                    System.out.println(Thread.currentThread().getName() + " : " + i);
                    try {
                        Thread.sleep(500);
                    } catch (InterruptedException ie) {
                    }
                }
            }
        }

        /**
         * 静态方法属于类
         */
        public static synchronized void test2() {
            int i = 5;
            while (i-- > 0) {
                System.out.println(Thread.currentThread().getName() + " : " + i);
                try {
                    Thread.sleep(500);
                } catch (InterruptedException ie) {
                }
            }
        }
}

三、锁优化

依据一：数据显示，许多锁有局部性特征，也就是说很多锁的锁定和释放都发生在特定的线程上。
依据二：数据显示，大部分Java对象不存在竞争。

• 适应性自旋-Adaptive Spinning
• 锁消除-Lock Elimination
• 锁粗化-Lock Coarsening
• 轻量级锁-Lightweight Locking
• 偏向锁-Biased Locking

3.1 偏向锁

当我们开发了一个多线程环境下的模块时，其他人可能把它用在单线程环境下，此时加锁逻辑就是多余的。即使使用轻量级锁，每次获取锁都执行CAS原子指令也是一种性能损耗。使用偏向锁，线程首次获取锁时记录偏向于它自己,当有其他线程获取锁时，偏向锁要撤销，使用其他锁机制，如轻量级锁。

lock-field中有一个bit用于记录是否偏向状态，初始状态下是处于偏向锁状态，但没有设置偏向的线程ID。当线程首次获取锁时，发现没有指定偏向的线程，则使用CAS设置偏向线程，来避免竞态条件。

3.2 轻量级锁（Thin Lock）

相对于每次对象锁定都获取monitor结构的重量级锁而言，轻量级锁只是使用CAS原子指令修改lock-field（锁信息字段），因此轻量级锁不支持wait和notify。当发生锁竞争时，轻量级锁膨胀，同时分配monitor结构，lock-field更新成monitor的指针。

Java的锁是可重入的，所以需要记录当前锁的重入次数和锁的持有者。

• 记录方式一：
  最直接的方式是把lock-field分成两部分，一个记录锁的持有者，一个记录锁重入次数。由于lock-field字段长度固定，所以重入次数被限制了。重入次数达到上限只能升级为重量级锁。

• 记录方式二：
  当线程需要获取锁时，在获取锁的线程栈中保存lock-records记录。线程获取的所有锁记录都将保存在这个集合中，它的顺序和获取锁的顺序一致。

轻量级锁的变种和提升包含 tasuki-lock 和 meta-lock 其算法思想是一致的，差异在于实现细节，

1、轻量级锁的加锁过程

在代码进入同步块的时，如果同步对象锁状态为无锁（锁标志位为“01”，偏向锁位为“0”）虚拟机首先将在当前线程的栈帧中建立一个名为锁记录（Lock Record）的空间，用于存储锁对象目前的Mark Word的拷贝（官方称之为 Displaced Mark Word）。然后，虚拟机将使用CAS操作尝试将对象的Mark Word更新为指向Lock Record的指针，并将Lock record里的owner指针指向object mark word。如果这个更新动作成功了，那么这个线程就拥有了该对象的锁，并且对象Mark Word的锁标志位设置为“00”，即表示此对象处于轻量级锁定状态。

如果这个更新操作失败了，虚拟机首先会检查对象的Mark Word是否指向当前线程的栈帧，如果是就说明当前线程已经拥有了这个对象的锁，那就可以直接进入同步块继续执行。
否则说明多个线程竞争锁，轻量级锁就要膨胀为重量级锁，锁标志的状态值变为“10”，Mark Word中存储的就是指向重量级锁（互斥量）的指针，后面等待锁的线程也要进入阻塞状态。
而当前线程便尝试使用自旋来获取锁，自旋就是为了不让线程阻塞，而采用循环去获取锁的过程。

                 图2.1 轻量级锁CAS操作前/后堆栈与对象的状态

2、轻量级锁的解锁过程：

（1）通过CAS操作尝试把线程中复制的Displaced Mark Word对象替换当前的Mark Word。

（2）如果替换成功，整个同步过程就完成了。

（3）如果替换失败，说明有其他线程尝试过获取该锁（此时锁已膨胀），那就要在释放锁的同时，唤醒被挂起的线程。

3.3 锁消除

锁消除即删除不必要的加锁操作。根据代码逃逸技术，如果判断到一段代码中，堆上的数据不会逃逸出当前线程，那么可以认为这段代码是线程安全的，不必要加锁。

1
2
3
4
5
6
7
8

public class Test extends Thread{
    public static void main(String[] args) {
        contactString("aa", "bb", "cc");
    }
    public static String contactString(String s1, String s2, String s3) {
        return new StringBuffer().append(s1).append(s2).append(s3).toString();
    }
}

虽然StringBuffer的append是一个同步方法，但是这段程序中的StringBuffer属于一个局部变量，并且不会从该方法中逃逸出去，所以其实这过程是线程安全的，可以将锁消除。

3.4 锁粗化

虚拟机对连续的加锁操作（synchronized append）进行范围扩展（粗化）到整个操作序列的外部。

1
2
3
4
5
6
7

public String concatString(String s1,String s2, String s3){
    StringBuffer sb = new StringBUffer();
    sb.append(s1);
    sb.append(s2);
    sb.append(s3);
    return sb.toString();
}

四、参考资料

1.Evaluating and improving biased locking in the HotSpot virtual machine
2.Java并发编程：Synchronized底层优化（偏向锁、轻量级锁）
3.锁：锁优化（synchronized 锁升级过程、锁消除、锁粗化）
4.Synchronization

一、什么是Flow

1、如何通过同步和异步方式返回多个值？

1.1 同步方式返回多个值

1
2
3
4
5

fun simple(): List<Int> = listOf(1, 2, 3)
 
fun main() {
    simple().forEach { value -> println(value) } 
}

1.2 同步方式依次返回多个值

1
2
3
4
5
6
7
8
9
10

fun simple(): Sequence<Int> = sequence { // sequence builder
    for (i in 1..3) {
        Thread.sleep(1000) // pretend we are computing it
        yield(i) // yield next value
    }
}

fun main() {
    simple().forEach { value -> println("time = ${System.currentTimeMillis()} ,$value") } 
}

1.3 异步方式返回多个值

1
2
3
4
5
6
7
8

suspend fun simple(): List<Int> {
    delay(1000) // pretend we are doing something asynchronous here
    return listOf(1, 2, 3)
}

fun main() = runBlocking<Unit> {
    simple().forEach { value -> println(value) } 
}

1.4 如何通过异步的方式依次返回多个值呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

fun simple(): Flow<Int> = flow { // flow builder
    for (i in 1..3) {
        delay(100) // pretend we are doing something useful here
        emit(i) // emit next value
    }
}

fun main() = runBlocking<Unit> {
    // Launch a concurrent coroutine to check if the main thread is blocked
    launch {
        for (k in 1..3) {
            println("I'm not blocked $k")
            delay(100)
        }
    }
    // Collect the flow
    simple().collect { value -> println(value) } 
}

通过flow，我们可以实现异步的数据流。

2、Flow是冷数据流

冷数据流：每次调用collect函数时都会触发执行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

fun simple(): Flow<Int> = flow { 
    println("Flow started")
    for (i in 1..3) {
        delay(100)
        emit(i)
    }
}

fun main() = runBlocking<Unit> {
    println("Calling simple function...")
    val flow = simple()
    println("Calling collect...")
    flow.collect { value -> println(value) } 
    println("Calling collect again...")
    flow.collect { value -> println(value) } 
}

3、Flow的取消

1
2
3
4
5
6
7
8
9
10
11
12
13
14

fun simple(): Flow<Int> = flow { 
    for (i in 1..3) {
        delay(100)          
        println("Emitting $i")
        emit(i)
    }
}

fun main() = runBlocking<Unit> {
    withTimeoutOrNull(250) { // Timeout after 250ms 
        simple().collect { value -> println(value) } 
    }
    println("Done")
}

4、如何构建Flow？

• flow{ ... }
• flowOf
• .asFlow()

5、Flow操作符

5.1 中间操作符

• map
• filter
• transform
• take

5.2 终止操作符

• collect
• toList / toSet
• first / single
• reduce / fold

5.3 buffer当流的处理速度慢于发射速度时，通过buffer提前缓存可以提高效率：

优化前：耗时1200ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

fun simple(): Flow<Int> = flow {
    for (i in 1..3) {
        delay(100) // pretend we are asynchronously waiting 100 ms
        emit(i) // emit next value
    }
}

fun main() = runBlocking<Unit> { 
    val time = measureTimeMillis {
        simple().collect { value -> 
            delay(300) // pretend we are processing it for 300 ms
            println(value) 
        } 
    }   
    println("Collected in $time ms")
}

优化后：耗时1000ms

1
2
3
4
5
6
7
8
9

val time = measureTimeMillis {
    simple()
        .buffer() // buffer emissions, don't wait
        .collect { value -> 
            delay(300) // pretend we are processing it for 300 ms
            println(value) 
        } 
}   
println("Collected in $time ms")

5.4 conflate当生产速度大于消费速度，忽略未来得及处理的值

1
2
3
4
5
6
7
8
9
10
11
12
13

val time = measureTimeMillis {
    simple()
        .conflate() // conflate emissions, don't process each one
        .collect { value -> 
            delay(300) // pretend we are processing it for 300 ms
            println(value) 
        } 
}   
println("Collected in $time ms")
//输出：
//1
//3
//Collected in 758 ms

5.5 collectLatest 如果消费者很慢，取消它，新值过来时再重新启动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

val time = measureTimeMillis {
    simple()
        .collectLatest { value -> // cancel & restart on the latest value
            println("Collecting $value") 
            delay(300) // pretend we are processing it for 300 ms
            println("Done $value") 
        } 
}   
println("Collected in $time ms")
//output:
//Collecting 1
//Collecting 2
//Collecting 3
//Done 3
//Collected in 741 ms

5.6 多个flow合并：zip / combine

使用zip操作符

1
2
3
4
5
6
7
8

val nums = (1..3).asFlow() // numbers 1..3
val strs = flowOf("one", "two", "three") // strings 
nums.zip(strs) { a, b -> "$a -> $b" } // compose a single string
    .collect { println(it) } // collect and print
//output:
//1 -> one
//2 -> two
//3 -> three

当两个flow不同步时：

1
2
3
4
5
6
7
8
9
10
11
12

//速度不同步时，使用zip，到达同步点才输出
val nums = (1..3).asFlow().onEach { delay(300) } // numbers 1..3 every 300 ms
val strs = flowOf("one", "two", "three").onEach { delay(400) } // strings every 400 ms
val startTime = System.currentTimeMillis() // remember the start time 
nums.zip(strs) { a, b -> "$a -> $b" } // compose a single string with "zip"
    .collect { value -> // collect and print 
        println("$value at ${System.currentTimeMillis() - startTime} ms from start") 
    } 
//output:
//1 -> one at 428 ms from start
//2 -> two at 828 ms from start
//3 -> three at 1230 ms from start

1
2
3
4
5
6
7
8
9
10
11
12
13
14

////速度不同步时，使用combine，有值到达即输出，无视同步
val nums = (1..3).asFlow().onEach { delay(300) } // numbers 1..3 every 300 ms
val strs = flowOf("one", "two", "three").onEach { delay(400) } // strings every 400 ms          
val startTime = System.currentTimeMillis() // remember the start time 
nums.combine(strs) { a, b -> "$a -> $b" } // compose a single string with "combine"
    .collect { value -> // collect and print 
        println("$value at ${System.currentTimeMillis() - startTime} ms from start") 
    } 
//output:
//1 -> one at 452 ms from start
//2 -> one at 651 ms from start
//2 -> two at 854 ms from start
//3 -> two at 952 ms from start
//3 -> three at 1256 ms from start

参考文档：
1.官方文档

1.对称加解密的过程：

（大家用相同的钥匙来进行加解密）
发送端和接收端首先要共享相同的密钥k(即通信前双方都需要知道对应的密钥)才能进行通信。发送端用共享密钥k对明文p进行加密，得到密文c，并将得到的密文发送给接收端，接收端收到密文后，并用其相同的共享密钥k对密文进行解密，得出明文p。

一般加密和解密的算法是公开的，需要保持隐秘的是密钥k
流行的对称加密算法有：DES，Triple-DES，RC2和RC4，AES

缺点：

• 发送方和接收方首先需要共享相同的密钥，即存在密钥k的分发问题，如何安全的把共享密钥在双方进行分享，这本身也是一个如何安全通信的问题，一种方法是提前双方约定好，不通过具体的通信进行协商，避免被监听和截获。另外一种方式，将是下面我们介绍的通过非对称加密信道进行对称密码的分发和共享，即混合加密系统。
• 密钥管理的复杂度问题。由于对称加密的密钥是一对一的使用方式，若一方要跟n方通信，则需要维护n对密钥。

优点：

• 加密和解密的速度要比非对称加密快很多，因此常用非对称加密建立的安全信道进行共享密钥的分享，完成后，具体的加解密则使用对称加密。即混合加密系统。

另外一个点需要重点说明的是，密钥k的长度对解密破解的难度有很重大的影响，k的长度越长，对应的密码空间就越大，遭到暴力破解或者词典破解的难度就更大，就更加安全。

2.数字签名的过程：

• 发送方A首先对变长的报文提取成一个定长的摘要，一般是md5等
• A对摘要应用了一个签名函数，并且用A自己的私钥作为参数，因为只有A才知道私钥，所以正确的签名会说明签名者就是其所有者。
• 一旦计算出签名，节点A就将其附加到报文的末尾，并将报文和签名一起都发送给B
• 在接收端B，首先会按照同样的算法计算出报文的摘要，然后对签名用A的公钥进行解码，得出解码后的摘要，两个摘要进行比较，则可以判断是否是A发送的且内容没被篡改过。

3.非对称加解密的过程：

加密一方找到接收方的公钥e (如何找到呢？大部分的公钥查找工作实际上都是通过数字证书来实现的)，然后用公钥e对明文p进行加密后得到密文c，并将得到的密文发送给接收方，接收方收到密文后，用自己保留的私钥d进行解密，得到明文p，需要注意的是：用公钥加密的密文，只有拥有私钥的一方才能解密，这样就可以解决加密的各方可以统一使用一个公钥即可。

常用的非对称加密算法有：RSA

优点：

• 不存在密钥分发的问题，解码方可以自己生成密钥对，一个做私钥存起来，另外一个作为公钥进行发布。
• 解决了密钥管理的复杂度问题，多个加密方都可以使用一个已知的公钥进行加密，但只有拥有私钥的一方才能解密。

缺点：

• 非对称加密不足的地方是加解密的速度没有对称加密快。

综上，分析了对称加密和非对称加密各自的优缺点后，有没有一种办法是可以利用两者的优点但避开对应的缺点呢？答应是有的，实际上用得最多的是混合加密系统，比如在两个节点间通过便捷的公开密码加密技术建立起安全通信，然后再用安全的通信产生并发送临时的随机对称密钥，通过更快的对称加密技术对剩余的数据进行加密。

一、人们如何做出决策

1.1 人们面临权衡取舍

选择一样东西就意味着你要放弃另外一样东西。认识到生活中的权衡是重要的，因为人们只有了解他们可以得到的选择，才能作出良好的决策。

1.2 某种东西的成本是为了得到它而放弃的东西

一种东西的机会成本是为了得到这种东西所放弃的东西

1.3 理性人考虑边际量

生活中的许多决策涉及到对现有行动计划进行微小的增量调整。 经济学家把这些调整称为边际变动。
个人和企业通过考虑边际量将会作出更好的决策。只有一种行动的边际收益大于边际成本，一个理性决策者才 会采取这项行动。

1.4 人们会对激励作出反应

• 由于理性人通过比较成本与收益🉐做出决策，所以他们会对激励做出反应。
• 在分析任何一种政策时，不仅应该考虑直接影响，而且还应该考 虑激励发生作用的间接影响。
• 如果政策改变了激励，它就将使人们改 变自己的行为。

二、人们如何相互影响

2.1 贸易能使每个人的状况变得更好

贸易使各国可以专 门从事自己最擅长活动，并享有很多的各种各样物品与劳务

2.2 市场通常是组织经济活动的一种好方法

• 在市场经济中，中央计划者的决策被千百万企业和家庭的决策所取代。
• 价格和利己引导人们决策
• 价格就是看不见的手用来指引经济活动的工具
• 当政府阻止价格根据供求状况自发调整时，他就限制了看不见的手🤚对组成经济的千百万家庭👪和企业的决策进行协调的能力

2.3 政府有时可以改善市场结果

• 只有在政府实施规则并维护对市场经济至关重要的制度时，看不见的手才能施展其魔力。
• 看不见的手🤚是强有力的，但并不是无所不能的。政府干预经济的原因有两类：促进效率和促进平等。

三、整体经济如何运行

3.1 一国的生活水平取决于它生产物品与服务的能力

生产率：每单位劳动投入所生产的物品与服务数量。

3.2 当政府发行了过多货币时，物价上升

3.3 社会面临通货膨胀与失业之间的短期权衡取舍

• 货币的增加刺激社会的整体支出水平，从而增加对物品与服务的需求
• 需求的增加随着时间的推移，会引起企业提高物价，同时它也鼓励企业雇佣更多的工人👷，并生产更多的物品与服务
• 雇佣更多的工人👷意味着更少的失业。

一、可重定位文件

1
2
3
4
5
6
7
8
9

//main.c                    //x.c

extern void foo(void);      |   #include <stdio.h>
                            |
int main(void)              |   void foo()
{                           |   {
    foo();                  |       printf("foo\n");
    return 0;               |   }
}                           |

1
2
3
4
5
6
7
8
9

> objdump -d main.o
00000000 <main>:
   0:	55                   	push   %ebp
   1:	89 e5                	mov    %esp,%ebp
   3:	83 e4 f0             	and    $0xfffffff0,%esp
   6:	e8 fc ff ff ff       	call   7 <main+0x7>
   b:	b8 00 00 00 00       	mov    $0x0,%eax
  10:	c9                   	leave
  11:	c3                   	ret

在编译和汇编阶段，[main.c -> main.o] 汇编器无法确定外部定义的函数和全局变量的地址，所以它只能使用一个假地址占位，并产生一条额外的记录，让后面的链接器使用这条记录帮它完成地址修正。这条记录对于代码段来说放在[.rel.text] ，对于数据段来说放在[.rel.data],它们都是重定位文件的一个section。

对于每一条记录都对应于如下的一个数据结构：

1
2
3
4
5

typedef struct {
        Elf32_Addr r_offset;
        uint32_t   r_info;
        int32_t    r_addend;
} Elf32_Rela;

二、静态链接

1、多个目标文件的合并:

2、对代码段，数据段以及各符号进行地址分配
3、根据 [relocation entries] 重新计算代码和数据段中的假地址。

三、动态链接

1、静态链接的缺点

• 静态链接将使一些公用代码如libc库产生冗余，浪费内存和磁盘空间
• 如果模块化开发，一个模块更新就得重新链接

2、动态链接的概念

相较于静态链接在编译期进行链接操作，将链接过程推迟到运行时进行的过程叫动态链接。

3、动态链接的实现

3.1 地址无关代码
由于在运行时，代码段是共享的，只能读不能写，所以需要将指令中那些需要修改的部分分离出来，跟数据部分放在一起，这样指令部分就可以保持不变，而数据部分可以在每一个进程中拥有一个副本。

3.2 全局偏移表（Global Offset Table）
当链接过程发生在运行期时，外部的符号调用只有在运行时装载模块后才能确定模块被装载的地址，以及模块内符号的确切地址。所以ELF提供了一个全局偏移表（GOT）来记录这些外部模块的符号引用。当模块被装载时，会更新此表的内容。

四、参考文献

1.Linking
2.understanding-relocation-elf
3.ELF Binaries and Relocation Entries
4.static-linking-dynamic-linking
5.ELF函数重定位问题

一、市盈率

1.1 PE - 静态市盈率

① 市盈率 = 当日收盘价 / 上一年度每股税后利润

② 市盈率 = 当前总市值 / 上年度净利润

理解：

• 公司需要累计多少年的盈利才能达到目前的市价水平。
• 值越低说明投资回收期短，风险越小，投资价值越高。
• 值越大说明翻本期长，风险大。

缺点：

• 取的是上一年度的净利润，是一个过去的值，有点滞后。

例子：
你花了240w买了一套二手房，打算进行出租赚点外快，已知去年平均月租2w，一年收益大概24w。以去年这些数据为参考，你预计十年后才能赚回成本240w，所以市盈率 = 10。

1.2 动态市盈率
为了弥补静态市盈率的滞后性，增加动态市盈率作为参考指标。

市盈率 = 当前总市值 / X

根据当前的时间节点不同计算X的值：
X = 当年最近一个季度的净利润 * 4
X = 最近半年净利润 * 2
X = 最近三季度净利润 * 1.5

1.3 静态市盈率 vs 动态市盈率

• 静态市盈率反映的是过去的数据，动态市盈率反映的是未来的预估
• 动态市盈率 > 静态市盈率，说明最近（一个季度、半年、三个季度）公司的利润下降了。

1.4 TTM-Trailing Twelve Months

• 最近十二个月市盈率，也叫滚动市盈率。
• 它也是一个对过去情况的分析说明。

二、每股净值产

每股净值产 = （总资产 - 总负债） / 总股数

三、市净率

3.1 PB-市净率

市净率 = 每股市价 / 每股净值产
每股净资产 = 股东权益 / 总股本

市净率越低那么它的投资价值就越高，这也就意味着它的风险越低。

一、概述

代码是解决问题的工具。当通过编码方式解决一个问题时，通常有如下步骤：

• 定义问题
• 设计解决方案
• 编码实现方案
• 测试程序

编码实现通常是我们利用计算机高级语言书写的，符合一定逻辑的程序代码，这种含逻辑的代码计算机是无法理解的，它能理解的只是一条条由0和1组成的指令即机器语言。所以这就涉及从高级语言到机器语言的翻译和转换过程，处理这个过程的程序叫编译器。

编译器这个程序，很庞大很复杂，为了让它简洁，好控制，我们把它拆成四个部分：

• 预处理器
• 编译器
• 汇编器
• 链接器

每一个阶段基本上都是在为下一个阶段做准备，它的过程如下图所示：

预处理器（Preprocessor）处理代码的过程叫预处理阶段，它所做的工作包括：

• #define宏定义展开
• 处理条件编译指令
• 处理#include指令
• 删除注释
• 添加行号
• 保留#pragma指令

编译器（Compiler）处理代码的过程叫编译，它主要是将上一步的产物转换成汇编代码，它的工作内容包括：

• 词法分析
• 语法分析
• 语义分析
• 优化

汇编器（Assembler）处理代码的过程叫汇编过程，它主要将汇编代码转换成二进制的机器码

• 汇编码到机器码的翻译

链接器（Linker）处理代码的过程叫链接过程，多个文件合并成一个文件

• 空间与地址分配-相同部分合并
• 符号解析和重定位-合并后位置（偏移量）调整

综上可知，目标文件是程序未链接前的一个中间文件。目标文件内容的存储方式符合ELF文件标准，所以他是一种特殊的ELF文件。

二、文件结构解析

目标文件其实是ELF文件的一种，常见的ELF文件还有.so和.oat文件等。ELF文件存在两种观察角度，分别是编译角度和运行角度。编译角度是指，在代码编译阶段的存储格式。运行角度是指，文件被加载进内存时的存储格式。
两个角度看到的结构略有差异。如图：

从图中可以得到这样一些信息：
1、Program Header Table对于编译视图是可选的，因为它只在程序被加载进内存时使用到。Section Header Table对于执行视图是可选的。
2、编译视图是以section为组织单位，执行视图是以segment为组织单位（多个section会被映射到同一个segment）。

下面介绍一些重要的结构。

ELF Header-文件的总体结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#define EI_NIDENT 16
typedef struct {
    unsigned char e_ident[EI_NIDENT];
    Elf32_Half e_type;               /* 此elf文件的类型见下表  */
    Elf32_Half e_machine;            /* CPU平台架构  */
    Elf32_Word e_version;            /* 此文件的版本  */
    Elf32_Addr e_entry;              /* 加载完该程序后的执行入口  */
    Elf32_Off e_phoff;               /* program header table在文件中的偏移量  */
    Elf32_Off e_shoff;               /* section header table在此文件中的偏移量 */
    Elf32_Word e_flags;              /* processor-specific flags associated with the file */
    Elf32_Half e_ehsize;             /* the ELF header's size in bytes. */
    Elf32_Half e_phentsize;          /* program-header-table数组中一个元素的大小 */
    Elf32_Half e_phnum;              /* program-header-table数组元素的个数 */
    Elf32_Half e_shentsize;          /* section header table数组中一个元素的大小 */
    Elf32_Half e_shnum;              /* section header table包含的元素个数 */
    Elf32_Half e_shstrndx;           /* the section header table index of the entry associated with the section name string table. */
 } Elf32_Ehdr;

file /bin/bash //executable
file /xxx/xx.so //shared object

Program Header Table

程序装载时，根据此结构的信息对文件进行分段（segment）。描述了磁盘上可执行文件的内存布局以及如何映射到内存中。

1
2
3
4
5
6
7
8
9
10

typedef struct {
   uint32_t   p_type;   /* 此元素描述的是哪种segment，以及如何解析  */
   Elf32_Off  p_offset; /* segment首字节在文件中的偏移值  */
   Elf32_Addr p_vaddr;  /* 应该加载到内存中的哪个虚拟地址中  */
   Elf32_Addr p_paddr;  /* 相关的物理地址，BSD中为0  */
   uint32_t   p_filesz; /* 文件的字节数  */
   uint32_t   p_memsz;  /* 加载到内存中的字节数  */
   uint32_t   p_flags;  /* segment类型标志位  */
   uint32_t   p_align;  /* 内存对齐  */
} Elf32_Phdr;

Section Header Table

用于定位文件中所有的section，主要用于链接和调试，没有Section Header Table程序仍然可以正常运行，因为它没有对内存布局进行描述，它是一个元素为Elf32_Shdr的数组结构。

1
2
3
4
5
6
7
8
9
10
11
12
13

typedef struct
{
	Elf32_Word sh_name;      /* Section name (string tbl index)   */
	Elf32_Word sh_type;      /* Section type                      */
	Elf32_Word sh_flags;     /* Section flags                     */
	Elf32_Addr sh_addr;      /* Section virtual addr at execution */
	Elf32_Off sh_offset;     /* Section file offset               */
	Elf32_Word sh_size;      /* Section size in bytes             */
	Elf32_Word sh_link;      /* Link to another section           */
	Elf32_Word sh_info;      /* Additional section information    */
	Elf32_Word sh_addralign; /* Section alignment                 */
	Elf32_Word sh_entsize;   /* Entry size if section holds table */
} Elf32_Shdr;

字符串表和符号表（String and symbol tables）

存放scetion的名字，以及符号信息。其他结构通过index访问此结构中的字符串信息。符号表保存了用于定位符号引用的信息。它是以下结构的数组：

1
2
3
4
5
6
7
8

typedef struct {
       uint32_t      st_name;
       Elf32_Addr    st_value;
       uint32_t      st_size;
       unsigned char st_info;
       unsigned char st_other;
       uint16_t      st_shndx;
} Elf32_Sym;

Relocation entries (Rel & Rela)

重定位是连接符号引用（函数的名字）和符号定义（函数的定义、函数的实现）的过程。重定位文件必须包含如何修改section内容的信息，来让执行文件或共享目标文件正确的调用外部函数。

1
2
3
4
5
6
7
8
9
10

typedef struct {
        Elf32_Addr      r_offset;
        Elf32_Word      r_info;
} Elf32_Rel;
 
typedef struct {
        Elf32_Addr      r_offset;
        Elf32_Word      r_info;
        Elf32_Sword     r_addend;
} Elf32_Rela;

r_offset：
对于重定位文件来说，此值表示从section的开始到被修改值在section中的偏移量。
对于执行文件和共享库文件来说，此值表示需要被重定位的虚拟地址。

r_info：
符号表的index和重定位的类型。

r_addend：
用于计算重定位字段的值。

Dynamic tags（Dyn）

.dynamic这个section存储一些包含动态链接信息的结构

1
2
3
4
5
6
7
8
9

typedef struct {
        Elf32_Sword    d_tag;
        union {
            Elf32_Word d_val;
            Elf32_Addr d_ptr;
        } d_un;
 } Elf32_Dyn;
           
extern Elf64_Dyn _DYNAMIC[];

一些图示

三、参考链接

Linux manual page
The structure of an ARM ELF image
Compiling, Linking and Building

一、Class文件结构概览

1.1 概述

• 每一个class文件包含一个类或者接口的定义
• 以大端方式存储
• u1、u2、u4分别表示1、2、4个字节

1.2 数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

ClassFile {
    u4             magic;
    u2             minor_version;
    u2             major_version;
    u2             constant_pool_count;
    cp_info        constant_pool[constant_pool_count-1];
    u2             access_flags;
    u2             this_class;
    u2             super_class;
    u2             interfaces_count;
    u2             interfaces[interfaces_count];
    u2             fields_count;
    field_info     fields[fields_count];
    u2             methods_count;
    method_info    methods[methods_count];
    u2             attributes_count;
    attribute_info attributes[attributes_count];
}

1.3 图形化表示

1.4 示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public interface Car {
    void drive();
}

public class BMWCar implements Car{

    private String name;
    
    public BMWCar() {
        name = "宝马";
    }
    
    @Override
    public void drive() {
        System.out.println("BMW car drive." + name);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

Last modified 2017-11-10; size 644 bytes
  MD5 checksum ac6d7477d45479490e4ea3f660b1dcdd
  Compiled from "BMWCar.java"
public class BMWCar implements Car
  minor version: 0
  major version: 52
  flags: ACC_PUBLIC, ACC_SUPER
Constant pool:
   #1 = Methodref          #12.#23        // java/lang/Object."<init>":()V
   #2 = String             #24            // 宝马
   #3 = Fieldref           #11.#25        // BMWCar.name:Ljava/lang/String;
   #4 = Fieldref           #26.#27        // java/lang/System.out:Ljava/io/PrintStream;
   #5 = Class              #28            // java/lang/StringBuilder
   #6 = Methodref          #5.#23         // java/lang/StringBuilder."<init>":()V
   #7 = String             #29            // BMW car drive.
   #8 = Methodref          #5.#30         // java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
   #9 = Methodref          #5.#31         // java/lang/StringBuilder.toString:()Ljava/lang/String;
  #10 = Methodref          #32.#33        // java/io/PrintStream.println:(Ljava/lang/String;)V
  #11 = Class              #34            // BMWCar
  #12 = Class              #35            // java/lang/Object
  #13 = Class              #36            // Car
  #14 = Utf8               name
  #15 = Utf8               Ljava/lang/String;
  #16 = Utf8               <init>
  #17 = Utf8               ()V
  #18 = Utf8               Code
  #19 = Utf8               LineNumberTable
  #20 = Utf8               drive
  #21 = Utf8               SourceFile
  #22 = Utf8               BMWCar.java
  #23 = NameAndType        #16:#17        // "<init>":()V
  #24 = Utf8               宝马
  #25 = NameAndType        #14:#15        // name:Ljava/lang/String;
  #26 = Class              #37            // java/lang/System
  #27 = NameAndType        #38:#39        // out:Ljava/io/PrintStream;
  #28 = Utf8               java/lang/StringBuilder
  #29 = Utf8               BMW car drive.
  #30 = NameAndType        #40:#41        // append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
  #31 = NameAndType        #42:#43        // toString:()Ljava/lang/String;
  #32 = Class              #44            // java/io/PrintStream
  #33 = NameAndType        #45:#46        // println:(Ljava/lang/String;)V
  #34 = Utf8               BMWCar
  #35 = Utf8               java/lang/Object
  #36 = Utf8               Car
  #37 = Utf8               java/lang/System
  #38 = Utf8               out
  #39 = Utf8               Ljava/io/PrintStream;
  #40 = Utf8               append
  #41 = Utf8               (Ljava/lang/String;)Ljava/lang/StringBuilder;
  #42 = Utf8               toString
  #43 = Utf8               ()Ljava/lang/String;
  #44 = Utf8               java/io/PrintStream
  #45 = Utf8               println
  #46 = Utf8               (Ljava/lang/String;)V
{
  public BMWCar();
    descriptor: ()V
    flags: ACC_PUBLIC
    Code:
      stack=2, locals=1, args_size=1
         0: aload_0
         1: invokespecial #1                  // Method java/lang/Object."<init>":()V
         4: aload_0
         5: ldc           #2                  // String 宝马
         7: putfield      #3                  // Field name:Ljava/lang/String;
        10: return
      LineNumberTable:
        line 6: 0
        line 7: 4
        line 8: 10

  public void drive();
    descriptor: ()V
    flags: ACC_PUBLIC
    Code:
      stack=3, locals=1, args_size=1
         0: getstatic     #4                  // Field java/lang/System.out:Ljava/io/PrintStream;
         3: new           #5                  // class java/lang/StringBuilder
         6: dup
         7: invokespecial #6                  // Method java/lang/StringBuilder."<init>":()V
        10: ldc           #7                  // String BMW car drive.
        12: invokevirtual #8                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
        15: aload_0
        16: getfield      #3                  // Field name:Ljava/lang/String;
        19: invokevirtual #8                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
        22: invokevirtual #9                  // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
        25: invokevirtual #10                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
        28: return
      LineNumberTable:
        line 12: 0
        line 13: 28
}
SourceFile: "BMWCar.java"

二、常量池的结构

常量池是一个cp_info的数组：通过tag定位到具体的数据结构，再通过数据结构的表示，判断下面几个字节怎么解析。

1
2
3
4

cp_info {
    u1 tag; //cp-info的类型
    u1 info[];//类型对应的数组
}

三、字段的结构

每一个字段用一个 field_info的结构体表示

1
2
3
4
5
6
7

field_info {
    u2             access_flags;
    u2             name_index;//指向常量池的index，表示字段名
    u2             descriptor_index;//指向常量池的inde，字段的描述符
    u2             attributes_count;
    attribute_info attributes[attributes_count];
}

四、方法的结构

1
2
3
4
5
6
7

method_info {
    u2             access_flags;
    u2             name_index;
    u2             descriptor_index;
    u2             attributes_count;
    attribute_info attributes[attributes_count];//Code字节码信息
}

五、属性的结构

1
2
3
4
5

attribute_info {
    u2 attribute_name_index;
    u4 attribute_length;
    u1 info[attribute_length];
}

六、参考链接

Chapter 4. The class File Format

Java Class文件结构解析