Bootlin logo

Elixir Cross Referencer

   1
   2
   3
   4
   5
   6
   7
   8
   9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
 100
 101
 102
 103
 104
 105
 106
 107
 108
 109
 110
 111
 112
 113
 114
 115
 116
 117
 118
 119
 120
 121
 122
 123
 124
 125
 126
 127
 128
 129
 130
 131
 132
 133
 134
 135
 136
 137
 138
 139
 140
 141
 142
 143
 144
 145
 146
 147
 148
 149
 150
 151
 152
 153
 154
 155
 156
 157
 158
 159
 160
 161
 162
 163
 164
 165
 166
 167
 168
 169
 170
 171
 172
 173
 174
 175
 176
 177
 178
 179
 180
 181
 182
 183
 184
 185
 186
 187
 188
 189
 190
 191
 192
 193
 194
 195
 196
 197
 198
 199
 200
 201
 202
 203
 204
 205
 206
 207
 208
 209
 210
 211
 212
 213
 214
 215
 216
 217
 218
 219
 220
 221
 222
 223
 224
 225
 226
 227
 228
 229
 230
 231
 232
 233
 234
 235
 236
 237
 238
 239
 240
 241
 242
 243
 244
 245
 246
 247
 248
 249
 250
 251
 252
 253
 254
 255
 256
 257
 258
 259
 260
 261
 262
 263
 264
 265
 266
 267
 268
 269
 270
 271
 272
 273
 274
 275
 276
 277
 278
 279
 280
 281
 282
 283
 284
 285
 286
 287
 288
 289
 290
 291
 292
 293
 294
 295
 296
 297
 298
 299
 300
 301
 302
 303
 304
 305
 306
 307
 308
 309
 310
 311
 312
 313
 314
 315
 316
 317
 318
 319
 320
 321
 322
 323
 324
 325
 326
 327
 328
 329
 330
 331
 332
 333
 334
 335
 336
 337
 338
 339
 340
 341
 342
 343
 344
 345
 346
 347
 348
 349
 350
 351
 352
 353
 354
 355
 356
 357
 358
 359
 360
 361
 362
 363
 364
 365
 366
 367
 368
 369
 370
 371
 372
 373
 374
 375
 376
 377
 378
 379
 380
 381
 382
 383
 384
 385
 386
 387
 388
 389
 390
 391
 392
 393
 394
 395
 396
 397
 398
 399
 400
 401
 402
 403
 404
 405
 406
 407
 408
 409
 410
 411
 412
 413
 414
 415
 416
 417
 418
 419
 420
 421
 422
 423
 424
 425
 426
 427
 428
 429
 430
 431
 432
 433
 434
 435
 436
 437
 438
 439
 440
 441
 442
 443
 444
 445
 446
 447
 448
 449
 450
 451
 452
 453
 454
 455
 456
 457
 458
 459
 460
 461
 462
 463
 464
 465
 466
 467
 468
 469
 470
 471
 472
 473
 474
 475
 476
 477
 478
 479
 480
 481
 482
 483
 484
 485
 486
 487
 488
 489
 490
 491
 492
 493
 494
 495
 496
 497
 498
 499
 500
 501
 502
 503
 504
 505
 506
 507
 508
 509
 510
 511
 512
 513
 514
 515
 516
 517
 518
 519
 520
 521
 522
 523
 524
 525
 526
 527
 528
 529
 530
 531
 532
 533
 534
 535
 536
 537
 538
 539
 540
 541
 542
 543
 544
 545
 546
 547
 548
 549
 550
 551
 552
 553
 554
 555
 556
 557
 558
 559
 560
 561
 562
 563
 564
 565
 566
 567
 568
 569
 570
 571
 572
 573
 574
 575
 576
 577
 578
 579
 580
 581
 582
 583
 584
 585
 586
 587
 588
 589
 590
 591
 592
 593
 594
 595
 596
 597
 598
 599
 600
 601
 602
 603
 604
 605
 606
 607
 608
 609
 610
 611
 612
 613
 614
 615
 616
 617
 618
 619
 620
 621
 622
 623
 624
 625
 626
 627
 628
 629
 630
 631
 632
 633
 634
 635
 636
 637
 638
 639
 640
 641
 642
 643
 644
 645
 646
 647
 648
 649
 650
 651
 652
 653
 654
 655
 656
 657
 658
 659
 660
 661
 662
 663
 664
 665
 666
 667
 668
 669
 670
 671
 672
 673
 674
 675
 676
 677
 678
 679
 680
 681
 682
 683
 684
 685
 686
 687
 688
 689
 690
 691
 692
 693
 694
 695
 696
 697
 698
 699
 700
 701
 702
 703
 704
 705
 706
 707
 708
 709
 710
 711
 712
 713
 714
 715
 716
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734
 735
 736
 737
 738
 739
 740
 741
 742
 743
 744
 745
 746
 747
 748
 749
 750
 751
 752
 753
 754
 755
 756
 757
 758
 759
 760
 761
 762
 763
 764
 765
 766
 767
 768
 769
 770
 771
 772
 773
 774
 775
 776
 777
 778
 779
 780
 781
 782
 783
 784
 785
 786
 787
 788
 789
 790
 791
 792
 793
 794
 795
 796
 797
 798
 799
 800
 801
 802
 803
 804
 805
 806
 807
 808
 809
 810
 811
 812
 813
 814
 815
 816
 817
 818
 819
 820
 821
 822
 823
 824
 825
 826
 827
 828
 829
 830
 831
 832
 833
 834
 835
 836
 837
 838
 839
 840
 841
 842
 843
 844
 845
 846
 847
 848
 849
 850
 851
 852
 853
 854
 855
 856
 857
 858
 859
 860
 861
 862
 863
 864
 865
 866
 867
 868
 869
 870
 871
 872
 873
 874
 875
 876
 877
 878
 879
 880
 881
 882
 883
 884
 885
 886
 887
 888
 889
 890
 891
 892
 893
 894
 895
 896
 897
 898
 899
 900
 901
 902
 903
 904
 905
 906
 907
 908
 909
 910
 911
 912
 913
 914
 915
 916
 917
 918
 919
 920
 921
 922
 923
 924
 925
 926
 927
 928
 929
 930
 931
 932
 933
 934
 935
 936
 937
 938
 939
 940
 941
 942
 943
 944
 945
 946
 947
 948
 949
 950
 951
 952
 953
 954
 955
 956
 957
 958
 959
 960
 961
 962
 963
 964
 965
 966
 967
 968
 969
 970
 971
 972
 973
 974
 975
 976
 977
 978
 979
 980
 981
 982
 983
 984
 985
 986
 987
 988
 989
 990
 991
 992
 993
 994
 995
 996
 997
 998
 999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
