Big Ben

一个半吊子的编码爱好者

0%

Posted on Edited on
哈希搜索是典型的以空间换时间的算法，不论其建立哈希表时间，还是搜索时间均小于优质算法：快速排序和二分搜索。在数组尺寸为1万，哈希参数为1000（哈希函数是val%HASH_ARG）时，其时间参数为

qsort takes: 1755060 ns (1.75 ms)
build hash table takes: 1181122 ns (1.18 ms)

Array size: 10000, Value range: 10000
average search time:
binary search: 166 ns
hash search: 48 ns


其排序时间减少30%，单次搜索时间减少70%。性能提升很多。缺点是由于引入hash_node结构，1万个整数，大小为4Bx1w，需要扩展出16Bx1w，空间使用提升了4倍。另有空间提升两倍的算法（参考散列法解决1000个整数的搜索 - cqnuztq的专栏 - 博客频道 - CSDN.NET）

当数组尺寸进一步上升（10w），而值域不变时，时间参数为

qsort takes: 25675050 ns (25.67 ms)
build hash table takes: 47017148 ns (47.02 ms)

Array size: 100000, Value range: 10000
average search time:
        binary search: 220 ns
        hash search: 276 ns

此时哈希搜索已经在排序和搜索上，全面落后了。究其原因是什么？因为此时数组尺寸上升，但哈希函数和哈希参数并没变，所以哈希冲突数大大上升。考虑冲突的概率相同，所以每个哈希索引下的冲突数约为（ARRAY_SIZE / HASH_ARG），以上面的取值为例，则冲突数为100，即其时间复杂度为100，而二分搜索的复杂度为logn = 16.6，已经远小于哈希搜索的复杂度了。

综上，哈希搜索适用于属性值范围远小于数组个数的情况，下面的笔记中有使用哈希搜索的一个例子，比较好的阐述了这个特性（从大量整数中选取最小/大的若干个 « GoCalf Blog）。但数组范围不能过大，导致冲突数上升过快。或者说为了提高哈希搜索的效率，最好能找到一个能消除冲突的哈希函数。

下面附上源码

// Hash search
// Ben @ 2013-04-29

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct hash_node
{
     int inited;
     int key;
     int pos;
     struct hash_node* next;
};

#define HASH_ARG     1000
static struct hash_node hash_table[HASH_ARG];

void build_hash_table(int* L, int size)
{
     memset ((char*)hash_table, 0, sizeof(hash_table));

     int i;
     for (i=0; i<size; i++)
     {
          int index = hash(L[i]);

          if (hash_table[index].inited == 1)
          {
               struct hash_node* n = &hash_table[index];
               while (n->next != NULL)
                    n = n->next;
               n->next = (struct hash_node*)malloc(sizeof(struct hash_node));
               n->next->inited = 1;
               n->next->key = L[i];
               n->next->pos = i;
               n->next->next = NULL;
          }
          else
          {
               hash_table[index].inited = 1;
               hash_table[index].key = L[i];
               hash_table[index].pos = i;
          }
     }
}

void destroy_hash_table()
{
     int i;
     for(i=0; i<HASH_ARG; i++)
     {
          struct hash_node* n = hash_table[i].next;

          while (n != NULL)
          {
               struct hash_node* tmp = n->next;
               free(n);
               n = tmp;
          }
     }
}

int hash(int val)
{
     return val%HASH_ARG;
}

int hsearch(int t, int* L, int size)
{
     int index = hash(t);
     struct hash_node* i = &hash_table[index];
     while (i != NULL)
     {
          if (t == i->key)
               break;
          else
               i = i->next;
     }

     if (i ==  NULL)
          return -1;
     else
          return i->pos;
}

Posted on Edited on
有几点记录一下：
1.快速排序的时间复杂度是nlogn，推到《数据结构》上有，看不懂。在记录为有序时，快速排序退化成冒泡排序。
2.注意是low跟high记录交换，而并非跟枢轴记录交换。前者才能保证low，high两部分的基本有序。只不过要注意，low，high记录交换后，low记录本身存在偶然性，即其跟枢轴记录的相对大小不确定。需要比较，然后做出交换动作，才能保证前后两个分支的基本有序，如下面绿色注释部分所指出的。


================2013/5/2更新===========================

Programming Pearls第11章，着重介绍了快速排序，其讲解的深度和算法的优美度都远大于严蔚敏的《数据结构》第十章所介绍的。挑一种比较基本的快速排序实现如下，并做一些笔记

// 解决了原先swap相同变量的问题
#define swap(a, b) \
     if (a!=b)\
     {\
          a = (a)+(b);\
          b = (a)-(b);\
          a = (a)-(b);\
     }

void qsort(int* L, int size)
{
          // 确保递归循环能结束，而非死循环
     if (size <= 1)
          return;

          // i,j可以理解为从两侧开始扫描，
          // while循环的目的是为了将数组转变为如下图
          // i变量为了找比t大的数，j变量为了找比t小的数
     int t = L[0];
     int i = 0, j = size; 
     while (1)
     {
          do
          {
               i ++;
          } while (i<size && L[i]<t);
                    // 此时i有两种可能：
          // 1）i==u, 2）x[i]>=t
          do
          {
               j --;
          } while (L[j]>t);
                    // 此时j只有一种可能：x[j]<=t
                    // 当i,j交叉时，说明整个数组扫描完毕
          if (i>j)
               break;
          swap (L[i], L[j]);
     }
     swap(L[0], L[j]);
     qsort(L, j);
     qsort(&L[j+1], size-1-j);
}

