Big Ben

migrate type——buddy system的好搭档

Posted on 2012-12-12 Edited on 2012-12-14

Linux一共定义5中migrate type，如下：

#define MIGRATE_UNMOVABLE     0
#define MIGRATE_RECLAIMABLE   1
#define MIGRATE_MOVABLE       2  /* 未见有使用该标志位的代码*/
#define MIGRATE_PCPTYPES      3 /* the number of types on the pcp lists */
#define MIGRATE_RESERVE       3
#define MIGRATE_ISOLATE       4 /* can't allocate from here */
#define MIGRATE_TYPES         5

为什么要定义migrate type，可以参考linux内核对伙伴系统的改进--migrate_type。简要来说就是Linux将可移动或不可移动的内存分开分配，以便最大程度的减少碎片，提升分配大块内存的能力。基于这种思路，可见上述5种migrate type最重要的就是MIGRATE_UNMOVABLE，MIGRATE_MOVABLE。另一个重要的type就是MIGRATE_RESERVE，这表示page被reserve，不接受buddy system管理，可参见函数setup_zone_migrate_reserve。在启动时，会依据water mark min来reserve一些page做备用。

这三个type是用到最多的三种，下面的fallback机制也用到了

static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {
     [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_RESERVE },
     [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_RESERVE },
     [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
     [MIGRATE_RESERVE]     = { MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE }, /* Never used */
};

migrate type在memmap_init中初始化为MIGRATE_MOVABLE，如下：

void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone,
          unsigned long start_pfn, enum memmap_context context)
{
     struct page *page;
     unsigned long end_pfn = start_pfn + size;
     unsigned long pfn;
     struct zone *z;

     if (highest_memmap_pfn < end_pfn - 1)
          highest_memmap_pfn = end_pfn - 1;

     z = &NODE_DATA(nid)->node_zones[zone];
     for (pfn = start_pfn; pfn < end_pfn; pfn++) {
……
          page = pfn_to_page(pfn);
……
          SetPageReserved(page);
          /*
          * Mark the block movable so that blocks are reserved for
          * movable at startup. This will force kernel allocations
          * to reserve their blocks rather than leaking throughout
          * the address space during boot when many long-lived
          * kernel allocations are made. Later some blocks near
          * the start are marked MIGRATE_RESERVE by
          * setup_zone_migrate_reserve()
          *
          * bitmap is created for zone's valid pfn range. but memmap
          * can be created for invalid pages (for alignment)
          * check here not to call set_pageblock_migratetype() against
          * pfn out of zone.
          */
          if ((z->zone_start_pfn <= pfn)
              && (pfn < z->zone_start_pfn + z->spanned_pages)
              && !(pfn & (pageblock_nr_pages - 1)))
               set_pageblock_migratetype(page, MIGRATE_MOVABLE);

          INIT_LIST_HEAD(&page->lru);
……
     }
}

上面的函数，遍历memmap数组，也就是该zone所有页面的page结构体，

1）首先设置page->flags的PG_reserved位，意思是不受内存管理系统控制。没错，此时仍在bootmem控制下，之后再__free_pages_bootmem时，会清除该位，将其纳入buddy系统。

2）之后set_pageblock_migratetype将所有page的migrate type设为MIGRATE_MOVABLE。之前提到的按照water mark min来reserve一些页面，顺序上在这个函数的后面才会被调用。

3）再看一下migrate type的初始化函数，set_pageblock_migratetype -> set_pageblock_flags_group

void set_pageblock_flags_group(struct page *page, unsigned long flags,
                         int start_bitidx, int end_bitidx)
{
     struct zone *zone;
     unsigned long *bitmap;
     unsigned long pfn, bitidx;
     unsigned long value = 1;

     zone = page_zone(page);
     pfn = page_to_pfn(page);
     bitmap = get_pageblock_bitmap(zone, pfn);
     bitidx = pfn_to_bitidx(zone, pfn);

     for (; start_bitidx <= end_bitidx; start_bitidx++, value <<= 1)
          if (flags & value)
               __set_bit(bitidx + start_bitidx, bitmap);
          else
               __clear_bit(bitidx + start_bitidx, bitmap);
}
没有想象的那么简单吧，其中有一个bitmap，他是什么呢？如下：

static unsigned long __init usemap_size(unsigned long zonesize)
{
     unsigned long usemapsize;

     usemapsize = roundup(zonesize, pageblock_nr_pages);
     usemapsize = usemapsize >> pageblock_order;
     usemapsize *= NR_PAGEBLOCK_BITS;
     usemapsize = roundup(usemapsize, 8 * sizeof(unsigned long));

     return usemapsize / 8;
}

static void __init setup_usemap(struct pglist_data *pgdat,
                    struct zone *zone, unsigned long zonesize)
{
     unsigned long usemapsize = usemap_size(zonesize);
     zone->pageblock_flags = NULL;
     if (usemapsize)
          zone->pageblock_flags = alloc_bootmem_node(pgdat, usemapsize);
}

所谓的bitmap就是zone->pageblock_flags。每个zone被分割成若干个pageblock，每个pageblock分配3位来表示migrate type。pageblock其实就是freearea中order最大的一块内存，从下面的代码可以看出来：

free_area_init_core -> set_pageblock_order(pageblock_default_order())

static inline int pageblock_default_order(void)
{
     if (HPAGE_SHIFT > PAGE_SHIFT)
          return HUGETLB_PAGE_ORDER;

     return MAX_ORDER-1;
}

在使用的时候，用get_pageblock_migratetype(page)来获得本page的migrate type。因为只要没有做migrate type的迁移，每个page的migrate type总是和他所在的pageblock是一致的。migrate type只会在fallback机制中改变。也就是分配内存，在本migrate type中无内存可分配，就要去备用的migrate type列表中找最大块内存，迁移过来，再不济还有reserved的页面。

下面分析一下migrate type是如何改变的。还是有点小复杂的。

1）首先所有讲到fallback机制的资料上都会提醒我们注意，在从backup migratetype中取内存时，是从大的order往小order递减，直到我们需要的order，如果没有就返回NULL

2）第二点值得注意的是，并不是fallback机制一起作用，page的migratetype就会改变。而是在满足一定的条件的情况下才会发生。条件就是红圈中的，以及下面的page moved >= pageblock / 2。什么意思呢？就是说，当找到的这块大内存的order超过pageblock_order的一半，以7800为例，default pageblock_order是MAX_ORDER-1 = 10，则这块内存order要超过5，就是32个page。第二个条件就是，这块大内存所在的pageblock上有超过一半的空闲buddy。若满足这两点，这块内存所在的pageblock的migratetype会被修改，那么属于他且已分配出去的buddy在释放时，会被合并到新的migratetype中。

