这半年一直着迷于SPOJ SHORTEN,它有个很好听的名字Code golf, 即源代码越少得分越高.

首先于2013/10月开始在SPOJ classical写了一个月的题目,主要是C了.
然后是SPOJ challenge,挺有意思,主要是时间效率的比较, 当然也有代码比较的.

偶然的机会在SPOJ的主页看到了SPOJ SHORTEN,当时很好奇,发现是CODE GOLF的竞赛,里头有各种奇怪的语言,J(第一次知道这个语言是在projecteuler, 好久没在这里活跃了)、K、BrainFuck等.
因为自己对awk有点了解,所以自己用AWK写了几道题,发现超有意思。

于是边温习AWK,边做题,越发不可自拔. 从去年12月份开始,疯狂刷题,努力缩短代码.每发现个技巧,便能缩短个把字符.要代码越短,需要不同的角度看待问题,然后实现这个算法,得到最优的.

经过两个月的奋战,在SPOJ SHORTEN排名第3了,对awk有一定程度的熟悉了,当然还有Python和C，成就感无疑是第一位的.

期间认识几个牛人：mitchs、hallvaboo、piotr和jander等.
另外几个自豪的题目: SPIRAL, RPN, SUDCHECK, GCD4.

另外这10天在golf.shinh.org刷了一遍gxawk.

哦,该写论文了..

引用：
1. www.spoj.com/SHORTEN
2. www.spoj.com
3. golf.shinh.org
4. en.wikipedia.org/wiki/Code_golf
5. http://sites.google.com/site/codegolfingtips/Home
6. http://www.spoj.com/SHORTEN/embed/links/


 

1. Lightbot2 http://www.u148.net/game2/2011/12/Light_Bot_2/
2. 引盒入洞 http://orbox.info/
3. 引球入洞 http://www.isoball.com/
4. 引砖入洞 http://www.u148.net/game/month_0710/bloxorz/

花了一个月做JOS[1], 阅读xv6[2]和linux-0.11[3], 收获颇多.
MIT的计算机和Linus果然名不虚传(即便只是linux-0.11).

## 读源码也是一种乐趣.

-----------------------------------
JOS

它分为七个实验:
1.启动.
2.内存管理.
3.用户环境
4.可抢断多任务
5.文件系统
6.网络驱动
7.A shell

============================
Lab 1: Booting a PC.
计算机启动->BIOS->引导启动程序->内核, 也可见[4].

引导启动程序主要干两件事:
1.将处理器从实模式转换到32位保护模式. (boot/boot.S)
2.从硬盘读内核, 将控制权转给内核. (boot/main.c)

内核获得控制之后, 由于代码还在低地址运行需要开启分页机制, 然后通过间接调用跳到
高地址的C初始化代码. (kern/entry.S, kern/entrypgdir.c)

内核初始化(kern/init.c):
1)console: keyboard/vga/serial. (kern/console.c)
2)目前直接monitor.(kern/monitor.c) (后序实验初始化, 如内存, 文件系统等)

Challenges:
1) Enhance the console, see [3] "字符设备驱动程序"一章.

Summary: It took me much time to review not-so-familiar knowledge, i.e.
assembly instructions, 80x86 registers, and gdb.


============================
Lab 2: Memory Management.

Part 1: 物理内存管理. (kern/pmap.c)
1)页面的初始化.
2)页面的分配和回收.

Part 2: 虚拟内存. (kern/pmap.c)
1)虚拟地址/线性地址/物理地址三者之间的转换.
2)页表的管理, 插入和删除页面时页目录和页表的更新.

Part 3: 内核地址空间
1)JOS 内存layout. (inc/memlayout.h)
2)内核的保护. (页表项, 段选择符)

Challenges:
1) Reducing pages for KERNBASE mapping, see [2](entrypgdir in main.c).
2) Malloc/free, see [2](umallo.c) and [4](lib/mallo.c).

Summary: I'm more clear about these three addresses and memory
layout/allocating/freeing, etc.


============================
Lab 3: User Environments.

Part A: 用户环境和异常处理

JOS的用户环境类似于Unix进程. (kern/env.c)
1) 内核需要为用户环境保存的信息. (env_id 含有个有趣的部分)
2) 分配用户环境空间, 创建和运行用户环境. (由于没有文件系统, JOS嵌入binary到
        kernel)

