LCOV - code coverage report
Current view: top level - backends/glass - glass_check.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 954b5873a738 Lines: 96 224 42.9 %
Date: 2019-06-30 05:20:33 Functions: 2 11 18.2 %
Branches: 135 392 34.4 %

           Branch data     Line data    Source code
       1                 :            : /** @file glass_check.cc
       2                 :            :  * @brief Btree checking
       3                 :            :  */
       4                 :            : /* Copyright 1999,2000,2001 BrightStation PLC
       5                 :            :  * Copyright 2002 Ananova Ltd
       6                 :            :  * Copyright 2002,2004,2005,2008,2009,2011,2012,2013,2014,2016 Olly Betts
       7                 :            :  * Copyright 2008 Lemur Consulting Ltd
       8                 :            :  *
       9                 :            :  * This program is free software; you can redistribute it and/or
      10                 :            :  * modify it under the terms of the GNU General Public License as
      11                 :            :  * published by the Free Software Foundation; either version 2 of the
      12                 :            :  * License, or (at your option) any later version.
      13                 :            :  *
      14                 :            :  * This program is distributed in the hope that it will be useful,
      15                 :            :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      16                 :            :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      17                 :            :  * GNU General Public License for more details.
      18                 :            :  *
      19                 :            :  * You should have received a copy of the GNU General Public License
      20                 :            :  * along with this program; if not, write to the Free Software
      21                 :            :  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301
      22                 :            :  * USA
      23                 :            :  */
      24                 :            : 
      25                 :            : #include <config.h>
      26                 :            : 
      27                 :            : #include "glass_check.h"
      28                 :            : #include "glass_version.h"
      29                 :            : #include "unicode/description_append.h"
      30                 :            : #include "xapian/constants.h"
      31                 :            : 
      32                 :            : #include <climits>
      33                 :            : #include <cstring>
      34                 :            : #include <memory>
      35                 :            : #include <ostream>
      36                 :            : 
      37                 :            : using namespace Glass;
      38                 :            : using namespace std;
      39                 :            : 
      40                 :          0 : void GlassTableCheck::print_spaces(int n) const
      41                 :            : {
      42         [ #  # ]:          0 :     while (n--) out->put(' ');
      43                 :          0 : }
      44                 :            : 
      45                 :          0 : void GlassTableCheck::print_bytes(int n, const uint8_t * p) const
      46                 :            : {
      47                 :          0 :     out->write(reinterpret_cast<const char *>(p), n);
      48                 :          0 : }
      49                 :            : 
      50                 :          0 : void GlassTableCheck::print_key(const uint8_t * p, int c, int j) const
      51                 :            : {
      52         [ #  # ]:          0 :     if (j == 0) {
      53         [ #  # ]:          0 :         LeafItem item(p, c);
      54         [ #  # ]:          0 :         string key;
      55         [ #  # ]:          0 :         if (item.key().length() >= 0)
      56         [ #  # ]:          0 :             item.key().read(&key);
      57         [ #  # ]:          0 :         string escaped;
      58         [ #  # ]:          0 :         description_append(escaped, key);
      59         [ #  # ]:          0 :         *out << escaped;
      60         [ #  # ]:          0 :         int x = item.component_of();
      61 [ #  # ][ #  # ]:          0 :         *out << ' ' << x;
      62         [ #  # ]:          0 :         if (item.last_component()) {
      63 [ #  # ][ #  # ]:          0 :             *out << '/' << x;
      64                 :          0 :         }
      65                 :            :     } else {
      66         [ #  # ]:          0 :         BItem item(p, c);
      67         [ #  # ]:          0 :         string key;
      68         [ #  # ]:          0 :         if (item.key().length() >= 0)
      69         [ #  # ]:          0 :             item.key().read(&key);
      70         [ #  # ]:          0 :         string escaped;
      71         [ #  # ]:          0 :         description_append(escaped, key);
      72         [ #  # ]:          0 :         *out << escaped;
      73                 :            :     }
      74                 :          0 : }
      75                 :            : 
      76                 :          0 : void GlassTableCheck::print_tag(const uint8_t * p, int c, int j) const
      77                 :            : {
      78         [ #  # ]:          0 :     if (j == 0) {
      79         [ #  # ]:          0 :         LeafItem item(p, c);
      80         [ #  # ]:          0 :         string tag;
      81         [ #  # ]:          0 :         item.append_chunk(&tag);
      82         [ #  # ]:          0 :         string escaped;
      83         [ #  # ]:          0 :         description_append(escaped, tag);
      84 [ #  # ][ #  # ]:          0 :         *out << ' ' << escaped;
      85                 :            :     } else {
      86         [ #  # ]:          0 :         BItem item(p, c);
      87 [ #  # ][ #  # ]:          0 :         *out << "--> [" << item.block_given_by() << ']';
         [ #  # ][ #  # ]
      88                 :            :     }
      89                 :          0 : }
      90                 :            : 
      91                 :          0 : void GlassTableCheck::report_block_full(int m, int n, const uint8_t * p) const
      92                 :            : {
      93                 :          0 :     int j = GET_LEVEL(p);
      94                 :          0 :     int dir_end = DIR_END(p);
      95                 :          0 :     *out << '\n';
      96                 :          0 :     print_spaces(m);
      97                 :          0 :     *out << "Block [" << n << "] level " << j << ", revision *" << REVISION(p)
      98                 :          0 :          << " items (" << (dir_end - DIR_START) / D2 << ") usage "
      99                 :          0 :          << block_usage(p) << "%:\n";
     100         [ #  # ]:          0 :     for (int c = DIR_START; c < dir_end; c += D2) {
     101                 :          0 :         print_spaces(m);
     102                 :          0 :         print_key(p, c, j);
     103                 :          0 :         *out << ' ';
     104                 :          0 :         print_tag(p, c, j);
     105                 :          0 :         *out << '\n';
     106                 :            :     }
     107                 :          0 : }
     108                 :            : 
     109                 :          0 : int GlassTableCheck::block_usage(const uint8_t * p) const
     110                 :            : {
     111                 :          0 :     int space = block_size - DIR_END(p);
     112                 :          0 :     int free = TOTAL_FREE(p);
     113                 :          0 :     return (space - free) * 100 / space;  /* a percentage */
     114                 :            : }
     115                 :            : 
     116                 :            : /** GlassTableCheck::report_block(m, n, p) prints the block at p, block number n,
     117                 :            :  *  indented by m spaces.
     118                 :            :  */
     119                 :          0 : void GlassTableCheck::report_block(int m, int n, const uint8_t * p) const
     120                 :            : {
     121                 :          0 :     int j = GET_LEVEL(p);
     122                 :          0 :     int dir_end = DIR_END(p);
     123                 :            :     int c;
     124                 :          0 :     print_spaces(m);
     125                 :          0 :     *out << "[" << n << "] *" << REVISION(p) << " ("
     126                 :          0 :          << (dir_end - DIR_START) / D2 << ") " << block_usage(p) << "% ";
     127                 :            : 
     128         [ #  # ]:          0 :     for (c = DIR_START; c < dir_end; c += D2) {
     129 [ #  # ][ #  # ]:          0 :         if (c >= DIR_START + 6 && c < dir_end - 6) {
     130         [ #  # ]:          0 :             if (c == DIR_START + 6) *out << "... ";
     131                 :          0 :             continue;
     132                 :            :         }
     133                 :            : 
     134                 :          0 :         print_key(p, c, j);
     135                 :          0 :         *out << ' ';
     136                 :            :     }
     137                 :          0 :     *out << endl;
     138                 :          0 : }
     139                 :            : 
     140                 :            : [[noreturn]]
     141                 :            : static void
     142                 :          0 : failure(const char *msg, uint4 n, int c = 0)
     143                 :            : {
     144         [ #  # ]:          0 :     string e = "Block ";
     145 [ #  # ][ #  # ]:          0 :     e += str(n);
     146         [ #  # ]:          0 :     if (c) {
     147         [ #  # ]:          0 :         e += " item ";
     148 [ #  # ][ #  # ]:          0 :         e += str((c - DIR_START) / D2);
     149                 :            :     }
     150         [ #  # ]:          0 :     e += ": ";
     151         [ #  # ]:          0 :     e += msg;
     152 [ #  # ][ #  # ]:          0 :     throw Xapian::DatabaseError(e);
     153                 :            : }
     154                 :            : 
     155                 :            : void
     156                 :         60 : GlassTableCheck::block_check(Glass::Cursor * C_, int j, int opts,
     157                 :            :                              GlassFreeListChecker & flcheck)
     158                 :            : {
     159                 :         60 :     const uint8_t * p = C_[j].get_p();
     160                 :         60 :     uint4 n = C_[j].get_n();
     161                 :            :     int c;
     162         [ +  + ]:         60 :     int significant_c = j == 0 ? DIR_START : DIR_START + D2;
     163                 :            :         /* the first key in an index block is dummy, remember */
     164                 :            : 
     165                 :         60 :     size_t max_free = MAX_FREE(p);
     166                 :         60 :     int dir_end = DIR_END(p);
     167                 :         60 :     int total_free = block_size - dir_end;
     168                 :            : 
     169         [ -  + ]:         60 :     if (!flcheck.mark_used(n))
     170                 :          0 :         failure("used more than once in the Btree", n);
     171                 :            : 
     172         [ -  + ]:         60 :     if (j != GET_LEVEL(p))
     173                 :          0 :         failure("wrong level", n);
     174                 :            :     // dir_end must be > DIR_START, fit within the block, and be odd.
     175 [ +  - ][ +  - ]:         60 :     if (dir_end <= DIR_START || dir_end > int(block_size) || (dir_end & 1) != 1)
                 [ -  + ]
     176                 :          0 :         failure("directory end pointer invalid", n);
     177                 :            : 
     178         [ -  + ]:         60 :     if (opts & Xapian::DBCHECK_SHORT_TREE)
     179                 :          0 :         report_block(3*(level - j), n, p);
     180                 :            : 
     181         [ -  + ]:         60 :     if (opts & Xapian::DBCHECK_FULL_TREE)
     182                 :          0 :         report_block_full(3*(level - j), n, p);
     183                 :            : 
     184         [ +  + ]:         60 :     if (j == 0) {
     185         [ +  + ]:       2811 :         for (c = DIR_START; c < dir_end; c += D2) {
     186         [ +  - ]:       2755 :             LeafItem item(p, c);
     187                 :       2755 :             int o = item.get_address() - p;
     188         [ -  + ]:       2755 :             if (o > int(block_size))
     189                 :          0 :                 failure("item starts outside block", n, c);
     190         [ -  + ]:       2755 :             if (o - dir_end < int(max_free))
     191                 :          0 :                 failure("item overlaps directory", n, c);
     192                 :            : 
     193         [ +  - ]:       2755 :             int kt_len = item.size();
     194         [ -  + ]:       2755 :             if (o + kt_len > int(block_size))
     195                 :          0 :                 failure("item ends outside block", n, c);
     196                 :       2755 :             total_free -= kt_len;
     197                 :            : 
     198 [ +  + ][ +  - ]:       2755 :             if (c > significant_c && compare(LeafItem(p, c - D2), item) >= 0)
         [ +  - ][ -  + ]
                 [ +  + ]
           [ -  +  #  # ]
     199                 :          0 :                 failure("not in sorted order", n, c);
     200                 :            :         }
     201                 :            :     } else {
     202         [ +  + ]:         15 :         for (c = DIR_START; c < dir_end; c += D2) {
     203         [ +  - ]:         11 :             BItem item(p, c);
     204                 :         11 :             int o = item.get_address() - p;
     205         [ -  + ]:         11 :             if (o > int(block_size))
     206                 :          0 :                 failure("item starts outside block", n, c);
     207         [ -  + ]:         11 :             if (o - dir_end < int(max_free))
     208                 :          0 :                 failure("item overlaps directory", n, c);
     209                 :            : 
     210         [ +  - ]:         11 :             int kt_len = item.size();
     211         [ -  + ]:         11 :             if (o + kt_len > int(block_size))
     212                 :          0 :                 failure("item ends outside block", n, c);
     213                 :         11 :             total_free -= kt_len;
     214                 :            : 
     215 [ +  + ][ +  - ]:         11 :             if (c > significant_c && compare(BItem(p, c - D2), item) >= 0)
         [ +  - ][ -  + ]
                 [ +  + ]
           [ -  +  #  # ]
     216                 :          0 :                 failure("not in sorted order", n, c);
     217                 :            :         }
     218                 :            :     }
     219         [ -  + ]:         60 :     if (total_free != TOTAL_FREE(p))
     220                 :          0 :         failure("stored total free space value wrong", n);
     221                 :            : 
     222         [ +  + ]:         64 :     if (j == 0) return;
     223         [ +  + ]:         15 :     for (c = DIR_START; c < dir_end; c += D2) {
     224                 :         11 :         C_[j].c = c;
     225 [ +  - ][ +  - ]:         11 :         block_to_cursor(C_, j - 1, BItem(p, c).block_given_by());
     226                 :            : 
     227                 :         11 :         block_check(C_, j - 1, opts, flcheck);
     228                 :            : 
     229                 :         11 :         const uint8_t * q = C_[j - 1].get_p();
     230                 :            :         /* if j == 1, and c > DIR_START, the first key of level j - 1 must be
     231                 :            :          * >= the key of p, c: */
     232                 :            : 
     233 [ +  - ][ +  + ]:         11 :         if (j == 1 && c > DIR_START)
     234 [ +  - ][ +  - ]:          7 :             if (compare(LeafItem(q, DIR_START), BItem(p, c)) < 0)
                 [ -  + ]
     235                 :          0 :                 failure("leaf key < left dividing key in level above", n, c);
     236                 :            : 
     237                 :            :         /* if j > 1, and c > DIR_START, the second key of level j - 1 must be
     238                 :            :          * >= the key of p, c: */
     239                 :            : 
     240 [ -  + ][ #  # ]:         22 :         if (j > 1 && c > DIR_START && DIR_END(q) > DIR_START + D2 &&
         [ #  # ][ #  # ]
         [ #  # ][ -  + ]
     241 [ #  # ][ #  # ]:         11 :             compare(BItem(q, DIR_START + D2), BItem(p, c)) < 0)
         [ #  # ][ -  + ]
                 [ +  - ]
           [ #  #  #  # ]
     242                 :          0 :             failure("key < left dividing key in level above", n, c);
     243                 :            : 
     244                 :            :         /* the last key of level j - 1 must be < the key of p, c + D2, if c +
     245                 :            :          * D2 < dir_end: */
     246                 :            : 
     247         [ +  + ]:         11 :         if (c + D2 < dir_end) {
     248         [ +  - ]:          7 :             if (j == 1) {
     249 [ +  - ][ +  - ]:          7 :                 if (compare(LeafItem(q, DIR_END(q) - D2), BItem(p, c + D2)) >= 0)
         [ +  - ][ -  + ]
     250                 :          0 :                     failure("leaf key >= right dividing key in level above", n, c);
     251         [ #  # ]:          0 :             } else if (DIR_START + D2 < DIR_END(q)) {
     252 [ #  # ][ #  # ]:          0 :                 if (compare(BItem(q, DIR_END(q) - D2), BItem(p, c + D2)) >= 0)
         [ #  # ][ #  # ]
     253                 :          0 :                     failure("key >= right dividing key in level above", n, c);
     254                 :            :             }
     255                 :            :         }
     256                 :            : 
     257         [ -  + ]:         11 :         if (REVISION(q) > REVISION(p))
     258                 :          0 :             failure("block has greater revision than parent", n);
     259                 :            :     }
     260                 :            : }
     261                 :            : 
     262                 :            : GlassTableCheck *
     263                 :         59 : GlassTableCheck::check(const char * tablename, const string & path, int fd,
     264                 :            :                        off_t offset_,
     265                 :            :                        const GlassVersion & version_file, int opts,
     266                 :            :                        ostream *out)
     267                 :            : {
     268         [ +  - ]:         59 :     string filename(path);
     269         [ +  - ]:         59 :     filename += '/';
     270         [ +  - ]:         59 :     filename += tablename;
     271         [ +  - ]:         59 :     filename += '.';
     272                 :            : 
     273                 :            :     unique_ptr<GlassTableCheck> B(
     274                 :            :             fd < 0 ?
     275         [ +  - ]:         29 :             new GlassTableCheck(tablename, filename, false, out) :
     276 [ +  + ][ +  - ]:        147 :             new GlassTableCheck(tablename, fd, offset_, false, out));
         [ +  - ][ +  - ]
     277                 :            : 
     278                 :            :     Glass::table_type tab_type;
     279         [ +  + ]:         59 :     if (strcmp(tablename, "postlist") == 0) {
     280                 :         15 :         tab_type = Glass::POSTLIST;
     281         [ +  + ]:         44 :     } else if (strcmp(tablename, "docdata") == 0) {
     282                 :         10 :         tab_type = Glass::DOCDATA;
     283         [ +  + ]:         34 :     } else if (strcmp(tablename, "termlist") == 0) {
     284                 :         15 :         tab_type = Glass::TERMLIST;
     285         [ +  + ]:         19 :     } else if (strcmp(tablename, "position") == 0) {
     286                 :          9 :         tab_type = Glass::POSITION;
     287         [ +  + ]:         10 :     } else if (strcmp(tablename, "spelling") == 0) {
     288                 :          5 :         tab_type = Glass::SPELLING;
     289         [ +  - ]:          5 :     } else if (strcmp(tablename, "synonym") == 0) {
     290                 :          5 :         tab_type = Glass::SYNONYM;
     291                 :            :     } else {
     292         [ #  # ]:          0 :         string e = "Unknown table: ";
     293         [ #  # ]:          0 :         e += tablename;
     294 [ #  # ][ #  # ]:          0 :         throw Xapian::DatabaseError(e);
     295                 :            :     }
     296                 :            : 
     297         [ +  - ]:         59 :     B->open(0, version_file.get_root(tab_type), version_file.get_revision());
     298                 :         59 :     Glass::Cursor * C = B->C;
     299                 :            : 
     300         [ +  + ]:         59 :     if (opts & Xapian::DBCHECK_SHOW_STATS) {
     301 [ +  - ][ +  - ]:         10 :         *out << "blocksize=" << B->block_size / 1024 << "K"
     302 [ +  - ][ +  - ]:         20 :                 " items=" << B->item_count
     303 [ +  - ][ +  - ]:         20 :              << " firstunused=" << B->free_list.get_first_unused_block()
     304 [ +  - ][ +  - ]:         20 :              << " revision=" << B->revision_number
     305 [ +  - ][ +  - ]:         20 :              << " levels=" << B->level
     306         [ +  - ]:         10 :              << " root=";
     307         [ +  + ]:         10 :         if (B->faked_root_block)
     308         [ +  - ]:          2 :             *out << "(faked)";
     309                 :            :         else
     310 [ +  - ][ +  - ]:          8 :             *out << C[B->level].get_n();
     311         [ +  - ]:         10 :         *out << endl;
     312                 :            :     }
     313                 :            : 
     314         [ +  + ]:         59 :     if (B->faked_root_block) {
     315 [ +  + ][ +  + ]:         10 :         if (out && opts)
     316         [ +  - ]:          2 :             *out << "void ";
     317                 :            :     } else {
     318                 :            :         // We walk the Btree marking off the blocks which it uses, then walk
     319                 :            :         // the free list, marking the blocks which aren't used.  Any blocks not
     320                 :            :         // marked have been leaked.
     321         [ +  - ]:         49 :         GlassFreeListChecker flcheck(B->free_list);
     322         [ +  - ]:         98 :         GlassFreeListChecker flcheck2(B->free_list);
     323         [ +  - ]:         49 :         B->block_check(C, B->level, opts, flcheck);
     324                 :            : 
     325         [ -  + ]:         49 :         if (opts & Xapian::DBCHECK_SHOW_FREELIST) {
     326         [ #  # ]:          0 :             *out << "Freelist:";
     327         [ #  # ]:          0 :             if (B->free_list.empty())
     328         [ #  # ]:          0 :                 *out << " empty";
     329                 :            :         }
     330         [ +  + ]:        109 :         while (!B->free_list.empty()) {
     331         [ +  - ]:         60 :             uint4 n = B->free_list.walk(B.get(), B->block_size, true);
     332         [ -  + ]:         60 :             if (opts & Xapian::DBCHECK_SHOW_FREELIST)
     333 [ #  # ][ #  # ]:          0 :                 *out << ' ' << n;
     334         [ -  + ]:         60 :             if (!flcheck2.mark_used(n)) {
     335         [ #  # ]:          0 :                 if (opts & Xapian::DBCHECK_SHOW_FREELIST)
     336         [ #  # ]:          0 :                     *out << endl;
     337                 :          0 :                 failure("Same block is in freelist more than once", n);
     338                 :            :             }
     339         [ -  + ]:         60 :             if (!flcheck.mark_used(n)) {
     340         [ #  # ]:          0 :                 if (opts & Xapian::DBCHECK_SHOW_FREELIST)
     341         [ #  # ]:          0 :                     *out << endl;
     342                 :          0 :                 failure("Used block also in freelist", n);
     343                 :            :             }
     344                 :            :         }
     345         [ -  + ]:         49 :         if (opts & Xapian::DBCHECK_SHOW_FREELIST)
     346         [ #  # ]:          0 :             *out << endl;
     347                 :            : 
     348                 :            :         uint4 first_bad;
     349         [ +  - ]:         49 :         uint4 count = flcheck.count_set_bits(&first_bad);
     350                 :            :         // Skip this check for a single file DB for now.  FIXME
     351 [ +  + ][ -  + ]:         49 :         if (count && fd < 0) {
     352         [ #  # ]:          0 :             string e = str(count);
     353         [ #  # ]:          0 :             e += " unused block(s) missing from the free list, first is ";
     354 [ #  # ][ #  # ]:          0 :             e += str(first_bad);
     355 [ #  # ][ #  # ]:          0 :             throw Xapian::DatabaseError(e);
     356                 :         49 :         }
     357                 :            :     }
     358 [ +  + ][ +  + ]:         59 :     if (out && opts) *out << "B-tree checked okay" << endl;
         [ +  - ][ +  - ]
     359                 :        118 :     return B.release();
     360                 :            : }
     361                 :            : 
     362                 :          0 : void GlassTableCheck::report_cursor(int N, const Glass::Cursor * C_) const
     363                 :            : {
     364                 :          0 :     *out << N << ")\n";
     365         [ #  # ]:          0 :     for (int i = 0; i <= level; ++i)
     366                 :          0 :         *out << "p=" << C_[i].get_p() << ", "
     367                 :          0 :                 "c=" << C_[i].c << ", "
     368                 :          0 :                 "n=[" << C_[i].get_n() << "], "
     369                 :          0 :                 "rewrite=" << C_[i].rewrite << endl;
     370                 :          0 : }
     371                 :            : 
     372                 :            : #ifdef DISABLE_GPL_LIBXAPIAN
     373                 :            : # error GPL source we cannot relicense included in libxapian
     374                 :            : #endif

Generated by: LCOV version 1.11