1 /* 2 * Copyright 2004-2012, Axel Dörfler, axeld@pinc-software.de. 3 * Distributed under the terms of the MIT License. 4 */ 5 6 7 #include <new> 8 #include <stdlib.h> 9 #include <string.h> 10 11 #ifdef FS_SHELL 12 # include "vfs.h" 13 # include "fssh_api_wrapper.h" 14 15 using namespace FSShell; 16 #else 17 # include <unistd.h> 18 19 # include <KernelExport.h> 20 # include <fs_cache.h> 21 22 # include <condition_variable.h> 23 # include <file_cache.h> 24 # include <generic_syscall.h> 25 # include <util/AutoLock.h> 26 # include <util/DoublyLinkedList.h> 27 # include <vfs.h> 28 # include <vm/vm.h> 29 # include <vm/vm_page.h> 30 # include <vm/VMCache.h> 31 32 # include "kernel_debug_config.h" 33 #endif 34 35 36 //#define TRACE_FILE_MAP 37 #ifdef TRACE_FILE_MAP 38 # define TRACE(x...) dprintf_no_syslog(x) 39 #else 40 # define TRACE(x...) ; 41 #endif 42 43 // TODO: use a sparse array - eventually, the unused BlockMap would be something 44 // to reuse for this. We could also have an upperbound of memory consumption 45 // for the whole map. 46 // TODO: it would be nice if we could free a file map in low memory situations. 47 48 49 #define CACHED_FILE_EXTENTS 2 50 // must be smaller than MAX_FILE_IO_VECS 51 // TODO: find out how much of these are typically used 52 53 struct file_extent { 54 off_t offset; 55 file_io_vec disk; 56 }; 57 58 struct file_extent_array { 59 file_extent* array; 60 size_t max_count; 61 }; 62 63 class FileMap 64 #if DEBUG_FILE_MAP 65 : public DoublyLinkedListLinkImpl<FileMap> 66 #endif 67 { 68 public: 69 FileMap(struct vnode* vnode, off_t size); 70 ~FileMap(); 71 72 void Invalidate(off_t offset, off_t size); 73 void SetSize(off_t size); 74 75 status_t Translate(off_t offset, size_t size, 76 file_io_vec* vecs, size_t* _count, 77 size_t align); 78 79 file_extent* ExtentAt(uint32 index); 80 81 size_t Count() const { return fCount; } 82 struct vnode* Vnode() const { return fVnode; } 83 off_t Size() const { return fSize; } 84 85 status_t SetMode(uint32 mode); 86 87 private: 88 file_extent* _FindExtent(off_t offset, uint32* _index); 89 status_t _MakeSpace(size_t count); 90 status_t _Add(file_io_vec* vecs, size_t vecCount, 91 off_t& lastOffset); 92 status_t _Cache(off_t offset, off_t size); 93 void _InvalidateAfter(off_t offset); 94 void _Free(); 95 96 union { 97 file_extent fDirect[CACHED_FILE_EXTENTS]; 98 file_extent_array fIndirect; 99 }; 100 mutex fLock; 101 size_t fCount; 102 struct vnode* fVnode; 103 off_t fSize; 104 bool fCacheAll; 105 }; 106 107 #if DEBUG_FILE_MAP 108 typedef DoublyLinkedList<FileMap> FileMapList; 109 110 static FileMapList sList; 111 static mutex sLock; 112 #endif 113 114 115 FileMap::FileMap(struct vnode* vnode, off_t size) 116 : 117 fCount(0), 118 fVnode(vnode), 119 fSize(size), 120 fCacheAll(false) 121 { 122 mutex_init(&fLock, "file map"); 123 124 #if DEBUG_FILE_MAP 125 MutexLocker _(sLock); 126 sList.Add(this); 127 #endif 128 } 129 130 131 FileMap::~FileMap() 132 { 133 _Free(); 134 mutex_destroy(&fLock); 135 136 #if DEBUG_FILE_MAP 137 MutexLocker _(sLock); 138 sList.Remove(this); 139 #endif 140 } 141 142 143 file_extent* 144 FileMap::ExtentAt(uint32 index) 145 { 146 if (index >= fCount) 147 return NULL; 148 149 if (fCount > CACHED_FILE_EXTENTS) 150 return &fIndirect.array[index]; 151 152 return &fDirect[index]; 153 } 154 155 156 file_extent* 157 FileMap::_FindExtent(off_t offset, uint32 *_index) 158 { 159 int32 left = 0; 160 int32 right = fCount - 1; 161 162 while (left <= right) { 163 int32 index = (left + right) / 2; 164 file_extent* extent = ExtentAt(index); 165 166 if (extent->offset > offset) { 167 // search in left part 168 right = index - 1; 169 } else if (extent->offset + extent->disk.length <= offset) { 170 // search in right part 171 left = index + 1; 172 } else { 173 // found extent 174 if (_index) 175 *_index = index; 176 177 return extent; 178 } 179 } 180 181 return NULL; 182 } 183 184 185 status_t 186 FileMap::_MakeSpace(size_t count) 187 { 188 if (count <= CACHED_FILE_EXTENTS) { 189 // just use the reserved area in the file_cache_ref structure 190 if (fCount > CACHED_FILE_EXTENTS) { 191 // the new size is smaller than the minimal array size 192 file_extent *array = fIndirect.array; 193 memcpy(fDirect, array, sizeof(file_extent) * count); 194 free(array); 195 } 196 } else { 197 // resize array if needed 198 file_extent* oldArray = NULL; 199 size_t maxCount = CACHED_FILE_EXTENTS; 200 if (fCount > CACHED_FILE_EXTENTS) { 201 oldArray = fIndirect.array; 202 maxCount = fIndirect.max_count; 203 } 204 205 if (count > maxCount) { 206 // allocate new array 207 while (maxCount < count) { 208 if (maxCount < 32768) 209 maxCount <<= 1; 210 else 211 maxCount += 32768; 212 } 213 214 file_extent* newArray = (file_extent *)realloc(oldArray, 215 maxCount * sizeof(file_extent)); 216 if (newArray == NULL) 217 return B_NO_MEMORY; 218 219 if (fCount > 0 && fCount <= CACHED_FILE_EXTENTS) 220 memcpy(newArray, fDirect, sizeof(file_extent) * fCount); 221 222 fIndirect.array = newArray; 223 fIndirect.max_count = maxCount; 224 } 225 } 226 227 fCount = count; 228 return B_OK; 229 } 230 231 232 status_t 233 FileMap::_Add(file_io_vec* vecs, size_t vecCount, off_t& lastOffset) 234 { 235 TRACE("FileMap@%p::Add(vecCount = %ld)\n", this, vecCount); 236 237 uint32 start = fCount; 238 off_t offset = 0; 239 240 status_t status = _MakeSpace(fCount + vecCount); 241 if (status != B_OK) 242 return status; 243 244 file_extent* lastExtent = NULL; 245 if (start != 0) { 246 lastExtent = ExtentAt(start - 1); 247 offset = lastExtent->offset + lastExtent->disk.length; 248 } 249 250 for (uint32 i = 0; i < vecCount; i++) { 251 if (lastExtent != NULL) { 252 if (lastExtent->disk.offset + lastExtent->disk.length 253 == vecs[i].offset 254 || (lastExtent->disk.offset == -1 && vecs[i].offset == -1)) { 255 256 lastExtent->disk.length += vecs[i].length; 257 offset += vecs[i].length; 258 259 _MakeSpace(fCount - 1); 260 if (fCount == CACHED_FILE_EXTENTS) { 261 // We moved the indirect array into the direct one, making 262 // lastExtent a stale pointer, re-get it. 263 lastExtent = ExtentAt(start - 1); 264 } 265 266 continue; 267 } 268 } 269 270 file_extent* extent = ExtentAt(start++); 271 extent->offset = offset; 272 extent->disk = vecs[i]; 273 274 offset += extent->disk.length; 275 lastExtent = extent; 276 } 277 278 #ifdef TRACE_FILE_MAP 279 for (uint32 i = 0; i < fCount; i++) { 280 file_extent* extent = ExtentAt(i); 281 TRACE("[%ld] extent offset %lld, disk offset %lld, length %lld\n", 282 i, extent->offset, extent->disk.offset, extent->disk.length); 283 } 284 #endif 285 286 lastOffset = offset; 287 return B_OK; 288 } 289 290 291 void 292 FileMap::_InvalidateAfter(off_t offset) 293 { 294 uint32 index; 295 file_extent* extent = _FindExtent(offset, &index); 296 if (extent != NULL) { 297 uint32 resizeTo = index + 1; 298 299 if (extent->offset + extent->disk.length > offset) { 300 extent->disk.length = offset - extent->offset; 301 if (extent->disk.length == 0) 302 resizeTo = index; 303 } 304 305 _MakeSpace(resizeTo); 306 } 307 } 308 309 310 /*! Invalidates or removes the specified part of the file map. 311 */ 312 void 313 FileMap::Invalidate(off_t offset, off_t size) 314 { 315 MutexLocker _(fLock); 316 317 // TODO: honour size, we currently always remove everything after "offset" 318 if (offset == 0) { 319 _Free(); 320 return; 321 } 322 323 _InvalidateAfter(offset); 324 } 325 326 327 void 328 FileMap::SetSize(off_t size) 329 { 330 MutexLocker _(fLock); 331 332 if (size < fSize) 333 _InvalidateAfter(size); 334 335 fSize = size; 336 } 337 338 339 void 340 FileMap::_Free() 341 { 342 if (fCount > CACHED_FILE_EXTENTS) 343 free(fIndirect.array); 344 345 fCount = 0; 346 } 347 348 349 status_t 350 FileMap::_Cache(off_t offset, off_t size) 351 { 352 file_extent* lastExtent = NULL; 353 if (fCount > 0) 354 lastExtent = ExtentAt(fCount - 1); 355 356 off_t mapEnd = 0; 357 if (lastExtent != NULL) 358 mapEnd = lastExtent->offset + lastExtent->disk.length; 359 360 off_t end = offset + size; 361 362 if (fCacheAll && mapEnd < end) 363 return B_ERROR; 364 365 status_t status = B_OK; 366 file_io_vec vecs[8]; 367 const size_t kMaxVecs = 8; 368 369 while (status == B_OK && mapEnd < end) { 370 // We don't have the requested extents yet, retrieve them 371 size_t vecCount = kMaxVecs; 372 status = vfs_get_file_map(Vnode(), mapEnd, ~0UL, vecs, &vecCount); 373 if (status == B_OK || status == B_BUFFER_OVERFLOW) 374 status = _Add(vecs, vecCount, mapEnd); 375 } 376 377 return status; 378 } 379 380 381 status_t 382 FileMap::SetMode(uint32 mode) 383 { 384 if (mode != FILE_MAP_CACHE_ALL && mode != FILE_MAP_CACHE_ON_DEMAND) 385 return B_BAD_VALUE; 386 387 MutexLocker _(fLock); 388 389 if ((mode == FILE_MAP_CACHE_ALL && fCacheAll) 390 || (mode == FILE_MAP_CACHE_ON_DEMAND && !fCacheAll)) 391 return B_OK; 392 393 if (mode == FILE_MAP_CACHE_ALL) { 394 status_t status = _Cache(0, fSize); 395 if (status != B_OK) 396 return status; 397 398 fCacheAll = true; 399 } else 400 fCacheAll = false; 401 402 return B_OK; 403 } 404 405 406 status_t 407 FileMap::Translate(off_t offset, size_t size, file_io_vec* vecs, size_t* _count, 408 size_t align) 409 { 410 if (offset < 0) 411 return B_BAD_VALUE; 412 413 MutexLocker _(fLock); 414 415 size_t maxVecs = *_count; 416 size_t padLastVec = 0; 417 418 if (offset >= Size()) { 419 *_count = 0; 420 return B_OK; 421 } 422 if ((off_t)(offset + size) > fSize) { 423 if (align > 1) { 424 off_t alignedSize = (fSize + align - 1) & ~(off_t)(align - 1); 425 if ((off_t)(offset + size) >= alignedSize) 426 padLastVec = alignedSize - fSize; 427 } 428 size = fSize - offset; 429 } 430 431 // First, we need to make sure that we have already cached all file 432 // extents needed for this request. 433 434 status_t status = _Cache(offset, size); 435 if (status != B_OK) 436 return status; 437 438 // We now have cached the map of this file as far as we need it, now 439 // we need to translate it for the requested access. 440 441 uint32 index; 442 file_extent* fileExtent = _FindExtent(offset, &index); 443 444 offset -= fileExtent->offset; 445 if (fileExtent->disk.offset != -1) 446 vecs[0].offset = fileExtent->disk.offset + offset; 447 else 448 vecs[0].offset = -1; 449 vecs[0].length = fileExtent->disk.length - offset; 450 451 if (vecs[0].length >= (off_t)size) { 452 vecs[0].length = size + padLastVec; 453 *_count = 1; 454 return B_OK; 455 } 456 457 // copy the rest of the vecs 458 459 size -= vecs[0].length; 460 uint32 vecIndex = 1; 461 462 while (true) { 463 fileExtent++; 464 465 vecs[vecIndex++] = fileExtent->disk; 466 467 if ((off_t)size <= fileExtent->disk.length) { 468 vecs[vecIndex - 1].length = size + padLastVec; 469 break; 470 } 471 472 if (vecIndex >= maxVecs) { 473 *_count = vecIndex; 474 return B_BUFFER_OVERFLOW; 475 } 476 477 size -= fileExtent->disk.length; 478 } 479 480 *_count = vecIndex; 481 return B_OK; 482 } 483 484 485 // #pragma mark - 486 487 488 #if DEBUG_FILE_MAP 489 490 static int 491 dump_file_map(int argc, char** argv) 492 { 493 if (argc < 2) { 494 print_debugger_command_usage(argv[0]); 495 return 0; 496 } 497 498 bool printExtents = false; 499 if (argc > 2 && !strcmp(argv[1], "-p")) 500 printExtents = true; 501 502 FileMap* map = (FileMap*)parse_expression(argv[argc - 1]); 503 if (map == NULL) { 504 kprintf("invalid file map!\n"); 505 return 0; 506 } 507 508 kprintf("FileMap %p\n", map); 509 kprintf(" size %" B_PRIdOFF "\n", map->Size()); 510 kprintf(" count %lu\n", map->Count()); 511 512 if (!printExtents) 513 return 0; 514 515 for (uint32 i = 0; i < map->Count(); i++) { 516 file_extent* extent = map->ExtentAt(i); 517 518 kprintf(" [%" B_PRIu32 "] offset %" B_PRIdOFF ", disk offset %" 519 B_PRIdOFF ", length %" B_PRIdOFF "\n", i, extent->offset, 520 extent->disk.offset, extent->disk.length); 521 } 522 523 return 0; 524 } 525 526 527 static int 528 dump_file_map_stats(int argc, char** argv) 529 { 530 off_t minSize = 0; 531 off_t maxSize = -1; 532 533 if (argc == 2) { 534 maxSize = parse_expression(argv[1]); 535 } else if (argc > 2) { 536 minSize = parse_expression(argv[1]); 537 maxSize = parse_expression(argv[2]); 538 } 539 540 FileMapList::Iterator iterator = sList.GetIterator(); 541 off_t size = 0; 542 off_t mapSize = 0; 543 uint32 extents = 0; 544 uint32 count = 0; 545 uint32 emptyCount = 0; 546 547 while (iterator.HasNext()) { 548 FileMap* map = iterator.Next(); 549 550 if (minSize > map->Size() || (maxSize != -1 && maxSize < map->Size())) 551 continue; 552 553 if (map->Count() != 0) { 554 file_extent* extent = map->ExtentAt(map->Count() - 1); 555 if (extent != NULL) 556 mapSize += extent->offset + extent->disk.length; 557 558 extents += map->Count(); 559 } else 560 emptyCount++; 561 562 size += map->Size(); 563 count++; 564 } 565 566 kprintf("%" B_PRId32 " file maps (%" B_PRIu32 " empty), %" B_PRIdOFF " file" 567 " bytes in total, %" B_PRIdOFF " bytes cached, %" B_PRIu32 " extents\n", 568 count, emptyCount, size, mapSize, extents); 569 kprintf("average %" B_PRIu32 " extents per map for %" B_PRIdOFF " bytes.\n", 570 extents / (count - emptyCount), mapSize / (count - emptyCount)); 571 572 return 0; 573 } 574 575 #endif // DEBUG_FILE_MAP 576 577 578 // #pragma mark - private kernel API 579 580 581 extern "C" status_t 582 file_map_init(void) 583 { 584 #if DEBUG_FILE_MAP 585 add_debugger_command_etc("file_map", &dump_file_map, 586 "Dumps the specified file map.", 587 "[-p] <file-map>\n" 588 " -p - causes the file extents to be printed as well.\n" 589 " <file-map> - pointer to the file map.\n", 0); 590 add_debugger_command("file_map_stats", &dump_file_map_stats, 591 "Dumps some file map statistics."); 592 593 mutex_init(&sLock, "file map list"); 594 #endif 595 return B_OK; 596 } 597 598 599 // #pragma mark - public FS API 600 601 602 extern "C" void* 603 file_map_create(dev_t mountID, ino_t vnodeID, off_t size) 604 { 605 TRACE("file_map_create(mountID = %ld, vnodeID = %lld, size = %lld)\n", 606 mountID, vnodeID, size); 607 608 // Get the vnode for the object 609 // (note, this does not grab a reference to the node) 610 struct vnode* vnode; 611 if (vfs_lookup_vnode(mountID, vnodeID, &vnode) != B_OK) 612 return NULL; 613 614 return new(std::nothrow) FileMap(vnode, size); 615 } 616 617 618 extern "C" void 619 file_map_delete(void* _map) 620 { 621 FileMap* map = (FileMap*)_map; 622 if (map == NULL) 623 return; 624 625 TRACE("file_map_delete(map = %p)\n", map); 626 delete map; 627 } 628 629 630 extern "C" void 631 file_map_set_size(void* _map, off_t size) 632 { 633 FileMap* map = (FileMap*)_map; 634 if (map == NULL) 635 return; 636 637 map->SetSize(size); 638 } 639 640 641 extern "C" void 642 file_map_invalidate(void* _map, off_t offset, off_t size) 643 { 644 FileMap* map = (FileMap*)_map; 645 if (map == NULL) 646 return; 647 648 map->Invalidate(offset, size); 649 } 650 651 652 extern "C" status_t 653 file_map_set_mode(void* _map, uint32 mode) 654 { 655 FileMap* map = (FileMap*)_map; 656 if (map == NULL) 657 return B_BAD_VALUE; 658 659 return map->SetMode(mode); 660 } 661 662 663 extern "C" status_t 664 file_map_translate(void* _map, off_t offset, size_t size, file_io_vec* vecs, 665 size_t* _count, size_t align) 666 { 667 TRACE("file_map_translate(map %p, offset %lld, size %ld)\n", 668 _map, offset, size); 669 670 FileMap* map = (FileMap*)_map; 671 if (map == NULL) 672 return B_BAD_VALUE; 673 674 return map->Translate(offset, size, vecs, _count, align); 675 } 676 677