Browsed by
分类:C

proxychains-ng 原理解析

proxychains-ng 原理解析

Preface

提起 proxychains 相信大家都并不陌生,这个程序可以方便的让你在终端使用 SOCKS5, SOCKS4, HTTP 等协议代理网络访问,而不需要为了转换 SOCKS5 协议再搭建一个 HTTP 的代理来使用 http_proxy, https_proxy 这些 Shell 内置的环境变量来访问网络了。不过 proxychains 并不对所有的应用程序有效,一个典型的情况是 Golang 编写的 程序是无法使用 proxychains 进行代理的。在使用 proxychains 的时候会报这样的错误:

下面就通过对 proxychains-ng 的原理的解析,来解答这个问题,并且为 golang 编写的程序提供一个解决方案。

Shared Libraries

Linux 下的很多程序都依赖着多种多样的动态链接库(shared library),使用动态链接库既可以节省磁盘的空间大小(你编译出来的程序不会特别大),同时也会节省程序的运行内存,多个共享动态链接库的进程只需要一份库在内存中。若是静态链接的话,则每一个进程都要带一份库。通过  ls -l /usr/lib (根据发行版不同路径可能会有不同)即可看到很多动态链接库。

首先来介绍几个动态链接库的基本知识,大家会发现这个文件夹下面有很多链接,比如

有两个指向 libzmf-0.0.so.0.0.2 的软连接这些文件的名字很相似,那么具体都代表什么呢,下面就来进行说明。

对于一个动态链接库来说,有三个名字,分别是 soname, linkername 和 realname

  • linkername: libxxx.so (没有任何版本号) 在安装 library 的时候建立,是一个链接到 realname 的软链接
  • soname: libxxx.so.(VER) (带有版本号) 在安装 library 的时候建立,是一个链接到 realname 的软链接
  • realname: libxxx.so.(VER).(MINOR).[RELEASE] (必须带有版本号和 minor number, 可选的为带有 release number) 是该 library 本身

对于上面这个例子来说 libzmf-0.0 的 soname 就是 libzmf-0.0.so.0, linkername 是 libzmf-0.0.so,realname 是 libzmf-0.0.so.0.0.2

当一个程序指定要链接的动态链接库的时候,他们指定的是这个链接库的 soname, 而不是 realname 这样的考量是在链接库更新 minor number 的时候,不需要对这个程序进行重新链接,至于为什么没有用 linkername 是为了 ABI 兼容性考虑,当一个库升级后 ABI 发生了变化时,依赖这个库的程序必须要重新编译才能使用,否则就会因为 ABI 不兼容导致段错误等问题发生。因而当一个库的 MAJOR VER NUMBER 更新时,说明它有 ABI Breaking Change. 而当一个库只是更新了 MINOR/RELEASE NUMBER 的时候 这时我们不需要进行重新编译。

Dynamic Loading Progress

本文重点在于讲解 proxychains 的原理,因而对 loader 部分只提及相关部分,下述过程并不是完整的程序加载过程

在 Linux 上所有动态链接的程序都会链接一个 ld-linux-xxxx.so(下面简称 ld-linux.so) 的动态链接库,这个动态链接库很特殊,它会解析该程序所需的 shared libraires ,并且加载他们以及他们必要的依赖 我们可以通过查看每一个动态链接的程序的 Dynamic Section 了解到其依赖的链接库都是什么。比如这是 curl 直接依赖的动态链接库:

注意这些只是 “直接依赖”, ld-linux.so 还会去解析这些依赖的 library 的依赖是什么,最后得到我们通过 ldd 看到的输出结果

对于每一个 library 是如何解析到其路径的具体过程,可以通过查看 man 8 ld-linux  了解具体过程

Special Environment Variable: LD_PRELOAD

在 ld-linux(8) 的 Man Page 里 我们可以看到这样一个环境变量的说明: LD_PRELOAD

A list of additional, user-specified, ELF shared objects to be loaded before all others.

当 secure-execution 模式没有开启的时候 指定 在 LD_PRELOAD 里的 shared library 会比其他任何 shared libray 都先加载. 这就给我们去伪造, hook 调用函数提供了途径。

背景知识铺垫到这里就结束了,接下来我们将结合 proxychains-ng 的代码介绍其原理

Proxychains-ng 的原理

简单来说, proxychains-ng 就是 hook 了 libc 里提供的基本网络通讯函数

这些包在 SETUP_SYM 里的函数(在 SOLARIS 中 connect 是 __xnet_connect)会被 proxychains 进行 hook, 然后通过内置的 hook 函数进行后续代理操作。

我们查看 src/libproxychains.c 可以发现,这个 libproxychains.c 含有 connect, sendto, … 这些函数, 而且函数的签名和 connect(3) sendto(3)… 的都一样

这就是 proxychains 的原理所在,proxychains 将这些函数重写一份,并且 export libproxychains 为 shared library. 当该 Library 被 preload (设置在 LD_PRELOAD) 里的时候,则在程序调用 connect , close 等网络相关的 libc 函数的时候,就会被 proxychains 接管。

我们在代码里还能看到很多的 true_xxx 函数, 他们只有函数调用没有定义, 在 src/core.h 中定义这些符号从外部引用

为了进一步理解 proxychains 我们需要弄清楚 这个 true_xxx 从何而来, 因为这些函数被钩子函数们屡次调用。我们现在就回到 SETUP_SYM 这个宏的定义上来

