// SPDX-License-Identifier: GPL-2.0-only
/*
 * balloc.c
 *
 * PURPOSE
 *      Block allocation handling routines for the OSTA-UDF(tm) filesystem.
 *
 * COPYRIGHT
 *  (C) 1999-2001 Ben Fennema
 *  (C) 1999 Stelias Computing Inc
 *
 * HISTORY
 *
 *  02/24/99 blf  Created.
 *
 */

#include "udfdecl.h"

#include <linux/bitops.h>
#include <linux/overflow.h>

#include "udf_i.h"
#include "udf_sb.h"

#define udf_clear_bit   __test_and_clear_bit_le
#define udf_set_bit     __test_and_set_bit_le
#define udf_test_bit    test_bit_le
#define udf_find_next_one_bit   find_next_bit_le

static int read_block_bitmap(struct super_block *sb,
                             struct udf_bitmap *bitmap, unsigned int block,
                             unsigned long bitmap_nr)
{
        struct buffer_head *bh = NULL;
        int i;
        int max_bits, off, count;
        struct kernel_lb_addr loc;

        loc.logicalBlockNum = bitmap->s_extPosition;
        loc.partitionReferenceNum = UDF_SB(sb)->s_partition;

        bh = sb_bread(sb, udf_get_lb_pblock(sb, &loc, block));
        bitmap->s_block_bitmap[bitmap_nr] = bh;
        if (!bh)
                return -EIO;

        /* Check consistency of Space Bitmap buffer. */
        max_bits = sb->s_blocksize * 8;
        if (!bitmap_nr) {
                off = sizeof(struct spaceBitmapDesc) << 3;
                count = min(max_bits - off, bitmap->s_nr_groups);
        } else {
                /*
                 * Rough check if bitmap number is too big to have any bitmap
                 * blocks reserved.
                 */
                if (bitmap_nr >
                    (bitmap->s_nr_groups >> (sb->s_blocksize_bits + 3)) + 2)
                        return 0;
                off = 0;
                count = bitmap->s_nr_groups - bitmap_nr * max_bits +
                                (sizeof(struct spaceBitmapDesc) << 3);
                count = min(count, max_bits);
        }

        for (i = 0; i < count; i++)
                if (udf_test_bit(i + off, bh->b_data)) {
                        bitmap->s_block_bitmap[bitmap_nr] =
                                                        ERR_PTR(-EFSCORRUPTED);
                        brelse(bh);
                        return -EFSCORRUPTED;
                }
        return 0;
}

static int load_block_bitmap(struct super_block *sb,
                             struct udf_bitmap *bitmap,
                             unsigned int block_group)
{
        int retval = 0;
        int nr_groups = bitmap->s_nr_groups;

        if (block_group >= nr_groups) {
                udf_debug("block_group (%u) > nr_groups (%d)\n",
                          block_group, nr_groups);
        }

        if (bitmap->s_block_bitmap[block_group]) {
                /*
                 * The bitmap failed verification in the past. No point in
                 * trying again.
                 */
                if (IS_ERR(bitmap->s_block_bitmap[block_group]))
                        return PTR_ERR(bitmap->s_block_bitmap[block_group]);
                return block_group;
        }

        retval = read_block_bitmap(sb, bitmap, block_group, block_group);
        if (retval < 0)
                return retval;

        return block_group;
}

static void udf_add_free_space(struct super_block *sb, u16 partition, u32 cnt)
{
        struct udf_sb_info *sbi = UDF_SB(sb);
        struct logicalVolIntegrityDesc *lvid;

        if (!sbi->s_lvid_bh)
                return;

        lvid = (struct logicalVolIntegrityDesc *)sbi->s_lvid_bh->b_data;
        le32_add_cpu(&lvid->freeSpaceTable[partition], cnt);
        udf_updated_lvid(sb);
}

