%!
%%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 6 FMDOCUMENT
0 0 /Palatino-Roman FMFONTDEFINE
1 0 /Times-Roman FMFONTDEFINE
2 0 /Courier FMFONTDEFINE
3 0 /Courier-Bold 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
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(Outline) 72 42.62 T
(December 16, 1993) 255.07 42.62 T
(1) 500 42.62 T
1 36 Q
4 K
(Outline) 252.01 696 T
1 18 Q
0 K
(Basic \336le system layout) 72 648 T
(Btree algorithms & data structures) 72 616 T
(Space allocation interfaces and design) 72 584 T
(Inode allocation interfaces and design) 72 552 T
(Block mapping interfaces and design) 72 520 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
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(Superblock) 72 42.62 T
(December 16, 1993) 255.07 42.62 T
(2) 500 42.62 T
1 36 Q
4 K
(Superblock) 224.02 696 T
1 18 Q
0 K
(File system is divided into a number of Allocation Groups) 72 648 T
(All but the last are of equal size) 72 616 T
(Each allocation group starts with a super block \050block 0\051 and an) 72 584 T
(allocation group header \050block 1\051) 72 564 T
(One copy of superblock per allocation group, but only the \336rst) 72 532 T
(one is ever updated except when \336le system changes size) 72 512 T
2 9 Q
(typedef struct xfs_sb {) 72 481 T
(uuid_t) 108 470 T
(sb_uuid;) 216 470 T
(/* f) 288 470 T
(ile system unique id */) 309.57 470 T
(xfs_fsblock_t) 108 459 T
(sb_dblocks;) 216 459 T
(/* number of data blocks */) 288 459 T
(__uint32_t) 108 448 T
(sb_blocksize;) 216 448 T
(/* logical block size, bytes */) 286.1 448 T
(/*) 108 437 T
( * sb_magic is at offset 28 to be at the same location as fs_magic) 108 426 T
( * in an EFS f) 108 415 T
(ilesystem, thus ensuring there is no confusion.) 183.49 415 T
( */) 108 404 T
(__uint32_t) 108 393 T
(sb_magicnum;) 216 393 T
(/* magic number == XFS_SB_MAGIC */) 288 393 T
(xfs_fsblock_t) 108 382 T
(sb_rblocks;) 216 382 T
(/* number of realtime blocks */) 288 382 T
(xfs_fsblock_t) 108 371 T
(sb_rbitmap;) 216 371 T
(/* bitmap for realtime blocks */) 288 371 T
(xfs_fsblock_t) 108 360 T
(sb_rsummary;) 216 360 T
(/* summary for xfs_rbitmap */) 288 360 T
(xfs_ino_t) 108 349 T
(sb_rootino;) 216 349 T
(/* root inode number */) 288 349 T
(xfs_agblock_t) 108 338 T
(sb_rextsize;) 216 338 T
(/* realtime extent size, blocks */) 288 338 T
(xfs_agblock_t) 108 327 T
(sb_agblocks;) 216 327 T
(/* size of an allocation group */) 288 327 T
(xfs_agnumber_t) 108 316 T
(sb_agcount;) 216 316 T
(/* number of allocation groups */) 288 316 T
(__uint16_t) 108 305 T
(sb_versionnum;) 216 305 T
(/* header version == XFS_SB_VERSION */) 291.49 305 T
(__uint16_t) 108 294 T
(sb_sectsize;) 216 294 T
(/* volume sector size, bytes */) 288 294 T
(__uint16_t) 108 283 T
(sb_inodesize;) 216 283 T
(/* inode size, bytes */) 288 283 T
(__uint16_t) 108 272 T
(sb_inopblock;) 216 272 T
(/* inodes per block */) 288 272 T
(char) 108 261 T
(sb_fname[6];) 216 261 T
(/* f) 288 261 T
(ile system name */) 309.57 261 T
(char) 108 250 T
(sb_fpack[6];) 216 250 T
(/* f) 288 250 T
(ile system pack name */) 309.57 250 T
(__uint8_t) 108 239 T
(sb_blocklog;) 216 239 T
(/* log2 of xfs_blocksize */) 288 239 T
(__uint8_t) 108 228 T
(sb_sectlog;) 216 228 T
(/* log2 of xfs_sectsize */) 288 228 T
(__uint8_t) 108 217 T
(sb_inodelog;) 216 217 T
(/* log2 of xfs_inodesize */) 288 217 T
(__uint8_t) 108 206 T
(sb_inopblog;) 216 206 T
(/* log2 of xfs_inopblock */) 288 206 T
(__uint8_t) 108 195 T
(sb_smallf) 216 195 T
(iles;) 264.53 195 T
(/* set if small f) 291.49 195 T
(iles in inodes */) 383.17 195 T
(/* statistics */) 108 184 T
(/* These f) 108 173 T
(ields must remain contiguous. If you really) 161.93 173 T
( * want to change their layout, make sure you f) 108 162 T
(ix the) 361.45 162 T
( * code in xfs_trans_apply_sb_deltas\050\051.) 108 151 T
( */) 108 140 T
(__uint64_t) 108 129 T
(sb_icount;) 216 129 T
(/* allocated inodes */) 288 129 T
(__uint64_t) 108 118 T
(sb_ifree;) 216 118 T
(/* free inodes */) 288 118 T
(__uint64_t) 108 107 T
(sb_fdblocks;) 216 107 T
(/* free data blocks */) 288 107 T
(__uint32_t) 108 96 T
(sb_frextents;) 216 96 T
(/* free realtime extents */) 288 96 T
(} xfs_sb_t;) 72 85 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
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(Allocation Gr) 72 42.62 T
(oup Header) 119.85 42.62 T
(December 16, 1993) 255.07 42.62 T
(3) 500 42.62 T
1 36 Q
4 K
(Allocation Group Header) 123.07 696 T
1 18 Q
0 K
(Allocation group header \050xfs_aghdr_t\051 contains information to) 72 648 T
(\336nd everything in its allocation group) 72 628 T
(Three sections:) 72 596 T
1 14 Q
(1.) 72 572.67 T
(Identi\336cation) 85.75 572.67 T
(2.) 72 550.67 T
(Freespace information) 85.75 550.67 T
(3.) 72 528.67 T
(Inode information) 85.75 528.67 T
1 18 Q
(May split into multiple buf) 72 498 T
(fers \050512 byte sections\051 to increase) 265.59 498 T
(parallelism) 72 478 T
2 9 Q
(typedef struct xfs_aghdr {) 72 426 T
(__uint32_t) 108 415 T
(ag_magic;) 216 415 T
(/* magic number == XFS_AGH_MAGIC */) 288 415 T
(__uint16_t) 108 404 T
(ag_version;) 216 404 T
(/* header version == XFS_AGH_VERSION */) 288 404 T
(xfs_agnumber_t) 108 393 T
(ag_seqno;) 216 393 T
(/* sequence # starting from 0 */) 288 393 T
(xfs_agblock_t) 108 382 T
(ag_length;) 216 382 T
(/* size in blocks of a.g. */) 288 382 T
(/*) 108 371 T
( * Freespace information) 108 360 T
( */) 108 349 T
(xfs_agblock_t) 108 338 T
(ag_roots[XFS_BTNUM_MAX - 1];) 216 338 T
(/* BNO, CNT */) 366.99 338 T
(xfs_agblock_t) 108 327 T
(ag_freelist;) 216 327 T
(/* free blocks */) 288 327 T
(__uint16_t) 108 316 T
(ag_levels[XFS_BTNUM_MAX - 1];) 216 316 T
(/* BNO, CNT */) 372.38 316 T
(xfs_extlen_t) 108 305 T
(ag_f) 216 305 T
(list_count;) 237.57 305 T
(/* #blocks */) 296.89 305 T
(xfs_extlen_t) 108 294 T
(ag_freeblks;) 216 294 T
(/* total free blocks */) 288 294 T
(xfs_extlen_t) 108 283 T
(ag_longest;) 216 283 T
(/* longest free space */) 288 283 T
(/*) 108 272 T
( * Inode information) 108 261 T
( * Inodes are mapped by interpreting the inode number, so no) 108 250 T
( * mapping data is needed here.) 108 239 T
( */) 108 228 T
(xfs_agino_t) 108 217 T
(ag_icount;) 216 217 T
(/* count of allocated inodes */) 288 217 T
(xfs_agino_t) 108 206 T
(ag_if) 216 206 T
(irst;) 242.96 206 T
(/* f) 288 206 T
(irst allocated inode */) 309.57 206 T
(xfs_agino_t) 108 195 T
(ag_ilast;) 216 195 T
(/* last allocated inode */) 288 195 T
(xfs_agino_t) 108 184 T
(ag_if) 216 184 T
(list;) 242.96 184 T
(/* f) 288 184 T
(irst free inode */) 309.57 184 T
(xfs_agino_t) 108 173 T
(ag_ifcount;) 216 173 T
(/* number of free inodes */) 288 173 T
(} xfs_aghdr_t;) 72 162 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
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(Btr) 72 42.62 T
(ee Block Format) 82.51 42.62 T
(December 16, 1993) 255.07 42.62 T
(4) 500 42.62 T
1 36 Q
4 K
(Btree Block Format) 163.03 696 T
1 18 Q
0 K
(Btrees used in the space manager:) 72 648 T
3 12 Q
(\245) 72 624.67 T
1 14 Q
(freespace, sorted by block number \050BNO\051) 85.75 624.67 T
3 12 Q
(\245) 72 602.67 T
1 14 Q
(freespace, sorted by block size \050CNT\051) 85.75 602.67 T
3 12 Q
(\245) 72 580.67 T
1 14 Q
(block map, sorted by \336le of) 85.75 580.67 T
(fset \050BMAP\051) 239.39 580.67 T
1 18 Q
(All use a common header structure xfs_btree_block_t and some) 72 550 T
(common code.) 72 530 T
-0.5 (Each btree block occupies one \336le system block exactly) 72 498 P
-0.5 (, unless it) 468.53 498 P
(is being stored in an inode \050and is smaller\051.) 72 478 T
(Each btree block consists of a header) 72 446 T
(, some records, and some) 338.06 446 T
-0.6 (pointers. The record type varies from btree to btree; the pointer is) 72 426 P
(a block number within an allocation group \050xfs_agblock_t\051. The) 72 406 T
(pointers are absent in leaf blocks.) 72 386 T
2 9 Q
(typedef struct xfs_btree_block) 72 366 T
({) 72 355 T
(__uint32_t) 108 344 T
(bb_magic;) 180 344 T
(/* magic number for block type */) 252 344 T
(__uint16_t) 108 333 T
(bb_level;) 180 333 T
(/* 0 is a leaf */) 252 333 T
(__uint16_t) 108 322 T
(bb_numrecs;) 180 322 T
(/* current # of data records */) 252 322 T
(xfs_agblock_t) 108 311 T
(bb_leftsib;) 180 311 T
(/* left sibling block or NULLAGBLOCK */) 252 311 T
(xfs_agblock_t) 108 300 T
(bb_rightsib;) 180 300 T
(/* right sibling block or NULLAGBLOCK */) 252 300 T
(} xfs_btree_block_t;) 72 289 T
1 18 Q
(Records for BNO and CNT btree blocks have this format:) 72 261 T
2 9 Q
(typedef struct xfs_alloc_rec) 72 241 T
({) 72 230 T
(xfs_agblock_t) 108 219 T
(ar_startblock;) 180 219 T
(/* starting block number */) 255.49 219 T
(xfs_extlen_t) 108 208 T
(ar_blockcount;) 180 208 T
(/* count of free blocks */) 255.49 208 T
(} xfs_alloc_rec_t;) 72 197 T
1 18 Q
(Records for BMAP btree blocks have this format:) 72 169 T
2 9 Q
(typedef struct xfs_bmbt_rec) 72 149 T
({) 72 138 T
(__uint32_t) 108 127 T
(l0, l1, l2, l3;) 180 127 T
(} xfs_bmbt_rec_t;) 72 116 T
(/* l0:0-31 and l1:9-31 are startoff.) 72 105 T
( * l1:0-8, l2:0-31, and l3:21-31 are startblock.) 72 94 T
( * l3:0-20 are blockcount.) 72 83 T
( */) 72 72 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
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(Disk Inode Format \0501\051) 72 42.62 T
(December 16, 1993) 255.07 42.62 T
(5) 500 42.62 T
1 36 Q
4 K
(Disk Inode Format \0501\051) 144.54 696 T
1 18 Q
0 K
(Disk inodes contain a core section \050xfs_dinode_core_t\051 and a) 72 648 T
-0.71 (union, which contains type-speci\336c information. Important to the) 72 628 P
(space manager are three formats: AGINO, EXTENTS, and) 72 608 T
(BTREE.) 72 588 T
(AGINO is used to link free inodes together in a list.) 72 556 T
(EXTENTS is used to keep extent information when the extents) 72 524 T
(will \336t in the inode.) 72 504 T
(BTREE is used when the number of extents is too lar) 72 472 T
(ge to \336t in) 454.43 472 T
(the inode.) 72 452 T
(T) 72 420 T
(imestamp values are currently 64 bits \05032 bits of seconds since) 82.36 420 T
(1970, 32 bits of nanoseconds\051 although only the seconds are) 72 400 T
(\336lled in and exported to users.) 72 380 T
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
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(Disk Inode Format \0502\051) 72 42.62 T
(December 16, 1993) 255.07 42.62 T
(6) 500 42.62 T
1 36 Q
4 K
(Disk Inode Format \0502\051) 144.54 696 T
2 9 Q
0 K
(typedef struct xfs_dinode_core {) 72 643 T
(__uint16_t) 108 632 T
(di_magic;) 216 632 T
(/* inode magic # = XFS_DINODE_MAGIC */) 288 632 T
(__uint16_t) 108 621 T
(di_mode;) 216 621 T
(/* mode and type of f) 288 621 T
(ile */) 401.24 621 T
(__int8_t) 108 610 T
(di_version;) 216 610 T
(/* inode version */) 288 610 T
(__int8_t) 108 599 T
(di_format;) 216 599 T
(/* format of di_c data */) 288 599 T
(__int16_t) 108 588 T
(di_nlink;) 216 588 T
(/* number of links to f) 288 588 T
(ile */) 412.03 588 T
(__uint16_t) 108 577 T
(di_uid;) 216 577 T
(/* owner\325s user id */) 288 577 T
(__uint16_t) 108 566 T
(di_gid;) 216 566 T
(/* owner\325s group id */) 288 566 T
(xfs_extnum_t) 108 555 T
(di_nextents;) 216 555 T
(/* number of extents in f) 288 555 T
(ile */) 422.81 555 T
(__int64_t) 108 544 T
(di_size;) 216 544 T
(/* number of bytes in f) 288 544 T
(ile */) 412.03 544 T
(uuid_t) 108 533 T
(di_uuid;) 216 533 T
(/* f) 288 533 T
(ile unique id */) 309.57 533 T
(/*) 108 522 T
( * While these f) 108 511 T
(ields hold 64 bit values, we will only) 194.28 511 T
( * be using the upper 32 bits for now. The t_nsec) 108 500 T
( * portion of the f) 108 489 T
(ields should always be zero. This) 210.46 489 T
( * leaves room for expansion in the future if necessary.) 108 478 T
( */) 108 467 T
(xfs_timestamp_t) 108 456 T
(di_atime;) 216 456 T
(/* time last accessed */) 288 456 T
(xfs_timestamp_t) 108 445 T
(di_mtime;) 216 445 T
(/* time last modif) 288 445 T
(ied */) 385.06 445 T
(xfs_timestamp_t) 108 434 T
(di_ctime;) 216 434 T
(/* time created/inode modif) 288 434 T
(ied */) 433.6 434 T
(/*) 108 423 T
( * Should this be 64 bits? What does nfs3.0 want?) 108 412 T
( */) 108 401 T
(__uint32_t) 108 390 T
(di_gen;) 216 390 T
(/* generation number */) 288 390 T
(xfs_agino_t) 108 379 T
(di_nexti;) 216 379 T
(/* next allocated inode in ag */) 288 379 T
(} xfs_dinode_core_t;) 72 368 T
(typedef struct xfs_dinode) 72 346 T
({) 72 335 T
(xfs_dinode_core_t) 108 324 T
(di_core;) 216 324 T
(union {) 108 313 T
(xfs_agino_t) 144 302 T
(di_next;) 252 302 T
(/* next inode for freelist inodes */) 324 302 T
(dev_t) 144 291 T
(di_dev;) 252 291 T
(/* device for IFCHR/IFBLK */) 324 291 T
(char) 144 280 T
(di_c[1];) 252 280 T
(/* local contents */) 324 280 T
(xfs_bmbt_rec_t) 144 269 T
(di_bmx[1];) 252 269 T
(/* extent list */) 324 269 T
(xfs_btree_block_t) 144 258 T
(di_bmbt;) 252 258 T
(/* btree root */) 324 258 T
(uuid_t) 144 247 T
(di_muuid;) 252 247 T
(/* mount point value */) 324 247 T
(}) 108 236 T
(di_u;) 180 236 T
(} xfs_dinode_t;) 72 225 T
(/*) 72 203 T
( * Values for di_format) 72 192 T
( */) 72 181 T
(typedef enum xfs_dinode_fmt) 72 170 T
({) 72 159 T
(XFS_DINODE_FMT_AGINO,) 108 148 T
(/* free inodes: di_next */) 221.24 148 T
(XFS_DINODE_FMT_DEV,) 108 137 T
(/* CHR, BLK: di_dev */) 210.46 137 T
(XFS_DINODE_FMT_LOCAL,) 108 126 T
(/* DIR, REG, LNK: di_c */) 221.24 126 T
(XFS_DINODE_FMT_EXTENTS,) 108 115 T
(/* DIR, REG, LNK: di_bmx */) 232.03 115 T
(XFS_DINODE_FMT_BTREE,) 108 104 T
(/* DIR, REG, LNK: di_bmbt */) 221.24 104 T
(XFS_DINODE_FMT_UUID) 108 93 T
(/* MNT: di_uuid */) 215.85 93 T
(} xfs_dinode_fmt_t;) 72 82 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
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(Inode Numbers) 72 42.62 T
(December 16, 1993) 255.07 42.62 T
(7) 500 42.62 T
1 36 Q
4 K
(Inode Numbers) 194.54 696 T
1 18 Q
0 K
(Inode numbers consist of three parts:) 72 648 T
1 14 Q
(1.) 72 624.67 T
(allocation group number) 85.75 624.67 T
(2.) 72 602.67 T
(block number in the allocation group) 85.75 602.67 T
(3.) 72 580.67 T
(index of the inode in its block) 85.75 580.67 T
1 18 Q
(The current layout has:) 72 550 T
2 9 Q
(/*) 72 530 T
( * low sb_inopblog bits - offset in block) 72 519 T
( * next 32 - sb_blocklog bits - block number in allocation group) 72 508 T
( * next 32 bits - allocation group number) 72 497 T
( * high sb_blocklog - sb_inopblog bits - 0) 72 486 T
( */) 72 475 T
1 18 Q
(The layout will be changed soon to have the middle \336eld be) 72 447 T
(shorter) 72 427 T
(, its width will depend on the allocation group size. This) 121.24 427 T
(will allow more inode numbers to \336t in 32 bits.) 72 407 T
(Macros are used to construct and deconstruct inode numbers.) 72 375 T
(The low two \336elds are also referred to as the \322allocation group) 72 355 T
(inode number\323, or xfs_agino_t.) 72 335 T
2 9 Q
(#def) 72 304 T
(ine) 93.57 304 T
(xfs_mask\050k\051) 144 304 T
(\050\0501 << k\051 - 1\051) 216 304 T
(#def) 72 293 T
(ine) 93.57 293 T
(xfs_ino_offset_bits\050s\051) 144 293 T
(\050\050s\051->sb_inopblog\051) 262.63 293 T
(#def) 72 282 T
(ine) 93.57 282 T
(xfs_ino_agbno_bits\050s\051) 144 282 T
(\05032 - \050s\051->sb_blocklog\051) 257.24 282 T
(#def) 72 271 T
(ine) 93.57 271 T
(xfs_ino_agino_bits\050s\051) 144 271 T
(\050xfs_ino_offset_bits\050s\051 + xfs_ino_agbno_bits\050s\051\051) 257.24 271 T
(#def) 72 260 T
(ine) 93.57 260 T
(xfs_ino_agno_bits\050s\051) 144 260 T
(32) 251.85 260 T
(#def) 72 238 T
(ine) 93.57 238 T
(xfs_ino_to_agno\050s,i\051) 144 238 T
(\050\050xfs_agnumber_t\051\050\050i\051 >> xfs_ino_agino_bits\050s\051\051\051) 251.85 238 T
(#def) 72 227 T
(ine) 93.57 227 T
(xfs_ino_to_agino\050s,i\051) 144 227 T
(\050\050xfs_agino_t\051\050i\051 & xfs_mask\050xfs_ino_agino_bits\050s\051\051\051) 257.24 227 T
(#def) 72 216 T
(ine) 93.57 216 T
(xfs_ino_to_agbno\050s,i\051) 144 216 T
(\134) 257.24 216 T
-0.13 ( \050\050\050xfs_agblock_t\051\050i\051 >> xfs_ino_offset_bits\050s\051\051 & xfs_mask\050xfs_ino_agbno_bits\050s\051\051\051) 72 205 P
(#def) 72 194 T
(ine) 93.57 194 T
(xfs_ino_to_offset\050s,i\051) 144 194 T
(\050\050int\051\050i\051 & xfs_mask\050xfs_ino_offset_bits\050s\051\051\051) 262.63 194 T
(#def) 72 172 T
(ine) 93.57 172 T
(xfs_agino_to_ino\050s,a,i\051) 144 172 T
(\050\050\050xfs_ino_t\051\050a\051 << xfs_ino_agino_bits\050s\051\051 | \050i\051\051) 268.03 172 T
(#def) 72 161 T
(ine) 93.57 161 T
(xfs_agino_to_agbno\050s,i\051) 144 161 T
(\050\050i\051 >> xfs_ino_offset_bits\050s\051\051) 268.03 161 T
(#def) 72 150 T
(ine) 93.57 150 T
(xfs_agino_to_offset\050s,i\051) 144 150 T
(\050\050i\051 & xfs_mask\050xfs_ino_offset_bits\050s\051\051\051) 273.42 150 T
(#def) 72 128 T
(ine) 93.57 128 T
(xfs_offbno_to_agino\050s,b,o\051) 144 128 T
( \134) 284.2 128 T
(\050\050xfs_agino_t\051\050\050\050b\051 << xfs_ino_offset_bits\050s\051\051 | \050o\051\051\051) 216 117 T
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
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(Btr) 72 42.62 T
(ee Cursors) 82.51 42.62 T
(December 16, 1993) 255.07 42.62 T
(8) 500 42.62 T
1 36 Q
4 K
(Btree Cursors) 206.53 696 T
1 18 Q
0 K
-0.05 (Our current working position in a btree is recorded in a structure) 72 648 P
(called a \322cursor\323 \050xfs_btree_cur_t\051. The cursor contains identi-) 72 628 T
-0.07 (fying information \050which btree, for example\051 that allows generic) 72 608 P
(code to be useful. It also contains a buf) 72 588 T
(fer pointer for each level) 357.47 588 T
-0.74 (in the btree, and an index number \050pointer\051 of a record within that) 72 568 P
(btree block.) 72 548 T
(Cursors are used as the interface with all btree services. For) 72 516 T
(example, to do a btree insertion, there are the following steps:) 72 496 T
1 14 Q
(1.) 72 472.67 T
(Allocate / initialize a cursor) 85.75 472.67 T
(2.) 72 450.67 T
(Do a lookup to \336nd the insertion location and set the insertion value) 85.75 450.67 T
(3.) 72 428.67 T
(Do an insert operation) 85.75 428.67 T
(4.) 72 406.67 T
(Delete the cursor) 85.75 406.67 T
2 9 Q
(typedef struct xfs_btree_cur) 72 382 T
({) 72 371 T
(xfs_trans_t) 108 360 T
(*bc_tp;) 180 360 T
(/* links cursors on freelist */) 252 360 T
(xfs_mount_t) 108 349 T
(*bc_mp;) 180 349 T
(/* mount struct */) 252 349 T
(buf_t) 108 338 T
(*bc_agbuf;) 180 338 T
(/* ag buffer */) 252 338 T
(xfs_agnumber_t) 108 327 T
(bc_agno;) 183.49 327 T
(/* ag number */) 252 327 T
(union {) 108 316 T
(xfs_alloc_rec_t) 144 305 T
(a;) 252 305 T
(/* btree records */) 288 305 T
(xfs_bmbt_irec_t) 144 294 T
(b;) 252 294 T
(}) 108 283 T
(bc_rec;) 180 283 T
(buf_t) 108 272 T
(*bc_bufs[XFS_BTREE_MAXLEVELS];) 180 272 T
(/* buffer pointers */) 360 272 T
(int) 108 261 T
(bc_ptrs[XFS_BTREE_MAXLEVELS];) 180 261 T
(/* record/pointer numbers */) 360 261 T
(int) 108 250 T
(bc_nlevels;) 180 250 T
(/* number of btree levels */) 252 250 T
(xfs_btnum_t) 108 239 T
(bc_btnum;) 180 239 T
(/* btree identif) 252 239 T
(ier */) 338.28 239 T
(int) 108 228 T
(bc_blocklog;) 180 228 T
(/* block size of f) 252 228 T
(ile system */) 349.06 228 T
(union {) 108 217 T
(struct {) 144 206 T
(int) 180 195 T
(inodesize;) 288 195 T
(/* needed for BMAP */) 360 195 T
(struct xfs_inode) 180 184 T
(*ip;) 288 184 T
(/* needed for BMAP */) 360 184 T
(} b;) 144 173 T
(/* type b private data */) 252 173 T
(}) 108 162 T
(bc_private;) 180 162 T
(/* type-private data */) 252 162 T
(} xfs_btree_cur_t;) 72 151 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
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(Main Btr) 72 42.62 T
(ee Interfaces) 103.05 42.62 T
(December 16, 1993) 255.07 42.62 T
(9) 500 42.62 T
1 36 Q
4 K
(Main Btree Interfaces) 149.08 696 T
1 18 Q
0 K
(Btree code is replicated for extent allocation and \336le space allo-) 72 648 T
(cation. Pre\336x for code is xfs_alloc_ or xfs_bmbt_.) 72 628 T
(The main interfaces are:) 72 596 T
2 9 Q
(int delete\050xfs_btree_cur_t *cur\051;) 72 576 T
(int insert\050xfs_btree_cur_t *cur\051;) 72 565 T
(int lookup_eq\050xfs_btree_cur_t *cur, xfs_agblock_t bno, xfs_extlen_t len\051;) 72 554 T
(int lookup_ge\050xfs_btree_cur_t *cur, xfs_agblock_t bno, xfs_extlen_t len\051;) 72 543 T
(int lookup_le\050xfs_btree_cur_t *cur, xfs_agblock_t bno, xfs_extlen_t len\051;) 72 532 T
(int update\050xfs_btree_cur_t *cur, xfs_agblock_t bno, xfs_extlen_t len\051;) 72 521 T
1 18 Q
-0.62 (The ar) 72 482 P
-0.62 (guments to the lookup and update calls match the elements) 117.5 482 P
(of the btree records: block number and length for the freespace) 72 462 T
(btrees; \336le of) 72 442 T
(fset, block number) 166.61 442 T
(, and length for the bmap btree.) 300.3 442 T
-0.16 (The lookup interfaces specify where \050exactly\051 to stop the search:) 72 410 P
(at a record exactly equal to, less than or equal to, or greater than) 72 390 T
(or equal to the requested record. The lookup_gt and lookup_lt) 72 370 T
(interfaces are not present because none of my code needs them.) 72 350 T
(Insert inserts a record whose value was speci\336ed by the most) 72 318 T
(recent lookup call, or alternatively stored in the cursor by the) 72 298 T
(caller) 72 278 T
(. If the latter method is used, the cursor must still be point-) 110.97 278 T
(ing to the right place in the btree after the most recent lookup.) 72 258 T
(Delete deletes the record last looked up.) 72 226 T
(There are interfaces to adjust the cursor position other than by) 72 194 T
(doing a lookup, given on the next slide.) 72 174 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
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(Btr) 72 42.62 T
(ee Service Routines) 82.51 42.62 T
(December 16, 1993) 255.07 42.62 T
(10) 496 42.62 T
1 36 Q
4 K
(Btree Service Routines) 140.04 696 T
1 18 Q
0 K
(Some of these are lower) 72 648 T
(-level routines in the btree implementa-) 245.5 648 T
(tions, some are secondary interfaces used by the callers of the) 72 628 T
-0.01 (high-level btree interfaces. The xfs_btree_... routines are shared) 72 608 P
(between both implementations.) 72 588 T
2 9 Q
(void xfs_btree_del_cursor\050xfs_btree_cur_t *cur\051;) 72 568 T
(xfs_btree_cur_t *xfs_btree_dup_cursor\050xfs_btree_cur_t *cur\051;) 72 557 T
(int xfs_btree_f) 72 546 T
(irstrec\050xfs_btree_cur_t *cur, int level\051;) 152.89 546 T
-0.16 (xfs_btree_cur_t *xfs_btree_init_cursor\050xfs_mount_t *mp, xfs_trans_t *tp, buf_t *agbuf,) 72 535 P
(xfs_agnumber_t agno, xfs_btnum_t btno, struct xfs_inode *ip\051;) 72 525 T
(int xfs_btree_lastrec\050xfs_btree_cur_t *cur, int level\051;) 72 514 T
(int decrement\050xfs_btree_cur_t *cur, int level\051;) 72 492 T
(int delrec\050xfs_btree_cur_t *cur, int level\051;) 72 481 T
(int get_rec\050xfs_btree_cur_t *cur, xfs_agblock_t *bnop, xfs_extlen_t *lenp\051;) 72 470 T
(int increment\050xfs_btree_cur_t *cur, int level\051;) 72 459 T
-0.73 (int insrec\050xfs_btree_cur_t *cur, int level, xfs_agblock_t *bnop, xfs_alloc_rec_t *recp,) 72 448 P
(xfs_btree_cur_t **curp\051;) 72 438 T
(int lookup\050xfs_btree_cur_t *cur, xfs_lookup_t mode\051;) 72 427 T
(int lshift\050xfs_btree_cur_t *cur, int level\051;) 72 416 T
(int newroot\050xfs_btree_cur_t *cur\051;) 72 405 T
(int rshift\050xfs_btree_cur_t *cur, int level\051;) 72 394 T
-0.13 (int split\050xfs_btree_cur_t *cur, int level, xfs_agblock_t *bnop, xfs_alloc_rec_t *recp,) 72 383 P
(xfs_btree_cur_t **curp\051;) 72 373 T
(void updkey\050xfs_btree_cur_t *cur, xfs_alloc_rec_t *keyp, int level\051;) 72 362 T
1 18 Q
-0.34 (Decrement and increment are used to move around in the tree, as) 72 334 P
(are \050less frequently\051 \336rstrec and lastrec.) 72 314 T
(Insrec and delrec do one level\325) 72 282 T
(s worth of insert/delete for the) 292.31 282 T
(insert/delete routines.) 72 262 T
(Lshift and rshift do balancing \0501 record at a time\051 for insrec and) 72 230 T
(delrec.) 72 210 T
(Split is used by insrec to do block splits.) 72 178 T
(Updkey marches up the tree setting the key values if the \336rst) 72 146 T
(record in a block is changed.) 72 126 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
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(Space Allocation Interfaces) 72 42.62 T
(December 16, 1993) 255.07 42.62 T
(1) 496.44 42.62 T
(1) 500 42.62 T
1 36 Q
4 K
(Space Allocation Interfaces) 107.09 696 T
1 18 Q
0 K
(These interfaces are used to allocate and free extents of disk) 72 648 T
(space.) 72 628 T
2 9 Q
(typedef enum xfs_alloctype) 72 608 T
({) 72 597 T
(XFS_ALLOCTYPE_ANY_AG,) 108 586 T
(/* Any allocation group ok */) 252 586 T
(XFS_ALLOCTYPE_START_AG,) 108 575 T
(/* start with this bno\325s allocation group */) 252 575 T
(XFS_ALLOCTYPE_THIS_AG,) 108 564 T
(/* must be somewhere in bno\325s allocation group */) 252 564 T
(XFS_ALLOCTYPE_NEAR_BNO,) 108 553 T
(/* must be in bno\325s ag and near bno */) 252 553 T
(XFS_ALLOCTYPE_THIS_BNO) 108 542 T
(/* must be at exactly bno */) 252 542 T
(} xfs_alloctype_t;) 72 531 T
(xfs_fsblock_t xfs_alloc_extent\050xfs_trans_t *tp, xfs_fsblock_t bno, xfs_extlen_t len,) 72 509 T
(xfs_alloctype_t f) 72 499 T
(lag\051;) 163.67 499 T
(xfs_agblock_t xfs_alloc_next_free\050xfs_mount_t *mp, xfs_trans_t *tp, buf_t *agbuf,) 72 488 T
(xfs_agblock_t bno\051;) 72 478 T
-0.05 (xfs_fsblock_t xfs_alloc_vextent\050xfs_trans_t *tp, xfs_fsblock_t bno,) 72 467 P
(xfs_extlen_t minlen, xfs_extlen_t maxlen, xfs_extlen_t *len, xfs_alloctype_t f) 72 457 T
(lag\051;) 492.61 457 T
(int xfs_free_extent\050xfs_trans_t *tp, xfs_fsblock_t bno, xfs_extlen_t len\051;) 72 446 T
1 18 Q
(The generic allocation routine is xfs_alloc_vextent \050variable) 72 407 T
(extent\051; xfs_alloc_extent is implemented with it.) 72 387 T
(It is given a transaction, an allocation mode, a minimum and a) 72 355 T
-0.39 (maximum length, and a block number) 72 335 P
-0.39 (. It attempts to allocate the) 342.88 335 P
-0.22 (maximum block it can, less than or equal to maxlen, greater than) 72 315 P
(or equal to minlen.) 72 295 T
-0.62 (The \337ag ar) 72 263 P
-0.62 (gument controls its behavior as given in the comments) 148.36 263 P
(above.) 72 243 T
(The free_extent routine just frees the extent given by bno and) 72 211 T
(len; the frees don\325) 72 191 T
(t have to match the allocations.) 202.07 191 T
(The next_free routine is used to scan the freelist held by this) 72 159 T
(code; it\325) 72 139 T
(s really an internal routine, exposed for the debugging) 130.47 139 T
(code to print the list with.) 72 119 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
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(Space Allocation Internals) 72 42.62 T
(December 16, 1993) 255.07 42.62 T
(12) 496 42.62 T
1 36 Q
4 K
(Space Allocation Internals) 115.06 696 T
1 18 Q
0 K
(Space allocation maintains two btrees representing free space in) 72 648 T
(the \336le system. The btrees are named BNO and CNT) 72 628 T
(. BNO is) 455.89 628 T
(sorted by block number) 72 608 T
(, CNT by extent length. Each contains) 241.66 608 T
(exactly the same data, only in a dif) 72 588 T
(ferent order) 322.49 588 T
(.) 405.91 588 T
(Each allocation \336rst selects an allocation group to allocate from;) 72 556 T
(this is iterative for XFS_ALLOCTYPE_ANY_AG and) 72 536 T
(XFS_ALLOCTYPE_ST) 72 516 T
(AR) 247.48 516 T
(T_AG. Then the routine xfs_allo-) 271.38 516 T
(c_ag_vextent is called, with ar) 72 496 T
(guments as for xfs_alloc_vextent) 291.01 496 T
(plus an allocation group number and buf) 72 476 T
(fer) 363.48 476 T
(. The \337ag ar) 382.45 476 T
(gument) 473.56 476 T
(has been reduced to the three in-allocation group cases.) 72 456 T
(xfs_alloc_ag_vextent reduces to a switch out to routines xfs_al-) 72 424 T
(loc_ag_vextent_{size, near) 72 404 T
(, exact}, plus bookkeeping.) 266.76 404 T
(These three routines implement all the allocation policy) 72 372 T
(.) 472.06 372 T
(xfs_free_extent reduces to some address translation and a call to) 72 340 T
-0.64 (xfs_free_ag_extent. It checks for adjacent freespace, and mer) 72 320 P
-0.64 (ges) 512.16 320 P
(it with the new freespace if present. The two btrees are adjusted) 72 300 T
(by inserts and updates to accomplish this.) 72 280 T
-0.26 (T) 72 248 P
-0.26 (o avoid running out of space in the middle of operations, and to) 81.73 248 P
(avoid calling itself recursively to obtain space, this code main-) 72 228 T
(tains a set of blocks on a list, that it can use.) 72 208 T
FMENDPAGE
%%EndPage: "12" 13
%%Page: "13" 13
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(xfs_alloc_ag_vextent_size \050example\051) 72 42.62 T
(December 16, 1993) 255.07 42.62 T
(13) 496 42.62 T
1 36 Q
4 K
(xfs_alloc_ag_vextent_size) 115.06 696 T
(\050example\051) 233.04 654 T
2 9 Q
0 K
(xfs_agblock_t) 72 612 T
(xfs_alloc_ag_vextent_size\050xfs_trans_t *tp, buf_t *agbuf, xfs_agnumber_t agno, xfs_ex-) 72 601 T
(tlen_t minlen, xfs_extlen_t maxlen, xfs_extlen_t *len\051) 72 591 T
({) 72 580 T
(xfs_btree_cur_t *bno_cur;) 108 569 T
(xfs_btree_cur_t *cnt_cur;) 108 558 T
(xfs_agblock_t fbno;) 108 547 T
(xfs_extlen_t f) 108 536 T
(len = 0;) 183.49 536 T
(int i;) 108 525 T
(xfs_extlen_t rlen;) 108 514 T
(xfs_mount_t *mp;) 108 503 T
(mp = tp->t_mountp;) 108 481 T
(cnt_cur = xfs_btree_init_cursor\050mp, tp, agbuf, agno, XFS_BTNUM_CNT, 0\051;) 108 470 T
(if \050!xfs_alloc_lookup_ge\050cnt_cur, 0, maxlen\051\051 {) 108 459 T
(if \050xfs_alloc_decrement\050cnt_cur, 0\051\051) 144 448 T
(xfs_alloc_get_rec\050cnt_cur, &fbno, &f) 180 437 T
(len\051;) 374.13 437 T
(if \050f) 144 426 T
(len < minlen\051 {) 170.96 426 T
(xfs_btree_del_cursor\050cnt_cur\051;) 180 415 T
(return NULLAGBLOCK;) 180 404 T
(}) 144 393 T
(rlen = f) 144 382 T
(len;) 187.14 382 T
(} else {) 108 371 T
(xfs_alloc_get_rec\050cnt_cur, &fbno, &f) 144 360 T
(len\051;) 338.13 360 T
(rlen = maxlen;) 144 349 T
(}) 108 338 T
(xfs_alloc_delete\050cnt_cur\051;) 108 327 T
(bno_cur = xfs_btree_init_cursor\050mp, tp, agbuf, agno, XFS_BTNUM_BNO, 0\051;) 108 316 T
(i = xfs_alloc_lookup_eq\050bno_cur, fbno, f) 108 305 T
(len\051;) 323.7 305 T
(if \050rlen < f) 108 294 T
(len\051 {) 172.71 294 T
(xfs_alloc_lookup_eq\050cnt_cur, fbno + rlen, f) 144 283 T
(len - rlen\051;) 375.88 283 T
(xfs_alloc_insert\050cnt_cur\051;) 144 272 T
(xfs_alloc_update\050bno_cur, fbno + rlen, f) 144 261 T
(len - rlen\051;) 359.7 261 T
(} else) 108 250 T
(xfs_alloc_delete\050bno_cur\051;) 144 239 T
(*len = rlen;) 108 228 T
(xfs_btree_del_cursor\050bno_cur\051;) 108 217 T
(xfs_btree_del_cursor\050cnt_cur\051;) 108 206 T
(return fbno;) 108 195 T
(}) 72 184 T
FMENDPAGE
%%EndPage: "13" 14
%%Page: "14" 14
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(Inode Allocation Interfaces) 72 42.62 T
(December 16, 1993) 255.07 42.62 T
(14) 496 42.62 T
1 36 Q
4 K
(Inode Allocation Interfaces) 109.09 696 T
1 18 Q
0 K
(Disk inode allocation is done in the layer below xfs_ialloc. The) 72 648 T
-0.01 (routine xfs_dialloc turns a free inode into an allocated inode and) 72 628 P
-0.58 (returns it to the caller) 72 608 P
-0.58 (. It also may allocate more inodes \050turn free) 222.57 608 P
(blocks into inode blocks\051 if necessary) 72 588 T
(.) 342.14 588 T
(xfs_difree is used to turn used inodes into free inodes.) 72 556 T
-0.72 (W) 72 524 P
-0.72 (e never turn free inodes into free blocks, although I suppose we) 87.54 524 P
(could.) 72 504 T
(xfs_dilocate is used to turn an inode number into an inode loca-) 72 472 T
(tion; it is very simple. The inode\325) 72 452 T
(s location is returned in ar) 315.87 452 T
(gu-) 502.92 452 T
(ments bno and of) 72 432 T
(f.) 196.1 432 T
-0.28 (In an earlier version of this code, btrees were used to map inodes) 72 400 P
(to locations; this has all been removed in favor of storing the) 72 380 T
(block numbers in the inode numbers.) 72 360 T
2 9 Q
(xfs_ino_t xfs_dialloc\050xfs_trans_t *tp, xfs_ino_t parent, int sameag, mode_t mode\051;) 72 329 T
(xfs_agino_t xfs_dialloc_next_free\050xfs_mount_t *mp, xfs_trans_t *tp, buf_t *agbuf,) 72 318 T
(xfs_agino_t agino\051;) 72 308 T
(xfs_agino_t xfs_difree\050xfs_trans_t *tp, xfs_ino_t inode\051;) 72 297 T
(int xfs_dilocate\050xfs_mount_t *mp, xfs_trans_t *tp, xfs_ino_t ino, xfs_fsblock_t *bno,) 72 286 T
(int *off\051;) 72 276 T
FMENDPAGE
%%EndPage: "14" 15
%%Page: "15" 15
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(Inode Allocation Internals) 72 42.62 T
(December 16, 1993) 255.07 42.62 T
(15) 496 42.62 T
1 36 Q
4 K
(Inode Allocation Internals) 117.06 696 T
1 18 Q
0 K
(This code is very simple now) 72 648 T
(. There are two internal routines:) 282.2 648 T
2 9 Q
(int /* success/failure */) 72 628 T
(xfs_ialloc_ag_alloc\050xfs_trans_t *tp, /* transaction pointer */) 72 617 T
( buf_t *agbuf\051; /* alloc grp buffer */) 72 606 T
(buf_t * /* allocation group buffer */) 72 584 T
(xfs_ialloc_ag_select\050xfs_trans_t *tp, /* transaction pointer */) 72 573 T
( xfs_ino_t parent, /* parent directory inode number */) 72 562 T
( int sameag, /* =1 to force to same ag. as parent */) 72 551 T
( mode_t mode\051; /* bits set to indicate f) 72 540 T
(ile type */) 422.51 540 T
1 18 Q
(Xfs_ialloc_ag_select is used to select an allocation group to do) 72 501 T
(the inode allocation in; the code in xfs_dialloc iterates through) 72 481 T
(other allocation groups, if the \336rst is unsuccessful, and it isn\325) 72 461 T
(t) 510.4 461 T
(told not to.) 72 441 T
(Xfs_ialloc_ag_alloc allocates new inodes from freespace, if nec-) 72 409 T
(essary to satisfy the xfs_dialloc request.) 72 389 T
(Inodes are allocated in chunks of from 1 block to 256 inodes or) 72 357 T
(16 blocks, whichever is smaller) 72 337 T
(. A variable extent allocation is) 298.35 337 T
(used, where the block number is one past the previously allo-) 72 317 T
(cated inodes.) 72 297 T
FMENDPAGE
%%EndPage: "15" 16
%%Page: "16" 16
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(Block Mapping Interfaces) 72 42.62 T
(December 16, 1993) 255.07 42.62 T
(16) 496 42.62 T
1 36 Q
4 K
(Block Mapping Interfaces) 118.07 696 T
1 18 Q
0 K
(The main interface to block mapping is xfs_bmap. This routine) 72 648 T
(does not exist yet.) 72 628 T
(The routine xfs_bmapi is an inode version of xfs_bmap. It is) 72 596 T
(given an inode, a \336le of) 72 576 T
(fset and length, a read/write \337ag, and an) 241.56 576 T
(array of extent descriptors \050and its size\051. It \336lls in the extent) 72 556 T
(descriptors, and for writes into holes \050or past the end of \336le\051 it) 72 536 T
(allocates space to the \336le as well.) 72 516 T
2 9 Q
(void xfs_bmapi\050xfs_mount_t *mp, xfs_trans_t *tp, struct xfs_inode *ip, xfs_fsblock_t) 72 485 T
(bno, xfs_extlen_t len, int rw, xfs_bmbt_irec_t *maps, int *nmaps\051;) 72 475 T
FMENDPAGE
%%EndPage: "16" 17
%%Page: "17" 17
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(In-cor) 72 42.62 T
(e Inode Format) 92.94 42.62 T
(December 16, 1993) 255.07 42.62 T
(17) 496 42.62 T
1 36 Q
4 K
(In-core Inode Format) 152.07 696 T
1 18 Q
0 K
(Only the portion of the inode relevant to block mapping is dis-) 72 648 T
(cussed here!) 72 628 T
(The inode points to an array of extents, which is sorted by of) 72 596 T
(fset) 508.87 596 T
(in the \336le. This array is generated \050for btree-format \336les\051 by the) 72 576 T
(routine xfs_bmap_read_extents; for extent-format \336les the array) 72 556 T
(lives in the disk inode and is just copied into the incore array) 72 536 T
(.) 508.55 536 T
(For btree-format \336les, the bmap btree root is also pointed to by) 72 504 T
(the incore inode. The btree code manipulates this root just as it) 72 484 T
(manipulates all the other blocks in the tree, with all the macros) 72 464 T
(knowing the dif) 72 444 T
(ference.) 185.61 444 T
FMENDPAGE
%%EndPage: "17" 18
%%Page: "18" 18
612 792 0 FMBEGINPAGE
0 8 Q
0 X
0 K
(Silicon Graphics Pr) 72 750.67 T
(oprietary) 139.57 750.67 T
(Space Manager Overview) 242.42 750.67 T
(Doug Doucette) 450.38 750.67 T
72 54 540 54 2 L
0.25 H
2 Z
N
(Block Mapping Internals) 72 42.62 T
(December 16, 1993) 255.07 42.62 T
(18) 496 42.62 T
1 36 Q
4 K
(Block Mapping Internals) 126.04 696 T
1 18 Q
0 K
-0.29 (Block mapping for extent-format \336les is simple; the extent list in) 72 648 P
-0.81 (core is searched \050binary) 72 628 P
-0.81 (, eventually\051. New records are inserted or) 239.74 628 P
(appended to the list.) 72 608 T
(For btree-format \336les, in addition, the btree must be searched) 72 576 T
(\050xfs_bmbt_lookup_eq\051 and then inserted to or updated depend-) 72 556 T
(ing on whether the new extent is adjacent to the old extents or) 72 536 T
(not. The btree interfaces used are exactly the same as for) 72 516 T
(freespace allocation.) 72 496 T
(xfs_bmapi has four basic sections:) 72 464 T
1 14 Q
(1.) 72 440.67 T
(Figure out where the \336rst extent-list record to look at is.) 85.75 440.67 T
(2.) 72 418.67 T
(Map \050and allocate if necessary\051 the \336le space into \336le system blocks) 85.75 418.67 T
(3.) 72 396.67 T
-0.03 (If the \336le is extents-format and now has too many extents to \336t in the disk inode,) 85.75 396.67 P
(convert the \336le to btree-format.) 85.75 380.67 T
(4.) 72 358.67 T
(Log all the changes.) 85.75 358.67 T
FMENDPAGE
%%EndPage: "18" 19
%%Trailer
%%BoundingBox: 0 0 612 792
%%Pages: 18 1
%%DocumentFonts: Palatino-Roman
%%+ Times-Roman
%%+ Courier
%%+ Courier-Bold
![[BACK]](/icons/back.gif){kind=icon}
Return to space_overview.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