整个算法的关键是在那个while(1)循环，如何保证此循环可以正确的结束。
要保证正确，要保证以下三点：
     1. 循环结束后，j点左侧的都要小于t，j点右侧都要大于t
     2. 循环不变式是i <= j
     3. 保证在交换时，i、j没有交叉

============================================================
#include <stdio.h>
#include <time.h>

// 注意：不加{}，会影响到if分支
#define swap(a, b) \
{\
     a = (a)+(b);\
     b = (a)-(b);\
     a = (a)-(b);\
}
#define dim(a) (sizeof(a)/sizeof(a[0]))

void qsort(int* L, int size);

main()
{
     int i;
     int a[10] = {0};
     srand(time(NULL));
     for (i=0; i<dim(a); i++)
     {
          a[i] = rand() % 100;
     }
     qsort(a, dim(a));

     printf("a: ");
     for (i=0; i<dim(a); i++)
     {
          printf("%d ", a[i]);
     }
     printf("\n");
}

void qsort(int* L, int size)
{
     switch (size)
     {
          case 0:
               printf ("empty array is input.\n");
               return;
          case 1:
               printf ("input array has only 1 member.\n");
               return;
          case 2:
               if (L[0] > L[1])
               {
                    swap(L[0], L[1]);
               }
               return;
          default:
               break;
     }
    
     int low = 1, high = size - 1;
     while(low < high)
     {
          while (low<high && L[low] <= L[0])
          {
               low ++;
          }
          if (low != high)
               swap(L[low], L[high]);
          while (low<high && L[high] >= L[0])
          {
               high --;
          }
          if (low != high)
               swap(L[low], L[high]);
     }

         //////////////////////
     // 注意：这里low的位置存在随机性，《数据结构》中并没有注意到这点
     if (L[0] > L[low])
          swap(L[0], L[low])
     else if (L[0] < L[low])
     {
          low --;
          if (low != 0)
               swap(L[0], L[low])
     }
         //////////////////////

     qsort(L, low);
     if (low < size-1)
          qsort(&L[low+1], size-low-1);
}

Posted on Edited on
1.什么时候会用到swap？
     1）换出
     当内核在分配内存时，调用__alloc_pages，如果没有空闲页，内核会启动页面交换机制，也就是try_to_free_pages。代码如下：
1293    page = get_page_from_freelist(gfp_mask, order,
1294                 zonelist, ALLOC_NO_WATERMARKS);
1295             if (page)
1296                 goto got_pg;

1306    if (!w ait)
1307         goto nopage;

1316
1317     did_some_progress = try_to_free_pages(zonelist->zones, gfp_mask);

     可以看到，如果分配者允许等待，则会开始回收页面。再往下的调用关系如下：
          try_to_free_pages->shrink_zones->shrink_zone->shrink_inactive_list->add_to_swap->pageout->(swapper_space.a_ops->writepage)
     最终调用块设备接口，将page写到磁盘交换分区的swap file上。
     2）换入
     当引发缺页异常时，内核调用handle_pte_fault，当检测到
          !pte_present(entry) <=> (pte_val(pte) & L_PTE_PRESENT == 0)
     此时会调用do_swap_page->read_swap_cache_async->swap_readpage来读入换出的页数据到新的一页，原先的页面会释放成hot page到伙伴系统。

2.swap的工作原理
     swap就是交换，每次需要交换哪些，和linux的页回收机制也就是著名的LRU算法，有些相似。彼是决定要回收哪些。之前我们也提到过LRU这个名词。现在可以知道他到底是一个什么样的算法了。LRU = Least Recently Used，可以参考LRU算法。
     对于交换算法，我们对页面的新旧程度不需要弄的那么清楚，我们只需要知道有两个list：active_list & inactive_list。每次try_to_free_pages在交换时，将active page放一部分到inactive list，再将inactive page释放一部分到磁盘上。其核心函数就是上面提到的shrink_zone。
     1）首先来看try_to_free_pages
          for (priority = DEF_PRIORITY; priority >= 0; priority--) {
               ……
               nr_reclaimed += shrink_zones(priority, zones, &sc);
               shrink_slab(sc.nr_scanned, gfp_mask, lru_pages);
               ……
          }
     这里有一个priority的机制。这里其实并没有什么优先级机制，只是每次尽量少的扫描页面，以保证速率。到shrink_zone里面有：
          zone->nr_scan_active +=
               (zone_page_state(zone, NR_ACTIVE) >> priority) + 1;
     这一段我一度看了好久，其实不要考虑的那么死。他只是一个一步步增加扫描页面的数量的方法。当priority = 12~1的时候，扫描数量每次增加zone->nr_active/(2^priority)个页面。如果到priority =1的时候，nr_scan_active仍然没达到sc->swap_cluster_max（32）的话，即scan的总数的理论值为zone->nr_active*(1-1/(2^12))，则priority=0，此时scan总数将超过zone->nr_active的总数。那是不是就有问题了呢？当然不是，因为后面再做页面转移的时候，检测标准是list_empty，不会操作超过列表范围的页面的。

     2）shrink_zone
            /* 根据priority来决定扫描页面的数量，inactive的数量采用同样的方式获得
       * 至少要保证sc->swap_cluster_max个页面，即32个页面
       */
918     zone->nr_scan_active +=
919         (zone_page_state(zone, NR_ACTIVE) >> priority) + 1;
920     nr_active = zone->nr_scan_active;
921     if (nr_active >= sc->swap_cluster_max)
922         zone->nr_scan_active = 0;
923     else
924         nr_active = 0;
925
               ……
933          // nr_active: 从active转到inactive列表上的页面数
                // nr_inactive: 从inactive列表换出到磁盘的页面数
