14 Jun 2017
很多大型开源项目使用 make 来构建, 有时候我们想知道一个文件是怎么被构建出来的, 或者说是从哪些文件构建出来的,
知道这些对于找到程序的入口是很有帮助的. 那么该怎么做呢?
第一反应肯定是直接看 Makefile, 但是大型项目的 Makefile 都很复杂, 各种 include 和变量.
虽然 make 提供 -n 和 -p 选项, 但是因为构建命令里还会调用 make 命令,
当使用 -n 选项时, 这些命令并不会执行, 所以看不到最终执行的所有指令.
那么该怎么办呢? 其实很简单, 直接构建然后从构建输出的日志里来寻找答案,
因为 make 默认会将构建时执行的命令打印出来 (如果使用了 -s 选项或者命令加了 @ 前缀就不会输出).
下面我们以查看 OpenJDK 中 bin/java 是如何构建出来的为例来看下具体的操作:
-
首先将项目完整的构建一遍
-
将你想要追踪的文件删除, 这里我们将 bin/java 删掉
-
重新构建一遍项目同时将输出重定向到一个文件里
步骤 1 和 2 主要是为了减少构建日志输出的量从而方便搜索
-
最后就是从输出日志里搜索相关的信息
以 bin/java 为例, 我们在构建日志里搜索 bin/java, 找到如下日志:
/Applications/Xcode.app/Contents/Developer/usr/bin/llvm-gcc -o /Users/yoncise/Downloads/openjdk/build/macosx-x86_64/bin/java -m64 -Xlinker -rpath -Xlinker @loader_path/. -Xlinker -install_name -Xlinker @rpath/java -L/Users/yoncise/Downloads/openjdk/build/macosx-x86_64/lib -Wl,-all_load /Users/yoncise/Downloads/openjdk/build/macosx-x86_64/tmp/java/jli/obj64/static/libjli.a -framework Cocoa -framework Security -framework ApplicationServices -sectcreate __TEXT __info_plist ../../../../src/macosx/lib/Info-cmdline.plist \
/Users/yoncise/Downloads/openjdk/build/macosx-x86_64/tmp/java/java/obj64/main.o -pthread -lz -pthread
我们可以发现 bin/java 的构建依赖 /Users/yoncise/Downloads/openjdk/build/macosx-x86_64/tmp/java/java/obj64/main.o.
根据目录我们可以知道, 这个文件是第一次完整构建的时候生成的并不是程序的源码, 删掉它, 再重复上面的步骤构建一遍.
再一次构建完成后, 我们在构建日志里搜索 obj64/main.o 可以找到如下日志:
/Applications/Xcode.app/Contents/Developer/usr/bin/llvm-gcc -Os -fno-strict-aliasing -fPIC -W -Wall -Wno-unused -Wno-parentheses -pipe -m64 -fno-omit-frame-pointer -D_LITTLE_ENDIAN -F/System/Library/Frameworks/JavaVM.framework/Frameworks -F/System/Library/Frameworks/ApplicationServices.framework/Frameworks -I/usr/X11R6/include -D_DARWIN_UNLIMITED_SELECT -DNDEBUG -DARCH='"x86_64"' -Dx86_64 -D_ALLBSD_SOURCE -DRELEASE='"1.7.0-internal"' -DFULL_VERSION='"1.7.0-internal-yoncise_2017_06_13_23_02-b00"' -DJDK_MAJOR_VERSION='"1"' -DJDK_MINOR_VERSION='"7"' -D_LARGEFILE64_SOURCE -D_GNU_SOURCE -D_REENTRANT -DMACOSX -D_LP64=1 -I/usr/X11R6/include -D_DARWIN_UNLIMITED_SELECT -I. -I/Users/yoncise/Downloads/openjdk/build/macosx-x86_64/tmp/java/java/CClassHeaders -I../../../../src/macosx/javavm/export -I../../../../src/share/javavm/export -I../../../../src/share/bin -I../../../../src/macosx/bin -I../../../../src/solaris/bin -DPACKAGE_PATH='"/opt/local"' -DPROGNAME='"java"' -DEXPAND_CLASSPATH_WILDCARDS -DLAUNCHER_NAME='"openjdk"' -c -o /Users/yoncise/Downloads/openjdk/build/macosx-x86_64/tmp/java/java/obj64/main.o \
-DRELEASE='"1.7.0-internal"' -DFULL_VERSION='"1.7.0-internal-yoncise_2017_06_13_23_02-b00"' -DJDK_MAJOR_VERSION='"1"' -DJDK_MINOR_VERSION='"7"' ../../../../src/share/bin/main.c
至此, 我们发现 bin/java 的入口文件是 src/share/bin/main.c !
02 Jun 2017
多线程编程中, 互斥 (mutual exclusion, a.k.a. mutex) 是一个很重要的概念.
而互斥的本质就是对于临界区 (critical section) 的管理.
以前一直以为, 要实现互斥必须需要 CPU 提供相关的原语指令 (比如 Test and Set 指令) 才行.
现在发现原来有很多算法可以实现互斥.
软件方案
互斥这一问题最早是由 Dijkstra 在 1965 年提出的,
要求一个算法使得 N 台计算机在任意时刻, 有且只有一台计算机在执行临界区的代码.
N 台电脑之间通过一块共享的存储区域传递消息, 对于共享区域的读或者写是原子操作.
如果一个变量会被多个线程读写的话, 我们称之为 公共变量 (Public).
如果一个变量会被多个线程读但只会被一个线程写的话, 我们称之为 保护变量 (Protected).
如果一个变量只会被一个线程读写的话, 我们称之为 私有变量 (Private).
保护变量被多个线程读取并在一定条件下使用是没有问题的.
我们会发现, 下面提到的互斥算法从本质上来讲都是 通过使用保护变量来对公共变量的读写进行同步.
我们来看一个具体的 Java 的多线程问题: N 个线程对一个变量加 M 次 1,
如何不用任何现成的锁机制使得最后这个变量的值为 N * M.
public class MutualExclusion {
static final int N = 10;
static final int M = 10000;
volatile static int count = 0;
public static void main(String[] args) {
Thread[] threads = new Thread[N];
for (int i = 0; i < N; i++) {
Thread t = new Worker(i);
threads[i] = t;
t.start();
}
for (Thread t: threads) {
try {
t.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
if (count != N * M) {
System.out.println("count (" + count + ") != N * M (" + String.valueOf(N * M) + ")");
}
}
static class Worker extends Thread {
int id;
Worker(int id) {
this.id = id;
}
@Override
public void run() {
for (int i = 0; i < M; i++) {
this.lock();
// critical section
count++;
if (i % 1000 == 0) {
System.out.println(this.getName() + ": " + count);
}
this.unlock();
}
}
void lock() {
// TODO
}
void unlock() {
// TODO
}
}
}
Dijkstra 提出的算法
这个算法是 Dijkstra 在提出互斥问题的那篇论文里给出的:
static AtomicIntegerArray b = new AtomicIntegerArray(N);
static AtomicIntegerArray c = new AtomicIntegerArray(N);
volatile static int k = 0;
void lock() {
b.set(this.id, 0);
outer:
for (;;) {
if (k == this.id) {
c.set(this.id, 0);
for (int i = 0; i < N; i++) {
if (i != this.id && c.get(i) == 0) {
continue outer;
}
}
break;
} else {
c.set(this.id, 1);
if (b.get(k) == 1) {
k = this.id;
}
}
}
}
void unlock() {
b.set(this.id, 1);
c.set(this.id, 1);
}
为了防止因为 JMM 中的 cache 影响程序的正常运行, 所以这里使用 AtomicIntegerArray 替代 boolean[].
这里的 k 是公共变量, Dijkstra 提出的算法利用 b 和 c 这两个保护变量来进行同步.
这个算法存在一个问题, 就是 k == this.id 的线程可能会一直获得执行权, 从而导致其它线程一直等待.
后来 Knuth 等人针对这个问题对算法进行了改进, 感兴趣的可以找相关文献看看.
Perterson 算法
这个算法是解决两线程的互斥算法, 结构非常简单, 这里就直接把 Peterseon 原文里的代码摘抄过来:
/* trying protocol for P1 */
Q1 := true;
TURN := 1;
wait until not Q2 or TURN = 2;
Critical Section;
/* exit protocol for P1 */
Q1 := false.
/* trying protocol for P2 */
Q2 := true;
TURN := 2;
wait until not Q1 or TURN = 1;
Critical Section;
/* exit protocol for P2 */
Q2 := false.
Filter 算法
Peterson 在同一篇论文里把互斥算法扩展到支持 N 个线程, 这个算法又被称作 Filter 算法.
static AtomicIntegerArray level = new AtomicIntegerArray(N);
static AtomicIntegerArray lastToEnter = new AtomicIntegerArray(N - 1);
void lock() {
for (int i = 0; i < (N - 1); i++) {
level.set(this.id, i);
lastToEnter.set(i, this.id);
outer:
while (lastToEnter.get(i) == this.id) {
for (int k = 0; k < N; k++ ) {
if (k != this.id && level.get(k) >= i) {
continue outer;
}
}
break;
}
}
}
void unlock() {
level.set(this.id, -1);
}
算法中, 每个线程都有个 level, 线程需要一级一级的升级, 直到 level 达到 N
(算法中并没有真的达到 N, 但相当于升级到 N) 才获得执行权限.
在每个 level 中应用 Peterson 算法确保会有一个线程维持在该等级.
P.S. 互斥算法不仅仅上面介绍的这几种, 还有很多,
比如 Dekker 算法和面包店算法, 感兴趣的就自己查阅资料吧, 本质都差不多的.
硬件方案
解决互斥问题的关键就是对公共变量的读写进行同步, 如果硬件上能保证对一个公共变量的读写是同步的就可以解决互斥问题.
下面简单介绍几种常见的方案.
关中断
实现互斥最简单的办法就是关中断. 但是这样会导致系统的性能严重下降,
对于多 CPU 的系统关中断也不能解决问题.
Test and Set 指令
硬件提供的 TS 指令可以看做是一个函数(函数的执行不会被打断):
int TS(int* locked) {
if (*locked == 0) {
*locked = 1;
return 1;
}
return 0;
}
有了 TS 指令, 可以很容易对临界区进行管理:
while (TS(locked) == 0) {
// wait
}
// critical section
*locked = 1
对换 (Swap) 指令
和 TS 指令类似, Swap 也可以看作是一个函数:
void swap(int* a, int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
进程可以这样使用 Swap 指令:
int pi = 1; // 私有变量
while (pi == 1) {
swap(locked, &pi);
}
// critical section
*locked = 0;
操作系统教程
经典互斥算法 - 郑思遥
26 May 2017
-
Endianess
尾: 表示低的地方即低地址位
大/小: 表示权重
所以, 大尾: 权重大的字节放在低地址位. 小尾: 权重小的字节放在低地址位.
Endianness
-
分段分页
分段分页是 处理器 提供的功能.
逻辑地址 –(分段机制)–> 线性地址 –(分页机制)–> 物理地址
-
内存
内存 (Memory) 不等同于内存条, 内存条只是其中一部分. 内存还包括显存, BIOS 等等.
-
端口
处理器和外设通讯使用 IN/OUT 指令来读写相应的端口.
26 May 2017
-
C++ 有两类创建对象的方式: 1). 分配在栈上 2). 分配在堆上
class Foo: public Bar {
public:
Foo() { std::cout << "Empty constructor" << std::endl; }
Foo(const Foo&) { std::cout << "Copy constructor" << std::endl; }
Foo(const char* str) { std::cout << "char constructor: " << str << std::endl; }
~Foo() { std::cout << "destructor" << std::endl; }
};
// 对象分配在在栈上, 当离开该作用域时, 会自动 delete 该对象
Foo foo; // 调用 Empty constructor
Foo foo {}; // 同上
Foo foo = {} // 同上
Foo foo("test"); // 调用带参数的构造方法
Foo foo {"test"}; // 同上
Foo foo = {"test"}; //同上
Foo foo(); // 这是个方法声明, 不是创建对象!
// 理论上是先调用了 Empty constructor 然后再调用了 Copy constructor
// 不过一般编译器都会进行优化, 所以实际上等价于 Foo foo;
Foo foo = Foo();
Foo foo = Foo {}; // 同上
Bar bar = Foo {} // 这里编译器不会优化, bar 的实际类型是 Bar 而不是 Foo!
// 对象分配在堆上, 需要自己 delete 该对象
Foo *foo = new Foo();
Foo *foo = new Foo {}; // 同上
delete foo;
new/delete 操作的都是 pointer.
Prefer {} initialization over alternatives unless you have a strong reason not to.
Calling constructors in c++ without new
What is difference between instantiating an fooect using new vs. without
C++ default Constructor not being called
Why is list initialization (using curly braces) better than the alternatives?
-
初始化私有的 static 成员变量:
// foo.hpp
class Foo {
private:
static int bar;
};
// foo.cpp
Foo::bar = 1;
一开始觉得 foo.cpp 访问不到 bar, 觉得应该通过方法初始化,
不过转念一想, 应该和方法一样 define 是不受访问控制影响的.
static member variable when declared private
-
友元声明在 private, protected 和 public 中没有任何区别.
声明为友元的类或方法可以访问该类的私有成员.
Friend declaration in C++ - difference between public and private
-
virtual 相当于 Java 指令里的 invokevirtual.
不管一个方法是否被声明成 virtual, 它都可以被子类 override.
当调用一个不是 virtual 的方法时, 调用哪个方法是在编译时就确定的.
相反, virtual 的方法是在运行时决定调用哪个的, 即多态.
class Foo {
public:
void print() { std::cout << "Foo print" << std::endl; }
virtual void virtualPrint() { std::cout << "Foo virtual print" << std::endl; }
};
class Bar: public Foo {
public:
void print() { std::cout << "Bar print" << std::endl; }
virtual void virtualPrint() { std::cout << "Bar virtual print" << std::endl; }
};
Foo *foo = new Bar {};
foo->print(); // Foo print
foo->virtualPrint(); // Bar virtual print
C++ Virtual/Pure Virtual Explained
-
C++ 中没有 super 的关键字, 通过 namespace 调用父类的方法.
主要还是因为 C++ 支持多继承,
用 super 的话会有 MRO 的问题.
How to call a parent class function from derived class function?
-
继承时指定的 private, protected 和 public 就是对继承关系的访问控制.
Difference between private, public, and protected inheritance
-
A reference can be thought of as a constant pointer
(not to be confused with a pointer to a constant value!) with automatic indirection,
i.e. the compiler will apply the * operator for you.
但是你还是得把它当成一个对象来用.
Foo& foo = *(new Foo {});
What are the differences between a pointer variable and a reference variable in C++?
make
-
Makefile 由 rules 组成, 语法如下:
target ... : prerequisite ...
<tab>recipe
<tab>...
或者
target ... : prerequisite ... ; recipe
<tab>recipe
<tab>...
Rule Syntax
-
make 默认执行第一个名称开头不是 . 的 target.
How does “make” app know default target to build if no target is specified?
-
同一个 target 可以出现在多个 rule 中, 只要多条 rule 中的 prerequisite 有一个修改时间晚于 target
那么 recipe 就会被执行. 如果有多个 recipe, 那么只有最后出现的那条 rule 的 recipe 会被执行, 同时会抛出 warning.
但是, 上面说的情况并不是总是成立的:
target 后面如果接的是 :: 而不是 : 那么这条 rule 被称为 double-colon rule.
如果一个 target 出现在多个 rule 中时这些 rule 必须是相同的类型.
如果同一个 target 出现在多个 rule 中, 并且这些 rule 是 double-colon rule 时,
这些 rule 是相互独立的, 只要一条 rule 中的 prerequisite 修改时间晚于 target 那么 recipe 就会被执行.
Multiple Rules for One Target
Double-Colon Rules
-
通常变量赋值使用 =, 这样赋值的变量被称为 recursively expanded variables:
foo = $(bar)
bar = $(ugh)
ugh = Huh?
# 输出 Huh?
all:;echo $(foo)
GNU make 变量赋值还可以使用 := 或者 ::= (::= 是 POSIX 标准), 这样定义的变量被称为 simply expanded variables:
x := foo
y := $(x) bar
x := later
等价于
The Two Flavors of Variables
-
默认情况下 (不带 -s 选项) make 执行时, 会输出 recipe 执行的命令.
但是如果 recipe 加上 @ 前缀, 那么命令本身就不会被输出, 对于 echo 这种命令很有用.
Recipe Echoing
23 May 2017
Dump 就是对程序运行时内存上的信息进行转储, 让我们可以查看程序当时的运行情况.
Dump 对于调优和排错是非常有用的工具.
Heap Dump
Java 运行时对象分配在堆内存上, Heap dump 就是对堆内存进行转储.
生成
Heap dump 的生成有两种方式:
1) 运行 Java 程序时添加 -XX:+HeapDumpOnOutOfMemoryError 选项,
这样当程序发生 Out of Memory 错误时就会自动生成一份 Heap dump.
2) 使用 jmap 工具生成. 首先我们用 jps 找到程序的 pid (严谨点说其实是 lvmid), 然后运行:
jmap -dump:live,format=b,file=heap.bin <pid>
分析
可以使用 Java 自带的 jhat 工具来分析 Heap dump:
等待一会, 就会提示
Started HTTP server on port 7000
Server is ready.
这时候浏览器中访问 127.0.0.1:7000 就可以了.
但是, jhat 在分析较大的 Heap dump 时效率比较差,
所以推荐使用 eclipse 提供的 Memory Analyzer (MAT) 来分析.
Thread Dump
Thread dump 转储的是线程相关的内存数据 (例如该线程的调用栈).
Thread dump 有时候也被称为 javacore, 不过好像 javacore 是 IBM 虚拟机才有的.
生成
可以使用自带的 jstack 生成 Thread dump:
jstack <pid> >> thread.dump
分析
Thread dump 就是个文本文件格式, 直接打开查看就可以了.
Intellij IDEA 提供 Stacktrace 的分析, 我们可以用它来分析 Thread dump,
这样可以方便的知道某个线程运行到哪里.
打开 Intellij IDEAD -> Analyze -> Anaylyze Stacktrace...,
把 Thread dump 的内容复制粘贴进去, 确认即可.
Core Dump
上面提到的 Heap dump 和 Thread dump 都是和 Java 直接相关的,
Core dump 则是操作系统提供的, 所有程序在意外退出时, 操作系统都可以生成 Core dump.
Core dump 包含了程序运行时的所有内存信息,
所以我们可以使用 Core dump 同时分析堆内存和运行时栈.
生成
默认操作系统是不生成 Core dump 的, 我们需要先打开:
# 如果你用的是 bash
ulimit -c unlimited
# 如果你像我一样用的是 zsh
limit coredumpsize unlimited
ulimit/limit 是设置 dump 的大小的, 默认为 0 也就是不 dump.
我们可以使用下面的命令来查看当前设置的大小:
# 如果你用的是 bash
ulimit -c
# 如果你像我一样用的是 zsh
limit coredumpsize
确认打开后, 我们可以使用 kill -ABRT <pid> 来生成 Core dump.
不过需要注意的是, 使用这种方法只有在当前 Terminal 下运行的 Java 程序才能生成 Core dump.
也就是说, 你必须在打开了 Core dump 的 Terminal 下运行 Java 程序,
这样 kill -ABRT <pid> 才会生成 Core dump.
如果你 Java 程序运行在一个没有打开 Core dump 的 Terminal 下,
那么即使你的 kill -ABRT <pid> 运行在打开了 Core dump 的 Terminal 下,
这时候 Core dump 也是不会生成的.
我们也可以使用 gcore 来生成生成 Core dump. 使用这个方法就无所谓你有没有使用
ulimit/limit 打开 Core dump 了.
sudo gcore <pid>
Mac 下 Core dump 生成在 /cores/ 文件夹下.
分析
我们可以使用 gdb 来分析 Core dump 文件.
Java 自带的 jstack 和 jmap 也可以用来分析 Core dump:
jstack <executable> <core dump file>
jmap <executable> <core dump file>
这里的 <executable> 指的是你运行 Java 程序时使用的 java, 一般可以用 $JAVA_HOME/bin/java 代替.
如果你指定的 java 和你运行用的 java 不是同一个版本, 就会抛出 sun.jvm.hotspot.debugger.UnmappedAddressException.
另外你使用的 jstack 和 jamp 也需要是相应的版本, 否则会提示 Can't attach to the core file.