projects / GitHub / LineageOS / android_kernel_samsung_universal7580.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
battery: sec_battery: export {CURRENT/VOLTAGE}_MAX to sysfs
[GitHub/LineageOS/android_kernel_samsung_universal7580.git] / fs / sdfat / amap_smart.c
1 /*
2 * Copyright (C) 2012-2013 Samsung Electronics Co., Ltd.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see <http://www.gnu.org/licenses/>.
16 */
17
18 /************************************************************************/
19 /* */
20 /* PROJECT : exFAT & FAT12/16/32 File System */
21 /* FILE : amap_smart.c */
22 /* PURPOSE : FAT32 Smart allocation code for sdFAT */
23 /* */
24 /*----------------------------------------------------------------------*/
25 /* NOTES */
26 /* */
27 /* */
28 /************************************************************************/
29
30 #include <linux/slab.h>
31 #include <linux/vmalloc.h>
32
33 #include "sdfat.h"
34 #include "core.h"
35 #include "amap_smart.h"
36
37 /* AU list related functions */
38 static inline void amap_list_del(struct list_head *entry)
39 {
40 __list_del(entry->prev, entry->next);
41
42 /* Will be used to check if the entry is a single entry(selected) */
43 entry->prev = NULL;
44 entry->next = NULL;
45 }
46
47 static inline int amap_insert_to_list(AU_INFO_T *au, struct slist_head *shead)
48 {
49 struct slist_head *entry = &au->shead;
50
51 ASSERT(!entry->head);
52
53 entry->next = shead->next;
54 entry->head = shead;
55
56 shead->next = entry;
57
58 return 0;
59 }
60
61 static inline int amap_remove_from_list(AU_INFO_T *au, struct slist_head *shead)
62 {
63 struct slist_head *entry = &au->shead;
64 struct slist_head *iter;
65
66 BUG_ON(entry->head != shead);
67
68 iter = shead;
69
70 while (iter->next) {
71 if (iter->next == entry) {
72 // iter->next = iter->next->next
73 iter->next = entry->next;
74
75 entry->next = NULL;
76 entry->head = NULL;
77 return 0;
78 }
79 iter = iter->next;
80 }
81
82 BUG_ON("Not reachable");
83 }
84
85 /* Full-linear serach => Find AU with max. number of fclu */
86 static inline AU_INFO_T *amap_find_hot_au_largest(struct slist_head *shead)
87 {
88 struct slist_head *iter;
89 uint16_t max_fclu = 0;
90 AU_INFO_T *entry, *ret = NULL;
91
92 ASSERT(shead->head == shead); /* Singly-list condition */
93 ASSERT(shead->next != shead);
94
95 iter = shead->next;
96
97 while (iter) {
98 entry = list_entry(iter, AU_INFO_T, shead);
99
100 if (entry->free_clusters > max_fclu) {
101 max_fclu = entry->free_clusters;
102 ret = entry;
103 }
104
105 iter = iter->next;
106 }
107
108 return ret;
109 }
110
111 /* Find partially used AU with max. number of fclu.
112 * If there is no partial AU available, pick a clean one
113 */
114 static inline AU_INFO_T *amap_find_hot_au_partial(AMAP_T *amap)
115 {
116 struct slist_head *iter;
117 uint16_t max_fclu = 0;
118 AU_INFO_T *entry, *ret = NULL;
119
120 iter = &amap->slist_hot;
121 ASSERT(iter->head == iter); /* Singly-list condition */
122 ASSERT(iter->next != iter);
123
124 iter = iter->next;
125
126 while (iter) {
127 entry = list_entry(iter, AU_INFO_T, shead);
128
129 if (entry->free_clusters > max_fclu) {
130 if (entry->free_clusters < amap->clusters_per_au) {
131 max_fclu = entry->free_clusters;
132 ret = entry;
133 } else {
134 if (!ret)
135 ret = entry;
136 }
137 }
138
139 iter = iter->next;
140 }
141
142 return ret;
143 }
144
145
146
147
148 /*
149 * Size-base AU management functions
150 */
151
152 /*
153 * Add au into cold AU MAP
154 * au: an isolated (not in a list) AU data structure
155 */
156 int amap_add_cold_au(AMAP_T *amap, AU_INFO_T *au)
157 {
158 FCLU_NODE_T *fclu_node = NULL;
159
160 /* Check if a single entry */
161 BUG_ON(au->head.prev);
162
163 /* Ignore if the au is full */
164 if (!au->free_clusters)
165 return 0;
166
167 /* Find entry */
168 fclu_node = NODE(au->free_clusters, amap);
169
170 /* Insert to the list */
171 list_add_tail(&(au->head), &(fclu_node->head));
172
173 /* Update fclu_hint (Increase) */
174 if (au->free_clusters > amap->fclu_hint)
175 amap->fclu_hint = au->free_clusters;
176
177 return 0;
178 }
179
180 /*
181 * Remove an AU from AU MAP
182 */
183 int amap_remove_cold_au(AMAP_T *amap, AU_INFO_T *au)
184 {
185 struct list_head *prev = au->head.prev;
186
187 /* Single entries are not managed in lists */
188 if (!prev) {
189 BUG_ON(au->free_clusters > 0);
190 return 0;
191 }
192
193 /* remove from list */
194 amap_list_del(&(au->head));
195
196 return 0;
197 }
198
199
200 /* "Find" best fit AU
201 * returns NULL if there is no AU w/ enough free space.
202 *
203 * This function doesn't change AU status.
204 * The caller should call amap_remove_cold_au() if needed.
205 */
206 AU_INFO_T *amap_find_cold_au_bestfit(AMAP_T *amap, uint16_t free_clusters)
207 {
208 AU_INFO_T *au = NULL;
209 FCLU_NODE_T *fclu_iter;
210
211 if (free_clusters <= 0 || free_clusters > amap->clusters_per_au) {
212 EMSG("AMAP: amap_find_cold_au_bestfit / unexpected arg. (%d)\n",
213 free_clusters);
214 return NULL;
215 }
216
217 fclu_iter = NODE(free_clusters, amap);
218
219 if (amap->fclu_hint < free_clusters) {
220 /* There is no AUs with enough free_clusters */
221 return NULL;
222 }
223
224 /* Naive Hash management (++) */
225 do {
226 if (!list_empty(&fclu_iter->head)) {
227 struct list_head *first = fclu_iter->head.next;
228
229 au = list_entry(first, AU_INFO_T, head);
230
231 break;
232 }
233
234 fclu_iter++;
235 } while (fclu_iter < (amap->fclu_nodes + amap->clusters_per_au));
236
237
238 // BUG_ON(au->free_clusters < 0);
239 BUG_ON(au && (au->free_clusters > amap->clusters_per_au));
240
241 return au;
242 }
243
244
245 /* "Pop" best fit AU
246 *
247 * returns NULL if there is no AU w/ enough free space.
248 * The returned AU will not be in the list anymore.
249 */
250 AU_INFO_T *amap_pop_cold_au_bestfit(AMAP_T *amap, uint16_t free_clusters)
251 {
252 /* Naive implementation */
253 AU_INFO_T *au;
254
255 au = amap_find_cold_au_bestfit(amap, free_clusters);
256 if (au)
257 amap_remove_cold_au(amap, au);
258
259 return au;
260 }
261
262
263
264 /* Pop the AU with the largest free space
265 *
266 * search from 'start_fclu' to 0
267 * (target freecluster : -1 for each step)
268 * start_fclu = 0 means to search from the max. value
269 */
270 AU_INFO_T *amap_pop_cold_au_largest(AMAP_T *amap, uint16_t start_fclu)
271 {
272 AU_INFO_T *au = NULL;
273 FCLU_NODE_T *fclu_iter;
274
275 if (!start_fclu)
276 start_fclu = amap->clusters_per_au;
277 if (start_fclu > amap->clusters_per_au)
278 start_fclu = amap->clusters_per_au;
279
280 /* Use hint (search start point) */
281 if (amap->fclu_hint < start_fclu)
282 fclu_iter = NODE(amap->fclu_hint, amap);
283 else
284 fclu_iter = NODE(start_fclu, amap);
285
286 /* Naive Hash management */
287 do {
288 if (!list_empty(&fclu_iter->head)) {
289 struct list_head *first = fclu_iter->head.next;
290
291 au = list_entry(first, AU_INFO_T, head);
292 // BUG_ON((au < amap->entries) || ((amap->entries + amap->n_au) <= au));
293
294 amap_list_del(first);
295
296 // (Hint) Possible maximum value of free clusters (among cold)
297 /* if it wasn't the whole search, don't update fclu_hint */
298 if (start_fclu == amap->clusters_per_au)
299 amap->fclu_hint = au->free_clusters;
300
301 break;
302 }
303
304 fclu_iter--;
305 } while (amap->fclu_nodes <= fclu_iter);
306
307 return au;
308 }
309
310
311
312 /*
313 * ===============================================
314 * Allocation Map related functions
315 * ===============================================
316 */
317
318 /* Create AMAP related data structure (mount time) */
319 int amap_create(struct super_block *sb, u32 pack_ratio, u32 sect_per_au, u32 hidden_sect)
320 {
321 FS_INFO_T *fsi = &(SDFAT_SB(sb)->fsi);
322 AMAP_T *amap;
323 int total_used_clusters;
324 int n_au_table = 0;
325 int i, i_clu, i_au;
326 int i_au_root = -1, i_au_hot_from = INT_MAX;
327 u32 misaligned_sect = hidden_sect;
328 u64 tmp;
329
330 BUG_ON(!fsi->bd_opened);
331
332 if (fsi->amap)
333 return -EEXIST;
334
335 /* Check conditions */
336 if (fsi->vol_type != FAT32) {
337 sdfat_msg(sb, KERN_ERR, "smart allocation is only available "
338 "with fat32-fs");
339 return -ENOTSUPP;
340 }
341
342 if (fsi->num_sectors < AMAP_MIN_SUPPORT_SECTORS) {
343 sdfat_msg(sb, KERN_ERR, "smart allocation is only available "
344 "with sectors above %d", AMAP_MIN_SUPPORT_SECTORS);
345 return -ENOTSUPP;
346 }
347
348 /* AU size must be a multiple of clu_size */
349 if ((sect_per_au <= 0) || (sect_per_au & (fsi->sect_per_clus - 1))) {
350 sdfat_msg(sb, KERN_ERR,
351 "invalid AU size (sect_per_au : %u, "
352 "sect_per_clus : %u) "
353 "please re-format for performance.",
354 sect_per_au, fsi->sect_per_clus);
355 return -EINVAL;
356 }
357
358 /* the start sector of this partition must be a multiple of clu_size */
359 if (misaligned_sect & (fsi->sect_per_clus - 1)) {
360 sdfat_msg(sb, KERN_ERR,
361 "misaligned part (start sect : %u, "
362 "sect_per_clus : %u) "
363 "please re-format for performance.",
364 misaligned_sect, fsi->sect_per_clus);
365 return -EINVAL;
366 }
367
368 /* data start sector must be a multiple of clu_size */
369 if (fsi->data_start_sector & (fsi->sect_per_clus - 1)) {
370 sdfat_msg(sb, KERN_ERR,
371 "misaligned data area (start sect : %llu, "
372 "sect_per_clus : %u) "
373 "please re-format for performance.",
374 fsi->data_start_sector, fsi->sect_per_clus);
375 return -EINVAL;
376 }
377
378 misaligned_sect &= (sect_per_au - 1);
379
380 /* Allocate data structrues */
381 amap = kzalloc(sizeof(AMAP_T), GFP_NOIO);
382 if (!amap)
383 return -ENOMEM;
384
385 amap->sb = sb;
386
387 tmp = fsi->num_sectors + misaligned_sect + sect_per_au - 1;
388 do_div(tmp, sect_per_au);
389 amap->n_au = tmp;
390 amap->n_clean_au = 0;
391 amap->n_full_au = 0;
392
393 /* Reflect block-partition align first,
394 * then partition-data_start align
395 */
396 amap->clu_align_bias = (misaligned_sect / fsi->sect_per_clus);
397 amap->clu_align_bias += (fsi->data_start_sector >> fsi->sect_per_clus_bits) - CLUS_BASE;
398 amap->clusters_per_au = sect_per_au / fsi->sect_per_clus;
399
400 /* That is,
401 * the size of cluster is at least 4KB if the size of AU is 4MB
402 */
403 if (amap->clusters_per_au > MAX_CLU_PER_AU) {
404 sdfat_log_msg(sb, KERN_INFO,
405 "too many clusters per AU (clus/au:%d > %d).",
406 amap->clusters_per_au,
407 MAX_CLU_PER_AU);
408 }
409
410 /* is it needed? why here? */
411 // set_sb_dirty(sb);
412
413 spin_lock_init(&amap->amap_lock);
414
415 amap->option.packing_ratio = pack_ratio;
416 amap->option.au_size = sect_per_au;
417 amap->option.au_align_factor = hidden_sect;
418
419
420 /* Allocate AU info table */
421 n_au_table = (amap->n_au + N_AU_PER_TABLE - 1) / N_AU_PER_TABLE;
422 amap->au_table = kmalloc(sizeof(AU_INFO_T *) * n_au_table, GFP_NOIO);
423 if (!amap->au_table) {
424 sdfat_msg(sb, KERN_ERR,
425 "failed to alloc amap->au_table\n");
426 kfree(amap);
427 return -ENOMEM;
428 }
429
430 for (i = 0; i < n_au_table; i++)
431 amap->au_table[i] = (AU_INFO_T *)get_zeroed_page(GFP_NOIO);
432
433 /* Allocate buckets indexed by # of free clusters */
434 amap->fclu_order = get_order(sizeof(FCLU_NODE_T) * amap->clusters_per_au);
435
436 // XXX: amap->clusters_per_au limitation is 512 (w/ 8 byte list_head)
437 sdfat_log_msg(sb, KERN_INFO, "page orders for AU nodes : %d "
438 "(clus_per_au : %d, node_size : %lu)",
439 amap->fclu_order,
440 amap->clusters_per_au,
441 (unsigned long)sizeof(FCLU_NODE_T));
442
443 if (!amap->fclu_order)
444 amap->fclu_nodes = (FCLU_NODE_T *)get_zeroed_page(GFP_NOIO);
445 else
446 amap->fclu_nodes = vzalloc(PAGE_SIZE << amap->fclu_order);
447
448 amap->fclu_hint = amap->clusters_per_au;
449
450 /* Hot AU list, ignored AU list */
451 amap->slist_hot.next = NULL;
452 amap->slist_hot.head = &amap->slist_hot;
453 amap->total_fclu_hot = 0;
454
455 amap->slist_ignored.next = NULL;
456 amap->slist_ignored.head = &amap->slist_ignored;
457
458 /* Strategy related vars. */
459 amap->cur_cold.au = NULL;
460 amap->cur_hot.au = NULL;
461 amap->n_need_packing = 0;
462
463
464 /* Build AMAP info */
465 total_used_clusters = 0; // Count # of used clusters
466
467 i_au_root = i_AU_of_CLU(amap, fsi->root_dir);
468 i_au_hot_from = amap->n_au - (SMART_ALLOC_N_HOT_AU - 1);
469
470 for (i = 0; i < amap->clusters_per_au; i++)
471 INIT_LIST_HEAD(&amap->fclu_nodes[i].head);
472
473 /*
474 * Thanks to kzalloc()
475 * amap->entries[i_au].free_clusters = 0;
476 * amap->entries[i_au].head.prev = NULL;
477 * amap->entries[i_au].head.next = NULL;
478 */
479
480 /* Parse FAT table */
481 for (i_clu = CLUS_BASE; i_clu < fsi->num_clusters; i_clu++) {
482 u32 clu_data;
483 AU_INFO_T *au;
484
485 if (fat_ent_get(sb, i_clu, &clu_data)) {
486 sdfat_msg(sb, KERN_ERR,
487 "failed to read fat entry(%u)\n", i_clu);
488 goto free_and_eio;
489 }
490
491 if (IS_CLUS_FREE(clu_data)) {
492 au = GET_AU(amap, i_AU_of_CLU(amap, i_clu));
493 au->free_clusters++;
494 } else
495 total_used_clusters++;
496 }
497
498 /* Build AU list */
499 for (i_au = 0; i_au < amap->n_au; i_au++) {
500 AU_INFO_T *au = GET_AU(amap, i_au);
501
502 au->idx = i_au;
503 BUG_ON(au->free_clusters > amap->clusters_per_au);
504
505 if (au->free_clusters == amap->clusters_per_au)
506 amap->n_clean_au++;
507 else if (au->free_clusters == 0)
508 amap->n_full_au++;
509
510 /* If hot, insert to the hot list */
511 if (i_au >= i_au_hot_from) {
512 amap_add_hot_au(amap, au);
513 amap->total_fclu_hot += au->free_clusters;
514 } else if (i_au != i_au_root || SMART_ALLOC_N_HOT_AU == 0) {
515 /* Otherwise, insert to the free cluster hash */
516 amap_add_cold_au(amap, au);
517 }
518 }
519
520 /* Hot list -> (root) -> (last) -> (last - 1) -> ... */
521 if (i_au_root >= 0 && SMART_ALLOC_N_HOT_AU > 0) {
522 amap_add_hot_au(amap, GET_AU(amap, i_au_root));
523 amap->total_fclu_hot += GET_AU(amap, i_au_root)->free_clusters;
524 }
525
526 fsi->amap = amap;
527 fsi->used_clusters = total_used_clusters;
528
529 sdfat_msg(sb, KERN_INFO,
530 "AMAP: Smart allocation enabled (opt : %u / %u / %u)",
531 amap->option.au_size, amap->option.au_align_factor,
532 amap->option.packing_ratio);
533
534 /* Debug purpose - check */
535 //{
536 //u32 used_clusters;
537 //fat_count_used_clusters(sb, &used_clusters)
538 //ASSERT(used_clusters == total_used_clusters);
539 //}
540
541 return 0;
542
543
544 free_and_eio:
545 if (amap) {
546 if (amap->au_table) {
547 for (i = 0; i < n_au_table; i++)
548 free_page((unsigned long)amap->au_table[i]);
549 kfree(amap->au_table);
550 }
551 if (amap->fclu_nodes) {
552 if (!amap->fclu_order)
553 free_page((unsigned long)amap->fclu_nodes);
554 else
555 vfree(amap->fclu_nodes);
556 }
557 kfree(amap);
558 }
559 return -EIO;
560 }
561
562
563 /* Free AMAP related structure */
564 void amap_destroy(struct super_block *sb)
565 {
566 AMAP_T *amap = SDFAT_SB(sb)->fsi.amap;
567 int n_au_table;
568
569 if (!amap)
570 return;
571
572 DMSG("%s\n", __func__);
573
574 n_au_table = (amap->n_au + N_AU_PER_TABLE - 1) / N_AU_PER_TABLE;
575
576 if (amap->au_table) {
577 int i;
578
579 for (i = 0; i < n_au_table; i++)
580 free_page((unsigned long)amap->au_table[i]);
581
582 kfree(amap->au_table);
583 }
584 if (!amap->fclu_order)
585 free_page((unsigned long)amap->fclu_nodes);
586 else
587 vfree(amap->fclu_nodes);
588 kfree(amap);
589 SDFAT_SB(sb)->fsi.amap = NULL;
590 }
591
592
593 /*
594 * Check status of FS
595 * and change destination if needed to disable AU-aligned alloc.
596 * (from ALLOC_COLD_ALIGNED to ALLOC_COLD_SEQ)
597 */
598 static inline int amap_update_dest(AMAP_T *amap, int ori_dest)
599 {
600 FS_INFO_T *fsi = &(SDFAT_SB(amap->sb)->fsi);
601 int n_partial_au, n_partial_freeclus;
602
603 if (ori_dest != ALLOC_COLD_ALIGNED)
604 return ori_dest;
605
606 /* # of partial AUs and # of clusters in those AUs */
607 n_partial_au = amap->n_au - amap->n_clean_au - amap->n_full_au;
608 n_partial_freeclus = fsi->num_clusters - fsi->used_clusters -
609 amap->clusters_per_au * amap->n_clean_au;
610
611 /* Status of AUs : Full / Partial / Clean
612 * If there are many partial (and badly fragmented) AUs,
613 * the throughput will decrease extremly.
614 *
615 * The follow code will treat those worst cases.
616 */
617
618 /* XXX: AMAP heuristics */
619 if ((amap->n_clean_au * 50 <= amap->n_au) &&
620 (n_partial_freeclus*2) < (n_partial_au*amap->clusters_per_au)) {
621 /* If clean AUs are fewer than 2% of n_au (80 AUs per 16GB)
622 * and fragment ratio is more than 2 (AVG free_clusters=half AU)
623 *
624 * disable clean-first allocation
625 * enable VFAT-like sequential allocation
626 */
627 return ALLOC_COLD_SEQ;
628 }
629
630 return ori_dest;
631 }
632
633
634 #define PACKING_SOFTLIMIT (amap->option.packing_ratio)
635 #define PACKING_HARDLIMIT (amap->option.packing_ratio * 4)
636 /*
637 * Pick a packing AU if needed.
638 * Otherwise just return NULL
639 *
640 * This function includes some heuristics.
641 */
642 static inline AU_INFO_T *amap_get_packing_au(AMAP_T *amap, int dest, int num_to_wb, int *clu_to_skip)
643 {
644 AU_INFO_T *au = NULL;
645
646 if (dest == ALLOC_COLD_PACKING) {
647 /* ALLOC_COLD_PACKING:
648 * Packing-first mode for defrag.
649 * Optimized to save clean AU
650 *
651 * 1) best-fit AU
652 * 2) Smallest AU (w/ minimum free clusters)
653 */
654 if (num_to_wb >= amap->clusters_per_au)
655 num_to_wb = num_to_wb % amap->clusters_per_au;
656
657 /* 이거 주석처리하면, AU size 딱 맞을때는 clean, 나머지는 작은거부터 */
658 if (num_to_wb == 0)
659 num_to_wb = 1; // Don't use clean AUs
660
661 au = amap_find_cold_au_bestfit(amap, num_to_wb);
662 if (au && au->free_clusters == amap->clusters_per_au && num_to_wb > 1) {
663 /* if au is clean then get a new partial one */
664 au = amap_find_cold_au_bestfit(amap, 1);
665 }
666
667 if (au) {
668 amap->n_need_packing = 0;
669 amap_remove_cold_au(amap, au);
670 return au;
671 }
672 }
673
674
675 /* Heuristic packing:
676 * This will improve QoS greatly.
677 *
678 * Count # of AU_ALIGNED allocation.
679 * If the number exceeds the specific threshold,
680 * allocate on a partial AU or generate random I/O.
681 */
682 if ((PACKING_SOFTLIMIT > 0) &&
683 (amap->n_need_packing >= PACKING_SOFTLIMIT) &&
684 (num_to_wb < (int)amap->clusters_per_au)) {
685 /* Best-fit packing:
686 * If num_to_wb (expected number to be allocated) is smaller
687 * than AU_SIZE, find a best-fit AU.
688 */
689
690 /* Back margin (heuristics) */
691 if (num_to_wb < amap->clusters_per_au / 4)
692 num_to_wb = amap->clusters_per_au / 4;
693
694 au = amap_find_cold_au_bestfit(amap, num_to_wb);
695 if (au != NULL) {
696 amap_remove_cold_au(amap, au);
697
698 MMSG("AMAP: packing (cnt: %d) / softlimit, "
699 "best-fit (num_to_wb: %d))\n",
700 amap->n_need_packing, num_to_wb);
701
702 if (au->free_clusters > num_to_wb) { // Best-fit search: if 문 무조건 hit
703 *clu_to_skip = au->free_clusters - num_to_wb;
704 /* otherwise don't skip */
705 }
706 amap->n_need_packing = 0;
707 return au;
708 }
709 }
710
711 if ((PACKING_HARDLIMIT != 0) &&
712 amap->n_need_packing >= PACKING_HARDLIMIT) {
713 /* Compulsory SLC flushing:
714 * If there was no chance to do best-fit packing
715 * and the # of AU-aligned allocation exceeds HARD threshold,
716 * then pick a clean AU and generate a compulsory random I/O.
717 */
718 au = amap_pop_cold_au_largest(amap, amap->clusters_per_au);
719 if (au) {
720 MMSG("AMAP: packing (cnt: %d) / hard-limit, largest)\n",
721 amap->n_need_packing);
722
723 if (au->free_clusters >= 96) {
724 *clu_to_skip = au->free_clusters / 2;
725 MMSG("AMAP: cluster idx re-position\n");
726 }
727 amap->n_need_packing = 0;
728 return au;
729 }
730 }
731
732 /* Update # of clean AU allocation */
733 amap->n_need_packing++;
734 return NULL;
735 }
736
737
738 /* Pick a target AU:
739 * This function should be called
740 * only if there are one or more free clusters in the bdev.
741 */
742 TARGET_AU_T *amap_get_target_au(AMAP_T *amap, int dest, int num_to_wb)
743 {
744 int loop_count = 0;
745
746 retry:
747 if (++loop_count >= 3) {
748 /* No space available (or AMAP consistency error)
749 * This could happen because of the ignored AUs but not likely
750 * (because the defrag daemon will not work if there is no enough space)
751 */
752 BUG_ON(amap->slist_ignored.next == NULL);
753 return NULL;
754 }
755
756 /* Hot clusters (DIR) */
757 if (dest == ALLOC_HOT) {
758
759 /* Working hot AU exist? */
760 if (amap->cur_hot.au == NULL || amap->cur_hot.au->free_clusters == 0) {
761 AU_INFO_T *au;
762
763 if (amap->total_fclu_hot == 0) {
764 /* No more hot AU avaialbe */
765 dest = ALLOC_COLD;
766
767 goto retry;
768 }
769
770 au = amap_find_hot_au_partial(amap);
771
772 BUG_ON(au == NULL);
773 BUG_ON(au->free_clusters <= 0);
774
775 amap->cur_hot.au = au;
776 amap->cur_hot.idx = 0;
777 amap->cur_hot.clu_to_skip = 0;
778 }
779
780 /* Now allocate on a hot AU */
781 return &amap->cur_hot;
782 }
783
784 /* Cold allocation:
785 * If amap->cur_cold.au has one or more free cluster(s),
786 * then just return amap->cur_cold
787 */
788 if ((!amap->cur_cold.au)
789 || (amap->cur_cold.idx == amap->clusters_per_au)
790 || (amap->cur_cold.au->free_clusters == 0)) {
791
792 AU_INFO_T *au = NULL;
793 const AU_INFO_T *old_au = amap->cur_cold.au;
794 int n_clu_to_skip = 0;
795
796 if (old_au) {
797 ASSERT(!IS_AU_WORKING(old_au, amap));
798 /* must be NOT WORKING AU.
799 * (only for information gathering)
800 */
801 }
802
803 /* Next target AU is needed:
804 * There are 3 possible ALLOC options for cold AU
805 *
806 * ALLOC_COLD_ALIGNED: Clean AU first, but heuristic packing is ON
807 * ALLOC_COLD_PACKING: Packing AU first (usually for defrag)
808 * ALLOC_COLD_SEQ : Sequential AU allocation (VFAT-like)
809 */
810
811 /* Experimental: Modify allocation destination if needed (ALIGNED => SEQ) */
812 // dest = amap_update_dest(amap, dest);
813
814 if ((dest == ALLOC_COLD_SEQ) && old_au) {
815 int i_au = old_au->idx + 1;
816
817 while (i_au != old_au->idx) {
818 au = GET_AU(amap, i_au);
819
820 if ((au->free_clusters > 0) &&
821 !IS_AU_HOT(au, amap) &&
822 !IS_AU_IGNORED(au, amap)) {
823 MMSG("AMAP: new cold AU(%d) with %d "
824 "clusters (seq)\n",
825 au->idx, au->free_clusters);
826
827 amap_remove_cold_au(amap, au);
828 goto ret_new_cold;
829 }
830 i_au++;
831 if (i_au >= amap->n_au)
832 i_au = 0;
833 }
834
835 // no cold AUs are available => Hot allocation
836 dest = ALLOC_HOT;
837 goto retry;
838 }
839
840
841 /*
842 * Check if packing is needed
843 * (ALLOC_COLD_PACKING is treated by this function)
844 */
845 au = amap_get_packing_au(amap, dest, num_to_wb, &n_clu_to_skip);
846 if (au) {
847 MMSG("AMAP: new cold AU(%d) with %d clusters "
848 "(packing)\n", au->idx, au->free_clusters);
849 goto ret_new_cold;
850 }
851
852 /* ALLOC_COLD_ALIGNED */
853 /* Check if the adjacent AU is clean */
854 if (old_au && ((old_au->idx + 1) < amap->n_au)) {
855 au = GET_AU(amap, old_au->idx + 1);
856 if ((au->free_clusters == amap->clusters_per_au) &&
857 !IS_AU_HOT(au, amap) &&
858 !IS_AU_IGNORED(au, amap)) {
859 MMSG("AMAP: new cold AU(%d) with %d clusters "
860 "(adjacent)\n", au->idx, au->free_clusters);
861 amap_remove_cold_au(amap, au);
862 goto ret_new_cold;
863 }
864 }
865
866 /* Clean or largest AU */
867 au = amap_pop_cold_au_largest(amap, 0);
868 if (!au) {
869 //ASSERT(amap->total_fclu_hot == (fsi->num_clusters - fsi->used_clusters - 2));
870 dest = ALLOC_HOT;
871 goto retry;
872 }
873
874 MMSG("AMAP: New cold AU (%d) with %d clusters\n",
875 au->idx, au->free_clusters);
876
877 ret_new_cold:
878 SET_AU_WORKING(au);
879
880 amap->cur_cold.au = au;
881 amap->cur_cold.idx = 0;
882 amap->cur_cold.clu_to_skip = n_clu_to_skip;
883 }
884
885 return &amap->cur_cold;
886 }
887
888 /* Put and update target AU */
889 void amap_put_target_au(AMAP_T *amap, TARGET_AU_T *cur, unsigned int num_allocated)
890 {
891 /* Update AMAP info vars. */
892 if (num_allocated > 0 &&
893 (cur->au->free_clusters + num_allocated) == amap->clusters_per_au) {
894 /* if the target AU was a clean AU before this allocation ... */
895 amap->n_clean_au--;
896 }
897 if (num_allocated > 0 &&
898 cur->au->free_clusters == 0)
899 amap->n_full_au++;
900
901 if (IS_AU_HOT(cur->au, amap)) {
902 /* Hot AU */
903 MMSG("AMAP: hot allocation at AU %d\n", cur->au->idx);
904 amap->total_fclu_hot -= num_allocated;
905
906 /* Intra-AU round-robin */
907 if (cur->idx >= amap->clusters_per_au)
908 cur->idx = 0;
909
910 /* No more space available */
911 if (cur->au->free_clusters == 0)
912 cur->au = NULL;
913
914 } else {
915 /* non-hot AU */
916 ASSERT(IS_AU_WORKING(cur->au, amap));
917
918 if (cur->idx >= amap->clusters_per_au || cur->au->free_clusters == 0) {
919 /* It should be inserted back to AU MAP */
920 cur->au->shead.head = NULL; // SET_AU_NOT_WORKING
921 amap_add_cold_au(amap, cur->au);
922
923 // cur->au = NULL; // This value will be used for the next AU selection
924 cur->idx = amap->clusters_per_au; // AU closing
925 }
926 }
927
928 }
929
930
931 /* Reposition target->idx for packing (Heuristics):
932 * Skip (num_to_skip) free clusters in (cur->au)
933 */
934 static inline int amap_skip_cluster(struct super_block *sb, TARGET_AU_T *cur, int num_to_skip)
935 {
936 AMAP_T *amap = SDFAT_SB(sb)->fsi.amap;
937 u32 clu, read_clu;
938 MMSG_VAR(int num_to_skip_orig = num_to_skip);
939
940 if (num_to_skip >= cur->au->free_clusters) {
941 EMSG("AMAP(%s): skip mis-use. amap_566\n", __func__);
942 return -EIO;
943 }
944
945 clu = CLU_of_i_AU(amap, cur->au->idx, cur->idx);
946 while (num_to_skip > 0) {
947 if (clu >= CLUS_BASE) {
948 /* Cf.
949 * If AMAP's integrity is okay,
950 * we don't need to check if (clu < fsi->num_clusters)
951 */
952
953 if (fat_ent_get(sb, clu, &read_clu))
954 return -EIO;
955
956 if (IS_CLUS_FREE(read_clu))
957 num_to_skip--;
958 }
959
960 // Move clu->idx
961 clu++;
962 (cur->idx)++;
963
964 if (cur->idx >= amap->clusters_per_au) {
965 /* End of AU (Not supposed) */
966 EMSG("AMAP: Skip - End of AU?! (amap_596)\n");
967 cur->idx = 0;
968 return -EIO;
969 }
970 }
971
972 MMSG("AMAP: Skip_clusters (%d skipped => %d, among %d free clus)\n",
973 num_to_skip_orig, cur->idx, cur->au->free_clusters);
974
975 return 0;
976 }
977
978
979 /* AMAP-based allocation function for FAT32 */
980 s32 amap_fat_alloc_cluster(struct super_block *sb, u32 num_alloc, CHAIN_T *p_chain, s32 dest)
981 {
982 AMAP_T *amap = SDFAT_SB(sb)->fsi.amap;
983 TARGET_AU_T *cur = NULL;
984 AU_INFO_T *target_au = NULL; /* Allocation target AU */
985 s32 ret = -ENOSPC;
986 u32 last_clu = CLUS_EOF, read_clu;
987 u32 new_clu, total_cnt;
988 u32 num_allocated = 0, num_allocated_each = 0;
989 FS_INFO_T *fsi = &(SDFAT_SB(sb)->fsi);
990
991 BUG_ON(!amap);
992 BUG_ON(IS_CLUS_EOF(fsi->used_clusters));
993
994 total_cnt = fsi->num_clusters - CLUS_BASE;
995
996 if (unlikely(total_cnt < fsi->used_clusters)) {
997 sdfat_fs_error_ratelimit(sb,
998 "AMAP(%s): invalid used clusters(t:%u,u:%u)\n",
999 __func__, total_cnt, fsi->used_clusters);
1000 return -EIO;
1001 }
1002
1003 if (num_alloc > total_cnt - fsi->used_clusters)
1004 return -ENOSPC;
1005
1006 p_chain->dir = CLUS_EOF;
1007
1008 set_sb_dirty(sb);
1009
1010 // spin_lock(&amap->amap_lock);
1011
1012 retry_alloc:
1013 /* Allocation strategy implemented */
1014 cur = amap_get_target_au(amap, dest, fsi->reserved_clusters);
1015 if (unlikely(!cur)) {
1016 // There is no available AU (only ignored-AU are left)
1017 sdfat_msg(sb, KERN_ERR, "AMAP Allocator: no avaialble AU.");
1018 goto error;
1019 }
1020
1021 /* If there are clusters to skip */
1022 if (cur->clu_to_skip > 0) {
1023 if (amap_skip_cluster(sb, &amap->cur_cold, cur->clu_to_skip)) {
1024 ret = -EIO;
1025 goto error;
1026 }
1027 cur->clu_to_skip = 0;
1028 }
1029
1030 target_au = cur->au;
1031
1032 /*
1033 * cur->au : target AU info pointer
1034 * cur->idx : the intra-cluster idx in the AU to start from
1035 */
1036 BUG_ON(!cur->au);
1037 BUG_ON(!cur->au->free_clusters);
1038 BUG_ON(cur->idx >= amap->clusters_per_au);
1039
1040 num_allocated_each = 0;
1041 new_clu = CLU_of_i_AU(amap, target_au->idx, cur->idx);
1042
1043 do {
1044 /* Allocate at the target AU */
1045 if ((new_clu >= CLUS_BASE) && (new_clu < fsi->num_clusters)) {
1046 if (fat_ent_get(sb, new_clu, &read_clu)) {
1047 // spin_unlock(&amap->amap_lock);
1048 ret = -EIO;
1049 goto error;
1050 }
1051
1052 if (IS_CLUS_FREE(read_clu)) {
1053 BUG_ON(GET_AU(amap, i_AU_of_CLU(amap, new_clu)) != target_au);
1054
1055 /* Free cluster found */
1056 if (fat_ent_set(sb, new_clu, CLUS_EOF)) {
1057 ret = -EIO;
1058 goto error;
1059 }
1060
1061 num_allocated_each++;
1062
1063 if (IS_CLUS_EOF(p_chain->dir)) {
1064 p_chain->dir = new_clu;
1065 } else {
1066 if (fat_ent_set(sb, last_clu, new_clu)) {
1067 ret = -EIO;
1068 goto error;
1069 }
1070 }
1071 last_clu = new_clu;
1072
1073 /* Update au info */
1074 target_au->free_clusters--;
1075 }
1076
1077 }
1078
1079 new_clu++;
1080 (cur->idx)++;
1081
1082 /* End of the AU */
1083 if ((cur->idx >= amap->clusters_per_au) || !(target_au->free_clusters))
1084 break;
1085 } while (num_allocated_each < num_alloc);
1086
1087 /* Update strategy info */
1088 amap_put_target_au(amap, cur, num_allocated_each);
1089
1090
1091 num_allocated += num_allocated_each;
1092 fsi->used_clusters += num_allocated_each;
1093 num_alloc -= num_allocated_each;
1094
1095
1096 if (num_alloc > 0)
1097 goto retry_alloc;
1098
1099 // spin_unlock(&amap->amap_lock);
1100 return 0;
1101 error:
1102 if (num_allocated)
1103 fsi->fs_func->free_cluster(sb, p_chain, 0);
1104 return ret;
1105 }
1106
1107
1108 /* Free cluster for FAT32 (not implemented yet) */
1109 s32 amap_free_cluster(struct super_block *sb, CHAIN_T *p_chain, s32 do_relse)
1110 {
1111 return -ENOTSUPP;
1112 }
1113
1114
1115 /*
1116 * This is called by fat_free_cluster()
1117 * to update AMAP info.
1118 */
1119 s32 amap_release_cluster(struct super_block *sb, u32 clu)
1120 {
1121 AMAP_T *amap = SDFAT_SB(sb)->fsi.amap;
1122 AU_INFO_T *au;
1123 int i_au;
1124
1125 // spin_lock(&amap->amap_lock);
1126
1127 /* Update AU info */
1128 i_au = i_AU_of_CLU(amap, clu);
1129 BUG_ON(i_au >= amap->n_au);
1130 au = GET_AU(amap, i_au);
1131 if (au->free_clusters >= amap->clusters_per_au) {
1132 sdfat_fs_error(sb, "%s, au->free_clusters(%hd) is "
1133 "greater than or equal to amap->clusters_per_au(%hd)",
1134 __func__, au->free_clusters, amap->clusters_per_au);
1135 return -EIO;
1136 }
1137
1138 if (IS_AU_HOT(au, amap)) {
1139 MMSG("AMAP: Hot cluster freed\n");
1140 au->free_clusters++;
1141 amap->total_fclu_hot++;
1142 } else if (!IS_AU_WORKING(au, amap) && !IS_AU_IGNORED(au, amap)) {
1143 /* Ordinary AU - update AU tree */
1144 // Can be optimized by implementing amap_update_au
1145 amap_remove_cold_au(amap, au);
1146 au->free_clusters++;
1147 amap_add_cold_au(amap, au);
1148 } else
1149 au->free_clusters++;
1150
1151
1152 /* Update AMAP info */
1153 if (au->free_clusters == amap->clusters_per_au)
1154 amap->n_clean_au++;
1155 if (au->free_clusters == 1)
1156 amap->n_full_au--;
1157
1158 // spin_unlock(&amap->amap_lock);
1159 return 0;
1160 }
1161
1162
1163 /*
1164 * Check if the cluster is in a working AU
1165 * The caller should hold sb lock.
1166 * This func. should be used only if smart allocation is on
1167 */
1168 s32 amap_check_working(struct super_block *sb, u32 clu)
1169 {
1170 AMAP_T *amap = SDFAT_SB(sb)->fsi.amap;
1171 AU_INFO_T *au;
1172
1173 BUG_ON(!amap);
1174 au = GET_AU(amap, i_AU_of_CLU(amap, clu));
1175 return IS_AU_WORKING(au, amap);
1176 }
1177
1178
1179 /*
1180 * Return the # of free clusters in that AU
1181 */
1182 s32 amap_get_freeclus(struct super_block *sb, u32 clu)
1183 {
1184 AMAP_T *amap = SDFAT_SB(sb)->fsi.amap;
1185 AU_INFO_T *au;
1186
1187 BUG_ON(!amap);
1188 au = GET_AU(amap, i_AU_of_CLU(amap, clu));
1189 return (s32)au->free_clusters;
1190 }
1191
1192
1193 /*
1194 * Add the AU containing 'clu' to the ignored AU list.
1195 * The AU will not be used by the allocator.
1196 *
1197 * XXX: Ignored counter needed
1198 */
1199 s32 amap_mark_ignore(struct super_block *sb, u32 clu)
1200 {
1201 AMAP_T *amap = SDFAT_SB(sb)->fsi.amap;
1202 AU_INFO_T *au;
1203
1204 BUG_ON(!amap);
1205 au = GET_AU(amap, i_AU_of_CLU(amap, clu));
1206
1207 if (IS_AU_HOT(au, amap)) {
1208 /* Doesn't work with hot AUs */
1209 return -EPERM;
1210 } else if (IS_AU_WORKING(au, amap)) {
1211 return -EBUSY;
1212 }
1213
1214 //BUG_ON(IS_AU_IGNORED(au, amap) && (GET_IGN_CNT(au) == 0));
1215 if (IS_AU_IGNORED(au, amap))
1216 return 0;
1217
1218 amap_remove_cold_au(amap, au);
1219 amap_insert_to_list(au, &amap->slist_ignored);
1220
1221 BUG_ON(!IS_AU_IGNORED(au, amap));
1222
1223 //INC_IGN_CNT(au);
1224 MMSG("AMAP: Mark ignored AU (%d)\n", au->idx);
1225 return 0;
1226 }
1227
1228
1229 /*
1230 * This function could be used only on IGNORED AUs.
1231 * The caller should care whether it's ignored or not before using this func.
1232 */
1233 s32 amap_unmark_ignore(struct super_block *sb, u32 clu)
1234 {
1235 AMAP_T *amap = SDFAT_SB(sb)->fsi.amap;
1236 AU_INFO_T *au;
1237
1238 BUG_ON(!amap);
1239
1240 au = GET_AU(amap, i_AU_of_CLU(amap, clu));
1241
1242 BUG_ON(!IS_AU_IGNORED(au, amap));
1243 // BUG_ON(GET_IGN_CNT(au) == 0);
1244
1245 amap_remove_from_list(au, &amap->slist_ignored);
1246 amap_add_cold_au(amap, au);
1247
1248 BUG_ON(IS_AU_IGNORED(au, amap));
1249
1250 //DEC_IGN_CNT(au);
1251
1252 MMSG("AMAP: Unmark ignored AU (%d)\n", au->idx);
1253
1254 return 0;
1255 }
1256
1257 /*
1258 * Unmark all ignored AU
1259 * This will return # of unmarked AUs
1260 */
1261 s32 amap_unmark_ignore_all(struct super_block *sb)
1262 {
1263 AMAP_T *amap = SDFAT_SB(sb)->fsi.amap;
1264 struct slist_head *entry;
1265 AU_INFO_T *au;
1266 int n = 0;
1267
1268 BUG_ON(!amap);
1269 entry = amap->slist_ignored.next;
1270 while (entry) {
1271 au = list_entry(entry, AU_INFO_T, shead);
1272
1273 BUG_ON(au != GET_AU(amap, au->idx));
1274 BUG_ON(!IS_AU_IGNORED(au, amap));
1275
1276 //CLEAR_IGN_CNT(au);
1277 amap_remove_from_list(au, &amap->slist_ignored);
1278 amap_add_cold_au(amap, au);
1279
1280 MMSG("AMAP: Unmark ignored AU (%d)\n", au->idx);
1281 n++;
1282
1283 entry = amap->slist_ignored.next;
1284 }
1285
1286 BUG_ON(amap->slist_ignored.next != NULL);
1287 MMSG("AMAP: unmark_ignore_all, total %d AUs\n", n);
1288
1289 return n;
1290 }
1291
1292 /**
1293 * @fn amap_get_au_stat
1294 * @brief report AUs status depending on mode
1295 * @return positive on success, 0 otherwise
1296 * @param sbi super block info
1297 * @param mode TOTAL, CLEAN and FULL
1298 */
1299 u32 amap_get_au_stat(struct super_block *sb, s32 mode)
1300 {
1301 AMAP_T *amap = SDFAT_SB(sb)->fsi.amap;
1302
1303 if (!amap)
1304 return 0;
1305
1306 if (mode == VOL_AU_STAT_TOTAL)
1307 return amap->n_au;
1308 else if (mode == VOL_AU_STAT_CLEAN)
1309 return amap->n_clean_au;
1310 else if (mode == VOL_AU_STAT_FULL)
1311 return amap->n_full_au;
1312
1313 return 0;
1314 }
1315