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 } 235