3）我们在测试上面所说的第二个条件时，会先将pageblock中空闲的buddy移到新的migratetype中，但并不真正的改变其migratetype。因为涉及到获取migratetype的操作，都是通过函数get_pageblock_migratetype来实现的。所以只要不修改整块pageblock的migratetype就不会影响到其下所有buddy的migratetype属性。

4）当找到的这块大内存超过pageblock时，会将其下所有的pageblock的migratetype都修改成我们所需要的migratetype。其实这里反映出的思想和上面是一样的，就是找到的空闲内存足够大，就迁移migratetype。

5）最后值得注意的一点就是，红圈中的条件判断其实不完整，真实代码中的判断是这样的：

if (unlikely(current_order >= (pageblock_order >> 1)) ||
start_migratetype == MIGRATE_RECLAIMABLE ||
page_group_by_mobility_disabled) { …… }
page_group_by_mobility_disabled表示迁移特性关闭，也就是说页面并不受migratetype所限制，那页面应该可以随心所欲的迁移，实际上确实如此，后面如果page_group_by_mobility_disabled，也并不需要判断有多少free buddy，就可以迁移页面了。

另外一个，start_migratetype == MIGRATE_RECLAIMABLE就值得推敲了。所有代码中都没有看到对其的使用。网络上对其的解释是：

可回收页：不能直接移动，但可以删除，其内容可以从某些源重新生成

所以我认为MIGRATE_RECLAIMABLE因为很容易被释放（或叫回收），他也是MIGRATE_UNMOVABLE和MIGRATE_MOVABLE的第一替补，所以不管找到的空闲页面有多大，都应该尽可能的迁移给他。

migrate type——buddy system的好搭档

Posted on 2012-12-12 Edited on 2012-12-14

Linux一共定义5中migrate type，如下：

#define MIGRATE_UNMOVABLE     0
#define MIGRATE_RECLAIMABLE   1
#define MIGRATE_MOVABLE       2  /* 未见有使用该标志位的代码*/
#define MIGRATE_PCPTYPES      3 /* the number of types on the pcp lists */
#define MIGRATE_RESERVE       3
#define MIGRATE_ISOLATE       4 /* can't allocate from here */
#define MIGRATE_TYPES         5

为什么要定义migrate type，可以参考linux内核对伙伴系统的改进--migrate_type。简要来说就是Linux将可移动或不可移动的内存分开分配，以便最大程度的减少碎片，提升分配大块内存的能力。基于这种思路，可见上述5种migrate type最重要的就是MIGRATE_UNMOVABLE，MIGRATE_MOVABLE。另一个重要的type就是MIGRATE_RESERVE，这表示page被reserve，不接受buddy system管理，可参见函数setup_zone_migrate_reserve。在启动时，会依据water mark min来reserve一些page做备用。

这三个type是用到最多的三种，下面的fallback机制也用到了

static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {
     [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_RESERVE },
     [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_RESERVE },
     [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
     [MIGRATE_RESERVE]     = { MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE }, /* Never used */
};

migrate type在memmap_init中初始化为MIGRATE_MOVABLE，如下：

void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone,
          unsigned long start_pfn, enum memmap_context context)
{
     struct page *page;
     unsigned long end_pfn = start_pfn + size;
     unsigned long pfn;
     struct zone *z;

     if (highest_memmap_pfn < end_pfn - 1)
          highest_memmap_pfn = end_pfn - 1;

     z = &NODE_DATA(nid)->node_zones[zone];
     for (pfn = start_pfn; pfn < end_pfn; pfn++) {
……
          page = pfn_to_page(pfn);
……
          SetPageReserved(page);
          /*
          * Mark the block movable so that blocks are reserved for
          * movable at startup. This will force kernel allocations
          * to reserve their blocks rather than leaking throughout
          * the address space during boot when many long-lived
          * kernel allocations are made. Later some blocks near
          * the start are marked MIGRATE_RESERVE by
          * setup_zone_migrate_reserve()
          *
          * bitmap is created for zone's valid pfn range. but memmap
          * can be created for invalid pages (for alignment)
          * check here not to call set_pageblock_migratetype() against
          * pfn out of zone.
          */
          if ((z->zone_start_pfn <= pfn)
              && (pfn < z->zone_start_pfn + z->spanned_pages)
              && !(pfn & (pageblock_nr_pages - 1)))
               set_pageblock_migratetype(page, MIGRATE_MOVABLE);

          INIT_LIST_HEAD(&page->lru);
……
     }
}

上面的函数，遍历memmap数组，也就是该zone所有页面的page结构体，

1）首先设置page->flags的PG_reserved位，意思是不受内存管理系统控制。没错，此时仍在bootmem控制下，之后再__free_pages_bootmem时，会清除该位，将其纳入buddy系统。

2）之后set_pageblock_migratetype将所有page的migrate type设为MIGRATE_MOVABLE。之前提到的按照water mark min来reserve一些页面，顺序上在这个函数的后面才会被调用。

3）再看一下migrate type的初始化函数，set_pageblock_migratetype -> set_pageblock_flags_group

void set_pageblock_flags_group(struct page *page, unsigned long flags,
                         int start_bitidx, int end_bitidx)
{
     struct zone *zone;
     unsigned long *bitmap;
     unsigned long pfn, bitidx;
     unsigned long value = 1;

     zone = page_zone(page);
     pfn = page_to_pfn(page);
     bitmap = get_pageblock_bitmap(zone, pfn);
     bitidx = pfn_to_bitidx(zone, pfn);

     for (; start_bitidx <= end_bitidx; start_bitidx++, value <<= 1)
          if (flags & value)
               __set_bit(bitidx + start_bitidx, bitmap);
          else
               __clear_bit(bitidx + start_bitidx, bitmap);
}
没有想象的那么简单吧，其中有一个bitmap，他是什么呢？如下：

static unsigned long __init usemap_size(unsigned long zonesize)
{
     unsigned long usemapsize;

     usemapsize = roundup(zonesize, pageblock_nr_pages);
     usemapsize = usemapsize >> pageblock_order;
     usemapsize *= NR_PAGEBLOCK_BITS;
     usemapsize = roundup(usemapsize, 8 * sizeof(unsigned long));

     return usemapsize / 8;
}

static void __init setup_usemap(struct pglist_data *pgdat,
                    struct zone *zone, unsigned long zonesize)
{
     unsigned long usemapsize = usemap_size(zonesize);
     zone->pageblock_flags = NULL;
     if (usemapsize)
          zone->pageblock_flags = alloc_bootmem_node(pgdat, usemapsize);
}

所谓的bitmap就是zone->pageblock_flags。每个zone被分割成若干个pageblock，每个pageblock分配3位来表示migrate type。pageblock其实就是freearea中order最大的一块内存，从下面的代码可以看出来：

free_area_init_core -> set_pageblock_order(pageblock_default_order())

static inline int pageblock_default_order(void)
{
     if (HPAGE_SHIFT > PAGE_SHIFT)
          return HUGETLB_PAGE_ORDER;

     return MAX_ORDER-1;
}

