X-Git-Url: https://git.sesse.net/?p=plocate;a=blobdiff_plain;f=plocate-build.cpp;h=028a1ee06c620d8274ae707ba1905041ac288a17;hp=8e004e7bd248b724936c806a24aeb61970718d60;hb=HEAD;hpb=12cf48afe678b047fec19b76e14a3e8b29bb33f6 diff --git a/plocate-build.cpp b/plocate-build.cpp index 8e004e7..227eae5 100644 --- a/plocate-build.cpp +++ b/plocate-build.cpp @@ -1,53 +1,39 @@ +#include "database-builder.h" +#include "db.h" +#include "dprintf.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include #include +#include #include -#include -#include #include -#include -#include -#include -#include -#include -#include -#include -#include #include - -#include "vp4.h" - -#define P4NENC_BOUND(n) ((n+127)/128+(n+32)*sizeof(uint32_t)) -#define dprintf(...) -//#define dprintf(...) fprintf(stderr, __VA_ARGS__); +#include +#include using namespace std; using namespace std::chrono; - -static inline uint32_t read_unigram(const string &s, size_t idx) -{ - if (idx < s.size()) { - return (unsigned char)s[idx]; - } else { - return 0; - } -} -static inline uint32_t read_trigram(const string &s, size_t start) -{ - return read_unigram(s, start) | - (read_unigram(s, start + 1) << 8) | - (read_unigram(s, start + 2) << 16); -} +bool use_debug = false; -enum -{ - DBE_NORMAL = 0, /* A non-directory file */ - DBE_DIRECTORY = 1, /* A directory */ - DBE_END = 2 /* End of directory contents; contains no name */ +enum { + DBE_NORMAL = 0, /* A non-directory file */ + DBE_DIRECTORY = 1, /* A directory */ + DBE_END = 2 /* End of directory contents; contains no name */ }; // From mlocate. -struct db_header -{ +struct db_header { uint8_t magic[8]; uint32_t conf_size; uint8_t version; @@ -56,190 +42,237 @@ struct db_header }; // From mlocate. -struct db_directory -{ +struct db_directory { uint64_t time_sec; uint32_t time_nsec; uint8_t pad[4]; }; -const char *handle_directory(const char *ptr, vector *files) +string read_cstr(FILE *fp) { - ptr += sizeof(db_directory); + string ret; + for (;;) { + int ch = getc(fp); + if (ch == -1) { + perror("getc"); + exit(1); + } + if (ch == 0) { + return ret; + } + ret.push_back(ch); + } +} + +void handle_directory(FILE *fp, DatabaseReceiver *receiver) +{ + db_directory dummy; + if (fread(&dummy, sizeof(dummy), 1, fp) != 1) { + if (feof(fp)) { + return; + } else { + perror("fread"); + } + } - string dir_path = ptr; - ptr += dir_path.size() + 1; + string dir_path = read_cstr(fp); if (dir_path == "/") { dir_path = ""; } - - for ( ;; ) { - uint8_t type = *ptr++; + + for (;;) { + int type = getc(fp); if (type == DBE_NORMAL) { - string filename = ptr; - files->push_back(dir_path + "/" + filename); - ptr += filename.size() + 1; + string filename = read_cstr(fp); + receiver->add_file(dir_path + "/" + filename, unknown_dir_time); } else if (type == DBE_DIRECTORY) { - string dirname = ptr; - files->push_back(dir_path + "/" + dirname); - ptr += dirname.size() + 1; + string dirname = read_cstr(fp); + receiver->add_file(dir_path + "/" + dirname, unknown_dir_time); } else { - return ptr; + return; // Probably end. } } } -void read_mlocate(const char *filename, vector *files) +void read_plaintext(FILE *fp, DatabaseReceiver *receiver) { - int fd = open(filename, O_RDONLY); - if (fd == -1) { - perror(filename); + if (fseek(fp, 0, SEEK_SET) != 0) { + perror("fseek"); exit(1); } - off_t len = lseek(fd, 0, SEEK_END); - if (len == -1) { - perror("lseek"); - exit(1); + + while (!feof(fp)) { + char buf[1024]; + if (fgets(buf, sizeof(buf), fp) == nullptr) { + break; + } + string s(buf); + assert(!s.empty()); + while (s.back() != '\n' && !feof(fp)) { + // The string was longer than the buffer, so read again. + if (fgets(buf, sizeof(buf), fp) == nullptr) { + break; + } + s += buf; + } + if (!s.empty() && s.back() == '\n') + s.pop_back(); + receiver->add_file(move(s), unknown_dir_time); } - const char *data = (char *)mmap(nullptr, len, PROT_READ, MAP_SHARED, fd, /*offset=*/0); - if (data == MAP_FAILED) { - perror("mmap"); +} + +void read_mlocate(FILE *fp, DatabaseReceiver *receiver) +{ + if (fseek(fp, 0, SEEK_SET) != 0) { + perror("fseek"); exit(1); } - const db_header *hdr = (const db_header *)data; + db_header hdr; + if (fread(&hdr, sizeof(hdr), 1, fp) != 1) { + perror("short read"); + exit(1); + } // TODO: Care about the base path. - string path = data + sizeof(db_header); - uint64_t offset = sizeof(db_header) + path.size() + 1 + ntohl(hdr->conf_size); + string path = read_cstr(fp); - const char *ptr = data + offset; - while (ptr < data + len) { - ptr = handle_directory(ptr, files); + if (fseek(fp, ntohl(hdr.conf_size), SEEK_CUR) != 0) { + perror("skip conf block"); + exit(1); } - munmap((void *)data, len); - close(fd); + while (!feof(fp)) { + handle_directory(fp, receiver); + } } -void do_build(const char *infile, const char *outfile) +void do_build(const char *infile, const char *outfile, int block_size, bool plaintext, bool check_visibility) { - //steady_clock::time_point start = steady_clock::now(); - - vector files; - read_mlocate(infile, &files); - if (false) { // To read a plain text file. - FILE *fp = fopen(infile, "r"); - while (!feof(fp)) { - char buf[1024]; - if (fgets(buf, 1024, fp) == nullptr || feof(fp)) { - break; - } - string s(buf); - if (s.back() == '\n') s.pop_back(); - files.push_back(move(s)); - } - fclose(fp); - } - dprintf("Read %zu files from %s\n", files.size(), infile); - - unordered_map pl; - size_t trigrams = 0, longest_posting_list = 0; - unordered_map> invindex; - for (size_t i = 0; i < files.size(); ++i) { - const string &s = files[i]; - if (s.size() >= 3) { - for (size_t j = 0; j < s.size() - 2; ++j) { - uint32_t trgm = read_trigram(s, j); - invindex[trgm].push_back(i); - } - } + FILE *infp = fopen(infile, "rb"); + if (infp == nullptr) { + perror(infile); + exit(1); } - string buf; - size_t bytes_used = 0; - for (auto &[trigram, docids] : invindex) { - auto last = unique(docids.begin(), docids.end()); - docids.erase(last, docids.end()); - longest_posting_list = max(longest_posting_list, docids.size()); - trigrams += docids.size(); - size_t bytes_needed = P4NENC_BOUND(docids.size()); - if (buf.size() < bytes_needed) buf.resize(bytes_needed); - size_t bytes = p4nd1enc128v32(&docids[0], docids.size(), reinterpret_cast(&buf[0])); - pl[trigram] = string(buf.data(), bytes); - bytes_used += bytes; + // Train the dictionary by sampling real blocks. + // The documentation for ZDICT_trainFromBuffer() claims that a reasonable + // dictionary size is ~100 kB, but 1 kB seems to actually compress better for us, + // and decompress just as fast. + DictionaryBuilder builder(/*blocks_to_keep=*/1000, block_size); + if (plaintext) { + read_plaintext(infp, &builder); + } else { + read_mlocate(infp, &builder); } - dprintf("%zu files, %zu different trigrams, %zu entries, avg len %.2f, longest %zu\n", - files.size(), invindex.size(), trigrams, double(trigrams) / invindex.size(), longest_posting_list); + string dictionary = builder.train(1024); - dprintf("%zu bytes used for posting lists (%.2f bits/entry)\n", bytes_used, 8 * bytes_used / double(trigrams)); - //steady_clock::time_point end = steady_clock::now(); - dprintf("Building posting lists took %.1f ms.\n\n", 1e3 * duration(end - start).count()); - - vector all_trigrams; - for (auto &[trigram, docids] : invindex) { - all_trigrams.push_back(trigram); + DatabaseBuilder db(outfile, /*owner=*/-1, block_size, dictionary, check_visibility); + DatabaseReceiver *corpus = db.start_corpus(/*store_dir_times=*/false); + if (plaintext) { + read_plaintext(infp, corpus); + } else { + read_mlocate(infp, corpus); } - sort(all_trigrams.begin(), all_trigrams.end()); + fclose(infp); - umask(0027); - FILE *outfp = fopen(outfile, "wb"); + dprintf("Read %zu files from %s\n", corpus->num_files_seen(), infile); + db.finish_corpus(); +} - // Write the header. - uint64_t num_trigrams = invindex.size(); // 64 to get alignment. - fwrite(&num_trigrams, sizeof(num_trigrams), 1, outfp); +void usage() +{ + printf( + "Usage: plocate-build MLOCATE_DB PLOCATE_DB\n" + "\n" + "Generate plocate index from mlocate.db, typically /var/lib/mlocate/mlocate.db.\n" + "Normally, the destination should be /var/lib/mlocate/plocate.db.\n" + "\n" + " -b, --block-size SIZE number of filenames to store in each block (default 32)\n" + " -p, --plaintext input is a plaintext file, not an mlocate database\n" + " -l, --require-visibility FLAG check visibility before reporting files\n" + " --help print this help\n" + " --version print version information\n"); +} - // Find out where the posting lists will end. - uint64_t offset = sizeof(uint64_t) * 2 + 16 * all_trigrams.size(); - uint64_t filename_index_offset = offset; - for (uint32_t trgm : all_trigrams) { - filename_index_offset += pl[trgm].size(); +void version() +{ + printf("plocate-build %s\n", PACKAGE_VERSION); + printf("Copyright 2020 Steinar H. Gunderson\n"); + printf("License GPLv2+: GNU GPL version 2 or later .\n"); + printf("This is free software: you are free to change and redistribute it.\n"); + printf("There is NO WARRANTY, to the extent permitted by law.\n"); +} + +bool parse_bool(const string &str, bool *result) +{ + if (str == "0" || str == "no") { + *result = false; + return true; } - fwrite(&filename_index_offset, sizeof(filename_index_offset), 1, outfp); + if (str == "1" || str == "yes") { + *result = true; + return true; + } + return false; +} - size_t bytes_for_trigrams = 0, bytes_for_posting_lists = 0, bytes_for_filename_index = 0, bytes_for_filenames = 0; +int main(int argc, char **argv) +{ + static const struct option long_options[] = { + { "block-size", required_argument, 0, 'b' }, + { "plaintext", no_argument, 0, 'p' }, + { "require-visibility", required_argument, 0, 'l' }, + { "help", no_argument, 0, 'h' }, + { "version", no_argument, 0, 'V' }, + { "debug", no_argument, 0, 'D' }, // Not documented. + { 0, 0, 0, 0 } + }; - for (uint32_t trgm : all_trigrams) { - // 16 bytes: trgm (4), number of docids (4), byte offset (8) - fwrite(&trgm, sizeof(trgm), 1, outfp); // One byte wasted, but OK. - uint32_t num_docids = invindex[trgm].size(); - fwrite(&num_docids, sizeof(num_docids), 1, outfp); - fwrite(&offset, sizeof(offset), 1, outfp); - offset += pl[trgm].size(); - bytes_for_trigrams += 16; - } + int block_size = 32; + bool plaintext = false; + bool check_visibility = true; - // Write the actual posting lists. - for (uint32_t trgm : all_trigrams) { - fwrite(pl[trgm].data(), pl[trgm].size(), 1, outfp); - bytes_for_posting_lists += pl[trgm].size(); + setlocale(LC_ALL, ""); + for (;;) { + int option_index = 0; + int c = getopt_long(argc, argv, "b:hpl:VD", long_options, &option_index); + if (c == -1) { + break; + } + switch (c) { + case 'b': + block_size = atoi(optarg); + break; + case 'p': + plaintext = true; + break; + case 'l': + if (!parse_bool(optarg, &check_visibility) != 0) { + fprintf(stderr, "plocate-build: invalid value `%s' for --%s\n", + optarg, "require-visibility"); + exit(EXIT_FAILURE); + } + break; + case 'h': + usage(); + exit(0); + case 'V': + version(); + exit(0); + case 'D': + use_debug = true; + break; + default: + exit(1); + } } - // Write the offsets to the filenames. - offset = filename_index_offset + files.size() * sizeof(offset); - for (const string &filename : files) { - fwrite(&offset, sizeof(offset), 1, outfp); - offset += filename.size() + 1; - bytes_for_filename_index += sizeof(offset); - bytes_for_filenames += filename.size() + 1; - } - - // Write the actual filenames. - for (const string &filename : files) { - fwrite(filename.c_str(), filename.size() + 1, 1, outfp); + if (argc - optind != 2) { + usage(); + exit(1); } - fclose(outfp); - - dprintf("Trigrams: %'7.1f MB\n", bytes_for_trigrams / 1048576.0); - dprintf("Posting lists: %'7.1f MB\n", bytes_for_posting_lists / 1048576.0); - dprintf("Filename index: %'7.1f MB\n", bytes_for_filename_index / 1048576.0); - dprintf("Filenames: %'7.1f MB\n", bytes_for_filenames / 1048576.0); - dprintf("\n"); -} - -int main(int argc, char **argv) -{ - do_build(argv[1], argv[2]); + do_build(argv[optind], argv[optind + 1], block_size, plaintext, check_visibility); exit(EXIT_SUCCESS); }