伙伴算法的数据结构

2012年3月6日 由 edsionte 5 条评论 »

伙伴算法(buddy system)在物理内存管理中占据十分重要的位置,这种算法可以有效的避免内存中的外部碎片。所谓外部碎片(external fragmentation),就是指内存频繁请求和释放大小不同的连续页框后,导致在已分配页框块周围分散了许多小块空闲的页框,尽管这些空闲页框的总数可以满足接下来的请求,但却无法满足一个大块的连续页框。本文接下来详细说明伙伴算法在内核中的结构描述,其基本原理本文不再赘述。

在每个内存管理区中都有一个free_area数组,该数组的长度为MAX_ORDER,默认值为11。free_area数组描述的就是伙伴算法中每个分配阶(从0到11)所对应的页框块链表。比如free_area[2]所对应的页框块链表中,每个节点对应4个连续的页框(2的2次方)。

struct zone {
……
struct free_area        free_area[MAX_ORDER];
……
}

#ifndef CONFIG_FORCE_MAX_ZONEORDER
#define MAX_ORDER 11
#else
#define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
#endif

可以看到,free_area数组的元素类型是struct free_area,该结构的描述如下:

struct free_area {
        struct list_head        free_list[MIGRATE_TYPES];
        unsigned long           nr_free;
};

在这个结构中的确有一个表示当前分配阶所对应的页框块链表free_list,不过这里稍显复杂一下,因free_list是一个链表数组,这个数组也称为迁移数组。我们可以将这个数组看作是对页框块链表的进一步细分,每个数组元素对应一种迁移类型的页框块链表。迁移列表是在内核2.6.24中引入的,它更加的避免了由于系统长期运行而产生的外部碎片。除了链表结构以外,该结构使用nr_free表示当前链表中空闲页框块的数目,比如free_area[2]中nr_free的值为5,表示有5个大小为4的页框块,那么总的页框数目为20。

根据上面对伙伴算法数据结构的描述,可以得到下面的关系图:

上图表示的是某个内存节点中的某个内存管理区中的伙伴算法示意图。需要注意的是,页框描述符page中有一个lru字段,该字段即为链接每个页框块的链表节点。

struct page {
……
        struct list_head lru;
……
};

从图中也可以看出,链表中负责连接前后页框块的是该页框块首页框中的链表节点。

Linux页框分配函数的实现(3)-快速分配函数

2012年3月2日 由 edsionte 2 条评论 »

关于页框分配函数的实现,前文中已经对主体实现函数和慢速分配函数作了简单说明。这两个函数主要的功能即根据系统内存实时的使用情况及时调整分配限制,并再次调用快速分配函数get_page_from_freelist()。

该函数可以看作是伙伴系统的前置函数,它通过传递进来的分配标志和分配阶,并结合系统当时的内存使用情况来判断是否可以进行内存分配。如果可以分配,那么进行实际的内存分配工作,既调用那些基于伙伴算法而实现的内存分配函数。

3.快速分配函数

static struct page *
get_page_from_freelist(gfp_t gfp_mask, nodemask_t *nodemask, unsigned int order,
		struct zonelist *zonelist, int high_zoneidx, int alloc_flags,
		struct zone *preferred_zone, int migratetype)
{
	struct zoneref *z;
	struct page *page = NULL;
	int classzone_idx;
	struct zone *zone;
	nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */
	int zlc_active = 0;		/* set if using zonelist_cache */
	int did_zlc_setup = 0;		/* just call zlc_setup() one time */

	classzone_idx = zone_idx(preferred_zone);

现在开始遍历指定zonelist上的zone。在通过for_each_zone_zonelist_nodemask()遍历时,该函数会过滤掉那些索引值大于high_zoneidx的zone。比如当前high_zoneidx所指定的zone为ZONE_NORMAL,那么当前遍历的zone只能为ZONE_DMA或ZONE_NORMAL类型,而不能是ZONE_HIGH,这些关系判断的依据即为这些类型对应的索引值。因为内存管理区的类型是通过枚举类型来描述的,因此索引值也就是这些类型对应的枚举值。

zonelist_scan:
	for_each_zone_zonelist_nodemask(zone, z, zonelist,
						high_zoneidx, nodemask) {
		if (NUMA_BUILD && zlc_active &&
			!zlc_zone_worth_trying(zonelist, z, allowednodes))
				continue;
		if ((alloc_flags & ALLOC_CPUSET) &&
			!cpuset_zone_allowed_softwall(zone, gfp_mask))
				goto try_next_zone;

即便当前zone的索引小于high_zoneidx,也不能急于分配内存,还要检查这个内存管理区是空闲的页框是否充足。这个过程通过上述两个if语句来完成。接下来,如果分配标志中设置了ALLOC_NO_WATERMARKS,即表明此刻不再考虑分配水位线。否则就要分析此刻内存的水位线。

通过分配标志从水位线数组中获得当前的水位线mark,再传入zone_watermark_ok()判断在当前的水位线下是否可以分配内存。如果可以分配内存则跳入try_this_zone。

		BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK); 		if (!(alloc_flags & ALLOC_NO_WATERMARKS)) { 			unsigned long mark; 			int ret; 			mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];
			if (zone_watermark_ok(zone, order, mark,
				    classzone_idx, alloc_flags))
				goto try_this_zone;

