O que significam os “recursos habilitados” no GNU?

8

Quando eu uso find --version com o GNU find, recebo algo assim:

find (GNU findutils) 4.5.9     
[license text]
Features enabled: D_TYPE O_NOFOLLOW(enabled) LEAF_OPTIMISATION FTS(FTS_CWDFD) CBO(level=2)

O que esses "recursos" significam? Há alguma referência a O_NOFOLLOW ser uma medida de segurança em man find e há uma menção de LEAF_OPTIMISATION sendo uma otimização que economiza algumas% delstat de chamadas em nós de folha. Mas não consigo encontrar nada sobre FTS , D_TYPE ou CBO .

    
por nneonneo 17.02.2015 / 21:10

3 respostas

8

Esta é uma resposta completa derivada das respostas de Ketan e Daniel Kullman, assim como minha própria pesquisa.

A maioria dos "recursos" acabam sendo otimizações de consulta, já que find é, em geral, capaz de consultas (quase) arbitrariamente complexas no sistema de arquivos.

D_TYPE

A presença do recurso D_TYPE significa que find foi compilado com suporte para o campo d_type em struct dirent . Este campo é uma extensão BSD também adotada pelo Linux, que fornece o tipo de arquivo (diretório, arquivo, pipe, socket, dispositivo char / block, etc.) na estrutura retornada de readdir e amigos. Como uma otimização, find pode usar isso para reduzir ou eliminar lstat das chamadas quando -type é usado como uma expressão de filtro.

readdir nem sempre pode preencher d_type em alguns sistemas de arquivos, então, às vezes, um lstat ainda será necessário.

Mais informações na documentação oficial: link

O_NOFOLLOW

Esta opção irá ler (enabled) ou (disabled) . Se presente e ativado, esse recurso implementa uma medida de segurança que protege find de certos ataques de corrida TOCTTOU. Especificamente, ele evita que find atravesse um link simbólico durante a execução do diretório, o que poderia ocorrer se o diretório fosse substituído por um link simbólico depois que o tipo de arquivo do diretório fosse verificado, mas antes da entrada do diretório.

Com essa opção ativada, find usará open(..., O_NOFOLLOW) no diretório para abrir apenas os diretórios reais e, em seguida, usar openat para abrir arquivos nesse diretório.

LEAF_OPTIMISATION

Essa otimização um pouco obscura permite que find deduza quais subdiretórios de um diretório pai são diretórios usando a contagem de links do diretório pai, já que os subdiretórios contribuirão para a contagem de links do pai (por meio do link .. ) . Em determinadas circunstâncias, permitirá que find elimine uma chamada stat . No entanto, se o sistema de arquivos ou o SO representar incorretamente o st_nlinks , ele poderá fazer com que find produza resultados falsos (isso é, felizmente, uma ocorrência muito rara).

Mais informações na documentação oficial: link

FTS

Quando ativado, o recurso FTS faz com que find use o fts API para percorrer a hierarquia de arquivos, em vez de uma implementação recursiva direta.

Não está claro para mim qual é a vantagem de fts , mas FTS é basicamente o padrão em todas as versões find padrão que vi até agora.

Mais informações: link , link

CBO

Acontece que (depois de ler o código-fonte find como sugerido por daniel kullman) esse "CBO" refere-se ao nível de otimização da consulta (significa "otimizador baseado em custo"). Por exemplo, se eu fizer find -O9001 --version , obtenho

Features enabled: D_TYPE O_NOFOLLOW(enabled) LEAF_OPTIMISATION FTS() CBO(level=9001) 

Olhando para a opção -O em man find , vejo

-Olevel
  Enables query optimisation.   The find program reorders tests to speed up execution  while  preserving  the  overall
  effect; that is, predicates with side effects are not reordered relative to each other.  The optimisations performed
  at each optimisation level are as follows.

  0      Equivalent to optimisation level 1.

  1      This is the default optimisation level  and  corresponds  to  the  traditional  behaviour.   Expressions  are
         reordered  so that tests based only on the names of files (for example -name and -regex) are performed first.

  2      Any -type or -xtype tests are performed after any tests based only on the names  of  files,  but  before  any
         tests  that  require information from the inode.  On many modern versions of Unix, file types are returned by
         readdir() and so these predicates are faster to evaluate than predicates which need to stat the file first.

  3      At this optimisation level, the full cost-based query optimiser is enabled.  The order of tests  is  modified
         so  that  cheap  (i.e. fast) tests are performed first and more expensive ones are performed later, if neces-
         sary.  Within each cost band, predicates are evaluated earlier or later according to whether they are  likely
         to  succeed or not.  For -o, predicates which are likely to succeed are evaluated earlier, and for -a, predi-
         cates which are likely to fail are evaluated earlier.

  The cost-based optimiser has a fixed idea of how likely any given test is to succeed.  In some cases the probability
  takes  account of the specific nature of the test (for example, -type f is assumed to be more likely to succeed than
  -type c).  The cost-based optimiser is currently being evaluated.   If it does not actually improve the  performance
  of find, it will be removed again.  Conversely, optimisations that prove to be reliable, robust and effective may be
  enabled at lower optimisation levels over time.  However, the default behaviour (i.e. optimisation level 1) will not
  be  changed  in  the 4.3.x release series.  The findutils test suite runs all the tests on find at each optimisation
  level and ensures that the result is the same.

Mistério resolvido! É um pouco estranho que a opção seja um valor de tempo de execução; normalmente eu esperaria que a saída --version refletisse apenas as opções de tempo de compilação.

    
por 17.02.2015 / 22:54
1

Informações sobre O_NOFOLLOW são fornecidas na página info de find :

9.2.1.1 O_NOFOLLOW

..................

If your system supports the O_NOFOLLOW flag (1) to the open(2)' system call,find' uses it when safely changing directory. The target directory is first opened and then find' changes working directory with thefchdir()' system call. This ensures that symbolic links are not followed, preventing the sort of race condition attack in which use is made of symbolic links.

...

Na árvore de origem, CBO ocorre apenas no arquivo parser.c :

 printf("CBO(level=%d) ", (int)(options.optimisation_level)); 

indicando que é uma otimização baseada em custo (meu melhor palpite).

D_TYPE ocorre em vários lugares na árvore de origem e parece que tem a ver com o tipo de entrada de diretório:

$ grep 'D_TYPE' */**

Rendimentos:

find/parser.c:#if defined USE_STRUCT_DIRENT_D_TYPE && defined HAVE_STRUCT_DIRENT_D_TYPE
lib/savedirinfo.c:#if defined HAVE_STRUCT_DIRENT_D_TYPE && defined USE_STRUCT_DIRENT_D_TYPE

e mais algumas entradas. Você pode encontrar a fonte aqui .

    
por 17.02.2015 / 22:59
0

Ao olhar através da árvore de fontes findutils ( link ), eu encontrei o seguinte:

  • configure.ac: --enable-d_type-optimization, use os dados do tipo de arquivo retornados em struct dirent.d_type por readdir ()),
  • m4 / withfts.m4: --without-fts Use um mecanismo antigo para pesquisar o sistema de arquivos, em vez de usar fts ()

Não encontrei nada sobre o CBO; você pode ter que baixar o código-fonte e procurar o termo ..

    
por 17.02.2015 / 22:39

Tags