异常处理, 设置中断描述表IDT. (kern/trap.c, kern/trapentry.S)

Part B: 页故障, 断点和系统调用
页故障, CR2. (kern/trap.c)

断点, 主要用来user-mode panic. (kern/trap.c)

系统调用. (kern/syscall.c)
1)参数的传递是通过5个registers(edx, ecx, ebx, edi, esi), eax保存系统调用号.

Challenges:
1) Clean trapentry.S up, we can script it, see [4](vectors.pl).
2) Support 'continue', set TF and RF of EFLAGS, then go back user.
3) Sysenter/sysexit, see [5].

Summary: Trap, exception, and syscall; kernel protection; kernel/user address
space switching.


============================
Lab 4: Preemptive multitasking

Part A: 多核支持和合作式多任务

多核支持: (kern/lapic.c) ## 这部分没细看
1)BSP(bootstrap processor) 激活APs(application processors)
2)Per-CPU 状态和初始化. (Kernel stack, tss 和 tss 描述符, 当前env, registers,
        idle env)

Locking(kern/spinlock.c), Big Kernel Lock.

Scheduling(kern/sched.c), Round-Robin.

System calls for 创建用户环境: (注意权限和地址的合法性判断)
1) sys_exofork, 类似Unix fork, 创建新用户环境, child 被标记不可运行.
2) sys_env_set_status, 设置可运行或不可运行.
3) sys_page_alloc, 分配新页面.
4) sys_page_map, 复制一页面的映射.
5) sys_page_unmap, unmap 一页面.

Part B: Copy-on-Write Fork

用户级页错误处理函数:
1) 设置页错误处理函数.
2) 异常栈(Exception stack).
3) 调用页错误处理函数.
4) Entrypoint. ## 有点难且有趣

实现CoW Fork: ## 难点: 理解vpt/vpd
1) 设置页错误处理函数.
2) sys_exofork 创建新env.
3) 为父/子env 设置cow-or-writable 页面为 cow, 除了异常栈.
4) 为子env设置页错误处理函数.
5) 标记子env可运行.

Part C: IPC

1) send/receive.
2) lib wrapper.

## 令我十分吃惊的是primes.c, 它用一种新颖的思路实现prime sieve.

## 这部分Challenges十分有趣, 花了我很多时间, 尤其是power-series.
Challenges:
1) Drop big kernel lock, see [2] and [4].
2) Add a scheduling policy, well, todo.
3) SFORK, easy but heed the global ``thisenv'' pointer.
4) Un-loop ipc_send, the only way I can occur is the block-wait.
5) Matrix multiplication, using sfork.
6) Power series, GOOD ONE, also see [6](Python implementation).
7) "Improving IPC by Kernel Design", so many tricks :-), todo.

Summary: Other CPUs are activated by BSP; Locking and Scheduling both are big
chunks; COW fork is easy to say, but seem tricky to implement; Page Fault is
also tricky; IPC...

============================
Lab 5: File System
## 主要工作是看代码.

文件系统在磁盘上数据结构:
1) 区(Sector)与块(Block)
2) 超级块(Superblock)

3) 块位图(block bitmap)
4) 文件元数据(File meta-data)

文件系统组成部分:
1) 磁盘访问, see also [4]'s "块设备驱动程序" 一节.
2) 块缓存的管理.
3) 位图的管理.
4) 文件操作.

该文件系统是由一个专门env来实现, JOS 通过IPC的方式让其它env来使用该文件系统.

Spawning processes
## 这段代码还挺有意思.
##

Challenges:
1) Crash-resilient, see [2]
2) Inode, see [2]
3) Unix-style exec, tricky as the kernel is needed to do the entire replacement.
4) Mmap-style, no that hard.

Summary: Delving into this simple FS, now I understand FS more clearly.


============================
Lab 6: Network Driver

## 本实验主要阅读Intel的8254x手册, 以及阅读源码(略过lwIP).

## 之前我一直使用从官方编译的QEMU, 这个实验要使用6.828的版本便于调试(见JOS-tool).

## 这个实验开始grade-test改用python实现, 这可以说是一大改进, 因为可以部分测试了,
## 十分方便.

