62 static void move_up_lpt_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap,  in move_up_lpt_heap()  argument
99 static void adjust_lpt_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap,  in adjust_lpt_heap()  argument
178 static int add_to_lpt_heap(struct ubifs_info *c, struct ubifs_lprops *lprops,  in add_to_lpt_heap()  argument
181 	struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];  in add_to_lpt_heap()
202 			list_add(&lp->list, &c->uncat_list);  in add_to_lpt_heap()
205 			move_up_lpt_heap(c, heap, lprops, cat);  in add_to_lpt_heap()
206 			dbg_check_heap(c, heap, cat, lprops->hpos);  in add_to_lpt_heap()
209 		dbg_check_heap(c, heap, cat, -1);  in add_to_lpt_heap()
214 		move_up_lpt_heap(c, heap, lprops, cat);  in add_to_lpt_heap()
215 		dbg_check_heap(c, heap, cat, lprops->hpos);  in add_to_lpt_heap()
226 static void remove_from_lpt_heap(struct ubifs_info *c,  in remove_from_lpt_heap()  argument
232 	heap = &c->lpt_heap[cat - 1];  in remove_from_lpt_heap()
239 		adjust_lpt_heap(c, heap, heap->arr[hpos], hpos, cat);  in remove_from_lpt_heap()
241 	dbg_check_heap(c, heap, cat, -1);  in remove_from_lpt_heap()
256 static void lpt_heap_replace(struct ubifs_info *c,  in lpt_heap_replace()  argument
263 	heap = &c->lpt_heap[cat - 1];  in lpt_heap_replace()
275 void ubifs_add_to_cat(struct ubifs_info *c, struct ubifs_lprops *lprops,  in ubifs_add_to_cat()  argument
282 		if (add_to_lpt_heap(c, lprops, cat))  in ubifs_add_to_cat()
288 		list_add(&lprops->list, &c->uncat_list);  in ubifs_add_to_cat()
291 		list_add(&lprops->list, &c->empty_list);  in ubifs_add_to_cat()
294 		list_add(&lprops->list, &c->freeable_list);  in ubifs_add_to_cat()
295 		c->freeable_cnt += 1;  in ubifs_add_to_cat()
298 		list_add(&lprops->list, &c->frdi_idx_list);  in ubifs_add_to_cat()
306 	c->in_a_category_cnt += 1;  in ubifs_add_to_cat()
307 	ubifs_assert(c->in_a_category_cnt <= c->main_lebs);  in ubifs_add_to_cat()
318 static void ubifs_remove_from_cat(struct ubifs_info *c,  in ubifs_remove_from_cat()  argument
325 		remove_from_lpt_heap(c, lprops, cat);  in ubifs_remove_from_cat()
328 		c->freeable_cnt -= 1;  in ubifs_remove_from_cat()
329 		ubifs_assert(c->freeable_cnt >= 0);  in ubifs_remove_from_cat()
341 	c->in_a_category_cnt -= 1;  in ubifs_remove_from_cat()
342 	ubifs_assert(c->in_a_category_cnt >= 0);  in ubifs_remove_from_cat()
355 void ubifs_replace_cat(struct ubifs_info *c, struct ubifs_lprops *old_lprops,  in ubifs_replace_cat()  argument
365 		lpt_heap_replace(c, old_lprops, new_lprops, cat);  in ubifs_replace_cat()
387 void ubifs_ensure_cat(struct ubifs_info *c, struct ubifs_lprops *lprops)  in ubifs_ensure_cat()  argument
393 	cat = ubifs_categorize_lprops(c, lprops);  in ubifs_ensure_cat()
396 	ubifs_remove_from_cat(c, lprops, LPROPS_UNCAT);  in ubifs_ensure_cat()
397 	ubifs_add_to_cat(c, lprops, cat);  in ubifs_ensure_cat()
410 int ubifs_categorize_lprops(const struct ubifs_info *c,  in ubifs_categorize_lprops()  argument
416 	if (lprops->free == c->leb_size) {  in ubifs_categorize_lprops()
421 	if (lprops->free + lprops->dirty == c->leb_size) {  in ubifs_categorize_lprops()
429 		if (lprops->dirty + lprops->free >= c->min_idx_node_sz)  in ubifs_categorize_lprops()
432 		if (lprops->dirty >= c->dead_wm &&  in ubifs_categorize_lprops()
450 static void change_category(struct ubifs_info *c, struct ubifs_lprops *lprops)  in change_category()  argument
453 	int new_cat = ubifs_categorize_lprops(c, lprops);  in change_category()
461 		heap = &c->lpt_heap[new_cat - 1];  in change_category()
462 		adjust_lpt_heap(c, heap, lprops, lprops->hpos, new_cat);  in change_category()
464 		ubifs_remove_from_cat(c, lprops, old_cat);  in change_category()
465 		ubifs_add_to_cat(c, lprops, new_cat);  in change_category()
481 int ubifs_calc_dark(const struct ubifs_info *c, int spc)  in ubifs_calc_dark()  argument
485 	if (spc < c->dark_wm)  in ubifs_calc_dark()
493 	if (spc - c->dark_wm < MIN_WRITE_SZ)  in ubifs_calc_dark()
496 	return c->dark_wm;  in ubifs_calc_dark()
504 static int is_lprops_dirty(struct ubifs_info *c, struct ubifs_lprops *lprops)  in is_lprops_dirty()  argument
509 	pos = (lprops->lnum - c->main_first) & (UBIFS_LPT_FANOUT - 1);  in is_lprops_dirty()
534 const struct ubifs_lprops *ubifs_change_lp(struct ubifs_info *c,  in ubifs_change_lp()  argument
548 	ubifs_assert(mutex_is_locked(&c->lp_mutex));  in ubifs_change_lp()
549 	ubifs_assert(c->lst.empty_lebs >= 0 &&  in ubifs_change_lp()
550 		     c->lst.empty_lebs <= c->main_lebs);  in ubifs_change_lp()
551 	ubifs_assert(c->freeable_cnt >= 0);  in ubifs_change_lp()
552 	ubifs_assert(c->freeable_cnt <= c->main_lebs);  in ubifs_change_lp()
553 	ubifs_assert(c->lst.taken_empty_lebs >= 0);  in ubifs_change_lp()
554 	ubifs_assert(c->lst.taken_empty_lebs <= c->lst.empty_lebs);  in ubifs_change_lp()
555 	ubifs_assert(!(c->lst.total_free & 7) && !(c->lst.total_dirty & 7));  in ubifs_change_lp()
556 	ubifs_assert(!(c->lst.total_dead & 7) && !(c->lst.total_dark & 7));  in ubifs_change_lp()
557 	ubifs_assert(!(c->lst.total_used & 7));  in ubifs_change_lp()
561 	if (!is_lprops_dirty(c, lprops)) {  in ubifs_change_lp()
562 		lprops = ubifs_lpt_lookup_dirty(c, lprops->lnum);  in ubifs_change_lp()
566 		ubifs_assert(lprops == ubifs_lpt_lookup_dirty(c, lprops->lnum));  in ubifs_change_lp()
570 	spin_lock(&c->space_lock);  in ubifs_change_lp()
571 	if ((lprops->flags & LPROPS_TAKEN) && lprops->free == c->leb_size)  in ubifs_change_lp()
572 		c->lst.taken_empty_lebs -= 1;  in ubifs_change_lp()
578 		if (old_spc < c->dead_wm)  in ubifs_change_lp()
579 			c->lst.total_dead -= old_spc;  in ubifs_change_lp()
581 			c->lst.total_dark -= ubifs_calc_dark(c, old_spc);  in ubifs_change_lp()
583 		c->lst.total_used -= c->leb_size - old_spc;  in ubifs_change_lp()
588 		c->lst.total_free += free - lprops->free;  in ubifs_change_lp()
591 		if (free == c->leb_size) {  in ubifs_change_lp()
592 			if (lprops->free != c->leb_size)  in ubifs_change_lp()
593 				c->lst.empty_lebs += 1;  in ubifs_change_lp()
594 		} else if (lprops->free == c->leb_size)  in ubifs_change_lp()
595 			c->lst.empty_lebs -= 1;  in ubifs_change_lp()
601 		c->lst.total_dirty += dirty - lprops->dirty;  in ubifs_change_lp()
609 				c->lst.idx_lebs -= 1;  in ubifs_change_lp()
611 			c->lst.idx_lebs += 1;  in ubifs_change_lp()
619 		if (new_spc < c->dead_wm)  in ubifs_change_lp()
620 			c->lst.total_dead += new_spc;  in ubifs_change_lp()
622 			c->lst.total_dark += ubifs_calc_dark(c, new_spc);  in ubifs_change_lp()
624 		c->lst.total_used += c->leb_size - new_spc;  in ubifs_change_lp()
627 	if ((lprops->flags & LPROPS_TAKEN) && lprops->free == c->leb_size)  in ubifs_change_lp()
628 		c->lst.taken_empty_lebs += 1;  in ubifs_change_lp()
630 	change_category(c, lprops);  in ubifs_change_lp()
631 	c->idx_gc_cnt += idx_gc_cnt;  in ubifs_change_lp()
632 	spin_unlock(&c->space_lock);  in ubifs_change_lp()
641 void ubifs_get_lp_stats(struct ubifs_info *c, struct ubifs_lp_stats *lst)  in ubifs_get_lp_stats()  argument
643 	spin_lock(&c->space_lock);  in ubifs_get_lp_stats()
644 	memcpy(lst, &c->lst, sizeof(struct ubifs_lp_stats));  in ubifs_get_lp_stats()
645 	spin_unlock(&c->space_lock);  in ubifs_get_lp_stats()
663 int ubifs_change_one_lp(struct ubifs_info *c, int lnum, int free, int dirty,  in ubifs_change_one_lp()  argument
669 	ubifs_get_lprops(c);  in ubifs_change_one_lp()
671 	lp = ubifs_lpt_lookup_dirty(c, lnum);  in ubifs_change_one_lp()
678 	lp = ubifs_change_lp(c, lp, free, dirty, flags, idx_gc_cnt);  in ubifs_change_one_lp()
683 	ubifs_release_lprops(c);  in ubifs_change_one_lp()
685 		ubifs_err(c, "cannot change properties of LEB %d, error %d",  in ubifs_change_one_lp()
702 int ubifs_update_one_lp(struct ubifs_info *c, int lnum, int free, int dirty,  in ubifs_update_one_lp()  argument
708 	ubifs_get_lprops(c);  in ubifs_update_one_lp()
710 	lp = ubifs_lpt_lookup_dirty(c, lnum);  in ubifs_update_one_lp()
717 	lp = ubifs_change_lp(c, lp, free, lp->dirty + dirty, flags, 0);  in ubifs_update_one_lp()
722 	ubifs_release_lprops(c);  in ubifs_update_one_lp()
724 		ubifs_err(c, "cannot update properties of LEB %d, error %d",  in ubifs_update_one_lp()
739 int ubifs_read_one_lp(struct ubifs_info *c, int lnum, struct ubifs_lprops *lp)  in ubifs_read_one_lp()  argument
744 	ubifs_get_lprops(c);  in ubifs_read_one_lp()
746 	lpp = ubifs_lpt_lookup(c, lnum);  in ubifs_read_one_lp()
749 		ubifs_err(c, "cannot read properties of LEB %d, error %d",  in ubifs_read_one_lp()
757 	ubifs_release_lprops(c);  in ubifs_read_one_lp()
768 const struct ubifs_lprops *ubifs_fast_find_free(struct ubifs_info *c)  in ubifs_fast_find_free()  argument
773 	ubifs_assert(mutex_is_locked(&c->lp_mutex));  in ubifs_fast_find_free()
775 	heap = &c->lpt_heap[LPROPS_FREE - 1];  in ubifs_fast_find_free()
792 const struct ubifs_lprops *ubifs_fast_find_empty(struct ubifs_info *c)  in ubifs_fast_find_empty()  argument
796 	ubifs_assert(mutex_is_locked(&c->lp_mutex));  in ubifs_fast_find_empty()
798 	if (list_empty(&c->empty_list))  in ubifs_fast_find_empty()
801 	lprops = list_entry(c->empty_list.next, struct ubifs_lprops, list);  in ubifs_fast_find_empty()
804 	ubifs_assert(lprops->free == c->leb_size);  in ubifs_fast_find_empty()
815 const struct ubifs_lprops *ubifs_fast_find_freeable(struct ubifs_info *c)  in ubifs_fast_find_freeable()  argument
819 	ubifs_assert(mutex_is_locked(&c->lp_mutex));  in ubifs_fast_find_freeable()
821 	if (list_empty(&c->freeable_list))  in ubifs_fast_find_freeable()
824 	lprops = list_entry(c->freeable_list.next, struct ubifs_lprops, list);  in ubifs_fast_find_freeable()
827 	ubifs_assert(lprops->free + lprops->dirty == c->leb_size);  in ubifs_fast_find_freeable()
828 	ubifs_assert(c->freeable_cnt > 0);  in ubifs_fast_find_freeable()
839 const struct ubifs_lprops *ubifs_fast_find_frdi_idx(struct ubifs_info *c)  in ubifs_fast_find_frdi_idx()  argument
843 	ubifs_assert(mutex_is_locked(&c->lp_mutex));  in ubifs_fast_find_frdi_idx()
845 	if (list_empty(&c->frdi_idx_list))  in ubifs_fast_find_frdi_idx()
848 	lprops = list_entry(c->frdi_idx_list.next, struct ubifs_lprops, list);  in ubifs_fast_find_frdi_idx()
851 	ubifs_assert(lprops->free + lprops->dirty == c->leb_size);  in ubifs_fast_find_frdi_idx()
865 int dbg_check_cats(struct ubifs_info *c)  in dbg_check_cats()  argument
871 	if (!dbg_is_chk_gen(c) && !dbg_is_chk_lprops(c))  in dbg_check_cats()
874 	list_for_each_entry(lprops, &c->empty_list, list) {  in dbg_check_cats()
875 		if (lprops->free != c->leb_size) {  in dbg_check_cats()
876 			ubifs_err(c, "non-empty LEB %d on empty list (free %d dirty %d flags %d)",  in dbg_check_cats()
882 			ubifs_err(c, "taken LEB %d on empty list (free %d dirty %d flags %d)",  in dbg_check_cats()
890 	list_for_each_entry(lprops, &c->freeable_list, list) {  in dbg_check_cats()
891 		if (lprops->free + lprops->dirty != c->leb_size) {  in dbg_check_cats()
892 			ubifs_err(c, "non-freeable LEB %d on freeable list (free %d dirty %d flags %d)",  in dbg_check_cats()
898 			ubifs_err(c, "taken LEB %d on freeable list (free %d dirty %d flags %d)",  in dbg_check_cats()
905 	if (i != c->freeable_cnt) {  in dbg_check_cats()
906 		ubifs_err(c, "freeable list count %d expected %d", i,  in dbg_check_cats()
907 			  c->freeable_cnt);  in dbg_check_cats()
912 	list_for_each(pos, &c->idx_gc)  in dbg_check_cats()
914 	if (i != c->idx_gc_cnt) {  in dbg_check_cats()
915 		ubifs_err(c, "idx_gc list count %d expected %d", i,  in dbg_check_cats()
916 			  c->idx_gc_cnt);  in dbg_check_cats()
920 	list_for_each_entry(lprops, &c->frdi_idx_list, list) {  in dbg_check_cats()
921 		if (lprops->free + lprops->dirty != c->leb_size) {  in dbg_check_cats()
922 			ubifs_err(c, "non-freeable LEB %d on frdi_idx list (free %d dirty %d flags %d)",  in dbg_check_cats()
928 			ubifs_err(c, "taken LEB %d on frdi_idx list (free %d dirty %d flags %d)",  in dbg_check_cats()
934 			ubifs_err(c, "non-index LEB %d on frdi_idx list (free %d dirty %d flags %d)",  in dbg_check_cats()
942 		struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];  in dbg_check_cats()
947 				ubifs_err(c, "null ptr in LPT heap cat %d", cat);  in dbg_check_cats()
951 				ubifs_err(c, "bad ptr in LPT heap cat %d", cat);  in dbg_check_cats()
955 				ubifs_err(c, "taken LEB in LPT heap cat %d", cat);  in dbg_check_cats()
964 void dbg_check_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap, int cat,  in dbg_check_heap()  argument
969 	if (!dbg_is_chk_gen(c) && !dbg_is_chk_lprops(c))  in dbg_check_heap()
985 		lp = ubifs_lpt_lookup(c, lprops->lnum);  in dbg_check_heap()
991 			ubifs_err(c, "lprops %zx lp %zx lprops->lnum %d lp->lnum %d",  in dbg_check_heap()
1011 		ubifs_err(c, "failed cat %d hpos %d err %d", cat, i, err);  in dbg_check_heap()
1013 		ubifs_dump_heap(c, heap, cat);  in dbg_check_heap()
1029 static int scan_check_cb(struct ubifs_info *c,  in scan_check_cb()  argument
1040 		cat = ubifs_categorize_lprops(c, lp);  in scan_check_cb()
1042 			ubifs_err(c, "bad LEB category %d expected %d",  in scan_check_cb()
1054 			list = &c->empty_list;  in scan_check_cb()
1057 			list = &c->freeable_list;  in scan_check_cb()
1060 			list = &c->frdi_idx_list;  in scan_check_cb()
1063 			list = &c->uncat_list;  in scan_check_cb()
1077 				ubifs_err(c, "bad LPT list (category %d)", cat);  in scan_check_cb()
1085 		struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];  in scan_check_cb()
1089 			ubifs_err(c, "bad LPT heap (category %d)", cat);  in scan_check_cb()
1094 	buf = __vmalloc(c->leb_size, GFP_NOFS, PAGE_KERNEL);  in scan_check_cb()
1102 	if (lp->free == c->leb_size) {  in scan_check_cb()
1104 		lst->total_free += c->leb_size;  in scan_check_cb()
1105 		lst->total_dark += ubifs_calc_dark(c, c->leb_size);  in scan_check_cb()
1108 	if (lp->free + lp->dirty == c->leb_size &&  in scan_check_cb()
1112 		lst->total_dark  +=  ubifs_calc_dark(c, c->leb_size);  in scan_check_cb()
1116 	sleb = ubifs_scan(c, lnum, 0, buf, 0);  in scan_check_cb()
1120 			ubifs_dump_lprops(c);  in scan_check_cb()
1121 			ubifs_dump_budg(c, &c->bi);  in scan_check_cb()
1136 			ubifs_err(c, "indexing node in data LEB %d:%d",  in scan_check_cb()
1144 			key_read(c, ubifs_idx_key(c, idx), &snod->key);  in scan_check_cb()
1148 		found = ubifs_tnc_has_node(c, &snod->key, level, lnum,  in scan_check_cb()
1157 	free = c->leb_size - sleb->endpt;  in scan_check_cb()
1160 	if (free > c->leb_size || free < 0 || dirty > c->leb_size ||  in scan_check_cb()
1162 		ubifs_err(c, "bad calculated accounting for LEB %d: free %d, dirty %d",  in scan_check_cb()
1167 	if (lp->free + lp->dirty == c->leb_size &&  in scan_check_cb()
1168 	    free + dirty == c->leb_size)  in scan_check_cb()
1170 		    (!is_idx && free == c->leb_size) ||  in scan_check_cb()
1171 		    lp->free == c->leb_size) {  in scan_check_cb()
1185 	    lnum != c->ihead_lnum) {  in scan_check_cb()
1205 		if (free == c->leb_size)  in scan_check_cb()
1209 			ubifs_err(c, "indexing node without indexing flag");  in scan_check_cb()
1215 		ubifs_err(c, "data node with indexing flag");  in scan_check_cb()
1219 	if (free == c->leb_size)  in scan_check_cb()
1226 		lst->total_used += c->leb_size - free - dirty;  in scan_check_cb()
1233 		if (spc < c->dead_wm)  in scan_check_cb()
1236 			lst->total_dark += ubifs_calc_dark(c, spc);  in scan_check_cb()
1244 	ubifs_err(c, "bad accounting of LEB %d: free %d, dirty %d flags %#x, should be free %d, dirty %d",  in scan_check_cb()
1246 	ubifs_dump_leb(c, lnum);  in scan_check_cb()
1266 int dbg_check_lprops(struct ubifs_info *c)  in dbg_check_lprops()  argument
1271 	if (!dbg_is_chk_lprops(c))  in dbg_check_lprops()
1278 	for (i = 0; i < c->jhead_cnt; i++) {  in dbg_check_lprops()
1279 		err = ubifs_wbuf_sync(&c->jheads[i].wbuf);  in dbg_check_lprops()
1285 	err = ubifs_lpt_scan_nolock(c, c->main_first, c->leb_cnt - 1,  in dbg_check_lprops()
1291 	if (lst.empty_lebs != c->lst.empty_lebs ||  in dbg_check_lprops()
1292 	    lst.idx_lebs != c->lst.idx_lebs ||  in dbg_check_lprops()
1293 	    lst.total_free != c->lst.total_free ||  in dbg_check_lprops()
1294 	    lst.total_dirty != c->lst.total_dirty ||  in dbg_check_lprops()
1295 	    lst.total_used != c->lst.total_used) {  in dbg_check_lprops()
1296 		ubifs_err(c, "bad overall accounting");  in dbg_check_lprops()
1297 …ubifs_err(c, "calculated: empty_lebs %d, idx_lebs %d, total_free %lld, total_dirty %lld, total_use…  in dbg_check_lprops()
1300 …ubifs_err(c, "read from lprops: empty_lebs %d, idx_lebs %d, total_free %lld, total_dirty %lld, tot…  in dbg_check_lprops()
1301 			  c->lst.empty_lebs, c->lst.idx_lebs, c->lst.total_free,  in dbg_check_lprops()
1302 			  c->lst.total_dirty, c->lst.total_used);  in dbg_check_lprops()
1307 	if (lst.total_dead != c->lst.total_dead ||  in dbg_check_lprops()
1308 	    lst.total_dark != c->lst.total_dark) {  in dbg_check_lprops()
1309 		ubifs_err(c, "bad dead/dark space accounting");  in dbg_check_lprops()
1310 		ubifs_err(c, "calculated: total_dead %lld, total_dark %lld",  in dbg_check_lprops()
1312 		ubifs_err(c, "read from lprops: total_dead %lld, total_dark %lld",  in dbg_check_lprops()
1313 			  c->lst.total_dead, c->lst.total_dark);  in dbg_check_lprops()
1318 	err = dbg_check_cats(c);  in dbg_check_lprops()