fs/hfsplus/bitmap.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  *  linux/fs/hfsplus/bitmap.c
0004  *
0005  * Copyright (C) 2001
0006  * Brad Boyer (flar@allandria.com)
0007  * (C) 2003 Ardis Technologies <roman@ardistech.com>
0008  *
0009  * Handling of allocation file
0010  */
0011
0012 #include <linux/pagemap.h>
0013
0014 #include "hfsplus_fs.h"
0015 #include "hfsplus_raw.h"
0016
0017 #define PAGE_CACHE_BITS (PAGE_SIZE * 8)
0018
0019 int hfsplus_block_allocate(struct super_block *sb, u32 size,
0020         u32 offset, u32 *max)
0021 {
0022     struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb);
0023     struct page *page;
0024     struct address_space *mapping;
0025     __be32 *pptr, *curr, *end;
0026     u32 mask, start, len, n;
0027     __be32 val;
0028     int i;
0029
0030     len = *max;
0031     if (!len)
0032         return size;
0033
0034     hfs_dbg(BITMAP, "block_allocate: %u,%u,%u\n", size, offset, len);
0035     mutex_lock(&sbi->alloc_mutex);
0036     mapping = sbi->alloc_file->i_mapping;
0037     page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS, NULL);
0038     if (IS_ERR(page)) {
0039         start = size;
0040         goto out;
0041     }
0042     pptr = kmap(page);
0043     curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
0044     i = offset % 32;
0045     offset &= ~(PAGE_CACHE_BITS - 1);
0046     if ((size ^ offset) / PAGE_CACHE_BITS)
0047         end = pptr + PAGE_CACHE_BITS / 32;
0048     else
0049         end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
0050
0051     /* scan the first partial u32 for zero bits */
0052     val = *curr;
0053     if (~val) {
0054         n = be32_to_cpu(val);
0055         mask = (1U << 31) >> i;
0056         for (; i < 32; mask >>= 1, i++) {
0057             if (!(n & mask))
0058                 goto found;
0059         }
0060     }
0061     curr++;
0062
0063     /* scan complete u32s for the first zero bit */
0064     while (1) {
0065         while (curr < end) {
0066             val = *curr;
0067             if (~val) {
0068                 n = be32_to_cpu(val);
0069                 mask = 1 << 31;
0070                 for (i = 0; i < 32; mask >>= 1, i++) {
0071                     if (!(n & mask))
0072                         goto found;
0073                 }
0074             }
0075             curr++;
0076         }
0077         kunmap(page);
0078         offset += PAGE_CACHE_BITS;
0079         if (offset >= size)
0080             break;
0081         page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
0082                      NULL);
0083         if (IS_ERR(page)) {
0084             start = size;
0085             goto out;
0086         }
0087         curr = pptr = kmap(page);
0088         if ((size ^ offset) / PAGE_CACHE_BITS)
0089             end = pptr + PAGE_CACHE_BITS / 32;
0090         else
0091             end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
0092     }
0093     hfs_dbg(BITMAP, "bitmap full\n");
0094     start = size;
0095     goto out;
0096
0097 found:
0098     start = offset + (curr - pptr) * 32 + i;
0099     if (start >= size) {
0100         hfs_dbg(BITMAP, "bitmap full\n");
0101         goto out;
0102     }
0103     /* do any partial u32 at the start */
0104     len = min(size - start, len);
0105     while (1) {
0106         n |= mask;
0107         if (++i >= 32)
0108             break;
0109         mask >>= 1;
0110         if (!--len || n & mask)
0111             goto done;
0112     }
0113     if (!--len)
0114         goto done;
0115     *curr++ = cpu_to_be32(n);
0116     /* do full u32s */
0117     while (1) {
0118         while (curr < end) {
0119             n = be32_to_cpu(*curr);
0120             if (len < 32)
0121                 goto last;
0122             if (n) {
0123                 len = 32;
0124                 goto last;
0125             }
0126             *curr++ = cpu_to_be32(0xffffffff);
0127             len -= 32;
0128         }
0129         set_page_dirty(page);
0130         kunmap(page);
0131         offset += PAGE_CACHE_BITS;
0132         page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
0133                      NULL);
0134         if (IS_ERR(page)) {
0135             start = size;
0136             goto out;
0137         }
0138         pptr = kmap(page);
0139         curr = pptr;
0140         end = pptr + PAGE_CACHE_BITS / 32;
0141     }
0142 last:
0143     /* do any partial u32 at end */
0144     mask = 1U << 31;
0145     for (i = 0; i < len; i++) {
0146         if (n & mask)
0147             break;
0148         n |= mask;
0149         mask >>= 1;
0150     }
0151 done:
0152     *curr = cpu_to_be32(n);
0153     set_page_dirty(page);
0154     kunmap(page);
0155     *max = offset + (curr - pptr) * 32 + i - start;
0156     sbi->free_blocks -= *max;
0157     hfsplus_mark_mdb_dirty(sb);
0158     hfs_dbg(BITMAP, "-> %u,%u\n", start, *max);
0159 out:
0160     mutex_unlock(&sbi->alloc_mutex);
0161     return start;
0162 }
0163
0164 int hfsplus_block_free(struct super_block *sb, u32 offset, u32 count)
0165 {
0166     struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb);
0167     struct page *page;
0168     struct address_space *mapping;
0169     __be32 *pptr, *curr, *end;
0170     u32 mask, len, pnr;
0171     int i;
0172
0173     /* is there any actual work to be done? */
0174     if (!count)
0175         return 0;
0176
0177     hfs_dbg(BITMAP, "block_free: %u,%u\n", offset, count);
0178     /* are all of the bits in range? */
0179     if ((offset + count) > sbi->total_blocks)
0180         return -ENOENT;
0181
0182     mutex_lock(&sbi->alloc_mutex);
0183     mapping = sbi->alloc_file->i_mapping;
0184     pnr = offset / PAGE_CACHE_BITS;
0185     page = read_mapping_page(mapping, pnr, NULL);
0186     if (IS_ERR(page))
0187         goto kaboom;
0188     pptr = kmap(page);
0189     curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
0190     end = pptr + PAGE_CACHE_BITS / 32;
0191     len = count;
0192
0193     /* do any partial u32 at the start */
0194     i = offset % 32;
0195     if (i) {
0196         int j = 32 - i;
0197         mask = 0xffffffffU << j;
0198         if (j > count) {
0199             mask |= 0xffffffffU >> (i + count);
0200             *curr++ &= cpu_to_be32(mask);
0201             goto out;
0202         }
0203         *curr++ &= cpu_to_be32(mask);
0204         count -= j;
0205     }
0206
0207     /* do full u32s */
0208     while (1) {
0209         while (curr < end) {
0210             if (count < 32)
0211                 goto done;
0212             *curr++ = 0;
0213             count -= 32;
0214         }
0215         if (!count)
0216             break;
0217         set_page_dirty(page);
0218         kunmap(page);
0219         page = read_mapping_page(mapping, ++pnr, NULL);
0220         if (IS_ERR(page))
0221             goto kaboom;
0222         pptr = kmap(page);
0223         curr = pptr;
0224         end = pptr + PAGE_CACHE_BITS / 32;
0225     }
0226 done:
0227     /* do any partial u32 at end */
0228     if (count) {
0229         mask = 0xffffffffU >> count;
0230         *curr &= cpu_to_be32(mask);
0231     }
0232 out:
0233     set_page_dirty(page);
0234     kunmap(page);
0235     sbi->free_blocks += len;
0236     hfsplus_mark_mdb_dirty(sb);
0237     mutex_unlock(&sbi->alloc_mutex);
0238
0239     return 0;
0240
0241 kaboom:
0242     pr_crit("unable to mark blocks free: error %ld\n", PTR_ERR(page));
0243     mutex_unlock(&sbi->alloc_mutex);
0244
0245     return -EIO;
0246 }