quotaio_tree.c revision a86d55da8bf41335aa2fc5ec16ca63859d918e81
1/* 2 * Implementation of new quotafile format 3 * 4 * Jan Kara <jack@suse.cz> - sponsored by SuSE CR 5 */ 6 7#include "config.h" 8#include <sys/types.h> 9#include <errno.h> 10#include <stdio.h> 11#include <stdlib.h> 12#include <string.h> 13#include <unistd.h> 14 15#include "common.h" 16#include "quotaio_tree.h" 17#include "quotaio.h" 18 19typedef char *dqbuf_t; 20 21#define freedqbuf(buf) ext2fs_free_mem(&buf) 22 23static inline dqbuf_t getdqbuf(void) 24{ 25 dqbuf_t buf; 26 if (ext2fs_get_memzero(QT_BLKSIZE, &buf)) { 27 log_err("Failed to allocate dqbuf", ""); 28 return NULL; 29 } 30 31 return buf; 32} 33 34/* Is given dquot empty? */ 35int qtree_entry_unused(struct qtree_mem_dqinfo *info, char *disk) 36{ 37 int i; 38 39 for (i = 0; i < info->dqi_entry_size; i++) 40 if (disk[i]) 41 return 0; 42 return 1; 43} 44 45int qtree_dqstr_in_blk(struct qtree_mem_dqinfo *info) 46{ 47 return (QT_BLKSIZE - sizeof(struct qt_disk_dqdbheader)) / 48 info->dqi_entry_size; 49} 50 51static int get_index(qid_t id, int depth) 52{ 53 return (id >> ((QT_TREEDEPTH - depth - 1) * 8)) & 0xff; 54} 55 56/* Read given block */ 57static void read_blk(struct quota_handle *h, uint blk, dqbuf_t buf) 58{ 59 int err; 60 61 err = h->e2fs_read(&h->qh_qf, blk << QT_BLKSIZE_BITS, buf, 62 QT_BLKSIZE); 63 if (err < 0) 64 log_err("Cannot read block %u: %s", blk, strerror(errno)); 65 else if (err != QT_BLKSIZE) 66 memset(buf + err, 0, QT_BLKSIZE - err); 67} 68 69/* Write block */ 70static int write_blk(struct quota_handle *h, uint blk, dqbuf_t buf) 71{ 72 int err; 73 74 err = h->e2fs_write(&h->qh_qf, blk << QT_BLKSIZE_BITS, buf, 75 QT_BLKSIZE); 76 if (err < 0 && errno != ENOSPC) 77 log_err("Cannot write block (%u): %s", blk, strerror(errno)); 78 if (err != QT_BLKSIZE) 79 return -ENOSPC; 80 return 0; 81} 82 83/* Get free block in file (either from free list or create new one) */ 84static int get_free_dqblk(struct quota_handle *h) 85{ 86 dqbuf_t buf = getdqbuf(); 87 struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf; 88 struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; 89 int blk; 90 91 if (!buf) 92 return -ENOMEM; 93 94 if (info->dqi_free_blk) { 95 blk = info->dqi_free_blk; 96 read_blk(h, blk, buf); 97 info->dqi_free_blk = ext2fs_le32_to_cpu(dh->dqdh_next_free); 98 } else { 99 memset(buf, 0, QT_BLKSIZE); 100 /* Assure block allocation... */ 101 if (write_blk(h, info->dqi_blocks, buf) < 0) { 102 freedqbuf(buf); 103 log_err("Cannot allocate new quota block " 104 "(out of disk space).", ""); 105 return -ENOSPC; 106 } 107 blk = info->dqi_blocks++; 108 } 109 mark_quotafile_info_dirty(h); 110 freedqbuf(buf); 111 return blk; 112} 113 114/* Put given block to free list */ 115static void put_free_dqblk(struct quota_handle *h, dqbuf_t buf, uint blk) 116{ 117 struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf; 118 struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; 119 120 dh->dqdh_next_free = ext2fs_cpu_to_le32(info->dqi_free_blk); 121 dh->dqdh_prev_free = ext2fs_cpu_to_le32(0); 122 dh->dqdh_entries = ext2fs_cpu_to_le16(0); 123 info->dqi_free_blk = blk; 124 mark_quotafile_info_dirty(h); 125 write_blk(h, blk, buf); 126} 127 128/* Remove given block from the list of blocks with free entries */ 129static void remove_free_dqentry(struct quota_handle *h, dqbuf_t buf, uint blk) 130{ 131 dqbuf_t tmpbuf = getdqbuf(); 132 struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf; 133 uint nextblk = ext2fs_le32_to_cpu(dh->dqdh_next_free), prevblk = 134 135 ext2fs_le32_to_cpu(dh->dqdh_prev_free); 136 137 if (!tmpbuf) 138 return; 139 140 if (nextblk) { 141 read_blk(h, nextblk, tmpbuf); 142 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free = 143 dh->dqdh_prev_free; 144 write_blk(h, nextblk, tmpbuf); 145 } 146 if (prevblk) { 147 read_blk(h, prevblk, tmpbuf); 148 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_next_free = 149 dh->dqdh_next_free; 150 write_blk(h, prevblk, tmpbuf); 151 } else { 152 h->qh_info.u.v2_mdqi.dqi_qtree.dqi_free_entry = nextblk; 153 mark_quotafile_info_dirty(h); 154 } 155 freedqbuf(tmpbuf); 156 dh->dqdh_next_free = dh->dqdh_prev_free = ext2fs_cpu_to_le32(0); 157 write_blk(h, blk, buf); /* No matter whether write succeeds 158 * block is out of list */ 159} 160 161/* Insert given block to the beginning of list with free entries */ 162static void insert_free_dqentry(struct quota_handle *h, dqbuf_t buf, uint blk) 163{ 164 dqbuf_t tmpbuf = getdqbuf(); 165 struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf; 166 struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; 167 168 if (!tmpbuf) 169 return; 170 171 dh->dqdh_next_free = ext2fs_cpu_to_le32(info->dqi_free_entry); 172 dh->dqdh_prev_free = ext2fs_cpu_to_le32(0); 173 write_blk(h, blk, buf); 174 if (info->dqi_free_entry) { 175 read_blk(h, info->dqi_free_entry, tmpbuf); 176 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free = 177 ext2fs_cpu_to_le32(blk); 178 write_blk(h, info->dqi_free_entry, tmpbuf); 179 } 180 freedqbuf(tmpbuf); 181 info->dqi_free_entry = blk; 182 mark_quotafile_info_dirty(h); 183} 184 185/* Find space for dquot */ 186static uint find_free_dqentry(struct quota_handle *h, struct dquot *dquot, 187 int *err) 188{ 189 int blk, i; 190 struct qt_disk_dqdbheader *dh; 191 struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; 192 char *ddquot; 193 dqbuf_t buf; 194 195 *err = 0; 196 buf = getdqbuf(); 197 if (!buf) { 198 *err = -ENOMEM; 199 return 0; 200 } 201 202 dh = (struct qt_disk_dqdbheader *)buf; 203 if (info->dqi_free_entry) { 204 blk = info->dqi_free_entry; 205 read_blk(h, blk, buf); 206 } else { 207 blk = get_free_dqblk(h); 208 if (blk < 0) { 209 freedqbuf(buf); 210 *err = blk; 211 return 0; 212 } 213 memset(buf, 0, QT_BLKSIZE); 214 info->dqi_free_entry = blk; 215 mark_quotafile_info_dirty(h); 216 } 217 218 /* Block will be full? */ 219 if (ext2fs_le16_to_cpu(dh->dqdh_entries) + 1 >= 220 qtree_dqstr_in_blk(info)) 221 remove_free_dqentry(h, buf, blk); 222 223 dh->dqdh_entries = 224 ext2fs_cpu_to_le16(ext2fs_le16_to_cpu(dh->dqdh_entries) + 1); 225 /* Find free structure in block */ 226 ddquot = buf + sizeof(struct qt_disk_dqdbheader); 227 for (i = 0; 228 i < qtree_dqstr_in_blk(info) && !qtree_entry_unused(info, ddquot); 229 i++) 230 ddquot += info->dqi_entry_size; 231 232 if (i == qtree_dqstr_in_blk(info)) 233 log_err("find_free_dqentry(): Data block full but it " 234 "shouldn't.", ""); 235 236 write_blk(h, blk, buf); 237 dquot->dq_dqb.u.v2_mdqb.dqb_off = 238 (blk << QT_BLKSIZE_BITS) + sizeof(struct qt_disk_dqdbheader) + 239 i * info->dqi_entry_size; 240 freedqbuf(buf); 241 return blk; 242} 243 244/* Insert reference to structure into the trie */ 245static int do_insert_tree(struct quota_handle *h, struct dquot *dquot, 246 uint * treeblk, int depth) 247{ 248 dqbuf_t buf; 249 int newson = 0, newact = 0; 250 u_int32_t *ref; 251 uint newblk; 252 int ret = 0; 253 254 log_debug("inserting in tree: treeblk=%u, depth=%d", *treeblk, depth); 255 buf = getdqbuf(); 256 if (!buf) 257 return -ENOMEM; 258 259 if (!*treeblk) { 260 ret = get_free_dqblk(h); 261 if (ret < 0) 262 goto out_buf; 263 *treeblk = ret; 264 memset(buf, 0, QT_BLKSIZE); 265 newact = 1; 266 } else { 267 read_blk(h, *treeblk, buf); 268 } 269 270 ref = (u_int32_t *) buf; 271 newblk = ext2fs_le32_to_cpu(ref[get_index(dquot->dq_id, depth)]); 272 if (!newblk) 273 newson = 1; 274 if (depth == QT_TREEDEPTH - 1) { 275 if (newblk) 276 log_err("Inserting already present quota entry " 277 "(block %u).", 278 ref[get_index(dquot->dq_id, depth)]); 279 newblk = find_free_dqentry(h, dquot, &ret); 280 } else { 281 ret = do_insert_tree(h, dquot, &newblk, depth + 1); 282 } 283 284 if (newson && ret >= 0) { 285 ref[get_index(dquot->dq_id, depth)] = 286 ext2fs_cpu_to_le32(newblk); 287 write_blk(h, *treeblk, buf); 288 } else if (newact && ret < 0) { 289 put_free_dqblk(h, buf, *treeblk); 290 } 291 292out_buf: 293 freedqbuf(buf); 294 return ret; 295} 296 297/* Wrapper for inserting quota structure into tree */ 298static void dq_insert_tree(struct quota_handle *h, struct dquot *dquot) 299{ 300 uint tmp = QT_TREEOFF; 301 302 if (do_insert_tree(h, dquot, &tmp, 0) < 0) 303 log_err("Cannot write quota (id %u): %s", 304 (uint) dquot->dq_id, strerror(errno)); 305} 306 307/* Write dquot to file */ 308void qtree_write_dquot(struct dquot *dquot) 309{ 310 ssize_t ret; 311 char *ddquot; 312 struct quota_handle *h = dquot->dq_h; 313 struct qtree_mem_dqinfo *info = 314 &dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree; 315 log_debug("writing ddquot 1: off=%llu, info->dqi_entry_size=%u", 316 dquot->dq_dqb.u.v2_mdqb.dqb_off, 317 info->dqi_entry_size); 318 ret = ext2fs_get_mem(info->dqi_entry_size, &ddquot); 319 if (ret) { 320 errno = ENOMEM; 321 log_err("Quota write failed (id %u): %s", 322 (uint)dquot->dq_id, strerror(errno)); 323 return; 324 } 325 326 if (!dquot->dq_dqb.u.v2_mdqb.dqb_off) 327 dq_insert_tree(dquot->dq_h, dquot); 328 info->dqi_ops->mem2disk_dqblk(ddquot, dquot); 329 log_debug("writing ddquot 2: off=%llu, info->dqi_entry_size=%u", 330 dquot->dq_dqb.u.v2_mdqb.dqb_off, 331 info->dqi_entry_size); 332 ret = h->e2fs_write(&h->qh_qf, dquot->dq_dqb.u.v2_mdqb.dqb_off, ddquot, 333 info->dqi_entry_size); 334 335 if (ret != info->dqi_entry_size) { 336 if (ret > 0) 337 errno = ENOSPC; 338 log_err("Quota write failed (id %u): %s", 339 (uint)dquot->dq_id, strerror(errno)); 340 } 341 ext2fs_free_mem(&ddquot); 342} 343 344/* Free dquot entry in data block */ 345static void free_dqentry(struct quota_handle *h, struct dquot *dquot, uint blk) 346{ 347 struct qt_disk_dqdbheader *dh; 348 struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; 349 dqbuf_t buf = getdqbuf(); 350 351 if (!buf) 352 return; 353 354 if (dquot->dq_dqb.u.v2_mdqb.dqb_off >> QT_BLKSIZE_BITS != blk) 355 log_err("Quota structure has offset to other block (%u) " 356 "than it should (%u).", blk, 357 (uint) (dquot->dq_dqb.u.v2_mdqb.dqb_off >> 358 QT_BLKSIZE_BITS)); 359 360 read_blk(h, blk, buf); 361 dh = (struct qt_disk_dqdbheader *)buf; 362 dh->dqdh_entries = 363 ext2fs_cpu_to_le16(ext2fs_le16_to_cpu(dh->dqdh_entries) - 1); 364 365 if (!ext2fs_le16_to_cpu(dh->dqdh_entries)) { /* Block got free? */ 366 remove_free_dqentry(h, buf, blk); 367 put_free_dqblk(h, buf, blk); 368 } else { 369 memset(buf + (dquot->dq_dqb.u.v2_mdqb.dqb_off & 370 ((1 << QT_BLKSIZE_BITS) - 1)), 371 0, info->dqi_entry_size); 372 373 /* First free entry? */ 374 if (ext2fs_le16_to_cpu(dh->dqdh_entries) == 375 qtree_dqstr_in_blk(info) - 1) 376 /* This will also write data block */ 377 insert_free_dqentry(h, buf, blk); 378 else 379 write_blk(h, blk, buf); 380 } 381 dquot->dq_dqb.u.v2_mdqb.dqb_off = 0; 382 freedqbuf(buf); 383} 384 385/* Remove reference to dquot from tree */ 386static void remove_tree(struct quota_handle *h, struct dquot *dquot, 387 uint * blk, int depth) 388{ 389 dqbuf_t buf = getdqbuf(); 390 uint newblk; 391 u_int32_t *ref = (u_int32_t *) buf; 392 393 if (!buf) 394 return; 395 396 read_blk(h, *blk, buf); 397 newblk = ext2fs_le32_to_cpu(ref[get_index(dquot->dq_id, depth)]); 398 if (depth == QT_TREEDEPTH - 1) { 399 free_dqentry(h, dquot, newblk); 400 newblk = 0; 401 } else { 402 remove_tree(h, dquot, &newblk, depth + 1); 403 } 404 405 if (!newblk) { 406 int i; 407 408 ref[get_index(dquot->dq_id, depth)] = ext2fs_cpu_to_le32(0); 409 410 /* Block got empty? */ 411 for (i = 0; i < QT_BLKSIZE && !buf[i]; i++); 412 413 /* Don't put the root block into the free block list */ 414 if (i == QT_BLKSIZE && *blk != QT_TREEOFF) { 415 put_free_dqblk(h, buf, *blk); 416 *blk = 0; 417 } else { 418 write_blk(h, *blk, buf); 419 } 420 } 421 freedqbuf(buf); 422} 423 424/* Delete dquot from tree */ 425void qtree_delete_dquot(struct dquot *dquot) 426{ 427 uint tmp = QT_TREEOFF; 428 429 if (!dquot->dq_dqb.u.v2_mdqb.dqb_off) /* Even not allocated? */ 430 return; 431 remove_tree(dquot->dq_h, dquot, &tmp, 0); 432} 433 434/* Find entry in block */ 435static ext2_loff_t find_block_dqentry(struct quota_handle *h, 436 struct dquot *dquot, uint blk) 437{ 438 struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; 439 dqbuf_t buf = getdqbuf(); 440 int i; 441 char *ddquot = buf + sizeof(struct qt_disk_dqdbheader); 442 443 if (!buf) 444 return -ENOMEM; 445 446 read_blk(h, blk, buf); 447 for (i = 0; 448 i < qtree_dqstr_in_blk(info) && !info->dqi_ops->is_id(ddquot, dquot); 449 i++) 450 ddquot += info->dqi_entry_size; 451 452 if (i == qtree_dqstr_in_blk(info)) 453 log_err("Quota for id %u referenced but not present.", 454 dquot->dq_id); 455 freedqbuf(buf); 456 return (blk << QT_BLKSIZE_BITS) + sizeof(struct qt_disk_dqdbheader) + 457 i * info->dqi_entry_size; 458} 459 460/* Find entry for given id in the tree */ 461static ext2_loff_t find_tree_dqentry(struct quota_handle *h, 462 struct dquot *dquot, 463 uint blk, int depth) 464{ 465 dqbuf_t buf = getdqbuf(); 466 ext2_loff_t ret = 0; 467 u_int32_t *ref = (u_int32_t *) buf; 468 469 if (!buf) 470 return -ENOMEM; 471 472 read_blk(h, blk, buf); 473 ret = 0; 474 blk = ext2fs_le32_to_cpu(ref[get_index(dquot->dq_id, depth)]); 475 if (!blk) /* No reference? */ 476 goto out_buf; 477 if (depth < QT_TREEDEPTH - 1) 478 ret = find_tree_dqentry(h, dquot, blk, depth + 1); 479 else 480 ret = find_block_dqentry(h, dquot, blk); 481out_buf: 482 freedqbuf(buf); 483 return ret; 484} 485 486/* Find entry for given id in the tree - wrapper function */ 487static inline ext2_loff_t find_dqentry(struct quota_handle *h, 488 struct dquot *dquot) 489{ 490 return find_tree_dqentry(h, dquot, QT_TREEOFF, 0); 491} 492 493/* 494 * Read dquot from disk. 495 */ 496struct dquot *qtree_read_dquot(struct quota_handle *h, qid_t id) 497{ 498 struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; 499 ext2_loff_t offset; 500 ssize_t ret; 501 char *ddquot; 502 struct dquot *dquot = get_empty_dquot(); 503 504 if (!dquot) 505 return NULL; 506 if (ext2fs_get_mem(info->dqi_entry_size, &ddquot)) { 507 ext2fs_free_mem(&dquot); 508 return NULL; 509 } 510 511 dquot->dq_id = id; 512 dquot->dq_h = h; 513 dquot->dq_dqb.u.v2_mdqb.dqb_off = 0; 514 memset(&dquot->dq_dqb, 0, sizeof(struct util_dqblk)); 515 516 offset = find_dqentry(h, dquot); 517 if (offset > 0) { 518 dquot->dq_dqb.u.v2_mdqb.dqb_off = offset; 519 ret = h->e2fs_read(&h->qh_qf, offset, ddquot, 520 info->dqi_entry_size); 521 if (ret != info->dqi_entry_size) { 522 if (ret > 0) 523 errno = EIO; 524 log_err("Cannot read quota structure for id %u: %s", 525 dquot->dq_id, strerror(errno)); 526 } 527 info->dqi_ops->disk2mem_dqblk(dquot, ddquot); 528 } 529 ext2fs_free_mem(&ddquot); 530 return dquot; 531} 532 533/* 534 * Scan all dquots in file and call callback on each 535 */ 536#define set_bit(bmp, ind) ((bmp)[(ind) >> 3] |= (1 << ((ind) & 7))) 537#define get_bit(bmp, ind) ((bmp)[(ind) >> 3] & (1 << ((ind) & 7))) 538 539static int report_block(struct dquot *dquot, uint blk, char *bitmap, 540 int (*process_dquot) (struct dquot *, char *)) 541{ 542 struct qtree_mem_dqinfo *info = 543 &dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree; 544 dqbuf_t buf = getdqbuf(); 545 struct qt_disk_dqdbheader *dh; 546 char *ddata; 547 int entries, i; 548 549 if (!buf) 550 return 0; 551 552 set_bit(bitmap, blk); 553 read_blk(dquot->dq_h, blk, buf); 554 dh = (struct qt_disk_dqdbheader *)buf; 555 ddata = buf + sizeof(struct qt_disk_dqdbheader); 556 entries = ext2fs_le16_to_cpu(dh->dqdh_entries); 557 for (i = 0; i < qtree_dqstr_in_blk(info); 558 i++, ddata += info->dqi_entry_size) 559 if (!qtree_entry_unused(info, ddata)) { 560 info->dqi_ops->disk2mem_dqblk(dquot, ddata); 561 if (process_dquot(dquot, NULL) < 0) 562 break; 563 } 564 freedqbuf(buf); 565 return entries; 566} 567 568static void check_reference(struct quota_handle *h, uint blk) 569{ 570 if (blk >= h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks) 571 log_err("Illegal reference (%u >= %u) in %s quota file. " 572 "Quota file is probably corrupted.\n" 573 "Please run e2fsck (8) to fix it.", 574 blk, 575 h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks, 576 type2name(h->qh_type)); 577} 578 579static int report_tree(struct dquot *dquot, uint blk, int depth, char *bitmap, 580 int (*process_dquot) (struct dquot *, char *)) 581{ 582 int entries = 0, i; 583 dqbuf_t buf = getdqbuf(); 584 u_int32_t *ref = (u_int32_t *) buf; 585 586 if (!buf) 587 return 0; 588 589 read_blk(dquot->dq_h, blk, buf); 590 if (depth == QT_TREEDEPTH - 1) { 591 for (i = 0; i < QT_BLKSIZE >> 2; i++) { 592 blk = ext2fs_le32_to_cpu(ref[i]); 593 check_reference(dquot->dq_h, blk); 594 if (blk && !get_bit(bitmap, blk)) 595 entries += report_block(dquot, blk, bitmap, 596 process_dquot); 597 } 598 } else { 599 for (i = 0; i < QT_BLKSIZE >> 2; i++) 600 blk = ext2fs_le32_to_cpu(ref[i]); 601 if (blk) { 602 check_reference(dquot->dq_h, blk); 603 entries += report_tree(dquot, blk, depth + 1, 604 bitmap, process_dquot); 605 } 606 } 607 freedqbuf(buf); 608 return entries; 609} 610 611static uint find_set_bits(char *bmp, int blocks) 612{ 613 uint i, used = 0; 614 615 for (i = 0; i < blocks; i++) 616 if (get_bit(bmp, i)) 617 used++; 618 return used; 619} 620 621int qtree_scan_dquots(struct quota_handle *h, 622 int (*process_dquot) (struct dquot *, char *)) 623{ 624 char *bitmap; 625 struct v2_mem_dqinfo *v2info = &h->qh_info.u.v2_mdqi; 626 struct qtree_mem_dqinfo *info = &v2info->dqi_qtree; 627 struct dquot *dquot = get_empty_dquot(); 628 629 if (!dquot) 630 return -1; 631 632 dquot->dq_h = h; 633 if (ext2fs_get_memzero((info->dqi_blocks + 7) >> 3, &bitmap)) { 634 ext2fs_free_mem(&dquot); 635 return -1; 636 } 637 v2info->dqi_used_entries = report_tree(dquot, QT_TREEOFF, 0, bitmap, 638 process_dquot); 639 v2info->dqi_data_blocks = find_set_bits(bitmap, info->dqi_blocks); 640 ext2fs_free_mem(&bitmap); 641 ext2fs_free_mem(&dquot); 642 return 0; 643} 644