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
  18 int 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
  94 found:
  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         }
 139 last:
 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         }
 148 done:
 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);
 156 out:
 157         mutex_unlock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
 158         return start;
 159 }
 160
 161 int 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         }
 218 done:
 219         /* do any partial u32 at end */
 220         if (count) {
 221                 mask = 0xffffffffU >> count;
 222                 *curr &= cpu_to_be32(mask);
 223         }
 224 out:
 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 }