1// SPDX-License-Identifier: GPL-2.0-only
2/* binder_alloc_selftest.c
3 *
4 * Android IPC Subsystem
5 *
6 * Copyright (C) 2017 Google, Inc.
7 */
8
9#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
10
11#include <linux/mm_types.h>
12#include <linux/err.h>
13#include "binder_alloc.h"
14
15#define BUFFER_NUM 5
16#define BUFFER_MIN_SIZE (PAGE_SIZE / 8)
17
18static bool binder_selftest_run = true;
19static int binder_selftest_failures;
20static DEFINE_MUTEX(binder_selftest_lock);
21
22/**
23 * enum buf_end_align_type - Page alignment of a buffer
24 * end with regard to the end of the previous buffer.
25 *
26 * In the pictures below, buf2 refers to the buffer we
27 * are aligning. buf1 refers to previous buffer by addr.
28 * Symbol [ means the start of a buffer, ] means the end
29 * of a buffer, and | means page boundaries.
30 */
31enum buf_end_align_type {
32 /**
33 * @SAME_PAGE_UNALIGNED: The end of this buffer is on
34 * the same page as the end of the previous buffer and
35 * is not page aligned. Examples:
36 * buf1 ][ buf2 ][ ...
37 * buf1 ]|[ buf2 ][ ...
38 */
39 SAME_PAGE_UNALIGNED = 0,
40 /**
41 * @SAME_PAGE_ALIGNED: When the end of the previous buffer
42 * is not page aligned, the end of this buffer is on the
43 * same page as the end of the previous buffer and is page
44 * aligned. When the previous buffer is page aligned, the
45 * end of this buffer is aligned to the next page boundary.
46 * Examples:
47 * buf1 ][ buf2 ]| ...
48 * buf1 ]|[ buf2 ]| ...
49 */
50 SAME_PAGE_ALIGNED,
51 /**
52 * @NEXT_PAGE_UNALIGNED: The end of this buffer is on
53 * the page next to the end of the previous buffer and
54 * is not page aligned. Examples:
55 * buf1 ][ buf2 | buf2 ][ ...
56 * buf1 ]|[ buf2 | buf2 ][ ...
57 */
58 NEXT_PAGE_UNALIGNED,
59 /**
60 * @NEXT_PAGE_ALIGNED: The end of this buffer is on
61 * the page next to the end of the previous buffer and
62 * is page aligned. Examples:
63 * buf1 ][ buf2 | buf2 ]| ...
64 * buf1 ]|[ buf2 | buf2 ]| ...
65 */
66 NEXT_PAGE_ALIGNED,
67 /**
68 * @NEXT_NEXT_UNALIGNED: The end of this buffer is on
69 * the page that follows the page after the end of the
70 * previous buffer and is not page aligned. Examples:
71 * buf1 ][ buf2 | buf2 | buf2 ][ ...
72 * buf1 ]|[ buf2 | buf2 | buf2 ][ ...
73 */
74 NEXT_NEXT_UNALIGNED,
75 LOOP_END,
76};
77
78static void pr_err_size_seq(size_t *sizes, int *seq)
79{
80 int i;
81
82 pr_err("alloc sizes: ");
83 for (i = 0; i < BUFFER_NUM; i++)
84 pr_cont("[%zu]", sizes[i]);
85 pr_cont("\n");
86 pr_err("free seq: ");
87 for (i = 0; i < BUFFER_NUM; i++)
88 pr_cont("[%d]", seq[i]);
89 pr_cont("\n");
90}
91
92static bool check_buffer_pages_allocated(struct binder_alloc *alloc,
93 struct binder_buffer *buffer,
94 size_t size)
95{
96 void __user *page_addr;
97 void __user *end;
98 int page_index;
99
100 end = (void __user *)PAGE_ALIGN((uintptr_t)buffer->user_data + size);
101 page_addr = buffer->user_data;
102 for (; page_addr < end; page_addr += PAGE_SIZE) {
103 page_index = (page_addr - alloc->buffer) / PAGE_SIZE;
104 if (!alloc->pages[page_index].page_ptr ||
105 !list_empty(head: &alloc->pages[page_index].lru)) {
106 pr_err("expect alloc but is %s at page index %d\n",
107 alloc->pages[page_index].page_ptr ?
108 "lru" : "free", page_index);
109 return false;
110 }
111 }
112 return true;
113}
114
115static void binder_selftest_alloc_buf(struct binder_alloc *alloc,
116 struct binder_buffer *buffers[],
117 size_t *sizes, int *seq)
118{
119 int i;
120
121 for (i = 0; i < BUFFER_NUM; i++) {
122 buffers[i] = binder_alloc_new_buf(alloc, data_size: sizes[i], offsets_size: 0, extra_buffers_size: 0, is_async: 0, pid: 0);
123 if (IS_ERR(ptr: buffers[i]) ||
124 !check_buffer_pages_allocated(alloc, buffer: buffers[i],
125 size: sizes[i])) {
126 pr_err_size_seq(sizes, seq);
127 binder_selftest_failures++;
128 }
129 }
130}
131
132static void binder_selftest_free_buf(struct binder_alloc *alloc,
133 struct binder_buffer *buffers[],
134 size_t *sizes, int *seq, size_t end)
135{
136 int i;
137
138 for (i = 0; i < BUFFER_NUM; i++)
139 binder_alloc_free_buf(alloc, buffer: buffers[seq[i]]);
140
141 for (i = 0; i < end / PAGE_SIZE; i++) {
142 /**
143 * Error message on a free page can be false positive
144 * if binder shrinker ran during binder_alloc_free_buf
145 * calls above.
146 */
147 if (list_empty(head: &alloc->pages[i].lru)) {
148 pr_err_size_seq(sizes, seq);
149 pr_err("expect lru but is %s at page index %d\n",
150 alloc->pages[i].page_ptr ? "alloc" : "free", i);
151 binder_selftest_failures++;
152 }
153 }
154}
155
156static void binder_selftest_free_page(struct binder_alloc *alloc)
157{
158 int i;
159 unsigned long count;
160
161 while ((count = list_lru_count(lru: &binder_alloc_lru))) {
162 list_lru_walk(lru: &binder_alloc_lru, isolate: binder_alloc_free_page,
163 NULL, nr_to_walk: count);
164 }
165
166 for (i = 0; i < (alloc->buffer_size / PAGE_SIZE); i++) {
167 if (alloc->pages[i].page_ptr) {
168 pr_err("expect free but is %s at page index %d\n",
169 list_empty(&alloc->pages[i].lru) ?
170 "alloc" : "lru", i);
171 binder_selftest_failures++;
172 }
173 }
174}
175
176static void binder_selftest_alloc_free(struct binder_alloc *alloc,
177 size_t *sizes, int *seq, size_t end)
178{
179 struct binder_buffer *buffers[BUFFER_NUM];
180
181 binder_selftest_alloc_buf(alloc, buffers, sizes, seq);
182 binder_selftest_free_buf(alloc, buffers, sizes, seq, end);
183
184 /* Allocate from lru. */
185 binder_selftest_alloc_buf(alloc, buffers, sizes, seq);
186 if (list_lru_count(lru: &binder_alloc_lru))
187 pr_err("lru list should be empty but is not\n");
188
189 binder_selftest_free_buf(alloc, buffers, sizes, seq, end);
190 binder_selftest_free_page(alloc);
191}
192
193static bool is_dup(int *seq, int index, int val)
194{
195 int i;
196
197 for (i = 0; i < index; i++) {
198 if (seq[i] == val)
199 return true;
200 }
201 return false;
202}
203
204/* Generate BUFFER_NUM factorial free orders. */
205static void binder_selftest_free_seq(struct binder_alloc *alloc,
206 size_t *sizes, int *seq,
207 int index, size_t end)
208{
209 int i;
210
211 if (index == BUFFER_NUM) {
212 binder_selftest_alloc_free(alloc, sizes, seq, end);
213 return;
214 }
215 for (i = 0; i < BUFFER_NUM; i++) {
216 if (is_dup(seq, index, val: i))
217 continue;
218 seq[index] = i;
219 binder_selftest_free_seq(alloc, sizes, seq, index: index + 1, end);
220 }
221}
222
223static void binder_selftest_alloc_size(struct binder_alloc *alloc,
224 size_t *end_offset)
225{
226 int i;
227 int seq[BUFFER_NUM] = {0};
228 size_t front_sizes[BUFFER_NUM];
229 size_t back_sizes[BUFFER_NUM];
230 size_t last_offset, offset = 0;
231
232 for (i = 0; i < BUFFER_NUM; i++) {
233 last_offset = offset;
234 offset = end_offset[i];
235 front_sizes[i] = offset - last_offset;
236 back_sizes[BUFFER_NUM - i - 1] = front_sizes[i];
237 }
238 /*
239 * Buffers share the first or last few pages.
240 * Only BUFFER_NUM - 1 buffer sizes are adjustable since
241 * we need one giant buffer before getting to the last page.
242 */
243 back_sizes[0] += alloc->buffer_size - end_offset[BUFFER_NUM - 1];
244 binder_selftest_free_seq(alloc, sizes: front_sizes, seq, index: 0,
245 end: end_offset[BUFFER_NUM - 1]);
246 binder_selftest_free_seq(alloc, sizes: back_sizes, seq, index: 0, end: alloc->buffer_size);
247}
248
249static void binder_selftest_alloc_offset(struct binder_alloc *alloc,
250 size_t *end_offset, int index)
251{
252 int align;
253 size_t end, prev;
254
255 if (index == BUFFER_NUM) {
256 binder_selftest_alloc_size(alloc, end_offset);
257 return;
258 }
259 prev = index == 0 ? 0 : end_offset[index - 1];
260 end = prev;
261
262 BUILD_BUG_ON(BUFFER_MIN_SIZE * BUFFER_NUM >= PAGE_SIZE);
263
264 for (align = SAME_PAGE_UNALIGNED; align < LOOP_END; align++) {
265 if (align % 2)
266 end = ALIGN(end, PAGE_SIZE);
267 else
268 end += BUFFER_MIN_SIZE;
269 end_offset[index] = end;
270 binder_selftest_alloc_offset(alloc, end_offset, index: index + 1);
271 }
272}
273
274/**
275 * binder_selftest_alloc() - Test alloc and free of buffer pages.
276 * @alloc: Pointer to alloc struct.
277 *
278 * Allocate BUFFER_NUM buffers to cover all page alignment cases,
279 * then free them in all orders possible. Check that pages are
280 * correctly allocated, put onto lru when buffers are freed, and
281 * are freed when binder_alloc_free_page is called.
282 */
283void binder_selftest_alloc(struct binder_alloc *alloc)
284{
285 size_t end_offset[BUFFER_NUM];
286
287 if (!binder_selftest_run)
288 return;
289 mutex_lock(&binder_selftest_lock);
290 if (!binder_selftest_run || !alloc->vma)
291 goto done;
292 pr_info("STARTED\n");
293 binder_selftest_alloc_offset(alloc, end_offset, index: 0);
294 binder_selftest_run = false;
295 if (binder_selftest_failures > 0)
296 pr_info("%d tests FAILED\n", binder_selftest_failures);
297 else
298 pr_info("PASSED\n");
299
300done:
301 mutex_unlock(lock: &binder_selftest_lock);
302}
303

source code of linux/drivers/android/binder_alloc_selftest.c