SPOJ SHORTEN
这半年一直着迷于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/
Jos
花了一个月做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
Load
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
Permutation
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
Books
上个学期读的课外书:
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总结贴出来吧.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，记录自己学习轨迹。
偶尔改变下生活，挺不错的。
malloc笔记
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.
Executable and Linkable Format
花了几天学习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]
Tarjan's off-line least common ancestors algorithm
problem 21-3 of CLRS.
See wiki.
