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