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 | |
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 | /** |
76 | * @LOOP_END: The number of enum values in &buf_end_align_type. |
77 | * It is used for controlling loop termination. |
78 | */ |
79 | LOOP_END, |
80 | }; |
81 | |
82 | static void pr_err_size_seq(size_t *sizes, int *seq) |
83 | { |
84 | int i; |
85 | |
86 | pr_err("alloc sizes: " ); |
87 | for (i = 0; i < BUFFER_NUM; i++) |
88 | pr_cont("[%zu]" , sizes[i]); |
89 | pr_cont("\n" ); |
90 | pr_err("free seq: " ); |
91 | for (i = 0; i < BUFFER_NUM; i++) |
92 | pr_cont("[%d]" , seq[i]); |
93 | pr_cont("\n" ); |
94 | } |
95 | |
96 | static bool check_buffer_pages_allocated(struct binder_alloc *alloc, |
97 | struct binder_buffer *buffer, |
98 | size_t size) |
99 | { |
100 | unsigned long page_addr; |
101 | unsigned long end; |
102 | int page_index; |
103 | |
104 | end = PAGE_ALIGN(buffer->user_data + size); |
105 | page_addr = buffer->user_data; |
106 | for (; page_addr < end; page_addr += PAGE_SIZE) { |
107 | page_index = (page_addr - alloc->buffer) / PAGE_SIZE; |
108 | if (!alloc->pages[page_index].page_ptr || |
109 | !list_empty(head: &alloc->pages[page_index].lru)) { |
110 | pr_err("expect alloc but is %s at page index %d\n" , |
111 | alloc->pages[page_index].page_ptr ? |
112 | "lru" : "free" , page_index); |
113 | return false; |
114 | } |
115 | } |
116 | return true; |
117 | } |
118 | |
119 | static void binder_selftest_alloc_buf(struct binder_alloc *alloc, |
120 | struct binder_buffer *buffers[], |
121 | size_t *sizes, int *seq) |
122 | { |
123 | int i; |
124 | |
125 | for (i = 0; i < BUFFER_NUM; i++) { |
126 | buffers[i] = binder_alloc_new_buf(alloc, data_size: sizes[i], offsets_size: 0, extra_buffers_size: 0, is_async: 0); |
127 | if (IS_ERR(ptr: buffers[i]) || |
128 | !check_buffer_pages_allocated(alloc, buffer: buffers[i], |
129 | size: sizes[i])) { |
130 | pr_err_size_seq(sizes, seq); |
131 | binder_selftest_failures++; |
132 | } |
133 | } |
134 | } |
135 | |
136 | static void binder_selftest_free_buf(struct binder_alloc *alloc, |
137 | struct binder_buffer *buffers[], |
138 | size_t *sizes, int *seq, size_t end) |
139 | { |
140 | int i; |
141 | |
142 | for (i = 0; i < BUFFER_NUM; i++) |
143 | binder_alloc_free_buf(alloc, buffer: buffers[seq[i]]); |
144 | |
145 | for (i = 0; i < end / PAGE_SIZE; i++) { |
146 | /** |
147 | * Error message on a free page can be false positive |
148 | * if binder shrinker ran during binder_alloc_free_buf |
149 | * calls above. |
150 | */ |
151 | if (list_empty(head: &alloc->pages[i].lru)) { |
152 | pr_err_size_seq(sizes, seq); |
153 | pr_err("expect lru but is %s at page index %d\n" , |
154 | alloc->pages[i].page_ptr ? "alloc" : "free" , i); |
155 | binder_selftest_failures++; |
156 | } |
157 | } |
158 | } |
159 | |
160 | static void binder_selftest_free_page(struct binder_alloc *alloc) |
161 | { |
162 | int i; |
163 | unsigned long count; |
164 | |
165 | while ((count = list_lru_count(lru: &binder_freelist))) { |
166 | list_lru_walk(lru: &binder_freelist, isolate: binder_alloc_free_page, |
167 | NULL, nr_to_walk: count); |
168 | } |
169 | |
170 | for (i = 0; i < (alloc->buffer_size / PAGE_SIZE); i++) { |
171 | if (alloc->pages[i].page_ptr) { |
172 | pr_err("expect free but is %s at page index %d\n" , |
173 | list_empty(&alloc->pages[i].lru) ? |
174 | "alloc" : "lru" , i); |
175 | binder_selftest_failures++; |
176 | } |
177 | } |
178 | } |
179 | |
180 | static void binder_selftest_alloc_free(struct binder_alloc *alloc, |
181 | size_t *sizes, int *seq, size_t end) |
182 | { |
183 | struct binder_buffer *buffers[BUFFER_NUM]; |
184 | |
185 | binder_selftest_alloc_buf(alloc, buffers, sizes, seq); |
186 | binder_selftest_free_buf(alloc, buffers, sizes, seq, end); |
187 | |
188 | /* Allocate from lru. */ |
189 | binder_selftest_alloc_buf(alloc, buffers, sizes, seq); |
190 | if (list_lru_count(lru: &binder_freelist)) |
191 | pr_err("lru list should be empty but is not\n" ); |
192 | |
193 | binder_selftest_free_buf(alloc, buffers, sizes, seq, end); |
194 | binder_selftest_free_page(alloc); |
195 | } |
196 | |
197 | static bool is_dup(int *seq, int index, int val) |
198 | { |
199 | int i; |
200 | |
201 | for (i = 0; i < index; i++) { |
202 | if (seq[i] == val) |
203 | return true; |
204 | } |
205 | return false; |
206 | } |
207 | |
208 | /* Generate BUFFER_NUM factorial free orders. */ |
209 | static void binder_selftest_free_seq(struct binder_alloc *alloc, |
210 | size_t *sizes, int *seq, |
211 | int index, size_t end) |
212 | { |
213 | int i; |
214 | |
215 | if (index == BUFFER_NUM) { |
216 | binder_selftest_alloc_free(alloc, sizes, seq, end); |
217 | return; |
218 | } |
219 | for (i = 0; i < BUFFER_NUM; i++) { |
220 | if (is_dup(seq, index, val: i)) |
221 | continue; |
222 | seq[index] = i; |
223 | binder_selftest_free_seq(alloc, sizes, seq, index: index + 1, end); |
224 | } |
225 | } |
226 | |
227 | static void binder_selftest_alloc_size(struct binder_alloc *alloc, |
228 | size_t *end_offset) |
229 | { |
230 | int i; |
231 | int seq[BUFFER_NUM] = {0}; |
232 | size_t front_sizes[BUFFER_NUM]; |
233 | size_t back_sizes[BUFFER_NUM]; |
234 | size_t last_offset, offset = 0; |
235 | |
236 | for (i = 0; i < BUFFER_NUM; i++) { |
237 | last_offset = offset; |
238 | offset = end_offset[i]; |
239 | front_sizes[i] = offset - last_offset; |
240 | back_sizes[BUFFER_NUM - i - 1] = front_sizes[i]; |
241 | } |
242 | /* |
243 | * Buffers share the first or last few pages. |
244 | * Only BUFFER_NUM - 1 buffer sizes are adjustable since |
245 | * we need one giant buffer before getting to the last page. |
246 | */ |
247 | back_sizes[0] += alloc->buffer_size - end_offset[BUFFER_NUM - 1]; |
248 | binder_selftest_free_seq(alloc, sizes: front_sizes, seq, index: 0, |
249 | end: end_offset[BUFFER_NUM - 1]); |
250 | binder_selftest_free_seq(alloc, sizes: back_sizes, seq, index: 0, end: alloc->buffer_size); |
251 | } |
252 | |
253 | static void binder_selftest_alloc_offset(struct binder_alloc *alloc, |
254 | size_t *end_offset, int index) |
255 | { |
256 | int align; |
257 | size_t end, prev; |
258 | |
259 | if (index == BUFFER_NUM) { |
260 | binder_selftest_alloc_size(alloc, end_offset); |
261 | return; |
262 | } |
263 | prev = index == 0 ? 0 : end_offset[index - 1]; |
264 | end = prev; |
265 | |
266 | BUILD_BUG_ON(BUFFER_MIN_SIZE * BUFFER_NUM >= PAGE_SIZE); |
267 | |
268 | for (align = SAME_PAGE_UNALIGNED; align < LOOP_END; align++) { |
269 | if (align % 2) |
270 | end = ALIGN(end, PAGE_SIZE); |
271 | else |
272 | end += BUFFER_MIN_SIZE; |
273 | end_offset[index] = end; |
274 | binder_selftest_alloc_offset(alloc, end_offset, index: index + 1); |
275 | } |
276 | } |
277 | |
278 | /** |
279 | * binder_selftest_alloc() - Test alloc and free of buffer pages. |
280 | * @alloc: Pointer to alloc struct. |
281 | * |
282 | * Allocate BUFFER_NUM buffers to cover all page alignment cases, |
283 | * then free them in all orders possible. Check that pages are |
284 | * correctly allocated, put onto lru when buffers are freed, and |
285 | * are freed when binder_alloc_free_page is called. |
286 | */ |
287 | void binder_selftest_alloc(struct binder_alloc *alloc) |
288 | { |
289 | size_t end_offset[BUFFER_NUM]; |
290 | |
291 | if (!binder_selftest_run) |
292 | return; |
293 | mutex_lock(&binder_selftest_lock); |
294 | if (!binder_selftest_run || !alloc->vma) |
295 | goto done; |
296 | pr_info("STARTED\n" ); |
297 | binder_selftest_alloc_offset(alloc, end_offset, index: 0); |
298 | binder_selftest_run = false; |
299 | if (binder_selftest_failures > 0) |
300 | pr_info("%d tests FAILED\n" , binder_selftest_failures); |
301 | else |
302 | pr_info("PASSED\n" ); |
303 | |
304 | done: |
305 | mutex_unlock(lock: &binder_selftest_lock); |
306 | } |
307 | |