1 // SPDX-License-Identifier: GPL-2.0-only 2 /* binder_alloc.c 3 * 4 * Android IPC Subsystem 5 * 6 * Copyright (C) 2007-2017 Google, Inc. 7 */ 8 9 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt 10 11 #include <linux/list.h> 12 #include <linux/sched/mm.h> 13 #include <linux/module.h> 14 #include <linux/rtmutex.h> 15 #include <linux/rbtree.h> 16 #include <linux/seq_file.h> 17 #include <linux/vmalloc.h> 18 #include <linux/slab.h> 19 #include <linux/sched.h> 20 #include <linux/list_lru.h> 21 #include <linux/ratelimit.h> 22 #include <asm/cacheflush.h> 23 #include <linux/uaccess.h> 24 #include <linux/highmem.h> 25 #include <linux/sizes.h> 26 #include "binder_alloc.h" 27 #include "binder_trace.h" 28 29 struct list_lru binder_alloc_lru; 30 31 static DEFINE_MUTEX(binder_alloc_mmap_lock); 32 33 enum { 34 BINDER_DEBUG_USER_ERROR = 1U << 0, 35 BINDER_DEBUG_OPEN_CLOSE = 1U << 1, 36 BINDER_DEBUG_BUFFER_ALLOC = 1U << 2, 37 BINDER_DEBUG_BUFFER_ALLOC_ASYNC = 1U << 3, 38 }; 39 static uint32_t binder_alloc_debug_mask = BINDER_DEBUG_USER_ERROR; 40 41 module_param_named(debug_mask, binder_alloc_debug_mask, 42 uint, 0644); 43 44 #define binder_alloc_debug(mask, x...) \ 45 do { \ 46 if (binder_alloc_debug_mask & mask) \ 47 pr_info_ratelimited(x); \ 48 } while (0) 49 50 static struct binder_buffer *binder_buffer_next(struct binder_buffer *buffer) 51 { 52 return list_entry(buffer->entry.next, struct binder_buffer, entry); 53 } 54 55 static struct binder_buffer *binder_buffer_prev(struct binder_buffer *buffer) 56 { 57 return list_entry(buffer->entry.prev, struct binder_buffer, entry); 58 } 59 60 static size_t binder_alloc_buffer_size(struct binder_alloc *alloc, 61 struct binder_buffer *buffer) 62 { 63 if (list_is_last(&buffer->entry, &alloc->buffers)) 64 return alloc->buffer + alloc->buffer_size - buffer->user_data; 65 return binder_buffer_next(buffer)->user_data - buffer->user_data; 66 } 67 68 static void binder_insert_free_buffer(struct binder_alloc *alloc, 69 struct binder_buffer *new_buffer) 70 { 71 struct rb_node **p = &alloc->free_buffers.rb_node; 72 struct rb_node *parent = NULL; 73 struct binder_buffer *buffer; 74 size_t buffer_size; 75 size_t new_buffer_size; 76 77 BUG_ON(!new_buffer->free); 78 79 new_buffer_size = binder_alloc_buffer_size(alloc, new_buffer); 80 81 binder_alloc_debug(BINDER_DEBUG_BUFFER_ALLOC, 82 "%d: add free buffer, size %zd, at %pK\n", 83 alloc->pid, new_buffer_size, new_buffer); 84 85 while (*p) { 86 parent = *p; 87 buffer = rb_entry(parent, struct binder_buffer, rb_node); 88 BUG_ON(!buffer->free); 89 90 buffer_size = binder_alloc_buffer_size(alloc, buffer); 91 92 if (new_buffer_size < buffer_size) 93 p = &parent->rb_left; 94 else 95 p = &parent->rb_right; 96 } 97 rb_link_node(&new_buffer->rb_node, parent, p); 98 rb_insert_color(&new_buffer->rb_node, &alloc->free_buffers); 99 } 100 101 static void binder_insert_allocated_buffer_locked( 102 struct binder_alloc *alloc, struct binder_buffer *new_buffer) 103 { 104 struct rb_node **p = &alloc->allocated_buffers.rb_node; 105 struct rb_node *parent = NULL; 106 struct binder_buffer *buffer; 107 108 BUG_ON(new_buffer->free); 109 110 while (*p) { 111 parent = *p; 112 buffer = rb_entry(parent, struct binder_buffer, rb_node); 113 BUG_ON(buffer->free); 114 115 if (new_buffer->user_data < buffer->user_data) 116 p = &parent->rb_left; 117 else if (new_buffer->user_data > buffer->user_data) 118 p = &parent->rb_right; 119 else 120 BUG(); 121 } 122 rb_link_node(&new_buffer->rb_node, parent, p); 123 rb_insert_color(&new_buffer->rb_node, &alloc->allocated_buffers); 124 } 125 126 static struct binder_buffer *binder_alloc_prepare_to_free_locked( 127 struct binder_alloc *alloc, 128 uintptr_t user_ptr) 129 { 130 struct rb_node *n = alloc->allocated_buffers.rb_node; 131 struct binder_buffer *buffer; 132 void __user *uptr; 133 134 uptr = (void __user *)user_ptr; 135 136 while (n) { 137 buffer = rb_entry(n, struct binder_buffer, rb_node); 138 BUG_ON(buffer->free); 139 140 if (uptr < buffer->user_data) 141 n = n->rb_left; 142 else if (uptr > buffer->user_data) 143 n = n->rb_right; 144 else { 145 /* 146 * Guard against user threads attempting to 147 * free the buffer when in use by kernel or 148 * after it's already been freed. 149 */ 150 if (!buffer->allow_user_free) 151 return ERR_PTR(-EPERM); 152 buffer->allow_user_free = 0; 153 return buffer; 154 } 155 } 156 return NULL; 157 } 158 159 /** 160 * binder_alloc_prepare_to_free() - get buffer given user ptr 161 * @alloc: binder_alloc for this proc 162 * @user_ptr: User pointer to buffer data 163 * 164 * Validate userspace pointer to buffer data and return buffer corresponding to 165 * that user pointer. Search the rb tree for buffer that matches user data 166 * pointer. 167 * 168 * Return: Pointer to buffer or NULL 169 */ 170 struct binder_buffer *binder_alloc_prepare_to_free(struct binder_alloc *alloc, 171 uintptr_t user_ptr) 172 { 173 struct binder_buffer *buffer; 174 175 mutex_lock(&alloc->mutex); 176 buffer = binder_alloc_prepare_to_free_locked(alloc, user_ptr); 177 mutex_unlock(&alloc->mutex); 178 return buffer; 179 } 180 181 static int binder_update_page_range(struct binder_alloc *alloc, int allocate, 182 void __user *start, void __user *end) 183 { 184 void __user *page_addr; 185 unsigned long user_page_addr; 186 struct binder_lru_page *page; 187 struct vm_area_struct *vma = NULL; 188 struct mm_struct *mm = NULL; 189 bool need_mm = false; 190 191 binder_alloc_debug(BINDER_DEBUG_BUFFER_ALLOC, 192 "%d: %s pages %pK-%pK\n", alloc->pid, 193 allocate ? "allocate" : "free", start, end); 194 195 if (end <= start) 196 return 0; 197 198 trace_binder_update_page_range(alloc, allocate, start, end); 199 200 if (allocate == 0) 201 goto free_range; 202 203 for (page_addr = start; page_addr < end; page_addr += PAGE_SIZE) { 204 page = &alloc->pages[(page_addr - alloc->buffer) / PAGE_SIZE]; 205 if (!page->page_ptr) { 206 need_mm = true; 207 break; 208 } 209 } 210 211 if (need_mm && mmget_not_zero(alloc->vma_vm_mm)) 212 mm = alloc->vma_vm_mm; 213 214 if (mm) { 215 mmap_read_lock(mm); 216 vma = vma_lookup(mm, alloc->vma_addr); 217 } 218 219 if (!vma && need_mm) { 220 binder_alloc_debug(BINDER_DEBUG_USER_ERROR, 221 "%d: binder_alloc_buf failed to map pages in userspace, no vma\n", 222 alloc->pid); 223 goto err_no_vma; 224 } 225 226 for (page_addr = start; page_addr < end; page_addr += PAGE_SIZE) { 227 int ret; 228 bool on_lru; 229 size_t index; 230 231 index = (page_addr - alloc->buffer) / PAGE_SIZE; 232 page = &alloc->pages[index]; 233 234 if (page->page_ptr) { 235 trace_binder_alloc_lru_start(alloc, index); 236 237 on_lru = list_lru_del(&binder_alloc_lru, &page->lru); 238 WARN_ON(!on_lru); 239 240 trace_binder_alloc_lru_end(alloc, index); 241 continue; 242 } 243 244 if (WARN_ON(!vma)) 245 goto err_page_ptr_cleared; 246 247 trace_binder_alloc_page_start(alloc, index); 248 page->page_ptr = alloc_page(GFP_KERNEL | 249 __GFP_HIGHMEM | 250 __GFP_ZERO); 251 if (!page->page_ptr) { 252 pr_err("%d: binder_alloc_buf failed for page at %pK\n", 253 alloc->pid, page_addr); 254 goto err_alloc_page_failed; 255 } 256 page->alloc = alloc; 257 INIT_LIST_HEAD(&page->lru); 258 259 user_page_addr = (uintptr_t)page_addr; 260 ret = vm_insert_page(vma, user_page_addr, page[0].page_ptr); 261 if (ret) { 262 pr_err("%d: binder_alloc_buf failed to map page at %lx in userspace\n", 263 alloc->pid, user_page_addr); 264 goto err_vm_insert_page_failed; 265 } 266 267 if (index + 1 > alloc->pages_high) 268 alloc->pages_high = index + 1; 269 270 trace_binder_alloc_page_end(alloc, index); 271 } 272 if (mm) { 273 mmap_read_unlock(mm); 274 mmput(mm); 275 } 276 return 0; 277 278 free_range: 279 for (page_addr = end - PAGE_SIZE; 1; page_addr -= PAGE_SIZE) { 280 bool ret; 281 size_t index; 282 283 index = (page_addr - alloc->buffer) / PAGE_SIZE; 284 page = &alloc->pages[index]; 285 286 trace_binder_free_lru_start(alloc, index); 287 288 ret = list_lru_add(&binder_alloc_lru, &page->lru); 289 WARN_ON(!ret); 290 291 trace_binder_free_lru_end(alloc, index); 292 if (page_addr == start) 293 break; 294 continue; 295 296 err_vm_insert_page_failed: 297 __free_page(page->page_ptr); 298 page->page_ptr = NULL; 299 err_alloc_page_failed: 300 err_page_ptr_cleared: 301 if (page_addr == start) 302 break; 303 } 304 err_no_vma: 305 if (mm) { 306 mmap_read_unlock(mm); 307 mmput(mm); 308 } 309 return vma ? -ENOMEM : -ESRCH; 310 } 311 312 313 static inline void binder_alloc_set_vma(struct binder_alloc *alloc, 314 struct vm_area_struct *vma) 315 { 316 unsigned long vm_start = 0; 317 318 /* 319 * Allow clearing the vma with holding just the read lock to allow 320 * munmapping downgrade of the write lock before freeing and closing the 321 * file using binder_alloc_vma_close(). 322 */ 323 if (vma) { 324 vm_start = vma->vm_start; 325 mmap_assert_write_locked(alloc->vma_vm_mm); 326 } else { 327 mmap_assert_locked(alloc->vma_vm_mm); 328 } 329 330 alloc->vma_addr = vm_start; 331 } 332 333 static inline struct vm_area_struct *binder_alloc_get_vma( 334 struct binder_alloc *alloc) 335 { 336 struct vm_area_struct *vma = NULL; 337 338 if (alloc->vma_addr) 339 vma = vma_lookup(alloc->vma_vm_mm, alloc->vma_addr); 340 341 return vma; 342 } 343 344 static bool debug_low_async_space_locked(struct binder_alloc *alloc, int pid) 345 { 346 /* 347 * Find the amount and size of buffers allocated by the current caller; 348 * The idea is that once we cross the threshold, whoever is responsible 349 * for the low async space is likely to try to send another async txn, 350 * and at some point we'll catch them in the act. This is more efficient 351 * than keeping a map per pid. 352 */ 353 struct rb_node *n; 354 struct binder_buffer *buffer; 355 size_t total_alloc_size = 0; 356 size_t num_buffers = 0; 357 358 for (n = rb_first(&alloc->allocated_buffers); n != NULL; 359 n = rb_next(n)) { 360 buffer = rb_entry(n, struct binder_buffer, rb_node); 361 if (buffer->pid != pid) 362 continue; 363 if (!buffer->async_transaction) 364 continue; 365 total_alloc_size += binder_alloc_buffer_size(alloc, buffer) 366 + sizeof(struct binder_buffer); 367 num_buffers++; 368 } 369 370 /* 371 * Warn if this pid has more than 50 transactions, or more than 50% of 372 * async space (which is 25% of total buffer size). Oneway spam is only 373 * detected when the threshold is exceeded. 374 */ 375 if (num_buffers > 50 || total_alloc_size > alloc->buffer_size / 4) { 376 binder_alloc_debug(BINDER_DEBUG_USER_ERROR, 377 "%d: pid %d spamming oneway? %zd buffers allocated for a total size of %zd\n", 378 alloc->pid, pid, num_buffers, total_alloc_size); 379 if (!alloc->oneway_spam_detected) { 380 alloc->oneway_spam_detected = true; 381 return true; 382 } 383 } 384 return false; 385 } 386 387 static struct binder_buffer *binder_alloc_new_buf_locked( 388 struct binder_alloc *alloc, 389 size_t data_size, 390 size_t offsets_size, 391 size_t extra_buffers_size, 392 int is_async, 393 int pid) 394 { 395 struct rb_node *n = alloc->free_buffers.rb_node; 396 struct binder_buffer *buffer; 397 size_t buffer_size; 398 struct rb_node *best_fit = NULL; 399 void __user *has_page_addr; 400 void __user *end_page_addr; 401 size_t size, data_offsets_size; 402 int ret; 403 404 mmap_read_lock(alloc->vma_vm_mm); 405 if (!binder_alloc_get_vma(alloc)) { 406 mmap_read_unlock(alloc->vma_vm_mm); 407 binder_alloc_debug(BINDER_DEBUG_USER_ERROR, 408 "%d: binder_alloc_buf, no vma\n", 409 alloc->pid); 410 return ERR_PTR(-ESRCH); 411 } 412 mmap_read_unlock(alloc->vma_vm_mm); 413 414 data_offsets_size = ALIGN(data_size, sizeof(void *)) + 415 ALIGN(offsets_size, sizeof(void *)); 416 417 if (data_offsets_size < data_size || data_offsets_size < offsets_size) { 418 binder_alloc_debug(BINDER_DEBUG_BUFFER_ALLOC, 419 "%d: got transaction with invalid size %zd-%zd\n", 420 alloc->pid, data_size, offsets_size); 421 return ERR_PTR(-EINVAL); 422 } 423 size = data_offsets_size + ALIGN(extra_buffers_size, sizeof(void *)); 424 if (size < data_offsets_size || size < extra_buffers_size) { 425 binder_alloc_debug(BINDER_DEBUG_BUFFER_ALLOC, 426 "%d: got transaction with invalid extra_buffers_size %zd\n", 427 alloc->pid, extra_buffers_size); 428 return ERR_PTR(-EINVAL); 429 } 430 if (is_async && 431 alloc->free_async_space < size + sizeof(struct binder_buffer)) { 432 binder_alloc_debug(BINDER_DEBUG_BUFFER_ALLOC, 433 "%d: binder_alloc_buf size %zd failed, no async space left\n", 434 alloc->pid, size); 435 return ERR_PTR(-ENOSPC); 436 } 437 438 /* Pad 0-size buffers so they get assigned unique addresses */ 439 size = max(size, sizeof(void *)); 440 441 while (n) { 442 buffer = rb_entry(n, struct binder_buffer, rb_node); 443 BUG_ON(!buffer->free); 444 buffer_size = binder_alloc_buffer_size(alloc, buffer); 445 446 if (size < buffer_size) { 447 best_fit = n; 448 n = n->rb_left; 449 } else if (size > buffer_size) 450 n = n->rb_right; 451 else { 452 best_fit = n; 453 break; 454 } 455 } 456 if (best_fit == NULL) { 457 size_t allocated_buffers = 0; 458 size_t largest_alloc_size = 0; 459 size_t total_alloc_size = 0; 460 size_t free_buffers = 0; 461 size_t largest_free_size = 0; 462 size_t total_free_size = 0; 463 464 for (n = rb_first(&alloc->allocated_buffers); n != NULL; 465 n = rb_next(n)) { 466 buffer = rb_entry(n, struct binder_buffer, rb_node); 467 buffer_size = binder_alloc_buffer_size(alloc, buffer); 468 allocated_buffers++; 469 total_alloc_size += buffer_size; 470 if (buffer_size > largest_alloc_size) 471 largest_alloc_size = buffer_size; 472 } 473 for (n = rb_first(&alloc->free_buffers); n != NULL; 474 n = rb_next(n)) { 475 buffer = rb_entry(n, struct binder_buffer, rb_node); 476 buffer_size = binder_alloc_buffer_size(alloc, buffer); 477 free_buffers++; 478 total_free_size += buffer_size; 479 if (buffer_size > largest_free_size) 480 largest_free_size = buffer_size; 481 } 482 binder_alloc_debug(BINDER_DEBUG_USER_ERROR, 483 "%d: binder_alloc_buf size %zd failed, no address space\n", 484 alloc->pid, size); 485 binder_alloc_debug(BINDER_DEBUG_USER_ERROR, 486 "allocated: %zd (num: %zd largest: %zd), free: %zd (num: %zd largest: %zd)\n", 487 total_alloc_size, allocated_buffers, 488 largest_alloc_size, total_free_size, 489 free_buffers, largest_free_size); 490 return ERR_PTR(-ENOSPC); 491 } 492 if (n == NULL) { 493 buffer = rb_entry(best_fit, struct binder_buffer, rb_node); 494 buffer_size = binder_alloc_buffer_size(alloc, buffer); 495 } 496 497 binder_alloc_debug(BINDER_DEBUG_BUFFER_ALLOC, 498 "%d: binder_alloc_buf size %zd got buffer %pK size %zd\n", 499 alloc->pid, size, buffer, buffer_size); 500 501 has_page_addr = (void __user *) 502 (((uintptr_t)buffer->user_data + buffer_size) & PAGE_MASK); 503 WARN_ON(n && buffer_size != size); 504 end_page_addr = 505 (void __user *)PAGE_ALIGN((uintptr_t)buffer->user_data + size); 506 if (end_page_addr > has_page_addr) 507 end_page_addr = has_page_addr; 508 ret = binder_update_page_range(alloc, 1, (void __user *) 509 PAGE_ALIGN((uintptr_t)buffer->user_data), end_page_addr); 510 if (ret) 511 return ERR_PTR(ret); 512 513 if (buffer_size != size) { 514 struct binder_buffer *new_buffer; 515 516 new_buffer = kzalloc(sizeof(*buffer), GFP_KERNEL); 517 if (!new_buffer) { 518 pr_err("%s: %d failed to alloc new buffer struct\n", 519 __func__, alloc->pid); 520 goto err_alloc_buf_struct_failed; 521 } 522 new_buffer->user_data = (u8 __user *)buffer->user_data + size; 523 list_add(&new_buffer->entry, &buffer->entry); 524 new_buffer->free = 1; 525 binder_insert_free_buffer(alloc, new_buffer); 526 } 527 528 rb_erase(best_fit, &alloc->free_buffers); 529 buffer->free = 0; 530 buffer->allow_user_free = 0; 531 binder_insert_allocated_buffer_locked(alloc, buffer); 532 binder_alloc_debug(BINDER_DEBUG_BUFFER_ALLOC, 533 "%d: binder_alloc_buf size %zd got %pK\n", 534 alloc->pid, size, buffer); 535 buffer->data_size = data_size; 536 buffer->offsets_size = offsets_size; 537 buffer->async_transaction = is_async; 538 buffer->extra_buffers_size = extra_buffers_size; 539 buffer->pid = pid; 540 buffer->oneway_spam_suspect = false; 541 if (is_async) { 542 alloc->free_async_space -= size + sizeof(struct binder_buffer); 543 binder_alloc_debug(BINDER_DEBUG_BUFFER_ALLOC_ASYNC, 544 "%d: binder_alloc_buf size %zd async free %zd\n", 545 alloc->pid, size, alloc->free_async_space); 546 if (alloc->free_async_space < alloc->buffer_size / 10) { 547 /* 548 * Start detecting spammers once we have less than 20% 549 * of async space left (which is less than 10% of total 550 * buffer size). 551 */ 552 buffer->oneway_spam_suspect = debug_low_async_space_locked(alloc, pid); 553 } else { 554 alloc->oneway_spam_detected = false; 555 } 556 } 557 return buffer; 558 559 err_alloc_buf_struct_failed: 560 binder_update_page_range(alloc, 0, (void __user *) 561 PAGE_ALIGN((uintptr_t)buffer->user_data), 562 end_page_addr); 563 return ERR_PTR(-ENOMEM); 564 } 565 566 /** 567 * binder_alloc_new_buf() - Allocate a new binder buffer 568 * @alloc: binder_alloc for this proc 569 * @data_size: size of user data buffer 570 * @offsets_size: user specified buffer offset 571 * @extra_buffers_size: size of extra space for meta-data (eg, security context) 572 * @is_async: buffer for async transaction 573 * @pid: pid to attribute allocation to (used for debugging) 574 * 575 * Allocate a new buffer given the requested sizes. Returns 576 * the kernel version of the buffer pointer. The size allocated 577 * is the sum of the three given sizes (each rounded up to 578 * pointer-sized boundary) 579 * 580 * Return: The allocated buffer or %NULL if error 581 */ 582 struct binder_buffer *binder_alloc_new_buf(struct binder_alloc *alloc, 583 size_t data_size, 584 size_t offsets_size, 585 size_t extra_buffers_size, 586 int is_async, 587 int pid) 588 { 589 struct binder_buffer *buffer; 590 591 mutex_lock(&alloc->mutex); 592 buffer = binder_alloc_new_buf_locked(alloc, data_size, offsets_size, 593 extra_buffers_size, is_async, pid); 594 mutex_unlock(&alloc->mutex); 595 return buffer; 596 } 597 598 static void __user *buffer_start_page(struct binder_buffer *buffer) 599 { 600 return (void __user *)((uintptr_t)buffer->user_data & PAGE_MASK); 601 } 602 603 static void __user *prev_buffer_end_page(struct binder_buffer *buffer) 604 { 605 return (void __user *) 606 (((uintptr_t)(buffer->user_data) - 1) & PAGE_MASK); 607 } 608 609 static void binder_delete_free_buffer(struct binder_alloc *alloc, 610 struct binder_buffer *buffer) 611 { 612 struct binder_buffer *prev, *next = NULL; 613 bool to_free = true; 614 615 BUG_ON(alloc->buffers.next == &buffer->entry); 616 prev = binder_buffer_prev(buffer); 617 BUG_ON(!prev->free); 618 if (prev_buffer_end_page(prev) == buffer_start_page(buffer)) { 619 to_free = false; 620 binder_alloc_debug(BINDER_DEBUG_BUFFER_ALLOC, 621 "%d: merge free, buffer %pK share page with %pK\n", 622 alloc->pid, buffer->user_data, 623 prev->user_data); 624 } 625 626 if (!list_is_last(&buffer->entry, &alloc->buffers)) { 627 next = binder_buffer_next(buffer); 628 if (buffer_start_page(next) == buffer_start_page(buffer)) { 629 to_free = false; 630 binder_alloc_debug(BINDER_DEBUG_BUFFER_ALLOC, 631 "%d: merge free, buffer %pK share page with %pK\n", 632 alloc->pid, 633 buffer->user_data, 634 next->user_data); 635 } 636 } 637 638 if (PAGE_ALIGNED(buffer->user_data)) { 639 binder_alloc_debug(BINDER_DEBUG_BUFFER_ALLOC, 640 "%d: merge free, buffer start %pK is page aligned\n", 641 alloc->pid, buffer->user_data); 642 to_free = false; 643 } 644 645 if (to_free) { 646 binder_alloc_debug(BINDER_DEBUG_BUFFER_ALLOC, 647 "%d: merge free, buffer %pK do not share page with %pK or %pK\n", 648 alloc->pid, buffer->user_data, 649 prev->user_data, 650 next ? next->user_data : NULL); 651 binder_update_page_range(alloc, 0, buffer_start_page(buffer), 652 buffer_start_page(buffer) + PAGE_SIZE); 653 } 654 list_del(&buffer->entry); 655 kfree(buffer); 656 } 657 658 static void binder_free_buf_locked(struct binder_alloc *alloc, 659 struct binder_buffer *buffer) 660 { 661 size_t size, buffer_size; 662 663 buffer_size = binder_alloc_buffer_size(alloc, buffer); 664 665 size = ALIGN(buffer->data_size, sizeof(void *)) + 666 ALIGN(buffer->offsets_size, sizeof(void *)) + 667 ALIGN(buffer->extra_buffers_size, sizeof(void *)); 668 669 binder_alloc_debug(BINDER_DEBUG_BUFFER_ALLOC, 670 "%d: binder_free_buf %pK size %zd buffer_size %zd\n", 671 alloc->pid, buffer, size, buffer_size); 672 673 BUG_ON(buffer->free); 674 BUG_ON(size > buffer_size); 675 BUG_ON(buffer->transaction != NULL); 676 BUG_ON(buffer->user_data < alloc->buffer); 677 BUG_ON(buffer->user_data > alloc->buffer + alloc->buffer_size); 678 679 if (buffer->async_transaction) { 680 alloc->free_async_space += buffer_size + sizeof(struct binder_buffer); 681 682 binder_alloc_debug(BINDER_DEBUG_BUFFER_ALLOC_ASYNC, 683 "%d: binder_free_buf size %zd async free %zd\n", 684 alloc->pid, size, alloc->free_async_space); 685 } 686 687 binder_update_page_range(alloc, 0, 688 (void __user *)PAGE_ALIGN((uintptr_t)buffer->user_data), 689 (void __user *)(((uintptr_t) 690 buffer->user_data + buffer_size) & PAGE_MASK)); 691 692 rb_erase(&buffer->rb_node, &alloc->allocated_buffers); 693 buffer->free = 1; 694 if (!list_is_last(&buffer->entry, &alloc->buffers)) { 695 struct binder_buffer *next = binder_buffer_next(buffer); 696 697 if (next->free) { 698 rb_erase(&next->rb_node, &alloc->free_buffers); 699 binder_delete_free_buffer(alloc, next); 700 } 701 } 702 if (alloc->buffers.next != &buffer->entry) { 703 struct binder_buffer *prev = binder_buffer_prev(buffer); 704 705 if (prev->free) { 706 binder_delete_free_buffer(alloc, buffer); 707 rb_erase(&prev->rb_node, &alloc->free_buffers); 708 buffer = prev; 709 } 710 } 711 binder_insert_free_buffer(alloc, buffer); 712 } 713 714 static void binder_alloc_clear_buf(struct binder_alloc *alloc, 715 struct binder_buffer *buffer); 716 /** 717 * binder_alloc_free_buf() - free a binder buffer 718 * @alloc: binder_alloc for this proc 719 * @buffer: kernel pointer to buffer 720 * 721 * Free the buffer allocated via binder_alloc_new_buf() 722 */ 723 void binder_alloc_free_buf(struct binder_alloc *alloc, 724 struct binder_buffer *buffer) 725 { 726 /* 727 * We could eliminate the call to binder_alloc_clear_buf() 728 * from binder_alloc_deferred_release() by moving this to 729 * binder_alloc_free_buf_locked(). However, that could 730 * increase contention for the alloc mutex if clear_on_free 731 * is used frequently for large buffers. The mutex is not 732 * needed for correctness here. 733 */ 734 if (buffer->clear_on_free) { 735 binder_alloc_clear_buf(alloc, buffer); 736 buffer->clear_on_free = false; 737 } 738 mutex_lock(&alloc->mutex); 739 binder_free_buf_locked(alloc, buffer); 740 mutex_unlock(&alloc->mutex); 741 } 742 743 /** 744 * binder_alloc_mmap_handler() - map virtual address space for proc 745 * @alloc: alloc structure for this proc 746 * @vma: vma passed to mmap() 747 * 748 * Called by binder_mmap() to initialize the space specified in 749 * vma for allocating binder buffers 750 * 751 * Return: 752 * 0 = success 753 * -EBUSY = address space already mapped 754 * -ENOMEM = failed to map memory to given address space 755 */ 756 int binder_alloc_mmap_handler(struct binder_alloc *alloc, 757 struct vm_area_struct *vma) 758 { 759 int ret; 760 const char *failure_string; 761 struct binder_buffer *buffer; 762 763 mutex_lock(&binder_alloc_mmap_lock); 764 if (alloc->buffer_size) { 765 ret = -EBUSY; 766 failure_string = "already mapped"; 767 goto err_already_mapped; 768 } 769 alloc->buffer_size = min_t(unsigned long, vma->vm_end - vma->vm_start, 770 SZ_4M); 771 mutex_unlock(&binder_alloc_mmap_lock); 772 773 alloc->buffer = (void __user *)vma->vm_start; 774 775 alloc->pages = kcalloc(alloc->buffer_size / PAGE_SIZE, 776 sizeof(alloc->pages[0]), 777 GFP_KERNEL); 778 if (alloc->pages == NULL) { 779 ret = -ENOMEM; 780 failure_string = "alloc page array"; 781 goto err_alloc_pages_failed; 782 } 783 784 buffer = kzalloc(sizeof(*buffer), GFP_KERNEL); 785 if (!buffer) { 786 ret = -ENOMEM; 787 failure_string = "alloc buffer struct"; 788 goto err_alloc_buf_struct_failed; 789 } 790 791 buffer->user_data = alloc->buffer; 792 list_add(&buffer->entry, &alloc->buffers); 793 buffer->free = 1; 794 binder_insert_free_buffer(alloc, buffer); 795 alloc->free_async_space = alloc->buffer_size / 2; 796 binder_alloc_set_vma(alloc, vma); 797 798 return 0; 799 800 err_alloc_buf_struct_failed: 801 kfree(alloc->pages); 802 alloc->pages = NULL; 803 err_alloc_pages_failed: 804 alloc->buffer = NULL; 805 mutex_lock(&binder_alloc_mmap_lock); 806 alloc->buffer_size = 0; 807 err_already_mapped: 808 mutex_unlock(&binder_alloc_mmap_lock); 809 binder_alloc_debug(BINDER_DEBUG_USER_ERROR, 810 "%s: %d %lx-%lx %s failed %d\n", __func__, 811 alloc->pid, vma->vm_start, vma->vm_end, 812 failure_string, ret); 813 return ret; 814 } 815 816 817 void binder_alloc_deferred_release(struct binder_alloc *alloc) 818 { 819 struct rb_node *n; 820 int buffers, page_count; 821 struct binder_buffer *buffer; 822 823 buffers = 0; 824 mutex_lock(&alloc->mutex); 825 BUG_ON(alloc->vma_addr && 826 vma_lookup(alloc->vma_vm_mm, alloc->vma_addr)); 827 828 while ((n = rb_first(&alloc->allocated_buffers))) { 829 buffer = rb_entry(n, struct binder_buffer, rb_node); 830 831 /* Transaction should already have been freed */ 832 BUG_ON(buffer->transaction); 833 834 if (buffer->clear_on_free) { 835 binder_alloc_clear_buf(alloc, buffer); 836 buffer->clear_on_free = false; 837 } 838 binder_free_buf_locked(alloc, buffer); 839 buffers++; 840 } 841 842 while (!list_empty(&alloc->buffers)) { 843 buffer = list_first_entry(&alloc->buffers, 844 struct binder_buffer, entry); 845 WARN_ON(!buffer->free); 846 847 list_del(&buffer->entry); 848 WARN_ON_ONCE(!list_empty(&alloc->buffers)); 849 kfree(buffer); 850 } 851 852 page_count = 0; 853 if (alloc->pages) { 854 int i; 855 856 for (i = 0; i < alloc->buffer_size / PAGE_SIZE; i++) { 857 void __user *page_addr; 858 bool on_lru; 859 860 if (!alloc->pages[i].page_ptr) 861 continue; 862 863 on_lru = list_lru_del(&binder_alloc_lru, 864 &alloc->pages[i].lru); 865 page_addr = alloc->buffer + i * PAGE_SIZE; 866 binder_alloc_debug(BINDER_DEBUG_BUFFER_ALLOC, 867 "%s: %d: page %d at %pK %s\n", 868 __func__, alloc->pid, i, page_addr, 869 on_lru ? "on lru" : "active"); 870 __free_page(alloc->pages[i].page_ptr); 871 page_count++; 872 } 873 kfree(alloc->pages); 874 } 875 mutex_unlock(&alloc->mutex); 876 if (alloc->vma_vm_mm) 877 mmdrop(alloc->vma_vm_mm); 878 879 binder_alloc_debug(BINDER_DEBUG_OPEN_CLOSE, 880 "%s: %d buffers %d, pages %d\n", 881 __func__, alloc->pid, buffers, page_count); 882 } 883 884 static void print_binder_buffer(struct seq_file *m, const char *prefix, 885 struct binder_buffer *buffer) 886 { 887 seq_printf(m, "%s %d: %pK size %zd:%zd:%zd %s\n", 888 prefix, buffer->debug_id, buffer->user_data, 889 buffer->data_size, buffer->offsets_size, 890 buffer->extra_buffers_size, 891 buffer->transaction ? "active" : "delivered"); 892 } 893 894 /** 895 * binder_alloc_print_allocated() - print buffer info 896 * @m: seq_file for output via seq_printf() 897 * @alloc: binder_alloc for this proc 898 * 899 * Prints information about every buffer associated with 900 * the binder_alloc state to the given seq_file 901 */ 902 void binder_alloc_print_allocated(struct seq_file *m, 903 struct binder_alloc *alloc) 904 { 905 struct rb_node *n; 906 907 mutex_lock(&alloc->mutex); 908 for (n = rb_first(&alloc->allocated_buffers); n != NULL; n = rb_next(n)) 909 print_binder_buffer(m, " buffer", 910 rb_entry(n, struct binder_buffer, rb_node)); 911 mutex_unlock(&alloc->mutex); 912 } 913 914 /** 915 * binder_alloc_print_pages() - print page usage 916 * @m: seq_file for output via seq_printf() 917 * @alloc: binder_alloc for this proc 918 */ 919 void binder_alloc_print_pages(struct seq_file *m, 920 struct binder_alloc *alloc) 921 { 922 struct binder_lru_page *page; 923 int i; 924 int active = 0; 925 int lru = 0; 926 int free = 0; 927 928 mutex_lock(&alloc->mutex); 929 /* 930 * Make sure the binder_alloc is fully initialized, otherwise we might 931 * read inconsistent state. 932 */ 933 934 mmap_read_lock(alloc->vma_vm_mm); 935 if (binder_alloc_get_vma(alloc) == NULL) { 936 mmap_read_unlock(alloc->vma_vm_mm); 937 goto uninitialized; 938 } 939 940 mmap_read_unlock(alloc->vma_vm_mm); 941 for (i = 0; i < alloc->buffer_size / PAGE_SIZE; i++) { 942 page = &alloc->pages[i]; 943 if (!page->page_ptr) 944 free++; 945 else if (list_empty(&page->lru)) 946 active++; 947 else 948 lru++; 949 } 950 951 uninitialized: 952 mutex_unlock(&alloc->mutex); 953 seq_printf(m, " pages: %d:%d:%d\n", active, lru, free); 954 seq_printf(m, " pages high watermark: %zu\n", alloc->pages_high); 955 } 956 957 /** 958 * binder_alloc_get_allocated_count() - return count of buffers 959 * @alloc: binder_alloc for this proc 960 * 961 * Return: count of allocated buffers 962 */ 963 int binder_alloc_get_allocated_count(struct binder_alloc *alloc) 964 { 965 struct rb_node *n; 966 int count = 0; 967 968 mutex_lock(&alloc->mutex); 969 for (n = rb_first(&alloc->allocated_buffers); n != NULL; n = rb_next(n)) 970 count++; 971 mutex_unlock(&alloc->mutex); 972 return count; 973 } 974 975 976 /** 977 * binder_alloc_vma_close() - invalidate address space 978 * @alloc: binder_alloc for this proc 979 * 980 * Called from binder_vma_close() when releasing address space. 981 * Clears alloc->vma to prevent new incoming transactions from 982 * allocating more buffers. 983 */ 984 void binder_alloc_vma_close(struct binder_alloc *alloc) 985 { 986 binder_alloc_set_vma(alloc, NULL); 987 } 988 989 /** 990 * binder_alloc_free_page() - shrinker callback to free pages 991 * @item: item to free 992 * @lock: lock protecting the item 993 * @cb_arg: callback argument 994 * 995 * Called from list_lru_walk() in binder_shrink_scan() to free 996 * up pages when the system is under memory pressure. 997 */ 998 enum lru_status binder_alloc_free_page(struct list_head *item, 999 struct list_lru_one *lru, 1000 spinlock_t *lock, 1001 void *cb_arg) 1002 __must_hold(lock) 1003 { 1004 struct mm_struct *mm = NULL; 1005 struct binder_lru_page *page = container_of(item, 1006 struct binder_lru_page, 1007 lru); 1008 struct binder_alloc *alloc; 1009 uintptr_t page_addr; 1010 size_t index; 1011 struct vm_area_struct *vma; 1012 1013 alloc = page->alloc; 1014 if (!mutex_trylock(&alloc->mutex)) 1015 goto err_get_alloc_mutex_failed; 1016 1017 if (!page->page_ptr) 1018 goto err_page_already_freed; 1019 1020 index = page - alloc->pages; 1021 page_addr = (uintptr_t)alloc->buffer + index * PAGE_SIZE; 1022 1023 mm = alloc->vma_vm_mm; 1024 if (!mmget_not_zero(mm)) 1025 goto err_mmget; 1026 if (!mmap_read_trylock(mm)) 1027 goto err_mmap_read_lock_failed; 1028 vma = binder_alloc_get_vma(alloc); 1029 1030 list_lru_isolate(lru, item); 1031 spin_unlock(lock); 1032 1033 if (vma) { 1034 trace_binder_unmap_user_start(alloc, index); 1035 1036 zap_page_range(vma, page_addr, PAGE_SIZE); 1037 1038 trace_binder_unmap_user_end(alloc, index); 1039 } 1040 mmap_read_unlock(mm); 1041 mmput_async(mm); 1042 1043 trace_binder_unmap_kernel_start(alloc, index); 1044 1045 __free_page(page->page_ptr); 1046 page->page_ptr = NULL; 1047 1048 trace_binder_unmap_kernel_end(alloc, index); 1049 1050 spin_lock(lock); 1051 mutex_unlock(&alloc->mutex); 1052 return LRU_REMOVED_RETRY; 1053 1054 err_mmap_read_lock_failed: 1055 mmput_async(mm); 1056 err_mmget: 1057 err_page_already_freed: 1058 mutex_unlock(&alloc->mutex); 1059 err_get_alloc_mutex_failed: 1060 return LRU_SKIP; 1061 } 1062 1063 static unsigned long 1064 binder_shrink_count(struct shrinker *shrink, struct shrink_control *sc) 1065 { 1066 return list_lru_count(&binder_alloc_lru); 1067 } 1068 1069 static unsigned long 1070 binder_shrink_scan(struct shrinker *shrink, struct shrink_control *sc) 1071 { 1072 return list_lru_walk(&binder_alloc_lru, binder_alloc_free_page, 1073 NULL, sc->nr_to_scan); 1074 } 1075 1076 static struct shrinker binder_shrinker = { 1077 .count_objects = binder_shrink_count, 1078 .scan_objects = binder_shrink_scan, 1079 .seeks = DEFAULT_SEEKS, 1080 }; 1081 1082 /** 1083 * binder_alloc_init() - called by binder_open() for per-proc initialization 1084 * @alloc: binder_alloc for this proc 1085 * 1086 * Called from binder_open() to initialize binder_alloc fields for 1087 * new binder proc 1088 */ 1089 void binder_alloc_init(struct binder_alloc *alloc) 1090 { 1091 alloc->pid = current->group_leader->pid; 1092 alloc->vma_vm_mm = current->mm; 1093 mmgrab(alloc->vma_vm_mm); 1094 mutex_init(&alloc->mutex); 1095 INIT_LIST_HEAD(&alloc->buffers); 1096 } 1097 1098 int binder_alloc_shrinker_init(void) 1099 { 1100 int ret = list_lru_init(&binder_alloc_lru); 1101 1102 if (ret == 0) { 1103 ret = register_shrinker(&binder_shrinker, "android-binder"); 1104 if (ret) 1105 list_lru_destroy(&binder_alloc_lru); 1106 } 1107 return ret; 1108 } 1109 1110 /** 1111 * check_buffer() - verify that buffer/offset is safe to access 1112 * @alloc: binder_alloc for this proc 1113 * @buffer: binder buffer to be accessed 1114 * @offset: offset into @buffer data 1115 * @bytes: bytes to access from offset 1116 * 1117 * Check that the @offset/@bytes are within the size of the given 1118 * @buffer and that the buffer is currently active and not freeable. 1119 * Offsets must also be multiples of sizeof(u32). The kernel is 1120 * allowed to touch the buffer in two cases: 1121 * 1122 * 1) when the buffer is being created: 1123 * (buffer->free == 0 && buffer->allow_user_free == 0) 1124 * 2) when the buffer is being torn down: 1125 * (buffer->free == 0 && buffer->transaction == NULL). 1126 * 1127 * Return: true if the buffer is safe to access 1128 */ 1129 static inline bool check_buffer(struct binder_alloc *alloc, 1130 struct binder_buffer *buffer, 1131 binder_size_t offset, size_t bytes) 1132 { 1133 size_t buffer_size = binder_alloc_buffer_size(alloc, buffer); 1134 1135 return buffer_size >= bytes && 1136 offset <= buffer_size - bytes && 1137 IS_ALIGNED(offset, sizeof(u32)) && 1138 !buffer->free && 1139 (!buffer->allow_user_free || !buffer->transaction); 1140 } 1141 1142 /** 1143 * binder_alloc_get_page() - get kernel pointer for given buffer offset 1144 * @alloc: binder_alloc for this proc 1145 * @buffer: binder buffer to be accessed 1146 * @buffer_offset: offset into @buffer data 1147 * @pgoffp: address to copy final page offset to 1148 * 1149 * Lookup the struct page corresponding to the address 1150 * at @buffer_offset into @buffer->user_data. If @pgoffp is not 1151 * NULL, the byte-offset into the page is written there. 1152 * 1153 * The caller is responsible to ensure that the offset points 1154 * to a valid address within the @buffer and that @buffer is 1155 * not freeable by the user. Since it can't be freed, we are 1156 * guaranteed that the corresponding elements of @alloc->pages[] 1157 * cannot change. 1158 * 1159 * Return: struct page 1160 */ 1161 static struct page *binder_alloc_get_page(struct binder_alloc *alloc, 1162 struct binder_buffer *buffer, 1163 binder_size_t buffer_offset, 1164 pgoff_t *pgoffp) 1165 { 1166 binder_size_t buffer_space_offset = buffer_offset + 1167 (buffer->user_data - alloc->buffer); 1168 pgoff_t pgoff = buffer_space_offset & ~PAGE_MASK; 1169 size_t index = buffer_space_offset >> PAGE_SHIFT; 1170 struct binder_lru_page *lru_page; 1171 1172 lru_page = &alloc->pages[index]; 1173 *pgoffp = pgoff; 1174 return lru_page->page_ptr; 1175 } 1176 1177 /** 1178 * binder_alloc_clear_buf() - zero out buffer 1179 * @alloc: binder_alloc for this proc 1180 * @buffer: binder buffer to be cleared 1181 * 1182 * memset the given buffer to 0 1183 */ 1184 static void binder_alloc_clear_buf(struct binder_alloc *alloc, 1185 struct binder_buffer *buffer) 1186 { 1187 size_t bytes = binder_alloc_buffer_size(alloc, buffer); 1188 binder_size_t buffer_offset = 0; 1189 1190 while (bytes) { 1191 unsigned long size; 1192 struct page *page; 1193 pgoff_t pgoff; 1194 1195 page = binder_alloc_get_page(alloc, buffer, 1196 buffer_offset, &pgoff); 1197 size = min_t(size_t, bytes, PAGE_SIZE - pgoff); 1198 memset_page(page, pgoff, 0, size); 1199 bytes -= size; 1200 buffer_offset += size; 1201 } 1202 } 1203 1204 /** 1205 * binder_alloc_copy_user_to_buffer() - copy src user to tgt user 1206 * @alloc: binder_alloc for this proc 1207 * @buffer: binder buffer to be accessed 1208 * @buffer_offset: offset into @buffer data 1209 * @from: userspace pointer to source buffer 1210 * @bytes: bytes to copy 1211 * 1212 * Copy bytes from source userspace to target buffer. 1213 * 1214 * Return: bytes remaining to be copied 1215 */ 1216 unsigned long 1217 binder_alloc_copy_user_to_buffer(struct binder_alloc *alloc, 1218 struct binder_buffer *buffer, 1219 binder_size_t buffer_offset, 1220 const void __user *from, 1221 size_t bytes) 1222 { 1223 if (!check_buffer(alloc, buffer, buffer_offset, bytes)) 1224 return bytes; 1225 1226 while (bytes) { 1227 unsigned long size; 1228 unsigned long ret; 1229 struct page *page; 1230 pgoff_t pgoff; 1231 void *kptr; 1232 1233 page = binder_alloc_get_page(alloc, buffer, 1234 buffer_offset, &pgoff); 1235 size = min_t(size_t, bytes, PAGE_SIZE - pgoff); 1236 kptr = kmap_local_page(page) + pgoff; 1237 ret = copy_from_user(kptr, from, size); 1238 kunmap_local(kptr); 1239 if (ret) 1240 return bytes - size + ret; 1241 bytes -= size; 1242 from += size; 1243 buffer_offset += size; 1244 } 1245 return 0; 1246 } 1247 1248 static int binder_alloc_do_buffer_copy(struct binder_alloc *alloc, 1249 bool to_buffer, 1250 struct binder_buffer *buffer, 1251 binder_size_t buffer_offset, 1252 void *ptr, 1253 size_t bytes) 1254 { 1255 /* All copies must be 32-bit aligned and 32-bit size */ 1256 if (!check_buffer(alloc, buffer, buffer_offset, bytes)) 1257 return -EINVAL; 1258 1259 while (bytes) { 1260 unsigned long size; 1261 struct page *page; 1262 pgoff_t pgoff; 1263 1264 page = binder_alloc_get_page(alloc, buffer, 1265 buffer_offset, &pgoff); 1266 size = min_t(size_t, bytes, PAGE_SIZE - pgoff); 1267 if (to_buffer) 1268 memcpy_to_page(page, pgoff, ptr, size); 1269 else 1270 memcpy_from_page(ptr, page, pgoff, size); 1271 bytes -= size; 1272 pgoff = 0; 1273 ptr = ptr + size; 1274 buffer_offset += size; 1275 } 1276 return 0; 1277 } 1278 1279 int binder_alloc_copy_to_buffer(struct binder_alloc *alloc, 1280 struct binder_buffer *buffer, 1281 binder_size_t buffer_offset, 1282 void *src, 1283 size_t bytes) 1284 { 1285 return binder_alloc_do_buffer_copy(alloc, true, buffer, buffer_offset, 1286 src, bytes); 1287 } 1288 1289 int binder_alloc_copy_from_buffer(struct binder_alloc *alloc, 1290 void *dest, 1291 struct binder_buffer *buffer, 1292 binder_size_t buffer_offset, 1293 size_t bytes) 1294 { 1295 return binder_alloc_do_buffer_copy(alloc, false, buffer, buffer_offset, 1296 dest, bytes); 1297 } 1298 1299