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