在使用的时候，用get_pageblock_migratetype(page)来获得本page的migrate type。因为只要没有做migrate type的迁移，每个page的migrate type总是和他所在的pageblock是一致的。migrate type只会在fallback机制中改变。也就是分配内存，在本migrate type中无内存可分配，就要去备用的migrate type列表中找最大块内存，迁移过来，再不济还有reserved的页面。

下面分析一下migrate type是如何改变的。还是有点小复杂的。

1）首先所有讲到fallback机制的资料上都会提醒我们注意，在从backup migratetype中取内存时，是从大的order往小order递减，直到我们需要的order，如果没有就返回NULL

2）第二点值得注意的是，并不是fallback机制一起作用，page的migratetype就会改变。而是在满足一定的条件的情况下才会发生。条件就是红圈中的，以及下面的page moved >= pageblock / 2。什么意思呢？就是说，当找到的这块大内存的order超过pageblock_order的一半，以7800为例，default pageblock_order是MAX_ORDER-1 = 10，则这块内存order要超过5，就是32个page。第二个条件就是，这块大内存所在的pageblock上有超过一半的空闲buddy。若满足这两点，这块内存所在的pageblock的migratetype会被修改，那么属于他且已分配出去的buddy在释放时，会被合并到新的migratetype中。

3）我们在测试上面所说的第二个条件时，会先将pageblock中空闲的buddy移到新的migratetype中，但并不真正的改变其migratetype。因为涉及到获取migratetype的操作，都是通过函数get_pageblock_migratetype来实现的。所以只要不修改整块pageblock的migratetype就不会影响到其下所有buddy的migratetype属性。

4）当找到的这块大内存超过pageblock时，会将其下所有的pageblock的migratetype都修改成我们所需要的migratetype。其实这里反映出的思想和上面是一样的，就是找到的空闲内存足够大，就迁移migratetype。

5）最后值得注意的一点就是，红圈中的条件判断其实不完整，真实代码中的判断是这样的：

if (unlikely(current_order >= (pageblock_order >> 1)) ||
start_migratetype == MIGRATE_RECLAIMABLE ||
page_group_by_mobility_disabled) { …… }
page_group_by_mobility_disabled表示迁移特性关闭，也就是说页面并不受migratetype所限制，那页面应该可以随心所欲的迁移，实际上确实如此，后面如果page_group_by_mobility_disabled，也并不需要判断有多少free buddy，就可以迁移页面了。

另外一个，start_migratetype == MIGRATE_RECLAIMABLE就值得推敲了。所有代码中都没有看到对其的使用。网络上对其的解释是：

可回收页：不能直接移动，但可以删除，其内容可以从某些源重新生成

所以我认为MIGRATE_RECLAIMABLE因为很容易被释放（或叫回收），他也是MIGRATE_UNMOVABLE和MIGRATE_MOVABLE的第一替补，所以不管找到的空闲页面有多大，都应该尽可能的迁移给他。

伙伴系统buddy allocator (1)——初始化

Posted on 2012-12-08 Edited on 2018-09-07

之前有学习过bootmem和memblock两种内存分配方式，分别在笔记 memblock工作原理和 bootmem工作原理中有所记录。这是两种在启动阶段使用的内存分配方式。至于为什么开始的时候要用bootmem这种简单的分配方式，而不直接上伙伴系统呢，Gorman在其书中这样指出：

It is impractical to statically initialize all the core kernel memory structures at compile time because there are simply far too many permutations of hardware con-ﬁgurations. To set up even the basic structures, though, requires memory because even the physical page allocator, discussed in the next chapter, needs to allocate memory to initialize itself.
-- 《Understanding the Linux®Virtual Memory Manager》

简而言之，就是不管是buddy allocator还是slab allocator，都太复杂，牵涉到各种对抗碎片的机制，其本身的初始化就要牵涉到内存分配的事情，所以Linux kernel先用bootmem等简单机制顶一阵，之后再把所有内存都分配给伙伴系统，交给他管理。

本篇先说伙伴系统的初始化。关于伙伴系统就不做介绍了，具体可以参考Linux伙伴系统(一)--伙伴系统的概述 - vanbreaker的专栏 - 博客频道 - CSDN.NET。下面简单列一下涉及到的几个数据结构。

struct zone {
……
     struct per_cpu_pageset __percpu *pageset;
……
struct free_area     free_area[MAX_ORDER];
……
}

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

不一一作解释了，只说一下和伙伴系统相关的部分。所有的伙伴系统的概念，其实都是在zone->free_area[MAX_ORDER]中，借用Gorman的一幅图
每一个order的free_area都有自己的一组按migrate type分类的list，nr_free表示这个order共有多少个空闲块。而list中的节点就是page->lru。

下面开始真正的初始化：
如果不考虑高端内存的话，核心函数就在free_all_bootmem。free_all_bootmem就是在遍历bootmem，并释放bdata_list上的每一块bootmem。下面以释放一块的代码为例。
  while (start < end) {

unsigned long *map, idx, vec;

          map = bdata->node_bootmem_map;
          idx = start - bdata->node_min_pfn;
          vec = ~map[idx / BITS_PER_LONG]; // vec是map取反，则vec中0表示已分配，1表示未分配

/* aligned的含义是，start有没有和LONG边界对齐，
* 没有的话，多出来的部分，也要按order 0来释放
*/
          if (aligned && vec == ~0UL && start + BITS_PER_LONG < end) {
               int order = ilog2(BITS_PER_LONG);

               __free_pages_bootmem(pfn_to_page(start), order);
               count += BITS_PER_LONG;
          } else {
               unsigned long off = 0;

               while (vec && off < BITS_PER_LONG) {
                    if (vec & 1) {
                         page = pfn_to_page(start + off);
                         __free_pages_bootmem(page, 0);
                         count++;
                    }
                    vec >>= 1;
                    off++;
               }
          }
          start += BITS_PER_LONG;
}
这个函数看起来其实很简单，他的核心内容都在释放bootmem上，不管是整片释放还是按页释放，最后都会落到函数__free_pages_bootmem里。其处理流程是
1）__ClearPageReserved
2）所有page count设为0，set_page_count(page, 0)
3）page block首页count设为1，set_page_refcounted(page);
4）__free_pages(page, order);
所以最后归根结底就到了__free_pages。这是一个很重要的函数，也包含了很多知识点。其定义在mm/page_alloc.c中。

所有的释放被分成两种情况：1）单页释放 2）按order释放。

1.单页释放

如果是单页的话，则将之释放到zone->pageset中，冷页加入头部，热页加入尾部。关于冷热页可以参考笔记认识Linux物理内存管理系统--Buddy System。简单来说，zone->pageset是个per-CPU变量，每个pageset有个struct per_cpu_pages pcp成员，这个成员就代表着一组page。所有的page就在下面的lists这组列表中。那么这组内存从何而来，从初始化的进程看来，就是在释放bootmem时候的这些单个页，就被释放到per-CPU内存中。之所以要有这个per-CPU的内存，是为了减少在分配1页这种小内存时，还要获取zone->lock来锁住整个区域，这样很不划算。
struct per_cpu_pageset {
     struct per_cpu_pages pcp;
     ……
};

