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 	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 {
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(&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 
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++) {
122 		buffers[i] = binder_alloc_new_buf(alloc, sizes[i], 0, 0, 0, 0);
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[],
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, 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(&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 
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 
176 static 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(&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 
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,
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, i))
217 			continue;
218 		seq[index] = i;
219 		binder_selftest_free_seq(alloc, sizes, seq, index + 1, end);
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 	 */
243 	back_sizes[0] += alloc->buffer_size - end_offset[BUFFER_NUM - 1];
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);
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 
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 + 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  */
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 }
303