static void udf_bitmap_free_blocks(struct super_block *sb,
                                   struct udf_bitmap *bitmap,
                                   struct kernel_lb_addr *bloc,
                                   uint32_t offset,
                                   uint32_t count)
{
        struct udf_sb_info *sbi = UDF_SB(sb);
        struct buffer_head *bh = NULL;
        unsigned long block;
        unsigned long block_group;
        unsigned long bit;
        unsigned long i;
        int bitmap_nr;
        unsigned long overflow;

        mutex_lock(&sbi->s_alloc_mutex);
        /* We make sure this cannot overflow when mounting the filesystem */
        block = bloc->logicalBlockNum + offset +
                (sizeof(struct spaceBitmapDesc) << 3);
        do {
                overflow = 0;
                block_group = block >> (sb->s_blocksize_bits + 3);
                bit = block % (sb->s_blocksize << 3);

                /*
                * Check to see if we are freeing blocks across a group boundary.
                */
                if (bit + count > (sb->s_blocksize << 3)) {
                        overflow = bit + count - (sb->s_blocksize << 3);
                        count -= overflow;
                }
                bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
                if (bitmap_nr < 0)
                        goto error_return;

                bh = bitmap->s_block_bitmap[bitmap_nr];
                for (i = 0; i < count; i++) {
                        if (udf_set_bit(bit + i, bh->b_data)) {
                                udf_debug("bit %lu already set\n", bit + i);
                                udf_debug("byte=%2x\n",
                                          ((__u8 *)bh->b_data)[(bit + i) >> 3]);
                        }
                }
                udf_add_free_space(sb, sbi->s_partition, count);
                mark_buffer_dirty(bh);
                if (overflow) {
                        block += count;
                        count = overflow;
                }
        } while (overflow);

error_return:
        mutex_unlock(&sbi->s_alloc_mutex);
}

static int udf_bitmap_prealloc_blocks(struct super_block *sb,
                                      struct udf_bitmap *bitmap,
                                      uint16_t partition, uint32_t first_block,
                                      uint32_t block_count)
{
        struct udf_sb_info *sbi = UDF_SB(sb);
        int alloc_count = 0;
        int bit, block, block_group;
        int bitmap_nr;
        struct buffer_head *bh;
        __u32 part_len;

        mutex_lock(&sbi->s_alloc_mutex);
        part_len = sbi->s_partmaps[partition].s_partition_len;
        if (first_block >= part_len)
                goto out;

        if (first_block + block_count > part_len)
                block_count = part_len - first_block;

        do {
                block = first_block + (sizeof(struct spaceBitmapDesc) << 3);
                block_group = block >> (sb->s_blocksize_bits + 3);

                bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
                if (bitmap_nr < 0)
                        goto out;
                bh = bitmap->s_block_bitmap[bitmap_nr];

                bit = block % (sb->s_blocksize << 3);

                while (bit < (sb->s_blocksize << 3) && block_count > 0) {
                        if (!udf_clear_bit(bit, bh->b_data))
                                goto out;
                        block_count--;
                        alloc_count++;
                        bit++;
                        block++;
                }
                mark_buffer_dirty(bh);
        } while (block_count > 0);

out:
        udf_add_free_space(sb, partition, -alloc_count);
        mutex_unlock(&sbi->s_alloc_mutex);
        return alloc_count;
}