该网络驱动分为四个部分:
1) 核心网络服务环境
2) 输入环境
3) 输出环境
4) 定时器
## 主要完成2/3/4.

Part A: 初始化和网络包的传输

网卡识别与初始化:
1) PCI接口
2) 内存映射I/O
3) DMA

包的传输, 传输队列的初始化与更新, 注意队列满的处理.

Output 环境, 注意等待的情况.

Part B: 包的接收和Web服务器

包的接受, 类似于传输的情况, 接收队列的相关处理.

Input 环境, 注意IPC 页面的竞争.

Web 服务器, 一个简单网页服务器的实现.

Challenges:
1) Reading MAC address from EEPROM, from the 8254x manual, there are two ways to
         do this:EEPROM Read register and control register. But the first doesn't work,
         the second implementation is stolen from linux-2.6.38.
2) Zero-copy, messy, see [7].
3) For other challenges, I'm sorry, either you're hard or I'm busy.

Summary: I'm forced to read the Intel's 8054x manual, and now feel comfortable
about hardware's details. Networking seems to be interesting.


============================
Lab 7: Final Project
1) 共享库代码, PTE_COW.
2) 键盘接口, see [3].
3) Shell, see also [2].

Challenges:
1) The project, 我还不够优秀来完成这个Project, 没有足够好的想法。

Summary: This lab except the challenge requires the least code. If I have much
time, I would want to see the bash source.


============================
Needed requirements:
1) OS concept
2) 80x86 concept
2) Assembly(gas)/C/Inline_assembler
3) GDB
4) ELF, part.

Optional requirements:
1) Hardware programming, keyboard/console/disk/network etc.
2) Make, Makefile of course.
3) Shell, grade test for lab1-5.
4) Python, grade test for lab6-7. ## It took me 1/2 day to understand, and
        another 1/2 to deal with the qemu-bug.
5) Qemu, well I didn't dive into it.
6) Gcc/ld, ditto.

Tools I use:
## well, it could be better to write another article.

1) Vim. You need a damn great editor and make full use of it. For vim, I heavily
        use cscope, marks, tabs, global/substitute, etc, and good plugins[8].
2) Tmux. A terminal multiplexer (Before I used GNU screen).

-----------------------------------
Xv6
阅读[2]给的书和源码.

-----------------------------------
Linux-0.11
阅读[3]和linux-0.11源码.



引用: ## JOS主页本身含有大量好资源.
[1] MIT-JOS, http://pdos.csail.mit.edu/6.828/2011/overview.html
[2] Xv6, http://pdos.csail.mit.edu/6.828/2011/xv6.html
[3] Linux0.11, <<linux内核完全剖析>> 赵炯
[4] Booting, http://www.ruanyifeng.com/blog/2013/02/booting.html
[5] Sysenter, http://articles.manugarg.com/systemcallinlinux2_6.html
[6] Power-series, https://github.com/pdonis/powerseries
[7] Zero-copy, http://www.ibm.com/developerworks/library/j-zerocopy/index.html
[8] Vim-good-plugins, https://github.com/carlhuda/janus

Let's dive into load average.