struct per_cpu_pages {
     int count;          /* number of pages in the list */
     int high;          /* high watermark, emptying needed */
     int batch;          /* chunk size for buddy add/remove */

     /* Lists of pages, one per migrate type stored on the pcp-lists */
     struct list_head lists[MIGRATE_PCPTYPES];
};

所谓的冷和热，就是指是否在CPU高速缓存中，一般是在L2 Cache。zone->pageset->pcp[n]这张表上的项，也就是页面按照一定的规则被换入换出，头部最有可能是在热区，那么尾部就最有可能在冷区。所以假如分配单独页面时，尽量分配该list的头部页面。
pcp->high, batch，是维护这些list的指标，当所有lists中页面总数超过high的时候，就要释放batch个页面到buddy system。也就是free_pcppages_bulk，其过程跟后面的__free_pages_ok是一样的。high, batch的初始化是在setup_per_cpu_pageset->setup_zone_pageset(zone)->setup_pageset(pcp, zone_batchsize(zone)) -> zone_batchsize(zone)。其选择是有一定讲究的，有兴趣的可以参考mm\page_alloc.c。

2.按order释放

按order来释放，反而过程简单清晰一些，只是通过几个小技巧找到本order块的buddy，以及合成后的combined index，之后只要不断的向上合并到不能合并为之，再set order，就大功告成。加入没有buddy的话，就直接set order，同时会用__SetPageBuddy来设置page结构的flags的第19位PG_buddy位，表示本page已释放，并在buddy list上。最后一点要注意的就是，合成好后的block如果小于MAX_ORDER的，还要放在zone->free_area[order].list的尾部，以便尽量不被分配出去，最好能继续被合并成大块。

这里值得欣赏的是，怎么找到buddy和combined index。

找到buddy，其实就是一个表达式

page_idx ^ (1<<order)

仔细算算吧，他就是page_idx +/- (2^order)，若page_idx的order位为1，相当于减，order位为0相当于加。这个式子太优美了。还有怎么找到parent index呢？同样很简洁

combined_idx = page_idx & (1<<order)

值得好好学习学习。

伙伴系统buddy allocator (1)——初始化

Posted on 2012-12-08 Edited on 2018-09-07

之前有学习过bootmem和memblock两种内存分配方式，分别在笔记 memblock工作原理和 bootmem工作原理中有所记录。这是两种在启动阶段使用的内存分配方式。至于为什么开始的时候要用bootmem这种简单的分配方式，而不直接上伙伴系统呢，Gorman在其书中这样指出：

It is impractical to statically initialize all the core kernel memory structures at compile time because there are simply far too many permutations of hardware con-ﬁgurations. To set up even the basic structures, though, requires memory because even the physical page allocator, discussed in the next chapter, needs to allocate memory to initialize itself.
-- 《Understanding the Linux®Virtual Memory Manager》

简而言之，就是不管是buddy allocator还是slab allocator，都太复杂，牵涉到各种对抗碎片的机制，其本身的初始化就要牵涉到内存分配的事情，所以Linux kernel先用bootmem等简单机制顶一阵，之后再把所有内存都分配给伙伴系统，交给他管理。

本篇先说伙伴系统的初始化。关于伙伴系统就不做介绍了，具体可以参考Linux伙伴系统(一)--伙伴系统的概述 - vanbreaker的专栏 - 博客频道 - CSDN.NET。下面简单列一下涉及到的几个数据结构。

struct zone {
……
     struct per_cpu_pageset __percpu *pageset;
……
struct free_area     free_area[MAX_ORDER];
……
}

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

不一一作解释了，只说一下和伙伴系统相关的部分。所有的伙伴系统的概念，其实都是在zone->free_area[MAX_ORDER]中，借用Gorman的一幅图
每一个order的free_area都有自己的一组按migrate type分类的list，nr_free表示这个order共有多少个空闲块。而list中的节点就是page->lru。

下面开始真正的初始化：
如果不考虑高端内存的话，核心函数就在free_all_bootmem。free_all_bootmem就是在遍历bootmem，并释放bdata_list上的每一块bootmem。下面以释放一块的代码为例。
  while (start < end) {

unsigned long *map, idx, vec;

          map = bdata->node_bootmem_map;
          idx = start - bdata->node_min_pfn;
          vec = ~map[idx / BITS_PER_LONG]; // vec是map取反，则vec中0表示已分配，1表示未分配

/* aligned的含义是，start有没有和LONG边界对齐，
* 没有的话，多出来的部分，也要按order 0来释放
*/
          if (aligned && vec == ~0UL && start + BITS_PER_LONG < end) {
               int order = ilog2(BITS_PER_LONG);

               __free_pages_bootmem(pfn_to_page(start), order);
               count += BITS_PER_LONG;
          } else {
               unsigned long off = 0;

               while (vec && off < BITS_PER_LONG) {
                    if (vec & 1) {
                         page = pfn_to_page(start + off);
                         __free_pages_bootmem(page, 0);
                         count++;
                    }
                    vec >>= 1;
                    off++;
               }
          }
          start += BITS_PER_LONG;
}
这个函数看起来其实很简单，他的核心内容都在释放bootmem上，不管是整片释放还是按页释放，最后都会落到函数__free_pages_bootmem里。其处理流程是
1）__ClearPageReserved
2）所有page count设为0，set_page_count(page, 0)
3）page block首页count设为1，set_page_refcounted(page);
4）__free_pages(page, order);
所以最后归根结底就到了__free_pages。这是一个很重要的函数，也包含了很多知识点。其定义在mm/page_alloc.c中。

所有的释放被分成两种情况：1）单页释放 2）按order释放。

1.单页释放

如果是单页的话，则将之释放到zone->pageset中，冷页加入头部，热页加入尾部。关于冷热页可以参考笔记认识Linux物理内存管理系统--Buddy System。简单来说，zone->pageset是个per-CPU变量，每个pageset有个struct per_cpu_pages pcp成员，这个成员就代表着一组page。所有的page就在下面的lists这组列表中。那么这组内存从何而来，从初始化的进程看来，就是在释放bootmem时候的这些单个页，就被释放到per-CPU内存中。之所以要有这个per-CPU的内存，是为了减少在分配1页这种小内存时，还要获取zone->lock来锁住整个区域，这样很不划算。
struct per_cpu_pageset {
     struct per_cpu_pages pcp;
     ……
};

struct per_cpu_pages {
     int count;          /* number of pages in the list */
     int high;          /* high watermark, emptying needed */
     int batch;          /* chunk size for buddy add/remove */