static udf_pblk_t udf_bitmap_new_block(struct super_block *sb,
                                struct udf_bitmap *bitmap, uint16_t partition,
                                uint32_t goal, int *err)
{
        struct udf_sb_info *sbi = UDF_SB(sb);
        int newbit, bit = 0;
        udf_pblk_t block;
        int block_group, group_start;
        int end_goal, nr_groups, bitmap_nr, i;
        struct buffer_head *bh = NULL;
        char *ptr;
        udf_pblk_t newblock = 0;

        *err = -ENOSPC;
        mutex_lock(&sbi->s_alloc_mutex);

repeat:
        if (goal >= sbi->s_partmaps[partition].s_partition_len)
                goal = 0;

        nr_groups = bitmap->s_nr_groups;
        block = goal + (sizeof(struct spaceBitmapDesc) << 3);
        block_group = block >> (sb->s_blocksize_bits + 3);
        group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc);

        bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
        if (bitmap_nr < 0)
                goto error_return;
        bh = bitmap->s_block_bitmap[bitmap_nr];
        ptr = memscan((char *)bh->b_data + group_start, 0xFF,
                      sb->s_blocksize - group_start);

        if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) {
                bit = block % (sb->s_blocksize << 3);
                if (udf_test_bit(bit, bh->b_data))
                        goto got_block;

                end_goal = (bit + 63) & ~63;
                bit = udf_find_next_one_bit(bh->b_data, end_goal, bit);
                if (bit < end_goal)
                        goto got_block;

                ptr = memscan((char *)bh->b_data + (bit >> 3), 0xFF,
                              sb->s_blocksize - ((bit + 7) >> 3));
                newbit = (ptr - ((char *)bh->b_data)) << 3;
                if (newbit < sb->s_blocksize << 3) {
                        bit = newbit;
                        goto search_back;
                }

                newbit = udf_find_next_one_bit(bh->b_data,
                                               sb->s_blocksize << 3, bit);
                if (newbit < sb->s_blocksize << 3) {
                        bit = newbit;
                        goto got_block;
                }
        }

        for (i = 0; i < (nr_groups * 2); i++) {
                block_group++;
                if (block_group >= nr_groups)
                        block_group = 0;
                group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc);

                bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
                if (bitmap_nr < 0)
                        goto error_return;
                bh = bitmap->s_block_bitmap[bitmap_nr];
                if (i < nr_groups) {
                        ptr = memscan((char *)bh->b_data + group_start, 0xFF,
                                      sb->s_blocksize - group_start);
                        if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) {
                                bit = (ptr - ((char *)bh->b_data)) << 3;
                                break;
                        }
                } else {
                        bit = udf_find_next_one_bit(bh->b_data,
                                                    sb->s_blocksize << 3,
                                                    group_start << 3);
                        if (bit < sb->s_blocksize << 3)
                                break;
                }
        }
        if (i >= (nr_groups * 2)) {
                mutex_unlock(&sbi->s_alloc_mutex);
                return newblock;
        }
        if (bit < sb->s_blocksize << 3)
                goto search_back;
        else
                bit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3,
                                            group_start << 3);
        if (bit >= sb->s_blocksize << 3) {
                mutex_unlock(&sbi->s_alloc_mutex);
                return 0;
        }

search_back:
        i = 0;
        while (i < 7 && bit > (group_start << 3) &&
               udf_test_bit(bit - 1, bh->b_data)) {
                ++i;
                --bit;
        }

got_block:
        newblock = bit + (block_group << (sb->s_blocksize_bits + 3)) -
                (sizeof(struct spaceBitmapDesc) << 3);

        if (newblock >= sbi->s_partmaps[partition].s_partition_len) {
                /*
                 * Ran off the end of the bitmap, and bits following are
                 * non-compliant (not all zero)
                 */
                udf_err(sb, "bitmap for partition %d corrupted (block %u marked"
                        " as free, partition length is %u)\n", partition,
                        newblock, sbi->s_partmaps[partition].s_partition_len);
                goto error_return;
        }

        if (!udf_clear_bit(bit, bh->b_data)) {
                udf_debug("bit already cleared for block %d\n", bit);
                goto repeat;
        }

        mark_buffer_dirty(bh);

        udf_add_free_space(sb, partition, -1);
        mutex_unlock(&sbi->s_alloc_mutex);
        *err = 0;
        return newblock;

error_return:
        *err = -EIO;
        mutex_unlock(&sbi->s_alloc_mutex);
        return 0;
}

