Оригинал Поиск Дополнительно Вход
ДомойОсновная Компоненты FreePascal Начинающим KOL Игры Corba Media Журнал WinAPI Сети Прочее Базы .Net
Конференция "WinAPI" » Несколько ускоренный способ сканирования директории.
[1 - 20 из 22]<< < 1 2 > >>
  
  • Riply © (14.10.07 21:09) [0]
    Здравствуйте !
    Т.к. последнее время эта тема стала популярной на форуме, решила
    попробовать посмотреть на нее с точки зрения Naitive API.
    (Если честно, то  мне самой это понадобилось для сравнительного анализа
    и контроля моих MFT-творений и изучения "как это делают другие" :)
    Почитала, что по этому поводу говорят в интернете.
    Во всех местах (которые я сумела найти) приходят к одному и тому-же
    выводу: "Этим путем - не ускориться".

    Давайте попробуем усомниться в этом ? :)
    (Усомняться мы будем, подглядывая в исходники Игоря Шевченко :)
    Сначала определим структуру в которой будем хранить данные
    для каждого объекта. Она должна быть очень маленькой.
    Ведь если мы сканируем диск с миллионом объектов, то увеличение ее размера
    всего на один байт съест целый мегабайт памяти.

    OBJ_DATA_INF0 = record
    case Integer of
     0: (ChildCount: DWORD;
         FirstChildOffset: DWORD); // для директорий
     1: (SizeOfData: LONGLONG);    // для файлов и файловых потоков
     end;

    _NAMED_QUERY_OBJECT = packed record
      OffsetNextEntry   : Word;  // Смещение на следующий блок
      ObjAttributes     : ULONG; // Атрибуты объекта
      ExternalData      : OBJ_DATA_INF0;
      ObjNameLength     : Word; // нилл-терминайт не считаем.
      ObjName           : array[0..0] of Byte;
     end;


    (Здесь оставлен простор для уменьшения :)
    Например, в ExternalData.SizeOfData предполагается хранить размер файла.
    Но для него вполне хватит и 48 бит. Так что туда можно запихать ObjNameLength
    и сэкономить аж целых два байта :) Так же можно уменьшить и ObjAttributes,
    переопределив, какие и сколько нам надо.
    "Оставляю это заинтересованным лицам" (с) Leonid Troyanovsky

    И заодно пара функций для расчета размера записи и выравнивания его до SizeOf(DWord)
    (Мудрые люди из Microsoft выравнивают структуру FILE_BOTH_DIR_INFORMATION
    до SizeOf(Int64), ну а мы (т.к. плохо понимаем "зачем и почему") остановимся на DWord :)
    function NT_NameAddedSizeB(const NameLength: integer): integer; inline;
    begin
    if NameLength >= SizeOf(WideChar)
     then Result := NameLength - SizeOf(Byte) else Result := -1;
    end;

    function QueryObj_EdgeSize(const BytesInName: integer): integer;
    var
    Value: integer;
    begin
    Value := SizeOf(_NAMED_QUERY_OBJECT) + NT_NameAddedSizeB(BytesInName);
    Result := Value mod SizeOf(DWord);
    if Result > 0 then Result := Value + SizeOf(DWord) - Result else inc(Result, Value);
    end;



    Ну а теперь можно и посканировать. Я приведу только схему кода,
    оговорив параметры вызовов, т.к. кроме этого и обычной рекурсии в нем ничего нет :)
    Используемые функции: NtQueryDirectoryFile, NtOpenFile и NtClose.

    Нам понадобяться два блока памяти: для буффера, передаваемого в NtQueryDirectoryFile
    и для списка наших NAMED_QUERY_OBJECT.

    Попробуем оценить их размеры:
    NtQueryDirectoryFile будем вызывать так:
    ObjectAttr: POBJECT_ATTRIBUTES  - инициализируем хендлом открытого родителя
    (он у нас будет, мы же в рекурсии) и только именем файла (без пути).
    NtQueryDirectoryFile(..., @ObjectAttr(POBJECT_ATTRIBUTES),...
                       FileDirectoryInformation(FILE_INFORMATION_CLASS), - выбор класса важен.
                       False(ReturnSingleEntry),...);
    Мы за один вызов будем пытаться получить все объекты (ReturnSingleEntry = False),
    и экономить на размере буфера не будем, т.к. его нехватка потребует не только
    перевыделения памяти, но и лишнего вызова NtQueryDirectoryFile.
    Такого размера: FS_OBJ_QUERY_INC_SIZE = $10000 * 8 хватает, примерно на 5000 объектов,
    лежащих в корне сканируемого.
    Примерная работа:
    function TNtQueryObjectFS._QueryDirectoryFileMem(const ObjHandle: THandle;
                                                    const InfoClass: FILE_INFORMATION_CLASS;
                                                    RetSngleEntry, RestartScan: LongBool): NTSTATUS;
    var
    IoBlock: TIoStatusBlock;
    begin
    Result := NtQueryDirectoryFile(ObjHandle, FhEvent, nil, nil, @IoBlock, FpObjInfo,
                                   FcbObjInfo, InfoClass, RetSngleEntry, nil, RestartScan);
    while True do
     case Result of
      STATUS_BUFFER_OVERFLOW, STATUS_INFO_LENGTH_MISMATCH:
       begin
        _ReallocQueryBuffer(FcbObjInfo + FcbObjInfo);
        Result := NtQueryDirectoryFile(ObjHandle, FhEvent, nil, nil, @IoBlock, FpObjInfo,
                                       FcbObjInfo, InfoClass, RetSngleEntry, nil,
                                       Result = STATUS_INFO_LENGTH_MISMATCH);

       end;
      else Exit;
     end;
    end;

    function TNtQueryObjectFS._QueryDirectoryFile(const aOffset: DWord; const ObjHandle: THandle;
                                                 const InfoClass: FILE_INFORMATION_CLASS;
                                                 RetSngleEntry: LongBool): NTSTATUS;
    begin
    Result := _QueryDirectoryFileMem(ObjHandle, InfoClass, RetSngleEntry, True);
    while Result = STATUS_SUCCESS do
     begin
      FROOT_FIND_DATA.AddObjectsBlock(aOffset, FpObjInfo, InfoClass, FirstCall);<--Пишем наши данные
      Result := _QueryDirectoryFileMem(ObjHandle, InfoClass, RetSngleEntry, False);
     end;
    end;

  • Riply © (14.10.07 21:10) [1]
    Примерно так выглядит тело рекурсии:
    function TNtQueryObjectFS._QueryFileDirectoryRec(const aOffset: DWord; const NtScanRec: TNtScanRec;
                                                    const DesAccess: ACCESS_MASK;
                                                    const InfoClass: FILE_INFORMATION_CLASS;
                                                    const RetSngle: Boolean) : NTSTATUS;
    var
    ObjectAttr: OBJECT_ATTRIBUTES;
    IoBlock: TIoStatusBlock;
    usSubObj: TUnicodeString;
    _ScanRec: TNtScanRec;
    Tmp, Offset, LastOffset: DWord;
    begin
    Tmp := NtScanRec.RootNameLen shr SHR_WCHAR;
    InitializeObjectAttributes(@ObjectAttr, @NtScanRec.ObjName, OBJ_CASE_INSENSITIVE, NtScanRec.hParent, nil);
    Result := NtOpenFile(@_ScanRec.hParent, DesAccess, @ObjectAttr, @IoBlock, ALX_FILE_SHARE_ALL,
                         FILE_SYNCHRONOUS_IO_NONALERT or FILE_DIRECTORY_FILE);
    if FixStatus(Result) = STATUS_SUCCESS then
     try
      Us_InitNull(@_ScanRec.ObjName);
      Offset := FROOT_FIND_DATA.UsedSize;
      Result := _QueryDirectoryFile(aOffset, _ScanRec.hParent, InfoClass, RetSngle);
      if Result = STATUS_NO_MORE_FILES then
       begin
        LastOffset := FROOT_FIND_DATA.UsedSize;
        while Offset < LastOffset do
         begin
          with FROOT_FIND_DATA.Blocks(Offset)^ do
           begin
            inc(FMemCount, QueryObj_EdgeSize(Tmp + SizeOf(Char) + (ObjNameLength shr SHR_WCHAR)));
            if IsNotScannedDirectory then
             if GetNameU(@usSubObj) = STATUS_SUCCESS then
              begin
               Result := Us_Duplicate(@usSubObj, @_ScanRec.ObjName);
               if Result = STATUS_SUCCESS then
                try
                 _ScanRec.RootNameLen := _ScanRec.ObjName.Length + SizeOf(WideChar) + NtScanRec.RootNameLen;
                 _QueryFileDirectoryRec(Offset, _ScanRec, DesAccess, InfoClass, RetSngle);
                finally
                 Us_FreeMem(@_ScanRec.ObjName);
                end;
              end;
            inc(Offset, FROOT_FIND_DATA.Blocks(Offset).OffsetNextEntry);
           end;
         end;
       end;
     finally
      Us_FreeMem(@_ScanRec.ObjName);
      Nt_Close(_ScanRec.hParent);
     end
    else Err_ShowNT(Result, usSubObj.Buffer);
    end;


    В этой ф-ии мы записываем полученные результаты в виде:
    имени(без пути)
    смещения на следующий элемент
    смещения на первого ребенка
    атрибутов.
    Заодно высчитываем точный размер будующей структуры в которую
    конвертируем все это дело для удобства последующей работы с данными :)
    После пояснений Игоря Шевченко и clickmaker`а о механизме выделения памяти в
    Rtl ф-иях для UNICODE_STRING, я (в данной задаче) использовала "самописные"
    ф-ии - аналоги Rtl ф-ий,только использующие GetMem, FreeMem.
    (Мизерный выигрыш - а приятно :)

    При оценке начального размера буфера для NAMED_QUERY_OBJECT, я поступаю так:
    Если нас вызвали просканировать целый диск, то считываю значение MftValidDataLength из MFT.
    (все равно нам открывать диск :) и поделив его на размер записи в MFT получаю
    довольно точное число валидных объектов на диске.
    Если же сканировать надо директорию, то начальный размер берем с потолка :)

    Резюме:
    Мы пытались выиграть на:
    1. Уходе от постоянной ковертации больших строк из PChar в UNICODE_STRING и обратно.
    2. Открытии всех объектов, используя Handle родителя.
    3. Получении сразу всех "корневых" объектов за один запрос.
    4. Хранении данных "в одном блоке памяти"

    Сравнивалось заполнение TStrings при помощи FindFirst/NextFile, с одной стороны
    и полный объем работ (подготовка, сканирование, конвертация результатов в
    индексированную структуру, и последующее заполнение из нее TStrings) с другой стороны.

    Тестирование показало выигрыш в скорости
    на "индексированном" диске - в два раза
    на не "индексированном" диске - на 20-25%.

    Учитывая, что все это нуждается в доработке напильником, оптимизации и исправлении ошибок,
    результат очень даже ничего :)

    P.S.
    Доводить это хозяйство "до ума" не буду, ибо данная методика
    не идет ни в какое сравнение с работой через MFT, а любопытство свое я уже удовлетворила :)

    P.P.S.
    Уфф... :)
  • Правильный Вася (14.10.07 21:23) [2]
    лучше бы оформить статьей и выложить здесь же на сайте
    ведь есть такая возможность
  • vasIZmax © (14.10.07 21:28) [3]
    //off topic
    > Доводить это хозяйство "до ума" не буду

    имхо, доведи как раз "до ума" (со всеми пояснениями ИШ и clickmaker`а) и получится статья, мож за одно и снимешь "занавес без статейности" на сайте:)
    //off topic
  • Riply © (14.10.07 21:29) [4]
    > [2] Правильный Вася   (14.10.07 21:23)
    > лучше бы оформить статьей и выложить здесь же на сайте
    > ведь есть такая возможность

    Статьи надо уметь писать...
    А я так... поразглагольствовала в "начинающих".
    Если что не так, то уж очень сильно не накажут :)
  • vasIZmax © (14.10.07 21:29) [5]
    > Правильный Вася   (14.10.07 21:23) [2]

    мысли сходятся что ль?:-)
  • Virgo_Style © (14.10.07 21:31) [6]
    каждый раз, читая твои темы в "начинающих", я думаю - а какая же тема будет достойна обсуждения в Основной, или, избавь Тьма, в WinAPI? ))))
  • vpbar © (15.10.07 09:58) [7]
    Riply - ты супер.  Не пойму, почему в начинающих. (Скромная наверно).
    И мысль про статью действительно хорошая.
    Если ты  будешь публиковать свои изыскания, то лично мне это очень пригодится.
    Спасибо.
  • Игорь Шевченко © (15.10.07 09:58) [8]
    Riply ©   (14.10.07 21:09)

    Не стоит думать, что систему дураки писали :) Каталоги сканируются настолько быстро, насколько возможно :)
  • Riply © (15.10.07 15:39) [9]
    > [8] Игорь Шевченко ©   (15.10.07 09:58)
    >Не стоит думать, что систему дураки писали :)

    Чем больше я изучаю систему, тем больше поражаюсь уму ее создателей.
    Это без смайлика.

    >Каталоги сканируются настолько быстро, насколько возможно :)

    Да. Но при этом используются некоторые(вынужденные) ограничения
    в угоду удобства (и надежности) ф-ий FindFirst/Next
    Во-первых:
    Читаем Рихтера:
    "Например, функции ядра Windows 2000 выполняют все операции с использованием Unicode символов и строк
    Если вызвать ANSI-версию какой-нибудь Windows-функции, ей придется, преобразовав строки ил ANSI в Unicode, вызывать свою Unicode-версию. Для преобразования строк ANSI-функции нужно выделить блок памяти,
    в котором она размещает Unicode-версию строки."

    Мы же в нашем убрали все ANSI - Unicode преобразования.
    А их было-бы по два на объект. При миллионе объектов - два миллиона преобразований.
    Внушительно, не правда-ли ?
    Плюс, мы не таскаем за собой пути объектов и соответственно не преобразуем их :)

    Так же Рихтер пишет о более медленном обращении к куче,
    через которую идут эти преобразования.

    Во-вторых:
    За один запрос мы получаем сразу все корневые объекты.
    В случае со стандартным сканированием, если корневых объектов 5000, то мы 5000 раз
    делаем запрос, а так один. Тоже убедительно. Не правда-ли ? :)

    В-третьих:
    При открытии объекта, мы используем Handle его родителя, что нескольо ускоряет
    поиск файловой записи в MFT

    И напоследок:
    Мы располагаем, полученные данные последовательно в одном блоке памяти.
    Что тоже дает существенный прирост :)
  • Ins © (15.10.07 15:42) [10]

    > Мы же в нашем убрали все ANSI - Unicode преобразования.
    > А их было-бы по два на объект. При миллионе объектов - два
    > миллиона преобразований.
    > Внушительно, не правда-ли ?
    > Плюс, мы не таскаем за собой пути объектов и соответственно
    > не преобразуем их :)

    Так используйте FindFirstFileW
  • Riply © (15.10.07 15:48) [11]
    > [10] Ins ©   (15.10.07 15:42)
    > Так используйте FindFirstFileW
    Можно, но он не уберет преобразования DosPath ---> NtPath и обратно.
    А они, в свою очередь, потребуют работы с памятью.
  • Riply © (15.10.07 17:22) [12]
    Для тех, кому интересно...
    В [0] Riply © (14.10.07 21:09), я так скромненько упомянула:
    "FileDirectoryInformation - выбор класса важен."
    Пояснять "почему" не стала, что бы не бросалось в глаза, что сама не понимаю :)
    Но использование, например, FileBothDirectoryInformation вместо
    FileDirectoryInformation подтормаживает работу.
    В структуру добавляются всего три поля, казалось бы
    на скорость не повлияет... ан нет. Причины мне не понятны :(
  • Leonid Troyanovsky © (15.10.07 18:47) [13]

    > Riply ©   (15.10.07 17:22) [12]

    > на скорость не повлияет... ан нет. Причины мне не понятны

    Дык, это, оказывается, был вопрос :)
    Чего сказать, хорошо завуалирован.

    http://rsdn.ru/?Info/Howtoask.xml
    даже как-то неудобно вспоминать ;)

    --
    Regards, LVT.
  • Riply © (16.10.07 02:24) [14]
    > [13] Leonid Troyanovsky ©   (15.10.07 18:47)
    > Дык, это, оказывается, был вопрос :)
    > Чего сказать, хорошо завуалирован.

    Нет. Это был не вопрос. Это было пояснение, что данное утверждение
    взято автором с потолка и пояснить причины он пока не может. :)

    P.S.
    А когда этот автор хочет задать вопрос, то он
    строевым шагом идет в "начинающие" и спрашивает :)
    Благо опыт по вопросо-задаванию у нее имеется :)
  • Германн © (16.10.07 02:29) [15]

    > Riply ©   (16.10.07 02:24) [14]


    > P.S.
    > А когда этот автор хочет задать вопрос, то он
    > строевым шагом идет в "начинающие" и спрашивает :)

    А разве ты свой пост не поместила в "Начинающие"?
    http://pda.delphimaster.net/?id=1192381766&n=18
  • Riply © (16.10.07 02:41) [16]
    > [15] Германн ©   (16.10.07 02:29)
    > А разве ты свой пост не поместила в "Начинающие"?

    Поместила. Каюсь. В следующий раз придеться учитывать, что только из одного
    факта нахождения поста в "Начинающих" неотвратимо следует,
    что в нем (посте) содержится вопрос :)

    На самом деле причины были другие: Я здесь (на форуме) уже
    столько "Великих Открытий" насовершала, что уже страшно что-то утверждать. :)
    А то выдет как всегда :)
    А в "Начинающих" - это просто попытка "начинающего" чуть поразглагольствовать на тему:)
  • Riply © (16.10.07 02:52) [17]
    >[16] Riply ©
    Напомнило. Взято из "Физики продолжают шутить"
    "Описание экспериментальной методики"
    Фразу (в работе автора) типа:
    «Для детального исследования мы выбрали три образца».
    Надо понимать так:
    "Результаты, полученные на остальных двадцати образцах,
    не лезли ни в какие ворота".
    :)
  • Германн © (16.10.07 02:53) [18]

    > Поместила. Каюсь.

    А я что против?
    Да помещай сколько влезет. Наш форум из-за этого только станет лучше!
    Но ведь это твои слова -
    > А когда этот автор хочет задать вопрос, то он
    > строевым шагом идет в "начинающие" и спрашивает :)
    >

    Или ты об обязательном наличии знака вопроса "?" ?
    :-)
  • Германн © (16.10.07 02:56) [19]

    > Riply ©   (16.10.07 02:52) [17]
    >
    > >[16] Riply ©
    > Напомнило. Взято из "Физики продолжают шутить"
    >

    Я знаю твоё знание сей замечательной книжки.  И я всецело приветствую твоё стремление!
[1 - 20 из 22]<< < 1 2 > >>
 
Конференция "WinAPI" » Несколько ускоренный способ сканирования директории.
ДомойОсновная Компоненты FreePascal Начинающим KOL Игры Corba Media Журнал WinAPI Сети Прочее Базы .Net
Есть новые Нет новых   [120362   +46][b:0][p:0.004]