934     while (nr_active || nr_inactive) {
935         if (nr_active) {
936             nr_to_scan = min(nr_active,
937                     (unsigned long)sc->swap_cluster_max);
938             nr_active -= nr_to_scan;
939             shrink_active_list(nr_to_scan, zone, sc, priority);
940         }
941
942         if (nr_inactive) {
943             nr_to_scan = min(nr_inactive,
944                     (unsigned long)sc->swap_cluster_max);
945             nr_inactive -= nr_to_scan;
946             nr_reclaimed += shrink_inactive_list(nr_to_scan, zone,
947                                 sc);
948         }
949     }

     3）shrink_inactive_list
     经过上面的分析，其实已经可以看出，shrink_inactive_list要做的工作就是，扫描传入的nr_to_scan页面，再将合适的页面换出到磁盘，并返回换出的页面数。其流程如下：
     是不是很简单，没错，就是这么简单。isolate_lru_pages负责扫描页面的struct page结构，根据其flags来决定是否可以换出，可以换出的放到输出列表上，以备shrink_page_list来做真正的换出。

     4）shrink_page_list
     其主线如下：
     
     经过一系列的判断后，将页面换出，并且用__pagevec_release_nonlru(&freed_pvec)将页面释放回buddy system，注意在创建freed_pvec时，指定了页面的属性为cold。整个算法的精髓，在于哪些inactive的页面不可以换出。
     先看，shrink_page_list中有几个标号
keep：直接将页面add回page_list
keep_locked：指该页面已经被lock了，需要先解锁再进入keep标号
activate_locked：将页面激活，再放回page_list，这个在后续，该页面会被放入active list
free_it：这个是正常流程，页面会被释放，然后进入扫描下一个页面
     所以代码中，凡是经过判断后，要调转到以上前三个标号的地方，那些页面都是不会被换出释放的。具体来说，有以下这些情况：
     a. !sc->may_swap && page_mapped(page)
     b. PageWriteback(page)
     c. PageDirty(page) && page_referenced(page, 1)
     d. PageDirty(page) && !may_enter_fs
     e. PageDirty(page) && !sc->may_writepage
     代码中多个函数调用涉及到page->mapping成员，例如page_mapping, page_mapped。简单介绍一下这个成员，其取值有以下三种情况。也可以参考这个链接Linux内存管理中address_space疑惑及解答 
（1）swapper_space：
          如果page->mapping等于0，说明该页属于交换告诉缓存swap cache
（2）anon_vma： 
          如果page->mapping不等于0，但第0位为0，说明该页为匿名也，此时mapping指向一个struct anon_vma结构变量；
（3）address_space：
          如果page->mapping不等于0，但第0位不为0，则mapping指向一个struct address_space地址空间结构变量；

     5）swap cache
     上面简述了linux页缓冲交换机制的工作原理，最后回到swap cache这一基本结构上来。gorman的书里面讲得很清楚了。下面做一些笔记。
     
     为什么要有swap cache这个东西？
     因为A significant number of the pages referenced by a process early in its life may only be used for initialization and then never used again. It is better to swap out those pages and create more disk
buffers than leave them resident and unused.

     swap cache vs. page cache
     The swap cache is purely conceptual because it is simply a specialization of the page cache.
          1. in the swap cache rather than the page cache is that pages in the swap cache always use swapper space as their address space in page→mapping.
          2. pages are added to the swap cache with add_to_swap_cache(),shown in Figure 11.3, instead of add_to_page_cache().

     所有的swap file信息都保存在这个数组中
     static struct swap_info_struct swap_info[MAX_SWAPFILES];
     可见swap file最多可以有MAX_SWAPFILES个，也就是32个。
64 struct swap_info_struct {
65      unsigned int flags;
66      kdev_t swap_device;
67      spinlock_t sdev_lock;
68      struct dentry * swap_file;
69      struct vfsmount *swap_vfsmnt;
70      unsigned short * swap_map;
71      unsigned int lowest_bit;
72      unsigned int highest_bit;
73      unsigned int cluster_next;
74      unsigned int cluster_nr;
75      int prio;
76      int pages;
77      unsigned long max;
78      int next;
79 };
     swap_info是一个数组，也是一个虚拟链表，每个成员用next指向了下一个链表成员的索引号。这个链表同时用另一个变量描述。这里指明了这个链表的头在哪里，其表尾成员的next = -1。
153 struct swap_list_t {
154     int head; /* head of priority-ordered swapfile list */
155     int next; /* swapfile to be used next */
156 };
     swap area由swap_info_struct描述，并且可以通过命令动态的增加。每一个swap area指向一个swap file，该file被分割成若干个page size的slot，第0个slot被用来存储swap_header，如下：
25 union swap_header {
26      struct
27      {
28           char reserved[PAGE_SIZE - 10];
29           char magic[10];
30      } magic;
31      struct
32      {
33           char bootbits[1024];
34           unsigned int version;
35           unsigned int last_page;
36           unsigned int nr_badpages;
37           unsigned int padding[125];
38           unsigned int badpages[1];
39      } info;
40 };
     添加padding是为了能和磁盘的cluster对齐，badpages数组限制了一个swap area的页数，其尺寸由下面的公式得到。每个成员指向了一个page结构体。
               
     swap cache最核心的部分，是一个叫做swp_entry_t的结构，其实他就是一个unsigned long。当页面被换出时，其原先的页表项pte被用于存储这个值。通过这个swp_entry_t，我们可以定位到该页数据被写到哪个swap area的哪个位置。其组成如下图所示：
     Type指引了哪个swap area，offset指引了该页在swap_map数组中的位置，也可以通过改offset算得swap file中的sector位置。具体可以参考下面的函数
     (swapper_space.a_ops->swap_writepage) -> get_swap_bio -> map_swap_page

