Changes to speed up FindGap.

[KeepingRealBusy]

Jeroen,

Here is the code for FindGapOld - only added ShowDebug statements to compare New and Old.

Dave.

Code:

/* Look for a gap, a block of empty clusters on the volume.
   MinimumLcn: Start scanning for gaps at this location. If there is a gap
     at this location then return it. Zero is the begin of the disk.
   MaximumLcn: Stop scanning for gaps at this location. Zero is the end of
     the disk.
   MinimumSize: The gap must have at least this many contiguous free clusters.
     Zero will match any gap, so will return the first gap at or above
     MinimumLcn.
   MustFit: if YES then only return a gap that is bigger/equal than the
     MinimumSize. If NO then return a gap bigger/equal than MinimumSize,
     or if no such gap is found return the largest gap on the volume (above
     MinimumLcn).
   FindHighestGap: if NO then return the lowest gap that is bigger/equal
     than the MinimumSize. If YES then return the highest gap.
   Return YES if succes, NO if no gap was found or an error occurred.
   The routine asks Windows for the cluster bitmap every time. It would be
   faster to cache the bitmap in memory, but that would cause more fails
   because of stale information.
   */
int FindGapOld(
    struct DefragDataStruct *Data,
    ULONG64 MinimumLcn,          /* Gap must be at or above this LCN. */
    ULONG64 MaximumLcn,          /* Gap must be below this LCN. */
    ULONG64 MinimumSize,         /* Gap must be at least this big. */
    int MustFit,                 /* YES: gap must be at least MinimumSize. */
    int FindHighestGap,          /* YES: return the last gap that fits. */
    ULONG64 *BeginLcn,           /* Result, LCN of begin of cluster. */
    ULONG64 *EndLcn,             /* Result, LCN of end of cluster. */
    BOOL IgnoreMftExcludes) {
  STARTING_LCN_INPUT_BUFFER BitmapParam;
  struct {
    ULONG64 StartingLcn;
    ULONG64 BitmapSize;
    BYTE Buffer[65536];               /* Most efficient if binary multiple. */
    } BitmapData;
  ULONG64 Lcn;
  ULONG64 ClusterStart;
  ULONG64 HighestBeginLcn;
  ULONG64 HighestEndLcn;
  ULONG64 LargestBeginLcn;
  ULONG64 LargestEndLcn;
  int Index;
  int IndexMax;
  BYTE Mask;
  int InUse;
  int PrevInUse;
  DWORD ErrorCode;
  WCHAR s1[BUFSIZ];
  DWORD w;
//  ULONG64 LastLcn = 0;
  /* Sanity check. */
  if (MinimumLcn >= Data->TotalClusters) return(NO);

  /* Main loop to walk through the entire clustermap. */
  Lcn = MinimumLcn;
  ClusterStart = 0;
  PrevInUse = 1;
  HighestBeginLcn = 0;
  HighestEndLcn = 0;
  LargestBeginLcn = 0;
  LargestEndLcn = 0;

//  /* "Looking for gap from %I64d, to %I64d for size %I64d" */
//  Data->ShowDebug(1,NULL,L"Looking for gap from %I64d, to %I64d for size %I64d",MinimumLcn,MaximumLcn,MinimumSize);

//  /* "Exclude 0 from %I64d, to %I64d" */
//  Data->ShowDebug(1,NULL,L"Exclude 0 from %I64d, to %I64d",Data->MftExcludes[0].Start,Data->MftExcludes[0].End);

//  /* "Exclude 1 from %I64d, to %I64d" */
//  Data->ShowDebug(1,NULL,L"Exclude 1 from %I64d, to %I64d",Data->MftExcludes[1].Start,Data->MftExcludes[1].End);

//  /* "Exclude 2 from %I64d, to %I64d" */
//  Data->ShowDebug(1,NULL,L"Exclude 2 from %I64d, to %I64d",Data->MftExcludes[2].Start,Data->MftExcludes[2].End);

  do {
    /* Fetch a block of cluster data. If error then return NO. */
    BitmapParam.StartingLcn.QuadPart = Lcn;
    ErrorCode = DeviceIoControl(Data->Disk.VolumeHandle,FSCTL_GET_VOLUME_BITMAP,
      &BitmapParam,sizeof(BitmapParam),&BitmapData,sizeof(BitmapData),&w,NULL);
    if (ErrorCode != 0) {
        ErrorCode = NO_ERROR;
      } else {
        ErrorCode = GetLastError();
        }
    if ((ErrorCode != NO_ERROR) && (ErrorCode != ERROR_MORE_DATA)) {
      /* Show debug message: "ERROR: could not get volume bitmap: %s" */
      SystemErrorStr(GetLastError(),s1,BUFSIZ);
      Data->ShowDebug(1,NULL,Data->DebugMsg[12],s1);
      return(NO);
      }

    /* Sanity check. */
    if (Lcn >= BitmapData.StartingLcn + BitmapData.BitmapSize) return(NO);
    if (MaximumLcn == 0) MaximumLcn = BitmapData.StartingLcn + BitmapData.BitmapSize;

    /* Analyze the clusterdata. We resume where the previous block left
       off. If a cluster is found that matches the criteria then return
       it's LCN (Logical Cluster Number). */
    Lcn = BitmapData.StartingLcn;
    Index = 0;
    Mask = 1;

//    /* "Bitmap from %I64d, to %I64d" */
//    Data->ShowDebug(1,NULL,L"Bitmap from %I64d, to %I64d",
//                    BitmapData.StartingLcn,BitmapData.StartingLcn + BitmapData.BitmapSize);

    IndexMax = sizeof(BitmapData.Buffer);
    if (BitmapData.BitmapSize / 8 < IndexMax) IndexMax = (int)(BitmapData.BitmapSize / 8);
    while ((Index < IndexMax) && (Lcn < MaximumLcn)) {

//      if (Lcn != (LastLcn + 1)) {
//        /* "Last Lcn %I64d" */
//        Data->ShowDebug(1,NULL,L"Last Lcn %I64d",LastLcn);
//        /* "New Lcn %I64d" */
//        Data->ShowDebug(1,NULL,L"New Lcn %I64d",Lcn);
//        }
//      LastLcn = Lcn;

      if (Lcn >= MinimumLcn) {
        InUse = (BitmapData.Buffer[Index] & Mask);
        if (((Lcn >= Data->MftExcludes[0].Start) && (Lcn < Data->MftExcludes[0].End)) ||
            ((Lcn >= Data->MftExcludes[1].Start) && (Lcn < Data->MftExcludes[1].End)) ||
            ((Lcn >= Data->MftExcludes[2].Start) && (Lcn < Data->MftExcludes[2].End))) {
          if (IgnoreMftExcludes == FALSE) InUse = 1;
          }
        if ((PrevInUse == 0) && (InUse != 0)) {
          /* Show debug message: "Gap found: LCN=%I64d, Size=%I64d" */
          Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,Lcn - ClusterStart);
//          Data->ShowDebug(1,NULL,Data->DebugMsg[13],ClusterStart,Lcn - ClusterStart);

          /* If the gap is bigger/equal than the mimimum size then return it,
             or remember it, depending on the FindHighestGap parameter. */
          if ((ClusterStart >= MinimumLcn) &&
              (Lcn - ClusterStart >= MinimumSize)) {
            if (FindHighestGap == NO) {
              if (BeginLcn != NULL) *BeginLcn = ClusterStart;
              if (EndLcn != NULL) *EndLcn = Lcn;
              return(YES);
              }
            HighestBeginLcn = ClusterStart;
            HighestEndLcn = Lcn;
            }

          /* Remember the largest gap on the volume. */
          if ((LargestBeginLcn == 0) ||
              (LargestEndLcn - LargestBeginLcn < Lcn - ClusterStart)) {
            LargestBeginLcn = ClusterStart;
            LargestEndLcn = Lcn;
            }
          }
        if ((PrevInUse != 0) && (InUse == 0)) ClusterStart = Lcn;
//        if ((PrevInUse != 0) && (InUse == 0)) {
//           ClusterStart = Lcn;
//          /* Show debug message: "ClusterStart = %I64d" */
//          Data->ShowDebug(1,NULL,L"ClusterStart = %I64d",Lcn);
//          }
        PrevInUse = InUse;
        }
      if (Mask == 128) {
          Mask = 1;
          Index = Index + 1;
        } else {
          Mask = Mask << 1;
          }
      Lcn = Lcn + 1;
      }

//    /* "Index and IndexMax %I64d, %I64d" */
//    Data->ShowDebug(1,NULL,L"Index and IndexMax %d, %d",Index,IndexMax);
//    /* "Lcn and MaximumLcn %I64d, %I64d" */
//    Data->ShowDebug(1,NULL,L"Lcn and MaximumLcn %I64d, %I64d",Lcn,MaximumLcn);

    } while ((ErrorCode == ERROR_MORE_DATA) &&
             (Lcn < BitmapData.StartingLcn + BitmapData.BitmapSize) &&
             (Lcn < MaximumLcn));

  /* Process the last gap. */
  if (PrevInUse == 0) {
    /* Show debug message: "Gap found: LCN=%I64d, Size=%I64d" */
    Data->ShowDebug(6,NULL,Data->DebugMsg[13],ClusterStart,Lcn - ClusterStart);
//    Data->ShowDebug(1,NULL,Data->DebugMsg[13],ClusterStart,Lcn - ClusterStart);

    if ((ClusterStart >= MinimumLcn) &&
        (Lcn - ClusterStart >= MinimumSize)) {
      if (FindHighestGap == NO) {
        if (BeginLcn != NULL) *BeginLcn = ClusterStart;
        if (EndLcn != NULL) *EndLcn = Lcn;
        return(YES);
        }
      HighestBeginLcn = ClusterStart;
      HighestEndLcn = Lcn;
      }

    /* Remember the largest gap on the volume. */
    if ((LargestBeginLcn == 0) ||
        (LargestEndLcn - LargestBeginLcn < Lcn - ClusterStart)) {
      LargestBeginLcn = ClusterStart;
      LargestEndLcn = Lcn;
      }
    }

  /* If the FindHighestGap flag is YES then return the highest gap we have
     found. */
  if ((FindHighestGap == YES) && (HighestBeginLcn != 0)) {
    if (BeginLcn != NULL) *BeginLcn = HighestBeginLcn;
    if (EndLcn != NULL) *EndLcn = HighestEndLcn;
    return(YES);
    }

  /* If the MustFit flag is NO then return the largest gap we have found. */
  if ((MustFit == NO) && (LargestBeginLcn != 0)) {
    if (BeginLcn != NULL) *BeginLcn = LargestBeginLcn;
    if (EndLcn != NULL) *EndLcn = LargestEndLcn;
    return(YES);
    }

  /* No gap found, return NO. */
  return(NO);
  }