Sample output of `uptime':
 18:38:47 up 28 days,  9:15,  9 users,  load average: 2.63, 2.67, 2.50
当前时间, 系统运行时间, 目前登录用户数, 过去1/5/15 min的平均负载

什么是load average?  
来自于uptime(1)
System load averages is the average number of processes that are either
        in a runnable or uninterruptable state.  A process in a runnable  state
        is  either using the CPU or waiting to use the CPU.  A process in unin‐
        terruptable state is waiting for some I/O access, eg waiting for  disk.
        The  averages  are  taken over the three time intervals.  Load averages
        are not normalized for the number of CPUs in a system, so a load  aver‐
        age  of 1 means a single CPU system is loaded all the time while on a 4
        CPU system it means it was idle 75% of the time.

Kernel magic:
source code in kernel/sched.c, include/linux/sched.h

/* calc_global_load function */
3252   avenrun[0] = calc_load(avenrun[0], EXP_1, active); /* 1min */
3253   avenrun[1] = calc_load(avenrun[1], EXP_5, active); /* 5min */
3254   avenrun[2] = calc_load(avenrun[2], EXP_15, active);/* 15min */

3256   calc_load_update += LOAD_FREQ;

而calc_load 的定义:

3046 static unsigned long
3047 calc_load(unsigned long load, unsigned long exp, unsigned long active)
3048 {
3049   load *= exp;;
3050   load += active * (FIXED_1 - exp);
3051   load += 1UL << (FSHIFT - 1);
3052   return load >> FSHIFT;
3053 }

故计算公式:
load(t1) = (load(t0)*exp + active*(FIXED_1-exp)) >> FSHIFT

exp 有EXP_1, EXP_5, EXP_15, 对应1min, 5min, 15min.
但EXP_*, FSHIFT, FIXED_1 又是什么？

/*
* These are the constant used to fake the fixed-point load-average
* counting. Some notes:
*  - 11 bit fractions expand to 22 bits by the multiplies: this gives
*    a load-average precision of 10 bits integer + 11 bits fractional
*  - if you want to count load-averages more often, you need more
*    precision, or rounding will get you. With 2-second counting freq,
*    the EXP_n values would be 1981, 2034 and 2043 if still using only
*    11 bit fractions.
*/
125 #define FSHIFT    11    /* nr of bits of precision */
126 #define FIXED_1   (1<<FSHIFT) /* 1.0 as fixed-point */
127 #define LOAD_FREQ (5*HZ+1)  /* 5 sec intervals */
128 #define EXP_1   1884    /* 1/exp(5sec/1min) as fixed-point */
129 #define EXP_5   2014    /* 1/exp(5sec/5min) */
130 #define EXP_15    2037    /* 1/exp(5sec/15min) */

由此可知真正的计算公式:
load(t1) = load(t0) * exp_m + active * (1 - exp_m)
其中exp_m 对应于EXP_M, 是小于1的常量, 称之为负载因子, 作为前次负载的比重。

EPX_* 是如何计算的？

代码实现的exp_m = exp(-load_freq/m), load_freq 为更新频率
由于每隔5s进行负载计算的更新, 过去 m min的负载因子
exp_m = exp(-5s/60ms), 所以
EXP_M = exp_m << FSHIFT
                        = 2**11 * exp(-5/60m)
                        = 2**(11 - 5*log2(e)/60m)

EXP_1 = 2**(11 - 5*log2(e)/60) = 1884
同理EXP_5 = 2014, EXP_15 = 2037

reference:
http://en.wikipedia.org/wiki/Load_(computing)
http://www.teamquest.com/pdfs/whitepaper/ldavg1.pdf

Methods of listing all permutations of a list:
1. Recursive algorithm
2. Lexicographic order
3. Johnson-Trotter algorithm
4. B. Heap's algorithm
references:
http://en.wikipedia.org/wiki/Permutation
http://www.cut-the-knot.org/do_you_know/AllPerm.shtml
http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml

上个学期读的课外书:

0. <<一个数学家的辩白>>, 哈代, << A Mathematician's Apology>>, G.H.Hardy, 作者从自己的角度谈论了数学中的美,http://zh.wikipedia.org/wiki/一个数学家的自白

1. <<动物庄园>>, 乔治奥威尔， <<Animal Farm>>, George Orwell, 描述了一场“动物主义”革命的酝酿、兴起和最终蜕, http://baike.baidu.com/view/155123.htm

2. <<1984>>, 乔治奥威尔， <<Nineteen Eighty-Four>>, George Orwell, 刻划了一个令人感到窒息和恐怖的，以追逐权力为最终目标的假想的极权主义社会, http://baike.baidu.com/view/416121.htm

3. <<麦田里的守望者>> 塞林格, <<The Catcher in the Rye>>, J.D.Salinger, 一个16岁少年被学校开除后在纽约游荡的三天里经历与感受, http://baike.baidu.com/view/558175.htm

4. <<瓦尔登湖>> 梭罗, <<Walden>>, H.D.Thoreau, 作者与大自然水乳交融的田园生活, http://baike.baidu.com/view/152609.htm

5. <<霍乱时期的爱情>>, 马尔克斯, <<El amor en los tiempos del cóler>> (<<Love in the Time of Cholera>>), Gabriel GarcíaMárq,一段长达半个多世纪的三角恋, http://baike.baidu.com/view/533323.htm

6. <<百年孤独>>, 马尔克斯, <<Cien años de soledad>>, Gabriel GarcíaMár, 一个家族七代人的故事, http://baike.baidu.com/view/37227.htm

虽然有点晚，还是整理下把之前写的2012总结贴出来吧.2012 总结

一年的学习记录：

1月上旬学了算法导论NP复杂度和渐进分析，下旬回家

2月上半月screen的用法, lua简单学习(awesome的配置文件)，

2月下半月，3-4月决定,打印文章，教室自习，静心看文章.

4月底放弃看文章，基于以下原因：
  i) 这2个月来，感觉理论东西有点虚，感觉没进步，除了英文阅读能力得到点提高，
        想法都被实现.
  ii)自身的技术没怎么提高，我不读博，不打算搞科研，只想学点技术，提高自己的能力,
        同时做点项目，积累经验。

所以换了老师（当时老师是纯文章，没项目），新老师方向跟linux有关，我比较感兴趣。
另外此时开始做projecteuler.net里头的题目，同时学习python;
实验室发电脑，折腾了gentoo, screen 换到 tmux.

5-10月跟新老师做些虚拟化调度器,同步,并行程序的学习。
空余时间学了些命令与python，做些euler题和pythonchallenge.com。

5月学习linux kernel cfs调度算法，开始接触内核代码，《linux kernel development》。
 代码真是看了一遍又一遍。另5月1号7天一直研究diophantie equation,
 http://projecteuler.net/problem=261，可当时没做出来。

6月主要还是看调度/同步/锁的文章,同时开始接触xen, 并行编程mpi/openmp。

7月xen的使用, openmp 同步机制的实现, futex。
还花了10天学习《Fundamentals of Queueing Theory》(哎，大部分内容现在忘了一干二净)。

8月上旬回家。

8月下旬-10 学习xen虚拟化的设计原理和代码阅读。
书籍《The Definitive Guide to the Xen Hypervisor》。另外学习net filter, gnuplot.

11-12月 老师开始不管我，我也没找他，自己学习些技术。
折腾了mentohust, ELF, 重新看了OPENMP, FUTEX, 还有PTHREAD。

现在我已经游离了, 原因:
 i)交流能力差: 我对这个只能慢慢提高了，先把普通话说好，以后多写写,理清思路，然后
尝试对自己说。
 ii)不够FOCUS ，不够上心, 不够积极: 是的，对交代的任务基本完成之后的多余时间基本
用来学了些自己喜欢整的东西，不会去想科研。


这一年来：
平时比较少玩桥牌了，虽然中途有几段时间又迷上了。

开始重拾对数学的兴趣，《一个数学家的辩白》，《古今数学思想（一）》,
对数论学习的比较多（euler工程）。

开始关注小说和哲学了。
9月份开始，每晚会花上1-2个小时看些小说，到现在为止，看了以下书
《瓦尔登湖》, 《麦田里的守望者》，《霍乱时期的爱情》,《动物庄园》，《1984》。

开始会享受音乐和电影，虽然电影大概是一礼拜一部.

开始思考人生了, 生命意义，目标，未来计划.

一直以来都会锻炼身体，2个月前办了张健身卡，现在一个礼拜基本有5天去健身，
每天90分钟左右,挺好的。

总结：
学到比较多东西，虽然有点杂乱;日子充实,偶尔寂寞.

学到的知识不用就会被遗忘, 而且没写blog记录。以后多多写些blog，记录自己学习轨迹。

偶尔改变下生活，挺不错的。

glibc malloc (aka ptmalloc2)

resource:
http://gee.cs.oswego.edu/dl/html/malloc.html
malloc/malloc.c from http://ftp.gnu.org/gnu/glibc/glibc-2.15.tar.gz

基本结构:

	

	struct malloc_chunk {

	

	  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */

	  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */

	

	  struct malloc_chunk* fd;         /* double links -- used only if free. */

	  struct malloc_chunk* bk;

	

	  /* Only used for large blocks: pointer to next larger size.  */

	  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */

	  struct malloc_chunk* bk_nextsize;

	};

细节：

• 已分配的chunk: `boundary tag'方法来管理内存.

	    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	      |             Size of previous chunk, if free                 | |

	      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	      |             Size of chunk, in bytes                       |M|P|

	      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	      |             User data starts here...                          .

	      .                                                               .

	      .             (malloc_usable_size() bytes)                      .

	      .                                                               |

	nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	      |             Size of chunk                                     |

	      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   "chunk" 由malloc 代码使用, "mem" 是返回给用户的，"nextchunk" 是下一连续的块,
   chunk 总是双字对齐的,所以mem也是双字对齐.

