Como os diretórios são implementados nos sistemas de arquivos Unix?

19

Minha pergunta é como os diretórios são implementados? Eu posso acreditar em uma estrutura de dados como uma variável, por exemplo, tabela, matriz ou similar. Como o UNIX é Open Source, posso procurar na fonte o que o programa faz quando criou um novo diretório. Você pode me dizer onde procurar ou elaborar o tópico? Que um diretório "é" um arquivo que eu poderia entender e um diretório é realmente um arquivo? Não sei se é verdade que os arquivos são armazenados "em" enquanto ainda assim você poderia dizer o arquivo do word sobre quase tudo e não sei o que absolutamente não é um arquivo, pois você pode chamar mesmo uma variável de Arquivo. Por exemplo, um link certamente não é um arquivo e um link é como um diretório, mas isso viola o fato de um diretório ser um arquivo?

Niklas
fonte
1
Você está interessado em algum sistema de arquivos específico?
Ignacio Vazquez-Abrams
3
No UNIX, tudo é um arquivo (sabedoria histórica). Mas nem todo UNIX é de código aberto. Gnu não é Unix, sabia? O Open Solaris é um Unix de código aberto, enquanto o Linux é apenas um SO unixóide. :) E sim - sistemas de arquivos - Reiserfs? Ext2-3-4? XFS? NFS?
usuário desconhecido
2
Um link também é realmente um arquivo.
mattdm
5
Um link simbólico é um arquivo. Um link físico é uma vantagem no gráfico do sistema de arquivos.
dmckee
3
Anúncio: você pode estar interessado na proposta do site de desenvolvimento de sistemas operacionais .
Gilles 'SO- stop be evil'

Respostas:

22

A estrutura interna dos diretórios depende do sistema de arquivos em uso. Se você quiser saber exatamente o que acontece, dê uma olhada nas implementações do sistema de arquivos.

Basicamente, na maioria dos sistemas de arquivos, um diretório é uma matriz associativa entre nomes de arquivos (chaves) e números de inodes (valores). Algo assim¹:

1167010 .
1158721 ..
1167626 subdir
 132651 barfile
 132650 bazfile

Esta lista é codificada de maneira mais ou menos eficiente dentro de uma cadeia de (geralmente) blocos de 4KB. Observe que o conteúdo dos arquivos regulares é armazenado de maneira semelhante. No caso de diretórios, não faz sentido saber qual tamanho é realmente usado dentro desses blocos. É por isso que os tamanhos dos diretórios relatados por dusão múltiplos de 4KB.

Os inodes existem para unir blocos, formando uma única entidade, a saber, um 'arquivo' no sentido geral. Eles são identificados por um número que é algum tipo de endereço e cada um é geralmente armazenado como um único bloco especial.

O gerenciamento de tudo isso acontece no modo kernel. O software apenas pede a criação de um diretório com uma função chamada int mkdir(const char *pathname, mode_t mode);levando a uma chamada do sistema, e todo o resto é realizado nos bastidores.

Sobre a estrutura de links:

Um link físico não é um arquivo, é apenas uma nova entrada de diretório (isto é, uma associação nome - número de inode ) referente a uma entidade de inode preexistente². Isso significa que o mesmo inode pode ser acessado a partir de diferentes nomes de caminho. Em particular, como os metadados (permissões, propriedade, registros de data e hora ...) são armazenados no inode, eles são únicos e independentes do nome do caminho escolhido para acessar o arquivo.

Um link simbólico é um arquivo e é distinto do seu destino. Isso significa que ele tem seu próprio inode. Costumava ser tratado como um arquivo normal: o caminho de destino era armazenado em um bloco de dados. Mas agora, por razões de eficiência em sistemas de arquivos ext recentes , caminhos com menos de 60 bytes de comprimento são armazenados no próprio inode (usando os campos que normalmente seriam usados ​​para armazenar os ponteiros nos blocos de dados).

-
1. isto foi obtido usando ls -ai1 testdir.
2. cujo tipo deve ser diferente de 'diretório' hoje em dia.

Stéphane Gimenez
fonte
Obrigado pela elaboração, para que eu possa entender a diferença entre diretórios e arquivos em nível programático.
Niklas
12

