25 static int make_idx_node(struct ubifs_info *c, struct ubifs_idx_node *idx,  in make_idx_node()  argument
37 		struct ubifs_branch *br = ubifs_idx_branch(c, idx, i);  in make_idx_node()
40 		key_write_idx(c, &zbr->key, &br->key);  in make_idx_node()
44 		ubifs_copy_hash(c, zbr->hash, ubifs_branch_hash(c, br));  in make_idx_node()
46 			ubifs_err(c, "bad ref in znode");  in make_idx_node()
47 			ubifs_dump_znode(c, znode);  in make_idx_node()
49 				ubifs_dump_znode(c, zbr->znode);  in make_idx_node()
54 	ubifs_prepare_node(c, idx, len, 0);  in make_idx_node()
55 	ubifs_node_calc_hash(c, idx, hash);  in make_idx_node()
61 	err = insert_old_idx_znode(c, znode);  in make_idx_node()
72 		ubifs_copy_hash(c, hash, zbr->hash);  in make_idx_node()
74 		c->zroot.lnum = lnum;  in make_idx_node()
75 		c->zroot.offs = offs;  in make_idx_node()
76 		c->zroot.len = len;  in make_idx_node()
77 		ubifs_copy_hash(c, hash, c->zroot.hash);  in make_idx_node()
79 	c->calc_idx_sz += ALIGN(len, 8);  in make_idx_node()
81 	atomic_long_dec(&c->dirty_zn_cnt);  in make_idx_node()
83 	ubifs_assert(c, ubifs_zn_dirty(znode));  in make_idx_node()
84 	ubifs_assert(c, ubifs_zn_cow(znode));  in make_idx_node()
106 static int fill_gap(struct ubifs_info *c, int lnum, int gap_start, int gap_end,  in fill_gap()  argument
111 	ubifs_assert(c, (gap_start & 7) == 0);  in fill_gap()
112 	ubifs_assert(c, (gap_end & 7) == 0);  in fill_gap()
113 	ubifs_assert(c, gap_end >= gap_start);  in fill_gap()
120 	while (c->enext) {  in fill_gap()
121 		len = ubifs_idx_node_sz(c, c->enext->child_cnt);  in fill_gap()
123 			struct ubifs_znode *znode = c->enext;  in fill_gap()
127 			ubifs_assert(c, alen <= gap_remains);  in fill_gap()
128 			err = make_idx_node(c, c->ileb_buf + gap_pos, znode,  in fill_gap()
134 			c->enext = znode->cnext;  in fill_gap()
135 			if (c->enext == c->cnext)  in fill_gap()
136 				c->enext = NULL;  in fill_gap()
141 	if (gap_end == c->leb_size) {  in fill_gap()
142 		c->ileb_len = ALIGN(gap_pos, c->min_io_size);  in fill_gap()
144 		pad_len = c->ileb_len - gap_pos;  in fill_gap()
150 	ubifs_pad(c, c->ileb_buf + gap_pos, pad_len);  in fill_gap()
163 static int find_old_idx(struct ubifs_info *c, int lnum, int offs)  in find_old_idx()  argument
168 	p = c->old_idx.rb_node;  in find_old_idx()
198 static int is_idx_node_in_use(struct ubifs_info *c, union ubifs_key *key,  in is_idx_node_in_use()  argument
203 	ret = is_idx_node_in_tnc(c, key, level, lnum, offs);  in is_idx_node_in_use()
207 		if (find_old_idx(c, lnum, offs))  in is_idx_node_in_use()
224 static int layout_leb_in_gaps(struct ubifs_info *c, int p)  in layout_leb_in_gaps()  argument
232 	lnum = ubifs_find_dirty_idx_leb(c);  in layout_leb_in_gaps()
239 	c->gap_lebs[p] = lnum;  in layout_leb_in_gaps()
246 	sleb = ubifs_scan(c, lnum, 0, c->ileb_buf, 0);  in layout_leb_in_gaps()
247 	c->ileb_len = 0;  in layout_leb_in_gaps()
255 		ubifs_assert(c, snod->type == UBIFS_IDX_NODE);  in layout_leb_in_gaps()
257 		key_read(c, ubifs_idx_key(c, idx), &snod->key);  in layout_leb_in_gaps()
260 		in_use = is_idx_node_in_use(c, &snod->key, level, lnum,  in layout_leb_in_gaps()
277 			written = fill_gap(c, lnum, gap_start, gap_end, &dirt);  in layout_leb_in_gaps()
287 	c->ileb_len = c->leb_size;  in layout_leb_in_gaps()
288 	gap_end = c->leb_size;  in layout_leb_in_gaps()
290 	written = fill_gap(c, lnum, gap_start, gap_end, &dirt);  in layout_leb_in_gaps()
298 		err = ubifs_read_one_lp(c, lnum, &lp);  in layout_leb_in_gaps()
301 		if (lp.free == c->leb_size) {  in layout_leb_in_gaps()
306 			err = ubifs_change_one_lp(c, lnum,  in layout_leb_in_gaps()
307 						  c->leb_size - c->ileb_len,  in layout_leb_in_gaps()
314 	err = ubifs_change_one_lp(c, lnum, c->leb_size - c->ileb_len, dirt,  in layout_leb_in_gaps()
318 	err = ubifs_leb_change(c, lnum, c->ileb_buf, c->ileb_len);  in layout_leb_in_gaps()
334 static int get_leb_cnt(struct ubifs_info *c, int cnt)  in get_leb_cnt()  argument
339 	cnt -= (c->leb_size - c->ihead_offs) / c->max_idx_node_sz;  in get_leb_cnt()
342 	d = c->leb_size / c->max_idx_node_sz;  in get_leb_cnt()
356 static int layout_in_gaps(struct ubifs_info *c, int cnt)  in layout_in_gaps()  argument
362 	c->gap_lebs = kmalloc_array(c->lst.idx_lebs + 1, sizeof(int),  in layout_in_gaps()
364 	if (!c->gap_lebs)  in layout_in_gaps()
367 	old_idx_lebs = c->lst.idx_lebs;  in layout_in_gaps()
369 		ubifs_assert(c, p < c->lst.idx_lebs);  in layout_in_gaps()
370 		written = layout_leb_in_gaps(c, p);  in layout_in_gaps()
374 				kfree(c->gap_lebs);  in layout_in_gaps()
375 				c->gap_lebs = NULL;  in layout_in_gaps()
378 			if (!dbg_is_chk_index(c)) {  in layout_in_gaps()
383 				ubifs_warn(c, "out of space");  in layout_in_gaps()
384 				ubifs_dump_budg(c, &c->bi);  in layout_in_gaps()
385 				ubifs_dump_lprops(c);  in layout_in_gaps()
392 		leb_needed_cnt = get_leb_cnt(c, cnt);  in layout_in_gaps()
394 		       leb_needed_cnt, c->ileb_cnt);  in layout_in_gaps()
403 		if (leb_needed_cnt > c->ileb_cnt && p >= old_idx_lebs &&  in layout_in_gaps()
404 		    old_idx_lebs < c->lst.idx_lebs) {  in layout_in_gaps()
405 			old_idx_lebs = c->lst.idx_lebs;  in layout_in_gaps()
406 			gap_lebs = krealloc(c->gap_lebs, sizeof(int) *  in layout_in_gaps()
409 				kfree(c->gap_lebs);  in layout_in_gaps()
410 				c->gap_lebs = NULL;  in layout_in_gaps()
413 			c->gap_lebs = gap_lebs;  in layout_in_gaps()
415 	} while (leb_needed_cnt > c->ileb_cnt);  in layout_in_gaps()
417 	c->gap_lebs[p] = -1;  in layout_in_gaps()
429 static int layout_in_empty_space(struct ubifs_info *c)  in layout_in_empty_space()  argument
435 	cnext = c->enext;  in layout_in_empty_space()
439 	lnum = c->ihead_lnum;  in layout_in_empty_space()
440 	buf_offs = c->ihead_offs;  in layout_in_empty_space()
442 	buf_len = ubifs_idx_node_sz(c, c->fanout);  in layout_in_empty_space()
443 	buf_len = ALIGN(buf_len, c->min_io_size);  in layout_in_empty_space()
448 	next_len = ubifs_idx_node_sz(c, cnext->child_cnt);  in layout_in_empty_space()
449 	if (buf_offs + next_len > c->leb_size)  in layout_in_empty_space()
455 		len = ubifs_idx_node_sz(c, znode->child_cnt);  in layout_in_empty_space()
459 			if (c->ileb_nxt >= c->ileb_cnt) {  in layout_in_empty_space()
460 				ubifs_err(c, "out of space");  in layout_in_empty_space()
463 			lnum = c->ilebs[c->ileb_nxt++];  in layout_in_empty_space()
487 			c->zroot.lnum = lnum;  in layout_in_empty_space()
488 			c->zroot.offs = offs;  in layout_in_empty_space()
489 			c->zroot.len = len;  in layout_in_empty_space()
491 		c->calc_idx_sz += ALIGN(len, 8);  in layout_in_empty_space()
497 		atomic_long_dec(&c->dirty_zn_cnt);  in layout_in_empty_space()
504 		if (cnext == c->cnext)  in layout_in_empty_space()
507 			next_len = ubifs_idx_node_sz(c, cnext->child_cnt);  in layout_in_empty_space()
515 		    buf_offs + used + next_len <= c->leb_size &&  in layout_in_empty_space()
520 		    buf_offs + used + next_len <= c->leb_size)  in layout_in_empty_space()
523 			blen = ALIGN(wlen, c->min_io_size);  in layout_in_empty_space()
528 			if (buf_offs + next_len > c->leb_size) {  in layout_in_empty_space()
529 				err = ubifs_update_one_lp(c, lnum,  in layout_in_empty_space()
530 					c->leb_size - buf_offs, blen - used,  in layout_in_empty_space()
542 		err = ubifs_update_one_lp(c, lnum, c->leb_size - buf_offs,  in layout_in_empty_space()
549 	c->dbg->new_ihead_lnum = lnum;  in layout_in_empty_space()
550 	c->dbg->new_ihead_offs = buf_offs;  in layout_in_empty_space()
568 static int layout_commit(struct ubifs_info *c, int no_space, int cnt)  in layout_commit()  argument
573 		err = layout_in_gaps(c, cnt);  in layout_commit()
577 	err = layout_in_empty_space(c);  in layout_commit()
642 static int get_znodes_to_commit(struct ubifs_info *c)  in get_znodes_to_commit()  argument
647 	c->cnext = find_first_dirty(c->zroot.znode);  in get_znodes_to_commit()
648 	znode = c->enext = c->cnext;  in get_znodes_to_commit()
655 		ubifs_assert(c, !ubifs_zn_cow(znode));  in get_znodes_to_commit()
660 			znode->cnext = c->cnext;  in get_znodes_to_commit()
670 	ubifs_assert(c, cnt == atomic_long_read(&c->dirty_zn_cnt));  in get_znodes_to_commit()
683 static int alloc_idx_lebs(struct ubifs_info *c, int cnt)  in alloc_idx_lebs()  argument
687 	c->ileb_cnt = 0;  in alloc_idx_lebs()
688 	c->ileb_nxt = 0;  in alloc_idx_lebs()
689 	leb_cnt = get_leb_cnt(c, cnt);  in alloc_idx_lebs()
693 	c->ilebs = kmalloc_array(leb_cnt, sizeof(int), GFP_NOFS);  in alloc_idx_lebs()
694 	if (!c->ilebs)  in alloc_idx_lebs()
697 		lnum = ubifs_find_free_leb_for_idx(c);  in alloc_idx_lebs()
700 		c->ilebs[c->ileb_cnt++] = lnum;  in alloc_idx_lebs()
703 	if (dbg_is_chk_index(c) && !get_random_u32_below(8))  in alloc_idx_lebs()
717 static int free_unused_idx_lebs(struct ubifs_info *c)  in free_unused_idx_lebs()  argument
721 	for (i = c->ileb_nxt; i < c->ileb_cnt; i++) {  in free_unused_idx_lebs()
722 		lnum = c->ilebs[i];  in free_unused_idx_lebs()
724 		er = ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0,  in free_unused_idx_lebs()
738 static int free_idx_lebs(struct ubifs_info *c)  in free_idx_lebs()  argument
742 	err = free_unused_idx_lebs(c);  in free_idx_lebs()
743 	kfree(c->ilebs);  in free_idx_lebs()
744 	c->ilebs = NULL;  in free_idx_lebs()
758 int ubifs_tnc_start_commit(struct ubifs_info *c, struct ubifs_zbranch *zroot)  in ubifs_tnc_start_commit()  argument
762 	mutex_lock(&c->tnc_mutex);  in ubifs_tnc_start_commit()
763 	err = dbg_check_tnc(c, 1);  in ubifs_tnc_start_commit()
766 	cnt = get_znodes_to_commit(c);  in ubifs_tnc_start_commit()
770 		err = alloc_idx_lebs(c, cnt);  in ubifs_tnc_start_commit()
775 		err = layout_commit(c, no_space, cnt);  in ubifs_tnc_start_commit()
778 		ubifs_assert(c, atomic_long_read(&c->dirty_zn_cnt) == 0);  in ubifs_tnc_start_commit()
779 		err = free_unused_idx_lebs(c);  in ubifs_tnc_start_commit()
783 	destroy_old_idx(c);  in ubifs_tnc_start_commit()
784 	memcpy(zroot, &c->zroot, sizeof(struct ubifs_zbranch));  in ubifs_tnc_start_commit()
786 	err = ubifs_save_dirty_idx_lnums(c);  in ubifs_tnc_start_commit()
790 	spin_lock(&c->space_lock);  in ubifs_tnc_start_commit()
799 	ubifs_assert(c, c->bi.min_idx_lebs == ubifs_calc_min_idx_lebs(c));  in ubifs_tnc_start_commit()
800 	c->bi.old_idx_sz = c->calc_idx_sz;  in ubifs_tnc_start_commit()
801 	c->bi.uncommitted_idx = 0;  in ubifs_tnc_start_commit()
802 	c->bi.min_idx_lebs = ubifs_calc_min_idx_lebs(c);  in ubifs_tnc_start_commit()
803 	spin_unlock(&c->space_lock);  in ubifs_tnc_start_commit()
804 	mutex_unlock(&c->tnc_mutex);  in ubifs_tnc_start_commit()
806 	dbg_cmt("number of index LEBs %d", c->lst.idx_lebs);  in ubifs_tnc_start_commit()
807 	dbg_cmt("size of index %llu", c->calc_idx_sz);  in ubifs_tnc_start_commit()
811 	free_idx_lebs(c);  in ubifs_tnc_start_commit()
813 	mutex_unlock(&c->tnc_mutex);  in ubifs_tnc_start_commit()
824 static int write_index(struct ubifs_info *c)  in write_index()  argument
831 	cnext = c->enext;  in write_index()
839 	lnum = c->ihead_lnum;  in write_index()
840 	buf_offs = c->ihead_offs;  in write_index()
843 	buf_len = ALIGN(c->max_idx_node_sz, c->min_io_size);  in write_index()
848 	next_len = ubifs_idx_node_sz(c, cnext->child_cnt);  in write_index()
849 	if (buf_offs + next_len > c->leb_size) {  in write_index()
850 		err = ubifs_update_one_lp(c, lnum, LPROPS_NC, 0, 0,  in write_index()
863 		idx = c->cbuf + used;  in write_index()
870 			struct ubifs_branch *br = ubifs_idx_branch(c, idx, i);  in write_index()
873 			key_write_idx(c, &zbr->key, &br->key);  in write_index()
877 			ubifs_copy_hash(c, zbr->hash, ubifs_branch_hash(c, br));  in write_index()
879 				ubifs_err(c, "bad ref in znode");  in write_index()
880 				ubifs_dump_znode(c, znode);  in write_index()
882 					ubifs_dump_znode(c, zbr->znode);  in write_index()
887 		len = ubifs_idx_node_sz(c, znode->child_cnt);  in write_index()
888 		ubifs_prepare_node(c, idx, len, 0);  in write_index()
889 		ubifs_node_calc_hash(c, idx, hash);  in write_index()
891 		mutex_lock(&c->tnc_mutex);  in write_index()
894 			ubifs_copy_hash(c, hash,  in write_index()
899 				ubifs_copy_hash(c, hash,  in write_index()
902 			ubifs_copy_hash(c, hash, c->zroot.hash);  in write_index()
905 		mutex_unlock(&c->tnc_mutex);  in write_index()
909 			lnum = c->ilebs[lnum_pos++];  in write_index()
918 			ubifs_err(c, "inconsistent znode posn");  in write_index()
925 		ubifs_assert(c, ubifs_zn_dirty(znode));  in write_index()
926 		ubifs_assert(c, ubifs_zn_cow(znode));  in write_index()
974 		if (cnext == c->cnext)  in write_index()
977 			next_len = ubifs_idx_node_sz(c, cnext->child_cnt);  in write_index()
980 		if (next_len && nxt_offs <= c->leb_size) {  in write_index()
987 			blen = ALIGN(wlen, c->min_io_size);  in write_index()
988 			ubifs_pad(c, c->cbuf + wlen, blen - wlen);  in write_index()
992 		err = ubifs_leb_write(c, lnum, c->cbuf, buf_offs, blen);  in write_index()
997 			if (nxt_offs > c->leb_size) {  in write_index()
998 				err = ubifs_update_one_lp(c, lnum, LPROPS_NC, 0,  in write_index()
1008 			memmove(c->cbuf, c->cbuf + blen, used);  in write_index()
1014 	if (lnum != c->dbg->new_ihead_lnum ||  in write_index()
1015 	    buf_offs != c->dbg->new_ihead_offs) {  in write_index()
1016 		ubifs_err(c, "inconsistent ihead");  in write_index()
1020 	c->ihead_lnum = lnum;  in write_index()
1021 	c->ihead_offs = buf_offs;  in write_index()
1032 static void free_obsolete_znodes(struct ubifs_info *c)  in free_obsolete_znodes()  argument
1036 	cnext = c->cnext;  in free_obsolete_znodes()
1044 			atomic_long_inc(&c->clean_zn_cnt);  in free_obsolete_znodes()
1047 	} while (cnext != c->cnext);  in free_obsolete_znodes()
1057 static int return_gap_lebs(struct ubifs_info *c)  in return_gap_lebs()  argument
1061 	if (!c->gap_lebs)  in return_gap_lebs()
1065 	for (p = c->gap_lebs; *p != -1; p++) {  in return_gap_lebs()
1066 		err = ubifs_change_one_lp(c, *p, LPROPS_NC, LPROPS_NC, 0,  in return_gap_lebs()
1072 	kfree(c->gap_lebs);  in return_gap_lebs()
1073 	c->gap_lebs = NULL;  in return_gap_lebs()
1083 int ubifs_tnc_end_commit(struct ubifs_info *c)  in ubifs_tnc_end_commit()  argument
1087 	if (!c->cnext)  in ubifs_tnc_end_commit()
1090 	err = return_gap_lebs(c);  in ubifs_tnc_end_commit()
1094 	err = write_index(c);  in ubifs_tnc_end_commit()
1098 	mutex_lock(&c->tnc_mutex);  in ubifs_tnc_end_commit()
1100 	dbg_cmt("TNC height is %d", c->zroot.znode->level + 1);  in ubifs_tnc_end_commit()
1102 	free_obsolete_znodes(c);  in ubifs_tnc_end_commit()
1104 	c->cnext = NULL;  in ubifs_tnc_end_commit()
1105 	kfree(c->ilebs);  in ubifs_tnc_end_commit()
1106 	c->ilebs = NULL;  in ubifs_tnc_end_commit()
1108 	mutex_unlock(&c->tnc_mutex);  in ubifs_tnc_end_commit()