2 * Copyright (c) 2013-2015 ARM Limited
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.
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.
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.
37 * Authors: Rene de Jong
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
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.
52 * IMPORTANT: number of planes should be a power of 2.
55 #include "dev/arm/flash_device.hh"
57 #include "debug/Drain.hh"
64 FlashDeviceParams::create()
66 return new FlashDevice(this);
71 * Flash Device constructor and destructor
74 FlashDevice::FlashDevice(const FlashDeviceParams
* p
):
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
),
88 planeMask(numPlanes
- 1),
89 planeEventQueue(numPlanes
),
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
101 if (numPlanes
& planeMask
)
102 fatal("Number of planes is not a power of 2 in flash device.\n");
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.
111 FlashDevice::initializeFlash(uint64_t disk_size
, uint32_t sector_size
)
113 diskSize
= disk_size
* sector_size
;
114 pagesPerBlock
= blockSize
/ pageSize
;
115 pagesPerDisk
= diskSize
/ pageSize
;
116 blocksPerDisk
= diskSize
/ blockSize
;
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
);
122 locationTable
.resize(pagesPerDisk
);
124 /**Garbage collection related*/
125 blockValidEntries
.resize(blocksPerDisk
, 0);
126 blockEmptyEntries
.resize(blocksPerDisk
, pagesPerBlock
);
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
137 unknownPages
.resize((pagesPerDisk
>> 5) + 1, 0xFFFFFFFF);
139 for (uint32_t count
= 0; count
< pagesPerDisk
; count
++) {
140 //setup lookup table + physical aspects
142 if (dataDistribution
== Enums::stripe
) {
143 locationTable
[count
].page
= count
/ blocksPerDisk
;
144 locationTable
[count
].block
= count
% blocksPerDisk
;
147 locationTable
[count
].page
= count
% pagesPerBlock
;
148 locationTable
[count
].block
= count
/ pagesPerBlock
;
153 FlashDevice::~FlashDevice()
155 DPRINTF(FlashDevice
, "Remove FlashDevice\n");
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.
164 FlashDevice::accessDevice(uint64_t address
, uint32_t amount
, Callback
*event
,
167 DPRINTF(FlashDevice
, "Flash calculation for %d bytes in %d pages\n"
170 std::vector
<Tick
> time(numPlanes
, 0);
171 uint64_t logic_page_addr
= address
/ pageSize
;
172 uint32_t plane_address
= 0;
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.
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
);
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
,
189 DPRINTF(FlashDevice
, "Page %d; %d bytes up to this point\n", count
,
192 plane_address
= locationTable
[logic_page_addr
].block
& planeMask
;
194 if (action
== ActionRead
) {
197 time
[plane_address
] += accessTimes(locationTable
[logic_page_addr
]
201 stats
.readAccess
.sample(logic_page_addr
);
202 stats
.readLatency
.sample(time
[plane_address
]);
205 //call accessTimes if appropriate, page may be unknown, so lets
206 //give it the benefit of the doubt
208 if (getUnknownPages(index
))
209 time
[plane_address
] += accessTimes
210 (locationTable
[logic_page_addr
].block
, ActionWrite
);
212 else //A remap is needed
213 time
[plane_address
] += remap(logic_page_addr
);
216 stats
.writeAccess
.sample(logic_page_addr
);
217 stats
.writeLatency
.sample(time
[plane_address
]);
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.
227 if (getUnknownPages(index
)) {
228 clearUnknownPages(index
);
229 --blockEmptyEntries
[locationTable
[logic_page_addr
].block
];
230 ++blockValidEntries
[locationTable
[logic_page_addr
].block
];
233 stats
.fileSystemAccess
.sample(address
);
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
241 for (uint32_t count
= 0; count
< numPlanes
; count
++){
242 plane_address
= (time
[plane_address
] > time
[count
]) ? plane_address
245 DPRINTF(FlashDevice
, "Plane %d is busy for %d ticks\n", count
,
248 if (time
[count
] != 0) {
250 struct CallBackEntry cbe
;
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.
257 if (planeEventQueue
[count
].empty())
258 cbe
.time
= time
[count
] + curTick();
260 cbe
.time
= time
[count
] +
261 planeEventQueue
[count
].back().time
;
263 planeEventQueue
[count
].push_back(cbe
);
265 DPRINTF(FlashDevice
, "scheduled at: %ld\n", cbe
.time
);
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);
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());
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.
290 FlashDevice::actionComplete()
292 DPRINTF(FlashDevice
, "Plane action completed\n");
293 uint8_t plane_address
= 0;
295 uint8_t next_event
= 0;
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()) {
301 * Invariant: All queued events are scheduled in the present
304 assert(planeEventQueue
[plane_address
].front().time
>= curTick());
306 if (planeEventQueue
[plane_address
].front().time
== curTick()) {
308 * To ensure that the follow-up action is executed correctly,
309 * the callback entry first need to be cleared before it can
312 Callback
*temp
= planeEventQueue
[plane_address
].front().
314 planeEventQueue
[plane_address
].pop_front();
316 /**Found a callback, lets make it happen*/
318 DPRINTF(FlashDevice
, "Callback, %d\n", plane_address
);
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
;
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);
342 DPRINTF(FlashDevice
, "returing from flash event\n");
343 DPRINTF(FlashDevice
, "first event @ %d\n", planeEvent
.when());
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).
352 FlashDevice::remap(uint64_t logic_page_addr
)
355 * Are there any empty left in this Block, or do we need to do an erase
357 if (blockEmptyEntries
[locationTable
[logic_page_addr
].block
] > 0) {
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;
364 Tick time
= accessTimes(locationTable
[logic_page_addr
].block
,
367 DPRINTF(FlashDevice
, "Remap returns %d ticks\n", time
);
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
)))
378 //use block as the logical start address of the block
379 block
= locationTable
[logic_page_addr
].block
* pagesPerBlock
;
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
) %
389 blockEmptyEntries
[locationTable
[logic_page_addr
].block
] =
392 ++stats
.totalGCActivations
;
394 DPRINTF(FlashDevice
, "Remap with erase action returns %d ticks\n",
403 * Calculates the accesstime per operation needed
406 FlashDevice::accessTimes(uint64_t block
, Actions action
)
412 /**Just read the page*/
417 /**Write the page, and read the result*/
418 time
= writeLatency
+ readLatency
;
422 /**Erase and check wether it was successfull*/
423 time
= eraseLatency
+ readLatency
;
427 /**Copy every valid page*/
428 uint32_t validpages
= blockValidEntries
[block
];
429 time
= validpages
* (readLatency
+ writeLatency
);
435 //Used to determine sequential action.
436 DPRINTF(FlashDevice
, "Access returns %d ticks\n", time
);
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
456 FlashDevice::clearUnknownPages(uint32_t index
)
458 unknownPages
[index
>> 5] &= ~(0x01 << (index
% 32));
462 * getUnknownPages. Verify wether a page is known
467 FlashDevice::getUnknownPages(uint32_t index
)
469 return unknownPages
[index
>> 5] & (0x01 << (index
% 32));
473 FlashDevice::regStats()
475 AbstractNVM::regStats();
477 using namespace Stats
;
479 std::string fd_name
= name() + ".FlashDevice";
481 // Register the stats
482 /** Amount of GC activations*/
483 stats
.totalGCActivations
484 .name(fd_name
+ ".totalGCActivations")
485 .desc("Number of Garbage collector activations")
488 /** Histogram of address accesses*/
491 .name(fd_name
+ ".writeAccessHist")
492 .desc("Histogram of write addresses")
496 .name(fd_name
+ ".readAccessHist")
497 .desc("Histogram of read addresses")
499 stats
.fileSystemAccess
501 .name(fd_name
+ ".fileSystemAccessHist")
502 .desc("Histogram of file system accesses")
505 /** Histogram of access latencies*/
508 .name(fd_name
+ ".writeLatencyHist")
509 .desc("Histogram of write latency")
513 .name(fd_name
+ ".readLatencyHist")
514 .desc("Histogram of read latency")
519 * Serialize; needed to create checkpoints
523 FlashDevice::serialize(CheckpointOut
&cp
) const
525 SERIALIZE_SCALAR(planeMask
);
527 SERIALIZE_CONTAINER(unknownPages
);
528 SERIALIZE_CONTAINER(blockValidEntries
);
529 SERIALIZE_CONTAINER(blockEmptyEntries
);
531 int location_table_size
= locationTable
.size();
532 SERIALIZE_SCALAR(location_table_size
);
533 for (uint32_t count
= 0; count
< location_table_size
; count
++) {
534 paramOut(cp
, csprintf("locationTable[%d].page", count
),
535 locationTable
[count
].page
);
536 paramOut(cp
, csprintf("locationTable[%d].block", count
),
537 locationTable
[count
].block
);
542 * Unserialize; needed to restore from checkpoints
546 FlashDevice::unserialize(CheckpointIn
&cp
)
548 UNSERIALIZE_SCALAR(planeMask
);
550 UNSERIALIZE_CONTAINER(unknownPages
);
551 UNSERIALIZE_CONTAINER(blockValidEntries
);
552 UNSERIALIZE_CONTAINER(blockEmptyEntries
);
554 int location_table_size
;
555 UNSERIALIZE_SCALAR(location_table_size
);
556 locationTable
.resize(location_table_size
);
557 for (uint32_t count
= 0; count
< location_table_size
; count
++) {
558 paramIn(cp
, csprintf("locationTable[%d].page", count
),
559 locationTable
[count
].page
);
560 paramIn(cp
, csprintf("locationTable[%d].block", count
),
561 locationTable
[count
].block
);
566 * Drain; needed to enable checkpoints
572 if (planeEvent
.scheduled()) {
573 DPRINTF(Drain
, "Flash device is draining...\n");
574 return DrainState::Draining
;
576 DPRINTF(Drain
, "Flash device in drained state\n");
577 return DrainState::Drained
;
582 * Checkdrain; needed to enable checkpoints
586 FlashDevice::checkDrain()
588 if (drainState() != DrainState::Draining
)
591 if (planeEvent
.when() > curTick()) {
592 DPRINTF(Drain
, "Flash device is still draining\n");
594 DPRINTF(Drain
, "Flash device is done draining\n");