Wykrywanie hardlinków

Hardlinki, inaczej łącza stałe lub dowiązania twarde są alternatywnymi nazwami dla pliku, referencjami wskazującymi istniejący wcześniej obiekt. Niestety nie istnieją żadne metody pozwalające określić, które nazwa lub referencją jest oryginalna, a która dodana później. Wszystkie nazwy/referencje wskazują ten sam blok danych.

Dosyć dawno temu starałem się znaleźć prosty sposób na wykrywanie łączy stałych oraz ich enumeracje, aby szybko sprawdzić, czy dany plik nie jest dowiązaniem do już przetworzonych wcześniej danych. Potrzeby można byłoby zawrzeć w dwóch prostych funkcjach.

Pierwsza, zwracająca ilość dowiązań twardych do podanego pliku, a zatem pozwalająca określić, czy dany plik jest dowiązaniem twardym (count > 1):

int GetHardLinkCount(const std::string& filename);

Druga, służąca do enumeracji, a tym samym do pobierania, wszystkich nazw dowiązań wskazujących na tą samą zawartość pliku, której prototyp można przedstawić w poniżej postaci:

template<typename F>
void EnumerateHardLink(const std::string& filename, F func);

Argument F jest dowolnym typem, który może zostać użyty w roli funktora, czyli dowolny, zdefiniowany funktor, funkcja lub lambda, o ściśle określonym prototypie:

void(*func)(const char* name, size_t length);

Przykład użycia takiej funkcji (wyświetlającej wszystkie nazwy hardlinków) jest bardzo prosty:

try {

	EnumerateHardLinks(
		filename,
		[](const char* name, size_t length) {
			std::cout << name << "\n";
		}
	);

} catch (const std::system_error& e) {
	std::cerr << "error: " << e.code() << " - " << e.what() << "\n";
}

Możemy w łatwy sposób zdefiniować przeciążenie funkcji EnumerateHardLinks, która będzie zwracać listę nazw:

typedef std::vector<std::string> StringList;

void EnumerateHardLinks(StringList& names, const std::string& filename) {
	EnumerateHardLinks(
		filename,
		[&](const char* name, size_t length) {
			names.push_back(name);
		}
	);
}

Zależnie od systemu plików, operacje wykonywane przez te funkcje są łatwe lub nieco trudniejsze w implementacji, podobnie zresztą z ich wydajnością. Większość systemów plików wspierających hardlinki używa implementacji bazujących na zliczaniu referencji, przechowywanych wraz z metadanymi pliku.

Moje “badania” i eksperymenty przeprowadzałem na dwóch interesujących mnie systemach: Windows (NTFS) i Linux (ext2/3). Wszelkie wnioski, uwagi i implementacje dotyczące tego drugiego, dotyczą także Unixa oraz innych systemów POSIX-owych.

Linux

W posixowych systemach (operacyjnych i plikowych) hardlinki są bardzo rozpowszechnione, tworzone są za pomocą standardowego narzędzia dostarczanego z systemem - ln. Nie istnieją natomiast żaden wbudowane w system narzędzia pozwalające w łatwy i przystępny sposób wystawali wszystkie dowiązania do danego pliku. Bardzo prosto można jedynie wyświetlić ilość łączy pliku. Dokonać tego można korzystając ze standardowych poleceń w konsoli, takich jak ls i stat.

Licznik dowiązań pliku - i_nlink

W linuksowych systemach plików opartych na inodach, ilość dowiązań przechowywana jest właśnie w strukturze reprezentującej i-węzeł - inode, w polu i_nlink (i_links_count w strukturach i-węzła ext2 i ext3 przechowywanych na dysku). Zatem sprawdzenie ilości dowiązań do danego pliku sprowadza się do pobrania tej informacji.