/*
 * This file is part of UBIFS.
 *
 * Copyright (C) 2006-2008 Nokia Corporation.
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 as published by
 * the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 * more details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program; if not, write to the Free Software Foundation, Inc., 51
 * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 *
 * Authors: Adrian Hunter
 *          Artem Bityutskiy (Битюцкий Артём)
 */

/*
 * This file implements the functions that access LEB properties and their
 * categories. LEBs are categorized based on the needs of UBIFS, and the
 * categories are stored as either heaps or lists to provide a fast way of
 * finding a LEB in a particular category. For example, UBIFS may need to find
 * an empty LEB for the journal, or a very dirty LEB for garbage collection.
 */

#include "ubifs.h"

/**
 * get_heap_comp_val - get the LEB properties value for heap comparisons.
 * @lprops: LEB properties
 * @cat: LEB category
 */
static int get_heap_comp_val(struct ubifs_lprops *lprops, int cat)
{
	switch (cat) {
	case LPROPS_FREE:
		return lprops->free;
	case LPROPS_DIRTY_IDX:
		return lprops->free + lprops->dirty;
	default:
		return lprops->dirty;
	}
}

/**
 * move_up_lpt_heap - move a new heap entry up as far as possible.
 * @c: UBIFS file-system description object
 * @heap: LEB category heap
 * @lprops: LEB properties to move
 * @cat: LEB category
 *
 * New entries to a heap are added at the bottom and then moved up until the
 * parent's value is greater.  In the case of LPT's category heaps, the value
 * is either the amount of free space or the amount of dirty space, depending
 * on the category.
 */
static void move_up_lpt_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap,
			     struct ubifs_lprops *lprops, int cat)
{
	int val1, val2, hpos;

	hpos = lprops->hpos;
	if (!hpos)
		return; /* Already top of the heap */
	val1 = get_heap_comp_val(lprops, cat);
	/* Compare to parent and, if greater, move up the heap */
	do {
		int ppos = (hpos - 1) / 2;

		val2 = get_heap_comp_val(heap->arr[ppos], cat);
		if (val2 >= val1)
			return;
		/* Greater than parent so move up */
		heap->arr[ppos]->hpos = hpos;
		heap->arr[hpos] = heap->arr[ppos];
		heap->arr[ppos] = lprops;
		lprops->hpos = ppos;
		hpos = ppos;
	} while (hpos);
}

/**
 * adjust_lpt_heap - move a changed heap entry up or down the heap.
 * @c: UBIFS file-system description object
 * @heap: LEB category heap
 * @lprops: LEB properties to move
 * @hpos: heap position of @lprops
 * @cat: LEB category
 *
 * Changed entries in a heap are moved up or down until the parent's value is
 * greater.  In the case of LPT's category heaps, the value is either the amount
 * of free space or the amount of dirty space, depending on the category.
 */
static void adjust_lpt_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap,
			    struct ubifs_lprops *lprops, int hpos, int cat)
{
	int val1, val2, val3, cpos;

	val1 = get_heap_comp_val(lprops, cat);
	/* Compare to parent and, if greater than parent, move up the heap */
	if (hpos) {
		int ppos = (hpos - 1) / 2;

		val2 = get_heap_comp_val(heap->arr[ppos], cat);
		if (val1 > val2) {
			/* Greater than parent so move up */
			while (1) {
				heap->arr[ppos]->hpos = hpos;
				heap->arr[hpos] = heap->arr[ppos];
				heap->arr[ppos] = lprops;
				lprops->hpos = ppos;
				hpos = ppos;
				if (!hpos)
					return;
				ppos = (hpos - 1) / 2;
				val2 = get_heap_comp_val(heap->arr[ppos], cat);
				if (val1 <= val2)
					return;
				/* Still greater than parent so keep going */
			}
		}
	}
	/* Not greater than parent, so compare to children */
	while (1) {
		/* Compare to left child */
		cpos = hpos * 2 + 1;
		if (cpos >= heap->cnt)
			return;
		val2 = get_heap_comp_val(heap->arr[cpos], cat);
		if (val1 < val2) {
			/* Less than left child, so promote biggest child */
			if (cpos + 1 < heap->cnt) {
				val3 = get_heap_comp_val(heap->arr[cpos + 1],
							 cat);
				if (val3 > val2)
					cpos += 1; /* Right child is bigger */
			}
			heap->arr[cpos]->hpos = hpos;
			heap->arr[hpos] = heap->arr[cpos];
			heap->arr[cpos] = lprops;
			lprops->hpos = cpos;
			hpos = cpos;
			continue;
		}
		/* Compare to right child */
		cpos += 1;
		if (cpos >= heap->cnt)
			return;
		val3 = get_heap_comp_val(heap->arr[cpos], cat);
		if (val1 < val3) {
			/* Less than right child, so promote right child */
			heap->arr[cpos]->hpos = hpos;
			heap->arr[hpos] = heap->arr[cpos];
			heap->arr[cpos] = lprops;
			lprops->hpos = cpos;
			hpos = cpos;
			continue;
		}
		return;
	}
}

/**
 * add_to_lpt_heap - add LEB properties to a LEB category heap.
 * @c: UBIFS file-system description object
 * @lprops: LEB properties to add
 * @cat: LEB category
 *
 * This function returns %1 if @lprops is added to the heap for LEB category
 * @cat, otherwise %0 is returned because the heap is full.
 */
static int add_to_lpt_heap(struct ubifs_info *c, struct ubifs_lprops *lprops,
			   int cat)
{
	struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];

	if (heap->cnt >= heap->max_cnt) {
		const int b = LPT_HEAP_SZ / 2 - 1;
		int cpos, val1, val2;

		/* Compare to some other LEB on the bottom of heap */
		/* Pick a position kind of randomly */
		cpos = (((size_t)lprops >> 4) & b) + b;
		ubifs_assert(cpos >= b);
		ubifs_assert(cpos < LPT_HEAP_SZ);
		ubifs_assert(cpos < heap->cnt);

		val1 = get_heap_comp_val(lprops, cat);
		val2 = get_heap_comp_val(heap->arr[cpos], cat);
		if (val1 > val2) {
			struct ubifs_lprops *lp;

			lp = heap->arr[cpos];
			lp->flags &= ~LPROPS_CAT_MASK;
			lp->flags |= LPROPS_UNCAT;
			list_add(&lp->list, &c->uncat_list);
			lprops->hpos = cpos;
			heap->arr[cpos] = lprops;
			move_up_lpt_heap(c, heap, lprops, cat);
			dbg_check_heap(c, heap, cat, lprops->hpos);
			return 1; /* Added to heap */
		}
		dbg_check_heap(c, heap, cat, -1);
		return 0; /* Not added to heap */
	} else {
		lprops->hpos = heap->cnt++;
		heap->arr[lprops->hpos] = lprops;
		move_up_lpt_heap(c, heap, lprops, cat);
		dbg_check_heap(c, heap, cat, lprops->hpos);
		return 1; /* Added to heap */
	}
}