     /* Lists of pages, one per migrate type stored on the pcp-lists */
     struct list_head lists[MIGRATE_PCPTYPES];
};

所谓的冷和热，就是指是否在CPU高速缓存中，一般是在L2 Cache。zone->pageset->pcp[n]这张表上的项，也就是页面按照一定的规则被换入换出，头部最有可能是在热区，那么尾部就最有可能在冷区。所以假如分配单独页面时，尽量分配该list的头部页面。
pcp->high, batch，是维护这些list的指标，当所有lists中页面总数超过high的时候，就要释放batch个页面到buddy system。也就是free_pcppages_bulk，其过程跟后面的__free_pages_ok是一样的。high, batch的初始化是在setup_per_cpu_pageset->setup_zone_pageset(zone)->setup_pageset(pcp, zone_batchsize(zone)) -> zone_batchsize(zone)。其选择是有一定讲究的，有兴趣的可以参考mm\page_alloc.c。

2.按order释放

按order来释放，反而过程简单清晰一些，只是通过几个小技巧找到本order块的buddy，以及合成后的combined index，之后只要不断的向上合并到不能合并为之，再set order，就大功告成。加入没有buddy的话，就直接set order，同时会用__SetPageBuddy来设置page结构的flags的第19位PG_buddy位，表示本page已释放，并在buddy list上。最后一点要注意的就是，合成好后的block如果小于MAX_ORDER的，还要放在zone->free_area[order].list的尾部，以便尽量不被分配出去，最好能继续被合并成大块。

这里值得欣赏的是，怎么找到buddy和combined index。

找到buddy，其实就是一个表达式

page_idx ^ (1<<order)

仔细算算吧，他就是page_idx +/- (2^order)，若page_idx的order位为1，相当于减，order位为0相当于加。这个式子太优美了。还有怎么找到parent index呢？同样很简洁

combined_idx = page_idx & (1<<order)

值得好好学习学习。

Linux内存之页表

Posted on 2012-11-23

Linux的相关页表的框架在 vmalloc分析中，__vmalloc_area_node调用流程与分配页表项两节中已经有所阐述。本文再做一些总体上的把握。文中会借用其中的一些图。

所谓的页表结构如下。针对现在的64位操作系统，Linux已经可以支持4级页表操作，即pgd，pud，pmd和pte。但目前一般嵌入式的应用并不会使能该功能，所以在代码中涉及到pud和pmd的指针，实际都是指向pgd表项的。

简单介绍下这幅图

1. 所有Linux都是4G的地址空间，每个表项代表2MB空间，共2K表项，占2个page

2. 所有的内存在表中都是有序的，即物理地址在这个空间中也是有低到高的

2. 每个pgd表项指向一个page，4KB，分成4个子表如上图。

3. 下面的两个子表2KB，包含512个表项，正好2MB空间，视为一个pte，其中每个表项指向一个page

pgd表保存在进程的mm_struct中

struct mm_struct {

……

pgd_t * pgd;

……

}

pte_alloc_map / pte_alloc_map_lock / pte_alloc_kernel这几个函数为pgd的每个表项分配他所指向的那一页数据，其实就是pte。

因为内存会不断的分配，不可能每次分配一个page都会新建这样的一张表格，所以Linux为每个pgd表项（代码中为了兼容，还是将之称为pmd）加入了一些标志位，并在每次分配之前，用宏pmd_present(*(pmd))来检验此pte是否已经分配了，如果已经分配就不会再分配了。这个标志位是怎么分配的呢？vmalloc分析也有所分析。即函数pmd_populate_kernel，其实还有其他函数，例如pmd_populate。他们调用这的最终函数都同是__pmd_populate。即

pmdp[0] = __pmd(pmdval) ; // = pmdval

pmdp[1] = __pmd(pmdval + 256 * sizeof(pte_t)); // = pmdval + 256 * sizeof(pte_t)

pmd_populate是在为用户空间的地址建立页表，而pmd_populate_kernel是在为内核地址建立页表。所以他们之间的差别便水到渠成了：

1. 两者为pmd填充的内容不一样

pmd_populate_kernel：__pa(pte_ptr) | _PAGE_KERNEL_TABLE

pmd_populate：page_to_pfn(ptep) << PAGE_SHIFT | _PAGE_USER_TABLE

可见，一个是物理地址+kernel标志，另一个是内核逻辑地址+user标志

2. 两者传入的参数也不同

pmd_populate_kernel传入的是内核逻辑地址

pmd_populate传入的则是page结构指针

不管怎么样，其实他们的实质是一样的，pmd的内容都是这一个page表格所在的具体位置（物理地址，或者物理地址偏移PAGE_SHIFT的内核逻辑地址）+一个标志内核进程还是用户进程的标志位。

至此，pte（或者pmd）的内容就讲清楚了，那有了这页表格后，就顺利成章的该往里面填pte表项了。首先用pte_offset_map / pte_offset_kernel找到表格中对应的表项，然后用函数set_pte_at真正的做填充。set_pte_at最终会调用到一个汇编函数set_pte_ext。如果不考虑高端内存的话，pte_offset_map和pte_offset_kernel是一样的，都

= pmd_page_vaddr(*(dir)) + __pte_index(addr)

前半部分是pmd的逻辑地址，后半部分是本page在pmd中的偏移量。

=========================分割线===================================

说了这么多，页表的建立就是这么些事情了。下面再举个小小的例子，是mmap实现的一种方式remap_pfn_range。mmap要做的事情是把一个文件（包括设备文件，如果是设备文件，则要驱动来支持）映射到一款内存地址上，那remap_pfn_range就是要为一段物理page建立页表项。先看他们的原型：

mmap (caddr_t addr, size_t len, int prot, int flags, int fd, off_t offset)

int remap_pfn_range(struct vm_area_struct *vma,

unsigned long virt_addr, unsigned long pfn,
unsigned long size, pgprot_t prot);

上面的mmap是Linux的API，可以针对普通文件和设备文件，所以比较有普遍性，下面是驱动中为了实现mmap经常会用到的remap_pfn_range函数。理一下他们的参数之间的对应关系：

mmap remap_pfn_range

addr <=> vma, virt_addr

fd,offset,len <=> pfn, size

调用过程就是：

1. 应用程序调用mmap来映射一个文件fd中offset~offset+len这一部分。

2. 内核按照传入的参数来，分配一个vma_area_struct，这个结构包含了所有要分配的地址映射的信息，包括物理地址（fd, offset,len）和虚拟地址空间（addr），所以remap_pfn_range的参数virt_addr，pfn，size，都在vma中有所描述了。至于为什么要这样做，我猜是为了提供灵活性，毕竟vma可以超过我们需要映射的地址空间，比如内核在分配vma时发现有两个vma可以合并，则传入的vma就大于我们需要的空间，这样就可以用virt_addr，pfn，size来说明我们需要的映射。

