понедельник, 29 июня 2009 г.

Быстрое копирование файлов

Беру в руки листок с заданиями по предмету операционные системы. Пробегаю глазами по тексту: эхо-сервер на мэйлслотах, асинхронный ввод-вывод, разделяемая память и прочая лабуда. Сплошь и рядом изучение существующих механизмов. Где же романтика?

Постойте, что тут у нас? Задача тридцать три: написать программу для быстрого копирования файлов, провести сравнение скорости с проводником Windows и Total Commander-ом в файловых системах FAT и NTFS. Оба-на! Ни единой подробности реализации в условии задания. В чём прикол? Мы же никогда не обгоним вышеперечисленных "соперников". Не говоря уже о десятке сторонних программ, встраиваемых в проводних Windows и ускоряющих(это ещё под сомнением) копирование.
Что же мы можем придумать такого необычного? Да и вообще, что обуславливает вариативность задания? Очевидные параметры:
1. Размер буфера
2. Вкл/Откл буферизации ОС
3. Прочие аттрибуты открытия файла

Для всех является очевидным, что чтение одного мегабайта данных за раз и чтение десять раз по сто килобайт несоизмеримы по времени. Второе несомненно выполняется намного дольше. А значит, чем больше буфер мы выберем, тем быстрее будет наше копирование. Это обычная логика здравомыслящего человека. Но мы ведь не для этого здесь собрались? Более бесполезную статью трудно придумать. Даже по меркам моего блога. И вообще уже, какая то вода получается, а не статья.

Нам известно, что в общем случае файл на жёстком диске хранится не одним куском, а разбит на фрагменты (в терминологии Microsoft - extents). Под экстентом мы будем понимать набор смежных секторов носителя информации. А что если мы будем считывать файл блоками размером с эти экстенты? Если размер экстента будет неприлично большой, будем считывать его за несколько раз. Тоесть при каждом считывании, потребуется считать с диска только подряд идущие сектора. Даст ли нам это преимущество в скорости? Для слабофрагментированных файлов наш алгоритм вообще сведётся к изначальному примитивному копированию с постоянным буфером. Немного погуглив, нашёл следующие ссылки:
1. FSCTL_GET_RETRIEVAL_POINTERS Control Code
2. http://www.gidforums.com/t-4551.html

Речь идёт о вызове функции драйвера для получения массива экстентов для конкретного файла с информацией о размере и привязке экстентов к реальным кластерам на диске.
VCN (Virtual Cluster Number) - номер виртуального кластера. Для каждого файла своя нумерация. Например, виртуальный кластер #3 в файле на диске (диск с размером кластера 4КБ) означает область файла с байта 12288 до байта 16391.
LCN (Logical Cluster Number) - номер реального кластера на носителе информации. Каждому виртуальному кластеру сопоставлен ровно один реальный и наоборот. Виртуальные нумеруются от начала файла, а реальные от начала диска.

Теперь разберёмся с кэшированием. Нужно ли нам кэширование ОС при чтении и при записи? Для сильно-фрагментированных файлов кэширование чтения не только не полезно, но и вредно. Мы ведь считываем с диска практически всегда поэкстентно. А значит послеидущие сектора нам точно не нужны. Значит кэширование чтения нам только навредит. Практика показала, что от кэширования записи тоже лучше отказаться. Ну и чего нам теперь не хватает? Берём и пишем код.

#define _WIN32_WINNT 0x0400

#include <windows.h>
#include <WinIoCtl.h>
#include <iostream>

using namespace std;

const wchar_t *FROM_FILE = L"c:\\Documents and Settings\\Артурчег\\Local Settings\\Application Data\\Microsoft\\CD Burning\\EPL.2009.Liverpool.vs.Arsenal.720p.HDTV.x264\\First time-001.mkv";
const wchar_t *TO_FILE = L"W:\\1.mkv";

