Posted on | In

目录

基本编译链接流程

  • 编译并输出汇编代码
    • g++ -S lib.cpp -o lib.s
  • 打包成ELF可重定位文件 ELF TYPE= ET_REL 即.o文件
    • g++ -c lib.s -o lib.o
  • 链接到动态库或者可执行文件
    • g++ lib.o -o a.out
    • g++ -shared lib.o -o a.out
Read more »

Posted on | In

目录

选项说明

  • -rdynamic

    • 该选项指示链接器添加所有的符号到动态符号表, 不仅仅是用到的部分
    • 在INTEL X64 linux gcc-6 未测试出该选项有否的异同 (也可认为是默认存在)
      • 无论是否用过都会添加

  • -fpic (position-independent code) 编译选项和链接选项

    • 用于生成PIC 位置无关代码 的共享库, 在链接到EXE时如果GOT表超过某些特定机器指定的最大值时会返回错误, 这时需要使用-fPIC进行重新编译和链接

  • -fPIC 编译选项和链接选项

    • 和-fpic一样, 但是回避掉了GOT大小的限制问题
    • 在编译和链接时都需要指定

-fpic与-fpie的差别很细微,当使用-fpie时编译器知道当前的编译会生成一个PIC模式的 main executable(也就是有main入口的可执行文件),这样对于内部定义的global符号,就不 要考虑全局符号介入(global symbol interpose)的问题,对于这样的globals直接产生 PC-relative方式的代码而不需要通过GOT/PLT. –Ian Lance Taylor

  • -fPIE 编译选项

    • 编译位置无关代码, 和PIC相同, 但是PIE假定了编译出的目标文件用于链接成可执行文件
    • 主要是访问外部符号时是否使用PLT/GOT
    • 实际可用-fPIC代替(不假定目标文件的最终链接目的)
    • -fpie 和-fpic一样

  • -pie 链接器选项

    • 用于生成 位置无关可执行文件 的可执行文件
    • 生成的可执行文件的ELF类型不是EXEC而是和共享库一样DYN
    • 需要-fPIE配合使用 否则会出现访问外部符号时候无法正确找到的错误
      • 这个问题等同用PIC链接非PIC编译的库

  • 其他备注

    • -no-pie 新版本g++比如6版本 默认启用pie 如不需要则要显式去除

      • 部分编译器支持

    • -fno-plt

      • 部分编译器支持

    • -fno-jump-tables

      • 部分编译器支持

    • 动态库查找路径

      • 链接时如果要使用-l 则需要先-L指定目录
      • 运行时如果不在系统指定目录的库需要设置LD_LIBRARY_PATH或者配置文件
        • 例如 简单设置export LD_LIBRARY_PATH=”./“ 路径

    • –static 组织在链接时使用动态库

    • –shared 生成动态库

    • –static-libgcc 链接静态libgcc库

    • –shared-libgcc 链接动态libgcc库

    • -static和-shared可以同时存在 这样会创建共享库 但该共享库引用的其他库会静态地链接到该共享库中

      • -Wl,–whole-archive 告诉链接器对其后面出现的静态库包含的函数和变量打包到动态库
      • -Wl,–no-whole-archive 关掉特性
        • 举例 -Wl,–whole-archive -la -lb -lc -Wl,–no-whole-archive

    • dlopen动态load共享库

Posted on | In

..1. 目录

ELF HASH

ELF的哈希表提供了对符号表的访问
组织结构如下:

labels
nbucket
nchain
bucket[0]
…
bucket[nbucket-1]
chain[0]
…
chain[nchain-1]
说明
  • bucket和chain的数量是相等的
  • 每个符号值对应一个字符串
  • 基本查找流程
    • 使用elf_hash得到hash值
    • 对hash值取模计算存放的符号值的桶
    • 如果该桶内没有数据则结束
    • 如果桶内内有数据不匹配
      • 以该符号值为下标的 chain 中存在下一个符号值
      • 重复该步骤直到找到和目标字符串匹配
    • 找到符号值对应的字符串以及符号加载时的偏移信息和符号地址信息
