1 /*
2 * Copyright 2001-2011, Haiku Inc. All rights reserved.
3 * This file may be used under the terms of the MIT License.
4 *
5 * Authors:
6 * Jérôme Duval
7 */
8
9
10 #include "ExtentStream.h"
11
12 #include <string.h>
13
14 #include "CachedBlock.h"
15 #include "Inode.h"
16 #include "Volume.h"
17
18
19 #undef ASSERT
20 //#define TRACE_EXT2
21 #ifdef TRACE_EXT2
22 # define TRACE(x...) dprintf("\33[34mext2:\33[0m ExtentStream::" x)
23 # define ASSERT(x) { if (!(x)) kernel_debugger("ext2: assert failed: " #x "\n"); }
24 #else
25 # define TRACE(x...) ;
26 # define ASSERT(x) ;
27 #endif
28 #define ERROR(x...) dprintf("\33[34mext2:\33[0m ExtentStream::" x)
29
30
ExtentStream(Volume * volume,Inode * inode,ext2_extent_stream * stream,off_t size)31 ExtentStream::ExtentStream(Volume* volume, Inode* inode,
32 ext2_extent_stream* stream, off_t size)
33 :
34 fVolume(volume),
35 fInode(inode),
36 fStream(stream),
37 fFirstBlock(volume->FirstDataBlock()),
38 fAllocatedPos(fFirstBlock),
39 fSize(size)
40 {
41 fNumBlocks = size == 0 ? 0 : ((size - 1) >> fVolume->BlockShift()) + 1;
42 }
43
44
~ExtentStream()45 ExtentStream::~ExtentStream()
46 {
47 }
48
49
50 status_t
FindBlock(off_t offset,fsblock_t & block,uint32 * _count)51 ExtentStream::FindBlock(off_t offset, fsblock_t& block, uint32 *_count)
52 {
53 fileblock_t index = offset >> fVolume->BlockShift();
54 TRACE("FindBlock(%" B_PRIdOFF ", %" B_PRIu64 ")\n", offset, index);
55
56 if (offset >= fSize) {
57 TRACE("FindBlock: offset larger than inode size\n");
58 return B_ENTRY_NOT_FOUND;
59 }
60
61 ext2_extent_stream *stream = fStream;
62 if (!stream->extent_header.IsValid())
63 panic("ExtentStream::FindBlock() invalid header\n");
64
65 CachedBlock cached(fVolume);
66 while (stream->extent_header.Depth() != 0) {
67 TRACE("FindBlock() depth %d\n",
68 stream->extent_header.Depth());
69 int32 i = 1;
70 while (i < stream->extent_header.NumEntries()
71 && stream->extent_index[i].LogicalBlock() <= index) {
72 i++;
73 }
74 TRACE("FindBlock() getting index %" B_PRId32 " at %" B_PRIu64 "\n",
75 i - 1, stream->extent_index[i - 1].PhysicalBlock());
76 stream = (ext2_extent_stream *)cached.SetTo(
77 stream->extent_index[i - 1].PhysicalBlock());
78 if (!stream->extent_header.IsValid())
79 panic("ExtentStream::FindBlock() invalid header\n");
80 if (!fInode->VerifyExtentChecksum(stream)) {
81 panic("ExtentStream::FindBlock() invalid checksum\n");
82 return B_BAD_DATA;
83 }
84 }
85
86 // find the extend following the one that should contain the logical block
87 int32 extentIndex;
88 if (stream->extent_header.NumEntries() > 7) {
89 // binary search when enough entries
90 int32 low = 0;
91 int32 high = stream->extent_header.NumEntries() - 1;
92 while (low < high) {
93 int32 middle = (high + low + 1) / 2;
94 if (stream->extent_entries[middle].LogicalBlock() > index)
95 high = middle - 1;
96 else
97 low = middle;
98 }
99
100 extentIndex = low + 1;
101 } else {
102 extentIndex = stream->extent_header.NumEntries();
103 for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) {
104 if (stream->extent_entries[i].LogicalBlock() > index) {
105 extentIndex = i;
106 break;
107 }
108 }
109 }
110
111 fileblock_t logicalEndIndex
112 = (fSize + fVolume->BlockSize() - 1) >> fVolume->BlockShift();
113
114 if (extentIndex == 0) {
115 // sparse block at the beginning of the stream
116 block = 0;
117 if (_count != NULL) {
118 *_count = stream->extent_header.NumEntries() == 0
119 ? logicalEndIndex - index
120 : stream->extent_entries[0].LogicalBlock() - index;
121 }
122 TRACE("FindBlock() sparse block index %" B_PRIu64 " at beginning of "
123 "stream\n", index);
124 return B_OK;
125 }
126
127 const ext2_extent_entry& extent = stream->extent_entries[extentIndex - 1];
128 // the extent supposedly containing the offset
129 fileblock_t diff = index - extent.LogicalBlock();
130 if (diff >= extent.Length()) {
131 // sparse block between extends or at the end of the stream
132 TRACE("FindBlock() sparse block index %" B_PRIu64 " at %" B_PRIu32
133 "\n", index, extent.LogicalBlock());
134 block = 0;
135 if (_count != NULL) {
136 *_count = stream->extent_header.NumEntries() == extentIndex
137 ? logicalEndIndex - index
138 : stream->extent_entries[extentIndex].LogicalBlock() - index;
139 }
140 return B_OK;
141 }
142
143 block = extent.PhysicalBlock() + diff;
144 if (_count != NULL)
145 *_count = extent.Length() - diff;
146
147 TRACE("FindBlock(offset %" B_PRIdOFF "): %" B_PRIu64 " %" B_PRIu32
148 "\n", offset, block, _count != NULL ? *_count : 1);
149
150 return B_OK;
151 }
152
153
154 status_t
Enlarge(Transaction & transaction,off_t & numBlocks)155 ExtentStream::Enlarge(Transaction& transaction, off_t& numBlocks)
156 {
157 TRACE("Enlarge(): current size: %" B_PRIdOFF ", target size: %" B_PRIdOFF
158 "\n", fNumBlocks, numBlocks);
159
160 off_t targetBlocks = numBlocks;
161 numBlocks = targetBlocks - fNumBlocks;
162 uint32 allocated = 0;
163
164 while (fNumBlocks < targetBlocks) {
165 // allocate new blocks
166 uint32 blockGroup = (fAllocatedPos - fFirstBlock)
167 / fVolume->BlocksPerGroup();
168
169 if (allocated == 0) {
170 status_t status = fVolume->AllocateBlocks(transaction, 1,
171 targetBlocks - fNumBlocks, blockGroup, fAllocatedPos,
172 allocated);
173 if (status != B_OK) {
174 ERROR("Enlarge(): AllocateBlocks() failed()\n");
175 return status;
176 }
177 }
178
179 ASSERT(_CheckBlock(fStream, fAllocatedPos) == B_OK);
180
181 ext2_extent_stream *stream = fStream;
182 fsblock_t path[stream->extent_header.Depth()];
183
184 // search for the leaf
185 CachedBlock cached(fVolume);
186 int32 level = -1;
187 for (; stream->extent_header.Depth() != 0;) {
188 if (stream->extent_header.NumEntries() == 0)
189 panic("stream->extent_header.NumEntries() == 0\n");
190 int32 lastIndex = stream->extent_header.NumEntries() - 1;
191 TRACE("Enlarge() depth %d\n", stream->extent_header.Depth());
192 TRACE("Enlarge() getting index %" B_PRId32 " at %" B_PRIu64 "\n",
193 lastIndex, stream->extent_index[lastIndex].PhysicalBlock());
194 path[++level] = stream->extent_index[lastIndex].PhysicalBlock();
195 stream = (ext2_extent_stream *)cached.SetTo(path[level]);
196 if (stream == NULL)
197 return B_IO_ERROR;
198 }
199
200 // check if the new extent is adjacent
201 if (stream->extent_header.NumEntries() > 0) {
202 ext2_extent_entry &last = stream->extent_entries[
203 stream->extent_header.NumEntries() - 1];
204 TRACE("Enlarge() last %" B_PRIu64 " allocatedPos %" B_PRIu64 "\n",
205 last.PhysicalBlock() + last.Length(), fAllocatedPos);
206 if (last.PhysicalBlock() + last.Length() == fAllocatedPos
207 && (last.Length() + allocated) <= EXT2_EXTENT_MAX_LENGTH) {
208 if (stream != fStream) {
209 stream = (ext2_extent_stream *)cached.SetToWritable(
210 transaction, cached.BlockNumber());
211 if (stream == NULL)
212 return B_IO_ERROR;
213 }
214 stream->extent_entries[stream->extent_header.NumEntries() - 1]
215 .SetLength(last.Length() + allocated);
216 fInode->SetExtentChecksum(stream);
217 fNumBlocks += allocated;
218 allocated = 0;
219 TRACE("Enlarge() entry extended\n");
220 continue;
221 }
222 }
223
224 if (stream->extent_header.NumEntries()
225 >= stream->extent_header.MaxEntries()) {
226 TRACE("Enlarge() adding leaf and indexes at depth %d level %"
227 B_PRId32 "\n", stream->extent_header.Depth(), level);
228 // try to add a leaf and indexes
229 while (--level >= 0) {
230 stream = (ext2_extent_stream *)cached.SetTo(path[level]);
231 if (stream == NULL)
232 return B_IO_ERROR;
233 if (stream->extent_header.NumEntries()
234 < stream->extent_header.MaxEntries()) {
235 break;
236 }
237 TRACE("Enlarge() going up from level %" B_PRId32 "\n", level);
238 }
239
240 if (level < 0 && fStream->extent_header.NumEntries()
241 >= fStream->extent_header.MaxEntries()) {
242 TRACE("Enlarge() add a level, increment root depth\n");
243 fsblock_t newBlock = fStream->extent_index[0].PhysicalBlock();
244 uint32 _allocated;
245 status_t status = fVolume->AllocateBlocks(transaction, 1, 1,
246 blockGroup, newBlock, _allocated);
247 if (status != B_OK) {
248 ERROR("Enlarge() AllocateBlocks() failed()\n");
249 return status;
250 }
251 ASSERT(_CheckBlock(fStream, newBlock) == B_OK);
252 TRACE("Enlarge() move root to block %" B_PRIu64 "\n",
253 newBlock);
254 numBlocks++;
255 stream = (ext2_extent_stream *)cached.SetToWritable(
256 transaction, newBlock);
257 if (stream == NULL)
258 return B_IO_ERROR;
259 ASSERT(fStream->extent_header.IsValid());
260 memcpy(stream, fStream, sizeof(ext2_extent_stream));
261 fStream->extent_header.SetDepth(stream->extent_header.Depth()
262 + 1);
263 TRACE("Enlarge() new root depth %d\n",
264 fStream->extent_header.Depth());
265 fStream->extent_header.SetNumEntries(1);
266 fStream->extent_index[0].SetLogicalBlock(0);
267 fStream->extent_index[0].SetPhysicalBlock(newBlock);
268 stream->extent_header.SetMaxEntries((fVolume->BlockSize()
269 - sizeof(ext2_extent_header)) / sizeof(ext2_extent_index));
270 fInode->SetExtentChecksum(stream);
271 ASSERT(stream->extent_header.IsValid());
272
273 ASSERT(Check());
274 continue;
275 }
276
277 if (level < 0)
278 stream = fStream;
279
280 uint16 depth = stream->extent_header.Depth();
281 while (depth > 1) {
282 TRACE("Enlarge() adding an index block at depth %d\n", depth);
283 fsblock_t newBlock = path[level];
284 uint32 _allocated;
285 status_t status = fVolume->AllocateBlocks(transaction, 1, 1,
286 blockGroup, newBlock, _allocated);
287 if (status != B_OK) {
288 ERROR("Enlarge(): AllocateBlocks() failed()\n");
289 return status;
290 }
291 ASSERT(_CheckBlock(fStream, newBlock) == B_OK);
292 numBlocks++;
293 int32 index = stream->extent_header.NumEntries();
294 stream->extent_index[index].SetLogicalBlock(fNumBlocks);
295 stream->extent_index[index].SetPhysicalBlock(newBlock);
296 stream->extent_header.SetNumEntries(index + 1);
297 fInode->SetExtentChecksum(stream);
298 path[level++] = newBlock;
299
300 depth = stream->extent_header.Depth() - 1;
301 TRACE("Enlarge() init index block %" B_PRIu64 " at depth %d\n",
302 newBlock, depth);
303 stream = (ext2_extent_stream *)cached.SetToWritable(
304 transaction, newBlock);
305 if (stream == NULL)
306 return B_IO_ERROR;
307 stream->extent_header.magic = EXT2_EXTENT_MAGIC;
308 stream->extent_header.SetNumEntries(0);
309 stream->extent_header.SetMaxEntries((fVolume->BlockSize()
310 - sizeof(ext2_extent_header)) / sizeof(ext2_extent_index));
311 stream->extent_header.SetDepth(depth);
312 stream->extent_header.SetGeneration(0);
313 fInode->SetExtentChecksum(stream);
314
315 ASSERT(Check());
316 }
317
318 TRACE("Enlarge() depth %d level %" B_PRId32 "\n",
319 stream->extent_header.Depth(), level);
320
321 if (stream->extent_header.Depth() == 1) {
322 TRACE("Enlarge() adding an entry block at depth %d level %"
323 B_PRId32 "\n", depth, level);
324 fsblock_t newBlock;
325 if (level >= 0)
326 newBlock = path[level];
327 else
328 newBlock = fStream->extent_index[0].PhysicalBlock();
329 uint32 _allocated;
330 status_t status = fVolume->AllocateBlocks(transaction, 1, 1,
331 blockGroup, newBlock, _allocated);
332 if (status != B_OK) {
333 ERROR("Enlarge(): AllocateBlocks() failed()\n");
334 return status;
335 }
336
337 ASSERT(_CheckBlock(fStream, newBlock) == B_OK);
338 numBlocks++;
339 int32 index = stream->extent_header.NumEntries();
340 stream->extent_index[index].SetLogicalBlock(fNumBlocks);
341 stream->extent_index[index].SetPhysicalBlock(newBlock);
342 stream->extent_header.SetNumEntries(index + 1);
343 fInode->SetExtentChecksum(stream);
344
345 TRACE("Enlarge() init entry block %" B_PRIu64
346 " at depth %d\n", newBlock, depth);
347 stream = (ext2_extent_stream *)cached.SetToWritable(
348 transaction, newBlock);
349 if (stream == NULL)
350 return B_IO_ERROR;
351 stream->extent_header.magic = EXT2_EXTENT_MAGIC;
352 stream->extent_header.SetNumEntries(0);
353 stream->extent_header.SetMaxEntries((fVolume->BlockSize()
354 - sizeof(ext2_extent_header)) / sizeof(ext2_extent_entry));
355 stream->extent_header.SetDepth(0);
356 stream->extent_header.SetGeneration(0);
357 fInode->SetExtentChecksum(stream);
358 ASSERT(Check());
359 }
360 }
361
362 // add a new entry
363 TRACE("Enlarge() add entry %" B_PRIu64 "\n", fAllocatedPos);
364 if (stream != fStream) {
365 stream = (ext2_extent_stream *)cached.SetToWritable(
366 transaction, cached.BlockNumber());
367 if (stream == NULL)
368 return B_IO_ERROR;
369 }
370 int32 index = stream->extent_header.NumEntries();
371 stream->extent_entries[index].SetLogicalBlock(fNumBlocks);
372 stream->extent_entries[index].SetLength(allocated);
373 stream->extent_entries[index].SetPhysicalBlock(fAllocatedPos);
374 stream->extent_header.SetNumEntries(index + 1);
375 fInode->SetExtentChecksum(stream);
376 TRACE("Enlarge() entry added at index %" B_PRId32 "\n", index);
377 ASSERT(stream->extent_header.IsValid());
378
379 fNumBlocks += allocated;
380 allocated = 0;
381 }
382
383 return B_OK;
384 }
385
386
387 status_t
Shrink(Transaction & transaction,off_t & numBlocks)388 ExtentStream::Shrink(Transaction& transaction, off_t& numBlocks)
389 {
390 TRACE("DataStream::Shrink(): current size: %" B_PRIdOFF ", target size: %"
391 B_PRIdOFF "\n", fNumBlocks, numBlocks);
392
393 off_t targetBlocks = numBlocks;
394 numBlocks = fNumBlocks - targetBlocks;
395
396 while (targetBlocks < fNumBlocks) {
397 ext2_extent_stream *stream = fStream;
398 fsblock_t path[stream->extent_header.Depth()];
399
400 // search for the leaf
401 CachedBlock cached(fVolume);
402 int32 level = -1;
403 for (; stream->extent_header.Depth() != 0;) {
404 if (stream->extent_header.NumEntries() == 0)
405 panic("stream->extent_header.NumEntries() == 0\n");
406 int32 lastIndex = stream->extent_header.NumEntries() - 1;
407 TRACE("Shrink() depth %d\n", stream->extent_header.Depth());
408 TRACE("Shrink() getting index %" B_PRId32 " at %" B_PRIu64 "\n",
409 lastIndex, stream->extent_index[lastIndex].PhysicalBlock());
410 path[++level] = stream->extent_index[lastIndex].PhysicalBlock();
411 stream = (ext2_extent_stream *)cached.SetToWritable(transaction,
412 path[level]);
413 if (stream == NULL)
414 return B_IO_ERROR;
415 if (!stream->extent_header.IsValid())
416 panic("Shrink() invalid header\n");
417 }
418
419 int32 index = stream->extent_header.NumEntries() - 1;
420 status_t status = B_OK;
421 while (index >= 0 && targetBlocks < fNumBlocks) {
422 ext2_extent_entry &last = stream->extent_entries[index];
423 if (last.LogicalBlock() + last.Length() < targetBlocks) {
424 status = B_BAD_DATA;
425 break;
426 }
427 uint16 length = min_c(last.Length(), fNumBlocks - targetBlocks);
428 fsblock_t block = last.PhysicalBlock() + last.Length() - length;
429 TRACE("Shrink() free block %" B_PRIu64 " length %d\n", block,
430 length);
431 status = fVolume->FreeBlocks(transaction, block, length);
432 if (status != B_OK)
433 break;
434 fNumBlocks -= length;
435 stream->extent_entries[index].SetLength(last.Length() - length);
436 TRACE("Shrink() new length for %" B_PRId32 ": %d\n", index, last.Length());
437 if (last.Length() != 0)
438 break;
439 index--;
440 TRACE("Shrink() next index: %" B_PRId32 "\n", index);
441 }
442 TRACE("Shrink() new entry count: %" B_PRId32 "\n", index + 1);
443 stream->extent_header.SetNumEntries(index + 1);
444 fInode->SetExtentChecksum(stream);
445 ASSERT(Check());
446
447 if (status != B_OK)
448 return status;
449
450 while (stream != fStream && stream->extent_header.NumEntries() == 0) {
451 TRACE("Shrink() empty leaf at depth %d\n",
452 stream->extent_header.Depth());
453 level--;
454 if (level >= 0) {
455 stream = (ext2_extent_stream *)cached.SetToWritable(
456 transaction, path[level]);
457 if (stream == NULL)
458 return B_IO_ERROR;
459 } else
460 stream = fStream;
461 if (!stream->extent_header.IsValid())
462 panic("Shrink() invalid header\n");
463 uint16 index = stream->extent_header.NumEntries() - 1;
464 ext2_extent_index &last = stream->extent_index[index];
465 if (last.PhysicalBlock() != path[level + 1])
466 panic("Shrink() last.PhysicalBlock() != path[level + 1]\n");
467 status = fVolume->FreeBlocks(transaction, last.PhysicalBlock(), 1);
468 if (status != B_OK)
469 return status;
470 numBlocks++;
471 stream->extent_header.SetNumEntries(index);
472 fInode->SetExtentChecksum(stream);
473 TRACE("Shrink() new entry count: %d\n", index);
474 }
475 if (stream == fStream && stream->extent_header.NumEntries() == 0)
476 stream->extent_header.SetDepth(0);
477
478 ASSERT(Check());
479 }
480
481 return B_OK;
482 }
483
484
485 void
Init()486 ExtentStream::Init()
487 {
488 fStream->extent_header.magic = EXT2_EXTENT_MAGIC;
489 fStream->extent_header.SetNumEntries(0);
490 fStream->extent_header.SetMaxEntries(4);
491 fStream->extent_header.SetDepth(0);
492 fStream->extent_header.SetGeneration(0);
493 fInode->SetExtentChecksum(fStream);
494 }
495
496
497 status_t
_Check(ext2_extent_stream * stream,fileblock_t & block)498 ExtentStream::_Check(ext2_extent_stream *stream, fileblock_t &block)
499 {
500 if (!stream->extent_header.IsValid()) {
501 panic("_Check() invalid header\n");
502 return B_BAD_VALUE;
503 }
504 if (stream->extent_header.Depth() == 0) {
505 for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) {
506 ext2_extent_entry &entry = stream->extent_entries[i];
507 if (entry.LogicalBlock() < block) {
508 panic("_Check() entry %" B_PRId32 " %" B_PRIu64 " %" B_PRIu32
509 "\n", i, block, entry.LogicalBlock());
510 return B_BAD_VALUE;
511 }
512 block = entry.LogicalBlock() + entry.Length();
513 }
514 return B_OK;
515 }
516
517 CachedBlock cached(fVolume);
518 for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) {
519 ext2_extent_index &index = stream->extent_index[i];
520 if (index.LogicalBlock() < block) {
521 panic("_Check() index %" B_PRId32 " %" B_PRIu64 " %" B_PRIu32
522 "\n", i, block, index.LogicalBlock());
523 return B_BAD_VALUE;
524 }
525 ext2_extent_stream *child = (ext2_extent_stream *)cached.SetTo(
526 index.PhysicalBlock());
527 if (child->extent_header.Depth() != (stream->extent_header.Depth() - 1)
528 || _Check(child, block) != B_OK)
529 return B_BAD_VALUE;
530 }
531 return B_OK;
532 }
533
534
535 bool
Check()536 ExtentStream::Check()
537 {
538 fileblock_t block = 0;
539 return _Check(fStream, block) == B_OK;
540 }
541
542
543 status_t
_CheckBlock(ext2_extent_stream * stream,fsblock_t block)544 ExtentStream::_CheckBlock(ext2_extent_stream *stream, fsblock_t block)
545 {
546 if (stream->extent_header.Depth() == 0) {
547 for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) {
548 ext2_extent_entry &entry = stream->extent_entries[i];
549 if (entry.PhysicalBlock() <= block
550 && (entry.PhysicalBlock() + entry.Length()) > block) {
551 panic("_CheckBlock() entry %" B_PRId32 " %" B_PRIu64 " %"
552 B_PRIu64 " %d\n", i, block, entry.PhysicalBlock(),
553 entry.Length());
554 return B_BAD_VALUE;
555 }
556 }
557 return B_OK;
558 }
559
560 CachedBlock cached(fVolume);
561 for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) {
562 ext2_extent_index &index = stream->extent_index[i];
563 if (index.PhysicalBlock() == block) {
564 panic("_CheckBlock() index %" B_PRId32 " %" B_PRIu64 "\n", i, block);
565 return B_BAD_VALUE;
566 }
567 ext2_extent_stream *child = (ext2_extent_stream *)cached.SetTo(
568 index.PhysicalBlock());
569 if (child->extent_header.Depth() != (stream->extent_header.Depth() - 1)
570 || _CheckBlock(child, block) != B_OK)
571 return B_BAD_VALUE;
572 }
573 return B_OK;
574 }
575
576