Orange Pi5 kernel

/*
 *  linux/fs/hfs/bitmap.c
 *
 * Copyright (C) 1996-1997  Paul H. Hargrove
 * (C) 2003 Ardis Technologies <roman@ardistech.com>
 * This file may be distributed under the terms of the GNU General Public License.
 *
 * Based on GPLed code Copyright (C) 1995  Michael Dreher
 *
 * This file contains the code to modify the volume bitmap:
 * search/set/clear bits.
 */
 
#include "hfs_fs.h"
 
/*
 * hfs_find_zero_bit()
 *
 * Description:
 *  Given a block of memory, its length in bits, and a starting bit number,
 *  determine the number of the first zero bits (in left-to-right ordering)
 *  in that range.
 *
 *  Returns >= 'size' if no zero bits are found in the range.
 *
 *  Accesses memory in 32-bit aligned chunks of 32-bits and thus
 *  may read beyond the 'size'th bit.
 */
static u32 hfs_find_set_zero_bits(__be32 *bitmap, u32 size, u32 offset, u32 *max)
{
<------>__be32 *curr, *end;
<------>u32 mask, start, len, n;
<------>__be32 val;
<------>int i;
 
<------>len = *max;
<------>if (!len)
<------><------>return size;
 
<------>curr = bitmap + (offset / 32);
<------>end = bitmap + ((size + 31) / 32);
 
<------>/* scan the first partial u32 for zero bits */
<------>val = *curr;
<------>if (~val) {
<------><------>n = be32_to_cpu(val);
<------><------>i = offset % 32;
<------><------>mask = (1U << 31) >> i;
<------><------>for (; i < 32; mask >>= 1, i++) {
<------><------><------>if (!(n & mask))
<------><------><------><------>goto found;
<------><------>}
<------>}
 
<------>/* scan complete u32s for the first zero bit */
<------>while (++curr < end) {
<------><------>val = *curr;
<------><------>if (~val) {
<------><------><------>n = be32_to_cpu(val);
<------><------><------>mask = 1 << 31;
<------><------><------>for (i = 0; i < 32; mask >>= 1, i++) {
<------><------><------><------>if (!(n & mask))
<------><------><------><------><------>goto found;
<------><------><------>}
<------><------>}
<------>}
<------>return size;
 
found:
<------>start = (curr - bitmap) * 32 + i;
<------>if (start >= size)
<------><------>return start;
<------>/* do any partial u32 at the start */
<------>len = min(size - start, len);
<------>while (1) {
<------><------>n |= mask;
<------><------>if (++i >= 32)
<------><------><------>break;
<------><------>mask >>= 1;
<------><------>if (!--len || n & mask)
<------><------><------>goto done;
<------>}
<------>if (!--len)
<------><------>goto done;
<------>*curr++ = cpu_to_be32(n);
<------>/* do full u32s */
<------>while (1) {
<------><------>n = be32_to_cpu(*curr);
<------><------>if (len < 32)
<------><------><------>break;
<------><------>if (n) {
<------><------><------>len = 32;
<------><------><------>break;
<------><------>}
<------><------>*curr++ = cpu_to_be32(0xffffffff);
<------><------>len -= 32;
<------>}
<------>/* do any partial u32 at end */
<------>mask = 1U << 31;
<------>for (i = 0; i < len; i++) {
<------><------>if (n & mask)
<------><------><------>break;
<------><------>n |= mask;
<------><------>mask >>= 1;
<------>}
done:
<------>*curr = cpu_to_be32(n);
<------>*max = (curr - bitmap) * 32 + i - start;
<------>return start;
}
 
/*
 * hfs_vbm_search_free()
 *
 * Description:
 *   Search for 'num_bits' consecutive cleared bits in the bitmap blocks of
 *   the hfs MDB. 'mdb' had better be locked or the returned range
 *   may be no longer free, when this functions returns!
 *   XXX Currently the search starts from bit 0, but it should start with
 *   the bit number stored in 's_alloc_ptr' of the MDB.
 * Input Variable(s):
 *   struct hfs_mdb *mdb: Pointer to the hfs MDB
 *   u16 *num_bits: Pointer to the number of cleared bits
 *     to search for
 * Output Variable(s):
 *   u16 *num_bits: The number of consecutive clear bits of the
 *     returned range. If the bitmap is fragmented, this will be less than
 *     requested and it will be zero, when the disk is full.
 * Returns:
 *   The number of the first bit of the range of cleared bits which has been
 *   found. When 'num_bits' is zero, this is invalid!
 * Preconditions:
 *   'mdb' points to a "valid" (struct hfs_mdb).
 *   'num_bits' points to a variable of type (u16), which contains
 *	the number of cleared bits to find.
 * Postconditions:
 *   'num_bits' is set to the length of the found sequence.
 */
