Interim commit, compiles. We need to bring in support code now.
[akaros.git] / kern / src / ns / chan.c
1 // INFERNO
2 #include <vfs.h>
3 #include <kfs.h>
4 #include <slab.h>
5 #include <kmalloc.h>
6 #include <kref.h>
7 #include <string.h>
8 #include <stdio.h>
9 #include <assert.h>
10 #include <error.h>
11 #include <cpio.h>
12 #include <pmap.h>
13 #include <smp.h>
14 #include <syscall.h>
15
16 char*
17 channame(struct chan *c)                /* DEBUGGING */
18 {
19         if(c == NULL)
20                 return "<NULL chan>";
21         if(c->name == NULL)
22                 return "<NULL name>";
23         if(c->name->s == NULL)
24                 return "<NULL name.s>";
25         return c->name->s;
26 }
27
28 enum
29 {
30         CNAMESLOP       = 20
31 };
32
33 struct
34 {
35         spinlock_t lock;
36         int     fid;
37         struct chan     *free;
38         struct chan     *list;
39 }chanalloc;
40
41 typedef struct Elemlist Elemlist;
42
43 struct Elemlist
44 {
45         char    *name;  /* copy of name, so '/' can be overwritten */
46         int     ARRAY_SIZEs;
47         char    **elems;
48         int     *off;
49         int     mustbedir;
50 };
51
52 #define SEP(c) ((c) == 0 || (c) == '/')
53 void cleancname(struct cname*);
54
55 int
56 isdotdot(char *p)
57 {
58         return p[0]=='.' && p[1]=='.' && p[2]=='\0';
59 }
60
61 int
62 emptystr(char *s)
63 {
64         if(s == NULL)
65                 return 1;
66         if(s[0] == '\0')
67                 return 1;
68         return 0;
69 }
70
71 /*
72  * Atomically replace *p with copy of s
73  */
74 void
75 kstrdup(char **p, char *s)
76 {
77         int n;
78         char *t, *prev;
79
80         n = strlen(s)+1;
81         /* if it's a user, we can wait for memory; if not, something's very wrong */
82         if (current) {
83                 t = kzmalloc(n, 0);
84         }else{
85                 t = kzmalloc(n, 0);
86                 if(t == NULL)
87                         panic("kstrdup: no memory");
88         }
89         memmove(t, s, n);
90         prev = *p;
91         *p = t;
92         kfree(prev);
93 }
94
95 void
96 chandevreset(void)
97 {
98         int i;
99
100         for(i=0; devtab[i] != NULL; i++)
101                 devtab[i]->reset();
102 }
103
104 void
105 chandevinit(void)
106 {
107         int i;
108
109         for(i=0; devtab[i] != NULL; i++)
110                 devtab[i]->init();
111 }
112
113 void
114 chandevshutdown(void)
115 {
116         int i;
117         
118         /* shutdown in reverse order */
119         for(i=0; devtab[i] != NULL; i++)
120                 ;
121         for(i--; i >= 0; i--)
122                 devtab[i]->shutdown();
123 }
124
125 struct chan*
126 newchan(void)
127 {
128         struct chan *c;
129
130         spin_lock(&(&chanalloc)->lock);
131         c = chanalloc.free;
132         if(c != 0)
133                 chanalloc.free = c->next;
134         spin_unlock(&(&chanalloc)->lock);
135
136         if(c == NULL) {
137                 c = kzmalloc(sizeof(struct chan), 0);
138                 spin_lock(&(&chanalloc)->lock);
139                 c->fid = ++chanalloc.fid;
140                 c->link = chanalloc.list;
141                 chanalloc.list = c;
142                 spin_unlock(&(&chanalloc)->lock);
143         }
144
145         /* if you get an error before associating with a dev,
146            close calls rootclose, a nop */
147         c->type = 0;
148         c->flag = 0;
149         kref_init(&c->ref, fake_release, 1);
150         c->dev = 0;
151         c->offset = 0;
152         c->iounit = 0;
153         c->umh = 0;
154         c->uri = 0;
155         c->dri = 0;
156         c->aux = 0;
157         c->mchan = 0;
158         c->mcp = 0;
159         c->mux = 0;
160         c->mqid.path = 0;
161         c->mqid.vers = 0;
162         c->mqid.type = 0;
163         c->name = 0;
164         return c;
165 }
166
167 static struct kref ncname;
168
169 struct cname*
170 newcname(char *s)
171 {
172         struct cname *n;
173         int i;
174
175         n = kzmalloc(sizeof(*n), 0);
176         i = strlen(s);
177         n->len = i;
178         n->alen = i+CNAMESLOP;
179         n->s = kzmalloc(n->alen, 0);
180         memmove(n->s, s, i+1);
181         kref_init(&n->ref, fake_release, 1);
182         kref_get(&n->ref, 1);
183         return n;
184 }
185
186 void
187 cnameclose(struct cname *n)
188 {
189         if(n == NULL)
190                 return;
191         if(kref_put(&n->ref))
192                 return;
193         kref_put(&n->ref);
194         kfree(n->s);
195         kfree(n);
196 }
197
198 struct cname*
199 addelem(struct cname *n, char *s)
200 {
201         int i, a;
202         char *t;
203         struct cname *new;
204
205         if(s[0]=='.' && s[1]=='\0')
206                 return n;
207
208         if(kref_refcnt(&n->ref) > 1){
209                 /* copy on write */
210                 new = newcname(n->s);
211                 cnameclose(n);
212                 n = new;
213         }
214
215         i = strlen(s);
216         if(n->len+1+i+1 > n->alen){
217                 a = n->len+1+i+1 + CNAMESLOP;
218                 t = kzmalloc(a, 0);
219                 memmove(t, n->s, n->len+1);
220                 kfree(n->s);
221                 n->s = t;
222                 n->alen = a;
223         }
224         if(n->len>0 && n->s[n->len-1]!='/' && s[0]!='/')        /* don't insert extra slash if one is present */
225                 n->s[n->len++] = '/';
226         memmove(n->s+n->len, s, i+1);
227         n->len += i;
228         if(isdotdot(s))
229                 cleancname(n);
230         return n;
231 }
232
233 void
234 chanfree(struct chan *c)
235 {
236         c->flag = CFREE;
237
238         if(c->umh != NULL){
239                 putmhead(c->umh);
240                 c->umh = NULL;
241         }
242         if(c->umc != NULL){
243                 cclose(c->umc);
244                 c->umc = NULL;
245         }
246         if(c->mux != NULL){
247                 //
248                 muxclose(c->mux);
249                 c->mux = NULL;
250         }
251         if(c->mchan != NULL){
252                 cclose(c->mchan);
253                 c->mchan = NULL;
254         }
255
256         cnameclose(c->name);
257
258         spin_lock(&(&chanalloc)->lock);
259         c->next = chanalloc.free;
260         chanalloc.free = c;
261         spin_unlock(&(&chanalloc)->lock);
262 }
263
264 void
265 cclose(struct chan *c)
266 {
267         ERRSTACK(2);
268         if(c == 0)
269                 return;
270
271         if(c->flag&CFREE)
272                 panic("cclose %lux", getcallerpc(&c));
273
274         if(kref_put(&c->ref))
275                 return;
276
277         if(!waserror()){
278                 devtab[c->type]->close(c);
279                 poperror();
280         }
281         chanfree(c);
282 }
283
284 /*
285  * Make sure we have the only copy of c.  (Copy on write.)
286  */
287 struct chan*
288 cunique(struct chan *c)
289 {
290         struct chan *nc;
291
292         if(kref_refcnt(&c->ref) != 1) {
293                 nc = cclone(c);
294                 cclose(c);
295                 c = nc;
296         }
297
298         return c;
299 }
300
301 int
302 eqqid(struct qid a, struct qid b)
303 {
304         return a.path==b.path && a.vers==b.vers;
305 }
306
307 int
308 eqchan(struct chan *a, struct chan *b, int pathonly)
309 {
310         if(a->qid.path != b->qid.path)
311                 return 0;
312         if(!pathonly && a->qid.vers!=b->qid.vers)
313                 return 0;
314         if(a->type != b->type)
315                 return 0;
316         if(a->dev != b->dev)
317                 return 0;
318         return 1;
319 }
320
321 int
322 eqchantdqid(struct chan *a, int type, int dev, struct qid qid, int pathonly)
323 {
324         if(a->qid.path != qid.path)
325                 return 0;
326         if(!pathonly && a->qid.vers!=qid.vers)
327                 return 0;
328         if(a->type != type)
329                 return 0;
330         if(a->dev != dev)
331                 return 0;
332         return 1;
333 }
334
335 struct mhead*
336 newmhead(struct chan *from)
337 {
338         struct mhead *mh;
339
340         mh = kzmalloc(sizeof(struct mhead), 0);
341         kref_init(&mh->ref, fake_release, 1);
342         mh->from = from;
343         kref_get(&from->ref, 1);
344
345 /*
346         n = from->name->len;
347         if(n >= sizeof(mh->fromname))
348                 n = sizeof(mh->fromname)-1;
349         memmove(mh->fromname, from->name->s, n);
350         mh->fromname[n] = 0;
351 */
352         return mh;
353 }
354
355 int
356 cmount(struct chan *new, struct chan *old, int flag, char *spec)
357 {
358         ERRSTACK(2);
359         struct pgrp *pg;
360         int order, flg;
361         struct mhead *m, **l, *mh;
362         struct mount *nm, *f, *um, **h;
363
364         if(QTDIR & (old->qid.type^new->qid.type))
365                 error(Emount);
366
367 if(old->umh)
368         printd("cmount old extra umh\n");
369
370         order = flag&MORDER;
371
372         if((old->qid.type&QTDIR)==0 && order != MREPL)
373                 error(Emount);
374
375         mh = new->umh;
376
377         /*
378          * Not allowed to bind when the old directory
379          * is itself a union.  (Maybe it should be allowed, but I don't see
380          * what the semantics would be.)
381          *
382          * We need to check mh->mount->next to tell unions apart from
383          * simple mount points, so that things like
384          *      mount -c fd /root
385          *      bind -c /root /
386          * work.  The check of mount->mflag catches things like
387          *      mount fd /root
388          *      bind -c /root /
389          * 
390          * This is far more complicated than it should be, but I don't
391          * see an easier way at the moment.             -rsc
392          */
393         if((flag&MCREATE) && mh && mh->mount
394         && (mh->mount->next || !(mh->mount->mflag&MCREATE)))
395                 error(Emount);
396
397         pg = current->pgrp;
398         wlock(&pg->ns);
399
400         l = &MOUNTH(pg, old->qid);
401         for(m = *l; m; m = m->hash) {
402                 if(eqchan(m->from, old, 1))
403                         break;
404                 l = &m->hash;
405         }
406
407         if(m == NULL) {
408                 /*
409                  *  nothing mounted here yet.  create a mount
410                  *  head and add to the hash table.
411                  */
412                 m = newmhead(old);
413                 *l = m;
414
415                 /*
416                  *  if this is a union mount, add the old
417                  *  node to the mount chain.
418                  */
419                 if(order != MREPL)
420                         m->mount = newmount(m, old, 0, 0);
421         }
422         wlock(&m->lock);
423         if(waserror()){
424                 wunlock(&m->lock);
425                 nexterror();
426         }
427         wunlock(&pg->ns);
428
429         nm = newmount(m, new, flag, spec);
430         if(mh != NULL && mh->mount != NULL) {
431                 /*
432                  *  copy a union when binding it onto a directory
433                  */
434                 flg = order;
435                 if(order == MREPL)
436                         flg = MAFTER;
437                 h = &nm->next;
438                 um = mh->mount;
439                 for(um = um->next; um; um = um->next) {
440                         f = newmount(m, um->to, flg, um->spec);
441                         *h = f;
442                         h = &f->next;
443                 }
444         }
445
446         if(m->mount && order == MREPL) {
447                 mountfree(m->mount);
448                 m->mount = 0;
449         }
450
451         if(flag & MCREATE)
452                 nm->mflag |= MCREATE;
453
454         if(m->mount && order == MAFTER) {
455                 for(f = m->mount; f->next; f = f->next)
456                         ;
457                 f->next = nm;
458         }
459         else {
460                 for(f = nm; f->next; f = f->next)
461                         ;
462                 f->next = m->mount;
463                 m->mount = nm;
464         }
465
466         wunlock(&m->lock);
467         poperror();
468         return nm->mountid;
469 }
470
471 void
472 cunmount(struct chan *mnt, struct chan *mounted)
473 {
474         struct pgrp *pg;
475         struct mhead *m, **l;
476         struct mount *f, **p;
477
478         if(mnt->umh)    /* should not happen */
479                 printd("cunmount newp extra umh %p has %p\n", mnt, mnt->umh);
480
481         /*
482          * It _can_ happen that mounted->umh is non-NULL, 
483          * because mounted is the result of namec(Aopen)
484          * (see sysfile.c:/^sysunmount).
485          * If we open a union directory, it will have a umh.
486          * Although surprising, this is okay, since the
487          * cclose will take care of freeing the umh.
488          */
489
490         pg = current->pgrp;
491         wlock(&pg->ns);
492
493         l = &MOUNTH(pg, mnt->qid);
494         for(m = *l; m; m = m->hash) {
495                 if(eqchan(m->from, mnt, 1))
496                         break;
497                 l = &m->hash;
498         }
499
500         if(m == 0) {
501                 wunlock(&pg->ns);
502                 error(Eunmount);
503         }
504
505         wlock(&m->lock);
506         if(mounted == 0) {
507                 *l = m->hash;
508                 wunlock(&pg->ns);
509                 mountfree(m->mount);
510                 m->mount = NULL;
511                 cclose(m->from);
512                 wunlock(&m->lock);
513                 putmhead(m);
514                 return;
515         }
516
517         p = &m->mount;
518         for(f = *p; f; f = f->next) {
519                 /* BUG: Needs to be 2 pass */
520                 if(eqchan(f->to, mounted, 1) ||
521                   (f->to->mchan && eqchan(f->to->mchan, mounted, 1))) {
522                         *p = f->next;
523                         f->next = 0;
524                         mountfree(f);
525                         if(m->mount == NULL) {
526                                 *l = m->hash;
527                                 cclose(m->from);
528                                 wunlock(&m->lock);
529                                 wunlock(&pg->ns);
530                                 putmhead(m);
531                                 return;
532                         }
533                         wunlock(&m->lock);
534                         wunlock(&pg->ns);
535                         return;
536                 }
537                 p = &f->next;
538         }
539         wunlock(&m->lock);
540         wunlock(&pg->ns);
541         error(Eunion);
542 }
543
544 struct chan*
545 cclone(struct chan *c)
546 {
547         struct chan *nc;
548         struct walkqid *wq;
549
550         wq = devtab[c->type]->walk(c, NULL, NULL, 0);
551         if(wq == NULL)
552                 error("clone failed");
553         nc = wq->clone;
554         kfree(wq);
555         nc->name = c->name;
556         if(c->name)
557                 kref_get(&c->name->ref, 1);
558         return nc;
559 }
560
561 int
562 findmount(struct chan **cp,
563           struct mhead **mp, int type, int dev, struct qid qid)
564 {
565         struct pgrp *pg;
566         struct mhead *m;
567
568         pg = current->pgrp;
569         rlock(&pg->ns);
570         for(m = MOUNTH(pg, qid); m; m = m->hash){
571                 rlock(&m->lock);
572 if(m->from == NULL){
573         printd("m %p m->from 0\n", m);
574         runlock(&m->lock);
575         continue;
576 }
577                 if(eqchantdqid(m->from, type, dev, qid, 1)) {
578                         runlock(&pg->ns);
579                         if(mp != NULL){
580                                 kref_get(&m->ref, 1);
581                                 if(*mp != NULL)
582                                         putmhead(*mp);
583                                 *mp = m;
584                         }
585                         if(*cp != NULL)
586                                 cclose(*cp);
587                         kref_get(&m->mount->to->ref, 1);
588                         *cp = m->mount->to;
589                         runlock(&m->lock);
590                         return 1;
591                 }
592                 runlock(&m->lock);
593         }
594
595         runlock(&pg->ns);
596         return 0;
597 }
598
599 int
600 domount(struct chan **cp, struct mhead **mp)
601 {
602         return findmount(cp, mp, (*cp)->type, (*cp)->dev, (*cp)->qid);
603 }
604
605 struct chan*
606 undomount(struct chan *c, struct cname *name)
607 {
608         ERRSTACK(2);
609         struct chan *nc;
610         struct pgrp *pg;
611         struct mount *t;
612         struct mhead **h, **he, *f;
613
614         pg = current->pgrp;
615         rlock(&pg->ns);
616         if(waserror()) {
617                 runlock(&pg->ns);
618                 nexterror();
619         }
620
621         he = &pg->mnthash[MNTHASH];
622         for(h = pg->mnthash; h < he; h++) {
623                 for(f = *h; f; f = f->hash) {
624                         if(strcmp(f->from->name->s, name->s) != 0)
625                                 continue;
626                         for(t = f->mount; t; t = t->next) {
627                                 if(eqchan(c, t->to, 1)) {
628                                         /*
629                                          * We want to come out on the left hand side of the mount
630                                          * point using the element of the union that we entered on.
631                                          * To do this, find the element that has a from name of
632                                          * c->name->s.
633                                          */
634                                         if(strcmp(t->head->from->name->s, name->s) != 0)
635                                                 continue;
636                                         nc = t->head->from;
637                                         kref_get(&nc->ref, 1);
638                                         cclose(c);
639                                         c = nc;
640                                         break;
641                                 }
642                         }
643                 }
644         }
645         poperror();
646         runlock(&pg->ns);
647         return c;
648 }
649
650 /*
651  * Either walks all the way or not at all.  No partial results in *cp.
652  * *nerror is the number of names to display in an error message.
653  */
654 static char Edoesnotexist[] = "does not exist";
655 int
656 walk(struct chan **cp, char **names, int nnames, int nomount, int *nerror)
657 {
658         int dev, dotdot, i, n, nhave, ntry, type;
659         struct chan *c, *nc;
660         struct cname *cname;
661         struct mount *f;
662         struct mhead *mh, *nmh;
663         struct walkqid *wq;
664
665         c = *cp;
666         kref_get(&c->ref, 1);
667         cname = c->name;
668         kref_get(&cname->ref, 1);
669         mh = NULL;
670
671         /*
672          * While we haven't gotten all the way down the path:
673          *    1. step through a mount po int unused_int, if any
674          *    2. send a walk request for initial dotdot or initial prefix without dotdot
675          *    3. move to the first mountpoint along the way.
676          *    4. repeat.
677          *
678          * An invariant is that each time through the loop, c is on the undomount
679          * side of the mount po int unused_int, and c's name is cname.
680          */
681         for(nhave=0; nhave<nnames; nhave+=n){
682                 if((c->qid.type&QTDIR)==0){
683                         if(nerror)
684                                 *nerror = nhave;
685                         cnameclose(cname);
686                         cclose(c);
687                         set_errstr(Enotdir);
688                         if(mh != NULL)
689                                 putmhead(mh);
690                         return -1;
691                 }
692                 ntry = nnames - nhave;
693                 if(ntry > MAXWELEM)
694                         ntry = MAXWELEM;
695                 dotdot = 0;
696                 for(i=0; i<ntry; i++){
697                         if(isdotdot(names[nhave+i])){
698                                 if(i==0) {
699                                         dotdot = 1;
700                                         ntry = 1;
701                                 } else
702                                         ntry = i;
703                                 break;
704                         }
705                 }
706
707                 if(!dotdot && !nomount)
708                         domount(&c, &mh);
709
710                 type = c->type;
711                 dev = c->dev;
712
713                 if((wq = devtab[type]->walk(c, NULL, names+nhave, ntry)) == NULL){
714                         /* try a union mount, if any */
715                         if(mh && !nomount){
716                                 /*
717                                  * mh->mount == c, so start at mh->mount->next
718                                  */
719                                 rlock(&mh->lock);
720                                 for(f = mh->mount->next; f; f = f->next)
721                                         if((wq = devtab[f->to->type]->walk(f->to, NULL, names+nhave, ntry)) != NULL)
722                                                 break;
723                                 runlock(&mh->lock);
724                                 if(f != NULL){
725                                         type = f->to->type;
726                                         dev = f->to->dev;
727                                 }
728                         }
729                         if(wq == NULL){
730                                 cclose(c);
731                                 cnameclose(cname);
732                                 if(nerror)
733                                         *nerror = nhave+1;
734                                 if(mh != NULL)
735                                         putmhead(mh);
736                                 return -1;
737                         }
738                 }
739
740                 nmh = NULL;
741                 if(dotdot) {
742                         assert(wq->nqid == 1);
743                         assert(wq->clone != NULL);
744
745                         cname = addelem(cname, "..");
746                         nc = undomount(wq->clone, cname);
747                         n = 1;
748                 } else {
749                         nc = NULL;
750                         if(!nomount)
751                                 for(i=0; i<wq->nqid && i<ntry-1; i++)
752                                         if(findmount(&nc, &nmh, type, dev, wq->qid[i]))
753                                                 break;
754                         if(nc == NULL){ /* no mount points along path */
755                                 if(wq->clone == NULL){
756                                         cclose(c);
757                                         cnameclose(cname);
758                                         if(wq->nqid==0 || (wq->qid[wq->nqid-1].type&QTDIR)){
759                                                 if(nerror)
760                                                         *nerror = nhave+wq->nqid+1;
761                                                 set_errstr(Edoesnotexist);
762                                         }else{
763                                                 if(nerror)
764                                                         *nerror = nhave+wq->nqid;
765                                                 set_errstr(Enotdir);
766                                         }
767                                         kfree(wq);
768                                         if(mh != NULL)
769                                                 putmhead(mh);
770                                         return -1;
771                                 }
772                                 n = wq->nqid;
773                                 nc = wq->clone;
774                         }else{          /* stopped early, at a mount point */
775                                 if(wq->clone != NULL){
776                                         cclose(wq->clone);
777                                         wq->clone = NULL;
778                                 }
779                                 n = i+1;
780                         }
781                         for(i=0; i<n; i++)
782                                 cname = addelem(cname, names[nhave+i]);
783                 }
784                 cclose(c);
785                 c = nc;
786                 putmhead(mh);
787                 mh = nmh;
788                 kfree(wq);
789         }
790
791         putmhead(mh);
792
793         c = cunique(c);
794
795         if(c->umh != NULL){     //BUG
796                 printd("walk umh\n");
797                 putmhead(c->umh);
798                 c->umh = NULL;
799         }
800
801         cnameclose(c->name);
802         c->name = cname;
803
804         cclose(*cp);
805         *cp = c;
806         if(nerror)
807                 *nerror = 0;
808         return 0;
809 }
810
811 /*
812  * c is a mounted non-creatable directory.  find a creatable one.
813  */
814 struct chan*
815 createdir(struct chan *c, struct mhead *m)
816 {
817         ERRSTACK(2);
818         struct chan *nc;
819         struct mount *f;
820
821         rlock(&m->lock);
822         if(waserror()) {
823                 runlock(&m->lock);
824                 nexterror();
825         }
826         for(f = m->mount; f; f = f->next) {
827                 if(f->mflag&MCREATE) {
828                         nc = cclone(f->to);
829                         runlock(&m->lock);
830                         poperror();
831                         cclose(c);
832                         return nc;
833                 }
834         }
835         error(Enocreate);
836         return 0;
837 }
838
839 /*
840  * In place, rewrite name to compress multiple /, eliminate ., and process ..
841  */
842 void
843 cleancname(struct cname *n)
844 {
845         char *p;
846
847         if(n->s[0] == '#'){
848                 p = strchr(n->s, '/');
849                 if(p == NULL)
850                         return;
851                 cleanname(p);
852
853                 /*
854                  * The correct name is #i rather than #i/,
855                  * but the correct name of #/ is #/.
856                  */
857                 if(strcmp(p, "/")==0 && n->s[1] != '/')
858                         *p = '\0';
859         }else
860                 cleanname(n->s);
861         n->len = strlen(n->s);
862 }
863
864 static void
865 growparse(Elemlist *e)
866 {
867         char **new;
868         int *inew;
869         enum { Delta = 8 };
870
871         if(e->ARRAY_SIZEs % Delta == 0){
872                 new = kzmalloc((e->ARRAY_SIZEs + Delta) * sizeof(char *), 0);
873                 memmove(new, e->elems, e->ARRAY_SIZEs*sizeof( char *));
874                 kfree(e->elems);
875                 e->elems = new;
876                 inew = kzmalloc((e->ARRAY_SIZEs + Delta + 1) * sizeof(int), 0);
877                 memmove(inew, e->off, e->ARRAY_SIZEs*sizeof(int));
878                 kfree(e->off);
879                 e->off = inew;
880         }
881 }
882
883 /*
884  * The name is known to be valid.
885  * Copy the name so slashes can be overwritten.
886  * An empty string will set ARRAY_SIZE=0.
887  * A path ending in / or /. or /.//./ etc. will have
888  * e.mustbedir = 1, so that we correctly
889  * reject, e.g., "/adm/users/." when /adm/users is a file
890  * rather than a directory.
891  */
892 static void
893 parsename(char *name, Elemlist *e)
894 {
895         char *slash;
896
897         kstrdup(&e->name, name);
898         name = e->name;
899         e->ARRAY_SIZEs = 0;
900         e->elems = NULL;
901         e->off = kzmalloc(sizeof(int), 0);
902         e->off[0] = skipslash(name) - name;
903         for(;;){
904                 name = skipslash(name);
905                 if(*name=='\0'){
906                         e->mustbedir = 1;
907                         break;
908                 }
909                 growparse(e);
910                 
911                 e->elems[e->ARRAY_SIZEs++] = name;
912                 /* we may want to do this again some day
913                 slash = utfrune(name, '/');
914                 */
915                 slash = index(name, '/');
916                 if(slash == NULL){
917                         e->off[e->ARRAY_SIZEs] = name+strlen(name) - e->name;
918                         e->mustbedir = 0;
919                         break;
920                 }
921                 e->off[e->ARRAY_SIZEs] = slash - e->name;
922                 *slash++ = '\0';
923                 name = slash;
924         }
925 }
926
927 void*
928 memrchr(void *va, int c, long n)
929 {
930         uint8_t *a, *e;
931
932         a = va;
933         for(e=a+n-1; e>a; e--)
934                 if(*e == c)
935                         return e;
936         return NULL;
937 }
938
939 /*
940  * Turn a name into a channel.
941  * &name[0] is known to be a valid address.  It may be a kernel address.
942  *
943  * Opening with amode Aopen, Acreate, or Aremove guarantees
944  * that the result will be the only reference to that particular fid.
945  * This is necessary since we might pass the result to
946  * devtab[]->remove().
947  *
948  * Opening Atodir, Amount, or Aaccess does not guarantee this.
949  *
950  * Opening Aaccess can, under certain conditions, return a
951  * correct Chan* but with an incorrect struct cname attached.
952  * Since the functions that open Aaccess (sysstat, syswstat, sys_stat)
953  * do not use the struct cname*, this avoids an unnecessary clone.
954  */
955 struct chan*
956 namec(char *aname, int amode, int omode, uint32_t perm)
957 {
958         ERRSTACK(4);
959         int n, prefix, len, t, nomount, npath;
960         struct chan *c, *cnew;
961         struct cname *cname;
962         Elemlist e;
963         struct mhead *m;
964         char *createerr, tmperrbuf[ERRMAX];
965         char *name;
966         // Rune r;
967
968         name = aname;
969         if(name[0] == '\0')
970                 error("empty file name");
971         validname(name, 1);
972
973         /*
974          * Find the starting off point (the current slash, the root of
975          * a device tree, or the current dot) as well as the name to
976          * evaluate starting there.
977          */
978         nomount = 0;
979         switch(name[0]){
980         case '/':
981                 c = current->pgrp->slash;
982                 kref_get(&c->ref, 1);
983                 break;
984         
985         case '#':
986                 nomount = 1;
987                 get_cur_genbuf()[0] = '\0';
988                 n = 0;
989                 while(*name!='\0' && (*name != '/' || n < 2)){
990                         if(n >= sizeof(get_cur_genbuf())-1)
991                                 error(Efilename);
992                         get_cur_genbuf()[n++] = *name++;
993                 }
994                 get_cur_genbuf()[n] = '\0';
995 #if 0
996                 n = chartorune(&r, get_cur_genbuf()+1)+1;
997                 if(r == 'M')
998                         error(Enoattach);
999 #endif
1000                 if (get_cur_genbuf()[1] == 'M')
1001                         error(Enoattach);
1002                 /*
1003                  *  the nodevs exceptions are
1004                  *      |  it only gives access to pipes you create
1005                  *      e  this process's environment
1006                  *      s  private file2chan creation space
1007                  *      D private secure sockets name space
1008                  *      a private TLS name space
1009                  */
1010                 if(current->pgrp->nodevs &&
1011                    //              (utfrune("|esDa", r) == NULL
1012                    ((index("|esDa", get_cur_genbuf()[1]) == NULL)
1013                     || (get_cur_genbuf()[1] == 's' // || r == 's'
1014                         && get_cur_genbuf()[n]!='\0')))
1015                         error(Enoattach);
1016                 t = devno(/*r*/get_cur_genbuf()[1], 1);
1017                 if(t == -1)
1018                         error(Ebadsharp);
1019                 c = devtab[t]->attach(get_cur_genbuf()+n);
1020                 break;
1021
1022         default:
1023                 c = current->pgrp->dot;
1024                 kref_get(&c->ref, 1);
1025                 break;
1026         }
1027         prefix = name - aname;
1028
1029         e.name = NULL;
1030         e.elems = NULL;
1031         e.off = NULL;
1032         e.ARRAY_SIZEs = 0;
1033         if(waserror()){
1034                 cclose(c);
1035                 kfree(e.name);
1036                 kfree(e.elems);
1037                 kfree(e.off);
1038 //dumpmount();
1039                 nexterror();
1040         }
1041
1042         /*
1043          * Build a list of elements in the path.
1044          */
1045         parsename(name, &e);
1046
1047         /*
1048          * On create, ....
1049          */
1050         if(amode == Acreate){
1051                 /* perm must have DMDIR if last element is / or /. */
1052                 if(e.mustbedir && !(perm&DMDIR)){
1053                         npath = e.ARRAY_SIZEs;
1054                         strncpy(tmperrbuf,  "create without DMDIR", sizeof(tmperrbuf));
1055                         goto NameError;
1056                 }
1057
1058                 /* don't try to walk the last path element just yet. */
1059                 if(e.ARRAY_SIZEs == 0)
1060                         error(Eexist);
1061                 e.ARRAY_SIZEs--;
1062         }
1063
1064         if(walk(&c, e.elems, e.ARRAY_SIZEs, nomount, &npath) < 0){
1065                 if(npath < 0 || npath > e.ARRAY_SIZEs){
1066                         printd("namec %s walk error npath=%d\n", aname, npath);
1067                         nexterror();
1068                 }
1069 #warning "fix this mess with errstr and walking"
1070 #if 0
1071                 strncpy(tmperrbuf,  current->errstr, sizeof(tmperrbuf));
1072 #endif
1073         NameError:
1074 #if 0
1075                 len = prefix+e.off[npath];
1076                 if(len < ERRMAX/3 || (name=memrchr(aname, '/', len))==NULL || name==aname)
1077                         snprintf(get_cur_genbuf(), sizeof current->genbuf, "%.*s", len, aname);
1078                 else
1079                         snprintf(get_cur_genbuf(), sizeof current->genbuf, "...%.*s", (int)(len-(name-aname)), name);
1080                 snprintf(current->errstr, ERRMAX, "%#q %s", get_cur_genbuf(), tmperrbuf);
1081 #endif
1082                 error("some kinda name error");
1083                 nexterror();
1084         }
1085
1086         if(e.mustbedir && !(c->qid.type&QTDIR)){
1087                 npath = e.ARRAY_SIZEs;
1088                 strncpy(tmperrbuf,  "not a directory", sizeof(tmperrbuf));
1089                 goto NameError;
1090         }
1091
1092         if(amode == Aopen && (omode&3) == OEXEC && (c->qid.type&QTDIR)){
1093                 npath = e.ARRAY_SIZEs;
1094                 error("cannot exec directory");
1095         }
1096
1097         switch(amode){
1098         case Aaccess:
1099                 if(!nomount)
1100                         domount(&c, NULL);
1101                 break;
1102
1103         case Abind:
1104                 m = NULL;
1105                 if(!nomount)
1106                         domount(&c, &m);
1107                 if(c->umh != NULL)
1108                         putmhead(c->umh);
1109                 c->umh = m;
1110                 break;
1111
1112         case Aremove:
1113         case Aopen:
1114         Open:
1115                 /* save the name; domount might change c */
1116                 cname = c->name;
1117                 kref_get(&cname->ref, 1);
1118                 m = NULL;
1119                 if(!nomount)
1120                         domount(&c, &m);
1121
1122                 /* our own copy to open or remove */
1123                 c = cunique(c);
1124
1125                 /* now it's our copy anyway, we can put the name back */
1126                 cnameclose(c->name);
1127                 c->name = cname;
1128
1129                 switch(amode){
1130                 case Aremove:
1131                         putmhead(m);
1132                         break;
1133
1134                 case Aopen:
1135                 case Acreate:
1136 if(c->umh != NULL){
1137         printd("cunique umh\n");
1138         putmhead(c->umh);
1139         c->umh = NULL;
1140 }
1141
1142                         /* only save the mount head if it's a multiple element union */
1143                         if(m && m->mount && m->mount->next)
1144                                 c->umh = m;
1145                         else
1146                                 putmhead(m);
1147
1148                         if(omode == OEXEC)
1149                                 c->flag &= ~CCACHE;
1150
1151                         c = devtab[c->type]->open(c, omode&~OCEXEC);
1152
1153                         if(omode & OCEXEC)
1154                                 c->flag |= CCEXEC;
1155                         if(omode & ORCLOSE)
1156                                 c->flag |= CRCLOSE;
1157                         break;
1158                 }
1159                 break;
1160
1161         case Atodir:
1162                 /*
1163                  * Directories (e.g. for cd) are left before the mount po int unused_int,
1164                  * so one may mount on / or . and see the effect.
1165                  */
1166                 if(!(c->qid.type & QTDIR))
1167                         error(Enotdir);
1168                 break;
1169
1170         case Amount:
1171                 /*
1172                  * When mounting on an already mounted upon directory,
1173                  * one wants subsequent mounts to be attached to the
1174                  * original directory, not the replacement.  Don't domount.
1175                  */
1176                 break;
1177
1178         case Acreate:
1179                 /*
1180                  * We've already walked all but the last element.
1181                  * If the last exists, try to open it OTRUNC.
1182                  * If omode&OEXCL is set, just give up.
1183                  */
1184                 e.ARRAY_SIZEs++;
1185                 if(walk(&c, e.elems+e.ARRAY_SIZEs-1, 1, nomount, NULL) == 0){
1186                         if(omode&OEXCL)
1187                                 error(Eexist);
1188                         omode |= OTRUNC;
1189                         goto Open;
1190                 }
1191
1192                 /*
1193                  * The semantics of the create(2) system call are that if the
1194                  * file exists and can be written, it is to be opened with truncation.
1195                  * On the other hand, the create(5) message fails if the file exists.
1196                  * If we get two create(2) calls happening simultaneously, 
1197                  * they might both get here and send create(5) messages, but only 
1198                  * one of the messages will succeed.  To provide the expected create(2)
1199                  * semantics, the call with the failed message needs to try the above
1200                  * walk again, opening for truncation.  This correctly solves the 
1201                  * create/create race, in the sense that any observable outcome can
1202                  * be explained as one happening before the other.
1203                  * The create/create race is quite common.  For example, it happens
1204                  * when two rc subshells simultaneously update the same
1205                  * environment variable.
1206                  *
1207                  * The implementation still admits a create/create/remove race:
1208                  * (A) walk to file, fails
1209                  * (B) walk to file, fails
1210                  * (A) create file, succeeds, returns 
1211                  * (B) create file, fails
1212                  * (A) remove file, succeeds, returns
1213                  * (B) walk to file, return failure.
1214                  *
1215                  * This is hardly as common as the create/create race, and is really
1216                  * not too much worse than what might happen if (B) got a hold of a
1217                  * file descriptor and then the file was removed -- either way (B) can't do
1218                  * anything with the result of the create call.  So we don't care about this race.
1219                  *
1220                  * Applications that care about more fine-grained decision of the races
1221                  * can use the OEXCL flag to get at the underlying create(5) semantics;
1222                  * by default we provide the common case.
1223                  *
1224                  * We need to stay behind the mount point in case we
1225                  * need to do the first walk again (should the create fail).
1226                  *
1227                  * We also need to cross the mount point and find the directory
1228                  * in the union in which we should be creating.
1229                  *
1230                  * The channel staying behind is c, the one moving forward is cnew.
1231                  */
1232                 m = NULL;
1233                 cnew = NULL;    /* is this assignment necessary? */
1234                 if(!waserror()){        /* try create */
1235                         if(!nomount && findmount(&cnew, &m, c->type, c->dev, c->qid))
1236                                 cnew = createdir(cnew, m);
1237                         else{
1238                                 cnew = c;
1239                                 kref_get(&cnew->ref, 1);
1240                         }
1241
1242                         /*
1243                          * We need our own copy of the Chan because we're
1244                          * about to send a create, which will move it.  Once we have
1245                          * our own copy, we can fix the name, which might be wrong
1246                          * if findmount gave us a new Chan.
1247                          */
1248                         cnew = cunique(cnew);
1249                         cnameclose(cnew->name);
1250                         cnew->name = c->name;
1251                         kref_get(&cnew->name->ref, 1);
1252
1253                         devtab[cnew->type]->create(cnew, e.elems[e.ARRAY_SIZEs-1], omode&~(OEXCL|OCEXEC), perm);
1254                         poperror();
1255                         if(omode & OCEXEC)
1256                                 cnew->flag |= CCEXEC;
1257                         if(omode & ORCLOSE)
1258                                 cnew->flag |= CRCLOSE;
1259                         if(m)
1260                                 putmhead(m);
1261                         cclose(c);
1262                         c = cnew;
1263                         c->name = addelem(c->name, e.elems[e.ARRAY_SIZEs-1]);
1264                         break;
1265                 }
1266
1267                 /* create failed */
1268                 cclose(cnew);
1269                 if(m)
1270                         putmhead(m);
1271                 if(omode & OEXCL)
1272                         nexterror();
1273                 /* save error */
1274 #warning "more mess with errstr"
1275 #if 0
1276                 createerr = current->errstr;
1277                 current->errstr = tmperrbuf;
1278 #endif
1279                 /* note: we depend that walk does not error */
1280                 if(walk(&c, e.elems+e.ARRAY_SIZEs-1, 1, nomount, NULL) < 0){
1281                         error(createerr);       /* report true error */
1282                 }
1283 #if 0
1284                 set_errstr(createerr);
1285 #endif
1286                 omode |= OTRUNC;
1287                 goto Open;
1288
1289         default:
1290                 panic("unknown namec access %d\n", amode);
1291         }
1292
1293         poperror();
1294 #warning "how big is genbuf?"
1295         /* place final element in genbuf for e.g. exec */
1296 #if 0
1297         if(e.ARRAY_SIZEs > 0)
1298                 kstrncpy(get_cur_genbuf(), e.elems[e.ARRAY_SIZEs-1],  sizeof current->genbuf, sizeof(current->genbuf, e.elems[e.ARRAY_SIZEs-1]));
1299         else
1300                 kstrncpy(get_cur_genbuf(), ".",  sizeof current->genbuf, sizeof(current->genbuf, "."));
1301 #endif
1302         kfree(e.name);
1303         kfree(e.elems);
1304         kfree(e.off);
1305
1306         return c;
1307 }
1308
1309 /*
1310  * name is valid. skip leading / and ./ as much as possible
1311  */
1312 char*
1313 skipslash(char *name)
1314 {
1315         while(name[0]=='/' || (name[0]=='.' && (name[1]==0 || name[1]=='/')))
1316                 name++;
1317         return name;
1318 }
1319
1320 char isfrog[256]={
1321         /*NUL*/ 1, 1, 1, 1, 1, 1, 1, 1,
1322         /*BKS*/ 1, 1, 1, 1, 1, 1, 1, 1,
1323         /*DLE*/ 1, 1, 1, 1, 1, 1, 1, 1,
1324         /*CAN*/ 1, 1, 1, 1, 1, 1, 1, 1,
1325         ['/']   1,
1326         [0x7f]  1,
1327 };
1328
1329 /*
1330  * Check that the name
1331  *  a) is in valid memory.
1332  *  b) is shorter than 2^16 bytes, so it can fit in a 9P string field.
1333  *  c) contains no frogs.
1334  * The first byte is known to be addressible by the requester, so the
1335  * routine works for kernel and user memory both.
1336  * The parameter slashok flags whether a slash character is an error
1337  * or a valid character.
1338  */
1339 void
1340 validname(char *aname, int slashok)
1341 {
1342         char *ename, *name;
1343         int c;
1344
1345         name = aname;
1346         ename = memchr(name, 0, (1<<16));
1347
1348         if(ename==NULL || ename-name>=(1<<16))
1349                 error("name too long");
1350
1351         while(*name){
1352                 /* all characters above '~' are ok */
1353                 c = *( uint8_t *)name;
1354 #if 0       
1355                 if(c >= Runeself)
1356                         name += chartorune(&r, name);
1357 #endif
1358                 if(c >= 0x7f){
1359                         error("Akaros doesn't do UTF-8");
1360                 } else {
1361                         if(isfrog[c])
1362                                 if(!slashok || c!='/'){
1363                                         error("%s: %q", Ebadchar, aname);
1364                         }
1365                         name++;
1366                 }
1367         }
1368 }
1369
1370 void
1371 isdir(struct chan *c)
1372 {
1373         if(c->qid.type & QTDIR)
1374                 return;
1375         error(Enotdir);
1376 }
1377
1378 /*
1379  * This is necessary because there are many
1380  * pointers to the top of a given mount list:
1381  *
1382  *      - the mhead in the namespace hash table
1383  *      - the mhead in chans returned from findmount:
1384  *        used in namec and then by unionread.
1385  *      - the mhead in chans returned from createdir:
1386  *        used in the open/create race protect, which is gone.
1387  *
1388  * The RWlock in the Mhead protects the mount list it contains.
1389  * The mount list is deleted when we cunmount.
1390  * The RWlock ensures that nothing is using the mount list at that time.
1391  *
1392  * It is okay to replace c->mh with whatever you want as 
1393  * long as you are sure you have a unique reference to it.
1394  *
1395  * This comment might belong somewhere else.
1396  */
1397 void
1398 putmhead(struct mhead *m)
1399 {
1400         if(m && kref_put(&m->ref) == 0){
1401                 m->mount = (struct mount*)0xCafeBeef;
1402                 kfree(m);
1403         }
1404 }