结论
  • chain 的数量必然大于符号的数量
  • 不考虑性能, 桶的数量可以小于符号的数量 也可以同时小于chain的数量
  • 遇到冲突后从 chain 表中查找以出现冲突的符号值为下标位置的chain, 如果该chain无内容则从符号表中查找匹配的符号的值填充该chain
    • 如果有内容并且符号值依然冲突, 则用该冲突的符号值为索引继续查找下一个
    • 最差情况则相当于直接遍历符号表
Read more »

Posted on | In

目录

ELF文件类型和描述

(Executable and Linking Format) (可执行可链接格式) 文件

文件类型

  • 可重定位文件 (relocatable file)

    • 由源文件编译而成但是还没有链接成可执行文件, 扩展名通常为.o 通常’目标文件(object file)’ 用于与其他目标文件进行链接成可执行文件或者动态链接库.
    • 可重定位是指 对外部符号的访问会进行标记, 在链接时候会重写这部分访问(操作数)重定位到真正的位置上.
    • 重定位因为存在该修补 则有以下作用:
      • 重定位在执行时是直接使用真实位置 没有其他过程 性能非常好
      • 链接共享库的时候如果需要确定地址和修补, 则还需要保证多个共享库的地址不可以重叠, 在32位下这种保证会很容易用尽虚拟(地址)空间
      • 重定位需要修改代码段, 从而破坏’代码段’只读属性, 如果在链接阶段无法完成重定位, 则只能放在加载过程完成, 这样会导致’无法实现真正的代码共享’ . 比如所有进程使用的相同so文件在内存中实际上只有一份就是依赖于so的代码段只读且一致这个原则上的.

  • 共享目标文件(shared object file)，即动态连接库文件 它在以下两种情况下被使用

    • 在链接过程中与其它动态链接库或可重定位文件一起构建新的目标文件
    • 在可执行文件被加载的过程中 被动态链接到新的进程中 成为运行代码的一部分

  • 可执行文件(executable file)，经过连接的，可以执行的程序文件。

  • coredump文件 核心转储

Read more »

Posted on | In

全局分析和统计

  • top命令

    • free 查看内存使用信息
    • vmstate [delay时间] 按照delay时间打印内存使用 io读写 CPU用量等信息
    • iostat -m -x [时间] [次数] io读写详细信息

  • sar 系统活动情况报告 追溯统计数据 从最近的0点0分开始显示数据

    • sar -A 所有
    • sar -u CPU
    • sar -q 负载
    • sar -r 内存
    • CPU存在瓶颈，可用 sar -u 和 sar -q 等来查看
    • 内存存在瓶颈，可用sar -B、sar -r 和 sar -W 等来查看
    • I/O存在瓶颈，可用 sar -b、sar -u 和 sar -d 等来查看

  • df 查看当前硬盘存储

    • du -h –max-depth=1 [./] 统计当前目录树下的文件大小

  • IPC资源查询

    • ipcs -m 查看共享内存资源
    • ipcsrm -M [shmkey] 删除共享内存资源
    • ipcsrm -m [shmid] 删除shmid标识的共享内存资源

  • ulimit -a 配置位置 /etc/security/limits.conf

    • coredump文件的大小
    • 线程栈的大小
    • 单进程最大设备数
      • 单进程最大设备数的硬性限制在/proc/sys/fs/nr_open 中配置
      • 系统配置的最大设备数可查看/proc/sys/fs/file-max 中配置
      • 系统配置的最大设备数修改/etc/sysctl.conf | fs.file-max = 1000000

  • 全局线程总数

    • 查看位置 /proc/sys/kernel/threads-max

  • 单个进程最大线程数 PTHREAD_THREADS_MAX 新的NPTL实现中不存在该限制

    • 查看位置 /usr/include/bits/local_lim.h
    • 查看位置 /usr/include/x86_64-linux-gnu/bits/local_lim.h

  • whereis 查看命令所在位置

  • lsof [文件/路径] 查看占用该文件/该目录下文件的进程

  • lsof -i 查看当前活动的网络连接 包括TCP / UDP

  • lsof -p [pid] 查看当前进程所有打开的文件/设备

  • ulimit -s 栈大小

