quotaio_tree.c revision 38a420bfce58a4f32685e41104cd1dc4fd7d5013
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 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 loff_t find_tree_dqentry(struct quota_handle *h, struct dquot *dquot, 419 uint blk, int depth) 420{ 421 dqbuf_t buf = getdqbuf(); 422 loff_t ret = 0; 423 u_int32_t *ref = (u_int32_t *) buf; 424 425 read_blk(h, blk, buf); 426 ret = 0; 427 blk = ext2fs_le32_to_cpu(ref[get_index(dquot->dq_id, depth)]); 428 if (!blk) /* No reference? */ 429 goto out_buf; 430 if (depth < QT_TREEDEPTH - 1) 431 ret = find_tree_dqentry(h, dquot, blk, depth + 1); 432 else 433 ret = find_block_dqentry(h, dquot, blk); 434out_buf: 435 freedqbuf(buf); 436 return ret; 437} 438 439/* Find entry for given id in the tree - wrapper function */ 440static inline loff_t find_dqentry(struct quota_handle *h, struct dquot *dquot) 441{ 442 return find_tree_dqentry(h, dquot, QT_TREEOFF, 0); 443} 444 445/* 446 * Read dquot (either from disk or from kernel) 447 * User can use errno to detect errstr when NULL is returned 448 */ 449struct dquot *qtree_read_dquot(struct quota_handle *h, qid_t id) 450{ 451 struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; 452 loff_t offset; 453 ssize_t ret; 454 char *ddquot = smalloc(info->dqi_entry_size); 455 struct dquot *dquot = get_empty_dquot(); 456 457 dquot->dq_id = id; 458 dquot->dq_h = h; 459 dquot->dq_dqb.u.v2_mdqb.dqb_off = 0; 460 memset(&dquot->dq_dqb, 0, sizeof(struct util_dqblk)); 461 462 offset = find_dqentry(h, dquot); 463 if (offset > 0) { 464 dquot->dq_dqb.u.v2_mdqb.dqb_off = offset; 465 ret = h->e2fs_read(&h->qh_qf, offset, ddquot, 466 info->dqi_entry_size); 467 if (ret != info->dqi_entry_size) { 468 if (ret > 0) 469 errno = EIO; 470 log_fatal(2, 471 "Cannot read quota structure for id %u: %s", 472 dquot->dq_id, strerror(errno)); 473 } 474 info->dqi_ops->disk2mem_dqblk(dquot, ddquot); 475 } 476 return dquot; 477} 478 479/* 480 * Scan all dquots in file and call callback on each 481 */ 482#define set_bit(bmp, ind) ((bmp)[(ind) >> 3] |= (1 << ((ind) & 7))) 483#define get_bit(bmp, ind) ((bmp)[(ind) >> 3] & (1 << ((ind) & 7))) 484 485static int report_block(struct dquot *dquot, uint blk, char *bitmap, 486 int (*process_dquot) (struct dquot *, char *)) 487{ 488 struct qtree_mem_dqinfo *info = 489 &dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree; 490 dqbuf_t buf = getdqbuf(); 491 struct qt_disk_dqdbheader *dh; 492 char *ddata; 493 int entries, i; 494 495 set_bit(bitmap, blk); 496 read_blk(dquot->dq_h, blk, buf); 497 dh = (struct qt_disk_dqdbheader *)buf; 498 ddata = buf + sizeof(struct qt_disk_dqdbheader); 499 entries = ext2fs_le16_to_cpu(dh->dqdh_entries); 500 for (i = 0; i < qtree_dqstr_in_blk(info); 501 i++, ddata += info->dqi_entry_size) 502 if (!qtree_entry_unused(info, ddata)) { 503 info->dqi_ops->disk2mem_dqblk(dquot, ddata); 504 if (process_dquot(dquot, NULL) < 0) 505 break; 506 } 507 freedqbuf(buf); 508 return entries; 509} 510 511static void check_reference(struct quota_handle *h, uint blk) 512{ 513 if (blk >= h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks) 514 log_fatal(2, "Illegal reference (%u >= %u) in %s quota file. " 515 "Quota file is probably corrupted.\n" 516 "Please run e2fsck (8) to fix it.", 517 blk, 518 h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks, 519 type2name(h->qh_type)); 520} 521 522static int report_tree(struct dquot *dquot, uint blk, int depth, char *bitmap, 523 int (*process_dquot) (struct dquot *, char *)) 524{ 525 int entries = 0, i; 526 dqbuf_t buf = getdqbuf(); 527 u_int32_t *ref = (u_int32_t *) buf; 528 529 read_blk(dquot->dq_h, blk, buf); 530 if (depth == QT_TREEDEPTH - 1) { 531 for (i = 0; i < QT_BLKSIZE >> 2; i++) { 532 blk = ext2fs_le32_to_cpu(ref[i]); 533 check_reference(dquot->dq_h, blk); 534 if (blk && !get_bit(bitmap, blk)) 535 entries += report_block(dquot, blk, bitmap, 536 process_dquot); 537 } 538 } else { 539 for (i = 0; i < QT_BLKSIZE >> 2; i++) 540 blk = ext2fs_le32_to_cpu(ref[i]); 541 if (blk) { 542 check_reference(dquot->dq_h, blk); 543 entries += report_tree(dquot, blk, depth + 1, 544 bitmap, process_dquot); 545 } 546 } 547 freedqbuf(buf); 548 return entries; 549} 550 551static uint find_set_bits(char *bmp, int blocks) 552{ 553 uint i, used = 0; 554 555 for (i = 0; i < blocks; i++) 556 if (get_bit(bmp, i)) 557 used++; 558 return used; 559} 560 561int qtree_scan_dquots(struct quota_handle *h, 562 int (*process_dquot) (struct dquot *, char *)) 563{ 564 char *bitmap; 565 struct v2_mem_dqinfo *v2info = &h->qh_info.u.v2_mdqi; 566 struct qtree_mem_dqinfo *info = &v2info->dqi_qtree; 567 struct dquot *dquot = get_empty_dquot(); 568 569 dquot->dq_h = h; 570 bitmap = smalloc((info->dqi_blocks + 7) >> 3); 571 memset(bitmap, 0, (info->dqi_blocks + 7) >> 3); 572 v2info->dqi_used_entries = report_tree(dquot, QT_TREEOFF, 0, bitmap, 573 process_dquot); 574 v2info->dqi_data_blocks = find_set_bits(bitmap, info->dqi_blocks); 575 free(bitmap); 576 free(dquot); 577 return 0; 578} 579