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 
27 static bool binder_selftest_run = true;
28 static int binder_selftest_failures;
29 static 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  */
40 enum 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 
87 static 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 
101 static 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 
124 static 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 
141 static 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 
165 static 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 
185 static 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 
202 static 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. */
214 static 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 
232 static 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 
258 static 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  */
292 void 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 
309 done:
310 	mutex_unlock(&binder_selftest_lock);
311 }
312