flash_device.cc revision 11180
1/*
2 * Copyright (c) 2013-2015 ARM Limited
3 * All rights reserved
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder.  You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
13 *
14 * Redistribution and use in source and binary forms, with or without
15 * modification, are permitted provided that the following conditions are
16 * met: redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer;
18 * redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution;
21 * neither the name of the copyright holders nor the names of its
22 * contributors may be used to endorse or promote products derived from
23 * this software without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
29 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
31 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
35 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 *
37 * Authors: Rene de Jong
38 */
39
40/** @file
41 * This simplistic flash model is designed to model managed SLC NAND flash.
42 * This device will need an interface module (such as NVMe or UFS); Note that
43 * this model only calculates the delay and does not perform the actual
44 * transaction.
45 *
46 * To access the memory, use either readMemory or writeMemory. This will
47 * schedule an event at the tick where the action will finish. If a callback
48 * has been given as argument then that function will be called on completion
49 * of that event. Note that this does not guarantee that there are no other
50 * actions pending in the flash device.
51 *
52 * IMPORTANT: number of planes should be a power of 2.
53 */
54
55#include "dev/arm/flash_device.hh"
56
57#include "debug/Drain.hh"
58
59/**
60 * Create this device
61 */
62
63FlashDevice*
64FlashDeviceParams::create()
65{
66    return new FlashDevice(this);
67}
68
69
70/**
71 * Flash Device constructor and destructor
72 */
73
74FlashDevice::FlashDevice(const FlashDeviceParams* p):
75    AbstractNVM(p),
76    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