1 /* Copyright (c) 2008, XenSource Inc.
2 * 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 are met:
6 * * Redistributions of source code must retain the above copyright
7 * notice, this list of conditions and the following disclaimer.
8 * * Redistributions in binary form must reproduce the above copyright
9 * notice, this list of conditions and the following disclaimer in the
10 * documentation and/or other materials provided with the distribution.
11 * * Neither the name of XenSource Inc. nor the names of its contributors
12 * may be used to endorse or promote products derived from this software
13 * without specific prior written permission.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
19 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
23 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
24 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27 #include <stdio.h>
28 #include <errno.h>
29 #include <stdlib.h>
30 #include <string.h>
31
32 #include "relative-path.h"
33
34 #define sfree(ptr) \
35 do { \
36 free(ptr); \
37 ptr = NULL; \
38 } while (0)
39
40 /*
41 * count number of tokens between DELIMETER characters
42 */
43 static int
count_nodes(char * path)44 count_nodes(char *path)
45 {
46 int i;
47 char *tmp;
48
49 if (!path)
50 return 0;
51
52 for (i = 0, tmp = path; *tmp != '\0'; tmp++)
53 if (*tmp == DELIMITER)
54 i++;
55
56 return i;
57 }
58
59 /*
60 * return copy of next node in @path, or NULL
61 * @path is moved to the end of the next node
62 * @err is set to -errno on failure
63 * copy should be freed
64 */
65 static char *
next_node(char ** path,int * err)66 next_node(char **path, int *err)
67 {
68 int ret;
69 char *tmp, *start;
70
71 if (!path || !*path) {
72 *err = -EINVAL;
73 return NULL;
74 }
75
76 *err = 0;
77 start = *path;
78
79 for (tmp = *path; *tmp != '\0'; tmp++)
80 if (*tmp == DELIMITER) {
81 int size;
82 char *node;
83
84 size = tmp - start + 1;
85 node = malloc(size);
86 if (!node) {
87 *err = -ENOMEM;
88 return NULL;
89 }
90
91 ret = snprintf(node, size, "%s", start);
92 if (ret < 0) {
93 free(node);
94 *err = -EINVAL;
95 return NULL;
96 }
97
98 *path = tmp;
99 return node;
100 }
101
102 return NULL;
103 }
104
105 /*
106 * count number of nodes in common betwee @to and @from
107 * returns number of common nodes, or -errno on failure
108 */
109 static int
count_common_nodes(char * to,char * from)110 count_common_nodes(char *to, char *from)
111 {
112 int err, common;
113 char *to_node, *from_node;
114
115 if (!to || !from)
116 return -EINVAL;
117
118 err = 0;
119 common = 0;
120 to_node = NULL;
121 from_node = NULL;
122
123 do {
124 to_node = next_node(&to, &err);
125 if (err || !to_node)
126 break;
127
128 from_node = next_node(&from, &err);
129 if (err || !from_node)
130 break;
131
132 if (strncmp(to_node, from_node, MAX_NAME_LEN))
133 break;
134
135 ++to;
136 ++from;
137 ++common;
138 sfree(to_node);
139 sfree(from_node);
140
141 } while (1);
142
143 sfree(to_node);
144 sfree(from_node);
145
146 if (err)
147 return err;
148
149 return common;
150 }
151
152 /*
153 * construct path of @count '../', './' if @count is zero, or NULL on error
154 * result should be freed
155 */
156 static char *
up_nodes(int count)157 up_nodes(int count)
158 {
159 char *path, *tmp;
160 int i, ret, len, size;
161
162 if (!count)
163 return strdup("./");
164
165 len = strlen("../");
166 size = len * count;
167 if (size >= MAX_NAME_LEN)
168 return NULL;
169
170 path = malloc(size + 1);
171 if (!path)
172 return NULL;
173
174 tmp = path;
175 for (i = 0; i < count; i++) {
176 ret = sprintf(tmp, "../");
177 if (ret < 0 || ret != len) {
178 free(path);
179 return NULL;
180 }
181 tmp += ret;
182 }
183
184 return path;
185 }
186
187 /*
188 * return pointer to @offset'th node of path or NULL on error
189 */
190 static char *
node_offset(char * from,int offset)191 node_offset(char *from, int offset)
192 {
193 char *path;
194
195 if (!from || !offset)
196 return NULL;
197
198 for (path = from; *path != '\0'; path++) {
199 if (*path == DELIMITER)
200 if (--offset == 0)
201 return path + 1;
202 }
203
204 return NULL;
205 }
206
207 /*
208 * return a relative path from @from to @to
209 * result should be freed
210 */
211 char *
relative_path_to(char * from,char * to,int * err)212 relative_path_to(char *from, char *to, int *err)
213 {
214 int from_nodes, common;
215 char *to_absolute, *from_absolute;
216 char *up, *common_target_path, *relative_path;
217
218 *err = 0;
219 up = NULL;
220 to_absolute = NULL;
221 from_absolute = NULL;
222 relative_path = NULL;
223
224 if (strnlen(to, MAX_NAME_LEN) == MAX_NAME_LEN ||
225 strnlen(from, MAX_NAME_LEN) == MAX_NAME_LEN) {
226 EPRINTF("invalid input; max path length is %d\n",
227 MAX_NAME_LEN);
228 *err = -ENAMETOOLONG;
229 return NULL;
230 }
231
232 to_absolute = realpath(to, NULL);
233 if (!to_absolute) {
234 EPRINTF("failed to get absolute path of %s\n", to);
235 *err = -errno;
236 goto out;
237 }
238
239 from_absolute = realpath(from, NULL);
240 if (!from_absolute) {
241 EPRINTF("failed to get absolute path of %s\n", from);
242 *err = -errno;
243 goto out;
244 }
245
246 if (strnlen(to_absolute, MAX_NAME_LEN) == MAX_NAME_LEN ||
247 strnlen(from_absolute, MAX_NAME_LEN) == MAX_NAME_LEN) {
248 EPRINTF("invalid input; max path length is %d\n",
249 MAX_NAME_LEN);
250 *err = -ENAMETOOLONG;
251 goto out;
252 }
253
254 /* count nodes in source path */
255 from_nodes = count_nodes(from_absolute);
256
257 /* count nodes in common */
258 common = count_common_nodes(to_absolute + 1, from_absolute + 1);
259 if (common < 0) {
260 EPRINTF("failed to count common nodes of %s and %s: %d\n",
261 to_absolute, from_absolute, common);
262 *err = common;
263 goto out;
264 }
265
266 /* move up to common node */
267 up = up_nodes(from_nodes - common - 1);
268 if (!up) {
269 EPRINTF("failed to allocate relative path for %s: %d\n",
270 from_absolute, -ENOMEM);
271 *err = -ENOMEM;
272 goto out;
273 }
274
275 /* get path from common node to target */
276 common_target_path = node_offset(to_absolute, common + 1);
277 if (!common_target_path) {
278 EPRINTF("failed to find common target path to %s: %d\n",
279 to_absolute, -EINVAL);
280 *err = -EINVAL;
281 goto out;
282 }
283
284 /* get relative path */
285 if (asprintf(&relative_path, "%s%s", up, common_target_path) == -1) {
286 EPRINTF("failed to construct final path %s%s: %d\n",
287 up, common_target_path, -ENOMEM);
288 relative_path = NULL;
289 *err = -ENOMEM;
290 goto out;
291 }
292
293 out:
294 sfree(up);
295 sfree(to_absolute);
296 sfree(from_absolute);
297
298 return relative_path;
299 }
300