/**
 * remove_from_lpt_heap - remove LEB properties from a LEB category heap.
 * @c: UBIFS file-system description object
 * @lprops: LEB properties to remove
 * @cat: LEB category
 */
static void remove_from_lpt_heap(struct ubifs_info *c,
				 struct ubifs_lprops *lprops, int cat)
{
	struct ubifs_lpt_heap *heap;
	int hpos = lprops->hpos;

	heap = &c->lpt_heap[cat - 1];
	ubifs_assert(hpos >= 0 && hpos < heap->cnt);
	ubifs_assert(heap->arr[hpos] == lprops);
	heap->cnt -= 1;
	if (hpos < heap->cnt) {
		heap->arr[hpos] = heap->arr[heap->cnt];
		heap->arr[hpos]->hpos = hpos;
		adjust_lpt_heap(c, heap, heap->arr[hpos], hpos, cat);
	}
	dbg_check_heap(c, heap, cat, -1);
}

/**
 * lpt_heap_replace - replace lprops in a category heap.
 * @c: UBIFS file-system description object
 * @old_lprops: LEB properties to replace
 * @new_lprops: LEB properties with which to replace
 * @cat: LEB category
 *
 * During commit it is sometimes necessary to copy a pnode (see dirty_cow_pnode)
 * and the lprops that the pnode contains.  When that happens, references in
 * the category heaps to those lprops must be updated to point to the new
 * lprops.  This function does that.
 */
static void lpt_heap_replace(struct ubifs_info *c,
			     struct ubifs_lprops *old_lprops,
			     struct ubifs_lprops *new_lprops, int cat)
{
	struct ubifs_lpt_heap *heap;
	int hpos = new_lprops->hpos;

	heap = &c->lpt_heap[cat - 1];
	heap->arr[hpos] = new_lprops;
}

/**
 * ubifs_add_to_cat - add LEB properties to a category list or heap.
 * @c: UBIFS file-system description object
 * @lprops: LEB properties to add
 * @cat: LEB category to which to add
 *
 * LEB properties are categorized to enable fast find operations.
 */
void ubifs_add_to_cat(struct ubifs_info *c, struct ubifs_lprops *lprops,
		      int cat)
{
	switch (cat) {
	case LPROPS_DIRTY:
	case LPROPS_DIRTY_IDX:
	case LPROPS_FREE:
		if (add_to_lpt_heap(c, lprops, cat))
			break;
		/* No more room on heap so make it uncategorized */
		cat = LPROPS_UNCAT;
		/* Fall through */
	case LPROPS_UNCAT:
		list_add(&lprops->list, &c->uncat_list);
		break;
	case LPROPS_EMPTY:
		list_add(&lprops->list, &c->empty_list);
		break;
	case LPROPS_FREEABLE:
		list_add(&lprops->list, &c->freeable_list);
		c->freeable_cnt += 1;
		break;
	case LPROPS_FRDI_IDX:
		list_add(&lprops->list, &c->frdi_idx_list);
		break;
	default:
		ubifs_assert(0);
	}
	lprops->flags &= ~LPROPS_CAT_MASK;
	lprops->flags |= cat;
}

/**
 * ubifs_remove_from_cat - remove LEB properties from a category list or heap.
 * @c: UBIFS file-system description object
 * @lprops: LEB properties to remove
 * @cat: LEB category from which to remove
 *
 * LEB properties are categorized to enable fast find operations.
 */
static void ubifs_remove_from_cat(struct ubifs_info *c,
				  struct ubifs_lprops *lprops, int cat)
{
	switch (cat) {
	case LPROPS_DIRTY:
	case LPROPS_DIRTY_IDX:
	case LPROPS_FREE:
		remove_from_lpt_heap(c, lprops, cat);
		break;
	case LPROPS_FREEABLE:
		c->freeable_cnt -= 1;
		ubifs_assert(c->freeable_cnt >= 0);
		/* Fall through */
	case LPROPS_UNCAT:
	case LPROPS_EMPTY:
	case LPROPS_FRDI_IDX:
		ubifs_assert(!list_empty(&lprops->list));
		list_del(&lprops->list);
		break;
	default:
		ubifs_assert(0);
	}
}

/**
 * ubifs_replace_cat - replace lprops in a category list or heap.
 * @c: UBIFS file-system description object
 * @old_lprops: LEB properties to replace
 * @new_lprops: LEB properties with which to replace
 *
 * During commit it is sometimes necessary to copy a pnode (see dirty_cow_pnode)
 * and the lprops that the pnode contains. When that happens, references in
 * category lists and heaps must be replaced. This function does that.
 */
void ubifs_replace_cat(struct ubifs_info *c, struct ubifs_lprops *old_lprops,
		       struct ubifs_lprops *new_lprops)
{
	int cat;

	cat = new_lprops->flags & LPROPS_CAT_MASK;
	switch (cat) {
	case LPROPS_DIRTY:
	case LPROPS_DIRTY_IDX:
	case LPROPS_FREE:
		lpt_heap_replace(c, old_lprops, new_lprops, cat);
		break;
	case LPROPS_UNCAT:
	case LPROPS_EMPTY:
	case LPROPS_FREEABLE:
	case LPROPS_FRDI_IDX:
		list_replace(&old_lprops->list, &new_lprops->list);
		break;
	default:
		ubifs_assert(0);
	}
}

/**
 * ubifs_ensure_cat - ensure LEB properties are categorized.
 * @c: UBIFS file-system description object
 * @lprops: LEB properties
 *
 * A LEB may have fallen off of the bottom of a heap, and ended up as
 * uncategorized even though it has enough space for us now. If that is the case
 * this function will put the LEB back onto a heap.
 */
void ubifs_ensure_cat(struct ubifs_info *c, struct ubifs_lprops *lprops)
{
	int cat = lprops->flags & LPROPS_CAT_MASK;

	if (cat != LPROPS_UNCAT)
		return;
	cat = ubifs_categorize_lprops(c, lprops);
	if (cat == LPROPS_UNCAT)
		return;
	ubifs_remove_from_cat(c, lprops, LPROPS_UNCAT);
	ubifs_add_to_cat(c, lprops, cat);
}

