84af12711b9d33930b8aafef20c58df3c2a201f0
[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 = malloc(sizeof(struct afscp_dirstream));
211     if (ret == NULL) {
212         afscp_errno = ENOMEM;
213         return NULL;
214     }
215     memset(ret, 0, sizeof(struct afscp_dirstream));
216     memmove(&ret->fid, fid, sizeof(struct afscp_venusfid));
217     code = _DirUpdate(ret);
218     if (code < 0) {
219         afscp_CloseDir(ret);
220         return NULL;
221     }
222     ret->hashent = -1;
223     ret->entry = 0;
224
225     return ret;
226 }
227
228 struct afscp_dirent *
229 afscp_ReadDir(struct afscp_dirstream *d)
230 {
231     struct DirHeader *h = (struct DirHeader *)d->dirbuffer;
232     struct DirEntry *info;
233     int ent;
234
235
236     ent = d->entry;
237     while (ent == 0 && d->hashent < NHASHENT - 1) {
238         d->hashent++;
239         ent = ntohs(h->hashTable[d->hashent]);
240     }
241     if (ent == 0) {
242         afscp_errno = 0;
243         return NULL;
244     }
245     info = dir_get_entry(d, ent);
246     if (info == NULL) {
247         afscp_errno = 0;
248         return NULL;
249     }
250     d->ret.vnode = ntohl(info->fid.vnode);
251     d->ret.unique = ntohl(info->fid.vunique);
252     strlcpy(d->ret.name, info->name, sizeof(d->ret.name));      /* guaranteed to be NULL terminated? */
253     d->entry = ntohs(info->next);
254
255     return &d->ret;
256 }
257
258 /* as it calls _DirUpdate, this may corrupt any previously returned dirent's */
259 int
260 afscp_RewindDir(struct afscp_dirstream *d)
261 {
262     _DirUpdate(d);
263     d->hashent = -1;
264     d->entry = 0;
265     return 0;
266 }
267
268 int
269 afscp_CloseDir(struct afscp_dirstream *d)
270 {
271     free(d);
272     return 0;
273 }
274
275 static int
276 namehash(const char *name)
277 {
278     int hval, tval;
279
280     hval = 0;
281     while (*name != '\0')
282         hval = (hval * 173) + *name++;
283     tval = hval & (NHASHENT - 1);
284     return tval ? (hval < 0 ? NHASHENT - tval : tval)
285         : 0;
286 }
287
288 struct afscp_venusfid *
289 afscp_DirLookup(struct afscp_dirstream *d, const char *name)
290 {
291     int code;
292     int hval, entry;
293     struct DirHeader *h = (struct DirHeader *)d->dirbuffer;
294     struct DirEntry *info;
295
296     code = _DirUpdate(d);
297     if (code != 0) {
298         return NULL;
299     }
300     hval = namehash(name);
301     entry = ntohs(h->hashTable[hval]);
302
303     while (entry != 0) {
304         info = dir_get_entry(d, entry);
305         if (info == NULL) {
306             afscp_errno = EIO;
307             return NULL;
308         }
309         if (strcmp(info->name, name) == 0)
310             break;
311         entry = ntohs(info->next);
312     }
313     if (entry != 0) {
314         return afscp_MakeFid(d->fid.cell, d->fid.fid.Volume,
315                              ntohl(info->fid.vnode),
316                              ntohl(info->fid.vunique));
317     } else {
318         afscp_errno = ENOENT;
319         return NULL;
320     }
321 }
322
323 struct afscp_venusfid *
324 afscp_ResolveName(const struct afscp_venusfid *dir, const char *name)
325 {
326     struct afscp_venusfid *ret;
327     struct afscp_dirstream *d;
328
329     d = afscp_OpenDir(dir);
330     if (d == NULL) {
331         return NULL;
332     }
333     ret = afscp_DirLookup(d, name);
334     afscp_CloseDir(d);
335     return ret;
336 }
337
338 static int
339 gettoproot(struct afscp_cell *cell, char *p, char **q,
340            struct afscp_venusfid **root)
341 {
342     struct afscp_volume *rootvol;
343     char *r;
344
345     if (dirmode == DIRMODE_DYNROOT && (strcmp(p, "/afs") == 0)) {
346         afscp_errno = EINVAL;
347         return 1;
348     }
349     if (strncmp(p, "/afs", 4) == 0) {
350         afs_dprintf(("gettoproot: path is absolute\n"));
351         p = &p[5];
352         while (*p == '/')
353             p++;
354         if (dirmode == DIRMODE_DYNROOT) {
355             int voltype;
356           retry_dot:
357             voltype = ROVOL;
358             if (*p == '.') {
359                 p++;
360                 voltype = RWVOL;
361             }
362             if (*p == '/') {
363                 while (*p == '/')
364                     p++;
365                 goto retry_dot;
366             }
367             if (*p == '.' || *p == 0) {
368                 afscp_errno = EINVAL;
369                 return 1;
370             }
371             r = p;
372             while (*r && *r != '/')
373                 r++;
374             if (!*r) {
375                 afscp_errno = ENODEV;
376                 return 1;
377             }
378             *r++ = 0;
379             *q = r;
380             afs_dprintf(("gettoproot: dynroot looking up cell %s\n", p));
381             cell = afscp_CellByName(p, NULL);
382             if (cell == NULL) {
383                 afs_dprintf(("gettoproot: no such cell\n"));
384                 afscp_errno = ENODEV;
385                 return 1;
386             }
387             rootvol = afscp_VolumeByName(cell, "root.cell", voltype);
388             if (!rootvol && voltype == ROVOL)
389                 rootvol = afscp_VolumeByName(cell, "root.cell", RWVOL);
390         } else {
391             *q = p;
392             rootvol = afscp_VolumeByName(cell, "root.afs", ROVOL);
393             if (!rootvol)
394                 rootvol = afscp_VolumeByName(cell, "root.afs", RWVOL);
395         }
396         if (!rootvol)
397             afs_dprintf(("gettoproot: volume not found\n"));
398     } else {
399         afs_dprintf(("gettoproot: path is relative\n"));
400         if (p[0] == '/') {
401             afscp_errno = EXDEV;
402             return 1;
403         }
404         rootvol = afscp_VolumeByName(cell, "root.cell", ROVOL);
405         if (!rootvol)
406             rootvol = afscp_VolumeByName(cell, "root.cell", RWVOL);
407         *q = p;
408     }
409     if (rootvol == NULL) {
410         afscp_errno = ENODEV;
411         return 1;
412     }
413     *root = afscp_MakeFid(cell, rootvol->id, 1, 1);
414     return 0;
415 }
416
417 static int
418 getvolumeroot(struct afscp_cell *cell, int voltype, const char *vname,
419               struct afscp_venusfid **root)
420 {
421     struct afscp_volume *vol;
422     vol = afscp_VolumeByName(cell, vname, voltype);
423     if (!vol && voltype == ROVOL)
424         vol = afscp_VolumeByName(cell, vname, RWVOL);
425     if (vol == NULL) {
426         afscp_errno = ENODEV;
427         return 1;
428     }
429     *root = afscp_MakeFid(cell, vol->id, 1, 1);
430     return 0;
431 }
432
433 typedef struct fidstack_s {
434     int alloc;
435     int count;
436     struct afscp_venusfid **entries;
437 } *fidstack;
438
439 static fidstack
440 fidstack_alloc(void)
441 {
442     fidstack ret;
443
444     ret = malloc(sizeof(struct fidstack_s));
445     if (ret == NULL) {
446         afscp_errno = ENOMEM;
447         return NULL;
448     }
449     ret->alloc = 10;
450     ret->count = 0;
451     ret->entries = malloc(ret->alloc * sizeof(struct afscp_venusfid *));
452     if (ret->entries == NULL) {
453         free(ret);
454         afscp_errno = ENOMEM;
455         return NULL;
456     }
457     return ret;
458 }
459
460 static void
461 fidstack_push(fidstack s, struct afscp_venusfid *entry)
462 {
463     struct afscp_venusfid **new;
464     if (s->count >= s->alloc) {
465         new = realloc(s->entries, (s->alloc + 10) *
466                       sizeof(struct afscp_venusfid *));
467         if (new == NULL) {
468             return;
469         }
470         s->entries = new;
471         s->alloc += 10;
472     }
473     s->entries[s->count++] = entry;
474     return;
475 }
476
477 static struct afscp_venusfid *
478 fidstack_pop(fidstack s)
479 {
480     if (s->count)
481         return s->entries[--s->count];
482     return NULL;
483 }
484
485 static void
486 fidstack_free(fidstack s)
487 {
488     int i;
489
490     for (i = 0; i < s->count; i++)
491         free(s->entries[i]);
492     free(s->entries);
493     free(s);
494 }
495
496 static struct afscp_venusfid *_ResolvePath(const struct afscp_venusfid *,
497                                            fidstack, char *, int);
498
499 static struct afscp_venusfid *
500 afscp_HandleLink(struct afscp_venusfid *in,
501                  const struct afscp_venusfid *parent, fidstack fids,
502                  int follow, const struct AFSFetchStatus *s, int terminal)
503 {
504     char *linkbuf, *linkbufq;
505     struct afscp_cell *cell;
506     struct afscp_volume *v;
507     struct afscp_venusfid *root, *ret;
508     int voltype;
509     int code;
510     ssize_t len;
511     if ((s->UnixModeBits & 0111) && (follow == 0) && terminal) {        /* normal link */
512         return in;
513     }
514     linkbuf = malloc(s->Length + 1);
515     code = afscp_PRead(in, linkbuf, s->Length, 0);
516     if (code < 0) {
517         free(linkbuf);
518         free(in);
519         return NULL;
520     }
521     if (code != s->Length) {
522         afscp_errno = EIO;
523         free(linkbuf);
524         free(in);
525         return NULL;
526     }
527     linkbuf[s->Length] = 0;
528     if (s->UnixModeBits & 0111) {       /* normal link */
529         afs_dprintf(("Recursing on symlink %s...\n", linkbuf));
530         if (linkbuf[0] == '/') {
531             if (gettoproot(in->cell, linkbuf, &linkbufq, &root)) {
532                 free(linkbuf);
533                 free(in);
534                 return NULL;
535             }
536             free(in);
537             ret = _ResolvePath(root, 0, linkbufq, 0);
538             free(root);
539         } else {
540             free(in);
541             ret = _ResolvePath(parent, fids, linkbuf, 0);
542         }
543         free(linkbuf);
544     } else {                    /* mountpoint */
545         afs_dprintf(("EvalMountPoint %s...\n", linkbuf));
546         linkbufq = strchr(linkbuf, ':');
547         cell = in->cell;
548         v = afscp_VolumeById(cell, in->fid.Volume);
549         free(in);
550         if (v == NULL) {
551             free(linkbuf);
552             afscp_errno = ENODEV;
553             return NULL;
554         }
555         voltype = v->voltype;
556         if (linkbuf[0] == '%')
557             voltype = RWVOL;
558         if (linkbufq == NULL) {
559             linkbufq = linkbuf + 1;
560         } else {
561             *linkbufq++ = 0;
562             cell = afscp_CellByName(linkbuf + 1, NULL);
563             if (linkbuf[0] != '%')
564                 voltype = ROVOL;
565         }
566         if (cell == NULL) {
567             free(linkbuf);
568             afscp_errno = ENODEV;
569             return NULL;
570         }
571         len = strnlen(linkbufq, s->Length + 1);
572         if (len < 2) {
573             free(linkbuf);
574             afscp_errno = ENODEV;
575             return NULL;
576         }
577         len = strnlen(linkbufq, s->Length + 1);
578         linkbufq[len - 1] = 0;  /* eliminate trailer */
579         if (getvolumeroot(cell, voltype, linkbufq, &ret)) {
580             free(linkbuf);
581             return NULL;
582         }
583         free(linkbuf);
584     }
585     return ret;
586 }
587
588 static struct afscp_venusfid *
589 _ResolvePath(const struct afscp_venusfid *start, fidstack infids,
590              char *path, int follow)
591 {
592     struct afscp_venusfid *ret, *cwd;
593     struct AFSFetchStatus s;
594     char *p, *q;
595     int code;
596     int linkcount;
597     fidstack fids;
598
599     p = path;
600     ret = cwd = afscp_DupFid(start);
601     fids = infids;
602     if (fids == NULL)
603         fids = fidstack_alloc();
604     if (fids == NULL) {
605         return NULL;
606     }
607
608     while (p && *p) {
609         q = strchr(p, '/');
610         if (q)
611             *q++ = 0;
612         if (strcmp(p, ".") == 0) {
613             /* do nothing */
614         } else if (strcmp(p, "..") == 0) {
615             ret = fidstack_pop(fids);
616             if (ret == NULL)
617                 ret = cwd;
618             else
619                 free(cwd);
620         } else {
621             ret = afscp_ResolveName(cwd, p);
622             if (ret == NULL) {
623                 afs_dprintf(("Lookup %s in %lu.%lu.%lu failed\n", p,
624                              cwd->fid.Volume, cwd->fid.Vnode,
625                              cwd->fid.Unique));
626                 free(cwd);
627                 if (infids == NULL)
628                     fidstack_free(fids);
629                 return NULL;
630             }
631             afs_dprintf(("Lookup %s in %lu.%lu.%lu->%lu.%lu.%lu\n", p,
632                          cwd->fid.Volume, cwd->fid.Vnode, cwd->fid.Unique,
633                          ret->fid.Volume, ret->fid.Vnode, ret->fid.Unique));
634             linkcount = 0;
635
636           retry:
637             if ((ret->fid.Vnode & 1) == 0) {    /* not a directory; check for link */
638                 code = afscp_GetStatus(ret, &s);
639                 if (code != 0) {
640                     if (infids == NULL)
641                         fidstack_free(fids);
642                     free(cwd);
643                     free(ret);
644                     return NULL;
645                 }
646                 if (s.FileType == SymbolicLink) {
647                     if (linkcount++ > 5) {
648                         afscp_errno = ELOOP;
649                         if (infids == NULL)
650                             fidstack_free(fids);
651                         free(cwd);
652                         free(ret);
653                         return NULL;
654                     }
655                     ret =
656                         afscp_HandleLink(ret, cwd, fids, follow, &s,
657                                          (q == NULL));
658                     if (ret == NULL) {
659                         free(cwd);
660                         if (infids == NULL)
661                             fidstack_free(fids);
662                         return NULL;
663                     }
664                     afs_dprintf(("   ....-> %lu.%lu.%lu\n", ret->fid.Volume,
665                                  ret->fid.Vnode, ret->fid.Unique));
666                     goto retry;
667                 } else {
668                     if (q != NULL) {
669                         afscp_errno = ENOTDIR;
670                         free(cwd);
671                         free(ret);
672                         if (infids == NULL)
673                             fidstack_free(fids);
674                         return NULL;
675                     }
676                 }
677             }
678             fidstack_push(fids, cwd);
679         }
680         cwd = ret;
681
682         while ((q != NULL) && (*q == '/'))
683             q++;
684         p = q;
685     }
686     if (infids == NULL)
687         fidstack_free(fids);
688     return ret;
689 }
690
691 /*!
692  * Resolve a path to a FID starting from the root volume
693  *
694  * \param[in]   path    full path
695  *
696  * \post Returns a venusfid representing the final element of path
697  *
698  * \note There are three cases:
699  *       (1) begins with /afs: start in root.afs of cell or home cell
700  *       (2) else begins with /: error
701  *       (3) else start in root.cell of cell or home cell
702  */
703 struct afscp_venusfid *
704 afscp_ResolvePath(const char *path)
705 {
706     struct afscp_venusfid *root, *ret;
707     struct afscp_cell *cell;
708     int code;
709     char *p, *q;
710     p = strdup(path);           /* so we can modify the string */
711     if (p == NULL) {
712         afscp_errno = ENOMEM;
713         return NULL;
714     }
715     cell = afscp_DefaultCell();
716     if (cell == NULL) {
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 *p;
747
748     /* so we can modify the string */
749     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(p);
763     return ret;
764 }