LXR linux/fs/hfsplus/bitmap.c

   1/*
   2 *  linux/fs/hfsplus/bitmap.c
   3 *
   4 * Copyright (C) 2001
   5 * Brad Boyer (flar@allandria.com)
   6 * (C) 2003 Ardis Technologies <roman@ardistech.com>
   7 *
   8 * Handling of allocation file
   9 */
  10
  11#include <linux/pagemap.h>
  12
  13#include "hfsplus_fs.h"
  14#include "hfsplus_raw.h"
  15
  16#define PAGE_CACHE_BITS (PAGE_CACHE_SIZE * 8)
  17
  18int hfsplus_block_allocate(struct super_block *sb, u32 size, u32 offset, u32 *max)
  19{
  20        struct page *page;
  21        struct address_space *mapping;
  22        __be32 *pptr, *curr, *end;
  23        u32 mask, start, len, n;
  24        __be32 val;
  25        int i;
  26
  27        len = *max;
  28        if (!len)
  29                return size;
  30
  31        dprint(DBG_BITMAP, "block_allocate: %u,%u,%u\n", size, offset, len);
  32        mutex_lock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
  33        mapping = HFSPLUS_SB(sb).alloc_file->i_mapping;
  34        page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS, NULL);
  35        if (IS_ERR(page)) {
  36                start = size;
  37                goto out;
  38        }
  39        pptr = kmap(page);
  40        curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
  41        i = offset % 32;
  42        offset &= ~(PAGE_CACHE_BITS - 1);
  43        if ((size ^ offset) / PAGE_CACHE_BITS)
  44                end = pptr + PAGE_CACHE_BITS / 32;
  45        else
  46                end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
  47
  48        /* scan the first partial u32 for zero bits */
  49        val = *curr;
  50        if (~val) {
  51                n = be32_to_cpu(val);
  52                mask = (1U << 31) >> i;
  53                for (; i < 32; mask >>= 1, i++) {
  54                        if (!(n & mask))
  55                                goto found;
  56                }
  57        }
  58        curr++;
  59
  60        /* scan complete u32s for the first zero bit */
  61        while (1) {
  62                while (curr < end) {
  63                        val = *curr;
  64                        if (~val) {
  65                                n = be32_to_cpu(val);
  66                                mask = 1 << 31;
  67                                for (i = 0; i < 32; mask >>= 1, i++) {
  68                                        if (!(n & mask))
  69                                                goto found;
  70                                }
  71                        }
  72                        curr++;
  73                }
  74                kunmap(page);
  75                offset += PAGE_CACHE_BITS;
  76                if (offset >= size)
  77                        break;
  78                page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
  79                                         NULL);
  80                if (IS_ERR(page)) {
  81                        start = size;
  82                        goto out;
  83                }
  84                curr = pptr = kmap(page);
  85                if ((size ^ offset) / PAGE_CACHE_BITS)
  86                        end = pptr + PAGE_CACHE_BITS / 32;
  87                else
  88                        end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
  89        }
  90        dprint(DBG_BITMAP, "bitmap full\n");
  91        start = size;
  92        goto out;
  93
  94found:
  95        start = offset + (curr - pptr) * 32 + i;
  96        if (start >= size) {
  97                dprint(DBG_BITMAP, "bitmap full\n");
  98                goto out;
  99        }
 100        /* do any partial u32 at the start */
 101        len = min(size - start, len);
 102        while (1) {
 103                n |= mask;
 104                if (++i >= 32)
 105                        break;
 106                mask >>= 1;
 107                if (!--len || n & mask)
 108                        goto done;
 109        }
 110        if (!--len)
 111                goto done;
 112        *curr++ = cpu_to_be32(n);
 113        /* do full u32s */
 114        while (1) {
 115                while (curr < end) {
 116                        n = be32_to_cpu(*curr);
 117                        if (len < 32)
 118                                goto last;
 119                        if (n) {
 120                                len = 32;
 121                                goto last;
 122                        }
 123                        *curr++ = cpu_to_be32(0xffffffff);
 124                        len -= 32;
 125                }
 126                set_page_dirty(page);
 127                kunmap(page);
 128                offset += PAGE_CACHE_BITS;
 129                page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
 130                                         NULL);
 131                if (IS_ERR(page)) {
 132                        start = size;
 133                        goto out;
 134                }
 135                pptr = kmap(page);
 136                curr = pptr;
 137                end = pptr + PAGE_CACHE_BITS / 32;
 138        }
 139last:
 140        /* do any partial u32 at end */
 141        mask = 1U << 31;
 142        for (i = 0; i < len; i++) {
 143                if (n & mask)
 144                        break;
 145                n |= mask;
 146                mask >>= 1;
 147        }
 148done:
 149        *curr = cpu_to_be32(n);
 150        set_page_dirty(page);
 151        kunmap(page);
 152        *max = offset + (curr - pptr) * 32 + i - start;
 153        HFSPLUS_SB(sb).free_blocks -= *max;
 154        sb->s_dirt = 1;
 155        dprint(DBG_BITMAP, "-> %u,%u\n", start, *max);
 156out:
 157        mutex_unlock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
 158        return start;
 159}
 160
 161int hfsplus_block_free(struct super_block *sb, u32 offset, u32 count)
 162{
 163        struct page *page;
 164        struct address_space *mapping;
 165        __be32 *pptr, *curr, *end;
 166        u32 mask, len, pnr;
 167        int i;
 168
 169        /* is there any actual work to be done? */
 170        if (!count)
 171                return 0;
 172
 173        dprint(DBG_BITMAP, "block_free: %u,%u\n", offset, count);
 174        /* are all of the bits in range? */
 175        if ((offset + count) > HFSPLUS_SB(sb).total_blocks)
 176                return -2;
 177
 178        mutex_lock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
 179        mapping = HFSPLUS_SB(sb).alloc_file->i_mapping;
 180        pnr = offset / PAGE_CACHE_BITS;
 181        page = read_mapping_page(mapping, pnr, NULL);
 182        pptr = kmap(page);
 183        curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
 184        end = pptr + PAGE_CACHE_BITS / 32;
 185        len = count;
 186
 187        /* do any partial u32 at the start */
 188        i = offset % 32;
 189        if (i) {
 190                int j = 32 - i;
 191                mask = 0xffffffffU << j;
 192                if (j > count) {
 193                        mask |= 0xffffffffU >> (i + count);
 194                        *curr++ &= cpu_to_be32(mask);
 195                        goto out;
 196                }
 197                *curr++ &= cpu_to_be32(mask);
 198                count -= j;
 199        }
 200
 201        /* do full u32s */
 202        while (1) {
 203                while (curr < end) {
 204                        if (count < 32)
 205                                goto done;
 206                        *curr++ = 0;
 207                        count -= 32;
 208                }
 209                if (!count)
 210                        break;
 211                set_page_dirty(page);
 212                kunmap(page);
 213                page = read_mapping_page(mapping, ++pnr, NULL);
 214                pptr = kmap(page);
 215                curr = pptr;
 216                end = pptr + PAGE_CACHE_BITS / 32;
 217        }
 218done:
 219        /* do any partial u32 at end */
 220        if (count) {
 221                mask = 0xffffffffU >> count;
 222                *curr &= cpu_to_be32(mask);
 223        }
 224out:
 225        set_page_dirty(page);
 226        kunmap(page);
 227        HFSPLUS_SB(sb).free_blocks += len;
 228        sb->s_dirt = 1;
 229        mutex_unlock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
 230
 231        return 0;
 232}
 233