Как каталоги реализованы в файловых системах Unix?

19

У меня вопрос, как каталоги реализованы? Я могу поверить, что структура данных, как переменная, например, таблица, массив или подобное. Поскольку UNIX является открытым исходным кодом, я могу посмотреть в исходном коде, что делает программа, когда она создала новый каталог. Можете ли вы сказать мне, где искать или уточнить тему? Что каталог "это" файл, который я мог понять, и действительно ли каталог является файлом? Я не уверен, что это правда, что файлы хранятся «в» файлах, в то время как вы можете сказать слово файл почти обо всем, и я не уверен, что это абсолютно не файл, так как вы могли бы назвать даже переменную a файл. Например, ссылка, конечно, не файл, а ссылка похожа на каталог, но тогда это нарушает, что каталог является файлом?

Никлас
источник
1
Вы заинтересованы в какой-либо конкретной файловой системе?
Игнасио Васкес-Абрамс
3
В UNIX все является файлом (историческая мудрость). Но не каждый UNIX является открытым исходным кодом. Знаешь, GNU - это не Unix? Open Solaris - это Unix с открытым исходным кодом, в то время как Linux - только Unixoid OS. :) И да - файловые системы - Reiserfs? Ext2-3-4? XFS? NFS?
пользователь неизвестен
2
Ссылка на самом деле тоже файл.
Mattdm
5
Символическая ссылка является файлом. Жесткая ссылка - это грань в графе файловой системы.
dmckee
3
Реклама: вас может заинтересовать предложение по разработке операционных систем .
Жиль "ТАК - перестань быть злым"

Ответы:

22

Внутренняя структура каталогов зависит от используемой файловой системы. Если вы хотите точно знать, что происходит, взгляните на реализации файловой системы.

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

1167010 .
1158721 ..
1167626 subdir
 132651 barfile
 132650 bazfile

Этот список закодирован некоторым - более или менее эффективным способом - внутри цепочки (обычно) блоков по 4 КБ. Обратите внимание, что содержимое обычных файлов хранится аналогично. В случае каталогов нет смысла знать, какой размер фактически используется внутри этих блоков. Вот почему размеры каталогов, о которых сообщается du, кратны 4 КБ.

Иноды существуют для того, чтобы связать блоки вместе, образуя единый объект, а именно «файл» в общем смысле. Они идентифицируются по номеру, который является своего рода адресом, и каждый из них обычно хранится в виде отдельного специального блока.

Управление всем этим происходит в режиме ядра. Программное обеспечение просто запрашивает создание каталога с именем функции, int mkdir(const char *pathname, mode_t mode);ведущей к системному вызову, а все остальное выполняется за кулисами.

О структуре ссылок:

Жесткая ссылка - это не файл, это просто новая запись в каталоге (т. Е. Связь имени с номером инода ), относящаяся к существующей сущности инода2. Это означает, что к одному и тому же иноду можно обращаться с разных путей. В частности, поскольку метаданные (права доступа, владение, метки времени ...) хранятся в inode, они уникальны и не зависят от пути, выбранного для доступа к файлу.

Символическая ссылка - это файл, и он отличается от своей цели. Это означает, что у него есть свой собственный инод. Раньше он обрабатывался как обычный файл: целевой путь хранился в блоке данных. Но теперь, из соображений эффективности в последних файловых системах ext , пути длиной менее 60 байтов хранятся в самом inode (используя поля, которые обычно используются для хранения указателей на блоки данных).

-
1. это было получено с помощью ls -ai1 testdir.
2. чей тип должен отличаться от 'directory' в наше время.

Стефан Хименес
источник
Спасибо за разработку, чтобы я мог понять разницу между каталогами и файлами на программном уровне.
Никлас
12

Чтобы раскрыть сообщение от Стефана Гименеса, создание нового каталога - это процесс создания нового инода со значением st_mode S_IFDIR (в режиме разрешений), создание двух записей в первом блоке данных нового инода со ссылкой ( 2) системный вызов: '.' который указывает на этот новый индекс и '..', который указывает на родительский каталог, затем создает запись в родительском каталоге с индексом и именем нового каталога - первая и последняя часть выполняются системным вызовом mknod ( 2). Кроме того, только root может использовать mknod (2) в наши дни для таких задач, о которых мы говорим.

