blob: eaf6d891d46f642b4351230119ea4358ce30dea6 [file] [log] [blame]
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001/*
2 * This file is part of UBIFS.
3 *
4 * Copyright (C) 2006-2008 Nokia Corporation.
5 *
6 * This program is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 as published by
8 * the Free Software Foundation.
9 *
10 * This program is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
13 * more details.
14 *
15 * You should have received a copy of the GNU General Public License along with
16 * this program; if not, write to the Free Software Foundation, Inc., 51
17 * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18 *
19 * Authors: Adrian Hunter
20 * Artem Bityutskiy (Битюцкий Артём)
21 */
22
23/*
24 * This file implements the budgeting sub-system which is responsible for UBIFS
25 * space management.
26 *
27 * Factors such as compression, wasted space at the ends of LEBs, space in other
28 * journal heads, the effect of updates on the index, and so on, make it
29 * impossible to accurately predict the amount of space needed. Consequently
30 * approximations are used.
31 */
32
33#include "ubifs.h"
34#include <linux/writeback.h>
Artem Bityutskiy4d61db42008-12-18 14:06:51 +020035#include <linux/math64.h>
Artem Bityutskiy1e517642008-07-14 19:08:37 +030036
37/*
38 * When pessimistic budget calculations say that there is no enough space,
39 * UBIFS starts writing back dirty inodes and pages, doing garbage collection,
Artem Bityutskiy2acf8062008-12-09 11:04:40 -050040 * or committing. The below constant defines maximum number of times UBIFS
Artem Bityutskiy1e517642008-07-14 19:08:37 +030041 * repeats the operations.
42 */
Artem Bityutskiy2acf8062008-12-09 11:04:40 -050043#define MAX_MKSPC_RETRIES 3
Artem Bityutskiy1e517642008-07-14 19:08:37 +030044
45/*
46 * The below constant defines amount of dirty pages which should be written
47 * back at when trying to shrink the liability.
48 */
49#define NR_TO_WRITE 16
50
51/**
Artem Bityutskiy1e517642008-07-14 19:08:37 +030052 * shrink_liability - write-back some dirty pages/inodes.
53 * @c: UBIFS file-system description object
54 * @nr_to_write: how many dirty pages to write-back
55 *
56 * This function shrinks UBIFS liability by means of writing back some amount
57 * of dirty inodes and their pages. Returns the amount of pages which were
58 * written back. The returned value does not include dirty inodes which were
59 * synchronized.
60 *
61 * Note, this function synchronizes even VFS inodes which are locked
62 * (@i_mutex) by the caller of the budgeting function, because write-back does
63 * not touch @i_mutex.
64 */
65static int shrink_liability(struct ubifs_info *c, int nr_to_write)
66{
67 int nr_written;
68 struct writeback_control wbc = {
69 .sync_mode = WB_SYNC_NONE,
70 .range_end = LLONG_MAX,
71 .nr_to_write = nr_to_write,
72 };
73
74 generic_sync_sb_inodes(c->vfs_sb, &wbc);
75 nr_written = nr_to_write - wbc.nr_to_write;
76
77 if (!nr_written) {
78 /*
79 * Re-try again but wait on pages/inodes which are being
80 * written-back concurrently (e.g., by pdflush).
81 */
82 memset(&wbc, 0, sizeof(struct writeback_control));
83 wbc.sync_mode = WB_SYNC_ALL;
84 wbc.range_end = LLONG_MAX;
85 wbc.nr_to_write = nr_to_write;
86 generic_sync_sb_inodes(c->vfs_sb, &wbc);
87 nr_written = nr_to_write - wbc.nr_to_write;
88 }
89
90 dbg_budg("%d pages were written back", nr_written);
91 return nr_written;
92}
93
Artem Bityutskiy1e517642008-07-14 19:08:37 +030094/**
95 * run_gc - run garbage collector.
96 * @c: UBIFS file-system description object
97 *
98 * This function runs garbage collector to make some more free space. Returns
99 * zero if a free LEB has been produced, %-EAGAIN if commit is required, and a
100 * negative error code in case of failure.
101 */
102static int run_gc(struct ubifs_info *c)
103{
104 int err, lnum;
105
106 /* Make some free space by garbage-collecting dirty space */
107 down_read(&c->commit_sem);
108 lnum = ubifs_garbage_collect(c, 1);
109 up_read(&c->commit_sem);
110 if (lnum < 0)
111 return lnum;
112
113 /* GC freed one LEB, return it to lprops */
114 dbg_budg("GC freed LEB %d", lnum);
115 err = ubifs_return_leb(c, lnum);
116 if (err)
117 return err;
118 return 0;
119}
120
121/**
Artem Bityutskiy2acf8062008-12-09 11:04:40 -0500122 * get_liability - calculate current liability.
123 * @c: UBIFS file-system description object
124 *
125 * This function calculates and returns current UBIFS liability, i.e. the
126 * amount of bytes UBIFS has "promised" to write to the media.
127 */
128static long long get_liability(struct ubifs_info *c)
129{
130 long long liab;
131
132 spin_lock(&c->space_lock);
133 liab = c->budg_idx_growth + c->budg_data_growth + c->budg_dd_growth;
134 spin_unlock(&c->space_lock);
135 return liab;
136}
137
138/**
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300139 * make_free_space - make more free space on the file-system.
140 * @c: UBIFS file-system description object
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300141 *
142 * This function is called when an operation cannot be budgeted because there
143 * is supposedly no free space. But in most cases there is some free space:
Frederik Schwarzer025dfda2008-10-16 19:02:37 +0200144 * o budgeting is pessimistic, so it always budgets more than it is actually
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300145 * needed, so shrinking the liability is one way to make free space - the
146 * cached data will take less space then it was budgeted for;
147 * o GC may turn some dark space into free space (budgeting treats dark space
148 * as not available);
149 * o commit may free some LEB, i.e., turn freeable LEBs into free LEBs.
150 *
151 * So this function tries to do the above. Returns %-EAGAIN if some free space
152 * was presumably made and the caller has to re-try budgeting the operation.
153 * Returns %-ENOSPC if it couldn't do more free space, and other negative error
154 * codes on failures.
155 */
Artem Bityutskiy2acf8062008-12-09 11:04:40 -0500156static int make_free_space(struct ubifs_info *c)
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300157{
Artem Bityutskiy2acf8062008-12-09 11:04:40 -0500158 int err, retries = 0;
159 long long liab1, liab2;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300160
Artem Bityutskiy2acf8062008-12-09 11:04:40 -0500161 do {
162 liab1 = get_liability(c);
163 /*
164 * We probably have some dirty pages or inodes (liability), try
165 * to write them back.
166 */
167 dbg_budg("liability %lld, run write-back", liab1);
168 shrink_liability(c, NR_TO_WRITE);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300169
Artem Bityutskiy2acf8062008-12-09 11:04:40 -0500170 liab2 = get_liability(c);
171 if (liab2 < liab1)
172 return -EAGAIN;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300173
Artem Bityutskiy2acf8062008-12-09 11:04:40 -0500174 dbg_budg("new liability %lld (not shrinked)", liab2);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300175
Artem Bityutskiy2acf8062008-12-09 11:04:40 -0500176 /* Liability did not shrink again, try GC */
177 dbg_budg("Run GC");
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300178 err = run_gc(c);
179 if (!err)
180 return -EAGAIN;
181
Artem Bityutskiy2acf8062008-12-09 11:04:40 -0500182 if (err != -EAGAIN && err != -ENOSPC)
183 /* Some real error happened */
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300184 return err;
185
Artem Bityutskiy2acf8062008-12-09 11:04:40 -0500186 dbg_budg("Run commit (retries %d)", retries);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300187 err = ubifs_run_commit(c);
188 if (err)
189 return err;
Artem Bityutskiy2acf8062008-12-09 11:04:40 -0500190 } while (retries++ < MAX_MKSPC_RETRIES);
191
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300192 return -ENOSPC;
193}
194
195/**
Artem Bityutskiyfb1cd012009-03-16 09:56:57 +0200196 * ubifs_calc_min_idx_lebs - calculate amount of LEBs for the index.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300197 * @c: UBIFS file-system description object
198 *
Artem Bityutskiyfb1cd012009-03-16 09:56:57 +0200199 * This function calculates and returns the number of LEBs which should be kept
200 * for index usage.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300201 */
202int ubifs_calc_min_idx_lebs(struct ubifs_info *c)
203{
Artem Bityutskiyfb1cd012009-03-16 09:56:57 +0200204 int idx_lebs;
Artem Bityutskiy4d61db42008-12-18 14:06:51 +0200205 long long idx_size;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300206
207 idx_size = c->old_idx_sz + c->budg_idx_growth + c->budg_uncommitted_idx;
Adrian Hunter3a132522008-07-30 12:18:02 +0300208 /* And make sure we have thrice the index size of space reserved */
Artem Bityutskiyfb1cd012009-03-16 09:56:57 +0200209 idx_size += idx_size << 1;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300210 /*
211 * We do not maintain 'old_idx_size' as 'old_idx_lebs'/'old_idx_bytes'
212 * pair, nor similarly the two variables for the new index size, so we
213 * have to do this costly 64-bit division on fast-path.
214 */
Artem Bityutskiyfb1cd012009-03-16 09:56:57 +0200215 idx_lebs = div_u64(idx_size + c->idx_leb_size - 1, c->idx_leb_size);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300216 /*
217 * The index head is not available for the in-the-gaps method, so add an
218 * extra LEB to compensate.
219 */
Artem Bityutskiy4d61db42008-12-18 14:06:51 +0200220 idx_lebs += 1;
221 if (idx_lebs < MIN_INDEX_LEBS)
222 idx_lebs = MIN_INDEX_LEBS;
223 return idx_lebs;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300224}
225
226/**
227 * ubifs_calc_available - calculate available FS space.
228 * @c: UBIFS file-system description object
229 * @min_idx_lebs: minimum number of LEBs reserved for the index
230 *
231 * This function calculates and returns amount of FS space available for use.
232 */
233long long ubifs_calc_available(const struct ubifs_info *c, int min_idx_lebs)
234{
235 int subtract_lebs;
236 long long available;
237
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300238 available = c->main_bytes - c->lst.total_used;
239
240 /*
241 * Now 'available' contains theoretically available flash space
242 * assuming there is no index, so we have to subtract the space which
243 * is reserved for the index.
244 */
245 subtract_lebs = min_idx_lebs;
246
247 /* Take into account that GC reserves one LEB for its own needs */
248 subtract_lebs += 1;
249
250 /*
251 * The GC journal head LEB is not really accessible. And since
252 * different write types go to different heads, we may count only on
253 * one head's space.
254 */
255 subtract_lebs += c->jhead_cnt - 1;
256
257 /* We also reserve one LEB for deletions, which bypass budgeting */
258 subtract_lebs += 1;
259
260 available -= (long long)subtract_lebs * c->leb_size;
261
262 /* Subtract the dead space which is not available for use */
263 available -= c->lst.total_dead;
264
265 /*
266 * Subtract dark space, which might or might not be usable - it depends
267 * on the data which we have on the media and which will be written. If
268 * this is a lot of uncompressed or not-compressible data, the dark
269 * space cannot be used.
270 */
271 available -= c->lst.total_dark;
272
273 /*
274 * However, there is more dark space. The index may be bigger than
275 * @min_idx_lebs. Those extra LEBs are assumed to be available, but
276 * their dark space is not included in total_dark, so it is subtracted
277 * here.
278 */
279 if (c->lst.idx_lebs > min_idx_lebs) {
280 subtract_lebs = c->lst.idx_lebs - min_idx_lebs;
281 available -= subtract_lebs * c->dark_wm;
282 }
283
284 /* The calculations are rough and may end up with a negative number */
285 return available > 0 ? available : 0;
286}
287
288/**
289 * can_use_rp - check whether the user is allowed to use reserved pool.
290 * @c: UBIFS file-system description object
291 *
292 * UBIFS has so-called "reserved pool" which is flash space reserved
293 * for the superuser and for uses whose UID/GID is recorded in UBIFS superblock.
294 * This function checks whether current user is allowed to use reserved pool.
295 * Returns %1 current user is allowed to use reserved pool and %0 otherwise.
296 */
297static int can_use_rp(struct ubifs_info *c)
298{
David Howells26bf1942008-11-14 10:39:03 +1100299 if (current_fsuid() == c->rp_uid || capable(CAP_SYS_RESOURCE) ||
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300300 (c->rp_gid != 0 && in_group_p(c->rp_gid)))
301 return 1;
302 return 0;
303}
304
305/**
306 * do_budget_space - reserve flash space for index and data growth.
307 * @c: UBIFS file-system description object
308 *
Artem Bityutskiyfb1cd012009-03-16 09:56:57 +0200309 * This function makes sure UBIFS has enough free LEBs for index growth and
310 * data.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300311 *
Adrian Hunter3a132522008-07-30 12:18:02 +0300312 * When budgeting index space, UBIFS reserves thrice as many LEBs as the index
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300313 * would take if it was consolidated and written to the flash. This guarantees
314 * that the "in-the-gaps" commit method always succeeds and UBIFS will always
315 * be able to commit dirty index. So this function basically adds amount of
Artem Bityutskiyb364b412008-07-25 14:38:51 +0300316 * budgeted index space to the size of the current index, multiplies this by 3,
Artem Bityutskiyfb1cd012009-03-16 09:56:57 +0200317 * and makes sure this does not exceed the amount of free LEBs.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300318 *
319 * Notes about @c->min_idx_lebs and @c->lst.idx_lebs variables:
320 * o @c->lst.idx_lebs is the number of LEBs the index currently uses. It might
321 * be large, because UBIFS does not do any index consolidation as long as
322 * there is free space. IOW, the index may take a lot of LEBs, but the LEBs
323 * will contain a lot of dirt.
Artem Bityutskiy7d4e9cc2009-03-20 19:11:12 +0200324 * o @c->min_idx_lebs is the number of LEBS the index presumably takes. IOW,
325 * the index may be consolidated to take up to @c->min_idx_lebs LEBs.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300326 *
327 * This function returns zero in case of success, and %-ENOSPC in case of
328 * failure.
329 */
330static int do_budget_space(struct ubifs_info *c)
331{
332 long long outstanding, available;
333 int lebs, rsvd_idx_lebs, min_idx_lebs;
334
335 /* First budget index space */
336 min_idx_lebs = ubifs_calc_min_idx_lebs(c);
337
338 /* Now 'min_idx_lebs' contains number of LEBs to reserve */
339 if (min_idx_lebs > c->lst.idx_lebs)
340 rsvd_idx_lebs = min_idx_lebs - c->lst.idx_lebs;
341 else
342 rsvd_idx_lebs = 0;
343
344 /*
345 * The number of LEBs that are available to be used by the index is:
346 *
347 * @c->lst.empty_lebs + @c->freeable_cnt + @c->idx_gc_cnt -
348 * @c->lst.taken_empty_lebs
349 *
Artem Bityutskiy948cfb22008-08-20 11:56:33 +0300350 * @c->lst.empty_lebs are available because they are empty.
351 * @c->freeable_cnt are available because they contain only free and
352 * dirty space, @c->idx_gc_cnt are available because they are index
353 * LEBs that have been garbage collected and are awaiting the commit
354 * before they can be used. And the in-the-gaps method will grab these
355 * if it needs them. @c->lst.taken_empty_lebs are empty LEBs that have
356 * already been allocated for some purpose.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300357 *
Artem Bityutskiy948cfb22008-08-20 11:56:33 +0300358 * Note, @c->idx_gc_cnt is included to both @c->lst.empty_lebs (because
359 * these LEBs are empty) and to @c->lst.taken_empty_lebs (because they
360 * are taken until after the commit).
361 *
362 * Note, @c->lst.taken_empty_lebs may temporarily be higher by one
363 * because of the way we serialize LEB allocations and budgeting. See a
364 * comment in 'ubifs_find_free_space()'.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300365 */
366 lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt -
367 c->lst.taken_empty_lebs;
368 if (unlikely(rsvd_idx_lebs > lebs)) {
369 dbg_budg("out of indexing space: min_idx_lebs %d (old %d), "
370 "rsvd_idx_lebs %d", min_idx_lebs, c->min_idx_lebs,
371 rsvd_idx_lebs);
372 return -ENOSPC;
373 }
374
375 available = ubifs_calc_available(c, min_idx_lebs);
376 outstanding = c->budg_data_growth + c->budg_dd_growth;
377
378 if (unlikely(available < outstanding)) {
379 dbg_budg("out of data space: available %lld, outstanding %lld",
380 available, outstanding);
381 return -ENOSPC;
382 }
383
384 if (available - outstanding <= c->rp_size && !can_use_rp(c))
385 return -ENOSPC;
386
387 c->min_idx_lebs = min_idx_lebs;
388 return 0;
389}
390
391/**
392 * calc_idx_growth - calculate approximate index growth from budgeting request.
393 * @c: UBIFS file-system description object
394 * @req: budgeting request
395 *
396 * For now we assume each new node adds one znode. But this is rather poor
397 * approximation, though.
398 */
399static int calc_idx_growth(const struct ubifs_info *c,
400 const struct ubifs_budget_req *req)
401{
402 int znodes;
403
404 znodes = req->new_ino + (req->new_page << UBIFS_BLOCKS_PER_PAGE_SHIFT) +
405 req->new_dent;
406 return znodes * c->max_idx_node_sz;
407}
408
409/**
410 * calc_data_growth - calculate approximate amount of new data from budgeting
411 * request.
412 * @c: UBIFS file-system description object
413 * @req: budgeting request
414 */
415static int calc_data_growth(const struct ubifs_info *c,
416 const struct ubifs_budget_req *req)
417{
418 int data_growth;
419
420 data_growth = req->new_ino ? c->inode_budget : 0;
421 if (req->new_page)
422 data_growth += c->page_budget;
423 if (req->new_dent)
424 data_growth += c->dent_budget;
425 data_growth += req->new_ino_d;
426 return data_growth;
427}
428
429/**
430 * calc_dd_growth - calculate approximate amount of data which makes other data
431 * dirty from budgeting request.
432 * @c: UBIFS file-system description object
433 * @req: budgeting request
434 */
435static int calc_dd_growth(const struct ubifs_info *c,
436 const struct ubifs_budget_req *req)
437{
438 int dd_growth;
439
440 dd_growth = req->dirtied_page ? c->page_budget : 0;
441
442 if (req->dirtied_ino)
443 dd_growth += c->inode_budget << (req->dirtied_ino - 1);
444 if (req->mod_dent)
445 dd_growth += c->dent_budget;
446 dd_growth += req->dirtied_ino_d;
447 return dd_growth;
448}
449
450/**
451 * ubifs_budget_space - ensure there is enough space to complete an operation.
452 * @c: UBIFS file-system description object
453 * @req: budget request
454 *
455 * This function allocates budget for an operation. It uses pessimistic
456 * approximation of how much flash space the operation needs. The goal of this
457 * function is to make sure UBIFS always has flash space to flush all dirty
458 * pages, dirty inodes, and dirty znodes (liability). This function may force
459 * commit, garbage-collection or write-back. Returns zero in case of success,
460 * %-ENOSPC if there is no free space and other negative error codes in case of
461 * failures.
462 */
463int ubifs_budget_space(struct ubifs_info *c, struct ubifs_budget_req *req)
464{
465 int uninitialized_var(cmt_retries), uninitialized_var(wb_retries);
Artem Bityutskiy2acf8062008-12-09 11:04:40 -0500466 int err, idx_growth, data_growth, dd_growth, retried = 0;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300467
Artem Bityutskiy547000d2008-07-24 14:42:05 +0300468 ubifs_assert(req->new_page <= 1);
469 ubifs_assert(req->dirtied_page <= 1);
470 ubifs_assert(req->new_dent <= 1);
471 ubifs_assert(req->mod_dent <= 1);
472 ubifs_assert(req->new_ino <= 1);
473 ubifs_assert(req->new_ino_d <= UBIFS_MAX_INO_DATA);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300474 ubifs_assert(req->dirtied_ino <= 4);
475 ubifs_assert(req->dirtied_ino_d <= UBIFS_MAX_INO_DATA * 4);
Artem Bityutskiydab4b4d2008-07-24 14:52:45 +0300476 ubifs_assert(!(req->new_ino_d & 7));
477 ubifs_assert(!(req->dirtied_ino_d & 7));
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300478
479 data_growth = calc_data_growth(c, req);
480 dd_growth = calc_dd_growth(c, req);
481 if (!data_growth && !dd_growth)
482 return 0;
483 idx_growth = calc_idx_growth(c, req);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300484
485again:
486 spin_lock(&c->space_lock);
487 ubifs_assert(c->budg_idx_growth >= 0);
488 ubifs_assert(c->budg_data_growth >= 0);
489 ubifs_assert(c->budg_dd_growth >= 0);
490
491 if (unlikely(c->nospace) && (c->nospace_rp || !can_use_rp(c))) {
492 dbg_budg("no space");
493 spin_unlock(&c->space_lock);
494 return -ENOSPC;
495 }
496
497 c->budg_idx_growth += idx_growth;
498 c->budg_data_growth += data_growth;
499 c->budg_dd_growth += dd_growth;
500
501 err = do_budget_space(c);
502 if (likely(!err)) {
503 req->idx_growth = idx_growth;
504 req->data_growth = data_growth;
505 req->dd_growth = dd_growth;
506 spin_unlock(&c->space_lock);
507 return 0;
508 }
509
510 /* Restore the old values */
511 c->budg_idx_growth -= idx_growth;
512 c->budg_data_growth -= data_growth;
513 c->budg_dd_growth -= dd_growth;
514 spin_unlock(&c->space_lock);
515
516 if (req->fast) {
517 dbg_budg("no space for fast budgeting");
518 return err;
519 }
520
Artem Bityutskiy2acf8062008-12-09 11:04:40 -0500521 err = make_free_space(c);
522 cond_resched();
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300523 if (err == -EAGAIN) {
524 dbg_budg("try again");
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300525 goto again;
526 } else if (err == -ENOSPC) {
Artem Bityutskiy2acf8062008-12-09 11:04:40 -0500527 if (!retried) {
528 retried = 1;
529 dbg_budg("-ENOSPC, but anyway try once again");
530 goto again;
531 }
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300532 dbg_budg("FS is full, -ENOSPC");
533 c->nospace = 1;
534 if (can_use_rp(c) || c->rp_size == 0)
535 c->nospace_rp = 1;
536 smp_wmb();
537 } else
538 ubifs_err("cannot budget space, error %d", err);
539 return err;
540}
541
542/**
543 * ubifs_release_budget - release budgeted free space.
544 * @c: UBIFS file-system description object
545 * @req: budget request
546 *
547 * This function releases the space budgeted by 'ubifs_budget_space()'. Note,
548 * since the index changes (which were budgeted for in @req->idx_growth) will
549 * only be written to the media on commit, this function moves the index budget
550 * from @c->budg_idx_growth to @c->budg_uncommitted_idx. The latter will be
551 * zeroed by the commit operation.
552 */
553void ubifs_release_budget(struct ubifs_info *c, struct ubifs_budget_req *req)
554{
Artem Bityutskiy547000d2008-07-24 14:42:05 +0300555 ubifs_assert(req->new_page <= 1);
556 ubifs_assert(req->dirtied_page <= 1);
557 ubifs_assert(req->new_dent <= 1);
558 ubifs_assert(req->mod_dent <= 1);
559 ubifs_assert(req->new_ino <= 1);
560 ubifs_assert(req->new_ino_d <= UBIFS_MAX_INO_DATA);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300561 ubifs_assert(req->dirtied_ino <= 4);
562 ubifs_assert(req->dirtied_ino_d <= UBIFS_MAX_INO_DATA * 4);
Artem Bityutskiydab4b4d2008-07-24 14:52:45 +0300563 ubifs_assert(!(req->new_ino_d & 7));
564 ubifs_assert(!(req->dirtied_ino_d & 7));
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300565 if (!req->recalculate) {
566 ubifs_assert(req->idx_growth >= 0);
567 ubifs_assert(req->data_growth >= 0);
568 ubifs_assert(req->dd_growth >= 0);
569 }
570
571 if (req->recalculate) {
572 req->data_growth = calc_data_growth(c, req);
573 req->dd_growth = calc_dd_growth(c, req);
574 req->idx_growth = calc_idx_growth(c, req);
575 }
576
577 if (!req->data_growth && !req->dd_growth)
578 return;
579
580 c->nospace = c->nospace_rp = 0;
581 smp_wmb();
582
583 spin_lock(&c->space_lock);
584 c->budg_idx_growth -= req->idx_growth;
585 c->budg_uncommitted_idx += req->idx_growth;
586 c->budg_data_growth -= req->data_growth;
587 c->budg_dd_growth -= req->dd_growth;
588 c->min_idx_lebs = ubifs_calc_min_idx_lebs(c);
589
590 ubifs_assert(c->budg_idx_growth >= 0);
591 ubifs_assert(c->budg_data_growth >= 0);
Artem Bityutskiydab4b4d2008-07-24 14:52:45 +0300592 ubifs_assert(c->budg_dd_growth >= 0);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300593 ubifs_assert(c->min_idx_lebs < c->main_lebs);
Artem Bityutskiydab4b4d2008-07-24 14:52:45 +0300594 ubifs_assert(!(c->budg_idx_growth & 7));
595 ubifs_assert(!(c->budg_data_growth & 7));
596 ubifs_assert(!(c->budg_dd_growth & 7));
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300597 spin_unlock(&c->space_lock);
598}
599
600/**
601 * ubifs_convert_page_budget - convert budget of a new page.
602 * @c: UBIFS file-system description object
603 *
604 * This function converts budget which was allocated for a new page of data to
Frederik Schwarzer025dfda2008-10-16 19:02:37 +0200605 * the budget of changing an existing page of data. The latter is smaller than
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300606 * the former, so this function only does simple re-calculation and does not
607 * involve any write-back.
608 */
609void ubifs_convert_page_budget(struct ubifs_info *c)
610{
611 spin_lock(&c->space_lock);
612 /* Release the index growth reservation */
613 c->budg_idx_growth -= c->max_idx_node_sz << UBIFS_BLOCKS_PER_PAGE_SHIFT;
614 /* Release the data growth reservation */
615 c->budg_data_growth -= c->page_budget;
616 /* Increase the dirty data growth reservation instead */
617 c->budg_dd_growth += c->page_budget;
618 /* And re-calculate the indexing space reservation */
619 c->min_idx_lebs = ubifs_calc_min_idx_lebs(c);
620 spin_unlock(&c->space_lock);
621}
622
623/**
624 * ubifs_release_dirty_inode_budget - release dirty inode budget.
625 * @c: UBIFS file-system description object
626 * @ui: UBIFS inode to release the budget for
627 *
628 * This function releases budget corresponding to a dirty inode. It is usually
629 * called when after the inode has been written to the media and marked as
Adrian Hunter6d6cb0d2009-04-08 14:07:57 +0200630 * clean. It also causes the "no space" flags to be cleared.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300631 */
632void ubifs_release_dirty_inode_budget(struct ubifs_info *c,
633 struct ubifs_inode *ui)
634{
Artem Bityutskiy182854b2008-07-18 18:54:29 +0300635 struct ubifs_budget_req req;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300636
Artem Bityutskiy182854b2008-07-18 18:54:29 +0300637 memset(&req, 0, sizeof(struct ubifs_budget_req));
Adrian Hunter6d6cb0d2009-04-08 14:07:57 +0200638 /* The "no space" flags will be cleared because dd_growth is > 0 */
Artem Bityutskiydab4b4d2008-07-24 14:52:45 +0300639 req.dd_growth = c->inode_budget + ALIGN(ui->data_len, 8);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300640 ubifs_release_budget(c, &req);
641}
642
643/**
Artem Bityutskiy4b5f2762008-08-25 16:15:56 +0300644 * ubifs_reported_space - calculate reported free space.
645 * @c: the UBIFS file-system description object
646 * @free: amount of free space
647 *
648 * This function calculates amount of free space which will be reported to
649 * user-space. User-space application tend to expect that if the file-system
650 * (e.g., via the 'statfs()' call) reports that it has N bytes available, they
651 * are able to write a file of size N. UBIFS attaches node headers to each data
Artem Bityutskiy80736d42008-12-30 17:44:02 +0200652 * node and it has to write indexing nodes as well. This introduces additional
653 * overhead, and UBIFS has to report slightly less free space to meet the above
654 * expectations.
Artem Bityutskiy4b5f2762008-08-25 16:15:56 +0300655 *
656 * This function assumes free space is made up of uncompressed data nodes and
657 * full index nodes (one per data node, tripled because we always allow enough
658 * space to write the index thrice).
659 *
660 * Note, the calculation is pessimistic, which means that most of the time
661 * UBIFS reports less space than it actually has.
662 */
Artem Bityutskiy4d61db42008-12-18 14:06:51 +0200663long long ubifs_reported_space(const struct ubifs_info *c, long long free)
Artem Bityutskiy4b5f2762008-08-25 16:15:56 +0300664{
Artem Bityutskiyf171d4d2008-09-03 16:17:14 +0300665 int divisor, factor, f;
Artem Bityutskiy4b5f2762008-08-25 16:15:56 +0300666
667 /*
668 * Reported space size is @free * X, where X is UBIFS block size
669 * divided by UBIFS block size + all overhead one data block
670 * introduces. The overhead is the node header + indexing overhead.
671 *
Artem Bityutskiyf171d4d2008-09-03 16:17:14 +0300672 * Indexing overhead calculations are based on the following formula:
673 * I = N/(f - 1) + 1, where I - number of indexing nodes, N - number
674 * of data nodes, f - fanout. Because effective UBIFS fanout is twice
675 * as less than maximum fanout, we assume that each data node
Artem Bityutskiy4b5f2762008-08-25 16:15:56 +0300676 * introduces 3 * @c->max_idx_node_sz / (@c->fanout/2 - 1) bytes.
Artem Bityutskiy80736d42008-12-30 17:44:02 +0200677 * Note, the multiplier 3 is because UBIFS reserves thrice as more space
Artem Bityutskiy4b5f2762008-08-25 16:15:56 +0300678 * for the index.
679 */
Artem Bityutskiyf171d4d2008-09-03 16:17:14 +0300680 f = c->fanout > 3 ? c->fanout >> 1 : 2;
Artem Bityutskiy4b5f2762008-08-25 16:15:56 +0300681 factor = UBIFS_BLOCK_SIZE;
682 divisor = UBIFS_MAX_DATA_NODE_SZ;
Artem Bityutskiyf171d4d2008-09-03 16:17:14 +0300683 divisor += (c->max_idx_node_sz * 3) / (f - 1);
Artem Bityutskiy4b5f2762008-08-25 16:15:56 +0300684 free *= factor;
Artem Bityutskiy4d61db42008-12-18 14:06:51 +0200685 return div_u64(free, divisor);
Artem Bityutskiy4b5f2762008-08-25 16:15:56 +0300686}
687
688/**
Artem Bityutskiy84abf972009-01-23 14:54:59 +0200689 * ubifs_get_free_space_nolock - return amount of free space.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300690 * @c: UBIFS file-system description object
691 *
Artem Bityutskiy7dad1812008-08-25 18:58:19 +0300692 * This function calculates amount of free space to report to user-space.
693 *
694 * Because UBIFS may introduce substantial overhead (the index, node headers,
Artem Bityutskiyfb1cd012009-03-16 09:56:57 +0200695 * alignment, wastage at the end of LEBs, etc), it cannot report real amount of
696 * free flash space it has (well, because not all dirty space is reclaimable,
697 * UBIFS does not actually know the real amount). If UBIFS did so, it would
698 * bread user expectations about what free space is. Users seem to accustomed
699 * to assume that if the file-system reports N bytes of free space, they would
700 * be able to fit a file of N bytes to the FS. This almost works for
Artem Bityutskiy7dad1812008-08-25 18:58:19 +0300701 * traditional file-systems, because they have way less overhead than UBIFS.
702 * So, to keep users happy, UBIFS tries to take the overhead into account.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300703 */
Artem Bityutskiy84abf972009-01-23 14:54:59 +0200704long long ubifs_get_free_space_nolock(struct ubifs_info *c)
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300705{
Artem Bityutskiy84abf972009-01-23 14:54:59 +0200706 int rsvd_idx_lebs, lebs;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300707 long long available, outstanding, free;
708
Artem Bityutskiy84abf972009-01-23 14:54:59 +0200709 ubifs_assert(c->min_idx_lebs == ubifs_calc_min_idx_lebs(c));
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300710 outstanding = c->budg_data_growth + c->budg_dd_growth;
Artem Bityutskiy84abf972009-01-23 14:54:59 +0200711 available = ubifs_calc_available(c, c->min_idx_lebs);
Artem Bityutskiy7dad1812008-08-25 18:58:19 +0300712
713 /*
714 * When reporting free space to user-space, UBIFS guarantees that it is
715 * possible to write a file of free space size. This means that for
716 * empty LEBs we may use more precise calculations than
717 * 'ubifs_calc_available()' is using. Namely, we know that in empty
718 * LEBs we would waste only @c->leb_overhead bytes, not @c->dark_wm.
719 * Thus, amend the available space.
720 *
721 * Note, the calculations below are similar to what we have in
722 * 'do_budget_space()', so refer there for comments.
723 */
Artem Bityutskiy84abf972009-01-23 14:54:59 +0200724 if (c->min_idx_lebs > c->lst.idx_lebs)
725 rsvd_idx_lebs = c->min_idx_lebs - c->lst.idx_lebs;
Artem Bityutskiy7dad1812008-08-25 18:58:19 +0300726 else
727 rsvd_idx_lebs = 0;
728 lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt -
729 c->lst.taken_empty_lebs;
730 lebs -= rsvd_idx_lebs;
731 available += lebs * (c->dark_wm - c->leb_overhead);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300732
733 if (available > outstanding)
734 free = ubifs_reported_space(c, available - outstanding);
735 else
736 free = 0;
737 return free;
738}
Artem Bityutskiy84abf972009-01-23 14:54:59 +0200739
740/**
741 * ubifs_get_free_space - return amount of free space.
742 * @c: UBIFS file-system description object
743 *
744 * This function calculates and retuns amount of free space to report to
745 * user-space.
746 */
747long long ubifs_get_free_space(struct ubifs_info *c)
748{
749 long long free;
750
751 spin_lock(&c->space_lock);
752 free = ubifs_get_free_space_nolock(c);
753 spin_unlock(&c->space_lock);
754
755 return free;
756}