Файловые системы

Здесь мы пойдем от простого к сложному.

Очевидно, что никакая операционная система не сможет в полной мере воспользоваться чужой файловой системой, особенно атрибутами доступа; поэтому в описании каждой файловой системы говорится о том, как с ней обращается родная файловая система.

FAT

Название "FAT" - аббревиатура от "File Allocation Table". Том (volume) FAT (обычно занимающий целую дискету или раздел жесткого диска) имеет в своем составе:

• Boot Record (один сектор)

  содержит информацию о разделе и программу, запускающую ядро DOS или загрузчик другой OS.

• несколько (обычно две) копии FAT

  каждый элемент FAT соответствует одному из кластеров диска и содержит номер следующего кластера; 0 соответствует свободному кластеру, -1 соответствует последнему кластеру файла, -2 соответствует физически испорченному кластеру;

• Root (корневую директорию)

  на каждый файл отводится 32 байта:

  • 8 байт - имя файла (стертый файл помечается символом '\0xE5' вместо первой буквы имени);
  • 3 байта - расширение имени файла;
  • 1 байт - битовые атрибуты ReadOnly, Hidden, System, Volume, Directory и Archive от младшего бита к старшему;
  • 10 байт - зарезервировано;
  • 2 и 2 байта - время и дата последнего изменения файла;
  • 2 байта - начальный кластер файла;
  • 4 байта - размер файла;

• рабочее пространство, в котором располагаются файлы и поддиректории.

Первая неприятность связана с тем, что кластеры файла (вместе с приписанными к ним элементами FAT) образуют односвязный список. При последовательном чтении файла от начала к концу все нормально, но при работе с файлом прямого доступа, когда программа обращается к произвольно выбранным участкам файла, приходится перебирать список. В то время, когда создавался DOS, на той аппаратуре, на которой он создавался, просто не существовало носителей большого объема, а значит, проблема скорости при работе с файлом прямого доступа просто не возникала. Но по мере роста объема носителей встала дилема: надо наращивать либо размер кластера, теряя рабочее пространство в неполностью занятых кластерах, либо объем таблицы FAT, замедляя работу с файлами прямого доступа.

Первоначально использовался FAT12 - элемент FAT имел размер 12 бит, так что на диске могло быть до 4093 кластеров; этот тип FAT используется на дискетах и разделах жесткого диска до 8 мегабайт. С появлением жестких дисков был разработан FAT16, способный адресовать 65533 кластера (в обоих случаях три значения используются для внутренних целей). Ограничение числа кластеров разрядностью (размером) элемента FAT решили вопрос о компромисе между скоростью и экономным расходованием пространства в пользу скорости - на диске от одного до двух гигабайт размер кластера составляет 32 килобайта, а более двух гигабайт FAT-разделов не бывает. Файловые системы с компрессией (Stacker, DriveSpace) неожиданно позволили экономить место не столько за счет компрессии, сколько за счет более экономного использования рабочего пространства диска - все эти системы имеют собственные таблицы размещения данных и свободного места, хотя DOS по прежнему ведет FAT; удивительно, но ни одна из программ не внедряет собственную файловую систему, как это делает MSCDEX или любой сетевой редиректор.

К сожалению, я не нашел программ, способных форматировать дискеты и разделы жесткого диска с заданным мной размером кластера. Когда я переношу на дискете один большой файл (обычно архив), мне бы отлично подошел кластер максимального размера - меньше обращений в FAT и больше места остается под данные. А вот когда я создаю раздел на жестком диске размером 32 или 64 мегабайта, мне бы хотелось иметь размер кластера полкилобайта и килобайт соответственно, но format.com не делает размер кластера на жестком диске меньше двух килобайт. :-(

В Windows'95+OSR2 и Windows'98 используется FAT32 - ее формат я не знаю, но явно видно, что двух байт, отведенных в директоии для начального кластера, для FAT32 недостаточно. Почему для новой системы используется именно FAT, а не более совершенная система, я не понял; а если FAT32 существенно отличается от FAT12/16, то почему его называют "FAT", а не придумали ему более другое :-) название?

Вторая проблема связана с тем, что FAT не имеет в директории полей, которые могли бы помочь в поиске нужного файла, так что при открытии и удалении файла приходится искать соответствующую ему запись в директоии простым последовательным просмотром. При малом количестве файлов в машинах с первыми версиями DOS (которое лимитировалось объемом носителей) это не было особой проблемой, но с ростом объемов дисков и усложнением программ поиск нужного файла в директории стал существенно замедлять работу.

