LCOV - code coverage report
Current view: top level - backends/glass - glass_freelist.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 954b5873a738 Lines: 103 121 85.1 %
Date: 2019-06-30 05:20:33 Functions: 8 8 100.0 %
Branches: 53 136 39.0 %

           Branch data     Line data    Source code
       1                 :            : /** @file glass_freelist.cc
       2                 :            :  * @brief Glass 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 "glass_freelist.h"
      25                 :            : 
      26                 :            : #include "glass_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 Glass;
      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 GLASS_FREELIST_SIZE
      48                 :            : # define FREELIST_END_ \
      49                 :            :     (8 + (GLASS_FREELIST_SIZE < 3 ? 3 : GLASS_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                 :        365 : GlassFreeList::read_block(const GlassTable * B, uint4 n, uint8_t * ptr)
      68                 :            : {
      69                 :        365 :     B->read_block(n, ptr);
      70         [ -  + ]:        365 :     if (rare(GET_LEVEL(ptr) != LEVEL_FREELIST))
      71 [ #  # ][ #  # ]:          0 :         throw Xapian::DatabaseCorruptError("Freelist corrupt");
                 [ #  # ]
      72                 :        365 : }
      73                 :            : 
      74                 :            : void
      75                 :      16920 : GlassFreeList::write_block(const GlassTable * B, uint4 n, uint8_t * ptr,
      76                 :            :                            uint4 rev)
      77                 :            : {
      78                 :      16920 :     SET_REVISION(ptr, rev);
      79                 :      16920 :     aligned_write4(ptr + 4, 0);
      80                 :      16920 :     SET_LEVEL(ptr, LEVEL_FREELIST);
      81                 :      16920 :     B->write_block(n, ptr, flw_appending);
      82                 :      16920 : }
      83                 :            : 
      84                 :            : uint4
      85                 :     169278 : GlassFreeList::get_block(const GlassTable *B, uint4 block_size,
      86                 :            :                          uint4 * blk_to_free)
      87                 :            : {
      88         [ +  + ]:     169278 :     if (fl == fl_end) {
      89                 :      29538 :         return first_unused_block++;
      90                 :            :     }
      91                 :            : 
      92         [ +  + ]:     139740 :     if (p == 0) {
      93         [ -  + ]:        115 :         if (fl.n == UNUSED) {
      94 [ #  # ][ #  # ]:          0 :             throw Xapian::DatabaseCorruptError("Freelist pointer invalid");
                 [ #  # ]
      95                 :            :         }
      96                 :            :         // Actually read the current freelist block.
      97                 :        115 :         p = new uint8_t[block_size];
      98                 :        115 :         read_block(B, fl.n, p);
      99                 :            :     }
     100                 :            : 
     101                 :            :     // Either the freelist end is in this block, or this freelist block has a
     102                 :            :     // next pointer.
     103                 :            :     Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
     104                 :            : 
     105         [ +  + ]:     139740 :     if (fl.c != FREELIST_END - 4) {
     106                 :     139494 :         uint4 blk = aligned_read4(p + fl.c);
     107         [ -  + ]:     139494 :         if (blk == UNUSED)
     108 [ #  # ][ #  # ]:          0 :             throw Xapian::DatabaseCorruptError("Ran off end of freelist (" + str(fl.n) + ", " + str(fl.c) + ")");
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     109                 :     139494 :         fl.c += 4;
     110                 :     139494 :         return blk;
     111                 :            :     }
     112                 :            : 
     113                 :            :     // Delay handling marking old block as unused until after we've
     114                 :            :     // started a new one.
     115                 :        246 :     uint4 old_fl_blk = fl.n;
     116                 :            : 
     117                 :        246 :     fl.n = aligned_read4(p + fl.c);
     118         [ -  + ]:        246 :     if (fl.n == UNUSED) {
     119 [ #  # ][ #  # ]:          0 :         throw Xapian::DatabaseCorruptError("Freelist next pointer invalid");
                 [ #  # ]
     120                 :            :     }
     121                 :            :     // Allow for mini-header at start of freelist block.
     122                 :        246 :     fl.c = C_BASE;
     123                 :        246 :     read_block(B, fl.n, p);
     124                 :            : 
     125                 :            :     // Either the freelist end is in this block, or this freelist block has
     126                 :            :     // a next pointer.
     127                 :            :     Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
     128                 :            : 
     129         [ -  + ]:        246 :     if (blk_to_free) {
     130                 :            :         Assert(*blk_to_free == BLK_UNUSED);
     131                 :          0 :         *blk_to_free = old_fl_blk;
     132                 :            :     } else {
     133                 :        246 :         mark_block_unused(B, block_size, old_fl_blk);
     134                 :            :     }
     135                 :            : 
     136                 :     169278 :     return get_block(B, block_size);
     137                 :            : }
     138                 :            : 
     139                 :            : uint4
     140                 :         60 : GlassFreeList::walk(const GlassTable *B, uint4 block_size, bool inclusive)
     141                 :            : {
     142         [ -  + ]:         60 :     if (fl == fl_end) {
     143                 :            :         // It's expected that the caller checks !empty() first.
     144                 :          0 :         return UNUSED;
     145                 :            :     }
     146                 :            : 
     147         [ +  + ]:         60 :     if (p == 0) {
     148         [ -  + ]:          4 :         if (fl.n == UNUSED) {
     149 [ #  # ][ #  # ]:          0 :             throw Xapian::DatabaseCorruptError("Freelist pointer invalid");
                 [ #  # ]
     150                 :            :         }
     151                 :          4 :         p = new uint8_t[block_size];
     152                 :          4 :         read_block(B, fl.n, p);
     153         [ +  - ]:          4 :         if (inclusive) {
     154                 :            :             Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
     155                 :          4 :             return fl.n;
     156                 :            :         }
     157                 :            :     }
     158                 :            : 
     159                 :            :     // Either the freelist end is in this block, or this freelist block has
     160                 :            :     // a next pointer.
     161                 :            :     Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
     162                 :            : 
     163         [ +  - ]:         56 :     if (fl.c != FREELIST_END - 4) {
     164                 :         56 :         uint4 blk = aligned_read4(p + fl.c);
     165                 :         56 :         fl.c += 4;
     166                 :         56 :         return blk;
     167                 :            :     }
     168                 :            : 
     169                 :          0 :     fl.n = aligned_read4(p + fl.c);
     170         [ #  # ]:          0 :     if (fl.n == UNUSED) {
     171 [ #  # ][ #  # ]:          0 :         throw Xapian::DatabaseCorruptError("Freelist next pointer invalid");
                 [ #  # ]
     172                 :            :     }
     173                 :            :     // Allow for mini-header at start of freelist block.
     174                 :          0 :     fl.c = C_BASE;
     175                 :          0 :     read_block(B, fl.n, p);
     176                 :            : 
     177                 :            :     // Either the freelist end is in this block, or this freelist block has
     178                 :            :     // a next pointer.
     179                 :            :     Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
     180                 :            : 
     181         [ #  # ]:          0 :     if (inclusive)
     182                 :          0 :         return fl.n;
     183                 :         60 :     return walk(B, block_size, inclusive);
     184                 :            : }
     185                 :            : 
     186                 :            : void
     187                 :     141035 : GlassFreeList::mark_block_unused(const GlassTable * B, uint4 block_size, uint4 blk)
     188                 :            : {
     189                 :            :     // If the current flw block is full, we need to call get_block(), and if
     190                 :            :     // the returned block is the last entry in its freelist block, that block
     191                 :            :     // needs to be marked as unused.  The recursion this would create is
     192                 :            :     // problematic, so we instead note down that block and mark it as unused
     193                 :            :     // once we've processed the original request.
     194                 :     141035 :     uint4 blk_to_free = BLK_UNUSED;
     195                 :            : 
     196         [ +  + ]:     141035 :     if (!pw) {
     197         [ +  - ]:        348 :         pw = new uint8_t[block_size];
     198         [ -  + ]:        348 :         if (flw.c != 0) {
     199         [ #  # ]:          0 :             read_block(B, flw.n, pw);
     200                 :          0 :             flw_appending = true;
     201                 :            :         }
     202                 :            :     }
     203         [ +  + ]:     141035 :     if (flw.c == 0) {
     204         [ +  - ]:        348 :         uint4 n = get_block(B, block_size, &blk_to_free);
     205                 :        348 :         flw.n = n;
     206                 :        348 :         flw.c = C_BASE;
     207         [ +  - ]:        348 :         if (fl.c == 0) {
     208                 :        348 :             fl = fl_end = flw;
     209                 :            :         }
     210                 :        348 :         flw_appending = (n == first_unused_block - 1);
     211         [ +  - ]:        348 :         aligned_write4(pw + FREELIST_END - 4, UNUSED);
     212         [ +  + ]:     140687 :     } else if (flw.c == FREELIST_END - 4) {
     213                 :            :         // blk is free *after* the current revision gets released, so we can't
     214                 :            :         // just use blk as the next block in the freelist chain.
     215         [ +  - ]:        246 :         uint4 n = get_block(B, block_size, &blk_to_free);
     216         [ +  - ]:        246 :         aligned_write4(pw + flw.c, n);
     217                 :            : #ifdef GLASS_FREELIST_SIZE
     218                 :            :         if (block_size != FREELIST_END) {
     219                 :            :             memset(pw + FREELIST_END, 0, block_size - FREELIST_END);
     220                 :            :         }
     221                 :            : #endif
     222         [ +  - ]:        246 :         write_block(B, flw.n, pw, revision + 1);
     223 [ +  - ][ +  - ]:        246 :         if (p && flw.n == fl.n) {
     224                 :            :             // FIXME: share and refcount?
     225                 :        246 :             memcpy(p, pw, block_size);
     226                 :            :             Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
     227                 :            :         }
     228                 :        246 :         flw.n = n;
     229                 :        246 :         flw.c = C_BASE;
     230                 :        246 :         flw_appending = (n == first_unused_block - 1);
     231         [ +  - ]:        246 :         aligned_write4(pw + FREELIST_END - 4, UNUSED);
     232                 :            :     }
     233                 :            : 
     234         [ +  - ]:     141035 :     aligned_write4(pw + flw.c, blk);
     235                 :     141035 :     flw.c += 4;
     236                 :            : 
     237         [ -  + ]:     141035 :     if (blk_to_free != BLK_UNUSED)
     238         [ #  # ]:          0 :         mark_block_unused(B, block_size, blk_to_free);
     239                 :     141035 : }
     240                 :            : 
     241                 :            : void
     242                 :      45322 : GlassFreeList::commit(const GlassTable * B, uint4 block_size)
     243                 :            : {
     244 [ +  + ][ +  - ]:      45322 :     if (pw && flw.c != 0) {
     245                 :      16674 :         memset(pw + flw.c, 255, FREELIST_END - flw.c - 4);
     246                 :            : #ifdef GLASS_FREELIST_SIZE
     247                 :            :         if (block_size != FREELIST_END) {
     248                 :            :             memset(pw + FREELIST_END, 0xaa, block_size - FREELIST_END);
     249                 :            :         }
     250                 :            : #endif
     251                 :      16674 :         write_block(B, flw.n, pw, revision);
     252 [ +  + ][ +  + ]:      16674 :         if (p && flw.n == fl.n) {
     253                 :            :             // FIXME: share and refcount?
     254                 :      16077 :             memcpy(p, pw, block_size);
     255                 :            :             Assert(fl.n == fl_end.n || aligned_read4(p + FREELIST_END - 4) != UNUSED);
     256                 :            :         }
     257                 :      16674 :         flw_appending = true;
     258                 :      16674 :         fl_end = flw;
     259                 :            :     }
     260                 :      45322 : }
     261                 :            : 
     262                 :         98 : GlassFreeListChecker::GlassFreeListChecker(const GlassFreeList & fl)
     263                 :            : {
     264                 :         98 :     const unsigned BITS_PER_ELT = sizeof(elt_type) * 8;
     265                 :         98 :     const elt_type ALL_BITS = static_cast<elt_type>(-1);
     266                 :         98 :     uint4 first_unused = fl.get_first_unused_block();
     267                 :         98 :     bitmap_size = (first_unused + BITS_PER_ELT - 1) / BITS_PER_ELT;
     268 [ +  - ][ +  - ]:         98 :     bitmap = new elt_type[bitmap_size];
     269         [ +  - ]:         98 :     std::fill_n(bitmap, bitmap_size - 1, ALL_BITS);
     270                 :            :     // Only set the bits in the final element of bitmap which correspond to
     271                 :            :     // blocks < first_unused.
     272                 :         98 :     uint4 remainder = first_unused & (BITS_PER_ELT - 1);
     273         [ +  - ]:         98 :     if (remainder)
     274                 :         98 :         bitmap[bitmap_size - 1] = (static_cast<elt_type>(1) << remainder) - 1;
     275                 :            :     else
     276                 :          0 :         bitmap[bitmap_size - 1] = ALL_BITS;
     277                 :         98 : }
     278                 :            : 
     279                 :            : uint4
     280                 :         49 : GlassFreeListChecker::count_set_bits(uint4 * p_first_bad_blk) const
     281                 :            : {
     282                 :         49 :     const unsigned BITS_PER_ELT = sizeof(elt_type) * 8;
     283                 :         49 :     uint4 c = 0;
     284         [ +  + ]:         98 :     for (uint4 i = 0; i < bitmap_size; ++i) {
     285                 :         49 :         elt_type elt = bitmap[i];
     286         [ +  + ]:         49 :         if (usual(elt == 0))
     287                 :         29 :             continue;
     288 [ +  - ][ +  - ]:         20 :         if (c == 0 && p_first_bad_blk) {
     289                 :         20 :             uint4 first_bad_blk = i * BITS_PER_ELT;
     290                 :            :             if (false) {
     291                 :            : #if HAVE_DECL___BUILTIN_CTZ
     292                 :            :             } else if (sizeof(elt_type) == sizeof(unsigned)) {
     293                 :            :                 first_bad_blk += __builtin_ctz(elt);
     294                 :            : #endif
     295                 :            : #if HAVE_DECL___BUILTIN_CTZL
     296                 :            :             } else if (sizeof(elt_type) == sizeof(unsigned long)) {
     297                 :         20 :                 first_bad_blk += __builtin_ctzl(elt);
     298                 :            : #endif
     299                 :            : #if HAVE_DECL___BUILTIN_CTZLL
     300                 :            :             } else if (sizeof(elt_type) == sizeof(unsigned long long)) {
     301                 :            :                 first_bad_blk += __builtin_ctzll(elt);
     302                 :            : #endif
     303                 :            :             } else {
     304                 :            :                 for (elt_type mask = 1; (elt & mask) == 0; mask <<= 1) {
     305                 :            :                     ++first_bad_blk;
     306                 :            :                 }
     307                 :            :             }
     308                 :         20 :             *p_first_bad_blk = first_bad_blk;
     309                 :            :         }
     310                 :            : 
     311                 :            :         // Count set bits in elt.
     312                 :            :         if (false) {
     313                 :            : #if HAVE_DECL___BUILTIN_POPCOUNT
     314                 :            :         } else if (sizeof(elt_type) == sizeof(unsigned)) {
     315                 :            :             c += __builtin_popcount(elt);
     316                 :            : #elif HAVE_DECL___POPCNT
     317                 :            :         } else if (sizeof(elt_type) == sizeof(unsigned)) {
     318                 :            :             c += __popcnt(elt);
     319                 :            : #endif
     320                 :            : #if HAVE_DECL___BUILTIN_POPCOUNTL
     321                 :            :         } else if (sizeof(elt_type) == sizeof(unsigned long)) {
     322                 :         20 :             c += __builtin_popcountl(elt);
     323                 :            : #endif
     324                 :            : #if HAVE_DECL___BUILTIN_POPCOUNTLL
     325                 :            :         } else if (sizeof(elt_type) == sizeof(unsigned long long)) {
     326                 :            :             c += __builtin_popcountll(elt);
     327                 :            : #elif HAVE_DECL___POPCNT64
     328                 :            :         } else if (sizeof(elt_type) == sizeof(unsigned long long)) {
     329                 :            :             c += __popcnt64(elt);
     330                 :            : #endif
     331                 :            :         } else {
     332                 :            :             do {
     333                 :            :                 ++c;
     334                 :            :                 elt &= elt - 1;
     335                 :            :             } while (elt);
     336                 :            :         }
     337                 :            :     }
     338                 :         49 :     return c;
     339                 :            : }

Generated by: LCOV version 1.11