%!
%%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 /Times-Italic FMFONTDEFINE
4 0 /Courier 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 NameSpace Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(1) 500 42.62 T
1 24 Q
(xFS NameSpace Manager Design) 143.79 704 T
2 12 Q
(Curtis Anderson) 263.19 664 T
134.46 632.22 72 632.22 2 L
V
1.71 H
0 Z
N
2 18 Q
(1.0 Intr) 72 634 T
201.12 632.22 134.14 632.22 2 L
V
N
(oduction) 134.14 634 T
1 12 Q
0.18 (This document describes the requirements and proposed implementation for the namespace man-) 72 612 P
0.26 (agement functions of the xFS \336lesystem. Note that only the namespace features are de\336ned here,) 72 598 P
(attribute management, space management and other features are described elsewhere.) 72 584 T
0 (The NameSpace Manager supports all the traditional name-related VNODE operations by storing) 72 566 P
2.03 (specialized structures \050a directory\051 inside the logical address space provided by a \322\336le\323. The) 72 552 P
1.44 (Space Manager provides the \322\336le\323 abstraction and allows the caller to set the inode type as it) 72 538 P
(desires.) 72 524 T
0.26 (The reader will notice the extreme similarity between the NameSpace Manager and the Attribute) 72 506 P
0.62 (Manager designs. This is intentional, they are parallel in the system architecture and will in fact) 72 492 P
(share portions of code.) 72 478 T
157.45 446.22 72 446.22 2 L
V
N
2 18 Q
(2.0 Requir) 72 448 T
352.03 446.22 157.13 446.22 2 L
V
N
(ements and Functionality) 157.13 448 T
2 14 Q
(2.1 Requir) 72 418.67 T
(ements) 134.71 418.67 T
1 12 Q
(Here are the external requirements for the namespace management code in xFS.) 72 402 T
2 F
(2.1.1 Standard VNODE Operations and Semantics) 72 382 T
1 F
0.57 (This \336lesystem has to operate in a fairly standard VFS/VNODE environment, so all the existing) 72 366 P
(namespace-related entry points and ar) 72 352 T
(guments have to be available and working.) 253.63 352 T
2 F
(2.1.2 Fast for Large and Small Dir) 72 332 T
(ectories) 247.68 332 T
1 F
0.49 (The namespace operations must be fast for any size of directory) 72 316 P
0.49 (, not just \322normal\323 sizes. One of) 382.52 316 P
(the goals of the namespace design is to ef) 72 302 T
(\336ciently support very lar) 270.97 302 T
(ge single directories.) 389.01 302 T
2 F
(2.1.3 Internationalization) 72 282 T
1 F
0.33 (It should be possible to store \336le names in an international character set, and \336le contents should) 72 266 P
(be tagged so that processes can determine the character set used inside them.) 72 252 T
2 F
(2.1.4 Location Independence \050Distributed Naming\051) 72 232 T
1 F
-0.16 (Hooks must be available to support the planned distributed \336lesystem. These will take the form of) 72 216 P
-0.13 (\322mount point\323 type inodes and possibly remote device access, but may not be available in the \336rst) 72 202 P
(release.) 72 188 T
2 F
(2.1.5 IPC Rendezvous Nodes) 72 168 T
1 F
0.29 (An inode type will be provided that is similar to named pipes or sockets. It will provide an inter-) 72 152 P
(process communication conduit that will have more capabilities that a named pipe or socket.) 72 138 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 NameSpace Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(2) 500 42.62 T
1 12 Q
0.36 (Speci\336cally) 72 712 P
0.36 (, it will be able to take part in naming operations. There will be a way for a user pro-) 127.85 712 P
0.66 (cess to ask that for any naming operations that attempt to pass through the inode, the remaining) 72 698 P
1.04 (piece of the pathname will be passed out to the process. The intent is to allow active user pro-) 72 684 P
0.76 (cesses to be full participants in the namespace. It should be very easy to build a new \336lesystem) 72 670 P
(type in user mode with these IPC nodes.) 72 656 T
(IPC nodes may not be available in the \336rst release.) 72 638 T
2 14 Q
(2.2 Functionality \050ie: NameSpace Semantics\051) 72 610.67 T
1 12 Q
2.33 (This section describes all the objects that are visible in the namespace, and their associated) 72 594 P
(semantics. The implementation of these objects is described in a following section.) 72 580 T
2 F
(2.2.1 Object T) 72 560 T
(ypes) 143.73 560 T
1 F
0.18 (This section lists the dif) 72 544 P
0.18 (ferent types of objects that exist in the namespace, and what their seman-) 187.11 544 P
(tics are.) 72 530 T
2 F
(2.2.1.1 Files, Dir) 72 510 T
(ectories, Symlinks) 155.07 510 T
1 F
0.88 (These types will have the same semantics that they do in IRIX today) 72 494 P
0.88 (. Note that directories will) 410.89 494 P
(have a dif) 72 480 T
(ferent internal structure, but that readdir\050\051 and friends will be supported.) 119.07 480 T
2 F
(2.2.1.2 Pipes, Sockets, Device Nodes) 72 460 T
1 F
1.41 (Until the distributed \336lesystem support appears, these types will have the same semantics that) 72 444 P
0.23 (they do in IRIX today) 72 430 P
0.23 (. When the distributed system support appears, these questions will need to) 177.4 430 P
(be answered:) 72 416 T
(\245 How will a pipe act if the two opening processes are on dif) 72 400 T
(ferent machines?) 361.44 400 T
0.8 (\245 What should the \322originating address\323 of a socket be if the system managing the \336lesystem is) 72 386 P
(not the system managing the process?) 108 374 T
(\245 Should we provide transparent access to devices that are attached to remote machines?) 72 360 T
2 F
(2.2.1.3 Mount Points) 72 342 T
1 F
0.14 (These are a special inode type that is just a holder for the UUID of the \336lesystem we want access) 72 326 P
0.12 (to. It is somewhat analogous to a symlink in that the UUID speci\336es where to continue pathname) 72 312 P
(resolution.) 72 298 T
0.83 (When a pathname is being resolved and one of these inodes is found in the middle of the path-) 72 280 P
0.25 (name, the \336lesystem will return a message to the upper layers of the kernel saying that pathname) 72 266 P
-0.18 (resolution should continue from the indicated point on the indicated system \050ie: whatever is left of) 72 252 P
(the pathname, on the system that is managing the indicated \336lesystem\051.) 72 238 T
0.4 (One method of multi-hop pathname resolution would have the kernel on the system that ran into) 72 220 P
0.09 (the mountpoint inode pass a message on to the kernel managing the \322next\323 \336lesystem to continue) 72 206 P
-0.25 (pathname resolution, without involving the \322originator\323 system. This has a severe drawback when) 72 192 P
(one system in that chain fails.) 72 178 T
0 (Returning a message to the originating kernel rather than just passing it along allows the originat-) 72 160 P
0.64 (ing kernel to know who is doing processing on its behalf. The originating kernel can then tell if) 72 146 P
(the remote system has gone down or is just slow) 72 132 T
(.) 303.41 132 T
1.1 (During system boot or when a fragmented network is reconnected, mountpoint inodes come in) 72 114 P
1.66 (very handy) 72 100 P
1.66 (. As soon as the volume manager has a complete image of a volume ready) 126.5 100 P
1.66 (, it can) 504.37 100 P
1.47 (invoke the \336lesystem recovery manager) 72 86 P
1.47 (. As soon as that is done, the \336lesystem UUID can be) 268.39 86 P
-0.1 (announced to the world and operations can start. Note that an administrative \322mount\323 operation is) 72 72 P
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 NameSpace Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(3) 500 42.62 T
1 12 Q
0.67 (not required. In the case of reassembling a fragmented network, this technique works especially) 72 712 P
0.38 (well, since only the fact that the \336lesystem UUIDs are now available needs to be transferred and) 72 698 P
(the whole \322fragmented\323 section of the network becomes visible again.) 72 684 T
2 F
(2.2.1.4 IPC Nodes) 72 664 T
1 F
(IPC nodes are complicated beasties. Processes attached to them can:) 72 648 T
(\245 Participate in pathname operations via passing pathname fragments in and out.) 72 632 T
1.53 (\245 Provide \322\336le descriptor\323 support in that they can respond to \336lesystem operations \050eg: read/) 72 618 P
(write/stat/etc.\051.) 108 606 T
(\245 Lots more neato things....) 72 592 T
2 F
(2.2.2 Pathnames) 72 574 T
1 F
0.94 (The pathnames that xFS will support will be 8-bit clean, and will be stored as a \050bytes, length\051) 72 558 P
0.23 (pair) 72 544 P
0.23 (, but the interface will still use NULL-terminated strings \050ie: the unicode standard will not be) 90.17 544 P
-0.23 (supported in this release\051. W) 72 530 P
-0.23 (e should plan ahead for the possibility of supporting the unicode stan-) 207.7 530 P
(dard where a NULL byte doesn\325) 72 516 T
(t terminate a string.) 227.32 516 T
0.34 (A pathname will be limited to MAXP) 72 498 P
0.34 (A) 254.16 498 P
0.34 (THLEN bytes. Note that in a multi-byte character set, the) 261.49 498 P
0.22 (number of \322characters\323 will be less than the number of bytes. This also applies to the max length) 72 484 P
(of a \336le name \050a pathname component\051.) 72 470 T
0.45 (The upper layer VFS/VNODE code will need to be able to \336nd \322/\323, and the xFS \336lesystem code) 72 452 P
0.85 (will need to be able to \336nd \322.\323 and \322..\323, but that seems to be the only characters that the kernel) 72 438 P
(needs to parse for in the pathname.) 72 424 T
2 F
(2.2.3 Mounting of Filesystems) 72 404 T
1 F
1.27 (Until the distributed \336lesystem support comes along, we may not implement mount-point type) 72 388 P
(inodes, so we will use a traditional) 72 374 T
3 F
(mount) 241.23 374 T
1 F
( command to initiate kernel activity on a \336lesystem.) 271.21 374 T
2 F
(2.2.3.1 MountPoint T) 72 354 T
(ype Inodes) 180.06 354 T
1 F
0.37 (This is an inode type that contains the UUID of the new \336lesystem, and is used something like a) 72 338 P
(traditional symlink. It provides the UUID of the \336lesystem to continue pathname resolution with.) 72 324 T
0.88 (W) 72 306 P
0.88 (e must support the library interfaces that let programs read the /etc/mtab \336le. The \336lesystems) 82.36 306 P
0.42 (that are currently mounted will depend on other nodes in the local cluster being up, and network) 72 292 P
0.14 (connections to more remote systems being up. The list of currently mounted \336lesystems could be) 72 278 P
(a fairly dynamic thing.) 72 264 T
0.49 (The /etc/mtab \336le will be managed just the way it is today by non-xFS \336lesystems, but xFS \336le-) 72 246 P
0.21 (systems will not be recorded in the /etc/mtab \336le. The library routines will present all of the non-) 72 232 P
0.61 (xFS entries in the \336le, and will then use system calls to query the kernel as to what xFS \336lesys-) 72 218 P
(tems are currently mounted.) 72 204 T
256.36 172.22 72 172.22 2 L
V
1.71 H
0 Z
N
2 18 Q
(3.0 External Interfaces) 72 174 T
1 12 Q
1.24 (Listed here are the interfaces provided to external callers, the interfaces into other kernel code) 72 152 P
(used by this module, and the dependencies that this module has on the kernel and other modules.) 72 138 T
2 14 Q
(3.1 Supported VNODE Operations) 72 110.67 T
1 12 Q
3 (The following VFS/VNODE operations will point into the NameSpace manager code. The) 72 94 P
(semantics of each call are already de\336ned.) 72 80 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 NameSpace Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(4) 500 42.62 T
1 12 Q
(\245 vop_open) 72 712 T
(\245 vop_getattr) 72 698 T
(\245 vop_setattr) 72 684 T
(\245 vop_access) 72 670 T
(\245 vop_lookup) 72 656 T
(\245 vop_create) 72 642 T
(\245 vop_remove) 72 628 T
(\245 vop_link) 72 614 T
(\245 vop_rename) 72 600 T
(\245 vop_mkdir) 72 586 T
(\245 vop_rmdir) 72 572 T
(\245 vop_readdir) 72 558 T
(\245 vop_symlink) 72 544 T
(\245 vop_readlink) 72 530 T
(\245 vop_pathconf) 72 516 T
2 14 Q
(3.2 IRIX Components Used) 72 490.67 T
1 12 Q
(Lots of them.) 72 474 T
2 14 Q
(3.3 Dependencies on Other xFS Components) 72 446.67 T
1 12 Q
0.97 (This section lists functional and algorithmic dependencies of the NameSpace manager on other) 72 430 P
0.55 (modules in xFS. The NameSpace manager should be able to get all of its work done via calls to) 72 416 P
0.3 (Space manager routines, buf) 72 402 P
0.3 (fer cache routines, and to log/recovery manager routines. It will also) 209.24 402 P
(need to interact with the Attribute Manager to manage the space inside an inode.) 72 388 T
2 F
(3.3.1 Space Manager) 72 368 T
1 F
(The NameSpace manager is intended to be layered on top of the Space manager) 72 352 T
(.) 454.7 352 T
2 F
(3.3.1.1 Manage the inode pool) 72 332 T
(3.3.1.2 Pr) 72 314 T
(ovide the bmap\050\051 r) 120.42 314 T
(outine) 215.14 314 T
(3.3.2 Log/Recovery Manager) 72 296 T
(3.3.2.1 Pr) 72 278 T
(ovide Log W) 120.42 278 T
(rite Interfaces) 185.51 278 T
(3.3.3 Attribute Manager) 72 260 T
(3.3.3.1 Pr) 72 242 T
(ovide a PushOut pr) 120.42 242 T
(ocedur) 219.83 242 T
(e) 254.92 242 T
1 F
(text goes here) 72 226 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 NameSpace Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(5) 500 42.62 T
253.88 706.22 72 706.22 2 L
V
1.71 H
0 Z
N
2 18 Q
(4.0 Major Components) 72 708 T
2 14 Q
(4.1 List of Components) 72 678.67 T
1 12 Q
(Here is a partial diagram of the NameSpace Manager components and their interactions:) 72 662 T
2.07 (\245 Short Form Directory Routines - manage an extremely compact representation of directory) 72 411 P
0.17 (entries intended to maximize the number of entries that can \336t into the literal space inside) 108 399 P
(an inode.) 108 387 T
-0.06 (\245 Leaf Node Directory Routines - manage the contents of the leaf nodes of a directory) 72 373 P
-0.06 (. Leaf nodes) 481.17 373 P
-0.08 (are used in lar) 108 361 P
-0.08 (ge directory B-trees and as a special case when the only node is a single leaf) 175.15 361 P
(node. They are indexed on a hash value computed from the \336le name.) 108 349 T
-0.02 (\245 Intermediate/Root Node Directory Routines - implement a B*-tree using a hash value computed) 72 335 P
-0.17 (from the \336le name as a key) 108 323 P
-0.17 (, using the leaf node routines de\336ned above to actually store the) 236.1 323 P
(directory entries.) 108 311 T
-0.1 (\245 IPC Nodes - implement the ability for a user process to be a full participant in namespace opera-) 72 297 P
-0.09 (tions and in \336le descriptor based I/O. Used to implement special \336lesystems in user) 108 285 P
-0.09 (-mode.) 506.36 285 P
0.92 (\245 Mount Point Nodes - used as a symbolic continuation/redirection point in the namespace of a) 72 271 P
(distributed system.) 108 259 T
2 14 Q
(4.2 Internal Interfaces) 72 233.67 T
1 12 Q
(For each of the three components of the NameSpace Manager that relate to directories:) 72 217 T
(\245 There is a) 72 201 T
3 F
(cr) 129.48 201 T
(eate) 139.03 201 T
1 F
( routine to build a new block of this type.) 159.01 201 T
(\245 There is an) 72 187 T
3 F
(addname) 135.48 187 T
1 F
( routine to add a name to a directory with this structure.) 179.45 187 T
(\245 There is a) 72 173 T
3 F
(r) 129.48 173 T
(emovename) 133.71 173 T
1 F
( routine to remove a name from a directory with this structure.) 190.32 173 T
(\245 There is a) 72 159 T
3 F
(lookup) 129.48 159 T
1 F
( routine to search for a name in a directory with this structure.) 162.13 159 T
1.22 (\245 There is a migration routine to the adjacent directory structure. For example: migrating from) 72 145 P
-0.07 (shortform to leaf node, from leaf node to full B-tree, and equivalent routines for migrating) 108 133 P
(back again.) 108 121 T
(\245 There is a) 72 107 T
3 F
(getdents) 129.48 107 T
1 F
( routine to support readdir\050\051 and friends.) 169.46 107 T
72 63 540 720 C
76.5 423 535.5 658 C
378 595 234 595 234 541 324 541 324 487 378 487 6 Y
7 X
0 K
V
0.5 H
2 Z
0 X
N
108 487 162 595 R
7 X
V
0 X
N
171 487 315 487 315 532 225 532 225 595 171 595 6 Y
7 X
V
0 X
N
121.5 523 157.5 559 R
7 X
V
1 12 Q
0 X
(Short) 121.5 551 T
(Form) 121.5 537 T
247.5 559 373.5 577 R
7 X
V
0 X
(Intermediate/Root Nodes) 247.5 569 T
211.5 496 274.5 514 R
7 X
V
0 X
(Leaf Nodes) 211.5 506 T
94.5 613 517.5 613 2 L
1 H
N
94.5 469 517.5 469 2 L
N
207 622 405 640 R
7 X
V
0 X
(VFS/VNODE NameSpace Operations) 207 632 T
216 433 396 451 R
7 X
V
0 X
(Space Manager and Buf) 216 443 T
(fer Cache) 331.35 443 T
391.5 487 445.5 595 R
7 X
V
3 H
3 X
N
454.5 487 508.5 595 R
7 X
V
3 X
N
463.5 523 499.5 568 R
7 X
V
0 X
(Mount-) 463.5 560 T
(Point) 463.5 546 T
(nodes) 463.5 532 T
400.5 532 436.5 568 R
7 X
V
0 X
(IPC) 400.5 560 T
(Nodes) 400.5 546 T
72 63 540 720 C
0 0 612 792 C
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 NameSpace Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(6) 500 42.62 T
1 12 Q
0.65 (The routines listed above are usually just wrappers that call work routines that are used in com-) 72 712 P
0.13 (mon by the various components. For example, the internal routine to add a name to a leaf node is) 72 698 P
(called by the leaf node code and by the B*-tree code when it has reached the bottom of the tree.) 72 684 T
(There may be additional special purpose routines as well as those listed above.) 72 666 T
2 14 Q
(4.3 Algorithms) 72 638.67 T
1 12 Q
(In this section pseudocode is provided for each possible operation.) 72 622 T
2 F
(4.3.0.1 vop_open, vop_lookup, vop_access, and vop_cr) 72 602 T
(eate) 348.66 602 T
4 F
(pseudocode) 72 588 T
2 F
(4.3.0.2 vop_getattr and vop_setattr) 72 570 T
4 F
(pseudocode) 72 556 T
2 F
(4.3.0.3 vop_r) 72 538 T
(emove) 137.75 538 T
4 F
(pseudocode) 72 524 T
2 F
(4.3.0.4 vop_link) 72 506 T
4 F
(pseudocode) 72 492 T
2 F
(4.3.0.5 vop_r) 72 474 T
(ename) 137.75 474 T
4 F
(pseudocode) 72 460 T
2 F
(4.3.0.6 vop_mkdir) 72 442 T
(, vop_rmdir) 163.52 442 T
(, and vop_r) 223.72 442 T
(eaddir) 281.81 442 T
4 F
(pseudocode) 72 428 T
2 F
(4.3.0.7 vop_symlink and vop_r) 72 410 T
(eadlink) 228.39 410 T
4 F
(pseudocode) 72 396 T
2 F
(4.3.0.8 vop_pathconf) 72 378 T
4 F
(pseudocode) 72 364 T
2 14 Q
(4.4 Permanent Data Structur) 72 338.67 T
(es) 245.84 338.67 T
2 12 Q
( \050ie: On-Disk\051) 257.5 338.67 T
1 F
0.89 (The Space Manager will split the on-disk inode into three pieces: the UNIX guk, the data fork,) 72 322 P
0.77 (and the attribute fork. The UNIX guk is pretty traditional, while the data and attribute fork sec-) 72 308 P
(tions both have the same structure: they will either contain extent pointers, or literal data.) 72 294 T
-0.27 (The Space Manager will make the size of the literal area of each fork known to the namespace and) 72 276 P
0.32 (attribute routines so that they can use space-ef) 72 262 P
0.32 (\336cient optimized structures when their data will \336t) 295.55 262 P
1.68 (into the inode itself, and can use time-ef) 72 248 P
1.68 (\336cient structures when their data will not \336t into the) 276.05 248 P
0.12 (inode. If the namespace code needs more space in the inode, it can call into the attribute manager) 72 234 P
0.85 (with a request that the attributes be moved out of the inode and into extents. This is covered in) 72 220 P
-0.17 (more detail in the External Interfaces sections of this document and the Attribute Manager Design) 72 206 P
(document.) 72 192 T
-0.18 (When a directory is small, it is possible to store it inside the inode in place of extent pointers. This) 72 174 P
0.07 (has a tremendous appeal in that it will save an IO at something like half of all naming operations.) 72 160 P
(Name caches will alleviate some of the cost of such IOs, at the cost of cache management.) 72 146 T
0.07 (When a directory has too many entries to \336t into an inode, there is little choice but to fall back on) 72 128 P
(the familiar scheme of creating blocks of entries stored in a structure that looks like a regular \336le.) 72 114 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 NameSpace Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(7) 500 42.62 T
2 12 Q
(4.4.1 Small Dir) 72 712 T
(ectory Support) 148.41 712 T
1 F
1.27 (W) 72 696 P
1.27 (e will use a space-ef) 82.36 696 P
1.27 (\336cient structure when we try to \336t a directory into the literal area of an) 184.47 696 P
(inode. The entries will be packed into a \337at structure and sorted.) 72 682 T
(Unlike traditional UNIX directories, when an xFS directory is in this compacted form \322.\323 and \322..\323) 72 664 T
-0.07 (will not have explicit representations. The parent directory will simply have a dedicated \336eld, and) 72 650 P
(the self-reference \322.\323 will be calculated on the \337y) 72 636 T
(.) 307.35 636 T
(The structure for small directory entries is:) 72 618 T
2 F
(4.4.2 Large Dir) 72 403 T
(ectory Support) 149.73 403 T
1 F
-0.12 (A directory that does not \336t into the literal area of an inode will be structured as a B-tree keyed on) 72 387 P
1.58 (the hash value of the \336lenames stored in that directory) 72 373 P
1.58 (. The root, intermediate nodes, and the) 345.63 373 P
0.07 (leaves of the B-tree will each be sized to exactly \336t into a \336lesystem logical block. When a single) 72 359 P
0.96 (leaf node is suf) 72 345 P
0.96 (\336cient to store the whole directory) 147.6 345 P
0.96 (, there will be no intermediate nodes, just the) 316.49 345 P
-0.27 (single leaf node. For our application, it is expected that only in rare cases will directories use more) 72 331 P
(than that a leaf node.) 72 317 T
0.8 (Note that we are using a hash value calculated from the \336lename as the key into the B-tree and) 72 299 P
(leaf blocks, not the \336lename itself.) 72 285 T
-0.06 (In the B-tree and leaf node directory format, rather than complicate the B-tree structure by having) 72 267 P
0.77 (dedicated \336elds for \322.\323 and \322..\323 as in the compact directory format, we will represent the parent) 72 253 P
(directory) 72 239 T
(, \322..\323, and the self-reference, \322.\323, with actual entries.) 114.52 239 T
0.43 (The B-tree will contain its \322data\323 \050ie: the inode number of the referenced object\051 only at the leaf) 72 221 P
0.16 (level of the tree. This is known more formally as a B*-tree \050or sometimes as a B+-tree\051. This dif-) 72 207 P
0.53 (fers from a plain B-tree in that all the keys are in the leaves, rather than spread through the tree.) 72 193 P
1.27 (Since all keys are in the leaves, the leaf nodes can be linked together to give quick sequential) 72 179 P
(access to all the keys in the tree.) 72 165 T
72 63 540 720 C
75.38 419 536.62 614 C
309.37 434 516.37 605 R
7 X
0 K
V
4 12 Q
0 X
(struct xfs_dir_shortform {) 309.37 597 T
(struct xfs_dir_sf_hdr {) 345.37 585 T
(unchar par-) 417.37 573 T
(ent[8];) 309.37 561 T
(unchar count;) 417.37 549 T
(} hdr;) 345.37 537 T
(struct xfs_dir_sf_en-) 345.37 525 T
(try {) 309.37 513 T
(unchar inum-) 417.37 501 T
(ber[8];) 309.37 489 T
(unchar) 417.37 477 T
(namelen;) 309.37 465 T
(unchar) 417.37 453 T
(name[1];) 309.37 441 T
138.37 596 246.37 605 R
7 X
V
1 F
0 X
(parent dir inumber) 138.37 597 T
201.37 497 237.37 506 R
7 X
V
0 X
(baker) 201.37 498 T
138.37 578 228.37 587 R
7 X
V
0 X
(count of entries) 138.37 579 T
93.38 434 264.37 605 R
0.5 H
2 Z
N
93.38 587 264.37 587 2 L
N
93.38 542 264.37 542 2 L
N
93.38 515 264.37 515 2 L
N
93.38 488 264.37 488 2 L
N
93.38 461 264.37 461 2 L
N
201.37 524 237.37 533 R
7 X
V
0 X
(charlie) 201.37 525 T
201.37 551 237.37 560 R
7 X
V
0 X
(able) 201.37 552 T
201.37 443 237.37 452 R
7 X
V
0 X
(delta) 201.37 444 T
201.37 470 237.37 479 R
7 X
V
0 X
(zulu) 201.37 471 T
93.38 570 264.37 570 2 L
N
111.37 524 147.37 533 R
7 X
V
0 X
(I-6546) 111.37 525 T
111.37 551 147.37 560 R
7 X
V
0 X
(I-6523) 111.37 552 T
111.37 443 147.37 452 R
7 X
V
0 X
(I-4253) 111.37 444 T
111.37 470 147.37 479 R
7 X
V
0 X
(I-9833) 111.37 471 T
111.37 497 147.37 506 R
7 X
V
0 X
(I-1263) 111.37 498 T
174.37 551 183.37 560 R
7 X
V
0 X
(4) 174.37 552 T
174.37 524 183.37 533 R
7 X
V
0 X
(7) 174.37 525 T
174.37 497 185.37 506 R
7 X
V
0 X
(5) 174.37 498 T
174.37 470 186.37 479 R
7 X
V
0 X
(4) 174.37 471 T
174.37 443 183.37 452 R
7 X
V
0 X
(5) 174.37 444 T
192.37 569 192.37 434 2 L
1 H
N
156.37 569 156.37 434 2 L
N
72 63 540 720 C
0 0 612 792 C
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 NameSpace Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(8) 500 42.62 T
1 12 Q
(The structure for each B-tree leaf block in a lar) 72 712 T
(ge directory is:) 297.25 712 T
0.28 (Packed at the front are the hash value and of) 72 319 P
0.28 (fsets of each of the strings. The entries are sorted on) 287.1 319 P
(hash value. Packed at the back are the inode numbers, string lengths, and the strings themselves.) 72 305 T
72 63 540 720 C
75.38 333 536.62 708 C
129.37 636 219.37 645 R
7 X
0 K
V
1 12 Q
0 X
(\336rst used byte) 129.37 637 T
111.37 591 237.37 618 R
7 X
V
0 X
(run length coded map of) 111.37 610 T
(free space in block) 111.37 596 T
93.38 573 138.37 582 R
7 X
V
0 X
(hashval) 93.38 574 T
93.38 564 138.37 573 R
7 X
V
0 X
(hashval) 93.38 565 T
93.38 555 138.37 564 R
7 X
V
0 X
(hashval) 93.38 556 T
93.38 546 138.37 555 R
7 X
V
0 X
(hashval) 93.38 547 T
93.38 537 138.37 546 R
7 X
V
0 X
(hashval) 93.38 538 T
192.37 672 228.37 681 R
7 X
V
0 X
(next) 192.37 673 T
111.37 672 147.37 681 R
7 X
V
0 X
(prior) 111.37 673 T
129.37 654 219.37 663 R
7 X
V
0 X
(count of entries) 129.37 655 T
129.37 690 219.37 699 R
7 X
V
0 X
(magic number) 129.37 691 T
84.38 348 255.37 699 R
0.5 H
2 Z
N
84.38 681 255.37 681 2 L
N
84.38 582 255.37 582 2 L
N
84.38 573 255.37 573 2 L
N
84.38 564 255.37 564 2 L
N
84.38 555 255.37 555 2 L
N
84.38 546 255.37 546 2 L
N
84.38 456 255.37 456 2 L
N
84.38 429 255.37 429 2 L
N
84.38 402 255.37 402 2 L
N
84.38 375 255.37 375 2 L
N
250.29 471 245.09 474 250.29 477 250.29 474 4 Y
V
219.37 577.5 264.37 577.5 264.37 474 250.29 474 4 L
N
248.57 417 243.37 420 248.57 423 248.57 420 4 Y
V
219.37 568.5 273.37 568.5 273.37 420 248.57 420 4 L
N
247.48 444 242.28 447 247.48 450 247.48 447 4 Y
V
219.37 559.5 282.37 559.5 282.37 447 247.48 447 4 L
N
246.72 363 241.53 366 246.72 369 246.72 366 4 Y
V
219.37 550.5 291.37 550.5 291.37 366 246.72 366 4 L
N
84.38 538 255.37 538 2 L
N
246.17 390 240.98 393 246.17 396 246.17 393 4 Y
V
219.37 541.5 300.37 541.5 300.37 393 246.17 393 4 L
N
138.37 510 219.37 519 R
7 X
V
0 X
(unused space) 138.37 511 T
84.38 483 255.37 483 2 L
N
84.38 663 255.37 663 2 L
N
201.37 411 237.37 420 R
7 X
V
0 X
(baker) 201.37 412 T
201.37 438 237.37 447 R
7 X
V
0 X
(charlie) 201.37 439 T
201.37 465 237.37 474 R
7 X
V
0 X
(able) 201.37 466 T
201.37 357 237.37 366 R
7 X
V
0 X
(delta) 201.37 358 T
201.37 384 237.37 393 R
7 X
V
0 X
(zulu) 201.37 385 T
102.38 438 138.37 447 R
7 X
V
0 X
(I-6546) 102.38 439 T
102.38 465 138.37 474 R
7 X
V
0 X
(I-6523) 102.38 466 T
102.38 357 138.37 366 R
7 X
V
0 X
(I-4253) 102.38 358 T
102.38 384 138.37 393 R
7 X
V
0 X
(I-9833) 102.38 385 T
102.38 411 138.37 420 R
7 X
V
0 X
(I-1263) 102.38 412 T
165.37 465 174.37 474 R
7 X
V
0 X
(4) 165.37 466 T
165.37 438 174.37 447 R
7 X
V
0 X
(7) 165.37 439 T
165.37 411 176.37 420 R
7 X
V
0 X
(5) 165.37 412 T
165.37 384 177.37 393 R
7 X
V
0 X
(4) 165.37 385 T
165.37 357 174.37 366 R
7 X
V
0 X
(5) 165.37 358 T
174.37 582 174.37 537 2 L
1 H
N
84.38 645 255.37 645 2 L
0.5 H
N
84.38 627 255.37 627 2 L
N
174.37 681 174.37 663 2 L
1 H
N
309.37 393 525.37 699 R
7 X
V
4 F
0 X
(struct xfs_dir_leafblock {) 309.37 691 T
(struct xfs_dir_leaf_hdr) 345.37 679 T
(ushort magic;) 417.37 667 T
(xblkno forw;) 417.37 655 T
(xblkno back;) 417.37 643 T
(ushort count;) 417.37 631 T
(ushort) 417.37 619 T
(f) 309.37 607 T
(irstused;) 316.57 607 T
(ushort pad1;) 417.37 595 T
(struct xfs_-) 417.37 583 T
(dir_leaf_map {) 309.37 571 T
(ush-) 489.37 559 T
(ort base;) 309.37 547 T
(ush-) 489.37 535 T
(ort size;) 309.37 523 T
(} freema-) 417.37 511 T
(p[LEAF_MAPSIZE];) 309.37 499 T
(} hdr;) 345.37 487 T
-3.55 (struct xfs_dir_leaf_entry) 345.37 475 P
({) 309.37 463 T
(uint hashval;) 417.37 451 T
(ushort nameidx;) 417.37 439 T
(ushort pad2;) 417.37 427 T
(} leaves[1];) 345.37 415 T
(struct xfs_dir_leaf_name) 345.37 403 T
192.37 483 192.37 348 2 L
N
147.37 483 147.37 348 2 L
N
72 63 540 720 C
0 0 612 792 C
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 NameSpace Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(9) 500 42.62 T
1 12 Q
(The structure for the B-tree root or the intermediate nodes in a lar) 72 712 T
(ge directory is:) 386.2 712 T
0.38 (Packed at the front are the B-tree elements. Each element contains the associated hash value and) 72 454 P
-0.28 (the block number of the B-tree block that contains all the nodes between this key and the key from) 72 440 P
-0.19 (the prior entry in this B-tree block. Entries after the last hash value are pointed to by the) 72 426 P
3 F
-0.19 (after) 493.21 426 P
1 F
-0.19 ( \336eld) 515.87 426 P
(in the header structure.) 72 412 T
(The overall structure of the B*-tree used in a lar) 72 394 T
(ge directory is:) 302.6 394 T
1.73 (The B-tree is embedded inside a linear array of blocks, ie: a \336le structure. Pointers to B-tree) 72 142 P
(blocks are relative to the \336le, not to the \336lesystem.) 72 128 T
72 63 540 720 C
75.38 468 536.62 708 C
111.37 582 183.37 591 R
7 X
0 K
V
1 12 Q
0 X
(hashval) 111.37 583 T
201.37 582 273.37 591 R
7 X
V
0 X
(block number) 201.37 583 T
111.37 564 183.37 573 R
7 X
V
0 X
(hashval) 111.37 565 T
201.37 564 273.37 573 R
7 X
V
0 X
(block number) 201.37 565 T
111.37 546 183.37 555 R
7 X
V
0 X
(hashval) 111.37 547 T
201.37 546 273.37 555 R
7 X
V
0 X
(block number) 201.37 547 T
111.37 528 183.37 537 R
7 X
V
0 X
(hashval) 111.37 529 T
201.37 528 273.37 537 R
7 X
V
0 X
(block number) 201.37 529 T
147.37 672 246.37 681 R
7 X
V
0 X
(leaves next) 147.37 673 T
147.37 600 246.37 609 R
7 X
V
0 X
(count of entries) 147.37 601 T
147.37 690 246.37 699 R
7 X
V
0 X
(magic number) 147.37 691 T
102.38 483 273.37 699 R
0.5 H
2 Z
N
102.38 681 273.37 681 2 L
N
102.38 573 273.37 573 2 L
N
147.37 501 228.37 510 R
7 X
V
0 X
(unused space) 147.37 502 T
102.38 555 273.37 555 2 L
N
102.38 537 273.37 537 2 L
N
102.38 519 273.37 519 2 L
N
102.38 591 273.37 591 2 L
N
147.37 654 246.37 663 R
7 X
V
0 X
(count of free blocks) 147.37 655 T
147.37 636 246.37 645 R
7 X
V
0 X
(free block chain) 147.37 637 T
147.37 618 246.37 627 R
7 X
V
0 X
(node after all entries) 147.37 619 T
102.38 663 273.37 663 2 L
N
102.38 609 273.37 609 2 L
N
102.38 645 273.37 645 2 L
N
102.38 627 273.37 627 2 L
N
183.37 591 183.37 519 2 L
1 H
N
300.37 483 516.37 699 R
7 X
V
4 F
0 X
(struct xfs_dir_intnode {) 300.37 691 T
(struct xfs_dir_int_hdr {) 336.37 679 T
(ushort magic;) 408.37 667 T
(unchar leavesn-) 408.37 655 T
(ext;) 300.37 643 T
(unchar free-) 408.37 631 T
(blks;) 300.37 619 T
(xblkno) 408.37 607 T
(freechain;) 300.37 595 T
(xblkno after;) 408.37 583 T
(ushort count;) 408.37 571 T
(ushort pad1[3];) 408.37 559 T
(} hdr;) 336.37 547 T
(struct xfs_dir_int_entry) 336.37 535 T
({) 300.37 523 T
(uint hashval;) 408.37 511 T
(xblkno before;) 408.37 499 T
(ushort pad2;) 408.37 487 T
72 63 540 720 C
0 0 612 792 C
72 63 540 720 C
75.38 156 536.62 390 C
1 12 Q
0 X
0 K
(hash03) 264.37 247 T
(hash) 139.37 343.5 T
(value) 139.37 329.5 T
(hash) 175.62 343.5 T
(value) 175.62 329.5 T
(hash) 102.38 343.5 T
(value) 102.38 329.5 T
165.37 201 300.37 255 R
0.5 H
2 Z
N
219.37 309 354.37 363 R
N
309.37 201 444.37 255 R
N
255.37 255 255.37 201 2 L
N
210.37 255 210.37 201 2 L
N
264.37 363 264.37 309 2 L
N
309.37 363 309.37 309 2 L
N
354.37 255 354.37 201 2 L
N
399.37 255 399.37 201 2 L
N
(ditzy) 318.37 229 T
(cup) 363.37 229 T
(card) 228.37 337 T
(bird) 408.37 229 T
(bat) 264.37 229 T
(axe) 417.37 337 T
(ark) 219.37 229 T
(able) 273.37 337 T
(dup) 318.37 337 T
165.37 219 300.37 219 2 L
N
219.37 327 354.37 327 2 L
N
309.37 219 444.37 219 2 L
N
363.37 309 498.37 363 R
N
408.37 363 408.37 309 2 L
N
453.37 363 453.37 309 2 L
N
(corp) 462.37 337 T
(corn) 174.37 229 T
(cine) 372.37 337 T
363.37 327 498.37 327 2 L
N
(I-3352) 169.87 206.5 T
(I-553) 212.87 206.25 T
(I-1) 259.87 205.75 T
(163) 273.42 205.75 T
(I-7936) 223.62 314 T
(I-6287) 269.12 313.5 T
(I-1930) 313.87 314.5 T
(I-2752) 367.63 314.75 T
(I-8002) 412.38 315 T
(I-7723) 314.63 206.5 T
(I-5294) 358.63 206.75 T
(I-4823) 457.38 315 T
(I-6619) 404.63 206.5 T
84.38 300 516.37 372 R
N
147.37 192 453.37 264 R
N
(0) 84.38 283 T
(M) 489.37 283 T
(M+1) 147.37 175 T
(N) 426.37 175 T
93.38 309 210.37 363 R
N
100.69 363 100.69 309 2 L
N
166.5 363 166.5 309 2 L
N
129.94 363 129.94 309 2 L
N
203.06 363 203.06 309 2 L
N
137.25 363 137.25 309 2 L
N
173 363 173 309 2 L
N
163.57 260.72 165.37 255 159.52 256.3 161.54 258.51 4 Y
V
96.75 318 161.54 258.51 2 L
N
213.56 307.48 219.37 309.01 217.79 303.22 215.67 305.35 4 Y
V
133.5 318 156.37 291 201.37 291 215.68 305.34 4 L
N
357.55 307.48 363.36 309.01 361.78 303.22 359.67 305.35 4 Y
V
169.5 317.25 192.37 282 336.37 282 359.68 305.34 4 L
N
307.78 260.8 309.36 255.01 303.56 256.53 305.67 258.66 4 Y
V
206.25 318 219.37 273 291.37 273 305.68 258.66 4 L
N
255.37 237 300.37 237 2 L
1 H
N
(hash05) 273.37 355 T
264.37 345 309.37 345 2 L
N
(hash02) 219.37 247 T
210.37 237 255.37 237 2 L
N
(hash08) 417.37 355 T
408.37 345 453.37 345 2 L
N
(hash1) 363.37 247 T
(1) 390.91 247 T
354.37 237 399.37 237 2 L
N
(hash10) 318.37 247 T
309.37 237 354.37 237 2 L
N
(hash06) 318.37 355 T
309.37 345 354.37 345 2 L
N
(hash09) 462.37 355 T
453.37 345 498.37 345 2 L
N
(hash07) 372.37 355 T
363.37 345 408.37 345 2 L
N
(hash01) 174.37 247 T
165.37 237 210.37 237 2 L
N
(hash04) 228.37 355 T
219.37 345 264.37 345 2 L
N
(hash12) 408.37 247 T
399.37 237 444.37 237 2 L
N
72 63 540 720 C
0 0 612 792 C
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 NameSpace Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(10) 496 42.62 T
2 14 Q
(4.5 W) 72 710.67 T
(orking Data Structur) 106.21 710.67 T
(es \050ie: In-Memory\051) 232.66 710.67 T
2 12 Q
(4.5.1 Inode T) 72 692 T
(able) 138.2 692 T
1 F
0.26 (W) 72 676 P
0.26 (e will have a traditional incore inode table. The namespace manager will understand that when) 82.36 676 P
0.12 (an inode is marked as containing literal data, it must manage the directory structures \050in the com-) 72 662 P
(pressed format\051 inside the inode and not in a buf) 72 648 T
(fer) 303.95 648 T
(.) 316.61 648 T
0.39 (Since we have a split inode and space is being shared between the primary fork and the attribute) 72 630 P
0.54 (fork, the namespace manager has the right to call a function in the attribute manager asking that) 72 616 P
-0.22 (any attributes stored in the literal area of the inode be moved out into newly allocated blocks. This) 72 602 P
0.4 (routine will be called if a small directory \050ie: in the inode\051 grows lar) 72 588 P
0.4 (ge enough to need the space) 403.1 588 P
0 (occupied by the attributes in the inode, but not too lar) 72 574 P
0 (ge that it won\325) 328.66 574 P
0 (t \336t into the whole literal area) 398.07 574 P
(of the inode.) 72 560 T
2 F
(4.5.2 Dir) 72 540 T
(ectory Structur) 116.09 540 T
(e) 194.8 540 T
1 F
1.48 (The directory structures for both small and lar) 72 524 P
1.48 (ge directories have already been described. The) 302.99 524 P
0.79 (namespace manager code will use those structures either in the incore inode itself, or in buf) 72 510 P
0.79 (fers) 522.02 510 P
(that have been read from disk.) 72 496 T
2 14 Q
(4.6 Performance Characterization) 72 468.67 T
2 12 Q
(4.6.1 Inode Size and Structur) 72 450 T
(e) 221.04 450 T
1 F
0.49 (This table compares the approximate storage ef) 72 434 P
0.49 (\336ciency of small structured directories \050ie: inside) 301.89 434 P
2.08 (the inode\051 for various sizes of inodes for a typical kernel source tree on campus. This table) 72 420 P
-0.03 (assumes that an inode will contain 64 bytes of \336xed \336elds and have 9 bytes of overhead per entry) 72 406 P
-0.03 (.) 537 406 P
0.74 (The size of the inodes in a \336lesystem will be stored in the superblock for that \336lesystem. In the) 72 279 P
0.15 (\336rst release we may only support a single inode size, but we want the \337exibility in the data struc-) 72 265 P
(tures to allow us to have dif) 72 251 T
(ferent inode sizes per \336lesystem.) 205.03 251 T
2 F
(4.6.2 Small Dir) 72 231 T
(ectory Structur) 148.41 231 T
(e) 227.12 231 T
1 F
-0.12 (The ef) 72 215 P
-0.12 (\336ciency of not having to seek the disk heads out to read another block before we can access) 102.64 215 P
-0.14 (the directory will be a big win. For a lar) 72 201 P
-0.14 (ge percentage of directories, simply reading the inode will) 261.69 201 P
1.16 (gets us the contents of the directory and allow us to continue the naming operation. This table) 72 187 P
(assumes that an inode contains 64 bytes of \336xed \336elds.) 72 173 T
2 10 Q
(T) 85.75 383.33 T
(ABLE 1. Small Format Dir) 91.67 383.33 T
(ectory Ef\336ciency) 207.26 383.33 T
(Dirs that \336t) 160.72 362.33 T
1 F
(128B inode) 85.74 346.33 T
(27%) 160.72 346.33 T
(256B inode) 85.74 330.33 T
(62%) 160.72 330.33 T
(512B inode) 85.74 314.33 T
(85%) 160.72 314.33 T
(1024B inode) 85.74 298.33 T
(95%) 160.72 298.33 T
2 F
(T) 85.75 150.33 T
(ABLE 2. Number of User) 91.67 150.33 T
(-Settable Keys in a Small Dir) 199.84 150.33 T
(ectory versus Inode Size) 323.2 150.33 T
(128B) 208.23 129.33 T
(inode) 208.23 117.33 T
(256B) 263.28 129.33 T
(inode) 263.28 117.33 T
(512B) 316.11 129.33 T
(inode) 316.11 117.33 T
(1KB) 368.49 129.33 T
(inode) 368.49 117.33 T
1 F
(8 Byte Filenames) 85.74 101.33 T
(3) 208.23 101.33 T
(10) 263.28 101.33 T
(25) 316.11 101.33 T
(55) 368.49 101.33 T
(32 Byte Filenames) 85.74 85.33 T
(1) 208.23 85.33 T
(4) 263.28 85.33 T
(10) 316.11 85.33 T
(23) 368.49 85.33 T
79.74 377 226.02 377 2 L
V
0.5 H
0 Z
N
79.74 144 414.87 144 2 L
V
N
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 NameSpace 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
2 12 Q
(4.6.3 Large Dir) 72 712 T
(ectory Structur) 149.73 712 T
(e) 228.44 712 T
1 F
0.31 (A lar) 72 696 P
0.31 (ge directory will be structured as a B*-tree keyed on the hash value of the \336lenames. A B*-) 96.4 696 P
1.14 (tree improves on a plain B-tree in that since all the keys are in the leaves, those leaves can be) 72 682 P
-0.05 (linked together to give quick sequential access to all the keys in the tree. The access time to \336nd a) 72 668 P
0.19 (give key in a B*-tree is a logarithmic function of the directory size, not a linear relationship as in) 72 654 P
(most other UNIX namespace schemes.) 72 640 T
0.8 (For our application, it is expected that only in rare cases will directories use more than a single) 72 622 P
(leaf node.) 72 608 T
2 F
(4.6.4 Dir) 72 511 T
(ectory Inode Allocation Policy) 116.09 511 T
1 F
0.1 (One possibility for improving naming ef) 72 495 P
0.1 (\336ciency is to have the inode allocation policy try to clus-) 266.51 495 P
0.61 (ter directory inodes within the inode list of an AllocGroup. The intent is to increase our odds of) 72 481 P
0.23 (reading in about-to-be-accessed inodes along with the inode of current interest. It would increase) 72 467 P
(our cache hit ratio.) 72 453 T
2 F
(4.6.5 A) 72 433 T
(vailable Parallelism) 106.76 433 T
1 F
1.28 (Reading/writing a directory entry is impacted by the level of parallelism provided for reading/) 72 417 P
0.14 (writing a \336le because the underlying structure used by the NameSpace Manager for a directory is) 72 403 P
(that of a \336le.) 72 389 T
1.73 (Directory blocks will live in buf) 72 371 P
1.73 (fers, buf) 234.65 371 P
1.73 (fers are exclusively locked when accessed, and most) 276.12 371 P
1.44 (directory operations will take place under the auspices of the transaction manager \050which will) 72 357 P
0.16 (hold buf) 72 343 P
0.16 (fer block locks until the transaction completes\051, so operations on a single directory inode) 112.25 343 P
(will essentially be single threaded.) 72 329 T
2 F
(4.6.6 Logging Bandwidth Requir) 72 309 T
(ed) 239.39 309 T
1 F
(Directory operations will usually require one of:) 72 293 T
(\245 log the directory inode with the literal directory inside, or) 72 277 T
(\245 log the changed block\050s\051 in the directory B-tree.) 72 263 T
0.68 (In the \336rst case, we will log the whole inode, while in the second case we will log as many full) 72 247 P
(blocks as have changed in the operation.) 72 233 T
0.54 (Note that directory operations are usually a part of a lar) 72 215 P
0.54 (ger operation such as removing a \336le. In) 343.01 215 P
0.56 (such a case, an inode would be modi\336ed as part of the same transaction, thereby requiring more) 72 201 P
(log bandwidth than just the operation on the directory per se.) 72 187 T
2 F
(4.6.7 Effect on Disk Seek Patterns) 72 167 T
1 F
-0.14 (Obviously) 72 151 P
-0.14 (, when the directory is literally inside the inode, there is no impact on disk seek patterns) 121.2 151 P
(\050other than the lack of a required seek to access a data block\051.) 72 137 T
-0.16 (When the directory is not literally inside the inode, a disk seek and block read will be required. T) 72 119 P
-0.16 (o) 534 119 P
(be more speci\336c:) 72 105 T
(\245 a seek and read of the whole \336rst extent of the directory) 72 89 T
(If the desired \336lename is not in the \336rst extent \050unlikely\051, more seeks and reads will be required.) 72 73 T
2 10 Q
(T) 85.75 585.33 T
(ABLE 3. Number of User) 91.67 585.33 T
(-Settable Keys in a Large Dir) 199.84 585.33 T
(ectory Leaf versus Logical Block Size) 324.3 585.33 T
(512B LBS) 208.23 564.33 T
(1KB LBS) 263.28 564.33 T
(2KB LBS) 316.11 564.33 T
(4KB LBS) 368.93 564.33 T
(8KB LBS) 421.76 564.33 T
1 F
(8 Byte Filenames) 85.74 548.33 T
(19) 208.23 548.33 T
(39) 263.28 548.33 T
(80) 316.11 548.33 T
(162) 368.93 548.33 T
(326) 421.76 548.33 T
(32 Byte Filenames) 85.74 532.33 T
(9) 208.23 532.33 T
(20) 263.28 532.33 T
(41) 316.11 532.33 T
(82) 368.93 532.33 T
(166) 421.76 532.33 T
79.74 579 468.59 579 2 L
V
0.5 H
0 Z
N
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 NameSpace Manager Design) 72 42.62 T
(October 7, 1993) 260.9 42.62 T
(12) 496 42.62 T
2 14 Q
(4.7 Initialization Pr) 72 710.67 T
(ocedur) 187.97 710.67 T
(e) 228.91 710.67 T
3 12 Q
(Mkfs) 72 694 T
1 F
( will create the) 95.32 694 T
3 F
(r) 169.26 694 T
(oot) 173.48 694 T
1 F
( and) 188.8 694 T
3 F
(lost+found) 212.12 694 T
1 F
( directories when it lays out the \336lesystem.) 264.87 694 T
2 14 Q
(4.8 Logging Actions) 72 666.67 T
2 12 Q
(4.8.1 Normal Operation) 72 648 T
(4.8.1.1 T) 72 630 T
(ypes of Log Records) 115.09 630 T
(4.8.2 Recovery) 72 612 T
(4.8.2.1 Actions For Each T) 72 594 T
(ype of Log Record) 207.37 594 T
2 14 Q
(4.9 Disk T) 72 568.67 T
(ransfer Policies) 132 568.67 T
2 12 Q
(4.9.1 T) 72 550 T
(o Disk) 105.88 550 T
(4.9.1.1 Xfer size) 72 532 T
(4.9.1.2 Logging) 72 514 T
(4.9.2 Fr) 72 496 T
(om Disk) 111.42 496 T
(4.9.2.1 Xfer sizes) 72 478 T
213.87 448.22 72 448.22 2 L
V
1.71 H
0 Z
N
2 18 Q
(5.0 User Interface) 72 450 T
2 14 Q
(5.1 System Calls) 72 420.67 T
(5.2 Utilities) 72 394.67 T
372.87 364.22 72 364.22 2 L
V
N
2 18 Q
(6.0 Implementation Plan and Schedule) 72 366 T
2 14 Q
(6.1 Featur) 72 336.67 T
(es Not in V) 133.15 336.67 T
(ersion 1) 197.54 336.67 T
2 12 Q
(6.1.1 IPC Nodes) 72 318 T
1 F
(IPC nodes may not appear in the March release.) 72 302 T
2 F
(6.1.2 Mount Points) 72 282 T
1 F
(Mount point nodes may not appear in the March release.) 72 266 T
166.97 234.22 72 234.22 2 L
V
N
2 18 Q
(7.0 Initial T) 72 236 T
225.78 234.22 165.32 234.22 2 L
V
N
(est Plan) 165.32 236 T
FMENDPAGE
%%EndPage: "12" 13
%%Trailer
%%BoundingBox: 0 0 612 792
%%Pages: 12 1
%%DocumentFonts: Palatino-Roman
%%+ Times-Roman
%%+ Times-Bold
%%+ Times-Italic
%%+ Courier
![[BACK]](/icons/back.gif){kind=icon}
Return to naming.ps CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [Development] / xfs-website / design_docs / xfsdocs93_ps