Несколько ускоренный способ сканирования директории.

← →
Riply © (2007-10-14 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 © (2007-10-14 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.
Уфф... :)

← →
Правильный Вася (2007-10-14 21:23) [2]

лучше бы оформить статьей и выложить здесь же на сайте
ведь есть такая возможность

← →
vasIZmax © (2007-10-14 21:28) [3]

//off topic
> Доводить это хозяйство "до ума" не буду

имхо, доведи как раз "до ума" (со всеми пояснениями ИШ и clickmaker`а) и получится статья, мож за одно и снимешь "занавес без статейности" на сайте:)
//off topic

← →
Riply © (2007-10-14 21:29) [4]

> [2] Правильный Вася (14.10.07 21:23)
> лучше бы оформить статьей и выложить здесь же на сайте
> ведь есть такая возможность

Статьи надо уметь писать...
А я так... поразглагольствовала в "начинающих".
Если что не так, то уж очень сильно не накажут :)

← →
vasIZmax © (2007-10-14 21:29) [5]

> Правильный Вася (14.10.07 21:23) [2]

мысли сходятся что ль?:-)

← →
Virgo_Style © (2007-10-14 21:31) [6]

каждый раз, читая твои темы в "начинающих", я думаю - а какая же тема будет достойна обсуждения в Основной, или, избавь Тьма, в WinAPI? ))))

← →
vpbar © (2007-10-15 09:58) [7]

Riply - ты супер. Не пойму, почему в начинающих. (Скромная наверно).
И мысль про статью действительно хорошая.
Если ты будешь публиковать свои изыскания, то лично мне это очень пригодится.
Спасибо.

← →
Игорь Шевченко © (2007-10-15 09:58) [8]

Riply © (14.10.07 21:09)

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

← →
Riply © (2007-10-15 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 © (2007-10-15 15:42) [10]

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

Так используйте FindFirstFileW

← →
Riply © (2007-10-15 15:48) [11]

> [10] Ins © (15.10.07 15:42)
> Так используйте FindFirstFileW
Можно, но он не уберет преобразования DosPath ---> NtPath и обратно.
А они, в свою очередь, потребуют работы с памятью.

← →
Riply © (2007-10-15 17:22) [12]

Для тех, кому интересно...
В [0] Riply © (14.10.07 21:09), я так скромненько упомянула:
"FileDirectoryInformation - выбор класса важен."
Пояснять "почему" не стала, что бы не бросалось в глаза, что сама не понимаю :)
Но использование, например, FileBothDirectoryInformation вместо
FileDirectoryInformation подтормаживает работу.
В структуру добавляются всего три поля, казалось бы
на скорость не повлияет... ан нет. Причины мне не понятны :(

← →
Leonid Troyanovsky © (2007-10-15 18:47) [13]

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

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

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

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

--
Regards, LVT.

← →
Riply © (2007-10-16 02:24) [14]

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

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

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

← →
Германн © (2007-10-16 02:29) [15]

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

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

А разве ты свой пост не поместила в "Начинающие"?
http://delphimaster.net/view/2-1192381766/

> [15] Германн © (16.10.07 02:29)
> А разве ты свой пост не поместила в "Начинающие"?

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

На самом деле причины были другие: Я здесь (на форуме) уже
столько "Великих Открытий" насовершала, что уже страшно что-то утверждать. :)
А то выдет как всегда :)
А в "Начинающих" - это просто попытка "начинающего" чуть поразглагольствовать на тему:)

>[16] Riply ©
Напомнило. Взято из "Физики продолжают шутить"
"Описание экспериментальной методики"
Фразу (в работе автора) типа:
«Для детального исследования мы выбрали три образца».
Надо понимать так:
"Результаты, полученные на остальных двадцати образцах,
не лезли ни в какие ворота".
:)

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

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

Или ты об обязательном наличии знака вопроса "?" ?
:-)

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

Я знаю твоё знание сей замечательной книжки. И я всецело приветствую твоё стремление!

Удалено модератором
Примечание: Offtopic

>[0] Riply © (14.10.07 21:09)
Хочу вернуться к нашим баранам. Тьфу... К Riply`ским баранам :)
Случайно напоролась на следующее:
Когда мы таким образом только сканируем, то выигрыш от 15 до 50 %
(зависит от "состояния" диска, соотношения кол-во файлов/кол-во директорий,
уровня вложенности, длин имен и т.д. и т.п.)
Но дело приобретает совсем другой оборот, если нам еще надо и открывать файлы:
выигрыш уже считается "в разы".
Пример теста:
Внутри FindFirst/Next работаем, примерно, так:
Handle:= CreateFileA(PChar(Buf), FILE_ANY_ACCESS, ..., OPEN_EXISTING, ...); if Handle <> INVALID_HANDLE_VALUE then CloseHandle(Handle);

В нашем же случае, я не только открывала все файлы и директории,
но еще и перебирала их потоки.
Каково же было мое удивление, когда наш вариант (вместе с потоками)
посчитался быстрее в три раза. (23891 и 8113 ms).
P.S.
Вобщем то, если вдуматься, то стоило ожидать, учитывая сколько MFT
записей придется просмотреть.

P.S.S.
Сама скорость открытия файла очень сильно зависит от уровня доступа,
который мы запрашиваем (почему - пока не знаю).
Так что не жадничайте ! :))

Такие новости с поля боя к этому часу :)

Несколько ускоренный способ сканирования директории. Найти похожие ветки