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