remap_pfn_range最核心的部分就是为virt_addr~virt_addr+PAGE_ALIGN(size)的区间建立页表，代码如下

int remap_pfn_range(struct vm_area_struct *vma, unsigned long addr,
unsigned long pfn, unsigned long size, pgprot_t prot)
{

……

do {

        next = pgd_addr_end(addr, end);
        err = remap_pud_range(mm, pgd, addr, next,
                pfn + (addr >> PAGE_SHIFT), prot);
        if (err)
            break;
    } while (pgd++, addr = next, addr != end);

……

}

remap_pud_range -> remap_pmd_range -> remap_pte_range

前面两个是虚的，最后一个就是建立页表了

static int remap_pte_range(struct mm_struct *mm, pmd_t *pmd,

unsigned long addr, unsigned long end,
unsigned long pfn, pgprot_t prot)

{
……
    pte = pte_alloc_map_lock(mm, pmd, addr, &ptl);
……
    do {
        set_pte_at(mm, addr, pte, pte_mkspecial(pfn_pte(pfn, prot)));
        pfn++;
    } while (pte++, addr += PAGE_SIZE, addr != end);
……
}

传入的参数

1. pmd就是我们之前提到的pgd表项指向的那1个page

2. addr~end是要建立页表的虚拟地址范围

3. pfn是这块虚拟地址范围首地址的物理地址帧号

4. prot是一些标志位

内存页的wait-wake机制

Posted on 2012-11-13 Edited on 2012-11-22

关于内存也在分配时的等待唤醒机制，include/linux/mmzone.h 389行的注释为我们指出了用户可用的最基本的两个接口函数，__wait_on_page_locked / unlock_page，定义在mm/filemap.c中。但经过检查发现，真正能提供使用的其实是wait_on_page_locked函数，并没有__wait_on_page_locked 的实现。其作为一个定义在头文件中的inline函数，可以被包含此头文件的c文件调用，其实现主要是通过wait_on_page_bit函数。

* __wait_on_page_locked() and unlock_page() in mm/filemap.c, are the
* primary users of these fields, and in mm/page_alloc.c
* free_area_init_core() performs the initialization of them.

wait_on_page_bit的调用流程如下：

看起来很简单，不过里面暗藏玄机。

1）DEFINE_WAIT_BIT做了很多事情

它是标准的Linux等待机制中DEFINE_WAIT的变种。其中包含了标准的等待队列的成员变量wait_queue_t。另外包含了一个bit，通过word和bit_nr指定。

2）__wait_on_bit通过page_waitqueue来找到队列头，这里面就牵涉到哈希的问题，具体可以参考linux内核哈希查找（1）_zhe_wang-ChinaUnix博客，这里简要介绍一下。

哈希表共有表项size个，2^size >= pages / PAGES_PER_WAITQUEUE = pages/256

用来计算哈希值的wait_table_bits，是size中第一个1位的索引

哈希值的计算就是通过，该页的page结构指针（在mem_map数组中），wait_table_bits

所谓的哈希计算就是将这两个变量，通过一个巧妙的计算，生成某个区间内的随机值，然后散列到哈希表中，如果哈希冲突，则同一个表项采用链表的形式表示若干个成员。所以哈希值又叫散列值。

这里的哈希计算方法，就是(val * GOLDEN_RATIO_PRIME_32) >>(32 - bits)，GOLDEN_RATIO_PRIME_32是个很特别的值，经过研究，固定下来的，用它乘过之后，溢出后剩下来的值，随机性比较大。因为bits是size的第一个1，所以右移后的值一定<size，正好符合我们的要求。

3）在__wait_on_bit中会不断测试page->flags的PageLocked位，即第0位。然后会在真正要休眠的时候调用传入的sync_page，这个函数不复杂，但牵涉很广，和address_space结构有关。

4）在做完一系列的sync之后，最后调用io_schedule，让出处理器，进行等待。

unlock_page一样通过page结构指针和PageLocked位，找到哈希表中的等待队列。但一个哈希表项可以有256个page等在其中，所以不确定是怎么唤醒想要的那个page的。可能和wait->func=wake_bit_function有关。牵扯到wait queue机制。

find_next_zero_bit

Posted on 2012-11-12

unsigned long find_next_zero_bit(const unsigned long *addr,

unsigned long size,
unsigned long offset)

这个函数的用意是在addr开始的地址段中，找到一个为0的位，函数调用成功则返回该位的索引，如果没找到，则返回size。所以可以看出搜索范围并不包含size这个点，因为即便size这个点为0，满足要求，但其返回值和失败时的返回值是相同的，所以也看作是失败。

搜索示意图如下：

再分析代码：

unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
                 unsigned long offset)
{
    const unsigned long *p = addr + BITOP_WORD(offset);
    unsigned long result = offset & ~(BITS_PER_LONG-1); // result如上图，搜索起始点所在ULONG之前所有的bit
    unsigned long tmp;

    if (offset >= size)
        return size;
    size -= result; // 扣掉result，即size_new
    offset %= BITS_PER_LONG; // 取得所在ULONG中的偏移量，即offset_new
    if (offset) {
        tmp = *(p++);
        tmp |= ~0UL >> (BITS_PER_LONG - offset); // 将offset之内的bit全部置1，参看图1
        if (size < BITS_PER_LONG) // 这表示搜索范围在一个ULONG范围之内，参看图2
            goto found_first;
        if (~tmp) // tmp至少有一个0位，即tmp的BPL - offset这一段中至少有一个0。

            goto found_middle;
        size -= BITS_PER_LONG;
        result += BITS_PER_LONG;
    }
    while (size & ~(BITS_PER_LONG-1)) { // 不断遍历size前的ULONG
        if (~(tmp = *(p++)))
            goto found_middle;
        result += BITS_PER_LONG;
        size -= BITS_PER_LONG;
    }
    if (!size) // 当size正好是整数个ULONG时，如果没找着，返回值就是原始的size，若不是，会依次进found_first，然后found_middle
        return result;
    tmp = *p;

found_first:
    tmp |= ~0UL << size; // 将size以上部分全部置1

    if (tmp == ~0UL)    // offset~size或head~size之间没有0
        return result + size;   // 返回值即为传入的size
found_middle:
    return result + ffz(tmp); // ffz就是寻找unsigned long变量的第一个0位索引的宏
}

bootmem工作原理

Posted on 2012-11-06 Edited on 2018-09-08

if (test_bit(i, bdata->node_bootmem_map)) { // 如果连续空间不足，则返回重新搜索未分配区

sidx = align_idx(bdata, i, step);

if (sidx == i)

sidx += step;

goto find_block;

}

if (bdata->last_end_off & (PAGE_SIZE - 1) && // 上一次分配的空间末地址在页边界

PFN_DOWN(bdata->last_end_off) + 1 == sidx)

start_off = align_off(bdata, bdata->last_end_off, align); // align = 64，将start_off提升到last_end_off附近，要按align向下对齐