Read more »

Posted on | In

导语

64位下的linux地址空间虽然看起来虽然庞大2^64 但是实际上进行内核与用户空间的划分后, 包括ASLR以及PIE等机制的启用, 实际留给mmap和brk的可分配区域远远小于这个值, 大约是42T的可用地址空间. 本文根据内核代码的默认宏定义进行了X86-64下的布局分析, 给基于共享内存的用户空间选址给予一定的参考.

目录

LINUX内存布局

针对X86-64内核代码的分析

..1.1. 基本布局

- -
内核地址空间范围 [0XFFFF 0000 0000 0000, 0XFFFF FFFF FFFF FFFF]
用户地址空间 [0X0000 7FFF FFFF F000, 0X0000 0000 0000 0000]
不规范地址空间 不属于内核或者用户的地址空间属于不规范地址空间

用户空间的大小由宏定义TASK_SIZE决定, 在X86-64下这个大小默认为2^47-4096(128T) 对应十六进制数为: 0X0000 7FFF FFFF F000 .

..1.2. 用户空间布局

- 用户空间布局 -
0x0
保留区
代码段(PLT代码表部分)
代码段
数据段(GOT) 只读
数据段(.got.plt) 惰性加载机制
数据段(Data)
数据段(BSS)
堆空间(Heap)
↓
未分配区域
↑
内存映射区域(mmap)
栈空间(进程栈)
TASK_SIZE

ASLR地址空间随机化

地址空间配置随机加载（英语：Address space layout randomization，缩写ASLR，又称地址空间配置随机化、地址空间布局随机化）是一种防范内存损坏漏洞被利用的计算机安全技术。
ASLR通过随机放置进程关键数据区域的地址空间来防止攻击者能可靠地跳转到内存的特定位置来利用函数。现代操作系统一般都加设这一机制，以防范恶意程序对已知地址进行Return-to-libc攻击。
这些数据区域一般包括代码段 数据段 堆区 栈区 mmap 动态库等, 其中涉及代码段的随机一般需要代码位置无关化的支持(PIC PIE机制)

不同版本的操作系统和内核版本, 在ASLR的实现上会有细节的不同, 这里主要是根据目前的生产环境做的分析, 用于确认ASLR的在地址空间中对内存布局带来的扰动范围.

ASLR的设置与关闭

LINUX下常见的设置或关闭有方式:

设置randomize_va_space的等级

随机化虚拟地址空间的配置说明如下: 

1
2
3
4
5
6
7
8
9
10
11
12
/proc/sys/kernel/randomize_va_space
0 = Disabled
1 = Conservative Randomization
2 = Full Randomization
```  
总共分了三档, 不同版本其内容随着支持程度和等级划分略有不同, 默认启用的等级也不同, 以更具体的生产环境为准 大致如下:  
0 = 关闭  
1 = 保守随机化: 共享库 栈 mmap  vdso随机化   
2 = 完全随机化:  包括brk分配的内存   
    2.1 = 代码段和数据段的随机化需要PIE位置无关可执行程序的支持  编译链接时添加 -fpie -pie  

* 修改/关闭系统配置方式如下

echo 0 > /proc/sys/kernel/randomize_va_space

1
2

* 或者通过sysctl修改

sysctl -w kernel.randomize_va_space=0

1
2
3
4
5
6
7
8
9



##### 进程个性化设置: 进程描述符的成员personality设置 ADDR_NO_RANDOMIZE     
  * setarch $(uname -m) -R [--addr-no-randomize] [target exe]  
  * 例如 ldd ./benchmark_fast 在aslr环境下会看到每次so的内存位置都在变化   
    * setarch $(uname -m) -R ldd ./benchmark_fast 这样去查看则是固定不变的  

##### GDB调试中打开或者关闭ASLR(默认会禁用)

关闭ASLR：
set disable-randomization on
开启ASLR：
set disable-randomization off
查看：
show disable-randomization

1
2
3
4
5
6
7


### 内核代码中相关的宏定义和随机值计算

#### TASK_SIZE 定义 用户地址空间的大小    
在X86的内核代码中, 默认的TASK_SIZE为 (1UL << 47) - 4096)   
即

2^47-4096 => 0x7fff ffff f000 约为128T 

1
gdb调试程序默认会关闭aslr, 我们通过gdb运行一个程序, 然后对齐pmap可以得到如下内存分布:

00007ffff7ffc000 4K r—- ld-2.27.so
00007ffff7ffd000 4K rw— ld-2.27.so
00007ffff7ffe000 4K rw— [ anon ]
00007ffffffde000 132K rw— [ stack ]
ffffffffff600000 4K r-x– [ anon ]

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

00007ffffffde000 + 132K = ‭0x7FFFFFFFF000‬  和内核代码中的宏定义一致



```C++
#ifdef CONFIG_X86_32
/*
 * User space process size: 3GB (default).
 */