/**
 * ubifs_categorize_lprops - categorize LEB properties.
 * @c: UBIFS file-system description object
 * @lprops: LEB properties to categorize
 *
 * LEB properties are categorized to enable fast find operations. This function
 * returns the LEB category to which the LEB properties belong. Note however
 * that if the LEB category is stored as a heap and the heap is full, the
 * LEB properties may have their category changed to %LPROPS_UNCAT.
 */
int ubifs_categorize_lprops(const struct ubifs_info *c,
			    const struct ubifs_lprops *lprops)
{
	if (lprops->flags & LPROPS_TAKEN)
		return LPROPS_UNCAT;

	if (lprops->free == c->leb_size) {
		ubifs_assert(!(lprops->flags & LPROPS_INDEX));
		return LPROPS_EMPTY;
	}

	if (lprops->free + lprops->dirty == c->leb_size) {
		if (lprops->flags & LPROPS_INDEX)
			return LPROPS_FRDI_IDX;
		else
			return LPROPS_FREEABLE;
	}

	if (lprops->flags & LPROPS_INDEX) {
		if (lprops->dirty + lprops->free >= c->min_idx_node_sz)
			return LPROPS_DIRTY_IDX;
	} else {
		if (lprops->dirty >= c->dead_wm &&
		    lprops->dirty > lprops->free)
			return LPROPS_DIRTY;
		if (lprops->free > 0)
			return LPROPS_FREE;
	}

	return LPROPS_UNCAT;
}

/**
 * change_category - change LEB properties category.
 * @c: UBIFS file-system description object
 * @lprops: LEB properties to recategorize
 *
 * LEB properties are categorized to enable fast find operations. When the LEB
 * properties change they must be recategorized.
 */
static void change_category(struct ubifs_info *c, struct ubifs_lprops *lprops)
{
	int old_cat = lprops->flags & LPROPS_CAT_MASK;
	int new_cat = ubifs_categorize_lprops(c, lprops);

	if (old_cat == new_cat) {
		struct ubifs_lpt_heap *heap = &c->lpt_heap[new_cat - 1];

		/* lprops on a heap now must be moved up or down */
		if (new_cat < 1 || new_cat > LPROPS_HEAP_CNT)
			return; /* Not on a heap */
		heap = &c->lpt_heap[new_cat - 1];
		adjust_lpt_heap(c, heap, lprops, lprops->hpos, new_cat);
	} else {
		ubifs_remove_from_cat(c, lprops, old_cat);
		ubifs_add_to_cat(c, lprops, new_cat);
	}
}

/**
 * ubifs_get_lprops - get reference to LEB properties.
 * @c: the UBIFS file-system description object
 *
 * This function locks lprops. Lprops have to be unlocked by
 * 'ubifs_release_lprops()'.
 */
void ubifs_get_lprops(struct ubifs_info *c)
{
	mutex_lock(&c->lp_mutex);
}

/**
 * calc_dark - calculate LEB dark space size.
 * @c: the UBIFS file-system description object
 * @spc: amount of free and dirty space in the LEB
 *
 * This function calculates amount of dark space in an LEB which has @spc bytes
 * of free and dirty space. Returns the calculations result.
 *
 * Dark space is the space which is not always usable - it depends on which
 * nodes are written in which order. E.g., if an LEB has only 512 free bytes,
 * it is dark space, because it cannot fit a large data node. So UBIFS cannot
 * count on this LEB and treat these 512 bytes as usable because it is not true
 * if, for example, only big chunks of uncompressible data will be written to
 * the FS.
 */
static int calc_dark(struct ubifs_info *c, int spc)
{
	ubifs_assert(!(spc & 7));

	if (spc < c->dark_wm)
		return spc;

	/*
	 * If we have slightly more space then the dark space watermark, we can
	 * anyway safely assume it we'll be able to write a node of the
	 * smallest size there.
	 */
	if (spc - c->dark_wm < MIN_WRITE_SZ)
		return spc - MIN_WRITE_SZ;

	return c->dark_wm;
}

/**
 * is_lprops_dirty - determine if LEB properties are dirty.
 * @c: the UBIFS file-system description object
 * @lprops: LEB properties to test
 */
static int is_lprops_dirty(struct ubifs_info *c, struct ubifs_lprops *lprops)
{
	struct ubifs_pnode *pnode;
	int pos;

	pos = (lprops->lnum - c->main_first) & (UBIFS_LPT_FANOUT - 1);
	pnode = (struct ubifs_pnode *)container_of(lprops - pos,
						   struct ubifs_pnode,
						   lprops[0]);
	return !test_bit(COW_ZNODE, &pnode->flags) &&
	       test_bit(DIRTY_CNODE, &pnode->flags);
}

/**
 * ubifs_change_lp - change LEB properties.
 * @c: the UBIFS file-system description object
 * @lp: LEB properties to change
 * @free: new free space amount
 * @dirty: new dirty space amount
 * @flags: new flags
 * @idx_gc_cnt: change to the count of idx_gc list
 *
 * This function changes LEB properties. This function does not change a LEB
 * property (@free, @dirty or @flag) if the value passed is %LPROPS_NC.
 *
 * This function returns a pointer to the updated LEB properties on success
 * and a negative error code on failure. N.B. the LEB properties may have had to
 * be copied (due to COW) and consequently the pointer returned may not be the
 * same as the pointer passed.
 */
