flash_device.cc revision 11180:406240a8e7ef
12689Sktlim@umich.edu/* 22689Sktlim@umich.edu * Copyright (c) 2013-2015 ARM Limited 32689Sktlim@umich.edu * All rights reserved 42689Sktlim@umich.edu * 52689Sktlim@umich.edu * The license below extends only to copyright in the software and shall 62689Sktlim@umich.edu * not be construed as granting a license to any other intellectual 72689Sktlim@umich.edu * property including but not limited to intellectual property relating 82689Sktlim@umich.edu * to a hardware implementation of the functionality of the software 92689Sktlim@umich.edu * licensed hereunder. You may use the software subject to the license 102689Sktlim@umich.edu * terms below provided that you ensure that this notice is replicated 112689Sktlim@umich.edu * unmodified and in its entirety in all distributions of the software, 122689Sktlim@umich.edu * modified or unmodified, in source code or in binary form. 132689Sktlim@umich.edu * 142689Sktlim@umich.edu * Redistribution and use in source and binary forms, with or without 152689Sktlim@umich.edu * modification, are permitted provided that the following conditions are 162689Sktlim@umich.edu * met: redistributions of source code must retain the above copyright 172689Sktlim@umich.edu * notice, this list of conditions and the following disclaimer; 182689Sktlim@umich.edu * redistributions in binary form must reproduce the above copyright 192689Sktlim@umich.edu * notice, this list of conditions and the following disclaimer in the 202689Sktlim@umich.edu * documentation and/or other materials provided with the distribution; 212689Sktlim@umich.edu * neither the name of the copyright holders nor the names of its 222689Sktlim@umich.edu * contributors may be used to endorse or promote products derived from 232689Sktlim@umich.edu * this software without specific prior written permission. 242689Sktlim@umich.edu * 252689Sktlim@umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 262689Sktlim@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 272689Sktlim@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 282689Sktlim@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 292689Sktlim@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 302689Sktlim@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 312683Sktlim@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 322683Sktlim@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 332683Sktlim@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 342683Sktlim@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 352683Sktlim@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 362683Sktlim@umich.edu * 372683Sktlim@umich.edu * Authors: Rene de Jong 382683Sktlim@umich.edu */ 392683Sktlim@umich.edu 402683Sktlim@umich.edu/** @file 412683Sktlim@umich.edu * This simplistic flash model is designed to model managed SLC NAND flash. 422683Sktlim@umich.edu * This device will need an interface module (such as NVMe or UFS); Note that 432683Sktlim@umich.edu * this model only calculates the delay and does not perform the actual 442683Sktlim@umich.edu * transaction. 452683Sktlim@umich.edu * 462683Sktlim@umich.edu * To access the memory, use either readMemory or writeMemory. This will 472683Sktlim@umich.edu * schedule an event at the tick where the action will finish. If a callback 482683Sktlim@umich.edu * has been given as argument then that function will be called on completion 492683Sktlim@umich.edu * of that event. Note that this does not guarantee that there are no other 502683Sktlim@umich.edu * actions pending in the flash device. 512683Sktlim@umich.edu * 522683Sktlim@umich.edu * IMPORTANT: number of planes should be a power of 2. 532683Sktlim@umich.edu */ 542683Sktlim@umich.edu 552683Sktlim@umich.edu#include "dev/arm/flash_device.hh" 562683Sktlim@umich.edu 572683Sktlim@umich.edu#include "debug/Drain.hh" 582683Sktlim@umich.edu 592683Sktlim@umich.edu/** 602683Sktlim@umich.edu * Create this device 612683Sktlim@umich.edu */ 622683Sktlim@umich.edu 632683Sktlim@umich.eduFlashDevice* 642683Sktlim@umich.eduFlashDeviceParams::create() 652683Sktlim@umich.edu{ 662683Sktlim@umich.edu return new FlashDevice(this); 672683Sktlim@umich.edu} 682683Sktlim@umich.edu 692683Sktlim@umich.edu 702683Sktlim@umich.edu/** 712683Sktlim@umich.edu * Flash Device constructor and destructor 722683Sktlim@umich.edu */ 732683Sktlim@umich.edu 742683Sktlim@umich.eduFlashDevice::FlashDevice(const FlashDeviceParams* p): 752683Sktlim@umich.edu AbstractNVM(p), 762683Sktlim@umich.edu diskSize(0), 77 blockSize(p->blk_size), 78 pageSize(p->page_size), 79 GCActivePercentage(p->GC_active), 80 readLatency(p->read_lat), 81 writeLatency(p->write_lat), 82 eraseLatency(p->erase_lat), 83 dataDistribution(p->data_distribution), 84 numPlanes(p->num_planes), 85 pagesPerBlock(0), 86 pagesPerDisk(0), 87 blocksPerDisk(0), 88 planeMask(numPlanes - 1), 89 planeEventQueue(numPlanes), 90 planeEvent(this) 91{ 92 93 /* 94 * Let 'a' be a power of two of n bits, written such that a-n is the msb 95 * and a-0 is the lsb. Since it is a power of two, only one bit (a-x, 96 * with 0 <= x <= n) is set. If we subtract one from this number the bits 97 * a-(x-1) to a-0 are set and all the other bits are cleared. Hence a 98 * bitwise AND with those two numbers results in an integer with all bits 99 * cleared. 100 */ 101 if(numPlanes & planeMask) 102 fatal("Number of planes is not a power of 2 in flash device.\n"); 103} 104 105/** 106 * Initiates all the flash functions: initializes the lookup tables, age of 107 * the device, etc. This can only be done once the disk image is known. 108 * Thats why it can't be done in the constructor. 109 */ 110void 111FlashDevice::initializeFlash(uint64_t disk_size, uint32_t sector_size) 112{ 113 diskSize = disk_size * sector_size; 114 pagesPerBlock = blockSize / pageSize; 115 pagesPerDisk = diskSize / pageSize; 116 blocksPerDisk = diskSize / blockSize; 117 118 /** Sanity information: check flash configuration */ 119 DPRINTF(FlashDevice, "diskSize: %d Bytes; %d pages per block, %d pages " 120 "per disk\n", diskSize, pagesPerBlock, pagesPerDisk); 121 122 locationTable.resize(pagesPerDisk); 123 124 /**Garbage collection related*/ 125 blockValidEntries.resize(blocksPerDisk, 0); 126 blockEmptyEntries.resize(blocksPerDisk, pagesPerBlock); 127 128 /** 129 * This is a bitmap. Every bit is a page 130 * unknownPages is a vector of 32 bit integers. If every page was an 131 * integer, the total size would be pagesPerDisk; since we can map one 132 * page per bit we need ceil(pagesPerDisk/32) entries. 32 = 1 << 5 hence 133 * it will do to just shift pagesPerDisk five positions and add one. This 134 * will allocate one integer to many for this data structure in the worst 135 * case. 136 */ 137 unknownPages.resize((pagesPerDisk >> 5) + 1, 0xFFFFFFFF); 138 139 for (uint32_t count = 0; count < pagesPerDisk; count++) { 140 //setup lookup table + physical aspects 141 142 if (dataDistribution == Enums::stripe) { 143 locationTable[count].page = count / blocksPerDisk; 144 locationTable[count].block = count % blocksPerDisk; 145 146 } else { 147 locationTable[count].page = count % pagesPerBlock; 148 locationTable[count].block = count / pagesPerBlock; 149 } 150 } 151} 152 153FlashDevice::~FlashDevice() 154{ 155 DPRINTF(FlashDevice, "Remove FlashDevice\n"); 156} 157 158/** 159 * Handles the accesses to the device. 160 * The function determines when certain actions are scheduled and schedules 161 * an event that uses the callback function on completion of the action. 162 */ 163void 164FlashDevice::accessDevice(uint64_t address, uint32_t amount, Callback *event, 165 Actions action) 166{ 167 DPRINTF(FlashDevice, "Flash calculation for %d bytes in %d pages\n" 168 , amount, pageSize); 169 170 std::vector<Tick> time(numPlanes, 0); 171 uint64_t logic_page_addr = address / pageSize; 172 uint32_t plane_address = 0; 173 174 /** 175 * The access will be broken up in a number of page accesses. The number 176 * of page accesses depends on the amount that needs to be transfered. 177 * The assumption here is that the interface is completely ignorant of 178 * the page size and that this model has to figure out all of the 179 * transaction characteristics. 180 */ 181 for (uint32_t count = 0; amount > (count * pageSize); count++) { 182 uint32_t index = (locationTable[logic_page_addr].block * 183 pagesPerBlock) + (logic_page_addr % pagesPerBlock); 184 185 DPRINTF(FlashDevice, "Index 0x%8x, Block 0x%8x, pages/block %d," 186 " logic address 0x%8x\n", index, 187 locationTable[logic_page_addr].block, pagesPerBlock, 188 logic_page_addr); 189 DPRINTF(FlashDevice, "Page %d; %d bytes up to this point\n", count, 190 (count * pageSize)); 191 192 plane_address = locationTable[logic_page_addr].block & planeMask; 193 194 if (action == ActionRead) { 195 //lookup 196 //call accessTimes 197 time[plane_address] += accessTimes(locationTable[logic_page_addr] 198 .block, ActionRead); 199 200 /*stats*/ 201 stats.readAccess.sample(logic_page_addr); 202 stats.readLatency.sample(time[plane_address]); 203 } else { //write 204 //lookup 205 //call accessTimes if appropriate, page may be unknown, so lets 206 //give it the benefit of the doubt 207 208 if (getUnknownPages(index)) 209 time[plane_address] += accessTimes 210 (locationTable[logic_page_addr].block, ActionWrite); 211 212 else //A remap is needed 213 time[plane_address] += remap(logic_page_addr); 214 215 /*stats*/ 216 stats.writeAccess.sample(logic_page_addr); 217 stats.writeLatency.sample(time[plane_address]); 218 } 219 220 /** 221 * Check if the page is known and used. unknownPages is a bitmap of 222 * all the pages. It tracks wether we can be sure that the 223 * information of this page is taken into acount in the model (is it 224 * considered in blockValidEntries and blockEmptyEntries?). If it has 225 * been used in the past, then it is known. 226 */ 227 if (getUnknownPages(index)) { 228 clearUnknownPages(index); 229 --blockEmptyEntries[locationTable[logic_page_addr].block]; 230 ++blockValidEntries[locationTable[logic_page_addr].block]; 231 } 232 233 stats.fileSystemAccess.sample(address); 234 ++logic_page_addr; 235 } 236 237 /** 238 * previous part of the function found the times spend in different 239 * planes, now lets find the maximum to know when to callback the disk 240 */ 241 for (uint32_t count = 0; count < numPlanes; count++){ 242 plane_address = (time[plane_address] > time[count]) ? plane_address 243 : count; 244 245 DPRINTF(FlashDevice, "Plane %d is busy for %d ticks\n", count, 246 time[count]); 247 248 if (time[count] != 0) { 249 250 struct CallBackEntry cbe; 251 /** 252 * If there are no events for this plane, then add the current 253 * time to the occupation time; otherwise, plan it after the 254 * last event. If by chance that event is handled in this tick, 255 * then we would still end up with the same result. 256 */ 257 if (planeEventQueue[count].empty()) 258 cbe.time = time[count] + curTick(); 259 else 260 cbe.time = time[count] + 261 planeEventQueue[count].back().time; 262 cbe.function = NULL; 263 planeEventQueue[count].push_back(cbe); 264 265 DPRINTF(FlashDevice, "scheduled at: %ld\n", cbe.time); 266 267 if (!planeEvent.scheduled()) 268 schedule(planeEvent, planeEventQueue[count].back().time); 269 else if (planeEventQueue[count].back().time < planeEvent.when()) 270 reschedule(planeEvent, 271 planeEventQueue[plane_address].back().time, true); 272 } 273 } 274 275 //worst case two plane finish at the same time, each triggers an event 276 //and this callback will be called once. Maybe before the other plane 277 //could execute its event, but in the same tick. 278 planeEventQueue[plane_address].back().function = event; 279 DPRINTF(FlashDevice, "Callback queued for plane %d; %d in queue\n", 280 plane_address, planeEventQueue[plane_address].size()); 281 DPRINTF(FlashDevice, "first event @ %d\n", planeEvent.when()); 282} 283 284/** 285 * When a plane completes its action, this event is triggered. When a 286 * callback function was associated with that event, it will be called. 287 */ 288 289void 290FlashDevice::actionComplete() 291{ 292 DPRINTF(FlashDevice, "Plane action completed\n"); 293 uint8_t plane_address = 0; 294 295 uint8_t next_event = 0; 296 297 /**Search for a callback that is supposed to happen in this Tick*/ 298 for (plane_address = 0; plane_address < numPlanes; plane_address++) { 299 if (!planeEventQueue[plane_address].empty()) { 300 /** 301 * Invariant: All queued events are scheduled in the present 302 * or future. 303 */ 304 assert(planeEventQueue[plane_address].front().time >= curTick()); 305 306 if (planeEventQueue[plane_address].front().time == curTick()) { 307 /** 308 * To ensure that the follow-up action is executed correctly, 309 * the callback entry first need to be cleared before it can 310 * be called. 311 */ 312 Callback *temp = planeEventQueue[plane_address].front(). 313 function; 314 planeEventQueue[plane_address].pop_front(); 315 316 /**Found a callback, lets make it happen*/ 317 if (temp != NULL) { 318 DPRINTF(FlashDevice, "Callback, %d\n", plane_address); 319 temp->process(); 320 } 321 } 322 } 323 } 324 325 /** Find when to schedule the planeEvent next */ 326 for (plane_address = 0; plane_address < numPlanes; plane_address++) { 327 if (!planeEventQueue[plane_address].empty()) 328 if (planeEventQueue[next_event].empty() || 329 (planeEventQueue[plane_address].front().time < 330 planeEventQueue[next_event].front().time)) 331 next_event = plane_address; 332 } 333 334 /**Schedule the next plane that will be ready (if any)*/ 335 if (!planeEventQueue[next_event].empty()) { 336 DPRINTF(FlashDevice, "Schedule plane: %d\n", plane_address); 337 reschedule(planeEvent, planeEventQueue[next_event].front().time, true); 338 } 339 340 checkDrain(); 341 342 DPRINTF(FlashDevice, "returing from flash event\n"); 343 DPRINTF(FlashDevice, "first event @ %d\n", planeEvent.when()); 344} 345 346/** 347 * Handles the remapping of the pages. It is a (I hope) sensible statistic 348 * approach. asumption: garbage collection happens when a clean is needed 349 * (may become stochastic function). 350 */ 351Tick 352FlashDevice::remap(uint64_t logic_page_addr) 353{ 354 /** 355 * Are there any empty left in this Block, or do we need to do an erase 356 */ 357 if (blockEmptyEntries[locationTable[logic_page_addr].block] > 0) { 358 //just a remap 359 //update tables 360 --blockEmptyEntries[locationTable[logic_page_addr].block]; 361 //access to this table won't be sequential anymore 362 locationTable[logic_page_addr].page = pagesPerBlock + 2; 363 //access new block 364 Tick time = accessTimes(locationTable[logic_page_addr].block, 365 ActionWrite); 366 367 DPRINTF(FlashDevice, "Remap returns %d ticks\n", time); 368 return time; 369 370 } else { 371 //calculate how much time GC would have taken 372 uint32_t block = locationTable[logic_page_addr].block; 373 Tick time = ((GCActivePercentage * 374 (accessTimes(block, ActionCopy) + 375 accessTimes(block, ActionErase))) 376 / 100); 377 378 //use block as the logical start address of the block 379 block = locationTable[logic_page_addr].block * pagesPerBlock; 380 381 //assumption: clean will improve locality 382 for (uint32_t count = 0; count < pagesPerBlock; count++) { 383 assert(block + count < pagesPerDisk); 384 locationTable[block + count].page = (block + count) % 385 pagesPerBlock; 386 ++count; 387 } 388 389 blockEmptyEntries[locationTable[logic_page_addr].block] = 390 pagesPerBlock; 391 /*stats*/ 392 ++stats.totalGCActivations; 393 394 DPRINTF(FlashDevice, "Remap with erase action returns %d ticks\n", 395 time); 396 397 return time; 398 } 399 400} 401 402/** 403 * Calculates the accesstime per operation needed 404 */ 405Tick 406FlashDevice::accessTimes(uint64_t block, Actions action) 407{ 408 Tick time = 0; 409 410 switch(action) { 411 case ActionRead: { 412 /**Just read the page*/ 413 time = readLatency; 414 } break; 415 416 case ActionWrite: { 417 /**Write the page, and read the result*/ 418 time = writeLatency + readLatency; 419 } break; 420 421 case ActionErase: { 422 /**Erase and check wether it was successfull*/ 423 time = eraseLatency + readLatency; 424 } break; 425 426 case ActionCopy: { 427 /**Copy every valid page*/ 428 uint32_t validpages = blockValidEntries[block]; 429 time = validpages * (readLatency + writeLatency); 430 } break; 431 432 default: break; 433 } 434 435 //Used to determine sequential action. 436 DPRINTF(FlashDevice, "Access returns %d ticks\n", time); 437 return time; 438} 439 440/** 441 * clearUnknownPages. defines that a page is known and used 442 * unknownPages is a bitmap of all the pages. It tracks wether we can be sure 443 * that the information of this page is taken into acount in the model (is it 444 * considered in blockValidEntries and blockEmptyEntries?). If it has been 445 * used in the past, then it is known. But it needs to be tracked to make 446 * decisions about write accesses, and indirectly about copy actions. one 447 * unknownPage entry is a 32 bit integer. So if we have a page index, then 448 * that means that we need entry floor(index/32) (index >> 5) and we need to 449 * select the bit which number is equal to the remainder of index/32 450 * (index%32). The bit is cleared to make sure that we see it as considered 451 * in the future. 452 */ 453 454inline 455void 456FlashDevice::clearUnknownPages(uint32_t index) 457{ 458 unknownPages[index >> 5] &= ~(0x01 << (index % 32)); 459} 460 461/** 462 * getUnknownPages. Verify wether a page is known 463 */ 464 465inline 466bool 467FlashDevice::getUnknownPages(uint32_t index) 468{ 469 return unknownPages[index >> 5] & (0x01 << (index % 32)); 470} 471 472void 473FlashDevice::regStats() 474{ 475 using namespace Stats; 476 477 std::string fd_name = name() + ".FlashDevice"; 478 479 // Register the stats 480 /** Amount of GC activations*/ 481 stats.totalGCActivations 482 .name(fd_name + ".totalGCActivations") 483 .desc("Number of Garbage collector activations") 484 .flags(none); 485 486 /** Histogram of address accesses*/ 487 stats.writeAccess 488 .init(2) 489 .name(fd_name + ".writeAccessHist") 490 .desc("Histogram of write addresses") 491 .flags(pdf); 492 stats.readAccess 493 .init(2) 494 .name(fd_name + ".readAccessHist") 495 .desc("Histogram of read addresses") 496 .flags(pdf); 497 stats.fileSystemAccess 498 .init(100) 499 .name(fd_name + ".fileSystemAccessHist") 500 .desc("Histogram of file system accesses") 501 .flags(pdf); 502 503 /** Histogram of access latencies*/ 504 stats.writeLatency 505 .init(100) 506 .name(fd_name + ".writeLatencyHist") 507 .desc("Histogram of write latency") 508 .flags(pdf); 509 stats.readLatency 510 .init(100) 511 .name(fd_name + ".readLatencyHist") 512 .desc("Histogram of read latency") 513 .flags(pdf); 514} 515 516/** 517 * Serialize; needed to create checkpoints 518 */ 519 520void 521FlashDevice::serialize(CheckpointOut &cp) const 522{ 523 SERIALIZE_SCALAR(planeMask); 524 525 int unknown_pages_size = unknownPages.size(); 526 SERIALIZE_SCALAR(unknown_pages_size); 527 for (uint32_t count = 0; count < unknownPages.size(); count++) 528 SERIALIZE_SCALAR(unknownPages[count]); 529 530 int location_table_size = locationTable.size(); 531 SERIALIZE_SCALAR(location_table_size); 532 for (uint32_t count = 0; count < location_table_size; count++) { 533 SERIALIZE_SCALAR(locationTable[count].page); 534 SERIALIZE_SCALAR(locationTable[count].block); 535 } 536 537 int block_valid_entries_size = blockValidEntries.size(); 538 SERIALIZE_SCALAR(block_valid_entries_size); 539 for (uint32_t count = 0; count < blockValidEntries.size(); count++) 540 SERIALIZE_SCALAR(blockValidEntries[count]); 541 542 int block_empty_entries_size = blockEmptyEntries.size(); 543 SERIALIZE_SCALAR(block_empty_entries_size); 544 for (uint32_t count = 0; count < blockEmptyEntries.size(); count++) 545 SERIALIZE_SCALAR(blockEmptyEntries[count]); 546 547}; 548 549/** 550 * Unserialize; needed to restore from checkpoints 551 */ 552 553void 554FlashDevice::unserialize(CheckpointIn &cp) 555{ 556 UNSERIALIZE_SCALAR(planeMask); 557 558 int unknown_pages_size; 559 UNSERIALIZE_SCALAR(unknown_pages_size); 560 unknownPages.resize(unknown_pages_size); 561 for (uint32_t count = 0; count < unknown_pages_size; count++) 562 UNSERIALIZE_SCALAR(unknownPages[count]); 563 564 int location_table_size; 565 UNSERIALIZE_SCALAR(location_table_size); 566 locationTable.resize(location_table_size); 567 for (uint32_t count = 0; count < location_table_size; count++) { 568 UNSERIALIZE_SCALAR(locationTable[count].page); 569 UNSERIALIZE_SCALAR(locationTable[count].block); 570 } 571 572 int block_valid_entries_size; 573 UNSERIALIZE_SCALAR(block_valid_entries_size); 574 blockValidEntries.resize(block_valid_entries_size); 575 for (uint32_t count = 0; count < block_valid_entries_size; count++) 576 UNSERIALIZE_SCALAR(blockValidEntries[count]); 577 578 int block_empty_entries_size; 579 UNSERIALIZE_SCALAR(block_empty_entries_size); 580 blockEmptyEntries.resize(block_empty_entries_size); 581 for (uint32_t count = 0; count < block_empty_entries_size; count++) 582 UNSERIALIZE_SCALAR(blockEmptyEntries[count]); 583 584}; 585 586/** 587 * Drain; needed to enable checkpoints 588 */ 589 590DrainState 591FlashDevice::drain() 592{ 593 if (planeEvent.scheduled()) { 594 DPRINTF(Drain, "Flash device is draining...\n"); 595 return DrainState::Draining; 596 } else { 597 DPRINTF(Drain, "Flash device in drained state\n"); 598 return DrainState::Drained; 599 } 600} 601 602/** 603 * Checkdrain; needed to enable checkpoints 604 */ 605 606void 607FlashDevice::checkDrain() 608{ 609 if (drainState() != DrainState::Draining) 610 return; 611 612 if (planeEvent.when() > curTick()) { 613 DPRINTF(Drain, "Flash device is still draining\n"); 614 } else { 615 DPRINTF(Drain, "Flash device is done draining\n"); 616 signalDrainDone(); 617 } 618} 619