#define IA32_PAGE_OFFSET    PAGE_OFFSET
#define TASK_SIZE        PAGE_OFFSET
#define TASK_SIZE_LOW        TASK_SIZE
#define TASK_SIZE_MAX        TASK_SIZE
#define DEFAULT_MAP_WINDOW    TASK_SIZE
#define STACK_TOP        TASK_SIZE
#define STACK_TOP_MAX        STACK_TOP

#else

#ifdef CONFIG_X86_5LEVEL
#define __VIRTUAL_MASK_SHIFT    (pgtable_l5_enabled() ? 56 : 47)
#else
#define __VIRTUAL_MASK_SHIFT    47
#endif

#define TASK_SIZE_MAX    ((1UL << __VIRTUAL_MASK_SHIFT) - PAGE_SIZE)

#define DEFAULT_MAP_WINDOW    ((1UL << 47) - PAGE_SIZE)

/* This decides where the kernel will search for a free chunk of vm
 * space during mmap's.
 */
#define IA32_PAGE_OFFSET    ((current->personality & ADDR_LIMIT_3GB) ? \
                    0xc0000000 : 0xFFFFe000)

#define TASK_SIZE_LOW        (test_thread_flag(TIF_ADDR32) ? \
                    IA32_PAGE_OFFSET : DEFAULT_MAP_WINDOW)
#define TASK_SIZE        (test_thread_flag(TIF_ADDR32) ? \
                    IA32_PAGE_OFFSET : TASK_SIZE_MAX)
#define TASK_SIZE_OF(child)    ((test_tsk_thread_flag(child, TIF_ADDR32)) ? \
                    IA32_PAGE_OFFSET : TASK_SIZE_MAX)

#define STACK_TOP        TASK_SIZE_LOW
#define STACK_TOP_MAX        TASK_SIZE_MAX

#define INIT_THREAD  {                        \
    .addr_limit        = KERNEL_DS,            \
}

extern unsigned long KSTK_ESP(struct task_struct *task);

#endif /* CONFIG_X86_64 */

栈地址

随机值大小为17G = 0x3fffff000

代码位置如下:
load_elf_binary -> setup_arg_page 

1
2
retval = setup_arg_pages(bprm, randomize_stack_top(STACK_TOP),
                 executable_stack);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define __STACK_RND_MASK(is32bit) ((is32bit) ? 0x7ff : 0x3fffff)
#define STACK_RND_MASK __STACK_RND_MASK(mmap_is_ia32())

unsigned long randomize_stack_top(unsigned long stack_top)
{
    unsigned long random_variable = 0;

    if (current->flags & PF_RANDOMIZE) {
        random_variable = get_random_long();
        random_variable &= STACK_RND_MASK;
        random_variable <<= PAGE_SHIFT;
    }
    return PAGE_ALIGN(stack_top) - random_variable;
}

MMAP映射区起始地址

1
load_elf_binary -> setup_new_exec -> arch_pick_mmap_layout ->arch_pick_mmap_base

