1 // SPDX-License-Identifier: GPL-2.0-or-later
2
3 /* Helper function which provides a wrapper around a merge new VMA operation. */
merge_new(struct vma_merge_struct * vmg)4 static struct vm_area_struct *merge_new(struct vma_merge_struct *vmg)
5 {
6 struct vm_area_struct *vma;
7 /*
8 * For convenience, get prev and next VMAs. Which the new VMA operation
9 * requires.
10 */
11 vmg->next = vma_next(vmg->vmi);
12 vmg->prev = vma_prev(vmg->vmi);
13 vma_iter_next_range(vmg->vmi);
14
15 vma = vma_merge_new_range(vmg);
16 if (vma)
17 vma_assert_attached(vma);
18
19 return vma;
20 }
21
22 /*
23 * Helper function which provides a wrapper around the expansion of an existing
24 * VMA.
25 */
expand_existing(struct vma_merge_struct * vmg)26 static int expand_existing(struct vma_merge_struct *vmg)
27 {
28 return vma_expand(vmg);
29 }
30
31 /*
32 * Helper function to reset merge state the associated VMA iterator to a
33 * specified new range.
34 */
vmg_set_range(struct vma_merge_struct * vmg,unsigned long start,unsigned long end,pgoff_t pgoff,vma_flags_t vma_flags)35 void vmg_set_range(struct vma_merge_struct *vmg, unsigned long start,
36 unsigned long end, pgoff_t pgoff, vma_flags_t vma_flags)
37 {
38 vma_iter_set(vmg->vmi, start);
39
40 vmg->prev = NULL;
41 vmg->middle = NULL;
42 vmg->next = NULL;
43 vmg->target = NULL;
44
45 vmg->start = start;
46 vmg->end = end;
47 vmg->pgoff = pgoff;
48 vmg->anon_pgoff = start >> PAGE_SHIFT;
49 vmg->vma_flags = vma_flags;
50
51 vmg->just_expand = false;
52 vmg->__remove_middle = false;
53 vmg->__remove_next = false;
54 vmg->__adjust_middle_start = false;
55 vmg->__adjust_next_start = false;
56 }
57
58 /* Helper function to set both the VMG range and its anon_vma. */
vmg_set_range_anon_vma(struct vma_merge_struct * vmg,unsigned long start,unsigned long end,pgoff_t pgoff,vma_flags_t vma_flags,struct anon_vma * anon_vma)59 static void vmg_set_range_anon_vma(struct vma_merge_struct *vmg, unsigned long start,
60 unsigned long end, pgoff_t pgoff, vma_flags_t vma_flags,
61 struct anon_vma *anon_vma)
62 {
63 vmg_set_range(vmg, start, end, pgoff, vma_flags);
64 vmg->anon_vma = anon_vma;
65 }
66
67 /*
68 * Helper function to try to merge a new VMA.
69 *
70 * Update vmg and the iterator for it and try to merge, otherwise allocate a new
71 * VMA, link it to the maple tree and return it.
72 */
try_merge_new_vma(struct mm_struct * mm,struct vma_merge_struct * vmg,unsigned long start,unsigned long end,pgoff_t pgoff,vma_flags_t vma_flags,bool * was_merged)73 static struct vm_area_struct *try_merge_new_vma(struct mm_struct *mm,
74 struct vma_merge_struct *vmg, unsigned long start,
75 unsigned long end, pgoff_t pgoff, vma_flags_t vma_flags,
76 bool *was_merged)
77 {
78 struct vm_area_struct *merged;
79
80 vmg_set_range(vmg, start, end, pgoff, vma_flags);
81
82 merged = merge_new(vmg);
83 if (merged) {
84 *was_merged = true;
85 ASSERT_EQ(vmg->state, VMA_MERGE_SUCCESS);
86 return merged;
87 }
88
89 *was_merged = false;
90
91 ASSERT_EQ(vmg->state, VMA_MERGE_NOMERGE);
92
93 return alloc_and_link_vma(mm, start, end, pgoff, vma_flags);
94 }
95
test_simple_merge(void)96 static bool test_simple_merge(void)
97 {
98 struct vm_area_struct *vma;
99 vma_flags_t vma_flags = mk_vma_flags(VMA_READ_BIT, VMA_WRITE_BIT, VMA_MAYREAD_BIT,
100 VMA_MAYWRITE_BIT);
101 struct mm_struct mm = {};
102 struct vm_area_struct *vma_left = alloc_vma(&mm, 0, 0x1000, 0, vma_flags);
103 struct vm_area_struct *vma_right = alloc_vma(&mm, 0x2000, 0x3000, 2, vma_flags);
104 VMA_ITERATOR(vmi, &mm, 0x1000);
105 struct vma_merge_struct vmg = {
106 .mm = &mm,
107 .vmi = &vmi,
108 .start = 0x1000,
109 .end = 0x2000,
110 .vma_flags = vma_flags,
111 .pgoff = 1,
112 .anon_pgoff = 1,
113 };
114
115 ASSERT_FALSE(attach_vma(&mm, vma_left));
116 ASSERT_FALSE(attach_vma(&mm, vma_right));
117
118 vma = merge_new(&vmg);
119 ASSERT_NE(vma, NULL);
120
121 ASSERT_EQ(vma->vm_start, 0);
122 ASSERT_EQ(vma->vm_end, 0x3000);
123 ASSERT_EQ(vma_start_pgoff(vma), 0);
124 ASSERT_EQ(vma_start_anon_pgoff(vma), 0);
125 ASSERT_FLAGS_SAME_MASK(&vma->flags, vma_flags);
126
127 detach_free_vma(vma);
128 mtree_destroy(&mm.mm_mt);
129
130 return true;
131 }
132
test_simple_modify(void)133 static bool test_simple_modify(void)
134 {
135 struct vm_area_struct *vma;
136 vma_flags_t vma_flags = mk_vma_flags(VMA_READ_BIT, VMA_WRITE_BIT, VMA_MAYREAD_BIT,
137 VMA_MAYWRITE_BIT);
138 struct mm_struct mm = {};
139 struct vm_area_struct *init_vma = alloc_vma(&mm, 0, 0x3000, 0, vma_flags);
140 VMA_ITERATOR(vmi, &mm, 0x1000);
141
142 ASSERT_FALSE(attach_vma(&mm, init_vma));
143
144 /*
145 * The flags will not be changed, the vma_modify_flags() function
146 * performs the merge/split only.
147 */
148 vma = vma_modify_flags(&vmi, init_vma, init_vma,
149 0x1000, 0x2000, &vma_flags);
150 ASSERT_NE(vma, NULL);
151 /* We modify the provided VMA, and on split allocate new VMAs. */
152 ASSERT_EQ(vma, init_vma);
153
154 ASSERT_EQ(vma->vm_start, 0x1000);
155 ASSERT_EQ(vma->vm_end, 0x2000);
156 ASSERT_EQ(vma_start_pgoff(vma), 1);
157 ASSERT_EQ(vma_start_anon_pgoff(vma), 1);
158
159 /*
160 * Now walk through the three split VMAs and make sure they are as
161 * expected.
162 */
163
164 vma_iter_set(&vmi, 0);
165 vma = vma_iter_load(&vmi);
166
167 ASSERT_EQ(vma->vm_start, 0);
168 ASSERT_EQ(vma->vm_end, 0x1000);
169 ASSERT_EQ(vma_start_pgoff(vma), 0);
170 ASSERT_EQ(vma_start_anon_pgoff(vma), 0);
171
172 detach_free_vma(vma);
173 vma_iter_clear(&vmi);
174
175 vma = vma_next(&vmi);
176
177 ASSERT_EQ(vma->vm_start, 0x1000);
178 ASSERT_EQ(vma->vm_end, 0x2000);
179 ASSERT_EQ(vma_start_pgoff(vma), 1);
180 ASSERT_EQ(vma_start_anon_pgoff(vma), 1);
181
182 detach_free_vma(vma);
183 vma_iter_clear(&vmi);
184
185 vma = vma_next(&vmi);
186
187 ASSERT_EQ(vma->vm_start, 0x2000);
188 ASSERT_EQ(vma->vm_end, 0x3000);
189 ASSERT_EQ(vma_start_pgoff(vma), 2);
190 ASSERT_EQ(vma_start_anon_pgoff(vma), 2);
191
192 detach_free_vma(vma);
193 mtree_destroy(&mm.mm_mt);
194
195 return true;
196 }
197
test_simple_expand(void)198 static bool test_simple_expand(void)
199 {
200 vma_flags_t vma_flags = mk_vma_flags(VMA_READ_BIT, VMA_WRITE_BIT, VMA_MAYREAD_BIT,
201 VMA_MAYWRITE_BIT);
202 struct mm_struct mm = {};
203 struct vm_area_struct *vma = alloc_vma(&mm, 0, 0x1000, 0, vma_flags);
204 VMA_ITERATOR(vmi, &mm, 0);
205 struct vma_merge_struct vmg = {
206 .vmi = &vmi,
207 .target = vma,
208 .start = 0,
209 .end = 0x3000,
210 .pgoff = 0,
211 };
212
213 ASSERT_FALSE(attach_vma(&mm, vma));
214
215 ASSERT_FALSE(expand_existing(&vmg));
216
217 ASSERT_EQ(vma->vm_start, 0);
218 ASSERT_EQ(vma->vm_end, 0x3000);
219 ASSERT_EQ(vma_start_pgoff(vma), 0);
220 ASSERT_EQ(vma_start_anon_pgoff(vma), 0);
221
222 detach_free_vma(vma);
223 mtree_destroy(&mm.mm_mt);
224
225 return true;
226 }
227
test_simple_shrink(void)228 static bool test_simple_shrink(void)
229 {
230 vma_flags_t vma_flags = mk_vma_flags(VMA_READ_BIT, VMA_WRITE_BIT, VMA_MAYREAD_BIT,
231 VMA_MAYWRITE_BIT);
232 struct mm_struct mm = {};
233 struct vm_area_struct *vma = alloc_vma(&mm, 0, 0x3000, 0, vma_flags);
234 VMA_ITERATOR(vmi, &mm, 0);
235
236 ASSERT_FALSE(attach_vma(&mm, vma));
237
238 ASSERT_FALSE(vma_shrink(&vmi, vma, 0x1000));
239
240 ASSERT_EQ(vma->vm_start, 0);
241 ASSERT_EQ(vma->vm_end, 0x1000);
242 ASSERT_EQ(vma_start_pgoff(vma), 0);
243 ASSERT_EQ(vma_start_anon_pgoff(vma), 0);
244
245 detach_free_vma(vma);
246 mtree_destroy(&mm.mm_mt);
247
248 return true;
249 }
250
__test_merge_new(bool is_sticky,bool a_is_sticky,bool b_is_sticky,bool c_is_sticky)251 static bool __test_merge_new(bool is_sticky, bool a_is_sticky, bool b_is_sticky, bool c_is_sticky)
252 {
253 vma_flags_t vma_flags = mk_vma_flags(VMA_READ_BIT, VMA_WRITE_BIT,
254 VMA_MAYREAD_BIT, VMA_MAYWRITE_BIT);
255 struct mm_struct mm = {};
256 VMA_ITERATOR(vmi, &mm, 0);
257 struct vma_merge_struct vmg = {
258 .mm = &mm,
259 .vmi = &vmi,
260 };
261 struct anon_vma_chain dummy_anon_vma_chain_a = {
262 .anon_vma = &dummy_anon_vma,
263 };
264 struct anon_vma_chain dummy_anon_vma_chain_b = {
265 .anon_vma = &dummy_anon_vma,
266 };
267 struct anon_vma_chain dummy_anon_vma_chain_c = {
268 .anon_vma = &dummy_anon_vma,
269 };
270 struct anon_vma_chain dummy_anon_vma_chain_d = {
271 .anon_vma = &dummy_anon_vma,
272 };
273 const struct vm_operations_struct vm_ops = {
274 .close = dummy_close,
275 };
276 int count;
277 struct vm_area_struct *vma, *vma_a, *vma_b, *vma_c, *vma_d;
278 bool merged;
279
280 if (is_sticky)
281 vma_flags_set_mask(&vma_flags, VMA_STICKY_FLAGS);
282
283 /*
284 * 0123456789abc
285 * AA B CC
286 */
287 vma_a = alloc_and_link_vma(&mm, 0, 0x2000, 0, vma_flags);
288 ASSERT_NE(vma_a, NULL);
289 if (a_is_sticky)
290 vma_flags_set_mask(&vma_a->flags, VMA_STICKY_FLAGS);
291 /* We give each VMA a single avc so we can test anon_vma duplication. */
292 INIT_LIST_HEAD(&vma_a->anon_vma_chain);
293 list_add(&dummy_anon_vma_chain_a.same_vma, &vma_a->anon_vma_chain);
294
295 vma_b = alloc_and_link_vma(&mm, 0x3000, 0x4000, 3, vma_flags);
296 ASSERT_NE(vma_b, NULL);
297 if (b_is_sticky)
298 vma_flags_set_mask(&vma_b->flags, VMA_STICKY_FLAGS);
299 INIT_LIST_HEAD(&vma_b->anon_vma_chain);
300 list_add(&dummy_anon_vma_chain_b.same_vma, &vma_b->anon_vma_chain);
301
302 vma_c = alloc_and_link_vma(&mm, 0xb000, 0xc000, 0xb, vma_flags);
303 ASSERT_NE(vma_c, NULL);
304 if (c_is_sticky)
305 vma_flags_set_mask(&vma_c->flags, VMA_STICKY_FLAGS);
306 INIT_LIST_HEAD(&vma_c->anon_vma_chain);
307 list_add(&dummy_anon_vma_chain_c.same_vma, &vma_c->anon_vma_chain);
308
309 /*
310 * NO merge.
311 *
312 * 0123456789abc
313 * AA B ** CC
314 */
315 vma_d = try_merge_new_vma(&mm, &vmg, 0x7000, 0x9000, 7, vma_flags, &merged);
316 ASSERT_NE(vma_d, NULL);
317 INIT_LIST_HEAD(&vma_d->anon_vma_chain);
318 list_add(&dummy_anon_vma_chain_d.same_vma, &vma_d->anon_vma_chain);
319 ASSERT_FALSE(merged);
320 ASSERT_EQ(mm.map_count, 4);
321
322 /*
323 * Merge BOTH sides.
324 *
325 * 0123456789abc
326 * AA*B DD CC
327 */
328 vma_a->vm_ops = &vm_ops; /* This should have no impact. */
329 vma_b->anon_vma = &dummy_anon_vma;
330 vma = try_merge_new_vma(&mm, &vmg, 0x2000, 0x3000, 2, vma_flags, &merged);
331 ASSERT_EQ(vma, vma_a);
332 /* Merge with A, delete B. */
333 ASSERT_TRUE(merged);
334 ASSERT_EQ(vma->vm_start, 0);
335 ASSERT_EQ(vma->vm_end, 0x4000);
336 ASSERT_EQ(vma_start_pgoff(vma), 0);
337 ASSERT_EQ(vma->anon_vma, &dummy_anon_vma);
338 ASSERT_TRUE(vma_write_started(vma));
339 ASSERT_EQ(mm.map_count, 3);
340 if (is_sticky || a_is_sticky || b_is_sticky)
341 ASSERT_TRUE(vma_flags_test_any_mask(&vma->flags, VMA_STICKY_FLAGS));
342
343 /*
344 * Merge to PREVIOUS VMA.
345 *
346 * 0123456789abc
347 * AAAA* DD CC
348 */
349 vma = try_merge_new_vma(&mm, &vmg, 0x4000, 0x5000, 4, vma_flags, &merged);
350 ASSERT_EQ(vma, vma_a);
351 /* Extend A. */
352 ASSERT_TRUE(merged);
353 ASSERT_EQ(vma->vm_start, 0);
354 ASSERT_EQ(vma->vm_end, 0x5000);
355 ASSERT_EQ(vma_start_pgoff(vma), 0);
356 ASSERT_EQ(vma_start_anon_pgoff(vma), 0);
357 ASSERT_EQ(vma->anon_vma, &dummy_anon_vma);
358 ASSERT_TRUE(vma_write_started(vma));
359 ASSERT_EQ(mm.map_count, 3);
360 if (is_sticky || a_is_sticky)
361 ASSERT_TRUE(vma_flags_test_any_mask(&vma->flags, VMA_STICKY_FLAGS));
362
363 /*
364 * Merge to NEXT VMA.
365 *
366 * 0123456789abc
367 * AAAAA *DD CC
368 */
369 vma_d->anon_vma = &dummy_anon_vma;
370 vma_d->vm_ops = &vm_ops; /* This should have no impact. */
371 vma = try_merge_new_vma(&mm, &vmg, 0x6000, 0x7000, 6, vma_flags, &merged);
372 ASSERT_EQ(vma, vma_d);
373 /* Prepend. */
374 ASSERT_TRUE(merged);
375 ASSERT_EQ(vma->vm_start, 0x6000);
376 ASSERT_EQ(vma->vm_end, 0x9000);
377 ASSERT_EQ(vma_start_pgoff(vma), 6);
378 ASSERT_EQ(vma_start_anon_pgoff(vma), 6);
379 ASSERT_EQ(vma->anon_vma, &dummy_anon_vma);
380 ASSERT_TRUE(vma_write_started(vma));
381 ASSERT_EQ(mm.map_count, 3);
382 if (is_sticky) /* D uses is_sticky. */
383 ASSERT_TRUE(vma_flags_test_any_mask(&vma->flags, VMA_STICKY_FLAGS));
384
385 /*
386 * Merge BOTH sides.
387 *
388 * 0123456789abc
389 * AAAAA*DDD CC
390 */
391 vma_d->vm_ops = NULL; /* This would otherwise degrade the merge. */
392 vma = try_merge_new_vma(&mm, &vmg, 0x5000, 0x6000, 5, vma_flags, &merged);
393 ASSERT_EQ(vma, vma_a);
394 /* Merge with A, delete D. */
395 ASSERT_TRUE(merged);
396 ASSERT_EQ(vma->vm_start, 0);
397 ASSERT_EQ(vma->vm_end, 0x9000);
398 ASSERT_EQ(vma_start_pgoff(vma), 0);
399 ASSERT_EQ(vma_start_anon_pgoff(vma), 0);
400 ASSERT_EQ(vma->anon_vma, &dummy_anon_vma);
401 ASSERT_TRUE(vma_write_started(vma));
402 ASSERT_EQ(mm.map_count, 2);
403 if (is_sticky || a_is_sticky)
404 ASSERT_TRUE(vma_flags_test_any_mask(&vma->flags, VMA_STICKY_FLAGS));
405
406 /*
407 * Merge to NEXT VMA.
408 *
409 * 0123456789abc
410 * AAAAAAAAA *CC
411 */
412 vma_c->anon_vma = &dummy_anon_vma;
413 vma = try_merge_new_vma(&mm, &vmg, 0xa000, 0xb000, 0xa, vma_flags, &merged);
414 ASSERT_EQ(vma, vma_c);
415 /* Prepend C. */
416 ASSERT_TRUE(merged);
417 ASSERT_EQ(vma->vm_start, 0xa000);
418 ASSERT_EQ(vma->vm_end, 0xc000);
419 ASSERT_EQ(vma_start_pgoff(vma), 0xa);
420 ASSERT_EQ(vma_start_anon_pgoff(vma), 0xa);
421 ASSERT_EQ(vma->anon_vma, &dummy_anon_vma);
422 ASSERT_TRUE(vma_write_started(vma));
423 ASSERT_EQ(mm.map_count, 2);
424 if (is_sticky || c_is_sticky)
425 ASSERT_TRUE(vma_flags_test_any_mask(&vma->flags, VMA_STICKY_FLAGS));
426
427 /*
428 * Merge BOTH sides.
429 *
430 * 0123456789abc
431 * AAAAAAAAA*CCC
432 */
433 vma = try_merge_new_vma(&mm, &vmg, 0x9000, 0xa000, 0x9, vma_flags, &merged);
434 ASSERT_EQ(vma, vma_a);
435 /* Extend A and delete C. */
436 ASSERT_TRUE(merged);
437 ASSERT_EQ(vma->vm_start, 0);
438 ASSERT_EQ(vma->vm_end, 0xc000);
439 ASSERT_EQ(vma_start_pgoff(vma), 0);
440 ASSERT_EQ(vma_start_anon_pgoff(vma), 0);
441 ASSERT_EQ(vma->anon_vma, &dummy_anon_vma);
442 ASSERT_TRUE(vma_write_started(vma));
443 ASSERT_EQ(mm.map_count, 1);
444 if (is_sticky || a_is_sticky || c_is_sticky)
445 ASSERT_TRUE(vma_flags_test_any_mask(&vma->flags, VMA_STICKY_FLAGS));
446
447 /*
448 * Final state.
449 *
450 * 0123456789abc
451 * AAAAAAAAAAAAA
452 */
453
454 count = 0;
455 vma_iter_set(&vmi, 0);
456 for_each_vma(vmi, vma) {
457 ASSERT_NE(vma, NULL);
458 ASSERT_EQ(vma->vm_start, 0);
459 ASSERT_EQ(vma->vm_end, 0xc000);
460 ASSERT_EQ(vma_start_pgoff(vma), 0);
461 ASSERT_EQ(vma_start_anon_pgoff(vma), 0);
462 ASSERT_EQ(vma->anon_vma, &dummy_anon_vma);
463
464 detach_free_vma(vma);
465 count++;
466 }
467
468 /* Should only have one VMA left (though freed) after all is done.*/
469 ASSERT_EQ(count, 1);
470
471 mtree_destroy(&mm.mm_mt);
472 return true;
473 }
474
test_merge_new(void)475 static bool test_merge_new(void)
476 {
477 int i, j, k, l;
478
479 /* Generate every possible permutation of sticky flags. */
480 for (i = 0; i < 2; i++)
481 for (j = 0; j < 2; j++)
482 for (k = 0; k < 2; k++)
483 for (l = 0; l < 2; l++)
484 ASSERT_TRUE(__test_merge_new(i, j, k, l));
485
486 return true;
487 }
488
test_vma_merge_special_flags(void)489 static bool test_vma_merge_special_flags(void)
490 {
491 vma_flags_t vma_flags = mk_vma_flags(VMA_READ_BIT, VMA_WRITE_BIT,
492 VMA_MAYREAD_BIT, VMA_MAYWRITE_BIT);
493 struct mm_struct mm = {};
494 VMA_ITERATOR(vmi, &mm, 0);
495 struct vma_merge_struct vmg = {
496 .mm = &mm,
497 .vmi = &vmi,
498 };
499 vma_flag_t special_flags[] = { VMA_IO_BIT, VMA_DONTEXPAND_BIT,
500 VMA_PFNMAP_BIT, VMA_MIXEDMAP_BIT };
501 vma_flags_t all_special_flags = EMPTY_VMA_FLAGS;
502 int i;
503 struct vm_area_struct *vma_left, *vma;
504
505 /* Make sure there aren't new VM_SPECIAL flags. */
506 for (i = 0; i < ARRAY_SIZE(special_flags); i++)
507 vma_flags_set(&all_special_flags, special_flags[i]);
508 ASSERT_FLAGS_SAME_MASK(&all_special_flags, VMA_SPECIAL_FLAGS);
509
510 /*
511 * 01234
512 * AAA
513 */
514 vma_left = alloc_and_link_vma(&mm, 0, 0x3000, 0, vma_flags);
515 ASSERT_NE(vma_left, NULL);
516
517 /* 1. Set up new VMA with special flag that would otherwise merge. */
518
519 /*
520 * 01234
521 * AAA*
522 *
523 * This should merge if not for the VM_SPECIAL flag.
524 */
525 vmg_set_range(&vmg, 0x3000, 0x4000, 3, vma_flags);
526 for (i = 0; i < ARRAY_SIZE(special_flags); i++) {
527 vma_flag_t special_flag = special_flags[i];
528 vma_flags_t flags = vma_flags;
529
530 vma_flags_set(&flags, special_flag);
531 vma_left->flags = flags;
532 vmg.vma_flags = flags;
533 vma = merge_new(&vmg);
534 ASSERT_EQ(vma, NULL);
535 ASSERT_EQ(vmg.state, VMA_MERGE_NOMERGE);
536 }
537
538 /* 2. Modify VMA with special flag that would otherwise merge. */
539
540 /*
541 * 01234
542 * AAAB
543 *
544 * Create a VMA to modify.
545 */
546 vma = alloc_and_link_vma(&mm, 0x3000, 0x4000, 3, vma_flags);
547 ASSERT_NE(vma, NULL);
548 vmg.middle = vma;
549
550 for (i = 0; i < ARRAY_SIZE(special_flags); i++) {
551 vma_flag_t special_flag = special_flags[i];
552 vma_flags_t flags = vma_flags;
553
554 vma_flags_set(&flags, special_flag);
555 vma_left->flags = flags;
556 vmg.vma_flags = flags;
557 vma = merge_existing(&vmg);
558 ASSERT_EQ(vma, NULL);
559 ASSERT_EQ(vmg.state, VMA_MERGE_NOMERGE);
560 }
561
562 cleanup_mm(&mm, &vmi);
563 return true;
564 }
565
test_vma_merge_with_close(void)566 static bool test_vma_merge_with_close(void)
567 {
568 vma_flags_t vma_flags = mk_vma_flags(VMA_READ_BIT, VMA_WRITE_BIT,
569 VMA_MAYREAD_BIT, VMA_MAYWRITE_BIT);
570 struct mm_struct mm = {};
571 VMA_ITERATOR(vmi, &mm, 0);
572 struct vma_merge_struct vmg = {
573 .mm = &mm,
574 .vmi = &vmi,
575 };
576 const struct vm_operations_struct vm_ops = {
577 .close = dummy_close,
578 };
579 struct vm_area_struct *vma_prev, *vma_next, *vma;
580
581 /*
582 * When merging VMAs we are not permitted to remove any VMA that has a
583 * vm_ops->close() hook.
584 *
585 * Considering the two possible adjacent VMAs to which a VMA can be
586 * merged:
587 *
588 * [ prev ][ vma ][ next ]
589 *
590 * In no case will we need to delete prev. If the operation is
591 * mergeable, then prev will be extended with one or both of vma and
592 * next deleted.
593 *
594 * As a result, during initial mergeability checks, only
595 * can_vma_merge_before() (which implies the VMA being merged with is
596 * 'next' as shown above) bothers to check to see whether the next VMA
597 * has a vm_ops->close() callback that will need to be called when
598 * removed.
599 *
600 * If it does, then we cannot merge as the resources that the close()
601 * operation potentially clears down are tied only to the existing VMA
602 * range and we have no way of extending those to the nearly merged one.
603 *
604 * We must consider two scenarios:
605 *
606 * A.
607 *
608 * vm_ops->close: - - !NULL
609 * [ prev ][ vma ][ next ]
610 *
611 * Where prev may or may not be present/mergeable.
612 *
613 * This is picked up by a specific check in can_vma_merge_before().
614 *
615 * B.
616 *
617 * vm_ops->close: - !NULL
618 * [ prev ][ vma ]
619 *
620 * Where prev and vma are present and mergeable.
621 *
622 * This is picked up by a specific check in the modified VMA merge.
623 *
624 * IMPORTANT NOTE: We make the assumption that the following case:
625 *
626 * - !NULL NULL
627 * [ prev ][ vma ][ next ]
628 *
629 * Cannot occur, because vma->vm_ops being the same implies the same
630 * vma->vm_file, and therefore this would mean that next->vm_ops->close
631 * would be set too, and thus scenario A would pick this up.
632 */
633
634 /*
635 * The only case of a new VMA merge that results in a VMA being deleted
636 * is one where both the previous and next VMAs are merged - in this
637 * instance the next VMA is deleted, and the previous VMA is extended.
638 *
639 * If we are unable to do so, we reduce the operation to simply
640 * extending the prev VMA and not merging next.
641 *
642 * 0123456789
643 * PPP**NNNN
644 * ->
645 * 0123456789
646 * PPPPPPNNN
647 */
648
649 vma_prev = alloc_and_link_vma(&mm, 0, 0x3000, 0, vma_flags);
650 vma_next = alloc_and_link_vma(&mm, 0x5000, 0x9000, 5, vma_flags);
651 vma_next->vm_ops = &vm_ops;
652
653 vmg_set_range(&vmg, 0x3000, 0x5000, 3, vma_flags);
654 ASSERT_EQ(merge_new(&vmg), vma_prev);
655 ASSERT_EQ(vmg.state, VMA_MERGE_SUCCESS);
656 ASSERT_EQ(vma_prev->vm_start, 0);
657 ASSERT_EQ(vma_prev->vm_end, 0x5000);
658 ASSERT_EQ(vma_start_pgoff(vma_prev), 0);
659 ASSERT_EQ(vma_start_anon_pgoff(vma_prev), 0);
660
661 ASSERT_EQ(cleanup_mm(&mm, &vmi), 2);
662
663 /*
664 * When modifying an existing VMA there are further cases where we
665 * delete VMAs.
666 *
667 * <>
668 * 0123456789
669 * PPPVV
670 *
671 * In this instance, if vma has a close hook, the merge simply cannot
672 * proceed.
673 */
674
675 vma_prev = alloc_and_link_vma(&mm, 0, 0x3000, 0, vma_flags);
676 vma = alloc_and_link_vma(&mm, 0x3000, 0x5000, 3, vma_flags);
677 vma->vm_ops = &vm_ops;
678
679 vmg_set_range(&vmg, 0x3000, 0x5000, 3, vma_flags);
680 vmg.prev = vma_prev;
681 vmg.middle = vma;
682
683 /*
684 * The VMA being modified in a way that would otherwise merge should
685 * also fail.
686 */
687 ASSERT_EQ(merge_existing(&vmg), NULL);
688 ASSERT_EQ(vmg.state, VMA_MERGE_NOMERGE);
689
690 ASSERT_EQ(cleanup_mm(&mm, &vmi), 2);
691
692 /*
693 * This case is mirrored if merging with next.
694 *
695 * <>
696 * 0123456789
697 * VVNNNN
698 *
699 * In this instance, if vma has a close hook, the merge simply cannot
700 * proceed.
701 */
702
703 vma = alloc_and_link_vma(&mm, 0x3000, 0x5000, 3, vma_flags);
704 vma_next = alloc_and_link_vma(&mm, 0x5000, 0x9000, 5, vma_flags);
705 vma->vm_ops = &vm_ops;
706
707 vmg_set_range(&vmg, 0x3000, 0x5000, 3, vma_flags);
708 vmg.middle = vma;
709 ASSERT_EQ(merge_existing(&vmg), NULL);
710 /*
711 * Initially this is misapprehended as an out of memory report, as the
712 * close() check is handled in the same way as anon_vma duplication
713 * failures, however a subsequent patch resolves this.
714 */
715 ASSERT_EQ(vmg.state, VMA_MERGE_NOMERGE);
716
717 ASSERT_EQ(cleanup_mm(&mm, &vmi), 2);
718
719 /*
720 * Finally, we consider two variants of the case where we modify a VMA
721 * to merge with both the previous and next VMAs.
722 *
723 * The first variant is where vma has a close hook. In this instance, no
724 * merge can proceed.
725 *
726 * <>
727 * 0123456789
728 * PPPVVNNNN
729 */
730
731 vma_prev = alloc_and_link_vma(&mm, 0, 0x3000, 0, vma_flags);
732 vma = alloc_and_link_vma(&mm, 0x3000, 0x5000, 3, vma_flags);
733 vma_next = alloc_and_link_vma(&mm, 0x5000, 0x9000, 5, vma_flags);
734 vma->vm_ops = &vm_ops;
735
736 vmg_set_range(&vmg, 0x3000, 0x5000, 3, vma_flags);
737 vmg.prev = vma_prev;
738 vmg.middle = vma;
739
740 ASSERT_EQ(merge_existing(&vmg), NULL);
741 ASSERT_EQ(vmg.state, VMA_MERGE_NOMERGE);
742
743 ASSERT_EQ(cleanup_mm(&mm, &vmi), 3);
744
745 /*
746 * The second variant is where next has a close hook. In this instance,
747 * we reduce the operation to a merge between prev and vma.
748 *
749 * <>
750 * 0123456789
751 * PPPVVNNNN
752 * ->
753 * 0123456789
754 * PPPPPNNNN
755 */
756
757 vma_prev = alloc_and_link_vma(&mm, 0, 0x3000, 0, vma_flags);
758 vma = alloc_and_link_vma(&mm, 0x3000, 0x5000, 3, vma_flags);
759 vma_next = alloc_and_link_vma(&mm, 0x5000, 0x9000, 5, vma_flags);
760 vma_next->vm_ops = &vm_ops;
761
762 vmg_set_range(&vmg, 0x3000, 0x5000, 3, vma_flags);
763 vmg.prev = vma_prev;
764 vmg.middle = vma;
765
766 ASSERT_EQ(merge_existing(&vmg), vma_prev);
767 ASSERT_EQ(vmg.state, VMA_MERGE_SUCCESS);
768 ASSERT_EQ(vma_prev->vm_start, 0);
769 ASSERT_EQ(vma_prev->vm_end, 0x5000);
770 ASSERT_EQ(vma_start_pgoff(vma_prev), 0);
771 ASSERT_EQ(vma_start_anon_pgoff(vma_prev), 0);
772
773 ASSERT_EQ(cleanup_mm(&mm, &vmi), 2);
774
775 return true;
776 }
777
test_vma_merge_new_with_close(void)778 static bool test_vma_merge_new_with_close(void)
779 {
780 vma_flags_t vma_flags = mk_vma_flags(VMA_READ_BIT, VMA_WRITE_BIT,
781 VMA_MAYREAD_BIT, VMA_MAYWRITE_BIT);
782 struct mm_struct mm = {};
783 VMA_ITERATOR(vmi, &mm, 0);
784 struct vma_merge_struct vmg = {
785 .mm = &mm,
786 .vmi = &vmi,
787 };
788 struct vm_area_struct *vma_prev = alloc_and_link_vma(&mm, 0, 0x2000, 0, vma_flags);
789 struct vm_area_struct *vma_next = alloc_and_link_vma(&mm, 0x5000, 0x7000, 5, vma_flags);
790 const struct vm_operations_struct vm_ops = {
791 .close = dummy_close,
792 };
793 struct vm_area_struct *vma;
794
795 /*
796 * We should allow the partial merge of a proposed new VMA if the
797 * surrounding VMAs have vm_ops->close() hooks (but are otherwise
798 * compatible), e.g.:
799 *
800 * New VMA
801 * A v-------v B
802 * |-----| |-----|
803 * close close
804 *
805 * Since the rule is to not DELETE a VMA with a close operation, this
806 * should be permitted, only rather than expanding A and deleting B, we
807 * should simply expand A and leave B intact, e.g.:
808 *
809 * New VMA
810 * A B
811 * |------------||-----|
812 * close close
813 */
814
815 /* Have prev and next have a vm_ops->close() hook. */
816 vma_prev->vm_ops = &vm_ops;
817 vma_next->vm_ops = &vm_ops;
818
819 vmg_set_range(&vmg, 0x2000, 0x5000, 2, vma_flags);
820 vma = merge_new(&vmg);
821 ASSERT_NE(vma, NULL);
822 ASSERT_EQ(vmg.state, VMA_MERGE_SUCCESS);
823 ASSERT_EQ(vma->vm_start, 0);
824 ASSERT_EQ(vma->vm_end, 0x5000);
825 ASSERT_EQ(vma_start_pgoff(vma), 0);
826 ASSERT_EQ(vma_start_anon_pgoff(vma), 0);
827 ASSERT_EQ(vma->vm_ops, &vm_ops);
828 ASSERT_TRUE(vma_write_started(vma));
829 ASSERT_EQ(mm.map_count, 2);
830
831 cleanup_mm(&mm, &vmi);
832 return true;
833 }
834
__test_merge_existing(bool prev_is_sticky,bool middle_is_sticky,bool next_is_sticky)835 static bool __test_merge_existing(bool prev_is_sticky, bool middle_is_sticky, bool next_is_sticky)
836 {
837 vma_flags_t vma_flags = mk_vma_flags(VMA_READ_BIT, VMA_WRITE_BIT,
838 VMA_MAYREAD_BIT, VMA_MAYWRITE_BIT);
839 vma_flags_t prev_flags = vma_flags;
840 vma_flags_t next_flags = vma_flags;
841 struct mm_struct mm = {};
842 VMA_ITERATOR(vmi, &mm, 0);
843 struct vm_area_struct *vma, *vma_prev, *vma_next;
844 struct vma_merge_struct vmg = {
845 .mm = &mm,
846 .vmi = &vmi,
847 };
848 const struct vm_operations_struct vm_ops = {
849 .close = dummy_close,
850 };
851 struct anon_vma_chain avc = {};
852
853 if (prev_is_sticky)
854 vma_flags_set_mask(&prev_flags, VMA_STICKY_FLAGS);
855 if (middle_is_sticky)
856 vma_flags_set_mask(&vma_flags, VMA_STICKY_FLAGS);
857 if (next_is_sticky)
858 vma_flags_set_mask(&next_flags, VMA_STICKY_FLAGS);
859
860 /*
861 * Merge right case - partial span.
862 *
863 * <->
864 * 0123456789
865 * VVVVNNN
866 * ->
867 * 0123456789
868 * VNNNNNN
869 */
870 vma = alloc_and_link_vma(&mm, 0x2000, 0x6000, 2, vma_flags);
871 vma->vm_ops = &vm_ops; /* This should have no impact. */
872 vma_next = alloc_and_link_vma(&mm, 0x6000, 0x9000, 6, next_flags);
873 vma_next->vm_ops = &vm_ops; /* This should have no impact. */
874 vmg_set_range_anon_vma(&vmg, 0x3000, 0x6000, 3, vma_flags, &dummy_anon_vma);
875 vmg.middle = vma;
876 vmg.prev = vma;
877 vma_set_dummy_anon_vma(vma, &avc);
878 ASSERT_EQ(merge_existing(&vmg), vma_next);
879 ASSERT_EQ(vmg.state, VMA_MERGE_SUCCESS);
880 ASSERT_EQ(vma_next->vm_start, 0x3000);
881 ASSERT_EQ(vma_next->vm_end, 0x9000);
882 ASSERT_EQ(vma_start_pgoff(vma_next), 3);
883 ASSERT_EQ(vma_start_anon_pgoff(vma_next), 3);
884 ASSERT_EQ(vma_next->anon_vma, &dummy_anon_vma);
885 ASSERT_EQ(vma->vm_start, 0x2000);
886 ASSERT_EQ(vma->vm_end, 0x3000);
887 ASSERT_EQ(vma_start_pgoff(vma), 2);
888 ASSERT_EQ(vma_start_anon_pgoff(vma), 2);
889 ASSERT_TRUE(vma_write_started(vma));
890 ASSERT_TRUE(vma_write_started(vma_next));
891 ASSERT_EQ(mm.map_count, 2);
892 if (middle_is_sticky || next_is_sticky)
893 ASSERT_TRUE(vma_flags_test_any_mask(&vma_next->flags, VMA_STICKY_FLAGS));
894
895 /* Clear down and reset. */
896 ASSERT_EQ(cleanup_mm(&mm, &vmi), 2);
897
898 /*
899 * Merge right case - full span.
900 *
901 * <-->
902 * 0123456789
903 * VVVVNNN
904 * ->
905 * 0123456789
906 * NNNNNNN
907 */
908 vma = alloc_and_link_vma(&mm, 0x2000, 0x6000, 2, vma_flags);
909 vma_next = alloc_and_link_vma(&mm, 0x6000, 0x9000, 6, next_flags);
910 vma_next->vm_ops = &vm_ops; /* This should have no impact. */
911 vmg_set_range_anon_vma(&vmg, 0x2000, 0x6000, 2, vma_flags, &dummy_anon_vma);
912 vmg.middle = vma;
913 vma_set_dummy_anon_vma(vma, &avc);
914 ASSERT_EQ(merge_existing(&vmg), vma_next);
915 ASSERT_EQ(vmg.state, VMA_MERGE_SUCCESS);
916 ASSERT_EQ(vma_next->vm_start, 0x2000);
917 ASSERT_EQ(vma_next->vm_end, 0x9000);
918 ASSERT_EQ(vma_start_pgoff(vma_next), 2);
919 ASSERT_EQ(vma_start_anon_pgoff(vma_next), 2);
920 ASSERT_EQ(vma_next->anon_vma, &dummy_anon_vma);
921 ASSERT_TRUE(vma_write_started(vma_next));
922 ASSERT_EQ(mm.map_count, 1);
923 if (middle_is_sticky || next_is_sticky)
924 ASSERT_TRUE(vma_flags_test_any_mask(&vma_next->flags, VMA_STICKY_FLAGS));
925
926 /* Clear down and reset. We should have deleted vma. */
927 ASSERT_EQ(cleanup_mm(&mm, &vmi), 1);
928
929 /*
930 * Merge left case - partial span.
931 *
932 * <->
933 * 0123456789
934 * PPPVVVV
935 * ->
936 * 0123456789
937 * PPPPPPV
938 */
939 vma_prev = alloc_and_link_vma(&mm, 0, 0x3000, 0, prev_flags);
940 vma_prev->vm_ops = &vm_ops; /* This should have no impact. */
941 vma = alloc_and_link_vma(&mm, 0x3000, 0x7000, 3, vma_flags);
942 vma->vm_ops = &vm_ops; /* This should have no impact. */
943 vmg_set_range_anon_vma(&vmg, 0x3000, 0x6000, 3, vma_flags, &dummy_anon_vma);
944 vmg.prev = vma_prev;
945 vmg.middle = vma;
946 vma_set_dummy_anon_vma(vma, &avc);
947 ASSERT_EQ(merge_existing(&vmg), vma_prev);
948 ASSERT_EQ(vmg.state, VMA_MERGE_SUCCESS);
949 ASSERT_EQ(vma_prev->vm_start, 0);
950 ASSERT_EQ(vma_prev->vm_end, 0x6000);
951 ASSERT_EQ(vma_start_pgoff(vma_prev), 0);
952 ASSERT_EQ(vma_start_anon_pgoff(vma_prev), 0);
953 ASSERT_EQ(vma_prev->anon_vma, &dummy_anon_vma);
954 ASSERT_EQ(vma->vm_start, 0x6000);
955 ASSERT_EQ(vma->vm_end, 0x7000);
956 ASSERT_EQ(vma_start_pgoff(vma), 6);
957 ASSERT_EQ(vma_start_anon_pgoff(vma), 6);
958 ASSERT_TRUE(vma_write_started(vma_prev));
959 ASSERT_TRUE(vma_write_started(vma));
960 ASSERT_EQ(mm.map_count, 2);
961 if (prev_is_sticky || middle_is_sticky)
962 ASSERT_TRUE(vma_flags_test_any_mask(&vma_prev->flags, VMA_STICKY_FLAGS));
963
964 /* Clear down and reset. */
965 ASSERT_EQ(cleanup_mm(&mm, &vmi), 2);
966
967 /*
968 * Merge left case - full span.
969 *
970 * <-->
971 * 0123456789
972 * PPPVVVV
973 * ->
974 * 0123456789
975 * PPPPPPP
976 */
977 vma_prev = alloc_and_link_vma(&mm, 0, 0x3000, 0, prev_flags);
978 vma_prev->vm_ops = &vm_ops; /* This should have no impact. */
979 vma = alloc_and_link_vma(&mm, 0x3000, 0x7000, 3, vma_flags);
980 vmg_set_range_anon_vma(&vmg, 0x3000, 0x7000, 3, vma_flags, &dummy_anon_vma);
981 vmg.prev = vma_prev;
982 vmg.middle = vma;
983 vma_set_dummy_anon_vma(vma, &avc);
984 ASSERT_EQ(merge_existing(&vmg), vma_prev);
985 ASSERT_EQ(vmg.state, VMA_MERGE_SUCCESS);
986 ASSERT_EQ(vma_prev->vm_start, 0);
987 ASSERT_EQ(vma_prev->vm_end, 0x7000);
988 ASSERT_EQ(vma_start_pgoff(vma_prev), 0);
989 ASSERT_EQ(vma_start_anon_pgoff(vma_prev), 0);
990 ASSERT_EQ(vma_prev->anon_vma, &dummy_anon_vma);
991 ASSERT_TRUE(vma_write_started(vma_prev));
992 ASSERT_EQ(mm.map_count, 1);
993 if (prev_is_sticky || middle_is_sticky)
994 ASSERT_TRUE(vma_flags_test_any_mask(&vma_prev->flags, VMA_STICKY_FLAGS));
995
996 /* Clear down and reset. We should have deleted vma. */
997 ASSERT_EQ(cleanup_mm(&mm, &vmi), 1);
998
999 /*
1000 * Merge both case.
1001 *
1002 * <-->
1003 * 0123456789
1004 * PPPVVVVNNN
1005 * ->
1006 * 0123456789
1007 * PPPPPPPPPP
1008 */
1009 vma_prev = alloc_and_link_vma(&mm, 0, 0x3000, 0, prev_flags);
1010 vma_prev->vm_ops = &vm_ops; /* This should have no impact. */
1011 vma = alloc_and_link_vma(&mm, 0x3000, 0x7000, 3, vma_flags);
1012 vma_next = alloc_and_link_vma(&mm, 0x7000, 0x9000, 7, next_flags);
1013 vmg_set_range_anon_vma(&vmg, 0x3000, 0x7000, 3, vma_flags, &dummy_anon_vma);
1014 vmg.prev = vma_prev;
1015 vmg.middle = vma;
1016 vma_set_dummy_anon_vma(vma, &avc);
1017 ASSERT_EQ(merge_existing(&vmg), vma_prev);
1018 ASSERT_EQ(vmg.state, VMA_MERGE_SUCCESS);
1019 ASSERT_EQ(vma_prev->vm_start, 0);
1020 ASSERT_EQ(vma_prev->vm_end, 0x9000);
1021 ASSERT_EQ(vma_start_pgoff(vma_prev), 0);
1022 ASSERT_EQ(vma_start_anon_pgoff(vma_prev), 0);
1023 ASSERT_EQ(vma_prev->anon_vma, &dummy_anon_vma);
1024 ASSERT_TRUE(vma_write_started(vma_prev));
1025 ASSERT_EQ(mm.map_count, 1);
1026 if (prev_is_sticky || middle_is_sticky || next_is_sticky)
1027 ASSERT_TRUE(vma_flags_test_any_mask(&vma_prev->flags, VMA_STICKY_FLAGS));
1028
1029 /* Clear down and reset. We should have deleted prev and next. */
1030 ASSERT_EQ(cleanup_mm(&mm, &vmi), 1);
1031
1032 /*
1033 * Non-merge ranges. the modified VMA merge operation assumes that the
1034 * caller always specifies ranges within the input VMA so we need only
1035 * examine these cases.
1036 *
1037 * -
1038 * -
1039 * -
1040 * <->
1041 * <>
1042 * <>
1043 * 0123456789a
1044 * PPPVVVVVNNN
1045 */
1046
1047 vma_prev = alloc_and_link_vma(&mm, 0, 0x3000, 0, prev_flags);
1048 vma = alloc_and_link_vma(&mm, 0x3000, 0x8000, 3, vma_flags);
1049 vma_next = alloc_and_link_vma(&mm, 0x8000, 0xa000, 8, next_flags);
1050
1051 vmg_set_range(&vmg, 0x4000, 0x5000, 4, vma_flags);
1052 vmg.prev = vma;
1053 vmg.middle = vma;
1054 ASSERT_EQ(merge_existing(&vmg), NULL);
1055 ASSERT_EQ(vmg.state, VMA_MERGE_NOMERGE);
1056
1057 vmg_set_range(&vmg, 0x5000, 0x6000, 5, vma_flags);
1058 vmg.prev = vma;
1059 vmg.middle = vma;
1060 ASSERT_EQ(merge_existing(&vmg), NULL);
1061 ASSERT_EQ(vmg.state, VMA_MERGE_NOMERGE);
1062
1063 vmg_set_range(&vmg, 0x6000, 0x7000, 6, vma_flags);
1064 vmg.prev = vma;
1065 vmg.middle = vma;
1066 ASSERT_EQ(merge_existing(&vmg), NULL);
1067 ASSERT_EQ(vmg.state, VMA_MERGE_NOMERGE);
1068
1069 vmg_set_range(&vmg, 0x4000, 0x7000, 4, vma_flags);
1070 vmg.prev = vma;
1071 vmg.middle = vma;
1072 ASSERT_EQ(merge_existing(&vmg), NULL);
1073 ASSERT_EQ(vmg.state, VMA_MERGE_NOMERGE);
1074
1075 vmg_set_range(&vmg, 0x4000, 0x6000, 4, vma_flags);
1076 vmg.prev = vma;
1077 vmg.middle = vma;
1078 ASSERT_EQ(merge_existing(&vmg), NULL);
1079 ASSERT_EQ(vmg.state, VMA_MERGE_NOMERGE);
1080
1081 vmg_set_range(&vmg, 0x5000, 0x6000, 5, vma_flags);
1082 vmg.prev = vma;
1083 vmg.middle = vma;
1084 ASSERT_EQ(merge_existing(&vmg), NULL);
1085 ASSERT_EQ(vmg.state, VMA_MERGE_NOMERGE);
1086
1087 ASSERT_EQ(cleanup_mm(&mm, &vmi), 3);
1088
1089 return true;
1090 }
1091
test_merge_existing(void)1092 static bool test_merge_existing(void)
1093 {
1094 int i, j, k;
1095
1096 /* Generate every possible permutation of sticky flags. */
1097 for (i = 0; i < 2; i++)
1098 for (j = 0; j < 2; j++)
1099 for (k = 0; k < 2; k++)
1100 ASSERT_TRUE(__test_merge_existing(i, j, k));
1101
1102 return true;
1103 }
1104
test_anon_vma_non_mergeable(void)1105 static bool test_anon_vma_non_mergeable(void)
1106 {
1107 vma_flags_t vma_flags = mk_vma_flags(VMA_READ_BIT, VMA_WRITE_BIT,
1108 VMA_MAYREAD_BIT, VMA_MAYWRITE_BIT);
1109 struct mm_struct mm = {};
1110 VMA_ITERATOR(vmi, &mm, 0);
1111 struct vm_area_struct *vma, *vma_prev, *vma_next;
1112 struct vma_merge_struct vmg = {
1113 .mm = &mm,
1114 .vmi = &vmi,
1115 };
1116 struct anon_vma_chain dummy_anon_vma_chain_1 = {};
1117 struct anon_vma_chain dummy_anon_vma_chain_2 = {};
1118 struct anon_vma dummy_anon_vma_2;
1119
1120 /*
1121 * In the case of modified VMA merge, merging both left and right VMAs
1122 * but where prev and next have incompatible anon_vma objects, we revert
1123 * to a merge of prev and VMA:
1124 *
1125 * <-->
1126 * 0123456789
1127 * PPPVVVVNNN
1128 * ->
1129 * 0123456789
1130 * PPPPPPPNNN
1131 */
1132 vma_prev = alloc_and_link_vma(&mm, 0, 0x3000, 0, vma_flags);
1133 vma = alloc_and_link_vma(&mm, 0x3000, 0x7000, 3, vma_flags);
1134 vma_next = alloc_and_link_vma(&mm, 0x7000, 0x9000, 7, vma_flags);
1135
1136 /*
1137 * Give both prev and next single anon_vma_chain fields, so they will
1138 * merge with the NULL vmg->anon_vma.
1139 *
1140 * However, when prev is compared to next, the merge should fail.
1141 */
1142 vmg_set_range_anon_vma(&vmg, 0x3000, 0x7000, 3, vma_flags, NULL);
1143 vmg.prev = vma_prev;
1144 vmg.middle = vma;
1145 vma_set_dummy_anon_vma(vma_prev, &dummy_anon_vma_chain_1);
1146 __vma_set_dummy_anon_vma(vma_next, &dummy_anon_vma_chain_2, &dummy_anon_vma_2);
1147
1148 ASSERT_EQ(merge_existing(&vmg), vma_prev);
1149 ASSERT_EQ(vmg.state, VMA_MERGE_SUCCESS);
1150 ASSERT_EQ(vma_prev->vm_start, 0);
1151 ASSERT_EQ(vma_prev->vm_end, 0x7000);
1152 ASSERT_EQ(vma_start_pgoff(vma_prev), 0);
1153 ASSERT_EQ(vma_start_anon_pgoff(vma_prev), 0);
1154 ASSERT_TRUE(vma_write_started(vma_prev));
1155 ASSERT_FALSE(vma_write_started(vma_next));
1156
1157 /* Clear down and reset. */
1158 ASSERT_EQ(cleanup_mm(&mm, &vmi), 2);
1159
1160 /*
1161 * Now consider the new VMA case. This is equivalent, only adding a new
1162 * VMA in a gap between prev and next.
1163 *
1164 * <-->
1165 * 0123456789
1166 * PPP****NNN
1167 * ->
1168 * 0123456789
1169 * PPPPPPPNNN
1170 */
1171 vma_prev = alloc_and_link_vma(&mm, 0, 0x3000, 0, vma_flags);
1172 vma_next = alloc_and_link_vma(&mm, 0x7000, 0x9000, 7, vma_flags);
1173
1174 vmg_set_range_anon_vma(&vmg, 0x3000, 0x7000, 3, vma_flags, NULL);
1175 vmg.prev = vma_prev;
1176 vma_set_dummy_anon_vma(vma_prev, &dummy_anon_vma_chain_1);
1177 __vma_set_dummy_anon_vma(vma_next, &dummy_anon_vma_chain_2, &dummy_anon_vma_2);
1178
1179 vmg.anon_vma = NULL;
1180 ASSERT_EQ(merge_new(&vmg), vma_prev);
1181 ASSERT_EQ(vmg.state, VMA_MERGE_SUCCESS);
1182 ASSERT_EQ(vma_prev->vm_start, 0);
1183 ASSERT_EQ(vma_prev->vm_end, 0x7000);
1184 ASSERT_EQ(vma_start_pgoff(vma_prev), 0);
1185 ASSERT_EQ(vma_start_anon_pgoff(vma_prev), 0);
1186 ASSERT_TRUE(vma_write_started(vma_prev));
1187 ASSERT_FALSE(vma_write_started(vma_next));
1188
1189 /* Final cleanup. */
1190 ASSERT_EQ(cleanup_mm(&mm, &vmi), 2);
1191
1192 return true;
1193 }
1194
test_dup_anon_vma(void)1195 static bool test_dup_anon_vma(void)
1196 {
1197 vma_flags_t vma_flags = mk_vma_flags(VMA_READ_BIT, VMA_WRITE_BIT,
1198 VMA_MAYREAD_BIT, VMA_MAYWRITE_BIT);
1199 struct mm_struct mm = {};
1200 VMA_ITERATOR(vmi, &mm, 0);
1201 struct vma_merge_struct vmg = {
1202 .mm = &mm,
1203 .vmi = &vmi,
1204 };
1205 struct anon_vma_chain dummy_anon_vma_chain = {
1206 .anon_vma = &dummy_anon_vma,
1207 };
1208 struct vm_area_struct *vma_prev, *vma_next, *vma;
1209
1210 reset_dummy_anon_vma();
1211
1212 /*
1213 * Expanding a VMA delete the next one duplicates next's anon_vma and
1214 * assigns it to the expanded VMA.
1215 *
1216 * This covers new VMA merging, as these operations amount to a VMA
1217 * expand.
1218 */
1219 vma_prev = alloc_and_link_vma(&mm, 0, 0x3000, 0, vma_flags);
1220 vma_next = alloc_and_link_vma(&mm, 0x3000, 0x5000, 3, vma_flags);
1221 vma_next->anon_vma = &dummy_anon_vma;
1222
1223 vmg_set_range(&vmg, 0, 0x5000, 0, vma_flags);
1224 vmg.target = vma_prev;
1225 vmg.next = vma_next;
1226
1227 ASSERT_EQ(expand_existing(&vmg), 0);
1228
1229 /* Will have been cloned. */
1230 ASSERT_EQ(vma_prev->anon_vma, &dummy_anon_vma);
1231 ASSERT_TRUE(vma_prev->anon_vma->was_cloned);
1232
1233 /* Cleanup ready for next run. */
1234 cleanup_mm(&mm, &vmi);
1235
1236 /*
1237 * next has anon_vma, we assign to prev.
1238 *
1239 * |<----->|
1240 * |-------*********-------|
1241 * prev vma next
1242 * extend delete delete
1243 */
1244
1245 vma_prev = alloc_and_link_vma(&mm, 0, 0x3000, 0, vma_flags);
1246 vma = alloc_and_link_vma(&mm, 0x3000, 0x5000, 3, vma_flags);
1247 vma_next = alloc_and_link_vma(&mm, 0x5000, 0x8000, 5, vma_flags);
1248
1249 /* Initialise avc so mergeability check passes. */
1250 INIT_LIST_HEAD(&vma_next->anon_vma_chain);
1251 list_add(&dummy_anon_vma_chain.same_vma, &vma_next->anon_vma_chain);
1252
1253 vma_next->anon_vma = &dummy_anon_vma;
1254 vmg_set_range(&vmg, 0x3000, 0x5000, 3, vma_flags);
1255 vmg.prev = vma_prev;
1256 vmg.middle = vma;
1257
1258 ASSERT_EQ(merge_existing(&vmg), vma_prev);
1259 ASSERT_EQ(vmg.state, VMA_MERGE_SUCCESS);
1260
1261 ASSERT_EQ(vma_prev->vm_start, 0);
1262 ASSERT_EQ(vma_prev->vm_end, 0x8000);
1263
1264 ASSERT_EQ(vma_prev->anon_vma, &dummy_anon_vma);
1265 ASSERT_TRUE(vma_prev->anon_vma->was_cloned);
1266
1267 cleanup_mm(&mm, &vmi);
1268
1269 /*
1270 * vma has anon_vma, we assign to prev.
1271 *
1272 * |<----->|
1273 * |-------*********-------|
1274 * prev vma next
1275 * extend delete delete
1276 */
1277
1278 vma_prev = alloc_and_link_vma(&mm, 0, 0x3000, 0, vma_flags);
1279 vma = alloc_and_link_vma(&mm, 0x3000, 0x5000, 3, vma_flags);
1280 vma_next = alloc_and_link_vma(&mm, 0x5000, 0x8000, 5, vma_flags);
1281 vmg.anon_vma = &dummy_anon_vma;
1282 vma_set_dummy_anon_vma(vma, &dummy_anon_vma_chain);
1283 vmg_set_range(&vmg, 0x3000, 0x5000, 3, vma_flags);
1284 vmg.prev = vma_prev;
1285 vmg.middle = vma;
1286
1287 ASSERT_EQ(merge_existing(&vmg), vma_prev);
1288 ASSERT_EQ(vmg.state, VMA_MERGE_SUCCESS);
1289
1290 ASSERT_EQ(vma_prev->vm_start, 0);
1291 ASSERT_EQ(vma_prev->vm_end, 0x8000);
1292
1293 ASSERT_EQ(vma_prev->anon_vma, &dummy_anon_vma);
1294 ASSERT_TRUE(vma_prev->anon_vma->was_cloned);
1295
1296 cleanup_mm(&mm, &vmi);
1297
1298 /*
1299 * vma has anon_vma, we assign to prev.
1300 *
1301 * |<----->|
1302 * |-------*************
1303 * prev vma
1304 * extend shrink/delete
1305 */
1306
1307 vma_prev = alloc_and_link_vma(&mm, 0, 0x3000, 0, vma_flags);
1308 vma = alloc_and_link_vma(&mm, 0x3000, 0x8000, 3, vma_flags);
1309
1310 vma_set_dummy_anon_vma(vma, &dummy_anon_vma_chain);
1311 vmg_set_range(&vmg, 0x3000, 0x5000, 3, vma_flags);
1312 vmg.prev = vma_prev;
1313 vmg.middle = vma;
1314
1315 ASSERT_EQ(merge_existing(&vmg), vma_prev);
1316 ASSERT_EQ(vmg.state, VMA_MERGE_SUCCESS);
1317
1318 ASSERT_EQ(vma_prev->vm_start, 0);
1319 ASSERT_EQ(vma_prev->vm_end, 0x5000);
1320
1321 ASSERT_EQ(vma_prev->anon_vma, &dummy_anon_vma);
1322 ASSERT_TRUE(vma_prev->anon_vma->was_cloned);
1323
1324 cleanup_mm(&mm, &vmi);
1325
1326 /*
1327 * vma has anon_vma, we assign to next.
1328 *
1329 * |<----->|
1330 * *************-------|
1331 * vma next
1332 * shrink/delete extend
1333 */
1334
1335 vma = alloc_and_link_vma(&mm, 0, 0x5000, 0, vma_flags);
1336 vma_next = alloc_and_link_vma(&mm, 0x5000, 0x8000, 5, vma_flags);
1337
1338 vma_set_dummy_anon_vma(vma, &dummy_anon_vma_chain);
1339 vmg_set_range(&vmg, 0x3000, 0x5000, 3, vma_flags);
1340 vmg.prev = vma;
1341 vmg.middle = vma;
1342
1343 ASSERT_EQ(merge_existing(&vmg), vma_next);
1344 ASSERT_EQ(vmg.state, VMA_MERGE_SUCCESS);
1345
1346 ASSERT_EQ(vma_next->vm_start, 0x3000);
1347 ASSERT_EQ(vma_next->vm_end, 0x8000);
1348
1349 ASSERT_EQ(vma_next->anon_vma, &dummy_anon_vma);
1350 ASSERT_TRUE(vma_next->anon_vma->was_cloned);
1351
1352 cleanup_mm(&mm, &vmi);
1353 return true;
1354 }
1355
test_vmi_prealloc_fail(void)1356 static bool test_vmi_prealloc_fail(void)
1357 {
1358 vma_flags_t vma_flags = mk_vma_flags(VMA_READ_BIT, VMA_WRITE_BIT,
1359 VMA_MAYREAD_BIT, VMA_MAYWRITE_BIT);
1360 struct mm_struct mm = {};
1361 VMA_ITERATOR(vmi, &mm, 0);
1362 struct vma_merge_struct vmg = {
1363 .mm = &mm,
1364 .vmi = &vmi,
1365 };
1366 struct anon_vma_chain avc = {};
1367 struct vm_area_struct *vma_prev, *vma;
1368
1369 /*
1370 * We are merging vma into prev, with vma possessing an anon_vma, which
1371 * will be duplicated. We cause the vmi preallocation to fail and assert
1372 * the duplicated anon_vma is unlinked.
1373 */
1374
1375 vma_prev = alloc_and_link_vma(&mm, 0, 0x3000, 0, vma_flags);
1376 vma = alloc_and_link_vma(&mm, 0x3000, 0x5000, 3, vma_flags);
1377 vma->anon_vma = &dummy_anon_vma;
1378
1379 vmg_set_range_anon_vma(&vmg, 0x3000, 0x5000, 3, vma_flags, &dummy_anon_vma);
1380 vmg.prev = vma_prev;
1381 vmg.middle = vma;
1382 vma_set_dummy_anon_vma(vma, &avc);
1383
1384 fail_prealloc = true;
1385
1386 /* This will cause the merge to fail. */
1387 ASSERT_EQ(merge_existing(&vmg), NULL);
1388 ASSERT_EQ(vmg.state, VMA_MERGE_ERROR_NOMEM);
1389 /* We will already have assigned the anon_vma. */
1390 ASSERT_EQ(vma_prev->anon_vma, &dummy_anon_vma);
1391 /* And it was both cloned and unlinked. */
1392 ASSERT_TRUE(dummy_anon_vma.was_cloned);
1393 ASSERT_TRUE(dummy_anon_vma.was_unlinked);
1394
1395 cleanup_mm(&mm, &vmi); /* Resets fail_prealloc too. */
1396
1397 /*
1398 * We repeat the same operation for expanding a VMA, which is what new
1399 * VMA merging ultimately uses too. This asserts that unlinking is
1400 * performed in this case too.
1401 */
1402
1403 vma_prev = alloc_and_link_vma(&mm, 0, 0x3000, 0, vma_flags);
1404 vma = alloc_and_link_vma(&mm, 0x3000, 0x5000, 3, vma_flags);
1405 vma->anon_vma = &dummy_anon_vma;
1406
1407 vmg_set_range(&vmg, 0, 0x5000, 3, vma_flags);
1408 vmg.target = vma_prev;
1409 vmg.next = vma;
1410
1411 fail_prealloc = true;
1412 ASSERT_EQ(expand_existing(&vmg), -ENOMEM);
1413 ASSERT_EQ(vmg.state, VMA_MERGE_ERROR_NOMEM);
1414
1415 ASSERT_EQ(vma_prev->anon_vma, &dummy_anon_vma);
1416 ASSERT_TRUE(dummy_anon_vma.was_cloned);
1417 ASSERT_TRUE(dummy_anon_vma.was_unlinked);
1418
1419 cleanup_mm(&mm, &vmi);
1420 return true;
1421 }
1422
test_merge_extend(void)1423 static bool test_merge_extend(void)
1424 {
1425 vma_flags_t vma_flags = mk_vma_flags(VMA_READ_BIT, VMA_WRITE_BIT,
1426 VMA_MAYREAD_BIT, VMA_MAYWRITE_BIT);
1427 struct mm_struct mm = {};
1428 VMA_ITERATOR(vmi, &mm, 0x1000);
1429 struct vm_area_struct *vma;
1430
1431 vma = alloc_and_link_vma(&mm, 0, 0x1000, 0, vma_flags);
1432 alloc_and_link_vma(&mm, 0x3000, 0x4000, 3, vma_flags);
1433
1434 /*
1435 * Extend a VMA into the gap between itself and the following VMA.
1436 * This should result in a merge.
1437 *
1438 * <->
1439 * * *
1440 *
1441 */
1442
1443 ASSERT_EQ(vma_merge_extend(&vmi, vma, 0x2000), vma);
1444 ASSERT_EQ(vma->vm_start, 0);
1445 ASSERT_EQ(vma->vm_end, 0x4000);
1446 ASSERT_EQ(vma_start_pgoff(vma), 0);
1447 ASSERT_EQ(vma_start_anon_pgoff(vma), 0);
1448 ASSERT_TRUE(vma_write_started(vma));
1449 ASSERT_EQ(mm.map_count, 1);
1450
1451 cleanup_mm(&mm, &vmi);
1452 return true;
1453 }
1454
test_expand_only_mode(void)1455 static bool test_expand_only_mode(void)
1456 {
1457 vma_flags_t vma_flags = mk_vma_flags(VMA_READ_BIT, VMA_WRITE_BIT,
1458 VMA_MAYREAD_BIT, VMA_MAYWRITE_BIT);
1459 struct mm_struct mm = {};
1460 VMA_ITERATOR(vmi, &mm, 0);
1461 struct vm_area_struct *vma_prev, *vma;
1462 VMG_STATE(vmg, &mm, &vmi, 0x5000, 0x9000, vma_flags, 5, 5);
1463
1464 /*
1465 * Place a VMA prior to the one we're expanding so we assert that we do
1466 * not erroneously try to traverse to the previous VMA even though we
1467 * have, through the use of the just_expand flag, indicated we do not
1468 * need to do so.
1469 */
1470 alloc_and_link_vma(&mm, 0, 0x2000, 0, vma_flags);
1471
1472 /*
1473 * We will be positioned at the prev VMA, but looking to expand to
1474 * 0x9000.
1475 */
1476 vma_iter_set(&vmi, 0x3000);
1477 vma_prev = alloc_and_link_vma(&mm, 0x3000, 0x5000, 3, vma_flags);
1478 vmg.prev = vma_prev;
1479 vmg.just_expand = true;
1480
1481 vma = vma_merge_new_range(&vmg);
1482 ASSERT_NE(vma, NULL);
1483 ASSERT_EQ(vma, vma_prev);
1484 ASSERT_EQ(vmg.state, VMA_MERGE_SUCCESS);
1485 ASSERT_EQ(vma->vm_start, 0x3000);
1486 ASSERT_EQ(vma->vm_end, 0x9000);
1487 ASSERT_EQ(vma_start_pgoff(vma), 3);
1488 ASSERT_EQ(vma_start_anon_pgoff(vma), 3);
1489 ASSERT_TRUE(vma_write_started(vma));
1490 ASSERT_EQ(vma_iter_addr(&vmi), 0x3000);
1491 vma_assert_attached(vma);
1492
1493 cleanup_mm(&mm, &vmi);
1494 return true;
1495 }
1496
run_merge_tests(int * num_tests,int * num_fail)1497 static void run_merge_tests(int *num_tests, int *num_fail)
1498 {
1499 /* Very simple tests to kick the tyres. */
1500 TEST(simple_merge);
1501 TEST(simple_modify);
1502 TEST(simple_expand);
1503 TEST(simple_shrink);
1504
1505 TEST(merge_new);
1506 TEST(vma_merge_special_flags);
1507 TEST(vma_merge_with_close);
1508 TEST(vma_merge_new_with_close);
1509 TEST(merge_existing);
1510 TEST(anon_vma_non_mergeable);
1511 TEST(dup_anon_vma);
1512 TEST(vmi_prealloc_fail);
1513 TEST(merge_extend);
1514 TEST(expand_only_mode);
1515 }
1516