const struct ubifs_lprops *ubifs_change_lp(struct ubifs_info *c,
					   const struct ubifs_lprops *lp,
					   int free, int dirty, int flags,
					   int idx_gc_cnt)
{
	/*
	 * This is the only function that is allowed to change lprops, so we
	 * discard the const qualifier.
	 */
	struct ubifs_lprops *lprops = (struct ubifs_lprops *)lp;

	dbg_lp("LEB %d, free %d, dirty %d, flags %d",
	       lprops->lnum, free, dirty, flags);

	ubifs_assert(mutex_is_locked(&c->lp_mutex));
	ubifs_assert(c->lst.empty_lebs >= 0 &&
		     c->lst.empty_lebs <= c->main_lebs);
	ubifs_assert(c->freeable_cnt >= 0);
	ubifs_assert(c->freeable_cnt <= c->main_lebs);
	ubifs_assert(c->lst.taken_empty_lebs >= 0);
	ubifs_assert(c->lst.taken_empty_lebs <= c->lst.empty_lebs);
	ubifs_assert(!(c->lst.total_free & 7) && !(c->lst.total_dirty & 7));
	ubifs_assert(!(c->lst.total_dead & 7) && !(c->lst.total_dark & 7));
	ubifs_assert(!(c->lst.total_used & 7));
	ubifs_assert(free == LPROPS_NC || free >= 0);
	ubifs_assert(dirty == LPROPS_NC || dirty >= 0);

	if (!is_lprops_dirty(c, lprops)) {
		lprops = ubifs_lpt_lookup_dirty(c, lprops->lnum);
		if (IS_ERR(lprops))
			return lprops;
	} else
		ubifs_assert(lprops == ubifs_lpt_lookup_dirty(c, lprops->lnum));

	ubifs_assert(!(lprops->free & 7) && !(lprops->dirty & 7));

	spin_lock(&c->space_lock);

	if ((lprops->flags & LPROPS_TAKEN) && lprops->free == c->leb_size)
		c->lst.taken_empty_lebs -= 1;

	if (!(lprops->flags & LPROPS_INDEX)) {
		int old_spc;

		old_spc = lprops->free + lprops->dirty;
		if (old_spc < c->dead_wm)
			c->lst.total_dead -= old_spc;
		else
			c->lst.total_dark -= calc_dark(c, old_spc);

		c->lst.total_used -= c->leb_size - old_spc;
	}

	if (free != LPROPS_NC) {
		free = ALIGN(free, 8);
		c->lst.total_free += free - lprops->free;

		/* Increase or decrease empty LEBs counter if needed */
		if (free == c->leb_size) {
			if (lprops->free != c->leb_size)
				c->lst.empty_lebs += 1;
		} else if (lprops->free == c->leb_size)
			c->lst.empty_lebs -= 1;
		lprops->free = free;
	}

	if (dirty != LPROPS_NC) {
		dirty = ALIGN(dirty, 8);
		c->lst.total_dirty += dirty - lprops->dirty;
		lprops->dirty = dirty;
	}

	if (flags != LPROPS_NC) {
		/* Take care about indexing LEBs counter if needed */
		if ((lprops->flags & LPROPS_INDEX)) {
			if (!(flags & LPROPS_INDEX))
				c->lst.idx_lebs -= 1;
		} else if (flags & LPROPS_INDEX)
			c->lst.idx_lebs += 1;
		lprops->flags = flags;
	}

	if (!(lprops->flags & LPROPS_INDEX)) {
		int new_spc;

		new_spc = lprops->free + lprops->dirty;
		if (new_spc < c->dead_wm)
			c->lst.total_dead += new_spc;
		else
			c->lst.total_dark += calc_dark(c, new_spc);

		c->lst.total_used += c->leb_size - new_spc;
	}

	if ((lprops->flags & LPROPS_TAKEN) && lprops->free == c->leb_size)
		c->lst.taken_empty_lebs += 1;

	change_category(c, lprops);

	c->idx_gc_cnt += idx_gc_cnt;

	spin_unlock(&c->space_lock);

	return lprops;
}

/**
 * ubifs_release_lprops - release lprops lock.
 * @c: the UBIFS file-system description object
 *
 * This function has to be called after each 'ubifs_get_lprops()' call to
 * unlock lprops.
 */
void ubifs_release_lprops(struct ubifs_info *c)
{
	ubifs_assert(mutex_is_locked(&c->lp_mutex));
	ubifs_assert(c->lst.empty_lebs >= 0 &&
		     c->lst.empty_lebs <= c->main_lebs);

	mutex_unlock(&c->lp_mutex);
}

/**
 * ubifs_get_lp_stats - get lprops statistics.
 * @c: UBIFS file-system description object
 * @st: return statistics
 */
void ubifs_get_lp_stats(struct ubifs_info *c, struct ubifs_lp_stats *st)
{
	spin_lock(&c->space_lock);
	memcpy(st, &c->lst, sizeof(struct ubifs_lp_stats));
	spin_unlock(&c->space_lock);
}

/**
 * ubifs_change_one_lp - change LEB properties.
 * @c: the UBIFS file-system description object
 * @lnum: LEB to change properties for
 * @free: amount of free space
 * @dirty: amount of dirty space
 * @flags_set: flags to set
 * @flags_clean: flags to clean
 * @idx_gc_cnt: change to the count of idx_gc list
 *
 * This function changes properties of LEB @lnum. It is a helper wrapper over
 * 'ubifs_change_lp()' which hides lprops get/release. The arguments are the
 * same as in case of 'ubifs_change_lp()'. Returns zero in case of success and
 * a negative error code in case of failure.
 */
int ubifs_change_one_lp(struct ubifs_info *c, int lnum, int free, int dirty,
			int flags_set, int flags_clean, int idx_gc_cnt)
{
	int err = 0, flags;
	const struct ubifs_lprops *lp;

	ubifs_get_lprops(c);

	lp = ubifs_lpt_lookup_dirty(c, lnum);
	if (IS_ERR(lp)) {
		err = PTR_ERR(lp);
		goto out;
	}

	flags = (lp->flags | flags_set) & ~flags_clean;
	lp = ubifs_change_lp(c, lp, free, dirty, flags, idx_gc_cnt);
	if (IS_ERR(lp))
		err = PTR_ERR(lp);

out:
	ubifs_release_lprops(c);
	return err;
}

/**
 * ubifs_update_one_lp - update LEB properties.
 * @c: the UBIFS file-system description object
 * @lnum: LEB to change properties for
 * @free: amount of free space
 * @dirty: amount of dirty space to add
 * @flags_set: flags to set
 * @flags_clean: flags to clean
 *
 * This function is the same as 'ubifs_change_one_lp()' but @dirty is added to
 * current dirty space, not substitutes it.
 */
int ubifs_update_one_lp(struct ubifs_info *c, int lnum, int free, int dirty,
			int flags_set, int flags_clean)
{
	int err = 0, flags;
	const struct ubifs_lprops *lp;

	ubifs_get_lprops(c);

	lp = ubifs_lpt_lookup_dirty(c, lnum);
	if (IS_ERR(lp)) {
		err = PTR_ERR(lp);
		goto out;
	}

	flags = (lp->flags | flags_set) & ~flags_clean;
	lp = ubifs_change_lp(c, lp, free, lp->dirty + dirty, flags, 0);
	if (IS_ERR(lp))
		err = PTR_ERR(lp);

out:
	ubifs_release_lprops(c);
	return err;
}

/**
 * ubifs_read_one_lp - read LEB properties.
 * @c: the UBIFS file-system description object
 * @lnum: LEB to read properties for
 * @lp: where to store read properties
 *
 * This helper function reads properties of a LEB @lnum and stores them in @lp.
 * Returns zero in case of success and a negative error code in case of
 * failure.
 */