938     for ( ; ; ) {
939         struct list_head *lh;
940                  /*一直循环到offset落在该sector中*/
941         if (se->start_page <= offset &&
942                 offset < (se->start_page + se->nr_pages)) {
943             return se->start_block + (offset - se->start_page);
944         }
945         lh = se->list.next;
946         if (lh == &sis->extent_list)
947             lh = lh->next;
948         se = list_entry(lh, struct swap_extent, list);
949         sis->curr_swap_extent = se;
951     }

     那么这个swap_entry_t是怎么来的？其实也很简单，就是在swap_map数组中挨个找，first fit法。当然具体还有些技巧，其实在搜索时，是按照cluster的范围寻找，也就是循环直到找到一个空的cluster（256个等于0的swap_map成员）为止，目的是to have pages swapped out at the same time close together on the premise that pages swapped out together are related 。


Posted on Edited on
          这个函数是slab系统的核心函数之一，他是kmalloc的后盾，也可以直接作为分配内存的接口，供驱动调用。具体可以参看ldd3的chp 8的后备高速缓存一节（P217）。他其实和我们CPU的L1，L2缓存并没有什么关系。他有点类似于内存池，可以从中分配若干个size相同的内存块使用。

          其调用流程主线如下：
          
          主线还是很清楚的，就是通过kmem_cache_zalloc分配kmem_cache，然后各种初始化，最后加入cache_chain中。之前不清楚的一个问题——cache_chain是做什么用的，现在看起来应该是有答案了。他的作用就是保存已分配的kmem_cache记录，防止重名的cache产生，方便proc系统显示调试信息。
          整个流程中有几个值得关注的地方

