1implement Nametree; 2include "sys.m"; 3 sys: Sys; 4include "styx.m"; 5include "styxservers.m"; 6 Navop: import Styxservers; 7 Enotfound, Eexists: import Styxservers; 8 9Fholder: adt { 10 parentqid: big; 11 d: Sys->Dir; 12 child: cyclic ref Fholder; 13 sibling: cyclic ref Fholder; 14 hash: cyclic ref Fholder; 15}; 16 17init() 18{ 19 sys = load Sys Sys->PATH; 20} 21 22start(): (ref Tree, chan of ref Styxservers->Navop) 23{ 24 fs := ref Tree(chan of ref Treeop, chan of string); 25 c := chan of ref Styxservers->Navop; 26 spawn fsproc(c, fs.c); 27 return (fs, c); 28} 29 30Tree.quit(t: self ref Tree) 31{ 32 t.c <-= nil; 33} 34 35Tree.create(t: self ref Tree, parentq: big, d: Sys->Dir): string 36{ 37 t.c <-= ref Treeop.Create(t.reply, parentq, d); 38 return <-t.reply; 39} 40 41Tree.remove(t: self ref Tree, q: big): string 42{ 43 t.c <-= ref Treeop.Remove(t.reply, q); 44 return <-t.reply; 45} 46 47Tree.wstat(t: self ref Tree, q: big, d: Sys->Dir): string 48{ 49 t.c <-= ref Treeop.Wstat(t.reply, q, d); 50 return <-t.reply; 51} 52 53Tree.getpath(t: self ref Tree, q: big): string 54{ 55 t. c <-= ref Treeop.Getpath(t.reply, q); 56 return <-t.reply; 57} 58 59fsproc(c: chan of ref Styxservers->Navop, fsc: chan of ref Treeop) 60{ 61 tab := array[23] of ref Fholder; 62 63 for (;;) alt { 64 grq := <-c => 65 if (grq == nil) 66 exit; 67 (q, reply) := (grq.path, grq.reply); 68 fh := findfile(tab, q); 69 if (fh == nil) { 70 reply <-= (nil, Enotfound); 71 continue; 72 } 73 pick rq := grq { 74 Stat => 75 reply <-= (ref fh.d, nil); 76 Walk => 77 d := fswalk(tab, fh, rq.name); 78 if (d == nil) 79 reply <-= (nil, Enotfound); 80 else 81 reply <-= (d, nil); 82 Readdir => 83 (start, end) := (rq.offset, rq.offset + rq.count); 84 fh = fh.child; 85 for (i := 0; i < end && fh != nil; i++) { 86 if (i >= start) 87 reply <-= (ref fh.d, nil); 88 fh = fh.sibling; 89 } 90 reply <-= (nil, nil); 91 * => 92 panic(sys->sprint("unknown op %d\n", tagof(grq))); 93 } 94 grq := <-fsc => 95 if (grq == nil) 96 exit; 97 (q, reply) := (grq.q, grq.reply); 98 pick rq := grq { 99 Create => 100 reply <-= fscreate(tab, q, rq.d); 101 Remove => 102 reply <-= fsremove(tab, q); 103 Wstat => 104 reply <-= fswstat(tab, q, rq.d); 105 Getpath => 106 reply <-= fsgetpath(tab, q); 107 * => 108 panic(sys->sprint("unknown fs op %d\n", tagof(grq))); 109 } 110 } 111} 112 113hashfn(q: big, n: int): int 114{ 115 h := int (q % big n); 116 if (h < 0) 117 h += n; 118 return h; 119} 120 121findfile(tab: array of ref Fholder, q: big): ref Fholder 122{ 123 for (fh := tab[hashfn(q, len tab)]; fh != nil; fh = fh.hash) 124 if (fh.d.qid.path == q) 125 return fh; 126 return nil; 127} 128 129fsgetpath(tab: array of ref Fholder, q: big): string 130{ 131 fh := findfile(tab, q); 132 if (fh == nil) 133 return nil; 134 s := fh.d.name; 135 while (fh.parentqid != fh.d.qid.path) { 136 fh = findfile(tab, fh.parentqid); 137 if (fh == nil) 138 return nil; 139 s = fh.d.name + "/" + s; 140 } 141 return s; 142} 143 144fswalk(tab: array of ref Fholder, fh: ref Fholder, name: string): ref Sys->Dir 145{ 146 if (name == "..") 147 return ref findfile(tab, fh.parentqid).d; 148 for (fh = fh.child; fh != nil; fh = fh.sibling) 149 if (fh.d.name == name) 150 return ref fh.d; 151 return nil; 152} 153 154fsremove(tab: array of ref Fholder, q: big): string 155{ 156 prev: ref Fholder; 157 158 # remove from hash table 159 slot := hashfn(q, len tab); 160 for (fh := tab[slot]; fh != nil; fh = fh.hash) { 161 if (fh.d.qid.path == q) 162 break; 163 prev = fh; 164 } 165 if (fh == nil) 166 return Enotfound; 167 if (prev == nil) 168 tab[slot] = fh.hash; 169 else 170 prev.hash = fh.hash; 171 fh.hash = nil; 172 173 # remove from parent's children 174 parent := findfile(tab, fh.parentqid); 175 if (parent != nil) { 176 prev = nil; 177 for (sfh := parent.child; sfh != nil; sfh = sfh.sibling) { 178 if (sfh == fh) 179 break; 180 prev = sfh; 181 } 182 if (sfh == nil) 183 panic("child not found in parent"); 184 if (prev == nil) 185 parent.child = fh.sibling; 186 else 187 prev.sibling = fh.sibling; 188 } 189 fh.sibling = nil; 190 191 # now remove any descendents 192 sibling: ref Fholder; 193 for (sfh := fh.child; sfh != nil; sfh = sibling) { 194 sibling = sfh.sibling; 195 sfh.parentqid = sfh.d.qid.path; # make sure it doesn't disrupt things. 196 fsremove(tab, sfh.d.qid.path); 197 } 198 return nil; 199} 200 201fscreate(tab: array of ref Fholder, q: big, d: Sys->Dir): string 202{ 203 parent := findfile(tab, q); 204 if (findfile(tab, d.qid.path) != nil) 205 return Eexists; 206 # allow creation of a root directory only if its parent is itself 207 if (parent == nil && d.qid.path != q) 208 return Enotfound; 209 fh: ref Fholder; 210 if (parent == nil) 211 fh = ref Fholder(q, d, nil, nil, nil); 212 else { 213 if (fswalk(tab, parent, d.name) != nil) 214 return Eexists; 215 fh = ref Fholder(parent.d.qid.path, d, nil, nil, nil); 216 fh.sibling = parent.child; 217 parent.child = fh; 218 } 219 slot := hashfn(d.qid.path, len tab); 220 fh.hash = tab[slot]; 221 tab[slot] = fh; 222 return nil; 223} 224 225fswstat(tab: array of ref Fholder, q: big, d: Sys->Dir): string 226{ 227 fh := findfile(tab, q); 228 if (fh == nil) 229 return Enotfound; 230 231 d = applydir(d, fh.d); 232 233 # if renaming a file, check for duplicates 234 if (d.name != fh.d.name) { 235 parent := findfile(tab, fh.parentqid); 236 if (parent != nil && parent != fh && fswalk(tab, parent, d.name) != nil) 237 return Eexists; 238 } 239 fh.d = d; 240 fh.d.qid.path = q; # ensure the qid can't be changed 241 return nil; 242} 243 244applydir(d: Sys->Dir, onto: Sys->Dir): Sys->Dir 245{ 246 if (d.name != nil) 247 onto.name = d.name; 248 if (d.uid != nil) 249 onto.uid = d.uid; 250 if (d.gid != nil) 251 onto.gid = d.gid; 252 if (d.muid != nil) 253 onto.muid = d.muid; 254 if (d.qid.vers != ~0) 255 onto.qid.vers = d.qid.vers; 256 if (d.qid.qtype != ~0) 257 onto.qid.qtype = d.qid.qtype; 258 if (d.mode != ~0) 259 onto.mode = d.mode; 260 if (d.atime != ~0) 261 onto.atime = d.atime; 262 if (d.mtime != ~0) 263 onto.mtime = d.mtime; 264 if (d.length != ~big 0) 265 onto.length = d.length; 266 if (d.dtype != ~0) 267 onto.dtype = d.dtype; 268 if (d.dev != ~0) 269 onto.dev = d.dev; 270 return onto; 271} 272 273panic(s: string) 274{ 275 sys->fprint(sys->fildes(2), "panic: %s\n", s); 276 raise "panic"; 277} 278