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