1/* 2 * vfsv0 quota IO operations on file 3 */ 4 5#include <linux/errno.h> 6#include <linux/fs.h> 7#include <linux/mount.h> 8#include <linux/dqblk_v2.h> 9#include <linux/kernel.h> 10#include <linux/init.h> 11#include <linux/module.h> 12#include <linux/slab.h> 13#include <linux/quotaops.h> 14 15#include <asm/byteorder.h> 16 17#include "quota_tree.h" 18 19MODULE_AUTHOR("Jan Kara"); 20MODULE_DESCRIPTION("Quota trie support"); 21MODULE_LICENSE("GPL"); 22 23#define __QUOTA_QT_PARANOIA 24 25static int get_index(struct qtree_mem_dqinfo *info, qid_t id, int depth) 26{ 27 unsigned int epb = info->dqi_usable_bs >> 2; 28 29 depth = info->dqi_qtree_depth - depth - 1; 30 while (depth--) 31 id /= epb; 32 return id % epb; 33} 34 35/* Number of entries in one blocks */ 36static int qtree_dqstr_in_blk(struct qtree_mem_dqinfo *info) 37{ 38 return (info->dqi_usable_bs - sizeof(struct qt_disk_dqdbheader)) 39 / info->dqi_entry_size; 40} 41 42static char *getdqbuf(size_t size) 43{ 44 char *buf = kmalloc(size, GFP_NOFS); 45 if (!buf) 46 printk(KERN_WARNING 47 "VFS: Not enough memory for quota buffers.\n"); 48 return buf; 49} 50 51static ssize_t read_blk(struct qtree_mem_dqinfo *info, uint blk, char *buf) 52{ 53 struct super_block *sb = info->dqi_sb; 54 55 memset(buf, 0, info->dqi_usable_bs); 56 return sb->s_op->quota_read(sb, info->dqi_type, buf, 57 info->dqi_usable_bs, blk << info->dqi_blocksize_bits); 58} 59 60static ssize_t write_blk(struct qtree_mem_dqinfo *info, uint blk, char *buf) 61{ 62 struct super_block *sb = info->dqi_sb; 63 ssize_t ret; 64 65 ret = sb->s_op->quota_write(sb, info->dqi_type, buf, 66 info->dqi_usable_bs, blk << info->dqi_blocksize_bits); 67 if (ret != info->dqi_usable_bs) { 68 quota_error(sb, "dquota write failed"); 69 if (ret >= 0) 70 ret = -EIO; 71 } 72 return ret; 73} 74 75/* Remove empty block from list and return it */ 76static int get_free_dqblk(struct qtree_mem_dqinfo *info) 77{ 78 char *buf = getdqbuf(info->dqi_usable_bs); 79 struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf; 80 int ret, blk; 81 82 if (!buf) 83 return -ENOMEM; 84 if (info->dqi_free_blk) { 85 blk = info->dqi_free_blk; 86 ret = read_blk(info, blk, buf); 87 if (ret < 0) 88 goto out_buf; 89 info->dqi_free_blk = le32_to_cpu(dh->dqdh_next_free); 90 } 91 else { 92 memset(buf, 0, info->dqi_usable_bs); 93 /* Assure block allocation... */ 94 ret = write_blk(info, info->dqi_blocks, buf); 95 if (ret < 0) 96 goto out_buf; 97 blk = info->dqi_blocks++; 98 } 99 mark_info_dirty(info->dqi_sb, info->dqi_type); 100 ret = blk; 101out_buf: 102 kfree(buf); 103 return ret; 104} 105 106/* Insert empty block to the list */ 107static int put_free_dqblk(struct qtree_mem_dqinfo *info, char *buf, uint blk) 108{ 109 struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf; 110 int err; 111 112 dh->dqdh_next_free = cpu_to_le32(info->dqi_free_blk); 113 dh->dqdh_prev_free = cpu_to_le32(0); 114 dh->dqdh_entries = cpu_to_le16(0); 115 err = write_blk(info, blk, buf); 116 if (err < 0) 117 return err; 118 info->dqi_free_blk = blk; 119 mark_info_dirty(info->dqi_sb, info->dqi_type); 120 return 0; 121} 122 123/* Remove given block from the list of blocks with free entries */ 124static int remove_free_dqentry(struct qtree_mem_dqinfo *info, char *buf, 125 uint blk) 126{ 127 char *tmpbuf = getdqbuf(info->dqi_usable_bs); 128 struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf; 129 uint nextblk = le32_to_cpu(dh->dqdh_next_free); 130 uint prevblk = le32_to_cpu(dh->dqdh_prev_free); 131 int err; 132 133 if (!tmpbuf) 134 return -ENOMEM; 135 if (nextblk) { 136 err = read_blk(info, nextblk, tmpbuf); 137 if (err < 0) 138 goto out_buf; 139 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free = 140 dh->dqdh_prev_free; 141 err = write_blk(info, nextblk, tmpbuf); 142 if (err < 0) 143 goto out_buf; 144 } 145 if (prevblk) { 146 err = read_blk(info, prevblk, tmpbuf); 147 if (err < 0) 148 goto out_buf; 149 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_next_free = 150 dh->dqdh_next_free; 151 err = write_blk(info, prevblk, tmpbuf); 152 if (err < 0) 153 goto out_buf; 154 } else { 155 info->dqi_free_entry = nextblk; 156 mark_info_dirty(info->dqi_sb, info->dqi_type); 157 } 158 kfree(tmpbuf); 159 dh->dqdh_next_free = dh->dqdh_prev_free = cpu_to_le32(0); 160 /* No matter whether write succeeds block is out of list */ 161 if (write_blk(info, blk, buf) < 0) 162 quota_error(info->dqi_sb, "Can't write block (%u) " 163 "with free entries", blk); 164 return 0; 165out_buf: 166 kfree(tmpbuf); 167 return err; 168} 169 170/* Insert given block to the beginning of list with free entries */ 171static int insert_free_dqentry(struct qtree_mem_dqinfo *info, char *buf, 172 uint blk) 173{ 174 char *tmpbuf = getdqbuf(info->dqi_usable_bs); 175 struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf; 176 int err; 177 178 if (!tmpbuf) 179 return -ENOMEM; 180 dh->dqdh_next_free = cpu_to_le32(info->dqi_free_entry); 181 dh->dqdh_prev_free = cpu_to_le32(0); 182 err = write_blk(info, blk, buf); 183 if (err < 0) 184 goto out_buf; 185 if (info->dqi_free_entry) { 186 err = read_blk(info, info->dqi_free_entry, tmpbuf); 187 if (err < 0) 188 goto out_buf; 189 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free = 190 cpu_to_le32(blk); 191 err = write_blk(info, info->dqi_free_entry, tmpbuf); 192 if (err < 0) 193 goto out_buf; 194 } 195 kfree(tmpbuf); 196 info->dqi_free_entry = blk; 197 mark_info_dirty(info->dqi_sb, info->dqi_type); 198 return 0; 199out_buf: 200 kfree(tmpbuf); 201 return err; 202} 203 204/* Is the entry in the block free? */ 205int qtree_entry_unused(struct qtree_mem_dqinfo *info, char *disk) 206{ 207 int i; 208 209 for (i = 0; i < info->dqi_entry_size; i++) 210 if (disk[i]) 211 return 0; 212 return 1; 213} 214EXPORT_SYMBOL(qtree_entry_unused); 215 216/* Find space for dquot */ 217static uint find_free_dqentry(struct qtree_mem_dqinfo *info, 218 struct dquot *dquot, int *err) 219{ 220 uint blk, i; 221 struct qt_disk_dqdbheader *dh; 222 char *buf = getdqbuf(info->dqi_usable_bs); 223 char *ddquot; 224 225 *err = 0; 226 if (!buf) { 227 *err = -ENOMEM; 228 return 0; 229 } 230 dh = (struct qt_disk_dqdbheader *)buf; 231 if (info->dqi_free_entry) { 232 blk = info->dqi_free_entry; 233 *err = read_blk(info, blk, buf); 234 if (*err < 0) 235 goto out_buf; 236 } else { 237 blk = get_free_dqblk(info); 238 if ((int)blk < 0) { 239 *err = blk; 240 kfree(buf); 241 return 0; 242 } 243 memset(buf, 0, info->dqi_usable_bs); 244 /* This is enough as the block is already zeroed and the entry 245 * list is empty... */ 246 info->dqi_free_entry = blk; 247 mark_info_dirty(dquot->dq_sb, dquot->dq_type); 248 } 249 /* Block will be full? */ 250 if (le16_to_cpu(dh->dqdh_entries) + 1 >= qtree_dqstr_in_blk(info)) { 251 *err = remove_free_dqentry(info, buf, blk); 252 if (*err < 0) { 253 quota_error(dquot->dq_sb, "Can't remove block (%u) " 254 "from entry free list", blk); 255 goto out_buf; 256 } 257 } 258 le16_add_cpu(&dh->dqdh_entries, 1); 259 /* Find free structure in block */ 260 ddquot = buf + sizeof(struct qt_disk_dqdbheader); 261 for (i = 0; i < qtree_dqstr_in_blk(info); i++) { 262 if (qtree_entry_unused(info, ddquot)) 263 break; 264 ddquot += info->dqi_entry_size; 265 } 266#ifdef __QUOTA_QT_PARANOIA 267 if (i == qtree_dqstr_in_blk(info)) { 268 quota_error(dquot->dq_sb, "Data block full but it shouldn't"); 269 *err = -EIO; 270 goto out_buf; 271 } 272#endif 273 *err = write_blk(info, blk, buf); 274 if (*err < 0) { 275 quota_error(dquot->dq_sb, "Can't write quota data block %u", 276 blk); 277 goto out_buf; 278 } 279 dquot->dq_off = (blk << info->dqi_blocksize_bits) + 280 sizeof(struct qt_disk_dqdbheader) + 281 i * info->dqi_entry_size; 282 kfree(buf); 283 return blk; 284out_buf: 285 kfree(buf); 286 return 0; 287} 288 289/* Insert reference to structure into the trie */ 290static int do_insert_tree(struct qtree_mem_dqinfo *info, struct dquot *dquot, 291 uint *treeblk, int depth) 292{ 293 char *buf = getdqbuf(info->dqi_usable_bs); 294 int ret = 0, newson = 0, newact = 0; 295 __le32 *ref; 296 uint newblk; 297 298 if (!buf) 299 return -ENOMEM; 300 if (!*treeblk) { 301 ret = get_free_dqblk(info); 302 if (ret < 0) 303 goto out_buf; 304 *treeblk = ret; 305 memset(buf, 0, info->dqi_usable_bs); 306 newact = 1; 307 } else { 308 ret = read_blk(info, *treeblk, buf); 309 if (ret < 0) { 310 quota_error(dquot->dq_sb, "Can't read tree quota " 311 "block %u", *treeblk); 312 goto out_buf; 313 } 314 } 315 ref = (__le32 *)buf; 316 newblk = le32_to_cpu(ref[get_index(info, dquot->dq_id, depth)]); 317 if (!newblk) 318 newson = 1; 319 if (depth == info->dqi_qtree_depth - 1) { 320#ifdef __QUOTA_QT_PARANOIA 321 if (newblk) { 322 quota_error(dquot->dq_sb, "Inserting already present " 323 "quota entry (block %u)", 324 le32_to_cpu(ref[get_index(info, 325 dquot->dq_id, depth)])); 326 ret = -EIO; 327 goto out_buf; 328 } 329#endif 330 newblk = find_free_dqentry(info, dquot, &ret); 331 } else { 332 ret = do_insert_tree(info, dquot, &newblk, depth+1); 333 } 334 if (newson && ret >= 0) { 335 ref[get_index(info, dquot->dq_id, depth)] = 336 cpu_to_le32(newblk); 337 ret = write_blk(info, *treeblk, buf); 338 } else if (newact && ret < 0) { 339 put_free_dqblk(info, buf, *treeblk); 340 } 341out_buf: 342 kfree(buf); 343 return ret; 344} 345 346/* Wrapper for inserting quota structure into tree */ 347static inline int dq_insert_tree(struct qtree_mem_dqinfo *info, 348 struct dquot *dquot) 349{ 350 int tmp = QT_TREEOFF; 351 return do_insert_tree(info, dquot, &tmp, 0); 352} 353 354/* 355 * We don't have to be afraid of deadlocks as we never have quotas on quota 356 * files... 357 */ 358int qtree_write_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot) 359{ 360 int type = dquot->dq_type; 361 struct super_block *sb = dquot->dq_sb; 362 ssize_t ret; 363 char *ddquot = getdqbuf(info->dqi_entry_size); 364 365 if (!ddquot) 366 return -ENOMEM; 367 368 /* dq_off is guarded by dqio_mutex */ 369 if (!dquot->dq_off) { 370 ret = dq_insert_tree(info, dquot); 371 if (ret < 0) { 372 quota_error(sb, "Error %zd occurred while creating " 373 "quota", ret); 374 kfree(ddquot); 375 return ret; 376 } 377 } 378 spin_lock(&dq_data_lock); 379 info->dqi_ops->mem2disk_dqblk(ddquot, dquot); 380 spin_unlock(&dq_data_lock); 381 ret = sb->s_op->quota_write(sb, type, ddquot, info->dqi_entry_size, 382 dquot->dq_off); 383 if (ret != info->dqi_entry_size) { 384 quota_error(sb, "dquota write failed"); 385 if (ret >= 0) 386 ret = -ENOSPC; 387 } else { 388 ret = 0; 389 } 390 dqstats_inc(DQST_WRITES); 391 kfree(ddquot); 392 393 return ret; 394} 395EXPORT_SYMBOL(qtree_write_dquot); 396 397/* Free dquot entry in data block */ 398static int free_dqentry(struct qtree_mem_dqinfo *info, struct dquot *dquot, 399 uint blk) 400{ 401 struct qt_disk_dqdbheader *dh; 402 char *buf = getdqbuf(info->dqi_usable_bs); 403 int ret = 0; 404 405 if (!buf) 406 return -ENOMEM; 407 if (dquot->dq_off >> info->dqi_blocksize_bits != blk) { 408 quota_error(dquot->dq_sb, "Quota structure has offset to " 409 "other block (%u) than it should (%u)", blk, 410 (uint)(dquot->dq_off >> info->dqi_blocksize_bits)); 411 goto out_buf; 412 } 413 ret = read_blk(info, blk, buf); 414 if (ret < 0) { 415 quota_error(dquot->dq_sb, "Can't read quota data block %u", 416 blk); 417 goto out_buf; 418 } 419 dh = (struct qt_disk_dqdbheader *)buf; 420 le16_add_cpu(&dh->dqdh_entries, -1); 421 if (!le16_to_cpu(dh->dqdh_entries)) { /* Block got free? */ 422 ret = remove_free_dqentry(info, buf, blk); 423 if (ret >= 0) 424 ret = put_free_dqblk(info, buf, blk); 425 if (ret < 0) { 426 quota_error(dquot->dq_sb, "Can't move quota data block " 427 "(%u) to free list", blk); 428 goto out_buf; 429 } 430 } else { 431 memset(buf + 432 (dquot->dq_off & ((1 << info->dqi_blocksize_bits) - 1)), 433 0, info->dqi_entry_size); 434 if (le16_to_cpu(dh->dqdh_entries) == 435 qtree_dqstr_in_blk(info) - 1) { 436 /* Insert will write block itself */ 437 ret = insert_free_dqentry(info, buf, blk); 438 if (ret < 0) { 439 quota_error(dquot->dq_sb, "Can't insert quota " 440 "data block (%u) to free entry list", blk); 441 goto out_buf; 442 } 443 } else { 444 ret = write_blk(info, blk, buf); 445 if (ret < 0) { 446 quota_error(dquot->dq_sb, "Can't write quota " 447 "data block %u", blk); 448 goto out_buf; 449 } 450 } 451 } 452 dquot->dq_off = 0; /* Quota is now unattached */ 453out_buf: 454 kfree(buf); 455 return ret; 456} 457 458/* Remove reference to dquot from tree */ 459static int remove_tree(struct qtree_mem_dqinfo *info, struct dquot *dquot, 460 uint *blk, int depth) 461{ 462 char *buf = getdqbuf(info->dqi_usable_bs); 463 int ret = 0; 464 uint newblk; 465 __le32 *ref = (__le32 *)buf; 466 467 if (!buf) 468 return -ENOMEM; 469 ret = read_blk(info, *blk, buf); 470 if (ret < 0) { 471 quota_error(dquot->dq_sb, "Can't read quota data " 472 "block %u", blk); 473 goto out_buf; 474 } 475 newblk = le32_to_cpu(ref[get_index(info, dquot->dq_id, depth)]); 476 if (depth == info->dqi_qtree_depth - 1) { 477 ret = free_dqentry(info, dquot, newblk); 478 newblk = 0; 479 } else { 480 ret = remove_tree(info, dquot, &newblk, depth+1); 481 } 482 if (ret >= 0 && !newblk) { 483 int i; 484 ref[get_index(info, dquot->dq_id, depth)] = cpu_to_le32(0); 485 /* Block got empty? */ 486 for (i = 0; i < (info->dqi_usable_bs >> 2) && !ref[i]; i++) 487 ; 488 /* Don't put the root block into the free block list */ 489 if (i == (info->dqi_usable_bs >> 2) 490 && *blk != QT_TREEOFF) { 491 put_free_dqblk(info, buf, *blk); 492 *blk = 0; 493 } else { 494 ret = write_blk(info, *blk, buf); 495 if (ret < 0) 496 quota_error(dquot->dq_sb, "Can't write quota " 497 "tree block %u", blk); 498 } 499 } 500out_buf: 501 kfree(buf); 502 return ret; 503} 504 505/* Delete dquot from tree */ 506int qtree_delete_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot) 507{ 508 uint tmp = QT_TREEOFF; 509 510 if (!dquot->dq_off) /* Even not allocated? */ 511 return 0; 512 return remove_tree(info, dquot, &tmp, 0); 513} 514EXPORT_SYMBOL(qtree_delete_dquot); 515 516/* Find entry in block */ 517static loff_t find_block_dqentry(struct qtree_mem_dqinfo *info, 518 struct dquot *dquot, uint blk) 519{ 520 char *buf = getdqbuf(info->dqi_usable_bs); 521 loff_t ret = 0; 522 int i; 523 char *ddquot; 524 525 if (!buf) 526 return -ENOMEM; 527 ret = read_blk(info, blk, buf); 528 if (ret < 0) { 529 quota_error(dquot->dq_sb, "Can't read quota tree " 530 "block %u", blk); 531 goto out_buf; 532 } 533 ddquot = buf + sizeof(struct qt_disk_dqdbheader); 534 for (i = 0; i < qtree_dqstr_in_blk(info); i++) { 535 if (info->dqi_ops->is_id(ddquot, dquot)) 536 break; 537 ddquot += info->dqi_entry_size; 538 } 539 if (i == qtree_dqstr_in_blk(info)) { 540 quota_error(dquot->dq_sb, "Quota for id %u referenced " 541 "but not present", dquot->dq_id); 542 ret = -EIO; 543 goto out_buf; 544 } else { 545 ret = (blk << info->dqi_blocksize_bits) + sizeof(struct 546 qt_disk_dqdbheader) + i * info->dqi_entry_size; 547 } 548out_buf: 549 kfree(buf); 550 return ret; 551} 552 553/* Find entry for given id in the tree */ 554static loff_t find_tree_dqentry(struct qtree_mem_dqinfo *info, 555 struct dquot *dquot, uint blk, int depth) 556{ 557 char *buf = getdqbuf(info->dqi_usable_bs); 558 loff_t ret = 0; 559 __le32 *ref = (__le32 *)buf; 560 561 if (!buf) 562 return -ENOMEM; 563 ret = read_blk(info, blk, buf); 564 if (ret < 0) { 565 quota_error(dquot->dq_sb, "Can't read quota tree block %u", 566 blk); 567 goto out_buf; 568 } 569 ret = 0; 570 blk = le32_to_cpu(ref[get_index(info, dquot->dq_id, depth)]); 571 if (!blk) /* No reference? */ 572 goto out_buf; 573 if (depth < info->dqi_qtree_depth - 1) 574 ret = find_tree_dqentry(info, dquot, blk, depth+1); 575 else 576 ret = find_block_dqentry(info, dquot, blk); 577out_buf: 578 kfree(buf); 579 return ret; 580} 581 582/* Find entry for given id in the tree - wrapper function */ 583static inline loff_t find_dqentry(struct qtree_mem_dqinfo *info, 584 struct dquot *dquot) 585{ 586 return find_tree_dqentry(info, dquot, QT_TREEOFF, 0); 587} 588 589int qtree_read_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot) 590{ 591 int type = dquot->dq_type; 592 struct super_block *sb = dquot->dq_sb; 593 loff_t offset; 594 char *ddquot; 595 int ret = 0; 596 597#ifdef __QUOTA_QT_PARANOIA 598 /* Invalidated quota? */ 599 if (!sb_dqopt(dquot->dq_sb)->files[type]) { 600 quota_error(sb, "Quota invalidated while reading!"); 601 return -EIO; 602 } 603#endif 604 /* Do we know offset of the dquot entry in the quota file? */ 605 if (!dquot->dq_off) { 606 offset = find_dqentry(info, dquot); 607 if (offset <= 0) { /* Entry not present? */ 608 if (offset < 0) 609 quota_error(sb, "Can't read quota structure " 610 "for id %u", dquot->dq_id); 611 dquot->dq_off = 0; 612 set_bit(DQ_FAKE_B, &dquot->dq_flags); 613 memset(&dquot->dq_dqb, 0, sizeof(struct mem_dqblk)); 614 ret = offset; 615 goto out; 616 } 617 dquot->dq_off = offset; 618 } 619 ddquot = getdqbuf(info->dqi_entry_size); 620 if (!ddquot) 621 return -ENOMEM; 622 ret = sb->s_op->quota_read(sb, type, ddquot, info->dqi_entry_size, 623 dquot->dq_off); 624 if (ret != info->dqi_entry_size) { 625 if (ret >= 0) 626 ret = -EIO; 627 quota_error(sb, "Error while reading quota structure for id %u", 628 dquot->dq_id); 629 set_bit(DQ_FAKE_B, &dquot->dq_flags); 630 memset(&dquot->dq_dqb, 0, sizeof(struct mem_dqblk)); 631 kfree(ddquot); 632 goto out; 633 } 634 spin_lock(&dq_data_lock); 635 info->dqi_ops->disk2mem_dqblk(dquot, ddquot); 636 if (!dquot->dq_dqb.dqb_bhardlimit && 637 !dquot->dq_dqb.dqb_bsoftlimit && 638 !dquot->dq_dqb.dqb_ihardlimit && 639 !dquot->dq_dqb.dqb_isoftlimit) 640 set_bit(DQ_FAKE_B, &dquot->dq_flags); 641 spin_unlock(&dq_data_lock); 642 kfree(ddquot); 643out: 644 dqstats_inc(DQST_READS); 645 return ret; 646} 647EXPORT_SYMBOL(qtree_read_dquot); 648 649/* Check whether dquot should not be deleted. We know we are 650 * the only one operating on dquot (thanks to dq_lock) */ 651int qtree_release_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot) 652{ 653 if (test_bit(DQ_FAKE_B, &dquot->dq_flags) && 654 !(dquot->dq_dqb.dqb_curinodes | dquot->dq_dqb.dqb_curspace)) 655 return qtree_delete_dquot(info, dquot); 656 return 0; 657} 658EXPORT_SYMBOL(qtree_release_dquot); 659