(ELC 2015) System Wide Memory Defragmenter
(ELC 2015) System Wide Memory Defragmenter
(ELC 2015) System Wide Memory Defragmenter
Email: [email protected]
Samsung R&D Institute India - Bangalore
CONTENT
Objective
Introduction
Memory Reclaim Techniques in Kernel
Summary
Conclusion
OBJECTIVE
To quickly recover entire system memory in one shot
INTRODUCTION
Memory fragmentation?
Non availability of higher order contiguous pages, although there are lots
Node 0, zone
Normal
972
352
171
25
2 2
0
Higher-order pages
Free Memory = (972*1 + 352*2 + 171*4 + 25*8) = 2560*4K = 10MB
Although we have 10MB memory free, still the request for 2^4 order (16*4K =
64K contiguous block) may fail.
This situation is known as external memory fragmentation.
TotalFreePages =
N
=
j
=
i
=
Ki
=
fragmentation level.
We have developed a user-space utility to measure the
overall fragmentation level of the system.
OUTPUT is shown below:
Order
2-Power
1
2
4
8
16
32
64
128
256
512
1024
Total
Embedded Linux Conference, San Jose, CA, March-2015
Free Pages
972
352
171
25
0
0
0
0
0
0
0
0%
37%
65%
92%
100%
100%
100%
100%
100%
100%
100%
81%
Average value
0
1
2
3
4
5
6
7
8
9
10
Nr Pages
0.000 3.797 6.547 9.219 1.000 1.000 1.000 1.000 1.000 1.000 1.000
__alloc_pages_nodemask
page = __alloc_pages_slowpath
if
gfp_flag &
__GFP_NO_KSWAPD
?
page = get_page_from_freelist
wake_all_kswapd
rebalance
page = get_page_from_freelist
YES
if
!page
?
restart
if
!page
?
NO
(SUCCESS)
return page
YES
NO
page =
__alloc_pages_direct_compact
4
if
page
?
if
page
?
YES
rebalance
page = __alloc_pages_may_oom
if
page
?
NO
YES
YES
YES
NO
YES
should_alloc_ret
ry?
NO
YES
page =
__alloc_pages_direct_compact
NO
if
(order > 3)
?
if
page
?
NO
YES
NO
if
(!did_some_progres
s) ?
page =
__alloc_pages_direct_reclaim
NO
restart
FAIL
NO
if
page
?
YES
SUCCESS
9
Initialize scan_control
structure
nr_reclaimed =
do_try_to_free_pages
shrink_zones
Find reclaimable pages in
this zone
shrink_slab
if
nr_reclaimed >=
nr_to_reclaim
?
YES
return nr_reclaimed
pages
return nr_reclaimed
#endif
Embedded Linux Conference, San Jose, CA, March-2015
10
11
12
ION
ION System Heap
page = alloc_buffer_page(orders)
orders[] = {8, 4, 0}
if
page fail &&
order == 4
?
Shrink all memory (totalram_pages)
Embedded Linux Conference, San Jose, CA, March-2015
13
14
total
468
0
468
used
390
201
0
390
free
78
267
0
78
shared
buffers
0
16
cached
172
217
86
24
24
17
AFTER:
free -tm
Mem:
-/+ buffers/cache:
ZRAM Swap:
Total:
buddyinfo
Node 0, zone Normal
total
468
0
468
used
217
195
0
217
free
250
272
0
250
shared
buffers
cached
21
246
230
97
40
16
57
15
16
Normal
Fragmentation[%]
0
0.00%
1
1.00%
2
1.90%
3
2.30%
4
3.30%
5
3.90%
6
4.30%
7
4.90%
8
6.80%
9
8.10%
10
13.20%
Overall
4.52%
AFTER:
Zone:
Order
Normal
Fragmentation[%]
0
0.00%
1
0.30%
2
1.00%
3
1.60%
4
2.10%
5
2.50%
6
2.60%
7
3.20%
8
3.80%
9
5.80%
10
9.00%
Overall
2.90%
17
total
468
93
562
used
455
379
34
490
free
12
88
59
71
shared
buffers
cached
72
972
352
171
52
14
AFTER:
free -tm
Mem:
-/+ buffers/cache:
ZRAM Swap:
Total:
buddyinfo
Node 0, zone Normal
total
468
93
562
used
362
318
90
453
free
105
150
3
109
shared
buffers
cached
41
473
218
1316
802
373
102
31
18
19
AFTER:
20
Normal
Fragmentation[%]
0
0.00%
1
30.10%
2
52.50%
3
74.30%
4
87.60%
5
94.80%
6
97.90%
7
100.00%
8
100.00%
9
100.00%
10
100.00%
Overall
76.11%
AFTER:
Zone:
Order
Normal
Fragmentation[%]
0
0.00%
1
1.70%
2
3.30%
3
22.60%
4
46.40%
5
68.60%
6
80.70%
7
88.10%
8
92.30%
9
94.20%
10
100.00%
Overall
54.35%
21
22
total
460
0
460
used
429
229
0
429
free
31
231
0
31
shared
buffers
0
24
cached
176
445
197
88
22
AFTER:
free -tm
Mem:
-/+ buffers/cache:
ZRAM Swap:
Total:
buddyinfo
Node 0, zone Normal
total
460
0
460
used
271
205
0
271
free
188
254
0
188
shared
buffers
0
cached
6
59
298
348
489
1189
611
199
42
23
11
23
memory)
24
Normal
Fragmentation[%]
0
0.00%
1
5.60%
2
10.50%
3
14.90%
4
17.10%
5
18.10%
6
19.30%
7
20.90%
8
22.50%
9
29.00%
10
48.30%
Overall
18.75%
AFTER:
Zone:
Order
Normal
Fragmentation[%]
0
0.00%
1
1.00%
2
11.20%
3
23.70%
4
39.40%
5
55.60%
6
66.30%
7
70.70%
8
75.40%
9
80.50%
10
86.40%
Overall
46.38%
Here, fragmentation level increases, because lots of lower order pages were
25
total
460
92
552
used
440
369
60
501
free
20
90
31
51
shared
buffers
cached
65
1728
498
138
39
AFTER:
free -tm
Mem:
-/+ buffers/cache:
ZRAM Swap:
Total:
buddyinfo
Node 0, zone Normal
total
460
92
552
used
352
319
92
444
free
107
140
0
107
shared
buffers
cached
31
595
2884
1236
432
201
89
34
12
26
27
AFTER:
28
Normal
Fragmentation[%]
0
0.00%
1
32.40%
2
52.10%
3
63.00%
4
69.20%
5
69.50%
6
69.50%
7
69.50%
8
69.50%
9
69.50%
10
79.60%
Overall
58.53%
AFTER:
Zone:
Order
Normal
Fragmentation[%]
0
0.00%
1
2.10%
2
23.00%
3
40.90%
4
53.40%
5
65.10%
6
75.40%
7
83.30%
8
88.80%
9
94.40%
10
96.20%
Overall
56.60%
Although, overall fragmentation becomes little less, in this case, but still it
29
30
buddyinfo
Node 0, zone DMA
Node 0, zone Normal
total
749
1021
1771
used
697
417
0
697
free
51
332
1021
1073
shared
buffers
0
27
cached
252
2
48
2
188
2
126
0
107
3
38
1
13
2
4
1
1
1
1
1
1
0
8
AFTER:
free -tm
Mem:
-/+ buffers/cache:
Physical Swap:
Total:
buddyinfo
Node 0, zone DMA
Node 0, zone Normal
total
749
1021
1771
used
331
219
302
634
free
417
529
719
1136
shared
buffers
0
cached
21
90
1
151
1
124
2
65
1
37
3
31
3
20
2
2
2
44
3
52
1
18
2
71
31
32
DMA
Normal
Fragmentation[%] Fragmentation[%]
0
0.00%
0.00%
1
0.10%
0.00%
2
0.50%
2.40%
3
1.20%
6.60%
4
1.20%
13.70%
5
5.50%
18.80%
6
8.40%
22.20%
7
19.80%
24.40%
8
31.30%
25.40%
9
54.20%
27.60%
10
100.00%
31.80%
Overall
20.20%
15.72%
AFTER:
Zone:
Order
DMA
Normal
Fragmentation[%] Fragmentation[%]
0
0.00%
0.00%
1
0.00%
0.10%
2
0.00%
0.20%
3
0.20%
0.50%
4
0.40%
0.70%
5
1.70%
1.20%
6
4.20%
1.80%
7
7.50%
2.00%
8
14.10%
7.40%
9
33.90%
20.40%
10
47.10%
29.30%
Overall
9.92%
5.78%
33
total
749
1021
1771
used
685
593
445
1130
free
63
156
576
640
shared
buffers
cached
87
31
4039
6
859
9
336
5
120
6
113
6
66
0
25
0
6
0
0
1
0
0
1
11
cached
129
AFTER:
free -tm
Mem:
-/+ buffers/cache:
Physical Swap:
Total:
buddyinfo
Node 0, zone DMA
Node 0, zone Normal
total
749
1021
1771
used
620
479
580
1201
free
128
270
441
569
shared
buffers
0
89
349
84
388
75
270
58
66
43
46
19
23
8
16
2
12
1
3
1
0
0
21
34
35
DMA
Normal
Fragmentation[%] Fragmentation[%]
0
0.00%
0.00%
1
3.30%
25.20%
2
4.60%
36.30%
3
8.50%
45.20%
4
12.90%
51.60%
5
23.30%
63.50%
6
44.20%
77.50%
7
44.20%
88.10%
8
44.20%
93.20%
9
44.20%
93.20%
10
100.00%
69.64%
Overall
29.95%
60.64%
AFTER:
Zone:
Order
DMA
Normal
Fragmentation[%] Fragmentation[%]
0
0.00%
0.00%
1
2.30%
0.70%
2
6.60%
3.40%
3
14.40%
7.00%
4
26.40%
8.90%
5
44.30%
11.40%
6
60.10%
14.00%
7
73.40%
17.50%
8
80.00%
22.80%
9
86.70%
25.50%
10
100.00%
25.50%
Overall
44.93%
12.43%
36
37
total
460
92
552
used
453
391
0
453
free
shared
7
68
92
99
buffers
cached
58
162
104
287
46
AFTER:
free -tm
Mem:
-/+ buffers/cache:
ZRAM Swap:
Total:
buddyinfo
Node 0, zone Normal
total
460
92
552
used
331
275
85
416
free
128
184
7
135
shared
buffers
cached
52
271
139
1563
1380
462
101
14
38
AFTER:
495.009158]
495.752874]
495.806645]
495.826925]
495.838600]
495.847219]
495.853767]
495.859387]
495.865089]
495.868730]
495.868757]
[1:
[1:
[1:
[1:
[1:
[1:
[1:
[1:
[1:
[1:
[1:
Xorg:
Xorg:
Xorg:
Xorg:
Xorg:
Xorg:
Xorg:
Xorg:
Xorg:
Xorg:
Xorg:
Earlier, during ION system heap allocation, for every order-4 allocation, it fallback to
order-0 allocation. Thus application performance will be degraded.
With shrink memory during order-4 allocation failure, the fallback will happen only
once. The next order-4 allocations will pass.
Chances are that even order-8 allocation may pass, which will never happen in earlier
case. Thus application launch performance can be increased and OOM can be delayed.
40
Normal
Fragmentation[%]
0
0.00%
1
12.10%
2
25.10%
3
89.50%
4
100.00%
5
100.00%
6
100.00%
7
100.00%
8
100.00%
9
100.00%
10
100.00%
Overall
75.15%
AFTER:
Zone:
Order
Normal
Fragmentation[%]
0
0.00%
1
0.80%
2
1.60%
3
20.50%
4
54.00%
5
76.50%
6
86.30%
7
89.10%
8
89.80%
9
95.30%
10
96.80%
Overall
55.52%
41
SUMMARY
Initial Free Memory = 50MB, Reclaimable memory = 150MB
Existing Approach:
A1 A2 A3 A4 A5 A6 A7 A8 A9 A10
X1 = 50MB
A11
A12
X2 = 5MB X2 = 5MB
SLOW PATH
SLOW PATH
New Approach:
A1 A2 A3 A4 A5 A6 A7 A8 A9 A10
X1 = 50MB
A11
Run Memory
Shrinker
A12
A13
A14
NO SLOW PATH
42
CONCLUSION
It can be developed as a system tool and invoked from user or kernel space.
It can help in restoring the memory accumulated during initial boot-up, which
43
Thank You!
Questions??????
Embedded Linux Conference, San Jose, CA, March-2015
44