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