Jump to content
  • libag: convertendo em biblioteca a ferramenta de busca em arquivos ag

       (1 review)

    Theldus
     Share

    Introdução

    Há poucas semanas, um amigo comentou que estava buscando automatizar um processo que envolvia buscas por expressões regulares em arquivos binários. Essa tarefa normalmente é realizada com ferramentas de linha de comando específicas (grep, git-grep, ack-grepagripgrepugrep, entre outras), e um script pode invocá-las e fazer o parsing do output. A ripgrep em particular oferece resultados em JSON, o que facilita bastante o processo.

    Apesar disso, chamar um processo externo e intepretar a saída não é a maneira ideal de incorporar uma funcionalidade em um programa, sendo a mais correta o uso de uma biblioteca, mas surpreendi-me ao perceber que não havia nenhuma que cumprisse tal propósito.

    E assim nasceu a libag, um fork da ferramenta ag com o objetivo de transformá-la em uma biblioteca para facilitar a incorporação, em outros programas, do recurso de busca avançada no conteúdo de arquivos.

    Uso e recursos

    A libag requer as mesmas dependências do ag: liblzma, libpcre e zlib.

    No Ubuntu (e possivelmente em outras distribuições Debian-like):

    $ sudo apt install libpcre3-dev zlib1g-dev liblzma-dev

    Uma vez resolvidas as dependências o processo de build é bastante simples.

    Basta clonar o repositório:

    $ git clone https://github.com/Theldus/libag
    $ cd libag/

    e compilar:

    Makefile

    $ make -j4
    $ make install # Opcional

    CMake

    $ mkdir build && cd build/
    $ cmake .. -DCMAKE_BUILD_TYPE=Release
    $ make -j4

    O uso da biblioteca é bastante simples e consiste no uso de três funções básicas: ag_init()ag_search() e ag_finish() (embora funções mais avançadas também estejam disponíveis).

    Um exemplo mínimo e completo segue abaixo:

    #include <libag.h>
    
    int main(void) {
        struct ag_result **results;
        size_t nresults;
    
        char *query    = "foo";
        char *paths[1] = {"."};
    
        /* Initiate Ag library with default options. */
        ag_init();
    
        /* Searches for foo in the current path. */
        results = ag_search(query, 1, paths, &nresults);
        if (!results) {
            printf("No result found\n");
            return (1);
        }
    
        printf("%zu results found\\n", nresults);
    
        /* Show them on the screen, if any. */
        for (size_t i = 0; i < nresults; i++) {
            for (size_t j = 0; j < results[i]->nmatches; j++) {
                printf("file: %s, match: %s\n",
                    results[i]->file, results[i]->matches[j]->match);
            }
        }
    
        /* Free all results. */
        ag_free_all_results(results, nresults);
    
        /* Release Ag resources. */
        ag_finish();
        return 0;
    }

    Uma vez que a libag possui bindings para Python e Node.js, seguem os mesmos exemplos abaixo:

    Python:

    from libag import *
    
    # Initiate Ag library with default options.
    ag_init()
    
    # Search.
    nresults, results = ag_search("foo", ["."])
    if nresults == 0:
        print("no result found")
    else:
        print("{} results found".format(nresults))
    
        # Show them on the screen, if any.
        for file in results:
            for match in file.matches:
                print("file: {}, match: {}, start: {} / end: {}".
                format(file.file, match.match, match.byte_start, match.byte_end))
    
    # Free all resources.
    if nresults:
        ag_free_all_results(results)
    
    # Release Ag resources.
    ag_finish()

    Node.js (sujeito a alterações):

    const libag = require('./build/Release/libag_wrapper');
    
    libag.ag_init();
    
    r = libag.ag_search("foo", ["."]);
    
    r.results.forEach((file, i) => {
        file.matches.forEach((match, j) => {
            console.log(
                "File: " + file.file + ", match: " + match.match +
                ", start: " + match.byte_start + " / end: " + match.byte_end
            );
        });
    });
    
    libag.ag_finish();

    Uso "avançado" e pesquisa em arquivos binários

    O uso básico é como ilustrado acima e representa também as opções padrões do ag. Entretanto, a libag permite um controle fino sobre as opções de busca e também sobre as worker threads.

    As opções podem ser tunadas a partir da estrutura struct ag_config, que contém uma série de inteiros que representam diretamente o recurso desejado. Opções como num_workers e search_binary_files definem a quantidade de worker threads e habilitam a busca em arquivos binários, respectivamente.

    Um exemplo mais interessante segue abaixo, vamos localizar arquivos ELF e PE32 que também contenham meu nome de usuário neles:

    from libag import *
    
    pattern       = "david";
    elf_signature = "^\x7f\x45\x4c\x46";
    pe_signature  = "^\x4d\x5a";
    signatures    = elf_signature + "|" + pe_signature;
    
    # Enable binary files search
    config = ag_config()
    config.search_binary_files = 1
    
    # Initiate Ag library with custom options.
    ag_init_config(config)
    
    # Search.
    nresults, results = ag_search(signatures, ["dir/"])
    if nresults == 0:
        print("no result found")
        sys.exit(1)
    
    print("{} pe+elf found".format(nresults))
    for file in results:
        print("file: {}".format(file.file))
    
    pe_elf = []
    
    # Add to our list
    for file in results:
        pe_elf.append(file.file);
    ag_free_all_results(results)
    
    # Search again looking for pattern
    nresults, results = ag_search(pattern, pe_elf)
    if nresults == 0:
        print("no result found")
        sys.exit(1)
    
    # Show them
    print("{} binaries found that matches {}".format(nresults, pattern))
    for file in results:
        for match in file.matches:
            print("file: {}, match: {}, start: {} / end: {}".
                format(file.file, match.match, match.byte_start, match.byte_end))
    
    # Free all resources.
    ag_free_all_results(results)
    
    # Release Ag resources.
    ag_finish()

    A pasta dir/ contém um arquivo ELF, um PE32+, um plaintext e uma imagem .png. Note que o range informado pode ser verificado com dd+hexdump, como segue abaixo:

    $ file dir/*
    dir/hello:      PE32+ executable (console) x86-64, for MS Windows
    dir/img.png:    PNG image data, 1247 x 711, 8-bit/color RGB, non-interlaced
    dir/libag.so:   ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, with debug_info, not stripped
    dir/random.txt: ASCII text
    
    $ ./elf_pe.py 
    2 pe+elf found
    file: dir/libag.so
    file: dir/hello
    1 binaries found that matches david
    file: dir/libag.so, match: david, start: 90094 / end: 90098
    
    $ dd if=dir/libag.so bs=1 skip=90094 count=5 | hexdump -C
    5+0 records in
    5+0 records out
    5 bytes copied, 2.1437e-05 s, 233 kB/s
    00000000  64 61 76 69 64                                    |david|
    00000005

    É claro que o exemplo acima é bastante simplório e serve apenas para ilustrar possíveis casos de uso da biblioteca.

    O processo de "libificação"

    A escolha do fork do ag foi bem natural: eu já tinha alguma familiaridade com o código fonte do ag e eu já havia brincado com ele alguns meses atrás. Além disso, o código do ag não é tão grande e eu sou um programador C em 99.9% do meu tempo, o que elimina alternativas como ripgrep (Rust) e ugrep (C++).

    O processo de "libificação" não foi tão complicado: primeiro eu extraí apenas o código fonte do projeto e escrevi meus próprios/novos scripts de build por cima (Makefile e CMake). Depois disso, foi investigar o processo de search original do ag e trazer isso para a minha biblioteca.

    De forma resumida, o ag original pode ser divido em três grandes etapas:

    1. Inicialização
      1. Configura o log_level (para propósitos de debug);
      2. Inicializa as estruturas de .gitignore (o ag é capaz de ignorar esse tipo de arquivo);
      3. Inicializa as opções default da linha de comando;
      4. Realiza o parsing das opções de linha de comando;
      5. Compila a regex via PCRE;
      6. Inicializa os mutexes e as worker threads.
    2. Busca
      1. O processo de busca e path traversal é realizado por uma única thread, que a partir da lista de paths recuperados via linha de comando invoca a rotina search_dir(), que para cada novo path encontrado o adiciona em uma "work_queue_t" e acorda todas as worker threads (se estiverem dormindo) para recuperar mais trabalhos.

        O processo de sincronização é feito via mutexes, mas em defesa do maintainer original do ag, um profiling no Intel VTune mostra que o tempo de hold de cada thread é mínímo, o que realmente torna o ag (e libag) escalável com o aumento da quantidade de cores.

    3. Resultados
      1. Uma vez que uma worker thread (WT) obtém um novo "job", ela então começa a leitura do arquivo: seja via mmap (padrão) ou todo o arquivo de uma só vez. Para buscas de texto literal, a "WT" utiliza os algoritmos de BoyerMoore e de hash para identificação da string. Em caso de expressão regular, utiliza-se a biblioteca PCRE. A decisão dos algoritmos é feita automaticamente, para maior desempenho.

        À medida que novos resultados são encontrados (para um único arquivo), eles são adicionados em uma lista de matches, definida pelo tipo match_t e ao finalizar a leitura do arquivo os resultados encontrados são impressos na tela, protegidos por um mutex.

    Salvando os resultados

    Uma vez obtidos os resultados, entra então a maior "incisão" da libag: interferir no processo de dump dos resultados e salvá-los de forma estruturada e facilmente recuperável posteriormente.

    Para isso, foi introduzido um vetor de resultados (dinâmico) por WT, que armazena os dados obtidos até o momento. Além disso, a rotina principal das worker threads (search_file_worker()) foi levemente modificada para notificar do término das threads e também permitir facilmente manipular o "start/stop" delas sob demanda.

    Uma vez que toda a work queue foi preenchida e processada, a rotina de search (da biblioteca) pode resumir sua execução, fazendo o join dos resultados parciais das threads e retornando um "struct ag_search**", que contém uma lista de resultados por arquivo, a string do match, flags e byte de início e fim da ocorrência, algo como:

    /**
     * Structure that holds a single result, i.e: a file
     * that may contains multiples matches.
     */
    struct ag_result
    {
        char *file;
        size_t nmatches;
        struct ag_match
        {
            size_t byte_start;
            size_t byte_end;
            char *match;
        } **matches;
        int flags;
    };

    Bindings

    Para facilitar a utilização da libag, o projeto também possui bindings experimentais para Python 2/3 e também Node.js (em desenvolvimento). 

    Python

    Os bindings para Python foram escritos utilizando o SWIG: um programa que, dado um arquivo de interface, é capaz de gerar um "glue-code" que, quando compilado em conjunto com o código original, funciona como um wrapper/binding para a linguagem em questão.

    O SWIG gera código compilável para CPython e os tipos não-primitivos (como as duas estruturas introduzidas pela biblioteca) são mapeados via "type-maps".

    Node.js

    Embora o SWIG suporte Node.js, ele parece utilizar diretamente a API da v8 engine, que está sempre em constante mudanças, e portanto, o código gerado não compila na última versão estável (v14.17.1 LTS) do Node.

    Para contornar isso, os bindings para Node.js foram escritos em cima da Node-API, uma API em C (também disponível em C++, com nome de node-addon-api) que oferece um conjunto mínimo de recursos em cima da v8 e que têm como objetivo manter a estabilidade de addons escritos mesmo entre versões distintas do Node e v8.

    Limitações

    Ao contrário de programas construídos em cima de uma biblioteca, como o cURL+ libcurl, ag (aparentemente) nunca foi idealizado como tal e portanto o código fonte impõe certas restrições ao adaptá-lo para uma biblioteca, das quais vale destacar:

    • Apenas uma única configuração "global": não é possível (no momento) utilizar opções distintas de search para múltiplos searchs; Uma alternativa a isso é manter múltiplos "ag_config" e setá-los com ag_set_config() antes de cada busca. Esta limitação se deve ao ag utilizar uma única estrutura global para armazenar os parâmetros de linha de comando, estrutura essa utilizada em diversos pontos em todo o código fonte.
    • Uma busca de cada vez: assim como no item anterior, o ag também usa diversas estruturas globais para manter o estado da busca durante um ag_search(), o que impossibilita de utilizar múltiplos searchs simultaneamente. Uma solução temporária foi adicionada com o uso da função ag_search_ts(), que internamente utiliza locks para serializar todas as chamadas a ag_search().

    Dentre outros. Qualquer contribuição em pontos como esses e outros é muito bem vinda =).

    Conclusão

    Por fim, convido todos a conhecerem a página da libag no GitHub. Trata-se de um projeto de código aberto e, portanto, está aberto a contribuições. Espero que ele possa ser tão útil para mais pessoas quanto está sendo para os que já o utilizam!

    ~ Theldus signing off!


    Revisão: Leandro Fróes
    • Agradecer 1
    • Curtir 1
     Share


    User Feedback

    Join the conversation

    You can post now and register later. If you have an account, sign in now to post with your account.
    Note: Your post will require moderator approval before it will be visible.

    Guest

    • This will not be shown to other users.
    • Add a review...

      ×   Pasted as rich text.   Restore formatting

        Only 75 emoji are allowed.

      ×   Your link has been automatically embedded.   Display as a link instead

      ×   Your previous content has been restored.   Clear editor

      ×   You cannot paste images directly. Upload or insert images from URL.


    anderson_leite

       3 of 3 members found this review helpful 3 / 3 members

    Parabéns pelo projeto!

    Excelente contribuição, sempre achei que o AG já tinha uma lib junto com ele.

    Response from the author:

    Oi Anderson, muito obrigado. Pois é, facilitaria bastante a minha vida (e a de outras pessoas) se ele tivesse sido feito dessa forma, ainda tenho bastante coisa a ser feita na libag. Curioso que não encontrei nenhum projeto similar, e todos outros 'concorrentes' diretos do ag, como rg, ugrep dentre outros, aparentemente também não criam essa separação. O ripgrep em especial até possui uma nota sobre isso (em crates/core/README.md):

    ... Currently, there are no plans to make ripgrep core available as an independent library. However, much of the heavy lifting of ripgrep is done via its constituent crates, which can be reused independent of ripgrep. Unfortunately, there is no guide or tutorial to teach folks how to do this yet. ...

     

    • Curtir 3
    Link to review
    Share on other sites


  • Similar Content

×
×
  • Create New...