•  未分配的chunk: circular doubly-linked lists

	    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	      |             Size of previous chunk                            |

	      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	    `head:' |             Size of chunk, in bytes                   |P|

	      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	      |             Forward pointer to next chunk in list             |

	      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	      |             Back pointer to previous chunk in list            |

	      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	      |             Unused space (may be 0 bytes long)                .

	      .                                                               .

	      .                                                               |

	nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	    `foot:' |             Size of chunk, in bytes                     |

	      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

     注意到当前chunk 的`foot'  实际上是代表下一块的`prev_size'.

由于chunk size是双字的倍数, size的最低三比特分别用来表示:
   P (PREV_INUSE) (最低比特):
      1 前一块被分配, 此时pre_size未被使用,从而相当于给前一块,故overhead是1字(而不是2字)
      0 未分配, 此时size的前一字表示前一块的大小
   M (IS_MMAPPED):  由mmap 分配
   NON_MAIN_ARENA: 每thread 都有一个arena linked-list, 第一个是main_arena
      (malloc_state 结构, 详细见代码)

算法主要内部结构：
1. regular bins
An array of free chunks headers, 每个bin是双链表, size-order(small bins 相同
  大小), 先进先出原则(freed chunk 放到最前面, 分配从最后开始)，128个bins:
    64 bins of size       8
    32 bins of size      64
    16 bins of size     512
     8 bins of size    4096
     4 bins of size   32768
     2 bins of size  262144
     1 bin  of size what's left