SETUP_SYM 这个宏就是 true_xxx 系列函数的解析的关键

我们以 connect 为例,展开一下这个宏: SETUP_SYM(connect) 被展开为

这里 宏 invoke 了 load_sym 函数, 该函数如下 :

load_sym 调用了 dlsym 并且将 dlsym 返回值返回,然后通过上面的宏我们就知道 true_xxx 就会得到这个返回的地址 也就是函数地址。另一问题就是,这个返回的地址意味什么?相信很多人已经猜到了,true_xxx 这些函数就应该是指向那些没有被 hook 的原始网络函数的。我们现在查看 dlsym 的具体调用的含义。通过 dlsym(3) 我们知道了, dlsym 的两个参数分别为 dlopen 打开的 handle, 以及要解析的 symbol name。而  RTLD_NEXT 和 RTLD_DEFAULT 是两个 pseudo-handle。我们这里贴一下 RTLD_NEXT 的解释的全文

RTLD_NEXT
Find the next occurrence of the desired symbol in the search order after the current object. This allows one to provide a wrapper around a function in another shared object, so that,
for example, the definition of a function in a preloaded shared object (see LD_PRELOAD in ld.so(8)) can find and invoke the “real” function provided in another shared object (or for
that matter, the “next” definition of the function in cases where there are multiple layers of preloading).

可以知道,这个 pseudo-handle 会通过解析当前的 library search path 找到 第二个 symbol name 等于 symname 的函数,manpage 里还贴心的给出了一个应用场景,就是在这种 LD_PRELOAD 的情况下想要加载 “real” 函数的时候,这样可以方便的进行加载。

我们再来查看一下 hooked connect 函数的具体逻辑

通过这个判断可以看到,当该链接不满足 TCP 链接的条件的时候,是会去调用 libc 的 connect 函数继续下去

这里

就是 proxychains 将链接转到了自己的 SOCKS 链接逻辑里的调用。这之后的一切就随 proxychains 操作了。

看到这里相信大家对 proxychains 如何做到让其他程序能够代理链接有一定认识了。那么还有一个小问题没有解答,在 ArchLinux 和其他一些发行版上使用 proxychains 的时候我们也没有手动设置 LD_PRELOAD 这个环境变量,他是如何被设置的呢? 这里我们只需要去看 https://github.com/rofl0r/proxychains-ng/blob/1c8f8e4e7e31e64131f5f5e031f216b557f7b5ed/src/main.c#L139

这里通过 putenv 设置了 LD_PRELOAD 的环境变量,然后执行了 execvp 调用命令行后面指定的程序。

通过上述 code reading 我们可以得出结论: proxychains 是通过 LD_PRELOAD 让自己在其他所有 shared library 之前被解析, 并导出 libc 的网络功能函数 connect, close, sendto, … 等函数, 通过此方法 hook libc API , 来达到让其他的程序能够通过其进行 SOCKS5 proxy 访问的效果

那么我们来尝试一下吧~ 我们来 hook 一下 open 函数看看会出现什么事情

我们使用以下参数进行编译

