xapian-core/backends/honey/honey_table.h

   1 /** @file honey_table.h
   2  * @brief HoneyTable class
   3  */
   4 /* Copyright (C) 2017,2018 Olly Betts
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
  19  */
  20
  21 #ifndef XAPIAN_INCLUDED_HONEY_TABLE_H
  22 #define XAPIAN_INCLUDED_HONEY_TABLE_H
  23
  24 //#define SSINDEX_ARRAY
  25 //#define SSINDEX_BINARY_CHOP
  26 #define SSINDEX_SKIPLIST
  27
  28 #define SSINDEX_BINARY_CHOP_KEY_SIZE 4
  29
  30 //#include "xapian/constants.h"
  31 #include "xapian/error.h"
  32
  33 #include <algorithm>
  34 #if 0
  35 #include <iostream> // FIXME
  36 #endif
  37
  38 #include <cstdio> // For EOF
  39 #include <cstdlib> // std::abort()
  40 #include <type_traits>
  41 #ifdef HAVE_SYS_UIO_H
  42 # include <sys/uio.h>
  43 #endif
  44
  45 #include <sys/types.h>
  46 #include "safesysstat.h"
  47 #include "safeunistd.h"
  48
  49 #include "safeerrno.h"
  50
  51 #include "compression_stream.h"
  52 #include "honey_defs.h"
  53 #include "honey_version.h"
  54 #include "internaltypes.h"
  55 #include "io_utils.h"
  56 #include "pack.h"
  57 #include "str.h"
  58 #include "stringutils.h"
  59 #include "wordaccess.h"
  60
  61 #include "unicode/description_append.h"
  62
  63 #ifdef BLK_UNUSED
  64 # undef BLK_UNUSED
  65 #endif // FIXME: namespace it?
  66
  67 const uint4 BLK_UNUSED = uint4(-1);
  68
  69 class HoneyFreeListChecker;
  70
  71 const int FORCED_CLOSE = -2;
  72
  73 class BufferedFile {
  74     int fd = -1;
  75     mutable off_t pos = 0;
  76     bool read_only = true;
  77     mutable size_t buf_end = 0;
  78     mutable char buf[4096];
  79
  80   public:
  81     BufferedFile() { }
  82
  83     BufferedFile(const BufferedFile& o) : fd(o.fd) {
  84         if (!o.read_only) std::abort();
  85 #if 0
  86         if (o.buf_end) {
  87             buf_end = o.buf_end;
  88             std::memcpy(buf, o.buf, buf_end);
  89         }
  90 #endif
  91     }
  92
  93     BufferedFile(int fd_, off_t pos_, bool read_only_)
  94         : fd(fd_), pos(pos_), read_only(read_only_) {}
  95
  96     ~BufferedFile() {
  97 //      if (fd >= 0) ::close(fd);
  98     }
  99
 100     void close() {
 101         if (fd >= 0) {
 102             ::close(fd);
 103             fd = -1;
 104         }
 105     }
 106
 107     void force_close() {
 108         close();
 109         fd = FORCED_CLOSE;
 110     }
 111
 112     void reset_fd(bool permanent) {
 113         fd = permanent ? FORCED_CLOSE : -1;
 114     }
 115
 116     bool is_open() const { return fd >= 0; }
 117
 118     bool was_forced_closed() const { return fd == FORCED_CLOSE; }
 119
 120     bool open(const std::string& path, bool read_only_) {
 121 //      if (fd >= 0) ::close(fd);
 122         read_only = read_only_;
 123         if (read_only) {
 124             // FIXME: add new io_open_stream_rd() etc?
 125             fd = io_open_block_rd(path);
 126         } else {
 127             // FIXME: Always create anew for now...
 128             fd = io_open_block_wr(path, true);
 129         }
 130         return fd >= 0;
 131     }
 132
 133     off_t get_pos() const {
 134         return read_only ? pos - buf_end : pos + buf_end;
 135     }
 136
 137     void set_pos(off_t pos_) {
 138         if (!read_only) flush();
 139         if (false && pos_ >= pos) { // FIXME: need to take buf_end into account
 140             skip(pos_ - pos);
 141         } else {
 142             // FIXME: salvage some of the buffer if we can?
 143             buf_end = 0;
 144             pos = pos_;
 145         }
 146     }
 147
 148     void skip(size_t delta) const {
 149         if (!read_only) std::abort();
 150         // Keep any buffered data we can.
 151         if (delta > buf_end) {
 152             pos -= buf_end;
 153             pos += delta;
 154             buf_end = 0;
 155         } else {
 156             buf_end -= delta;
 157         }
 158     }
 159
 160 #if 0
 161     bool empty() const {
 162         if (buf_end) return false;
 163         struct stat sbuf;
 164         if (fd == -1 || fstat(fd, &sbuf) < 0) return true;
 165         return (sbuf.st_size == 0);
 166     }
 167 #endif
 168
 169     void write(unsigned char ch) {
 170         if (buf_end == sizeof(buf)) {
 171             // writev()?
 172             io_write(fd, buf, buf_end);
 173             pos += buf_end;
 174             buf_end = 0;
 175         }
 176         buf[buf_end++] = ch;
 177     }
 178
 179     void write(const char* p, size_t len) {
 180         if (buf_end + len <= sizeof(buf)) {
 181             memcpy(buf + buf_end, p, len);
 182             buf_end += len;
 183             return;
 184         }
 185
 186         pos += buf_end + len;
 187 #ifdef HAVE_WRITEV
 188         while (true) {
 189             struct iovec iov[2];
 190             iov[0].iov_base = buf;
 191             iov[0].iov_len = buf_end;
 192             iov[1].iov_base = const_cast<char*>(p);
 193             iov[1].iov_len = len;
 194             ssize_t n_ = writev(fd, iov, 2);
 195             if (n_ < 0) std::abort();
 196             size_t n = n_;
 197             if (n == buf_end + len) {
 198                 // Wrote everything.
 199                 buf_end = 0;
 200                 return;
 201             }
 202             if (n >= buf_end) {
 203                 // Wrote all of buf.
 204                 n -= buf_end;
 205                 p += n;
 206                 len -= n;
 207                 io_write(fd, p, len);
 208                 buf_end = 0;
 209                 return;
 210             }
 211             buf_end -= n;
 212             memmove(buf, buf + n, buf_end);
 213         }
 214 #else
 215         io_write(fd, buf, buf_end);
 216         if (len >= sizeof(buf)) {
 217             // If it's bigger than our buffer, just write it directly.
 218             io_write(fd, p, len);
 219             buf_end = 0;
 220             return;
 221         }
 222         memcpy(buf, p, len);
 223         buf_end = len;
 224 #endif
 225     }
 226
 227     int read() const {
 228 #if 1
 229         if (buf_end == 0) {
 230             // The buffer is currently empty, so we need to read at least one
 231             // byte.
 232             size_t r = io_pread(fd, buf, sizeof(buf), pos, 0);
 233             if (r < sizeof(buf)) {
 234                 if (r == 0) {
 235                     return EOF;
 236                 }
 237                 memmove(buf + sizeof(buf) - r, buf, r);
 238             }
 239             pos += r;
 240             buf_end = r;
 241         }
 242         return static_cast<unsigned char>(buf[sizeof(buf) - buf_end--]);
 243 #else
 244         unsigned char ch;
 245         if (io_pread(fd, &ch, 1, pos) != 1)
 246             return EOF;
 247         ++pos;
 248         return ch;
 249 #endif
 250     }
 251
 252     void read(char* p, size_t len) const {
 253 #if 1
 254         if (buf_end != 0) {
 255             if (len <= buf_end) {
 256                 memcpy(p, buf + sizeof(buf) - buf_end, len);
 257                 buf_end -= len;
 258                 return;
 259             }
 260             memcpy(p, buf + sizeof(buf) - buf_end, buf_end);
 261             p += buf_end;
 262             len -= buf_end;
 263             buf_end = 0;
 264         }
 265         // FIXME: refill buffer if len < sizeof(buf)
 266 #endif
 267         size_t r = io_pread(fd, p, len, pos, len);
 268         // io_pread() should throw an exception if it read < len bytes.
 269         AssertEq(r, len);
 270         pos += r;
 271     }
 272
 273     void flush() {
 274         if (!read_only && buf_end) {
 275             io_write(fd, buf, buf_end);
 276             pos += buf_end;
 277             buf_end = 0;
 278         }
 279     }
 280
 281     void sync() {
 282         io_sync(fd);
 283     }
 284
 285     void rewind(off_t start) {
 286         read_only = true;
 287         pos = start;
 288         buf_end = 0;
 289     }
 290 };
 291
 292 class HoneyCursor;
 293
 294 class SSIndex {
 295     std::string data;
 296 #if defined SSINDEX_BINARY_CHOP
 297     size_t block = size_t(-1);
 298 #elif defined SSINDEX_SKIPLIST
 299     size_t block = 0;
 300 #endif
 301 #if defined SSINDEX_BINARY_CHOP || defined SSINDEX_SKIPLIST
 302     std::string last_index_key;
 303 #endif
 304     // Put an index entry every this much:
 305     // FIXME: tune - seems 64K is common elsewhere
 306     enum { INDEXBLOCK = 4096 };
 307     SSIndex* parent_index = NULL;
 308
 309 #ifdef SSINDEX_ARRAY
 310     unsigned char first, last = static_cast<unsigned char>(-1);
 311     off_t* pointers = NULL;
 312 #endif
 313
 314   public:
 315     SSIndex() {
 316 #ifdef SSINDEX_ARRAY
 317         // Header added in write() method.
 318 #elif defined SSINDEX_BINARY_CHOP
 319         data.assign(5, '\x01');
 320 #elif defined SSINDEX_SKIPLIST
 321         data.assign(1, '\x02');
 322 #else
 323 # error "SSINDEX type not specified"
 324 #endif
 325     }
 326
 327     ~SSIndex() {
 328 #ifdef SSINDEX_ARRAY
 329         delete [] pointers;
 330 #endif
 331     }
 332
 333     void maybe_add_entry(const std::string& key, off_t ptr) {
 334 #ifdef SSINDEX_ARRAY
 335         unsigned char initial = key[0];
 336         if (!pointers) {
 337             pointers = new off_t[256]();
 338             first = initial;
 339         }
 340         // We should only be called for valid index points.
 341         AssertRel(int(initial), !=, last);
 342
 343         while (++last != int(initial)) {
 344             pointers[last] = ptr;
 345             // FIXME: Perhaps record this differently so that an exact key
 346             // search can return false?
 347         }
 348         pointers[initial] = ptr;
 349         last = initial;
 350 #elif defined SSINDEX_BINARY_CHOP
 351         // We store entries truncated to a maximum width (and trailing zeros
 352         // are used to indicate keys shorter than that max width).  These then
 353         // point to the first key that maps to this truncated value.
 354         //
 355         // We need constant width entries to allow binary chop to work, but
 356         // there are other ways to achieve this which could be explored.  We
 357         // could allow the full key width of 256 bytes, but that would take a
 358         // lot more space.  We could store a pointer (offset) to the key data,
 359         // but that's more complex to read, and adds the pointer overhead.  We
 360         // could use a "SKO" - a fixed width entry which encodes variable
 361         // length pointer and key with short keys in the entry and long keys
 362         // pointed to (or prefix included and rest pointed to).
 363         if (last_index_key.size() == SSINDEX_BINARY_CHOP_KEY_SIZE) {
 364             if (startswith(key, last_index_key)) {
 365                 return;
 366             }
 367         }
 368
 369         // Ensure the truncated key doesn't end in a zero byte.
 370         if (key.size() >= SSINDEX_BINARY_CHOP_KEY_SIZE) {
 371             // FIXME: Start from char N if we have N array index levels above.
 372             last_index_key.assign(key, 0, SSINDEX_BINARY_CHOP_KEY_SIZE);
 373             if (key[SSINDEX_BINARY_CHOP_KEY_SIZE - 1] == '\0')
 374                 return;
 375         } else {
 376             last_index_key = key;
 377             if (key.back() == '\0')
 378                 return;
 379             // Pad with zero bytes.
 380             last_index_key.resize(SSINDEX_BINARY_CHOP_KEY_SIZE);
 381         }
 382
 383         // Thin entries to at most one per INDEXBLOCK sized block.
 384         size_t cur_block = ptr / INDEXBLOCK;
 385         if (cur_block == block)
 386             return;
 387
 388 #if 0
 389         {
 390             std::string esc;
 391             description_append(esc, last_index_key);
 392             std::cout << "Adding «" << esc << "» -> file offset " << ptr << std::endl;
 393         }
 394 #endif
 395         data += last_index_key;
 396         size_t c = data.size();
 397         data.resize(c + 4);
 398         unaligned_write4(reinterpret_cast<unsigned char*>(&data[c]), ptr);
 399
 400         block = cur_block;
 401 #elif defined SSINDEX_SKIPLIST
 402         size_t cur_block = ptr / INDEXBLOCK;
 403         if (cur_block == block) return;
 404
 405         size_t reuse = common_prefix_length(last_index_key, key);
 406
 407         data += char(reuse);
 408         data += char(key.size() - reuse);
 409         data.append(key, reuse, key.size() - reuse);
 410         pack_uint(data, static_cast<std::make_unsigned<off_t>::type>(ptr));
 411
 412         block = cur_block;
 413         // FIXME: deal with parent_index...
 414
 415         last_index_key = key;
 416 #else
 417 # error "SSINDEX type not specified"
 418 #endif
 419     }
 420
 421     off_t write(BufferedFile& fh) {
 422 #ifdef SSINDEX_ARRAY
 423         if (!pointers) {
 424             first = last = 0;
 425             pointers = new off_t[1]();
 426         }
 427         data.resize(0);
 428         data.resize(3 + (last - first + 1) * 4);
 429         data[0] = 0;
 430         data[1] = first;
 431         data[2] = last - first;
 432         for (unsigned ch = first; ch <= last; ++ch) {
 433             size_t o = 3 + (ch - first) * 4;
 434             // FIXME: Just make offsets 8 bytes?  Or allow different widths?
 435             off_t ptr = pointers[ch];
 436             if (ptr > 0xffffffff)
 437                 throw Xapian::DatabaseError("Index offset needs >4 bytes");
 438             Assert(o + 4 <= data.size());
 439             unaligned_write4(reinterpret_cast<unsigned char*>(&data[o]), ptr);
 440         }
 441         delete [] pointers;
 442         pointers = NULL;
 443 #elif defined SSINDEX_BINARY_CHOP
 444         // Fill in bytes 1 to 4 with the number of entries.
 445         size_t n_index = (data.size() - 5) / (SSINDEX_BINARY_CHOP_KEY_SIZE + 4);
 446         data[1] = n_index >> 24;
 447         data[2] = n_index >> 16;
 448         data[3] = n_index >> 8;
 449         data[4] = n_index;
 450 #elif defined SSINDEX_SKIPLIST
 451         // Already built in data.
 452 #else
 453 # error "SSINDEX type not specified"
 454 #endif
 455
 456         off_t root = fh.get_pos();
 457         fh.write(data.data(), data.size());
 458         // FIXME: parent stuff...
 459         return root;
 460     }
 461
 462     size_t size() const {
 463         // FIXME: For SSINDEX_ARRAY, data.size() only correct after calling
 464         // write().
 465         size_t s = data.size();
 466         if (parent_index) s += parent_index->size();
 467         return s;
 468     }
 469 };
 470
 471 class HoneyCursor;
 472 class MutableHoneyCursor;
 473
 474 class HoneyTable {
 475     friend class HoneyCursor; // Allow access to fh.  FIXME cleaner way?
 476     friend class MutableHoneyCursor; // Allow access to fh.  FIXME cleaner way?
 477
 478     std::string path;
 479     bool read_only;
 480     int flags;
 481     uint4 compress_min;
 482     mutable BufferedFile fh;
 483     mutable std::string last_key;
 484     SSIndex index;
 485     off_t root = -1;
 486     honey_tablesize_t num_entries = 0;
 487     bool lazy;
 488
 489     bool single_file() const { return path.empty(); }
 490
 491     /** Offset to add to pointers in this table.
 492      *
 493      *  This is zero when each table is a separate file, but likely non-zero
 494      *  when the tables are all embedded in one file.
 495      */
 496     off_t offset = 0;
 497
 498     bool get_exact_entry(const std::string& key, std::string* tag) const;
 499
 500     bool read_key(std::string& key, size_t& val_size, bool& compressed) const;
 501
 502     void read_val(std::string& val, size_t val_size) const;
 503
 504   public:
 505     HoneyTable(const char*, const std::string& path_, bool read_only_,
 506                bool lazy_ = false)
 507         : path(path_ + HONEY_TABLE_EXTENSION),
 508           read_only(read_only_),
 509           lazy(lazy_)
 510     {
 511     }
 512
 513     HoneyTable(const char*, int fd, off_t offset_, bool read_only_,
 514                bool lazy_ = false)
 515         : read_only(read_only_),
 516           fh(fd, offset_, read_only_),
 517           lazy(lazy_),
 518           offset(offset_)
 519     {
 520     }
 521
 522     static size_t total_index_size;
 523
 524     ~HoneyTable() {
 525 #if 0
 526         size_t index_size = index.size();
 527         total_index_size += index_size;
 528         if (index_size)
 529             std::cout << "*** " << path << " - index " << index_size << " for "
 530                       << index.get_num_entries() << " entries; total_size = "
 531                       << total_index_size << std::endl;
 532 #endif
 533         if (!single_file())
 534             fh.close();
 535         else
 536             fh.reset_fd(false);
 537     }
 538
 539     bool is_writable() const { return !read_only; }
 540
 541     int get_flags() const { return flags; }
 542
 543     void set_full_compaction(bool) { }
 544
 545     void set_max_item_size(unsigned) { }
 546
 547     void create_and_open(int flags_, const Honey::RootInfo& root_info);
 548
 549     void open(int flags_, const Honey::RootInfo& root_info,
 550               honey_revision_number_t);
 551
 552     void close(bool permanent) {
 553         if (!single_file()) {
 554             if (permanent)
 555                 fh.force_close();
 556             else
 557                 fh.close();
 558         } else {
 559             fh.reset_fd(permanent);
 560         }
 561     }
 562
 563     const std::string& get_path() const { return path; }
 564
 565     void add(const std::string& key,
 566              const char* val,
 567              size_t val_size,
 568              bool compressed = false);
 569
 570     void add(const std::string& key,
 571              const std::string& val,
 572              bool compressed = false) {
 573         add(key, val.data(), val.size(), compressed);
 574     }
 575
 576     void flush_db() {
 577         root = index.write(fh);
 578         fh.flush();
 579     }
 580
 581     void cancel(const Honey::RootInfo&, honey_revision_number_t) {
 582         std::abort();
 583     }
 584
 585     void commit(honey_revision_number_t, Honey::RootInfo* root_info);
 586
 587     bool sync() {
 588         fh.sync();
 589         return true;
 590     }
 591
 592     bool empty() const {
 593         return num_entries == 0;
 594     }
 595
 596     bool get_exact_entry(const std::string& key, std::string& tag) const {
 597         return get_exact_entry(key, &tag);
 598     }
 599
 600     bool key_exists(const std::string& key) const {
 601         return get_exact_entry(key, NULL);
 602     }
 603
 604     bool del(const std::string&) {
 605         std::abort();
 606     }
 607
 608     // readahead probably not useful?  (FIXME)
 609     bool readahead_key(const std::string&) const { return false; }
 610
 611     bool is_modified() const { return !read_only && !empty(); }
 612
 613     HoneyCursor* cursor_get() const;
 614
 615     bool exists() const {
 616         struct stat sbuf;
 617         return stat(path.c_str(), &sbuf) == 0;
 618     }
 619
 620     bool is_open() const { return fh.is_open(); }
 621
 622     void set_changes(HoneyChanges*) { }
 623
 624     static void throw_database_closed() {
 625         throw Xapian::DatabaseError("Closed!");
 626     }
 627
 628     honey_tablesize_t get_entry_count() const { return num_entries; }
 629
 630     off_t get_root() const { return root; }
 631
 632     off_t get_offset() const { return offset; }
 633 };
 634
 635 #endif // XAPIAN_INCLUDED_HONEY_TABLE_H