int ubifs_read_one_lp(struct ubifs_info *c, int lnum, struct ubifs_lprops *lp)
{
	int err = 0;
	const struct ubifs_lprops *lpp;

	ubifs_get_lprops(c);

	lpp = ubifs_lpt_lookup(c, lnum);
	if (IS_ERR(lpp)) {
		err = PTR_ERR(lpp);
		goto out;
	}

	memcpy(lp, lpp, sizeof(struct ubifs_lprops));

out:
	ubifs_release_lprops(c);
	return err;
}

/**
 * ubifs_fast_find_free - try to find a LEB with free space quickly.
 * @c: the UBIFS file-system description object
 *
 * This function returns LEB properties for a LEB with free space or %NULL if
 * the function is unable to find a LEB quickly.
 */
const struct ubifs_lprops *ubifs_fast_find_free(struct ubifs_info *c)
{
	struct ubifs_lprops *lprops;
	struct ubifs_lpt_heap *heap;

	ubifs_assert(mutex_is_locked(&c->lp_mutex));

	heap = &c->lpt_heap[LPROPS_FREE - 1];
	if (heap->cnt == 0)
		return NULL;

	lprops = heap->arr[0];
	ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
	ubifs_assert(!(lprops->flags & LPROPS_INDEX));
	return lprops;
}

/**
 * ubifs_fast_find_empty - try to find an empty LEB quickly.
 * @c: the UBIFS file-system description object
 *
 * This function returns LEB properties for an empty LEB or %NULL if the
 * function is unable to find an empty LEB quickly.
 */
const struct ubifs_lprops *ubifs_fast_find_empty(struct ubifs_info *c)
{
	struct ubifs_lprops *lprops;

	ubifs_assert(mutex_is_locked(&c->lp_mutex));

	if (list_empty(&c->empty_list))
		return NULL;

	lprops = list_entry(c->empty_list.next, struct ubifs_lprops, list);
	ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
	ubifs_assert(!(lprops->flags & LPROPS_INDEX));
	ubifs_assert(lprops->free == c->leb_size);
	return lprops;
}

/**
 * ubifs_fast_find_freeable - try to find a freeable LEB quickly.
 * @c: the UBIFS file-system description object
 *
 * This function returns LEB properties for a freeable LEB or %NULL if the
 * function is unable to find a freeable LEB quickly.
 */
const struct ubifs_lprops *ubifs_fast_find_freeable(struct ubifs_info *c)
{
	struct ubifs_lprops *lprops;

	ubifs_assert(mutex_is_locked(&c->lp_mutex));

	if (list_empty(&c->freeable_list))
		return NULL;

	lprops = list_entry(c->freeable_list.next, struct ubifs_lprops, list);
	ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
	ubifs_assert(!(lprops->flags & LPROPS_INDEX));
	ubifs_assert(lprops->free + lprops->dirty == c->leb_size);
	ubifs_assert(c->freeable_cnt > 0);
	return lprops;
}

/**
 * ubifs_fast_find_frdi_idx - try to find a freeable index LEB quickly.
 * @c: the UBIFS file-system description object
 *
 * This function returns LEB properties for a freeable index LEB or %NULL if the
 * function is unable to find a freeable index LEB quickly.
 */
const struct ubifs_lprops *ubifs_fast_find_frdi_idx(struct ubifs_info *c)
{
	struct ubifs_lprops *lprops;

	ubifs_assert(mutex_is_locked(&c->lp_mutex));

	if (list_empty(&c->frdi_idx_list))
		return NULL;

	lprops = list_entry(c->frdi_idx_list.next, struct ubifs_lprops, list);
	ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
	ubifs_assert((lprops->flags & LPROPS_INDEX));
	ubifs_assert(lprops->free + lprops->dirty == c->leb_size);
	return lprops;
}

#ifdef CONFIG_UBIFS_FS_DEBUG

/**
 * dbg_check_cats - check category heaps and lists.
 * @c: UBIFS file-system description object
 *
 * This function returns %0 on success and a negative error code on failure.
 */
int dbg_check_cats(struct ubifs_info *c)
{
	struct ubifs_lprops *lprops;
	struct list_head *pos;
	int i, cat;

	if (!(ubifs_chk_flags & (UBIFS_CHK_GEN | UBIFS_CHK_LPROPS)))
		return 0;

	list_for_each_entry(lprops, &c->empty_list, list) {
		if (lprops->free != c->leb_size) {
			ubifs_err("non-empty LEB %d on empty list "
				  "(free %d dirty %d flags %d)", lprops->lnum,
				  lprops->free, lprops->dirty, lprops->flags);
			return -EINVAL;
		}
		if (lprops->flags & LPROPS_TAKEN) {
			ubifs_err("taken LEB %d on empty list "
				  "(free %d dirty %d flags %d)", lprops->lnum,
				  lprops->free, lprops->dirty, lprops->flags);
			return -EINVAL;
		}
	}

	i = 0;
	list_for_each_entry(lprops, &c->freeable_list, list) {
		if (lprops->free + lprops->dirty != c->leb_size) {
			ubifs_err("non-freeable LEB %d on freeable list "
				  "(free %d dirty %d flags %d)", lprops->lnum,
				  lprops->free, lprops->dirty, lprops->flags);
			return -EINVAL;
		}
		if (lprops->flags & LPROPS_TAKEN) {
			ubifs_err("taken LEB %d on freeable list "
				  "(free %d dirty %d flags %d)", lprops->lnum,
				  lprops->free, lprops->dirty, lprops->flags);
			return -EINVAL;
		}
		i += 1;
	}
	if (i != c->freeable_cnt) {
		ubifs_err("freeable list count %d expected %d", i,
			  c->freeable_cnt);
		return -EINVAL;
	}

	i = 0;
	list_for_each(pos, &c->idx_gc)
		i += 1;
	if (i != c->idx_gc_cnt) {
		ubifs_err("idx_gc list count %d expected %d", i,
			  c->idx_gc_cnt);
		return -EINVAL;
	}

	list_for_each_entry(lprops, &c->frdi_idx_list, list) {
		if (lprops->free + lprops->dirty != c->leb_size) {
			ubifs_err("non-freeable LEB %d on frdi_idx list "
				  "(free %d dirty %d flags %d)", lprops->lnum,
				  lprops->free, lprops->dirty, lprops->flags);
			return -EINVAL;
		}
		if (lprops->flags & LPROPS_TAKEN) {
			ubifs_err("taken LEB %d on frdi_idx list "
				  "(free %d dirty %d flags %d)", lprops->lnum,
				  lprops->free, lprops->dirty, lprops->flags);
			return -EINVAL;
		}
		if (!(lprops->flags & LPROPS_INDEX)) {
			ubifs_err("non-index LEB %d on frdi_idx list "
				  "(free %d dirty %d flags %d)", lprops->lnum,
				  lprops->free, lprops->dirty, lprops->flags);
			return -EINVAL;
		}
	}

	for (cat = 1; cat <= LPROPS_HEAP_CNT; cat++) {
		struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];

		for (i = 0; i < heap->cnt; i++) {
			lprops = heap->arr[i];
			if (!lprops) {
				ubifs_err("null ptr in LPT heap cat %d", cat);
				return -EINVAL;
			}
			if (lprops->hpos != i) {
				ubifs_err("bad ptr in LPT heap cat %d", cat);
				return -EINVAL;
			}
			if (lprops->flags & LPROPS_TAKEN) {
				ubifs_err("taken LEB in LPT heap cat %d", cat);
				return -EINVAL;
			}
		}
	}

	return 0;
}

