/* binder_alloc_selftest.c * * Android IPC Subsystem * * Copyright (C) 2017 Google, Inc. * * This software is licensed under the terms of the GNU General Public * License version 2, as published by the Free Software Foundation, and * may be copied, distributed, and modified under those terms. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * */ #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt #include <linux/mm_types.h> #include <linux/err.h> #include "binder_alloc.h" #define BUFFER_NUM 5 #define BUFFER_MIN_SIZE (PAGE_SIZE / 8) static bool binder_selftest_run = true; static int binder_selftest_failures; static DEFINE_MUTEX(binder_selftest_lock); /** * enum buf_end_align_type - Page alignment of a buffer * end with regard to the end of the previous buffer. * * In the pictures below, buf2 refers to the buffer we * are aligning. buf1 refers to previous buffer by addr. * Symbol [ means the start of a buffer, ] means the end * of a buffer, and | means page boundaries. */ enum buf_end_align_type { /** * @SAME_PAGE_UNALIGNED: The end of this buffer is on * the same page as the end of the previous buffer and * is not page aligned. Examples: * buf1 ][ buf2 ][ ... * buf1 ]|[ buf2 ][ ... */ SAME_PAGE_UNALIGNED = 0, /** * @SAME_PAGE_ALIGNED: When the end of the previous buffer * is not page aligned, the end of this buffer is on the * same page as the end of the previous buffer and is page * aligned. When the previous buffer is page aligned, the * end of this buffer is aligned to the next page boundary. * Examples: * buf1 ][ buf2 ]| ... * buf1 ]|[ buf2 ]| ... */ SAME_PAGE_ALIGNED, /** * @NEXT_PAGE_UNALIGNED: The end of this buffer is on * the page next to the end of the previous buffer and * is not page aligned. Examples: * buf1 ][ buf2 | buf2 ][ ... * buf1 ]|[ buf2 | buf2 ][ ... */ NEXT_PAGE_UNALIGNED, /** * @NEXT_PAGE_ALIGNED: The end of this buffer is on * the page next to the end of the previous buffer and * is page aligned. Examples: * buf1 ][ buf2 | buf2 ]| ... * buf1 ]|[ buf2 | buf2 ]| ... */ NEXT_PAGE_ALIGNED, /** * @NEXT_NEXT_UNALIGNED: The end of this buffer is on * the page that follows the page after the end of the * previous buffer and is not page aligned. Examples: * buf1 ][ buf2 | buf2 | buf2 ][ ... * buf1 ]|[ buf2 | buf2 | buf2 ][ ... */ NEXT_NEXT_UNALIGNED, LOOP_END, }; static void pr_err_size_seq(size_t *sizes, int *seq) { int i; pr_err("alloc sizes: "); for (i = 0; i < BUFFER_NUM; i++) pr_cont("[%zu]", sizes[i]); pr_cont("\n"); pr_err("free seq: "); for (i = 0; i < BUFFER_NUM; i++) pr_cont("[%d]", seq[i]); pr_cont("\n"); } static bool check_buffer_pages_allocated(struct binder_alloc *alloc, struct binder_buffer *buffer, size_t size) { void *page_addr, *end; int page_index; end = (void *)PAGE_ALIGN((uintptr_t)buffer->data + size); page_addr = buffer->data; for (; page_addr < end; page_addr += PAGE_SIZE) { page_index = (page_addr - alloc->buffer) / PAGE_SIZE; if (!alloc->pages[page_index].page_ptr || !list_empty(&alloc->pages[page_index].lru)) { pr_err("expect alloc but is %s at page index %d\n", alloc->pages[page_index].page_ptr ? "lru" : "free", page_index); return false; } } return true; } static void binder_selftest_alloc_buf(struct binder_alloc *alloc, struct binder_buffer *buffers[], size_t *sizes, int *seq) { int i; for (i = 0; i < BUFFER_NUM; i++) { buffers[i] = binder_alloc_new_buf(alloc, sizes[i], 0, 0, 0); if (IS_ERR(buffers[i]) || !check_buffer_pages_allocated(alloc, buffers[i], sizes[i])) { pr_err_size_seq(sizes, seq); binder_selftest_failures++; } } } static void binder_selftest_free_buf(struct binder_alloc *alloc, struct binder_buffer *buffers[], size_t *sizes, int *seq, size_t end) { int i; for (i = 0; i < BUFFER_NUM; i++) binder_alloc_free_buf(alloc, buffers[seq[i]]); for (i = 0; i < end / PAGE_SIZE; i++) { /** * Error message on a free page can be false positive * if binder shrinker ran during binder_alloc_free_buf * calls above. */ if (list_empty(&alloc->pages[i].lru)) { pr_err_size_seq(sizes, seq); pr_err("expect lru but is %s at page index %d\n", alloc->pages[i].page_ptr ? "alloc" : "free", i); binder_selftest_failures++; } } } static void binder_selftest_free_page(struct binder_alloc *alloc) { int i; unsigned long count; while ((count = list_lru_count(&binder_alloc_lru))) { list_lru_walk(&binder_alloc_lru, binder_alloc_free_page, NULL, count); } for (i = 0; i < (alloc->buffer_size / PAGE_SIZE); i++) { if (alloc->pages[i].page_ptr) { pr_err("expect free but is %s at page index %d\n", list_empty(&alloc->pages[i].lru) ? "alloc" : "lru", i); binder_selftest_failures++; } } } static void binder_selftest_alloc_free(struct binder_alloc *alloc, size_t *sizes, int *seq, size_t end) { struct binder_buffer *buffers[BUFFER_NUM]; binder_selftest_alloc_buf(alloc, buffers, sizes, seq); binder_selftest_free_buf(alloc, buffers, sizes, seq, end); /* Allocate from lru. */ binder_selftest_alloc_buf(alloc, buffers, sizes, seq); if (list_lru_count(&binder_alloc_lru)) pr_err("lru list should be empty but is not\n"); binder_selftest_free_buf(alloc, buffers, sizes, seq, end); binder_selftest_free_page(alloc); } static bool is_dup(int *seq, int index, int val) { int i; for (i = 0; i < index; i++) { if (seq[i] == val) return true; } return false; } /* Generate BUFFER_NUM factorial free orders. */ static void binder_selftest_free_seq(struct binder_alloc *alloc, size_t *sizes, int *seq, int index, size_t end) { int i; if (index == BUFFER_NUM) { binder_selftest_alloc_free(alloc, sizes, seq, end); return; } for (i = 0; i < BUFFER_NUM; i++) { if (is_dup(seq, index, i)) continue; seq[index] = i; binder_selftest_free_seq(alloc, sizes, seq, index + 1, end); } } static void binder_selftest_alloc_size(struct binder_alloc *alloc, size_t *end_offset) { int i; int seq[BUFFER_NUM] = {0}; size_t front_sizes[BUFFER_NUM]; size_t back_sizes[BUFFER_NUM]; size_t last_offset, offset = 0; for (i = 0; i < BUFFER_NUM; i++) { last_offset = offset; offset = end_offset[i]; front_sizes[i] = offset - last_offset; back_sizes[BUFFER_NUM - i - 1] = front_sizes[i]; } /* * Buffers share the first or last few pages. * Only BUFFER_NUM - 1 buffer sizes are adjustable since * we need one giant buffer before getting to the last page. */ back_sizes[0] += alloc->buffer_size - end_offset[BUFFER_NUM - 1]; binder_selftest_free_seq(alloc, front_sizes, seq, 0, end_offset[BUFFER_NUM - 1]); binder_selftest_free_seq(alloc, back_sizes, seq, 0, alloc->buffer_size); } static void binder_selftest_alloc_offset(struct binder_alloc *alloc, size_t *end_offset, int index) { int align; size_t end, prev; if (index == BUFFER_NUM) { binder_selftest_alloc_size(alloc, end_offset); return; } prev = index == 0 ? 0 : end_offset[index - 1]; end = prev; BUILD_BUG_ON(BUFFER_MIN_SIZE * BUFFER_NUM >= PAGE_SIZE); for (align = SAME_PAGE_UNALIGNED; align < LOOP_END; align++) { if (align % 2) end = ALIGN(end, PAGE_SIZE); else end += BUFFER_MIN_SIZE; end_offset[index] = end; binder_selftest_alloc_offset(alloc, end_offset, index + 1); } } /** * binder_selftest_alloc() - Test alloc and free of buffer pages. * @alloc: Pointer to alloc struct. * * Allocate BUFFER_NUM buffers to cover all page alignment cases, * then free them in all orders possible. Check that pages are * correctly allocated, put onto lru when buffers are freed, and * are freed when binder_alloc_free_page is called. */ void binder_selftest_alloc(struct binder_alloc *alloc) { size_t end_offset[BUFFER_NUM]; if (!binder_selftest_run) return; mutex_lock(&binder_selftest_lock); if (!binder_selftest_run || !alloc->vma) goto done; pr_info("STARTED\n"); binder_selftest_alloc_offset(alloc, end_offset, 0); binder_selftest_run = false; if (binder_selftest_failures > 0) pr_info("%d tests FAILED\n", binder_selftest_failures); else pr_info("PASSED\n"); done: mutex_unlock(&binder_selftest_lock); }