			if (zone_reclaim_mode == 0)
				goto this_zone_full;

如果运行到此处,说明此刻空闲内存不足,那么通过zone_reclaim()进行内存回收,回收的情况通过ret来描述。如果结果是ZONE_RECLAIM_NOSCAN,说明并没有进行回收,那么直接尝试下一个zone;如果结果是ZONE_RECLAIM_FULL,说明虽然进行了回收但是并没有回收到;默认的情况则是没有回收到足够多的内存。后两种情况均跳入this_zone_full处。

			ret = zone_reclaim(zone, gfp_mask, order);
			switch (ret) {
			case ZONE_RECLAIM_NOSCAN:
				/* did not scan */
				goto try_next_zone;
			case ZONE_RECLAIM_FULL:
				/* scanned but unreclaimable */
				goto this_zone_full;
			default:
				/* did we reclaim enough */
				if (!zone_watermark_ok(zone, order, mark,
						classzone_idx, alloc_flags))
					goto this_zone_full;
			}
		}

如果跳到此标号处说明可以在当前zone上分配内存,随即调用buffered_rmqueue()进入伙伴算法。

try_this_zone:
		page = buffered_rmqueue(preferred_zone, zone, order,
						gfp_mask, migratetype);
		if (page)
			break;

跳到此处说明当前zone的空闲内存不足,那么标记它。这样下次分配时直接将其忽略。

this_zone_full:
		if (NUMA_BUILD)
		        zlc_mark_zone_full(zonelist, z);

此处说明当前zone上的空闲内存不足,则需要在其他zone上尝试分配。

try_next_zone:
		if (NUMA_BUILD && !did_zlc_setup && nr_online_nodes > 1) {
			allowednodes = zlc_setup(zonelist, alloc_flags);
			zlc_active = 1;
			did_zlc_setup = 1;
		}
	}

此时,遍历zone的循环结束。如果第一次循环结束后page仍未空,则进行第二次分配,即跳入zonelist_scan重新遍历。当第二次分配结束后不管结果如何均返回。循环的次数由alc_active控制。

	if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {
		/* Disable zlc cache for second zonelist scan */
		zlc_active = 0;
		goto zonelist_scan;
	}
	return page;
}

至此,快速分配函数分析完毕。

Linux页框分配函数的实现(2)-慢速内存分配

2012年2月28日 由 edsionte 没有评论 »

2. 慢速分配函数

进入慢速分配函数后,先检查所请求的分配阶是否超过了MAX_ORDER。如果指定了GFP_THISNODE标志后,则不能继续进行慢速内存分配,因为该标志指明了内存不能进行回收,因此直接跳到nopage处的代码。

在经历一系列的参数检查之后,该函数通过调用wake_all_kswapd()唤醒每个zone所属node中的kswapd守护进程。这个守护进程负责换出很少使用的页,以提高目前系统可以用的空闲页框。

在kswapd交换进程被唤醒之后,该函数开始尝试新一轮的分配。它首先通过gfp_to_alloc_flags()对分配标志进行调整,稍微降低分配标准以便这次调用get_page_from_freelist()有可能分配到内存。

static inline struct page *
__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
        struct zonelist *zonelist, enum zone_type high_zoneidx,
        nodemask_t *nodemask, struct zone *preferred_zone,
        int migratetype)
{
        const gfp_t wait = gfp_mask & __GFP_WAIT;
        struct page *page = NULL;
        int alloc_flags;
        unsigned long pages_reclaimed = 0;
        unsigned long did_some_progress;
        struct task_struct *p = current;

        if (order >= MAX_ORDER) {
                WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
                return NULL;
        }

        if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE)
                goto nopage;

