%!
%%BoundingBox: (atend)
%%Pages: (atend)
%%DocumentFonts: (atend)
%%EndComments
%
% FrameMaker PostScript Prolog 3.0, for use with FrameMaker 3.0
% Copyright (c) 1986,87,89,90,91 by Frame Technology Corporation.
% All rights reserved.
%
% Known Problems:
% Due to bugs in Transcript, the 'PS-Adobe-' is omitted from line 1
/FMversion (3.0) def
% Set up Color vs. Black-and-White
/FMPrintInColor systemdict /colorimage known
systemdict /currentcolortransfer known or def
% Uncomment this line to force b&w on color printer
% /FMPrintInColor false def
/FrameDict 295 dict def
systemdict /errordict known not {/errordict 10 dict def
errordict /rangecheck {stop} put} if
% The readline in 23.0 doesn't recognize cr's as nl's on AppleTalk
FrameDict /tmprangecheck errordict /rangecheck get put
errordict /rangecheck {FrameDict /bug true put} put
FrameDict /bug false put
mark
% Some PS machines read past the CR, so keep the following 3 lines together!
currentfile 5 string readline
00
0000000000
cleartomark
errordict /rangecheck FrameDict /tmprangecheck get put
FrameDict /bug get {
/readline {
/gstring exch def
/gfile exch def
/gindex 0 def
{
gfile read pop
dup 10 eq {exit} if
dup 13 eq {exit} if
gstring exch gindex exch put
/gindex gindex 1 add def
} loop
pop
gstring 0 gindex getinterval true
} def
} if
/FMVERSION {
FMversion ne {
/Times-Roman findfont 18 scalefont setfont
100 100 moveto
(FrameMaker version does not match postscript_prolog!)
dup =
show showpage
} if
} def
/FMLOCAL {
FrameDict begin
0 def
end
} def
/gstring FMLOCAL
/gfile FMLOCAL
/gindex FMLOCAL
/orgxfer FMLOCAL
/orgproc FMLOCAL
/organgle FMLOCAL
/orgfreq FMLOCAL
/yscale FMLOCAL
/xscale FMLOCAL
/manualfeed FMLOCAL
/paperheight FMLOCAL
/paperwidth FMLOCAL
/FMDOCUMENT {
array /FMfonts exch def
/#copies exch def
FrameDict begin
0 ne dup {setmanualfeed} if
/manualfeed exch def
/paperheight exch def
/paperwidth exch def
/yscale exch def
/xscale exch def
currenttransfer cvlit /orgxfer exch def
currentscreen cvlit /orgproc exch def
/organgle exch def /orgfreq exch def
setpapername
manualfeed {true} {papersize} ifelse
{manualpapersize} {false} ifelse
{desperatepapersize} if
end
} def
/pagesave FMLOCAL
/orgmatrix FMLOCAL
/landscape FMLOCAL
/FMBEGINPAGE {
FrameDict begin
/pagesave save def
3.86 setmiterlimit
/landscape exch 0 ne def
landscape {
90 rotate 0 exch neg translate pop
}
{pop pop}
ifelse
xscale yscale scale
/orgmatrix matrix def
gsave
} def
/FMENDPAGE {
grestore
pagesave restore
end
showpage
} def
/FMFONTDEFINE {
FrameDict begin
findfont
ReEncode
1 index exch
definefont
FMfonts 3 1 roll
put
end
} def
/FMFILLS {
FrameDict begin
array /fillvals exch def
end
} def
/FMFILL {
FrameDict begin
fillvals 3 1 roll put
end
} def
/FMNORMALIZEGRAPHICS {
newpath
0.0 0.0 moveto
1 setlinewidth
0 setlinecap
0 0 0 sethsbcolor
0 setgray
} bind def
/fx FMLOCAL
/fy FMLOCAL
/fh FMLOCAL
/fw FMLOCAL
/llx FMLOCAL
/lly FMLOCAL
/urx FMLOCAL
/ury FMLOCAL
/FMBEGINEPSF {
end
/FMEPSF save def
/showpage {} def
FMNORMALIZEGRAPHICS
[/fy /fx /fh /fw /ury /urx /lly /llx] {exch def} forall
fx fy translate
rotate
fw urx llx sub div fh ury lly sub div scale
llx neg lly neg translate
} bind def
/FMENDEPSF {
FMEPSF restore
FrameDict begin
} bind def
FrameDict begin
/setmanualfeed {
%%BeginFeature *ManualFeed True
statusdict /manualfeed true put
%%EndFeature
} def
/max {2 copy lt {exch} if pop} bind def
/min {2 copy gt {exch} if pop} bind def
/inch {72 mul} def
/pagedimen {
paperheight sub abs 16 lt exch
paperwidth sub abs 16 lt and
{/papername exch def} {pop} ifelse
} def
/papersizedict FMLOCAL
/setpapername {
/papersizedict 14 dict def
papersizedict begin
/papername /unknown def
/Letter 8.5 inch 11.0 inch pagedimen
/LetterSmall 7.68 inch 10.16 inch pagedimen
/Tabloid 11.0 inch 17.0 inch pagedimen
/Ledger 17.0 inch 11.0 inch pagedimen
/Legal 8.5 inch 14.0 inch pagedimen
/Statement 5.5 inch 8.5 inch pagedimen
/Executive 7.5 inch 10.0 inch pagedimen
/A3 11.69 inch 16.5 inch pagedimen
/A4 8.26 inch 11.69 inch pagedimen
/A4Small 7.47 inch 10.85 inch pagedimen
/B4 10.125 inch 14.33 inch pagedimen
/B5 7.16 inch 10.125 inch pagedimen
end
} def
/papersize {
papersizedict begin
/Letter {lettertray letter} def
/LetterSmall {lettertray lettersmall} def
/Tabloid {11x17tray 11x17} def
/Ledger {ledgertray ledger} def
/Legal {legaltray legal} def
/Statement {statementtray statement} def
/Executive {executivetray executive} def
/A3 {a3tray a3} def
/A4 {a4tray a4} def
/A4Small {a4tray a4small} def
/B4 {b4tray b4} def
/B5 {b5tray b5} def
/unknown {unknown} def
papersizedict dup papername known {papername} {/unknown} ifelse get
end
/FMdicttop countdictstack 1 add def
statusdict begin stopped end
countdictstack -1 FMdicttop {pop end} for
} def
/manualpapersize {
papersizedict begin
/Letter {letter} def
/LetterSmall {lettersmall} def
/Tabloid {11x17} def
/Ledger {ledger} def
/Legal {legal} def
/Statement {statement} def
/Executive {executive} def
/A3 {a3} def
/A4 {a4} def
/A4Small {a4small} def
/B4 {b4} def
/B5 {b5} def
/unknown {unknown} def
papersizedict dup papername known {papername} {/unknown} ifelse get
end
stopped
} def
/desperatepapersize {
statusdict /setpageparams known
{
paperwidth paperheight 0 1
statusdict begin
{setpageparams} stopped pop
end
} if
} def
/savematrix {
orgmatrix currentmatrix pop
} bind def
/restorematrix {
orgmatrix setmatrix
} bind def
/dmatrix matrix def
/dpi 72 0 dmatrix defaultmatrix dtransform
dup mul exch dup mul add sqrt def
/freq dpi 18.75 div 8 div round dup 0 eq {pop 1} if 8 mul dpi exch div def
/sangle 1 0 dmatrix defaultmatrix dtransform exch atan def
/DiacriticEncoding [
/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef /space /exclam /quotedbl
/numbersign /dollar /percent /ampersand /quotesingle /parenleft
/parenright /asterisk /plus /comma /hyphen /period /slash /zero /one
/two /three /four /five /six /seven /eight /nine /colon /semicolon
/less /equal /greater /question /at /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 /bracketleft /backslash
/bracketright /asciicircum /underscore /grave /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 /braceleft /bar
/braceright /asciitilde /.notdef /Adieresis /Aring /Ccedilla /Eacute
/Ntilde /Odieresis /Udieresis /aacute /agrave /acircumflex /adieresis
/atilde /aring /ccedilla /eacute /egrave /ecircumflex /edieresis
/iacute /igrave /icircumflex /idieresis /ntilde /oacute /ograve
/ocircumflex /odieresis /otilde /uacute /ugrave /ucircumflex
/udieresis /dagger /.notdef /cent /sterling /section /bullet
/paragraph /germandbls /registered /copyright /trademark /acute
/dieresis /.notdef /AE /Oslash /.notdef /.notdef /.notdef /.notdef
/yen /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
/ordfeminine /ordmasculine /.notdef /ae /oslash /questiondown
/exclamdown /logicalnot /.notdef /florin /.notdef /.notdef
/guillemotleft /guillemotright /ellipsis /.notdef /Agrave /Atilde
/Otilde /OE /oe /endash /emdash /quotedblleft /quotedblright
/quoteleft /quoteright /.notdef /.notdef /ydieresis /Ydieresis
/fraction /currency /guilsinglleft /guilsinglright /fi /fl /daggerdbl
/periodcentered /quotesinglbase /quotedblbase /perthousand
/Acircumflex /Ecircumflex /Aacute /Edieresis /Egrave /Iacute
/Icircumflex /Idieresis /Igrave /Oacute /Ocircumflex /.notdef /Ograve
/Uacute /Ucircumflex /Ugrave /dotlessi /circumflex /tilde /macron
/breve /dotaccent /ring /cedilla /hungarumlaut /ogonek /caron
] def
/ReEncode {
dup
length
dict begin
{
1 index /FID ne
{def}
{pop pop} ifelse
} forall
0 eq {/Encoding DiacriticEncoding def} if
currentdict
end
} bind def
/graymode true def
/bwidth FMLOCAL
/bpside FMLOCAL
/bstring FMLOCAL
/onbits FMLOCAL
/offbits FMLOCAL
/xindex FMLOCAL
/yindex FMLOCAL
/x FMLOCAL
/y FMLOCAL
/setpattern {
/bwidth exch def
/bpside exch def
/bstring exch def
/onbits 0 def /offbits 0 def
freq sangle landscape {90 add} if
{/y exch def
/x exch def
/xindex x 1 add 2 div bpside mul cvi def
/yindex y 1 add 2 div bpside mul cvi def
bstring yindex bwidth mul xindex 8 idiv add get
1 7 xindex 8 mod sub bitshift and 0 ne
{/onbits onbits 1 add def 1}
{/offbits offbits 1 add def 0}
ifelse
}
setscreen
{} settransfer
offbits offbits onbits add div FMsetgray
/graymode false def
} bind def
/grayness {
FMsetgray
graymode not {
/graymode true def
orgxfer cvx settransfer
orgfreq organgle orgproc cvx setscreen
} if
} bind def
/HUE FMLOCAL
/SAT FMLOCAL
/BRIGHT FMLOCAL
/Colors FMLOCAL
FMPrintInColor
{
/HUE 0 def
/SAT 0 def
/BRIGHT 0 def
% array of arrays Hue and Sat values for the separations [HUE BRIGHT]
/Colors
[[0 0 ] % black
[0 0 ] % white
[0.00 1.0] % red
[0.37 1.0] % green
[0.60 1.0] % blue
[0.50 1.0] % cyan
[0.83 1.0] % magenta
[0.16 1.0] % comment / yellow
] def
/BEGINBITMAPCOLOR {
BITMAPCOLOR} def
/BEGINBITMAPCOLORc {
BITMAPCOLORc} def
/BEGINBITMAPTRUECOLOR {
BITMAPTRUECOLOR } def
/BEGINBITMAPTRUECOLORc {
BITMAPTRUECOLORc } def
/K {
Colors exch get dup
0 get /HUE exch store
1 get /BRIGHT exch store
HUE 0 eq BRIGHT 0 eq and
{1.0 SAT sub setgray}
{HUE SAT BRIGHT sethsbcolor}
ifelse
} def
/FMsetgray {
/SAT exch 1.0 exch sub store
HUE 0 eq BRIGHT 0 eq and
{1.0 SAT sub setgray}
{HUE SAT BRIGHT sethsbcolor}
ifelse
} bind def
}
{
/BEGINBITMAPCOLOR {
BITMAPGRAY} def
/BEGINBITMAPCOLORc {
BITMAPGRAYc} def
/BEGINBITMAPTRUECOLOR {
BITMAPTRUEGRAY } def
/BEGINBITMAPTRUECOLORc {
BITMAPTRUEGRAYc } def
/FMsetgray {setgray} bind def
/K {
pop
} def
}
ifelse
/normalize {
transform round exch round exch itransform
} bind def
/dnormalize {
dtransform round exch round exch idtransform
} bind def
/lnormalize {
0 dtransform exch cvi 2 idiv 2 mul 1 add exch idtransform pop
} bind def
/H {
lnormalize setlinewidth
} bind def
/Z {
setlinecap
} bind def
/fillvals FMLOCAL
/X {
fillvals exch get
dup type /stringtype eq
{8 1 setpattern}
{grayness}
ifelse
} bind def
/V {
gsave eofill grestore
} bind def
/N {
stroke
} bind def
/M {newpath moveto} bind def
/E {lineto} bind def
/D {curveto} bind def
/O {closepath} bind def
/n FMLOCAL
/L {
/n exch def
newpath
normalize
moveto
2 1 n {pop normalize lineto} for
} bind def
/Y {
L
closepath
} bind def
/x1 FMLOCAL
/x2 FMLOCAL
/y1 FMLOCAL
/y2 FMLOCAL
/rad FMLOCAL
/R {
/y2 exch def
/x2 exch def
/y1 exch def
/x1 exch def
x1 y1
x2 y1
x2 y2
x1 y2
4 Y
} bind def
% The following commented out code did not work for tangent lines of zero
% length. The code following it was provided by Frame to patch this error.
%
%/RR {
% /rad exch def
% normalize
% /y2 exch def
% /x2 exch def
% normalize
% /y1 exch def
% /x1 exch def
% newpath
% x1 y1 rad add moveto
% x1 y2 x2 y2 rad arcto
% x2 y2 x2 y1 rad arcto
% x2 y1 x1 y1 rad arcto
% x1 y1 x1 y2 rad arcto
% closepath
% 16 {pop} repeat
% } bind def
/rarc
{rad
{arcto} stopped
} bind def
/RR {
/rad exch def
normalize
/y2 exch def
/x2 exch def
normalize
/y1 exch def
/x1 exch def
mark
newpath
x1 y1 rad add moveto
x1 y2 x2 y2 rarc
x2 y2 x2 y1 rarc
x2 y1 x1 y1 rarc
% x2 y1 x1 y1 rarc
x1 y1 x1 y2 rarc
closepath
cleartomark
} bind def
/C {
grestore
gsave
R
clip
} bind def
/FMpointsize FMLOCAL
/F {
FMfonts exch get
FMpointsize scalefont
setfont
} bind def
/Q {
/FMpointsize exch def
F
} bind def
/T {
moveto show
} bind def
/RF {
rotate
0 ne {-1 1 scale} if
} bind def
/TF {
gsave
moveto
RF
show
grestore
} bind def
/P {
moveto
0 32 3 2 roll widthshow
} bind def
/PF {
gsave
moveto
RF
0 32 3 2 roll widthshow
grestore
} bind def
/S {
moveto
0 exch ashow
} bind def
/SF {
gsave
moveto
RF
0 exch ashow
grestore
} bind def
/B {
moveto
0 32 4 2 roll 0 exch awidthshow
} bind def
/BF {
gsave
moveto
RF
0 32 4 2 roll 0 exch awidthshow
grestore
} bind def
/G {
gsave
newpath
normalize translate 0.0 0.0 moveto
dnormalize scale
0.0 0.0 1.0 5 3 roll arc
closepath fill
grestore
} bind def
/A {
gsave
savematrix
newpath
2 index 2 div add exch 3 index 2 div sub exch
normalize 2 index 2 div sub exch 3 index 2 div add exch
translate
scale
0.0 0.0 1.0 5 3 roll arc
restorematrix
stroke
grestore
} bind def
/x FMLOCAL
/y FMLOCAL
/w FMLOCAL
/h FMLOCAL
/xx FMLOCAL
/yy FMLOCAL
/ww FMLOCAL
/hh FMLOCAL
/FMsaveobject FMLOCAL
/FMoptop FMLOCAL
/FMdicttop FMLOCAL
/BEGINPRINTCODE {
/FMdicttop countdictstack 1 add def
/FMoptop count 4 sub def
/FMsaveobject save def
userdict begin
/showpage {} def
FMNORMALIZEGRAPHICS
3 index neg 3 index neg translate
} bind def
/ENDPRINTCODE {
count -1 FMoptop {pop pop} for
countdictstack -1 FMdicttop {pop end} for
FMsaveobject restore
} bind def
/gn {
0
{ 46 mul
cf read pop
32 sub
dup 46 lt {exit} if
46 sub add
} loop
add
} bind def
/str FMLOCAL
/cfs {
/str sl string def
0 1 sl 1 sub {str exch val put} for
str def
} bind def
/ic [
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0223
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0223
0
{0 hx} {1 hx} {2 hx} {3 hx} {4 hx} {5 hx} {6 hx} {7 hx} {8 hx} {9 hx}
{10 hx} {11 hx} {12 hx} {13 hx} {14 hx} {15 hx} {16 hx} {17 hx} {18 hx}
{19 hx} {gn hx} {0} {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12}
{13} {14} {15} {16} {17} {18} {19} {gn} {0 wh} {1 wh} {2 wh} {3 wh}
{4 wh} {5 wh} {6 wh} {7 wh} {8 wh} {9 wh} {10 wh} {11 wh} {12 wh}
{13 wh} {14 wh} {gn wh} {0 bl} {1 bl} {2 bl} {3 bl} {4 bl} {5 bl} {6 bl}
{7 bl} {8 bl} {9 bl} {10 bl} {11 bl} {12 bl} {13 bl} {14 bl} {gn bl}
{0 fl} {1 fl} {2 fl} {3 fl} {4 fl} {5 fl} {6 fl} {7 fl} {8 fl} {9 fl}
{10 fl} {11 fl} {12 fl} {13 fl} {14 fl} {gn fl}
] def
/sl FMLOCAL
/val FMLOCAL
/ws FMLOCAL
/im FMLOCAL
/bs FMLOCAL
/cs FMLOCAL
/len FMLOCAL
/pos FMLOCAL
/ms {
/sl exch def
/val 255 def
/ws cfs
/im cfs
/val 0 def
/bs cfs
/cs cfs
} bind def
400 ms
/cip {
is
0
cf cs readline pop
{ ic exch get exec
add
} forall
pop
/tot w 1 sub def
0 1 tot {
/indx exch def
/indxa is indx get def
/placer nredt indxa get def
/placeg ngreent indxa get def
/placeb nbluet indxa get def
cris indx placer 255 mul cvi put
cgis indx placeg 255 mul cvi put
cbis indx placeb 255 mul cvi put
} for pop cris
} bind def
/ip {
is
0
cf cs readline pop
{ ic exch get exec
add
} forall
pop
} bind def
/wh {
/len exch def
/pos exch def
ws 0 len getinterval im pos len getinterval copy pop
pos len
} bind def
/bl {
/len exch def
/pos exch def
bs 0 len getinterval im pos len getinterval copy pop
pos len
} bind def
/s1 1 string def
/fl {
/len exch def
/pos exch def
/val cf s1 readhexstring pop 0 get def
pos 1 pos len add 1 sub {im exch val put} for
pos len
} bind def
/hx {
3 copy getinterval
cf exch readhexstring pop pop
} bind def
/h FMLOCAL
/w FMLOCAL
/d FMLOCAL
/lb FMLOCAL
/bitmapsave FMLOCAL
/is FMLOCAL
/cf FMLOCAL
/wbytes {
dup
8 eq {pop} {1 eq {7 add 8 idiv} {3 add 4 idiv} ifelse} ifelse
} bind def
/BEGINBITMAPBWc {
1 {} COMMONBITMAPc
} bind def
/BEGINBITMAPGRAYc {
8 {} COMMONBITMAPc
} bind def
/BEGINBITMAP2BITc {
2 {} COMMONBITMAPc
} bind def
/COMMONBITMAPc {
/r exch def
/d exch def
gsave
translate rotate scale /h exch def /w exch def
/lb w d wbytes def
sl lb lt {lb ms} if
/bitmapsave save def
r
/is im 0 lb getinterval def
ws 0 lb getinterval is copy pop
/cf currentfile def
w h d [w 0 0 h neg 0 h]
{ip} image
bitmapsave restore
grestore
} bind def
/BEGINBITMAPBW {
1 {} COMMONBITMAP
} bind def
/BEGINBITMAPGRAY {
8 {} COMMONBITMAP
} bind def
/BEGINBITMAP2BIT {
2 {} COMMONBITMAP
} bind def
/COMMONBITMAP {
/r exch def
/d exch def
gsave
translate rotate scale /h exch def /w exch def
/bitmapsave save def
r
/is w d wbytes string def
/cf currentfile def
w h d [w 0 0 h neg 0 h]
{cf is readhexstring pop} image
bitmapsave restore
grestore
} bind def
/proc1 FMLOCAL
/proc2 FMLOCAL
/newproc FMLOCAL
/Fmcc {
/proc2 exch cvlit def
/proc1 exch cvlit def
/newproc proc1 length proc2 length add array def
newproc 0 proc1 putinterval
newproc proc1 length proc2 putinterval
newproc cvx
} bind def
/ngrayt 256 array def
/nredt 256 array def
/nbluet 256 array def
/ngreent 256 array def
/gryt FMLOCAL
/blut FMLOCAL
/grnt FMLOCAL
/redt FMLOCAL
/indx FMLOCAL
/cynu FMLOCAL
/magu FMLOCAL
/yelu FMLOCAL
/k FMLOCAL
/u FMLOCAL
/colorsetup {
currentcolortransfer
/gryt exch def
/blut exch def
/grnt exch def
/redt exch def
0 1 255 {
/indx exch def
/cynu 1 red indx get 255 div sub def
/magu 1 green indx get 255 div sub def
/yelu 1 blue indx get 255 div sub def
/k cynu magu min yelu min def
nredt indx 1 0 cynu max sub redt exec put
ngreent indx 1 0 magu max sub grnt exec put
nbluet indx 1 0 yelu max sub blut exec put
ngrayt indx 1 k sub gryt exec put
} for
} bind def
/tran FMLOCAL
/fakecolorsetup {
/tran 256 string def
0 1 255 {/indx exch def
tran indx
red indx get 77 mul
green indx get 151 mul
blue indx get 28 mul
add add 256 idiv put} for
currenttransfer
{255 mul cvi tran exch get 255.0 div}
exch Fmcc settransfer
} bind def
/BITMAPCOLOR {
/d 8 def
gsave
translate rotate scale /h exch def /w exch def
/bitmapsave save def
colorsetup
/is w d wbytes string def
/ris w d wbytes string def
/gis w d wbytes string def
/bis w d wbytes string def
/cf currentfile def
w h d [w 0 0 h neg 0 h]
{cf is readhexstring pop
/tot w 1 sub def
0 1 tot {
/indx exch def
/indxa is indx get def
/placer nredt indxa get def
/placeg ngreent indxa get def
/placeb nbluet indxa get def
ris indx placer 255 mul cvi put
gis indx placeg 255 mul cvi put
bis indx placeb 255 mul cvi put
} for pop ris}
{gis} {bis} true 3 colorimage
bitmapsave restore
grestore
} bind def
/BITMAPCOLORc {
/d 8 def
gsave
translate rotate scale /h exch def /w exch def
/lb w d wbytes def
sl lb lt {lb ms} if
/bitmapsave save def
colorsetup
/is im 0 lb getinterval def
/cris lb string def
/cgis lb string def
/cbis lb string def
ws 0 lb getinterval is copy pop
/cf currentfile def
w h d [w 0 0 h neg 0 h]
{cip} {cgis} {cbis} true 3 colorimage
bitmapsave restore
grestore
} bind def
/BITMAPTRUECOLORc {
gsave
translate rotate scale /h exch def /w exch def
/bitmapsave save def
/is w string def
ws 0 w getinterval is copy pop
/cf currentfile def
w h 8 [w 0 0 h neg 0 h]
{ip} {gip} {bip} true 3 colorimage
bitmapsave restore
grestore
} bind def
/BITMAPTRUECOLOR {
gsave
translate rotate scale /h exch def /w exch def
/bitmapsave save def
/is w string def
/gis w string def
/bis w string def
/cf currentfile def
w h 8 [w 0 0 h neg 0 h]
{ cf is readhexstring pop }
{ cf gis readhexstring pop }
{ cf bis readhexstring pop }
true 3 colorimage
bitmapsave restore
grestore
} bind def
/BITMAPTRUEGRAYc {
gsave
translate rotate scale /h exch def /w exch def
/bitmapsave save def
/is w string def
ws 0 w getinterval is copy pop
/cf currentfile def
w h 8 [w 0 0 h neg 0 h]
{ip gip bip w gray} image
bitmapsave restore
grestore
} bind def
/ww FMLOCAL
/r FMLOCAL
/g FMLOCAL
/b FMLOCAL
/i FMLOCAL
/gray {
/ww exch def
/b exch def
/g exch def
/r exch def
0 1 ww 1 sub { /i exch def r i get .299 mul g i get .587 mul
b i get .114 mul add add r i 3 -1 roll floor cvi put } for
r
} bind def
/BITMAPTRUEGRAY {
gsave
translate rotate scale /h exch def /w exch def
/bitmapsave save def
/is w string def
/gis w string def
/bis w string def
/cf currentfile def
w h 8 [w 0 0 h neg 0 h]
{ cf is readhexstring pop
cf gis readhexstring pop
cf bis readhexstring pop w gray} image
bitmapsave restore
grestore
} bind def
/BITMAPGRAY {
8 {fakecolorsetup} COMMONBITMAP
} bind def
/BITMAPGRAYc {
8 {fakecolorsetup} COMMONBITMAPc
} bind def
/ENDBITMAP {
} bind def
end
/ALDsave FMLOCAL
/ALDmatrix matrix def ALDmatrix currentmatrix pop
/StartALD {
/ALDsave save def
savematrix
ALDmatrix setmatrix
} bind def
/InALD {
restorematrix
} bind def
/DoneALD {
ALDsave restore
} bind def
%%EndProlog
%%BeginSetup
(3.0) FMVERSION
1 1 612 792 0 1 10 FMDOCUMENT
0 0 /Palatino-Roman FMFONTDEFINE
1 0 /Times-Roman FMFONTDEFINE
2 0 /Times-Bold FMFONTDEFINE
3 0 /Courier-Bold FMFONTDEFINE
4 0 /Times-Italic FMFONTDEFINE
5 0 /Times-BoldItalic FMFONTDEFINE
32 FMFILLS
0 0 FMFILL
1 0.1 FMFILL
2 0.3 FMFILL
3 0.5 FMFILL
4 0.7 FMFILL
5 0.9 FMFILL
6 0.97 FMFILL
7 1 FMFILL
8 <0f1e3c78f0e1c387> FMFILL
9 <0f87c3e1f0783c1e> FMFILL
10 <cccccccccccccccc> FMFILL
11 <ffff0000ffff0000> FMFILL
12 <8142241818244281> FMFILL
13 <03060c183060c081> FMFILL
14 <8040201008040201> FMFILL
16 1 FMFILL
17 0.9 FMFILL
18 0.7 FMFILL
19 0.5 FMFILL
20 0.3 FMFILL
21 0.1 FMFILL
22 0.03 FMFILL
23 0 FMFILL
24 <f0e1c3870f1e3c78> FMFILL
25 <f0783c1e0f87c3e1> FMFILL
26 <3333333333333333> FMFILL
27 <0000ffff0000ffff> FMFILL
28 <7ebddbe7e7dbbd7e> FMFILL
29 <fcf9f3e7cf9f3f7e> FMFILL
30 <7fbfdfeff7fbfdfe> FMFILL
%%EndSetup
%%Page: "1" 1
%%BeginPaperSize: Letter
%%EndPaperSize
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(xFS Space Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(1) 500 42.62 T
1 24 Q
(xFS Space Manager Design) 172.43 704 T
2 12 Q
(Doug Doucette) 268.2 664 T
2 16 Q
(1.0 Intr) 72 621.33 T
(oduction) 127.23 621.33 T
1 12 Q
0.92 (This is the design document for the Space Manager module of xFS. The following areas of the) 72 594 P
0.03 (design are described: Functionality and External Interfaces; On-Disk Structures; Internal Compo-) 72 580 P
0.53 (nents and Interfaces; Internal Data Structures and Algorithms; User Library and Utility Support;) 72 566 P
(Performance Characterization; Implementation Plan and Schedule.) 72 552 T
2 16 Q
(2.0 Functionality and External Interfaces) 72 511.33 T
2 14 Q
(2.1 Overview) 72 476.67 T
1 12 Q
-0.12 (The Space Manager manages the allocation of disk space within a \336le system. It is responsible for) 72 450 P
0.45 (mapping a \336le \050a sequence of bytes\051 into a sequence of disk blocks. The internal structure of the) 72 436 P
0.14 (\336le system: allocation \050cylinder\051 groups, inodes, and freespace management are controlled by the) 72 422 P
(Space Manager) 72 408 T
(, as well as the above mapping function.) 145.78 408 T
0.81 (The space layout choices in the design are in\337uenced by the requirements to support very lar) 72 382 P
0.81 (ge) 528.68 382 P
0.83 (\336les and \336le systems ef) 72 368 P
0.83 (\336ciently) 187.04 368 P
0.83 (. The Space Manager is responsible for optimizing the layout of) 225.57 368 P
1.45 (blocks in a \336le, determining rate guarantee information for each \336le, and keeping related \336les) 72 354 P
(close to each other on the disks.) 72 340 T
0.14 (The internal details of space management are hidden from the users and from the Name Manager) 72 314 P
0.96 (layer) 72 300 P
0.96 (, except that users are allowed to determine whether a \336le is suf) 95.5 300 P
0.96 (\336ciently contiguous and if) 411.53 300 P
(not, to have the \336le\325) 72 286 T
(s space be reallocated so that it is more contiguous.) 167.61 286 T
2 14 Q
(2.2 External Interfaces Pr) 72 252.67 T
(ovided) 229.9 252.67 T
1 12 Q
0.9 (All exported interfaces are call-based, not message-based. Control and administration messages) 72 226 P
0.14 (may come from another node but will be handled by the system call and administration layer and) 72 212 P
(turned into a local call.) 72 198 T
2 F
(2.2.1 Interfaces to xFS Components) 72 166 T
3 F
(\245) 72 146 T
1 F
(inode manipulation routines \050analogous to iget, iput, efs_iupdat\051) 85.75 146 T
3 F
(\245) 72 126 T
1 F
(inode allocation and freeing routines \050analogous to efs_ialloc, efs_ifree\051) 85.75 126 T
FMENDPAGE
%%EndPage: "1" 2
%%Page: "2" 2
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(xFS Space Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(2) 500 42.62 T
2 12 Q
(2.2.2 Vnode \050per) 72 712 T
(-\336le\051 Interfaces) 159.17 712 T
3 F
(\245) 72 692 T
1 F
-0.19 (a block mapping and allocation routine \050VOP_BMAP\051. W) 85.75 692 P
-0.19 (ill accept a starting of) 363.79 692 P
-0.19 (fset and length,) 466.75 692 P
0.36 (vnode pointer) 85.75 678 P
0.36 (, read/write \337ag, and return an array of data structures describing the location of) 151.92 678 P
(the blocks. For writes, the disk space is allocated as necessary) 85.75 664 T
(.) 382.08 664 T
3 F
(\245) 72 644 T
1 F
0.29 (VOP_SET) 85.75 644 P
0.29 (A) 136.09 644 P
0.29 (TTR for the A) 143.42 644 P
0.29 (T_SIZE attribute, which sets the \336le size. HSM support would have) 211.92 644 P
(us add another operation to allow \322hole-punching\323 in a \336le\325) 85.75 630 T
(s address space.) 371.22 630 T
3 F
(\245) 72 610 T
1 F
0.86 (VOP_INACTIVE can result in the \336le being removed and its blocks truncated. This invokes) 85.75 610 P
(the same code that a VOP_SET) 85.75 596 T
(A) 236.35 596 T
(TTR of A) 243.68 596 T
(T_SIZE to 0 does.) 289.65 596 T
2 F
(2.2.3 VFS \050per \336le system\051 Interfaces) 72 564 T
3 F
(\245) 72 544 T
1 F
(\336le system extension and contraction need to be new vfsops routines.) 85.75 544 T
3 F
(\245) 72 524 T
1 F
(statistics are handled by VFS_ST) 85.75 524 T
(A) 244.69 524 T
(TVFS.) 252.02 524 T
2 14 Q
(2.3 External Interfaces Used) 72 490.67 T
2 12 Q
(2.3.1 Interfaces to xFS Components) 72 458 T
3 F
(\245) 72 438 T
1 F
(Buf) 85.75 438 T
(fer cache interfaces) 103.52 438 T
3 F
(\245) 72 418 T
1 F
(Log Manager interfaces) 85.75 418 T
3 F
(\245) 72 398 T
1 F
(V) 85.75 398 T
(olume Manager interfaces \050for rate guarantees?\051) 92.86 398 T
2 F
(2.3.2 Interfaces to IRIX Kernel) 72 366 T
3 F
(\245) 72 346 T
1 F
(Memory allocation) 85.75 346 T
3 F
(\245) 72 326 T
1 F
(Memory mapping interfaces \050for VOP_MAP) 85.75 326 T
(, etc.\051) 300.26 326 T
3 F
(\245) 72 306 T
1 F
(Locks and semaphores) 85.75 306 T
2 16 Q
(3.0 On-Disk Structur) 72 265.33 T
(es) 220.08 265.33 T
1 12 Q
1.33 (This section describes the logical structure and physical layout of all disk space for which the) 72 238 P
(Space Manager is responsible.) 72 224 T
2 14 Q
(3.1 Superblock) 72 190.67 T
1 12 Q
0.54 (The superblock is the root of all \336le system information. The superblock is located at the begin-) 72 164 P
-0.24 (ning of the \336le system \050of) 72 150 P
-0.24 (fset 0\051; this is a departure from historical behavior of UNIX \336le systems,) 194.16 150 P
-0.05 (which start at of) 72 136 P
-0.05 (fset 512 \050typically\051. T) 149.24 136 P
-0.05 (o avoid confusion between xFS and EFS \336le systems, of) 252.84 136 P
-0.05 (fset) 522.68 136 P
0.24 (512 of an xFS \336le system must contain a value other than the magic number value of an EFS \336le) 72 122 P
(system\325) 72 108 T
(s superblock.) 108.65 108 T
-0.29 (The superblock contains enough information to \336nd all the other pieces of the \336le system. There is) 72 82 P
(an incore copy of it which is part of the information belonging to a mounted \336le system.) 72 68 T
FMENDPAGE
%%EndPage: "2" 3
%%Page: "3" 3
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(xFS Space Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(3) 500 42.62 T
1 12 Q
(The following \336elds, at least, are present in the superblock:) 72 712 T
3 F
(\245) 72 692 T
1 F
(xFS magic number) 85.75 692 T
3 F
(\245) 72 672 T
1 F
(xFS version) 85.75 672 T
3 F
(\245) 72 652 T
1 F
(File system unique id) 85.75 652 T
3 F
(\245) 72 632 T
1 F
(Last name \336le system mounted as) 85.75 632 T
3 F
(\245) 72 612 T
1 F
(Logical block size \050lbsz, in bytes, 2) 85.75 612 T
1 10 Q
(9) 255.63 616.8 T
1 12 Q
( .. 2) 260.63 612 T
1 10 Q
(16) 278.62 616.8 T
1 12 Q
(\051) 288.61 612 T
3 F
(\245) 72 592 T
1 F
(Unreliable extent size \050in lbsz\051) 85.75 592 T
3 F
(\245) 72 572 T
1 F
(Physical sector size \050bytes\051) 85.75 572 T
3 F
(\245) 72 552 T
1 F
0.35 (Inode size \050bytes, 2) 85.75 552 P
1 10 Q
0.29 (7) 180.05 556.8 P
1 12 Q
0.35 ( .. 2) 185.05 552 P
1 10 Q
0.29 (1) 203.74 556.8 P
0.29 (1) 208.36 556.8 P
1 12 Q
0.35 (\051 and some information about how the space in the inode is divided) 213.36 552 P
(up, such as a minimum size for each of the data and attribute areas of the inode) 85.75 538 T
3 F
(\245) 72 518 T
1 F
(Data block allocation mechanism, choice of bitmap or B-tree, maybe others) 85.75 518 T
3 F
(\245) 72 498 T
1 F
(Small \336les allocated in inodes, or not) 85.75 498 T
3 F
(\245) 72 478 T
1 F
(Allocation group size \050in lbsz\051) 85.75 478 T
3 F
(\245) 72 458 T
1 F
(T) 85.75 458 T
(otal \336le system data sub-volume size \050in lbsz\051) 92.23 458 T
3 F
(\245) 72 438 T
1 F
(T) 85.75 438 T
(otal \336le system unreliable sub-volume size \050in extents\051) 92.23 438 T
3 F
(\245) 72 418 T
1 F
(Logical block number of bitmap for unreliable sub-volume extents) 85.75 418 T
3 F
(\245) 72 398 T
1 F
(Logical block number of summary information for unreliable sub-volume bitmap) 85.75 398 T
3 F
(\245) 72 378 T
1 F
(T) 85.75 378 T
(otal number of allocated and free inodes) 92.23 378 T
3 F
(\245) 72 358 T
1 F
(T) 85.75 358 T
(otal number of free data sub-volume blocks) 92.23 358 T
3 F
(\245) 72 338 T
1 F
(T) 85.75 338 T
(otal number of blocks allocated as data and as metadata in the data sub-volume) 92.23 338 T
3 F
(\245) 72 318 T
1 F
(T) 85.75 318 T
(otal number of unreliable sub-volume extents free) 92.23 318 T
0.59 (The only \336elds which change during normal operation are the statistical \336elds, containing infor-) 72 292 P
-0.13 (mation used by) 72 278 P
2 F
-0.13 (df) 147.9 278 P
1 F
-0.13 (. Changes to this information must be logged, to keep the \336le system consistent,) 158.56 278 P
0.83 (if the information is trusted across reboots. Alternatively) 72 264 P
0.83 (, the information could be computed at) 348.83 264 P
0.27 (mount time, and never written to disk at all \050except possibly at unmount time\051. This would avoid) 72 250 P
0.19 (the overhead of logging changes to the superblock at the cost of scanning all the allocation struc-) 72 236 P
0.5 (tures of the \336le system at mount time. The current plan is to avoid the mount-time scan, and log) 72 222 P
(the superblock changes.) 72 208 T
1.42 (The \336le system size and total \336elds also change when the \336le system is re-sized dynamically;) 72 182 P
(these changes must be logged.) 72 168 T
-0.03 (T) 72 142 P
-0.03 (o promote resilience to faults, it is necessary to have multiple copies of the super block informa-) 78.49 142 P
0.31 (tion that allows us to \336nd the rest of the \336le system. W) 72 128 P
0.31 (e will put a copy of the superblock as it is) 336.99 128 P
(initially formed with each allocation group, and at the end of the \336le system.) 72 114 T
FMENDPAGE
%%EndPage: "3" 4
%%Page: "4" 4
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(xFS Space Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(4) 500 42.62 T
2 14 Q
(3.2 Allocation gr) 72 710.67 T
(oup header) 174.35 710.67 T
1 12 Q
-0.1 (Each \336le system data sub-volume is divided into allocation groups, each \050except possibly the last\051) 72 684 P
-0.21 (having the same size. The size is chosen at the time the \336le system is created. The size chosen will) 72 670 P
0.4 (be in the range of 16MB to 1GB, with the default size being the total \336le system size divided by) 72 656 P
0.02 (eight; subject to the overriding minimum allocation group size, there shall be a minimum of eight) 72 642 P
0.49 (allocation groups. There may also be some rounding done to the allocation group size, details to) 72 628 P
(be \336gured out.) 72 614 T
1.55 (The primary reason to divide a \336le system into allocation groups is to promote parallelism in) 72 588 P
0.64 (space allocation in the \336le system: locking on allocation information can be done separately per) 72 574 P
0.64 (allocation group. This allows improved performance, especially in a multiprocessor) 72 560 P
0.64 (. The alloca-) 478.45 560 P
0.56 (tion groups are made a uniform size to make it easier to \336nd them in the event of an unreadable) 72 546 P
-0.11 (block; if the allocation groups were of a variable size, then either each one would have to be read-) 72 532 P
0.65 (able to \336gure out where the next one was, or there would need to be an index containing all the) 72 518 P
(allocation group addresses.) 72 504 T
0.67 (Each allocation group is composed of: a superblock \050only the \336rst one gets values updated after) 72 478 P
0.33 (\336le system creation time\051, at location 0 bytes; an allocation group header \050\336t into the \336rst logical) 72 464 P
1.39 (block along with the superblock data\051; and a bunch of data pointed at by the allocation group) 72 450 P
2.02 (header) 72 436 P
2.02 (. All the \322pointers\323 in the \336le system metadata are 64-bit logical block numbers, with) 103.3 436 P
(exceptions noted below being 32-bit block numbers relative to the start of the allocation group.) 72 422 T
(The following \336elds are present in the allocation group header:) 72 396 T
3 F
(\245) 72 376 T
1 F
(Allocation group header magic number \050for checking\051) 85.75 376 T
3 F
(\245) 72 356 T
1 F
(Allocation group header version number) 85.75 356 T
3 F
(\245) 72 336 T
1 F
(Allocation group sequence number \050for checking\051, starting from 0) 85.75 336 T
3 F
(\245) 72 316 T
1 F
0.22 (If the bitmap allocation scheme is used, the location \050relative block number\051 and size \050lbsz\051 of) 85.75 316 P
(the free block bitmap [see section) 85.75 302 T
(3.3,) 250.29 302 T
(\322Data block freelist\323] and summary information.) 271.28 302 T
3 F
(\245) 72 282 T
1 F
0.14 (If the two B-tree allocation scheme is used, the location \050relative block number\051 of each of the) 85.75 282 P
-0.08 (B-tree roots. W) 85.75 268 P
-0.08 (e might choose to \336t one or both roots into the allocation group header) 158.91 268 P
-0.08 (\325) 496.43 268 P
-0.08 (s logical) 499.77 268 P
(block.) 85.75 254 T
3 F
(\245) 72 234 T
1 F
1.61 (Location \050relative block number\051 of the \322inode\323 which contains the inode table; this might) 85.75 234 P
(instead be stored next to the allocation group header [see section) 85.75 220 T
(3.4,) 398.52 220 T
(\322Inode table\323]) 419.51 220 T
-0.2 (The number of free and allocated blocks and inodes could be maintained per allocation group. For) 72 194 P
0.48 (accuracy the changes would need to be logged, implying extra log activity not otherwise needed) 72 180 P
-0.2 (to log the allocation group header) 72 166 P
-0.2 (. Instead, this information will be present only in the superblock,) 231.88 166 P
0.12 (which is suf) 72 152 P
0.12 (\336cient for) 129.98 152 P
2 F
0.12 (df) 180.18 152 P
1 F
0.12 (\325) 191.5 152 P
0.12 (s purposes. Alternatively) 194.84 152 P
0.12 (, the information could be ignored on disk, and) 313.88 152 P
-0.06 (only used in memory) 72 138 P
-0.06 (. Further discussion of in-core structures is left for later in the document. For) 172.66 138 P
(now we assume that per) 72 124 T
(-allocation group information for) 187.01 124 T
2 F
(df) 348.89 124 T
1 F
( is not stored on disk.) 359.55 124 T
FMENDPAGE
%%EndPage: "4" 5
%%Page: "5" 5
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(xFS Space Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(5) 500 42.62 T
2 14 Q
(3.3 Data block fr) 72 710.67 T
(eelist) 175.51 710.67 T
1 12 Q
1.64 (There are two basic schemes under consideration for data block allocation. In both cases, the) 72 684 P
0.35 (designs do not keep any information in kernel memory) 72 670 P
0.35 (, just in buf) 337.19 670 P
0.35 (fers. That is, all information is) 392.67 670 P
-0.23 (read from and written to disk, and all changes are logged. This makes the designs scale better with) 72 656 P
(respect to memory usage than designs which gobble up some memory per allocation group.) 72 642 T
0.94 (In the \336rst scheme, a bitmap covers all the logical blocks in the allocation group, including the) 72 616 P
1.26 (header information and the bitmap itself. The bitmap is a single extent of logical blocks taken) 72 602 P
0.82 (from inside the allocation group\325) 72 588 P
0.82 (s blocks. The bitmap moves only if the \336le system is extended) 232.51 588 P
-0.02 (\050for the old last allocation group of the \336le system\051 or shrunk \050for the new last allocation group of) 72 574 P
-0.17 (the \336le system\051. Bits in the bitmap are set for free blocks, clear for allocated blocks. T) 72 560 P
-0.17 (o avoid hav-) 480.39 560 P
0.39 (ing to scan the entire bitmap to \336nd free extents of a given size, additional information is stored.) 72 546 P
0.22 (For each block of the bitmap, for each possible extent size in the allocation group that is a power) 72 532 P
1.25 (of two \0502) 72 518 P
1 10 Q
1.04 (k) 118.47 522.8 P
1 12 Q
1.25 (\051, we keep a count of the number of free extents of size 2) 123.47 518 P
1 10 Q
1.04 (k) 412.84 522.8 P
1 12 Q
1.25 ( to 2) 417.83 518 P
1 10 Q
1.04 (k+1) 441.66 522.8 P
1 12 Q
1.25 (-1 starting in the) 457.29 518 P
0.67 (block. The \322blocks\323 are \336le system logical blocks. This information occupies a variable amount) 72 504 P
-0.27 (of space depending on the allocation group and logical block size of the \336le system; worst case for) 72 490 P
0.2 (512 byte blocks and 1GB allocation groups is 21KB. For 4KB blocks and 1GB allocation groups) 72 476 P
1 (the size of the information is 288 bytes \050assuming that 4KB is taken as the bitmap block size\051.) 72 462 P
-0.23 (Each count entry is 16 bits. The information is ordered so that all entries related to a given size are) 72 448 P
0.6 (together) 72 434 P
0.6 (. These entries are searched to \336nd a bitmap block that must describe a free extent lar) 110.64 434 P
0.6 (ge) 528.68 434 P
0.37 (enough to satisfy our request. Then the bitmap block is searched to \336nd the starting location; the) 72 420 P
-0.25 (search must be successful. A slight alteration of this scheme restricts each count to cover only free) 72 406 P
(sections inside a single bitmap block; one scheme will be chosen depending on performance.) 72 392 T
0.1 (In the second scheme, the allocation information is kept in a pair of B-trees. Both B-trees contain) 72 366 P
1.2 (as data the pairs \050starting free block, free block count\051 for all the free extents in the allocation) 72 352 P
-0.13 (group. One B-tree is indexed by the starting free block, the other by the free block count \050and sec-) 72 338 P
-0.1 (ondarily by the starting free block, to make the keys unique\051. Block allocations \336rst search one B-) 72 324 P
0.27 (tree and then update both B-trees in the buf) 72 310 P
0.27 (fer cache \050and log the changes\051. Once the log entry is) 281.82 310 P
0.62 (made, the B-tree buf) 72 296 P
0.62 (fers can be released to be written to disk when practical. Assuming that the) 172.23 296 P
1.84 (buf) 72 282 P
1.84 (fer cache implements basically an LRU scheme for metadata, this means that only blocks) 87.77 282 P
(which are actually being referenced will be in memory) 72 268 T
(.) 333.67 268 T
0.5 (The current belief is that scheme one will be implemented \336rst, but both schemes will be imple-) 72 242 P
1.09 (mented eventually) 72 228 P
1.09 (. Performance analysis will show us whether both schemes must be retained,) 160.58 228 P
(and under what circumstances one outperforms the other) 72 214 T
(.) 343.46 214 T
2 14 Q
(3.4 Inode table) 72 180.67 T
1 12 Q
0.13 (W) 72 154 P
0.13 (e all dislike the old \050UFS, EFS\051 scheme of having all the inodes in the allocation group be con-) 82.36 154 P
0.36 (tiguously \050and statically\051 allocated. Therefore, xFS uses a scheme where the inodes are allocated) 72 140 P
1.15 (on-demand, in small groups. This implies either that the inodes are stored in a single variable-) 72 126 P
1.15 (sized extent, or that there is a high-level index pointing to chunks of inodes. The single-extent) 72 112 P
1.23 (scheme is simple but prone to failure of allocation if the \336le system is fragmented, so we will) 72 98 P
0.25 (ignore it. An index scheme could work in one of two general ways: either with \336xed-size chunks) 72 84 P
1.24 (of inodes and a single-extent index, or with a B-tree \050or a sequence of extent pointers\051 for the) 72 70 P
FMENDPAGE
%%EndPage: "5" 6
%%Page: "6" 6
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(xFS Space Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(6) 500 42.62 T
1 12 Q
1.64 (inode \322\336le\323 as is done for regular \336les \050see section) 72 712 P
1.64 (3.7,) 331.93 712 P
1.64 (\322Data and Attribute block representa-) 352.92 712 P
(tion\323\051. W) 72 698 T
(e have chosen the latter method.) 116.34 698 T
1.11 (Each allocation group header contains the root of a B-tree representing the inode space and an) 72 672 P
0.45 (inode number: the B-tree represents a \322\336le\323 which contains all the inode space for the allocation) 72 658 P
0.02 (group, and the inode number refers to the \336rst inode in the inode free list for the allocation group.) 72 644 P
0.8 (Inodes on the inode free list are linked together \050by inode number\051 through a \336eld in the inode.) 72 630 P
-0.07 (The \322\336le\323 containing the inodes is extended when necessary) 72 616 P
-0.07 (, with preallocation when possible: as) 359.79 616 P
0.69 (is done for any other \336le, an attempt will be made to extend the inode table contiguously) 72 602 P
0.69 (. Note,) 507 602 P
0.09 (however) 72 588 P
0.09 (, that sequential access to the inode table is rare, so its performance is not that important;) 112.81 588 P
-0.24 (the real reason for keeping the number of extents of the inode table small is to keep the B-tree rep-) 72 574 P
(resenting it \337atter) 72 560 T
(.) 155.95 560 T
1.31 (The B-tree entries contain the low 32 bits of the inode number for the \336rst inode in the inode) 72 534 P
0.59 (extent \050see section) 72 520 P
0.59 (3.5,) 164.77 520 P
0.59 (\322Inode numbers\323\051, the number of inodes in the extent \050always a multiple) 185.76 520 P
0.73 (of the number of inodes in a block\051, and the relative \050to the allocation group header\051 disk block) 72 506 P
-0.23 (number of the start of the extent. The B-tree is indexed by the inode number \336eld. This is dif) 72 492 P
-0.23 (ferent) 512.03 492 P
0.46 (from the B-tree used for the bmap function only in the units and the sizes of the \336elds; the algo-) 72 478 P
(rithms will be the same.) 72 464 T
0.46 (The issue of having an inode bitmap vs. having a freelist are really an independent dimension in) 72 438 P
1.18 (the comparison of inode management schemes. In the bitmap case, allocation and freeing both) 72 424 P
0.62 (require changing the inode and the bitmap word. In the freelist case, allocation and freeing both) 72 410 P
1.38 (require changing the allocation group header and the inode. The freelist case may require less) 72 396 P
0.49 (overall storage, since the freelist pointers are stored in the inodes. Theoretically) 72 382 P
0.49 (, the freelist case) 457.95 382 P
-0.29 (allows less parallelism than the bitmap case, since the bitmap is broken into pieces which could be) 72 368 P
0.53 (locked independently) 72 354 P
0.53 (. In practice, this does not appear to be a signi\336cant restriction, since inode) 174.68 354 P
-0.05 (allocations can proceed in parallel in each allocation group. The bitmap case allows for allocating) 72 340 P
-0.29 (inodes near each other more easily; it\325) 72 326 P
-0.29 (s not clear how important this is. Therefore we have decided) 252.79 326 P
(to go with the inode freelist scheme for xFS.) 72 312 T
1.33 (If we decided to use a bitmap scheme instead of a freelist, the most likely design is to scatter) 72 286 P
0.81 (inode-sized chunks of the free inode bitmap at the appropriate interval through the inode \322\336le\323.) 72 272 P
0.1 (For instance, if the inode size is 256 bytes, then at 256 * 8 = 2048 inode intervals, the data at that) 72 258 P
0.08 (of) 72 244 P
0.08 (fset in the inode \322\336le\323 would be a piece of bitmap instead of an inode. Thus to \336nd a free inode) 81.78 244 P
-0.26 (\322near\323 an allocated one, calculate and read the appropriate bitmap block, and look nearby the allo-) 72 230 P
(cated inode\325) 72 216 T
(s bit position.) 130.29 216 T
0.58 (Another possible design is to have an independent set of extents for the bitmap. Then the whole) 72 190 P
0.35 (set of issues about dealing with arbitrary sized bitmaps arises; it might be practical to restrict the) 72 176 P
-0.26 (bitmap to be a small number of extents, either \336xed or variable sized. In any case, more disk I/O is) 72 162 P
-0.29 (required to manipulate the bitmap unless it\325) 72 148 P
-0.29 (s trivial to \336nd the right bitmap block. The other disad-) 278.77 148 P
0.28 (vantage of an unadorned bitmap vs. a freelist, is that it\325) 72 134 P
0.28 (s harder to \336nd a free inode in the normal) 338.62 134 P
(case, when most inodes are allocated.) 72 120 T
FMENDPAGE
%%EndPage: "6" 7
%%Page: "7" 7
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(xFS Space Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(7) 500 42.62 T
2 14 Q
(3.5 Inode numbers) 72 710.67 T
1 12 Q
0.54 (Inodes contain the information de\336ning each \336le, directory) 72 684 P
0.54 (, etc. in the \336le system. Each inode is) 357.46 684 P
0.39 (named by its inode number) 72 670 P
0.39 (, or inumber) 203.66 670 P
0.39 (. Inodes are numbered sequentially through the entire \336le) 262.74 670 P
1.77 (system in traditional UNIX \336le systems. In such a \336le system, there are the same number of) 72 656 P
-0.15 (inodes in each allocation group \050cylinder group\051, and so there is no dif) 72 642 P
-0.15 (\336culty in locating a particu-) 407.37 642 P
0.04 (lar inode. In xFS, there is a variable number of inodes in each allocation group, and so having the) 72 628 P
1.04 (traditional numbering scheme would mean that there would be great dif) 72 614 P
1.04 (\336culty in translating an) 425.94 614 P
(inumber to an inode disk address.) 72 600 T
0.29 (The inode number in xFS is divided into two bit\336elds. The more signi\336cant bit\336eld is the alloca-) 72 574 P
0.92 (tion group number) 72 560 P
0.92 (, the less signi\336cant is the inode number within the allocation group. For the) 162.63 560 P
0.19 (moment, the two bit\336elds are each 32 bits, and the inumber is thus a 64 bit integer) 72 546 P
0.19 (. The dif) 468.2 546 P
0.19 (\336culty) 509.35 546 P
-0.03 (with dividing up a 32 bit integer into allocation group number and inode number is the possibility) 72 532 P
0.45 (of making a \336le system lar) 72 518 P
0.45 (ge enough that one or the other would run out of space in the bit\336eld.) 201.61 518 P
0.2 (Since we want this \336le system design to be good for ten years or so, we will choose to spend this) 72 504 P
(space in the disk format now) 72 490 T
(.) 209.46 490 T
2 14 Q
(3.6 Inode disk format) 72 456.67 T
1 12 Q
0.39 (The bulk of the design for the inode disk format is in the Directory Manager and Attribute Man-) 72 430 P
(ager design documents. The issues to be addressed by the Space Manager design are:) 72 416 T
3 F
(\245) 72 396 T
1 F
(How \336elds in the inode describe the space allocated for the \050parts of the\051 \336le) 85.75 396 T
3 F
(\245) 72 376 T
1 F
1.37 (The size of the inode, in particular the size of the area dedicated to holding small \336les and) 85.75 376 P
(small attribute areas) 85.75 362 T
0.98 (Each \336le has two address spaces, one for data and one for attributes. The sizes of the two byte) 72 336 P
0.14 (streams are arbitrary and independent from each other) 72 322 P
0.14 (. The inode has to contain enough informa-) 331.8 322 P
0.06 (tion to \336nd both byte streams. W) 72 308 P
0.06 (e want \322short\323 \336les and attribute sections to \336t completely inside) 228.96 308 P
0.39 (the inode, in the space where the block pointers would be for a longer \336le. This gives us a lower) 72 294 P
0.47 (bound on the space taken up by those pointers. For symbolic links, the maximum length is 1024) 72 280 P
0.19 (bytes; a typical length is more like 100 to 200 bytes for a long symlink. The other major \336le type) 72 266 P
0 (that might easily \336t is a directory) 72 252 P
0 (. It would be nice if a directory with a few short entries would \336t) 229.82 252 P
0.44 (in the inode. One reason to keep in mind, that symbolic links and directories are more important) 72 238 P
(here than regular \336les, is that they are accessed through special calls, not by read/write/mmap.) 72 224 T
0.7 (A total inode size of 512 bytes gives us about 450 bytes of storage, enough to satisfy the above) 72 198 P
-0.23 (pretty well, assuming that the attributes use negligible space. Going to 1024 bytes starts to waste a) 72 184 P
0.08 (lot of storage, unless the attributes are several hundred bytes long on average. Most \336les in a nor-) 72 170 P
0.27 (mal \336le system will be in one extent, and need very little space to represent their storage. Setting) 72 156 P
0.92 (the size to 256 bytes will give us around 200 bytes of storage, which is enough for many sym-) 72 142 P
-0.13 (links, and even some directories. For now we will assert that the size is selected at \336le system cre-) 72 128 P
(ation time, and is allowed to vary between \336le systems.) 72 114 T
0.85 (For the moment we will assume simply that a moderate-sized undif) 72 88 P
0.85 (ferentiated block of bytes is) 403.38 88 P
0.67 (available to the Space Manager in each inode. It was not an absolute requirement that the inode) 72 74 P
FMENDPAGE
%%EndPage: "7" 8
%%Page: "8" 8
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(xFS Space Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(8) 500 42.62 T
1 12 Q
0.08 (size be a power of 2, but it does make everything go faster) 72 712 P
0.08 (. Since we have a use for the space, we) 352.43 712 P
(can pad the inode size to be a power of 2 easily) 72 698 T
(.) 298.04 698 T
0.75 (W) 72 672 P
0.75 (e will assume that the inode contains \337ags which tell the Space Manager the current usage of) 82.36 672 P
0.68 (the block of bytes. W) 72 658 P
0.68 (e need the following information: size of the data section \050implies the size) 176.7 658 P
1.11 (and starting of) 72 644 P
1.11 (fset of the attribute section\051; \337ags for each section giving its representation. The) 143.29 644 P
0.64 (representation values are: is contained in the inode; is pointed to by direct extent pointers in the) 72 630 P
-0.26 (inode; the root of a B-tree which points to the \336les extents is contained in the inode. Possible addi-) 72 616 P
1.64 (tional representation values, should we wish to make one section small, are: inode contains a) 72 602 P
0.57 (block number) 72 588 P
0.57 (, where the block contains either the direct pointers or the B-tree root. W) 138.38 588 P
0.57 (e will not) 493.55 588 P
0.17 (necessarily implement all the possible representations, at \336rst, or ever) 72 574 P
0.17 (. See section) 406.94 574 P
0.17 (3.7,) 470.56 574 P
0.17 (\322Data and) 491.55 574 P
(Attribute block representation\323.) 72 560 T
-0.23 (The split between data and attribute space, in the initial implementation, will want to be done sim-) 72 534 P
0.85 (ply) 72 520 P
0.85 (, but could become more complex and dynamic in later releases. One possibility for the \336rst) 86.55 520 P
-0.3 (implementation is to split the space 50/50 between the two, then apply the \322does it \336t in the space\323) 72 506 P
0.5 (algorithm to each independently to determine which representation to use. Another possibility is) 72 492 P
0.67 (to place a block pointer for direct pointers to the attribute space \050or the root of its B-tree\051 in the) 72 478 P
0.48 (inode \050i.e., make it small and \336xed size, and use the rest of the space for the data block or its B-) 72 464 P
1.67 (tree root\051. The scheme can be more dynamic, at the cost of a more complex implementation,) 72 450 P
(allowing an arbitrary split between the spaces which changes over time.) 72 436 T
1.2 (The dynamic scheme in the design at the moment is as follows. Each of the data and attribute) 72 410 P
1.3 (areas have a minimum number of bytes reserved for them in every inode, namely) 72 396 P
1.3 (, the amount) 477.77 396 P
0.07 (needed to represent the data or attributes indirectly \050a small B-tree root\051. The free space, if any) 72 382 P
0.07 (, is) 525.93 382 P
0.8 (left between the data and attribute information. The Space Manager block mapping routine will) 72 368 P
0.67 (never be called on data or attributes whose representation is \322contained in the inode\323; the upper) 72 354 P
0.92 (layer code is responsible for I/O to those bytes. If the data or attributes are being extended and) 72 340 P
(will not \336t with the current representation, one of two things happen:) 72 326 T
(1.) 72 306 T
(If data is growing, and the data would \336t if the attributes occupied their minimum space, then) 85.75 306 T
(the upper layer calls the attribute layer to remove its direct data from the inode and make it) 85.75 292 T
(direct. The upper data layer then moves its new data into the vacated space.) 85.75 278 T
(2.) 72 258 T
(Otherwise, the growing section won\325) 85.75 258 T
(t \336t. It must kick itself out of the inode. For data, this) 263.07 258 T
(means calling the Space Manager to bmap the block of data \050which will make a B-tree or indi-) 85.75 244 T
(rect representation\051 then putting the data there \050in one log operation\051. For some kinds of data) 85.75 230 T
(\050e.g. directories, attributes\051 this may mean a format change, as well: the data representation is) 85.75 216 T
(block-structured.) 85.75 202 T
2 14 Q
(3.7 Data and Attribute block r) 72 168.67 T
(epr) 256.36 168.67 T
(esentation) 276.32 168.67 T
1 12 Q
0.12 (The mapping from the address spaces of a \336le to disk blocks in the volume is implemented either) 72 142 P
0.39 (by a B-tree or by a set of extent descriptors. For the B-tree case, the information in each node of) 72 128 P
0.58 (the tree is \050starting \336le of) 72 114 P
0.58 (fset [in logical blocks], starting volume block number) 195.59 114 P
0.58 (, length of extent) 456.99 114 P
0.55 ([in logical blocks]\051. The B-tree is keyed on the starting \336le of) 72 100 P
0.55 (fset \336eld. The root block of the B-) 372.27 100 P
-0.11 (tree is stored in the inode; this means that the root block is a dif) 72 86 P
-0.11 (ferent size than the other blocks of) 374.77 86 P
(the B-tree, which are of the logical block size of the \336le system.) 72 72 T
FMENDPAGE
%%EndPage: "8" 9
%%Page: "9" 9
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(xFS Space Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(9) 500 42.62 T
1 12 Q
0.51 (The B-tree is composed of \050potentially\051 multiple levels. At each level except the root level there) 72 712 P
0.06 (are multiple blocks. Each nonleaf block contains keys \050the starting \336le of) 72 698 P
0.06 (fset values\051 and pointers) 422.9 698 P
0.96 (to other blocks; each leaf node contains only nodes \050as above\051. The keys and pointers alternate) 72 684 P
0.56 (\050logically\051 in each block; when a pointer lies between two keys, the data \050starting \336le of) 72 670 P
0.56 (fsets\051 in) 501.14 670 P
0.22 (the block pointed to by the pointer lies between the two keys\325 values. Each block has) 72 656 P
4 F
0.22 (K) 486.26 656 P
1 F
0.22 (keys and) 497.48 656 P
4 F
0.4 (K+) 72 642 P
1 F
0.4 (1 pointers. When a block becomes full and an insertion is necessary) 88.1 642 P
0.4 (, one of two operations is) 416.77 642 P
-0.19 (performed. First, a rotation is attempted. Rotation attempts to move over\337ow nodes to both neigh-) 72 628 P
-0.2 (boring blocks. If both neighboring blocks are full, then the block is split: half of the information is) 72 614 P
0.8 (moved to a new block, and the parent block points to two blocks instead of one. [Alternatively) 72 600 P
0.8 (,) 537 600 P
-0.14 (two blocks can be split producing three new blocks. This keeps the tree bushier) 72 586 P
-0.14 (.] The procedure is) 449.85 586 P
0.24 (followed recursively until the root is reached or there is room for the new information in the par-) 72 572 P
-0.25 (ent block. Deletion operations do essentially the opposite work if the remaining blocks are not full) 72 558 P
0.15 (enough. Search operations \336nd the nearest lower or equal block number in the tree, then check to) 72 544 P
(see if the block requested exists.) 72 530 T
0 (For the extent descriptor case, we will have a pair of arrays: one of extent sizes \050lbsz, 32 bits\051 and) 72 504 P
0.53 (one of pointers to extents \05064 bit volume block numbers\051. If there is a hole in the \336le it is repre-) 72 490 P
0.1 (sented by a 0 extent pointer) 72 476 P
0.1 (. This scheme can be used for all \336les with a small number of extents.) 204.1 476 P
0.15 (The scheme requires a linear search through the array to \336nd a particular block, since the \336le of) 72 462 P
0.15 (f-) 532.01 462 P
0.99 (set information is implied by the cumulative sizes. As an alternative, the \336le of) 72 448 P
0.99 (fset \050another 64) 462.75 448 P
1.49 (bits\051 could be stored as well, and we could leave out the zero-pointers for holes in \336les. This) 72 434 P
0.8 (would mean that binary search was possible; on the other hand, fewer descriptors would \336t, for) 72 420 P
0.05 (the normal case where the \336les do not have holes. This information is stored in the inode directly) 72 406 P
0.05 (.) 537 406 P
1.03 (T) 72 392 P
1.03 (o compress this information down to 128 bits the information can be stored as 21 bits for the) 78.49 392 P
(size, 52 bits for the volume block number) 72 378 T
(, and 55 bits for the \336le block number \050for instance\051.) 271.39 378 T
(The extent descriptor method is used unless that representation does not \336t in the inode.) 72 352 T
2 14 Q
(3.8 Unr) 72 318.67 T
(eliable Sub-V) 120.33 318.67 T
(olume Space Management) 199.51 318.67 T
1 12 Q
0.12 (The unreliable sub-volume is divided into a number of \336xed-size pieces. The size is a multiple of) 72 292 P
1.96 (the \336le system block size, and is set at mkfs time, and stored in the superblock. The size is) 72 278 P
0.33 (expected to be relatively lar) 72 264 P
0.33 (ge, say 1Mbyte or so. Free space in this sub-volume can therefore be) 206.32 264 P
0.25 (represented by a simple bitmap. The bitmap must be reliable and so is stored in the data sub-vol-) 72 250 P
0.81 (ume; the superblock points to it. In order to speed allocation further) 72 236 P
0.81 (, a count is kept per bitmap) 404.89 236 P
0.58 (block, of the number of bits set. This set of counts is saved as an extent in the data sub-volume,) 72 222 P
(and also pointed to by the superblock.) 72 208 T
2 16 Q
(4.0 Internal Components and Interfaces) 72 167.33 T
3 12 Q
(\245) 72 144 T
1 F
(Allocation Group Manager \050includes allocation group selection for \336le and directory creation\051) 85.75 144 T
3 F
(\245) 72 124 T
1 F
-0.26 (Block and Extent Allocator \050for freespace within an allocation group, or the unreliable sub-vol-) 85.75 124 P
0.21 (ume\051; space may be allocated anywhere in the object, or near a particular block, or at an exact) 85.75 110 P
(location) 85.75 96 T
3 F
(\245) 72 76 T
1 F
(Inode Allocator \050allocation group speci\336ed or arbitrary\051) 85.75 76 T
FMENDPAGE
%%EndPage: "9" 10
%%Page: "10" 10
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(xFS Space Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(10) 496 42.62 T
3 12 Q
(\245) 72 712 T
1 F
(File Space Manager \050includes bmap routine\051) 85.75 712 T
3 F
(\245) 72 692 T
1 F
(Statistics Management \050includes VFS_ST) 85.75 692 T
(A) 285.67 692 T
(TVFS and performance monitoring\051) 293 692 T
3 F
(\245) 72 672 T
1 F
(Reor) 85.75 672 T
(ganizer Interfaces) 108.84 672 T
3 F
(\245) 72 652 T
1 F
(Interfaces out to Log Manager) 85.75 652 T
2 16 Q
(5.0 Internal Data Structur) 72 611.33 T
(es and Algorithms) 255.15 611.33 T
2 14 Q
(5.1 File System Structur) 72 576.67 T
(e) 219.82 576.67 T
1 12 Q
1.45 (For each mounted \336le system there is an incore \050allocated\051 structure containing or pointing to) 72 550 P
0.12 (information pertaining to the \336le system, the) 72 536 P
4 F
0.12 (vfs) 289.35 536 P
1 F
0.12 ( structure. This structure includes a \336eld) 302.68 536 P
4 F
0.12 (vfs_data) 499.35 536 P
1 F
0.39 (which is private data for the \336le system implementation. As is done for EFS, this \336eld will point) 72 522 P
0.49 (to a structure \050) 72 508 P
4 F
0.49 (xfs_mount) 143.08 508 P
1 F
0.49 ( for xFS,) 192.39 508 P
4 F
0.49 (mount) 239.17 508 P
1 F
0.49 ( for EFS\051 which contains some per) 269.16 508 P
0.49 (-\336le system informa-) 438.42 508 P
(tion. Included in the) 72 494 T
4 F
(xfs_mount) 171.6 494 T
1 F
( structure will be the following information:) 220.91 494 T
3 F
(\245) 72 474 T
1 F
(pointer back to the vfs structure) 85.75 474 T
3 F
(\245) 72 454 T
1 F
(vnode pointer for the block device for the data region of the volume) 85.75 454 T
3 F
(\245) 72 434 T
1 F
(vnode pointer for the block device for the log region of the volume) 85.75 434 T
3 F
(\245) 72 414 T
1 F
(inode pointer to the incore root inode of the \336le system) 85.75 414 T
3 F
(\245) 72 394 T
1 F
(pointer to the list of incore inodes for the \336le system) 85.75 394 T
3 F
(\245) 72 374 T
1 F
(some \336elds for quotas; in EFS there are \337ags, an inode pointer) 85.75 374 T
(, and a size) 384.4 374 T
3 F
(\245) 72 354 T
1 F
(some statistics for our own use in tuning the implementation) 85.75 354 T
3 F
(\245) 72 334 T
1 F
(a copy of the superblock structure) 85.75 334 T
3 F
(\245) 72 314 T
1 F
(an array of short structures, one per allocation group \050struct) 85.75 314 T
4 F
(cg) 373.85 314 T
1 F
( in EFS\051) 385.17 314 T
2 14 Q
(5.2 Buffering vs. Allocation) 72 280.67 T
1 12 Q
0.26 (The critical data structures where there is some question about incore \050allocated\051 vs. buf) 72 254 P
0.26 (fered are) 497.46 254 P
1.17 (inodes and data and inode allocation bitmaps \050or alternate data structures\051. For inodes, there is) 72 240 P
1.12 (certainly a precedent for caching them incore, into a \336xed-size pool of incore inode structures.) 72 226 P
0.38 (The incore inodes contain an ondisk inode as well as pointers and other information. The alloca-) 72 212 P
-0.1 (tion strategy for this inode pool must be examined. The next question for inodes is whether the B-) 72 198 P
-0.01 (tree representing the \336le\325) 72 184 P
-0.01 (s on-disk structure is pulled into memory or pulled on-demand into buf) 191.54 184 P
-0.01 (f-) 532.01 184 P
(ers. T) 72 170 T
(o allow support of very lar) 98.47 170 T
(ge \336les, this will need to use buf) 225.83 170 T
(fers.) 380.85 170 T
-0.01 (The free data block bitmaps \050or B-trees\051 are potentially very lar) 72 144 P
-0.01 (ge, indicating the use of buf) 376.08 144 P
-0.01 (fers to) 509.7 144 P
-0.25 (reference them. W) 72 130 P
-0.25 (e do not believe we can af) 159.45 130 P
-0.25 (ford to copy these into allocated memory for lar) 282.97 130 P
-0.25 (ge \336le) 510.6 130 P
(systems.) 72 116 T
FMENDPAGE
%%EndPage: "10" 11
%%Page: "11" 11
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(xFS Space Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(1) 496.44 42.62 T
(1) 500 42.62 T
1 12 Q
1.23 (The inode allocation structures, while not as lar) 72 712 P
1.23 (ge, can probably be buf) 308.23 712 P
1.23 (fered as well without a) 425.83 712 P
1 (substantial loss in performance. This assumption must be checked against the real implementa-) 72 698 P
(tion, though.) 72 684 T
2 14 Q
(5.3 File Contiguity) 72 650.67 T
1 12 Q
0.46 (One very important algorithm remains to be designed: how \336le contiguity is achieved. As this is) 72 624 P
0.7 (purely a performance matter) 72 610 P
0.7 (, the implementation \050whatever it is\051 can be left until the rest of the) 209.82 610 P
1.57 (\336le system implementation is functional. However) 72 596 P
1.57 (, the performance of the \336le system will be) 321.9 596 P
(truly awful without some attention paid to this problem.) 72 582 T
0.74 (A \336rst-stage solution is equivalent to that used by EFS, approximately) 72 556 P
0.74 (. When space is allocated) 415.46 556 P
1.02 (for a \336le, extra space is allocated at the end of the extent. The space can be returned if unused) 72 542 P
(when the \336le is closed, or this can be done by an asynchronous reor) 72 528 T
(ganizer process \050) 395.55 528 T
5 F
(fsr) 476.8 528 T
1 F
(\051.) 490.13 528 T
1.09 (A second-stage solution is to delay block allocations until lar) 72 502 P
1.09 (ger groups of blocks are accumu-) 374.37 502 P
-0.05 (lated, then dump the blocks into a single extent if possible. This requires changes to VOP_BMAP) 72 488 P
0.95 (and related stuf) 72 474 P
0.95 (f. The new blocks must be reserved instead of bmap\325ed. All the blocks must be) 147.62 474 P
-0.05 (pinned in the buf) 72 460 P
-0.05 (fer cache \050they cannot be written since no block is assigned\051, with a vnode/of) 153.23 460 P
-0.05 (fset) 522.68 460 P
0.73 (assigned to them but no physical volume address. This needs more examination to see what the) 72 446 P
(actual interfaces would be.) 72 432 T
2 16 Q
(6.0 User Library and Utility Support) 72 391.33 T
3 12 Q
(\245) 72 368 T
1 F
(mkfs, extendfs, shrinkfs) 85.75 368 T
3 F
(\245) 72 348 T
1 F
(\336le system tuning \050tunefs\051) 85.75 348 T
3 F
(\245) 72 328 T
1 F
(\336le system reor) 85.75 328 T
(ganizer \050fsr\051) 159.48 328 T
3 F
(\245) 72 308 T
1 F
(\336le system internals dumping \050fsdb or equivalent\051) 85.75 308 T
3 F
(\245) 72 288 T
1 F
(\336le system repair program \050fsck equivalent\051 for disaster recovery) 85.75 288 T
3 F
(\245) 72 268 T
1 F
(library interface to determine extent structure of a \336le) 85.75 268 T
3 F
(\245) 72 248 T
1 F
1.47 (interfaces provided for reor) 85.75 248 P
1.47 (ganizer to restructure the \336le \322atomically\323; for EFS this is done) 221.49 248 P
(through the fsctl driver) 85.75 234 T
2 16 Q
(7.0 Performance Characterization) 72 193.33 T
1 12 Q
0.2 (I\325m not comfortable supplying anything here until the other sections are more \336lled in. The strat-) 72 166 P
0.02 (egy is to make performance reasonable on small \336lesystems by using simpler algorithms and rep-) 72 152 P
(resentations until more complex algorithms are actually needed.) 72 138 T
FMENDPAGE
%%EndPage: "11" 12
%%Page: "12" 12
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(xFS Space Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(12) 496 42.62 T
2 16 Q
(8.0 Implementation Plan and Schedule) 72 709.33 T
3 12 Q
(\245) 72 686 T
1 F
1.14 (Implement simpler block allocation scheme and all other basic algorithms \050inode allocation,) 85.75 686 P
(bmap\051 for the simulation version of the \336le system.) 85.75 672 T
3 F
(\245) 72 652 T
1 F
-0.09 (Implement B-tree version of block allocation, also in the simulation version. The B-tree imple-) 85.75 652 P
(mentation can improve over time if this helps get the \336le system released.) 85.75 638 T
3 F
(\245) 72 618 T
1 F
(Implement direct \050in-inode\051 \336le support.) 85.75 618 T
3 F
(\245) 72 598 T
1 F
0.56 (At some point, switch over to live kernel use. This should happen in November) 85.75 598 P
0.56 (, according to) 473.27 598 P
(the last schedule we put together) 85.75 584 T
(.) 241.98 584 T
FMENDPAGE
%%EndPage: "12" 13
%%Trailer
%%BoundingBox: 0 0 612 792
%%Pages: 12 1
%%DocumentFonts: Palatino-Roman
%%+ Times-Roman
%%+ Times-Bold
%%+ Courier-Bold
%%+ Times-Italic
%%+ Times-BoldItalic
![[BACK]](/icons/back.gif){kind=icon}
Return to space.ps CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [Development] / xfs-website.orig / design_docs / xfsdocs93_ps