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        pptr = kmap(page);
  36        curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
  37        i = offset % 32;
  38        offset &= ~(PAGE_CACHE_BITS - 1);
  39        if ((size ^ offset) / PAGE_CACHE_BITS)
  40                end = pptr + PAGE_CACHE_BITS / 32;
  41        else
  42                end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
  43
  44        /* scan the first partial u32 for zero bits */
  45        val = *curr;
  46        if (~val) {
  47                n = be32_to_cpu(val);
  48                mask = (1U << 31) >> i;
  49                for (; i < 32; mask >>= 1, i++) {
  50                        if (!(n & mask))
  51                                goto found;
  52                }
  53        }
  54        curr++;
  55
  56        /* scan complete u32s for the first zero bit */
  57        while (1) {
  58                while (curr < end) {
  59                        val = *curr;
  60                        if (~val) {
  61                                n = be32_to_cpu(val);
  62                                mask = 1 << 31;
  63                                for (i = 0; i < 32; mask >>= 1, i++) {
  64                                        if (!(n & mask))
  65                                                goto found;
  66                                }
  67                        }
  68                        curr++;
  69                }
  70                kunmap(page);
  71                offset += PAGE_CACHE_BITS;
  72                if (offset >= size)
  73                        break;
  74                page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
  75                                         NULL);
  76                curr = pptr = kmap(page);
  77                if ((size ^ offset) / PAGE_CACHE_BITS)
  78                        end = pptr + PAGE_CACHE_BITS / 32;
  79                else
  80                        end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
  81        }
  82        dprint(DBG_BITMAP, "bitmap full\n");
  83        start = size;
  84        goto out;
  85
  86found:
  87        start = offset + (curr - pptr) * 32 + i;
  88        if (start >= size) {
  89                dprint(DBG_BITMAP, "bitmap full\n");
  90                goto out;
  91        }
  92        /* do any partial u32 at the start */
  93        len = min(size - start, len);
  94        while (1) {
  95                n |= mask;
  96                if (++i >= 32)
  97                        break;
  98                mask >>= 1;
  99                if (!--len || n & mask)
 100                        goto done;
 101        }
 102        if (!--len)
 103                goto done;
 104        *curr++ = cpu_to_be32(n);
 105        /* do full u32s */
 106        while (1) {
 107                while (curr < end) {
 108                        n = be32_to_cpu(*curr);
 109                        if (len < 32)
 110                                goto last;
 111                        if (n) {
 112                                len = 32;
 113                                goto last;
 114                        }
 115                        *curr++ = cpu_to_be32(0xffffffff);
 116                        len -= 32;
 117                }
 118                set_page_dirty(page);
 119                kunmap(page);
 120                offset += PAGE_CACHE_BITS;
 121                page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
 122                                         NULL);
 123                pptr = kmap(page);
 124                curr = pptr;
 125                end = pptr + PAGE_CACHE_BITS / 32;
 126        }
 127last:
 128        /* do any partial u32 at end */
 129        mask = 1U << 31;
 130        for (i = 0; i < len; i++) {
 131                if (n & mask)
 132                        break;
 133                n |= mask;
 134                mask >>= 1;
 135        }
 136done:
 137        *curr = cpu_to_be32(n);
 138        set_page_dirty(page);
 139        kunmap(page);
 140        *max = offset + (curr - pptr) * 32 + i - start;
 141        HFSPLUS_SB(sb).free_blocks -= *max;
 142        sb->s_dirt = 1;
 143        dprint(DBG_BITMAP, "-> %u,%u\n", start, *max);
 144out:
 145        mutex_unlock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
 146        return start;
 147}
 148
 149int hfsplus_block_free(struct super_block *sb, u32 offset, u32 count)
 150{
 151        struct page *page;
 152        struct address_space *mapping;
 153        __be32 *pptr, *curr, *end;
 154        u32 mask, len, pnr;
 155        int i;
 156
 157        /* is there any actual work to be done? */
 158        if (!count)
 159                return 0;
 160
 161        dprint(DBG_BITMAP, "block_free: %u,%u\n", offset, count);
 162        /* are all of the bits in range? */
 163        if ((offset + count) > HFSPLUS_SB(sb).total_blocks)
 164                return -2;
 165
 166        mutex_lock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
 167        mapping = HFSPLUS_SB(sb).alloc_file->i_mapping;
 168        pnr = offset / PAGE_CACHE_BITS;
 169        page = read_mapping_page(mapping, pnr, NULL);
 170        pptr = kmap(page);
 171        curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
 172        end = pptr + PAGE_CACHE_BITS / 32;
 173        len = count;
 174
 175        /* do any partial u32 at the start */
 176        i = offset % 32;
 177        if (i) {
 178                int j = 32 - i;
 179                mask = 0xffffffffU << j;
 180                if (j > count) {
 181                        mask |= 0xffffffffU >> (i + count);
 182                        *curr++ &= cpu_to_be32(mask);
 183                        goto out;
 184                }
 185                *curr++ &= cpu_to_be32(mask);
 186                count -= j;
 187        }
 188
 189        /* do full u32s */
 190        while (1) {
 191                while (curr < end) {
 192                        if (count < 32)
 193                                goto done;
 194                        *curr++ = 0;
 195                        count -= 32;
 196                }
 197                if (!count)
 198                        break;
 199                set_page_dirty(page);
 200                kunmap(page);
 201                page = read_mapping_page(mapping, ++pnr, NULL);
 202                pptr = kmap(page);
 203                curr = pptr;
 204                end = pptr + PAGE_CACHE_BITS / 32;
 205        }
 206done:
 207        /* do any partial u32 at end */
 208        if (count) {
 209                mask = 0xffffffffU >> count;
 210                *curr &= cpu_to_be32(mask);
 211        }
 212out:
 213        set_page_dirty(page);
 214        kunmap(page);
 215        HFSPLUS_SB(sb).free_blocks += len;
 216        sb->s_dirt = 1;
 217        mutex_unlock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
 218
 219        return 0;
 220}
 221