Go to the documentation of this file.00001 #include <stdlib.h>
00002 #include <string.h>
00003 #include "debug.h"
00004 #include "nand.h"
00005 #include "vmbitmap.h"
00006 #include "map.h"
00007 #include "ftl.h"
00008 #include "stat.h"
00009
00010 #define MIN_FREE_BLKS 10
00011 #define GC_BLKS 5
00012
00013 int indexpages;
00014
00015 enum { BLOCK_FREE=0,
00016 BLOCK_DATA,
00017 BLOCK_INDEX,
00018 BLOCK_GC,
00019 };
00020
00021 struct vbm_entry {
00022 _s32 invalid;
00023 _s32 map;
00024 _s32 score;
00025 };
00026
00027
00028
00029
00030
00031
00032 static struct _t_vm {
00033 struct vbm_entry *vbm;
00034
00035 _t_blk totblks;
00036
00037 _u32 *update_blk_no;
00038 _u32 *update_page_no;
00039 unsigned int max_update_blk;
00040 int max_score;
00041
00042 int fb_num;
00043 _t_blk cur_fb_no;
00044 } vm;
00045
00046
00047
00048
00049 _t_blk vm_alloc_block(int reqtype) {
00050 unsigned int i;
00051 _t_blk blkno;
00052 if(vm.fb_num == 0) {
00053 error("No free blocks. Need GC?\n");
00054 assert(0);
00055 }
00056
00057 for(i=0;i<vm.totblks; i++) {
00058 if(vm.vbm[vm.cur_fb_no].map==BLOCK_FREE) {
00059 blkno = vm.cur_fb_no;
00060 break;
00061 }
00062 vm.cur_fb_no++;
00063 if(vm.cur_fb_no>=vm.totblks) vm.cur_fb_no=0;
00064 }
00065 if(i==vm.totblks) {
00066 error("Can't find free block...\n");
00067 assert(0);
00068 return -1;
00069 }
00070 switch(reqtype) {
00071 case NAND_REQ_DATA:
00072 case NAND_REQ_GC:
00073 case NAND_REQ_WARM:
00074 vm.vbm[blkno].map=BLOCK_DATA;
00075 break;
00076 }
00077 vm.fb_num--;
00078
00079 return blkno;
00080 }
00081
00082
00083
00084
00085
00086
00087
00088
00089 _u32 vm_alloc_page(_t_sect lsn, _t_blk *pbn, _t_page *ppn, int reqtype) {
00090 int i, idxupd;
00091 switch(reqtype) {
00092 case NAND_REQ_DATA:
00093 case NAND_REQ_GC:
00094 idxupd = 0;
00095 break;
00096 case NAND_REQ_WARM:
00097 idxupd = 0;
00098 break;
00099 default:
00100 idxupd = vm.max_update_blk-1;
00101 indexpages++;
00102 if(indexpages==34) {
00103 i=3;
00104 }
00105 break;
00106 }
00107
00108 vm.update_page_no[idxupd]++;
00109
00110
00111 if(vm.update_page_no[idxupd]>=config_nand.page_per_blk) {
00112 vm.update_blk_no[idxupd] = vm_alloc_block(reqtype);
00113 vm.update_page_no[idxupd] = 0;
00114 }
00115
00116 *pbn = vm.update_blk_no[idxupd];
00117 *ppn = vm.update_page_no[idxupd];
00118
00119 assert(*pbn<config_nand.numblks);
00120 return 0;
00121 }
00122
00123
00124
00125
00126
00127 _t_blk vm_get_victim() {
00128 unsigned int i, j;
00129 int maxinvalid=0;
00130 _t_blk blkno;
00131
00132 for(i=0;i<vm.totblks;i++) {
00133
00134 if(vm.vbm[i].map==BLOCK_FREE) continue;
00135
00136 if(vm.vbm[i].invalid>=config_nand.page_per_blk) {
00137 blkno=i;
00138 break;
00139 }
00140
00141
00142 for(j=0;j<vm.max_update_blk;j++) {
00143 if(vm.update_blk_no[j]==i) {
00144 break;
00145 }
00146 }
00147 if(j!=vm.max_update_blk) continue;
00148
00149
00150 if(vm.vbm[i].invalid> maxinvalid) {
00151 maxinvalid = vm.vbm[i].invalid;
00152 blkno = i;
00153 }
00154 }
00155
00156 return blkno;
00157 }
00158
00159
00160
00161
00162
00163 int bitmap_sum(_u8 *bitmap) {
00164 int i, res=0;
00165 for(i=0;i<config_nand.page_per_blk;i++) {
00166 if(bitmap[i]) res++;
00167 }
00168 return res;
00169 }
00170
00171
00172
00173
00174 void vm_gc_run(_t_blk victim) {
00175 int i;
00176 _u32 opt;
00177 _u8 *block_bitmap;
00178 _t_sect lsn, lpa;
00179 _t_blk pbn;
00180 _t_page ppn;
00181
00182 block_bitmap = (_u8 *)malloc(sizeof(_u8) * config_nand.page_per_blk);
00183
00184
00185 bitmap_s_get_block(victim, block_bitmap);
00186 assert(bitmap_sum(block_bitmap)==vm.vbm[victim].invalid);
00187
00188 for(i=0; i< config_nand.page_per_blk; i++) {
00189 if(!block_bitmap[i]) {
00190
00191 lsn = nand_page_read(victim, i, 0, NAND_REQ_GC);
00192 lpa = LPA_F_SECT(lsn);
00193 opt = 0;
00194 pbn = victim;
00195
00196
00197 vm_alloc_page(lsn, &pbn, &ppn, NAND_REQ_GC);
00198
00199 nand_page_write(pbn, ppn, lsn, NAND_REQ_GC);
00200 vm_invalidate(victim, i, 1);
00201 map_update(lpa, MAKE_PA(pbn, ppn));
00202 }
00203 }
00204
00205 free(block_bitmap);
00206 }
00207
00208
00209
00210
00211 void vm_clear_block(_t_blk victim, int type) {
00212 unsigned int i;
00213 assert(vm.vbm[victim].map!=BLOCK_FREE);
00214 bitmap_s_clear_block(victim);
00215
00216 nand_block_erase(victim, type);
00217 vm.vbm[victim].map=BLOCK_FREE;
00218 vm.vbm[victim].invalid=0;
00219 vm.fb_num++;
00220
00221 for(i=0;i<vm.max_update_blk;i++) {
00222 if(vm.update_blk_no[i]==victim) {
00223 vm.update_blk_no[i]=-1;
00224 vm.update_page_no[i] = config_nand.page_per_blk;
00225 }
00226 }
00227 }
00228
00229
00230
00231
00232
00233
00234
00235 void vm_invalidate(_t_blk victim, _t_page ppn, _t_size length) {
00236 vm.vbm[victim].invalid+=length;
00237 assert(vm.vbm[victim].invalid<=config_nand.page_per_blk);
00238 if(vm.vbm[victim].map==BLOCK_INDEX) {
00239 indexpages-=length;
00240 }
00241
00242 bitmap_s_invalidate(victim, ppn, length);
00243
00244
00245 if(vm.vbm[victim].map==BLOCK_DATA && vm.vbm[victim].invalid==config_nand.page_per_blk) {
00246 vm_clear_block(victim, NAND_REQ_GC);
00247 }
00248 }
00249
00250 int vm_gc_check() {
00251 return vm.fb_num < MIN_FREE_BLKS;
00252 }
00253
00254
00255
00256
00257
00258 void vm_gc_start() {
00259 _u8 *bitmap;
00260 _t_blk victim;
00261
00262 if(!vm_gc_check()) {
00263 return;
00264 }
00265
00266 bitmap = (_u8 *)malloc(sizeof(_u8)*config_nand.page_per_blk);
00267 while(vm.fb_num < MIN_FREE_BLKS+GC_BLKS) {
00268
00269 victim = vm_get_victim();
00270 if(vm.vbm[victim].map==BLOCK_INDEX) {
00271 vm.vbm[victim].map=BLOCK_GC;
00272 bitmap_s_get_block(victim, bitmap);
00273
00274 assert(bitmap_sum(bitmap)==vm.vbm[victim].invalid);
00275 indexpages-=config_nand.page_per_blk - vm.vbm[victim].invalid;
00276 map_gc(victim, bitmap);
00277
00278 vm_clear_block(victim, NAND_REQ_DATA);
00279 } else {
00280 vm.vbm[victim].map=BLOCK_GC;
00281
00282 vm_gc_run(victim);
00283
00284 vm_clear_block(victim, NAND_REQ_DATA);
00285 }
00286 }
00287
00288 free(bitmap);
00289 }
00290
00291
00292
00293
00294 void vm_end() {
00295 if(vm.update_blk_no) {
00296 free(vm.update_blk_no);
00297 vm.update_blk_no=NULL;
00298 }
00299 if(vm.update_page_no) {
00300 free(vm.update_page_no);
00301 vm.update_page_no=NULL;
00302 }
00303 if(vm.vbm) {
00304 free(vm.vbm);
00305 vm.vbm = NULL;
00306 }
00307 }
00308
00309
00310
00311
00312 void vm_init() {
00313 unsigned int i;
00314
00315 vm.max_update_blk = 2;
00316
00317 vm.update_blk_no = (_u32 *)malloc(vm.max_update_blk * sizeof(_u32));
00318 vm.update_page_no = (_u32 *)malloc(vm.max_update_blk * sizeof(_u32));
00319 for(i=0;i<vm.max_update_blk;i++) {
00320 vm.update_blk_no[i] = -1;
00321 vm.update_page_no[i] = config_nand.page_per_blk;
00322 }
00323
00324 vm.fb_num = config_nand.numblks;
00325 vm.cur_fb_no = 0;
00326
00327 vm.totblks = config_nand.numblks;
00328 vm.vbm = (struct vbm_entry *)malloc(vm.totblks * sizeof(struct vbm_entry));
00329 for(i=0;i<vm.totblks;i++) {
00330 vm.vbm[i].invalid=0;
00331 vm.vbm[i].map = BLOCK_FREE;
00332 vm.vbm[i].score = 0;
00333 }
00334
00335 }