和内核中的hash table一样，内核中的红黑树比较“裸”。出于效率方面的考虑，并没有把所有的操作都封装起来。
在执行插入操作的时候，需要使用者自己按照搜索二叉树的方法找到想要插入的节点的父节点，然后调用rb_link_node函数将节点插入，再调用rb_insert_color函数对红黑树进行适当的“旋转”。
而在搜索红黑树的时候，则需要使用者自己按照普通二叉树的搜索方法进行搜索。当然，如何比较键值的大小也是使用者自己决定的。
内核的Documentation目录下有一篇rbtree.txt的文档详细的介绍了该如何使用红黑树。
下面是我写的一个使用红黑树的小例子，可在2.6.32下运行。在这个小程序中，coef被当作键值来使用。
#include <linux/init.h>
#include <linux/module.h>
#include <linux/rbtree.h>
struct q_coef
{
u8 coef;
u8 index;
struct rb_node node;
};
#define COEF_NUM 15
u8 coef[15] = {
0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80,
0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13,
};
struct q_coef q_coef[COEF_NUM];
static void q_coef_init(void)
{
int i;
memset(&q_coef, 0, sizeof(q_coef));
for (i = 0 ; i < COEF_NUM ; i++) {
q_coef[i].coef = coef[i];
q_coef[i].index = i + 1;
}
}
struct rb_root q_coef_tree = RB_ROOT;
static int q_coef_insert(struct rb_root *root, struct q_coef *data)
{
struct rb_node **new = &(root->rb_node), *parent = NULL;
/* Figure out where to put new code */
while (*new) {
struct q_coef *this = rb_entry(*new, struct q_coef, node);
parent = *new;
if (data->coef < this->coef)
new = &((*new)->rb_left);
else if (data->coef > this->coef)
new = &((*new)->rb_right);
else
return -1;
}
/* Add new node and rebalance tree. */
rb_link_node(&data->node, parent, new);
rb_insert_color(&data->node, root);
return 0;
}
static struct q_coef *q_coef_search(struct rb_root *root, u8 coef)
{
struct rb_node *node = root->rb_node;
while (node) {
struct q_coef *data = rb_entry(node, struct q_coef, node);
if (coef < data->coef)
node = node->rb_left;
else if (coef > data->coef)
node = node->rb_right;
else
return data;
}
return NULL;
}
static int rbtest_init (void)
{
int i;
struct q_coef *ptr;
struct rb_node *node;
int ret;
q_coef_init();
for (i = 0 ; i < COEF_NUM ; i++) {
ret = q_coef_insert(&q_coef_tree, &q_coef[i]);
if (ret < 0) {
printk(KERN_WARNING "q_coef_insert failed, i=%d\n", i);
return -1;
}
}
printk(KERN_INFO "search by input order:\n");
for (i = 0 ; i < COEF_NUM ; i++) {
ptr = q_coef_search(&q_coef_tree, coef[i]);
if (ptr == NULL) {
printk(KERN_WARNING "q_coef_search failed, i=%d\n", i);
return -1;
}
printk(KERN_INFO "coef[%02d]=0x%02x ptr->coef=0x%02x ptr->index=%02d\n",
i, coef[i], ptr->coef, ptr->index);
}
printk(KERN_INFO "search from first:\n");
for (node = rb_first(&q_coef_tree) ; node ; node = rb_next(node)) {
ptr = rb_entry(node, struct q_coef, node);
printk(KERN_INFO "ptr->coef=0x%02x ptr->index=%02d\n", ptr->coef, ptr->index);
}
printk(KERN_INFO "search from last:\n");
for (node = rb_last(&q_coef_tree) ; node ; node = rb_prev(node)) {
ptr = rb_entry(node, struct q_coef, node);
printk(KERN_INFO "ptr->coef=0x%02x ptr->index=%02d\n", ptr->coef, ptr->index);
}
printk(KERN_INFO "rbtest done\n");
return -1;
}
static void rbtest_exit (void)
{
}
module_init(rbtest_init);
module_exit(rbtest_exit);
MODULE_LICENSE("Dual BSD/GPL");
2010年11月14日星期日
2010年11月12日星期五
GF(2**8)的计算器
实现生成多项式为F(x) = x**8 + x**4 + x**3 + x**2 + 1的伽罗华域的加，减，乘，除，乘方运算。可以带括号。
将下面代码保存为pq.py,chmod +x pq.py，然后./pq.py即可进入计算器。按q退出。
解析算数表达式的程序有些问题，不支持乘方和其他运算混合。
#! /usr/bin/env python
# reference to http://www.cnblogs.com/flyingbread/archive/2007/02/03/638932.html
import re
def is_operator(ch):
if ch == '+' or ch == '-' or ch == '*' or ch == '/' or ch == '**':
return True
else:
return False
def is_parentheses_left(ch):
if ch == '(':
return True
else:
return False
def is_parentheses_right(ch):
if ch == ')':
return True
else:
return False
def opt_priority(ch):
if ch == '+' or ch == '-':
priority = 1
elif ch == '*' or ch == '/':
priority = 2
elif ch == '**':
priority = 3
else:
# maybe '('
priority = 0
return priority
# now we only support 2 operation number
def get_operation_number(ch):
if ch == '+' or ch == '-' or ch == '*' or ch == '/' or ch == '**':
return 2
else:
return 1
# primitive polynomial for GF(2**8)
# F(x) = x**8 + x**4 + x**3 + x**2 + 1
def do_add(a, b):
return a ^ b
def do_sub(a, b):
return a ^ b
gflog = [
0x00, 0x00, 0x01, 0x19, 0x02, 0x32, 0x1a, 0xc6, 0x03, 0xdf, 0x33, 0xee, 0x1b, 0x68, 0xc7, 0x4b,
0x04, 0x64, 0xe0, 0x0e, 0x34, 0x8d, 0xef, 0x81, 0x1c, 0xc1, 0x69, 0xf8, 0xc8, 0x08, 0x4c, 0x71,
0x05, 0x8a, 0x65, 0x2f, 0xe1, 0x24, 0x0f, 0x21, 0x35, 0x93, 0x8e, 0xda, 0xf0, 0x12, 0x82, 0x45,
0x1d, 0xb5, 0xc2, 0x7d, 0x6a, 0x27, 0xf9, 0xb9, 0xc9, 0x9a, 0x09, 0x78, 0x4d, 0xe4, 0x72, 0xa6,
0x06, 0xbf, 0x8b, 0x62, 0x66, 0xdd, 0x30, 0xfd, 0xe2, 0x98, 0x25, 0xb3, 0x10, 0x91, 0x22, 0x88,
0x36, 0xd0, 0x94, 0xce, 0x8f, 0x96, 0xdb, 0xbd, 0xf1, 0xd2, 0x13, 0x5c, 0x83, 0x38, 0x46, 0x40,
0x1e, 0x42, 0xb6, 0xa3, 0xc3, 0x48, 0x7e, 0x6e, 0x6b, 0x3a, 0x28, 0x54, 0xfa, 0x85, 0xba, 0x3d,
0xca, 0x5e, 0x9b, 0x9f, 0x0a, 0x15, 0x79, 0x2b, 0x4e, 0xd4, 0xe5, 0xac, 0x73, 0xf3, 0xa7, 0x57,
0x07, 0x70, 0xc0, 0xf7, 0x8c, 0x80, 0x63, 0x0d, 0x67, 0x4a, 0xde, 0xed, 0x31, 0xc5, 0xfe, 0x18,
0xe3, 0xa5, 0x99, 0x77, 0x26, 0xb8, 0xb4, 0x7c, 0x11, 0x44, 0x92, 0xd9, 0x23, 0x20, 0x89, 0x2e,
0x37, 0x3f, 0xd1, 0x5b, 0x95, 0xbc, 0xcf, 0xcd, 0x90, 0x87, 0x97, 0xb2, 0xdc, 0xfc, 0xbe, 0x61,
0xf2, 0x56, 0xd3, 0xab, 0x14, 0x2a, 0x5d, 0x9e, 0x84, 0x3c, 0x39, 0x53, 0x47, 0x6d, 0x41, 0xa2,
0x1f, 0x2d, 0x43, 0xd8, 0xb7, 0x7b, 0xa4, 0x76, 0xc4, 0x17, 0x49, 0xec, 0x7f, 0x0c, 0x6f, 0xf6,
0x6c, 0xa1, 0x3b, 0x52, 0x29, 0x9d, 0x55, 0xaa, 0xfb, 0x60, 0x86, 0xb1, 0xbb, 0xcc, 0x3e, 0x5a,
0xcb, 0x59, 0x5f, 0xb0, 0x9c, 0xa9, 0xa0, 0x51, 0x0b, 0xf5, 0x16, 0xeb, 0x7a, 0x75, 0x2c, 0xd7,
0x4f, 0xae, 0xd5, 0xe9, 0xe6, 0xe7, 0xad, 0xe8, 0x74, 0xd6, 0xf4, 0xea, 0xa8, 0x50, 0x58, 0xaf,
]
gfilog = [
0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13, 0x26,
0x4c, 0x98, 0x2d, 0x5a, 0xb4, 0x75, 0xea, 0xc9, 0x8f, 0x03, 0x06, 0x0c, 0x18, 0x30, 0x60, 0xc0,
0x9d, 0x27, 0x4e, 0x9c, 0x25, 0x4a, 0x94, 0x35, 0x6a, 0xd4, 0xb5, 0x77, 0xee, 0xc1, 0x9f, 0x23,
0x46, 0x8c, 0x05, 0x0a, 0x14, 0x28, 0x50, 0xa0, 0x5d, 0xba, 0x69, 0xd2, 0xb9, 0x6f, 0xde, 0xa1,
0x5f, 0xbe, 0x61, 0xc2, 0x99, 0x2f, 0x5e, 0xbc, 0x65, 0xca, 0x89, 0x0f, 0x1e, 0x3c, 0x78, 0xf0,
0xfd, 0xe7, 0xd3, 0xbb, 0x6b, 0xd6, 0xb1, 0x7f, 0xfe, 0xe1, 0xdf, 0xa3, 0x5b, 0xb6, 0x71, 0xe2,
0xd9, 0xaf, 0x43, 0x86, 0x11, 0x22, 0x44, 0x88, 0x0d, 0x1a, 0x34, 0x68, 0xd0, 0xbd, 0x67, 0xce,
0x81, 0x1f, 0x3e, 0x7c, 0xf8, 0xed, 0xc7, 0x93, 0x3b, 0x76, 0xec, 0xc5, 0x97, 0x33, 0x66, 0xcc,
0x85, 0x17, 0x2e, 0x5c, 0xb8, 0x6d, 0xda, 0xa9, 0x4f, 0x9e, 0x21, 0x42, 0x84, 0x15, 0x2a, 0x54,
0xa8, 0x4d, 0x9a, 0x29, 0x52, 0xa4, 0x55, 0xaa, 0x49, 0x92, 0x39, 0x72, 0xe4, 0xd5, 0xb7, 0x73,
0xe6, 0xd1, 0xbf, 0x63, 0xc6, 0x91, 0x3f, 0x7e, 0xfc, 0xe5, 0xd7, 0xb3, 0x7b, 0xf6, 0xf1, 0xff,
0xe3, 0xdb, 0xab, 0x4b, 0x96, 0x31, 0x62, 0xc4, 0x95, 0x37, 0x6e, 0xdc, 0xa5, 0x57, 0xae, 0x41,
0x82, 0x19, 0x32, 0x64, 0xc8, 0x8d, 0x07, 0x0e, 0x1c, 0x38, 0x70, 0xe0, 0xdd, 0xa7, 0x53, 0xa6,
0x51, 0xa2, 0x59, 0xb2, 0x79, 0xf2, 0xf9, 0xef, 0xc3, 0x9b, 0x2b, 0x56, 0xac, 0x45, 0x8a, 0x09,
0x12, 0x24, 0x48, 0x90, 0x3d, 0x7a, 0xf4, 0xf5, 0xf7, 0xf3, 0xfb, 0xeb, 0xcb, 0x8b, 0x0b, 0x16,
0x2c, 0x58, 0xb0, 0x7d, 0xfa, 0xe9, 0xcf, 0x83, 0x1b, 0x36, 0x6c, 0xd8, 0xad, 0x47, 0x8e, 0x00,
]
def do_mul(a, b):
if a == 0 or b == 0:
return 0;
else:
tmp = gflog[a] + gflog[b]
tmp = tmp % 255
return gfilog[tmp]
def do_div(a, b):
if a == 0:
return 0
elif b == 0:
print 'can not div 0'
return 0;
else:
tmp = gflog[a] - gflog[b]
if tmp < 0:
tmp = tmp + 255
return gfilog[tmp]
def do_power(a, b):
count = 0
result = 1
while (count < b):
result = do_mul(result, a)
count += 1
return result
def calc_once(num, ch):
if ch == '+':
ret = do_add(num[1], num[0])
elif ch == '-':
ret = do_sub(num[1], num[0])
elif ch == '*':
ret = do_mul(num[1], num[0])
elif ch == '/':
ret = do_div(num[1], num[0])
elif ch == '**':
ret = do_power(num[1], num[0])
else:
print 'unknow operation'
ret = 0
return ret
# 1. get ch from left to right
# 2. if ch is a number, output it
# 3. if ch is a operator or parenthese:
# a: if ch is '(', push to stack
# b: if ch is ')', pop stack until meet '('
# c: if ch is not parenthese, compare its priority with stack pop
# if ch priority is higher than the stack pop, push ch to stack
# else pop stack, push ch to stack
def midfix_to_posfix(midfix):
stack = []
posfix = []
for ch in midfix:
if is_parentheses_left(ch):
stack.append(ch)
elif is_parentheses_right(ch):
while True:
ch1 = stack.pop()
if is_parentheses_left(ch1):
break
else:
posfix.append(ch1)
elif is_operator(ch):
if len(stack) == 0:
stack.append(ch)
else:
ch1 = stack[-1]
if opt_priority(ch) > opt_priority(ch1):
stack.append(ch)
else:
ch1 = stack.pop()
posfix.append(ch1)
stack.append(ch)
else:
if len(ch) > 2 and ch[0:2] == '0x':
ch = int(ch, 16)
else:
ch = int(ch, 10)
posfix.append(ch)
while len(stack) != 0:
posfix.append(stack.pop())
return posfix
# get data from left to right
# if ch is a number, push to stack
# if ch is a operator, pop the number it needed, do calc, and push result to stack
# if data is paser comlete, pop the stack as result
def calc_posfix(posfix):
stack = []
for ch in posfix:
if is_operator(ch):
num = []
num.append(stack.pop())
if get_operation_number(ch) > 1:
num.append(stack.pop())
stack.append(calc_once(num, ch))
else:
stack.append(ch)
return stack.pop()
def main_loop():
# match all hex and dec number, and +,-,*,/,**
# note: hex must before dec number, and * must before **
print "please do not use ** mix with other operation, it's not support!"
regu_for_exp = re.compile('0x[0-9,a-f]+|[0-9]+|\*\*|\*|\+|\-|\/|\(|\)')
while True:
expression = raw_input('pq>:')
if expression != 'quit' and expression != 'q' and expression != 'exit':
midfix = regu_for_exp.findall(expression)
posfix = midfix_to_posfix(midfix)
result = calc_posfix(posfix)
if result is not None:
print "0x%02x" % result
else:
print result
else:
return
if __name__ == '__main__':
main_loop()
将下面代码保存为pq.py,chmod +x pq.py，然后./pq.py即可进入计算器。按q退出。
解析算数表达式的程序有些问题，不支持乘方和其他运算混合。
#! /usr/bin/env python
# reference to http://www.cnblogs.com/flyingbread/archive/2007/02/03/638932.html
import re
def is_operator(ch):
if ch == '+' or ch == '-' or ch == '*' or ch == '/' or ch == '**':
return True
else:
return False
def is_parentheses_left(ch):
if ch == '(':
return True
else:
return False
def is_parentheses_right(ch):
if ch == ')':
return True
else:
return False
def opt_priority(ch):
if ch == '+' or ch == '-':
priority = 1
elif ch == '*' or ch == '/':
priority = 2
elif ch == '**':
priority = 3
else:
# maybe '('
priority = 0
return priority
# now we only support 2 operation number
def get_operation_number(ch):
if ch == '+' or ch == '-' or ch == '*' or ch == '/' or ch == '**':
return 2
else:
return 1
# primitive polynomial for GF(2**8)
# F(x) = x**8 + x**4 + x**3 + x**2 + 1
def do_add(a, b):
return a ^ b
def do_sub(a, b):
return a ^ b
gflog = [
0x00, 0x00, 0x01, 0x19, 0x02, 0x32, 0x1a, 0xc6, 0x03, 0xdf, 0x33, 0xee, 0x1b, 0x68, 0xc7, 0x4b,
0x04, 0x64, 0xe0, 0x0e, 0x34, 0x8d, 0xef, 0x81, 0x1c, 0xc1, 0x69, 0xf8, 0xc8, 0x08, 0x4c, 0x71,
0x05, 0x8a, 0x65, 0x2f, 0xe1, 0x24, 0x0f, 0x21, 0x35, 0x93, 0x8e, 0xda, 0xf0, 0x12, 0x82, 0x45,
0x1d, 0xb5, 0xc2, 0x7d, 0x6a, 0x27, 0xf9, 0xb9, 0xc9, 0x9a, 0x09, 0x78, 0x4d, 0xe4, 0x72, 0xa6,
0x06, 0xbf, 0x8b, 0x62, 0x66, 0xdd, 0x30, 0xfd, 0xe2, 0x98, 0x25, 0xb3, 0x10, 0x91, 0x22, 0x88,
0x36, 0xd0, 0x94, 0xce, 0x8f, 0x96, 0xdb, 0xbd, 0xf1, 0xd2, 0x13, 0x5c, 0x83, 0x38, 0x46, 0x40,
0x1e, 0x42, 0xb6, 0xa3, 0xc3, 0x48, 0x7e, 0x6e, 0x6b, 0x3a, 0x28, 0x54, 0xfa, 0x85, 0xba, 0x3d,
0xca, 0x5e, 0x9b, 0x9f, 0x0a, 0x15, 0x79, 0x2b, 0x4e, 0xd4, 0xe5, 0xac, 0x73, 0xf3, 0xa7, 0x57,
0x07, 0x70, 0xc0, 0xf7, 0x8c, 0x80, 0x63, 0x0d, 0x67, 0x4a, 0xde, 0xed, 0x31, 0xc5, 0xfe, 0x18,
0xe3, 0xa5, 0x99, 0x77, 0x26, 0xb8, 0xb4, 0x7c, 0x11, 0x44, 0x92, 0xd9, 0x23, 0x20, 0x89, 0x2e,
0x37, 0x3f, 0xd1, 0x5b, 0x95, 0xbc, 0xcf, 0xcd, 0x90, 0x87, 0x97, 0xb2, 0xdc, 0xfc, 0xbe, 0x61,
0xf2, 0x56, 0xd3, 0xab, 0x14, 0x2a, 0x5d, 0x9e, 0x84, 0x3c, 0x39, 0x53, 0x47, 0x6d, 0x41, 0xa2,
0x1f, 0x2d, 0x43, 0xd8, 0xb7, 0x7b, 0xa4, 0x76, 0xc4, 0x17, 0x49, 0xec, 0x7f, 0x0c, 0x6f, 0xf6,
0x6c, 0xa1, 0x3b, 0x52, 0x29, 0x9d, 0x55, 0xaa, 0xfb, 0x60, 0x86, 0xb1, 0xbb, 0xcc, 0x3e, 0x5a,
0xcb, 0x59, 0x5f, 0xb0, 0x9c, 0xa9, 0xa0, 0x51, 0x0b, 0xf5, 0x16, 0xeb, 0x7a, 0x75, 0x2c, 0xd7,
0x4f, 0xae, 0xd5, 0xe9, 0xe6, 0xe7, 0xad, 0xe8, 0x74, 0xd6, 0xf4, 0xea, 0xa8, 0x50, 0x58, 0xaf,
]
gfilog = [
0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13, 0x26,
0x4c, 0x98, 0x2d, 0x5a, 0xb4, 0x75, 0xea, 0xc9, 0x8f, 0x03, 0x06, 0x0c, 0x18, 0x30, 0x60, 0xc0,
0x9d, 0x27, 0x4e, 0x9c, 0x25, 0x4a, 0x94, 0x35, 0x6a, 0xd4, 0xb5, 0x77, 0xee, 0xc1, 0x9f, 0x23,
0x46, 0x8c, 0x05, 0x0a, 0x14, 0x28, 0x50, 0xa0, 0x5d, 0xba, 0x69, 0xd2, 0xb9, 0x6f, 0xde, 0xa1,
0x5f, 0xbe, 0x61, 0xc2, 0x99, 0x2f, 0x5e, 0xbc, 0x65, 0xca, 0x89, 0x0f, 0x1e, 0x3c, 0x78, 0xf0,
0xfd, 0xe7, 0xd3, 0xbb, 0x6b, 0xd6, 0xb1, 0x7f, 0xfe, 0xe1, 0xdf, 0xa3, 0x5b, 0xb6, 0x71, 0xe2,
0xd9, 0xaf, 0x43, 0x86, 0x11, 0x22, 0x44, 0x88, 0x0d, 0x1a, 0x34, 0x68, 0xd0, 0xbd, 0x67, 0xce,
0x81, 0x1f, 0x3e, 0x7c, 0xf8, 0xed, 0xc7, 0x93, 0x3b, 0x76, 0xec, 0xc5, 0x97, 0x33, 0x66, 0xcc,
0x85, 0x17, 0x2e, 0x5c, 0xb8, 0x6d, 0xda, 0xa9, 0x4f, 0x9e, 0x21, 0x42, 0x84, 0x15, 0x2a, 0x54,
0xa8, 0x4d, 0x9a, 0x29, 0x52, 0xa4, 0x55, 0xaa, 0x49, 0x92, 0x39, 0x72, 0xe4, 0xd5, 0xb7, 0x73,
0xe6, 0xd1, 0xbf, 0x63, 0xc6, 0x91, 0x3f, 0x7e, 0xfc, 0xe5, 0xd7, 0xb3, 0x7b, 0xf6, 0xf1, 0xff,
0xe3, 0xdb, 0xab, 0x4b, 0x96, 0x31, 0x62, 0xc4, 0x95, 0x37, 0x6e, 0xdc, 0xa5, 0x57, 0xae, 0x41,
0x82, 0x19, 0x32, 0x64, 0xc8, 0x8d, 0x07, 0x0e, 0x1c, 0x38, 0x70, 0xe0, 0xdd, 0xa7, 0x53, 0xa6,
0x51, 0xa2, 0x59, 0xb2, 0x79, 0xf2, 0xf9, 0xef, 0xc3, 0x9b, 0x2b, 0x56, 0xac, 0x45, 0x8a, 0x09,
0x12, 0x24, 0x48, 0x90, 0x3d, 0x7a, 0xf4, 0xf5, 0xf7, 0xf3, 0xfb, 0xeb, 0xcb, 0x8b, 0x0b, 0x16,
0x2c, 0x58, 0xb0, 0x7d, 0xfa, 0xe9, 0xcf, 0x83, 0x1b, 0x36, 0x6c, 0xd8, 0xad, 0x47, 0x8e, 0x00,
]
def do_mul(a, b):
if a == 0 or b == 0:
return 0;
else:
tmp = gflog[a] + gflog[b]
tmp = tmp % 255
return gfilog[tmp]
def do_div(a, b):
if a == 0:
return 0
elif b == 0:
print 'can not div 0'
return 0;
else:
tmp = gflog[a] - gflog[b]
if tmp < 0:
tmp = tmp + 255
return gfilog[tmp]
def do_power(a, b):
count = 0
result = 1
while (count < b):
result = do_mul(result, a)
count += 1
return result
def calc_once(num, ch):
if ch == '+':
ret = do_add(num[1], num[0])
elif ch == '-':
ret = do_sub(num[1], num[0])
elif ch == '*':
ret = do_mul(num[1], num[0])
elif ch == '/':
ret = do_div(num[1], num[0])
elif ch == '**':
ret = do_power(num[1], num[0])
else:
print 'unknow operation'
ret = 0
return ret
# 1. get ch from left to right
# 2. if ch is a number, output it
# 3. if ch is a operator or parenthese:
# a: if ch is '(', push to stack
# b: if ch is ')', pop stack until meet '('
# c: if ch is not parenthese, compare its priority with stack pop
# if ch priority is higher than the stack pop, push ch to stack
# else pop stack, push ch to stack
def midfix_to_posfix(midfix):
stack = []
posfix = []
for ch in midfix:
if is_parentheses_left(ch):
stack.append(ch)
elif is_parentheses_right(ch):
while True:
ch1 = stack.pop()
if is_parentheses_left(ch1):
break
else:
posfix.append(ch1)
elif is_operator(ch):
if len(stack) == 0:
stack.append(ch)
else:
ch1 = stack[-1]
if opt_priority(ch) > opt_priority(ch1):
stack.append(ch)
else:
ch1 = stack.pop()
posfix.append(ch1)
stack.append(ch)
else:
if len(ch) > 2 and ch[0:2] == '0x':
ch = int(ch, 16)
else:
ch = int(ch, 10)
posfix.append(ch)
while len(stack) != 0:
posfix.append(stack.pop())
return posfix
# get data from left to right
# if ch is a number, push to stack
# if ch is a operator, pop the number it needed, do calc, and push result to stack
# if data is paser comlete, pop the stack as result
def calc_posfix(posfix):
stack = []
for ch in posfix:
if is_operator(ch):
num = []
num.append(stack.pop())
if get_operation_number(ch) > 1:
num.append(stack.pop())
stack.append(calc_once(num, ch))
else:
stack.append(ch)
return stack.pop()
def main_loop():
# match all hex and dec number, and +,-,*,/,**
# note: hex must before dec number, and * must before **
print "please do not use ** mix with other operation, it's not support!"
regu_for_exp = re.compile('0x[0-9,a-f]+|[0-9]+|\*\*|\*|\+|\-|\/|\(|\)')
while True:
expression = raw_input('pq>:')
if expression != 'quit' and expression != 'q' and expression != 'exit':
midfix = regu_for_exp.findall(expression)
posfix = midfix_to_posfix(midfix)
result = calc_posfix(posfix)
if result is not None:
print "0x%02x" % result
else:
print result
else:
return
if __name__ == '__main__':
main_loop()
2010年11月10日星期三
raid6中gflog与gfilog
写了一篇介绍raid6中gflog与gfilog的文章，用了太多的数学公式，所以用lyx写了，放到网页上似乎不太方便，于是放到了google code上，下面是下载地址：
http://raid6theory.googlecode.com/files/raid6_theory.pdf
http://raid6theory.googlecode.com/files/raid6_theory.pdf
2010年11月3日星期三
创建/sys入口和使用waitqueue的小例子
一个简单的示例程序。创建一个/sys的接口，可以读写，每次回读都是上次写入的内容。每次读写都会触发一次event。
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/fs.h>
#include <linux/cdev.h>
#include <linux/device.h>
#include <linux/kthread.h>
static struct cdev test_cdev;
static dev_t test_devno;
static struct class *test_class;
struct device *test_device;
struct test_thread {
wait_queue_head_t wqueue;
unsigned long flags;
struct task_struct *tsk;
unsigned long timeout;
}test_thread;
#define FROM_SHOW 0
#define FROM_STORE 1
static const struct file_operations test_fops =
{
.owner = THIS_MODULE,
};
static int test_fun(void *arg)
{
struct test_thread *thread = arg;
allow_signal(SIGKILL);
while (!kthread_should_stop()) {
/* We need to wait INTERRUPTIBLE so that
* we don't add to the load-average.
* That means we need to be sure no signals are
* pending
*/
if (signal_pending(current))
flush_signals(current);
wait_event_interruptible_timeout
(thread->wqueue,
test_bit(FROM_SHOW, &thread->flags)
|| test_bit(FROM_STORE, &thread->flags)
|| kthread_should_stop(),
thread->timeout);
printk("thread %s is waken up by %s\n",
thread->tsk->comm,
test_bit(FROM_SHOW, &thread->flags) ? "show" :
test_bit(FROM_STORE, &thread->flags) ? "store" : "kill");
thread->flags = 0;
}
return 0;
}
#define TEST_LEN 4096
static char test_buf[TEST_LEN];
static ssize_t test_show(struct device *ddev,
struct device_attribute *attr, char *buf)
{
int len;
struct test_thread *thread;
thread = dev_get_drvdata(ddev);
len = strlen(test_buf) + 1;
memcpy(buf, test_buf, len);
set_bit(FROM_SHOW, &thread->flags);
wake_up(&thread->wqueue);
return len;
}
static ssize_t test_store(struct device *ddev,
struct device_attribute *attr, const char *buf, size_t count)
{
size_t len;
struct test_thread *thread;
thread = dev_get_drvdata(ddev);
if (count < TEST_LEN - 1)
len = count;
else
len = TEST_LEN - 1;
memcpy(test_buf, buf, len);
test_buf[len] = 0;
set_bit(FROM_STORE, &thread->flags);
wake_up(&thread->wqueue);
return count;
}
static DEVICE_ATTR(test1, 0644, test_show, test_store);
static int test_init(void)
{
int ret;
ret = alloc_chrdev_region(&test_devno, 0, 255, "test");
if (ret) {
printk(KERN_INFO "alloc_chrdev_region failed, ret=%d\n", ret);
return ret;
}
cdev_init(&test_cdev, &test_fops);
test_cdev.owner = THIS_MODULE;
ret = cdev_add(&test_cdev, test_devno, 1);
if (ret) {
printk(KERN_INFO "cdev_add failed, ret=%d\n", ret);
goto free_devno;
}
test_class = class_create(THIS_MODULE, "test_class");
if (IS_ERR(test_class)) {
ret = PTR_ERR(test_class);
printk(KERN_INFO "class_create failed, ret=%d\n", ret);
goto free_cdev;
}
test_device = device_create(test_class, NULL, test_devno, NULL, "test");
if (IS_ERR(test_device)) {
ret = PTR_ERR(test_device);
printk(KERN_INFO "device_create failed, ret=%d\n", ret);
goto free_class;
}
ret = device_create_file(test_device, &dev_attr_test1);
if (ret) {
printk(KERN_INFO "device_create_file failed, ret=%d\n", ret);
goto free_device;
}
init_waitqueue_head(&test_thread.wqueue);
test_thread.timeout = MAX_SCHEDULE_TIMEOUT;
test_thread.flags = 0;
dev_set_drvdata(test_device, &test_thread);
test_thread.tsk = kthread_run(test_fun, &test_thread, "test_thread");
if (IS_ERR(test_thread.tsk)) {
ret = PTR_ERR(test_thread.tsk);
printk(KERN_INFO "kthread_run failed, ret=%d\n", ret);
goto free_file;
}
return 0;
free_file:
device_remove_file(test_device, &dev_attr_test1);
free_device:
device_destroy(test_class, test_devno);
free_class:
class_destroy(test_class);
free_cdev:
cdev_del(&test_cdev);
free_devno:
unregister_chrdev_region(test_devno, 255);
return ret;
}
void test_exit(void)
{
kthread_stop(test_thread.tsk);
device_remove_file(test_device, &dev_attr_test1);
device_destroy(test_class, test_devno);
class_destroy(test_class);
cdev_del(&test_cdev);
unregister_chrdev_region(test_devno, 255);
}
MODULE_LICENSE("GPL");
module_init (test_init);
module_exit (test_exit);
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/fs.h>
#include <linux/cdev.h>
#include <linux/device.h>
#include <linux/kthread.h>
static struct cdev test_cdev;
static dev_t test_devno;
static struct class *test_class;
struct device *test_device;
struct test_thread {
wait_queue_head_t wqueue;
unsigned long flags;
struct task_struct *tsk;
unsigned long timeout;
}test_thread;
#define FROM_SHOW 0
#define FROM_STORE 1
static const struct file_operations test_fops =
{
.owner = THIS_MODULE,
};
static int test_fun(void *arg)
{
struct test_thread *thread = arg;
allow_signal(SIGKILL);
while (!kthread_should_stop()) {
/* We need to wait INTERRUPTIBLE so that
* we don't add to the load-average.
* That means we need to be sure no signals are
* pending
*/
if (signal_pending(current))
flush_signals(current);
wait_event_interruptible_timeout
(thread->wqueue,
test_bit(FROM_SHOW, &thread->flags)
|| test_bit(FROM_STORE, &thread->flags)
|| kthread_should_stop(),
thread->timeout);
printk("thread %s is waken up by %s\n",
thread->tsk->comm,
test_bit(FROM_SHOW, &thread->flags) ? "show" :
test_bit(FROM_STORE, &thread->flags) ? "store" : "kill");
thread->flags = 0;
}
return 0;
}
#define TEST_LEN 4096
static char test_buf[TEST_LEN];
static ssize_t test_show(struct device *ddev,
struct device_attribute *attr, char *buf)
{
int len;
struct test_thread *thread;
thread = dev_get_drvdata(ddev);
len = strlen(test_buf) + 1;
memcpy(buf, test_buf, len);
set_bit(FROM_SHOW, &thread->flags);
wake_up(&thread->wqueue);
return len;
}
static ssize_t test_store(struct device *ddev,
struct device_attribute *attr, const char *buf, size_t count)
{
size_t len;
struct test_thread *thread;
thread = dev_get_drvdata(ddev);
if (count < TEST_LEN - 1)
len = count;
else
len = TEST_LEN - 1;
memcpy(test_buf, buf, len);
test_buf[len] = 0;
set_bit(FROM_STORE, &thread->flags);
wake_up(&thread->wqueue);
return count;
}
static DEVICE_ATTR(test1, 0644, test_show, test_store);
static int test_init(void)
{
int ret;
ret = alloc_chrdev_region(&test_devno, 0, 255, "test");
if (ret) {
printk(KERN_INFO "alloc_chrdev_region failed, ret=%d\n", ret);
return ret;
}
cdev_init(&test_cdev, &test_fops);
test_cdev.owner = THIS_MODULE;
ret = cdev_add(&test_cdev, test_devno, 1);
if (ret) {
printk(KERN_INFO "cdev_add failed, ret=%d\n", ret);
goto free_devno;
}
test_class = class_create(THIS_MODULE, "test_class");
if (IS_ERR(test_class)) {
ret = PTR_ERR(test_class);
printk(KERN_INFO "class_create failed, ret=%d\n", ret);
goto free_cdev;
}
test_device = device_create(test_class, NULL, test_devno, NULL, "test");
if (IS_ERR(test_device)) {
ret = PTR_ERR(test_device);
printk(KERN_INFO "device_create failed, ret=%d\n", ret);
goto free_class;
}
ret = device_create_file(test_device, &dev_attr_test1);
if (ret) {
printk(KERN_INFO "device_create_file failed, ret=%d\n", ret);
goto free_device;
}
init_waitqueue_head(&test_thread.wqueue);
test_thread.timeout = MAX_SCHEDULE_TIMEOUT;
test_thread.flags = 0;
dev_set_drvdata(test_device, &test_thread);
test_thread.tsk = kthread_run(test_fun, &test_thread, "test_thread");
if (IS_ERR(test_thread.tsk)) {
ret = PTR_ERR(test_thread.tsk);
printk(KERN_INFO "kthread_run failed, ret=%d\n", ret);
goto free_file;
}
return 0;
free_file:
device_remove_file(test_device, &dev_attr_test1);
free_device:
device_destroy(test_class, test_devno);
free_class:
class_destroy(test_class);
free_cdev:
cdev_del(&test_cdev);
free_devno:
unregister_chrdev_region(test_devno, 255);
return ret;
}
void test_exit(void)
{
kthread_stop(test_thread.tsk);
device_remove_file(test_device, &dev_attr_test1);
device_destroy(test_class, test_devno);
class_destroy(test_class);
cdev_del(&test_cdev);
unregister_chrdev_region(test_devno, 255);
}
MODULE_LICENSE("GPL");
module_init (test_init);
module_exit (test_exit);
2010年11月1日星期一
在加载驱动时自动创建设备节点
在网上找了些自动创建设备节点的办法，但由于内核接口的变化，已经无法使用了。下面这个程序是可以在2.6.32内核上使用的：
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/fs.h>
#include <linux/cdev.h>
#include <linux/device.h>
static struct cdev test_cdev;
static dev_t test_devno;
static struct class *test_class;
struct device *test_device;
static const struct file_operations test_fops =
{
.owner = THIS_MODULE,
};
static int test_init(void)
{
int ret;
ret = alloc_chrdev_region(&test_devno, 0, 255, "test");
if (ret) {
printk(KERN_INFO "alloc_chrdev_region failed, ret=%d\n", ret);
return ret;
}
cdev_init(&test_cdev, &test_fops);
test_cdev.owner = THIS_MODULE;
ret = cdev_add(&test_cdev, test_devno, 1);
if (ret) {
printk(KERN_INFO "cdev_add failed, ret=%d\n", ret);
goto free_devno;
}
test_class = class_create(THIS_MODULE, "test_class");
if (IS_ERR(test_class)) {
ret = PTR_ERR(test_class);
printk(KERN_INFO "class_create failed, ret=%d\n", ret);
goto free_cdev;
}
test_device = device_create(test_class, NULL, test_devno, NULL, "test");
if (IS_ERR(test_device)) {
ret = PTR_ERR(test_device);
printk(KERN_INFO "device_create failed, ret=%d\n", ret);
goto free_class;
}
return 0;
free_class:
class_destroy(test_class);
free_cdev:
cdev_del(&test_cdev);
free_devno:
unregister_chrdev_region(test_devno, 255);
return ret;
}
void test_exit(void)
{
device_destroy(test_class, test_devno);
class_destroy(test_class);
cdev_del(&test_cdev);
unregister_chrdev_region(test_devno, 255);
}
MODULE_LICENSE("GPL");
module_init (test_init);
module_exit (test_exit);
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/fs.h>
#include <linux/cdev.h>
#include <linux/device.h>
static struct cdev test_cdev;
static dev_t test_devno;
static struct class *test_class;
struct device *test_device;
static const struct file_operations test_fops =
{
.owner = THIS_MODULE,
};
static int test_init(void)
{
int ret;
ret = alloc_chrdev_region(&test_devno, 0, 255, "test");
if (ret) {
printk(KERN_INFO "alloc_chrdev_region failed, ret=%d\n", ret);
return ret;
}
cdev_init(&test_cdev, &test_fops);
test_cdev.owner = THIS_MODULE;
ret = cdev_add(&test_cdev, test_devno, 1);
if (ret) {
printk(KERN_INFO "cdev_add failed, ret=%d\n", ret);
goto free_devno;
}
test_class = class_create(THIS_MODULE, "test_class");
if (IS_ERR(test_class)) {
ret = PTR_ERR(test_class);
printk(KERN_INFO "class_create failed, ret=%d\n", ret);
goto free_cdev;
}
test_device = device_create(test_class, NULL, test_devno, NULL, "test");
if (IS_ERR(test_device)) {
ret = PTR_ERR(test_device);
printk(KERN_INFO "device_create failed, ret=%d\n", ret);
goto free_class;
}
return 0;
free_class:
class_destroy(test_class);
free_cdev:
cdev_del(&test_cdev);
free_devno:
unregister_chrdev_region(test_devno, 255);
return ret;
}
void test_exit(void)
{
device_destroy(test_class, test_devno);
class_destroy(test_class);
cdev_del(&test_cdev);
unregister_chrdev_region(test_devno, 255);
}
MODULE_LICENSE("GPL");
module_init (test_init);
module_exit (test_exit);
2010年10月24日星期日
linux 内核 hash table 的使用
很早以前就想学习一下如何使用linux内核中的散列函数。google了几次，发现
网上有大量介绍有关hlist的东西。可找来找去也找不到究竟该如何使用散列。
原来，我先入为主的认为内核中的散列函数会像那些高级语言中实现的散列功能
类似：我提供一对对的(key value)给内核，然后再调用某一个api，传给它一个
key，就可以得到对应的value。
后来参考了一些内核中应用散列的实例才发现，原来根本不是这么回事。实际
上，对于如何将输入数据散列到一个指定范围的算法，需要使用散列的人自己决
定。内核只提供了一个发射碰撞时把碰撞的项链接到一起的hlist结构。
例如，你创建了一个长度为m的散列表，并且已经选择了一个将输入数据映射到
范围0 ~ m-1的散列函数。接下来，你就要在这个长度为m的散列表的每个表项内
放上一个hlist_head结构体。然后在每个输入数据的结构体中定义一个
hlist_node的结构体。每当把一个输入通过散列函数映射到0 ~ m-1的范围内时，就
把这个输入的hlist_node挂到散列表对应的槽的hlist_head上面。当给定一个
key，想获取它的value的时候，就先用散列函数算出这个key对应的槽的位置，
然后遍历这个槽的hlist_node链表，找到与key相等的项。把它的value返回。
例如，有这样一个数组：
0x01, 0x02, 0x04, 0x08,0x10, 0x20, 0x40, 0x80, 0x1d, 0x3a, 0x74, 0xe8,
0xcd, 0x87, 0x13,
其中每个元素对应的索引号为：
1, 2, 3, 4, 5, ... 15
也就是说，当输入0x01时，我希望得到索引号1，当输入0x08时，得到4，当输入
0x3a时，得到10...
这种从数值到索引号的转换，可通过散列来实现。
下面是实现该功能的一个内核代码，散列函数我选择的是：
value = ((104 * key + 52) % 233) % 15
(实际上，对于输入固定的情况，使用完全散列可以获得完全固定的访问时间，
上面这个散列函数就是我想使用完全散列时搜索一个全域散列族得到的第一级散
列函数，但我发先这个散列函数已经足够好，总共才只有一次碰撞。所以就没有
必要像完全散列那样使用二级散列了。)
#include <linux/init.h>
#include <linux/module.h>
#include <linux/list.h>
struct q_coef
{
u8 coef;
u8 index;
struct hlist_node hash;
};
#define HASH_NUMBER 15
u8 coef[HASH_NUMBER] = {
0x01, 0x02, 0x04, 0x08,0x10, 0x20, 0x40, 0x80, 0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13,
};
struct q_coef q_coef_list[HASH_NUMBER];
struct hlist_head hashtbl[HASH_NUMBER];
static inline int hash_func(u8 k)
{
int a, b, p, m;
a = 104;
b = 52;
p = 233;
m = HASH_NUMBER;
return ((a * k + b) % p) % m;
}
static void hash_init(void)
{
int i, j;
for (i = 0 ; i < HASH_NUMBER ; i++) {
INIT_HLIST_HEAD(&hashtbl[i]);
INIT_HLIST_NODE(&q_coef_list[i].hash);
q_coef_list[i].coef = coef[i];
q_coef_list[i].index = i + 1;
}
for (i = 0 ; i < HASH_NUMBER ; i++) {
j = hash_func(q_coef_list[i].coef);
hlist_add_head(&q_coef_list[i].hash, &hashtbl[j]);
}
}
static void hash_test(void)
{
int i, j;
struct q_coef *q;
struct hlist_node *hn;
for (i = 0 ; i < HASH_NUMBER ; i++) {
j = hash_func(coef[i]);
hlist_for_each_entry(q, hn, &hashtbl[j], hash)
if (q->coef == coef[i])
printk("found: coef=0x%02x index=%d\n", q->coef, q->index);
}
}
static int htest_init (void)
{
hash_init();
hash_test();
return -1;
}
static void htest_exit (void)
{
}
module_init(htest_init);
module_exit(htest_exit);
MODULE_LICENSE("Dual BSD/GPL");
网上有大量介绍有关hlist的东西。可找来找去也找不到究竟该如何使用散列。
原来，我先入为主的认为内核中的散列函数会像那些高级语言中实现的散列功能
类似：我提供一对对的(key value)给内核，然后再调用某一个api，传给它一个
key，就可以得到对应的value。
后来参考了一些内核中应用散列的实例才发现，原来根本不是这么回事。实际
上，对于如何将输入数据散列到一个指定范围的算法，需要使用散列的人自己决
定。内核只提供了一个发射碰撞时把碰撞的项链接到一起的hlist结构。
例如，你创建了一个长度为m的散列表，并且已经选择了一个将输入数据映射到
范围0 ~ m-1的散列函数。接下来，你就要在这个长度为m的散列表的每个表项内
放上一个hlist_head结构体。然后在每个输入数据的结构体中定义一个
hlist_node的结构体。每当把一个输入通过散列函数映射到0 ~ m-1的范围内时，就
把这个输入的hlist_node挂到散列表对应的槽的hlist_head上面。当给定一个
key，想获取它的value的时候，就先用散列函数算出这个key对应的槽的位置，
然后遍历这个槽的hlist_node链表，找到与key相等的项。把它的value返回。
例如，有这样一个数组：
0x01, 0x02, 0x04, 0x08,0x10, 0x20, 0x40, 0x80, 0x1d, 0x3a, 0x74, 0xe8,
0xcd, 0x87, 0x13,
其中每个元素对应的索引号为：
1, 2, 3, 4, 5, ... 15
也就是说，当输入0x01时，我希望得到索引号1，当输入0x08时，得到4，当输入
0x3a时，得到10...
这种从数值到索引号的转换，可通过散列来实现。
下面是实现该功能的一个内核代码，散列函数我选择的是：
value = ((104 * key + 52) % 233) % 15
(实际上，对于输入固定的情况，使用完全散列可以获得完全固定的访问时间，
上面这个散列函数就是我想使用完全散列时搜索一个全域散列族得到的第一级散
列函数，但我发先这个散列函数已经足够好，总共才只有一次碰撞。所以就没有
必要像完全散列那样使用二级散列了。)
#include <linux/init.h>
#include <linux/module.h>
#include <linux/list.h>
struct q_coef
{
u8 coef;
u8 index;
struct hlist_node hash;
};
#define HASH_NUMBER 15
u8 coef[HASH_NUMBER] = {
0x01, 0x02, 0x04, 0x08,0x10, 0x20, 0x40, 0x80, 0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13,
};
struct q_coef q_coef_list[HASH_NUMBER];
struct hlist_head hashtbl[HASH_NUMBER];
static inline int hash_func(u8 k)
{
int a, b, p, m;
a = 104;
b = 52;
p = 233;
m = HASH_NUMBER;
return ((a * k + b) % p) % m;
}
static void hash_init(void)
{
int i, j;
for (i = 0 ; i < HASH_NUMBER ; i++) {
INIT_HLIST_HEAD(&hashtbl[i]);
INIT_HLIST_NODE(&q_coef_list[i].hash);
q_coef_list[i].coef = coef[i];
q_coef_list[i].index = i + 1;
}
for (i = 0 ; i < HASH_NUMBER ; i++) {
j = hash_func(q_coef_list[i].coef);
hlist_add_head(&q_coef_list[i].hash, &hashtbl[j]);
}
}
static void hash_test(void)
{
int i, j;
struct q_coef *q;
struct hlist_node *hn;
for (i = 0 ; i < HASH_NUMBER ; i++) {
j = hash_func(coef[i]);
hlist_for_each_entry(q, hn, &hashtbl[j], hash)
if (q->coef == coef[i])
printk("found: coef=0x%02x index=%d\n", q->coef, q->index);
}
}
static int htest_init (void)
{
hash_init();
hash_test();
return -1;
}
static void htest_exit (void)
{
}
module_init(htest_init);
module_exit(htest_exit);
MODULE_LICENSE("Dual BSD/GPL");
linux内核的raid0驱动介绍
1 raid和md的介绍
~~~~~~~~~~~~~~~~~
linux内核有一个md层，用于组建磁盘阵列。你可以为它指定若干个块设备，
并指定一种组建磁盘阵列的方法（raid0，raid1或者raid5，raid6之类的）。
它会建立一个虚拟的块设备，使用者对这个虚拟的块设备进行操作，md层按照
指定的raid算法转换成对实际块设备的操作。其中最简单的是raid0算法。
raid0算法按照固定的大小将请求读写的数据拆成小块，分别存在组成磁盘阵
列的各个块设备中。用raid0组建的磁盘阵列总大小等于各个块设备的大小之
和。由于各个块设备可以并行操作，所以使用raid0组建磁盘阵列速度会很快。
raid0的代码在kernel/drivers/md/raid0.c中。
2 初始化
~~~~~~~~~
raid0的初始化函数是raid0_init，它很简单，仅仅是把一个
mdk_personality结构体注册到md层。
对于raid0来说，这个结构体的内容如下：
static struct mdk_personality raid0_personality=
{
.name = "raid0",
.level = 0,
.owner = THIS_MODULE,
.make_request = raid0_make_request,
.run = raid0_run,
.stop = raid0_stop,
.status = raid0_status,
.size = raid0_size,
};
它定义了几个接口函数。
raid0_run用于初始化。当有上层指令为md层指定了几个实际的块设备，并
让md层将它们组建为raid0的时候， md层将会调用该函数。
当md层受到读写数据的请求时，将会调用raid0_make_request函数。该函
数的作用是把md层收到的传输请求转换为实际块设备的传输请求。
当md层终止raid0设备的时候，会调用raid0_stop函数。
raid0_status函数用于输出调试信息。
raid0_size函数返回整个raid0设备的总大小，也就是实际组成raid0的
几个块设备的容量之和。
下面主要介绍raid0_run和raid0_make_request两支函数。
3 raid0_run
~~~~~~~~~~~~
3.1 程序主干
=============
首先进行一些错误检测以及对md层使用的结构体mddev进行一些初始化。
然后调用一个比较重要的函数create_strip_zones，初始化raid0的strip。
接下来对md层虚拟的块设备做一些限制，最后将填充好的mddev结构体注
册到md层。接下来重点讲解create_strip_zones函数。
3.2 create_strip_zones
=======================
create_strip_zones函数会针对md层提供的实际块设别的大小建立
strip_zones。
3.2.1 strip_zone 的建立规则
----------------------------
我们假设有3个块设备组成raid0，分别考虑如下几种情况：
三个块设备大小都一样，比如都是40M，那么一共需要一个strip_zones。
如图所示：
如果这三个块设备的大小分别是60M，50M，40M，那么需要建立三个
strip_zones。60M 设备的前40M，50M设备的前40M，和整个40M的设备组成第
一个 strip_zone，60M设备的40M到50M的部分与50M设备的最后10M组成第二
个strip_zone，60M设备的最后10M是第三个strip_zone。
如下图所示：
如果三个块设备的大小分别是60M，50M，50M，那么一共需要建立两个
strip_zone。两个50M设备的全部和60M设备的前50M组成一个
strip_zone，60M设备的最后10M组成另一个strip_zone。
如下图所示：
3.2.2 确定需要建立多少个strip_zones
------------------------------------
进入create_strip_zones后，首先是一个双重循环，用来判断一共需要建立
多少个strip_zones。代码如下：
list_for_each_entry(rdev1, &mddev->disks, same_set) {
printk(KERN_INFO "raid0: looking at %s\n",
bdevname(rdev1->bdev,b));
c = 0;
/* round size to chunk_size */
sectors = rdev1->sectors;
sector_div(sectors, mddev->chunk_sectors);
rdev1->sectors = sectors * mddev->chunk_sectors;
list_for_each_entry(rdev2, &mddev->disks, same_set) {
printk(KERN_INFO "raid0: comparing %s(%llu)",
bdevname(rdev1->bdev,b),
(unsigned long long)rdev1->sectors);
printk(KERN_INFO " with %s(%llu)\n",
bdevname(rdev2->bdev,b),
(unsigned long long)rdev2->sectors);
if (rdev2 == rdev1) {
printk(KERN_INFO "raid0: END\n");
break;
}
if (rdev2->sectors == rdev1->sectors) {
/*
* Not unique, don't count it as a new
* group
*/
printk(KERN_INFO "raid0: EQUAL\n");
c = 1;
break;
}
printk(KERN_INFO "raid0: NOT EQUAL\n");
}
if (!c) {
printk(KERN_INFO "raid0: ==> UNIQUE\n");
conf->nr_strip_zones++;
printk(KERN_INFO "raid0: %d zones\n",
conf->nr_strip_zones);
}
}
我们还是以实际例子来分析一下程序的运行过程。假设共有三个块设备，名
字分别叫做blk1,blk2,blk3。大小分别为60M，60M,40M。mddev->disks这个
链表中存放了全部三个块设备，假设三个块设备在链表中的存放顺序依次为
blk1，blk2，blk3，那么list_for_each_entry宏会按照blk1，blk2，blk3
的顺序取出这三个块设备，对于两重循环都是如此。首先，进入第一重循
环，rdev1指向blk1，计算出rdev1的sector数量，应该是60M除以512。然后
进入第二重循环，第一次也取出了blk1，存放在rdev2中。比较rdev1和
rdev2是否相等，当然会相等，于是跳出第二重循环，判断变量c是否是0，
注意，在进入第二重循环之前c被置0，然后没有变化，所以此时c是0，于是
将记录strip_zones的变量加一。然后第一重循环进入第二轮，rdev1指向
blk2，计算出blk2的sectors数量，进入第二重循环。第二重循环还是先取
出blk1，放在rdev2中。判断rdev1和rdev2是否相等，当然不相等，继续往
下进行。比较rdev1和rdev2的大小是否相等。我们先前假设blk1和blk2大小
都是60M，所以相等。此时，设置c=1，然后跳出第二重循环。在第一重循环
的结尾处，判断c是否等于0，c不等于0，所以nr_strip_zones维持原来的数
值，即1。第一重循环进入第三次，rdev1指向blk3，进入第二重循环，rdev2首
先指向blk1，rdev1与rdev2不相等，rdev1的sectors与rdev2的sectors也不
相等，第二重循环进入第二次，rdev2指向blk2，结果与上一次一样，第二
重循环进入第三次，rdev2指向blk3，此时rdev1与rdev2相等，跳出第二重
循环，检查c的值，是0，所以nr_strip_zones加1。双重循环全部结束。最
终nr_strip_zones的值是2。
3.2.3 分配内存
---------------
conf->strip_zone = kzalloc(sizeof(struct strip_zone)*
conf->nr_strip_zones, GFP_KERNEL);
有多少个strip_zones，就分配多少个strip_zone结构体。
conf->devlist = kzalloc(sizeof(mdk_rdev_t*)*
conf->nr_strip_zones*mddev->raid_disks,
GFP_KERNEL);
mddev->disks中记录着共有多少个实际的块设备组成raid0。比如前面一直
举例有三个块设备，那么mddev->raid_disks的值就是3。conf->devlist中
存放着被分块后的实际设备。比如三个块设备的大小都一样，那么就在
mddev->devlist中存放三个块设备。如果三个块设备的大小分别是
40M，50M和60M，那么40M，50M的前40M，60M的前40M分别作为3个块设备存
放在mddev->devlist中，50M设备的后10M和60M设备的40M到50M阶段，又作
为两个设备存放在mddev->devlistg中，最后，60M设备的最后10M又作为一
个单独的设备存在mddev->devlist中。因此一共需要6个。这里用
strip_zones的个数乘以实际设备的个数分配内存，有可能会比实际需要的
内存数多一些，除非三个块设备的大小相等，此时分配的内存刚好等于实际
需求。
3.2.4 找出最小的strip_zone
---------------------------
接下来又是一个循环：
list_for_each_entry(rdev1, &mddev->disks, same_set)
...
作用很简单，就是找出长度最小的strip_zone。然后把最小strip_zone里面
包含的设备全都放进conf->devlist里面，实际上也就是全部的设备，因为
最小的strip_zone肯定包含了全部的设备。
3.2.5 把其他的strip_zone里面的设备放入conf->devlist之中。
----------------------------------------------------------
依然是一个循环：
for (i = 1; i <>nr_strip_zones; i++)
...
把被strip_zone分割过的设备放入conf->devlist中。以40M，50M，60M，的
设备为例，就是50M设备的后10M，60M设备的40至50M，50至60M这些部分放
入conf->devlist中。并且设置好它们在原本的块设备中的起始地址和偏移
量。
3.2.6 creaet_strip_zones的其余部分
-----------------------------------
注册一些回调函数，再对md构造的块设备做一些限制，然后就结束了。
3.3 raid0_run的其余部分
========================
没什么可说的，raid0_run函数的精髓就在create_strip_zones函数里面。建
立好strip_zones之后，raid0_run的主要工作就完成了。
4 raid0_make_request
~~~~~~~~~~~~~~~~~~~~~
raid0_make_request函数是处理读写数据的函数。它把传递给由md虚拟出来的
块设备的读写请求转换为到实际块设备的读写请求。然后md层会依据
raid0_make_request的转换结果把实际的读写请求送到实际的块设备中去。
4.1 程序主干
=============
首先进行一些必要的错误检测。
然后判断md层传下来的请求有没有chunk。md设备的数据存取是以chunk为单
位的。chunk的大小存储在mddev->chunk_sectors中。它的单位是512byte。
比如mddev->chunk_sectors=128，那么chunk的大小是128*512byte=64K。
如果传输跨chunk了，就把传输请求分成两个不跨chunk的请求，再递归调用
raid0_make_request函数处理。
如果传输没有跨chunk，先调用find_zone函数确定传输请求在哪个
strip_zone中，然后调用map_sector函数确定实际执行传输请求的块设备。
最后将实际执行请求的块设备的信息填入到bio之中。
4.2 find_zone
==============
find_zone函数用于确定传输请求落入哪个strip_zone中。数组
conf->strip_zone中按照先后顺序记录了所有的strip_zone。而每个
strip_zone的zone_end位中又记录着该strip_zone的结束地址（以sector为
单位）。从zone_end最小的strip_zone开始依次与传输要求的起始sector比
较大小。第一个zone_end比传输请求的起始sector大的strip_zone就是我们
要找的。
另外，find_zone函数还把传输起始的sector由以md设备的起始地址计算转换
为在执行strip_zone中的偏移地址。
4.3 map_sector
===============
map_sector函数用于确定实际执行传输的块设备。出于运行效率上的考虑，
它首先判断mddev->chunk_sectors是否是2的整数次幂。
mddev->chunk_sectors是md设备的chunk大小（前面提到过，它是以512byte
为单位的）。如果chunk的大小是2的整数次幂，在计算中就可以以左右移位
来代替乘法和除法运算。最终，该函数会从conf->devlist中返回一个设备，
也就是我们前面举例中提到的“50M设备的最后10M”或者“60M设备的第40M到第
50M”这样的设备，而不是实际的块设备，然后，把要进行存取操作的起始
section相对于这个设备的偏移量放入sector_offset中返回。
~~~~~~~~~~~~~~~~~
linux内核有一个md层，用于组建磁盘阵列。你可以为它指定若干个块设备，
并指定一种组建磁盘阵列的方法（raid0，raid1或者raid5，raid6之类的）。
它会建立一个虚拟的块设备，使用者对这个虚拟的块设备进行操作，md层按照
指定的raid算法转换成对实际块设备的操作。其中最简单的是raid0算法。
raid0算法按照固定的大小将请求读写的数据拆成小块，分别存在组成磁盘阵
列的各个块设备中。用raid0组建的磁盘阵列总大小等于各个块设备的大小之
和。由于各个块设备可以并行操作，所以使用raid0组建磁盘阵列速度会很快。
raid0的代码在kernel/drivers/md/raid0.c中。
2 初始化
~~~~~~~~~
raid0的初始化函数是raid0_init，它很简单，仅仅是把一个
mdk_personality结构体注册到md层。
对于raid0来说，这个结构体的内容如下：
static struct mdk_personality raid0_personality=
{
.name = "raid0",
.level = 0,
.owner = THIS_MODULE,
.make_request = raid0_make_request,
.run = raid0_run,
.stop = raid0_stop,
.status = raid0_status,
.size = raid0_size,
};
它定义了几个接口函数。
raid0_run用于初始化。当有上层指令为md层指定了几个实际的块设备，并
让md层将它们组建为raid0的时候， md层将会调用该函数。
当md层受到读写数据的请求时，将会调用raid0_make_request函数。该函
数的作用是把md层收到的传输请求转换为实际块设备的传输请求。
当md层终止raid0设备的时候，会调用raid0_stop函数。
raid0_status函数用于输出调试信息。
raid0_size函数返回整个raid0设备的总大小，也就是实际组成raid0的
几个块设备的容量之和。
下面主要介绍raid0_run和raid0_make_request两支函数。
3 raid0_run
~~~~~~~~~~~~
3.1 程序主干
=============
首先进行一些错误检测以及对md层使用的结构体mddev进行一些初始化。
然后调用一个比较重要的函数create_strip_zones，初始化raid0的strip。
接下来对md层虚拟的块设备做一些限制，最后将填充好的mddev结构体注
册到md层。接下来重点讲解create_strip_zones函数。
3.2 create_strip_zones
=======================
create_strip_zones函数会针对md层提供的实际块设别的大小建立
strip_zones。
3.2.1 strip_zone 的建立规则
----------------------------
我们假设有3个块设备组成raid0，分别考虑如下几种情况：
三个块设备大小都一样，比如都是40M，那么一共需要一个strip_zones。
如图所示：
如果这三个块设备的大小分别是60M，50M，40M，那么需要建立三个
strip_zones。60M 设备的前40M，50M设备的前40M，和整个40M的设备组成第
一个 strip_zone，60M设备的40M到50M的部分与50M设备的最后10M组成第二
个strip_zone，60M设备的最后10M是第三个strip_zone。
如下图所示：
如果三个块设备的大小分别是60M，50M，50M，那么一共需要建立两个
strip_zone。两个50M设备的全部和60M设备的前50M组成一个
strip_zone，60M设备的最后10M组成另一个strip_zone。
如下图所示：
------------------------------------
进入create_strip_zones后，首先是一个双重循环，用来判断一共需要建立
多少个strip_zones。代码如下：
list_for_each_entry(rdev1, &mddev->disks, same_set) {
printk(KERN_INFO "raid0: looking at %s\n",
bdevname(rdev1->bdev,b));
c = 0;
/* round size to chunk_size */
sectors = rdev1->sectors;
sector_div(sectors, mddev->chunk_sectors);
rdev1->sectors = sectors * mddev->chunk_sectors;
list_for_each_entry(rdev2, &mddev->disks, same_set) {
printk(KERN_INFO "raid0: comparing %s(%llu)",
bdevname(rdev1->bdev,b),
(unsigned long long)rdev1->sectors);
printk(KERN_INFO " with %s(%llu)\n",
bdevname(rdev2->bdev,b),
(unsigned long long)rdev2->sectors);
if (rdev2 == rdev1) {
printk(KERN_INFO "raid0: END\n");
break;
}
if (rdev2->sectors == rdev1->sectors) {
/*
* Not unique, don't count it as a new
* group
*/
printk(KERN_INFO "raid0: EQUAL\n");
c = 1;
break;
}
printk(KERN_INFO "raid0: NOT EQUAL\n");
}
if (!c) {
printk(KERN_INFO "raid0: ==> UNIQUE\n");
conf->nr_strip_zones++;
printk(KERN_INFO "raid0: %d zones\n",
conf->nr_strip_zones);
}
}
我们还是以实际例子来分析一下程序的运行过程。假设共有三个块设备，名
字分别叫做blk1,blk2,blk3。大小分别为60M，60M,40M。mddev->disks这个
链表中存放了全部三个块设备，假设三个块设备在链表中的存放顺序依次为
blk1，blk2，blk3，那么list_for_each_entry宏会按照blk1，blk2，blk3
的顺序取出这三个块设备，对于两重循环都是如此。首先，进入第一重循
环，rdev1指向blk1，计算出rdev1的sector数量，应该是60M除以512。然后
进入第二重循环，第一次也取出了blk1，存放在rdev2中。比较rdev1和
rdev2是否相等，当然会相等，于是跳出第二重循环，判断变量c是否是0，
注意，在进入第二重循环之前c被置0，然后没有变化，所以此时c是0，于是
将记录strip_zones的变量加一。然后第一重循环进入第二轮，rdev1指向
blk2，计算出blk2的sectors数量，进入第二重循环。第二重循环还是先取
出blk1，放在rdev2中。判断rdev1和rdev2是否相等，当然不相等，继续往
下进行。比较rdev1和rdev2的大小是否相等。我们先前假设blk1和blk2大小
都是60M，所以相等。此时，设置c=1，然后跳出第二重循环。在第一重循环
的结尾处，判断c是否等于0，c不等于0，所以nr_strip_zones维持原来的数
值，即1。第一重循环进入第三次，rdev1指向blk3，进入第二重循环，rdev2首
先指向blk1，rdev1与rdev2不相等，rdev1的sectors与rdev2的sectors也不
相等，第二重循环进入第二次，rdev2指向blk2，结果与上一次一样，第二
重循环进入第三次，rdev2指向blk3，此时rdev1与rdev2相等，跳出第二重
循环，检查c的值，是0，所以nr_strip_zones加1。双重循环全部结束。最
终nr_strip_zones的值是2。
3.2.3 分配内存
---------------
conf->strip_zone = kzalloc(sizeof(struct strip_zone)*
conf->nr_strip_zones, GFP_KERNEL);
有多少个strip_zones，就分配多少个strip_zone结构体。
conf->devlist = kzalloc(sizeof(mdk_rdev_t*)*
conf->nr_strip_zones*mddev->raid_disks,
GFP_KERNEL);
mddev->disks中记录着共有多少个实际的块设备组成raid0。比如前面一直
举例有三个块设备，那么mddev->raid_disks的值就是3。conf->devlist中
存放着被分块后的实际设备。比如三个块设备的大小都一样，那么就在
mddev->devlist中存放三个块设备。如果三个块设备的大小分别是
40M，50M和60M，那么40M，50M的前40M，60M的前40M分别作为3个块设备存
放在mddev->devlist中，50M设备的后10M和60M设备的40M到50M阶段，又作
为两个设备存放在mddev->devlistg中，最后，60M设备的最后10M又作为一
个单独的设备存在mddev->devlist中。因此一共需要6个。这里用
strip_zones的个数乘以实际设备的个数分配内存，有可能会比实际需要的
内存数多一些，除非三个块设备的大小相等，此时分配的内存刚好等于实际
需求。
3.2.4 找出最小的strip_zone
---------------------------
接下来又是一个循环：
list_for_each_entry(rdev1, &mddev->disks, same_set)
...
作用很简单，就是找出长度最小的strip_zone。然后把最小strip_zone里面
包含的设备全都放进conf->devlist里面，实际上也就是全部的设备，因为
最小的strip_zone肯定包含了全部的设备。
3.2.5 把其他的strip_zone里面的设备放入conf->devlist之中。
----------------------------------------------------------
依然是一个循环：
for (i = 1; i <>nr_strip_zones; i++)
...
把被strip_zone分割过的设备放入conf->devlist中。以40M，50M，60M，的
设备为例，就是50M设备的后10M，60M设备的40至50M，50至60M这些部分放
入conf->devlist中。并且设置好它们在原本的块设备中的起始地址和偏移
量。
3.2.6 creaet_strip_zones的其余部分
-----------------------------------
注册一些回调函数，再对md构造的块设备做一些限制，然后就结束了。
3.3 raid0_run的其余部分
========================
没什么可说的，raid0_run函数的精髓就在create_strip_zones函数里面。建
立好strip_zones之后，raid0_run的主要工作就完成了。
4 raid0_make_request
~~~~~~~~~~~~~~~~~~~~~
raid0_make_request函数是处理读写数据的函数。它把传递给由md虚拟出来的
块设备的读写请求转换为到实际块设备的读写请求。然后md层会依据
raid0_make_request的转换结果把实际的读写请求送到实际的块设备中去。
4.1 程序主干
=============
首先进行一些必要的错误检测。
然后判断md层传下来的请求有没有chunk。md设备的数据存取是以chunk为单
位的。chunk的大小存储在mddev->chunk_sectors中。它的单位是512byte。
比如mddev->chunk_sectors=128，那么chunk的大小是128*512byte=64K。
如果传输跨chunk了，就把传输请求分成两个不跨chunk的请求，再递归调用
raid0_make_request函数处理。
如果传输没有跨chunk，先调用find_zone函数确定传输请求在哪个
strip_zone中，然后调用map_sector函数确定实际执行传输请求的块设备。
最后将实际执行请求的块设备的信息填入到bio之中。
4.2 find_zone
==============
find_zone函数用于确定传输请求落入哪个strip_zone中。数组
conf->strip_zone中按照先后顺序记录了所有的strip_zone。而每个
strip_zone的zone_end位中又记录着该strip_zone的结束地址（以sector为
单位）。从zone_end最小的strip_zone开始依次与传输要求的起始sector比
较大小。第一个zone_end比传输请求的起始sector大的strip_zone就是我们
要找的。
另外，find_zone函数还把传输起始的sector由以md设备的起始地址计算转换
为在执行strip_zone中的偏移地址。
4.3 map_sector
===============
map_sector函数用于确定实际执行传输的块设备。出于运行效率上的考虑，
它首先判断mddev->chunk_sectors是否是2的整数次幂。
mddev->chunk_sectors是md设备的chunk大小（前面提到过，它是以512byte
为单位的）。如果chunk的大小是2的整数次幂，在计算中就可以以左右移位
来代替乘法和除法运算。最终，该函数会从conf->devlist中返回一个设备，
也就是我们前面举例中提到的“50M设备的最后10M”或者“60M设备的第40M到第
50M”这样的设备，而不是实际的块设备，然后，把要进行存取操作的起始
section相对于这个设备的偏移量放入sector_offset中返回。
订阅：
博文 (Atom)