int main(int argc, TCHAR *argv[])
{
DWORD time1 = GetTickCount();

// Подготовка файла
HANDLE hFile = CreateFile(
FROM_FILE, // 126 parts
GENERIC_READ,
FILE_SHARE_READ,
NULL,
OPEN_EXISTING,
FILE_ATTRIBUTE_NORMAL | FILE_FLAG_NO_BUFFERING,
NULL);

if( hFile == INVALID_HANDLE_VALUE )
{
cout << "CreateFile(): error " << GetLastError() << endl;
return 1;
}

// Подготовка буферов
STARTING_VCN_INPUT_BUFFER inputBuffer;
inputBuffer.StartingVcn.QuadPart = 0;

DWORD sz = sizeof(RETRIEVAL_POINTERS_BUFFER)+sizeof(LARGE_INTEGER)*2*1000000;
RETRIEVAL_POINTERS_BUFFER *outputBuffer = (RETRIEVAL_POINTERS_BUFFER*) new char [sz];
outputBuffer->ExtentCount = 1000000;
outputBuffer->StartingVcn.QuadPart = 0;

// Запрос данных о файле
DWORD retSize;
BOOL fResult = DeviceIoControl(
(HANDLE) hFile, // handle to device
FSCTL_GET_RETRIEVAL_POINTERS, // dwIoControlCode
(LPVOID) &inputBuffer, // input buffer
(DWORD) sizeof(inputBuffer), // size of input buffer
(LPVOID) outputBuffer, // output buffer
(DWORD) sz, // size of output buffer
(LPDWORD) &retSize, // number of bytes returned
(LPOVERLAPPED) NULL ); // OVERLAPPED structure

if (!fResult)
{
cout << "DeviceIoControl() error: " << GetLastError() << endl;
return 2;
}
cout << "File consist from " << outputBuffer->ExtentCount << " extents." << endl;

DWORD SECTOR_SIZE = 4096;

// Создание цепочки размеров
DWORD arrsize = outputBuffer->ExtentCount;
DWORD *arr = new DWORD [arrsize];
arr[0] = SECTOR_SIZE*(outputBuffer->Extents[0].NextVcn.QuadPart - outputBuffer->StartingVcn.QuadPart);

DWORD fsz = arr[0];
for(int i=1; i<arrsize; i++)
{
arr[i] = outputBuffer->Extents[i].NextVcn.QuadPart - outputBuffer->Extents[i-1].NextVcn.QuadPart;
arr[i] *= SECTOR_SIZE;
fsz += arr[i];
}
cout << "Aligned file size is " << fsz << " bytes." << endl;

DWORD MAX_BUFFER_SIZE = 10*1024*1024;
char *buffer = new char [MAX_BUFFER_SIZE];

// Создание файла
HANDLE hFileTo = CreateFile(
TO_FILE,
GENERIC_WRITE,
FILE_SHARE_WRITE,
NULL,
CREATE_ALWAYS,
FILE_ATTRIBUTE_NORMAL | FILE_FLAG_NO_BUFFERING, //!!! Remove if no aligned to 4096 !!!
NULL);

if( hFileTo == INVALID_HANDLE_VALUE )
{
cout << "CreateFile(): error " << GetLastError() << endl;
return 1;
}

// Цикл копирования
DWORD curSize = 0;
DWORD bytesReaden, bytesWritten;
for (int i=0; i<arrsize; i++)
{
if(arr[i] <= MAX_BUFFER_SIZE)
curSize = arr[i];
else {
curSize = MAX_BUFFER_SIZE;
arr[i] -= MAX_BUFFER_SIZE;
i--;
}
//curSize = MAX_BUFFER_SIZE;
fResult = ReadFile(hFile,buffer,curSize,&bytesReaden,NULL);

if (!fResult)
cout << "Reading Collision: " << GetLastError() << endl;

if (curSize != bytesReaden)
cout << "(curSize != bytesReaden) == (" << curSize << " != " << bytesReaden << ")\n";

fResult = WriteFile(hFileTo,buffer,bytesReaden,&bytesWritten,NULL);

if (!fResult)
{
cout << "Writing Collision (" << bytesWritten << " from " \
<< bytesReaden << " ) " << GetLastError() << endl;

// Дописывание хвоста файла (буферизация не отключена)
CloseHandle(hFileTo);
HANDLE hFileTo = CreateFile(
TO_FILE,
FILE_APPEND_DATA,
FILE_SHARE_WRITE,
NULL,
OPEN_EXISTING,
FILE_ATTRIBUTE_NORMAL,
NULL);
fResult = WriteFile(hFileTo,buffer,bytesReaden,&bytesWritten,NULL);
if (!fResult)
cout << "Writing ERROR: " << GetLastError() << endl;
break;
}
}

CloseHandle(hFile);
CloseHandle(hFileTo);

DWORD time2 = GetTickCount();
cout << "All right, my time is " << time2-time1 << " ms\n";

return 0;
}

Подсветка синтаксиса выполнена при помощи Notepad++



Реализованная система прошла тестирование на сильно-фрагментированных файлах. Быстро отыскать такие файлы в системе вам поможет отчет стандартной программы дефрагментации(рис. 1). Результаты тестирования представлены в таблице 1 и таблице 2. Тесты были проведены именно в том порядке в котором они представлены в таблице. Таблица говорит сама за себя.


Рис. 1. Отчёт дефрагментатора

Таблица 1
+------------+--------------+----------------------------------+
| Фрагментов | Размер файла | Имя файла |
+------------+--------------+----------------------------------+
| 1,858 | 1.01 ГБ | First time-001.mkv |
+------------+--------------+----------------------------------+
+-------------------------------+-----------+
| Программа | Время |
+-------------------------------+-----------+
| FragCopy (без буф-ии) | 62.128сек |
| FragCopy (без буф-ии) | 63.944сек |
| FragCopy (без буф-ии) | 62.078сек |
| FragCopy (без буф-ии чтения) | 62.484сек |
| FragCopy (с буф-ей) | 92.547сек |
+-------------------------------+-----------+
| Total Commander 6.55 (32Bit) | 79.200сек |
+-------------------------------+-----------+
| Проводник (Windows XP 32Bit) | 98.200сек |
+-------------------------------+-----------+

Таблица 2
+------------+--------------+----------------------------------+
| Фрагментов | Размер файла | Имя файла |
+------------+--------------+----------------------------------+
| 1,202 | 662 МБ | A0017447.exe |
+------------+--------------+----------------------------------+
+-------------------------------+-----------+
| Программа | Время |
+-------------------------------+-----------+
| FragCopy (без буф-ии) | 10.110сек |
| FragCopy (без буф-ии) | 10.062сек |
| FragCopy (без буф-ии) | 10.062сек |
| FragCopy (без буф-ии) | 10.000сек |
| FragCopy (без буф-ии чтения) | 38.703сек |
+-------------------------------+-----------+
| Total Commander 6.55 (32Bit) | 15.200сек |
+-------------------------------+-----------+
| Проводник (Windows XP 32Bit) | 13.900сек |
+-------------------------------+-----------+

Алгоритм хорошо себя показывает на файлах с большим числом фрагментов. Ну правильно, ведь при малом числе экстентов и их не малом размере мы копируем буфером постоянного размера. Никакого разнообразия. Есть идеи?

Комментариев нет: