Lines Matching refs:bad
20 * The purpose of badblocks set/clear is to manage bad blocks ranges which are
23 * When the caller of badblocks_set() wants to set a range of bad blocks, the
27 * more complicated when the setting range covers multiple already set bad block
28 * ranges, with restrictions of maximum length of each bad range and the bad
32 * for setting a large range of bad blocks, we can handle it by dividing the
34 * bad table full conditions. Every time only a smaller piece of the bad range
36 * possible overlapped or adjacent already set bad block ranges. Then the hard
39 * When setting a range of bad blocks to the bad table, the simplified situations
40 * to be considered are, (The already set bad blocks ranges are naming with
41 * prefix E, and the setting bad blocks range is naming with prefix S)
43 * 1) A setting range is not overlapped or adjacent to any other already set bad
51 * For this situation if the bad blocks table is not full, just allocate a
52 * free slot from the bad blocks table to mark the setting range S. The
57 * 2) A setting range starts exactly at a start LBA of an already set bad blocks
67 * be merged into existing bad range E. The result is,
77 * An extra slot from the bad blocks table will be allocated for S, and head
84 * be merged into existing bad range E. The result is,
94 bad blocks range E. The result is,
117 * 3) A setting range starts before the start LBA of an already set bad blocks
138 * 4) A setting range starts after the start LBA of an already set bad blocks
140 * 4.1) If the setting range S exactly matches the tail part of already set bad
187 * 4.3) If the setting bad blocks range S is overlapped with an already set bad
208 * 5) A setting bad blocks range S is adjacent to one or more already set bad
210 * 5.1) Front merge: If the already set bad blocks range E is before setting
225 * range S right after already set range E into the bad blocks table. The
231 * 6.1) Multiple already set ranges may merge into less ones in a full bad table
239 * In the above example, when the bad blocks table is full, inserting the
241 * can be allocated from bad blocks table. In this situation a proper
242 * setting method should be go though all the setting bad blocks range and
244 * is available slot from bad blocks table, re-try again to handle more
245 * setting bad blocks ranges as many as possible.
254 * to no-space in bad blocks table, but the following E1, E2 and E3 ranges
256 * 1 free slot in bad blocks table.
260 * Since the bad blocks table is not full anymore, re-try again for the
262 * bad blocks table with previous freed slot from multiple ranges merge.
264 * In the following example, in bad blocks table, E1 is an acked bad blocks
265 * range and E2 is an unacked bad blocks range, therefore they are not able
266 * to merge into a larger range. The setting bad blocks range S is acked,
275 * the bad blocks table should be (E3 is remaining part of E2 which is not
281 * The above result is correct but not perfect. Range E1 and S in the bad
283 * occupy less bad blocks table space and make badblocks_check() faster.
290 * 6.3) Behind merge: If the already set bad blocks range E is behind the setting
313 * S in front of the already set range E in the bad blocks table. The result
320 * the bad block range setting conditions. Maybe there is some rare corner case
322 * to no space, or some ranges are not merged to save bad blocks table space.
326 * which starts before or at current setting range. Since the setting bad blocks
332 * return correct bad blocks table index immediately.
335 * Clearing a bad blocks range from the bad block table has similar idea as
337 * when the clearing range hits middle of a bad block range, the existing bad
339 * bad block table. The simplified situations to be considered are, (The already
340 * set bad blocks ranges in bad block table are naming with prefix E, and the
341 * clearing bad blocks range is naming with prefix C)
343 * 1) A clearing range is not overlapped to any already set ranges in bad block
351 * For the above situations, no bad block to be cleared and no failure
353 * 2) The clearing range hits middle of an already setting bad blocks range in
354 * the bad block table.
361 * In this situation if the bad block table is not full, the range E will be
366 * 3) The clearing range starts exactly at same LBA as an already set bad block range
367 * from the bad block table.
377 * item deleted from bad block table. The result is,
388 * For this situation the whole bad blocks range E will be cleared and its
389 * corresponded item is deleted from the bad block table.
390 * 4) The clearing range exactly ends at same LBA as an already set bad block
404 * 5) The clearing range is partially overlapped with an already set bad block
405 * range from the bad block table.
406 * 5.1) The already set bad block range is front overlapped with the clearing
425 * 5.2) The already set bad block range is behind overlaopped with the clearing
446 * All bad blocks range clearing can be simplified into the above 5 situations
448 * while-loop. The idea is similar to bad blocks range setting but much
453 * Find the range starts at-or-before 's' from bad table. The search
454 * starts from index 'hint' and stops at index 'hint_end' from the bad
476 * Find the range starts at-or-before bad->start. If 'hint' is provided
477 * (hint >= 0) then search in the bad table from hint firstly. It is
478 * very probably the wanted bad range can be found from the hint index,
481 static int prev_badblocks(struct badblocks *bb, struct badblocks_context *bad,
484 sector_t s = bad->start;
508 /* Do bisect search in bad table */
531 * Return 'true' if the range indicated by 'bad' can be backward merged
532 * with the bad range (from the bad table) index by 'behind'.
535 struct badblocks_context *bad, int behind)
537 sector_t sectors = bad->len;
538 sector_t s = bad->start;
544 BB_ACK(p[behind]) == bad->ack)
550 * Do backward merge for range indicated by 'bad' and the bad range
551 * (from the bad table) indexed by 'behind'. The return value is merged
552 * sectors from bad->len.
554 static int behind_merge(struct badblocks *bb, struct badblocks_context *bad,
557 sector_t sectors = bad->len;
558 sector_t s = bad->start;
567 p[behind] = BB_MAKE(s, BB_LEN(p[behind]) + merged, bad->ack);
576 * Return 'true' if the range indicated by 'bad' can be forward
577 * merged with the bad range (from the bad table) indexed by 'prev'.
580 struct badblocks_context *bad)
582 sector_t s = bad->start;
585 if (BB_ACK(p[prev]) == bad->ack &&
593 * Do forward merge for range indicated by 'bad' and the bad range
594 * (from bad table) indexed by 'prev'. The return value is sectors
595 * merged from bad->len.
597 static int front_merge(struct badblocks *bb, int prev, struct badblocks_context *bad)
599 sector_t sectors = bad->len;
600 sector_t s = bad->start;
616 BB_LEN(p[prev]) + merged, bad->ack);
624 * handle: If a bad range (indexed by 'prev' from bad table) exactly
625 * starts as bad->start, and the bad range ahead of 'prev' (indexed by
626 * 'prev - 1' from bad table) exactly ends at where 'prev' starts, and
628 * these two bad range (from bad table) can be combined.
630 * Return 'true' if bad ranges indexed by 'prev' and 'prev - 1' from bad
634 struct badblocks_context *bad)
639 (BB_OFFSET(p[prev]) == bad->start) &&
648 * Combine the bad ranges indexed by 'prev' and 'prev - 1' (from bad
649 * table) into one larger bad range, and the new range is indexed by
666 * Return 'true' if the range indicated by 'bad' is exactly forward
667 * overlapped with the bad range (from bad table) indexed by 'front'.
668 * Exactly forward overlap means the bad range (from bad table) indexed
669 * by 'prev' does not cover the whole range indicated by 'bad'.
672 struct badblocks_context *bad)
676 if (bad->start >= BB_OFFSET(p[front]) &&
677 bad->start < BB_END(p[front]))
683 * Return 'true' if the range indicated by 'bad' is exactly backward
684 * overlapped with the bad range (from bad table) indexed by 'behind'.
686 static bool overlap_behind(struct badblocks *bb, struct badblocks_context *bad,
691 if (bad->start < BB_OFFSET(p[behind]) &&
692 (bad->start + bad->len) > BB_OFFSET(p[behind]))
698 * Return 'true' if the range indicated by 'bad' can overwrite the bad
699 * range (from bad table) indexed by 'prev'.
701 * The range indicated by 'bad' can overwrite the bad range indexed by
703 * 1) The whole range indicated by 'bad' can cover partial or whole bad
704 * range (from bad table) indexed by 'prev'.
705 * 2) The ack value of 'bad' is larger or equal to the ack value of bad
708 * If the overwriting doesn't cover the whole bad range (from bad table)
709 * indexed by 'prev', new range might be split from existing bad range,
710 * 1) The overwrite covers head or tail part of existing bad range, 1
711 * extra bad range will be split and added into the bad table.
712 * 2) The overwrite covers middle of existing bad range, 2 extra bad
714 * added into the bad table.
719 struct badblocks_context *bad, int *extra)
724 WARN_ON(!overlap_front(bb, prev, bad));
726 if (BB_ACK(p[prev]) >= bad->ack)
729 if (BB_END(p[prev]) <= (bad->start + bad->len)) {
730 len = BB_END(p[prev]) - bad->start;
731 if (BB_OFFSET(p[prev]) == bad->start)
736 bad->len = len;
738 if (BB_OFFSET(p[prev]) == bad->start)
743 * one, an extra slot needed from bad table.
755 * Do the overwrite from the range indicated by 'bad' to the bad range
756 * (from bad table) indexed by 'prev'.
758 * extra bad range(s) might be split and added into the bad table. All
759 * the splitting cases in the bad table will be handled here.
762 struct badblocks_context *bad, int extra)
771 bad->ack);
774 if (BB_OFFSET(p[prev]) == bad->start) {
776 bad->len, bad->ack);
779 p[prev + 1] = BB_MAKE(bad->start + bad->len,
784 bad->start - BB_OFFSET(p[prev]),
793 p[prev + 1] = BB_MAKE(bad->start, bad->len, bad->ack);
798 bad->start - BB_OFFSET(p[prev]),
807 p[prev + 1] = BB_MAKE(bad->start, bad->len, bad->ack);
816 return bad->len;
820 * Explicitly insert a range indicated by 'bad' to the bad table, where
823 static int insert_at(struct badblocks *bb, int at, struct badblocks_context *bad)
830 len = min_t(sector_t, bad->len, BB_MAX_LEN);
833 p[at] = BB_MAKE(bad->start, len, bad->ack);
858 /* Do exact work to set bad block range into the bad block table */
864 struct badblocks_context bad;
892 bad.ack = acknowledged;
896 bad.start = s;
897 bad.len = sectors;
901 len = insert_at(bb, 0, &bad);
907 prev = prev_badblocks(bb, &bad, hint);
913 if (bad.len > (BB_OFFSET(p[0]) - bad.start))
914 bad.len = BB_OFFSET(p[0]) - bad.start;
915 len = insert_at(bb, 0, &bad);
923 if (overlap_behind(bb, &bad, 0)) {
924 if (can_merge_behind(bb, &bad, 0)) {
925 len = behind_merge(bb, &bad, 0);
940 if (can_combine_front(bb, prev, &bad)) {
948 if (overlap_front(bb, prev, &bad)) {
949 if (can_merge_front(bb, prev, &bad)) {
950 len = front_merge(bb, prev, &bad);
955 if (!can_front_overwrite(bb, prev, &bad, &extra)) {
962 len = front_overwrite(bb, prev, &bad, extra);
966 if (can_combine_front(bb, prev, &bad)) {
975 if (can_merge_front(bb, prev, &bad)) {
976 len = front_merge(bb, prev, &bad);
986 overlap_behind(bb, &bad, prev + 1) &&
1000 /* cannot merge and there is space in bad table */
1002 overlap_behind(bb, &bad, prev + 1))
1003 bad.len = min_t(sector_t,
1004 bad.len, BB_OFFSET(p[prev + 1]) - bad.start);
1006 len = insert_at(bb, prev + 1, &bad);
1067 * Clear the bad block range from bad block table which is front overlapped
1069 * already set bad block range are cleared. If the whole bad block range is
1074 struct badblocks_context *bad, int *deleted)
1076 sector_t sectors = bad->len;
1077 sector_t s = bad->start;
1113 * bad block range from bad block table. In this condition the existing bad
1117 struct badblocks_context *bad)
1122 sector_t sectors = bad->len;
1123 sector_t s = bad->start;
1133 /* Do the exact work to clear bad block range from the bad block table */
1136 struct badblocks_context bad;
1156 * However it is better the think a block is bad when it
1157 * isn't than to think a block is not bad when it is.
1167 bad.ack = true;
1171 bad.start = s;
1172 bad.len = sectors;
1181 prev = prev_badblocks(bb, &bad, hint);
1185 if (overlap_behind(bb, &bad, 0)) {
1192 * Both situations are to clear non-bad range,
1200 if ((prev + 1) >= bb->count && !overlap_front(bb, prev, &bad)) {
1206 /* Clear will split a bad record but the table is full */
1207 if (badblocks_full(bb) && (BB_OFFSET(p[prev]) < bad.start) &&
1208 (BB_END(p[prev]) > (bad.start + sectors))) {
1213 if (overlap_front(bb, prev, &bad)) {
1214 if ((BB_OFFSET(p[prev]) < bad.start) &&
1215 (BB_END(p[prev]) > (bad.start + bad.len))) {
1218 len = front_splitting_clear(bb, prev, &bad);
1228 len = front_clear(bb, prev, &bad, &deleted);
1238 if ((prev + 1) < bb->count && overlap_behind(bb, &bad, prev + 1)) {
1239 len = BB_OFFSET(p[prev + 1]) - bad.start;
1241 /* Clear non-bad range should be treated as successful */
1248 /* Clear non-bad range should be treated as successful */
1273 /* Do the exact work to check bad blocks range from the bad block table */
1279 struct badblocks_context bad;
1304 bad.start = s;
1305 bad.len = sectors;
1312 prev = prev_badblocks(bb, &bad, hint);
1316 ((prev + 1) >= bb->count) && !overlap_front(bb, prev, &bad)) {
1322 if ((prev >= 0) && overlap_front(bb, prev, &bad)) {
1342 if ((prev + 1) < bb->count && overlap_behind(bb, &bad, prev + 1)) {
1343 len = BB_OFFSET(p[prev + 1]) - bad.start;
1374 * badblocks_check() - check a given range for bad sectors
1381 * We can record which blocks on each device are 'bad' and so just
1383 * Entries in the bad-block table are 64bits wide. This comprises:
1384 * Length of bad-range, in sectors: 0-511 for lengths 1-512
1385 * Start of bad-range, sector offset, 54 bits (allows 8 exbibytes)
1390 * Locking of the bad-block table uses a seqlock so badblocks_check
1392 * We will sometimes want to check for bad blocks in a bi_end_io function,
1395 * When looking for a bad block we specify a range and want to
1396 * know if any block in the range is bad. So we binary-search
1402 * 0: there are no known bad blocks in the range
1403 * 1: there are known bad block which are all acknowledged
1404 * -1: there are bad blocks which have not yet been acknowledged in metadata.
1405 * plus the start/length of the first bad section we overlap.
1415 * badblocks_set() - Add a range of bad blocks to the table.
1417 * @s: first sector to mark as bad
1418 * @sectors: number of sectors to mark as bad
1419 * @acknowledged: weather to mark the bad sectors as acknowledged
1437 * badblocks_clear() - Remove a range of bad blocks to the table.
1439 * @s: first sector to mark as bad
1440 * @sectors: number of sectors to mark as bad
1457 * ack_all_badblocks() - Acknowledge all bad blocks in a list.
1489 * badblocks_show() - sysfs access to bad-blocks list
1538 * badblocks_store() - sysfs access to bad-blocks list