Вообще говоря, в Windows'9x/NT используется не FAT, а VFAT - для размещения длинных имен при сохранении совместимости задействуют другие поля, помечая их как Volume. Для DOS создается имя в формате "8.3" (8 букв на имя, точка-разделитель, три буквы на расширение имени). В результате поиск нужного имени еще более замедляется.

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

Имя файла с расширеним, передаваемое из программы DOS'у, всегда преобразуется к заглавным буквам, так что на диске присутствуют только заглавные буквы; если другая OS работает и с заглавными, и с прописными буквами, то ей придется либо преобразовывать регистр (особенно неприятно это для систем, которые считают прописные и заглавные буквы различными), либо рисковать, что файл, чье имя содержит прописные буквы, окажется недоступным в DOS, либо использовать расширение типа VFAT.

UFS (Unix File System)

Так же, как Unix представляет не одну систему, а ряд совместимых, так же UFS - не одна система, а целый ряд. Информации о поддержке разными Unix'ами чужих UFS у меня пока нет; информацию по поводу поддержки чужих файловых систем для каждого конкретного Unix'а скорее всего можно найти в документации к программе 'mount'.

Основным отличием UFS от других известных мне систем является выделение атрибутов файла в отдельном объекте файловой системе - inode; это позволяет иметь доступ к файлу (к набору данных, хранящихся в файле) более чем по одному имени (так называемый жесткий линк; см.ниже), а заодно повысить эффективность функционирования системы.

Классическая UFS Отводит на файл 16 байт - 14-буквенное имя файла и двухбайтный номер inode; современые UFS позволяют создавать длинные имена (до 255 символов), а имена файлов хранят не подряд, а более разумно - в двоичном дереве или hash-таблице, а номер inode может быть любым - четырехбайтным или восьмибайтным.

Сам блок inode содержит:

• количество ссылок на файл - каждое имя, ссылающееся на файл, а также открытие файла увеличивают этот счетчик на единицу; файл стирается с высвобождением занятого места как только счетчик становится равным нулю (т.е. можно стереть открытый файл, а реально он сотрется когда его закроют);
• размер файла;
• дату и время создания, последнего изменения и последего чтения файла;
• тип файла - в Unix это бывает:
  • обычный файл;
  • директория;
  • файл блочного устройства;
  • файл символьного (последовательного) устройства;
  • поименованный пайп (название происходит от символа "|", называемого "pipe" - см.его значение в shell);
  • символьный линк (алиас);

    обычный файл и директория встречаются во всех файловых системах; файлы устройств являются интерфейсами к драйверам этих устройств;

• UID (идентификатор хозяина файла) и GID (идентификатор группы);
• атрибуты доступа:
  • Unix использует атрибуты 'Read', 'Write' и 'eXecute' для хозяина файла (owner), для одногрупника (group) и для остальных (other) - итого 9 бит; для директории эти атрибуты означают соответственно права на чтение списка файлов, на создание/удаление файлов и на обращение к файлам внутри директории;

    важной особенностью является то, что права доступа для хозяина определяются атрибутами для него, права для одногрупника и остальных для хозяина игнорируются; аналогично для одногркпника не играют никакой роли права для остальных;

  • кроме них есть атрибуты SetUID и SetGID - для запускаемого файла (не интерпретируемого) эти атрибуты определяют запуск процесса под правами не запустившего их пользователя, а хозяина и/или группы файла соотвнтственно;
  • и еще есть один атрибут - для директории он запрещает стирание файлов, не принадлежащих стирающему;
