54 static int valuable(struct ubifs_info *c, const struct ubifs_lprops *lprops)  in valuable()  argument
63 		heap = &c->lpt_heap[cat - 1];  in valuable()
66 		if (lprops->free + lprops->dirty >= c->dark_wm)  in valuable()
70 		n = c->lst.empty_lebs + c->freeable_cnt -  in valuable()
71 		    c->lst.taken_empty_lebs;  in valuable()
72 		if (n < c->lsave_cnt)  in valuable()
95 static int scan_for_dirty_cb(struct ubifs_info *c,  in scan_for_dirty_cb()  argument
105 	if (!in_tree && valuable(c, lprops))  in scan_for_dirty_cb()
114 	if (lprops->free + lprops->dirty == c->leb_size) {  in scan_for_dirty_cb()
118 	} else if (lprops->dirty < c->dead_wm)  in scan_for_dirty_cb()
136 static const struct ubifs_lprops *scan_for_dirty(struct ubifs_info *c,  in scan_for_dirty()  argument
146 	heap = &c->lpt_heap[LPROPS_FREE - 1];  in scan_for_dirty()
151 		if (lprops->dirty < c->dead_wm)  in scan_for_dirty()
162 	list_for_each_entry(lprops, &c->uncat_list, list) {  in scan_for_dirty()
169 		if (lprops->dirty < c->dead_wm)  in scan_for_dirty()
174 	if (c->pnodes_have >= c->pnode_cnt)  in scan_for_dirty()
181 	err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,  in scan_for_dirty()
186 	ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt);  in scan_for_dirty()
187 	c->lscan_lnum = data.lnum;  in scan_for_dirty()
188 	lprops = ubifs_lpt_lookup_dirty(c, data.lnum);  in scan_for_dirty()
193 	ubifs_assert(lprops->dirty >= c->dead_wm ||  in scan_for_dirty()
195 		      lprops->free + lprops->dirty == c->leb_size));  in scan_for_dirty()
233 int ubifs_find_dirty_leb(struct ubifs_info *c, struct ubifs_lprops *ret_lp,  in ubifs_find_dirty_leb()  argument
240 	ubifs_get_lprops(c);  in ubifs_find_dirty_leb()
245 		spin_lock(&c->space_lock);  in ubifs_find_dirty_leb()
246 		lebs = c->lst.empty_lebs + c->idx_gc_cnt;  in ubifs_find_dirty_leb()
247 		lebs += c->freeable_cnt - c->lst.taken_empty_lebs;  in ubifs_find_dirty_leb()
255 		if (c->bi.min_idx_lebs >= c->lst.idx_lebs) {  in ubifs_find_dirty_leb()
256 			rsvd_idx_lebs = c->bi.min_idx_lebs -  c->lst.idx_lebs;  in ubifs_find_dirty_leb()
259 		spin_unlock(&c->space_lock);  in ubifs_find_dirty_leb()
264 			lp = ubifs_fast_find_empty(c);  in ubifs_find_dirty_leb()
269 			lp = ubifs_fast_find_freeable(c);  in ubifs_find_dirty_leb()
278 		spin_lock(&c->space_lock);  in ubifs_find_dirty_leb()
279 		exclude_index = (c->bi.min_idx_lebs >= c->lst.idx_lebs);  in ubifs_find_dirty_leb()
280 		spin_unlock(&c->space_lock);  in ubifs_find_dirty_leb()
284 	heap = &c->lpt_heap[LPROPS_DIRTY - 1];  in ubifs_find_dirty_leb()
285 	idx_heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];  in ubifs_find_dirty_leb()
300 		if (sum < min_space || sum < c->half_leb_size)  in ubifs_find_dirty_leb()
318 		ubifs_assert(lp->free + lp->dirty >= c->dead_wm);  in ubifs_find_dirty_leb()
324 	lp = scan_for_dirty(c, min_space, pick_free, exclude_index);  in ubifs_find_dirty_leb()
329 	ubifs_assert(lp->dirty >= c->dead_wm ||  in ubifs_find_dirty_leb()
330 		     (pick_free && lp->free + lp->dirty == c->leb_size));  in ubifs_find_dirty_leb()
336 	lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,  in ubifs_find_dirty_leb()
346 	ubifs_release_lprops(c);  in ubifs_find_dirty_leb()
362 static int scan_for_free_cb(struct ubifs_info *c,  in scan_for_free_cb()  argument
372 	if (!in_tree && valuable(c, lprops))  in scan_for_free_cb()
381 	if (!data->pick_free && lprops->free == c->leb_size)  in scan_for_free_cb()
389 	if (lprops->free + lprops->dirty == c->leb_size && lprops->dirty > 0)  in scan_for_free_cb()
407 const struct ubifs_lprops *do_find_free_space(struct ubifs_info *c,  in do_find_free_space()  argument
417 		lprops = ubifs_fast_find_free(c);  in do_find_free_space()
422 		lprops = ubifs_fast_find_empty(c);  in do_find_free_space()
427 		lprops = ubifs_fast_find_free(c);  in do_find_free_space()
432 	heap = &c->lpt_heap[LPROPS_DIRTY - 1];  in do_find_free_space()
445 	list_for_each_entry(lprops, &c->uncat_list, list) {  in do_find_free_space()
454 	if (c->pnodes_have >= c->pnode_cnt)  in do_find_free_space()
460 	err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,  in do_find_free_space()
465 	ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt);  in do_find_free_space()
466 	c->lscan_lnum = data.lnum;  in do_find_free_space()
467 	lprops = ubifs_lpt_lookup_dirty(c, data.lnum);  in do_find_free_space()
493 int ubifs_find_free_space(struct ubifs_info *c, int min_space, int *offs,  in ubifs_find_free_space()  argument
500 	ubifs_get_lprops(c);  in ubifs_find_free_space()
503 	spin_lock(&c->space_lock);  in ubifs_find_free_space()
504 	if (c->bi.min_idx_lebs > c->lst.idx_lebs)  in ubifs_find_free_space()
505 		rsvd_idx_lebs = c->bi.min_idx_lebs -  c->lst.idx_lebs;  in ubifs_find_free_space()
508 	lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt -  in ubifs_find_free_space()
509 	       c->lst.taken_empty_lebs;  in ubifs_find_free_space()
515 		if (c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) {  in ubifs_find_free_space()
536 			c->lst.taken_empty_lebs += 1;  in ubifs_find_free_space()
538 	spin_unlock(&c->space_lock);  in ubifs_find_free_space()
540 	lprops = do_find_free_space(c, min_space, pick_free, squeeze);  in ubifs_find_free_space()
549 	lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC, flags, 0);  in ubifs_find_free_space()
556 		spin_lock(&c->space_lock);  in ubifs_find_free_space()
557 		c->lst.taken_empty_lebs -= 1;  in ubifs_find_free_space()
558 		spin_unlock(&c->space_lock);  in ubifs_find_free_space()
561 	*offs = c->leb_size - lprops->free;  in ubifs_find_free_space()
562 	ubifs_release_lprops(c);  in ubifs_find_free_space()
571 		err = ubifs_leb_unmap(c, lnum);  in ubifs_find_free_space()
576 	dbg_find("found LEB %d, free %d", lnum, c->leb_size - *offs);  in ubifs_find_free_space()
577 	ubifs_assert(*offs <= c->leb_size - min_space);  in ubifs_find_free_space()
582 		spin_lock(&c->space_lock);  in ubifs_find_free_space()
583 		c->lst.taken_empty_lebs -= 1;  in ubifs_find_free_space()
584 		spin_unlock(&c->space_lock);  in ubifs_find_free_space()
586 	ubifs_release_lprops(c);  in ubifs_find_free_space()
602 static int scan_for_idx_cb(struct ubifs_info *c,  in scan_for_idx_cb()  argument
612 	if (!in_tree && valuable(c, lprops))  in scan_for_idx_cb()
618 	if (lprops->free + lprops->dirty != c->leb_size)  in scan_for_idx_cb()
633 static const struct ubifs_lprops *scan_for_leb_for_idx(struct ubifs_info *c)  in scan_for_leb_for_idx()  argument
640 	err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,  in scan_for_leb_for_idx()
645 	ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt);  in scan_for_leb_for_idx()
646 	c->lscan_lnum = data.lnum;  in scan_for_leb_for_idx()
647 	lprops = ubifs_lpt_lookup_dirty(c, data.lnum);  in scan_for_leb_for_idx()
651 	ubifs_assert(lprops->free + lprops->dirty == c->leb_size);  in scan_for_leb_for_idx()
673 int ubifs_find_free_leb_for_idx(struct ubifs_info *c)  in ubifs_find_free_leb_for_idx()  argument
678 	ubifs_get_lprops(c);  in ubifs_find_free_leb_for_idx()
680 	lprops = ubifs_fast_find_empty(c);  in ubifs_find_free_leb_for_idx()
682 		lprops = ubifs_fast_find_freeable(c);  in ubifs_find_free_leb_for_idx()
691 			if (c->in_a_category_cnt != c->main_lebs ||  in ubifs_find_free_leb_for_idx()
692 			    c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) {  in ubifs_find_free_leb_for_idx()
693 				ubifs_assert(c->freeable_cnt == 0);  in ubifs_find_free_leb_for_idx()
694 				lprops = scan_for_leb_for_idx(c);  in ubifs_find_free_leb_for_idx()
714 	lprops = ubifs_change_lp(c, lprops, c->leb_size, 0, flags, 0);  in ubifs_find_free_leb_for_idx()
720 	ubifs_release_lprops(c);  in ubifs_find_free_leb_for_idx()
727 	err = ubifs_leb_unmap(c, lnum);  in ubifs_find_free_leb_for_idx()
729 		ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0,  in ubifs_find_free_leb_for_idx()
737 	ubifs_release_lprops(c);  in ubifs_find_free_leb_for_idx()
767 int ubifs_save_dirty_idx_lnums(struct ubifs_info *c)  in ubifs_save_dirty_idx_lnums()  argument
771 	ubifs_get_lprops(c);  in ubifs_save_dirty_idx_lnums()
773 	c->dirty_idx.cnt = c->lpt_heap[LPROPS_DIRTY_IDX - 1].cnt;  in ubifs_save_dirty_idx_lnums()
774 	memcpy(c->dirty_idx.arr, c->lpt_heap[LPROPS_DIRTY_IDX - 1].arr,  in ubifs_save_dirty_idx_lnums()
775 	       sizeof(void *) * c->dirty_idx.cnt);  in ubifs_save_dirty_idx_lnums()
777 	sort(c->dirty_idx.arr, c->dirty_idx.cnt, sizeof(void *),  in ubifs_save_dirty_idx_lnums()
780 	dbg_find("found %d dirty index LEBs", c->dirty_idx.cnt);  in ubifs_save_dirty_idx_lnums()
781 	if (c->dirty_idx.cnt)  in ubifs_save_dirty_idx_lnums()
783 			 c->dirty_idx.arr[c->dirty_idx.cnt - 1]->lnum,  in ubifs_save_dirty_idx_lnums()
784 			 c->dirty_idx.arr[c->dirty_idx.cnt - 1]->dirty,  in ubifs_save_dirty_idx_lnums()
785 			 c->dirty_idx.arr[c->dirty_idx.cnt - 1]->free);  in ubifs_save_dirty_idx_lnums()
787 	for (i = 0; i < c->dirty_idx.cnt; i++)  in ubifs_save_dirty_idx_lnums()
788 		c->dirty_idx.arr[i] = (void *)(size_t)c->dirty_idx.arr[i]->lnum;  in ubifs_save_dirty_idx_lnums()
789 	ubifs_release_lprops(c);  in ubifs_save_dirty_idx_lnums()
805 static int scan_dirty_idx_cb(struct ubifs_info *c,  in scan_dirty_idx_cb()  argument
815 	if (!in_tree && valuable(c, lprops))  in scan_dirty_idx_cb()
821 	if (lprops->free + lprops->dirty < c->min_idx_node_sz)  in scan_dirty_idx_cb()
838 static int find_dirty_idx_leb(struct ubifs_info *c)  in find_dirty_idx_leb()  argument
847 	heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];  in find_dirty_idx_leb()
850 		ret = scan_dirty_idx_cb(c, lprops, 1, &data);  in find_dirty_idx_leb()
854 	list_for_each_entry(lprops, &c->frdi_idx_list, list) {  in find_dirty_idx_leb()
855 		ret = scan_dirty_idx_cb(c, lprops, 1, &data);  in find_dirty_idx_leb()
859 	list_for_each_entry(lprops, &c->uncat_list, list) {  in find_dirty_idx_leb()
860 		ret = scan_dirty_idx_cb(c, lprops, 1, &data);  in find_dirty_idx_leb()
864 	if (c->pnodes_have >= c->pnode_cnt)  in find_dirty_idx_leb()
867 	err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,  in find_dirty_idx_leb()
873 	ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt);  in find_dirty_idx_leb()
874 	c->lscan_lnum = data.lnum;  in find_dirty_idx_leb()
875 	lprops = ubifs_lpt_lookup_dirty(c, data.lnum);  in find_dirty_idx_leb()
879 	ubifs_assert(lprops->free + lprops->dirty >= c->min_idx_node_sz);  in find_dirty_idx_leb()
886 	lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC,  in find_dirty_idx_leb()
898 static int get_idx_gc_leb(struct ubifs_info *c)  in get_idx_gc_leb()  argument
903 	err = ubifs_get_idx_gc_leb(c);  in get_idx_gc_leb()
911 	lp = ubifs_lpt_lookup_dirty(c, lnum);  in get_idx_gc_leb()
914 	lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,  in get_idx_gc_leb()
927 static int find_dirtiest_idx_leb(struct ubifs_info *c)  in find_dirtiest_idx_leb()  argument
933 		if (!c->dirty_idx.cnt)  in find_dirtiest_idx_leb()
936 		lnum = (size_t)c->dirty_idx.arr[--c->dirty_idx.cnt];  in find_dirtiest_idx_leb()
937 		lp = ubifs_lpt_lookup(c, lnum);  in find_dirtiest_idx_leb()
942 		lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,  in find_dirtiest_idx_leb()
963 int ubifs_find_dirty_idx_leb(struct ubifs_info *c)  in ubifs_find_dirty_idx_leb()  argument
967 	ubifs_get_lprops(c);  in ubifs_find_dirty_idx_leb()
973 	err = find_dirtiest_idx_leb(c);  in ubifs_find_dirty_idx_leb()
977 		err = find_dirty_idx_leb(c);  in ubifs_find_dirty_idx_leb()
981 		err = get_idx_gc_leb(c);  in ubifs_find_dirty_idx_leb()
983 	ubifs_release_lprops(c);  in ubifs_find_dirty_idx_leb()