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