restart:
        wake_all_kswapd(order, zonelist, high_zoneidx);
        alloc_flags = gfp_to_alloc_flags(gfp_mask);
        page = get_page_from_freelist(gfp_mask, nodemask, order, zonelist,
                        high_zoneidx, alloc_flags & ~ALLOC_NO_WATERMARKS,
                        preferred_zone, migratetype);
        if (page)
                goto got_pg;

如果page不为空,则说明内存申请成功,否则继续进行慢速内存分配。如果设置了ALLOC_NO_WATERMARKS标志,那么此时会忽略水印,并此时进入__alloc_pages_high_priority()。该函数内部会至少会再调用一次get_page_from_freelist(),如果设置了__GFP_NOFAIL标志,则不断的循环等待并尝试进行内存分配。

rebalance:
        if (alloc_flags & ALLOC_NO_WATERMARKS) {
                page = __alloc_pages_high_priority(gfp_mask, order,
                                zonelist, high_zoneidx, nodemask,
                                preferred_zone, migratetype);
                if (page)
                        goto got_pg;
        }

如果没有设置__GFP_WAIT,即wait为0,则不继续进行内存分配,直接跳到nopage处。如果PF_MEMALLOC被设置,也就是说调用内存分配函数着本身就是内存回收进程,则直接跳到nopage处。

        if (!wait)
                goto nopage;

        if (p->flags & PF_MEMALLOC)
                goto nopage;

        if (test_thread_flag(TIF_MEMDIE) && !(gfp_mask & __GFP_NOFAIL))
                goto nopage;

到目前为止,分配函数已经尝试好几次页框分配。如果现在仍未分配到请求的内存,那么接下来将进入一个比较耗时的阶段。内核通过将很少使用的页换出到磁盘上,以便在物理内存中有更多的空闲页框。这个过程可能会产生阻塞,也就是说会产生睡眠,因此它比较耗时。

__alloc_pages_direct_reclaim()的作用就是先通过try_to_free_pages()回收一些最近很少用的页,将其写回磁盘上的交换区,以便在物理内存中腾出更多的空间。接着,内核会再次调用get_page_from_freelist()尝试分配内存。

        page = __alloc_pages_direct_reclaim(gfp_mask, order,
                                        zonelist, high_zoneidx,
                                        nodemask,
                                        alloc_flags, preferred_zone,
                                        migratetype, &did_some_progress);
        if (page)
                goto got_pg;

如果内核进行了上述的回收和重新分配的过程后,仍未分配成功,既did_some_progress为0,那么此时内核不的不考虑是否发生了OOM(out of memory)。如果当前请求内存的进程发生了OOM,也就是说该进程试图拥有过多的内存,那么此时内核会调用OOM killer杀死它。并且跳转到restart处,重新进行内存分配。

        if (!did_some_progress) {
                if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {
                        if (oom_killer_disabled)
                                goto nopage;
                        page = __alloc_pages_may_oom(gfp_mask, order,
                                        zonelist, high_zoneidx,
                                        nodemask, preferred_zone,
                                        migratetype);
                        if (page)
                                goto got_pg;

                        if (order > PAGE_ALLOC_COSTLY_ORDER &&
                                                !(gfp_mask & __GFP_NOFAIL))
                                goto nopage;

                        goto restart;
                }
        }

此时再次判断是否要重新进行一次内存申请。如果有这个必要,那么等待写操作完成后再次跳到rebalance处重试。

        pages_reclaimed += did_some_progress;
        if (should_alloc_retry(gfp_mask, order, pages_reclaimed)) {
                congestion_wait(BLK_RW_ASYNC, HZ/50);
                goto rebalance;
        }

页框分配函数结束时候一般有两种情况,其中之一即为分配失败,并没有得到所需页框,因此打印一些内存分配失败的信息。

nopage:
        if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
                printk(KERN_WARNING "%s: page allocation failure."
                        " order:%d, mode:0x%x\n",
                        p->comm, order, gfp_mask);
                dump_stack();
                show_mem();
        }
        return page;

另一种情况,也就是得到了所需页框,那么直接返回这组页框的首页框描述符。

got_pg:
        if (kmemcheck_enabled)
                kmemcheck_pagealloc_alloc(page, order, gfp_mask);
        return page;

}

通过上述的过程可以看到,页框分配函数__alloc_pages()会多次尝试进行分配内存。而具体的页框分配操作是在get_page_from_freelist()中完成的,它根据伙伴算法分配所需大小的页框。

