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