lkml.org 
[lkml]   [2023]   [Jan]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH v3 4/5] sbitmap: add sbitmap_find_bit to remove repeat code in __sbitmap_get/__sbitmap_get_shallow
    Date
    There are three differences between __sbitmap_get and
    __sbitmap_get_shallow when searching free bit:
    1. __sbitmap_get_shallow limit number of bit to search per word.
    __sbitmap_get has no such limit.
    2. __sbitmap_get_shallow always searches with wrap set. __sbitmap_get set
    wrap according to round_robin.
    3. __sbitmap_get_shallow always searches from first bit in first word.
    __sbitmap_get searches from first bit when round_robin is not set
    otherwise searches from SB_NR_TO_BIT(sb, alloc_hint).

    Add helper function sbitmap_find_bit function to do common search while
    accept "limit depth per word", "wrap flag" and "first bit to
    search" from caller to support the need of both __sbitmap_get and
    __sbitmap_get_shallow.

    Reviewed-by: Jan Kara <jack@suse.cz>
    Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>
    ---
    lib/sbitmap.c | 70 ++++++++++++++++++++++++---------------------------
    1 file changed, 33 insertions(+), 37 deletions(-)

    diff --git a/lib/sbitmap.c b/lib/sbitmap.c
    index 27cfcc35956e..2514e7a3f6ca 100644
    --- a/lib/sbitmap.c
    +++ b/lib/sbitmap.c
    @@ -186,27 +186,22 @@ static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
    return nr;
    }

    -static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)
    +static int sbitmap_find_bit(struct sbitmap *sb,
    + unsigned int depth,
    + unsigned int index,
    + unsigned int alloc_hint,
    + bool wrap)
    {
    - unsigned int i, index;
    + unsigned int i;
    int nr = -1;

    - index = SB_NR_TO_INDEX(sb, alloc_hint);
    -
    - /*
    - * Unless we're doing round robin tag allocation, just use the
    - * alloc_hint to find the right word index. No point in looping
    - * twice in find_next_zero_bit() for that case.
    - */
    - if (sb->round_robin)
    - alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
    - else
    - alloc_hint = 0;
    -
    for (i = 0; i < sb->map_nr; i++) {
    nr = sbitmap_find_bit_in_word(&sb->map[index],
    - __map_depth(sb, index),
    - alloc_hint, !sb->round_robin);
    + min_t(unsigned int,
    + __map_depth(sb, index),
    + depth),
    + alloc_hint, wrap);
    +
    if (nr != -1) {
    nr += index << sb->shift;
    break;
    @@ -221,6 +216,26 @@ static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)
    return nr;
    }

    +static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)
    +{
    + unsigned int index;
    +
    + index = SB_NR_TO_INDEX(sb, alloc_hint);
    +
    + /*
    + * Unless we're doing round robin tag allocation, just use the
    + * alloc_hint to find the right word index. No point in looping
    + * twice in find_next_zero_bit() for that case.
    + */
    + if (sb->round_robin)
    + alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
    + else
    + alloc_hint = 0;
    +
    + return sbitmap_find_bit(sb, UINT_MAX, index, alloc_hint,
    + !sb->round_robin);
    +}
    +
    int sbitmap_get(struct sbitmap *sb)
    {
    int nr;
    @@ -242,31 +257,12 @@ static int __sbitmap_get_shallow(struct sbitmap *sb,
    unsigned int alloc_hint,
    unsigned long shallow_depth)
    {
    - unsigned int i, index;
    - int nr = -1;
    + unsigned int index;

    index = SB_NR_TO_INDEX(sb, alloc_hint);
    alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);

    - for (i = 0; i < sb->map_nr; i++) {
    - nr = sbitmap_find_bit_in_word(&sb->map[index],
    - min_t(unsigned int,
    - __map_depth(sb, index),
    - shallow_depth),
    - alloc_hint, true);
    -
    - if (nr != -1) {
    - nr += index << sb->shift;
    - break;
    - }
    -
    - /* Jump to next index. */
    - alloc_hint = 0;
    - if (++index >= sb->map_nr)
    - index = 0;
    - }
    -
    - return nr;
    + return sbitmap_find_bit(sb, shallow_depth, index, alloc_hint, true);
    }

    int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth)
    --
    2.30.0
    \
     
     \ /
      Last update: 2023-03-26 23:42    [W:4.184 / U:0.004 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site