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
Count() const81 size_t Count() const { return fCount; }
Vnode() const82 struct vnode* Vnode() const { return fVnode; }
Size() const83 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
FileMap(struct vnode * vnode,off_t size)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
~FileMap()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*
ExtentAt(uint32 index)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*
_FindExtent(off_t offset,uint32 * _index)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
_MakeSpace(size_t count)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
_Add(file_io_vec * vecs,size_t vecCount,off_t & lastOffset)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
_InvalidateAfter(off_t offset)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
Invalidate(off_t offset,off_t size)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
SetSize(off_t size)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
_Free()340 FileMap::_Free()
341 {
342 if (fCount > CACHED_FILE_EXTENTS)
343 free(fIndirect.array);
344
345 fCount = 0;
346 }
347
348
349 status_t
_Cache(off_t offset,off_t size)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
SetMode(uint32 mode)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
Translate(off_t offset,size_t size,file_io_vec * vecs,size_t * _count,size_t align)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
dump_file_map(int argc,char ** argv)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
dump_file_map_stats(int argc,char ** argv)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
file_map_init(void)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*
file_map_create(dev_t mountID,ino_t vnodeID,off_t size)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
file_map_delete(void * _map)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
file_map_set_size(void * _map,off_t size)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
file_map_invalidate(void * _map,off_t offset,off_t size)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
file_map_set_mode(void * _map,uint32 mode)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
file_map_translate(void * _map,off_t offset,size_t size,file_io_vec * vecs,size_t * _count,size_t align)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