Simulator
This lesson explains how to interact with the simulator for the exercise presented in the next lesson.
We'll cover the following...
This is the description of ffs.py, a simulator of FFS allocation policies. Use it
to study FFS behavior under different file and directory creation scenarios.
#! /usr/bin/env python
import math
import sys
from optparse import OptionParser
import random
class file_system:
def __init__(self, num_groups, blocks_per_group, inodes_per_group,
large_file_exception, spread_inodes,
contig_allocation_policy, spread_data_blocks, allocate_faraway,
show_block_addresses, do_per_file_stats, show_file_ops,
show_symbol_map, compute):
self.num_groups = num_groups
self.blocks_per_group = blocks_per_group
self.inodes_per_group = inodes_per_group
self.large_file_exception = large_file_exception
self.spread_inodes = spread_inodes
self.contig_allocation_policy = contig_allocation_policy
self.spread_data_blocks = spread_data_blocks
self.allocate_faraway = allocate_faraway
self.show_block_addresses = show_block_addresses
self.do_per_file_stats = do_per_file_stats
self.show_file_ops = show_file_ops
self.show_symbol_map = show_symbol_map
self.compute = compute
self.group_size = self.inodes_per_group + self.blocks_per_group
self.BITMAP_FREE = '__FREE__'
self.data_bitmap = []
self.inode_bitmap = []
for i in range(self.num_groups):
self.inode_bitmap.append([])
self.data_bitmap.append([])
for j in range(self.blocks_per_group):
self.data_bitmap[i].append(self.BITMAP_FREE)
for j in range(self.inodes_per_group):
self.inode_bitmap[i].append(self.BITMAP_FREE)
self.init_symbols()
self.total_data_free = blocks_per_group * num_groups
self.total_inodes_free = inodes_per_group * num_groups
# make root directory
self.inode_bitmap[0][0] = 0
self.data_bitmap[0][0] = 0 # use one data block for ALL DIRS
self.allocate_symbol(0, '/')
self.total_data_free -= 1
self.total_inodes_free -= 1
# data for each directory, indexed by inode number
self.dir_data = {}
self.dir_data[0] = [('.', 0), ('..', 0)]
# inode data: for each inode, type info
self.inode_type = {}
self.inode_type[0] = 'directory'
# and which blocks comprise the file
self.inode_blocks = {}
self.inode_blocks[0] = [0]
# map names to inode numbers
self.name_to_inode_map = {}
self.name_to_inode_map['/'] = 0
return
def vprint(self, msg):
if self.show_file_ops:
print msg,
return
def get_parent(self, path):
index_of_last_slash = path.rfind('/')
if index_of_last_slash == 0:
return '/', path[index_of_last_slash+1:len(path)]
return path[0:index_of_last_slash], path[index_of_last_slash+1:len(path)]
def name_to_inode(self, path):
if path not in self.name_to_inode_map:
return -1
else:
return self.name_to_inode_map[path]
def set_name_to_inode(self, path, inode_num):
if path in self.name_to_inode_map:
print 'abort: path already in mapping (internal error)'
exit(1)
self.name_to_inode_map[path] = inode_num
return
def get_free_count(self, group, bitmap):
cnt = 0
for b in bitmap:
if b == self.BITMAP_FREE:
cnt += 1
return cnt
def get_free_inode_count(self, group):
return self.get_free_count(group, self.inode_bitmap[group])
def get_free_data_count(self, group):
return self.get_free_count(group, self.data_bitmap[group])
def find_most_free_inodes(self, starting_point):
free_inodes_max = 0
target_group = -1
for g in range(starting_point, self.num_groups):
free_inodes_in_group = self.get_free_inode_count(g)
if free_inodes_in_group > free_inodes_max:
free_inodes_max = free_inodes_in_group
target_group = g
for g in range(0, starting_point):
free_inodes_in_group = self.get_free_inode_count(g)
if free_inodes_in_group > free_inodes_max:
free_inodes_max = free_inodes_in_group
target_group = g
return target_group
def find_free_inodes_in_range(self, group, how_many):
sum_free = 0
for g in range(group, group + how_many):
g_curr = g % self.num_groups
free_inodes_in_group = self.get_free_inode_count(g_curr)
sum_free += free_inodes_in_group
return sum_free
def find_most_free_inodes_multiple(self, starting_point, how_many):
free_inodes_max = 0
target_group = -1
for g in range(starting_point, self.num_groups, how_many):
sum_free = self.find_free_inodes_in_range(g, how_many)
if sum_free > free_inodes_max:
free_inodes_max = sum_free
target_group = g
for g in range(0, starting_point, how_many):
sum_free = self.find_free_inodes_in_range(g, how_many)
if sum_free > free_inodes_max:
free_inodes_max = sum_free
target_group = g
assert(target_group != -1)
return target_group
def find_free_inodes_near(self, target_group):
grower = (target_group + 1) % self.num_groups
shrinker = (target_group - 1) % self.num_groups
for i in range(self.num_groups - 1):
if i % 2 == 0:
current_group = grower
grower = (grower + 1) % self.num_groups
else:
current_group = shrinker
shrinker = (shrinker - 1) % self.num_groups
if self.get_free_inode_count(current_group) > 0:
return current_group
return 1
def pick_group(self, parent, filename, type):
if type == 'regular' and self.spread_inodes == False:
# FFS policy: pick based on parent
parent_inode_number = self.name_to_inode(parent)
target_group = parent_inode_number / self.inodes_per_group
# ensure group has free inode... (and free data blocks?)
num_free_inodes = self.get_free_inode_count(target_group)
if num_free_inodes == 0:
target_group = self.find_free_inodes_near(target_group)
return target_group
elif type == 'directory' or self.spread_inodes == True:
# find group with most free inodes
return self.find_most_free_inodes_multiple(0, self.allocate_faraway)
else:
print 'abort: bad file type [%s] (internal error)' % type
exit(1)
return 0
def range_free(self, group, index, needed, chunks_free):
if needed < chunks_free:
chunks_free = needed
# make list of blocks to check for freedom
index_begin = index
index_end = index + chunks_free - 1
if index_end >= self.blocks_per_group:
return False
for i in range(index_begin, index_end+1):
if self.data_bitmap[group][i] != self.BITMAP_FREE:
return False
return True
if self.data_bitmap[group][index] == self.BITMAP_FREE:
return True
return False
# group is just the group where the inode is
# size is how many are needed total
def allocate_blocks(self, target_group, size, inode_number):
assert(size <= self.total_data_free)
allocated = []
index = 0
allocated_in_group = 0
current_group = target_group
chunks_free = self.contig_allocation_policy
while True:
if self.range_free(current_group, index, size-len(allocated), chunks_free):
# print ' local alloc', current_group, index
assert(self.data_bitmap[current_group][index] == self.BITMAP_FREE)
self.data_bitmap[current_group][index] = inode_number
allocated_in_group += 1
allocated.append((current_group, index))
index += 1
if len(allocated) == size:
# print 'done', allocated
break
# this moves allocation interest to next group when needed
# i.e., when you've searched this entire group or
# when you've exhausted the large file exception
if index == self.blocks_per_group or \
(self.large_file_exception > 0 and \
allocated_in_group == self.large_file_exception):
allocated_in_group = 0
index = 0
current_group = (current_group + 1) % self.num_groups
if current_group == target_group:
chunks_free = 1
return allocated
def find_free_inode(self, group):
inode_number = -1
for i in range(self.inodes_per_group):
if self.inode_bitmap[group][i] == self.BITMAP_FREE:
inode_number = i
break
# don't think this can ever happen but ...
if inode_number == -1:
self.vprint('[cannot find free inode]')
return -1
return inode_number
def find_min_data_usage(self):
min_group = -1
min_usage = 0
for g in range(self.num_groups):
data_free = self.get_free_data_count(g)
if data_free > min_usage:
min_usage = data_free
min_group = g
return min_group
def mark_inode_used(self, group, inode_index):
self.inode_bitmap[group][inode_index] = inode_index + \
(group * self.inodes_per_group)
return
def do_delete(self, path):
parent, filename = self.get_parent(path)
# now, find the file in parent directory
parent_inode_number = self.name_to_inode(parent)
if parent_inode_number == -1:
self.vprint('[cannot find parent inode %s]' % parent)
return -1
del_index = -1
for i in range(len(self.dir_data[parent_inode_number])):
name, inode_number = self.dir_data[parent_inode_number][i]
if name == filename:
del_index = i
break
if del_index == -1:
self.vprint('[cannot find %s in dir %s]' % (filename, parent))
return -1
if self.inode_type[inode_number] == 'directory':
self.vprint('[cannot delete directories]')
return -1
self.dir_data[parent_inode_number].remove((name, inode_number))
for b in self.inode_blocks[inode_number]:
data_group = b / self.num_groups
data_index = b % self.num_groups
self.data_bitmap[data_group][data_index] = self.BITMAP_FREE
inode_group = inode_number / self.num_groups
inode_index = inode_number % self.num_groups
self.inode_bitmap[inode_group][inode_index] = self.BITMAP_FREE
self.free_symbol(inode_number)
del self.name_to_inode_map[path]
self.total_inodes_free += 1
self.total_data_free += len(self.inode_blocks[inode_number])
self.inode_type[inode_number] = ''
self.inode_blocks[inode_number] = []
return 0
def do_create(self, path, size, type):
parent, filename = self.get_parent(path)
# do global checks here
if self.total_inodes_free == 0:
self.vprint('[out of inodes]')
return -1
if self.total_data_free < size:
self.vprint('[out of disk space]')
return -1
# check if foo already exists
parent_inode_number = self.name_to_inode(parent)
if parent_inode_number == -1:
self.vprint('[failed to find parent %s]' % parent)
return -1
for (name, __inode_number) in self.dir_data[parent_inode_number]:
if name == filename:
self.vprint('[file %s already exists in dir %s]' % (filename, parent))
return -1
# allocate new inode: which group?
group = self.pick_group(parent, filename, type)
# pick inode now: it is guaranteed here that group will have a free inode
# thanks to pick_group()...
inode_index = self.find_free_inode(group)
# calc global inode number
inode_number = inode_index + (group * self.inodes_per_group)
# file allocation policy: could fail
# allocated = self.allocate_blocks(group, size, inode_number)
if self.spread_data_blocks:
dest_block_group = self.find_min_data_usage()
print 'target alloc', dest_block_group
allocated = self.allocate_blocks(dest_block_group, size, inode_number)
else:
allocated = self.allocate_blocks(group, size, inode_number)
if len(allocated) == 0:
# allocation failed: no room in file system
return -1
# now do all the allocation work: won't fail from here on down
self.mark_inode_used(group, inode_index)
self.dir_data[parent_inode_number].append((filename, inode_number))
# now, allocate some data blocks
self.inode_type[inode_number] = type
self.inode_blocks[inode_number] = []
for (selected_group, index) in allocated:
global_block_number = index + (selected_group * self.blocks_per_group)
# print 'global allocated', global_block_number
self.inode_blocks[inode_number].append(global_block_number)
# record name to inode number mapping for future lookups
self.set_name_to_inode(path, inode_number)
self.allocate_symbol(inode_number, filename)
# have to fill in contents of empty directory
if type == 'directory':
self.dir_data[inode_number] = [('.', 0), ('..', 0)]
# global accounting
self.total_inodes_free -= 1
self.total_data_free -= size
return 0
def init_symbols(self):
self.symbol_map = {}
self.used_symbols = []
self.available_symbols = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','A','B','C','D','E','F','G','H','I','J','K','L','M','O','P','Q','R','S','T','U','V','W','X','Y','Z','0','1','2','3','4','5','6','7','8','9','!','@','#','%','^','&','*','(',')','[',']','{','}','/','.','<','>','|']
return
def allocate_symbol(self, inode_number, suggested_name):
if suggested_name not in self.used_symbols \
and suggested_name in self.available_symbols:
choice = suggested_name
else:
assert(len(self.available_symbols) > 0)
choice = self.available_symbols[0]
# print 'sym', suggested_name, '->', choice
self.used_symbols.append(choice)
self.available_symbols.remove(choice)
self.symbol_map[inode_number] = choice
return
def free_symbol(self, inode_number):
symbol = self.symbol_map[inode_number]
del self.symbol_map[inode_number]
self.used_symbols.remove(symbol)
self.available_symbols.append(symbol)
return
def get_symbol(self, inode_number):
return self.symbol_map[inode_number]
def print_success_or_fail(self, rc):
if self.show_file_ops:
if rc == 0:
print 'success'
else:
print 'failed'
return
def do_verify(self):
data_used = 0
inodes_used = 0
for g in range(self.num_groups):
for i in range(self.blocks_per_group):
if self.data_bitmap[g][i] != self.BITMAP_FREE:
data_used += 1
for i in range(self.inodes_per_group):
if self.inode_bitmap[g][i] != self.BITMAP_FREE:
inodes_used += 1
assert(data_used + self.total_data_free == (self.num_groups * self.blocks_per_group))
assert(inodes_used + self.total_inodes_free == (self.num_groups * self.inodes_per_group))
for f in self.name_to_inode_map:
inode_number = self.name_to_inode_map[f]
blocks = self.inode_blocks[inode_number]
for b in blocks:
data_group = b / self.blocks_per_group
data_index = b % self.blocks_per_group
assert(self.data_bitmap[data_group][data_index] == inode_number)
return
def create(self, path, size):
self.vprint('op create %s [size:%d] ->' % (path, size))
rc = self.do_create(path, size, 'regular')
self.print_success_or_fail(rc)
return rc
def mkdir(self, path):
self.vprint('op mkdir %s ->' % path)
rc = self.do_create(path, 1, 'directory')
self.print_success_or_fail(rc)
return rc
def delete(self, path):
self.vprint('op delete %s ->' % path)
rc = self.do_delete(path)
self.print_success_or_fail(rc)
return
def read_input(self, filename):
fd = open(filename)
for line in fd:
in_line = line.strip('\n')
line_len = len(in_line)
if line_len == 0:
continue
tmp = in_line.split()
if len(tmp) == 0:
continue
if tmp[0] == 'file':
assert(len(tmp) == 3)
name, size = tmp[1], int(tmp[2])
self.create(name, size)
elif tmp[0] == 'dir':
assert(len(tmp) == 2)
name = tmp[1]
self.mkdir(name)
elif tmp[0] == 'delete':
assert(len(tmp) == 2)
name = tmp[1]
self.delete(name)
elif tmp[0] == 'dump':
assert(len(tmp) == 1)
self.dump()
else:
print 'command not recognized', tmp[0]
exit(1)
self.do_verify()
fd.close()
return
def list_to_string(self, bitmap):
out_str = ''
for i in range(len(bitmap)):
if i > 0 and i % 10 == 0:
out_str += ' '
if bitmap[i] == self.BITMAP_FREE:
out_str += '-'
else:
out_str += '%s' % self.get_symbol(bitmap[i])
return out_str
def do_numeric_header(self, power_level, how_many):
power = int(math.pow(10, power_level))
counter = 0
value = 0
out_str = ''
for i in range(how_many):
if i > 0 and i % 10 == 0:
out_str += ' '
out_str += '%d' % (value % 10)
counter += 1
if counter == power:
value += 1
counter = 0
print out_str,
return
def dump(self):
print ''
print 'num_groups: ', self.num_groups
print 'inodes_per_group:', self.inodes_per_group
print 'blocks_per_group:', self.blocks_per_group
print ''
print 'free data blocks: %d (of %d)' % (self.total_data_free,
(self.num_groups * self.blocks_per_group))
print 'free inodes: %d (of %d)' % (self.total_inodes_free,
(self.num_groups * self.inodes_per_group))
print ''
print 'spread inodes? ', self.spread_inodes
print 'spread data? ', self.spread_data_blocks
print 'contig alloc: ', self.contig_allocation_policy
print ''
inode_power = len('%s' % self.inodes_per_group) - 1
data_power = len('%s' % self.blocks_per_group) - 1
if inode_power > data_power:
max_power = inode_power
else:
max_power = data_power
while max_power >= 0:
print ' ', # spacing before inode print out
if inode_power >= max_power:
self.do_numeric_header(max_power, self.inodes_per_group)
else:
out_str = ' ' * self.inodes_per_group
print out_str,
if data_power >= max_power:
self.do_numeric_header(max_power, self.blocks_per_group)
else:
out_str = ' ' * self.inodes_per_group
print out_str,
print ''
max_power -= 1
print '\ngroup %s' % ('inodes'[0:self.inodes_per_group]),
out_str = ''
for i in range(self.inodes_per_group - len('inodes')):
out_str += ' '
print '%sdata' % out_str
count = 0
for i in range(self.num_groups):
# print ' %3d inodes %s' % (i, self.list_to_string(self.inode_bitmap[i]))
# print ' data %s' % (self.list_to_string(self.data_bitmap[i]))
if self.compute:
print ' %3d %s %s' % (i,
self.list_to_string(self.inode_bitmap[i]),
self.list_to_string(self.data_bitmap[i])),
if self.show_block_addresses:
print ' [%4d-%4d]' % (count, count + self.group_size - 1)
else:
print ''
else:
print ' %3d %s %s' % (i,
'?' * self.inodes_per_group,
'?' * self.blocks_per_group)
count += self.group_size
if self.show_symbol_map == False:
print ''
return
print '\nsymbol inode# filename filetype ',
if self.do_per_file_stats:
print 'block_addresses'
else:
print ''
# sorted(student_tuples, key=lambda student: student[2])
for name in sorted(self.name_to_inode_map):
inode_number = self.name_to_inode_map[name]
file_type = self.inode_type[inode_number]
print '%-6s %6d %-11s %9s' % \
(self.get_symbol(inode_number), inode_number, name, file_type),
if self.do_per_file_stats:
for i in self.inode_blocks[inode_number]:
print i,
print ''
else:
print ''
print ''
return
def get_dist(self, a, b):
if a > b:
return a - b
else:
return b - a
def get_spans(self, path):
inode_number = self.name_to_inode(path)
inode_group = inode_number / self.inodes_per_group
inode_index = inode_number % self.inodes_per_group
inode_address = inode_index + inode_group * self.group_size
# now find all data blocks
min_address = 1 + (self.num_groups * self.group_size)
max_address = -1
data_blocks = self.inode_blocks[inode_number]
for d in data_blocks:
data_group = d / self.blocks_per_group
data_index = d % self.blocks_per_group
data_address = data_index + (data_group * self.group_size) + self.inodes_per_group
if data_address > max_address: max_address = data_address
if data_address < min_address: min_address = data_address
return inode_number, inode_address, min_address, max_address
def do_all_spans(self):
current = 0
total_dist = 0
min_group = 1e6
max_group = -1
print 'span: files'
span_results = {}
filespan_sum = 0
filespan_cnt = 0
for f in self.name_to_inode_map:
inode_number, inode_address, min_address, max_address = self.get_spans(f)
if self.inode_type[inode_number] == 'directory':
continue
data_span = max_address - min_address
abs_min, abs_max = min_address, max_address
if inode_address < abs_min:
abs_min = inode_address
if inode_address > abs_max:
abs_max = inode_address
file_span = abs_max - abs_min
assert(inode_number not in span_results)
span_results[inode_number] = (inode_address, min_address, max_address)
if options.solve:
print ' file: %10s filespan: %3d' % (f, file_span)
else:
print ' file: %10s filespan: %s' % (f, '?')
filespan_sum += file_span
filespan_cnt += 1
if filespan_cnt > 0:
filespan_avg = '%3.2f' % (float(filespan_sum)/float(filespan_cnt))
if options.solve:
print ' avg filespan: %6s' % (filespan_avg)
else:
print ' avg filespan: ?'
print '\nspan: directories'
dirspan_sum = 0
dirspan_cnt = 0
for f in self.name_to_inode_map:
all_addresses = []
inode_number, inode_address, min_address, max_address = self.get_spans(f)
if self.inode_type[inode_number] != 'directory':
continue
for address in [inode_address, min_address, max_address]:
all_addresses.append(address)
for entry_name, entry_inode_number in self.dir_data[inode_number]:
if entry_name == '.' or entry_name == '..':
continue
if self.inode_type[entry_inode_number] == 'directory':
continue
for i in range(3):
all_addresses.append(span_results[entry_inode_number][i])
all_sorted = sorted(all_addresses)
# print 'dirspan', f, all_sorted[len(all_sorted)-1], all_sorted[0]
dirspan = all_sorted[len(all_sorted)-1] - all_sorted[0]
dirspan_sum += dirspan
dirspan_cnt += 1
if options.solve:
print ' dir: %10s dirspan: %3d' % (f, dirspan)
else:
print ' dir: %10s dirspan: ?' % (f)
dirspan_avg = '%3.2f' % (float(dirspan_sum)/float(dirspan_cnt))
if options.solve:
print ' avg dirspan: %6s' % (dirspan_avg)
else:
print ' avg dirspan: ?'
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_groups', default=10, help='number of block groups',
action='store', type='int', dest='num_groups')
parser.add_option('-d', '--datablocks_per_groups', default=30,
help='data blocks per group', action='store',
type='int', dest='blocks_per_group')
parser.add_option('-i', '--inodes_per_group', default=10, help='inodes per group',
action='store', type='int', dest='inodes_per_group')
parser.add_option('-L', '--large_file_exception', default=30,
help='0:off, N>0:blocks in group before spreading file to next group',
action='store', type='int', dest='large_file_exception')
parser.add_option('-f', '--input_file', default='/no/such/file', help='command file',
action='store', type='string', dest='input_file')
parser.add_option('-I', '--spread_inodes', default=False,
help='Instead of putting file inodes in parent dir group, \
spread them evenly around all groups',
action='store_true', dest='spread_inodes')
parser.add_option('-D', '--spread_data', default=False,
help='Instead of putting data near inode, \
spread them evenly around all groups',
action='store_true', dest='spread_data_blocks')
parser.add_option('-A', '--allocate_faraway', default=1,
help='When picking a group, examine this many groups at a time',
action='store', dest='allocate_faraway', type='int')
parser.add_option('-C', '--contig_allocation_policy', default=1,
help='number of contig free blocks needed to alloc',
action='store', type='int', dest='contig_allocation_policy')
parser.add_option('-T', '--show_spans', help='show file and directory spans',
default=False, action='store_true', dest='show_spans')
parser.add_option('-M', '--show_symbol_map', help='show symbol map',
default=False, action='store_true', dest='show_symbol_map')
parser.add_option('-B', '--show_block_addresses',
help='show block addresses alongside groups',
action='store_true', default=False, dest='show_block_addresses')
parser.add_option('-S', '--do_per_file_stats',
help='print out detailed inode stats',
action='store_true', default=False, dest='do_per_file_stats')
parser.add_option('-v', '--show_file_ops',
help='print out detailed per-op success/failure',
action='store_true', default=False, dest='show_file_ops')
parser.add_option('-c', '--compute', help='compute answers for me', action='store_true',
default=False, dest='solve')
(options, args) = parser.parse_args()
random.seed(options.seed)
fs = file_system(num_groups=options.num_groups,
blocks_per_group=options.blocks_per_group,
inodes_per_group=options.inodes_per_group,
large_file_exception=options.large_file_exception,
spread_inodes=options.spread_inodes,
contig_allocation_policy=options.contig_allocation_policy,
spread_data_blocks=options.spread_data_blocks,
allocate_faraway=options.allocate_faraway,
show_block_addresses=options.show_block_addresses,
do_per_file_stats=options.do_per_file_stats,
show_file_ops=options.show_file_ops,
show_symbol_map=options.show_symbol_map,
compute=options.solve)
fs.read_input(options.input_file)
fs.dump()
if options.show_spans:
fs.do_all_spans()
Simulator
The tool is invoked by specifying a command file with the -f flag, which
consists of a series of file create, file delete, and directory create
operations.
For example, run:
prompt> ./ffs.py -f in.example1 -c
to see the output from the first example in the chapter on how FFS based allocation works.
The file in.example1 consists of the following commands:
dir /a
dir /b
file /a/c 2
file /a/d 2
file /a/e 2
file /b/f 2
This tells the simulator to create two directories (/a and /b) and four files
(/a/c, /a/d, /a/e, and /b/f). The root directory is created by default.
The output of the simulator is the location of the inodes and data blocks of
all extant files and directories. For example, from the run above, we would
end up seeing (with the -c flag on, to show you the results):
prompt> ./ffs.py -f in.example1 -c
num_groups: Ask