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 #define FUSE_USE_VERSION	26
32 
33 #include <fuse.h>
34 #include <stdio.h>
35 #include <stdlib.h>
36 #include <unistd.h>
37 
38 #include "virtdir.h"
39 #include "defs.h"
40 
41  /* utility comparison routine for sorting and searching */
42 static int
43 compare(const void *vp1, const void *vp2)
44 {
45 	const virt_dirent_t	*tp1 = (const virt_dirent_t *) vp1;
46 	const virt_dirent_t	*tp2 = (const virt_dirent_t *) vp2;
47 
48 	return strcmp(tp1->name, tp2->name);
49 }
50 
51 /* save `n' chars of `s' in allocated storage */
52 static char *
53 strnsave(const char *s, int n)
54 {
55 	char	*cp;
56 
57 	if (n < 0) {
58 		n = strlen(s);
59 	}
60 	NEWARRAY(char, cp, n + 1, "strnsave", return NULL);
61 	(void) memcpy(cp, s, n);
62 	cp[n] = 0x0;
63 	return cp;
64 }
65 
66 /* ensure intermediate directories exist */
67 static void
68 mkdirs(virtdir_t *tp, const char *path, size_t size)
69 {
70 	virt_dirent_t	*ep;
71 	char		 name[MAXPATHLEN];
72 	char		*slash;
73 
74 	(void) strlcpy(name, path, sizeof(name));
75 	for (slash = name + 1 ; (slash = strchr(slash + 1, '/')) != NULL ; ) {
76 		*slash = 0x0;
77 		if ((ep = virtdir_find(tp, name, strlen(name))) == NULL) {
78 			virtdir_add(tp, name, strlen(name), 'd', NULL, 0);
79 		}
80 		*slash = '/';
81 	}
82 }
83 
84 /* get rid of multiple slashes in input */
85 static int
86 normalise(const char *name, size_t namelen, char *path, size_t pathsize)
87 {
88 	const char	*np;
89 	char		*pp;
90 	int		 done;
91 
92 	for (pp = path, np = name, done = 0 ;
93 	     !done && (unsigned)(pp - path) < pathsize - 1 &&
94 	     (unsigned)(np - name) <= namelen ; ) {
95 		switch(*np) {
96 		case '/':
97 			if (pp == path || *(pp - 1) != '/') {
98 				*pp++ = *np;
99 			}
100 			np += 1;
101 			break;
102 		case 0x0:
103 			done = 1;
104 			break;
105 		default:
106 			*pp++ = *np++;
107 			break;
108 		}
109 	}
110 	/* XXX - trailing slash? */
111 	*pp = 0x0;
112 	return (int)(pp - path);
113 }
114 
115 /* initialise the tree */
116 int
117 virtdir_init(virtdir_t *tp, const char *rootdir, struct stat *d, struct stat *f, struct stat *l)
118 {
119 	(void) memcpy(&tp->dir, d, sizeof(tp->dir));
120 	tp->dir.st_mode = S_IFDIR | 0755;
121 	tp->dir.st_nlink = 2;
122 	(void) memcpy(&tp->file, f, sizeof(tp->file));
123 	tp->file.st_mode = S_IFREG | 0644;
124 	tp->file.st_nlink = 1;
125 	(void) memcpy(&tp->lnk, l, sizeof(tp->lnk));
126 	tp->lnk.st_mode = S_IFLNK | 0644;
127 	tp->lnk.st_nlink = 1;
128 	if (rootdir != NULL) {
129 		tp->rootdir = strdup(rootdir);
130 	}
131 	return 1;
132 }
133 
134 /* add an entry to the tree */
135 int
136 virtdir_add(virtdir_t *tp, const char *name, size_t size, uint8_t type, const char *tgt, size_t tgtlen)
137 {
138 	struct stat	st;
139 	char		path[MAXPATHLEN];
140 	int		pathlen;
141 
142 	if (tp->v == NULL) {
143 		(void) stat(".", &st);
144 		virtdir_init(tp, NULL, &st, &st, &st);
145 	}
146 	pathlen = normalise(name, size, path, sizeof(path));
147 	if (virtdir_find(tp, path, pathlen) != NULL) {
148 		/* attempt to add a duplicate directory entry */
149 		return 0;
150 	}
151 	ALLOC(virt_dirent_t, tp->v, tp->size, tp->c, 10, 10, "virtdir_add",
152 			return 0);
153 	tp->v[tp->c].namelen = pathlen;
154 	if ((tp->v[tp->c].name = strnsave(path, pathlen)) == NULL) {
155 		return 0;
156 	}
157 	tp->v[tp->c].d_name = strrchr(tp->v[tp->c].name, '/') + 1;
158 	tp->v[tp->c].type = type;
159 	tp->v[tp->c].ino = (ino_t) random() & 0xfffff;
160 	if (tgt != NULL) {
161 		tp->v[tp->c].tgtlen = tgtlen;
162 		tp->v[tp->c].tgt = strnsave(tgt, tgtlen);
163 	}
164 	tp->c += 1;
165 	qsort(tp->v, tp->c, sizeof(tp->v[0]), compare);
166 	mkdirs(tp, path, pathlen);
167 	return 1;
168 }
169 
170 /* delete an entry from the tree */
171 int
172 virtdir_del(virtdir_t *tp, const char *name, size_t size)
173 {
174 	virt_dirent_t	*ep;
175 	unsigned	 i;
176 
177 	if ((ep = virtdir_find(tp, name, size)) == NULL) {
178 		return 0;
179 	}
180 	i = (int)(ep - tp->v);
181 	for (tp->c -= 1 ; i < tp->c ; i++) {
182 		tp->v[i] = tp->v[i + 1];
183 	}
184 	return 1;
185 }
186 
187 /* find an entry in the tree */
188 virt_dirent_t *
189 virtdir_find(virtdir_t *tp, const char *name, size_t namelen)
190 {
191 	virt_dirent_t	e;
192 	char		path[MAXPATHLEN];
193 
194 	(void) memset(&e, 0x0, sizeof(e));
195 	e.namelen = normalise(name, namelen, path, sizeof(path));
196 	e.name = path;
197 	return bsearch(&e, tp->v, tp->c, sizeof(tp->v[0]), compare);
198 }
199 
200 /* return the virtual offset in the tree */
201 int
202 virtdir_offset(virtdir_t *tp, virt_dirent_t *dp)
203 {
204 	return (int)(dp - tp->v);
205 }
206 
207 /* analogous to opendir(3) - open a directory, save information, and
208 * return a pointer to the dynamically allocated structure */
209 VIRTDIR *
210 openvirtdir(virtdir_t *tp, const char *d)
211 {
212 	VIRTDIR	*dirp;
213 
214 	NEW(VIRTDIR, dirp, "openvirtdir", exit(EXIT_FAILURE));
215 	dirp->dirname = strdup(d);
216 	dirp->dirnamelen = strlen(d);
217 	dirp->tp = tp;
218 	dirp->i = 0;
219 	return dirp;
220 }
221 
222 /* analogous to readdir(3) - read the next entry in the directory that
223 * was opened, and return a pointer to it */
224 virt_dirent_t *
225 readvirtdir(VIRTDIR *dirp)
226 {
227 	char	*from;
228 
229 	for ( ; dirp->i < dirp->tp->c ; dirp->i++) {
230 		from = (strcmp(dirp->dirname, "/") == 0) ?
231 			&dirp->tp->v[dirp->i].name[1] :
232 			&dirp->tp->v[dirp->i].name[dirp->dirnamelen + 1];
233 		if (strncmp(dirp->tp->v[dirp->i].name, dirp->dirname,
234 				dirp->dirnamelen) == 0 &&
235 		    *from != 0x0 &&
236 		    strchr(from, '/') == NULL) {
237 			return &dirp->tp->v[dirp->i++];
238 		}
239 	}
240 	return NULL;
241 }
242 
243 /* free the storage associated with the virtual directory structure */
244 void
245 closevirtdir(VIRTDIR *dirp)
246 {
247 	free(dirp->dirname);
248 	FREE(dirp);
249 }
250 
251 /* find a target in the tree -- not quick! */
252 virt_dirent_t *
253 virtdir_find_tgt(virtdir_t *tp, const char *tgt, size_t tgtlen)
254 {
255 	/* we don't need no stinking binary searches */
256 	unsigned	i;
257 	char		path[MAXPATHLEN];
258 
259 	(void) normalise(tgt, tgtlen, path, sizeof(path));
260 	for (i = 0 ; i < tp->c ; i++) {
261 		if (tp->v[i].tgt && strcmp(tp->v[i].tgt, path) == 0) {
262 			return &tp->v[i];
263 		}
264 	}
265 	return NULL;
266 }
267 
268 /* kill all of the space allocated to the tree */
269 void
270 virtdir_drop(virtdir_t *tp)
271 {
272 	unsigned	i;
273 
274 	for (i = 0 ; i < tp->c ; i++) {
275 		FREE(tp->v[i].name);
276 		if (tp->v[i].tgt) {
277 			FREE(tp->v[i].tgt);
278 		}
279 	}
280 	FREE(tp->v);
281 }
282 
283 /* return the value of the root directory of the tree */
284 char *
285 virtdir_rootdir(virtdir_t *tp)
286 {
287 	return tp->rootdir;
288 }
289 
290 #ifdef VIRTDIR_DEBUG
291 static void
292 ptree(virtdir_t * tp)
293 {
294 	int	i;
295 
296 	for (i = 0 ; i < tp->c ; i++) {
297 		printf("%s, tgt %s\n", tp->v[i].name, tp->v[i].tgt);
298 	}
299 }
300 #endif
301 
302 #ifdef VIRTDIR_DEBUG
303 int
304 main(int argc, char **argv)
305 {
306 	virt_dirent_t	*tp;
307 	virtdir_t		 t;
308 	struct stat		 st;
309 
310 	(void) memset(&t, 0x0, sizeof(t));
311 	stat(".", &st);
312 	virtdir_add(&t, ".", 1, 'd', NULL, 0);
313 	stat("..", &st);
314 	virtdir_add(&t, "..", 2, 'd', NULL, 0);
315 	st.st_mode = S_IFREG | 0644;
316 	virtdir_add(&t, "file1", 5, 'f', NULL, 0);
317 	ptree(&t);
318 	virtdir_add(&t, "file2", 5, 'f', NULL, 0);
319 	virtdir_add(&t, "file0", 5, 'f', NULL, 0);
320 	virtdir_add(&t, "abcde", 5, 'f', NULL, 0);
321 	virtdir_add(&t, "bcdef", 5, 'f', NULL, 0);
322 	virtdir_add(&t, "a", 1, 'f', NULL, 0);
323 	ptree(&t);
324 	if ((tp = virtdir_find(&t, "a", 1)) == NULL) {
325 		printf("borked2\n");
326 	} else {
327 		printf("a found\n");
328 	}
329 	virtdir_drop(&t);
330 	exit(EXIT_SUCCESS);
331 }
332 #endif
333