mmap的起始计算为:
STACK_TOP - 栈最大长度 - 间隙 - 随机值
栈最小长度为128M
随机位数配置在/proc/sys/vm/mmap_rnd_bits default=28
默认随机最大值为 0xFFFFFFF000 大约为1T
用户空间起始地址0x7FFFFFFFF000

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
94
95
96
97

#define TASK_SIZE_MAX     ((1UL << 47) - PAGE_SIZE) //0x7FFFFFFFF000
#define TASK_SIZE     TASK_SIZE_MAX

#define STACK_TOP          TASK_SIZE
#define STACK_TOP_MAX          TASK_SIZE_MAX

/* 1GB for 64bit, 8MB for 32bit */
#define __STACK_RND_MASK(is32bit) ((is32bit) ? 0x7ff : 0x3fffff)
#define STACK_RND_MASK __STACK_RND_MASK(mmap_is_ia32())


static unsigned long stack_maxrandom_size(unsigned long task_size)
{
    unsigned long max = 0;
    if (current->flags & PF_RANDOMIZE) {
        max = (-1UL) & __STACK_RND_MASK(task_size == task_size_32bit());
        max <<= PAGE_SHIFT;
    }

    return max;
}

//task size为0x7FFFFFFFF000
//随机值为 random()& ((1UL << 28)   -1) 个页面, 即0x00FFFFFFF000
void arch_pick_mmap_layout(struct mm_struct *mm, struct rlimit *rlim_stack)
{

    mm->get_unmapped_area = arch_get_unmapped_area_topdown;

    arch_pick_mmap_base(&mm->mmap_base, &mm->mmap_legacy_base,
            arch_rnd(mmap64_rnd_bits), task_size_64bit(0),
            rlim_stack);  //proc/sys/vm/mmap_rnd_bits  default=28

}

//
static unsigned long arch_rnd(unsigned int rndbits)
{
    if (!(current->flags & PF_RANDOMIZE))
        return 0;
    return (get_random_long() & ((1UL << rndbits) - 1)) << PAGE_SHIFT;  
}

/*
 * 新布局直接调用*base = mmap_base(random_factor, task_size, rlim_stack);  
 */
static void arch_pick_mmap_base(unsigned long *base, unsigned long *legacy_base,
        unsigned long random_factor, unsigned long task_size,
        struct rlimit *rlim_stack)
{
    *legacy_base = mmap_legacy_base(random_factor, task_size);
    if (mmap_is_legacy())
        *base = *legacy_base;
    else
        *base = mmap_base(random_factor, task_size, rlim_stack);
}

//这是是随机值的上下限保护 栈至少要有128M 
//task size减去随机值, 再减去栈的大小, 栈的最小值为128M  
static unsigned long mmap_base(unsigned long rnd, unsigned long task_size,
                   struct rlimit *rlim_stack)
{
    unsigned long gap = rlim_stack->rlim_cur;
    unsigned long pad = stack_maxrandom_size(task_size) + stack_guard_gap;
    unsigned long gap_min, gap_max;

    /* Values close to RLIM_INFINITY can overflow. */
    if (gap + pad > gap)
        gap += pad;

    /*
     * Top of mmap area (just below the process stack).
     * Leave an at least ~128 MB hole with possible stack randomization.
     */
    gap_min = SIZE_128M;
    gap_max = (task_size / 6) * 5;

    if (gap < gap_min)
        gap = gap_min;
    else if (gap > gap_max)
        gap = gap_max;

    return PAGE_ALIGN(task_size - gap - rnd);
}

//max = (0x3fffff <<= 12)   = 0x3fffff000
static unsigned long stack_maxrandom_size(unsigned long task_size)
{
    unsigned long max = 0;
    if (current->flags & PF_RANDOMIZE) {
        max = (-1UL) & __STACK_RND_MASK(task_size == task_size_32bit());
        max <<= PAGE_SHIFT;
    }

    return max;
}

代码段开始地址