static void udf_table_free_blocks(struct super_block *sb,
                                  struct inode *table,
                                  struct kernel_lb_addr *bloc,
                                  uint32_t offset,
                                  uint32_t count)
{
        struct udf_sb_info *sbi = UDF_SB(sb);
        uint32_t start, end;
        uint32_t elen;
        struct kernel_lb_addr eloc;
        struct extent_position oepos, epos;
        int8_t etype;
        struct udf_inode_info *iinfo;
        int ret = 0;

        mutex_lock(&sbi->s_alloc_mutex);
        iinfo = UDF_I(table);
        udf_add_free_space(sb, sbi->s_partition, count);

        start = bloc->logicalBlockNum + offset;
        end = bloc->logicalBlockNum + offset + count - 1;

        epos.offset = oepos.offset = sizeof(struct unallocSpaceEntry);
        elen = 0;
        epos.block = oepos.block = iinfo->i_location;
        epos.bh = oepos.bh = NULL;

        while (count) {
                ret = udf_next_aext(table, &epos, &eloc, &elen, &etype, 1);
                if (ret < 0)
                        goto error_return;
                if (ret == 0)
                        break;
                if (((eloc.logicalBlockNum +
                        (elen >> sb->s_blocksize_bits)) == start)) {
                        if ((0x3FFFFFFF - elen) <
                                        (count << sb->s_blocksize_bits)) {
                                uint32_t tmp = ((0x3FFFFFFF - elen) >>
                                                        sb->s_blocksize_bits);
                                count -= tmp;
                                start += tmp;
                                elen = (etype << 30) |
                                        (0x40000000 - sb->s_blocksize);
                        } else {
                                elen = (etype << 30) |
                                        (elen +
                                        (count << sb->s_blocksize_bits));
                                start += count;
                                count = 0;
                        }
                        udf_write_aext(table, &oepos, &eloc, elen, 1);
                } else if (eloc.logicalBlockNum == (end + 1)) {
                        if ((0x3FFFFFFF - elen) <
                                        (count << sb->s_blocksize_bits)) {
                                uint32_t tmp = ((0x3FFFFFFF - elen) >>
                                                sb->s_blocksize_bits);
                                count -= tmp;
                                end -= tmp;
                                eloc.logicalBlockNum -= tmp;
                                elen = (etype << 30) |
                                        (0x40000000 - sb->s_blocksize);
                        } else {
                                eloc.logicalBlockNum = start;
                                elen = (etype << 30) |
                                        (elen +
                                        (count << sb->s_blocksize_bits));
                                end -= count;
                                count = 0;
                        }
                        udf_write_aext(table, &oepos, &eloc, elen, 1);
                }

                if (epos.bh != oepos.bh) {
                        oepos.block = epos.block;
                        brelse(oepos.bh);
                        get_bh(epos.bh);
                        oepos.bh = epos.bh;
                        oepos.offset = 0;
                } else {
                        oepos.offset = epos.offset;
                }
        }

        if (count) {
                /*
                 * NOTE: we CANNOT use udf_add_aext here, as it can try to
                 * allocate a new block, and since we hold the super block
                 * lock already very bad things would happen :)
                 *
                 * We copy the behavior of udf_add_aext, but instead of
                 * trying to allocate a new block close to the existing one,
                 * we just steal a block from the extent we are trying to add.
                 *
                 * It would be nice if the blocks were close together, but it
                 * isn't required.
                 */

                int adsize;

                eloc.logicalBlockNum = start;
                elen = EXT_RECORDED_ALLOCATED |
                        (count << sb->s_blocksize_bits);

                if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT)
                        adsize = sizeof(struct short_ad);
                else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG)
                        adsize = sizeof(struct long_ad);
                else
                        goto error_return;

                if (epos.offset + (2 * adsize) > sb->s_blocksize) {
                        /* Steal a block from the extent being free'd */
                        udf_setup_indirect_aext(table, eloc.logicalBlockNum,
                                                &epos);

                        eloc.logicalBlockNum++;
                        elen -= sb->s_blocksize;
                }

                /* It's possible that stealing the block emptied the extent */
                if (elen)
                        __udf_add_aext(table, &epos, &eloc, elen, 1);
        }

error_return:
        brelse(epos.bh);
        brelse(oepos.bh);

        mutex_unlock(&sbi->s_alloc_mutex);
        return;
}

