drivers/android/binder_alloc_selftest.c

   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 }