LCOV - code coverage report
Current view: top level - backends/honey - honey_freelist.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 954b5873a738 Lines: 0 116 0.0 %
Date: 2019-06-30 05:20:33 Functions: 0 8 0.0 %
Branches: 0 124 0.0 %

           Branch data     Line data    Source code
       1                 :            : /** @file honey_freelist.cc
       2                 :            :  * @brief Honey freelist
       3                 :            :  */
       4                 :            : /* Copyright 2014,2015,2016 Olly Betts
       5                 :            :  *
       6                 :            :  * This program is free software; you can redistribute it and/or
       7                 :            :  * modify it under the terms of the GNU General Public License as
       8                 :            :  * published by the Free Software Foundation; either version 2 of the
       9                 :            :  * License, or (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
      19                 :            :  * USA
      20                 :            :  */
      21                 :            : 
      22                 :            : #include <config.h>
      23                 :            : 
      24                 :            : #include "honey_freelist.h"
      25                 :            : 
      26                 :            : #include "honey_table.h"
      27                 :            : #include "xapian/error.h"
      28                 :            : 
      29                 :            : #include "omassert.h"
      30                 :            : #include "wordaccess.h"
      31                 :            : #include <cstring>
      32                 :            : 
      33                 :            : #if !HAVE_DECL___BUILTIN_POPCOUNT
      34                 :            : // Only include <intrin.h> if we have to as it can result in warnings about
      35                 :            : // duplicate declarations of builtin functions under mingw.
      36                 :            : # if HAVE_DECL___POPCNT || HAVE_DECL___POPCNT64
      37                 :            : #  include <intrin.h>
      38                 :            : # endif
      39                 :            : #endif
      40                 :            : 
      41                 :            : using namespace std;
      42                 :            : using namespace Honey;
      43                 :            : 
      44                 :            : // Allow forcing the freelist to be shorter to tickle bugs.
      45                 :            : // FIXME: Sort out a way we can set this dynamically while running the
      46                 :            : // testsuite.
      47                 :            : #ifdef HONEY_FREELIST_SIZE
      48                 :            : # define FREELIST_END_ \
      49                 :            :     (8 + (HONEY_FREELIST_SIZE < 3 ? 3 : HONEY_FREELIST_SIZE) * 4)
      50                 :            : # define FREELIST_END (FREELIST_END_ < 2048 ? FREELIST_END_ : 2048)
      51                 :            : #else
      52                 :            : # define FREELIST_END block_size
      53                 :            : #endif
      54                 :            : 
      55                 :            : /** The first offset to use for storing free block info.
      56                 :            :  *
      57                 :            :  *  The first 4 bytes store the revision.  The next byte (which is the level
      58                 :            :  *  for a block in the B-tree) is set to LEVEL_FREELIST to mark this as a
      59                 :            :  *  freelist block).
      60                 :            :  */
      61                 :            : const unsigned C_BASE = 8;
      62                 :            : 
      63                 :            : /// Invalid freelist block value, so we can detect overreading bugs, etc.
      64                 :            : const uint4 UNUSED = static_cast<uint4>(-1);
      65                 :            : 
      66                 :            : void
      67                 :          0 : HoneyFreeList::read_block(const HoneyTable * B, uint4 n, uint8_t * ptr)
      68                 :            : {
      69                 :            : #ifdef SST_SEARCH
      70                 :            :     (void)B; (void)n; (void)ptr;
      71                 :            : #else
      72                 :            :     B->read_block(n, ptr);
      73                 :            :     if (rare(GET_LEVEL(ptr) != LEVEL_FREELIST))
      74                 :            :         throw Xapian::DatabaseCorruptError("Freelist corrupt");
      75                 :            : #endif
      76                 :          0 : }
      77                 :            : 
      78                 :            : void
      79                 :          0 : HoneyFreeList::write_block(const HoneyTable * B, uint4 n, uint8_t * ptr,
      80                 :            :                            uint4 rev)
      81                 :            : {
      82                 :            : #ifdef SST_SEARCH
      83                 :            :     (void)B; (void)n; (void)ptr; (void)rev;
      84                 :            : #else
      85                 :            :     SET_REVISION(ptr, rev);
      86                 :            :     aligned_write4(ptr + 4, 0);
      87                 :            :     SET_LEVEL(ptr, LEVEL_FREELIST);
      88                 :            :     B->write_block(n, ptr, flw_appending);
      89                 :            : #endif
      90                 :          0 : }
      91                 :            : 
      92                 :            : uint4
      93                 :          0 : HoneyFreeList::get_block(const HoneyTable *B, uint4 block_size,
      94                 :            :                          uint4 * blk_to_free)
      95                 :            : {
      96         [ #  # ]:          0 :     if (fl == fl_end) {
      97                 :          0 :         return first_unused_block++;
      98                 :            :     }
      99                 :            : 
     100         [ #  # ]:          0 :     if (p == 0) {
     101         [ #  # ]:          0 :         if (fl.n == UNUSED) {
     102 [ #  # ][ #  # ]:          0 :             throw Xapian::DatabaseCorruptError("Freelist pointer invalid");
                 [ #  # ]
     103                 :            :         }
     104                 :            :         // Actually read the current freelist block.
     105                 :          0 :         p = new uint8_t[block_size];
     106                 :          0 :         read_block(B, fl.n, p);
     107                 :            :     }
     108                 :            : 
     109                 :            :     // Either the freelist end is in this block, or this freelist block has a
     110                 :            :     // next pointer.
     111                 :            :     Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
     112                 :            : 
     113         [ #  # ]:          0 :     if (fl.c != FREELIST_END - 4) {
     114                 :          0 :         uint4 blk = aligned_read4(p + fl.c);
     115         [ #  # ]:          0 :         if (blk == UNUSED) {
     116 [ #  # ][ #  # ]:          0 :             throw Xapian::DatabaseCorruptError("Ran off end of freelist (" +
     117 [ #  # ][ #  # ]:          0 :                                                str(fl.n) + ", " + str(fl.c) +
         [ #  # ][ #  # ]
     118 [ #  # ][ #  # ]:          0 :                                                ")");
     119                 :            :         }
     120                 :          0 :         fl.c += 4;
     121                 :          0 :         return blk;
     122                 :            :     }
     123                 :            : 
     124                 :            :     // Delay handling marking old block as unused until after we've
     125                 :            :     // started a new one.
     126                 :          0 :     uint4 old_fl_blk = fl.n;
     127                 :            : 
     128                 :          0 :     fl.n = aligned_read4(p + fl.c);
     129         [ #  # ]:          0 :     if (fl.n == UNUSED) {
     130 [ #  # ][ #  # ]:          0 :         throw Xapian::DatabaseCorruptError("Freelist next pointer invalid");
                 [ #  # ]
     131                 :            :     }
     132                 :            :     // Allow for mini-header at start of freelist block.
     133                 :          0 :     fl.c = C_BASE;
     134                 :          0 :     read_block(B, fl.n, p);
     135                 :            : 
     136                 :            :     // Either the freelist end is in this block, or this freelist block has
     137                 :            :     // a next pointer.
     138                 :            :     Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
     139                 :            : 
     140         [ #  # ]:          0 :     if (blk_to_free) {
     141                 :            :         Assert(*blk_to_free == BLK_UNUSED);
     142                 :          0 :         *blk_to_free = old_fl_blk;
     143                 :            :     } else {
     144                 :          0 :         mark_block_unused(B, block_size, old_fl_blk);
     145                 :            :     }
     146                 :            : 
     147                 :          0 :     return get_block(B, block_size);
     148                 :            : }
     149                 :            : 
     150                 :            : uint4
     151                 :          0 : HoneyFreeList::walk(const HoneyTable *B, uint4 block_size, bool inclusive)
     152                 :            : {
     153         [ #  # ]:          0 :     if (fl == fl_end) {
     154                 :            :         // It's expected that the caller checks !empty() first.
     155                 :          0 :         return UNUSED;
     156                 :            :     }
     157                 :            : 
     158         [ #  # ]:          0 :     if (p == 0) {
     159         [ #  # ]:          0 :         if (fl.n == UNUSED) {
     160 [ #  # ][ #  # ]:          0 :             throw Xapian::DatabaseCorruptError("Freelist pointer invalid");
                 [ #  # ]
     161                 :            :         }
     162                 :          0 :         p = new uint8_t[block_size];
     163                 :          0 :         read_block(B, fl.n, p);
     164         [ #  # ]:          0 :         if (inclusive) {
     165                 :            :             Assert(fl.n == fl_end.n ||
     166                 :            :                    aligned_read4(p + FREELIST_END - 4) != UNUSED);
     167                 :          0 :             return fl.n;
     168                 :            :         }
     169                 :            :     }
     170                 :            : 
     171                 :            :     // Either the freelist end is in this block, or this freelist block has
     172                 :            :     // a next pointer.
     173                 :            :     Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
     174                 :            : 
     175         [ #  # ]:          0 :     if (fl.c != FREELIST_END - 4) {
     176                 :          0 :         uint4 blk = aligned_read4(p + fl.c);
     177                 :          0 :         fl.c += 4;
     178                 :          0 :         return blk;
     179                 :            :     }
     180                 :            : 
     181                 :          0 :     fl.n = aligned_read4(p + fl.c);
     182         [ #  # ]:          0 :     if (fl.n == UNUSED) {
     183 [ #  # ][ #  # ]:          0 :         throw Xapian::DatabaseCorruptError("Freelist next pointer invalid");
                 [ #  # ]
     184                 :            :     }
     185                 :            :     // Allow for mini-header at start of freelist block.
     186                 :          0 :     fl.c = C_BASE;
     187                 :          0 :     read_block(B, fl.n, p);
     188                 :            : 
     189                 :            :     // Either the freelist end is in this block, or this freelist block has
     190                 :            :     // a next pointer.
     191                 :            :     Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
     192                 :            : 
     193         [ #  # ]:          0 :     if (inclusive)
     194                 :          0 :         return fl.n;
     195                 :          0 :     return walk(B, block_size, inclusive);
     196                 :            : }
     197                 :            : 
     198                 :            : void
     199                 :          0 : HoneyFreeList::mark_block_unused(const HoneyTable * B,
     200                 :            :                                  uint4 block_size,
     201                 :            :                                  uint4 blk)
     202                 :            : {
     203                 :            :     // If the current flw block is full, we need to call get_block(), and if
     204                 :            :     // the returned block is the last entry in its freelist block, that block
     205                 :            :     // needs to be marked as unused.  The recursion this would create is
     206                 :            :     // problematic, so we instead note down that block and mark it as unused
     207                 :            :     // once we've processed the original request.
     208                 :          0 :     uint4 blk_to_free = BLK_UNUSED;
     209                 :            : 
     210         [ #  # ]:          0 :     if (!pw) {
     211         [ #  # ]:          0 :         pw = new uint8_t[block_size];
     212         [ #  # ]:          0 :         if (flw.c != 0) {
     213                 :          0 :             read_block(B, flw.n, pw);
     214                 :          0 :             flw_appending = true;
     215                 :            :         }
     216                 :            :     }
     217         [ #  # ]:          0 :     if (flw.c == 0) {
     218         [ #  # ]:          0 :         uint4 n = get_block(B, block_size, &blk_to_free);
     219                 :          0 :         flw.n = n;
     220                 :          0 :         flw.c = C_BASE;
     221         [ #  # ]:          0 :         if (fl.c == 0) {
     222                 :          0 :             fl = fl_end = flw;
     223                 :            :         }
     224                 :          0 :         flw_appending = (n == first_unused_block - 1);
     225         [ #  # ]:          0 :         aligned_write4(pw + FREELIST_END - 4, UNUSED);
     226         [ #  # ]:          0 :     } else if (flw.c == FREELIST_END - 4) {
     227                 :            :         // blk is free *after* the current revision gets released, so we can't
     228                 :            :         // just use blk as the next block in the freelist chain.
     229         [ #  # ]:          0 :         uint4 n = get_block(B, block_size, &blk_to_free);
     230         [ #  # ]:          0 :         aligned_write4(pw + flw.c, n);
     231                 :            : #ifdef HONEY_FREELIST_SIZE
     232                 :            :         if (block_size != FREELIST_END) {
     233                 :            :             memset(pw + FREELIST_END, 0, block_size - FREELIST_END);
     234                 :            :         }
     235                 :            : #endif
     236                 :          0 :         write_block(B, flw.n, pw, revision + 1);
     237 [ #  # ][ #  # ]:          0 :         if (p && flw.n == fl.n) {
     238                 :            :             // FIXME: share and refcount?
     239                 :          0 :             memcpy(p, pw, block_size);
     240                 :            :             Assert(fl.n == fl_end.n ||
     241                 :            :                    aligned_read4(p + FREELIST_END - 4) != UNUSED);
     242                 :            :         }
     243                 :          0 :         flw.n = n;
     244                 :          0 :         flw.c = C_BASE;
     245                 :          0 :         flw_appending = (n == first_unused_block - 1);
     246         [ #  # ]:          0 :         aligned_write4(pw + FREELIST_END - 4, UNUSED);
     247                 :            :     }
     248                 :            : 
     249         [ #  # ]:          0 :     aligned_write4(pw + flw.c, blk);
     250                 :          0 :     flw.c += 4;
     251                 :            : 
     252         [ #  # ]:          0 :     if (blk_to_free != BLK_UNUSED)
     253         [ #  # ]:          0 :         mark_block_unused(B, block_size, blk_to_free);
     254                 :          0 : }
     255                 :            : 
     256                 :            : void
     257                 :          0 : HoneyFreeList::commit(const HoneyTable * B, uint4 block_size)
     258                 :            : {
     259 [ #  # ][ #  # ]:          0 :     if (pw && flw.c != 0) {
     260                 :          0 :         memset(pw + flw.c, 255, FREELIST_END - flw.c - 4);
     261                 :            : #ifdef HONEY_FREELIST_SIZE
     262                 :            :         if (block_size != FREELIST_END) {
     263                 :            :             memset(pw + FREELIST_END, 0xaa, block_size - FREELIST_END);
     264                 :            :         }
     265                 :            : #endif
     266                 :          0 :         write_block(B, flw.n, pw, revision);
     267 [ #  # ][ #  # ]:          0 :         if (p && flw.n == fl.n) {
     268                 :            :             // FIXME: share and refcount?
     269                 :          0 :             memcpy(p, pw, block_size);
     270                 :            :             Assert(fl.n == fl_end.n ||
     271                 :            :                    aligned_read4(p + FREELIST_END - 4) != UNUSED);
     272                 :            :         }
     273                 :          0 :         flw_appending = true;
     274                 :          0 :         fl_end = flw;
     275                 :            :     }
     276                 :          0 : }
     277                 :            : 
     278                 :          0 : HoneyFreeListChecker::HoneyFreeListChecker(const HoneyFreeList & fl)
     279                 :            : {
     280                 :          0 :     const unsigned BITS_PER_ELT = sizeof(elt_type) * 8;
     281                 :          0 :     const elt_type ALL_BITS = static_cast<elt_type>(-1);
     282                 :          0 :     uint4 first_unused = fl.get_first_unused_block();
     283                 :          0 :     bitmap_size = (first_unused + BITS_PER_ELT - 1) / BITS_PER_ELT;
     284 [ #  # ][ #  # ]:          0 :     bitmap = new elt_type[bitmap_size];
     285         [ #  # ]:          0 :     std::fill_n(bitmap, bitmap_size - 1, ALL_BITS);
     286                 :            :     // Only set the bits in the final element of bitmap which correspond to
     287                 :            :     // blocks < first_unused.
     288                 :          0 :     uint4 remainder = first_unused & (BITS_PER_ELT - 1);
     289         [ #  # ]:          0 :     if (remainder)
     290                 :          0 :         bitmap[bitmap_size - 1] = (static_cast<elt_type>(1) << remainder) - 1;
     291                 :            :     else
     292                 :          0 :         bitmap[bitmap_size - 1] = ALL_BITS;
     293                 :          0 : }
     294                 :            : 
     295                 :            : uint4
     296                 :          0 : HoneyFreeListChecker::count_set_bits(uint4 * p_first_bad_blk) const
     297                 :            : {
     298                 :          0 :     const unsigned BITS_PER_ELT = sizeof(elt_type) * 8;
     299                 :          0 :     uint4 c = 0;
     300         [ #  # ]:          0 :     for (uint4 i = 0; i < bitmap_size; ++i) {
     301                 :          0 :         elt_type elt = bitmap[i];
     302         [ #  # ]:          0 :         if (usual(elt == 0))
     303                 :          0 :             continue;
     304 [ #  # ][ #  # ]:          0 :         if (c == 0 && p_first_bad_blk) {
     305                 :          0 :             uint4 first_bad_blk = i * BITS_PER_ELT;
     306                 :            :             if (false) {
     307                 :            : #if HAVE_DECL___BUILTIN_CTZ
     308                 :            :             } else if (sizeof(elt_type) == sizeof(unsigned)) {
     309                 :            :                 first_bad_blk += __builtin_ctz(elt);
     310                 :            : #endif
     311                 :            : #if HAVE_DECL___BUILTIN_CTZL
     312                 :            :             } else if (sizeof(elt_type) == sizeof(unsigned long)) {
     313                 :          0 :                 first_bad_blk += __builtin_ctzl(elt);
     314                 :            : #endif
     315                 :            : #if HAVE_DECL___BUILTIN_CTZLL
     316                 :            :             } else if (sizeof(elt_type) == sizeof(unsigned long long)) {
     317                 :            :                 first_bad_blk += __builtin_ctzll(elt);
     318                 :            : #endif
     319                 :            :             } else {
     320                 :            :                 for (elt_type mask = 1; (elt & mask) == 0; mask <<= 1) {
     321                 :            :                     ++first_bad_blk;
     322                 :            :                 }
     323                 :            :             }
     324                 :          0 :             *p_first_bad_blk = first_bad_blk;
     325                 :            :         }
     326                 :            : 
     327                 :            :         // Count set bits in elt.
     328                 :            :         if (false) {
     329                 :            : #if HAVE_DECL___BUILTIN_POPCOUNT
     330                 :            :         } else if (sizeof(elt_type) == sizeof(unsigned)) {
     331                 :            :             c += __builtin_popcount(elt);
     332                 :            : #elif HAVE_DECL___POPCNT
     333                 :            :         } else if (sizeof(elt_type) == sizeof(unsigned)) {
     334                 :            :             c += __popcnt(elt);
     335                 :            : #endif
     336                 :            : #if HAVE_DECL___BUILTIN_POPCOUNTL
     337                 :            :         } else if (sizeof(elt_type) == sizeof(unsigned long)) {
     338                 :          0 :             c += __builtin_popcountl(elt);
     339                 :            : #endif
     340                 :            : #if HAVE_DECL___BUILTIN_POPCOUNTLL
     341                 :            :         } else if (sizeof(elt_type) == sizeof(unsigned long long)) {
     342                 :            :             c += __builtin_popcountll(elt);
     343                 :            : #elif HAVE_DECL___POPCNT64
     344                 :            :         } else if (sizeof(elt_type) == sizeof(unsigned long long)) {
     345                 :            :             c += __popcnt64(elt);
     346                 :            : #endif
     347                 :            :         } else {
     348                 :            :             do {
     349                 :            :                 ++c;
     350                 :            :                 elt &= elt - 1;
     351                 :            :             } while (elt);
     352                 :            :         }
     353                 :            :     }
     354                 :          0 :     return c;
     355                 :            : }

Generated by: LCOV version 1.11