src/system/kernel/cache/file_map.cpp

   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 %Ld, disk offset %Ld, length %Ld\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 = %Ld, size = %Ld)\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 %Ld, 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