我们让 open 恒定返回 fd = 0 即为进程默认打开的标准输入 (/dev/pts) 我们执行  LD_PRELOAD=./libopen.so cat /usr/bin/vim 程序先是输出了一行 “Hooked open” 然后就 block 在了那里,好像在等待读入输入一样,而这个操作的原始行为应该是 cat 出来 /usr/bin/vim 这个 binary file 然后导致 terminal 乱码(逃 因而我们现在可以说,我们成功的 hook 了 libc 的函数 \w/ 感兴趣的朋友可以试试把上述代码的返回值修改为大于2的值,然后看看会发生什么。

Why Some Programs (e.g. Golang) Cannot Use It?

通过上文我们知道了,很多的 golang 程序都是静态链接的程序,当然不涉及到任何 shared library preload, 对于这些程序来说我们没有办法让他们使用 proxychains.

但是最初的这个奇怪的报错是什么?

我们 grep 224 发现这个的确出现在了 proxychains-ng 的代码中,而且还是一个 DNS 相关的变量, 我们可以猜测 对于涉及网络请求的golang程序,可能有一部分函数被 proxychains hook 了(Thanks to @Equim)。为了验证我们的猜想,我们给 proxychains 的每一个 Hook 的函数加上调试输出,下面放出一个 demo 程序,分别使用 golang 的 http.Get 和 net.Dial 两个方式向 myip.ipip.net 请求自己的 IP 地址

我们使用 go build 上面的代码 -> demo 然后 通过增加了调试信息的 Proxychains 执行 demo 得到如下输出:

我们发现,这个 demo 程序的 getaddrinfo 和 freeaddrinfo 被 hook 到了 proxychains 其他函数没有。因而我们的猜想得到了验证,具体可以去参考 golang source code (这里暂时不进行讨论)

A Way For Golang Programs to Use Proxychains

这个问题的答案就是使用 gccgo

我们先来看效果

不使用 proxychains 直接运行 编译得到的 demo

使用 proxychains 代理后

可以看出,这次 proxychains 生效了! Hooray

那么为什么生效了呢?

我们对比两个不同 compiler 编译出来的 go binary 的 shared library 可以发现

他们两个都 link 了 libc(内含有 connect 函数) 为什么一个会接受 proxy 一个不能呢? 猜测可以是, connect 函数在 gc compiler 版的 go 中调用的不是 libc 的 connect, 而在 gccgo 里则是调用了这个 我们需要通过阅读源码来弄清楚 connect 函数是来自哪里的。

GC(Go Compiler)下的调用

我们先来看 connect 在 gc (我们熟知的默认 go compiler) 下 connect 的调用链路:

在 <go_src>/src/syscall 下有一系列的 syscall 文件, 对于 Linux 64 bit 我们仅需要看 src/syscall/syscall_linux_amd64.go 这个文件,这里我们发现了

这样一段含有 connect 的签名的注释,每一行的 //sys //sysnb 会被 perl 脚本 src/syscall/mksyscall.pl 给展开, connect 展开后是这样的

查看 Syscall 的实现 我们跟踪到了 src/syscall/asm_linux_amd64.s 内的代码

可以看到这里是通过直接调用 syscall 进行了系统调用,而非使用了 libc 提供的 connect 函数。因而我们在这种情况下是无法让 connect 被 proxychains 给 hook 的

GCCGO 下的调用

我们再来看一下 gccgo 对 connect 的调用链路:

在 gccgo/libgo/go/syscall 下我们查看文件 socket_posix.go 可以看到

同样,这段代码也会被一个 mksyscall.awk 的宏展开为:

我们可以看到, 这里使用了 extern directive 将函数 c_connect 引用指向了外部的 connect 符号,  通过查看 libgo 的依赖关系(ldd) 我们发现 libgo 依赖 libc, libc 提供了 connect 因而 gccgo 编译出来的程序的 connect 是通过 libc 调用,而不是内部自行解决了,所以我们可以通过 proxychains 来进行 hook。

验证

最后再来验证一下我们的这个结论。  对于查看 shared lib 的相关内部过程,可以用一个神奇的环境变量 LD_DEBUG, 我们使用 LD_DEBUG=bindings 来展示出每一个符号的 bind 过程,查看两个不同的 go compiler 编译出的程序在 symbol resolution 时有什么不同。(都已经使用 LD_PRELOAD preload 了 libproxychains4.so )

For GCCGO

For GC

我们可以看出,在 gccgo 编译的版本中, libgo 需要的外部 symbol connect 被 bind 到了 GLIBC connect 而在 gc 编译的版本中则不存在这样的 binding. 因而我们得出结论 gccgo 编译的代码可以被 proxychain hook

Reference

  • ld-linux man page
  • dlsym(3) man page
  • http://tldp.org/HOWTO/Program-Library-HOWTO/shared-libraries.html
  • https://github.com/rofl0r/proxychains-ng

Misc

遗留问题: 在查看 LD_DEBUG=bindings 的时候,我们可以看到这样一段奇怪的 bind: binding file /usr/lib/libproxychains4.so [0] to /usr/lib/libpthread.so.0 [0]: normal symbol `connect’ proxychains 的 connect 竟然 bind 到了 libpthread 上,这让我很费解,尝试了 LD_DEBUG 看 curl 的 binding 也是最后到了 libpthread 上,这里就让我产生了一个悬而未解的问题: 莫非 proxychains 不仅仅 hook 了 libc 还 hook 了 libpthread? 我查看了 LD_DEBUG=1 curl xxx.cn 的输出,发现所有的 connect symbol 都是解析到了 libpthread.so 上,也许,所有的 connect 都没有走 libc 而是走了 libpthread?z 这就是另一个问题了。

后记: 因为最近在准备出国留学,备考申请事情多得很忙,几乎没有多少时间来研究技术,因而博客搁置的时间远比 3 个月长,甚至有的朋友留言说博主已经凉了,在此对大家的关注表示感谢,因为很多事情导致了博客没有更新。在备考结束后博客还会保持以前的进度持续更新的。同时感谢 @Equim 在撰写本文时提供的种种帮助,关于她说的另一个问题我在这里没有讲到,也是和 proxychains 有关的一个问题,链接在这里: https://hackerone.com/reports/361269 感兴趣的各位可以去看看

然后我就要继续去准备 GRE 了(x

Kernel Driver btusb Overview

Kernel Driver btusb Overview

Function

btusb_probe

btusb_probe is use for hot plug-in for bluetooth usb generic controller, here will explain the function in detail.

First is an interface check mechanism

This special condition is used for supporting apple Macbook 12,8 (2015 early). According to the normal specification, the main interface for USB is 0, and audio (isochronous) is 1, but apple made a change on it, changing the main interface to 2 and audio to 3. The “bInterfaceNumber !=2 ” is for checking hardware for the special case in Apple series product. The macro BTUSB_IFNUM_2 is a driver_info flag, for Macbook devices, this flag will be set, else it will be 0. See the btusb_table for detail.

Then do further check on blacklist devices, some of the blacklist device is because there are specific driver (e.g bcmxxxx) for the device, so they do not use the generic one called btusb. Some of them just because they are not supported, and other reasons.(Not sure what reason are there)

 

Then we allocate memory for structure btusb_data, use this to store data for the USB interface. Also we need to check the memory remained for the allocation. Then we do the real work: set up currrent interface endpoints for interrupt and bulk (Why only these two?) It go through all the endpoint in the current interface. We get the current_altsetting to get a list of current active(available) endpoints.

 

usb_endpoint_is_int_in and usb_endpoint_is_bulk_out, usb_endpoint_is_bulk_in are functions use to know what type of the endpoint is it. These info is use to set up driver data at the end of the call. If none of inter_ep, bulk_tx_ep or bulk_rx_ep is set, it will also result in No Device Error(ENODEV)

This part of code is used for URB generation. URB is short for “USB Request Block” According to the Bluetooth v5.0 Specification, When sending an Control URB to AMP, the bRequest field should be 0x2b. Shown in the figure below.

 

Currently, for the interface to work with kernel to perform different operations. The driver itself need to be convert to device structure. Use the function named interface_to_usbdev Here is a quote from Linux Device Driver 3 :

A USB device driver commonly has to convert data from a given struct usb_interface structure into a struct usb_device structure that the USB core needs for a wide range of function calls. To do this, the function interface_to_usbdev is provided. Hopefully, in the future, all USB calls that currently need a struct usb_device will be converted to take a struct usb_interface parameter and will not require the drivers to do the conversion.

 

Then we continue with the initialize process.

 

Here we init the workqueue, data->work and data->waker these are shared workqueue offered by kernel. (Default Shared workqueue). We call schedule_work(data->work) in btusb_notify function to submit a job into workqueue and data->waker is also controlled by other functions

Then these init_usb_anchor calls. In my view, is just a sort of data queue, URB request will be queued(anchored) in certain queue, then processed in serial. Then init the spinlock for the device(interface)

 

Another special case, for Intel bluetooth usb generic driver, kernel will use special recv handler functions, for other USB generic bluetooth driver, kernel just use the common one.

Then do a lot of device specific set-up, we skip the code and go to the  isochronous setup process.

 

 

Here, the usb_driver_claim_interface is used for set up more than one interface binding to the current device driver. It also happens when this is a isochronous or acm(?) interface, here it’s a isochronous interface

Finally we call hci_register_dev to register it , this is one of the function in the Bluetooth Host Controller Interface core function series, from file net/bluetooth/hci/hci_core.c. After that, we set the interface data to intf

[Linux 0.11] Draft 5 虚拟内存管理(mm/memory.c)

[Linux 0.11] Draft 5 虚拟内存管理(mm/memory.c)

Overview

本文介绍 32 位保护模式下的内存分页, 以及 linux0.11 对物理内存的管理。

意义

既然要使用内存分页,那么就一定有他的优势所在。我们首先来探讨一下使用内存分页的意义, 分页在于为进程提供了虚拟地址空间,通过提供的这个虚拟地址空间,我们可以做到下面的这些:

  1. 精细的权限控制粒度: 内存页大小以 4KB 为一页单位(也可以是4MB, 这里不讨论这种情况), 可以针对每一个内存页设置该4K空间的访问权限。相比分段的粗粒度精细了很多,目前的分段功能只是一个兼容性考虑,分段都是将整个0 – 最大内存空间直接映射为一个段;
  2. 可以使得进程独享地址空间: 通过切换CR3寄存器的内容,可以实现多个进程占用同一个虚拟地址空间。
  3. 有效的解决了进程对大块连续内存的请求: 这里用一个例子来说明一下。

例子是这样的: 如果我们有16MB的物理内存,现在有进程A B C分别占用5MB, 2MB, 3MB内存, 且不共享内存。然后现在进程B退出了,我们还剩余8MB内存,可是如果不使用分页的话,内存连续分配, 我们现在没有办法分配出一个连续的8MB的空间了,只能分配最多最多6MB连续的内存空间, 如下图所示。

而现在存在分页,虚拟地址,我们完全可以分配连续的8MB的虚拟地址空间,其中2MB映射到物理内存的中间那个2MB空隙,其余6MB映射到最后剩余的6MB。

由此可见,分页是十分必要的,那么下面就来介绍一下如何实现分页&虚拟内存管理

地址转换过程

我们先来看一下虚拟地址是如何转换为物理地址的 完整的转换过程为

虚拟地址 --> (GDT) --> 线性地址 --> (Page Table) --> 物理地址

关于VirtualAddr -> LinearAddr 的过程我在之前的文章中有过介绍,这里就不做说明,想要跳过那个文章的读者可以简单的理解为目前的虚拟地址和线性地址值是相同的,因而我们直接从线性地址出发。首先来看下图

 

(图片来源:Intel® 64 and IA-32 Architectures Software Developer’s Manual)

线性地址为32位的地址, 其中高十位为 Page Directory,中间十位为 Page Table,最后十二位是 Offset。过程如下:

  1. 根据 CR3 寄存器(忘记了寄存器的功能的话戳这里)找到了页目录表的地址。
  2. 根据 Linear Address 的高十位与页表目录地址相加,找到了对应的页目录项(PDE)。
  3. 页目录项内存有该页目录的起始地址,将此地址与 Linear Address 21 – 12 位(即中间十位)相加,找到对应的页表项(PTE)
  4. 根据页表项中记载的物理页地址,找到对应的物理页起始地址,再与 Offset 相加,对应到实际的物理地址。

通过上面的过程就实现了线性地址到物理地址的转换,可以看出,页表和页目录在这个过程中扮演了十分重要的角色,下面就来介绍一下他们的结构。

结构

一个页目录项(PTE)和页表项(PDE)均占用 4Bytes 空间

(图片来源:Intel® 64 and IA-32 Architectures Software Developer’s Manual)

如上图所示,这是一个 Page Table Entry (页面大小为4K)

首先我们看 Bit 0 ,这是 Present bit,只有当这个 Bit 为 1 的时候此项才表示一个 PTE(或者PDE),否则就是一个无效的表项。

Bit 1 表示这个页面的读写权限,当这个位被置 1 的时候 表示可读可写, 为 0 则表示只读 ,不过这里要注意一点,对于 Ring0 且 CR0 的 WP 位为 0 情况来说,Ring0 可以对只读页面进行写入,如果想要让 Ring 0 也不可以写入只读页面,需要将 CR0 的 WP 位置1

Bit 2 表示这个页面是系统页面还是用户页面,如果是系统页面则用户态无法使用此页面。

后续的标志位暂时不介绍。我们来看高20位, 这里表示了物理页的起始地址,如果这是一个页目录项而不是页表项,则这里表示的是页目录的起始物理地址

转换缓存

通过上述的过程我们也可以看出, Page Transform 的过程需要多次读取内存,会映像执行效率,为了解决这个问题,CPU对转换信息进行了缓存,如  TLB, PCID  等技术,这些不在本文进行介绍,这里要说明的是,因为缓存的存在,导致如果更新了已被缓存的页表项的信息(如修改FLAG, 或者物理地址),我们需要使缓存失效,具体的做法就是重新装载一次 CR3 寄存器。

示例

说了这么多理论知识,我们来进行几个实际的操作看看。我们基于 linux0.11 的模型来进行下面四个实验(毕设结束后会放出git repo,目前暂无)

  • 使得某个特定的线性地址无效 (下文有介绍)
  • 将线性地址映射到给定的物理地址 (提示,查看 mm.c put_page 函数)
  • 修改该页的权限为只读并验证  (修改 FLAG 的另一个实验)
  • 给出当前线性地址所在页的详细信息 (打印出必要的FLAG信息,以及该线性地址对应的物理页地址)

disable_linear 实现

我们设计了这样的函数原型:

void disable_linear(unsigned long addr)

这个函数内我们需要对线性地址进行禁用, 根据上文中所介绍的,使得线性地址无效,实际上就是使得那个对应的页表项无效,因而我们需要通过线性地址对应到其页表项,并对该页表项的 Bit 0 清零。如何 Disable 与 Reload TLB 留给大家自行实现

linear_to_pte这个函数的实现过程实际上就是地址转换过程的前三步, 实现的时候要注意移位操作不要出问题,其他的没有什么难点

这里给出一个实现

上面的代码对页目录项是否存在,以及是否是页目录项进行了判断,失败将返回 0 。

下面我们需要对函数的正确性进行验证,由于此代码版本还没有补充缺页异常的处理代码,因而当访问失效的虚拟内存地址时,会引发Page Fault -> Double Fault -> Triple Fault最后导致我们的OS不断重启,我们来验证一下,验证用代码如下:

运行之后, 看到 qemu / bochs 的确在不停的 reboot , 并且可以通过 bochs 的 GUI 界面看到我们的页表由原有的16MB一致映射变为了中间缺少 0xdad000 页。

下面以实验结果截图结束本文

[Linux 0.11] Draft 4 GCC Assembly

[Linux 0.11] Draft 4 GCC Assembly

全文参考 https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html#Extended-Asm

阅读文档永远比阅读博客能获得更多的信息哦~

本文对 GCC Assembly 进行总结和介绍,也是个人的笔记,欢迎各位指正,内容供参考

* Basic Asm — 基本不能用的 assembly
* Extended Asm 功能强大的可扩展的ASM

Read More Read More

Eudyptula Challenge 1 — 8 总结

Eudyptula Challenge 1 — 8 总结

TL;DR

(PS: 昨天竟然在一个非计算机领域的朋友口中听到TLNR好神奇)

从开始做eudyptula-challenge已经有一个多月了,也从原来的连第一关都会卡关好久到现在第八关只用了不到四十分钟的时间就写好了(虽然第八关的coding要求很简单,主要是要练习git send-mail的使用方法)随着Challenge的进行,之前关卡学到的一些东西难免会遗忘,因此在继续进行之前,现将前面学到的知识进行总结。注意: 本文不是Eudyptula Challenge的攻略,Eudyptula Challenge明确禁止了对答案代码的公布和分享,个人也赞同这种做法,毕竟是Challenge,需要你自己研究,而不是直接上网就能搜到答案(尽管现在的确能搜到答案了,比如某章鱼猫((

Intro

What is Eudyptula Challenge?

这里就引用官网的介绍了

The Eudyptula Challenge is a series of programming exercises for the Linux kernel, that start from a very basic “Hello world” kernel module, moving on up in complexity to getting patches accepted into the main Linux kernel source tree.

How does it work?

官网上也给了相应的介绍,不过窝认为从一个例子来介绍更为形象:

Eudyptula-Challenge的评判系统是由”A set of convoluted shell scripts that are slow to anger and impossible to debug.”(摘自官网)来进行的,也就是全部自动评测(不过有的时候它的只能程度让我猜想后面有人在操作*****(大雾

以一个Task为例, 当你注册成功Eudyptula Challenge之后,会收到一封说明邮件以及你的第一个任务,之后你所有的任务提交都将通过在第一个任务里给你分配的ID以plain-text mail的形式进行。

当你收到一个Task的时候,根据相应的知识完成任务要求的代码之后,你需要通过纯文本邮件客户端(如mutt)将proof运行结果的输出作为正文,将写好的代码作为附件(这里不能用gmail的plain-text模式,因为它会把邮件附件转为base64格式)通过客户端发送给[email protected],之后你会收到一封通知邮件,表示系统已经成功收到你的提交(有可能收不到,因为脚本也许会卡住,这时候你如果等了一天还没收到,那你可以再次发送一封,不要频繁重发,小企鹅会生气的(不要问我怎么知道的Orz))

通知邮件的格式是这样的

可以看到上一个最近处理的提交时间,以及当前你所在Task的队列里有多少人在你的前面,一般来说从Task01-Task08都是平均一天之内就会回复你的Submit的结果,除非是脚本出故障了(

然后只需要等待结果,在此期间你可以看看番,学学其他有趣的东西比如日语,比如机器学习( “There is a lot more
in life other than Linux kernel programming.”

结果到达之后,如果你成功通过这个Task,那么会收到Congrats以及下一个Task的任务邮件,如果你没有通过,你会收到具有一定指导信息的来自小企鹅的建议(代码逻辑错误,不够精简,格式不正确,etc)

以上就是Eudyptula Challenge的一个完整的流程~ 那么下面开始总结

Task 01

主要掌握了编写module Makefile的方法,以及module的最最最基本的骨架, init函数和cleanup函数 ,以及如何设置mutt客户端(这个好像是弄得最久的?) 关于mutt客户端的设定方法,参考我的上一篇文章, 关于simplest module的编写 参考本文即可 http://www.tldp.org/LDP/lkmpg/2.6/html/x121.html

Task 02

编译内核,使用menuconfig, config或者xconfig设置内核参数,编译自定义的内核,了解了linux-git tree 以及 linux version的命名方式 参考 https://www.kernel.org/doc/html/latest/process/howto.html 中的kernel developing process

在这里简述一下kernel develop的过程

  • 当某一个4.x版本发行之后,会有两周的窗口期,这个窗口期内可以提交大的修改,以及feature patch,通常情况下,这些patch都已经在 -next tree里存在了几周
  • 两周窗口期后,-rc1 版本会发布 正如其名, make the kernel as rock solid as possible( rc = rock ) 进入到rc1的patch应当修复regression问题 [ 4.10-rc1]
  • 当Linus认为当前代码tree已经处于可以进行充分测试的状态的时候,那么将会发布新的-rc版本,大约一周会发布一个-rc版本 [4.10-rc8]
  • 大概经过6周的发布过程,内核变得稳定。[4.10 发布]

编译内核之后,提交dmesg和uname -a信息作为任务验证信息即可

 

Task 03 – 04

如何提交Patches https://www.kernel.org/doc/html/latest/process/submitting-patches.html 

内核代码风格

Task 05

编写USB热加载的模块 要求编写一个模块在USB键盘插入到机器的时候自动加载此模块

参考内核的相关文档(writing_usb_driver.tmpl) 如果想要实现hotplug的话,需要建立一个MODULE_DEVICE_TABLE,它用于告诉内核,这个module支持相应的设备(提供vendorID & DeviceID)

之后需要实现一个用于热加载的函数probe,然后就可以了

 

Task 06

这里要求实现一个misc character device了, 要求这个device能够进行读写,并且执行相应的读写之后的处理逻辑。

这里要求学会如何注册misc_device, 以及了解file_operations结构体,并且为misc_device编写read write两个file_operation

内核内存区和用户内存区不能进行直接共享,需要通过copy_from_user以及 copy_to_user这两个函数进行内核和用户内存的拷贝

另外有两个非常方便的wrapper函数 simple_read_from_buffer simple_write_to_buffer

Task 07

编译 linux-next kernel,不过这里被一个kernel的bug卡住,编译好的新kernel启动的时候hang住

Task 08

将Task 06写的device放到debugfs中,而不是/dev下,要求实现并发 并要求使用git send-mail发送patch

debugfs创建文件和dir均很简单,在此不进行阐述。

为了实现并发,需要信号量或者是自旋锁。这里使用了rw_mutex (多写多读)。

关于自旋锁,信号量之后会考虑写文章进行解释

然后就是git send-mail这里要注意在format-patch的时候就加上的几个参数

--subject-prefix  加上ID prefix

--in-reply-to 第一封邮件的MessageID

--thread 以thread的形式发送

关于git send mail的配置不在这里进行说明,可以很容易的找到相应的配置方法

 

 

IO 多路复用 — select 和 poll

IO 多路复用 — select 和 poll

本文为 高性能网络编程学习 系列文章的第2篇

下面我们使用select, poll, epoll来进行IO multiplexing 本文我们演示 select 和 poll做IO多路复用

select的用法查看man page就可以得到,这里只列出遇到的问题

  • nfds参数,表明要watch的最大fd的数字 举例说明,如果你要watch的文件描述符为24 — 31,那么你应该将nfds设置为32
  • 为了防止SIGPIPE信号终止程序运行,要讲SIGPIPE信号忽略掉

代码如下

进行到这里的时候遇到了一个很费解的问题,server端在读取数据的时候会收到recv(): connection reset by peer这样的错误,使用tcpdump抓包查看后,发现client关闭链接的时候(cli.Close)并没有发送FIN给server端,而是直接关闭了链接,这时server再请求读取client的数据或者发送数据给client就会收到cli发来的RST(connection reset by peer) 关于这个问题的具体产生原因,目前有一个原因

  • 当客户端关闭链接的时候内核network buffer内还有数据,则不会发送FIN,而是发送RST

其他的原因还在调查,待定

ULK Chapter2 总结

ULK Chapter2 总结

本章的知识结构如下

地址转换过程

谈到内存地址,具体来讲有三种不同类型的地址,逻辑地址,线性地址,物理地址。

  • 逻辑地址对应内存的分段
  • 线性地址对应分页
  • 物理地址对应到硬件芯片上的内存单元的地址

MMU通过Segment Unit与Paging Unit两个硬件电路将一个逻辑地址转为物理地址, 具体转换过程如上代码段所示

下面对整个转换过程进行概述

段选择符

[0-1]RPL: 请求者特权级

[2]TI: Table Indicator, 指明是从GDT还是LDT中取出段描述符(Segment Descriptor)

[3-15]index:用来指定从GDT中第index项取出Segment Descriptor

段描述符

对段描述符的解释参考 [不是科普向?] RE: 从零开始的操作系统开发 第二集 中相应内容即可

Logical Addr ===> Linear Addr

逻辑地址的高16位为段选择符(Segment Selector)其余32位(或者64位)为偏移量(Offset)

流程如下

  1. 检查TI确定是从GDT(TI=0)还是从LDT(TI =1)中选择段描述符
  2. 从Segment Selector的index字段计算出段描述符的地址,计算方法 index * 8 (一个Segment Descriptor大小为8) 并与gdtr/ldtr中的内容相加得到Segment Descriptor
  3. 把逻辑地址的offset字段与Segment Descriptor中的Base字段相加,得到Linear Address

 

而Linux中的分段只是一个兼容性考虑,分段和分页的作用是重复的,分页能以更精细的粒度对内存进行管理,因而在Linux中分页是主要的手段,Linux分段中的用户代码段,数据段,内核代码段,数据段,都是以Base = 0 ,因而Linux下的逻辑地址和线性地址是一致的,(因为Base = 0 所以 Linear Address = Base + Offset = Offset) 即逻辑地址的偏移量和线性地址的值是相等的

 

Linear Addr ==> Physical Addr

至此我们已经得到了线性地址,下面需要将线性地址通过分页单元转为物理地址,下面以基本的分页模型对分页进行解释

80×86的常规分页结构为

页目录 页表 页框

如图

如图,Page Directory和PageTable的结构类似,都是由一些flag bit加上Field字段,Field字段表示页框的物理地址,如果是一个PageTable的话,那么这个页框就含有一页数据,Page Directory的话,页框内含有的是一个页的PageTable(页表的大小就是一个PageTable)

 

寻址的方式如下,首先根据CR3寄存器的内容,找到PageDirectory入口的物理地址,然后加上Linear Addr中的DIRECTORY,找到对应的PDE项,并根据此内容找到对应的Page Table的物理地址,并根据Linear Addr中的TABLE找到相应的Page即页框的物理地址,最后将此物理地址加上Linear Addr的OFFSET字段,最后得到物理地址

 

而在64位系统上,如果依旧采用这种最基本的分页结构的话,那么假设页框大小为4K,所以OFFSET位依旧为12bit,然后其余的52bit可以分给PT(Page Table的简称,下同)和PD(Page Directory的简称,下同),这样就会导致我们每个进程的页目录和页表变得非常非常多,超过256000项

因为这个原因,所以对于64位处理器的分页系统,都使用了更多级别的分页级别,如x86_64使用48位寻址,分页为4级线性地址分级为 9 + 9 + 9 + 9 + 12 如下图所示

原理都是一样的,只不过分页级别变多了

以上就是Logical Address ===> Physical Address的转换的大致流程

 

缓存技术

因为CPU Register的读取和内存的读取速度相差甚大,为了缩小这个差距,避免CPU等待过长的时间,使用缓存技术来将内存中的部分数据缓存在高速静态RAM(SRAM)里,即为高速缓存技术(Hardware Cache)

此外,将Logical Address转换为Physical Address也需要多次进行内存的读取(查找各级页表),为了加速此过程,引入了转换后援缓冲器Translation Lookaside Buffer(TLB)技术

Hardware Cache

对高速缓存的原理描述超出本文的范围,这里仅对高速缓存的读写方式进行一定说明:

在更新内存数据的时候,是同时更新高速缓存和内存的数据,还是仅仅更新缓存的数据,根据这个有两种不同的写策略

  • 通写(write-through): 既写RAM也写缓存
  • 回写(write-back): 只写缓存,只有当需要FLUSH的时候才更新RAM

操作系统可以针对不同的页框配置不同的告诉缓存管理策略,通过PCD位和PWT位

  • PCD表示是否对此页框启用告诉缓存
  • PWT表示是否采用write-through的策略

在Linux下,对全部的页框都启用告诉缓存,并且都采用write-back策略

TLB(快表)

TLB的作用是将Logical Address对应的Linear Address缓存起来,以加速对内存的访问

但是这个缓存是有失效期的,最明显的一个失效就是当PD都被替换了的时候,也就是cr3的寄存器内容更新了,硬件上,当cr3更新的时候,TLB的内容会自动失效

如何能够更好的利用TLB来加速访问是对Linux性能影响十分重要的一部分,为了避免多处理器系统上无用的TLB刷新,内核使用一种叫做Lazy TLB的技术,关于Lazy TLB技术的具体实现之后补充

不同的分页方式

上述已经对常规分页进行举例了,下面对不同的几种分页方式进行简单整理

扩展分页

80×86模型的另一种分页模式,页框大小为4MB而不是4KB,用于把大段连续的线性地址转换成相应的物理地址,因为没有了PT只有PD,节省了内存,同时PT—>Phy而不是PT–>PD–>Phy,少了一级转换效率也相应提高,

物理地址扩展(PAE)分页机制

早些时候,内存容量都很少,而当需要大内存(>4G)的服务器&程序出现的时候,上述的寻址方式就不能使用了,因而Intel将内存地址位数从32 –>36位(即将引脚从32个扩展到36个) 而之前的所有的地址转换都是从32位Linear Address转换到32位Physical Address的,需要有一种新的转换机制,将32bit linear addr->36bit phy addr,这种机制即为PAE机制,详情可以参考Intel手册 Vol3A相应的内容

Linux中的实现

对于Linux的具体处理将在之后在整理

 

 

 

将内核编译到自定义的目录下

将内核编译到自定义的目录下

参考wiki: https://wiki.archlinux.org/index.php/Kernels/Traditional_compilation

使用ArchLinux作为构建Linux的环境

方法如下 假设我们的customized directory为kernel-build

我们必须在kernel-tree目录结构下对内核进行编译,假设kernel-tree目录名为linux-kernel

下面是具体的操作:

在 make menuconfig 的时候,最好对内核版本进行修改,使之不会在make modules_install的时候覆盖掉现有内核的modules

修改途径为General Setup里的Local Version项

这样执行之后,应该在arch/ARCH/boot/下面存在bzImage内核镜像,并且modules应该被安装在了/lib/modules/<linux-version>-<localversion> 下

下一步操作, 修改linux.preset文件,并创建initrd文件

修改linux.preset文件, 修改完毕后的内容类似下面

我们需要修改ALL_kver, default_image, fallback_image三个选项,使其将image保存到指定的目录下

然后使用

创建initrd, initrd-fallback,目前kernel-build目录应该有如下文件:

然后使用

就可以运行我们自定义的Linux Kernel了,可以使用uname -a查看Kernel Version~

不过到这里我们仅仅完成了一个RAMDisk的Kernel,没有任何的文件系统被挂载,只有一个rescue filesystem和busybox的一些东西能使用,为了构建一个能够正常使用的Linux Image,包含一个Distro应该有的程序,下面将通过Linux From Scratch项目一步步构建一个可用的自己的Distro

多进程&多线程 echo server实现

多进程&多线程 echo server实现

本文为 高性能网络编程学习 系列文章的第1篇

 

多进程版本

本文承接上文的单进程 echo server 建立一个多进程的echo server。代码的改动不多,下面贴一下完整的代码

首先来查看一下fork的整个流程,document_2016-12-24_17-31-43

如图,fork之后子进程会调用read/write进行IO操作,而父进程会再次转到执行accept,使得每一个client都会fork一个进程来执行IO操作。下面记录并描述一下在写这个代码的时候遇到的几个问题

在使用fork的时候可能大家也遇到过这个现象,就是自己的进程莫名其妙的变成了后台进程,比如下面这段代码:

这段代码fork了两个进程,其中一个执行while(1)死循环在那里,另一个调用exit(0)退出,执行这段代码之后, 用ps可以查看到此进程的PPID(parent pid)变为了1。 其实这个问题很好解释,注意看 if 的判断,执行while(1)的并不是父进程,而是父进程fork出来的子进程,而父进程在子进程退出前就退出了,因而子进程变为孤儿进程,被init(pid=1)收养,所以就出现了上述的PPID=1的效果

 

第二个问题要注意的是关闭socket的操作,要在父子进程均关闭,只关闭子进程的socket对父进程同样fd的socket是没有影响的。

运行一下我们的benchmark程序,效果如下

可以看到,此性能相比单进程的已经好了很多,不过fork进程有个很致命的问题,当进程数过多的时候,fork会失败掉;以及进程切换开销会很大,fork进程数不受我们控制,导致fork进程过多系统load变高,系统性能下降

 

多线程版本

和多进程的类似,不过有一些地方需要注意,代码如下

相对于多进程版, 我们把子进程交互IO的逻辑拿到了handle_conn这个函数里进行处理,通过pthread_create创建线程,这里我们需要为每一个线程分配pthread_t结构,pthread_create创建的进程所拿到的函数参数是由(void *)指向的地址传递的。

在编写代码的时候遇到这样几个问题,

 

其实都是因为同一个原因导致的。下面把出问题的代码片段post一下

 

上面的代码就是把targs作为一个Stack上的变量,每一次循环不改变targs的地址,只改变targs的值。而多线程之间是共享同一个内存空间的,因而,每一次改变的都是同一个targs,所以不同线程的handl_conn看到的targs都是同一个,这不是我们期望要的效果,这里和多进程就不一样了,如果是多进程改变一个同名的变量,是通过COW技术修改同名变量的副本,而不是直接对父进程上的同一个变量进行修改。

 

运行上述正确的代码的benchmark如下