对于前64 bins, 即size < 512, 每个bin是同大小的块集合, 称之为smallbins;
其余为largebins, 且已排序.
布局：16 - 24 - 32 -..- 512 - 576 - 640 ---

2. unsorted chunks
所有split剩下块，返回块的集合.
在这些块放入regular bins之前malloc会有一次尝试对其分配

3. top
Top-most available chunk. (Wilderness preservation)
如果bins分配失败，从这里分配，否则尝试mmap, 再者通过MORECORE申请内存，
增加top.
see sbrk(2)

4. binmap
加快largebin的索引

5. fastbin
An array of lists 最近被释放小块(MAX_FAST_SIZE）, single-link, LIFO

malloc：
exact-fit, last_remaider chunk, best-fit. (Locality preservation)
malloc -> public_mALLOc -> _int_malloc
1. fastbins if any, returns
2. smallbins if any, returns
3. largebins if has fastchunks, consolidate fastchunks
4. unsorted-bin 寻找exact-fit 或 last_remaider chunk, if any returns
   否则将块放入regular bins(largebins need to be sorted)
5. largebins if any, split or exhaust, and returns
6. best-fit if any, split or exhaust, and returns
7. top if available split and returns
8. if has fastchunks, consolidate, then go to step 4
9. calls sYSMALLOc,

sYSMALLOc:
1. mmap if condition is satisfied, if ok then returns
2. not main_arena, try grow_heap and new_heap, otherwise try mmap if mmap is not tried
3. main_arena, MORECORE, otherwise mmap and do some adjustments and fenceposts.
4. finally, do the allocation.

free:
free -> public_fREe -> _int_free
1. if <fastsize, put into fastbin
2. if mmapped, munmap
3. if not mmapped, consolidate backward/forward, put into the unsorted bin or top
4. if freeing a large space, possibly consolidate fastchunks, sYSTRIm

For other similiar routines, says realloc/mallopt, see the implementations for the
details.

花了几天学习ELF格式, 之前的许多疑惑已经解开了.

主要学习资源是 http://www.acsu.buffalo.edu/~charngda/elf.html

可执行文件如何被执行？
1.sys_execve 处理execvc系统调用,调用do_execve
2.do_execve 打开该可执行文件,做些准备工作,然后调用search_binary_handler
3.search_binary_handler 确定可执行文件的类型(比如elf, 脚本), 调用相应的处理函数,这里是load_elf_binary
4.load_elf_binary将该执行文件载入内存.分配内存段,padzero BSS.
5.如果是动态链接, 该程序含有INTERP段(包含解释器的全路径,通常是ld.so), 调用load_elf_interp 载入该解释器
6.load_elf_binary最终调用start_thread, 将控制交给解释器或该用户程序

ld.so ?
ld.so 是动态链接器 linker/loader (编译时链接器ld叫做链接编辑器,"link editor"),干以下事情：
1.分析用户程序的DYNAMIC段, 确定所需要的依赖
2.找出并载入这些依赖,递归分析它们的DYNAMIC段以确定是否需要更多的依赖
3.进行任何必要的重定向工作来绑定这些对象
4.调用初始化函数
5.将控制权交给程序

ld.so 如何工作？
ld.so 自己当然不能是动态链接的. 入口地址是_start (ld -verbose | grep ENTRY), 然后调用_dl_start 载入自己的依赖
_dl_start做了什么事情？
1.分配初始TLS（thread local storage) 并且初始化线程指针如果需要的话（这些是ld.so自己的,不是用户程序的)
2.调用_dl_sysdep_start, 里头调用dl_main
3.dl_main 做了主要工作：
process_envvars 处理 LD_* 环境变量
检查程序的DYNAMIC段的NEEDED字段以确定依赖
_dl_init_paths 初始化动态链接库寻找路径
_dl_map_object_from_fd载入动态库，设置读写权限，zeroes out BSS段
_dl_relocate_object 运行时重定向

