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