Merge remote-tracking branch 'stable/linux-5.15.y' into rpi-5.15.y
[platform/kernel/linux-rpi.git] / block / badblocks.c
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 int badblocks_check(struct badblocks *bb, sector_t s, int sectors,
54                         sector_t *first_bad, int *bad_sectors)
55 {
56         int hi;
57         int lo;
58         u64 *p = bb->page;
59         int rv;
60         sector_t target = s + sectors;
61         unsigned seq;
62
63         if (bb->shift > 0) {
64                 /* round the start down, and the end up */
65                 s >>= bb->shift;
66                 target += (1<<bb->shift) - 1;
67                 target >>= bb->shift;
68                 sectors = target - s;
69         }
70         /* 'target' is now the first block after the bad range */
71
72 retry:
73         seq = read_seqbegin(&bb->lock);
74         lo = 0;
75         rv = 0;
76         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         while (hi - lo > 1) {
87                 int mid = (lo + hi) / 2;
88                 sector_t a = BB_OFFSET(p[mid]);
89
90                 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                         hi = mid;
98         }
99         /* 'lo' might be the last that started before target, but 'hi' isn't */
100         if (hi > lo) {
101                 /* need to check all range that end after 's' to see if
102                  * any are unacknowledged.
103                  */
104                 while (lo >= 0 &&
105                        BB_OFFSET(p[lo]) + BB_LEN(p[lo]) > s) {
106                         if (BB_OFFSET(p[lo]) < target) {
107                                 /* starts before the end, and finishes after
108                                  * the start, so they must overlap
109                                  */
110                                 if (rv != -1 && BB_ACK(p[lo]))
111                                         rv = 1;
112                                 else
113                                         rv = -1;
114                                 *first_bad = BB_OFFSET(p[lo]);
115                                 *bad_sectors = BB_LEN(p[lo]);
116                         }
117                         lo--;
118                 }
119         }
120
121         if (read_seqretry(&bb->lock, seq))
122                 goto retry;
123
124         return rv;
125 }
126 EXPORT_SYMBOL_GPL(badblocks_check);
127
128 static void badblocks_update_acked(struct badblocks *bb)
129 {
130         u64 *p = bb->page;
131         int i;
132         bool unacked = false;
133
134         if (!bb->unacked_exist)
135                 return;
136
137         for (i = 0; i < bb->count ; i++) {
138                 if (!BB_ACK(p[i])) {
139                         unacked = true;
140                         break;
141                 }
142         }
143
144         if (!unacked)
145                 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 int badblocks_set(struct badblocks *bb, sector_t s, int sectors,
164                         int acknowledged)
165 {
166         u64 *p;
167         int lo, hi;
168         int rv = 0;
169         unsigned long flags;
170
171         if (bb->shift < 0)
172                 /* badblocks are disabled */
173                 return 1;
174
175         if (bb->shift) {
176                 /* round the start down, and the end up */
177                 sector_t next = s + sectors;
178
179                 s >>= bb->shift;
180                 next += (1<<bb->shift) - 1;
181                 next >>= bb->shift;
182                 sectors = next - s;
183         }
184
185         write_seqlock_irqsave(&bb->lock, flags);
186
187         p = bb->page;
188         lo = 0;
189         hi = bb->count;
190         /* Find the last range that starts at-or-before 's' */
191         while (hi - lo > 1) {
192                 int mid = (lo + hi) / 2;
193                 sector_t a = BB_OFFSET(p[mid]);
194
195                 if (a <= s)
196                         lo = mid;
197                 else
198                         hi = mid;
199         }
200         if (hi > lo && BB_OFFSET(p[lo]) > s)
201                 hi = lo;
202
203         if (hi > lo) {
204                 /* we found a range that might merge with the start
205                  * of our new range
206                  */
207                 sector_t a = BB_OFFSET(p[lo]);
208                 sector_t e = a + BB_LEN(p[lo]);
209                 int ack = BB_ACK(p[lo]);
210
211                 if (e >= s) {
212                         /* Yes, we can merge with a previous range */
213                         if (s == a && s + sectors >= e)
214                                 /* new range covers old */
215                                 ack = acknowledged;
216                         else
217                                 ack = ack && acknowledged;
218
219                         if (e < s + sectors)
220                                 e = s + sectors;
221                         if (e - a <= BB_MAX_LEN) {
222                                 p[lo] = BB_MAKE(a, e-a, ack);
223                                 s = e;
224                         } else {
225                                 /* does not all fit in one range,
226                                  * make p[lo] maximal
227                                  */
228                                 if (BB_LEN(p[lo]) != BB_MAX_LEN)
229                                         p[lo] = BB_MAKE(a, BB_MAX_LEN, ack);
230                                 s = a + BB_MAX_LEN;
231                         }
232                         sectors = e - s;
233                 }
234         }
235         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                 sector_t a = BB_OFFSET(p[hi]);
240                 sector_t e = a + BB_LEN(p[hi]);
241                 int ack = BB_ACK(p[hi]);
242
243                 if (a <= s + sectors) {
244                         /* merging is possible */
245                         if (e <= s + sectors) {
246                                 /* full overlap */
247                                 e = s + sectors;
248                                 ack = acknowledged;
249                         } else
250                                 ack = ack && acknowledged;
251
252                         a = s;
253                         if (e - a <= BB_MAX_LEN) {
254                                 p[hi] = BB_MAKE(a, e-a, ack);
255                                 s = e;
256                         } else {
257                                 p[hi] = BB_MAKE(a, BB_MAX_LEN, ack);
258                                 s = a + BB_MAX_LEN;
259                         }
260                         sectors = e - s;
261                         lo = hi;
262                         hi++;
263                 }
264         }
265         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                 sector_t a = BB_OFFSET(p[hi]);
269                 int lolen = BB_LEN(p[lo]);
270                 int hilen = BB_LEN(p[hi]);
271                 int newlen = lolen + hilen - (s - a);
272
273                 if (s >= a && newlen < BB_MAX_LEN) {
274                         /* yes, we can combine them */
275                         int ack = BB_ACK(p[lo]) && BB_ACK(p[hi]);
276
277                         p[lo] = BB_MAKE(BB_OFFSET(p[lo]), newlen, ack);
278                         memmove(p + hi, p + hi + 1,
279                                 (bb->count - hi - 1) * 8);
280                         bb->count--;
281                 }
282         }
283         while (sectors) {
284                 /* didn't merge (it all).
285                  * Need to add a range just before 'hi'
286                  */
287                 if (bb->count >= MAX_BADBLOCKS) {
288                         /* No room for more */
289                         rv = 1;
290                         break;
291                 } else {
292                         int this_sectors = sectors;
293
294                         memmove(p + hi + 1, p + hi,
295                                 (bb->count - hi) * 8);
296                         bb->count++;
297
298                         if (this_sectors > BB_MAX_LEN)
299                                 this_sectors = BB_MAX_LEN;
300                         p[hi] = BB_MAKE(s, this_sectors, acknowledged);
301                         sectors -= this_sectors;
302                         s += this_sectors;
303                 }
304         }
305
306         bb->changed = 1;
307         if (!acknowledged)
308                 bb->unacked_exist = 1;
309         else
310                 badblocks_update_acked(bb);
311         write_sequnlock_irqrestore(&bb->lock, flags);
312
313         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 int badblocks_clear(struct badblocks *bb, sector_t s, int sectors)
332 {
333         u64 *p;
334         int lo, hi;
335         sector_t target = s + sectors;
336         int rv = 0;
337
338         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                 s += (1<<bb->shift) - 1;
346                 s >>= bb->shift;
347                 target >>= bb->shift;
348                 sectors = target - s;
349         }
350
351         write_seqlock_irq(&bb->lock);
352
353         p = bb->page;
354         lo = 0;
355         hi = bb->count;
356         /* Find the last range that starts before 'target' */
357         while (hi - lo > 1) {
358                 int mid = (lo + hi) / 2;
359                 sector_t a = BB_OFFSET(p[mid]);
360
361                 if (a < target)
362                         lo = mid;
363                 else
364                         hi = mid;
365         }
366         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                 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                         int ack = BB_ACK(p[lo]);
375                         sector_t a = BB_OFFSET(p[lo]);
376                         sector_t end = a + BB_LEN(p[lo]);
377
378                         if (a < s) {
379                                 /* we need to split this range */
380                                 if (bb->count >= MAX_BADBLOCKS) {
381                                         rv = -ENOSPC;
382                                         goto out;
383                                 }
384                                 memmove(p+lo+1, p+lo, (bb->count - lo) * 8);
385                                 bb->count++;
386                                 p[lo] = BB_MAKE(a, s-a, ack);
387                                 lo++;
388                         }
389                         p[lo] = BB_MAKE(target, end - target, ack);
390                         /* there is no longer an overlap */
391                         hi = lo;
392                         lo--;
393                 }
394                 while (lo >= 0 &&
395                        (BB_OFFSET(p[lo]) + BB_LEN(p[lo]) > s) &&
396                        (BB_OFFSET(p[lo]) < target)) {
397                         /* This range does overlap */
398                         if (BB_OFFSET(p[lo]) < s) {
399                                 /* Keep the early parts of this range. */
400                                 int ack = BB_ACK(p[lo]);
401                                 sector_t start = BB_OFFSET(p[lo]);
402
403                                 p[lo] = BB_MAKE(start, s - start, ack);
404                                 /* now low doesn't overlap, so.. */
405                                 break;
406                         }
407                         lo--;
408                 }
409                 /* 'lo' is strictly before, 'hi' is strictly after,
410                  * anything between needs to be discarded
411                  */
412                 if (hi - lo > 1) {
413                         memmove(p+lo+1, p+hi, (bb->count - hi) * 8);
414                         bb->count -= (hi - lo - 1);
415                 }
416         }
417
418         badblocks_update_acked(bb);
419         bb->changed = 1;
420 out:
421         write_sequnlock_irq(&bb->lock);
422         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 void ack_all_badblocks(struct badblocks *bb)
434 {
435         if (bb->page == NULL || bb->changed)
436                 /* no point even trying */
437                 return;
438         write_seqlock_irq(&bb->lock);
439
440         if (bb->changed == 0 && bb->unacked_exist) {
441                 u64 *p = bb->page;
442                 int i;
443
444                 for (i = 0; i < bb->count ; i++) {
445                         if (!BB_ACK(p[i])) {
446                                 sector_t start = BB_OFFSET(p[i]);
447                                 int len = BB_LEN(p[i]);
448
449                                 p[i] = BB_MAKE(start, len, 1);
450                         }
451                 }
452                 bb->unacked_exist = 0;
453         }
454         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 ssize_t badblocks_show(struct badblocks *bb, char *page, int unack)
468 {
469         size_t len;
470         int i;
471         u64 *p = bb->page;
472         unsigned seq;
473
474         if (bb->shift < 0)
475                 return 0;
476
477 retry:
478         seq = read_seqbegin(&bb->lock);
479
480         len = 0;
481         i = 0;
482
483         while (len < PAGE_SIZE && i < bb->count) {
484                 sector_t s = BB_OFFSET(p[i]);
485                 unsigned int length = BB_LEN(p[i]);
486                 int ack = BB_ACK(p[i]);
487
488                 i++;
489
490                 if (unack && ack)
491                         continue;
492
493                 len += snprintf(page+len, PAGE_SIZE-len, "%llu %u\n",
494                                 (unsigned long long)s << bb->shift,
495                                 length << bb->shift);
496         }
497         if (unack && len == 0)
498                 bb->unacked_exist = 0;
499
500         if (read_seqretry(&bb->lock, seq))
501                 goto retry;
502
503         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 ssize_t badblocks_store(struct badblocks *bb, const char *page, size_t len,
518                         int unack)
519 {
520         unsigned long long sector;
521         int length;
522         char newline;
523
524         switch (sscanf(page, "%llu %d%c", &sector, &length, &newline)) {
525         case 3:
526                 if (newline != '\n')
527                         return -EINVAL;
528                 fallthrough;
529         case 2:
530                 if (length <= 0)
531                         return -EINVAL;
532                 break;
533         default:
534                 return -EINVAL;
535         }
536
537         if (badblocks_set(bb, sector, length, !unack))
538                 return -ENOSPC;
539         else
540                 return len;
541 }
542 EXPORT_SYMBOL_GPL(badblocks_store);
543
544 static int __badblocks_init(struct device *dev, struct badblocks *bb,
545                 int enable)
546 {
547         bb->dev = dev;
548         bb->count = 0;
549         if (enable)
550                 bb->shift = 0;
551         else
552                 bb->shift = -1;
553         if (dev)
554                 bb->page = devm_kzalloc(dev, PAGE_SIZE, GFP_KERNEL);
555         else
556                 bb->page = kzalloc(PAGE_SIZE, GFP_KERNEL);
557         if (!bb->page) {
558                 bb->shift = -1;
559                 return -ENOMEM;
560         }
561         seqlock_init(&bb->lock);
562
563         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 int badblocks_init(struct badblocks *bb, int enable)
576 {
577         return __badblocks_init(NULL, bb, enable);
578 }
579 EXPORT_SYMBOL_GPL(badblocks_init);
580
581 int devm_init_badblocks(struct device *dev, struct badblocks *bb)
582 {
583         if (!bb)
584                 return -EINVAL;
585         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 void badblocks_exit(struct badblocks *bb)
594 {
595         if (!bb)
596                 return;
597         if (bb->dev)
598                 devm_kfree(bb->dev, bb->page);
599         else
600                 kfree(bb->page);
601         bb->page = NULL;
602 }
603 EXPORT_SYMBOL_GPL(badblocks_exit);