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