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