Commit | Line | Data |
---|---|---|
9c92ab61 | 1 | // SPDX-License-Identifier: GPL-2.0-only |
4175e2b4 SY |
2 | /* binder_alloc_selftest.c |
3 | * | |
4 | * Android IPC Subsystem | |
5 | * | |
6 | * Copyright (C) 2017 Google, Inc. | |
4175e2b4 SY |
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 | ||
18 | static bool binder_selftest_run = true; | |
19 | static int binder_selftest_failures; | |
20 | static 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 | */ | |
31 | enum 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 | ||
78 | static 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 | ||
92 | static bool check_buffer_pages_allocated(struct binder_alloc *alloc, | |
93 | struct binder_buffer *buffer, | |
94 | size_t size) | |
95 | { | |
36f30937 TK |
96 | void __user *page_addr; |
97 | void __user *end; | |
4175e2b4 SY |
98 | int page_index; |
99 | ||
36f30937 | 100 | end = (void __user *)PAGE_ALIGN((uintptr_t)buffer->user_data + size); |
bde4a19f | 101 | page_addr = buffer->user_data; |
74310e06 | 102 | for (; page_addr < end; page_addr += PAGE_SIZE) { |
4175e2b4 | 103 | page_index = (page_addr - alloc->buffer) / PAGE_SIZE; |
f2517eb7 SY |
104 | if (!alloc->pages[page_index].page_ptr || |
105 | !list_empty(&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); | |
4175e2b4 SY |
109 | return false; |
110 | } | |
111 | } | |
112 | return true; | |
113 | } | |
114 | ||
115 | static 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++) { | |
261e7818 | 122 | buffers[i] = binder_alloc_new_buf(alloc, sizes[i], 0, 0, 0, 0); |
4175e2b4 SY |
123 | if (IS_ERR(buffers[i]) || |
124 | !check_buffer_pages_allocated(alloc, buffers[i], | |
125 | sizes[i])) { | |
126 | pr_err_size_seq(sizes, seq); | |
127 | binder_selftest_failures++; | |
128 | } | |
129 | } | |
130 | } | |
131 | ||
132 | static void binder_selftest_free_buf(struct binder_alloc *alloc, | |
133 | struct binder_buffer *buffers[], | |
f2517eb7 | 134 | size_t *sizes, int *seq, size_t end) |
4175e2b4 SY |
135 | { |
136 | int i; | |
137 | ||
138 | for (i = 0; i < BUFFER_NUM; i++) | |
139 | binder_alloc_free_buf(alloc, buffers[seq[i]]); | |
140 | ||
f2517eb7 SY |
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(&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 | ||
156 | static void binder_selftest_free_page(struct binder_alloc *alloc) | |
157 | { | |
158 | int i; | |
159 | unsigned long count; | |
160 | ||
161 | while ((count = list_lru_count(&binder_alloc_lru))) { | |
162 | list_lru_walk(&binder_alloc_lru, binder_alloc_free_page, | |
163 | NULL, count); | |
164 | } | |
165 | ||
4175e2b4 | 166 | for (i = 0; i < (alloc->buffer_size / PAGE_SIZE); i++) { |
f2517eb7 SY |
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); | |
4175e2b4 SY |
171 | binder_selftest_failures++; |
172 | } | |
173 | } | |
174 | } | |
175 | ||
176 | static void binder_selftest_alloc_free(struct binder_alloc *alloc, | |
f2517eb7 | 177 | size_t *sizes, int *seq, size_t end) |
4175e2b4 SY |
178 | { |
179 | struct binder_buffer *buffers[BUFFER_NUM]; | |
180 | ||
181 | binder_selftest_alloc_buf(alloc, buffers, sizes, seq); | |
f2517eb7 SY |
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(&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); | |
4175e2b4 SY |
191 | } |
192 | ||
193 | static 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. */ | |
205 | static void binder_selftest_free_seq(struct binder_alloc *alloc, | |
f2517eb7 SY |
206 | size_t *sizes, int *seq, |
207 | int index, size_t end) | |
4175e2b4 SY |
208 | { |
209 | int i; | |
210 | ||
211 | if (index == BUFFER_NUM) { | |
f2517eb7 | 212 | binder_selftest_alloc_free(alloc, sizes, seq, end); |
4175e2b4 SY |
213 | return; |
214 | } | |
215 | for (i = 0; i < BUFFER_NUM; i++) { | |
216 | if (is_dup(seq, index, i)) | |
217 | continue; | |
218 | seq[index] = i; | |
f2517eb7 | 219 | binder_selftest_free_seq(alloc, sizes, seq, index + 1, end); |
4175e2b4 SY |
220 | } |
221 | } | |
222 | ||
223 | static 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 | */ | |
74310e06 | 243 | back_sizes[0] += alloc->buffer_size - end_offset[BUFFER_NUM - 1]; |
f2517eb7 SY |
244 | binder_selftest_free_seq(alloc, front_sizes, seq, 0, |
245 | end_offset[BUFFER_NUM - 1]); | |
246 | binder_selftest_free_seq(alloc, back_sizes, seq, 0, alloc->buffer_size); | |
4175e2b4 SY |
247 | } |
248 | ||
249 | static 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 | ||
74310e06 | 262 | BUILD_BUG_ON(BUFFER_MIN_SIZE * BUFFER_NUM >= PAGE_SIZE); |
4175e2b4 SY |
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 + 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 | |
f2517eb7 SY |
280 | * correctly allocated, put onto lru when buffers are freed, and |
281 | * are freed when binder_alloc_free_page is called. | |
4175e2b4 SY |
282 | */ |
283 | void 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, 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 | ||
300 | done: | |
301 | mutex_unlock(&binder_selftest_lock); | |
302 | } |