f5470f5bdc8b49ffe6525d4e9c21bb2f86a0acd5
[openafs.git] / src / libafscp / afscp_dir.c
1 /* AUTORIGHTS
2 Copyright (C) 2003 - 2010 Chaskiel Grundman
3 All rights reserved
4
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions
7 are met:
8
9 1. Redistributions of source code must retain the above copyright
10    notice, this list of conditions and the following disclaimer.
11
12 2. Redistributions in binary form must reproduce the above copyright
13    notice, this list of conditions and the following disclaimer in the
14    documentation and/or other materials provided with the distribution.
15
16 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27 #include <afsconfig.h>
28 #include <afs/param.h>
29
30 #include <roken.h>
31
32 #include <search.h>
33
34 #include <afs/vlserver.h>
35 #include <afs/vldbint.h>
36 #include <afs/dir.h>
37 #ifdef AFS_NT40_ENV
38 #include <afs/errmap_nt.h>
39 #endif
40 #include "afscp.h"
41 #include "afscp_internal.h"
42
43 static int dirmode = DIRMODE_CELL;
44
45 int
46 afscp_SetDirMode(int mode)
47 {
48     if ((mode != DIRMODE_CELL) && (mode != DIRMODE_DYNROOT)) {
49         afscp_errno = EINVAL;
50         return -1;
51     }
52     dirmode = mode;
53     return 0;
54 }
55
56 /* comparison function for tsearch */
57 static int
58 dircompare(const void *a, const void *b)
59 {
60     const struct afscp_dircache *sa = a, *sb = b;
61     if (sa->me.fid.Vnode < sb->me.fid.Vnode)
62         return -1;
63     if (sa->me.fid.Vnode > sb->me.fid.Vnode)
64         return 1;
65     if (sa->me.fid.Unique < sb->me.fid.Unique)
66         return -1;
67     if (sa->me.fid.Unique > sb->me.fid.Unique)
68         return 1;
69     return 0;
70 }
71
72 /* make sure the dirstream contains the most up to date directory contents */
73 static int
74 _DirUpdate(struct afscp_dirstream *d)
75 {
76     struct AFSFetchStatus s;
77     int code;
78     struct afscp_volume *v;
79     struct afscp_dircache key, *stored;
80     void **cached;
81
82
83     code = afscp_GetStatus(&d->fid, &s);
84     if (code != 0) {
85         return code;
86     }
87
88     if (d->dirbuffer && d->dv == s.DataVersion) {
89         return 0;
90     }
91     v = afscp_VolumeById(d->fid.cell, d->fid.fid.Volume);
92     if (v == NULL) {
93         afscp_errno = ENOENT;
94         return -1;
95     }
96
97     memcpy(&key.me, &d->fid, sizeof(struct afscp_venusfid));
98     cached = tfind(&key, &v->dircache, dircompare);
99     if (cached != NULL) {
100         stored = *(struct afscp_dircache **)cached;
101         if (d->dv == s.DataVersion) {
102             d->dirbuffer = stored->dirbuffer;
103             d->buflen = stored->buflen;
104             d->dv = stored->dv;
105             return 0;
106         }
107         pthread_mutex_lock(&(stored->mtx));
108         tdelete(&key, &v->dircache, dircompare);
109         stored->nwaiters++;
110         while (stored->nwaiters > 1) {
111             pthread_cond_wait(&(stored->cv), &(stored->mtx));
112         }
113         stored->nwaiters--;
114         pthread_cond_destroy(&(stored->cv));
115         pthread_mutex_unlock(&(stored->mtx));
116         pthread_mutex_destroy(&(stored->mtx));
117         if (d->dirbuffer != stored->dirbuffer)
118             free(stored->dirbuffer);
119         free(stored);
120     }
121     if (s.Length > BIGMAXPAGES * AFS_PAGESIZE) {
122         afscp_errno = EFBIG;
123         return -1;
124     }
125     if (d->buflen != s.Length) {
126         char *new;
127         if (d->dirbuffer) {
128             new = realloc(d->dirbuffer, s.Length);
129         } else {
130             new = malloc(s.Length);
131         }
132         if (new != NULL) {
133             d->dirbuffer = new;
134         } else {
135             afscp_errno = ENOMEM;
136             return -1;
137         }
138         d->buflen = s.Length;
139     }
140
141     code = afscp_PRead(&d->fid, d->dirbuffer, s.Length, 0);
142     if (code < 0) {
143         return -1;
144     }
145     d->dv = s.DataVersion;
146     cached = tsearch(&key, &v->dircache, dircompare);
147     if (cached != NULL) {
148         stored = malloc(sizeof(struct afscp_dircache));
149         if (stored != NULL) {
150             memcpy(&stored->me, &d->fid, sizeof(struct afscp_venusfid));
151             stored->buflen = d->buflen;
152             stored->dirbuffer = d->dirbuffer;
153             stored->dv = d->dv;
154             stored->nwaiters = 0;
155             pthread_mutex_init(&(stored->mtx), NULL);
156             pthread_cond_init(&(stored->cv), NULL);
157             *(struct afscp_dircache **)cached = stored;
158         } else {
159             tdelete(&key, &v->dircache, dircompare);
160         }
161     }
162     return 0;
163 }
164
165 static struct DirEntry *
166 dir_get_entry(struct afscp_dirstream *d, int entry)
167 {
168     struct DirHeader *h = (struct DirHeader *)d->dirbuffer;
169     /* struct PageHeader *p; */
170     struct DirEntry *ret;
171     /* int fr; */
172     int pg, off;
173
174     pg = entry >> LEPP;
175     off = entry & (EPP - 1);
176
177     if (pg * AFS_PAGESIZE >= d->buflen) {       /* beyond end of file */
178         return NULL;
179     }
180     if (!off || (!pg && off < DHE + 1)) {       /* offset refers to metadata */
181         return NULL;
182     }
183     if (pg < MAXPAGES && h->alloMap[pg] == EPP) {       /* page is empty */
184         return NULL;
185     }
186     /* p = (struct PageHeader *)&d->dirbuffer[pg * AFS_PAGESIZE]; */
187     /* p is set but not referenced later */
188     /* fr = p->freebitmap[off >> 8]; */
189     /* fr is set but not referenced later */
190     ret = (struct DirEntry *)&d->dirbuffer[pg * AFS_PAGESIZE + 32 * off];
191     return ret;
192 }
193
194 struct afscp_dirstream *
195 afscp_OpenDir(const struct afscp_venusfid *fid)
196 {
197     struct afscp_dirstream *ret;
198     struct AFSFetchStatus s;
199     int code;
200
201     code = afscp_GetStatus(fid, &s);
202     if (code != 0) {
203         return NULL;
204     }
205
206     if (s.FileType != Directory) {
207         afscp_errno = ENOTDIR;
208         return NULL;
209     }
210     ret = calloc(1, sizeof(struct afscp_dirstream));
211     if (ret == NULL) {
212         afscp_errno = ENOMEM;
213         return NULL;
214     }
215     memmove(&ret->fid, fid, sizeof(struct afscp_venusfid));
216     code = _DirUpdate(ret);
217     if (code < 0) {
218         afscp_CloseDir(ret);
219         return NULL;
220     }
221     ret->hashent = -1;
222     ret->entry = 0;
223
224     return ret;
225 }
226
227 struct afscp_dirent *
228 afscp_ReadDir(struct afscp_dirstream *d)
229 {
230     struct DirHeader *h = (struct DirHeader *)d->dirbuffer;
231     struct DirEntry *info;
232     int ent;
233
234
235     ent = d->entry;
236     while (ent == 0 && d->hashent < NHASHENT - 1) {
237         d->hashent++;
238         ent = ntohs(h->hashTable[d->hashent]);
239     }
240     if (ent == 0) {
241         afscp_errno = 0;
242         return NULL;
243     }
244     info = dir_get_entry(d, ent);
245     if (info == NULL) {
246         afscp_errno = 0;
247         return NULL;
248     }
249     d->ret.vnode = ntohl(info->fid.vnode);
250     d->ret.unique = ntohl(info->fid.vunique);
251     strlcpy(d->ret.name, info->name, sizeof(d->ret.name));      /* guaranteed to be NULL terminated? */
252     d->entry = ntohs(info->next);
253
254     return &d->ret;
255 }
256
257 /* as it calls _DirUpdate, this may corrupt any previously returned dirent's */
258 int
259 afscp_RewindDir(struct afscp_dirstream *d)
260 {
261     _DirUpdate(d);
262     d->hashent = -1;
263     d->entry = 0;
264     return 0;
265 }
266
267 int
268 afscp_CloseDir(struct afscp_dirstream *d)
269 {
270     free(d);
271     return 0;
272 }
273
274 static int
275 namehash(const char *name)
276 {
277     int hval, tval;
278
279     hval = 0;
280     while (*name != '\0')
281         hval = (hval * 173) + *name++;
282     tval = hval & (NHASHENT - 1);
283     return tval ? (hval < 0 ? NHASHENT - tval : tval)
284         : 0;
285 }
286
287 struct afscp_venusfid *
288 afscp_DirLookup(struct afscp_dirstream *d, const char *name)
289 {
290     int code;
291     int hval, entry;
292     struct DirHeader *h = (struct DirHeader *)d->dirbuffer;
293     struct DirEntry *info;
294
295     code = _DirUpdate(d);
296     if (code != 0) {
297         return NULL;
298     }
299     hval = namehash(name);
300     entry = ntohs(h->hashTable[hval]);
301
302     while (entry != 0) {
303         info = dir_get_entry(d, entry);
304         if (info == NULL) {
305             afscp_errno = EIO;
306             return NULL;
307         }
308         if (strcmp(info->name, name) == 0)
309             break;
310         entry = ntohs(info->next);
311     }
312     if (entry != 0) {
313         return afscp_MakeFid(d->fid.cell, d->fid.fid.Volume,
314                              ntohl(info->fid.vnode),
315                              ntohl(info->fid.vunique));
316     } else {
317         afscp_errno = ENOENT;
318         return NULL;
319     }
320 }
321
322 struct afscp_venusfid *
323 afscp_ResolveName(const struct afscp_venusfid *dir, const char *name)
324 {
325     struct afscp_venusfid *ret;
326     struct afscp_dirstream *d;
327
328     d = afscp_OpenDir(dir);
329     if (d == NULL) {
330         return NULL;
331     }
332     ret = afscp_DirLookup(d, name);
333     afscp_CloseDir(d);
334     return ret;
335 }
336
337 static int
338 gettoproot(struct afscp_cell *cell, char *p, char **q,
339            struct afscp_venusfid **root)
340 {
341     struct afscp_volume *rootvol;
342     char *r;
343
344     if (dirmode == DIRMODE_DYNROOT && (strcmp(p, "/afs") == 0)) {
345         afscp_errno = EINVAL;
346         return 1;
347     }
348     if (strncmp(p, "/afs", 4) == 0) {
349         afs_dprintf(("gettoproot: path is absolute\n"));
350         p = &p[5];
351         while (*p == '/')
352             p++;
353         if (dirmode == DIRMODE_DYNROOT) {
354             int voltype;
355           retry_dot:
356             voltype = ROVOL;
357             if (*p == '.') {
358                 p++;
359                 voltype = RWVOL;
360             }
361             if (*p == '/') {
362                 while (*p == '/')
363                     p++;
364                 goto retry_dot;
365             }
366             if (*p == '.' || *p == 0) {
367                 afscp_errno = EINVAL;
368                 return 1;
369             }
370             r = p;
371             while (*r && *r != '/')
372                 r++;
373             if (!*r && !*p) {
374                 afscp_errno = ENODEV;
375                 return 1;
376             }
377             *r++ = 0;
378             *q = r;
379             afs_dprintf(("gettoproot: dynroot looking up cell %s\n", p));
380             cell = afscp_CellByName(p, NULL);
381             if (cell == NULL) {
382                 afs_dprintf(("gettoproot: no such cell\n"));
383                 afscp_errno = ENODEV;
384                 return 1;
385             }
386             rootvol = afscp_VolumeByName(cell, "root.cell", voltype);
387             if (!rootvol && voltype == ROVOL)
388                 rootvol = afscp_VolumeByName(cell, "root.cell", RWVOL);
389         } else {
390             *q = p;
391             rootvol = afscp_VolumeByName(cell, "root.afs", ROVOL);
392             if (!rootvol)
393                 rootvol = afscp_VolumeByName(cell, "root.afs", RWVOL);
394         }
395         if (!rootvol)
396             afs_dprintf(("gettoproot: volume not found\n"));
397     } else {
398         afs_dprintf(("gettoproot: path is relative\n"));
399         if (p[0] == '/') {
400             afscp_errno = EXDEV;
401             return 1;
402         }
403         rootvol = afscp_VolumeByName(cell, "root.cell", ROVOL);
404         if (!rootvol)
405             rootvol = afscp_VolumeByName(cell, "root.cell", RWVOL);
406         *q = p;
407     }
408     if (rootvol == NULL) {
409         afscp_errno = ENODEV;
410         return 1;
411     }
412     *root = afscp_MakeFid(cell, rootvol->id, 1, 1);
413     return 0;
414 }
415
416 static int
417 getvolumeroot(struct afscp_cell *cell, int voltype, const char *vname,
418               struct afscp_venusfid **root)
419 {
420     struct afscp_volume *vol;
421     vol = afscp_VolumeByName(cell, vname, voltype);
422     if (!vol && voltype == ROVOL)
423         vol = afscp_VolumeByName(cell, vname, RWVOL);
424     if (vol == NULL) {
425         afscp_errno = ENODEV;
426         return 1;
427     }
428     *root = afscp_MakeFid(cell, vol->id, 1, 1);
429     return 0;
430 }
431
432 typedef struct fidstack_s {
433     int alloc;
434     int count;
435     struct afscp_venusfid **entries;
436 } *fidstack;
437
438 static fidstack
439 fidstack_alloc(void)
440 {
441     fidstack ret;
442
443     ret = malloc(sizeof(struct fidstack_s));
444     if (ret == NULL) {
445         afscp_errno = ENOMEM;
446         return NULL;
447     }
448     ret->alloc = 10;
449     ret->count = 0;
450     ret->entries = malloc(ret->alloc * sizeof(struct afscp_venusfid *));
451     if (ret->entries == NULL) {
452         free(ret);
453         afscp_errno = ENOMEM;
454         return NULL;
455     }
456     return ret;
457 }
458
459 static void
460 fidstack_push(fidstack s, struct afscp_venusfid *entry)
461 {
462     struct afscp_venusfid **new;
463     if (s->count >= s->alloc) {
464         new = realloc(s->entries, (s->alloc + 10) *
465                       sizeof(struct afscp_venusfid *));
466         if (new == NULL) {
467             return;
468         }
469         s->entries = new;
470         s->alloc += 10;
471     }
472     s->entries[s->count++] = entry;
473     return;
474 }
475
476 static struct afscp_venusfid *
477 fidstack_pop(fidstack s)
478 {
479     if (s->count)
480         return s->entries[--s->count];
481     return NULL;
482 }
483
484 static void
485 fidstack_free(fidstack s)
486 {
487     int i;
488
489     for (i = 0; i < s->count; i++)
490         free(s->entries[i]);
491     free(s->entries);
492     free(s);
493 }
494
495 static struct afscp_venusfid *_ResolvePath(const struct afscp_venusfid *,
496                                            fidstack, char *, int);
497
498 static struct afscp_venusfid *
499 afscp_HandleLink(struct afscp_venusfid *in,
500                  const struct afscp_venusfid *parent, fidstack fids,
501                  int follow, const struct AFSFetchStatus *s, int terminal)
502 {
503     char *linkbuf, *linkbufq;
504     struct afscp_cell *cell;
505     struct afscp_volume *v;
506     struct afscp_venusfid *root, *ret;
507     int voltype;
508     int code;
509     ssize_t len;
510     if ((s->UnixModeBits & 0111) && (follow == 0) && terminal) {        /* normal link */
511         return in;
512     }
513     linkbuf = malloc(s->Length + 1);
514     code = afscp_PRead(in, linkbuf, s->Length, 0);
515     if (code < 0) {
516         free(linkbuf);
517         free(in);
518         return NULL;
519     }
520     if (code != s->Length) {
521         afscp_errno = EIO;
522         free(linkbuf);
523         free(in);
524         return NULL;
525     }
526     linkbuf[s->Length] = 0;
527     if (s->UnixModeBits & 0111) {       /* normal link */
528         afs_dprintf(("Recursing on symlink %s...\n", linkbuf));
529         if (linkbuf[0] == '/') {
530             if (gettoproot(in->cell, linkbuf, &linkbufq, &root)) {
531                 free(linkbuf);
532                 free(in);
533                 return NULL;
534             }
535             free(in);
536             ret = _ResolvePath(root, 0, linkbufq, 0);
537             free(root);
538         } else {
539             free(in);
540             ret = _ResolvePath(parent, fids, linkbuf, 0);
541         }
542         free(linkbuf);
543     } else {                    /* mountpoint */
544         afs_dprintf(("EvalMountPoint %s...\n", linkbuf));
545         linkbufq = strchr(linkbuf, ':');
546         cell = in->cell;
547         v = afscp_VolumeById(cell, in->fid.Volume);
548         free(in);
549         if (v == NULL) {
550             free(linkbuf);
551             afscp_errno = ENODEV;
552             return NULL;
553         }
554         voltype = v->voltype;
555         if (linkbuf[0] == '%')
556             voltype = RWVOL;
557         if (linkbufq == NULL) {
558             linkbufq = linkbuf + 1;
559         } else {
560             *linkbufq++ = 0;
561             cell = afscp_CellByName(linkbuf + 1, NULL);
562             if (linkbuf[0] != '%')
563                 voltype = ROVOL;
564         }
565         if (cell == NULL) {
566             free(linkbuf);
567             afscp_errno = ENODEV;
568             return NULL;
569         }
570         len = strnlen(linkbufq, s->Length + 1);
571         if (len < 2) {
572             free(linkbuf);
573             afscp_errno = ENODEV;
574             return NULL;
575         }
576         len = strnlen(linkbufq, s->Length + 1);
577         linkbufq[len - 1] = 0;  /* eliminate trailer */
578         if (getvolumeroot(cell, voltype, linkbufq, &ret)) {
579             free(linkbuf);
580             return NULL;
581         }
582         free(linkbuf);
583     }
584     return ret;
585 }
586
587 static struct afscp_venusfid *
588 _ResolvePath(const struct afscp_venusfid *start, fidstack infids,
589              char *path, int follow)
590 {
591     struct afscp_venusfid *ret, *cwd;
592     struct AFSFetchStatus s;
593     char *p, *q;
594     int code;
595     int linkcount;
596     fidstack fids;
597
598     p = path;
599     ret = cwd = afscp_DupFid(start);
600     fids = infids;
601     if (fids == NULL)
602         fids = fidstack_alloc();
603     if (fids == NULL) {
604         return NULL;
605     }
606
607     while (p && *p) {
608         q = strchr(p, '/');
609         if (q)
610             *q++ = 0;
611         if (strcmp(p, ".") == 0) {
612             /* do nothing */
613         } else if (strcmp(p, "..") == 0) {
614             ret = fidstack_pop(fids);
615             if (ret == NULL)
616                 ret = cwd;
617             else
618                 free(cwd);
619         } else {
620             ret = afscp_ResolveName(cwd, p);
621             if (ret == NULL) {
622                 afs_dprintf(("Lookup %s in %lu.%lu.%lu failed\n", p,
623                              cwd->fid.Volume, cwd->fid.Vnode,
624                              cwd->fid.Unique));
625                 free(cwd);
626                 if (infids == NULL)
627                     fidstack_free(fids);
628                 return NULL;
629             }
630             afs_dprintf(("Lookup %s in %lu.%lu.%lu->%lu.%lu.%lu\n", p,
631                          cwd->fid.Volume, cwd->fid.Vnode, cwd->fid.Unique,
632                          ret->fid.Volume, ret->fid.Vnode, ret->fid.Unique));
633             linkcount = 0;
634
635           retry:
636             if ((ret->fid.Vnode & 1) == 0) {    /* not a directory; check for link */
637                 code = afscp_GetStatus(ret, &s);
638                 if (code != 0) {
639                     if (infids == NULL)
640                         fidstack_free(fids);
641                     free(cwd);
642                     free(ret);
643                     return NULL;
644                 }
645                 if (s.FileType == SymbolicLink) {
646                     if (linkcount++ > 5) {
647                         afscp_errno = ELOOP;
648                         if (infids == NULL)
649                             fidstack_free(fids);
650                         free(cwd);
651                         free(ret);
652                         return NULL;
653                     }
654                     ret =
655                         afscp_HandleLink(ret, cwd, fids, follow, &s,
656                                          (q == NULL));
657                     if (ret == NULL) {
658                         free(cwd);
659                         if (infids == NULL)
660                             fidstack_free(fids);
661                         return NULL;
662                     }
663                     afs_dprintf(("   ....-> %lu.%lu.%lu\n", ret->fid.Volume,
664                                  ret->fid.Vnode, ret->fid.Unique));
665                     goto retry;
666                 } else {
667                     if (q != NULL) {
668                         afscp_errno = ENOTDIR;
669                         free(cwd);
670                         free(ret);
671                         if (infids == NULL)
672                             fidstack_free(fids);
673                         return NULL;
674                     }
675                 }
676             }
677             fidstack_push(fids, cwd);
678         }
679         cwd = ret;
680
681         while ((q != NULL) && (*q == '/'))
682             q++;
683         p = q;
684     }
685     if (infids == NULL)
686         fidstack_free(fids);
687     return ret;
688 }
689
690 /*!
691  * Resolve a path to a FID starting from the root volume
692  *
693  * \param[in]   path    full path
694  *
695  * \post Returns a venusfid representing the final element of path
696  *
697  * \note There are three cases:
698  *       (1) begins with /afs: start in root.afs of cell or home cell
699  *       (2) else begins with /: error
700  *       (3) else start in root.cell of cell or home cell
701  */
702 struct afscp_venusfid *
703 afscp_ResolvePath(const char *path)
704 {
705     struct afscp_venusfid *root, *ret;
706     struct afscp_cell *cell;
707     int code;
708     char *p, *q;
709     p = strdup(path);           /* so we can modify the string */
710     if (p == NULL) {
711         afscp_errno = ENOMEM;
712         return NULL;
713     }
714     cell = afscp_DefaultCell();
715     if (cell == NULL) {
716         free(p);
717         afscp_errno = EINVAL;
718         return NULL;
719     }
720     code = gettoproot(cell, p, &q, &root);
721     if (code != 0) {
722         free(p);
723         return NULL;
724     }
725     if (q && *q) {
726         ret = _ResolvePath(root, 0, q, 1);
727         free(root);
728     } else
729         ret = root;
730     free(p);
731     return ret;
732 }
733
734 /*!
735  * Resolve a path to a FID starting from the given volume
736  *
737  * \param[in]   v       volume structure containing id and cell info
738  * \param[in]   path    path relative to volume v
739  *
740  * \post Returns a venusfid representing the final element of path
741  */
742 struct afscp_venusfid *
743 afscp_ResolvePathFromVol(const struct afscp_volume *v, const char *path)
744 {
745     struct afscp_venusfid *root, *ret;
746     char *origp, *p;
747
748     /* so we can modify the string */
749     origp = p = strdup(path);
750     if (p == NULL) {
751         afscp_errno = ENOMEM;
752         return NULL;
753     }
754     root = afscp_MakeFid(v->cell, v->id, 1, 1);
755     while (*p == '/')
756         p++;
757     if (*p != '\0') {
758         ret = _ResolvePath(root, 0, p, 1);
759         free(root);
760     } else
761         ret = root;
762     free(origp);
763     return ret;
764 }