[KeepingRealBusy]

Jeroen,

Here is the code for FindGap - the driver to count, time, and compare calls to New and Old.

Dave.

Code:

/* Time and check multiple versions of FindGap */
int FindGap(
  struct DefragDataStruct *Data,
  ULONG64 MinimumLcn,          /* Gap must be at or above this LCN. */
  ULONG64 MaximumLcn,          /* Gap must be below this LCN. */
  ULONG64 MinimumSize,         /* Gap must be at least this big. */
  int MustFit,                 /* YES: gap must be at least MinimumSize. */
  int FindHighestGap,          /* YES: return the last gap that fits. */
  ULONG64 *BeginLcn,           /* Result, LCN of begin of cluster. */
  ULONG64 *EndLcn,             /* Result, LCN of end of cluster. */
  BOOL IgnoreMftExcludes) {

  ULONG64 NewBegin;
  ULONG64 NewEnd;
  ULONG64 SaveBegin;
  ULONG64 SaveEnd;
  DWORD StartTime;
  DWORD EndTime;
  DWORD LoopCount;
  int OldResult;
  int NewResult;
  NewCount++;

  StartTime = GetTickCount();
  for(LoopCount = 0; LoopCount < 10; LoopCount++)
    NewResult = FindGapNew(Data,MinimumLcn,0,MinimumSize,YES,NO,&NewBegin,&NewEnd,FALSE);
  EndTime = GetTickCount();
  NewTime += (EndTime - StartTime);

  StartTime = GetTickCount();
  for(LoopCount = 0; LoopCount < 10; LoopCount++)
    OldResult = FindGapOld(Data,MinimumLcn,0,MinimumSize,YES,NO,BeginLcn,EndLcn,FALSE);
  EndTime = GetTickCount();
  OldTime += (EndTime - StartTime);
  /* Trap mismatched returns. */
  if ((NewBegin != *BeginLcn) && (NewEnd != *EndLcn)){
SaveBegin = *BeginLcn;
SaveEnd = *EndLcn;
    __asm
    {
    mov eax,NewCount
    xor ebx,ebx
    mov ebx,[ebx]
    }
  }
  return(OldResult);
}