else

1.初始化

1)arm_bootmem_init

有一点，先理清楚，Linux支持NUMA架构的内存管理，但NUMA一般应用于中大型系统，来灵活处理本地内存与远端内存，以提高平均内存读写速度，即优先使用本地内存或者访问速度较快的内存。但嵌入式设备或者我们的D7800并没有使用Linux的NUMA架构来管理内存。换句话说，就是我们的系统只有node 0，即其上只有本地内存。

上图中bdata_list在NUMA架构中包含了所有node的内存地址，但在我们的系统中，该list上只有node 0的：min~max_low低端内存地址空间。再看memblock，具体参考memblock工作原理，其中memblock.memory表格中，包含了meminfo中所有bank的物理地址区间。对应到一张图上，就如上图左半部分的示意图所示，bdata_list上node 0的min~max_low区段上，有着nrbanks个region_start~region_end内存区间。

于是，对应到代码里就很好理解了。在函数mark_bootmem中，遍历bdata_list列表，判断区段是否符合的条件如下。

if (pos < bdata->node_min_pfn ||

pos >= bdata->node_low_pfn) { // 表示超过了此node对应的区段，

BUG_ON(pos != start);

continue;

}

……

if (max == end) // end会不会超过max_low，即end是高端地址？我的理解，end可以超过low mem的限制，不过在bootmem中我们只考虑low mem的部分

return 0;

pos = bdata->node_low_pfn; // 运行到这里，表示start~end的region已经处理过了，只是max!=end，之后会空跑完剩下的循环

总体来说所谓的bootmem，即是为meminfo中所有nrbanks内存的min~maxlow，来分配一张bitmap，每一位代表一个page是否分配。他和memblock两套不同的机制。bootmem的bitmap被memblock管理，memblock变量，以及memblock的两张表格memblock_memory_init_regions和memblock_reserved_init_regions，都是存在.init.data section中，即在kernel image里。

2)arm_bootmem_free

其中本node内存指标示意图如下：

alloc_node_mem_map在后面的章节讨论。

还有一点需要补充一下，pgdat一般指向NODE_DATA(i)，即node_data[i]成员。对于我们的系统，只考虑node 0，所以pgdat可以简单的看成是指向node 0的数据。在init_bootmem_node中，我们对该node的bootmem部分加以初始化。其他部分在其他部分初始化。

3)free_area_init_core

a) 每个zone的page按照page block组织，每个page block包含MAX_ORDER-1 = 10，即1024页

b) 代码中几个指标备注如下：

size: 第j个zone的total_size，单位page

memmap_pages: 本zone的memmap数组需要的page数

realsize: totalsize - zhole_size[j] - memmap_pages - dma_reserve(如果是zone[0])

nr_kernel_pages += realsize; // 如果是HIGHMEM zone，更新nr_kernel_pages

nr_all_pages += realsize;

c) init_currently_empty_zone, memmap_init在后面章节讨论

4) memmap_init

memmap数组在arm_bootmem_free->free_area_init_node中通过alloc_node_mem_map-> alloc_bootmem_node来分配一段bootmem内存，并赋给pgdat->node_mem_map。memmap_init函数负责初始化这块区域（数组）中的每个成员。

a)关于SetPageReserved，在这里不知何用。

内核中申请到页面之后，要调用一下SetPageReserved，相当于告诉系统，这个页面我已经占了。对于每一个申请到的页面，应该都要这样做。

b)为每个页面设置miagrate type是为了防止外部碎片，其中的机制也略有些复杂

c)lru list是为了回收机制设计的，全称是Least Recently Used

d)关于struct page，具体可以参考Mel Gorman的《Understanding the Linux® Virtual Memory Manager》的P41：Pages一节。

5) alloc_bootmem_node

alloc_bootmem_node -> __alloc_bootmem_node -> ___alloc_bootmem_node -> alloc_arch_preferred_bootmem / alloc_bootmem_core / ___alloc_bootmem

最后落实到三个函数alloc_arch_preferred_bootmem / alloc_bootmem_core / ___alloc_bootmem。

alloc_arch_preferred_bootmem 和___alloc_bootmem在未定义CONFIG_NO_BOOTMEM时，最终调用的都是alloc_bootmem_core 。所以alloc_bootmem_core 是核心函数。

那么来看alloc_bootmem_core。

这其中有很多个指标，大体总结如下：

sidx / midx: start - bdata->node_min_pfn / max - bdata->node_min_pfn // 这两个变量也会有一些处理，但大体上可以认为是本node低端内存的首末地址页索引。

eidx: sidx + PFN_UP(size) // 需要分配空间末地址按页向下（增长方向）对齐后的页索引

start_off / end_off: 分配空间始末地址的物理地址

merge: PFN_DOWN(start_off) < sidx // 此时start_off是经过处理的，因为前次分配的末地址（last_end_off）所在页还有空闲，则将start_off向上提升到该页，并与last_end_off隔开一定的距离

bdata->last_end_off: 记录上一次分配末地址的物理地址，并不按页对齐，此变量只在alloc_bootmem_core中更新

bdata->hint_idx: 在alloc_bootmem_core中= PFN_UP(end_off)，在__free的时候= sidx，记录的是可分配地址的最小值的页索引

了解这些指标之后，对code就比较容易理解了。摘录如下

static void * __init alloc_bootmem_core (……) {

……

find_block:

sidx = find_next_zero_bit(bdata->node_bootmem_map, midx, sidx); // find_next_zero_bit参考另一篇笔记find_next_zero_bit

sidx = align_idx(bdata, sidx, step);

eidx = sidx + PFN_UP(size);

if (sidx >= midx || eidx > midx) // sidx > midx和eidx > midx比较好理解

break; // sidx = midx的情况指的是find_next_zero_bit返回的是midx，根据find_next_zero_bit这篇笔记可知，这种情况是find_next_zero_bit失败，没有找到未分配页

for (i = sidx; i < eidx; i++)

start_off = PFN_PHYS(sidx);

merge = PFN_DOWN(start_off) < sidx; // 表示本次分配与上次分配有交叠，参看图1

……

/*

* Reserve the area now:

*/

if (__reserve(bdata, PFN_DOWN(start_off) + merge, // merge =0: 没有交叠，正常分配，merge =1：和上次有交叠，但有交叠的页已经reserve过了，所以从下一页开始reserve

PFN_UP(end_off), BOOTMEM_EXCLUSIVE))

……

}

alloc_bootmem_core中还有个fall_back机制，具体如下：

static void * __init alloc_bootmem_core (……) {

……

if (bdata->hint_idx > sidx) { // hint_idx是可分配空间的最小值，这个条件表示搜索起始点可以向前提升

/*

* Handle the valid case of sidx being zero and still

* catch the fallback below.

*/

fallback = sidx + 1; // 记录fall_back值

sidx = align_idx(bdata, bdata->hint_idx, step); // 将sidx提升到hint_idx附近

}

while(1) {

find_block:

……

}

if (fallback) { // 如果搜索失败，则将sidx还原再重新搜索

sidx = align_idx(bdata, fallback - 1, step);

fallback = 0;

goto find_block;

}

return NULL;

}