Programowo (user space) dostęp do tych informacji możemy uzyskać przez jedną z funkcji rodziny [stat](http://linux.die.net/man/2/stat), które zwracają informacje o pliku w strukturze stat.

Funkcja GetHardLinkCount dla systemów posix-owych można w bardzo prosty sposób zaimplementować korzystając właśnie z wyżej podanej funkcji:

int GetFileLinkCount(const std::string& filename) {
	struct stat statinfo;

	if (lstat(filename.c_str(), &statinfo) == -1)
		throw std::system_error(errno, std::system_category(), "failed to get file info");

	return statinfo.st_nlink;
}

Dostęp do tych informacji jest w miarę szybki, implementacje funkcji stat wypełniają strukturę stat kopiując wymagane dane bezpośrednio z tablicy i-węzłów przechowywanych w pamięci.

Iteracja nazw dowiązań

Enumeracja wszystkich nazw hardlinków w systemie posixowym jest nieco bardziej złożoną sprawą. Aby powiązać ze sobą dowiązania do tego samego pliku, musza znajdować się na tym samym urządzeniu oraz musza odwoływać się do tego samego i-węzła. Tak działa “wyszukiwanie hardlinków” w poleceniu find, co można wywnioskować po analizie jego źródeł.

Przełącznik samefile przeszukuje w ten sposób drzewo systemu plików:

> find /home/malcom -samefile a
/home/malcom/b
/home/malcom/a

Podobnie przełącznik inum, szukając plików z podanym numerem i-węzła:

> find /home/malcom -inum 2360265
/home/malcom/b
/home/malcom/a

Przeszukując całe drzewo (zaczynając od roota), warto dodać przełącznik xdev ograniczający do tego samego urządzenia co podany plik, bo przecież łącza stałe “działają” tylko na tym samym urządzeniu/partycji.

Bazując na taki założeniach, możemy spróbować zaimplementować funkcję enumerująca nazwy wszystkich dowiązań do danego pliku:

template<typename F>
void EnumerateHardLinks(const std::string& filename, F func) {

	struct stat statinfo;
	if (lstat(filename.c_str(), &statinfo) == -1)
		throw std::system_error(errno, std::system_category(), "failed to get file info");

	const char* paths[] = { "/", nullptr };

	std::unique_ptr<FTS, int(*)(FTS*)> ftsp(
		fts_open(const_cast<char* const*>(paths), FTS_PHYSICAL | FTS_XDEV, nullptr),
		fts_close
	);

	if (!ftsp) {
		throw std::system_error(errno, std::system_category(), "failed to open file system tree");
	}

	do {

		FTSENT* ent = fts_read(ftsp.get());
		if (ent == nullptr) {
			if (errno != 0)
				throw std::system_error(errno, std::system_category(), "failed to read file system tree");
			break;
		}

		if (ent->fts_statp->st_ino == statinfo.st_ino)
			func(ent->fts_path, ent->fts_pathlen);

	} while (true);

}

W implementacji wykorzystano interfejs fts, ułatwiający iterację po drzewie plików. Oczywiście bez problemów można zaimplementować funkcję korzystającą ze standardowych funkcji operujących na systemie plików - opendir, readdir, stat, ale wykorzystanie fts przyspiesza i upraszcza znacznie kod. Podobnie można wykorzystać posixowy interfejs ftw, którego implementacja linuksowa bazuje na fts.

Szukanie odpowiednich plików-linków odbywa się na całym drzewie plików, co może być długotrwałym procesem, nawet mimo podania flagi FTS_XDEV, która ogranicza, a raczej filtruje iterowane elementy drzewa do tego samego urządzenia.

Skoro łącza stałe mogą jedynie być tworzone do wiązania elementów na tym samym urządzeniu, idealnym rozwiązaniem jest ograniczenie się do iteracji tylko do tego jednego urządzeniu, poczynając od mounpointu, zamiast “latać” po całym drzewie systemu plików.

Posiadając funkcję GetMountPoint, mapującą identyfikator urządzenia na ścieżkę do punktu montowania w systemie plików, wystarczyłoby nieco zmodyfikować wyżej prezentowaną funkcję, aby w sytuacji, gdy to możliwe przekazywać odpowiedni punkt startowy w miejscu inicjalizacji tablicy paths:

std::string root = GetMountPoint(statinfo.st_dev);
if (root.empty())
	root = "/";

const char* paths[] = { root.c_str(), nullptr };

Spod konsoli, bardzo łatwo możemy sprawdzić, jakie zamontowane urządzenia maja systemy plików i punkty montowania w systemie. Wykorzystać możemy narzędzie df, za pomocą którego, prócz listy podmontowanych urządzeń i statystyk ich zajętości, możemy także w łatwy sposób sprawdzić na jakim urządzeniu znajduje się podany plik. Można również przejrzeć zawartość pliku /etc/mtab lub /proc/mounts.

Programowo, jednym z rozwiązań jest skorzystanie z odpowiedniego API służącego do udostępniania informacji z tych plików opisujących zamontowane systemy. Nasza prosta implementacja przedstawiona poniżej, korzysta z funkcji rodziny getmntent:

std::string GetMountPoint(dev_t dev, bool rdev = true) {

	std::unique_ptr<FILE, int(*)(FILE*)> fp(
		setmntent(_PATH_MOUNTED, "r"),
		endmntent
	);

	if (!fp) {
		throw std::system_error(errno, std::system_category(), "failed to open mount table");
	}

	struct stat statinfo;
	struct mntent* mnt;

	do {

		mnt = getmntent(fp.get());
		if (mnt == nullptr) {
			if (errno != 0)
				throw std::system_error(errno, std::system_category(), "failed to get mount table info");
			break;
		}

		if (rdev && mnt->mnt_fsname[0] != '/')
			continue;

		if (lstat(mnt->mnt_dir, &statinfo) == 0) {
			if (statinfo.st_dev == dev)
				return std::string(mnt->mnt_dir);
		}

	} while (true);

	return std::string();
}

Parametr dev jest identyfikatorem poszukiwanego urządzenia, a rdev pozwala na określenie trybu dopasowania, czy maja być porównywane wszystkie systemy plików, czy tylko te “realne” będące fizycznymi urządzeniami.

W pakiecie gnulib można znaleźć bardzo ciekawą funkcje zwracająca listę zamontowanych systemów plików: read_file_system_list. Jej implementacja zawiera wiele definicji zależnych od używanego systemu i platformy, a także środowiska. Może być dobrym punktem wyjścia do implementacji funkcji GetMountPoint dla konkretnego systemu.

Windows

W systemie Windows dowiązania twarde wspierane są w systemie plików NTFS. Niestety dopiero w od wydania Visty, narzędzia niezbędne do ich obsługi - mklink i fsutil - zostały włączone na stałe do standardowej dystrybucji systemu, wcześniej trzeba było wykorzystywać zewnętrzne rozwiązania (fsutil można było pobrać ze stron Microsoftu lub FindLinks z sysinternals).

Licznik dowiązań pliku - NumberOfLinks

Podobnie jak w Linuksie, system pliku NTFS, przechowuje licznik referencji dowiązań w metadanych. Bezpośredni dostęp do tych danych nie jest możliwy za pomocą standardowych narzędzi konsolowych.

Programowo, można wykorzystać funkcję GetFileInformationByHandle, która podobnie jak posix-owy stat zwraca informacje o podanym pliku w odpowiedniej strukturze - BY_HANDLE_FILE_INFORMATION.

Implementacja funkcji GetHardLinkCount dla systemu Windows:

int GetFileLinkCount(const std::wstring& filename) {

	struct CloseHandleDeleter {
		typedef HANDLE pointer;
		void operator()(HANDLE handle) const { CloseHandle(handle); }
	};

	std::unique_ptr<HANDLE, CloseHandleDeleter> handle(
		CreateFileW(
			filename.c_str(), FILE_READ_ATTRIBUTES,
			FILE_SHARE_READ | FILE_SHARE_WRITE | FILE_SHARE_DELETE,
			NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL
		)
	);

	if (handle.get() == INVALID_HANDLE_VALUE)
		throw std::system_error(GetLastError(), std::system_category(), "failed to open file");

	BY_HANDLE_FILE_INFORMATION info;
	if (!GetFileInformationByHandle(handle.get(), &info))
		throw std::system_error(GetLastError(), std::system_category(), "failed to get file info");

	return info.nNumberOfLinks;
}

C Run-Time Library (CRT) kompilatora Visual C++ wspiera standard ANSI C i UNIX C, tym samym można wykorzystać subsystem POSIX wbudowany w systemy Microsoftu i skorzystać z funkcji stat.

Iteracja nazw dowiązań

Enumeracja nazw wszystkich łączy stałych do danych plików systemach Windows (NTFS) jest bardzo prosta. Narzędzie fsutil pozwala wylistować nazwy wszystkich dowiązań:

>fsutil hardlink list C:\Windows\notepad.exe
\Windows\winsxs\amd64_microsoft-windows-notepadwin_31bf3856ad364e35_6.1.7600.16385_none_9ebebe8614be1470\notepad.exe
\Windows\winsxs\amd64_microsoft-windows-notepad_31bf3856ad364e35_6.1.7600.16385_none_cb0f7f2289b0c21a\notepad.exe
\Windows\System32\notepad.exe
\Windows\notepad.exe

Programowo, Win32API zawiera odpowiednie do tego funkcje: FindFirstFileNameW i FindNextFileNameW, które odkryłem dzięki The Old New Thing.

Wykorzystując je w łatwy sposób można zaimplementować funkcję iterującą:

template<typename F>
void EnumerateHardLinks(const std::wstring& filename, F func) {

	WCHAR name[MAX_PATH];
	DWORD size = ARRAYSIZE(name);

	struct FindHandleDeleter {
		typedef HANDLE pointer;
		void operator()(HANDLE handle) const { FindClose(handle); }
	};

	std::unique_ptr<HANDLE, FindHandleDeleter> handle(
		FindFirstFileNameW(filename.c_str(), 0, &size, name)
	);

	if (handle.get() == INVALID_HANDLE_VALUE)
			throw std::system_error(GetLastError(), std::system_category(), "failed to get file name");

	func(name, size);

	while (true) {
		BOOL ret = FindNextFileNameW(handle.get(),  &size, name);
		if (!ret) {
			int error = GetLastError();
			if (error == ERROR_HANDLE_EOF)
				break;
			throw std::system_error(error, std::system_category(), "failed to get file name");
		}

		func(name, size);
	}

}

W implementacji EnumerateHardLinks, nie uwzględniono nazw plików (ścieżek) większych niż MAX_PATH, sam NTFS posiada limit 255 znaków UTF-16 na nazwę pliku, ale należy pamiętać, że my pobieramy pełną ścieżkę, limit kernela NT na nazwy to 32,767 UTF-16. Można w prosty sposób rozwiązać ten problem wykorzystując vector w roli bufora i powiększać jego pojemność, gdy funkcje FindFirstFileNameW i FindNextFileNameW zakończą się błędem z kodem ERROR_MORE_DATA. Wtedy wymagany rozmiar bufora zostanie zwrócony do zmiennej size.

Nazwy FindFirstFileNameW i FindNextFileNameW mogą sugerować, że następuje szukanie po drzewie plików, ale w rzeczywistości jest inaczej, dostęp do tych wszystkich danych nazw pliku jest bardzo szybki, można rzec że w stałym czasie. Nie trzeba iterować drzewa systemu plików, jak w przypadku systemów posixowych. Zgodnie z budową NTFS, wszystkie nazwy pliku trzymane są w atrybutach danego pliku - $FILE_NAME (0x30) znajdujących się w metadanych pliku, które z kolei zawarte są w Master File Table (MFT). Tak, więc funkcję te w rzeczywistości tylko iterują po tablicy trzymającej wszystkie nazwy danego pliku.

Funkcje te dostępne są tylko wersji UNICODE (suffix W), zatem interfejsy funkcji pobierającej licznik dowiązań i enumerującej ich nazwy, różnią się od tych przedstawionych we wstępie, typem reprezentującym napisy (wchar_t i std::wstring).

Uwagi

Wykrywanie hardlinków może być ciekawa lekcją, dzięki której można poznać bliżej system operacyjny lub system plików. Sam do końca nie wiedząc, jak nazwy dowiązań plików przechowywane są w NTFS-ie, uważałem ze funkcje API, o których pisałem wyżej, iterują drzewo pliku lub coś podobnego, a narzędzie fsutil działa podejrzanie szybko. Zmusiło mnie to do disassemblingu i reverse engineeringu, aby poznać jak to jest zrobione w tym toolsie, czy może nie używa jakiś wewnętrznych lub nieudokumentowanych funkcji, czy metod. A on korzysta właśnie z FindFirstFileNameW i FindNextFileNameW.

W implementacjach starłam się wykorzystywać dobre praktyki i idiomy języka C++, aby promować modern C++ i wykorzystanie wszystkich dostępnych obecnie możliwości tego języka. Jednym z widocznych tego skutków jest zastosowanie std::unique_ptr w roli RAII, co w rzeczy samej jest bardzo dobrym pomysłem i zalecanym posunięciem.

Odkąd w boost-cie, a także w STL-u zagościł ten typ inteligentnego wskaźnika, który może przyjąć własną definicję deletera, można w łatwy i przystępny sposób korzystać z idiomu RAII, bez pisania wielu wrapperów na różne typy zasobów.

Adam Sawicki, ładnie przedstawił, jak prosto wykorzystać unique_ptr wraz z zasobami i uchwytami zwracanymi poprzez większość funkcji WinAPI.

Głęboko wierze, że programiści C++ korzystają z tego idiomu, jak również wielu innych, w celu tworzenia prostszych, lepszych, bezpieczniejszych i czytelniejszych programów, z duchem nowoczesnego programowania w C++.