GNU Linux-libre 4.9.308-gnu1
[releases.git] / fs / ubifs / tnc_misc.c
1 /*
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 contains miscelanious TNC-related functions shared betweend
25  * different files. This file does not form any logically separate TNC
26  * sub-system. The file was created because there is a lot of TNC code and
27  * putting it all in one file would make that file too big and unreadable.
28  */
29
30 #include "ubifs.h"
31
32 /**
33  * ubifs_tnc_levelorder_next - next TNC tree element in levelorder traversal.
34  * @zr: root of the subtree to traverse
35  * @znode: previous znode
36  *
37  * This function implements levelorder TNC traversal. The LNC is ignored.
38  * Returns the next element or %NULL if @znode is already the last one.
39  */
40 struct ubifs_znode *ubifs_tnc_levelorder_next(struct ubifs_znode *zr,
41                                               struct ubifs_znode *znode)
42 {
43         int level, iip, level_search = 0;
44         struct ubifs_znode *zn;
45
46         ubifs_assert(zr);
47
48         if (unlikely(!znode))
49                 return zr;
50
51         if (unlikely(znode == zr)) {
52                 if (znode->level == 0)
53                         return NULL;
54                 return ubifs_tnc_find_child(zr, 0);
55         }
56
57         level = znode->level;
58
59         iip = znode->iip;
60         while (1) {
61                 ubifs_assert(znode->level <= zr->level);
62
63                 /*
64                  * First walk up until there is a znode with next branch to
65                  * look at.
66                  */
67                 while (znode->parent != zr && iip >= znode->parent->child_cnt) {
68                         znode = znode->parent;
69                         iip = znode->iip;
70                 }
71
72                 if (unlikely(znode->parent == zr &&
73                              iip >= znode->parent->child_cnt)) {
74                         /* This level is done, switch to the lower one */
75                         level -= 1;
76                         if (level_search || level < 0)
77                                 /*
78                                  * We were already looking for znode at lower
79                                  * level ('level_search'). As we are here
80                                  * again, it just does not exist. Or all levels
81                                  * were finished ('level < 0').
82                                  */
83                                 return NULL;
84
85                         level_search = 1;
86                         iip = -1;
87                         znode = ubifs_tnc_find_child(zr, 0);
88                         ubifs_assert(znode);
89                 }
90
91                 /* Switch to the next index */
92                 zn = ubifs_tnc_find_child(znode->parent, iip + 1);
93                 if (!zn) {
94                         /* No more children to look at, we have walk up */
95                         iip = znode->parent->child_cnt;
96                         continue;
97                 }
98
99                 /* Walk back down to the level we came from ('level') */
100                 while (zn->level != level) {
101                         znode = zn;
102                         zn = ubifs_tnc_find_child(zn, 0);
103                         if (!zn) {
104                                 /*
105                                  * This path is not too deep so it does not
106                                  * reach 'level'. Try next path.
107                                  */
108                                 iip = znode->iip;
109                                 break;
110                         }
111                 }
112
113                 if (zn) {
114                         ubifs_assert(zn->level >= 0);
115                         return zn;
116                 }
117         }
118 }
119
120 /**
121  * ubifs_search_zbranch - search znode branch.
122  * @c: UBIFS file-system description object
123  * @znode: znode to search in
124  * @key: key to search for
125  * @n: znode branch slot number is returned here
126  *
127  * This is a helper function which search branch with key @key in @znode using
128  * binary search. The result of the search may be:
129  *   o exact match, then %1 is returned, and the slot number of the branch is
130  *     stored in @n;
131  *   o no exact match, then %0 is returned and the slot number of the left
132  *     closest branch is returned in @n; the slot if all keys in this znode are
133  *     greater than @key, then %-1 is returned in @n.
134  */
135 int ubifs_search_zbranch(const struct ubifs_info *c,
136                          const struct ubifs_znode *znode,
137                          const union ubifs_key *key, int *n)
138 {
139         int beg = 0, end = znode->child_cnt, uninitialized_var(mid);
140         int uninitialized_var(cmp);
141         const struct ubifs_zbranch *zbr = &znode->zbranch[0];
142
143         ubifs_assert(end > beg);
144
145         while (end > beg) {
146                 mid = (beg + end) >> 1;
147                 cmp = keys_cmp(c, key, &zbr[mid].key);
148                 if (cmp > 0)
149                         beg = mid + 1;
150                 else if (cmp < 0)
151                         end = mid;
152                 else {
153                         *n = mid;
154                         return 1;
155                 }
156         }
157
158         *n = end - 1;
159
160         /* The insert point is after *n */
161         ubifs_assert(*n >= -1 && *n < znode->child_cnt);
162         if (*n == -1)
163                 ubifs_assert(keys_cmp(c, key, &zbr[0].key) < 0);
164         else
165                 ubifs_assert(keys_cmp(c, key, &zbr[*n].key) > 0);
166         if (*n + 1 < znode->child_cnt)
167                 ubifs_assert(keys_cmp(c, key, &zbr[*n + 1].key) < 0);
168
169         return 0;
170 }
171
172 /**
173  * ubifs_tnc_postorder_first - find first znode to do postorder tree traversal.
174  * @znode: znode to start at (root of the sub-tree to traverse)
175  *
176  * Find the lowest leftmost znode in a subtree of the TNC tree. The LNC is
177  * ignored.
178  */
179 struct ubifs_znode *ubifs_tnc_postorder_first(struct ubifs_znode *znode)
180 {
181         if (unlikely(!znode))
182                 return NULL;
183
184         while (znode->level > 0) {
185                 struct ubifs_znode *child;
186
187                 child = ubifs_tnc_find_child(znode, 0);
188                 if (!child)
189                         return znode;
190                 znode = child;
191         }
192
193         return znode;
194 }
195
196 /**
197  * ubifs_tnc_postorder_next - next TNC tree element in postorder traversal.
198  * @znode: previous znode
199  *
200  * This function implements postorder TNC traversal. The LNC is ignored.
201  * Returns the next element or %NULL if @znode is already the last one.
202  */
203 struct ubifs_znode *ubifs_tnc_postorder_next(struct ubifs_znode *znode)
204 {
205         struct ubifs_znode *zn;
206
207         ubifs_assert(znode);
208         if (unlikely(!znode->parent))
209                 return NULL;
210
211         /* Switch to the next index in the parent */
212         zn = ubifs_tnc_find_child(znode->parent, znode->iip + 1);
213         if (!zn)
214                 /* This is in fact the last child, return parent */
215                 return znode->parent;
216
217         /* Go to the first znode in this new subtree */
218         return ubifs_tnc_postorder_first(zn);
219 }
220
221 /**
222  * ubifs_destroy_tnc_subtree - destroy all znodes connected to a subtree.
223  * @znode: znode defining subtree to destroy
224  *
225  * This function destroys subtree of the TNC tree. Returns number of clean
226  * znodes in the subtree.
227  */
228 long ubifs_destroy_tnc_subtree(struct ubifs_znode *znode)
229 {
230         struct ubifs_znode *zn = ubifs_tnc_postorder_first(znode);
231         long clean_freed = 0;
232         int n;
233
234         ubifs_assert(zn);
235         while (1) {
236                 for (n = 0; n < zn->child_cnt; n++) {
237                         if (!zn->zbranch[n].znode)
238                                 continue;
239
240                         if (zn->level > 0 &&
241                             !ubifs_zn_dirty(zn->zbranch[n].znode))
242                                 clean_freed += 1;
243
244                         cond_resched();
245                         kfree(zn->zbranch[n].znode);
246                 }
247
248                 if (zn == znode) {
249                         if (!ubifs_zn_dirty(zn))
250                                 clean_freed += 1;
251                         kfree(zn);
252                         return clean_freed;
253                 }
254
255                 zn = ubifs_tnc_postorder_next(zn);
256         }
257 }
258
259 /**
260  * read_znode - read an indexing node from flash and fill znode.
261  * @c: UBIFS file-system description object
262  * @lnum: LEB of the indexing node to read
263  * @offs: node offset
264  * @len: node length
265  * @znode: znode to read to
266  *
267  * This function reads an indexing node from the flash media and fills znode
268  * with the read data. Returns zero in case of success and a negative error
269  * code in case of failure. The read indexing node is validated and if anything
270  * is wrong with it, this function prints complaint messages and returns
271  * %-EINVAL.
272  */
273 static int read_znode(struct ubifs_info *c, int lnum, int offs, int len,
274                       struct ubifs_znode *znode)
275 {
276         int i, err, type, cmp;
277         struct ubifs_idx_node *idx;
278
279         idx = kmalloc(c->max_idx_node_sz, GFP_NOFS);
280         if (!idx)
281                 return -ENOMEM;
282
283         err = ubifs_read_node(c, idx, UBIFS_IDX_NODE, len, lnum, offs);
284         if (err < 0) {
285                 kfree(idx);
286                 return err;
287         }
288
289         znode->child_cnt = le16_to_cpu(idx->child_cnt);
290         znode->level = le16_to_cpu(idx->level);
291
292         dbg_tnc("LEB %d:%d, level %d, %d branch",
293                 lnum, offs, znode->level, znode->child_cnt);
294
295         if (znode->child_cnt > c->fanout || znode->level > UBIFS_MAX_LEVELS) {
296                 ubifs_err(c, "current fanout %d, branch count %d",
297                           c->fanout, znode->child_cnt);
298                 ubifs_err(c, "max levels %d, znode level %d",
299                           UBIFS_MAX_LEVELS, znode->level);
300                 err = 1;
301                 goto out_dump;
302         }
303
304         for (i = 0; i < znode->child_cnt; i++) {
305                 const struct ubifs_branch *br = ubifs_idx_branch(c, idx, i);
306                 struct ubifs_zbranch *zbr = &znode->zbranch[i];
307
308                 key_read(c, &br->key, &zbr->key);
309                 zbr->lnum = le32_to_cpu(br->lnum);
310                 zbr->offs = le32_to_cpu(br->offs);
311                 zbr->len  = le32_to_cpu(br->len);
312                 zbr->znode = NULL;
313
314                 /* Validate branch */
315
316                 if (zbr->lnum < c->main_first ||
317                     zbr->lnum >= c->leb_cnt || zbr->offs < 0 ||
318                     zbr->offs + zbr->len > c->leb_size || zbr->offs & 7) {
319                         ubifs_err(c, "bad branch %d", i);
320                         err = 2;
321                         goto out_dump;
322                 }
323
324                 switch (key_type(c, &zbr->key)) {
325                 case UBIFS_INO_KEY:
326                 case UBIFS_DATA_KEY:
327                 case UBIFS_DENT_KEY:
328                 case UBIFS_XENT_KEY:
329                         break;
330                 default:
331                         ubifs_err(c, "bad key type at slot %d: %d",
332                                   i, key_type(c, &zbr->key));
333                         err = 3;
334                         goto out_dump;
335                 }
336
337                 if (znode->level)
338                         continue;
339
340                 type = key_type(c, &zbr->key);
341                 if (c->ranges[type].max_len == 0) {
342                         if (zbr->len != c->ranges[type].len) {
343                                 ubifs_err(c, "bad target node (type %d) length (%d)",
344                                           type, zbr->len);
345                                 ubifs_err(c, "have to be %d", c->ranges[type].len);
346                                 err = 4;
347                                 goto out_dump;
348                         }
349                 } else if (zbr->len < c->ranges[type].min_len ||
350                            zbr->len > c->ranges[type].max_len) {
351                         ubifs_err(c, "bad target node (type %d) length (%d)",
352                                   type, zbr->len);
353                         ubifs_err(c, "have to be in range of %d-%d",
354                                   c->ranges[type].min_len,
355                                   c->ranges[type].max_len);
356                         err = 5;
357                         goto out_dump;
358                 }
359         }
360
361         /*
362          * Ensure that the next key is greater or equivalent to the
363          * previous one.
364          */
365         for (i = 0; i < znode->child_cnt - 1; i++) {
366                 const union ubifs_key *key1, *key2;
367
368                 key1 = &znode->zbranch[i].key;
369                 key2 = &znode->zbranch[i + 1].key;
370
371                 cmp = keys_cmp(c, key1, key2);
372                 if (cmp > 0) {
373                         ubifs_err(c, "bad key order (keys %d and %d)", i, i + 1);
374                         err = 6;
375                         goto out_dump;
376                 } else if (cmp == 0 && !is_hash_key(c, key1)) {
377                         /* These can only be keys with colliding hash */
378                         ubifs_err(c, "keys %d and %d are not hashed but equivalent",
379                                   i, i + 1);
380                         err = 7;
381                         goto out_dump;
382                 }
383         }
384
385         kfree(idx);
386         return 0;
387
388 out_dump:
389         ubifs_err(c, "bad indexing node at LEB %d:%d, error %d", lnum, offs, err);
390         ubifs_dump_node(c, idx);
391         kfree(idx);
392         return -EINVAL;
393 }
394
395 /**
396  * ubifs_load_znode - load znode to TNC cache.
397  * @c: UBIFS file-system description object
398  * @zbr: znode branch
399  * @parent: znode's parent
400  * @iip: index in parent
401  *
402  * This function loads znode pointed to by @zbr into the TNC cache and
403  * returns pointer to it in case of success and a negative error code in case
404  * of failure.
405  */
406 struct ubifs_znode *ubifs_load_znode(struct ubifs_info *c,
407                                      struct ubifs_zbranch *zbr,
408                                      struct ubifs_znode *parent, int iip)
409 {
410         int err;
411         struct ubifs_znode *znode;
412
413         ubifs_assert(!zbr->znode);
414         /*
415          * A slab cache is not presently used for znodes because the znode size
416          * depends on the fanout which is stored in the superblock.
417          */
418         znode = kzalloc(c->max_znode_sz, GFP_NOFS);
419         if (!znode)
420                 return ERR_PTR(-ENOMEM);
421
422         err = read_znode(c, zbr->lnum, zbr->offs, zbr->len, znode);
423         if (err)
424                 goto out;
425
426         atomic_long_inc(&c->clean_zn_cnt);
427
428         /*
429          * Increment the global clean znode counter as well. It is OK that
430          * global and per-FS clean znode counters may be inconsistent for some
431          * short time (because we might be preempted at this point), the global
432          * one is only used in shrinker.
433          */
434         atomic_long_inc(&ubifs_clean_zn_cnt);
435
436         zbr->znode = znode;
437         znode->parent = parent;
438         znode->time = get_seconds();
439         znode->iip = iip;
440
441         return znode;
442
443 out:
444         kfree(znode);
445         return ERR_PTR(err);
446 }
447
448 /**
449  * ubifs_tnc_read_node - read a leaf node from the flash media.
450  * @c: UBIFS file-system description object
451  * @zbr: key and position of the node
452  * @node: node is returned here
453  *
454  * This function reads a node defined by @zbr from the flash media. Returns
455  * zero in case of success or a negative negative error code in case of
456  * failure.
457  */
458 int ubifs_tnc_read_node(struct ubifs_info *c, struct ubifs_zbranch *zbr,
459                         void *node)
460 {
461         union ubifs_key key1, *key = &zbr->key;
462         int err, type = key_type(c, key);
463         struct ubifs_wbuf *wbuf;
464
465         /*
466          * 'zbr' has to point to on-flash node. The node may sit in a bud and
467          * may even be in a write buffer, so we have to take care about this.
468          */
469         wbuf = ubifs_get_wbuf(c, zbr->lnum);
470         if (wbuf)
471                 err = ubifs_read_node_wbuf(wbuf, node, type, zbr->len,
472                                            zbr->lnum, zbr->offs);
473         else
474                 err = ubifs_read_node(c, node, type, zbr->len, zbr->lnum,
475                                       zbr->offs);
476
477         if (err) {
478                 dbg_tnck(key, "key ");
479                 return err;
480         }
481
482         /* Make sure the key of the read node is correct */
483         key_read(c, node + UBIFS_KEY_OFFSET, &key1);
484         if (!keys_eq(c, key, &key1)) {
485                 ubifs_err(c, "bad key in node at LEB %d:%d",
486                           zbr->lnum, zbr->offs);
487                 dbg_tnck(key, "looked for key ");
488                 dbg_tnck(&key1, "but found node's key ");
489                 ubifs_dump_node(c, node);
490                 return -EINVAL;
491         }
492
493         return 0;
494 }