1 /*
2  * COPYRIGHT:        See COPYRIGHT.TXT
3  * PROJECT:          Ext2 File System Driver for WinNT/2K/XP
4  * FILE:             indirect.c
5  * PROGRAMMER:       Matt Wu <mattwu@163.com>
6  * HOMEPAGE:         http://www.ext2fsd.com
7  * UPDATE HISTORY:
8  */
9 
10 /* INCLUDES *****************************************************************/
11 
12 #include "ext2fs.h"
13 
14 /* GLOBALS *****************************************************************/
15 
16 extern PEXT2_GLOBAL Ext2Global;
17 
18 /* DEFINITIONS *************************************************************/
19 
20 #ifdef ALLOC_PRAGMA
21 #endif
22 
23 
24 NTSTATUS
25 Ext2ExpandLast(
26     IN PEXT2_IRP_CONTEXT    IrpContext,
27     IN PEXT2_VCB            Vcb,
28     IN PEXT2_MCB            Mcb,
29     IN ULONG                Base,
30     IN ULONG                Layer,
31     IN PULONG *             Data,
32     IN PULONG               Hint,
33     IN PULONG               Block,
34     IN OUT PULONG           Number
35 )
36 {
37     PULONG      pData = NULL;
38     ULONG       i;
39     NTSTATUS    Status = STATUS_SUCCESS;
40 
41     if (Layer > 0 || IsMcbDirectory(Mcb)) {
42 
43         /* allocate buffer for new block */
44         pData = (ULONG *) Ext2AllocatePool(
45                     PagedPool,
46                     BLOCK_SIZE,
47                     EXT2_DATA_MAGIC
48                 );
49         if (!pData) {
50             DEBUG(DL_ERR, ( "Ex2ExpandBlock: failed to allocate memory for Data.\n"));
51             Status = STATUS_INSUFFICIENT_RESOURCES;
52             goto errorout;
53         }
54         RtlZeroMemory(pData, BLOCK_SIZE);
55         INC_MEM_COUNT(PS_BLOCK_DATA, pData, BLOCK_SIZE);
56     }
57 
58     /* allocate block from disk */
59     Status = Ext2NewBlock(
60                  IrpContext,
61                  Vcb,
62                  (Mcb->Inode.i_ino - 1) / BLOCKS_PER_GROUP,
63                  *Hint,
64                  Block,
65                  Number
66              );
67 
68     if (!NT_SUCCESS(Status)) {
69         goto errorout;
70     }
71 
72     /* increase inode i_blocks */
73     Mcb->Inode.i_blocks += (*Number << (BLOCK_BITS - 9));
74 
75     if (Layer == 0) {
76 
77         if (IsMcbDirectory(Mcb)) {
78             /* for directory we need initialize it's entry structure */
79             PEXT2_DIR_ENTRY2 pEntry;
80             pEntry = (PEXT2_DIR_ENTRY2) pData;
81             pEntry->rec_len = (USHORT)(BLOCK_SIZE);
82             ASSERT(*Number == 1);
83             Ext2SaveBlock(IrpContext, Vcb, *Block, (PVOID)pData);
84         }
85 
86         /* add new Extent into Mcb */
87         if (!Ext2AddBlockExtent(Vcb, Mcb, Base, (*Block), *Number)) {
88             DbgBreak();
89             ClearFlag(Mcb->Flags, MCB_ZONE_INITED);
90             Ext2ClearAllExtents(&Mcb->Extents);
91         }
92 
93     } else {
94 
95         /* zero the content of all meta blocks */
96         for (i = 0; i < *Number; i++) {
97             Ext2SaveBlock(IrpContext, Vcb, *Block + i, (PVOID)pData);
98             /* add block to meta extents */
99             if (!Ext2AddMcbMetaExts(Vcb, Mcb, *Block + i, 1)) {
100                 DbgBreak();
101                 Ext2Sleep(500);
102                 Ext2AddMcbMetaExts(Vcb, Mcb, *Block + i, 1);
103             }
104         }
105     }
106 
107 errorout:
108 
109     if (NT_SUCCESS(Status)) {
110         *Hint = *Block + *Number;
111         if (Data) {
112             *Data = pData;
113             ASSERT(*Number == 1);
114         } else {
115             if (pData) {
116                 Ext2FreePool(pData, EXT2_DATA_MAGIC);
117                 DEC_MEM_COUNT(PS_BLOCK_DATA, pData, BLOCK_SIZE);
118             }
119         }
120     } else {
121         if (pData) {
122             Ext2FreePool(pData, EXT2_DATA_MAGIC);
123             DEC_MEM_COUNT(PS_BLOCK_DATA, pData, BLOCK_SIZE);
124         }
125         if (*Block) {
126             Ext2FreeBlock(IrpContext, Vcb, *Block, *Number);
127             Mcb->Inode.i_blocks -= (*Number << (BLOCK_BITS - 9));
128             *Block = 0;
129         }
130     }
131 
132     return Status;
133 }
134 
135 NTSTATUS
136 Ext2GetBlock(
137     IN PEXT2_IRP_CONTEXT    IrpContext,
138     IN PEXT2_VCB            Vcb,
139     IN PEXT2_MCB            Mcb,
140     IN ULONG                Base,
141     IN ULONG                Layer,
142     IN ULONG                Start,
143     IN ULONG                SizeArray,
144     IN PULONG               BlockArray,
145     IN BOOLEAN              bAlloc,
146     IN OUT PULONG           Hint,
147     OUT PULONG              Block,
148     OUT PULONG              Number
149 )
150 {
151     NTSTATUS    Status = STATUS_SUCCESS;
152     PBCB        Bcb = NULL;
153     PULONG      pData = NULL;
154     ULONG       Slot = 0, i = 0;
155     ULONG       Unit = 1;
156 
157     LARGE_INTEGER Offset;
158 
159     if (Layer == 0) {
160 
161         *Number = 1;
162         if (BlockArray[0] == 0 && bAlloc) {
163 
164             /* now allocate new block */
165             Status = Ext2ExpandLast(
166                          IrpContext,
167                          Vcb,
168                          Mcb,
169                          Base,
170                          Layer,
171                          NULL,
172                          Hint,
173                          &BlockArray[0],
174                          Number
175                      );
176 
177             if (!NT_SUCCESS(Status)) {
178                 goto errorout;
179             }
180         } else {
181             /* check the block is valid or not */
182             if (BlockArray[0] >= TOTAL_BLOCKS) {
183                 DbgBreak();
184                 Status = STATUS_DISK_CORRUPT_ERROR;
185                 goto errorout;
186             }
187         }
188 
189         *Block = BlockArray[0];
190         for (i=1; i < SizeArray; i++) {
191             if (BlockArray[i] == BlockArray[i-1] + 1) {
192                 *Number = *Number + 1;
193             } else {
194                 break;
195             }
196         }
197         *Hint = BlockArray[*Number - 1];
198 
199     } else if (Layer <= 3) {
200 
201         /* check the block is valid or not */
202         if (BlockArray[0] == 0 || BlockArray[0] >= TOTAL_BLOCKS) {
203             DbgBreak();
204             Status = STATUS_DISK_CORRUPT_ERROR;
205             goto errorout;
206         }
207 
208         /* add block to meta extents */
209         if (!Ext2AddMcbMetaExts(Vcb, Mcb, BlockArray[0], 1)) {
210             DbgBreak();
211             Ext2Sleep(500);
212             Ext2AddMcbMetaExts(Vcb, Mcb, BlockArray[0], 1);
213         }
214 
215         /* map memory in cache for the index block */
216         Offset.QuadPart = ((LONGLONG)BlockArray[0]) << BLOCK_BITS;
217         if ( !CcPinRead( Vcb->Volume,
218                          (PLARGE_INTEGER) (&Offset),
219                          BLOCK_SIZE,
220                          PIN_WAIT,
221                          &Bcb,
222                          (void **)&pData )) {
223 
224             DEBUG(DL_ERR, ( "Ext2GetBlock: Failed to PinLock block: %xh ...\n",
225                             BlockArray[0] ));
226             Status = STATUS_CANT_WAIT;
227             goto errorout;
228         }
229 
230         if (Layer > 1) {
231             Unit = Vcb->max_blocks_per_layer[Layer - 1];
232         } else {
233             Unit = 1;
234         }
235 
236         Slot  = Start / Unit;
237         Start = Start % Unit;
238 
239         if (pData[Slot] == 0) {
240 
241             if (bAlloc) {
242 
243                 /* we need allocate new block and zero all data in case
244                    it's an in-direct block. Index stores the new block no. */
245                 ULONG   Count = 1;
246                 Status = Ext2ExpandLast(
247                              IrpContext,
248                              Vcb,
249                              Mcb,
250                              Base,
251                              Layer,
252                              NULL,
253                              Hint,
254                              &pData[Slot],
255                              &Count
256                          );
257 
258                 if (!NT_SUCCESS(Status)) {
259                     goto errorout;
260                 }
261 
262                 /* refresh hint block */
263                 *Hint = pData[Slot];
264 
265                 /* set dirty bit to notify system to flush */
266                 CcSetDirtyPinnedData(Bcb, NULL );
267                 SetFlag(Vcb->Volume->Flags, FO_FILE_MODIFIED);
268                 if (!Ext2AddVcbExtent(Vcb, Offset.QuadPart,
269                                       (LONGLONG)BLOCK_SIZE)) {
270                     DbgBreak();
271                     Ext2Sleep(100);
272                     if (!Ext2AddVcbExtent(Vcb, Offset.QuadPart,
273                                           (LONGLONG)BLOCK_SIZE)) {
274                         Status = STATUS_INSUFFICIENT_RESOURCES;
275                         goto errorout;
276                     }
277                 }
278 
279                 /* save inode information here */
280                 Ext2SaveInode(IrpContext, Vcb, &Mcb->Inode);
281 
282             } else {
283 
284                 *Number = 1;
285 
286                 if (Layer == 1) {
287                     for (i = Slot + 1; i < BLOCK_SIZE/4; i++) {
288                         if (pData[i] == 0) {
289                             *Number = *Number + 1;
290                         } else {
291                             break;
292                         }
293                     }
294                 } else if (Layer == 2) {
295                     *Number = BLOCK_SIZE/4 - Start;
296                 } else {
297                     *Number = BLOCK_SIZE/4;
298                 }
299 
300                 goto errorout;
301             }
302         }
303 
304         /* transfer to next recursion call */
305         Status = Ext2GetBlock(
306                      IrpContext,
307                      Vcb,
308                      Mcb,
309                      Base,
310                      Layer - 1,
311                      Start,
312                      BLOCK_SIZE/4 - Slot,
313                      &pData[Slot],
314                      bAlloc,
315                      Hint,
316                      Block,
317                      Number
318                  );
319 
320         if (!NT_SUCCESS(Status)) {
321             goto errorout;
322         }
323     }
324 
325 errorout:
326 
327     /* free the memory of pData */
328     if (Bcb) {
329         CcUnpinData(Bcb);
330     }
331 
332     if (!NT_SUCCESS(Status)) {
333         *Block = 0;
334     }
335 
336     return Status;
337 }
338 
339 
340 NTSTATUS
341 Ext2ExpandBlock(
342     IN PEXT2_IRP_CONTEXT IrpContext,
343     IN PEXT2_VCB         Vcb,
344     IN PEXT2_MCB         Mcb,
345     IN ULONG             Base,
346     IN ULONG             Layer,
347     IN ULONG             Start,
348     IN ULONG             SizeArray,
349     IN PULONG            BlockArray,
350     IN PULONG            Hint,
351     IN PULONG            Extra
352 )
353 {
354     ULONG       i = 0;
355     ULONG       j;
356     ULONG       Slot;
357     ULONG       Block = 0;
358     LARGE_INTEGER Offset;
359 
360     PBCB        Bcb = NULL;
361     PULONG      pData = NULL;
362     ULONG       Skip = 0;
363 
364     ULONG       Number;
365     ULONG       Wanted;
366 
367     NTSTATUS    Status = STATUS_SUCCESS;
368 
369     if (Layer == 1) {
370 
371         /*
372          * try to make all leaf block continuous to avoid fragments
373          */
374 
375         Number = min(SizeArray, ((*Extra + (Start & (BLOCK_SIZE/4 - 1))) * 4 / BLOCK_SIZE));
376         Wanted = 0;
377         DEBUG(DL_BLK, ("Ext2ExpandBlock: SizeArray=%xh Extra=%xh Start=%xh %xh\n",
378                        SizeArray, *Extra, Start, Number ));
379 
380         for (i=0; i < Number; i++) {
381             if (BlockArray[i] == 0) {
382                 Wanted += 1;
383             }
384         }
385 
386         i = 0;
387         while (Wanted > 0) {
388 
389             Number = Wanted;
390             Status = Ext2ExpandLast(
391                          IrpContext,
392                          Vcb,
393                          Mcb,
394                          Base,
395                          Layer,
396                          NULL,
397                          Hint,
398                          &Block,
399                          &Number
400                      );
401             if (!NT_SUCCESS(Status)) {
402                 goto errorout;
403             }
404 
405             ASSERT(Number > 0);
406             Wanted -= Number;
407             while (Number) {
408                 if (BlockArray[i] == 0) {
409                     BlockArray[i] = Block++;
410                     Number--;
411                 }
412                 i++;
413             }
414         }
415 
416     } else if (Layer == 0) {
417 
418         /*
419          * bulk allocation for inode data blocks
420          */
421 
422         i = 0;
423 
424         while (*Extra && i < SizeArray) {
425 
426             Wanted = 0;
427             Number = 1;
428 
429             for (j = i; j < SizeArray && j < i + *Extra; j++) {
430 
431                 if (BlockArray[j] >= TOTAL_BLOCKS) {
432                     DbgBreak();
433                     BlockArray[j] = 0;
434                 }
435 
436                 if (BlockArray[j] == 0) {
437                     Wanted += 1;
438                 } else {
439                     break;
440                 }
441             }
442 
443             if (Wanted == 0) {
444 
445                 /* add block extent into Mcb */
446                 ASSERT(BlockArray[i] != 0);
447                 if (!Ext2AddBlockExtent(Vcb, Mcb, Base + i, BlockArray[i], 1)) {
448                     DbgBreak();
449                     ClearFlag(Mcb->Flags, MCB_ZONE_INITED);
450                     Ext2ClearAllExtents(&Mcb->Extents);
451                 }
452 
453             } else {
454 
455                 Number = Wanted;
456                 Status = Ext2ExpandLast(
457                              IrpContext,
458                              Vcb,
459                              Mcb,
460                              Base + i,
461                              0,
462                              NULL,
463                              Hint,
464                              &Block,
465                              &Number
466                          );
467                 if (!NT_SUCCESS(Status)) {
468                     goto errorout;
469                 }
470 
471                 ASSERT(Number > 0);
472                 for (j = 0; j < Number; j++) {
473                     BlockArray[i + j] = Block++;
474                 }
475             }
476 
477             *Extra -= Number;
478             i += Number;
479         }
480 
481         goto errorout;
482     }
483 
484 
485     /*
486      * only for meta blocks allocation
487      */
488 
489     for (i = 0; *Extra && i < SizeArray; i++) {
490 
491         if (Layer <= 3) {
492 
493             if (BlockArray[i] >= TOTAL_BLOCKS) {
494                 DbgBreak();
495                 BlockArray[i] = 0;
496             }
497 
498             if (BlockArray[i] == 0) {
499                 Number = 1;
500                 Status = Ext2ExpandLast(
501                              IrpContext,
502                              Vcb,
503                              Mcb,
504                              Base,
505                              Layer,
506                              &pData,
507                              Hint,
508                              &BlockArray[i],
509                              &Number
510                          );
511                 if (!NT_SUCCESS(Status)) {
512                     goto errorout;
513                 }
514 
515             } else {
516 
517                 Offset.QuadPart = (((LONGLONG)BlockArray[i]) << BLOCK_BITS);
518                 if (!CcPinRead(
519                             Vcb->Volume,
520                             &Offset,
521                             BLOCK_SIZE,
522                             PIN_WAIT,
523                             &Bcb,
524                             (void **)&pData )) {
525 
526                     DEBUG(DL_ERR, ( "Ext2ExpandInode: failed to PinLock offset :%I64xh...\n",
527                                     Offset.QuadPart));
528                     Status = STATUS_CANT_WAIT;
529                     DbgBreak();
530                     goto errorout;
531                 }
532 
533                 /* add block to meta extents */
534                 if (!Ext2AddMcbMetaExts(Vcb, Mcb,  BlockArray[i], 1)) {
535                     DbgBreak();
536                     Ext2Sleep(500);
537                     Ext2AddMcbMetaExts(Vcb, Mcb,  BlockArray[i], 1);
538                 }
539             }
540 
541             Skip = Vcb->max_blocks_per_layer[Layer] * i;
542 
543             if (i == 0) {
544                 if (Layer > 1) {
545                     Slot  = Start / Vcb->max_blocks_per_layer[Layer - 1];
546                     Start = Start % Vcb->max_blocks_per_layer[Layer - 1];
547                     Skip += Slot * Vcb->max_blocks_per_layer[Layer - 1];
548                 } else {
549                     Slot  = Start;
550                     Start = 0;
551                     Skip += Slot;
552                 }
553             } else {
554                 Start = 0;
555                 Slot  = 0;
556             }
557 
558             Status = Ext2ExpandBlock(
559                          IrpContext,
560                          Vcb,
561                          Mcb,
562                          Base + Skip,
563                          Layer - 1,
564                          Start,
565                          BLOCK_SIZE/4 - Slot,
566                          &pData[Slot],
567                          Hint,
568                          Extra
569                      );
570 
571             if (Bcb) {
572                 CcSetDirtyPinnedData(Bcb, NULL);
573                 if (!Ext2AddBlockExtent(Vcb, NULL,
574                                         BlockArray[i],
575                                         BlockArray[i], 1)) {
576                     DbgBreak();
577                     Ext2Sleep(500);
578                     if (!Ext2AddBlockExtent(Vcb, NULL,
579                                             BlockArray[i],
580                                             BlockArray[i], 1)) {
581                     }
582                 }
583             } else {
584                 Ext2SaveBlock(IrpContext, Vcb, BlockArray[i], (PVOID)pData);
585             }
586 
587             if (pData) {
588                 if (Bcb) {
589                     CcUnpinData(Bcb);
590                     Bcb = NULL;
591                 } else {
592                     Ext2FreePool(pData, EXT2_DATA_MAGIC);
593                     DEC_MEM_COUNT(PS_BLOCK_DATA, pData, BLOCK_SIZE);
594                 }
595                 pData = NULL;
596             }
597 
598             if (!NT_SUCCESS(Status)) {
599                 DbgBreak();
600                 break;
601             }
602         }
603     }
604 
605 errorout:
606 
607     return Status;
608 }
609 
610 BOOLEAN
611 Ext2IsBlockEmpty(PULONG BlockArray, ULONG SizeArray)
612 {
613     ULONG i = 0;
614     for (i=0; i < SizeArray; i++) {
615         if (BlockArray[i]) {
616             break;
617         }
618     }
619     return (i == SizeArray);
620 }
621 
622 
623 NTSTATUS
624 Ext2TruncateBlock(
625     IN PEXT2_IRP_CONTEXT IrpContext,
626     IN PEXT2_VCB         Vcb,
627     IN PEXT2_MCB         Mcb,
628     IN ULONG             Base,
629     IN ULONG             Start,
630     IN ULONG             Layer,
631     IN ULONG             SizeArray,
632     IN PULONG            BlockArray,
633     IN PULONG            Extra
634 )
635 {
636     NTSTATUS    Status = STATUS_SUCCESS;
637     ULONG       i = 0;
638     ULONG       Slot = 0;
639     ULONG       Skip = 0;
640 
641     LONGLONG    Offset;
642     PBCB        Bcb = NULL;
643     PULONG      pData = NULL;
644 
645     ASSERT(Mcb != NULL);
646 
647     for (i = 0; i < SizeArray; i++) {
648 
649         if (Layer == 0) {
650 
651             ULONG   Number = 1;
652 
653             while (Extra &&  SizeArray > i + 1 && Number < *Extra) {
654 
655                 if (BlockArray[SizeArray - i - 1] ==
656                     BlockArray[SizeArray - i - 2] + 1) {
657 
658                     BlockArray[SizeArray - i - 1] = 0;
659                     Number++;
660                     SizeArray--;
661 
662                 } else {
663                     break;
664                 }
665             }
666 
667             if (BlockArray[SizeArray - i - 1]) {
668 
669                 Status = Ext2FreeBlock(IrpContext, Vcb, BlockArray[SizeArray - i - 1], Number);
670                 if (NT_SUCCESS(Status)) {
671                     ASSERT(Mcb->Inode.i_blocks >= (Number << (BLOCK_BITS - 9)));
672                     if (Mcb->Inode.i_blocks < (Number << (BLOCK_BITS - 9))) {
673                         Mcb->Inode.i_blocks = 0;
674                         DbgBreak();
675                     } else {
676                         Mcb->Inode.i_blocks -= (Number << (BLOCK_BITS - 9));
677                     }
678                     BlockArray[SizeArray - i - 1] = 0;
679                 }
680             }
681 
682             if (Extra) {
683 
684                 /* dec blocks count */
685                 ASSERT(*Extra >= Number);
686                 *Extra = *Extra - Number;
687 
688                 /* remove block mapping frm Mcb Extents */
689                 if (!Ext2RemoveBlockExtent(Vcb, Mcb, Base + SizeArray - 1 - i, Number)) {
690                     DbgBreak();
691                     ClearFlag(Mcb->Flags, MCB_ZONE_INITED);
692                     Ext2ClearAllExtents(&Mcb->Extents);
693                 }
694             }
695 
696         } else {
697 
698             ASSERT(Layer <= 3);
699 
700             if (BlockArray[SizeArray - i - 1] >= TOTAL_BLOCKS) {
701                 DbgBreak();
702                 BlockArray[SizeArray - i - 1] = 0;
703             }
704 
705             if (i == 0) {
706                 if (Layer > 1) {
707                     Slot  = Start / Vcb->max_blocks_per_layer[Layer - 1];
708                     Start = Start % Vcb->max_blocks_per_layer[Layer - 1];
709                 } else {
710                     Slot  = Start;
711                     Start = (BLOCK_SIZE / 4) - 1;
712                 }
713             } else {
714                 Slot = Start = (BLOCK_SIZE / 4) - 1;
715             }
716 
717             Skip = (SizeArray - i - 1) * Vcb->max_blocks_per_layer[Layer];
718 
719             if (BlockArray[SizeArray - i - 1]) {
720 
721                 Offset = (LONGLONG) (BlockArray[SizeArray - i - 1]);
722                 Offset = Offset << BLOCK_BITS;
723 
724                 if (!CcPinRead( Vcb->Volume,
725                                 (PLARGE_INTEGER) (&Offset),
726                                 BLOCK_SIZE,
727                                 PIN_WAIT,
728                                 &Bcb,
729                                 (void **)&pData )) {
730 
731                     DEBUG(DL_ERR, ( "Ext2TruncateBlock: PinLock failed on block %xh ...\n",
732                                     BlockArray[SizeArray - i - 1]));
733                     Status = STATUS_CANT_WAIT;
734                     DbgBreak();
735                     goto errorout;
736                 }
737 
738                 Status = Ext2TruncateBlock(
739                              IrpContext,
740                              Vcb,
741                              Mcb,
742                              Base + Skip,
743                              Start,
744                              Layer - 1,
745                              Slot + 1,
746                              &pData[0],
747                              Extra
748                          );
749 
750                 if (!NT_SUCCESS(Status)) {
751                     break;
752                 }
753 
754                 CcSetDirtyPinnedData(Bcb, NULL);
755                 Ext2AddVcbExtent(Vcb, Offset, (LONGLONG)BLOCK_SIZE);
756 
757                 if (*Extra || Ext2IsBlockEmpty(pData, BLOCK_SIZE/4)) {
758 
759                     Ext2TruncateBlock(
760                                  IrpContext,
761                                  Vcb,
762                                  Mcb,
763                                  Base + Skip,    /* base */
764                                  0,              /* start */
765                                  0,              /* layer */
766                                  1,
767                                  &BlockArray[SizeArray - i - 1],
768                                  NULL
769                              );
770 
771                     if (!Ext2RemoveMcbMetaExts(Vcb, Mcb, BlockArray[SizeArray - i - 1], 1)) {
772                         DbgBreak();
773                         Ext2Sleep(500);
774                         Ext2RemoveMcbMetaExts(Vcb, Mcb, BlockArray[SizeArray - i - 1], 1);
775                     }
776                 }
777 
778                 if (pData) {
779                     CcUnpinData(Bcb);
780                     Bcb = NULL;
781                     pData = NULL;
782                 }
783 
784             } else {
785 
786                 if (Layer > 1) {
787                     if (*Extra > Slot * Vcb->max_blocks_per_layer[Layer - 1] + Start + 1) {
788                         *Extra -= (Slot * Vcb->max_blocks_per_layer[Layer - 1] + Start + 1);
789                     } else {
790                         *Extra  = 0;
791                     }
792                 } else {
793                     if (*Extra > Slot + 1) {
794                         *Extra -= (Slot + 1);
795                     } else {
796                         *Extra  = 0;
797                     }
798                 }
799 
800                 if (!Ext2RemoveBlockExtent(Vcb, Mcb, Base + Skip, (Start + 1))) {
801                     DbgBreak();
802                     ClearFlag(Mcb->Flags, MCB_ZONE_INITED);
803                     Ext2ClearAllExtents(&Mcb->Extents);
804                 }
805             }
806         }
807 
808         if (Extra && *Extra == 0) {
809             break;
810         }
811     }
812 
813 errorout:
814 
815     if (pData) {
816         CcUnpinData(Bcb);
817     }
818 
819     return Status;
820 }
821 
822 NTSTATUS
823 Ext2MapIndirect(
824     IN PEXT2_IRP_CONTEXT    IrpContext,
825     IN PEXT2_VCB            Vcb,
826     IN PEXT2_MCB            Mcb,
827     IN ULONG                Index,
828     IN BOOLEAN              bAlloc,
829     OUT PULONG              pBlock,
830     OUT PULONG              Number
831 )
832 {
833     ULONG   Layer;
834     ULONG   Slot;
835 
836     ULONG   Base = Index;
837 
838     NTSTATUS Status = STATUS_SUCCESS;
839 
840     *pBlock = 0;
841     *Number = 0;
842 
843     for (Layer = 0; Layer < EXT2_BLOCK_TYPES; Layer++) {
844 
845         if (Index < Vcb->max_blocks_per_layer[Layer]) {
846 
847             ULONG   dwRet = 0, dwBlk = 0, dwHint = 0, dwArray = 0;
848 
849             Slot = (Layer==0) ? (Index):(Layer + EXT2_NDIR_BLOCKS - 1);
850             dwBlk = Mcb->Inode.i_block[Slot];
851 
852             if (dwBlk == 0) {
853 
854                 if (!bAlloc) {
855 
856                     *Number = 1;
857                     goto errorout;
858 
859                 } else {
860 
861                     if (Slot) {
862                         dwHint = Mcb->Inode.i_block[Slot - 1];
863                     }
864 
865                     /* allocate and zero block if necessary */
866                     *Number = 1;
867                     Status = Ext2ExpandLast(
868                                  IrpContext,
869                                  Vcb,
870                                  Mcb,
871                                  Base,
872                                  Layer,
873                                  NULL,
874                                  &dwHint,
875                                  &dwBlk,
876                                  Number
877                              );
878 
879                     if (!NT_SUCCESS(Status)) {
880                         goto errorout;
881                     }
882 
883                     /* save the it into inode*/
884                     Mcb->Inode.i_block[Slot] = dwBlk;
885 
886                     /* save the inode */
887                     if (!Ext2SaveInode(IrpContext, Vcb, &Mcb->Inode)) {
888                         DbgBreak();
889                         Status = STATUS_UNSUCCESSFUL;
890                         goto errorout;
891                     }
892                 }
893             }
894 
895             if (Layer == 0)
896                 dwArray = Vcb->max_blocks_per_layer[Layer] - Index;
897             else
898                 dwArray = 1;
899 
900             /* querying block number of the index-th file block */
901             Status = Ext2GetBlock(
902                          IrpContext,
903                          Vcb,
904                          Mcb,
905                          Base,
906                          Layer,
907                          Index,
908                          dwArray,
909                         (PULONG)&Mcb->Inode.i_block[Slot],
910                          bAlloc,
911                          &dwHint,
912                          &dwRet,
913                          Number
914                      );
915 
916             if (NT_SUCCESS(Status)) {
917                 *pBlock = dwRet;
918             }
919 
920             break;
921         }
922 
923         Index -= Vcb->max_blocks_per_layer[Layer];
924     }
925 
926 errorout:
927 
928     return Status;
929 }
930 
931 NTSTATUS
932 Ext2ExpandIndirect(
933     PEXT2_IRP_CONTEXT IrpContext,
934     PEXT2_VCB         Vcb,
935     PEXT2_MCB         Mcb,
936     ULONG             Start,
937     ULONG             End,
938     PLARGE_INTEGER    Size
939 )
940 {
941     NTSTATUS Status = STATUS_SUCCESS;
942 
943     ULONG    Layer = 0;
944     ULONG    Extra = 0;
945     ULONG    Hint = 0;
946     ULONG    Slot = 0;
947     ULONG    Base = 0;
948 
949     Extra = End - Start;
950 
951 	/* exceeds the biggest file size (indirect) */
952     if (End > Vcb->max_data_blocks) {
953         return STATUS_INVALID_PARAMETER;
954     }
955 
956     for (Layer = 0; Layer < EXT2_BLOCK_TYPES && Extra; Layer++) {
957 
958         if (Start >= Vcb->max_blocks_per_layer[Layer]) {
959 
960             Base  += Vcb->max_blocks_per_layer[Layer];
961             Start -= Vcb->max_blocks_per_layer[Layer];
962 
963         } else {
964 
965             /* get the slot in i_block array */
966             if (Layer == 0) {
967                 Base = Slot = Start;
968             } else {
969                 Slot = Layer + EXT2_NDIR_BLOCKS - 1;
970             }
971 
972             /* set block hint to avoid fragments */
973             if (Hint == 0) {
974                 if (Mcb->Inode.i_block[Slot] != 0) {
975                     Hint = Mcb->Inode.i_block[Slot];
976                 } else if (Slot > 1) {
977                     Hint = Mcb->Inode.i_block[Slot-1];
978                 }
979             }
980 
981             /* now expand this slot */
982             Status = Ext2ExpandBlock(
983                          IrpContext,
984                          Vcb,
985                          Mcb,
986                          Base,
987                          Layer,
988                          Start,
989                          (Layer == 0) ? (Vcb->max_blocks_per_layer[Layer] - Start) : 1,
990                          (PULONG)&Mcb->Inode.i_block[Slot],
991                          &Hint,
992                          &Extra
993                      );
994             if (!NT_SUCCESS(Status)) {
995                 break;
996             }
997 
998             Start = 0;
999             if (Layer == 0) {
1000                 Base = 0;
1001             }
1002             Base += Vcb->max_blocks_per_layer[Layer];
1003         }
1004     }
1005 
1006     Size->QuadPart = ((LONGLONG)(End - Extra)) << BLOCK_BITS;
1007 
1008     /* save inode whatever it succeeds to expand or not */
1009     Ext2SaveInode(IrpContext, Vcb, &Mcb->Inode);
1010 
1011     return Status;
1012 }
1013 
1014 NTSTATUS
1015 Ext2TruncateIndirectFast(
1016     PEXT2_IRP_CONTEXT IrpContext,
1017     PEXT2_VCB         Vcb,
1018     PEXT2_MCB         Mcb
1019     )
1020 {
1021     LONGLONG            Vba;
1022     LONGLONG            Lba;
1023     LONGLONG            Length;
1024     NTSTATUS            Status = STATUS_SUCCESS;
1025     int                 i;
1026 
1027     /* try to load all indirect blocks if mcb zone is not initialized */
1028     if (!IsZoneInited(Mcb)) {
1029         Status = Ext2InitializeZone(IrpContext, Vcb, Mcb);
1030         if (!NT_SUCCESS(Status)) {
1031             DbgBreak();
1032             ClearLongFlag(Mcb->Flags, MCB_ZONE_INITED);
1033             goto errorout;
1034         }
1035     }
1036 
1037     ASSERT (IsZoneInited(Mcb));
1038 
1039     /* delete all data blocks here */
1040     if (FsRtlNumberOfRunsInLargeMcb(&Mcb->Extents) != 0) {
1041         for (i = 0; FsRtlGetNextLargeMcbEntry(&Mcb->Extents, i, &Vba, &Lba, &Length); i++) {
1042             /* ignore the non-existing runs */
1043             if (-1 == Lba || Vba == 0 || Length <= 0)
1044                 continue;
1045             /* now do data block free */
1046             Ext2FreeBlock(IrpContext, Vcb, (ULONG)(Lba - 1), (ULONG)Length);
1047         }
1048     }
1049 
1050     /* delete all meta blocks here */
1051     if (FsRtlNumberOfRunsInLargeMcb(&Mcb->MetaExts) != 0) {
1052         for (i = 0; FsRtlGetNextLargeMcbEntry(&Mcb->MetaExts, i, &Vba, &Lba, &Length); i++) {
1053             /* ignore the non-existing runs */
1054             if (-1 == Lba || Vba == 0 || Length <= 0)
1055                 continue;
1056             /* now do meta block free */
1057             Ext2FreeBlock(IrpContext, Vcb, (ULONG)(Lba - 1), (ULONG)Length);
1058         }
1059     }
1060 
1061     /* clear data and meta extents */
1062     Ext2ClearAllExtents(&Mcb->Extents);
1063     Ext2ClearAllExtents(&Mcb->MetaExts);
1064     ClearFlag(Mcb->Flags, MCB_ZONE_INITED);
1065 
1066     /* clear inode blocks & sizes */
1067     Mcb->Inode.i_blocks = 0;
1068     Mcb->Inode.i_size = 0;
1069     memset(&Mcb->Inode.i_block[0], 0, sizeof(__u32) * 15);
1070 
1071     /* the caller will do inode save */
1072 
1073 errorout:
1074 
1075     return Status;
1076 }
1077 
1078 NTSTATUS
1079 Ext2TruncateIndirect(
1080     PEXT2_IRP_CONTEXT IrpContext,
1081     PEXT2_VCB         Vcb,
1082     PEXT2_MCB         Mcb,
1083     PLARGE_INTEGER    Size
1084 )
1085 {
1086     NTSTATUS Status = STATUS_SUCCESS;
1087 
1088     ULONG    Layer = 0;
1089 
1090     ULONG    Extra = 0;
1091     ULONG    Wanted = 0;
1092     ULONG    End;
1093     ULONG    Base;
1094 
1095     ULONG    SizeArray = 0;
1096     PULONG   BlockArray = NULL;
1097 
1098     /* translate file size to block */
1099     End = Base = Vcb->max_data_blocks;
1100     Wanted = (ULONG)((Size->QuadPart + BLOCK_SIZE - 1) >> BLOCK_BITS);
1101 
1102     /* do fast deletion here */
1103     if (Wanted == 0) {
1104         Status = Ext2TruncateIndirectFast(IrpContext, Vcb, Mcb);
1105         if (NT_SUCCESS(Status))
1106             goto errorout;
1107     }
1108 
1109     /* calculate blocks to be freed */
1110     Extra = End - Wanted;
1111 
1112     for (Layer = EXT2_BLOCK_TYPES; Layer > 0 && Extra; Layer--) {
1113 
1114         if (Vcb->max_blocks_per_layer[Layer - 1] == 0) {
1115             continue;
1116         }
1117 
1118         Base -= Vcb->max_blocks_per_layer[Layer - 1];
1119 
1120         if (Layer - 1 == 0) {
1121             BlockArray = (PULONG)&Mcb->Inode.i_block[0];
1122             SizeArray = End;
1123             ASSERT(End == EXT2_NDIR_BLOCKS && Base == 0);
1124         } else {
1125             BlockArray = (PULONG)&Mcb->Inode.i_block[EXT2_NDIR_BLOCKS - 1 + Layer - 1];
1126             SizeArray = 1;
1127         }
1128 
1129         Status = Ext2TruncateBlock(
1130                      IrpContext,
1131                      Vcb,
1132                      Mcb,
1133                      Base,
1134                      End - Base - 1,
1135                      Layer - 1,
1136                      SizeArray,
1137                      BlockArray,
1138                      &Extra
1139                  );
1140         if (!NT_SUCCESS(Status)) {
1141             break;
1142         }
1143 
1144         End = Base;
1145     }
1146 
1147 errorout:
1148 
1149     if (!NT_SUCCESS(Status)) {
1150         Size->QuadPart += ((ULONGLONG)Extra << BLOCK_BITS);
1151     }
1152 
1153     /* save inode */
1154     if (Mcb->Inode.i_size > (loff_t)(Size->QuadPart))
1155         Mcb->Inode.i_size = (loff_t)(Size->QuadPart);
1156     Ext2SaveInode(IrpContext, Vcb, &Mcb->Inode);
1157 
1158     return Status;
1159 }
1160