static int udf_table_prealloc_blocks(struct super_block *sb,
                                     struct inode *table, uint16_t partition,
                                     uint32_t first_block, uint32_t block_count)
{
        struct udf_sb_info *sbi = UDF_SB(sb);
        int alloc_count = 0;
        uint32_t elen, adsize;
        struct kernel_lb_addr eloc;
        struct extent_position epos;
        int8_t etype = -1;
        struct udf_inode_info *iinfo;
        int ret = 0;

        if (first_block >= sbi->s_partmaps[partition].s_partition_len)
                return 0;

        iinfo = UDF_I(table);
        if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT)
                adsize = sizeof(struct short_ad);
        else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG)
                adsize = sizeof(struct long_ad);
        else
                return 0;

        mutex_lock(&sbi->s_alloc_mutex);
        epos.offset = sizeof(struct unallocSpaceEntry);
        epos.block = iinfo->i_location;
        epos.bh = NULL;
        eloc.logicalBlockNum = 0xFFFFFFFF;

        while (first_block != eloc.logicalBlockNum) {
                ret = udf_next_aext(table, &epos, &eloc, &elen, &etype, 1);
                if (ret < 0)
                        goto err_out;
                if (ret == 0)
                        break;
                udf_debug("eloc=%u, elen=%u, first_block=%u\n",
                          eloc.logicalBlockNum, elen, first_block);
        }

        if (first_block == eloc.logicalBlockNum) {
                epos.offset -= adsize;

                alloc_count = (elen >> sb->s_blocksize_bits);
                if (alloc_count > block_count) {
                        alloc_count = block_count;
                        eloc.logicalBlockNum += alloc_count;
                        elen -= (alloc_count << sb->s_blocksize_bits);
                        udf_write_aext(table, &epos, &eloc,
                                        (etype << 30) | elen, 1);
                } else
                        udf_delete_aext(table, epos);
        } else {
                alloc_count = 0;
        }

err_out:
        brelse(epos.bh);

        if (alloc_count)
                udf_add_free_space(sb, partition, -alloc_count);
        mutex_unlock(&sbi->s_alloc_mutex);
        return alloc_count;
}

static udf_pblk_t udf_table_new_block(struct super_block *sb,
                               struct inode *table, uint16_t partition,
                               uint32_t goal, int *err)
{
        struct udf_sb_info *sbi = UDF_SB(sb);
        uint32_t spread = 0xFFFFFFFF, nspread = 0xFFFFFFFF;
        udf_pblk_t newblock = 0;
        uint32_t adsize;
        uint32_t elen, goal_elen = 0;
        struct kernel_lb_addr eloc, goal_eloc;
        struct extent_position epos, goal_epos;
        int8_t etype;
        struct udf_inode_info *iinfo = UDF_I(table);
        int ret = 0;

        *err = -ENOSPC;

        if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT)
                adsize = sizeof(struct short_ad);
        else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG)
                adsize = sizeof(struct long_ad);
        else
                return newblock;

        mutex_lock(&sbi->s_alloc_mutex);
        if (goal >= sbi->s_partmaps[partition].s_partition_len)
                goal = 0;

        /* We search for the closest matching block to goal. If we find
           a exact hit, we stop. Otherwise we keep going till we run out
           of extents. We store the buffer_head, bloc, and extoffset
           of the current closest match and use that when we are done.
         */
        epos.offset = sizeof(struct unallocSpaceEntry);
        epos.block = iinfo->i_location;
        epos.bh = goal_epos.bh = NULL;

        while (spread) {
                ret = udf_next_aext(table, &epos, &eloc, &elen, &etype, 1);
                if (ret <= 0)
                        break;
                if (goal >= eloc.logicalBlockNum) {
                        if (goal < eloc.logicalBlockNum +
                                        (elen >> sb->s_blocksize_bits))
                                nspread = 0;
                        else
                                nspread = goal - eloc.logicalBlockNum -
                                        (elen >> sb->s_blocksize_bits);
                } else {
                        nspread = eloc.logicalBlockNum - goal;
                }

                if (nspread < spread) {
                        spread = nspread;
                        if (goal_epos.bh != epos.bh) {
                                brelse(goal_epos.bh);
                                goal_epos.bh = epos.bh;
                                get_bh(goal_epos.bh);
                        }
                        goal_epos.block = epos.block;
                        goal_epos.offset = epos.offset - adsize;
                        goal_eloc = eloc;
                        goal_elen = (etype << 30) | elen;
                }
        }

        brelse(epos.bh);

        if (ret < 0 || spread == 0xFFFFFFFF) {
                brelse(goal_epos.bh);
                mutex_unlock(&sbi->s_alloc_mutex);
                if (ret < 0)
                        *err = ret;
                return 0;
        }

        /* Only allocate blocks from the beginning of the extent.
           That way, we only delete (empty) extents, never have to insert an
           extent because of splitting */
        /* This works, but very poorly.... */

        newblock = goal_eloc.logicalBlockNum;
        goal_eloc.logicalBlockNum++;
        goal_elen -= sb->s_blocksize;

        if (goal_elen)
                udf_write_aext(table, &goal_epos, &goal_eloc, goal_elen, 1);
        else
                udf_delete_aext(table, goal_epos);
        brelse(goal_epos.bh);

        udf_add_free_space(sb, partition, -1);

        mutex_unlock(&sbi->s_alloc_mutex);
        *err = 0;
        return newblock;
}

