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         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
  86 found:
  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         }
 127 last:
 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         }
 136 done:
 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);
 144 out:
 145         mutex_unlock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
 146         return start;
 147 }
 148
 149 int 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         }
 206 done:
 207         /* do any partial u32 at end */
 208         if (count) {
 209                 mask = 0xffffffffU >> count;
 210                 *curr &= cpu_to_be32(mask);
 211         }
 212 out:
 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 }