_dl_start返回后,调用_dl_start_user
1._dl_init_internal, 调用call_init执行每个被载入库的初始化函数（DYNAMIC INIT类型）,
2.最后将控制权交给程序的入口地址（通常是.text的初始地址）,其中将结束函数_dl_fini作为参数。

tips: 设置LD_DEBUG=all，然后运行程序以获得ld.so所采取的动作


.init, .fini, .preinit_array, .init_array and .finit_array

.init 和.fini 包含初始化和结束代码
如果gcc编译的话, .init 和.fini代码大致如下：
0000000000400510 <_init>:
 400510:       48 83 ec 08               sub    $0x8,%rsp
 400514:       e8 c3 00 00 00          callq  4005dc <call_gmon_start>
 400519:       e8 52 01 00 00          callq  400670 <frame_dummy>
 40051e:       e8 ad 03 00 00          callq  4008d0 <__do_global_ctors_aux>
 400523:       48 83 c4 08               add    $0x8,%rsp
 400527:       c3                              retq

0000000000400908 <_fini>:
 400908:       48 83 ec 08               sub    $0x8,%rsp
 40090c:       e8 ef fc ff ff               callq  400600 <__do_global_dtors_aux>
 400911:       48 83 c4 08               add    $0x8,%rsp
 400915:       c3                              retq

各只有一函数_init/_fini, 都是编译时生成的。
Glibc 为_init/_fini提供自己的开始与结束代码文件,依赖于编译参数（gcc -dumpspec).一般情况下是crti.o 开始，crtn.o 结束。
例外如果没有使用-shared，glibc 总是包含crt1.o, crt1.o含有.text的开始函数_start.
最后包括crtbegin.o,crtbeginS.o,或crtbeginT.o，取决于 -static or -shared

比如如果一个程序使用动态链接，没有profiling, 没有 fast math optimization 来编译，那么链接会以下顺序包括以下文件：
1. crt1.o
2. crti.o (call_gmon_start__)
3. crtbegin.o (frame_dummy,__do_global_ctors_aux)
4. user's code
5. crtend.o (__do_global_dtors_aux)
6. crtn.o

__do_global_ctors_aux 调用所有被标记 __attribute__ ((constructor)) 的函数, 它们存在.ctors区; 同样__do_global_dtors_aux 调用所有被标记 __attribute__ ((destructor)) 的函数 它们存在.dtors区.:

executed sequence:
.preinit_array -> .init -> .init_array -> main -> .finit_arary -> .fini