[KeepingRealBusy]

Jeroen,

The final piece, the changes to Fixup to report the counts and times on the log,
just a ShowDebug statement added.

Dave.

Code:

/* Move items to their zone. This will:
   - Defragment all fragmented files
   - Move regular files out of the directory zone.
   - Move SpaceHogs out of the directory- and regular zones.
   - Move items out of the MFT reserved zones
   */
void Fixup(struct DefragDataStruct *Data) {
  struct ItemStruct *Item;
  struct ItemStruct *NextItem;
  ULONG64 ItemLcn;
  ULONG64 GapBegin[3];
  ULONG64 GapEnd[3];
  int FileZone;
  WIN32_FILE_ATTRIBUTE_DATA Attributes;
  ULONG64 FileTime;
  FILETIME SystemTime1;
  ULONG64 SystemTime;
  ULONG64 LastCalcTime;
  int Result;
  ULARGE_INTEGER u;
  int MoveMe;

  CallShowStatus(Data,8,-1);               /* "Phase 3: Fixup" */

  /* Initialize: fetch the current time. */
  GetSystemTimeAsFileTime(&SystemTime1);
  u.LowPart = SystemTime1.dwLowDateTime;
  u.HighPart = SystemTime1.dwHighDateTime;
  SystemTime = u.QuadPart;

  /* Initialize the width of the progress bar: the total number of clusters
     of all the items. */
  for (Item = TreeSmallest(Data->ItemTree); Item != NULL; Item = TreeNext(Item)) {
    if (Item->Unmovable == YES) continue;
    if (Item->Exclude == YES) continue;
    if (Item->Clusters == 0) continue;
    Data->PhaseTodo = Data->PhaseTodo + Item->Clusters;
    }
  LastCalcTime = SystemTime;

  /* Exit if nothing to do. */
  if (Data->PhaseTodo == 0) return;

  /* Walk through all files and move the files that need to be moved. */
  for (FileZone = 0; FileZone < 3; FileZone++) {
    GapBegin[FileZone] = 0;
    GapEnd[FileZone] = 0;
    }
  NextItem = TreeSmallest(Data->ItemTree);
  while ((NextItem != NULL) && (*Data->Running == RUNNING)) {

    /* The loop will change the position of the item in the tree, so we have
       to determine the next item before executing the loop. */
    Item = NextItem;
    NextItem = TreeNext(Item);

    /* Ignore items that are unmovable or excluded. */
    if (Item->Unmovable == YES) continue;
    if (Item->Exclude == YES) continue;
    if (Item->Clusters == 0) continue;

    /* Ignore items that do not need to be moved. */
    FileZone = 1;
    if (Item->SpaceHog == YES) FileZone = 2;
    if (Item->Directory == YES) FileZone = 0;
    ItemLcn = GetItemLcn(Item);
    MoveMe = NO;
    if (IsFragmented(Item,0,Item->Clusters) == YES) {
      /* "I am fragmented." */
      Data->ShowDebug(4,Item,Data->DebugMsg[53]);
      MoveMe = YES;
      }
    if ((MoveMe == NO) &&
        (((ItemLcn >= Data->MftExcludes[0].Start) && (ItemLcn < Data->MftExcludes[0].End)) ||
         ((ItemLcn >= Data->MftExcludes[1].Start) && (ItemLcn < Data->MftExcludes[1].End)) ||
         ((ItemLcn >= Data->MftExcludes[2].Start) && (ItemLcn < Data->MftExcludes[2].End))) &&
        ((Data->Disk.Type != NTFS) || (MatchMask(Item->LongPath,L"?:\\$MFT") != YES))) {
      /* "I am in MFT reserved space." */
      Data->ShowDebug(4,Item,Data->DebugMsg[54]);
      MoveMe = YES;
      }
    if ((FileZone == 1) && (ItemLcn < Data->Zones[1]) && (MoveMe == NO)) {
      /* "I am a regular file in zone 1." */
      Data->ShowDebug(4,Item,Data->DebugMsg[55]);
      MoveMe = YES;
      }
    if ((FileZone == 2) && (ItemLcn < Data->Zones[2]) && (MoveMe == NO)) {
      /* "I am a spacehog in zone 1 or 2." */
      Data->ShowDebug(4,Item,Data->DebugMsg[56]);
      MoveMe = YES;
      }
    if (MoveMe == NO) {
      Data->PhaseDone = Data->PhaseDone + Item->Clusters;
      continue;
      }

    /* Ignore files that have been modified less than 15 minutes ago. */
    if (Item->Directory == NO) {
      Result = GetFileAttributesExW(Item->LongPath,GetFileExInfoStandard,&Attributes);
      if (Result != 0) {
        u.LowPart = Attributes.ftLastWriteTime.dwLowDateTime;
        u.HighPart = Attributes.ftLastWriteTime.dwHighDateTime;
        FileTime = u.QuadPart;
        if (FileTime + 15 * 60 * (ULONG64)10000000 > SystemTime) {
          Data->PhaseDone = Data->PhaseDone + Item->Clusters;
          continue;
          }
        }
      }

    /* If the file does not fit in the current gap then find another gap. */
    if (Item->Clusters > GapEnd[FileZone] - GapBegin[FileZone]) {
      Result = FindGap(Data,Data->Zones[FileZone],0,Item->Clusters,YES,NO,&GapBegin[FileZone],
        &GapEnd[FileZone],FALSE);
      if (Result == NO) {
        /* Show debug message: "Cannot move item away because no gap is big enough: %I64d[%lu]" */
        Data->ShowDebug(2,Item,Data->DebugMsg[25],GetItemLcn(Item),Item->Clusters);
        GapEnd[FileZone] = GapBegin[FileZone];         /* Force re-scan of gap. */
        Data->PhaseDone = Data->PhaseDone + Item->Clusters;
        continue;
        }
      }

    /* Move the item. */
    Result = MoveItem(Data,Item,GapBegin[FileZone],0,Item->Clusters,0);
    if (Result == YES) {
        GapBegin[FileZone] = GapBegin[FileZone] + Item->Clusters;
      } else {
        GapEnd[FileZone] = GapBegin[FileZone];         /* Force re-scan of gap. */
        }

    /* Get new system time. */
    GetSystemTimeAsFileTime(&SystemTime1);
    u.LowPart = SystemTime1.dwLowDateTime;
    u.HighPart = SystemTime1.dwHighDateTime;
    SystemTime = u.QuadPart;
    }
//    /* "NewCount, NewTime, and OldTime %u, %u, %u" */
//    Data->ShowDebug(1,NULL,L"NewCount, NewTime, and OldTime %u, %u, %u",NewCount,NewTime,OldTime);
  }

[jeroen]

Thanks again for your code, I appreciate it. I have to admit that I have not looked at it yet, it's still on my wishlist.

[Darlis]

necoo is actually a spammer and just copied parts of this post.
But it works as a reminder. 

[jeroen]

necoo is actually a spammer and just copied parts of this post.

Ah, I missed that. I have now removed the posting and blocked the userid.