Root/fs/quota/quota_tree.c

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

Archive Download this file



interactive