quotaio_tree.c

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