• расширенный ACL (Access Control List, Список Управления Доступом) или ссылку на ACL, если файловая система поддерживает ACL;
• несколько (в классической UFS - 13) ссылок на кластеры файловой системы (раскладка приведена для классической UFS):
  • первые 10 указывают на первые 10 кластеров файла;
  • 11-й указывает на кластер, содержащий адреса следующих 128-ми кластеров файла (в классической UFS размер кластера - полкилобайта, а адрес кластера - четыре байта);
  • 12-й указывает на кластер, содержащий адреса 128-ми кластеров, в свою очередь содержащих адреса следующих 16`384-рех кластеров файла;
  • последний указывает на кластер, ... вобщем, здесь используется еще на один уровень больше, что позволяет адресовать еще 2`097`152 кластера файла;

    итого получается 2`113`674 кластера по полкилобайта - чуть более гигабайта в файловой системе, способной работать с томами до двух терабайт (2^{^32} кластеров по полкилобайта).

    В современных UFS многое изменено: можно задавать произвольный размер кластера и использовать 64-битные указатели, так что ограничени классической UFS давно преодолены. Основное преимущество такой адресации в том, что маленькие файлы, к которым часто обращаются, достижимы прямо из inode, и так же быстро происходит обращение к началу большого файла; обращение в середину и конец большого файла происходят медленнее, чем в начало, но я не представляю, как можно обеспечить бОльшую скорость, не налагая жесткого требования заведомой дефрагментированности файла или хотя бы таблицы размещения его кластеров.

Во многих UFS если после создания файла в кластер ничего не писалось (например, после открытия файла переместили указатель далеко-далеко и что-то туда записали), то под этот кластер не отводится место, а ссылке, которая должна на него указывать, присваивается 0 (это особенно актуально в свете использования hash-таблиц, которые обычно имеют внутри себя пустое пространство). То же самое делается если кластер оказывается заполнен нулями (незаполненное место считается залитым нулями, хотя полагаться на это программисту я бы не советовал). По-моему, неплохой способ экономии места.

Часть систем UFS реализованы как отказоустойчивые с жерналированием, а часть по традиции обходится без этого - считается, что если на машине хранятся действительно важные данные, то эту машину можно обеспечить бесперебойным питанием и не подпускать к ней ламеров.

NetWare

Сведений об устройстве файловой системы NetWare у мня нет - знаю лишь, что она какая-то своя, естественно, более эффективная, чем FAT, и имеет более сложные ACL, чем классический Unix с его 'rwx' для owner, group и other.

NTFS

NTFS (NT File System) - наследница HPFS (High Performance File System) из OS/2:

• Windows'NT'3.x работает и с NTFS, и с HPFS, но игнорирует ACL, имеющиеся в HPFS (мне кажется, что NTFS изначально была сделана чисто из коммерческих соображений с целью сделать диски несовместимыми с OS/2);
• Windows'NT'4.0 отказывается форматировать диски под HPFS, но тем не менее работает с ними;
• в ServicePack5 внесена возможность динамической компрессии указанных файлов (введен атрибут, задающий степень компрессии); изначально эта возможность была анонсирована для Windows'2000.

Если ACL и список кластера файла малы, они находятся в директории вместе с другими атрибутами файла; если же они велики, для них выделяется отдельный блок (примерно как в UFS). /* Информация из книги Ф.Зубанова "Windows'NT - выбор профи". */

Каждый элемент ACL содержит запрет или разрешение для отдельного пользователи или группы на доступ к файлу (надо уточнять...). При попытке доступа производится последовательный просмотр списка управления доступом, и применяется первое же правило, под которое попадает пользователь (примерно так же работает IP-FireWall в большинстве маршрутизаторов). При назначении же файлу прав доступа запреты размещаются перед разрешениями, а в конце автоматически стоит "запрет всем", так что если хоть один элемент ACL запрещает доступ или если нет ни одного указания о пользователе, то в доступе будет отказано (исповедуется принцип "лучше запретить, чем разрешить"). (Меня удивляет, что ACL просматривается последовательно - можно было бы придумать более эффективный алгоритм просмотра больших ACL.)

Файлы хранятся в виде сбалансированного (без учета того, что к одним файлам обращаются чаще, чем к другим) двоичного дерева; при создании/удалении файла Windows'NT просматривает дерево и производит перебалансировку.

В NTFS предусмотрено ведение отказоустойчивой файловой системы - каждая операция, потенциально способная при сбое питания нарушить целостность файловой системы, производится как транзакция, т.е. сначала на диск (именно на диск - никакой отложенной записи!) записывается, что надо сделать (составляется задание на проведение транзакции), а затем вносятся изменения собственно в файловую систему. Если произошел сбой питания, то при включении Windows'NT просмотрит журнал заданий на проведение транзакций и выполнит те, которые помечены как начатые, но незаконченные.

Если файл удаляется, то Windows'NT не только удаляет запись о нем в директории и помечает занимаемое файлом место как свободное, но и затирает данные, содержавшиеся в файле - как в кэше, так и на диске (аналогично поступается с возвращаемой системе оперативной памятью - как физической, так и виртуальной). Это делается чтобы другая программа не получила случайно доступ к выброшенным другой программой секретным данным.

Последовательный просмотр ACL, регулярная балансировка двоичных деревьев в директориях, транзакционное выполнение операций с файловой системой и затирание данных на диске очень плохо отражается на производительности. Например, я пишу этот пассаж в редакторе МикроМир в DOS-сессии под Windows'NT'4.0 (да, я не люблю Windows'NT - просто я дежурю в фирме Монолит, а тут стоит Windows'NT, которой мне разрешили пользоваться), и на Pentium она тормозит сильнее, чем DOS-сессия в Windows'3.11 на 486! А все из-за того, что какая-то фоновая задача (знал бы, какая - убил бы!) каждые несколько секунд пишет что-то на диск (я слышу, как хрустят головки, перемещаемые с одного цилиндра на другой).

Атрибуты доступа

Атрибуты доступа FAT находятся вне конкуренции как по простоте, так и по бесполезности - DOS создавался как одноюзерская система, так что никакого разграничения доступа в FAT не предусмотрено, а зарезервированные 10 байт практически никто не пытался использовать. Поэтому за отсутствием сведений о файловой системе NetWare придется сравнивать UFS и NTFS.

По сравнению с NTFS, в которой можно с точностью до юзера назначить правА доступа к каждому файлу, UFS выглядит до предела примитивной; естественно, за счет примитивности обеспечивается существенно более высокая производительность. Если используется модель вычислений, в которой каждый элемент информации хранится в отдельном файле (например, большинство редакторов считаю тождественными понятия "файл" и "документ"), то развитая система ACL просто необходима; с другой стороны, появляется все больше систем, которые располагают документы не в отдельных файлах, а совершенно иначе; в качестве примера приведу организацию почтового ящика в Netscape Navigator, где все письма хранятся в одном файле, а в другом файле хранятся индексы, позволяющие быстро найти нужное письмо.

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

Гипотетически можно представить себе файловую систему, в которой можно задать ограничения доступа не только ко всему файлу, но и к отдельным частям файла; более того - алгоритм вычисления тех участков, к которым разрешен доступ, можно задавать в виде формул или даже программ (скриптов). Но рассмотрим такую задачу: каждый клиент системы имеет право переводить деньги со своего счета на чужой, но не обратно; для усложнения задачи можно добавить, что счета ведутся в разных валютах, и при переводе деньги должны пересчитываться по некоторому заданному в отдельном файле курсу. Файл, как он понимается в Unix и наследующих это понимание DOS, Windows'* и NetWare, является неструктурированным массивом байтов, так что понятия, связанные с увеличением/уменьшением суммы на счету, выше понимания файловой системы.

Из приведеного примера видно, что защита нужна не файлам, а данным! Это значит, что распределение прав доступа должна вести не универсальная программа типа драйвера файловой системы, а программа, детально знакомая со структурой данных - в данном примере это СУБД (Система Управления Базой Данных), которая может (а в ряде случаев просто обязана) вести собственную политику доступа, независимую от политики OS. В этом случае к файлам, содержащим БД, должен быть предоставлен полный доступ для СУБД и отказано в доступе для всех остальных; никакихсложных ACL в этом случае не нужно, да и простые атрибуты Unix оказываются слегка избыточными в том, что касается прав доступа для одногрупника.

Должна ли СУБД быть резидентной (постоянно запущенной) программой? Сервис в Windows'NT, NLM (NetWare Loaded Module) в сервису NetWare и демон в Unix - пример реализации такого подхода; но в Unix есть способ запуска демона в режиме сервиса (пусть никого не обманет одинаковое название "сервис" в Unix и Windows'NT - сервис в Windows'NT аналогичен демону в Unix, а сервис в Unix не имеет аналога в других OS), когда демон inetd запускает при обращениик порту Internet заданную программу, а пока эта программа не нужна, она не запущена.

Но в Unix есть еще один способ: если файлу с программой присвоен атрибут SetUID, то процесс будет запущен с правами не того юзера, который запустил эту программу, а с правами хозяина файла. Это означает, что любой пользователь без уведомления администратора машины в принципе может написать (или найти) программу, которая делает только то, что нужно; присвоить ей атрибут SetUID - и тем самым доверить другим выполнение некоторых операций от своего имени. Именно так работает программа passwd - она запускается с правами root; выясняет, кто ее запустил; и меняет пароль запустившего ее юзера на указанный, имея прямой доступ к файлам, в которых хранятся пароли всех юзеров.

Вообще-то такой способ предоставления прав доступа достаточно опасен, особенно если программа запускается с правами root (это относится к любым операционным системам и любому способу запуска программы); впрочем, кажется, никто (кроме, пожалуй, одной всемирно известной фирмы, которая начинает выпускать заплатки к своим продуктам чуть ли не раньше, чем эти продукты поступают в продажу) не отрицает необходимость корректного написания системных программ, а корректно написанная программа плохого не сделает.

По материалам ресурса ComER