ELF文件如果是普通的EXEC类型则会使用指定的入口地址下面讨论PIE编译出的DYN可执行文件
其加载地址为 DEFAULT_MAP_WINDOW /32上增加一个arch_mmap_rnd随机值
DEFAULT_MAP_WINDOW /32 = 0x555555554AAA
同mmap一样为 0x00FFFFFFF000 约1个T大小
代码段起始位置约为84T 随机值 1T

代码段数据段等整体随机 

1
2
3
4
5
6
7
if (interpreter) {
                load_bias = ELF_ET_DYN_BASE;
                if (current->flags & PF_RANDOMIZE)
                    load_bias += arch_mmap_rnd();
                elf_flags |= MAP_FIXED;
            } else
                load_bias = 0;
1
2
3
4
5
6
7
loc->elf_ex.e_entry += load_bias;
elf_bss += load_bias;
elf_brk += load_bias;
start_code += load_bias;
end_code += load_bias;
start_data += load_bias;
end_data += load_bias;

HEAP区开始地址

brk从BSS结束地址开始, 会有一个额外的随机arch_randomize_brk
为固定的大小范围0x02000000, 大约为33M 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if ((current->flags & PF_RANDOMIZE) && (randomize_va_space > 1)) {
		/*
		 * For architectures with ELF randomization, when executing
		 * a loader directly (i.e. no interpreter listed in ELF
		 * headers), move the brk area out of the mmap region
		 * (since it grows up, and may collide early with the stack
		 * growing down), and into the unused ELF_ET_DYN_BASE region.
		 */
		if (IS_ENABLED(CONFIG_ARCH_HAS_ELF_RANDOMIZE) &&
		    loc->elf_ex.e_type == ET_DYN && !interpreter)
			current->mm->brk = current->mm->start_brk =
				ELF_ET_DYN_BASE;

		current->mm->brk = current->mm->start_brk =
			arch_randomize_brk(current->mm);
#ifdef compat_brk_randomized
		current->brk_randomized = 1;
#endif
	}
1
2
3
4
unsigned long arch_randomize_brk(struct mm_struct *mm)
{
	return randomize_page(mm->brk, 0x02000000);
}

结论部分

假定编译出来的是PIE类型的ELF并且全开ASLR设置
那么在mmap和heap之间的地址空间大小大约是
128T - 17G - 1T - 84T - 1T -33M = 42T

mmap最小起始地址略小于0x0000 7F00 0000 0000
brk起始地址最大略大于 0x0000 5655 5555 5555

这个是以T为单位的粗略计算, 考虑到计算时忽略了一些小的单位(GB级别或者更小), 包括间隙 小的随机值, 以及动态库 数据段代码段本身占用的空间, 这里可以做一个进一步的保守计算来使用这个空间.

计算这个空间的意义在于, 例如我们对共享内存使用一个固定的地址时, 需要避免和系统本身的动态分配的地址空间相冲突, 而计算出来的地址空间的确定可以保证这一点, 例如可以用这两个地址做一个中值计算, 把这个中值作为安全的绝对地址使用.

