В.Д. Валединский - Избранные главы лекций по программированию (1114957), страница 3
Текст из файла (страница 3)
Если FileType = 0, то INode считается свободным.Поле Rights описывает права доступа к файлу. UNIX изначально разрабатывалась в качестве многопользовательской системы. Поле Rights содержит 3 группы флагов доступа: первая группа относится к самомувладельцу файла, вторая группа — к группе пользователей, к которой принадлежит владелец файла, третьягруппа описывает права доступа к файлу для всех остальных пользователей. Каждая группа флагов состоитиз 3 флагов (по 1 биту на флаг). Первый флаг отвечает за право чтения файла (Read), второй флаг — за правозаписи в файл (Write), третий флаг — за право запуска файла на выполнение (eXecute).
Если флаг установленв 1, данное право есть, если флаг сброшен в 0, данного права нет. Каждую группу можно представить полем из3 бит, т. е. числом от 0 до 7, а все три группы флагов записываются в виде 3 десятичных цифр 0..7. Рассмотримпример. Пусть Rights представлены в виде 761. Имеем 7=111=RWX, 6=110=RW-, 1=001=--X. Итак, владелец можетчитать, изменять и запускать файл, группе разрешено чтение и запись, а всем остальным разрешён толькозапуск.С точки зрения организации структур данных, таблица блоков является наиболее интересной.
Она описывает расположение дисковых блоков, в которых находится содержимое файла. Её размер фиксирован для даннойФС, однако в различных реализациях ФС они бывают длиной от 13 до 16 ячеек типа int. Если ячейка не используется, туда записывается 0.
Записи 0-9 содержат физические номера блоков, в которых лежат первые 10 блоков7файла c 0-го по 9-й. Если файл небольшой, и на него хватает 10 блоков, то проблем не возникает. Если 10 блоков для хранения файла недостаточно, тогда могут использоваться ячейки BlockTable[10]..BlockTable[15] —косвенные ссылки 1-ого — 6-ого уровня. Косвенная ссылка 1-ого уровня — это номер дискового блока с номерамипоследовательных блоков файла, начиная с 10-ого. Если блок содержит 29 байт, то в каждый блок мы можемпоместить 29 : 22 = 128 номеров последовательных блоков.0BlockTable123Disk[123]File[0]...st19Link38055...Disk[380]File[9]Disk[55]80...Disk[80]File[10]315Disk[315]File[10+128-1]Так мы сможем адресовать блоки файла с номерами 10..(10 + 128 − 1).
Если файл не помещается в (10 +128) блоков, то используется косвенная ссылка второго уровня. Она содержит номер блока, который содержитномера блоков, которые содержат номера блоков файла (10 + 128)..(10 + 128 + 1282 − 1). Таким образом, ссылкавторого уровня — это нечто вроде B-дерева номеров блоков глубины 2. Аналогично определяются ссылки болеевысоких уровней. Поскольку количество адресуемых блоков растёт как степени 128, шести ссылок будет болеечем достаточно в ближайшем обозримом будущем.Рассмотрим пример, в котором массив File[] представляет файл, разбитый на блоки, а массив Disk[] —модель диска с линейной адресацией2 физических блоков.При такой организации ФС восстановление файла становится почти невозможным: стоит уничтожить INode,соответствующий файлу, и никакая сила не поможет нам найти корень дерева блоков.Рассмотрим работу ФС на примере создания файла.
Для начала нам нужно найти свободный INode, а еслиего нет, то необходимо сообщить о том, что файл создать нельзя. Здесь необходимо отметить, что поиск свободного INode в большой таблице INodeArray — операция довольно длительная. Поэтому применяется следующаясхема: все индексы свободных INode объединяются в список, который хранится в отдельном блоке. В частности,номер этого служебного блока, как и прочая информация о состоянии ФС, хранится в SuperBlock. Кроме того,в SuperBlock хранится номер первого свободного INode. Подобные хитрости позволяют ускорить поиск.Допустим, однако, что INode найден. Отметим, что пока неясно, как найтисвободный блок для записи в него полезной информации.
Все номера свободныхблоков собираются в блочный стек, растущий из блока, номер которого такжепрописан в SuperBlock. При этом первый элемент каждого блока стека — ссылкана следующий блок, если он есть, остальные содержат номера свободных блоков.Когда очередной блок отводится под файл, он убирается из стека.
Если, наоборот,файл удаляется, то блоки добавляются в этот стек.Что касается имён файлов, то для их хранения предназначены файлыкаталоги. С помощью таких файлов и поддерживается древесная структура ФС Фактически файл-каталог —это просто таблица, сопоставляющая имена файлов и номера их INode. При этом разные имена могут ссылатьсяна один и тот же INode. В этом случае говорят, что это hard link, или жёсткая ссылка, на INode.
Кроме жёстких,бывают и мягкие ссылки (soft link ): это INode, ссылающийся на блоки файла с другим INode.Отметим ещё одну полезную особенность этой ФС: в файлах могут быть сколь угодно большие «дырки»,т. е. места, куда никогда не производилась запись. Например, ничто не мешает нам оставить нулевыми поляBlockTable[0]..BlockTable[10], а использовать только косвенные ссылки второго уровня.В заключение отметим, что в EXT3 были предприняты некоторые шаги по улучшению положения с восстановлением удалённых файлов.2 Существует два способа адресации физических блоков. Первый способ, используемый в BIOS, появился исходя из принциповфизической организации диска. В нём блоки нумеруются тройкой (Head, Track, Sector). Второй способ используется операционнымисистемами и заключается в последовательной нумерации всех блоков на всех дорожках по всем сторонам диска — Прим.
ред.82.3. NTFS (New Technology File System)Мы рассмотрим два типа файловых систем NTFS — систему WINNT4 (NT4) и WIN2000/XP (NT5). Ониимеют сходную идеологию, но есть и различия. В частности, NT5 оказывается более экономичной, если файлне разрежен, т. е. в нём нет дырок.Раздел NTFS разбит на 3 куска: BOOT Record, Master File Table (MFT), DATA.
MFT разбита на куски по 1Кб. Область Data разбивается на кластеры размером от 512 до 4096 байт. На MFT выделяется фиксированноедисковое пространство — около 15% общего объёма раздела. Это число может варьироваться, и в зависимости отпотребностей может быть увеличено до 50%. Далее мы увидим, что это место может вовсе не пропадать даромблагодаря тому, что в области данных MFT может храниться и полезная информация, в частности, содержимоенебольших файлов.В NTFS файл представляет собой набор атрибутов.
Каждая запись MFT представляет собой последовательность кусков данных, снабжённых заголовками. Эти куски и называются атрибутами. Считав заголовок, мыможем определить размер данного атрибута и затем без труда выковыривать из него информацию. Всю последовательность кусков предваряет общий заголовок, содержащий информацию о количестве атрибутов и т. д.16 записей MFT отводятся под служебные файлы (MetaFile), жизненно важные для работы файловой системы:• $MFT — собственно MFT.
В системе она представлена как файл.• $MFTMirr — зеркальное отражение MFT — файл с копией начала MFT для повышения надёжности.• $LogFile — протокол работы ФС, обепечивающий транзакционный механизм, наподобие того, как этосделано в больших СУБД типа Oracle или Sybase. В случае неудачного завершения какой-либо операцииесть возможность сделать откат (rollback) к предыдущему состоянию.• $Volume — описание данного дискового тома. NTFS позволяет объединять несколько физических устройствв один логический раздел.• $AttrDef — описание всех атрибутов, встречающихся в данной ФС.• $ — корневой каталог (имени не имеет).• $BitMap — битовое множество всех свободных кластеров.• $Boot — загрузочная запись.• $BadClus — список плохих кластеров.• $Secure — Security Descriptors — дескрипторы безопасности.• $Upcase — соответствие больших и маленьких букв.
Имена в NTFS хранятся в UNICODE, поэтому, чтобыиметь возможность иногда не различать верхний и нижний регистр, создаётся таблица UpCase.• $Extend — Дескриптор расширений ФС.Каждый файл имеет свой 64-битный идентификатор (File ID), который состоит из 16-битного счётчикаSequence Number и 48-битного идентификатора (Record Index), являющегося индексом в таблице MFT.Перечислим атрибуты, использующиеся в ФС.Standard InformationAttribute ListVolume NameIndex AllocationFile NameObject IDVolume InfoBitmapSecurity DescriptorReparse PointIndex RootDataЗапись в MFT устроена так: заголовок содержит File ID и Base Record Index. Base Record Index — индексбазовой записи — указывает на базовую запись MFT, поскольку их может быть несколько для одного файла.Далее следуют атрибуты, например, имя файла и его данные.
Атрибуты делятся на резидентные и нерезидентные. Резидентный атрибут — атрибут, данные которого содержатся прямо в MFT, т. е. за ними никуда ненадо лезть. Нерезидентность атрибута означает, что в MFT хранится ссылка на данные атрибута, хранящиесяв области раздела DATA.Index Root — дескриптор небольшого по размеру каталога. Такой атрибут резидентен. Index Allocation —дескриптор большого каталога.
Такой атрибут нерезидентен, и в самом атрибуте хранится ссылка на кореньB-дерева с ID файлов, упорядоченными по именам. Узлы этого B-дерева сложены в кластеры.Всё сказанное выше в равной мере справедливо для систем NT4 и NT5. Теперь займёмся описанием атрибутаData для файлов в NT4.Атрибут Data представляет собой цепочку элементов, называемых run-ами (от слова «run» — бежать). Каждый run состоит из 3 чисел: VCN, LCN, CL.
Здесь• VCN (Virtual Cluster Number) — виртуальный номер кластера. Этот номер соответствует порядковомуномеру кластера в файле.9• LCN (Logical Cluster Number) — логический номер кластера. Этот номер соответствует номеру кластерана диске, т. е. его физическому номеру.• CL (Chain Length) — длина цепочки.Пример 3.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
