-
Notifications
You must be signed in to change notification settings - Fork 27
/
Copy pathslab-allocator-and-kmalloc.html
636 lines (422 loc) · 46.9 KB
/
slab-allocator-and-kmalloc.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
<!DOCTYPE html>
<html lang="en">
<!-- Head tag -->
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="google-site-verification" content="xBT4GhYoi5qRD5tr338pgPM5OWHHIDR6mNg1a3euekI" />
<meta name="baidu-site-verification" content="093lY4ziMu" />
<meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
<meta name="description" content="一个有内涵的技术分享平台">
<meta name="keyword" content="meizu,kernel,魅族">
<link rel="shortcut icon" href="/img/ironman-draw.png">
<!-- Place this tag in your head or just before your close body tag. -->
<script async defer src="https://buttons.github.io/buttons.js"></script>
<!--<link href='http://fonts.googleapis.com/css?family=Montserrat:400,700' rel='stylesheet' type='text/css'>-->
<title>
SLAB 分配器和 kmalloc - 魅族内核团队
</title>
<link rel="canonical" href="https://kernel.meizu.com//slab-allocator-and-kmalloc.html">
<!-- Bootstrap Core CSS -->
<link rel="stylesheet" href="css/bootstrap.min.css">
<!-- Custom CSS -->
<link rel="stylesheet" href="css/dusign-light.css">
<link rel="stylesheet" href="css/dusign-common-light.css">
<link rel="stylesheet" href="css/font-awesome.css">
<link rel="stylesheet" href="css/toc.css">
<!-- background effects end -->
<!-- Pygments Highlight CSS -->
<link rel="stylesheet" href="css/highlight.css">
<link rel="stylesheet" href="css/widget.css">
<link rel="stylesheet" href="css/rocket.css">
<link rel="stylesheet" href="css/signature.css">
<link rel="stylesheet" href="css/fonts.googleapis.css">
<link rel="stylesheet" href="//cdn.bootcss.com/font-awesome/4.3.0/css/font-awesome.min.css">
<!-- photography -->
<link rel="stylesheet" href="css/photography.css">
<!-- ga & ba script hoook -->
<script></script>
<meta name="generator" content="Hexo 7.3.0"></head>
<!-- hack iOS CSS :active style -->
<body ontouchstart="">
<!-- background effects start -->
<!-- background effects end -->
<!-- Modified by Yu-Hsuan Yen -->
<!-- Post Header -->
<style type="text/css">
header.intro-header{
background-image: linear-gradient(rgba(0, 0, 0, 0.3), rgba(0, 0, 0, 0.3)), url('')
/*post*/
}
</style>
<header class="intro-header" >
<!-- Signature -->
<div id="signature">
<div class="container">
<div class="row">
<div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1">
<div class="post-heading">
<div class="tags">
<a class="tag" href="/tags/#Linux" title="Linux">Linux</a>
<a class="tag" href="/tags/#SLAB" title="SLAB">SLAB</a>
<a class="tag" href="/tags/#SLUB" title="SLUB">SLUB</a>
</div>
<h1>SLAB 分配器和 kmalloc</h1>
<h2 class="subheading"></h2>
<span class="meta">
Posted by Guo Chumou on
2016-05-09
</span>
</div>
</div>
</div>
</div>
</div>
<div class="waveWrapper">
<div class="wave wave_before" style="background-image: url('/img/wave-light.png')"></div>
<div class="wave wave_after" style="background-image: url('/img/wave-light.png')"></div>
</div>
</header>
<!-- Navigation -->
<nav class="navbar navbar-default navbar-custom navbar-fixed-top">
<div class="container-fluid">
<!-- Brand and toggle get grouped for better mobile display -->
<div class="navbar-header page-scroll">
<button type="button" class="navbar-toggle">
<span class="sr-only">Toggle navigation</span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</button>
<a class="navbar-brand" href="/">魅族内核团队</a>
</div>
<!-- Collect the nav links, forms, and other content for toggling -->
<!-- Known Issue, found by Hux:
<nav>'s height woule be hold on by its content.
so, when navbar scale out, the <nav> will cover tags.
also mask any touch event of tags, unfortunately.
-->
<div id="huxblog_navbar">
<div class="navbar-collapse">
<ul class="nav navbar-nav navbar-right">
<li>
<a href="/">Home</a>
</li>
<li>
<a href="/about/">About</a>
</li>
<li>
<a href="/archive/">Archives</a>
</li>
<li>
<a href="/categories/">Categories</a>
</li>
<li>
<a href="/tags/">Tags</a>
</li>
</ul>
</div>
</div>
<!-- /.navbar-collapse -->
</div>
<!-- /.container -->
</nav>
<script>
// Drop Bootstarp low-performance Navbar
// Use customize navbar with high-quality material design animation
// in high-perf jank-free CSS3 implementation
var $body = document.body;
var $toggle = document.querySelector('.navbar-toggle');
var $navbar = document.querySelector('#huxblog_navbar');
var $collapse = document.querySelector('.navbar-collapse');
$toggle.addEventListener('click', handleMagic)
function handleMagic(e){
if ($navbar.className.indexOf('in') > 0) {
// CLOSE
$navbar.className = " ";
// wait until animation end.
setTimeout(function(){
// prevent frequently toggle
if($navbar.className.indexOf('in') < 0) {
$collapse.style.height = "0px"
}
},400)
}else{
// OPEN
$collapse.style.height = "auto"
$navbar.className += " in";
}
}
</script>
<!-- Main Content -->
<!-- Post Content -->
<article>
<div class="container">
<div class="row">
<!-- Post Container -->
<div class="
col-lg-8 col-lg-offset-2
col-md-10 col-md-offset-1
post-container">
<h2 id="为什么要有-SLAB"><a href="#为什么要有-SLAB" class="headerlink" title="为什么要有 SLAB"></a>为什么要有 SLAB</h2><p>一般来说，一个新东西的产生总是为了解决某一个现有的问题的。那么，slab 是为了解决什么问题呢？我们知道，在 Linux 内核中的内存管理是使用伙伴系统 (Buddy System)，但是这个系统有一个问题就是，它的最小单位是页，即 PAGE_SIZE ，在 x86 架构中这个常数一般是 4k 。但是很多情况下我们要分配的单元大小是远远小于 4k 的，如果使用伙伴系统的话，必定是会产生很大的浪费的。所以，一个粒度更加小的分配器呼之欲出，SLAB 就是为了解决这个小粒度内存分配的问题的。</p>
<h2 id="如何解决以及结构组织"><a href="#如何解决以及结构组织" class="headerlink" title="如何解决以及结构组织"></a>如何解决以及结构组织</h2><p>既然 SLAB 分配器已经定下了这样的一个目标，那么它的策略是什么呢？ 答曰，SLAB 分配器是基于所谓“面向对象”的思想，当然，这里的“面向对象”跟 C++ 和 Java 等的“面向对象”是不一样的。这里的“面向对象”更加确切的说法是“面向对象类型”，不同的类型使用不同的 SLAB ，一个 SLAB 只分配一种类型。而且，SLAB 为了提高内核中一些十分频繁进行分配释放的“对象”的分配效率， SLAB 的做法是：每次释放掉某个对象之后，不是立即将其返回给伙伴系统（SLAB 分配器是建立在伙伴系统之上的），而是存放在一个叫 array_cache 的结构中，下次要分配的时候就可以直接从这里分配，从而加快了速度。</p>
<p>这里必须明确几个概念，说明如下：</p>
<ul>
<li><p>缓存(cache) : 这里的缓存只是一个叫法而已，其实就是一个管理结构头，它控制了每个 SLAB 的布局，具体的结构体是 struct kmem_cache 。（注意，虽然现在几乎所有的书或者博客都将这一个结构称为“缓存”，不过我觉得在这里称为“管理结构头”是更为合适的，所以下文中统一将“缓存（cache）”称为“管理结构头”。）</p>
</li>
<li><p>SLAB: 从伙伴系统分配的 2^order 个物理页就组成了一个 SLAB ，而后续的操作就是在这个 SLAB 上在进行细分的，具体的结构体是 struct slab 。</p>
</li>
<li><p>对象(object) : 上面说到，每一个 SLAB 都只针对一个数据类型，这个数据类型就被称为该 SLAB 的“对象”，将该对象进行对齐之后的大小就是该“对象”的大小，依照该大小将上面的 SLAB 进行切分，从而实现了我们想要的细粒度内存分配。</p>
</li>
<li><p>per-CPU 缓存：这个就是上面提到的 array_cache ，这个是为了加快分配，预先从 SLAB 中分配部分对象内存以加快速度。具体的结构体是 struct array_cache，包含在 struct kmem_cache 中。</p>
</li>
</ul>
<p>还有，我们在用户态编程的时候，需要分配内存的时候，一般都是使用 malloc() 函数来实现。那么在内核态编程中，如果我们要分配内存，而且又没有必要使用上面的基于某个特定对象的，内核给我们提供了一个类似 malloc() 的接口—— kmalloc() 。值得注意的是，其实 kmalloc() 也是基于 SLAB 分配器的，只不过它所需要的管理结构头已经按照 2^n 的大小排列事先准备好了而已，这个管理结构体数组是 struct cache_sizes malloc_sizes[] 。</p>
<p>还有，每个“对象”的缓存被组织成一个链表——cache_chain，然后每个缓存的 SLAB 被组织了三个不同的链表——slab_full，slab_partial 和 slab_free，这三个链表有何不同应该可以见名知意，就不赘述了。</p>
<p>然后，你可能就会发现了，在<strong>对象</strong>那一点，很可能出现一种情况，那就是 SLAB 的大小跟 object 的大小不整除，也就是说有不足于一个 object 的大小的空间剩余，怎么办，浪费掉吗？肯定不是！内核很好地利用了这些剩余的空间，提出了“缓存染色(cache coloring)”的概念。当然，这里的<strong>染色</strong>不是真的去染成红绿蓝等颜色，这只是一种说法而已。具体地将，就是让每个缓存的 SLAB 在页的起始位置有不同的偏移，以缓解<strong>缓存过热</strong>的问题。注意，这里提到的“缓存过热”中的“缓存”是真的 CPU 的物理缓存。具体的我后面会详细说明，这里只是综述一下。</p>
<h2 id="初始化——-kmem-cache-init"><a href="#初始化——-kmem-cache-init" class="headerlink" title="初始化—— kmem_cache_init()"></a>初始化—— kmem_cache_init()</h2><p>想要让 SLAB 分配器工作起来，必须进行一系列的初始化。不过这里存在一个“鸡生蛋蛋生鸡”的问题。我们前面说过，每个缓存需要一个管理结构头，而建立缓存的实质就是分配一个管理结构头 struct kmem_cache 来描述 SLAB 的布局，以指导后续的分配行为，这个建立缓存的过程是用函数 kmem_cache_create() 来实现的，这里只是点一下，下面会详细说明。很明显这个管理结构头的大小小于一页，那么是十分适合使用 SLAB 分配器进行分配的，但是问题是此时 SLAB 分配器还没有初始化完成，怎么办？内核的做法是直接静态分配一个 struct kmem_cache 类型的变量——cache_cache（不得不说，这个变量名起得真好！），然后呢，整个初始化的过程分为六步：</p>
<ol>
<li><p>初始化 struct kmem_cache 变量 cache_cache 。该变量之所以重要，是因为<strong>它是以后所有的对象的管理结构头的管理结构头，专业一点的话可以称作是“元管理结构头”</strong>，然后上面提到的 array_cache 和三个链表 kmem_list3 都是这个结构体里面的成员，初始化也都是静态分配的，对应的静态变量分别是 initarray_cache 和 initkmem_list3 。</p>
</li>
<li><p>建立 kmalloc() 的 struct array_cache 对应大小的管理结构头。为什么要进行这一步呢，因为下面的步骤是要完整地建立其 kmalloc() 支持的所有 2^n 大小的管理结构头，完成这一步就相当于 kmalloc() 完全可用了。但是每个管理结构头都必须要 struct array_cache 和 struct kmem_list3 这两个辅助管理结构头，就必须要建立这两个对应大小的 kmalloc() 的管理结构头以便能够使用 kmalloc() <strong>动态分配</strong>！这里之所以要提到<strong>动态分配</strong>是因为在给 struct array_cache 对应大小建立 kmalloc() 的管理结构头的时候，其自己的 struct array_cache 和 struct kmem_list3 也是静态分配的，所以后续将会把它们使用动态分配的空间替换掉。</p>
</li>
<li><p>建立 kmalloc() 的 struct kmem_list3 对应大小的管理结构头以及剩下的 2^n 对应大小的管理结构头。第二点已经说明过了，就不重复了。</p>
</li>
<li><p>（其实包括第五步）此时 kmalloc() 已经可用了，所以如上面所说要使用 kmalloc() 分配的动态内存去替代前面所有的静态内存，需要替换的对象有：cache_cache 的 struct array_cache ，struct array_cache 对应大小的 kmalloc() 的管理结构头的 struct array_cache 和 struct kmem_list3，以及 struct kmem_list3 对应大小的 kmalloc() 的管理结构头的 struct kmem_list3 。</p>
</li>
<li><p>重新调整各个管理结构体的 struct array_cache 中的 entry[] 的数目。</p>
</li>
</ol>
<p>然后这里有一个问题就是，内核是如何知道当前是属于哪一个阶段呢？为了解决这个问题，内核使用了一个枚举变量 g_cpucache_up ，其接受的变量范围有：NULL , PARTIAL_AC , PARTIAL_L3，PEARLY , FULL 。当第二步完成的时候，标记为 PARTIAL_AC ，此时意味着以后的 struct array_cache 都可以使用 kmalloc() 分配了；当第三步完成的时候，标记为 PARTIAL_L3 ，此时意味着以后的 struct kmem_l3 都可以使用；当第四和第五步完成的时候，标记为 PARTIAL_EARLY ，此时意味着 kmalloc() 已经支持所有其支持的 2^n 大小的内存分配了。</p>
<p>然后有一个很重要的点就是，如果你读过 mm/slab.c 的源代码，你就会发现，在建立 struct array_cache 的管理结构头和为 kmalloc() 各个管理结构头的 struct array_cache 的时候，**内核使用的是 struct arraycache_init 而不是 struct array_cache **，这究竟是怎么一回事？其实这是很有讲究的，且听我慢慢到来。</p>
<p>其实 struct initarray_cache 的完整结构是这样的：</p>
<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">struct</span> <span class="keyword">arraycache_init</span> {</span><br><span class="line"> <span class="keyword">struct</span> array_cache cache;</span><br><span class="line"> <span class="keyword">void</span> <span class="operator">*</span>entry[BOOT_CPUCACHE_ENTRIES];</span><br><span class="line">};</span><br></pre></td></tr></table></figure>
<p>从上面的结构可以看出，struct arraycache_init 就只是比 struct array_cache 多了一个 void * 的数组而已，这个究竟有什么区别呢？诶，别着急，我们再来看一下 struct array_cache 的结构就清楚了：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">struct</span> <span class="title class_">array_cache</span> {</span><br><span class="line"> <span class="type">unsigned</span> <span class="type">int</span> avail;</span><br><span class="line"> unsighed <span class="type">int</span> limit;</span><br><span class="line"> <span class="type">unsigned</span> <span class="type">int</span> batchcount;</span><br><span class="line"> <span class="type">unsigned</span> <span class="type">int</span> touched;</span><br><span class="line"> <span class="type">spinlock_t</span> lock;</span><br><span class="line"> <span class="type">void</span> *entry[];</span><br><span class="line">};</span><br></pre></td></tr></table></figure>
<p>联系上文我提到 Per-CPU 的时候说过，为了加快速度将 SLAB 的一部分内存分配到 array_cache ，而事实上就上面我们看到的 struct array_cache 的结构，只是有一个 void * 的数组而已，而且是个伪数组，并没有数组项。其实细想这是一种十分优美的实现方法。因为各个管理结构头所需要的“一部分内存”是不一样的，这样就保证了一个通用性，每次要访问 array_cache 里面的内存的时候，只需要进行 array_cache->entry[下标] 就可以了。然后我们再来解决上面提到的 struct arraycache_init 的问题。内核静态分配了这样的一个 struct arraycache_init 的静态变量：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">static</span> <span class="keyword">struct</span> <span class="title class_">arraycache_init</span> initarray_cache __initdata =</span><br><span class="line"> { {<span class="number">0</span>, BOOT_CPUCACHE_ENTRIES, <span class="number">1</span>, <span class="number">0</span>} };</span><br></pre></td></tr></table></figure>
<p>对照结构体的成员我们发现，struct array_cache 的 batchcount 被被赋值为 BOOT_CPUCACHE_ENTRIES ，这个 batchcount 是什么来头呢？这个变量就是控制着我们上面提到的“一部分内存”的具体量了。更重要的是，我们可以看到，struct arraycache_init 多出来的那个 void * 数组的个数，就是 BOOT_CPUCACHE_ENTRIES 。也就是说，<strong>struct array_cache 的管理结构头的 struct array_cache 里面的 entry 的真正空间就在这里了。</strong></p>
<p>提到这里的话，那么初始化的第六步就可以彻底地理解了：为每个 kmalloc() 的管理结构头的 array_cache 重新调整 entry 的个数，具体的函数调用是 enable_cpucache()->do_tune_cpucache()->alloc_arraycache() 。</p>
<h2 id="创建管理结构头——-kmem-cache-create"><a href="#创建管理结构头——-kmem-cache-create" class="headerlink" title="创建管理结构头—— kmem_cache_create()"></a>创建管理结构头—— kmem_cache_create()</h2><p>因为在初始化的过程中已经静态分配了管理结构头的管理结构头—— cache_cache，所以可以直接使用 kmem_cache_alloc() 给提供的对象建立其自己的管理结构头 struct kmem_cache ，而这个函数的作用也是如此。除了如此外，这个函数还有一个十分重要的功能就是创建 SLAB 的布局，即—— 应该占用页帧的阶数，SLAB 管理头应该在页内还是页外，剩余空间是多少，染色的个数，染色的大小（这两个说法在这里可能有点奇怪，不过等我们提到“染色”的时候就清楚了）等，具体的函数调用是 calculate_slab_order()->cache_estimate() ，过程比较简单，就不提了。</p>
<p>最后调用 enable_cpu_cache() 配置 struct array_cache 和 struct kmem_list3 ，这一步类似于我们在初始化那一节提到的第六步，也就不在重复了。</p>
<p>最后建立的管理结构头加入到 cache_chain 这个链表。</p>
<h2 id="分配内存——-kmem-cache-alloc"><a href="#分配内存——-kmem-cache-alloc" class="headerlink" title="分配内存—— kmem_cache_alloc()"></a>分配内存—— kmem_cache_alloc()</h2><p>kmem_cache_alloc() 这个函数进过多层的封装，最终调用的是 ____cache_alloc() ，kmalloc() 也是如此。我们先来看一下这个函数：</p>
<figure class="highlight xl"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line">static inline void * ____cache_alloc(struct kmem_cache *cachep, gfp_t flags)</span><br><span class="line">{</span><br><span class="line"> void *objp;</span><br><span class="line"> struct array_cache *ac;</span><br><span class="line"></span><br><span class="line"> check_irq_off();</span><br><span class="line"></span><br><span class="line"> ac = cpu_cache_get(cachep);</span><br><span class="line"> <span class="function"><span class="title">if</span> (likely(ac-></span>avail)) {</span><br><span class="line"> STATS_INC_ALLOCHIT(cachep);</span><br><span class="line"> <span class="function"><span class="title">ac</span>-></span>touched = <span class="number">1</span>;</span><br><span class="line"> <span class="function"><span class="title">objp</span> = ac-></span><span class="function"><span class="title">entry</span>[--ac-></span>avail];</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> STATS_INC_ALLOCMISS(cachep);</span><br><span class="line"> objp = cache_alloc_refill(cachep, flags);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="title">kmemleak_erase</span>(&ac-></span><span class="function"><span class="title">entry</span>[ac-></span>avail]);</span><br><span class="line"> return objp;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>这里首先涉及到我当初一直困惑的一个点：在使用 kmem_cache_create() 建立相关的管理结构之后，究竟有没有分配真正的内存空间呢？在通读了相关的代码之后，我得到了答案：<strong>没有，也没必要。因为存在这么一种情况：如果使用 kmem_cache_create() 之后还分配了真正的内存空间之后，如果该 SLAB 一直不使用，那么岂不是浪费了很多宝贵的内存了吗？</strong></p>
<p>解决上面的这一个疑惑之后，我们就可以知道在上面的代码中，第一次我们是走 else 那个分支了，也就是调用了 cache_alloc_refill() 来分配空间：</p>
<figure class="highlight xl"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line">static void *cache_alloc_refill(struct kmem_cache *cachep, gfp_t flags)</span><br><span class="line">{</span><br><span class="line"> ...</span><br><span class="line">retry:</span><br><span class="line"> ...</span><br><span class="line"> <span class="keyword">while</span> (batchcount > <span class="number">0</span>) {</span><br><span class="line"> struct list_head *entry;</span><br><span class="line"> struct slab *slabp;</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="title">entry</span> = l3-></span>slabs_partial.next;</span><br><span class="line"> <span class="function"><span class="title">if</span> (entry == &l3-></span>slabs_partial) {</span><br><span class="line"> <span class="function"><span class="title">l3</span>-></span>free_touched = <span class="number">1</span>;</span><br><span class="line"> <span class="function"><span class="title">entry</span> = l3-></span>slabs_free.next;</span><br><span class="line"> <span class="function"><span class="title">if</span> (entry == &l3-></span>slabs_free)</span><br><span class="line"> goto must_grow;</span><br><span class="line"> }</span><br><span class="line"> }</span><br></pre></td></tr></table></figure>
<p>这里我再插一句：在 Linux 内核中的链表的实现是十分简洁优美的，它只有两个指针，并不存在数据域。这么做是为了通用性，即任何结构都可以组织自己的链表，然后在结构体中嵌入 struct list_head 即可。然后可能有人会问了，如果我有一个 struct list_head ，那么如何才能访问到该链表的起始结构呢？内核十分贴心的给我们准备了一个宏：<strong>container_of</strong>：</p>
<figure class="highlight elm"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">#define container_of(ptr, <span class="keyword">type</span>, member) ({ \</span><br><span class="line"> const typeof((type *)0->member)*__mptr = (ptr); \</span><br><span class="line"> (<span class="keyword">type</span> *)((char *)__mptr - offsetof(type, member)) \</span><br><span class="line"> })</span><br></pre></td></tr></table></figure>
<p>简单来说，这个宏的作用就是：*<em>我有一个类型为 (type <em>)->member 的变量，想要得到包含该变量的 type 类型变量的地址。</em></em></p>
<p>所以在这里，如前面所说，这里 l3 的三个链表都是连接 struct SLAB 类型的，而这个类型就是内存空间的真正所在，也就是我们前面所说的 2^order 个物理页组成的 SLAB。</p>
<p>在 kmem_cache_create() 的过程中，在分配 struct kmem_list3 的时候调用了 kmem_list3_init() (line 3844) 将 l3 的三个链表全都置为首尾相连的空链表，所以上面的函数在初次运行的时候最终将跳转到 must_grow 这个标签：</p>
<figure class="highlight xl"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line">must_grow:</span><br><span class="line"> <span class="function"><span class="title">l3</span>-></span><span class="function"><span class="title">free_objects</span> -= ac-></span>avail;</span><br><span class="line">alloc_done:</span><br><span class="line"> <span class="function"><span class="title">spin_unlock</span>(&l3-></span>list_lock);</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="title">if</span> (unlikely(!ac-></span>avail)) {</span><br><span class="line"> int x;</span><br><span class="line"> x = cache_grow(cachep, flag | THISNODE, node, NULL);</span><br><span class="line"></span><br><span class="line"> ac = cpu_cache_get(cachep);</span><br><span class="line"> <span class="function"><span class="title">if</span> (!x && ac-></span>avail)</span><br><span class="line"> return NULL;</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="title">if</span> (!ac-></span>avail)</span><br><span class="line"> goto retry;</span><br><span class="line"> }</span><br></pre></td></tr></table></figure>
<p>很明显，函数将调用 cache_grow() 来进行真正的内存分配：</p>
<figure class="highlight xl"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">static int cache_grow(struct kmem_cache *cachep,</span><br><span class="line"> gfp_t flags, int nodeid, void *objp)</span><br><span class="line">{</span><br><span class="line"> ...</span><br><span class="line"> <span class="function"><span class="title">offset</span> = l3-></span>colour_next;</span><br><span class="line"> <span class="function"><span class="title">l3</span>-></span>colour_next++;</span><br><span class="line"> <span class="function"><span class="title">if</span> (l3-></span><span class="function"><span class="title">colour_next</span> >= cachep-></span>colour)</span><br><span class="line"> <span class="function"><span class="title">l3</span>-></span>colour = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="title">offset</span> *= cachep-></span>colur_off;</span><br><span class="line"> ...</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>诶，到这里，总算可以说到前面铺垫了很久的所谓的“缓存着色”了，不过我觉得我得先简单地提一下 CPU cache 的工作原理才行：</p>
<p>CPU cache 就是我们常看到的一级缓存，二级缓存，三级缓存啊，引入这些缓存是因为内存 RAM 的速度相较于 CPU 的速度而言，是在是太慢了，所以为了提高速度， CPU 制造商提供了速度接近于 CPU 的小容量缓存，以便加速 CPU 与 RAM 的数据交换。具体的策略是：</p>
<p>每块 cache 会被分为更小的 cache line ，每个 cache line 的容量是一样的，然后 CPU 将虚拟地址分成三部分—— data, index, tag ，其中 data 长度是 cache line 的长度，index 的长度是 cache 的长度减去 data 的长度，最后 tag 的长度是虚拟地址的长度减去 data+index 的长度。举个例子，在 x86 的机器中，虚拟地址的地址空间是 32bit=2^32 ，假设我们的一级缓存有 4MB=2^22，cache line 的长度是 64bit=2^6 ，所以，data 就是 6 位，index 就是 (22-6) = 12 位，tag 就是 32-22=10 位。然后得到这些位之后，CPU 的每一个虚拟地址，将其分成上面的三部分之后，将按照 index 作为索引存入到 cache 中，然后在看需要的内容是否在 cache 中，这回比较需要的虚拟地址的 tag 与 cache 对应索引 index 的 tag 是否一致，如果一致说明 cache hit ，否则说明 cache miss 。</p>
<p>有点啰嗦，不过这些知识准备是必须的，然后我们就可以来具体阐述了。</p>
<p>我们在前面提到，SLAB 利用剩余的不足一个 object 的空间来进行缓存染色。具体说来，就是以平台的 cache line 的长度（存储在 cachep->colour_off）为偏移值（<strong>这一点非常重要！</strong>），计算出剩余的空间有多少个偏移值 cachep->colour ，然后就从 0 到 cachep->colour - 1（这个值是 l3->colour_next），每次就偏移 colour_next * colour_off 。这样，根据我们上面的叙述，每个 SLAB 将最终被放到不同的 cache line ，从而缓解了缓存过热的问题。</p>
<p>不过，如果你细心一点的话，你也可以发现，其实这个方法并不是特别的有效，因为它的有效范围只有 colour 个，也就是说，colour 个之后，还是会发生覆盖的问题，所以我在上面才用了<strong>缓解</strong>一词。</p>
<p>总之，上面的代码就计算了下一个偏移值 offset ，那么真正的偏移在那里呢？请看后面的代码：</p>
<figure class="highlight lisp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">if (!objp)</span><br><span class="line"> objp = kmem_getpages(<span class="name">cachep</span>, local_flags, nodeid)<span class="comment">;</span></span><br><span class="line">if (!objp)</span><br><span class="line"> goto failed<span class="comment">;</span></span><br><span class="line"></span><br><span class="line">slabp = alloc_slabmgmt(<span class="name">cachep</span>, objp, offset,</span><br><span class="line"> local_flags & ~GFP_CONSTRAINT_MASK, nodeid)<span class="comment">;</span></span><br></pre></td></tr></table></figure>
<p>真正的页分配就在这里了—— kmem_getpages() ，而真正的偏移就在 alloc_slabmgmt() 这个函数：</p>
<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line">static <span class="keyword">struct</span> slab *alloc_slabmgmt(<span class="keyword">struct</span> kmem_cache *cachep, void *objp,</span><br><span class="line"> <span class="built_in">int</span> colour_off, gfp_t local_flags,</span><br><span class="line"> <span class="built_in">int</span> nodeid)</span><br><span class="line">{</span><br><span class="line"> <span class="keyword">struct</span> slab *slabp;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> (<span class="type">OFF_SLAB</span>(cachep)) {</span><br><span class="line"> ...</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> slabp = objp + colour_off;</span><br><span class="line"> colour_off += cachep->slab_size;</span><br><span class="line"> }</span><br><span class="line"> slabp->inuse = <span class="number">0</span>;</span><br><span class="line"> slabp->colouroff = colour_off;</span><br><span class="line"> slabp->s_mem = objp + colour_off;</span><br><span class="line"> ...</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>诶，这里就可以很明显的看出来了整个 SLAB 的布局了：在连续页 objp 的起始，先是 colour_off 的偏移，然后是 SLAB 的一些管理头（管理头的大小是 cachep->slab_size），最后就是 object 的起始地址 slab->s_mem 了。</p>
<p>接下来的具体工作就是设置 SLAB 的 bufctl 控制数组，这里简单地提一下：slab 控制头有一个成员是 slabp->free ，意义是当前可用的 object 的索引，而 bufctl 控制的则是当前可用的下一个 object 的索引。</p>
<p>然后，新建立的 SLAB 加入到 l3 的 slabs_free 链表（这很重要！）。然后 cache_grow() 函数结束，返回 cache_alloc_refill() ，注意，此时我们只是分配了一个新的 SLAB ，还没有分配出去。具体就是在 goto retry 重新回到 cache_alloc_refill() 那里重新分配，因为此时我们的 slabs_free 已经不是空的了，所以函数接下来将 batchcount 个 object 移到 array_cache 中，然后修改 SLAB 的 bufctl 数组。最后，看 SLAB 是否所有 object 都分配完了，如果是，则移到 l3->slabs_full，否则则移到 l3->slabs_partial 。</p>
<p>然后，在后续的操作中，如果 array_cache 中有空间，则从其直接分配，否则就看 slabs_partial 或者是 slabs_free 是否有足够的 object ，在不然，就再次重复上面分配 SLAB 的操作了。</p>
<h2 id="释放内存——-kmem-cache-free"><a href="#释放内存——-kmem-cache-free" class="headerlink" title="释放内存—— kmem_cache_free()"></a>释放内存—— kmem_cache_free()</h2><p>有了上面已经十分详细的阐述之后，释放内存和后面的销毁就显得简单许多了，就是从 array_cache 移回 SLAB 并且修改 bufctl 控制数组而已。就不赘述了。</p>
<h2 id="销毁内存——-kmem-cache-destroy"><a href="#销毁内存——-kmem-cache-destroy" class="headerlink" title="销毁内存—— kmem_cache_destroy()"></a>销毁内存—— kmem_cache_destroy()</h2><p>同样不赘述了。</p>
<p>好了，整个 SLAB 分配器我大概就简单地说到这里。下面我说一下我自己的看法。我们可以发现，SLAB 为了加快分配速度，使用了很多的管理结构，其中花销最大的就是那个 bufctl 数组，所以如果是分配小的 object 的话，那么这个 bufctl 数组占用的空间还是相当可观的。这也是它的一个主要的缺点。而后来的 SLUB，就是针对这个缺点进行了有效的改进，而这，我在后面的博客中，将会详细讲解。</p>
<hr>
<!-- Pager -->
<ul class="pager">
<li class="previous">
<a href="//android-sensor-framework.html" data-toggle="tooltip" data-placement="top" title="Android Sensor Framework 概览">← Previous Post</a>
</li>
<li class="next">
<a href="//gps-introduction.html" data-toggle="tooltip" data-placement="top" title="Android 5.1 上的 MTK GPS">Next Post →</a>
</li>
</ul>
<!-- tip start -->
<div class="comment_notes">
<p>
This is copyright.
</p>
</div>
<!-- tip end -->
<!-- Music start-->
<!-- Music end -->
<!-- Sharing -->
<div class="social-share" data-wechat-qrcode-helper="" align="center"></div>
<!-- css & js -->
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/social-share.js/1.0.16/css/share.min.css">
<script src="https://cdnjs.cloudflare.com/ajax/libs/social-share.js/1.0.16/js/social-share.min.js"></script>
<!-- Sharing -->
<!-- gitment start -->
<!-- gitment end -->
<!-- 来必力City版安装代码 -->
<!-- City版安装代码已完成 -->
<!-- disqus comment start -->
<!-- disqus comment end -->
</div>
<!-- Tabe of Content -->
<!-- Table of Contents -->
<!-- Sidebar Container -->
<div class="
col-lg-8 col-lg-offset-2
col-md-10 col-md-offset-1
sidebar-container">
<!-- Featured Tags -->
<section>
<!-- no hr -->
<h5><a href="/tags/">FEATURED TAGS</a></h5>
<div class="tags">
<a class="tag" href="/tags/#Linux" title="Linux">Linux</a>
<a class="tag" href="/tags/#SLAB" title="SLAB">SLAB</a>
<a class="tag" href="/tags/#SLUB" title="SLUB">SLUB</a>
</div>
</section>
<!-- Friends Blog -->
<hr>
<h5>FRIENDS</h5>
<ul class="list-inline">
<li><a href="#" target="_blank">Other</a></li>
</ul>
</div>
</div>
</div>
</article>
<!-- async load function -->
<script>
function async(u, c) {
var d = document, t = 'script',
o = d.createElement(t),
s = d.getElementsByTagName(t)[0];
o.src = u;
if (c) { o.addEventListener('load', function (e) { c(null, e); }, false); }
s.parentNode.insertBefore(o, s);
}
</script>
<!-- anchor-js, Doc:http://bryanbraun.github.io/anchorjs/ -->
<script>
async("https://cdn.bootcss.com/anchor-js/1.1.1/anchor.min.js",function(){
anchors.options = {
visible: 'hover',
placement: 'left',
icon: 'ℬ'
};
anchors.add().remove('.intro-header h1').remove('.subheading').remove('.sidebar-container h5');
})
</script>
<style type="text/css">
/* place left on bigger screen */
@media all and (min-width: 800px) {
.anchorjs-link{
position: absolute;
left: -0.75em;
font-size: 1.1em;
margin-top : -0.1em;
}
}
</style>
<!-- Footer -->
<!-- Footer -->
<footer>
<div class="container">
<div class="row">
<div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1">
<ul class="list-inline text-center">
</ul>
<p class="copyright text-muted">
Copyright © meizu 2024
<br>
Powered by
<a href="https://github.com/dusign/hexo-theme-snail">
<i>hexo-theme-snail</i>
</a> |
<iframe name="star" style="margin-left: 2px; margin-bottom:-5px;" frameborder="0" scrolling="0"
width="100px" height="20px"
src="https://ghbtns.com/github-btn.html?user=dusign&repo=hexo-theme-snail&type=star&count=true">
</iframe>
</p>
</div>
</div>
</div>
</footer>
<!-- jQuery -->
<script src="js/jquery.min.js"></script>
<!-- Bootstrap Core JavaScript -->
<script src="js/bootstrap.min.js"></script>
<!-- Custom Theme JavaScript -->
<script src="js/hux-blog.min.js"></script>
<!-- Search -->
<script src="js/search.js"></script>
<!-- async load function -->
<script>
function async(u, c) {
var d = document, t = 'script',
o = d.createElement(t),
s = d.getElementsByTagName(t)[0];
o.src = u;
if (c) { o.addEventListener('load', function (e) { c(null, e); }, false); }
s.parentNode.insertBefore(o, s);
}
</script>
<!-- jquery.tagcloud.js -->
<script>
// only load tagcloud.js in tag.html
if($('#tag_cloud').length !== 0){
async("https://kernel.meizu.com/js/jquery.tagcloud.js",function(){
$.fn.tagcloud.defaults = {
//size: {start: 1, end: 1, unit: 'em'},
color: {start: '#bbbbee', end: '#0085a1'},
};
$('#tag_cloud a').tagcloud();
})
}
</script>
<!--fastClick.js -->
<script>
async("https://cdn.bootcss.com/fastclick/1.0.6/fastclick.min.js", function(){
var $nav = document.querySelector("nav");
if($nav) FastClick.attach($nav);
})
</script>
<!-- Google Analytics -->
<script>
// dynamic User by Hux
var _gaId = 'UA-XXXXXXXX-X';
var _gaDomain = 'yoursite';
// Originial
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', _gaId, _gaDomain);
ga('send', 'pageview');
</script>
<!-- Baidu Tongji -->
<!-- Search -->
<script type="text/javascript">
var search_path = "search.xml";
if (search_path.length == 0) {
search_path = "search.xml";
}
var path = "/" + search_path;
searchFunc(path, 'local-search-input', 'local-search-result');
</script>
<!-- busuanzi -->
<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
<a id="rocket" href="#top" class=""></a>
<script type="text/javascript" src="/js/totop.js?v=1.0.0" async=""></script>
<script type="text/javascript" src="/js/toc.js?v=1.0.0" async=""></script>
<!-- background effects line -->
<script type="text/javascript" src="/js/mouse-click.js" content='["🌱","just do it","🍀"]' color='["rgb(121,93,179)" ,"rgb(76,180,231)" ,"rgb(184,90,154)"]'></script>
<!-- background effects end -->
<!--<script size="50" alpha='0.3' zIndex="-999" src="/js/ribbonStatic.js"></script>-->
<script src="/js/ribbonDynamic.js"></script>
</body>
</html>