线段树笔记

有这样一类问题,给定一个数列,让你求某段区间内和。如果对某个值或某段区间内的值进行修改后,如何快速的求和。如果线性执行更新操作或求和操作,无疑时间复杂度太大了。
那么借助分治的思想,在执行更新区间的操作时,把它转化为几段区间的更新,同样求和操作时,也通过维护分段区间的和来达到快速求区间和的问题。线段树就是利用二叉树这种数据结构,来维护区间信息的一种数据结构。

Read More

如何实现进程代码段的分页度量

之前通过读取/proc/pid/mem的方法读取某个进程的内存数据,mem内部是用copy_from_user实现的,是对虚拟地址进行的操作。但是在某一时刻,该进程的所有内存页不一定都已经被加载到内存。由于虚拟内存的存在,只有那页代码被访问到时(copy_from_user()会判断缺页的情况),才会产生缺页中断,将该页代码加载到内存。这种方式并不够理想,理想的方法是判断哪些数据页已加载到内存中,然后对其进行度量。

Read More

如何编写一个简单地内核模块

Linux给应用程序提供了丰富的api,但是有时候我们需要跟硬件交互,访问一些特权级信息,所以可以使用编写内核模块这种方式。
另外Linux是宏内核结构,效率非常高,没有微内核那样各个模块之间的通讯损耗,但是又不能方便的对内核进行改动,可扩展性和可维护性比较差,内核模块提供了一种动态加载代码的方式,弥补了宏内核的不足。

Read More

利用ICMPv4协议实现一个ping程序

Icmp(Internet Control Message Protocol)协议一般与IP协议结合使用,以便给IP协议提供诊断和控制信息。
Icmp通常被认为是Ip协议的一部分,传输的时候也是被封装在Ip报文内。
我们在判断网络状况时用的ping程序就利用了ICMP协议。接下来先运行系统上的ping程序,用tcpdump抓包查看一下传输的数据。
然后解释一下icmp数据报的各个字段。最后思考一下ping程序的结构,然后用c++实现一个自己的ping程序。

Read More