From 21a60258976227daaf7a4c35e96c3d77d4988b15 Mon Sep 17 00:00:00 2001 From: Artem Bityutskiy Date: Fri, 12 Dec 2008 11:13:17 -0500 Subject: UBIFS: improve budgeting dump Dump available space calculated by budgeting subsystem. Signed-off-by: Artem Bityutskiy --- fs/ubifs/budget.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'fs/ubifs/budget.c') diff --git a/fs/ubifs/budget.c b/fs/ubifs/budget.c index 1a4973e1066..d5a65037e17 100644 --- a/fs/ubifs/budget.c +++ b/fs/ubifs/budget.c @@ -713,8 +713,8 @@ void ubifs_release_dirty_inode_budget(struct ubifs_info *c, * (e.g., via the 'statfs()' call) reports that it has N bytes available, they * are able to write a file of size N. UBIFS attaches node headers to each data * node and it has to write indexind nodes as well. This introduces additional - * overhead, and UBIFS it has to report sligtly less free space to meet the - * above expectetion. + * overhead, and UBIFS has to report sligtly less free space to meet the above + * expectetions. * * This function assumes free space is made up of uncompressed data nodes and * full index nodes (one per data node, tripled because we always allow enough -- cgit v1.2.3 From af14a1ad792621942a03e4bd0e5f17b6e177e2e0 Mon Sep 17 00:00:00 2001 From: Artem Bityutskiy Date: Fri, 19 Dec 2008 19:26:29 +0200 Subject: UBIFS: fix available blocks count Take into account that 2 eraseblocks are never available because they are reserved for the index. This gives more realistic count of FS blocks. To avoid future confusions like this, introduce a constant. Signed-off-by: Artem Bityutskiy --- fs/ubifs/budget.c | 9 ++------- 1 file changed, 2 insertions(+), 7 deletions(-) (limited to 'fs/ubifs/budget.c') diff --git a/fs/ubifs/budget.c b/fs/ubifs/budget.c index d5a65037e17..e4234254700 100644 --- a/fs/ubifs/budget.c +++ b/fs/ubifs/budget.c @@ -280,13 +280,8 @@ int ubifs_calc_min_idx_lebs(struct ubifs_info *c) * extra LEB to compensate. */ ret += 1; - /* - * At present the index needs at least 2 LEBs: one for the index head - * and one for in-the-gaps method (which currently does not cater for - * the index head and so excludes it from consideration). - */ - if (ret < 2) - ret = 2; + if (ret < MIN_INDEX_LEBS) + ret = MIN_INDEX_LEBS; return ret; } -- cgit v1.2.3 From 4d61db4f87b527734ac0cc830dda8fcc4e2add2f Mon Sep 17 00:00:00 2001 From: Artem Bityutskiy Date: Thu, 18 Dec 2008 14:06:51 +0200 Subject: UBIFS: use nicer 64-bit math Instead of using do_div(), use better primitives from linux/math64.h. Signed-off-by: Artem Bityutskiy --- fs/ubifs/budget.c | 25 +++++++++++-------------- 1 file changed, 11 insertions(+), 14 deletions(-) (limited to 'fs/ubifs/budget.c') diff --git a/fs/ubifs/budget.c b/fs/ubifs/budget.c index e4234254700..0bcb8031ca1 100644 --- a/fs/ubifs/budget.c +++ b/fs/ubifs/budget.c @@ -32,7 +32,7 @@ #include "ubifs.h" #include -#include +#include /* * When pessimistic budget calculations say that there is no enough space, @@ -258,8 +258,8 @@ static int make_free_space(struct ubifs_info *c, struct retries_info *ri) */ int ubifs_calc_min_idx_lebs(struct ubifs_info *c) { - int ret; - uint64_t idx_size; + int idx_lebs, eff_leb_size = c->leb_size - c->max_idx_node_sz; + long long idx_size; idx_size = c->old_idx_sz + c->budg_idx_growth + c->budg_uncommitted_idx; @@ -271,18 +271,16 @@ int ubifs_calc_min_idx_lebs(struct ubifs_info *c) * pair, nor similarly the two variables for the new index size, so we * have to do this costly 64-bit division on fast-path. */ - if (do_div(idx_size, c->leb_size - c->max_idx_node_sz)) - ret = idx_size + 1; - else - ret = idx_size; + idx_size += eff_leb_size - 1; + idx_lebs = div_u64(idx_size, eff_leb_size); /* * The index head is not available for the in-the-gaps method, so add an * extra LEB to compensate. */ - ret += 1; - if (ret < MIN_INDEX_LEBS) - ret = MIN_INDEX_LEBS; - return ret; + idx_lebs += 1; + if (idx_lebs < MIN_INDEX_LEBS) + idx_lebs = MIN_INDEX_LEBS; + return idx_lebs; } /** @@ -718,7 +716,7 @@ void ubifs_release_dirty_inode_budget(struct ubifs_info *c, * Note, the calculation is pessimistic, which means that most of the time * UBIFS reports less space than it actually has. */ -long long ubifs_reported_space(const struct ubifs_info *c, uint64_t free) +long long ubifs_reported_space(const struct ubifs_info *c, long long free) { int divisor, factor, f; @@ -740,8 +738,7 @@ long long ubifs_reported_space(const struct ubifs_info *c, uint64_t free) divisor = UBIFS_MAX_DATA_NODE_SZ; divisor += (c->max_idx_node_sz * 3) / (f - 1); free *= factor; - do_div(free, divisor); - return free; + return div_u64(free, divisor); } /** -- cgit v1.2.3 From c8f915913afdfe1a796e312e21658b8edcf20868 Mon Sep 17 00:00:00 2001 From: Artem Bityutskiy Date: Fri, 19 Dec 2008 16:11:13 +0200 Subject: UBIFS: avoid unnecessary calculations Do not calculate min_idx_lebs, because it is available in c->min_idx_lebs Signed-off-by: Artem Bityutskiy --- fs/ubifs/budget.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'fs/ubifs/budget.c') diff --git a/fs/ubifs/budget.c b/fs/ubifs/budget.c index 0bcb8031ca1..44cff803171 100644 --- a/fs/ubifs/budget.c +++ b/fs/ubifs/budget.c @@ -763,7 +763,8 @@ long long ubifs_get_free_space(struct ubifs_info *c) long long available, outstanding, free; spin_lock(&c->space_lock); - min_idx_lebs = ubifs_calc_min_idx_lebs(c); + min_idx_lebs = c->min_idx_lebs; + ubifs_assert(min_idx_lebs == ubifs_calc_min_idx_lebs(c)); outstanding = c->budg_data_growth + c->budg_dd_growth; /* -- cgit v1.2.3 From 2edc2025c2583a18eafe5cdbc7deb36e320aaec5 Mon Sep 17 00:00:00 2001 From: Artem Bityutskiy Date: Mon, 22 Dec 2008 11:21:03 +0200 Subject: UBIFS: do not lie about used blocks Do not force UBIFS return 0 used space when it is empty. It leads to a situation when creating any file immediately produces tens of used blocks, which looks very weird. It is better to be honest and say that some blocks are used even if the FS is empty. And ext2 does the same. Signed-off-by: Artem Bityutskiy --- fs/ubifs/budget.c | 10 ---------- 1 file changed, 10 deletions(-) (limited to 'fs/ubifs/budget.c') diff --git a/fs/ubifs/budget.c b/fs/ubifs/budget.c index 44cff803171..3715d011495 100644 --- a/fs/ubifs/budget.c +++ b/fs/ubifs/budget.c @@ -766,16 +766,6 @@ long long ubifs_get_free_space(struct ubifs_info *c) min_idx_lebs = c->min_idx_lebs; ubifs_assert(min_idx_lebs == ubifs_calc_min_idx_lebs(c)); outstanding = c->budg_data_growth + c->budg_dd_growth; - - /* - * Force the amount available to the total size reported if the used - * space is zero. - */ - if (c->lst.total_used <= UBIFS_INO_NODE_SZ && !outstanding) { - spin_unlock(&c->space_lock); - return (long long)c->block_cnt << UBIFS_BLOCK_SHIFT; - } - available = ubifs_calc_available(c, min_idx_lebs); /* -- cgit v1.2.3 From 2acf80675800d5e6775990d1280cca5c2ffb30e6 Mon Sep 17 00:00:00 2001 From: Artem Bityutskiy Date: Tue, 9 Dec 2008 11:04:40 -0500 Subject: UBIFS: simplify make_free_space The 'make_free_space()' function was too complex and this patch simplifies it. It also fixes a bug - the freespace test failed straight away on UBI volumes with 512 bytes LEB size. Signed-off-by: Artem Bityutskiy --- fs/ubifs/budget.c | 151 ++++++++++++++++++------------------------------------ 1 file changed, 49 insertions(+), 102 deletions(-) (limited to 'fs/ubifs/budget.c') diff --git a/fs/ubifs/budget.c b/fs/ubifs/budget.c index 3715d011495..4d270f0a856 100644 --- a/fs/ubifs/budget.c +++ b/fs/ubifs/budget.c @@ -37,13 +37,10 @@ /* * When pessimistic budget calculations say that there is no enough space, * UBIFS starts writing back dirty inodes and pages, doing garbage collection, - * or committing. The below constants define maximum number of times UBIFS + * or committing. The below constant defines maximum number of times UBIFS * repeats the operations. */ -#define MAX_SHRINK_RETRIES 8 -#define MAX_GC_RETRIES 4 -#define MAX_CMT_RETRIES 2 -#define MAX_NOSPC_RETRIES 1 +#define MAX_MKSPC_RETRIES 3 /* * The below constant defines amount of dirty pages which should be written @@ -51,30 +48,6 @@ */ #define NR_TO_WRITE 16 -/** - * struct retries_info - information about re-tries while making free space. - * @prev_liability: previous liability - * @shrink_cnt: how many times the liability was shrinked - * @shrink_retries: count of liability shrink re-tries (increased when - * liability does not shrink) - * @try_gc: GC should be tried first - * @gc_retries: how many times GC was run - * @cmt_retries: how many times commit has been done - * @nospc_retries: how many times GC returned %-ENOSPC - * - * Since we consider budgeting to be the fast-path, and this structure has to - * be allocated on stack and zeroed out, we make it smaller using bit-fields. - */ -struct retries_info { - long long prev_liability; - unsigned int shrink_cnt; - unsigned int shrink_retries:5; - unsigned int try_gc:1; - unsigned int gc_retries:4; - unsigned int cmt_retries:3; - unsigned int nospc_retries:1; -}; - /** * shrink_liability - write-back some dirty pages/inodes. * @c: UBIFS file-system description object @@ -146,10 +119,26 @@ static int run_gc(struct ubifs_info *c) return 0; } +/** + * get_liability - calculate current liability. + * @c: UBIFS file-system description object + * + * This function calculates and returns current UBIFS liability, i.e. the + * amount of bytes UBIFS has "promised" to write to the media. + */ +static long long get_liability(struct ubifs_info *c) +{ + long long liab; + + spin_lock(&c->space_lock); + liab = c->budg_idx_growth + c->budg_data_growth + c->budg_dd_growth; + spin_unlock(&c->space_lock); + return liab; +} + /** * make_free_space - make more free space on the file-system. * @c: UBIFS file-system description object - * @ri: information about previous invocations of this function * * This function is called when an operation cannot be budgeted because there * is supposedly no free space. But in most cases there is some free space: @@ -165,87 +154,42 @@ static int run_gc(struct ubifs_info *c) * Returns %-ENOSPC if it couldn't do more free space, and other negative error * codes on failures. */ -static int make_free_space(struct ubifs_info *c, struct retries_info *ri) +static int make_free_space(struct ubifs_info *c) { - int err; - - /* - * If we have some dirty pages and inodes (liability), try to write - * them back unless this was tried too many times without effect - * already. - */ - if (ri->shrink_retries < MAX_SHRINK_RETRIES && !ri->try_gc) { - long long liability; - - spin_lock(&c->space_lock); - liability = c->budg_idx_growth + c->budg_data_growth + - c->budg_dd_growth; - spin_unlock(&c->space_lock); + int err, retries = 0; + long long liab1, liab2; - if (ri->prev_liability >= liability) { - /* Liability does not shrink, next time try GC then */ - ri->shrink_retries += 1; - if (ri->gc_retries < MAX_GC_RETRIES) - ri->try_gc = 1; - dbg_budg("liability did not shrink: retries %d of %d", - ri->shrink_retries, MAX_SHRINK_RETRIES); - } - - dbg_budg("force write-back (count %d)", ri->shrink_cnt); - shrink_liability(c, NR_TO_WRITE + ri->shrink_cnt); + do { + liab1 = get_liability(c); + /* + * We probably have some dirty pages or inodes (liability), try + * to write them back. + */ + dbg_budg("liability %lld, run write-back", liab1); + shrink_liability(c, NR_TO_WRITE); - ri->prev_liability = liability; - ri->shrink_cnt += 1; - return -EAGAIN; - } + liab2 = get_liability(c); + if (liab2 < liab1) + return -EAGAIN; - /* - * Try to run garbage collector unless it was already tried too many - * times. - */ - if (ri->gc_retries < MAX_GC_RETRIES) { - ri->gc_retries += 1; - dbg_budg("run GC, retries %d of %d", - ri->gc_retries, MAX_GC_RETRIES); + dbg_budg("new liability %lld (not shrinked)", liab2); - ri->try_gc = 0; + /* Liability did not shrink again, try GC */ + dbg_budg("Run GC"); err = run_gc(c); if (!err) return -EAGAIN; - if (err == -EAGAIN) { - dbg_budg("GC asked to commit"); - err = ubifs_run_commit(c); - if (err) - return err; - return -EAGAIN; - } - - if (err != -ENOSPC) + if (err != -EAGAIN && err != -ENOSPC) + /* Some real error happened */ return err; - /* - * GC could not make any progress. If this is the first time, - * then it makes sense to try to commit, because it might make - * some dirty space. - */ - dbg_budg("GC returned -ENOSPC, retries %d", - ri->nospc_retries); - if (ri->nospc_retries >= MAX_NOSPC_RETRIES) - return err; - ri->nospc_retries += 1; - } - - /* Neither GC nor write-back helped, try to commit */ - if (ri->cmt_retries < MAX_CMT_RETRIES) { - ri->cmt_retries += 1; - dbg_budg("run commit, retries %d of %d", - ri->cmt_retries, MAX_CMT_RETRIES); + dbg_budg("Run commit (retries %d)", retries); err = ubifs_run_commit(c); if (err) return err; - return -EAGAIN; - } + } while (retries++ < MAX_MKSPC_RETRIES); + return -ENOSPC; } @@ -523,8 +467,7 @@ static int calc_dd_growth(const struct ubifs_info *c, int ubifs_budget_space(struct ubifs_info *c, struct ubifs_budget_req *req) { int uninitialized_var(cmt_retries), uninitialized_var(wb_retries); - int err, idx_growth, data_growth, dd_growth; - struct retries_info ri; + int err, idx_growth, data_growth, dd_growth, retried = 0; ubifs_assert(req->new_page <= 1); ubifs_assert(req->dirtied_page <= 1); @@ -542,7 +485,6 @@ int ubifs_budget_space(struct ubifs_info *c, struct ubifs_budget_req *req) if (!data_growth && !dd_growth) return 0; idx_growth = calc_idx_growth(c, req); - memset(&ri, 0, sizeof(struct retries_info)); again: spin_lock(&c->space_lock); @@ -580,12 +522,17 @@ again: return err; } - err = make_free_space(c, &ri); + err = make_free_space(c); + cond_resched(); if (err == -EAGAIN) { dbg_budg("try again"); - cond_resched(); goto again; } else if (err == -ENOSPC) { + if (!retried) { + retried = 1; + dbg_budg("-ENOSPC, but anyway try once again"); + goto again; + } dbg_budg("FS is full, -ENOSPC"); c->nospace = 1; if (can_use_rp(c) || c->rp_size == 0) -- cgit v1.2.3 From 80736d41f895bc472b2433a1c27fa6d4afe6ca35 Mon Sep 17 00:00:00 2001 From: Artem Bityutskiy Date: Tue, 30 Dec 2008 17:44:02 +0200 Subject: UBIFS: fix numerous spelling mistakes Signed-off-by: Artem Bityutskiy --- fs/ubifs/budget.c | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) (limited to 'fs/ubifs/budget.c') diff --git a/fs/ubifs/budget.c b/fs/ubifs/budget.c index 4d270f0a856..31870d8dab8 100644 --- a/fs/ubifs/budget.c +++ b/fs/ubifs/budget.c @@ -652,9 +652,9 @@ void ubifs_release_dirty_inode_budget(struct ubifs_info *c, * user-space. User-space application tend to expect that if the file-system * (e.g., via the 'statfs()' call) reports that it has N bytes available, they * are able to write a file of size N. UBIFS attaches node headers to each data - * node and it has to write indexind nodes as well. This introduces additional - * overhead, and UBIFS has to report sligtly less free space to meet the above - * expectetions. + * node and it has to write indexing nodes as well. This introduces additional + * overhead, and UBIFS has to report slightly less free space to meet the above + * expectations. * * This function assumes free space is made up of uncompressed data nodes and * full index nodes (one per data node, tripled because we always allow enough @@ -677,7 +677,7 @@ long long ubifs_reported_space(const struct ubifs_info *c, long long free) * of data nodes, f - fanout. Because effective UBIFS fanout is twice * as less than maximum fanout, we assume that each data node * introduces 3 * @c->max_idx_node_sz / (@c->fanout/2 - 1) bytes. - * Note, the multiplier 3 is because UBIFS reseves thrice as more space + * Note, the multiplier 3 is because UBIFS reserves thrice as more space * for the index. */ f = c->fanout > 3 ? c->fanout >> 1 : 2; @@ -695,10 +695,10 @@ long long ubifs_reported_space(const struct ubifs_info *c, long long free) * This function calculates amount of free space to report to user-space. * * Because UBIFS may introduce substantial overhead (the index, node headers, - * alighment, wastage at the end of eraseblocks, etc), it cannot report real + * alignment, wastage at the end of eraseblocks, etc), it cannot report real * amount of free flash space it has (well, because not all dirty space is - * reclamable, UBIFS does not actually know the real amount). If UBIFS did so, - * it would bread user expectetion about what free space is. Users seem to + * reclaimable, UBIFS does not actually know the real amount). If UBIFS did so, + * it would bread user expectations about what free space is. Users seem to * accustomed to assume that if the file-system reports N bytes of free space, * they would be able to fit a file of N bytes to the FS. This almost works for * traditional file-systems, because they have way less overhead than UBIFS. -- cgit v1.2.3