307 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/* binder_alloc_selftest.c3 *4 * Android IPC Subsystem5 *6 * Copyright (C) 2017 Google, Inc.7 */8 9#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt10 11#include <linux/mm_types.h>12#include <linux/err.h>13#include "binder_alloc.h"14 15#define BUFFER_NUM 516#define BUFFER_MIN_SIZE (PAGE_SIZE / 8)17 18static bool binder_selftest_run = true;19static int binder_selftest_failures;20static DEFINE_MUTEX(binder_selftest_lock);21 22/**23 * enum buf_end_align_type - Page alignment of a buffer24 * end with regard to the end of the previous buffer.25 *26 * In the pictures below, buf2 refers to the buffer we27 * are aligning. buf1 refers to previous buffer by addr.28 * Symbol [ means the start of a buffer, ] means the end29 * of a buffer, and | means page boundaries.30 */31enum buf_end_align_type {32 /**33 * @SAME_PAGE_UNALIGNED: The end of this buffer is on34 * the same page as the end of the previous buffer and35 * 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 buffer42 * is not page aligned, the end of this buffer is on the43 * same page as the end of the previous buffer and is page44 * aligned. When the previous buffer is page aligned, the45 * 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 on53 * the page next to the end of the previous buffer and54 * 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 on61 * the page next to the end of the previous buffer and62 * 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 on69 * the page that follows the page after the end of the70 * 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 82static 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 96static 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(&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 119static 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, sizes[i], 0, 0, 0);127 if (IS_ERR(buffers[i]) ||128 !check_buffer_pages_allocated(alloc, buffers[i],129 sizes[i])) {130 pr_err_size_seq(sizes, seq);131 binder_selftest_failures++;132 }133 }134}135 136static 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, buffers[seq[i]]);144 145 for (i = 0; i < end / PAGE_SIZE; i++) {146 /**147 * Error message on a free page can be false positive148 * if binder shrinker ran during binder_alloc_free_buf149 * calls above.150 */151 if (list_empty(&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 160static void binder_selftest_free_page(struct binder_alloc *alloc)161{162 int i;163 unsigned long count;164 165 while ((count = list_lru_count(&binder_freelist))) {166 list_lru_walk(&binder_freelist, binder_alloc_free_page,167 NULL, 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 180static 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(&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 197static 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. */209static 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, i))221 continue;222 seq[index] = i;223 binder_selftest_free_seq(alloc, sizes, seq, index + 1, end);224 }225}226 227static 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 since245 * 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, front_sizes, seq, 0,249 end_offset[BUFFER_NUM - 1]);250 binder_selftest_free_seq(alloc, back_sizes, seq, 0, alloc->buffer_size);251}252 253static 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 else272 end += BUFFER_MIN_SIZE;273 end_offset[index] = end;274 binder_selftest_alloc_offset(alloc, end_offset, 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 are284 * correctly allocated, put onto lru when buffers are freed, and285 * are freed when binder_alloc_free_page is called.286 */287void 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, 0);298 binder_selftest_run = false;299 if (binder_selftest_failures > 0)300 pr_info("%d tests FAILED\n", binder_selftest_failures);301 else302 pr_info("PASSED\n");303 304done:305 mutex_unlock(&binder_selftest_lock);306}307