flash_device.cc

Go to the documentation of this file.

/*
 * Copyright (c) 2013-2015 ARM Limited
 * All rights reserved
 *
 * The license below extends only to copyright in the software and shall
 * not be construed as granting a license to any other intellectual
 * property including but not limited to intellectual property relating
 * to a hardware implementation of the functionality of the software
 * licensed hereunder.  You may use the software subject to the license
 * terms below provided that you ensure that this notice is replicated
 * unmodified and in its entirety in all distributions of the software,
 * modified or unmodified, in source code or in binary form.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Rene de Jong
 */

#include "dev/arm/flash_device.hh"

#include "base/trace.hh"
#include "debug/Drain.hh"

FlashDevice*
FlashDeviceParams::create()
{
    return new FlashDevice(this);
}


FlashDevice::FlashDevice(const FlashDeviceParams* p):
    AbstractNVM(p),
    diskSize(0),
    blockSize(p->blk_size),
    pageSize(p->page_size),
    GCActivePercentage(p->GC_active),
    readLatency(p->read_lat),
    writeLatency(p->write_lat),
    eraseLatency(p->erase_lat),
    dataDistribution(p->data_distribution),
    numPlanes(p->num_planes),
    pagesPerBlock(0),
    pagesPerDisk(0),
    blocksPerDisk(0),
    planeMask(numPlanes - 1),
    planeEventQueue(numPlanes),
    planeEvent([this]{ actionComplete(); }, name())
{

    /*
     * Let 'a' be a power of two of n bits, written such that a-n is the msb
     * and a-0 is the lsb. Since it is a power of two, only one bit (a-x,
     * with 0 <= x <= n) is set. If we subtract one from this number the bits
     * a-(x-1) to a-0 are set and all the other bits are cleared. Hence a
     * bitwise AND with those two numbers results in an integer with all bits
     * cleared.
     */
    if (numPlanes & planeMask)
        fatal("Number of planes is not a power of 2 in flash device.\n");
}

void
FlashDevice::initializeFlash(uint64_t disk_size, uint32_t sector_size)
{
    diskSize = disk_size * sector_size;
    pagesPerBlock = blockSize / pageSize;
    pagesPerDisk = diskSize / pageSize;
    blocksPerDisk = diskSize / blockSize;

    DPRINTF(FlashDevice, "diskSize: %d Bytes; %d pages per block, %d pages "
            "per disk\n", diskSize, pagesPerBlock, pagesPerDisk);

    locationTable.resize(pagesPerDisk);

    blockValidEntries.resize(blocksPerDisk, 0);
    blockEmptyEntries.resize(blocksPerDisk, pagesPerBlock);

    unknownPages.resize((pagesPerDisk >> 5) + 1, 0xFFFFFFFF);

    for (uint32_t count = 0; count < pagesPerDisk; count++) {
        //setup lookup table + physical aspects

        if (dataDistribution == Enums::stripe) {
            locationTable[count].page = count / blocksPerDisk;
            locationTable[count].block = count % blocksPerDisk;

        } else {
            locationTable[count].page = count % pagesPerBlock;
            locationTable[count].block = count / pagesPerBlock;
        }
    }
}

FlashDevice::~FlashDevice()
{
    DPRINTF(FlashDevice, "Remove FlashDevice\n");
}

