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