¿Qué significan las "características habilitadas" en GNU encontrar?

Cuando uso find --versioncon GNU find, obtengo algo como esto:

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

¿Qué significan estas "características"? Hay alguna referencia a O_NOFOLLOWser una medida de seguridad man find, y hay una mención de LEAF_OPTIMISATIONser una optimización que ahorra algunas lstatllamadas en los nodos hoja. Pero no puedo encontrar nada sobre FTS, D_TYPEo CBO.

Esta es una respuesta completa derivada de las respuestas de Ketan y Daniel Kullman, así como de mi propia investigación.

La mayoría de las "características" resultan ser optimizaciones de consultas, ya findque en general es capaz de consultas (casi) arbitrariamente complejas en el sistema de archivos.

D_TYPE

La presencia de la D_TYPEfunción significa que findse compiló con soporte para el d_typecampo en struct dirent. Este campo es una extensión BSD también adoptada por Linux, que proporciona el tipo de archivo (directorio, archivo, tubería, socket, dispositivo char / block, etc.) en la estructura devuelta por readdiry amigos. Como optimización, findpuede usar esto para reducir o eliminar lstatllamadas cuando -typese usa como una expresión de filtro.

readdires posible que no siempre se llene d_typeen algunos sistemas de archivos, por lo que a veces lstataún será necesario.

Más información de la documentación oficial: https://www.gnu.org/software/findutils/manual/html_node/find_html/d_005ftype-Optimisation.html

O_NOFOLLOW

Esta opción leerá (enabled)o (disabled). Si está presente y habilitada, esta característica implementa una medida de seguridad que protege findcontra ciertos ataques de carrera TOCTTOU. Específicamente, evita findatravesar un enlace simbólico mientras se realiza el recorrido del directorio, lo que podría ocurrir si el directorio fuera reemplazado por un enlace simbólico después de verificar el tipo de archivo del directorio pero antes de ingresar el directorio.

Con esta opción habilitada, findse usará open(..., O_NOFOLLOW)en el directorio para abrir solo directorios reales, luego se usará openatpara abrir archivos dentro de ese directorio.

HOJA_OPTIMIZACIÓN

Esta optimización ligeramente oscura permite finddeducir qué subdirectorios de un directorio padre son directorios mediante el uso del recuento de enlaces del directorio padre, ya que los subdirectorios contribuirán al recuento de enlaces del padre (a través del ..enlace). En ciertas circunstancias, permitirá findeludir una statllamada. Sin embargo, si el sistema de archivos o el sistema operativo tergiversan st_nlinks, puede findproducir resultados falsos (afortunadamente, esto es muy raro).

Más información en la documentación oficial: https://www.gnu.org/software/findutils/manual/html_node/find_html/Leaf-Optimisation.html

FTS

Cuando está habilitada, la FTScaracterística hace findque use la ftsAPI para atravesar la jerarquía de archivos, en lugar de una implementación recursiva directa.

No tengo claro cuál es la ventaja fts, pero FTSes básicamente el valor predeterminado en todas las findversiones predeterminadas que he visto hasta ahora.

Más información: https://www.gnu.org/software/findutils/manual/html_node/find_html/fts.html , http://man7.org/linux/man-pages/man3/fts.3.html

CBO

Resulta (después de leer el findcódigo fuente según lo sugerido por daniel kullman) que "CBO" se refiere al nivel de optimización de la consulta (significa "optimizador basado en costos"). Por ejemplo, si lo hago find -O9001 --version, me sale

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

Mirando la -Oopción en man find, veo

-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.

¡Misterio resuelto! Es un poco extraño que la opción sea un valor de tiempo de ejecución; por lo general, esperaría que la --versionsalida solo refleje las opciones de tiempo de compilación.

La información sobre O_NOFOLLOWse proporciona en la infopágina de find:

9.2.1.1 O_NOFOLLOW

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

Si su sistema es compatible con el indicador O_NOFOLLOW (1) para la open(2)' system call,búsqueda, lo utiliza cuando cambia de directorio de forma segura. El directorio de destino se abre primero y luego se find' changes working directory with thellama al sistema fchdir (). Esto garantiza que no se sigan los enlaces simbólicos, evitando el tipo de ataque de condición de carrera en el que se utilizan enlaces simbólicos.

...

Desde el árbol fuente, CBOocurre solo en el archivo parser.c:

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

indicando que es una optimización basada en el costo (mi mejor suposición).

D_TYPE ocurre en varios lugares en el árbol de origen y parece que tiene que ver con el tipo de entrada de directorio:

$ grep 'D_TYPE' */**

Rendimientos:

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

Y algunas entradas más. Puedes encontrar la fuente aquí .

Al mirar a través del árbol fuente findutils ( http://git.savannah.gnu.org/cgit/findutils.git/tree/ ), encontré lo siguiente:

• configure.ac: --enable-d_type-optimization, haga uso de los datos del tipo de archivo devueltos en struct dirent.d_type por readdir ()),
• m4 / withfts.m4: --without-fts Use un mecanismo anterior para buscar en el sistema de archivos, en lugar de usar fts ()

No encontré nada sobre CBO; es posible que deba descargar el código fuente y buscar el término.