void
FlashDevice::accessDevice(uint64_t address, uint32_t amount, Callback *event,
                          Actions action)
{
    DPRINTF(FlashDevice, "Flash calculation for %d bytes in %d pages\n"
            , amount, pageSize);

    std::vector<Tick> time(numPlanes, 0);
    uint64_t logic_page_addr = address / pageSize;
    uint32_t plane_address = 0;

    for (uint32_t count = 0; amount > (count * pageSize); count++) {
        uint32_t index = (locationTable[logic_page_addr].block *
                          pagesPerBlock) + (logic_page_addr % pagesPerBlock);

        DPRINTF(FlashDevice, "Index 0x%8x, Block 0x%8x, pages/block %d,"
                " logic address 0x%8x\n", index,
                locationTable[logic_page_addr].block, pagesPerBlock,
                logic_page_addr);
        DPRINTF(FlashDevice, "Page %d; %d bytes up to this point\n", count,
                (count * pageSize));

        plane_address = locationTable[logic_page_addr].block & planeMask;

        if (action == ActionRead) {
            //lookup
            //call accessTimes
            time[plane_address] += accessTimes(locationTable[logic_page_addr]
                                               .block, ActionRead);

            /*stats*/
            stats.readAccess.sample(logic_page_addr);
            stats.readLatency.sample(time[plane_address]);
        } else { //write
            //lookup
            //call accessTimes if appropriate, page may be unknown, so lets
            //give it the benefit of the doubt

            if (getUnknownPages(index))
                time[plane_address] += accessTimes
                    (locationTable[logic_page_addr].block, ActionWrite);

            else //A remap is needed
                time[plane_address] += remap(logic_page_addr);

            /*stats*/
            stats.writeAccess.sample(logic_page_addr);
            stats.writeLatency.sample(time[plane_address]);
        }

        if (getUnknownPages(index)) {
            clearUnknownPages(index);
            --blockEmptyEntries[locationTable[logic_page_addr].block];
            ++blockValidEntries[locationTable[logic_page_addr].block];
        }

        stats.fileSystemAccess.sample(address);
        ++logic_page_addr;
    }

    for (uint32_t count = 0; count < numPlanes; count++){
        plane_address = (time[plane_address] > time[count]) ? plane_address
            : count;

        DPRINTF(FlashDevice, "Plane %d is busy for %d ticks\n", count,
                time[count]);

        if (time[count] != 0) {

            struct CallBackEntry cbe;
            if (planeEventQueue[count].empty())
                cbe.time = time[count] + curTick();
            else
                cbe.time = time[count] +
                           planeEventQueue[count].back().time;
            cbe.function = NULL;
            planeEventQueue[count].push_back(cbe);

            DPRINTF(FlashDevice, "scheduled at: %ld\n", cbe.time);

            if (!planeEvent.scheduled())
                schedule(planeEvent, planeEventQueue[count].back().time);
            else if (planeEventQueue[count].back().time < planeEvent.when())
                reschedule(planeEvent,
                    planeEventQueue[plane_address].back().time, true);
        }
    }

    //worst case two plane finish at the same time, each triggers an event
    //and this callback will be called once. Maybe before the other plane
    //could execute its event, but in the same tick.
    planeEventQueue[plane_address].back().function = event;
    DPRINTF(FlashDevice, "Callback queued for plane %d; %d in queue\n",
            plane_address, planeEventQueue[plane_address].size());
    DPRINTF(FlashDevice, "first event @ %d\n", planeEvent.when());
}

void
FlashDevice::actionComplete()
{
    DPRINTF(FlashDevice, "Plane action completed\n");
    uint8_t plane_address = 0;

    uint8_t next_event = 0;

    for (plane_address = 0; plane_address < numPlanes; plane_address++) {
        if (!planeEventQueue[plane_address].empty()) {
            assert(planeEventQueue[plane_address].front().time >= curTick());

            if (planeEventQueue[plane_address].front().time == curTick()) {
                Callback *temp = planeEventQueue[plane_address].front().
                                 function;
                planeEventQueue[plane_address].pop_front();

                if (temp != NULL) {
                    DPRINTF(FlashDevice, "Callback, %d\n", plane_address);
                    temp->process();
                }
            }
        }
    }

    for (plane_address = 0; plane_address < numPlanes; plane_address++) {
        if (!planeEventQueue[plane_address].empty())
            if (planeEventQueue[next_event].empty() ||
                    (planeEventQueue[plane_address].front().time <
                     planeEventQueue[next_event].front().time))
                next_event = plane_address;
    }

    if (!planeEventQueue[next_event].empty()) {
        DPRINTF(FlashDevice, "Schedule plane: %d\n", plane_address);
        reschedule(planeEvent, planeEventQueue[next_event].front().time, true);
    }

    checkDrain();

    DPRINTF(FlashDevice, "returing from flash event\n");
    DPRINTF(FlashDevice, "first event @ %d\n", planeEvent.when());
}

Tick
FlashDevice::remap(uint64_t logic_page_addr)
{
    if (blockEmptyEntries[locationTable[logic_page_addr].block] > 0) {
        //just a remap
        //update tables
        --blockEmptyEntries[locationTable[logic_page_addr].block];
        //access to this table won't be sequential anymore
        locationTable[logic_page_addr].page = pagesPerBlock + 2;
        //access new block
        Tick time = accessTimes(locationTable[logic_page_addr].block,
                                ActionWrite);

        DPRINTF(FlashDevice, "Remap returns %d ticks\n", time);
        return time;

    } else {
        //calculate how much time GC would have taken
        uint32_t block = locationTable[logic_page_addr].block;
        Tick time = ((GCActivePercentage *
                       (accessTimes(block, ActionCopy) +
                        accessTimes(block, ActionErase)))
                     / 100);

        //use block as the logical start address of the block
        block = locationTable[logic_page_addr].block * pagesPerBlock;

        //assumption: clean will improve locality
        for (uint32_t count = 0; count < pagesPerBlock; count++) {
            assert(block + count < pagesPerDisk);
            locationTable[block + count].page = (block + count) %
                pagesPerBlock;
        }

        blockEmptyEntries[locationTable[logic_page_addr].block] =
            pagesPerBlock;
        /*stats*/
        ++stats.totalGCActivations;

        DPRINTF(FlashDevice, "Remap with erase action returns %d ticks\n",
                time);

        return time;
    }

}

