快乐虾 http://blog.csdn.net/lights_joy/ lights@hb165.com     本文适用于 ADI bf561 DSP 优视BF561EVB开发板 uclinux-2008r1-rc8 (移植到vdsp5) Visual DSP++ 5.0   欢迎转载，但请保留作者信息     buddy算法是用来做内存管理的经典算法，目的是为了解决内存的外碎片。 避免外碎片的方法有两种： 1，利用分页单元把一组非连续的空闲页框映射到非连续的线性地址区间。 2，开发适当的技术来记录现存的空闲连续页框块的情况，以尽量避免为满足对小块的请求而把大块的空闲块进行分割。 内核选择第二种方法。这个算法的时间效率更高，但是由于使用 best-fit 方法的缘故，会产生内存浪费。 buddy算法将所有空闲页框分组为11个块链表，每个块链表的每个块元素分别包含1,2,4,8,16,32,64,128,256,512,1024个连续的页框，每个块的第一个页框的物理地址是该块大小的整数倍。如，大小为16个页框的块，其起始地址是16*2^12(一个页框的大小为4k,16个页框的大小为16*4K,1k=1024=2的10次方，4k=2的12次方)的倍数。 例，假设要请求一个128个页框的块，算法先检查128个页框的链表是否有空闲块，如果没有则查256个页框的链表，有则将256个页框的块分裂两份，一份使用，一份插入128个页框的链表。如果还没有，就查512个页框的链表，有的话就分裂为128，128，256，一个128使用，剩余两个插入对应链表。如果在512还没查到，则返回出错信号。 回收过程相反，内核试图把大小为b的空闲伙伴合并为一个大小为2b的单独快，满足以下条件的两个块称为伙伴：1，两个块具有相同的大小，记做b；2，它们的物理地址是连续的，3，第一个块的第一个页框的物理地址是2*b*2^12的倍数，该算法迭代，如果成功合并所释放的块，会试图合并2b的块来形成更大的块。

1.1.1   查找buddy页

在buddy算法中，每一页都有一个buddy页与之相对应，使用__page_find_buddy函数可以找到指定页面对应的buddy页面： /*  * Locate the struct page for both the matching buddy in our  * pair (buddy1) and the combined O(n+1) page they form (page).  *  * 1) Any buddy B1 will have an order O twin B2 which satisfies  * the following equation:  *     B2 = B1 ^ (1 << O)  * For example, if the starting buddy (buddy2) is #8 its order  * 1 buddy is #10:  *     B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10  *  * 2) Any buddy B will have an order O+1 parent P which  * satisfies the following equation:  *     P = B & ~(1 << O)  *  * Assumption: *_mem_map is contiguous at least up to MAX_ORDER  */ static inline struct page * __page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order) {      unsigned long buddy_idx = page_idx ^ (1 << order);        return page + (buddy_idx - page_idx); } 由于每一页都可能属于不同order的buddy块，所以此函数同时接受page_idx和order做为参数。 下表给出几个不同的页号在不同的order下的buddy序号。 页号 0 1 2 3 4 5 6 7 8 9 10 11 0 0 0 0 0 0 0 0 0 0 0 0 0 1 -1 2 4 8 16 32 64 128 256 512 1024 2048 10 1 -2 4 -8 16 32 64 128 256 512 1024 2048 100 1 2 -4 8 16 -32 -64 128 256 512 1024 2048 1000 1 2 4 -8 16 -32 -64 -128 -256 -512 1024 2048 从上表中可以看出，负号表示这个页对应的BUDDY页在此页的前面，正号则表示其BUDDY页在此页的后面。 从上表还可以看出，不论输入的页号是否为2的整数倍，其BUDDY页都与其相差2的整数倍。 由于此函数只是计算BUDDY页的页面差距，它并不判断这两个页面是否符合BUDDY的条件，因此还需要一个独立的函数来判断这两个页面是否真的互为BUDDY。

1.1.2   确认两个页面是否互为buddy

