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