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