1	// SPDX-License-Identifier: GPL-2.0-only
2	/*
3	* This file is part of UBIFS.
4	*
5	* Copyright (C) 2006-2008 Nokia Corporation
6	*
7	* Authors: Artem Bityutskiy (Битюцкий Артём)
8	* Adrian Hunter
9	*/
10
11	/*
12	* This file implements most of the debugging stuff which is compiled in only
13	* when it is enabled. But some debugging check functions are implemented in
14	* corresponding subsystem, just because they are closely related and utilize
15	* various local functions of those subsystems.
16	*/
17
18	#include <linux/module.h>
19	#include <linux/debugfs.h>
20	#include <linux/math64.h>
21	#include <linux/uaccess.h>
22	#include <linux/random.h>
23	#include <linux/ctype.h>
24	#include "ubifs.h"
25
26	static DEFINE_SPINLOCK(dbg_lock);
27
28	static const char *get_key_fmt(int fmt)
29	{
30	switch (fmt) {
31	case UBIFS_SIMPLE_KEY_FMT:
32	return "simple";
33	default:
34	return "unknown/invalid format";
35	}
36	}
37
38	static const char *get_key_hash(int hash)
39	{
40	switch (hash) {
41	case UBIFS_KEY_HASH_R5:
42	return "R5";
43	case UBIFS_KEY_HASH_TEST:
44	return "test";
45	default:
46	return "unknown/invalid name hash";
47	}
48	}
49
50	static const char *get_key_type(int type)
51	{
52	switch (type) {
53	case UBIFS_INO_KEY:
54	return "inode";
55	case UBIFS_DENT_KEY:
56	return "direntry";
57	case UBIFS_XENT_KEY:
58	return "xentry";
59	case UBIFS_DATA_KEY:
60	return "data";
61	case UBIFS_TRUN_KEY:
62	return "truncate";
63	default:
64	return "unknown/invalid key";
65	}
66	}
67
68	static const char *get_dent_type(int type)
69	{
70	switch (type) {
71	case UBIFS_ITYPE_REG:
72	return "file";
73	case UBIFS_ITYPE_DIR:
74	return "dir";
75	case UBIFS_ITYPE_LNK:
76	return "symlink";
77	case UBIFS_ITYPE_BLK:
78	return "blkdev";
79	case UBIFS_ITYPE_CHR:
80	return "char dev";
81	case UBIFS_ITYPE_FIFO:
82	return "fifo";
83	case UBIFS_ITYPE_SOCK:
84	return "socket";
85	default:
86	return "unknown/invalid type";
87	}
88	}
89
90	const char *dbg_snprintf_key(const struct ubifs_info *c,
91	const union ubifs_key *key, char *buffer, int len)
92	{
93	char *p = buffer;
94	int type = key_type(c, key);
95
96	if (c->key_fmt == UBIFS_SIMPLE_KEY_FMT) {
97	switch (type) {
98	case UBIFS_INO_KEY:
99	len -= snprintf(buf: p, size: len, fmt: "(%lu, %s)",
100	(unsigned long)key_inum(c, k: key),
101	get_key_type(type));
102	break;
103	case UBIFS_DENT_KEY:
104	case UBIFS_XENT_KEY:
105	len -= snprintf(buf: p, size: len, fmt: "(%lu, %s, %#08x)",
106	(unsigned long)key_inum(c, k: key),
107	get_key_type(type), key_hash(c, key));
108	break;
109	case UBIFS_DATA_KEY:
110	len -= snprintf(buf: p, size: len, fmt: "(%lu, %s, %u)",
111	(unsigned long)key_inum(c, k: key),
112	get_key_type(type), key_block(c, key));
113	break;
114	case UBIFS_TRUN_KEY:
115	len -= snprintf(buf: p, size: len, fmt: "(%lu, %s)",
116	(unsigned long)key_inum(c, k: key),
117	get_key_type(type));
118	break;
119	default:
120	len -= snprintf(buf: p, size: len, fmt: "(bad key type: %#08x, %#08x)",
121	key->u32[0], key->u32[1]);
122	}
123	} else
124	len -= snprintf(buf: p, size: len, fmt: "bad key format %d", c->key_fmt);
125	ubifs_assert(c, len > 0);
126	return p;
127	}
128
129	const char *dbg_ntype(int type)
130	{
131	switch (type) {
132	case UBIFS_PAD_NODE:
133	return "padding node";
134	case UBIFS_SB_NODE:
135	return "superblock node";
136	case UBIFS_MST_NODE:
137	return "master node";
138	case UBIFS_REF_NODE:
139	return "reference node";
140	case UBIFS_INO_NODE:
141	return "inode node";
142	case UBIFS_DENT_NODE:
143	return "direntry node";
144	case UBIFS_XENT_NODE:
145	return "xentry node";
146	case UBIFS_DATA_NODE:
147	return "data node";
148	case UBIFS_TRUN_NODE:
149	return "truncate node";
150	case UBIFS_IDX_NODE:
151	return "indexing node";
152	case UBIFS_CS_NODE:
153	return "commit start node";
154	case UBIFS_ORPH_NODE:
155	return "orphan node";
156	case UBIFS_AUTH_NODE:
157	return "auth node";
158	default:
159	return "unknown node";
160	}
161	}
162
163	static const char *dbg_gtype(int type)
164	{
165	switch (type) {
166	case UBIFS_NO_NODE_GROUP:
167	return "no node group";
168	case UBIFS_IN_NODE_GROUP:
169	return "in node group";
170	case UBIFS_LAST_OF_NODE_GROUP:
171	return "last of node group";
172	default:
173	return "unknown";
174	}
175	}
176
177	const char *dbg_cstate(int cmt_state)
178	{
179	switch (cmt_state) {
180	case COMMIT_RESTING:
181	return "commit resting";
182	case COMMIT_BACKGROUND:
183	return "background commit requested";
184	case COMMIT_REQUIRED:
185	return "commit required";
186	case COMMIT_RUNNING_BACKGROUND:
187	return "BACKGROUND commit running";
188	case COMMIT_RUNNING_REQUIRED:
189	return "commit running and required";
190	case COMMIT_BROKEN:
191	return "broken commit";
192	default:
193	return "unknown commit state";
194	}
195	}
196
197	const char *dbg_jhead(int jhead)
198	{
199	switch (jhead) {
200	case GCHD:
201	return "0 (GC)";
202	case BASEHD:
203	return "1 (base)";
204	case DATAHD:
205	return "2 (data)";
206	default:
207	return "unknown journal head";
208	}
209	}
210
211	static void dump_ch(const struct ubifs_ch *ch)
212	{
213	pr_err("\tmagic %#x\n", le32_to_cpu(ch->magic));
214	pr_err("\tcrc %#x\n", le32_to_cpu(ch->crc));
215	pr_err("\tnode_type %d (%s)\n", ch->node_type,
216	dbg_ntype(ch->node_type));
217	pr_err("\tgroup_type %d (%s)\n", ch->group_type,
218	dbg_gtype(ch->group_type));
219	pr_err("\tsqnum %llu\n",
220	(unsigned long long)le64_to_cpu(ch->sqnum));
221	pr_err("\tlen %u\n", le32_to_cpu(ch->len));
222	}
223
224	void ubifs_dump_inode(struct ubifs_info *c, const struct inode *inode)
225	{
226	const struct ubifs_inode *ui = ubifs_inode(inode);
227	struct fscrypt_name nm = {0};
228	union ubifs_key key;
229	struct ubifs_dent_node *dent, *pdent = NULL;
230	int count = 2;
231
232	pr_err("Dump in-memory inode:");
233	pr_err("\tinode %lu\n", inode->i_ino);
234	pr_err("\tsize %llu\n",
235	(unsigned long long)i_size_read(inode));
236	pr_err("\tnlink %u\n", inode->i_nlink);
237	pr_err("\tuid %u\n", (unsigned int)i_uid_read(inode));
238	pr_err("\tgid %u\n", (unsigned int)i_gid_read(inode));
239	pr_err("\tatime %u.%u\n",
240	(unsigned int) inode_get_atime_sec(inode),
241	(unsigned int) inode_get_atime_nsec(inode));
242	pr_err("\tmtime %u.%u\n",
243	(unsigned int) inode_get_mtime_sec(inode),
244	(unsigned int) inode_get_mtime_nsec(inode));
245	pr_err("\tctime %u.%u\n",
246	(unsigned int) inode_get_ctime_sec(inode),
247	(unsigned int) inode_get_ctime_nsec(inode));
248	pr_err("\tcreat_sqnum %llu\n", ui->creat_sqnum);
249	pr_err("\txattr_size %u\n", ui->xattr_size);
250	pr_err("\txattr_cnt %u\n", ui->xattr_cnt);
251	pr_err("\txattr_names %u\n", ui->xattr_names);
252	pr_err("\tdirty %u\n", ui->dirty);
253	pr_err("\txattr %u\n", ui->xattr);
254	pr_err("\tbulk_read %u\n", ui->bulk_read);
255	pr_err("\tsynced_i_size %llu\n",
256	(unsigned long long)ui->synced_i_size);
257	pr_err("\tui_size %llu\n",
258	(unsigned long long)ui->ui_size);
259	pr_err("\tflags %d\n", ui->flags);
260	pr_err("\tcompr_type %d\n", ui->compr_type);
261	pr_err("\tlast_page_read %lu\n", ui->last_page_read);
262	pr_err("\tread_in_a_row %lu\n", ui->read_in_a_row);
263	pr_err("\tdata_len %d\n", ui->data_len);
264
265	if (!S_ISDIR(inode->i_mode))
266	return;
267
268	pr_err("List of directory entries:\n");
269	ubifs_assert(c, !mutex_is_locked(&c->tnc_mutex));
270
271	lowest_dent_key(c, key: &key, inum: inode->i_ino);
272	while (1) {
273	dent = ubifs_tnc_next_ent(c, key: &key, nm: &nm);
274	if (IS_ERR(ptr: dent)) {
275	if (PTR_ERR(ptr: dent) != -ENOENT)
276	pr_err("error %ld\n", PTR_ERR(dent));
277	break;
278	}
279
280	pr_err("\t%d: inode %llu, type %s, len %d\n",
281	count++, (unsigned long long) le64_to_cpu(dent->inum),
282	get_dent_type(dent->type),
283	le16_to_cpu(dent->nlen));
284
285	fname_name(&nm) = dent->name;
286	fname_len(&nm) = le16_to_cpu(dent->nlen);
287	kfree(objp: pdent);
288	pdent = dent;
289	key_read(c, from: &dent->key, to: &key);
290	}
291	kfree(objp: pdent);
292	}
293
294	void ubifs_dump_node(const struct ubifs_info *c, const void *node, int node_len)
295	{
296	int i, n, type, safe_len, max_node_len, min_node_len;
297	union ubifs_key key;
298	const struct ubifs_ch *ch = node;
299	char key_buf[DBG_KEY_BUF_LEN];
300
301	/* If the magic is incorrect, just hexdump the first bytes */
302	if (le32_to_cpu(ch->magic) != UBIFS_NODE_MAGIC) {
303	pr_err("Not a node, first %zu bytes:", UBIFS_CH_SZ);
304	print_hex_dump(KERN_ERR, prefix_str: "", prefix_type: DUMP_PREFIX_OFFSET, rowsize: 32, groupsize: 1,
305	buf: (void *)node, UBIFS_CH_SZ, ascii: 1);
306	return;
307	}
308
309	/* Skip dumping unknown type node */
310	type = ch->node_type;
311	if (type < 0 || type >= UBIFS_NODE_TYPES_CNT) {
312	pr_err("node type %d was not recognized\n", type);
313	return;
314	}
315
316	spin_lock(lock: &dbg_lock);
317	dump_ch(ch: node);
318
319	if (c->ranges[type].max_len == 0) {
320	max_node_len = min_node_len = c->ranges[type].len;
321	} else {
322	max_node_len = c->ranges[type].max_len;
323	min_node_len = c->ranges[type].min_len;
324	}
325	safe_len = le32_to_cpu(ch->len);
326	safe_len = safe_len > 0 ? safe_len : 0;
327	safe_len = min3(safe_len, max_node_len, node_len);
328	if (safe_len < min_node_len) {
329	pr_err("node len(%d) is too short for %s, left %d bytes:\n",
330	safe_len, dbg_ntype(type),
331	safe_len > UBIFS_CH_SZ ?
332	safe_len - (int)UBIFS_CH_SZ : 0);
333	if (safe_len > UBIFS_CH_SZ)
334	print_hex_dump(KERN_ERR, prefix_str: "", prefix_type: DUMP_PREFIX_OFFSET, rowsize: 32, groupsize: 1,
335	buf: (void *)node + UBIFS_CH_SZ,
336	len: safe_len - UBIFS_CH_SZ, ascii: 0);
337	goto out_unlock;
338	}
339	if (safe_len != le32_to_cpu(ch->len))
340	pr_err("\ttruncated node length %d\n", safe_len);
341
342	switch (type) {
343	case UBIFS_PAD_NODE:
344	{
345	const struct ubifs_pad_node *pad = node;
346
347	pr_err("\tpad_len %u\n", le32_to_cpu(pad->pad_len));
348	break;
349	}
350	case UBIFS_SB_NODE:
351	{
352	const struct ubifs_sb_node *sup = node;
353	unsigned int sup_flags = le32_to_cpu(sup->flags);
354
355	pr_err("\tkey_hash %d (%s)\n",
356	(int)sup->key_hash, get_key_hash(sup->key_hash));
357	pr_err("\tkey_fmt %d (%s)\n",
358	(int)sup->key_fmt, get_key_fmt(sup->key_fmt));
359	pr_err("\tflags %#x\n", sup_flags);
360	pr_err("\tbig_lpt %u\n",
361	!!(sup_flags & UBIFS_FLG_BIGLPT));
362	pr_err("\tspace_fixup %u\n",
363	!!(sup_flags & UBIFS_FLG_SPACE_FIXUP));
364	pr_err("\tmin_io_size %u\n", le32_to_cpu(sup->min_io_size));
365	pr_err("\tleb_size %u\n", le32_to_cpu(sup->leb_size));
366	pr_err("\tleb_cnt %u\n", le32_to_cpu(sup->leb_cnt));
367	pr_err("\tmax_leb_cnt %u\n", le32_to_cpu(sup->max_leb_cnt));
368	pr_err("\tmax_bud_bytes %llu\n",
369	(unsigned long long)le64_to_cpu(sup->max_bud_bytes));
370	pr_err("\tlog_lebs %u\n", le32_to_cpu(sup->log_lebs));
371	pr_err("\tlpt_lebs %u\n", le32_to_cpu(sup->lpt_lebs));
372	pr_err("\torph_lebs %u\n", le32_to_cpu(sup->orph_lebs));
373	pr_err("\tjhead_cnt %u\n", le32_to_cpu(sup->jhead_cnt));
374	pr_err("\tfanout %u\n", le32_to_cpu(sup->fanout));
375	pr_err("\tlsave_cnt %u\n", le32_to_cpu(sup->lsave_cnt));
376	pr_err("\tdefault_compr %u\n",
377	(int)le16_to_cpu(sup->default_compr));
378	pr_err("\trp_size %llu\n",
379	(unsigned long long)le64_to_cpu(sup->rp_size));
380	pr_err("\trp_uid %u\n", le32_to_cpu(sup->rp_uid));
381	pr_err("\trp_gid %u\n", le32_to_cpu(sup->rp_gid));
382	pr_err("\tfmt_version %u\n", le32_to_cpu(sup->fmt_version));
383	pr_err("\ttime_gran %u\n", le32_to_cpu(sup->time_gran));
384	pr_err("\tUUID %pUB\n", sup->uuid);
385	break;
386	}
387	case UBIFS_MST_NODE:
388	{
389	const struct ubifs_mst_node *mst = node;
390
391	pr_err("\thighest_inum %llu\n",
392	(unsigned long long)le64_to_cpu(mst->highest_inum));
393	pr_err("\tcommit number %llu\n",
394	(unsigned long long)le64_to_cpu(mst->cmt_no));
395	pr_err("\tflags %#x\n", le32_to_cpu(mst->flags));
396	pr_err("\tlog_lnum %u\n", le32_to_cpu(mst->log_lnum));
397	pr_err("\troot_lnum %u\n", le32_to_cpu(mst->root_lnum));
398	pr_err("\troot_offs %u\n", le32_to_cpu(mst->root_offs));
399	pr_err("\troot_len %u\n", le32_to_cpu(mst->root_len));
400	pr_err("\tgc_lnum %u\n", le32_to_cpu(mst->gc_lnum));
401	pr_err("\tihead_lnum %u\n", le32_to_cpu(mst->ihead_lnum));
402	pr_err("\tihead_offs %u\n", le32_to_cpu(mst->ihead_offs));
403	pr_err("\tindex_size %llu\n",
404	(unsigned long long)le64_to_cpu(mst->index_size));
405	pr_err("\tlpt_lnum %u\n", le32_to_cpu(mst->lpt_lnum));
406	pr_err("\tlpt_offs %u\n", le32_to_cpu(mst->lpt_offs));
407	pr_err("\tnhead_lnum %u\n", le32_to_cpu(mst->nhead_lnum));
408	pr_err("\tnhead_offs %u\n", le32_to_cpu(mst->nhead_offs));
409	pr_err("\tltab_lnum %u\n", le32_to_cpu(mst->ltab_lnum));
410	pr_err("\tltab_offs %u\n", le32_to_cpu(mst->ltab_offs));
411	pr_err("\tlsave_lnum %u\n", le32_to_cpu(mst->lsave_lnum));
412	pr_err("\tlsave_offs %u\n", le32_to_cpu(mst->lsave_offs));
413	pr_err("\tlscan_lnum %u\n", le32_to_cpu(mst->lscan_lnum));
414	pr_err("\tleb_cnt %u\n", le32_to_cpu(mst->leb_cnt));
415	pr_err("\tempty_lebs %u\n", le32_to_cpu(mst->empty_lebs));
416	pr_err("\tidx_lebs %u\n", le32_to_cpu(mst->idx_lebs));
417	pr_err("\ttotal_free %llu\n",
418	(unsigned long long)le64_to_cpu(mst->total_free));
419	pr_err("\ttotal_dirty %llu\n",
420	(unsigned long long)le64_to_cpu(mst->total_dirty));
421	pr_err("\ttotal_used %llu\n",
422	(unsigned long long)le64_to_cpu(mst->total_used));
423	pr_err("\ttotal_dead %llu\n",
424	(unsigned long long)le64_to_cpu(mst->total_dead));
425	pr_err("\ttotal_dark %llu\n",
426	(unsigned long long)le64_to_cpu(mst->total_dark));
427	break;
428	}
429	case UBIFS_REF_NODE:
430	{
431	const struct ubifs_ref_node *ref = node;
432
433	pr_err("\tlnum %u\n", le32_to_cpu(ref->lnum));
434	pr_err("\toffs %u\n", le32_to_cpu(ref->offs));
435	pr_err("\tjhead %u\n", le32_to_cpu(ref->jhead));
436	break;
437	}
438	case UBIFS_INO_NODE:
439	{
440	const struct ubifs_ino_node *ino = node;
441
442	key_read(c, from: &ino->key, to: &key);
443	pr_err("\tkey %s\n",
444	dbg_snprintf_key(c, &key, key_buf, DBG_KEY_BUF_LEN));
445	pr_err("\tcreat_sqnum %llu\n",
446	(unsigned long long)le64_to_cpu(ino->creat_sqnum));
447	pr_err("\tsize %llu\n",
448	(unsigned long long)le64_to_cpu(ino->size));
449	pr_err("\tnlink %u\n", le32_to_cpu(ino->nlink));
450	pr_err("\tatime %lld.%u\n",
451	(long long)le64_to_cpu(ino->atime_sec),
452	le32_to_cpu(ino->atime_nsec));
453	pr_err("\tmtime %lld.%u\n",
454	(long long)le64_to_cpu(ino->mtime_sec),
455	le32_to_cpu(ino->mtime_nsec));
456	pr_err("\tctime %lld.%u\n",
457	(long long)le64_to_cpu(ino->ctime_sec),
458	le32_to_cpu(ino->ctime_nsec));
459	pr_err("\tuid %u\n", le32_to_cpu(ino->uid));
460	pr_err("\tgid %u\n", le32_to_cpu(ino->gid));
461	pr_err("\tmode %u\n", le32_to_cpu(ino->mode));
462	pr_err("\tflags %#x\n", le32_to_cpu(ino->flags));
463	pr_err("\txattr_cnt %u\n", le32_to_cpu(ino->xattr_cnt));
464	pr_err("\txattr_size %u\n", le32_to_cpu(ino->xattr_size));
465	pr_err("\txattr_names %u\n", le32_to_cpu(ino->xattr_names));
466	pr_err("\tcompr_type %#x\n",
467	(int)le16_to_cpu(ino->compr_type));
468	pr_err("\tdata len %u\n", le32_to_cpu(ino->data_len));
469	break;
470	}
471	case UBIFS_DENT_NODE:
472	case UBIFS_XENT_NODE:
473	{
474	const struct ubifs_dent_node *dent = node;
475	int nlen = le16_to_cpu(dent->nlen);
476
477	key_read(c, from: &dent->key, to: &key);
478	pr_err("\tkey %s\n",
479	dbg_snprintf_key(c, &key, key_buf, DBG_KEY_BUF_LEN));
480	pr_err("\tinum %llu\n",
481	(unsigned long long)le64_to_cpu(dent->inum));
482	pr_err("\ttype %d\n", (int)dent->type);
483	pr_err("\tnlen %d\n", nlen);
484	pr_err("\tname ");
485
486	if (nlen > UBIFS_MAX_NLEN ||
487	nlen > safe_len - UBIFS_DENT_NODE_SZ)
488	pr_err("(bad name length, not printing, bad or corrupted node)");
489	else {
490	for (i = 0; i < nlen && dent->name[i]; i++)
491	pr_cont("%c", isprint(dent->name[i]) ?
492	dent->name[i] : '?');
493	}
494	pr_cont("\n");
495
496	break;
497	}
498	case UBIFS_DATA_NODE:
499	{
500	const struct ubifs_data_node *dn = node;
501
502	key_read(c, from: &dn->key, to: &key);
503	pr_err("\tkey %s\n",
504	dbg_snprintf_key(c, &key, key_buf, DBG_KEY_BUF_LEN));
505	pr_err("\tsize %u\n", le32_to_cpu(dn->size));
506	pr_err("\tcompr_typ %d\n",
507	(int)le16_to_cpu(dn->compr_type));
508	pr_err("\tdata size %u\n",
509	le32_to_cpu(ch->len) - (unsigned int)UBIFS_DATA_NODE_SZ);
510	pr_err("\tdata (length = %d):\n",
511	safe_len - (int)UBIFS_DATA_NODE_SZ);
512	print_hex_dump(KERN_ERR, prefix_str: "\t", prefix_type: DUMP_PREFIX_OFFSET, rowsize: 32, groupsize: 1,
513	buf: (void *)&dn->data,
514	len: safe_len - (int)UBIFS_DATA_NODE_SZ, ascii: 0);
515	break;
516	}
517	case UBIFS_TRUN_NODE:
518	{
519	const struct ubifs_trun_node *trun = node;
520
521	pr_err("\tinum %u\n", le32_to_cpu(trun->inum));
522	pr_err("\told_size %llu\n",
523	(unsigned long long)le64_to_cpu(trun->old_size));
524	pr_err("\tnew_size %llu\n",
525	(unsigned long long)le64_to_cpu(trun->new_size));
526	break;
527	}
528	case UBIFS_IDX_NODE:
529	{
530	const struct ubifs_idx_node *idx = node;
531	int max_child_cnt = (safe_len - UBIFS_IDX_NODE_SZ) /
532	(ubifs_idx_node_sz(c, child_cnt: 1) -
533	UBIFS_IDX_NODE_SZ);
534
535	n = min_t(int, le16_to_cpu(idx->child_cnt), max_child_cnt);
536	pr_err("\tchild_cnt %d\n", (int)le16_to_cpu(idx->child_cnt));
537	pr_err("\tlevel %d\n", (int)le16_to_cpu(idx->level));
538	pr_err("\tBranches:\n");
539
540	for (i = 0; i < n && i < c->fanout; i++) {
541	const struct ubifs_branch *br;
542
543	br = ubifs_idx_branch(c, idx, bnum: i);
544	key_read(c, from: &br->key, to: &key);
545	pr_err("\t%d: LEB %d:%d len %d key %s\n",
546	i, le32_to_cpu(br->lnum), le32_to_cpu(br->offs),
547	le32_to_cpu(br->len),
548	dbg_snprintf_key(c, &key, key_buf,
549	DBG_KEY_BUF_LEN));
550	}
551	break;
552	}
553	case UBIFS_CS_NODE:
554	break;
555	case UBIFS_ORPH_NODE:
556	{
557	const struct ubifs_orph_node *orph = node;
558
559	pr_err("\tcommit number %llu\n",
560	(unsigned long long)
561	le64_to_cpu(orph->cmt_no) & LLONG_MAX);
562	pr_err("\tlast node flag %llu\n",
563	(unsigned long long)(le64_to_cpu(orph->cmt_no)) >> 63);
564	n = (safe_len - UBIFS_ORPH_NODE_SZ) >> 3;
565	pr_err("\t%d orphan inode numbers:\n", n);
566	for (i = 0; i < n; i++)
567	pr_err("\t ino %llu\n",
568	(unsigned long long)le64_to_cpu(orph->inos[i]));
569	break;
570	}
571	case UBIFS_AUTH_NODE:
572	{
573	break;
574	}
575	default:
576	pr_err("node type %d was not recognized\n", type);
577	}
578
579	out_unlock:
580	spin_unlock(lock: &dbg_lock);
581	}
582
583	void ubifs_dump_budget_req(const struct ubifs_budget_req *req)
584	{
585	spin_lock(lock: &dbg_lock);
586	pr_err("Budgeting request: new_ino %d, dirtied_ino %d\n",
587	req->new_ino, req->dirtied_ino);
588	pr_err("\tnew_ino_d %d, dirtied_ino_d %d\n",
589	req->new_ino_d, req->dirtied_ino_d);
590	pr_err("\tnew_page %d, dirtied_page %d\n",
591	req->new_page, req->dirtied_page);
592	pr_err("\tnew_dent %d, mod_dent %d\n",
593	req->new_dent, req->mod_dent);
594	pr_err("\tidx_growth %d\n", req->idx_growth);
595	pr_err("\tdata_growth %d dd_growth %d\n",
596	req->data_growth, req->dd_growth);
597	spin_unlock(lock: &dbg_lock);
598	}
599
600	void ubifs_dump_lstats(const struct ubifs_lp_stats *lst)
601	{
602	spin_lock(lock: &dbg_lock);
603	pr_err("(pid %d) Lprops statistics: empty_lebs %d, idx_lebs %d\n",
604	current->pid, lst->empty_lebs, lst->idx_lebs);
605	pr_err("\ttaken_empty_lebs %d, total_free %lld, total_dirty %lld\n",
606	lst->taken_empty_lebs, lst->total_free, lst->total_dirty);
607	pr_err("\ttotal_used %lld, total_dark %lld, total_dead %lld\n",
608	lst->total_used, lst->total_dark, lst->total_dead);
609	spin_unlock(lock: &dbg_lock);
610	}
611
612	void ubifs_dump_budg(struct ubifs_info *c, const struct ubifs_budg_info *bi)
613	{
614	int i;
615	struct rb_node *rb;
616	struct ubifs_bud *bud;
617	struct ubifs_gced_idx_leb *idx_gc;
618	long long available, outstanding, free;
619
620	spin_lock(lock: &c->space_lock);
621	spin_lock(lock: &dbg_lock);
622	pr_err("(pid %d) Budgeting info: data budget sum %lld, total budget sum %lld\n",
623	current->pid, bi->data_growth + bi->dd_growth,
624	bi->data_growth + bi->dd_growth + bi->idx_growth);
625	pr_err("\tbudg_data_growth %lld, budg_dd_growth %lld, budg_idx_growth %lld\n",
626	bi->data_growth, bi->dd_growth, bi->idx_growth);
627	pr_err("\tmin_idx_lebs %d, old_idx_sz %llu, uncommitted_idx %lld\n",
628	bi->min_idx_lebs, bi->old_idx_sz, bi->uncommitted_idx);
629	pr_err("\tpage_budget %d, inode_budget %d, dent_budget %d\n",
630	bi->page_budget, bi->inode_budget, bi->dent_budget);
631	pr_err("\tnospace %u, nospace_rp %u\n", bi->nospace, bi->nospace_rp);
632	pr_err("\tdark_wm %d, dead_wm %d, max_idx_node_sz %d\n",
633	c->dark_wm, c->dead_wm, c->max_idx_node_sz);
634
635	if (bi != &c->bi)
636	/*
637	* If we are dumping saved budgeting data, do not print
638	* additional information which is about the current state, not
639	* the old one which corresponded to the saved budgeting data.
640	*/
641	goto out_unlock;
642
643	pr_err("\tfreeable_cnt %d, calc_idx_sz %lld, idx_gc_cnt %d\n",
644	c->freeable_cnt, c->calc_idx_sz, c->idx_gc_cnt);
645	pr_err("\tdirty_pg_cnt %ld, dirty_zn_cnt %ld, clean_zn_cnt %ld\n",
646	atomic_long_read(&c->dirty_pg_cnt),
647	atomic_long_read(&c->dirty_zn_cnt),
648	atomic_long_read(&c->clean_zn_cnt));
649	pr_err("\tgc_lnum %d, ihead_lnum %d\n", c->gc_lnum, c->ihead_lnum);
650
651	/* If we are in R/O mode, journal heads do not exist */
652	if (c->jheads)
653	for (i = 0; i < c->jhead_cnt; i++)
654	pr_err("\tjhead %s\t LEB %d\n",
655	dbg_jhead(c->jheads[i].wbuf.jhead),
656	c->jheads[i].wbuf.lnum);
657	for (rb = rb_first(&c->buds); rb; rb = rb_next(rb)) {
658	bud = rb_entry(rb, struct ubifs_bud, rb);
659	pr_err("\tbud LEB %d\n", bud->lnum);
660	}
661	list_for_each_entry(bud, &c->old_buds, list)
662	pr_err("\told bud LEB %d\n", bud->lnum);
663	list_for_each_entry(idx_gc, &c->idx_gc, list)
664	pr_err("\tGC'ed idx LEB %d unmap %d\n",
665	idx_gc->lnum, idx_gc->unmap);
666	pr_err("\tcommit state %d\n", c->cmt_state);
667
668	/* Print budgeting predictions */
669	available = ubifs_calc_available(c, min_idx_lebs: c->bi.min_idx_lebs);
670	outstanding = c->bi.data_growth + c->bi.dd_growth;
671	free = ubifs_get_free_space_nolock(c);
672	pr_err("Budgeting predictions:\n");
673	pr_err("\tavailable: %lld, outstanding %lld, free %lld\n",
674	available, outstanding, free);
675	out_unlock:
676	spin_unlock(lock: &dbg_lock);
677	spin_unlock(lock: &c->space_lock);
678	}
679
680	void ubifs_dump_lprop(const struct ubifs_info *c, const struct ubifs_lprops *lp)
681	{
682	int i, spc, dark = 0, dead = 0;
683	struct rb_node *rb;
684	struct ubifs_bud *bud;
685
686	spc = lp->free + lp->dirty;
687	if (spc < c->dead_wm)
688	dead = spc;
689	else
690	dark = ubifs_calc_dark(c, spc);
691
692	if (lp->flags & LPROPS_INDEX)
693	pr_err("LEB %-7d free %-8d dirty %-8d used %-8d free + dirty %-8d flags %#x (",
694	lp->lnum, lp->free, lp->dirty, c->leb_size - spc, spc,
695	lp->flags);
696	else
697	pr_err("LEB %-7d free %-8d dirty %-8d used %-8d free + dirty %-8d dark %-4d dead %-4d nodes fit %-3d flags %#-4x (",
698	lp->lnum, lp->free, lp->dirty, c->leb_size - spc, spc,
699	dark, dead, (int)(spc / UBIFS_MAX_NODE_SZ), lp->flags);
700
701	if (lp->flags & LPROPS_TAKEN) {
702	if (lp->flags & LPROPS_INDEX)
703	pr_cont("index, taken");
704	else
705	pr_cont("taken");
706	} else {
707	const char *s;
708
709	if (lp->flags & LPROPS_INDEX) {
710	switch (lp->flags & LPROPS_CAT_MASK) {
711	case LPROPS_DIRTY_IDX:
712	s = "dirty index";
713	break;
714	case LPROPS_FRDI_IDX:
715	s = "freeable index";
716	break;
717	default:
718	s = "index";
719	}
720	} else {
721	switch (lp->flags & LPROPS_CAT_MASK) {
722	case LPROPS_UNCAT:
723	s = "not categorized";
724	break;
725	case LPROPS_DIRTY:
726	s = "dirty";
727	break;
728	case LPROPS_FREE:
729	s = "free";
730	break;
731	case LPROPS_EMPTY:
732	s = "empty";
733	break;
734	case LPROPS_FREEABLE:
735	s = "freeable";
736	break;
737	default:
738	s = NULL;
739	break;
740	}
741	}
742	pr_cont("%s", s);
743	}
744
745	for (rb = rb_first((struct rb_root *)&c->buds); rb; rb = rb_next(rb)) {
746	bud = rb_entry(rb, struct ubifs_bud, rb);
747	if (bud->lnum == lp->lnum) {
748	int head = 0;
749	for (i = 0; i < c->jhead_cnt; i++) {
750	/*
751	* Note, if we are in R/O mode or in the middle
752	* of mounting/re-mounting, the write-buffers do
753	* not exist.
754	*/
755	if (c->jheads &&
756	lp->lnum == c->jheads[i].wbuf.lnum) {
757	pr_cont(", jhead %s", dbg_jhead(i));
758	head = 1;
759	}
760	}
761	if (!head)
762	pr_cont(", bud of jhead %s",
763	dbg_jhead(bud->jhead));
764	}
765	}
766	if (lp->lnum == c->gc_lnum)
767	pr_cont(", GC LEB");
768	pr_cont(")\n");
769	}
770
771	void ubifs_dump_lprops(struct ubifs_info *c)
772	{
773	int lnum, err;
774	struct ubifs_lprops lp;
775	struct ubifs_lp_stats lst;
776
777	pr_err("(pid %d) start dumping LEB properties\n", current->pid);
778	ubifs_get_lp_stats(c, lst: &lst);
779	ubifs_dump_lstats(lst: &lst);
780
781	for (lnum = c->main_first; lnum < c->leb_cnt; lnum++) {
782	err = ubifs_read_one_lp(c, lnum, lp: &lp);
783	if (err) {
784	ubifs_err(c, fmt: "cannot read lprops for LEB %d", lnum);
785	continue;
786	}
787
788	ubifs_dump_lprop(c, lp: &lp);
789	}
790	pr_err("(pid %d) finish dumping LEB properties\n", current->pid);
791	}
792
793	void ubifs_dump_lpt_info(struct ubifs_info *c)
794	{
795	int i;
796
797	spin_lock(lock: &dbg_lock);
798	pr_err("(pid %d) dumping LPT information\n", current->pid);
799	pr_err("\tlpt_sz: %lld\n", c->lpt_sz);
800	pr_err("\tpnode_sz: %d\n", c->pnode_sz);
801	pr_err("\tnnode_sz: %d\n", c->nnode_sz);
802	pr_err("\tltab_sz: %d\n", c->ltab_sz);
803	pr_err("\tlsave_sz: %d\n", c->lsave_sz);
804	pr_err("\tbig_lpt: %u\n", c->big_lpt);
805	pr_err("\tlpt_hght: %d\n", c->lpt_hght);
806	pr_err("\tpnode_cnt: %d\n", c->pnode_cnt);
807	pr_err("\tnnode_cnt: %d\n", c->nnode_cnt);
808	pr_err("\tdirty_pn_cnt: %d\n", c->dirty_pn_cnt);
809	pr_err("\tdirty_nn_cnt: %d\n", c->dirty_nn_cnt);
810	pr_err("\tlsave_cnt: %d\n", c->lsave_cnt);
811	pr_err("\tspace_bits: %d\n", c->space_bits);
812	pr_err("\tlpt_lnum_bits: %d\n", c->lpt_lnum_bits);
813	pr_err("\tlpt_offs_bits: %d\n", c->lpt_offs_bits);
814	pr_err("\tlpt_spc_bits: %d\n", c->lpt_spc_bits);
815	pr_err("\tpcnt_bits: %d\n", c->pcnt_bits);
816	pr_err("\tlnum_bits: %d\n", c->lnum_bits);
817	pr_err("\tLPT root is at %d:%d\n", c->lpt_lnum, c->lpt_offs);
818	pr_err("\tLPT head is at %d:%d\n",
819	c->nhead_lnum, c->nhead_offs);
820	pr_err("\tLPT ltab is at %d:%d\n", c->ltab_lnum, c->ltab_offs);
821	if (c->big_lpt)
822	pr_err("\tLPT lsave is at %d:%d\n",
823	c->lsave_lnum, c->lsave_offs);
824	for (i = 0; i < c->lpt_lebs; i++)
825	pr_err("\tLPT LEB %d free %d dirty %d tgc %d cmt %d\n",
826	i + c->lpt_first, c->ltab[i].free, c->ltab[i].dirty,
827	c->ltab[i].tgc, c->ltab[i].cmt);
828	spin_unlock(lock: &dbg_lock);
829	}
830
831	void ubifs_dump_leb(const struct ubifs_info *c, int lnum)
832	{
833	struct ubifs_scan_leb *sleb;
834	struct ubifs_scan_node *snod;
835	void *buf;
836
837	pr_err("(pid %d) start dumping LEB %d\n", current->pid, lnum);
838
839	buf = __vmalloc(size: c->leb_size, GFP_NOFS);
840	if (!buf) {
841	ubifs_err(c, fmt: "cannot allocate memory for dumping LEB %d", lnum);
842	return;
843	}
844
845	sleb = ubifs_scan(c, lnum, offs: 0, sbuf: buf, quiet: 0);
846	if (IS_ERR(ptr: sleb)) {
847	ubifs_err(c, fmt: "scan error %d", (int)PTR_ERR(ptr: sleb));
848	goto out;
849	}
850
851	pr_err("LEB %d has %d nodes ending at %d\n", lnum,
852	sleb->nodes_cnt, sleb->endpt);
853
854	list_for_each_entry(snod, &sleb->nodes, list) {
855	cond_resched();
856	pr_err("Dumping node at LEB %d:%d len %d\n", lnum,
857	snod->offs, snod->len);
858	ubifs_dump_node(c, node: snod->node, node_len: c->leb_size - snod->offs);
859	}
860
861	pr_err("(pid %d) finish dumping LEB %d\n", current->pid, lnum);
862	ubifs_scan_destroy(sleb);
863
864	out:
865	vfree(addr: buf);
866	return;
867	}
868
869	void ubifs_dump_znode(const struct ubifs_info *c,
870	const struct ubifs_znode *znode)
871	{
872	int n;
873	const struct ubifs_zbranch *zbr;
874	char key_buf[DBG_KEY_BUF_LEN];
875
876	spin_lock(lock: &dbg_lock);
877	if (znode->parent)
878	zbr = &znode->parent->zbranch[znode->iip];
879	else
880	zbr = &c->zroot;
881
882	pr_err("znode %p, LEB %d:%d len %d parent %p iip %d level %d child_cnt %d flags %lx\n",
883	znode, zbr->lnum, zbr->offs, zbr->len, znode->parent, znode->iip,
884	znode->level, znode->child_cnt, znode->flags);
885
886	if (znode->child_cnt <= 0 || znode->child_cnt > c->fanout) {
887	spin_unlock(lock: &dbg_lock);
888	return;
889	}
890
891	pr_err("zbranches:\n");
892	for (n = 0; n < znode->child_cnt; n++) {
893	zbr = &znode->zbranch[n];
894	if (znode->level > 0)
895	pr_err("\t%d: znode %p LEB %d:%d len %d key %s\n",
896	n, zbr->znode, zbr->lnum, zbr->offs, zbr->len,
897	dbg_snprintf_key(c, &zbr->key, key_buf,
898	DBG_KEY_BUF_LEN));
899	else
900	pr_err("\t%d: LNC %p LEB %d:%d len %d key %s\n",
901	n, zbr->znode, zbr->lnum, zbr->offs, zbr->len,
902	dbg_snprintf_key(c, &zbr->key, key_buf,
903	DBG_KEY_BUF_LEN));
904	}
905	spin_unlock(lock: &dbg_lock);
906	}
907
908	void ubifs_dump_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap, int cat)
909	{
910	int i;
911
912	pr_err("(pid %d) start dumping heap cat %d (%d elements)\n",
913	current->pid, cat, heap->cnt);
914	for (i = 0; i < heap->cnt; i++) {
915	struct ubifs_lprops *lprops = heap->arr[i];
916
917	pr_err("\t%d. LEB %d hpos %d free %d dirty %d flags %d\n",
918	i, lprops->lnum, lprops->hpos, lprops->free,
919	lprops->dirty, lprops->flags);
920	}
921	pr_err("(pid %d) finish dumping heap\n", current->pid);
922	}
923
924	void ubifs_dump_pnode(struct ubifs_info *c, struct ubifs_pnode *pnode,
925	struct ubifs_nnode *parent, int iip)
926	{
927	int i;
928
929	pr_err("(pid %d) dumping pnode:\n", current->pid);
930	pr_err("\taddress %zx parent %zx cnext %zx\n",
931	(size_t)pnode, (size_t)parent, (size_t)pnode->cnext);
932	pr_err("\tflags %lu iip %d level %d num %d\n",
933	pnode->flags, iip, pnode->level, pnode->num);
934	for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
935	struct ubifs_lprops *lp = &pnode->lprops[i];
936
937	pr_err("\t%d: free %d dirty %d flags %d lnum %d\n",
938	i, lp->free, lp->dirty, lp->flags, lp->lnum);
939	}
940	}
941
942	void ubifs_dump_tnc(struct ubifs_info *c)
943	{
944	struct ubifs_znode *znode;
945	int level;
946
947	pr_err("\n");
948	pr_err("(pid %d) start dumping TNC tree\n", current->pid);
949	znode = ubifs_tnc_levelorder_next(c, zr: c->zroot.znode, NULL);
950	level = znode->level;
951	pr_err("== Level %d ==\n", level);
952	while (znode) {
953	if (level != znode->level) {
954	level = znode->level;
955	pr_err("== Level %d ==\n", level);
956	}
957	ubifs_dump_znode(c, znode);
958	znode = ubifs_tnc_levelorder_next(c, zr: c->zroot.znode, znode);
959	}
960	pr_err("(pid %d) finish dumping TNC tree\n", current->pid);
961	}
962
963	static int dump_znode(struct ubifs_info *c, struct ubifs_znode *znode,
964	void *priv)
965	{
966	ubifs_dump_znode(c, znode);
967	return 0;
968	}
969
970	/**
971	* ubifs_dump_index - dump the on-flash index.
972	* @c: UBIFS file-system description object
973	*
974	* This function dumps whole UBIFS indexing B-tree, unlike 'ubifs_dump_tnc()'
975	* which dumps only in-memory znodes and does not read znodes which from flash.
976	*/
977	void ubifs_dump_index(struct ubifs_info *c)
978	{
979	dbg_walk_index(c, NULL, znode_cb: dump_znode, NULL);
980	}
981
982	/**
983	* dbg_save_space_info - save information about flash space.
984	* @c: UBIFS file-system description object
985	*
986	* This function saves information about UBIFS free space, dirty space, etc, in
987	* order to check it later.
988	*/
989	void dbg_save_space_info(struct ubifs_info *c)
990	{
991	struct ubifs_debug_info *d = c->dbg;
992	int freeable_cnt;
993
994	spin_lock(lock: &c->space_lock);
995	memcpy(&d->saved_lst, &c->lst, sizeof(struct ubifs_lp_stats));
996	memcpy(&d->saved_bi, &c->bi, sizeof(struct ubifs_budg_info));
997	d->saved_idx_gc_cnt = c->idx_gc_cnt;
998
999	/*
1000	* We use a dirty hack here and zero out @c->freeable_cnt, because it
1001	* affects the free space calculations, and UBIFS might not know about
1002	* all freeable eraseblocks. Indeed, we know about freeable eraseblocks
1003	* only when we read their lprops, and we do this only lazily, upon the
1004	* need. So at any given point of time @c->freeable_cnt might be not
1005	* exactly accurate.
1006	*
1007	* Just one example about the issue we hit when we did not zero
1008	* @c->freeable_cnt.
1009	* 1. The file-system is mounted R/O, c->freeable_cnt is %0. We save the
1010	* amount of free space in @d->saved_free
1011	* 2. We re-mount R/W, which makes UBIFS to read the "lsave"
1012	* information from flash, where we cache LEBs from various
1013	* categories ('ubifs_remount_fs()' -> 'ubifs_lpt_init()'
1014	* -> 'lpt_init_wr()' -> 'read_lsave()' -> 'ubifs_lpt_lookup()'
1015	* -> 'ubifs_get_pnode()' -> 'update_cats()'
1016	* -> 'ubifs_add_to_cat()').
1017	* 3. Lsave contains a freeable eraseblock, and @c->freeable_cnt
1018	* becomes %1.
1019	* 4. We calculate the amount of free space when the re-mount is
1020	* finished in 'dbg_check_space_info()' and it does not match
1021	* @d->saved_free.
1022	*/
1023	freeable_cnt = c->freeable_cnt;
1024	c->freeable_cnt = 0;
1025	d->saved_free = ubifs_get_free_space_nolock(c);
1026	c->freeable_cnt = freeable_cnt;
1027	spin_unlock(lock: &c->space_lock);
1028	}
1029
1030	/**
1031	* dbg_check_space_info - check flash space information.
1032	* @c: UBIFS file-system description object
1033	*
1034	* This function compares current flash space information with the information
1035	* which was saved when the 'dbg_save_space_info()' function was called.
1036	* Returns zero if the information has not changed, and %-EINVAL if it has
1037	* changed.
1038	*/
1039	int dbg_check_space_info(struct ubifs_info *c)
1040	{
1041	struct ubifs_debug_info *d = c->dbg;
1042	struct ubifs_lp_stats lst;
1043	long long free;
1044	int freeable_cnt;
1045
1046	spin_lock(lock: &c->space_lock);
1047	freeable_cnt = c->freeable_cnt;
1048	c->freeable_cnt = 0;
1049	free = ubifs_get_free_space_nolock(c);
1050	c->freeable_cnt = freeable_cnt;
1051	spin_unlock(lock: &c->space_lock);
1052
1053	if (free != d->saved_free) {
1054	ubifs_err(c, fmt: "free space changed from %lld to %lld",
1055	d->saved_free, free);
1056	goto out;
1057	}
1058
1059	return 0;
1060
1061	out:
1062	ubifs_msg(c, fmt: "saved lprops statistics dump");
1063	ubifs_dump_lstats(lst: &d->saved_lst);
1064	ubifs_msg(c, fmt: "saved budgeting info dump");
1065	ubifs_dump_budg(c, bi: &d->saved_bi);
1066	ubifs_msg(c, fmt: "saved idx_gc_cnt %d", d->saved_idx_gc_cnt);
1067	ubifs_msg(c, fmt: "current lprops statistics dump");
1068	ubifs_get_lp_stats(c, lst: &lst);
1069	ubifs_dump_lstats(lst: &lst);
1070	ubifs_msg(c, fmt: "current budgeting info dump");
1071	ubifs_dump_budg(c, bi: &c->bi);
1072	dump_stack();
1073	return -EINVAL;
1074	}
1075
1076	/**
1077	* dbg_check_synced_i_size - check synchronized inode size.
1078	* @c: UBIFS file-system description object
1079	* @inode: inode to check
1080	*
1081	* If inode is clean, synchronized inode size has to be equivalent to current
1082	* inode size. This function has to be called only for locked inodes (@i_mutex
1083	* has to be locked). Returns %0 if synchronized inode size if correct, and
1084	* %-EINVAL if not.
1085	*/
1086	int dbg_check_synced_i_size(const struct ubifs_info *c, struct inode *inode)
1087	{
1088	int err = 0;
1089	struct ubifs_inode *ui = ubifs_inode(inode);
1090
1091	if (!dbg_is_chk_gen(c))
1092	return 0;
1093	if (!S_ISREG(inode->i_mode))
1094	return 0;
1095
1096	mutex_lock(&ui->ui_mutex);
1097	spin_lock(lock: &ui->ui_lock);
1098	if (ui->ui_size != ui->synced_i_size && !ui->dirty) {
1099	ubifs_err(c, fmt: "ui_size is %lld, synced_i_size is %lld, but inode is clean",
1100	ui->ui_size, ui->synced_i_size);
1101	ubifs_err(c, fmt: "i_ino %lu, i_mode %#x, i_size %lld", inode->i_ino,
1102	inode->i_mode, i_size_read(inode));
1103	dump_stack();
1104	err = -EINVAL;
1105	}
1106	spin_unlock(lock: &ui->ui_lock);
1107	mutex_unlock(lock: &ui->ui_mutex);
1108	return err;
1109	}
1110
1111	/*
1112	* dbg_check_dir - check directory inode size and link count.
1113	* @c: UBIFS file-system description object
1114	* @dir: the directory to calculate size for
1115	* @size: the result is returned here
1116	*
1117	* This function makes sure that directory size and link count are correct.
1118	* Returns zero in case of success and a negative error code in case of
1119	* failure.
1120	*
1121	* Note, it is good idea to make sure the @dir->i_mutex is locked before
1122	* calling this function.
1123	*/
1124	int dbg_check_dir(struct ubifs_info *c, const struct inode *dir)
1125	{
1126	unsigned int nlink = 2;
1127	union ubifs_key key;
1128	struct ubifs_dent_node *dent, *pdent = NULL;
1129	struct fscrypt_name nm = {0};
1130	loff_t size = UBIFS_INO_NODE_SZ;
1131
1132	if (!dbg_is_chk_gen(c))
1133	return 0;
1134
1135	if (!S_ISDIR(dir->i_mode))
1136	return 0;
1137
1138	lowest_dent_key(c, key: &key, inum: dir->i_ino);
1139	while (1) {
1140	int err;
1141
1142	dent = ubifs_tnc_next_ent(c, key: &key, nm: &nm);
1143	if (IS_ERR(ptr: dent)) {
1144	err = PTR_ERR(ptr: dent);
1145	if (err == -ENOENT)
1146	break;
1147	kfree(objp: pdent);
1148	return err;
1149	}
1150
1151	fname_name(&nm) = dent->name;
1152	fname_len(&nm) = le16_to_cpu(dent->nlen);
1153	size += CALC_DENT_SIZE(fname_len(&nm));
1154	if (dent->type == UBIFS_ITYPE_DIR)
1155	nlink += 1;
1156	kfree(objp: pdent);
1157	pdent = dent;
1158	key_read(c, from: &dent->key, to: &key);
1159	}
1160	kfree(objp: pdent);
1161
1162	if (i_size_read(inode: dir) != size) {
1163	ubifs_err(c, fmt: "directory inode %lu has size %llu, but calculated size is %llu",
1164	dir->i_ino, (unsigned long long)i_size_read(inode: dir),
1165	(unsigned long long)size);
1166	ubifs_dump_inode(c, inode: dir);
1167	dump_stack();
1168	return -EINVAL;
1169	}
1170	if (dir->i_nlink != nlink) {
1171	ubifs_err(c, fmt: "directory inode %lu has nlink %u, but calculated nlink is %u",
1172	dir->i_ino, dir->i_nlink, nlink);
1173	ubifs_dump_inode(c, inode: dir);
1174	dump_stack();
1175	return -EINVAL;
1176	}
1177
1178	return 0;
1179	}
1180
1181	/**
1182	* dbg_check_key_order - make sure that colliding keys are properly ordered.
1183	* @c: UBIFS file-system description object
1184	* @zbr1: first zbranch
1185	* @zbr2: following zbranch
1186	*
1187	* In UBIFS indexing B-tree colliding keys has to be sorted in binary order of
1188	* names of the direntries/xentries which are referred by the keys. This
1189	* function reads direntries/xentries referred by @zbr1 and @zbr2 and makes
1190	* sure the name of direntry/xentry referred by @zbr1 is less than
1191	* direntry/xentry referred by @zbr2. Returns zero if this is true, %1 if not,
1192	* and a negative error code in case of failure.
1193	*/
1194	static int dbg_check_key_order(struct ubifs_info *c, struct ubifs_zbranch *zbr1,
1195	struct ubifs_zbranch *zbr2)
1196	{
1197	int err, nlen1, nlen2, cmp;
1198	struct ubifs_dent_node *dent1, *dent2;
1199	union ubifs_key key;
1200	char key_buf[DBG_KEY_BUF_LEN];
1201
1202	ubifs_assert(c, !keys_cmp(c, &zbr1->key, &zbr2->key));
1203	dent1 = kmalloc(UBIFS_MAX_DENT_NODE_SZ, GFP_NOFS);
1204	if (!dent1)
1205	return -ENOMEM;
1206	dent2 = kmalloc(UBIFS_MAX_DENT_NODE_SZ, GFP_NOFS);
1207	if (!dent2) {
1208	err = -ENOMEM;
1209	goto out_free;
1210	}
1211
1212	err = ubifs_tnc_read_node(c, zbr: zbr1, node: dent1);
1213	if (err)
1214	goto out_free;
1215	err = ubifs_validate_entry(c, dent: dent1);
1216	if (err)
1217	goto out_free;
1218
1219	err = ubifs_tnc_read_node(c, zbr: zbr2, node: dent2);
1220	if (err)
1221	goto out_free;
1222	err = ubifs_validate_entry(c, dent: dent2);
1223	if (err)
1224	goto out_free;
1225
1226	/* Make sure node keys are the same as in zbranch */
1227	err = 1;
1228	key_read(c, from: &dent1->key, to: &key);
1229	if (keys_cmp(c, key1: &zbr1->key, key2: &key)) {
1230	ubifs_err(c, fmt: "1st entry at %d:%d has key %s", zbr1->lnum,
1231	zbr1->offs, dbg_snprintf_key(c, key: &key, buffer: key_buf,
1232	DBG_KEY_BUF_LEN));
1233	ubifs_err(c, fmt: "but it should have key %s according to tnc",
1234	dbg_snprintf_key(c, key: &zbr1->key, buffer: key_buf,
1235	DBG_KEY_BUF_LEN));
1236	ubifs_dump_node(c, node: dent1, UBIFS_MAX_DENT_NODE_SZ);
1237	goto out_free;
1238	}
1239
1240	key_read(c, from: &dent2->key, to: &key);
1241	if (keys_cmp(c, key1: &zbr2->key, key2: &key)) {
1242	ubifs_err(c, fmt: "2nd entry at %d:%d has key %s", zbr1->lnum,
1243	zbr1->offs, dbg_snprintf_key(c, key: &key, buffer: key_buf,
1244	DBG_KEY_BUF_LEN));
1245	ubifs_err(c, fmt: "but it should have key %s according to tnc",
1246	dbg_snprintf_key(c, key: &zbr2->key, buffer: key_buf,
1247	DBG_KEY_BUF_LEN));
1248	ubifs_dump_node(c, node: dent2, UBIFS_MAX_DENT_NODE_SZ);
1249	goto out_free;
1250	}
1251
1252	nlen1 = le16_to_cpu(dent1->nlen);
1253	nlen2 = le16_to_cpu(dent2->nlen);
1254
1255	cmp = memcmp(p: dent1->name, q: dent2->name, min_t(int, nlen1, nlen2));
1256	if (cmp < 0 || (cmp == 0 && nlen1 < nlen2)) {
1257	err = 0;
1258	goto out_free;
1259	}
1260	if (cmp == 0 && nlen1 == nlen2)
1261	ubifs_err(c, fmt: "2 xent/dent nodes with the same name");
1262	else
1263	ubifs_err(c, fmt: "bad order of colliding key %s",
1264	dbg_snprintf_key(c, key: &key, buffer: key_buf, DBG_KEY_BUF_LEN));
1265
1266	ubifs_msg(c, fmt: "first node at %d:%d\n", zbr1->lnum, zbr1->offs);
1267	ubifs_dump_node(c, node: dent1, UBIFS_MAX_DENT_NODE_SZ);
1268	ubifs_msg(c, fmt: "second node at %d:%d\n", zbr2->lnum, zbr2->offs);
1269	ubifs_dump_node(c, node: dent2, UBIFS_MAX_DENT_NODE_SZ);
1270
1271	out_free:
1272	kfree(objp: dent2);
1273	kfree(objp: dent1);
1274	return err;
1275	}
1276
1277	/**
1278	* dbg_check_znode - check if znode is all right.
1279	* @c: UBIFS file-system description object
1280	* @zbr: zbranch which points to this znode
1281	*
1282	* This function makes sure that znode referred to by @zbr is all right.
1283	* Returns zero if it is, and %-EINVAL if it is not.
1284	*/
1285	static int dbg_check_znode(struct ubifs_info *c, struct ubifs_zbranch *zbr)
1286	{
1287	struct ubifs_znode *znode = zbr->znode;
1288	struct ubifs_znode *zp = znode->parent;
1289	int n, err, cmp;
1290
1291	if (znode->child_cnt <= 0 || znode->child_cnt > c->fanout) {
1292	err = 1;
1293	goto out;
1294	}
1295	if (znode->level < 0) {
1296	err = 2;
1297	goto out;
1298	}
1299	if (znode->iip < 0 || znode->iip >= c->fanout) {
1300	err = 3;
1301	goto out;
1302	}
1303
1304	if (zbr->len == 0)
1305	/* Only dirty zbranch may have no on-flash nodes */
1306	if (!ubifs_zn_dirty(znode)) {
1307	err = 4;
1308	goto out;
1309	}
1310
1311	if (ubifs_zn_dirty(znode)) {
1312	/*
1313	* If znode is dirty, its parent has to be dirty as well. The
1314	* order of the operation is important, so we have to have
1315	* memory barriers.
1316	*/
1317	smp_mb();
1318	if (zp && !ubifs_zn_dirty(znode: zp)) {
1319	/*
1320	* The dirty flag is atomic and is cleared outside the
1321	* TNC mutex, so znode's dirty flag may now have
1322	* been cleared. The child is always cleared before the
1323	* parent, so we just need to check again.
1324	*/
1325	smp_mb();
1326	if (ubifs_zn_dirty(znode)) {
1327	err = 5;
1328	goto out;
1329	}
1330	}
1331	}
1332
1333	if (zp) {
1334	const union ubifs_key *min, *max;
1335
1336	if (znode->level != zp->level - 1) {
1337	err = 6;
1338	goto out;
1339	}
1340
1341	/* Make sure the 'parent' pointer in our znode is correct */
1342	err = ubifs_search_zbranch(c, znode: zp, key: &zbr->key, n: &n);
1343	if (!err) {
1344	/* This zbranch does not exist in the parent */
1345	err = 7;
1346	goto out;
1347	}
1348
1349	if (znode->iip >= zp->child_cnt) {
1350	err = 8;
1351	goto out;
1352	}
1353
1354	if (znode->iip != n) {
1355	/* This may happen only in case of collisions */
1356	if (keys_cmp(c, key1: &zp->zbranch[n].key,
1357	key2: &zp->zbranch[znode->iip].key)) {
1358	err = 9;
1359	goto out;
1360	}
1361	n = znode->iip;
1362	}
1363
1364	/*
1365	* Make sure that the first key in our znode is greater than or
1366	* equal to the key in the pointing zbranch.
1367	*/
1368	min = &zbr->key;
1369	cmp = keys_cmp(c, key1: min, key2: &znode->zbranch[0].key);
1370	if (cmp == 1) {
1371	err = 10;
1372	goto out;
1373	}
1374
1375	if (n + 1 < zp->child_cnt) {
1376	max = &zp->zbranch[n + 1].key;
1377
1378	/*
1379	* Make sure the last key in our znode is less or
1380	* equivalent than the key in the zbranch which goes
1381	* after our pointing zbranch.
1382	*/
1383	cmp = keys_cmp(c, key1: max,
1384	key2: &znode->zbranch[znode->child_cnt - 1].key);
1385	if (cmp == -1) {
1386	err = 11;
1387	goto out;
1388	}
1389	}
1390	} else {
1391	/* This may only be root znode */
1392	if (zbr != &c->zroot) {
1393	err = 12;
1394	goto out;
1395	}
1396	}
1397
1398	/*
1399	* Make sure that next key is greater or equivalent then the previous
1400	* one.
1401	*/
1402	for (n = 1; n < znode->child_cnt; n++) {
1403	cmp = keys_cmp(c, key1: &znode->zbranch[n - 1].key,
1404	key2: &znode->zbranch[n].key);
1405	if (cmp > 0) {
1406	err = 13;
1407	goto out;
1408	}
1409	if (cmp == 0) {
1410	/* This can only be keys with colliding hash */
1411	if (!is_hash_key(c, key: &znode->zbranch[n].key)) {
1412	err = 14;
1413	goto out;
1414	}
1415
1416	if (znode->level != 0 || c->replaying)
1417	continue;
1418
1419	/*
1420	* Colliding keys should follow binary order of
1421	* corresponding xentry/dentry names.
1422	*/
1423	err = dbg_check_key_order(c, zbr1: &znode->zbranch[n - 1],
1424	zbr2: &znode->zbranch[n]);
1425	if (err < 0)
1426	return err;
1427	if (err) {
1428	err = 15;
1429	goto out;
1430	}
1431	}
1432	}
1433
1434	for (n = 0; n < znode->child_cnt; n++) {
1435	if (!znode->zbranch[n].znode &&
1436	(znode->zbranch[n].lnum == 0 ||
1437	znode->zbranch[n].len == 0)) {
1438	err = 16;
1439	goto out;
1440	}
1441
1442	if (znode->zbranch[n].lnum != 0 &&
1443	znode->zbranch[n].len == 0) {
1444	err = 17;
1445	goto out;
1446	}
1447
1448	if (znode->zbranch[n].lnum == 0 &&
1449	znode->zbranch[n].len != 0) {
1450	err = 18;
1451	goto out;
1452	}
1453
1454	if (znode->zbranch[n].lnum == 0 &&
1455	znode->zbranch[n].offs != 0) {
1456	err = 19;
1457	goto out;
1458	}
1459
1460	if (znode->level != 0 && znode->zbranch[n].znode)
1461	if (znode->zbranch[n].znode->parent != znode) {
1462	err = 20;
1463	goto out;
1464	}
1465	}
1466
1467	return 0;
1468
1469	out:
1470	ubifs_err(c, fmt: "failed, error %d", err);
1471	ubifs_msg(c, fmt: "dump of the znode");
1472	ubifs_dump_znode(c, znode);
1473	if (zp) {
1474	ubifs_msg(c, fmt: "dump of the parent znode");
1475	ubifs_dump_znode(c, znode: zp);
1476	}
1477	dump_stack();
1478	return -EINVAL;
1479	}
1480
1481	/**
1482	* dbg_check_tnc - check TNC tree.
1483	* @c: UBIFS file-system description object
1484	* @extra: do extra checks that are possible at start commit
1485	*
1486	* This function traverses whole TNC tree and checks every znode. Returns zero
1487	* if everything is all right and %-EINVAL if something is wrong with TNC.
1488	*/
1489	int dbg_check_tnc(struct ubifs_info *c, int extra)
1490	{
1491	struct ubifs_znode *znode;
1492	long clean_cnt = 0, dirty_cnt = 0;
1493	int err, last;
1494
1495	if (!dbg_is_chk_index(c))
1496	return 0;
1497
1498	ubifs_assert(c, mutex_is_locked(&c->tnc_mutex));
1499	if (!c->zroot.znode)
1500	return 0;
1501
1502	znode = ubifs_tnc_postorder_first(znode: c->zroot.znode);
1503	while (1) {
1504	struct ubifs_znode *prev;
1505	struct ubifs_zbranch *zbr;
1506
1507	if (!znode->parent)
1508	zbr = &c->zroot;
1509	else
1510	zbr = &znode->parent->zbranch[znode->iip];
1511
1512	err = dbg_check_znode(c, zbr);
1513	if (err)
1514	return err;
1515
1516	if (extra) {
1517	if (ubifs_zn_dirty(znode))
1518	dirty_cnt += 1;
1519	else
1520	clean_cnt += 1;
1521	}
1522
1523	prev = znode;
1524	znode = ubifs_tnc_postorder_next(c, znode);
1525	if (!znode)
1526	break;
1527
1528	/*
1529	* If the last key of this znode is equivalent to the first key
1530	* of the next znode (collision), then check order of the keys.
1531	*/
1532	last = prev->child_cnt - 1;
1533	if (prev->level == 0 && znode->level == 0 && !c->replaying &&
1534	!keys_cmp(c, key1: &prev->zbranch[last].key,
1535	key2: &znode->zbranch[0].key)) {
1536	err = dbg_check_key_order(c, zbr1: &prev->zbranch[last],
1537	zbr2: &znode->zbranch[0]);
1538	if (err < 0)
1539	return err;
1540	if (err) {
1541	ubifs_msg(c, fmt: "first znode");
1542	ubifs_dump_znode(c, znode: prev);
1543	ubifs_msg(c, fmt: "second znode");
1544	ubifs_dump_znode(c, znode);
1545	return -EINVAL;
1546	}
1547	}
1548	}
1549
1550	if (extra) {
1551	if (clean_cnt != atomic_long_read(v: &c->clean_zn_cnt)) {
1552	ubifs_err(c, fmt: "incorrect clean_zn_cnt %ld, calculated %ld",
1553	atomic_long_read(v: &c->clean_zn_cnt),
1554	clean_cnt);
1555	return -EINVAL;
1556	}
1557	if (dirty_cnt != atomic_long_read(v: &c->dirty_zn_cnt)) {
1558	ubifs_err(c, fmt: "incorrect dirty_zn_cnt %ld, calculated %ld",
1559	atomic_long_read(v: &c->dirty_zn_cnt),
1560	dirty_cnt);
1561	return -EINVAL;
1562	}
1563	}
1564
1565	return 0;
1566	}
1567
1568	/**
1569	* dbg_walk_index - walk the on-flash index.
1570	* @c: UBIFS file-system description object
1571	* @leaf_cb: called for each leaf node
1572	* @znode_cb: called for each indexing node
1573	* @priv: private data which is passed to callbacks
1574	*
1575	* This function walks the UBIFS index and calls the @leaf_cb for each leaf
1576	* node and @znode_cb for each indexing node. Returns zero in case of success
1577	* and a negative error code in case of failure.
1578	*
1579	* It would be better if this function removed every znode it pulled to into
1580	* the TNC, so that the behavior more closely matched the non-debugging
1581	* behavior.
1582	*/
1583	int dbg_walk_index(struct ubifs_info *c, dbg_leaf_callback leaf_cb,
1584	dbg_znode_callback znode_cb, void *priv)
1585	{
1586	int err;
1587	struct ubifs_zbranch *zbr;
1588	struct ubifs_znode *znode, *child;
1589
1590	mutex_lock(&c->tnc_mutex);
1591	/* If the root indexing node is not in TNC - pull it */
1592	if (!c->zroot.znode) {
1593	c->zroot.znode = ubifs_load_znode(c, zbr: &c->zroot, NULL, iip: 0);
1594	if (IS_ERR(ptr: c->zroot.znode)) {
1595	err = PTR_ERR(ptr: c->zroot.znode);
1596	c->zroot.znode = NULL;
1597	goto out_unlock;
1598	}
1599	}
1600
1601	/*
1602	* We are going to traverse the indexing tree in the postorder manner.
1603	* Go down and find the leftmost indexing node where we are going to
1604	* start from.
1605	*/
1606	znode = c->zroot.znode;
1607	while (znode->level > 0) {
1608	zbr = &znode->zbranch[0];
1609	child = zbr->znode;
1610	if (!child) {
1611	child = ubifs_load_znode(c, zbr, parent: znode, iip: 0);
1612	if (IS_ERR(ptr: child)) {
1613	err = PTR_ERR(ptr: child);
1614	goto out_unlock;
1615	}
1616	}
1617
1618	znode = child;
1619	}
1620
1621	/* Iterate over all indexing nodes */
1622	while (1) {
1623	int idx;
1624
1625	cond_resched();
1626
1627	if (znode_cb) {
1628	err = znode_cb(c, znode, priv);
1629	if (err) {
1630	ubifs_err(c, fmt: "znode checking function returned error %d",
1631	err);
1632	ubifs_dump_znode(c, znode);
1633	goto out_dump;
1634	}
1635	}
1636	if (leaf_cb && znode->level == 0) {
1637	for (idx = 0; idx < znode->child_cnt; idx++) {
1638	zbr = &znode->zbranch[idx];
1639	err = leaf_cb(c, zbr, priv);
1640	if (err) {
1641	ubifs_err(c, fmt: "leaf checking function returned error %d, for leaf at LEB %d:%d",
1642	err, zbr->lnum, zbr->offs);
1643	goto out_dump;
1644	}
1645	}
1646	}
1647
1648	if (!znode->parent)
1649	break;
1650
1651	idx = znode->iip + 1;
1652	znode = znode->parent;
1653	if (idx < znode->child_cnt) {
1654	/* Switch to the next index in the parent */
1655	zbr = &znode->zbranch[idx];
1656	child = zbr->znode;
1657	if (!child) {
1658	child = ubifs_load_znode(c, zbr, parent: znode, iip: idx);
1659	if (IS_ERR(ptr: child)) {
1660	err = PTR_ERR(ptr: child);
1661	goto out_unlock;
1662	}
1663	zbr->znode = child;
1664	}
1665	znode = child;
1666	} else
1667	/*
1668	* This is the last child, switch to the parent and
1669	* continue.
1670	*/
1671	continue;
1672
1673	/* Go to the lowest leftmost znode in the new sub-tree */
1674	while (znode->level > 0) {
1675	zbr = &znode->zbranch[0];
1676	child = zbr->znode;
1677	if (!child) {
1678	child = ubifs_load_znode(c, zbr, parent: znode, iip: 0);
1679	if (IS_ERR(ptr: child)) {
1680	err = PTR_ERR(ptr: child);
1681	goto out_unlock;
1682	}
1683	zbr->znode = child;
1684	}
1685	znode = child;
1686	}
1687	}
1688
1689	mutex_unlock(lock: &c->tnc_mutex);
1690	return 0;
1691
1692	out_dump:
1693	if (znode->parent)
1694	zbr = &znode->parent->zbranch[znode->iip];
1695	else
1696	zbr = &c->zroot;
1697	ubifs_msg(c, fmt: "dump of znode at LEB %d:%d", zbr->lnum, zbr->offs);
1698	ubifs_dump_znode(c, znode);
1699	out_unlock:
1700	mutex_unlock(lock: &c->tnc_mutex);
1701	return err;
1702	}
1703
1704	/**
1705	* add_size - add znode size to partially calculated index size.
1706	* @c: UBIFS file-system description object
1707	* @znode: znode to add size for
1708	* @priv: partially calculated index size
1709	*
1710	* This is a helper function for 'dbg_check_idx_size()' which is called for
1711	* every indexing node and adds its size to the 'long long' variable pointed to
1712	* by @priv.
1713	*/
1714	static int add_size(struct ubifs_info *c, struct ubifs_znode *znode, void *priv)
1715	{
1716	long long *idx_size = priv;
1717	int add;
1718
1719	add = ubifs_idx_node_sz(c, child_cnt: znode->child_cnt);
1720	add = ALIGN(add, 8);
1721	*idx_size += add;
1722	return 0;
1723	}
1724
1725	/**
1726	* dbg_check_idx_size - check index size.
1727	* @c: UBIFS file-system description object
1728	* @idx_size: size to check
1729	*
1730	* This function walks the UBIFS index, calculates its size and checks that the
1731	* size is equivalent to @idx_size. Returns zero in case of success and a
1732	* negative error code in case of failure.
1733	*/
1734	int dbg_check_idx_size(struct ubifs_info *c, long long idx_size)
1735	{
1736	int err;
1737	long long calc = 0;
1738
1739	if (!dbg_is_chk_index(c))
1740	return 0;
1741
1742	err = dbg_walk_index(c, NULL, znode_cb: add_size, priv: &calc);
1743	if (err) {
1744	ubifs_err(c, fmt: "error %d while walking the index", err);
1745	return err;
1746	}
1747
1748	if (calc != idx_size) {
1749	ubifs_err(c, fmt: "index size check failed: calculated size is %lld, should be %lld",
1750	calc, idx_size);
1751	dump_stack();
1752	return -EINVAL;
1753	}
1754
1755	return 0;
1756	}
1757
1758	/**
1759	* struct fsck_inode - information about an inode used when checking the file-system.
1760	* @rb: link in the RB-tree of inodes
1761	* @inum: inode number
1762	* @mode: inode type, permissions, etc
1763	* @nlink: inode link count
1764	* @xattr_cnt: count of extended attributes
1765	* @references: how many directory/xattr entries refer this inode (calculated
1766	* while walking the index)
1767	* @calc_cnt: for directory inode count of child directories
1768	* @size: inode size (read from on-flash inode)
1769	* @xattr_sz: summary size of all extended attributes (read from on-flash
1770	* inode)
1771	* @calc_sz: for directories calculated directory size
1772	* @calc_xcnt: count of extended attributes
1773	* @calc_xsz: calculated summary size of all extended attributes
1774	* @xattr_nms: sum of lengths of all extended attribute names belonging to this
1775	* inode (read from on-flash inode)
1776	* @calc_xnms: calculated sum of lengths of all extended attribute names
1777	*/
1778	struct fsck_inode {
1779	struct rb_node rb;
1780	ino_t inum;
1781	umode_t mode;
1782	unsigned int nlink;
1783	unsigned int xattr_cnt;
1784	int references;
1785	int calc_cnt;
1786	long long size;
1787	unsigned int xattr_sz;
1788	long long calc_sz;
1789	long long calc_xcnt;
1790	long long calc_xsz;
1791	unsigned int xattr_nms;
1792	long long calc_xnms;
1793	};
1794
1795	/**
1796	* struct fsck_data - private FS checking information.
1797	* @inodes: RB-tree of all inodes (contains @struct fsck_inode objects)
1798	*/
1799	struct fsck_data {
1800	struct rb_root inodes;
1801	};
1802
1803	/**
1804	* add_inode - add inode information to RB-tree of inodes.
1805	* @c: UBIFS file-system description object
1806	* @fsckd: FS checking information
1807	* @ino: raw UBIFS inode to add
1808	*
1809	* This is a helper function for 'check_leaf()' which adds information about
1810	* inode @ino to the RB-tree of inodes. Returns inode information pointer in
1811	* case of success and a negative error code in case of failure.
1812	*/
1813	static struct fsck_inode *add_inode(struct ubifs_info *c,
1814	struct fsck_data *fsckd,
1815	struct ubifs_ino_node *ino)
1816	{
1817	struct rb_node **p, *parent = NULL;
1818	struct fsck_inode *fscki;
1819	ino_t inum = key_inum_flash(c, k: &ino->key);
1820	struct inode *inode;
1821	struct ubifs_inode *ui;
1822
1823	p = &fsckd->inodes.rb_node;
1824	while (*p) {
1825	parent = *p;
1826	fscki = rb_entry(parent, struct fsck_inode, rb);
1827	if (inum < fscki->inum)
1828	p = &(*p)->rb_left;
1829	else if (inum > fscki->inum)
1830	p = &(*p)->rb_right;
1831	else
1832	return fscki;
1833	}
1834
1835	if (inum > c->highest_inum) {
1836	ubifs_err(c, fmt: "too high inode number, max. is %lu",
1837	(unsigned long)c->highest_inum);
1838	return ERR_PTR(error: -EINVAL);
1839	}
1840
1841	fscki = kzalloc(size: sizeof(struct fsck_inode), GFP_NOFS);
1842	if (!fscki)
1843	return ERR_PTR(error: -ENOMEM);
1844
1845	inode = ilookup(sb: c->vfs_sb, ino: inum);
1846
1847	fscki->inum = inum;
1848	/*
1849	* If the inode is present in the VFS inode cache, use it instead of
1850	* the on-flash inode which might be out-of-date. E.g., the size might
1851	* be out-of-date. If we do not do this, the following may happen, for
1852	* example:
1853	* 1. A power cut happens
1854	* 2. We mount the file-system R/O, the replay process fixes up the
1855	* inode size in the VFS cache, but on on-flash.
1856	* 3. 'check_leaf()' fails because it hits a data node beyond inode
1857	* size.
1858	*/
1859	if (!inode) {
1860	fscki->nlink = le32_to_cpu(ino->nlink);
1861	fscki->size = le64_to_cpu(ino->size);
1862	fscki->xattr_cnt = le32_to_cpu(ino->xattr_cnt);
1863	fscki->xattr_sz = le32_to_cpu(ino->xattr_size);
1864	fscki->xattr_nms = le32_to_cpu(ino->xattr_names);
1865	fscki->mode = le32_to_cpu(ino->mode);
1866	} else {
1867	ui = ubifs_inode(inode);
1868	fscki->nlink = inode->i_nlink;
1869	fscki->size = inode->i_size;
1870	fscki->xattr_cnt = ui->xattr_cnt;
1871	fscki->xattr_sz = ui->xattr_size;
1872	fscki->xattr_nms = ui->xattr_names;
1873	fscki->mode = inode->i_mode;
1874	iput(inode);
1875	}
1876
1877	if (S_ISDIR(fscki->mode)) {
1878	fscki->calc_sz = UBIFS_INO_NODE_SZ;
1879	fscki->calc_cnt = 2;
1880	}
1881
1882	rb_link_node(node: &fscki->rb, parent, rb_link: p);
1883	rb_insert_color(&fscki->rb, &fsckd->inodes);
1884
1885	return fscki;
1886	}
1887
1888	/**
1889	* search_inode - search inode in the RB-tree of inodes.
1890	* @fsckd: FS checking information
1891	* @inum: inode number to search
1892	*
1893	* This is a helper function for 'check_leaf()' which searches inode @inum in
1894	* the RB-tree of inodes and returns an inode information pointer or %NULL if
1895	* the inode was not found.
1896	*/
1897	static struct fsck_inode *search_inode(struct fsck_data *fsckd, ino_t inum)
1898	{
1899	struct rb_node *p;
1900	struct fsck_inode *fscki;
1901
1902	p = fsckd->inodes.rb_node;
1903	while (p) {
1904	fscki = rb_entry(p, struct fsck_inode, rb);
1905	if (inum < fscki->inum)
1906	p = p->rb_left;
1907	else if (inum > fscki->inum)
1908	p = p->rb_right;
1909	else
1910	return fscki;
1911	}
1912	return NULL;
1913	}
1914
1915	/**
1916	* read_add_inode - read inode node and add it to RB-tree of inodes.
1917	* @c: UBIFS file-system description object
1918	* @fsckd: FS checking information
1919	* @inum: inode number to read
1920	*
1921	* This is a helper function for 'check_leaf()' which finds inode node @inum in
1922	* the index, reads it, and adds it to the RB-tree of inodes. Returns inode
1923	* information pointer in case of success and a negative error code in case of
1924	* failure.
1925	*/
1926	static struct fsck_inode *read_add_inode(struct ubifs_info *c,
1927	struct fsck_data *fsckd, ino_t inum)
1928	{
1929	int n, err;
1930	union ubifs_key key;
1931	struct ubifs_znode *znode;
1932	struct ubifs_zbranch *zbr;
1933	struct ubifs_ino_node *ino;
1934	struct fsck_inode *fscki;
1935
1936	fscki = search_inode(fsckd, inum);
1937	if (fscki)
1938	return fscki;
1939
1940	ino_key_init(c, key: &key, inum);
1941	err = ubifs_lookup_level0(c, key: &key, zn: &znode, n: &n);
1942	if (!err) {
1943	ubifs_err(c, fmt: "inode %lu not found in index", (unsigned long)inum);
1944	return ERR_PTR(error: -ENOENT);
1945	} else if (err < 0) {
1946	ubifs_err(c, fmt: "error %d while looking up inode %lu",
1947	err, (unsigned long)inum);
1948	return ERR_PTR(error: err);
1949	}
1950
1951	zbr = &znode->zbranch[n];
1952	if (zbr->len < UBIFS_INO_NODE_SZ) {
1953	ubifs_err(c, fmt: "bad node %lu node length %d",
1954	(unsigned long)inum, zbr->len);
1955	return ERR_PTR(error: -EINVAL);
1956	}
1957
1958	ino = kmalloc(size: zbr->len, GFP_NOFS);
1959	if (!ino)
1960	return ERR_PTR(error: -ENOMEM);
1961
1962	err = ubifs_tnc_read_node(c, zbr, node: ino);
1963	if (err) {
1964	ubifs_err(c, fmt: "cannot read inode node at LEB %d:%d, error %d",
1965	zbr->lnum, zbr->offs, err);
1966	kfree(objp: ino);
1967	return ERR_PTR(error: err);
1968	}
1969
1970	fscki = add_inode(c, fsckd, ino);
1971	kfree(objp: ino);
1972	if (IS_ERR(ptr: fscki)) {
1973	ubifs_err(c, fmt: "error %ld while adding inode %lu node",
1974	PTR_ERR(ptr: fscki), (unsigned long)inum);
1975	return fscki;
1976	}
1977
1978	return fscki;
1979	}
1980
1981	/**
1982	* check_leaf - check leaf node.
1983	* @c: UBIFS file-system description object
1984	* @zbr: zbranch of the leaf node to check
1985	* @priv: FS checking information
1986	*
1987	* This is a helper function for 'dbg_check_filesystem()' which is called for
1988	* every single leaf node while walking the indexing tree. It checks that the
1989	* leaf node referred from the indexing tree exists, has correct CRC, and does
1990	* some other basic validation. This function is also responsible for building
1991	* an RB-tree of inodes - it adds all inodes into the RB-tree. It also
1992	* calculates reference count, size, etc for each inode in order to later
1993	* compare them to the information stored inside the inodes and detect possible
1994	* inconsistencies. Returns zero in case of success and a negative error code
1995	* in case of failure.
1996	*/
1997	static int check_leaf(struct ubifs_info *c, struct ubifs_zbranch *zbr,
1998	void *priv)
1999	{
2000	ino_t inum;
2001	void *node;
2002	struct ubifs_ch *ch;
2003	int err, type = key_type(c, key: &zbr->key);
2004	struct fsck_inode *fscki;
2005
2006	if (zbr->len < UBIFS_CH_SZ) {
2007	ubifs_err(c, fmt: "bad leaf length %d (LEB %d:%d)",
2008	zbr->len, zbr->lnum, zbr->offs);
2009	return -EINVAL;
2010	}
2011
2012	node = kmalloc(size: zbr->len, GFP_NOFS);
2013	if (!node)
2014	return -ENOMEM;
2015
2016	err = ubifs_tnc_read_node(c, zbr, node);
2017	if (err) {
2018	ubifs_err(c, fmt: "cannot read leaf node at LEB %d:%d, error %d",
2019	zbr->lnum, zbr->offs, err);
2020	goto out_free;
2021	}
2022
2023	/* If this is an inode node, add it to RB-tree of inodes */
2024	if (type == UBIFS_INO_KEY) {
2025	fscki = add_inode(c, fsckd: priv, ino: node);
2026	if (IS_ERR(ptr: fscki)) {
2027	err = PTR_ERR(ptr: fscki);
2028	ubifs_err(c, fmt: "error %d while adding inode node", err);
2029	goto out_dump;
2030	}
2031	goto out;
2032	}
2033
2034	if (type != UBIFS_DENT_KEY && type != UBIFS_XENT_KEY &&
2035	type != UBIFS_DATA_KEY) {
2036	ubifs_err(c, fmt: "unexpected node type %d at LEB %d:%d",
2037	type, zbr->lnum, zbr->offs);
2038	err = -EINVAL;
2039	goto out_free;
2040	}
2041
2042	ch = node;
2043	if (le64_to_cpu(ch->sqnum) > c->max_sqnum) {
2044	ubifs_err(c, fmt: "too high sequence number, max. is %llu",
2045	c->max_sqnum);
2046	err = -EINVAL;
2047	goto out_dump;
2048	}
2049
2050	if (type == UBIFS_DATA_KEY) {
2051	long long blk_offs;
2052	struct ubifs_data_node *dn = node;
2053
2054	ubifs_assert(c, zbr->len >= UBIFS_DATA_NODE_SZ);
2055
2056	/*
2057	* Search the inode node this data node belongs to and insert
2058	* it to the RB-tree of inodes.
2059	*/
2060	inum = key_inum_flash(c, k: &dn->key);
2061	fscki = read_add_inode(c, fsckd: priv, inum);
2062	if (IS_ERR(ptr: fscki)) {
2063	err = PTR_ERR(ptr: fscki);
2064	ubifs_err(c, fmt: "error %d while processing data node and trying to find inode node %lu",
2065	err, (unsigned long)inum);
2066	goto out_dump;
2067	}
2068
2069	/* Make sure the data node is within inode size */
2070	blk_offs = key_block_flash(c, k: &dn->key);
2071	blk_offs <<= UBIFS_BLOCK_SHIFT;
2072	blk_offs += le32_to_cpu(dn->size);
2073	if (blk_offs > fscki->size) {
2074	ubifs_err(c, fmt: "data node at LEB %d:%d is not within inode size %lld",
2075	zbr->lnum, zbr->offs, fscki->size);
2076	err = -EINVAL;
2077	goto out_dump;
2078	}
2079	} else {
2080	int nlen;
2081	struct ubifs_dent_node *dent = node;
2082	struct fsck_inode *fscki1;
2083
2084	ubifs_assert(c, zbr->len >= UBIFS_DENT_NODE_SZ);
2085
2086	err = ubifs_validate_entry(c, dent);
2087	if (err)
2088	goto out_dump;
2089
2090	/*
2091	* Search the inode node this entry refers to and the parent
2092	* inode node and insert them to the RB-tree of inodes.
2093	*/
2094	inum = le64_to_cpu(dent->inum);
2095	fscki = read_add_inode(c, fsckd: priv, inum);
2096	if (IS_ERR(ptr: fscki)) {
2097	err = PTR_ERR(ptr: fscki);
2098	ubifs_err(c, fmt: "error %d while processing entry node and trying to find inode node %lu",
2099	err, (unsigned long)inum);
2100	goto out_dump;
2101	}
2102
2103	/* Count how many direntries or xentries refers this inode */
2104	fscki->references += 1;
2105
2106	inum = key_inum_flash(c, k: &dent->key);
2107	fscki1 = read_add_inode(c, fsckd: priv, inum);
2108	if (IS_ERR(ptr: fscki1)) {
2109	err = PTR_ERR(ptr: fscki1);
2110	ubifs_err(c, fmt: "error %d while processing entry node and trying to find parent inode node %lu",
2111	err, (unsigned long)inum);
2112	goto out_dump;
2113	}
2114
2115	nlen = le16_to_cpu(dent->nlen);
2116	if (type == UBIFS_XENT_KEY) {
2117	fscki1->calc_xcnt += 1;
2118	fscki1->calc_xsz += CALC_DENT_SIZE(nlen);
2119	fscki1->calc_xsz += CALC_XATTR_BYTES(fscki->size);
2120	fscki1->calc_xnms += nlen;
2121	} else {
2122	fscki1->calc_sz += CALC_DENT_SIZE(nlen);
2123	if (dent->type == UBIFS_ITYPE_DIR)
2124	fscki1->calc_cnt += 1;
2125	}
2126	}
2127
2128	out:
2129	kfree(objp: node);
2130	return 0;
2131
2132	out_dump:
2133	ubifs_msg(c, fmt: "dump of node at LEB %d:%d", zbr->lnum, zbr->offs);
2134	ubifs_dump_node(c, node, node_len: zbr->len);
2135	out_free:
2136	kfree(objp: node);
2137	return err;
2138	}
2139
2140	/**
2141	* free_inodes - free RB-tree of inodes.
2142	* @fsckd: FS checking information
2143	*/
2144	static void free_inodes(struct fsck_data *fsckd)
2145	{
2146	struct fsck_inode *fscki, *n;
2147
2148	rbtree_postorder_for_each_entry_safe(fscki, n, &fsckd->inodes, rb)
2149	kfree(objp: fscki);
2150	}
2151
2152	/**
2153	* check_inodes - checks all inodes.
2154	* @c: UBIFS file-system description object
2155	* @fsckd: FS checking information
2156	*
2157	* This is a helper function for 'dbg_check_filesystem()' which walks the
2158	* RB-tree of inodes after the index scan has been finished, and checks that
2159	* inode nlink, size, etc are correct. Returns zero if inodes are fine,
2160	* %-EINVAL if not, and a negative error code in case of failure.
2161	*/
2162	static int check_inodes(struct ubifs_info *c, struct fsck_data *fsckd)
2163	{
2164	int n, err;
2165	union ubifs_key key;
2166	struct ubifs_znode *znode;
2167	struct ubifs_zbranch *zbr;
2168	struct ubifs_ino_node *ino;
2169	struct fsck_inode *fscki;
2170	struct rb_node *this = rb_first(&fsckd->inodes);
2171
2172	while (this) {
2173	fscki = rb_entry(this, struct fsck_inode, rb);
2174	this = rb_next(this);
2175
2176	if (S_ISDIR(fscki->mode)) {
2177	/*
2178	* Directories have to have exactly one reference (they
2179	* cannot have hardlinks), although root inode is an
2180	* exception.
2181	*/
2182	if (fscki->inum != UBIFS_ROOT_INO &&
2183	fscki->references != 1) {
2184	ubifs_err(c, fmt: "directory inode %lu has %d direntries which refer it, but should be 1",
2185	(unsigned long)fscki->inum,
2186	fscki->references);
2187	goto out_dump;
2188	}
2189	if (fscki->inum == UBIFS_ROOT_INO &&
2190	fscki->references != 0) {
2191	ubifs_err(c, fmt: "root inode %lu has non-zero (%d) direntries which refer it",
2192	(unsigned long)fscki->inum,
2193	fscki->references);
2194	goto out_dump;
2195	}
2196	if (fscki->calc_sz != fscki->size) {
2197	ubifs_err(c, fmt: "directory inode %lu size is %lld, but calculated size is %lld",
2198	(unsigned long)fscki->inum,
2199	fscki->size, fscki->calc_sz);
2200	goto out_dump;
2201	}
2202	if (fscki->calc_cnt != fscki->nlink) {
2203	ubifs_err(c, fmt: "directory inode %lu nlink is %d, but calculated nlink is %d",
2204	(unsigned long)fscki->inum,
2205	fscki->nlink, fscki->calc_cnt);
2206	goto out_dump;
2207	}
2208	} else {
2209	if (fscki->references != fscki->nlink) {
2210	ubifs_err(c, fmt: "inode %lu nlink is %d, but calculated nlink is %d",
2211	(unsigned long)fscki->inum,
2212	fscki->nlink, fscki->references);
2213	goto out_dump;
2214	}
2215	}
2216	if (fscki->xattr_sz != fscki->calc_xsz) {
2217	ubifs_err(c, fmt: "inode %lu has xattr size %u, but calculated size is %lld",
2218	(unsigned long)fscki->inum, fscki->xattr_sz,
2219	fscki->calc_xsz);
2220	goto out_dump;
2221	}
2222	if (fscki->xattr_cnt != fscki->calc_xcnt) {
2223	ubifs_err(c, fmt: "inode %lu has %u xattrs, but calculated count is %lld",
2224	(unsigned long)fscki->inum,
2225	fscki->xattr_cnt, fscki->calc_xcnt);
2226	goto out_dump;
2227	}
2228	if (fscki->xattr_nms != fscki->calc_xnms) {
2229	ubifs_err(c, fmt: "inode %lu has xattr names' size %u, but calculated names' size is %lld",
2230	(unsigned long)fscki->inum, fscki->xattr_nms,
2231	fscki->calc_xnms);
2232	goto out_dump;
2233	}
2234	}
2235
2236	return 0;
2237
2238	out_dump:
2239	/* Read the bad inode and dump it */
2240	ino_key_init(c, key: &key, inum: fscki->inum);
2241	err = ubifs_lookup_level0(c, key: &key, zn: &znode, n: &n);
2242	if (!err) {
2243	ubifs_err(c, fmt: "inode %lu not found in index",
2244	(unsigned long)fscki->inum);
2245	return -ENOENT;
2246	} else if (err < 0) {
2247	ubifs_err(c, fmt: "error %d while looking up inode %lu",
2248	err, (unsigned long)fscki->inum);
2249	return err;
2250	}
2251
2252	zbr = &znode->zbranch[n];
2253	ino = kmalloc(size: zbr->len, GFP_NOFS);
2254	if (!ino)
2255	return -ENOMEM;
2256
2257	err = ubifs_tnc_read_node(c, zbr, node: ino);
2258	if (err) {
2259	ubifs_err(c, fmt: "cannot read inode node at LEB %d:%d, error %d",
2260	zbr->lnum, zbr->offs, err);
2261	kfree(objp: ino);
2262	return err;
2263	}
2264
2265	ubifs_msg(c, fmt: "dump of the inode %lu sitting in LEB %d:%d",
2266	(unsigned long)fscki->inum, zbr->lnum, zbr->offs);
2267	ubifs_dump_node(c, node: ino, node_len: zbr->len);
2268	kfree(objp: ino);
2269	return -EINVAL;
2270	}
2271
2272	/**
2273	* dbg_check_filesystem - check the file-system.
2274	* @c: UBIFS file-system description object
2275	*
2276	* This function checks the file system, namely:
2277	* o makes sure that all leaf nodes exist and their CRCs are correct;
2278	* o makes sure inode nlink, size, xattr size/count are correct (for all
2279	* inodes).
2280	*
2281	* The function reads whole indexing tree and all nodes, so it is pretty
2282	* heavy-weight. Returns zero if the file-system is consistent, %-EINVAL if
2283	* not, and a negative error code in case of failure.
2284	*/
2285	int dbg_check_filesystem(struct ubifs_info *c)
2286	{
2287	int err;
2288	struct fsck_data fsckd;
2289
2290	if (!dbg_is_chk_fs(c))
2291	return 0;
2292
2293	fsckd.inodes = RB_ROOT;
2294	err = dbg_walk_index(c, leaf_cb: check_leaf, NULL, priv: &fsckd);
2295	if (err)
2296	goto out_free;
2297
2298	err = check_inodes(c, fsckd: &fsckd);
2299	if (err)
2300	goto out_free;
2301
2302	free_inodes(fsckd: &fsckd);
2303	return 0;
2304
2305	out_free:
2306	ubifs_err(c, fmt: "file-system check failed with error %d", err);
2307	dump_stack();
2308	free_inodes(fsckd: &fsckd);
2309	return err;
2310	}
2311
2312	/**
2313	* dbg_check_data_nodes_order - check that list of data nodes is sorted.
2314	* @c: UBIFS file-system description object
2315	* @head: the list of nodes ('struct ubifs_scan_node' objects)
2316	*
2317	* This function returns zero if the list of data nodes is sorted correctly,
2318	* and %-EINVAL if not.
2319	*/
2320	int dbg_check_data_nodes_order(struct ubifs_info *c, struct list_head *head)
2321	{
2322	struct list_head *cur;
2323	struct ubifs_scan_node *sa, *sb;
2324
2325	if (!dbg_is_chk_gen(c))
2326	return 0;
2327
2328	for (cur = head->next; cur->next != head; cur = cur->next) {
2329	ino_t inuma, inumb;
2330	uint32_t blka, blkb;
2331
2332	cond_resched();
2333	sa = container_of(cur, struct ubifs_scan_node, list);
2334	sb = container_of(cur->next, struct ubifs_scan_node, list);
2335
2336	if (sa->type != UBIFS_DATA_NODE) {
2337	ubifs_err(c, fmt: "bad node type %d", sa->type);
2338	ubifs_dump_node(c, node: sa->node, node_len: c->leb_size - sa->offs);
2339	return -EINVAL;
2340	}
2341	if (sb->type != UBIFS_DATA_NODE) {
2342	ubifs_err(c, fmt: "bad node type %d", sb->type);
2343	ubifs_dump_node(c, node: sb->node, node_len: c->leb_size - sb->offs);
2344	return -EINVAL;
2345	}
2346
2347	inuma = key_inum(c, k: &sa->key);
2348	inumb = key_inum(c, k: &sb->key);
2349
2350	if (inuma < inumb)
2351	continue;
2352	if (inuma > inumb) {
2353	ubifs_err(c, fmt: "larger inum %lu goes before inum %lu",
2354	(unsigned long)inuma, (unsigned long)inumb);
2355	goto error_dump;
2356	}
2357
2358	blka = key_block(c, key: &sa->key);
2359	blkb = key_block(c, key: &sb->key);
2360
2361	if (blka > blkb) {
2362	ubifs_err(c, fmt: "larger block %u goes before %u", blka, blkb);
2363	goto error_dump;
2364	}
2365	if (blka == blkb) {
2366	ubifs_err(c, fmt: "two data nodes for the same block");
2367	goto error_dump;
2368	}
2369	}
2370
2371	return 0;
2372
2373	error_dump:
2374	ubifs_dump_node(c, node: sa->node, node_len: c->leb_size - sa->offs);
2375	ubifs_dump_node(c, node: sb->node, node_len: c->leb_size - sb->offs);
2376	return -EINVAL;
2377	}
2378
2379	/**
2380	* dbg_check_nondata_nodes_order - check that list of data nodes is sorted.
2381	* @c: UBIFS file-system description object
2382	* @head: the list of nodes ('struct ubifs_scan_node' objects)
2383	*
2384	* This function returns zero if the list of non-data nodes is sorted correctly,
2385	* and %-EINVAL if not.
2386	*/
2387	int dbg_check_nondata_nodes_order(struct ubifs_info *c, struct list_head *head)
2388	{
2389	struct list_head *cur;
2390	struct ubifs_scan_node *sa, *sb;
2391
2392	if (!dbg_is_chk_gen(c))
2393	return 0;
2394
2395	for (cur = head->next; cur->next != head; cur = cur->next) {
2396	ino_t inuma, inumb;
2397	uint32_t hasha, hashb;
2398
2399	cond_resched();
2400	sa = container_of(cur, struct ubifs_scan_node, list);
2401	sb = container_of(cur->next, struct ubifs_scan_node, list);
2402
2403	if (sa->type != UBIFS_INO_NODE && sa->type != UBIFS_DENT_NODE &&
2404	sa->type != UBIFS_XENT_NODE) {
2405	ubifs_err(c, fmt: "bad node type %d", sa->type);
2406	ubifs_dump_node(c, node: sa->node, node_len: c->leb_size - sa->offs);
2407	return -EINVAL;
2408	}
2409	if (sb->type != UBIFS_INO_NODE && sb->type != UBIFS_DENT_NODE &&
2410	sb->type != UBIFS_XENT_NODE) {
2411	ubifs_err(c, fmt: "bad node type %d", sb->type);
2412	ubifs_dump_node(c, node: sb->node, node_len: c->leb_size - sb->offs);
2413	return -EINVAL;
2414	}
2415
2416	if (sa->type != UBIFS_INO_NODE && sb->type == UBIFS_INO_NODE) {
2417	ubifs_err(c, fmt: "non-inode node goes before inode node");
2418	goto error_dump;
2419	}
2420
2421	if (sa->type == UBIFS_INO_NODE && sb->type != UBIFS_INO_NODE)
2422	continue;
2423
2424	if (sa->type == UBIFS_INO_NODE && sb->type == UBIFS_INO_NODE) {
2425	/* Inode nodes are sorted in descending size order */
2426	if (sa->len < sb->len) {
2427	ubifs_err(c, fmt: "smaller inode node goes first");
2428	goto error_dump;
2429	}
2430	continue;
2431	}
2432
2433	/*
2434	* This is either a dentry or xentry, which should be sorted in
2435	* ascending (parent ino, hash) order.
2436	*/
2437	inuma = key_inum(c, k: &sa->key);
2438	inumb = key_inum(c, k: &sb->key);
2439
2440	if (inuma < inumb)
2441	continue;
2442	if (inuma > inumb) {
2443	ubifs_err(c, fmt: "larger inum %lu goes before inum %lu",
2444	(unsigned long)inuma, (unsigned long)inumb);
2445	goto error_dump;
2446	}
2447
2448	hasha = key_block(c, key: &sa->key);
2449	hashb = key_block(c, key: &sb->key);
2450
2451	if (hasha > hashb) {
2452	ubifs_err(c, fmt: "larger hash %u goes before %u",
2453	hasha, hashb);
2454	goto error_dump;
2455	}
2456	}
2457
2458	return 0;
2459
2460	error_dump:
2461	ubifs_msg(c, fmt: "dumping first node");
2462	ubifs_dump_node(c, node: sa->node, node_len: c->leb_size - sa->offs);
2463	ubifs_msg(c, fmt: "dumping second node");
2464	ubifs_dump_node(c, node: sb->node, node_len: c->leb_size - sb->offs);
2465	return -EINVAL;
2466	}
2467
2468	static inline int chance(unsigned int n, unsigned int out_of)
2469	{
2470	return !!(get_random_u32_below(ceil: out_of) + 1 <= n);
2471
2472	}
2473
2474	static int power_cut_emulated(struct ubifs_info *c, int lnum, int write)
2475	{
2476	struct ubifs_debug_info *d = c->dbg;
2477
2478	ubifs_assert(c, dbg_is_tst_rcvry(c));
2479
2480	if (!d->pc_cnt) {
2481	/* First call - decide delay to the power cut */
2482	if (chance(n: 1, out_of: 2)) {
2483	unsigned long delay;
2484
2485	if (chance(n: 1, out_of: 2)) {
2486	d->pc_delay = 1;
2487	/* Fail within 1 minute */
2488	delay = get_random_u32_below(ceil: 60000);
2489	d->pc_timeout = jiffies;
2490	d->pc_timeout += msecs_to_jiffies(m: delay);
2491	ubifs_warn(c, fmt: "failing after %lums", delay);
2492	} else {
2493	d->pc_delay = 2;
2494	delay = get_random_u32_below(ceil: 10000);
2495	/* Fail within 10000 operations */
2496	d->pc_cnt_max = delay;
2497	ubifs_warn(c, fmt: "failing after %lu calls", delay);
2498	}
2499	}
2500
2501	d->pc_cnt += 1;
2502	}
2503
2504	/* Determine if failure delay has expired */
2505	if (d->pc_delay == 1 && time_before(jiffies, d->pc_timeout))
2506	return 0;
2507	if (d->pc_delay == 2 && d->pc_cnt++ < d->pc_cnt_max)
2508	return 0;
2509
2510	if (lnum == UBIFS_SB_LNUM) {
2511	if (write && chance(n: 1, out_of: 2))
2512	return 0;
2513	if (chance(n: 19, out_of: 20))
2514	return 0;
2515	ubifs_warn(c, fmt: "failing in super block LEB %d", lnum);
2516	} else if (lnum == UBIFS_MST_LNUM || lnum == UBIFS_MST_LNUM + 1) {
2517	if (chance(n: 19, out_of: 20))
2518	return 0;
2519	ubifs_warn(c, fmt: "failing in master LEB %d", lnum);
2520	} else if (lnum >= UBIFS_LOG_LNUM && lnum <= c->log_last) {
2521	if (write && chance(n: 99, out_of: 100))
2522	return 0;
2523	if (chance(n: 399, out_of: 400))
2524	return 0;
2525	ubifs_warn(c, fmt: "failing in log LEB %d", lnum);
2526	} else if (lnum >= c->lpt_first && lnum <= c->lpt_last) {
2527	if (write && chance(n: 7, out_of: 8))
2528	return 0;
2529	if (chance(n: 19, out_of: 20))
2530	return 0;
2531	ubifs_warn(c, fmt: "failing in LPT LEB %d", lnum);
2532	} else if (lnum >= c->orph_first && lnum <= c->orph_last) {
2533	if (write && chance(n: 1, out_of: 2))
2534	return 0;
2535	if (chance(n: 9, out_of: 10))
2536	return 0;
2537	ubifs_warn(c, fmt: "failing in orphan LEB %d", lnum);
2538	} else if (lnum == c->ihead_lnum) {
2539	if (chance(n: 99, out_of: 100))
2540	return 0;
2541	ubifs_warn(c, fmt: "failing in index head LEB %d", lnum);
2542	} else if (c->jheads && lnum == c->jheads[GCHD].wbuf.lnum) {
2543	if (chance(n: 9, out_of: 10))
2544	return 0;
2545	ubifs_warn(c, fmt: "failing in GC head LEB %d", lnum);
2546	} else if (write && !RB_EMPTY_ROOT(&c->buds) &&
2547	!ubifs_search_bud(c, lnum)) {
2548	if (chance(n: 19, out_of: 20))
2549	return 0;
2550	ubifs_warn(c, fmt: "failing in non-bud LEB %d", lnum);
2551	} else if (c->cmt_state == COMMIT_RUNNING_BACKGROUND ||
2552	c->cmt_state == COMMIT_RUNNING_REQUIRED) {
2553	if (chance(n: 999, out_of: 1000))
2554	return 0;
2555	ubifs_warn(c, fmt: "failing in bud LEB %d commit running", lnum);
2556	} else {
2557	if (chance(n: 9999, out_of: 10000))
2558	return 0;
2559	ubifs_warn(c, fmt: "failing in bud LEB %d commit not running", lnum);
2560	}
2561
2562	d->pc_happened = 1;
2563	ubifs_warn(c, fmt: "========== Power cut emulated ==========");
2564	dump_stack();
2565	return 1;
2566	}
2567
2568	static int corrupt_data(const struct ubifs_info *c, const void *buf,
2569	unsigned int len)
2570	{
2571	unsigned int from, to, ffs = chance(n: 1, out_of: 2);
2572	unsigned char *p = (void *)buf;
2573
2574	from = get_random_u32_below(ceil: len);
2575	/* Corruption span max to end of write unit */
2576	to = min(len, ALIGN(from + 1, c->max_write_size));
2577
2578	ubifs_warn(c, fmt: "filled bytes %u-%u with %s", from, to - 1,
2579	ffs ? "0xFFs" : "random data");
2580
2581	if (ffs)
2582	memset(p + from, 0xFF, to - from);
2583	else
2584	get_random_bytes(buf: p + from, len: to - from);
2585
2586	return to;
2587	}
2588
2589	int dbg_leb_write(struct ubifs_info *c, int lnum, const void *buf,
2590	int offs, int len)
2591	{
2592	int err, failing;
2593
2594	if (dbg_is_power_cut(c))
2595	return -EROFS;
2596
2597	failing = power_cut_emulated(c, lnum, write: 1);
2598	if (failing) {
2599	len = corrupt_data(c, buf, len);
2600	ubifs_warn(c, fmt: "actually write %d bytes to LEB %d:%d (the buffer was corrupted)",
2601	len, lnum, offs);
2602	}
2603	err = ubi_leb_write(desc: c->ubi, lnum, buf, offset: offs, len);
2604	if (err)
2605	return err;
2606	if (failing)
2607	return -EROFS;
2608	return 0;
2609	}
2610
2611	int dbg_leb_change(struct ubifs_info *c, int lnum, const void *buf,
2612	int len)
2613	{
2614	int err;
2615
2616	if (dbg_is_power_cut(c))
2617	return -EROFS;
2618	if (power_cut_emulated(c, lnum, write: 1))
2619	return -EROFS;
2620	err = ubi_leb_change(desc: c->ubi, lnum, buf, len);
2621	if (err)
2622	return err;
2623	if (power_cut_emulated(c, lnum, write: 1))
2624	return -EROFS;
2625	return 0;
2626	}
2627
2628	int dbg_leb_unmap(struct ubifs_info *c, int lnum)
2629	{
2630	int err;
2631
2632	if (dbg_is_power_cut(c))
2633	return -EROFS;
2634	if (power_cut_emulated(c, lnum, write: 0))
2635	return -EROFS;
2636	err = ubi_leb_unmap(desc: c->ubi, lnum);
2637	if (err)
2638	return err;
2639	if (power_cut_emulated(c, lnum, write: 0))
2640	return -EROFS;
2641	return 0;
2642	}
2643
2644	int dbg_leb_map(struct ubifs_info *c, int lnum)
2645	{
2646	int err;
2647
2648	if (dbg_is_power_cut(c))
2649	return -EROFS;
2650	if (power_cut_emulated(c, lnum, write: 0))
2651	return -EROFS;
2652	err = ubi_leb_map(desc: c->ubi, lnum);
2653	if (err)
2654	return err;
2655	if (power_cut_emulated(c, lnum, write: 0))
2656	return -EROFS;
2657	return 0;
2658	}
2659
2660	/*
2661	* Root directory for UBIFS stuff in debugfs. Contains sub-directories which
2662	* contain the stuff specific to particular file-system mounts.
2663	*/
2664	static struct dentry *dfs_rootdir;
2665
2666	static int dfs_file_open(struct inode *inode, struct file *file)
2667	{
2668	file->private_data = inode->i_private;
2669	return nonseekable_open(inode, filp: file);
2670	}
2671
2672	/**
2673	* provide_user_output - provide output to the user reading a debugfs file.
2674	* @val: boolean value for the answer
2675	* @u: the buffer to store the answer at
2676	* @count: size of the buffer
2677	* @ppos: position in the @u output buffer
2678	*
2679	* This is a simple helper function which stores @val boolean value in the user
2680	* buffer when the user reads one of UBIFS debugfs files. Returns amount of
2681	* bytes written to @u in case of success and a negative error code in case of
2682	* failure.
2683	*/
2684	static int provide_user_output(int val, char __user *u, size_t count,
2685	loff_t *ppos)
2686	{
2687	char buf[3];
2688
2689	if (val)
2690	buf[0] = '1';
2691	else
2692	buf[0] = '0';
2693	buf[1] = '\n';
2694	buf[2] = 0x00;
2695
2696	return simple_read_from_buffer(to: u, count, ppos, from: buf, available: 2);
2697	}
2698
2699	static ssize_t dfs_file_read(struct file *file, char __user *u, size_t count,
2700	loff_t *ppos)
2701	{
2702	struct dentry *dent = file->f_path.dentry;
2703	struct ubifs_info *c = file->private_data;
2704	struct ubifs_debug_info *d = c->dbg;
2705	int val;
2706
2707	if (dent == d->dfs_chk_gen)
2708	val = d->chk_gen;
2709	else if (dent == d->dfs_chk_index)
2710	val = d->chk_index;
2711	else if (dent == d->dfs_chk_orph)
2712	val = d->chk_orph;
2713	else if (dent == d->dfs_chk_lprops)
2714	val = d->chk_lprops;
2715	else if (dent == d->dfs_chk_fs)
2716	val = d->chk_fs;
2717	else if (dent == d->dfs_tst_rcvry)
2718	val = d->tst_rcvry;
2719	else if (dent == d->dfs_ro_error)
2720	val = c->ro_error;
2721	else
2722	return -EINVAL;
2723
2724	return provide_user_output(val, u, count, ppos);
2725	}
2726
2727	/**
2728	* interpret_user_input - interpret user debugfs file input.
2729	* @u: user-provided buffer with the input
2730	* @count: buffer size
2731	*
2732	* This is a helper function which interpret user input to a boolean UBIFS
2733	* debugfs file. Returns %0 or %1 in case of success and a negative error code
2734	* in case of failure.
2735	*/
2736	static int interpret_user_input(const char __user *u, size_t count)
2737	{
2738	size_t buf_size;
2739	char buf[8];
2740
2741	buf_size = min_t(size_t, count, (sizeof(buf) - 1));
2742	if (copy_from_user(to: buf, from: u, n: buf_size))
2743	return -EFAULT;
2744
2745	if (buf[0] == '1')
2746	return 1;
2747	else if (buf[0] == '0')
2748	return 0;
2749
2750	return -EINVAL;
2751	}
2752
2753	static ssize_t dfs_file_write(struct file *file, const char __user *u,
2754	size_t count, loff_t *ppos)
2755	{
2756	struct ubifs_info *c = file->private_data;
2757	struct ubifs_debug_info *d = c->dbg;
2758	struct dentry *dent = file->f_path.dentry;
2759	int val;
2760
2761	if (file->f_path.dentry == d->dfs_dump_lprops) {
2762	ubifs_dump_lprops(c);
2763	return count;
2764	}
2765	if (file->f_path.dentry == d->dfs_dump_budg) {
2766	ubifs_dump_budg(c, bi: &c->bi);
2767	return count;
2768	}
2769	if (file->f_path.dentry == d->dfs_dump_tnc) {
2770	mutex_lock(&c->tnc_mutex);
2771	ubifs_dump_tnc(c);
2772	mutex_unlock(lock: &c->tnc_mutex);
2773	return count;
2774	}
2775
2776	val = interpret_user_input(u, count);
2777	if (val < 0)
2778	return val;
2779
2780	if (dent == d->dfs_chk_gen)
2781	d->chk_gen = val;
2782	else if (dent == d->dfs_chk_index)
2783	d->chk_index = val;
2784	else if (dent == d->dfs_chk_orph)
2785	d->chk_orph = val;
2786	else if (dent == d->dfs_chk_lprops)
2787	d->chk_lprops = val;
2788	else if (dent == d->dfs_chk_fs)
2789	d->chk_fs = val;
2790	else if (dent == d->dfs_tst_rcvry)
2791	d->tst_rcvry = val;
2792	else if (dent == d->dfs_ro_error)
2793	c->ro_error = !!val;
2794	else
2795	return -EINVAL;
2796
2797	return count;
2798	}
2799
2800	static const struct file_operations dfs_fops = {
2801	.open = dfs_file_open,
2802	.read = dfs_file_read,
2803	.write = dfs_file_write,
2804	.owner = THIS_MODULE,
2805	.llseek = no_llseek,
2806	};
2807
2808	/**
2809	* dbg_debugfs_init_fs - initialize debugfs for UBIFS instance.
2810	* @c: UBIFS file-system description object
2811	*
2812	* This function creates all debugfs files for this instance of UBIFS.
2813	*
2814	* Note, the only reason we have not merged this function with the
2815	* 'ubifs_debugging_init()' function is because it is better to initialize
2816	* debugfs interfaces at the very end of the mount process, and remove them at
2817	* the very beginning of the mount process.
2818	*/
2819	void dbg_debugfs_init_fs(struct ubifs_info *c)
2820	{
2821	int n;
2822	const char *fname;
2823	struct ubifs_debug_info *d = c->dbg;
2824
2825	n = snprintf(buf: d->dfs_dir_name, UBIFS_DFS_DIR_LEN + 1, UBIFS_DFS_DIR_NAME,
2826	c->vi.ubi_num, c->vi.vol_id);
2827	if (n > UBIFS_DFS_DIR_LEN) {
2828	/* The array size is too small */
2829	return;
2830	}
2831
2832	fname = d->dfs_dir_name;
2833	d->dfs_dir = debugfs_create_dir(name: fname, parent: dfs_rootdir);
2834
2835	fname = "dump_lprops";
2836	d->dfs_dump_lprops = debugfs_create_file(name: fname, S_IWUSR, parent: d->dfs_dir, data: c,
2837	fops: &dfs_fops);
2838
2839	fname = "dump_budg";
2840	d->dfs_dump_budg = debugfs_create_file(name: fname, S_IWUSR, parent: d->dfs_dir, data: c,
2841	fops: &dfs_fops);
2842
2843	fname = "dump_tnc";
2844	d->dfs_dump_tnc = debugfs_create_file(name: fname, S_IWUSR, parent: d->dfs_dir, data: c,
2845	fops: &dfs_fops);
2846
2847	fname = "chk_general";
2848	d->dfs_chk_gen = debugfs_create_file(name: fname, S_IRUSR | S_IWUSR,
2849	parent: d->dfs_dir, data: c, fops: &dfs_fops);
2850
2851	fname = "chk_index";
2852	d->dfs_chk_index = debugfs_create_file(name: fname, S_IRUSR | S_IWUSR,
2853	parent: d->dfs_dir, data: c, fops: &dfs_fops);
2854
2855	fname = "chk_orphans";
2856	d->dfs_chk_orph = debugfs_create_file(name: fname, S_IRUSR | S_IWUSR,
2857	parent: d->dfs_dir, data: c, fops: &dfs_fops);
2858
2859	fname = "chk_lprops";
2860	d->dfs_chk_lprops = debugfs_create_file(name: fname, S_IRUSR | S_IWUSR,
2861	parent: d->dfs_dir, data: c, fops: &dfs_fops);
2862
2863	fname = "chk_fs";
2864	d->dfs_chk_fs = debugfs_create_file(name: fname, S_IRUSR | S_IWUSR,
2865	parent: d->dfs_dir, data: c, fops: &dfs_fops);
2866
2867	fname = "tst_recovery";
2868	d->dfs_tst_rcvry = debugfs_create_file(name: fname, S_IRUSR | S_IWUSR,
2869	parent: d->dfs_dir, data: c, fops: &dfs_fops);
2870
2871	fname = "ro_error";
2872	d->dfs_ro_error = debugfs_create_file(name: fname, S_IRUSR | S_IWUSR,
2873	parent: d->dfs_dir, data: c, fops: &dfs_fops);
2874	}
2875
2876	/**
2877	* dbg_debugfs_exit_fs - remove all debugfs files.
2878	* @c: UBIFS file-system description object
2879	*/
2880	void dbg_debugfs_exit_fs(struct ubifs_info *c)
2881	{
2882	debugfs_remove_recursive(dentry: c->dbg->dfs_dir);
2883	}
2884
2885	struct ubifs_global_debug_info ubifs_dbg;
2886
2887	static struct dentry *dfs_chk_gen;
2888	static struct dentry *dfs_chk_index;
2889	static struct dentry *dfs_chk_orph;
2890	static struct dentry *dfs_chk_lprops;
2891	static struct dentry *dfs_chk_fs;
2892	static struct dentry *dfs_tst_rcvry;
2893
2894	static ssize_t dfs_global_file_read(struct file *file, char __user *u,
2895	size_t count, loff_t *ppos)
2896	{
2897	struct dentry *dent = file->f_path.dentry;
2898	int val;
2899
2900	if (dent == dfs_chk_gen)
2901	val = ubifs_dbg.chk_gen;
2902	else if (dent == dfs_chk_index)
2903	val = ubifs_dbg.chk_index;
2904	else if (dent == dfs_chk_orph)
2905	val = ubifs_dbg.chk_orph;
2906	else if (dent == dfs_chk_lprops)
2907	val = ubifs_dbg.chk_lprops;
2908	else if (dent == dfs_chk_fs)
2909	val = ubifs_dbg.chk_fs;
2910	else if (dent == dfs_tst_rcvry)
2911	val = ubifs_dbg.tst_rcvry;
2912	else
2913	return -EINVAL;
2914
2915	return provide_user_output(val, u, count, ppos);
2916	}
2917
2918	static ssize_t dfs_global_file_write(struct file *file, const char __user *u,
2919	size_t count, loff_t *ppos)
2920	{
2921	struct dentry *dent = file->f_path.dentry;
2922	int val;
2923
2924	val = interpret_user_input(u, count);
2925	if (val < 0)
2926	return val;
2927
2928	if (dent == dfs_chk_gen)
2929	ubifs_dbg.chk_gen = val;
2930	else if (dent == dfs_chk_index)
2931	ubifs_dbg.chk_index = val;
2932	else if (dent == dfs_chk_orph)
2933	ubifs_dbg.chk_orph = val;
2934	else if (dent == dfs_chk_lprops)
2935	ubifs_dbg.chk_lprops = val;
2936	else if (dent == dfs_chk_fs)
2937	ubifs_dbg.chk_fs = val;
2938	else if (dent == dfs_tst_rcvry)
2939	ubifs_dbg.tst_rcvry = val;
2940	else
2941	return -EINVAL;
2942
2943	return count;
2944	}
2945
2946	static const struct file_operations dfs_global_fops = {
2947	.read = dfs_global_file_read,
2948	.write = dfs_global_file_write,
2949	.owner = THIS_MODULE,
2950	.llseek = no_llseek,
2951	};
2952
2953	/**
2954	* dbg_debugfs_init - initialize debugfs file-system.
2955	*
2956	* UBIFS uses debugfs file-system to expose various debugging knobs to
2957	* user-space. This function creates "ubifs" directory in the debugfs
2958	* file-system.
2959	*/
2960	void dbg_debugfs_init(void)
2961	{
2962	const char *fname;
2963
2964	fname = "ubifs";
2965	dfs_rootdir = debugfs_create_dir(name: fname, NULL);
2966
2967	fname = "chk_general";
2968	dfs_chk_gen = debugfs_create_file(name: fname, S_IRUSR | S_IWUSR, parent: dfs_rootdir,
2969	NULL, fops: &dfs_global_fops);
2970
2971	fname = "chk_index";
2972	dfs_chk_index = debugfs_create_file(name: fname, S_IRUSR | S_IWUSR,
2973	parent: dfs_rootdir, NULL, fops: &dfs_global_fops);
2974
2975	fname = "chk_orphans";
2976	dfs_chk_orph = debugfs_create_file(name: fname, S_IRUSR | S_IWUSR,
2977	parent: dfs_rootdir, NULL, fops: &dfs_global_fops);
2978
2979	fname = "chk_lprops";
2980	dfs_chk_lprops = debugfs_create_file(name: fname, S_IRUSR | S_IWUSR,
2981	parent: dfs_rootdir, NULL, fops: &dfs_global_fops);
2982
2983	fname = "chk_fs";
2984	dfs_chk_fs = debugfs_create_file(name: fname, S_IRUSR | S_IWUSR, parent: dfs_rootdir,
2985	NULL, fops: &dfs_global_fops);
2986
2987	fname = "tst_recovery";
2988	dfs_tst_rcvry = debugfs_create_file(name: fname, S_IRUSR | S_IWUSR,
2989	parent: dfs_rootdir, NULL, fops: &dfs_global_fops);
2990	}
2991
2992	/**
2993	* dbg_debugfs_exit - remove the "ubifs" directory from debugfs file-system.
2994	*/
2995	void dbg_debugfs_exit(void)
2996	{
2997	debugfs_remove_recursive(dentry: dfs_rootdir);
2998	}
2999
3000	void ubifs_assert_failed(struct ubifs_info *c, const char *expr,
3001	const char *file, int line)
3002	{
3003	ubifs_err(c, fmt: "UBIFS assert failed: %s, in %s:%u", expr, file, line);
3004
3005	switch (c->assert_action) {
3006	case ASSACT_PANIC:
3007	BUG();
3008	break;
3009
3010	case ASSACT_RO:
3011	ubifs_ro_mode(c, err: -EINVAL);
3012	break;
3013
3014	case ASSACT_REPORT:
3015	default:
3016	dump_stack();
3017	break;
3018
3019	}
3020	}
3021
3022	/**
3023	* ubifs_debugging_init - initialize UBIFS debugging.
3024	* @c: UBIFS file-system description object
3025	*
3026	* This function initializes debugging-related data for the file system.
3027	* Returns zero in case of success and a negative error code in case of
3028	* failure.
3029	*/
3030	int ubifs_debugging_init(struct ubifs_info *c)
3031	{
3032	c->dbg = kzalloc(size: sizeof(struct ubifs_debug_info), GFP_KERNEL);
3033	if (!c->dbg)
3034	return -ENOMEM;
3035
3036	return 0;
3037	}
3038
3039	/**
3040	* ubifs_debugging_exit - free debugging data.
3041	* @c: UBIFS file-system description object
3042	*/
3043	void ubifs_debugging_exit(struct ubifs_info *c)
3044	{
3045	kfree(objp: c->dbg);
3046	}
3047