echo和backslash

2012年2月14日 由 edsionte 2 条评论 »

echo命令是一个看似简单的命令,当它和转义,命令替换等相遇时,则会发生许多令人迷惑的现象。

1.echo \z和echo “\z”的不同

echo命令比较特殊,对于它本身而言,转义符加上某些字符会引发一些特殊含义,这与转义本身的含义又相反。比如\n在echo中表示回车换行,\t表示水平制表符等。不过,echo命令在bash中默认是不开启对这些特殊转义符进行解释的,如果要开启则必须加上-e选项。
对于下述的命令:

$ echo -e "\\thello"
	hello

它的执行过程是:

1).”\\thello”首先被bash解释为”\thello”。

2).”\thello”作为echo的参数,由于加入了-e,因此echo将\t解释为水平制表符。

3).显示结果。

上述命令发生了两次转义,第一即为执行过程1中bash处理命令行时,第二次即为2中echo处理自身参数时。

对于弱引用而言,双引号中的所有字符都被当做普通字符,除了\,$和反引号(本文所述的反引号就主键盘上数字1左边的符号)。

在对字符串不加引用的情况下,\会发挥其转义的特性,即显示字符字面含义,即便该字符是普通字符,因此echo \z的结果为z。而双引号中所有字符都被解释成shell解释成了普通字符,”\z”被解释的结果为\z,并且\z并不是echo的特定转义符号,因此echo “\z”的结果为\z。

edsionte@edsionte-laptop:~/mytest$ echo \z
+ echo z
z
edsionte@edsionte-laptop:~/mytest$ echo "\z"
+ echo '\z'
\z

这里你也许有疑问:弱引用是不能关闭$,\和反引号的特殊含义的,为何echo “\z”中的\没有起到转义的作用呢?

这里需要注意的是,弱引用中\符号仅对$,\,反引号和双引号这几个特殊字符起转义作用,而其他字符前的\均不起作用,也就是说shell会忽略它,将这个\作为普通字符。

edsionte@edsionte-laptop:~/mytest$ t=a
+ t=a
edsionte@edsionte-laptop:~/mytest$ echo "\$t"
+ echo '$t'
$t
edsionte@edsionte-laptop:~/mytest$ echo "\*t"
+ echo '\*t'
\*t

通过上述的分析,也就简单解释了为何echo \z和echo “\z”会有不同的结果。

2.echo `echo \z`的疑惑

接下来要说明的不是上述一条命令,而是关于它的“一系列”命令。

$ cat test2echo.sh
#!/bin/bash

echo `echo \z`
echo `echo \\z`
echo `echo \\\z`
echo `echo \\\\z`
echo `echo \\\\\\z`
echo `echo \\\\\\\z`
$ bash test2echo.sh
z
z
\z
\z
\z
\\z

这几条echo命令中均嵌套了另一个echo命令,命令替换使用的是反引号而不是$()。从上面的结果可以看出当echo遇到\时发生了一些奇怪的现象,比如为何第3,4,5条echo命令的结果是一致的。

在解释上述这几个echo命令之前,我们先看下面的脚本:

$ cat testecho.sh
#!/bin/bash

echo \z
echo \\z
echo \\\z
echo \\\\z
echo \\\\\\z
echo \\\\\\\z
$ bash testecho.sh
z
\z
\z
\\z
\\\z
\\\z

上面的脚本的结果是比较容易想到的。第一条echo中的\由于对z进行转义;第二条echo中的第一个\对第二个\进行转义;第三条echo中的第一个\对第二个\进行转义,第三个\对z进行转义;后续的echo命令的规则都是一致的。

如果将testecho.sh中的结果作为test2echo.sh中每个内层echo的输出,那么会不会得到test2echo.sh最终的结果呢?比如echo `echo \\\z`,内部echo的结果是\z,那么这个双层echo可以看作是echo \z。按照上述1中的讨论,结果应该是z。看来处理过程并不是如此。

那么echo `echo \\\z`是否可以看作是echo “\z”?根据上述1中的讨论结果,结果正确。不过对于echo `echo \\\\z`,按照这样的处理并不成立。

接下来我们使用set命令来追踪test2echo.sh的执行过程:

$ cat test2echo.sh
#!/bin/bash

set -x

