457 static int prev_by_hint(struct badblocks *bb, sector_t s, int hint)  in prev_by_hint()  argument
460 	u64 *p = bb->page;  in prev_by_hint()
463 	while ((hint < hint_end) && ((hint + 1) <= bb->count) &&  in prev_by_hint()
465 		if ((hint + 1) == bb->count || BB_OFFSET(p[hint + 1]) > s) {  in prev_by_hint()
481 static int prev_badblocks(struct badblocks *bb, struct badblocks_context *bad,  in prev_badblocks()  argument
489 	if (!bb->count)  in prev_badblocks()
493 		ret = prev_by_hint(bb, s, hint);  in prev_badblocks()
499 	hi = bb->count;  in prev_badblocks()
500 	p = bb->page;  in prev_badblocks()
534 static bool can_merge_front(struct badblocks *bb, int prev,  in can_merge_front()  argument
538 	u64 *p = bb->page;  in can_merge_front()
552 static int front_merge(struct badblocks *bb, int prev, struct badblocks_context *bad)  in front_merge()  argument
556 	u64 *p = bb->page;  in front_merge()
565 		if ((prev + 1) < bb->count &&  in front_merge()
588 static bool can_combine_front(struct badblocks *bb, int prev,  in can_combine_front()  argument
591 	u64 *p = bb->page;  in can_combine_front()
609 static void front_combine(struct badblocks *bb, int prev)  in front_combine()  argument
611 	u64 *p = bb->page;  in front_combine()
616 	if ((prev + 1) < bb->count)  in front_combine()
617 		memmove(p + prev, p + prev + 1, (bb->count - prev - 1) * 8);  in front_combine()
626 static bool overlap_front(struct badblocks *bb, int front,  in overlap_front()  argument
629 	u64 *p = bb->page;  in overlap_front()
641 static bool overlap_behind(struct badblocks *bb, struct badblocks_context *bad,  in overlap_behind()  argument
644 	u64 *p = bb->page;  in overlap_behind()
673 static bool can_front_overwrite(struct badblocks *bb, int prev,  in can_front_overwrite()  argument
676 	u64 *p = bb->page;  in can_front_overwrite()
679 	WARN_ON(!overlap_front(bb, prev, bad));  in can_front_overwrite()
703 	if ((bb->count + (*extra)) > MAX_BADBLOCKS)  in can_front_overwrite()
716 static int front_overwrite(struct badblocks *bb, int prev,  in front_overwrite()  argument
719 	u64 *p = bb->page;  in front_overwrite()
733 				(bb->count - prev - 1) * 8);  in front_overwrite()
747 				(bb->count - prev - 1) * 8);  in front_overwrite()
761 			(bb->count - prev - 1) * 8);  in front_overwrite()
778 static int insert_at(struct badblocks *bb, int at, struct badblocks_context *bad)  in insert_at()  argument
780 	u64 *p = bb->page;  in insert_at()
783 	WARN_ON(badblocks_full(bb));  in insert_at()
786 	if (at < bb->count)  in insert_at()
787 		memmove(p + at + 1, p + at, (bb->count - at) * 8);  in insert_at()
793 static void badblocks_update_acked(struct badblocks *bb)  in badblocks_update_acked()  argument
796 	u64 *p = bb->page;  in badblocks_update_acked()
799 	if (!bb->unacked_exist)  in badblocks_update_acked()
802 	for (i = 0; i < bb->count ; i++) {  in badblocks_update_acked()
810 		bb->unacked_exist = 0;  in badblocks_update_acked()
817 static bool try_adjacent_combine(struct badblocks *bb, int prev)  in try_adjacent_combine()  argument
819 	u64 *p = bb->page;  in try_adjacent_combine()
821 	if (prev >= 0 && (prev + 1) < bb->count &&  in try_adjacent_combine()
829 		if ((prev + 2) < bb->count)  in try_adjacent_combine()
831 				(bb->count -  (prev + 2)) * 8);  in try_adjacent_combine()
832 		bb->count--;  in try_adjacent_combine()
839 static bool _badblocks_set(struct badblocks *bb, sector_t s, sector_t sectors,  in _badblocks_set()  argument
848 	if (bb->shift < 0)  in _badblocks_set()
856 	if (bb->shift) {  in _badblocks_set()
860 		rounddown(s, 1 << bb->shift);  in _badblocks_set()
861 		roundup(next, 1 << bb->shift);  in _badblocks_set()
865 	write_seqlock_irqsave(&bb->lock, flags);  in _badblocks_set()
868 	p = bb->page;  in _badblocks_set()
875 	if (badblocks_full(bb))  in _badblocks_set()
878 	if (badblocks_empty(bb)) {  in _badblocks_set()
879 		len = insert_at(bb, 0, &bad);  in _badblocks_set()
880 		bb->count++;  in _badblocks_set()
885 	prev = prev_badblocks(bb, &bad, hint);  in _badblocks_set()
892 		len = insert_at(bb, 0, &bad);  in _badblocks_set()
893 		bb->count++;  in _badblocks_set()
900 	if (can_combine_front(bb, prev, &bad)) {  in _badblocks_set()
901 		front_combine(bb, prev);  in _badblocks_set()
902 		bb->count--;  in _badblocks_set()
908 	if (can_merge_front(bb, prev, &bad)) {  in _badblocks_set()
909 		len = front_merge(bb, prev, &bad);  in _badblocks_set()
915 	if (overlap_front(bb, prev, &bad)) {  in _badblocks_set()
918 		if (!can_front_overwrite(bb, prev, &bad, &extra)) {  in _badblocks_set()
928 		len = front_overwrite(bb, prev, &bad, extra);  in _badblocks_set()
930 		bb->count += extra;  in _badblocks_set()
932 		if (can_combine_front(bb, prev, &bad)) {  in _badblocks_set()
933 			front_combine(bb, prev);  in _badblocks_set()
934 			bb->count--;  in _badblocks_set()
942 	if ((prev + 1) < bb->count &&  in _badblocks_set()
943 	    overlap_behind(bb, &bad, prev + 1))  in _badblocks_set()
947 	len = insert_at(bb, prev + 1, &bad);  in _badblocks_set()
948 	bb->count++;  in _badblocks_set()
964 	try_adjacent_combine(bb, prev);  in _badblocks_set()
968 		set_changed(bb);  in _badblocks_set()
971 			bb->unacked_exist = 1;  in _badblocks_set()
973 			badblocks_update_acked(bb);  in _badblocks_set()
976 	write_sequnlock_irqrestore(&bb->lock, flags);  in _badblocks_set()
988 static int front_clear(struct badblocks *bb, int prev,  in front_clear()  argument
993 	u64 *p = bb->page;  in front_clear()
1006 			if ((prev + 1) < bb->count)  in front_clear()
1008 				       (bb->count - prev - 1) * 8);  in front_clear()
1031 static int front_splitting_clear(struct badblocks *bb, int prev,  in front_splitting_clear()  argument
1034 	u64 *p = bb->page;  in front_splitting_clear()
1043 	memmove(p + prev + 2, p + prev + 1, (bb->count - prev - 1) * 8);  in front_splitting_clear()
1049 static bool _badblocks_clear(struct badblocks *bb, sector_t s, sector_t sectors)  in _badblocks_clear()  argument
1056 	if (bb->shift < 0)  in _badblocks_clear()
1064 	if (bb->shift) {  in _badblocks_clear()
1074 		roundup(s, 1 << bb->shift);  in _badblocks_clear()
1075 		rounddown(target, 1 << bb->shift);  in _badblocks_clear()
1079 	write_seqlock_irq(&bb->lock);  in _badblocks_clear()
1082 	p = bb->page;  in _badblocks_clear()
1088 	if (badblocks_empty(bb)) {  in _badblocks_clear()
1095 	prev = prev_badblocks(bb, &bad, hint);  in _badblocks_clear()
1099 		if (overlap_behind(bb, &bad, 0)) {  in _badblocks_clear()
1114 	if ((prev + 1) >= bb->count && !overlap_front(bb, prev, &bad)) {  in _badblocks_clear()
1121 	if (badblocks_full(bb) && (BB_OFFSET(p[prev]) < bad.start) &&  in _badblocks_clear()
1127 	if (overlap_front(bb, prev, &bad)) {  in _badblocks_clear()
1131 			if ((bb->count + 1) <= MAX_BADBLOCKS) {  in _badblocks_clear()
1132 				len = front_splitting_clear(bb, prev, &bad);  in _badblocks_clear()
1133 				bb->count += 1;  in _badblocks_clear()
1142 			len = front_clear(bb, prev, &bad, &deleted);  in _badblocks_clear()
1143 			bb->count -= deleted;  in _badblocks_clear()
1152 	if ((prev + 1) < bb->count && overlap_behind(bb, &bad, prev + 1)) {  in _badblocks_clear()
1173 		badblocks_update_acked(bb);  in _badblocks_clear()
1174 		set_changed(bb);  in _badblocks_clear()
1177 	write_sequnlock_irq(&bb->lock);  in _badblocks_clear()
1186 static int _badblocks_check(struct badblocks *bb, sector_t s, sector_t sectors,  in _badblocks_check()  argument
1193 	u64 *p = bb->page;  in _badblocks_check()
1200 	if (badblocks_empty(bb)) {  in _badblocks_check()
1205 	prev = prev_badblocks(bb, &bad, hint);  in _badblocks_check()
1209 	    ((prev + 1) >= bb->count) && !overlap_front(bb, prev, &bad)) {  in _badblocks_check()
1215 	if ((prev >= 0) && overlap_front(bb, prev, &bad)) {  in _badblocks_check()
1235 	if ((prev + 1) < bb->count && overlap_behind(bb, &bad, prev + 1)) {  in _badblocks_check()
1298 int badblocks_check(struct badblocks *bb, sector_t s, sector_t sectors,  in badblocks_check()  argument
1304 	WARN_ON(bb->shift < 0 || sectors == 0);  in badblocks_check()
1306 	if (bb->shift > 0) {  in badblocks_check()
1310 		rounddown(s, 1 << bb->shift);  in badblocks_check()
1311 		roundup(target, 1 << bb->shift);  in badblocks_check()
1316 	seq = read_seqbegin(&bb->lock);  in badblocks_check()
1317 	rv = _badblocks_check(bb, s, sectors, first_bad, bad_sectors);  in badblocks_check()
1318 	if (read_seqretry(&bb->lock, seq))  in badblocks_check()
1341 bool badblocks_set(struct badblocks *bb, sector_t s, sector_t sectors,  in badblocks_set()  argument
1344 	return _badblocks_set(bb, s, sectors, acknowledged);  in badblocks_set()
1362 bool badblocks_clear(struct badblocks *bb, sector_t s, sector_t sectors)  in badblocks_clear()  argument
1364 	return _badblocks_clear(bb, s, sectors);  in badblocks_clear()
1375 void ack_all_badblocks(struct badblocks *bb)  in ack_all_badblocks()  argument
1377 	if (bb->page == NULL || bb->changed)  in ack_all_badblocks()
1380 	write_seqlock_irq(&bb->lock);  in ack_all_badblocks()
1382 	if (bb->changed == 0 && bb->unacked_exist) {  in ack_all_badblocks()
1383 		u64 *p = bb->page;  in ack_all_badblocks()
1386 		for (i = 0; i < bb->count ; i++) {  in ack_all_badblocks()
1395 		for (i = 0; i < bb->count ; i++)  in ack_all_badblocks()
1396 			while (try_adjacent_combine(bb, i))  in ack_all_badblocks()
1399 		bb->unacked_exist = 0;  in ack_all_badblocks()
1401 	write_sequnlock_irq(&bb->lock);  in ack_all_badblocks()
1414 ssize_t badblocks_show(struct badblocks *bb, char *page, int unack)  in badblocks_show()  argument
1418 	u64 *p = bb->page;  in badblocks_show()
1421 	if (bb->shift < 0)  in badblocks_show()
1425 	seq = read_seqbegin(&bb->lock);  in badblocks_show()
1430 	while (len < PAGE_SIZE && i < bb->count) {  in badblocks_show()
1441 				(unsigned long long)s << bb->shift,  in badblocks_show()
1442 				length << bb->shift);  in badblocks_show()
1445 		bb->unacked_exist = 0;  in badblocks_show()
1447 	if (read_seqretry(&bb->lock, seq))  in badblocks_show()
1464 ssize_t badblocks_store(struct badblocks *bb, const char *page, size_t len,  in badblocks_store()  argument
1484 	if (!badblocks_set(bb, sector, length, !unack))  in badblocks_store()
1491 static int __badblocks_init(struct device *dev, struct badblocks *bb,  in __badblocks_init()  argument
1494 	bb->dev = dev;  in __badblocks_init()
1495 	bb->count = 0;  in __badblocks_init()
1497 		bb->shift = 0;  in __badblocks_init()
1499 		bb->shift = -1;  in __badblocks_init()
1501 		bb->page = devm_kzalloc(dev, PAGE_SIZE, GFP_KERNEL);  in __badblocks_init()
1503 		bb->page = kzalloc(PAGE_SIZE, GFP_KERNEL);  in __badblocks_init()
1504 	if (!bb->page) {  in __badblocks_init()
1505 		bb->shift = -1;  in __badblocks_init()
1508 	seqlock_init(&bb->lock);  in __badblocks_init()
1522 int badblocks_init(struct badblocks *bb, int enable)  in badblocks_init()  argument
1524 	return __badblocks_init(NULL, bb, enable);  in badblocks_init()
1528 int devm_init_badblocks(struct device *dev, struct badblocks *bb)  in devm_init_badblocks()  argument
1530 	if (!bb)  in devm_init_badblocks()
1532 	return __badblocks_init(dev, bb, 1);  in devm_init_badblocks()
1540 void badblocks_exit(struct badblocks *bb)  in badblocks_exit()  argument
1542 	if (!bb)  in badblocks_exit()
1544 	if (bb->dev)  in badblocks_exit()
1545 		devm_kfree(bb->dev, bb->page);  in badblocks_exit()
1547 		kfree(bb->page);  in badblocks_exit()
1548 	bb->page = NULL;  in badblocks_exit()