u32 hfs_vbm_search_free(struct super_block *sb, u32 goal, u32 *num_bits)
{
<------>void *bitmap;
<------>u32 pos;
 
<------>/* make sure we have actual work to perform */
<------>if (!*num_bits)
<------><------>return 0;
 
<------>mutex_lock(&HFS_SB(sb)->bitmap_lock);
<------>bitmap = HFS_SB(sb)->bitmap;
 
<------>pos = hfs_find_set_zero_bits(bitmap, HFS_SB(sb)->fs_ablocks, goal, num_bits);
<------>if (pos >= HFS_SB(sb)->fs_ablocks) {
<------><------>if (goal)
<------><------><------>pos = hfs_find_set_zero_bits(bitmap, goal, 0, num_bits);
<------><------>if (pos >= HFS_SB(sb)->fs_ablocks) {
<------><------><------>*num_bits = pos = 0;
<------><------><------>goto out;
<------><------>}
<------>}
 
<------>hfs_dbg(BITMAP, "alloc_bits: %u,%u\n", pos, *num_bits);
<------>HFS_SB(sb)->free_ablocks -= *num_bits;
<------>hfs_bitmap_dirty(sb);
out:
<------>mutex_unlock(&HFS_SB(sb)->bitmap_lock);
<------>return pos;
}
 
 
/*
 * hfs_clear_vbm_bits()
 *
 * Description:
 *   Clear the requested bits in the volume bitmap of the hfs filesystem
 * Input Variable(s):
 *   struct hfs_mdb *mdb: Pointer to the hfs MDB
 *   u16 start: The offset of the first bit
 *   u16 count: The number of bits
 * Output Variable(s):
 *   None
 * Returns:
 *    0: no error
 *   -1: One of the bits was already clear.  This is a strange
 *	 error and when it happens, the filesystem must be repaired!
 *   -2: One or more of the bits are out of range of the bitmap.
 * Preconditions:
 *   'mdb' points to a "valid" (struct hfs_mdb).
 * Postconditions:
 *   Starting with bit number 'start', 'count' bits in the volume bitmap
 *   are cleared. The affected bitmap blocks are marked "dirty", the free
 *   block count of the MDB is updated and the MDB is marked dirty.
 */
int hfs_clear_vbm_bits(struct super_block *sb, u16 start, u16 count)
{
<------>__be32 *curr;
<------>u32 mask;
<------>int i, len;
 
<------>/* is there any actual work to be done? */
<------>if (!count)
<------><------>return 0;
 
<------>hfs_dbg(BITMAP, "clear_bits: %u,%u\n", start, count);
<------>/* are all of the bits in range? */
<------>if ((start + count) > HFS_SB(sb)->fs_ablocks)
<------><------>return -2;
 
<------>mutex_lock(&HFS_SB(sb)->bitmap_lock);
<------>/* bitmap is always on a 32-bit boundary */
<------>curr = HFS_SB(sb)->bitmap + (start / 32);
<------>len = count;
 
<------>/* do any partial u32 at the start */
<------>i = start % 32;
<------>if (i) {
<------><------>int j = 32 - i;
<------><------>mask = 0xffffffffU << j;
<------><------>if (j > count) {
<------><------><------>mask |= 0xffffffffU >> (i + count);
<------><------><------>*curr &= cpu_to_be32(mask);
<------><------><------>goto out;
<------><------>}
<------><------>*curr++ &= cpu_to_be32(mask);
<------><------>count -= j;
<------>}
 
<------>/* do full u32s */
<------>while (count >= 32) {
<------><------>*curr++ = 0;
<------><------>count -= 32;
<------>}
<------>/* do any partial u32 at end */
<------>if (count) {
<------><------>mask = 0xffffffffU >> count;
<------><------>*curr &= cpu_to_be32(mask);
<------>}
out:
<------>HFS_SB(sb)->free_ablocks += len;
<------>mutex_unlock(&HFS_SB(sb)->bitmap_lock);
<------>hfs_bitmap_dirty(sb);
 
<------>return 0;
}