最好不要放代码到.init区, e.g.
void __attribute__((section(".init"))) foo() {
        ...
}
因为这样会导致__do_global_ctors_aux 不会被调用(自己试试）
同样不要加代码到.fini，会导致segmentation fault

_start ?

_start 是glibc 代码，被编译成crt1.o, 在编译时被链接到用户程序的二进制代码
_start 总是被放在.text的开始处，ld 指定_start的地址为入口地址，所以总是可以保证最开始运行_start (编译时可以通过-e选项指定不同的初始地址）
_start 设置好参数，再调用__libc_start_main
__libc_start_main( int(*main) (int, char **, char **),
                              int argc,
                              char *argv,
                              int (*init) (int, char **, char **),
                              void (*fini) (void),
                              void (*rtld_fini) (void),
                              void *stack_end)
)

__libc_start_main 干了以下事情：
1. 设置好argv和envp
2. __pthread_initialize_minimal 初始化线程本地存储(TLS)
3. 设置好线程栈保护
4. 注册动态链接器的解析器（rtld_fini)，如果有的话(使用__cxa_atexit)
5. __libc_init_first 初始化glibc
6. 注册 __libc_csu_init(fini）
7. __libc_csu_init (init):
        1).preinit_array
        2).init
        3).init_array
8. 设置好线程释放/取消所需的数据结构
9. main
10. exit

如果main最后一代码是return XX, XX 会传给exit. 如果没有或只是return，undefined.
当然如果用户程序自己调用了exit/abort， exit 会被调用.

如果一个程序没有main, 将会看到``undefined reference to main''的错误。
如何找到一个可执行二进制文件的main地址？
1. 32-bit x86, 第一个参数是最后一个压入栈，
   objdump -j .text -d a.out | grep -B2 'call.*__libc_start_main' | awk '/push.*0x/ {print $NF}'
2. 64-bit x86, 第一个参数存在RDI寄存器，
   objdump -j .text -d a.out | grep -B5 'call.*__libc_start_main' | awk '/mov.*%rdi/ {print $NF}'


重定向
连接时重定向(链接编辑器ld, .rel.text or .rela.text)/动态时重定向(ld.so, DYNAMIC)
_GLOBAL_OFFSET_TABLE_, .got.plt section, DYNAMIC segment

RUNTIME RELOCATION 重定向
prelinked
R_X86_64_RELATIVE => base + *(base + relative) 存在 base + relative
R_X86_64_GLOB_DAT => base（含该符号ELF的基址） + Symbol Value + Addend
R_X86_64_JUMP_SLOT => same with R_X86_64_GLOB_DAT
R_X86_64_COPY => 与R_X86_64_GLOB_DAT相结合

.plt/.got  
动态链接器默认是懒惰型重定向，即要用到某符号时才重定向
1) PLT(Procedure Linkage Table), 每个记录对应一个输出函数.
比如call  function_call_n # 对应地址是PLT[n+1]
在i386体系中,代码类似于：
PLT[n+1]:jmp *GOT[n+3]
                 push #n
                 jmp PLT[0]

第一次调用时，GOT[n+3] 指向PLT[n+1]+6, 即push #n、然后jmp PLT[0], PLT[0]根据压入栈的n来解决该符号地址，再将该地址填入GOT[n+3].
PLT[0]: push &GOT[1]
            jmp  GOT[2]   # point to resolver()
2) GOT (Global Offset Table)
        开始3条是特殊用途,后面M条是函数PLT，再D条是全局数据
        GOT[0] = linked list pointer used by the dyn-loader
        GOT[1] = pointer to reloc table for this module
        GOT[2] = pointer to the fixed/resolver code, located in the ld.so
        GOT[3..3+M] = indirect function call helper, one per imported function
        GOT[3+M+1..end] = indirect pointers for global data references, one per imported global

每个库和可执行文件都有自己的PLT/GOT

其他详细请看[1]

resources:
http://www.acsu.buffalo.edu/~charngda/elf.html[1]
http://netwinder.osuosl.org/users/p/patb/public_html/elf_relocs.html[2]
PIC / noPIC: http://en.wikipedia.org/wiki/Position-independent_code[3]
GNU HASH: https://blogs.oracle.com/ali/entry/gnu_hash_elf_sections[4]
 

problem 21-3 of CLRS.

See wiki.