void dbg_check_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap, int cat,
		    int add_pos)
{
	int i = 0, j, err = 0;

	if (!(ubifs_chk_flags & (UBIFS_CHK_GEN | UBIFS_CHK_LPROPS)))
		return;

	for (i = 0; i < heap->cnt; i++) {
		struct ubifs_lprops *lprops = heap->arr[i];
		struct ubifs_lprops *lp;

		if (i != add_pos)
			if ((lprops->flags & LPROPS_CAT_MASK) != cat) {
				err = 1;
				goto out;
			}
		if (lprops->hpos != i) {
			err = 2;
			goto out;
		}
		lp = ubifs_lpt_lookup(c, lprops->lnum);
		if (IS_ERR(lp)) {
			err = 3;
			goto out;
		}
		if (lprops != lp) {
			dbg_msg("lprops %zx lp %zx lprops->lnum %d lp->lnum %d",
				(size_t)lprops, (size_t)lp, lprops->lnum,
				lp->lnum);
			err = 4;
			goto out;
		}
		for (j = 0; j < i; j++) {
			lp = heap->arr[j];
			if (lp == lprops) {
				err = 5;
				goto out;
			}
			if (lp->lnum == lprops->lnum) {
				err = 6;
				goto out;
			}
		}
	}
out:
	if (err) {
		dbg_msg("failed cat %d hpos %d err %d", cat, i, err);
		dbg_dump_stack();
		dbg_dump_heap(c, heap, cat);
	}
}

/**
 * struct scan_check_data - data provided to scan callback function.
 * @lst: LEB properties statistics
 * @err: error code
 */
struct scan_check_data {
	struct ubifs_lp_stats lst;
	int err;
};

/**
 * scan_check_cb - scan callback.
 * @c: the UBIFS file-system description object
 * @lp: LEB properties to scan
 * @in_tree: whether the LEB properties are in main memory
 * @data: information passed to and from the caller of the scan
 *
 * This function returns a code that indicates whether the scan should continue
 * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
 * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
 * (%LPT_SCAN_STOP).
 */
static int scan_check_cb(struct ubifs_info *c,
			 const struct ubifs_lprops *lp, int in_tree,
			 struct scan_check_data *data)
{
	struct ubifs_scan_leb *sleb;
	struct ubifs_scan_node *snod;
	struct ubifs_lp_stats *lst = &data->lst;
	int cat, lnum = lp->lnum, is_idx = 0, used = 0, free, dirty;

	cat = lp->flags & LPROPS_CAT_MASK;
	if (cat != LPROPS_UNCAT) {
		cat = ubifs_categorize_lprops(c, lp);
		if (cat != (lp->flags & LPROPS_CAT_MASK)) {
			ubifs_err("bad LEB category %d expected %d",
				  (lp->flags & LPROPS_CAT_MASK), cat);
			goto out;
		}
	}

	/* Check lp is on its category list (if it has one) */
	if (in_tree) {
		struct list_head *list = NULL;

		switch (cat) {
		case LPROPS_EMPTY:
			list = &c->empty_list;
			break;
		case LPROPS_FREEABLE:
			list = &c->freeable_list;
			break;
		case LPROPS_FRDI_IDX:
			list = &c->frdi_idx_list;
			break;
		case LPROPS_UNCAT:
			list = &c->uncat_list;
			break;
		}
		if (list) {
			struct ubifs_lprops *lprops;
			int found = 0;

			list_for_each_entry(lprops, list, list) {
				if (lprops == lp) {
					found = 1;
					break;
				}
			}
			if (!found) {
				ubifs_err("bad LPT list (category %d)", cat);
				goto out;
			}
		}
	}

	/* Check lp is on its category heap (if it has one) */
	if (in_tree && cat > 0 && cat <= LPROPS_HEAP_CNT) {
		struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];

