1 /* 2 * Copyright � 2007 Alistair Crooks. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 3. The name of the author may not be used to endorse or promote 13 * products derived from this software without specific prior written 14 * permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS 17 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 20 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE 22 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 24 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 25 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 26 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 #include <sys/types.h> 29 #include <sys/stat.h> 30 31 #include <fuse.h> 32 #include <stdio.h> 33 #include <stdlib.h> 34 #include <unistd.h> 35 36 #include "virtdir.h" 37 #include "defs.h" 38 39 /* utility comparison routine for sorting and searching */ 40 static int 41 compare(const void *vp1, const void *vp2) 42 { 43 const virt_dirent_t *tp1 = (const virt_dirent_t *) vp1; 44 const virt_dirent_t *tp2 = (const virt_dirent_t *) vp2; 45 46 return strcmp(tp1->name, tp2->name); 47 } 48 49 /* save `n' chars of `s' in allocated storage */ 50 static char * 51 strnsave(const char *s, int n) 52 { 53 char *cp; 54 55 if (n < 0) { 56 n = strlen(s); 57 } 58 NEWARRAY(char, cp, n + 1, "strnsave", return NULL); 59 (void) memcpy(cp, s, n); 60 cp[n] = 0x0; 61 return cp; 62 } 63 64 /* ensure intermediate directories exist */ 65 static void 66 mkdirs(virtdir_t *tp, const char *path, size_t size) 67 { 68 virt_dirent_t *ep; 69 char name[MAXPATHLEN]; 70 char *slash; 71 72 (void) strlcpy(name, path, sizeof(name)); 73 for (slash = name + 1 ; (slash = strchr(slash + 1, '/')) != NULL ; ) { 74 *slash = 0x0; 75 if ((ep = virtdir_find(tp, name, strlen(name))) == NULL) { 76 virtdir_add(tp, name, strlen(name), 'd', NULL, 0); 77 } 78 *slash = '/'; 79 } 80 } 81 82 /* get rid of multiple slashes in input */ 83 static int 84 normalise(const char *name, size_t namelen, char *path, size_t pathsize) 85 { 86 const char *np; 87 char *pp; 88 int done; 89 90 for (pp = path, np = name, done = 0 ; !done && (int)(pp - path) < pathsize - 1 && (int)(np - name) <= namelen ; ) { 91 switch(*np) { 92 case '/': 93 if (pp == path || *(pp - 1) != '/') { 94 *pp++ = *np; 95 } 96 np += 1; 97 break; 98 case 0x0: 99 done = 1; 100 break; 101 default: 102 *pp++ = *np++; 103 break; 104 } 105 } 106 /* XXX - trailing slash? */ 107 *pp = 0x0; 108 return (int)(pp - path); 109 } 110 111 /* initialise the tree */ 112 int 113 virtdir_init(virtdir_t *tp, const char *rootdir, struct stat *d, struct stat *f, struct stat *l) 114 { 115 (void) memcpy(&tp->dir, d, sizeof(tp->dir)); 116 tp->dir.st_mode = S_IFDIR | 0755; 117 tp->dir.st_nlink = 2; 118 (void) memcpy(&tp->file, f, sizeof(tp->file)); 119 tp->file.st_mode = S_IFREG | 0644; 120 tp->file.st_nlink = 1; 121 (void) memcpy(&tp->lnk, l, sizeof(tp->lnk)); 122 tp->lnk.st_mode = S_IFLNK | 0644; 123 tp->lnk.st_nlink = 1; 124 if (rootdir != NULL) { 125 tp->rootdir = strdup(rootdir); 126 } 127 return 1; 128 } 129 130 /* add an entry to the tree */ 131 int 132 virtdir_add(virtdir_t *tp, const char *name, size_t size, uint8_t type, const char *tgt, size_t tgtlen) 133 { 134 struct stat st; 135 char path[MAXPATHLEN]; 136 int pathlen; 137 138 if (tp->v == NULL) { 139 (void) stat(".", &st); 140 virtdir_init(tp, NULL, &st, &st, &st); 141 } 142 pathlen = normalise(name, size, path, sizeof(path)); 143 if (virtdir_find(tp, path, pathlen) != NULL) { 144 /* attempt to add a duplicate directory entry */ 145 return 0; 146 } 147 ALLOC(virt_dirent_t, tp->v, tp->size, tp->c, 10, 10, "virtdir_add", 148 return 0); 149 tp->v[tp->c].namelen = pathlen; 150 if ((tp->v[tp->c].name = strnsave(path, pathlen)) == NULL) { 151 return 0; 152 } 153 tp->v[tp->c].d_name = strrchr(tp->v[tp->c].name, '/') + 1; 154 tp->v[tp->c].type = type; 155 tp->v[tp->c].ino = (ino_t) random() & 0xfffff; 156 if (tgt != NULL) { 157 tp->v[tp->c].tgtlen = tgtlen; 158 tp->v[tp->c].tgt = strnsave(tgt, tgtlen); 159 } 160 tp->c += 1; 161 qsort(tp->v, tp->c, sizeof(tp->v[0]), compare); 162 mkdirs(tp, path, pathlen); 163 return 1; 164 } 165 166 /* delete an entry from the tree */ 167 int 168 virtdir_del(virtdir_t *tp, const char *name, size_t size) 169 { 170 virt_dirent_t *ep; 171 int i; 172 173 if ((ep = virtdir_find(tp, name, size)) == NULL) { 174 return 0; 175 } 176 i = (int)(ep - tp->v) / sizeof(tp->v[0]); 177 for (tp->c -= 1 ; i < tp->c ; i++) { 178 tp->v[i] = tp->v[i + 1]; 179 } 180 return 1; 181 } 182 183 /* find an entry in the tree */ 184 virt_dirent_t * 185 virtdir_find(virtdir_t *tp, const char *name, size_t namelen) 186 { 187 virt_dirent_t e; 188 char path[MAXPATHLEN]; 189 190 (void) memset(&e, 0x0, sizeof(e)); 191 e.namelen = normalise(name, namelen, path, sizeof(path)); 192 e.name = path; 193 return bsearch(&e, tp->v, tp->c, sizeof(tp->v[0]), compare); 194 } 195 196 /* return the virtual offset in the tree */ 197 int 198 virtdir_offset(virtdir_t *tp, virt_dirent_t *dp) 199 { 200 return (int)(dp - tp->v); 201 } 202 203 /* analogous to opendir(3) - open a directory, save information, and 204 * return a pointer to the dynamically allocated structure */ 205 VIRTDIR * 206 openvirtdir(virtdir_t *tp, const char *d) 207 { 208 VIRTDIR *dirp; 209 210 NEW(VIRTDIR, dirp, "openvirtdir", exit(EXIT_FAILURE)); 211 dirp->dirname = strdup(d); 212 dirp->dirnamelen = strlen(d); 213 dirp->tp = tp; 214 dirp->i = 0; 215 return dirp; 216 } 217 218 /* analogous to readdir(3) - read the next entry in the directory that 219 * was opened, and return a pointer to it */ 220 virt_dirent_t * 221 readvirtdir(VIRTDIR *dirp) 222 { 223 char *from; 224 225 for ( ; dirp->i < dirp->tp->c ; dirp->i++) { 226 from = (strcmp(dirp->dirname, "/") == 0) ? 227 &dirp->tp->v[dirp->i].name[1] : 228 &dirp->tp->v[dirp->i].name[dirp->dirnamelen + 1]; 229 if (strncmp(dirp->tp->v[dirp->i].name, dirp->dirname, 230 dirp->dirnamelen) == 0 && 231 *from != 0x0 && 232 strchr(from, '/') == NULL) { 233 return &dirp->tp->v[dirp->i++]; 234 } 235 } 236 return NULL; 237 } 238 239 /* free the storage associated with the virtual directory structure */ 240 void 241 closevirtdir(VIRTDIR *dirp) 242 { 243 free(dirp->dirname); 244 FREE(dirp); 245 } 246 247 /* find a target in the tree -- not quick! */ 248 virt_dirent_t * 249 virtdir_find_tgt(virtdir_t *tp, const char *tgt, size_t tgtlen) 250 { 251 /* we don't need no stinking binary searches */ 252 char path[MAXPATHLEN]; 253 int i; 254 255 (void) normalise(tgt, tgtlen, path, sizeof(path)); 256 for (i = 0 ; i < tp->c ; i++) { 257 if (tp->v[i].tgt && strcmp(tp->v[i].tgt, path) == 0) { 258 return &tp->v[i]; 259 } 260 } 261 return NULL; 262 } 263 264 /* kill all of the space allocated to the tree */ 265 void 266 virtdir_drop(virtdir_t *tp) 267 { 268 int i; 269 270 for (i = 0 ; i < tp->c ; i++) { 271 FREE(tp->v[i].name); 272 if (tp->v[i].tgt) { 273 FREE(tp->v[i].tgt); 274 } 275 } 276 FREE(tp->v); 277 } 278 279 /* return the value of the root directory of the tree */ 280 char * 281 virtdir_rootdir(virtdir_t *tp) 282 { 283 return tp->rootdir; 284 } 285 286 #ifdef VIRTDIR_DEBUG 287 static void 288 ptree(virtdir_t * tp) 289 { 290 int i; 291 292 for (i = 0 ; i < tp->c ; i++) { 293 printf("%s, tgt %s\n", tp->v[i].name, tp->v[i].tgt); 294 } 295 } 296 #endif 297 298 #ifdef VIRTDIR_DEBUG 299 int 300 main(int argc, char **argv) 301 { 302 virt_dirent_t *tp; 303 virtdir_t t; 304 struct stat st; 305 306 (void) memset(&t, 0x0, sizeof(t)); 307 stat(".", &st); 308 virtdir_add(&t, ".", 1, 'd', NULL, 0); 309 stat("..", &st); 310 virtdir_add(&t, "..", 2, 'd', NULL, 0); 311 st.st_mode = S_IFREG | 0644; 312 virtdir_add(&t, "file1", 5, 'f', NULL, 0); 313 ptree(&t); 314 virtdir_add(&t, "file2", 5, 'f', NULL, 0); 315 virtdir_add(&t, "file0", 5, 'f', NULL, 0); 316 virtdir_add(&t, "abcde", 5, 'f', NULL, 0); 317 virtdir_add(&t, "bcdef", 5, 'f', NULL, 0); 318 virtdir_add(&t, "a", 1, 'f', NULL, 0); 319 ptree(&t); 320 if ((tp = virtdir_find(&t, "a", 1)) == NULL) { 321 printf("borked2\n"); 322 } else { 323 printf("a found\n"); 324 } 325 virtdir_drop(&t); 326 exit(EXIT_SUCCESS); 327 } 328 #endif 329