Line data    Source code

       1             : /*   SPDX-License-Identifier: BSD-3-Clause
       2             :  *   Copyright (C) 2022 Intel Corporation.
       3             :  *   All rights reserved.
       4             :  */
       5             : 
       6             : #include "spdk/log.h"
       7             : #include "spdk/util.h"
       8             : 
       9             : #include "ftl_bitmap.h"
      10             : #include "ftl_internal.h"
      11             : 
      12             : typedef unsigned long bitmap_word;
      13             : 
      14             : const size_t ftl_bitmap_buffer_alignment = sizeof(bitmap_word);
      15             : 
      16             : #define FTL_BITMAP_WORD_SHIFT   spdk_u32log2(sizeof(bitmap_word) * 8)
      17             : #define FTL_BITMAP_WORD_MASK    (~(~0UL << FTL_BITMAP_WORD_SHIFT))
      18             : 
      19             : uint64_t
      20           0 : ftl_bitmap_bits_to_size(uint64_t bits)
      21             : {
      22           0 :         uint64_t size;
      23             : 
      24           0 :         if (bits < ftl_bitmap_buffer_alignment) {
      25           0 :                 bits = ftl_bitmap_buffer_alignment;
      26           0 :         }
      27             : 
      28           0 :         size = spdk_divide_round_up(bits, 8);
      29           0 :         size = spdk_divide_round_up(size, ftl_bitmap_buffer_alignment) * ftl_bitmap_buffer_alignment;
      30             : 
      31           0 :         return size;
      32           0 : }
      33             : 
      34             : uint64_t
      35           0 : ftl_bitmap_bits_to_blocks(uint64_t bits)
      36             : {
      37           0 :         uint64_t size = ftl_bitmap_bits_to_size(bits);
      38             : 
      39           0 :         return spdk_divide_round_up(size, FTL_BLOCK_SIZE);
      40           0 : }
      41             : 
      42             : struct ftl_bitmap {
      43             :         bitmap_word *buf;
      44             :         size_t size;
      45             : };
      46             : 
      47           3 : struct ftl_bitmap *ftl_bitmap_create(void *buf, size_t size)
      48             : {
      49           3 :         struct ftl_bitmap *bitmap;
      50             : 
      51           3 :         if ((uintptr_t)buf % ftl_bitmap_buffer_alignment) {
      52           1 :                 SPDK_ERRLOG("Buffer for bitmap must be aligned to %lu bytes\n",
      53             :                             ftl_bitmap_buffer_alignment);
      54           1 :                 return NULL;
      55             :         }
      56             : 
      57           2 :         if (size % ftl_bitmap_buffer_alignment) {
      58           1 :                 SPDK_ERRLOG("Size of buffer for bitmap must be divisible by %lu bytes\n",
      59             :                             ftl_bitmap_buffer_alignment);
      60           1 :                 return NULL;
      61             :         }
      62             : 
      63           1 :         bitmap = calloc(1, sizeof(*bitmap));
      64           1 :         if (!bitmap) {
      65           0 :                 return NULL;
      66             :         }
      67             : 
      68           1 :         bitmap->buf = buf;
      69           1 :         bitmap->size = size / sizeof(bitmap_word);
      70             : 
      71           1 :         return bitmap;
      72           3 : }
      73             : 
      74             : void
      75           0 : ftl_bitmap_destroy(struct ftl_bitmap *bitmap)
      76             : {
      77           0 :         free(bitmap);
      78           0 : }
      79             : 
      80             : static inline void
      81        2128 : locate_bit(const struct ftl_bitmap *bitmap, uint64_t bit,
      82             :            bitmap_word **word_out, uint8_t *word_bit_idx_out)
      83             : {
      84        2128 :         size_t word_idx = bit >> FTL_BITMAP_WORD_SHIFT;
      85             : 
      86        2128 :         assert(word_idx < bitmap->size);
      87             : 
      88        2128 :         *word_bit_idx_out = bit & FTL_BITMAP_WORD_MASK;
      89        2128 :         *word_out = &bitmap->buf[word_idx];
      90        2128 : }
      91             : 
      92             : bool
      93        2078 : ftl_bitmap_get(const struct ftl_bitmap *bitmap, uint64_t bit)
      94             : {
      95        2078 :         bitmap_word *word;
      96        2078 :         uint8_t word_bit_idx;
      97             : 
      98        2078 :         locate_bit(bitmap, bit, &word, &word_bit_idx);
      99             : 
     100        2078 :         return *word & (1UL << word_bit_idx);
     101        2078 : }
     102             : 
     103             : void
     104          30 : ftl_bitmap_set(struct ftl_bitmap *bitmap, uint64_t bit)
     105             : {
     106          30 :         bitmap_word *word;
     107          30 :         uint8_t word_bit_idx;
     108             : 
     109          30 :         locate_bit(bitmap, bit, &word, &word_bit_idx);
     110             : 
     111          30 :         *word |= (1UL << word_bit_idx);
     112          30 : }
     113             : 
     114             : void
     115          20 : ftl_bitmap_clear(struct ftl_bitmap *bitmap, uint64_t bit)
     116             : {
     117          20 :         bitmap_word *word;
     118          20 :         uint8_t word_bit_idx;
     119             : 
     120          20 :         locate_bit(bitmap, bit, &word, &word_bit_idx);
     121             : 
     122          20 :         *word &= ~(1UL << word_bit_idx);
     123          20 : }
     124             : 
     125             : static uint64_t
     126         100 : ftl_bitmap_find_first(struct ftl_bitmap *bitmap, uint64_t start_bit,
     127             :                       uint64_t end_bit, bool value)
     128             : {
     129         100 :         bitmap_word skip = (value ? 0 : ~0UL);
     130         100 :         bitmap_word word;
     131         100 :         size_t i, end;
     132         100 :         uint64_t ret;
     133             : 
     134         100 :         assert(start_bit <= end_bit);
     135             : 
     136         100 :         i = start_bit >> FTL_BITMAP_WORD_SHIFT;
     137         100 :         assert(i < bitmap->size);
     138             : 
     139         100 :         word = (bitmap->buf[i] ^ skip) & (~0UL << (start_bit & FTL_BITMAP_WORD_MASK));
     140         100 :         if (word != 0) {
     141          74 :                 goto found;
     142             :         }
     143             : 
     144          26 :         end = spdk_min((end_bit >> FTL_BITMAP_WORD_SHIFT) + 1, bitmap->size);
     145         136 :         for (i = i + 1; i < end; i++) {
     146         134 :                 word = bitmap->buf[i] ^ skip;
     147         134 :                 if (word != 0) {
     148          24 :                         goto found;
     149             :                 }
     150         110 :         }
     151             : 
     152           2 :         return UINT64_MAX;
     153             : found:
     154          98 :         ret = (i << FTL_BITMAP_WORD_SHIFT) + __builtin_ctzl(word);
     155          98 :         if (ret > end_bit) {
     156          18 :                 return UINT64_MAX;
     157             :         }
     158          80 :         return ret;
     159         100 : }
     160             : 
     161             : uint64_t
     162          50 : ftl_bitmap_find_first_set(struct ftl_bitmap *bitmap, uint64_t start_bit, uint64_t end_bit)
     163             : {
     164          50 :         return ftl_bitmap_find_first(bitmap, start_bit, end_bit, true);
     165             : }
     166             : 
     167             : uint64_t
     168          50 : ftl_bitmap_find_first_clear(struct ftl_bitmap *bitmap, uint64_t start_bit,
     169             :                             uint64_t end_bit)
     170             : {
     171          50 :         return ftl_bitmap_find_first(bitmap, start_bit, end_bit, false);
     172             : }
     173             : 
     174             : uint64_t
     175           2 : ftl_bitmap_count_set(struct ftl_bitmap *bitmap)
     176             : {
     177           2 :         size_t i;
     178           2 :         bitmap_word *word = bitmap->buf;
     179           2 :         uint64_t count = 0;
     180             : 
     181          18 :         for (i = 0; i < bitmap->size; i++, word++) {
     182          16 :                 count += __builtin_popcountl(*word);
     183          16 :         }
     184             : 
     185           4 :         return count;
     186           2 : }