Tick
FlashDevice::accessTimes(uint64_t block, Actions action)
{
    Tick time = 0;

    switch(action) {
      case ActionRead: {
          time = readLatency;
      } break;

      case ActionWrite: {
          time = writeLatency + readLatency;
      } break;

      case ActionErase: {
          time = eraseLatency + readLatency;
      } break;

      case ActionCopy: {
          uint32_t validpages = blockValidEntries[block];
          time = validpages * (readLatency + writeLatency);
      } break;

      default: break;
    }

    //Used to determine sequential action.
    DPRINTF(FlashDevice, "Access returns %d ticks\n", time);
    return time;
}

inline
void
FlashDevice::clearUnknownPages(uint32_t index)
{
    unknownPages[index >> 5] &= ~(0x01 << (index % 32));
}

inline
bool
FlashDevice::getUnknownPages(uint32_t index)
{
    return unknownPages[index >> 5] & (0x01 << (index % 32));
}

void
FlashDevice::regStats()
{
    AbstractNVM::regStats();

    using namespace Stats;

    std::string fd_name = name() + ".FlashDevice";

    // Register the stats
    stats.totalGCActivations
        .name(fd_name + ".totalGCActivations")
        .desc("Number of Garbage collector activations")
        .flags(none);

    stats.writeAccess
        .init(2)
        .name(fd_name + ".writeAccessHist")
        .desc("Histogram of write addresses")
        .flags(pdf);
    stats.readAccess
        .init(2)
        .name(fd_name + ".readAccessHist")
        .desc("Histogram of read addresses")
        .flags(pdf);
    stats.fileSystemAccess
        .init(100)
        .name(fd_name + ".fileSystemAccessHist")
        .desc("Histogram of file system accesses")
        .flags(pdf);

    stats.writeLatency
        .init(100)
        .name(fd_name + ".writeLatencyHist")
        .desc("Histogram of write latency")
        .flags(pdf);
    stats.readLatency
        .init(100)
        .name(fd_name + ".readLatencyHist")
        .desc("Histogram of read latency")
        .flags(pdf);
}

void
FlashDevice::serialize(CheckpointOut &cp) const
{
    SERIALIZE_SCALAR(planeMask);

    SERIALIZE_CONTAINER(unknownPages);
    SERIALIZE_CONTAINER(blockValidEntries);
    SERIALIZE_CONTAINER(blockEmptyEntries);

    int location_table_size = locationTable.size();
    SERIALIZE_SCALAR(location_table_size);
    for (uint32_t count = 0; count < location_table_size; count++) {
        paramOut(cp, csprintf("locationTable[%d].page", count),
                 locationTable[count].page);
        paramOut(cp, csprintf("locationTable[%d].block", count),
                 locationTable[count].block);
    }
};

void
FlashDevice::unserialize(CheckpointIn &cp)
{
    UNSERIALIZE_SCALAR(planeMask);

    UNSERIALIZE_CONTAINER(unknownPages);
    UNSERIALIZE_CONTAINER(blockValidEntries);
    UNSERIALIZE_CONTAINER(blockEmptyEntries);

    int location_table_size;
    UNSERIALIZE_SCALAR(location_table_size);
    locationTable.resize(location_table_size);
    for (uint32_t count = 0; count < location_table_size; count++) {
        paramIn(cp, csprintf("locationTable[%d].page", count),
                locationTable[count].page);
        paramIn(cp, csprintf("locationTable[%d].block", count),
                locationTable[count].block);
    }
};

DrainState
FlashDevice::drain()
{
    if (planeEvent.scheduled()) {
        DPRINTF(Drain, "Flash device is draining...\n");
        return DrainState::Draining;
    } else {
        DPRINTF(Drain, "Flash device in drained state\n");
        return DrainState::Drained;
    }
}

void
FlashDevice::checkDrain()
{
    if (drainState() != DrainState::Draining)
        return;

    if (planeEvent.when() > curTick()) {
        DPRINTF(Drain, "Flash device is still draining\n");
    } else {
        DPRINTF(Drain, "Flash device is done draining\n");
        signalDrainDone();
    }
}