Merge tag 'platform-drivers-x86-v5.3-1' of git://git.infradead.org/linux-platform...
[linux-2.6-block.git] / drivers / android / binder_alloc_selftest.c
1 // SPDX-License-Identifier: GPL-2.0-only
2 /* binder_alloc_selftest.c
3  *
4  * Android IPC Subsystem
5  *
6  * Copyright (C) 2017 Google, Inc.
7  */
8
9 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
10
11 #include <linux/mm_types.h>
12 #include <linux/err.h>
13 #include "binder_alloc.h"
14
15 #define BUFFER_NUM 5
16 #define BUFFER_MIN_SIZE (PAGE_SIZE / 8)
17
18 static bool binder_selftest_run = true;
19 static int binder_selftest_failures;
20 static DEFINE_MUTEX(binder_selftest_lock);
21
22 /**
23  * enum buf_end_align_type - Page alignment of a buffer
24  * end with regard to the end of the previous buffer.
25  *
26  * In the pictures below, buf2 refers to the buffer we
27  * are aligning. buf1 refers to previous buffer by addr.
28  * Symbol [ means the start of a buffer, ] means the end
29  * of a buffer, and | means page boundaries.
30  */
31 enum buf_end_align_type {
32         /**
33          * @SAME_PAGE_UNALIGNED: The end of this buffer is on
34          * the same page as the end of the previous buffer and
35          * 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 buffer
42          * is not page aligned, the end of this buffer is on the
43          * same page as the end of the previous buffer and is page
44          * aligned. When the previous buffer is page aligned, the
45          * 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 on
53          * the page next to the end of the previous buffer and
54          * 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 on
61          * the page next to the end of the previous buffer and
62          * 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 on
69          * the page that follows the page after the end of the
70          * previous buffer and is not page aligned. Examples:
71          * buf1 ][ buf2 | buf2 | buf2 ][ ...
72          * buf1 ]|[ buf2 | buf2 | buf2 ][ ...
73          */
74         NEXT_NEXT_UNALIGNED,
75         LOOP_END,
76 };
77
78 static void pr_err_size_seq(size_t *sizes, int *seq)
79 {
80         int i;
81
82         pr_err("alloc sizes: ");
83         for (i = 0; i < BUFFER_NUM; i++)
84                 pr_cont("[%zu]", sizes[i]);
85         pr_cont("\n");
86         pr_err("free seq: ");
87         for (i = 0; i < BUFFER_NUM; i++)
88                 pr_cont("[%d]", seq[i]);
89         pr_cont("\n");
90 }
91
92 static bool check_buffer_pages_allocated(struct binder_alloc *alloc,
93                                          struct binder_buffer *buffer,
94                                          size_t size)
95 {
96         void __user *page_addr;
97         void __user *end;
98         int page_index;
99
100         end = (void __user *)PAGE_ALIGN((uintptr_t)buffer->user_data + size);
101         page_addr = buffer->user_data;
102         for (; page_addr < end; page_addr += PAGE_SIZE) {
103                 page_index = (page_addr - alloc->buffer) / PAGE_SIZE;
104                 if (!alloc->pages[page_index].page_ptr ||
105                     !list_empty(&alloc->pages[page_index].lru)) {
106                         pr_err("expect alloc but is %s at page index %d\n",
107                                alloc->pages[page_index].page_ptr ?
108                                "lru" : "free", page_index);
109                         return false;
110                 }
111         }
112         return true;
113 }
114
115 static void binder_selftest_alloc_buf(struct binder_alloc *alloc,
116                                       struct binder_buffer *buffers[],
117                                       size_t *sizes, int *seq)
118 {
119         int i;
120
121         for (i = 0; i < BUFFER_NUM; i++) {
122                 buffers[i] = binder_alloc_new_buf(alloc, sizes[i], 0, 0, 0);
123                 if (IS_ERR(buffers[i]) ||
124                     !check_buffer_pages_allocated(alloc, buffers[i],
125                                                   sizes[i])) {
126                         pr_err_size_seq(sizes, seq);
127                         binder_selftest_failures++;
128                 }
129         }
130 }
131
132 static void binder_selftest_free_buf(struct binder_alloc *alloc,
133                                      struct binder_buffer *buffers[],
134                                      size_t *sizes, int *seq, size_t end)
135 {
136         int i;
137
138         for (i = 0; i < BUFFER_NUM; i++)
139                 binder_alloc_free_buf(alloc, buffers[seq[i]]);
140
141         for (i = 0; i < end / PAGE_SIZE; i++) {
142                 /**
143                  * Error message on a free page can be false positive
144                  * if binder shrinker ran during binder_alloc_free_buf
145                  * calls above.
146                  */
147                 if (list_empty(&alloc->pages[i].lru)) {
148                         pr_err_size_seq(sizes, seq);
149                         pr_err("expect lru but is %s at page index %d\n",
150                                alloc->pages[i].page_ptr ? "alloc" : "free", i);
151                         binder_selftest_failures++;
152                 }
153         }
154 }
155
156 static void binder_selftest_free_page(struct binder_alloc *alloc)
157 {
158         int i;
159         unsigned long count;
160
161         while ((count = list_lru_count(&binder_alloc_lru))) {
162                 list_lru_walk(&binder_alloc_lru, binder_alloc_free_page,
163                               NULL, count);
164         }
165
166         for (i = 0; i < (alloc->buffer_size / PAGE_SIZE); i++) {
167                 if (alloc->pages[i].page_ptr) {
168                         pr_err("expect free but is %s at page index %d\n",
169                                list_empty(&alloc->pages[i].lru) ?
170                                "alloc" : "lru", i);
171                         binder_selftest_failures++;
172                 }
173         }
174 }
175
176 static void binder_selftest_alloc_free(struct binder_alloc *alloc,
177                                        size_t *sizes, int *seq, size_t end)
178 {
179         struct binder_buffer *buffers[BUFFER_NUM];
180
181         binder_selftest_alloc_buf(alloc, buffers, sizes, seq);
182         binder_selftest_free_buf(alloc, buffers, sizes, seq, end);
183
184         /* Allocate from lru. */
185         binder_selftest_alloc_buf(alloc, buffers, sizes, seq);
186         if (list_lru_count(&binder_alloc_lru))
187                 pr_err("lru list should be empty but is not\n");
188
189         binder_selftest_free_buf(alloc, buffers, sizes, seq, end);
190         binder_selftest_free_page(alloc);
191 }
192
193 static bool is_dup(int *seq, int index, int val)
194 {
195         int i;
196
197         for (i = 0; i < index; i++) {
198                 if (seq[i] == val)
199                         return true;
200         }
201         return false;
202 }
203
204 /* Generate BUFFER_NUM factorial free orders. */
205 static void binder_selftest_free_seq(struct binder_alloc *alloc,
206                                      size_t *sizes, int *seq,
207                                      int index, size_t end)
208 {
209         int i;
210
211         if (index == BUFFER_NUM) {
212                 binder_selftest_alloc_free(alloc, sizes, seq, end);
213                 return;
214         }
215         for (i = 0; i < BUFFER_NUM; i++) {
216                 if (is_dup(seq, index, i))
217                         continue;
218                 seq[index] = i;
219                 binder_selftest_free_seq(alloc, sizes, seq, index + 1, end);
220         }
221 }
222
223 static void binder_selftest_alloc_size(struct binder_alloc *alloc,
224                                        size_t *end_offset)
225 {
226         int i;
227         int seq[BUFFER_NUM] = {0};
228         size_t front_sizes[BUFFER_NUM];
229         size_t back_sizes[BUFFER_NUM];
230         size_t last_offset, offset = 0;
231
232         for (i = 0; i < BUFFER_NUM; i++) {
233                 last_offset = offset;
234                 offset = end_offset[i];
235                 front_sizes[i] = offset - last_offset;
236                 back_sizes[BUFFER_NUM - i - 1] = front_sizes[i];
237         }
238         /*
239          * Buffers share the first or last few pages.
240          * Only BUFFER_NUM - 1 buffer sizes are adjustable since
241          * we need one giant buffer before getting to the last page.
242          */
243         back_sizes[0] += alloc->buffer_size - end_offset[BUFFER_NUM - 1];
244         binder_selftest_free_seq(alloc, front_sizes, seq, 0,
245                                  end_offset[BUFFER_NUM - 1]);
246         binder_selftest_free_seq(alloc, back_sizes, seq, 0, alloc->buffer_size);
247 }
248
249 static void binder_selftest_alloc_offset(struct binder_alloc *alloc,
250                                          size_t *end_offset, int index)
251 {
252         int align;
253         size_t end, prev;
254
255         if (index == BUFFER_NUM) {
256                 binder_selftest_alloc_size(alloc, end_offset);
257                 return;
258         }
259         prev = index == 0 ? 0 : end_offset[index - 1];
260         end = prev;
261
262         BUILD_BUG_ON(BUFFER_MIN_SIZE * BUFFER_NUM >= PAGE_SIZE);
263
264         for (align = SAME_PAGE_UNALIGNED; align < LOOP_END; align++) {
265                 if (align % 2)
266                         end = ALIGN(end, PAGE_SIZE);
267                 else
268                         end += BUFFER_MIN_SIZE;
269                 end_offset[index] = end;
270                 binder_selftest_alloc_offset(alloc, end_offset, index + 1);
271         }
272 }
273
274 /**
275  * binder_selftest_alloc() - Test alloc and free of buffer pages.
276  * @alloc: Pointer to alloc struct.
277  *
278  * Allocate BUFFER_NUM buffers to cover all page alignment cases,
279  * then free them in all orders possible. Check that pages are
280  * correctly allocated, put onto lru when buffers are freed, and
281  * are freed when binder_alloc_free_page is called.
282  */
283 void binder_selftest_alloc(struct binder_alloc *alloc)
284 {
285         size_t end_offset[BUFFER_NUM];
286
287         if (!binder_selftest_run)
288                 return;
289         mutex_lock(&binder_selftest_lock);
290         if (!binder_selftest_run || !alloc->vma)
291                 goto done;
292         pr_info("STARTED\n");
293         binder_selftest_alloc_offset(alloc, end_offset, 0);
294         binder_selftest_run = false;
295         if (binder_selftest_failures > 0)
296                 pr_info("%d tests FAILED\n", binder_selftest_failures);
297         else
298                 pr_info("PASSED\n");
299
300 done:
301         mutex_unlock(&binder_selftest_lock);
302 }