kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

1.5倍空间归并排序--Knuth

divide-and-conquer algorithm, in the style suggested by Knuth volume 3 (2nd edition),

1
2
3
4
5
6
7
8
   |-------------I-------------|-------------|

         p1            p2            ex

p1+p2原数组,p1前半部分,p2后半部分,ex额外空间
1、将p2用ex额外空间排到p2
2、将p1排到ex
3、将p2、ex合并到原数组

dd 命令

贴自http://www.chinaunix.net/old_jh/4/1025448.html dd 是 Linux/UNIX 下的一个非常有用的命令,作用是用指定大小的块拷贝一个文件,并在拷贝的同时进行指定的转换。

1. 命令简介

dd 的主要选项:

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
指定数字的地方若以下列字符结尾乘以相应的数字:
b=512, c=1, k=1024, w=2, xm=number m
if=file
输入文件名,缺省为标准输入。
of=file
输出文件名,缺省为标准输出。
ibs=bytes
一次读入 bytes 个字节(即一个块大小为 bytes 个字节)。
obs=bytes
一次写 bytes 个字节(即一个块大小为 bytes 个字节)。
bs=bytes
同时设置读写块的大小为 bytes ,可代替 ibs 和 obs 。
cbs=bytes
一次转换 bytes 个字节,即转换缓冲区大小。
skip=blocks
从输入文件开头跳过 blocks 个块后再开始复制。
seek=blocks
从输出文件开头跳过 blocks 个块后再开始复制。(通常只有当输出文件是磁盘或磁带时才有效)。
count=blocks
仅拷贝 blocks 个块,块大小等于 ibs 指定的字节数。
conv=conversion[,conversion...]
用指定的参数转换文件。
转换参数:
ascii 转换 EBCDIC 为 ASCII。
ebcdic 转换 ASCII 为 EBCDIC。
ibm 转换 ASCII 为 alternate EBCDIC.
block 把每一行转换为长度为 cbs 的记录,不足部分用空格填充。
unblock 使每一行的长度都为 cbs ,不足部分用空格填充。
lcase 把大写字符转换为小写字符。
ucase 把小写字符转换为大写字符。
swab 交换输入的每对字节。 
noerror 出错时不停止。
notrunc 不截短输出文件。
sync 把每个输入块填充到ibs个字节,不足部分用空(NUL)字符补齐。

2.实例分析

2.1.数据备份与恢复
2.1.1整盘数据备份与恢复

备份:
dd if=/dev/hdx of=/dev/hdy
将本地的/dev/hdx整盘备份到/dev/hdy
dd if=/dev/hdx of=/path/to/image
将/dev/hdx全盘数据备份到指定路径的image文件
dd if=/dev/hdx | gzip >/path/to/image.gz
备份/dev/hdx全盘数据,并利用gzip工具进行压缩,保存到指定路径
恢复:
dd if=/path/to/image of=/dev/hdx
将备份文件恢复到指定盘
gzip -dc /path/to/image.gz | dd of=/dev/hdx
将压缩的备份文件恢复到指定盘

2.1.2.利用netcat远程备份

dd if=/dev/hda bs=16065b | netcat < targethost-IP > 1234
在源主机上执行此命令备份/dev/hda
netcat -l -p 1234 | dd of=/dev/hdc bs=16065b
在目的主机上执行此命令来接收数据并写入/dev/hdc
netcat -l -p 1234 | bzip2 > partition.img
netcat -l -p 1234 | gzip > partition.img
以上两条指令是目的主机指令的变化分别采用bzip2 gzip对数据进行压缩,并将备份文件保存在当前目录。

2.1.3.备份MBR

备份:
dd if=/dev/hdx of=/path/to/image count=1 bs=512
备份磁盘开始的512Byte大小的MBR信息到指定文件
恢复:
dd if=/path/to/image of=/dev/hdx
将备份的MBR信息写到磁盘开始部分

2.1.4.备份软盘

