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