结论部分补充验证数据

  • 没有开启PIE和ASLR
    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
    0000000000400000      4K r-x-- a.out (deleted)
    0000000000600000      4K r---- a.out (deleted)
    0000000000601000  40964K rw--- a.out (deleted)
    0000000002e02000    132K rw---   [ anon ]
    00007ffff70f2000   1732K r-x-- libc-2.27.so
    00007ffff72a3000   2044K ----- libc-2.27.so
    00007ffff74a2000     16K r---- libc-2.27.so
    00007ffff74a6000      8K rw--- libc-2.27.so
    00007ffff74a8000     16K rw---   [ anon ]
    00007ffff74ac000     92K r-x-- libgcc_s.so.1
    00007ffff74c3000   2044K ----- libgcc_s.so.1
    00007ffff76c2000      4K r---- libgcc_s.so.1
    00007ffff76c3000      4K rw--- libgcc_s.so.1
    00007ffff76c4000   1608K r-x-- libm-2.27.so
    00007ffff7856000   2044K ----- libm-2.27.so
    00007ffff7a55000      4K r---- libm-2.27.so
    00007ffff7a56000      4K rw--- libm-2.27.so
    00007ffff7a57000   1480K r-x-- libstdc++.so.6.0.25
    00007ffff7bc9000   2048K ----- libstdc++.so.6.0.25
    00007ffff7dc9000     40K r---- libstdc++.so.6.0.25
    00007ffff7dd3000      8K rw--- libstdc++.so.6.0.25
    00007ffff7dd5000     12K rw---   [ anon ]
    00007ffff7dd8000    148K r-x-- ld-2.27.so
    00007ffff7fd7000     24K rw---   [ anon ]
    00007ffff7ff8000      8K r----   [ anon ]
    00007ffff7ffa000      8K r-x--   [ anon ]
    00007ffff7ffc000      4K r---- ld-2.27.so
    00007ffff7ffd000      4K rw--- ld-2.27.so
    00007ffff7ffe000      4K rw---   [ anon ]
    00007ffffffde000    132K rw---   [ stack ]
    ffffffffff600000      4K r-x--   [ anon ]
  • 开启PIE和ASLR后多次测试得到的一个接近最小可分配空间的内存分布结果如下:
    代码段从0x0000 5640开始
    mmap的则从0x 0000 7eff开始而不是概率更大的0x 0000 7f** 这样的地址 
    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
    00005640b5092000      4K r-x-- a.out
    00005640b5292000      4K r---- a.out
    00005640b5293000  40964K rw--- a.out
    00005640b99f2000    132K rw---   [ anon ]
    00007effd7734000  20484K rw---   [ anon ]
    00007effd8b35000   1732K r-x-- libc-2.27.so
    00007effd8ce6000   2044K ----- libc-2.27.so
    00007effd8ee5000     16K r---- libc-2.27.so
    00007effd8ee9000      8K rw--- libc-2.27.so
    00007effd8eeb000     16K rw---   [ anon ]
    00007effd8eef000     92K r-x-- libgcc_s.so.1
    00007effd8f06000   2044K ----- libgcc_s.so.1
    00007effd9105000      4K r---- libgcc_s.so.1
    00007effd9106000      4K rw--- libgcc_s.so.1
    00007effd9107000   1608K r-x-- libm-2.27.so
    00007effd9299000   2044K ----- libm-2.27.so
    00007effd9498000      4K r---- libm-2.27.so
    00007effd9499000      4K rw--- libm-2.27.so
    00007effd949a000   1480K r-x-- libstdc++.so.6.0.25
    00007effd960c000   2048K ----- libstdc++.so.6.0.25
    00007effd980c000     40K r---- libstdc++.so.6.0.25
    00007effd9816000      8K rw--- libstdc++.so.6.0.25
    00007effd9818000     12K rw---   [ anon ]
    00007effd981b000    148K r-x-- ld-2.27.so
    00007effd9a1e000     24K rw---   [ anon ]
    00007effd9a3f000      4K r---- ld-2.27.so
    00007effd9a40000      4K rw--- ld-2.27.so
    00007effd9a41000      4K rw---   [ anon ]
    00007ffd922c7000    132K rw---   [ stack ]
    00007ffd92385000      8K r----   [ anon ]
    00007ffd92387000      8K r-x--   [ anon ]
    ffffffffff600000      4K r-x--   [ anon ]

Posted on | In