dd if=/dev/fd0 of=disk.img count=1 bs=1440k
将软驱数据备份到当前目录的disk.img文件

2.1.5.拷贝内存资料到硬盘

dd if=/dev/mem of=/root/mem.bin bs=1024
将内存里的数据拷贝到root目录下的mem.bin文件

2.1.6.从光盘拷贝iso镜像

dd if=/dev/cdrom of=/root/cd.iso
拷贝光盘数据到root文件夹下,并保存为cd.iso文件

2.2.增加Swap分区文件大小

dd if=/dev/zero of=/swapfile bs=1024 count=262144
创建一个足够大的文件(此处为256M)
mkswap /swapfile
把这个文件变成swap文件
swapon /swapfile
启用这个swap文件
/swapfile swap swap defaults 0 0
在每次开机的时候自动加载swap文件, 需要在 /etc/fstab 文件中增加一行

2.3销毁磁盘数据

dd if=/dev/urandom of=/dev/hda1
利用随机的数据填充硬盘,在某些必要的场合可以用来销毁数据。执行此操作以后,/dev/hda1将无法挂载,创建和拷贝操作无法执行。

2.4磁盘管理
2.4.1.得到最恰当的block size
1
2
3
4
dd if=/dev/zero bs=1024 count=1000000 of=/root/1Gb.file
dd if=/dev/zero bs=2048 count=500000 of=/root/1Gb.file
dd if=/dev/zero bs=4096 count=250000 of=/root/1Gb.file    
dd if=/dev/zero bs=8192 count=125000 of=/root/1Gb.file

通过比较dd指令输出中所显示的命令执行时间,即可确定系统最佳的block size大小

2.4.2测试硬盘读写速度
1
2
dd if=/root/1Gb.file bs=64k | dd of=/dev/null
dd if=/dev/zero of=/root/1Gb.file bs=1024 count=1000000

通过上两个命令输出的执行时间,可以计算出测试硬盘的读/写速度

2.4.3.修复硬盘

dd if=/dev/sda of=/dev/sda
当硬盘较长时间(比如1,2年)放置不使用后,磁盘上会产生magnetic flux point。当磁头读到这些区域时会遇到困难,并可能导致I/O 错误。当这种情况影响到硬盘的第一个扇区时,可能导致硬盘报废。上边的命令有可能使这些数据起死回生。且这个过程是安全,高效的。

offsetof宏 container_of宏

Linux内核中,用两个非常巧妙地宏实现了,一个是offsetof宏,另一个是container_of宏,下面讲解一下这两个宏。

1. offsetof宏

【定义】:
1
#define offsetof(TYPE, MEMBER) ((size_t) & ((TYPE *)0)->MEMBER )
【功能】: 获得一个结构体变量成员在此结构体中的偏移量。
【例子】:
1
2
3
4
5
6
7
8
9
10
11
struct A 
	{ 
	int x ; 
	int y; 
	int z; 
}; 

void main() 
{ 
	printf("the offset of z is %d",offsetof( struct A, z )  ); 
} 

// 输出结果为 8

【分析】:

该宏,TYPE为结构体类型,MEMBER 为结构体内的变量名。
(TYPE )0) 是欺骗编译器说有一个指向结构TYPE 的指针,其地址值0
(TYPE
)0)->MEMBER 是要取得结构体TYPE中成员变量MEMBER的地址. 因为基址为0,所以,这时MEMBER的地址当然就是MEMBER在TYPE中的偏移了。

2. container_of宏(即实现了题目中的功能)

【定义】:
1
#define container_of(ptr, type, member)   ({const typeof( ((type *)0)->member ) *__mptr = (ptr); (type *)( (char *)__mptr - offsetof(type,member) );})
【功能】:

从结构体(type)某成员变量(member)指针(ptr)来求出该结构体(type)的首指针。

【例子】:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct A 
{ 
	int x ; 
	int y; 
	int z; 
}; 
 
struct A myTest; 
 
int *pz = &myTest.z; 
 