echo `echo \z`
echo `echo \\z`
echo `echo \\\z`
echo `echo \\\\z`
echo `echo \\\\\\z`
echo `echo \\\\\\\z`
$ bash test2echo.sh
++ echo z
+ echo z
z
++ echo z
+ echo z
z
++ echo '\z'
+ echo '\z'
\z
++ echo '\z'
+ echo '\z'
\z
++ echo '\z'
+ echo '\z'
\z
++ echo '\\z'
+ echo '\\z'
\\z

通过加入-x选项我们可以发现内部echo的输出结果被单引号所引用,因此可以得知上述双层echo命令的结果都是内部echo的输出结果。因为每个内部echo的输出都通过单引号原封不动的作为外部echo的输入,并且单引号中的所有字符都是普通字符(除了单引号本身)。那么究竟是什么原因才导致这样令人迷惑的结果?

在上述问题1中我们已经说明过双引号中\对$,反引号,双引号和\起到转义作用,即显示这些字符的字面意思,那么这几个特殊字符前的\也将抽离所在字符串。同样,反引号中也存在这样的问题,如果反引号中有\,并且\后紧跟的字符是$,反引号,双引号和\这些字符时,那么这些特殊字符前的\将抽离。

按照上述的解释,test2echo.sh中各个echo的执行过程就明了了。以echo `echo \\\z`为例,它的执行过程如下:

1).\\\z由于反引号中的\前出现了\,因此第二个\被抽离,原始命令成为echo `echo \\z`。

2).执行反引号中的echo,原始命令成为echo ‘\z’

3).执行外部echo,结果为\z。

再举一例,比如上述的echo `echo \\\\\\\z`,它的执行过程如下:

1).内部\\\\\\\z由于反引号中的\前又出现了\,因此有三个\被抽离,原始命令成为echo `echo \\\\z`。

2).执行反引号中的echo,原始命令成为echo ‘\\z’

3).执行外部echo,结果为\\z。

其他命令的执行过程也是如此。每个命令中的反引号部分都先经过\的抽离,接着bash对字符串进行转移处理,再输入内部echo;内部echo处理完成后,传递给外部echo,最终输出结果。上述过程中的2)和3)均可以通过set -x来追踪。

 

从修改文件扩展名到子串删除

2012年1月30日 由 edsionte 没有评论 »

之前在这篇文章中已经列举了一种通用的批量修改文件后缀名的方法,今天看到变量替换${var%pattern},因此又有下面的一种方法:

#!/bin/bash

if [ $# -ne 3 ]
then
	echo "Usage:$(basename $0) old_name new_name dir"
	exit -1
fi

old_name="$1"
new_name="$2"
dir="$3"

for file in $(ls *.$old_name)
do
	newfile=${file%.$old_name}.$new_name
	mv $file $newfile
	echo "$file ===> $newfile"
done

exit 0

该脚本用到了变量替换中的子串删除方法:${var%pattern}。它的作用是从变量$var的末尾删除最小匹配$pattern字符串。与此对应的方法${var%%pattern}则是删除最大匹配$pattern字串。比如:

edsionte@edsionte-laptop:~/mytest$ var=abcd12345abc6789
edsionte@edsionte-laptop:~/mytest$ pattern=b*9
edsionte@edsionte-laptop:~/mytest$ echo "${var%$pattern}"
abcd12345a
edsionte@edsionte-laptop:~/mytest$ echo "${var%%$pattern}"
a

如果想从变量$var开头删除字符串$pattern,则可以使用${var#pattern}删除最小匹配的字符串,而${var##pattern}则可以删除最大匹配$pattern的字符串。比如:

edsionte@edsionte-laptop:~/mytest$ var=abcd12345abc6789
edsionte@edsionte-laptop:~/mytest$ pattern=a*c
edsionte@edsionte-laptop:~/mytest$ echo "${var#$pattern}"
d12345abc6789
edsionte@edsionte-laptop:~/mytest$ echo "${var##$pattern}"
6789

从变量中删除指定字符串是一种常见的操作。

windows 7 ultimate product key

windows 7 ultimate product key

winrar download free

winrar download free

winzip registration code

winzip registration code

winzip free download

winzip free download

winzip activation code

winzip activation code

windows 7 key generator

windows 7 key generator

winzip freeware

winzip freeware

winzip free download full version

winzip free download full version

free winrar download

free winrar download

free winrar

free winrar

windows 7 crack

windows 7 crack

windows xp product key

windows xp product key

windows 7 activation crack

windows7 activation crack

free winzip

free winzip

winrar free download

winrar free download

winrar free

winrar free

download winrar free

download winrar free

windows 7 product key

windows 7 product key