6) init_currently_empty_zone

本函数主要是为了初始化zone结构，更明确的就是：（1）wait queue table初始化，（2）free_area初始化

调用顺序如下

zone_wait_table_init -> zone_init_free_lists(zone)

a) zone_wait_table_init

此函数初始化了zone->wait_table，这是一张哈希表，有zone->wait_table_hash_nr_entries个表项（最少4，最多4096）。wait_table相关内容可参考可以参考Mel Gorman的《Understanding the Linux® Virtual Memory Manager》P40：Zone Wait Queue Table一节。内存页的wait-wake机制请参考笔记内存页的wait-wake机制。

本函数调用流程为：

wait_table_hash_nr_entries(zone_size_pages) -> wait_table_bits(zone->wait_table_hash_nr_entries) -> alloc_bootmem_node(pgdat, alloc_size) -> 遍历所有哈希项，并初始化init_waitqueue_head(zone->wait_table + i)

b）zone_init_free_lists

牵涉到migrate type，尚不清楚其中的机制，会用新篇来作介绍

arm架构，函数调用过程

Posted on 2012-11-01

注意：R11=fp;R12=ip;R13=SP；R14=LR；R15=PC；R0,R1,R2用于传递参数和存放函数返回值。
注意；低地址的寄存器被压入低地址内存中，也就是说如果向下增长，高地址寄存器先压，向上增长测试低地址先压。
注意：根据“ARM-thumb 过程调用标准”：
1， r0-r3 用作传入函数参数，传出函数返回值。在子程序调用之间，可以将 r0-r3 用于任何用途。被调用函数在返回之前不必恢复 r0-r3。---如果调用函数需要再次使用 r0-r3 的内容，则它必须保留这些内容。
2， r4-r11 被用来存放函数的局部变量。如果被调用函数使用了这些寄存器，它在返回之前必须恢复这些寄存器的值。
3， r12 是内部调用暂时寄存器 ip。它在过程链接胶合代码（例如，交互操作胶合代码）中用于此角色。在过程调用之间，可以将它用于任何用途。被调用函数在返回之前不必恢复 r12。

4，寄存器 r13 是栈指针 sp。它不能用于任何其它用途。sp 中存放的值在退出被调用函数时必须与进入时的值相同。
5，寄存器 r14 是链接寄存器 lr。如果您保存了返回地址，则可以在调用之间将 r14 用于其它用途，程序返回时要恢复

6，寄存器 r15 是程序计数器 PC。它不能用于任何其它用途。

7，在中断程序中，所有的寄存器都必须保护，编译器会自动保护R4～R11，所以一般你自己只要在程序的开头
sub lr,lr,#4
stmfd sp!,{r0-r3,r12,lr}；保护R0～R3，R12,LR就可以了，除非你用汇编人为的去改变R4~R11的值。（具体去看UCOS os_cpu_a.S中的IRQ中断的代码）

1.函数调用前，调用函数需要保护现场，即r0-r3，因为被调用函数不会帮助保存这一部分，之后，需要把参数传入r0-r3，如果超过4个参数则开辟栈空间，将参数压栈

2.三个重要参数需要压栈，fp，lr，ip，即r11-r13，fp是调用函数保存现场的底部，lr是返回地址，ip是调用函数的栈底指针

3.在函数退出时，lr会被加载到pc，ip加载到sp，此时跳转回调用函数，然后拷贝出r0-r3中的返回值，并开始恢复现场。

CPU调度

Posted on 2012-10-10 Edited on 2018-09-06

1.评价准则

CPU使用率：<40% 轻负荷，>90% 重负荷
吞吐量：一个时间单元内处理进程的数量
周转时间：进程提交到完成的时间，包含了等待和处理时间。
等待时间
响应时间：从提交到第一次响应之间的时间间隔

2.算法

1）先到先服务（FCFS）

最普通的一种调度方法。它是非抢占的，而且往往不是最优算法。因为它的等待时间依赖于处理任务的顺序。

2）最短作业优先（SJF）

SJF算法被证明为是最佳算法，因为其等待时间最短。但其实现难度是无法预料下一个任务的处理时间。现在比较常用的做法是，采用估计算法来预测下一个处理时间。所以往往时间越久，预测越准确，所以SJF调度经常用于长期调度。

可抢占式的SJF算法，被称作最短剩余时间优先调度。

3）优先权调度

SJF是一种特殊的优先权调度算法。这个算法有个问题，即无穷阻塞，又叫饥饿。因为如果一直有高优先级任务来抢占资源，则有可能有一些低优先级任务永远得不到操作。饥饿的解决方案是老化，即随着时间的推移，增大一些低优先级任务的优先级。

4）轮转法（RR，round-robin）

这是将CPU处理时间分成许多小的时间片，每个任务轮流获得CPU时间。这是专门为分时系统设计的，每个任务都会得到处理时间。但每次切换任务都会又一次上下文切换，这个会消耗一定的资源。

5）多级队列调度

这是指将所有任务分成若干个处理队列，每个队列可采用不同的调度算法，然后队列之间可采用固定优先权可抢占调度，或者采用round-robin调度，即所有队列分享时间片。

6）多级反馈队列调度

这是当下最通用的CPU调度算法。这是加强版的多级队列调度。任务可以在队列之间移动。需要长时间操作的任务，会被转移到低优先级队列；等待时间过长的任务，会被转移到高优先级队列。

这种调度算法可由下列参数定义：

队列数量
每个队列的调度算法
任务升级到高优先级队列的条件
任务降级到低优先级队列的条件
某个任务初始时该进入哪个队列

3.Linux调度算法

Linux assigns higher-priority tasks longer time quanta and lower-priority tasks shorter time quanta. The relationship between priorities and time-slice length is shown in Figure 5.15.

Each runqueue contains two priority arrays: active and expired.The active array contains all tasks with time remaining in their time slices, and the expired array contains all expired tasks.

Each of these priority arrays contains a list of tasks indexed according to priority (Figure 5.16). The scheduler chooses the task with the highest priority from the active array for execution on the CPU.

When all tasks have exhausted their time slices (that is, the active array is empty), the two priority arrays are exchanged: the expired array becomes the active array, and vice versa.

Real-time tasks are assigned static priorities. All other tasks have dynamic priorities that are based on their nice values plus or minus the value 5. 这个要看任务的等待时间，等太久了就要减5以提高优先级，否则要加5降低优先级。

A task’s dynamic priority is recalculated when the task has exhausted its time quantum and is to be moved to the expired array. Thus, when the two arrays are exchanged, all tasks in the new active array have been assigned new priorities and corresponding time slices.