Line data    Source code

       1             : #include "clusterautoconfig.h"
       2             : 
       3             : #include <inttypes.h>
       4             : #include <stdlib.h>
       5             : #include <string.h>
       6             : #include <unistd.h>
       7             : #include <limits.h>
       8             : 
       9             : #include "libgfs2.h"
      10             : 
      11             : #if BITS_PER_LONG == 32
      12             : #define LBITMASK   (0x55555555UL)
      13             : #define LBITSKIP55 (0x55555555UL)
      14             : #define LBITSKIP00 (0x00000000UL)
      15             : #else
      16             : #define LBITMASK   (0x5555555555555555UL)
      17             : #define LBITSKIP55 (0x5555555555555555UL)
      18             : #define LBITSKIP00 (0x0000000000000000UL)
      19             : #endif
      20             : 
      21             : #define ALIGN(x,a) (((x)+(a)-1)&~((a)-1))
      22             : 
      23             : /**
      24             :  * bit_search
      25             :  * @ptr: Pointer to bitmap data
      26             :  * @mask: Mask to use (normally 0x55555.... but adjusted for search start)
      27             :  * @state: The state we are searching for
      28             :  *
      29             :  * We xor the bitmap data with a patter which is the bitwise opposite
      30             :  * of what we are looking for, this gives rise to a pattern of ones
      31             :  * wherever there is a match. Since we have two bits per entry, we
      32             :  * take this pattern, shift it down by one place and then and it with
      33             :  * the original. All the even bit positions (0,2,4, etc) then represent
      34             :  * successful matches, so we mask with 0x55555..... to remove the unwanted
      35             :  * odd bit positions.
      36             :  *
      37             :  * This allows searching of a whole u64 at once (32 blocks) with a
      38             :  * single test (on 64 bit arches).
      39             :  */
      40             : 
      41    38698224 : static inline uint64_t bit_search(const __le64 *ptr,
      42             :                                        unsigned long long mask,
      43             :                                        uint8_t state)
      44             : {
      45             :         unsigned long long tmp;
      46             :         static const unsigned long long search[] = {
      47             :                 [0] = 0xffffffffffffffffULL,
      48             :                 [1] = 0xaaaaaaaaaaaaaaaaULL,
      49             :                 [2] = 0x5555555555555555ULL,
      50             :                 [3] = 0x0000000000000000ULL,
      51             :         };
      52    38698224 :         tmp = le64_to_cpu(*ptr) ^ search[state];
      53    38698224 :         tmp &= (tmp >> 1);
      54    38698224 :         tmp &= mask;
      55    38698224 :         return tmp;
      56             : }
      57             : 
      58             : /**
      59             :  * lgfs2_bitfit - Find a free block in the bitmaps
      60             :  * @buffer: the buffer that holds the bitmaps
      61             :  * @buflen: the length (in bytes) of the buffer
      62             :  * @goal: the block to try to allocate
      63             :  * @old_state: the state of the block we're looking for
      64             :  *
      65             :  * Return: the block number that was allocated
      66             :  */
      67      320198 : unsigned long lgfs2_bitfit(const unsigned char *buf, const unsigned int len,
      68             :                           unsigned long goal, unsigned char state)
      69             : {
      70      320198 :         uint32_t spoint = (goal << 1) & ((8 * sizeof(uint64_t)) - 1);
      71      320198 :         const __le64 *ptr = ((__le64 *)buf) + (goal >> 5);
      72      320198 :         const __le64 *end = (__le64 *) (buf + ALIGN(len, sizeof(uint64_t)));
      73             :         uint64_t tmp;
      74      320198 :         uint64_t mask = 0x5555555555555555ULL;
      75             :         uint32_t bit;
      76             : 
      77      320198 :         if (state > 3)
      78           0 :                 return 0;
      79             : 
      80             :         /* Mask off bits we don't care about at the start of the search */
      81      320198 :         mask <<= spoint;
      82      320198 :         tmp = bit_search(ptr, mask, state);
      83      320198 :         ptr++;
      84    38698224 :         while(tmp == 0 && ptr < end) {
      85    38378026 :                 tmp = bit_search(ptr, 0x5555555555555555ULL, state);
      86    38378026 :                 ptr++;
      87             :         }
      88             :         /* Mask off any bits which are more than len bytes from the start */
      89      320198 :         if (ptr == end && (len & (sizeof(uint64_t) - 1)))
      90        1794 :                 tmp &= (((uint64_t)~0) >>
      91        1794 :                         (64 - 8 * (len & (sizeof(uint64_t) - 1))));
      92             :         /* Didn't find anything, so return */
      93      320198 :         if (tmp == 0)
      94      223018 :                 return LGFS2_BFITNOENT;
      95       97180 :         ptr--;
      96       97180 :         bit = ffsll(tmp);
      97       97180 :         bit /= 2;       /* two bits per entry in the bitmap */
      98       97180 :         return (((const unsigned char *)ptr - buf) * GFS2_NBBY) + bit;
      99             : }
     100             : 
     101             : /*
     102             :  * lgfs2_check_range - check if blkno is within FS limits
     103             :  * @sdp: super block
     104             :  * @blkno: block number
     105             :  *
     106             :  * Returns: 0 if ok, -1 if out of bounds
     107             :  */
     108     2170736 : int lgfs2_check_range(struct lgfs2_sbd *sdp, uint64_t blkno)
     109             : {
     110     2170736 :         if((blkno > sdp->fssize) || (blkno <= LGFS2_SB_ADDR(sdp)))
     111           6 :                 return -1;
     112     2170730 :         return 0;
     113             : }
     114             : 
     115             : /*
     116             :  * lgfs2_set_bitmap
     117             :  * @sdp: super block
     118             :  * @blkno: block number relative to file system
     119             :  * @state: one of three possible states
     120             :  *
     121             :  * This function sets the value of a bit of the
     122             :  * file system bitmap.
     123             :  *
     124             :  * Returns: 0 on success, -1 on error
     125             :  */
     126     2495706 : int lgfs2_set_bitmap(lgfs2_rgrp_t rgd, uint64_t blkno, int state)
     127             : {
     128             :         int           buf;
     129             :         uint32_t        rgrp_block;
     130     2495706 :         struct lgfs2_bitmap *bits = NULL;
     131             :         unsigned char *byte, cur_state;
     132             :         unsigned int bit;
     133             : 
     134             :         /* FIXME: should GFS2_BLKST_INVALID be allowed */
     135     2495706 :         if ((state < GFS2_BLKST_FREE) || (state > GFS2_BLKST_DINODE))
     136           0 :                 return -1;
     137             : 
     138     2495706 :         if(!rgd || blkno < rgd->rt_data0)
     139           0 :                 return -1;
     140             : 
     141     2495706 :         rgrp_block = (uint32_t)(blkno - rgd->rt_data0);
     142     7176118 :         for(buf= 0; buf < rgd->rt_length; buf++){
     143     7176118 :                 bits = &(rgd->rt_bits[buf]);
     144     7176118 :                 if(rgrp_block < ((bits->bi_start + bits->bi_len)*GFS2_NBBY))
     145     2495706 :                         break;
     146             :         }
     147             : 
     148     2495706 :         if (bits == NULL)
     149           0 :                 return -1;
     150     2495706 :         byte = (unsigned char *)(bits->bi_data + bits->bi_offset) +
     151     2495706 :                 (rgrp_block/GFS2_NBBY - bits->bi_start);
     152     2495706 :         bit = (rgrp_block % GFS2_NBBY) * GFS2_BIT_SIZE;
     153             : 
     154     2495706 :         cur_state = (*byte >> bit) & GFS2_BIT_MASK;
     155     2495706 :         *byte ^= cur_state << bit;
     156     2495706 :         *byte |= state << bit;
     157             : 
     158     2495706 :         bits->bi_modified = 1;
     159     2495706 :         return 0;
     160             : }
     161             : 
     162             : /*
     163             :  * lgfs2_get_bitmap - get value of FS bitmap
     164             :  * @sdp: super block
     165             :  * @blkno: block number relative to file system
     166             :  *
     167             :  * This function gets the value of a bit of the
     168             :  * file system bitmap.
     169             :  * Possible state values for a block in the bitmap are:
     170             :  *  GFS_BLKST_FREE     (0)
     171             :  *  GFS_BLKST_USED     (1)
     172             :  *  GFS_BLKST_INVALID  (2)
     173             :  *  GFS_BLKST_DINODE   (3)
     174             :  *
     175             :  * Returns: state on success, -1 on error
     176             :  */
     177     1968110 : int lgfs2_get_bitmap(struct lgfs2_sbd *sdp, uint64_t blkno, struct lgfs2_rgrp_tree *rgd)
     178             : {
     179             :         uint64_t offset;
     180     1968110 :         uint32_t i = 0;
     181             :         char *byte;
     182             :         unsigned int bit;
     183             :         struct lgfs2_bitmap *bi;
     184             : 
     185     1968110 :         if (rgd == NULL) {
     186           2 :                 rgd = lgfs2_blk2rgrpd(sdp, blkno);
     187           2 :                 if(rgd == NULL)
     188           0 :                         return -1;
     189             :         }
     190             : 
     191     1968110 :         offset = blkno - rgd->rt_data0;
     192     1968110 :         if (offset > UINT_MAX) {
     193           0 :                 errno = EINVAL;
     194           0 :                 return -1;
     195             :         }
     196     1968110 :         if (offset >= rgd->rt_data0 + rgd->rt_data) {
     197           0 :                 errno = E2BIG;
     198           0 :                 return -1;
     199             :         }
     200             : 
     201     1968110 :         if (offset >= ((uint64_t)rgd->rt_bits->bi_start + rgd->rt_bits->bi_len) * GFS2_NBBY) {
     202     1200911 :                 offset += (sizeof(struct gfs2_rgrp) - sizeof(struct gfs2_meta_header))
     203             :                           * GFS2_NBBY;
     204     1200911 :                 i = offset / sdp->sd_blocks_per_bitmap;
     205     1200911 :                 offset -= (uint64_t)i * sdp->sd_blocks_per_bitmap;
     206             :         }
     207             : 
     208     1968110 :         bi = &rgd->rt_bits[i];
     209     1968110 :         if (bi->bi_data == NULL)
     210           0 :                 return GFS2_BLKST_FREE;
     211             : 
     212     1968110 :         byte = (bi->bi_data + bi->bi_offset) + (offset/GFS2_NBBY);
     213     1968110 :         bit = (offset % GFS2_NBBY) * GFS2_BIT_SIZE;
     214             : 
     215     1968110 :         return (*byte >> bit) & GFS2_BIT_MASK;
     216             : }