要确认两个指定的页面是否互为buddy，可以使用page_is_buddy函数： /*  * This function checks whether a page is free && is the buddy  * we can do coalesce a page and its buddy if  * (a) the buddy is not in a hole &&  * (b) the buddy is in the buddy system &&  * (c) a page and its buddy have the same order &&  * (d) a page and its buddy are in the same zone.  *  * For recording whether a page is in the buddy system, we use PG_buddy.  * Setting, clearing, and testing PG_buddy is serialized by zone->lock.  *  * For recording page's order, we use page_private(page).  */ static inline int page_is_buddy(struct page *page, struct page *buddy,                                      int order) {      if (!pfn_valid_within(page_to_pfn(buddy)))     // 恒为false          return 0;        if (page_zone_id(page) != page_zone_id(buddy))          return 0;        if (PageBuddy(buddy) && page_order(buddy) == order) {          BUG_ON(page_count(buddy) != 0);          return 1;      }      return 0; } 在这里PageBuddy用于判断一个页面是否带有PG_buddy标记。注意：在初始化的时候，所有的页面都只有PG_reserved标记。 #define PageBuddy(page)     test_bit(PG_buddy, &(page)->flags)

1.1.3   内存分配

1.1.3.1             数据分配方式

在使用BUDDY分配数据之前，必须先明确数据的分配方式，这是通过GFP_xxx一系列的宏定义来控制的。可以将这些宏取或，再将值传递到内存分配函数中。 /*  * GFP bitmasks..  *  * Zone modifiers (see linux/mmzone.h - low three bits)  *  * Do not put any conditional on these. If necessary modify the definitions  * without the underscores and use the consistently. The definitions here may  * be used in bit comparisons.  */ #define __GFP_DMA  ((__force gfp_t)0x01u) #define __GFP_HIGHMEM  ((__force gfp_t)0x02u) #define __GFP_DMA32    ((__force gfp_t)0x04u)   /*  * Action modifiers - doesn't change the zoning  *  * __GFP_REPEAT: Try hard to allocate the memory, but the allocation attempt  * _might_ fail.  This depends upon the particular VM implementation.  *  * __GFP_NOFAIL: The VM implementation _must_ retry infinitely: the caller  * cannot handle allocation failures.  *  * __GFP_NORETRY: The VM implementation must not retry indefinitely.  */ #define __GFP_WAIT ((__force gfp_t)0x10u) /* Can wait and reschedule? */ #define __GFP_HIGH ((__force gfp_t)0x20u) /* Should access emergency pools? */ #define __GFP_IO   ((__force gfp_t)0x40u) /* Can start physical IO? */ #define __GFP_FS   ((__force gfp_t)0x80u) /* Can call down to low-level FS? */ #define __GFP_COLD ((__force gfp_t)0x100u) /* Cache-cold page required */ #define __GFP_NOWARN   ((__force gfp_t)0x200u) /* Suppress page allocation failure warning */ #define __GFP_REPEAT   ((__force gfp_t)0x400u) /* Retry the allocation.  Might fail */ #define __GFP_NOFAIL   ((__force gfp_t)0x800u) /* Retry for ever.  Cannot fail */ #define __GFP_NORETRY  ((__force gfp_t)0x1000u)/* Do not retry.  Might fail */ #define __GFP_COMP ((__force gfp_t)0x4000u)/* Add compound page metadata */ #define __GFP_ZERO ((__force gfp_t)0x8000u)/* Return zeroed page on success */ #define __GFP_NOMEMALLOC ((__force gfp_t)0x10000u) /* Don't use emergency reserves */ #define __GFP_HARDWALL   ((__force gfp_t)0x20000u) /* Enforce hardwall cpuset memory allocs */ #define __GFP_THISNODE ((__force gfp_t)0x40000u)/* No fallback, no policies */   #define __GFP_BITS_SHIFT 20 /* Room for 20 __GFP_FOO bits */ #define __GFP_BITS_MASK ((__force gfp_t)((1 << __GFP_BITS_SHIFT) - 1))   /* if you forget to add the bitmask here kernel will crash, period */ #define GFP_LEVEL_MASK (__GFP_WAIT|__GFP_HIGH|__GFP_IO|__GFP_FS| /               __GFP_COLD|__GFP_NOWARN|__GFP_REPEAT| /               __GFP_NOFAIL|__GFP_NORETRY|__GFP_COMP| /               __GFP_NOMEMALLOC|__GFP_HARDWALL|__GFP_THISNODE)   /* This equals 0, but use constants in case they ever change */ #define GFP_NOWAIT (GFP_ATOMIC & ~__GFP_HIGH) /* GFP_ATOMIC means both !wait (__GFP_WAIT not set) and use emergency pool */ #define GFP_ATOMIC (__GFP_HIGH) #define GFP_NOIO   (__GFP_WAIT) #define GFP_NOFS   (__GFP_WAIT | __GFP_IO) #define