1. kmem_cache的初始化
     1）当size >= (PAGE_SIZE >> 3 = 512KB时，flags |= CFLGS_OFF_SLAB
     2）calculate_slab_order(cachep, size, align, flags)
          
          所谓的num与offslab_limit就是下面off-slab这种情况下，由整块2^order个页面决定的object数(num)，和右边kmem_bufctl_t数组决定的object数(offslab_limit)。可见有一个约束就是，num要小于offslab_limit，也就是左边小于右边。很好理解，因为右边是左边的管控。
          3）如果left_over太多，足够放得下slab_size，会将off-slab转变为on-slab
2. off-slab时，slab mngmt放在哪
          调用cachep->slabp_cache = kmem_find_general_cachep(slab_size, 0u)，去寻找这个size cache来存放slab mngmt。
               kmem_find_general_cachep -> __find_general_cachep -> (return malloc_sizes[n]->cs_cachep)

3. CPU cache的初始化
          setup_cpu_cache(cachep, gfp)
          这是一个很复杂的函数，先看调用流程

          
          整个过程根据g_cpucache_up分成三个部分
          1）FULL状态，此时，所有的cache初始化都完成了，setup_cpu_cache要做的就是enable_cpucache。这也是一个很复杂的函数，再另开新篇介绍
          2）PARTIAL_AC/L3状态，此时调用此函数的kmem_cache_create仍在kmem_cache_init中，初始化才刚开始，需要先对struct arracy_cache和kmem_list3s用到的内存进行初始化，否则其他cache在初始化时，无法动态地为这两个结构体分配内存
          3）剩下的就是，AC和L3都分配好了，其他的cache再create就可以正常的调用kmalloc了

          INDEX_AC的array_cache初始化是initarray_generic.cache
          INDEX_AC / L3的kmem_list3初始化是initkmem_list3[SIZE_AC / L3]
          cache_cache的array_cache初始化是initarray_cache，kmem_list3初始化是initkmem_list3[CACHE_CACHE]
          这些在kmem_cache_init的step 4,5都会被重新用kmalloc进行动态分配，并且array_cache会用memcpy将原先值赋入，list会用splice进行合并。
          

Posted on Edited on
          这个函数是slab系统的核心函数之一，他是kmalloc的后盾，也可以直接作为分配内存的接口，供驱动调用。具体可以参看ldd3的chp 8的后备高速缓存一节（P217）。他其实和我们CPU的L1，L2缓存并没有什么关系。他有点类似于内存池，可以从中分配若干个size相同的内存块使用。

          其调用流程主线如下：
          
          主线还是很清楚的，就是通过kmem_cache_zalloc分配kmem_cache，然后各种初始化，最后加入cache_chain中。之前不清楚的一个问题——cache_chain是做什么用的，现在看起来应该是有答案了。他的作用就是保存已分配的kmem_cache记录，防止重名的cache产生，方便proc系统显示调试信息。
          整个流程中有几个值得关注的地方

1. kmem_cache的初始化
     1）当size >= (PAGE_SIZE >> 3 = 512KB时，flags |= CFLGS_OFF_SLAB
     2）calculate_slab_order(cachep, size, align, flags)
          
          所谓的num与offslab_limit就是下面off-slab这种情况下，由整块2^order个页面决定的object数(num)，和右边kmem_bufctl_t数组决定的object数(offslab_limit)。可见有一个约束就是，num要小于offslab_limit，也就是左边小于右边。很好理解，因为右边是左边的管控。
          3）如果left_over太多，足够放得下slab_size，会将off-slab转变为on-slab
2. off-slab时，slab mngmt放在哪
          调用cachep->slabp_cache = kmem_find_general_cachep(slab_size, 0u)，去寻找这个size cache来存放slab mngmt。
               kmem_find_general_cachep -> __find_general_cachep -> (return malloc_sizes[n]->cs_cachep)

3. CPU cache的初始化
          setup_cpu_cache(cachep, gfp)
          这是一个很复杂的函数，先看调用流程

          
          整个过程根据g_cpucache_up分成三个部分
          1）FULL状态，此时，所有的cache初始化都完成了，setup_cpu_cache要做的就是enable_cpucache。这也是一个很复杂的函数，再另开新篇介绍
          2）PARTIAL_AC/L3状态，此时调用此函数的kmem_cache_create仍在kmem_cache_init中，初始化才刚开始，需要先对struct arracy_cache和kmem_list3s用到的内存进行初始化，否则其他cache在初始化时，无法动态地为这两个结构体分配内存
          3）剩下的就是，AC和L3都分配好了，其他的cache再create就可以正常的调用kmalloc了

          INDEX_AC的array_cache初始化是initarray_generic.cache
          INDEX_AC / L3的kmem_list3初始化是initkmem_list3[SIZE_AC / L3]
          cache_cache的array_cache初始化是initarray_cache，kmem_list3初始化是initkmem_list3[CACHE_CACHE]
          这些在kmem_cache_init的step 4,5都会被重新用kmalloc进行动态分配，并且array_cache会用memcpy将原先值赋入，list会用splice进行合并。
          

Posted on Edited on
array_cache也就是Gorman书中的per-CPU cache。书中提到，为什么要有这个数据结构，有两点原因：
     1）This way the hardware cache will be used for as long as possible on the same CPU.
     2）The second major benefit of this method is that spinlocks do not have to be held

先看下kmem_cache数据结构：
struct kmem_cache {
/* 1) per-cpu data, touched during every alloc/free */
     struct array_cache *array[NR_CPUS];
/* 2) Cache tunables. Protected by cache_chain_mutex */
     unsigned int batchcount;
     unsigned int limit;
     unsigned int shared;

     unsigned int buffer_size;
     u32 reciprocal_buffer_size;
     ……
}

     array_cache是kmem_cache的第一个成员，而且是针对每个CPU都有一个这样的结构与之对应，这也印证了上面Gorman提到的两点原因。在每个kmem_cache被创建的时候，都需要去初始化这个结构，具体来说就是：
     setup_cpu_cache -> enable_cpucache -> do_tune_cpucache
     具体流程如下：

可见do_tune_cpucache的作用就是分配这个array_cache，并付给对应的CPU的变量。这里不清楚为什么要所有的online CPU都要分配一遍，然后只取用一个当前CPU的值。那么怎么使用这个array_cache，会在讲分配的笔记中再做详细介绍。不过这里有个free_block函数，阅读这个函数，可以对array_cache的工作原理也有一个大体的了解。

     先看整个调用流程：

     array_cache数据结构正如上图中的代码所显示，除了touched不知道有什么用之外，其他几个变量的作用还是很清晰的，从名字也可以看得出来：
  • avail，当前还有几个空闲的位子可以分配
  • limit，自然就是分配的上限，之前也说过，在enable_cpucache中也有定义
  • batchcount，linux中一般，一次操作的数量都是用batch来表示，所以这里就是array_cache在增长或释放时，一次操作的object数
  • entry，就是array_cache的核心成员了，也就是我们的object数组
     这里面有一个问题不清楚，为什么free_block释放的是ccold->avail个object，avail不应该是本身就是free的object吗？
     经过阅读分配内存的代码，可以回答这个问题了，首先分配内存，都是从array_cache->entry数组中取object，返回给调用者，此时avail的object会被分配出去，avail变少。当avail为0时，系统调用某个函数，从kmem_cache中去取object，赋给array_cache，一次取batchcount个object，这时avail就会增加，而kmem_list3->free_objects就会减少相应的数目。而kmem_list3->free_objects会在cache_grow时递增cachep->num。

Posted on Edited on
array_cache也就是Gorman书中的per-CPU cache。书中提到，为什么要有这个数据结构，有两点原因：
     1）This way the hardware cache will be used for as long as possible on the same CPU.
     2）The second major benefit of this method is that spinlocks do not have to be held

先看下kmem_cache数据结构：
struct kmem_cache {
/* 1) per-cpu data, touched during every alloc/free */
     struct array_cache *array[NR_CPUS];
/* 2) Cache tunables. Protected by cache_chain_mutex */
     unsigned int batchcount;
     unsigned int limit;
     unsigned int shared;

     unsigned int buffer_size;
     u32 reciprocal_buffer_size;
     ……
}

     array_cache是kmem_cache的第一个成员，而且是针对每个CPU都有一个这样的结构与之对应，这也印证了上面Gorman提到的两点原因。在每个kmem_cache被创建的时候，都需要去初始化这个结构，具体来说就是：
     setup_cpu_cache -> enable_cpucache -> do_tune_cpucache
     具体流程如下：

可见do_tune_cpucache的作用就是分配这个array_cache，并付给对应的CPU的变量。这里不清楚为什么要所有的online CPU都要分配一遍，然后只取用一个当前CPU的值。那么怎么使用这个array_cache，会在讲分配的笔记中再做详细介绍。不过这里有个free_block函数，阅读这个函数，可以对array_cache的工作原理也有一个大体的了解。

     先看整个调用流程：

     array_cache数据结构正如上图中的代码所显示，除了touched不知道有什么用之外，其他几个变量的作用还是很清晰的，从名字也可以看得出来：
  • avail，当前还有几个空闲的位子可以分配
  • limit，自然就是分配的上限，之前也说过，在enable_cpucache中也有定义
  • batchcount，linux中一般，一次操作的数量都是用batch来表示，所以这里就是array_cache在增长或释放时，一次操作的object数
  • entry，就是array_cache的核心成员了，也就是我们的object数组
     这里面有一个问题不清楚，为什么free_block释放的是ccold->avail个object，avail不应该是本身就是free的object吗？
     经过阅读分配内存的代码，可以回答这个问题了，首先分配内存，都是从array_cache->entry数组中取object，返回给调用者，此时avail的object会被分配出去，avail变少。当avail为0时，系统调用某个函数，从kmem_cache中去取object，赋给array_cache，一次取batchcount个object，这时avail就会增加，而kmem_list3->free_objects就会减少相应的数目。而kmem_list3->free_objects会在cache_grow时递增cachep->num。

Posted on Edited on
前面提到过的buddy allocator通过用order列表来管理页面，从而达到减少外部碎片的效果。但是不可能每次分配都分配一页或者几页的内存，那样内存利用率太低，系统中将充满了内部碎片。所以，slab分配器也就应运而生了，其就是为了减少内部碎片而生的。具体为什么引入，以及slab的一些简介可以参考 Linux slab 分配器剖析， Fred's blog: 三月 2009。

     
     所谓的slab就是基于这么一张图的系统。简化之，其实就是一种基于后备高速缓存内存分配（参考ldd3，page247 ch 8）方式的内存管理系统。

     他的初始化由下图中的g_cpucache_up来标志，共有5个状态，按顺序依次迁移，在start_kernel -> mm_init -> kmem_cache_init中到达EARLY状态。此时slab_is_availabe()函数就返回真，也就是说此时slab系统已经就绪了。而最终的FULL状态是在kmem_cache_init_late中完成的。


上面这几个函数中可以看出，核心其实就是 kmem_cache_init。下面将重点介绍这个函数。
     这个函数很大，而且包含了很多知识点，具体可以参考《Understanding the Linux® Virtual Memory Manager》chapter 8。关于slab系统的内容很多，而且不是很好理解。先列举几个重要的数据结构。当然最核心的数据结构就是kmem_cache了，因为他巨大，所以就不在此列举了。

    1. kmem_list3
     struct kmem_list3 {
     struct list_head slabs_partial;     /* partial list first, better asm code */
     struct list_head slabs_full;
     struct list_head slabs_free;
     unsigned long free_objects;
     unsigned int free_limit;
     unsigned int colour_next;     /* Per-node cache coloring */
     spinlock_t list_lock;
     struct array_cache *shared;     /* shared per node */
     struct array_cache **alien;     /* on other nodes */
     unsigned long next_reap;     /* updated without locking */
     int free_touched;          /* updated without locking */
};
最重要的就是前3个参数，也就是我们在图1中提到的三个list：slab_full, slab_partial, slab_empty。

     2. array_cache
struct array_cache {
     unsigned int avail;
     unsigned int limit;
     unsigned int batchcount;
     unsigned int touched;
     spinlock_t lock;
     void *entry[];     /*
               * Must have this definition in here for the proper
               * alignment of array_cache. Also simplifies accessing
               * the entries.
               */
};
struct kmem_cache {
/* 1) per-cpu data, touched during every alloc/free */
     struct array_cache *array[NR_CPUS];
          ……
}
          array_cache是per CPU变量，具体可参考《Understanding the Linux® Virtual Memory Manager》chp 8.5: Per-CPU Object Cache。每一个cache，在create的时候，都会被分配一个array_cache（enable_cpucache）来提高性能。当然我们的总cache——cache_cache（从名字可以看出，它是cache的cache）也有一个这样的变量，在初始化时被填了一个__init_data initarray_cache.cache。之后在kmem_cache_init中再通过kmalloc来分配。arraycache与kmem_cache的关系大体如下图
     关于array_cache具体的内容会在另一篇笔记中作介绍slab allocator （3）—— arraycache。

     3. cache_sizes
     Gorman的书中将其称之为sizes cache。其实他就是一组定义了size的cache。在slab初始化的时候，我们会经常看到malloc_sizes这个数组，其定义如下：
struct cache_sizes malloc_sizes[] = {
#define CACHE(x) { .cs_size = (x) },
#include <linux/kmalloc_sizes.h>
     CACHE(ULONG_MAX)
#undef CACHE
};
struct cache_sizes {
     size_t               cs_size;
     struct kmem_cache     *cs_cachep;
#ifdef CONFIG_ZONE_DMA
     struct kmem_cache     *cs_dmacachep;
#endif
};
再看linux/kmalloc_sizes.h
#if (PAGE_SIZE == 4096)
     CACHE(32)
#endif
     CACHE(64)
#if L1_CACHE_BYTES < 64
     CACHE(96)
#endif
     CACHE(128)
#if L1_CACHE_BYTES < 128
     CACHE(192)
#endif
     CACHE(256)
     CACHE(512)
     CACHE(1024)
     CACHE(2048)
     CACHE(4096)
     CACHE(8192)
     CACHE(16384)
     CACHE(32768)
     CACHE(65536)
     CACHE(131072)
     ……
          稍加分析我们就可以知道在kmalloc_sizes.h中已经定义好了一组固定size的cache了，只是他们对应的两组cache列表（cs_cachep, cs_dmacachep）还没分配。之后在我们的kmem_cache_init中对INDEX_AC和INDEX_L3的初始化，都是在为这个数组的成员初始化。
INDEX_AC：sizeof(struct arraycache_init)对应的malloc_sizes中的索引。
INDEX_L3：sizeof(struct kmem_list3)对应的malloc_sizes中的索引。
          为什么要把这两个size单独提出来做初始化，我推测是因为在kmem_cache_create到时候需要频繁的分配arraycache_init和kmem_list3，而且对于kmem_cache来说也就这两个struct是需要动态分配的，所以需要先对这两个size的cache先做初始化，以便在初始化其他malloc_sizes数组成员的时候，可以使用这两个cache来为之分配arraycache_init和kmem_list3。

          说完这些数据结构了，再回头看看kmem_cache_init的流程。其实无非就是对cache_cache，malloc_sizes做初始化，下面还有几个值得关注的点。
     1. cache_chain
          在kmem_cache_init的一开始处，有
INIT_LIST_HEAD(&cache_chain);
list_add(&cache_cache.next, &cache_chain);
尚不知这个cache_chain是作何用的，先暂且列在这里

     2. cache_estimate
     1504     for (order = 0; order < MAX_ORDER; order++) {
1505         cache_estimate(order, cache_cache.buffer_size,
1506             cache_line_size(), 0, &left_over, &cache_cache.num);
1507         if (cache_cache.num)
1508             break;
1509     }
          这个函数作用其实很简单，就是决定：(1)cache_cache.buffer_size，也就是cache_cache的object size，以及可以存储多少个object (2)slab manager存储位置（on-slab/off-slab：看看flags是否包含CFLGS_OFF_SLAB）(3)利用slab上剩余的空间，初始化coloring机制。
          一个cache_cache的slab空间分割如下图：
          其中object的size如下：
          offsetof(struct kmem_cache, nodelists) + nr_node_ids * sizeof(struct kmem_list3 *);
          其实就是sizeof(kmem_cache)。可见cache_cache的slab要分配的就是kmem_cache。最后cache_cache->slab_size = slab_mgmt_size。
          coloring scheme的初始化为：
          cache_cache.colour_off = cache_line_size();
          cache_cache.colour = left_over / cache_cache.colour_off;
     
     3. init_list
          在kmem_cache_init的最后，有
1604         for_each_online_node(nid) {
1605             init_list(&cache_cache, &initkmem_list3[CACHE_CACHE + nid], nid);
1606
1607             init_list(malloc_sizes[INDEX_AC].cs_cachep,
1608                   &initkmem_list3[SIZE_AC + nid], nid);
1609
1610             if (INDEX_AC != INDEX_L3) {
1611                 init_list(malloc_sizes[INDEX_L3].cs_cachep,
1612                       &initkmem_list3[SIZE_L3 + nid], nid);
1613             }
1614         }
          init_list写的很复杂，其实仔细理解之后，实现的内容很简单，就是为cache_cache以及两个size cache （INDEX_AC, INDEX_L3）分配kmem_list3结构体，并用memcpy将initkmem_list3中的内容拷贝过来，另外再用MAKE_ALL_LISTS -> MAKE_LIST -> list_splice 来合并initkmem_list3列表中的内容。
可见有时候，不要把复杂的问题想简单了，该仔细处理的还是要仔细处理，特别是针对这种列表结构体。

kmem_cache_init中也运用kmem_cache_create来分配cache了，但这个过于复杂，将在另一篇笔记中加以阐述slab allocator （2）—— kmem_cache_create。

Posted on Edited on
前面提到过的buddy allocator通过用order列表来管理页面，从而达到减少外部碎片的效果。但是不可能每次分配都分配一页或者几页的内存，那样内存利用率太低，系统中将充满了内部碎片。所以，slab分配器也就应运而生了，其就是为了减少内部碎片而生的。具体为什么引入，以及slab的一些简介可以参考 Linux slab 分配器剖析， Fred's blog: 三月 2009。

     
     所谓的slab就是基于这么一张图的系统。简化之，其实就是一种基于后备高速缓存内存分配（参考ldd3，page247 ch 8）方式的内存管理系统。

     他的初始化由下图中的g_cpucache_up来标志，共有5个状态，按顺序依次迁移，在start_kernel -> mm_init -> kmem_cache_init中到达EARLY状态。此时slab_is_availabe()函数就返回真，也就是说此时slab系统已经就绪了。而最终的FULL状态是在kmem_cache_init_late中完成的。


上面这几个函数中可以看出，核心其实就是 kmem_cache_init。下面将重点介绍这个函数。
     这个函数很大，而且包含了很多知识点，具体可以参考《Understanding the Linux® Virtual Memory Manager》chapter 8。关于slab系统的内容很多，而且不是很好理解。先列举几个重要的数据结构。当然最核心的数据结构就是kmem_cache了，因为他巨大，所以就不在此列举了。

    1. kmem_list3
     struct kmem_list3 {
     struct list_head slabs_partial;     /* partial list first, better asm code */
     struct list_head slabs_full;
     struct list_head slabs_free;
     unsigned long free_objects;
     unsigned int free_limit;
     unsigned int colour_next;     /* Per-node cache coloring */
     spinlock_t list_lock;
     struct array_cache *shared;     /* shared per node */
     struct array_cache **alien;     /* on other nodes */
     unsigned long next_reap;     /* updated without locking */
     int free_touched;          /* updated without locking */
};
最重要的就是前3个参数，也就是我们在图1中提到的三个list：slab_full, slab_partial, slab_empty。

     2. array_cache
struct array_cache {
     unsigned int avail;
     unsigned int limit;
     unsigned int batchcount;
     unsigned int touched;
     spinlock_t lock;
     void *entry[];     /*
               * Must have this definition in here for the proper
               * alignment of array_cache. Also simplifies accessing
               * the entries.
               */
};
struct kmem_cache {
/* 1) per-cpu data, touched during every alloc/free */
     struct array_cache *array[NR_CPUS];
          ……
}
          array_cache是per CPU变量，具体可参考《Understanding the Linux® Virtual Memory Manager》chp 8.5: Per-CPU Object Cache。每一个cache，在create的时候，都会被分配一个array_cache（enable_cpucache）来提高性能。当然我们的总cache——cache_cache（从名字可以看出，它是cache的cache）也有一个这样的变量，在初始化时被填了一个__init_data initarray_cache.cache。之后在kmem_cache_init中再通过kmalloc来分配。arraycache与kmem_cache的关系大体如下图
     关于array_cache具体的内容会在另一篇笔记中作介绍slab allocator （3）—— arraycache。

     3. cache_sizes
     Gorman的书中将其称之为sizes cache。其实他就是一组定义了size的cache。在slab初始化的时候，我们会经常看到malloc_sizes这个数组，其定义如下：
struct cache_sizes malloc_sizes[] = {
#define CACHE(x) { .cs_size = (x) },
#include <linux/kmalloc_sizes.h>
     CACHE(ULONG_MAX)
#undef CACHE
};
struct cache_sizes {
     size_t               cs_size;
     struct kmem_cache     *cs_cachep;
#ifdef CONFIG_ZONE_DMA
     struct kmem_cache     *cs_dmacachep;
#endif
};
再看linux/kmalloc_sizes.h
#if (PAGE_SIZE == 4096)
     CACHE(32)
#endif
     CACHE(64)
#if L1_CACHE_BYTES < 64
     CACHE(96)
#endif
     CACHE(128)
#if L1_CACHE_BYTES < 128
     CACHE(192)
#endif
     CACHE(256)
     CACHE(512)
     CACHE(1024)
     CACHE(2048)
     CACHE(4096)
     CACHE(8192)
     CACHE(16384)
     CACHE(32768)
     CACHE(65536)
     CACHE(131072)
     ……
          稍加分析我们就可以知道在kmalloc_sizes.h中已经定义好了一组固定size的cache了，只是他们对应的两组cache列表（cs_cachep, cs_dmacachep）还没分配。之后在我们的kmem_cache_init中对INDEX_AC和INDEX_L3的初始化，都是在为这个数组的成员初始化。
INDEX_AC：sizeof(struct arraycache_init)对应的malloc_sizes中的索引。
INDEX_L3：sizeof(struct kmem_list3)对应的malloc_sizes中的索引。
          为什么要把这两个size单独提出来做初始化，我推测是因为在kmem_cache_create到时候需要频繁的分配arraycache_init和kmem_list3，而且对于kmem_cache来说也就这两个struct是需要动态分配的，所以需要先对这两个size的cache先做初始化，以便在初始化其他malloc_sizes数组成员的时候，可以使用这两个cache来为之分配arraycache_init和kmem_list3。

          说完这些数据结构了，再回头看看kmem_cache_init的流程。其实无非就是对cache_cache，malloc_sizes做初始化，下面还有几个值得关注的点。
     1. cache_chain
          在kmem_cache_init的一开始处，有
INIT_LIST_HEAD(&cache_chain);
list_add(&cache_cache.next, &cache_chain);
尚不知这个cache_chain是作何用的，先暂且列在这里

     2. cache_estimate
     1504     for (order = 0; order < MAX_ORDER; order++) {
1505         cache_estimate(order, cache_cache.buffer_size,
1506             cache_line_size(), 0, &left_over, &cache_cache.num);
1507         if (cache_cache.num)
1508             break;
1509     }
          这个函数作用其实很简单，就是决定：(1)cache_cache.buffer_size，也就是cache_cache的object size，以及可以存储多少个object (2)slab manager存储位置（on-slab/off-slab：看看flags是否包含CFLGS_OFF_SLAB）(3)利用slab上剩余的空间，初始化coloring机制。
          一个cache_cache的slab空间分割如下图：
          其中object的size如下：
          offsetof(struct kmem_cache, nodelists) + nr_node_ids * sizeof(struct kmem_list3 *);
          其实就是sizeof(kmem_cache)。可见cache_cache的slab要分配的就是kmem_cache。最后cache_cache->slab_size = slab_mgmt_size。
          coloring scheme的初始化为：
          cache_cache.colour_off = cache_line_size();
          cache_cache.colour = left_over / cache_cache.colour_off;
     
     3. init_list
          在kmem_cache_init的最后，有
1604         for_each_online_node(nid) {
1605             init_list(&cache_cache, &initkmem_list3[CACHE_CACHE + nid], nid);
1606
1607             init_list(malloc_sizes[INDEX_AC].cs_cachep,
1608                   &initkmem_list3[SIZE_AC + nid], nid);
1609
1610             if (INDEX_AC != INDEX_L3) {
1611                 init_list(malloc_sizes[INDEX_L3].cs_cachep,
1612                       &initkmem_list3[SIZE_L3 + nid], nid);
1613             }
1614         }
          init_list写的很复杂，其实仔细理解之后，实现的内容很简单，就是为cache_cache以及两个size cache （INDEX_AC, INDEX_L3）分配kmem_list3结构体，并用memcpy将initkmem_list3中的内容拷贝过来，另外再用MAKE_ALL_LISTS -> MAKE_LIST -> list_splice 来合并initkmem_list3列表中的内容。
可见有时候，不要把复杂的问题想简单了，该仔细处理的还是要仔细处理，特别是针对这种列表结构体。

kmem_cache_init中也运用kmem_cache_create来分配cache了，但这个过于复杂，将在另一篇笔记中加以阐述slab allocator （2）—— kmem_cache_create。