void udf_free_blocks(struct super_block *sb, struct inode *inode,
                     struct kernel_lb_addr *bloc, uint32_t offset,
                     uint32_t count)
{
        uint16_t partition = bloc->partitionReferenceNum;
        struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition];
        uint32_t blk;

        if (check_add_overflow(bloc->logicalBlockNum, offset, &blk) ||
            check_add_overflow(blk, count, &blk) ||
            bloc->logicalBlockNum + count > map->s_partition_len) {
                udf_debug("Invalid request to free blocks: (%d, %u), off %u, "
                          "len %u, partition len %u\n",
                          partition, bloc->logicalBlockNum, offset, count,
                          map->s_partition_len);
                return;
        }

        if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) {
                udf_bitmap_free_blocks(sb, map->s_uspace.s_bitmap,
                                       bloc, offset, count);
        } else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) {
                udf_table_free_blocks(sb, map->s_uspace.s_table,
                                      bloc, offset, count);
        }

        if (inode) {
                inode_sub_bytes(inode,
                                ((sector_t)count) << sb->s_blocksize_bits);
        }
}

inline int udf_prealloc_blocks(struct super_block *sb,
                               struct inode *inode,
                               uint16_t partition, uint32_t first_block,
                               uint32_t block_count)
{
        struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition];
        int allocated;

        if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP)
                allocated = udf_bitmap_prealloc_blocks(sb,
                                                       map->s_uspace.s_bitmap,
                                                       partition, first_block,
                                                       block_count);
        else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE)
                allocated = udf_table_prealloc_blocks(sb,
                                                      map->s_uspace.s_table,
                                                      partition, first_block,
                                                      block_count);
        else
                return 0;

        if (inode && allocated > 0)
                inode_add_bytes(inode, allocated << sb->s_blocksize_bits);
        return allocated;
}

inline udf_pblk_t udf_new_block(struct super_block *sb,
                         struct inode *inode,
                         uint16_t partition, uint32_t goal, int *err)
{
        struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition];
        udf_pblk_t block;

        if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP)
                block = udf_bitmap_new_block(sb,
                                             map->s_uspace.s_bitmap,
                                             partition, goal, err);
        else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE)
                block = udf_table_new_block(sb,
                                            map->s_uspace.s_table,
                                            partition, goal, err);
        else {
                *err = -EIO;
                return 0;
        }
        if (inode && block)
                inode_add_bytes(inode, sb->s_blocksize);
        return block;
}