8e337cd86d478b7362a5e49afd25d8bcd17bbedf
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
< pageSize
; count
++) {
383 locationTable
[block
+ count
].page
= (block
+ count
) %
388 blockEmptyEntries
[locationTable
[logic_page_addr
].block
] =
391 ++stats
.totalGCActivations
;
393 DPRINTF(FlashDevice
, "Remap with erase action returns %d ticks\n",
402 * Calculates the accesstime per operation needed
405 FlashDevice::accessTimes(uint64_t block
, Actions action
)
411 /**Just read the page*/
416 /**Write the page, and read the result*/
417 time
= writeLatency
+ readLatency
;
421 /**Erase and check wether it was successfull*/
422 time
= eraseLatency
+ readLatency
;
426 /**Copy every valid page*/
427 uint32_t validpages
= blockValidEntries
[block
];
428 time
= validpages
* (readLatency
+ writeLatency
);
434 //Used to determine sequential action.
435 DPRINTF(FlashDevice
, "Access returns %d ticks\n", time
);
440 * clearUnknownPages. defines that a page is known and used
441 * unknownPages is a bitmap of all the pages. It tracks wether we can be sure
442 * that the information of this page is taken into acount in the model (is it
443 * considered in blockValidEntries and blockEmptyEntries?). If it has been
444 * used in the past, then it is known. But it needs to be tracked to make
445 * decisions about write accesses, and indirectly about copy actions. one
446 * unknownPage entry is a 32 bit integer. So if we have a page index, then
447 * that means that we need entry floor(index/32) (index >> 5) and we need to
448 * select the bit which number is equal to the remainder of index/32
449 * (index%32). The bit is cleared to make sure that we see it as considered
455 FlashDevice::clearUnknownPages(uint32_t index
)
457 unknownPages
[index
>> 5] &= ~(0x01 << (index
% 32));
461 * getUnknownPages. Verify wether a page is known
466 FlashDevice::getUnknownPages(uint32_t index
)
468 return unknownPages
[index
>> 5] & (0x01 << (index
% 32));
472 FlashDevice::regStats()
474 using namespace Stats
;
476 std::string fd_name
= name() + ".FlashDevice";
478 // Register the stats
479 /** Amount of GC activations*/
480 stats
.totalGCActivations
481 .name(fd_name
+ ".totalGCActivations")
482 .desc("Number of Garbage collector activations")
485 /** Histogram of address accesses*/
488 .name(fd_name
+ ".writeAccessHist")
489 .desc("Histogram of write addresses")
493 .name(fd_name
+ ".readAccessHist")
494 .desc("Histogram of read addresses")
496 stats
.fileSystemAccess
498 .name(fd_name
+ ".fileSystemAccessHist")
499 .desc("Histogram of file system accesses")
502 /** Histogram of access latencies*/
505 .name(fd_name
+ ".writeLatencyHist")
506 .desc("Histogram of write latency")
510 .name(fd_name
+ ".readLatencyHist")
511 .desc("Histogram of read latency")
516 * Serialize; needed to create checkpoints
520 FlashDevice::serialize(CheckpointOut
&cp
) const
522 SERIALIZE_SCALAR(planeMask
);
524 int unknown_pages_size
= unknownPages
.size();
525 SERIALIZE_SCALAR(unknown_pages_size
);
526 for (uint32_t count
= 0; count
< unknownPages
.size(); count
++)
527 SERIALIZE_SCALAR(unknownPages
[count
]);
529 int location_table_size
= locationTable
.size();
530 SERIALIZE_SCALAR(location_table_size
);
531 for (uint32_t count
= 0; count
< location_table_size
; count
++) {
532 SERIALIZE_SCALAR(locationTable
[count
].page
);
533 SERIALIZE_SCALAR(locationTable
[count
].block
);
536 int block_valid_entries_size
= blockValidEntries
.size();
537 SERIALIZE_SCALAR(block_valid_entries_size
);
538 for (uint32_t count
= 0; count
< blockValidEntries
.size(); count
++)
539 SERIALIZE_SCALAR(blockValidEntries
[count
]);
541 int block_empty_entries_size
= blockEmptyEntries
.size();
542 SERIALIZE_SCALAR(block_empty_entries_size
);
543 for (uint32_t count
= 0; count
< blockEmptyEntries
.size(); count
++)
544 SERIALIZE_SCALAR(blockEmptyEntries
[count
]);
549 * Unserialize; needed to restore from checkpoints
553 FlashDevice::unserialize(CheckpointIn
&cp
)
555 UNSERIALIZE_SCALAR(planeMask
);
557 int unknown_pages_size
;
558 UNSERIALIZE_SCALAR(unknown_pages_size
);
559 unknownPages
.resize(unknown_pages_size
);
560 for (uint32_t count
= 0; count
< unknown_pages_size
; count
++)
561 UNSERIALIZE_SCALAR(unknownPages
[count
]);
563 int location_table_size
;
564 UNSERIALIZE_SCALAR(location_table_size
);
565 locationTable
.resize(location_table_size
);
566 for (uint32_t count
= 0; count
< location_table_size
; count
++) {
567 UNSERIALIZE_SCALAR(locationTable
[count
].page
);
568 UNSERIALIZE_SCALAR(locationTable
[count
].block
);
571 int block_valid_entries_size
;
572 UNSERIALIZE_SCALAR(block_valid_entries_size
);
573 blockValidEntries
.resize(block_valid_entries_size
);
574 for (uint32_t count
= 0; count
< block_valid_entries_size
; count
++)
575 UNSERIALIZE_SCALAR(blockValidEntries
[count
]);
577 int block_empty_entries_size
;
578 UNSERIALIZE_SCALAR(block_empty_entries_size
);
579 blockEmptyEntries
.resize(block_empty_entries_size
);
580 for (uint32_t count
= 0; count
< block_empty_entries_size
; count
++)
581 UNSERIALIZE_SCALAR(blockEmptyEntries
[count
]);
586 * Drain; needed to enable checkpoints
592 if (planeEvent
.scheduled()) {
593 DPRINTF(Drain
, "Flash device is draining...\n");
594 return DrainState::Draining
;
596 DPRINTF(Drain
, "Flash device in drained state\n");
597 return DrainState::Drained
;
602 * Checkdrain; needed to enable checkpoints
606 FlashDevice::checkDrain()
608 if (drainState() != DrainState::Draining
)
611 if (planeEvent
.when() > curTick()) {
612 DPRINTF(Drain
, "Flash device is still draining\n");
614 DPRINTF(Drain
, "Flash device is done draining\n");