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 lastExtent->disk.length += vecs[i].length; 249 offset += vecs[i].length; 250 start--; 251 _MakeSpace(fCount - 1); 252 continue; 253 } 254 } 255 256 file_extent* extent = ExtentAt(start + i); 257 extent->offset = offset; 258 extent->disk = vecs[i]; 259 260 offset += extent->disk.length; 261 lastExtent = extent; 262 } 263 264 #ifdef TRACE_FILE_MAP 265 for (uint32 i = 0; i < fCount; i++) { 266 file_extent* extent = ExtentAt(i); 267 TRACE("[%ld] extent offset %Ld, disk offset %Ld, length %Ld\n", 268 i, extent->offset, extent->disk.offset, extent->disk.length); 269 } 270 #endif 271 272 lastOffset = offset; 273 return B_OK; 274 } 275 276 277 void 278 FileMap::_InvalidateAfter(off_t offset) 279 { 280 uint32 index; 281 file_extent* extent = _FindExtent(offset, &index); 282 if (extent != NULL) { 283 uint32 resizeTo = index + 1; 284 285 if (extent->offset + extent->disk.length > offset) { 286 extent->disk.length = offset - extent->offset; 287 if (extent->disk.length == 0) 288 resizeTo = index; 289 } 290 291 _MakeSpace(resizeTo); 292 } 293 } 294 295 296 /*! Invalidates or removes the specified part of the file map. 297 */ 298 void 299 FileMap::Invalidate(off_t offset, off_t size) 300 { 301 MutexLocker _(fLock); 302 303 // TODO: honour size, we currently always remove everything after "offset" 304 if (offset == 0) { 305 _Free(); 306 return; 307 } 308 309 _InvalidateAfter(offset); 310 } 311 312 313 void 314 FileMap::SetSize(off_t size) 315 { 316 MutexLocker _(fLock); 317 318 if (size < fSize) 319 _InvalidateAfter(size); 320 321 fSize = size; 322 } 323 324 325 void 326 FileMap::_Free() 327 { 328 if (fCount > CACHED_FILE_EXTENTS) 329 free(fIndirect.array); 330 331 fCount = 0; 332 } 333 334 335 status_t 336 FileMap::_Cache(off_t offset, off_t size) 337 { 338 file_extent* lastExtent = NULL; 339 if (fCount > 0) 340 lastExtent = ExtentAt(fCount - 1); 341 342 off_t mapEnd = 0; 343 if (lastExtent != NULL) 344 mapEnd = lastExtent->offset + lastExtent->disk.length; 345 346 off_t end = offset + size; 347 348 if (fCacheAll && mapEnd < end) 349 return B_ERROR; 350 351 status_t status = B_OK; 352 file_io_vec vecs[8]; 353 const size_t kMaxVecs = 8; 354 355 while (status == B_OK && mapEnd < end) { 356 // We don't have the requested extents yet, retrieve them 357 size_t vecCount = kMaxVecs; 358 status = vfs_get_file_map(Vnode(), mapEnd, ~0UL, vecs, &vecCount); 359 if (status == B_OK || status == B_BUFFER_OVERFLOW) 360 status = _Add(vecs, vecCount, mapEnd); 361 } 362 363 return status; 364 } 365 366 367 status_t 368 FileMap::SetMode(uint32 mode) 369 { 370 if (mode != FILE_MAP_CACHE_ALL && mode != FILE_MAP_CACHE_ON_DEMAND) 371 return B_BAD_VALUE; 372 373 MutexLocker _(fLock); 374 375 if ((mode == FILE_MAP_CACHE_ALL && fCacheAll) 376 || (mode == FILE_MAP_CACHE_ON_DEMAND && !fCacheAll)) 377 return B_OK; 378 379 if (mode == FILE_MAP_CACHE_ALL) { 380 status_t status = _Cache(0, fSize); 381 if (status != B_OK) 382 return status; 383 384 fCacheAll = true; 385 } else 386 fCacheAll = false; 387 388 return B_OK; 389 } 390 391 392 status_t 393 FileMap::Translate(off_t offset, size_t size, file_io_vec* vecs, size_t* _count, 394 size_t align) 395 { 396 if (offset < 0) 397 return B_BAD_VALUE; 398 399 MutexLocker _(fLock); 400 401 size_t maxVecs = *_count; 402 size_t padLastVec = 0; 403 404 if (offset >= Size()) { 405 *_count = 0; 406 return B_OK; 407 } 408 if (offset + size > fSize) { 409 if (align > 1) { 410 off_t alignedSize = (fSize + align - 1) & ~(off_t)(align - 1); 411 if (offset + size >= alignedSize) 412 padLastVec = alignedSize - fSize; 413 } 414 size = fSize - offset; 415 } 416 417 // First, we need to make sure that we have already cached all file 418 // extents needed for this request. 419 420 status_t status = _Cache(offset, size); 421 if (status != B_OK) 422 return status; 423 424 // We now have cached the map of this file as far as we need it, now 425 // we need to translate it for the requested access. 426 427 uint32 index; 428 file_extent* fileExtent = _FindExtent(offset, &index); 429 430 offset -= fileExtent->offset; 431 if (fileExtent->disk.offset != -1) 432 vecs[0].offset = fileExtent->disk.offset + offset; 433 else 434 vecs[0].offset = -1; 435 vecs[0].length = fileExtent->disk.length - offset; 436 437 if (vecs[0].length >= size) { 438 vecs[0].length = size + padLastVec; 439 *_count = 1; 440 return B_OK; 441 } 442 443 // copy the rest of the vecs 444 445 size -= vecs[0].length; 446 uint32 vecIndex = 1; 447 448 while (true) { 449 fileExtent++; 450 451 vecs[vecIndex++] = fileExtent->disk; 452 453 if (size <= fileExtent->disk.length) { 454 vecs[vecIndex - 1].length = size + padLastVec; 455 break; 456 } 457 458 if (vecIndex >= maxVecs) { 459 *_count = vecIndex; 460 return B_BUFFER_OVERFLOW; 461 } 462 463 size -= fileExtent->disk.length; 464 } 465 466 *_count = vecIndex; 467 return B_OK; 468 } 469 470 471 // #pragma mark - 472 473 474 #if DEBUG_FILE_MAP 475 476 static int 477 dump_file_map(int argc, char** argv) 478 { 479 if (argc < 2) { 480 print_debugger_command_usage(argv[0]); 481 return 0; 482 } 483 484 bool printExtents = false; 485 if (argc > 2 && !strcmp(argv[1], "-p")) 486 printExtents = true; 487 488 FileMap* map = (FileMap*)parse_expression(argv[argc - 1]); 489 if (map == NULL) { 490 kprintf("invalid file map!\n"); 491 return 0; 492 } 493 494 kprintf("FileMap %p\n", map); 495 kprintf(" size %Ld\n", map->Size()); 496 kprintf(" count %lu\n", map->Count()); 497 498 if (!printExtents) 499 return 0; 500 501 for (uint32 i = 0; i < map->Count(); i++) { 502 file_extent* extent = map->ExtentAt(i); 503 504 kprintf(" [%lu] offset %Ld, disk offset %Ld, length %Ld\n", 505 i, extent->offset, extent->disk.offset, extent->disk.length); 506 } 507 508 return 0; 509 } 510 511 512 static int 513 dump_file_map_stats(int argc, char** argv) 514 { 515 off_t minSize = 0; 516 off_t maxSize = -1; 517 518 if (argc == 2) { 519 maxSize = parse_expression(argv[1]); 520 } else if (argc > 2) { 521 minSize = parse_expression(argv[1]); 522 maxSize = parse_expression(argv[2]); 523 } 524 525 FileMapList::Iterator iterator = sList.GetIterator(); 526 off_t size = 0; 527 off_t mapSize = 0; 528 uint32 extents = 0; 529 uint32 count = 0; 530 uint32 emptyCount = 0; 531 532 while (iterator.HasNext()) { 533 FileMap* map = iterator.Next(); 534 535 if (minSize > map->Size() || (maxSize != -1 && maxSize < map->Size())) 536 continue; 537 538 if (map->Count() != 0) { 539 file_extent* extent = map->ExtentAt(map->Count() - 1); 540 if (extent != NULL) 541 mapSize += extent->offset + extent->disk.length; 542 543 extents += map->Count(); 544 } else 545 emptyCount++; 546 547 size += map->Size(); 548 count++; 549 } 550 551 kprintf("%ld file maps (%ld empty), %Ld file bytes in total, %Ld bytes " 552 "cached, %lu extents\n", count, emptyCount, size, mapSize, extents); 553 kprintf("average %lu extents per map for %Ld bytes.\n", 554 extents / (count - emptyCount), mapSize / (count - emptyCount)); 555 556 return 0; 557 } 558 559 #endif // DEBUG_FILE_MAP 560 561 562 // #pragma mark - private kernel API 563 564 565 extern "C" status_t 566 file_map_init(void) 567 { 568 #if DEBUG_FILE_MAP 569 add_debugger_command_etc("file_map", &dump_file_map, 570 "Dumps the specified file map.", 571 "[-p] <file-map>\n" 572 " -p - causes the file extents to be printed as well.\n" 573 " <file-map> - pointer to the file map.\n", 0); 574 add_debugger_command("file_map_stats", &dump_file_map_stats, 575 "Dumps some file map statistics."); 576 577 mutex_init(&sLock, "file map list"); 578 #endif 579 return B_OK; 580 } 581 582 583 // #pragma mark - public FS API 584 585 586 extern "C" void* 587 file_map_create(dev_t mountID, ino_t vnodeID, off_t size) 588 { 589 TRACE("file_map_create(mountID = %ld, vnodeID = %Ld, size = %Ld)\n", 590 mountID, vnodeID, size); 591 592 // Get the vnode for the object 593 // (note, this does not grab a reference to the node) 594 struct vnode* vnode; 595 if (vfs_lookup_vnode(mountID, vnodeID, &vnode) != B_OK) 596 return NULL; 597 598 return new(std::nothrow) FileMap(vnode, size); 599 } 600 601 602 extern "C" void 603 file_map_delete(void* _map) 604 { 605 FileMap* map = (FileMap*)_map; 606 if (map == NULL) 607 return; 608 609 TRACE("file_map_delete(map = %p)\n", map); 610 delete map; 611 } 612 613 614 extern "C" void 615 file_map_set_size(void* _map, off_t size) 616 { 617 FileMap* map = (FileMap*)_map; 618 if (map == NULL) 619 return; 620 621 map->SetSize(size); 622 } 623 624 625 extern "C" void 626 file_map_invalidate(void* _map, off_t offset, off_t size) 627 { 628 FileMap* map = (FileMap*)_map; 629 if (map == NULL) 630 return; 631 632 map->Invalidate(offset, size); 633 } 634 635 636 extern "C" status_t 637 file_map_set_mode(void* _map, uint32 mode) 638 { 639 FileMap* map = (FileMap*)_map; 640 if (map == NULL) 641 return B_BAD_VALUE; 642 643 return map->SetMode(mode); 644 } 645 646 647 extern "C" status_t 648 file_map_translate(void* _map, off_t offset, size_t size, file_io_vec* vecs, 649 size_t* _count, size_t align) 650 { 651 TRACE("file_map_translate(map %p, offset %Ld, size %ld)\n", 652 _map, offset, size); 653 654 FileMap* map = (FileMap*)_map; 655 if (map == NULL) 656 return B_BAD_VALUE; 657 658 return map->Translate(offset, size, vecs, _count, align); 659 } 660 661