Para expandir a postagem de Stéphane Gimenez, criar um novo diretório é o processo de criar um novo inode com o valor st_mode de S_IFDIR (com o modo de permissões), criando duas entradas no primeiro bloco de dados do novo inode com o link ( 2) chamada do sistema: '.' que aponta para este novo inode e '..' que aponta para o diretório pai e, em seguida, cria uma entrada no diretório pai com o inode e o nome do novo diretório - a primeira e a última parte são feitas pela chamada de sistema mknod ( 2) Além disso, apenas o root pode usar o mknod (2) atualmente para tarefas como as que estamos falando.

Por exemplo, mkdir("/home/larry.user/xyzzy", 0666)é essencialmente o seguinte (esse era o código C dos dias SysV [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 System Programming", 1987, pp69-71.

Como era propenso a erros (e um dos principais motivos do fsck), uma chamada de sistema mkdir (2) foi criada para poder fazer isso por você.

Observe que um objeto do sistema de arquivos amy pode ser criado com o mknod (2): arquivo regular, diretório, arquivo do dispositivo, link simbólico etc. Então, para responder a uma das perguntas do OP, sim, um diretório é um arquivo, o que significa dizer "ele é um objeto, representado por um inode, residente em um sistema de arquivos que se comporta com uma interface de E / S ".

Arcege
fonte
Obrigado pela resposta muito interessante. Entendo e acho que também posso procurar na fonte o programa touchque cria um arquivo vazio e ver o que ele faz.
Niklas
2

se você deseja obter mais informações sobre sistemas de arquivos Unix / Linux, recomendo 2 livros: Noções básicas sobre o kernel do Linux e o desenvolvimento do kernel do Linux . Esses são os melhores livros para entender o kernel do Linux.

Nos sistemas Unix "Common File Model", cada diretório é considerado um arquivo, que contém uma lista de arquivos e diretórios.

No VFS (Virtual File Systems), os diretórios são representados em uma estrutura chamada dentry. A dentry é uma estrutura C com um nome de cadeia ( d_name ), um ponteiro para uma inodo ( d_inode ) e um ponteiro para o dentry-mãe ( d_parent ). Um inode é uma estrutura para lidar com informações sobre um arquivo no sistema de arquivos. Por exemplo, se você tiver o diretório /tmp/test/foo, o VFS criará um objeto de dentry para cada componente no nome do caminho. Portanto, ele criará um objeto de dentry para /, um segundo objeto de dentry para a testentrada do diretório raiz e um terceiro objeto de dentry para a fooentrada do diretório de teste.

Dimitri
fonte
Obrigado Dimitri. Quero entender por que algum projeto escolheu uma estrutura de dados específica, como uma árvore B, uma árvore binária, uma série trie ou associativa. Eu acho que é importante escolher uma estrutura de dados / modelo de dados adequados. Aprender sobre as diferentes implementações fornece os detalhes que estou procurando.
Niklas
1

Você pode começar lendo http://www.freebsd.org/doc/en/books/design-44bsd/book.html#OVERVIEW-FILESYSTEM . Para mais detalhes, obtenha o excelente livro clássico "O Projeto e Implementação do Sistema Operacional 4.4 BSD".

estalar
fonte
Obrigado pelo link. Eu entendo que ambos os arquivos são diretórios, basicamente, são matrizes que são interpretadas como arquivos ou diretórios. Por favor me corrijam se eu estiver errado ..
Niklas
1
Os diretórios são tradicionalmente apenas arquivos especialmente formatados, mas isso não é mais verdade: en.wikipedia.org/wiki/ReiserFS#Design No ReiserFS e em alguns outros, diretórios são entradas em um banco de dados. Os diretórios podem atuar como matrizes, mas isso é apenas a abstração da programação.
precisa
Muito obrigado por apontar os detalhes. Agora eu acho que entendo mais como os sistemas de arquivos funcionam e ainda me pergunto como e por que o programa locatefunciona e como isso está relacionado à atualização do programa de localização executando updatedb(por exemplo, uso PC-BSD, DragonflyBSD e Ubuntu Natty inicializando a partir de Live CDs e comparando diferentes instalações e interfaces)
Niklas