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