xen-arm 算法技巧赏析(0)

原创文章,转载请注明出处.转载自: Li Haifeng's Blog
本文链接地址: xen-arm 算法技巧赏析(0)

1 /*
2 原以为,在平时的工程实现中,算法几乎是用不上的。但在看内核的过程中,发现算法还是比较重要的。
3 尤其是一些细微而又精巧的程序设计技巧。这些技巧是需要掌握的。
4
5 下面的这段程序摘自:xen-arm中,的内存初始化部分。
6 功能:从first_page页开始的nr_pages页在页位图中,表示为空闲页。
7 页位图,位于_end之后。_end标识xen-arm kernel的结束地址。
8
9 */
10 static void map_free(unsigned long first_page, unsigned long nr_pages)
11 {
12 unsigned long start_off, end_off, curr_idx, end_idx;
13
14 #ifndef NDEBUG
15 unsigned long i;
16 /* Check that the block isn’t already freed. */
17 for ( i = 0; i < nr_pages; i++ )
18 ASSERT(allocated_in_map(first_page + i));//ASSERT:如果条件不成立,就报错
19 #endif
20
21 curr_idx  = (first_page-min_page) / PAGES_PER_MAPWORD;
22 start_off = (first_page-min_page) & (PAGES_PER_MAPWORD-1);
23 end_idx   = (first_page-min_page + nr_pages) / PAGES_PER_MAPWORD;
24 end_off   = (first_page-min_page + nr_pages) & (PAGES_PER_MAPWORD-1);
25
26 if ( curr_idx == end_idx )
27 {
28 //这个算法还是比较巧妙的
29 //1<<start_off – 1 从start_off位开始,全部为1
30 /*
31 -(1<<end_off) 从0 ~ end_off 开始,全部为0–
32 通过这种方式,把0~end_off之间全部变为0 ,而end_off ~31之间为1
33 */
34 //两者之或,就是从start_off ~ end_off 之间全部为0了
35 alloc_bitmap[curr_idx] &= -(1UL<<end_off) | ((1UL<<start_off)-1);
36 }
37 else
38 {
39 alloc_bitmap[curr_idx] &= (1UL<<start_off)-1;//start_off~31之间的为0,妙哉!
40 while ( ++curr_idx != end_idx ) alloc_bitmap[curr_idx] = 0;
41 alloc_bitmap[curr_idx] &= -(1UL<<end_off);
42 }
43 }
44

From Li Haifeng's Blog, post xen-arm 算法技巧赏析(0)

Post Footer automatically generated by wp-posturl plugin for wordpress.

分享到: