1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56#include <linux/slab.h>
57#include <linux/pagemap.h>
58#include <linux/list_sort.h>
59#include "ubifs.h"
60
61
62
63
64
65
66#define SOFT_LEBS_LIMIT 4
67#define HARD_LEBS_LIMIT 32
68
69
70
71
72
73
74
75
76
77
78
79
80
81static int switch_gc_head(struct ubifs_info *c)
82{
83 int err, gc_lnum = c->gc_lnum;
84 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
85
86 ubifs_assert(gc_lnum != -1);
87 dbg_gc("switch GC head from LEB %d:%d to LEB %d (waste %d bytes)",
88 wbuf->lnum, wbuf->offs + wbuf->used, gc_lnum,
89 c->leb_size - wbuf->offs - wbuf->used);
90
91 err = ubifs_wbuf_sync_nolock(wbuf);
92 if (err)
93 return err;
94
95
96
97
98
99 err = ubifs_leb_unmap(c, gc_lnum);
100 if (err)
101 return err;
102
103 err = ubifs_add_bud_to_log(c, GCHD, gc_lnum, 0);
104 if (err)
105 return err;
106
107 c->gc_lnum = -1;
108 err = ubifs_wbuf_seek_nolock(wbuf, gc_lnum, 0);
109 return err;
110}
111
112
113
114
115
116
117
118
119
120
121static int data_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
122{
123 ino_t inuma, inumb;
124 struct ubifs_info *c = priv;
125 struct ubifs_scan_node *sa, *sb;
126
127 cond_resched();
128 if (a == b)
129 return 0;
130
131 sa = list_entry(a, struct ubifs_scan_node, list);
132 sb = list_entry(b, struct ubifs_scan_node, list);
133
134 ubifs_assert(key_type(c, &sa->key) == UBIFS_DATA_KEY);
135 ubifs_assert(key_type(c, &sb->key) == UBIFS_DATA_KEY);
136 ubifs_assert(sa->type == UBIFS_DATA_NODE);
137 ubifs_assert(sb->type == UBIFS_DATA_NODE);
138
139 inuma = key_inum(c, &sa->key);
140 inumb = key_inum(c, &sb->key);
141
142 if (inuma == inumb) {
143 unsigned int blka = key_block(c, &sa->key);
144 unsigned int blkb = key_block(c, &sb->key);
145
146 if (blka <= blkb)
147 return -1;
148 } else if (inuma <= inumb)
149 return -1;
150
151 return 1;
152}
153
154
155
156
157
158
159
160
161
162
163
164static int nondata_nodes_cmp(void *priv, struct list_head *a,
165 struct list_head *b)
166{
167 ino_t inuma, inumb;
168 struct ubifs_info *c = priv;
169 struct ubifs_scan_node *sa, *sb;
170
171 cond_resched();
172 if (a == b)
173 return 0;
174
175 sa = list_entry(a, struct ubifs_scan_node, list);
176 sb = list_entry(b, struct ubifs_scan_node, list);
177
178 ubifs_assert(key_type(c, &sa->key) != UBIFS_DATA_KEY &&
179 key_type(c, &sb->key) != UBIFS_DATA_KEY);
180 ubifs_assert(sa->type != UBIFS_DATA_NODE &&
181 sb->type != UBIFS_DATA_NODE);
182
183
184 if (sa->type == UBIFS_INO_NODE) {
185 if (sb->type == UBIFS_INO_NODE)
186 return sb->len - sa->len;
187 return -1;
188 }
189 if (sb->type == UBIFS_INO_NODE)
190 return 1;
191
192 ubifs_assert(key_type(c, &sa->key) == UBIFS_DENT_KEY ||
193 key_type(c, &sa->key) == UBIFS_XENT_KEY);
194 ubifs_assert(key_type(c, &sb->key) == UBIFS_DENT_KEY ||
195 key_type(c, &sb->key) == UBIFS_XENT_KEY);
196 ubifs_assert(sa->type == UBIFS_DENT_NODE ||
197 sa->type == UBIFS_XENT_NODE);
198 ubifs_assert(sb->type == UBIFS_DENT_NODE ||
199 sb->type == UBIFS_XENT_NODE);
200
201 inuma = key_inum(c, &sa->key);
202 inumb = key_inum(c, &sb->key);
203
204 if (inuma == inumb) {
205 uint32_t hasha = key_hash(c, &sa->key);
206 uint32_t hashb = key_hash(c, &sb->key);
207
208 if (hasha <= hashb)
209 return -1;
210 } else if (inuma <= inumb)
211 return -1;
212
213 return 1;
214}
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243static int sort_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
244 struct list_head *nondata, int *min)
245{
246 int err;
247 struct ubifs_scan_node *snod, *tmp;
248
249 *min = INT_MAX;
250
251
252 list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {
253 ubifs_assert(snod->type == UBIFS_INO_NODE ||
254 snod->type == UBIFS_DATA_NODE ||
255 snod->type == UBIFS_DENT_NODE ||
256 snod->type == UBIFS_XENT_NODE ||
257 snod->type == UBIFS_TRUN_NODE);
258
259 if (snod->type != UBIFS_INO_NODE &&
260 snod->type != UBIFS_DATA_NODE &&
261 snod->type != UBIFS_DENT_NODE &&
262 snod->type != UBIFS_XENT_NODE) {
263
264 list_del(&snod->list);
265 kfree(snod);
266 continue;
267 }
268
269 ubifs_assert(key_type(c, &snod->key) == UBIFS_DATA_KEY ||
270 key_type(c, &snod->key) == UBIFS_INO_KEY ||
271 key_type(c, &snod->key) == UBIFS_DENT_KEY ||
272 key_type(c, &snod->key) == UBIFS_XENT_KEY);
273
274 err = ubifs_tnc_has_node(c, &snod->key, 0, sleb->lnum,
275 snod->offs, 0);
276 if (err < 0)
277 return err;
278
279 if (!err) {
280
281 list_del(&snod->list);
282 kfree(snod);
283 continue;
284 }
285
286 if (snod->len < *min)
287 *min = snod->len;
288
289 if (key_type(c, &snod->key) != UBIFS_DATA_KEY)
290 list_move_tail(&snod->list, nondata);
291 }
292
293
294 list_sort(c, &sleb->nodes, &data_nodes_cmp);
295 list_sort(c, nondata, &nondata_nodes_cmp);
296
297 err = dbg_check_data_nodes_order(c, &sleb->nodes);
298 if (err)
299 return err;
300 err = dbg_check_nondata_nodes_order(c, nondata);
301 if (err)
302 return err;
303 return 0;
304}
305
306
307
308
309
310
311
312
313
314
315
316
317static int move_node(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
318 struct ubifs_scan_node *snod, struct ubifs_wbuf *wbuf)
319{
320 int err, new_lnum = wbuf->lnum, new_offs = wbuf->offs + wbuf->used;
321
322 cond_resched();
323 err = ubifs_wbuf_write_nolock(wbuf, snod->node, snod->len);
324 if (err)
325 return err;
326
327 err = ubifs_tnc_replace(c, &snod->key, sleb->lnum,
328 snod->offs, new_lnum, new_offs,
329 snod->len);
330 list_del(&snod->list);
331 kfree(snod);
332 return err;
333}
334
335
336
337
338
339
340
341
342
343
344
345static int move_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb)
346{
347 int err, min;
348 LIST_HEAD(nondata);
349 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
350
351 if (wbuf->lnum == -1) {
352
353
354
355
356 err = switch_gc_head(c);
357 if (err)
358 return err;
359 }
360
361 err = sort_nodes(c, sleb, &nondata, &min);
362 if (err)
363 goto out;
364
365
366 while (1) {
367 int avail;
368 struct ubifs_scan_node *snod, *tmp;
369
370
371 list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {
372 avail = c->leb_size - wbuf->offs - wbuf->used;
373 if (snod->len > avail)
374
375
376
377
378 break;
379
380 err = move_node(c, sleb, snod, wbuf);
381 if (err)
382 goto out;
383 }
384
385
386 list_for_each_entry_safe(snod, tmp, &nondata, list) {
387 avail = c->leb_size - wbuf->offs - wbuf->used;
388 if (avail < min)
389 break;
390
391 if (snod->len > avail) {
392
393
394
395
396
397
398
399 if (key_type(c, &snod->key) == UBIFS_DENT_KEY ||
400 snod->len == UBIFS_INO_NODE_SZ)
401 break;
402 continue;
403 }
404
405 err = move_node(c, sleb, snod, wbuf);
406 if (err)
407 goto out;
408 }
409
410 if (list_empty(&sleb->nodes) && list_empty(&nondata))
411 break;
412
413
414
415
416
417 err = switch_gc_head(c);
418 if (err)
419 goto out;
420 }
421
422 return 0;
423
424out:
425 list_splice_tail(&nondata, &sleb->nodes);
426 return err;
427}
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442static int gc_sync_wbufs(struct ubifs_info *c)
443{
444 int err, i;
445
446 for (i = 0; i < c->jhead_cnt; i++) {
447 if (i == GCHD)
448 continue;
449 err = ubifs_wbuf_sync(&c->jheads[i].wbuf);
450 if (err)
451 return err;
452 }
453 return 0;
454}
455
456
457
458
459
460
461
462
463
464
465int ubifs_garbage_collect_leb(struct ubifs_info *c, struct ubifs_lprops *lp)
466{
467 struct ubifs_scan_leb *sleb;
468 struct ubifs_scan_node *snod;
469 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
470 int err = 0, lnum = lp->lnum;
471
472 ubifs_assert(c->gc_lnum != -1 || wbuf->offs + wbuf->used == 0 ||
473 c->need_recovery);
474 ubifs_assert(c->gc_lnum != lnum);
475 ubifs_assert(wbuf->lnum != lnum);
476
477 if (lp->free + lp->dirty == c->leb_size) {
478
479 dbg_gc("LEB %d is free, return it", lp->lnum);
480 ubifs_assert(!(lp->flags & LPROPS_INDEX));
481
482 if (lp->free != c->leb_size) {
483
484
485
486
487
488 err = gc_sync_wbufs(c);
489 if (err)
490 return err;
491 err = ubifs_change_one_lp(c, lp->lnum, c->leb_size,
492 0, 0, 0, 0);
493 if (err)
494 return err;
495 }
496 err = ubifs_leb_unmap(c, lp->lnum);
497 if (err)
498 return err;
499
500 if (c->gc_lnum == -1) {
501 c->gc_lnum = lnum;
502 return LEB_RETAINED;
503 }
504
505 return LEB_FREED;
506 }
507
508
509
510
511
512 sleb = ubifs_scan(c, lnum, 0, c->sbuf, 0);
513 if (IS_ERR(sleb))
514 return PTR_ERR(sleb);
515
516 ubifs_assert(!list_empty(&sleb->nodes));
517 snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list);
518
519 if (snod->type == UBIFS_IDX_NODE) {
520 struct ubifs_gced_idx_leb *idx_gc;
521
522 dbg_gc("indexing LEB %d (free %d, dirty %d)",
523 lnum, lp->free, lp->dirty);
524 list_for_each_entry(snod, &sleb->nodes, list) {
525 struct ubifs_idx_node *idx = snod->node;
526 int level = le16_to_cpu(idx->level);
527
528 ubifs_assert(snod->type == UBIFS_IDX_NODE);
529 key_read(c, ubifs_idx_key(c, idx), &snod->key);
530 err = ubifs_dirty_idx_node(c, &snod->key, level, lnum,
531 snod->offs);
532 if (err)
533 goto out;
534 }
535
536 idx_gc = kmalloc(sizeof(struct ubifs_gced_idx_leb), GFP_NOFS);
537 if (!idx_gc) {
538 err = -ENOMEM;
539 goto out;
540 }
541
542 idx_gc->lnum = lnum;
543 idx_gc->unmap = 0;
544 list_add(&idx_gc->list, &c->idx_gc);
545
546
547
548
549
550
551
552 err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0,
553 LPROPS_INDEX, 1);
554 if (err)
555 goto out;
556 err = LEB_FREED_IDX;
557 } else {
558 dbg_gc("data LEB %d (free %d, dirty %d)",
559 lnum, lp->free, lp->dirty);
560
561 err = move_nodes(c, sleb);
562 if (err)
563 goto out_inc_seq;
564
565 err = gc_sync_wbufs(c);
566 if (err)
567 goto out_inc_seq;
568
569 err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0, 0, 0);
570 if (err)
571 goto out_inc_seq;
572
573
574 c->gced_lnum = lnum;
575 smp_wmb();
576 c->gc_seq += 1;
577 smp_wmb();
578
579 if (c->gc_lnum == -1) {
580 c->gc_lnum = lnum;
581 err = LEB_RETAINED;
582 } else {
583 err = ubifs_wbuf_sync_nolock(wbuf);
584 if (err)
585 goto out;
586
587 err = ubifs_leb_unmap(c, lnum);
588 if (err)
589 goto out;
590
591 err = LEB_FREED;
592 }
593 }
594
595out:
596 ubifs_scan_destroy(sleb);
597 return err;
598
599out_inc_seq:
600
601 c->gced_lnum = lnum;
602 smp_wmb();
603 c->gc_seq += 1;
604 smp_wmb();
605 goto out;
606}
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644int ubifs_garbage_collect(struct ubifs_info *c, int anyway)
645{
646 int i, err, ret, min_space = c->dead_wm;
647 struct ubifs_lprops lp;
648 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
649
650 ubifs_assert_cmt_locked(c);
651 ubifs_assert(!c->ro_media && !c->ro_mount);
652
653 if (ubifs_gc_should_commit(c))
654 return -EAGAIN;
655
656 mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);
657
658 if (c->ro_error) {
659 ret = -EROFS;
660 goto out_unlock;
661 }
662
663
664 ubifs_assert(!wbuf->used);
665
666 for (i = 0; ; i++) {
667 int space_before, space_after;
668
669 cond_resched();
670
671
672 if (ubifs_gc_should_commit(c)) {
673 ret = -EAGAIN;
674 break;
675 }
676
677 if (i > SOFT_LEBS_LIMIT && !list_empty(&c->idx_gc)) {
678
679
680
681
682 dbg_gc("soft limit, some index LEBs GC'ed, -EAGAIN");
683 ubifs_commit_required(c);
684 ret = -EAGAIN;
685 break;
686 }
687
688 if (i > HARD_LEBS_LIMIT) {
689
690
691
692
693 dbg_gc("hard limit, -ENOSPC");
694 ret = -ENOSPC;
695 break;
696 }
697
698
699
700
701
702
703
704
705 ret = ubifs_find_dirty_leb(c, &lp, min_space, anyway ? 0 : 1);
706 if (ret) {
707 if (ret == -ENOSPC)
708 dbg_gc("no more dirty LEBs");
709 break;
710 }
711
712 dbg_gc("found LEB %d: free %d, dirty %d, sum %d (min. space %d)",
713 lp.lnum, lp.free, lp.dirty, lp.free + lp.dirty,
714 min_space);
715
716 space_before = c->leb_size - wbuf->offs - wbuf->used;
717 if (wbuf->lnum == -1)
718 space_before = 0;
719
720 ret = ubifs_garbage_collect_leb(c, &lp);
721 if (ret < 0) {
722 if (ret == -EAGAIN) {
723
724
725
726
727
728
729 err = ubifs_return_leb(c, lp.lnum);
730 if (err)
731 ret = err;
732 break;
733 }
734 goto out;
735 }
736
737 if (ret == LEB_FREED) {
738
739 dbg_gc("LEB %d freed, return", lp.lnum);
740 ret = lp.lnum;
741 break;
742 }
743
744 if (ret == LEB_FREED_IDX) {
745
746
747
748
749
750
751 dbg_gc("indexing LEB %d freed, continue", lp.lnum);
752 continue;
753 }
754
755 ubifs_assert(ret == LEB_RETAINED);
756 space_after = c->leb_size - wbuf->offs - wbuf->used;
757 dbg_gc("LEB %d retained, freed %d bytes", lp.lnum,
758 space_after - space_before);
759
760 if (space_after > space_before) {
761
762 min_space >>= 1;
763 if (min_space < c->dead_wm)
764 min_space = c->dead_wm;
765 continue;
766 }
767
768 dbg_gc("did not make progress");
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786 if (i < SOFT_LEBS_LIMIT) {
787 dbg_gc("try again");
788 continue;
789 }
790
791 min_space <<= 1;
792 if (min_space > c->dark_wm)
793 min_space = c->dark_wm;
794 dbg_gc("set min. space to %d", min_space);
795 }
796
797 if (ret == -ENOSPC && !list_empty(&c->idx_gc)) {
798 dbg_gc("no space, some index LEBs GC'ed, -EAGAIN");
799 ubifs_commit_required(c);
800 ret = -EAGAIN;
801 }
802
803 err = ubifs_wbuf_sync_nolock(wbuf);
804 if (!err)
805 err = ubifs_leb_unmap(c, c->gc_lnum);
806 if (err) {
807 ret = err;
808 goto out;
809 }
810out_unlock:
811 mutex_unlock(&wbuf->io_mutex);
812 return ret;
813
814out:
815 ubifs_assert(ret < 0);
816 ubifs_assert(ret != -ENOSPC && ret != -EAGAIN);
817 ubifs_wbuf_sync_nolock(wbuf);
818 ubifs_ro_mode(c, ret);
819 mutex_unlock(&wbuf->io_mutex);
820 ubifs_return_leb(c, lp.lnum);
821 return ret;
822}
823
824
825
826
827
828
829
830
831
832
833
834
835int ubifs_gc_start_commit(struct ubifs_info *c)
836{
837 struct ubifs_gced_idx_leb *idx_gc;
838 const struct ubifs_lprops *lp;
839 int err = 0, flags;
840
841 ubifs_get_lprops(c);
842
843
844
845
846
847 while (1) {
848 lp = ubifs_fast_find_freeable(c);
849 if (!lp)
850 break;
851 ubifs_assert(!(lp->flags & LPROPS_TAKEN));
852 ubifs_assert(!(lp->flags & LPROPS_INDEX));
853 err = ubifs_leb_unmap(c, lp->lnum);
854 if (err)
855 goto out;
856 lp = ubifs_change_lp(c, lp, c->leb_size, 0, lp->flags, 0);
857 if (IS_ERR(lp)) {
858 err = PTR_ERR(lp);
859 goto out;
860 }
861 ubifs_assert(!(lp->flags & LPROPS_TAKEN));
862 ubifs_assert(!(lp->flags & LPROPS_INDEX));
863 }
864
865
866 list_for_each_entry(idx_gc, &c->idx_gc, list)
867 idx_gc->unmap = 1;
868
869
870 while (1) {
871 lp = ubifs_fast_find_frdi_idx(c);
872 if (IS_ERR(lp)) {
873 err = PTR_ERR(lp);
874 goto out;
875 }
876 if (!lp)
877 break;
878 idx_gc = kmalloc(sizeof(struct ubifs_gced_idx_leb), GFP_NOFS);
879 if (!idx_gc) {
880 err = -ENOMEM;
881 goto out;
882 }
883 ubifs_assert(!(lp->flags & LPROPS_TAKEN));
884 ubifs_assert(lp->flags & LPROPS_INDEX);
885
886 flags = (lp->flags | LPROPS_TAKEN) ^ LPROPS_INDEX;
887 lp = ubifs_change_lp(c, lp, c->leb_size, 0, flags, 1);
888 if (IS_ERR(lp)) {
889 err = PTR_ERR(lp);
890 kfree(idx_gc);
891 goto out;
892 }
893 ubifs_assert(lp->flags & LPROPS_TAKEN);
894 ubifs_assert(!(lp->flags & LPROPS_INDEX));
895 idx_gc->lnum = lp->lnum;
896 idx_gc->unmap = 1;
897 list_add(&idx_gc->list, &c->idx_gc);
898 }
899out:
900 ubifs_release_lprops(c);
901 return err;
902}
903
904
905
906
907
908
909
910int ubifs_gc_end_commit(struct ubifs_info *c)
911{
912 struct ubifs_gced_idx_leb *idx_gc, *tmp;
913 struct ubifs_wbuf *wbuf;
914 int err = 0;
915
916 wbuf = &c->jheads[GCHD].wbuf;
917 mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);
918 list_for_each_entry_safe(idx_gc, tmp, &c->idx_gc, list)
919 if (idx_gc->unmap) {
920 dbg_gc("LEB %d", idx_gc->lnum);
921 err = ubifs_leb_unmap(c, idx_gc->lnum);
922 if (err)
923 goto out;
924 err = ubifs_change_one_lp(c, idx_gc->lnum, LPROPS_NC,
925 LPROPS_NC, 0, LPROPS_TAKEN, -1);
926 if (err)
927 goto out;
928 list_del(&idx_gc->list);
929 kfree(idx_gc);
930 }
931out:
932 mutex_unlock(&wbuf->io_mutex);
933 return err;
934}
935
936
937
938
939
940
941
942
943
944void ubifs_destroy_idx_gc(struct ubifs_info *c)
945{
946 while (!list_empty(&c->idx_gc)) {
947 struct ubifs_gced_idx_leb *idx_gc;
948
949 idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb,
950 list);
951 c->idx_gc_cnt -= 1;
952 list_del(&idx_gc->list);
953 kfree(idx_gc);
954 }
955}
956
957
958
959
960
961
962
963int ubifs_get_idx_gc_leb(struct ubifs_info *c)
964{
965 struct ubifs_gced_idx_leb *idx_gc;
966 int lnum;
967
968 if (list_empty(&c->idx_gc))
969 return -ENOSPC;
970 idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb, list);
971 lnum = idx_gc->lnum;
972
973 list_del(&idx_gc->list);
974 kfree(idx_gc);
975 return lnum;
976}
977