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 drainManager(NULL),
90 planeEventQueue(numPlanes),
91 planeEvent(this)
92{
93
94 /*
95 * Let 'a' be a power of two of n bits, written such that a-n is the msb
96 * and a-0 is the lsb. Since it is a power of two, only one bit (a-x,
97 * with 0 <= x <= n) is set. If we subtract one from this number the bits
98 * a-(x-1) to a-0 are set and all the other bits are cleared. Hence a
99 * bitwise AND with those two numbers results in an integer with all bits
100 * cleared.
101 */
102 if(numPlanes & planeMask)
103 fatal("Number of planes is not a power of 2 in flash device.\n");
104}
105
106/**
107 * Initiates all the flash functions: initializes the lookup tables, age of
108 * the device, etc. This can only be done once the disk image is known.
109 * Thats why it can't be done in the constructor.
110 */
111void
112FlashDevice::initializeFlash(uint64_t disk_size, uint32_t sector_size)
113{
114 diskSize = disk_size * sector_size;
115 pagesPerBlock = blockSize / pageSize;
116 pagesPerDisk = diskSize / pageSize;
117 blocksPerDisk = diskSize / blockSize;
118
119 /** Sanity information: check flash configuration */
120 DPRINTF(FlashDevice, "diskSize: %d Bytes; %d pages per block, %d pages "
121 "per disk\n", diskSize, pagesPerBlock, pagesPerDisk);
122
123 locationTable.resize(pagesPerDisk);
124
125 /**Garbage collection related*/
126 blockValidEntries.resize(blocksPerDisk, 0);
127 blockEmptyEntries.resize(blocksPerDisk, pagesPerBlock);
128
129 /**
130 * This is a bitmap. Every bit is a page
131 * unknownPages is a vector of 32 bit integers. If every page was an
132 * integer, the total size would be pagesPerDisk; since we can map one
133 * page per bit we need ceil(pagesPerDisk/32) entries. 32 = 1 << 5 hence
134 * it will do to just shift pagesPerDisk five positions and add one. This
135 * will allocate one integer to many for this data structure in the worst
136 * case.
137 */
138 unknownPages.resize((pagesPerDisk >> 5) + 1, 0xFFFFFFFF);
139
140 for (uint32_t count = 0; count < pagesPerDisk; count++) {
141 //setup lookup table + physical aspects
142
143 if (dataDistribution == Enums::stripe) {
144 locationTable[count].page = count / blocksPerDisk;
145 locationTable[count].block = count % blocksPerDisk;
146
147 } else {
148 locationTable[count].page = count % pagesPerBlock;
149 locationTable[count].block = count / pagesPerBlock;
150 }
151 }
152}
153
154FlashDevice::~FlashDevice()
155{
156 DPRINTF(FlashDevice, "Remove FlashDevice\n");
157}
158
159/**
160 * Handles the accesses to the device.
161 * The function determines when certain actions are scheduled and schedules
162 * an event that uses the callback function on completion of the action.
163 */
164void
165FlashDevice::accessDevice(uint64_t address, uint32_t amount, Callback *event,
166 Actions action)
167{
168 DPRINTF(FlashDevice, "Flash calculation for %d bytes in %d pages\n"
169 , amount, pageSize);
170
171 std::vector<Tick> time(numPlanes, 0);
172 uint64_t logic_page_addr = address / pageSize;
173 uint32_t plane_address = 0;
174
175 /**
176 * The access will be broken up in a number of page accesses. The number
177 * of page accesses depends on the amount that needs to be transfered.
178 * The assumption here is that the interface is completely ignorant of
179 * the page size and that this model has to figure out all of the
180 * transaction characteristics.
181 */
182 for (uint32_t count = 0; amount > (count * pageSize); count++) {
183 uint32_t index = (locationTable[logic_page_addr].block *
184 pagesPerBlock) + (logic_page_addr % pagesPerBlock);
185
186 DPRINTF(FlashDevice, "Index 0x%8x, Block 0x%8x, pages/block %d,"
187 " logic address 0x%8x\n", index,
188 locationTable[logic_page_addr].block, pagesPerBlock,
189 logic_page_addr);
190 DPRINTF(FlashDevice, "Page %d; %d bytes up to this point\n", count,
191 (count * pageSize));
192
193 plane_address = locationTable[logic_page_addr].block & planeMask;
194
195 if (action == ActionRead) {
196 //lookup
197 //call accessTimes
198 time[plane_address] += accessTimes(locationTable[logic_page_addr]
199 .block, ActionRead);
200
201 /*stats*/
202 stats.readAccess.sample(logic_page_addr);
203 stats.readLatency.sample(time[plane_address]);
204 } else { //write
205 //lookup
206 //call accessTimes if appropriate, page may be unknown, so lets
207 //give it the benefit of the doubt
208
209 if (getUnknownPages(index))
210 time[plane_address] += accessTimes
211 (locationTable[logic_page_addr].block, ActionWrite);
212
213 else //A remap is needed
214 time[plane_address] += remap(logic_page_addr);
215
216 /*stats*/
217 stats.writeAccess.sample(logic_page_addr);
218 stats.writeLatency.sample(time[plane_address]);
219 }
220
221 /**
222 * Check if the page is known and used. unknownPages is a bitmap of
223 * all the pages. It tracks wether we can be sure that the
224 * information of this page is taken into acount in the model (is it
225 * considered in blockValidEntries and blockEmptyEntries?). If it has
226 * been used in the past, then it is known.
227 */
228 if (getUnknownPages(index)) {
229 clearUnknownPages(index);
230 --blockEmptyEntries[locationTable[logic_page_addr].block];
231 ++blockValidEntries[locationTable[logic_page_addr].block];
232 }
233
234 stats.fileSystemAccess.sample(address);
235 ++logic_page_addr;
236 }
237
238 /**
239 * previous part of the function found the times spend in different
240 * planes, now lets find the maximum to know when to callback the disk
241 */
242 for (uint32_t count = 0; count < numPlanes; count++){
243 plane_address = (time[plane_address] > time[count]) ? plane_address
244 : count;
245
246 DPRINTF(FlashDevice, "Plane %d is busy for %d ticks\n", count,
247 time[count]);
248
249 if (time[count] != 0) {
250
251 struct CallBackEntry cbe;
252 /**
253 * If there are no events for this plane, then add the current
254 * time to the occupation time; otherwise, plan it after the
255 * last event. If by chance that event is handled in this tick,
256 * then we would still end up with the same result.
257 */
258 if (planeEventQueue[count].empty())
259 cbe.time = time[count] + curTick();
260 else
261 cbe.time = time[count] +
262 planeEventQueue[count].back().time;
263 cbe.function = NULL;
264 planeEventQueue[count].push_back(cbe);
265
266 DPRINTF(FlashDevice, "scheduled at: %ld\n", cbe.time);
267
268 if (!planeEvent.scheduled())
269 schedule(planeEvent, planeEventQueue[count].back().time);
270 else if (planeEventQueue[count].back().time < planeEvent.when())
271 reschedule(planeEvent,
272 planeEventQueue[plane_address].back().time, true);
273 }
274 }
275
276 //worst case two plane finish at the same time, each triggers an event
277 //and this callback will be called once. Maybe before the other plane
278 //could execute its event, but in the same tick.
279 planeEventQueue[plane_address].back().function = event;
280 DPRINTF(FlashDevice, "Callback queued for plane %d; %d in queue\n",
281 plane_address, planeEventQueue[plane_address].size());
282 DPRINTF(FlashDevice, "first event @ %d\n", planeEvent.when());
283}
284
285/**
286 * When a plane completes its action, this event is triggered. When a
287 * callback function was associated with that event, it will be called.
288 */
289
290void
291FlashDevice::actionComplete()
292{
293 DPRINTF(FlashDevice, "Plane action completed\n");
294 uint8_t plane_address = 0;
295
296 uint8_t next_event = 0;
297
298 /**Search for a callback that is supposed to happen in this Tick*/
299 for (plane_address = 0; plane_address < numPlanes; plane_address++) {
300 if (!planeEventQueue[plane_address].empty()) {
301 /**
302 * Invariant: All queued events are scheduled in the present
303 * or future.
304 */
305 assert(planeEventQueue[plane_address].front().time >= curTick());
306
307 if (planeEventQueue[plane_address].front().time == curTick()) {
308 /**
309 * To ensure that the follow-up action is executed correctly,
310 * the callback entry first need to be cleared before it can
311 * be called.
312 */
313 Callback *temp = planeEventQueue[plane_address].front().
314 function;
315 planeEventQueue[plane_address].pop_front();
316
317 /**Found a callback, lets make it happen*/
318 if (temp != NULL) {
319 DPRINTF(FlashDevice, "Callback, %d\n", plane_address);
320 temp->process();
321 }
322 }
323 }
324 }
325
326 /** Find when to schedule the planeEvent next */
327 for (plane_address = 0; plane_address < numPlanes; plane_address++) {
328 if (!planeEventQueue[plane_address].empty())
329 if (planeEventQueue[next_event].empty() ||
330 (planeEventQueue[plane_address].front().time <
331 planeEventQueue[next_event].front().time))
332 next_event = plane_address;
333 }
334
335 /**Schedule the next plane that will be ready (if any)*/
336 if (!planeEventQueue[next_event].empty()) {
337 DPRINTF(FlashDevice, "Schedule plane: %d\n", plane_address);
338 reschedule(planeEvent, planeEventQueue[next_event].front().time, true);
339 }
340
341 checkDrain();
342
343 DPRINTF(FlashDevice, "returing from flash event\n");
344 DPRINTF(FlashDevice, "first event @ %d\n", planeEvent.when());
345}
346
347/**
348 * Handles the remapping of the pages. It is a (I hope) sensible statistic
349 * approach. asumption: garbage collection happens when a clean is needed
350 * (may become stochastic function).
351 */
352Tick
353FlashDevice::remap(uint64_t logic_page_addr)
354{
355 /**
356 * Are there any empty left in this Block, or do we need to do an erase
357 */
358 if (blockEmptyEntries[locationTable[logic_page_addr].block] > 0) {
359 //just a remap
360 //update tables
361 --blockEmptyEntries[locationTable[logic_page_addr].block];
362 //access to this table won't be sequential anymore
363 locationTable[logic_page_addr].page = pagesPerBlock + 2;
364 //access new block
365 Tick time = accessTimes(locationTable[logic_page_addr].block,
366 ActionWrite);
367
368 DPRINTF(FlashDevice, "Remap returns %d ticks\n", time);
369 return time;
370
371 } else {
372 //calculate how much time GC would have taken
373 uint32_t block = locationTable[logic_page_addr].block;
374 Tick time = ((GCActivePercentage *
375 (accessTimes(block, ActionCopy) +
376 accessTimes(block, ActionErase)))
377 / 100);
378
379 //use block as the logical start address of the block
380 block = locationTable[logic_page_addr].block * pagesPerBlock;
381
382 //assumption: clean will improve locality
383 for (uint32_t count = 0; count < pageSize; count++) {
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
590unsigned int
591FlashDevice::drain(DrainManager *dm)
592{
593 unsigned int count = 0;
594
595 if (planeEvent.scheduled()) {
596 count = 1;
597 drainManager = dm;
598 } else {
599 DPRINTF(Drain, "Flash device in drained state\n");
600 }
601
602 if (count) {
603 DPRINTF(Drain, "Flash device is draining...\n");
| 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 drainManager(NULL),
90 planeEventQueue(numPlanes),
91 planeEvent(this)
92{
93
94 /*
95 * Let 'a' be a power of two of n bits, written such that a-n is the msb
96 * and a-0 is the lsb. Since it is a power of two, only one bit (a-x,
97 * with 0 <= x <= n) is set. If we subtract one from this number the bits
98 * a-(x-1) to a-0 are set and all the other bits are cleared. Hence a
99 * bitwise AND with those two numbers results in an integer with all bits
100 * cleared.
101 */
102 if(numPlanes & planeMask)
103 fatal("Number of planes is not a power of 2 in flash device.\n");
104}
105
106/**
107 * Initiates all the flash functions: initializes the lookup tables, age of
108 * the device, etc. This can only be done once the disk image is known.
109 * Thats why it can't be done in the constructor.
110 */
111void
112FlashDevice::initializeFlash(uint64_t disk_size, uint32_t sector_size)
113{
114 diskSize = disk_size * sector_size;
115 pagesPerBlock = blockSize / pageSize;
116 pagesPerDisk = diskSize / pageSize;
117 blocksPerDisk = diskSize / blockSize;
118
119 /** Sanity information: check flash configuration */
120 DPRINTF(FlashDevice, "diskSize: %d Bytes; %d pages per block, %d pages "
121 "per disk\n", diskSize, pagesPerBlock, pagesPerDisk);
122
123 locationTable.resize(pagesPerDisk);
124
125 /**Garbage collection related*/
126 blockValidEntries.resize(blocksPerDisk, 0);
127 blockEmptyEntries.resize(blocksPerDisk, pagesPerBlock);
128
129 /**
130 * This is a bitmap. Every bit is a page
131 * unknownPages is a vector of 32 bit integers. If every page was an
132 * integer, the total size would be pagesPerDisk; since we can map one
133 * page per bit we need ceil(pagesPerDisk/32) entries. 32 = 1 << 5 hence
134 * it will do to just shift pagesPerDisk five positions and add one. This
135 * will allocate one integer to many for this data structure in the worst
136 * case.
137 */
138 unknownPages.resize((pagesPerDisk >> 5) + 1, 0xFFFFFFFF);
139
140 for (uint32_t count = 0; count < pagesPerDisk; count++) {
141 //setup lookup table + physical aspects
142
143 if (dataDistribution == Enums::stripe) {
144 locationTable[count].page = count / blocksPerDisk;
145 locationTable[count].block = count % blocksPerDisk;
146
147 } else {
148 locationTable[count].page = count % pagesPerBlock;
149 locationTable[count].block = count / pagesPerBlock;
150 }
151 }
152}
153
154FlashDevice::~FlashDevice()
155{
156 DPRINTF(FlashDevice, "Remove FlashDevice\n");
157}
158
159/**
160 * Handles the accesses to the device.
161 * The function determines when certain actions are scheduled and schedules
162 * an event that uses the callback function on completion of the action.
163 */
164void
165FlashDevice::accessDevice(uint64_t address, uint32_t amount, Callback *event,
166 Actions action)
167{
168 DPRINTF(FlashDevice, "Flash calculation for %d bytes in %d pages\n"
169 , amount, pageSize);
170
171 std::vector<Tick> time(numPlanes, 0);
172 uint64_t logic_page_addr = address / pageSize;
173 uint32_t plane_address = 0;
174
175 /**
176 * The access will be broken up in a number of page accesses. The number
177 * of page accesses depends on the amount that needs to be transfered.
178 * The assumption here is that the interface is completely ignorant of
179 * the page size and that this model has to figure out all of the
180 * transaction characteristics.
181 */
182 for (uint32_t count = 0; amount > (count * pageSize); count++) {
183 uint32_t index = (locationTable[logic_page_addr].block *
184 pagesPerBlock) + (logic_page_addr % pagesPerBlock);
185
186 DPRINTF(FlashDevice, "Index 0x%8x, Block 0x%8x, pages/block %d,"
187 " logic address 0x%8x\n", index,
188 locationTable[logic_page_addr].block, pagesPerBlock,
189 logic_page_addr);
190 DPRINTF(FlashDevice, "Page %d; %d bytes up to this point\n", count,
191 (count * pageSize));
192
193 plane_address = locationTable[logic_page_addr].block & planeMask;
194
195 if (action == ActionRead) {
196 //lookup
197 //call accessTimes
198 time[plane_address] += accessTimes(locationTable[logic_page_addr]
199 .block, ActionRead);
200
201 /*stats*/
202 stats.readAccess.sample(logic_page_addr);
203 stats.readLatency.sample(time[plane_address]);
204 } else { //write
205 //lookup
206 //call accessTimes if appropriate, page may be unknown, so lets
207 //give it the benefit of the doubt
208
209 if (getUnknownPages(index))
210 time[plane_address] += accessTimes
211 (locationTable[logic_page_addr].block, ActionWrite);
212
213 else //A remap is needed
214 time[plane_address] += remap(logic_page_addr);
215
216 /*stats*/
217 stats.writeAccess.sample(logic_page_addr);
218 stats.writeLatency.sample(time[plane_address]);
219 }
220
221 /**
222 * Check if the page is known and used. unknownPages is a bitmap of
223 * all the pages. It tracks wether we can be sure that the
224 * information of this page is taken into acount in the model (is it
225 * considered in blockValidEntries and blockEmptyEntries?). If it has
226 * been used in the past, then it is known.
227 */
228 if (getUnknownPages(index)) {
229 clearUnknownPages(index);
230 --blockEmptyEntries[locationTable[logic_page_addr].block];
231 ++blockValidEntries[locationTable[logic_page_addr].block];
232 }
233
234 stats.fileSystemAccess.sample(address);
235 ++logic_page_addr;
236 }
237
238 /**
239 * previous part of the function found the times spend in different
240 * planes, now lets find the maximum to know when to callback the disk
241 */
242 for (uint32_t count = 0; count < numPlanes; count++){
243 plane_address = (time[plane_address] > time[count]) ? plane_address
244 : count;
245
246 DPRINTF(FlashDevice, "Plane %d is busy for %d ticks\n", count,
247 time[count]);
248
249 if (time[count] != 0) {
250
251 struct CallBackEntry cbe;
252 /**
253 * If there are no events for this plane, then add the current
254 * time to the occupation time; otherwise, plan it after the
255 * last event. If by chance that event is handled in this tick,
256 * then we would still end up with the same result.
257 */
258 if (planeEventQueue[count].empty())
259 cbe.time = time[count] + curTick();
260 else
261 cbe.time = time[count] +
262 planeEventQueue[count].back().time;
263 cbe.function = NULL;
264 planeEventQueue[count].push_back(cbe);
265
266 DPRINTF(FlashDevice, "scheduled at: %ld\n", cbe.time);
267
268 if (!planeEvent.scheduled())
269 schedule(planeEvent, planeEventQueue[count].back().time);
270 else if (planeEventQueue[count].back().time < planeEvent.when())
271 reschedule(planeEvent,
272 planeEventQueue[plane_address].back().time, true);
273 }
274 }
275
276 //worst case two plane finish at the same time, each triggers an event
277 //and this callback will be called once. Maybe before the other plane
278 //could execute its event, but in the same tick.
279 planeEventQueue[plane_address].back().function = event;
280 DPRINTF(FlashDevice, "Callback queued for plane %d; %d in queue\n",
281 plane_address, planeEventQueue[plane_address].size());
282 DPRINTF(FlashDevice, "first event @ %d\n", planeEvent.when());
283}
284
285/**
286 * When a plane completes its action, this event is triggered. When a
287 * callback function was associated with that event, it will be called.
288 */
289
290void
291FlashDevice::actionComplete()
292{
293 DPRINTF(FlashDevice, "Plane action completed\n");
294 uint8_t plane_address = 0;
295
296 uint8_t next_event = 0;
297
298 /**Search for a callback that is supposed to happen in this Tick*/
299 for (plane_address = 0; plane_address < numPlanes; plane_address++) {
300 if (!planeEventQueue[plane_address].empty()) {
301 /**
302 * Invariant: All queued events are scheduled in the present
303 * or future.
304 */
305 assert(planeEventQueue[plane_address].front().time >= curTick());
306
307 if (planeEventQueue[plane_address].front().time == curTick()) {
308 /**
309 * To ensure that the follow-up action is executed correctly,
310 * the callback entry first need to be cleared before it can
311 * be called.
312 */
313 Callback *temp = planeEventQueue[plane_address].front().
314 function;
315 planeEventQueue[plane_address].pop_front();
316
317 /**Found a callback, lets make it happen*/
318 if (temp != NULL) {
319 DPRINTF(FlashDevice, "Callback, %d\n", plane_address);
320 temp->process();
321 }
322 }
323 }
324 }
325
326 /** Find when to schedule the planeEvent next */
327 for (plane_address = 0; plane_address < numPlanes; plane_address++) {
328 if (!planeEventQueue[plane_address].empty())
329 if (planeEventQueue[next_event].empty() ||
330 (planeEventQueue[plane_address].front().time <
331 planeEventQueue[next_event].front().time))
332 next_event = plane_address;
333 }
334
335 /**Schedule the next plane that will be ready (if any)*/
336 if (!planeEventQueue[next_event].empty()) {
337 DPRINTF(FlashDevice, "Schedule plane: %d\n", plane_address);
338 reschedule(planeEvent, planeEventQueue[next_event].front().time, true);
339 }
340
341 checkDrain();
342
343 DPRINTF(FlashDevice, "returing from flash event\n");
344 DPRINTF(FlashDevice, "first event @ %d\n", planeEvent.when());
345}
346
347/**
348 * Handles the remapping of the pages. It is a (I hope) sensible statistic
349 * approach. asumption: garbage collection happens when a clean is needed
350 * (may become stochastic function).
351 */
352Tick
353FlashDevice::remap(uint64_t logic_page_addr)
354{
355 /**
356 * Are there any empty left in this Block, or do we need to do an erase
357 */
358 if (blockEmptyEntries[locationTable[logic_page_addr].block] > 0) {
359 //just a remap
360 //update tables
361 --blockEmptyEntries[locationTable[logic_page_addr].block];
362 //access to this table won't be sequential anymore
363 locationTable[logic_page_addr].page = pagesPerBlock + 2;
364 //access new block
365 Tick time = accessTimes(locationTable[logic_page_addr].block,
366 ActionWrite);
367
368 DPRINTF(FlashDevice, "Remap returns %d ticks\n", time);
369 return time;
370
371 } else {
372 //calculate how much time GC would have taken
373 uint32_t block = locationTable[logic_page_addr].block;
374 Tick time = ((GCActivePercentage *
375 (accessTimes(block, ActionCopy) +
376 accessTimes(block, ActionErase)))
377 / 100);
378
379 //use block as the logical start address of the block
380 block = locationTable[logic_page_addr].block * pagesPerBlock;
381
382 //assumption: clean will improve locality
383 for (uint32_t count = 0; count < pageSize; count++) {
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
590unsigned int
591FlashDevice::drain(DrainManager *dm)
592{
593 unsigned int count = 0;
594
595 if (planeEvent.scheduled()) {
596 count = 1;
597 drainManager = dm;
598 } else {
599 DPRINTF(Drain, "Flash device in drained state\n");
600 }
601
602 if (count) {
603 DPRINTF(Drain, "Flash device is draining...\n");
|