..1. 多线程

  1. 老的LinuxThreads (管理线程机制) 设计中线程栈的位置在 HEAP之下 的高位 导致无法可信的设置heap大小
  2. 新的NPTL解决了老的线程机制中的管理单点问题 信号问题 内存布局问题等 顺便实现了PTHREAD_PROCESS_SHARED
  3. pthread_attr_setstackaddr可指定线程栈的地址(mmap)
  4. pthread的创建和销毁
    1. 创建
      1. 使用用户提供的stack创建线程并加入__stack_user
      2. nptl 先尝试获取stack_cache中tid为0大小合适的空闲stack, 如果失败则从mmap分配新的stack, 然后加入stack_used
      3. tid list等信息存储在stack内存的高地址端的头部
    2. start_thread执行完用户函数后会进行数据回收和清理(但无法销毁自身)
      1. 如果该线程非detach 则等待join (没有join则会一直保留)
      2. 如果该线程被detach 则执行__free_tcb
        1. 如果是用户分配的stack 从stack_user链表中移除并清理tls 线程局部存储
        2. 如果是自动分配的stack 从stack_used链表中移除, 然后加入stack_cache中, 清理tls线程局部存储(此时tid不为0)
        3. 检查当前stack_cache的总大小, 超过阈值则遍历一次stack_cache并释放掉(tid为0)空闲的stack, 如果小于阈值则提前break该次遍历
    3. 内核在该线程结束后 会对该线程的tid清零(创建线程时CLONE_CHILD_CLEARTID参数会让内存清除某标记内存), 此后该资源可以安全销毁.
  5. brk和mmap的分配由glibc确定 默认规则是小于M_MMAP_THRESHOLD宏走brk 但是新系统的算法可能会让大于这个参数的临时分配也走brk
    Read more »

Posted on | In

SDM框架对系统发展生命周期的过程描述

SDM(软件开发方法)框架是在SDLC在软件开发早起

  • (SDM框架)软件开发过程有以下基本的核心活动内容
    • 需求分析 (Requirements analysis)
    • 领域设计 (Software design)
    • 系统设计 (Software engineering)
    • 编码开发 (Software construction)
    • 功能验证 (Software testing)
    • 错误修正 (Debugging)
    • 部署交付 (Software deployment)
    • 维护 (Software maintenance)
      Read more »

Posted on | In

在认知心理学中, 问题解决的思维过程被描述为: 在问题空间下, 经过思考与推理, 达到目的的心理历程.
该过程分为四个阶段

  • 发现问题
  • 分析（明确）问题
  • 提出假设
  • 验证假设

其中问题空间(问题域)是指问题解决者对所要解决的问题的一切可能的认识状态, 包括对问题的初始状态和目标状态的认识, 以及如何从初始状态转化为目标状态的认知操作等.

问题的解决就是对问题空间进行搜索, 找到一条从问题的初始状态到达目标状态的通路.

问题解决的一般性阶段及其描述:

  • 问题的存在,发现和提出
  • 定义问题域, 即定义问题集以及问题的约束集
  • 从问题域中递归的构造可演算的计算(概念)模型
  • 制定现实可执行的解决方案
  • 实施并植入问题域所在现实环境验证
  • 问题的解决

在这个过程中, 每个过程的推进都可能会伴随对其前向的阶段所做的处理发起修正, 在此过程中我们会不断的逼近’真正的问题’的问题定义, 以及’真正的问题解决’的结果, 从而采用形式化的方法寻找到最优的解决路径

Read more »

Posted on | In
KDTREE

空间K维划分, 用来快速寻找距离最近的障碍(指定数量) 优化RVO的资源消耗.

路径规划

高级规划

DIJKSTRA 最短路径 等寻路方法

底层规划

VO RVO ORCA等Obstacle Avoidance避障算法

KDTREE

这个是一个简单的KDTREE实现 用来寻找距离最近的障碍(指定数量) 优化RVO的资源消耗.

VO Velocity Obstacles 速度障碍

核心思想: 只要在未来有可能会发生碰撞的速度 都排除在外
抖动现象: 两个位移单位存在可能会发生路径碰撞的情况下会同时采取保守的避让速度,导致新速度偏离过大又大幅度回归,从而产生震荡.

RVO Reciprocal Velocity Obstacles 互惠的速度障碍

核心思想: 优化VO思想, 假定对方也会采取避障行为, 缩小(average VO)速度.

ORCA Optimal Reciprocal Collision Avoidance 最优互惠碰撞避免

核心思想: 优化RVO, 额外考虑速度大小, 求解过程使用线性规划,更高效简洁.

  • 对其他所有agents的ORCA求交（线性规划），再与自己可选速度求交集，得候选速度集ORCAτA
  • 在候选集中求解跟自己偏好速度最近的一个速度vnewA
Read more »