Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0
2 : /*
3 : * Bad block management
4 : *
5 : * - Heavily based on MD badblocks code from Neil Brown
6 : *
7 : * Copyright (c) 2015, Intel Corporation.
8 : */
9 :
10 : #include <linux/badblocks.h>
11 : #include <linux/seqlock.h>
12 : #include <linux/device.h>
13 : #include <linux/kernel.h>
14 : #include <linux/module.h>
15 : #include <linux/stddef.h>
16 : #include <linux/types.h>
17 : #include <linux/slab.h>
18 :
19 : /**
20 : * badblocks_check() - check a given range for bad sectors
21 : * @bb: the badblocks structure that holds all badblock information
22 : * @s: sector (start) at which to check for badblocks
23 : * @sectors: number of sectors to check for badblocks
24 : * @first_bad: pointer to store location of the first badblock
25 : * @bad_sectors: pointer to store number of badblocks after @first_bad
26 : *
27 : * We can record which blocks on each device are 'bad' and so just
28 : * fail those blocks, or that stripe, rather than the whole device.
29 : * Entries in the bad-block table are 64bits wide. This comprises:
30 : * Length of bad-range, in sectors: 0-511 for lengths 1-512
31 : * Start of bad-range, sector offset, 54 bits (allows 8 exbibytes)
32 : * A 'shift' can be set so that larger blocks are tracked and
33 : * consequently larger devices can be covered.
34 : * 'Acknowledged' flag - 1 bit. - the most significant bit.
35 : *
36 : * Locking of the bad-block table uses a seqlock so badblocks_check
37 : * might need to retry if it is very unlucky.
38 : * We will sometimes want to check for bad blocks in a bi_end_io function,
39 : * so we use the write_seqlock_irq variant.
40 : *
41 : * When looking for a bad block we specify a range and want to
42 : * know if any block in the range is bad. So we binary-search
43 : * to the last range that starts at-or-before the given endpoint,
44 : * (or "before the sector after the target range")
45 : * then see if it ends after the given start.
46 : *
47 : * Return:
48 : * 0: there are no known bad blocks in the range
49 : * 1: there are known bad block which are all acknowledged
50 : * -1: there are bad blocks which have not yet been acknowledged in metadata.
51 : * plus the start/length of the first bad section we overlap.
52 : */
53 0 : int badblocks_check(struct badblocks *bb, sector_t s, int sectors,
54 : sector_t *first_bad, int *bad_sectors)
55 : {
56 0 : int hi;
57 0 : int lo;
58 0 : u64 *p = bb->page;
59 0 : int rv;
60 0 : sector_t target = s + sectors;
61 0 : unsigned seq;
62 :
63 0 : if (bb->shift > 0) {
64 : /* round the start down, and the end up */
65 0 : s >>= bb->shift;
66 0 : target += (1<<bb->shift) - 1;
67 0 : target >>= bb->shift;
68 0 : sectors = target - s;
69 : }
70 : /* 'target' is now the first block after the bad range */
71 :
72 0 : retry:
73 0 : seq = read_seqbegin(&bb->lock);
74 0 : lo = 0;
75 0 : rv = 0;
76 0 : hi = bb->count;
77 :
78 : /* Binary search between lo and hi for 'target'
79 : * i.e. for the last range that starts before 'target'
80 : */
81 : /* INVARIANT: ranges before 'lo' and at-or-after 'hi'
82 : * are known not to be the last range before target.
83 : * VARIANT: hi-lo is the number of possible
84 : * ranges, and decreases until it reaches 1
85 : */
86 0 : while (hi - lo > 1) {
87 0 : int mid = (lo + hi) / 2;
88 0 : sector_t a = BB_OFFSET(p[mid]);
89 :
90 0 : if (a < target)
91 : /* This could still be the one, earlier ranges
92 : * could not.
93 : */
94 : lo = mid;
95 : else
96 : /* This and later ranges are definitely out. */
97 0 : hi = mid;
98 : }
99 : /* 'lo' might be the last that started before target, but 'hi' isn't */
100 0 : if (hi > lo) {
101 : /* need to check all range that end after 's' to see if
102 : * any are unacknowledged.
103 : */
104 0 : while (lo >= 0 &&
105 0 : BB_OFFSET(p[lo]) + BB_LEN(p[lo]) > s) {
106 0 : if (BB_OFFSET(p[lo]) < target) {
107 : /* starts before the end, and finishes after
108 : * the start, so they must overlap
109 : */
110 0 : if (rv != -1 && BB_ACK(p[lo]))
111 : rv = 1;
112 : else
113 0 : rv = -1;
114 0 : *first_bad = BB_OFFSET(p[lo]);
115 0 : *bad_sectors = BB_LEN(p[lo]);
116 : }
117 0 : lo--;
118 : }
119 : }
120 :
121 0 : if (read_seqretry(&bb->lock, seq))
122 0 : goto retry;
123 :
124 0 : return rv;
125 : }
126 : EXPORT_SYMBOL_GPL(badblocks_check);
127 :
128 0 : static void badblocks_update_acked(struct badblocks *bb)
129 : {
130 0 : u64 *p = bb->page;
131 0 : int i;
132 0 : bool unacked = false;
133 :
134 0 : if (!bb->unacked_exist)
135 : return;
136 :
137 0 : for (i = 0; i < bb->count ; i++) {
138 0 : if (!BB_ACK(p[i])) {
139 : unacked = true;
140 : break;
141 : }
142 : }
143 :
144 0 : if (!unacked)
145 0 : bb->unacked_exist = 0;
146 : }
147 :
148 : /**
149 : * badblocks_set() - Add a range of bad blocks to the table.
150 : * @bb: the badblocks structure that holds all badblock information
151 : * @s: first sector to mark as bad
152 : * @sectors: number of sectors to mark as bad
153 : * @acknowledged: weather to mark the bad sectors as acknowledged
154 : *
155 : * This might extend the table, or might contract it if two adjacent ranges
156 : * can be merged. We binary-search to find the 'insertion' point, then
157 : * decide how best to handle it.
158 : *
159 : * Return:
160 : * 0: success
161 : * 1: failed to set badblocks (out of space)
162 : */
163 0 : int badblocks_set(struct badblocks *bb, sector_t s, int sectors,
164 : int acknowledged)
165 : {
166 0 : u64 *p;
167 0 : int lo, hi;
168 0 : int rv = 0;
169 0 : unsigned long flags;
170 :
171 0 : if (bb->shift < 0)
172 : /* badblocks are disabled */
173 : return 1;
174 :
175 0 : if (bb->shift) {
176 : /* round the start down, and the end up */
177 0 : sector_t next = s + sectors;
178 :
179 0 : s >>= bb->shift;
180 0 : next += (1<<bb->shift) - 1;
181 0 : next >>= bb->shift;
182 0 : sectors = next - s;
183 : }
184 :
185 0 : write_seqlock_irqsave(&bb->lock, flags);
186 :
187 0 : p = bb->page;
188 0 : lo = 0;
189 0 : hi = bb->count;
190 : /* Find the last range that starts at-or-before 's' */
191 0 : while (hi - lo > 1) {
192 0 : int mid = (lo + hi) / 2;
193 0 : sector_t a = BB_OFFSET(p[mid]);
194 :
195 0 : if (a <= s)
196 : lo = mid;
197 : else
198 0 : hi = mid;
199 : }
200 0 : if (hi > lo && BB_OFFSET(p[lo]) > s)
201 0 : hi = lo;
202 :
203 0 : if (hi > lo) {
204 : /* we found a range that might merge with the start
205 : * of our new range
206 : */
207 0 : sector_t a = BB_OFFSET(p[lo]);
208 0 : sector_t e = a + BB_LEN(p[lo]);
209 0 : int ack = BB_ACK(p[lo]);
210 :
211 0 : if (e >= s) {
212 : /* Yes, we can merge with a previous range */
213 0 : if (s == a && s + sectors >= e)
214 : /* new range covers old */
215 : ack = acknowledged;
216 : else
217 0 : ack = ack && acknowledged;
218 :
219 0 : if (e < s + sectors)
220 : e = s + sectors;
221 0 : if (e - a <= BB_MAX_LEN) {
222 0 : p[lo] = BB_MAKE(a, e-a, ack);
223 0 : s = e;
224 : } else {
225 : /* does not all fit in one range,
226 : * make p[lo] maximal
227 : */
228 0 : if (BB_LEN(p[lo]) != BB_MAX_LEN)
229 0 : p[lo] = BB_MAKE(a, BB_MAX_LEN, ack);
230 0 : s = a + BB_MAX_LEN;
231 : }
232 0 : sectors = e - s;
233 : }
234 : }
235 0 : if (sectors && hi < bb->count) {
236 : /* 'hi' points to the first range that starts after 's'.
237 : * Maybe we can merge with the start of that range
238 : */
239 0 : sector_t a = BB_OFFSET(p[hi]);
240 0 : sector_t e = a + BB_LEN(p[hi]);
241 0 : int ack = BB_ACK(p[hi]);
242 :
243 0 : if (a <= s + sectors) {
244 : /* merging is possible */
245 0 : if (e <= s + sectors) {
246 : /* full overlap */
247 : e = s + sectors;
248 : ack = acknowledged;
249 : } else
250 0 : ack = ack && acknowledged;
251 :
252 0 : a = s;
253 0 : if (e - a <= BB_MAX_LEN) {
254 0 : p[hi] = BB_MAKE(a, e-a, ack);
255 0 : s = e;
256 : } else {
257 0 : p[hi] = BB_MAKE(a, BB_MAX_LEN, ack);
258 0 : s = a + BB_MAX_LEN;
259 : }
260 0 : sectors = e - s;
261 0 : lo = hi;
262 0 : hi++;
263 : }
264 : }
265 0 : if (sectors == 0 && hi < bb->count) {
266 : /* we might be able to combine lo and hi */
267 : /* Note: 's' is at the end of 'lo' */
268 0 : sector_t a = BB_OFFSET(p[hi]);
269 0 : int lolen = BB_LEN(p[lo]);
270 0 : int hilen = BB_LEN(p[hi]);
271 0 : int newlen = lolen + hilen - (s - a);
272 :
273 0 : if (s >= a && newlen < BB_MAX_LEN) {
274 : /* yes, we can combine them */
275 0 : int ack = BB_ACK(p[lo]) && BB_ACK(p[hi]);
276 :
277 0 : p[lo] = BB_MAKE(BB_OFFSET(p[lo]), newlen, ack);
278 0 : memmove(p + hi, p + hi + 1,
279 0 : (bb->count - hi - 1) * 8);
280 0 : bb->count--;
281 : }
282 : }
283 0 : while (sectors) {
284 : /* didn't merge (it all).
285 : * Need to add a range just before 'hi'
286 : */
287 0 : if (bb->count >= MAX_BADBLOCKS) {
288 : /* No room for more */
289 : rv = 1;
290 : break;
291 : } else {
292 0 : int this_sectors = sectors;
293 :
294 0 : memmove(p + hi + 1, p + hi,
295 0 : (bb->count - hi) * 8);
296 0 : bb->count++;
297 :
298 0 : if (this_sectors > BB_MAX_LEN)
299 : this_sectors = BB_MAX_LEN;
300 0 : p[hi] = BB_MAKE(s, this_sectors, acknowledged);
301 0 : sectors -= this_sectors;
302 0 : s += this_sectors;
303 : }
304 : }
305 :
306 0 : bb->changed = 1;
307 0 : if (!acknowledged)
308 0 : bb->unacked_exist = 1;
309 : else
310 0 : badblocks_update_acked(bb);
311 0 : write_sequnlock_irqrestore(&bb->lock, flags);
312 :
313 0 : return rv;
314 : }
315 : EXPORT_SYMBOL_GPL(badblocks_set);
316 :
317 : /**
318 : * badblocks_clear() - Remove a range of bad blocks to the table.
319 : * @bb: the badblocks structure that holds all badblock information
320 : * @s: first sector to mark as bad
321 : * @sectors: number of sectors to mark as bad
322 : *
323 : * This may involve extending the table if we spilt a region,
324 : * but it must not fail. So if the table becomes full, we just
325 : * drop the remove request.
326 : *
327 : * Return:
328 : * 0: success
329 : * 1: failed to clear badblocks
330 : */
331 0 : int badblocks_clear(struct badblocks *bb, sector_t s, int sectors)
332 : {
333 0 : u64 *p;
334 0 : int lo, hi;
335 0 : sector_t target = s + sectors;
336 0 : int rv = 0;
337 :
338 0 : if (bb->shift > 0) {
339 : /* When clearing we round the start up and the end down.
340 : * This should not matter as the shift should align with
341 : * the block size and no rounding should ever be needed.
342 : * However it is better the think a block is bad when it
343 : * isn't than to think a block is not bad when it is.
344 : */
345 0 : s += (1<<bb->shift) - 1;
346 0 : s >>= bb->shift;
347 0 : target >>= bb->shift;
348 0 : sectors = target - s;
349 : }
350 :
351 0 : write_seqlock_irq(&bb->lock);
352 :
353 0 : p = bb->page;
354 0 : lo = 0;
355 0 : hi = bb->count;
356 : /* Find the last range that starts before 'target' */
357 0 : while (hi - lo > 1) {
358 0 : int mid = (lo + hi) / 2;
359 0 : sector_t a = BB_OFFSET(p[mid]);
360 :
361 0 : if (a < target)
362 : lo = mid;
363 : else
364 0 : hi = mid;
365 : }
366 0 : if (hi > lo) {
367 : /* p[lo] is the last range that could overlap the
368 : * current range. Earlier ranges could also overlap,
369 : * but only this one can overlap the end of the range.
370 : */
371 0 : if ((BB_OFFSET(p[lo]) + BB_LEN(p[lo]) > target) &&
372 : (BB_OFFSET(p[lo]) < target)) {
373 : /* Partial overlap, leave the tail of this range */
374 0 : int ack = BB_ACK(p[lo]);
375 0 : sector_t a = BB_OFFSET(p[lo]);
376 0 : sector_t end = a + BB_LEN(p[lo]);
377 :
378 0 : if (a < s) {
379 : /* we need to split this range */
380 0 : if (bb->count >= MAX_BADBLOCKS) {
381 0 : rv = -ENOSPC;
382 0 : goto out;
383 : }
384 0 : memmove(p+lo+1, p+lo, (bb->count - lo) * 8);
385 0 : bb->count++;
386 0 : p[lo] = BB_MAKE(a, s-a, ack);
387 0 : lo++;
388 : }
389 0 : p[lo] = BB_MAKE(target, end - target, ack);
390 : /* there is no longer an overlap */
391 0 : hi = lo;
392 0 : lo--;
393 : }
394 0 : while (lo >= 0 &&
395 0 : (BB_OFFSET(p[lo]) + BB_LEN(p[lo]) > s) &&
396 : (BB_OFFSET(p[lo]) < target)) {
397 : /* This range does overlap */
398 0 : if (BB_OFFSET(p[lo]) < s) {
399 : /* Keep the early parts of this range. */
400 0 : int ack = BB_ACK(p[lo]);
401 0 : sector_t start = BB_OFFSET(p[lo]);
402 :
403 0 : p[lo] = BB_MAKE(start, s - start, ack);
404 : /* now low doesn't overlap, so.. */
405 0 : break;
406 : }
407 0 : lo--;
408 : }
409 : /* 'lo' is strictly before, 'hi' is strictly after,
410 : * anything between needs to be discarded
411 : */
412 0 : if (hi - lo > 1) {
413 0 : memmove(p+lo+1, p+hi, (bb->count - hi) * 8);
414 0 : bb->count -= (hi - lo - 1);
415 : }
416 : }
417 :
418 0 : badblocks_update_acked(bb);
419 0 : bb->changed = 1;
420 0 : out:
421 0 : write_sequnlock_irq(&bb->lock);
422 0 : return rv;
423 : }
424 : EXPORT_SYMBOL_GPL(badblocks_clear);
425 :
426 : /**
427 : * ack_all_badblocks() - Acknowledge all bad blocks in a list.
428 : * @bb: the badblocks structure that holds all badblock information
429 : *
430 : * This only succeeds if ->changed is clear. It is used by
431 : * in-kernel metadata updates
432 : */
433 0 : void ack_all_badblocks(struct badblocks *bb)
434 : {
435 0 : if (bb->page == NULL || bb->changed)
436 : /* no point even trying */
437 : return;
438 0 : write_seqlock_irq(&bb->lock);
439 :
440 0 : if (bb->changed == 0 && bb->unacked_exist) {
441 0 : u64 *p = bb->page;
442 0 : int i;
443 :
444 0 : for (i = 0; i < bb->count ; i++) {
445 0 : if (!BB_ACK(p[i])) {
446 0 : sector_t start = BB_OFFSET(p[i]);
447 0 : int len = BB_LEN(p[i]);
448 :
449 0 : p[i] = BB_MAKE(start, len, 1);
450 : }
451 : }
452 0 : bb->unacked_exist = 0;
453 : }
454 0 : write_sequnlock_irq(&bb->lock);
455 : }
456 : EXPORT_SYMBOL_GPL(ack_all_badblocks);
457 :
458 : /**
459 : * badblocks_show() - sysfs access to bad-blocks list
460 : * @bb: the badblocks structure that holds all badblock information
461 : * @page: buffer received from sysfs
462 : * @unack: weather to show unacknowledged badblocks
463 : *
464 : * Return:
465 : * Length of returned data
466 : */
467 0 : ssize_t badblocks_show(struct badblocks *bb, char *page, int unack)
468 : {
469 0 : size_t len;
470 0 : int i;
471 0 : u64 *p = bb->page;
472 0 : unsigned seq;
473 :
474 0 : if (bb->shift < 0)
475 : return 0;
476 :
477 0 : retry:
478 0 : seq = read_seqbegin(&bb->lock);
479 :
480 0 : len = 0;
481 0 : i = 0;
482 :
483 0 : while (len < PAGE_SIZE && i < bb->count) {
484 0 : sector_t s = BB_OFFSET(p[i]);
485 0 : unsigned int length = BB_LEN(p[i]);
486 0 : int ack = BB_ACK(p[i]);
487 :
488 0 : i++;
489 :
490 0 : if (unack && ack)
491 0 : continue;
492 :
493 0 : len += snprintf(page+len, PAGE_SIZE-len, "%llu %u\n",
494 : (unsigned long long)s << bb->shift,
495 0 : length << bb->shift);
496 : }
497 0 : if (unack && len == 0)
498 0 : bb->unacked_exist = 0;
499 :
500 0 : if (read_seqretry(&bb->lock, seq))
501 0 : goto retry;
502 :
503 0 : return len;
504 : }
505 : EXPORT_SYMBOL_GPL(badblocks_show);
506 :
507 : /**
508 : * badblocks_store() - sysfs access to bad-blocks list
509 : * @bb: the badblocks structure that holds all badblock information
510 : * @page: buffer received from sysfs
511 : * @len: length of data received from sysfs
512 : * @unack: weather to show unacknowledged badblocks
513 : *
514 : * Return:
515 : * Length of the buffer processed or -ve error.
516 : */
517 0 : ssize_t badblocks_store(struct badblocks *bb, const char *page, size_t len,
518 : int unack)
519 : {
520 0 : unsigned long long sector;
521 0 : int length;
522 0 : char newline;
523 :
524 0 : switch (sscanf(page, "%llu %d%c", §or, &length, &newline)) {
525 0 : case 3:
526 0 : if (newline != '\n')
527 : return -EINVAL;
528 0 : fallthrough;
529 : case 2:
530 0 : if (length <= 0)
531 : return -EINVAL;
532 0 : break;
533 : default:
534 : return -EINVAL;
535 : }
536 :
537 0 : if (badblocks_set(bb, sector, length, !unack))
538 : return -ENOSPC;
539 : else
540 0 : return len;
541 : }
542 : EXPORT_SYMBOL_GPL(badblocks_store);
543 :
544 0 : static int __badblocks_init(struct device *dev, struct badblocks *bb,
545 : int enable)
546 : {
547 0 : bb->dev = dev;
548 0 : bb->count = 0;
549 0 : if (enable)
550 0 : bb->shift = 0;
551 : else
552 0 : bb->shift = -1;
553 0 : if (dev)
554 0 : bb->page = devm_kzalloc(dev, PAGE_SIZE, GFP_KERNEL);
555 : else
556 0 : bb->page = kzalloc(PAGE_SIZE, GFP_KERNEL);
557 0 : if (!bb->page) {
558 0 : bb->shift = -1;
559 0 : return -ENOMEM;
560 : }
561 0 : seqlock_init(&bb->lock);
562 :
563 0 : return 0;
564 : }
565 :
566 : /**
567 : * badblocks_init() - initialize the badblocks structure
568 : * @bb: the badblocks structure that holds all badblock information
569 : * @enable: weather to enable badblocks accounting
570 : *
571 : * Return:
572 : * 0: success
573 : * -ve errno: on error
574 : */
575 0 : int badblocks_init(struct badblocks *bb, int enable)
576 : {
577 0 : return __badblocks_init(NULL, bb, enable);
578 : }
579 : EXPORT_SYMBOL_GPL(badblocks_init);
580 :
581 0 : int devm_init_badblocks(struct device *dev, struct badblocks *bb)
582 : {
583 0 : if (!bb)
584 : return -EINVAL;
585 0 : return __badblocks_init(dev, bb, 1);
586 : }
587 : EXPORT_SYMBOL_GPL(devm_init_badblocks);
588 :
589 : /**
590 : * badblocks_exit() - free the badblocks structure
591 : * @bb: the badblocks structure that holds all badblock information
592 : */
593 0 : void badblocks_exit(struct badblocks *bb)
594 : {
595 0 : if (!bb)
596 : return;
597 0 : if (bb->dev)
598 0 : devm_kfree(bb->dev, bb->page);
599 : else
600 0 : kfree(bb->page);
601 0 : bb->page = NULL;
602 : }
603 : EXPORT_SYMBOL_GPL(badblocks_exit);
|