Например, mkdir("/home/larry.user/xyzzy", 0666)по сути, следующее (это был код C из SysV days [1]):

int mode = 0666;
char newdir[] = "/home/larry.user/xyzzy";
char path1[NAMESZ+4, path2[NAMESZ+4], *p;
mknod(newdir, S_IFDIR|mode);
strcpy(path1, newdir);
strcat(path1, "/."); /* "." link */
link(newdir, path1);
strcat(path1, ".");  /* ".." link */
strcpy(path2, newdir);
if ((p = strrchr(path2, '/') == (char *)0) /* root directory */
    link(".", path1);
else {
    *p = '\0';
    link(path2, path1);
}
  1. Haviland & Salama, "Системное программирование в UNIX", 1987, стр. 69-71.

Это было слишком подвержено ошибкам (и одной из основных причин fsck), поэтому системный вызов mkdir (2) был создан, чтобы сделать это за вас.

Обратите внимание, что любой объект файловой системы может быть создан с помощью mknod (2): обычный файл, каталог, файл устройства, символическая ссылка и т. Д. Поэтому, чтобы ответить на один из вопросов ОП, да, каталог - это файл, что означает: «он является объектом, представленным inode, находящимся в файловой системе, которая работает с интерфейсом ввода / вывода ".

Arcege
источник
Спасибо за очень интересный ответ. Я понимаю и думаю, что могу также посмотреть в исходном коде программу, touchкоторая создает пустой файл, и посмотреть, что он делает.
Никлас
2

если вы хотите получить больше информации о файловых системах Unix / Linux, я рекомендую вам две книги « Понимание ядра Linux и разработка ядра Linux» . Это лучшие книги для понимания ядра Linux.

В Unix-системах «Common File Model» каждый каталог рассматривается как файл, который содержит список файлов и каталогов.

В VFS (виртуальные файловые системы) каталоги представлены в виде структуры dentry. Это dentry структура C с именем строки ( d_name ), указателем на inode ( d_inode ) и указателем на родительский dentry ( d_parent ). Inode - это структура для обработки информации о файле в файловой системе. Например, если у вас есть каталог /tmp/test/foo, VFS создаст объект dentry для каждого компонента в имени пути. Таким образом, он создаст объект dentry для /второго объекта dentry для testвхода в корневой каталог и третий объект dentry для fooвхода в тестовый каталог.

Dimitri
источник
Спасибо, Дмитрий. Я хочу понять, почему какой-то проект выбрал определенную структуру данных, такую ​​как B-дерево, двоичное дерево, три или ассоциативный массив. Я думаю, что важно выбрать подходящую структуру данных / модель данных. Изучение различных реализаций дает детали, которые я ищу.
Никлас
1

Вы можете начать с чтения http://www.freebsd.org/doc/en/books/design-44bsd/book.html#OVERVIEW-FILESYSTEM . Для получения более подробной информации получите отличную классическую книгу «Разработка и внедрение операционной системы 4.4 BSD».

щелчок
источник
Спасибо за ссылку. Я понимаю, что оба файла являются каталогами, в основном это массивы, которые интерпретируются как файлы или каталоги. Пожалуйста, поправьте меня, если я ошибаюсь ..
Никлас
1
Каталоги традиционно представляют собой просто специально отформатированные файлы, но это уже не так: en.wikipedia.org/wiki/ReiserFS#Design В ReiserFS и некоторых других каталогах являются записями в базе данных. Каталоги могут выступать в качестве массивов, но это всего лишь абстракция программирования.
Брюс Эдигер
Большое спасибо за указание деталей. Теперь я думаю, что я больше понимаю, как работают файловые системы, все еще задаваясь вопросом, как и почему программа locateработает и как это связано с обновлением программы locate при запуске updatedb(в частности, я использую загрузку с PC-BSD, DragonflyBSD и Ubuntu Natty с Live CD и сравнение различных установок. и интерфейсы)
Никлас