#! /usr/bin/env python from __future__ import print_function from collections import * from optparse import OptionParser import random import string class ssd: def __init__(self, ssd_type, num_logical_pages, num_blocks, pages_per_block, block_erase_time, page_program_time, page_read_time, high_water_mark, low_water_mark, trace_gc, show_state): # type self.TYPE_DIRECT = 1 self.TYPE_LOGGING = 2 self.TYPE_IDEAL = 3 if ssd_type == 'direct': self.ssd_type = self.TYPE_DIRECT elif ssd_type == 'log': self.ssd_type = self.TYPE_LOGGING elif ssd_type == 'ideal': self.ssd_type = self.TYPE_IDEAL else: print('bad SSD type (%s)' % ssd_type) exit(1) # size self.num_logical_pages = num_logical_pages self.num_blocks = num_blocks self.pages_per_block = pages_per_block # parameters self.block_erase_time = block_erase_time self.page_program_time = page_program_time self.page_read_time = page_read_time # init each page of each block to INVALID self.STATE_INVALID = 1 self.STATE_ERASED = 2 self.STATE_VALID = 3 self.num_pages = self.num_blocks * self.pages_per_block self.state = {} for i in range(self.num_pages): self.state[i] = self.STATE_INVALID # data itself self.data = {} for i in range(self.num_pages): self.data[i] = ' ' # LOGGING stuff # reverse map: for each physical page, what LOGICAL page refers to it? # which page to write to right now? self.current_page = -1 self.current_block = 0 # gc counts self.gc_count = 0 self.gc_current_block = 0 self.gc_high_water_mark = high_water_mark self.gc_low_water_mark = low_water_mark self.gc_trace = trace_gc self.show_state = show_state # can use this as a log block self.gc_used_blocks = {} for i in range(self.num_blocks): self.gc_used_blocks[i] = 0 # counts so as to help the GC self.live_count = {} for i in range(self.num_blocks): self.live_count[i] = 0 # FTL self.forward_map = {} for i in range(self.num_logical_pages): self.forward_map[i] = -1 self.reverse_map = {} for i in range(self.num_pages): self.reverse_map[i] = -1 # stats self.physical_erase_count = {} self.physical_read_count = {} self.physical_write_count = {} for i in range(self.num_blocks): self.physical_erase_count[i] = 0 self.physical_read_count[i] = 0 self.physical_write_count[i] = 0 self.physical_erase_sum = 0 self.physical_write_sum = 0 self.physical_read_sum = 0 self.logical_trim_sum = 0 self.logical_write_sum = 0 self.logical_read_sum = 0 self.logical_trim_fail_sum = 0 self.logical_write_fail_sum = 0 self.logical_read_fail_sum = 0 return def blocks_in_use(self): used = 0 for i in range(self.num_blocks): used += self.gc_used_blocks[i] return used def physical_erase(self, block_address): page_begin = block_address * self.pages_per_block page_end = page_begin + self.pages_per_block - 1 for page in range(page_begin, page_end + 1): self.data[page] = ' ' self.state[page] = self.STATE_ERASED # now, definitely NOT in use self.gc_used_blocks[block_address] = 0 # STATS self.physical_erase_count[block_address] += 1 self.physical_erase_sum += 1 return def physical_program(self, page_address, data): self.data[page_address] = data self.state[page_address] = self.STATE_VALID # STATS self.physical_write_count[page_address / self.pages_per_block] += 1 self.physical_write_sum += 1 return def physical_read(self, page_address): # STATS self.physical_read_count[page_address / self.pages_per_block] += 1 self.physical_read_sum += 1 return self.data[page_address] def read_direct(self, address): return self.physical_read(address) def write_direct(self, page_address, data): block_address = page_address / self.pages_per_block page_begin = block_address * self.pages_per_block page_end = page_begin + self.pages_per_block - 1 old_list = [] for old_page in range(page_begin, page_end + 1): if self.state[old_page] == self.STATE_VALID: old_data = self.physical_read(old_page) old_list.append((old_page, old_data)) self.physical_erase(block_address) for (old_page, old_data) in old_list: if old_page == page_address: continue self.physical_program(old_page, old_data) self.physical_program(page_address, data) self.forward_map[page_address] = page_address self.reverse_map[page_address] = page_address return 'success' def write_ideal(self, page_address, data): self.physical_program(page_address, data) self.forward_map[page_address] = page_address self.reverse_map[page_address] = page_address return 'success' def is_block_free(self, block): first_page = block * self.pages_per_block if self.state[first_page] == self.STATE_INVALID or self.state[first_page] == self.STATE_ERASED: if self.state[first_page] == self.STATE_INVALID: self.physical_erase(block) self.current_block = block self.current_page = first_page self.gc_used_blocks[block] = 1 return True return False def get_cursor(self): if self.current_page == -1: for block in range(self.current_block, self.num_blocks) + range(0, self.current_block): if self.is_block_free(block): return 0 return -1 return 0 def update_cursor(self): self.current_page += 1 if self.current_page % self.pages_per_block == 0: self.current_page = -1 return def write_logging(self, page_address, data, is_gc_write=False): if self.get_cursor() == -1: self.logical_write_fail_sum += 1 return 'failure: device full' # NORMAL MODE writing assert(self.state[self.current_page] == self.STATE_ERASED) self.physical_program(self.current_page, data) self.forward_map[page_address] = self.current_page self.reverse_map[self.current_page] = page_address self.update_cursor() return 'success' def garbage_collect(self): blocks_cleaned = 0 for block in range(self.gc_current_block, self.num_blocks) + range(0, self.gc_current_block): # don't GC the block currently being written to if block == self.current_block: continue # page to start looking for live blocks page_start = block * self.pages_per_block # is this page (and hence block) already erased? then don't bother if self.state[page_start] == self.STATE_ERASED: continue # collect list of live physical pages in this block live_pages = [] for page in range(page_start, page_start + self.pages_per_block): logical_page = self.reverse_map[page] if logical_page != -1 and self.forward_map[logical_page] == page: live_pages.append(page) # if ONLY live blocks, don't clean it! (why bother with move?) if len(live_pages) == self.pages_per_block: continue # live pages should be copied to current writing location for page in live_pages: # live: so copy it someplace new if self.gc_trace: print('gc %d:: read(physical_page=%d)' % (self.gc_count, page)) print('gc %d:: write()' % self.gc_count) data = self.physical_read(page) self.write(self.reverse_map[page], data) # finally, erase the block and see if we're done blocks_cleaned += 1 self.physical_erase(block) if self.gc_trace: print('gc %d:: erase(block=%d)' % (self.gc_count, block)) if self.show_state: print('') self.dump() print('') if self.blocks_in_use() <= self.gc_low_water_mark: # done! record where we stopped and return self.gc_current_block = block self.gc_count += 1 return # END: block iteration return def upkeep(self): # GARBAGE COLLECTION if self.blocks_in_use() >= self.gc_high_water_mark: self.garbage_collect() # WEAR LEVELING: for future return def trim(self, address): self.logical_trim_sum += 1 if address < 0 or address >= self.num_logical_pages: self.logical_trim_fail_sum += 1 return 'fail: illegal trim address' if self.forward_map[address] == -1: self.logical_trim_fail_sum += 1 return 'fail: uninitialized trim' self.forward_map[address] = -1 return 'success' def read(self, address): self.logical_read_sum += 1 if address < 0 or address >= self.num_logical_pages: self.logical_read_fail_sum += 1 return 'fail: illegal read address' if self.forward_map[address] == -1: self.logical_read_fail_sum += 1 return 'fail: uninitialized read' # USED for DIRECT and LOGGING and IDEAL return self.read_direct(self.forward_map[address]) def write(self, address, data): self.logical_write_sum += 1 if address < 0 or address >= self.num_logical_pages: self.logical_write_fail_sum += 1 return 'fail: illegal write address' if self.ssd_type == self.TYPE_DIRECT: return self.write_direct(address, data) elif self.ssd_type == self.TYPE_IDEAL: return self.write_ideal(address, data) else: return self.write_logging(address, data) def printable_state(self, s): if s == self.STATE_INVALID: return 'i' elif s == self.STATE_ERASED: return 'E' elif s == self.STATE_VALID: return 'v' else: print('bad state %d' % s) exit(1) def stats(self): print('Physical Operations Per Block') print('Erases ', end='') for i in range(self.num_blocks): print('%3d ' % self.physical_erase_count[i], end='') print(' Sum: %d' % self.physical_erase_sum) print('Writes ', end='') for i in range(self.num_blocks): print('%3d ' % self.physical_write_count[i], end='') print(' Sum: %d' % self.physical_write_sum) print('Reads ', end='') for i in range(self.num_blocks): print('%3d ' % self.physical_read_count[i], end='') print(' Sum: %d' % self.physical_read_sum) print('') print('Logical Operation Sums') print(' Write count %d (%d failed)' % (self.logical_write_sum, self.logical_write_fail_sum)) print(' Read count %d (%d failed)' % (self.logical_read_sum, self.logical_read_fail_sum)) print(' Trim count %d (%d failed)' % (self.logical_trim_sum, self.logical_trim_fail_sum)) print('') print('Times') print(' Erase time %.2f' % (self.physical_erase_sum * self.block_erase_time)) print(' Write time %.2f' % (self.physical_write_sum * self.page_program_time)) print(' Read time %.2f' % (self.physical_read_sum * self.page_read_time)) total_time = self.physical_erase_sum * self.block_erase_time + self.physical_write_sum * self.page_program_time + self.physical_read_sum * self.page_read_time print(' Total time %.2f' % total_time) return def dump(self): # FTL print('FTL ', end='') count = 0 ftl_columns = (self.pages_per_block * self.num_blocks) / 7 for i in range(self.num_logical_pages): if self.forward_map[i] == -1: continue count += 1 print('%3d:%3d ' % (i, self.forward_map[i]), end='') if count > 0 and count % ftl_columns == 0: print('\n ', end='') if count == 0: print('(empty)', end='') print('') # FLASH? print('Block ', end='') for i in range(self.num_blocks): out_str = '%d' % i print(out_str + ' ' * (self.pages_per_block - len(out_str) + 1), end='') print('') max_len = len(str(self.num_pages)) for n in range(max_len, 0, -1): if n == max_len: print('Page ', end='') else: print(' ', end='') for i in range(self.num_pages): out_str = str(i).zfill(max_len)[max_len - n] print(out_str, end='') if i > 0 and (i+1) % 10 == 0: print(end=' ') print('') print('State ', end='') for i in range(self.num_pages): print('%s' % self.printable_state(self.state[i]), end='') if i > 0 and (i+1) % 10 == 0: print(end=' ') print('') # DATA print('Data ', end='') for i in range(self.num_pages): if self.state[i] == self.STATE_VALID: print('%s' % self.data[i], end='') else: print(' ', end='') if i > 0 and (i+1) % 10 == 0: print(end=' ') print('') # LIVE print('Live ', end='') for i in range(self.num_pages): if self.state[i] == self.STATE_VALID and self.forward_map[self.reverse_map[i]] == i: print('+', end='') else: print(' ', end='') if i > 0 and (i+1) % 10 == 0: print(end=' ') print('') return # # MAIN PROGRAM # parser = OptionParser() parser.add_option('-s', '--seed', default=0, help='the random seed', action='store', type='int', dest='seed') parser.add_option('-n', '--num_cmds', default=10, help='number of commands to randomly generate', action='store', type='int', dest='num_cmds') parser.add_option('-P', '--op_percentages', default='40/50/10', help='if rand, percent of reads/writes/trims', action='store', type='string', dest='op_percentages') parser.add_option('-K', '--skew', default='', help='if non-empty, skew, e.g., 80/20: 80% of ops to 20% of blocks', action='store', type='string', dest='skew') parser.add_option('-k', '--skew_start', default=0, help='if --skew, skew after this many writes', action='store', type='int', dest='skew_start') parser.add_option('-r', '--read_fails', default=0, help='if rand, percent of reads that can fail', action='store', type='int', dest='read_fail') parser.add_option('-L', '--cmd_list', default='', help='comma-separated list of commands (e.g., r10,w20:a)', action='store', type='string', dest='cmd_list') parser.add_option('-T', '--ssd_type', default='direct', help='SSD type: ideal, direct, log', action='store', type='string', dest='ssd_type') parser.add_option('-l', '--logical_pages', default=80, help='number of logical pages in interface', action='store', type='int', dest='num_logical_pages') parser.add_option('-B', '--num_blocks', default=12, help='number of physical blocks in SSD', action='store', type='int', dest='num_blocks') parser.add_option('-p', '--pages_per_block', default=10, help='pages per physical block', action='store', type='int', dest='pages_per_block') parser.add_option('-G', '--high_water_mark', default=10, help='blocks used before gc trigger', action='store', type='int', dest='high_water_mark') parser.add_option('-g', '--low_water_mark', default=8, help='gc target before stopping gc', action='store', type='int', dest='low_water_mark') parser.add_option('-R', '--read_time', default=10, help='page read time (usecs)', action='store', type='int', dest='read_time') parser.add_option('-W', '--program_time', default=40, help='page program time (usecs)', action='store', type='int', dest='program_time') parser.add_option('-E', '--erase_time', default=1000, help='page erase time (usecs)', action='store', type='int', dest='erase_time') parser.add_option('-J', '--show_gc', default=False, help='show garbage collector behavior', action='store_true', dest='show_gc') parser.add_option('-F', '--show_state', default=False, help='show flash state', action='store_true', dest='show_state') parser.add_option('-C', '--show_cmds', default=False, help='show commands', action='store_true', dest='show_cmds') parser.add_option('-q', '--quiz_cmds', default=False, help='quiz commands', action='store_true', dest='quiz_cmds') parser.add_option('-S', '--show_stats', default=False, help='show statistics', action='store_true', dest='show_stats') parser.add_option('-c', '--compute', default=False, help='compute answers for me', action='store_true', dest='solve') (options, args) = parser.parse_args() random.seed(options.seed) print('ARG seed %s' % options.seed) print('ARG num_cmds %s' % options.num_cmds) print('ARG op_percentages %s' % options.op_percentages) print('ARG skew %s' % options.skew) print('ARG skew_start %s' % options.skew_start) print('ARG read_fail %s' % options.read_fail) print('ARG cmd_list %s' % options.cmd_list) print('ARG ssd_type %s' % options.ssd_type) print('ARG num_logical_pages %s' % options.num_logical_pages) print('ARG num_blocks %s' % options.num_blocks) print('ARG pages_per_block %s' % options.pages_per_block) print('ARG high_water_mark %s' % options.high_water_mark) print('ARG low_water_mark %s' % options.low_water_mark) print('ARG erase_time %s' % options.erase_time) print('ARG program_time %s' % options.program_time) print('ARG read_time %s' % options.read_time) print('ARG show_gc %s' % options.show_gc) print('ARG show_state %s' % options.show_state) print('ARG show_cmds %s' % options.show_cmds) print('ARG quiz_cmds %s' % options.quiz_cmds) print('ARG show_stats %s' % options.show_stats) print('ARG compute %s' % options.solve) print('') s = ssd(ssd_type=options.ssd_type, num_logical_pages=options.num_logical_pages, num_blocks=options.num_blocks, pages_per_block=options.pages_per_block, block_erase_time=float(options.erase_time), page_program_time=float(options.program_time), page_read_time=float(options.read_time), high_water_mark=options.high_water_mark, low_water_mark=options.low_water_mark, trace_gc=options.show_gc, show_state=options.show_state) # # generate cmds (if not passed in by cmd_list) # hot_cold = False skew_start = options.skew_start if options.skew != '': hot_cold = True skew = options.skew.split('/') if len(skew) != 2: print('bad skew specification; should be 80/20 or something like that') exit(1) hot_percent = int(skew[0])/100.0 hot_target = int(skew[1])/100.0 if options.cmd_list == '': max_page_addr = int(options.num_logical_pages) num_cmds = int(options.num_cmds) p = options.op_percentages.split('/') assert(len(p) == 3) percent_reads, percent_writes, percent_trims = int(p[0]), int(p[1]), int(p[2]) if percent_writes <= 0: print('must have some writes, otherwise nothing in the SSD!') exit(1) printable = string.digits + string.letters cmd_list = [] valid_addresses = [] while len(cmd_list) < num_cmds: which_cmd = int(random.random() * 100.0) if which_cmd < percent_reads: # READ if random.randint(0, 99) < int(options.read_fail): address = random.randint(0, max_page_addr - 1) else: if len(valid_addresses) < 2: continue address = random.choice(valid_addresses) cmd_list.append('r%d' % address) elif which_cmd < percent_reads + percent_writes: # WRITE if skew_start == 0 and hot_cold and random.random() < hot_percent: address = random.randint(0, int(hot_target * (max_page_addr - 1))) else: address = random.randint(0, max_page_addr - 1) if address not in valid_addresses: valid_addresses.append(address) data = random.choice(list(printable)) cmd_list.append('w%d:%s' % (address, data)) if skew_start > 0: skew_start -= 1 else: # TRIM if len(valid_addresses) < 1: continue address = random.choice(valid_addresses) cmd_list.append('t%d' % address) valid_addresses.remove(address) else: cmd_list = options.cmd_list.split(',') s.dump() print('') show_state = options.show_state show_cmds = options.show_cmds quiz_cmds = options.quiz_cmds if quiz_cmds: show_state = True op = 0 for cmd in cmd_list: if cmd == '': break if cmd[0] == 'r': # r10 address = int(cmd.split('r')[1]) data = s.read(address) if show_cmds or (quiz_cmds and options.solve): print('cmd %3d:: read(%d) -> %s' % (op, address, data)) elif quiz_cmds: print('cmd %3d:: read(%d) -> ??' % (op, address)) op += 1 elif cmd[0] == 'w': # w80:b parts = cmd.split(':') address = int(parts[0].split('w')[1]) data = parts[1] rc = s.write(address, data) if show_cmds or (quiz_cmds and options.solve): print('cmd %3d:: write(%d, %s) -> %s' % (op, address, data, rc)) elif quiz_cmds: print('cmd %3d:: command(??) -> ??' % op) op += 1 elif cmd[0] == 't': address = int(cmd.split('t')[1]) rc = s.trim(address) if show_cmds or (quiz_cmds and options.solve): print('cmd %3d:: trim(%d) -> %s' % (op, address, rc)) elif quiz_cmds: print('cmd %d:: command(??) -> ??' % op) op += 1 if show_state: print('') s.dump() print('') # Do GC? s.upkeep() if not show_state: print('') s.dump() print('') if options.show_stats: s.stats() print('')

Exercise

Simulator