Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
FreeBSD/Linux Kernel Cross Reference
sys/fs/hfsplus/extents.c
Version:
- FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
SearchContext: - none - 3 - 10
1 /* 2 * linux/fs/hfsplus/extents.c 3 * 4 * Copyright (C) 2001 5 * Brad Boyer (flar@allandria.com) 6 * (C) 2003 Ardis Technologies <roman@ardistech.com> 7 * 8 * Handling of Extents both in catalog and extents overflow trees 9 */ 10 11 #include <linux/errno.h> 12 #include <linux/fs.h> 13 #include <linux/pagemap.h> 14 #include <linux/version.h> 15 #if LINUX_VERSION_CODE >= KERNEL_VERSION(2,5,0) 16 #include <linux/buffer_head.h> 17 #endif 18 19 #include "hfsplus_fs.h" 20 #include "hfsplus_raw.h" 21 22 /* Compare two extents keys, returns 0 on same, pos/neg for difference */ 23 int hfsplus_cmp_ext_key(hfsplus_btree_key *k1, hfsplus_btree_key *k2) 24 { 25 u32 k1id, k2id; 26 u32 k1s, k2s; 27 28 k1id = k1->ext.cnid; 29 k2id = k2->ext.cnid; 30 if (k1id != k2id) 31 return be32_to_cpu(k1id) < be32_to_cpu(k2id) ? -1 : 1; 32 33 if (k1->ext.fork_type != k2->ext.fork_type) 34 return k1->ext.fork_type < k2->ext.fork_type ? -1 : 1; 35 36 k1s = k1->ext.start_block; 37 k2s = k2->ext.start_block; 38 if (k1s == k2s) 39 return 0; 40 return be32_to_cpu(k1s) < be32_to_cpu(k2s) ? -1 : 1; 41 } 42 43 void hfsplus_fill_ext_key(hfsplus_btree_key *key, u32 cnid, 44 u32 block, u8 type) 45 { 46 key->key_len = cpu_to_be16(HFSPLUS_EXT_KEYLEN - 2); 47 key->ext.cnid = cpu_to_be32(cnid); 48 key->ext.start_block = cpu_to_be32(block); 49 key->ext.fork_type = type; 50 key->ext.pad = 0; 51 } 52 53 static u32 hfsplus_find_extent(hfsplus_extent *extent, u32 off) 54 { 55 int i; 56 u32 count; 57 58 for (i = 0; i < 8; extent++, i++) { 59 count = be32_to_cpu(extent->block_count); 60 if (off < count) 61 return be32_to_cpu(extent->start_block) + off; 62 off -= count; 63 } 64 /* panic? */ 65 return 0; 66 } 67 68 static int hfsplus_find_extentry(struct hfsplus_find_data *fd, 69 hfsplus_extent *extent) 70 { 71 int res; 72 73 fd->key->ext.cnid = 0; 74 res = hfsplus_btree_find(fd); 75 if (res && res != -ENOENT) 76 return res; 77 if (fd->key->ext.cnid != fd->search_key->ext.cnid || 78 fd->key->ext.fork_type != fd->search_key->ext.fork_type) 79 return -ENOENT; 80 //if (fd->entrylength != ext_key_size)... 81 hfsplus_bnode_readbytes(fd->bnode, extent, fd->entryoffset, fd->entrylength); 82 return 0; 83 } 84 85 /* Get a block at iblock for inode, possibly allocating if create */ 86 int hfsplus_get_block(struct inode *inode, sector_t iblock, 87 struct buffer_head *bh_result, int create) 88 { 89 struct super_block *sb; 90 hfsplus_extent_rec ext_entry; 91 struct hfsplus_find_data fd; 92 int err = -EIO; 93 u32 ablock, dblock = 0; 94 95 sb = inode->i_sb; 96 97 /* Convert inode block to disk allocation block */ 98 ablock = iblock; 99 100 if (ablock >= HFSPLUS_I(inode).total_blocks) { 101 if (ablock > HFSPLUS_I(inode).total_blocks || !create) 102 return -EIO; 103 if (ablock >= HFSPLUS_I(inode).alloc_blocks) { 104 err = hfsplus_extend_file(inode); 105 if (err) 106 return err; 107 } 108 HFSPLUS_I(inode).mmu_private += sb->s_blocksize; 109 HFSPLUS_I(inode).total_blocks++; 110 mark_inode_dirty(inode); 111 } else 112 create = 0; 113 114 if (ablock < HFSPLUS_I(inode).extent_blocks) { 115 dblock = hfsplus_find_extent(HFSPLUS_I(inode).extents, ablock); 116 } else { 117 hfsplus_find_init(HFSPLUS_SB(sb).ext_tree, &fd); 118 hfsplus_fill_ext_key(fd.search_key, inode->i_ino, ablock, HFSPLUS_IS_RSRC(inode) ? 119 HFSPLUS_TYPE_RSRC : HFSPLUS_TYPE_DATA); 120 err = hfsplus_find_extentry(&fd, ext_entry); 121 if (!err) 122 dblock = hfsplus_find_extent(ext_entry, ablock - 123 be32_to_cpu(fd.key->ext.start_block)); 124 hfsplus_find_exit(&fd); 125 if (err) 126 return err; 127 } 128 129 if (!dblock) 130 return -EIO; 131 dprint(DBG_EXTENT, "get_block(%lu): %lu - %u\n", inode->i_ino, iblock, dblock); 132 133 map_bh(bh_result, sb, dblock + HFSPLUS_SB(sb).blockoffset); 134 if (create) 135 set_buffer_new(bh_result); 136 return 0; 137 } 138 139 static void hfsplus_dump_extent(hfsplus_extent *extent) 140 { 141 int i; 142 143 dprint(DBG_EXTENT, " "); 144 for (i = 0; i < 8; i++) 145 dprint(DBG_EXTENT, " %u:%u", be32_to_cpu(extent[i].start_block), 146 be32_to_cpu(extent[i].block_count)); 147 dprint(DBG_EXTENT, "\n"); 148 } 149 150 static int hfsplus_add_extent(hfsplus_extent *extent, u32 offset, 151 u32 alloc_block, u32 block_count) 152 { 153 u32 count, start; 154 int i; 155 156 hfsplus_dump_extent(extent); 157 for (i = 0; i < 8; extent++, i++) { 158 count = be32_to_cpu(extent->block_count); 159 if (offset == count) { 160 start = be32_to_cpu(extent->start_block); 161 if (alloc_block != start + count) { 162 if (++i >= 8) 163 return -ENOSPC; 164 extent++; 165 extent->start_block = cpu_to_be32(alloc_block); 166 } else 167 block_count += count; 168 extent->block_count = cpu_to_be32(block_count); 169 return 0; 170 } else if (offset < count) 171 break; 172 offset -= count; 173 } 174 /* panic? */ 175 return -EIO; 176 } 177 178 void hfsplus_free_blocks(struct super_block *sb, u32 start, u32 count) 179 { 180 struct inode *anode; 181 struct buffer_head *bh; 182 int size, blk, off; 183 unsigned long *data, word, m; 184 185 anode = HFSPLUS_SB(sb).alloc_file; 186 size = sb->s_blocksize / sizeof(unsigned long); 187 blk = (start >> sb->s_blocksize_bits) / 8; 188 off = (start & (sb->s_blocksize * 8 - 1)) / 8 / sizeof(unsigned long); 189 m = 1 << (~start & (8 * sizeof(unsigned long) - 1)); 190 191 HFSPLUS_SB(sb).free_blocks += count; 192 sb->s_dirt = 1; 193 194 while (count) { 195 bh = hfsplus_getblk(anode, blk); 196 data = (unsigned long *)bh->b_data; 197 do { 198 word = ~be32_to_cpu(data[off]); 199 for (;;) { 200 if (word & m) 201 printk("freeing free block %u\n", start); 202 word |= m; 203 start++; 204 if (!--count) { 205 data[off] = cpu_to_be32(~word); 206 goto done; 207 } 208 if (!(m >>= 1)) 209 break; 210 } 211 data[off] = cpu_to_be32(~word); 212 m = 1UL << (8 * sizeof(unsigned long) - 1); 213 } while (++off < size); 214 done: 215 mark_buffer_dirty_inode(bh, anode); 216 brelse(bh); 217 if (++blk >= anode->i_blocks) 218 break; 219 off = 0; 220 } 221 if (count) 222 printk("%u block left to free\n", count); 223 } 224 225 int hfsplus_free_extents(struct super_block *sb, hfsplus_extent *extent, 226 u32 offset, u32 block_nr) 227 { 228 u32 count, start; 229 int i; 230 231 hfsplus_dump_extent(extent); 232 for (i = 0; i < 8; extent++, i++) { 233 count = be32_to_cpu(extent->block_count); 234 if (offset == count) 235 goto found; 236 else if (offset < count) 237 break; 238 offset -= count; 239 } 240 /* panic? */ 241 return -EIO; 242 found: 243 for (;;) { 244 start = be32_to_cpu(extent->start_block); 245 if (count <= block_nr) { 246 hfsplus_free_blocks(sb, start, count); 247 extent->block_count = 0; 248 extent->start_block = 0; 249 block_nr -= count; 250 } else { 251 count -= block_nr; 252 hfsplus_free_blocks(sb, start + count, block_nr); 253 extent->block_count = cpu_to_be32(count); 254 block_nr = 0; 255 } 256 if (!block_nr || !i) 257 return 0; 258 i--; 259 extent--; 260 count = be32_to_cpu(extent->block_count); 261 } 262 } 263 264 int hfsplus_free_fork(struct super_block *sb, u32 cnid, hfsplus_fork_raw *fork, int type) 265 { 266 struct hfsplus_find_data fd; 267 hfsplus_extent_rec ext_entry; 268 u32 total_blocks, blocks, start; 269 int res, i; 270 271 total_blocks = be32_to_cpu(fork->total_blocks); 272 if (!total_blocks) 273 return 0; 274 275 blocks = 0; 276 for (i = 0; i < 8; i++) 277 blocks += be32_to_cpu(fork->extents[i].block_count); 278 279 res = hfsplus_free_extents(sb, fork->extents, blocks, blocks); 280 if (res) 281 return res; 282 if (total_blocks == blocks) 283 return 0; 284 285 hfsplus_find_init(HFSPLUS_SB(sb).ext_tree, &fd); 286 do { 287 hfsplus_fill_ext_key(fd.search_key, cnid, 288 total_blocks, type); 289 res = hfsplus_find_extentry(&fd, ext_entry); 290 if (res) 291 break; 292 start = be32_to_cpu(fd.key->ext.start_block); 293 hfsplus_free_extents(sb, ext_entry, 294 total_blocks - start, 295 total_blocks); 296 hfsplus_bnode_remove_rec(&fd); 297 total_blocks = start; 298 } while (total_blocks > blocks); 299 hfsplus_find_exit(&fd); 300 301 return res; 302 } 303 304 int hfsplus_extend_file(struct inode *inode) 305 { 306 struct super_block *sb = inode->i_sb; 307 struct inode *anode = HFSPLUS_SB(sb).alloc_file; 308 struct hfsplus_find_data fd; 309 hfsplus_extent_rec ext_entry; 310 struct buffer_head *bh; 311 u32 blk, blk1, ablock, block_count; 312 unsigned long *data, word, m; 313 int res, size, off, i; 314 315 if (anode->i_size * 8 < HFSPLUS_SB(sb).total_blocks - HFSPLUS_SB(sb).free_blocks + 8) { 316 // extend alloc file 317 BUG(); 318 } 319 blk = blk1 = (HFSPLUS_SB(sb).next_alloc >> sb->s_blocksize_bits) / 8; 320 off = (HFSPLUS_SB(sb).next_alloc & (sb->s_blocksize * 8 - 1)) / sizeof(unsigned long) / 8; 321 322 for (;;) { 323 // ignore first off for now... 324 off = 0; 325 bh = hfsplus_getblk(anode, blk); 326 if (blk == anode->i_blocks - 1) 327 size = (HFSPLUS_SB(sb).total_blocks & 328 (sb->s_blocksize * 8 - 1)) / 329 8 / sizeof(unsigned long); 330 else 331 size = sb->s_blocksize / sizeof(unsigned long); 332 data = (unsigned long *)bh->b_data; 333 do { 334 word = be32_to_cpu(data[off]); 335 if (!~word) 336 continue; 337 m = 1UL << (sizeof(unsigned long) * 8 - 1); 338 for (i = 0; m; i++, m >>= 1) { 339 if (word & m) 340 continue; 341 ablock = (blk << sb->s_blocksize_bits) * 8 + 342 off * sizeof(unsigned long) * 8 + i; 343 block_count = 1; 344 word |= m; 345 #if 0 346 while ((m >>= 1) && !(word & m)) { 347 block_count++; 348 word |= m; 349 } 350 #endif 351 data[off] = cpu_to_be32(word); 352 mark_buffer_dirty_inode(bh, anode); 353 brelse(bh); 354 goto found; 355 } 356 } while (++off < size); 357 brelse(bh); 358 if (++blk >= anode->i_blocks) 359 blk = 0; 360 if (blk == blk1) 361 return -ENOSPC; 362 } 363 364 found: 365 dprint(DBG_EXTENT, "extend %lu: %u,%u\n", inode->i_ino, ablock, block_count); 366 if (HFSPLUS_I(inode).alloc_blocks <= HFSPLUS_I(inode).extent_blocks) { 367 if (!HFSPLUS_I(inode).extent_blocks) { 368 dprint(DBG_EXTENT, "first extents\n"); 369 /* no extents yet */ 370 HFSPLUS_I(inode).extents[0].start_block = cpu_to_be32(ablock); 371 HFSPLUS_I(inode).extents[0].block_count = cpu_to_be32(block_count); 372 res = 0; 373 } else 374 /* try to append to extents in inode */ 375 res = hfsplus_add_extent(HFSPLUS_I(inode).extents, 376 HFSPLUS_I(inode).alloc_blocks, 377 ablock, block_count); 378 if (!res) { 379 hfsplus_dump_extent(HFSPLUS_I(inode).extents); 380 HFSPLUS_I(inode).extent_blocks += block_count; 381 } else if (res == -ENOSPC) { 382 /* create new extent, so find place to insert it */ 383 hfsplus_find_init(HFSPLUS_SB(sb).ext_tree, &fd); 384 hfsplus_fill_ext_key(fd.search_key, inode->i_ino, 385 HFSPLUS_I(inode).alloc_blocks, 386 HFSPLUS_IS_RSRC(inode) ? 387 HFSPLUS_TYPE_RSRC : HFSPLUS_TYPE_DATA); 388 res = hfsplus_find_extentry(&fd, ext_entry); 389 if (res && res != -ENOENT) { 390 hfsplus_find_exit(&fd); 391 goto out; 392 } 393 goto insert_extent; 394 } 395 } else { 396 hfsplus_find_init(HFSPLUS_SB(sb).ext_tree, &fd); 397 hfsplus_fill_ext_key(fd.search_key, inode->i_ino, 398 HFSPLUS_I(inode).alloc_blocks, 399 HFSPLUS_IS_RSRC(inode) ? 400 HFSPLUS_TYPE_RSRC : HFSPLUS_TYPE_DATA); 401 res = hfsplus_find_extentry(&fd, ext_entry); 402 if (res) { 403 hfsplus_find_exit(&fd); 404 goto out; 405 } 406 407 res = hfsplus_add_extent(ext_entry, HFSPLUS_I(inode).alloc_blocks - 408 be32_to_cpu(fd.key->ext.start_block), 409 ablock, block_count); 410 if (!res) { 411 hfsplus_dump_extent(ext_entry); 412 hfsplus_bnode_writebytes(fd.bnode, &ext_entry, 413 fd.entryoffset, 414 sizeof(ext_entry)); 415 } else if (res == -ENOSPC) 416 goto insert_extent; 417 hfsplus_find_exit(&fd); 418 } 419 out: 420 if (!res) { 421 HFSPLUS_I(inode).alloc_blocks += block_count; 422 mark_inode_dirty(inode); 423 HFSPLUS_SB(sb).free_blocks -= block_count; 424 sb->s_dirt = 1; 425 } 426 return res; 427 428 insert_extent: 429 dprint(DBG_EXTENT, "insert new extent\n"); 430 memset(ext_entry, 0, sizeof(ext_entry)); 431 ext_entry[0].start_block = cpu_to_be32(ablock); 432 ext_entry[0].block_count = cpu_to_be32(block_count); 433 434 hfsplus_bnode_insert_rec(&fd, ext_entry, sizeof(ext_entry)); 435 hfsplus_find_exit(&fd); 436 res = 0; 437 goto out; 438 } 439 440 void hfsplus_truncate(struct inode *inode) 441 { 442 struct super_block *sb = inode->i_sb; 443 struct hfsplus_find_data fd; 444 hfsplus_extent_rec ext_entry; 445 u32 blk_cnt, start; 446 int res; 447 448 dprint(DBG_INODE, "truncate: %lu, %Lu -> %Lu\n", inode->i_ino, 449 (long long)HFSPLUS_I(inode).mmu_private, inode->i_size); 450 if (inode->i_size == HFSPLUS_I(inode).mmu_private) 451 return; 452 if (inode->i_size > HFSPLUS_I(inode).mmu_private) { 453 struct address_space *mapping = inode->i_mapping; 454 struct page *page; 455 u32 size = inode->i_size - 1; 456 int res; 457 458 page = grab_cache_page(mapping, size >> PAGE_CACHE_SHIFT); 459 if (!page) 460 return; 461 size &= PAGE_CACHE_SIZE - 1; 462 size++; 463 res = mapping->a_ops->prepare_write(NULL, page, size, size); 464 if (!res) 465 res = mapping->a_ops->commit_write(NULL, page, size, size); 466 if (res) 467 inode->i_size = HFSPLUS_I(inode).mmu_private; 468 unlock_page(page); 469 page_cache_release(page); 470 mark_inode_dirty(inode); 471 return; 472 } 473 blk_cnt = (inode->i_size + sb->s_blocksize - 1) >> sb->s_blocksize_bits; 474 475 while (1) { 476 if (HFSPLUS_I(inode).alloc_blocks <= HFSPLUS_I(inode).extent_blocks) { 477 hfsplus_free_extents(sb, HFSPLUS_I(inode).extents, 478 HFSPLUS_I(inode).alloc_blocks, 479 HFSPLUS_I(inode).alloc_blocks - blk_cnt); 480 hfsplus_dump_extent(HFSPLUS_I(inode).extents); 481 HFSPLUS_I(inode).extent_blocks = blk_cnt; 482 break; 483 } 484 hfsplus_find_init(HFSPLUS_SB(sb).ext_tree, &fd); 485 hfsplus_fill_ext_key(fd.search_key, inode->i_ino, 486 HFSPLUS_I(inode).alloc_blocks, 487 HFSPLUS_IS_RSRC(inode) ? 488 HFSPLUS_TYPE_RSRC : HFSPLUS_TYPE_DATA); 489 res = hfsplus_find_extentry(&fd, ext_entry); 490 if (res) { 491 hfsplus_find_exit(&fd); 492 break; 493 } 494 start = be32_to_cpu(fd.key->ext.start_block); 495 hfsplus_free_extents(sb, ext_entry, 496 HFSPLUS_I(inode).alloc_blocks - start, 497 HFSPLUS_I(inode).alloc_blocks - blk_cnt); 498 hfsplus_dump_extent(ext_entry); 499 if (blk_cnt > start) { 500 hfsplus_bnode_writebytes(fd.bnode, &ext_entry, 501 fd.entryoffset, 502 sizeof(ext_entry)); 503 hfsplus_find_exit(&fd); 504 break; 505 } 506 HFSPLUS_I(inode).alloc_blocks = start; 507 hfsplus_bnode_remove_rec(&fd); 508 hfsplus_find_exit(&fd); 509 } 510 HFSPLUS_I(inode).mmu_private = inode->i_size; 511 HFSPLUS_I(inode).alloc_blocks = HFSPLUS_I(inode).total_blocks = blk_cnt; 512 }
Cache object: e8a5b3dc7054aeaea0146b4a39a6cdd2
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]