Exercise
Enhance your understanding by getting hands-on practice by attempting these questions about FFS.
Simulator
This section introduces ffs.py, a simple FFS simulator you can use to understand better how FFS-based file and directory allocation work. See the previous lesson for details on how to run the simulator.
#! /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
Questions
-
Examine the file
in.largefile, and then run the simulator with flag-f in.largefileand-L 4. The latter sets the large-file exception to 4 blocks. What will the resulting allocation look like? Run with-cto check. -
Now run with
-L 30. What do you expect to see? Once again, turn on-cto see if you were right. You can also use-Sto see exactly which blocks were allocated to ...
Ask