		if ((lp->hpos != -1 && heap->arr[lp->hpos]->lnum != lnum) ||
		    lp != heap->arr[lp->hpos]) {
			ubifs_err("bad LPT heap (category %d)", cat);
			goto out;
		}
	}

	sleb = ubifs_scan(c, lnum, 0, c->dbg_buf);
	if (IS_ERR(sleb)) {
		/*
		 * After an unclean unmount, empty and freeable LEBs
		 * may contain garbage.
		 */
		if (lp->free == c->leb_size) {
			ubifs_err("scan errors were in empty LEB "
				  "- continuing checking");
			lst->empty_lebs += 1;
			lst->total_free += c->leb_size;
			lst->total_dark += calc_dark(c, c->leb_size);
			return LPT_SCAN_CONTINUE;
		}

		if (lp->free + lp->dirty == c->leb_size &&
		    !(lp->flags & LPROPS_INDEX)) {
			ubifs_err("scan errors were in freeable LEB "
				  "- continuing checking");
			lst->total_free  += lp->free;
			lst->total_dirty += lp->dirty;
			lst->total_dark  +=  calc_dark(c, c->leb_size);
			return LPT_SCAN_CONTINUE;
		}
		data->err = PTR_ERR(sleb);
		return LPT_SCAN_STOP;
	}

	is_idx = -1;
	list_for_each_entry(snod, &sleb->nodes, list) {
		int found, level = 0;

		cond_resched();

		if (is_idx == -1)
			is_idx = (snod->type == UBIFS_IDX_NODE) ? 1 : 0;

		if (is_idx && snod->type != UBIFS_IDX_NODE) {
			ubifs_err("indexing node in data LEB %d:%d",
				  lnum, snod->offs);
			goto out_destroy;
		}

		if (snod->type == UBIFS_IDX_NODE) {
			struct ubifs_idx_node *idx = snod->node;

			key_read(c, ubifs_idx_key(c, idx), &snod->key);
			level = le16_to_cpu(idx->level);
		}

		found = ubifs_tnc_has_node(c, &snod->key, level, lnum,
					   snod->offs, is_idx);
		if (found) {
			if (found < 0)
				goto out_destroy;
			used += ALIGN(snod->len, 8);
		}
	}

	free = c->leb_size - sleb->endpt;
	dirty = sleb->endpt - used;

	if (free > c->leb_size || free < 0 || dirty > c->leb_size ||
	    dirty < 0) {
		ubifs_err("bad calculated accounting for LEB %d: "
			  "free %d, dirty %d", lnum, free, dirty);
		goto out_destroy;
	}

	if (lp->free + lp->dirty == c->leb_size &&
	    free + dirty == c->leb_size)
		if ((is_idx && !(lp->flags & LPROPS_INDEX)) ||
		    (!is_idx && free == c->leb_size) ||
		    lp->free == c->leb_size) {
			/*
			 * Empty or freeable LEBs could contain index
			 * nodes from an uncompleted commit due to an
			 * unclean unmount. Or they could be empty for
			 * the same reason. Or it may simply not have been
			 * unmapped.
			 */
			free = lp->free;
			dirty = lp->dirty;
			is_idx = 0;
		    }

	if (is_idx && lp->free + lp->dirty == free + dirty &&
	    lnum != c->ihead_lnum) {
		/*
		 * After an unclean unmount, an index LEB could have a different
		 * amount of free space than the value recorded by lprops. That
		 * is because the in-the-gaps method may use free space or
		 * create free space (as a side-effect of using ubi_leb_change
		 * and not writing the whole LEB). The incorrect free space
		 * value is not a problem because the index is only ever
		 * allocated empty LEBs, so there will never be an attempt to
		 * write to the free space at the end of an index LEB - except
		 * by the in-the-gaps method for which it is not a problem.
		 */
		free = lp->free;
		dirty = lp->dirty;
	}

	if (lp->free != free || lp->dirty != dirty)
		goto out_print;

	if (is_idx && !(lp->flags & LPROPS_INDEX)) {
		if (free == c->leb_size)
			/* Free but not unmapped LEB, it's fine */
			is_idx = 0;
		else {
			ubifs_err("indexing node without indexing "
				  "flag");
			goto out_print;
		}
	}

	if (!is_idx && (lp->flags & LPROPS_INDEX)) {
		ubifs_err("data node with indexing flag");
		goto out_print;
	}

	if (free == c->leb_size)
		lst->empty_lebs += 1;

	if (is_idx)
		lst->idx_lebs += 1;

	if (!(lp->flags & LPROPS_INDEX))
		lst->total_used += c->leb_size - free - dirty;
	lst->total_free += free;
	lst->total_dirty += dirty;

	if (!(lp->flags & LPROPS_INDEX)) {
		int spc = free + dirty;

		if (spc < c->dead_wm)
			lst->total_dead += spc;
		else
			lst->total_dark += calc_dark(c, spc);
	}

	ubifs_scan_destroy(sleb);

	return LPT_SCAN_CONTINUE;

out_print:
	ubifs_err("bad accounting of LEB %d: free %d, dirty %d flags %#x, "
		  "should be free %d, dirty %d",
		  lnum, lp->free, lp->dirty, lp->flags, free, dirty);
	dbg_dump_leb(c, lnum);
out_destroy:
	ubifs_scan_destroy(sleb);
out:
	data->err = -EINVAL;
	return LPT_SCAN_STOP;
}

/**
 * dbg_check_lprops - check all LEB properties.
 * @c: UBIFS file-system description object
 *
 * This function checks all LEB properties and makes sure they are all correct.
 * It returns zero if everything is fine, %-EINVAL if there is an inconsistency
 * and other negative error codes in case of other errors. This function is
 * called while the file system is locked (because of commit start), so no
 * additional locking is required. Note that locking the LPT mutex would cause
 * a circular lock dependency with the TNC mutex.
 */
int dbg_check_lprops(struct ubifs_info *c)
{
	int i, err;
	struct scan_check_data data;
	struct ubifs_lp_stats *lst = &data.lst;

	if (!(ubifs_chk_flags & UBIFS_CHK_LPROPS))
		return 0;

	/*
	 * As we are going to scan the media, the write buffers have to be
	 * synchronized.
	 */
	for (i = 0; i < c->jhead_cnt; i++) {
		err = ubifs_wbuf_sync(&c->jheads[i].wbuf);
		if (err)
			return err;
	}

	memset(lst, 0, sizeof(struct ubifs_lp_stats));

	data.err = 0;
	err = ubifs_lpt_scan_nolock(c, c->main_first, c->leb_cnt - 1,
				    (ubifs_lpt_scan_callback)scan_check_cb,
				    &data);
	if (err && err != -ENOSPC)
		goto out;
	if (data.err) {
		err = data.err;
		goto out;
	}

	if (lst->empty_lebs != c->lst.empty_lebs ||
	    lst->idx_lebs != c->lst.idx_lebs ||
	    lst->total_free != c->lst.total_free ||
	    lst->total_dirty != c->lst.total_dirty ||
	    lst->total_used != c->lst.total_used) {
		ubifs_err("bad overall accounting");
		ubifs_err("calculated: empty_lebs %d, idx_lebs %d, "
			  "total_free %lld, total_dirty %lld, total_used %lld",
			  lst->empty_lebs, lst->idx_lebs, lst->total_free,
			  lst->total_dirty, lst->total_used);
		ubifs_err("read from lprops: empty_lebs %d, idx_lebs %d, "
			  "total_free %lld, total_dirty %lld, total_used %lld",
			  c->lst.empty_lebs, c->lst.idx_lebs, c->lst.total_free,
			  c->lst.total_dirty, c->lst.total_used);
		err = -EINVAL;
		goto out;
	}

	if (lst->total_dead != c->lst.total_dead ||
	    lst->total_dark != c->lst.total_dark) {
		ubifs_err("bad dead/dark space accounting");
		ubifs_err("calculated: total_dead %lld, total_dark %lld",
			  lst->total_dead, lst->total_dark);
		ubifs_err("read from lprops: total_dead %lld, total_dark %lld",
			  c->lst.total_dead, c->lst.total_dark);
		err = -EINVAL;
		goto out;
	}

	err = dbg_check_cats(c);
out:
	return err;
}

#endif /* CONFIG_UBIFS_FS_DEBUG */