struct A* getHeaderPtr( int *pz ) 
{ 
	return container_of( pz , struct A, z ); 
} 
【分析】:

(1) typeof( ( (type )0)->member )为取出member成员的变量类型。
(2) 定义__mptr指针ptr为指向该成员变量的指针(即指向ptr所指向的变量处)
(3) (char
)__mptr - offsetof(type,member)) 用该成员变量的实际地址减去该变量在结构体中的偏移,来求出结构体起始地址。
(4) ({ })这个扩展返回程序块中最后一个表达式的值。

Universal Build-ID

http://fedoraproject.org/wiki/Summer_Coding_2010_ideas_-_Universal_Build-ID

Summary

Build-IDs are currently being put into binaries, shared libraries, core files and related debuginfo files to uniquely identify the build a user or developer is working with. There are a couple of conventions in place to use this information to identify “currently running” or “distro installed” builds. This helps with identifying what was being run and match it to the corresponding package, sources and debuginfo for tools that want to help the user show what is going on (at the moment mostly when things break). We would like to extend this to a more universial approach, that helps people identify historical, local, non- or cross-distro or organisational builds. So that Build-IDs become useful outside the current “static” setup and retain information over time and across upgrades.

Build-ID background

Build-IDs are unique identifiers of “builds”. A build is an executable, a shared library, the kernel, a module, etc. You can also find the build-id in a running process, a core file or a separate debuginfo file.

The main idea behind Build-IDs is to make elf files “self-identifying”. This means that when you have a Build-ID it should uniquely identify a final executable or shared library. The default Build-ID calculation (done through ld –build-id, see the ld manual) calculates a sha1 hash (160 bits/20 bytes) based on all the ELF header bits and section contents in the file. Which means that it is unique among the set of meaningful contents for ELF files and identical when the output file would otherwise have been identical. GCC now passes –build-id to the linker by default.

When an executable or shared library is loaded into memory the Build-ID will also be loaded into memory, a core dump of a process will also have the Build-IDs of the executable and the shared libraries embedded. And when separating debuginfo from the main executable or shared library into .debug files the original Build-ID will also be copied over. This means it is easy to match a core file or a running process to the original executable and shared library builds. And that matching those against the debuginfo files that provide more information for introspection and debugging should be trivial.

Fedora has had full support for build-ids since Fedora Core 8: https://fedoraproject.org/wiki/Releases/FeatureBuildId

Getting Build-IDs

A simple way to get the build-id(s) is through eu-unstrip (part of elfutils).

build-id from an executable, shared library or separate debuginfo file:
$ eu-unstrip -n -e <exec|.sharedlib|.debug>

build-ids of an executable and all shared libraries from a core file:
$ eu-unstrip -n –core

build-ids of an executable and all shared libraries of a running process:
$ eu-unstrip -n –pid

build-id of the running kernel and all loaded modules:
$ eu-unstrip -n -k

强制内联和强制不内联

1.强制不内联

一个函数,如果代码量比较少的话,用 -O3优化开关的话,gcc有可能将这个函数强制内联(inline)即使,你在函数前没有写inline助记符。
如果是一个手写汇编的函数,那样的话很有可能破坏参数。gcc里有强制不内联的,用法如下

1
void foo() __attribute__((noinline));

但是有的gcc可能会忽略 noinline。
那么你可以将你实现的这个函数写到调用函数之后,就不会被inline了。这是因为编译器gcc只内联当前函数之前可见(实现代码在前)的函数。

2.优化时无法识别inline函数中的ASM汇编

当GCC尝试内联一个函数时,如果该函数中存在内联汇编,则该汇编语句块可能被丢弃;

1
2
3
4
5
6
7
8
9
10
11
12
13
__inline__ __attribute__((always_inline))int Increment(int volatile *add, int inc)
{
    int res;
    __asm__
    (
    "lock \n\t"
    "xaddl %0,(%1)\n\t"
    :"=r"(res)
    :"r"(add),"0"(inc)
    :"memory"
    );
    return res;
}